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

universal_weave/
lib.rs
