One Pass, No Fixpoint: How rustc Solves Borrow Regions by Condensing Them Into SCCs

TL;DR: Region constraints ('a: 'b) form a graph that is usually cyclic. The borrow checker does not iterate to a fixpoint over that graph. It condenses the graph into strongly connected components — where every member is equal by construction — and then walks the condensation in dependency order, unioning values once per edge. One pass, no worklist, no convergence argument.

The old, pre-NLL borrow checker computed region constraints by iterating: it had a set of region variables, a set of constraints, and it looped until nothing changed. Every loop was a full re-scan of every constraint, and the loop count was unbounded in principle. NLL replaced that with a region inference pass that is structurally different: it computes, for each region, the set of program points where it must be live.

The algorithm

// compiler/rustc_borrowck/src/region_infer/region_context.rs:858-886

impl<'tcx> UnsolvedRegionInferenceContext<'tcx> {
    /// Propagate the region constraints: this will grow the values
    /// for each region variable until all the constraints are
    /// satisfied. Note that some values may grow **too** large to
    /// be feasible, but we check this later.
    #[instrument(skip(self), level = "debug")]
    fn propagate_constraints(&mut self) {
        ...
        // To propagate constraints, we walk the DAG induced by the
        // SCC. For each SCC `A`, we visit its successors and compute
        // their values, then we union all those values to get our
        // own. This one-shot approach works because iteration is in
        // dependency order. I.e. a chain A: B: C will visit C, B, A.
        for scc_a in self.constraint_sccs.all_sccs() {
            // Walk each SCC `B` such that `A: B`...
            for &scc_b in self.inner.constraint_sccs.successors(scc_a) {
                debug!(?scc_b);
                self.inner.scc_values.add_region(scc_a, scc_b);
            }
        }
    }
}

That comment is the whole algorithm. Two properties make it work:

1. Within an SCC, all regions are equal. If 'a: 'b and 'b: 'a, then 'a and 'b must have the same value. So one value per SCC is enough, and it is exactly right.
2. The condensation is a DAG, and rustc walks it in dependency order. The SCC data structure guarantees this:

// compiler/rustc_data_structures/src/graph/scc/mod.rs:129-137

/// Returns an iterator over the SCCs in the graph.
///
/// The SCCs will be iterated in **dependency order** (or **post order**),
/// meaning that if `S1 -> S2`, we will visit `S2` first and `S1` after.
/// This is convenient when the edges represent dependencies: when you visit
/// `S1`, the value for `S2` will already have been computed.
pub fn all_sccs(&self) -> impl Iterator<Item = S> + 'static {
    (0..self.scc_data.len()).map(S::new)
}

Tarjan’s algorithm naturally emits SCCs in reverse topological order, which is exactly dependency order for this graph. So the walk is: for each SCC, all successors are already final; union them in; move on.

What “union” costs

The value of a region is not a boolean, it is a set of program points. And the union of two such sets is not free:

// compiler/rustc_borrowck/src/region_infer/values.rs:298-304

/// Adds all elements in `r_from` to `r_to` (because e.g., `r_to:
/// `r_from`).
pub(crate) fn add_region(&mut self, r_to: N, r_from: N) -> bool {
    self.points.union_rows(r_from, r_to)
        | self.free_regions.union_rows(r_from, r_to)
        | self.placeholders.union_rows(r_from, r_to)
}

Three separate sparse matrices — program points, free regions, placeholders — unioned independently. (The dimension split is the subject of its own article: end(X) doesn’t live in the CFG.)

The points dimension is an interval matrix, not a bitmatrix, because region liveness is contiguous:

// compiler/rustc_index/src/interval.rs:345-358

/// This data structure optimizes for cases where the stored bits in each row
/// are expected to be highly contiguous (long ranges of 1s or 0s), in contrast
/// to BitMatrix and SparseBitMatrix which are optimized for
/// "random"/non-contiguous bits and cheap(er) point queries at the expense of
/// memory usage.
#[derive(Clone)]
pub struct SparseIntervalMatrix<R, C>
where
    R: Idx,
    C: Idx,
{
    rows: IndexVec<R, IntervalSet<C>>,
    column_size: usize,
}

