Is Vec invariant?


#1
pub struct Node<'a> {
    children: Vec<Rc<RefCell<Box<Child + 'a>>>>,
}

impl<'a> Node<'a> {
    pub fn add_child<T>(&mut self, child: Rc<RefCell<Box<T>>>)
        where T: Child + 'a
    {
        self.children.push(child);
    }
}

It outputs

error: mismatched types:
 expected
  `alloc::rc::Rc<core::cell::RefCell<Box<child::Child + 'a>>>`,
 found
  `alloc::rc::Rc<core::cell::RefCell<Box<T>>>`
(expected trait child::Child, found type parameter) [E0308]

#2

See https://doc.rust-lang.org/nightly/nomicon/subtyping.html … in particular, RefCell<T> is invariant over T.


#3

Vec is variant, and RefCell is invariant, as demonstrated by this code:

#![allow(unused)]

use std::cell::RefCell;

fn vec_short<'a>(_: &'a i32, _: Vec<&'a i32>) {}

fn vec_long(x: Vec<&'static i32>) {
    let local = 0;
    vec_short(&local, x) // shortens 'static to 'a
}


fn refcell_short<'a>(_: &'a i32, _: RefCell<&'a i32>) {}

fn refcell_long(x: RefCell<&'static i32>) {
    let local = 0;
    refcell_short(&local, x) // error: shortening would be illegal
}


fn main() {}

Compiling that gives the following error:

<anon>:16:20: 16:25 error: `local` does not live long enough
<anon>:16     refcell_short(&local, x)
                             ^~~~~
note: reference must be valid for the static lifetime...
<anon>:15:19: 17:2 note: ...but borrowed value is only valid for the block suffix following statement 0 at 15:18
<anon>:15     let local = 0;
<anon>:16     refcell_short(&local, x)
<anon>:17 }
error: aborting due to previous error

Commenting out the refcell_short call (but not the vec_short one) allows it to compile fine.

However, that’s a red herring: the problem isn’t subtyping. In fact, Box<T> (when T: Trait) and Box<Trait> have no subtyping relationship, subtyping only comes up in Rust via lifetimes. The fundamental problem stopping this working with trait objects is that Box<Trait> has a different representation in memory to Box<T>, and so converting a Vec<Box<T>> into a Vec<Box<Trait>> requires changing things in memory, which can’t be done implicitly.