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

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