Based on The Rules of References:
At any given time, you can have either one mutable reference or any number of immutable references.
What problems does it solve? Why this rule exists at all?!
1 Like
It's there to prevent race conditions that will certainly occur if 2 or more places in your code have mutable access to the same chunk of memory at the same time.
Consider this simple function:
fn my_function() {
let mut a = 12;
let b = &a;
let c = &mut a;
println!("{a}, {b}, {c}");
}
This code violates Rust’s references rule, as it creates both an immutable reference (b) and a mutable reference (c) to a. However, a is just a local variable in this function, and there’s only the main thread, so no other threads could be accessing it simultaneously. Since only one part of the code accesses a at any given time, it seems unlikely for any race condition to occur here. So why is this rule enforced in such a simple, single-threaded context?
1 Like
This blog post from 2015 spells out some motivations behind the aliasing XOR mutability design. I think it's mostly about correctness, but a lot of optimizations are based around (the lack of) aliasing as well.
The correctness and optimization considerations apply to single-threaded programs too.
5 Likes
Have you heard about the “iterator invalidation” problem? This is where you have a collection, and an iterator over the collection, and you modify the collection while the iterator is running (e.g. removing an item). If nothing is done, this will often result in some kind of invalid state, such as an out-of-bounds access. Languages which have iterators in the standard library have taken various approaches to this problem:
- Don't do that; it's undefined behavior (C++).
- The iterator and the collection coordinate to signal an error if this is done (Java).
- Collections are always immutable, so this can't happen (pure-functional programming).
- Something arbitrary but well-defined happens; but it might not be what you wanted your algorithm to do.
Rust’s answer to this problem is that[1] the borrow checker prevents such a program from even compiling. The reference rules prevent bugs, and collections don’t have to worry about giving a meaning to simultaneous mutation and iteration, which is something that can come up in a single-threaded program, with a function working on only local data.
In general, sufficiently complex programs can have bugs that aren’t race conditions but look very much like them, which are about ordering of side effects. Rust’s reference rules prevent many of this class of bugs by constraining which side effects can occur when.
under typical conditions, with no interior mutability ↩︎
22 Likes
It's to ensure memory safety, in other words to ensure that references are always valid.
The following blog post gives a bunch of examples where this matters:
You can easily have race conditions in rust, maybe you meant data races? But even then the borrow checker is not just for that (see the blogpost linked above).
5 Likes
fn my_function() {
let mut a = vec![1, 2, 3];
let b = &a;
let c = &mut a;
// extra stuff not in your example
let val = &b[0];
c.clear();
// also the print has one more thing
println!("{a}, {b}, {c}, {val}");
}
This code (Playground) is the same as your example here with just a couple extra operations. My code shouldn’t compile, because it gets a reference to the first element of the vector and then clears the vector, dropping all that memory, which leads to val pointing to freed and invalid memory. Both examples are equivalent to the borrow checker, so neither can compile.
Also see kpreid’s post above about iterator invalidation.
8 Likes
I read the blog post and found out a situation where this rule ensures memory safety even in single-threaded program!
fn push_all(from: &Vec<i32>, to: &mut Vec<i32>) {
for i in from.iter() {
to.push(*i);
}
}
fn my_function() {
let mut vec = vec![1,2,3];
push_all(&vec, &mut vec);
}
This would spell disaster! As we're pushing elements onto the vector, it will occasionally need to resize, allocating a new hunk of memory and copying its elements over to it. The iterator would be left with a dangling pointer into the old memory, leading to memory unsafety (with attendant segfaults or worse).
Fortunately, Rust ensures that whenever a mutable borrow is active, no other borrows of the object are active, producing the message:
error: cannot borrow `vec` as mutable because it is also borrowed as immutable
push_all(&vec, &mut vec);
^~~
1 Like
This is a sample code for "iterator invalidation" problem:
fn remove_items(a: &Vec<i32>, b: &mut Vec<i32>) {
for i in a.iter() {
if i % 2 == 0 { // a dummy condition
b.remove(*i as usize);
}
}
}
Which Rust's references rule prevent that.
A mutable reference is exclusive; a shared reference to the same data cannot exist at the same time. Therefore, you cannot call remove_items() in a way which causes iterator invalidation; if remove_items() is called then it can rely on a and b pointing to different vectors. So, remove_items() does not contain an iterator invalidation bug, because Rust makes that guarantee about the references that are its arguments.
2 Likes
Putting aside compiler optimizations and potential logic bugs, there is a big reason for the rule in the single threaded case that helped me understand it: it is necessary to avoid "use after free". A language with tracing GC doesn't have this problem to solve.
let mut v = vec![0, 1, 2];
let r1 = &mut v;
let r2 = &v[2];
// This drops the original vec and frees its memory.
*r1 = vec![];
// This would access the freed memory, if Rust allowed it.
assert_eq!(*r2, 2);
error[E0502]: cannot borrow `v` as immutable because it is also borrowed as mutable
--> src/lib.rs:12:19
|
11 | let r1 = &mut v;
| ------ mutable borrow occurs here
12 | let r2 = &v[2];
| ^ immutable borrow occurs here
...
15 | *r1 = vec![];
| --- mutable borrow later used here
1 Like
Thanks to @quinedot, @SkiFire13, @jumpnbrownweasel, @cod10129, @firebits.io and @kpreid for the examples and blog posts! I’m now convinced why this rule is necessary even in single-threaded programs. I’ve learned that it’s not just about preventing data races—it also helps avoid issues like accessing freed memory, using deallocated memory, iterator invalidation, and more.
I’ve also updated the topic title to Why Does Rust Enforce the "One Mutable or Many Immutable References" Rule in Single-Threaded Programs?, which I think is more relevant.
However, I’m still curious about the optimization benefits of this rule. How does it work?
4 Likes
Consider this function:
fn fill<T: Copy>(input: &T, output: &mut [T]) {
for elem in output {
*elem = *input;
}
}
Knowing that input can't point to a part of output, the compiler can generate machine code that copies *input into a register (if it's small enough) once, and then copies that register to *elem in the loop.
If it didn’t know that, it would have to read input on every iteration of the loop, because one of the previous iterations might have overwritten the value.
13 Likes
For example, consider a loop like this:
pub fn rev_swap<T>(a: &mut [T], b: &mut [T], n: usize) {
let (a, b) = (&mut a[..n], &mut b[..n]);
for i in 0..n {
std::mem::swap(&mut a[i], &mut b[n-1-i]);
}
}
(This is essentially the internals of [T]::reverse.)
Can the compiler vectorize that loop? In Rust yes, but only because of the "one mutable reference" rule -- the two slices cannot overlap thanks to that rule.
Without the rule, it's possible that they'd overlap, and thus the compiler would need to preserve the exact behaviour we wrote by doing the reads and writes in exactly the order in the source code, because the behaviour of one loop iteration might affect the next.
But thanks to not overlapping, the compiler knows it's an "embarrassingly parallel" loop at the SIMD level, and thus it knows how to optimize it.
10 Likes
The benefits are similar to the use of the restrict keyword in C. Except that Rust automatically enables this for all &mut references and, even more importantly, guarantees that only a single reference is active rather than relying on the programmer to guarantee this.
4 Likes
Wow, I have a whole new appreciation for this rule now!
Thank you, everyone!
3 Likes
As I know the data race is:
typically it refers to a situation where a memory operation in one thread could potentially attempt to access a memory location at the same time that a memory operation in another thread is writing to that memory location
What is race condition? Could you provide an example of it?
Here is an example in Wikipedia of a race condition that could occur in Rust when using simple atomic load/store operations, with no other synchronization.
1 Like
Summary of the topic:
The Rules of References
At any given time, you can have either one mutable reference or any number of immutable references.
The above quote is from The Book. You might ask yourself why this rule exists at all and what problems it prevents. Maybe the first answer that comes to mind is that it prevents data races in multi-threaded programs. But the usefulness of this rule isn’t just limited to preventing data races; it also has benefits in single-threaded programs, which you will appreciate once you understand them!
Preventing Dangling Pointers (Use-After-Free Errors)
For example:
fn push_all(from: &Vec<i32>, to: &mut Vec<i32>) {
for i in from.iter() {
to.push(*i);
}
}
fn my_function() {
let mut vec = vec![1,2,3];
push_all(&vec, &mut vec);
}
This would be disastrous! As we're pushing elements onto the vector, it may need to resize, allocating new memory and copying its elements over to it. The iterator would then be left with a dangling pointer into the old memory, leading to memory unsafety (causing potential segmentation faults or worse).
Here’s another example:
let mut v = vec![0, 1, 2];
let r1 = &mut v;
let r2 = &v[2];
// This drops the original vec and frees its memory.
*r1 = vec![];
// This would access the freed memory, if Rust allowed it.
assert_eq!(*r2, 2);
Optimization
If the compiler knows that there is only one pointer to a memory block, it can produce better optimized code. This rule ensures that only a single active reference exists so that the compiler can perform optimizations. Reading this article about C’s restrict can help get the idea.
Consider this simple example:
fn fill<T: Copy>(input: &T, output: &mut [T]) {
for elem in output {
*elem = *input;
}
}
Knowing that input can’t point to part of output, the compiler can generate machine code that copies *input into a register (if it’s small enough) once, and then copies that register to *elem in the loop.
If it didn’t know this, it would have to read input on every iteration of the loop because one of the previous iterations might have overwritten the value.
The compiler can also use vectorization and the CPU’s SIMD (Single Instruction, Multiple Data) capability to perform multiple operations in parallel, which improves performance. For example, consider a loop like this:
pub fn rev_swap<T>(a: &mut [T], b: &mut [T], n: usize) {
let (a, b) = (&mut a[..n], &mut b[..n]);
for i in 0..n {
std::mem::swap(&mut a[i], &mut b[n-1-i]);
}
}
Can the compiler vectorize this loop? In Rust, yes, but only because of the "one mutable reference" rule — the two slices cannot overlap due to this rule.
Without the rule, the slices might overlap, meaning the compiler would need to preserve the exact behavior by performing reads and writes in the specific order in the code because one loop iteration might affect the next. But since they don’t overlap, the compiler knows it’s an "embarrassingly parallel" loop at the SIMD level, allowing it to optimize accordingly.
Thanks to @quinedot, @kpreid, @SkiFire13, @jumpnbrownweasel and @scottmcm
5 Likes