Covariance: when "lifetimes" can shrink

So, in some of the previous chapters we've seen that sometimes, there is a seemingly silly operation which can be done: that of shrinking or shortening expiry-dates / regions / "lifetimes".

For instance, let's consider the simplest lifetime-infected type: a borrow (to, say, some primitive type):

&'borrow i32
// but also:
&'borrow mut i32

When you got your hands on such a thing with a 'long borrow, if you have to feed it to some API that wants a 'short borrow instead, you can!

use ::core::convert::identity;

fn demo<'short, 'long : 'short>(
    r: &'long mut i32,
) -> &'short mut i32
{
    identity::<&'short mut i32>(r) // ✅ OK!
}

This is called a subtyping relation, and you may observe that it is quite similar to an implicit coercion.

I'll personally be using the following syntax to express this subtyping property:

&'long mut i32 ➘ &'short mut i32

• In the type-theory realm, they instead use <: for this, but I've never been very fond of this sigil, especially given how for lifetimes it's when we have 'big ≥ 'short that we have &'big () <: &'short (), which I find more confusing than saying &'big () ➘ &'short ().

  I like ➘ because:

  • it looks like a -> without being exactly that one (so as to avoid ambiguities with function signatures);
  • we could almost interpret it as a "decay"ing operation, which I personally find to fit quite well the subtyping properties within actual code 🙂 (the amount of type information goes down as we fit into a supertype).

Is shrinking lifetimes really "silly"?

let local = String::from("…");
let names: Vec<&str> = vec![local.as_str(), "static str"];

let storage: PathBuf;
let file_to_read: &Path =
    match ::std::env::args_os().nth(1) {
        | Some(s) => {
            storage = s.into();
            &storage
        },
        // no `.to_owned()` whatsoever needed in this branch 💪
        | None => "default-file.toml".as_ref(),
    }
;

fn pick<'ret>(
    left: &'ret str,
    right: &'ret str,
) -> &'ret str
{
    if … { left } else { right }
}

fn pick<'ret, 'left, 'right>(
    left: &'left str,
    right: &'right str,
) -> &'ret str
where
    'left : 'ret,
    'right : 'ret,
{
    // Here, we have `'left` and `'right` lifetimes in  branch;
    // by covariance they get to shrink-unify down to some `'ret` intersection.
    if … { left } else { right }
}

Covariance, a definition

Covariant lifetime parameter

So, this property of certain generic lifetime parameters being allowed to shrink is called covariance (in that lifetime parameter). While most generic types will happen to be covariant, there is an important exception / counter-example which we need to be aware of:

• mutable…
• …borrows!

When both properties are "ticked"/met, then any lifetime in the borrowee is not (allowed) to be shrunk. We say of such a lifetime that it is non-covariant, or for short¹, invariant.

• ⚠️ notice how we're talking of the lifetimes that may occur within the borrowee: the lifetime of the borrow itself is not part of the invariant stuff.

For instance, let's look at the type of that second argument of {Display,Debug}::fmt function:

&'_ mut Formatter<'_>

Naming the lifetimes, we end up with:

// mutable borrow of
//  vvvvvvvvvvvv
    &'borrow mut Formatter<'fmt>
//               ^^^^^^^^^^^^^^^
//              invariant borrowee



//  can shrink
//      =
//  covariant
//   vvvvvvv
    &'borrow mut Formatter<'fmt>
//                         ^^^^
//                     cannot shrink (nor grow)
//                           =
//                       invariant

A more typical albeit potentially visually confusing example is when the borrowee is itself a borrow:

&'borrow mut (&'fmt str)

In both cases, we have a &mut-able 'borrow, with thus a covariant/shrinkable lifetime, and behind such borrow, a thus invariant borrowee, resulting in 'fmt not being allowed to shrink (nor grow).

• Reminder that shared mutability exists

  Note that the unique borrow, &mut, is not the only form of mutable borrow. Consider, for instance:

  // Covariant in `'borrow`, invariant in `'fmt`.
  &'borrow Cell<&'fmt str>
  

  • To gain a better intuition of this, I highly recommend that you open your mind to the following "statement":

    use ::core::cell::Cell as Mut;
    

    • (this is a legitimate thing to do since Cell does indeed let you mutate "its interior")

    Thay way we end up with:

    &'borrow Mut<&'fmt str>
    

  Finally, for technical reasons², it turns out that the harmless owned shared mutability wrappers have to be declared invariant as well, despite the lack of borrows:

  // Invariant too!
  Cell<&'_ str>
  

  In practice, you're more likely to run into this when dealing with things like a Mut ex, a RwLock<_>, or any form of channel (at least the Sender<_> end):

  //! Invariant
  Mut ex<&'_ str>
  RwLock<&'_ str>
  RefCell<&'_ str>
  channel::Sender<&'_ str>
  

Covariant type parameter and composition rules

It turns out that saying:

• given &'borrow /* Borrowee */,
• then, each lifetime occurring in Borrowee (if any),
• is covariant;

is kind of a mouthful to say/write/express. We thus define this conventional term, when this occurs: we'll talk of &'borrow T being covariant in the T type parameter.

So a not-so-formal definition of type-parameter-covariance would be:

• Determining whether a <T>-generic type is covariant

  A practical rule (of thumb) for determining whether a <T>-generic type is covariant (in T) is to replace T by, say. &'s str, and seeing the covariance (in 's) of the resulting type, since that will then be the covariance of the <T>-generic type.

  Examples:

  • What is the covariance of type Example<T> = (T, i32);?

    1. We replace T with &'s str: what is the covariance of (&'s str, i32)?

    2. We somehow know that type ExampleT<'s> = (&'s str, i32) is covariant (in 's).

    3. "Thus", Example<T> is covariant (in T).

  • What is the covariance of type Example<T> = Arc<Cell<T>>;?

    1. We replace T with &'s str: what is the covariance of Arc<Cell<&'s str>>?

    2. We know that "lifetimes behind a Cell are invariant", so we know that:

       type ExampleT<'s> = Arc<Cell<&'s str>> is invariant (in 's).

    3. "Thus", Example<T> is invariant (in T).

• Composition rules: when you know that a <T>-generic type is covariant:

  For instance, consider type Vec<T> (or, more generally, any type F<T>).

  Now define some type depending on a lifetime parameter:

  type T<'lt> = (i32, &'lt str, bool); // FYI, this is covariant.
  

  Then the resulting type, F<T<'lt>>, i.e., Vec<(i32, &'lt str, bool)>, will have the same variance as T<'lt> alone: <T>-covariant types let the <'lt>-variance inside T pass through.