pagesift_html/
dom.rs

1//! 文档树：所有节点放在一个 `Vec` 里，用 u32 下标互相引用；文本和属性值尽量直接指向源字符串。
2
3use std::borrow::Cow;
4
5use crate::Tag;
6
7pub(crate) const NONE: u32 = u32::MAX;
8/// [`Span`] 起点的最高位：为 1 时指向解码缓冲区，否则指向源字符串。
9const OWNED: u32 = 1 << 31;
10
11/// 一段字符串：源 HTML 里的一段，或者解码缓冲区里的一段（含字符引用、需要改写的内容）。
12#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
13pub(crate) struct Span {
14    start: u32,
15    len: u32,
16}
17
18impl Span {
19    pub(crate) fn source(start: usize, end: usize) -> Span {
20        Span {
21            start: start as u32,
22            len: (end - start) as u32,
23        }
24    }
25
26    pub(crate) fn owned(start: usize, end: usize) -> Span {
27        Span {
28            start: start as u32 | OWNED,
29            len: (end - start) as u32,
30        }
31    }
32
33    pub(crate) fn is_owned(self) -> bool {
34        self.start & OWNED != 0
35    }
36
37    pub(crate) fn offset(self) -> usize {
38        (self.start & !OWNED) as usize
39    }
40
41    pub(crate) fn end(self) -> usize {
42        self.offset() + self.len as usize
43    }
44
45    pub(crate) fn is_empty(self) -> bool {
46        self.len == 0
47    }
48
49    pub(crate) fn skip(self, n: usize) -> Span {
50        Span {
51            start: self.start + n as u32,
52            len: self.len - n as u32,
53        }
54    }
55}
56
57#[derive(Debug, Clone, Copy)]
58pub(crate) struct Attr {
59    pub(crate) name: Span,
60    pub(crate) value: Span,
61}
62
63#[derive(Debug, Clone, Copy)]
64pub(crate) enum Data {
65    Document,
66    Doctype,
67    Element {
68        tag: Tag,
69        /// 只有 [`Tag::Other`] 才有名字；已知标签的名字来自 [`Tag::name`]。
70        name: Span,
71        attrs: u32,
72        attrs_len: u32,
73    },
74    Text(Span),
75    Comment(Span),
76}
77
78#[derive(Debug, Clone, Copy)]
79pub(crate) struct Node {
80    pub(crate) parent: u32,
81    pub(crate) first_child: u32,
82    pub(crate) last_child: u32,
83    pub(crate) prev: u32,
84    pub(crate) next: u32,
85    pub(crate) data: Data,
86}
87
88impl Node {
89    pub(crate) fn new(data: Data) -> Node {
90        Node {
91            parent: NONE,
92            first_child: NONE,
93            last_child: NONE,
94            prev: NONE,
95            next: NONE,
96            data,
97        }
98    }
99}
100
101/// 解析好的文档。借用源字符串（输入含 `\r` 或 NUL 时持有规范化后的副本）。
102pub struct Html<'s> {
103    pub(crate) src: Cow<'s, str>,
104    pub(crate) buf: String,
105    pub(crate) nodes: Vec<Node>,
106    pub(crate) attrs: Vec<Attr>,
107}
108
109/// Reusable allocation storage for parsing consecutive documents on one
110/// worker. The parsed [`Html`] owns the buffers while it is in use; call
111/// [`ParseScratch::recycle`] after all node references have been dropped.
112#[derive(Default)]
113pub struct ParseScratch {
114    pub(crate) buf: String,
115    pub(crate) nodes: Vec<Node>,
116    pub(crate) attrs: Vec<Attr>,
117}
118
119impl ParseScratch {
120    /// Return a completed document's backing allocations to this scratch
121    /// object. Source HTML is never retained.
122    pub fn recycle(&mut self, mut html: Html<'_>) {
123        html.buf.clear();
124        html.nodes.clear();
125        html.attrs.clear();
126        self.buf = if html.buf.capacity() <= 1024 * 1024 {
127            html.buf
128        } else {
129            String::new()
130        };
131        self.nodes = if html.nodes.capacity() <= 16 * 1024 {
132            html.nodes
133        } else {
134            Vec::new()
135        };
136        self.attrs = if html.attrs.capacity() <= 32 * 1024 {
137            html.attrs
138        } else {
139            Vec::new()
140        };
141    }
142}
143
144impl<'s> Html<'s> {
145    /// 解析整个 HTML 文档。永不失败：任何输入都会得到一棵树。
146    pub fn parse(html: &'s str) -> Html<'s> {
147        crate::builder::parse(html)
148    }
149
150    /// Parse while reusing node, attribute, and decoded-text allocations from
151    /// the preceding document handled by this worker.
152    pub fn parse_with_scratch(html: &'s str, scratch: &mut ParseScratch) -> Html<'s> {
153        crate::builder::parse_with_scratch(html, scratch)
154    }
155
156    /// 文档根节点（不是 `<html>` 元素，是它的父节点）。
157    pub fn root(&self) -> NodeRef<'_> {
158        NodeRef { doc: self, id: 0 }
159    }
160
161    /// 节点总数。节点 id 的范围是 `0..len()`，可以用来开按节点下标索引的数组。
162    pub fn len(&self) -> usize {
163        self.nodes.len()
164    }
165
166    pub fn is_empty(&self) -> bool {
167        self.nodes.len() <= 1
168    }
169
170    pub fn get(&self, id: NodeId) -> NodeRef<'_> {
171        NodeRef {
172            doc: self,
173            id: id.0,
174        }
175    }
176
177    /// 第一个 `<body>`，没有时返回根节点。
178    pub fn body(&self) -> NodeRef<'_> {
179        self.root()
180            .descendants()
181            .find(|n| n.tag() == Some(Tag::Body))
182            .unwrap_or_else(|| self.root())
183    }
184
185    pub(crate) fn str(&self, s: Span) -> &str {
186        let (start, end) = (s.offset(), s.end());
187        if s.is_owned() {
188            &self.buf[start..end]
189        } else {
190            &self.src[start..end]
191        }
192    }
193}
194
195impl std::fmt::Debug for Html<'_> {
196    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
197        f.debug_struct("Html")
198            .field("nodes", &self.nodes.len())
199            .finish()
200    }
201}
202
203/// 节点 id，在同一个文档里唯一，取值 `0..Html::len()`。
204#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
205pub struct NodeId(u32);
206
207impl NodeId {
208    pub fn index(self) -> usize {
209        self.0 as usize
210    }
211}
212
213/// 节点的引用。可以复制，比较时比的是节点身份。
214#[derive(Clone, Copy)]
215pub struct NodeRef<'a> {
216    doc: &'a Html<'a>,
217    id: u32,
218}
219
220impl PartialEq for NodeRef<'_> {
221    fn eq(&self, other: &Self) -> bool {
222        self.id == other.id && std::ptr::eq(self.doc, other.doc)
223    }
224}
225
226impl Eq for NodeRef<'_> {}
227
228impl std::fmt::Debug for NodeRef<'_> {
229    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
230        match self.node().data {
231            Data::Document => write!(f, "#document"),
232            Data::Doctype => write!(f, "<!DOCTYPE>"),
233            Data::Element { .. } => write!(f, "<{}>", self.as_element().unwrap().name()),
234            Data::Text(s) => write!(f, "{:?}", self.doc.str(s)),
235            Data::Comment(s) => write!(f, "<!--{}-->", self.doc.str(s)),
236        }
237    }
238}
239
240impl<'a> NodeRef<'a> {
241    fn node(&self) -> &'a Node {
242        &self.doc.nodes[self.id as usize]
243    }
244
245    fn at(&self, id: u32) -> Option<NodeRef<'a>> {
246        (id != NONE).then_some(NodeRef { doc: self.doc, id })
247    }
248
249    pub fn id(&self) -> NodeId {
250        NodeId(self.id)
251    }
252
253    pub fn document(&self) -> &'a Html<'a> {
254        self.doc
255    }
256
257    pub fn parent(&self) -> Option<NodeRef<'a>> {
258        self.at(self.node().parent)
259    }
260
261    pub fn first_child(&self) -> Option<NodeRef<'a>> {
262        self.at(self.node().first_child)
263    }
264
265    pub fn last_child(&self) -> Option<NodeRef<'a>> {
266        self.at(self.node().last_child)
267    }
268
269    pub fn next_sibling(&self) -> Option<NodeRef<'a>> {
270        self.at(self.node().next)
271    }
272
273    pub fn prev_sibling(&self) -> Option<NodeRef<'a>> {
274        self.at(self.node().prev)
275    }
276
277    pub fn children(&self) -> Children<'a> {
278        Children {
279            doc: self.doc,
280            front: self.node().first_child,
281            back: self.node().last_child,
282        }
283    }
284
285    /// 自身加所有后代，先序（文档顺序）。
286    pub fn descendants(&self) -> Descendants<'a> {
287        Descendants {
288            doc: self.doc,
289            root: self.id,
290            next: self.id,
291        }
292    }
293
294    /// 父节点、祖父节点……直到根，不含自身。
295    pub fn ancestors(&self) -> Ancestors<'a> {
296        Ancestors {
297            doc: self.doc,
298            next: self.node().parent,
299        }
300    }
301
302    pub fn is_element(&self) -> bool {
303        matches!(self.node().data, Data::Element { .. })
304    }
305
306    pub fn is_text(&self) -> bool {
307        matches!(self.node().data, Data::Text(_))
308    }
309
310    pub fn is_comment(&self) -> bool {
311        matches!(self.node().data, Data::Comment(_))
312    }
313
314    pub fn is_document(&self) -> bool {
315        matches!(self.node().data, Data::Document)
316    }
317
318    pub fn as_element(&self) -> Option<Element<'a>> {
319        match self.node().data {
320            Data::Element {
321                tag,
322                name,
323                attrs,
324                attrs_len,
325            } => Some(Element {
326                doc: self.doc,
327                tag,
328                name,
329                attrs: &self.doc.attrs[attrs as usize..(attrs + attrs_len) as usize],
330            }),
331            _ => None,
332        }
333    }
334
335    /// 元素的标签；不是元素时为 `None`。
336    pub fn tag(&self) -> Option<Tag> {
337        match self.node().data {
338            Data::Element { tag, .. } => Some(tag),
339            _ => None,
340        }
341    }
342
343    pub fn as_text(&self) -> Option<&'a str> {
344        match self.node().data {
345            Data::Text(s) => Some(self.doc.str(s)),
346            _ => None,
347        }
348    }
349
350    pub fn as_comment(&self) -> Option<&'a str> {
351        match self.node().data {
352            Data::Comment(s) => Some(self.doc.str(s)),
353            _ => None,
354        }
355    }
356
357    /// 子树里所有文本节点按顺序拼起来。
358    pub fn text(&self) -> String {
359        let mut out = String::new();
360        for d in self.descendants() {
361            if let Some(t) = d.as_text() {
362                out.push_str(t);
363            }
364        }
365        out
366    }
367}
368
369/// 元素：标签、名字和属性。
370#[derive(Clone, Copy)]
371pub struct Element<'a> {
372    doc: &'a Html<'a>,
373    tag: Tag,
374    name: Span,
375    attrs: &'a [Attr],
376}
377
378impl<'a> Element<'a> {
379    pub fn tag(&self) -> Tag {
380        self.tag
381    }
382
383    /// 小写标签名。
384    pub fn name(&self) -> &'a str {
385        match self.tag {
386            Tag::Other => self.doc.str(self.name),
387            t => t.name(),
388        }
389    }
390
391    /// 属性值，`name` 用小写。同名属性只保留第一个（规范如此）。
392    pub fn attr(&self, name: &str) -> Option<&'a str> {
393        self.attrs
394            .iter()
395            .find(|a| a.name.len as usize == name.len() && self.doc.str(a.name) == name)
396            .map(|a| self.doc.str(a.value))
397    }
398
399    pub fn attrs(&self) -> impl Iterator<Item = (&'a str, &'a str)> + 'a {
400        let doc = self.doc;
401        self.attrs
402            .iter()
403            .map(move |a| (doc.str(a.name), doc.str(a.value)))
404    }
405}
406
407impl std::fmt::Debug for Element<'_> {
408    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
409        write!(f, "<{}", self.name())?;
410        for (k, v) in self.attrs() {
411            write!(f, " {k}={v:?}")?;
412        }
413        write!(f, ">")
414    }
415}
416
417pub struct Children<'a> {
418    doc: &'a Html<'a>,
419    front: u32,
420    back: u32,
421}
422
423impl<'a> Iterator for Children<'a> {
424    type Item = NodeRef<'a>;
425    fn next(&mut self) -> Option<NodeRef<'a>> {
426        if self.front == NONE {
427            return None;
428        }
429        let id = self.front;
430        if id == self.back {
431            self.front = NONE;
432            self.back = NONE;
433        } else {
434            self.front = self.doc.nodes[id as usize].next;
435        }
436        Some(NodeRef { doc: self.doc, id })
437    }
438}
439
440impl DoubleEndedIterator for Children<'_> {
441    fn next_back(&mut self) -> Option<Self::Item> {
442        if self.back == NONE {
443            return None;
444        }
445        let id = self.back;
446        if id == self.front {
447            self.front = NONE;
448            self.back = NONE;
449        } else {
450            self.back = self.doc.nodes[id as usize].prev;
451        }
452        Some(NodeRef { doc: self.doc, id })
453    }
454}
455
456pub struct Descendants<'a> {
457    doc: &'a Html<'a>,
458    root: u32,
459    next: u32,
460}
461
462impl<'a> Iterator for Descendants<'a> {
463    type Item = NodeRef<'a>;
464    fn next(&mut self) -> Option<NodeRef<'a>> {
465        if self.next == NONE {
466            return None;
467        }
468        let id = self.next;
469        let nodes = &self.doc.nodes;
470        let n = &nodes[id as usize];
471        self.next = if n.first_child != NONE {
472            n.first_child
473        } else {
474            // 没有子节点：找自己或最近祖先的下一个兄弟，到子树根为止
475            let mut cur = id;
476            loop {
477                if cur == self.root {
478                    break NONE;
479                }
480                let c = &nodes[cur as usize];
481                if c.next != NONE {
482                    break c.next;
483                }
484                cur = c.parent;
485                if cur == NONE {
486                    break NONE;
487                }
488            }
489        };
490        Some(NodeRef { doc: self.doc, id })
491    }
492}
493
494pub struct Ancestors<'a> {
495    doc: &'a Html<'a>,
496    next: u32,
497}
498
499impl<'a> Iterator for Ancestors<'a> {
500    type Item = NodeRef<'a>;
501    fn next(&mut self) -> Option<NodeRef<'a>> {
502        if self.next == NONE {
503            return None;
504        }
505        let id = self.next;
506        self.next = self.doc.nodes[id as usize].parent;
507        Some(NodeRef { doc: self.doc, id })
508    }
509}
pagesift_html/dom.rs

pagesift_html/
dom.rs
