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