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 :).

[nikomatsakis]

Wait, these are supposed to be invariant. This is definitely a bug. It would be great to figure out just which nightly regressed this, maybe somebody can run cargo bisect?

@rustbot cleanup

[nikomatsakis]

Er, I guess I meant this?

@rustbot ping cleanup

[rustbot]

Hey Cleanup Crew ICE-breakers! This bug has been identified as a good
"Cleanup ICE-breaking candidate". In case it's useful, here are some
instructions for tackling these sorts of bugs. Maybe take a look?
Thanks! <3

cc @AminArria @chrissimpkins @contrun @DutchGhost @elshize @ethanboxx @h-michael @HallerPatrick @hdhoang @hellow554 @imtsuki @jakevossen5 @kanru @KarlK90 @LeSeulArtichaut @MAdrianMattocks @matheus-consoli @mental32 @nmccarty @Noah-Kennedy @pard68 @PeytonT @pierreN @Redblueflame @RobbieClarken @RobertoSnap @robjtede @SarthakSingh31 @senden9 @shekohex @sinato @spastorino @turboladen @woshilapin @yerke

[hellow554]

searched toolchains nightly-2016-06-01 through nightly-2020-01-01
regression in nightly-2017-03-12

e4eb964...824c9eb

Previous error message:

error[E0495]: cannot infer an appropriate lifetime for lifetime parameter 'a in function call due to conflicting requirements
  --> src/main.rs:25:5
   |
25 |     bad(&Bar(PhantomData), x)
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^
   |
note: first, the lifetime cannot outlive the lifetime 'a as defined on the body at 24:41...
  --> src/main.rs:24:42
   |
24 |   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
  --> src/main.rs: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)
  --> src/main.rs:25:9
   |
25 |     bad(&Bar(PhantomData), x)
   |         ^^^^^^^^^^^^^^^^^

error: aborting due to previous error

I used a slightly modified variant (just removed the dyn IIRC):

Code used

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: &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());
}

[varkor]

Most likely candidate seems to be #40319, cc @eddyb.

[nikomatsakis]

Thanks! Super useful.

[spastorino]

After discussing a bit with @nikomatsakis this sounds more like P-critical than P-high.

[bjorn3]

@rustbot modify labels:-E-needs-bisection

[nikomatsakis]

Crater run from the fix suggested 16 non-spurious regressions (thanks to @bjorn3 for the analysis).

I was thinking about that and I realize that it's plausible that we could do variance inference on associated types and use that to inform the variance for dyn types. It is sensible, for example, that a dyn Iterator<Item = X> is covariant with respect to X (that is the trait used in one of the affected examples).

I'm a bit nervous about this though. For one thing, the core operations exposed by a dyn type are clearly just its methods, but people can also project out from dyn types (though that projection is generally considered invariant over the input types). But for another, it seems to give rise to some asymmetry and complexity around traits and variance that we have thus far avoided (and which I might prefer to continue to avoid).