rustc_type_ir/solve/
inspect.rs

1//! Data structure used to inspect trait solver behavior.
2//!
3//! During trait solving we optionally build "proof trees", the root of
4//! which is a [GoalEvaluation]. These  trees are used by the compiler
5//! to inspect the behavior of the trait solver and to access its internal
6//! state, e.g. for diagnostics and when selecting impls during codegen.
7//!
8//! Because each nested goal in the solver gets [canonicalized] separately
9//! and we discard inference progress via "probes", we cannot mechanically
10//! use proof trees without somehow "lifting up" data local to the current
11//! `InferCtxt`. To use the data from evaluation we therefore canonicalize
12//! it and store it as a [CanonicalState].
13//!
14//! Proof trees are only shallow, we do not compute the proof tree for nested
15//! goals. Visiting proof trees instead recomputes nested goals in the parents
16//! inference context when necessary.
17//!
18//! [canonicalized]: https://rustc-dev-guide.rust-lang.org/solve/canonicalization.html
19
20use derive_where::derive_where;
21use rustc_type_ir_macros::{TypeFoldable_Generic, TypeVisitable_Generic};
22
23use crate::solve::{CandidateSource, Certainty, Goal, GoalSource, QueryResult};
24use crate::{Canonical, CanonicalVarValues, Interner};
25
26/// Some `data` together with information about how they relate to the input
27/// of the canonical query.
28///
29/// This is only ever used as [CanonicalState]. Any type information in proof
30/// trees used mechanically has to be canonicalized as we otherwise leak
31/// inference variables from a nested `InferCtxt`.
32#[derive_where(Clone, PartialEq, Hash, Debug; I: Interner, T)]
33#[derive_where(Copy; I: Interner, T: Copy)]
34#[derive(TypeVisitable_Generic, TypeFoldable_Generic)]
35pub struct State<I: Interner, T> {
36    pub var_values: CanonicalVarValues<I>,
37    pub data: T,
38}
39
40impl<I: Interner, T: Eq> Eq for State<I, T> {}
41
42pub type CanonicalState<I, T> = Canonical<I, State<I, T>>;
43
44/// When evaluating a goal we also store the original values
45/// for the `CanonicalVarValues` of the canonicalized goal.
46/// We use this to map any [CanonicalState] from the local `InferCtxt`
47/// of the solver query to the `InferCtxt` of the caller.
48#[derive_where(PartialEq, Eq, Hash; I: Interner)]
49pub struct GoalEvaluation<I: Interner> {
50    pub uncanonicalized_goal: Goal<I, I::Predicate>,
51    pub orig_values: Vec<I::GenericArg>,
52    pub final_revision: I::Probe,
53    pub result: QueryResult<I>,
54}
55
56/// A self-contained computation during trait solving. This either
57/// corresponds to a `EvalCtxt::probe(_X)` call or the root evaluation
58/// of a goal.
59#[derive_where(PartialEq, Eq, Hash, Debug; I: Interner)]
60pub struct Probe<I: Interner> {
61    /// What happened inside of this probe in chronological order.
62    pub steps: Vec<ProbeStep<I>>,
63    pub kind: ProbeKind<I>,
64    pub final_state: CanonicalState<I, ()>,
65}
66
67#[derive_where(PartialEq, Eq, Hash, Debug; I: Interner)]
68pub enum ProbeStep<I: Interner> {
69    /// We added a goal to the `EvalCtxt` which will get proven
70    /// the next time `EvalCtxt::try_evaluate_added_goals` is called.
71    AddGoal(GoalSource, CanonicalState<I, Goal<I, I::Predicate>>),
72    /// A call to `probe` while proving the current goal. This is
73    /// used whenever there are multiple candidates to prove the
74    /// current goal.
75    NestedProbe(Probe<I>),
76    /// A trait goal was satisfied by an impl candidate.
77    RecordImplArgs { impl_args: CanonicalState<I, I::GenericArgs> },
78    /// A call to `EvalCtxt::evaluate_added_goals_make_canonical_response` with
79    /// `Certainty` was made. This is the certainty passed in, so it's not unified
80    /// with the certainty of the `try_evaluate_added_goals` that is done within;
81    /// if it's `Certainty::Yes`, then we can trust that the candidate is "finished"
82    /// and we didn't force ambiguity for some reason.
83    MakeCanonicalResponse { shallow_certainty: Certainty },
84}
85
86/// What kind of probe we're in. In case the probe represents a candidate, or
87/// the final result of the current goal - via [ProbeKind::Root] - we also
88/// store the [QueryResult].
89#[derive_where(Clone, Copy, PartialEq, Eq, Hash, Debug; I: Interner)]
90#[derive(TypeVisitable_Generic, TypeFoldable_Generic)]
91pub enum ProbeKind<I: Interner> {
92    /// The root inference context while proving a goal.
93    Root { result: QueryResult<I> },
94    /// Probe entered when normalizing the self ty during candidate assembly
95    NormalizedSelfTyAssembly,
96    /// A candidate for proving a trait or alias-relate goal.
97    TraitCandidate { source: CandidateSource<I>, result: QueryResult<I> },
98    /// Used in the probe that wraps normalizing the non-self type for the unsize
99    /// trait, which is also structurally matched on.
100    UnsizeAssembly,
101    /// Used to do a probe to find out what projection type(s) match a given
102    /// alias bound or projection predicate. For trait upcasting, this is used
103    /// to prove that the source type upholds all of the target type's object
104    /// bounds. For object type bounds, this is used when eagerly replacing
105    /// supertrait aliases.
106    ProjectionCompatibility,
107    /// Looking for param-env candidates that satisfy the trait ref for a projection.
108    ShadowedEnvProbing,
109    /// Try to unify an opaque type with an existing key in the storage.
110    OpaqueTypeStorageLookup { result: QueryResult<I> },
111    /// Checking that a rigid alias is well-formed.
112    RigidAlias { result: QueryResult<I> },
113}
rustc_type_ir/solve/inspect.rs

rustc_type_ir/solve/
inspect.rs
