summaryrefslogtreecommitdiffstats
path: root/vendor/ena/src
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--vendor/ena/src/bitvec.rs301
-rw-r--r--vendor/ena/src/lib.rs24
-rw-r--r--vendor/ena/src/snapshot_vec.rs441
-rw-r--r--vendor/ena/src/undo_log.rs248
-rw-r--r--vendor/ena/src/unify/backing_vec.rs263
-rw-r--r--vendor/ena/src/unify/mod.rs594
-rw-r--r--vendor/ena/src/unify/tests.rs486
7 files changed, 2357 insertions, 0 deletions
diff --git a/vendor/ena/src/bitvec.rs b/vendor/ena/src/bitvec.rs
new file mode 100644
index 000000000..3677c8c5e
--- /dev/null
+++ b/vendor/ena/src/bitvec.rs
@@ -0,0 +1,301 @@
+// Copyright 2015 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+/// A very simple BitVector type.
+pub struct BitVector {
+ data: Vec<u64>,
+}
+
+impl BitVector {
+ pub fn new(num_bits: usize) -> BitVector {
+ let num_words = u64s(num_bits);
+ BitVector { data: vec![0; num_words] }
+ }
+
+ pub fn contains(&self, bit: usize) -> bool {
+ let (word, mask) = word_mask(bit);
+ (self.data[word] & mask) != 0
+ }
+
+ /// Returns true if the bit has changed.
+ pub fn insert(&mut self, bit: usize) -> bool {
+ let (word, mask) = word_mask(bit);
+ let data = &mut self.data[word];
+ let value = *data;
+ let new_value = value | mask;
+ *data = new_value;
+ new_value != value
+ }
+
+ pub fn insert_all(&mut self, all: &BitVector) -> bool {
+ assert!(self.data.len() == all.data.len());
+ let mut changed = false;
+ for (i, j) in self.data.iter_mut().zip(&all.data) {
+ let value = *i;
+ *i = value | *j;
+ if value != *i {
+ changed = true;
+ }
+ }
+ changed
+ }
+
+ pub fn grow(&mut self, num_bits: usize) {
+ let num_words = u64s(num_bits);
+ let extra_words = self.data.len() - num_words;
+ self.data.extend((0..extra_words).map(|_| 0));
+ }
+
+ /// Iterates over indexes of set bits in a sorted order
+ pub fn iter<'a>(&'a self) -> BitVectorIter<'a> {
+ BitVectorIter {
+ iter: self.data.iter(),
+ current: 0,
+ idx: 0,
+ }
+ }
+}
+
+pub struct BitVectorIter<'a> {
+ iter: ::std::slice::Iter<'a, u64>,
+ current: u64,
+ idx: usize,
+}
+
+impl<'a> Iterator for BitVectorIter<'a> {
+ type Item = usize;
+ fn next(&mut self) -> Option<usize> {
+ while self.current == 0 {
+ self.current = if let Some(&i) = self.iter.next() {
+ if i == 0 {
+ self.idx += 64;
+ continue;
+ } else {
+ self.idx = u64s(self.idx) * 64;
+ i
+ }
+ } else {
+ return None;
+ }
+ }
+ let offset = self.current.trailing_zeros() as usize;
+ self.current >>= offset;
+ self.current >>= 1; // shift otherwise overflows for 0b1000_0000_…_0000
+ self.idx += offset + 1;
+ return Some(self.idx - 1);
+ }
+}
+
+/// A "bit matrix" is basically a square matrix of booleans
+/// represented as one gigantic bitvector. In other words, it is as if
+/// you have N bitvectors, each of length N. Note that `elements` here is `N`/
+#[derive(Clone)]
+pub struct BitMatrix {
+ elements: usize,
+ vector: Vec<u64>,
+}
+
+impl BitMatrix {
+ // Create a new `elements x elements` matrix, initially empty.
+ pub fn new(elements: usize) -> BitMatrix {
+ // For every element, we need one bit for every other
+ // element. Round up to an even number of u64s.
+ let u64s_per_elem = u64s(elements);
+ BitMatrix {
+ elements: elements,
+ vector: vec![0; elements * u64s_per_elem],
+ }
+ }
+
+ /// The range of bits for a given element.
+ fn range(&self, element: usize) -> (usize, usize) {
+ let u64s_per_elem = u64s(self.elements);
+ let start = element * u64s_per_elem;
+ (start, start + u64s_per_elem)
+ }
+
+ pub fn add(&mut self, source: usize, target: usize) -> bool {
+ let (start, _) = self.range(source);
+ let (word, mask) = word_mask(target);
+ let mut vector = &mut self.vector[..];
+ let v1 = vector[start + word];
+ let v2 = v1 | mask;
+ vector[start + word] = v2;
+ v1 != v2
+ }
+
+ /// Do the bits from `source` contain `target`?
+ ///
+ /// Put another way, if the matrix represents (transitive)
+ /// reachability, can `source` reach `target`?
+ pub fn contains(&self, source: usize, target: usize) -> bool {
+ let (start, _) = self.range(source);
+ let (word, mask) = word_mask(target);
+ (self.vector[start + word] & mask) != 0
+ }
+
+ /// Returns those indices that are reachable from both `a` and
+ /// `b`. This is an O(n) operation where `n` is the number of
+ /// elements (somewhat independent from the actual size of the
+ /// intersection, in particular).
+ pub fn intersection(&self, a: usize, b: usize) -> Vec<usize> {
+ let (a_start, a_end) = self.range(a);
+ let (b_start, b_end) = self.range(b);
+ let mut result = Vec::with_capacity(self.elements);
+ for (base, (i, j)) in (a_start..a_end).zip(b_start..b_end).enumerate() {
+ let mut v = self.vector[i] & self.vector[j];
+ for bit in 0..64 {
+ if v == 0 {
+ break;
+ }
+ if v & 0x1 != 0 {
+ result.push(base * 64 + bit);
+ }
+ v >>= 1;
+ }
+ }
+ result
+ }
+
+ /// Add the bits from `read` to the bits from `write`,
+ /// return true if anything changed.
+ ///
+ /// This is used when computing transitive reachability because if
+ /// you have an edge `write -> read`, because in that case
+ /// `write` can reach everything that `read` can (and
+ /// potentially more).
+ pub fn merge(&mut self, read: usize, write: usize) -> bool {
+ let (read_start, read_end) = self.range(read);
+ let (write_start, write_end) = self.range(write);
+ let vector = &mut self.vector[..];
+ let mut changed = false;
+ for (read_index, write_index) in (read_start..read_end).zip(write_start..write_end) {
+ let v1 = vector[write_index];
+ let v2 = v1 | vector[read_index];
+ vector[write_index] = v2;
+ changed = changed | (v1 != v2);
+ }
+ changed
+ }
+}
+
+fn u64s(elements: usize) -> usize {
+ (elements + 63) / 64
+}
+
+fn word_mask(index: usize) -> (usize, u64) {
+ let word = index / 64;
+ let mask = 1 << (index % 64);
+ (word, mask)
+}
+
+#[test]
+fn bitvec_iter_works() {
+ let mut bitvec = BitVector::new(100);
+ bitvec.insert(1);
+ bitvec.insert(10);
+ bitvec.insert(19);
+ bitvec.insert(62);
+ bitvec.insert(63);
+ bitvec.insert(64);
+ bitvec.insert(65);
+ bitvec.insert(66);
+ bitvec.insert(99);
+ assert_eq!(bitvec.iter().collect::<Vec<_>>(),
+ [1, 10, 19, 62, 63, 64, 65, 66, 99]);
+}
+
+#[test]
+fn bitvec_iter_works_2() {
+ let mut bitvec = BitVector::new(300);
+ bitvec.insert(1);
+ bitvec.insert(10);
+ bitvec.insert(19);
+ bitvec.insert(62);
+ bitvec.insert(66);
+ bitvec.insert(99);
+ bitvec.insert(299);
+ assert_eq!(bitvec.iter().collect::<Vec<_>>(),
+ [1, 10, 19, 62, 66, 99, 299]);
+
+}
+
+#[test]
+fn bitvec_iter_works_3() {
+ let mut bitvec = BitVector::new(319);
+ bitvec.insert(0);
+ bitvec.insert(127);
+ bitvec.insert(191);
+ bitvec.insert(255);
+ bitvec.insert(319);
+ assert_eq!(bitvec.iter().collect::<Vec<_>>(), [0, 127, 191, 255, 319]);
+}
+
+#[test]
+fn union_two_vecs() {
+ let mut vec1 = BitVector::new(65);
+ let mut vec2 = BitVector::new(65);
+ assert!(vec1.insert(3));
+ assert!(!vec1.insert(3));
+ assert!(vec2.insert(5));
+ assert!(vec2.insert(64));
+ assert!(vec1.insert_all(&vec2));
+ assert!(!vec1.insert_all(&vec2));
+ assert!(vec1.contains(3));
+ assert!(!vec1.contains(4));
+ assert!(vec1.contains(5));
+ assert!(!vec1.contains(63));
+ assert!(vec1.contains(64));
+}
+
+#[test]
+fn grow() {
+ let mut vec1 = BitVector::new(65);
+ assert!(vec1.insert(3));
+ assert!(!vec1.insert(3));
+ assert!(vec1.insert(5));
+ assert!(vec1.insert(64));
+ vec1.grow(128);
+ assert!(vec1.contains(3));
+ assert!(vec1.contains(5));
+ assert!(vec1.contains(64));
+ assert!(!vec1.contains(126));
+}
+
+#[test]
+fn matrix_intersection() {
+ let mut vec1 = BitMatrix::new(200);
+
+ // (*) Elements reachable from both 2 and 65.
+
+ vec1.add(2, 3);
+ vec1.add(2, 6);
+ vec1.add(2, 10); // (*)
+ vec1.add(2, 64); // (*)
+ vec1.add(2, 65);
+ vec1.add(2, 130);
+ vec1.add(2, 160); // (*)
+
+ vec1.add(64, 133);
+
+ vec1.add(65, 2);
+ vec1.add(65, 8);
+ vec1.add(65, 10); // (*)
+ vec1.add(65, 64); // (*)
+ vec1.add(65, 68);
+ vec1.add(65, 133);
+ vec1.add(65, 160); // (*)
+
+ let intersection = vec1.intersection(2, 64);
+ assert!(intersection.is_empty());
+
+ let intersection = vec1.intersection(2, 65);
+ assert_eq!(intersection, &[10, 64, 160]);
+}
diff --git a/vendor/ena/src/lib.rs b/vendor/ena/src/lib.rs
new file mode 100644
index 000000000..aed352407
--- /dev/null
+++ b/vendor/ena/src/lib.rs
@@ -0,0 +1,24 @@
+// Copyright 2015 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+//! An implementation of union-find. See the `unify` module for more
+//! details.
+
+#![cfg_attr(feature = "bench", feature(test))]
+
+#[macro_use]
+extern crate log;
+
+#[cfg(feature = "persistent")]
+extern crate dogged;
+
+pub mod snapshot_vec;
+pub mod undo_log;
+pub mod unify;
diff --git a/vendor/ena/src/snapshot_vec.rs b/vendor/ena/src/snapshot_vec.rs
new file mode 100644
index 000000000..efde49aea
--- /dev/null
+++ b/vendor/ena/src/snapshot_vec.rs
@@ -0,0 +1,441 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+//! A utility class for implementing "snapshottable" things; a snapshottable data structure permits
+//! you to take a snapshot (via `start_snapshot`) and then, after making some changes, elect either
+//! to rollback to the start of the snapshot or commit those changes.
+//!
+//! This vector is intended to be used as part of an abstraction, not serve as a complete
+//! abstraction on its own. As such, while it will roll back most changes on its own, it also
+//! supports a `get_mut` operation that gives you an arbitrary mutable pointer into the vector. To
+//! ensure that any changes you make this with this pointer are rolled back, you must invoke
+//! `record` to record any changes you make and also supplying a delegate capable of reversing
+//! those changes.
+
+use self::UndoLog::*;
+
+use std::fmt;
+use std::marker::PhantomData;
+use std::mem;
+use std::ops;
+
+use undo_log::{Rollback, Snapshots, UndoLogs, VecLog};
+
+#[derive(Debug)]
+pub enum UndoLog<D: SnapshotVecDelegate> {
+ /// New variable with given index was created.
+ NewElem(usize),
+
+ /// Variable with given index was changed *from* the given value.
+ SetElem(usize, D::Value),
+
+ /// Extensible set of actions
+ Other(D::Undo),
+}
+
+impl<D: SnapshotVecDelegate> Rollback<UndoLog<D>> for SnapshotVecStorage<D> {
+ fn reverse(&mut self, undo: UndoLog<D>) {
+ self.values.reverse(undo)
+ }
+}
+impl<D: SnapshotVecDelegate> Rollback<UndoLog<D>> for Vec<D::Value> {
+ fn reverse(&mut self, undo: UndoLog<D>) {
+ match undo {
+ NewElem(i) => {
+ self.pop();
+ assert!(Vec::len(self) == i);
+ }
+
+ SetElem(i, v) => {
+ self[i] = v;
+ }
+
+ Other(u) => {
+ D::reverse(self, u);
+ }
+ }
+ }
+}
+
+pub trait VecLike<D>: AsRef<[D::Value]> + AsMut<[D::Value]> + Rollback<UndoLog<D>>
+where
+ D: SnapshotVecDelegate,
+{
+ fn push(&mut self, item: D::Value);
+ fn len(&self) -> usize;
+ fn reserve(&mut self, size: usize);
+}
+
+impl<D> VecLike<D> for Vec<D::Value>
+where
+ D: SnapshotVecDelegate,
+{
+ fn push(&mut self, item: D::Value) {
+ Vec::push(self, item)
+ }
+ fn len(&self) -> usize {
+ Vec::len(self)
+ }
+ fn reserve(&mut self, size: usize) {
+ Vec::reserve(self, size)
+ }
+}
+
+impl<D> VecLike<D> for &'_ mut Vec<D::Value>
+where
+ D: SnapshotVecDelegate,
+{
+ fn push(&mut self, item: D::Value) {
+ Vec::push(self, item)
+ }
+ fn len(&self) -> usize {
+ Vec::len(self)
+ }
+ fn reserve(&mut self, size: usize) {
+ Vec::reserve(self, size)
+ }
+}
+
+#[allow(type_alias_bounds)]
+pub type SnapshotVecStorage<D: SnapshotVecDelegate> =
+ SnapshotVec<D, Vec<<D as SnapshotVecDelegate>::Value>, ()>;
+
+pub struct SnapshotVec<
+ D: SnapshotVecDelegate,
+ V: VecLike<D> = Vec<<D as SnapshotVecDelegate>::Value>,
+ L = VecLog<UndoLog<D>>,
+> {
+ values: V,
+ undo_log: L,
+ _marker: PhantomData<D>,
+}
+
+impl<D, V, L> fmt::Debug for SnapshotVec<D, V, L>
+where
+ D: SnapshotVecDelegate,
+ V: VecLike<D> + fmt::Debug,
+ L: fmt::Debug,
+{
+ fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
+ fmt.debug_struct("SnapshotVec")
+ .field("values", &self.values)
+ .field("undo_log", &self.undo_log)
+ .finish()
+ }
+}
+
+// Snapshots are tokens that should be created/consumed linearly.
+pub struct Snapshot<S = ::undo_log::Snapshot> {
+ pub(crate) value_count: usize,
+ snapshot: S,
+}
+
+pub trait SnapshotVecDelegate {
+ type Value;
+ type Undo;
+
+ fn reverse(values: &mut Vec<Self::Value>, action: Self::Undo);
+}
+
+// HACK(eddyb) manual impl avoids `Default` bound on `D`.
+impl<D: SnapshotVecDelegate, V: VecLike<D> + Default, L: Default> Default for SnapshotVec<D, V, L> {
+ fn default() -> Self {
+ SnapshotVec {
+ values: V::default(),
+ undo_log: Default::default(),
+ _marker: PhantomData,
+ }
+ }
+}
+
+impl<D: SnapshotVecDelegate, V: VecLike<D> + Default, L: Default> SnapshotVec<D, V, L> {
+ /// Creates a new `SnapshotVec`. If `L` is set to `()` then most mutating functions will not
+ /// be accessible without calling `with_log` and supplying a compatibly `UndoLogs` instance.
+ pub fn new() -> Self {
+ Self::default()
+ }
+}
+
+impl<D: SnapshotVecDelegate> SnapshotVecStorage<D> {
+ /// Creates a `SnapshotVec` using the `undo_log`, allowing mutating methods to be called
+ pub fn with_log<'a, L>(
+ &'a mut self,
+ undo_log: L,
+ ) -> SnapshotVec<D, &'a mut Vec<<D as SnapshotVecDelegate>::Value>, L>
+ where
+ L: UndoLogs<UndoLog<D>>,
+ {
+ SnapshotVec {
+ values: &mut self.values,
+ undo_log,
+ _marker: PhantomData,
+ }
+ }
+}
+
+impl<D: SnapshotVecDelegate, L: Default> SnapshotVec<D, Vec<D::Value>, L> {
+ pub fn with_capacity(c: usize) -> Self {
+ SnapshotVec {
+ values: Vec::with_capacity(c),
+ undo_log: Default::default(),
+ _marker: PhantomData,
+ }
+ }
+}
+
+impl<V: VecLike<D>, D: SnapshotVecDelegate, U> SnapshotVec<D, V, U> {
+ pub fn len(&self) -> usize {
+ self.values.len()
+ }
+
+ pub fn get(&self, index: usize) -> &D::Value {
+ &self.values.as_ref()[index]
+ }
+
+ /// Returns a mutable pointer into the vec; whatever changes you make here cannot be undone
+ /// automatically, so you should be sure call `record()` with some sort of suitable undo
+ /// action.
+ pub fn get_mut(&mut self, index: usize) -> &mut D::Value {
+ &mut self.values.as_mut()[index]
+ }
+
+ /// Reserve space for new values, just like an ordinary vec.
+ pub fn reserve(&mut self, additional: usize) {
+ // This is not affected by snapshots or anything.
+ self.values.reserve(additional);
+ }
+}
+
+impl<V: VecLike<D>, D: SnapshotVecDelegate, L: UndoLogs<UndoLog<D>>> SnapshotVec<D, V, L> {
+ fn in_snapshot(&self) -> bool {
+ self.undo_log.in_snapshot()
+ }
+
+ pub fn record(&mut self, action: D::Undo) {
+ if self.in_snapshot() {
+ self.undo_log.push(Other(action));
+ }
+ }
+
+ pub fn push(&mut self, elem: D::Value) -> usize {
+ let len = self.values.len();
+ self.values.push(elem);
+
+ if self.in_snapshot() {
+ self.undo_log.push(NewElem(len));
+ }
+
+ len
+ }
+
+ /// Updates the element at the given index. The old value will saved (and perhaps restored) if
+ /// a snapshot is active.
+ pub fn set(&mut self, index: usize, new_elem: D::Value) {
+ let old_elem = mem::replace(&mut self.values.as_mut()[index], new_elem);
+ if self.undo_log.in_snapshot() {
+ self.undo_log.push(SetElem(index, old_elem));
+ }
+ }
+
+ /// Updates all elements. Potentially more efficient -- but
+ /// otherwise equivalent to -- invoking `set` for each element.
+ pub fn set_all(&mut self, mut new_elems: impl FnMut(usize) -> D::Value) {
+ if !self.undo_log.in_snapshot() {
+ for (index, slot) in self.values.as_mut().iter_mut().enumerate() {
+ *slot = new_elems(index);
+ }
+ } else {
+ for i in 0..self.values.len() {
+ self.set(i, new_elems(i));
+ }
+ }
+ }
+
+ pub fn update<OP>(&mut self, index: usize, op: OP)
+ where
+ OP: FnOnce(&mut D::Value),
+ D::Value: Clone,
+ {
+ if self.undo_log.in_snapshot() {
+ let old_elem = self.values.as_mut()[index].clone();
+ self.undo_log.push(SetElem(index, old_elem));
+ }
+ op(&mut self.values.as_mut()[index]);
+ }
+}
+
+impl<D, V, L> SnapshotVec<D, V, L>
+where
+ D: SnapshotVecDelegate,
+ V: VecLike<D> + Rollback<UndoLog<D>>,
+ L: Snapshots<UndoLog<D>>,
+{
+ pub fn start_snapshot(&mut self) -> Snapshot<L::Snapshot> {
+ Snapshot {
+ value_count: self.values.len(),
+ snapshot: self.undo_log.start_snapshot(),
+ }
+ }
+
+ pub fn actions_since_snapshot(&self, snapshot: &Snapshot<L::Snapshot>) -> &[UndoLog<D>] {
+ self.undo_log.actions_since_snapshot(&snapshot.snapshot)
+ }
+
+ pub fn rollback_to(&mut self, snapshot: Snapshot<L::Snapshot>) {
+ let values = &mut self.values;
+ self.undo_log.rollback_to(|| values, snapshot.snapshot);
+ }
+
+ /// Commits all changes since the last snapshot. Of course, they
+ /// can still be undone if there is a snapshot further out.
+ pub fn commit(&mut self, snapshot: Snapshot<L::Snapshot>) {
+ self.undo_log.commit(snapshot.snapshot);
+ }
+}
+
+impl<D: SnapshotVecDelegate, V: VecLike<D>, L> ops::Deref for SnapshotVec<D, V, L> {
+ type Target = [D::Value];
+ fn deref(&self) -> &[D::Value] {
+ self.values.as_ref()
+ }
+}
+
+impl<D: SnapshotVecDelegate, V: VecLike<D>, L> ops::DerefMut for SnapshotVec<D, V, L> {
+ fn deref_mut(&mut self) -> &mut [D::Value] {
+ self.values.as_mut()
+ }
+}
+
+impl<D: SnapshotVecDelegate, V: VecLike<D>, L> ops::Index<usize> for SnapshotVec<D, V, L> {
+ type Output = D::Value;
+ fn index(&self, index: usize) -> &D::Value {
+ self.get(index)
+ }
+}
+
+impl<D: SnapshotVecDelegate, V: VecLike<D>, L> ops::IndexMut<usize> for SnapshotVec<D, V, L> {
+ fn index_mut(&mut self, index: usize) -> &mut D::Value {
+ self.get_mut(index)
+ }
+}
+
+impl<D: SnapshotVecDelegate, V: VecLike<D> + Extend<D::Value>> Extend<D::Value>
+ for SnapshotVec<D, V>
+{
+ fn extend<T>(&mut self, iterable: T)
+ where
+ T: IntoIterator<Item = D::Value>,
+ {
+ let initial_len = self.values.len();
+ self.values.extend(iterable);
+ let final_len = self.values.len();
+
+ if self.in_snapshot() {
+ self.undo_log
+ .extend((initial_len..final_len).map(|len| NewElem(len)));
+ }
+ }
+}
+
+impl<D: SnapshotVecDelegate, V, L> Clone for SnapshotVec<D, V, L>
+where
+ V: VecLike<D> + Clone,
+ L: Clone,
+{
+ fn clone(&self) -> Self {
+ SnapshotVec {
+ values: self.values.clone(),
+ undo_log: self.undo_log.clone(),
+ _marker: PhantomData,
+ }
+ }
+}
+
+impl<D: SnapshotVecDelegate> Clone for UndoLog<D>
+where
+ D::Value: Clone,
+ D::Undo: Clone,
+{
+ fn clone(&self) -> Self {
+ match *self {
+ NewElem(i) => NewElem(i),
+ SetElem(i, ref v) => SetElem(i, v.clone()),
+ Other(ref u) => Other(u.clone()),
+ }
+ }
+}
+
+impl SnapshotVecDelegate for i32 {
+ type Value = i32;
+ type Undo = ();
+
+ fn reverse(_: &mut Vec<i32>, _: ()) {}
+}
+
+#[test]
+fn basic() {
+ let mut vec: SnapshotVec<i32> = SnapshotVec::default();
+ assert!(!vec.in_snapshot());
+ assert_eq!(vec.len(), 0);
+ vec.push(22);
+ vec.push(33);
+ assert_eq!(vec.len(), 2);
+ assert_eq!(*vec.get(0), 22);
+ assert_eq!(*vec.get(1), 33);
+ vec.set(1, 34);
+ assert_eq!(vec.len(), 2);
+ assert_eq!(*vec.get(0), 22);
+ assert_eq!(*vec.get(1), 34);
+
+ let snapshot = vec.start_snapshot();
+ assert!(vec.in_snapshot());
+
+ vec.push(44);
+ vec.push(55);
+ vec.set(1, 35);
+ assert_eq!(vec.len(), 4);
+ assert_eq!(*vec.get(0), 22);
+ assert_eq!(*vec.get(1), 35);
+ assert_eq!(*vec.get(2), 44);
+ assert_eq!(*vec.get(3), 55);
+
+ vec.rollback_to(snapshot);
+ assert!(!vec.in_snapshot());
+
+ assert_eq!(vec.len(), 2);
+ assert_eq!(*vec.get(0), 22);
+ assert_eq!(*vec.get(1), 34);
+}
+
+#[test]
+#[should_panic]
+fn out_of_order() {
+ let mut vec: SnapshotVec<i32> = SnapshotVec::default();
+ vec.push(22);
+ let snapshot1 = vec.start_snapshot();
+ vec.push(33);
+ let snapshot2 = vec.start_snapshot();
+ vec.push(44);
+ vec.rollback_to(snapshot1); // bogus, but accepted
+ vec.rollback_to(snapshot2); // asserts
+}
+
+#[test]
+fn nested_commit_then_rollback() {
+ let mut vec: SnapshotVec<i32> = SnapshotVec::default();
+ vec.push(22);
+ let snapshot1 = vec.start_snapshot();
+ let snapshot2 = vec.start_snapshot();
+ vec.set(0, 23);
+ vec.commit(snapshot2);
+ assert_eq!(*vec.get(0), 23);
+ vec.rollback_to(snapshot1);
+ assert_eq!(*vec.get(0), 22);
+}
diff --git a/vendor/ena/src/undo_log.rs b/vendor/ena/src/undo_log.rs
new file mode 100644
index 000000000..93c38030a
--- /dev/null
+++ b/vendor/ena/src/undo_log.rs
@@ -0,0 +1,248 @@
+//! Module which contains the snapshot/rollback functionality of the `ena` data structures.
+//!
+//! For most usecases this is just an internal implementation detail. However if many `ena`
+//! data structures are used snapshotted simultaneously it is possible to use
+//! `UnificationTableStorage`/`SnapshotVecStorage` instead and use a custom `UndoLogs<T>`
+//! type capable of recording the actions of all used data structures.
+//!
+//! Since the `*Storage` variants do not have an undo log `with_log` must be called with the
+//! unified log before any mutating actions.
+
+/// A trait which allows undo actions (`T`) to be pushed which can be used to rollback actio at a
+/// later time if needed.
+///
+/// The undo actions themselves are opaque to `UndoLogs`, only specified `Rollback` implementations
+/// need to know what an action is and how to reverse it.
+pub trait UndoLogs<T> {
+ /// True if a snapshot has started, false otherwise
+ fn in_snapshot(&self) -> bool {
+ self.num_open_snapshots() > 0
+ }
+
+ /// How many open snapshots this undo log currently has
+ fn num_open_snapshots(&self) -> usize;
+
+ /// Pushes a new "undo item" onto the undo log. This method is invoked when some action is taken
+ /// (e.g., a variable is unified). It records the info needed to reverse that action should an
+ /// enclosing snapshot be rolleod back.
+ fn push(&mut self, undo: T);
+
+ /// Removes all items from the undo log.
+ fn clear(&mut self);
+
+ /// Extends the undo log with many undos.
+ fn extend<I>(&mut self, undos: I)
+ where
+ Self: Sized,
+ I: IntoIterator<Item = T>,
+ {
+ undos.into_iter().for_each(|undo| self.push(undo));
+ }
+}
+
+impl<'a, T, U> UndoLogs<T> for &'a mut U
+where
+ U: UndoLogs<T>,
+{
+ fn in_snapshot(&self) -> bool {
+ U::in_snapshot(self)
+ }
+ fn num_open_snapshots(&self) -> usize {
+ U::num_open_snapshots(self)
+ }
+ fn push(&mut self, undo: T) {
+ U::push(self, undo)
+ }
+ fn clear(&mut self) {
+ U::clear(self);
+ }
+ fn extend<I>(&mut self, undos: I)
+ where
+ Self: Sized,
+ I: IntoIterator<Item = T>,
+ {
+ U::extend(self, undos)
+ }
+}
+
+/// A trait which extends `UndoLogs` to allow snapshots to be done at specific points. Each snapshot can then be used to
+/// rollback any changes to an underlying data structures if they were not desirable.
+///
+/// Each snapshot must be consumed linearly with either `rollback_to` or `commit`.
+pub trait Snapshots<T>: UndoLogs<T> {
+ type Snapshot;
+
+ /// Returns true if `self` has made any changes since snapshot started.
+ fn has_changes(&self, snapshot: &Self::Snapshot) -> bool {
+ !self.actions_since_snapshot(snapshot).is_empty()
+ }
+
+ /// Returns the slice of actions that were taken since the snapshot began.
+ fn actions_since_snapshot(&self, snapshot: &Self::Snapshot) -> &[T];
+
+ /// Starts a new snapshot. That snapshot must eventually either be committed via a call to
+ /// commit or rollback via rollback_to. Snapshots can be nested (i.e., you can start a snapshot
+ /// whilst another snapshot is in progress) but you must then commit or rollback the inner
+ /// snapshot before attempting to commit or rollback the outer snapshot.
+ fn start_snapshot(&mut self) -> Self::Snapshot;
+
+ /// Rollback (undo) the changes made to `storage` since the snapshot.
+ fn rollback_to<R>(&mut self, storage: impl FnOnce() -> R, snapshot: Self::Snapshot)
+ where
+ R: Rollback<T>;
+
+ /// Commit: keep the changes that have been made since the snapshot began
+ fn commit(&mut self, snapshot: Self::Snapshot);
+}
+
+impl<T, U> Snapshots<T> for &'_ mut U
+where
+ U: Snapshots<T>,
+{
+ type Snapshot = U::Snapshot;
+ fn has_changes(&self, snapshot: &Self::Snapshot) -> bool {
+ U::has_changes(self, snapshot)
+ }
+ fn actions_since_snapshot(&self, snapshot: &Self::Snapshot) -> &[T] {
+ U::actions_since_snapshot(self, snapshot)
+ }
+
+ fn start_snapshot(&mut self) -> Self::Snapshot {
+ U::start_snapshot(self)
+ }
+ fn rollback_to<R>(&mut self, storage: impl FnOnce() -> R, snapshot: Self::Snapshot)
+ where
+ R: Rollback<T>,
+ {
+ U::rollback_to(self, storage, snapshot)
+ }
+
+ fn commit(&mut self, snapshot: Self::Snapshot) {
+ U::commit(self, snapshot)
+ }
+}
+
+pub struct NoUndo;
+impl<T> UndoLogs<T> for NoUndo {
+ fn num_open_snapshots(&self) -> usize {
+ 0
+ }
+ fn push(&mut self, _undo: T) {}
+ fn clear(&mut self) {}
+}
+
+/// A basic undo log.
+#[derive(Clone, Debug)]
+pub struct VecLog<T> {
+ log: Vec<T>,
+ num_open_snapshots: usize,
+}
+
+impl<T> Default for VecLog<T> {
+ fn default() -> Self {
+ VecLog {
+ log: Vec::new(),
+ num_open_snapshots: 0,
+ }
+ }
+}
+
+impl<T> UndoLogs<T> for VecLog<T> {
+ fn num_open_snapshots(&self) -> usize {
+ self.num_open_snapshots
+ }
+ fn push(&mut self, undo: T) {
+ self.log.push(undo);
+ }
+ fn clear(&mut self) {
+ self.log.clear();
+ self.num_open_snapshots = 0;
+ }
+}
+
+impl<T> Snapshots<T> for VecLog<T> {
+ type Snapshot = Snapshot;
+
+ fn has_changes(&self, snapshot: &Self::Snapshot) -> bool {
+ self.log.len() > snapshot.undo_len
+ }
+ fn actions_since_snapshot(&self, snapshot: &Snapshot) -> &[T] {
+ &self.log[snapshot.undo_len..]
+ }
+
+ fn start_snapshot(&mut self) -> Snapshot {
+ self.num_open_snapshots += 1;
+ Snapshot {
+ undo_len: self.log.len(),
+ }
+ }
+
+ fn rollback_to<R>(&mut self, values: impl FnOnce() -> R, snapshot: Snapshot)
+ where
+ R: Rollback<T>,
+ {
+ debug!("rollback_to({})", snapshot.undo_len);
+
+ self.assert_open_snapshot(&snapshot);
+
+ if self.log.len() > snapshot.undo_len {
+ let mut values = values();
+ while self.log.len() > snapshot.undo_len {
+ values.reverse(self.log.pop().unwrap());
+ }
+ }
+
+ self.num_open_snapshots -= 1;
+ }
+
+ fn commit(&mut self, snapshot: Snapshot) {
+ debug!("commit({})", snapshot.undo_len);
+
+ self.assert_open_snapshot(&snapshot);
+
+ if self.num_open_snapshots == 1 {
+ // The root snapshot. It's safe to clear the undo log because
+ // there's no snapshot further out that we might need to roll back
+ // to.
+ assert!(snapshot.undo_len == 0);
+ self.log.clear();
+ }
+
+ self.num_open_snapshots -= 1;
+ }
+}
+
+impl<T> VecLog<T> {
+ fn assert_open_snapshot(&self, snapshot: &Snapshot) {
+ // Failures here may indicate a failure to follow a stack discipline.
+ assert!(self.log.len() >= snapshot.undo_len);
+ assert!(self.num_open_snapshots > 0);
+ }
+}
+
+impl<T> std::ops::Index<usize> for VecLog<T> {
+ type Output = T;
+ fn index(&self, key: usize) -> &T {
+ &self.log[key]
+ }
+}
+
+/// A trait implemented for storage types (like `SnapshotVecStorage`) which can be rolled back using actions of type `U`.
+pub trait Rollback<U> {
+ fn reverse(&mut self, undo: U);
+}
+
+impl<T, U> Rollback<U> for &'_ mut T
+where
+ T: Rollback<U>,
+{
+ fn reverse(&mut self, undo: U) {
+ T::reverse(self, undo)
+ }
+}
+
+/// Snapshots are tokens that should be created/consumed linearly.
+pub struct Snapshot {
+ // Length of the undo log at the time the snapshot was taken.
+ undo_len: usize,
+}
diff --git a/vendor/ena/src/unify/backing_vec.rs b/vendor/ena/src/unify/backing_vec.rs
new file mode 100644
index 000000000..7c1eb2ced
--- /dev/null
+++ b/vendor/ena/src/unify/backing_vec.rs
@@ -0,0 +1,263 @@
+#[cfg(feature = "persistent")]
+use dogged::DVec;
+use snapshot_vec as sv;
+use std::marker::PhantomData;
+use std::ops::{self, Range};
+
+use undo_log::{Rollback, Snapshots, UndoLogs, VecLog};
+
+use super::{UnifyKey, UnifyValue, VarValue};
+
+#[allow(dead_code)] // rustc BUG
+#[allow(type_alias_bounds)]
+type Key<S: UnificationStoreBase> = <S as UnificationStoreBase>::Key;
+
+/// Largely internal trait implemented by the unification table
+/// backing store types. The most common such type is `InPlace`,
+/// which indicates a standard, mutable unification table.
+pub trait UnificationStoreBase: ops::Index<usize, Output = VarValue<Key<Self>>> {
+ type Key: UnifyKey<Value = Self::Value>;
+ type Value: UnifyValue;
+
+ fn len(&self) -> usize;
+
+ fn tag() -> &'static str {
+ Self::Key::tag()
+ }
+}
+
+pub trait UnificationStoreMut: UnificationStoreBase {
+ fn reset_unifications(&mut self, value: impl FnMut(u32) -> VarValue<Self::Key>);
+
+ fn push(&mut self, value: VarValue<Self::Key>);
+
+ fn reserve(&mut self, num_new_values: usize);
+
+ fn update<F>(&mut self, index: usize, op: F)
+ where
+ F: FnOnce(&mut VarValue<Self::Key>);
+}
+
+pub trait UnificationStore: UnificationStoreMut {
+ type Snapshot;
+
+ fn start_snapshot(&mut self) -> Self::Snapshot;
+
+ fn rollback_to(&mut self, snapshot: Self::Snapshot);
+
+ fn commit(&mut self, snapshot: Self::Snapshot);
+
+ fn values_since_snapshot(&self, snapshot: &Self::Snapshot) -> Range<usize>;
+}
+
+/// Backing store for an in-place unification table.
+/// Not typically used directly.
+#[derive(Clone, Debug)]
+pub struct InPlace<
+ K: UnifyKey,
+ V: sv::VecLike<Delegate<K>> = Vec<VarValue<K>>,
+ L = VecLog<sv::UndoLog<Delegate<K>>>,
+> {
+ pub(crate) values: sv::SnapshotVec<Delegate<K>, V, L>,
+}
+
+// HACK(eddyb) manual impl avoids `Default` bound on `K`.
+impl<K: UnifyKey, V: sv::VecLike<Delegate<K>> + Default, L: Default> Default for InPlace<K, V, L> {
+ fn default() -> Self {
+ InPlace {
+ values: sv::SnapshotVec::new(),
+ }
+ }
+}
+
+impl<K, V, L> UnificationStoreBase for InPlace<K, V, L>
+where
+ K: UnifyKey,
+ V: sv::VecLike<Delegate<K>>,
+{
+ type Key = K;
+ type Value = K::Value;
+
+ fn len(&self) -> usize {
+ self.values.len()
+ }
+}
+
+impl<K, V, L> UnificationStoreMut for InPlace<K, V, L>
+where
+ K: UnifyKey,
+ V: sv::VecLike<Delegate<K>>,
+ L: UndoLogs<sv::UndoLog<Delegate<K>>>,
+{
+ #[inline]
+ fn reset_unifications(&mut self, mut value: impl FnMut(u32) -> VarValue<Self::Key>) {
+ self.values.set_all(|i| value(i as u32));
+ }
+
+ #[inline]
+ fn push(&mut self, value: VarValue<Self::Key>) {
+ self.values.push(value);
+ }
+
+ #[inline]
+ fn reserve(&mut self, num_new_values: usize) {
+ self.values.reserve(num_new_values);
+ }
+
+ #[inline]
+ fn update<F>(&mut self, index: usize, op: F)
+ where
+ F: FnOnce(&mut VarValue<Self::Key>),
+ {
+ self.values.update(index, op)
+ }
+}
+
+impl<K, V, L> UnificationStore for InPlace<K, V, L>
+where
+ K: UnifyKey,
+ V: sv::VecLike<Delegate<K>>,
+ L: Snapshots<sv::UndoLog<Delegate<K>>>,
+{
+ type Snapshot = sv::Snapshot<L::Snapshot>;
+
+ #[inline]
+ fn start_snapshot(&mut self) -> Self::Snapshot {
+ self.values.start_snapshot()
+ }
+
+ #[inline]
+ fn rollback_to(&mut self, snapshot: Self::Snapshot) {
+ self.values.rollback_to(snapshot);
+ }
+
+ #[inline]
+ fn commit(&mut self, snapshot: Self::Snapshot) {
+ self.values.commit(snapshot);
+ }
+
+ #[inline]
+ fn values_since_snapshot(&self, snapshot: &Self::Snapshot) -> Range<usize> {
+ snapshot.value_count..self.len()
+ }
+}
+
+impl<K, V, L> ops::Index<usize> for InPlace<K, V, L>
+where
+ V: sv::VecLike<Delegate<K>>,
+ K: UnifyKey,
+{
+ type Output = VarValue<K>;
+ fn index(&self, index: usize) -> &VarValue<K> {
+ &self.values[index]
+ }
+}
+
+#[doc(hidden)]
+#[derive(Copy, Clone, Debug)]
+pub struct Delegate<K>(PhantomData<K>);
+
+impl<K: UnifyKey> sv::SnapshotVecDelegate for Delegate<K> {
+ type Value = VarValue<K>;
+ type Undo = ();
+
+ fn reverse(_: &mut Vec<VarValue<K>>, _: ()) {}
+}
+
+impl<K: UnifyKey> Rollback<sv::UndoLog<Delegate<K>>> for super::UnificationTableStorage<K> {
+ fn reverse(&mut self, undo: sv::UndoLog<Delegate<K>>) {
+ self.values.values.reverse(undo);
+ }
+}
+
+#[cfg(feature = "persistent")]
+#[derive(Clone, Debug)]
+pub struct Persistent<K: UnifyKey> {
+ values: DVec<VarValue<K>>,
+}
+
+// HACK(eddyb) manual impl avoids `Default` bound on `K`.
+#[cfg(feature = "persistent")]
+impl<K: UnifyKey> Default for Persistent<K> {
+ fn default() -> Self {
+ Persistent {
+ values: DVec::new(),
+ }
+ }
+}
+
+#[cfg(feature = "persistent")]
+impl<K: UnifyKey> UnificationStoreBase for Persistent<K> {
+ type Key = K;
+ type Value = K::Value;
+
+ fn len(&self) -> usize {
+ self.values.len()
+ }
+}
+
+#[cfg(feature = "persistent")]
+impl<K: UnifyKey> UnificationStoreMut for Persistent<K> {
+ #[inline]
+ fn reset_unifications(&mut self, mut value: impl FnMut(u32) -> VarValue<Self::Key>) {
+ // Without extending dogged, there isn't obviously a more
+ // efficient way to do this. But it's pretty dumb. Maybe
+ // dogged needs a `map`.
+ for i in 0..self.values.len() {
+ self.values[i] = value(i as u32);
+ }
+ }
+
+ #[inline]
+ fn push(&mut self, value: VarValue<Self::Key>) {
+ self.values.push(value);
+ }
+
+ #[inline]
+ fn reserve(&mut self, _num_new_values: usize) {
+ // not obviously relevant to DVec.
+ }
+
+ #[inline]
+ fn update<F>(&mut self, index: usize, op: F)
+ where
+ F: FnOnce(&mut VarValue<Self::Key>),
+ {
+ let p = &mut self.values[index];
+ op(p);
+ }
+}
+
+#[cfg(feature = "persistent")]
+impl<K: UnifyKey> UnificationStore for Persistent<K> {
+ type Snapshot = Self;
+
+ #[inline]
+ fn start_snapshot(&mut self) -> Self::Snapshot {
+ self.clone()
+ }
+
+ #[inline]
+ fn rollback_to(&mut self, snapshot: Self::Snapshot) {
+ *self = snapshot;
+ }
+
+ #[inline]
+ fn commit(&mut self, _snapshot: Self::Snapshot) {}
+
+ #[inline]
+ fn values_since_snapshot(&self, snapshot: &Self::Snapshot) -> Range<usize> {
+ snapshot.len()..self.len()
+ }
+}
+
+#[cfg(feature = "persistent")]
+impl<K> ops::Index<usize> for Persistent<K>
+where
+ K: UnifyKey,
+{
+ type Output = VarValue<K>;
+ fn index(&self, index: usize) -> &VarValue<K> {
+ &self.values[index]
+ }
+}
diff --git a/vendor/ena/src/unify/mod.rs b/vendor/ena/src/unify/mod.rs
new file mode 100644
index 000000000..a26d699d8
--- /dev/null
+++ b/vendor/ena/src/unify/mod.rs
@@ -0,0 +1,594 @@
+// Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+//! Union-find implementation. The main type is `UnificationTable`.
+//!
+//! You can define your own type for the *keys* in the table, but you
+//! must implement `UnifyKey` for that type. The assumption is that
+//! keys will be newtyped integers, hence we require that they
+//! implement `Copy`.
+//!
+//! Keys can have values associated with them. The assumption is that
+//! these values are cheaply cloneable (ideally, `Copy`), and some of
+//! the interfaces are oriented around that assumption. If you just
+//! want the classical "union-find" algorithm where you group things
+//! into sets, use the `Value` type of `()`.
+//!
+//! When you have keys with non-trivial values, you must also define
+//! how those values can be merged. As part of doing this, you can
+//! define the "error" type to return on error; if errors are not
+//! possible, use `NoError` (an uninstantiable struct). Using this
+//! type also unlocks various more ergonomic methods (e.g., `union()`
+//! in place of `unify_var_var()`).
+//!
+//! The best way to see how it is used is to read the `tests.rs` file;
+//! search for e.g. `UnitKey`.
+
+use std::fmt::Debug;
+use std::marker;
+use std::ops::Range;
+
+use snapshot_vec::{self as sv, UndoLog};
+use undo_log::{UndoLogs, VecLog};
+
+mod backing_vec;
+pub use self::backing_vec::{
+ Delegate, InPlace, UnificationStore, UnificationStoreBase, UnificationStoreMut,
+};
+
+#[cfg(feature = "persistent")]
+pub use self::backing_vec::Persistent;
+
+#[cfg(test)]
+mod tests;
+
+/// This trait is implemented by any type that can serve as a type
+/// variable. We call such variables *unification keys*. For example,
+/// this trait is implemented by `IntVid`, which represents integral
+/// variables.
+///
+/// Each key type has an associated value type `V`. For example, for
+/// `IntVid`, this is `Option<IntVarValue>`, representing some
+/// (possibly not yet known) sort of integer.
+///
+/// Clients are expected to provide implementations of this trait; you
+/// can see some examples in the `test` module.
+pub trait UnifyKey: Copy + Clone + Debug + PartialEq {
+ type Value: UnifyValue;
+
+ fn index(&self) -> u32;
+
+ fn from_index(u: u32) -> Self;
+
+ fn tag() -> &'static str;
+
+ /// If true, then `self` should be preferred as root to `other`.
+ /// Note that we assume a consistent partial ordering, so
+ /// returning true implies that `other.prefer_as_root_to(self)`
+ /// would return false. If there is no ordering between two keys
+ /// (i.e., `a.prefer_as_root_to(b)` and `b.prefer_as_root_to(a)`
+ /// both return false) then the rank will be used to determine the
+ /// root in an optimal way.
+ ///
+ /// NB. The only reason to implement this method is if you want to
+ /// control what value is returned from `find()`. In general, it
+ /// is better to let the unification table determine the root,
+ /// since overriding the rank can cause execution time to increase
+ /// dramatically.
+ #[allow(unused_variables)]
+ fn order_roots(
+ a: Self,
+ a_value: &Self::Value,
+ b: Self,
+ b_value: &Self::Value,
+ ) -> Option<(Self, Self)> {
+ None
+ }
+}
+
+/// Trait implemented for **values** associated with a unification
+/// key. This trait defines how to merge the values from two keys that
+/// are unioned together. This merging can be fallible. If you attempt
+/// to union two keys whose values cannot be merged, then the error is
+/// propagated up and the two keys are not unioned.
+///
+/// This crate provides implementations of `UnifyValue` for `()`
+/// (which is infallible) and `Option<T>` (where `T: UnifyValue`). The
+/// option implementation merges two sum-values using the `UnifyValue`
+/// implementation of `T`.
+///
+/// See also `EqUnifyValue`, which is a convenience trait for cases
+/// where the "merge" operation succeeds only if the two values are
+/// equal.
+pub trait UnifyValue: Clone + Debug {
+ /// Defines the type to return when merging of two values fails.
+ /// If merging is infallible, use the special struct `NoError`
+ /// found in this crate, which unlocks various more convenient
+ /// methods on the unification table.
+ type Error;
+
+ /// Given two values, produce a new value that combines them.
+ /// If that is not possible, produce an error.
+ fn unify_values(value1: &Self, value2: &Self) -> Result<Self, Self::Error>;
+}
+
+/// A convenient helper for unification values which must be equal or
+/// else an error occurs. For example, if you are unifying types in a
+/// simple functional language, this may be appropriate, since (e.g.)
+/// you can't unify a type variable bound to `int` with one bound to
+/// `float` (but you can unify two type variables both bound to
+/// `int`).
+///
+/// Any type which implements `EqUnifyValue` automatially implements
+/// `UnifyValue`; if the two values are equal, merging is permitted.
+/// Otherwise, the error `(v1, v2)` is returned, where `v1` and `v2`
+/// are the two unequal values.
+pub trait EqUnifyValue: Eq + Clone + Debug {}
+
+impl<T: EqUnifyValue> UnifyValue for T {
+ type Error = (T, T);
+
+ fn unify_values(value1: &Self, value2: &Self) -> Result<Self, Self::Error> {
+ if value1 == value2 {
+ Ok(value1.clone())
+ } else {
+ Err((value1.clone(), value2.clone()))
+ }
+ }
+}
+
+/// A struct which can never be instantiated. Used
+/// for the error type for infallible cases.
+#[derive(Debug)]
+pub struct NoError {
+ _dummy: (),
+}
+
+/// Value of a unification key. We implement Tarjan's union-find
+/// algorithm: when two keys are unified, one of them is converted
+/// into a "redirect" pointing at the other. These redirects form a
+/// DAG: the roots of the DAG (nodes that are not redirected) are each
+/// associated with a value of type `V` and a rank. The rank is used
+/// to keep the DAG relatively balanced, which helps keep the running
+/// time of the algorithm under control. For more information, see
+/// <http://en.wikipedia.org/wiki/Disjoint-set_data_structure>.
+#[derive(PartialEq, Clone, Debug)]
+pub struct VarValue<K: UnifyKey> {
+ parent: K, // if equal to self, this is a root
+ value: K::Value, // value assigned (only relevant to root)
+ rank: u32, // max depth (only relevant to root)
+}
+
+/// Table of unification keys and their values. You must define a key type K
+/// that implements the `UnifyKey` trait. Unification tables can be used in two-modes:
+///
+/// - in-place (`UnificationTable<InPlace<K>>` or `InPlaceUnificationTable<K>`):
+/// - This is the standard mutable mode, where the array is modified
+/// in place.
+/// - To do backtracking, you can employ the `snapshot` and `rollback_to`
+/// methods.
+/// - persistent (`UnificationTable<Persistent<K>>` or `PersistentUnificationTable<K>`):
+/// - In this mode, we use a persistent vector to store the data, so that
+/// cloning the table is an O(1) operation.
+/// - This implies that ordinary operations are quite a bit slower though.
+/// - Requires the `persistent` feature be selected in your Cargo.toml file.
+#[derive(Clone, Debug, Default)]
+pub struct UnificationTable<S: UnificationStoreBase> {
+ /// Indicates the current value of each key.
+ values: S,
+}
+
+pub type UnificationStorage<K> = Vec<VarValue<K>>;
+pub type UnificationTableStorage<K> = UnificationTable<InPlace<K, UnificationStorage<K>, ()>>;
+
+/// A unification table that uses an "in-place" vector.
+#[allow(type_alias_bounds)]
+pub type InPlaceUnificationTable<
+ K: UnifyKey,
+ V: sv::VecLike<Delegate<K>> = Vec<VarValue<K>>,
+ L = VecLog<UndoLog<Delegate<K>>>,
+> = UnificationTable<InPlace<K, V, L>>;
+
+/// A unification table that uses a "persistent" vector.
+#[cfg(feature = "persistent")]
+#[allow(type_alias_bounds)]
+pub type PersistentUnificationTable<K: UnifyKey> = UnificationTable<Persistent<K>>;
+
+/// At any time, users may snapshot a unification table. The changes
+/// made during the snapshot may either be *committed* or *rolled back*.
+pub struct Snapshot<S: UnificationStore> {
+ // Link snapshot to the unification store `S` of the table.
+ marker: marker::PhantomData<S>,
+ snapshot: S::Snapshot,
+}
+
+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, // this is a root
+ value: value,
+ rank: rank,
+ }
+ }
+
+ fn redirect(&mut self, to: K) {
+ self.parent = to;
+ }
+
+ fn root(&mut self, rank: u32, value: K::Value) {
+ self.rank = rank;
+ self.value = value;
+ }
+
+ 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> UnificationTableStorage<K>
+where
+ K: UnifyKey,
+{
+ /// Creates a `UnificationTable` using an external `undo_log`, allowing mutating methods to be
+ /// called if `L` does not implement `UndoLogs`
+ pub fn with_log<'a, L>(
+ &'a mut self,
+ undo_log: L,
+ ) -> UnificationTable<InPlace<K, &'a mut UnificationStorage<K>, L>>
+ where
+ L: UndoLogs<sv::UndoLog<Delegate<K>>>,
+ {
+ UnificationTable {
+ values: InPlace {
+ values: self.values.values.with_log(undo_log),
+ },
+ }
+ }
+}
+
+// We can't use V:LatticeValue, much as I would like to,
+// because frequently the pattern is that V=Option<U> for some
+// other type parameter U, and we have no way to say
+// Option<U>:LatticeValue.
+
+impl<S: UnificationStoreBase + Default> UnificationTable<S> {
+ pub fn new() -> Self {
+ Self::default()
+ }
+}
+
+impl<S: UnificationStore> UnificationTable<S> {
+ /// Starts a new snapshot. Each snapshot must be either
+ /// rolled back or committed in a "LIFO" (stack) order.
+ pub fn snapshot(&mut self) -> Snapshot<S> {
+ Snapshot {
+ marker: marker::PhantomData::<S>,
+ snapshot: self.values.start_snapshot(),
+ }
+ }
+
+ /// Reverses all changes since the last snapshot. Also
+ /// removes any keys that have been created since then.
+ pub fn rollback_to(&mut self, snapshot: Snapshot<S>) {
+ debug!("{}: rollback_to()", S::tag());
+ self.values.rollback_to(snapshot.snapshot);
+ }
+
+ /// Commits all changes since the last snapshot. Of course, they
+ /// can still be undone if there is a snapshot further out.
+ pub fn commit(&mut self, snapshot: Snapshot<S>) {
+ debug!("{}: commit()", S::tag());
+ self.values.commit(snapshot.snapshot);
+ }
+
+ /// Returns the keys of all variables created since the `snapshot`.
+ pub fn vars_since_snapshot(&self, snapshot: &Snapshot<S>) -> Range<S::Key> {
+ let range = self.values.values_since_snapshot(&snapshot.snapshot);
+ S::Key::from_index(range.start as u32)..S::Key::from_index(range.end as u32)
+ }
+}
+
+impl<S: UnificationStoreBase> UnificationTable<S> {
+ /// Returns the number of keys created so far.
+ pub fn len(&self) -> usize {
+ self.values.len()
+ }
+}
+
+impl<S: UnificationStoreMut> UnificationTable<S> {
+ /// Starts a new snapshot. Each snapshot must be either
+ /// Creates a fresh key with the given value.
+ pub fn new_key(&mut self, value: S::Value) -> S::Key {
+ let len = self.values.len();
+ let key: S::Key = UnifyKey::from_index(len as u32);
+ self.values.push(VarValue::new_var(key, value));
+ debug!("{}: created new key: {:?}", S::tag(), key);
+ key
+ }
+
+ /// Reserve memory for `num_new_keys` to be created. Does not
+ /// actually create the new keys; you must then invoke `new_key`.
+ pub fn reserve(&mut self, num_new_keys: usize) {
+ self.values.reserve(num_new_keys);
+ }
+
+ /// Clears all unifications that have been performed, resetting to
+ /// the initial state. The values of each variable are given by
+ /// the closure.
+ pub fn reset_unifications(&mut self, mut value: impl FnMut(S::Key) -> S::Value) {
+ self.values.reset_unifications(|i| {
+ let key = UnifyKey::from_index(i as u32);
+ let value = value(key);
+ VarValue::new_var(key, value)
+ });
+ }
+
+ /// Obtains the current value for a particular key.
+ /// Not for end-users; they can use `probe_value`.
+ fn value(&self, key: S::Key) -> &VarValue<S::Key> {
+ &self.values[key.index() as usize]
+ }
+
+ /// Find the root node for `vid`. This uses the standard
+ /// union-find algorithm with path compression:
+ /// <http://en.wikipedia.org/wiki/Disjoint-set_data_structure>.
+ ///
+ /// NB. This is a building-block operation and you would probably
+ /// prefer to call `probe` below.
+ ///
+ /// This is an always-inlined version of this function for the hot
+ /// callsites. `uninlined_get_root_key` is the never-inlined version.
+ #[inline(always)]
+ fn inlined_get_root_key(&mut self, vid: S::Key) -> S::Key {
+ let redirect = {
+ match self.value(vid).parent(vid) {
+ None => return vid,
+ Some(redirect) => redirect,
+ }
+ };
+
+ let root_key: S::Key = self.uninlined_get_root_key(redirect);
+ if root_key != redirect {
+ // Path compression
+ self.update_value(vid, |value| value.parent = root_key);
+ }
+
+ root_key
+ }
+
+ // This is a never-inlined version of this function for cold callsites.
+ // 'inlined_get_root_key` is the always-inlined version.
+ #[inline(never)]
+ fn uninlined_get_root_key(&mut self, vid: S::Key) -> S::Key {
+ self.inlined_get_root_key(vid)
+ }
+
+ fn update_value<OP>(&mut self, key: S::Key, op: OP)
+ where
+ OP: FnOnce(&mut VarValue<S::Key>),
+ {
+ self.values.update(key.index() as usize, op);
+ debug!("Updated variable {:?} to {:?}", key, self.value(key));
+ }
+
+ /// Either redirects `node_a` to `node_b` or vice versa, depending
+ /// on the relative rank. The value associated with the new root
+ /// will be `new_value`.
+ ///
+ /// NB: This is the "union" operation of "union-find". It is
+ /// really more of a building block. If the values associated with
+ /// your key are non-trivial, you would probably prefer to call
+ /// `unify_var_var` below.
+ fn unify_roots(&mut self, key_a: S::Key, key_b: S::Key, new_value: S::Value) {
+ debug!("unify(key_a={:?}, key_b={:?})", key_a, key_b);
+
+ let rank_a = self.value(key_a).rank;
+ let rank_b = self.value(key_b).rank;
+ if let Some((new_root, redirected)) = S::Key::order_roots(
+ key_a,
+ &self.value(key_a).value,
+ key_b,
+ &self.value(key_b).value,
+ ) {
+ // compute the new rank for the new root that they chose;
+ // this may not be the optimal choice.
+ let new_rank = if new_root == key_a {
+ debug_assert!(redirected == key_b);
+ if rank_a > rank_b {
+ rank_a
+ } else {
+ rank_b + 1
+ }
+ } else {
+ debug_assert!(new_root == key_b);
+ debug_assert!(redirected == key_a);
+ if rank_b > rank_a {
+ rank_b
+ } else {
+ rank_a + 1
+ }
+ };
+ self.redirect_root(new_rank, redirected, new_root, new_value);
+ } else if rank_a > rank_b {
+ // a has greater rank, so a should become b's parent,
+ // i.e., b should redirect to a.
+ self.redirect_root(rank_a, key_b, key_a, new_value);
+ } else if rank_a < rank_b {
+ // b has greater rank, so a should redirect to b.
+ self.redirect_root(rank_b, key_a, key_b, new_value);
+ } else {
+ // If equal, redirect one to the other and increment the
+ // other's rank.
+ self.redirect_root(rank_a + 1, key_a, key_b, new_value);
+ }
+ }
+
+ /// Internal method to redirect `old_root_key` (which is currently
+ /// a root) to a child of `new_root_key` (which will remain a
+ /// root). The rank and value of `new_root_key` will be updated to
+ /// `new_rank` and `new_value` respectively.
+ fn redirect_root(
+ &mut self,
+ new_rank: u32,
+ old_root_key: S::Key,
+ new_root_key: S::Key,
+ new_value: S::Value,
+ ) {
+ self.update_value(old_root_key, |old_root_value| {
+ old_root_value.redirect(new_root_key);
+ });
+ self.update_value(new_root_key, |new_root_value| {
+ new_root_value.root(new_rank, new_value);
+ });
+ }
+}
+
+/// ////////////////////////////////////////////////////////////////////////
+/// Public API
+
+impl<S, K, V> UnificationTable<S>
+where
+ S: UnificationStoreMut<Key = K, Value = V>,
+ K: UnifyKey<Value = V>,
+ V: UnifyValue,
+{
+ /// Unions two keys without the possibility of failure; only
+ /// applicable when unify values use `NoError` as their error
+ /// type.
+ pub fn union<K1, K2>(&mut self, a_id: K1, b_id: K2)
+ where
+ K1: Into<K>,
+ K2: Into<K>,
+ V: UnifyValue<Error = NoError>,
+ {
+ self.unify_var_var(a_id, b_id).unwrap();
+ }
+
+ /// Unions a key and a value without the possibility of failure;
+ /// only applicable when unify values use `NoError` as their error
+ /// type.
+ pub fn union_value<K1>(&mut self, id: K1, value: V)
+ where
+ K1: Into<K>,
+ V: UnifyValue<Error = NoError>,
+ {
+ self.unify_var_value(id, value).unwrap();
+ }
+
+ /// Given two keys, indicates whether they have been unioned together.
+ pub fn unioned<K1, K2>(&mut self, a_id: K1, b_id: K2) -> bool
+ where
+ K1: Into<K>,
+ K2: Into<K>,
+ {
+ self.find(a_id) == self.find(b_id)
+ }
+
+ /// Given a key, returns the (current) root key.
+ pub fn find<K1>(&mut self, id: K1) -> K
+ where
+ K1: Into<K>,
+ {
+ let id = id.into();
+ self.uninlined_get_root_key(id)
+ }
+
+ /// Unions together two variables, merging their values. If
+ /// merging the values fails, the error is propagated and this
+ /// method has no effect.
+ pub fn unify_var_var<K1, K2>(&mut self, a_id: K1, b_id: K2) -> Result<(), V::Error>
+ where
+ K1: Into<K>,
+ K2: Into<K>,
+ {
+ let a_id = a_id.into();
+ let b_id = b_id.into();
+
+ let root_a = self.uninlined_get_root_key(a_id);
+ let root_b = self.uninlined_get_root_key(b_id);
+
+ if root_a == root_b {
+ return Ok(());
+ }
+
+ let combined = V::unify_values(&self.value(root_a).value, &self.value(root_b).value)?;
+
+ Ok(self.unify_roots(root_a, root_b, combined))
+ }
+
+ /// Sets the value of the key `a_id` to `b`, attempting to merge
+ /// with the previous value.
+ pub fn unify_var_value<K1>(&mut self, a_id: K1, b: V) -> Result<(), V::Error>
+ where
+ K1: Into<K>,
+ {
+ let a_id = a_id.into();
+ let root_a = self.uninlined_get_root_key(a_id);
+ let value = V::unify_values(&self.value(root_a).value, &b)?;
+ self.update_value(root_a, |node| node.value = value);
+ Ok(())
+ }
+
+ /// Returns the current value for the given key. If the key has
+ /// been union'd, this will give the value from the current root.
+ pub fn probe_value<K1>(&mut self, id: K1) -> V
+ where
+ K1: Into<K>,
+ {
+ self.inlined_probe_value(id)
+ }
+
+ // An always-inlined version of `probe_value`, for hot callsites.
+ #[inline(always)]
+ pub fn inlined_probe_value<K1>(&mut self, id: K1) -> V
+ where
+ K1: Into<K>,
+ {
+ let id = id.into();
+ let id = self.inlined_get_root_key(id);
+ self.value(id).value.clone()
+ }
+}
+
+///////////////////////////////////////////////////////////////////////////
+
+impl UnifyValue for () {
+ type Error = NoError;
+
+ fn unify_values(_: &(), _: &()) -> Result<(), NoError> {
+ Ok(())
+ }
+}
+
+impl<V: UnifyValue> UnifyValue for Option<V> {
+ type Error = V::Error;
+
+ fn unify_values(a: &Option<V>, b: &Option<V>) -> Result<Self, V::Error> {
+ match (a, b) {
+ (&None, &None) => Ok(None),
+ (&Some(ref v), &None) | (&None, &Some(ref v)) => Ok(Some(v.clone())),
+ (&Some(ref a), &Some(ref b)) => match V::unify_values(a, b) {
+ Ok(v) => Ok(Some(v)),
+ Err(err) => Err(err),
+ },
+ }
+ }
+}
diff --git a/vendor/ena/src/unify/tests.rs b/vendor/ena/src/unify/tests.rs
new file mode 100644
index 000000000..5665aba0c
--- /dev/null
+++ b/vendor/ena/src/unify/tests.rs
@@ -0,0 +1,486 @@
+// Copyright 2015 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// Naming the benchmarks using uppercase letters helps them sort
+// better.
+#![allow(non_snake_case)]
+
+#[cfg(feature = "bench")]
+extern crate test;
+#[cfg(feature = "bench")]
+use self::test::Bencher;
+use std::cmp;
+#[cfg(feature = "persistent")]
+use unify::Persistent;
+use unify::{EqUnifyValue, InPlace, InPlaceUnificationTable, NoError, UnifyKey, UnifyValue};
+use unify::{UnificationStore, UnificationTable};
+
+#[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)]
+struct UnitKey(u32);
+
+impl UnifyKey for UnitKey {
+ type Value = ();
+ fn index(&self) -> u32 {
+ self.0
+ }
+ fn from_index(u: u32) -> UnitKey {
+ UnitKey(u)
+ }
+ fn tag() -> &'static str {
+ "UnitKey"
+ }
+}
+
+macro_rules! all_modes {
+ ($name:ident for $t:ty => $body:tt) => {
+ fn test_body<
+ $name: Clone + Default + UnificationStore<Key = $t, Value = <$t as UnifyKey>::Value>,
+ >() {
+ $body
+ }
+
+ test_body::<InPlace<$t>>();
+
+ #[cfg(feature = "persistent")]
+ test_body::<Persistent<$t>>();
+ };
+}
+
+#[test]
+fn basic() {
+ all_modes! {
+ S for UnitKey => {
+ let mut ut: UnificationTable<S> = UnificationTable::new();
+ let k1 = ut.new_key(());
+ let k2 = ut.new_key(());
+ assert_eq!(ut.unioned(k1, k2), false);
+ ut.union(k1, k2);
+ assert_eq!(ut.unioned(k1, k2), true);
+ }
+ }
+}
+
+#[test]
+fn big_array() {
+ all_modes! {
+ S for UnitKey => {
+ let mut ut: UnificationTable<S> = UnificationTable::new();
+ let mut keys = Vec::new();
+ const MAX: usize = 1 << 15;
+
+ for _ in 0..MAX {
+ keys.push(ut.new_key(()));
+ }
+
+ for i in 1..MAX {
+ let l = keys[i - 1];
+ let r = keys[i];
+ ut.union(l, r);
+ }
+
+ for i in 0..MAX {
+ assert!(ut.unioned(keys[0], keys[i]));
+ }
+ }
+ }
+}
+
+#[cfg(feature = "bench")]
+fn big_array_bench_generic<S: Default + UnificationStore<Key = UnitKey, Value = ()>>(
+ b: &mut Bencher,
+) {
+ let mut ut: UnificationTable<S> = UnificationTable::new();
+ let mut keys = Vec::new();
+ const MAX: usize = 1 << 15;
+
+ for _ in 0..MAX {
+ keys.push(ut.new_key(()));
+ }
+
+ b.iter(|| {
+ for i in 1..MAX {
+ let l = keys[i - 1];
+ let r = keys[i];
+ ut.union(l, r);
+ }
+
+ for i in 0..MAX {
+ assert!(ut.unioned(keys[0], keys[i]));
+ }
+ })
+}
+
+#[cfg(feature = "bench")]
+#[bench]
+fn big_array_bench_InPlace(b: &mut Bencher) {
+ big_array_bench_generic::<InPlace<UnitKey>>(b);
+}
+
+#[cfg(all(feature = "bench", feature = "persistent"))]
+#[bench]
+fn big_array_bench_Persistent(b: &mut Bencher) {
+ big_array_bench_generic::<Persistent<UnitKey>>(b);
+}
+
+#[cfg(feature = "bench")]
+fn big_array_bench_in_snapshot_generic<S: Default + UnificationStore<Key = UnitKey, Value = ()>>(
+ b: &mut Bencher,
+) {
+ let mut ut: UnificationTable<S> = UnificationTable::new();
+ let mut keys = Vec::new();
+ const MAX: usize = 1 << 15;
+
+ for _ in 0..MAX {
+ keys.push(ut.new_key(()));
+ }
+
+ b.iter(|| {
+ let snapshot = ut.snapshot();
+
+ for i in 1..MAX {
+ let l = keys[i - 1];
+ let r = keys[i];
+ ut.union(l, r);
+ }
+
+ for i in 0..MAX {
+ assert!(ut.unioned(keys[0], keys[i]));
+ }
+
+ ut.rollback_to(snapshot);
+ })
+}
+
+#[cfg(feature = "bench")]
+#[bench]
+fn big_array_bench_in_snapshot_InPlace(b: &mut Bencher) {
+ big_array_bench_in_snapshot_generic::<InPlace<UnitKey>>(b);
+}
+
+#[cfg(all(feature = "bench", feature = "persistent"))]
+#[bench]
+fn big_array_bench_in_snapshot_Persistent(b: &mut Bencher) {
+ big_array_bench_in_snapshot_generic::<Persistent<UnitKey>>(b);
+}
+
+#[cfg(feature = "bench")]
+fn big_array_bench_clone_generic<
+ S: Default + Clone + UnificationStore<Key = UnitKey, Value = ()>,
+>(
+ b: &mut Bencher,
+) {
+ let mut ut: UnificationTable<S> = UnificationTable::new();
+ let mut keys = Vec::new();
+ const MAX: usize = 1 << 15;
+
+ for _ in 0..MAX {
+ keys.push(ut.new_key(()));
+ }
+
+ b.iter(|| {
+ let saved_table = ut.clone();
+
+ for i in 1..MAX {
+ let l = keys[i - 1];
+ let r = keys[i];
+ ut.union(l, r);
+ }
+
+ for i in 0..MAX {
+ assert!(ut.unioned(keys[0], keys[i]));
+ }
+
+ ut = saved_table;
+ })
+}
+
+#[cfg(feature = "bench")]
+#[bench]
+fn big_array_bench_clone_InPlace(b: &mut Bencher) {
+ big_array_bench_clone_generic::<InPlace<UnitKey>>(b);
+}
+
+#[cfg(all(feature = "bench", feature = "persistent"))]
+#[bench]
+fn big_array_bench_clone_Persistent(b: &mut Bencher) {
+ big_array_bench_clone_generic::<Persistent<UnitKey>>(b);
+}
+
+#[test]
+fn even_odd() {
+ all_modes! {
+ S for UnitKey => {
+ let mut ut: UnificationTable<S> = UnificationTable::new();
+ let mut keys = Vec::new();
+ const MAX: usize = 1 << 10;
+
+ for i in 0..MAX {
+ let key = ut.new_key(());
+ keys.push(key);
+
+ if i >= 2 {
+ ut.union(key, keys[i - 2]);
+ }
+ }
+
+ for i in 1..MAX {
+ assert!(!ut.unioned(keys[i - 1], keys[i]));
+ }
+
+ for i in 2..MAX {
+ assert!(ut.unioned(keys[i - 2], keys[i]));
+ }
+ }
+ }
+}
+
+#[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)]
+struct IntKey(u32);
+
+impl UnifyKey for IntKey {
+ type Value = Option<i32>;
+ fn index(&self) -> u32 {
+ self.0
+ }
+ fn from_index(u: u32) -> IntKey {
+ IntKey(u)
+ }
+ fn tag() -> &'static str {
+ "IntKey"
+ }
+}
+
+impl EqUnifyValue for i32 {}
+
+#[test]
+fn unify_same_int_twice() {
+ all_modes! {
+ S for IntKey => {
+ let mut ut: UnificationTable<S> = UnificationTable::new();
+ let k1 = ut.new_key(None);
+ let k2 = ut.new_key(None);
+ assert!(ut.unify_var_value(k1, Some(22)).is_ok());
+ assert!(ut.unify_var_value(k2, Some(22)).is_ok());
+ assert!(ut.unify_var_var(k1, k2).is_ok());
+ assert_eq!(ut.probe_value(k1), Some(22));
+ }
+ }
+}
+
+#[test]
+fn unify_vars_then_int_indirect() {
+ all_modes! {
+ S for IntKey => {
+ let mut ut: UnificationTable<S> = UnificationTable::new();
+ let k1 = ut.new_key(None);
+ let k2 = ut.new_key(None);
+ assert!(ut.unify_var_var(k1, k2).is_ok());
+ assert!(ut.unify_var_value(k1, Some(22)).is_ok());
+ assert_eq!(ut.probe_value(k2), Some(22));
+ }
+ }
+}
+
+#[test]
+fn unify_vars_different_ints_1() {
+ all_modes! {
+ S for IntKey => {
+ let mut ut: UnificationTable<S> = UnificationTable::new();
+ let k1 = ut.new_key(None);
+ let k2 = ut.new_key(None);
+ assert!(ut.unify_var_var(k1, k2).is_ok());
+ assert!(ut.unify_var_value(k1, Some(22)).is_ok());
+ assert!(ut.unify_var_value(k2, Some(23)).is_err());
+ }
+ }
+}
+
+#[test]
+fn unify_vars_different_ints_2() {
+ all_modes! {
+ S for IntKey => {
+ let mut ut: UnificationTable<S> = UnificationTable::new();
+ let k1 = ut.new_key(None);
+ let k2 = ut.new_key(None);
+ assert!(ut.unify_var_var(k2, k1).is_ok());
+ assert!(ut.unify_var_value(k1, Some(22)).is_ok());
+ assert!(ut.unify_var_value(k2, Some(23)).is_err());
+ }
+ }
+}
+
+#[test]
+fn unify_distinct_ints_then_vars() {
+ all_modes! {
+ S for IntKey => {
+ let mut ut: UnificationTable<S> = UnificationTable::new();
+ let k1 = ut.new_key(None);
+ let k2 = ut.new_key(None);
+ assert!(ut.unify_var_value(k1, Some(22)).is_ok());
+ assert!(ut.unify_var_value(k2, Some(23)).is_ok());
+ assert!(ut.unify_var_var(k2, k1).is_err());
+ }
+ }
+}
+
+#[test]
+fn unify_root_value_1() {
+ all_modes! {
+ S for IntKey => {
+ let mut ut: UnificationTable<S> = UnificationTable::new();
+ let k1 = ut.new_key(None);
+ let k2 = ut.new_key(None);
+ let k3 = ut.new_key(None);
+ assert!(ut.unify_var_value(k1, Some(22)).is_ok());
+ assert!(ut.unify_var_var(k1, k2).is_ok());
+ assert!(ut.unify_var_value(k3, Some(23)).is_ok());
+ assert!(ut.unify_var_var(k1, k3).is_err());
+ }
+ }
+}
+
+#[test]
+fn unify_root_value_2() {
+ all_modes! {
+ S for IntKey => {
+ let mut ut: UnificationTable<S> = UnificationTable::new();
+ let k1 = ut.new_key(None);
+ let k2 = ut.new_key(None);
+ let k3 = ut.new_key(None);
+ assert!(ut.unify_var_value(k1, Some(22)).is_ok());
+ assert!(ut.unify_var_var(k2, k1).is_ok());
+ assert!(ut.unify_var_value(k3, Some(23)).is_ok());
+ assert!(ut.unify_var_var(k1, k3).is_err());
+ }
+ }
+}
+
+#[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)]
+struct OrderedKey(u32);
+
+#[derive(Copy, Clone, Debug, Hash, PartialEq, Eq, PartialOrd, Ord)]
+struct OrderedRank(u32);
+
+impl UnifyKey for OrderedKey {
+ type Value = OrderedRank;
+ fn index(&self) -> u32 {
+ self.0
+ }
+ fn from_index(u: u32) -> OrderedKey {
+ OrderedKey(u)
+ }
+ fn tag() -> &'static str {
+ "OrderedKey"
+ }
+ fn order_roots(
+ a: OrderedKey,
+ a_rank: &OrderedRank,
+ b: OrderedKey,
+ b_rank: &OrderedRank,
+ ) -> Option<(OrderedKey, OrderedKey)> {
+ println!("{:?} vs {:?}", a_rank, b_rank);
+ if a_rank > b_rank {
+ Some((a, b))
+ } else if b_rank > a_rank {
+ Some((b, a))
+ } else {
+ None
+ }
+ }
+}
+
+impl UnifyValue for OrderedRank {
+ type Error = NoError;
+
+ fn unify_values(value1: &Self, value2: &Self) -> Result<Self, NoError> {
+ Ok(OrderedRank(cmp::max(value1.0, value2.0)))
+ }
+}
+
+#[test]
+fn ordered_key() {
+ all_modes! {
+ S for OrderedKey => {
+ let mut ut: UnificationTable<S> = UnificationTable::new();
+
+ let k0_1 = ut.new_key(OrderedRank(0));
+ let k0_2 = ut.new_key(OrderedRank(0));
+ let k0_3 = ut.new_key(OrderedRank(0));
+ let k0_4 = ut.new_key(OrderedRank(0));
+
+ ut.union(k0_1, k0_2); // rank of one of those will now be 1
+ ut.union(k0_3, k0_4); // rank of new root also 1
+ ut.union(k0_1, k0_3); // rank of new root now 2
+
+ let k0_5 = ut.new_key(OrderedRank(0));
+ let k0_6 = ut.new_key(OrderedRank(0));
+ ut.union(k0_5, k0_6); // rank of new root now 1
+
+ ut.union(k0_1, k0_5); // new root rank 2, should not be k0_5 or k0_6
+ assert!(vec![k0_1, k0_2, k0_3, k0_4].contains(&ut.find(k0_1)));
+ }
+ }
+}
+
+#[test]
+fn ordered_key_k1() {
+ all_modes! {
+ S for UnitKey => {
+ let mut ut: InPlaceUnificationTable<OrderedKey> = UnificationTable::new();
+
+ let k0_1 = ut.new_key(OrderedRank(0));
+ let k0_2 = ut.new_key(OrderedRank(0));
+ let k0_3 = ut.new_key(OrderedRank(0));
+ let k0_4 = ut.new_key(OrderedRank(0));
+
+ ut.union(k0_1, k0_2); // rank of one of those will now be 1
+ ut.union(k0_3, k0_4); // rank of new root also 1
+ ut.union(k0_1, k0_3); // rank of new root now 2
+
+ let k1_5 = ut.new_key(OrderedRank(1));
+ let k1_6 = ut.new_key(OrderedRank(1));
+ ut.union(k1_5, k1_6); // rank of new root now 1
+
+ ut.union(k0_1, k1_5); // even though k1 has lower rank, it wins
+ assert!(
+ vec![k1_5, k1_6].contains(&ut.find(k0_1)),
+ "unexpected choice for root: {:?}",
+ ut.find(k0_1)
+ );
+ }
+ }
+}
+
+/// Test that we *can* clone.
+#[test]
+fn clone_table() {
+ all_modes! {
+ S for IntKey => {
+ let mut ut: UnificationTable<S> = UnificationTable::new();
+ let k1 = ut.new_key(None);
+ let k2 = ut.new_key(None);
+ let k3 = ut.new_key(None);
+ assert!(ut.unify_var_value(k1, Some(22)).is_ok());
+ assert!(ut.unify_var_value(k2, Some(22)).is_ok());
+ assert!(ut.unify_var_var(k1, k2).is_ok());
+ assert_eq!(ut.probe_value(k3), None);
+
+ let mut ut1 = ut.clone();
+ assert_eq!(ut1.probe_value(k1), Some(22));
+ assert_eq!(ut1.probe_value(k3), None);
+
+ assert!(ut.unify_var_value(k3, Some(44)).is_ok());
+
+ assert_eq!(ut1.probe_value(k1), Some(22));
+ assert_eq!(ut1.probe_value(k3), None);
+ assert_eq!(ut.probe_value(k3), Some(44));
+ }
+ }
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-09-13 18:23:13 +0000