And the union itself is careful about operand order:

// compiler/rustc_index/src/interval.rs:313-330

pub fn union(&mut self, other: &IntervalSet<I>) -> bool
where
    I: Step,
{
    assert_eq!(self.domain, other.domain);
    if self.map.len() < other.map.len() {
        let backup = self.clone();
        self.map.clone_from(&other.map);
        return self.union(&backup);
    }
    ...

If the left side is smaller, it swaps the operands and recurses, so the loop always iterates over the larger set’s intervals while inserting into the smaller one. That is the standard “merge into the smaller container” trick, and it matters when one region has two intervals and the other has two hundred.

The fixpoint that isn’t

Compare with the old design. The classic formulation is a worklist algorithm: put every region in the worklist, pop one, union its successors’ values into it, and if it grew, re-enqueue its predecessors. That is O(R·E) set unions in the worst case, and — worse — it re-does work that the SCC structure makes unnecessary.

The condensation changes the shape of the problem:

• before: R regions, E constraints, up to R rounds;
• after: S SCCs (S ≤ R), E unions on SCC values, one round.

For the common case where most regions are not in cycles, S ≈ R and the constant factor is what you save. For the pathological case — a big cycle of mutually borrowing regions, which happens with self-referential structs and closures — the old algorithm would spin; the new one computes the answer once.

The SCC computation is not free either

There is one subtlety: the SCC computation happens before the propagation, and the propagation can add constraints. If a new constraint merges two SCCs, the SCCs have to be recomputed. The borrow checker avoids this by folding the higher-ranked (“placeholder”) analysis into the SCC computation itself, as an annotation:

// compiler/rustc_borrowck/src/handle_placeholders.rs:154-169

impl scc::Annotation for RegionTracker {
    fn update_scc(&mut self, other: &Self) {
        trace!("{:?} << {:?}", self.representative, other.representative);
        self.representative = self.representative.min(other.representative);
        self.update_reachable(other);
    }

    fn update_reachable(&mut self, other: &Self) {
        self.max_nameable_universe = self.max_nameable_universe.min(other.max_nameable_universe);
        ...
    }
}

The scc::Annotation trait is a commutative-merge interface that Tarjan’s DFS calls automatically as it pops nodes off its stack. So the borrow checker gets, in the same O(V+E) traversal, the representative region for each SCC, the largest nameable universe reachable from it, and the set of reachable placeholders. All of that used to be a separate fixpoint.

And when a genuinely unnameable placeholder turns up, the constraint set is rewritten and the SCCs are recomputed — once:

// compiler/rustc_borrowck/src/handle_placeholders.rs:283-302

let added_constraints = rewrite_placeholder_outlives(
    &constraint_sccs,
    &scc_annotations,
    fr_static,
    &mut outlives_constraints,
);

let (constraint_sccs, scc_annotations) = if added_constraints {
    let mut annotations = SccAnnotations::init(&definitions);

    // We changed the constraint set and so must recompute SCCs.
    // Optimisation opportunity: if we can add them incrementally (and that's
    // possible because edges to 'static always only merge SCCs into 'static),
    // we would potentially save a lot of work here.
    (compute_sccs(&outlives_constraints, &mut annotations), annotations.scc_to_annotation)
} else {
    // If we didn't add any back-edges; no more work needs doing
    debug!("No constraints rewritten!");
    (constraint_sccs, scc_annotations.scc_to_annotation)
};

Note the “Optimisation opportunity” comment: the authors know this is a second pass and have written down why it is rare.

Where it lives

• compiler/rustc_borrowck/src/region_infer/region_context.rs — propagate_constraints.
• compiler/rustc_data_structures/src/graph/scc/mod.rs — the dependency-order SCC iterator.
• compiler/rustc_borrowck/src/region_infer/values.rs — the region value representation and add_region.
• compiler/rustc_index/src/interval.rs — the interval matrix.
• compiler/rustc_borrowck/src/handle_placeholders.rs — the SCC annotation trick.

The takeaway is a nice one: a fixpoint over a graph is often a fixpoint over a condensation of that graph, and if you can prove the members of each strongly connected component are equal, the condensation is a DAG and the fixpoint is a single topological sweep.