src/librustc/middle/infer/unify.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 pub use self::VarValue::*;
  12
  13 use std::marker;
  14
  15 use middle::ty::{expected_found, IntVarValue};
  16 use middle::ty::{self, Ty};
  17 use middle::infer::{uok, ures};
  18 use middle::infer::InferCtxt;
  19 use std::cell::RefCell;
  20 use std::fmt::Debug;
  21 use std::marker::PhantomData;
  22 use syntax::ast;
  23 use util::snapshot_vec as sv;
  24
  25 /// This trait is implemented by any type that can serve as a type
  26 /// variable. We call such variables *unification keys*. For example,
  27 /// this trait is implemented by `IntVid`, which represents integral
  28 /// variables.
  29 ///
  30 /// Each key type has an associated value type `V`. For example, for
  31 /// `IntVid`, this is `Option<IntVarValue>`, representing some
  32 /// (possibly not yet known) sort of integer.
  33 ///
  34 /// Implementations of this trait are at the end of this file.
  35 pub trait UnifyKey : Clone + Debug + PartialEq {
  36     type Value : UnifyValue;
  37
  38     fn index(&self) -> uint;
  39
  40     fn from_index(u: uint) -> Self;
  41
  42     // Given an inference context, returns the unification table
  43     // appropriate to this key type.
  44     fn unification_table<'v>(infcx: &'v InferCtxt)
  45                              -> &'v RefCell<UnificationTable<Self>>;
  46
  47     fn tag(k: Option<Self>) -> &'static str;
  48 }
  49
  50 /// Trait for valid types that a type variable can be set to. Note that
  51 /// this is typically not the end type that the value will take on, but
  52 /// rather an `Option` wrapper (where `None` represents a variable
  53 /// whose value is not yet set).
  54 ///
  55 /// Implementations of this trait are at the end of this file.
  56 pub trait UnifyValue : Clone + PartialEq + Debug {
  57 }
  58
  59 /// Value of a unification key. We implement Tarjan's union-find
  60 /// algorithm: when two keys are unified, one of them is converted
  61 /// into a "redirect" pointing at the other. These redirects form a
  62 /// DAG: the roots of the DAG (nodes that are not redirected) are each
  63 /// associated with a value of type `V` and a rank. The rank is used
  64 /// to keep the DAG relatively balanced, which helps keep the running
  65 /// time of the algorithm under control. For more information, see
  66 /// <http://en.wikipedia.org/wiki/Disjoint-set_data_structure>.
  67 #[derive(PartialEq,Clone,Debug)]
  68 pub enum VarValue<K:UnifyKey> {
  69     Redirect(K),
  70     Root(K::Value, uint),
  71 }
  72
  73 /// Table of unification keys and their values.
  74 pub struct UnificationTable<K:UnifyKey> {
  75     /// Indicates the current value of each key.
  76     values: sv::SnapshotVec<Delegate<K>>,
  77 }
  78
  79 /// At any time, users may snapshot a unification table.  The changes
  80 /// made during the snapshot may either be *committed* or *rolled back*.
  81 pub struct Snapshot<K:UnifyKey> {
  82     // Link snapshot to the key type `K` of the table.
  83     marker: marker::PhantomData<K>,
  84     snapshot: sv::Snapshot,
  85 }
  86
  87 /// Internal type used to represent the result of a `get()` operation.
  88 /// Conveys the current root and value of the key.
  89 pub struct Node<K:UnifyKey> {
  90     pub key: K,
  91     pub value: K::Value,
  92     pub rank: uint,
  93 }
  94
  95 #[derive(Copy)]
  96 pub struct Delegate<K>(PhantomData<K>);
  97
  98 // We can't use V:LatticeValue, much as I would like to,
  99 // because frequently the pattern is that V=Option<U> for some
 100 // other type parameter U, and we have no way to say
 101 // Option<U>:LatticeValue.
 102
 103 impl<K:UnifyKey> UnificationTable<K> {
 104     pub fn new() -> UnificationTable<K> {
 105         UnificationTable {
 106             values: sv::SnapshotVec::new(Delegate(PhantomData)),
 107         }
 108     }
 109
 110     /// Starts a new snapshot. Each snapshot must be either
 111     /// rolled back or committed in a "LIFO" (stack) order.
 112     pub fn snapshot(&mut self) -> Snapshot<K> {
 113         Snapshot { marker: marker::PhantomData::<K>,
 114                    snapshot: self.values.start_snapshot() }
 115     }
 116
 117     /// Reverses all changes since the last snapshot. Also
 118     /// removes any keys that have been created since then.
 119     pub fn rollback_to(&mut self, snapshot: Snapshot<K>) {
 120         debug!("{}: rollback_to()", UnifyKey::tag(None::<K>));
 121         self.values.rollback_to(snapshot.snapshot);
 122     }
 123
 124     /// Commits all changes since the last snapshot. Of course, they
 125     /// can still be undone if there is a snapshot further out.
 126     pub fn commit(&mut self, snapshot: Snapshot<K>) {
 127         debug!("{}: commit()", UnifyKey::tag(None::<K>));
 128         self.values.commit(snapshot.snapshot);
 129     }
 130
 131     pub fn new_key(&mut self, value: K::Value) -> K {
 132         let index = self.values.push(Root(value, 0));
 133         let k = UnifyKey::from_index(index);
 134         debug!("{}: created new key: {:?}",
 135                UnifyKey::tag(None::<K>),
 136                k);
 137         k
 138     }
 139
 140     /// Find the root node for `vid`. This uses the standard union-find algorithm with path
 141     /// compression: http://en.wikipedia.org/wiki/Disjoint-set_data_structure
 142     pub fn get(&mut self, tcx: &ty::ctxt, vid: K) -> Node<K> {
 143         let index = vid.index();
 144         let value = (*self.values.get(index)).clone();
 145         match value {
 146             Redirect(redirect) => {
 147                 let node: Node<K> = self.get(tcx, redirect.clone());
 148                 if node.key != redirect {
 149                     // Path compression
 150                     self.values.set(index, Redirect(node.key.clone()));
 151                 }
 152                 node
 153             }
 154             Root(value, rank) => {
 155                 Node { key: vid, value: value, rank: rank }
 156             }
 157         }
 158     }
 159
 160     fn is_root(&self, key: &K) -> bool {
 161         match *self.values.get(key.index()) {
 162             Redirect(..) => false,
 163             Root(..) => true,
 164         }
 165     }
 166
 167     /// Sets the value for `vid` to `new_value`. `vid` MUST be a root node! Also, we must be in the
 168     /// middle of a snapshot.
 169     pub fn set<'tcx>(&mut self,
 170                      _tcx: &ty::ctxt<'tcx>,
 171                      key: K,
 172                      new_value: VarValue<K>)
 173     {
 174         assert!(self.is_root(&key));
 175
 176         debug!("Updating variable {:?} to {:?}",
 177                key, new_value);
 178
 179         self.values.set(key.index(), new_value);
 180     }
 181
 182     /// Either redirects node_a to node_b or vice versa, depending on the relative rank. Returns
 183     /// the new root and rank. You should then update the value of the new root to something
 184     /// suitable.
 185     pub fn unify<'tcx>(&mut self,
 186                        tcx: &ty::ctxt<'tcx>,
 187                        node_a: &Node<K>,
 188                        node_b: &Node<K>)
 189                        -> (K, uint)
 190     {
 191         debug!("unify(node_a(id={:?}, rank={:?}), node_b(id={:?}, rank={:?}))",
 192                node_a.key,
 193                node_a.rank,
 194                node_b.key,
 195                node_b.rank);
 196
 197         if node_a.rank > node_b.rank {
 198             // a has greater rank, so a should become b's parent,
 199             // i.e., b should redirect to a.
 200             self.set(tcx, node_b.key.clone(), Redirect(node_a.key.clone()));
 201             (node_a.key.clone(), node_a.rank)
 202         } else if node_a.rank < node_b.rank {
 203             // b has greater rank, so a should redirect to b.
 204             self.set(tcx, node_a.key.clone(), Redirect(node_b.key.clone()));
 205             (node_b.key.clone(), node_b.rank)
 206         } else {
 207             // If equal, redirect one to the other and increment the
 208             // other's rank.
 209             assert_eq!(node_a.rank, node_b.rank);
 210             self.set(tcx, node_b.key.clone(), Redirect(node_a.key.clone()));
 211             (node_a.key.clone(), node_a.rank + 1)
 212         }
 213     }
 214 }
 215
 216 impl<K:UnifyKey> sv::SnapshotVecDelegate for Delegate<K> {
 217     type Value = VarValue<K>;
 218     type Undo = ();
 219
 220     fn reverse(&mut self, _: &mut Vec<VarValue<K>>, _: ()) {
 221         panic!("Nothing to reverse");
 222     }
 223 }
 224
 225 ///////////////////////////////////////////////////////////////////////////
 226 // Code to handle simple keys like ints, floats---anything that
 227 // doesn't have a subtyping relationship we need to worry about.
 228
 229 /// Indicates a type that does not have any kind of subtyping
 230 /// relationship.
 231 pub trait SimplyUnifiable<'tcx> : Clone + PartialEq + Debug {
 232     fn to_type(&self, tcx: &ty::ctxt<'tcx>) -> Ty<'tcx>;
 233     fn to_type_err(expected_found<Self>) -> ty::type_err<'tcx>;
 234 }
 235
 236 pub fn err<'tcx, V:SimplyUnifiable<'tcx>>(a_is_expected: bool,
 237                                           a_t: V,
 238                                           b_t: V)
 239                                           -> ures<'tcx> {
 240     if a_is_expected {
 241         Err(SimplyUnifiable::to_type_err(
 242             ty::expected_found {expected: a_t, found: b_t}))
 243     } else {
 244         Err(SimplyUnifiable::to_type_err(
 245             ty::expected_found {expected: b_t, found: a_t}))
 246     }
 247 }
 248
 249 pub trait InferCtxtMethodsForSimplyUnifiableTypes<'tcx,K,V>
 250     where K : UnifyKey<Value=Option<V>>,
 251           V : SimplyUnifiable<'tcx>,
 252           Option<V> : UnifyValue,
 253 {
 254     fn simple_vars(&self,
 255                    a_is_expected: bool,
 256                    a_id: K,
 257                    b_id: K)
 258                    -> ures<'tcx>;
 259     fn simple_var_t(&self,
 260                     a_is_expected: bool,
 261                     a_id: K,
 262                     b: V)
 263                     -> ures<'tcx>;
 264     fn probe_var(&self, a_id: K) -> Option<Ty<'tcx>>;
 265 }
 266
 267 impl<'a,'tcx,V,K> InferCtxtMethodsForSimplyUnifiableTypes<'tcx,K,V> for InferCtxt<'a,'tcx>
 268     where K : UnifyKey<Value=Option<V>>,
 269           V : SimplyUnifiable<'tcx>,
 270           Option<V> : UnifyValue,
 271 {
 272     /// Unifies two simple keys. Because simple keys do not have any subtyping relationships, if
 273     /// both keys have already been associated with a value, then those two values must be the
 274     /// same.
 275     fn simple_vars(&self,
 276                    a_is_expected: bool,
 277                    a_id: K,
 278                    b_id: K)
 279                    -> ures<'tcx>
 280     {
 281         let tcx = self.tcx;
 282         let table = UnifyKey::unification_table(self);
 283         let node_a: Node<K> = table.borrow_mut().get(tcx, a_id);
 284         let node_b: Node<K> = table.borrow_mut().get(tcx, b_id);
 285         let a_id = node_a.key.clone();
 286         let b_id = node_b.key.clone();
 287
 288         if a_id == b_id { return uok(); }
 289
 290         let combined = {
 291             match (&node_a.value, &node_b.value) {
 292                 (&None, &None) => {
 293                     None
 294                 }
 295                 (&Some(ref v), &None) | (&None, &Some(ref v)) => {
 296                     Some((*v).clone())
 297                 }
 298                 (&Some(ref v1), &Some(ref v2)) => {
 299                     if *v1 != *v2 {
 300                         return err(a_is_expected, (*v1).clone(), (*v2).clone())
 301                     }
 302                     Some((*v1).clone())
 303                 }
 304             }
 305         };
 306
 307         let (new_root, new_rank) = table.borrow_mut().unify(tcx,
 308                                                             &node_a,
 309                                                             &node_b);
 310         table.borrow_mut().set(tcx, new_root, Root(combined, new_rank));
 311         return Ok(())
 312     }
 313
 314     /// Sets the value of the key `a_id` to `b`. Because simple keys do not have any subtyping
 315     /// relationships, if `a_id` already has a value, it must be the same as `b`.
 316     fn simple_var_t(&self,
 317                     a_is_expected: bool,
 318                     a_id: K,
 319                     b: V)
 320                     -> ures<'tcx>
 321     {
 322         let tcx = self.tcx;
 323         let table = UnifyKey::unification_table(self);
 324         let node_a = table.borrow_mut().get(tcx, a_id);
 325         let a_id = node_a.key.clone();
 326
 327         match node_a.value {
 328             None => {
 329                 table.borrow_mut().set(tcx, a_id, Root(Some(b), node_a.rank));
 330                 return Ok(());
 331             }
 332
 333             Some(ref a_t) => {
 334                 if *a_t == b {
 335                     return Ok(());
 336                 } else {
 337                     return err(a_is_expected, (*a_t).clone(), b);
 338                 }
 339             }
 340         }
 341     }
 342
 343     fn probe_var(&self, a_id: K) -> Option<Ty<'tcx>> {
 344         let tcx = self.tcx;
 345         let table = UnifyKey::unification_table(self);
 346         let node_a = table.borrow_mut().get(tcx, a_id);
 347         match node_a.value {
 348             None => None,
 349             Some(ref a_t) => Some(a_t.to_type(tcx))
 350         }
 351     }
 352 }
 353
 354 ///////////////////////////////////////////////////////////////////////////
 355
 356 // Integral type keys
 357
 358 impl UnifyKey for ty::IntVid {
 359     type Value = Option<IntVarValue>;
 360
 361     fn index(&self) -> uint { self.index as uint }
 362
 363     fn from_index(i: uint) -> ty::IntVid { ty::IntVid { index: i as u32 } }
 364
 365     fn unification_table<'v>(infcx: &'v InferCtxt) -> &'v RefCell<UnificationTable<ty::IntVid>> {
 366         return &infcx.int_unification_table;
 367     }
 368
 369     fn tag(_: Option<ty::IntVid>) -> &'static str {
 370         "IntVid"
 371     }
 372 }
 373
 374 impl<'tcx> SimplyUnifiable<'tcx> for IntVarValue {
 375     fn to_type(&self, tcx: &ty::ctxt<'tcx>) -> Ty<'tcx> {
 376         match *self {
 377             ty::IntType(i) => ty::mk_mach_int(tcx, i),
 378             ty::UintType(i) => ty::mk_mach_uint(tcx, i),
 379         }
 380     }
 381
 382     fn to_type_err(err: expected_found<IntVarValue>) -> ty::type_err<'tcx> {
 383         return ty::terr_int_mismatch(err);
 384     }
 385 }
 386
 387 impl UnifyValue for Option<IntVarValue> { }
 388
 389 // Floating point type keys
 390
 391 impl UnifyKey for ty::FloatVid {
 392     type Value = Option<ast::FloatTy>;
 393
 394     fn index(&self) -> uint { self.index as uint }
 395
 396     fn from_index(i: uint) -> ty::FloatVid { ty::FloatVid { index: i as u32 } }
 397
 398     fn unification_table<'v>(infcx: &'v InferCtxt) -> &'v RefCell<UnificationTable<ty::FloatVid>> {
 399         return &infcx.float_unification_table;
 400     }
 401
 402     fn tag(_: Option<ty::FloatVid>) -> &'static str {
 403         "FloatVid"
 404     }
 405 }
 406
 407 impl UnifyValue for Option<ast::FloatTy> {
 408 }
 409
 410 impl<'tcx> SimplyUnifiable<'tcx> for ast::FloatTy {
 411     fn to_type(&self, tcx: &ty::ctxt<'tcx>) -> Ty<'tcx> {
 412         ty::mk_mach_float(tcx, *self)
 413     }
 414
 415     fn to_type_err(err: expected_found<ast::FloatTy>) -> ty::type_err<'tcx> {
 416         ty::terr_float_mismatch(err)
 417     }
 418 }