simple union-find implementation HEAD canon

Change-Id: I32b78b3eee68205032591578fca70c366a6a6964

1 files changed, 269 insertions, 46 deletions

diff --git a/crates/core/src/id.rs b/crates/core/src/id.rs
index a216dd8..b2c289c 100644
--- a/crates/core/src/id.rs
+++ b/crates/core/src/id.rs
@@ -3,12 +3,147 @@
 
 use core::hash::Hash;
 
-/// Numeric identifier representation.
+#[cfg(feature = "core-fmt")]
+use core::fmt;
+
+#[cfg(feature = "core-error")]
+use core::error;
+
+use crate::utilities::{CheckedArithmeticExt, IntegerOverflowError};
+
+/// Constructs a new [`Identifier`] type.
+///
+/// ```rust
+/// # #![feature(const_trait_impl)]
+/// # #![feature(const_default)]
+/// # #![feature(const_result_trait_fn)]
+/// # #![feature(const_convert)]
+/// # use azimuth_core::make_id;
+///
+/// make_id!(pub Thing, "Some documentation about this `Identifier`");
+/// ```
+///
+/// This generates a newtype `Thing` implementing `Identifier` and several
+/// conversion helpers. Alternatively, if you want to choose the underlying
+/// representation, specify a type implementing `Integer` like this:
+///
+/// ```rust
+/// # #![feature(const_trait_impl)]
+/// # #![feature(const_default)]
+/// # #![feature(const_result_trait_fn)]
+/// # #![feature(const_convert)]
+/// # use azimuth_core::make_id;
+///
+/// make_id!(pub Thing(u16), "Some documentation about this `Identifier`");
+/// ```
+#[macro_export]
+macro_rules! make_id {
+    ($scope:vis $name:ident, $documentation:expr) => {
+        make_id!($scope $name(usize), $documentation);
+    };
+    ($scope:vis $name:ident($integer:tt), $documentation:expr) => {
+        #[repr(transparent)]
+        #[doc = $documentation]
+        #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
+        #[cfg_attr(feature = "core-fmt", derive(Debug))]
+        $scope struct $name(pub(crate) $integer);
+
+        //SAFETY: we don't alter the structure of the underlying `Integer`
+        //        implementation in any way
+        unsafe impl const $crate::id::Identifier for $name {
+            type Integer = $integer;
+
+            fn new(v: Self::Integer) -> Self {
+                Self(v)
+            }
+
+            fn from_usize(v: usize) -> core::result::Result<Self, $crate::id::UsizeTruncationError> {
+                <$integer as $crate::id::Integer>::from_usize(v).map(Self)
+            }
+
+            fn into_representation(self) -> Self::Integer {
+                self.0
+            }
+
+            fn into_usize(self) -> usize {
+                <$integer as $crate::id::Integer>::into_usize(self.0)
+            }
+
+            fn increment(self) -> core::result::Result<Self, $crate::utilities::IntegerOverflowError> {
+                <$integer as $crate::id::Integer>::increment(self.0).map(Self)
+            }
+
+            fn decrement(self) -> core::result::Result<Self, $crate::utilities::IntegerOverflowError> {
+                <$integer as $crate::id::Integer>::decrement(self.0).map(Self)
+            }
+        }
+
+        $crate::make_id!(@try_from_usize $name, $integer);
+
+        impl const Default for $name {
+            fn default() -> Self {
+                Self(<$integer as $crate::id::Integer>::ZERO)
+            }
+        }
+
+        impl const From<$name> for $integer {
+            fn from(id: $name) -> Self {
+                id.0
+            }
+        }
+
+        impl const From<$integer> for $name {
+            fn from(v: $integer) -> Self {
+                Self(v)
+            }
+        }
+    };
+    //NOTE: we ignore this for `usize` because the automatic `TryFrom<usize>`
+    //      implementation would conflict
+    (@try_from_usize $_name:ident, usize) => {};
+    (@try_from_usize $name:ident, $integer:ty) => {
+        impl const TryFrom<usize> for $name {
+            type Error = $crate::id::UsizeTruncationError;
+
+            fn try_from(v: usize) -> Result<Self, Self::Error> {
+                <Self as $crate::id::Identifier>::from_usize(v)
+            }
+        }
+
+        impl const From<$name> for usize {
+            fn from(id: $name) -> Self {
+                <$name as $crate::id::Identifier>::into_usize(id)
+            }
+        }
+    };
+}
+
+/// Dense numeric identifier representation.
 ///
 /// Most implementors of this should be defined using the `id` macro for
 /// consistency in their implementations.
