compiler/rustc_middle/src/infer/canonical.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::MemberConstraint;
  25 use crate::ty::subst::GenericArg;
  26 use crate::ty::{self, BoundVar, List, Region, Ty, TyCtxt};
  27 use rustc_index::vec::IndexVec;
  28 use rustc_macros::HashStable;
  29 use smallvec::SmallVec;
  30 use std::iter;
  31 use std::ops::Index;
  32
  33 /// A "canonicalized" type `V` is one where all free inference
  34 /// variables have been rewritten to "canonical vars". These are
  35 /// numbered starting from 0 in order of first appearance.
  36 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, TyDecodable, TyEncodable)]
  37 #[derive(HashStable, TypeFoldable, Lift)]
  38 pub struct Canonical<'tcx, V> {
  39     pub max_universe: ty::UniverseIndex,
  40     pub variables: CanonicalVarInfos<'tcx>,
  41     pub value: V,
  42 }
  43
  44 pub type CanonicalVarInfos<'tcx> = &'tcx List<CanonicalVarInfo<'tcx>>;
  45
  46 /// A set of values corresponding to the canonical variables from some
  47 /// `Canonical`. You can give these values to
  48 /// `canonical_value.substitute` to substitute them into the canonical
  49 /// value at the right places.
  50 ///
  51 /// When you canonicalize a value `V`, you get back one of these
  52 /// vectors with the original values that were replaced by canonical
  53 /// variables. You will need to supply it later to instantiate the
  54 /// canonicalized query response.
  55 #[derive(Clone, Debug, PartialEq, Eq, Hash, TyDecodable, TyEncodable)]
  56 #[derive(HashStable, TypeFoldable, Lift)]
  57 pub struct CanonicalVarValues<'tcx> {
  58     pub var_values: IndexVec<BoundVar, GenericArg<'tcx>>,
  59 }
  60
  61 /// When we canonicalize a value to form a query, we wind up replacing
  62 /// various parts of it with canonical variables. This struct stores
  63 /// those replaced bits to remember for when we process the query
  64 /// result.
  65 #[derive(Clone, Debug)]
  66 pub struct OriginalQueryValues<'tcx> {
  67     /// Map from the universes that appear in the query to the
  68     /// universes in the caller context. For the time being, we only
  69     /// ever put ROOT values into the query, so this map is very
  70     /// simple.
  71     pub universe_map: SmallVec<[ty::UniverseIndex; 4]>,
  72
  73     /// This is equivalent to `CanonicalVarValues`, but using a
  74     /// `SmallVec` yields a significant performance win.
  75     pub var_values: SmallVec<[GenericArg<'tcx>; 8]>,
  76 }
  77
  78 impl<'tcx> Default for OriginalQueryValues<'tcx> {
  79     fn default() -> Self {
  80         let mut universe_map = SmallVec::default();
  81         universe_map.push(ty::UniverseIndex::ROOT);
  82
  83         Self { universe_map, var_values: SmallVec::default() }
  84     }
  85 }
  86
  87 /// Information about a canonical variable that is included with the
  88 /// canonical value. This is sufficient information for code to create
  89 /// a copy of the canonical value in some other inference context,
  90 /// with fresh inference variables replacing the canonical values.
  91 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, TyDecodable, TyEncodable, HashStable)]
  92 pub struct CanonicalVarInfo<'tcx> {
  93     pub kind: CanonicalVarKind<'tcx>,
  94 }
  95
  96 impl<'tcx> CanonicalVarInfo<'tcx> {
  97     pub fn universe(&self) -> ty::UniverseIndex {
  98         self.kind.universe()
  99     }
 100
 101     pub fn is_existential(&self) -> bool {
 102         match self.kind {
 103             CanonicalVarKind::Ty(_) => true,
 104             CanonicalVarKind::PlaceholderTy(_) => false,
 105             CanonicalVarKind::Region(_) => true,
 106             CanonicalVarKind::PlaceholderRegion(..) => false,
 107             CanonicalVarKind::Const(..) => true,
 108             CanonicalVarKind::PlaceholderConst(_) => false,
 109         }
 110     }
 111 }
 112
 113 /// Describes the "kind" of the canonical variable. This is a "kind"
 114 /// in the type-theory sense of the term -- i.e., a "meta" type system
 115 /// that analyzes type-like values.
 116 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, TyDecodable, TyEncodable, HashStable)]
 117 pub enum CanonicalVarKind<'tcx> {
 118     /// Some kind of type inference variable.
 119     Ty(CanonicalTyVarKind),
 120
 121     /// A "placeholder" that represents "any type".
 122     PlaceholderTy(ty::PlaceholderType),
 123
 124     /// Region variable `'?R`.
 125     Region(ty::UniverseIndex),
 126
 127     /// A "placeholder" that represents "any region". Created when you
 128     /// are solving a goal like `for<'a> T: Foo<'a>` to represent the
 129     /// bound region `'a`.
 130     PlaceholderRegion(ty::PlaceholderRegion),
 131
 132     /// Some kind of const inference variable.
 133     Const(ty::UniverseIndex, Ty<'tcx>),
 134
 135     /// A "placeholder" that represents "any const".
 136     PlaceholderConst(ty::PlaceholderConst<'tcx>),
 137 }
 138
 139 impl<'tcx> CanonicalVarKind<'tcx> {
 140     pub fn universe(self) -> ty::UniverseIndex {
 141         match self {
 142             CanonicalVarKind::Ty(kind) => match kind {
 143                 CanonicalTyVarKind::General(ui) => ui,
 144                 CanonicalTyVarKind::Float | CanonicalTyVarKind::Int => ty::UniverseIndex::ROOT,
 145             },
 146
 147             CanonicalVarKind::PlaceholderTy(placeholder) => placeholder.universe,
 148             CanonicalVarKind::Region(ui) => ui,
 149             CanonicalVarKind::PlaceholderRegion(placeholder) => placeholder.universe,
 150             CanonicalVarKind::Const(ui, _) => ui,
 151             CanonicalVarKind::PlaceholderConst(placeholder) => placeholder.universe,
 152         }
 153     }
 154 }
 155
 156 /// Rust actually has more than one category of type variables;
 157 /// notably, the type variables we create for literals (e.g., 22 or
 158 /// 22.) can only be instantiated with integral/float types (e.g.,
 159 /// usize or f32). In order to faithfully reproduce a type, we need to
 160 /// know what set of types a given type variable can be unified with.
 161 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, TyDecodable, TyEncodable, HashStable)]
 162 pub enum CanonicalTyVarKind {
 163     /// General type variable `?T` that can be unified with arbitrary types.
 164     General(ty::UniverseIndex),
 165
 166     /// Integral type variable `?I` (that can only be unified with integral types).
 167     Int,
 168
 169     /// Floating-point type variable `?F` (that can only be unified with float types).
 170     Float,
 171 }
 172
 173 /// After we execute a query with a canonicalized key, we get back a
 174 /// `Canonical<QueryResponse<..>>`. You can use
 175 /// `instantiate_query_result` to access the data in this result.
 176 #[derive(Clone, Debug, HashStable, TypeFoldable, Lift)]
 177 pub struct QueryResponse<'tcx, R> {
 178     pub var_values: CanonicalVarValues<'tcx>,
 179     pub region_constraints: QueryRegionConstraints<'tcx>,
 180     pub certainty: Certainty,
 181     pub value: R,
 182 }
 183
 184 #[derive(Clone, Debug, Default, HashStable, TypeFoldable, Lift)]
 185 pub struct QueryRegionConstraints<'tcx> {
 186     pub outlives: Vec<QueryOutlivesConstraint<'tcx>>,
 187     pub member_constraints: Vec<MemberConstraint<'tcx>>,
 188 }
 189
 190 impl QueryRegionConstraints<'_> {
 191     /// Represents an empty (trivially true) set of region
 192     /// constraints.
 193     pub fn is_empty(&self) -> bool {
 194         self.outlives.is_empty() && self.member_constraints.is_empty()
 195     }
 196 }
 197
 198 pub type Canonicalized<'tcx, V> = Canonical<'tcx, V>;
 199
 200 pub type CanonicalizedQueryResponse<'tcx, T> = &'tcx Canonical<'tcx, QueryResponse<'tcx, T>>;
 201
 202 /// Indicates whether or not we were able to prove the query to be
 203 /// true.
 204 #[derive(Copy, Clone, Debug, HashStable)]
 205 pub enum Certainty {
 206     /// The query is known to be true, presuming that you apply the
 207     /// given `var_values` and the region-constraints are satisfied.
 208     Proven,
 209
 210     /// The query is not known to be true, but also not known to be
 211     /// false. The `var_values` represent *either* values that must
 212     /// hold in order for the query to be true, or helpful tips that
 213     /// *might* make it true. Currently rustc's trait solver cannot
 214     /// distinguish the two (e.g., due to our preference for where
 215     /// clauses over impls).
 216     ///
 217     /// After some unifiations and things have been done, it makes
 218     /// sense to try and prove again -- of course, at that point, the
 219     /// canonical form will be different, making this a distinct
 220     /// query.
 221     Ambiguous,
 222 }
 223
 224 impl Certainty {
 225     pub fn is_proven(&self) -> bool {
 226         match self {
 227             Certainty::Proven => true,
 228             Certainty::Ambiguous => false,
 229         }
 230     }
 231 }
 232
 233 impl<'tcx, R> QueryResponse<'tcx, R> {
 234     pub fn is_proven(&self) -> bool {
 235         self.certainty.is_proven()
 236     }
 237 }
 238
 239 impl<'tcx, R> Canonical<'tcx, QueryResponse<'tcx, R>> {
 240     pub fn is_proven(&self) -> bool {
 241         self.value.is_proven()
 242     }
 243
 244     pub fn is_ambiguous(&self) -> bool {
 245         !self.is_proven()
 246     }
 247 }
 248
 249 impl<'tcx, R> Canonical<'tcx, ty::ParamEnvAnd<'tcx, R>> {
 250     #[inline]
 251     pub fn without_const(mut self) -> Self {
 252         self.value = self.value.without_const();
 253         self
 254     }
 255 }
 256
 257 impl<'tcx, V> Canonical<'tcx, V> {
 258     /// Allows you to map the `value` of a canonical while keeping the
 259     /// same set of bound variables.
 260     ///
 261     /// **WARNING:** This function is very easy to mis-use, hence the
 262     /// name!  In particular, the new value `W` must use all **the
 263     /// same type/region variables** in **precisely the same order**
 264     /// as the original! (The ordering is defined by the
 265     /// `TypeFoldable` implementation of the type in question.)
 266     ///
 267     /// An example of a **correct** use of this:
 268     ///
 269     /// ```rust,ignore (not real code)
 270     /// let a: Canonical<'_, T> = ...;
 271     /// let b: Canonical<'_, (T,)> = a.unchecked_map(|v| (v, ));
 272     /// ```
 273     ///
 274     /// An example of an **incorrect** use of this:
 275     ///
 276     /// ```rust,ignore (not real code)
 277     /// let a: Canonical<'tcx, T> = ...;
 278     /// let ty: Ty<'tcx> = ...;
 279     /// let b: Canonical<'tcx, (T, Ty<'tcx>)> = a.unchecked_map(|v| (v, ty));
 280     /// ```
 281     pub fn unchecked_map<W>(self, map_op: impl FnOnce(V) -> W) -> Canonical<'tcx, W> {
 282         let Canonical { max_universe, variables, value } = self;
 283         Canonical { max_universe, variables, value: map_op(value) }
 284     }
 285 }
 286
 287 pub type QueryOutlivesConstraint<'tcx> =
 288     ty::Binder<'tcx, ty::OutlivesPredicate<GenericArg<'tcx>, Region<'tcx>>>;
 289
 290 TrivialTypeFoldableAndLiftImpls! {
 291     for <'tcx> {
 292         crate::infer::canonical::Certainty,
 293         crate::infer::canonical::CanonicalVarInfo<'tcx>,
 294         crate::infer::canonical::CanonicalVarKind<'tcx>,
 295     }
 296 }
 297
 298 TrivialTypeFoldableImpls! {
 299     for <'tcx> {
 300         crate::infer::canonical::CanonicalVarInfos<'tcx>,
 301     }
 302 }
 303
 304 impl<'tcx> CanonicalVarValues<'tcx> {
 305     #[inline]
 306     pub fn len(&self) -> usize {
 307         self.var_values.len()
 308     }
 309
 310     /// Makes an identity substitution from this one: each bound var
 311     /// is matched to the same bound var, preserving the original kinds.
 312     /// For example, if we have:
 313     /// `self.var_values == [Type(u32), Lifetime('a), Type(u64)]`
 314     /// we'll return a substitution `subst` with:
 315     /// `subst.var_values == [Type(^0), Lifetime(^1), Type(^2)]`.
 316     pub fn make_identity(&self, tcx: TyCtxt<'tcx>) -> Self {
 317         use crate::ty::subst::GenericArgKind;
 318
 319         CanonicalVarValues {
 320             var_values: iter::zip(&self.var_values, 0..)
 321                 .map(|(kind, i)| match kind.unpack() {
 322                     GenericArgKind::Type(..) => {
 323                         tcx.mk_ty(ty::Bound(ty::INNERMOST, ty::BoundVar::from_u32(i).into())).into()
 324                     }
 325                     GenericArgKind::Lifetime(..) => {
 326                         let br =
 327                             ty::BoundRegion { var: ty::BoundVar::from_u32(i), kind: ty::BrAnon(i) };
 328                         tcx.mk_region(ty::ReLateBound(ty::INNERMOST, br)).into()
 329                     }
 330                     GenericArgKind::Const(ct) => tcx
 331                         .mk_const(ty::Const {
 332                             ty: ct.ty,
 333                             val: ty::ConstKind::Bound(ty::INNERMOST, ty::BoundVar::from_u32(i)),
 334                         })
 335                         .into(),
 336                 })
 337                 .collect(),
 338         }
 339     }
 340 }
 341
 342 impl<'a, 'tcx> IntoIterator for &'a CanonicalVarValues<'tcx> {
 343     type Item = GenericArg<'tcx>;
 344     type IntoIter = ::std::iter::Cloned<::std::slice::Iter<'a, GenericArg<'tcx>>>;
 345
 346     fn into_iter(self) -> Self::IntoIter {
 347         self.var_values.iter().cloned()
 348     }
 349 }
 350
 351 impl<'tcx> Index<BoundVar> for CanonicalVarValues<'tcx> {
 352     type Output = GenericArg<'tcx>;
 353
 354     fn index(&self, value: BoundVar) -> &GenericArg<'tcx> {
 355         &self.var_values[value]
 356     }
 357 }