Reborrow: difference when explicitly dropping parent reference vs falling out of scope?

abigagli · August 15, 2023, 9:15am

I'm trying to internalise how reborrowing actually works.
Consider the following snippet:

struct Thing;

let mut owner = Thing;
let parent_ref = &mut owner;
let sub_ref = &mut *parent_ref; // Reborrow here

From my understanding, the peculiarity of reborrowing is that sub_ref does NOT directly borrow the owned value, instead it "goes through" parent_ref which effectively results as borrowed and hence unusable while sub_ref is in scope.

But I also thought that since parent_ref results borrowed, the compiler wouldn't allow me to do something like

// THIS COMPILES
let mut owner = Thing;
let sub_ref: &mut Thing;
{
    let parent_ref = &mut owner;
    sub_ref = &mut *parent_ref; // <-- Reborrow here

    // parent_ref goes out of scope
}
dbg!(sub_ref); // Just use sub_ref

Only if I add an explicit drop of parent_ref, I then get a compiler error

// THIS DOES NOT COMPILE
let mut owner = Thing;
let sub_ref: &mut Thing;
{
    let parent_ref = &mut owner;
    sub_ref = &mut *parent_ref; // <-- Reborrow here

    std::mem::drop(parent_ref);
}
dbg!(sub_ref); // Just use sub_ref

I thought that if sub_ref effectively borrows parent_ref, then parent_ref wouldn't be allowed to go out of scope while sub_ref was alive, similarly to the classic example

let borrower: &Thing;
{
    let owner = Thing;
    borrower =&owner;
}
dbg!(borrower);

I realise this probably doesn't have to do directly with re-borrowing but it is probably something more fundamental like:
parent_ref can go out of scope even if it is borrowed since it is itself a reference (i.e. a non-owning binding)?
In other words, unless I explicitly try to use it (i.e. with std::mem::drop), just going out of scope doesn't count as a use-while-borrowed?

quinedot · August 15, 2023, 9:40am

Yes, that's pretty much correct. References can go out of scope without it counting as a use of what they reference, but moving or reborrowing a &mut (e.g. by passing it to mem::drop) is definitely such a use.^[1] And that use conflicts with the referenced value being (re-)borrowed.

Though not well documented, this actually comes up all the time. Consider this function:

pub const fn first_mut(self: &mut [T]) -> Option<&mut T> {
    match if let [first, ..] = self { Some(first) } else { None }
}

The &mut reference which is self falls out of scope at the end of the function, yet the borrow which takes place through self is allowed to persist after the return of the function. Moreover, &mut are not Copy, so self is often^[2] a reborrow of something else.

Be careful here -- parent_ref is not borrowed.^[3] Instead, *parent_ref is reborrowed. If you change the example like so:

    {
        let mut parent_ref = &mut owner;
        sub_ref = &mut parent_ref; // no longer a reborrow of `*parent_ref`
    }
    dbg!(sub_ref); // Just use sub_ref

Then it no longer compiles. Going out of scope is still a "use" of parent_ref (but not of *parent_ref).

The idea is that mem::drop is free to read and mutate everything reachable through the &mut, for example. ↩︎
maybe even always, as far as the compiler is concerned? ↩︎
Even though the lifetime of its type did become part of a constraint on sub_ref's type's lifetime. ↩︎

steffahn · August 15, 2023, 10:42am

I usually think of what a re-borrow let r: &mut T = &mut *other; can achieve as some kind of hybrid operation, which incorporates the following possible behaviors

moving other into r
borrowing other (which would yield a &mut &mut T) and then dereferencing (yielding a shorter-lived &mut T, based on a borrow of other)

Most (or maybe all(?)) cases of re-borrows should be explainable following either of these interpretations – just think of the compiler being smart and choosing the right behavior as required. (It helps that the machine code for either of these things is the same, so there’s no actual “choice” to be made, and the borrow-checker can feel free to come up with some way to model the union of both of these things.)

vague · August 15, 2023, 12:22pm

Thanks for pointing it out. You're right.

I have to admit we can't always see the reborrow step in MIR by trying more snippets

fn f() {
    let mut owner = Thing;
    let sub_ref = &mut owner;
    sub_ref.f();
    sub_ref.f();
}
// MIR
fn f() -> () {
    ...
    scope 1 {
        debug owner => const Thing;
        let _2: &mut Thing;
        scope 2 {
            debug sub_ref => _2;
        }
    }
    bb0: {
        _2 = &mut _1;
        _3 = Thing::f(_2) -> bb1; // Note: this is a reborrow! If it's not, `Thing::f(move _2)` should be seen.
    }
    bb1: {
        _4 = Thing::f(_2) -> bb2; // An implicit reborrow too.
    }
    ...
}

