simple union-find implementation HEAD canon

Change-Id: I32b78b3eee68205032591578fca70c366a6a6964

6 files changed, 675 insertions, 66 deletions

diff --git a/crates/core/src/egraph/mod.rs b/crates/core/src/egraph/mod.rs
index 8e006b3..7b41d2c 100644
--- a/crates/core/src/egraph/mod.rs
+++ b/crates/core/src/egraph/mod.rs
@@ -1,4 +1,6 @@
 //! E-graph implementation.
 
+pub mod union_find;
+
 /// something
 pub struct EGraph {}
diff --git a/crates/core/src/egraph/union_find.rs b/crates/core/src/egraph/union_find.rs
index 8d5422d..daae62c 100644
--- a/crates/core/src/egraph/union_find.rs
+++ b/crates/core/src/egraph/union_find.rs
@@ -1,6 +1,363 @@
 //! Union-find / disjoint-set data structure implementations.
 
-/// Simple union-find implementation.
+use alloc::{
+    alloc::{Allocator, Global},
+    collections::TryReserveError,
+    vec::Vec,
+};
+use core::cmp;
+
+use crate::id::Identifier;
+
+//NOTE: maybe we should look into finding a way to bind identifiers to the
+//      isize cap of vector sizes to avoid the error condition that would
+//      result from saturating this bound?
+
+/// Simple union-find implementation using union by min-id.
 ///
