pagesift_html/select/
mod.rs

1//! CSS 选择器：解析成从右往左排列的复合选择器链，匹配时沿父节点、前兄弟回溯，过程中不分配内存。
2//!
3//! 支持的语法：类型、`*`、`#id`、`.class`、属性（`[a]` `=` `~=` `|=` `^=` `$=` `*=`，带 `i`/`s` 标志）、
4//! 后代/子/相邻兄弟/通用兄弟组合器、选择器列表、`:not()` `:is()` `:where()` `:has()`、
5//! `:nth-child()` `:nth-last-child()`（可带 `of S`）`:nth-of-type()` `:nth-last-of-type()`、
6//! `:first-child` `:last-child` `:only-child` `:first-of-type` `:last-of-type` `:only-of-type`、
7//! `:empty` `:root` `:scope`。
8//! 命名空间、伪元素和依赖浏览器状态的伪类（`:hover` 等）不支持，解析时报错。
9//!
10//! 语义和 scraper（Servo 的 selectors）一致：class 和 id 区分大小写（no-quirks），
11//! HTML 规范列出的一些属性（`type`、`lang` 等）的值默认不区分大小写。
12//!
13//! ```
14//! use pagesift_html::{Html, Selector};
15//!
16//! let doc = Html::parse(r#"<ul><li class="a">x</li><li class="b">y</li></ul>"#);
17//! let sel = Selector::parse("ul > li:not(.a)").unwrap();
18//! let hits: Vec<String> = doc.select(&sel).map(|n| n.text()).collect();
19//! assert_eq!(hits, ["y"]);
20//! ```
21
22use std::fmt;
23use std::str::FromStr;
24
25use crate::{Descendants, Html, NodeRef, Tag};
26
27/// 函数式伪类（`:not(` 等）的最大嵌套层数，限制解析器的递归深度。
28pub(super) const MAX_NESTING: u32 = 32;
29/// 匹配时最深的递归层数（复合选择器个数加上嵌套），限制匹配器的栈深度。
30const MAX_DEPTH: u32 = 256;
31
32/// 解析好的选择器列表（逗号分隔）。解析一次，可以在多个文档、多个线程上复用。
33#[derive(Debug, Clone)]
34pub struct Selector {
35    list: Box<[Complex]>,
36}
37
38/// 复杂选择器，例如 `ul.nav > li a`。`parts[0]` 是最右边的复合选择器（匹配主体），
39/// `parts[i].comb` 是 `parts[i]` 和它左边的 `parts[i + 1]` 之间的组合器。
40#[derive(Debug, Clone)]
41pub(super) struct Complex {
42    pub(super) parts: Box<[Compound]>,
43}
44
45#[derive(Debug, Clone)]
46pub(super) struct Compound {
47    /// 含已知标签的类型选择器时就是那个标签：匹配前先比节点的标签，多数节点不用构造 [`Element`]。
48    pub(super) tag: Option<Tag>,
49    pub(super) simples: Box<[Simple]>,
50    pub(super) comb: Comb,
51}
52
53#[derive(Debug, Clone, Copy, PartialEq, Eq)]
54pub(super) enum Comb {
55    Descendant,
56    Child,
57    Next,
58    Later,
59}
60
61#[derive(Debug, Clone)]
62pub(super) enum Simple {
63    /// 类型选择器。已知标签比枚举；`Other` 和外部内容（SVG 等）里的元素比小写名字。
64    Type(Tag, Box<str>),
65    Id(Box<str>),
66    Class(Box<str>),
67    Attr(Box<AttrSel>),
68    Nth(Box<Nth>),
69    Empty,
70    Root,
71    Scope,
72    /// `:has()` 里相对选择器的锚点，即正在判断 `:has()` 的那个元素。
73    Anchor,
74    Not(Selector),
75    Is(Selector),
76    Has(Selector),
77}
78
79impl Simple {
80    /// 复合选择器里先检查便宜的条件。
81    pub(super) fn cost(&self) -> u8 {
82        match self {
83            Simple::Type(..) => 0,
84            Simple::Id(_) => 1,
85            Simple::Class(_) => 2,
86            Simple::Attr(_) => 3,
87            Simple::Empty | Simple::Root | Simple::Scope | Simple::Anchor => 4,
88            Simple::Nth(_) => 5,
89            Simple::Not(_) | Simple::Is(_) => 6,
90            Simple::Has(_) => 7,
91        }
92    }
93}
94
95#[derive(Debug, Clone)]
96pub(super) struct AttrSel {
97    pub(super) name: Box<str>,
98    pub(super) op: AttrOp,
99    pub(super) value: Box<str>,
100    /// 值按 ASCII 不区分大小写比较。
101    pub(super) ci: bool,
102}
103
104#[derive(Debug, Clone, Copy, PartialEq, Eq)]
105pub(super) enum AttrOp {
106    Exists,
107    Equals,
108    Includes,
109    Dash,
110    Prefix,
111    Suffix,
112    Substring,
113    /// 永远不匹配：`~=` 的值为空或含空白，`^=` `$=` `*=` 的值为空。
114    Never,
115}
116
117/// `:nth-*()`：位置满足 `a*n + b`（n ≥ 0）。
118#[derive(Debug, Clone)]
119pub(super) struct Nth {
120    pub(super) a: i32,
121    pub(super) b: i32,
122    /// 从后往前数。
123    pub(super) last: bool,
124    /// 只数同类型的兄弟。
125    pub(super) of_type: bool,
126    /// `of S`：只数匹配 S 的兄弟，自身也要匹配 S。
127    pub(super) of: Option<Selector>,
128}
129
130impl Nth {
131    pub(super) fn simple(a: i32, b: i32, last: bool, of_type: bool) -> Simple {
132        Simple::Nth(Box::new(Nth {
133            a,
134            b,
135            last,
136            of_type,
137            of: None,
138        }))
139    }
140}
141
142/// 选择器语法错误：出错位置（字节偏移）和原因。
143#[derive(Debug, Clone, PartialEq, Eq)]
144pub struct SelectorError {
145    offset: usize,
146    message: String,
147}
148
149impl SelectorError {
150    /// 出错位置在选择器字符串里的字节偏移。
151    pub fn offset(&self) -> usize {
152        self.offset
153    }
154
155    pub fn message(&self) -> &str {
156        &self.message
157    }
158}
159
160impl fmt::Display for SelectorError {
161    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
162        write!(f, "{} at offset {}", self.message, self.offset)
163    }
164}
165
166impl std::error::Error for SelectorError {}
167
168impl Selector {
169    /// 解析选择器列表。语法错误、不支持的语法返回错误，不会 panic。
170    pub fn parse(s: &str) -> Result<Selector, SelectorError> {
171        let mut p = Parser {
172            s,
173            b: s.as_bytes(),
174            pos: 0,
175            nesting: 0,
176        };
177        let (sel, depth) = p.list(false, false)?;
178        if p.pos < p.b.len() {
179            return Err(p.unexpected());
180        }
181        if depth > MAX_DEPTH {
182            return Err(SelectorError {
183                offset: 0,
184                message: format!("selector is too complex (matching depth {depth} > {MAX_DEPTH})"),
185            });
186        }
187        Ok(sel)
188    }
189
190    /// 元素是否匹配。`:scope` 匹配根元素。不是元素的节点永远不匹配。
191    pub fn matches(&self, node: NodeRef<'_>) -> bool {
192        self.matches_with_scope(node, None)
193    }
194
195    /// 元素是否匹配，`:scope` 匹配 `scope`（为 `None` 时匹配根元素）。
196    pub fn matches_with_scope(&self, node: NodeRef<'_>, scope: Option<NodeRef<'_>>) -> bool {
197        let cx = Ctx::new(scope.filter(NodeRef::is_element).map(|s| s.id()), None);
198        node.is_element() && self.matches_in(node, &cx)
199    }
200
201    #[inline]
202    pub(super) fn matches_in(&self, el: NodeRef<'_>, cx: &Ctx) -> bool {
203        self.list.iter().any(|c| {
204            c.parts[0].tag_may_match(el) && match_complex(&c.parts, 0, el, cx) == Res::Matched
205        })
206    }
207}
208
209impl FromStr for Selector {
210    type Err = SelectorError;
211    fn from_str(s: &str) -> Result<Self, Self::Err> {
212        Selector::parse(s)
213    }
214}
215
216impl<'a> Html<'a> {
217    /// 文档里匹配选择器的所有元素，按文档顺序。
218    pub fn select<'s>(&'a self, sel: &'s Selector) -> Select<'a, 's> {
219        Select {
220            inner: self.root().descendants(),
221            sel,
222            cx: Ctx::new(None, None),
223        }
224    }
225}
226
227impl<'a> NodeRef<'a> {
228    /// 后代（不含自身）里匹配选择器的元素，按文档顺序；`:scope` 匹配自身。
229    pub fn select<'s>(&self, sel: &'s Selector) -> Select<'a, 's> {
230        let mut inner = self.descendants();
231        inner.next();
232        Select {
233            inner,
234            sel,
235            cx: Ctx::new(self.is_element().then(|| self.id()), None),
236        }
237    }
238}
239
240/// [`Html::select`] 和 [`NodeRef::select`] 返回的迭代器。
241pub struct Select<'a, 's> {
242    inner: Descendants<'a>,
243    sel: &'s Selector,
244    cx: Ctx,
245}
246
247impl<'a> Iterator for Select<'a, '_> {
248    type Item = NodeRef<'a>;
249    fn next(&mut self) -> Option<NodeRef<'a>> {
250        self.inner
251            .by_ref()
252            .find(|n| n.is_element() && self.sel.matches_in(*n, &self.cx))
253    }
254}
255
256mod matcher;
257mod nth;
258mod parse;
259
260use matcher::{Ctx, Res, match_complex};
261use parse::Parser;
262
263/// HTML 规范里值不区分大小写的属性（selectors 对 HTML 元素也按这张表处理）。
264pub(super) const CASE_INSENSITIVE_ATTRS: &[&str] = &[
265    "accept",
266    "accept-charset",
267    "align",
268    "alink",
269    "axis",
270    "bgcolor",
271    "charset",
272    "checked",
273    "clear",
274    "codetype",
275    "color",
276    "compact",
277    "declare",
278    "defer",
279    "dir",
280    "direction",
281    "disabled",
282    "enctype",
283    "face",
284    "frame",
285    "hreflang",
286    "http-equiv",
287    "lang",
288    "language",
289    "link",
290    "media",
291    "method",
292    "multiple",
293    "nohref",
294    "noresize",
295    "noshade",
296    "nowrap",
297    "readonly",
298    "rel",
299    "rev",
300    "rules",
301    "scope",
302    "scrolling",
303    "selected",
304    "shape",
305    "target",
306    "text",
307    "type",
308    "valign",
309    "valuetype",
310    "vlink",
311];
312
313#[cfg(test)]
314mod tests {
315    use super::*;
316
317    const DOC: &str = r##"<!doctype html><html lang="EN"><head><title>T</title></head><body>
318        <div id="main" class="wrap  big">
319          <h1 class="title">Head</h1>
320          <p class="lead intro" data-x="foo-bar">One</p>
321          <p>Two <a href="https://a.example/x.pdf" rel="NoFollow">A</a></p>
322          <p></p>
323          <!-- c -->
324          <ul><li>1</li><li class="odd">2</li><li>3</li><li>4</li><li>5</li></ul>
325          <span lang="en-US">S</span><em>E</em><span>S2</span>
326          <svg><a href="#s">svg-a</a></svg>
327          <my-widget data-k="Ü">W</my-widget>
328        </div>
329        <table><tr><td>c1</td><td>c2</td></tr></table>
330    </body></html>"##;
331
332    fn sel(doc: &Html<'_>, s: &str) -> Vec<String> {
333        let sel = Selector::parse(s).unwrap_or_else(|e| panic!("{s}: {e}"));
334        doc.select(&sel)
335            .map(|n| {
336                let e = n.as_element().unwrap();
337                let t = n.text();
338                if t.trim().is_empty() {
339                    e.name().to_owned()
340                } else {
341                    t.trim().to_owned()
342                }
343            })
344            .collect()
345    }
346
347    #[test]
348    fn simple_selectors() {
349        let doc = Html::parse(DOC);
350        assert_eq!(sel(&doc, "h1"), ["Head"]);
351        assert_eq!(sel(&doc, "H1"), ["Head"]);
352        assert_eq!(sel(&doc, "#main > .title"), ["Head"]);
353        assert_eq!(sel(&doc, "p.lead.intro"), ["One"]);
354        assert_eq!(sel(&doc, ".wrap.big > h1"), ["Head"]);
355        assert!(sel(&doc, ".WRAP").is_empty());
356        assert_eq!(sel(&doc, "my-widget"), ["W"]);
357        assert_eq!(sel(&doc, "svg a"), ["svg-a"]);
358        assert_eq!(sel(&doc, "a").len(), 2);
359        assert_eq!(sel(&doc, "td:last-child"), ["c2"]);
360        assert_eq!(
361            sel(&doc, "*").len(),
362            doc.root().descendants().filter(|n| n.is_element()).count()
363        );
364        assert_eq!(sel(&doc, "#m\\61 in > h1"), ["Head"]);
365        assert_eq!(sel(&doc, "h1, li.odd, h1"), ["Head", "2"]);
366    }
367
368    #[test]
369    fn attribute_selectors() {
370        let doc = Html::parse(DOC);
371        assert_eq!(sel(&doc, "[data-x]"), ["One"]);
372        assert_eq!(sel(&doc, "[data-x=foo-bar]"), ["One"]);
373        assert_eq!(sel(&doc, "[data-x='foo-bar']"), ["One"]);
374        assert_eq!(sel(&doc, "[data-x|=foo]"), ["One"]);
375        assert!(sel(&doc, "[data-x|=fo]").is_empty());
376        assert_eq!(sel(&doc, "[data-x^=foo]"), ["One"]);
377        assert_eq!(sel(&doc, "[data-x$=\"bar\"]"), ["One"]);
378        assert_eq!(sel(&doc, "[data-x*='o-b']"), ["One"]);
379        assert!(sel(&doc, "[data-x*='O-B']").is_empty());
380        assert_eq!(sel(&doc, "[data-x*='O-B' i]"), ["One"]);
381        assert_eq!(sel(&doc, "[class~=intro]"), ["One"]);
382        assert!(sel(&doc, "[class~='']").is_empty());
383        assert!(sel(&doc, "[data-x^='']").is_empty());
384        assert_eq!(sel(&doc, "a[href$='.PDF' i]"), ["A"]);
385        // rel、lang 属于 HTML 不区分大小写的属性
386        assert_eq!(sel(&doc, "a[rel=nofollow]"), ["A"]);
387        assert!(sel(&doc, "a[rel=nofollow s]").is_empty());
388        assert_eq!(sel(&doc, "span[lang|=EN]"), ["S"]);
389        assert_eq!(sel(&doc, "[data-k='Ü']"), ["W"]);
390    }
391
392    #[test]
393    fn combinators() {
394        let doc = Html::parse(DOC);
395        assert_eq!(sel(&doc, "body li"), ["1", "2", "3", "4", "5"]);
396        assert!(sel(&doc, "body > li").is_empty());
397        assert_eq!(sel(&doc, "h1 + p"), ["One"]);
398        assert_eq!(sel(&doc, "h1 ~ p"), ["One", "Two A", "p"]);
399        assert_eq!(sel(&doc, "li.odd ~ li"), ["3", "4", "5"]);
400        assert_eq!(sel(&doc, "li.odd+li"), ["3"]);
401        assert_eq!(sel(&doc, "span + em + span"), ["S2"]);
402        assert_eq!(sel(&doc, "div p > a"), ["A"]);
403        assert_eq!(sel(&doc, "html body div ul > li + li ~ li").len(), 3);
404        assert_eq!(sel(&doc, "#main /* c */ h1"), ["Head"]);
405    }
406
407    #[test]
408    fn pseudo_classes() {
409        let doc = Html::parse(DOC);
410        assert_eq!(sel(&doc, "li:first-child"), ["1"]);
411        assert_eq!(sel(&doc, "li:last-child"), ["5"]);
412        assert_eq!(sel(&doc, "li:nth-child(2)"), ["2"]);
413        assert_eq!(sel(&doc, "li:nth-child(odd)"), ["1", "3", "5"]);
414        assert_eq!(sel(&doc, "li:nth-child(EVEN)"), ["2", "4"]);
415        assert_eq!(sel(&doc, "li:nth-child(-n+2)"), ["1", "2"]);
416        assert_eq!(sel(&doc, "li:nth-child(2n + 1)"), ["1", "3", "5"]);
417        assert_eq!(sel(&doc, "li:nth-child(n+4)"), ["4", "5"]);
418        assert_eq!(sel(&doc, "li:nth-last-child(2)"), ["4"]);
419        assert_eq!(sel(&doc, "li:nth-child(odd of :not(.odd))"), ["1", "4"]);
420        assert_eq!(sel(&doc, "#main > p:nth-of-type(2)"), ["Two A"]);
421        assert_eq!(sel(&doc, "#main > span:last-of-type"), ["S2"]);
422        assert_eq!(sel(&doc, "#main > :only-of-type").len(), 5);
423        assert_eq!(sel(&doc, "title:only-child"), ["T"]);
424        assert_eq!(sel(&doc, "#main > p:empty"), ["p"]);
425        assert_eq!(sel(&doc, ":root").len(), 1);
426        assert_eq!(sel(&doc, "p:not(.lead):not(:empty)"), ["Two A"]);
427        assert_eq!(sel(&doc, "p:not(.lead, :empty)"), ["Two A"]);
428        assert_eq!(sel(&doc, ":is(h1, li.odd)"), ["Head", "2"]);
429        assert_eq!(sel(&doc, ":where(#main) > h1"), ["Head"]);
430        assert_eq!(sel(&doc, "p:has(> a)"), ["Two A"]);
431        assert_eq!(sel(&doc, "h1:has(+ p.lead)"), ["Head"]);
432        assert_eq!(sel(&doc, "li:has(~ li.odd)"), ["1"]);
433        assert_eq!(sel(&doc, "div:has(li.odd)").len(), 1);
434        assert_eq!(sel(&doc, "body > :not(div, table)").len(), 0);
435    }
436
437    #[test]
438    fn scope() {
439        let doc = Html::parse(DOC);
440        let ul = doc.select(&"ul".parse().unwrap()).next().unwrap();
441        let s: Selector = ":scope > li:first-child".parse().unwrap();
442        assert_eq!(ul.select(&s).map(|n| n.text()).collect::<Vec<_>>(), ["1"]);
443        // 后代不含自身
444        let s: Selector = "ul".parse().unwrap();
445        assert_eq!(ul.select(&s).count(), 0);
446        let html = doc.select(&":scope".parse().unwrap()).collect::<Vec<_>>();
447        assert_eq!(html.len(), 1);
448        assert_eq!(html[0].tag(), Some(Tag::Html));
449    }
450
451    #[test]
452    fn errors() {
453        for (s, msg) in [
454            ("", "expected a selector"),
455            ("div[", "attribute"),
456            ("p:::x", "pseudo-elements"),
457            ("p::before", "pseudo-elements"),
458            ("a:hover", "unsupported pseudo-class `:hover`"),
459            ("a:foo(1)", "unsupported pseudo-class `:foo()`"),
460            ("a >", "expected a selector"),
461            ("a,", "expected a selector"),
462            (",a", "unexpected `,`"),
463            ("a > > b", "unexpected `>`"),
464            ("svg|a", "namespaces"),
465            ("[x=1]", "attribute value"),
466            ("[x=y z]", "unknown attribute selector flag"),
467            ("li:nth-child(2nd)", "An+B"),
468            ("li:nth-child(+ 2)", "An+B"),
469            ("li:nth-child(2n+)", "An+B"),
470            (":not(a", "expected `)`"),
471            (":not()", "unexpected `)`"),
472            ("a)", "unexpected `)`"),
473            ("#1a", "identifier"),
474            ("a.b*", "unexpected `*`"),
475            ("[a='x\ny']", "unterminated string"),
476        ] {
477            let e = Selector::parse(s).expect_err(s);
478            assert!(e.to_string().contains(msg), "{s:?}: {e}");
479        }
480        let deep = format!("{}a{}", ":not(".repeat(40), ")".repeat(40));
481        assert!(
482            Selector::parse(&deep)
483                .unwrap_err()
484                .to_string()
485                .contains("nested deeper")
486        );
487        let long = vec!["a"; 300].join(" ");
488        assert!(
489            Selector::parse(&long)
490                .unwrap_err()
491                .to_string()
492                .contains("too complex")
493        );
494        assert!(Selector::parse(&vec!["a"; 200].join(" ")).is_ok());
495    }
496
497    #[test]
498    fn descendant_backtracking_is_not_exponential() {
499        let html = format!("{}{}", "<div>".repeat(400), "<span>x</span>");
500        let doc = Html::parse(&html);
501        let s: Selector = "div div div div div div div div div div p span"
502            .parse()
503            .unwrap();
504        assert_eq!(doc.select(&s).count(), 0);
505        let s: Selector = "div div div div div div div div div div span"
506            .parse()
507            .unwrap();
508        assert_eq!(doc.select(&s).count(), 1);
509    }
510}
pagesift_html/select/mod.rs

pagesift_html/select/
mod.rs
