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 {
198            scope: scope.filter(NodeRef::is_element).map(|s| s.id()),
199            anchor: None,
200        };
201        node.is_element() && self.matches_in(node, &cx)
202    }
203
204    #[inline]
205    pub(super) fn matches_in(&self, el: NodeRef<'_>, cx: &Ctx) -> bool {
206        self.list.iter().any(|c| {
207            c.parts[0].tag_may_match(el) && match_complex(&c.parts, 0, el, cx) == Res::Matched
208        })
209    }
210}
211
212impl FromStr for Selector {
213    type Err = SelectorError;
214    fn from_str(s: &str) -> Result<Self, Self::Err> {
215        Selector::parse(s)
216    }
217}
218
219impl<'a> Html<'a> {
220    /// 文档里匹配选择器的所有元素，按文档顺序。
221    pub fn select<'s>(&'a self, sel: &'s Selector) -> Select<'a, 's> {
222        Select {
223            inner: self.root().descendants(),
224            sel,
225            cx: Ctx {
226                scope: None,
227                anchor: None,
228            },
229        }
230    }
231}
232
233impl<'a> NodeRef<'a> {
234    /// 后代（不含自身）里匹配选择器的元素，按文档顺序；`:scope` 匹配自身。
235    pub fn select<'s>(&self, sel: &'s Selector) -> Select<'a, 's> {
236        let mut inner = self.descendants();
237        inner.next();
238        Select {
239            inner,
240            sel,
241            cx: Ctx {
242                scope: self.is_element().then(|| self.id()),
243                anchor: None,
244            },
245        }
246    }
247}
248
249/// [`Html::select`] 和 [`NodeRef::select`] 返回的迭代器。
250pub struct Select<'a, 's> {
251    inner: Descendants<'a>,
252    sel: &'s Selector,
253    cx: Ctx,
254}
255
256impl<'a> Iterator for Select<'a, '_> {
257    type Item = NodeRef<'a>;
258    fn next(&mut self) -> Option<NodeRef<'a>> {
259        self.inner
260            .by_ref()
261            .find(|n| n.is_element() && self.sel.matches_in(*n, &self.cx))
262    }
263}
264
265mod matcher;
266mod parse;
267
268use matcher::{Ctx, Res, match_complex};
269use parse::Parser;
270
271/// HTML 规范里值不区分大小写的属性（selectors 对 HTML 元素也按这张表处理）。
272pub(super) const CASE_INSENSITIVE_ATTRS: &[&str] = &[
273    "accept",
274    "accept-charset",
275    "align",
276    "alink",
277    "axis",
278    "bgcolor",
279    "charset",
280    "checked",
281    "clear",
282    "codetype",
283    "color",
284    "compact",
285    "declare",
286    "defer",
287    "dir",
288    "direction",
289    "disabled",
290    "enctype",
291    "face",
292    "frame",
293    "hreflang",
294    "http-equiv",
295    "lang",
296    "language",
297    "link",
298    "media",
299    "method",
300    "multiple",
301    "nohref",
302    "noresize",
303    "noshade",
304    "nowrap",
305    "readonly",
306    "rel",
307    "rev",
308    "rules",
309    "scope",
310    "scrolling",
311    "selected",
312    "shape",
313    "target",
314    "text",
315    "type",
316    "valign",
317    "valuetype",
318    "vlink",
319];
320
321#[cfg(test)]
322mod tests {
323    use super::*;
324
325    const DOC: &str = r##"<!doctype html><html lang="EN"><head><title>T</title></head><body>
326        <div id="main" class="wrap  big">
327          <h1 class="title">Head</h1>
328          <p class="lead intro" data-x="foo-bar">One</p>
329          <p>Two <a href="https://a.example/x.pdf" rel="NoFollow">A</a></p>
330          <p></p>
331          <!-- c -->
332          <ul><li>1</li><li class="odd">2</li><li>3</li><li>4</li><li>5</li></ul>
333          <span lang="en-US">S</span><em>E</em><span>S2</span>
334          <svg><a href="#s">svg-a</a></svg>
335          <my-widget data-k="Ü">W</my-widget>
336        </div>
337        <table><tr><td>c1</td><td>c2</td></tr></table>
338    </body></html>"##;
339
340    fn sel(doc: &Html<'_>, s: &str) -> Vec<String> {
341        let sel = Selector::parse(s).unwrap_or_else(|e| panic!("{s}: {e}"));
342        doc.select(&sel)
343            .map(|n| {
344                let e = n.as_element().unwrap();
345                let t = n.text();
346                if t.trim().is_empty() {
347                    e.name().to_owned()
348                } else {
349                    t.trim().to_owned()
350                }
351            })
352            .collect()
353    }
354
355    #[test]
356    fn simple_selectors() {
357        let doc = Html::parse(DOC);
358        assert_eq!(sel(&doc, "h1"), ["Head"]);
359        assert_eq!(sel(&doc, "H1"), ["Head"]);
360        assert_eq!(sel(&doc, "#main > .title"), ["Head"]);
361        assert_eq!(sel(&doc, "p.lead.intro"), ["One"]);
362        assert_eq!(sel(&doc, ".wrap.big > h1"), ["Head"]);
363        assert!(sel(&doc, ".WRAP").is_empty());
364        assert_eq!(sel(&doc, "my-widget"), ["W"]);
365        assert_eq!(sel(&doc, "svg a"), ["svg-a"]);
366        assert_eq!(sel(&doc, "a").len(), 2);
367        assert_eq!(sel(&doc, "td:last-child"), ["c2"]);
368        assert_eq!(
369            sel(&doc, "*").len(),
370            doc.root().descendants().filter(|n| n.is_element()).count()
371        );
372        assert_eq!(sel(&doc, "#m\\61 in > h1"), ["Head"]);
373        assert_eq!(sel(&doc, "h1, li.odd, h1"), ["Head", "2"]);
374    }
375
376    #[test]
377    fn attribute_selectors() {
378        let doc = Html::parse(DOC);
379        assert_eq!(sel(&doc, "[data-x]"), ["One"]);
380        assert_eq!(sel(&doc, "[data-x=foo-bar]"), ["One"]);
381        assert_eq!(sel(&doc, "[data-x='foo-bar']"), ["One"]);
382        assert_eq!(sel(&doc, "[data-x|=foo]"), ["One"]);
383        assert!(sel(&doc, "[data-x|=fo]").is_empty());
384        assert_eq!(sel(&doc, "[data-x^=foo]"), ["One"]);
385        assert_eq!(sel(&doc, "[data-x$=\"bar\"]"), ["One"]);
386        assert_eq!(sel(&doc, "[data-x*='o-b']"), ["One"]);
387        assert!(sel(&doc, "[data-x*='O-B']").is_empty());
388        assert_eq!(sel(&doc, "[data-x*='O-B' i]"), ["One"]);
389        assert_eq!(sel(&doc, "[class~=intro]"), ["One"]);
390        assert!(sel(&doc, "[class~='']").is_empty());
391        assert!(sel(&doc, "[data-x^='']").is_empty());
392        assert_eq!(sel(&doc, "a[href$='.PDF' i]"), ["A"]);
393        // rel、lang 属于 HTML 不区分大小写的属性
394        assert_eq!(sel(&doc, "a[rel=nofollow]"), ["A"]);
395        assert!(sel(&doc, "a[rel=nofollow s]").is_empty());
396        assert_eq!(sel(&doc, "span[lang|=EN]"), ["S"]);
397        assert_eq!(sel(&doc, "[data-k='Ü']"), ["W"]);
398    }
399
400    #[test]
401    fn combinators() {
402        let doc = Html::parse(DOC);
403        assert_eq!(sel(&doc, "body li"), ["1", "2", "3", "4", "5"]);
404        assert!(sel(&doc, "body > li").is_empty());
405        assert_eq!(sel(&doc, "h1 + p"), ["One"]);
406        assert_eq!(sel(&doc, "h1 ~ p"), ["One", "Two A", "p"]);
407        assert_eq!(sel(&doc, "li.odd ~ li"), ["3", "4", "5"]);
408        assert_eq!(sel(&doc, "li.odd+li"), ["3"]);
409        assert_eq!(sel(&doc, "span + em + span"), ["S2"]);
410        assert_eq!(sel(&doc, "div p > a"), ["A"]);
411        assert_eq!(sel(&doc, "html body div ul > li + li ~ li").len(), 3);
412        assert_eq!(sel(&doc, "#main /* c */ h1"), ["Head"]);
413    }
414
415    #[test]
416    fn pseudo_classes() {
417        let doc = Html::parse(DOC);
418        assert_eq!(sel(&doc, "li:first-child"), ["1"]);
419        assert_eq!(sel(&doc, "li:last-child"), ["5"]);
420        assert_eq!(sel(&doc, "li:nth-child(2)"), ["2"]);
421        assert_eq!(sel(&doc, "li:nth-child(odd)"), ["1", "3", "5"]);
422        assert_eq!(sel(&doc, "li:nth-child(EVEN)"), ["2", "4"]);
423        assert_eq!(sel(&doc, "li:nth-child(-n+2)"), ["1", "2"]);
424        assert_eq!(sel(&doc, "li:nth-child(2n + 1)"), ["1", "3", "5"]);
425        assert_eq!(sel(&doc, "li:nth-child(n+4)"), ["4", "5"]);
426        assert_eq!(sel(&doc, "li:nth-last-child(2)"), ["4"]);
427        assert_eq!(sel(&doc, "li:nth-child(odd of :not(.odd))"), ["1", "4"]);
428        assert_eq!(sel(&doc, "#main > p:nth-of-type(2)"), ["Two A"]);
429        assert_eq!(sel(&doc, "#main > span:last-of-type"), ["S2"]);
430        assert_eq!(sel(&doc, "#main > :only-of-type").len(), 5);
431        assert_eq!(sel(&doc, "title:only-child"), ["T"]);
432        assert_eq!(sel(&doc, "#main > p:empty"), ["p"]);
433        assert_eq!(sel(&doc, ":root").len(), 1);
434        assert_eq!(sel(&doc, "p:not(.lead):not(:empty)"), ["Two A"]);
435        assert_eq!(sel(&doc, "p:not(.lead, :empty)"), ["Two A"]);
436        assert_eq!(sel(&doc, ":is(h1, li.odd)"), ["Head", "2"]);
437        assert_eq!(sel(&doc, ":where(#main) > h1"), ["Head"]);
438        assert_eq!(sel(&doc, "p:has(> a)"), ["Two A"]);
439        assert_eq!(sel(&doc, "h1:has(+ p.lead)"), ["Head"]);
440        assert_eq!(sel(&doc, "li:has(~ li.odd)"), ["1"]);
441        assert_eq!(sel(&doc, "div:has(li.odd)").len(), 1);
442        assert_eq!(sel(&doc, "body > :not(div, table)").len(), 0);
443    }
444
445    #[test]
446    fn scope() {
447        let doc = Html::parse(DOC);
448        let ul = doc.select(&"ul".parse().unwrap()).next().unwrap();
449        let s: Selector = ":scope > li:first-child".parse().unwrap();
450        assert_eq!(ul.select(&s).map(|n| n.text()).collect::<Vec<_>>(), ["1"]);
451        // 后代不含自身
452        let s: Selector = "ul".parse().unwrap();
453        assert_eq!(ul.select(&s).count(), 0);
454        let html = doc.select(&":scope".parse().unwrap()).collect::<Vec<_>>();
455        assert_eq!(html.len(), 1);
456        assert_eq!(html[0].tag(), Some(Tag::Html));
457    }
458
459    #[test]
460    fn errors() {
461        for (s, msg) in [
462            ("", "expected a selector"),
463            ("div[", "attribute"),
464            ("p:::x", "pseudo-elements"),
465            ("p::before", "pseudo-elements"),
466            ("a:hover", "unsupported pseudo-class `:hover`"),
467            ("a:foo(1)", "unsupported pseudo-class `:foo()`"),
468            ("a >", "expected a selector"),
469            ("a,", "expected a selector"),
470            (",a", "unexpected `,`"),
471            ("a > > b", "unexpected `>`"),
472            ("svg|a", "namespaces"),
473            ("[x=1]", "attribute value"),
474            ("[x=y z]", "unknown attribute selector flag"),
475            ("li:nth-child(2nd)", "An+B"),
476            ("li:nth-child(+ 2)", "An+B"),
477            ("li:nth-child(2n+)", "An+B"),
478            (":not(a", "expected `)`"),
479            (":not()", "unexpected `)`"),
480            ("a)", "unexpected `)`"),
481            ("#1a", "identifier"),
482            ("a.b*", "unexpected `*`"),
483            ("[a='x\ny']", "unterminated string"),
484        ] {
485            let e = Selector::parse(s).expect_err(s);
486            assert!(e.to_string().contains(msg), "{s:?}: {e}");
487        }
488        let deep = format!("{}a{}", ":not(".repeat(40), ")".repeat(40));
489        assert!(
490            Selector::parse(&deep)
491                .unwrap_err()
492                .to_string()
493                .contains("nested deeper")
494        );
495        let long = vec!["a"; 300].join(" ");
496        assert!(
497            Selector::parse(&long)
498                .unwrap_err()
499                .to_string()
500                .contains("too complex")
501        );
502        assert!(Selector::parse(&vec!["a"; 200].join(" ")).is_ok());
503    }
504
505    #[test]
506    fn descendant_backtracking_is_not_exponential() {
507        let html = format!("{}{}", "<div>".repeat(400), "<span>x</span>");
508        let doc = Html::parse(&html);
509        let s: Selector = "div div div div div div div div div div p span"
510            .parse()
511            .unwrap();
512        assert_eq!(doc.select(&s).count(), 0);
513        let s: Selector = "div div div div div div div div div div span"
514            .parse()
515            .unwrap();
516        assert_eq!(doc.select(&s).count(), 1);
517    }
518}
pagesift_html/select/mod.rs

pagesift_html/select/
mod.rs
