Repository: rust
Issue: HRTB on subtrait unsoundly provides HTRB on supertrait with weaker implied bounds
Labels: A-type-system,A-lifetimes,A-trait-system,P-high,T-compiler,I-unsound,C-bug,S-bug-has-test,T-types,A-implied-bounds,A-higher-ranked

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
```rust
trait Subtrait<'a, 'b, R>: Supertrait<'a, 'b> {}
trait Supertrait<'a, 'b> {}
```
then a higher ranked trait bound (HRTB) like this
```rust
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 
```rust
for<'a, 'b> Subtrait<'a, 'b, &'b &'a ()>
```
appears to imply the bound
```rust
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:
```rust
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](https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=6c498c0767464cf079ce57b6e385ebd0))

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:
```rust
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](https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=58afccefecc6f224a4a4757cc5a165be))

<hr>

Finally, here’s how to turn this into actual UB:
```rust
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](https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=abafc3ee064eda1aace72d2e71759b8d))

This demonstration compiles since Rust `1.7`.

@rustbot modify labels: T-compiler, A-traits, A-lifetimes, A-typesystem
and someone please add “I-unsound 💥”.