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

universal_weave/
lib.rs
