Associated type variance bounds

[Jules-Bertholet]

The problem

Given a trait:

trait Trait {
    type Assoc<'a, T, U>;
}

In the above, <Self as Trait>::Assoc<'a, T, U> is invariant with respect to Self, 'a, T, and U.

Frustratingly, today's Rust provides no way to specify a different variance. This limits the language's expressiveness. For example, it makes it certain GAT abstractions much less ergonomic:

Variance of lifetime arguments in GATs

I've been searching and couldn't find any previous discussion of this specific issue. GATs are great! I've been using them in one of my projects and they've been making huge improvements on some of my type-system woes. But I've ran into an annoying gotcha in the form of variance. I've made a GAT that generalizes over &'a T and std::cell::Ref<'a, T>. Both of those are covariant in their lifetime argument. But it seems like GATs are always invariant in their lifetime arguments. (Of course, if th…

It also makes it effectively impossible to implement generic data structures that store enum discriminants or pointer metadata, while properly encapsulating that implementation detail:

Can we implement bivariance for 'static associated types?

Recently Discriminant<T> was changed to be invariant over T due to the use of the new DiscriminantKind trait. This change had to be made because associated types for T are always invariant with respect to T. The previous implementation was covariant: struct Discriminant<T>(u64, PhantomData<fn() -> T); In this case we really want bivariance: there's no reason for the type of discriminant to change regardless of lifetimes. While AFAIK this is impossible now, it seems that this should be possible…

An explicit syntax for requiring associated types to have a particular variance would alleviate all of these issues.

---

Propsed solution

There is lost of bikeshedding in the first thread regarding syntax for this feature, but I'd like to propose another option: a new type of where-clause bound. For example:

trait Trait {
    type Assoc<'a, T, U>: covariant(Self) + contravariant(T) + covariant(U) + contravariant(U);
}

In the above, <Self as Trait>::Assoc<'a, T, U> is covariant with respect to Self, invariant with respect to 'a, contravariant with respect to T, and bivariant with respect to U. Any implementation of Trait must uphold these guarantees:

impl<'s> Trait for &'s () {
    // Following is a valid implementation, meets all the variance bounds.
    type Assoc<'a, T, U> = (Self, &'a mut u32, fn(T));
}

impl Trait for i32 {
    // Following is also a valid implementation, meets all the variance bounds.
    type Assoc<'a, T, U> = ();
}

/*
impl<'s> Trait for &'s u32 {
    // ERROR: the bound `covariant(Self)` is not satisfied
    type Assoc<'a, T, U> = (&'s mut Self, &'a mut u32, fn(T));
}
*/

Variance bounds outside the trait definition

An advantage of type bounds is that they are usable in where clauses outside the trait definition. For example, one can write:

trait Foo {
    type Assoc;
}

fn bar<T: Foo>(&T) -> <T as Foo>::Assoc where T::Assoc: covariant(T) {
   // ...
}

// This struct is covariant with respect to `T`
struct Baz<T>
where
    T: Foo,
    <T as Foo>::Assoc: covariant(T),
{
    inner: <T as Foo>::Assoc
}

In addition to being more flexible than attributes on the type parameters, trait bounds can be relegated to the where clause, alongside all the other complicated type bounds. This helps keep code and documentation approachable.

Restrictions on variance bounds

For simplicity, I would suggest that variance bounds be restricted in the following ways, at least initially:

• They can restrict only the associated types of traits
• No matter where a variance bound appears, its type parameter (the T in covariant(T)) must be one of:
  • The Self type of the trait
  • A GAT type parameter of the associated type

---

Conclusion

Variance is infamously hard to grasp. In part because of this, the Rust language tries hard to make it implicit and hide it from the programmer. Most of the time, this makes sense. But when you do need explicit control, Rust doesn't provide it. Things that should work become impossible, and give error messages that only confuse you more. Explicit variance annotations for the few cases where they are necessary would make the language more ergonomic and easier to use.

[elidupree]

As the OP from the first thread, I find this proposal appealing!

A big thing we have to worry about is discoverability:

• I like the choice of including the full names ("covariant" etc.) in the syntax, so that if someone sees existing code using this feature, they can look it up. This might not be the right choice for a commonly used feature, but since this is intended to be a rarely used feature, the priorities are different
• The big challenge is discoverability for someone who needs this feature, but hasn't seen any existing code that uses it. My first thought is that it could use a lot of attention to making good error messages for lifetime-related errors involving GATs; I'm not familiar with the internals of how error messages are generated, but maybe it would be good to workshop some examples. The first scenario that comes to mind is when you make a GAT that is implicitly invariant and then use it in a way that assumes covariance.

[Jules-Bertholet]

An interesting wrinkle: with view types, Rust might get more than one kind of variance.

struct Example {
   foo: usize,
   bar: usize,
}

If the view type Example { foo } is a supertype of Example, then &mut (Example { foo }) should be a supertype of &mut Example. The latter is strictly more powerful than the former. And one of the major motivations behind view types is to allow replacing fn(&mut Example) with fn(&mut (Example { foo })), which requires &mut to be covariant with respect to view types.