compiler/rustc_infer/src/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
  24 use crate::infer::{ConstVariableOrigin, ConstVariableOriginKind};
  25 use crate::infer::{InferCtxt, RegionVariableOrigin, TypeVariableOrigin, TypeVariableOriginKind};
  26 use rustc_index::vec::IndexVec;
  27 use rustc_middle::ty::fold::TypeFoldable;
  28 use rustc_middle::ty::subst::GenericArg;
  29 use rustc_middle::ty::{self, BoundVar, List};
  30 use rustc_span::source_map::Span;
  31
  32 pub use rustc_middle::infer::canonical::*;
  33 use substitute::CanonicalExt;
  34
  35 mod canonicalizer;
  36 pub mod query_response;
  37 mod substitute;
  38
  39 impl<'tcx> InferCtxt<'tcx> {
  40     /// Creates a substitution S for the canonical value with fresh
  41     /// inference variables and applies it to the canonical value.
  42     /// Returns both the instantiated result *and* the substitution S.
  43     ///
  44     /// This can be invoked as part of constructing an
  45     /// inference context at the start of a query (see
  46     /// `InferCtxtBuilder::build_with_canonical`). It basically
  47     /// brings the canonical value "into scope" within your new infcx.
  48     ///
  49     /// At the end of processing, the substitution S (once
  50     /// canonicalized) then represents the values that you computed
  51     /// for each of the canonical inputs to your query.
  52     pub fn instantiate_canonical_with_fresh_inference_vars<T>(
  53         &self,
  54         span: Span,
  55         canonical: &Canonical<'tcx, T>,
  56     ) -> (T, CanonicalVarValues<'tcx>)
  57     where
  58         T: TypeFoldable<'tcx>,
  59     {
  60         // For each universe that is referred to in the incoming
  61         // query, create a universe in our local inference context. In
  62         // practice, as of this writing, all queries have no universes
  63         // in them, so this code has no effect, but it is looking
  64         // forward to the day when we *do* want to carry universes
  65         // through into queries.
  66         //
  67         // Instantiate the root-universe content into the current universe,
  68         // and create fresh universes for the higher universes.
  69         let universes: IndexVec<ty::UniverseIndex, _> = std::iter::once(self.universe())
  70             .chain((1..=canonical.max_universe.as_u32()).map(|_| self.create_next_universe()))
  71             .collect();
  72
  73         let canonical_inference_vars =
  74             self.instantiate_canonical_vars(span, canonical.variables, |ui| universes[ui]);
  75         let result = canonical.substitute(self.tcx, &canonical_inference_vars);
  76         (result, canonical_inference_vars)
  77     }
  78
  79     /// Given the "infos" about the canonical variables from some
  80     /// canonical, creates fresh variables with the same
  81     /// characteristics (see `instantiate_canonical_var` for
  82     /// details). You can then use `substitute` to instantiate the
  83     /// canonical variable with these inference variables.
  84     fn instantiate_canonical_vars(
  85         &self,
  86         span: Span,
  87         variables: &List<CanonicalVarInfo<'tcx>>,
  88         universe_map: impl Fn(ty::UniverseIndex) -> ty::UniverseIndex,
  89     ) -> CanonicalVarValues<'tcx> {
  90         let var_values: IndexVec<BoundVar, GenericArg<'tcx>> = variables
  91             .iter()
  92             .map(|info| self.instantiate_canonical_var(span, info, &universe_map))
  93             .collect();
  94
  95         CanonicalVarValues { var_values }
  96     }
  97
  98     /// Given the "info" about a canonical variable, creates a fresh
  99     /// variable for it. If this is an existentially quantified
 100     /// variable, then you'll get a new inference variable; if it is a
 101     /// universally quantified variable, you get a placeholder.
 102     fn instantiate_canonical_var(
 103         &self,
 104         span: Span,
 105         cv_info: CanonicalVarInfo<'tcx>,
 106         universe_map: impl Fn(ty::UniverseIndex) -> ty::UniverseIndex,
 107     ) -> GenericArg<'tcx> {
 108         match cv_info.kind {
 109             CanonicalVarKind::Ty(ty_kind) => {
 110                 let ty = match ty_kind {
 111                     CanonicalTyVarKind::General(ui) => self.next_ty_var_in_universe(
 112                         TypeVariableOrigin { kind: TypeVariableOriginKind::MiscVariable, span },
 113                         universe_map(ui),
 114                     ),
 115
 116                     CanonicalTyVarKind::Int => self.next_int_var(),
 117
 118                     CanonicalTyVarKind::Float => self.next_float_var(),
 119                 };
 120                 ty.into()
 121             }
 122
 123             CanonicalVarKind::PlaceholderTy(ty::PlaceholderType { universe, name }) => {
 124                 let universe_mapped = universe_map(universe);
 125                 let placeholder_mapped = ty::PlaceholderType { universe: universe_mapped, name };
 126                 self.tcx.mk_ty(ty::Placeholder(placeholder_mapped)).into()
 127             }
 128
 129             CanonicalVarKind::Region(ui) => self
 130                 .next_region_var_in_universe(
 131                     RegionVariableOrigin::MiscVariable(span),
 132                     universe_map(ui),
 133                 )
 134                 .into(),
 135
 136             CanonicalVarKind::PlaceholderRegion(ty::PlaceholderRegion { universe, name }) => {
 137                 let universe_mapped = universe_map(universe);
 138                 let placeholder_mapped = ty::PlaceholderRegion { universe: universe_mapped, name };
 139                 self.tcx.mk_region(ty::RePlaceholder(placeholder_mapped)).into()
 140             }
 141
 142             CanonicalVarKind::Const(ui, ty) => self
 143                 .next_const_var_in_universe(
 144                     ty,
 145                     ConstVariableOrigin { kind: ConstVariableOriginKind::MiscVariable, span },
 146                     universe_map(ui),
 147                 )
 148                 .into(),
 149
 150             CanonicalVarKind::PlaceholderConst(ty::PlaceholderConst { universe, name }, ty) => {
 151                 let universe_mapped = universe_map(universe);
 152                 let placeholder_mapped = ty::PlaceholderConst { universe: universe_mapped, name };
 153                 self.tcx.mk_const(placeholder_mapped, ty).into()
 154             }
 155         }
 156     }
 157 }