auto trait candidate selection is unsound

[lcnr]

struct Always<T, U>(T, U);
unsafe impl<T, U> Send for Always<T, U> {}
struct Foo<T, U>(Always<T, U>);

trait False {}
unsafe impl<U: False> Send for Foo<u32, U> {}

trait WithAssoc {
    type Output;
}
impl<T: Send> WithAssoc for T {
    type Output = Self;
}
impl WithAssoc for Foo<u32, ()> {
    type Output = Box<i32>;
}

fn generic<T, U>(v: Foo<T, U>, f: fn(<Foo<T, U> as WithAssoc>::Output) -> i32) {
    f(foo(v));
}

fn foo<T: Send>(x: T) -> <T as WithAssoc>::Output {
    x
}

fn main() {
    generic(Foo(Always(0, ())), |b| *b);
}

Segmentation fault (core dumped)

---

There are two impls of Send for Foo, the explicit impl<U: False> Send for Foo<u32, U> and the implicit one if all fields are Send. The implicit one always holds in this example.

Candidate selection only acknowledges the existence of the implicit impl if the explicit one is known to not apply even when ignoring where bounds.

For Foo<T, U>: Send candidate selection can't use impl<U: False> Send for Foo<u32, U>, because Foo<T, U> is more generic than Foo<u32, U>. So we use the implicit impl which always applies.

For Foo<u32, ()> the explicit impl does apply, ignoring where bounds. This impl gets rejected however, as (): False does not hold. As we don't consider the implicit impl in this case we therefore accept impl WithAssoc for Foo<u32, ()> during coherence.

We now have two arbitrary overlapping impls which is unsound.

[lcnr]

modifying main to the following this unsoundness exists since version 1.0

fn main() {
    fn deref(b: Box<i32>) -> i32 {
        *b
    }
    generic(Foo(Always(0, ())), deref);
}

[steffahn]

Using e.g. Unpin or UnwindSafe instead of Send allows you to remove the unsafe. (Of course it won’t work with Rust 1.0 anymore with those.)

---

@rustbot label A-traits, T-compiler

[jackh726]

I think there was some discussion previously in wg-traits that an implicit impl should never be considered if there is an explicit impl. And I think that makes sense and would fix this. It isn't fully backwards compatible though, but I'm unsure how often that would get run into in practice.

[apiraino]

Assigning priority as discussed as part of the Prioritization Working Group procedure and removing I-prioritize.

@rustbot label -I-prioritize +P-high

[lcnr]

a more beautiful example ✨ https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=7dcd002a139a2c2d18b2651aeca8a7c0

[pnkfelix]

Visited for P-high review

Work seems to be ongoing in #93367, including a lint that fires today, so at least people are aware of the issue, I hope.

[pnkfelix]

visiting for 2023 Q1 P-high review

@lcnr am I correct in thinking that resolving this is blocked on #107374 ?

[pnkfelix]

also, assigning this to @lcnr based on an assumption that #107374 will resolve this

[lcnr]

The current status here is that there's a lint (#93367) which warns on impls which will change behavior due to the fix. Actually landing the fix breaks some crates and keeping the behavior of imagequant would require the stabilization of marker_trait_attrs (which is blocked on the new trait solver). See #85048 (comment)

I just saw that @kornelski actually rewrote imagequant to silence the lint in ImageOptim/libimagequant@d69cbfd in a way which does not rely on marker_traits 🤔 ❤️

So maybe we don't actually have to land the new solver for this.

Going to mentor someone to:

• rebase discard default auto trait impls if explicit ones exist #85048 and rerun crater
• open PRs to fix the remaining crater regressions
• potentially land the new PR, closing this soundness hole

Please open a thread in #t-types on zulip if you get stuck

[Ddystopia]

Hello, can I give it a try?

[lcnr]

fixed by #113312