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