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