node topological sorting

Change-Id: I6a6a6964255d818be1bf9a8f4ec9e317befa19c5

1 files changed, 110 insertions, 0 deletions

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 {}
+}