-pub trait Id:
-    Copy + Clone + PartialEq + Eq + PartialOrd + Ord + Hash + Send + Sync
+///
+/// # Safety
+///
+/// `Identifier::from_usize` and `Identifier::into_usize` must form an
+/// order isomorphism between the `Id: Identifier` and an initial segment of
+/// `usize`.
+///
+/// Equivalently:
+///
+/// 1. (Order consistency) For all `Id`s `a`, `b`: `a.cmp(&b) ==
+///    a.into_usize().cmp(&b.into_usize())`.
+///
+/// 2. (Inverse)
+///    - For all `Id`s `a`: `Id::from_usize(a.into_usize()) == Ok(a)`.
+///    - For all `usize`s `u`: if `Id::from_usize(u) == Ok(a)` then
+///      `a.into_usize() == u`.
+///
+/// 3. (Initial segment) If for some `usize` `u`,
+///    `Id::from_usize(u).is_err()`, then for all `v >= u`,
+///    `Id::from_usize(v).is_err()`.
+pub const unsafe trait Identifier:
+    Copy + Eq + Ord + Hash + Send + Sync
 {
     /// The backing integer type for this identifier.
     type Integer: Integer;
@@ -16,6 +151,69 @@ pub trait Id:
     /// Instantiate a new identifier from its underlying representation.
     #[must_use]
     fn new(v: Self::Integer) -> Self;
+
+    /// Instantiate a new identifier from a `usize`.
+    ///
+    /// # Errors
+    ///
+    /// Returns an error if the `usize` is too large to fit in the underlying
+    /// representation.
+    fn from_usize(v: usize) -> Result<Self, UsizeTruncationError>;
+
+    /// Decompose this identifier into its underlying representation.
+    #[must_use]
+    fn into_representation(self) -> Self::Integer;
+
+    /// Decompose this identifier into a `usize`.
+    #[must_use]
+    fn into_usize(self) -> usize;
+
+    /// Increment the underlying value of this identifier.
+    ///
+    /// # Errors
+    ///
+    /// Returns an error if the result would have overflowed.
+    fn increment(self) -> Result<Self, IntegerOverflowError>;
+
+    /// Decrement the underlying value of this identifier.
+    ///
+    /// # Errors
+    ///
+    /// Returns an error if the result would have overflowed.
+    fn decrement(self) -> Result<Self, IntegerOverflowError>;
+}
+
+//SAFETY: this doesn't alter the structure of the underlying `Integer`
+//        implementation in any way
+unsafe impl<T> const Identifier for T
+where
+    T: const Integer,
+{
+    type Integer = T;
+
+    fn new(v: Self::Integer) -> Self {
+        v
+    }
+
+    fn from_usize(v: usize) -> Result<Self, UsizeTruncationError> {
+        T::from_usize(v)
+    }
+
+    fn into_representation(self) -> Self::Integer {
+        self
+    }
+
+    fn into_usize(self) -> usize {
+        <T as Integer>::into_usize(self)
+    }
+
+    fn increment(self) -> Result<Self, IntegerOverflowError> {
+        <T as Integer>::increment(self)
+    }
+
+    fn decrement(self) -> Result<Self, IntegerOverflowError> {
+        <T as Integer>::decrement(self)
+    }
 }
 
 //NOTE: we don't use the same [`Integer`] trait in `numerics` here as there
@@ -23,72 +221,81 @@ pub trait Id:
 //      checked overflow---that may not be wanted in more general arithmetic
 //      operations.
 
