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, TypeSuperFoldable};
  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<'tcx> InferCtxt<'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     /// ```ignore (illustrative)
  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(_) | ty::ReErased | ty::ReStatic | ty::ReEarlyBound(..) => r,
 184
 185             ty::RePlaceholder(placeholder) => canonicalizer.canonical_var_for_region(
 186                 CanonicalVarInfo { kind: CanonicalVarKind::PlaceholderRegion(placeholder) },
 187                 r,
 188             ),
 189
 190             ty::ReVar(vid) => {
 191                 let universe = canonicalizer.region_var_universe(vid);
 192                 canonicalizer.canonical_var_for_region(
 193                     CanonicalVarInfo { kind: CanonicalVarKind::Region(universe) },
 194                     r,
 195                 )
 196             }
 197
 198             _ => {
 199                 // Other than `'static` or `'empty`, the query
 200                 // response should be executing in a fully
 201                 // canonicalized environment, so there shouldn't be
 202                 // any other region names it can come up.
 203                 //
 204                 // rust-lang/rust#57464: `impl Trait` can leak local
 205                 // scopes (in manner violating typeck). Therefore, use
 206                 // `delay_span_bug` to allow type error over an ICE.
 207                 ty::tls::with(|tcx| {
 208                     tcx.sess.delay_span_bug(
 209                         rustc_span::DUMMY_SP,
 210                         &format!("unexpected region in query response: `{:?}`", r),
 211                     );
 212                 });
 213                 r
 214             }
 215         }
 216     }
 217
 218     fn any(&self) -> bool {
 219         false
 220     }
 221
 222     fn preserve_universes(&self) -> bool {
 223         true
 224     }
 225 }
 226
 227 struct CanonicalizeUserTypeAnnotation;
 228
 229 impl CanonicalizeMode for CanonicalizeUserTypeAnnotation {
 230     fn canonicalize_free_region<'tcx>(
 231         &self,
 232         canonicalizer: &mut Canonicalizer<'_, 'tcx>,
 233         r: ty::Region<'tcx>,
 234     ) -> ty::Region<'tcx> {
 235         match *r {
 236             ty::ReEarlyBound(_) | ty::ReFree(_) | ty::ReErased | ty::ReStatic => r,
 237             ty::ReVar(_) => canonicalizer.canonical_var_for_region_in_root_universe(r),
 238             _ => {
 239                 // We only expect region names that the user can type.
 240                 bug!("unexpected region in query response: `{:?}`", r)
 241             }
 242         }
 243     }
 244
 245     fn any(&self) -> bool {
 246         false
 247     }
 248
 249     fn preserve_universes(&self) -> bool {
 250         false
 251     }
 252 }
 253
 254 struct CanonicalizeAllFreeRegions;
 255
 256 impl CanonicalizeMode for CanonicalizeAllFreeRegions {
 257     fn canonicalize_free_region<'tcx>(
 258         &self,
 259         canonicalizer: &mut Canonicalizer<'_, 'tcx>,
 260         r: ty::Region<'tcx>,
 261     ) -> ty::Region<'tcx> {
 262         canonicalizer.canonical_var_for_region_in_root_universe(r)
 263     }
 264
 265     fn any(&self) -> bool {
 266         true
 267     }
 268
 269     fn preserve_universes(&self) -> bool {
 270         false
 271     }
 272 }
 273
 274 struct CanonicalizeAllFreeRegionsPreservingUniverses;
 275
 276 impl CanonicalizeMode for CanonicalizeAllFreeRegionsPreservingUniverses {
 277     fn canonicalize_free_region<'tcx>(
 278         &self,
 279         canonicalizer: &mut Canonicalizer<'_, 'tcx>,
 280         r: ty::Region<'tcx>,
 281     ) -> ty::Region<'tcx> {
 282         let universe = canonicalizer.infcx.universe_of_region(r);
 283         canonicalizer.canonical_var_for_region(
 284             CanonicalVarInfo { kind: CanonicalVarKind::Region(universe) },
 285             r,
 286         )
 287     }
 288
 289     fn any(&self) -> bool {
 290         true
 291     }
 292
 293     fn preserve_universes(&self) -> bool {
 294         true
 295     }
 296 }
 297
 298 struct CanonicalizeFreeRegionsOtherThanStatic;
 299
 300 impl CanonicalizeMode for CanonicalizeFreeRegionsOtherThanStatic {
 301     fn canonicalize_free_region<'tcx>(
 302         &self,
 303         canonicalizer: &mut Canonicalizer<'_, 'tcx>,
 304         r: ty::Region<'tcx>,
 305     ) -> ty::Region<'tcx> {
 306         if r.is_static() { r } else { canonicalizer.canonical_var_for_region_in_root_universe(r) }
 307     }
 308
 309     fn any(&self) -> bool {
 310         true
 311     }
 312
 313     fn preserve_universes(&self) -> bool {
 314         false
 315     }
 316 }
 317
 318 struct Canonicalizer<'cx, 'tcx> {
 319     infcx: &'cx InferCtxt<'tcx>,
 320     tcx: TyCtxt<'tcx>,
 321     variables: SmallVec<[CanonicalVarInfo<'tcx>; 8]>,
 322     query_state: &'cx mut OriginalQueryValues<'tcx>,
 323     // Note that indices is only used once `var_values` is big enough to be
 324     // heap-allocated.
 325     indices: FxHashMap<GenericArg<'tcx>, BoundVar>,
 326     canonicalize_mode: &'cx dyn CanonicalizeMode,
 327     needs_canonical_flags: TypeFlags,
 328
 329     binder_index: ty::DebruijnIndex,
 330 }
 331
 332 impl<'cx, 'tcx> TypeFolder<'tcx> for Canonicalizer<'cx, 'tcx> {
 333     fn tcx<'b>(&'b self) -> TyCtxt<'tcx> {
 334         self.tcx
 335     }
 336
 337     fn fold_binder<T>(&mut self, t: ty::Binder<'tcx, T>) -> ty::Binder<'tcx, T>
 338     where
 339         T: TypeFoldable<'tcx>,
 340     {
 341         self.binder_index.shift_in(1);
 342         let t = t.super_fold_with(self);
 343         self.binder_index.shift_out(1);
 344         t
 345     }
 346
 347     fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
 348         match *r {
 349             ty::ReLateBound(index, ..) => {
 350                 if index >= self.binder_index {
 351                     bug!("escaping late-bound region during canonicalization");
 352                 } else {
 353                     r
 354                 }
 355             }
 356
 357             ty::ReVar(vid) => {
 358                 let resolved_vid = self
 359                     .infcx
 360                     .inner
 361                     .borrow_mut()
 362                     .unwrap_region_constraints()
 363                     .opportunistic_resolve_var(vid);
 364                 debug!(
 365                     "canonical: region var found with vid {:?}, \
 366                      opportunistically resolved to {:?}",
 367                     vid, resolved_vid
 368                 );
 369                 let r = self.tcx.reuse_or_mk_region(r, ty::ReVar(resolved_vid));
 370                 self.canonicalize_mode.canonicalize_free_region(self, r)
 371             }
 372
 373             ty::ReStatic
 374             | ty::ReEarlyBound(..)
 375             | ty::ReFree(_)
 376             | ty::RePlaceholder(..)
 377             | ty::ReErased => self.canonicalize_mode.canonicalize_free_region(self, r),
 378         }
 379     }
 380
 381     fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
 382         match *t.kind() {
 383             ty::Infer(ty::TyVar(vid)) => {
 384                 debug!("canonical: type var found with vid {:?}", vid);
 385                 match self.infcx.probe_ty_var(vid) {
 386                     // `t` could be a float / int variable; canonicalize that instead.
 387                     Ok(t) => {
 388                         debug!("(resolved to {:?})", t);
 389                         self.fold_ty(t)
 390                     }
 391
 392                     // `TyVar(vid)` is unresolved, track its universe index in the canonicalized
 393                     // result.
 394                     Err(mut ui) => {
 395                         if !self.canonicalize_mode.preserve_universes() {
 396                             // FIXME: perf problem described in #55921.
 397                             ui = ty::UniverseIndex::ROOT;
 398                         }
 399                         self.canonicalize_ty_var(
 400                             CanonicalVarInfo {
 401                                 kind: CanonicalVarKind::Ty(CanonicalTyVarKind::General(ui)),
 402                             },
 403                             t,
 404                         )
 405                     }
 406                 }
 407             }
 408
 409             ty::Infer(ty::IntVar(_)) => self.canonicalize_ty_var(
 410                 CanonicalVarInfo { kind: CanonicalVarKind::Ty(CanonicalTyVarKind::Int) },
 411                 t,
 412             ),
 413
 414             ty::Infer(ty::FloatVar(_)) => self.canonicalize_ty_var(
 415                 CanonicalVarInfo { kind: CanonicalVarKind::Ty(CanonicalTyVarKind::Float) },
 416                 t,
 417             ),
 418
 419             ty::Infer(ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => {
 420                 bug!("encountered a fresh type during canonicalization")
 421             }
 422
 423             ty::Placeholder(placeholder) => self.canonicalize_ty_var(
 424                 CanonicalVarInfo { kind: CanonicalVarKind::PlaceholderTy(placeholder) },
 425                 t,
 426             ),
 427
 428             ty::Bound(debruijn, _) => {
 429                 if debruijn >= self.binder_index {
 430                     bug!("escaping bound type during canonicalization")
 431                 } else {
 432                     t
 433                 }
 434             }
 435
 436             ty::Closure(..)
 437             | ty::Generator(..)
 438             | ty::GeneratorWitness(..)
 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::Projection(..)
 457             | ty::Foreign(..)
 458             | ty::Param(..)
 459             | ty::Opaque(..) => {
 460                 if t.flags().intersects(self.needs_canonical_flags) {
 461                     t.super_fold_with(self)
 462                 } else {
 463                     t
 464                 }
 465             }
 466         }
 467     }
 468
 469     fn fold_const(&mut self, ct: ty::Const<'tcx>) -> ty::Const<'tcx> {
 470         match ct.kind() {
 471             ty::ConstKind::Infer(InferConst::Var(vid)) => {
 472                 debug!("canonical: const var found with vid {:?}", vid);
 473                 match self.infcx.probe_const_var(vid) {
 474                     Ok(c) => {
 475                         debug!("(resolved to {:?})", c);
 476                         return self.fold_const(c);
 477                     }
 478
 479                     // `ConstVar(vid)` is unresolved, track its universe index in the
 480                     // canonicalized result
 481                     Err(mut ui) => {
 482                         if !self.canonicalize_mode.preserve_universes() {
 483                             // FIXME: perf problem described in #55921.
 484                             ui = ty::UniverseIndex::ROOT;
 485                         }
 486                         return self.canonicalize_const_var(
 487                             CanonicalVarInfo { kind: CanonicalVarKind::Const(ui, ct.ty()) },
 488                             ct,
 489                         );
 490                     }
 491                 }
 492             }
 493             ty::ConstKind::Infer(InferConst::Fresh(_)) => {
 494                 bug!("encountered a fresh const during canonicalization")
 495             }
 496             ty::ConstKind::Bound(debruijn, _) => {
 497                 if debruijn >= self.binder_index {
 498                     bug!("escaping bound type during canonicalization")
 499                 } else {
 500                     return ct;
 501                 }
 502             }
 503             ty::ConstKind::Placeholder(placeholder) => {
 504                 return self.canonicalize_const_var(
 505                     CanonicalVarInfo {
 506                         kind: CanonicalVarKind::PlaceholderConst(placeholder, ct.ty()),
 507                     },
 508                     ct,
 509                 );
 510             }
 511             _ => {}
 512         }
 513
 514         let flags = FlagComputation::for_const(ct);
 515         if flags.intersects(self.needs_canonical_flags) { ct.super_fold_with(self) } else { ct }
 516     }
 517 }
 518
 519 impl<'cx, 'tcx> Canonicalizer<'cx, 'tcx> {
 520     /// The main `canonicalize` method, shared impl of
 521     /// `canonicalize_query` and `canonicalize_response`.
 522     fn canonicalize<V>(
 523         value: V,
 524         infcx: &InferCtxt<'tcx>,
 525         tcx: TyCtxt<'tcx>,
 526         canonicalize_region_mode: &dyn CanonicalizeMode,
 527         query_state: &mut OriginalQueryValues<'tcx>,
 528     ) -> Canonicalized<'tcx, V>
 529     where
 530         V: TypeFoldable<'tcx>,
 531     {
 532         let needs_canonical_flags = if canonicalize_region_mode.any() {
 533             TypeFlags::NEEDS_INFER |
 534             TypeFlags::HAS_FREE_REGIONS | // `HAS_RE_PLACEHOLDER` implies `HAS_FREE_REGIONS`
 535             TypeFlags::HAS_TY_PLACEHOLDER |
 536             TypeFlags::HAS_CT_PLACEHOLDER
 537         } else {
 538             TypeFlags::NEEDS_INFER
 539                 | TypeFlags::HAS_RE_PLACEHOLDER
 540                 | TypeFlags::HAS_TY_PLACEHOLDER
 541                 | TypeFlags::HAS_CT_PLACEHOLDER
 542         };
 543
 544         // Fast path: nothing that needs to be canonicalized.
 545         if !value.has_type_flags(needs_canonical_flags) {
 546             let canon_value = Canonical {
 547                 max_universe: ty::UniverseIndex::ROOT,
 548                 variables: List::empty(),
 549                 value,
 550             };
 551             return canon_value;
 552         }
 553
 554         let mut canonicalizer = Canonicalizer {
 555             infcx,
 556             tcx,
 557             canonicalize_mode: canonicalize_region_mode,
 558             needs_canonical_flags,
 559             variables: SmallVec::new(),
 560             query_state,
 561             indices: FxHashMap::default(),
 562             binder_index: ty::INNERMOST,
 563         };
 564         let out_value = value.fold_with(&mut canonicalizer);
 565
 566         // Once we have canonicalized `out_value`, it should not
 567         // contain anything that ties it to this inference context
 568         // anymore.
 569         debug_assert!(!out_value.needs_infer() && !out_value.has_placeholders());
 570
 571         let canonical_variables =
 572             tcx.intern_canonical_var_infos(&canonicalizer.universe_canonicalized_variables());
 573
 574         let max_universe = canonical_variables
 575             .iter()
 576             .map(|cvar| cvar.universe())
 577             .max()
 578             .unwrap_or(ty::UniverseIndex::ROOT);
 579
 580         Canonical { max_universe, variables: canonical_variables, value: out_value }
 581     }
 582
 583     /// Creates a canonical variable replacing `kind` from the input,
 584     /// or returns an existing variable if `kind` has already been
 585     /// seen. `kind` is expected to be an unbound variable (or
 586     /// potentially a free region).
 587     fn canonical_var(&mut self, info: CanonicalVarInfo<'tcx>, kind: GenericArg<'tcx>) -> BoundVar {
 588         let Canonicalizer { variables, query_state, indices, .. } = self;
 589
 590         let var_values = &mut query_state.var_values;
 591
 592         let universe = info.universe();
 593         if universe != ty::UniverseIndex::ROOT {
 594             assert!(self.canonicalize_mode.preserve_universes());
 595
 596             // Insert universe into the universe map. To preserve the order of the
 597             // universes in the value being canonicalized, we don't update the
 598             // universe in `info` until we have finished canonicalizing.
 599             match query_state.universe_map.binary_search(&universe) {
 600                 Err(idx) => query_state.universe_map.insert(idx, universe),
 601                 Ok(_) => {}
 602             }
 603         }
 604
 605         // This code is hot. `variables` and `var_values` are usually small
 606         // (fewer than 8 elements ~95% of the time). They are SmallVec's to
 607         // avoid allocations in those cases. We also don't use `indices` to
 608         // determine if a kind has been seen before until the limit of 8 has
 609         // been exceeded, to also avoid allocations for `indices`.
 610         if !var_values.spilled() {
 611             // `var_values` is stack-allocated. `indices` isn't used yet. Do a
 612             // direct linear search of `var_values`.
 613             if let Some(idx) = var_values.iter().position(|&k| k == kind) {
 614                 // `kind` is already present in `var_values`.
 615                 BoundVar::new(idx)
 616             } else {
 617                 // `kind` isn't present in `var_values`. Append it. Likewise
 618                 // for `info` and `variables`.
 619                 variables.push(info);
 620                 var_values.push(kind);
 621                 assert_eq!(variables.len(), var_values.len());
 622
 623                 // If `var_values` has become big enough to be heap-allocated,
 624                 // fill up `indices` to facilitate subsequent lookups.
 625                 if var_values.spilled() {
 626                     assert!(indices.is_empty());
 627                     *indices = var_values
 628                         .iter()
 629                         .enumerate()
 630                         .map(|(i, &kind)| (kind, BoundVar::new(i)))
 631                         .collect();
 632                 }
 633                 // The cv is the index of the appended element.
 634                 BoundVar::new(var_values.len() - 1)
 635             }
 636         } else {
 637             // `var_values` is large. Do a hashmap search via `indices`.
 638             *indices.entry(kind).or_insert_with(|| {
 639                 variables.push(info);
 640                 var_values.push(kind);
 641                 assert_eq!(variables.len(), var_values.len());
 642                 BoundVar::new(variables.len() - 1)
 643             })
 644         }
 645     }
 646
 647     /// Replaces the universe indexes used in `var_values` with their index in
 648     /// `query_state.universe_map`. This minimizes the maximum universe used in
 649     /// the canonicalized value.
 650     fn universe_canonicalized_variables(self) -> SmallVec<[CanonicalVarInfo<'tcx>; 8]> {
 651         if self.query_state.universe_map.len() == 1 {
 652             return self.variables;
 653         }
 654
 655         let reverse_universe_map: FxHashMap<ty::UniverseIndex, ty::UniverseIndex> = self
 656             .query_state
 657             .universe_map
 658             .iter()
 659             .enumerate()
 660             .map(|(idx, universe)| (*universe, ty::UniverseIndex::from_usize(idx)))
 661             .collect();
 662
 663         self.variables
 664             .iter()
 665             .map(|v| CanonicalVarInfo {
 666                 kind: match v.kind {
 667                     CanonicalVarKind::Ty(CanonicalTyVarKind::Int | CanonicalTyVarKind::Float) => {
 668                         return *v;
 669                     }
 670                     CanonicalVarKind::Ty(CanonicalTyVarKind::General(u)) => {
 671                         CanonicalVarKind::Ty(CanonicalTyVarKind::General(reverse_universe_map[&u]))
 672                     }
 673                     CanonicalVarKind::Region(u) => {
 674                         CanonicalVarKind::Region(reverse_universe_map[&u])
 675                     }
 676                     CanonicalVarKind::Const(u, t) => {
 677                         CanonicalVarKind::Const(reverse_universe_map[&u], t)
 678                     }
 679                     CanonicalVarKind::PlaceholderTy(placeholder) => {
 680                         CanonicalVarKind::PlaceholderTy(ty::Placeholder {
 681                             universe: reverse_universe_map[&placeholder.universe],
 682                             ..placeholder
 683                         })
 684                     }
 685                     CanonicalVarKind::PlaceholderRegion(placeholder) => {
 686                         CanonicalVarKind::PlaceholderRegion(ty::Placeholder {
 687                             universe: reverse_universe_map[&placeholder.universe],
 688                             ..placeholder
 689                         })
 690                     }
 691                     CanonicalVarKind::PlaceholderConst(placeholder, t) => {
 692                         CanonicalVarKind::PlaceholderConst(
 693                             ty::Placeholder {
 694                                 universe: reverse_universe_map[&placeholder.universe],
 695                                 ..placeholder
 696                             },
 697                             t,
 698                         )
 699                     }
 700                 },
 701             })
 702             .collect()
 703     }
 704
 705     /// Shorthand helper that creates a canonical region variable for
 706     /// `r` (always in the root universe). The reason that we always
 707     /// put these variables into the root universe is because this
 708     /// method is used during **query construction:** in that case, we
 709     /// are taking all the regions and just putting them into the most
 710     /// generic context we can. This may generate solutions that don't
 711     /// fit (e.g., that equate some region variable with a placeholder
 712     /// it can't name) on the caller side, but that's ok, the caller
 713     /// can figure that out. In the meantime, it maximizes our
 714     /// caching.
 715     ///
 716     /// (This works because unification never fails -- and hence trait
 717     /// selection is never affected -- due to a universe mismatch.)
 718     fn canonical_var_for_region_in_root_universe(
 719         &mut self,
 720         r: ty::Region<'tcx>,
 721     ) -> ty::Region<'tcx> {
 722         self.canonical_var_for_region(
 723             CanonicalVarInfo { kind: CanonicalVarKind::Region(ty::UniverseIndex::ROOT) },
 724             r,
 725         )
 726     }
 727
 728     /// Returns the universe in which `vid` is defined.
 729     fn region_var_universe(&self, vid: ty::RegionVid) -> ty::UniverseIndex {
 730         self.infcx.inner.borrow_mut().unwrap_region_constraints().var_universe(vid)
 731     }
 732
 733     /// Creates a canonical variable (with the given `info`)
 734     /// representing the region `r`; return a region referencing it.
 735     fn canonical_var_for_region(
 736         &mut self,
 737         info: CanonicalVarInfo<'tcx>,
 738         r: ty::Region<'tcx>,
 739     ) -> ty::Region<'tcx> {
 740         let var = self.canonical_var(info, r.into());
 741         let br = ty::BoundRegion { var, kind: ty::BrAnon(var.as_u32()) };
 742         let region = ty::ReLateBound(self.binder_index, br);
 743         self.tcx().mk_region(region)
 744     }
 745
 746     /// Given a type variable `ty_var` of the given kind, first check
 747     /// if `ty_var` is bound to anything; if so, canonicalize
 748     /// *that*. Otherwise, create a new canonical variable for
 749     /// `ty_var`.
 750     fn canonicalize_ty_var(&mut self, info: CanonicalVarInfo<'tcx>, ty_var: Ty<'tcx>) -> Ty<'tcx> {
 751         let infcx = self.infcx;
 752         let bound_to = infcx.shallow_resolve(ty_var);
 753         if bound_to != ty_var {
 754             self.fold_ty(bound_to)
 755         } else {
 756             let var = self.canonical_var(info, ty_var.into());
 757             self.tcx().mk_ty(ty::Bound(self.binder_index, var.into()))
 758         }
 759     }
 760
 761     /// Given a type variable `const_var` of the given kind, first check
 762     /// if `const_var` is bound to anything; if so, canonicalize
 763     /// *that*. Otherwise, create a new canonical variable for
 764     /// `const_var`.
 765     fn canonicalize_const_var(
 766         &mut self,
 767         info: CanonicalVarInfo<'tcx>,
 768         const_var: ty::Const<'tcx>,
 769     ) -> ty::Const<'tcx> {
 770         let infcx = self.infcx;
 771         let bound_to = infcx.shallow_resolve(const_var);
 772         if bound_to != const_var {
 773             self.fold_const(bound_to)
 774         } else {
 775             let var = self.canonical_var(info, const_var.into());
 776             self.tcx().mk_const(ty::ConstS {
 777                 kind: ty::ConstKind::Bound(self.binder_index, var),
 778                 ty: self.fold_ty(const_var.ty()),
 779             })
 780         }
 781     }
 782 }