Divide by Four: How rustc's Trait Solver Makes Itself Stop

TL;DR: The new trait solver has a recursion budget. Normally each nested goal costs one unit. But once an overflow has been observed anywhere below, the budget is divided by four instead of decremented. The effective depth after k overflows is depth / 4^k, so the total work is linear rather than quadratic — and the solver gives up almost instantly after the first sign of pathology.

Trait solving is the part of a Rust compiler most likely to run away. The problems are mutually recursive trait bounds, deeply nested associated types, and goals that expand into thousands of sub-goals. The old solver handled this with a recursion limit and a “cycle” error. The new solver handles it with a budget that shrinks geometrically once things go bad.

The budget

// compiler/rustc_type_ir/src/search_graph/mod.rs:287-326

impl AvailableDepth {
    /// Returns the remaining depth allowed for nested goals.
    ///
    /// This is generally simply one less than the current depth.
    /// However, if we encountered overflow, we significantly reduce
    /// the remaining depth of all nested goals to prevent hangs
    /// in case there is exponential blowup.
    fn allowed_depth_for_nested<D: Delegate>(
        root_depth: AvailableDepth,
        stack: &Stack<D::Cx>,
        lower_available_depth: LowerAvailableDepth,
    ) -> Option<AvailableDepth> {
        if let Some(last) = stack.last() {
            match lower_available_depth {
                LowerAvailableDepth::Yes => {}
                LowerAvailableDepth::No => {
                    return Some(last.available_depth);
                }
            }

            if last.available_depth.0 == 0 {
                return None;
            }

            Some(if last.encountered_overflow {
                AvailableDepth(last.available_depth.0 / D::DIVIDE_AVAILABLE_DEPTH_ON_OVERFLOW)
            } else {
                AvailableDepth(last.available_depth.0 - 1)
            })
        } else {
            Some(root_depth)
        }
    }

and the divisor:

// compiler/rustc_next_trait_solver/src/solve/search_graph.rs:43
const DIVIDE_AVAILABLE_DEPTH_ON_OVERFLOW: usize = 4;

Read the difference between the two branches:

• normal case: available_depth - 1;
• after an overflow: available_depth / 4.

That is the entire trick. The budget is not a counter, it is an amount of remaining work, and once the solver knows it is in a pathological region it takes away three quarters of the remaining work rather than one unit.

Why dividing is the right shape

The classic failure mode of a recursion-limited solver is quadratic behaviour: each level of the recursion can fan out into a constant number of sub-goals, so the total number of goals is proportional to depth^2 in the worst case. With a budget of 128, that is thousands of goals — each of which may be expensive.

Dividing changes the shape. After the first overflow, the budget is depth / 4; after the second (one level deeper), depth / 16; then depth / 64. The total work becomes:

depth + depth/4 + depth/16 + ... = depth * 4/3

— linear in the budget rather than quadratic. The solver does not “run for 128 levels”; it runs for 128, then 32, then 8, then 2, then 0. Total nesting explored: about 160 levels, but the branching factor collapses along the way.

The practical effect is that the new solver gives up fast on pathological input, which is what you want from a compiler: a clear “trait bound is not satisfied” (or an explicit overflow error) in 10 ms beats a 40-second hang.

The overflow handler poisons the parent

// compiler/rustc_type_ir/src/search_graph/mod.rs:936-957

fn handle_overflow(&self, cx: X, input: X::Input) -> X::Result {
    if let Some(last) = self.stack.last_mut() {
        last.encountered_overflow = true;
        // If computing a goal `B` depends on another goal `A` and
        // `A` has a nested goal which overflows, then computing `B`
        // at the same depth, but with `A` already on the stack,
        // would encounter a solver cycle instead, potentially
        // changing the result.
        //
        // We must therefore not use the global cache entry for `B` in that case.
        // See tests/ui/traits/next-solver/cycles/hidden-by-overflow.rs
        last.nested_goals.insert(last.input, PathsToNested::EMPTY);
    }

    debug!("encountered stack overflow");
    D::stack_overflow_result(cx, input)
}

Two things happen when an overflow is detected. The frame is marked (encountered_overflow = true), which is what makes the next nested goal divide rather than decrement. And the parent’s nested-goal set is invalidated, so the global cache entry for the parent is not reused — because computing the parent at a shallower depth, with the overflowing goal already on the stack, could produce a cycle instead of an overflow, and those two have different answers.

That second point is subtle and important: overflow and cycle are not the same thing, and the solver has to make sure a cached “yes” from one context is not reused in the other.

The LowerAvailableDepth::No escape hatch

Not all nested goals should consume depth. NormalizesTo goals behave like function calls rather than independent nested evaluations:

// compiler/rustc_type_ir/src/search_graph/mod.rs:263-275

When LowerAvailableDepth::No is in effect, the child’s budget is the parent’s budget, unchanged. So a chain of normalizations does not burn the budget, while a chain of nested obligations does.

The cache has to know about all this

For the global cache to stay sound, each entry records the goals it transitively touched — but only once something interesting has happened:

// compiler/rustc_type_ir/src/search_graph/mod.rs:498-514

/// The nested goals of each stack entry and the path from the
/// stack entry to that nested goal.
///
/// They are used when checking whether reevaluating a global cache
/// would encounter a cycle or use a provisional cache entry given
/// the current search graph state. We need to disable the global cache
/// in this case as it could otherwise result in behavioral differences.
/// Cycles can impact behavior. The cycle ABA may have different final
/// results from a the cycle BAB depending on the cycle root.
///
/// We only start tracking nested goals once we've either encountered
/// overflow or a solver cycle. This is a performance optimization to
/// avoid tracking nested goals on the happy path.
#[derive_where(Debug, Default, Clone; X: Cx)]
struct NestedGoals<X: Cx> {
    nested_goals: HashMap<X::Input, PathsToNested>,
}

and the applicability check rejects entries whose nested goals are on the stack:

// compiler/rustc_type_ir/src/search_graph/mod.rs:1190-1206

fn candidate_is_applicable(
    &self,
    step_kind_from_parent: PathKind,
    nested_goals: &NestedGoals<X>,
) -> bool {
    // If the global cache entry didn't depend on any nested goals, it always
    // applies.
    if nested_goals.is_empty() {
        return true;
    }

    // If a nested goal of the global cache entry is on the stack, we would
    // definitely encounter a cycle.
    if self.stack.iter().any(|e| nested_goals.contains(e.input)) {
        debug!("cache entry not applicable due to stack");
        return false;
    }

The lazy tracking is a nice touch: on the happy path (no cycles, no overflow) the map is empty and the check is a single is_empty() test. Only in the pathological case does the dependency graph get materialized.

Where it lives

• compiler/rustc_type_ir/src/search_graph/mod.rs — AvailableDepth, handle_overflow, NestedGoals, candidate_is_applicable.
• compiler/rustc_next_trait_solver/src/solve/search_graph.rs — DIVIDE_AVAILABLE_DEPTH_ON_OVERFLOW = 4.

Takeaway

A recursion limit answers “how deep may I go?”. A budget answers “how much work may I do?”. The second question is the useful one, and when the answer is “a lot”, the right response to a hint of pathology is to remove most of the remaining budget, not a little of it. Dividing by four is a one-line change with a dramatic effect on worst-case compile times.