read_fonts/model/glyph/color/
decycler.rs

1//! Cycle detection for depth first traversals of a graph.
2
3use core::ops::{Deref, DerefMut};
4
5#[derive(Copy, Clone, Debug)]
6pub(crate) enum DecyclerError {
7    DepthLimitExceeded,
8    CycleDetected,
9}
10
11/// Cycle detector for a depth first traversal of a graph.
12///
13/// The graph is expected to have unique node identifiers of type `T`, and
14/// the traversal is limited to a depth of `D`.
15///
16/// Based on `hb_decycler_t` in HarfBuzz
17/// (<https://github.com/harfbuzz/harfbuzz/blob/a2ea5d28cb5387f4de2049802474b817be15ad5b/src/hb-decycler.hh>),
18/// an extension of Floyd's tortoise and hare algorithm
19/// (<https://en.wikipedia.org/wiki/Cycle_detection#Floyd's_tortoise_and_hare>)
20/// to depth first traversals.
21///
22/// Unlike HarfBuzz, which supports traversals of any depth with a linked
23/// list on the stack, this stores the chain in a fixed array indexed by
24/// depth. This imposes the depth limit, which is also needed to prevent
25/// stack overflow.
26pub(crate) struct Decycler<T, const D: usize> {
27    node_ids: [T; D],
28    depth: usize,
29}
30
31impl<T, const D: usize> Decycler<T, D>
32where
33    T: Copy + PartialEq + Default,
34{
35    pub(super) fn new() -> Self {
36        Self {
37            node_ids: [T::default(); D],
38            depth: 0,
39        }
40    }
41
42    /// Enters the node uniquely identified by `node_id`.
43    ///
44    /// Returns an error if a cycle is detected or the depth limit is reached.
45    /// Otherwise, increases the depth and returns a guard that decreases it
46    /// when dropped.
47    ///
48    /// The guard dereferences to the decycler, so a recursive traversal can
49    /// pass it down to check child nodes.
50    pub(super) fn enter(&mut self, node_id: T) -> Result<DecyclerGuard<'_, T, D>, DecyclerError> {
51        if self.depth < D {
52            if self.depth == 0 || self.node_ids[self.depth / 2] != node_id {
53                self.node_ids[self.depth] = node_id;
54                self.depth += 1;
55                Ok(DecyclerGuard { decycler: self })
56            } else {
57                Err(DecyclerError::CycleDetected)
58            }
59        } else {
60            Err(DecyclerError::DepthLimitExceeded)
61        }
62    }
63}
64
65impl<T, const D: usize> Default for Decycler<T, D>
66where
67    T: Copy + PartialEq + Default,
68{
69    fn default() -> Self {
70        Self::new()
71    }
72}
73
74pub(crate) struct DecyclerGuard<'a, T, const D: usize> {
75    decycler: &'a mut Decycler<T, D>,
76}
77
78impl<T, const D: usize> Deref for DecyclerGuard<'_, T, D> {
79    type Target = Decycler<T, D>;
80
81    fn deref(&self) -> &Self::Target {
82        self.decycler
83    }
84}
85
86impl<T, const D: usize> DerefMut for DecyclerGuard<'_, T, D> {
87    fn deref_mut(&mut self) -> &mut Self::Target {
88        self.decycler
89    }
90}
91
92impl<T, const D: usize> Drop for DecyclerGuard<'_, T, D> {
93    fn drop(&mut self) {
94        self.decycler.depth -= 1;
95    }
96}
97
98#[cfg(test)]
99mod tests {
100    use super::*;
101    use alloc::vec::Vec;
102
103    #[test]
104    fn graph_with_cycles() {
105        let tree = Tree {
106            nodes: alloc::vec![
107                Node::new(alloc::vec![1, 2]),
108                Node::new(alloc::vec![2, 3]),
109                Node::new(alloc::vec![]),
110                Node::new(alloc::vec![0, 1]),
111            ],
112        };
113        let result = tree.traverse(&mut TestDecycler::new());
114        assert!(matches!(result, Err(DecyclerError::CycleDetected)));
115    }
116
117    #[test]
118    fn exceeds_max_depth() {
119        let mut nodes = (0..MAX_DEPTH)
120            .map(|ix| Node::new(alloc::vec![ix + 1]))
121            .collect::<Vec<_>>();
122        nodes.push(Node::new(alloc::vec![]));
123        let tree = Tree { nodes };
124        let result = tree.traverse(&mut TestDecycler::new());
125        assert!(matches!(result, Err(DecyclerError::DepthLimitExceeded)));
126    }
127
128    #[test]
129    fn well_formed_tree() {
130        let mut nodes = (0..MAX_DEPTH - 1)
131            .map(|ix| Node::new(alloc::vec![ix + 1]))
132            .collect::<Vec<_>>();
133        nodes.push(Node::new(alloc::vec![]));
134        let tree = Tree { nodes };
135        let result = tree.traverse(&mut TestDecycler::new());
136        assert!(result.is_ok());
137    }
138
139    const MAX_DEPTH: usize = 64;
140    type TestDecycler = Decycler<usize, MAX_DEPTH>;
141
142    struct Node {
143        child_ids: Vec<usize>,
144    }
145
146    impl Node {
147        fn new(child_ids: Vec<usize>) -> Self {
148            Self { child_ids }
149        }
150    }
151
152    struct Tree {
153        nodes: Vec<Node>,
154    }
155
156    impl Tree {
157        fn traverse(&self, decycler: &mut TestDecycler) -> Result<(), DecyclerError> {
158            self.traverse_impl(decycler, 0)
159        }
160
161        fn traverse_impl(
162            &self,
163            decycler: &mut TestDecycler,
164            node_id: usize,
165        ) -> Result<(), DecyclerError> {
166            let mut cycle_guard = decycler.enter(node_id)?;
167            let node = &self.nodes[node_id];
168            for child_id in &node.child_ids {
169                self.traverse_impl(&mut cycle_guard, *child_id)?;
170            }
171            Ok(())
172        }
173    }
174}
read_fonts/model/glyph/color/decycler.rs

read_fonts/model/glyph/color/
decycler.rs
