Info
This started as a short post to help me better understand Rust's Borrow Checker. However, with the learning and research I did, it morphed into something more akin to a blog post. I don't run a blog and am not interested in just sharing my ideas. My main goal in posting this is to start a discussion about the ideas, such as improvements or critiques, to see if they are viable or not. That said, if there is something that I clearly don't understand I'm open to being corrected.
This post has some similarities to the post Overzealous borrow-checker (IMHO) - #9 by vitalyd. While these two posts are rooted in the same pain point, this post is more about potential changes to the language while the other is looking for help understanding the current state of Rust.
mut == unique
In the post mentioned above @trentj made some assertions that seamed a little backwards to me, and I haven't found any documentation that supports his statements. Specifically:
As I understand it @trentj is saying that the keyword mut labels an object or reference as unique/exclusive and mutability is enabled by uniqueness. However, I've always understood it to be that mut labels an object as mutable and uniqueness is used to ensure a data race does not occur. Given the current state of Rust, I can understand the mindset of framing it as uniqueness is the primary object and mutability follows uniqueness. However, from what I've read it doesn't sound like that is how the language evolved. Also that's not how the documentation frames it.
The first quote was from a comment about optimizations enabled by uniqueness. I believe compilers have other means of determining uniqueness and it wouldn't make sense to declare a variable mut just to ensure its unique if you aren't going to mutate it. In fact, now that I think about it, I've even seen a warning related to that:
warning: variable does not need to be mutable
I understand that the point of the borrow checker is to prevent data races, and that having a mutable reference alongside an immutable one can cause a data race. However, I ran into this case recently that made me think the rules are a little too strict. More specifically, I believe an immutable reference could be allowed along side a mutable reference in certain circumstances without introducing the potential for a data race.
Example 1 (from The Book)
Original snippet:
let mut s = String::from("hello");
let r1 = &s; // no problem
let r2 = &s; // no problem
println!("{r1} and {r2}");
// Variables r1 and r2 will not be used after this point.
let r3 = &mut s; // no problem
println!("{r3}");
Naively using the mutable reference before and after the immutable borrow:
let mut s = String::from("hello");
let r3 = &mut s; // no problem
println!("{r3}");
let r1 = &s; // 2nd borrow (error)
let r2 = &s; // 3rd borrow (error)
println!("{r1} and {r2}");
// Variables r1 and r2 will not be used after this point.
println!("{r3}");
Assuming r3 actually needs to be mutable, there are two easy ways to fix the errors:
let mut s = String::from("hello");
let r3 = &mut s; // no problem
println!("{r3}");
let r1 = &r3; // 1. borrow from r3 instead of s
let r2 = &r3; // 1. borrow from r3 instead of s
println!("{r1} and {r2}");
// Variables r1 and r2 will not be used after this point.
// 1. could also move above to a function with r3 as the input
let r3 = &mut s; // 2. duplicate mutable borrow
println!("{r3}");
Either of these two changes by themselves would fix the problem. For the fist solution, why is borrowing from the reference ok, but not borrowing from the source? The borrow checker didn't forget where the reference was borrowed from since that is the cause of the error. For the second solution, why should adding code after an error fix the error? It's not like that line actually does anything. It's a direct copy of a previous line that just shadows the original declaration. (While I understand in this case why adding a line after the error fixes it, this isn't always intuitive, especially when learning Rust.)
Example 2
let mut v = vec![1, 2, 3, 4];
for e in v.iter_mut() {
*e += 1;
println!("{:?}", &v); // 2nd borrow (error)
}
The error could easily be fixed like so:
let mut v = vec![1, 2, 3, 4];
for i in 0..v.len() {
v[i] += 1;
println!("{:?}", &v);
}
The 'fixed' code doesn't actually need to use the index, it's just a way to reference elements without borrowing. While this if fine when using contiguous lists where indexing is inexpensive, it doesn't work so well if the container is more expensive to index (e.g. linked list or tree). In that case the indexing operation can easily change the algorithm complexity from O(n) to O(n * log(n)) or even O(n^2)!
Solution: Inactive Mutable References
In between uses, a mutable reference is treated as an immutable reference for the purpose of borrow checking rules. Using a mutable reference could then be treated at promoting an immutable reference to a mutable reference directly before use and demoting it back to an immutable reference directly after use. The result is that no other references can exist when a mutable reference is used, but immutable references can be created and used in between usages of the mutable reference as long as it is not used after the next use of the mutable reference. Note that it's critical the mutable reference is considered immutable and not out of scope to prevent changing the state of the referenced object in between access. If a second mutable reference is needed in between usages, you can still create the new mutable reference as shown in the first example.
From The Book:
A data race is similar to a race condition and happens when these three behaviors occur:
- Two or more pointers access the same data at the same time.
- At least one of the pointers is being used to write to the data.
- Thereโs no mechanism being used to synchronize access to the data.
The only concern here is the third point. But as demonstrated in the first example, the compiler already has mechanisms to synchronize access without adding a new scope for every reference. Inactive mutable references would just be an extension of that mechanism. In the case of the second example, loop unrolling can be used to apply the same logic.
Postscript
In the post Overzealous borrow-checker (IMHO) - #9 by vitalyd, mentioned above, @daboross gives an example similar to Example 1 above and indicates that relaxing the uniqueness requirement for mutable borrows might be feasible.
It's been over 6 years since then, and it appears that some related changes to the borrow checker have been made in that time. Non-lexical lifetimes (NLL) is one example of such a change which appears to have been introduced in 2018 but not universally applied until 2022.
While I recognize that adding Inactive Mutable References would be a more involved change, and potentially more problematic change, I think it's still worth considering and discussing as a community.
Motivation
let mut v = vec![1, 2, 3, 4];
let l = v.len()
for i in 0..l {
if i == 0 { v = vec![0, 2, 4]; } // this is stupid, but hey, no errors!
v[i] += 1; // panics when i == l - 1
println!("{:?}", &v);
}
let mut v = vec![1, 2, 3, 4];
for e in v.iter_mut() {
// if i == 0 { v = vec![0, 2, 4]; } // error; just like I want
*e += 1;
// println!("{:?}", &v); // but now I can't do this :(
}
While this is essentially the same as example 2 for inactive mutable borrow and the solution below solves the same problem, each mechanisms has different applications and combining them would simplify code in many instances. See the section Combining Inactive Mutable Reference and Element Tags for an example.
Solution: Element Tags
While the exact implementation would need to be flushed out, the general concept is that a type can have an associated element tag type that can be passed to the an object of that type to access the element associated with the given tag. Types could then have a tags method that returns a means of iterating through all valid tags. Tags and tag iterators would only ever immutably borrow the structure of an object and a tag would need to be passed to the object to obtain a reference to the associated element.
What is meant by borrowing the structure is that the shape of the object could not be changed but the content could. For example, lists can't change size and trees can't change shape, but the values of the elements could change. Note that this could not be used for types where updating a value needs to update the structure (e.g. set, BST, heap, etc.).
One requirement to maintain the utility of the feature would be that every element access method would need to have constant time complexity so that iterating over tags and accessing elements has a comparable time complexity to iterating over elements. Additionally, the compiler would ideally be able to associate tag objects with the source object and provide an error if a tag object was passed to a different source object.
While some use cases of tags would have overlap with interior mutability types (i.e. Cell and RefCell), those types aren't ideal because they're intrusive and add other limitations (i.e. runtime borrow checking).
let mut v = vec![1, 2, 3, 4];
for t in v.tags() {
// if i == 0 { v = vec![0, 2, 4]; } // error; tags borrows from the structure
let e = &v.t; // borrows data like tuple field access; different syntax (i.e. &t(v), &v[t], something else)?
println!("{}", e); // last use of e
let m = &mut v.t; // borrowing the element not the structure (e out of scope)
// println!("{}", &v.t); // error; m would be the 2nd borrow
println!("{:?}", &v); // error; 2nd borrow
m += 1; // last use of m
let e = &v.t; // m considered out of scope
// println!("{}", m); // error; makes e the 2nd borrow
println!("{}", e);
println!("{}", &v.t);
println!("{:?}", &v); // tags is immutable borrow; this is allowed :)
}
Precedence
let mut t = (1, 2);
let p = &mut t;
// t = (0, 2, 4); // assignment after borrow (error)
let r = (&mut p.0, &mut p.1);
println!("{}, {}", r.0, r.1);
let mut v = vec![1, 2, 3, 4];
let p = &mut v;
// v = vec![0, 2, 4]; // assignment after borrow (error)
let t = p.len() / 2;
let a = &mut p[1];
println!("{}", a);
let (l, r) = p.as_mut_slice().split_at_mut(t);
println!("{:?}, {:?}", l, r);
Note: The purpose of p is to demonstrate that the element borrow can come from a reference and not just the owning value.
In these examples the tuple field access operators, index operator, and split_at_mut function (also chuncks_mut, etc.) could be considered mechanisms for obtaining a reference from a tag. However, while the tuple field access operators provide a compiler error when an invalid tag is used, the indices to the slice access operators and methods generally only provide runtime errors.
One major difference between element tags and these examples is that none of these mechanisms borrow from the source object before the element access occurs. As far as I know there are no means of only borrowing the structure and not the elements. However, adding that functionality could even have uses outside of tags. For example the len method on std::Vec only needs to borrow the structure, but currently using it can prevent mutable uses of the vec.
I recognize that this would likely be a bigger change than Inactive Mutable References, but I don't think it's unfeasible. It would likely require using lifetime annotations to specify that only part of an object is borrowed.
let mut v = vec![1, 2, 3, 4];
for t in v.tags() {
// if i == 0 { v = vec![0, 2, 4]; } // error; tags borrows from the structure
let e = &v.t; // tagged element access
println!("{}", e); // last use of e
let m = &mut v.t;
println!("{}", &v.t); // m is inactive mutable reference and considered immutable
println!("{:?}", &v);
m += 1; // last use of m
let e = &v.t; // m considered out of scope
// println!("{}", m); // error; m is not the only borrow
println!("{}", e);
println!("{}", &v.t);
println!("{:?}", &v); // tags is immutable borrow; this is allowed :)
}
1 post - 1 participant
๐ท๏ธ Rust_feed