Unifying borrow and reborrow (conceptually) via access

Reborrow as a feature of the Rust type system has often been considered "compiler magic", poorly documented. But IMO it plays a very fundamental role in Rust's whole logic of ownership and borrowing. So this short tutorial is about my understanding on reborrow, and also borrow, through a unified concept: manipulation of access.

First I want to show why the borrow rules of Rust fail to explain reborrow well. Consider the following program:

let mut i = 1; // forget i32 being copyable for a moment
let m1 = &mut i;
let m2 = &mut *m1;
*m2 = 2;
*m1 = 3;

The above code compiles, but when we are assigning to m2, both m1 and m2 are still not completely out of scope, despite they are both borrow to i.

Of course, this behavior won't violate the "only one mutable borrow" principle if we take NLL's non-continuous lifetime into concern: m1 is live before and after the *m2 = 2 line, but is not during that line. But this simple explanation cannot tell why swapping the two assignments lead to a type error. To also cover this behavior, we will need an extra rule that the lifetime of two mutable borrows must not "overlap". We require one of them's scope to be contained in that of the other.

Still, the above rules cannot fully account everything. If we instead define m2 as &mut i, i.e. direct borrow to i instead of reborrow of m1, the above code would not compile. This time we have to add the rules for reborrow.

Now that we have explained all the behaviors above, IMO this explanation is by no means satisfactory. The "no overlap" rule and rules for reborrow seem artificial, and that probably contributes to the "compiler magic" impression of reborrow. Well the Rust type system is very complex, and magics unavoidably exist here and there. But what if there happens to be a better explanation in this particular case? And that's what I'm going to propose below: a (not sure if it is novel) unifed view of borrow and reborrow via the concept of access.

Although it is not an official terminology, the concept of access appears in a quite obvious way in Rust (assume T is a non-copy type):

  • A value of type T has the owner (= read + write + deallocate) access to an address holding T
  • A value of type &mut T has a (unique) mutable borrow (= read + write) access to an address holding T
  • A value of type &T has a (shared) immutable borrow (= read) access to an address holding T

We can rephrase the process of borrowing using the language of access. When we borrow from a owner, what we are actually doing is borrowing the access to the address of the owner, mutably or immutably. When the owner is being moved, assigned, or killed, no borrow of it must live, because we need to take back the access of the owner to perform these operations.

Now what about reborrow? From the view of access, reborrowing is nothing but manipulating a non-owner access. Let's illustrate this by a simple case analysis:

  • reborrowing a mutable borrow mutably: the borrowee holds a read-write access to some address borrowed elsewhere, now we take away that access temporarily and pass it to the borrower.
  • reborrowing a mutable borrow immutably: similar to the above case, but instead of passing the borrowed read-write access down directly, we turn it into many read access'es.
  • reborrowing a immutable borrow immutably: similar

So from the view of access, borrowing and reborrowing are essentially the same thing: manipulation and borrowing of access. To unify borrowing and reborrowing, we only need a slight modification to the famous "one mutable or many immutable" rule: we generalize it to a access borrowing diagram, as follows:
borrow-diagram
The arrows indicate valid directions of borrowing and manipulating the access.
The "owner" onde is lacking a self-looping an arrow, because Rust requires unique ownership for memory management, i.e. the deallocation access must not be borrowed.

Now let's rephrase the principles of Rust using the language of access:

  • Access of values may be bororwed, according to the diagram above
  • When a value is moved, assigned or is dropping out of scope, it must take back all of its access

Let's apply these rephrased principles to see if it can proprely explain the examples at the beginning of this post:

let mut i = 1; // forget i32 being copyable for a moment
let m1 = &mut i; // m1 borrows its access from i
let m2 = &mut *m1; // m2 (re)borrows its access from m1
*m2 = 2; // m2 using its access for writing
*m1 = 3; // We are assigning to m1 here, so m1 must take back its access.
         // Hence m2 must drop out of scope here.
// Now m1 is still usable, but m2 is not

If we exchange the two assignments:

let mut i = 1; // forget i32 being copyable for a moment
let m1 = &mut i; // m1 borrows its access from i
let m2 = &mut *m1; // m2 (re)borrows its access from m1
*m1 = 3; // We are assigning to m1 here, so m1 must take back its access.
         // Hence m2 must drop out of scope here.
*m2 = 2; // Now m2 already drops out of scope, type error!

If we instead set m2 = &mut i:

let mut i = 1; // forget i32 being copyable for a moment
let m1 = &mut i; // m1 borrows its access from i
let m2 = &mut i; // m2 borrows from i directly
                 // To afford this new borrow, i must take its access back
                 // Hence m1 must drop out of scope
*m2 = 2; // m2 using its access for writing
*m1 = 3; // m1 already drops out of scope, type error!

Yay, the new principles work perfectly! Finally, if you are aware of the stacked borrow model used to test unsafe code, the access explanation above can also deduce the principles of stacked borrow. Assume we have a chain of mutable (re)borrows:

owner -> m1 -> m2 -> ... -> mn

If we now assign to m1, m1 must take back its access, from m2. So m2 must drop out of scope, but this in turn requires m2 to take back its access. Ultimately, everything from m2 to mn must be killed, or "popped out of the stack" in the stacked borrow model, in order to assign to m1.

2 Likes

Nits:

  • Missing a ; in the first code block
  • You sometimes use i and sometimes use x.

I also think of stacked borrows as "non-crossing" (in execution timeline; I haven't bothered to write it up or explore it for complex scenarios like visualizing loops).

Fixed, thx.

Yes, IMO stacked borrow and the "non-crossing" rule are really describing the same behavior of reborrowing. The main difference lies in the fact that stacked borrow is an executable semantic for checking unsafe code dynamically, the "non-crossing" rule being a static borrow checking rule for safe Rust instead.