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, 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 kind: GoalEvaluationKind<I>,
53    pub result: QueryResult<I>,
54}
55
56impl<I: Interner> Eq for GoalEvaluation<I> {}
57
58#[derive_where(PartialEq, Hash, Debug; I: Interner)]
59pub enum GoalEvaluationKind<I: Interner> {
60    Overflow,
61    Evaluation {
62        /// This is always `ProbeKind::Root`.
63        final_revision: Probe<I>,
64    },
65}
66
67impl<I: Interner> Eq for GoalEvaluationKind<I> {}
68
69/// A self-contained computation during trait solving. This either
70/// corresponds to a `EvalCtxt::probe(_X)` call or the root evaluation
71/// of a goal.
72#[derive_where(PartialEq, Hash, Debug; I: Interner)]
73pub struct Probe<I: Interner> {
74    /// What happened inside of this probe in chronological order.
75    pub steps: Vec<ProbeStep<I>>,
76    pub kind: ProbeKind<I>,
77    pub final_state: CanonicalState<I, ()>,
78}
79
80impl<I: Interner> Eq for Probe<I> {}
81
82#[derive_where(PartialEq, Hash, Debug; I: Interner)]
83pub enum ProbeStep<I: Interner> {
84    /// We added a goal to the `EvalCtxt` which will get proven
85    /// the next time `EvalCtxt::try_evaluate_added_goals` is called.
86    AddGoal(GoalSource, CanonicalState<I, Goal<I, I::Predicate>>),
87    /// A call to `probe` while proving the current goal. This is
88    /// used whenever there are multiple candidates to prove the
89    /// current goal.
90    NestedProbe(Probe<I>),
91    /// A trait goal was satisfied by an impl candidate.
92    RecordImplArgs { impl_args: CanonicalState<I, I::GenericArgs> },
93    /// A call to `EvalCtxt::evaluate_added_goals_make_canonical_response` with
94    /// `Certainty` was made. This is the certainty passed in, so it's not unified
95    /// with the certainty of the `try_evaluate_added_goals` that is done within;
96    /// if it's `Certainty::Yes`, then we can trust that the candidate is "finished"
97    /// and we didn't force ambiguity for some reason.
98    MakeCanonicalResponse { shallow_certainty: Certainty },
99}
100
101impl<I: Interner> Eq for ProbeStep<I> {}
102
103/// What kind of probe we're in. In case the probe represents a candidate, or
104/// the final result of the current goal - via [ProbeKind::Root] - we also
105/// store the [QueryResult].
106#[derive_where(Clone, Copy, PartialEq, Hash, Debug; I: Interner)]
107#[derive(TypeVisitable_Generic, TypeFoldable_Generic)]
108pub enum ProbeKind<I: Interner> {
109    /// The root inference context while proving a goal.
110    Root { result: QueryResult<I> },
111    /// Probe entered when normalizing the self ty during candidate assembly
112    NormalizedSelfTyAssembly,
113    /// A candidate for proving a trait or alias-relate goal.
114    TraitCandidate { source: CandidateSource<I>, result: QueryResult<I> },
115    /// Used in the probe that wraps normalizing the non-self type for the unsize
116    /// trait, which is also structurally matched on.
117    UnsizeAssembly,
118    /// Used to do a probe to find out what projection type(s) match a given
119    /// alias bound or projection predicate. For trait upcasting, this is used
120    /// to prove that the source type upholds all of the target type's object
121    /// bounds. For object type bounds, this is used when eagerly replacing
122    /// supertrait aliases.
123    ProjectionCompatibility,
124    /// Looking for param-env candidates that satisfy the trait ref for a projection.
125    ShadowedEnvProbing,
126    /// Try to unify an opaque type with an existing key in the storage.
127    OpaqueTypeStorageLookup { result: QueryResult<I> },
128    /// Checking that a rigid alias is well-formed.
129    RigidAlias { result: QueryResult<I> },
130}
131
132impl<I: Interner> Eq for ProbeKind<I> {}
rustc_type_ir/solve/inspect.rs

rustc_type_ir/solve/
inspect.rs
