Subtyping rules for associated type projections

[nikomatsakis]

@Kimundi showed me this example program which fails to compile. Here is a reduced version:

fn main() {
    let s: &'static str = "foo";
    let b: B<()> = B::new(s, ());
    b.get_short();
}

trait IntoRef<'a> {
    type T: Clone;
    fn into_ref(self, &'a str) -> Self::T;
}

impl<'a> IntoRef<'a> for () {
    type T = &'a str;
    fn into_ref(self, s: &'a str) -> &'a str {
        s
    }
}

struct B<'a, P: IntoRef<'a>>(P::T);

impl<'a, P: IntoRef<'a>> B<'a, P> {
    fn new(s: &'a str, i: P) -> B<'a, P> {
        B(i.into_ref(s))
    }

    fn get_short(&self) -> P::T {
        self.0.clone()
    }
}

This yields:

lunch-box. rustc ~/tmp/kimundi.rs
/home/nmatsakis/tmp/kimundi.rs:3:20: 3:26 error: cannot infer an appropriate lifetime for lifetime parameter `'a` due to conflicting requirements
/home/nmatsakis/tmp/kimundi.rs:3     let b: B<()> = B::new(s, ());
                                                    ^~~~~~
/home/nmatsakis/tmp/kimundi.rs:4:5: 4:18 note: first, the lifetime must be contained by the method call at 4:4...
/home/nmatsakis/tmp/kimundi.rs:4     b.get_short();
                                     ^~~~~~~~~~~~~
/home/nmatsakis/tmp/kimundi.rs:4:5: 4:18 note: ...so type `&str` of expression is valid during the expression
/home/nmatsakis/tmp/kimundi.rs:4     b.get_short();
                                     ^~~~~~~~~~~~~
/home/nmatsakis/tmp/kimundi.rs:3:27: 3:28 note: but, the lifetime must also be contained by the expression at 3:26...
/home/nmatsakis/tmp/kimundi.rs:3     let b: B<()> = B::new(s, ());
                                                           ^
/home/nmatsakis/tmp/kimundi.rs:3:27: 3:28 note: ...so that auto-reference is valid at the time of borrow
/home/nmatsakis/tmp/kimundi.rs:3     let b: B<()> = B::new(s, ());
                                                           ^
error: aborting due to previous error

However, if you change the type of b to B<'static, ()>, it builds. Seems like there is a missing constraint somewhere in the region inference graph.

[nikomatsakis]

I tagged this as associated items as my best guess is that the constraint that would P::T to affect 'a is somehow getting lost.

[nikomatsakis]

I think the problem is actually variance, as @Kimundi guessed initially, or perhaps a question of what the subtyping rules for associated types ought to be. Let's consider a simple trait Foo:

trait Foo {
    type Output;

    fn method(&self);
}

The normal variance inference will conclude that Foo is contravariant w/r/t Self, because Self only appears in a contravariant position in the method signature for method().

Now imagine I have <U as Foo>::Output and <U' as Foo>::Output, where U <: U'. What can we say about the relationship between U::Output and U'::Output, if any?

My first thought was that since <U' as Foo> <: <U as Foo> (since Foo is contravariant), we could say that U'::Output <: U::Output. But that doesn't seem to make any sense -- after all, this contravariance result is based purely on method signatures, and has no relation to the associated type definitions. And anyway we can easily concoct some examples where that relationship doesn't hold:

struct Bar<T>(T); // covariant in T
impl<T> Foo for Bar<T> {
    type Output = fn() -> T;
}

Now if U=Bar<T> and U'=Bar<T'>, where T <: T', then U <: U'. So we'd expect that if my initial rules were correct, then U'::Output <: U::Output -- and hence fn() -> T' <: fn() -> T. But in fact fn() -> T <: fn() -> T', since fn types are covariant in their return type and T <: T'. So in this case U::Output <: U'::Output.

But clearly we also can't conclude that U::Output <: U'::Output in general either. After all, we can easily build another example where the relationship is the opposite:

struct Baz<T>(T);
impl<T> Foo for Baz<T> {
    type Output = fn(T);
}

So it seems like the only thing we can conclude is that TraitRef::ItemName <: TraitRef'::ItemName iff TraitRef == TraitRef'. In other words, a projection type is invariant with respect to its trait reference. This seems awfully strong but it's not clear to me how to make a weaker rule, at least not without some kind of declaration in the trait somehow relating the variance of Output to the trait inputs.

[pnkfelix]

Yes, I think your examples have hit it on the head: In general one cannot draw any conclusion about the relationship between U::Output and U'::Output without adding constraints (in the trait definition itself) on (1.) what the implementing type chooses for the Output associated item and/or (2.) the variance of that associated type with respect to the trait inputs and/or the Self type. And we do not currently have anyway to express such constraints in the language, AFAICT.

[nikomatsakis]

@Kimundi I'll try to get a fix up for this today, but in the meantime you CAN workaround it by adding a method like this to the trait:

fn dummy(&self, x: &'a ()) -> &'a () { x }

[nikomatsakis]

I already implemented the fix but I'm a bit stymied on how to write nice unit tests without support for where for<'a> &'a T : Trait style where clauses. I may just go off on a yak shave and implement those, which I've been meaning to do for other reasons.

[nikomatsakis]

Fix enqueued (#21747).

[Kimundi]

Thanks! I'll use the workaround for now.