node topological sorting

Change-Id: I6a6a6964255d818be1bf9a8f4ec9e317befa19c5

10 files changed, 731 insertions, 650 deletions

diff --git a/crates/core/Cargo.toml b/crates/core/Cargo.toml
index f7c0d75..ac6d047 100644
--- a/crates/core/Cargo.toml
+++ b/crates/core/Cargo.toml
@@ -32,3 +32,6 @@ generativity.workspace = true
 [dev-dependencies]
 proptest.workspace = true
 proptest-state-machine.workspace = true
+
+[lints]
+workspace = true
diff --git a/crates/core/src/egraph/mod.rs b/crates/core/src/egraph/mod.rs
new file mode 100644
index 0000000..8e006b3
--- /dev/null
+++ b/crates/core/src/egraph/mod.rs
@@ -0,0 +1,4 @@
+//! E-graph implementation.
+
+/// something
+pub struct EGraph {}
diff --git a/crates/core/src/egraph/union_find.rs b/crates/core/src/egraph/union_find.rs
new file mode 100644
index 0000000..8d5422d
--- /dev/null
+++ b/crates/core/src/egraph/union_find.rs
@@ -0,0 +1,6 @@
+//! Union-find / disjoint-set data structure implementations.
+
+/// Simple union-find implementation.
+///
+/// Operates according to a union by min-id scheme.
+pub struct UnionFind {}
diff --git a/crates/core/src/expressions/mod.rs b/crates/core/src/expressions/mod.rs
index 902ead1..5ffb5a6 100644
--- a/crates/core/src/expressions/mod.rs
+++ b/crates/core/src/expressions/mod.rs
@@ -7,10 +7,16 @@ use alloc::{
     vec,
     vec::Vec,
 };
-use core::{hint, iter::TrustedLen};
+use core::{hint, iter::TrustedLen, mem::MaybeUninit};
 use generativity::{Guard, Id};
 
-use crate::numerics::rational::Rational;
+use crate::{
+    numerics::rational::Rational,
+    utilities::{
+        CheckedArithmeticExt, IntegerOverflowError, VecMemoryExt,
+        WrappingArithmeticExt,
+    },
+};
 
 #[cfg(feature = "core-fmt")]
 use core::fmt;
@@ -18,15 +24,11 @@ use core::fmt;
 #[cfg(feature = "core-error")]
 use core::error;
 
-//TODO: consider topological sorting of the expression's internals as this
-//      may be better for performance.
-//TODO: consider garbage collection of unreachable nodes (and their
-//      children).
-//TODO: if we add garbage collection, support marking a node for deletion
-//      when garbage collection is performed.
-//TODO: consider renaming `OpenExpression` to something else.
-//TODO: add more thorough documentation, along the lines of the standard
-//      library's `Vec`, given how this is a very fundamental type.
+//TODO: support marking a node for deletion when garbage collection is
+//      performed.
+//TODO: consider btree/hashmap for interned strings to speed up the process
+//      of locating the intern.
+//TODO: make topological sorting in-place.
 
 /// Representation of a mathematical expression.
 ///
@@ -54,10 +56,14 @@ where
 
     /// Root node of the expression.
     pub(crate) root: Option<NodeIndexInternal>,
+
+    /// Allocator used by the [`Expression`].
+    pub(crate) alloc: A,
 }
 
 impl Expression<Global> {
     /// Constructs an empty expression.
+    #[must_use]
     pub fn new() -> Self {
         Self::new_in(Global)
     }
@@ -68,21 +74,80 @@ where
     A: Allocator + Clone,
 {
     /// Constructs an empty expression using the provided [`Allocator`].
+    #[must_use]
     pub fn new_in(alloc: A) -> Self {
         Self {
             inner: Vec::new_in(alloc.clone()),
-            interns: Vec::new_in(alloc),
+            interns: Vec::new_in(alloc.clone()),
             root: None,
+            alloc,
         }
     }
 
     /// Clears the expression, removing all nodes and associated information.
+    ///
+    /// This does not free up unused space. To do that, use
+    /// [`Expression::shrink_to_fit`] after calling this.
     pub fn clear(&mut self) {
         self.inner.clear();
         self.interns.clear();
         self.root = None;
     }
 
+    /// Sorts and garbage collects the node list.
+    ///
+    /// This may not necessarily free the unused memory. To ensure that
+    /// happens, call [`Expression::shrink_to_fit`] after calling this.
+    ///
+    /// # Errors
+    ///
+    /// An error is returned if reserving space for the permutation vector
+    /// failed or if a cycle was found.
+    ///
+    /// The latter should not happen, but is enumerated in possible errors for
+    /// testing purposes. Prefer crashing if this happens.
+    pub fn sort(mut self) -> Result<Self, Error> {
+        if let Some(root) = self.root {
+            let (permutation, n_reachable) = permutation_vector_of(
+                self.alloc.clone(),
+                root,
+                self.inner.as_slice(),
+            )?;
+
+            let mut inner =
+                Vec::with_capacity_in(n_reachable, self.alloc.clone());
+
+            let start = inner.as_mut_ptr() as *mut MaybeUninit<NodeInternal>;
+            for (node, position) in self.inner.into_iter().zip(permutation) {
+                if position != usize::MAX {
+                    //SAFETY: positions are guaranteed to be less than
+                    //        `n_reachable` as `n_reachable` would have been
+                    //        the next position, all indices are unique
+                    unsafe {
+                        start.add(position).write(MaybeUninit::new(node));
+                    }
+                }
+            }
+
+            //SAFETY: we sized the vector to contain exactly the number of
+            //        reachable nodes
+            unsafe { inner.set_len(n_reachable) };
+
+            self.inner = inner;
+        } else {
+            self.clear();
+        }
+
+        Ok(self)
+    }
+
+    /// Shrinks the capacity of the node list and intern list as much as
+    /// possible.
+    pub fn shrink_to_fit(&mut self) {
+        self.inner.shrink_to_fit();
+        self.interns.shrink_to_fit();
+    }
+
     /// Opens up the expression for additive operations and indexing.
     ///
     /// While in this state, no destructive operations may be done, such as
@@ -101,10 +166,9 @@ where
         &mut self,
         node: NodeInternal,
     ) -> Result<NodeIndexInternal, Error> {
-        self.inner.try_reserve(1)?;
-        //SAFETY: we just reserved space for this element
-        unsafe { self.inner.push_within_capacity(node).unwrap_unchecked() }
-        Ok(NodeIndexInternal(self.inner.len() - 1))
+        let index = self.inner.len();
+        self.inner.try_push(node)?;
+        Ok(NodeIndexInternal(index))
     }
 
     /// Inserts a [`&str`] into the intern list if it doesn't already exist
@@ -124,14 +188,9 @@ where
             return Ok(StringIndexInternal(i));
         }
 
