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
  53     pub fn instantiate_canonical_with_fresh_inference_vars<T>(
  54         &self,
  55         span: Span,
  56         canonical: &Canonical<'tcx, T>,
  57     ) -> (T, CanonicalVarValues<'tcx>)
  58     where
  59         T: TypeFoldable<'tcx>,
  60     {
  61         // For each universe that is referred to in the incoming
  62         // query, create a universe in our local inference context. In
  63         // practice, as of this writing, all queries have no universes
  64         // in them, so this code has no effect, but it is looking
  65         // forward to the day when we *do* want to carry universes
  66         // through into queries.
  67         let universes: IndexVec<ty::UniverseIndex, _> = std::iter::once(ty::UniverseIndex::ROOT)
  68             .chain((0..canonical.max_universe.as_u32()).map(|_| self.create_next_universe()))
  69             .collect();
  70
  71         let canonical_inference_vars =
  72             self.instantiate_canonical_vars(span, canonical.variables, |ui| universes[ui]);
  73         let result = canonical.substitute(self.tcx, &canonical_inference_vars);
  74         (result, canonical_inference_vars)
  75     }
  76
  77     /// Given the "infos" about the canonical variables from some
  78     /// canonical, creates fresh variables with the same
  79     /// characteristics (see `instantiate_canonical_var` for
  80     /// details). You can then use `substitute` to instantiate the
  81     /// canonical variable with these inference variables.
  82     fn instantiate_canonical_vars(
  83         &self,
  84         span: Span,
  85         variables: &List<CanonicalVarInfo<'tcx>>,
  86         universe_map: impl Fn(ty::UniverseIndex) -> ty::UniverseIndex,
  87     ) -> CanonicalVarValues<'tcx> {
  88         let var_values: IndexVec<BoundVar, GenericArg<'tcx>> = variables
  89             .iter()
  90             .map(|info| self.instantiate_canonical_var(span, info, &universe_map))
  91             .collect();
  92
  93         CanonicalVarValues { var_values }
  94     }
  95
  96     /// Given the "info" about a canonical variable, creates a fresh
  97     /// variable for it. If this is an existentially quantified
  98     /// variable, then you'll get a new inference variable; if it is a
  99     /// universally quantified variable, you get a placeholder.
 100     fn instantiate_canonical_var(
 101         &self,
 102         span: Span,
 103         cv_info: CanonicalVarInfo<'tcx>,
 104         universe_map: impl Fn(ty::UniverseIndex) -> ty::UniverseIndex,
 105     ) -> GenericArg<'tcx> {
 106         match cv_info.kind {
 107             CanonicalVarKind::Ty(ty_kind) => {
 108                 let ty = match ty_kind {
 109                     CanonicalTyVarKind::General(ui) => self.next_ty_var_in_universe(
 110                         TypeVariableOrigin { kind: TypeVariableOriginKind::MiscVariable, span },
 111                         universe_map(ui),
 112                     ),
 113
 114                     CanonicalTyVarKind::Int => self.next_int_var(),
 115
 116                     CanonicalTyVarKind::Float => self.next_float_var(),
 117                 };
 118                 ty.into()
 119             }
 120
 121             CanonicalVarKind::PlaceholderTy(ty::PlaceholderType { universe, name }) => {
 122                 let universe_mapped = universe_map(universe);
 123                 let placeholder_mapped = ty::PlaceholderType { universe: universe_mapped, name };
 124                 self.tcx.mk_ty(ty::Placeholder(placeholder_mapped)).into()
 125             }
 126
 127             CanonicalVarKind::Region(ui) => self
 128                 .next_region_var_in_universe(
 129                     RegionVariableOrigin::MiscVariable(span),
 130                     universe_map(ui),
 131                 )
 132                 .into(),
 133
 134             CanonicalVarKind::PlaceholderRegion(ty::PlaceholderRegion { universe, name }) => {
 135                 let universe_mapped = universe_map(universe);
 136                 let placeholder_mapped = ty::PlaceholderRegion { universe: universe_mapped, name };
 137                 self.tcx.mk_region(ty::RePlaceholder(placeholder_mapped)).into()
 138             }
 139
 140             CanonicalVarKind::Const(ui, ty) => self
 141                 .next_const_var_in_universe(
 142                     ty,
 143                     ConstVariableOrigin { kind: ConstVariableOriginKind::MiscVariable, span },
 144                     universe_map(ui),
 145                 )
 146                 .into(),
 147
 148             CanonicalVarKind::PlaceholderConst(ty::PlaceholderConst { universe, name }) => {
 149                 let universe_mapped = universe_map(universe);
 150                 let placeholder_mapped = ty::PlaceholderConst { universe: universe_mapped, name };
 151                 self.tcx
 152                     .mk_const(ty::ConstS {
 153                         val: ty::ConstKind::Placeholder(placeholder_mapped),
 154                         ty: name.ty,
 155                     })
 156                     .into()
 157             }
 158         }
 159     }
 160 }