Ante: New Way to Blend Borrow Checking and Reference Counting
62 points by veqq
62 points by veqq
We used to think that it was impossible to have "shared mutable borrowing", where we could have a borrowed reference to something, even though others can mutate it through their own references. Heck, Rust is basically built on that belief.
Eliminating shared mutable state is not some unfortunate sacrifice Rust had to make to achieve its goals – its a goal of Rust in its own right, as having shared mutable state inhibits local reasoning about code.
"References are like jumps" by withoutboats covers this very well.
If you have in a language the ability to alias two variables so that they refer to the same location in memory, and also the ability to assign values to variables as execution progresses, your ability to locally reason about the behavior of a component of your system becomes badly inhibited. Depriving the user of the ability to mutate aliased state by accident is critical to enabling the user to easily create correctly functioning systems.
Though Rust’s rules around lifetimes are usually framed in the public consciousness as “a way to avoid garbage collection,” the reality is that they are a much deeper and more significant construct than that. They are a way to make tractable programming in a language which allows both mutable state and aliased state, by guaranteeing that state is not aliased while it is being mutated. This is an incredibly powerful tool for understanding the behavior of the system because you can analyze the behavior of your system locally: you never need to worry about “spooky action at a distance.”
Unfortunately, most people seem to have taken the wrong lesson from Rust. They see all of this business with lifetimes and ownership as a dirty mess that Rust has had to adopt because it wanted to avoid garbage collection. But this is completely backwards! Rust adopted rules around shared mutable state and this enabled it to avoid garbage collection. These rules are a good idea regardless.
Yes, I had the same thought when the author discussed the Mojo borrow checker in an earlier post. Rust's borrow checkers maintains value semantics, even in single-threaded programs.
This is quite nice!
If I understand correctly, the shared-to-mutable magic comes from it being for types that aren't shared across threads, and uniqueness of Rc is done by acting as if all objects of the same type were borrowed for the same lifetime?
Even if explicit vs seamless syntax is a matter of taste, it shows that the compiler knowing more about a Cell can be more flexible about taking mutable references to it.
And it avoids Rust's misleading terminology of using mut to mean exclusive/unique.
Hm...ok, I was wondering what the cross-thread story was like. "Does uniq promotion inply acquiring a lock?"
But I see, the comparison is to Rc not Arc.
And it avoids Rust's misleading terminology of using mut to mean exclusive/unique.
Mind expanding on this thought?
I can't speak for kornel, but from my perspective the misleading part is that &mut does not actually tell you that the type behind the reference is mutable—or rather, its absence doesn't tell you that it isn't. This is because of "shared mutability" affordances like Cell/RefCell/Mutex/RwLock which give you mutability through a shared reference. What &mut actually guarantees is that no one else has a reference to the value at this moment (unless someone did bad things with unsafe code), which implies that you are allowed to mutate it.
I’m not sure what you mean here? If you have a reference you know the value is immutable. Can you provide a concrete example of the lack of mut not being immutable, just so I can understand what you’re referring to?
I suspect the confusion here is just a disagreement in terminology, but let me take an example from the article I linked in a sibling comment: given a shared or "immutable" reference &AtomicU32 to an atomic u32, it's possible to change the value by invoking store(). Thus the value is mutable despite being accessed via a (non-mut) reference.
I'm not sure I understand? Lets say I have
let my_ref_to_x : &AtomicU32 = x; // syntax likely borked, I haven't written rust in a while
....
your reference is still valid, it still refers to the same atomic storage, etc. store, load, and get_mut all work. It feels like you are conflating the value of the object you are referencing with the value that it is referencing.
If that is the case, you may be applying implementation knowledge that is not relevant. It may help to think of Atomic<u32> as a handle
struct Atomic<T> {
value: Box<T>
}
Not because it reflects the implementation, but because it makes it more clear that the value of the Atomic<T> is not the stored value.
If I'm wrong and there are cases where AtomicU32 can change despite holding an immutable value I'd be genuinely curious.
Mutability and uniqueness are two sides of the same coin. Neither is inherently right or wrong, it just depends on which framing you find most interesting.
Rust went with the mutability framing because there is already a ton of stuff that's weird about Rust, and so it's less offputting at first. But then sometimes people learn about "interior mutability" and then decree that uniqueness is the One True Framing. (Though not everyone that prefers it does for that reason, of course, I just find it's a common stage people go through, and some go back to preferring mutability, others stay there for more serious reasons.)
My hope is that Rust has paved enough of a way that future languages with similar systems can choose to go the uniqueness route if they prefer.
You can have mutable stuff that starts from something that is not mut, like atomics or mutexes.
&T means "I have a reference to a T, and other (objects/threads/etc) may also have a reference to that same T."
&mut T means "I have a reference to that T, and no other thread has a reference to that same T."
This gets confused with mutability because id you have a &mut T, there is not a memory-safety issue with mutating it: you cannot race another thread.*
The fact that it actually means "exclusive" means you can use it for tricks:
impl GenerationalGC {
/// Store an object in the GC arena, returning a pointer to the object.
fn store<'a, T>(&'a self, item: T) -> Ptr<'a, T> { ...};
/// Mark this object as a GC root.
/// Get a root ID that is stable across GC.
fn add_root<'a, T>(&'a self, ptr: Ptr<'a, T>) -> usize { ... }
/// Garbage collect.
///
/// Because this takes &mut self,
/// and Ptr contains a reference to this GC ('a),
/// the compiler will prove that there are no Ptrs outstanding when collect is called,
/// or fail to compile.
/// That is, it ensures you're registered everything you want to keep over the GC as a root, and discarded all the other Ptrs.
fn collect(&mut self) { ... }
All those methods "mutate" the underlying structure; the difference is whether there can be more than one reference to the structure when they are invoked.
* ...well, memory barriers and other very low things aside :-)
The blog post "Accurate mental model for Rust's reference types" by David Tolnay explains this point well, imo.
I’m unsure how this works? It seems to be saying “if I have a mutable pointer to an object I can take a mutating reference to a slice of that object”
But in that case it seems that I can do (arbitrary syntax)
mutref someobjext = … mutref subfield = someobjext.a.b someobjext.a = somethingelse
Which would seem to cause a break (subfield becomes invalid, or the value of subfield changes) and I couldn’t work out how the semantics work (there was so much prose, comparisons to other languages, and code examples in this post but not just a basic “here are the step by step semantics of this behaviour”)