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, 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         CanonicalVarValues {
  91             var_values: self.tcx.mk_substs(
  92                 variables
  93                     .iter()
  94                     .map(|info| self.instantiate_canonical_var(span, info, &universe_map)),
  95             ),
  96         }
  97     }
  98
  99     /// Given the "info" about a canonical variable, creates a fresh
 100     /// variable for it. If this is an existentially quantified
 101     /// variable, then you'll get a new inference variable; if it is a
 102     /// universally quantified variable, you get a placeholder.
 103     fn instantiate_canonical_var(
 104         &self,
 105         span: Span,
 106         cv_info: CanonicalVarInfo<'tcx>,
 107         universe_map: impl Fn(ty::UniverseIndex) -> ty::UniverseIndex,
 108     ) -> GenericArg<'tcx> {
 109         match cv_info.kind {
 110             CanonicalVarKind::Ty(ty_kind) => {
 111                 let ty = match ty_kind {
 112                     CanonicalTyVarKind::General(ui) => self.next_ty_var_in_universe(
 113                         TypeVariableOrigin { kind: TypeVariableOriginKind::MiscVariable, span },
 114                         universe_map(ui),
 115                     ),
 116
 117                     CanonicalTyVarKind::Int => self.next_int_var(),
 118
 119                     CanonicalTyVarKind::Float => self.next_float_var(),
 120                 };
 121                 ty.into()
 122             }
 123
 124             CanonicalVarKind::PlaceholderTy(ty::PlaceholderType { universe, name }) => {
 125                 let universe_mapped = universe_map(universe);
 126                 let placeholder_mapped = ty::PlaceholderType { universe: universe_mapped, name };
 127                 self.tcx.mk_ty(ty::Placeholder(placeholder_mapped)).into()
 128             }
 129
 130             CanonicalVarKind::Region(ui) => self
 131                 .next_region_var_in_universe(
 132                     RegionVariableOrigin::MiscVariable(span),
 133                     universe_map(ui),
 134                 )
 135                 .into(),
 136
 137             CanonicalVarKind::PlaceholderRegion(ty::PlaceholderRegion { universe, name }) => {
 138                 let universe_mapped = universe_map(universe);
 139                 let placeholder_mapped = ty::PlaceholderRegion { universe: universe_mapped, name };
 140                 self.tcx.mk_region(ty::RePlaceholder(placeholder_mapped)).into()
 141             }
 142
 143             CanonicalVarKind::Const(ui, ty) => self
 144                 .next_const_var_in_universe(
 145                     ty,
 146                     ConstVariableOrigin { kind: ConstVariableOriginKind::MiscVariable, span },
 147                     universe_map(ui),
 148                 )
 149                 .into(),
 150
 151             CanonicalVarKind::PlaceholderConst(ty::PlaceholderConst { universe, name }, ty) => {
 152                 let universe_mapped = universe_map(universe);
 153                 let placeholder_mapped = ty::PlaceholderConst { universe: universe_mapped, name };
 154                 self.tcx.mk_const(placeholder_mapped, ty).into()
 155             }
 156         }
 157     }
 158 }