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