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

universal_weave/
lib.rs
