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

universal_weave/
lib.rs
