Why is a Cell used to create unmovable objects?

Question

So I ran into this code snippet showing how to create "unmoveable" types in Rust - moves are prevented because the compiler treats the object as borrowed for its whole lifetime.

use std::cell::Cell;
use std::marker;

struct Unmovable<'a> {
    lock: Cell<marker::ContravariantLifetime<'a>>,
    marker: marker::NoCopy
}

impl<'a> Unmovable<'a> {
    fn new() -> Unmovable<'a> {
        Unmovable { 
            lock: Cell::new(marker::ContravariantLifetime),
            marker: marker::NoCopy
        }
    }
    fn lock(&'a self) {
        self.lock.set(marker::ContravariantLifetime);
    }
    fn new_in(self_: &'a mut Option<Unmovable<'a>>) {
        *self_ = Some(Unmovable::new());
        self_.as_ref().unwrap().lock();
    }
}

fn main(){
    let x = Unmovable::new();
    x.lock();

    // error: cannot move out of `x` because it is borrowed
    // let z = x; 

    let mut y = None;
    Unmovable::new_in(&mut y);

    // error: cannot move out of `y` because it is borrowed
    // let z = y; 

    assert_eq!(std::mem::size_of::<Unmovable>(), 0)
}

I don't yet understand how this works. My guess is that the lifetime of the borrow-pointer argument is forced to match the lifetime of the lock field. The weird thing is, this code continues working in the same way if:

• I change ContravariantLifetime<'a> to CovariantLifetime<'a>, or to InvariantLifetime<'a>.
• I remove the body of the lock method.

But, if I remove the Cell, and just use lock: marker::ContravariantLifetime<'a> directly, as so:

use std::marker;

struct Unmovable<'a> {
    lock: marker::ContravariantLifetime<'a>,
    marker: marker::NoCopy
}

impl<'a> Unmovable<'a> {
    fn new() -> Unmovable<'a> {
        Unmovable { 
            lock: marker::ContravariantLifetime,
            marker: marker::NoCopy
        }
    }
    fn lock(&'a self) {
    }
    fn new_in(self_: &'a mut Option<Unmovable<'a>>) {
        *self_ = Some(Unmovable::new());
        self_.as_ref().unwrap().lock();
    }
}

fn main(){
    let x = Unmovable::new();
    x.lock();

    // does not error?
    let z = x;

    let mut y = None;
    Unmovable::new_in(&mut y);

    // does not error?
    let z = y;

    assert_eq!(std::mem::size_of::<Unmovable>(), 0)
}

Then the "Unmoveable" object is allowed to move. Why would that be?

Answer 1

The true answer is comprised of a moderately complex consideration of lifetime variancy, with a couple of misleading aspects of the code that need to be sorted out.

For the code below, 'a is an arbitrary lifetime, 'small is an arbitrary lifetime that is smaller than 'a (this can be expressed by the constraint 'a: 'small), and 'static is used as the most common example of a lifetime that is larger than 'a.

Here are the facts and steps to follow in the consideration:

