associated types in generics cause lifetime invariance

[tamird]

playground

trait WithAssoc {
    type Assoc;
}

struct ImplsAssoc<'a> {
    phantom: core::marker::PhantomData<&'a ()>,
}

impl WithAssoc for ImplsAssoc<'_> {
    type Assoc = ();
}

struct Holder<W: WithAssoc> {
    foo: W,
    bar: W::Assoc,
}

struct CovariantHolder<W: WithAssoc<Assoc = Assoc>, Assoc = <W as WithAssoc>::Assoc> {
    foo: W,
    bar: Assoc,
}

// This doesn't compile.
fn invariant<'a: 'b, 'b>(x: Holder<ImplsAssoc<'a>>) -> Holder<ImplsAssoc<'b>> {
    x
}

// This compiles.
fn covariant<'a: 'b, 'b>(x: CovariantHolder<ImplsAssoc<'a>>) -> CovariantHolder<ImplsAssoc<'b>> {
    x
}

24 | fn invariant<'a: 'b, 'b>(x: Holder<ImplsAssoc<'a>>) -> Holder<ImplsAssoc<'b>> {
   |              --      -- lifetime `'b` defined here
   |              |
   |              lifetime `'a` defined here
25 |     x
   |     ^ function was supposed to return data with lifetime `'a` but it is returning data with lifetime `'b`
   |
   = help: consider adding the following bound: `'b: 'a`
   = note: requirement occurs because of the type `Holder<ImplsAssoc<'_>>`, which makes the generic argument `ImplsAssoc<'_>` invariant
   = note: the struct `Holder<W>` is invariant over the parameter `W`
   = help: see <https://doc.rust-lang.org/nomicon/subtyping.html> for more information about variance

It's not clear to me why Holder and CovariantHolder are any different. It's not possible construct a CovariantHolder<T, S> where S is anything other than <T as WithAssoc>::Assoc. Why does the compiler treat them differently?

[WaffleLapkin]

The answer is that "that's just how associated types work", when you have X::Assoc in a field, you are always invariant over X. t-types folks may have deeper insight here, but I think it would be correct to say Holder<T> <: Holder<U> <=> T <: U, T::Assoc <: U::Assoc, rust just chooses not to do that. The second example doesn't use associated types in fields, so it doesn't run into that problem and gets CovariantHolder<T, TA> <: CovariantHolder<U, UA> <=> T <: U, TA <: TU as normal, note that in this example there are no associated types in the subtyping, the bound is only needed to check validity of the types.

Again, I don't have the best insight here, but that's how I see it.

Another part to this (thanks to @danielhenrymantilla for suggesting), is that if you want Holder<T> <: Holder<U> <=> T <: U, T::Assoc <: U::Assoc and have consistent rules, then for this example:

struct S<I: Iterator>(I::Item);

You'll have to have S potentially be bivariant over I (since you'll have S<A> <: S<B> <=> A::Item <: B::Item which does not necessarily relate A and B). And bivarience seems to have always been a no-no in rust (again, t-types folks might know more about why).

[tamird]

You could imagine a rule that preserves covariance over type parameters if avoiding bivariance is a goal.

Hopefully t-types folks can chime in.

[tamird]

Batted this around with ChatGPT:

Rust's variance computation for structs operates mainly on type parameters. This is an intentional design decision rooted in simplicity and efficiency. Computing variance by deeply inspecting all fields would be a more complex process, both conceptually and computationally.

The situation with CovariantHolder does feel like a loophole. By decoupling the associated type from its parent type using generics (even if they are essentially representing the same type), you're directing the Rust compiler to treat them differently when it comes to variance.

It's worth noting that these kind of "tricks" or workarounds can sometimes have unintended consequences or become "gotchas" for developers reading the code, as they might not immediately understand why such a construct is in place.

Is it a bug? That's a matter of perspective. It's more of a side effect of the current design decisions made for variance computation in Rust. If this behavior causes issues in real-world code, it could be raised to the Rust community for consideration. They have a track record of refining and improving the language based on practical feedback.

real world example: #57440

[vldm]

I struggled with same issue.
And strange part for me is that using CovariantHolder<..> in other structure - makes this structure to be invariant over lifetime.

trait WithAssoc {
    type Assoc;
}

struct ImplsAssoc<'a> {
    phantom: core::marker::PhantomData<&'a ()>,
}

impl WithAssoc for ImplsAssoc<'_> {
    type Assoc = ();
}

struct CovariantHolder<T, A = <T as WithAssoc>::Assoc>
where
    T: WithAssoc<Assoc = A>,
    {
    
    pub t: T,
    pub a: A,
}
// This compiles.
fn covariant<'long: 'short, 'short>(x: CovariantHolder<ImplsAssoc<'long>>) -> CovariantHolder<ImplsAssoc<'short>> {
    x
}

struct Holder<'a>(CovariantHolder<ImplsAssoc<'a>>);

fn invariant<'long: 'short, 'short>(x: Holder<'long>) -> Holder<'short> {
    x
}

https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=cdaa5f63958a06afdeccb7c37c63348d

Or i have missed something and this is considered as expected behavior?

[danielhenrymantilla]

Yeah, the hack needs to be manually propagated to every holder that also wishes to remain covariant, alas:

struct Holder<'a>(CovariantHolder<ImplsAssoc<'a>, ()>);

It's a bit of code repetition, but at least you do get a very clear and direct compiler error if you get the assoc type wrong