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