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//! - [`DependentWeave`](dependent::DependentWeave) - A tree-based [`Weave`] where each [`Node`] depends on the contents of the previous Node.
5//!     - [`DependentLoroWeave`](dependent::loro::DependentLoroWeave) - A [`DependentWeave`](dependent::DependentWeave) wrapper which adds collaborative editing using the [`loro`] CRDT library (requires `rkyv` and `loro` features to be enabled).
6//! - [`IndependentWeave`](independent::IndependentWeave) - A DAG-based [`Weave`] where each [`Node`] does *not* depend on the contents of the previous Node.
7//!
8//! Operations on the built-in [`Weave`] implementations always preserve node ordering through the use of [`IndexSet`](indexmap::IndexSet), and (non-tail) insertion and removal operations on ordered sets can have a worst-case time complexity of O(n).
9//!
10//! Efficient (de)serialization is supported using `rkyv` and `serde`. Basic functionality for versioning serialized data is provided by [`VersionedBytes`](versioning::VersionedBytes) (requires `rkyv` feature to be enabled).
11
12#![no_std]
13#![forbid(non_ascii_idents)]
14#![warn(missing_docs)]
15#![warn(let_underscore)]
16#![warn(unsafe_code)]
17#![warn(clippy::pedantic)]
18#![warn(clippy::cargo)]
19#![allow(clippy::multiple_crate_versions, reason = "Unresolvable")]
20#![warn(clippy::nursery)]
21#![warn(clippy::restriction)]
22#![allow(clippy::blanket_clippy_restriction_lints, reason = "Conflicting lint")]
23#![allow(clippy::allow_attributes, reason = "Conflicting lint")]
24#![allow(clippy::pattern_type_mismatch, reason = "Conflicting lint")]
25#![allow(clippy::separated_literal_suffix, reason = "Conflicting lint")]
26#![allow(clippy::semicolon_outside_block, reason = "Conflicting lint")]
27#![allow(
28    clippy::field_scoped_visibility_modifiers,
29    reason = "Used by IndependentWeave::from()"
30)]
31#![allow(
32    clippy::missing_inline_in_public_items,
33    reason = "Reasonable candidates have already been inlined"
34)]
35#![allow(clippy::inline_always, reason = "Performance")]
36#![allow(clippy::exhaustive_enums, reason = "API")]
37#![allow(clippy::exhaustive_structs, reason = "API")]
38#![allow(clippy::little_endian_bytes, reason = "API")]
39#![allow(clippy::partial_pub_fields, reason = "API")]
40#![allow(clippy::pub_use, reason = "API")]
41#![allow(clippy::arbitrary_source_item_ordering, reason = "Readability")]
42#![allow(clippy::question_mark_used, reason = "Readability")]
43#![allow(clippy::single_call_fn, reason = "Readability")]
44#![allow(clippy::single_char_lifetime_names, reason = "Readability")]
45#![allow(clippy::else_if_without_else, reason = "Style")]
46#![allow(clippy::if_then_some_else_none, reason = "Style")]
47#![allow(clippy::implicit_return, reason = "Style")]
48#![allow(clippy::min_ident_chars, reason = "Style")]
49#![allow(clippy::mod_module_files, reason = "Style")]
50#![allow(clippy::module_name_repetitions, reason = "Style")]
51#![allow(clippy::multiple_inherent_impl, reason = "Style")]
52#![allow(clippy::try_err, reason = "Style")]
53#![allow(clippy::allow_attributes_without_reason)] // TODO
54#![allow(clippy::indexing_slicing)] // TODO
55#![allow(clippy::unwrap_in_result)] // TODO
56#![allow(clippy::unwrap_used)] // TODO
57#![allow(clippy::missing_docs_in_private_items)] // TODO
58#![allow(clippy::shadow_unrelated)] // TODO
59#![allow(clippy::shadow_reuse)] // TODO
60#![allow(clippy::shadow_same)] // TODO
61
62/*
63
64Testing notes:
65- When running multiple tests, use `cargo nextest run` instead of `cargo test`
66- Test building for no_std using `cargo build --target=aarch64-unknown-none --no-default-features --features serde,rkyv,legacy`
67- The following tests continue to function in release mode:
68    - layout_reference
69    - layout_dependent
70    - layout_independent
71    - archived_dependent
72    - archived_independent
73    - dependent_behavior_unchanged
74    - independent_behavior_unchanged
75    - independent_extends_dependent
76
77*/
78
79mod contract;
80pub mod dependent;
81pub mod independent;
82pub mod wrappers;
83
84#[cfg(all(
85    feature = "layout",
86    any(target_pointer_width = "32", target_pointer_width = "64")
87))]
88pub mod layout;
89
90#[cfg(feature = "rkyv")]
91pub mod versioning;
92
93pub use contracts;
94pub use hashbrown;
95pub use indexmap;
96
97#[cfg(feature = "layout")]
98pub use glam;
99
100#[cfg(feature = "layout")]
101pub use tinyvec;
102
103#[cfg(feature = "rkyv")]
104pub use rkyv;
105
106#[cfg(feature = "serde")]
107pub use serde;
108
109#[cfg(feature = "loro")]
110pub use loro;
111
112extern crate alloc;
113
114use alloc::vec::Vec;
115use core::{
116    cmp::{Ordering, Reverse},
117    hash::{BuildHasher, Hash},
118};
119
120use hashbrown::{HashMap, hash_map::Entry};
121use scratchpads::{ScratchpadMap, ScratchpadSet, ScratchpadVec};
122
123#[cfg(feature = "rkyv")]
124use rkyv::collections::swiss_table::{ArchivedHashMap, ArchivedIndexSet};
125
126/// An item within a [`Weave`] which can be connected to other items.
127#[must_use]
128pub trait Node<K, T>
129where
130    K: Hash + Copy + Eq + Ord,
131{
132    /// Identifiers corresponding to the node's parents without duplicates.
133    type From;
134    /// Identifiers corresponding to the node's children without duplicates.
135    type To;
136
137    /// Returns the node's unique identifier.
138    #[must_use]
139    fn id(&self) -> K;
140    /// Returns a reference to the identifiers corresponding to the node's parents.
141    #[must_use]
142    fn from(&self) -> &Self::From;
143    /// Returns a reference to the identifiers corresponding to the node's children.
144    #[must_use]
145    fn to(&self) -> &Self::To;
146    /// Returns `true` if the node is considered active.
147    ///
148    /// The meaning of this value can depend on the underlying [`Weave`] implementation.
149    #[must_use]
150    fn is_active(&self) -> bool;
151    /// Returns a reference to the node's contents.
152    #[must_use]
153    fn contents(&self) -> &T;
154}
155
156/// [`Node`] contents which can be split apart or merged together.
157pub trait DiscreteContents: Sized {
158    /// Splits the item at specified index.
159    ///
160    /// If splitting the item fails, the original contents are returned.
161    fn split(self, at: usize) -> DiscreteContentResult<Self>;
162    /// Merges two items together.
163    ///
164    /// If merging the two items fails, the original contents are returned in the order they were specified in.
165    fn merge(self, value: Self) -> DiscreteContentResult<Self>;
166}
167
168/// A type representing the results of an action on a [`DiscreteContents`] item.
169#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
170#[allow(missing_docs, reason = "Enum items are self-explanatory")]
171#[must_use]
172pub enum DiscreteContentResult<T> {
173    One(T),
174    Two(T, T),
175}
176
177impl DiscreteContents for () {
178    fn split(self, _at: usize) -> DiscreteContentResult<Self> {
179        DiscreteContentResult::Two((), ())
180    }
181    fn merge(self, _value: Self) -> DiscreteContentResult<Self> {
182        DiscreteContentResult::One(())
183    }
184}
185
186/// [`Node`] contents which do not depend on the contents of other [`Node`] objects in order to be meaningful.
187pub trait IndependentContents {}
188
189impl IndependentContents for () {}
190
191/// [`Node`] contents which can be meaningfully deduplicated.
192///
193/// Deduplication must be symmetric: `a.is_duplicate_of(b)` implies `b.is_duplicate_of(a)`.
194pub trait DeduplicatableContents {
195    /// Tests if `self` and `other` should be considered duplicates of each other.
196    #[must_use]
197    fn is_duplicate_of(&self, other: &Self) -> bool;
198}
199
200/// A document linking together multiple [`Node`] objects without cyclical links.
201///
202/// # Deserialization
203///
204/// If a Weave implementation supports deserialization, it must validate internal consistency during the deserialization process in a way which is robust to untrusted inputs.
205///
206/// # Panics
207///
208/// All panics should be assumed to leave the Weave in a malformed state unless otherwise specified by the implementation.
209#[must_use]
210pub trait Weave<K, N, T>
211where
212    K: Hash + Copy + Eq + Ord,
213    N: Node<K, T>,
214{
215    /// Mapping between identifiers and nodes.
216    type Nodes;
217    /// Identifiers of root nodes (nodes which do not have any parents) without duplicates.
218    type Roots;
219
220    /// Returns the number of nodes stored within the Weave.
221    #[must_use]
222    fn len(&self) -> usize;
223    /// Returns `true` if the Weave does not contain any nodes.
224    #[must_use]
225    fn is_empty(&self) -> bool;
226    /// Returns a reference to the identifier:node mapping.
227    #[must_use]
228    fn nodes(&self) -> &Self::Nodes;
229    /// Returns a reference to the identifiers of root nodes (nodes which do not have any parents).
230    #[must_use]
231    fn roots(&self) -> &Self::Roots;
232    /// Returns `true` if the Weave contains a node with the specified identifier.
233    #[must_use]
234    fn contains(&self, id: &K) -> bool;
235    /// Returns `true` if the Weave contains an active node (`node.is_active() == true`) with the specified identifier.
236    ///
237    /// The meaning of this value can depend on the underlying Weave implementation.
238    #[must_use]
239    fn contains_active(&self, id: &K) -> bool;
240    /// Returns a reference to the node corresponding to the identifier.
241    #[must_use]
242    fn get(&self, id: &K) -> Option<&N>;
243    /// Convenience method for `self.get(id).map(Node::from)`.
244    #[must_use]
245    fn get_parents(&self, id: &K) -> Option<&N::From>;
246    /// Convenience method for `self.get(id).map(Node::to)`.
247    #[must_use]
248    fn get_children(&self, id: &K) -> Option<&N::To>;
249    /// Convenience method for `self.get(id).map(Node::contents)`.
250    #[must_use]
251    fn get_contents(&self, id: &K) -> Option<&T>;
252    /// Builds a list of all node identifiers ordered by their positions in the Weave without duplicates.
253    fn get_ordered_identifiers(&mut self, output: &mut Vec<K>);
254    /// Recursively builds a list of all children of the specified node ordered by their positions in the Weave without duplicates.
255    ///
256    /// The returned list starts with the identifier of the specified node.
257    fn get_ordered_identifiers_from(&mut self, id: &K, output: &mut Vec<K>);
258    /// Builds a path through the Weave starting at the deepest active node and ending at a root node.
259    ///
260    /// In an [`ActivePathWeave`], this path will be the longest contiguous path of active nodes.
261    fn get_active_path(&mut self, output: &mut Vec<K>);
262    /// Builds a path through the Weave starting at the specified node and ending at a root node.
263    ///
264    /// In an [`ActivePathWeave`], this path will preferentially route through the active path.
265    fn get_path_from(&mut self, id: &K, output: &mut Vec<K>);
266    /// Inserts a node into the Weave, returning `true` if the insertion was successful.
267    ///
268    /// This function may change the active status of nodes if it is necessary to preserve internal consistency.
269    fn insert(&mut self, node: N) -> bool;
270    /// Sets the active status of a node with the specified identifier.
271    ///
272    /// This function may change the active status of other nodes in an implementation-specific manner if it is necessary to preserve internal consistency.
273    fn set_active(&mut self, id: &K, value: bool) -> bool;
274    /// Removes a node with the specified identifier, returning its value if it was present within the Weave.
275    ///
276    /// This function may remove or update other nodes if it is necessary to preserve internal consistency.
277    ///
278    /// This function uses the same removal logic as [`Weave::remove_tracked`].
279    fn remove(&mut self, id: &K) -> Option<N>;
280    /// Removes a node with the specified identifier, returning `true` if it was present within the Weave.
281    ///
282    /// 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.
283    ///
284    /// # Panics
285    ///
286    /// May panic if `on_removal` panics.
287    fn remove_tracked(&mut self, id: &K, on_removal: impl FnMut(N)) -> bool;
288    /// Removes all nodes from the Weave.
289    ///
290    /// In a [`MetadataWeave`], the associated metadata is left unchanged.
291    fn clear(&mut self);
292}
293
294/// A [`Weave`] containing document-wide metadata.
295///
296/// # Panics
297///
298/// All panics should be assumed to leave the Weave in a malformed state unless otherwise specified by the implementation.
299pub trait MetadataWeave<K, N, T, M>: Weave<K, N, T>
300where
301    K: Hash + Copy + Eq + Ord,
302    N: Node<K, T>,
303{
304    /// Returns a reference to the Weave's associated metadata.
305    #[must_use]
306    fn metadata(&self) -> &M;
307    /// Mutable access to the Weave's associated metadata.
308    ///
309    /// # Panics
310    ///
311    /// May panic if `callback` panics.
312    fn metadata_mut<O>(&mut self, callback: impl FnOnce(&mut M) -> O) -> O;
313}
314
315/// A [`Weave`] where nodes can be bookmarked.
316pub trait BookmarkableWeave<K, N, T>: Weave<K, N, T>
317where
318    K: Hash + Copy + Eq + Ord,
319    N: Node<K, T>,
320{
321    /// Identifiers of bookmarked nodes.
322    type Bookmarks;
323
324    /// Returns a reference to the identifiers of bookmarked nodes.
325    #[must_use]
326    fn bookmarks(&self) -> &Self::Bookmarks;
327    /// Returns `true` if the Weave contains a bookmarked node with the specified identifier.
328    #[must_use]
329    fn contains_bookmark(&self, id: &K) -> bool;
330    /// Sets the bookmarked status of a node with the specified identifier.
331    fn set_bookmarked(&mut self, id: &K, value: bool) -> bool;
332}
333
334/// A [`Weave`] where the ordering of nodes is stable and can be user-defined.
335///
336/// # Panics
337///
338/// All panics should be assumed to leave the Weave in a malformed state unless otherwise specified by the implementation.
339pub trait SortableWeave<K, N, T>: Weave<K, N, T>
340where
341    K: Hash + Copy + Eq + Ord,
342    N: Node<K, T>,
343{
344    /// Sorts the child nodes of a parent node with the specified identifier using the comparison function `cmp`.
345    ///
346    /// # Panics
347    ///
348    /// May panic if `cmp` does not implement a [total order](https://en.wikipedia.org/wiki/Total_order), or if `cmp` itself panics.
349    fn sort_children_by(&mut self, id: &K, cmp: impl FnMut(&N, &N) -> Ordering) -> bool;
350    /// Sorts the identifiers of a parent node's children with the specified identifier using the comparison function `cmp`.
351    ///
352    /// # Panics
353    ///
354    /// May panic if `cmp` does not implement a [total order](https://en.wikipedia.org/wiki/Total_order), or if `cmp` itself panics.
355    fn sort_children_by_id(&mut self, id: &K, cmp: impl FnMut(&K, &K) -> Ordering) -> bool;
356    /// Sorts root nodes (nodes which do not have any parents) using the comparison function `cmp`.
357    ///
358    /// # Panics
359    ///
360    /// May panic if `cmp` does not implement a [total order](https://en.wikipedia.org/wiki/Total_order), or if `cmp` itself panics.
361    fn sort_roots_by(&mut self, cmp: impl FnMut(&N, &N) -> Ordering);
362    /// Sorts the identifiers of root nodes (nodes which do not have any parents) using the comparison function `cmp`.
363    ///
364    /// # Panics
365    ///
366    /// May panic if `cmp` does not implement a [total order](https://en.wikipedia.org/wiki/Total_order), or if `cmp` itself panics.
367    fn sort_roots_by_id(&mut self, cmp: impl FnMut(&K, &K) -> Ordering);
368}
369
370/// A [`Weave`] where the ordering of bookmarked nodes is stable and can be user-defined.
371///
372/// # Panics
373///
374/// All panics should be assumed to leave the Weave in a malformed state unless otherwise specified by the implementation.
375pub trait SortableBookmarkableWeave<K, N, T>:
376    BookmarkableWeave<K, N, T> + SortableWeave<K, N, T>
377where
378    K: Hash + Copy + Eq + Ord,
379    N: Node<K, T>,
380{
381    /// Sorts bookmarked nodes using the comparison function `cmp`.
382    ///
383    /// # Panics
384    ///
385    /// May panic if `cmp` does not implement a [total order](https://en.wikipedia.org/wiki/Total_order), or if `cmp` itself panics.
386    fn sort_bookmarks_by(&mut self, cmp: impl FnMut(&N, &N) -> Ordering);
387    /// Sorts the identifiers of bookmarked nodes using the comparison function `cmp`.
388    ///
389    /// # Panics
390    ///
391    /// May panic if `cmp` does not implement a [total order](https://en.wikipedia.org/wiki/Total_order), or if `cmp` itself panics.
392    fn sort_bookmarks_by_id(&mut self, cmp: impl FnMut(&K, &K) -> Ordering);
393}
394
395/// A [`Weave`] where only one [`Node`] can be considered active at a time.
396pub trait ActiveSingularWeave<K, N, T>: Weave<K, N, T>
397where
398    K: Hash + Copy + Eq + Ord,
399    N: Node<K, T>,
400{
401    /// Returns the active node's identifier, if any.
402    #[must_use]
403    fn active(&self) -> Option<K>;
404}
405
406/// A [`Weave`] where every [`Node`] in the active path is always considered active.
407pub trait ActivePathWeave<K, N, T>: Weave<K, N, T>
408where
409    K: Hash + Copy + Eq + Ord,
410    N: Node<K, T>,
411{
412    /// Identifiers of active nodes.
413    type Active;
414
415    /// Returns a reference to the identifiers of active nodes.
416    #[must_use]
417    fn active(&self) -> &Self::Active;
418    /// Replaces the currently active path with the specified set of node IDs.
419    ///
420    /// If the new active path would result in internal inconsistency, this function will correct the path in an implementation-specific manner.
421    fn set_active_path(&mut self, active: impl Iterator<Item = K>);
422}
423
424/// A [`Weave`] where [`Node`] objects do not depend on their parents in order to be meaningful.
425pub trait IndependentWeave<K, N, T>: Weave<K, N, T> + SemiIndependentWeave<K, N, T>
426where
427    K: Hash + Copy + Eq + Ord,
428    N: Node<K, T>,
429    T: IndependentContents,
430{
431    /// Moves a node with the specified identifier to a new set of parent nodes, returning `true` if the move was successful.
432    ///
433    /// This function may change the active status of other nodes if it is necessary to preserve internal consistency.
434    fn move_to(&mut self, id: &K, new_parents: &[K]) -> bool;
435}
436
437/// A [`Weave`] where [`Node`] objects do not depend on the *contents* of their parents in order to be meaningful.
438///
439/// # Panics
440///
441/// All panics should be assumed to leave the Weave in a malformed state unless otherwise specified by the implementation.
442pub trait SemiIndependentWeave<K, N, T>: Weave<K, N, T>
443where
444    K: Hash + Copy + Eq + Ord,
445    N: Node<K, T>,
446    T: IndependentContents,
447{
448    /// Mutable access to the contents of a node with the specified identifier.
449    ///
450    /// Returns `Some` if the node's contents were successfully updated.
451    ///
452    /// # Panics
453    ///
454    /// May panic if `callback` panics.
455    #[must_use]
456    fn get_contents_mut<O>(&mut self, id: &K, callback: impl FnOnce(&mut T) -> O) -> Option<O>;
457}
458
459/// A [`Weave`] where the contents of [`Node`] objects can be split and merged.
460///
461/// # Panics
462///
463/// All panics should be assumed to leave the Weave in a malformed state unless otherwise specified by the implementation.
464pub trait DiscreteWeave<K, N, T>: Weave<K, N, T>
465where
466    K: Hash + Copy + Eq + Ord,
467    N: Node<K, T>,
468    T: DiscreteContents,
469{
470    /// Splits a node with the specified identifier at the given index, creating a new child node with the identifier `new_id`.
471    ///
472    /// If the target node is at the end of the active path, the right side of the split will be inactive.
473    ///
474    /// Returns `false` if splitting the node failed.
475    ///
476    /// # Panics
477    ///
478    /// May panic if `T::split` panics.
479    fn split(&mut self, id: &K, at: usize, new_id: K) -> bool;
480    /// Merges a node with the specified identifier with its parent, with the newly merged node inheriting the parent's identifier.
481    ///
482    /// Returns the identifier of the merged node if merging was successful.
483    ///
484    /// # Panics
485    ///
486    /// May panic if `T::merge` panics.
487    fn merge_with_parent(&mut self, id: &K) -> Option<K>;
488}
489
490/// A geometric item within an arrangement of a Weave's content.
491#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
492pub enum LayoutItem<K, V, P> {
493    /// Computed geometry for a [`Node`].
494    Node {
495        /// Node identifier.
496        id: K,
497        /// Node center position.
498        center: V,
499        /// Node size.
500        size: V,
501    },
502    /// Computed geometry for a connection between [`Node`]s.
503    Polyline {
504        /// Parent node where the connection starts.
505        from: K,
506        /// Child node where the connection ends.
507        to: K,
508        /// Points for a polyline routed between the two nodes.
509        points: P,
510    },
511}
512
513/// An algorithm which arranges a [`Weave`]'s content for graphical rendering in an efficiently accessible form.
514///
515/// # Panics
516///
517/// All panics should be assumed to leave the Layouter and Weave in a malformed state unless otherwise specified by the implementation.
518pub trait Layouter<W, K, N, T, V, P>
519where
520    W: Weave<K, N, T>,
521    K: Hash + Copy + Eq + Ord,
522    N: Node<K, T>,
523{
524    /// Arranges a [`Weave`]'s content for graphical rendering using a closure which maps [`Node`]s to their dimensions.
525    ///
526    /// # Panics
527    ///
528    /// Panics if the [`Weave`]'s content could not be arranged due to an unsatisfiable constraint or numerical overflow.
529    ///
530    /// May panic if `map` panics or if the underlying [`Weave`] is improperly implemented.
531    fn layout(&mut self, weave: &mut W, sizes: impl FnMut(&K) -> V);
532    /// Returns the size of the bounding box enclosing the arrangement's content.
533    fn size(&self) -> V;
534    /// Returns [`LayoutItem`]s within the specified bounds in the order that they should be rendered.
535    fn view(&mut self, min: V, max: V, callback: impl FnMut(LayoutItem<K, V, P>));
536}
537
538/// A read-only [`Weave`].
539#[must_use]
540pub trait ImmutableWeave<K, N, T>
541where
542    K: Hash + Copy + Eq + Ord,
543    N: Node<K, T>,
544{
545    /// Mapping between identifiers and nodes.
546    type Nodes;
547    /// Identifiers of root nodes (nodes which do not have any parents) without duplicates.
548    type Roots;
549
550    /// Returns the number of nodes stored within the Weave.
551    #[must_use]
552    fn len(&self) -> usize;
553    /// Returns `true` if the Weave does not contain any nodes.
554    #[must_use]
555    fn is_empty(&self) -> bool;
556    /// Returns a reference to the identifier:node mapping.
557    #[must_use]
558    fn nodes(&self) -> &Self::Nodes;
559    /// Returns a reference to the identifiers of root nodes (nodes which do not have any parents).
560    #[must_use]
561    fn roots(&self) -> &Self::Roots;
562    /// Returns `true` if the Weave contains a node with the specified identifier.
563    #[must_use]
564    fn contains(&self, id: &K) -> bool;
565    /// Returns `true` if the Weave contains an active node (`node.is_active() == true`) with the specified identifier.
566    ///
567    /// The meaning of this value can depend on the underlying Weave implementation.
568    #[must_use]
569    fn contains_active(&self, id: &K) -> bool;
570    /// Returns a reference to the node corresponding to the identifier.
571    #[must_use]
572    fn get(&self, id: &K) -> Option<&N>;
573    /// Convenience method for `self.get(id).map(Node::from)`.
574    #[must_use]
575    fn get_parents(&self, id: &K) -> Option<&N::From>;
576    /// Convenience method for `self.get(id).map(Node::to)`.
577    #[must_use]
578    fn get_children(&self, id: &K) -> Option<&N::To>;
579    /// Convenience method for `self.get(id).map(Node::contents)`.
580    #[must_use]
581    fn get_contents(&self, id: &K) -> Option<&T>;
582    /// Builds a list of all node identifiers ordered by their positions in the Weave without duplicates.
583    fn get_ordered_identifiers(&self, output: &mut Vec<K>);
584    /// Recursively builds a list of all children of the specified node ordered by their positions in the Weave without duplicates.
585    ///
586    /// The returned list starts with the identifier of the specified node.
587    fn get_ordered_identifiers_from(&self, id: &K, output: &mut Vec<K>);
588    /// Builds a path through the Weave starting at the deepest active node and ending at a root node.
589    ///
590    /// In an [`ImmutableActivePathWeave`], this path will be the longest contiguous path of active nodes.
591    fn get_active_path(&self, output: &mut Vec<K>);
592    /// Builds a path through the Weave starting at the specified node and ending at a root node.
593    ///
594    /// In an [`ImmutableActivePathWeave`], this path will preferentially route through the active path.
595    fn get_path_from(&self, id: &K, output: &mut Vec<K>);
596}
597
598/// An [`ImmutableWeave`] containing document-wide metadata.
599pub trait ImmutableMetadataWeave<K, N, T, M>: ImmutableWeave<K, N, T>
600where
601    K: Hash + Copy + Eq + Ord,
602    N: Node<K, T>,
603{
604    /// Returns a reference to the Weave's associated metadata.
605    #[must_use]
606    fn metadata(&self) -> &M;
607}
608
609/// An [`ImmutableWeave`] where nodes can be bookmarked.
610pub trait ImmutableBookmarkableWeave<K, N, T>: ImmutableWeave<K, N, T>
611where
612    K: Hash + Copy + Eq + Ord,
613    N: Node<K, T>,
614{
615    /// Identifiers of bookmarked nodes.
616    type Bookmarks;
617
618    /// Returns a reference to the identifiers of bookmarked nodes.
619    #[must_use]
620    fn bookmarks(&self) -> &Self::Bookmarks;
621    /// Returns `true` if the Weave contains a bookmarked node with the specified identifier.
622    #[must_use]
623    fn contains_bookmark(&self, id: &K) -> bool;
624}
625
626/// An [`ImmutableWeave`] where only one [`Node`] can be considered active at a time.
627pub trait ImmutableActiveSingularWeave<K, N, T>: ImmutableWeave<K, N, T>
628where
629    K: Hash + Copy + Eq + Ord,
630    N: Node<K, T>,
631{
632    /// Returns the active node's identifier, if any.
633    #[must_use]
634    fn active(&self) -> Option<K>;
635}
636
637/// An [`ImmutableWeave`] where every [`Node`] in the active path is always considered active.
638pub trait ImmutableActivePathWeave<K, N, T>: ImmutableWeave<K, N, T>
639where
640    K: Hash + Copy + Eq + Ord,
641    N: Node<K, T>,
642{
643    /// Identifiers of active nodes.
644    type Active;
645
646    /// Returns a reference to the identifiers of active nodes.
647    #[must_use]
648    fn active(&self) -> &Self::Active;
649}
650
651/// An algorithm which arranges an [`ImmutableWeave`]'s content for graphical rendering in an efficiently accessible form.
652///
653/// # Panics
654///
655/// All panics should be assumed to leave the Layouter in a malformed state unless otherwise specified by the implementation.
656pub trait ImmutableLayouter<W, K, N, T, V, P>
657where
658    W: ImmutableWeave<K, N, T>,
659    K: Hash + Copy + Eq + Ord,
660    N: Node<K, T>,
661{
662    /// Arranges an [`ImmutableWeave`]'s content for graphical rendering using a closure which maps [`Node`]s to their dimensions.
663    ///
664    /// # Panics
665    ///
666    /// Panics if the [`ImmutableWeave`]'s content could not be arranged due to an unsatisfiable constraint or numerical overflow.
667    ///
668    /// May panic if `map` panics or if the underlying [`ImmutableWeave`] is improperly implemented.
669    fn layout(&mut self, weave: &W, sizes: impl FnMut(&K) -> V);
670    /// Returns the size of the bounding box enclosing the arrangement's content.
671    fn size(&self) -> V;
672    /// Returns [`LayoutItem`]s within the specified bounds in the order that they should be rendered.
673    fn view(&mut self, min: V, max: V, callback: impl FnMut(LayoutItem<K, V, P>));
674}
675
676#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
677enum Step<A, B> {
678    Enter(A),
679    Exit(B),
680}
681
682fn topological_sort<'a, K, N, T, S>(
683    nodes: &'a HashMap<K, N, S>,
684    roots: impl DoubleEndedIterator<Item = K>,
685    stack: &mut ScratchpadVec<'_, K>,
686    mut identifier_callback: impl FnMut(K),
687    identifier_map: &mut ScratchpadMap<'_, K, usize, S>,
688) where
689    K: Hash + Copy + Eq + Ord + 'a,
690    N: Node<K, T> + 'a,
691    <N as Node<K, T>>::From: 'a,
692    <N as Node<K, T>>::To: 'a,
693    &'a N::From: IntoIterator<Item = &'a K, IntoIter: DoubleEndedIterator + ExactSizeIterator>,
694    &'a N::To: IntoIterator<Item = &'a K, IntoIter: DoubleEndedIterator>,
695    S: BuildHasher + Default + Clone,
696{
697    identifier_map.extend(nodes.iter().map(|(&k, n)| (k, n.from().into_iter().len())));
698
699    stack.extend(roots.rev());
700
701    while let Some(id) = stack.pop() {
702        identifier_callback(id);
703
704        for child in nodes[&id].to().into_iter().rev().copied() {
705            let remaining = identifier_map.get_mut(&child).unwrap();
706            #[allow(clippy::arithmetic_side_effects, reason = "Can never underflow")]
707            {
708                *remaining -= 1;
709            }
710
711            if *remaining == 0 {
712                stack.push(child);
713            }
714        }
715    }
716}
717
718#[cfg(feature = "rkyv")]
719fn archived_topological_sort<'a, K, N, T, S>(
720    nodes: &'a ArchivedHashMap<K, N>,
721    roots: &'a ArchivedIndexSet<K>,
722    stack: &mut ScratchpadVec<'_, K>,
723    mut identifier_callback: impl FnMut(K),
724    identifier_map: &mut ScratchpadMap<'_, K, usize, S>,
725) where
726    K: Hash + Copy + Eq + Ord + 'a,
727    N: Node<K, T, From = ArchivedIndexSet<K>, To = ArchivedIndexSet<K>> + 'a,
728    S: BuildHasher + Default + Clone,
729{
730    identifier_map.extend(nodes.iter().map(|(&k, n)| (k, n.from().len())));
731
732    stack.extend(archived_set_reverse_order(roots));
733
734    while let Some(id) = stack.pop() {
735        identifier_callback(id);
736
737        for child in archived_set_reverse_order(nodes[&id].to()).copied() {
738            let remaining = identifier_map.get_mut(&child).unwrap();
739            #[allow(clippy::arithmetic_side_effects, reason = "Can never underflow")]
740            {
741                *remaining -= 1;
742            }
743
744            if *remaining == 0 {
745                stack.push(child);
746            }
747        }
748    }
749}
750
751fn topological_sort_subgraph<'a, K, N, T, S>(
752    nodes: &'a HashMap<K, N, S>,
753    filter: impl Fn(&K) -> bool,
754    subgraph_root: K,
755    stack: &mut ScratchpadVec<'_, K>,
756    mut identifier_callback: impl FnMut(K),
757    identifier_map: &mut ScratchpadMap<'_, K, usize, S>,
758) where
759    K: Hash + Copy + Eq + Ord + 'a,
760    N: Node<K, T> + 'a,
761    <N as Node<K, T>>::From: 'a,
762    <N as Node<K, T>>::To: 'a,
763    &'a N::From: IntoIterator<Item = &'a K, IntoIter: DoubleEndedIterator>,
764    &'a N::To: IntoIterator<Item = &'a K, IntoIter: DoubleEndedIterator>,
765    S: BuildHasher + Default + Clone,
766{
767    /*if filter(id)
768        && !identifier_map.contains_key(id)
769        && nodes[id]
770            .from()
771            .into_iter()
772            .filter(|&parent| filter(parent))
773            .count()
774            == 0
775    {
776        stack.push(*id);
777    }*/
778
779    stack.push(subgraph_root);
780
781    while let Some(id) = stack.pop() {
782        identifier_callback(id);
783
784        for child in nodes[&id].to().into_iter().rev().copied() {
785            if !filter(&child) {
786                continue;
787            }
788
789            let remaining = identifier_map.entry(child).or_insert_with(|| {
790                nodes[&child]
791                    .from()
792                    .into_iter()
793                    .filter(|&parent| filter(parent))
794                    .count()
795            });
796            #[allow(clippy::arithmetic_side_effects, reason = "Can never underflow")]
797            {
798                *remaining -= 1;
799            }
800
801            if *remaining == 0 {
802                stack.push(child);
803            }
804        }
805    }
806}
807
808#[cfg(feature = "rkyv")]
809fn archived_topological_sort_subgraph<'a, K, N, T, S>(
810    nodes: &'a ArchivedHashMap<K, N>,
811    filter: impl Fn(&K) -> bool,
812    subgraph_root: K,
813    stack: &mut ScratchpadVec<'_, K>,
814    mut identifier_callback: impl FnMut(K),
815    identifier_map: &mut ScratchpadMap<'_, K, usize, S>,
816) where
817    K: Hash + Copy + Eq + Ord + 'a,
818    N: Node<K, T, From = ArchivedIndexSet<K>, To = ArchivedIndexSet<K>> + 'a,
819    S: BuildHasher + Default + Clone,
820{
821    /*if filter(id)
822        && !identifier_map.contains_key(id)
823        && nodes[id]
824            .from()
825            .into_iter()
826            .filter(|&parent| filter(parent))
827            .count()
828            == 0
829    {
830        stack.push(*id);
831    }*/
832
833    stack.push(subgraph_root);
834
835    while let Some(id) = stack.pop() {
836        identifier_callback(id);
837
838        for child in archived_set_reverse_order(nodes[&id].to()).copied() {
839            if !filter(&child) {
840                continue;
841            }
842
843            let remaining = identifier_map.entry(child).or_insert_with(|| {
844                nodes[&child]
845                    .from()
846                    .iter()
847                    .filter(|&parent| filter(parent))
848                    .count()
849            });
850            #[allow(clippy::arithmetic_side_effects, reason = "Can never underflow")]
851            {
852                *remaining -= 1;
853            }
854
855            if *remaining == 0 {
856                stack.push(child);
857            }
858        }
859    }
860}
861
862fn shortest_path_to_ancestor<'a, K, N, T, S>(
863    nodes: &'a HashMap<K, N, S>,
864    id: &'a K,
865    target: impl Fn(&'a N) -> bool,
866    scratchpad: &mut ScratchpadVec<'_, K>,
867    scratchpad_map: &mut ScratchpadMap<'_, K, K, S>,
868    path: &mut Vec<K>,
869) where
870    K: Hash + Copy + Eq + Ord + 'a,
871    N: Node<K, T> + 'a,
872    <N as Node<K, T>>::From: 'a,
873    <N as Node<K, T>>::To: 'a,
874    &'a N::From: IntoIterator<Item = &'a K, IntoIter: DoubleEndedIterator>,
875    &'a N::To: IntoIterator<Item = &'a K, IntoIter: DoubleEndedIterator>,
876    S: BuildHasher + Default + Clone,
877{
878    scratchpad.push(*id);
879    scratchpad_map.insert(*id, *id);
880
881    let mut head = 0;
882
883    while head < scratchpad.len() {
884        let id = scratchpad[head];
885        #[allow(clippy::arithmetic_side_effects, reason = "Can never overflow")]
886        {
887            head += 1;
888        }
889
890        let node = &nodes[&id];
891
892        if target(node) {
893            path.push(id);
894            break;
895        }
896
897        for parent in node.from().into_iter().copied() {
898            if let Entry::Vacant(entry) = scratchpad_map.entry(parent) {
899                entry.insert(id);
900                scratchpad.push(parent);
901            }
902        }
903    }
904
905    while let Some(last) = path.last()
906        && last != id
907    {
908        path.push(scratchpad_map[last]);
909    }
910}
911
912#[cfg(feature = "rkyv")]
913fn archived_shortest_path_to_ancestor<'a, K, N, T, S>(
914    nodes: &'a ArchivedHashMap<K, N>,
915    id: &'a K,
916    target: impl Fn(&'a N) -> bool,
917    scratchpad: &mut ScratchpadVec<'_, K>,
918    scratchpad_map: &mut ScratchpadMap<'_, K, K, S>,
919    path: &mut Vec<K>,
920) where
921    K: Hash + Copy + Eq + Ord + 'a,
922    N: Node<K, T, From = ArchivedIndexSet<K>> + 'a,
923    S: BuildHasher + Default + Clone,
924{
925    scratchpad.push(*id);
926    scratchpad_map.insert(*id, *id);
927
928    let mut head = 0;
929
930    while head < scratchpad.len() {
931        let id = scratchpad[head];
932        #[allow(clippy::arithmetic_side_effects, reason = "Can never overflow")]
933        {
934            head += 1;
935        }
936
937        let node = &nodes[&id];
938
939        if target(node) {
940            path.push(id);
941            break;
942        }
943
944        for parent in node.from().iter().copied() {
945            if let Entry::Vacant(entry) = scratchpad_map.entry(parent) {
946                entry.insert(id);
947                scratchpad.push(parent);
948            }
949        }
950    }
951
952    while let Some(last) = path.last()
953        && last != id
954    {
955        path.push(scratchpad_map[last]);
956    }
957}
958
959fn longest_candidate_path_to_root<'a, K, N, T, S>(
960    nodes: &'a HashMap<K, N, S>,
961    topological_order: &[K],
962    is_candidate: impl Fn(&K) -> bool,
963    scratchpad_map: &mut ScratchpadMap<'_, K, (usize, K), S>,
964    mut reversed_path_callback: impl FnMut(K),
965) where
966    K: Hash + Copy + Eq + Ord + 'a,
967    N: Node<K, T> + 'a,
968    <N as Node<K, T>>::From: 'a,
969    <N as Node<K, T>>::To: 'a,
970    &'a N::From: IntoIterator<Item = &'a K, IntoIter: DoubleEndedIterator + ExactSizeIterator>,
971    &'a N::To: IntoIterator<Item = &'a K, IntoIter: DoubleEndedIterator>,
972    S: BuildHasher + Default + Clone,
973{
974    let mut longest_distance = None;
975
976    for id in topological_order {
977        if !is_candidate(id) {
978            continue;
979        }
980
981        let from = nodes[id].from().into_iter();
982
983        let has_parents = from.len() != 0;
984        let best_parent = from
985            .filter_map(|id| scratchpad_map.get(id).map(|v| (v.0, id)))
986            .min_by_key(|&(v, _)| Reverse(v));
987
988        #[allow(clippy::arithmetic_side_effects, reason = "Can never overflow")]
989        let distance = match best_parent {
990            Some((parent_distance, parent)) => Some((parent_distance + 1, *parent)),
991            None => {
992                if has_parents {
993                    None
994                } else {
995                    Some((0, *id))
996                }
997            }
998        };
999
1000        if let Some((distance, parent)) = distance {
1001            scratchpad_map.insert(*id, (distance, parent));
1002
1003            if longest_distance.is_none_or(|(value, _)| distance > value) {
1004                longest_distance = Some((distance, *id));
1005            }
1006        }
1007    }
1008
1009    if let Some(mut id) = longest_distance.map(|(_, id)| id) {
1010        loop {
1011            reversed_path_callback(id);
1012
1013            let parent = scratchpad_map[&id].1;
1014            if parent == id {
1015                break;
1016            }
1017            id = parent;
1018        }
1019    }
1020}
1021
1022#[cfg(feature = "rkyv")]
1023fn archived_longest_candidate_path_to_root<'a, K, N, T, S>(
1024    nodes: &'a ArchivedHashMap<K, N>,
1025    topological_order: &'a [K],
1026    is_candidate: impl Fn(&K) -> bool,
1027    scratchpad_map: &mut ScratchpadMap<'_, K, (usize, K), S>,
1028    mut reversed_path_callback: impl FnMut(K),
1029) where
1030    K: Hash + Copy + Eq + Ord + 'a,
1031    N: Node<K, T, From = ArchivedIndexSet<K>> + 'a,
1032    S: BuildHasher + Default + Clone,
1033{
1034    let mut longest_distance = None;
1035
1036    for id in topological_order {
1037        if !is_candidate(id) {
1038            continue;
1039        }
1040
1041        let from = nodes[id].from();
1042
1043        let has_parents = !from.is_empty();
1044        let best_parent = from
1045            .iter()
1046            .filter_map(|id| scratchpad_map.get(id).map(|v| (v.0, id)))
1047            .min_by_key(|&(v, _)| Reverse(v));
1048
1049        #[allow(clippy::arithmetic_side_effects, reason = "Can never overflow")]
1050        let distance = match best_parent {
1051            Some((parent_distance, parent)) => Some((parent_distance + 1, *parent)),
1052            None => {
1053                if has_parents {
1054                    None
1055                } else {
1056                    Some((0, *id))
1057                }
1058            }
1059        };
1060
1061        if let Some((distance, parent)) = distance {
1062            scratchpad_map.insert(*id, (distance, parent));
1063
1064            if longest_distance.is_none_or(|(value, _)| distance > value) {
1065                longest_distance = Some((distance, *id));
1066            }
1067        }
1068    }
1069
1070    if let Some(mut id) = longest_distance.map(|(_, id)| id) {
1071        loop {
1072            reversed_path_callback(id);
1073
1074            let parent = scratchpad_map[&id].1;
1075            if parent == id {
1076                break;
1077            }
1078            id = parent;
1079        }
1080    }
1081}
1082
1083fn ancestor_subgraph<'a, K, N, T, S>(
1084    nodes: &'a HashMap<K, N, S>,
1085    id: K,
1086    stack: &mut ScratchpadVec<'_, K>,
1087    identifiers: &mut ScratchpadSet<'_, K, S>,
1088    mut root_callback: impl FnMut(K),
1089) where
1090    K: Hash + Copy + Eq + Ord + 'a,
1091    N: Node<K, T>,
1092    <N as Node<K, T>>::From: 'a,
1093    <N as Node<K, T>>::To: 'a,
1094    &'a N::From: IntoIterator<Item = &'a K, IntoIter: DoubleEndedIterator + ExactSizeIterator>,
1095    &'a N::To: IntoIterator<Item = &'a K, IntoIter: DoubleEndedIterator>,
1096    S: BuildHasher + Default + Clone,
1097{
1098    if identifiers.insert(id) {
1099        stack.push(id);
1100    }
1101
1102    while let Some(id) = stack.pop() {
1103        let from = nodes[&id].from().into_iter();
1104
1105        if from.len() == 0 {
1106            root_callback(id);
1107        } else {
1108            for parent in from.rev().copied() {
1109                if identifiers.insert(parent) {
1110                    stack.push(parent);
1111                }
1112            }
1113        }
1114    }
1115}
1116
1117fn ancestor_subgraph_reaches<'a, K, N, T, S>(
1118    nodes: &'a HashMap<K, N, S>,
1119    ids: impl DoubleEndedIterator<Item = K>,
1120    target: impl Fn(&K) -> bool,
1121    stack: &mut ScratchpadVec<'_, K>,
1122    identifiers: &mut ScratchpadSet<'_, K, S>,
1123) -> bool
1124where
1125    K: Hash + Copy + Eq + Ord + 'a,
1126    N: Node<K, T>,
1127    <N as Node<K, T>>::From: 'a,
1128    <N as Node<K, T>>::To: 'a,
1129    &'a N::From: IntoIterator<Item = &'a K, IntoIter: DoubleEndedIterator>,
1130    &'a N::To: IntoIterator<Item = &'a K, IntoIter: DoubleEndedIterator>,
1131    S: BuildHasher + Default + Clone,
1132{
1133    for id in ids.rev() {
1134        if identifiers.insert(id) {
1135            if target(&id) {
1136                return true;
1137            }
1138
1139            stack.push(id);
1140        }
1141    }
1142
1143    while let Some(id) = stack.pop() {
1144        for parent in nodes[&id].from().into_iter().rev().copied() {
1145            if identifiers.insert(parent) {
1146                if target(&parent) {
1147                    return true;
1148                }
1149
1150                stack.push(parent);
1151            }
1152        }
1153    }
1154
1155    false
1156}
1157
1158#[cfg(feature = "rkyv")]
1159fn archived_ancestor_subgraph<'a, K, N, T, S>(
1160    nodes: &'a ArchivedHashMap<K, N>,
1161    id: K,
1162    stack: &mut ScratchpadVec<'_, K>,
1163    identifiers: &mut ScratchpadSet<'_, K, S>,
1164    mut root_callback: impl FnMut(K),
1165) where
1166    K: Hash + Copy + Eq + Ord + 'a,
1167    N: Node<K, T, From = ArchivedIndexSet<K>> + 'a,
1168    S: BuildHasher + Default + Clone,
1169{
1170    if identifiers.insert(id) {
1171        stack.push(id);
1172    }
1173
1174    while let Some(id) = stack.pop() {
1175        let from = nodes[&id].from();
1176
1177        if from.is_empty() {
1178            root_callback(id);
1179        } else {
1180            for parent in archived_set_reverse_order(from).copied() {
1181                if identifiers.insert(parent) {
1182                    stack.push(parent);
1183                }
1184            }
1185        }
1186    }
1187}
1188
1189fn descendant_subgraph<'a, K, N, T, S>(
1190    nodes: &'a HashMap<K, N, S>,
1191    id: K,
1192    stack: &mut ScratchpadVec<'_, K>,
1193    identifiers: &mut ScratchpadSet<'_, K, S>,
1194) where
1195    K: Hash + Copy + Eq + Ord + 'a,
1196    N: Node<K, T>,
1197    <N as Node<K, T>>::From: 'a,
1198    <N as Node<K, T>>::To: 'a,
1199    &'a N::From: IntoIterator<Item = &'a K, IntoIter: DoubleEndedIterator>,
1200    &'a N::To: IntoIterator<Item = &'a K, IntoIter: DoubleEndedIterator>,
1201    S: BuildHasher + Default + Clone,
1202{
1203    if identifiers.insert(id) {
1204        stack.push(id);
1205    }
1206
1207    while let Some(id) = stack.pop() {
1208        for child in nodes[&id].to().into_iter().rev().copied() {
1209            if identifiers.insert(child) {
1210                stack.push(child);
1211            }
1212        }
1213    }
1214}
1215
1216fn descendant_subgraph_reaches<'a, K, N, T, S>(
1217    nodes: &'a HashMap<K, N, S>,
1218    ids: impl DoubleEndedIterator<Item = K>,
1219    target: impl Fn(&K) -> bool,
1220    stack: &mut ScratchpadVec<'_, K>,
1221    identifiers: &mut ScratchpadSet<'_, K, S>,
1222) -> bool
1223where
1224    K: Hash + Copy + Eq + Ord + 'a,
1225    N: Node<K, T>,
1226    <N as Node<K, T>>::From: 'a,
1227    <N as Node<K, T>>::To: 'a,
1228    &'a N::From: IntoIterator<Item = &'a K, IntoIter: DoubleEndedIterator>,
1229    &'a N::To: IntoIterator<Item = &'a K, IntoIter: DoubleEndedIterator>,
1230    S: BuildHasher + Default + Clone,
1231{
1232    for id in ids.rev() {
1233        if identifiers.insert(id) {
1234            if target(&id) {
1235                return true;
1236            }
1237
1238            stack.push(id);
1239        }
1240    }
1241
1242    while let Some(id) = stack.pop() {
1243        for child in nodes[&id].to().into_iter().rev().copied() {
1244            if identifiers.insert(child) {
1245                if target(&child) {
1246                    return true;
1247                }
1248
1249                stack.push(child);
1250            }
1251        }
1252    }
1253
1254    false
1255}
1256
1257#[cfg(feature = "rkyv")]
1258fn archived_descendant_subgraph<'a, K, N, T, S>(
1259    nodes: &'a ArchivedHashMap<K, N>,
1260    id: K,
1261    stack: &mut ScratchpadVec<'_, K>,
1262    identifiers: &mut ScratchpadSet<'_, K, S>,
1263) where
1264    K: Hash + Copy + Eq + Ord + 'a,
1265    N: Node<K, T, To = ArchivedIndexSet<K>> + 'a,
1266    S: BuildHasher + Default + Clone,
1267{
1268    if identifiers.insert(id) {
1269        stack.push(id);
1270    }
1271
1272    while let Some(id) = stack.pop() {
1273        for child in archived_set_reverse_order(nodes[&id].to()).copied() {
1274            if identifiers.insert(child) {
1275                stack.push(child);
1276            }
1277        }
1278    }
1279}
1280
1281#[cfg(feature = "rkyv")]
1282fn archived_set_reverse_order<T>(set: &ArchivedIndexSet<T>) -> impl Iterator<Item = &T> {
1283    (0..set.len())
1284        .rev()
1285        .filter_map(|index| set.get_index(index))
1286}
universal_weave/lib.rs

universal_weave/
lib.rs