-        self.interns.try_reserve(1)?;
-        //SAFETY: we just reserved space for this element
-        unsafe {
-            self.interns
-                .push_within_capacity(string.as_ref().into())
-                .unwrap_unchecked()
-        }
-        Ok(StringIndexInternal(self.interns.len() - 1))
+        let index = self.interns.len();
+        self.interns.try_push(string.as_ref().into())?;
+        Ok(StringIndexInternal(index))
     }
 
     /// Returns the number of nodes within this expression.
@@ -175,6 +234,9 @@ where
 
             while let Some((node_index, state)) = stack.pop() {
                 //SAFETY: all internal indices are guaranteed to be valid
+                //NOTE: this lint is ignored because we have a state machine
+                //      test which exercises this wildcard arm
+                #[allow(clippy::wildcard_enum_match_arm)]
                 match *unsafe { self.inner.get_unchecked(node_index.0) } {
                     NodeInternal::BinaryOperation(_, _, _)
                         if state == State::Close =>
@@ -243,7 +305,11 @@ where
                             self.interns.get_unchecked(s)
                         })?;
                     }
-                    _ => unreachable!(),
+                    _ =>
+                    {
+                        #![allow(clippy::unreachable)]
+                        unreachable!()
+                    }
                 }
             }
         }
@@ -347,8 +413,15 @@ where
             )
                 .into())
         } else {
+            //NOTE: used to roll back the vector if an invalid child node is
+            //      found in the arguments
+            let rollback_size = self.0.inner.len();
+
             let number_of_joins = n_arguments.saturating_sub(1);
-            self.0.inner.try_reserve(number_of_joins + 1)?;
+            self.0.inner.try_reserve(number_of_joins.errored_add(1)?)?;
+
+            //NOTE: we define this beforehand to avoid arithmetic
+            let operation_index = NodeIndexInternal(self.0.inner.len());
 
             //SAFETY: the iterator is required to implement `TrustedLen` so
             //        we will have reserved enough space for these in addition
@@ -381,30 +454,39 @@ where
                         //      more slot to hold an `NodeInternal::Join`
                         _ => NodeInternal::Operation(
                             operator,
-                            Some(NodeIndexInternal(self.0.inner.len() + 1)),
+                            //NOTE: `Vec::len` is bounded by `isize::MAX`
+                            //      for non-ZSTs
+                            Some(NodeIndexInternal(
+                                self.0.inner.len().wrapping_add(1),
+                            )),
                         ),
                     })
-                    .unwrap_unchecked()
+                    .unwrap_unchecked();
             }
