src/librustc/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 guide][c].
  21 //!
  22 //! [c]: https://rust-lang.github.io/rustc-guide/traits/canonicalization.html
  23
  24 use crate::infer::{InferCtxt, RegionVariableOrigin, TypeVariableOrigin};
  25 use rustc_data_structures::indexed_vec::IndexVec;
  26 use rustc_macros::HashStable;
  27 use serialize::UseSpecializedDecodable;
  28 use smallvec::SmallVec;
  29 use std::ops::Index;
  30 use syntax::source_map::Span;
  31 use crate::ty::fold::TypeFoldable;
  32 use crate::ty::subst::Kind;
  33 use crate::ty::{self, BoundVar, Lift, List, Region, TyCtxt};
  34
  35 mod canonicalizer;
  36
  37 pub mod query_response;
  38
  39 mod substitute;
  40
  41 /// A "canonicalized" type `V` is one where all free inference
  42 /// variables have been rewritten to "canonical vars". These are
  43 /// numbered starting from 0 in order of first appearance.
  44 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable, HashStable)]
  45 pub struct Canonical<'gcx, V> {
  46     pub max_universe: ty::UniverseIndex,
  47     pub variables: CanonicalVarInfos<'gcx>,
  48     pub value: V,
  49 }
  50
  51 pub type CanonicalVarInfos<'gcx> = &'gcx List<CanonicalVarInfo>;
  52
  53 impl<'gcx> UseSpecializedDecodable for CanonicalVarInfos<'gcx> {}
  54
  55 /// A set of values corresponding to the canonical variables from some
  56 /// `Canonical`. You can give these values to
  57 /// `canonical_value.substitute` to substitute them into the canonical
  58 /// value at the right places.
  59 ///
  60 /// When you canonicalize a value `V`, you get back one of these
  61 /// vectors with the original values that were replaced by canonical
  62 /// variables. You will need to supply it later to instantiate the
  63 /// canonicalized query response.
  64 #[derive(Clone, Debug, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable, HashStable)]
  65 pub struct CanonicalVarValues<'tcx> {
  66     pub var_values: IndexVec<BoundVar, Kind<'tcx>>,
  67 }
  68
  69 /// When we canonicalize a value to form a query, we wind up replacing
  70 /// various parts of it with canonical variables. This struct stores
  71 /// those replaced bits to remember for when we process the query
  72 /// result.
  73 #[derive(Clone, Debug, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable)]
  74 pub struct OriginalQueryValues<'tcx> {
  75     /// Map from the universes that appear in the query to the
  76     /// universes in the caller context. For the time being, we only
  77     /// ever put ROOT values into the query, so this map is very
  78     /// simple.
  79     pub universe_map: SmallVec<[ty::UniverseIndex; 4]>,
  80
  81     /// This is equivalent to `CanonicalVarValues`, but using a
  82     /// `SmallVec` yields a significant performance win.
  83     pub var_values: SmallVec<[Kind<'tcx>; 8]>,
  84 }
  85
  86 impl Default for OriginalQueryValues<'tcx> {
  87     fn default() -> Self {
  88         let mut universe_map = SmallVec::default();
  89         universe_map.push(ty::UniverseIndex::ROOT);
  90
  91         Self {
  92             universe_map,
  93             var_values: SmallVec::default(),
  94         }
  95     }
  96 }
  97
  98 /// Information about a canonical variable that is included with the
  99 /// canonical value. This is sufficient information for code to create
 100 /// a copy of the canonical value in some other inference context,
 101 /// with fresh inference variables replacing the canonical values.
 102 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable, HashStable)]
 103 pub struct CanonicalVarInfo {
 104     pub kind: CanonicalVarKind,
 105 }
 106
 107 impl CanonicalVarInfo {
 108     pub fn universe(&self) -> ty::UniverseIndex {
 109         self.kind.universe()
 110     }
 111
 112     pub fn is_existential(&self) -> bool {
 113         match self.kind {
 114             CanonicalVarKind::Ty(_) => true,
 115             CanonicalVarKind::PlaceholderTy(_) => false,
 116             CanonicalVarKind::Region(_) => true,
 117             CanonicalVarKind::PlaceholderRegion(..) => false,
 118         }
 119     }
 120 }
 121
 122 /// Describes the "kind" of the canonical variable. This is a "kind"
 123 /// in the type-theory sense of the term -- i.e., a "meta" type system
 124 /// that analyzes type-like values.
 125 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable, HashStable)]
 126 pub enum CanonicalVarKind {
 127     /// Some kind of type inference variable.
 128     Ty(CanonicalTyVarKind),
 129
 130     /// A "placeholder" that represents "any type".
 131     PlaceholderTy(ty::PlaceholderType),
 132
 133     /// Region variable `'?R`.
 134     Region(ty::UniverseIndex),
 135
 136     /// A "placeholder" that represents "any region". Created when you
 137     /// are solving a goal like `for<'a> T: Foo<'a>` to represent the
 138     /// bound region `'a`.
 139     PlaceholderRegion(ty::PlaceholderRegion),
 140 }
 141
 142 impl CanonicalVarKind {
 143     pub fn universe(self) -> ty::UniverseIndex {
 144         match self {
 145             CanonicalVarKind::Ty(kind) => match kind {
 146                 CanonicalTyVarKind::General(ui) => ui,
 147                 CanonicalTyVarKind::Float | CanonicalTyVarKind::Int => ty::UniverseIndex::ROOT,
 148             }
 149
 150             CanonicalVarKind::PlaceholderTy(placeholder) => placeholder.universe,
 151             CanonicalVarKind::Region(ui) => ui,
 152             CanonicalVarKind::PlaceholderRegion(placeholder) => placeholder.universe,
 153         }
 154     }
 155 }
 156
 157 /// Rust actually has more than one category of type variables;
 158 /// notably, the type variables we create for literals (e.g., 22 or
 159 /// 22.) can only be instantiated with integral/float types (e.g.,
 160 /// usize or f32). In order to faithfully reproduce a type, we need to
 161 /// know what set of types a given type variable can be unified with.
 162 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable, HashStable)]
 163 pub enum CanonicalTyVarKind {
 164     /// General type variable `?T` that can be unified with arbitrary types.
 165     General(ty::UniverseIndex),
 166
 167     /// Integral type variable `?I` (that can only be unified with integral types).
 168     Int,
 169
 170     /// Floating-point type variable `?F` (that can only be unified with float types).
 171     Float,
 172 }
 173
 174 /// After we execute a query with a canonicalized key, we get back a
 175 /// `Canonical<QueryResponse<..>>`. You can use
 176 /// `instantiate_query_result` to access the data in this result.
 177 #[derive(Clone, Debug, HashStable)]
 178 pub struct QueryResponse<'tcx, R> {
 179     pub var_values: CanonicalVarValues<'tcx>,
 180     pub region_constraints: Vec<QueryRegionConstraint<'tcx>>,
 181     pub certainty: Certainty,
 182     pub value: R,
 183 }
 184
 185 pub type Canonicalized<'gcx, V> = Canonical<'gcx, <V as Lift<'gcx>>::Lifted>;
 186
 187 pub type CanonicalizedQueryResponse<'gcx, T> =
 188     &'gcx Canonical<'gcx, QueryResponse<'gcx, <T as Lift<'gcx>>::Lifted>>;
 189
 190 /// Indicates whether or not we were able to prove the query to be
 191 /// true.
 192 #[derive(Copy, Clone, Debug, HashStable)]
 193 pub enum Certainty {
 194     /// The query is known to be true, presuming that you apply the
 195     /// given `var_values` and the region-constraints are satisfied.
 196     Proven,
 197
 198     /// The query is not known to be true, but also not known to be
 199     /// false. The `var_values` represent *either* values that must
 200     /// hold in order for the query to be true, or helpful tips that
 201     /// *might* make it true. Currently rustc's trait solver cannot
 202     /// distinguish the two (e.g., due to our preference for where
 203     /// clauses over impls).
 204     ///
 205     /// After some unifiations and things have been done, it makes
 206     /// sense to try and prove again -- of course, at that point, the
 207     /// canonical form will be different, making this a distinct
 208     /// query.
 209     Ambiguous,
 210 }
 211
 212 impl Certainty {
 213     pub fn is_proven(&self) -> bool {
 214         match self {
 215             Certainty::Proven => true,
 216             Certainty::Ambiguous => false,
 217         }
 218     }
 219
 220     pub fn is_ambiguous(&self) -> bool {
 221         !self.is_proven()
 222     }
 223 }
 224
 225 impl<'tcx, R> QueryResponse<'tcx, R> {
 226     pub fn is_proven(&self) -> bool {
 227         self.certainty.is_proven()
 228     }
 229
 230     pub fn is_ambiguous(&self) -> bool {
 231         !self.is_proven()
 232     }
 233 }
 234
 235 impl<'tcx, R> Canonical<'tcx, QueryResponse<'tcx, R>> {
 236     pub fn is_proven(&self) -> bool {
 237         self.value.is_proven()
 238     }
 239
 240     pub fn is_ambiguous(&self) -> bool {
 241         !self.is_proven()
 242     }
 243 }
 244
 245 impl<'gcx, V> Canonical<'gcx, V> {
 246     /// Allows you to map the `value` of a canonical while keeping the
 247     /// same set of bound variables.
 248     ///
 249     /// **WARNING:** This function is very easy to mis-use, hence the
 250     /// name!  In particular, the new value `W` must use all **the
 251     /// same type/region variables** in **precisely the same order**
 252     /// as the original! (The ordering is defined by the
 253     /// `TypeFoldable` implementation of the type in question.)
 254     ///
 255     /// An example of a **correct** use of this:
 256     ///
 257     /// ```rust,ignore (not real code)
 258     /// let a: Canonical<'_, T> = ...;
 259     /// let b: Canonical<'_, (T,)> = a.unchecked_map(|v| (v, ));
 260     /// ```
 261     ///
 262     /// An example of an **incorrect** use of this:
 263     ///
 264     /// ```rust,ignore (not real code)
 265     /// let a: Canonical<'tcx, T> = ...;
 266     /// let ty: Ty<'tcx> = ...;
 267     /// let b: Canonical<'tcx, (T, Ty<'tcx>)> = a.unchecked_map(|v| (v, ty));
 268     /// ```
 269     pub fn unchecked_map<W>(self, map_op: impl FnOnce(V) -> W) -> Canonical<'gcx, W> {
 270         let Canonical {
 271             max_universe,
 272             variables,
 273             value,
 274         } = self;
 275         Canonical {
 276             max_universe,
 277             variables,
 278             value: map_op(value),
 279         }
 280     }
 281 }
 282
 283 pub type QueryRegionConstraint<'tcx> = ty::Binder<ty::OutlivesPredicate<Kind<'tcx>, Region<'tcx>>>;
 284
 285 impl<'cx, 'gcx, 'tcx> InferCtxt<'cx, 'gcx, 'tcx> {
 286     /// Creates a substitution S for the canonical value with fresh
 287     /// inference variables and applies it to the canonical value.
 288     /// Returns both the instantiated result *and* the substitution S.
 289     ///
 290     /// This is only meant to be invoked as part of constructing an
 291     /// inference context at the start of a query (see
 292     /// `InferCtxtBuilder::enter_with_canonical`). It basically
 293     /// brings the canonical value "into scope" within your new infcx.
 294     ///
 295     /// At the end of processing, the substitution S (once
 296     /// canonicalized) then represents the values that you computed
 297     /// for each of the canonical inputs to your query.
 298
 299     pub fn instantiate_canonical_with_fresh_inference_vars<T>(
 300         &self,
 301         span: Span,
 302         canonical: &Canonical<'tcx, T>,
 303     ) -> (T, CanonicalVarValues<'tcx>)
 304     where
 305         T: TypeFoldable<'tcx>,
 306     {
 307         // For each universe that is referred to in the incoming
 308         // query, create a universe in our local inference context. In
 309         // practice, as of this writing, all queries have no universes
 310         // in them, so this code has no effect, but it is looking
 311         // forward to the day when we *do* want to carry universes
 312         // through into queries.
 313         let universes: IndexVec<ty::UniverseIndex, _> = std::iter::once(ty::UniverseIndex::ROOT)
 314             .chain((0..canonical.max_universe.as_u32()).map(|_| self.create_next_universe()))
 315             .collect();
 316
 317         let canonical_inference_vars =
 318             self.instantiate_canonical_vars(span, canonical.variables, |ui| universes[ui]);
 319         let result = canonical.substitute(self.tcx, &canonical_inference_vars);
 320         (result, canonical_inference_vars)
 321     }
 322
 323     /// Given the "infos" about the canonical variables from some
 324     /// canonical, creates fresh variables with the same
 325     /// characteristics (see `instantiate_canonical_var` for
 326     /// details). You can then use `substitute` to instantiate the
 327     /// canonical variable with these inference variables.
 328     fn instantiate_canonical_vars(
 329         &self,
 330         span: Span,
 331         variables: &List<CanonicalVarInfo>,
 332         universe_map: impl Fn(ty::UniverseIndex) -> ty::UniverseIndex,
 333     ) -> CanonicalVarValues<'tcx> {
 334         let var_values: IndexVec<BoundVar, Kind<'tcx>> = variables
 335             .iter()
 336             .map(|info| self.instantiate_canonical_var(span, *info, &universe_map))
 337             .collect();
 338
 339         CanonicalVarValues { var_values }
 340     }
 341
 342     /// Given the "info" about a canonical variable, creates a fresh
 343     /// variable for it. If this is an existentially quantified
 344     /// variable, then you'll get a new inference variable; if it is a
 345     /// universally quantified variable, you get a placeholder.
 346     fn instantiate_canonical_var(
 347         &self,
 348         span: Span,
 349         cv_info: CanonicalVarInfo,
 350         universe_map: impl Fn(ty::UniverseIndex) -> ty::UniverseIndex,
 351     ) -> Kind<'tcx> {
 352         match cv_info.kind {
 353             CanonicalVarKind::Ty(ty_kind) => {
 354                 let ty = match ty_kind {
 355                     CanonicalTyVarKind::General(ui) => {
 356                         self.next_ty_var_in_universe(
 357                             TypeVariableOrigin::MiscVariable(span),
 358                             universe_map(ui)
 359                         )
 360                     }
 361
 362                     CanonicalTyVarKind::Int => self.next_int_var(),
 363
 364                     CanonicalTyVarKind::Float => self.next_float_var(),
 365                 };
 366                 ty.into()
 367             }
 368
 369             CanonicalVarKind::PlaceholderTy(ty::PlaceholderType { universe, name }) => {
 370                 let universe_mapped = universe_map(universe);
 371                 let placeholder_mapped = ty::PlaceholderType {
 372                     universe: universe_mapped,
 373                     name,
 374                 };
 375                 self.tcx.mk_ty(ty::Placeholder(placeholder_mapped)).into()
 376             }
 377
 378             CanonicalVarKind::Region(ui) => self.next_region_var_in_universe(
 379                 RegionVariableOrigin::MiscVariable(span),
 380                 universe_map(ui),
 381             ).into(),
 382
 383             CanonicalVarKind::PlaceholderRegion(ty::PlaceholderRegion { universe, name }) => {
 384                 let universe_mapped = universe_map(universe);
 385                 let placeholder_mapped = ty::PlaceholderRegion {
 386                     universe: universe_mapped,
 387                     name,
 388                 };
 389                 self.tcx.mk_region(ty::RePlaceholder(placeholder_mapped)).into()
 390             }
 391         }
 392     }
 393 }
 394
 395 CloneTypeFoldableAndLiftImpls! {
 396     crate::infer::canonical::Certainty,
 397     crate::infer::canonical::CanonicalVarInfo,
 398     crate::infer::canonical::CanonicalVarKind,
 399 }
 400
 401 CloneTypeFoldableImpls! {
 402     for <'tcx> {
 403         crate::infer::canonical::CanonicalVarInfos<'tcx>,
 404     }
 405 }
 406
 407 BraceStructTypeFoldableImpl! {
 408     impl<'tcx, C> TypeFoldable<'tcx> for Canonical<'tcx, C> {
 409         max_universe,
 410         variables,
 411         value,
 412     } where C: TypeFoldable<'tcx>
 413 }
 414
 415 BraceStructLiftImpl! {
 416     impl<'a, 'tcx, T> Lift<'tcx> for Canonical<'a, T> {
 417         type Lifted = Canonical<'tcx, T::Lifted>;
 418         max_universe, variables, value
 419     } where T: Lift<'tcx>
 420 }
 421
 422 impl<'tcx> CanonicalVarValues<'tcx> {
 423     pub fn len(&self) -> usize {
 424         self.var_values.len()
 425     }
 426
 427     /// Makes an identity substitution from this one: each bound var
 428     /// is matched to the same bound var, preserving the original kinds.
 429     /// For example, if we have:
 430     /// `self.var_values == [Type(u32), Lifetime('a), Type(u64)]`
 431     /// we'll return a substitution `subst` with:
 432     /// `subst.var_values == [Type(^0), Lifetime(^1), Type(^2)]`.
 433     pub fn make_identity<'a>(&self, tcx: TyCtxt<'a, 'tcx, 'tcx>) -> Self {
 434         use crate::ty::subst::UnpackedKind;
 435
 436         CanonicalVarValues {
 437             var_values: self.var_values.iter()
 438                 .zip(0..)
 439                 .map(|(kind, i)| match kind.unpack() {
 440                     UnpackedKind::Type(..) => tcx.mk_ty(
 441                         ty::Bound(ty::INNERMOST, ty::BoundVar::from_u32(i).into())
 442                     ).into(),
 443                     UnpackedKind::Lifetime(..) => tcx.mk_region(
 444                         ty::ReLateBound(ty::INNERMOST, ty::BoundRegion::BrAnon(i))
 445                     ).into(),
 446                     UnpackedKind::Const(..) => {
 447                         unimplemented!() // FIXME(const_generics)
 448                     }
 449                 })
 450                 .collect()
 451         }
 452     }
 453 }
 454
 455 impl<'a, 'tcx> IntoIterator for &'a CanonicalVarValues<'tcx> {
 456     type Item = Kind<'tcx>;
 457     type IntoIter = ::std::iter::Cloned<::std::slice::Iter<'a, Kind<'tcx>>>;
 458
 459     fn into_iter(self) -> Self::IntoIter {
 460         self.var_values.iter().cloned()
 461     }
 462 }
 463
 464 BraceStructLiftImpl! {
 465     impl<'a, 'tcx> Lift<'tcx> for CanonicalVarValues<'a> {
 466         type Lifted = CanonicalVarValues<'tcx>;
 467         var_values,
 468     }
 469 }
 470
 471 BraceStructTypeFoldableImpl! {
 472     impl<'tcx> TypeFoldable<'tcx> for CanonicalVarValues<'tcx> {
 473         var_values,
 474     }
 475 }
 476
 477 BraceStructTypeFoldableImpl! {
 478     impl<'tcx, R> TypeFoldable<'tcx> for QueryResponse<'tcx, R> {
 479         var_values, region_constraints, certainty, value
 480     } where R: TypeFoldable<'tcx>,
 481 }
 482
 483 BraceStructLiftImpl! {
 484     impl<'a, 'tcx, R> Lift<'tcx> for QueryResponse<'a, R> {
 485         type Lifted = QueryResponse<'tcx, R::Lifted>;
 486         var_values, region_constraints, certainty, value
 487     } where R: Lift<'tcx>
 488 }
 489
 490 impl<'tcx> Index<BoundVar> for CanonicalVarValues<'tcx> {
 491     type Output = Kind<'tcx>;
 492
 493     fn index(&self, value: BoundVar) -> &Kind<'tcx> {
 494         &self.var_values[value]
 495     }
 496 }