-/// Operates according to a union by min-id scheme.
-pub struct UnionFind {}
+/// All [`Identifier`]s are assumed to be their own parents by default.
+#[derive(Clone)]
+#[cfg_attr(feature = "core-fmt", derive(Debug))]
+pub struct UnionFind<Id, A = Global>
+where
+    A: Allocator + Clone,
+{
+    /// Vector mapping an e-class to its parent e-class.
+    ///
+    /// # Invariants
+    ///
+    /// For every stored parent `p`, `p.into_usize() < self.inner.len()`; and
+    /// for every `i < self.inner.len()`, `Id::from_usize(i)` succeeds.
+    pub(crate) inner: Vec<Id, A>,
+
+    /// Allocator used by the [`UnionFind`].
+    pub(crate) alloc: A,
+}
+
+impl<Id> UnionFind<Id, Global> {
+    /// Constructs an empty union-find data structure.
+    #[must_use]
+    #[inline]
+    pub fn new() -> Self {
+        Self::new_in(Global)
+    }
+}
+
+impl<Id, A> UnionFind<Id, A>
+where
+    A: Allocator + Clone,
+{
+    /// Constructs an empty union-find data structure using the provided
+    /// [`Allocator`].
+    #[must_use]
+    #[inline]
+    pub fn new_in(alloc: A) -> Self {
+        Self {
+            inner: Vec::new_in(alloc.clone()),
+            alloc,
+        }
+    }
+}
+
+impl<Id, A> UnionFind<Id, A>
+where
+    A: Allocator + Clone,
+    Id: Identifier,
+{
+    /// Helper method for converting a `usize` into an [`Identifier`],
+    /// encoding our core assumption.
+    #[must_use]
+    #[inline(always)]
+    fn index_to_id(id: usize) -> Id {
+        debug_assert!(Id::from_usize(id).is_ok());
+
+        //SAFETY: the e-class wouldn't be representable if a usize didn't fit
+        //        into its id
+        unsafe { Id::from_usize(id).unwrap_unchecked() }
+    }
+
+    /// Makes all represented e-classes their own parents.
+    ///
+    /// This does not free up any space; it only edits e-classes already
+    /// represented.
+    #[inline]
+    pub fn reset(&mut self) {
+        for (child, parent) in self.inner.iter_mut().enumerate() {
+            *parent = Self::index_to_id(child);
+        }
+    }
+
+    /// Removes all represented e-classes from the data structure.
+    ///
+    /// This does not return any used memory to the operating system; it only
+    /// calls [`Vec::clear`].
+    #[inline(always)]
+    pub fn clear(&mut self) {
+        self.inner.clear();
+    }
+
+    /// Shrinks the internal data structure so that the minimum amount of
+    /// memory is used.
+    #[inline(always)]
+    pub fn shrink_to_fit(&mut self) {
+        self.inner.shrink_to_fit();
+    }
+
+    /// Returns the id of the represented e-class with the greatest id.
+    #[inline]
+    pub fn greatest_represented(&self) -> Option<Id> {
+        if let Some(id) = self.inner.len().checked_sub(1) {
+            return Some(Self::index_to_id(id));
+        }
+        None
+    }
+
+    /// Indicates if no e-classes are represented.
+    #[inline(always)]
+    pub fn is_empty(&self) -> bool {
+        self.inner.is_empty()
+    }
+
+    /// Reserves sufficient space in the union-find data structure to contain
+    /// all of the given e-class ids.
+    ///
+    /// # Errors
+    ///
+    /// An error is returned if reserving space for new ids fails.
+    #[inline(always)]
+    pub fn ensure_contains_all(
+        &mut self,
+        ids: impl IntoIterator<Item = Id>,
+    ) -> Result<(), TryReserveError> {
+        if let Some(id) = ids.into_iter().max() {
+            self.ensure_contains(id)?;
+        }
+        Ok(())
+    }
+
+    /// Reserves sufficient space in the union-find data structure to contain
+    /// the given e-class id.
+    ///
+    /// # Errors
+    ///
+    /// An error is returned if reserving space for new ids fails.
+    #[inline]
+    pub fn ensure_contains(&mut self, id: Id) -> Result<(), TryReserveError> {
+        let index = id.into_usize();
+
+        if index < self.inner.len() {
+            return Ok(());
+        }
+
+        let current_size = self.inner.len();
+
+        //NOTE: we just established that index is at least equal to the
+        //      length of the parent vector and `saturating_add` will prevent
+        //      roll-over to 0 from `usize::MAX`
+        self.inner.try_reserve(
+            index.wrapping_sub(current_size).saturating_add(1),
+        )?;
+
+        for (parent, child) in self
+            .inner
+            .spare_capacity_mut()
+            .iter_mut()
+            .zip(current_size..=index)
+        {
+            parent.write(Self::index_to_id(child));
+        }
+
+        //NOTE: we know by the requirement that vectors (containing non-ZSTs)
+        //      may have at most a size of `isize::MAX` that our index is
+        //      nowhere near `usize::MAX`
+        //SAFETY: we just wrote to the unused capacity
+        unsafe {
+            self.inner.set_len(index.wrapping_add(1));
+        }
+
+        Ok(())
+    }
+
+    /// Locates the canonical representation of the given e-class without
+    /// performing path compression.
+    #[inline]
+    pub fn find(&self, id: Id) -> Id {
+        if id.into_usize() >= self.inner.len() {
+            return id;
+        }
+
+        //NOTE: we know all further indices are valid from this point on
+
+        let mut current = id;
+        loop {
+            //SAFETY: refer to the above note
+            let parent =
+                *unsafe { self.inner.get_unchecked(current.into_usize()) };
+            if current == parent {
+                break current;
+            }
+            current = parent;
+        }
+    }
+
+    /// Indicates if two e-class ids share the same parent.
+    #[inline(always)]
+    pub fn equivalent(&self, a: Id, b: Id) -> bool {
+        self.find(a) == self.find(b)
+    }
+
+    /// Indicates if two e-class ids share the same parent, performing path
+    /// compression.
+    #[inline(always)]
+    pub fn equivalent_mut(&mut self, a: Id, b: Id) -> bool {
+        self.find_mut(a) == self.find_mut(b)
+    }
+
+    /// Locates the canonical representation of the given e-class, performing
+    /// path compression.
+    #[inline]
+    pub fn find_mut(&mut self, id: Id) -> Id {
+        if id.into_usize() >= self.inner.len() {
+            return id;
+        }
+
+        let mut current = id;
+        let base_ptr = self.inner.as_mut_ptr();
+
+        //SAFETY: we know these indices are in bounds after the check above
+        //        and due to invariants on the contents of the vector
+        unsafe {
+            loop {
+                let parent_ptr = base_ptr.add(current.into_usize());
+                let parent = *parent_ptr;
+
+                if current == parent {
+                    break current;
+                }
+
+                let grandparent = *base_ptr.add(parent.into_usize());
+                parent_ptr.write(grandparent);
+                current = grandparent;
+            }
+        }
+    }
+
+    /* TODO: implement this and the data structure it will use
+    /// Locates the canonical representation of several e-classes, performing path compression.
+    #[inline]
+    pub fn find_mut_all(&mut self, ids: impl IntoIterator<Item = Id>) -> Result<FindMutAll<Id>, TryReserveError> {
+        //NOTE: needs a try_extend or something to fallibly collect the iterator into a new vec and sort it. we can do this but it'd be more work in the utilities file
+    }
+    */
+
+    /// Merges the given e-classes and returns their representatives,
+    /// indicating which is the parent of the other.
+    ///
+    /// If either is not present and they differ, space is reserved for them
+    /// both.
+    ///
+    /// # Errors
+    ///
+    /// An error is returned if reserving space for new ids fails.
+    #[inline]
+    pub fn merge(
+        &mut self,
+        a: Id,
+        b: Id,
+    ) -> Result<Union<Id>, TryReserveError> {
+        let a = self.find_mut(a);
+        let b = self.find_mut(b);
+
+        let [parent, child] = cmp::minmax(a, b);
+
+        if parent != child {
+            self.ensure_contains(child)?;
+
+            //SAFETY: because of invariants on the inner vector, and due to
+            //        us reserving space if the id is not already contained,
+            //        this is safe
+            *unsafe { self.inner.get_unchecked_mut(child.into_usize()) } =
+                parent;
+        }
+
+        Ok(Union { parent, child })
+    }
+}
+
+impl<Id> Default for UnionFind<Id, Global> {
+    fn default() -> Self {
+        Self::new()
+    }
+}
+
+/// Result of merging two e-classes.
+#[derive(Debug, Copy, Clone, PartialEq, Eq)]
+pub struct Union<Id> {
+    /// The parent e-class.
+    pub parent: Id,
+
+    /// The child e-class.
+    pub child: Id,
+}
+
+impl<Id> Union<Id>
+where
+    Id: Identifier,
+{
+    /// Indicates if an e-class merge was made in this union operation.
+    #[must_use]
+    #[inline(always)]
+    pub fn changed(&self) -> bool {
+        self.parent != self.child
+    }
+}
+
+/// Iterator over canonical representations of e-classes.
+pub struct FindMutAll<'a, Id, A>
+where
+    A: Allocator + Clone,
+{
+    /// The union find we are locating canonical representations within.
+    pub(crate) union_find: &'a mut UnionFind<Id, A>,
+
+    /// The `Id`s we are finding canonical representations of.
+    pub(crate) ids: Vec<Id, A>,
+}
+
+#[cfg(all(test, feature = "core-error"))]
+mod test {
+    use super::*;
+
+    #[test]
+    fn union_find_reserve() {
+        let mut union_find = UnionFind::default();
+
+        union_find
+            .ensure_contains(5usize)
+            .expect("unable to reserve space to contain an identifier");
+
+        assert_eq!(&[0, 1, 2, 3, 4, 5], union_find.inner.as_slice());
+
+        union_find
+            .ensure_contains(6usize)
+            .expect("unable to reserve space to contain an identifier");
+
+        assert_eq!(&[0, 1, 2, 3, 4, 5, 6], union_find.inner.as_slice());
+
+        union_find
+            .ensure_contains(5usize)
+            .expect("unable to reserve space to contain an identifier");
+
+        assert_eq!(&[0, 1, 2, 3, 4, 5, 6], union_find.inner.as_slice());
+
+        union_find
+            .ensure_contains(0usize)
+            .expect("unable to reserve space to contain an identifier");
+
+        assert_eq!(&[0, 1, 2, 3, 4, 5, 6], union_find.inner.as_slice());
+
+        union_find
+            .ensure_contains(usize::MAX)
+            .expect_err("reserving greater than `isize::MAX` should fail");
+    }
+}
diff --git a/crates/core/src/expressions/mod.rs b/crates/core/src/expressions/mod.rs
index 5ffb5a6..eadd55d 100644
--- a/crates/core/src/expressions/mod.rs
+++ b/crates/core/src/expressions/mod.rs
@@ -1040,7 +1040,7 @@ where
 
 /// Representation of an error that occurred within [`Expression`].
 #[non_exhaustive]
