Newbie question: why doesn't Rust have 3 kinds of references?

Note: I am just learning Rust now, so I don't have much experience with it.

TL;DR: with my little understanding, I think a more relaxed, non-exclusive, reference type could be added to Rust, in a mostly-backwards compatible way, so that more safe use-cases are accepted by the borrow checker. In this long post I try to explain how I came up with this idea. I would like to know whether I am missing something and this idea is actually stupid, which I guess is most likely the case.

Motivation

My understanding is that we need to mutually exclude & foo and &mut foo because foo may contain heap-allocated data and therefore & foo may be used to obtain a reference to heap-allocated data, which could then be rendered invalid by a change to foo through a &mut foo.

However, I stumbled across some limitations of this coarse-grained approach and read that they are well-known limitations. For example, replacing an element in a Vec does not reallocate the heap buffer, so it could be performed while another shared reference to the vector exists. Also, a shared reference to a vector could be safely used (in a single-threaded setting) to check the length of the vector while a mutable reference is used to push new elements to it, as checking the length does not require accessing the heap allocation. As the last example, in my understanding, a Box never frees its heap allocation until the destructor is called, so while the contents of the box can be modified by mutable references, this can never invalidate shared references, as those heap locations are never freed and reassigned to unrelated objects. They will always contain a (hopefully valid) instance of the correct type.

So it appears to me that the strict limitations of shared and mutable references are designed for swappable heap allocations, while a more relaxed model could be used when no heap allocations are involved, or when the involved allocations are never swapped with different ones. So I wonder, why not add this relaxed model to the language and allow some more pieces of code to compile, such as the ones I mentioned above?

Idea

Two types of memory regions

We start by realizing that our objects can store their contents in two types of memory regions:

  • stable regions are allocated in (or even before) the constructor of the object itself, and are not deallocated until the object is destroyed. These include the memory area where the object itself is stored (think the storage of the Vec struct itself, which is just a pointer and two integers), but also memory regions that are heap-allocated in the constructor, assigned to a pointer, and never deallocated until the destructor is called (think the heap allocation of Box). References to data in these stable regions can never be invalid. The data in these regions can change, but the regions will keep containing data of the correct type for the entire lifetime of the object.

  • unstable regions are memory regions that an object allocates and deallocates during its lifetime, through its mutating methods, such that references to these regions may become invalid when certain mutating methods of the object are called (think about the raw buffer used by Vec, which is replaced and deallocated when a capacity change is necessary, or a Box field within another object, which can be reassigned to another Box object by a mutating method).

Three types of references

Based on this, we can come up with three kinds of references:

  • unstable unique references can be used to perform mutating and non-mutating operations on any part of an object. Because these references may point to an unstable region, which may disappear with any mutating method call, only a single unstable unique reference can exist at any point in time, and it is consumed whenever it is passed to a function. This is exactly the behaviour of current mutating references.

  • unstable shared references can be used to perform non-mutating operations on any part of an object. Because these references may point to an unstable region, which may disappear with any mutating method call, unstable shared references cannot coexist with an unstable unique reference. However, they can coexist with other unstable shared references, as they cannot invalidate each other. This is exactly the behaviour of current shared references.

  • stable references can be used to perform mutating and non-mutating operations, but only on stable regions of an object. Because they can only mutate stable regions, they cannot invalidate any reference. And because they can only point to stable regions, they cannot be invalidated by any other reference. Therefore, these references can coexist with themselves and with any other kind of reference and can always last for the entire lifetime of the referenced object.

Basically, we can add a third type of reference that is not mutually exclusive with the existing two types, and that can be used to safely perform operations on a subset of the data that can change value but not memory address.

Creation rules

As it is now, unstable references can be created for any object. The only restriction is that unstable shared references cannot be held at the same time as unstable unique references, and only one of the latter can be held at any time.

On the other hand, it is not possible to hold stable references to all objects, but only to those that reside in stable regions. The stack-allocated and statically-allocated objects are stable. Heap-allocated objects are stable if and only if they can be reached from a stable object by following a stable pointer, that is, a pointer that is guarantee to be initialized in the object constructor, never reassigned and only freed in the object destructor.

To achieve this, it is necessary to annotate pointers as stable. If a pointer is annotated as stable, the compiler enforces its initialization and prevents its reassignment, effectively treating it as an immutable field. The compiler also prevents any attempt to obtain a stable reference to a field that is accessed via a pointer that is not annotated as stable.

Conversion rules

As it is now, unstable unique references can be safely converted to unstable shared references of the same or shorter lifetime. Or, in other words, if you have exclusive mutating access to any part of an object for a certain period of time, then you can have non-mutating access to any part of that object for up to that same period of time.

