Are there two kinds of covariance?

help
#1

The test code of some standard library containers asserts the (co)variance of some iterators. For BTreeMap (and BTreeSet), it also test the container itself. For instance, it checks that something like this compiles:

fn test_variance<'new>(v: BTreeSet<&'static str>) -> BTreeSet<&'new str> {
    v
}

I read this as "if you carry long lived references, you can pretend to be carrying short lived references", and I gather that this is what covariance boils down to in Rust.

I'm trying to understand in what code this comes into play. I thought this would be a good example:

fn pick_from<'a>(set1: BTreeSet<&'a i32>, _set2: BTreeSet<&'a i32>) -> &'a i32 {
   set1.iter().next().unwrap()
}

This function requires that both sets can pretend to have the same type and the same lifetime for their contents, right? So pass in two sets with references of different lifetimes, and we see covariance in action, right?

let one = 1;
let set1 = once(&one).collect::<BTreeSet<_>>();
{
    let two = 2;
    let set2 = once(&two).collect::<BTreeSet<_>>();
    let _x = pick_from(set1, set2);
}

playground

Well, no. if I go break the implementation of BTreeSet such that it is invariant (as far as I know) and fails test_variance but succeeds all the rest, the pick_from example also still happily compiles.

I wish I could find a simpler way to show that, but I couldn't figure out how to make a simple invariant container (variations of struct VecRef<'a, T>(Vec<&'a mut T>)). Or at least something failing the test_variance tests.

#2

I'm gonna guess that you tried something along these lines:

use ::core::iter::once;

type BTreeSet<T> = ::std::collections::BTreeSet<::core::cell::Cell<T>>;

fn pick_from<'a> (set1: &BTreeSet<&'a i32>, _set2: &BTreeSet<&'a i32>)
  -> &'a i32
{
   set1.iter().next().unwrap().get()
}

fn main ()
{
    let one = 1;
    let set1 = once(&one).map(Into::into).collect::<BTreeSet<_>>();
    {
        let two = 2;
        let set2 = once(&two).map(Into::into).collect::<BTreeSet<_>>();
        let _x = pick_from(&set1, &set2);
    }
}

This one passes thanks to NLL, we could say: that borrow over one does not necessarily have to be held longer than that over two, independently of the BTreeSets.

  • the #[may_dangle] on their impl Drop is what makes this possible, otherwise a container with Drop impl would not let NLL kick in.

    • (The fact there is a unsafe impl <#[may_dangle] T> Drop is also what makes it mandatory to thus have, at least, a PhantomData<T> to express that elements of type T may be transitively dropped, otherwise with only pointer types that would be unsound).

One way to avoid it is to simply "use" such borrow after the maximal scope of two, so as to make sure that doesn't apply here:

    let set1 = once(&one).map(Into::into).collect::<BTreeSet<_>>();
    {
        let two = 2;
        let set2 = once(&two).map(Into::into).collect::<BTreeSet<_>>();
        let _x = pick_from(&set1, &set2);
    }
+   drop(set1); // Seen as a use.
}

That will successfully fail #Oxymoron :upside_down_face::

error[E0597]: `two` does not live long enough
  --> src/main.rs:19:25
   |
19 |         let set2 = once(&two).map(Into::into).collect::<BTreeSet<_>>();
   |                         ^^^^ borrowed value does not live long enough
20 |         let _x = pick_from(&set1, &set2);
21 |     }
   |     - `two` dropped here while still borrowed
22 |     drop(set1);
   |          ---- borrow later used here
1 Like
#3

Actually, I changed LeafNode's *const to *mut to see what happens, and made acquaintance with the variance tests.

I contrasted the 3 versions to better understand it:

use ::core::cell::Cell;

struct Hull<T>(T);

impl<T> Hull<T> {
    fn new(t: T) -> Self {
        Self(t)
    }
}

struct Covariant<'a, T>(Option<Hull<&'a T>>);
struct Invariant<'a, T>(Option<Cell<&'a T>>);
/*
impl<'a, T> Drop for Invariant<'a, T> {
    fn drop(&mut self) {
    }
}
*/
        
#[allow(dead_code)]
fn test_covariance<'new>(v: Covariant<'static, i32>) -> Covariant<'new, i32> {
    v
}

fn choose_co<'a>(v1: &Covariant<'a, i32>, _v2: &Covariant<'a, i32>) -> &'a i32 {
    v1.0.as_ref().unwrap().0
}

fn choose_in<'a>(v1: &Invariant<'a, i32>, _v2: &Invariant<'a, i32>) -> &'a i32 {
    v1.0.as_ref().unwrap().get()
}

fn main() {
    let one = 1;
    let co1 = Covariant(Some(Hull::new(&one)));
    let in1 = Invariant(Some(Cell::new(&one)));
    {
        let two = 2;
        let co2 = Covariant(Some(Hull::new(&two)));
        let in2 = Invariant(Some(Cell::new(&two)));
        choose_co(&co1, &co2);
        choose_in(&in1, &in2);
    }
    drop(co1);
}

playground

If you uncomment the drop handler, indeed the invariant container doesn't like any of it. Unless you also involve may_dangle

What really confused me is that I expected some error around the invocation of pick_from, but I gather now that it merely imposes a constraint on the lifetimes, and when the compiler can't sort out the lifetimes, it blames the things at the border of its search space, and not all the contraints.

#4

That works too, and is even a cleaner approach. I had used a type alias with a wrapping Cell simply as a quick & dirty way to achieve invariance / opt out of covariance in the Playground :+1: