diff options
Diffstat (limited to '')
-rw-r--r-- | compiler/rustc_infer/src/infer/canonical/mod.rs | 159 |
1 files changed, 159 insertions, 0 deletions
diff --git a/compiler/rustc_infer/src/infer/canonical/mod.rs b/compiler/rustc_infer/src/infer/canonical/mod.rs new file mode 100644 index 000000000..a9294a85e --- /dev/null +++ b/compiler/rustc_infer/src/infer/canonical/mod.rs @@ -0,0 +1,159 @@ +//! **Canonicalization** is the key to constructing a query in the +//! middle of type inference. Ordinarily, it is not possible to store +//! types from type inference in query keys, because they contain +//! references to inference variables whose lifetimes are too short +//! and so forth. Canonicalizing a value T1 using `canonicalize_query` +//! produces two things: +//! +//! - a value T2 where each unbound inference variable has been +//! replaced with a **canonical variable**; +//! - a map M (of type `CanonicalVarValues`) from those canonical +//! variables back to the original. +//! +//! We can then do queries using T2. These will give back constraints +//! on the canonical variables which can be translated, using the map +//! M, into constraints in our source context. This process of +//! translating the results back is done by the +//! `instantiate_query_result` method. +//! +//! For a more detailed look at what is happening here, check +//! out the [chapter in the rustc dev guide][c]. +//! +//! [c]: https://rust-lang.github.io/chalk/book/canonical_queries/canonicalization.html + +use crate::infer::{ConstVariableOrigin, ConstVariableOriginKind}; +use crate::infer::{InferCtxt, RegionVariableOrigin, TypeVariableOrigin, TypeVariableOriginKind}; +use rustc_index::vec::IndexVec; +use rustc_middle::ty::fold::TypeFoldable; +use rustc_middle::ty::subst::GenericArg; +use rustc_middle::ty::{self, BoundVar, List}; +use rustc_span::source_map::Span; + +pub use rustc_middle::infer::canonical::*; +use substitute::CanonicalExt; + +mod canonicalizer; +pub mod query_response; +mod substitute; + +impl<'cx, 'tcx> InferCtxt<'cx, 'tcx> { + /// Creates a substitution S for the canonical value with fresh + /// inference variables and applies it to the canonical value. + /// Returns both the instantiated result *and* the substitution S. + /// + /// This is only meant to be invoked as part of constructing an + /// inference context at the start of a query (see + /// `InferCtxtBuilder::enter_with_canonical`). It basically + /// brings the canonical value "into scope" within your new infcx. + /// + /// At the end of processing, the substitution S (once + /// canonicalized) then represents the values that you computed + /// for each of the canonical inputs to your query. + pub fn instantiate_canonical_with_fresh_inference_vars<T>( + &self, + span: Span, + canonical: &Canonical<'tcx, T>, + ) -> (T, CanonicalVarValues<'tcx>) + where + T: TypeFoldable<'tcx>, + { + // For each universe that is referred to in the incoming + // query, create a universe in our local inference context. In + // practice, as of this writing, all queries have no universes + // in them, so this code has no effect, but it is looking + // forward to the day when we *do* want to carry universes + // through into queries. + let universes: IndexVec<ty::UniverseIndex, _> = std::iter::once(ty::UniverseIndex::ROOT) + .chain((0..canonical.max_universe.as_u32()).map(|_| self.create_next_universe())) + .collect(); + + let canonical_inference_vars = + self.instantiate_canonical_vars(span, canonical.variables, |ui| universes[ui]); + let result = canonical.substitute(self.tcx, &canonical_inference_vars); + (result, canonical_inference_vars) + } + + /// Given the "infos" about the canonical variables from some + /// canonical, creates fresh variables with the same + /// characteristics (see `instantiate_canonical_var` for + /// details). You can then use `substitute` to instantiate the + /// canonical variable with these inference variables. + fn instantiate_canonical_vars( + &self, + span: Span, + variables: &List<CanonicalVarInfo<'tcx>>, + universe_map: impl Fn(ty::UniverseIndex) -> ty::UniverseIndex, + ) -> CanonicalVarValues<'tcx> { + let var_values: IndexVec<BoundVar, GenericArg<'tcx>> = variables + .iter() + .map(|info| self.instantiate_canonical_var(span, info, &universe_map)) + .collect(); + + CanonicalVarValues { var_values } + } + + /// Given the "info" about a canonical variable, creates a fresh + /// variable for it. If this is an existentially quantified + /// variable, then you'll get a new inference variable; if it is a + /// universally quantified variable, you get a placeholder. + fn instantiate_canonical_var( + &self, + span: Span, + cv_info: CanonicalVarInfo<'tcx>, + universe_map: impl Fn(ty::UniverseIndex) -> ty::UniverseIndex, + ) -> GenericArg<'tcx> { + match cv_info.kind { + CanonicalVarKind::Ty(ty_kind) => { + let ty = match ty_kind { + CanonicalTyVarKind::General(ui) => self.next_ty_var_in_universe( + TypeVariableOrigin { kind: TypeVariableOriginKind::MiscVariable, span }, + universe_map(ui), + ), + + CanonicalTyVarKind::Int => self.next_int_var(), + + CanonicalTyVarKind::Float => self.next_float_var(), + }; + ty.into() + } + + CanonicalVarKind::PlaceholderTy(ty::PlaceholderType { universe, name }) => { + let universe_mapped = universe_map(universe); + let placeholder_mapped = ty::PlaceholderType { universe: universe_mapped, name }; + self.tcx.mk_ty(ty::Placeholder(placeholder_mapped)).into() + } + + CanonicalVarKind::Region(ui) => self + .next_region_var_in_universe( + RegionVariableOrigin::MiscVariable(span), + universe_map(ui), + ) + .into(), + + CanonicalVarKind::PlaceholderRegion(ty::PlaceholderRegion { universe, name }) => { + let universe_mapped = universe_map(universe); + let placeholder_mapped = ty::PlaceholderRegion { universe: universe_mapped, name }; + self.tcx.mk_region(ty::RePlaceholder(placeholder_mapped)).into() + } + + CanonicalVarKind::Const(ui, ty) => self + .next_const_var_in_universe( + ty, + ConstVariableOrigin { kind: ConstVariableOriginKind::MiscVariable, span }, + universe_map(ui), + ) + .into(), + + CanonicalVarKind::PlaceholderConst(ty::PlaceholderConst { universe, name }, ty) => { + let universe_mapped = universe_map(universe); + let placeholder_mapped = ty::PlaceholderConst { universe: universe_mapped, name }; + self.tcx + .mk_const(ty::ConstS { + kind: ty::ConstKind::Placeholder(placeholder_mapped), + ty, + }) + .into() + } + } + } +} |