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 covers(&self, tree: &html::Document) -> bool {
158 self.order.len() == tree.len()
159 }
160
161 pub fn len(&self) -> usize {
163 self.raw.len()
164 }
165
166 pub fn is_empty(&self) -> bool {
167 self.raw.is_empty()
168 }
169
170 pub fn order(&self, id: NodeId) -> u32 {
172 self.order.get(id as usize).copied().unwrap_or(u32::MAX)
173 }
174
175 pub fn node_at(&self, at: u32) -> NodeId {
177 self.raw[at as usize]
178 }
179
180 pub fn kind_at(&self, at: u32) -> u8 {
182 self.kind[at as usize]
183 }
184
185 pub fn tag_at(&self, at: u32) -> usize {
187 self.tag.get(at as usize).map_or(0, |&t| t as usize)
188 }
189
190 pub fn tag_id_named(&self, name: &str) -> Option<usize> {
194 let lower = name.to_ascii_lowercase();
195 match html::tag_number(&lower) {
196 Some(t) => Some(t as usize + 1),
197 None => self.names.get(&lower).copied(),
198 }
199 }
200
201 pub fn with_id<'t>(&self, id: &str, id_of: impl Fn(NodeId) -> Option<&'t str>) -> Vec<NodeId> {
204 let ids = self.ids.get_or_init(|| {
205 let mut ids: HashMap<String, Vec<u32>> = HashMap::new();
206 for (j, &raw) in self.raw.iter().enumerate() {
207 if let Some(v) = id_of(raw) {
208 ids.entry(v.to_string()).or_default().push(j as u32);
209 }
210 }
211 ids
212 });
213 ids.get(id)
214 .map(|at| at.iter().map(|&j| self.raw[j as usize]).collect())
215 .unwrap_or_default()
216 }
217
218 pub fn descendants(
221 &self,
222 at: u32,
223 include_self: bool,
224 keep: impl Fn(u8, usize) -> bool,
225 out: &mut Vec<NodeId>,
226 ) {
227 let start = if include_self { at } else { at + 1 } as usize;
228 for j in start..self.end[at as usize] as usize {
229 if keep(self.kind[j], self.tag[j] as usize) {
230 out.push(self.raw[j]);
231 }
232 }
233 }
234
235 pub fn end_of(&self, at: u32) -> u32 {
237 self.end[at as usize]
238 }
239
240 pub fn parent_of(&self, at: u32) -> u32 {
243 self.parent[at as usize]
244 }
245
246 pub fn children(&self, at: u32, keep: impl Fn(u8, usize) -> bool, out: &mut Vec<NodeId>) {
248 let stop = self.end[at as usize] as usize;
249 let mut c = at as usize + 1;
250 while c < stop {
251 if keep(self.kind[c], self.tag[c] as usize) {
252 out.push(self.raw[c]);
253 }
254 c = self.end[c] as usize;
255 }
256 }
257}