1 // Copyright 2014 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 //! This module contains the "canonicalizer" itself.
13 //! For an overview of what canonicaliation is and how it fits into
14 //! rustc, check out the [chapter in the rustc guide][c].
16 //! [c]: https://rust-lang-nursery.github.io/rustc-guide/traits/canonicalization.html
18 use infer::canonical::{
19 Canonical, CanonicalTyVarKind, CanonicalVarInfo, CanonicalVarKind, Canonicalized,
23 use std::sync::atomic::Ordering;
24 use ty::fold::{TypeFoldable, TypeFolder};
26 use ty::{self, BoundTy, BoundVar, Lift, List, Ty, TyCtxt, TypeFlags};
28 use rustc_data_structures::fx::FxHashMap;
29 use rustc_data_structures::indexed_vec::Idx;
30 use smallvec::SmallVec;
32 impl<'cx, 'gcx, 'tcx> InferCtxt<'cx, 'gcx, 'tcx> {
33 /// Canonicalizes a query value `V`. When we canonicalize a query,
34 /// we not only canonicalize unbound inference variables, but we
35 /// *also* replace all free regions whatsoever. So for example a
36 /// query like `T: Trait<'static>` would be canonicalized to
42 /// with a mapping M that maps `'?0` to `'static`.
44 /// To get a good understanding of what is happening here, check
45 /// out the [chapter in the rustc guide][c].
47 /// [c]: https://rust-lang-nursery.github.io/rustc-guide/traits/canonicalization.html#canonicalizing-the-query
48 pub fn canonicalize_query<V>(
51 query_state: &mut OriginalQueryValues<'tcx>,
52 ) -> Canonicalized<'gcx, V>
54 V: TypeFoldable<'tcx> + Lift<'gcx>,
59 .queries_canonicalized
60 .fetch_add(1, Ordering::Relaxed);
62 Canonicalizer::canonicalize(
66 &CanonicalizeAllFreeRegions,
71 /// Canonicalizes a query *response* `V`. When we canonicalize a
72 /// query response, we only canonicalize unbound inference
73 /// variables, and we leave other free regions alone. So,
74 /// continuing with the example from `canonicalize_query`, if
75 /// there was an input query `T: Trait<'static>`, it would have
76 /// been canonicalized to
82 /// with a mapping M that maps `'?0` to `'static`. But if we found that there
83 /// exists only one possible impl of `Trait`, and it looks like
85 /// impl<T> Trait<'static> for T { .. }
87 /// then we would prepare a query result R that (among other
88 /// things) includes a mapping to `'?0 := 'static`. When
89 /// canonicalizing this query result R, we would leave this
90 /// reference to `'static` alone.
92 /// To get a good understanding of what is happening here, check
93 /// out the [chapter in the rustc guide][c].
95 /// [c]: https://rust-lang-nursery.github.io/rustc-guide/traits/canonicalization.html#canonicalizing-the-query-result
96 pub fn canonicalize_response<V>(&self, value: &V) -> Canonicalized<'gcx, V>
98 V: TypeFoldable<'tcx> + Lift<'gcx>,
100 let mut query_state = OriginalQueryValues::default();
101 Canonicalizer::canonicalize(
105 &CanonicalizeQueryResponse,
110 pub fn canonicalize_user_type_annotation<V>(&self, value: &V) -> Canonicalized<'gcx, V>
112 V: TypeFoldable<'tcx> + Lift<'gcx>,
114 let mut query_state = OriginalQueryValues::default();
115 Canonicalizer::canonicalize(
119 &CanonicalizeUserTypeAnnotation,
124 /// A hacky variant of `canonicalize_query` that does not
125 /// canonicalize `'static`. Unfortunately, the existing leak
126 /// check treaks `'static` differently in some cases (see also
127 /// #33684), so if we are performing an operation that may need to
128 /// prove "leak-check" related things, we leave `'static`
131 /// FIXME(#48536) -- once we have universes, we can remove this and just use
132 /// `canonicalize_query`.
133 pub fn canonicalize_hr_query_hack<V>(
136 query_state: &mut OriginalQueryValues<'tcx>,
137 ) -> Canonicalized<'gcx, V>
139 V: TypeFoldable<'tcx> + Lift<'gcx>,
144 .queries_canonicalized
145 .fetch_add(1, Ordering::Relaxed);
147 Canonicalizer::canonicalize(
151 &CanonicalizeFreeRegionsOtherThanStatic,
157 /// Controls how we canonicalize "free regions" that are not inference
158 /// variables. This depends on what we are canonicalizing *for* --
159 /// e.g., if we are canonicalizing to create a query, we want to
160 /// replace those with inference variables, since we want to make a
161 /// maximally general query. But if we are canonicalizing a *query
162 /// response*, then we don't typically replace free regions, as they
163 /// must have been introduced from other parts of the system.
164 trait CanonicalizeRegionMode {
165 fn canonicalize_free_region(
167 canonicalizer: &mut Canonicalizer<'_, '_, 'tcx>,
169 ) -> ty::Region<'tcx>;
171 fn any(&self) -> bool;
174 struct CanonicalizeQueryResponse;
176 impl CanonicalizeRegionMode for CanonicalizeQueryResponse {
177 fn canonicalize_free_region(
179 canonicalizer: &mut Canonicalizer<'_, '_, 'tcx>,
181 ) -> ty::Region<'tcx> {
183 ty::ReFree(_) | ty::ReEmpty | ty::ReErased | ty::ReStatic | ty::ReEarlyBound(..) => r,
184 ty::RePlaceholder(placeholder) => canonicalizer.canonical_var_for_region(
186 kind: CanonicalVarKind::PlaceholderRegion(*placeholder),
191 let universe = canonicalizer.region_var_universe(*vid);
192 canonicalizer.canonical_var_for_region(
194 kind: CanonicalVarKind::Region(universe),
200 // Other than `'static` or `'empty`, the query
201 // response should be executing in a fully
202 // canonicalized environment, so there shouldn't be
203 // any other region names it can come up.
204 bug!("unexpected region in query response: `{:?}`", r)
209 fn any(&self) -> bool {
214 struct CanonicalizeUserTypeAnnotation;
216 impl CanonicalizeRegionMode for CanonicalizeUserTypeAnnotation {
217 fn canonicalize_free_region(
219 canonicalizer: &mut Canonicalizer<'_, '_, 'tcx>,
221 ) -> ty::Region<'tcx> {
223 ty::ReEarlyBound(_) | ty::ReFree(_) | ty::ReErased | ty::ReEmpty | ty::ReStatic => r,
224 ty::ReVar(_) => canonicalizer.canonical_var_for_region_in_root_universe(r),
226 // We only expect region names that the user can type.
227 bug!("unexpected region in query response: `{:?}`", r)
232 fn any(&self) -> bool {
237 struct CanonicalizeAllFreeRegions;
239 impl CanonicalizeRegionMode for CanonicalizeAllFreeRegions {
240 fn canonicalize_free_region(
242 canonicalizer: &mut Canonicalizer<'_, '_, 'tcx>,
244 ) -> ty::Region<'tcx> {
245 canonicalizer.canonical_var_for_region_in_root_universe(r)
248 fn any(&self) -> bool {
253 struct CanonicalizeFreeRegionsOtherThanStatic;
255 impl CanonicalizeRegionMode for CanonicalizeFreeRegionsOtherThanStatic {
256 fn canonicalize_free_region(
258 canonicalizer: &mut Canonicalizer<'_, '_, 'tcx>,
260 ) -> ty::Region<'tcx> {
261 if let ty::ReStatic = r {
264 canonicalizer.canonical_var_for_region_in_root_universe(r)
268 fn any(&self) -> bool {
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
280 indices: FxHashMap<Kind<'tcx>, BoundVar>,
281 canonicalize_region_mode: &'cx dyn CanonicalizeRegionMode,
282 needs_canonical_flags: TypeFlags,
284 binder_index: ty::DebruijnIndex,
287 impl<'cx, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for Canonicalizer<'cx, 'gcx, 'tcx> {
288 fn tcx<'b>(&'b self) -> TyCtxt<'b, 'gcx, 'tcx> {
292 fn fold_binder<T>(&mut self, t: &ty::Binder<T>) -> ty::Binder<T>
293 where T: TypeFoldable<'tcx>
295 self.binder_index.shift_in(1);
296 let t = t.super_fold_with(self);
297 self.binder_index.shift_out(1);
301 fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
303 ty::ReLateBound(index, ..) => {
304 if index >= self.binder_index {
305 bug!("escaping late bound region during canonicalization")
314 .borrow_region_constraints()
315 .opportunistic_resolve_var(self.tcx, vid);
317 "canonical: region var found with vid {:?}, \
318 opportunistically resolved to {:?}",
321 self.canonicalize_region_mode
322 .canonicalize_free_region(self, r)
326 | ty::ReEarlyBound(..)
329 | ty::RePlaceholder(..)
331 | ty::ReErased => self.canonicalize_region_mode
332 .canonicalize_free_region(self, r),
334 ty::ReClosureBound(..) => {
335 bug!("closure bound region encountered during canonicalization")
340 fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
342 ty::Infer(ty::TyVar(_)) => self.canonicalize_ty_var(CanonicalTyVarKind::General, t),
344 ty::Infer(ty::IntVar(_)) => self.canonicalize_ty_var(CanonicalTyVarKind::Int, t),
346 ty::Infer(ty::FloatVar(_)) => self.canonicalize_ty_var(CanonicalTyVarKind::Float, t),
348 ty::Infer(ty::FreshTy(_))
349 | ty::Infer(ty::FreshIntTy(_))
350 | ty::Infer(ty::FreshFloatTy(_)) => {
351 bug!("encountered a fresh type during canonicalization")
354 ty::Bound(bound_ty) => {
355 if bound_ty.index >= self.binder_index {
356 bug!("escaping bound type during canonicalization")
364 | ty::GeneratorWitness(..)
383 | ty::UnnormalizedProjection(..)
386 | ty::Opaque(..) => {
387 if t.flags.intersects(self.needs_canonical_flags) {
388 t.super_fold_with(self)
397 impl<'cx, 'gcx, 'tcx> Canonicalizer<'cx, 'gcx, 'tcx> {
398 /// The main `canonicalize` method, shared impl of
399 /// `canonicalize_query` and `canonicalize_response`.
402 infcx: Option<&InferCtxt<'_, 'gcx, 'tcx>>,
403 tcx: TyCtxt<'_, 'gcx, 'tcx>,
404 canonicalize_region_mode: &dyn CanonicalizeRegionMode,
405 query_state: &mut OriginalQueryValues<'tcx>,
406 ) -> Canonicalized<'gcx, V>
408 V: TypeFoldable<'tcx> + Lift<'gcx>,
410 let needs_canonical_flags = if canonicalize_region_mode.any() {
411 TypeFlags::HAS_FREE_REGIONS | TypeFlags::KEEP_IN_LOCAL_TCX
413 TypeFlags::KEEP_IN_LOCAL_TCX
416 let gcx = tcx.global_tcx();
418 // Fast path: nothing that needs to be canonicalized.
419 if !value.has_type_flags(needs_canonical_flags) {
420 let out_value = gcx.lift(value).unwrap();
421 let canon_value = Canonical {
422 max_universe: ty::UniverseIndex::ROOT,
423 variables: List::empty(),
429 let mut canonicalizer = Canonicalizer {
432 canonicalize_region_mode,
433 needs_canonical_flags,
434 variables: SmallVec::new(),
436 indices: FxHashMap::default(),
437 binder_index: ty::INNERMOST,
439 let out_value = value.fold_with(&mut canonicalizer);
441 // Once we have canonicalized `out_value`, it should not
442 // contain anything that ties it to this inference context
443 // anymore, so it should live in the global arena.
444 let out_value = gcx.lift(&out_value).unwrap_or_else(|| {
446 "failed to lift `{:?}`, canonicalized from `{:?}`",
452 let canonical_variables = tcx.intern_canonical_var_infos(&canonicalizer.variables);
454 let max_universe = canonical_variables
456 .map(|cvar| cvar.universe())
458 .unwrap_or(ty::UniverseIndex::ROOT);
462 variables: canonical_variables,
467 /// Creates a canonical variable replacing `kind` from the input,
468 /// or returns an existing variable if `kind` has already been
469 /// seen. `kind` is expected to be an unbound variable (or
470 /// potentially a free region).
471 fn canonical_var(&mut self, info: CanonicalVarInfo, kind: Kind<'tcx>) -> BoundVar {
479 let var_values = &mut query_state.var_values;
481 // This code is hot. `variables` and `var_values` are usually small
482 // (fewer than 8 elements ~95% of the time). They are SmallVec's to
483 // avoid allocations in those cases. We also don't use `indices` to
484 // determine if a kind has been seen before until the limit of 8 has
485 // been exceeded, to also avoid allocations for `indices`.
486 let var = if !var_values.spilled() {
487 // `var_values` is stack-allocated. `indices` isn't used yet. Do a
488 // direct linear search of `var_values`.
489 if let Some(idx) = var_values.iter().position(|&k| k == kind) {
490 // `kind` is already present in `var_values`.
493 // `kind` isn't present in `var_values`. Append it. Likewise
494 // for `info` and `variables`.
495 variables.push(info);
496 var_values.push(kind);
497 assert_eq!(variables.len(), var_values.len());
499 // If `var_values` has become big enough to be heap-allocated,
500 // fill up `indices` to facilitate subsequent lookups.
501 if var_values.spilled() {
502 assert!(indices.is_empty());
503 *indices = var_values
506 .map(|(i, &kind)| (kind, BoundVar::new(i)))
509 // The cv is the index of the appended element.
510 BoundVar::new(var_values.len() - 1)
513 // `var_values` is large. Do a hashmap search via `indices`.
514 *indices.entry(kind).or_insert_with(|| {
515 variables.push(info);
516 var_values.push(kind);
517 assert_eq!(variables.len(), var_values.len());
518 BoundVar::new(variables.len() - 1)
525 /// Shorthand helper that creates a canonical region variable for
526 /// `r` (always in the root universe). The reason that we always
527 /// put these variables into the root universe is because this
528 /// method is used during **query construction:** in that case, we
529 /// are taking all the regions and just putting them into the most
530 /// generic context we can. This may generate solutions that don't
531 /// fit (e.g., that equate some region variable with a placeholder
532 /// it can't name) on the caller side, but that's ok, the caller
533 /// can figure that out. In the meantime, it maximizes our
536 /// (This works because unification never fails -- and hence trait
537 /// selection is never affected -- due to a universe mismatch.)
538 fn canonical_var_for_region_in_root_universe(
541 ) -> ty::Region<'tcx> {
542 self.canonical_var_for_region(
544 kind: CanonicalVarKind::Region(ty::UniverseIndex::ROOT),
550 /// Returns the universe in which `vid` is defined.
551 fn region_var_universe(&self, vid: ty::RegionVid) -> ty::UniverseIndex {
554 .borrow_region_constraints()
558 /// Create a canonical variable (with the given `info`)
559 /// representing the region `r`; return a region referencing it.
560 fn canonical_var_for_region(
562 info: CanonicalVarInfo,
564 ) -> ty::Region<'tcx> {
565 let var = self.canonical_var(info, r.into());
566 let region = ty::ReLateBound(
568 ty::BoundRegion::BrAnon(var.index() as u32)
570 self.tcx().mk_region(region)
573 /// Given a type variable `ty_var` of the given kind, first check
574 /// if `ty_var` is bound to anything; if so, canonicalize
575 /// *that*. Otherwise, create a new canonical variable for
577 fn canonicalize_ty_var(&mut self, ty_kind: CanonicalTyVarKind, ty_var: Ty<'tcx>) -> Ty<'tcx> {
578 let infcx = self.infcx.expect("encountered ty-var without infcx");
579 let bound_to = infcx.shallow_resolve(ty_var);
580 if bound_to != ty_var {
581 self.fold_ty(bound_to)
583 let info = CanonicalVarInfo {
584 kind: CanonicalVarKind::Ty(ty_kind),
586 let var = self.canonical_var(info, ty_var.into());
587 self.tcx().mk_ty(ty::Bound(BoundTy::new(self.binder_index, var)))