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

pagesift_html/
dom.rs
