diff options
| -rw-r--r-- | Cargo.lock | 164 | ||||
| -rw-r--r-- | Cargo.toml | 72 | ||||
| -rw-r--r-- | crates/core/Cargo.toml | 3 | ||||
| -rw-r--r-- | crates/core/src/egraph/mod.rs | 4 | ||||
| -rw-r--r-- | crates/core/src/egraph/union_find.rs | 6 | ||||
| -rw-r--r-- | crates/core/src/expressions/mod.rs | 429 | ||||
| -rw-r--r-- | crates/core/src/hive/group.rs | 122 | ||||
| -rw-r--r-- | crates/core/src/hive/mod.rs | 336 | ||||
| -rw-r--r-- | crates/core/src/hive/skipfield.rs | 67 | ||||
| -rw-r--r-- | crates/core/src/id.rs | 110 | ||||
| -rw-r--r-- | crates/core/src/lib.rs | 114 | ||||
| -rw-r--r-- | crates/core/src/utilities.rs | 190 |
12 files changed, 848 insertions, 769 deletions
diff --git a/Cargo.lock b/Cargo.lock index 90f9da1..7d6133f 100644 --- a/Cargo.lock +++ b/Cargo.lock @@ -34,21 +34,21 @@ checksum = "5e764a1d40d510daf35e07be9eb06e75770908c27d411ee6c92109c9840eaaf7" [[package]] name = "bitflags" -version = "2.9.4" +version = "2.10.0" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "2261d10cca569e4643e526d8dc2e62e433cc8aba21ab764233731f8d369bf394" +checksum = "812e12b5285cc515a9c72a5c1d3b6d46a19dac5acfef5265968c166106e31dd3" [[package]] name = "cfg-if" -version = "1.0.3" +version = "1.0.4" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "2fd1289c04a9ea8cb22300a459a72a385d7c73d3259e2ed7dcb2af674838cfa9" +checksum = "9330f8b2ff13f34540b44e946ef35111825727b38d33286ef986142615121801" [[package]] name = "errno" -version = "0.3.13" +version = "0.3.14" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "778e2ac28f6c47af28e4907f13ffd1e1ddbd400980a9abd7c8df189bf578a5ad" +checksum = "39cab71617ae0d63f51a36d69f866391735b51691dbda63cf6f96d042b63efeb" dependencies = [ "libc", "windows-sys", @@ -74,33 +74,27 @@ checksum = "5881e4c3c2433fe4905bb19cfd2b5d49d4248274862b68c27c33d9ba4e13f9ec" [[package]] name = "getrandom" -version = "0.3.3" +version = "0.3.4" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "26145e563e54f2cadc477553f1ec5ee650b00862f0a58bcd12cbdc5f0ea2d2f4" +checksum = "899def5c37c4fd7b2664648c28120ecec138e4d395b459e5ca34f9cce2dd77fd" dependencies = [ "cfg-if", "libc", "r-efi", - "wasi", + "wasip2", ] [[package]] -name = "lazy_static" -version = "1.5.0" -source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "bbd2bcb4c963f2ddae06a2efc7e9f3591312473c50c6685e1f298068316e66fe" - -[[package]] name = "libc" -version = "0.2.175" +version = "0.2.178" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "6a82ae493e598baaea5209805c49bbf2ea7de956d50d7da0da1164f9c6d28543" +checksum = "37c93d8daa9d8a012fd8ab92f088405fb202ea0b6ab73ee2482ae66af4f42091" [[package]] name = "linux-raw-sys" -version = "0.9.4" +version = "0.11.0" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "cd945864f07fe9f5371a27ad7b52a172b4b499999f1d97574c9fa68373937e12" +checksum = "df1d3c3b53da64cf5760482273a98e575c651a67eec7f77df96b5b642de8f039" [[package]] name = "num-traits" @@ -128,23 +122,22 @@ dependencies = [ [[package]] name = "proc-macro2" -version = "1.0.101" +version = "1.0.103" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "89ae43fd86e4158d6db51ad8e2b80f313af9cc74f5c0e03ccb87de09998732de" +checksum = "5ee95bc4ef87b8d5ba32e8b7714ccc834865276eab0aed5c9958d00ec45f49e8" dependencies = [ "unicode-ident", ] [[package]] name = "proptest" -version = "1.7.0" +version = "1.9.0" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "6fcdab19deb5195a31cf7726a210015ff1496ba1464fd42cb4f537b8b01b471f" +checksum = "bee689443a2bd0a16ab0348b52ee43e3b2d1b1f931c8aa5c9f8de4c86fbe8c40" dependencies = [ "bit-set", "bit-vec", "bitflags", - "lazy_static", "num-traits", "rand", "rand_chacha", @@ -157,9 +150,9 @@ dependencies = [ [[package]] name = "proptest-state-machine" -version = "0.4.0" +version = "0.6.0" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "53f556db2c446aa1f554a94938ea54bf16a37742bbb984dc5d8dcf6866b1dd5a" +checksum = "7eba9bfb050fa950d84cff5135a6c455610e03defc124cea67059515cd8293df" dependencies = [ "proptest", ] @@ -172,9 +165,9 @@ checksum = "a1d01941d82fa2ab50be1e79e6714289dd7cde78eba4c074bc5a4374f650dfe0" [[package]] name = "quote" -version = "1.0.40" +version = "1.0.42" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "1885c039570dc00dcb4ff087a89e185fd56bae234ddc7f056a945bf36467248d" +checksum = "a338cc41d27e6cc6dce6cefc13a0729dfbb81c262b1f519331575dd80ef3067f" dependencies = [ "proc-macro2", ] @@ -225,15 +218,15 @@ dependencies = [ [[package]] name = "regex-syntax" -version = "0.8.6" +version = "0.8.8" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "caf4aa5b0f434c91fe5c7f1ecb6a5ece2130b02ad2a590589dda5146df959001" +checksum = "7a2d987857b319362043e95f5353c0535c1f58eec5336fdfcf626430af7def58" [[package]] name = "rustix" -version = "1.0.8" +version = "1.1.2" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "11181fbabf243db407ef8df94a6ce0b2f9a733bd8be4ad02b4eda9602296cac8" +checksum = "cd15f8a2c5551a84d56efdc1cd049089e409ac19a3072d5037a17fd70719ff3e" dependencies = [ "bitflags", "errno", @@ -244,9 +237,9 @@ dependencies = [ [[package]] name = "rusty-fork" -version = "0.3.0" +version = "0.3.1" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "cb3dcc6e454c328bb824492db107ab7c0ae8fcffe4ad210136ef014458c1bc4f" +checksum = "cc6bf79ff24e648f6da1f8d1f011e9cac26491b619e6b9280f2b47f1774e6ee2" dependencies = [ "fnv", "quick-error", @@ -256,9 +249,9 @@ dependencies = [ [[package]] name = "syn" -version = "2.0.106" +version = "2.0.111" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "ede7c438028d4436d71104916910f5bb611972c5cfd7f89b8300a8186e6fada6" +checksum = "390cc9a294ab71bdb1aa2e99d13be9c753cd2d7bd6560c77118597410c4d2e87" dependencies = [ "proc-macro2", "quote", @@ -267,9 +260,9 @@ dependencies = [ [[package]] name = "tempfile" -version = "3.21.0" +version = "3.23.0" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "15b61f8f20e3a6f7e0649d825294eaf317edce30f82cf6026e7e4cb9222a7d1e" +checksum = "2d31c77bdf42a745371d260a26ca7163f1e0924b64afa0b688e61b5a9fa02f16" dependencies = [ "fastrand", "getrandom", @@ -286,9 +279,9 @@ checksum = "eaea85b334db583fe3274d12b4cd1880032beab409c0d774be044d4480ab9a94" [[package]] name = "unicode-ident" -version = "1.0.18" +version = "1.0.22" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "5a5f39404a5da50712a4c1eecf25e90dd62b613502b7e925fd4e4d19b5c96512" +checksum = "9312f7c4f6ff9069b165498234ce8be658059c6728633667c526e27dc2cf1df5" [[package]] name = "wait-timeout" @@ -300,114 +293,49 @@ dependencies = [ ] [[package]] -name = "wasi" -version = "0.14.4+wasi-0.2.4" +name = "wasip2" +version = "1.0.1+wasi-0.2.4" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "88a5f4a424faf49c3c2c344f166f0662341d470ea185e939657aaff130f0ec4a" +checksum = "0562428422c63773dad2c345a1882263bbf4d65cf3f42e90921f787ef5ad58e7" dependencies = [ "wit-bindgen", ] [[package]] name = "windows-link" -version = "0.1.3" +version = "0.2.1" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "5e6ad25900d524eaabdbbb96d20b4311e1e7ae1699af4fb28c17ae66c80d798a" +checksum = "f0805222e57f7521d6a62e36fa9163bc891acd422f971defe97d64e70d0a4fe5" [[package]] name = "windows-sys" -version = "0.60.2" -source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "f2f500e4d28234f72040990ec9d39e3a6b950f9f22d3dba18416c35882612bcb" -dependencies = [ - "windows-targets", -] - -[[package]] -name = "windows-targets" -version = "0.53.3" +version = "0.61.2" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "d5fe6031c4041849d7c496a8ded650796e7b6ecc19df1a431c1a363342e5dc91" +checksum = "ae137229bcbd6cdf0f7b80a31df61766145077ddf49416a728b02cb3921ff3fc" dependencies = [ "windows-link", - "windows_aarch64_gnullvm", - "windows_aarch64_msvc", - "windows_i686_gnu", - "windows_i686_gnullvm", - "windows_i686_msvc", - "windows_x86_64_gnu", - "windows_x86_64_gnullvm", - "windows_x86_64_msvc", ] [[package]] -name = "windows_aarch64_gnullvm" -version = "0.53.0" -source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "86b8d5f90ddd19cb4a147a5fa63ca848db3df085e25fee3cc10b39b6eebae764" - -[[package]] -name = "windows_aarch64_msvc" -version = "0.53.0" -source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "c7651a1f62a11b8cbd5e0d42526e55f2c99886c77e007179efff86c2b137e66c" - -[[package]] -name = "windows_i686_gnu" -version = "0.53.0" -source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "c1dc67659d35f387f5f6c479dc4e28f1d4bb90ddd1a5d3da2e5d97b42d6272c3" - -[[package]] -name = "windows_i686_gnullvm" -version = "0.53.0" -source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "9ce6ccbdedbf6d6354471319e781c0dfef054c81fbc7cf83f338a4296c0cae11" - -[[package]] -name = "windows_i686_msvc" -version = "0.53.0" -source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "581fee95406bb13382d2f65cd4a908ca7b1e4c2f1917f143ba16efe98a589b5d" - -[[package]] -name = "windows_x86_64_gnu" -version = "0.53.0" -source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "2e55b5ac9ea33f2fc1716d1742db15574fd6fc8dadc51caab1c16a3d3b4190ba" - -[[package]] -name = "windows_x86_64_gnullvm" -version = "0.53.0" -source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "0a6e035dd0599267ce1ee132e51c27dd29437f63325753051e71dd9e42406c57" - -[[package]] -name = "windows_x86_64_msvc" -version = "0.53.0" -source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "271414315aff87387382ec3d271b52d7ae78726f5d44ac98b4f4030c91880486" - -[[package]] name = "wit-bindgen" -version = "0.45.1" +version = "0.46.0" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "5c573471f125075647d03df72e026074b7203790d41351cd6edc96f46bcccd36" +checksum = "f17a85883d4e6d00e8a97c586de764dabcc06133f7f1d55dce5cdc070ad7fe59" [[package]] name = "zerocopy" -version = "0.8.27" +version = "0.8.31" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "0894878a5fa3edfd6da3f88c4805f4c8558e2b996227a3d864f47fe11e38282c" +checksum = "fd74ec98b9250adb3ca554bdde269adf631549f51d8a8f8f0a10b50f1cb298c3" dependencies = [ "zerocopy-derive", ] [[package]] name = "zerocopy-derive" -version = "0.8.27" +version = "0.8.31" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "88d2b8d9c68ad2b9e4340d7832716a4d21a22a1154777ad56ea55c51a9cf3831" +checksum = "d8a8d209fdf45cf5138cbb5a506f6b52522a25afccc534d1475dad8e31105c6a" dependencies = [ "proc-macro2", "quote", diff --git a/Cargo.toml b/Cargo.toml index 1b50de4..4901b85 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -13,7 +13,77 @@ generativity = "1" proptest = "1" # Used to make more thorough tests using `proptest` -proptest-state-machine = "0.4" +proptest-state-machine = "0.6" + +[workspace.lints.rust] +missing_docs = "deny" +trivial_casts = "deny" +trivial_numeric_casts = "deny" + +[workspace.lints.rust.unexpected_cfgs] +level = "warn" +# Kani will trigger this lint otherwise +check-cfg = ['cfg(kani)'] + +[workspace.lints.rustdoc] +broken_intra_doc_links = "deny" + +[workspace.lints.clippy] +cargo_common_metadata = "warn" +dbg_macro = "warn" +needless_pass_by_ref_mut = "warn" +needless_pass_by_value = "warn" +print_stderr = "warn" +print_stdout = "warn" +todo = "warn" +unimplemented = "warn" +unreachable = "warn" +arithmetic_side_effects = "deny" +await_holding_lock = "deny" +cast_lossless = "deny" +cast_possible_truncation = "deny" +clone_on_ref_ptr = "deny" +default_trait_access = "deny" +doc_markdown = "deny" +empty_enums = "deny" +enum_glob_use = "deny" +exit = "deny" +expect_used = "deny" +explicit_deref_methods = "deny" +explicit_into_iter_loop = "deny" +explicit_iter_loop = "deny" +fallible_impl_from = "deny" +filetype_is_file = "deny" +float_cmp = "deny" +float_cmp_const = "deny" +fn_params_excessive_bools = "deny" +imprecise_flops = "deny" +indexing_slicing = "deny" +inefficient_to_string = "deny" +infinite_iter = "deny" +large_digit_groups = "deny" +large_stack_arrays = "deny" +manual_filter_map = "deny" +match_like_matches_macro = "deny" +missing_errors_doc = "deny" +missing_safety_doc = "deny" +must_use_candidate = "deny" +mut_mut = "deny" +option_option = "deny" +panic = "deny" +panic_in_result_fn = "deny" +redundant_clone = "deny" +redundant_else = "deny" +rest_pat_in_fully_bound_structs = "deny" +single_match_else = "deny" +implicit_clone = "deny" +undocumented_unsafe_blocks = "deny" +unneeded_field_pattern = "deny" +unused_self = "deny" +unwrap_used = "deny" +wildcard_dependencies = "deny" +wildcard_enum_match_arm = "deny" +wildcard_imports = "deny" [profile.release] opt-level = 3 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 {} |