• Normally, lifetimes are contravariant; &'a T is contravariant with regards to 'a (as is T<'a> in the absence of any variancy markers), meaning that if you have a &'a T, it’s OK to substitute a longer lifetime than 'a, e.g. you can store in such a place a &'static T and treat it as though it were a &'a T (you’re allowed to shorten the lifetime).

• In a few places, lifetimes can be invariant; the most common example is &'a mut T which is invariant with regards to 'a, meaning that if you have a &'a mut T, you cannot store a &'small mut T in it (the borrow doesn’t live long enough), but you also cannot store a &'static mut T in it, because that would cause trouble for the reference being stored as it would be forgotten that it actually lived for longer, and so you could end up with multiple simultaneous mutable references being created.

• A Cell contains an UnsafeCell; what isn’t so obvious is that UnsafeCell is magic, being wired to the compiler for special treatment as the language item named “unsafe”. Importantly, UnsafeCell<T> is invariant with regards to T, for similar sorts of reasons to the invariance of &'a mut T with regards to 'a.

• Thus, Cell<any lifetime variancy marker> will actually behave the same as Cell<InvariantLifetime<'a>>.

• Furthermore, you don’t actually need to use Cell any more; you can just use InvariantLifetime<'a>.

• Returning to the example with the Cell wrapping removed and a ContravariantLifetime (actually equivalent to just defining struct Unmovable<'a>;, for contravariance is the default as is no Copy implementation): why does it allow moving the value? … I must confess, I don’t grok this particular case yet and would appreciate some help myself in understanding why it’s allowed. It seems back to front, that covariance would allow the lock to be shortlived but that contravariance and invariance wouldn’t, but in practice it seems that only invariance is performing the desired function.

Anyway, here’s the final result. Cell<ContravariantLifetime<'a>> is changed to InvariantLifetime<'a> and that’s the only functional change, making the lock method function as desired, taking a borrow with an invariant lifetime. (Another solution would be to have lock take &'a mut self, for a mutable reference is, as already discussed, invariant; this is inferior, however, as it requires needless mutability.)

One other thing that needs mentioning: the contents of the lock and new_in methods are completely superfluous. The body of a function will never change the static behaviour of the compiler; only the signature matters. The fact that the lifetime parameter 'a is marked invariant is the key point. So the whole “construct an Unmovable object and call lock on it” part of new_in is completely superfluous. Similarly setting the contents of the cell in lock was a waste of time. (Note that it is again the invariance of 'a in Unmovable<'a> that makes new_in work, not the fact that it is a mutable reference.)

use std::marker;

struct Unmovable<'a> {
    lock: marker::InvariantLifetime<'a>,
}

impl<'a> Unmovable<'a> {
    fn new() -> Unmovable<'a> {
        Unmovable { 
            lock: marker::InvariantLifetime,
        }
    }

    fn lock(&'a self) { }

    fn new_in(_: &'a mut Option<Unmovable<'a>>) { }
}

fn main() {
    let x = Unmovable::new();
    x.lock();

    // This is an error, as desired:
    let z = x;

    let mut y = None;
    Unmovable::new_in(&mut y);

    // Yay, this is an error too!
    let z = y;
}

Answer 2

An interesting problem! Here's my understanding of it...

Here's another example that doesn't use Cell:

#![feature(core)]

use std::marker::InvariantLifetime;

struct Unmovable<'a> { //'
    lock: Option<InvariantLifetime<'a>>, //'
}

impl<'a> Unmovable<'a> {
    fn lock_it(&'a mut self) { //'
        self.lock = Some(InvariantLifetime)
    }
}

fn main() {
    let mut u = Unmovable { lock: None };
    u.lock_it();
    let v = u;
}

(Playpen)

The important trick here is that the structure needs to borrow itself. Once we have done that, it can no longer be moved because any move would invalidate the borrow. This isn't conceptually different from any other kind of borrow:

struct A(u32);

fn main() {
    let a = A(42);
    let b = &a;
    let c = a;
}

The only thing is that you need some way of letting the struct contain its own reference, which isn't possible to do at construction time. My example uses Option, which requires &mut self and the linked example uses Cell, which allows for interior mutability and just &self.

Both examples use a lifetime marker because it allows the typesystem to track the lifetime without needing to worry about a particular instance.

Let's look at your constructor:

fn new() -> Unmovable<'a> { //'
    Unmovable { 
        lock: marker::ContravariantLifetime,
        marker: marker::NoCopy
    }
}

Here, the lifetime put into lock is chosen by the caller, and it ends up being the normal lifetime of the Unmovable struct. There's no borrow of self.

Let's next look at your lock method:

fn lock(&'a self) {
}

Here, the compiler knows that the lifetime won't change. However, if we make it mutable:

fn lock(&'a mut self) {
}

Bam! It's locked again. This is because the compiler knows that the internal fields could change. We can actually apply this to our Option variant and remove the body of lock_it!