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<'cx, 'tcx> InferCtxt<'cx, '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 is only meant to be invoked as part of constructing an
  45     /// inference context at the start of a query (see
  46     /// `InferCtxtBuilder::enter_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         let universes: IndexVec<ty::UniverseIndex, _> = std::iter::once(ty::UniverseIndex::ROOT)
  67             .chain((0..canonical.max_universe.as_u32()).map(|_| self.create_next_universe()))
  68             .collect();
  69
  70         let canonical_inference_vars =
  71             self.instantiate_canonical_vars(span, canonical.variables, |ui| universes[ui]);
  72         let result = canonical.substitute(self.tcx, &canonical_inference_vars);
  73         (result, canonical_inference_vars)
  74     }
  75
  76     /// Given the "infos" about the canonical variables from some
  77     /// canonical, creates fresh variables with the same
  78     /// characteristics (see `instantiate_canonical_var` for
  79     /// details). You can then use `substitute` to instantiate the
  80     /// canonical variable with these inference variables.
  81     fn instantiate_canonical_vars(
  82         &self,
  83         span: Span,
  84         variables: &List<CanonicalVarInfo<'tcx>>,
  85         universe_map: impl Fn(ty::UniverseIndex) -> ty::UniverseIndex,
  86     ) -> CanonicalVarValues<'tcx> {
  87         let var_values: IndexVec<BoundVar, GenericArg<'tcx>> = variables
  88             .iter()
  89             .map(|info| self.instantiate_canonical_var(span, info, &universe_map))
  90             .collect();
  91
  92         CanonicalVarValues { var_values }
  93     }
  94
  95     /// Given the "info" about a canonical variable, creates a fresh
  96     /// variable for it. If this is an existentially quantified
  97     /// variable, then you'll get a new inference variable; if it is a
  98     /// universally quantified variable, you get a placeholder.
  99     fn instantiate_canonical_var(
 100         &self,
 101         span: Span,
 102         cv_info: CanonicalVarInfo<'tcx>,
 103         universe_map: impl Fn(ty::UniverseIndex) -> ty::UniverseIndex,
 104     ) -> GenericArg<'tcx> {
 105         match cv_info.kind {
 106             CanonicalVarKind::Ty(ty_kind) => {
 107                 let ty = match ty_kind {
 108                     CanonicalTyVarKind::General(ui) => self.next_ty_var_in_universe(
 109                         TypeVariableOrigin { kind: TypeVariableOriginKind::MiscVariable, span },
 110                         universe_map(ui),
 111                     ),
 112
 113                     CanonicalTyVarKind::Int => self.next_int_var(),
 114
 115                     CanonicalTyVarKind::Float => self.next_float_var(),
 116                 };
 117                 ty.into()
 118             }
 119
 120             CanonicalVarKind::PlaceholderTy(ty::PlaceholderType { universe, name }) => {
 121                 let universe_mapped = universe_map(universe);
 122                 let placeholder_mapped = ty::PlaceholderType { universe: universe_mapped, name };
 123                 self.tcx.mk_ty(ty::Placeholder(placeholder_mapped)).into()
 124             }
 125
 126             CanonicalVarKind::Region(ui) => self
 127                 .next_region_var_in_universe(
 128                     RegionVariableOrigin::MiscVariable(span),
 129                     universe_map(ui),
 130                 )
 131                 .into(),
 132
 133             CanonicalVarKind::PlaceholderRegion(ty::PlaceholderRegion { universe, name }) => {
 134                 let universe_mapped = universe_map(universe);
 135                 let placeholder_mapped = ty::PlaceholderRegion { universe: universe_mapped, name };
 136                 self.tcx.mk_region(ty::RePlaceholder(placeholder_mapped)).into()
 137             }
 138
 139             CanonicalVarKind::Const(ui, ty) => self
 140                 .next_const_var_in_universe(
 141                     ty,
 142                     ConstVariableOrigin { kind: ConstVariableOriginKind::MiscVariable, span },
 143                     universe_map(ui),
 144                 )
 145                 .into(),
 146
 147             CanonicalVarKind::PlaceholderConst(ty::PlaceholderConst { universe, name }) => {
 148                 let universe_mapped = universe_map(universe);
 149                 let placeholder_mapped = ty::PlaceholderConst { universe: universe_mapped, name };
 150                 self.tcx
 151                     .mk_const(ty::ConstS {
 152                         val: ty::ConstKind::Placeholder(placeholder_mapped),
 153                         ty: name.ty,
 154                     })
 155                     .into()
 156             }
 157         }
 158     }
 159 }