Coherence can be bypassed by an indirect impl for a trait object

[arielb1]

Comments

The check for manual impl Object for Object only makes sure there is no direct impl Object for dyn Object - it does not consider such indirect impls. Therefore, you can write a blanket impl<T: ?Sized> Object for T that conflicts with the builtin impl Object for dyn Object.

Reproducer

edit: minimal reproducer from #57893 (comment)

trait Object<U> {
    type Output;
}

impl<T: ?Sized, U> Object<U> for T {
    type Output = U;
}

fn foo<T: ?Sized, U>(x: <T as Object<U>>::Output) -> U {
    x
}

fn transmute<T, U>(x: T) -> U {
    foo::<dyn Object<U, Output = T>, U>(x)
}

---

I had some difficulties with getting the standard "incoherence ICE" reproducer, because the object candidate supersedes the impl candidate in selection. So here's a "transmute_lifetime" reproducer.

trait Object {
    type Output;
}

trait Marker<'b> {}
impl<'b> Marker<'b> for dyn Object<Output=&'b u64> {}

impl<'b, T: ?Sized + Marker<'b>> Object for T {
    type Output = &'static u64;
}

fn foo<'a, 'b, T: Marker<'b> + ?Sized>(x: <T as Object>::Output) -> &'a u64 {
    x
}

fn transmute_lifetime<'a, 'b>(x: &'a u64) -> &'b u64 {
    foo::<dyn Object<Output=&'a u64>>(x)
}

// And yes this is a genuine `transmute_lifetime`!
fn get_dangling<'a>() -> &'a u64 {
    let x = 0;
    transmute_lifetime(&x)
}

fn main() {
    let r = get_dangling();
    println!("{}", r);
}

Duplicates, see also

• Associated type constraints on super traits allowing for unsound transmutation to trait objects  #114389

[scalexm]

@arielb1 Interesting. I guess we would need a deeper check, something along the lines of:

impl<T> Object for SomeType<T> where WC {
/* ... */
}

// If the following goal has a non-empty set of solutions, reject the impl.
exists<T> {
    exists<U> {
        Unify(dyn Object<Output = U>, SomeType<T>),
        dyn Object<Output = U>: WC
    }
}

cc @nikomatsakis

[arielb1]

Sure.

What makes this non-trivial is auto-traits (dyn Object + Send is a distinct wrt. unification from dyn Object), and to some extent binders (unless you ignore them in unification). i.e., supposing the impl you have is

impl<T> Object<'a> for SomeType<T> where WC

Then the "ideal" lowering would be something of this format:

// If the following goal has a non-empty set of solutions, reject the impl.
exists<T: type, 'a('x): lifetime -> lifetime, U('x): lifetime -> type, AT: list of auto-traits> [
    Unify(dyn for<'s> Object<'a('s), Output = U('s)> + AT, SomeType<T>),
    dyn for<'s> Object<'a('s), Output = U('s)> + AT: WC
}

If you ignore binders in unification (i.e., you consider for<'a> Object<'a, Output=&'a T> to be the same as Object<'x, Output=&'y T> in coherence), then you don't have to deal with the HRTB problem, but you still have to deal with auto-traits:

// If the following goal has a non-empty set of solutions, reject the impl.
exists<T: type, 'a: lifetime, U: type, AT: list of auto-traits> [
    Unify(dyn Object<'a, Output = U> + AT, SomeType<T>),
    dyn Object<'a, Output = U> + AT: WC
}

While I don't think this is insurmountable, it is fairly annoying and places some restrictions on how you encode auto-traits.

[Aaron1011]

I'm interested in working on this.

[Aaron1011]

It turns out that only one trait is necessary to reproduce this: (playground)

trait Object {
    type Output;
}

impl<T: ?Sized> Object for T {
    type Output = &'static u64;
}

fn foo<'a, T: ?Sized>(x: <T as Object>::Output) -> &'a u64 {
    x
}

fn transmute_lifetime<'a, 'b>(x: &'a u64) -> &'b u64 {
    foo::<dyn Object<Output=&'a u64>>(x)
}

// And yes this is a genuine `transmute_lifetime`!
fn get_dangling<'a>() -> &'a u64 {
    let x = 0;
    transmute_lifetime(&x)
}

fn main() {
    let r = get_dangling();
    println!("{}", r);
}

This seems quite bad, as simply writing a blanket impl is enough to expose the issue.

[Aaron1011]

One way to fix this issue would be the following:

If a trait has any associated items, and a blanket impl exists for it, that trait cannot be object-safe.

This is pretty extreme - however, the only other solution I can think of would be to deny all blanket impls of a trait with associated items - which seems even worse, given that the trait might not have even been object-safe to begin with.

[Centril]

Unfortunately, it gets worse. Here's an implementation of mem::transmute in safe Rust:

trait Object<U> {
    type Output;
}

impl<T: ?Sized, U> Object<U> for T {
    type Output = U;
}

fn foo<T: ?Sized, U>(x: <T as Object<U>>::Output) -> U {
    x
}

fn transmute<T, U>(x: T) -> U {
    foo::<dyn Object<U, Output = T>, U>(x)
}

I think blame should be assigned to not normalizing <T as Object<U>>::Output to U in fn foo. If that happened, foo::<dyn Object<U, Output = T>, U>(x) would not type-check.

I checked the code above with godbolt and the problem has existed since Rust 1.0.0.

[jonas-schievink]

The first comments in the thread seem to indicate that the problem is instead with the blanket impl itself being accepted by the compiler.

If I understood correctly, @Centril's impl above can be applied to dyn Object<U, Output=T> for any U and T, and defines Output=U. However, a trait object like dyn Object<U, Output=T> already provides an implicit impl with the same input types, but a different output type, which is incoherent.

[jonas-schievink]

Seems like a good idea to discuss in language and compiler team, nominating.