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

universal_weave/
lib.rs
