diff options
Diffstat (limited to 'src/librustc_data_structures/unify')
| -rw-r--r-- | src/librustc_data_structures/unify/mod.rs | 91 | ||||
| -rw-r--r-- | src/librustc_data_structures/unify/tests.rs | 35 |
2 files changed, 67 insertions, 59 deletions
diff --git a/src/librustc_data_structures/unify/mod.rs b/src/librustc_data_structures/unify/mod.rs index c6da70eef75..fe7fa06c962 100644 --- a/src/librustc_data_structures/unify/mod.rs +++ b/src/librustc_data_structures/unify/mod.rs @@ -56,21 +56,21 @@ impl Combine for () { /// time of the algorithm under control. For more information, see /// <http://en.wikipedia.org/wiki/Disjoint-set_data_structure>. #[derive(PartialEq,Clone,Debug)] -pub struct VarValue<K:UnifyKey> { - parent: K, // if equal to self, this is a root +pub struct VarValue<K: UnifyKey> { + parent: K, // if equal to self, this is a root value: K::Value, // value assigned (only relevant to root) - rank: u32, // max depth (only relevant to root) + rank: u32, // max depth (only relevant to root) } /// Table of unification keys and their values. -pub struct UnificationTable<K:UnifyKey> { +pub struct UnificationTable<K: UnifyKey> { /// Indicates the current value of each key. values: sv::SnapshotVec<Delegate<K>>, } /// At any time, users may snapshot a unification table. The changes /// made during the snapshot may either be *committed* or *rolled back*. -pub struct Snapshot<K:UnifyKey> { +pub struct Snapshot<K: UnifyKey> { // Link snapshot to the key type `K` of the table. marker: marker::PhantomData<K>, snapshot: sv::Snapshot, @@ -79,15 +79,17 @@ pub struct Snapshot<K:UnifyKey> { #[derive(Copy, Clone)] struct Delegate<K>(PhantomData<K>); -impl<K:UnifyKey> VarValue<K> { +impl<K: UnifyKey> VarValue<K> { fn new_var(key: K, value: K::Value) -> VarValue<K> { VarValue::new(key, value, 0) } fn new(parent: K, value: K::Value, rank: u32) -> VarValue<K> { - VarValue { parent: parent, // this is a root - value: value, - rank: rank } + VarValue { + parent: parent, // this is a root + value: value, + rank: rank, + } } fn redirect(self, to: K) -> VarValue<K> { @@ -95,7 +97,11 @@ impl<K:UnifyKey> VarValue<K> { } fn root(self, rank: u32, value: K::Value) -> VarValue<K> { - VarValue { rank: rank, value: value, ..self } + VarValue { + rank: rank, + value: value, + ..self + } } /// Returns the key of this node. Only valid if this is a root @@ -122,18 +128,18 @@ impl<K:UnifyKey> VarValue<K> { // other type parameter U, and we have no way to say // Option<U>:LatticeValue. -impl<K:UnifyKey> UnificationTable<K> { +impl<K: UnifyKey> UnificationTable<K> { pub fn new() -> UnificationTable<K> { - UnificationTable { - values: sv::SnapshotVec::new() - } + UnificationTable { values: sv::SnapshotVec::new() } } /// Starts a new snapshot. Each snapshot must be either /// rolled back or committed in a "LIFO" (stack) order. pub fn snapshot(&mut self) -> Snapshot<K> { - Snapshot { marker: marker::PhantomData::<K>, - snapshot: self.values.start_snapshot() } + Snapshot { + marker: marker::PhantomData::<K>, + snapshot: self.values.start_snapshot(), + } } /// Reverses all changes since the last snapshot. Also @@ -154,9 +160,7 @@ impl<K:UnifyKey> UnificationTable<K> { let len = self.values.len(); let key: K = UnifyKey::from_index(len as u32); self.values.push(VarValue::new_var(key, value)); - debug!("{}: created new key: {:?}", - UnifyKey::tag(None::<K>), - key); + debug!("{}: created new key: {:?}", UnifyKey::tag(None::<K>), key); key } @@ -179,9 +183,7 @@ impl<K:UnifyKey> UnificationTable<K> { } root } - None => { - value - } + None => value, } } @@ -195,8 +197,7 @@ impl<K:UnifyKey> UnificationTable<K> { fn set(&mut self, key: K, new_value: VarValue<K>) { assert!(self.is_root(key)); - debug!("Updating variable {:?} to {:?}", - key, new_value); + debug!("Updating variable {:?} to {:?}", key, new_value); let index = key.index() as usize; self.values.set(index, new_value); @@ -243,7 +244,7 @@ impl<K:UnifyKey> UnificationTable<K> { } } -impl<K:UnifyKey> sv::SnapshotVecDelegate for Delegate<K> { +impl<K: UnifyKey> sv::SnapshotVecDelegate for Delegate<K> { type Value = VarValue<K>; type Undo = (); @@ -253,7 +254,7 @@ impl<K:UnifyKey> sv::SnapshotVecDelegate for Delegate<K> { /////////////////////////////////////////////////////////////////////////// // Base union-find algorithm, where we are just making sets -impl<'tcx,K:UnifyKey> UnificationTable<K> +impl<'tcx, K: UnifyKey> UnificationTable<K> where K::Value: Combine { pub fn union(&mut self, a_id: K, b_id: K) { @@ -285,30 +286,24 @@ impl<'tcx,K:UnifyKey> UnificationTable<K> // floats---anything that doesn't have a subtyping relationship we // need to worry about. -impl<'tcx,K,V> UnificationTable<K> - where K: UnifyKey<Value=Option<V>>, - V: Clone+PartialEq+Debug, +impl<'tcx, K, V> UnificationTable<K> + where K: UnifyKey<Value = Option<V>>, + V: Clone + PartialEq + Debug { - pub fn unify_var_var(&mut self, - a_id: K, - b_id: K) - -> Result<(),(V,V)> - { + pub fn unify_var_var(&mut self, a_id: K, b_id: K) -> Result<(), (V, V)> { let node_a = self.get(a_id); let node_b = self.get(b_id); let a_id = node_a.key(); let b_id = node_b.key(); - if a_id == b_id { return Ok(()); } + if a_id == b_id { + return Ok(()); + } let combined = { match (&node_a.value, &node_b.value) { - (&None, &None) => { - None - } - (&Some(ref v), &None) | (&None, &Some(ref v)) => { - Some(v.clone()) - } + (&None, &None) => None, + (&Some(ref v), &None) | (&None, &Some(ref v)) => Some(v.clone()), (&Some(ref v1), &Some(ref v2)) => { if *v1 != *v2 { return Err((v1.clone(), v2.clone())); @@ -323,11 +318,7 @@ impl<'tcx,K,V> UnificationTable<K> /// Sets the value of the key `a_id` to `b`. Because simple keys do not have any subtyping /// relationships, if `a_id` already has a value, it must be the same as `b`. - pub fn unify_var_value(&mut self, - a_id: K, - b: V) - -> Result<(),(V,V)> - { + pub fn unify_var_value(&mut self, a_id: K, b: V) -> Result<(), (V, V)> { let mut node_a = self.get(a_id); match node_a.value { @@ -358,7 +349,13 @@ impl<'tcx,K,V> UnificationTable<K> pub fn unsolved_variables(&mut self) -> Vec<K> { self.values .iter() - .filter_map(|vv| if vv.value.is_some() { None } else { Some(vv.key()) }) + .filter_map(|vv| { + if vv.value.is_some() { + None + } else { + Some(vv.key()) + } + }) .collect() } } diff --git a/src/librustc_data_structures/unify/tests.rs b/src/librustc_data_structures/unify/tests.rs index 089e629a569..f29a7132e83 100644 --- a/src/librustc_data_structures/unify/tests.rs +++ b/src/librustc_data_structures/unify/tests.rs @@ -19,9 +19,15 @@ struct UnitKey(u32); impl UnifyKey for UnitKey { type Value = (); - fn index(&self) -> u32 { self.0 } - fn from_index(u: u32) -> UnitKey { UnitKey(u) } - fn tag(_: Option<UnitKey>) -> &'static str { "UnitKey" } + fn index(&self) -> u32 { + self.0 + } + fn from_index(u: u32) -> UnitKey { + UnitKey(u) + } + fn tag(_: Option<UnitKey>) -> &'static str { + "UnitKey" + } } #[test] @@ -45,7 +51,7 @@ fn big_array() { } for i in 1..MAX { - let l = keys[i-1]; + let l = keys[i - 1]; let r = keys[i]; ut.union(l, r); } @@ -68,7 +74,7 @@ fn big_array_bench(b: &mut Bencher) { b.iter(|| { for i in 1..MAX { - let l = keys[i-1]; + let l = keys[i - 1]; let r = keys[i]; ut.union(l, r); } @@ -90,16 +96,16 @@ fn even_odd() { keys.push(key); if i >= 2 { - ut.union(key, keys[i-2]); + ut.union(key, keys[i - 2]); } } for i in 1..MAX { - assert!(!ut.unioned(keys[i-1], keys[i])); + assert!(!ut.unioned(keys[i - 1], keys[i])); } for i in 2..MAX { - assert!(ut.unioned(keys[i-2], keys[i])); + assert!(ut.unioned(keys[i - 2], keys[i])); } } @@ -108,9 +114,15 @@ struct IntKey(u32); impl UnifyKey for IntKey { type Value = Option<i32>; - fn index(&self) -> u32 { self.0 } - fn from_index(u: u32) -> IntKey { IntKey(u) } - fn tag(_: Option<IntKey>) -> &'static str { "IntKey" } + fn index(&self) -> u32 { + self.0 + } + fn from_index(u: u32) -> IntKey { + IntKey(u) + } + fn tag(_: Option<IntKey>) -> &'static str { + "IntKey" + } } /// Test unifying a key whose value is `Some(_)` with a key whose value is `None`. @@ -191,4 +203,3 @@ fn unify_key_Some_x_val_x() { assert!(ut.unify_var_value(k1, 22).is_ok()); assert_eq!(ut.probe(k1), Some(22)); } - |