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 pub use self::RelationDir::*;
12 use self::TypeVariableValue::*;
13 use self::UndoEntry::*;
14 use hir::def_id::{DefId};
15 use syntax::util::small_vector::SmallVector;
21 use std::marker::PhantomData;
24 use rustc_data_structures::snapshot_vec as sv;
25 use rustc_data_structures::unify as ut;
27 pub struct TypeVariableTable<'tcx> {
28 values: sv::SnapshotVec<Delegate<'tcx>>,
29 eq_relations: ut::UnificationTable<ty::TyVid>,
32 /// Reasons to create a type inference variable
34 pub enum TypeVariableOrigin {
36 NormalizeProjectionType(Span),
38 TypeParameterDefinition(Span, ast::Name),
39 TransformedUpvar(Span),
40 SubstitutionPlaceholder(Span),
44 DivergingBlockExpr(Span),
46 LatticeVariable(Span),
49 struct TypeVariableData<'tcx> {
50 value: TypeVariableValue<'tcx>,
51 origin: TypeVariableOrigin,
55 enum TypeVariableValue<'tcx> {
58 relations: Vec<Relation>,
59 default: Option<Default<'tcx>>
63 // We will use this to store the required information to recapitulate what happened when
65 #[derive(Clone, Debug, PartialEq, Eq, Hash)]
66 pub struct Default<'tcx> {
68 /// The span where the default was incurred
69 pub origin_span: Span,
70 /// The definition that the default originates from
75 snapshot: sv::Snapshot,
76 eq_snapshot: ut::Snapshot<ty::TyVid>,
79 enum UndoEntry<'tcx> {
80 // The type of the var was specified.
81 SpecifyVar(ty::TyVid, Vec<Relation>, Option<Default<'tcx>>),
82 Relate(ty::TyVid, ty::TyVid),
83 RelateRange(ty::TyVid, usize),
86 struct Delegate<'tcx>(PhantomData<&'tcx ()>);
88 type Relation = (RelationDir, ty::TyVid);
90 #[derive(Copy, Clone, Eq, PartialEq, Hash, Debug)]
91 pub enum RelationDir {
92 SubtypeOf, SupertypeOf, EqTo, BiTo
96 fn opposite(self) -> RelationDir {
98 SubtypeOf => SupertypeOf,
99 SupertypeOf => SubtypeOf,
106 impl<'tcx> TypeVariableTable<'tcx> {
107 pub fn new() -> TypeVariableTable<'tcx> {
109 values: sv::SnapshotVec::new(),
110 eq_relations: ut::UnificationTable::new(),
114 fn relations<'a>(&'a mut self, a: ty::TyVid) -> &'a mut Vec<Relation> {
115 relations(self.values.get_mut(a.index as usize))
118 pub fn default(&self, vid: ty::TyVid) -> Option<Default<'tcx>> {
119 match &self.values.get(vid.index as usize).value {
121 &Bounded { ref default, .. } => default.clone()
125 pub fn var_diverges<'a>(&'a self, vid: ty::TyVid) -> bool {
126 self.values.get(vid.index as usize).diverging
129 pub fn var_origin(&self, vid: ty::TyVid) -> &TypeVariableOrigin {
130 &self.values.get(vid.index as usize).origin
133 /// Records that `a <: b`, `a :> b`, or `a == b`, depending on `dir`.
135 /// Precondition: neither `a` nor `b` are known.
136 pub fn relate_vars(&mut self, a: ty::TyVid, dir: RelationDir, b: ty::TyVid) {
137 let a = self.root_var(a);
138 let b = self.root_var(b);
141 // a and b must be equal which we mark in the unification table
142 let root = self.eq_relations.union(a, b);
143 // In addition to being equal, all relations from the variable which is no longer
144 // the root must be added to the root so they are not forgotten as the other
145 // variable should no longer be referenced (other than to get the root)
146 let other = if a == root { b } else { a };
148 let (relations, root_relations) = if other.index < root.index {
149 let (pre, post) = self.values.split_at_mut(root.index as usize);
150 (relations(&mut pre[other.index as usize]), relations(&mut post[0]))
152 let (pre, post) = self.values.split_at_mut(other.index as usize);
153 (relations(&mut post[0]), relations(&mut pre[root.index as usize]))
155 root_relations.extend_from_slice(relations);
158 self.values.record(RelateRange(root, count));
160 self.relations(a).push((dir, b));
161 self.relations(b).push((dir.opposite(), a));
162 self.values.record(Relate(a, b));
167 /// Instantiates `vid` with the type `ty` and then pushes an entry onto `stack` for each of the
168 /// relations of `vid` to other variables. The relations will have the form `(ty, dir, vid1)`
169 /// where `vid1` is some other variable id.
171 /// Precondition: `vid` must be a root in the unification table
172 pub fn instantiate_and_push(
176 stack: &mut SmallVector<(Ty<'tcx>, RelationDir, ty::TyVid)>)
178 debug_assert!(self.root_var(vid) == vid);
180 let value_ptr = &mut self.values.get_mut(vid.index as usize).value;
181 mem::replace(value_ptr, Known(ty))
184 let (relations, default) = match old_value {
185 Bounded { relations, default } => (relations, default),
186 Known(_) => bug!("Asked to instantiate variable that is \
187 already instantiated")
190 for &(dir, vid) in &relations {
191 stack.push((ty, dir, vid));
194 self.values.record(SpecifyVar(vid, relations, default));
197 pub fn new_var(&mut self,
199 origin: TypeVariableOrigin,
200 default: Option<Default<'tcx>>,) -> ty::TyVid {
201 debug!("new_var(diverging={:?}, origin={:?})", diverging, origin);
202 self.eq_relations.new_key(());
203 let index = self.values.push(TypeVariableData {
204 value: Bounded { relations: vec![], default: default },
208 let v = ty::TyVid { index: index as u32 };
209 debug!("new_var: diverging={:?} index={:?}", diverging, v);
213 pub fn num_vars(&self) -> usize {
217 pub fn root_var(&mut self, vid: ty::TyVid) -> ty::TyVid {
218 self.eq_relations.find(vid)
221 pub fn probe(&mut self, vid: ty::TyVid) -> Option<Ty<'tcx>> {
222 let vid = self.root_var(vid);
226 /// Retrieves the type of `vid` given that it is currently a root in the unification table
227 pub fn probe_root(&mut self, vid: ty::TyVid) -> Option<Ty<'tcx>> {
228 debug_assert!(self.root_var(vid) == vid);
229 match self.values.get(vid.index as usize).value {
230 Bounded { .. } => None,
235 pub fn replace_if_possible(&mut self, t: Ty<'tcx>) -> Ty<'tcx> {
237 ty::TyInfer(ty::TyVar(v)) => {
238 match self.probe(v) {
247 pub fn snapshot(&mut self) -> Snapshot {
249 snapshot: self.values.start_snapshot(),
250 eq_snapshot: self.eq_relations.snapshot(),
254 pub fn rollback_to(&mut self, s: Snapshot) {
255 debug!("rollback_to{:?}", {
256 for action in self.values.actions_since_snapshot(&s.snapshot) {
258 sv::UndoLog::NewElem(index) => {
259 debug!("inference variable _#{}t popped", index)
266 self.values.rollback_to(s.snapshot);
267 self.eq_relations.rollback_to(s.eq_snapshot);
270 pub fn commit(&mut self, s: Snapshot) {
271 self.values.commit(s.snapshot);
272 self.eq_relations.commit(s.eq_snapshot);
275 pub fn types_escaping_snapshot(&mut self, s: &Snapshot) -> Vec<Ty<'tcx>> {
277 * Find the set of type variables that existed *before* `s`
278 * but which have only been unified since `s` started, and
279 * return the types with which they were unified. So if we had
280 * a type variable `V0`, then we started the snapshot, then we
281 * created a type variable `V1`, unifed `V0` with `T0`, and
282 * unified `V1` with `T1`, this function would return `{T0}`.
285 let mut new_elem_threshold = u32::MAX;
286 let mut escaping_types = Vec::new();
287 let actions_since_snapshot = self.values.actions_since_snapshot(&s.snapshot);
288 debug!("actions_since_snapshot.len() = {}", actions_since_snapshot.len());
289 for action in actions_since_snapshot {
291 sv::UndoLog::NewElem(index) => {
292 // if any new variables were created during the
293 // snapshot, remember the lower index (which will
294 // always be the first one we see). Note that this
295 // action must precede those variables being
297 new_elem_threshold = min(new_elem_threshold, index as u32);
298 debug!("NewElem({}) new_elem_threshold={}", index, new_elem_threshold);
301 sv::UndoLog::Other(SpecifyVar(vid, ..)) => {
302 if vid.index < new_elem_threshold {
303 // quick check to see if this variable was
304 // created since the snapshot started or not.
305 let escaping_type = match self.values.get(vid.index as usize).value {
306 Bounded { .. } => bug!(),
309 escaping_types.push(escaping_type);
311 debug!("SpecifyVar({:?}) new_elem_threshold={}", vid, new_elem_threshold);
321 pub fn unsolved_variables(&mut self) -> Vec<ty::TyVid> {
322 (0..self.values.len())
324 let vid = ty::TyVid { index: i as u32 };
325 if self.probe(vid).is_some() {
335 impl<'tcx> sv::SnapshotVecDelegate for Delegate<'tcx> {
336 type Value = TypeVariableData<'tcx>;
337 type Undo = UndoEntry<'tcx>;
339 fn reverse(values: &mut Vec<TypeVariableData<'tcx>>, action: UndoEntry<'tcx>) {
341 SpecifyVar(vid, relations, default) => {
342 values[vid.index as usize].value = Bounded {
343 relations: relations,
349 relations(&mut (*values)[a.index as usize]).pop();
350 relations(&mut (*values)[b.index as usize]).pop();
353 RelateRange(i, n) => {
354 let relations = relations(&mut (*values)[i.index as usize]);
363 fn relations<'a>(v: &'a mut TypeVariableData) -> &'a mut Vec<Relation> {
365 Known(_) => bug!("var_sub_var: variable is known"),
366 Bounded { ref mut relations, .. } => relations