skrifa/
decycler.rs

1//! Support for cycle detection in DFS graph traversals.
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 DFS traversal of a graph.
12///
13/// The graph is expected to have unique node identifiers of type `T`
14/// and traversal depth is limited to the constant `D`.
15///
16/// This is based on `hb_decycler_t` in HarfBuzz (<https://github.com/harfbuzz/harfbuzz/blob/a2ea5d28cb5387f4de2049802474b817be15ad5b/src/hb-decycler.hh>)
17/// which is an extension of Floyd's tortoise and hare algorithm (<https://en.wikipedia.org/wiki/Cycle_detection#Floyd's_tortoise_and_hare>)
18/// to DFS traversals.
19///
20/// Unlike the implementation in HB which supports traversals of arbitrary
21/// depth, this is limited to a constant value. Instead of building a
22/// forward-linked list of nodes (on the stack) to track the traversal chain,
23/// we simply use a fixed size array, indexed by depth, which imposes the
24/// limit.
25///
26/// It _might_ be possible to implement the HB algorithm in safe Rust but
27/// satisfying the borrow checker would be a challenge and we require a depth
28/// limit to prevent stack overflows anyway. Improvements welcome!
29pub(crate) struct Decycler<T, const D: usize> {
30    node_ids: [T; D],
31    depth: usize,
32}
33
34impl<T, const D: usize> Decycler<T, D>
35where
36    T: Copy + PartialEq + Default,
37{
38    pub fn new() -> Self {
39        Self {
40            node_ids: [T::default(); D],
41            depth: 0,
42        }
43    }
44
45    /// Enters a new graph node with the given value that uniquely
46    /// identifies the current node.
47    ///
48    /// Returns an error when a cycle is detected or the max depth of the
49    /// traversal is exceeded. Otherwise, increases the current depth and
50    /// returns a guard object that will decrease the depth when dropped.
51    ///
52    /// The guard object derefs to the decycler, so it can be passed to
53    /// a recursive traversal function to check for cycles in descendent
54    /// nodes in a graph.
55    pub fn enter(&mut self, node_id: T) -> Result<DecyclerGuard<'_, T, D>, DecyclerError> {
56        if self.depth < D {
57            if self.depth == 0 || self.node_ids[self.depth / 2] != node_id {
58                self.node_ids[self.depth] = node_id;
59                self.depth += 1;
60                Ok(DecyclerGuard { decycler: self })
61            } else {
62                Err(DecyclerError::CycleDetected)
63            }
64        } else {
65            Err(DecyclerError::DepthLimitExceeded)
66        }
67    }
68}
69
70impl<T, const D: usize> Default for Decycler<T, D>
71where
72    T: Copy + PartialEq + Default,
73{
74    fn default() -> Self {
75        Self::new()
76    }
77}
78
79pub(crate) struct DecyclerGuard<'a, T, const D: usize> {
80    decycler: &'a mut Decycler<T, D>,
81}
82
83impl<T, const D: usize> Deref for DecyclerGuard<'_, T, D> {
84    type Target = Decycler<T, D>;
85
86    fn deref(&self) -> &Self::Target {
87        self.decycler
88    }
89}
90
91impl<T, const D: usize> DerefMut for DecyclerGuard<'_, T, D> {
92    fn deref_mut(&mut self) -> &mut Self::Target {
93        self.decycler
94    }
95}
96
97impl<T, const D: usize> Drop for DecyclerGuard<'_, T, D> {
98    fn drop(&mut self) {
99        self.decycler.depth -= 1;
100    }
101}
102
103#[cfg(test)]
104mod tests {
105    use super::*;
106
107    #[test]
108    fn graph_with_cycles() {
109        let tree = Tree {
110            nodes: vec![
111                Node::new(vec![1, 2]),
112                Node::new(vec![2, 3]),
113                Node::new(vec![]),
114                Node::new(vec![0, 1]),
115            ],
116        };
117        let result = tree.traverse(&mut TestDecycler::new());
118        assert!(matches!(result, Err(DecyclerError::CycleDetected)));
119    }
120
121    #[test]
122    fn exceeds_max_depth() {
123        let mut nodes = (0..MAX_DEPTH)
124            .map(|ix| Node::new(vec![ix + 1]))
125            .collect::<Vec<_>>();
126        nodes.push(Node::new(vec![]));
127        let tree = Tree { nodes };
128        let result = tree.traverse(&mut TestDecycler::new());
129        assert!(matches!(result, Err(DecyclerError::DepthLimitExceeded)));
130    }
131
132    #[test]
133    fn well_formed_tree() {
134        let mut nodes = (0..MAX_DEPTH - 1)
135            .map(|ix| Node::new(vec![ix + 1]))
136            .collect::<Vec<_>>();
137        nodes.push(Node::new(vec![]));
138        let tree = Tree { nodes };
139        let result = tree.traverse(&mut TestDecycler::new());
140        assert!(result.is_ok());
141    }
142
143    const MAX_DEPTH: usize = 64;
144    type TestDecycler = Decycler<usize, MAX_DEPTH>;
145
146    struct Node {
147        child_ids: Vec<usize>,
148    }
149
150    impl Node {
151        fn new(child_ids: Vec<usize>) -> Self {
152            Self { child_ids }
153        }
154    }
155
156    struct Tree {
157        nodes: Vec<Node>,
158    }
159
160    impl Tree {
161        fn traverse(&self, decycler: &mut TestDecycler) -> Result<(), DecyclerError> {
162            self.traverse_impl(decycler, 0)
163        }
164
165        fn traverse_impl(
166            &self,
167            decycler: &mut TestDecycler,
168            node_id: usize,
169        ) -> Result<(), DecyclerError> {
170            let mut cycle_guard = decycler.enter(node_id)?;
171            let node = &self.nodes[node_id];
172            for child_id in &node.child_ids {
173                self.traverse_impl(&mut cycle_guard, *child_id)?;
174            }
175            Ok(())
176        }
177    }
178}
skrifa/decycler.rs

skrifa/
decycler.rs
