[nll] move 2-phase borrows into MIR lowering

[nikomatsakis]

@RalfJung and I were talking and we realized that -- with a bit of work -- we could make 2-phase borrows be something fully handled during MIR lowering. This is nice because it means that the rest of the model (e.g., the Unsafe Code Guidelines aliasing model) doesn't have to be aware of it.

There are basically two places we use 2PB today. Let me break down at a high-level how to handle each of them.

Method calls, operators, etc

The first place is for a case like self.push(self.len()). Today, we lower to the push call to:

TMP0 = &mut2 self
TMP1 = lower<self.len()>
push(TMP0, TMP1)

The borrow checker finds the use of TMP0 on the last line and considers that the activation point. In particular, for each 2PB, there must be an exactly one use which is dominated by the borrow and which postdominates the borrow. This use is the activation point.

The idea would be to change to instead lower as:

TMP0 = &mut self
TMP1 = &*TMP0;
TMP2 = lower<self.len() where self=*TMP1>
push(TMP0, TMP2)

Here, we borrow self mutably as normal but then reborrow it to create a shared reference TMP1. Then, when we lower the arguments, any reference to self is rewritten so that it does not refer to self but rather *TMP1 (which has the same type as self). Then the normal NLL mechanisms come into play.

We'd obviously have to tweak our error messages here so that *TMP1 is displayed as "self" to the end-user.

The key observation here is that we can statically see all references to self while lowering the arguments and rewrite them to reference *TMP1 instead. (In fact, we already use a mechanism like this when lowering match guards, see below.)

Matches

We also rely on 2PB to handle variables in match pattern guards. The basic idea of how we lower something like this:

match foo {
  Some(ref mut x) if G => ... 
}

is that we introduce various artificial borrows. The first is a borrow of the place being matched (foo) -- that borrow begins when the match begins and ends upon entering some arm. The second is for bindings that are accessed during match arms. These are each implicitly mapped to a dereference of a shared borrow. So (today!) you wind up with something like:

// Start of match
B0 {
  TMP0 = &foo // the match borrow
  TMP1 = DISCRIMINANT(foo)
  if TMP1 == Some { goto B1 } else { B3 }
}

// We found `foo` is a `Some`
B1 {
  TMP2 = &mut2 foo.as<Some>.0
  TMP3 = &TMP2
  TMP4 = <lower G where x=*TMP3>
  if TMP4 is true { goto B2 }
}

// Corresponds to the `Some` arm:
B2 {
  DROP(TMP0) // borrow of `foo` ends as we enter the arm
  <lower arm body>
}

B3 { ... }

Again, this is what we do today. For this to work, we rely on TMP2 = &mut2 foo.as<Some>.0 being a 2-phase borrow that never gets activated, since otherwise it would overlap with the TMP0 borrow that is definitely still in scope.

Instead of that, we will create a shared borrow and then use some kind of case from &&T to &&mut T:

B1 {
  TMP2 = &foo.as<Some>.0
  TMP3 = &TMP2
  TMP4 = TMP3 as &&mut T
  TMP5 = <lower G where x=*TMP4>
  if TMP5 is true { goto B2 }
}

This cast is provably safe (@RalfJung has done it!), so there is no unsafe code or anything else involved here.

cc @pnkfelix @arielb1

UPDATE: Lightly edited for clarity.

[RalfJung]

The key point is that TMP2 = &mut2 foo.as<Some>.0 is a 2-phase borrow that never gets activated.

The "never gets activated" is important, because this blatantly overlaps with a shared borrow. So this is like an "immutable &mut". And the only reason we have it is that we want an & &mut T (the only use of TMP2 is TMP3 = &TMP2).

So yeah, the proposal is to instead create that &&mut T directly from an &&T, which is a safe conversion.

[nikomatsakis]

@RalfJung yep, reworded to make that a touch more explicit

[arielb1]

The match lowering - we currently break address consistency

I thought we were using TMP2 as x (i.e. the match binding) both inside the arm and inside the guard, but apparently we don't and the world doesn't explode.

However, having x be the same both within the guard and outside it means that x maintains a single consistent address during its lifetime, so e.g. this code always prints the same address twice (which I think is the right thing to do, but of course we can specify it either way).

#![feature(nll)]

fn main() {
    let mut x = 2;
    match x {
        ref mut t if {
            println!("In Guard: {:?}", (&t) as *const &mut i32);
            true
        } => {
            // with current play.rust-lang.org debug, this prints a different address
            // than in the guard.
            println!("In   Arm: {:?}", (&t) as *const &mut i32);
        }
        _ => {}
    }
}

