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.
13 use std
::marker
::PhantomData
;
14 use snapshot_vec
as sv
;
19 /// This trait is implemented by any type that can serve as a type
20 /// variable. We call such variables *unification keys*. For example,
21 /// this trait is implemented by `IntVid`, which represents integral
24 /// Each key type has an associated value type `V`. For example, for
25 /// `IntVid`, this is `Option<IntVarValue>`, representing some
26 /// (possibly not yet known) sort of integer.
28 /// Clients are expected to provide implementations of this trait; you
29 /// can see some examples in the `test` module.
30 pub trait UnifyKey
: Copy
+ Clone
+ Debug
+ PartialEq
{
31 type Value
: Clone
+ PartialEq
+ Debug
;
33 fn index(&self) -> u32;
35 fn from_index(u
: u32) -> Self;
37 fn tag(k
: Option
<Self>) -> &'
static str;
40 /// This trait is implemented for unify values that can be
41 /// combined. This relation should be a monoid.
43 fn combine(&self, other
: &Self) -> Self;
47 fn combine(&self, _other
: &()) {}
50 /// Value of a unification key. We implement Tarjan's union-find
51 /// algorithm: when two keys are unified, one of them is converted
52 /// into a "redirect" pointing at the other. These redirects form a
53 /// DAG: the roots of the DAG (nodes that are not redirected) are each
54 /// associated with a value of type `V` and a rank. The rank is used
55 /// to keep the DAG relatively balanced, which helps keep the running
56 /// time of the algorithm under control. For more information, see
57 /// <http://en.wikipedia.org/wiki/Disjoint-set_data_structure>.
58 #[derive(PartialEq,Clone,Debug)]
59 pub struct VarValue
<K
:UnifyKey
> {
60 parent
: K
, // if equal to self, this is a root
61 value
: K
::Value
, // value assigned (only relevant to root)
62 rank
: u32, // max depth (only relevant to root)
65 /// Table of unification keys and their values.
66 pub struct UnificationTable
<K
:UnifyKey
> {
67 /// Indicates the current value of each key.
68 values
: sv
::SnapshotVec
<Delegate
<K
>>,
71 /// At any time, users may snapshot a unification table. The changes
72 /// made during the snapshot may either be *committed* or *rolled back*.
73 pub struct Snapshot
<K
:UnifyKey
> {
74 // Link snapshot to the key type `K` of the table.
75 marker
: marker
::PhantomData
<K
>,
76 snapshot
: sv
::Snapshot
,
79 #[derive(Copy, Clone)]
80 struct Delegate
<K
>(PhantomData
<K
>);
82 impl<K
:UnifyKey
> VarValue
<K
> {
83 fn new_var(key
: K
, value
: K
::Value
) -> VarValue
<K
> {
84 VarValue
::new(key
, value
, 0)
87 fn new(parent
: K
, value
: K
::Value
, rank
: u32) -> VarValue
<K
> {
88 VarValue
{ parent
: parent
, // this is a root
93 fn redirect(self, to
: K
) -> VarValue
<K
> {
94 VarValue { parent: to, ..self }
97 fn root(self, rank
: u32, value
: K
::Value
) -> VarValue
<K
> {
98 VarValue { rank: rank, value: value, ..self }
101 /// Returns the key of this node. Only valid if this is a root
102 /// node, which you yourself must ensure.
107 fn parent(&self, self_key
: K
) -> Option
<K
> {
108 self.if_not_self(self.parent
, self_key
)
111 fn if_not_self(&self, key
: K
, self_key
: K
) -> Option
<K
> {
120 // We can't use V:LatticeValue, much as I would like to,
121 // because frequently the pattern is that V=Option<U> for some
122 // other type parameter U, and we have no way to say
123 // Option<U>:LatticeValue.
125 impl<K
:UnifyKey
> UnificationTable
<K
> {
126 pub fn new() -> UnificationTable
<K
> {
128 values
: sv
::SnapshotVec
::new()
132 /// Starts a new snapshot. Each snapshot must be either
133 /// rolled back or committed in a "LIFO" (stack) order.
134 pub fn snapshot(&mut self) -> Snapshot
<K
> {
135 Snapshot
{ marker
: marker
::PhantomData
::<K
>,
136 snapshot
: self.values
.start_snapshot() }
139 /// Reverses all changes since the last snapshot. Also
140 /// removes any keys that have been created since then.
141 pub fn rollback_to(&mut self, snapshot
: Snapshot
<K
>) {
142 debug
!("{}: rollback_to()", UnifyKey
::tag(None
::<K
>));
143 self.values
.rollback_to(snapshot
.snapshot
);
146 /// Commits all changes since the last snapshot. Of course, they
147 /// can still be undone if there is a snapshot further out.
148 pub fn commit(&mut self, snapshot
: Snapshot
<K
>) {
149 debug
!("{}: commit()", UnifyKey
::tag(None
::<K
>));
150 self.values
.commit(snapshot
.snapshot
);
153 pub fn new_key(&mut self, value
: K
::Value
) -> K
{
154 let len
= self.values
.len();
155 let key
: K
= UnifyKey
::from_index(len
as u32);
156 self.values
.push(VarValue
::new_var(key
, value
));
157 debug
!("{}: created new key: {:?}",
158 UnifyKey
::tag(None
::<K
>),
163 /// Find the root node for `vid`. This uses the standard
164 /// union-find algorithm with path compression:
165 /// <http://en.wikipedia.org/wiki/Disjoint-set_data_structure>.
167 /// NB. This is a building-block operation and you would probably
168 /// prefer to call `probe` below.
169 fn get(&mut self, vid
: K
) -> VarValue
<K
> {
170 let index
= vid
.index() as usize;
171 let mut value
: VarValue
<K
> = self.values
.get(index
).clone();
172 match value
.parent(vid
) {
174 let root
: VarValue
<K
> = self.get(redirect
);
175 if root
.key() != redirect
{
177 value
.parent
= root
.key();
178 self.values
.set(index
, value
);
188 fn is_root(&self, key
: K
) -> bool
{
189 let index
= key
.index() as usize;
190 self.values
.get(index
).parent(key
).is_none()
193 /// Sets the value for `vid` to `new_value`. `vid` MUST be a root
194 /// node! This is an internal operation used to impl other things.
195 fn set(&mut self, key
: K
, new_value
: VarValue
<K
>) {
196 assert
!(self.is_root(key
));
198 debug
!("Updating variable {:?} to {:?}",
201 let index
= key
.index() as usize;
202 self.values
.set(index
, new_value
);
205 /// Either redirects `node_a` to `node_b` or vice versa, depending
206 /// on the relative rank. The value associated with the new root
207 /// will be `new_value`.
209 /// NB: This is the "union" operation of "union-find". It is
210 /// really more of a building block. If the values associated with
211 /// your key are non-trivial, you would probably prefer to call
212 /// `unify_var_var` below.
213 fn unify(&mut self, root_a
: VarValue
<K
>, root_b
: VarValue
<K
>, new_value
: K
::Value
) {
214 debug
!("unify(root_a(id={:?}, rank={:?}), root_b(id={:?}, rank={:?}))",
220 if root_a
.rank
> root_b
.rank
{
221 // a has greater rank, so a should become b's parent,
222 // i.e., b should redirect to a.
223 self.redirect_root(root_a
.rank
, root_b
, root_a
, new_value
);
224 } else if root_a
.rank
< root_b
.rank
{
225 // b has greater rank, so a should redirect to b.
226 self.redirect_root(root_b
.rank
, root_a
, root_b
, new_value
);
228 // If equal, redirect one to the other and increment the
230 self.redirect_root(root_a
.rank
+ 1, root_a
, root_b
, new_value
);
234 fn redirect_root(&mut self,
236 old_root
: VarValue
<K
>,
237 new_root
: VarValue
<K
>,
238 new_value
: K
::Value
) {
239 let old_root_key
= old_root
.key();
240 let new_root_key
= new_root
.key();
241 self.set(old_root_key
, old_root
.redirect(new_root_key
));
242 self.set(new_root_key
, new_root
.root(new_rank
, new_value
));
246 impl<K
:UnifyKey
> sv
::SnapshotVecDelegate
for Delegate
<K
> {
247 type Value
= VarValue
<K
>;
250 fn reverse(_
: &mut Vec
<VarValue
<K
>>, _
: ()) {}
253 ///////////////////////////////////////////////////////////////////////////
254 // Base union-find algorithm, where we are just making sets
256 impl<'tcx
,K
:UnifyKey
> UnificationTable
<K
>
257 where K
::Value
: Combine
259 pub fn union(&mut self, a_id
: K
, b_id
: K
) {
260 let node_a
= self.get(a_id
);
261 let node_b
= self.get(b_id
);
262 let a_id
= node_a
.key();
263 let b_id
= node_b
.key();
265 let new_value
= node_a
.value
.combine(&node_b
.value
);
266 self.unify(node_a
, node_b
, new_value
);
270 pub fn find(&mut self, id
: K
) -> K
{
274 pub fn find_value(&mut self, id
: K
) -> K
::Value
{
278 pub fn unioned(&mut self, a_id
: K
, b_id
: K
) -> bool
{
279 self.find(a_id
) == self.find(b_id
)
283 ///////////////////////////////////////////////////////////////////////////
284 // Code to handle keys which carry a value, like ints,
285 // floats---anything that doesn't have a subtyping relationship we
286 // need to worry about.
288 impl<'tcx
,K
,V
> UnificationTable
<K
>
289 where K
: UnifyKey
<Value
=Option
<V
>>,
290 V
: Clone
+PartialEq
+Debug
,
292 pub fn unify_var_var(&mut self,
297 let node_a
= self.get(a_id
);
298 let node_b
= self.get(b_id
);
299 let a_id
= node_a
.key();
300 let b_id
= node_b
.key();
302 if a_id
== b_id { return Ok(()); }
305 match (&node_a
.value
, &node_b
.value
) {
309 (&Some(ref v
), &None
) | (&None
, &Some(ref v
)) => {
312 (&Some(ref v1
), &Some(ref v2
)) => {
314 return Err((v1
.clone(), v2
.clone()));
321 Ok(self.unify(node_a
, node_b
, combined
))
324 /// Sets the value of the key `a_id` to `b`. Because simple keys do not have any subtyping
325 /// relationships, if `a_id` already has a value, it must be the same as `b`.
326 pub fn unify_var_value(&mut self,
331 let mut node_a
= self.get(a_id
);
335 node_a
.value
= Some(b
);
336 self.set(node_a
.key(), node_a
);
344 Err((a_t
.clone(), b
))
350 pub fn has_value(&mut self, id
: K
) -> bool
{
351 self.get(id
).value
.is_some()
354 pub fn probe(&mut self, a_id
: K
) -> Option
<V
> {
355 self.get(a_id
).value
.clone()
358 pub fn unsolved_variables(&mut self) -> Vec
<K
> {
361 .filter_map(|vv
| if vv
.value
.is_some() { None }
else { Some(vv.key()) }
)