-#[derive(PartialEq, Eq)]
+#[derive(Clone, PartialEq, Eq)]
 #[cfg_attr(feature = "core-fmt", derive(Debug))]
 pub enum Error {
     /// Memory reservation error.
@@ -1093,6 +1093,10 @@ impl error::Error for Error {}
 
 #[cfg(all(test, feature = "core-error"))]
 mod test {
+    #![allow(clippy::arithmetic_side_effects)]
+    #![allow(clippy::indexing_slicing)]
+    #![allow(clippy::unreachable)]
+    #![allow(clippy::wildcard_enum_match_arm)]
     #![allow(clippy::expect_used)]
 
     use super::*;
@@ -1258,7 +1262,10 @@ mod test {
         type Transition = ExpressionTransition;
 
         fn init_state() -> BoxedStrategy<Self::State> {
-            //TODO: randomly initialize state
+            //NOTE: we could randomly initialize state. i don't think this is
+            //      necessary to test this sufficiently, but if we ever do, we
+            //      also need to tweak the constructor of the [`Expression`]
+            //      to replicate one from the reference state
             Just(Self::State::default()).boxed()
         }
 
@@ -1436,17 +1443,8 @@ mod test {
         type Reference = ExpressionReference;
 
         fn init_test(
-            ref_state: &<Self::Reference as ReferenceStateMachine>::State,
+            _ref_state: &<Self::Reference as ReferenceStateMachine>::State,
         ) -> Self::SystemUnderTest {
-            /*let mut expr = Expression {
-                inner: Vec::new(),
-                interns: Vec::new(),
-                root: ref_state.root.map(NodeIndexInternal),
-            };
-
-            for node in ref_state.nodes {
-                //TODO: finish replicating state over here
-            }*/
             ExpressionWrapper::Closed(Expression::new())
         }
 
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 {}
 }
diff --git a/crates/core/src/lib.rs b/crates/core/src/lib.rs
index 24b7ac3..0b40bbd 100644
--- a/crates/core/src/lib.rs
+++ b/crates/core/src/lib.rs
@@ -4,6 +4,13 @@
 #![feature(trusted_len)]
 #![feature(assert_matches)]
 #![feature(stmt_expr_attributes)]
+#![feature(const_trait_impl)]
+#![feature(const_option_ops)]
+#![feature(const_result_trait_fn)]
+#![feature(const_convert)]
+#![feature(const_default)]
+#![feature(const_clone)]
+#![feature(cmp_minmax)]
 
 //! A highly portable computer algebra system library implemented in Rust.
 
diff --git a/crates/core/src/utilities.rs b/crates/core/src/utilities.rs
index 583ad7c..b6bb86d 100644
--- a/crates/core/src/utilities.rs
+++ b/crates/core/src/utilities.rs
@@ -34,7 +34,7 @@ where
 }
 
 /// Extension trait for wrapping arithmetic.
-pub trait WrappingArithmeticExt {
+pub const trait WrappingArithmeticExt {
     /// Wrapping integer increment.
     fn wrapping_increment(self) -> Self;
 
@@ -50,7 +50,7 @@ pub trait WrappingArithmeticExt {
 
 macro_rules! wrapping_arithmetic_ext_impl {
     ($t:ty) => {
-        impl WrappingArithmeticExt for $t {
+        impl const WrappingArithmeticExt for $t {
             fn wrapping_increment(self) -> Self {
                 self.wrapping_add(1)
             }
@@ -84,7 +84,7 @@ wrapping_arithmetic_ext_impl!(i8);
 
 /// Extension trait for checked arithmetic that turns the output into a
 /// [`Result`].
-pub trait CheckedArithmeticExt: Sized {
+pub const trait CheckedArithmeticExt: Sized {
     /// Checked integer addition.
     ///
     /// # Errors
@@ -92,6 +92,13 @@ pub trait CheckedArithmeticExt: Sized {
     /// Returns an error if the result would have overflowed.
     fn errored_add(self, rhs: Self) -> Result<Self, IntegerOverflowError>;
 
+    /// Checked integer decrement.
+    ///
+    /// # Errors
+    ///
+    /// Returns an error if the result would have overflowed.
+    fn errored_decrement(self) -> Result<Self, IntegerOverflowError>;
+
     /// Checked integer division.
     ///
     /// # Errors
@@ -99,6 +106,13 @@ pub trait CheckedArithmeticExt: Sized {
     /// Returns an error if the result would have overflowed.
     fn errored_div(self, rhs: Self) -> Result<Self, IntegerOverflowError>;
 
+    /// Checked integer increment.
+    ///
+    /// # Errors
+    ///
+    /// Returns an error if the result would have overflowed.
+    fn errored_increment(self) -> Result<Self, IntegerOverflowError>;
+
     /// Checked integer multiplication.
     ///
     /// # Errors
@@ -123,7 +137,7 @@ pub trait CheckedArithmeticExt: Sized {
 
 macro_rules! checked_arithmetic_ext_impl {
     ($t:ty) => {
-        impl CheckedArithmeticExt for $t {
+        impl const CheckedArithmeticExt for $t {
             fn errored_add(
                 self,
                 rhs: Self,
@@ -131,6 +145,10 @@ macro_rules! checked_arithmetic_ext_impl {
                 self.checked_add(rhs).ok_or(IntegerOverflowError)
             }
 
+            fn errored_decrement(self) -> Result<Self, IntegerOverflowError> {
+                self.errored_sub(1)
+            }
+
             fn errored_div(
                 self,
                 rhs: Self,
@@ -138,6 +156,10 @@ macro_rules! checked_arithmetic_ext_impl {
                 self.checked_div(rhs).ok_or(IntegerOverflowError)
             }
 
+            fn errored_increment(self) -> Result<Self, IntegerOverflowError> {
+                self.errored_add(1)
+            }
+
             fn errored_mul(
                 self,
                 rhs: Self,
@@ -175,7 +197,7 @@ checked_arithmetic_ext_impl!(i16);
 checked_arithmetic_ext_impl!(i8);
 
 /// Representation of an integer overflow error.
-#[derive(PartialEq, Eq)]
+#[derive(Copy, Clone, PartialEq, Eq)]
 #[cfg_attr(feature = "core-fmt", derive(Debug))]
 pub struct IntegerOverflowError;