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