The Borrow Checker Blames the Most Interesting Constraint: BFS, Then a Ranking

TL;DR: Lifetime errors are hard to explain because there are usually many constraints that could be blamed. rustc picks one in two steps: a breadth-first search finds the shortest path through the constraint graph (fewest constraints), and then a hand-tuned “interest” score picks the most user-facing constraint on that path — scanning from the source end or the target end depending on which side is being blamed.

A borrow checker error looks like this:

error[E0597]: `x` does not live long enough
  --> src/main.rs:5:20
   |
5  |     drop(x);
   |           ^ borrowed value does not live long enough

The “borrowed value does not live long enough” part is easy. The hard part is picking which constraint in the chain of lifetime requirements to blame. A function with six lifetime parameters can have dozens of outlives constraints between them, and most of them are compiler-generated noise.

Step one: shortest path

// compiler/rustc_borrowck/src/region_infer/region_context.rs:453-475

let mut context = IndexVec::from_elem(Trace::NotVisited, &self.definitions);
context[from_region] = Trace::StartRegion;

let fr_static = self.universal_regions().fr_static;

// Use a deque so that we do a breadth-first search. We will
// stop at the first match, which ought to be the shortest
// path (fewest constraints).
let mut deque = VecDeque::new();
deque.push_back(from_region);

while let Some(r) = deque.pop_front() {

The choice of VecDeque + pop_front over Vec + pop is deliberate and commented: BFS, not DFS. A DFS would find a path, and the path it finds would be arbitrary — often long, often winding through irrelevant constraints. BFS finds the path with the fewest constraints, which is already a decent proxy for “the constraint the user most likely intended”.

Step two: the interest ranking

But shortest is not the same as most useful. rustc goes further and scores each constraint by how interesting it is for a human:

// compiler/rustc_borrowck/src/region_infer/region_context.rs:684-768

// To pick a constraint to blame, we organize constraints by how interesting we expect them
// to be in diagnostics, then pick the most interesting one closest to either the source or
// the target on our constraint path.
let constraint_interest = |constraint: &OutlivesConstraint<'tcx>| {
    // Try to avoid blaming constraints from desugarings, since they may not clearly match
    // match what users have written. As an exception, allow blaming returns generated by
    // `?` desugaring, since the correspondence is fairly clear.
    let category = if let Some(kind) = constraint.span.desugaring_kind()
        && (kind != DesugaringKind::QuestionMark
            || !matches!(constraint.category, ConstraintCategory::Return(_)))
    {
        ConstraintCategory::Boring
    } else {
        constraint.category
    };

    let interest = match category {
        // Returns usually provide a type to blame and have specially written diagnostics,
        // so prioritize them.
        ConstraintCategory::Return(_) => 0,

The scores are hand-assigned integers. Zero is “a return expression”, which gets priority because it has a type to show and a dedicated diagnostic message. Everything else is worse, in increasing order, ending with solver-internal constraints.

The final selection picks the best-scoring constraint, scanning the path from one end or the other:

// compiler/rustc_borrowck/src/region_infer/region_context.rs:1510-1513 (region_context.rs:750-768)

let best_choice = if blame_source {
    path.iter().enumerate().rev().min_by_key(|(_, c)| constraint_interest(c)).unwrap().0
} else {
    path.iter().enumerate().min_by_key(|(_, c)| constraint_interest(c)).unwrap().0
};

min_by_key finds the lowest interest number, i.e. the most interesting constraint. The only difference between the two branches is the direction of the scan:

• blame_source → scan the path in reverse, preferring constraints near the source;
• otherwise (blaming a placeholder or a target) → scan forward, preferring constraints near the target.

That asymmetry matters. When you are blaming a sub-type bound, the interesting constraint is near the source; when you are blaming a higher-ranked placeholder, the interesting constraint is near the target.

The cold path is deferred

One more detail worth stealing: the constraints themselves are not built during the search. The search walks a Trace graph, and the actual OutlivesConstraint values are only materialized at the end, on the error path:

// compiler/rustc_borrowck/src/region_infer/region_context.rs:477-509

let mut result = vec![];
let mut p = r;
// This loop is cold and runs at the end, which is why we delay
// `OutlivesConstraint` construction until now.
loop {
    match context[p] {
        Trace::FromGraph(c) => {
            p = c.sup;
            result.push(*c);
        }
        ...

The comment is the whole justification: constraint construction involves spans, categories and variance info, and building it for every successful borrow check would be pure waste. The search therefore carries a lightweight Trace enum — NotVisited, StartRegion, FromGraph, FromStatic — and only converts it into real constraints when it is about to complain.

Why not just blame the constraint that failed?

Because there usually isn’t one. The constraint that “failed” is often a derived fact — the region grew too large because of a chain of other constraints. Blaming the derived failure gives the user a message about something they never wrote.

Instead rustc picks the constraint on the path that is closest to the user and most likely to be the real intent. If you have ever seen a lifetime error that pointed at a ? operator, at a return statement, or at an explicit type annotation rather than at the compiler’s internal machinery, this is why.

Where it lives

• compiler/rustc_borrowck/src/region_infer/region_context.rs — the BFS (best_blame_constraint), the constraint_interest closure, and the deferred construction of OutlivesConstraint.
• compiler/rustc_borrowck/src/region_infer/region_context.rs — ConstraintCategory, the enum the ranking is built on.

Takeaway

Error messages are a performance problem too: they run on the cold path, but they run on the path that users actually see, and a confusing error costs a user far more time than a slow compile. Spending a BFS plus a hand-tuned ranking to pick the right constraint is a good trade, and the “build the expensive thing only on the error path” pattern makes it cheap enough to always do.