]>
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::*; | |
1a4d82fc | 14 | use middle::ty::{self, Ty}; |
c1a9b12d SL |
15 | use syntax::ast::DefId; |
16 | use syntax::codemap::Span; | |
17 | ||
1a4d82fc | 18 | use std::cmp::min; |
85aaf69f | 19 | use std::marker::PhantomData; |
1a4d82fc JJ |
20 | use std::mem; |
21 | use std::u32; | |
d9579d0f | 22 | use rustc_data_structures::snapshot_vec as sv; |
1a4d82fc JJ |
23 | |
24 | pub struct TypeVariableTable<'tcx> { | |
85aaf69f | 25 | values: sv::SnapshotVec<Delegate<'tcx>>, |
1a4d82fc JJ |
26 | } |
27 | ||
28 | struct TypeVariableData<'tcx> { | |
29 | value: TypeVariableValue<'tcx>, | |
30 | diverging: bool | |
31 | } | |
32 | ||
33 | enum TypeVariableValue<'tcx> { | |
34 | Known(Ty<'tcx>), | |
c1a9b12d SL |
35 | Bounded { |
36 | relations: Vec<Relation>, | |
37 | default: Option<Default<'tcx>> | |
38 | } | |
39 | } | |
40 | ||
41 | // We will use this to store the required information to recapitulate what happened when | |
42 | // an error occurs. | |
43 | #[derive(Clone, Debug, PartialEq, Eq, Hash)] | |
44 | pub struct Default<'tcx> { | |
45 | pub ty: Ty<'tcx>, | |
46 | /// The span where the default was incurred | |
47 | pub origin_span: Span, | |
48 | /// The definition that the default originates from | |
49 | pub def_id: DefId | |
1a4d82fc JJ |
50 | } |
51 | ||
52 | pub struct Snapshot { | |
53 | snapshot: sv::Snapshot | |
54 | } | |
55 | ||
c1a9b12d | 56 | enum UndoEntry<'tcx> { |
1a4d82fc | 57 | // The type of the var was specified. |
c1a9b12d | 58 | SpecifyVar(ty::TyVid, Vec<Relation>, Option<Default<'tcx>>), |
1a4d82fc JJ |
59 | Relate(ty::TyVid, ty::TyVid), |
60 | } | |
61 | ||
85aaf69f | 62 | struct Delegate<'tcx>(PhantomData<&'tcx ()>); |
1a4d82fc JJ |
63 | |
64 | type Relation = (RelationDir, ty::TyVid); | |
65 | ||
c34b1796 | 66 | #[derive(Copy, Clone, PartialEq, Debug)] |
1a4d82fc | 67 | pub enum RelationDir { |
85aaf69f | 68 | SubtypeOf, SupertypeOf, EqTo, BiTo |
1a4d82fc JJ |
69 | } |
70 | ||
71 | impl RelationDir { | |
72 | fn opposite(self) -> RelationDir { | |
73 | match self { | |
74 | SubtypeOf => SupertypeOf, | |
75 | SupertypeOf => SubtypeOf, | |
85aaf69f SL |
76 | EqTo => EqTo, |
77 | BiTo => BiTo, | |
1a4d82fc JJ |
78 | } |
79 | } | |
80 | } | |
81 | ||
82 | impl<'tcx> TypeVariableTable<'tcx> { | |
83 | pub fn new() -> TypeVariableTable<'tcx> { | |
d9579d0f | 84 | TypeVariableTable { values: sv::SnapshotVec::new() } |
1a4d82fc JJ |
85 | } |
86 | ||
87 | fn relations<'a>(&'a mut self, a: ty::TyVid) -> &'a mut Vec<Relation> { | |
c34b1796 | 88 | relations(self.values.get_mut(a.index as usize)) |
1a4d82fc JJ |
89 | } |
90 | ||
c1a9b12d SL |
91 | pub fn default(&self, vid: ty::TyVid) -> Option<Default<'tcx>> { |
92 | match &self.values.get(vid.index as usize).value { | |
93 | &Known(_) => None, | |
94 | &Bounded { ref default, .. } => default.clone() | |
95 | } | |
96 | } | |
97 | ||
1a4d82fc | 98 | pub fn var_diverges<'a>(&'a self, vid: ty::TyVid) -> bool { |
c34b1796 | 99 | self.values.get(vid.index as usize).diverging |
1a4d82fc JJ |
100 | } |
101 | ||
102 | /// Records that `a <: b`, `a :> b`, or `a == b`, depending on `dir`. | |
103 | /// | |
104 | /// Precondition: neither `a` nor `b` are known. | |
105 | pub fn relate_vars(&mut self, a: ty::TyVid, dir: RelationDir, b: ty::TyVid) { | |
106 | if a != b { | |
107 | self.relations(a).push((dir, b)); | |
108 | self.relations(b).push((dir.opposite(), a)); | |
109 | self.values.record(Relate(a, b)); | |
110 | } | |
111 | } | |
112 | ||
113 | /// Instantiates `vid` with the type `ty` and then pushes an entry onto `stack` for each of the | |
114 | /// relations of `vid` to other variables. The relations will have the form `(ty, dir, vid1)` | |
115 | /// where `vid1` is some other variable id. | |
116 | pub fn instantiate_and_push( | |
117 | &mut self, | |
118 | vid: ty::TyVid, | |
119 | ty: Ty<'tcx>, | |
120 | stack: &mut Vec<(Ty<'tcx>, RelationDir, ty::TyVid)>) | |
121 | { | |
122 | let old_value = { | |
c34b1796 | 123 | let value_ptr = &mut self.values.get_mut(vid.index as usize).value; |
1a4d82fc JJ |
124 | mem::replace(value_ptr, Known(ty)) |
125 | }; | |
126 | ||
c1a9b12d SL |
127 | let (relations, default) = match old_value { |
128 | Bounded { relations, default } => (relations, default), | |
1a4d82fc JJ |
129 | Known(_) => panic!("Asked to instantiate variable that is \ |
130 | already instantiated") | |
131 | }; | |
132 | ||
85aaf69f | 133 | for &(dir, vid) in &relations { |
1a4d82fc JJ |
134 | stack.push((ty, dir, vid)); |
135 | } | |
136 | ||
c1a9b12d | 137 | self.values.record(SpecifyVar(vid, relations, default)); |
1a4d82fc JJ |
138 | } |
139 | ||
c1a9b12d SL |
140 | pub fn new_var(&mut self, |
141 | diverging: bool, | |
142 | default: Option<Default<'tcx>>) -> ty::TyVid { | |
1a4d82fc | 143 | let index = self.values.push(TypeVariableData { |
c1a9b12d | 144 | value: Bounded { relations: vec![], default: default }, |
1a4d82fc JJ |
145 | diverging: diverging |
146 | }); | |
147 | ty::TyVid { index: index as u32 } | |
148 | } | |
149 | ||
150 | pub fn probe(&self, vid: ty::TyVid) -> Option<Ty<'tcx>> { | |
c34b1796 | 151 | match self.values.get(vid.index as usize).value { |
c1a9b12d | 152 | Bounded { .. } => None, |
1a4d82fc JJ |
153 | Known(t) => Some(t) |
154 | } | |
155 | } | |
156 | ||
157 | pub fn replace_if_possible(&self, t: Ty<'tcx>) -> Ty<'tcx> { | |
158 | match t.sty { | |
62682a34 | 159 | ty::TyInfer(ty::TyVar(v)) => { |
1a4d82fc JJ |
160 | match self.probe(v) { |
161 | None => t, | |
162 | Some(u) => u | |
163 | } | |
164 | } | |
165 | _ => t, | |
166 | } | |
167 | } | |
168 | ||
169 | pub fn snapshot(&mut self) -> Snapshot { | |
170 | Snapshot { snapshot: self.values.start_snapshot() } | |
171 | } | |
172 | ||
173 | pub fn rollback_to(&mut self, s: Snapshot) { | |
174 | self.values.rollback_to(s.snapshot); | |
175 | } | |
176 | ||
177 | pub fn commit(&mut self, s: Snapshot) { | |
178 | self.values.commit(s.snapshot); | |
179 | } | |
180 | ||
181 | pub fn types_escaping_snapshot(&self, s: &Snapshot) -> Vec<Ty<'tcx>> { | |
182 | /*! | |
183 | * Find the set of type variables that existed *before* `s` | |
184 | * but which have only been unified since `s` started, and | |
185 | * return the types with which they were unified. So if we had | |
186 | * a type variable `V0`, then we started the snapshot, then we | |
187 | * created a type variable `V1`, unifed `V0` with `T0`, and | |
188 | * unified `V1` with `T1`, this function would return `{T0}`. | |
189 | */ | |
190 | ||
191 | let mut new_elem_threshold = u32::MAX; | |
192 | let mut escaping_types = Vec::new(); | |
193 | let actions_since_snapshot = self.values.actions_since_snapshot(&s.snapshot); | |
194 | debug!("actions_since_snapshot.len() = {}", actions_since_snapshot.len()); | |
85aaf69f | 195 | for action in actions_since_snapshot { |
1a4d82fc JJ |
196 | match *action { |
197 | sv::UndoLog::NewElem(index) => { | |
198 | // if any new variables were created during the | |
199 | // snapshot, remember the lower index (which will | |
200 | // always be the first one we see). Note that this | |
201 | // action must precede those variables being | |
202 | // specified. | |
203 | new_elem_threshold = min(new_elem_threshold, index as u32); | |
204 | debug!("NewElem({}) new_elem_threshold={}", index, new_elem_threshold); | |
205 | } | |
206 | ||
c1a9b12d | 207 | sv::UndoLog::Other(SpecifyVar(vid, _, _)) => { |
1a4d82fc JJ |
208 | if vid.index < new_elem_threshold { |
209 | // quick check to see if this variable was | |
210 | // created since the snapshot started or not. | |
211 | let escaping_type = self.probe(vid).unwrap(); | |
212 | escaping_types.push(escaping_type); | |
213 | } | |
214 | debug!("SpecifyVar({:?}) new_elem_threshold={}", vid, new_elem_threshold); | |
215 | } | |
216 | ||
217 | _ => { } | |
218 | } | |
219 | } | |
220 | ||
221 | escaping_types | |
222 | } | |
c1a9b12d SL |
223 | |
224 | pub fn unsolved_variables(&self) -> Vec<ty::TyVid> { | |
225 | self.values | |
226 | .iter() | |
227 | .enumerate() | |
228 | .filter_map(|(i, value)| match &value.value { | |
229 | &TypeVariableValue::Known(_) => None, | |
230 | &TypeVariableValue::Bounded { .. } => Some(ty::TyVid { index: i as u32 }) | |
231 | }) | |
232 | .collect() | |
233 | } | |
1a4d82fc JJ |
234 | } |
235 | ||
85aaf69f SL |
236 | impl<'tcx> sv::SnapshotVecDelegate for Delegate<'tcx> { |
237 | type Value = TypeVariableData<'tcx>; | |
c1a9b12d | 238 | type Undo = UndoEntry<'tcx>; |
85aaf69f | 239 | |
c1a9b12d | 240 | fn reverse(values: &mut Vec<TypeVariableData<'tcx>>, action: UndoEntry<'tcx>) { |
1a4d82fc | 241 | match action { |
c1a9b12d SL |
242 | SpecifyVar(vid, relations, default) => { |
243 | values[vid.index as usize].value = Bounded { | |
244 | relations: relations, | |
245 | default: default | |
246 | }; | |
1a4d82fc JJ |
247 | } |
248 | ||
249 | Relate(a, b) => { | |
c34b1796 AL |
250 | relations(&mut (*values)[a.index as usize]).pop(); |
251 | relations(&mut (*values)[b.index as usize]).pop(); | |
1a4d82fc JJ |
252 | } |
253 | } | |
254 | } | |
255 | } | |
256 | ||
257 | fn relations<'a>(v: &'a mut TypeVariableData) -> &'a mut Vec<Relation> { | |
258 | match v.value { | |
259 | Known(_) => panic!("var_sub_var: variable is known"), | |
c1a9b12d | 260 | Bounded { ref mut relations, .. } => relations |
1a4d82fc JJ |
261 | } |
262 | } |