rustc's Trait Solver Doesn't Write Error Messages: It Writes Proof Trees

TL;DR: During trait solving, rustc never formats an error message. It records a proof tree — a structured trace of which candidate was tried and what it required — and only if the goal ultimately fails does it replay that trace (with the global cache disabled) to find the obligation that actually failed. The result is a fast solver and much better error messages.

Most compilers build error messages as they go. The solver tries a candidate, the candidate fails, and the failure handler formats a diagnostic right there. It works, but it is expensive: every candidate evaluation may construct spans, allocate strings, and build a Diag that will be thrown away 99.9% of the time.

rustc’s next-generation solver does the opposite.

The proof tree

rust
// compiler/rustc_next_trait_solver/src/solve/inspect/build.rs:17-46

/// We need to know whether to build a prove tree while evaluating. We
/// pass a `ProofTreeBuilder` with `state: Some(None)` into the search
/// graph which then causes the initial `EvalCtxt::compute_goal` to actually
/// build a proof tree which then gets written into the `state`.
///
/// Building the proof tree for a single evaluation step happens via the
/// [EvaluationStepBuilder] which is updated by the `EvalCtxt` when
/// appropriate.
pub(crate) struct ProofTreeBuilder<D, I = <D as SolverDelegate>::Interner>
where
    D: SolverDelegate<Interner = I>,
    I: Interner,
{
    state: Option<Box<Option<inspect::Probe<I>>>>,
    _infcx: PhantomData<D>,
}

impl<D: SolverDelegate<Interner = I>, I: Interner> ProofTreeBuilder<D> {
    pub(crate) fn new() -> ProofTreeBuilder<D> {
        ProofTreeBuilder { state: Some(Box::new(None)), _infcx: PhantomData }
    }

    pub(crate) fn new_noop() -> ProofTreeBuilder<D> {
        ProofTreeBuilder { state: None, _infcx: PhantomData }
    }

    pub(crate) fn is_noop(&self) -> bool {
        self.state.is_none()
    }
}

Note the two constructors. new_noop() builds nothing. The normal solving path uses the noop builder — the proof tree is not even allocated. Only when the diagnostic machinery asks for one does the real builder get installed.

The cache is disabled while recording

This is the subtle part. If you replay a proof tree from the global cache, you get a different trace than the one that actually ran, because the cached path skipped work. So the search graph disables the cache when a proof tree is being built:

rust
// compiler/rustc_type_ir/src/search_graph/mod.rs:834-852

// Lookup the global cache unless we're building proof trees or are currently
// fuzzing.
let validate_cache = if !D::inspect_is_noop(inspect) {
    None
} else if let Some(scope) = D::enter_validation_scope(cx, input) {
    ...
} else if let Some(result) =
    self.lookup_global_cache(cx, input, step_kind_from_parent, available_depth)
{
    return result;
} else {
    None
};

Read that first branch: if !D::inspect_is_noop(inspect) { None } — when we are building a proof tree, the global cache lookup is skipped entirely. The recorded trace is therefore the true, uncached, from-scratch evaluation.

That makes diagnostics more expensive than solving (the goal is re-run from scratch), but it makes them correct, and it happens only on the error path.

Replaying the tree

When an obligation fails, the diagnostic machinery re-runs the goal with a real builder and walks the resulting tree to find the deepest interesting obligation:

rust
// compiler/rustc_trait_selection/src/solve/inspect/analyse.rs:178-200

pub fn instantiate_proof_tree_for_nested_goal(
    &self,
    source: GoalSource,
    goal: Goal<'tcx, ty::Predicate<'tcx>>,
    span: Span,
) -> InspectGoal<'a, 'tcx> {
    let infcx = self.goal.infcx;
    match goal.predicate.kind().no_bound_vars() {
        Some(ty::PredicateKind::NormalizesTo(ty::NormalizesTo { .. })) => {
            // We don't handle `NormalizesTo` as a nested goal
            unreachable!()
        }
        _ => {
            // We're using a probe here as evaluating a goal could constrain
            // inference variables by choosing one candidate. If we then recurse
            // into another candidate who ends up with different inference
            // constraints, we get an ICE if we already applied the constraints
            // from the chosen candidate.
            let proof_tree =
                infcx.probe(|_| infcx.evaluate_root_goal_for_proof_tree(goal, span).1);
            InspectGoal::new(infcx, self.goal.depth + 1, proof_tree, source)
        }
    }
}

and the error derivation walks it looking for the best leaf:

rust
// compiler/rustc_trait_selection/src/solve/fulfill/derive_errors.rs:150-178

