Two-Phase Borrows Are Just Dominator Queries: How `v.push(v.len())` Compiles

TL;DR: v.push(v.len()) is the canonical example of a two-phase borrow. The obvious implementation is a dataflow analysis that tracks, at every point, whether each mutable borrow is “reserved but not yet active”. rustc does no such analysis. It finds the activation point by looking at the MIR, and then answers “is this borrow active at this location?” with two dominator-tree queries — O(1), no fixpoint, no extra domain.

Two-phase borrows are Rust’s answer to the classic aliasing problem:

rust
let mut v = vec![1, 2, 3];
v.push(v.len());   // this compiles!

At the point where push is called, a &mut v must exist (it is the receiver). At the same time, v.len() needs a &v. Both are fine — but only if the &mut v is reserved rather than active while v.len() is evaluated. Two-phase borrows split the mutable borrow into two moments:

reservation: the &mut v is created, but reads of v are still allowed;
activation: the moment the reference is actually used as a mutable reference — in this case, the &mut v argument being passed to push.

The obvious implementation, and its cost

The textbook approach: add a dataflow analysis over a domain of “borrow activation states”, run it to fixpoint over the whole function, and answer “is borrow B active at point P?” from the computed state.

That is a full extra pass over the function body, with its own domain (a bitset over borrow indices), its own convergence cost, and its own memory. For a feature that only matters for a handful of call sites per function.

What rustc does instead

Step one: find the activation syntactically. When the borrow checker walks the MIR and encounters a two-phase borrow statement, it records the reservation and remembers the temporary it was assigned to:

rust
// compiler/rustc_borrowck/src/borrow_set.rs:441-473

let idx = if !kind.is_two_phase_borrow() {
    debug!("  -> {:?}", location);
    self.insert_borrow(location, borrow(TwoPhaseActivation::NotTwoPhase))
} else {
    // When we encounter a 2-phase borrow statement, it will always
    // be assigning into a temporary TEMP:
    //
    //    TEMP = &foo
    //
    // so extract `temp`.
    let Some(temp) = assigned_place.as_local() else {
        span_bug!(
            self.body.source_info(location).span,
            "expected 2-phase borrow to assign to a local, not `{:?}",
            assigned_place,
        );
    };

    // Consider the borrow not activated to start. When we find an activation, we'll update
    // this field.
    let idx = self.insert_borrow(location, borrow(TwoPhaseActivation::NotActivated));

    // Insert `temp` into the list of pending activations. From
    // now on, we'll be on the lookout for a use of it. Note that
    // we are guaranteed that this use will come after the
    // assignment.
    let prev = self.pending_activations.insert(temp, idx);
    assert_eq!(prev, None, "temporary associated with multiple two phase borrows");

    idx
};

Step two: the activation is the next use of that temporary:

rust
// compiler/rustc_borrowck/src/borrow_set.rs:524-569

fn visit_local(&mut self, temp: Local, context: PlaceContext, location: Location) {
    if !context.is_use() {
        return;
    }

    // We found a use of some temporary TMP
    // check whether we (earlier) saw a 2-phase borrow like
    //
    //     TMP = &mut place
    let Some(&borrow_index) = self.pending_activations.get(&temp) else {
        return;
    };
    let borrow_data = &mut self.borrows[borrow_index];

    // Watch out: the use of TMP in the borrow itself
    // doesn't count as an activation. =)
    if borrow_data.reserve_location == location
        && context == PlaceContext::MutatingUse(MutatingUseContext::Store)
    {
        return;
    }
    ...
    self.activation_map.entry(location).or_default().push(borrow_index);

    borrow_data.activation_location = TwoPhaseActivation::ActivatedAt(location);
}

No fixpoint, no worklist: a hash map from temporary to pending activation, and the first use of that temporary after the reservation is the activation. The comment “the use of TMP in the borrow itself doesn’t count as an activation” is the one subtlety — the store that creates the borrow is also a use of the temporary.

Step three: the dominator argument

Now the question the checker actually asks at each use site: “is this borrow active here?” — and the answer comes from the dominator tree:

rust
// compiler/rustc_borrowck/src/path_utils.rs:60-120