The method lowering - array accesses

For a less "cosmetic" problem, I don't see how the proposed lowering would handle array indexes that might not be disjoint (and potentially similar cases involving unions). We can't rewrite x[j] to be a function of x[i] because it isn't.

#![feature(nll)]

fn main() { doit(0, 0); }

fn doit(i: usize, j: usize) {
    let mut x = [Vec::new(), Vec::new()];
    x[i].push(x[j].len());
}

[arielb1]

I think the "array access" problem is currently a bit "academic", because accessing things like Vec<T> involves calling Deref which loses the "purity magic", but it will become a bigger problem come DerefMove.

[RalfJung]

With DerefMove, couldn't we detect the "root" of what is being referenced, and then rewrite that? So with x[i].foo(x[j]), we'd rewrite x.

[arielb1]

Rewrite x to what?

[arielb1]

If we also allow for "complex" cases like x.a[i].foo(&mut x.b, x.a[j]), this rewriting starts feeling like reimplementing the borrow checker in the lowering.

In any case, why is DerefMove a required ingredient? You can't move from something that is borrowed.

[arielb1]

In addition to these "rewriting is a PITA" issues, there's also a more "fundamental" way to differentiate rewrite-based from "real 2-phase based" approaches: 2-phase borrows allow pre-existing immutable borrows to live right up to the activation point, as in:

fn main() {
    let mut x = vec![];
    let p = &x;
    x.push(p.len());
}

Unlike the previous examples which seem like a very natural combination of features, I'm less sure that this has to work to "not be a bug in 2ΦB" - either way would be "fine".

[RalfJung]

Rewrite x to what?

x[i].foo(x[j]) becomes

let tmp = &mut x;
let x2 = &*tmp;
let _1 = x2[j];
tmp[i].foo(_1)

but yeah, once we want to do this for more complex paths (in particular, once there are disjoint paths) this becomes more "interesting". x.a[i].foo(&mut x.b, x.a[j]) we could handle by saying "we apply the rewriting based on the path before the first Index", but that might fail otherwise.

In addition to these "rewriting is a PITA" issues, there's also a more "fundamental" way to differentiate rewrite-based from "real 2-phase based" approaches: 2-phase borrows allow pre-existing immutable borrows to live right up to the activation point, as in:

Yeah, this will never be as powerful as "full" 2-phsae borrows.

Funny enough, I find your example actually easier to think about in terms of my RustBelt model of types that x.push(x.len()). Namely, after

    let mut x = vec![];
    let p = &x; // let's call this lifetime 'a

there is something you have in your typing context (we called it a "blocked type assignment") which says that once 'a is over, you get full permissions for x back. All two-phase borrows would do here now is to change this to

1. Also remember in that blocked assignment that x is shared for 'a (we would need for for other stuff as well), and
2. make that &mut x (part of the method call) have the effect that x changes to "once 'a is over, you have a mutable borrow to x" -- essentially "chaining" the proof that from owning x we can create a mutable borrow together with the blocked type assignment for x.

Obviously I haven't worked this out in all details, but it seems at least plausible. I would then also think the same way about x.push(x.len()): We first create a shared reference and obtain a blocked type assignment for x, and then we do the &mut x for the first parameter of push.

---

Now what does this mean for stacked borrows? I suppose it means we would allow creating a &mut for a frozen location as long as it does not get activated.

[nikomatsakis]

@RalfJung @arielb1

but yeah, once we want to do this for more complex paths (in particular, once there are disjoint paths) this becomes more "interesting". x.a[i].foo(&mut x.b, x.a[j]) we could handle by saying "we apply the rewriting based on the path before the first Index", but that might fail otherwise.

Note though that we don't currently handle examples involving Deref or Index. My assumption has been that if we want to handle things like Index trait, we are going to have to go to something more like @arielb1's Ref2 — that is, a more fundamental expansion of what a lifetime is. In particular, I think we need to trace those results through the type.

This is however the largest source of regressions (aka bugfixes). Most of them have the form of something like vec[i] += vec[j], though sometimes it is something like foo(&mut bar, bar.baz()). It may or may not be something we wind up wanting to fix.

Another thing to consider: how the Polonius model comes into play here. Until now, Polonius and 2-phase were orthogonal. I had expected to transition the existing codebase to use Polonius once we "ship" — something which, actually, gets a lot easier if we do the rewriting-based approach we are talking about here — but maybe it's worth thinking about how we can model something like 2-phase there as well. (That .. doesn't seem too hard. In particular, I could imagine threading a kind of "Activated" fact along.)