HRTB on subtrait unsoundly provides HTRB on supertrait with weaker implied bounds

[steffahn]

I’m giving an exploitation below at the end of this description. This is my interpretation of where exactly the unsoundness lies:

If I have a trait hierarchy

trait Subtrait<'a, 'b, R>: Supertrait<'a, 'b> {}
trait Supertrait<'a, 'b> {}

then a higher ranked trait bound (HRTB) like this

for<'a, 'b> Subtrait<'a, 'b, &'b &'a ()>

does/should only apply to such lifetimes 'a, 'b that fulfill the outlives-relation 'a: 'b.
('a: 'b is needed for &'b &'a () to be a valid type.)

However, the bound

for<'a, 'b> Subtrait<'a, 'b, &'b &'a ()>

appears to imply the bound

for<'a, 'b> Supertrait<'a, 'b>,

and in this one, the lifetimes 'a and 'b are universally quantified without any implicit outlives-relation.

This implication is demonstrated below:

fn need_hrtb_subtrait<S>()
where
    S: for<'a, 'b> Subtrait<'a, 'b, &'b &'a ()>,
{
    need_hrtb_supertrait::<S>() // <- this call works
}

fn need_hrtb_supertrait<S>()
where
    S: for<'a, 'b> Supertrait<'a, 'b>,
{
}

(playground)

One could of course debate whether for<'a, 'b> Subtrait<'a, 'b, &'b &'a ()> should perhaps in-fact include a for<'a, 'b> Supertrait<'a, 'b> bound, but that seems kind-of weird IMO, and also the following code demonstrates that you only need Supertrait<'a, 'b> with 'a: 'b for a fully generic Subtrait<'a, 'b, &'b &'a ()> implementation:

struct MyStruct;
impl<'a: 'b, 'b> Supertrait<'a, 'b> for MyStruct {}
impl<'a, 'b> Subtrait<'a, 'b, &'b &'a ()> for MyStruct {}

fn main() {
    need_hrtb_subtrait::<MyStruct>();
}

(playground)

---

Finally, here’s how to turn this into actual UB:

trait Subtrait<'a, 'b, R>: Supertrait<'a, 'b> {}
trait Supertrait<'a, 'b> {
    fn convert<T: ?Sized>(x: &'a T) -> &'b T;
}

fn need_hrtb_subtrait<'a_, 'b_, S, T: ?Sized>(x: &'a_ T) -> &'b_ T
where
    S: for<'a, 'b> Subtrait<'a, 'b, &'b &'a ()>,
{
    need_hrtb_supertrait::<S, T>(x) // <- this call works
}

fn need_hrtb_supertrait<'a_, 'b_, S, T: ?Sized>(x: &'a_ T) -> &'b_ T
where
    S: for<'a, 'b> Supertrait<'a, 'b>,
{
    S::convert(x)
}

struct MyStruct;
impl<'a: 'b, 'b> Supertrait<'a, 'b> for MyStruct {
    fn convert<T: ?Sized>(x: &'a T) -> &'b T {
        x
    }
}
impl<'a, 'b> Subtrait<'a, 'b, &'b &'a ()> for MyStruct {}

fn extend_lifetime<'a, 'b, T: ?Sized>(x: &'a T) -> &'b T {
    need_hrtb_subtrait::<MyStruct, T>(x)
}

fn main() {
    let d;
    {
        let x = "Hello World".to_string();
        d = extend_lifetime(&x);
    }
    println!("{}", d);
}

��~��U�

(playground)

This demonstration compiles since Rust 1.7.

@rustbot modify labels: T-compiler, A-traits, A-lifetimes, A-typesystem
and someone please add “I-unsound 💥”.

[jackh726]

Just wanted to write a couple thoughts:
First,

trait Supertrait<'a, 'b, R>: Subtrait<'a, 'b> {}

is kind of the wrong naming. Here Subtrait is actually a supertrait of Supertrait. Naming is backwards.

Second, I wonder if this might just be solved to make this fn convert<T: ?Sized>(x: &'a T) -> &'b T; not allowed as-is. Theoretically, that shouldn't be WF unless 'a: 'b.

[steffahn]

Here Subtrait is actually a supertrait of Supertrait. Naming is backwards.

How did I miss this… One moment, let me fix this…… Edit: Done.

I wonder if this might just be solved to make this fn convert<T: ?Sized>(x: &'a T) -> &'b T; not allowed as-is. Theoretically, that shouldn't be WF unless 'a: 'b.

Why should it not be WF? The implementation could just panic!() unconditionally. The only bounds necessary for the type are T: 'a and T: 'b. By the way are you referring to the declaration of the implementation of this method that should be rejected? Edit: Probably referring to the declaration, since the implementation does come with a 'a: 'b bound anyways.

[JohnTitor]

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

[pnkfelix]

Discussed in T-compiler triage meeting. Added relevant labels. Believed to be known long-standing issue, and something that the traits WG wants to address alongside improvements to trait infrastructure.

But: Not a release blocker, so downgrading to P-high.

[nikomatsakis]

Strongly related to #25860

[lcnr]

here's an example where the trait hierarchy is a bit more problematic.

trait Subtrait<T>: Supertrait {}
trait Supertrait {
    fn action(self);
}

fn subs_to_soup<T, U>(x: T)
where
    T: Subtrait<U>,
{
    soup(x)
}

fn soup<T: Supertrait>(x: T) {
    x.action();
}

impl<'a, 'b: 'a> Supertrait for (&'b str, &mut &'a str) {
    fn action(self) {
        *self.1 = self.0;
    }
}

impl<'a, 'b> Subtrait<&'a &'b str> for (&'b str, &mut &'a str) {}

fn main() {
    let mut d = "hi";
    {
        let x = "Hello World".to_string();
        subs_to_soup((x.as_str(), &mut d));
    }
    println!("{}", d);
}

we should require trait solving to prove wf for the types it creates while matching impls ✨