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