rustc_type_ir/solve/
inspect.rs

Help
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 std::fmt::Debug;
21use std::hash::Hash;
22
23use derive_where::derive_where;
24use rustc_type_ir_macros::{TypeFoldable_Generic, TypeVisitable_Generic};
25
26use crate::solve::{CandidateSource, CanonicalInput, Certainty, Goal, GoalSource, QueryResult};
27use crate::{Canonical, CanonicalVarValues, Interner};
28
29/// Some `data` together with information about how they relate to the input
30/// of the canonical query.
31///
32/// This is only ever used as [CanonicalState]. Any type information in proof
33/// trees used mechanically has to be canonicalized as we otherwise leak
34/// inference variables from a nested `InferCtxt`.
35#[derive_where(Clone; I: Interner, T: Clone)]
36#[derive_where(Copy; I: Interner, T: Copy)]
37#[derive_where(PartialEq; I: Interner, T: PartialEq)]
38#[derive_where(Eq; I: Interner, T: Eq)]
39#[derive_where(Hash; I: Interner, T: Hash)]
40#[derive_where(Debug; I: Interner, T: Debug)]
41#[derive(TypeVisitable_Generic, TypeFoldable_Generic)]
42pub struct State<I: Interner, T> {
43    pub var_values: CanonicalVarValues<I>,
44    pub data: T,
45}
46
47pub type CanonicalState<I, T> = Canonical<I, State<I, T>>;
48
49/// When evaluating a goal we also store the original values
50/// for the `CanonicalVarValues` of the canonicalized goal.
51/// We use this to map any [CanonicalState] from the local `InferCtxt`
52/// of the solver query to the `InferCtxt` of the caller.
53#[derive_where(PartialEq, Eq, Hash; I: Interner)]
54pub struct GoalEvaluation<I: Interner> {
55    pub uncanonicalized_goal: Goal<I, I::Predicate>,
56    pub orig_values: Vec<I::GenericArg>,
57    pub evaluation: CanonicalGoalEvaluation<I>,
58}
59
60#[derive_where(PartialEq, Eq, Hash, Debug; I: Interner)]
61pub struct CanonicalGoalEvaluation<I: Interner> {
62    pub goal: CanonicalInput<I>,
63    pub kind: CanonicalGoalEvaluationKind<I>,
64    pub result: QueryResult<I>,
65}
66
67#[derive_where(PartialEq, Eq, Hash, Debug; I: Interner)]
68pub enum CanonicalGoalEvaluationKind<I: Interner> {
69    Overflow,
70    Evaluation {
71        /// This is always `ProbeKind::Root`.
72        final_revision: Probe<I>,
73    },
74}
75
76/// A self-contained computation during trait solving. This either
77/// corresponds to a `EvalCtxt::probe(_X)` call or the root evaluation
78/// of a goal.
79#[derive_where(PartialEq, Eq, Hash, Debug; I: Interner)]
80pub struct Probe<I: Interner> {
81    /// What happened inside of this probe in chronological order.
82    pub steps: Vec<ProbeStep<I>>,
83    pub kind: ProbeKind<I>,
84    pub final_state: CanonicalState<I, ()>,
85}
86
87#[derive_where(PartialEq, Eq, Hash, Debug; I: Interner)]
88pub enum ProbeStep<I: Interner> {
89    /// We added a goal to the `EvalCtxt` which will get proven
90    /// the next time `EvalCtxt::try_evaluate_added_goals` is called.
91    AddGoal(GoalSource, CanonicalState<I, Goal<I, I::Predicate>>),
92    /// A call to `probe` while proving the current goal. This is
93    /// used whenever there are multiple candidates to prove the
94    /// current goal.
95    NestedProbe(Probe<I>),
96    /// A trait goal was satisfied by an impl candidate.
97    RecordImplArgs { impl_args: CanonicalState<I, I::GenericArgs> },
98    /// A call to `EvalCtxt::evaluate_added_goals_make_canonical_response` with
99    /// `Certainty` was made. This is the certainty passed in, so it's not unified
100    /// with the certainty of the `try_evaluate_added_goals` that is done within;
101    /// if it's `Certainty::Yes`, then we can trust that the candidate is "finished"
102    /// and we didn't force ambiguity for some reason.
103    MakeCanonicalResponse { shallow_certainty: Certainty },
104}
105
106/// What kind of probe we're in. In case the probe represents a candidate, or
107/// the final result of the current goal - via [ProbeKind::Root] - we also
108/// store the [QueryResult].
109#[derive_where(Clone, Copy, PartialEq, Eq, Hash, Debug; I: Interner)]
110#[derive(TypeVisitable_Generic, TypeFoldable_Generic)]
111pub enum ProbeKind<I: Interner> {
112    /// The root inference context while proving a goal.
113    Root { result: QueryResult<I> },
114    /// Probe entered when normalizing the self ty during candidate assembly
115    NormalizedSelfTyAssembly,
116    /// A candidate for proving a trait or alias-relate goal.
117    TraitCandidate { source: CandidateSource<I>, result: QueryResult<I> },
118    /// Used in the probe that wraps normalizing the non-self type for the unsize
119    /// trait, which is also structurally matched on.
120    UnsizeAssembly,
121    /// During upcasting from some source object to target object type, used to
122    /// do a probe to find out what projection type(s) may be used to prove that
123    /// the source type upholds all of the target type's object bounds.
124    UpcastProjectionCompatibility,
125    /// Looking for param-env candidates that satisfy the trait ref for a projection.
126    ShadowedEnvProbing,
127    /// Try to unify an opaque type with an existing key in the storage.
128    OpaqueTypeStorageLookup { result: QueryResult<I> },
129    /// Checking that a rigid alias is well-formed.
130    RigidAlias { result: QueryResult<I> },
131}
rustc_type_ir/solve/inspect.rs

rustc_type_ir/solve/
inspect.rs