-/// Valid integer types backing an [`Id`].
-pub trait Integer:
-    Copy
-    + Clone
-    + PartialEq
-    + Eq
-    + PartialOrd
-    + Ord
-    + Hash
-    + Send
-    + Sync
-    + sealed::Sealed
+/// Valid integer types backing an [`Identifier`].
+pub const trait Integer:
+    Copy + Eq + Ord + Hash + Send + Sync + CheckedArithmeticExt + sealed::Sealed
 {
     /// Zero value of the integer type.
     const ZERO: Self;
 
-    /// Convert this integer into a `usize`.
+    /// Converts this integer into a `usize`.
     fn into_usize(self) -> usize;
 
-    /// Construct an integer from a `usize`.
+    /// Constructs an integer from a `usize`.
     ///
-    /// Returns `None` if no corresponding integer exists.
-    fn from_usize(v: usize) -> Option<Self>;
+    /// # Errors
+    ///
+    /// Returns an error if the `usize` is too large to fit in the integer.
+    fn from_usize(v: usize) -> Result<Self, UsizeTruncationError>;
 
-    /// Returns the successor value of this integer.
+    /// Increments the value of this integer.
+    ///
+    /// # Errors
     ///
-    /// If this would have overflowed, `None` is returned.
-    fn increment(self) -> Option<Self>;
+    /// Returns an error if the result would have overflowed.
+    fn increment(self) -> Result<Self, IntegerOverflowError>;
 
-    //// Returns the predecessor value of this integer.
+    /// Decrements the value of this integer.
+    ///
+    /// # Errors
     ///
-    /// If this would have overflowed, `None` is returned.
-    fn decrement(self) -> Option<Self>;
+    /// Returns an error if the result would have overflowed.
+    fn decrement(self) -> Result<Self, IntegerOverflowError>;
 }
 
 macro_rules! integer_impl {
-    ($t:ty) => {
+    ($t:tt) => {
         impl sealed::Sealed for $t {}
 
-        impl Integer for $t {
+        impl const Integer for $t {
             const ZERO: Self = 0;
 
-            #[allow(trivial_numeric_casts, clippy::cast_possible_truncation)]
-            fn into_usize(self) -> usize {
-                //NOTE: truncation never happens as `Integer` implementations
-                //      are gated behind `target_pointer_width`.
-                self as usize
-            }
+            integer_impl!(@usize_specialization $t);
 
-            #[allow(trivial_numeric_casts, clippy::cast_possible_truncation)]
-            fn from_usize(v: usize) -> Option<Self> {
-                //NOTE: truncation can't happen, see above.
-                if v <= Self::MAX as usize {
-                    //NOTE: we just checked this exists and doesn't truncate.
-                    Some(v as $t)
-                } else {
-                    None
-                }
+            fn increment(self) -> Result<Self, IntegerOverflowError> {
+                self.errored_increment()
             }
 
-            fn increment(self) -> Option<Self> {
-                self.checked_add(1)
+            fn decrement(self) -> Result<Self, IntegerOverflowError> {
+                self.errored_decrement()
             }
+        }
+    };
+    (@usize_specialization usize) => {
+        fn into_usize(self) -> usize {
+            self
+        }
 
-            fn decrement(self) -> Option<Self> {
-                self.checked_sub(1)
+        fn from_usize(v: usize) -> Result<Self, UsizeTruncationError> {
+            Ok(v)
+        }
+    };
+    (@usize_specialization $t:tt) => {
+        #[allow(clippy::cast_possible_truncation)]
+        fn into_usize(self) -> usize {
+            //NOTE: truncation never happens as `Integer` implementations
+            //      are gated behind `target_pointer_width`.
+            self as usize
+        }
+
+        #[allow(clippy::cast_possible_truncation)]
+        fn from_usize(v: usize) -> Result<Self, UsizeTruncationError> {
+            //NOTE: truncation can't happen due to pointer width gating.
+            if v <= Self::MAX as usize {
+                //NOTE: we just checked this exists and doesn't truncate.
+                Ok(v as $t)
+            } else {
+                Err(UsizeTruncationError)
             }
         }
     };
@@ -105,6 +312,22 @@ integer_impl!(u32);
 integer_impl!(u16);
 integer_impl!(u8);
 
+/// Representation of an error caused by a conversion to an integer from a
+/// `usize`.
+#[derive(Copy, Clone, PartialEq, Eq)]
+#[cfg_attr(feature = "core-fmt", derive(Debug))]
+pub struct UsizeTruncationError;
+
+#[cfg(feature = "core-fmt")]
+impl fmt::Display for UsizeTruncationError {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        f.write_str("usize truncation")
+    }
+}
+
+#[cfg(feature = "core-error")]
+impl error::Error for UsizeTruncationError {}
+
 mod sealed {
     pub trait Sealed {}
 }