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

universal_weave/
lib.rs
