Extending the borrow checker

1

Preface

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

Inactive Mutable Reference

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.

Mutability Promotion / Structure Tags

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.

Combining Inactive Mutable Reference and Element Tags

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 :)
}
2

You need to distinguish between a mut binding...

let mut x = String::new();
match some_option {
    Some(mut inner) => { ... }
    None => {}
}

...and &mut _s. The former disallows taking a &mut _ to the binding (you can't use &mut x) and disallows reassigning the variable (you can't x = ... a second time without introducing a new binding). But that's it. If you take a compiling program and make every non-mut binding mut, the program will still compile with no change in semantics. It will just print a ton of warnings when compiling.

&mut _ on the other hand are the exclusive bits. Aliasing the referent of an active &mut _ is UB.

(But defining exactly when this happens is tricky.)

The borrow checker prevents r3 from being used so long as the borrows in r1 and r2 are active. r3 is temporary inactivated, if you will.

The original borrow of s in the first r3 can expire after the first println, since it won't be used anymore. Similar to how r1 and r2's borrows expire after the second println.

One reason is consistency and the ability to reason about what's UB or not, for example in unsafe code.

Another is that it's just more in line with how compilers work, and how Rust has made Rust lifetimes ('a things) part of variable's types. The borrow checker uses liveness analysis (a general compiler technique) to know when the variable is alive, which keeps the lifetime in the type of the variable alive, which can keep the borrow alive.

This would be UB if both loops are allowed to run. What in your model prevents it?

    let mut m = Arc::new(String::from("Hi"));
    let mr = Arc::get_mut(&mut m).unwrap();

    let other = m.clone();
    thread::spawn(move || {
        loop {
            sleep(Duration::from_secs(1));
            println!("{other}");
        }
    });

    loop {
        sleep(Duration::from_secs(10));
        mr.push_str("!");
    }

The most important parts of NLL were applied in 2018. Probably very few people noticed the final throwing of the switch in 2022, but pretty much everyone could tell the difference after NLL first landed.

There have been occasional smaller improvements since then, and std has scoped threads now. The next-gen borrow checker (Polonius) will solve a few more problems, e.g. involving conditionally returned borrows.

Sounds like branded indices, maybe. From the human text anyway.

Sometimes you can use shared (interior) mutability temporarily instead of changing your data structures (but I recognize it has limited applicability).

There is an interest in the ability to refine what fields methods borrow, so you don't have to borrow the whole thing like &self and &mut self require. Search for "view types".

2 Likes
3

Avoiding data races is not the primary goal, it's just a nice consequence of the rules chosen by Rust. The main goal is avoiding temporary memory safety issues, most notably use-after-free issues.

Sure, unique references are not the only way you can do mutations. See for example these recent blogposts on alternative ideas:

The issues in general is that you either need to introduce some pretty big limitations, or you need to perform some very hard analysis (for which you probably need to also need to introduce limitations in order to make it reasonable in practice).

Simple code like your example could be made to work, but what's the point of it if the same approach doesn't scale to real programs? The danger is that this ends up creating a situation where the toy example you write while learning work but then the same approach fail once you start putting into practice what you learned, not too different from how people get confused while learning ownership because i32 is Copy and doesn't need to follow the same rules as other types like Vec.

It's subtle but it does something other than just adding some code: it changes the meaning of the next line, making its r3 resolve the new variable just created rather than the initial one. That is, it removes a use of the original r3 variable.

This is unfortunately unsound because there's currently unsafe code relying on the current behaviour. For example Cell::get_mut and Cell::set would be unsound with this kind of mutable reference, even just with the "demotion" part, because it assume you should not be able to call methods taking &self (e.g. Cell::set) while holding on a mutable borrow of the value (e.g. any reference derived from the result of Cell::get_mut). Calling Cell::set is obviously problematic because it can invalidate such references, e.g. by causing a deallocation of the memory they point to.

A more "weird" example is std::thread::scope, where the scope object hold a borrow of any data that is passed to a spawned thread. Even though the scope object might be unused in a certain moment the thread in the background could still access the data it borrowed, so it's important that no demotion occurs in this situation.

This doesn't mean there can't be a world where your proposal holds, but at least Cell::get_mut, RefCell::get_mut, Mutex::get_mut, Arc::get_mut, Arc::make_mut, std::thread::scope and possibly others would not be able to exist there.

4

Re:

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.

The way you say "Variables r1 and r2 will not be used after this point." in Rust is

    drop(r1);
    drop(r2);

which the borrow checker understands.

Or, better, enclose the code with local variables in { }, so they go out of scope before you want to borrow again.

5

Some code could have temporarily put an invalid (non-String) value at location of s, with guarantee to restore it to a valid instance before the mutable reference expires. That is a sound unsafe pattern now.

6

In this case it's not:

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's try to ensure this by `drop`ping them.
drop(r1);
drop(r2);
println!("{r1} and {r2}"); // oops, they're still available, and this isn't an error!
7

A bit of confusion of ideas I think: shared references are Copy so drop doesn't move out the value.

This basically makes drop() the way you say "this is the last use... if it matters."

The problem of course is that the error in the original snippet is creating the shared references in the first place. If they were permitted due to some local reasoning trick, the rest of Rust doesn't have any issue with the rest of that code.

1 Like
8

Honestly, these were more a theoretical exercise and I didn't think these ideas would ever actually get incorporated. I was pretty sure there would be some unsafe code that depended on the current behavior that would break if a change was made. Though, I hadn't thought of any specific examples.

Theoretically, because Arc does it's own reference counting it could also perform checks before cloning and either panic or return an option, but that change would cause it's own host of new problems.

I thought this is what would happen, but I figured I'd give it a whack anyways.

I'll have to look into these.

I did not write this, it was copied directly from The Book, see link in the original post.

9

With the signature...

pub fn get_mut(this: &mut Arc<T, A>) -> Option<&mut T>

...there's no way for the Arc to perform some action when the returned &mut T stops existing. Or if you prefer, the only way for it to "know" that the returned &mut T doesn't exist is when another method is called, because that's only possible once the &mut T doesn't exist anymore. But that's the very property that would go away with "resuming &muts".

Anyway, the exclusiveness of &mut _ is a fundamental property that can be relied upon for logical invariants in safe code, not just soundness in unsafe code.

1 Like
10

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.