In addition, unstable references can be converted to stable references of the same or shorter lifetime. This may lead to a stable reference to an unstable memory region. However, as already happens now, the borrow checker will ensure that the lifetime of each unstable reference ends as soon as the unstable region of the object may be invalidated. So while stable references created directly from an object have the same lifetime as the object itself, stable references created through an unstable reference will only last as long as that unstable reference, which means until another unstable reference may cause an invalidation. Thus memory safety is guaranteed.

On the other hand, stable references cannot be converted to unstable references, or used to extract references to unstable parts of an object. If that was to be allowed, one could convert a stable reference to an unstable shared reference while an unstable unique reference to the same object was active in another code fragment, which would break the memory safety.

Backwards-compatible change

Because we are just adding one more type of reference, we can do it in a quite backwards-compatible way.

  1. First, the concepts of stable regions and stable references can be added to the language and compiler. Because existing references are still valid and have the strictest behaviour (unstable), and because all pointers and heap regions are treated as unstable by default, all code keeps working as before.
  2. Then, API developers can start using the new features at their own pace, relaxing the constraints from unstable references to stable references. This is trivial when no heap pointers are involved. When heap pointers are involved, the developers first need to mark them as stable, and then they can relax the references that interact with these stable pointers. All of this does not affect users of the API, because the original unstable references can be cast to stable references of the same lifetime.
  3. Finally, users of the upgraded APIs can upgrade their code and start ripping the benefits, being able to write more straightforward code and have more fine-grained control over reference invalidation.

Examples

In these examples we keep using & for unstable shared references and &mut for unstable unique references, and we introduce &stable for stable references. Furthermore, we just prepend stable to a pointer type to annotate it as a stable pointer, telling the compiler it will not be reassigned to a different memory region.

We can start with a sketch of the structure of Vec (greatly oversimplified), to show that while some methods still need the unstable references, others can switch to stable references.

pub struct Vec<T> {
    ptr: *mut T,
    cap: usize,
    len: usize,
}

impl Vec<T> {
    // we can call this even when someone else holds
    // a &mut to this vector, because whatever they do
    // they cannot render the access to field cap invalid
    pub fn capacity(&stable self) -> usize {
        self.cap
    }

    // same as above
    pub fn len(&stable self) -> usize {
        self.len
    }

    // by using &mut, we invalidate all unstable references
    // to this vector, which is necessary because we are
    // about to invalidate at least some of them by
    // reallocating ptr
    pub fn reserve(&mut self, additional: usize) {
        unsafe {
            let ptr = somehow_allocate(self.len + additional);
            somehow_copy(ptr, self.ptr, self.len);
            swap(ptr, self.ptr);
            somehow_free(ptr);
        }
    }

    // we are mutating the vector, but we are not invalidating
    // any references, because we are not changing the capacity
    // of the vector (vectors never shrink).
    pub fn swap_remove(&stable self, index: usize) -> T {
        unsafe {
            let last_ptr = somehow_advance(self.ptr, self.len - 1);
            let rem_ptr = somehow_advance(self.ptr, index);
            somehow_swap_contents(last_ptr, rem_ptr);
            self.len = self.len - 1;
            *last_ptr
        }
    }
}

impl<T> ops::Deref for Vec<T> {
    type Target = [T];
    // here we need an unstable reference, because the slice
    // may be invalidated as soon as more elements are added
    // to the vector
    fn deref(&self) -> &[T] {
        unsafe {
            slice::from_raw_parts(self.as_ptr(), self.len)
        }
    }
}

Let's now see some allowed/disallowed patterns:

let mut vec = vec![1, 2, 3];
let unstable_shared = &vec;
let stable_vec = &stable vec;
let stable_elem = &stable vec[0]; // compile error! not stable at all!
let unstable_unique = &mut vec;

unstable_unique.push(4);    // this may reallocate the heap buffer
unstable_shared[0];         // compile error! mutable borrow invalidated this!
stable_vec[0];              // compile error! elements are not stable!
stable_vec.len();           // ok; not accessing the heap at all
stable_vec.swap_replace(1); // ok; no heap reallocation happens,
                            // no risk of invalidating other pointers

Finally, this is how the Box struct would look like (again, super oversimplified):

pub struct Box<T> {
    // pointer marked as stable: will never be
    // reallocated, will always point to the same
    // memory area, from the end of the constructor
    // to the invocation of the destructor of the box
    ptr: stable *const T
}

impl<T> Deref for Box<T> {
    type Target = T;
    // self.ptr is stable, that is, it won't
    // be freed for the entire lifetime of self.
    // therefore, we can return a stable reference
    // to the boxed value which will allow mutations
    // from multiple references without ever risking
    // invalid accesses
    fn deref(&stable self) -> &stable T {
        unsafe { &stable *self.ptr }
    }
}
1 Like

This is not just because of heap allocations. For example, changing an enum from one variant to another could break references to fields of the enum.

Yes, and this can be done safely with split_at_mut or using Cell as described here.

