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