sauron_core/vdom/patch/
tree_path.rs

1use super::Node;
2use std::fmt::Debug;
3
4/// Describe the path traversal of a Node starting from the root node
5///
6/// The figure below shows `node_idx` in a depth first traversal.
7///
8/// ```text
9///            .─.
10///           ( 0 )
11///            `-'
12///           /   \
13///          /     \
14///         /       \
15///        ▼         ▼
16///       .─.         .─.
17///      ( 1 )       ( 4 )
18///       `-'         `-'
19///      /  \          | \ '.
20///     /    \         |  \  '.
21///    ▼      ▼        |   \   '.
22///  .─.      .─.      ▼    ▼     ▼
23/// ( 2 )    ( 3 )    .─.   .─.   .─.
24///  `─'      `─'    ( 5 ) ( 6 ) ( 7 )
25///                   `─'   `─'   `─'
26/// ```
27///
28/// The figure below shows the index of each child node relative to their parent node
29///
30/// ```text
31///             .─.
32///            ( 0 )
33///             `-'
34///            /   \
35///           /     \
36///          /       \
37///         ▼         ▼
38///        .─.         .─.
39///       ( 0 )       ( 1 )
40///        `-'         `-'
41///       /  \          | \ '.
42///      /    \         |  \  '.
43///     ▼      ▼        |   \   '.
44///   .─.      .─.      ▼    ▼     ▼
45///  ( 0 )    ( 1 )    .─.   .─.   .─.
46///   `─'      `─'    ( 0 ) ( 1 ) ( 2 )
47///                    `─'   `─'   `─'
48/// ```
49/// The equivalent idx and path are as follows:
50/// ```text
51///    0 = []
52///    1 = [0]
53///    2 = [0,0]
54///    3 = [0,1]
55///    4 = [1]
56///    5 = [1,0]
57///    6 = [1,1]
58///    7 = [1,2]
59/// ```
60#[derive(Debug, Clone, PartialEq, PartialOrd, Eq, Ord, Hash)]
61pub struct TreePath {
62    /// An array of child index at each level of the dom tree.
63    /// The children of the nodes at each child index is traverse
64    /// at each traversal the first element of path is removed until
65    /// the path becomes empty.
66    /// If the path has become empty the node is said to be found.
67    ///
68    /// Empty path means root node
69    pub path: Vec<usize>,
70}
71
72impl TreePath {
73    /// create a TreePath with node index `node_idx` and traversal path `path`
74    pub fn new(path: impl IntoIterator<Item = usize>) -> Self {
75        Self {
76            path: path.into_iter().collect(),
77        }
78    }
79
80    /// create a TreePath which starts at empty vec which is the root node of a DOM tree
81    pub fn root() -> Self {
82        Self { path: vec![] }
83    }
84
85    /// add a path node idx
86    pub fn push(&mut self, node_idx: usize) {
87        self.path.push(node_idx)
88    }
89
90    /// create a new TreePath with an added node_index
91    /// This is used for traversing into child elements
92    pub fn traverse(&self, node_idx: usize) -> Self {
93        let mut new_path = self.clone();
94        new_path.push(node_idx);
95        new_path
96    }
97
98    /// backtrack to the parent node path
99    pub fn backtrack(&self) -> Self {
100        let mut new_path = self.clone();
101        new_path.path.pop();
102        new_path
103    }
104
105    /// remove first node index of this treepath
106    /// Everytime a node is traversed, the first element should be removed
107    /// until no more index is in this path
108    pub fn remove_first(&mut self) -> usize {
109        self.path.remove(0)
110    }
111
112    /// pluck the next in line node index in this treepath
113    pub fn pluck(&mut self) -> usize {
114        self.remove_first()
115    }
116
117    /// go to the next sibling
118    pub fn next_sibling(&self) -> Self {
119        let mut new_path = self.clone();
120        let last = new_path.path.pop().expect("last");
121        new_path.traverse(last + 1)
122    }
123
124    /// jump to the sibling n
125    pub fn jump_to_sibling(&self, n: usize) -> Self {
126        let mut new_path = self.clone();
127        let last = new_path.path.pop().expect("last");
128        new_path.traverse(last + n)
129    }
130
131    /// returns tree if the path is empty
132    /// This is used for checking if the path has been traversed
133    pub fn is_empty(&self) -> bool {
134        self.path.is_empty()
135    }
136
137    /// find the node using the path of this tree path
138    pub fn find_node_by_path<'a, MSG>(&self, node: &'a Node<MSG>) -> Option<&'a Node<MSG>> {
139        let mut path = self.clone();
140        traverse_node_by_path(node, &mut path)
141    }
142}
143
144impl<const N: usize> From<[usize; N]> for TreePath {
145    fn from(array: [usize; N]) -> Self {
146        Self {
147            path: array.to_vec(),
148        }
149    }
150}
151
152impl From<Vec<usize>> for TreePath {
153    fn from(vec: Vec<usize>) -> Self {
154        Self { path: vec }
155    }
156}
157
158fn traverse_node_by_path<'a, MSG>(
159    node: &'a Node<MSG>,
160    path: &mut TreePath,
161) -> Option<&'a Node<MSG>> {
162    if path.path.is_empty() {
163        Some(node)
164    } else {
165        let idx = path.path.remove(0);
166        if let Some(child) = node.children().get(idx) {
167            traverse_node_by_path(child, path)
168        } else {
169            None
170        }
171    }
172}
173
174#[cfg(test)]
175mod tests {
176    use super::*;
177
178    use crate::vdom::*;
179
180    #[test]
181    fn test_traverse() {
182        let path = TreePath::from([0]);
183
184        assert_eq!(path.traverse(1), TreePath::from([0, 1]));
185    }
186
187    #[test]
188    fn test_next_sibling() {
189        let path = TreePath::from([0]);
190
191        assert_eq!(path.next_sibling(), TreePath::from([1]));
192    }
193
194    #[test]
195    fn test_next_sibling_deep() {
196        let path = TreePath::from([0, 1, 1, 2]);
197
198        assert_eq!(path.next_sibling(), TreePath::from([0, 1, 1, 3]));
199    }
200
201    #[test]
202    fn test_jump_sibling() {
203        let path = TreePath::from([0, 1, 1, 2]);
204
205        assert_eq!(path.jump_to_sibling(4), TreePath::from([0, 1, 1, 6]));
206    }
207
208    fn sample_node() -> Node<()> {
209        let node: Node<()> = element(
210            "div",
211            vec![attr("class", "[]"), attr("id", "0")],
212            vec![
213                element(
214                    "div",
215                    vec![attr("class", "[0]"), attr("id", "1")],
216                    vec![
217                        element("div", vec![attr("class", "[0,0]"), attr("id", "2")], vec![]),
218                        element("div", vec![attr("class", "[0,1]"), attr("id", "3")], vec![]),
219                    ],
220                ),
221                element(
222                    "div",
223                    vec![attr("class", "[1]"), attr("id", "4")],
224                    vec![
225                        element("div", vec![attr("class", "[1,0]"), attr("id", "5")], vec![]),
226                        element("div", vec![attr("class", "[1,1]"), attr("id", "6")], vec![]),
227                        element("div", vec![attr("class", "[1,2]"), attr("id", "7")], vec![]),
228                    ],
229                ),
230            ],
231        );
232        node
233    }
234
235    // index is the index of this code with respect to it's sibling
236    fn assert_traverse_match(node: &Node<()>, node_idx: &mut usize, path: Vec<usize>) {
237        let id = node.attribute_value(&"id").unwrap()[0];
238        let class = node.attribute_value(&"class").unwrap()[0];
239        assert_eq!(id.as_str(), Some(node_idx.to_string()).as_deref());
240        assert_eq!(class.as_str(), Some(format_vec(&path)).as_deref());
241        for (i, child) in node.children().iter().enumerate() {
242            *node_idx += 1;
243            let mut child_path = path.clone();
244            child_path.push(i);
245            assert_traverse_match(child, node_idx, child_path);
246        }
247    }
248
249    fn traverse_tree_path(node: &Node<()>, path: &TreePath, node_idx: &mut usize) {
250        let id = node.attribute_value(&"id").unwrap()[0];
251        let class = node.attribute_value(&"class").unwrap()[0];
252        assert_eq!(id.as_str(), Some(node_idx.to_string()).as_deref());
253        assert_eq!(class.as_str(), Some(format_vec(&path.path)).as_deref());
254        for (i, child) in node.children().iter().enumerate() {
255            *node_idx += 1;
256            let mut child_path = path.clone();
257            child_path.path.push(i);
258            traverse_tree_path(child, &child_path, node_idx);
259        }
260    }
261
262    fn format_vec(v: &[usize]) -> String {
263        format!(
264            "[{}]",
265            v.iter()
266                .map(|v| v.to_string())
267                .collect::<Vec<_>>()
268                .join(",")
269        )
270    }
271
272    #[test]
273    fn should_match_paths() {
274        let node = sample_node();
275        assert_traverse_match(&node, &mut 0, vec![]);
276        traverse_tree_path(&node, &TreePath::new(vec![]), &mut 0);
277    }
278
279    #[test]
280    fn should_find_root_node() {
281        let node = sample_node();
282        let path = TreePath::new(vec![]);
283        let root = path.find_node_by_path(&node);
284        assert_eq!(Some(&node), root);
285    }
286
287    #[test]
288    fn should_find_node1() {
289        let node = sample_node();
290        let path = TreePath::new(vec![0]);
291        let found = path.find_node_by_path(&node);
292        let expected = element(
293            "div",
294            vec![attr("class", "[0]"), attr("id", "1")],
295            vec![
296                element("div", vec![attr("class", "[0,0]"), attr("id", "2")], vec![]),
297                element("div", vec![attr("class", "[0,1]"), attr("id", "3")], vec![]),
298            ],
299        );
300        assert_eq!(Some(&expected), found);
301    }
302
303    #[test]
304    fn should_find_node2() {
305        let node = sample_node();
306        let path = TreePath::new(vec![0, 0]);
307        let found = path.find_node_by_path(&node);
308        let expected = element("div", vec![attr("class", "[0,0]"), attr("id", "2")], vec![]);
309        assert_eq!(Some(&expected), found);
310    }
311
312    #[test]
313    fn should_find_node3() {
314        let node = sample_node();
315        let path = TreePath::new(vec![0, 1]);
316        let found = path.find_node_by_path(&node);
317        let expected = element("div", vec![attr("class", "[0,1]"), attr("id", "3")], vec![]);
318        assert_eq!(Some(&expected), found);
319    }
320
321    #[test]
322    fn should_find_node4() {
323        let node = sample_node();
324        let path = TreePath::new(vec![1]);
325        let found = path.find_node_by_path(&node);
326        let expected = element(
327            "div",
328            vec![attr("class", "[1]"), attr("id", "4")],
329            vec![
330                element("div", vec![attr("class", "[1,0]"), attr("id", "5")], vec![]),
331                element("div", vec![attr("class", "[1,1]"), attr("id", "6")], vec![]),
332                element("div", vec![attr("class", "[1,2]"), attr("id", "7")], vec![]),
333            ],
334        );
335        assert_eq!(Some(&expected), found);
336    }
337
338    #[test]
339    fn should_find_node5() {
340        let node = sample_node();
341        let path = TreePath::new(vec![1, 0]);
342        let found = path.find_node_by_path(&node);
343        let expected = element("div", vec![attr("class", "[1,0]"), attr("id", "5")], vec![]);
344        assert_eq!(Some(&expected), found);
345    }
346
347    #[test]
348    fn should_find_node6() {
349        let node = sample_node();
350        let path = TreePath::new(vec![1, 1]);
351        let found = path.find_node_by_path(&node);
352        let expected = element("div", vec![attr("class", "[1,1]"), attr("id", "6")], vec![]);
353        assert_eq!(Some(&expected), found);
354    }
355
356    #[test]
357    fn should_find_none_in_013() {
358        let node = sample_node();
359        let path = TreePath::new(vec![0, 1, 3]);
360        let found = path.find_node_by_path(&node);
361        assert_eq!(None, found);
362    }
363
364    #[test]
365    fn should_find_none_in_00000() {
366        let node = sample_node();
367        let path = TreePath::new(vec![0, 0, 0, 0]);
368        let found = path.find_node_by_path(&node);
369        assert_eq!(None, found);
370    }
371
372    #[test]
373    fn should_find_none_in_007() {
374        let node = sample_node();
375        let path = TreePath::new(vec![0, 0, 7]);
376        let bond = path.find_node_by_path(&node);
377        assert_eq!(None, bond);
378    }
379}
sauron_core/vdom/patch/tree_path.rs

sauron_core/vdom/patch/
tree_path.rs
