1use std::collections::HashMap;
9use std::sync::OnceLock;
10
11use parsec::{self as html, NodeId};
12
13pub 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
23const FIRST_NAMED: usize = 1000;
26
27pub struct Index {
30 raw: Vec<u32>,
31 parent: Vec<u32>,
33 end: Vec<u32>,
35 kind: Vec<u8>,
36 tag: Vec<u32>,
38 order: Vec<u32>,
40 names: HashMap<String, usize>,
42 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
59fn tag_key(tree: &html::Document, id: u32) -> &str {
61 let name = tree.lower_name(id).unwrap_or("");
62 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 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 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 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 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 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 pub fn order(&self, id: NodeId) -> u32 {
166 self.order.get(id as usize).copied().unwrap_or(u32::MAX)
167 }
168
169 pub fn node_at(&self, at: u32) -> NodeId {
171 self.raw[at as usize]
172 }
173
174 pub fn kind_at(&self, at: u32) -> u8 {
176 self.kind[at as usize]
177 }
178
179 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 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 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 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 pub fn end_of(&self, at: u32) -> u32 {
231 self.end[at as usize]
232 }
233
234 pub fn parent_of(&self, at: u32) -> u32 {
237 self.parent[at as usize]
238 }
239
240 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}