src/librustc_data_structures/unify/mod.rs

   1 // Copyright 2012-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 use std::marker;
  12 use std::fmt::Debug;
  13 use std::marker::PhantomData;
  14 use snapshot_vec as sv;
  15
  16 #[cfg(test)]
  17 mod tests;
  18
  19 /// This trait is implemented by any type that can serve as a type
  20 /// variable. We call such variables *unification keys*. For example,
  21 /// this trait is implemented by `IntVid`, which represents integral
  22 /// variables.
  23 ///
  24 /// Each key type has an associated value type `V`. For example, for
  25 /// `IntVid`, this is `Option<IntVarValue>`, representing some
  26 /// (possibly not yet known) sort of integer.
  27 ///
  28 /// Clients are expected to provide implementations of this trait; you
  29 /// can see some examples in the `test` module.
  30 pub trait UnifyKey : Copy + Clone + Debug + PartialEq {
  31     type Value: Clone + PartialEq + Debug;
  32
  33     fn index(&self) -> u32;
  34
  35     fn from_index(u: u32) -> Self;
  36
  37     fn tag(k: Option<Self>) -> &'static str;
  38 }
  39
  40 /// Value of a unification key. We implement Tarjan's union-find
  41 /// algorithm: when two keys are unified, one of them is converted
  42 /// into a "redirect" pointing at the other. These redirects form a
  43 /// DAG: the roots of the DAG (nodes that are not redirected) are each
  44 /// associated with a value of type `V` and a rank. The rank is used
  45 /// to keep the DAG relatively balanced, which helps keep the running
  46 /// time of the algorithm under control. For more information, see
  47 /// <http://en.wikipedia.org/wiki/Disjoint-set_data_structure>.
  48 #[derive(PartialEq,Clone,Debug)]
  49 pub struct VarValue<K:UnifyKey> {
  50     parent: K,       // if equal to self, this is a root
  51     value: K::Value, // value assigned (only relevant to root)
  52     rank: u32,       // max depth (only relevant to root)
  53 }
  54
  55 /// Table of unification keys and their values.
  56 pub struct UnificationTable<K:UnifyKey> {
  57     /// Indicates the current value of each key.
  58     values: sv::SnapshotVec<Delegate<K>>,
  59 }
  60
  61 /// At any time, users may snapshot a unification table.  The changes
  62 /// made during the snapshot may either be *committed* or *rolled back*.
  63 pub struct Snapshot<K:UnifyKey> {
  64     // Link snapshot to the key type `K` of the table.
  65     marker: marker::PhantomData<K>,
  66     snapshot: sv::Snapshot,
  67 }
  68
  69 #[derive(Copy, Clone)]
  70 struct Delegate<K>(PhantomData<K>);
  71
  72 impl<K:UnifyKey> VarValue<K> {
  73     fn new_var(key: K, value: K::Value) -> VarValue<K> {
  74         VarValue::new(key, value, 0)
  75     }
  76
  77     fn new(parent: K, value: K::Value, rank: u32) -> VarValue<K> {
  78         VarValue { parent: parent, // this is a root
  79                    value: value,
  80                    rank: rank }
  81     }
  82
  83     fn redirect(self, to: K) -> VarValue<K> {
  84         VarValue { parent: to, ..self }
  85     }
  86
  87     fn root(self, rank: u32, value: K::Value) -> VarValue<K> {
  88         VarValue { rank: rank, value: value, ..self }
  89     }
  90
  91     /// Returns the key of this node. Only valid if this is a root
  92     /// node, which you yourself must ensure.
  93     fn key(&self) -> K {
  94         self.parent
  95     }
  96
  97     fn parent(&self, self_key: K) -> Option<K> {
  98         self.if_not_self(self.parent, self_key)
  99     }
 100
 101     fn if_not_self(&self, key: K, self_key: K) -> Option<K> {
 102         if key == self_key {
 103             None
 104         } else {
 105             Some(key)
 106         }
 107     }
 108 }
 109
 110 // We can't use V:LatticeValue, much as I would like to,
 111 // because frequently the pattern is that V=Option<U> for some
 112 // other type parameter U, and we have no way to say
 113 // Option<U>:LatticeValue.
 114
 115 impl<K:UnifyKey> UnificationTable<K> {
 116     pub fn new() -> UnificationTable<K> {
 117         UnificationTable {
 118             values: sv::SnapshotVec::new()
 119         }
 120     }
 121
 122     /// Starts a new snapshot. Each snapshot must be either
 123     /// rolled back or committed in a "LIFO" (stack) order.
 124     pub fn snapshot(&mut self) -> Snapshot<K> {
 125         Snapshot { marker: marker::PhantomData::<K>,
 126                    snapshot: self.values.start_snapshot() }
 127     }
 128
 129     /// Reverses all changes since the last snapshot. Also
 130     /// removes any keys that have been created since then.
 131     pub fn rollback_to(&mut self, snapshot: Snapshot<K>) {
 132         debug!("{}: rollback_to()", UnifyKey::tag(None::<K>));
 133         self.values.rollback_to(snapshot.snapshot);
 134     }
 135
 136     /// Commits all changes since the last snapshot. Of course, they
 137     /// can still be undone if there is a snapshot further out.
 138     pub fn commit(&mut self, snapshot: Snapshot<K>) {
 139         debug!("{}: commit()", UnifyKey::tag(None::<K>));
 140         self.values.commit(snapshot.snapshot);
 141     }
 142
 143     pub fn new_key(&mut self, value: K::Value) -> K {
 144         let len = self.values.len();
 145         let key: K = UnifyKey::from_index(len as u32);
 146         self.values.push(VarValue::new_var(key, value));
 147         debug!("{}: created new key: {:?}",
 148                UnifyKey::tag(None::<K>),
 149                key);
 150         key
 151     }
 152
 153     /// Find the root node for `vid`. This uses the standard
 154     /// union-find algorithm with path compression:
 155     /// <http://en.wikipedia.org/wiki/Disjoint-set_data_structure>.
 156     ///
 157     /// NB. This is a building-block operation and you would probably
 158     /// prefer to call `probe` below.
 159     fn get(&mut self, vid: K) -> VarValue<K> {
 160         let index = vid.index() as usize;
 161         let mut value: VarValue<K> = self.values.get(index).clone();
 162         match value.parent(vid) {
 163             Some(redirect) => {
 164                 let root: VarValue<K> = self.get(redirect);
 165                 if root.key() != redirect {
 166                     // Path compression
 167                     value.parent = root.key();
 168                     self.values.set(index, value);
 169                 }
 170                 root
 171             }
 172             None => {
 173                 value
 174             }
 175         }
 176     }
 177
 178     fn is_root(&self, key: K) -> bool {
 179         let index = key.index() as usize;
 180         self.values.get(index).parent(key).is_none()
 181     }
 182
 183     /// Sets the value for `vid` to `new_value`. `vid` MUST be a root
 184     /// node! This is an internal operation used to impl other things.
 185     fn set(&mut self, key: K, new_value: VarValue<K>) {
 186         assert!(self.is_root(key));
 187
 188         debug!("Updating variable {:?} to {:?}",
 189                key, new_value);
 190
 191         let index = key.index() as usize;
 192         self.values.set(index, new_value);
 193     }
 194
 195     /// Either redirects `node_a` to `node_b` or vice versa, depending
 196     /// on the relative rank. The value associated with the new root
 197     /// will be `new_value`.
 198     ///
 199     /// NB: This is the "union" operation of "union-find". It is
 200     /// really more of a building block. If the values associated with
 201     /// your key are non-trivial, you would probably prefer to call
 202     /// `unify_var_var` below.
 203     fn unify(&mut self, root_a: VarValue<K>, root_b: VarValue<K>, new_value: K::Value) {
 204         debug!("unify(root_a(id={:?}, rank={:?}), root_b(id={:?}, rank={:?}))",
 205                root_a.key(),
 206                root_a.rank,
 207                root_b.key(),
 208                root_b.rank);
 209
 210         if root_a.rank > root_b.rank {
 211             // a has greater rank, so a should become b's parent,
 212             // i.e., b should redirect to a.
 213             self.redirect_root(root_a.rank, root_b, root_a, new_value);
 214         } else if root_a.rank < root_b.rank {
 215             // b has greater rank, so a should redirect to b.
 216             self.redirect_root(root_b.rank, root_a, root_b, new_value);
 217         } else {
 218             // If equal, redirect one to the other and increment the
 219             // other's rank.
 220             self.redirect_root(root_a.rank + 1, root_a, root_b, new_value);
 221         }
 222     }
 223
 224     fn redirect_root(&mut self,
 225                      new_rank: u32,
 226                      old_root: VarValue<K>,
 227                      new_root: VarValue<K>,
 228                      new_value: K::Value) {
 229         let old_root_key = old_root.key();
 230         let new_root_key = new_root.key();
 231         self.set(old_root_key, old_root.redirect(new_root_key));
 232         self.set(new_root_key, new_root.root(new_rank, new_value));
 233     }
 234 }
 235
 236 impl<K:UnifyKey> sv::SnapshotVecDelegate for Delegate<K> {
 237     type Value = VarValue<K>;
 238     type Undo = ();
 239
 240     fn reverse(_: &mut Vec<VarValue<K>>, _: ()) {}
 241 }
 242
 243 ///////////////////////////////////////////////////////////////////////////
 244 // Base union-find algorithm, where we are just making sets
 245
 246 impl<'tcx,K> UnificationTable<K>
 247     where K : UnifyKey<Value=()>,
 248 {
 249     pub fn union(&mut self, a_id: K, b_id: K) {
 250         let node_a = self.get(a_id);
 251         let node_b = self.get(b_id);
 252         let a_id = node_a.key();
 253         let b_id = node_b.key();
 254         if a_id != b_id {
 255             self.unify(node_a, node_b, ());
 256         }
 257     }
 258
 259     pub fn find(&mut self, id: K) -> K {
 260         self.get(id).key()
 261     }
 262
 263     pub fn unioned(&mut self, a_id: K, b_id: K) -> bool {
 264         self.find(a_id) == self.find(b_id)
 265     }
 266 }
 267
 268 ///////////////////////////////////////////////////////////////////////////
 269 // Code to handle keys which carry a value, like ints,
 270 // floats---anything that doesn't have a subtyping relationship we
 271 // need to worry about.
 272
 273 impl<'tcx,K,V> UnificationTable<K>
 274     where K: UnifyKey<Value=Option<V>>,
 275           V: Clone+PartialEq+Debug,
 276 {
 277     pub fn unify_var_var(&mut self,
 278                          a_id: K,
 279                          b_id: K)
 280                          -> Result<(),(V,V)>
 281     {
 282         let node_a = self.get(a_id);
 283         let node_b = self.get(b_id);
 284         let a_id = node_a.key();
 285         let b_id = node_b.key();
 286
 287         if a_id == b_id { return Ok(()); }
 288
 289         let combined = {
 290             match (&node_a.value, &node_b.value) {
 291                 (&None, &None) => {
 292                     None
 293                 }
 294                 (&Some(ref v), &None) | (&None, &Some(ref v)) => {
 295                     Some(v.clone())
 296                 }
 297                 (&Some(ref v1), &Some(ref v2)) => {
 298                     if *v1 != *v2 {
 299                         return Err((v1.clone(), v2.clone()));
 300                     }
 301                     Some(v1.clone())
 302                 }
 303             }
 304         };
 305
 306         Ok(self.unify(node_a, node_b, combined))
 307     }
 308
 309     /// Sets the value of the key `a_id` to `b`. Because simple keys do not have any subtyping
 310     /// relationships, if `a_id` already has a value, it must be the same as `b`.
 311     pub fn unify_var_value(&mut self,
 312                            a_id: K,
 313                            b: V)
 314                            -> Result<(),(V,V)>
 315     {
 316         let mut node_a = self.get(a_id);
 317
 318         match node_a.value {
 319             None => {
 320                 node_a.value = Some(b);
 321                 self.set(node_a.key(), node_a);
 322                 Ok(())
 323             }
 324
 325             Some(ref a_t) => {
 326                 if *a_t == b {
 327                     Ok(())
 328                 } else {
 329                     Err((a_t.clone(), b))
 330                 }
 331             }
 332         }
 333     }
 334
 335     pub fn has_value(&mut self, id: K) -> bool {
 336         self.get(id).value.is_some()
 337     }
 338
 339     pub fn probe(&mut self, a_id: K) -> Option<V> {
 340         self.get(a_id).value.clone()
 341     }
 342
 343     pub fn unsolved_variables(&mut self) -> Vec<K> {
 344         self.values
 345             .iter()
 346             .filter_map(|vv| if vv.value.is_some() { None } else { Some(vv.key()) })
 347             .collect()
 348     }
 349 }