initial commit

Change-Id: I6a6a69640e8a301a692a5455d1261816280d9cde

14 files changed, 634 insertions, 0 deletions

diff --git a/.cargo/config.toml b/.cargo/config.toml
new file mode 100644
index 0000000..320f0bf
--- /dev/null
+++ b/.cargo/config.toml
@@ -0,0 +1,6 @@
+[build]
+rustflags = "-C target-cpu=native"
+
+[target.x86_64-unknown-linux-gnu]
+linker = "clang"
+rustflags = ["-Clink-arg=-fuse-ld=lld", "-Clink-arg=-Wl,--no-rosegment"]
diff --git a/.editorconfig b/.editorconfig
new file mode 100644
index 0000000..42324f6
--- /dev/null
+++ b/.editorconfig
@@ -0,0 +1,15 @@
+root = true
+
+[*]
+charset = utf-8
+end_of_line = lf
+insert_final_newline = true
+trim_trailing_whitespace = true
+
+[*.{toml,md}]
+indent_style = space
+indent_size = 2
+
+[*.rs]
+indent_style = space
+indent_size = 4
diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..ea8c4bf
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1 @@
+/target
diff --git a/Cargo.lock b/Cargo.lock
new file mode 100644
index 0000000..4a34977
--- /dev/null
+++ b/Cargo.lock
@@ -0,0 +1,7 @@
+# This file is automatically @generated by Cargo.
+# It is not intended for manual editing.
+version = 4
+
+[[package]]
+name = "azimuth-core"
+version = "0.0.0"
diff --git a/Cargo.toml b/Cargo.toml
new file mode 100644
index 0000000..8f0e019
--- /dev/null
+++ b/Cargo.toml
@@ -0,0 +1,18 @@
+[workspace]
+members = [
+  "crates/*"
+]
+resolver = "3"
+
+[profile.release]
+opt-level = 3
+codegen-units = 1
+debug = false
+strip = "symbols"
+panic = "abort"
+lto = "thin"
+
+[profile.release-profile]
+inherits = "release"
+debug = true
+strip = false
diff --git a/crates/core/Cargo.toml b/crates/core/Cargo.toml
new file mode 100644
index 0000000..baf4b00
--- /dev/null
+++ b/crates/core/Cargo.toml
@@ -0,0 +1,22 @@
+[package]
+name = "azimuth-core"
+description = "core implementation of the azimuth computer algebra system"
+categories = ["Mathematics", "No standard library", "Algorithms"]
+keywords = ["no_std", "library", "mathematics", "cross-platform"]
+version = "0.0.0"
+authors = ["superwhiskers <[email protected]>"]
+repository = "https://github.com/superwhiskers/azimuth"
+readme = "readme.md"
+edition = "2024"
+license = "AGPL-3.0"
+
+[features]
+# Enable the use of core::fmt in azimuth-core.
+#
+# Gated behind a feature to reduce code bloat where it is undesirable.
+core-fmt = []
+
+# Enable the use of core::error in azimuth-core.
+#
+# Gated behind a feature due to its dependency upon core::fmt.
+core-error = ["core-fmt"]
diff --git a/crates/core/src/hive/group.rs b/crates/core/src/hive/group.rs
new file mode 100644
index 0000000..32d070e
--- /dev/null
+++ b/crates/core/src/hive/group.rs
@@ -0,0 +1,104 @@
+//! 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)]
+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`.
+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 in the [`Hive`].
+    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 }
+    }
+}
diff --git a/crates/core/src/hive/mod.rs b/crates/core/src/hive/mod.rs
new file mode 100644
index 0000000..17568e3
--- /dev/null
+++ b/crates/core/src/hive/mod.rs
@@ -0,0 +1,256 @@
+//! 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`
+
+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.
+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),
+        );
+
+        (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 {
+        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> {
+        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,
+
+    /// An unspecified allocation error occurred.
+    ///
+    /// 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, fmt: &mut fmt::Formatter<'_>) -> Result<(), fmt::Error> {
+        fmt.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"
+            }
+        };
+        fmt.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
new file mode 100644
index 0000000..0fb2ab4
--- /dev/null
+++ b/crates/core/src/hive/skipfield.rs
@@ -0,0 +1,60 @@
+//! 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::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
+    fn from_usize(u: usize) -> Self;
+
+    /// Conversion method from `isize` using `as` or an equivalent
+    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 {
+        u as u16
+    }
+
+    #[inline(always)]
+    fn from_isize(i: isize) -> Self {
+        i 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 {
+        u as u8
+    }
+
+    #[inline(always)]
+    fn from_isize(i: isize) -> Self {
+        i as u8
+    }
+}
diff --git a/crates/core/src/lib.rs b/crates/core/src/lib.rs
new file mode 100644
index 0000000..330ad58
--- /dev/null
+++ b/crates/core/src/lib.rs
@@ -0,0 +1,62 @@
+#![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)]
+
+//! A highly portable computer algebra system library implemented in Rust
+
+extern crate alloc;
+
+pub mod hive;
diff --git a/deny.toml b/deny.toml
new file mode 100644
index 0000000..f52b32a
--- /dev/null
+++ b/deny.toml
@@ -0,0 +1,31 @@
+[licenses]
+allow = ["AGPL-3.0"]
+
+[bans]
+multiple-versions = "deny"
+wildcards = "deny"
+allow = []
+
+[bans.workspace-dependencies]
+duplicates = "deny"
+include-path-dependencies = true
+unused = "deny"
+
+[bans.build]
+allow-build-scripts = []
+executables = "deny"
+interpreted = "deny"
+enable-builtin-globs = true
+include-dependencies = true
+include-archives = true
+
+[sources]
+unknown-registry = "deny"
+unknown-git = "deny"
+allow-registry = ["https://github.com/rust-lang/crates.io-index"]
+allow-git = []
+
+[sources.allow-org]
+github = []
+gitlab = []
+bitbucket = []
diff --git a/readme.md b/readme.md
new file mode 100644
index 0000000..f0a4ff6
--- /dev/null
+++ b/readme.md
@@ -0,0 +1,49 @@
+# azimuth
+
+a new computer algebra system
+
+## goals
+
+our first goal for azimuth is that it should be able to compute
+the antiderivative of an arbitrary function at least as fast as
+[rubi](https://rulebasedintegration.org/).
+
+ideally, we should be able to do this faster and maybe (?) produce better
+antiderivatives because:
+
+- we are writing our own software (not just using mathematica)
+- we are using a different technique that we hope produces better
+  antiderivatives (e-graphs)
+  - this will hopefully allow us to aggressively parallelize the process
+    where this provides performance benefits
+
+## technical requirements
+
+these are some rules we've outlined. they aren't intended to be general
+software guidelines, they are strict because we feel they are achievable
+given our scope.
+
+- unnecessary serial computation is a bug
+  - if it can be done in parallel it should be if the overhead does not
+    outweigh the benefit
+- unnecessary memory usage is a bug
+- excessively slow computation is a bug
+  - any instance of a computation slower than any peer is a bug
+- unclear code is a bug
+  - code should be readable by anyone familiar with the language and
+    the domain
+- bad abstractions are a bug
+  - defined as:
+    - having more requirements than necessary to enclose their interface
+    - trying to hide away details that aren't all that well hidden or
+      make sense to hide
+    - not doing only one thing where this is a reasonable constraint
+- unspecified pre/post-conditions or invariants are a bug
+- undocumented code is a bug
+- requiring more than `cargo build` to build in most circumstances is a bug
+- crate dependencies other than `std`/`core`/`alloc` or code vetted in
+  its entirety are a bug
+
+## why
+
+why not?
diff --git a/rust-toolchain b/rust-toolchain
new file mode 100644
index 0000000..bf867e0
--- /dev/null
+++ b/rust-toolchain
@@ -0,0 +1 @@
+nightly
diff --git a/rustfmt.toml b/rustfmt.toml
new file mode 100644
index 0000000..47b52dd
--- /dev/null
+++ b/rustfmt.toml
@@ -0,0 +1,2 @@
+max_width = 78
+wrap_comments = true