By comparison, explicit reborrowing in MIR

fn g() {
    let mut owner = Thing;
    let mut sub_ref = &mut owner;
    sub_ref.f();
    sub_ref.f();
    let sub_sub_ref = &mut sub_ref; // this line affacts how reborrows display in MIR
    sub_sub_ref.f();
}
// MIR
fn g() -> () {
    ...
    scope 1 {
        debug owner => const Thing;
        let mut _2: &mut Thing;
        scope 2 {
            debug sub_ref => _2;
            let _7: &mut &mut Thing;
            scope 3 {
                debug sub_sub_ref => _7;
            }
        }
    }
    bb0: {
        _2 = &mut _1;
        _4 = _2; // The reborrow can be seen here.
        _3 = Thing::f(move _4) -> bb1 // But this is mere move, no reborrow.
    }
    bb1: {
        _6 = _2; // The reborrow can be seen here.
        _5 = Thing::f(move _6) -> bb2; // But this is mere move, no reborrow.
    }
    bb2: {
        _7 = &mut _2;
        _9 = deref_copy (*_7);
        _8 = Thing::f(_9) -> bb3;
    }
    ...
}

steffahn · August 15, 2023, 12:41pm

FYI, I had answered to the original post, having barely skimmed yours – if you felt like my view added some perspective that made you re-think your answer though, that’s alright, I guess ^⁠_⁠^

steffahn · August 15, 2023, 1:02pm

Regarding mir (output in the playground), it looks to me as if that mir has seen (at least some minor) optimizations. I’m too lazy to look up compiler flags that one could perhaps run manually to output less optimized mir.

One way to see the difference between move and re-borrow nonetheless is if you put the value into a struct. E.g.

fn f(x: &mut i32) {
    let y: (&mut _,) = (x,);
    *y.0 += 1;
}
fn g(x: &mut i32) {
    let y: (_,) = (x,);
    *y.0 += 1;
}

the &mut _ type annotation makes the compile introduce an implicit reborrow. The resulting mir

fn f(_1: &mut i32) -> () {
    debug x => _1;                       // in scope 0 at src/lib.rs:1:6: 1:7
    let mut _0: ();                      // return place in scope 0 at src/lib.rs:1:19: 1:19
    let _2: (&mut i32,);                 // in scope 0 at src/lib.rs:2:9: 2:10
    let mut _3: (i32, bool);             // in scope 0 at src/lib.rs:3:5: 3:14
    let mut _4: &mut i32;                // in scope 0 at src/lib.rs:2:9: 2:10
    let mut _5: &mut i32;                // in scope 0 at src/lib.rs:2:9: 2:10
    let mut _6: &mut i32;                // in scope 0 at src/lib.rs:2:9: 2:10
    scope 1 {
        debug y => _2;                   // in scope 1 at src/lib.rs:2:9: 2:10
    }

    bb0: {
        _2 = (_1,);                      // scope 0 at src/lib.rs:2:24: 2:28
        _4 = deref_copy (_2.0: &mut i32); // scope 1 at src/lib.rs:3:5: 3:14
        _3 = CheckedAdd((*_4), const 1_i32); // scope 1 at src/lib.rs:3:5: 3:14
        _5 = deref_copy (_2.0: &mut i32); // scope 1 at src/lib.rs:3:5: 3:14
        assert(!move (_3.1: bool), "attempt to compute `{} + {}`, which would overflow", (*_5), const 1_i32) -> bb1; // scope 1 at src/lib.rs:3:5: 3:14
    }

    bb1: {
        _6 = deref_copy (_2.0: &mut i32); // scope 1 at src/lib.rs:3:5: 3:14
        (*_6) = move (_3.0: i32);        // scope 1 at src/lib.rs:3:5: 3:14
        return;                          // scope 0 at src/lib.rs:4:2: 4:2
    }
}

