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::*;
15 use middle::ty::{self, Ty};
19 use util::snapshot_vec as sv;
21 pub struct TypeVariableTable<'tcx> {
22 values: sv::SnapshotVec<TypeVariableData<'tcx>,UndoEntry,Delegate>,
25 struct TypeVariableData<'tcx> {
26 value: TypeVariableValue<'tcx>,
30 enum TypeVariableValue<'tcx> {
32 Bounded(Vec<Relation>),
36 snapshot: sv::Snapshot
40 // The type of the var was specified.
41 SpecifyVar(ty::TyVid, Vec<Relation>),
42 Relate(ty::TyVid, ty::TyVid),
47 type Relation = (RelationDir, ty::TyVid);
49 #[derive(Copy, PartialEq, Show)]
50 pub enum RelationDir {
51 SubtypeOf, SupertypeOf, EqTo
55 fn opposite(self) -> RelationDir {
57 SubtypeOf => SupertypeOf,
58 SupertypeOf => SubtypeOf,
64 impl<'tcx> TypeVariableTable<'tcx> {
65 pub fn new() -> TypeVariableTable<'tcx> {
66 TypeVariableTable { values: sv::SnapshotVec::new(Delegate) }
69 fn relations<'a>(&'a mut self, a: ty::TyVid) -> &'a mut Vec<Relation> {
70 relations(self.values.get_mut(a.index as uint))
73 pub fn var_diverges<'a>(&'a self, vid: ty::TyVid) -> bool {
74 self.values.get(vid.index as uint).diverging
77 /// Records that `a <: b`, `a :> b`, or `a == b`, depending on `dir`.
79 /// Precondition: neither `a` nor `b` are known.
80 pub fn relate_vars(&mut self, a: ty::TyVid, dir: RelationDir, b: ty::TyVid) {
82 self.relations(a).push((dir, b));
83 self.relations(b).push((dir.opposite(), a));
84 self.values.record(Relate(a, b));
88 /// Instantiates `vid` with the type `ty` and then pushes an entry onto `stack` for each of the
89 /// relations of `vid` to other variables. The relations will have the form `(ty, dir, vid1)`
90 /// where `vid1` is some other variable id.
91 pub fn instantiate_and_push(
95 stack: &mut Vec<(Ty<'tcx>, RelationDir, ty::TyVid)>)
98 let value_ptr = &mut self.values.get_mut(vid.index as uint).value;
99 mem::replace(value_ptr, Known(ty))
102 let relations = match old_value {
104 Known(_) => panic!("Asked to instantiate variable that is \
105 already instantiated")
108 for &(dir, vid) in relations.iter() {
109 stack.push((ty, dir, vid));
112 self.values.record(SpecifyVar(vid, relations));
115 pub fn new_var(&mut self, diverging: bool) -> ty::TyVid {
116 let index = self.values.push(TypeVariableData {
117 value: Bounded(vec![]),
120 ty::TyVid { index: index as u32 }
123 pub fn probe(&self, vid: ty::TyVid) -> Option<Ty<'tcx>> {
124 match self.values.get(vid.index as uint).value {
130 pub fn replace_if_possible(&self, t: Ty<'tcx>) -> Ty<'tcx> {
132 ty::ty_infer(ty::TyVar(v)) => {
133 match self.probe(v) {
142 pub fn snapshot(&mut self) -> Snapshot {
143 Snapshot { snapshot: self.values.start_snapshot() }
146 pub fn rollback_to(&mut self, s: Snapshot) {
147 self.values.rollback_to(s.snapshot);
150 pub fn commit(&mut self, s: Snapshot) {
151 self.values.commit(s.snapshot);
154 pub fn types_escaping_snapshot(&self, s: &Snapshot) -> Vec<Ty<'tcx>> {
156 * Find the set of type variables that existed *before* `s`
157 * but which have only been unified since `s` started, and
158 * return the types with which they were unified. So if we had
159 * a type variable `V0`, then we started the snapshot, then we
160 * created a type variable `V1`, unifed `V0` with `T0`, and
161 * unified `V1` with `T1`, this function would return `{T0}`.
164 let mut new_elem_threshold = u32::MAX;
165 let mut escaping_types = Vec::new();
166 let actions_since_snapshot = self.values.actions_since_snapshot(&s.snapshot);
167 debug!("actions_since_snapshot.len() = {}", actions_since_snapshot.len());
168 for action in actions_since_snapshot.iter() {
170 sv::UndoLog::NewElem(index) => {
171 // if any new variables were created during the
172 // snapshot, remember the lower index (which will
173 // always be the first one we see). Note that this
174 // action must precede those variables being
176 new_elem_threshold = min(new_elem_threshold, index as u32);
177 debug!("NewElem({}) new_elem_threshold={}", index, new_elem_threshold);
180 sv::UndoLog::Other(SpecifyVar(vid, _)) => {
181 if vid.index < new_elem_threshold {
182 // quick check to see if this variable was
183 // created since the snapshot started or not.
184 let escaping_type = self.probe(vid).unwrap();
185 escaping_types.push(escaping_type);
187 debug!("SpecifyVar({}) new_elem_threshold={}", vid, new_elem_threshold);
198 impl<'tcx> sv::SnapshotVecDelegate<TypeVariableData<'tcx>,UndoEntry> for Delegate {
199 fn reverse(&mut self,
200 values: &mut Vec<TypeVariableData>,
203 SpecifyVar(vid, relations) => {
204 values[vid.index as uint].value = Bounded(relations);
208 relations(&mut (*values)[a.index as uint]).pop();
209 relations(&mut (*values)[b.index as uint]).pop();
215 fn relations<'a>(v: &'a mut TypeVariableData) -> &'a mut Vec<Relation> {
217 Known(_) => panic!("var_sub_var: variable is known"),
218 Bounded(ref mut relations) => relations