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 ofBox
). 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 aBox
field within another object, which can be reassigned to anotherBox
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.
- 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.
- 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.
- 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 }
}
}