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         panic!("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(&self) -> ty::t;
 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     fn probe_var(&self, a_id: K) -> Option<ty::t>;
 291 }
 292
 293 impl<'a,'tcx,V:SimplyUnifiable,K:UnifyKey<Option<V>>>
 294     InferCtxtMethodsForSimplyUnifiableTypes<V,K> for InferCtxt<'a, 'tcx>
 295 {
 296     fn simple_vars(&self,
 297                    a_is_expected: bool,
 298                    a_id: K,
 299                    b_id: K)
 300                    -> ures
 301     {
 302         /*!
 303          * Unifies two simple keys.  Because simple keys do
 304          * not have any subtyping relationships, if both keys
 305          * have already been associated with a value, then those two
 306          * values must be the same.
 307          */
 308
 309         let tcx = self.tcx;
 310         let table = UnifyKey::unification_table(self);
 311         let node_a = table.borrow_mut().get(tcx, a_id);
 312         let node_b = table.borrow_mut().get(tcx, b_id);
 313         let a_id = node_a.key.clone();
 314         let b_id = node_b.key.clone();
 315
 316         if a_id == b_id { return uok(); }
 317
 318         let combined = {
 319             match (&node_a.value, &node_b.value) {
 320                 (&None, &None) => {
 321                     None
 322                 }
 323                 (&Some(ref v), &None) | (&None, &Some(ref v)) => {
 324                     Some((*v).clone())
 325                 }
 326                 (&Some(ref v1), &Some(ref v2)) => {
 327                     if *v1 != *v2 {
 328                         return err(a_is_expected, (*v1).clone(), (*v2).clone())
 329                     }
 330                     Some((*v1).clone())
 331                 }
 332             }
 333         };
 334
 335         let (new_root, new_rank) = table.borrow_mut().unify(tcx,
 336                                                             &node_a,
 337                                                             &node_b);
 338         table.borrow_mut().set(tcx, new_root, Root(combined, new_rank));
 339         return Ok(())
 340     }
 341
 342     fn simple_var_t(&self,
 343                     a_is_expected: bool,
 344                     a_id: K,
 345                     b: V)
 346                     -> ures
 347     {
 348         /*!
 349          * Sets the value of the key `a_id` to `b`.  Because
 350          * simple keys do not have any subtyping relationships,
 351          * if `a_id` already has a value, it must be the same as
 352          * `b`.
 353          */
 354
 355         let tcx = self.tcx;
 356         let table = UnifyKey::unification_table(self);
 357         let node_a = table.borrow_mut().get(tcx, a_id);
 358         let a_id = node_a.key.clone();
 359
 360         match node_a.value {
 361             None => {
 362                 table.borrow_mut().set(tcx, a_id, Root(Some(b), node_a.rank));
 363                 return Ok(());
 364             }
 365
 366             Some(ref a_t) => {
 367                 if *a_t == b {
 368                     return Ok(());
 369                 } else {
 370                     return err(a_is_expected, (*a_t).clone(), b);
 371                 }
 372             }
 373         }
 374     }
 375
 376     fn probe_var(&self, a_id: K) -> Option<ty::t> {
 377         let tcx = self.tcx;
 378         let table = UnifyKey::unification_table(self);
 379         let node_a = table.borrow_mut().get(tcx, a_id);
 380         match node_a.value {
 381             None => None,
 382             Some(ref a_t) => Some(a_t.to_type())
 383         }
 384     }
 385 }
 386
 387 ///////////////////////////////////////////////////////////////////////////
 388
 389 // Integral type keys
 390
 391 impl UnifyKey<Option<IntVarValue>> for ty::IntVid {
 392     fn index(&self) -> uint { self.index }
 393
 394     fn from_index(i: uint) -> ty::IntVid { ty::IntVid { index: i } }
 395
 396     fn unification_table<'v>(infcx: &'v InferCtxt)
 397         -> &'v RefCell<UnificationTable<ty::IntVid, Option<IntVarValue>>>
 398     {
 399         return &infcx.int_unification_table;
 400     }
 401
 402     fn tag(_: Option<ty::IntVid>) -> &'static str {
 403         "IntVid"
 404     }
 405 }
 406
 407 impl SimplyUnifiable for IntVarValue {
 408     fn to_type(&self) -> ty::t {
 409         match *self {
 410             ty::IntType(i) => ty::mk_mach_int(i),
 411             ty::UintType(i) => ty::mk_mach_uint(i),
 412         }
 413     }
 414
 415     fn to_type_err(err: expected_found<IntVarValue>) -> ty::type_err {
 416         return ty::terr_int_mismatch(err);
 417     }
 418 }
 419
 420 impl UnifyValue for Option<IntVarValue> { }
 421
 422 // Floating point type keys
 423
 424 impl UnifyKey<Option<ast::FloatTy>> for ty::FloatVid {
 425     fn index(&self) -> uint { self.index }
 426
 427     fn from_index(i: uint) -> ty::FloatVid { ty::FloatVid { index: i } }
 428
 429     fn unification_table<'v>(infcx: &'v InferCtxt)
 430         -> &'v RefCell<UnificationTable<ty::FloatVid, Option<ast::FloatTy>>>
 431     {
 432         return &infcx.float_unification_table;
 433     }
 434
 435     fn tag(_: Option<ty::FloatVid>) -> &'static str {
 436         "FloatVid"
 437     }
 438 }
 439
 440 impl UnifyValue for Option<ast::FloatTy> {
 441 }
 442
 443 impl SimplyUnifiable for ast::FloatTy {
 444     fn to_type(&self) -> ty::t {
 445         ty::mk_mach_float(*self)
 446     }
 447
 448     fn to_type_err(err: expected_found<ast::FloatTy>) -> ty::type_err {
 449         return ty::terr_float_mismatch(err);
 450     }
 451 }
 452
 453 impl<K:Repr,V:Repr> Repr for VarValue<K,V> {
 454     fn repr(&self, tcx: &ty::ctxt) -> String {
 455         match *self {
 456             Redirect(ref k) => format!("Redirect({})", k.repr(tcx)),
 457             Root(ref v, r) => format!("Root({}, {})", v.repr(tcx), r)
 458         }
 459     }
 460 }