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