-            let operation_index = NodeIndexInternal(self.0.inner.len() - 1);
+
+            //NOTE: we know by this point that the number of arguments is at
+            //      least 3 for the code that uses it
+            let final_index = n_arguments.wrapping_sub(1);
 
             //NOTE: we are exclusively inserting `NodeInternal::Join`s now
             for (i, argument) in arguments.enumerate() {
+                //NOTE: this check is necessary because it is possible for a
+                //      consumer to get a lifetime-branded index to a `Join`
+                //      node
                 if matches!(
                     //SAFETY: lifetime branding ensures this index is valid
                     unsafe { self.0.inner.get_unchecked(argument.0) },
                     NodeInternal::Join(_, _)
                 ) {
-                    //NOTE: leaving the inner vector in this state is not
-                    //      invalid as nothing will be able to reference any
-                    //      of the slots allocated already
-                    //
-                    //      when it is added, garbage collection will clean up
-                    //      after this if it happens
+                    //NOTE: this is necessary to avoid any invalid indices
+                    //      being present in the vector when we perform
+                    //      topological sort
+                    self.0.inner.truncate(rollback_size);
+
                     return Err(Error::InvalidChild);
                 }
 
-                if i != n_arguments - 1 {
+                if i != final_index {
                     //SAFETY: we know that we have reserved enough space for
                     //        each join by this point
                     unsafe {
@@ -412,18 +494,23 @@ where
                             .inner
                             .push_within_capacity(NodeInternal::Join(
                                 argument.into(),
-                                NodeIndexInternal(self.0.inner.len() + 1),
+                                //NOTE: `Vec::len` is bounded by
+                                //      `isize::MAX` for non-ZSTs
+                                NodeIndexInternal(
+                                    self.0.inner.len().wrapping_add(1),
+                                ),
                             ))
-                            .unwrap_unchecked()
+                            .unwrap_unchecked();
                     }
                 } else {
-                    let last_index = self.0.inner.len() - 1;
+                    //NOTE: this is okay because we added the previous index
+                    let previous_index = self.0.inner.len().wrapping_sub(1);
 
                     if let &mut NodeInternal::Join(_, ref mut second) =
                         //SAFETY: we know that if we are at this point,
                         //        the current last element exists
                         unsafe {
-                            self.0.inner.get_unchecked_mut(last_index)
+                            self.0.inner.get_unchecked_mut(previous_index)
                         }
                     {
                         *second = argument.into();
@@ -451,12 +538,12 @@ where
 
     /// Returns the number of nodes within this expression.
     pub fn len(&self) -> usize {
-        self.0.inner.len()
+        self.0.len()
     }
 
     /// Indicates if the expression has no nodes.
     pub fn is_empty(&self) -> bool {
-        self.0.inner.is_empty()
+        self.0.is_empty()
     }
 
     /// Gets the root node of the expression, if it exists.
@@ -565,23 +652,12 @@ impl<'a, 'id> Iterator for Children<'a, 'id> {
             let current = unsafe { self.inner.get_unchecked(current.0) };
             Some(
                 (
+                    //NOTE: this lint is ignored because we have a state
+                    //      machine test which exercises this wildcard arm
+                    #[allow(clippy::wildcard_enum_match_arm)]
                     match *current {
-                        NodeInternal::Operation(_, Some(index)) => {
-                            //SAFETY: all internal indices are guaranteed to
-                            //        be valid
-                            let next =
-                                unsafe { self.inner.get_unchecked(index.0) };
-
-                            if let NodeInternal::Join(child_index, _) = *next
-                            {
-                                self.current = Some(index);
-                                child_index
-                            } else {
-                                self.current = None;
-                                index
-                            }
-                        }
-                        NodeInternal::Join(_, index) => {
+                        NodeInternal::Join(_, index)
+                        | NodeInternal::Operation(_, Some(index)) => {
                             //SAFETY: all internal indices are guaranteed to
                             //        be valid
                             let next =
@@ -606,7 +682,11 @@ impl<'a, 'id> Iterator for Children<'a, 'id> {
                             self.current = None;
                             index
                         }
-                        _ => unreachable!(),
+                        _ =>
+                        {
+                            #![allow(clippy::unreachable)]
+                            unreachable!()
+                        }
                     },
                     self.id,
                 )
@@ -623,7 +703,7 @@ impl<'a, 'id> Iterator for Children<'a, 'id> {
 #[derive(Eq, PartialEq, Copy, Clone, Hash)]
 #[cfg_attr(feature = "core-fmt", derive(Debug))]
 //NOTE: false positive, see https://github.com/CAD97/generativity/issues/13
-#[allow(repr_transparent_external_private_fields)]
+#[allow(repr_transparent_non_zst_fields)]
 pub struct NodeIndex<'id>(usize, Id<'id>);
 
 impl<'id> From<(NodeIndexInternal, Id<'id>)> for NodeIndex<'id> {
@@ -652,7 +732,7 @@ impl From<NodeIndex<'_>> for NodeIndexInternal {
 #[derive(Eq, PartialEq, Copy, Clone, Hash)]
 #[cfg_attr(feature = "core-fmt", derive(Debug))]
 //NOTE: false positive, see https://github.com/CAD97/generativity/issues/13
-#[allow(repr_transparent_external_private_fields)]
+#[allow(repr_transparent_non_zst_fields)]
 pub struct StringIndex<'id>(usize, Id<'id>);
 
 impl<'id> From<(StringIndexInternal, Id<'id>)> for StringIndex<'id> {
@@ -798,19 +878,189 @@ impl fmt::Display for ScalarValue {
     }
 }
 
+/// Returns a permutation vector for the given list of [`Expression`] nodes
+/// and the number of reachable nodes.
+///
+/// Applying this permutation vector to the node list will topologically sort
+/// it. Nodes without any incoming edges will be marked with `usize::MAX` in
+/// the permutation vector. The root node is ignored as it is not expected to
+/// have an incoming edge. This is acceptable as given our constraints, it is
+/// not possible for an index to be greater than `isize::MAX`.
+///
+/// # Errors
+///
+/// An error is returned if a cycle was found or if reserving space for the
+/// permutation vector failed.
+fn permutation_vector_of<A>(
+    alloc: A,
+    root: NodeIndexInternal,
+    vertices: &[NodeInternal],
+) -> Result<(Vec<usize, A>, usize), Error>
+where
+    A: Allocator + Clone,
+{
+    let mut indegree =
+        Vec::try_with_capacity_in(vertices.len(), alloc.clone())?;
+    indegree.resize(vertices.len(), 0);
+
+    //NOTE: used to queue nodes for reachability checks and Kahn's algorithm
+    let mut worklist = Vec::try_with_capacity_in(1, alloc.clone())?;
+
+    //SAFETY: we just reserved space for this element
+    unsafe {
+        worklist.push_within_capacity(root.0).unwrap_unchecked();
+    }
+
+    //NOTE: maps indices to their index in a topologically sorted node
+    //      vector. indices with the value of `usize::MAX` are not
+    //      reachable and should be removed by garbage collection. during the
+    //      reachability check, nodes which are reachable are mapped to
+    //      themselves as this is harmless and can be used to skip seen nodes
+    let mut permutation = Vec::try_with_capacity_in(vertices.len(), alloc)?;
+    permutation.resize(vertices.len(), usize::MAX);
+
+    let mut n_reachable = 0usize;
+    while let Some(current) = worklist.pop() {
+        //SAFETY: we have reserved enough space to track the permuted index
+        //        of all valid indices
+        let permuted_index =
+            unsafe { permutation.get_unchecked_mut(current) };
+        if *permuted_index == current {
+            continue;
+        }
+        *permuted_index = current;
+
+        //NOTE: this is okay because allocation sizes are limited to
+        //      `isize::MAX`;
+        n_reachable.wrapping_increment_mut();
+
+        //SAFETY: all indices in the vertex list are valid
+        #[allow(clippy::wildcard_enum_match_arm)]
+        match unsafe { vertices.get_unchecked(current) } {
+            NodeInternal::Operation(_, Some(NodeIndexInternal(i))) => {
+                //SAFETY: we have reserved enough space to track the indegree
+                //        of all valid indices
+                unsafe { indegree.get_unchecked_mut(*i) }
+                    .wrapping_increment_mut();
+
+                worklist.try_push(*i)?;
+            }
+            NodeInternal::Join(
+                NodeIndexInternal(i),
+                NodeIndexInternal(j),
+            )
+            | NodeInternal::BinaryOperation(
+                _,
+                NodeIndexInternal(i),
+                NodeIndexInternal(j),
+            ) => {
+                //SAFETY: ditto
+                unsafe { indegree.get_unchecked_mut(*i) }
+                    .wrapping_increment_mut();
+
+                worklist.try_push(*i)?;
+
+                //SAFETY: ditto
+                unsafe { indegree.get_unchecked_mut(*j) }
+                    .wrapping_increment_mut();
+
+                worklist.try_push(*j)?;
+            }
+            _ => (),
+        }
+    }
+
+    //NOTE: tracks the location of the cursor within the permuted vector and
+    //      serves as a count of the nodes which we have permuted
+    let mut permuted_position = 0;
+
+    //NOTE: double check there's no cycle that goes to root.
+    //SAFETY: we have reserved enough space to track the indegree of all
+    //        valid indices
+    if *unsafe { indegree.get_unchecked(root.0) } != 0 {
+        return Err(Error::Cycle);
+    }
+
+    worklist.try_push(root.0)?;
+    while let Some(current) = worklist.pop() {
+        //SAFETY: we constructed the permutation vector so that indexing into
+        //        it with vertex indices is always okay
+        *unsafe { permutation.get_unchecked_mut(current) } =
+            permuted_position;
+        permuted_position.wrapping_increment_mut();
+
+        //SAFETY: all indices in the vertex list are valid
+        #[allow(clippy::wildcard_enum_match_arm)]
+        match unsafe { vertices.get_unchecked(current) } {
+            NodeInternal::Operation(_, Some(NodeIndexInternal(i))) => {
+                //SAFETY: we have reserved enough space to track the indegree
+                //        of all valid indices
+                let indegree_of_i = unsafe { indegree.get_unchecked_mut(*i) };
+
+                indegree_of_i.wrapping_decrement_mut();
+                if *indegree_of_i == 0 {
+                    worklist.try_push(*i)?;
+                }
+            }
+            NodeInternal::Join(
+                NodeIndexInternal(i),
+                NodeIndexInternal(j),
+            )
+            | NodeInternal::BinaryOperation(
+                _,
+                NodeIndexInternal(i),
+                NodeIndexInternal(j),
+            ) => {
+                //SAFETY: ditto
+                let indegree_of_i = unsafe { indegree.get_unchecked_mut(*i) };
+
+                indegree_of_i.wrapping_decrement_mut();
+                if *indegree_of_i == 0 {
+                    worklist.try_push(*i)?;
+                }
+
+                //SAFETY: ditto
+                let indegree_of_j = unsafe { indegree.get_unchecked_mut(*j) };
+
+                indegree_of_j.wrapping_decrement_mut();
+                if *indegree_of_j == 0 {
+                    worklist.try_push(*j)?;
+                }
+            }
+            _ => (),
+        }
+    }
+
+    if n_reachable == permuted_position {
+        Ok((permutation, n_reachable))
+    } else {
+        Err(Error::Cycle)
+    }
+}
+
 /// Representation of an error that occurred within [`Expression`].
 #[non_exhaustive]
-#[derive(Eq, PartialEq)]
+#[derive(PartialEq, Eq)]
 #[cfg_attr(feature = "core-fmt", derive(Debug))]
 pub enum Error {
     /// Memory reservation error.
     TryReserveError(TryReserveError),
 
+    /// Unhandleable integer overflow error.
+    IntegerOverflowError,
+
     /// Invalid child node.
     ///
     /// This occurs when you attempt to pass an index that points to a
     /// [`Node::Join`] as a child of an operation.
     InvalidChild,
+
+    /// A cycle was found in the [`Expression`].
+    ///
+    /// This is impossible, but representable as an error state for testing
+    /// purposes.
+    #[doc(hidden)]
+    Cycle,
 }
 
 impl From<TryReserveError> for Error {
@@ -819,12 +1069,20 @@ impl From<TryReserveError> for Error {
     }
 }
 
+impl From<IntegerOverflowError> for Error {
+    fn from(_: IntegerOverflowError) -> Self {
+        Self::IntegerOverflowError
+    }
+}
+
 #[cfg(feature = "core-fmt")]
 impl fmt::Display for Error {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
         let reason = match self {
             Error::TryReserveError(_) => "unable to allocate memory",
+            Error::IntegerOverflowError => "integer overflow",
             Error::InvalidChild => "invalid child node",
+            Error::Cycle => "expression contains a cycle",
         };
         f.write_str(reason)
     }
@@ -888,9 +1146,16 @@ mod test {
         );
 
         expr.set_root_node(product);
-        let expr = expr.close();
 
-        println!("{}", expr);
+        let old_length = expr.len();
+        let expr = expr.close().sort().expect("unable to sort an expression");
+        assert_eq!(old_length, expr.len());
+
+        make_guard!(h);
+        let mut expr = expr.open(h);
+        expr.take_root_node();
+        let expr = expr.close().sort().expect("unable to sort an expression");
+        assert!(expr.is_empty());
     }
 
     /// Reference state machine for [`Expression`]s.
@@ -1171,10 +1436,17 @@ mod test {
         type Reference = ExpressionReference;
 
         fn init_test(
-            _ref_state: &<Self::Reference as ReferenceStateMachine>::State,
+            ref_state: &<Self::Reference as ReferenceStateMachine>::State,
         ) -> Self::SystemUnderTest {
-            //TODO: randomly initialize state in the reference and replicate
-            //      it over here.
+            /*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())
         }
 
@@ -1454,7 +1726,14 @@ mod test {
                 }
             }
 
-            //TODO: the graph must never contain a cycle.
+            //NOTE: ensure string conversion doesn't panic.
+            let _ = expr.to_string();
+
+            if let Some(root) = expr.root {
+                permutation_vector_of(Global, root, expr.inner.as_slice())
+                    .expect("expression must not contain a cycle");
+            }
+
             //TODO: validate the layout of the entire expression against the
             //      reference.
         }
@@ -1475,6 +1754,18 @@ mod test {
         })]
 
         #[test]
-        fn matches_state_machine(sequential 1..1_000 => ExpressionWrapper);
+        fn matches_state_machine(sequential 1..=250 => ExpressionWrapper);
+    }
+}
+
+#[cfg(all(kani, feature = "core-error"))]
+mod verification {
+    use super::*;
+
+    use generativity::make_guard;
+
+    #[kani::proof]
+    fn simple() {
+        //TODO: add more of a proof here
     }
 }
diff --git a/crates/core/src/hive/group.rs b/crates/core/src/hive/group.rs
deleted file mode 100644
index 9217897..0000000
--- a/crates/core/src/hive/group.rs
+++ /dev/null
@@ -1,122 +0,0 @@
-//! An implementation of the individual memory blocks that make up a hive.
-
-use core::{
-    mem::{self, ManuallyDrop},
-    ptr::NonNull,
-};
-
-use crate::hive::skipfield;
-
-/// A type that may be either part of the free list or an element.
-pub union Slot<T, Sk>
-where
-    Sk: skipfield::SkipfieldType,
-{
-    /// An element of the [`Group`].
-    element: ManuallyDrop<T>,
-
-    /// A free list index.
-    free_list: FreeList<Sk>,
-}
-
-/// The contents of a free list index.
-///
-/// This uses the `packed` C representation to avoid any excess space. This is
-/// not a problem in the general case as our type will only ever be `u16` or
-/// `u8` unless an end-user overrides the skipfield type with a custom
-/// implementation.
-#[repr(C, packed)]
-#[derive(Copy, Clone)]
-#[cfg_attr(feature = "core-fmt", derive(Debug))]
-pub struct FreeList<Sk>
-where
-    Sk: skipfield::SkipfieldType,
-{
-    /// Index of the previous element in the free list.
-    pub previous: Sk,
-
-    /// Index of the next element in the free list.
-    pub next: Sk,
-}
-
-/// A doubly-linked `Group` of `T` with a skipfield type of `Sk`.
-#[cfg_attr(feature = "core-fmt", derive(Debug))]
-pub struct Group<T, Sk>
-where
-    Sk: skipfield::SkipfieldType,
-{
-    /// Pointer to the start of the skipfield.
-    pub skipfield: Option<NonNull<Sk>>,
-
-    /// Pointer to the next [`Group`].
-    pub next: Option<NonNull<Group<T, Sk>>>,
-
-    /// Pointer to element storage.
-    pub elements: Option<NonNull<Slot<T, Sk>>>,
-
-    /// Pointer to the previous [`Group`].
-    pub previous: Option<NonNull<Group<T, Sk>>>,
-
-    /// Index of the last erased element in the group.
-    ///
-    /// The last erased element contains the index of the next, and so on. If
-    /// this is equal to the maximum value of the underlying integer type,
-    /// then the free list is considered to be empty.
-    pub free_list_head: Sk,
-
-    /// Total number of elements this [`Group`] can hold.
-    pub capacity: Sk,
-
-    /// Number of elements stored in this [`Group`].
-    pub size: Sk,
-
-    /// Pointer to the next [`Group`] with erased elements.
-    pub next_with_erasures: Option<NonNull<Group<T, Sk>>>,
-
-    /// Pointer to the previous [`Group`] with erased elements.
-    pub previous_with_erasures: Option<NonNull<Group<T, Sk>>>,
-
-    /// Number assigned to this group.
-    pub number: usize,
-}
-
-impl<T, Sk> Group<T, Sk>
-where
-    Sk: skipfield::SkipfieldType,
-{
-    /// Size of each individual element within a [`Group`]
-    pub const ELEMENT_ALLOCATION_SIZE: usize =
-        compute_element_allocation_size::<T, Sk>();
-}
-
-/// Helper function which computes the allocation size of elements
-const fn compute_element_allocation_size<T, Sk>() -> usize {
-    let t_align = mem::align_of::<T>();
-    let t_size = mem::size_of::<T>();
-    let sk2_size = mem::size_of::<Sk>() * 2;
-    if t_align > t_size {
-        if sk2_size > t_align {
-            sk2_size
-        } else {
-            t_align
-        }
-    } else if sk2_size > t_size {
-        sk2_size
-    } else {
-        t_size
-    }
-}
-
-#[cfg(all(test, feature = "core-error"))]
-mod test {
-    use super::*;
-
-    #[test]
-    fn validate_element_allocation_size() {
-        assert_eq!(
-            Group::<u32, u8>::ELEMENT_ALLOCATION_SIZE,
-            4,
-            "element allocation size with T = u32, Sk = u8 is 4"
-        );
-    }
-}
diff --git a/crates/core/src/hive/mod.rs b/crates/core/src/hive/mod.rs
deleted file mode 100644
index 3f83099..0000000
--- a/crates/core/src/hive/mod.rs
+++ /dev/null
@@ -1,336 +0,0 @@
-//! An implementation of a bucket array type following the approach used in
-//! the [C++26 `hive`](https://eel.is/c++draft/hive) structure.
-
-//TODO: traits to implement for `Hive`:
-//      - Ord - Eq - Clone - Debug - Deref<Target=[T]> (?) - AsRef - Borrow
-//      - AsMut - Extend - From [array, slice, vec, etc...] - FromIterator
-//      - Hash - IntoIterator - Index - IndexMut
-//      - PartialEq [array, slice, vec, etc...] - PartialOrd - Write
-//TODO: define zero-sized-type handling in `Hive`
-//TODO: define situations where we panic
-//TODO: consider factoring out code that does not care about the type
-//      parameters into a separate struct to reduce the amount of code
-//      generated, akin to what the standard library does with `RawVec` and
-//      `RawVecInner`
-//TODO: try_reserve_exact, reserve_exact
-
-use alloc::alloc::{Allocator, Global, Layout};
-use core::{cmp, mem, ptr::NonNull};
-
-#[cfg(feature = "core-fmt")]
-use core::fmt;
-
-#[cfg(feature = "core-error")]
-use core::error;
-
-pub mod group;
-pub mod skipfield;
-
-/// An implementation of a bucket array using a skipfield.
-#[cfg_attr(feature = "core-fmt", derive(Debug))]
-pub struct Hive<T, Sk = u16, A = Global>
-where
-    Sk: skipfield::SkipfieldType,
-    A: Allocator,
-{
-    /// Head of the doubly linked list of groups with erased elements
-    head_with_erasures: Option<NonNull<group::Group<T, Sk>>>,
-
-    /// Head of the singly linked list of unused groups
-    unused_head: Option<NonNull<group::Group<T, Sk>>>,
-
-    /// Number of occupied element spaces
-    size: usize,
-
-    /// Total number of element spaces available
-    capacity: usize,
-
-    /// Minimum capacity of new [`Group`]s
-    min_block_capacity: Sk,
-
-    /// Maximum capacity of new [`Group`]s
-    max_block_capacity: Sk,
-
-    /// The allocator used by this [`Hive`].
-    alloc: A,
-}
-
-impl<T, Sk> Hive<T, Sk, Global>
-where
-    Sk: skipfield::SkipfieldType,
-{
-    /// Constructs a new, empty `Hive<T, Sk>`.
-    ///
-    /// No allocations are performed until elements are inserted.
-    pub fn new() -> Self {
-        Self::new_in(Global)
-    }
-
-    /// Constructs a new, empty `Hive<T, Sk>` with at least the specified
-    /// capacity.
-    ///
-    /// The hive will be able to hold at least `capacity` elements without
-    /// reallocating. This method is allowed to allocate for more elements
-    /// than `capacity`. If `capacity` is zero, the hive will not
-    /// allocate.
-    ///
-    /// # Panics
-    ///
-    /// Panics if the allocator reports allocation failure or if the capacity
-    /// exceeds `isize::MAX` bytes.
-    #[cfg(feature = "core-fmt")]
-    pub fn with_capacity(capacity: usize) -> Self {
-        Self::with_capacity_in(capacity, Global)
-    }
-
-    /// Constructs a new, empty `Hive<T, Sk>` with at least the specified
-    /// capacity.
-    ///
-    /// The hive will be able to hold at least `capacity` elements without
-    /// reallocating. This method is allowed to allocate for more elements
-    /// than `capacity`. If `capacity` is zero, the hive will not
-    /// allocate.
-    ///
-    /// # Errors
-    ///
-    /// Returns an error if the allocator reports allocation failure or if the
-    /// capacity exceeds `isize::MAX` bytes.
-    pub fn try_with_capacity(capacity: usize) -> Result<Self, Error> {
-        Self::try_with_capacity_in(capacity, Global)
-    }
-}
-
-impl<T, Sk, A> Hive<T, Sk, A>
-where
-    Sk: skipfield::SkipfieldType,
-    A: Allocator,
-{
-    /// Function returning the default bounds for individual [`Group`]
-    /// capacity
-    ///
-    /// These are borrowed from [here], as those bounds were determined
-    /// according to benchmarking results. However, they have not been
-    /// replicated against this implementation of the concept.
-    ///
-    /// [here]: https://github.com/mattreecebentley/plf_hive/blob/main/plf_hive.h#L293-L307
-    fn default_group_capacity_bounds() -> (Sk, Sk)
-    where
-        Sk: skipfield::SkipfieldType,
-    {
-        let max_capacity = cmp::min(
-            cmp::min(Sk::MAXIMUM, Sk::from_usize(8192)),
-            Sk::from_isize(isize::MAX),
-        );
-        let adaptive_size = (mem::size_of::<Self>()
-            + mem::size_of::<group::Group<T, Sk>>() * 2)
-            / group::Group::<T, Sk>::ELEMENT_ALLOCATION_SIZE;
-        let min_capacity = cmp::max(
-            Sk::from_usize(8usize),
-            cmp::min(Sk::from_usize(adaptive_size), max_capacity),
-        );
-
-        //NOTE: anything that calls `panic` indirectly or does anything that
-        // touches standard output      requires core::fmt :skull:
-        #[cfg(feature = "core-fmt")]
-        debug_assert!(
-            max_capacity >= min_capacity,
-            "maximum capacity bound is greater than or equal to the minimum capacity bound"
-        );
-
-        (min_capacity, max_capacity)
-    }
-
-    /// Constructs a new, empty `Hive<T, Sk, A>`.
-    ///
-    /// No allocations are performed until elements are inserted.
-    pub fn new_in(alloc: A) -> Self {
-        let (min_block_capacity, max_block_capacity) =
-            Self::default_group_capacity_bounds();
-        Self {
-            head_with_erasures: None,
-            unused_head: None,
-            size: 0,
-            capacity: 0,
-            min_block_capacity,
-            max_block_capacity,
-            alloc,
-        }
-    }
-
-    /// Constructs a new, empty `Hive<T, Sk, A>` with at least the specified
-    /// capacity.
-    ///
-    /// The hive will be able to hold at least `capacity` elements without
-    /// reallocating. This method is allowed to allocate for more elements
-    /// than `capacity`. If `capacity` is zero, the hive will not
-    /// allocate.
-    ///
-    /// # Panics
-    ///
-    /// Panics if the allocator reports allocation failure or if the capacity
-    /// exceeds `isize::MAX` bytes.
-    #[cfg(feature = "core-fmt")]
-    pub fn with_capacity_in(capacity: usize, alloc: A) -> Self {
-        //PANIC: this is acceptable as the panic is mentioned above and it is
-        //       used to assert an invariant.
-        #[allow(clippy::expect_used)]
-        Self::try_with_capacity_in(capacity, alloc)
-            .expect("allocation should not fail")
-    }
-
-    /// Constructs a new, empty `Hive<T, Sk, A>` with at least the specified
-    /// capacity.
-    ///
-    /// The hive will be able to hold at least `capacity` elements without
-    /// reallocating. This method is allowed to allocate for more elements
-    /// than `capacity`. If `capacity` is zero, the hive will not
-    /// allocate.
-    ///
-    /// # Errors
-    ///
-    /// Returns an error if the allocator reports allocation failure or if the
-    /// capacity exceeds `isize::MAX` bytes.
-    pub fn try_with_capacity_in(
-        capacity: usize,
-        alloc: A,
-    ) -> Result<Self, Error> {
-        let mut hive = Self::new_in(alloc);
-        hive.try_reserve(capacity)?;
-        Ok(hive)
-    }
-
-    /// Reserves capacity for at least `additional` more elements to be
-    /// inserted in the given `Hive<T, Sk, A>`.
-    ///
-    /// The collection may reserve more space to avoid future allocations.
-    /// After calling `reserve`, the capacity will be greater than or equal to
-    /// `self.len() + additional`. Does nothing if the capacity is already
-    /// sufficient.
-    ///
-    /// # Panics
-    ///
-    /// Panics if the allocator reports allocation failure or if the new
-    /// capacity exceeds `isize::MAX` bytes.
-    #[cfg(feature = "core-fmt")]
-    pub fn reserve(&mut self, additional: usize) {
-        todo!()
-    }
-
-    /// Reserves capacity for at least `additional` more elements to be
-    /// inserted in the given `Hive<T, Sk, A>`.
-    ///
-    /// The collection may reserve more space to avoid future allocations.
-    /// After calling `reserve`, the capacity will be greater than or equal to
-    /// `self.len() + additional`. Does nothing if the capacity is already
-    /// sufficient.
-    ///
-    /// # Errors
-    ///
-    /// Returns an error if the allocator reports allocation failure or if the
-    /// new capacity exceeds `isize::MAX` bytes.
-    pub fn try_reserve(&mut self, additional: usize) -> Result<(), Error> {
-        todo!()
-    }
-
-    /// Checks if the container needs to grow to accommodate `additional` more
-    /// elements
-    #[inline]
-    fn needs_to_grow(&self, additional: usize) -> bool {
-        additional > self.capacity.wrapping_sub(self.size)
-    }
-
-    /// Grow the `Hive<T, Sk, A>` by the given amount, leaving room for more
-    /// elements than necessary.
-    ///
-    /// # Errors
-    ///
-    /// Returns an error if the allocator reports allocation failure or if the
-    /// new capacity exceeds `isize::MAX` bytes.
-    fn grow_amortized(&mut self, additional: usize) -> Result<(), Error> {
-        #[cfg(feature = "core-fmt")]
-        debug_assert!(
-            additional > 0,
-            "at least space enough for one element will be added"
-        );
-
-        if mem::size_of::<T>() == 0 {
-            //NOTE: akin to raw_vec in alloc, if we get here with a zero
-            //      sized type, since the capacity is definitionally full when
-            //      it is holding one, the hive would necessarily
-            //      be overfull
-            return Err(Error::CapacityOverflow);
-        }
-
-        todo!()
-    }
-}
-
-impl<T, Sk> Default for Hive<T, Sk, Global>
-where
-    Sk: skipfield::SkipfieldType,
-{
-    fn default() -> Self {
-        Self::new()
-    }
-}
-
-/// Representation of an error that occurred within [`Hive`].
-#[non_exhaustive]
-#[derive(Eq, PartialEq)]
-#[cfg_attr(feature = "core-fmt", derive(Debug))]
-pub enum Error {
-    /// Allocation size exceeded `isize::MAX`.
-    CapacityOverflow,
-
-    /// Unspecified allocation error.
-    ///
-    /// The layout used during allocation is provided for troubleshooting
-    /// where that is possible. Ideally, future revisions of the
-    /// `allocator_api` feature will provide more information in `AllocError`
-    /// but for now this is all we can do.
-    #[non_exhaustive]
-    AllocError {
-        /// Layout of the failed allocation.
-        layout: Layout,
-    },
-}
-
-#[cfg(feature = "core-fmt")]
-impl fmt::Display for Error {
-    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        f.write_str("memory allocation failed")?;
-        let reason = match self {
-            Error::CapacityOverflow => {
-                " because the computed capacity exceeded the hive's maximum"
-            }
-            Error::AllocError { .. } => {
-                " because the memory allocator returned an error"
-            }
-        };
-        f.write_str(reason)
-    }
-}
-
-#[cfg(feature = "core-error")]
-impl error::Error for Error {}
-
-/// Guard function ensuring that we don't overflow `isize::MAX`.
-///
-/// The Rust standard library has a similar function, found [here]. However,
-/// that implementation of it ignores the check on platforms with a `usize`
-/// wider than 64 bits. This is probably fine, as no platform Rust supports
-/// has a virtual address space larger than 8 EiB, but out of caution, we
-/// always make the check here.
-///
-/// [here]: https://github.com/rust-lang/rust/blob/a27f3e3fd1e4d16160f8885b6b06665b5319f56c/library/alloc/src/raw_vec/mod.rs#L802-L817
-#[inline]
-fn alloc_guard(alloc_size: usize) -> Result<(), Error> {
-    //TODO: consider predicating this check over `usize::BITS < 64` as the
-    //      rust std does. only do this if it has a measurable performance
-    //      impact
-    if alloc_size > isize::MAX as usize {
-        Err(Error::CapacityOverflow)
-    } else {
-        Ok(())
-    }
-}
diff --git a/crates/core/src/hive/skipfield.rs b/crates/core/src/hive/skipfield.rs
deleted file mode 100644
index 16a3dcb..0000000
--- a/crates/core/src/hive/skipfield.rs
+++ /dev/null
@@ -1,67 +0,0 @@
-//! An implementation of a trait describing valid skipfield integer types.
-//!
-//! Only `u16`s and `u8`s are supported by default. However, other integral
-//! types may be used by implementing this trait on them; the trait is not
-//! sealed.
-
-use core::{
-    cmp,
-    ops::{Add, AddAssign, Sub, SubAssign},
-};
-
-/// Trait describing integral types in a generic way suitable for use as the
-/// element type of a skipfield.
-pub trait SkipfieldType:
-    Add + AddAssign + Sub + SubAssign + Ord + PartialOrd + Copy + Sized
-{
-    /// The maximum attainable value of this type.
-    const MAXIMUM: Self;
-
-    /// The zero element of this type.
-    const ZERO: Self;
-
-    /// The one element of this type.
-    const ONE: Self;
-
-    /// Conversion method from `usize` using `as` or an equivalent
-    ///
-    /// Caps the value of the input by the maximum of `Self`.
-    fn from_usize(u: usize) -> Self;
-
-    /// Conversion method from `isize` using `as` or an equivalent
-    ///
-    /// Caps the value of the input by the maximum of `Self`.
-    fn from_isize(i: isize) -> Self;
-}
-
-impl SkipfieldType for u16 {
-    const MAXIMUM: Self = u16::MAX;
-    const ZERO: Self = 0;
-    const ONE: Self = 1;
-
-    #[inline(always)]
-    fn from_usize(u: usize) -> Self {
-        cmp::min(u, Self::MAXIMUM as usize) as u16
-    }
-
-    #[inline(always)]
-    fn from_isize(i: isize) -> Self {
-        cmp::min(i, Self::MAXIMUM as isize) as u16
-    }
-}
-
-impl SkipfieldType for u8 {
-    const MAXIMUM: Self = u8::MAX;
-    const ZERO: Self = 0;
-    const ONE: Self = 1;
-
-    #[inline(always)]
-    fn from_usize(u: usize) -> Self {
-        cmp::min(u, Self::MAXIMUM as usize) as u8
-    }
-
-    #[inline(always)]
-    fn from_isize(i: isize) -> Self {
-        cmp::min(i, Self::MAXIMUM as isize) as u8
-    }
-}
diff --git a/crates/core/src/id.rs b/crates/core/src/id.rs
new file mode 100644
index 0000000..a216dd8
--- /dev/null
+++ b/crates/core/src/id.rs
@@ -0,0 +1,110 @@
+//! Identifier newtype primitives and helpers for defining and working with
+//! them.
+
+use core::hash::Hash;
+
+/// 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
+{
+    /// The backing integer type for this identifier.
+    type Integer: Integer;
+
+    /// Instantiate a new identifier from its underlying representation.
+    #[must_use]
+    fn new(v: Self::Integer) -> Self;
+}
+
+//NOTE: we don't use the same [`Integer`] trait in `numerics` here as there
+//      is specific behavior desired in an "integer backing an id"---such as
+//      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
+{
+    /// Zero value of the integer type.
+    const ZERO: Self;
+
+    /// Convert this integer into a `usize`.
+    fn into_usize(self) -> usize;
+
+    /// Construct an integer from a `usize`.
+    ///
+    /// Returns `None` if no corresponding integer exists.
+    fn from_usize(v: usize) -> Option<Self>;
+
+    /// Returns the successor value of this integer.
+    ///
+    /// If this would have overflowed, `None` is returned.
+    fn increment(self) -> Option<Self>;
+
+    //// Returns the predecessor value of this integer.
+    ///
+    /// If this would have overflowed, `None` is returned.
+    fn decrement(self) -> Option<Self>;
+}
+
+macro_rules! integer_impl {
+    ($t:ty) => {
+        impl sealed::Sealed for $t {}
+
+        impl 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
+            }
+
+            #[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) -> Option<Self> {
+                self.checked_add(1)
+            }
+
+            fn decrement(self) -> Option<Self> {
+                self.checked_sub(1)
+            }
+        }
+    };
+}
+
+integer_impl!(usize);
+
+#[cfg(target_pointer_width = "64")]
+integer_impl!(u64);
+
+#[cfg(any(target_pointer_width = "64", target_pointer_width = "32"))]
+integer_impl!(u32);
+
+integer_impl!(u16);
+integer_impl!(u8);
+
+mod sealed {
+    pub trait Sealed {}
+}
diff --git a/crates/core/src/lib.rs b/crates/core/src/lib.rs
index 54c04c5..24b7ac3 100644
--- a/crates/core/src/lib.rs
+++ b/crates/core/src/lib.rs
@@ -1,67 +1,69 @@
 #![cfg_attr(not(test), no_std)]
-#![warn(
-    clippy::cargo_common_metadata,
-    clippy::dbg_macro,
-    clippy::needless_pass_by_ref_mut,
-    clippy::needless_pass_by_value,
-    clippy::print_stderr,
-    clippy::print_stdout,
-    clippy::todo,
-    clippy::unimplemented
-)]
-#![deny(
-    clippy::await_holding_lock,
-    rustdoc::broken_intra_doc_links,
-    clippy::cast_lossless,
-    clippy::clone_on_ref_ptr,
-    clippy::default_trait_access,
-    clippy::doc_markdown,
-    clippy::empty_enum,
-    clippy::enum_glob_use,
-    clippy::exit,
-    clippy::expect_used,
-    clippy::explicit_deref_methods,
-    clippy::explicit_into_iter_loop,
-    clippy::explicit_iter_loop,
-    clippy::fallible_impl_from,
-    clippy::filetype_is_file,
-    clippy::float_cmp,
-    clippy::float_cmp_const,
-    clippy::imprecise_flops,
-    clippy::inefficient_to_string,
-    clippy::large_digit_groups,
-    clippy::large_stack_arrays,
-    clippy::manual_filter_map,
-    clippy::match_like_matches_macro,
-    missing_docs,
-    clippy::missing_errors_doc,
-    clippy::missing_safety_doc,
-    clippy::mut_mut,
-    clippy::option_option,
-    clippy::panic,
-    clippy::panic_in_result_fn,
-    clippy::redundant_clone,
-    clippy::redundant_else,
-    clippy::rest_pat_in_fully_bound_structs,
-    clippy::single_match_else,
-    clippy::implicit_clone,
-    trivial_casts,
-    trivial_numeric_casts,
-    clippy::undocumented_unsafe_blocks,
-    clippy::unused_self,
-    clippy::unwrap_used,
-    clippy::wildcard_dependencies,
-    clippy::wildcard_imports
-)]
 #![feature(allocator_api)]
 #![feature(vec_push_within_capacity)]
 #![feature(trusted_len)]
 #![feature(assert_matches)]
+#![feature(stmt_expr_attributes)]
 
-//! A highly portable computer algebra system library implemented in Rust
+//! A highly portable computer algebra system library implemented in Rust.
 
 extern crate alloc;
 
+pub mod egraph;
 pub mod expressions;
-pub mod hive;
+pub mod id;
 pub mod numerics;
+pub mod utilities;
+
+/// Asserts a condition at compile time.
+#[macro_export]
+macro_rules! static_assert {
+    ($cond:expr $(,)?) => {
+        const _: () = {
+            if !$cond {
+                panic!(concat!(
+                    "static assertion failed: ",
+                    stringify!($cond),
+                ));
+            }
+        };
+    };
+    ($cond:expr, $msg:literal $(,)?) => {
+        const _: () = {
+            if !$cond {
+                panic!($msg);
+            }
+        };
+    };
+}
+
+/// Asserts equality at compile time.
+#[macro_export]
+macro_rules! static_assert_eq {
+    ($a:expr, $b:expr $(,)?) => {
+        const _: () = {
+            if $a != $b {
+                panic!(concat!(
+                    "static assertion failed: ",
+                    stringify!($a),
+                    " == ",
+                    stringify!($b),
+                ));
+            }
+        };
+    };
+    ($a:expr, $b:expr, $msg:literal $(,)?) => {
+        const _: () = {
+            if $a != $b {
+                panic!(concat!(
+                    "static assertion failed: ",
+                    stringify!($a),
+                    " == ",
+                    stringify!($b),
+                    ": ",
+                    $msg,
+                ));
+            }
+        };
+    };
+}
diff --git a/crates/core/src/utilities.rs b/crates/core/src/utilities.rs
new file mode 100644
index 0000000..583ad7c
--- /dev/null
+++ b/crates/core/src/utilities.rs
@@ -0,0 +1,190 @@
+//! Utilities used throughout the library.
+
+use alloc::{alloc::Allocator, collections::TryReserveError, vec::Vec};
+
+#[cfg(feature = "core-fmt")]
+use core::fmt;
+
+#[cfg(feature = "core-error")]
+use core::error;
+
+/// Extension trait for handling OOM conditions better with a [`Vec`].
+pub trait VecMemoryExt<T> {
+    /// Appends an element to the back of the vector.
+    ///
+    /// # Errors
+    ///
+    /// This method errors if the capacity overflows or if the allocator
+    /// reports a failure.
+    fn try_push(&mut self, value: T) -> Result<(), TryReserveError>;
+}
+
+impl<T, A> VecMemoryExt<T> for Vec<T, A>
+where
+    A: Allocator,
+{
+    fn try_push(&mut self, value: T) -> Result<(), TryReserveError> {
+        self.try_reserve(1)?;
+
+        //SAFETY: we just reserved space for this element
+        unsafe { self.push_within_capacity(value).unwrap_unchecked() };
+
+        Ok(())
+    }
+}
+
+/// Extension trait for wrapping arithmetic.
+pub trait WrappingArithmeticExt {
+    /// Wrapping integer increment.
+    fn wrapping_increment(self) -> Self;
+
+    /// Mutable wrapping integer increment.
+    fn wrapping_increment_mut(&mut self);
+
+    /// Wrapping integer decrement.
+    fn wrapping_decrement(self) -> Self;
+
+    /// Mutable wrapping integer decrement.
+    fn wrapping_decrement_mut(&mut self);
+}
+
+macro_rules! wrapping_arithmetic_ext_impl {
+    ($t:ty) => {
+        impl WrappingArithmeticExt for $t {
+            fn wrapping_increment(self) -> Self {
+                self.wrapping_add(1)
+            }
+
+            fn wrapping_increment_mut(&mut self) {
+                *self = self.wrapping_add(1);
+            }
+
+            fn wrapping_decrement(self) -> Self {
+                self.wrapping_sub(1)
+            }
+
+            fn wrapping_decrement_mut(&mut self) {
+                *self = self.wrapping_sub(1);
+            }
+        }
+    };
+}
+
+wrapping_arithmetic_ext_impl!(usize);
+wrapping_arithmetic_ext_impl!(u64);
+wrapping_arithmetic_ext_impl!(u32);
+wrapping_arithmetic_ext_impl!(u16);
+wrapping_arithmetic_ext_impl!(u8);
+
+wrapping_arithmetic_ext_impl!(isize);
+wrapping_arithmetic_ext_impl!(i64);
+wrapping_arithmetic_ext_impl!(i32);
+wrapping_arithmetic_ext_impl!(i16);
+wrapping_arithmetic_ext_impl!(i8);
+
+/// Extension trait for checked arithmetic that turns the output into a
+/// [`Result`].
+pub trait CheckedArithmeticExt: Sized {
+    /// Checked integer addition.
+    ///
+    /// # Errors
+    ///
+    /// Returns an error if the result would have overflowed.
+    fn errored_add(self, rhs: Self) -> Result<Self, IntegerOverflowError>;
+
+    /// Checked integer division.
+    ///
+    /// # Errors
+    ///
+    /// Returns an error if the result would have overflowed.
+    fn errored_div(self, rhs: Self) -> Result<Self, IntegerOverflowError>;
+
+    /// Checked integer multiplication.
+    ///
+    /// # Errors
+    ///
+    /// Returns an error if the result would have overflowed.
+    fn errored_mul(self, rhs: Self) -> Result<Self, IntegerOverflowError>;
+
+    /// Checked integer remainder.
+    ///
+    /// # Errors
+    ///
+    /// Returns an error if the result would have overflowed.
+    fn errored_rem(self, rhs: Self) -> Result<Self, IntegerOverflowError>;
+
+    /// Checked integer subtraction.
+    ///
+    /// # Errors
+    ///
+    /// Returns an error if the result would have overflowed.
+    fn errored_sub(self, rhs: Self) -> Result<Self, IntegerOverflowError>;
+}
+
+macro_rules! checked_arithmetic_ext_impl {
+    ($t:ty) => {
+        impl CheckedArithmeticExt for $t {
+            fn errored_add(
+                self,
+                rhs: Self,
+            ) -> Result<Self, IntegerOverflowError> {
+                self.checked_add(rhs).ok_or(IntegerOverflowError)
+            }
+
+            fn errored_div(
+                self,
+                rhs: Self,
+            ) -> Result<Self, IntegerOverflowError> {
+                self.checked_div(rhs).ok_or(IntegerOverflowError)
+            }
+
+            fn errored_mul(
+                self,
+                rhs: Self,
+            ) -> Result<Self, IntegerOverflowError> {
+                self.checked_mul(rhs).ok_or(IntegerOverflowError)
+            }
+
+            fn errored_rem(
+                self,
+                rhs: Self,
+            ) -> Result<Self, IntegerOverflowError> {
+                self.checked_rem(rhs).ok_or(IntegerOverflowError)
+            }
+
+            fn errored_sub(
+                self,
+                rhs: Self,
+            ) -> Result<Self, IntegerOverflowError> {
+                self.checked_sub(rhs).ok_or(IntegerOverflowError)
+            }
+        }
+    };
+}
+
+checked_arithmetic_ext_impl!(usize);
+checked_arithmetic_ext_impl!(u64);
+checked_arithmetic_ext_impl!(u32);
+checked_arithmetic_ext_impl!(u16);
+checked_arithmetic_ext_impl!(u8);
+
+checked_arithmetic_ext_impl!(isize);
+checked_arithmetic_ext_impl!(i64);
+checked_arithmetic_ext_impl!(i32);
+checked_arithmetic_ext_impl!(i16);
+checked_arithmetic_ext_impl!(i8);
+
+/// Representation of an integer overflow error.
+#[derive(PartialEq, Eq)]
+#[cfg_attr(feature = "core-fmt", derive(Debug))]
+pub struct IntegerOverflowError;
+
+#[cfg(feature = "core-fmt")]
+impl fmt::Display for IntegerOverflowError {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        f.write_str("integer overflow")
+    }
+}
+
+#[cfg(feature = "core-error")]
+impl error::Error for IntegerOverflowError {}