]>
Commit | Line | Data |
---|---|---|
1a4d82fc JJ |
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. | |
4 | // | |
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. | |
10 | ||
11 | //! Freshening is the process of replacing unknown variables with fresh types. The idea is that | |
12 | //! the type, after freshening, contains no inference variables but instead contains either a | |
13 | //! value for each variable or fresh "arbitrary" types wherever a variable would have been. | |
14 | //! | |
15 | //! Freshening is used primarily to get a good type for inserting into a cache. The result | |
16 | //! summarizes what the type inferencer knows "so far". The primary place it is used right now is | |
17 | //! in the trait matching algorithm, which needs to be able to cache whether an `impl` self type | |
18 | //! matches some other type X -- *without* affecting `X`. That means if that if the type `X` is in | |
19 | //! fact an unbound type variable, we want the match to be regarded as ambiguous, because depending | |
20 | //! on what type that type variable is ultimately assigned, the match may or may not succeed. | |
21 | //! | |
3b2f2976 XL |
22 | //! To handle closures, freshened types also have to contain the signature and kind of any |
23 | //! closure in the local inference context, as otherwise the cache key might be invalidated. | |
24 | //! The way this is done is somewhat hacky - the closure signature is appended to the substs, | |
25 | //! as well as the closure kind "encoded" as a type. Also, special handling is needed when | |
26 | //! the closure signature contains a reference to the original closure. | |
27 | //! | |
1a4d82fc JJ |
28 | //! Note that you should be careful not to allow the output of freshening to leak to the user in |
29 | //! error messages or in any other form. Freshening is only really useful as an internal detail. | |
30 | //! | |
3b2f2976 XL |
31 | //! Because of the manipulation required to handle closures, doing arbitrary operations on |
32 | //! freshened types is not recommended. However, in addition to doing equality/hash | |
33 | //! comparisons (for caching), it is possible to do a `ty::_match` operation between | |
34 | //! 2 freshened types - this works even with the closure encoding. | |
35 | //! | |
36 | //! __An important detail concerning regions.__ The freshener also replaces *all* free regions with | |
3157f602 | 37 | //! 'erased. The reason behind this is that, in general, we do not take region relationships into |
1a4d82fc JJ |
38 | //! account when making type-overloaded decisions. This is important because of the design of the |
39 | //! region inferencer, which is not based on unification but rather on accumulating and then | |
40 | //! solving a set of constraints. In contrast, the type inferencer assigns a value to each type | |
41 | //! variable only once, and it does so as soon as it can, so it is reasonable to ask what the type | |
42 | //! inferencer knows "so far". | |
43 | ||
54a0048b SL |
44 | use ty::{self, Ty, TyCtxt, TypeFoldable}; |
45 | use ty::fold::TypeFolder; | |
476ff2be | 46 | use util::nodemap::FxHashMap; |
3b2f2976 | 47 | |
9e0c209e | 48 | use std::collections::hash_map::Entry; |
1a4d82fc JJ |
49 | |
50 | use super::InferCtxt; | |
d9579d0f | 51 | use super::unify_key::ToType; |
1a4d82fc | 52 | |
a7813a04 XL |
53 | pub struct TypeFreshener<'a, 'gcx: 'a+'tcx, 'tcx: 'a> { |
54 | infcx: &'a InferCtxt<'a, 'gcx, 'tcx>, | |
1a4d82fc | 55 | freshen_count: u32, |
476ff2be | 56 | freshen_map: FxHashMap<ty::InferTy, Ty<'tcx>>, |
1a4d82fc JJ |
57 | } |
58 | ||
a7813a04 XL |
59 | impl<'a, 'gcx, 'tcx> TypeFreshener<'a, 'gcx, 'tcx> { |
60 | pub fn new(infcx: &'a InferCtxt<'a, 'gcx, 'tcx>) | |
61 | -> TypeFreshener<'a, 'gcx, 'tcx> { | |
1a4d82fc | 62 | TypeFreshener { |
041b39d2 | 63 | infcx, |
1a4d82fc | 64 | freshen_count: 0, |
0bf4aa26 | 65 | freshen_map: Default::default(), |
1a4d82fc JJ |
66 | } |
67 | } | |
68 | ||
69 | fn freshen<F>(&mut self, | |
70 | opt_ty: Option<Ty<'tcx>>, | |
71 | key: ty::InferTy, | |
72 | freshener: F) | |
73 | -> Ty<'tcx> where | |
74 | F: FnOnce(u32) -> ty::InferTy, | |
75 | { | |
c30ab7b3 SL |
76 | if let Some(ty) = opt_ty { |
77 | return ty.fold_with(self); | |
1a4d82fc JJ |
78 | } |
79 | ||
80 | match self.freshen_map.entry(key) { | |
81 | Entry::Occupied(entry) => *entry.get(), | |
82 | Entry::Vacant(entry) => { | |
83 | let index = self.freshen_count; | |
84 | self.freshen_count += 1; | |
c1a9b12d | 85 | let t = self.infcx.tcx.mk_infer(freshener(index)); |
1a4d82fc JJ |
86 | entry.insert(t); |
87 | t | |
88 | } | |
89 | } | |
90 | } | |
91 | } | |
92 | ||
a7813a04 XL |
93 | impl<'a, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for TypeFreshener<'a, 'gcx, 'tcx> { |
94 | fn tcx<'b>(&'b self) -> TyCtxt<'b, 'gcx, 'tcx> { | |
1a4d82fc JJ |
95 | self.infcx.tcx |
96 | } | |
97 | ||
7cac9316 | 98 | fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> { |
9e0c209e | 99 | match *r { |
1a4d82fc JJ |
100 | ty::ReLateBound(..) => { |
101 | // leave bound regions alone | |
102 | r | |
103 | } | |
104 | ||
105 | ty::ReStatic | | |
7cac9316 | 106 | ty::ReEarlyBound(..) | |
1a4d82fc JJ |
107 | ty::ReFree(_) | |
108 | ty::ReScope(_) | | |
e9174d1e | 109 | ty::ReVar(_) | |
0bf4aa26 | 110 | ty::RePlaceholder(..) | |
3157f602 XL |
111 | ty::ReEmpty | |
112 | ty::ReErased => { | |
113 | // replace all free regions with 'erased | |
cc61c64b | 114 | self.tcx().types.re_erased |
1a4d82fc | 115 | } |
ff7c6d11 | 116 | |
0531ce1d | 117 | ty::ReCanonical(..) | |
ff7c6d11 XL |
118 | ty::ReClosureBound(..) => { |
119 | bug!( | |
0531ce1d | 120 | "encountered unexpected region: {:?}", |
ff7c6d11 XL |
121 | r, |
122 | ); | |
123 | } | |
1a4d82fc JJ |
124 | } |
125 | } | |
126 | ||
127 | fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> { | |
3b2f2976 XL |
128 | if !t.needs_infer() && !t.has_erasable_regions() && |
129 | !(t.has_closure_types() && self.infcx.in_progress_tables.is_some()) { | |
62682a34 SL |
130 | return t; |
131 | } | |
132 | ||
c34b1796 AL |
133 | let tcx = self.infcx.tcx; |
134 | ||
1a4d82fc | 135 | match t.sty { |
b7449926 | 136 | ty::Infer(ty::TyVar(v)) => { |
0531ce1d | 137 | let opt_ty = self.infcx.type_variables.borrow_mut().probe(v).known(); |
c34b1796 | 138 | self.freshen( |
54a0048b | 139 | opt_ty, |
c34b1796 AL |
140 | ty::TyVar(v), |
141 | ty::FreshTy) | |
1a4d82fc JJ |
142 | } |
143 | ||
b7449926 | 144 | ty::Infer(ty::IntVar(v)) => { |
c34b1796 AL |
145 | self.freshen( |
146 | self.infcx.int_unification_table.borrow_mut() | |
0531ce1d | 147 | .probe_value(v) |
c34b1796 AL |
148 | .map(|v| v.to_type(tcx)), |
149 | ty::IntVar(v), | |
150 | ty::FreshIntTy) | |
1a4d82fc JJ |
151 | } |
152 | ||
b7449926 | 153 | ty::Infer(ty::FloatVar(v)) => { |
c34b1796 AL |
154 | self.freshen( |
155 | self.infcx.float_unification_table.borrow_mut() | |
0531ce1d | 156 | .probe_value(v) |
c34b1796 AL |
157 | .map(|v| v.to_type(tcx)), |
158 | ty::FloatVar(v), | |
d9579d0f | 159 | ty::FreshFloatTy) |
1a4d82fc JJ |
160 | } |
161 | ||
b7449926 XL |
162 | ty::Infer(ty::FreshTy(c)) | |
163 | ty::Infer(ty::FreshIntTy(c)) | | |
164 | ty::Infer(ty::FreshFloatTy(c)) => { | |
1a4d82fc | 165 | if c >= self.freshen_count { |
54a0048b SL |
166 | bug!("Encountered a freshend type with id {} \ |
167 | but our counter is only at {}", | |
168 | c, | |
169 | self.freshen_count); | |
1a4d82fc JJ |
170 | } |
171 | t | |
172 | } | |
173 | ||
0bf4aa26 | 174 | ty::Infer(ty::BoundTy(..)) => |
0531ce1d XL |
175 | bug!("encountered canonical ty during freshening"), |
176 | ||
b7449926 XL |
177 | ty::Generator(..) | |
178 | ty::Bool | | |
179 | ty::Char | | |
180 | ty::Int(..) | | |
181 | ty::Uint(..) | | |
182 | ty::Float(..) | | |
183 | ty::Adt(..) | | |
184 | ty::Str | | |
185 | ty::Error | | |
186 | ty::Array(..) | | |
187 | ty::Slice(..) | | |
188 | ty::RawPtr(..) | | |
189 | ty::Ref(..) | | |
190 | ty::FnDef(..) | | |
191 | ty::FnPtr(_) | | |
192 | ty::Dynamic(..) | | |
193 | ty::Never | | |
194 | ty::Tuple(..) | | |
195 | ty::Projection(..) | | |
0bf4aa26 | 196 | ty::UnnormalizedProjection(..) | |
b7449926 XL |
197 | ty::Foreign(..) | |
198 | ty::Param(..) | | |
199 | ty::Closure(..) | | |
200 | ty::GeneratorWitness(..) | | |
201 | ty::Opaque(..) => { | |
9cc50fc6 | 202 | t.super_fold_with(self) |
1a4d82fc JJ |
203 | } |
204 | } | |
205 | } | |
206 | } |