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