eure_document/plan/
traverse.rs

1//! Reachable-node traversal helpers for a [`LayoutPlan`].
2
3use alloc::vec::Vec;
4
5use alloc::string::ToString;
6
7use crate::document::node::NodeValue;
8use crate::document::{EureDocument, NodeId};
9use crate::path::{ArrayIndexKind, PathSegment};
10use crate::value::{ObjectKey, PartialObjectKey};
11
12/// Return every [`NodeId`] reachable from the document root, in a stable
13/// (document-order) traversal: extensions first, then content children.
14pub fn all_reachable_ids(doc: &EureDocument) -> Vec<NodeId> {
15    let mut out = Vec::new();
16    let mut stack = alloc::vec![doc.get_root_id()];
17    let mut seen = Vec::new();
18    while let Some(id) = stack.pop() {
19        if seen.contains(&id) {
20            continue;
21        }
22        seen.push(id);
23        out.push(id);
24        let node = doc.node(id);
25        // Push children in reverse so that pop order equals document order.
26        let mut children: Vec<NodeId> = Vec::new();
27        for (_, &ext) in node.extensions.iter() {
28            children.push(ext);
29        }
30        match &node.content {
31            NodeValue::Map(map) => {
32                for (_, &cid) in map.iter() {
33                    children.push(cid);
34                }
35            }
36            NodeValue::PartialMap(pm) => {
37                for (_, &cid) in pm.iter() {
38                    children.push(cid);
39                }
40            }
41            NodeValue::Array(arr) => {
42                for &cid in arr.iter() {
43                    children.push(cid);
44                }
45            }
46            NodeValue::Tuple(tup) => {
47                for &cid in tup.iter() {
48                    children.push(cid);
49                }
50            }
51            _ => {}
52        }
53        for child in children.into_iter().rev() {
54            stack.push(child);
55        }
56    }
57    // Stable order: we want root first, then DFS document order. Since we
58    // pushed in reverse and popped, `out` already reflects that. Sort by
59    // NodeId to be deterministic.
60    out.sort_by_key(|id| id.0);
61    out
62}
63
64/// Return the direct children of `parent` along with the [`PathSegment`]
65/// used to address each one. Extensions come first, then content children
66/// in their document order.
67pub fn children_of(doc: &EureDocument, parent: NodeId) -> Vec<(PathSegment, NodeId)> {
68    let mut out = Vec::new();
69    let node = doc.node(parent);
70    for (ident, &child) in node.extensions.iter() {
71        out.push((PathSegment::Extension(ident.clone()), child));
72    }
73    match &node.content {
74        NodeValue::Map(map) => {
75            for (key, &child) in map.iter() {
76                out.push((PathSegment::Value(key.clone()), child));
77            }
78        }
79        NodeValue::PartialMap(pm) => {
80            for (key, &child) in pm.iter() {
81                out.push((PathSegment::from_partial_object_key(key.clone()), child));
82            }
83        }
84        NodeValue::Array(arr) => {
85            for (i, &child) in arr.iter().enumerate() {
86                out.push((PathSegment::ArrayIndex(ArrayIndexKind::Specific(i)), child));
87            }
88        }
89        NodeValue::Tuple(tup) => {
90            for (i, &child) in tup.iter().enumerate() {
91                out.push((PathSegment::TupleIndex(i as u8), child));
92            }
93        }
94        _ => {}
95    }
96    out
97}
98
99/// Return the child node at a single [`PathSegment`] under `parent`.
100///
101/// This is ported verbatim from the previous `layout.rs` so that lookups
102/// against both `Map` and `PartialMap` forms succeed regardless of which
103/// segment flavor the caller uses.
104pub fn child_node_id(
105    doc: &EureDocument,
106    parent_id: NodeId,
107    segment: &PathSegment,
108) -> Option<NodeId> {
109    let parent = doc.node(parent_id);
110    match segment {
111        PathSegment::Extension(ext) => parent.extensions.get(ext).copied(),
112        PathSegment::Ident(ident) => match &parent.content {
113            NodeValue::Map(map) => map.get(&ObjectKey::String(ident.to_string())).copied(),
114            NodeValue::PartialMap(map) => map
115                .find(&PartialObjectKey::String(ident.to_string()))
116                .copied(),
117            _ => None,
118        },
119        PathSegment::Value(key) => match &parent.content {
120            NodeValue::Map(map) => map.get(key).copied(),
121            NodeValue::PartialMap(map) => map.find(&PartialObjectKey::from(key.clone())).copied(),
122            _ => None,
123        },
124        PathSegment::PartialValue(key) => match &parent.content {
125            NodeValue::Map(map) => ObjectKey::try_from(key.clone())
126                .ok()
127                .and_then(|object_key| map.get(&object_key))
128                .copied(),
129            NodeValue::PartialMap(map) => map.find(key).copied(),
130            _ => None,
131        },
132        PathSegment::ArrayIndex(index) => match &parent.content {
133            NodeValue::Array(array) => match index {
134                ArrayIndexKind::Specific(i) => array.get(*i),
135                ArrayIndexKind::Push | ArrayIndexKind::Current => None,
136            },
137            _ => None,
138        },
139        PathSegment::TupleIndex(index) => match &parent.content {
140            NodeValue::Tuple(tuple) => tuple.get(*index as usize),
141            _ => None,
142        },
143        PathSegment::HoleKey(label) => match &parent.content {
144            NodeValue::PartialMap(map) => map.find(&PartialObjectKey::Hole(label.clone())).copied(),
145            _ => None,
146        },
147    }
148}
eure_document/plan/traverse.rs

eure_document/plan/
traverse.rs
