]>
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 | pub use self::RelationDir::*; | |
12 | use self::TypeVariableValue::*; | |
13 | use self::UndoEntry::*; | |
54a0048b | 14 | use hir::def_id::{DefId}; |
c30ab7b3 | 15 | use syntax::util::small_vector::SmallVector; |
3157f602 | 16 | use syntax_pos::Span; |
c30ab7b3 | 17 | use ty::{self, Ty}; |
c1a9b12d | 18 | |
1a4d82fc | 19 | use std::cmp::min; |
85aaf69f | 20 | use std::marker::PhantomData; |
1a4d82fc JJ |
21 | use std::mem; |
22 | use std::u32; | |
d9579d0f | 23 | use rustc_data_structures::snapshot_vec as sv; |
54a0048b | 24 | use rustc_data_structures::unify as ut; |
1a4d82fc JJ |
25 | |
26 | pub struct TypeVariableTable<'tcx> { | |
85aaf69f | 27 | values: sv::SnapshotVec<Delegate<'tcx>>, |
54a0048b | 28 | eq_relations: ut::UnificationTable<ty::TyVid>, |
1a4d82fc JJ |
29 | } |
30 | ||
31 | struct TypeVariableData<'tcx> { | |
32 | value: TypeVariableValue<'tcx>, | |
33 | diverging: bool | |
34 | } | |
35 | ||
36 | enum TypeVariableValue<'tcx> { | |
37 | Known(Ty<'tcx>), | |
c1a9b12d SL |
38 | Bounded { |
39 | relations: Vec<Relation>, | |
40 | default: Option<Default<'tcx>> | |
41 | } | |
42 | } | |
43 | ||
44 | // We will use this to store the required information to recapitulate what happened when | |
45 | // an error occurs. | |
46 | #[derive(Clone, Debug, PartialEq, Eq, Hash)] | |
47 | pub struct Default<'tcx> { | |
48 | pub ty: Ty<'tcx>, | |
49 | /// The span where the default was incurred | |
50 | pub origin_span: Span, | |
51 | /// The definition that the default originates from | |
52 | pub def_id: DefId | |
1a4d82fc JJ |
53 | } |
54 | ||
55 | pub struct Snapshot { | |
54a0048b SL |
56 | snapshot: sv::Snapshot, |
57 | eq_snapshot: ut::Snapshot<ty::TyVid>, | |
1a4d82fc JJ |
58 | } |
59 | ||
c1a9b12d | 60 | enum UndoEntry<'tcx> { |
1a4d82fc | 61 | // The type of the var was specified. |
c1a9b12d | 62 | SpecifyVar(ty::TyVid, Vec<Relation>, Option<Default<'tcx>>), |
1a4d82fc | 63 | Relate(ty::TyVid, ty::TyVid), |
54a0048b | 64 | RelateRange(ty::TyVid, usize), |
1a4d82fc JJ |
65 | } |
66 | ||
85aaf69f | 67 | struct Delegate<'tcx>(PhantomData<&'tcx ()>); |
1a4d82fc JJ |
68 | |
69 | type Relation = (RelationDir, ty::TyVid); | |
70 | ||
54a0048b | 71 | #[derive(Copy, Clone, Eq, PartialEq, Hash, Debug)] |
1a4d82fc | 72 | pub enum RelationDir { |
85aaf69f | 73 | SubtypeOf, SupertypeOf, EqTo, BiTo |
1a4d82fc JJ |
74 | } |
75 | ||
76 | impl RelationDir { | |
77 | fn opposite(self) -> RelationDir { | |
78 | match self { | |
79 | SubtypeOf => SupertypeOf, | |
80 | SupertypeOf => SubtypeOf, | |
85aaf69f SL |
81 | EqTo => EqTo, |
82 | BiTo => BiTo, | |
1a4d82fc JJ |
83 | } |
84 | } | |
85 | } | |
86 | ||
87 | impl<'tcx> TypeVariableTable<'tcx> { | |
88 | pub fn new() -> TypeVariableTable<'tcx> { | |
54a0048b SL |
89 | TypeVariableTable { |
90 | values: sv::SnapshotVec::new(), | |
91 | eq_relations: ut::UnificationTable::new(), | |
92 | } | |
1a4d82fc JJ |
93 | } |
94 | ||
95 | fn relations<'a>(&'a mut self, a: ty::TyVid) -> &'a mut Vec<Relation> { | |
c34b1796 | 96 | relations(self.values.get_mut(a.index as usize)) |
1a4d82fc JJ |
97 | } |
98 | ||
c1a9b12d SL |
99 | pub fn default(&self, vid: ty::TyVid) -> Option<Default<'tcx>> { |
100 | match &self.values.get(vid.index as usize).value { | |
101 | &Known(_) => None, | |
102 | &Bounded { ref default, .. } => default.clone() | |
103 | } | |
104 | } | |
105 | ||
1a4d82fc | 106 | pub fn var_diverges<'a>(&'a self, vid: ty::TyVid) -> bool { |
c34b1796 | 107 | self.values.get(vid.index as usize).diverging |
1a4d82fc JJ |
108 | } |
109 | ||
110 | /// Records that `a <: b`, `a :> b`, or `a == b`, depending on `dir`. | |
111 | /// | |
112 | /// Precondition: neither `a` nor `b` are known. | |
113 | pub fn relate_vars(&mut self, a: ty::TyVid, dir: RelationDir, b: ty::TyVid) { | |
54a0048b SL |
114 | let a = self.root_var(a); |
115 | let b = self.root_var(b); | |
1a4d82fc | 116 | if a != b { |
54a0048b SL |
117 | if dir == EqTo { |
118 | // a and b must be equal which we mark in the unification table | |
119 | let root = self.eq_relations.union(a, b); | |
120 | // In addition to being equal, all relations from the variable which is no longer | |
121 | // the root must be added to the root so they are not forgotten as the other | |
122 | // variable should no longer be referenced (other than to get the root) | |
123 | let other = if a == root { b } else { a }; | |
124 | let count = { | |
125 | let (relations, root_relations) = if other.index < root.index { | |
126 | let (pre, post) = self.values.split_at_mut(root.index as usize); | |
127 | (relations(&mut pre[other.index as usize]), relations(&mut post[0])) | |
128 | } else { | |
129 | let (pre, post) = self.values.split_at_mut(other.index as usize); | |
130 | (relations(&mut post[0]), relations(&mut pre[root.index as usize])) | |
131 | }; | |
132 | root_relations.extend_from_slice(relations); | |
133 | relations.len() | |
134 | }; | |
135 | self.values.record(RelateRange(root, count)); | |
136 | } else { | |
137 | self.relations(a).push((dir, b)); | |
138 | self.relations(b).push((dir.opposite(), a)); | |
139 | self.values.record(Relate(a, b)); | |
140 | } | |
1a4d82fc JJ |
141 | } |
142 | } | |
143 | ||
144 | /// Instantiates `vid` with the type `ty` and then pushes an entry onto `stack` for each of the | |
145 | /// relations of `vid` to other variables. The relations will have the form `(ty, dir, vid1)` | |
146 | /// where `vid1` is some other variable id. | |
54a0048b SL |
147 | /// |
148 | /// Precondition: `vid` must be a root in the unification table | |
1a4d82fc JJ |
149 | pub fn instantiate_and_push( |
150 | &mut self, | |
151 | vid: ty::TyVid, | |
152 | ty: Ty<'tcx>, | |
c30ab7b3 | 153 | stack: &mut SmallVector<(Ty<'tcx>, RelationDir, ty::TyVid)>) |
1a4d82fc | 154 | { |
54a0048b | 155 | debug_assert!(self.root_var(vid) == vid); |
1a4d82fc | 156 | let old_value = { |
c34b1796 | 157 | let value_ptr = &mut self.values.get_mut(vid.index as usize).value; |
1a4d82fc JJ |
158 | mem::replace(value_ptr, Known(ty)) |
159 | }; | |
160 | ||
c1a9b12d SL |
161 | let (relations, default) = match old_value { |
162 | Bounded { relations, default } => (relations, default), | |
54a0048b SL |
163 | Known(_) => bug!("Asked to instantiate variable that is \ |
164 | already instantiated") | |
1a4d82fc JJ |
165 | }; |
166 | ||
85aaf69f | 167 | for &(dir, vid) in &relations { |
1a4d82fc JJ |
168 | stack.push((ty, dir, vid)); |
169 | } | |
170 | ||
c1a9b12d | 171 | self.values.record(SpecifyVar(vid, relations, default)); |
1a4d82fc JJ |
172 | } |
173 | ||
c1a9b12d SL |
174 | pub fn new_var(&mut self, |
175 | diverging: bool, | |
176 | default: Option<Default<'tcx>>) -> ty::TyVid { | |
54a0048b | 177 | self.eq_relations.new_key(()); |
1a4d82fc | 178 | let index = self.values.push(TypeVariableData { |
c1a9b12d | 179 | value: Bounded { relations: vec![], default: default }, |
1a4d82fc JJ |
180 | diverging: diverging |
181 | }); | |
3157f602 XL |
182 | let v = ty::TyVid { index: index as u32 }; |
183 | debug!("new_var() -> {:?}", v); | |
184 | v | |
1a4d82fc JJ |
185 | } |
186 | ||
54a0048b SL |
187 | pub fn root_var(&mut self, vid: ty::TyVid) -> ty::TyVid { |
188 | self.eq_relations.find(vid) | |
189 | } | |
190 | ||
191 | pub fn probe(&mut self, vid: ty::TyVid) -> Option<Ty<'tcx>> { | |
192 | let vid = self.root_var(vid); | |
193 | self.probe_root(vid) | |
194 | } | |
195 | ||
196 | /// Retrieves the type of `vid` given that it is currently a root in the unification table | |
197 | pub fn probe_root(&mut self, vid: ty::TyVid) -> Option<Ty<'tcx>> { | |
198 | debug_assert!(self.root_var(vid) == vid); | |
c34b1796 | 199 | match self.values.get(vid.index as usize).value { |
c1a9b12d | 200 | Bounded { .. } => None, |
1a4d82fc JJ |
201 | Known(t) => Some(t) |
202 | } | |
203 | } | |
204 | ||
54a0048b | 205 | pub fn replace_if_possible(&mut self, t: Ty<'tcx>) -> Ty<'tcx> { |
1a4d82fc | 206 | match t.sty { |
62682a34 | 207 | ty::TyInfer(ty::TyVar(v)) => { |
1a4d82fc JJ |
208 | match self.probe(v) { |
209 | None => t, | |
210 | Some(u) => u | |
211 | } | |
212 | } | |
213 | _ => t, | |
214 | } | |
215 | } | |
216 | ||
217 | pub fn snapshot(&mut self) -> Snapshot { | |
54a0048b SL |
218 | Snapshot { |
219 | snapshot: self.values.start_snapshot(), | |
220 | eq_snapshot: self.eq_relations.snapshot(), | |
221 | } | |
1a4d82fc JJ |
222 | } |
223 | ||
224 | pub fn rollback_to(&mut self, s: Snapshot) { | |
3157f602 XL |
225 | debug!("rollback_to{:?}", { |
226 | for action in self.values.actions_since_snapshot(&s.snapshot) { | |
227 | match *action { | |
228 | sv::UndoLog::NewElem(index) => { | |
229 | debug!("inference variable _#{}t popped", index) | |
230 | } | |
231 | _ => { } | |
232 | } | |
233 | } | |
234 | }); | |
235 | ||
1a4d82fc | 236 | self.values.rollback_to(s.snapshot); |
54a0048b | 237 | self.eq_relations.rollback_to(s.eq_snapshot); |
1a4d82fc JJ |
238 | } |
239 | ||
240 | pub fn commit(&mut self, s: Snapshot) { | |
241 | self.values.commit(s.snapshot); | |
54a0048b | 242 | self.eq_relations.commit(s.eq_snapshot); |
1a4d82fc JJ |
243 | } |
244 | ||
54a0048b | 245 | pub fn types_escaping_snapshot(&mut self, s: &Snapshot) -> Vec<Ty<'tcx>> { |
1a4d82fc JJ |
246 | /*! |
247 | * Find the set of type variables that existed *before* `s` | |
248 | * but which have only been unified since `s` started, and | |
249 | * return the types with which they were unified. So if we had | |
250 | * a type variable `V0`, then we started the snapshot, then we | |
251 | * created a type variable `V1`, unifed `V0` with `T0`, and | |
252 | * unified `V1` with `T1`, this function would return `{T0}`. | |
253 | */ | |
254 | ||
255 | let mut new_elem_threshold = u32::MAX; | |
256 | let mut escaping_types = Vec::new(); | |
257 | let actions_since_snapshot = self.values.actions_since_snapshot(&s.snapshot); | |
258 | debug!("actions_since_snapshot.len() = {}", actions_since_snapshot.len()); | |
85aaf69f | 259 | for action in actions_since_snapshot { |
1a4d82fc JJ |
260 | match *action { |
261 | sv::UndoLog::NewElem(index) => { | |
262 | // if any new variables were created during the | |
263 | // snapshot, remember the lower index (which will | |
264 | // always be the first one we see). Note that this | |
265 | // action must precede those variables being | |
266 | // specified. | |
267 | new_elem_threshold = min(new_elem_threshold, index as u32); | |
268 | debug!("NewElem({}) new_elem_threshold={}", index, new_elem_threshold); | |
269 | } | |
270 | ||
9e0c209e | 271 | sv::UndoLog::Other(SpecifyVar(vid, ..)) => { |
1a4d82fc JJ |
272 | if vid.index < new_elem_threshold { |
273 | // quick check to see if this variable was | |
274 | // created since the snapshot started or not. | |
54a0048b SL |
275 | let escaping_type = match self.values.get(vid.index as usize).value { |
276 | Bounded { .. } => bug!(), | |
277 | Known(ty) => ty, | |
278 | }; | |
1a4d82fc JJ |
279 | escaping_types.push(escaping_type); |
280 | } | |
281 | debug!("SpecifyVar({:?}) new_elem_threshold={}", vid, new_elem_threshold); | |
282 | } | |
283 | ||
284 | _ => { } | |
285 | } | |
286 | } | |
287 | ||
288 | escaping_types | |
289 | } | |
c1a9b12d | 290 | |
54a0048b SL |
291 | pub fn unsolved_variables(&mut self) -> Vec<ty::TyVid> { |
292 | (0..self.values.len()) | |
293 | .filter_map(|i| { | |
294 | let vid = ty::TyVid { index: i as u32 }; | |
295 | if self.probe(vid).is_some() { | |
296 | None | |
297 | } else { | |
298 | Some(vid) | |
299 | } | |
c1a9b12d SL |
300 | }) |
301 | .collect() | |
302 | } | |
1a4d82fc JJ |
303 | } |
304 | ||
85aaf69f SL |
305 | impl<'tcx> sv::SnapshotVecDelegate for Delegate<'tcx> { |
306 | type Value = TypeVariableData<'tcx>; | |
c1a9b12d | 307 | type Undo = UndoEntry<'tcx>; |
85aaf69f | 308 | |
c1a9b12d | 309 | fn reverse(values: &mut Vec<TypeVariableData<'tcx>>, action: UndoEntry<'tcx>) { |
1a4d82fc | 310 | match action { |
c1a9b12d SL |
311 | SpecifyVar(vid, relations, default) => { |
312 | values[vid.index as usize].value = Bounded { | |
313 | relations: relations, | |
314 | default: default | |
315 | }; | |
1a4d82fc JJ |
316 | } |
317 | ||
318 | Relate(a, b) => { | |
c34b1796 AL |
319 | relations(&mut (*values)[a.index as usize]).pop(); |
320 | relations(&mut (*values)[b.index as usize]).pop(); | |
1a4d82fc | 321 | } |
54a0048b SL |
322 | |
323 | RelateRange(i, n) => { | |
324 | let relations = relations(&mut (*values)[i.index as usize]); | |
325 | for _ in 0..n { | |
326 | relations.pop(); | |
327 | } | |
328 | } | |
1a4d82fc JJ |
329 | } |
330 | } | |
331 | } | |
332 | ||
333 | fn relations<'a>(v: &'a mut TypeVariableData) -> &'a mut Vec<Relation> { | |
334 | match v.value { | |
54a0048b | 335 | Known(_) => bug!("var_sub_var: variable is known"), |
c1a9b12d | 336 | Bounded { ref mut relations, .. } => relations |
1a4d82fc JJ |
337 | } |
338 | } |