supa_mdx_lint/utils/
char_tree.rs

Help
1#![allow(dead_code)]
2// The [mutable key lint](https://rust-lang.github.io/rust-clippy/master/index.html#mutable_key_type)
3// has known false positives when dealing with a struct that has only partial
4// interior mutability. In this module, CharNode has a children field that needs
5// interior mutability to build the tree, but it's hashed on the value field,
6// so the lint can be ignored.
7#![allow(clippy::mutable_key_type)]
8
9use std::{
10    cell::RefCell,
11    collections::HashSet,
12    hash::{Hash, Hasher},
13    rc::Rc,
14};
15
16#[derive(Debug, Eq, PartialEq, Hash)]
17enum NodeValue {
18    Initial,
19    Char(char),
20    /// The path leading up to this node is not a valid word and should be
21    /// abandoned
22    Abort,
23    /// The path leading up to this node is a complete word in and of itself
24    Finish,
25}
26
27#[derive(Debug)]
28struct CharNodeInner {
29    value: NodeValue,
30    children: RefCell<Option<HashSet<CharNode>>>,
31}
32
33#[derive(Debug, Clone)]
34pub(super) struct CharNode(Rc<CharNodeInner>);
35
36impl PartialEq for CharNode {
37    fn eq(&self, other: &Self) -> bool {
38        self.0.value == other.0.value
39    }
40}
41
42impl Eq for CharNode {}
43
44impl Hash for CharNode {
45    fn hash<H: Hasher>(&self, state: &mut H) {
46        self.0.value.hash(state);
47    }
48}
49
50impl CharNode {
51    pub(super) fn initiate() -> Self {
52        Self(Rc::new(CharNodeInner {
53            value: NodeValue::Initial,
54            children: RefCell::new(None),
55        }))
56    }
57
58    fn new(value: char) -> Self {
59        Self(Rc::new(CharNodeInner {
60            value: NodeValue::Char(value),
61            children: RefCell::new(None),
62        }))
63    }
64
65    fn new_abort() -> Self {
66        Self(Rc::new(CharNodeInner {
67            value: NodeValue::Abort,
68            children: RefCell::new(None),
69        }))
70    }
71
72    fn new_finish() -> Self {
73        Self(Rc::new(CharNodeInner {
74            value: NodeValue::Finish,
75            children: RefCell::new(None),
76        }))
77    }
78
79    fn add_child(&mut self, child: CharNode) {
80        let mut children = self.0.children.borrow_mut();
81        let children_set = children.get_or_insert_with(HashSet::new);
82        children_set.insert(child);
83    }
84
85    pub(super) fn is_root(&self) -> bool {
86        self.0.value == NodeValue::Initial
87    }
88
89    pub(super) fn append(&mut self, value: char) -> Self {
90        let new_child = Self::new(value);
91        self.add_child(new_child.clone());
92        new_child
93    }
94
95    pub(super) fn abort(&mut self) {
96        let new_child = Self::new_abort();
97        self.add_child(new_child);
98    }
99
100    pub(super) fn mark_finished_word(&mut self) {
101        let new_child = Self::new_finish();
102        self.add_child(new_child);
103    }
104
105    pub(super) fn collect(&self) -> Vec<String> {
106        fn traverse(node: &CharNode, prefix: &str, result: &mut Vec<String>) {
107            match node.0.value {
108                NodeValue::Initial => {
109                    if let Some(children) = &*node.0.children.borrow() {
110                        let new_prefix = "";
111                        for child in children {
112                            traverse(child, new_prefix, result);
113                        }
114                    }
115                }
116                NodeValue::Char(value) => {
117                    let new_prefix = format!("{}{}", prefix, value);
118                    if let Some(children) = &*node.0.children.borrow() {
119                        for child in children {
120                            if child.0.value == NodeValue::Finish {
121                                result.push(new_prefix.clone());
122                            } else {
123                                traverse(child, &new_prefix, result);
124                            }
125                        }
126                    } else {
127                        result.push(new_prefix);
128                    }
129                }
130                _ => {}
131            }
132        }
133
134        let mut result = Vec::new();
135        traverse(self, "", &mut result);
136        result
137    }
138}
139
140#[cfg(test)]
141mod tests {
142    use super::*;
143
144    #[test]
145    fn test_char_tree_collect() {
146        let mut root = CharNode::initiate();
147        let mut child1 = root.append('a');
148        let mut child2 = child1.append('b');
149        child1.append('c');
150        child2.append('d');
151
152        let collected = child1.collect();
153        assert_eq!(collected.len(), 2);
154        assert!(collected.contains(&"abd".to_string()));
155        assert!(collected.contains(&"ac".to_string()));
156    }
157
158    #[test]
159    fn test_char_tree_collect_with_aborts() {
160        let mut root = CharNode::initiate();
161        let mut child1 = root.append('a');
162        let mut child2 = child1.append('b');
163        child1.append('c');
164        child2.append('d');
165        let mut aborted_child = child2.append('e');
166        aborted_child.abort();
167
168        let collected = child1.collect();
169        assert_eq!(collected.len(), 2);
170        assert!(collected.contains(&"ac".to_string()));
171        assert!(collected.contains(&"abd".to_string()));
172    }
173
174    #[test]
175    fn test_char_tree_with_mid_path_finish() {
176        let mut root = CharNode::initiate();
177        let mut child1 = root.append('a');
178        let mut child2 = child1.append('b');
179        child2.mark_finished_word();
180        child2.append('c');
181
182        let collected = child1.collect();
183        assert_eq!(collected.len(), 2);
184        assert!(collected.contains(&"ab".to_string()));
185        assert!(collected.contains(&"abc".to_string()));
186    }
187}
supa_mdx_lint/utils/char_tree.rs

supa_mdx_lint/utils/
char_tree.rs
