atmos/os_lib/
dom_traversal.rs

1//! W3C DOM Standard §6 Traversal
2//! NodeFilter, TreeWalker, NodeIterator の純粋幾何・走査・フィルタ判定ロジック。
3
4use alloc::vec::Vec;
5
6// NodeFilter 定数
7pub const FILTER_ACCEPT: u32 = 1;
8pub const FILTER_REJECT: u32 = 2;
9pub const FILTER_SKIP: u32 = 3;
10
11pub const SHOW_ALL: u32 = 0xFFFF_FFFF;
12pub const SHOW_ELEMENT: u32 = 0x1;
13pub const SHOW_ATTRIBUTE: u32 = 0x2;
14pub const SHOW_TEXT: u32 = 0x4;
15pub const SHOW_CDATA_SECTION: u32 = 0x8;
16pub const SHOW_ENTITY_REFERENCE: u32 = 0x10;
17pub const SHOW_ENTITY: u32 = 0x20;
18pub const SHOW_PROCESSING_INSTRUCTION: u32 = 0x40;
19pub const SHOW_COMMENT: u32 = 0x80;
20pub const SHOW_DOCUMENT: u32 = 0x100;
21pub const SHOW_DOCUMENT_TYPE: u32 = 0x200;
22pub const SHOW_DOCUMENT_FRAGMENT: u32 = 0x400;
23pub const SHOW_NOTATION: u32 = 0x800;
24
25#[derive(Clone, Copy, Debug, PartialEq, Eq)]
26pub enum FilterResult {
27    Accept,
28    Reject,
29    Skip,
30}
31
32impl FilterResult {
33    pub fn from_u32(val: u32) -> Self {
34        match val {
35            FILTER_ACCEPT => FilterResult::Accept,
36            FILTER_REJECT => FilterResult::Reject,
37            FILTER_SKIP => FilterResult::Skip,
38            _ => FilterResult::Accept,
39        }
40    }
41}
42
43/// ノード型が `whatToShow` ビットマスクに適合するか判定する
44pub fn what_to_show_matches(what_to_show: u32, node_type: u16) -> bool {
45    if node_type == 0 || node_type > 32 {
46        return false;
47    }
48    if what_to_show == SHOW_ALL {
49        return true;
50    }
51    let mask = 1u32 << (node_type - 1);
52    (what_to_show & mask) != 0
53}
54
55/// DOM 木の走査に必要な関係を取得するトレイト
56pub trait TraversalTree {
57    fn parent(&self, idx: usize) -> Option<usize>;
58    fn first_child(&self, idx: usize) -> Option<usize>;
59    fn last_child(&self, idx: usize) -> Option<usize>;
60    fn next_sibling(&self, idx: usize) -> Option<usize>;
61    fn previous_sibling(&self, idx: usize) -> Option<usize>;
62    fn node_type(&self, idx: usize) -> u16;
63}
64
65/// テストや軽量操作用のツリーノード構造体
66#[derive(Clone, Debug, PartialEq, Eq)]
67pub struct SimpleTreeNode {
68    pub parent: Option<usize>,
69    pub children: Vec<usize>,
70    pub node_type: u16,
71}
72
73#[derive(Clone, Debug, Default, PartialEq, Eq)]
74pub struct SimpleTree {
75    pub nodes: Vec<SimpleTreeNode>,
76}
77
78impl SimpleTree {
79    pub fn new() -> Self {
80        Self { nodes: Vec::new() }
81    }
82
83    pub fn add_node(&mut self, parent: Option<usize>, node_type: u16) -> usize {
84        let idx = self.nodes.len();
85        self.nodes.push(SimpleTreeNode {
86            parent,
87            children: Vec::new(),
88            node_type,
89        });
90        if let Some(p) = parent {
91            if let Some(pn) = self.nodes.get_mut(p) {
92                pn.children.push(idx);
93            }
94        }
95        idx
96    }
97}
98
99impl TraversalTree for SimpleTree {
100    fn parent(&self, idx: usize) -> Option<usize> {
101        self.nodes.get(idx).and_then(|n| n.parent)
102    }
103
104    fn first_child(&self, idx: usize) -> Option<usize> {
105        self.nodes.get(idx).and_then(|n| n.children.first().copied())
106    }
107
108    fn last_child(&self, idx: usize) -> Option<usize> {
109        self.nodes.get(idx).and_then(|n| n.children.last().copied())
110    }
111
112    fn next_sibling(&self, idx: usize) -> Option<usize> {
113        let p = self.parent(idx)?;
114        let kids = &self.nodes.get(p)?.children;
115        let pos = kids.iter().position(|&c| c == idx)?;
116        kids.get(pos + 1).copied()
117    }
118
119    fn previous_sibling(&self, idx: usize) -> Option<usize> {
120        let p = self.parent(idx)?;
121        let kids = &self.nodes.get(p)?.children;
122        let pos = kids.iter().position(|&c| c == idx)?;
123        if pos > 0 {
124            kids.get(pos - 1).copied()
125        } else {
126            None
127        }
128    }
129
130    fn node_type(&self, idx: usize) -> u16 {
131        self.nodes.get(idx).map(|n| n.node_type).unwrap_or(1)
132    }
133}
134
135/// ノードに対する総合判定（whatToShow ＋ カスタムフィルタ関数）
136pub fn evaluate_node_filter<T: TraversalTree, F: FnMut(usize) -> FilterResult>(
137    tree: &T,
138    idx: usize,
139    what_to_show: u32,
140    filter: &mut F,
141) -> FilterResult {
142    let ntype = tree.node_type(idx);
143    if !what_to_show_matches(what_to_show, ntype) {
144        return FilterResult::Skip;
145    }
146    filter(idx)
147}
148
149/// TreeWalker: `parentNode` 走査
150pub fn tw_parent_node<T: TraversalTree, F: FnMut(usize) -> FilterResult>(
151    tree: &T,
152    root: usize,
153    cur: usize,
154    what_to_show: u32,
155    filter: &mut F,
156) -> Option<usize> {
157    let mut node = cur;
158    while node != root {
159        let p = tree.parent(node)?;
160        let res = evaluate_node_filter(tree, p, what_to_show, filter);
161        if res == FilterResult::Accept {
162            return Some(p);
163        }
164        node = p;
165    }
166    None
167}
168
169/// TreeWalker: `firstChild` 走査
170pub fn tw_first_child<T: TraversalTree, F: FnMut(usize) -> FilterResult>(
171    tree: &T,
172    cur: usize,
173    what_to_show: u32,
174    filter: &mut F,
175) -> Option<usize> {
176    tw_traverse_children(tree, cur, true, what_to_show, filter)
177}
178
179/// TreeWalker: `lastChild` 走査
180pub fn tw_last_child<T: TraversalTree, F: FnMut(usize) -> FilterResult>(
181    tree: &T,
182    cur: usize,
183    what_to_show: u32,
184    filter: &mut F,
185) -> Option<usize> {
186    tw_traverse_children(tree, cur, false, what_to_show, filter)
187}
188
189fn tw_traverse_children<T: TraversalTree, F: FnMut(usize) -> FilterResult>(
190    tree: &T,
191    parent: usize,
192    first: bool,
193    what_to_show: u32,
194    filter: &mut F,
195) -> Option<usize> {
196    let mut child = if first {
197        tree.first_child(parent)
198    } else {
199        tree.last_child(parent)
200    };
201
202    while let Some(c) = child {
203        let res = evaluate_node_filter(tree, c, what_to_show, filter);
204        if res == FilterResult::Accept {
205            return Some(c);
206        }
207        if res == FilterResult::Skip {
208            // スキップされた場合はその子孫から探す
209            if let Some(descendant) = tw_traverse_children(tree, c, first, what_to_show, filter) {
210                return Some(descendant);
211            }
212        }
213        // Reject または Skip の子孫が見つからなかった場合は次の兄弟へ
214        child = if first {
215            tree.next_sibling(c)
216        } else {
217            tree.previous_sibling(c)
218        };
219    }
220    None
221}
222
223/// TreeWalker: `nextSibling` 走査
224pub fn tw_next_sibling<T: TraversalTree, F: FnMut(usize) -> FilterResult>(
225    tree: &T,
226    root: usize,
227    cur: usize,
228    what_to_show: u32,
229    filter: &mut F,
230) -> Option<usize> {
231    tw_traverse_siblings(tree, root, cur, true, what_to_show, filter)
232}
233
234/// TreeWalker: `previousSibling` 走査
235pub fn tw_previous_sibling<T: TraversalTree, F: FnMut(usize) -> FilterResult>(
236    tree: &T,
237    root: usize,
238    cur: usize,
239    what_to_show: u32,
240    filter: &mut F,
241) -> Option<usize> {
242    tw_traverse_siblings(tree, root, cur, false, what_to_show, filter)
243}
244
245fn tw_traverse_siblings<T: TraversalTree, F: FnMut(usize) -> FilterResult>(
246    tree: &T,
247    root: usize,
248    cur: usize,
249    next: bool,
250    what_to_show: u32,
251    filter: &mut F,
252) -> Option<usize> {
253    let mut node = cur;
254    if node == root {
255        return None;
256    }
257
258    loop {
259        let mut sibling = if next {
260            tree.next_sibling(node)
261        } else {
262            tree.previous_sibling(node)
263        };
264
265        while let Some(s) = sibling {
266            let res = evaluate_node_filter(tree, s, what_to_show, filter);
267            if res == FilterResult::Accept {
268                return Some(s);
269            }
270            if res == FilterResult::Skip {
271                if let Some(descendant) = tw_traverse_children(tree, s, next, what_to_show, filter) {
272                    return Some(descendant);
273                }
274            }
275            sibling = if next {
276                tree.next_sibling(s)
277            } else {
278                tree.previous_sibling(s)
279            };
280        }
281
282        // 親ノードが FILTER_SKIP の場合、親の兄弟へ遡る（root を越えない範囲で）
283        let p = tree.parent(node)?;
284        if p == root {
285            return None;
286        }
287        let pres = evaluate_node_filter(tree, p, what_to_show, filter);
288        if pres == FilterResult::Accept {
289            return None;
290        }
291        node = p;
292    }
293}
294
295/// TreeWalker: `nextNode` 走査（W3C DOM Standard §6.2.2 準拠）
296pub fn tw_next_node<T: TraversalTree, F: FnMut(usize) -> FilterResult>(
297    tree: &T,
298    root: usize,
299    cur: usize,
300    what_to_show: u32,
301    filter: &mut F,
302) -> Option<usize> {
303    let mut node = cur;
304    let mut result = FilterResult::Accept;
305
306    loop {
307        // 1. 子孫ノードへの下降（直前が REJECT でない限り）
308        while result != FilterResult::Reject {
309            if let Some(child) = tree.first_child(node) {
310                node = child;
311                result = evaluate_node_filter(tree, node, what_to_show, filter);
312                if result == FilterResult::Accept {
313                    return Some(node);
314                }
315            } else {
316                break;
317            }
318        }
319
320        // 2. 次の兄弟、または祖先の次の兄弟を探す
321        let mut temp = node;
322
323        loop {
324            if temp == root {
325                return None;
326            }
327            if let Some(sib) = tree.next_sibling(temp) {
328                node = sib;
329                break;
330            }
331            let p = tree.parent(temp)?;
332            temp = p;
333        }
334
335        result = evaluate_node_filter(tree, node, what_to_show, filter);
336        if result == FilterResult::Accept {
337            return Some(node);
338        }
339    }
340}
341
342/// TreeWalker: `previousNode` 走査（W3C DOM Standard §6.2.3 準拠）
343pub fn tw_previous_node<T: TraversalTree, F: FnMut(usize) -> FilterResult>(
344    tree: &T,
345    root: usize,
346    cur: usize,
347    what_to_show: u32,
348    filter: &mut F,
349) -> Option<usize> {
350    let mut node = cur;
351
352    while node != root {
353        let mut sibling = tree.previous_sibling(node);
354        while let Some(sib) = sibling {
355            node = sib;
356            let mut result = evaluate_node_filter(tree, node, what_to_show, filter);
357            while result != FilterResult::Reject {
358                if let Some(last_child) = tree.last_child(node) {
359                    node = last_child;
360                    result = evaluate_node_filter(tree, node, what_to_show, filter);
361                } else {
362                    break;
363                }
364            }
365            if result == FilterResult::Accept {
366                return Some(node);
367            }
368            sibling = tree.previous_sibling(node);
369        }
370
371        if node == root {
372            return None;
373        }
374        let p = tree.parent(node)?;
375        node = p;
376        if evaluate_node_filter(tree, node, what_to_show, filter) == FilterResult::Accept {
377            return Some(node);
378        }
379    }
380    None
381}
382
383/// NodeIterator: `step_next`
384pub fn ni_step_next<T: TraversalTree, F: FnMut(usize) -> FilterResult>(
385    tree: &T,
386    root: usize,
387    cur: usize,
388    what_to_show: u32,
389    filter: &mut F,
390) -> Option<usize> {
391    let mut node = cur;
392    loop {
393        // 通常の pre-order 次ノード
394        let next = if let Some(c) = tree.first_child(node) {
395            Some(c)
396        } else {
397            let mut anc = node;
398            let mut found = None;
399            while anc != root {
400                if let Some(sib) = tree.next_sibling(anc) {
401                    found = Some(sib);
402                    break;
403                }
404                anc = tree.parent(anc)?;
405            }
406            found
407        };
408
409        let n = next?;
410        // NodeIterator では FILTER_REJECT も FILTER_SKIP と同様に扱い、単に該当ノードをスキップする
411        let res = evaluate_node_filter(tree, n, what_to_show, filter);
412        if res == FilterResult::Accept {
413            return Some(n);
414        }
415        node = n;
416    }
417}
418
419/// NodeIterator: `step_previous`
420pub fn ni_step_previous<T: TraversalTree, F: FnMut(usize) -> FilterResult>(
421    tree: &T,
422    root: usize,
423    cur: usize,
424    what_to_show: u32,
425    filter: &mut F,
426) -> Option<usize> {
427    let mut node = cur;
428    loop {
429        if node == root {
430            return None;
431        }
432        let prev = if let Some(sib) = tree.previous_sibling(node) {
433            let mut deep = sib;
434            while let Some(last) = tree.last_child(deep) {
435                deep = last;
436            }
437            deep
438        } else {
439            tree.parent(node)?
440        };
441
442        let res = evaluate_node_filter(tree, prev, what_to_show, filter);
443        if res == FilterResult::Accept {
444            return Some(prev);
445        }
446        node = prev;
447    }
448}
atmos/os_lib/dom_traversal.rs

atmos/os_lib/
dom_traversal.rs
