Unsoundness due to variance of trait objects WRT associated types

[trha]

IIUC currently a trait object is always covariant in its associated types, regardless of their positions.

trait Foo {
  type A;
  // `A` appears in contravariant position
  fn foo(&self, _: Self::A) {}
}

impl Foo for () {
  type A = &'static ();
}

fn bar<'a>(_: &'a dyn Foo<A = &'a ()>) {}

fn main() {
  let x = ();
  // Let 'x be the lifetime of `&x`
  // 'static <: 'x
  // `dyn Foo` covariant to `Foo::A`
  // `&dyn Foo<A = &'static ()>` <: `&dyn Foo<A = &'x ()>`
  bar(&x);
}

This makes it possible to pass a non-static reference to a function expecting a static reference:

use std::marker::PhantomData;

trait Foo {
    type A;
    type B;
    fn foo(&self, x: Self::A) -> Self::B;
}

struct Bar<T>(PhantomData<T>);

impl<T: 'static> Foo for Bar<T> {
    type A = &'static T;
    type B = &'static T;
    fn foo(&self, x: Self::A) -> Self::B {
        x
    }
}

fn bad<'a, T>(x: &dyn Foo<A = &'a T, B = &'static T>, k: &'a T) -> &'static T {
    x.foo(k)
}

/// Extends the lifetime of an arbitrary reference.
fn extend<'a, T>(x: &'a T) -> &'static T {
    bad(&Bar(PhantomData), x)
}

fn dangle_ref() -> &'static String {
    let x = "hello world".to_string();
    extend(&x)
}

fn main() {
    // This segfaults.
    println!("{}", dangle_ref());
}

[memoryruins]

With rustc 1.0.0 ..= 1.16.0, the following error was emitted:

error[E0495]: cannot infer an appropriate lifetime for lifetime parameter 'a in function call due to conflicting requirements
  --> <source>:25:5
   |
25 |     bad(&Bar(PhantomData), x)
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^
   |
note: first, the lifetime cannot outlive the lifetime 'a as defined on the body at 24:45...
  --> <source>:24:46
   |
24 |   pub fn extend<'a, T>(x: &'a T) -> &'static T {
   |  ______________________________________________^ starting here...
25 | |     bad(&Bar(PhantomData), x)
26 | | }
   | |_^ ...ending here
note: ...so that reference does not outlive borrowed content
  --> <source>:25:28
   |
25 |     bad(&Bar(PhantomData), x)
   |                            ^
   = note: but, the lifetime must be valid for the static lifetime...
note: ...so that types are compatible (expected &'static T, found &T)
  --> <source>:25:9
   |
25 |     bad(&Bar(PhantomData), x)
   |         ^^^^^^^^^^^^^^^^^

error: aborting due to previous error

Compiler returned: 101

[Mark-Simulacrum]

@nikomatsakis -- this looks plausibly similar to #44454, but I don't know enough to be certain.

[RalfJung]

Oh wow how are these not invariant? Cc @eddyb

[spastorino]

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

[spastorino]

Just in case, in my last action I've removed I-nominated by accident and added it back :).