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