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
109impl<'s> Html<'s> {
110    /// 解析整个 HTML 文档。永不失败：任何输入都会得到一棵树。
111    pub fn parse(html: &'s str) -> Html<'s> {
112        crate::builder::parse(html)
113    }
114
115    /// 文档根节点（不是 `<html>` 元素，是它的父节点）。
116    pub fn root(&self) -> NodeRef<'_> {
117        NodeRef { doc: self, id: 0 }
118    }
119
120    /// 节点总数。节点 id 的范围是 `0..len()`，可以用来开按节点下标索引的数组。
121    pub fn len(&self) -> usize {
122        self.nodes.len()
123    }
124
125    pub fn is_empty(&self) -> bool {
126        self.nodes.len() <= 1
127    }
128
129    pub fn get(&self, id: NodeId) -> NodeRef<'_> {
130        NodeRef {
131            doc: self,
132            id: id.0,
133        }
134    }
135
136    /// 第一个 `<body>`，没有时返回根节点。
137    pub fn body(&self) -> NodeRef<'_> {
138        self.root()
139            .descendants()
140            .find(|n| n.tag() == Some(Tag::Body))
141            .unwrap_or_else(|| self.root())
142    }
143
144    pub(crate) fn str(&self, s: Span) -> &str {
145        let (start, end) = (s.offset(), s.end());
146        if s.is_owned() {
147            &self.buf[start..end]
148        } else {
149            &self.src[start..end]
150        }
151    }
152}
153
154impl std::fmt::Debug for Html<'_> {
155    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
156        f.debug_struct("Html")
157            .field("nodes", &self.nodes.len())
158            .finish()
159    }
160}
161
162/// 节点 id，在同一个文档里唯一，取值 `0..Html::len()`。
163#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
164pub struct NodeId(u32);
165
166impl NodeId {
167    pub fn index(self) -> usize {
168        self.0 as usize
169    }
170}
171
172/// 节点的引用。可以复制，比较时比的是节点身份。
173#[derive(Clone, Copy)]
174pub struct NodeRef<'a> {
175    doc: &'a Html<'a>,
176    id: u32,
177}
178
179impl PartialEq for NodeRef<'_> {
180    fn eq(&self, other: &Self) -> bool {
181        self.id == other.id && std::ptr::eq(self.doc, other.doc)
182    }
183}
184
185impl Eq for NodeRef<'_> {}
186
187impl std::fmt::Debug for NodeRef<'_> {
188    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
189        match self.node().data {
190            Data::Document => write!(f, "#document"),
191            Data::Doctype => write!(f, "<!DOCTYPE>"),
192            Data::Element { .. } => write!(f, "<{}>", self.as_element().unwrap().name()),
193            Data::Text(s) => write!(f, "{:?}", self.doc.str(s)),
194            Data::Comment(s) => write!(f, "<!--{}-->", self.doc.str(s)),
195        }
196    }
197}
198
199impl<'a> NodeRef<'a> {
200    fn node(&self) -> &'a Node {
201        &self.doc.nodes[self.id as usize]
202    }
203
204    fn at(&self, id: u32) -> Option<NodeRef<'a>> {
205        (id != NONE).then_some(NodeRef { doc: self.doc, id })
206    }
207
208    pub fn id(&self) -> NodeId {
209        NodeId(self.id)
210    }
211
212    pub fn document(&self) -> &'a Html<'a> {
213        self.doc
214    }
215
216    pub fn parent(&self) -> Option<NodeRef<'a>> {
217        self.at(self.node().parent)
218    }
219
220    pub fn first_child(&self) -> Option<NodeRef<'a>> {
221        self.at(self.node().first_child)
222    }
223
224    pub fn last_child(&self) -> Option<NodeRef<'a>> {
225        self.at(self.node().last_child)
226    }
227
228    pub fn next_sibling(&self) -> Option<NodeRef<'a>> {
229        self.at(self.node().next)
230    }
231
232    pub fn prev_sibling(&self) -> Option<NodeRef<'a>> {
233        self.at(self.node().prev)
234    }
235
236    pub fn children(&self) -> Children<'a> {
237        Children {
238            doc: self.doc,
239            front: self.node().first_child,
240            back: self.node().last_child,
241        }
242    }
243
244    /// 自身加所有后代，先序（文档顺序）。
245    pub fn descendants(&self) -> Descendants<'a> {
246        Descendants {
247            doc: self.doc,
248            root: self.id,
249            next: self.id,
250        }
251    }
252
253    /// 父节点、祖父节点……直到根，不含自身。
254    pub fn ancestors(&self) -> Ancestors<'a> {
255        Ancestors {
256            doc: self.doc,
257            next: self.node().parent,
258        }
259    }
260
261    pub fn is_element(&self) -> bool {
262        matches!(self.node().data, Data::Element { .. })
263    }
264
265    pub fn is_text(&self) -> bool {
266        matches!(self.node().data, Data::Text(_))
267    }
268
269    pub fn is_comment(&self) -> bool {
270        matches!(self.node().data, Data::Comment(_))
271    }
272
273    pub fn is_document(&self) -> bool {
274        matches!(self.node().data, Data::Document)
275    }
276
277    pub fn as_element(&self) -> Option<Element<'a>> {
278        match self.node().data {
279            Data::Element {
280                tag,
281                name,
282                attrs,
283                attrs_len,
284            } => Some(Element {
285                doc: self.doc,
286                tag,
287                name,
288                attrs: &self.doc.attrs[attrs as usize..(attrs + attrs_len) as usize],
289            }),
290            _ => None,
291        }
292    }
293
294    /// 元素的标签；不是元素时为 `None`。
295    pub fn tag(&self) -> Option<Tag> {
296        match self.node().data {
297            Data::Element { tag, .. } => Some(tag),
298            _ => None,
299        }
300    }
301
302    pub fn as_text(&self) -> Option<&'a str> {
303        match self.node().data {
304            Data::Text(s) => Some(self.doc.str(s)),
305            _ => None,
306        }
307    }
308
309    pub fn as_comment(&self) -> Option<&'a str> {
310        match self.node().data {
311            Data::Comment(s) => Some(self.doc.str(s)),
312            _ => None,
313        }
314    }
315
316    /// 子树里所有文本节点按顺序拼起来。
317    pub fn text(&self) -> String {
318        let mut out = String::new();
319        for d in self.descendants() {
320            if let Some(t) = d.as_text() {
321                out.push_str(t);
322            }
323        }
324        out
325    }
326}
327
328/// 元素：标签、名字和属性。
329#[derive(Clone, Copy)]
330pub struct Element<'a> {
331    doc: &'a Html<'a>,
332    tag: Tag,
333    name: Span,
334    attrs: &'a [Attr],
335}
336
337impl<'a> Element<'a> {
338    pub fn tag(&self) -> Tag {
339        self.tag
340    }
341
342    /// 小写标签名。
343    pub fn name(&self) -> &'a str {
344        match self.tag {
345            Tag::Other => self.doc.str(self.name),
346            t => t.name(),
347        }
348    }
349
350    /// 属性值，`name` 用小写。同名属性只保留第一个（规范如此）。
351    pub fn attr(&self, name: &str) -> Option<&'a str> {
352        self.attrs
353            .iter()
354            .find(|a| a.name.len as usize == name.len() && self.doc.str(a.name) == name)
355            .map(|a| self.doc.str(a.value))
356    }
357
358    pub fn attrs(&self) -> impl Iterator<Item = (&'a str, &'a str)> + 'a {
359        let doc = self.doc;
360        self.attrs
361            .iter()
362            .map(move |a| (doc.str(a.name), doc.str(a.value)))
363    }
364}
365
366impl std::fmt::Debug for Element<'_> {
367    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
368        write!(f, "<{}", self.name())?;
369        for (k, v) in self.attrs() {
370            write!(f, " {k}={v:?}")?;
371        }
372        write!(f, ">")
373    }
374}
375
376pub struct Children<'a> {
377    doc: &'a Html<'a>,
378    front: u32,
379    back: u32,
380}
381
382impl<'a> Iterator for Children<'a> {
383    type Item = NodeRef<'a>;
384    fn next(&mut self) -> Option<NodeRef<'a>> {
385        if self.front == NONE {
386            return None;
387        }
388        let id = self.front;
389        if id == self.back {
390            self.front = NONE;
391            self.back = NONE;
392        } else {
393            self.front = self.doc.nodes[id as usize].next;
394        }
395        Some(NodeRef { doc: self.doc, id })
396    }
397}
398
399impl DoubleEndedIterator for Children<'_> {
400    fn next_back(&mut self) -> Option<Self::Item> {
401        if self.back == NONE {
402            return None;
403        }
404        let id = self.back;
405        if id == self.front {
406            self.front = NONE;
407            self.back = NONE;
408        } else {
409            self.back = self.doc.nodes[id as usize].prev;
410        }
411        Some(NodeRef { doc: self.doc, id })
412    }
413}
414
415pub struct Descendants<'a> {
416    doc: &'a Html<'a>,
417    root: u32,
418    next: u32,
419}
420
421impl<'a> Iterator for Descendants<'a> {
422    type Item = NodeRef<'a>;
423    fn next(&mut self) -> Option<NodeRef<'a>> {
424        if self.next == NONE {
425            return None;
426        }
427        let id = self.next;
428        let nodes = &self.doc.nodes;
429        let n = &nodes[id as usize];
430        self.next = if n.first_child != NONE {
431            n.first_child
432        } else {
433            // 没有子节点：找自己或最近祖先的下一个兄弟，到子树根为止
434            let mut cur = id;
435            loop {
436                if cur == self.root {
437                    break NONE;
438                }
439                let c = &nodes[cur as usize];
440                if c.next != NONE {
441                    break c.next;
442                }
443                cur = c.parent;
444                if cur == NONE {
445                    break NONE;
446                }
447            }
448        };
449        Some(NodeRef { doc: self.doc, id })
450    }
451}
452
453pub struct Ancestors<'a> {
454    doc: &'a Html<'a>,
455    next: u32,
456}
457
458impl<'a> Iterator for Ancestors<'a> {
459    type Item = NodeRef<'a>;
460    fn next(&mut self) -> Option<NodeRef<'a>> {
461        if self.next == NONE {
462            return None;
463        }
464        let id = self.next;
465        self.next = self.doc.nodes[id as usize].parent;
466        Some(NodeRef { doc: self.doc, id })
467    }
468}
pagesift_html/dom.rs

pagesift_html/
dom.rs
