use std::marker;
use std::fmt::Debug;
use std::marker::PhantomData;
use snapshot_vec as sv;
#[cfg(test)]
mod tests;
pub trait UnifyKey: Copy + Clone + Debug + PartialEq {
type Value: Clone + PartialEq + Debug;
fn index(&self) -> u32;
fn from_index(u: u32) -> Self;
fn tag(k: Option<Self>) -> &'static str;
}
pub trait Combine {
fn combine(&self, other: &Self) -> Self;
}
impl Combine for () {
fn combine(&self, _other: &()) {}
}
#[derive(PartialEq,Clone,Debug)]
pub struct VarValue<K: UnifyKey> {
parent: K, value: K::Value, rank: u32, }
pub struct UnificationTable<K: UnifyKey> {
values: sv::SnapshotVec<Delegate<K>>,
}
pub struct Snapshot<K: UnifyKey> {
marker: marker::PhantomData<K>,
snapshot: sv::Snapshot,
}
#[derive(Copy, Clone)]
struct Delegate<K>(PhantomData<K>);
impl<K: UnifyKey> VarValue<K> {
fn new_var(key: K, value: K::Value) -> VarValue<K> {
VarValue::new(key, value, 0)
}
fn new(parent: K, value: K::Value, rank: u32) -> VarValue<K> {
VarValue {
parent: parent, value,
rank,
}
}
fn redirect(self, to: K) -> VarValue<K> {
VarValue { parent: to, ..self }
}
fn root(self, rank: u32, value: K::Value) -> VarValue<K> {
VarValue {
rank,
value,
..self
}
}
fn key(&self) -> K {
self.parent
}
fn parent(&self, self_key: K) -> Option<K> {
self.if_not_self(self.parent, self_key)
}
fn if_not_self(&self, key: K, self_key: K) -> Option<K> {
if key == self_key { None } else { Some(key) }
}
}
impl<K: UnifyKey> UnificationTable<K> {
pub fn new() -> UnificationTable<K> {
UnificationTable { values: sv::SnapshotVec::new() }
}
pub fn snapshot(&mut self) -> Snapshot<K> {
Snapshot {
marker: marker::PhantomData::<K>,
snapshot: self.values.start_snapshot(),
}
}
pub fn rollback_to(&mut self, snapshot: Snapshot<K>) {
debug!("{}: rollback_to()", UnifyKey::tag(None::<K>));
self.values.rollback_to(snapshot.snapshot);
}
pub fn commit(&mut self, snapshot: Snapshot<K>) {
debug!("{}: commit()", UnifyKey::tag(None::<K>));
self.values.commit(snapshot.snapshot);
}
pub fn new_key(&mut self, value: K::Value) -> K {
let len = self.values.len();
let key: K = UnifyKey::from_index(len as u32);
self.values.push(VarValue::new_var(key, value));
debug!("{}: created new key: {:?}", UnifyKey::tag(None::<K>), key);
key
}
fn get(&mut self, vid: K) -> VarValue<K> {
let index = vid.index() as usize;
let mut value: VarValue<K> = self.values.get(index).clone();
match value.parent(vid) {
Some(redirect) => {
let root: VarValue<K> = self.get(redirect);
if root.key() != redirect {
value.parent = root.key();
self.values.set(index, value);
}
root
}
None => value,
}
}
fn is_root(&self, key: K) -> bool {
let index = key.index() as usize;
self.values.get(index).parent(key).is_none()
}
fn set(&mut self, key: K, new_value: VarValue<K>) {
assert!(self.is_root(key));
debug!("Updating variable {:?} to {:?}", key, new_value);
let index = key.index() as usize;
self.values.set(index, new_value);
}
fn unify(&mut self, root_a: VarValue<K>, root_b: VarValue<K>, new_value: K::Value) -> K {
debug!("unify(root_a(id={:?}, rank={:?}), root_b(id={:?}, rank={:?}))",
root_a.key(),
root_a.rank,
root_b.key(),
root_b.rank);
if root_a.rank > root_b.rank {
self.redirect_root(root_a.rank, root_b, root_a, new_value)
} else if root_a.rank < root_b.rank {
self.redirect_root(root_b.rank, root_a, root_b, new_value)
} else {
self.redirect_root(root_a.rank + 1, root_a, root_b, new_value)
}
}
fn redirect_root(&mut self,
new_rank: u32,
old_root: VarValue<K>,
new_root: VarValue<K>,
new_value: K::Value)
-> K {
let old_root_key = old_root.key();
let new_root_key = new_root.key();
self.set(old_root_key, old_root.redirect(new_root_key));
self.set(new_root_key, new_root.root(new_rank, new_value));
new_root_key
}
}
impl<K: UnifyKey> sv::SnapshotVecDelegate for Delegate<K> {
type Value = VarValue<K>;
type Undo = ();
fn reverse(_: &mut Vec<VarValue<K>>, _: ()) {}
}
impl<'tcx, K: UnifyKey> UnificationTable<K>
where K::Value: Combine
{
pub fn union(&mut self, a_id: K, b_id: K) -> K {
let node_a = self.get(a_id);
let node_b = self.get(b_id);
let a_id = node_a.key();
let b_id = node_b.key();
if a_id != b_id {
let new_value = node_a.value.combine(&node_b.value);
self.unify(node_a, node_b, new_value)
} else {
a_id
}
}
pub fn find(&mut self, id: K) -> K {
self.get(id).key()
}
pub fn find_value(&mut self, id: K) -> K::Value {
self.get(id).value
}
#[cfg(test)]
fn unioned(&mut self, a_id: K, b_id: K) -> bool {
self.find(a_id) == self.find(b_id)
}
}
impl<'tcx, K, V> UnificationTable<K>
where K: UnifyKey<Value = Option<V>>,
V: Clone + PartialEq + Debug
{
pub fn unify_var_var(&mut self, a_id: K, b_id: K) -> Result<K, (V, V)> {
let node_a = self.get(a_id);
let node_b = self.get(b_id);
let a_id = node_a.key();
let b_id = node_b.key();
if a_id == b_id {
return Ok(a_id);
}
let combined = {
match (&node_a.value, &node_b.value) {
(&None, &None) => None,
(&Some(ref v), &None) |
(&None, &Some(ref v)) => Some(v.clone()),
(&Some(ref v1), &Some(ref v2)) => {
if *v1 != *v2 {
return Err((v1.clone(), v2.clone()));
}
Some(v1.clone())
}
}
};
Ok(self.unify(node_a, node_b, combined))
}
pub fn unify_var_value(&mut self, a_id: K, b: V) -> Result<(), (V, V)> {
let mut node_a = self.get(a_id);
match node_a.value {
None => {
node_a.value = Some(b);
self.set(node_a.key(), node_a);
Ok(())
}
Some(ref a_t) => {
if *a_t == b {
Ok(())
} else {
Err((a_t.clone(), b))
}
}
}
}
pub fn has_value(&mut self, id: K) -> bool {
self.get(id).value.is_some()
}
pub fn probe(&mut self, a_id: K) -> Option<V> {
self.get(a_id).value
}
pub fn unsolved_variables(&mut self) -> Vec<K> {
self.values
.iter()
.filter_map(|vv| {
if vv.value.is_some() {
None
} else {
Some(vv.key())
}
})
.collect()
}
}