Could we allow references inside a Cell if we assume any two Cells alias?

language design
1

So I have this single threaded async code that uses Cell in two ways:

struct Processor {
    resume: Cell<Option<oneshot::Sender<()>>>,
}

impl Processor {
    pub async fn run(&self) {
        loop {
            let (resume, pause) = oneshot::channel();
            self.resume.set(Some(resume));
            pause.await.unwrap()
            // do stuff
        }
    }

    pub fn paused(&self) -> bool {
        let resume = self.resume.take();
        let out = match resume {
            Some(_) => true,
            None => false,
        };
        self.resume.set(resume);
        out
    }

    pub fn resume(&self) {
        if let Some(resume) = self.resume.take() {
            resume.send(()).unwrap();
        }
    }
}

In resume, Cell feels very useful, like it's forcing me to write better code. In another language I would just write self.resume.send(());, leaving it ambiguous what's left in self.resume. Cell forces me to explicitly move the sender before using it. In paused on the other hand, Cell just adds a bunch of noise to the program that feels avoidable. The point of moving out of the Cell before reading is so that we don't accidentally alias it, since two &Cells are allowed to alias. However, in this function we can see statically that no other Cell<Option<oneshot::Sender<()>>>s are accessed between when the value is taken and when it is returned, so in theory it could be possible to reference the interior. Imagine if Cell could have methods

impl Cell<T> {
    lifetime 'shared;
    fn ref(&self) -> &'shared T { ... }
    fn ref_mut(&self) -> &'shared mut T { ... }
}

so that references from any two Cell<T>s would be assumed to alias since they share the same lifetime.

2

This exact design doesn't work because it doesn't prevent calling ref_mut while a shared borrow of the inside of the same cell already exists. Rust doesn't have a "two things with the same lifetime are assumed to alias", and in fact an &'a T and &'a mut T are assumed to not alias (because mutable references are assumed to not alias anything, including other references with the same lifetime). As a simple example, in

fn example(a: &mut (u32, u32), f: impl for<'a> FnOnce(&'a u32, &'a u32)) {
    let a0 = &mut a.0;
    let a1 = &mut a.1;
    (f)(a0, a1);
}

a0 and a1 have the same lifetime as each other, but are assumed to not alias (and in fact the implementation of f is allowed to optimise based on the lack of aliasing).

Although this specific design doesn't work, the general principle of "allow references to be accessed directly inside a Cell variant on the assumption that they all alias" does work. The usual technique involves passing around references to some sort of uniqueness-proof singleton in order to prove that you aren't making two conflicting references to the same type of cell, and is implemented in crates like ghost-cell and qcell.

It's a pity that this technique is confined to a few fairly obscure crates, because I consider it to be fairly fundamental to why Rust works. My current model of "how Rust references work" is as follows:

  1. When you create an object, it is unique and thus you get a unique reference to it;
  2. Unique references allow "cell transmutes" in which you can soundly transmute the type of an object by changing what sort of cells exist inside it (e.g. it would be sound to transmute &mut T to and from &mut Cell<T>, &mut GhostCell<'brand, T> for any 'brand, or any other type of cell that has no metadata, and you can do this on fields in addition to doing it on the whole object). (A note of caution: this is safe from the lifetime point of view, but not necessarily from the layout point of view, so you might need extra #[repr(transparent)] to make it work.)
  3. A unique reference can be reborrowed as a shared reference. At this point, it is no longer safe to do a cell transmute until the reborrow ends – the type of cells you use have to be consistent to avoid the creation of aliasing references.
  4. Shared references are Copy, so you can copy them to create aliasing references (and if they point to something interior-mutable, mutate through them).

Steps 2 and 3 are effectively a case of "delegating the permission to access the object" to a singleton (i.e. you can form a mutable reference to the inside of the cell if you have a mutable reference to the singleton, and can form a shared reference to the inside of the cell if you have a shared reference to the singleton), and different types of cell vary based on what the singleton is. (For &T, the singleton is conceptually an arbitrary read-only global variable – anyone can shared-reference it but nobody can mutable-reference it. For &Cell<T>, the singleton is conceptually a thread-local singleton, which is why Cell isn't thread-safe – Sending a reference would change which singleton it was tied to, violating memory safety (and forming a persistent reference to the inside of the Cell is disallowed because there's no way to prove that it doesn't overborrow the singleton).ghost-cell has its own singleton type, and qcell gives you the choice of four different singleton types.)

I call this the "cell permission model", and don't think I've ever written it down in full before like this, but it's very helpful for understanding what you can and can't soundly do with cells. (Note that it doesn't fit runtime-fallible cells like RefCell and Mutex, which work entirely differently and are more related to AtomicPtr than to Cell. Both could be written entirely in safe Rust if it had an AtomicEnum type, assuming Mutex had access to a safe interface to an appropriate blocking system call.) Actually formalising it is a little awkward due to interactions with unsafe code and due to Rust's memory not being typed, but I think it should be possible to formalise.

1 Like
3

I believe you're underestimating the amount of operations that would have to be disallowed to support this safely.

For example I suspect you'd like to write the body of paused as self.resume.ref().is_some(), but there's nothing guaranteeing that is_some doesn't somehow end up accessing self.resume through e.g. a thread-local variable. Of course it doesn't, but is there any guarantee that this is and will be the case? You end up needing additional language features and annotations to express this, and this can get out of hand really quickly.

I believe your problem is much better solved by an utility method on Cell that that performs the same dance you do in paused.