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 holdingT
- A value of type
&mut T
has a (unique) mutable borrow (= read + write) access to an address holdingT
- A value of type
&T
has a (shared) immutable borrow (= read) access to an address holdingT
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:
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
.