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::next_solver::{
25    AliasTy, Binder, Canonical, CanonicalVarValues, CanonicalVars, Const, DbInterner, GenericArg,
26    Goal, ParamEnv, PlaceholderConst, PlaceholderRegion, PlaceholderTy, Predicate, PredicateKind,
27    Region, Ty, TyKind,
28    infer::{
29        DefineOpaqueTypes, InferCtxt, TypeTrace,
30        traits::{Obligation, PredicateObligations},
31    },
32};
33use instantiate::CanonicalExt;
34use rustc_index::IndexVec;
35use rustc_type_ir::{
36    AliasRelationDirection, AliasTyKind, CanonicalTyVarKind, CanonicalVarKind, InferTy,
37    TypeFoldable, UniverseIndex, Upcast, Variance,
38    inherent::{SliceLike, Ty as _},
39    relate::{
40        Relate, TypeRelation, VarianceDiagInfo,
41        combine::{super_combine_consts, super_combine_tys},
42    },
43};
44
45pub mod instantiate;
46
47impl<'db> InferCtxt<'db> {
48    /// Creates an instantiation S for the canonical value with fresh inference
49    /// variables and placeholders then applies it to the canonical value.
50    /// Returns both the instantiated result *and* the instantiation S.
51    ///
52    /// This can be invoked as part of constructing an
53    /// inference context at the start of a query (see
54    /// `InferCtxtBuilder::build_with_canonical`). It basically
55    /// brings the canonical value "into scope" within your new infcx.
56    ///
57    /// At the end of processing, the instantiation S (once
58    /// canonicalized) then represents the values that you computed
59    /// for each of the canonical inputs to your query.
60    pub fn instantiate_canonical<T>(
61        &self,
62        canonical: &Canonical<'db, T>,
63    ) -> (T, CanonicalVarValues<'db>)
64    where
65        T: TypeFoldable<DbInterner<'db>>,
66    {
67        // For each universe that is referred to in the incoming
68        // query, create a universe in our local inference context. In
69        // practice, as of this writing, all queries have no universes
70        // in them, so this code has no effect, but it is looking
71        // forward to the day when we *do* want to carry universes
72        // through into queries.
73        //
74        // Instantiate the root-universe content into the current universe,
75        // and create fresh universes for the higher universes.
76        let universes: IndexVec<UniverseIndex, _> = std::iter::once(self.universe())
77            .chain((1..=canonical.max_universe.as_u32()).map(|_| self.create_next_universe()))
78            .collect();
79
80        let canonical_inference_vars =
81            self.instantiate_canonical_vars(canonical.variables, |ui| universes[ui]);
82        let result = canonical.instantiate(self.interner, &canonical_inference_vars);
83        (result, canonical_inference_vars)
84    }
85
86    /// Given the "infos" about the canonical variables from some
87    /// canonical, creates fresh variables with the same
88    /// characteristics (see `instantiate_canonical_var` for
89    /// details). You can then use `instantiate` to instantiate the
90    /// canonical variable with these inference variables.
91    fn instantiate_canonical_vars(
92        &self,
93        variables: CanonicalVars<'db>,
94        universe_map: impl Fn(UniverseIndex) -> UniverseIndex,
95    ) -> CanonicalVarValues<'db> {
96        CanonicalVarValues {
97            var_values: self.interner.mk_args_from_iter(
98                variables.iter().map(|info| self.instantiate_canonical_var(info, &universe_map)),
99            ),
100        }
101    }
102
103    /// Given the "info" about a canonical variable, creates a fresh
104    /// variable for it. If this is an existentially quantified
105    /// variable, then you'll get a new inference variable; if it is a
106    /// universally quantified variable, you get a placeholder.
107    ///
108    /// FIXME(-Znext-solver): This is public because it's used by the
109    /// new trait solver which has a different canonicalization routine.
110    /// We should somehow deduplicate all of this.
111    pub fn instantiate_canonical_var(
112        &self,
113        cv_info: CanonicalVarKind<DbInterner<'db>>,
114        universe_map: impl Fn(UniverseIndex) -> UniverseIndex,
115    ) -> GenericArg<'db> {
116        match cv_info {
117            CanonicalVarKind::Ty(ty_kind) => {
118                let ty = match ty_kind {
119                    CanonicalTyVarKind::General(ui) => {
120                        self.next_ty_var_in_universe(universe_map(ui))
121                    }
122
123                    CanonicalTyVarKind::Int => self.next_int_var(),
124
125                    CanonicalTyVarKind::Float => self.next_float_var(),
126                };
127                ty.into()
128            }
129
130            CanonicalVarKind::PlaceholderTy(PlaceholderTy { universe, bound }) => {
131                let universe_mapped = universe_map(universe);
132                let placeholder_mapped = PlaceholderTy { universe: universe_mapped, bound };
133                Ty::new_placeholder(self.interner, placeholder_mapped).into()
134            }
135
136            CanonicalVarKind::Region(ui) => {
137                self.next_region_var_in_universe(universe_map(ui)).into()
138            }
139
140            CanonicalVarKind::PlaceholderRegion(PlaceholderRegion { universe, bound }) => {
141                let universe_mapped = universe_map(universe);
142                let placeholder_mapped: crate::next_solver::Placeholder<
143                    crate::next_solver::BoundRegion,
144                > = PlaceholderRegion { universe: universe_mapped, bound };
145                Region::new_placeholder(self.interner, placeholder_mapped).into()
146            }
147
148            CanonicalVarKind::Const(ui) => self.next_const_var_in_universe(universe_map(ui)).into(),
149            CanonicalVarKind::PlaceholderConst(PlaceholderConst { universe, bound }) => {
150                let universe_mapped = universe_map(universe);
151                let placeholder_mapped = PlaceholderConst { universe: universe_mapped, bound };
152                Const::new_placeholder(self.interner, placeholder_mapped).into()
153            }
154        }
155    }
156}
hir_ty/next_solver/infer/canonical/mod.rs

hir_ty/next_solver/infer/canonical/
mod.rs
