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 ofCovariant
, 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 thetransmute_copy
inreborrow
will not cause UB? Should I add more constraints?