universal_weave/
lib.rs

1//! General-purpose building blocks for [Loom](https://generative.ink/posts/loom-interface-to-the-multiverse/) implementations.
2//!
3//! This library aims to make building Loom implementations easier by providing the following primitives:
4//! - [`DependentWeave`](dependent::DependentWeave) - A tree-based [`Weave`] where each [`Node`] depends on the contents of the previous Node.
5//!     - [`DependentLoroWeave`](dependent::loro::DependentLoroWeave) - A [`DependentWeave`](dependent::DependentWeave) wrapper which adds collaborative editing using the [`loro`] CRDT library (requires `rkyv` and `loro` features to be enabled).
6//! - [`IndependentWeave`](independent::IndependentWeave) - A DAG-based [`Weave`] where each [`Node`] does *not* depend on the contents of the previous Node.
7//!
8//! Operations on the built-in [`Weave`] implementations always preserve node ordering through the use of [`IndexSet`](indexmap::IndexSet), and (non-tail) insertion and removal operations on ordered sets can have a worst-case time complexity of O(n).
9//!
10//! Efficient (de)serialization is supported using `rkyv` and `serde`. Basic functionality for versioning serialized data is provided by [`VersionedBytes`](versioning::VersionedBytes) (requires `rkyv` feature to be enabled).
11
12#![no_std]
13#![forbid(non_ascii_idents)]
14#![warn(missing_docs)]
15#![warn(let_underscore)]
16#![warn(clippy::pedantic)]
17#![warn(clippy::cargo)]
18#![allow(clippy::multiple_crate_versions, reason = "Unresolvable")]
19#![warn(clippy::nursery)]
20#![warn(clippy::restriction)]
21#![allow(clippy::blanket_clippy_restriction_lints, reason = "Conflicting lint")]
22#![allow(clippy::allow_attributes, reason = "Conflicting lint")]
23#![allow(clippy::pattern_type_mismatch, reason = "Conflicting lint")]
24#![allow(clippy::separated_literal_suffix, reason = "Conflicting lint")]
25#![allow(clippy::semicolon_outside_block, reason = "Conflicting lint")]
26#![allow(
27    clippy::field_scoped_visibility_modifiers,
28    reason = "Used by IndependentWeave::from()"
29)]
30#![allow(
31    clippy::missing_inline_in_public_items,
32    reason = "Reasonable candidates have already been inlined"
33)]
34#![allow(clippy::exhaustive_enums, reason = "API")]
35#![allow(clippy::exhaustive_structs, reason = "API")]
36#![allow(clippy::little_endian_bytes, reason = "API")]
37#![allow(clippy::partial_pub_fields, reason = "API")]
38#![allow(clippy::pub_use, reason = "API")]
39#![allow(clippy::arbitrary_source_item_ordering, reason = "Readability")]
40#![allow(clippy::question_mark_used, reason = "Readability")]
41#![allow(clippy::single_call_fn, reason = "Readability")]
42#![allow(clippy::single_char_lifetime_names, reason = "Readability")]
43#![allow(clippy::else_if_without_else, reason = "Style")]
44#![allow(clippy::if_then_some_else_none, reason = "Style")]
45#![allow(clippy::implicit_return, reason = "Style")]
46#![allow(clippy::min_ident_chars, reason = "Style")]
47#![allow(clippy::mod_module_files, reason = "Style")]
48#![allow(clippy::module_name_repetitions, reason = "Style")]
49#![allow(clippy::multiple_inherent_impl, reason = "Style")]
50#![allow(clippy::try_err, reason = "Style")]
51#![allow(clippy::allow_attributes_without_reason)] // TODO
52#![allow(clippy::indexing_slicing)] // TODO
53#![allow(clippy::unwrap_in_result)] // TODO
54#![allow(clippy::unwrap_used)] // TODO
55#![allow(clippy::missing_docs_in_private_items)] // TODO
56#![allow(clippy::shadow_unrelated)] // TODO
57#![allow(clippy::shadow_reuse)] // TODO
58
59/*
60
61Testing notes:
62- When running multiple tests, use `cargo nextest run` instead of `cargo test`
63- Test building for no_std using `cargo build --target=aarch64-unknown-none --no-default-features --features serde,rkyv,legacy`
64- The following tests continue to function in release mode:
65    - archived_dependent
66    - archived_independent
67    - dependent_behavior_unchanged
68    - independent_behavior_unchanged
69    - independent_extends_dependent
70
71*/
72
73mod contract;
74pub mod dependent;
75pub mod independent;
76pub mod wrappers;
77
78#[cfg(feature = "rkyv")]
79pub mod versioning;
80
81pub use contracts;
82pub use hashbrown;
83pub use indexmap;
84
85#[cfg(feature = "rkyv")]
86pub use rkyv;
87
88#[cfg(feature = "serde")]
89pub use serde;
90
91#[cfg(feature = "loro")]
92pub use loro;
93
94extern crate alloc;
95
96use alloc::vec::Vec;
97use core::{
98    cmp::{Ordering, Reverse},
99    hash::{BuildHasher, Hash},
100};
101
102use hashbrown::HashMap;
103use scratchpads::{ScratchpadMap, ScratchpadSet, ScratchpadVec};
104
105#[cfg(feature = "rkyv")]
106use rkyv::collections::swiss_table::{ArchivedHashMap, ArchivedIndexSet};
107
108/// An item within a [`Weave`] which can be connected to other items.
109#[must_use]
110pub trait Node<K, T>
111where
112    K: Hash + Copy + Eq + Ord,
113{
114    /// Identifiers corresponding to the node's parents.
115    type From;
116    /// Identifiers corresponding to the node's children.
117    type To;
118
119    /// Returns the node's unique identifier.
120    #[must_use]
121    fn id(&self) -> K;
122    /// Returns a reference to the identifiers corresponding to the node's parents.
123    #[must_use]
124    fn from(&self) -> &Self::From;
125    /// Returns a reference to the identifiers corresponding to the node's children.
126    #[must_use]
127    fn to(&self) -> &Self::To;
128    /// Returns `true` if the node is considered active.
129    ///
130    /// The meaning of this value can depend on the underlying [`Weave`] implementation.
131    #[must_use]
132    fn is_active(&self) -> bool;
133    /// Returns a reference to the node's contents.
134    #[must_use]
135    fn contents(&self) -> &T;
136}
137
138/// [`Node`] contents which can be split apart or merged together.
139pub trait DiscreteContents: Sized {
140    /// Splits the item at specified index.
141    ///
142    /// If splitting the item fails, the original contents are returned.
143    fn split(self, at: usize) -> DiscreteContentResult<Self>;
144    /// Merges two items together.
145    ///
146    /// If merging the two items fails, the original contents are returned in the order they were specified in.
147    fn merge(self, value: Self) -> DiscreteContentResult<Self>;
148}
149
150/// A type representing the results of an action on a [`DiscreteContents`] item.
151#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
152#[allow(missing_docs, reason = "Enum items are self-explanatory")]
153#[must_use]
154pub enum DiscreteContentResult<T> {
155    One(T),
156    Two(T, T),
157}
158
159/// [`Node`] contents which do not depend on the contents of other [`Node`] objects in order to be meaningful.
160pub trait IndependentContents {}
161
162/// [`Node`] contents which can be meaningfully deduplicated.
163///
164/// Deduplication must be symmetric: `a.is_duplicate_of(b)` implies `b.is_duplicate_of(a)`.
165pub trait DeduplicatableContents {
166    /// Tests if `self` and `other` should be considered duplicates of each other.
167    #[must_use]
168    fn is_duplicate_of(&self, other: &Self) -> bool;
169}
170
171/// A document linking together multiple [`Node`] objects without cyclical links.
172///
173/// # Deserialization
174///
175/// If a Weave implementation supports deserialization, it must validate internal consistency during the deserialization process in a way which is robust to untrusted inputs.
176///
177/// # Panics
178///
179/// All panics should be assumed to leave the Weave in a malformed state unless otherwise specified by the implementation.
180#[must_use]
181pub trait Weave<K, N, T>
182where
183    K: Hash + Copy + Eq + Ord,
184    N: Node<K, T>,
185{
186    /// Mapping between identifiers and nodes.
187    type Nodes;
188    /// Identifiers of root nodes (nodes which do not have any parents).
189    type Roots;
190
191    /// Returns the number of nodes stored within the Weave.
192    #[must_use]
193    fn len(&self) -> usize;
194    /// Returns `true` if the Weave does not contain any nodes.
195    #[must_use]
196    fn is_empty(&self) -> bool;
197    /// Returns a reference to the identifier:node mapping.
198    #[must_use]
199    fn nodes(&self) -> &Self::Nodes;
200    /// Returns a reference to the identifiers of root nodes (nodes which do not have any parents).
201    #[must_use]
202    fn roots(&self) -> &Self::Roots;
203    /// Returns `true` if the Weave contains a node with the specified identifier.
204    #[must_use]
205    fn contains(&self, id: &K) -> bool;
206    /// Returns `true` if the Weave contains an active node (`node.is_active() == true`) with the specified identifier.
207    ///
208    /// The meaning of this value can depend on the underlying Weave implementation.
209    #[must_use]
210    fn contains_active(&self, id: &K) -> bool;
211    /// Returns a reference to the node corresponding to the identifier.
212    #[must_use]
213    fn get(&self, id: &K) -> Option<&N>;
214    /// Convenience method for `self.get(id).map(Node::from)`.
215    #[must_use]
216    fn get_parents(&self, id: &K) -> Option<&N::From>;
217    /// Convenience method for `self.get(id).map(Node::to)`.
218    #[must_use]
219    fn get_children(&self, id: &K) -> Option<&N::To>;
220    /// Convenience method for `self.get(id).map(Node::contents)`.
221    #[must_use]
222    fn get_contents(&self, id: &K) -> Option<&T>;
223    /// Builds a list of all node identifiers ordered by their positions in the Weave.
224    fn get_ordered_identifiers(&mut self, output: &mut Vec<K>);
225    /// Recursively builds a list of all children of the specified node ordered by their positions in the Weave.
226    ///
227    /// The returned list starts with the identifier of the specified node.
228    fn get_ordered_identifiers_from(&mut self, id: &K, output: &mut Vec<K>);
229    /// Builds a path through the Weave starting at the deepest active node and ending at a root node.
230    ///
231    /// In an [`ActivePathWeave`], this path will be the longest contiguous path of active nodes.
232    fn get_active_path(&mut self, output: &mut Vec<K>);
233    /// Builds a path through the Weave starting at the specified node and ending at a root node.
234    ///
235    /// In an [`ActivePathWeave`], this path will preferentially route through the active path.
236    fn get_path_from(&mut self, id: &K, output: &mut Vec<K>);
237    /// Inserts a node into the Weave, returning `true` if the insertion was successful.
238    ///
239    /// This function may change the active status of nodes if it is necessary to preserve internal consistency.
240    fn insert(&mut self, node: N) -> bool;
241    /// Sets the active status of a node with the specified identifier.
242    ///
243    /// This function may change the active status of other nodes in an implementation-specific manner if it is necessary to preserve internal consistency.
244    fn set_active(&mut self, id: &K, value: bool) -> bool;
245    /// Removes a node with the specified identifier, returning its value if it was present within the Weave.
246    ///
247    /// This function may remove or update other nodes if it is necessary to preserve internal consistency.
248    ///
249    /// This function uses the same removal logic as [`Weave::remove_tracked`].
250    fn remove(&mut self, id: &K) -> Option<N>;
251    /// Removes a node with the specified identifier, returning `true` if it was present within the Weave.
252    ///
253    /// This function may remove or update other nodes if it is necessary to preserve internal consistency. Every removed node will be returned by the `on_removal` call, with removal ordering being defined by the `Weave` implementation.
254    ///
255    /// # Panics
256    ///
257    /// May panic if `on_removal` panics.
258    fn remove_tracked(&mut self, id: &K, on_removal: impl FnMut(N)) -> bool;
259    /// Removes all nodes from the Weave.
260    ///
261    /// In a [`MetadataWeave`], the associated metadata is left unchanged.
262    fn clear(&mut self);
263}
264
265/// A [`Weave`] containing document-wide metadata.
266///
267/// # Panics
268///
269/// All panics should be assumed to leave the Weave in a malformed state unless otherwise specified by the implementation.
270pub trait MetadataWeave<K, N, T, M>: Weave<K, N, T>
271where
272    K: Hash + Copy + Eq + Ord,
273    N: Node<K, T>,
274{
275    /// Returns a reference to the Weave's associated metadata.
276    #[must_use]
277    fn metadata(&self) -> &M;
278    /// Mutable access to the Weave's associated metadata.
279    ///
280    /// # Panics
281    ///
282    /// May panic if `callback` panics.
283    fn metadata_mut<O>(&mut self, callback: impl FnOnce(&mut M) -> O) -> O;
284}
285
286/// A [`Weave`] where nodes can be bookmarked.
287pub trait BookmarkableWeave<K, N, T>: Weave<K, N, T>
288where
289    K: Hash + Copy + Eq + Ord,
290    N: Node<K, T>,
291{
292    /// Identifiers of bookmarked nodes.
293    type Bookmarks;
294
295    /// Returns a reference to the identifiers of bookmarked nodes.
296    #[must_use]
297    fn bookmarks(&self) -> &Self::Bookmarks;
298    /// Returns `true` if the Weave contains a bookmarked node with the specified identifier.
299    #[must_use]
300    fn contains_bookmark(&self, id: &K) -> bool;
301    /// Sets the bookmarked status of a node with the specified identifier.
302    fn set_bookmarked(&mut self, id: &K, value: bool) -> bool;
303}
304
305/// A [`Weave`] where the ordering of nodes is stable and can be user-defined.
306///
307/// # Panics
308///
309/// All panics should be assumed to leave the Weave in a malformed state unless otherwise specified by the implementation.
310pub trait SortableWeave<K, N, T>: Weave<K, N, T>
311where
312    K: Hash + Copy + Eq + Ord,
313    N: Node<K, T>,
314{
315    /// Sorts the child nodes of a parent node with the specified identifier using the comparison function `cmp`.
316    ///
317    /// # Panics
318    ///
319    /// May panic if `cmp` does not implement a [total order](https://en.wikipedia.org/wiki/Total_order), or if `cmp` itself panics.
320    fn sort_children_by(&mut self, id: &K, cmp: impl FnMut(&N, &N) -> Ordering) -> bool;
321    /// Sorts the identifiers of a parent node's children with the specified identifier using the comparison function `cmp`.
322    ///
323    /// # Panics
324    ///
325    /// May panic if `cmp` does not implement a [total order](https://en.wikipedia.org/wiki/Total_order), or if `cmp` itself panics.
326    fn sort_children_by_id(&mut self, id: &K, cmp: impl FnMut(&K, &K) -> Ordering) -> bool;
327    /// Sorts root nodes (nodes which do not have any parents) using the comparison function `cmp`.
328    ///
329    /// # Panics
330    ///
331    /// May panic if `cmp` does not implement a [total order](https://en.wikipedia.org/wiki/Total_order), or if `cmp` itself panics.
332    fn sort_roots_by(&mut self, cmp: impl FnMut(&N, &N) -> Ordering);
333    /// Sorts the identifiers of root nodes (nodes which do not have any parents) using the comparison function `cmp`.
334    ///
335    /// # Panics
336    ///
337    /// May panic if `cmp` does not implement a [total order](https://en.wikipedia.org/wiki/Total_order), or if `cmp` itself panics.
338    fn sort_roots_by_id(&mut self, cmp: impl FnMut(&K, &K) -> Ordering);
339}
340
341/// A [`Weave`] where the ordering of bookmarked nodes is stable and can be user-defined.
342///
343/// # Panics
344///
345/// All panics should be assumed to leave the Weave in a malformed state unless otherwise specified by the implementation.
346pub trait SortableBookmarkableWeave<K, N, T>:
347    BookmarkableWeave<K, N, T> + SortableWeave<K, N, T>
348where
349    K: Hash + Copy + Eq + Ord,
350    N: Node<K, T>,
351{
352    /// Sorts bookmarked nodes using the comparison function `cmp`.
353    ///
354    /// # Panics
355    ///
356    /// May panic if `cmp` does not implement a [total order](https://en.wikipedia.org/wiki/Total_order), or if `cmp` itself panics.
357    fn sort_bookmarks_by(&mut self, cmp: impl FnMut(&N, &N) -> Ordering);
358    /// Sorts the identifiers of bookmarked nodes using the comparison function `cmp`.
359    ///
360    /// # Panics
361    ///
362    /// May panic if `cmp` does not implement a [total order](https://en.wikipedia.org/wiki/Total_order), or if `cmp` itself panics.
363    fn sort_bookmarks_by_id(&mut self, cmp: impl FnMut(&K, &K) -> Ordering);
364}
365
366/// A [`Weave`] where only one [`Node`] can be considered active at a time.
367pub trait ActiveSingularWeave<K, N, T>: Weave<K, N, T>
368where
369    K: Hash + Copy + Eq + Ord,
370    N: Node<K, T>,
371{
372    /// Returns the active node's identifier, if any.
373    #[must_use]
374    fn active(&self) -> Option<K>;
375}
376
377/// A [`Weave`] where every [`Node`] in the active path is always considered active.
378pub trait ActivePathWeave<K, N, T>: Weave<K, N, T>
379where
380    K: Hash + Copy + Eq + Ord,
381    N: Node<K, T>,
382{
383    /// Identifiers of active nodes.
384    type Active;
385
386    /// Returns a reference to the identifiers of active nodes.
387    #[must_use]
388    fn active(&self) -> &Self::Active;
389    /// Replaces the currently active path with the specified set of node IDs.
390    ///
391    /// If the new active path would result in internal inconsistency, this function will correct the path in an implementation-specific manner.
392    fn set_active_path(&mut self, active: impl Iterator<Item = K>);
393}
394
395/// A [`Weave`] where [`Node`] objects do not depend on their parents in order to be meaningful.
396pub trait IndependentWeave<K, N, T>: Weave<K, N, T> + SemiIndependentWeave<K, N, T>
397where
398    K: Hash + Copy + Eq + Ord,
399    N: Node<K, T>,
400    T: IndependentContents,
401{
402    /// Moves a node with the specified identifier to a new set of parent nodes, returning `true` if the move was successful.
403    ///
404    /// This function may change the active status of other nodes if it is necessary to preserve internal consistency.
405    fn move_to(&mut self, id: &K, new_parents: &[K]) -> bool;
406}
407
408/// A [`Weave`] where [`Node`] objects do not depend on the *contents* of their parents in order to be meaningful.
409///
410/// # Panics
411///
412/// All panics should be assumed to leave the Weave in a malformed state unless otherwise specified by the implementation.
413pub trait SemiIndependentWeave<K, N, T>: Weave<K, N, T>
414where
415    K: Hash + Copy + Eq + Ord,
416    N: Node<K, T>,
417    T: IndependentContents,
418{
419    /// Mutable access to the contents of a node with the specified identifier.
420    ///
421    /// Returns `Some` if the node's contents were successfully updated.
422    ///
423    /// # Panics
424    ///
425    /// May panic if `callback` panics.
426    #[must_use]
427    fn get_contents_mut<O>(&mut self, id: &K, callback: impl FnOnce(&mut T) -> O) -> Option<O>;
428}
429
430/// A [`Weave`] where the contents of [`Node`] objects can be split and merged.
431///
432/// # Panics
433///
434/// All panics should be assumed to leave the Weave in a malformed state unless otherwise specified by the implementation.
435pub trait DiscreteWeave<K, N, T>: Weave<K, N, T>
436where
437    K: Hash + Copy + Eq + Ord,
438    N: Node<K, T>,
439    T: DiscreteContents,
440{
441    /// Splits a node with the specified identifier at the given index, creating a new child node with the identifier `new_id`.
442    ///
443    /// If the target node is at the end of the active path, the right side of the split will be inactive.
444    ///
445    /// Returns `false` if splitting the node failed.
446    ///
447    /// # Panics
448    ///
449    /// May panic if `T::split` panics.
450    fn split(&mut self, id: &K, at: usize, new_id: K) -> bool;
451    /// Merges a node with the specified identifier with its parent, with the newly merged node inheriting the parent's identifier.
452    ///
453    /// Returns the identifier of the merged node if merging was successful.
454    ///
455    /// # Panics
456    ///
457    /// May panic if `T::merge` panics.
458    fn merge_with_parent(&mut self, id: &K) -> Option<K>;
459}
460
461/// A read-only [`Weave`].
462#[must_use]
463pub trait ImmutableWeave<K, N, T>
464where
465    K: Hash + Copy + Eq + Ord,
466    N: Node<K, T>,
467{
468    /// Mapping between identifiers and nodes.
469    type Nodes;
470    /// Identifiers of root nodes (nodes which do not have any parents).
471    type Roots;
472
473    /// Returns the number of nodes stored within the Weave.
474    #[must_use]
475    fn len(&self) -> usize;
476    /// Returns `true` if the Weave does not contain any nodes.
477    #[must_use]
478    fn is_empty(&self) -> bool;
479    /// Returns a reference to the identifier:node mapping.
480    #[must_use]
481    fn nodes(&self) -> &Self::Nodes;
482    /// Returns a reference to the identifiers of root nodes (nodes which do not have any parents).
483    #[must_use]
484    fn roots(&self) -> &Self::Roots;
485    /// Returns `true` if the Weave contains a node with the specified identifier.
486    #[must_use]
487    fn contains(&self, id: &K) -> bool;
488    /// Returns `true` if the Weave contains an active node (`node.is_active() == true`) with the specified identifier.
489    ///
490    /// The meaning of this value can depend on the underlying Weave implementation.
491    #[must_use]
492    fn contains_active(&self, id: &K) -> bool;
493    /// Returns a reference to the node corresponding to the identifier.
494    #[must_use]
495    fn get(&self, id: &K) -> Option<&N>;
496    /// Convenience method for `self.get(id).map(Node::from)`.
497    #[must_use]
498    fn get_parents(&self, id: &K) -> Option<&N::From>;
499    /// Convenience method for `self.get(id).map(Node::to)`.
500    #[must_use]
501    fn get_children(&self, id: &K) -> Option<&N::To>;
502    /// Convenience method for `self.get(id).map(Node::contents)`.
503    #[must_use]
504    fn get_contents(&self, id: &K) -> Option<&T>;
505    /// Builds a list of all node identifiers ordered by their positions in the Weave.
506    fn get_ordered_identifiers(&self, output: &mut Vec<K>);
507    /// Recursively builds a list of all children of the specified node ordered by their positions in the Weave.
508    ///
509    /// The returned list starts with the identifier of the specified node.
510    fn get_ordered_identifiers_from(&self, id: &K, output: &mut Vec<K>);
511    /// Builds a path through the Weave starting at the deepest active node and ending at a root node.
512    ///
513    /// In an [`ImmutableActivePathWeave`], this path will be the longest contiguous path of active nodes.
514    fn get_active_path(&self, output: &mut Vec<K>);
515    /// Builds a path through the Weave starting at the specified node and ending at a root node.
516    ///
517    /// In an [`ImmutableActivePathWeave`], this path will preferentially route through the active path.
518    fn get_path_from(&self, id: &K, output: &mut Vec<K>);
519}
520
521/// An [`ImmutableWeave`] containing document-wide metadata.
522pub trait ImmutableMetadataWeave<K, N, T, M>: ImmutableWeave<K, N, T>
523where
524    K: Hash + Copy + Eq + Ord,
525    N: Node<K, T>,
526{
527    /// Returns a reference to the Weave's associated metadata.
528    #[must_use]
529    fn metadata(&self) -> &M;
530}
531
532/// An [`ImmutableWeave`] where nodes can be bookmarked.
533pub trait ImmutableBookmarkableWeave<K, N, T>: ImmutableWeave<K, N, T>
534where
535    K: Hash + Copy + Eq + Ord,
536    N: Node<K, T>,
537{
538    /// Identifiers of bookmarked nodes.
539    type Bookmarks;
540
541    /// Returns a reference to the identifiers of bookmarked nodes.
542    #[must_use]
543    fn bookmarks(&self) -> &Self::Bookmarks;
544    /// Returns `true` if the Weave contains a bookmarked node with the specified identifier.
545    #[must_use]
546    fn contains_bookmark(&self, id: &K) -> bool;
547}
548
549/// An [`ImmutableWeave`] where only one [`Node`] can be considered active at a time.
550pub trait ImmutableActiveSingularWeave<K, N, T>: ImmutableWeave<K, N, T>
551where
552    K: Hash + Copy + Eq + Ord,
553    N: Node<K, T>,
554{
555    /// Returns the active node's identifier, if any.
556    #[must_use]
557    fn active(&self) -> Option<K>;
558}
559
560/// An [`ImmutableWeave`] where every [`Node`] in the active path is always considered active.
561pub trait ImmutableActivePathWeave<K, N, T>: ImmutableWeave<K, N, T>
562where
563    K: Hash + Copy + Eq + Ord,
564    N: Node<K, T>,
565{
566    /// Identifiers of active nodes.
567    type Active;
568
569    /// Returns a reference to the identifiers of active nodes.
570    #[must_use]
571    fn active(&self) -> &Self::Active;
572}
573
574#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
575enum Step<A, B> {
576    Enter(A),
577    Exit(B),
578}
579
580fn topological_sort<'a, K, N, T, S>(
581    nodes: &'a HashMap<K, N, S>,
582    roots: impl DoubleEndedIterator<Item = K>,
583    stack: &mut ScratchpadVec<'_, K>,
584    mut identifier_callback: impl FnMut(K),
585    identifier_map: &mut ScratchpadMap<'_, K, usize, S>,
586) where
587    K: Hash + Copy + Eq + Ord + 'a,
588    N: Node<K, T> + 'a,
589    <N as Node<K, T>>::From: 'a,
590    <N as Node<K, T>>::To: 'a,
591    &'a N::From: IntoIterator<Item = &'a K, IntoIter: DoubleEndedIterator + ExactSizeIterator>,
592    &'a N::To: IntoIterator<Item = &'a K, IntoIter: DoubleEndedIterator>,
593    S: BuildHasher + Default + Clone,
594{
595    stack.extend(roots.rev());
596
597    while let Some(id) = stack.pop() {
598        identifier_callback(id);
599
600        for child in nodes[&id].to().into_iter().rev().copied() {
601            let remaining = identifier_map
602                .entry(child)
603                .or_insert_with(|| nodes[&child].from().into_iter().len());
604            *remaining = remaining.strict_sub(1);
605
606            if *remaining == 0 {
607                stack.push(child);
608            }
609        }
610    }
611}
612
613#[cfg(feature = "rkyv")]
614fn archived_topological_sort<'a, K, N, T, S>(
615    nodes: &'a ArchivedHashMap<K, N>,
616    roots: &'a ArchivedIndexSet<K>,
617    stack: &mut ScratchpadVec<'_, K>,
618    mut identifier_callback: impl FnMut(K),
619    identifier_map: &mut ScratchpadMap<'_, K, usize, S>,
620) where
621    K: Hash + Copy + Eq + Ord + 'a,
622    N: Node<K, T, From = ArchivedIndexSet<K>, To = ArchivedIndexSet<K>> + 'a,
623    S: BuildHasher + Default + Clone,
624{
625    stack.extend(archived_set_reverse_order(roots));
626
627    while let Some(id) = stack.pop() {
628        identifier_callback(id);
629
630        for child in archived_set_reverse_order(nodes[&id].to()).copied() {
631            let remaining = identifier_map
632                .entry(child)
633                .or_insert_with(|| nodes[&child].from().iter().len());
634            *remaining = remaining.strict_sub(1);
635
636            if *remaining == 0 {
637                stack.push(child);
638            }
639        }
640    }
641}
642
643fn topological_sort_subgraph<'a, K, N, T, S>(
644    nodes: &'a HashMap<K, N, S>,
645    filter: impl Fn(&K) -> bool,
646    subgraph_root: K,
647    stack: &mut ScratchpadVec<'_, K>,
648    mut identifier_callback: impl FnMut(K),
649    identifier_map: &mut ScratchpadMap<'_, K, usize, S>,
650) where
651    K: Hash + Copy + Eq + Ord + 'a,
652    N: Node<K, T> + 'a,
653    <N as Node<K, T>>::From: 'a,
654    <N as Node<K, T>>::To: 'a,
655    &'a N::From: IntoIterator<Item = &'a K, IntoIter: DoubleEndedIterator>,
656    &'a N::To: IntoIterator<Item = &'a K, IntoIter: DoubleEndedIterator>,
657    S: BuildHasher + Default + Clone,
658{
659    /*if filter(id)
660        && !identifier_map.contains_key(id)
661        && nodes[id]
662            .from()
663            .into_iter()
664            .filter(|&parent| filter(parent))
665            .count()
666            == 0
667    {
668        stack.push(*id);
669    }*/
670
671    stack.push(subgraph_root);
672
673    while let Some(id) = stack.pop() {
674        identifier_callback(id);
675
676        for child in nodes[&id].to().into_iter().rev().copied() {
677            if !filter(&child) {
678                continue;
679            }
680
681            let remaining = identifier_map.entry(child).or_insert_with(|| {
682                nodes[&child]
683                    .from()
684                    .into_iter()
685                    .filter(|&parent| filter(parent))
686                    .count()
687            });
688            *remaining = remaining.strict_sub(1);
689
690            if *remaining == 0 {
691                stack.push(child);
692            }
693        }
694    }
695}
696
697#[cfg(feature = "rkyv")]
698fn archived_topological_sort_subgraph<'a, K, N, T, S>(
699    nodes: &'a ArchivedHashMap<K, N>,
700    filter: impl Fn(&K) -> bool,
701    subgraph_root: K,
702    stack: &mut ScratchpadVec<'_, K>,
703    mut identifier_callback: impl FnMut(K),
704    identifier_map: &mut ScratchpadMap<'_, K, usize, S>,
705) where
706    K: Hash + Copy + Eq + Ord + 'a,
707    N: Node<K, T, From = ArchivedIndexSet<K>, To = ArchivedIndexSet<K>> + 'a,
708    S: BuildHasher + Default + Clone,
709{
710    /*if filter(id)
711        && !identifier_map.contains_key(id)
712        && nodes[id]
713            .from()
714            .into_iter()
715            .filter(|&parent| filter(parent))
716            .count()
717            == 0
718    {
719        stack.push(*id);
720    }*/
721
722    stack.push(subgraph_root);
723
724    while let Some(id) = stack.pop() {
725        identifier_callback(id);
726
727        for child in archived_set_reverse_order(nodes[&id].to()).copied() {
728            if !filter(&child) {
729                continue;
730            }
731
732            let remaining = identifier_map.entry(child).or_insert_with(|| {
733                nodes[&child]
734                    .from()
735                    .iter()
736                    .filter(|&parent| filter(parent))
737                    .count()
738            });
739            *remaining = remaining.strict_sub(1);
740
741            if *remaining == 0 {
742                stack.push(child);
743            }
744        }
745    }
746}
747
748fn shortest_path_to_ancestor<'a, K, N, T, S>(
749    nodes: &'a HashMap<K, N, S>,
750    id: &'a K,
751    target: impl Fn(&'a N) -> bool,
752    scratchpad: &mut ScratchpadVec<'_, K>,
753    scratchpad_map: &mut ScratchpadMap<'_, K, K, S>,
754    scratchpad_set: &mut ScratchpadSet<'_, K, S>,
755    path: &mut Vec<K>,
756) where
757    K: Hash + Copy + Eq + Ord + 'a,
758    N: Node<K, T> + 'a,
759    <N as Node<K, T>>::From: 'a,
760    <N as Node<K, T>>::To: 'a,
761    &'a N::From: IntoIterator<Item = &'a K, IntoIter: DoubleEndedIterator>,
762    &'a N::To: IntoIterator<Item = &'a K, IntoIter: DoubleEndedIterator>,
763    S: BuildHasher + Default + Clone,
764{
765    scratchpad.push(*id);
766    scratchpad_set.insert(*id);
767
768    let mut head = 0;
769
770    while head < scratchpad.len() {
771        let id = scratchpad[head];
772        head = head.strict_add(1);
773
774        let node = &nodes[&id];
775
776        if target(node) {
777            path.push(id);
778
779            while let Some(child) = scratchpad_map.remove(path.last().unwrap()) {
780                path.push(child);
781            }
782
783            return;
784        }
785
786        for parent in node.from().into_iter().copied() {
787            if scratchpad_set.insert(parent) {
788                scratchpad.push(parent);
789                scratchpad_map.insert(parent, id);
790            }
791        }
792    }
793}
794
795#[cfg(feature = "rkyv")]
796fn archived_shortest_path_to_ancestor<'a, K, N, T, S>(
797    nodes: &'a ArchivedHashMap<K, N>,
798    id: &'a K,
799    target: impl Fn(&'a N) -> bool,
800    scratchpad: &mut ScratchpadVec<'_, K>,
801    scratchpad_map: &mut ScratchpadMap<'_, K, K, S>,
802    scratchpad_set: &mut ScratchpadSet<'_, K, S>,
803    path: &mut Vec<K>,
804) where
805    K: Hash + Copy + Eq + Ord + 'a,
806    N: Node<K, T, From = ArchivedIndexSet<K>> + 'a,
807    S: BuildHasher + Default + Clone,
808{
809    scratchpad.push(*id);
810    scratchpad_set.insert(*id);
811
812    let mut head = 0;
813
814    while head < scratchpad.len() {
815        let id = scratchpad[head];
816        head = head.strict_add(1);
817
818        let node = &nodes[&id];
819
820        if target(node) {
821            path.push(id);
822
823            while let Some(child) = scratchpad_map.remove(path.last().unwrap()) {
824                path.push(child);
825            }
826
827            return;
828        }
829
830        for parent in node.from().iter().copied() {
831            if scratchpad_set.insert(parent) {
832                scratchpad.push(parent);
833                scratchpad_map.insert(parent, id);
834            }
835        }
836    }
837}
838
839fn longest_candidate_path_to_root<'a, K, N, T, S>(
840    nodes: &'a HashMap<K, N, S>,
841    topological_order: &[K],
842    is_candidate: impl Fn(&K) -> bool,
843    scratchpad_map: &mut ScratchpadMap<'_, K, usize, S>,
844    mut reversed_path_callback: impl FnMut(K),
845) where
846    K: Hash + Copy + Eq + Ord + 'a,
847    N: Node<K, T> + 'a,
848    <N as Node<K, T>>::From: 'a,
849    <N as Node<K, T>>::To: 'a,
850    &'a N::From: IntoIterator<Item = &'a K, IntoIter: DoubleEndedIterator>,
851    &'a N::To: IntoIterator<Item = &'a K, IntoIter: DoubleEndedIterator>,
852    S: BuildHasher + Default + Clone,
853{
854    let mut longest_distance = None;
855
856    for id in topological_order {
857        if !is_candidate(id) {
858            continue;
859        }
860
861        let node = &nodes[id];
862        let distance = if node.from().into_iter().next().is_none() {
863            Some(0)
864        } else {
865            node.from()
866                .into_iter()
867                .filter_map(|parent| scratchpad_map.get(parent).copied())
868                .max()
869                .map(|l| l.strict_add(1))
870        };
871
872        if let Some(distance) = distance {
873            scratchpad_map.insert(*id, distance);
874
875            if longest_distance.is_none_or(|(value, _)| distance > value) {
876                longest_distance = Some((distance, id));
877            }
878        }
879    }
880
881    let mut current = longest_distance.map(|(_, id)| id);
882
883    while let Some(id) = current {
884        reversed_path_callback(*id);
885
886        current = nodes[id]
887            .from()
888            .into_iter()
889            .filter_map(|parent| {
890                scratchpad_map
891                    .get(parent)
892                    .copied()
893                    .map(|distance| (parent, distance))
894            })
895            .min_by_key(|&(_, distance)| Reverse(distance))
896            .map(|(parent, _)| parent);
897    }
898}
899
900#[cfg(feature = "rkyv")]
901fn archived_longest_candidate_path_to_root<'a, K, N, T, S>(
902    nodes: &'a ArchivedHashMap<K, N>,
903    topological_order: &'a [K],
904    is_candidate: impl Fn(&K) -> bool,
905    scratchpad_map: &mut ScratchpadMap<'_, K, usize, S>,
906    mut reversed_path_callback: impl FnMut(K),
907) where
908    K: Hash + Copy + Eq + Ord + 'a,
909    N: Node<K, T, From = ArchivedIndexSet<K>> + 'a,
910    S: BuildHasher + Default + Clone,
911{
912    let mut longest_distance = None;
913
914    for id in topological_order {
915        if !is_candidate(id) {
916            continue;
917        }
918
919        let node = &nodes[id];
920        let distance = if node.from().is_empty() {
921            Some(0)
922        } else {
923            node.from()
924                .iter()
925                .filter_map(|parent| scratchpad_map.get(parent).copied())
926                .max()
927                .map(|l| l.strict_add(1))
928        };
929
930        if let Some(distance) = distance {
931            scratchpad_map.insert(*id, distance);
932
933            if longest_distance.is_none_or(|(value, _)| distance > value) {
934                longest_distance = Some((distance, id));
935            }
936        }
937    }
938
939    let mut current = longest_distance.map(|(_, id)| id);
940
941    while let Some(id) = current {
942        reversed_path_callback(*id);
943
944        current = nodes[id]
945            .from()
946            .iter()
947            .filter_map(|parent| {
948                scratchpad_map
949                    .get(parent)
950                    .copied()
951                    .map(|distance| (parent, distance))
952            })
953            .min_by_key(|&(_, distance)| Reverse(distance))
954            .map(|(parent, _)| parent);
955    }
956}
957
958fn ancestor_subgraph<'a, K, N, T, S>(
959    nodes: &'a HashMap<K, N, S>,
960    id: K,
961    stack: &mut ScratchpadVec<'_, K>,
962    identifiers: &mut ScratchpadSet<'_, K, S>,
963    mut root_callback: impl FnMut(K),
964) where
965    K: Hash + Copy + Eq + Ord + 'a,
966    N: Node<K, T>,
967    <N as Node<K, T>>::From: 'a,
968    <N as Node<K, T>>::To: 'a,
969    &'a N::From: IntoIterator<Item = &'a K, IntoIter: DoubleEndedIterator + ExactSizeIterator>,
970    &'a N::To: IntoIterator<Item = &'a K, IntoIter: DoubleEndedIterator>,
971    S: BuildHasher + Default + Clone,
972{
973    if identifiers.insert(id) {
974        stack.push(id);
975    }
976
977    while let Some(id) = stack.pop() {
978        let from = nodes[&id].from().into_iter();
979
980        if from.len() == 0 {
981            root_callback(id);
982        } else {
983            for parent in from.rev().copied() {
984                if identifiers.insert(parent) {
985                    stack.push(parent);
986                }
987            }
988        }
989    }
990}
991
992fn ancestor_subgraph_reaches<'a, K, N, T, S>(
993    nodes: &'a HashMap<K, N, S>,
994    ids: impl DoubleEndedIterator<Item = K>,
995    target: impl Fn(&K) -> bool,
996    stack: &mut ScratchpadVec<'_, K>,
997    identifiers: &mut ScratchpadSet<'_, K, S>,
998) -> bool
999where
1000    K: Hash + Copy + Eq + Ord + 'a,
1001    N: Node<K, T>,
1002    <N as Node<K, T>>::From: 'a,
1003    <N as Node<K, T>>::To: 'a,
1004    &'a N::From: IntoIterator<Item = &'a K, IntoIter: DoubleEndedIterator>,
1005    &'a N::To: IntoIterator<Item = &'a K, IntoIter: DoubleEndedIterator>,
1006    S: BuildHasher + Default + Clone,
1007{
1008    for id in ids.rev() {
1009        if identifiers.insert(id) {
1010            if target(&id) {
1011                return true;
1012            }
1013
1014            stack.push(id);
1015        }
1016    }
1017
1018    while let Some(id) = stack.pop() {
1019        for parent in nodes[&id].from().into_iter().rev().copied() {
1020            if identifiers.insert(parent) {
1021                if target(&parent) {
1022                    return true;
1023                }
1024
1025                stack.push(parent);
1026            }
1027        }
1028    }
1029
1030    false
1031}
1032
1033#[cfg(feature = "rkyv")]
1034fn archived_ancestor_subgraph<'a, K, N, T, S>(
1035    nodes: &'a ArchivedHashMap<K, N>,
1036    id: K,
1037    stack: &mut ScratchpadVec<'_, K>,
1038    identifiers: &mut ScratchpadSet<'_, K, S>,
1039    mut root_callback: impl FnMut(K),
1040) where
1041    K: Hash + Copy + Eq + Ord + 'a,
1042    N: Node<K, T, From = ArchivedIndexSet<K>> + 'a,
1043    S: BuildHasher + Default + Clone,
1044{
1045    if identifiers.insert(id) {
1046        stack.push(id);
1047    }
1048
1049    while let Some(id) = stack.pop() {
1050        let from = nodes[&id].from();
1051
1052        if from.is_empty() {
1053            root_callback(id);
1054        } else {
1055            for parent in archived_set_reverse_order(from).copied() {
1056                if identifiers.insert(parent) {
1057                    stack.push(parent);
1058                }
1059            }
1060        }
1061    }
1062}
1063
1064fn descendant_subgraph<'a, K, N, T, S>(
1065    nodes: &'a HashMap<K, N, S>,
1066    id: K,
1067    stack: &mut ScratchpadVec<'_, K>,
1068    identifiers: &mut ScratchpadSet<'_, K, S>,
1069) where
1070    K: Hash + Copy + Eq + Ord + 'a,
1071    N: Node<K, T>,
1072    <N as Node<K, T>>::From: 'a,
1073    <N as Node<K, T>>::To: 'a,
1074    &'a N::From: IntoIterator<Item = &'a K, IntoIter: DoubleEndedIterator>,
1075    &'a N::To: IntoIterator<Item = &'a K, IntoIter: DoubleEndedIterator>,
1076    S: BuildHasher + Default + Clone,
1077{
1078    if identifiers.insert(id) {
1079        stack.push(id);
1080    }
1081
1082    while let Some(id) = stack.pop() {
1083        for child in nodes[&id].to().into_iter().rev().copied() {
1084            if identifiers.insert(child) {
1085                stack.push(child);
1086            }
1087        }
1088    }
1089}
1090
1091fn descendant_subgraph_reaches<'a, K, N, T, S>(
1092    nodes: &'a HashMap<K, N, S>,
1093    ids: impl DoubleEndedIterator<Item = K>,
1094    target: impl Fn(&K) -> bool,
1095    stack: &mut ScratchpadVec<'_, K>,
1096    identifiers: &mut ScratchpadSet<'_, K, S>,
1097) -> bool
1098where
1099    K: Hash + Copy + Eq + Ord + 'a,
1100    N: Node<K, T>,
1101    <N as Node<K, T>>::From: 'a,
1102    <N as Node<K, T>>::To: 'a,
1103    &'a N::From: IntoIterator<Item = &'a K, IntoIter: DoubleEndedIterator>,
1104    &'a N::To: IntoIterator<Item = &'a K, IntoIter: DoubleEndedIterator>,
1105    S: BuildHasher + Default + Clone,
1106{
1107    for id in ids.rev() {
1108        if identifiers.insert(id) {
1109            if target(&id) {
1110                return true;
1111            }
1112
1113            stack.push(id);
1114        }
1115    }
1116
1117    while let Some(id) = stack.pop() {
1118        for child in nodes[&id].to().into_iter().rev().copied() {
1119            if identifiers.insert(child) {
1120                if target(&child) {
1121                    return true;
1122                }
1123
1124                stack.push(child);
1125            }
1126        }
1127    }
1128
1129    false
1130}
1131
1132#[cfg(feature = "rkyv")]
1133fn archived_descendant_subgraph<'a, K, N, T, S>(
1134    nodes: &'a ArchivedHashMap<K, N>,
1135    id: K,
1136    stack: &mut ScratchpadVec<'_, K>,
1137    identifiers: &mut ScratchpadSet<'_, K, S>,
1138) where
1139    K: Hash + Copy + Eq + Ord + 'a,
1140    N: Node<K, T, To = ArchivedIndexSet<K>> + 'a,
1141    S: BuildHasher + Default + Clone,
1142{
1143    if identifiers.insert(id) {
1144        stack.push(id);
1145    }
1146
1147    while let Some(id) = stack.pop() {
1148        for child in archived_set_reverse_order(nodes[&id].to()).copied() {
1149            if identifiers.insert(child) {
1150                stack.push(child);
1151            }
1152        }
1153    }
1154}
1155
1156#[cfg(feature = "rkyv")]
1157fn archived_set_reverse_order<T>(set: &ArchivedIndexSet<T>) -> impl Iterator<Item = &T> {
1158    (0..set.len())
1159        .rev()
1160        .filter_map(|index| set.get_index(index))
1161}
universal_weave/lib.rs

universal_weave/
lib.rs
