hir_ty/next_solver/infer/canonical/
mod.rs

1//! **Canonicalization** is the key to constructing a query in the
2//! middle of type inference. Ordinarily, it is not possible to store
3//! types from type inference in query keys, because they contain
4//! references to inference variables whose lifetimes are too short
5//! and so forth. Canonicalizing a value T1 using `canonicalize_query`
6//! produces two things:
7//!
8//! - a value T2 where each unbound inference variable has been
9//!   replaced with a **canonical variable**;
10//! - a map M (of type `CanonicalVarValues`) from those canonical
11//!   variables back to the original.
12//!
13//! We can then do queries using T2. These will give back constraints
14//! on the canonical variables which can be translated, using the map
15//! M, into constraints in our source context. This process of
16//! translating the results back is done by the
17//! `instantiate_query_result` method.
18//!
19//! For a more detailed look at what is happening here, check
20//! out the [chapter in the rustc dev guide][c].
21//!
22//! [c]: https://rust-lang.github.io/chalk/book/canonical_queries/canonicalization.html
23
24use crate::{
25    Span,
26    next_solver::{
27        ArgOutlivesPredicate, Canonical, CanonicalVarValues, Const, DbInterner, GenericArg,
28        OpaqueTypeKey, PlaceholderConst, PlaceholderRegion, PlaceholderType, Region, Ty, TyKind,
29        infer::InferCtxt,
30    },
31};
32use instantiate::CanonicalExt;
33use macros::{TypeFoldable, TypeVisitable};
34use rustc_index::IndexVec;
35use rustc_type_ir::inherent::IntoKind;
36use rustc_type_ir::{CanonicalVarKind, InferTy, TypeFoldable, UniverseIndex, inherent::Ty as _};
37
38pub mod canonicalizer;
39pub mod instantiate;
40
41impl<'db> InferCtxt<'db> {
42    /// Creates an instantiation S for the canonical value with fresh inference
43    /// variables and placeholders then applies it to the canonical value.
44    /// Returns both the instantiated result *and* the instantiation S.
45    ///
46    /// This can be invoked as part of constructing an
47    /// inference context at the start of a query (see
48    /// `InferCtxtBuilder::build_with_canonical`). It basically
49    /// brings the canonical value "into scope" within your new infcx.
50    ///
51    /// At the end of processing, the instantiation S (once
52    /// canonicalized) then represents the values that you computed
53    /// for each of the canonical inputs to your query.
54    pub fn instantiate_canonical<T>(
55        &self,
56        span: Span,
57        canonical: &Canonical<'db, T>,
58    ) -> (T, CanonicalVarValues<'db>)
59    where
60        T: TypeFoldable<DbInterner<'db>>,
61    {
62        // For each universe that is referred to in the incoming
63        // query, create a universe in our local inference context. In
64        // practice, as of this writing, all queries have no universes
65        // in them, so this code has no effect, but it is looking
66        // forward to the day when we *do* want to carry universes
67        // through into queries.
68        //
69        // Instantiate the root-universe content into the current universe,
70        // and create fresh universes for the higher universes.
71        let universes: IndexVec<UniverseIndex, _> = std::iter::once(self.universe())
72            .chain((1..=canonical.max_universe.as_u32()).map(|_| self.create_next_universe()))
73            .collect();
74
75        let var_values = CanonicalVarValues::instantiate(
76            self.interner,
77            canonical.var_kinds,
78            |var_values, info| {
79                self.instantiate_canonical_var(span, info, var_values, |ui| universes[ui])
80            },
81        );
82        let result = canonical.instantiate(self.interner, &var_values);
83        (result, var_values)
84    }
85
86    /// Given the "info" about a canonical variable, creates a fresh
87    /// variable for it. If this is an existentially quantified
88    /// variable, then you'll get a new inference variable; if it is a
89    /// universally quantified variable, you get a placeholder.
90    ///
91    /// FIXME(-Znext-solver): This is public because it's used by the
92    /// new trait solver which has a different canonicalization routine.
93    /// We should somehow deduplicate all of this.
94    pub fn instantiate_canonical_var(
95        &self,
96        span: Span,
97        cv_info: CanonicalVarKind<DbInterner<'db>>,
98        previous_var_values: &[GenericArg<'db>],
99        universe_map: impl Fn(UniverseIndex) -> UniverseIndex,
100    ) -> GenericArg<'db> {
101        match cv_info {
102            CanonicalVarKind::Ty { ui, sub_root } => {
103                let vid = self.next_ty_var_id_in_universe(universe_map(ui), span);
104                // If this inference variable is related to an earlier variable
105                // via subtyping, we need to add that info to the inference context.
106                if let Some(prev) = previous_var_values.get(sub_root.as_usize()) {
107                    if let TyKind::Infer(InferTy::TyVar(sub_root)) = prev.expect_ty().kind() {
108                        self.sub_unify_ty_vids_raw(vid, sub_root);
109                    } else {
110                        unreachable!()
111                    }
112                }
113                Ty::new_var(self.interner, vid).into()
114            }
115
116            CanonicalVarKind::Int => self.next_int_var().into(),
117
118            CanonicalVarKind::Float => self.next_float_var().into(),
119
120            CanonicalVarKind::PlaceholderTy(PlaceholderType { universe, bound, .. }) => {
121                let universe_mapped = universe_map(universe);
122                let placeholder_mapped = PlaceholderType::new(universe_mapped, bound);
123                Ty::new_placeholder(self.interner, placeholder_mapped).into()
124            }
125
126            CanonicalVarKind::Region(ui) => {
127                self.next_region_var_in_universe(universe_map(ui), span).into()
128            }
129
130            CanonicalVarKind::PlaceholderRegion(PlaceholderRegion { universe, bound, .. }) => {
131                let universe_mapped = universe_map(universe);
132                let placeholder_mapped = PlaceholderRegion::new(universe_mapped, bound);
133                Region::new_placeholder(self.interner, placeholder_mapped).into()
134            }
135
136            CanonicalVarKind::Const(ui) => {
137                self.next_const_var_in_universe(universe_map(ui), span).into()
138            }
139            CanonicalVarKind::PlaceholderConst(PlaceholderConst { universe, bound, .. }) => {
140                let universe_mapped = universe_map(universe);
141                let placeholder_mapped = PlaceholderConst::new(universe_mapped, bound);
142                Const::new_placeholder(self.interner, placeholder_mapped).into()
143            }
144        }
145    }
146}
147
148/// After we execute a query with a canonicalized key, we get back a
149/// `Canonical<QueryResponse<..>>`. You can use
150/// `instantiate_query_result` to access the data in this result.
151#[derive(Clone, Debug, TypeVisitable, TypeFoldable)]
152pub struct QueryResponse<'db, R> {
153    pub var_values: CanonicalVarValues<'db>,
154    pub region_constraints: QueryRegionConstraints<'db>,
155    pub opaque_types: Vec<(OpaqueTypeKey<'db>, Ty<'db>)>,
156    pub value: R,
157}
158
159#[derive(Clone, Debug, Default, PartialEq, Eq, Hash, TypeVisitable, TypeFoldable)]
160pub struct QueryRegionConstraints<'db> {
161    pub outlives: Vec<QueryOutlivesConstraint<'db>>,
162    pub assumptions: Vec<ArgOutlivesPredicate<'db>>,
163}
164
165pub type QueryOutlivesConstraint<'tcx> = ArgOutlivesPredicate<'tcx>;
hir_ty/next_solver/infer/canonical/mod.rs

hir_ty/next_solver/infer/canonical/
mod.rs