fn g(_1: &mut i32) -> () {
    debug x => _1;                       // in scope 0 at src/lib.rs:5:6: 5:7
    let mut _0: ();                      // return place in scope 0 at src/lib.rs:5:19: 5:19
    let _2: (&mut i32,);                 // in scope 0 at src/lib.rs:6:9: 6:10
    let mut _3: (i32, bool);             // in scope 0 at src/lib.rs:7:5: 7:14
    let mut _4: &mut i32;                // in scope 0 at src/lib.rs:6:9: 6:10
    let mut _5: &mut i32;                // in scope 0 at src/lib.rs:6:9: 6:10
    let mut _6: &mut i32;                // in scope 0 at src/lib.rs:6:9: 6:10
    scope 1 {
        debug y => _2;                   // in scope 1 at src/lib.rs:6:9: 6:10
    }

    bb0: {
        _2 = (move _1,);                 // scope 0 at src/lib.rs:6:19: 6:23
        _4 = deref_copy (_2.0: &mut i32); // scope 1 at src/lib.rs:7:5: 7:14
        _3 = CheckedAdd((*_4), const 1_i32); // scope 1 at src/lib.rs:7:5: 7:14
        _5 = deref_copy (_2.0: &mut i32); // scope 1 at src/lib.rs:7:5: 7:14
        assert(!move (_3.1: bool), "attempt to compute `{} + {}`, which would overflow", (*_5), const 1_i32) -> bb1; // scope 1 at src/lib.rs:7:5: 7:14
    }

    bb1: {
        _6 = deref_copy (_2.0: &mut i32); // scope 1 at src/lib.rs:7:5: 7:14
        (*_6) = move (_3.0: i32);        // scope 1 at src/lib.rs:7:5: 7:14
        return;                          // scope 0 at src/lib.rs:8:2: 8:2
    }
}

differs in

_2 = (_1,);

vs

_2 = (move _1,);

one can see even more differences, if the reference is also reborrowed or moved out of some struct:

fn f(x: (&mut i32,)) {
    let y: (&mut _,) = (x.0,);
    *y.0 += 1;
}
fn g(x: (&mut i32,)) {
    let y: (_,) = (x.0,);
    *y.0 += 1;
}

fn f(_1: (&mut i32,)) -> () {
    debug x => _1;                       // in scope 0 at src/lib.rs:1:6: 1:7
    let mut _0: ();                      // return place in scope 0 at src/lib.rs:1:22: 1:22
    let _2: (&mut i32,);                 // in scope 0 at src/lib.rs:2:9: 2:10
    let mut _3: (i32, bool);             // in scope 0 at src/lib.rs:3:5: 3:14
    let mut _4: &mut i32;                // in scope 0 at src/lib.rs:1:6: 1:7
    let mut _5: &mut i32;                // in scope 0 at src/lib.rs:2:9: 2:10
    let mut _6: &mut i32;                // in scope 0 at src/lib.rs:2:9: 2:10
    let mut _7: &mut i32;                // in scope 0 at src/lib.rs:2:9: 2:10
    scope 1 {
        debug y => _2;                   // in scope 1 at src/lib.rs:2:9: 2:10
    }

    bb0: {
        _4 = deref_copy (_1.0: &mut i32); // scope 0 at src/lib.rs:2:25: 2:28
        _2 = (_4,);                      // scope 0 at src/lib.rs:2:24: 2:30
        _5 = deref_copy (_2.0: &mut i32); // scope 1 at src/lib.rs:3:5: 3:14
        _3 = CheckedAdd((*_5), const 1_i32); // scope 1 at src/lib.rs:3:5: 3:14
        _6 = deref_copy (_2.0: &mut i32); // scope 1 at src/lib.rs:3:5: 3:14
        assert(!move (_3.1: bool), "attempt to compute `{} + {}`, which would overflow", (*_6), const 1_i32) -> bb1; // scope 1 at src/lib.rs:3:5: 3:14
    }

    bb1: {
        _7 = deref_copy (_2.0: &mut i32); // scope 1 at src/lib.rs:3:5: 3:14
        (*_7) = move (_3.0: i32);        // scope 1 at src/lib.rs:3:5: 3:14
        return;                          // scope 0 at src/lib.rs:4:2: 4:2
    }
}

