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 std::mem;
  20 use syntax::ast;
  21 use util::ppaux::Repr;
  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     values: Vec<VarValue<K,V>>,
  86
  87     /**
  88      * When a snapshot is active, logs each change made to the table
  89      * so that they can be unrolled.
  90      */
  91     undo_log: Vec<UndoLog<K,V>>,
  92 }
  93
  94 /**
  95  * At any time, users may snapshot a unification table.  The changes
  96  * made during the snapshot may either be *committed* or *rolled back*.
  97  */
  98 pub struct Snapshot<K> {
  99     // Ensure that this snapshot is keyed to the table type.
 100     marker1: marker::CovariantType<K>,
 101
 102     // Snapshots are tokens that should be created/consumed linearly.
 103     marker2: marker::NoCopy,
 104
 105     // Length of the undo log at the time the snapshot was taken.
 106     length: uint,
 107 }
 108
 109 #[deriving(PartialEq)]
 110 enum UndoLog<K,V> {
 111     /// Indicates where a snapshot started.
 112     OpenSnapshot,
 113
 114     /// Indicates a snapshot that has been committed.
 115     CommittedSnapshot,
 116
 117     /// New variable with given index was created.
 118     NewVar(uint),
 119
 120     /// Variable with given index was changed *from* the given value.
 121     SetVar(uint, VarValue<K,V>),
 122 }
 123
 124 /**
 125  * Internal type used to represent the result of a `get()` operation.
 126  * Conveys the current root and value of the key.
 127  */
 128 pub struct Node<K,V> {
 129     pub key: K,
 130     pub value: V,
 131     pub rank: uint,
 132 }
 133
 134 // We can't use V:LatticeValue, much as I would like to,
 135 // because frequently the pattern is that V=Bounds<U> for some
 136 // other type parameter U, and we have no way to say
 137 // Bounds<U>:
 138
 139 impl<V:PartialEq+Clone+Repr,K:UnifyKey<V>> UnificationTable<K,V> {
 140     pub fn new() -> UnificationTable<K,V> {
 141         UnificationTable {
 142             values: Vec::new(),
 143             undo_log: Vec::new()
 144         }
 145     }
 146
 147     pub fn in_snapshot(&self) -> bool {
 148         /*! True if a snapshot has been started. */
 149
 150         self.undo_log.len() > 0
 151     }
 152
 153     /**
 154      * Starts a new snapshot. Each snapshot must be either
 155      * rolled back or committed in a "LIFO" (stack) order.
 156      */
 157     pub fn snapshot(&mut self) -> Snapshot<K> {
 158         let length = self.undo_log.len();
 159         debug!("{}: snapshot at length {}",
 160                UnifyKey::tag(None::<K>),
 161                length);
 162         self.undo_log.push(OpenSnapshot);
 163         Snapshot { length: length,
 164                    marker1: marker::CovariantType,
 165                    marker2: marker::NoCopy }
 166     }
 167
 168     fn assert_open_snapshot(&self, snapshot: &Snapshot<K>) {
 169         // Or else there was a failure to follow a stack discipline:
 170         assert!(self.undo_log.len() > snapshot.length);
 171
 172         // Invariant established by start_snapshot():
 173         assert!(*self.undo_log.get(snapshot.length) == OpenSnapshot);
 174     }
 175
 176     /**
 177      * Reverses all changes since the last snapshot. Also
 178      * removes any keys that have been created since then.
 179      */
 180     pub fn rollback_to(&mut self, tcx: &ty::ctxt, snapshot: Snapshot<K>) {
 181         debug!("{}: rollback_to({})",
 182                UnifyKey::tag(None::<K>),
 183                snapshot.length);
 184
 185         self.assert_open_snapshot(&snapshot);
 186
 187         while self.undo_log.len() > snapshot.length + 1 {
 188             match self.undo_log.pop().unwrap() {
 189                 OpenSnapshot => {
 190                     // This indicates a failure to obey the stack discipline.
 191                     tcx.sess.bug("Cannot rollback an uncommitted snapshot");
 192                 }
 193
 194                 CommittedSnapshot => {
 195                     // This occurs when there are nested snapshots and
 196                     // the inner is committed but outer is rolled back.
 197                 }
 198
 199                 NewVar(i) => {
 200                     assert!(self.values.len() == i);
 201                     self.values.pop();
 202                 }
 203
 204                 SetVar(i, v) => {
 205                     *self.values.get_mut(i) = v;
 206                 }
 207             }
 208         }
 209
 210         let v = self.undo_log.pop().unwrap();
 211         assert!(v == OpenSnapshot);
 212         assert!(self.undo_log.len() == snapshot.length);
 213     }
 214
 215     /**
 216      * Commits all changes since the last snapshot. Of course, they
 217      * can still be undone if there is a snapshot further out.
 218      */
 219     pub fn commit(&mut self, snapshot: Snapshot<K>) {
 220         debug!("{}: commit({})",
 221                UnifyKey::tag(None::<K>),
 222                snapshot.length);
 223
 224         self.assert_open_snapshot(&snapshot);
 225
 226         if snapshot.length == 0 {
 227             // The root snapshot.
 228             self.undo_log.truncate(0);
 229         } else {
 230             *self.undo_log.get_mut(snapshot.length) = CommittedSnapshot;
 231         }
 232     }
 233
 234     pub fn new_key(&mut self, value: V) -> K {
 235         let index = self.values.len();
 236
 237         if self.in_snapshot() {
 238             self.undo_log.push(NewVar(index));
 239         }
 240
 241         self.values.push(Root(value, 0));
 242         let k = UnifyKey::from_index(index);
 243         debug!("{}: created new key: {}",
 244                UnifyKey::tag(None::<K>),
 245                k);
 246         k
 247     }
 248
 249     fn swap_value(&mut self,
 250                   index: uint,
 251                   new_value: VarValue<K,V>)
 252                   -> VarValue<K,V>
 253     {
 254         /*!
 255          * Primitive operation to swap a value in the var array.
 256          * Caller should update the undo log if we are in a snapshot.
 257          */
 258
 259         let loc = self.values.get_mut(index);
 260         mem::replace(loc, new_value)
 261     }
 262
 263     pub fn get(&mut self, tcx: &ty::ctxt, vid: K) -> Node<K,V> {
 264         /*!
 265          * Find the root node for `vid`. This uses the standard
 266          * union-find algorithm with path compression:
 267          * http://en.wikipedia.org/wiki/Disjoint-set_data_structure
 268          */
 269
 270         let index = vid.index();
 271         let value = (*self.values.get(index)).clone();
 272         match value {
 273             Redirect(redirect) => {
 274                 let node: Node<K,V> = self.get(tcx, redirect.clone());
 275                 if node.key != redirect {
 276                     // Path compression
 277                     let old_value =
 278                         self.swap_value(index, Redirect(node.key.clone()));
 279
 280                     // If we are in a snapshot, record this compression,
 281                     // because it's possible that the unification which
 282                     // caused it will be rolled back later.
 283                     if self.in_snapshot() {
 284                         self.undo_log.push(SetVar(index, old_value));
 285                     }
 286                 }
 287                 node
 288             }
 289             Root(value, rank) => {
 290                 Node { key: vid, value: value, rank: rank }
 291             }
 292         }
 293     }
 294
 295     fn is_root(&self, key: &K) -> bool {
 296         match *self.values.get(key.index()) {
 297             Redirect(..) => false,
 298             Root(..) => true,
 299         }
 300     }
 301
 302     pub fn set(&mut self,
 303                tcx: &ty::ctxt,
 304                key: K,
 305                new_value: VarValue<K,V>)
 306     {
 307         /*!
 308          * Sets the value for `vid` to `new_value`. `vid` MUST be a
 309          * root node! Also, we must be in the middle of a snapshot.
 310          */
 311
 312         assert!(self.is_root(&key));
 313         assert!(self.in_snapshot());
 314
 315         debug!("Updating variable {} to {}",
 316                key.repr(tcx),
 317                new_value.repr(tcx));
 318
 319         let index = key.index();
 320         let old_value = self.swap_value(index, new_value);
 321         self.undo_log.push(SetVar(index, old_value));
 322     }
 323
 324     pub fn unify(&mut self,
 325                  tcx: &ty::ctxt,
 326                  node_a: &Node<K,V>,
 327                  node_b: &Node<K,V>)
 328                  -> (K, uint)
 329     {
 330         /*!
 331          * Either redirects node_a to node_b or vice versa, depending
 332          * on the relative rank. Returns the new root and rank.  You
 333          * should then update the value of the new root to something
 334          * suitable.
 335          */
 336
 337         debug!("unify(node_a(id={}, rank={}), node_b(id={}, rank={}))",
 338                node_a.key.repr(tcx),
 339                node_a.rank,
 340                node_b.key.repr(tcx),
 341                node_b.rank);
 342
 343         if node_a.rank > node_b.rank {
 344             // a has greater rank, so a should become b's parent,
 345             // i.e., b should redirect to a.
 346             self.set(tcx, node_b.key.clone(), Redirect(node_a.key.clone()));
 347             (node_a.key.clone(), node_a.rank)
 348         } else if node_a.rank < node_b.rank {
 349             // b has greater rank, so a should redirect to b.
 350             self.set(tcx, node_a.key.clone(), Redirect(node_b.key.clone()));
 351             (node_b.key.clone(), node_b.rank)
 352         } else {
 353             // If equal, redirect one to the other and increment the
 354             // other's rank.
 355             assert_eq!(node_a.rank, node_b.rank);
 356             self.set(tcx, node_b.key.clone(), Redirect(node_a.key.clone()));
 357             (node_a.key.clone(), node_a.rank + 1)
 358         }
 359     }
 360 }
 361
 362 ///////////////////////////////////////////////////////////////////////////
 363 // Code to handle simple keys like ints, floats---anything that
 364 // doesn't have a subtyping relationship we need to worry about.
 365
 366 /**
 367  * Indicates a type that does not have any kind of subtyping
 368  * relationship.
 369  */
 370 pub trait SimplyUnifiable : Clone + PartialEq + Repr {
 371     fn to_type_err(expected_found<Self>) -> ty::type_err;
 372 }
 373
 374 pub fn err<V:SimplyUnifiable>(a_is_expected: bool,
 375                               a_t: V,
 376                               b_t: V) -> ures {
 377     if a_is_expected {
 378         Err(SimplyUnifiable::to_type_err(
 379             ty::expected_found {expected: a_t, found: b_t}))
 380     } else {
 381         Err(SimplyUnifiable::to_type_err(
 382             ty::expected_found {expected: b_t, found: a_t}))
 383     }
 384 }
 385
 386 pub trait InferCtxtMethodsForSimplyUnifiableTypes<V:SimplyUnifiable,
 387                                                   K:UnifyKey<Option<V>>> {
 388     fn simple_vars(&self,
 389                    a_is_expected: bool,
 390                    a_id: K,
 391                    b_id: K)
 392                    -> ures;
 393     fn simple_var_t(&self,
 394                     a_is_expected: bool,
 395                     a_id: K,
 396                     b: V)
 397                     -> ures;
 398 }
 399
 400 impl<'tcx,V:SimplyUnifiable,K:UnifyKey<Option<V>>>
 401     InferCtxtMethodsForSimplyUnifiableTypes<V,K> for InferCtxt<'tcx>
 402 {
 403     fn simple_vars(&self,
 404                    a_is_expected: bool,
 405                    a_id: K,
 406                    b_id: K)
 407                    -> ures
 408     {
 409         /*!
 410          * Unifies two simple keys.  Because simple keys do
 411          * not have any subtyping relationships, if both keys
 412          * have already been associated with a value, then those two
 413          * values must be the same.
 414          */
 415
 416         let tcx = self.tcx;
 417         let table = UnifyKey::unification_table(self);
 418         let node_a = table.borrow_mut().get(tcx, a_id);
 419         let node_b = table.borrow_mut().get(tcx, b_id);
 420         let a_id = node_a.key.clone();
 421         let b_id = node_b.key.clone();
 422
 423         if a_id == b_id { return uok(); }
 424
 425         let combined = {
 426             match (&node_a.value, &node_b.value) {
 427                 (&None, &None) => {
 428                     None
 429                 }
 430                 (&Some(ref v), &None) | (&None, &Some(ref v)) => {
 431                     Some((*v).clone())
 432                 }
 433                 (&Some(ref v1), &Some(ref v2)) => {
 434                     if *v1 != *v2 {
 435                         return err(a_is_expected, (*v1).clone(), (*v2).clone())
 436                     }
 437                     Some((*v1).clone())
 438                 }
 439             }
 440         };
 441
 442         let (new_root, new_rank) = table.borrow_mut().unify(tcx,
 443                                                             &node_a,
 444                                                             &node_b);
 445         table.borrow_mut().set(tcx, new_root, Root(combined, new_rank));
 446         return Ok(())
 447     }
 448
 449     fn simple_var_t(&self,
 450                     a_is_expected: bool,
 451                     a_id: K,
 452                     b: V)
 453                     -> ures
 454     {
 455         /*!
 456          * Sets the value of the key `a_id` to `b`.  Because
 457          * simple keys do not have any subtyping relationships,
 458          * if `a_id` already has a value, it must be the same as
 459          * `b`.
 460          */
 461
 462         let tcx = self.tcx;
 463         let table = UnifyKey::unification_table(self);
 464         let node_a = table.borrow_mut().get(tcx, a_id);
 465         let a_id = node_a.key.clone();
 466
 467         match node_a.value {
 468             None => {
 469                 table.borrow_mut().set(tcx, a_id, Root(Some(b), node_a.rank));
 470                 return Ok(());
 471             }
 472
 473             Some(ref a_t) => {
 474                 if *a_t == b {
 475                     return Ok(());
 476                 } else {
 477                     return err(a_is_expected, (*a_t).clone(), b);
 478                 }
 479             }
 480         }
 481     }
 482 }
 483
 484 ///////////////////////////////////////////////////////////////////////////
 485
 486 // General type keys
 487
 488 impl UnifyKey<Bounds<ty::t>> for ty::TyVid {
 489     fn index(&self) -> uint { self.index }
 490
 491     fn from_index(i: uint) -> ty::TyVid { ty::TyVid { index: i } }
 492
 493     fn unification_table<'v>(infcx: &'v InferCtxt)
 494         -> &'v RefCell<UnificationTable<ty::TyVid, Bounds<ty::t>>>
 495     {
 496         return &infcx.type_unification_table;
 497     }
 498
 499     fn tag(_: Option<ty::TyVid>) -> &'static str {
 500         "TyVid"
 501     }
 502 }
 503
 504 impl UnifyValue for Bounds<ty::t> { }
 505
 506 // Integral type keys
 507
 508 impl UnifyKey<Option<IntVarValue>> for ty::IntVid {
 509     fn index(&self) -> uint { self.index }
 510
 511     fn from_index(i: uint) -> ty::IntVid { ty::IntVid { index: i } }
 512
 513     fn unification_table<'v>(infcx: &'v InferCtxt)
 514         -> &'v RefCell<UnificationTable<ty::IntVid, Option<IntVarValue>>>
 515     {
 516         return &infcx.int_unification_table;
 517     }
 518
 519     fn tag(_: Option<ty::IntVid>) -> &'static str {
 520         "IntVid"
 521     }
 522 }
 523
 524 impl SimplyUnifiable for IntVarValue {
 525     fn to_type_err(err: expected_found<IntVarValue>) -> ty::type_err {
 526         return ty::terr_int_mismatch(err);
 527     }
 528 }
 529
 530 impl UnifyValue for Option<IntVarValue> { }
 531
 532 // Floating point type keys
 533
 534 impl UnifyKey<Option<ast::FloatTy>> for ty::FloatVid {
 535     fn index(&self) -> uint { self.index }
 536
 537     fn from_index(i: uint) -> ty::FloatVid { ty::FloatVid { index: i } }
 538
 539     fn unification_table<'v>(infcx: &'v InferCtxt)
 540         -> &'v RefCell<UnificationTable<ty::FloatVid, Option<ast::FloatTy>>>
 541     {
 542         return &infcx.float_unification_table;
 543     }
 544
 545     fn tag(_: Option<ty::FloatVid>) -> &'static str {
 546         "FloatVid"
 547     }
 548 }
 549
 550 impl UnifyValue for Option<ast::FloatTy> {
 551 }
 552
 553 impl SimplyUnifiable for ast::FloatTy {
 554     fn to_type_err(err: expected_found<ast::FloatTy>) -> ty::type_err {
 555         return ty::terr_float_mismatch(err);
 556     }
 557 }
 558
 559 impl<K:Repr,V:Repr> Repr for VarValue<K,V> {
 560     fn repr(&self, tcx: &ty::ctxt) -> String {
 561         match *self {
 562             Redirect(ref k) => format!("Redirect({})", k.repr(tcx)),
 563             Root(ref v, r) => format!("Root({}, {})", v.repr(tcx), r)
 564         }
 565     }
 566 }