Exploring Interior Mutability, Auto Traits and Side Effects

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.

3 Likes

This is one of many possible situations where Rust would benefit from an effect system, allowing functions that are statically known to not have certain side effects (such as "accessing cell interiors"). Then you could have something along the lines of

impl<T> Cell<T> {
    pub fn with_mut(&self, f: impl FnOnce(&mut T) + NeverAccessesCellInteriors) { … }
}

even without preventing the type T from containing other Cells.

But it's hard to graft an effect system onto Rust when it wasn't designed for that from the ground up. (In particular, note that you wouldn't be able to call any other functions from inside the closure, unless those functions had also been explicitly annotated with NeverAccessesCellInteriors...) There have been a bunch of prior discussions on the topic, but I don't recall any satisfying conclusions.

6 Likes

This already exists in the compiler:

But is probably not going to be the path forward here, as this RFC is in FCP-close.


As another potential direction, here's something I threw together a while back as an experiment to makes it easier to get a &mut using the swap/take approach:

https://lib.rs/crates/pawn

I haven't used that in anger to see whether it works well, though.

4 Likes

You may be interested in the qcell crate, that provides alternative cell designs.

LCell is especially interesting, with lifetime-based compile-time borrow checking.

2 Likes

An effect system sounds interesting and would certainly offer more flexibility around interior mutation. The type system approach got me far, but ultimately wasn't enough to solve my problem. A system to detect side effects might also be interesting for other applications, such as transactions.

Preventing interior mutation and any form of IO-like file and network access could enforce requirements, that require manual review, today, the former aiding safe wrappers around unsafe and the latter being a big help for preventing other kind of logic bugs. panic/exit-free code would allow some optimizations where MaybeUninit could be used instead of Option.

Anyway, I also arrive at the same solution as you. One way to describe side effects are as "traits for functions". Rust could offer some built-in fn traits, that could be used like this:

// In core/std:
pub fn trait NoInteriorMutation;

// In user code:
pub fn with_mut(&self, f: F)
where
    F: FnOnce(&mut T) + NoInteriorMutation { … }

It's important to differentiate between what the trait acts on, because for closures, traits could either target the fn or the auto-generated struct while for simple function pointers, it's unambiguous.

I think the question of how to use them would already be solved by this. The more difficult question is, how does one implement them? This brings me to what scottmcm wrote.


@scottmcm I totally agree with you on the auto trait misery. Having taken some time to think about them in addition to how side effects would be used, I came to the conclusion, that auto traits, how they currently work, need to die. What I thought of would have to be accompanied with an edition change.

Auto Traits V2 would work as follows: Instead of auto traits being implicitly implemented, they have to be explicitly implemented. Safe auto traits will cease to exist (I still don't know why they exist, in the first place). Existing safe auto traits will become regular safe traits. Negative auto trait impls will cease to exist. Implementing an auto trait can be done in 2 ways: safe and unsafe. Let's take Send and Sync in combination with usize and AtomicUsize as an example. I think it's generally easier to understand examples than me trying to explain the behavior with only text.

pub auto trait Send {} // unsafe implied
pub auto trait Sync {}

unsafe impl Send for usize {} // No longer implicitly implemented

pub struct UnsafeCell<T>(T); // If T implements <auto trait>, <auto trait> can be implemented safely, otherwise it can be implemented unsafely

impl<T> Send for UnsafeCell<T>
where
    T: ?Sized + Send {} // No unsafe needed here, but explicit impl required

// No longer needed (forgetting this with old auto traits could end up in a disaster):
// impl<T> !Sync for UnsafeCell<T>
// where
//     T: ?Sized

pub struct AtomicUsize(UnsafeCell<usize>);

impl Send for AtomicUsize {}
unsafe impl Sync for AtomicUsize {}

NoDrop will become an auto trait. NoDrop will be added as a super trait to Copy (this was already implied). Drop and NoDrop will be mutually exlusive. I think this covers the basics.

Such a huge change will require tooling for edition migration, otherwise the process would become very error prone. The tool would add explicit auto trait impls where there were implicit auto trait impls before. Negative impls won't need to be removed, since they'll throw a compile error and are easily found.


Back to side effects. fn traits would be similar to auto traits as described above. The way they differ from regular ones is how they are applied, since functions don't impl anything. Closures will automatically impl fn traits, that are applicable, just like Fn* traits are implemented according to what criteria the closure fullfills.

As for what the guarantee might look like, this could be one way of doing it (didn't put too much thought into this):

fn my_fn() -> usize
impl NoInteriorMutation { … }

There would be no unsafe impl for fn traits, since they're all built-in and AFAIK, there is no sensible reason for allowing that.

1 Like

So, for what it's worth, it would be very difficult for Rust to add function traits like this. They'd need a rollout similar to const fn, where every library author is encouraged to add as many "does not do X" traits to their functions as possible, which would often only be possible after their dependencies do it first (since you can't make foo be NoInteriorMutation if it calls other_library::bar and bar hasn't been tagged NoInteriorMutation yet). I figure the best case would be if we design a full, robust effect system so there'd only be one rollout instead of a whole bunch of partial rollouts in sequence.

That said, if we did do it, let's go over some details. Perhaps the most interesting case is functions with callbacks:

fn my_fn<F: FnOnce()>(callback: F) {
  callback()
}

What my_fn does depends on what callback does, so we would need conditional impls, like so:

impl<F: FnOnce + NoInteriorMutation> NoInteriorMutation for my_fn {}
impl<F: FnOnce + NoPanic> NoPanic for my_fn {}
impl<F: FnOnce + NoWackyHijinks> NoWackyHijinks for my_fn {}
...

But of course, users should be able to create additional effects, so we need an unbounded collection of impls here. To properly have an effect system, we would have to generalize over effects, i.e. something like this:

impl<effect trait E, F: FnOnce + E> E for my_fn {}

which is a type of higher kinded polymorphism that Rust has not attempted yet.

3 Likes

In order to ease adding such traits, one could create a tool, that automatically adds traits to all fns, that have none or in the case of new fn traits being introduced, one could provide the name of the trait as an argument which will be added to all possible fns regardless of already existing trait impls. Reviewing these changes will be a matter of looking at the version control diff and is certainly easier to handle than manually adding the traits for each fn.

Sadly, I think it might be necessary to use shorter names, as I suspect there will be quite a few fn traits and there is a point where expressive names actually hurt readability, especially since they're built-in and appear very frequently (which is why I think fn is a great keyword as opposed to function). Perhaps, trait aliases could be a good compromise?

Proposed fn traits are in fact effects, and these lack of expressiveness: one can force only having certain effects.

I'm thinking of effect subtyping: we can allow an effect variable have both subtype and supertype - this way we could declare an effect that is forced to be at least this and at most that. For example if we have filesystem effect and file_open effect we can specify what our fopen function does: at least opens file and at most performs arbitrary actions with filesystem, so we have something like fn<effect E: file_open..filesystem> fopen(...) -> ....

In this effects subtyping relation we have one minimum: pure - and one maximum: impure. These two effects are implied in declaration like effect N: ..network and effect F: ffi.. where we are saying that fn with effect F does at least ffi.

1 Like

While inheritance makes sense for us to reason about something, the problem is stability. Once pure has been defined, there can be no effect added later to that definition. It'd have to be called pure2 which is pure + not-the-new-effect, otherwise it'd have the same issues as auto traits. However, what could be done is for users to define aliases, i.e. they can define their own form of pureness and that is going to stay the same, even if another effect is added. It's less convenient, but the only way to not mess up the effect system.

As for FFI, thanks for reminding me about it. That is actually the valid reason I didn't think about, as to why one should be able to unsafely annotate fns with what kind of side effects it doesn't have. It'd be impossible to use FFI for anything, that has some restriction about what a function is allowed to do.

EDIT: It's an interesting question whether FFI should be considered a side effect by itself.

1 Like

unsafe, failable aka try, async and proposed gen (it's done via transform and coeffect of runtime (context?)), const, plain functions are just special cases of either effects or coeffects.

This is the point - pure shouldn't be redefined later. I've heard about effect algebra, where effects can be combined together to create another effects: such that effect A: B + C means that effect A includes both B and C.

FFI is actually about user guarantees, since C (and almost another languages) doesn't offer any effect system. This way, foreign functions can do anything. I guess this effect might be in a completely separate branch of impure - pure subtyping path.

P.S Was inheritance just more than subtyping?

Would declaring "at least" be actually useful for anything? File::open for example may well return NotFound inside its Result

This is closely related to the following question:

Given function f such as:

fn f(...) ... {
    ...
    if false { fopen("*some non existent file*") }
    ...
}

Do this function have side effect(s)? Why?

But it will try to open it, it's an effect. Will an action succeed? - well, we don't know. How to properly type such effect is an open question, but I bet that we should consider trying to perform an action as performs this action.

EDIT: another example:

There function opener should have have at least fopen effect:

/// this is kinda BAD, but it is example...
fn<effect FS, effect Console> print_from_file_or_create_file(
    file: &'_ str, opener: fn<FS>(&str)->...
)   where FS: fopen..filesystem
{
    if (file_exist) {
        let file_h = opener(file); 
        print!(file_h.contents());}
    else {
        create_file(file)
    };
}

Guess I just don't see any benefit in declaring "function will definitely try to open a file". How would that be useful? This function may write to memory outside its stack, this function may perform IO, this function may panic, etc are useful to know. But modelling in type system that the function will definitely try to open a file.. What for?.. I don't think actually existing research programming languages with effects are trying to model this either.

At least in rust, where function types typically must be written out, the question seems underspecified. But in some version of the type system and language we could have:

fn f<B: Bool, IF<B, IOEffect>>(...) ... {
    ...
    if B { fopen("file.txt") }
    ...
}

This is branching into the wildly hypothetical though.