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