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

universal_weave/
lib.rs
