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