Expressing the covariance of GATs

Hi all,

I'm the author of the cc-traits crate defining common traits for collection data structures, using GATs. One of the basic trait it provides defines what type is used to reference the items of the collection. Here is its definition:

/// Abstract collection that can be immutably referenced.
pub trait CollectionRef: Collection {
	/// Type of references to items of the collection.
	type ItemRef<'a>: Clone + Deref<Target = Self::Item>
	where
		Self: 'a;
}

Overall, this crate has been very useful to me to define various abstractions of data structures. However there has been one shortcoming that keeps coming back biting me once in a while: the associated type ItemRef<'a> is not covariant w.r.t 'a as we would expect from a reference, at least according to the compiler. So I tried to find a way to express that, yes, ItemRef<'a> is covariant. Here is what I came up with:

/// Covariant associated type.
/// 
/// A type implementing this trait is [covariant](https://doc.rust-lang.org/nomicon/subtyping.html#variance)
/// with regards to the lifetime `'a`.
/// This means that if this type is used as a generic associated type
/// parameterized by the lifetime `'a` (e.g. `type T<'a> = ThisType<..., 'a, ...>`)
/// then any `T<'long>` can be changed into any `T<'short>` as long as `'long: 'short`.
/// 
/// ## Safety
/// 
/// To implement this trait, you **must** ensure that:
/// 
/// - The size of the type does not change with `'a`.
/// - Every type parameter is covariant with regards to `'a`.
/// - Every composing type (field type) is covariant with regards to `'a`.
pub unsafe trait Covariant<'a> {}

unsafe impl<'a, T> Covariant<'a> for &'a T {}
unsafe impl<'a, T> Covariant<'a> for &'a mut T {}
unsafe impl<'a, T: Covariant<'a>> Covariant<'a> for Box<T> {}
unsafe impl<'a, T: Covariant<'a>> Covariant<'a> for std::rc::Rc<T> {}
unsafe impl<'a, T: Covariant<'a>> Covariant<'a> for std::rc::Weak<T> {}
unsafe impl<'a, T: Covariant<'a>> Covariant<'a> for std::sync::Arc<T> {}
unsafe impl<'a, T: Covariant<'a>> Covariant<'a> for std::sync::Weak<T> {}

pub trait CollectionRef: Collection {
	type ItemRef<'a>: Clone + Deref<Target = Self::Item> + Covariant<'a> // <- note the `Covariant<'a>` bound
	where
		Self: 'a;

	/// Changes an item reference into a shorter lived reference.
	/// 
	/// Item references are [covariant](https://doc.rust-lang.org/nomicon/subtyping.html#variance) with
	/// regard to the defined lifetime parameter `'a`, which is ensured by the [`Covariant`] trait.
	/// This means that any `ItemRef<'long>` can be changed into any `ItemRef<'short>` as long as `'long: 'short`,
	/// safely and without cost.
	fn reborrow<'short, 'long: 'short>(r: Self::ItemRef<'long>) -> Self::ItemRef<'short> {
		// This is safe because the `Self::ItemRef<'long'>` type implements `Covariant<'long>`.
		unsafe {
			let shorter = std::mem::transmute_copy(&r);
			std::mem::forget(r);
			shorter
		}
	}
}

Obviously, this is a very unsafe procedure, and I want to be extra sure that I didn't miss anything. This is why I would like some reviewing of this piece of code.

I have several questions:

  • Is it possible to define a GAT whose size changes w.r.t its lifetime parameter? I couldn't find any example. To be sure I added the "The size of the type does not change with 'a." constraint in the definition of Covariant, but I don't know if that is necessary.
  • In fact, are all the constraints defined in the ## Safety block necessary/sufficient to know that the transmute_copy in reborrow will not cause UB? Should I add more constraints?

Instead of an unsafe trait Covariant and transmuting fn reborrow, why not just make reborrow a required method associated function of CollectionRef? For genuinely covariant GATs the implementation is as simple as

    type ItemRef<'a> = &'a Foo; // or whatever
    fn reborrow<'short, 'long: 'short>(x: Self::ItemRef<'long>) -> Self::ItemRef<'short> {
        x
    }

And for contravariant or invariant GATs there's no reasonable implementation at all. No unsafe in sight!

(By the way, I think "reborrowing" usually refers to doing &*x or &mut *x where x is some raw pointer or reference—the mechanism that makes your reborrow function work is subtyping.)

P.S. I got this trick from dtolnay in this IRLO thread about GAT variance.

2 Likes

why not just make reborrow a required method associated function of CollectionRef

Ah yes, this would be a safe way to do it I admit, but I should have mentioned that I want to avoid this solution because it forces the CollectionRef implementor to explicitly define the reborrow function. CollectionRef is not the only trait defined in my crate that have a reference-like associated type, and I expect implementors to just use an actual reference for all of them most of the time. So that would mean re-implementing the same function over and over with a trivial definition (the one you gave). I tried it, it's very annoying. Using my Covariant trait allows me to discharge this burden from the implementor, since I can provide ready-to-use implementations for common reference types &'a T, &'a mut T, Rc<T> and so on, as shown in the post.

I think "reborrowing" usually refers to doing &*x or &mut *x where x is some raw pointer or reference

Yes you are probably right, I should find another name. At first I was using the name shorter but I wasn't feeling it. I'm open for other ideas :grinning:

This should be easy to DRY up with a simple macro_rules!.

As for naming, how about upcast_item_ref? "Upcast" because the function lets you pass from a "smaller" type ItemRef<'long> to a "bigger" type ItemRef<'short>, upward in the subtyping chain.

This should be easy to DRY up with a simple macro_rules!.

I think you are convincing me. The more I think about it and the more I think I'll go back to doing that. It may be a bit annoying for implementors but at least it's safe and saves us a copy (although the compiler is probably smart enough to avoid it).

1 Like

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.