fn find_best_leaf_obligation<'tcx>(
    infcx: &'tcx InferCtxt<'tcx>,
    obligation: &PredicateObligation<'tcx>,
    consider_ambiguities: bool,
) -> PredicateObligation<'tcx> {
    let obligation = infcx.deeply_resolve_ignoring_regions(obligation.clone());
    // FIXME: we use a probe here as the `BestObligation` visitor does not
    // check whether it uses candidates which get shadowed by where-bounds.
    //
    // We should probably fix the visitor to not do so instead, as this also
    // means the leaf obligation may be incorrect.
    let obligation = infcx
        .fudge_inference_if_ok(|| {
            infcx
                .visit_proof_tree(
                    obligation.as_goal(),
                    &mut BestObligation { obligation: obligation.clone(), consider_ambiguities },
                )
                .break_value()
                .ok_or(())
                // walk around the fact that the cause in `Obligation` is ignored by folders so that
                // we can properly fudge the infer vars in cause code.
                .map(|o| (o.cause.clone(), o))
        })
        .map(|(cause, o)| PredicateObligation { cause, ..o })
        .unwrap_or(obligation);
    deeply_normalize_for_diagnostics(infcx, obligation.param_env, obligation)
}

visit_proof_tree walks the recorded Probe tree — steps like AddGoal, NestedProbe, MakeCanonicalResponse, RecordImplArgs — and the visitor picks the “best” leaf obligation.

The `probe` wrapper is load-bearing

Notice the infcx.probe(...) in the snippet above. Replaying a candidate can constrain inference variables — choosing a candidate applies its where-clauses to the inference context. If the diagnostic machinery then replays a different candidate with different constraints, it would hit an ICE (“we already applied the constraints from the chosen candidate”).

The fix is to run the replay inside a probe: a snapshot of the inference context that is rolled back afterwards. This is the same snapshot/undo machinery the solver itself uses to try candidates and back out.

The FIXME in the source is an honest admission that this is a workaround: the visitor should not be using shadowed candidates in the first place.

What the solver does build eagerly

Not everything is deferred. The solver does maintain a canonical response for each candidate — the answer, canonicalized so it can be cached and compared:

rust

// compiler/rustc_next_trait_solver/src/solve/mod.rs:321-405

and the merging logic is where the performance lives:

rust
let always_applicable = candidates.iter().enumerate().find(|(_, candidate)| {
    candidate.result.value.certainty == Certainty::Yes
        && has_no_inference_or_external_constraints(candidate.result)
});

if let Some((i, candidate)) = always_applicable {
    return Some((candidate.result, MergeCandidateInfo::AlwaysApplicable(i)));
}

If one candidate applies with certainty and imposes no constraints, it subsumes the others — and the solver can then ignore the other candidates' head usages, which prunes fixpoint iterations.

If the candidates are not equal but are equal modulo region constraints, they merge. Otherwise the solver flounders to ambiguity, keeping the strongest “maybe cause”:

rust
fn bail_with_ambiguity(&mut self, candidates: &[Candidate<I>]) -> CanonicalResponse<I> {
    debug_assert!(candidates.len() > 1);
    let maybe = candidates.iter().fold(MaybeInfo::AMBIGUOUS, |maybe, candidate| {
        // We pull down the certainty of `Certainty::Yes` to ambiguity when combining
        // these responses, b/c we're combining more than one response and this we
        // don't know which one applies.
        match candidate.result.value.certainty {
            Certainty::Yes => maybe,
            Certainty::Maybe(cand_maybe) => maybe.or(cand_maybe),
        }
    });
    self.make_ambiguous_response_no_constraints(maybe)
}

Note the comment: combining responses lowers certainty to ambiguity because we do not know which candidate applies. But the “maybe cause” is preserved with or, so an overflow is not silently downgraded to plain ambiguity.

Where it lives

compiler/rustc_next_trait_solver/src/solve/inspect/build.rs — the ProofTreeBuilder.
compiler/rustc_type_ir/src/search_graph/mod.rs — cache disabling during proof-tree construction.
compiler/rustc_trait_selection/src/solve/inspect/analyse.rs — replaying the tree.
compiler/rustc_trait_selection/src/solve/fulfill/derive_errors.rs — finding the best leaf obligation.
compiler/rustc_next_trait_solver/src/solve/mod.rs — candidate merging.

Takeaway

Deferred diagnostics are a classic performance technique: do not build the thing you might throw away. What is unusual here is how rustc defers them. It does not merely postpone the message; it records enough structured information to reconstruct the evaluation later, and it deliberately disables its cache during that reconstruction so the replay is faithful. The side effect is better errors: the diagnostic code can ask questions of the trace (“which nested goal failed?”) that eager diagnostics could never answer.