A RefCell can do this. It can also be done without runtime checks in a manner similar to this.

The Box could contain an enum, or the Box could be mem::swaped with another box and then destroyed.

This sounds very similar to what &Cell<T> does today.

13 Likes

There are many other reasons, like avoiding data races. And as it turns out, ensuring exclusive access is semantically useful to, for things like Mutex guards, or just maintaining some logical invariants -- you can temporarily break the invariants of your data structure while holding a &mut without worrying about them being observed (modulo something like a panic). (&mut would have been better named &uniq.)

Other reasons aside, you can clobber memory on the stack too.

Say I have a Vec<String>. Thread A says let s: &str = v[0].as_ref();. Thread B says v[0] = String::new();. The String in slot 0 is freed and s dangles.

That would be a data race, which is considered UB in Rust.

This is both a data race, and suffers from the same "my allocation still being around doesn't mean everything transitively in my allocation sticks around" problem as replacing Vec elements.


Some of the applications you mention are possible to some extent by turning a &mut Thing into a &Cell<Thing> and utilizing interior (shared) mutability. In the case of a slice (e.g. created from a &mut Vec), you can then replace elements without worrying about dangling references, as there can be no references that penetrate the Cells. (You can only deal with elements as a whole.)

5 Likes

Obligatory mention of The Problem With Single-threaded Shared Mutability - In Pursuit of Laziness

Which quotes this comment I've always liked:

My intuition is that code far away from my code might as well be in another thread , for all I can reason about what it will do to shared mutable state.

Many people consider it an advantage that it needs the "lock" of &mut to swap_remove in a vector.

Generally, opting-in to extra concerns -- like alice mentions with &Cell<T> -- covers those situations that need it.

And as a meta-point, the bar for a new reference type is incredibly high. Even &pin didn't happen, for example. There are a ton of different things that would need to be reevaluated for a &stable -- like you have Deref taking &stable, but that's not what the trait says. So would there be a new DerefStable? Where does that fit into the hierarchy? Would we need an IndexStable too? Etc.

8 Likes

split_at_mut and Cell::from_mut require me to pass an &mut, which would prevent me from holding any other reference to the vector. Or am I missing something? My point was that it is perfectly safe to have multiple mutating references to the vector (and even to the same portion of the vector), as long as the operation does not reallocate the heap.

When you are using the Cell::from_mut utility, then all of your references to the vector would be a &Cell<...> reference.

You are right about this, I did not think about enums. The hypothetical &stable would need to be disallowed when the same bits can be reinterpreted in multiple ways, and that would greatly reduce the number of potential applications.

Fair.

I suspect that you will find that the rules I described for &Cell<T> under the projection heading in this article match rather closely the rules you are suggesting for your new reference type.

4 Likes

I'm going through the article now and that is indeed true. Thanks for the link!

2 Likes

@quinedot You are right that this would create a lot of issues in multi-threaded scenarios. I was purely reasoning within a single thread, where multiple structures/closures/whatever may be holding references to the same object and modifying it, but not in parallel, so data races should not happen.

I didn't even start thinking how this would work with multithreading, but I guess you would want to stick to mutexes to ensure that you can re-establish all invariants before anyone can see your changes, no matter if they are in stable memory or not.

That's why I was thinking that this hypothetical &stable reference would not propagate transitively through pointers, unless those pointers are explicitly marked as stable, in which case the compiler would not allow them to be deallocated or swapped out before the destructor of the containing object.

1 Like

Gotcha. I second Scott's recommendation of the article linked above (and Niko's post that it links to as well).

@scottmcm thanks for the link!

Yes, I am aware that adding a new reference type would basically amount to designing an entirely new language. This was written mostly as an exercise in understanding Rust.

One answer is that if you ignore the distinction between a reference and pointers (I am never entirely clear what the distinction really is), Rust DOES have more than 2 kinds of references, it has "smart pointers" such as Box, Rc, Ref and RefMut, Arc and also different kinds of cells : Cell, RefCell, Mutex, for a start. It all fits together and makes sense (eventually).

2 Likes

The so-called "raw" pointers have somewhat looser validity requirements: they do not have an associated lifetime, you are allowed to perform pointer arithmetic on them, and two *mut T raw pointers are allowed to alias.

In contrast, so-called "references" are pointers with extra compile-time information (such as lifetime annotations) and requirements (e.g., they must always point to a valid, initialized object, and two &muts must never alias) associated with them. As a consequence, references are always safe to dereference, while "raw" pointers require unsafe.

If you ignore these differences arising out of memory safety requirements, then both pointer-like types provide the essential feature of pointers: they allow indirection.

1 Like

why doesn’t Rust have 3 kinds of references?

Well, how confusing do you want a programming language to be?

The two kinds of reference and the rules around them are enough for my feeble mind already.

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.