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, CanonicalVarValues,
23 use std::sync::atomic::Ordering;
24 use ty::fold::{TypeFoldable, TypeFolder};
26 use ty::{self, CanonicalVar, Lift, Slice, Ty, TyCtxt, TypeFlags};
28 use rustc_data_structures::fx::FxHashMap;
29 use rustc_data_structures::indexed_vec::IndexVec;
31 impl<'cx, 'gcx, 'tcx> InferCtxt<'cx, 'gcx, 'tcx> {
32 /// Canonicalizes a query value `V`. When we canonicalize a query,
33 /// we not only canonicalize unbound inference variables, but we
34 /// *also* replace all free regions whatsoever. So for example a
35 /// query like `T: Trait<'static>` would be canonicalized to
41 /// with a mapping M that maps `'?0` to `'static`.
43 /// To get a good understanding of what is happening here, check
44 /// out the [chapter in the rustc guide][c].
46 /// [c]: https://rust-lang-nursery.github.io/rustc-guide/traits/canonicalization.html#canonicalizing-the-query
47 pub fn canonicalize_query<V>(
50 ) -> (Canonicalized<'gcx, V>, CanonicalVarValues<'tcx>)
52 V: TypeFoldable<'tcx> + Lift<'gcx>,
57 .queries_canonicalized
58 .fetch_add(1, Ordering::Relaxed);
60 Canonicalizer::canonicalize(
64 CanonicalizeRegionMode {
66 other_free_regions: true,
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>(
99 ) -> (Canonicalized<'gcx, V>, CanonicalVarValues<'tcx>)
101 V: TypeFoldable<'tcx> + Lift<'gcx>,
103 Canonicalizer::canonicalize(
107 CanonicalizeRegionMode {
108 static_region: false,
109 other_free_regions: false,
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`
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>(
126 ) -> (Canonicalized<'gcx, V>, CanonicalVarValues<'tcx>)
128 V: TypeFoldable<'tcx> + Lift<'gcx>,
133 .queries_canonicalized
134 .fetch_add(1, Ordering::Relaxed);
136 Canonicalizer::canonicalize(
140 CanonicalizeRegionMode {
141 static_region: false,
142 other_free_regions: true,
148 /// If this flag is true, then all free regions will be replaced with
149 /// a canonical var. This is used to make queries as generic as
150 /// possible. For example, the query `F: Foo<'static>` would be
151 /// canonicalized to `F: Foo<'0>`.
152 struct CanonicalizeRegionMode {
154 other_free_regions: bool,
157 impl CanonicalizeRegionMode {
158 fn any(&self) -> bool {
159 self.static_region || self.other_free_regions
163 struct Canonicalizer<'cx, 'gcx: 'tcx, 'tcx: 'cx> {
164 infcx: Option<&'cx InferCtxt<'cx, 'gcx, 'tcx>>,
165 tcx: TyCtxt<'cx, 'gcx, 'tcx>,
166 variables: IndexVec<CanonicalVar, CanonicalVarInfo>,
167 indices: FxHashMap<Kind<'tcx>, CanonicalVar>,
168 var_values: IndexVec<CanonicalVar, Kind<'tcx>>,
169 canonicalize_region_mode: CanonicalizeRegionMode,
170 needs_canonical_flags: TypeFlags,
173 impl<'cx, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for Canonicalizer<'cx, 'gcx, 'tcx> {
174 fn tcx<'b>(&'b self) -> TyCtxt<'b, 'gcx, 'tcx> {
178 fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> {
180 ty::ReLateBound(..) => {
181 // leave bound regions alone
189 .borrow_region_constraints()
190 .opportunistic_resolve_var(self.tcx, vid);
191 let info = CanonicalVarInfo {
192 kind: CanonicalVarKind::Region,
195 "canonical: region var found with vid {:?}, \
196 opportunistically resolved to {:?}",
199 let cvar = self.canonical_var(info, r.into());
200 self.tcx().mk_region(ty::ReCanonical(cvar))
204 if self.canonicalize_region_mode.static_region {
205 let info = CanonicalVarInfo {
206 kind: CanonicalVarKind::Region,
208 let cvar = self.canonical_var(info, r.into());
209 self.tcx().mk_region(ty::ReCanonical(cvar))
218 | ty::ReSkolemized(..)
221 if self.canonicalize_region_mode.other_free_regions {
222 let info = CanonicalVarInfo {
223 kind: CanonicalVarKind::Region,
225 let cvar = self.canonical_var(info, r.into());
226 self.tcx().mk_region(ty::ReCanonical(cvar))
232 ty::ReClosureBound(..) | ty::ReCanonical(_) => {
233 bug!("canonical region encountered during canonicalization")
238 fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
240 ty::TyInfer(ty::TyVar(_)) => self.canonicalize_ty_var(CanonicalTyVarKind::General, t),
242 ty::TyInfer(ty::IntVar(_)) => self.canonicalize_ty_var(CanonicalTyVarKind::Int, t),
244 ty::TyInfer(ty::FloatVar(_)) => self.canonicalize_ty_var(CanonicalTyVarKind::Float, t),
246 ty::TyInfer(ty::FreshTy(_))
247 | ty::TyInfer(ty::FreshIntTy(_))
248 | ty::TyInfer(ty::FreshFloatTy(_)) => {
249 bug!("encountered a fresh type during canonicalization")
252 ty::TyInfer(ty::CanonicalTy(_)) => {
253 bug!("encountered a canonical type during canonicalization")
257 | ty::TyGenerator(..)
258 | ty::TyGeneratorWitness(..)
276 | ty::TyProjection(..)
279 | ty::TyAnon(..) => {
280 if t.flags.intersects(self.needs_canonical_flags) {
281 t.super_fold_with(self)
290 impl<'cx, 'gcx, 'tcx> Canonicalizer<'cx, 'gcx, 'tcx> {
291 /// The main `canonicalize` method, shared impl of
292 /// `canonicalize_query` and `canonicalize_response`.
295 infcx: Option<&'cx InferCtxt<'cx, 'gcx, 'tcx>>,
296 tcx: TyCtxt<'cx, 'gcx, 'tcx>,
297 canonicalize_region_mode: CanonicalizeRegionMode,
298 ) -> (Canonicalized<'gcx, V>, CanonicalVarValues<'tcx>)
300 V: TypeFoldable<'tcx> + Lift<'gcx>,
303 !value.has_type_flags(TypeFlags::HAS_CANONICAL_VARS),
304 "canonicalizing a canonical value: {:?}",
308 let needs_canonical_flags = if canonicalize_region_mode.any() {
309 TypeFlags::HAS_FREE_REGIONS | TypeFlags::KEEP_IN_LOCAL_TCX
311 TypeFlags::KEEP_IN_LOCAL_TCX
314 let gcx = tcx.global_tcx();
316 // Fast path: nothing that needs to be canonicalized.
317 if !value.has_type_flags(needs_canonical_flags) {
318 let out_value = gcx.lift(value).unwrap();
319 let canon_value = Canonical {
320 variables: Slice::empty(),
323 let values = CanonicalVarValues {
324 var_values: IndexVec::default(),
326 return (canon_value, values);
329 let mut canonicalizer = Canonicalizer {
332 canonicalize_region_mode,
333 needs_canonical_flags,
334 variables: IndexVec::default(),
335 indices: FxHashMap::default(),
336 var_values: IndexVec::default(),
338 let out_value = value.fold_with(&mut canonicalizer);
340 // Once we have canonicalized `out_value`, it should not
341 // contain anything that ties it to this inference context
342 // anymore, so it should live in the global arena.
343 let out_value = gcx.lift(&out_value).unwrap_or_else(|| {
345 "failed to lift `{:?}`, canonicalized from `{:?}`",
351 let canonical_variables = tcx.intern_canonical_var_infos(&canonicalizer.variables.raw);
353 let canonical_value = Canonical {
354 variables: canonical_variables,
357 let canonical_var_values = CanonicalVarValues {
358 var_values: canonicalizer.var_values,
360 (canonical_value, canonical_var_values)
363 /// Creates a canonical variable replacing `kind` from the input,
364 /// or returns an existing variable if `kind` has already been
365 /// seen. `kind` is expected to be an unbound variable (or
366 /// potentially a free region).
367 fn canonical_var(&mut self, info: CanonicalVarInfo, kind: Kind<'tcx>) -> CanonicalVar {
378 let cvar1 = variables.push(info);
379 let cvar2 = var_values.push(kind);
380 assert_eq!(cvar1, cvar2);
386 /// Given a type variable `ty_var` of the given kind, first check
387 /// if `ty_var` is bound to anything; if so, canonicalize
388 /// *that*. Otherwise, create a new canonical variable for
390 fn canonicalize_ty_var(&mut self, ty_kind: CanonicalTyVarKind, ty_var: Ty<'tcx>) -> Ty<'tcx> {
391 let infcx = self.infcx.expect("encountered ty-var without infcx");
392 let bound_to = infcx.shallow_resolve(ty_var);
393 if bound_to != ty_var {
394 self.fold_ty(bound_to)
396 let info = CanonicalVarInfo {
397 kind: CanonicalVarKind::Ty(ty_kind),
399 let cvar = self.canonical_var(info, ty_var.into());
400 self.tcx().mk_infer(ty::InferTy::CanonicalTy(cvar))