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 the longest contiguous path of active nodes which ends at a root node.
199    fn get_active_path(&mut self, output: &mut Vec<K>);
200    /// Builds a path through the Weave starting at the specified node and ending at a root node.
201    ///
202    /// In an [`ActivePathWeave`], this path will preferentially route through the active path.
203    fn get_path_from(&mut self, id: &K, output: &mut Vec<K>);
204    /// Inserts a node into the Weave, returning `true` if the insertion was successful.
205    ///
206    /// This function may change the active status of nodes if it is necessary to preserve internal consistency.
207    fn add_node(&mut self, node: N) -> bool;
208    /// Sets the active status of a node with the specified identifier.
209    ///
210    /// This function may change the active status of other nodes in an implementation-specific manner if it is necessary to preserve internal consistency.
211    fn set_node_active_status(&mut self, id: &K, value: bool) -> bool;
212    /// Removes a node with the specified identifier, returning its value if it was present within the Weave.
213    ///
214    /// This function may remove or update other nodes if it is necessary to preserve internal consistency.
215    ///
216    /// This function uses the same removal logic as [`Weave::remove_node_tracked`].
217    fn remove_node(&mut self, id: &K) -> Option<N>;
218    /// Removes a node with the specified identifier, returning `true` if it was present within the Weave.
219    ///
220    /// 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.
221    ///
222    /// # Panics
223    ///
224    /// May panic if `on_removal` panics.
225    fn remove_node_tracked(&mut self, id: &K, on_removal: impl FnMut(N)) -> bool;
226    /// Removes all nodes from the Weave.
227    fn remove_all_nodes(&mut self);
228}
229
230/// A [`Weave`] containing document-wide metadata.
231pub trait MetadataWeave<K, N, T, M>: Weave<K, N, T>
232where
233    K: Hash + Copy + Eq + Ord,
234    N: Node<K, T>,
235{
236    /// Returns a reference to the Weave's associated metadata.
237    #[must_use]
238    fn metadata(&self) -> &M;
239    /// Mutable access to the Weave's associated metadata.
240    ///
241    /// # Panics
242    ///
243    /// May panic if `callback` panics.
244    fn metadata_mut<O>(&mut self, callback: impl FnOnce(&mut M) -> O) -> O;
245}
246
247/// A [`Weave`] where nodes can be bookmarked.
248pub trait BookmarkableWeave<K, N, T>: Weave<K, N, T>
249where
250    K: Hash + Copy + Eq + Ord,
251    N: Node<K, T>,
252{
253    /// Identifiers of bookmarked nodes.
254    type Bookmarks;
255
256    /// Returns a reference to the identifiers of bookmarked nodes.
257    #[must_use]
258    fn bookmarks(&self) -> &Self::Bookmarks;
259    /// Returns `true` if the Weave contains a bookmarked node with the specified identifier.
260    #[must_use]
261    fn contains_bookmark(&self, id: &K) -> bool;
262    /// Sets the bookmarked status of a node with the specified identifier.
263    fn set_node_bookmarked_status(&mut self, id: &K, value: bool) -> bool;
264}
265
266/// A [`Weave`] where the ordering of nodes is stable and can be user-defined.
267pub trait SortableWeave<K, N, T>: Weave<K, N, T>
268where
269    K: Hash + Copy + Eq + Ord,
270    N: Node<K, T>,
271{
272    /// Builds a list of all node identifiers ordered by their positions in the Weave.
273    ///
274    /// Unlike [`Weave::get_ordered_node_identifiers`], this function reverses the ordering of node children.
275    fn get_ordered_node_identifiers_mirrored(&mut self, output: &mut Vec<K>);
276    /// Recursively builds a list of all children of the specified node ordered by their positions in the Weave.
277    ///
278    /// Unlike [`Weave::get_ordered_node_identifiers_from`], this function reverses the ordering of node children.
279    fn get_ordered_node_identifiers_mirrored_from(&mut self, id: &K, output: &mut Vec<K>);
280    /// Sorts the child nodes of a parent node with the specified identifier using the comparison function `cmp`.
281    ///
282    /// # Panics
283    ///
284    /// May panic if `cmp` does not implement a [total order](https://en.wikipedia.org/wiki/Total_order), or if `cmp` itself panics.
285    fn sort_node_children_by(&mut self, id: &K, cmp: impl FnMut(&N, &N) -> Ordering) -> bool;
286    /// Sorts the identifiers of a parent node's children with the specified identifier using the comparison function `cmp`.
287    ///
288    /// # Panics
289    ///
290    /// May panic if `cmp` does not implement a [total order](https://en.wikipedia.org/wiki/Total_order), or if `cmp` itself panics.
291    fn sort_node_children_by_id(&mut self, id: &K, cmp: impl FnMut(&K, &K) -> Ordering) -> bool;
292    /// Sorts root nodes (nodes which do not have any parents) using the comparison function `cmp`.
293    ///
294    /// # Panics
295    ///
296    /// May panic if `cmp` does not implement a [total order](https://en.wikipedia.org/wiki/Total_order), or if `cmp` itself panics.
297    fn sort_roots_by(&mut self, cmp: impl FnMut(&N, &N) -> Ordering);
298    /// Sorts the identifiers of root nodes (nodes which do not have any parents) using the comparison function `cmp`.
299    ///
300    /// # Panics
301    ///
302    /// May panic if `cmp` does not implement a [total order](https://en.wikipedia.org/wiki/Total_order), or if `cmp` itself panics.
303    fn sort_roots_by_id(&mut self, cmp: impl FnMut(&K, &K) -> Ordering);
304}
305
306/// A [`Weave`] where the ordering of bookmarked nodes is stable and can be user-defined.
307pub trait SortableBookmarkableWeave<K, N, T>:
308    BookmarkableWeave<K, N, T> + SortableWeave<K, N, T>
309where
310    K: Hash + Copy + Eq + Ord,
311    N: Node<K, T>,
312{
313    /// Sorts bookmarked nodes 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_bookmarks_by(&mut self, cmp: impl FnMut(&N, &N) -> Ordering);
319    /// Sorts the identifiers of bookmarked nodes 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_bookmarks_by_id(&mut self, cmp: impl FnMut(&K, &K) -> Ordering);
325}
326
327/// A [`Weave`] where only one [`Node`] can be considered active at a time.
328pub trait ActiveSingularWeave<K, N, T>: Weave<K, N, T>
329where
330    K: Hash + Copy + Eq + Ord,
331    N: Node<K, T>,
332{
333    /// Returns the active node's identifier, if any.
334    #[must_use]
335    fn active(&self) -> Option<K>;
336}
337
338/// A [`Weave`] where every [`Node`] in the active path is always considered active.
339pub trait ActivePathWeave<K, N, T>: Weave<K, N, T>
340where
341    K: Hash + Copy + Eq + Ord,
342    N: Node<K, T>,
343{
344    /// Identifiers of active nodes.
345    type Active;
346
347    /// Returns a reference to the identifiers of active nodes.
348    #[must_use]
349    fn active(&self) -> &Self::Active;
350    /// Replaces the active path.
351    ///
352    /// If the new active path would result in internal inconsistency, this function will correct the path in an implementation-specific manner.
353    fn set_active_path(&mut self, active: impl Iterator<Item = K>);
354}
355
356/// A [`Weave`] where [`Node`] objects do not depend on their parents in order to be meaningful.
357pub trait IndependentWeave<K, N, T>: Weave<K, N, T> + SemiIndependentWeave<K, N, T>
358where
359    K: Hash + Copy + Eq + Ord,
360    N: Node<K, T>,
361    T: IndependentContents,
362{
363    /// Moves a node with the specified identifier to a new set of parent nodes, returning `true` if the move was successful.
364    ///
365    /// This function may change the active status of other nodes if it is necessary to preserve internal consistency.
366    fn move_node(&mut self, id: &K, new_parents: &[K]) -> bool;
367}
368
369/// A [`Weave`] where [`Node`] objects do not depend on the *contents* of their parents in order to be meaningful.
370pub trait SemiIndependentWeave<K, N, T>: Weave<K, N, T>
371where
372    K: Hash + Copy + Eq + Ord,
373    N: Node<K, T>,
374    T: IndependentContents,
375{
376    /// Mutable access to the contents of a node with the specified identifier.
377    ///
378    /// # Panics
379    ///
380    /// May panic if `callback` panics.
381    fn get_contents_mut<O>(&mut self, id: &K, callback: impl FnOnce(&mut T) -> O) -> Option<O>;
382}
383
384/// A [`Weave`] where the contents of [`Node`] objects can be split and merged.
385pub trait DiscreteWeave<K, N, T>: Weave<K, N, T>
386where
387    K: Hash + Copy + Eq + Ord,
388    N: Node<K, T>,
389    T: DiscreteContents,
390{
391    /// Splits a node with the specified identifier at the given index, creating a new child node with the identifier `new_id`.
392    ///
393    /// Returns `false` if splitting the node failed or the node could not be found.
394    fn split_node(&mut self, id: &K, at: usize, new_id: K) -> bool;
395    /// Merges a node with the specified identifier with its parent, with the newly merged node inheriting the parent's identifier.
396    ///
397    /// Returns the identifier of the merged node if merging was successful.
398    fn merge_with_parent(&mut self, id: &K) -> Option<K>;
399}
400
401/// A [`Weave`] where [`Node`] objects can be meaningfully deduplicated by their contents.
402pub trait DeduplicatableWeave<K, N, T>: Weave<K, N, T>
403where
404    K: Hash + Copy + Eq + Ord,
405    N: Node<K, T>,
406    T: DeduplicatableContents,
407{
408    /// An iterator over the specified node's sibling identifiers which contain contents which are duplicates of the specified node's contents.
409    #[must_use]
410    fn find_duplicates(&self, id: &K) -> impl Iterator<Item = K>;
411}
412
413/// A read-only [`Weave`].
414#[must_use]
415pub trait ImmutableWeave<K, N, T>
416where
417    K: Hash + Copy + Eq + Ord,
418    N: Node<K, T>,
419{
420    /// Mapping between identifiers and nodes.
421    type Nodes;
422    /// Identifiers of root nodes (nodes which do not have any parents).
423    type Roots;
424
425    /// Returns the number of nodes stored within the Weave.
426    #[must_use]
427    fn len(&self) -> usize;
428    /// Returns `true` if the Weave does not contain any nodes.
429    #[must_use]
430    fn is_empty(&self) -> bool;
431    /// Returns a reference to the identifier:node mapping.
432    #[must_use]
433    fn nodes(&self) -> &Self::Nodes;
434    /// Returns a reference to the identifiers of root nodes (nodes which do not have any parents).
435    #[must_use]
436    fn roots(&self) -> &Self::Roots;
437    /// Returns `true` if the Weave contains a node with the specified identifier.
438    #[must_use]
439    fn contains(&self, id: &K) -> bool;
440    /// Returns `true` if the Weave contains an active node (`node.is_active() == true`) with the specified identifier.
441    ///
442    /// The meaning of this value can depend on the underlying Weave implementation.
443    #[must_use]
444    fn contains_active(&self, id: &K) -> bool;
445    /// Returns a reference to the node corresponding to the identifier.
446    #[must_use]
447    fn get_node(&self, id: &K) -> Option<&N>;
448    /// Builds a list of all node identifiers ordered by their positions in the Weave.
449    fn get_ordered_node_identifiers(&self, output: &mut Vec<K>);
450    /// Recursively builds a list of all children of the specified node ordered by their positions in the Weave.
451    fn get_ordered_node_identifiers_from(&self, id: &K, output: &mut Vec<K>);
452    /// Builds the longest contiguous path of active nodes which ends at a root node.
453    fn get_active_path(&self, output: &mut Vec<K>);
454    /// Builds a path through the Weave starting at the specified node and ending at a root node.
455    ///
456    /// In an [`ImmutableActivePathWeave`], this path will preferentially route through the active path.
457    fn get_path_from(&self, id: &K, output: &mut Vec<K>);
458}
459
460/// An [`ImmutableWeave`] containing document-wide metadata.
461pub trait ImmutableMetadataWeave<K, N, T, M>: ImmutableWeave<K, N, T>
462where
463    K: Hash + Copy + Eq + Ord,
464    N: Node<K, T>,
465{
466    /// Returns a reference to the Weave's associated metadata.
467    #[must_use]
468    fn metadata(&self) -> &M;
469}
470
471/// An [`ImmutableWeave`] where nodes can be bookmarked.
472pub trait ImmutableBookmarkableWeave<K, N, T>: ImmutableWeave<K, N, T>
473where
474    K: Hash + Copy + Eq + Ord,
475    N: Node<K, T>,
476{
477    /// Identifiers of bookmarked nodes.
478    type Bookmarks;
479
480    /// Returns a reference to the identifiers of bookmarked nodes.
481    #[must_use]
482    fn bookmarks(&self) -> &Self::Bookmarks;
483    /// Returns `true` if the Weave contains a bookmarked node with the specified identifier.
484    #[must_use]
485    fn contains_bookmark(&self, id: &K) -> bool;
486}
487
488/// An [`ImmutableWeave`] where the ordering of nodes is stable and can be user-defined.
489pub trait ImmutableSortableWeave<K, N, T>: ImmutableWeave<K, N, T>
490where
491    K: Hash + Copy + Eq + Ord,
492    N: Node<K, T>,
493{
494    /// Builds a list of all node identifiers ordered by their positions in the Weave.
495    ///
496    /// Unlike [`ImmutableWeave::get_ordered_node_identifiers`], this function reverses the ordering of node children.
497    fn get_ordered_node_identifiers_mirrored(&self, output: &mut Vec<K>);
498    /// Recursively builds a list of all children of the specified node ordered by their positions in the Weave.
499    ///
500    /// Unlike [`ImmutableWeave::get_ordered_node_identifiers_from`], this function reverses the ordering of node children.
501    fn get_ordered_node_identifiers_mirrored_from(&self, id: &K, output: &mut Vec<K>);
502}
503
504/// An [`ImmutableWeave`] where only one [`Node`] can be considered active at a time.
505pub trait ImmutableActiveSingularWeave<K, N, T>: ImmutableWeave<K, N, T>
506where
507    K: Hash + Copy + Eq + Ord,
508    N: Node<K, T>,
509{
510    /// Returns the active node's identifier, if any.
511    #[must_use]
512    fn active(&self) -> Option<K>;
513}
514
515/// An [`ImmutableWeave`] where every [`Node`] in the active path is always considered active.
516pub trait ImmutableActivePathWeave<K, N, T>: ImmutableWeave<K, N, T>
517where
518    K: Hash + Copy + Eq + Ord,
519    N: Node<K, T>,
520{
521    /// Identifiers of active nodes.
522    type Active;
523
524    /// Returns a reference to the identifiers of active nodes.
525    #[must_use]
526    fn active(&self) -> &Self::Active;
527}
528
529#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
530enum Step<A, B> {
531    Enter(A),
532    Exit(B),
533}
534
535fn topological_sort<'a, K, N, T, S>(
536    nodes: &'a HashMap<K, N, S>,
537    id: &'a K,
538    scratchpad: &mut Vec<K>,
539    identifiers: &mut Vec<K>,
540    identifier_set: &mut HashSet<K, S>,
541    identifier_map: &mut HashMap<K, usize, S>,
542) where
543    K: Hash + Copy + Eq + Ord + 'a,
544    N: Node<K, T> + 'a,
545    <N as Node<K, T>>::From: 'a,
546    <N as Node<K, T>>::To: 'a,
547    &'a N::From: IntoIterator<Item = &'a K, IntoIter: DoubleEndedIterator + ExactSizeIterator>,
548    &'a N::To: IntoIterator<Item = &'a K, IntoIter: DoubleEndedIterator>,
549    S: BuildHasher + Default + Clone,
550{
551    scratchpad.push(*id);
552
553    while let Some(id) = scratchpad.pop() {
554        let node = &nodes[&id];
555
556        if identifier_set.contains(&id)
557            || identifier_map
558                .get(&id)
559                .copied()
560                .unwrap_or_else(|| node.from().into_iter().len())
561                != 0
562        {
563            continue;
564        }
565
566        identifiers.push(id);
567        identifier_set.insert(id);
568
569        for child in node.to().into_iter().rev().copied() {
570            let remaining = identifier_map
571                .entry(child)
572                .or_insert_with(|| nodes[&child].from().into_iter().len());
573            *remaining = remaining.strict_sub(1);
574
575            scratchpad.push(child);
576        }
577    }
578}
579
580fn topological_sort_subgraph<'a, K, N, T, S>(
581    nodes: &'a HashMap<K, N, S>,
582    filter: &impl Fn(&K) -> bool,
583    id: &'a K,
584    scratchpad: &mut Vec<K>,
585    identifiers: &mut Vec<K>,
586    identifier_set: &mut HashSet<K, S>,
587    identifier_map: &mut HashMap<K, usize, S>,
588) where
589    K: Hash + Copy + Eq + Ord + 'a,
590    N: Node<K, T> + 'a,
591    <N as Node<K, T>>::From: 'a,
592    <N as Node<K, T>>::To: 'a,
593    &'a N::From: IntoIterator<Item = &'a K, IntoIter: DoubleEndedIterator>,
594    &'a N::To: IntoIterator<Item = &'a K, IntoIter: DoubleEndedIterator>,
595    S: BuildHasher + Default + Clone,
596{
597    scratchpad.push(*id);
598
599    while let Some(id) = scratchpad.pop() {
600        let node = &nodes[&id];
601
602        if !filter(&id)
603            || identifier_set.contains(&id)
604            || identifier_map.get(&id).copied().unwrap_or_else(|| {
605                node.from()
606                    .into_iter()
607                    .filter(|&parent| filter(parent))
608                    .count()
609            }) != 0
610        {
611            continue;
612        }
613
614        identifiers.push(id);
615        identifier_set.insert(id);
616
617        for child in node.to().into_iter().rev().copied() {
618            let remaining = identifier_map.entry(child).or_insert_with(|| {
619                nodes[&child]
620                    .from()
621                    .into_iter()
622                    .filter(|&parent| filter(parent))
623                    .count()
624            });
625            *remaining = remaining.strict_sub(1);
626
627            scratchpad.push(child);
628        }
629    }
630}
631
632fn topological_sort_subgraph_mirrored<'a, K, N, T, S>(
633    nodes: &'a HashMap<K, N, S>,
634    filter: &impl Fn(&K) -> bool,
635    id: &'a K,
636    scratchpad: &mut Vec<K>,
637    identifiers: &mut Vec<K>,
638    identifier_set: &mut HashSet<K, S>,
639    identifier_map: &mut HashMap<K, usize, S>,
640) where
641    K: Hash + Copy + Eq + Ord + 'a,
642    N: Node<K, T> + 'a,
643    <N as Node<K, T>>::From: 'a,
644    <N as Node<K, T>>::To: 'a,
645    &'a N::From: IntoIterator<Item = &'a K, IntoIter: DoubleEndedIterator>,
646    &'a N::To: IntoIterator<Item = &'a K, IntoIter: DoubleEndedIterator>,
647    S: BuildHasher + Default + Clone,
648{
649    scratchpad.push(*id);
650
651    while let Some(id) = scratchpad.pop() {
652        let node = &nodes[&id];
653
654        if !filter(&id)
655            || identifier_set.contains(&id)
656            || identifier_map.get(&id).copied().unwrap_or_else(|| {
657                node.from()
658                    .into_iter()
659                    .filter(|&parent| filter(parent))
660                    .count()
661            }) != 0
662        {
663            continue;
664        }
665
666        identifiers.push(id);
667        identifier_set.insert(id);
668
669        for child in node.to().into_iter().copied() {
670            let remaining = identifier_map.entry(child).or_insert_with(|| {
671                nodes[&child]
672                    .from()
673                    .into_iter()
674                    .filter(|&parent| filter(parent))
675                    .count()
676            });
677            *remaining = remaining.strict_sub(1);
678
679            scratchpad.push(child);
680        }
681    }
682}
683
684fn topological_sort_mirrored<'a, K, N, T, S>(
685    nodes: &'a HashMap<K, N, S>,
686    id: &'a K,
687    scratchpad: &mut Vec<K>,
688    identifiers: &mut Vec<K>,
689    identifier_set: &mut HashSet<K, S>,
690    identifier_map: &mut HashMap<K, usize, S>,
691) where
692    K: Hash + Copy + Eq + Ord + 'a,
693    N: Node<K, T> + 'a,
694    <N as Node<K, T>>::From: 'a,
695    <N as Node<K, T>>::To: 'a,
696    &'a N::From: IntoIterator<Item = &'a K, IntoIter: DoubleEndedIterator + ExactSizeIterator>,
697    &'a N::To: IntoIterator<Item = &'a K, IntoIter: DoubleEndedIterator>,
698    S: BuildHasher + Default + Clone,
699{
700    scratchpad.push(*id);
701
702    while let Some(id) = scratchpad.pop() {
703        let node = &nodes[&id];
704
705        if identifier_set.contains(&id)
706            || identifier_map
707                .get(&id)
708                .copied()
709                .unwrap_or_else(|| node.from().into_iter().len())
710                != 0
711        {
712            continue;
713        }
714
715        identifiers.push(id);
716        identifier_set.insert(id);
717
718        for child in node.to().into_iter().copied() {
719            let remaining = identifier_map
720                .entry(child)
721                .or_insert_with(|| nodes[&child].from().into_iter().len());
722            *remaining = remaining.strict_sub(1);
723
724            scratchpad.push(child);
725        }
726    }
727}
728
729fn detect_cycles<'a, K, N, T, S>(
730    nodes: &'a HashMap<K, N, S>,
731    roots: impl Iterator<Item = K>,
732    scratchpad: &mut Vec<Step<K, K>>,
733    scratchpad_map: &mut HashMap<K, bool, S>,
734) -> bool
735where
736    K: Hash + Copy + Eq + Ord + 'a,
737    N: Node<K, T> + 'a,
738    <N as Node<K, T>>::From: 'a,
739    <N as Node<K, T>>::To: 'a,
740    &'a N::From: IntoIterator<Item = &'a K, IntoIter: DoubleEndedIterator>,
741    &'a N::To: IntoIterator<Item = &'a K, IntoIter: DoubleEndedIterator + ExactSizeIterator>,
742    S: BuildHasher + Default + Clone,
743{
744    for root in roots {
745        if scratchpad_map.contains_key(&root) {
746            continue;
747        }
748
749        scratchpad.push(Step::Enter(root));
750
751        while let Some(step) = scratchpad.pop() {
752            match step {
753                Step::Enter(id) => {
754                    scratchpad.push(Step::Exit(id));
755
756                    match scratchpad_map.entry(id) {
757                        Entry::Occupied(entry) => {
758                            if !entry.get() {
759                                return true;
760                            }
761                        }
762                        Entry::Vacant(entry) => {
763                            entry.insert_entry(false);
764
765                            scratchpad.extend(
766                                nodes[&id].to().into_iter().rev().copied().map(Step::Enter),
767                            );
768                        }
769                    }
770                }
771                Step::Exit(id) => {
772                    scratchpad_map.insert(id, true);
773                }
774            }
775        }
776    }
777
778    scratchpad_map.len() != nodes.len()
779}
780
781fn shortest_path_to_ancestor<'a, K, N, T, S>(
782    nodes: &'a HashMap<K, N, S>,
783    id: &'a K,
784    target: &impl Fn(&'a N) -> bool,
785    scratchpad: &mut VecDeque<K>,
786    scratchpad_map: &mut HashMap<K, K, S>,
787    scratchpad_set: &mut HashSet<K, S>,
788    path: &mut Vec<K>,
789) where
790    K: Hash + Copy + Eq + Ord + 'a,
791    N: Node<K, T> + 'a,
792    <N as Node<K, T>>::From: 'a,
793    <N as Node<K, T>>::To: 'a,
794    &'a N::From: IntoIterator<Item = &'a K, IntoIter: DoubleEndedIterator>,
795    &'a N::To: IntoIterator<Item = &'a K, IntoIter: DoubleEndedIterator>,
796    S: BuildHasher + Default + Clone,
797{
798    scratchpad.push_front(*id);
799    scratchpad_set.insert(*id);
800
801    while let Some(id) = scratchpad.pop_back() {
802        let node = &nodes[&id];
803
804        if target(node) {
805            scratchpad.clear();
806
807            path.push(id);
808
809            while let Some(child) = scratchpad_map.remove(path.last().unwrap()) {
810                path.push(child);
811            }
812
813            return;
814        }
815
816        for parent in node.from().into_iter().copied() {
817            if scratchpad_set.insert(parent) {
818                scratchpad.push_front(parent);
819                scratchpad_map.insert(parent, id);
820            }
821        }
822    }
823}
824
825fn longest_candidate_path_to_root<'a, K, N, T, S>(
826    nodes: &'a HashMap<K, N, S>,
827    topological_order: &[K],
828    is_candidate: &impl Fn(&K) -> bool,
829    scratchpad_map: &mut HashMap<K, usize, S>,
830    reversed_path: &mut Vec<K>,
831) where
832    K: Hash + Copy + Eq + Ord + 'a,
833    N: Node<K, T> + 'a,
834    <N as Node<K, T>>::From: 'a,
835    <N as Node<K, T>>::To: 'a,
836    &'a N::From: IntoIterator<Item = &'a K, IntoIter: DoubleEndedIterator>,
837    &'a N::To: IntoIterator<Item = &'a K, IntoIter: DoubleEndedIterator>,
838    S: BuildHasher + Default + Clone,
839{
840    let mut longest_distance = None;
841
842    for id in topological_order {
843        if !is_candidate(id) {
844            continue;
845        }
846
847        let node = &nodes[id];
848        let distance = if node.from().into_iter().next().is_none() {
849            Some(0)
850        } else {
851            node.from()
852                .into_iter()
853                .filter_map(|parent| scratchpad_map.get(parent).copied())
854                .max()
855                .map(|l| l.strict_add(1))
856        };
857
858        if let Some(distance) = distance {
859            scratchpad_map.insert(*id, distance);
860
861            if longest_distance.is_none_or(|(value, _)| distance > value) {
862                longest_distance = Some((distance, id));
863            }
864        }
865    }
866
867    let mut current = longest_distance.map(|(_, id)| id);
868
869    while let Some(id) = current {
870        reversed_path.push(*id);
871
872        current = nodes[id]
873            .from()
874            .into_iter()
875            .filter(|id| scratchpad_map.contains_key(*id))
876            .min_by_key(|id| Reverse(scratchpad_map[*id]));
877    }
878}
879
880fn ancestor_subgraph<'a, K, N, T, S>(
881    nodes: &'a HashMap<K, N, S>,
882    id: K,
883    scratchpad: &mut Vec<K>,
884    identifiers: &mut HashSet<K, S>,
885) where
886    K: Hash + Copy + Eq + Ord + 'a,
887    N: Node<K, T>,
888    <N as Node<K, T>>::From: 'a,
889    <N as Node<K, T>>::To: 'a,
890    &'a N::From: IntoIterator<Item = &'a K, IntoIter: DoubleEndedIterator>,
891    &'a N::To: IntoIterator<Item = &'a K, IntoIter: DoubleEndedIterator>,
892    S: BuildHasher + Default + Clone,
893{
894    scratchpad.push(id);
895
896    while let Some(id) = scratchpad.pop() {
897        if identifiers.insert(id) {
898            scratchpad.extend(nodes[&id].from().into_iter().rev().copied());
899        }
900    }
901}
902
903fn descendant_subgraph<'a, K, N, T, S>(
904    nodes: &'a HashMap<K, N, S>,
905    id: K,
906    scratchpad: &mut Vec<K>,
907    identifiers: &mut HashSet<K, S>,
908) where
909    K: Hash + Copy + Eq + Ord + 'a,
910    N: Node<K, T>,
911    <N as Node<K, T>>::From: 'a,
912    <N as Node<K, T>>::To: 'a,
913    &'a N::From: IntoIterator<Item = &'a K, IntoIter: DoubleEndedIterator>,
914    &'a N::To: IntoIterator<Item = &'a K, IntoIter: DoubleEndedIterator>,
915    S: BuildHasher + Default + Clone,
916{
917    scratchpad.push(id);
918
919    while let Some(id) = scratchpad.pop() {
920        if identifiers.insert(id) {
921            scratchpad.extend(nodes[&id].to().into_iter().rev().copied());
922        }
923    }
924}
universal_weave/lib.rs

universal_weave/
lib.rs
