Background
I've been taking a deep dive into unsafe recently and specifically designing data structures, which use unsafe internally and offer a safe API. I'm a fan of zero-cost abstractions and Rust's safety guarantees. IMO, the combination of both makes Rust an outstanding programming language. However, there are some problem domains where Rust's feature richness make it hard to prove soundness of a safe API and some API designs become outright impossible without unsafe.
My current enemies when working with unsafe:
- Interior mutability
- Global state
RefCell, Who Doesn't Like Hate It?
Interior mutability causes a huge headache and designing sound data structures, that abstract over UnsafeCell is incredibly easy to mess up. The living proof why it's so hard is RefCell. It is the data structure, that no one really likes, but everyone accepts, because Cell can only take you so far and while Cell<Option<_>> can help, it's trading one overhead with another.
RefCell is the data structure, that becomes 100% useless, if it can be proven whether it can panic at runtime (hint: it can always be proven whether it's panic-free) and is therefore a terrible offender of zero-cost abstractions. Sadly, proving it is a non-trivial task and the overhead at compile-time to construct the proof is too big to justify. That makes RefCell a concession from Rust to its user. It sacrifices runtime performance and memory for significantly faster compile-times (I imagine, proving whether RefCell can panic could easily double the compile-time, heavily depending on its use).
Cell, Our Zero-Cost Abstraction Hero?
While I'm fairly certain, it's impossible to ever get rid of RefCell, maybe there is a way to enhance Cell or design a new type of Cell to reduce the usage of RefCell. To be able to come up with an improvement, one has to understand the design behind Cell and why its API is sound, first.
Cell is great! Everyone likes Cell! It is the embodiment of zero-cost abstractions. It doesn't incur any time or space penalty at runtime. How does it work, though? One of the first things we're taught in Rust is, that mutable references are exclusive, i.e. you cannot have 2 mutable references pointing to the same location in memory. If Cell allows arbitrary mutation of it's interior, doesn't it offend this rule? The obvious answer is, "no, it doesn't".
The reason can be explained as follows: Cell does in fact not allow users to obtain a reference to the interior value. While it does use references internally, that doesn't pose a problem. Cell is not thread-safe (!Sync) and you cannot stop a function execution in the middle and run another one within the same thread. Cell also doesn't call methods of the interior value, that take a reference to self. This ensures, that there is only ever a single reference to the interior value at any time, which is enough to prove correctness. Now, that we've established why Cell is sound, how is it able to offer a useful API without any references?
Swapping and Copy
Cell offers 2 important ways to mutate and work with the interior value. The general method is to swap out the interior value with another one. Swapping works with either owned values via replace/set (set is effectively a replace, that doesn't return the previous value) and take (implicit; T: Default) or a reference to another Cell via swap. Alternatively, if the the interior value is Copy, Cell offers a way to read the interior value without mutation. It simply copies it. There's not much to explain here, except for…
Why Copy Works and Clone Doesn't
Why does Cell not require Clone instead of Copy to read the internal value? Copy is a special compiler-built-in trait, i.e. we cannot recreate this trait's capabilities ourselves with the tools we are given. Copy is special, in that it literally copies a value, i.e. it copies the 1s and 0s without performing any additional operations. That last part is what makes Copy work.
Clone, on the other hand is a trait with a user-defined clone method, that is called to produce another value of the same kind. There is neither a guarantee, the value is copied literally nor that it has no side effects. Losing the guarantee of a literal Copy is sad, but actually not what prevents Cell from requiring Clone, instead. What does block it, however, is the possibility of a side effect, i.e. the interior value might mutate its interior via UnsafeCell during the cloning.
This allows obtaining a mutable reference while having an immutable reference to the same value, which is undefined behavior.
// NOTE: I never worked with `Any`, so this is just a conceptual showcase, not meant to run as-is.
struct Evil(&'static Cell<&'static dyn Any>);
impl Clone for Evil {
fn clone(&self) {
let a = self.0.get();
// Try cast `a` to `Evil` and call `set` on the inner value,
// obtaining the mutable reference while an immutable reference
// to the interior exists.
}
}
let a: &'static Cell<&'static dyn Any> =
Box::leak(Box::new(Cell::new(&())));
let b: &'static dyn Any = &Evil::new(a);
a.set(b); // a is self-referential, now
let b = a.get(); // Imagine this called `clone`, instead
Cell's Limits
Cell's biggest shortcoming are types, that live (partially) on the heap. Heap (de)allocation is expensive and anything living on the heap cannot be copied by copying the pointer. Cloning is necessary, which we established is not sound for Cell's get method, but in this case wouldn't be satisfying, anyway. To be able to read the interior value, we have to swap it out for some other value, but since allocation is expensive and we only want to temporarily borrow it, creating a new value is not what we want. This is where most people reach out RefCell or ditch that approach and directly use UnsafeCell with the danger of UB to avoid the overhead.
Can We Find a Better Approach?
In order to avoid the overhead of cloning from Cell and bookkeeping from RefCell, we need to be able to to get a temporary mutable reference only with the help of the borrow checker and type system and prevent overlapping mutable references.
Problem with a simple get_mut method:
// pub fn get_mut(&self) -> &mut T { … }
let a = Cell::<u8>::new(0);
let b: &mut u8 = a.get_mut();
// Nothing prevents calling the method, again, while the
// previous reference is still active. This is UB!
let c: &mut u8 = a.get_mut();
drop((b, c));
Getting creative with closures:
// pub fn with_mut(&self, f: impl FnOnce(&mut T)) { … }
let a = Cell::<u8>::new(0);
// Not returning a reference is the first key of preventing
// multiple mutable references. The following does not compile:
// let b: &mut u8 = a.with_mut(|value| …);
// let c: &mut u8 = a.with_mut(|value| …);
// drop((b, c));
However, the following does still work:
a.with_mut(|value| {
// The closure captures `a` via shared reference.
// This allows calling `with_mut` inside itself,
// creating multiple overlapping mutable references.
// This is UB!
a.with_mut(|value| { … });
});
The main problem is, that we can capture the same Cell directly or indirectly within with_mut.
Auto-traits and negative impls to the rescue (nightly-only):
pub unsafe auto trait NoCell {}
impl !NoCell for UnsafeCell {}
We can express truly immutable references, now! (&T where T: NoCell)
Trying to apply it for our use-case:
// pub fn with_mut(&self, f: impl FnOnce(&mut T) + NoCell) { … }
let a = Cell::<u8>::new(0);
// This doesn't compile, anymore:
// a.with_mut(|value| {
// a.with_mut(|value| { … });
// });
However, we can still apply the trick I showed earlier to prove why cloning is unsound.
That's a simple problem to solve, though. We just have to apply the trait bound to T, as well, not just the captured state of the closure:
impl<T> Cell<T>
where
T: NoCell {
pub fn with_mut(&self, f: impl FnOnce(&mut T) + NoCell) { … }
}
Have we finally found the solution to get a mutable reference without requiring the use of unsafe from the user? Sadly, not quite. While the auto-trait allows creating a truly immutable reference, the same cannot be said for methods of &T: NoCell.
Just like closures can capture their environment, every function implicitly "captures" the global environment. This global environment is always present and access cannot be restricted by trait bounds. That means, we have no (good¹) way to prevent UB from occuring in with_mut.
¹ Some solution involving const was proposed on the user forum, but it didn't work for anything heap-related, which did not strike me as really solving the actual problem.
Conclusion
If we could somehow restrict access to globals like we can to captured state for closures, I'm optimistic, that we could create a sound abstraction, that increases the number of use-cases of Cell while reducing those of RefCell.
The notion of true immutability introduced here could be of interest to other areas, as well. I haven't explored that feature, yet.
Open Question
What are your thoughts about enhancing Cell with this kind of feature? What do you think about having more control about access to global state? Do you have an idea, how a solution might look like?
Personally, I just reached the conclusion, today and before thinking too hard about it, I thought it'd be nice to share my recently made experience and let others join in on this little adventure of exploring possible solutions for safe zero-cost abstractions.
P.S.: Thanks to all the people in the community who helped me understand what to watch out for when designing safe APIs around unsafe code in Rust.