Learn Rust With Entirely Too Many Linked Lists
← Ch V
Chapter VI A Production Unsafe Deque
Ch VII →
  1. 37 — Layout
  2. 38 — Variance and Subtyping
  3. 39 — Basics
  4. 40 — Panic Safety
  5. 41 — Boring Combinatorics
  6. 42 — Filling In Random Bits
  7. 43 — Testing
  8. 44 — Send, Sync, and Compile Tests
  9. 45 — An Introduction To Cursors
  10. 46 — Implementing Cursors
  11. 47 — Testing Cursors
  12. 48 — Final Code
38

Variance and Subtyping

Rust has subtyping, but only over lifetimes. &'long T is a subtype of &'short T because anywhere the shorter borrow is required, a longer one will do. Variance says how a generic type lifts that relationship. We need to pick: covariant, contravariant, or invariant in T. Wrong choice = soundness hole.

  1. Covariance: Foo<&'long T> is a subtype of Foo<&'short T>. This is what you want for owning containers — a Vec<&'static str> should pass for a Vec<&'a str>. Contravariance is the opposite, mostly seen in function arguments. Invariance is no relationship — required wherever interior mutability touches T.
    // covariant in T (what we want):
//   LinkedList<&'static str>  →  LinkedList<&'a str>     OK
//
// invariant in T (what *mut T would force):
//   LinkedList<&'static str>  →  LinkedList<&'a str>     reject
//
// contravariant in T (rare, function args):
//   fn(&'a str)               →  fn(&'static str)        OK
  2. PhantomData<X> makes the enclosing struct inherit the variance of X. The standard cookbook: PhantomData<T> for "contains a T" (covariant, dropck-aware), PhantomData<&'a T> for "borrows a T" (covariant, no drop), PhantomData<&'a mut T> for "borrows mutably" (invariant), PhantomData<fn(T)> for "contravariant in T". PhantomData<Box<T>> is covariant and signals owning-and-dropping for dropck.
    // our pick:
struct LinkedList<T> {
    front: Option<NonNull<Node<T>>>,
    back: Option<NonNull<Node<T>>>,
    len: usize,
    _marker: PhantomData<Box<Node<T>>>,
    //                  ^^^^^^^^^^^^^^^
    //   covariant in T, claims to own and drop Node<T>
}
  3. Drop check ("dropck") is the second job of the marker. When the list is dropped, the compiler needs to know whether dropping Node<T> could touch borrowed data of lifetime 'a. Without a PhantomData<Box<...>>, the compiler sees raw pointers and doesn't realize we own and drop Node<T>. With it, dropck handles cyclic-lifetime cases like LinkedList<&'a Cell<...>> correctly.
    // without the marker, this could compile and be unsound:
// {
//     let mut list: LinkedList<&Cell<...>> = LinkedList::new();
//     let cell = Cell::new(...);
//     list.push_back(&cell);
//     // cell dropped first, then list dropped, dropck doesn't see
//     // that list's drop touches T via Box<Node<T>> -- BAD.
// }
//
// PhantomData<Box<Node<T>>> tells dropck the truth.