rustc_infer/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
24pub use instantiate::{CanonicalExt, instantiate_value};
25use rustc_index::IndexVec;
26pub use rustc_middle::infer::canonical::*;
27use rustc_middle::ty::{self, GenericArg, Ty, TyCtxt, TypeFoldable};
28use rustc_span::Span;
29
30use crate::infer::{InferCtxt, RegionVariableOrigin};
31
32mod canonicalizer;
33mod instantiate;
34pub mod query_response;
35
36impl<'tcx> InferCtxt<'tcx> {
37    /// Creates an instantiation S for the canonical value with fresh inference
38    /// variables and placeholders then applies it to the canonical value.
39    /// Returns both the instantiated result *and* the instantiation S.
40    ///
41    /// This can be invoked as part of constructing an
42    /// inference context at the start of a query (see
43    /// `InferCtxtBuilder::build_with_canonical`). It basically
44    /// brings the canonical value "into scope" within your new infcx.
45    ///
46    /// At the end of processing, the instantiation S (once
47    /// canonicalized) then represents the values that you computed
48    /// for each of the canonical inputs to your query.
49    pub fn instantiate_canonical<T>(
50        &self,
51        span: Span,
52        canonical: &Canonical<'tcx, T>,
53    ) -> (T, CanonicalVarValues<'tcx>)
54    where
55        T: TypeFoldable<TyCtxt<'tcx>>,
56    {
57        // For each universe that is referred to in the incoming
58        // query, create a universe in our local inference context. In
59        // practice, as of this writing, all queries have no universes
60        // in them, so this code has no effect, but it is looking
61        // forward to the day when we *do* want to carry universes
62        // through into queries.
63        //
64        // Instantiate the root-universe content into the current universe,
65        // and create fresh universes for the higher universes.
66        let universes: IndexVec<ty::UniverseIndex, _> = std::iter::once(self.universe())
67            .chain((1..=canonical.max_universe.as_u32()).map(|_| self.create_next_universe()))
68            .collect();
69
70        let var_values = CanonicalVarValues::instantiate(
71            self.tcx,
72            &canonical.var_kinds,
73            |prev_var_values, info| {
74                self.instantiate_canonical_var(span, info, &prev_var_values, |ui| universes[ui])
75            },
76        );
77        let result = canonical.instantiate(self.tcx, &var_values);
78        (result, var_values)
79    }
80
81    /// Given the "info" about a canonical variable, creates a fresh
82    /// variable for it. If this is an existentially quantified
83    /// variable, then you'll get a new inference variable; if it is a
84    /// universally quantified variable, you get a placeholder.
85    ///
86    /// FIXME(-Znext-solver): This is public because it's used by the
87    /// new trait solver which has a different canonicalization routine.
88    /// We should somehow deduplicate all of this.
89    pub fn instantiate_canonical_var(
90        &self,
91        span: Span,
92        kind: CanonicalVarKind<'tcx>,
93        prev_var_values: &[GenericArg<'tcx>],
94        universe_map: impl Fn(ty::UniverseIndex) -> ty::UniverseIndex,
95    ) -> GenericArg<'tcx> {
96        match kind {
97            CanonicalVarKind::Ty { ui, sub_root } => {
98                let vid = self.next_ty_vid_in_universe(span, universe_map(ui));
99                // If this inference variable is related to an earlier variable
100                // via subtyping, we need to add that info to the inference context.
101                if let Some(prev) = prev_var_values.get(sub_root.as_usize()) {
102                    if let &ty::Infer(ty::TyVar(sub_root)) = prev.expect_ty().kind() {
103                        self.sub_unify_ty_vids_raw(vid, sub_root);
104                    } else {
105                        ::core::panicking::unreachable_default_msg()unreachable!()
106                    }
107                }
108                Ty::new_var(self.tcx, vid).into()
109            }
110
111            CanonicalVarKind::Int => self.next_int_var().into(),
112
113            CanonicalVarKind::Float => {
114                // There is no HirId available to pass as a lint_id.
115                self.next_float_var(span, None).into()
116            }
117
118            CanonicalVarKind::PlaceholderTy(ty::PlaceholderType { universe, bound, .. }) => {
119                let universe_mapped = universe_map(universe);
120                let placeholder_mapped = ty::PlaceholderType::new(universe_mapped, bound);
121                Ty::new_placeholder(self.tcx, placeholder_mapped).into()
122            }
123
124            CanonicalVarKind::Region(ui) => self
125                .next_region_var_in_universe(RegionVariableOrigin::Misc(span), universe_map(ui))
126                .into(),
127
128            CanonicalVarKind::PlaceholderRegion(ty::PlaceholderRegion {
129                universe, bound, ..
130            }) => {
131                let universe_mapped = universe_map(universe);
132                let placeholder_mapped = ty::PlaceholderRegion::new(universe_mapped, bound);
133                ty::Region::new_placeholder(self.tcx, placeholder_mapped).into()
134            }
135
136            CanonicalVarKind::Const(ui) => {
137                self.next_const_var_in_universe(span, universe_map(ui)).into()
138            }
139            CanonicalVarKind::PlaceholderConst(ty::PlaceholderConst {
140                universe, bound, ..
141            }) => {
142                let universe_mapped = universe_map(universe);
143                let placeholder_mapped = ty::PlaceholderConst::new(universe_mapped, bound);
144                ty::Const::new_placeholder(self.tcx, placeholder_mapped).into()
145            }
146        }
147    }
148}
rustc_infer/infer/canonical/mod.rs

rustc_infer/infer/canonical/
mod.rs
