From 698f8c2f01ea549d77d7dc3338a12e04c11057b9 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 17 Apr 2024 14:02:58 +0200 Subject: Adding upstream version 1.64.0+dfsg1. Signed-off-by: Daniel Baumann --- vendor/ena/src/unify/backing_vec.rs | 263 ++++++++++++++++ vendor/ena/src/unify/mod.rs | 594 ++++++++++++++++++++++++++++++++++++ vendor/ena/src/unify/tests.rs | 486 +++++++++++++++++++++++++++++ 3 files changed, 1343 insertions(+) create mode 100644 vendor/ena/src/unify/backing_vec.rs create mode 100644 vendor/ena/src/unify/mod.rs create mode 100644 vendor/ena/src/unify/tests.rs (limited to 'vendor/ena/src/unify') 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 = ::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>> { + type Key: UnifyKey; + 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); + + fn push(&mut self, value: VarValue); + + fn reserve(&mut self, num_new_values: usize); + + fn update(&mut self, index: usize, op: F) + where + F: FnOnce(&mut VarValue); +} + +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; +} + +/// Backing store for an in-place unification table. +/// Not typically used directly. +#[derive(Clone, Debug)] +pub struct InPlace< + K: UnifyKey, + V: sv::VecLike> = Vec>, + L = VecLog>>, +> { + pub(crate) values: sv::SnapshotVec, V, L>, +} + +// HACK(eddyb) manual impl avoids `Default` bound on `K`. +impl> + Default, L: Default> Default for InPlace { + fn default() -> Self { + InPlace { + values: sv::SnapshotVec::new(), + } + } +} + +impl UnificationStoreBase for InPlace +where + K: UnifyKey, + V: sv::VecLike>, +{ + type Key = K; + type Value = K::Value; + + fn len(&self) -> usize { + self.values.len() + } +} + +impl UnificationStoreMut for InPlace +where + K: UnifyKey, + V: sv::VecLike>, + L: UndoLogs>>, +{ + #[inline] + fn reset_unifications(&mut self, mut value: impl FnMut(u32) -> VarValue) { + self.values.set_all(|i| value(i as u32)); + } + + #[inline] + fn push(&mut self, value: VarValue) { + self.values.push(value); + } + + #[inline] + fn reserve(&mut self, num_new_values: usize) { + self.values.reserve(num_new_values); + } + + #[inline] + fn update(&mut self, index: usize, op: F) + where + F: FnOnce(&mut VarValue), + { + self.values.update(index, op) + } +} + +impl UnificationStore for InPlace +where + K: UnifyKey, + V: sv::VecLike>, + L: Snapshots>>, +{ + type Snapshot = sv::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 { + snapshot.value_count..self.len() + } +} + +impl ops::Index for InPlace +where + V: sv::VecLike>, + K: UnifyKey, +{ + type Output = VarValue; + fn index(&self, index: usize) -> &VarValue { + &self.values[index] + } +} + +#[doc(hidden)] +#[derive(Copy, Clone, Debug)] +pub struct Delegate(PhantomData); + +impl sv::SnapshotVecDelegate for Delegate { + type Value = VarValue; + type Undo = (); + + fn reverse(_: &mut Vec>, _: ()) {} +} + +impl Rollback>> for super::UnificationTableStorage { + fn reverse(&mut self, undo: sv::UndoLog>) { + self.values.values.reverse(undo); + } +} + +#[cfg(feature = "persistent")] +#[derive(Clone, Debug)] +pub struct Persistent { + values: DVec>, +} + +// HACK(eddyb) manual impl avoids `Default` bound on `K`. +#[cfg(feature = "persistent")] +impl Default for Persistent { + fn default() -> Self { + Persistent { + values: DVec::new(), + } + } +} + +#[cfg(feature = "persistent")] +impl UnificationStoreBase for Persistent { + type Key = K; + type Value = K::Value; + + fn len(&self) -> usize { + self.values.len() + } +} + +#[cfg(feature = "persistent")] +impl UnificationStoreMut for Persistent { + #[inline] + fn reset_unifications(&mut self, mut value: impl FnMut(u32) -> VarValue) { + // 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.values.push(value); + } + + #[inline] + fn reserve(&mut self, _num_new_values: usize) { + // not obviously relevant to DVec. + } + + #[inline] + fn update(&mut self, index: usize, op: F) + where + F: FnOnce(&mut VarValue), + { + let p = &mut self.values[index]; + op(p); + } +} + +#[cfg(feature = "persistent")] +impl UnificationStore for Persistent { + 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 { + snapshot.len()..self.len() + } +} + +#[cfg(feature = "persistent")] +impl ops::Index for Persistent +where + K: UnifyKey, +{ + type Output = VarValue; + fn index(&self, index: usize) -> &VarValue { + &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 or the MIT license +// , 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`, 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` (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; +} + +/// 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 UnifyValue for T { + type Error = (T, T); + + fn unify_values(value1: &Self, value2: &Self) -> Result { + 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 +/// . +#[derive(PartialEq, Clone, Debug)] +pub struct VarValue { + 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>` or `InPlaceUnificationTable`): +/// - 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>` or `PersistentUnificationTable`): +/// - 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 { + /// Indicates the current value of each key. + values: S, +} + +pub type UnificationStorage = Vec>; +pub type UnificationTableStorage = UnificationTable, ()>>; + +/// A unification table that uses an "in-place" vector. +#[allow(type_alias_bounds)] +pub type InPlaceUnificationTable< + K: UnifyKey, + V: sv::VecLike> = Vec>, + L = VecLog>>, +> = UnificationTable>; + +/// A unification table that uses a "persistent" vector. +#[cfg(feature = "persistent")] +#[allow(type_alias_bounds)] +pub type PersistentUnificationTable = UnificationTable>; + +/// 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 { + // Link snapshot to the unification store `S` of the table. + marker: marker::PhantomData, + snapshot: S::Snapshot, +} + +impl VarValue { + fn new_var(key: K, value: K::Value) -> VarValue { + VarValue::new(key, value, 0) + } + + fn new(parent: K, value: K::Value, rank: u32) -> VarValue { + 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 { + self.if_not_self(self.parent, self_key) + } + + fn if_not_self(&self, key: K, self_key: K) -> Option { + if key == self_key { + None + } else { + Some(key) + } + } +} +impl UnificationTableStorage +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, L>> + where + L: UndoLogs>>, + { + 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 for some +// other type parameter U, and we have no way to say +// Option:LatticeValue. + +impl UnificationTable { + pub fn new() -> Self { + Self::default() + } +} + +impl UnificationTable { + /// Starts a new snapshot. Each snapshot must be either + /// rolled back or committed in a "LIFO" (stack) order. + pub fn snapshot(&mut self) -> Snapshot { + Snapshot { + marker: marker::PhantomData::, + 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) { + 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) { + 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) -> Range { + 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 UnificationTable { + /// Returns the number of keys created so far. + pub fn len(&self) -> usize { + self.values.len() + } +} + +impl UnificationTable { + /// 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 { + &self.values[key.index() as usize] + } + + /// Find the root node for `vid`. This uses the standard + /// union-find algorithm with path compression: + /// . + /// + /// 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(&mut self, key: S::Key, op: OP) + where + OP: FnOnce(&mut VarValue), + { + 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 UnificationTable +where + S: UnificationStoreMut, + K: UnifyKey, + V: UnifyValue, +{ + /// Unions two keys without the possibility of failure; only + /// applicable when unify values use `NoError` as their error + /// type. + pub fn union(&mut self, a_id: K1, b_id: K2) + where + K1: Into, + K2: Into, + V: UnifyValue, + { + 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(&mut self, id: K1, value: V) + where + K1: Into, + V: UnifyValue, + { + self.unify_var_value(id, value).unwrap(); + } + + /// Given two keys, indicates whether they have been unioned together. + pub fn unioned(&mut self, a_id: K1, b_id: K2) -> bool + where + K1: Into, + K2: Into, + { + self.find(a_id) == self.find(b_id) + } + + /// Given a key, returns the (current) root key. + pub fn find(&mut self, id: K1) -> K + where + K1: Into, + { + 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(&mut self, a_id: K1, b_id: K2) -> Result<(), V::Error> + where + K1: Into, + K2: Into, + { + 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(&mut self, a_id: K1, b: V) -> Result<(), V::Error> + where + K1: Into, + { + 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(&mut self, id: K1) -> V + where + K1: Into, + { + self.inlined_probe_value(id) + } + + // An always-inlined version of `probe_value`, for hot callsites. + #[inline(always)] + pub fn inlined_probe_value(&mut self, id: K1) -> V + where + K1: Into, + { + 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 UnifyValue for Option { + type Error = V::Error; + + fn unify_values(a: &Option, b: &Option) -> Result { + 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 or the MIT license +// , 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::Value>, + >() { + $body + } + + test_body::>(); + + #[cfg(feature = "persistent")] + test_body::>(); + }; +} + +#[test] +fn basic() { + all_modes! { + S for UnitKey => { + let mut ut: UnificationTable = 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 = 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>( + b: &mut Bencher, +) { + let mut ut: UnificationTable = 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::>(b); +} + +#[cfg(all(feature = "bench", feature = "persistent"))] +#[bench] +fn big_array_bench_Persistent(b: &mut Bencher) { + big_array_bench_generic::>(b); +} + +#[cfg(feature = "bench")] +fn big_array_bench_in_snapshot_generic>( + b: &mut Bencher, +) { + let mut ut: UnificationTable = 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::>(b); +} + +#[cfg(all(feature = "bench", feature = "persistent"))] +#[bench] +fn big_array_bench_in_snapshot_Persistent(b: &mut Bencher) { + big_array_bench_in_snapshot_generic::>(b); +} + +#[cfg(feature = "bench")] +fn big_array_bench_clone_generic< + S: Default + Clone + UnificationStore, +>( + b: &mut Bencher, +) { + let mut ut: UnificationTable = 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::>(b); +} + +#[cfg(all(feature = "bench", feature = "persistent"))] +#[bench] +fn big_array_bench_clone_Persistent(b: &mut Bencher) { + big_array_bench_clone_generic::>(b); +} + +#[test] +fn even_odd() { + all_modes! { + S for UnitKey => { + let mut ut: UnificationTable = 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; + 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 = 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 = 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 = 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 = 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 = 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 = 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 = 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 { + Ok(OrderedRank(cmp::max(value1.0, value2.0))) + } +} + +#[test] +fn ordered_key() { + all_modes! { + S for OrderedKey => { + let mut ut: UnificationTable = 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 = 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 = 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)); + } + } +} -- cgit v1.2.3