compiler/rustc_infer/src/infer/canonical/canonicalizer.rs

   1 //! This module contains the "canonicalizer" itself.
   2 //!
   3 //! For an overview of what canonicalization is and how it fits into
   4 //! rustc, check out the [chapter in the rustc dev guide][c].
   5 //!
   6 //! [c]: https://rust-lang.github.io/chalk/book/canonical_queries/canonicalization.html
   7
   8 use crate::infer::canonical::{
   9     Canonical, CanonicalTyVarKind, CanonicalVarInfo, CanonicalVarKind, Canonicalized,
  10     OriginalQueryValues,
  11 };
  12 use crate::infer::InferCtxt;
  13 use rustc_middle::ty::flags::FlagComputation;
  14 use rustc_middle::ty::fold::{TypeFoldable, TypeFolder};
  15 use rustc_middle::ty::subst::GenericArg;
  16 use rustc_middle::ty::{self, BoundVar, InferConst, List, Ty, TyCtxt, TypeFlags};
  17 use std::sync::atomic::Ordering;
  18
  19 use rustc_data_structures::fx::FxHashMap;
  20 use rustc_index::vec::Idx;
  21 use smallvec::SmallVec;
  22
  23 impl<'cx, 'tcx> InferCtxt<'cx, 'tcx> {
  24     /// Canonicalizes a query value `V`. When we canonicalize a query,
  25     /// we not only canonicalize unbound inference variables, but we
  26     /// *also* replace all free regions whatsoever. So for example a
  27     /// query like `T: Trait<'static>` would be canonicalized to
  28     ///
  29     /// ```text
  30     /// T: Trait<'?0>
  31     /// ```
  32     ///
  33     /// with a mapping M that maps `'?0` to `'static`.
  34     ///
  35     /// To get a good understanding of what is happening here, check
  36     /// out the [chapter in the rustc dev guide][c].
  37     ///
  38     /// [c]: https://rust-lang.github.io/chalk/book/canonical_queries/canonicalization.html#canonicalizing-the-query
  39     pub fn canonicalize_query<V>(
  40         &self,
  41         value: V,
  42         query_state: &mut OriginalQueryValues<'tcx>,
  43     ) -> Canonicalized<'tcx, V>
  44     where
  45         V: TypeFoldable<'tcx>,
  46     {
  47         self.tcx.sess.perf_stats.queries_canonicalized.fetch_add(1, Ordering::Relaxed);
  48
  49         Canonicalizer::canonicalize(value, self, self.tcx, &CanonicalizeAllFreeRegions, query_state)
  50     }
  51
  52     /// Like [Self::canonicalize_query], but preserves distinct universes. For
  53     /// example, canonicalizing `&'?0: Trait<'?1>`, where `'?0` is in `U1` and
  54     /// `'?1` is in `U3` would be canonicalized to have ?0` in `U1` and `'?1`
  55     /// in `U2`.
  56     ///
  57     /// This is used for Chalk integration.
  58     pub fn canonicalize_query_preserving_universes<V>(
  59         &self,
  60         value: V,
  61         query_state: &mut OriginalQueryValues<'tcx>,
  62     ) -> Canonicalized<'tcx, V>
  63     where
  64         V: TypeFoldable<'tcx>,
  65     {
  66         self.tcx.sess.perf_stats.queries_canonicalized.fetch_add(1, Ordering::Relaxed);
  67
  68         Canonicalizer::canonicalize(
  69             value,
  70             self,
  71             self.tcx,
  72             &CanonicalizeAllFreeRegionsPreservingUniverses,
  73             query_state,
  74         )
  75     }
  76
  77     /// Canonicalizes a query *response* `V`. When we canonicalize a
  78     /// query response, we only canonicalize unbound inference
  79     /// variables, and we leave other free regions alone. So,
  80     /// continuing with the example from `canonicalize_query`, if
  81     /// there was an input query `T: Trait<'static>`, it would have
  82     /// been canonicalized to
  83     ///
  84     /// ```text
  85     /// T: Trait<'?0>
  86     /// ```
  87     ///
  88     /// with a mapping M that maps `'?0` to `'static`. But if we found that there
  89     /// exists only one possible impl of `Trait`, and it looks like
  90     ///
  91     ///     impl<T> Trait<'static> for T { .. }
  92     ///
  93     /// then we would prepare a query result R that (among other
  94     /// things) includes a mapping to `'?0 := 'static`. When
  95     /// canonicalizing this query result R, we would leave this
  96     /// reference to `'static` alone.
  97     ///
  98     /// To get a good understanding of what is happening here, check
  99     /// out the [chapter in the rustc dev guide][c].
 100     ///
 101     /// [c]: https://rust-lang.github.io/chalk/book/canonical_queries/canonicalization.html#canonicalizing-the-query-result
 102     pub fn canonicalize_response<V>(&self, value: V) -> Canonicalized<'tcx, V>
 103     where
 104         V: TypeFoldable<'tcx>,
 105     {
 106         let mut query_state = OriginalQueryValues::default();
 107         Canonicalizer::canonicalize(
 108             value,
 109             self,
 110             self.tcx,
 111             &CanonicalizeQueryResponse,
 112             &mut query_state,
 113         )
 114     }
 115
 116     pub fn canonicalize_user_type_annotation<V>(&self, value: V) -> Canonicalized<'tcx, V>
 117     where
 118         V: TypeFoldable<'tcx>,
 119     {
 120         let mut query_state = OriginalQueryValues::default();
 121         Canonicalizer::canonicalize(
 122             value,
 123             self,
 124             self.tcx,
 125             &CanonicalizeUserTypeAnnotation,
 126             &mut query_state,
 127         )
 128     }
 129
 130     /// A variant of `canonicalize_query` that does not
 131     /// canonicalize `'static`. This is useful when
 132     /// the query implementation can perform more efficient
 133     /// handling of `'static` regions (e.g. trait evaluation).
 134     pub fn canonicalize_query_keep_static<V>(
 135         &self,
 136         value: V,
 137         query_state: &mut OriginalQueryValues<'tcx>,
 138     ) -> Canonicalized<'tcx, V>
 139     where
 140         V: TypeFoldable<'tcx>,
 141     {
 142         self.tcx.sess.perf_stats.queries_canonicalized.fetch_add(1, Ordering::Relaxed);
 143
 144         Canonicalizer::canonicalize(
 145             value,
 146             self,
 147             self.tcx,
 148             &CanonicalizeFreeRegionsOtherThanStatic,
 149             query_state,
 150         )
 151     }
 152 }
 153
 154 /// Controls how we canonicalize "free regions" that are not inference
 155 /// variables. This depends on what we are canonicalizing *for* --
 156 /// e.g., if we are canonicalizing to create a query, we want to
 157 /// replace those with inference variables, since we want to make a
 158 /// maximally general query. But if we are canonicalizing a *query
 159 /// response*, then we don't typically replace free regions, as they
 160 /// must have been introduced from other parts of the system.
 161 trait CanonicalizeMode {
 162     fn canonicalize_free_region<'tcx>(
 163         &self,
 164         canonicalizer: &mut Canonicalizer<'_, 'tcx>,
 165         r: ty::Region<'tcx>,
 166     ) -> ty::Region<'tcx>;
 167
 168     fn any(&self) -> bool;
 169
 170     // Do we preserve universe of variables.
 171     fn preserve_universes(&self) -> bool;
 172 }
 173
 174 struct CanonicalizeQueryResponse;
 175
 176 impl CanonicalizeMode for CanonicalizeQueryResponse {
 177     fn canonicalize_free_region<'tcx>(
 178         &self,
 179         canonicalizer: &mut Canonicalizer<'_, 'tcx>,
 180         r: ty::Region<'tcx>,
 181     ) -> ty::Region<'tcx> {
 182         match *r {
 183             ty::ReFree(_)
 184             | ty::ReErased
 185             | ty::ReStatic
 186             | ty::ReEmpty(ty::UniverseIndex::ROOT)
 187             | ty::ReEarlyBound(..) => r,
 188
 189             ty::RePlaceholder(placeholder) => canonicalizer.canonical_var_for_region(
 190                 CanonicalVarInfo { kind: CanonicalVarKind::PlaceholderRegion(placeholder) },
 191                 r,
 192             ),
 193
 194             ty::ReVar(vid) => {
 195                 let universe = canonicalizer.region_var_universe(vid);
 196                 canonicalizer.canonical_var_for_region(
 197                     CanonicalVarInfo { kind: CanonicalVarKind::Region(universe) },
 198                     r,
 199                 )
 200             }
 201
 202             ty::ReEmpty(ui) => {
 203                 bug!("canonicalizing 'empty in universe {:?}", ui) // FIXME
 204             }
 205
 206             _ => {
 207                 // Other than `'static` or `'empty`, the query
 208                 // response should be executing in a fully
 209                 // canonicalized environment, so there shouldn't be
 210                 // any other region names it can come up.
 211                 //
 212                 // rust-lang/rust#57464: `impl Trait` can leak local
 213                 // scopes (in manner violating typeck). Therefore, use
 214                 // `delay_span_bug` to allow type error over an ICE.
 215                 ty::tls::with(|tcx| {
 216                     tcx.sess.delay_span_bug(
 217                         rustc_span::DUMMY_SP,
 218                         &format!("unexpected region in query response: `{:?}`", r),
 219                     );
 220                 });
 221                 r
 222             }
 223         }
 224     }
 225
 226     fn any(&self) -> bool {
 227         false
 228     }
 229
 230     fn preserve_universes(&self) -> bool {
 231         true
 232     }
 233 }
 234
 235 struct CanonicalizeUserTypeAnnotation;
 236
 237 impl CanonicalizeMode for CanonicalizeUserTypeAnnotation {
 238     fn canonicalize_free_region<'tcx>(
 239         &self,
 240         canonicalizer: &mut Canonicalizer<'_, 'tcx>,
 241         r: ty::Region<'tcx>,
 242     ) -> ty::Region<'tcx> {
 243         match *r {
 244             ty::ReEarlyBound(_) | ty::ReFree(_) | ty::ReErased | ty::ReStatic => r,
 245             ty::ReVar(_) => canonicalizer.canonical_var_for_region_in_root_universe(r),
 246             _ => {
 247                 // We only expect region names that the user can type.
 248                 bug!("unexpected region in query response: `{:?}`", r)
 249             }
 250         }
 251     }
 252
 253     fn any(&self) -> bool {
 254         false
 255     }
 256
 257     fn preserve_universes(&self) -> bool {
 258         false
 259     }
 260 }
 261
 262 struct CanonicalizeAllFreeRegions;
 263
 264 impl CanonicalizeMode for CanonicalizeAllFreeRegions {
 265     fn canonicalize_free_region<'tcx>(
 266         &self,
 267         canonicalizer: &mut Canonicalizer<'_, 'tcx>,
 268         r: ty::Region<'tcx>,
 269     ) -> ty::Region<'tcx> {
 270         canonicalizer.canonical_var_for_region_in_root_universe(r)
 271     }
 272
 273     fn any(&self) -> bool {
 274         true
 275     }
 276
 277     fn preserve_universes(&self) -> bool {
 278         false
 279     }
 280 }
 281
 282 struct CanonicalizeAllFreeRegionsPreservingUniverses;
 283
 284 impl CanonicalizeMode for CanonicalizeAllFreeRegionsPreservingUniverses {
 285     fn canonicalize_free_region<'tcx>(
 286         &self,
 287         canonicalizer: &mut Canonicalizer<'_, 'tcx>,
 288         r: ty::Region<'tcx>,
 289     ) -> ty::Region<'tcx> {
 290         let universe = canonicalizer.infcx.universe_of_region(r);
 291         canonicalizer.canonical_var_for_region(
 292             CanonicalVarInfo { kind: CanonicalVarKind::Region(universe) },
 293             r,
 294         )
 295     }
 296
 297     fn any(&self) -> bool {
 298         true
 299     }
 300
 301     fn preserve_universes(&self) -> bool {
 302         true
 303     }
 304 }
 305
 306 struct CanonicalizeFreeRegionsOtherThanStatic;
 307
 308 impl CanonicalizeMode for CanonicalizeFreeRegionsOtherThanStatic {
 309     fn canonicalize_free_region<'tcx>(
 310         &self,
 311         canonicalizer: &mut Canonicalizer<'_, 'tcx>,
 312         r: ty::Region<'tcx>,
 313     ) -> ty::Region<'tcx> {
 314         if r.is_static() { r } else { canonicalizer.canonical_var_for_region_in_root_universe(r) }
 315     }
 316
 317     fn any(&self) -> bool {
 318         true
 319     }
 320
 321     fn preserve_universes(&self) -> bool {
 322         false
 323     }
 324 }
 325
 326 struct Canonicalizer<'cx, 'tcx> {
 327     infcx: &'cx InferCtxt<'cx, 'tcx>,
 328     tcx: TyCtxt<'tcx>,
 329     variables: SmallVec<[CanonicalVarInfo<'tcx>; 8]>,
 330     query_state: &'cx mut OriginalQueryValues<'tcx>,
 331     // Note that indices is only used once `var_values` is big enough to be
 332     // heap-allocated.
 333     indices: FxHashMap<GenericArg<'tcx>, BoundVar>,
 334     canonicalize_mode: &'cx dyn CanonicalizeMode,
 335     needs_canonical_flags: TypeFlags,
 336
 337     binder_index: ty::DebruijnIndex,
 338 }
 339
 340 impl<'cx, 'tcx> TypeFolder<'tcx> for Canonicalizer<'cx, 'tcx> {
 341     fn tcx<'b>(&'b self) -> TyCtxt<'tcx> {
 342         self.tcx
 343     }
 344
 345     fn fold_binder<T>(&mut self, t: ty::Binder<'tcx, T>) -> ty::Binder<'tcx, T>
 346     where
 347         T: TypeFoldable<'tcx>,
 348     {
 349         self.binder_index.shift_in(1);
 350         let t = t.super_fold_with(self);
 351         self.binder_index.shift_out(1);
 352         t
 353     }
 354
 355     fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
 356         match *r {
 357             ty::ReLateBound(index, ..) => {
 358                 if index >= self.binder_index {
 359                     bug!("escaping late-bound region during canonicalization");
 360                 } else {
 361                     r
 362                 }
 363             }
 364
 365             ty::ReVar(vid) => {
 366                 let resolved_vid = self
 367                     .infcx
 368                     .inner
 369                     .borrow_mut()
 370                     .unwrap_region_constraints()
 371                     .opportunistic_resolve_var(vid);
 372                 debug!(
 373                     "canonical: region var found with vid {:?}, \
 374                      opportunistically resolved to {:?}",
 375                     vid, r
 376                 );
 377                 let r = self.tcx.reuse_or_mk_region(r, ty::ReVar(resolved_vid));
 378                 self.canonicalize_mode.canonicalize_free_region(self, r)
 379             }
 380
 381             ty::ReStatic
 382             | ty::ReEarlyBound(..)
 383             | ty::ReFree(_)
 384             | ty::ReEmpty(_)
 385             | ty::RePlaceholder(..)
 386             | ty::ReErased => self.canonicalize_mode.canonicalize_free_region(self, r),
 387         }
 388     }
 389
 390     fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
 391         match *t.kind() {
 392             ty::Infer(ty::TyVar(vid)) => {
 393                 debug!("canonical: type var found with vid {:?}", vid);
 394                 match self.infcx.probe_ty_var(vid) {
 395                     // `t` could be a float / int variable; canonicalize that instead.
 396                     Ok(t) => {
 397                         debug!("(resolved to {:?})", t);
 398                         self.fold_ty(t)
 399                     }
 400
 401                     // `TyVar(vid)` is unresolved, track its universe index in the canonicalized
 402                     // result.
 403                     Err(mut ui) => {
 404                         if !self.canonicalize_mode.preserve_universes() {
 405                             // FIXME: perf problem described in #55921.
 406                             ui = ty::UniverseIndex::ROOT;
 407                         }
 408                         self.canonicalize_ty_var(
 409                             CanonicalVarInfo {
 410                                 kind: CanonicalVarKind::Ty(CanonicalTyVarKind::General(ui)),
 411                             },
 412                             t,
 413                         )
 414                     }
 415                 }
 416             }
 417
 418             ty::Infer(ty::IntVar(_)) => self.canonicalize_ty_var(
 419                 CanonicalVarInfo { kind: CanonicalVarKind::Ty(CanonicalTyVarKind::Int) },
 420                 t,
 421             ),
 422
 423             ty::Infer(ty::FloatVar(_)) => self.canonicalize_ty_var(
 424                 CanonicalVarInfo { kind: CanonicalVarKind::Ty(CanonicalTyVarKind::Float) },
 425                 t,
 426             ),
 427
 428             ty::Infer(ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => {
 429                 bug!("encountered a fresh type during canonicalization")
 430             }
 431
 432             ty::Placeholder(placeholder) => self.canonicalize_ty_var(
 433                 CanonicalVarInfo { kind: CanonicalVarKind::PlaceholderTy(placeholder) },
 434                 t,
 435             ),
 436
 437             ty::Bound(debruijn, _) => {
 438                 if debruijn >= self.binder_index {
 439                     bug!("escaping bound type during canonicalization")
 440                 } else {
 441                     t
 442                 }
 443             }
 444
 445             ty::Closure(..)
 446             | ty::Generator(..)
 447             | ty::GeneratorWitness(..)
 448             | ty::Bool
 449             | ty::Char
 450             | ty::Int(..)
 451             | ty::Uint(..)
 452             | ty::Float(..)
 453             | ty::Adt(..)
 454             | ty::Str
 455             | ty::Error(_)
 456             | ty::Array(..)
 457             | ty::Slice(..)
 458             | ty::RawPtr(..)
 459             | ty::Ref(..)
 460             | ty::FnDef(..)
 461             | ty::FnPtr(_)
 462             | ty::Dynamic(..)
 463             | ty::Never
 464             | ty::Tuple(..)
 465             | ty::Projection(..)
 466             | ty::Foreign(..)
 467             | ty::Param(..)
 468             | ty::Opaque(..) => {
 469                 if t.flags().intersects(self.needs_canonical_flags) {
 470                     t.super_fold_with(self)
 471                 } else {
 472                     t
 473                 }
 474             }
 475         }
 476     }
 477
 478     fn fold_const(&mut self, ct: ty::Const<'tcx>) -> ty::Const<'tcx> {
 479         match ct.val() {
 480             ty::ConstKind::Infer(InferConst::Var(vid)) => {
 481                 debug!("canonical: const var found with vid {:?}", vid);
 482                 match self.infcx.probe_const_var(vid) {
 483                     Ok(c) => {
 484                         debug!("(resolved to {:?})", c);
 485                         return self.fold_const(c);
 486                     }
 487
 488                     // `ConstVar(vid)` is unresolved, track its universe index in the
 489                     // canonicalized result
 490                     Err(mut ui) => {
 491                         if !self.canonicalize_mode.preserve_universes() {
 492                             // FIXME: perf problem described in #55921.
 493                             ui = ty::UniverseIndex::ROOT;
 494                         }
 495                         return self.canonicalize_const_var(
 496                             CanonicalVarInfo { kind: CanonicalVarKind::Const(ui, ct.ty()) },
 497                             ct,
 498                         );
 499                     }
 500                 }
 501             }
 502             ty::ConstKind::Infer(InferConst::Fresh(_)) => {
 503                 bug!("encountered a fresh const during canonicalization")
 504             }
 505             ty::ConstKind::Bound(debruijn, _) => {
 506                 if debruijn >= self.binder_index {
 507                     bug!("escaping bound type during canonicalization")
 508                 } else {
 509                     return ct;
 510                 }
 511             }
 512             ty::ConstKind::Placeholder(placeholder) => {
 513                 return self.canonicalize_const_var(
 514                     CanonicalVarInfo { kind: CanonicalVarKind::PlaceholderConst(placeholder) },
 515                     ct,
 516                 );
 517             }
 518             _ => {}
 519         }
 520
 521         let flags = FlagComputation::for_const(ct);
 522         if flags.intersects(self.needs_canonical_flags) { ct.super_fold_with(self) } else { ct }
 523     }
 524 }
 525
 526 impl<'cx, 'tcx> Canonicalizer<'cx, 'tcx> {
 527     /// The main `canonicalize` method, shared impl of
 528     /// `canonicalize_query` and `canonicalize_response`.
 529     fn canonicalize<V>(
 530         value: V,
 531         infcx: &InferCtxt<'_, 'tcx>,
 532         tcx: TyCtxt<'tcx>,
 533         canonicalize_region_mode: &dyn CanonicalizeMode,
 534         query_state: &mut OriginalQueryValues<'tcx>,
 535     ) -> Canonicalized<'tcx, V>
 536     where
 537         V: TypeFoldable<'tcx>,
 538     {
 539         let needs_canonical_flags = if canonicalize_region_mode.any() {
 540             TypeFlags::NEEDS_INFER |
 541             TypeFlags::HAS_FREE_REGIONS | // `HAS_RE_PLACEHOLDER` implies `HAS_FREE_REGIONS`
 542             TypeFlags::HAS_TY_PLACEHOLDER |
 543             TypeFlags::HAS_CT_PLACEHOLDER
 544         } else {
 545             TypeFlags::NEEDS_INFER
 546                 | TypeFlags::HAS_RE_PLACEHOLDER
 547                 | TypeFlags::HAS_TY_PLACEHOLDER
 548                 | TypeFlags::HAS_CT_PLACEHOLDER
 549         };
 550
 551         // Fast path: nothing that needs to be canonicalized.
 552         if !value.has_type_flags(needs_canonical_flags) {
 553             let canon_value = Canonical {
 554                 max_universe: ty::UniverseIndex::ROOT,
 555                 variables: List::empty(),
 556                 value,
 557             };
 558             return canon_value;
 559         }
 560
 561         let mut canonicalizer = Canonicalizer {
 562             infcx,
 563             tcx,
 564             canonicalize_mode: canonicalize_region_mode,
 565             needs_canonical_flags,
 566             variables: SmallVec::new(),
 567             query_state,
 568             indices: FxHashMap::default(),
 569             binder_index: ty::INNERMOST,
 570         };
 571         let out_value = value.fold_with(&mut canonicalizer);
 572
 573         // Once we have canonicalized `out_value`, it should not
 574         // contain anything that ties it to this inference context
 575         // anymore.
 576         debug_assert!(!out_value.needs_infer() && !out_value.has_placeholders());
 577
 578         let canonical_variables =
 579             tcx.intern_canonical_var_infos(&canonicalizer.universe_canonicalized_variables());
 580
 581         let max_universe = canonical_variables
 582             .iter()
 583             .map(|cvar| cvar.universe())
 584             .max()
 585             .unwrap_or(ty::UniverseIndex::ROOT);
 586
 587         Canonical { max_universe, variables: canonical_variables, value: out_value }
 588     }
 589
 590     /// Creates a canonical variable replacing `kind` from the input,
 591     /// or returns an existing variable if `kind` has already been
 592     /// seen. `kind` is expected to be an unbound variable (or
 593     /// potentially a free region).
 594     fn canonical_var(&mut self, info: CanonicalVarInfo<'tcx>, kind: GenericArg<'tcx>) -> BoundVar {
 595         let Canonicalizer { variables, query_state, indices, .. } = self;
 596
 597         let var_values = &mut query_state.var_values;
 598
 599         let universe = info.universe();
 600         if universe != ty::UniverseIndex::ROOT {
 601             assert!(self.canonicalize_mode.preserve_universes());
 602
 603             // Insert universe into the universe map. To preserve the order of the
 604             // universes in the value being canonicalized, we don't update the
 605             // universe in `info` until we have finished canonicalizing.
 606             match query_state.universe_map.binary_search(&universe) {
 607                 Err(idx) => query_state.universe_map.insert(idx, universe),
 608                 Ok(_) => {}
 609             }
 610         }
 611
 612         // This code is hot. `variables` and `var_values` are usually small
 613         // (fewer than 8 elements ~95% of the time). They are SmallVec's to
 614         // avoid allocations in those cases. We also don't use `indices` to
 615         // determine if a kind has been seen before until the limit of 8 has
 616         // been exceeded, to also avoid allocations for `indices`.
 617         if !var_values.spilled() {
 618             // `var_values` is stack-allocated. `indices` isn't used yet. Do a
 619             // direct linear search of `var_values`.
 620             if let Some(idx) = var_values.iter().position(|&k| k == kind) {
 621                 // `kind` is already present in `var_values`.
 622                 BoundVar::new(idx)
 623             } else {
 624                 // `kind` isn't present in `var_values`. Append it. Likewise
 625                 // for `info` and `variables`.
 626                 variables.push(info);
 627                 var_values.push(kind);
 628                 assert_eq!(variables.len(), var_values.len());
 629
 630                 // If `var_values` has become big enough to be heap-allocated,
 631                 // fill up `indices` to facilitate subsequent lookups.
 632                 if var_values.spilled() {
 633                     assert!(indices.is_empty());
 634                     *indices = var_values
 635                         .iter()
 636                         .enumerate()
 637                         .map(|(i, &kind)| (kind, BoundVar::new(i)))
 638                         .collect();
 639                 }
 640                 // The cv is the index of the appended element.
 641                 BoundVar::new(var_values.len() - 1)
 642             }
 643         } else {
 644             // `var_values` is large. Do a hashmap search via `indices`.
 645             *indices.entry(kind).or_insert_with(|| {
 646                 variables.push(info);
 647                 var_values.push(kind);
 648                 assert_eq!(variables.len(), var_values.len());
 649                 BoundVar::new(variables.len() - 1)
 650             })
 651         }
 652     }
 653
 654     /// Replaces the universe indexes used in `var_values` with their index in
 655     /// `query_state.universe_map`. This minimizes the maximum universe used in
 656     /// the canonicalized value.
 657     fn universe_canonicalized_variables(self) -> SmallVec<[CanonicalVarInfo<'tcx>; 8]> {
 658         if self.query_state.universe_map.len() == 1 {
 659             return self.variables;
 660         }
 661
 662         let reverse_universe_map: FxHashMap<ty::UniverseIndex, ty::UniverseIndex> = self
 663             .query_state
 664             .universe_map
 665             .iter()
 666             .enumerate()
 667             .map(|(idx, universe)| (*universe, ty::UniverseIndex::from_usize(idx)))
 668             .collect();
 669
 670         self.variables
 671             .iter()
 672             .map(|v| CanonicalVarInfo {
 673                 kind: match v.kind {
 674                     CanonicalVarKind::Ty(CanonicalTyVarKind::Int | CanonicalTyVarKind::Float) => {
 675                         return *v;
 676                     }
 677                     CanonicalVarKind::Ty(CanonicalTyVarKind::General(u)) => {
 678                         CanonicalVarKind::Ty(CanonicalTyVarKind::General(reverse_universe_map[&u]))
 679                     }
 680                     CanonicalVarKind::Region(u) => {
 681                         CanonicalVarKind::Region(reverse_universe_map[&u])
 682                     }
 683                     CanonicalVarKind::Const(u, t) => {
 684                         CanonicalVarKind::Const(reverse_universe_map[&u], t)
 685                     }
 686                     CanonicalVarKind::PlaceholderTy(placeholder) => {
 687                         CanonicalVarKind::PlaceholderTy(ty::Placeholder {
 688                             universe: reverse_universe_map[&placeholder.universe],
 689                             ..placeholder
 690                         })
 691                     }
 692                     CanonicalVarKind::PlaceholderRegion(placeholder) => {
 693                         CanonicalVarKind::PlaceholderRegion(ty::Placeholder {
 694                             universe: reverse_universe_map[&placeholder.universe],
 695                             ..placeholder
 696                         })
 697                     }
 698                     CanonicalVarKind::PlaceholderConst(placeholder) => {
 699                         CanonicalVarKind::PlaceholderConst(ty::Placeholder {
 700                             universe: reverse_universe_map[&placeholder.universe],
 701                             ..placeholder
 702                         })
 703                     }
 704                 },
 705             })
 706             .collect()
 707     }
 708
 709     /// Shorthand helper that creates a canonical region variable for
 710     /// `r` (always in the root universe). The reason that we always
 711     /// put these variables into the root universe is because this
 712     /// method is used during **query construction:** in that case, we
 713     /// are taking all the regions and just putting them into the most
 714     /// generic context we can. This may generate solutions that don't
 715     /// fit (e.g., that equate some region variable with a placeholder
 716     /// it can't name) on the caller side, but that's ok, the caller
 717     /// can figure that out. In the meantime, it maximizes our
 718     /// caching.
 719     ///
 720     /// (This works because unification never fails -- and hence trait
 721     /// selection is never affected -- due to a universe mismatch.)
 722     fn canonical_var_for_region_in_root_universe(
 723         &mut self,
 724         r: ty::Region<'tcx>,
 725     ) -> ty::Region<'tcx> {
 726         self.canonical_var_for_region(
 727             CanonicalVarInfo { kind: CanonicalVarKind::Region(ty::UniverseIndex::ROOT) },
 728             r,
 729         )
 730     }
 731
 732     /// Returns the universe in which `vid` is defined.
 733     fn region_var_universe(&self, vid: ty::RegionVid) -> ty::UniverseIndex {
 734         self.infcx.inner.borrow_mut().unwrap_region_constraints().var_universe(vid)
 735     }
 736
 737     /// Creates a canonical variable (with the given `info`)
 738     /// representing the region `r`; return a region referencing it.
 739     fn canonical_var_for_region(
 740         &mut self,
 741         info: CanonicalVarInfo<'tcx>,
 742         r: ty::Region<'tcx>,
 743     ) -> ty::Region<'tcx> {
 744         let var = self.canonical_var(info, r.into());
 745         let br = ty::BoundRegion { var, kind: ty::BrAnon(var.as_u32()) };
 746         let region = ty::ReLateBound(self.binder_index, br);
 747         self.tcx().mk_region(region)
 748     }
 749
 750     /// Given a type variable `ty_var` of the given kind, first check
 751     /// if `ty_var` is bound to anything; if so, canonicalize
 752     /// *that*. Otherwise, create a new canonical variable for
 753     /// `ty_var`.
 754     fn canonicalize_ty_var(&mut self, info: CanonicalVarInfo<'tcx>, ty_var: Ty<'tcx>) -> Ty<'tcx> {
 755         let infcx = self.infcx;
 756         let bound_to = infcx.shallow_resolve(ty_var);
 757         if bound_to != ty_var {
 758             self.fold_ty(bound_to)
 759         } else {
 760             let var = self.canonical_var(info, ty_var.into());
 761             self.tcx().mk_ty(ty::Bound(self.binder_index, var.into()))
 762         }
 763     }
 764
 765     /// Given a type variable `const_var` of the given kind, first check
 766     /// if `const_var` is bound to anything; if so, canonicalize
 767     /// *that*. Otherwise, create a new canonical variable for
 768     /// `const_var`.
 769     fn canonicalize_const_var(
 770         &mut self,
 771         info: CanonicalVarInfo<'tcx>,
 772         const_var: ty::Const<'tcx>,
 773     ) -> ty::Const<'tcx> {
 774         let infcx = self.infcx;
 775         let bound_to = infcx.shallow_resolve(const_var);
 776         if bound_to != const_var {
 777             self.fold_const(bound_to)
 778         } else {
 779             let var = self.canonical_var(info, const_var.into());
 780             self.tcx().mk_const(ty::ConstS {
 781                 val: ty::ConstKind::Bound(self.binder_index, var),
 782                 ty: self.fold_ty(const_var.ty()),
 783             })
 784         }
 785     }
 786 }