fn g(_1: (&mut i32,)) -> () {
    debug x => _1;                       // in scope 0 at src/lib.rs:5:6: 5:7
    let mut _0: ();                      // return place in scope 0 at src/lib.rs:5:22: 5:22
    let _2: (&mut i32,);                 // in scope 0 at src/lib.rs:6:9: 6:10
    let mut _3: &mut i32;                // in scope 0 at src/lib.rs:6:20: 6:23
    let mut _4: (i32, bool);             // in scope 0 at src/lib.rs:7:5: 7:14
    let mut _5: &mut i32;                // in scope 0 at src/lib.rs:6:9: 6:10
    let mut _6: &mut i32;                // in scope 0 at src/lib.rs:6:9: 6:10
    let mut _7: &mut i32;                // in scope 0 at src/lib.rs:6:9: 6:10
    scope 1 {
        debug y => _2;                   // in scope 1 at src/lib.rs:6:9: 6:10
    }

    bb0: {
        _3 = move (_1.0: &mut i32);      // scope 0 at src/lib.rs:6:20: 6:23
        _2 = (move _3,);                 // scope 0 at src/lib.rs:6:19: 6:25
        _5 = deref_copy (_2.0: &mut i32); // scope 1 at src/lib.rs:7:5: 7:14
        _4 = CheckedAdd((*_5), const 1_i32); // scope 1 at src/lib.rs:7:5: 7:14
        _6 = deref_copy (_2.0: &mut i32); // scope 1 at src/lib.rs:7:5: 7:14
        assert(!move (_4.1: bool), "attempt to compute `{} + {}`, which would overflow", (*_6), const 1_i32) -> bb1; // scope 1 at src/lib.rs:7:5: 7:14
    }

    bb1: {
        _7 = deref_copy (_2.0: &mut i32); // scope 1 at src/lib.rs:7:5: 7:14
        (*_7) = move (_4.0: i32);        // scope 1 at src/lib.rs:7:5: 7:14
        return;                          // scope 0 at src/lib.rs:8:2: 8:2
    }
}

now apparently we have

        _4 = deref_copy (_1.0: &mut i32); // scope 0 at src/lib.rs:2:25: 2:28
        _2 = (_4,);                      // scope 0 at src/lib.rs:2:24: 2:30

vs

       _3 = move (_1.0: &mut i32);      // scope 0 at src/lib.rs:6:20: 6:23
       _2 = (move _3,);                 // scope 0 at src/lib.rs:6:19: 6:25

(the re-numbering of variable names should be irrelevant, so think of _4 and _3 as the same)

I’m not familiar enough with mir to know the meanings of move or deref_copy or operations like creating a tuple with or without the “move”. Also, in Release mode, you’ll gain additional StorageLive / StorageDead annotations that are also slightly different between these examples, for which I’m also not 100% certain what precise meaning they have.

vague · August 15, 2023, 1:19pm

Indeed. Reborrow vs move can be observed in MIR. But the MIR output is fragile and it's difficult to tell the nuances.

abigagli · August 15, 2023, 5:51pm

Oh this is an important point I was missing, thanks for pointing it out.

I think what you're saying is basically what is shown in Example 1 of the reborrow constraints section of the NLL RFC:

Going back to my initial snippet and adding some lifetime annotation

struct Thing;
let mut owner = Thing;
let parent_ref: &’parent mut Thing = &’parent mut owner;
let sub_ref: &’sub mut Thing = &’sub mut *parent_ref; // Reborrow here

What happens is not that parent_ref is borrowed, but rather that an implicit 'parent: 'sub bound is added so that owner is considered borrowed as long as sub_ref is in use

EDIT: While I am at it (I mean reading through the reborrow constraint), I'm having a hard time understanding what does the sentence in bold below mean in the description of the supporting prefixes algorithm:

The supporting prefixes for an lvalue are formed by stripping away fields and derefs, except that we stop when we reach the deref of a shared reference. Inituitively, shared references are different because they are Copy -- and hence one could always copy the shared reference into a temporary and get an equivalent path

I get that shared references are Copy, but I can't grasp the mentioned intuition: what does it mean to copy a shared reference in a temporary and get an equivalent path? Why does that imply that you can stop the enumeration of the supporting prefixes?

quinedot · August 15, 2023, 6:58pm

If you have a x: &'a mut &'b (String, String), say, you can get a &'b String out of it by copying the inner shared reference.

// let y: &'b String = &(**x).0;
let tmp: &'b (String, String) = *x;
let y: &'b String = &(*tmp).0;

So there's no reason for the outer 'a to impose a constraint.

To generalize, consider this situation:

struct MySlice<'a>(&'a mut [String]);

impl<'a> MySlice<'a> {
    fn split_first_mut<'s>(&'s mut self) -> Option<&'a mut String> {
        // We can't get a `&'a mut String` from reborrowing through `self` as
        // that will impose a constraint (we can only get a `&'s mut String`).
        //
        // So to satisfy the signature, we need to get the inner `&'a mut _`
        // out from "behind" `self`.  Fortunately, the empty `&mut []` slice
        // can be conjured from nowhere (and implements `Default` even),
        // so we have a way to do this.
        let inner = std::mem::take(&mut self.0);
        
        // Now we have an unnested `&'a mut [String]` to work with and
        // don't have to worry about any `'s` constraints
        let (first, rest) = match inner {
            [] => (None, &mut [][..]),
            [s, tail @ ..] => (Some(s), tail),
        };
        
        self.0 = rest;
        first
    }
}

