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