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