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.
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.
11 pub use self::VarValue::*;
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;
22 use util::snapshot_vec as sv;
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
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.
33 /// Implementations of this trait are at the end of this file.
34 pub trait UnifyKey : Clone + Debug + PartialEq {
35 type Value : UnifyValue;
37 fn index(&self) -> uint;
39 fn from_index(u: uint) -> Self;
41 // Given an inference context, returns the unification table
42 // appropriate to this key type.
43 fn unification_table<'v>(infcx: &'v InferCtxt)
44 -> &'v RefCell<UnificationTable<Self>>;
46 fn tag(k: Option<Self>) -> &'static str;
49 /// Trait for valid types that a type variable can be set to. Note that
50 /// this is typically not the end type that the value will take on, but
51 /// rather an `Option` wrapper (where `None` represents a variable
52 /// whose value is not yet set).
54 /// Implementations of this trait are at the end of this file.
55 pub trait UnifyValue : Clone + PartialEq + Debug {
58 /// Value of a unification key. We implement Tarjan's union-find
59 /// algorithm: when two keys are unified, one of them is converted
60 /// into a "redirect" pointing at the other. These redirects form a
61 /// DAG: the roots of the DAG (nodes that are not redirected) are each
62 /// associated with a value of type `V` and a rank. The rank is used
63 /// to keep the DAG relatively balanced, which helps keep the running
64 /// time of the algorithm under control. For more information, see
65 /// <http://en.wikipedia.org/wiki/Disjoint-set_data_structure>.
66 #[derive(PartialEq,Clone,Debug)]
67 pub enum VarValue<K:UnifyKey> {
72 /// Table of unification keys and their values.
73 pub struct UnificationTable<K:UnifyKey> {
74 /// Indicates the current value of each key.
75 values: sv::SnapshotVec<Delegate<K>>,
78 /// At any time, users may snapshot a unification table. The changes
79 /// made during the snapshot may either be *committed* or *rolled back*.
80 pub struct Snapshot<K:UnifyKey> {
81 // Link snapshot to the key type `K` of the table.
82 marker: marker::CovariantType<K>,
83 snapshot: sv::Snapshot,
86 /// Internal type used to represent the result of a `get()` operation.
87 /// Conveys the current root and value of the key.
88 pub struct Node<K:UnifyKey> {
95 pub struct Delegate<K>;
97 // We can't use V:LatticeValue, much as I would like to,
98 // because frequently the pattern is that V=Option<U> for some
99 // other type parameter U, and we have no way to say
100 // Option<U>:LatticeValue.
102 impl<K:UnifyKey> UnificationTable<K> {
103 pub fn new() -> UnificationTable<K> {
105 values: sv::SnapshotVec::new(Delegate),
109 /// Starts a new snapshot. Each snapshot must be either
110 /// rolled back or committed in a "LIFO" (stack) order.
111 pub fn snapshot(&mut self) -> Snapshot<K> {
112 Snapshot { marker: marker::CovariantType::<K>,
113 snapshot: self.values.start_snapshot() }
116 /// Reverses all changes since the last snapshot. Also
117 /// removes any keys that have been created since then.
118 pub fn rollback_to(&mut self, snapshot: Snapshot<K>) {
119 debug!("{}: rollback_to()", UnifyKey::tag(None::<K>));
120 self.values.rollback_to(snapshot.snapshot);
123 /// Commits all changes since the last snapshot. Of course, they
124 /// can still be undone if there is a snapshot further out.
125 pub fn commit(&mut self, snapshot: Snapshot<K>) {
126 debug!("{}: commit()", UnifyKey::tag(None::<K>));
127 self.values.commit(snapshot.snapshot);
130 pub fn new_key(&mut self, value: K::Value) -> K {
131 let index = self.values.push(Root(value, 0));
132 let k = UnifyKey::from_index(index);
133 debug!("{}: created new key: {:?}",
134 UnifyKey::tag(None::<K>),
139 /// Find the root node for `vid`. This uses the standard union-find algorithm with path
140 /// compression: http://en.wikipedia.org/wiki/Disjoint-set_data_structure
141 pub fn get(&mut self, tcx: &ty::ctxt, vid: K) -> Node<K> {
142 let index = vid.index();
143 let value = (*self.values.get(index)).clone();
145 Redirect(redirect) => {
146 let node: Node<K> = self.get(tcx, redirect.clone());
147 if node.key != redirect {
149 self.values.set(index, Redirect(node.key.clone()));
153 Root(value, rank) => {
154 Node { key: vid, value: value, rank: rank }
159 fn is_root(&self, key: &K) -> bool {
160 match *self.values.get(key.index()) {
161 Redirect(..) => false,
166 /// Sets the value for `vid` to `new_value`. `vid` MUST be a root node! Also, we must be in the
167 /// middle of a snapshot.
168 pub fn set<'tcx>(&mut self,
169 _tcx: &ty::ctxt<'tcx>,
171 new_value: VarValue<K>)
173 assert!(self.is_root(&key));
175 debug!("Updating variable {:?} to {:?}",
178 self.values.set(key.index(), new_value);
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
184 pub fn unify<'tcx>(&mut self,
185 tcx: &ty::ctxt<'tcx>,
190 debug!("unify(node_a(id={:?}, rank={:?}), node_b(id={:?}, rank={:?}))",
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)
206 // If equal, redirect one to the other and increment the
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)
215 impl<K:UnifyKey> sv::SnapshotVecDelegate for Delegate<K> {
216 type Value = VarValue<K>;
219 fn reverse(&mut self, _: &mut Vec<VarValue<K>>, _: ()) {
220 panic!("Nothing to reverse");
224 ///////////////////////////////////////////////////////////////////////////
225 // Code to handle simple keys like ints, floats---anything that
226 // doesn't have a subtyping relationship we need to worry about.
228 /// Indicates a type that does not have any kind of subtyping
230 pub trait SimplyUnifiable<'tcx> : Clone + PartialEq + Debug {
231 fn to_type(&self, tcx: &ty::ctxt<'tcx>) -> Ty<'tcx>;
232 fn to_type_err(expected_found<Self>) -> ty::type_err<'tcx>;
235 pub fn err<'tcx, V:SimplyUnifiable<'tcx>>(a_is_expected: bool,
240 Err(SimplyUnifiable::to_type_err(
241 ty::expected_found {expected: a_t, found: b_t}))
243 Err(SimplyUnifiable::to_type_err(
244 ty::expected_found {expected: b_t, found: a_t}))
248 pub trait InferCtxtMethodsForSimplyUnifiableTypes<'tcx,K,V>
249 where K : UnifyKey<Value=Option<V>>,
250 V : SimplyUnifiable<'tcx>,
251 Option<V> : UnifyValue,
253 fn simple_vars(&self,
258 fn simple_var_t(&self,
263 fn probe_var(&self, a_id: K) -> Option<Ty<'tcx>>;
266 impl<'a,'tcx,V,K> InferCtxtMethodsForSimplyUnifiableTypes<'tcx,K,V> for InferCtxt<'a,'tcx>
267 where K : UnifyKey<Value=Option<V>>,
268 V : SimplyUnifiable<'tcx>,
269 Option<V> : UnifyValue,
271 /// Unifies two simple keys. Because simple keys do not have any subtyping relationships, if
272 /// both keys have already been associated with a value, then those two values must be the
274 fn simple_vars(&self,
281 let table = UnifyKey::unification_table(self);
282 let node_a: Node<K> = table.borrow_mut().get(tcx, a_id);
283 let node_b: Node<K> = table.borrow_mut().get(tcx, b_id);
284 let a_id = node_a.key.clone();
285 let b_id = node_b.key.clone();
287 if a_id == b_id { return uok(); }
290 match (&node_a.value, &node_b.value) {
294 (&Some(ref v), &None) | (&None, &Some(ref v)) => {
297 (&Some(ref v1), &Some(ref v2)) => {
299 return err(a_is_expected, (*v1).clone(), (*v2).clone())
306 let (new_root, new_rank) = table.borrow_mut().unify(tcx,
309 table.borrow_mut().set(tcx, new_root, Root(combined, new_rank));
313 /// Sets the value of the key `a_id` to `b`. Because simple keys do not have any subtyping
314 /// relationships, if `a_id` already has a value, it must be the same as `b`.
315 fn simple_var_t(&self,
322 let table = UnifyKey::unification_table(self);
323 let node_a = table.borrow_mut().get(tcx, a_id);
324 let a_id = node_a.key.clone();
328 table.borrow_mut().set(tcx, a_id, Root(Some(b), node_a.rank));
336 return err(a_is_expected, (*a_t).clone(), b);
342 fn probe_var(&self, a_id: K) -> Option<Ty<'tcx>> {
344 let table = UnifyKey::unification_table(self);
345 let node_a = table.borrow_mut().get(tcx, a_id);
348 Some(ref a_t) => Some(a_t.to_type(tcx))
353 ///////////////////////////////////////////////////////////////////////////
355 // Integral type keys
357 impl UnifyKey for ty::IntVid {
358 type Value = Option<IntVarValue>;
360 fn index(&self) -> uint { self.index as uint }
362 fn from_index(i: uint) -> ty::IntVid { ty::IntVid { index: i as u32 } }
364 fn unification_table<'v>(infcx: &'v InferCtxt) -> &'v RefCell<UnificationTable<ty::IntVid>> {
365 return &infcx.int_unification_table;
368 fn tag(_: Option<ty::IntVid>) -> &'static str {
373 impl<'tcx> SimplyUnifiable<'tcx> for IntVarValue {
374 fn to_type(&self, tcx: &ty::ctxt<'tcx>) -> Ty<'tcx> {
376 ty::IntType(i) => ty::mk_mach_int(tcx, i),
377 ty::UintType(i) => ty::mk_mach_uint(tcx, i),
381 fn to_type_err(err: expected_found<IntVarValue>) -> ty::type_err<'tcx> {
382 return ty::terr_int_mismatch(err);
386 impl UnifyValue for Option<IntVarValue> { }
388 // Floating point type keys
390 impl UnifyKey for ty::FloatVid {
391 type Value = Option<ast::FloatTy>;
393 fn index(&self) -> uint { self.index as uint }
395 fn from_index(i: uint) -> ty::FloatVid { ty::FloatVid { index: i as u32 } }
397 fn unification_table<'v>(infcx: &'v InferCtxt) -> &'v RefCell<UnificationTable<ty::FloatVid>> {
398 return &infcx.float_unification_table;
401 fn tag(_: Option<ty::FloatVid>) -> &'static str {
406 impl UnifyValue for Option<ast::FloatTy> {
409 impl<'tcx> SimplyUnifiable<'tcx> for ast::FloatTy {
410 fn to_type(&self, tcx: &ty::ctxt<'tcx>) -> Ty<'tcx> {
411 ty::mk_mach_float(tcx, *self)
414 fn to_type_err(err: expected_found<ast::FloatTy>) -> ty::type_err<'tcx> {
415 ty::terr_float_mismatch(err)