We worked around the constraints imposed by 's by moving the inner &'a _ "out from underneath" temporarily. In this example, we exploited &mut [] being special enough to be conjured from nowhere and swapped in the empty exclusive slice.

But in the case of shared references, which are Copy, it's trivial to get them out from underneath the outer reference -- you just copy them out! ^[1] The borrow checker understands this (by stopping the enumeration of supporting prefixes), so you don't have to go through the dance of creating explicit temporary copies.

You don't even need something to replace them with, because you're not moving from behind a borrow, you're copying. ↩︎

curoli · August 16, 2023, 1:22am

Hello,

Maybe I'm missing something, but I would have expected that

let mut a = Thing;
let b = & mut a;
let c = & mut * b;

should be equivalent to

let mut a = Thing;
let b = & mut a;
let c = & mut a;

After all, in either case, we end up with two exclusive references to the same thing, why should it matter how they were created?

The two are allowed to coexist as long as their usage doesn't overlap. Trying to use both at the same time will be an error.

quinedot · August 16, 2023, 2:42am

How do you define "usage doesn't overlap"? The lifetimes of reborrows do overlap with the original, which is what makes &mut usable most of the time. They also cover cases like splitting borrows across fields and soundly handling nested borrows.

Or from a different direction, if you want to ensure the two borrows of a don't alias, you need to provide some way of tracking that along with an argument of how that algorithm prevents aliasing. I.e. an alternative to how Rust prevents aliasing today (reborrows with their lifetimes and the NLL algorithm).^[1]

let b1 = & mut a;
let c1 = & mut a;

let b2 = & mut a;
let c2 = & mut * b2;

b1 and c1 are exclusive borrows of a (the creation of which is a use of a) that have independent lifetimes^[2] -- but lifetimes that must not overlap to avoid a borrow error. When you use a, any borrow of a must not be active, so b1 can't be usable after c1 is created.

But c2 is a reborrow of the place *b2 (the creation of which is a use of *b2 but not of a). The lifetime of c2's type is constrained by the lifetime of b2's type. c2 can't be usable after *b2 is used (and e.g. passing b2 somewhere would also be a use of *b2), nor after a is used (and the lifetime constraints are what creates a "breadcrumb trail" back from c2 to b2 to a).

This is a casual description of the NLL RFC algorithm; working through it formally tends to be tedious for humans. The most relevant portions here would be

let b1 = & mut a;   // Creation of loan of `a` with lifetime `'b1`

let c1 = & mut a;   // `b1` still active due to next line, but a
                    //    "deep write" of `a` occurs (borrow error)

let _use = b1;      // Use requiring `'b1` to be active

Versus

let b2 = &mut a;    // Creation of loan of `a` with lifetime `'b2`

let c2 = &mut *b2;  // Loan of `*b2` with lifetime `'c2` s.t. `'b2: 'c2`

let _use = b2;      // Use requiring `'b2` to be active

// ...but nothing has required `'c2` to be active here, so no borrow error
// even though this counts as a use of `*b2`.  `a` has not been used since
// the creation of `b2`.

Alternatively, you may have heard of "stacked borrows" or "tree borrows"; in those models, there must be a single path of exclusive borrowing back to some specific place/memory. Introducing a fresh borrow (c1) must therefore "cancel" any other existing borrows, where as reborrowing (c2) allows for extending an existing path.

a --&mut a-- b1
 `--&mut a-- c1 // has to "cancel" b1 or there'd be more than one path

a --&mut a-- b2 --&mut *b2-- c2 // There's just one path

Occasionally I've seen people say/feature-request "it'd be nice if this borrow could automatically re-activate where needed" or the like, but I don't think I've ever seen someone provide an actual algorithm, much less one with an argument of soundness etc. ↩︎
no lifetime constraints are introduced ↩︎

curoli · August 16, 2023, 12:28pm

Thank you so much for the detailed explanation!

I guess I wasn't thinking this through properly. I was somehow assuming that only data flow should matter. But, of course, there needs to be a measure of exclusivity, and that is currently before-after relationships.

I have a feeling it would be really useful to have a type of borrow checker that is more based on data flow than on code location, but coming up with something that is locally decidable will be tough.

abigagli · August 18, 2023, 3:42pm

Oh tanks again for the valuable insight.

I think I get it now:

while enumerating the supporting prefixes, you're "walking up" the chain of derefs adding

'cur_borrow: 'prev_borrow

constraints along the way.

But when you find a shared borrow you can stop walking up because you could have got that by "copying it out from underneath the outer reference" and use that as the starting point of the path leading down to what you're reborrowing without even knowing that there were further derefs up the chain.

If that makes sense...

At least it kind of does for me at the moment....

Thanks again.