Skip to main content

parsec_xpath/
index.rs

1// SPDX-License-Identifier: Apache-2.0
2// Copyright 2026 James Conway
3
4//! A flat index of a document's nodes in document order. A node's
5//! descendants are the contiguous range after it, so scanning them is a
6//! pass over small arrays rather than a walk through the tree's links.
7
8use std::collections::HashMap;
9use std::sync::OnceLock;
10
11use parsec::{self as html, NodeId};
12
13/// The node kinds, as the index stores them: the DOM's nodeType numbers.
14pub const ELEMENT: u8 = 0x01;
15pub const TEXT: u8 = 0x03;
16pub const CDATA: u8 = 0x04;
17pub const PI: u8 = 0x07;
18pub const COMMENT: u8 = 0x08;
19pub const DOCUMENT: u8 = 0x09;
20pub const DOCTYPE: u8 = 0x0A;
21const OTHER: u8 = 0x0B;
22
23/// Tag ids of names the parser doesn't know start here; below it, a known
24/// tag's number plus one.
25const FIRST_NAMED: usize = 1000;
26
27/// The index of one version of a tree. Its owner builds it once and keeps
28/// it until the tree changes: every query reads it, none builds it.
29pub struct Index {
30    raw: Vec<u32>,
31    /// Each node's parent's position; u32::MAX for the root.
32    parent: Vec<u32>,
33    /// One past the last descendant of each node.
34    end: Vec<u32>,
35    kind: Vec<u8>,
36    /// u32, as node ids are: one for every node adds up on a big page.
37    tag: Vec<u32>,
38    /// Each node's position, by node id; u32::MAX for one not indexed.
39    order: Vec<u32>,
40    /// Tag ids of the lowercase names the parser doesn't know.
41    names: HashMap<String, usize>,
42    /// Positions of the elements carrying each `id`, built on first use.
43    ids: OnceLock<HashMap<String, Vec<u32>>>,
44}
45
46fn kind_of(tree: &html::Document, id: u32) -> u8 {
47    match tree.kind(id) {
48        html::Kind::Element { .. } => ELEMENT,
49        html::Kind::Text(_) => TEXT,
50        html::Kind::Cdata(_) => CDATA,
51        html::Kind::ProcessingInstruction { .. } => PI,
52        html::Kind::Comment(_) => COMMENT,
53        html::Kind::Document => DOCUMENT,
54        html::Kind::Doctype { .. } => DOCTYPE,
55        html::Kind::Fragment | html::Kind::ShadowRoot(_) => OTHER,
56    }
57}
58
59/// An element's name for tag ids: lowercase, without an XML prefix.
60fn tag_key(tree: &html::Document, id: u32) -> &str {
61    let name = tree.lower_name(id).unwrap_or("");
62    // Only XML has prefixes: in HTML, <o:p> is an element called "o:p".
63    match tree.kind(id) {
64        html::Kind::Element {
65            ns: html::Ns::Xml, ..
66        } => name.split_once(':').map_or(name, |(_, local)| local),
67        _ => name,
68    }
69}
70
71impl Index {
72    /// Indexes the tree under each of `roots` in turn: the document, then
73    /// any subtrees removed from it or built apart from it, so every node
74    /// a caller can hold has a position.
75    pub fn build(tree: &html::Document, roots: &[NodeId]) -> Index {
76        let mut raw = Vec::with_capacity(tree.len());
77        let mut parent = Vec::with_capacity(tree.len());
78        let mut kind = Vec::with_capacity(tree.len());
79        let mut tag = Vec::with_capacity(tree.len());
80        let mut order = vec![u32::MAX; tree.len()];
81        let mut names: HashMap<String, usize> = HashMap::new();
82        for &root in roots {
83            // Preorder by the tree's links, keeping each node's parent's
84            // position on a stack of the open ancestors.
85            let mut ancestors: Vec<u32> = Vec::new();
86            let mut at = Some(root);
87            while let Some(n) = at {
88                let pos = raw.len() as u32;
89                order[n as usize] = pos;
90                raw.push(n);
91                parent.push(ancestors.last().copied().unwrap_or(u32::MAX));
92                let k = kind_of(tree, n);
93                kind.push(k);
94                // From the lowercase name alone, as tag_id_named works it
95                // out: an XML <title> shares HTML title's id.
96                tag.push(if k != ELEMENT {
97                    0
98                } else if let Some(t) = tree.known_tag(n) {
99                    t as usize + 1
100                } else {
101                    let key = tag_key(tree, n).to_ascii_lowercase();
102                    match html::tag_number(&key) {
103                        Some(t) => t as usize + 1,
104                        None => {
105                            let next = FIRST_NAMED + names.len();
106                            *names.entry(key).or_insert(next)
107                        }
108                    }
109                } as u32);
110                at = match tree.first_child(n) {
111                    Some(child) => {
112                        ancestors.push(pos);
113                        Some(child)
114                    }
115                    None => {
116                        let mut up = n;
117                        loop {
118                            if up == root {
119                                break None;
120                            }
121                            if let Some(s) = tree.next_sibling(up) {
122                                break Some(s);
123                            }
124                            up = tree
125                                .parent(up)
126                                .expect("a node inside the root has a parent");
127                            ancestors.pop();
128                        }
129                    }
130                };
131            }
132        }
133        let n = raw.len();
134        // Children come after their parent, so one backward pass carries
135        // each subtree's end up to its parent.
136        let mut end: Vec<u32> = (1..=n as u32).collect();
137        for i in (1..n).rev() {
138            let p = parent[i] as usize;
139            if p < n && end[i] > end[p] {
140                end[p] = end[i];
141            }
142        }
143        Index {
144            raw,
145            parent,
146            end,
147            kind,
148            tag,
149            order,
150            names,
151            ids: OnceLock::new(),
152        }
153    }
154
155    /// How many nodes are indexed.
156    pub fn len(&self) -> usize {
157        self.raw.len()
158    }
159
160    pub fn is_empty(&self) -> bool {
161        self.raw.is_empty()
162    }
163
164    /// A node's position; u32::MAX if it was made after the index was.
165    pub fn order(&self, id: NodeId) -> u32 {
166        self.order.get(id as usize).copied().unwrap_or(u32::MAX)
167    }
168
169    /// The node at position `at`.
170    pub fn node_at(&self, at: u32) -> NodeId {
171        self.raw[at as usize]
172    }
173
174    /// The kind ([`ELEMENT`], [`TEXT`] and so on) at position `at`.
175    pub fn kind_at(&self, at: u32) -> u8 {
176        self.kind[at as usize]
177    }
178
179    /// The tag id at position `at`.
180    pub fn tag_at(&self, at: u32) -> usize {
181        self.tag.get(at as usize).map_or(0, |&t| t as usize)
182    }
183
184    /// The tag id elements named `name` (compared lowercased) carry, if
185    /// any element could: a known tag's always, another name's only when
186    /// some element in the document has it.
187    pub fn tag_id_named(&self, name: &str) -> Option<usize> {
188        let lower = name.to_ascii_lowercase();
189        match html::tag_number(&lower) {
190            Some(t) => Some(t as usize + 1),
191            None => self.names.get(&lower).copied(),
192        }
193    }
194
195    /// The elements whose `id` is `id`, in document order. `id_of` reads a
196    /// node's `id` attribute; the first call's is used for every call.
197    pub fn with_id<'t>(&self, id: &str, id_of: impl Fn(NodeId) -> Option<&'t str>) -> Vec<NodeId> {
198        let ids = self.ids.get_or_init(|| {
199            let mut ids: HashMap<String, Vec<u32>> = HashMap::new();
200            for (j, &raw) in self.raw.iter().enumerate() {
201                if let Some(v) = id_of(raw) {
202                    ids.entry(v.to_string()).or_default().push(j as u32);
203                }
204            }
205            ids
206        });
207        ids.get(id)
208            .map(|at| at.iter().map(|&j| self.raw[j as usize]).collect())
209            .unwrap_or_default()
210    }
211
212    /// Appends to `out` the nodes below `at` (from `at` itself if
213    /// `include_self`) that pass `keep(kind, tag)`, in document order.
214    pub fn descendants(
215        &self,
216        at: u32,
217        include_self: bool,
218        keep: impl Fn(u8, usize) -> bool,
219        out: &mut Vec<NodeId>,
220    ) {
221        let start = if include_self { at } else { at + 1 } as usize;
222        for j in start..self.end[at as usize] as usize {
223            if keep(self.kind[j], self.tag[j] as usize) {
224                out.push(self.raw[j]);
225            }
226        }
227    }
228
229    /// One past the last descendant of `at`.
230    pub fn end_of(&self, at: u32) -> u32 {
231        self.end[at as usize]
232    }
233
234    /// The position of the parent of the node at `at`; u32::MAX for a
235    /// root.
236    pub fn parent_of(&self, at: u32) -> u32 {
237        self.parent[at as usize]
238    }
239
240    /// Appends to `out` the children of `at` that pass `keep(kind, tag)`.
241    pub fn children(&self, at: u32, keep: impl Fn(u8, usize) -> bool, out: &mut Vec<NodeId>) {
242        let stop = self.end[at as usize] as usize;
243        let mut c = at as usize + 1;
244        while c < stop {
245            if keep(self.kind[c], self.tag[c] as usize) {
246                out.push(self.raw[c]);
247            }
248            c = self.end[c] as usize;
249        }
250    }
251}