pub(super) fn is_active<'tcx>(
    dominators: &Dominators<BasicBlock>,
    borrow_data: &BorrowData<'tcx>,
    location: Location,
) -> bool {
    debug!("is_active(borrow_data={:?}, location={:?})", borrow_data, location);

    let activation_location = match borrow_data.activation_location {
        // If this is not a 2-phase borrow, it is always active.
        TwoPhaseActivation::NotTwoPhase => return true,
        // And if the unique 2-phase use is not an activation, then it is *never* active.
        TwoPhaseActivation::NotActivated => return false,
        // Otherwise, we derive info from the activation point `loc`:
        TwoPhaseActivation::ActivatedAt(loc) => loc,
    };

    // Otherwise, it is active for every location *except* in between
    // the reservation and the activation:
    //
    //       X
    //      /
    //     R      <--+ Except for this
    //    / \        | diamond
    //    \ /        |
    //     A  <------+
    //     |
    //     Z
    //
    // Note that we assume that:
    // - the reservation R dominates the activation A
    // - the activation A post-dominates the reservation R (ignoring unwinding edges).
    //
    // This means that there can't be an edge that leaves A and
    // comes back into that diamond unless it passes through R.
    //
    // Suboptimal: In some cases, this code walks the dominator
    // tree twice when it only has to be walked once. I am
    // lazy. -nmatsakis

    // If dominated by the activation A, then it is active. The
    // activation occurs upon entering the point A, so this is
    // also true if location == activation_location.
    if activation_location.dominates(location, dominators) {
        return true;
    }

    // The reservation starts *on exiting* the reservation block,
    // so check if the location is dominated by R.successor. If so,
    // this point falls in between the reservation and location.
    let reserve_location = borrow_data.reserve_location.successor_within_block();
    if reserve_location.dominates(location, dominators) {
        false
    } else {
        // Otherwise, this point is outside the diamond, so
        // consider the borrow active. This could happen for
        // example if the borrow remains active around a loop (in
        // which case it would be active also for the point R,
        // which would generate an error).
        true
    }
}

The diamond diagram is the whole idea. The borrow is inactive only in the region between the reservation and the activation — and that region is exactly characterized by two dominator facts:

the activation dominates the location → the borrow is active;
the reservation’s successor dominates the location → we are in the “between” window → the borrow is inactive;
otherwise → outside the diamond → active.

The soundness argument is in the comment: the reservation dominates the activation, and the activation post-dominates the reservation, so no edge can leave the diamond and come back without passing through the reservation.

And the borrow checker calls it like this:

rust
// compiler/rustc_borrowck/src/lib.rs:1324-1329

(Read(kind), BorrowKind::Mut { .. }) => {
    // Reading from mere reservations of mutable-borrows is OK.
    if !is_active(this.dominators(), borrow, location) {
        assert!(borrow.kind.is_two_phase_borrow());
        return ControlFlow::Continue(());
    }

The dominator tree is already computed — mir::basic_blocks::Cache caches it — so this is free.

The cost

Approach	Cost
Dataflow analysis over borrow activation states	One extra fixpoint pass over the body, a domain of `O(#borrows)` bits, per function
Dominator queries	Two `dominates()` calls per borrow use site, O(1) each with the cached tree

And there is a bonus: the dominator formulation gives a much better explanation when the borrow checker does complain. “This borrow is active here because you used v between the reservation and the activation” is a message a human can act on.

The admitted inefficiency in the comment — “this code walks the dominator tree twice when it only has to be walked once. I am lazy. -nmatsakis” — is still vastly cheaper than a dataflow pass.

Where it lives

compiler/rustc_borrowck/src/borrow_set.rs — finding the reservation and the activation.
compiler/rustc_borrowck/src/path_utils.rs — is_active and the dominator argument.
compiler/rustc_borrowck/src/lib.rs — the check itself.
tests/ui/borrowck/two-phase-baseline.rs — the canonical test, including v.push(v.len()).

Takeaway

This is a good example of a feature that looks like it needs a new analysis but does not. The question “is the borrow active here?” has a purely local answer if you frame it in terms of dominance instead of “which side of the activation are we on”. Framing it right turned an O(functions × borrows × points) analysis into two tree queries.