Skip to main content

parsec/
css.rs

1// SPDX-License-Identifier: Apache-2.0
2// Copyright 2026 James Conway
3
4//! CSS selectors, as Selectors Level 4 defines them and browsers match
5//! them in a static page: parsed once, matched right to left.
6//!
7//! What browsers do on a page nobody is looking at decides the rest:
8//! `:hover`, `:focus` and the like parse but never match, as does a
9//! pseudo-element (`::before`), since no element in a tree is one;
10//! `:scope` is the element a query runs from, and ids and classes compare
11//! exactly except in a quirks-mode document.
12
13use std::cell::{Cell, RefCell};
14use std::cmp::Reverse;
15use std::collections::{BTreeMap, BinaryHeap, HashMap};
16use std::rc::Rc;
17use std::time::{Duration, Instant};
18
19use crate::dom::{AttrNs, Data, Document, NONE, NodeId, Ns, Quirks};
20use crate::pattern::Pattern;
21use crate::tags::Tag;
22
23/// A selector that couldn't be parsed, and why.
24#[derive(Debug, Clone, PartialEq, Eq)]
25pub struct SelectorError {
26    pub reason: String,
27}
28
29impl std::fmt::Display for SelectorError {
30    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
31        f.write_str(&self.reason)
32    }
33}
34
35impl std::error::Error for SelectorError {}
36
37fn error<T>(reason: impl Into<String>) -> Result<T, SelectorError> {
38    Err(SelectorError {
39        reason: reason.into(),
40    })
41}
42
43/// A comma-separated list of selectors; an element matches if any does.
44#[derive(Debug, Clone)]
45pub struct SelectorList(Vec<Complex>);
46
47/// Compound selectors joined by combinators, kept right to left: `parts[0]`
48/// is the subject, and each part's combinator relates it to the next one.
49#[derive(Debug, Clone)]
50struct Complex {
51    parts: Vec<(Compound, Combinator)>,
52}
53
54#[derive(Debug, Clone, Copy, PartialEq, Eq)]
55enum Combinator {
56    /// The leftmost part has none.
57    None,
58    Descendant,
59    Child,
60    NextSibling,
61    SubsequentSibling,
62    /// `||`: a table cell in a column the `col` on its left covers.
63    Column,
64}
65
66#[derive(Debug, Clone, Default)]
67struct Compound(Vec<Simple>);
68
69#[derive(Debug, Clone)]
70enum Simple {
71    /// A type selector, lowercased for HTML elements, as written for the
72    /// rest.
73    Type {
74        lower: String,
75        exact: String,
76        /// The lowercased name as a known tag, so HTML elements compare
77        /// by number.
78        tag: Tag,
79    },
80    Id(String),
81    Class(String),
82    Attr(AttrSelector),
83    Pseudo(Pseudo),
84    /// The element a `:has()` argument is relative to.
85    Anchor,
86    /// The element is in this namespace: a declared prefix, or the default.
87    Ns(Ns),
88}
89
90#[derive(Debug, Clone)]
91struct AttrSelector {
92    lower: String,
93    exact: String,
94    /// `[*|name]`: in any namespace, or none.
95    any_ns: bool,
96    /// `[prefix|name]` with the prefix declared for attributes: only in
97    /// that namespace.
98    in_ns: Option<AttrNs>,
99    op: AttrOp,
100    value: String,
101    case: Case,
102}
103
104#[derive(Debug, Clone, Copy, PartialEq, Eq)]
105enum AttrOp {
106    Exists,
107    Equals,
108    Includes,
109    DashMatch,
110    Prefix,
111    Suffix,
112    Substring,
113}
114
115#[derive(Debug, Clone, Copy, PartialEq, Eq)]
116enum Case {
117    /// As the document language says: HTML lists some attributes whose
118    /// values compare without case.
119    Default,
120    Insensitive,
121    Sensitive,
122}
123
124#[derive(Debug, Clone)]
125enum Pseudo {
126    Not(SelectorList),
127    Is(SelectorList),
128    /// Matches as `:is()` does, with no specificity.
129    Where(SelectorList),
130    Has(SelectorList),
131    Nth {
132        a: i32,
133        b: i32,
134        last: bool,
135        of_type: bool,
136        of: Option<SelectorList>,
137    },
138    Only {
139        of_type: bool,
140    },
141    Empty,
142    Root,
143    Scope,
144    AnyLink,
145    Checked,
146    Disabled,
147    Enabled,
148    Required,
149    Optional,
150    ReadWrite,
151    ReadOnly,
152    PlaceholderShown,
153    /// `:blank`: a field a user types text into that holds none.
154    Blank,
155    /// `:defined`: everything but an HTML custom element, which a static
156    /// document never defines.
157    Defined,
158    Target,
159    TargetWithin,
160    LocalLink,
161    /// `:lang()`'s language ranges, lowercased.
162    Lang(Vec<String>),
163    /// `:dir(rtl)` when true, `:dir(ltr)` when false.
164    Dir(bool),
165    Default,
166    Indeterminate,
167    InRange,
168    OutOfRange,
169    Valid,
170    Invalid,
171    /// A state no static page is in: `:hover`, `:focus`, `:visited`...
172    Never,
173    /// A pseudo-element, `::before` or `::part(x)`: valid in a selector, as
174    /// a browser's querySelector has it, and never an element in the tree.
175    Element,
176    /// `:host`, or `:host(<compound>)`: the shadow host, seen from inside
177    /// its shadow tree.
178    Host(Option<Box<Compound>>),
179    /// `:host-context(<compound>)`: the shadow host, when it or a
180    /// shadow-including ancestor matches.
181    HostContext(Box<Compound>),
182    /// `::slotted(<compound>)`, first in its compound: an element assigned
183    /// (after flattening) to a slot that the rest of the selector matches.
184    Slotted(Box<Compound>),
185    /// `:heading` (empty) or `:heading(1, 3)`: an h1-h6 of a listed level.
186    Heading(Vec<i64>),
187    /// `:nth-col()` and `:nth-last-col()`: a table cell in a column at
188    /// that position.
189    NthCol {
190        a: i32,
191        b: i32,
192        last: bool,
193    },
194}
195
196// ---- parsing ---------------------------------------------------------------
197
198struct Parser<'a> {
199    s: &'a str,
200    pos: usize,
201    /// How deep in `:not()`, `:is()` and the like it is; parsing and
202    /// matching both recurse, so a limit keeps a pathological selector
203    /// from overflowing the stack.
204    depth: u32,
205    /// Inside `:has()`, where Selectors 4 doesn't allow another `:has()`.
206    in_has: bool,
207    /// Inside `:host()`, `:host-context()` or `::slotted()`, whose argument
208    /// is a compound: no combinator anywhere in it, `:not()`'s included.
209    compound_only: bool,
210    opts: &'a ParseOptions<'a>,
211}
212
213/// Nesting deeper than any real selector, and shallow enough for a
214/// thread's stack.
215const MAX_DEPTH: u32 = 32;
216
217fn is_name_start(c: char) -> bool {
218    c.is_ascii_alphabetic() || c == '_' || !c.is_ascii()
219}
220
221fn is_name(c: char) -> bool {
222    is_name_start(c) || c.is_ascii_digit() || c == '-'
223}
224
225impl<'a> Parser<'a> {
226    fn peek(&self) -> Option<char> {
227        self.s[self.pos..].chars().next()
228    }
229
230    fn peek_at(&self, n: usize) -> Option<char> {
231        self.s[self.pos..].chars().nth(n)
232    }
233
234    fn bump(&mut self) -> Option<char> {
235        let c = self.peek()?;
236        self.pos += c.len_utf8();
237        Some(c)
238    }
239
240    fn eat(&mut self, c: char) -> bool {
241        if self.peek() == Some(c) {
242            self.pos += c.len_utf8();
243            true
244        } else {
245            false
246        }
247    }
248
249    /// Whitespace and comments; true if there was whitespace. A comment
250    /// alone separates nothing, so `a/**/.b` is the compound `a.b`.
251    fn skip_space(&mut self) -> bool {
252        let mut space = false;
253        loop {
254            if matches!(self.peek(), Some(' ' | '\t' | '\n' | '\r' | '\x0C')) {
255                self.pos += 1;
256                space = true;
257            } else if !self.skip_comment() {
258                return space;
259            }
260        }
261    }
262
263    /// One comment, if one starts here. An unclosed one runs to the end.
264    fn skip_comment(&mut self) -> bool {
265        if !self.s[self.pos..].starts_with("/*") {
266            return false;
267        }
268        match self.s[self.pos + 2..].find("*/") {
269            Some(end) => self.pos += end + 4,
270            None => self.pos = self.s.len(),
271        }
272        true
273    }
274
275    fn at_end(&self) -> bool {
276        self.pos >= self.s.len()
277    }
278
279    /// A backslash escape, the backslash already read.
280    fn escape(&mut self) -> Result<char, SelectorError> {
281        let Some(c) = self.peek() else {
282            return Ok('\u{FFFD}');
283        };
284        if c == '\n' {
285            return error("a backslash before a newline");
286        }
287        if c.is_ascii_hexdigit() {
288            let start = self.pos;
289            while self.pos - start < 6 && self.peek().is_some_and(|c| c.is_ascii_hexdigit()) {
290                self.pos += 1;
291            }
292            let code = u32::from_str_radix(&self.s[start..self.pos], 16).unwrap();
293            if matches!(self.peek(), Some(' ' | '\t' | '\n' | '\x0C')) {
294                self.pos += 1;
295            }
296            return Ok(match code {
297                0 | 0xD800..=0xDFFF | 0x11_0000.. => '\u{FFFD}',
298                _ => char::from_u32(code).unwrap_or('\u{FFFD}'),
299            });
300        }
301        self.pos += c.len_utf8();
302        Ok(c)
303    }
304
305    fn starts_name(&self) -> bool {
306        match self.peek() {
307            Some('\\') => self.peek_at(1).is_some_and(|c| c != '\n'),
308            Some('-') => match self.peek_at(1) {
309                Some(c) if is_name_start(c) || c == '-' => true,
310                Some('\\') => self.peek_at(2).is_some_and(|c| c != '\n'),
311                _ => false,
312            },
313            Some(c) => is_name_start(c),
314            None => false,
315        }
316    }
317
318    fn name(&mut self) -> Result<String, SelectorError> {
319        let mut out = String::new();
320        loop {
321            match self.peek() {
322                Some('\\') if self.peek_at(1).is_some_and(|c| c != '\n') => {
323                    self.pos += 1;
324                    out.push(self.escape()?);
325                }
326                Some(c) if is_name(c) => {
327                    self.pos += c.len_utf8();
328                    out.push(c);
329                }
330                _ => return Ok(out),
331            }
332        }
333    }
334
335    fn ident(&mut self) -> Result<String, SelectorError> {
336        if !self.starts_name() {
337            return error(format!("expected a name at {:?}", &self.s[self.pos..]));
338        }
339        self.name()
340    }
341
342    fn string(&mut self, quote: char) -> Result<String, SelectorError> {
343        let mut out = String::new();
344        loop {
345            match self.bump() {
346                None => return Ok(out),
347                Some(c) if c == quote => return Ok(out),
348                Some('\n') => return error("a newline in a string"),
349                Some('\\') => match self.peek() {
350                    Some('\n') => self.pos += 1,
351                    None => {}
352                    Some(_) => out.push(self.escape()?),
353                },
354                Some(c) => out.push(c),
355            }
356        }
357    }
358
359    fn selector_list(&mut self, forgiving: bool) -> Result<SelectorList, SelectorError> {
360        let mut out = Vec::new();
361        loop {
362            self.skip_space();
363            let start = self.pos;
364            match self.complex(false) {
365                Ok(c) => out.push(c),
366                Err(e) if !forgiving => return Err(e),
367                Err(e) => {
368                    // Forgiving: skip to the next comma at this level. A
369                    // block the bad argument opens and never closes swallows
370                    // the rest of the input, the function's own `)` with
371                    // it, so nothing is left to forgive: browsers refuse
372                    // `:is(#[x)` while taking `:is(#, .a)`.
373                    self.pos = start;
374                    if self.skip_to_comma() {
375                        return Err(e);
376                    }
377                }
378            }
379            self.skip_space();
380            if !self.eat(',') {
381                break;
382            }
383        }
384        if out.is_empty() && !forgiving {
385            return error("an empty selector");
386        }
387        Ok(SelectorList(out))
388    }
389
390    /// Skips to the next `,` or closing bracket at this level. True when
391    /// the input ended inside a block opened on the way.
392    fn skip_to_comma(&mut self) -> bool {
393        // The closers of the blocks open so far: a `)` inside `[` is just
394        // a token.
395        let mut open: Vec<char> = Vec::new();
396        while let Some(c) = self.peek() {
397            match c {
398                '(' => open.push(')'),
399                '[' => open.push(']'),
400                ')' | ']' | ',' if open.is_empty() => return false,
401                ')' | ']' if open.last() == Some(&c) => {
402                    open.pop();
403                }
404                '"' | '\'' => {
405                    self.pos += 1;
406                    let _ = self.string(c);
407                    continue;
408                }
409                '\\' => self.pos += 1,
410                _ => {}
411            }
412            self.bump();
413        }
414        !open.is_empty()
415    }
416
417    /// A complex selector; `relative` for `:has()`, where it may start with
418    /// a combinator and is relative to the anchor.
419    fn complex(&mut self, relative: bool) -> Result<Complex, SelectorError> {
420        let mut parts: Vec<(Compound, Combinator)> = Vec::new();
421        let mut pending = Combinator::None;
422        if relative {
423            self.skip_space();
424            pending = self.combinator().unwrap_or(Combinator::Descendant);
425            parts.push((Compound(vec![Simple::Anchor]), Combinator::None));
426            self.skip_space();
427        }
428        loop {
429            let compound = self.compound()?;
430            let has_element = compound
431                .0
432                .iter()
433                .any(|s| matches!(s, Simple::Pseudo(Pseudo::Element | Pseudo::Slotted(_))));
434            if let Some(last) = parts.last_mut() {
435                last.1 = pending;
436            }
437            parts.push((compound, Combinator::None));
438            let space = self.skip_space();
439            if self.at_end() || matches!(self.peek(), Some(',' | ')')) {
440                break;
441            }
442            if has_element {
443                return error("a pseudo-element must end the selector");
444            }
445            if self.compound_only && !relative {
446                return error(
447                    "only a compound selector can go in :host(), :host-context() or ::slotted()",
448                );
449            }
450            pending = match self.combinator() {
451                Some(c) => {
452                    self.skip_space();
453                    c
454                }
455                None if space => Combinator::Descendant,
456                None => return error(format!("unexpected {:?}", &self.s[self.pos..])),
457            };
458        }
459        // Stored left to right while reading; matched right to left.
460        let mut combinators: Vec<Combinator> = parts.iter().map(|p| p.1).collect();
461        combinators.pop();
462        parts.reverse();
463        combinators.reverse();
464        for (i, c) in combinators.into_iter().enumerate() {
465            parts[i].1 = c;
466        }
467        let last = parts.len() - 1;
468        parts[last].1 = Combinator::None;
469        Ok(Complex { parts })
470    }
471
472    fn combinator(&mut self) -> Option<Combinator> {
473        match self.peek()? {
474            '>' => {
475                self.pos += 1;
476                Some(Combinator::Child)
477            }
478            '+' => {
479                self.pos += 1;
480                Some(Combinator::NextSibling)
481            }
482            '~' => {
483                self.pos += 1;
484                Some(Combinator::SubsequentSibling)
485            }
486            '|' if self.peek_at(1) == Some('|') => {
487                self.pos += 2;
488                Some(Combinator::Column)
489            }
490            _ => None,
491        }
492    }
493
494    fn compound(&mut self) -> Result<Compound, SelectorError> {
495        let mut simple = Vec::new();
496        let mut universal = false;
497        // Whether the compound has a type selector or `*`, and whether it
498        // had a namespace prefix, which the default doesn't override.
499        let mut explicit = false;
500        let mut prefixed = false;
501        // A type selector or universal, with an optional namespace prefix.
502        let bar = |p: &Self| p.peek() == Some('|') && p.peek_at(1) != Some('|');
503        if self.peek() == Some('*') || self.starts_name() || bar(self) {
504            explicit = true;
505            let star = self.eat('*');
506            universal = star;
507            let name = if star || self.peek() == Some('|') {
508                String::new()
509            } else {
510                self.name()?
511            };
512            if bar(self) && self.peek_at(1) != Some('=') {
513                self.pos += 1;
514                prefixed = true;
515                // `*|` is any namespace; `|x` asks for none, which no
516                // element in an HTML document has; any other prefix must
517                // be declared.
518                let ns = match (star, name.is_empty()) {
519                    (true, _) => None,
520                    (false, true) => {
521                        simple.push(Simple::Pseudo(Pseudo::Never));
522                        None
523                    }
524                    (false, false) => Some(self.namespace(&name)?),
525                };
526                if !self.eat('*') {
527                    let local = self.ident()?;
528                    simple.push(type_selector(local));
529                }
530                if let Some(ns) = ns {
531                    simple.push(Simple::Ns(ns));
532                }
533            } else if !star {
534                simple.push(type_selector(name));
535            }
536        }
537        // After a pseudo-element only pseudo-classes that don't read the
538        // tree, and more pseudo-elements, may follow: `::before:hover`, not
539        // `::before.x` or `::part(x):has(li)`; after `::slotted()` only
540        // pseudo-elements. Some(true) is after `::slotted()`.
541        let mut after_element: Option<bool> = None;
542        loop {
543            while self.skip_comment() {}
544            if after_element.is_some() && matches!(self.peek(), Some('#' | '.' | '[')) {
545                return error("only a pseudo-class can follow a pseudo-element");
546            }
547            match self.peek() {
548                Some('#') => {
549                    self.pos += 1;
550                    // An ID is an identifier, so `#1a` isn't one.
551                    if !self.starts_name() {
552                        return error(match self.peek() {
553                            Some(c) if c.is_ascii_digit() => "an ID can't start with a digit",
554                            Some('-') if self.peek_at(1).is_some_and(|c| c.is_ascii_digit()) => {
555                                "an ID can't start with a hyphen and a digit"
556                            }
557                            _ => "a # with no ID after it",
558                        });
559                    }
560                    simple.push(Simple::Id(self.name()?));
561                }
562                Some('.') => {
563                    self.pos += 1;
564                    simple.push(Simple::Class(self.ident()?));
565                }
566                Some('[') => {
567                    self.pos += 1;
568                    let declared = self.declared_attr_prefix();
569                    let mut attr = self.attr()?;
570                    simple.push(match declared {
571                        // An element namespace: no attribute is in one.
572                        Some(None) => Simple::Pseudo(Pseudo::Never),
573                        Some(Some(ns)) => {
574                            attr.in_ns = Some(ns);
575                            Simple::Attr(attr)
576                        }
577                        None => Simple::Attr(attr),
578                    });
579                }
580                Some(':') if self.peek_at(1) == Some(':') => {
581                    if self.depth > 0 {
582                        return error("a pseudo-element can't go inside a pseudo-class");
583                    }
584                    self.pos += 2;
585                    match self.pseudo_element()? {
586                        // First, so matching finds it at once.
587                        Some(arg) => {
588                            simple.insert(0, Simple::Pseudo(Pseudo::Slotted(Box::new(arg))));
589                            after_element = Some(true);
590                        }
591                        None => {
592                            simple.push(Simple::Pseudo(Pseudo::Element));
593                            after_element = Some(false);
594                        }
595                    }
596                }
597                Some(':') => {
598                    self.pos += 1;
599                    let pseudo = self.pseudo()?;
600                    let element = matches!(pseudo, Pseudo::Element);
601                    match after_element {
602                        Some(true) if !element => {
603                            return error("only a pseudo-element can follow ::slotted()");
604                        }
605                        Some(_) if pseudo.reads_the_tree() => {
606                            return error(
607                                "a tree-structural pseudo-class can't follow a pseudo-element",
608                            );
609                        }
610                        _ => {}
611                    }
612                    if element {
613                        after_element = Some(false);
614                    }
615                    simple.push(Simple::Pseudo(pseudo));
616                }
617                _ => break,
618            }
619        }
620        if simple.is_empty() && !universal {
621            return error(match self.peek() {
622                Some(c) => format!("unexpected {c:?}"),
623                None => "a selector ends early".to_string(),
624            });
625        }
626        // The default namespace limits a compound without a prefix, but as
627        // Selectors 4 says for :is(), not one inside a functional
628        // pseudo-class that has no type selector or `*`.
629        // shortcut: that exemption covers every compound in the argument,
630        // not just its subject; split them if a selector ever needs it.
631        if let Some(ns) = self.opts.default
632            && !prefixed
633            && (explicit || self.depth == 0)
634        {
635            simple.push(Simple::Ns(ns));
636        }
637        Ok(Compound(simple))
638    }
639
640    fn namespace(&self, prefix: &str) -> Result<Ns, SelectorError> {
641        match self.opts.namespaces.iter().find(|(p, _)| *p == prefix) {
642            Some(&(_, ns)) => Ok(ns),
643            None => error(format!("namespace prefix {prefix:?} isn't declared")),
644        }
645    }
646
647    /// Eats a declared `prefix|` at the start of an attribute selector,
648    /// giving its attribute namespace, or None for a prefix declared only
649    /// for elements. Anything else is left for `attr` to read or refuse.
650    fn declared_attr_prefix(&mut self) -> Option<Option<AttrNs>> {
651        let start = self.pos;
652        self.skip_space();
653        if self.starts_name()
654            && let Ok(name) = self.ident()
655            && self.peek() == Some('|')
656            && self.peek_at(1) != Some('=')
657        {
658            let attr = self.opts.attr_namespaces.iter().find(|(p, _)| *p == name);
659            if let Some(&(_, ns)) = attr {
660                self.pos += 1;
661                return Some(Some(ns));
662            }
663            if self.opts.namespaces.iter().any(|(p, _)| *p == name) {
664                self.pos += 1;
665                return Some(None);
666            }
667        }
668        self.pos = start;
669        None
670    }
671
672    fn attr(&mut self) -> Result<AttrSelector, SelectorError> {
673        self.skip_space();
674        let mut any_ns = false;
675        if self.peek() == Some('*') && self.peek_at(1) == Some('|') {
676            self.pos += 2;
677            any_ns = true;
678        } else if self.peek() == Some('|') {
679            self.pos += 1;
680        }
681        let name = self.ident()?;
682        if self.peek() == Some('|') && self.peek_at(1) != Some('=') {
683            return error(format!("namespace prefix {name:?} isn't declared"));
684        }
685        self.skip_space();
686        // The end of the input closes every open block, as CSS reads it, so
687        // `[class` and `[class="x"` are whole.
688        let op = match self.peek() {
689            Some(']') | None => {
690                self.eat(']');
691                return Ok(AttrSelector {
692                    lower: name.to_ascii_lowercase(),
693                    exact: name,
694                    any_ns,
695                    in_ns: None,
696                    op: AttrOp::Exists,
697                    value: String::new(),
698                    case: Case::Default,
699                });
700            }
701            Some('=') => {
702                self.pos += 1;
703                AttrOp::Equals
704            }
705            Some(c @ ('~' | '|' | '^' | '$' | '*')) if self.peek_at(1) == Some('=') => {
706                self.pos += 2;
707                match c {
708                    '~' => AttrOp::Includes,
709                    '|' => AttrOp::DashMatch,
710                    '^' => AttrOp::Prefix,
711                    '$' => AttrOp::Suffix,
712                    _ => AttrOp::Substring,
713                }
714            }
715            _ => return error("a bad attribute selector"),
716        };
717        self.skip_space();
718        let value = match self.peek() {
719            Some(q @ ('"' | '\'')) => {
720                self.pos += 1;
721                self.string(q)?
722            }
723            _ => self.ident()?,
724        };
725        self.skip_space();
726        let mut case = Case::Default;
727        if let Some(c) = self.peek()
728            && c.is_ascii_alphabetic()
729        {
730            let flag = self.ident()?;
731            case = match flag.to_ascii_lowercase().as_str() {
732                "i" => Case::Insensitive,
733                "s" => Case::Sensitive,
734                _ => return error(format!("unknown attribute flag {flag:?}")),
735            };
736            self.skip_space();
737        }
738        if !self.eat(']') && !self.at_end() {
739            return error("an attribute selector without its ]");
740        }
741        Ok(AttrSelector {
742            lower: name.to_ascii_lowercase(),
743            exact: name,
744            any_ns,
745            in_ns: None,
746            op,
747            value,
748            case,
749        })
750    }
751
752    /// A pseudo-element, after its `::`: the ones CSS defines, with
753    /// `::part()`, `::slotted()` and `::highlight()` taking their argument.
754    /// Anything else, `::text` included, is an error. `::slotted()` gives
755    /// its argument; nothing but another pseudo-element may follow it.
756    fn pseudo_element(&mut self) -> Result<Option<Compound>, SelectorError> {
757        let name = self.ident()?.to_ascii_lowercase();
758        if self.eat('(') {
759            self.skip_space();
760            match name.as_str() {
761                "part" => {
762                    self.ident()?;
763                    while self.skip_space() && self.starts_name() {
764                        self.ident()?;
765                    }
766                }
767                "slotted" => {
768                    // Its compound can't hold a pseudo-element either.
769                    let compound = self.compound_argument()?;
770                    self.skip_space();
771                    if !self.eat(')') && !self.at_end() {
772                        return error("::slotted() without its )");
773                    }
774                    return Ok(Some(compound));
775                }
776                "highlight" => {
777                    self.ident()?;
778                }
779                _ => return error(format!("::{name}() isn't a pseudo-element")),
780            }
781            self.skip_space();
782            if !self.eat(')') && !self.at_end() {
783                return error(format!("::{name}() without its )"));
784            }
785            return Ok(None);
786        }
787        match name.as_str() {
788            "before"
789            | "after"
790            | "marker"
791            | "placeholder"
792            | "selection"
793            | "first-line"
794            | "first-letter"
795            | "backdrop"
796            | "file-selector-button"
797            | "cue"
798            | "spelling-error"
799            | "grammar-error"
800            | "target-text"
801            | "details-content"
802            | "checkmark"
803            | "picker-icon"
804            | "scroll-marker"
805            | "scroll-marker-group"
806            | "scroll-button"
807            | "column"
808            | "view-transition" => Ok(None),
809            _ => error(format!("::{name} isn't a pseudo-element")),
810        }
811    }
812
813    fn pseudo(&mut self) -> Result<Pseudo, SelectorError> {
814        let name = self.ident()?.to_ascii_lowercase();
815        if self.eat('(') {
816            let p = self.pseudo_function(&name)?;
817            self.skip_space();
818            if !self.eat(')') && !self.at_end() {
819                return error(format!(":{name}() without its )"));
820            }
821            return Ok(p);
822        }
823        Ok(match name.as_str() {
824            "first-child" => nth(0, 1, false, false),
825            "last-child" => nth(0, 1, true, false),
826            "only-child" => Pseudo::Only { of_type: false },
827            "first-of-type" => nth(0, 1, false, true),
828            "last-of-type" => nth(0, 1, true, true),
829            "only-of-type" => Pseudo::Only { of_type: true },
830            "empty" => Pseudo::Empty,
831            "heading" => Pseudo::Heading(Vec::new()),
832            "root" => Pseudo::Root,
833            "scope" => Pseudo::Scope,
834            "link" | "any-link" => Pseudo::AnyLink,
835            "checked" => Pseudo::Checked,
836            "disabled" => Pseudo::Disabled,
837            "enabled" => Pseudo::Enabled,
838            "required" => Pseudo::Required,
839            "optional" => Pseudo::Optional,
840            "read-write" => Pseudo::ReadWrite,
841            "read-only" => Pseudo::ReadOnly,
842            "placeholder-shown" => Pseudo::PlaceholderShown,
843            "blank" => Pseudo::Blank,
844            "defined" => Pseudo::Defined,
845            "target" => Pseudo::Target,
846            "target-within" => Pseudo::TargetWithin,
847            "local-link" => Pseudo::LocalLink,
848            "default" => Pseudo::Default,
849            "indeterminate" => Pseudo::Indeterminate,
850            "in-range" => Pseudo::InRange,
851            "out-of-range" => Pseudo::OutOfRange,
852            "valid" => Pseudo::Valid,
853            "invalid" => Pseudo::Invalid,
854            "hover" | "active" | "focus" | "focus-visible" | "focus-within" | "visited"
855            | "user-invalid" | "user-valid" => Pseudo::Never,
856            // CSS 2's pseudo-elements, still allowed with one colon.
857            "before" | "after" | "first-line" | "first-letter" => Pseudo::Element,
858            "host" => Pseudo::Host(None),
859            _ => return error(format!(":{name} isn't supported")),
860        })
861    }
862
863    fn pseudo_function(&mut self, name: &str) -> Result<Pseudo, SelectorError> {
864        if self.depth >= MAX_DEPTH {
865            return error(format!("selectors nest more than {MAX_DEPTH} deep"));
866        }
867        self.depth += 1;
868        let result = self.pseudo_function_body(name);
869        self.depth -= 1;
870        result
871    }
872
873    fn pseudo_function_body(&mut self, name: &str) -> Result<Pseudo, SelectorError> {
874        Ok(match name {
875            "not" => Pseudo::Not(self.selector_list(false)?),
876            "host" => Pseudo::Host(Some(Box::new(self.compound_argument()?))),
877            "host-context" => Pseudo::HostContext(Box::new(self.compound_argument()?)),
878            "is" | "matches" => Pseudo::Is(self.selector_list(true)?),
879            "where" => Pseudo::Where(self.selector_list(true)?),
880            "has" => {
881                if self.in_has {
882                    return error(":has() can't go inside :has()");
883                }
884                self.in_has = true;
885                let list = self.has_list();
886                self.in_has = false;
887                Pseudo::Has(list?)
888            }
889            "nth-child" | "nth-last-child" | "nth-of-type" | "nth-last-of-type" => {
890                let of_type = name.ends_with("of-type");
891                let last = name.starts_with("nth-last");
892                let close = self.close_paren();
893                let arg = &self.s[self.pos..close];
894                let (anb, rest) = match split_of(arg) {
895                    Some((anb, rest)) if !of_type => (anb, Some(rest)),
896                    Some(_) => return error("`of` only goes in :nth-child and :nth-last-child"),
897                    None => (arg, None),
898                };
899                let (a, b) = an_plus_b(anb)?;
900                let of = rest
901                    .map(|rest| SelectorList::parse_at(rest, self.depth, self.in_has, self.opts))
902                    .transpose()?;
903                self.pos = close;
904                Pseudo::Nth {
905                    a,
906                    b,
907                    last,
908                    of_type,
909                    of,
910                }
911            }
912            "nth-col" | "nth-last-col" => {
913                let close = self.close_paren();
914                let (a, b) = an_plus_b(&self.s[self.pos..close])?;
915                self.pos = close;
916                Pseudo::NthCol {
917                    a,
918                    b,
919                    last: name == "nth-last-col",
920                }
921            }
922            "lang" => {
923                let mut ranges = Vec::new();
924                loop {
925                    self.skip_space();
926                    // A wildcard such as *-CH can't be a name, so it's quoted.
927                    let range = match self.peek() {
928                        Some(q @ ('"' | '\'')) => {
929                            self.pos += 1;
930                            self.string(q)?
931                        }
932                        _ => self.ident()?,
933                    };
934                    ranges.push(range.to_ascii_lowercase());
935                    self.skip_space();
936                    if !self.eat(',') {
937                        break;
938                    }
939                }
940                Pseudo::Lang(ranges)
941            }
942            // Selectors 5's draft: a list of integers, not An+B.
943            "heading" => {
944                let mut levels = Vec::new();
945                loop {
946                    self.skip_space();
947                    let start = self.pos;
948                    if matches!(self.peek(), Some('+' | '-')) {
949                        self.pos += 1;
950                    }
951                    while self.peek().is_some_and(|c| c.is_ascii_digit()) {
952                        self.pos += 1;
953                    }
954                    let whole = !self.peek().is_some_and(|c| is_name(c) || c == '.');
955                    match self.s[start..self.pos].parse() {
956                        Ok(level) if whole => levels.push(level),
957                        _ => return error(":heading() takes integers, like :heading(1, 3)"),
958                    }
959                    self.skip_space();
960                    if !self.eat(',') {
961                        break;
962                    }
963                }
964                Pseudo::Heading(levels)
965            }
966            "dir" => {
967                self.skip_space();
968                let dir = self.ident()?.to_ascii_lowercase();
969                self.skip_space();
970                // Any identifier is allowed; only ltr and rtl ever match.
971                match dir.as_str() {
972                    "ltr" => Pseudo::Dir(false),
973                    "rtl" => Pseudo::Dir(true),
974                    _ => Pseudo::Never,
975                }
976            }
977            _ => return error(format!(":{name}() isn't supported")),
978        })
979    }
980
981    /// The compound in `:host()`, `:host-context()` or `::slotted()`,
982    /// with no combinator inside it at any depth.
983    fn compound_argument(&mut self) -> Result<Compound, SelectorError> {
984        if self.depth >= MAX_DEPTH {
985            return error(format!("selectors nest more than {MAX_DEPTH} deep"));
986        }
987        self.skip_space();
988        let outer = std::mem::replace(&mut self.compound_only, true);
989        self.depth += 1;
990        let compound = self.compound();
991        self.depth -= 1;
992        self.compound_only = outer;
993        compound
994    }
995
996    fn has_list(&mut self) -> Result<SelectorList, SelectorError> {
997        let mut out = Vec::new();
998        loop {
999            out.push(self.complex(true)?);
1000            self.skip_space();
1001            if !self.eat(',') {
1002                return Ok(SelectorList(out));
1003            }
1004        }
1005    }
1006
1007    /// Where the `)` closing the current parenthesis is, past nested
1008    /// ones and strings.
1009    fn close_paren(&self) -> usize {
1010        let b = self.s.as_bytes();
1011        let mut depth = 0;
1012        let mut i = self.pos;
1013        while i < b.len() {
1014            match b[i] {
1015                b'\\' => i += 1,
1016                q @ (b'"' | b'\'') => {
1017                    i += 1;
1018                    while i < b.len() && b[i] != q {
1019                        if b[i] == b'\\' {
1020                            i += 1;
1021                        }
1022                        i += 1;
1023                    }
1024                }
1025                b'(' => depth += 1,
1026                b')' if depth == 0 => return i,
1027                b')' => depth -= 1,
1028                _ => {}
1029            }
1030            i += 1;
1031        }
1032        b.len()
1033    }
1034}
1035
1036/// Whether the first strong character of `text` is right to left (Some(true))
1037/// or left to right (Some(false)); None when it has none.
1038// shortcut: letters in the right-to-left scripts' blocks count as strong
1039// right to left and any other letter as strong left to right, rather than
1040// reading Unicode's Bidi_Class; use the real table if a script needs it.
1041fn first_strong_rtl(text: &str) -> Option<bool> {
1042    text.chars()
1043        .filter(|c| c.is_alphabetic())
1044        .map(|c| {
1045            matches!(c as u32,
1046            0x0590..=0x08FF | 0xFB1D..=0xFDFF | 0xFE70..=0xFEFF
1047            | 0x10800..=0x10FFF | 0x1E800..=0x1EFFF)
1048        })
1049        .next()
1050}
1051
1052/// Whether a language `tag` matches a `range`, both lowercase, by RFC 4647's
1053/// extended filtering as Selectors 4 uses it: `de` matches `de-CH`, `de-CH`
1054/// matches `de-Latn-CH`, and `*` stands for any subtag. Subtags the range
1055/// leaves out match anything, but never past a one-letter one such as `x`.
1056fn lang_matches(range: &str, tag: &str) -> bool {
1057    if range.is_empty() || tag.is_empty() {
1058        return range == tag;
1059    }
1060    let r: Vec<&str> = range.split('-').collect();
1061    let t: Vec<&str> = tag.split('-').collect();
1062    // A tag that isn't well-formed (BCP 47: subtags of 1 to 8 letters or
1063    // digits) is no language, so it matches no range.
1064    if t.iter()
1065        .any(|s| s.is_empty() || s.len() > 8 || !s.bytes().all(|b| b.is_ascii_alphanumeric()))
1066    {
1067        return false;
1068    }
1069    if r[0] != "*" && r[0] != t[0] {
1070        return false;
1071    }
1072    let (mut i, mut j) = (1, 1);
1073    while i < r.len() {
1074        if r[i] == "*" {
1075            i += 1;
1076        } else if j >= t.len() {
1077            return false;
1078        } else if r[i] == t[j] {
1079            i += 1;
1080            j += 1;
1081        } else if t[j].len() == 1 {
1082            return false;
1083        } else {
1084            j += 1;
1085        }
1086    }
1087    true
1088}
1089
1090/// An `<input>`'s type as the HTML Standard reads it: a known type in any
1091/// case, anything else (or none) text.
1092fn input_type_state(typ: Option<&str>) -> &'static str {
1093    const TYPES: [&str; 22] = [
1094        "hidden",
1095        "text",
1096        "search",
1097        "tel",
1098        "url",
1099        "email",
1100        "password",
1101        "date",
1102        "month",
1103        "week",
1104        "time",
1105        "datetime-local",
1106        "number",
1107        "range",
1108        "color",
1109        "checkbox",
1110        "radio",
1111        "file",
1112        "submit",
1113        "image",
1114        "reset",
1115        "button",
1116    ];
1117    typ.and_then(|t| TYPES.iter().find(|k| k.eq_ignore_ascii_case(t)))
1118        .copied()
1119        .unwrap_or("text")
1120}
1121
1122/// The `<input>` types a user types text into: the ones `placeholder`
1123/// applies to.
1124fn text_entry(typ: &str) -> bool {
1125    matches!(
1126        typ,
1127        "text" | "search" | "url" | "tel" | "email" | "password" | "number"
1128    )
1129}
1130
1131/// HTML's valid custom element name: a lowercase ASCII letter, then
1132/// PCENChars including a hyphen, and not one of the hyphenated names SVG
1133/// and MathML already use.
1134pub(crate) fn custom_element_name(name: &str) -> bool {
1135    const RESERVED: [&str; 8] = [
1136        "annotation-xml",
1137        "color-profile",
1138        "font-face",
1139        "font-face-src",
1140        "font-face-uri",
1141        "font-face-format",
1142        "font-face-name",
1143        "missing-glyph",
1144    ];
1145    let pcen = |c: char| {
1146        matches!(c,
1147            '-' | '.' | '0'..='9' | '_' | 'a'..='z' | '\u{B7}'
1148            | '\u{C0}'..='\u{D6}' | '\u{D8}'..='\u{F6}' | '\u{F8}'..='\u{37D}'
1149            | '\u{37F}'..='\u{1FFF}' | '\u{200C}'..='\u{200D}' | '\u{203F}'..='\u{2040}'
1150            | '\u{2070}'..='\u{218F}' | '\u{2C00}'..='\u{2FEF}' | '\u{3001}'..='\u{D7FF}'
1151            | '\u{F900}'..='\u{FDCF}' | '\u{FDF0}'..='\u{FFFD}' | '\u{10000}'..='\u{EFFFF}')
1152    };
1153    name.starts_with(|c: char| c.is_ascii_lowercase())
1154        && name.contains('-')
1155        && name.chars().all(pcen)
1156        && !RESERVED.contains(&name)
1157}
1158
1159fn readonly_applies(typ: &str) -> bool {
1160    matches!(
1161        typ,
1162        "text"
1163            | "search"
1164            | "url"
1165            | "tel"
1166            | "email"
1167            | "password"
1168            | "date"
1169            | "month"
1170            | "week"
1171            | "time"
1172            | "datetime-local"
1173            | "number"
1174    )
1175}
1176
1177/// The value sanitization algorithm for the types validation reads: line
1178/// breaks out, url and email trimmed, an email list trimmed item by item, and
1179/// a date, time or number that isn't valid gone.
1180fn sanitized(typ: &str, value: &str, multiple: bool) -> String {
1181    let no_breaks: String = value.chars().filter(|&c| c != '\n' && c != '\r').collect();
1182    let trim = |s: &str| {
1183        s.trim_matches(|c: char| c.is_ascii_whitespace())
1184            .to_string()
1185    };
1186    match typ {
1187        "url" => trim(&no_breaks),
1188        "email" if multiple => value.split(',').map(trim).collect::<Vec<_>>().join(","),
1189        "email" => trim(&no_breaks),
1190        "number" | "date" | "month" | "week" | "time" | "datetime-local" => {
1191            if input_number(typ, value).is_some() {
1192                value.to_string()
1193            } else {
1194                String::new()
1195            }
1196        }
1197        _ => no_breaks,
1198    }
1199}
1200
1201/// The rules for parsing floating-point number values: leading whitespace
1202/// skipped, an optional sign, then as much of a number as there is.
1203fn parse_float_value(s: &str) -> Option<f64> {
1204    let s = s.trim_start_matches(|c: char| c.is_ascii_whitespace());
1205    let b = s.as_bytes();
1206    let mut i = usize::from(matches!(b.first(), Some(b'-' | b'+')));
1207    let digits = |i: &mut usize| {
1208        let at = *i;
1209        while b.get(*i).is_some_and(u8::is_ascii_digit) {
1210            *i += 1;
1211        }
1212        *i > at
1213    };
1214    let mut end;
1215    let whole = digits(&mut i);
1216    end = i;
1217    if b.get(i) == Some(&b'.') {
1218        let mut j = i + 1;
1219        if digits(&mut j) {
1220            i = j;
1221            end = i;
1222        } else if !whole {
1223            return None;
1224        }
1225    }
1226    if !whole && end == usize::from(matches!(b.first(), Some(b'-' | b'+'))) {
1227        return None;
1228    }
1229    if matches!(b.get(end), Some(b'e' | b'E')) {
1230        let mut j = end + 1;
1231        if matches!(b.get(j), Some(b'+' | b'-')) {
1232            j += 1;
1233        }
1234        if digits(&mut j) {
1235            end = j;
1236        }
1237    }
1238    s[..end]
1239        .trim_start_matches('+')
1240        .parse::<f64>()
1241        .ok()
1242        .filter(|n| n.is_finite())
1243}
1244
1245/// The rules for parsing non-negative integers: leading whitespace and a
1246/// `+` skipped, then the digits up to the first that isn't one.
1247fn parse_non_negative(s: &str) -> Option<u32> {
1248    let s = s.trim_start_matches(|c: char| c.is_ascii_whitespace());
1249    let s = s.strip_prefix('+').unwrap_or(s);
1250    let end = s.find(|c: char| !c.is_ascii_digit()).unwrap_or(s.len());
1251    s[..end].parse().ok()
1252}
1253
1254/// The HTML Standard's valid email address: a local part of letters,
1255/// digits and ``.!#$%&'*+/=?^_`{|}~-``, then `@` and dot-separated labels
1256/// of up to 63 letters, digits and hyphens that don't start or end with one.
1257fn valid_email(address: &str) -> bool {
1258    let Some((local, domain)) = address.split_once('@') else {
1259        return false;
1260    };
1261    let local_ok = !local.is_empty()
1262        && local
1263            .chars()
1264            .all(|c| c.is_ascii_alphanumeric() || ".!#$%&'*+/=?^_`{|}~-".contains(c));
1265    let label_ok = |l: &str| {
1266        !l.is_empty()
1267            && l.len() <= 63
1268            && l.chars().all(|c| c.is_ascii_alphanumeric() || c == '-')
1269            && !l.starts_with('-')
1270            && !l.ends_with('-')
1271    };
1272    local_ok && domain.split('.').all(label_ok)
1273}
1274
1275/// The day the Monday of the year's first ISO week falls on.
1276fn monday_of_week_1(y: i64) -> i64 {
1277    let jan4 = days(y, 1, 4);
1278    let weekday = (jan4 - 1) % 7; // 1 January of year 1 was a Monday: 0
1279    jan4 - weekday
1280}
1281
1282/// An `<input>` value of `typ` as a number that orders as the values do:
1283/// the number, or for dates and times a count of days, months, weeks or
1284/// milliseconds. None when it isn't a valid value of that type.
1285fn input_number(typ: &str, v: &str) -> Option<f64> {
1286    match typ {
1287        "number" | "range" => float_number(v),
1288        "date" => date(v).map(|(y, m, d)| days(y, m, d) as f64),
1289        "month" => {
1290            let (y, m) = v.split_once('-')?;
1291            let (y, m) = (year(y)?, two_digits(m)?);
1292            (1..=12).contains(&m).then(|| (y * 12 + m - 1) as f64)
1293        }
1294        "week" => {
1295            let (y, w) = v.split_once("-W")?;
1296            let (y, w) = (year(y)?, two_digits(w)?);
1297            (1..=weeks_in(y))
1298                .contains(&w)
1299                .then(|| (monday_of_week_1(y) + (w - 1) * 7) as f64)
1300        }
1301        "time" => time_ms(v),
1302        "datetime-local" => {
1303            let at = v.find(['T', ' '])?;
1304            let (y, m, d) = date(&v[..at])?;
1305            Some(days(y, m, d) as f64 * 86_400_000.0 + time_ms(&v[at + 1..])?)
1306        }
1307        _ => None,
1308    }
1309}
1310
1311/// HTML's valid floating-point number: -?digits(.digits)?(e[+-]?digits)?,
1312/// or with no digits before a point.
1313fn float_number(v: &str) -> Option<f64> {
1314    let b = v.as_bytes();
1315    let mut i = usize::from(b.first() == Some(&b'-'));
1316    let digits = |i: &mut usize| {
1317        let at = *i;
1318        while b.get(*i).is_some_and(u8::is_ascii_digit) {
1319            *i += 1;
1320        }
1321        *i > at
1322    };
1323    let whole = digits(&mut i);
1324    // A point needs digits after it: 1. isn't a number.
1325    let point = b.get(i) == Some(&b'.');
1326    if point {
1327        i += 1;
1328    }
1329    let fraction = point && digits(&mut i);
1330    if point && !fraction {
1331        return None;
1332    }
1333    if !whole && !fraction {
1334        return None;
1335    }
1336    if matches!(b.get(i), Some(b'e' | b'E')) {
1337        i += 1;
1338        if matches!(b.get(i), Some(b'+' | b'-')) {
1339            i += 1;
1340        }
1341        if !digits(&mut i) {
1342            return None;
1343        }
1344    }
1345    if i != b.len() {
1346        return None;
1347    }
1348    v.parse().ok().filter(|n: &f64| n.is_finite())
1349}
1350
1351/// Four or more ASCII digits, above zero.
1352fn year(s: &str) -> Option<i64> {
1353    (s.len() >= 4 && s.bytes().all(|c| c.is_ascii_digit()))
1354        .then(|| s.parse().ok())
1355        .flatten()
1356        .filter(|&y| y > 0)
1357}
1358
1359fn two_digits(s: &str) -> Option<i64> {
1360    (s.len() == 2 && s.bytes().all(|c| c.is_ascii_digit())).then(|| s.parse().ok())?
1361}
1362
1363fn leap(y: i64) -> bool {
1364    (y % 4 == 0 && y % 100 != 0) || y % 400 == 0
1365}
1366
1367/// YYYY-MM-DD, a real day.
1368fn date(v: &str) -> Option<(i64, i64, i64)> {
1369    let mut parts = v.splitn(3, '-');
1370    let (y, m, d) = (
1371        year(parts.next()?)?,
1372        two_digits(parts.next()?)?,
1373        two_digits(parts.next()?)?,
1374    );
1375    let last = match m {
1376        1 | 3 | 5 | 7 | 8 | 10 | 12 => 31,
1377        4 | 6 | 9 | 11 => 30,
1378        2 if leap(y) => 29,
1379        2 => 28,
1380        _ => return None,
1381    };
1382    (1..=last).contains(&d).then_some((y, m, d))
1383}
1384
1385/// Days from 1 January of year 1 to the date, for comparing.
1386fn days(y: i64, m: i64, d: i64) -> i64 {
1387    let before = y - 1;
1388    let mut n = before * 365 + before / 4 - before / 100 + before / 400;
1389    for month in 1..m {
1390        n += match month {
1391            1 | 3 | 5 | 7 | 8 | 10 | 12 => 31,
1392            4 | 6 | 9 | 11 => 30,
1393            _ if leap(y) => 29,
1394            _ => 28,
1395        };
1396    }
1397    n + d
1398}
1399
1400/// 53 for a year whose 1 January is a Thursday, or a Wednesday in a leap
1401/// year; 52 for the rest.
1402fn weeks_in(y: i64) -> i64 {
1403    let weekday = days(y, 1, 1) % 7; // 1 January of year 1 was a Monday: 1
1404    if weekday == 4 || (weekday == 3 && leap(y)) {
1405        53
1406    } else {
1407        52
1408    }
1409}
1410
1411/// HH:MM, HH:MM:SS or HH:MM:SS.fff in milliseconds.
1412fn time_ms(v: &str) -> Option<f64> {
1413    let mut parts = v.splitn(3, ':');
1414    let (h, m) = (two_digits(parts.next()?)?, two_digits(parts.next()?)?);
1415    if h > 23 || m > 59 {
1416        return None;
1417    }
1418    let seconds = match parts.next() {
1419        None => 0.0,
1420        Some(s) => {
1421            let (whole, frac) = s.split_once('.').unwrap_or((s, ""));
1422            let sec = two_digits(whole)?;
1423            let frac_ok = frac.len() <= 3
1424                && frac.bytes().all(|c| c.is_ascii_digit())
1425                && (!s.contains('.') || !frac.is_empty());
1426            if sec > 59 || !frac_ok {
1427                return None;
1428            }
1429            s.parse::<f64>().ok()?
1430        }
1431    };
1432    Some(((h * 60 + m) as f64 * 60.0 + seconds) * 1000.0)
1433}
1434
1435/// `2n+1 of .x` into `2n+1` and `.x`.
1436fn split_of(arg: &str) -> Option<(&str, &str)> {
1437    let lower = arg.to_ascii_lowercase();
1438    let mut from = 0;
1439    while let Some(i) = lower[from..].find("of") {
1440        let at = from + i;
1441        let before = lower[..at].chars().next_back();
1442        let after = lower[at + 2..].chars().next();
1443        if before.is_some_and(is_space_char) && after.is_some_and(is_space_char) {
1444            return Some((&arg[..at], &arg[at + 2..]));
1445        }
1446        from = at + 2;
1447    }
1448    None
1449}
1450
1451/// The `An+B` microsyntax: `odd`, `even`, `3`, `-n+2`, `2n + 1`...
1452fn an_plus_b(text: &str) -> Result<(i32, i32), SelectorError> {
1453    let text = text.trim().to_ascii_lowercase();
1454    let bad = || SelectorError {
1455        reason: format!("{text:?} isn't An+B"),
1456    };
1457    match text.as_str() {
1458        "odd" => return Ok((2, 1)),
1459        "even" => return Ok((2, 0)),
1460        "" => return Err(bad()),
1461        _ => {}
1462    }
1463    // Whitespace can only go around the sign before B, as in `2n + 1`:
1464    // `2 n` and `+ 5` are two tokens where An+B wants one.
1465    let Some(i) = text.find('n') else {
1466        return text.parse::<i32>().map(|b| (0, b)).map_err(|_| bad());
1467    };
1468    let compact: String = text[i + 1..].split_whitespace().collect();
1469    let a = match &text[..i] {
1470        "" | "+" => 1,
1471        "-" => -1,
1472        s => s.parse::<i32>().map_err(|_| bad())?,
1473    };
1474    let rest = compact.as_str();
1475    let b = if rest.is_empty() {
1476        0
1477    } else if rest.len() > 1
1478        && rest.starts_with(['+', '-'])
1479        && rest[1..].bytes().all(|c| c.is_ascii_digit())
1480    {
1481        rest.parse::<i32>().map_err(|_| bad())?
1482    } else {
1483        return Err(bad());
1484    };
1485    Ok((a, b))
1486}
1487
1488fn type_selector(name: String) -> Simple {
1489    let lower = name.to_ascii_lowercase();
1490    Simple::Type {
1491        tag: Tag::from_name(&lower),
1492        lower,
1493        exact: name,
1494    }
1495}
1496
1497fn nth(a: i32, b: i32, last: bool, of_type: bool) -> Pseudo {
1498    Pseudo::Nth {
1499        a,
1500        b,
1501        last,
1502        of_type,
1503        of: None,
1504    }
1505}
1506
1507/// What a stylesheet's `@namespace` rules would declare, for
1508/// [`SelectorList::parse_with`]. The default declares nothing, as
1509/// [`SelectorList::parse`] does.
1510///
1511/// Namespaces are named by [`Ns`] for elements and [`AttrNs`] for
1512/// attributes, so only the ones the parser puts nodes in can be declared:
1513/// HTML, SVG and MathML, and XLink, XML and XMLNS. A custom namespace URI
1514/// has nothing to name it. Neither do [`Ns::Xml`] and [`AttrNs::Host`],
1515/// which stand for whatever namespace the host keeps for an XML node, so
1516/// declaring either is an error.
1517#[derive(Debug, Clone, Copy, Default)]
1518pub struct ParseOptions<'a> {
1519    /// Prefixes and their namespaces: `("svg", Ns::Svg)` makes `svg|rect`
1520    /// a `rect` in the SVG namespace. Prefixes compare exactly.
1521    pub namespaces: &'a [(&'a str, Ns)],
1522    /// Prefixes for attribute selectors: `("xlink", AttrNs::XLink)` makes
1523    /// `[xlink|href]` SVG's `xlink:href`. A prefix only in `namespaces`
1524    /// names an element namespace, which no attribute is in, so it matches
1525    /// nothing in an attribute selector.
1526    pub attr_namespaces: &'a [(&'a str, AttrNs)],
1527    /// The `@namespace` without a prefix: type selectors and `*` without
1528    /// a prefix match only elements in it, and so does a compound with
1529    /// neither. Attribute selectors aren't affected.
1530    pub default: Option<Ns>,
1531}
1532
1533impl SelectorList {
1534    pub fn parse(selector: &str) -> Result<SelectorList, SelectorError> {
1535        SelectorList::parse_with(selector, &ParseOptions::default())
1536    }
1537
1538    /// [`SelectorList::parse`] with namespace prefixes declared, as
1539    /// `@namespace` rules would.
1540    pub fn parse_with(selector: &str, opts: &ParseOptions) -> Result<SelectorList, SelectorError> {
1541        let declared = opts
1542            .namespaces
1543            .iter()
1544            .map(|&(_, ns)| ns)
1545            .chain(opts.default);
1546        if declared.into_iter().any(|ns| ns == Ns::Xml) {
1547            return error("Ns::Xml isn't a namespace a selector can declare");
1548        }
1549        if opts
1550            .attr_namespaces
1551            .iter()
1552            .any(|(_, ns)| matches!(ns, AttrNs::Host(_)))
1553        {
1554            return error("AttrNs::Host isn't a namespace a selector can declare");
1555        }
1556        SelectorList::parse_at(selector, 0, false, opts)
1557    }
1558
1559    fn parse_at(
1560        selector: &str,
1561        depth: u32,
1562        in_has: bool,
1563        opts: &ParseOptions,
1564    ) -> Result<SelectorList, SelectorError> {
1565        let mut p = Parser {
1566            s: selector,
1567            pos: 0,
1568            depth,
1569            in_has,
1570            compound_only: false,
1571            opts,
1572        };
1573        let list = p.selector_list(false)?;
1574        p.skip_space();
1575        if !p.at_end() {
1576            return error(format!("unexpected {:?}", &selector[p.pos..]));
1577        }
1578        Ok(list)
1579    }
1580
1581    /// Whether `el` matches, with `scope` as `:scope` (the root element
1582    /// when `None`).
1583    pub fn matches(&self, doc: &Document, el: NodeId, scope: Option<NodeId>) -> bool {
1584        self.matches_with(doc, el, scope, &MatchOptions::default())
1585    }
1586
1587    /// [`SelectorList::matches`] with what the document alone can't say,
1588    /// such as its URL.
1589    pub fn matches_with(
1590        &self,
1591        doc: &Document,
1592        el: NodeId,
1593        scope: Option<NodeId>,
1594        options: &MatchOptions<'_>,
1595    ) -> bool {
1596        if doc.is_removed(el) {
1597            return false;
1598        }
1599        let cx = Cx::new(doc, scope, scope.unwrap_or(el), Page::new(doc, options.url));
1600        self.0.iter().any(|c| cx.complex(c, el, el))
1601    }
1602
1603    /// [`SelectorList::select`] with what the document alone can't say,
1604    /// such as its URL.
1605    pub fn select_with(
1606        &self,
1607        doc: &Document,
1608        scope: NodeId,
1609        options: &MatchOptions<'_>,
1610    ) -> Vec<NodeId> {
1611        self.iter_with(doc, scope, options).collect()
1612    }
1613
1614    /// [`SelectorList::select_with`] within [`MatchOptions::budget`]: an
1615    /// error once it has run out, rather than the matches found so far.
1616    pub fn try_select_with(
1617        &self,
1618        doc: &Document,
1619        scope: NodeId,
1620        options: &MatchOptions<'_>,
1621    ) -> Result<Vec<NodeId>, MatchTimeout> {
1622        let mut select = self.iter_with(doc, scope, options);
1623        select.cx.limit(options);
1624        let found = select.by_ref().collect();
1625        timeout(&select.cx, options)?;
1626        Ok(found)
1627    }
1628
1629    /// [`SelectorList::matches_with`] within [`MatchOptions::budget`].
1630    pub fn try_matches_with(
1631        &self,
1632        doc: &Document,
1633        el: NodeId,
1634        scope: Option<NodeId>,
1635        options: &MatchOptions<'_>,
1636    ) -> Result<bool, MatchTimeout> {
1637        if doc.is_removed(el) {
1638            return Ok(false);
1639        }
1640        let mut cx = Cx::new(doc, scope, scope.unwrap_or(el), Page::new(doc, options.url));
1641        cx.limit(options);
1642        let found = self.0.iter().any(|c| cx.complex(c, el, el));
1643        timeout(&cx, options)?;
1644        Ok(found)
1645    }
1646
1647    fn iter_with<'a>(
1648        &'a self,
1649        doc: &'a Document,
1650        scope: NodeId,
1651        options: &MatchOptions<'_>,
1652    ) -> Select<'a> {
1653        Select {
1654            list: self,
1655            // One Cx for the whole walk, so its pattern matches share one budget.
1656            cx: Cx::new(doc, Some(scope), scope, Page::new(doc, options.url)),
1657            scope,
1658            at: doc.first_child(scope),
1659        }
1660    }
1661
1662    /// The elements under `scope` that match, in document order. As in a
1663    /// browser, combinators look past `scope`: `article .price` run on an
1664    /// article matches the prices inside it.
1665    pub fn select(&self, doc: &Document, scope: NodeId) -> Vec<NodeId> {
1666        self.select_iter(doc, scope).collect()
1667    }
1668
1669    /// The matches [`SelectorList::select`] gives, found one at a time as
1670    /// the iterator is read, so stopping early walks only that far.
1671    pub fn select_iter<'a>(&'a self, doc: &'a Document, scope: NodeId) -> Select<'a> {
1672        self.iter_with(doc, scope, &MatchOptions::default())
1673    }
1674
1675    /// The first match in document order, without looking further.
1676    pub fn select_first(&self, doc: &Document, scope: NodeId) -> Option<NodeId> {
1677        self.select_iter(doc, scope).next()
1678    }
1679
1680    /// Selectors 4's specificity, (IDs, classes, types), of the most
1681    /// specific selector in the list, which is how `:is()` counts one.
1682    /// `:is()`, `:not()` and `:has()` count as their most specific
1683    /// argument, `:nth-child(An+B of S)` as a class plus S, and `:where()`
1684    /// as nothing. (`|x`, which matches nothing, counts a class too much.)
1685    pub fn specificity(&self) -> (u32, u32, u32) {
1686        self.0
1687            .iter()
1688            .map(Complex::specificity)
1689            .max()
1690            .unwrap_or((0, 0, 0))
1691    }
1692}
1693
1694impl Complex {
1695    fn specificity(&self) -> (u32, u32, u32) {
1696        self.parts.iter().fold((0, 0, 0), |sum, (compound, _)| {
1697            compound.0.iter().fold(sum, |(a, b, c), simple| {
1698                let (x, y, z) = simple.specificity();
1699                (a + x, b + y, c + z)
1700            })
1701        })
1702    }
1703}
1704
1705impl Compound {
1706    fn specificity(&self) -> (u32, u32, u32) {
1707        self.0.iter().fold((0, 0, 0), |(a, b, c), simple| {
1708            let (x, y, z) = simple.specificity();
1709            (a + x, b + y, c + z)
1710        })
1711    }
1712}
1713
1714impl Pseudo {
1715    /// Whether matching reads the tree around the element, which a
1716    /// pseudo-element has none of.
1717    fn reads_the_tree(&self) -> bool {
1718        matches!(
1719            self,
1720            Pseudo::Nth { .. }
1721                | Pseudo::Only { .. }
1722                | Pseudo::Empty
1723                | Pseudo::Root
1724                | Pseudo::Scope
1725                | Pseudo::Has(_)
1726                | Pseudo::Heading(_)
1727        )
1728    }
1729}
1730
1731impl Simple {
1732    fn specificity(&self) -> (u32, u32, u32) {
1733        match self {
1734            Simple::Id(_) => (1, 0, 0),
1735            Simple::Class(_) | Simple::Attr(_) => (0, 1, 0),
1736            Simple::Type { .. } => (0, 0, 1),
1737            Simple::Anchor | Simple::Ns(_) => (0, 0, 0),
1738            Simple::Pseudo(p) => match p {
1739                Pseudo::Is(list) | Pseudo::Not(list) | Pseudo::Has(list) => list.specificity(),
1740                Pseudo::Where(_) => (0, 0, 0),
1741                Pseudo::Nth { of: Some(list), .. } => {
1742                    let (a, b, c) = list.specificity();
1743                    (a, b + 1, c)
1744                }
1745                Pseudo::Element => (0, 0, 1),
1746                Pseudo::Host(Some(c)) | Pseudo::HostContext(c) => {
1747                    let (a, b, c) = c.specificity();
1748                    (a, b + 1, c)
1749                }
1750                Pseudo::Slotted(c) => {
1751                    let (a, b, c) = c.specificity();
1752                    (a, b, c + 1)
1753                }
1754                _ => (0, 1, 0),
1755            },
1756        }
1757    }
1758}
1759
1760/// The matches of [`SelectorList::select_iter`], in document order.
1761pub struct Select<'a> {
1762    list: &'a SelectorList,
1763    cx: Cx<'a>,
1764    scope: NodeId,
1765    at: Option<NodeId>,
1766}
1767
1768impl Iterator for Select<'_> {
1769    type Item = NodeId;
1770
1771    fn next(&mut self) -> Option<NodeId> {
1772        let doc = self.cx.doc;
1773        // A walk by the tree's own links, in document order: down to the
1774        // first child, else along to the next sibling, else back up.
1775        while let Some(n) = self.at {
1776            if self.cx.timed_out.get() {
1777                return None;
1778            }
1779            let element = doc.element(n).is_some();
1780            self.at = match doc.first_child(n).filter(|_| element) {
1781                Some(child) => Some(child),
1782                None => {
1783                    let mut up = Some(n);
1784                    let mut next = None;
1785                    while let Some(u) = up {
1786                        if u == self.scope {
1787                            break;
1788                        }
1789                        if let Some(s) = doc.next_sibling(u) {
1790                            next = Some(s);
1791                            break;
1792                        }
1793                        up = doc.parent(u);
1794                    }
1795                    next
1796                }
1797            };
1798            if element && self.list.0.iter().any(|c| self.cx.complex(c, n, n)) {
1799                return Some(n);
1800            }
1801        }
1802        None
1803    }
1804}
1805
1806fn push_children_reversed(doc: &Document, n: NodeId, stack: &mut Vec<NodeId>) {
1807    let at = stack.len();
1808    stack.extend(doc.children(n));
1809    stack[at..].reverse();
1810}
1811
1812// ---- matching --------------------------------------------------------------
1813
1814/// What matching needs that a document doesn't carry. The default has
1815/// none of it, so `:target` and `:local-link` match nothing.
1816#[derive(Debug, Clone, Copy, Default)]
1817pub struct MatchOptions<'a> {
1818    /// The document's URL, for `:target`, `:target-within` and `:local-link`.
1819    pub url: Option<&'a str>,
1820    /// Give up after this long. Most selectors cost a walk of the tree,
1821    /// but some cost more on some pages: a descendant combinator over a
1822    /// very deep tree, `:has()` of more than one compound. A crawler
1823    /// matching pages it doesn't control should set one. Only
1824    /// [`SelectorList::try_select_with`] and
1825    /// [`SelectorList::try_matches_with`] read it; the clock is read every
1826    /// 1,024 compounds matched.
1827    pub budget: Option<Duration>,
1828    /// Give up after matching this many compounds, which those two read
1829    /// as they read `budget`. It needs no clock, so it works where there
1830    /// is none to read, as on wasm32-unknown-unknown, and gives the same
1831    /// answer on any machine. A walk of the tree is a compound or so an
1832    /// element; a few hundred million is seconds of work.
1833    pub max_steps: Option<u64>,
1834}
1835
1836/// A query that ran past [`MatchOptions::budget`] or
1837/// [`MatchOptions::max_steps`].
1838#[derive(Debug, Clone, Copy, PartialEq, Eq)]
1839pub struct MatchTimeout {
1840    /// The budget, or zero when it was the step limit that ran out.
1841    pub budget: Duration,
1842    /// The step limit, when it was that which ran out.
1843    pub max_steps: Option<u64>,
1844}
1845
1846impl std::fmt::Display for MatchTimeout {
1847    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
1848        match self.max_steps {
1849            Some(steps) => write!(f, "matching took more than {steps} steps"),
1850            None => write!(f, "matching took longer than {:?}", self.budget),
1851        }
1852    }
1853}
1854
1855impl std::error::Error for MatchTimeout {}
1856
1857/// When a query with `options` gives up: never for a budget past what
1858/// the clock can count.
1859fn deadline(options: &MatchOptions<'_>) -> Option<Instant> {
1860    options.budget.and_then(|b| Instant::now().checked_add(b))
1861}
1862
1863fn timeout(cx: &Cx<'_>, options: &MatchOptions<'_>) -> Result<(), MatchTimeout> {
1864    if !cx.timed_out.get() {
1865        return Ok(());
1866    }
1867    let max_steps = options.max_steps.filter(|&m| cx.steps.get() > m);
1868    Err(MatchTimeout {
1869        budget: match max_steps {
1870            Some(_) => Duration::ZERO,
1871            None => options.budget.unwrap_or_default(),
1872        },
1873        max_steps,
1874    })
1875}
1876
1877/// The document's URL worked out once per query.
1878struct Page {
1879    /// Without its fragment.
1880    url: url::Url,
1881    /// What links resolve against: a `<base href>`, else the URL.
1882    base: url::Url,
1883    /// The element the fragment indicates.
1884    target: Option<NodeId>,
1885}
1886
1887impl Page {
1888    // Parsec's own WHATWG URL parser (#26) takes the url crate's place when it lands.
1889    fn new(doc: &Document, url: Option<&str>) -> Option<Page> {
1890        let mut url = url::Url::parse(url?).ok()?;
1891        let fragment = url.fragment().map(str::to_string);
1892        url.set_fragment(None);
1893        let elements = tree_elements(doc);
1894        let base = elements
1895            .iter()
1896            .find(|&&n| html_element_named(doc, n, "base") && attr_of(doc, n, "href").is_some())
1897            .and_then(|&n| url.join(attr_of(doc, n, "href")?).ok())
1898            .unwrap_or_else(|| url.clone());
1899        let target = fragment.and_then(|f| indicated(doc, &elements, &f));
1900        Some(Page { url, base, target })
1901    }
1902}
1903
1904/// The document's elements in tree order.
1905fn tree_elements(doc: &Document) -> Vec<NodeId> {
1906    let (mut out, mut stack) = (Vec::new(), vec![doc.root()]);
1907    while let Some(n) = stack.pop() {
1908        if doc.element(n).is_some() {
1909            out.push(n);
1910        }
1911        push_children_reversed(doc, n, &mut stack);
1912    }
1913    out
1914}
1915
1916fn html_element_named(doc: &Document, n: NodeId, name: &str) -> bool {
1917    doc.element(n).is_some_and(|e| e.ns == Ns::Html) && doc.lower_name(n) == Some(name)
1918}
1919
1920fn attr_of<'a>(doc: &'a Document, n: NodeId, name: &str) -> Option<&'a str> {
1921    doc.attrs(n)
1922        .find(|(ns, a, _)| *ns == AttrNs::None && *a == name)
1923        .map(|(_, _, v)| v)
1924}
1925
1926/// The HTML Standard's indicated part: the first element whose `id` is
1927/// the fragment, else the first `<a>` with that `name`; tried as given,
1928/// then percent-decoded. An empty fragment, or `top` with no element of
1929/// that name, indicates the top of the document, which is no element.
1930fn indicated(doc: &Document, elements: &[NodeId], fragment: &str) -> Option<NodeId> {
1931    if fragment.is_empty() {
1932        return None;
1933    }
1934    let find = |f: &str| {
1935        elements
1936            .iter()
1937            .copied()
1938            .find(|&n| attr_of(doc, n, "id") == Some(f))
1939            .or_else(|| {
1940                elements.iter().copied().find(|&n| {
1941                    html_element_named(doc, n, "a") && attr_of(doc, n, "name") == Some(f)
1942                })
1943            })
1944    };
1945    find(fragment).or_else(|| find(&percent_decode(fragment)))
1946}
1947
1948/// %XX escapes as bytes, read as UTF-8 with any bad sequence replaced.
1949fn percent_decode(s: &str) -> String {
1950    let b = s.as_bytes();
1951    let mut out = Vec::with_capacity(b.len());
1952    let mut i = 0;
1953    while i < b.len() {
1954        let hex = |c: u8| (c as char).to_digit(16);
1955        match (
1956            b[i],
1957            b.get(i + 1).and_then(|&c| hex(c)),
1958            b.get(i + 2).and_then(|&c| hex(c)),
1959        ) {
1960            (b'%', Some(h), Some(l)) => {
1961                out.push((h * 16 + l) as u8);
1962                i += 3;
1963            }
1964            (c, _, _) => {
1965                out.push(c);
1966                i += 1;
1967            }
1968        }
1969    }
1970    String::from_utf8_lossy(&out).into_owned()
1971}
1972
1973struct Cx<'a> {
1974    doc: &'a Document,
1975    scope: Option<NodeId>,
1976    /// The shadow root whose tree the selector is matched in, and its
1977    /// host; [`NONE`] for both in any other tree. There the host stands
1978    /// in for the root, as the parent of its top-level nodes, and only
1979    /// `:host` and `:host-context()` match it.
1980    shadow: NodeId,
1981    host: NodeId,
1982    page: Option<Page>,
1983    /// Steps left for `pattern` matches in this query, shared by all of them.
1984    pattern_budget: Cell<u32>,
1985    /// When to give up, for the `try_` queries, by the clock or by the
1986    /// count of compounds matched; `limited` if either is set.
1987    deadline: Option<Instant>,
1988    max_steps: u64,
1989    limited: bool,
1990    /// Compounds matched, while `limited`.
1991    steps: Cell<u64>,
1992    timed_out: Cell<bool>,
1993    /// Each element's place among its siblings, worked out for a whole
1994    /// parent the first time `:nth-*` needs one, so a query over a parent
1995    /// with n children counts them once rather than n times.
1996    places: RefCell<IdMap<NodeId, Place>>,
1997    /// The same for `:nth-child(An+B of S)`, keyed by S as well: each
1998    /// element matching S, its place among the siblings that do, and how
1999    /// many do.
2000    of_places: RefCell<IdMap<(usize, NodeId), (u32, u32)>>,
2001    /// For a `:has()` argument of one compound, keyed by it and an
2002    /// element: whether the element's subtree (`:has(x)`), or the element
2003    /// and its later siblings (`:has(~ x)`), hold a match. Every anchor
2004    /// asks the same question of the elements below or after it, so a
2005    /// query asks it of each element once.
2006    has_seen: RefCell<IdMap<(usize, NodeId), bool>>,
2007    /// Whether an element matches a selector of more than one compound
2008    /// inside `:is()`, `:where()` or `:not()`, by the selector's address:
2009    /// each level of such nesting tried every ancestor again for the level
2010    /// inside it, so the time doubled with each, as a stylesheet's nested
2011    /// rules (`& .x`) are written.
2012    nested_seen: RefCell<IdMap<(usize, NodeId), bool>>,
2013    /// Each table's columns, worked out the first time `||` or
2014    /// `:nth-col()` needs them, so a big table isn't laid out per cell.
2015    tables: RefCell<IdMap<NodeId, Rc<Columns>>>,
2016}
2017
2018/// A map keyed by node ids and selectors' addresses, numbers the parser
2019/// and the query hand out rather than the page, hashed with a multiply:
2020/// SipHash's guard against chosen keys guards nothing here, and made
2021/// `div:has(img)` half as slow again.
2022type IdMap<K, V> = HashMap<K, V, std::hash::BuildHasherDefault<IdHasher>>;
2023
2024#[derive(Default)]
2025struct IdHasher(u64);
2026
2027impl std::hash::Hasher for IdHasher {
2028    fn write(&mut self, bytes: &[u8]) {
2029        for &b in bytes {
2030            self.write_u64(b as u64);
2031        }
2032    }
2033
2034    fn write_u32(&mut self, n: u32) {
2035        self.write_u64(n as u64);
2036    }
2037
2038    fn write_usize(&mut self, n: usize) {
2039        self.write_u64(n as u64);
2040    }
2041
2042    fn write_u64(&mut self, n: u64) {
2043        self.0 = (self.0.rotate_left(5) ^ n).wrapping_mul(0x51_7c_c1_b7_27_22_0a_95);
2044    }
2045
2046    fn finish(&self) -> u64 {
2047        self.0
2048    }
2049}
2050
2051/// How far a failed part of a complex selector says to back up.
2052#[derive(Clone, Copy, PartialEq, Eq)]
2053enum Fail {
2054    /// The element didn't match: the part to the left may try another.
2055    Sibling,
2056    /// A sibling combinator ran out of siblings: back up to the nearest
2057    /// descendant combinator, which may try a higher ancestor.
2058    Descendant,
2059    /// A combinator ran out of ancestors: no higher one can help.
2060    Global,
2061}
2062
2063impl Fail {
2064    /// What running out of elements to try means for a combinator.
2065    fn exhausted(combinator: Combinator) -> Fail {
2066        match combinator {
2067            Combinator::NextSibling | Combinator::SubsequentSibling => Fail::Descendant,
2068            // Another cell may sit under other cols: the part to the right
2069            // may try one.
2070            Combinator::Column => Fail::Sibling,
2071            _ => Fail::Global,
2072        }
2073    }
2074}
2075
2076/// A table's columns by the HTML table model: the first column and how
2077/// many each cell and each `col` covers, and how many there are in all.
2078#[derive(Default)]
2079struct Columns {
2080    cells: HashMap<NodeId, (u32, u32)>,
2081    /// In column order, side by side.
2082    cols: Vec<(NodeId, u32, u32)>,
2083    /// Where each col is in `cols`, so `||` steps to the next in O(1).
2084    col_index: HashMap<NodeId, usize>,
2085    width: u32,
2086}
2087
2088/// The columns cells from earlier rows of a row group still cover, kept
2089/// as runs rather than slots, so time and memory follow the cells and not
2090/// the table's width, and a row with nothing reaching into it costs
2091/// nothing.
2092#[derive(Default)]
2093struct Cover {
2094    /// The row being laid out, counted from the group's first.
2095    row: u32,
2096    /// Disjoint runs: first column -> (column after the last, first row
2097    /// no longer covered), u32::MAX for rowspan=0.
2098    runs: BTreeMap<u32, (u32, u32)>,
2099    /// The runs' union as maximal contiguous blocks, first column ->
2100    /// column after the last, so finding a free column is one lookup
2101    /// however many runs sit side by side.
2102    blocks: BTreeMap<u32, u32>,
2103    /// Each run's last row, soonest first; an entry whose run has since
2104    /// been split or replaced is skipped.
2105    ends: BinaryHeap<Reverse<(u32, u32)>>,
2106}
2107
2108impl Cover {
2109    /// Drops the runs that stop before `row`.
2110    fn advance(&mut self, row: u32) {
2111        while let Some(&Reverse((until, start))) = self.ends.peek() {
2112            if until > row {
2113                break;
2114            }
2115            self.ends.pop();
2116            if let Some(&(end, u)) = self.runs.get(&start)
2117                && u == until
2118            {
2119                self.runs.remove(&start);
2120                let (&bs, &be) = self
2121                    .blocks
2122                    .range(..=start)
2123                    .next_back()
2124                    .expect("a run's block");
2125                self.blocks.remove(&bs);
2126                if bs < start {
2127                    self.blocks.insert(bs, start);
2128                }
2129                if end < be {
2130                    self.blocks.insert(end, be);
2131                }
2132            }
2133        }
2134    }
2135
2136    /// The first column from `x` that nothing covers.
2137    fn free(&self, x: u32) -> u32 {
2138        match self.blocks.range(..=x).next_back() {
2139            Some((_, &end)) if end > x => end,
2140            _ => x,
2141        }
2142    }
2143
2144    /// Covers `[start, end)` until row `until`. Where a run already covers
2145    /// part of it, a table model error, that part keeps the later row.
2146    fn add(&mut self, start: u32, end: u32, until: u32) {
2147        let mut over: Vec<(u32, u32, u32)> = Vec::new();
2148        if let Some((&rs, &(re, ru))) = self.runs.range(..start).next_back()
2149            && re > start
2150        {
2151            over.push((rs, re, ru));
2152        }
2153        over.extend(
2154            self.runs
2155                .range(start..end)
2156                .map(|(&rs, &(re, ru))| (rs, re, ru)),
2157        );
2158        let mut pieces = Vec::new();
2159        let mut at = start;
2160        for &(rs, re, ru) in &over {
2161            self.runs.remove(&rs);
2162            if rs < start {
2163                pieces.push((rs, start, ru));
2164            }
2165            let (os, oe) = (rs.max(start), re.min(end));
2166            if at < os {
2167                pieces.push((at, os, until));
2168            }
2169            pieces.push((os, oe, ru.max(until)));
2170            if re > end {
2171                pieces.push((end, re, ru));
2172            }
2173            at = oe;
2174        }
2175        if at < end {
2176            pieces.push((at, end, until));
2177        }
2178        for (ps, pe, pu) in pieces {
2179            self.runs.insert(ps, (pe, pu));
2180            self.ends.push(Reverse((pu, ps)));
2181        }
2182        // The union grows by [start, end): merge it with the blocks it
2183        // touches.
2184        let (mut bs, mut be) = (start, end);
2185        if let Some((&s, &e)) = self.blocks.range(..=start).next_back()
2186            && e >= start
2187        {
2188            bs = s;
2189            be = be.max(e);
2190            self.blocks.remove(&s);
2191        }
2192        while let Some((&s, &e)) = self.blocks.range(bs..=be).next() {
2193            self.blocks.remove(&s);
2194            be = be.max(e);
2195        }
2196        self.blocks.insert(bs, be);
2197    }
2198}
2199
2200/// An element's position among its parent's element children, counting
2201/// from 1, and among those of its own type.
2202#[derive(Clone, Copy)]
2203struct Place {
2204    index: u32,
2205    count: u32,
2206    type_index: u32,
2207    type_count: u32,
2208}
2209
2210/// HTML attributes whose values selectors compare without case, unless the
2211/// selector says `s` (the HTML Standard, "case-sensitivity of selectors").
2212fn case_insensitive_attr(name: &str) -> bool {
2213    matches!(
2214        name,
2215        "accept"
2216            | "accept-charset"
2217            | "align"
2218            | "alink"
2219            | "axis"
2220            | "bgcolor"
2221            | "charset"
2222            | "checked"
2223            | "clear"
2224            | "codetype"
2225            | "color"
2226            | "compact"
2227            | "declare"
2228            | "defer"
2229            | "dir"
2230            | "direction"
2231            | "disabled"
2232            | "enctype"
2233            | "face"
2234            | "frame"
2235            | "hreflang"
2236            | "http-equiv"
2237            | "lang"
2238            | "language"
2239            | "link"
2240            | "media"
2241            | "method"
2242            | "multiple"
2243            | "nohref"
2244            | "noresize"
2245            | "noshade"
2246            | "nowrap"
2247            | "readonly"
2248            | "rel"
2249            | "rev"
2250            | "rules"
2251            | "scope"
2252            | "scrolling"
2253            | "selected"
2254            | "shape"
2255            | "target"
2256            | "text"
2257            | "type"
2258            | "valign"
2259            | "valuetype"
2260            | "vlink"
2261    )
2262}
2263
2264fn is_space_char(c: char) -> bool {
2265    matches!(c, ' ' | '\t' | '\n' | '\r' | '\x0C')
2266}
2267
2268impl<'a> Cx<'a> {
2269    /// A context for matching in `in_tree`'s tree.
2270    fn new(doc: &'a Document, scope: Option<NodeId>, in_tree: NodeId, page: Option<Page>) -> Self {
2271        // Free when the document has no shadow roots.
2272        let (shadow, host) = match doc.shadow_roots.is_empty() {
2273            true => (NONE, NONE),
2274            false => {
2275                let root = doc.tree_root(in_tree);
2276                doc.shadow_host(root).map_or((NONE, NONE), |h| (root, h))
2277            }
2278        };
2279        Cx {
2280            doc,
2281            scope,
2282            shadow,
2283            host,
2284            page,
2285            pattern_budget: Cell::new(crate::pattern::SELECT_STEP_LIMIT),
2286            deadline: None,
2287            max_steps: u64::MAX,
2288            limited: false,
2289            steps: Cell::new(0),
2290            timed_out: Cell::new(false),
2291            places: RefCell::default(),
2292            of_places: RefCell::default(),
2293            has_seen: RefCell::default(),
2294            nested_seen: RefCell::default(),
2295            tables: RefCell::default(),
2296        }
2297    }
2298
2299    fn html_tag_of(&self, n: NodeId) -> Option<Tag> {
2300        self.doc
2301            .element(n)
2302            .filter(|e| e.ns == Ns::Html)
2303            .map(|e| e.tag)
2304    }
2305
2306    /// The table a cell belongs to: its row's, the row in the table or in
2307    /// one of its row groups.
2308    fn table_of_cell(&self, cell: NodeId) -> Option<NodeId> {
2309        if !matches!(self.html_tag_of(cell), Some(Tag::Td | Tag::Th)) {
2310            return None;
2311        }
2312        let tr = self
2313            .doc
2314            .parent(cell)
2315            .filter(|&p| self.html_tag_of(p) == Some(Tag::Tr))?;
2316        let p = self.doc.parent(tr)?;
2317        match self.html_tag_of(p)? {
2318            Tag::Table => Some(p),
2319            Tag::Thead | Tag::Tbody | Tag::Tfoot => self
2320                .doc
2321                .parent(p)
2322                .filter(|&t| self.html_tag_of(t) == Some(Tag::Table)),
2323            _ => None,
2324        }
2325    }
2326
2327    /// A cell's table's columns, and the cell's first column and span.
2328    fn cell_columns(&self, cell: NodeId) -> Option<(Rc<Columns>, u32, u32)> {
2329        let table = self.table_of_cell(cell)?;
2330        let columns = self.columns(table);
2331        let &(x, n) = columns.cells.get(&cell)?;
2332        Some((columns, x, n))
2333    }
2334
2335    fn columns(&self, table: NodeId) -> Rc<Columns> {
2336        if let Some(c) = self.tables.borrow().get(&table) {
2337            return c.clone();
2338        }
2339        let c = Rc::new(self.lay_out(table));
2340        self.tables.borrow_mut().insert(table, c.clone());
2341        c
2342    }
2343
2344    /// A `span`, `colspan` or `rowspan` as the HTML Standard reads it:
2345    /// missing, unparsable or zero gives 1, and it stops at `max`.
2346    fn span(&self, el: NodeId, name: &str, max: u32) -> u32 {
2347        self.attr(el, name)
2348            .and_then(parse_non_negative)
2349            .filter(|&n| n > 0)
2350            .map_or(1, |n| n.min(max))
2351    }
2352
2353    /// The HTML Standard's "forming a table", as far as columns go:
2354    /// `colgroup`s before the first row give the `col`s their columns,
2355    /// and each cell takes the first column its row leaves free, rows
2356    /// above reaching down with `rowspan` included.
2357    fn lay_out(&self, table: NodeId) -> Columns {
2358        let doc = self.doc;
2359        let mut out = Columns::default();
2360        let mut col_x = 0;
2361        let mut rows_started = false;
2362        let mut cover = Cover::default();
2363        for child in doc.children(table) {
2364            match self.html_tag_of(child) {
2365                Some(Tag::Colgroup) if !rows_started => {
2366                    let mut has_cols = false;
2367                    for c in doc.children(child) {
2368                        if self.html_tag_of(c) == Some(Tag::Col) {
2369                            has_cols = true;
2370                            let n = self.span(c, "span", 1000);
2371                            out.col_index.insert(c, out.cols.len());
2372                            out.cols.push((c, col_x, n));
2373                            col_x += n;
2374                        }
2375                    }
2376                    if !has_cols {
2377                        col_x += self.span(child, "span", 1000);
2378                    }
2379                }
2380                Some(Tag::Tr) => {
2381                    rows_started = true;
2382                    self.lay_out_row(child, &mut cover, &mut out);
2383                }
2384                Some(Tag::Thead | Tag::Tbody | Tag::Tfoot) => {
2385                    rows_started = true;
2386                    // Cells don't reach from one row group into another.
2387                    cover = Cover::default();
2388                    for r in doc.children(child) {
2389                        if self.html_tag_of(r) == Some(Tag::Tr) {
2390                            self.lay_out_row(r, &mut cover, &mut out);
2391                        }
2392                    }
2393                    cover = Cover::default();
2394                }
2395                _ => {}
2396            }
2397        }
2398        out.width = out.width.max(col_x);
2399        out
2400    }
2401
2402    fn lay_out_row(&self, tr: NodeId, cover: &mut Cover, out: &mut Columns) {
2403        let row = cover.row;
2404        cover.advance(row);
2405        let mut x = 0;
2406        for cell in self.doc.children(tr) {
2407            if !matches!(self.html_tag_of(cell), Some(Tag::Td | Tag::Th)) {
2408                continue;
2409            }
2410            x = cover.free(x);
2411            let span = self.span(cell, "colspan", 1000);
2412            let until = match self.attr(cell, "rowspan").and_then(parse_non_negative) {
2413                Some(0) => u32::MAX,
2414                n => row.saturating_add(n.map_or(1, |n| n.min(65534))),
2415            };
2416            cover.add(x, x + span, until);
2417            out.cells.insert(cell, (x, span));
2418            x += span;
2419            out.width = out.width.max(x);
2420        }
2421        cover.row += 1;
2422    }
2423
2424    /// `el`'s place among its siblings, or None if it has no parent.
2425    fn place(&self, el: NodeId) -> Option<Place> {
2426        if let Some(&p) = self.places.borrow().get(&el) {
2427            return Some(p);
2428        }
2429        let doc = self.doc;
2430        let parent = doc.parent(el)?;
2431        let kids: Vec<NodeId> = doc
2432            .children(parent)
2433            .filter(|&k| doc.element(k).is_some())
2434            .collect();
2435        // One entry per element type among the children: an example of it,
2436        // and how many there are so far. A few types are found by a scan;
2437        // past that by a key that's equal when same_type says so, as a
2438        // scan made a parent of n different types cost n²: a known HTML
2439        // tag by its number, any other by its name, which is the page's,
2440        // so hashed as std does.
2441        let mut types: Vec<(NodeId, u32)> = Vec::new();
2442        let mut keyed = false;
2443        let mut by_tag: IdMap<Tag, usize> = IdMap::default();
2444        let mut by_name: HashMap<(u8, Tag, &str), usize> = HashMap::new();
2445        fn file<'d>(
2446            doc: &'d Document,
2447            by_tag: &mut IdMap<Tag, usize>,
2448            by_name: &mut HashMap<(u8, Tag, &'d str), usize>,
2449            e: &'d crate::dom::Element,
2450            t: usize,
2451        ) {
2452            if e.ns == Ns::Html && e.tag != Tag::Other {
2453                by_tag.insert(e.tag, t);
2454            } else {
2455                by_name.insert((e.ns as u8, e.tag, doc.element_name(e)), t);
2456            }
2457        }
2458        let mut of_type = Vec::with_capacity(kids.len());
2459        for &k in &kids {
2460            let e = doc.element(k).unwrap();
2461            let found = if !keyed {
2462                types
2463                    .iter()
2464                    .position(|&(rep, _)| same_type(doc, doc.element(rep).unwrap(), e))
2465            } else if e.ns == Ns::Html && e.tag != Tag::Other {
2466                by_tag.get(&e.tag).copied()
2467            } else {
2468                by_name
2469                    .get(&(e.ns as u8, e.tag, doc.element_name(e)))
2470                    .copied()
2471            };
2472            let t = match found {
2473                Some(t) => t,
2474                None => {
2475                    types.push((k, 0));
2476                    if keyed {
2477                        file(doc, &mut by_tag, &mut by_name, e, types.len() - 1);
2478                    } else if types.len() > 16 {
2479                        keyed = true;
2480                        for (i, &(rep, _)) in types.iter().enumerate() {
2481                            let rep = doc.element(rep).unwrap();
2482                            file(doc, &mut by_tag, &mut by_name, rep, i);
2483                        }
2484                    }
2485                    types.len() - 1
2486                }
2487            };
2488            types[t].1 += 1;
2489            of_type.push((t, types[t].1));
2490        }
2491        let mut places = self.places.borrow_mut();
2492        places.reserve(kids.len());
2493        for (i, (&k, &(t, type_index))) in kids.iter().zip(&of_type).enumerate() {
2494            places.insert(
2495                k,
2496                Place {
2497                    index: i as u32 + 1,
2498                    count: kids.len() as u32,
2499                    type_index,
2500                    type_count: types[t].1,
2501                },
2502            );
2503        }
2504        places.get(&el).copied()
2505    }
2506
2507    /// `el`'s place among its siblings that match `of`, and how many do,
2508    /// worked out for the whole parent at once; None if it has no parent
2509    /// or doesn't match.
2510    fn of_place(&self, of: &SelectorList, el: NodeId) -> Option<(u32, u32)> {
2511        let key = std::ptr::from_ref(of) as usize;
2512        if let Some(&p) = self.of_places.borrow().get(&(key, el)) {
2513            return Some(p);
2514        }
2515        let doc = self.doc;
2516        let parent = doc.parent(el)?;
2517        let kids: Vec<NodeId> = doc
2518            .children(parent)
2519            .filter(|&k| doc.element(k).is_some() && of.0.iter().any(|c| self.complex(c, k, k)))
2520            .collect();
2521        let mut places = self.of_places.borrow_mut();
2522        for (i, &k) in kids.iter().enumerate() {
2523            places.insert((key, k), (i as u32 + 1, kids.len() as u32));
2524        }
2525        places.get(&(key, el)).copied()
2526    }
2527
2528    /// Whether `el` is at an+b among its siblings (of its type), by the
2529    /// places worked out for its parent; None if it has no parent.
2530    #[inline(never)]
2531    fn nth_by_place(&self, el: NodeId, a: i32, b: i32, last: bool, of_type: bool) -> Option<bool> {
2532        let pl = self.place(el)?;
2533        let (index, count) = if of_type {
2534            (pl.type_index, pl.type_count)
2535        } else {
2536            (pl.index, pl.count)
2537        };
2538        let index = if last { count - index + 1 } else { index };
2539        Some(nth_matches(a as i64, b as i64, index as i64))
2540    }
2541
2542    fn parent_element(&self, n: NodeId) -> Option<NodeId> {
2543        self.doc
2544            .parent(n)
2545            .filter(|&p| self.doc.element(p).is_some())
2546    }
2547
2548    fn prev_element(&self, n: NodeId) -> Option<NodeId> {
2549        let mut at = self.doc.prev_sibling(n);
2550        while let Some(p) = at {
2551            if self.doc.element(p).is_some() {
2552                return Some(p);
2553            }
2554            at = self.doc.prev_sibling(p);
2555        }
2556        None
2557    }
2558
2559    fn next_element(&self, n: NodeId) -> Option<NodeId> {
2560        let mut at = self.doc.next_sibling(n);
2561        while let Some(p) = at {
2562            if self.doc.element(p).is_some() {
2563                return Some(p);
2564            }
2565            at = self.doc.next_sibling(p);
2566        }
2567        None
2568    }
2569
2570    /// Does `el` match `c`? `anchor` is the element a relative selector in
2571    /// `:has()` hangs from.
2572    ///
2573    /// A loop over the parts, not a call per part: a selector can chain as
2574    /// many compounds as it likes, and a call each overflowed the stack.
2575    /// When a part fails, it backs up only as far as can help, as browsers
2576    /// do. If the rest found no ancestor at all, no higher one will do; if
2577    /// a sibling failed, the nearest descendant combinator tries the next
2578    /// ancestor. Trying every choice instead made `x div div ...` over a
2579    /// few dozen nested divs take seconds.
2580    fn complex(&self, c: &Complex, el: NodeId, anchor: NodeId) -> bool {
2581        if let Some(Simple::Pseudo(Pseudo::Slotted(arg))) = c.parts[0].0.0.first() {
2582            return self.slotted(c, arg, el, anchor);
2583        }
2584        // The subject first, here, so a one-part selector costs no more.
2585        self.compound(&c.parts[0].0, el, anchor)
2586            && (c.parts.len() == 1 || self.complex_rest(c, el, anchor))
2587    }
2588
2589    /// `X::slotted(arg)`, `el` the subject: an element `arg` matches,
2590    /// assigned after flattening to a slot in this shadow tree, which the
2591    /// rest of the selector matches from there.
2592    #[cold]
2593    fn slotted(&self, c: &Complex, arg: &Compound, el: NodeId, anchor: NodeId) -> bool {
2594        if self.shadow == NONE || self.doc.element(el).is_none() {
2595            return false;
2596        }
2597        let mut slot = self.doc.assigned_slot(el);
2598        while let Some(s) = slot {
2599            if self.doc.tree_root(s) == self.shadow {
2600                break;
2601            }
2602            slot = self.doc.assigned_slot(s);
2603        }
2604        let Some(slot) = slot else {
2605            return false;
2606        };
2607        self.simples(&arg.0, el, anchor)
2608            && self.compound_of(&c.parts[0].0.0[1..], slot, anchor)
2609            && (c.parts.len() == 1 || self.complex_rest(c, slot, anchor))
2610    }
2611
2612    /// The parts after the subject, which `el` matched.
2613    #[inline(never)]
2614    fn complex_rest(&self, c: &Complex, el: NodeId, anchor: NodeId) -> bool {
2615        let parts = &c.parts;
2616        // Two parts, the commonest chain, have no part further left to back
2617        // up to: try each element the combinator reaches, and stop.
2618        if let [(_, combinator), (left, _)] = parts.as_slice() {
2619            let mut at = self.step(*combinator, el);
2620            while let Some(p) = at {
2621                if self.compound(left, p, anchor) {
2622                    return true;
2623                }
2624                if matches!(combinator, Combinator::Child | Combinator::NextSibling) {
2625                    return false;
2626                }
2627                at = self.next_step(*combinator, el, p);
2628            }
2629            return false;
2630        }
2631        // What each part left of the current one matched, to back up to.
2632        let mut inline = [0; 16];
2633        let mut spilled;
2634        let matched: &mut [NodeId] = if parts.len() <= inline.len() {
2635            &mut inline
2636        } else {
2637            spilled = vec![0; parts.len()];
2638            &mut spilled
2639        };
2640        matched[0] = el;
2641        let Some(next) = self.step(parts[0].1, el) else {
2642            return false;
2643        };
2644        // In `:has()`, only the last part, the anchor, may match the anchor,
2645        // and nothing matches above it (or above its siblings, after `~`
2646        // or `+`): from there no combinator leads back. Reaching one is
2647        // running out, so a chain under a deep anchor stops there rather
2648        // than at the root.
2649        let fence = matches!(parts.last(), Some((Compound(s), _)) if matches!(s.as_slice(), [Simple::Anchor]))
2650            .then(|| (anchor, self.step(Combinator::Child, anchor)));
2651        let fenced = |i: usize, at: NodeId| {
2652            i + 1 < parts.len() && fence.is_some_and(|(a, up)| at == a || Some(at) == up)
2653        };
2654        let (mut i, mut at) = (1, next);
2655        loop {
2656            let mut fail = if fenced(i, at) {
2657                Fail::exhausted(parts[i - 1].1)
2658            } else if !self.compound(&parts[i].0, at, anchor) {
2659                Fail::Sibling
2660            } else if i + 1 == parts.len() {
2661                return true;
2662            } else {
2663                let combinator = parts[i].1;
2664                match self.step(combinator, at) {
2665                    Some(next) => {
2666                        matched[i] = at;
2667                        (i, at) = (i + 1, next);
2668                        continue;
2669                    }
2670                    None => Fail::exhausted(combinator),
2671                }
2672            };
2673            // `at` failed parts[i]; back up to the part left of it.
2674            loop {
2675                if i == 0 || fail == Fail::Global {
2676                    return false;
2677                }
2678                i -= 1;
2679                let combinator = parts[i].1;
2680                let retry = match (fail, combinator) {
2681                    (_, Combinator::Child) => {
2682                        fail = Fail::Descendant;
2683                        false
2684                    }
2685                    (_, Combinator::NextSibling)
2686                    | (Fail::Descendant, Combinator::SubsequentSibling) => false,
2687                    _ => true,
2688                };
2689                if retry {
2690                    if let Some(next) = self.next_step(combinator, matched[i], at) {
2691                        (i, at) = (i + 1, next);
2692                        break;
2693                    }
2694                    fail = Fail::exhausted(combinator);
2695                }
2696                at = matched[i];
2697            }
2698        }
2699    }
2700
2701    /// The element a combinator looks at next from `el`: its parent, or
2702    /// its previous element sibling.
2703    #[inline]
2704    fn step(&self, combinator: Combinator, el: NodeId) -> Option<NodeId> {
2705        // In a shadow tree the host is the root's stand-in: the parent of
2706        // its top-level nodes, with no parent or siblings of its own.
2707        if el == self.host {
2708            return None;
2709        }
2710        match combinator {
2711            Combinator::Child | Combinator::Descendant => {
2712                let parent = self.doc.parent(el);
2713                if parent == Some(self.shadow) {
2714                    Some(self.host)
2715                } else {
2716                    parent
2717                }
2718            }
2719            Combinator::NextSibling | Combinator::SubsequentSibling => self.prev_element(el),
2720            Combinator::Column => self.col_after(el, None),
2721            Combinator::None => None,
2722        }
2723    }
2724
2725    /// The element after `prev` that `combinator` reaches from `origin`:
2726    /// the next one up or back from `prev`, or for `||`, the next col
2727    /// over `origin`'s columns, which `prev` alone can't say.
2728    fn next_step(&self, combinator: Combinator, origin: NodeId, prev: NodeId) -> Option<NodeId> {
2729        match combinator {
2730            Combinator::Column => self.col_after(origin, Some(prev)),
2731            _ => self.step(combinator, prev),
2732        }
2733    }
2734
2735    /// The cols over any of a cell's columns, in column order: the first,
2736    /// or the one after `prev`.
2737    fn col_after(&self, cell: NodeId, prev: Option<NodeId>) -> Option<NodeId> {
2738        let (t, x, n) = self.cell_columns(cell)?;
2739        let i = match prev {
2740            None => t.cols.partition_point(|&(_, cx, cn)| cx + cn <= x),
2741            Some(p) => t.col_index.get(&p)? + 1,
2742        };
2743        t.cols
2744            .get(i)
2745            .filter(|&&(_, cx, _)| cx < x + n)
2746            .map(|&(col, ..)| col)
2747    }
2748
2749    /// Whether the budget has run out. Once it has, every compound fails,
2750    /// so whatever is matching unwinds quickly. Out of line, so a query
2751    /// without a budget pays one test of `deadline` per compound.
2752    #[cold]
2753    #[inline(never)]
2754    fn out_of_time(&self) -> bool {
2755        let steps = self.steps.get().saturating_add(1);
2756        self.steps.set(steps);
2757        if steps > self.max_steps
2758            || steps.is_multiple_of(1024) && self.deadline.is_some_and(|d| Instant::now() >= d)
2759        {
2760            self.timed_out.set(true);
2761        }
2762        self.timed_out.get()
2763    }
2764
2765    /// Sets the limits the `try_` queries give up at.
2766    fn limit(&mut self, options: &MatchOptions<'_>) {
2767        self.deadline = deadline(options);
2768        self.max_steps = options.max_steps.unwrap_or(u64::MAX);
2769        self.limited = self.deadline.is_some() || options.max_steps.is_some();
2770    }
2771
2772    fn compound(&self, compound: &Compound, el: NodeId, anchor: NodeId) -> bool {
2773        self.compound_of(&compound.0, el, anchor)
2774    }
2775
2776    fn compound_of(&self, simples: &[Simple], el: NodeId, anchor: NodeId) -> bool {
2777        // The host is featureless in its shadow tree: only `:host` and
2778        // `:host-context()`, alone or in `:is()` or `:where()`, match it,
2779        // and a `:has()` inside `:host()` reaching back to it.
2780        if el == self.host
2781            && !matches!(simples, [Simple::Anchor])
2782            && (simples.is_empty()
2783                || !simples.iter().all(|s| {
2784                    matches!(
2785                        s,
2786                        Simple::Pseudo(
2787                            Pseudo::Host(_)
2788                                | Pseudo::HostContext(_)
2789                                | Pseudo::Is(_)
2790                                | Pseudo::Where(_)
2791                        )
2792                    )
2793                }))
2794        {
2795            return false;
2796        }
2797        self.simples(simples, el, anchor)
2798    }
2799
2800    /// Whether `el` matches every one of a compound's simple selectors,
2801    /// as anywhere else: the host isn't featureless here.
2802    fn simples(&self, simples: &[Simple], el: NodeId, anchor: NodeId) -> bool {
2803        if self.limited && self.out_of_time() {
2804            return false;
2805        }
2806        if matches!(simples, [Simple::Anchor]) {
2807            return el == anchor;
2808        }
2809        let Some(e) = self.doc.element(el) else {
2810            return false;
2811        };
2812        simples.iter().all(|s| match s {
2813            Simple::Type { lower, exact, tag } => {
2814                if e.ns == Ns::Html {
2815                    if *tag != Tag::Other || e.tag != Tag::Other {
2816                        e.tag == *tag
2817                    } else {
2818                        self.doc.element_name(e) == lower
2819                    }
2820                } else if e.ns == Ns::Xml {
2821                    // In XML a type selector names the local part, in any
2822                    // case: `creator` finds `dc:creator` and `Creator`.
2823                    xml_local(self.doc.element_name(e)).eq_ignore_ascii_case(lower)
2824                } else {
2825                    self.doc.element_name(e) == exact
2826                }
2827            }
2828            Simple::Id(id) => self.attr(el, "id").is_some_and(|v| self.quirks_eq(v, id)),
2829            Simple::Class(class) => self.attr(el, "class").is_some_and(|v| {
2830                v.split(is_space_char)
2831                    .any(|c| !c.is_empty() && self.quirks_eq(c, class))
2832            }),
2833            Simple::Attr(a) => self.attr_matches(el, e.ns, a),
2834            Simple::Pseudo(p) => self.pseudo(p, el, anchor),
2835            Simple::Anchor => el == anchor,
2836            Simple::Ns(ns) => e.ns == *ns,
2837        })
2838    }
2839
2840    fn quirks_eq(&self, a: &str, b: &str) -> bool {
2841        if self.doc.quirks() == Quirks::Quirks {
2842            a.eq_ignore_ascii_case(b)
2843        } else {
2844            a == b
2845        }
2846    }
2847
2848    /// The element's language: the nearest `xml:lang` or `lang` on it or
2849    /// an ancestor, `xml:lang` first, as HTML has it. None when nothing says.
2850    fn lang(&self, el: NodeId) -> Option<&str> {
2851        let mut at = Some(el);
2852        while let Some(n) = at {
2853            let mut plain = None;
2854            for (ns, name, value) in self.doc.attrs(n) {
2855                match (ns, name) {
2856                    (AttrNs::Xml, "lang") => return Some(value),
2857                    (AttrNs::None, "lang") => plain = Some(value),
2858                    _ => {}
2859                }
2860            }
2861            if plain.is_some() {
2862                return plain;
2863            }
2864            at = self.doc.parent(n);
2865        }
2866        None
2867    }
2868
2869    /// Whether the element's directionality is right to left, by HTML's
2870    /// rules as far as the document decides them: `dir="ltr"` or `"rtl"`,
2871    /// `dir="auto"` and `<bdi>` from their text, and otherwise the parent's,
2872    /// left to right at the top. Only an HTML element's `dir` counts.
2873    fn is_rtl(&self, el: NodeId) -> bool {
2874        let mut at = Some(el);
2875        while let Some(n) = at {
2876            let Some(e) = self.doc.element(n) else {
2877                return false;
2878            };
2879            if e.ns == Ns::Html {
2880                match self.dir(n).as_deref() {
2881                    Some("ltr") => return false,
2882                    Some("rtl") => return true,
2883                    Some("auto") => return self.auto_rtl(n),
2884                    _ if self.doc.lower_name(n) == Some("bdi") => return self.auto_rtl(n),
2885                    _ => {}
2886                }
2887            }
2888            at = self.doc.parent(n);
2889        }
2890        false
2891    }
2892
2893    /// A valid `dir` value, lowercased.
2894    fn dir(&self, el: NodeId) -> Option<String> {
2895        self.attr(el, "dir")
2896            .map(|d| d.to_ascii_lowercase())
2897            .filter(|d| matches!(d.as_str(), "ltr" | "rtl" | "auto"))
2898    }
2899
2900    /// `dir="auto"`: right to left when the first strong character is. A
2901    /// text field reads its value; anything else its text, leaving out
2902    /// `<bdi>`, `<script>`, `<style>`, `<textarea>` and anything with its own
2903    /// `dir`. No strong character at all is left to right.
2904    fn auto_rtl(&self, el: NodeId) -> bool {
2905        let tag = self.doc.element(el).map(|e| e.tag);
2906        if tag == Some(Tag::Textarea) {
2907            return first_strong_rtl(&self.doc.text(el)).unwrap_or(false);
2908        }
2909        if tag == Some(Tag::Input) {
2910            let text_field = self.attr(el, "type").is_none_or(|t| {
2911                matches!(
2912                    t.to_ascii_lowercase().as_str(),
2913                    "text" | "search" | "tel" | "url" | "email"
2914                )
2915            });
2916            return text_field
2917                && first_strong_rtl(self.attr(el, "value").unwrap_or("")).unwrap_or(false);
2918        }
2919        let mut stack: Vec<NodeId> = self.doc.children(el).collect();
2920        stack.reverse();
2921        while let Some(n) = stack.pop() {
2922            match self.doc.kind(n) {
2923                crate::Kind::Text(t) => {
2924                    if let Some(rtl) = first_strong_rtl(t) {
2925                        return rtl;
2926                    }
2927                }
2928                crate::Kind::Element { ns, .. } => {
2929                    let skip = ns == Ns::Html
2930                        && (self.dir(n).is_some()
2931                            || matches!(
2932                                self.doc.element(n).map(|e| e.tag),
2933                                Some(Tag::Script | Tag::Style | Tag::Textarea)
2934                            )
2935                            || self.doc.lower_name(n) == Some("bdi"));
2936                    if !skip {
2937                        let at = stack.len();
2938                        stack.extend(self.doc.children(n));
2939                        stack[at..].reverse();
2940                    }
2941                }
2942                _ => {}
2943            }
2944        }
2945        false
2946    }
2947
2948    /// Whether `el` is an `<input>` whose type, in any case, is one of `types`.
2949    fn input_type(&self, el: NodeId, types: &[&str]) -> bool {
2950        self.attr(el, "type")
2951            .is_some_and(|t| types.iter().any(|w| t.eq_ignore_ascii_case(w)))
2952    }
2953
2954    fn html_tag(&self, n: NodeId, tag: Tag) -> bool {
2955        self.doc
2956            .element(n)
2957            .is_some_and(|e| e.ns == Ns::Html && e.tag == tag)
2958    }
2959
2960    fn html_named(&self, n: NodeId, name: &str) -> bool {
2961        self.doc.element(n).is_some_and(|e| e.ns == Ns::Html)
2962            && self.doc.lower_name(n) == Some(name)
2963    }
2964
2965    /// `el`'s tree in tree order, from its root.
2966    // shortcut: walked afresh for each control matched, so :default or
2967    // :indeterminate over a page of n radio buttons is O(n^2); keep a
2968    // per-select index of forms and radio groups if pages ever have
2969    // thousands.
2970    fn tree_of(&self, el: NodeId) -> Vec<NodeId> {
2971        let mut root = el;
2972        while let Some(p) = self.doc.parent(root) {
2973            root = p;
2974        }
2975        let (mut out, mut stack) = (Vec::new(), vec![root]);
2976        while let Some(n) = stack.pop() {
2977            out.push(n);
2978            let at = stack.len();
2979            stack.extend(self.doc.children(n));
2980            stack[at..].reverse();
2981        }
2982        out
2983    }
2984
2985    /// The form a control belongs to: the one its `form` attribute names,
2986    /// or with no such attribute the nearest form around it.
2987    fn form_owner(&self, el: NodeId) -> Option<NodeId> {
2988        if let Some(id) = self.attr(el, "form") {
2989            return self
2990                .tree_of(el)
2991                .into_iter()
2992                .find(|&n| self.doc.element(n).is_some() && self.attr(n, "id") == Some(id))
2993                .filter(|&f| self.html_tag(f, Tag::Form));
2994        }
2995        let mut at = self.parent_element(el);
2996        while let Some(p) = at {
2997            if self.html_tag(p, Tag::Form) {
2998                return Some(p);
2999            }
3000            at = self.parent_element(p);
3001        }
3002        None
3003    }
3004
3005    fn submit_button(&self, el: NodeId, tag: Tag) -> bool {
3006        match tag {
3007            // A button's type is submit unless it says reset or button.
3008            Tag::Button => self.attr(el, "type").is_none_or(|t| {
3009                !t.eq_ignore_ascii_case("reset") && !t.eq_ignore_ascii_case("button")
3010            }),
3011            Tag::Input => self.input_type(el, &["submit", "image"]),
3012            _ => false,
3013        }
3014    }
3015
3016    /// Whether `el` is its form's default button: the first submit button
3017    /// in tree order that belongs to the same form.
3018    fn default_button(&self, el: NodeId, tag: Tag) -> bool {
3019        if !self.submit_button(el, tag) {
3020            return false;
3021        }
3022        let Some(form) = self.form_owner(el) else {
3023            return false;
3024        };
3025        self.tree_of(el).into_iter().find(|&n| {
3026            self.doc.element(n).is_some_and(|e| {
3027                e.ns == Ns::Html && self.submit_button(n, e.tag) && self.form_owner(n) == Some(form)
3028            })
3029        }) == Some(el)
3030    }
3031
3032    /// Whether no radio button in `el`'s group is checked: the radio
3033    /// buttons with its name and form, in its tree. With no name it's a
3034    /// group of one.
3035    fn radio_group_unchecked(&self, el: NodeId) -> bool {
3036        if self.attr(el, "checked").is_some() {
3037            return false;
3038        }
3039        let Some(name) = self.attr(el, "name").filter(|n| !n.is_empty()) else {
3040            return true;
3041        };
3042        let form = self.form_owner(el);
3043        !self.tree_of(el).into_iter().any(|n| {
3044            self.html_tag(n, Tag::Input)
3045                && self.input_type(n, &["radio"])
3046                && self.attr(n, "name") == Some(name)
3047                && self.attr(n, "checked").is_some()
3048                && self.form_owner(n) == form
3049        })
3050    }
3051
3052    /// For an `<input>` with range limitations that takes part in
3053    /// validation, whether its value is in range; None for any other.
3054    /// An empty or unreadable value isn't out of range, and a range
3055    /// input's value is always brought into range.
3056    fn in_range(&self, el: NodeId) -> Option<bool> {
3057        let typ = self.attr(el, "type")?.to_ascii_lowercase();
3058        let read = |name: &str| self.attr(el, name).and_then(|v| input_number(&typ, v));
3059        let (min, max) = match typ.as_str() {
3060            "range" => (read("min").or(Some(0.0)), read("max").or(Some(100.0))),
3061            "number" | "date" | "month" | "week" | "time" | "datetime-local" => {
3062                (read("min"), read("max"))
3063            }
3064            _ => return None,
3065        };
3066        if min.is_none() && max.is_none() {
3067            return None;
3068        }
3069        // Barred from validation: disabled, read-only where that applies,
3070        // or inside a datalist.
3071        let in_datalist = {
3072            let mut at = self.parent_element(el);
3073            let mut found = false;
3074            while let Some(p) = at {
3075                if self.html_named(p, "datalist") {
3076                    found = true;
3077                    break;
3078                }
3079                at = self.parent_element(p);
3080            }
3081            found
3082        };
3083        if self.disabled(el, Tag::Input)
3084            || (typ != "range" && self.attr(el, "readonly").is_some())
3085            || in_datalist
3086        {
3087            return None;
3088        }
3089        if typ == "range" {
3090            return Some(true);
3091        }
3092        let Some(value) = read("value") else {
3093            return Some(true);
3094        };
3095        Some(match (min, max) {
3096            // A time range may wrap past midnight: 22:00 to 06:00.
3097            (Some(lo), Some(hi)) if typ == "time" && lo > hi => value >= lo || value <= hi,
3098            _ => min.is_none_or(|lo| value >= lo) && max.is_none_or(|hi| value <= hi),
3099        })
3100    }
3101
3102    /// For `:valid` and `:invalid`: whether `el` satisfies its constraints,
3103    /// or for a form or fieldset whether everything in it does; None for an
3104    /// element that doesn't take part in validation.
3105    fn valid(&self, el: NodeId, tag: Tag) -> Option<bool> {
3106        match tag {
3107            Tag::Form => Some(!self.tree_of(el).into_iter().any(|n| {
3108                self.doc.element(n).is_some_and(|e| e.ns == Ns::Html)
3109                    && self.form_owner(n) == Some(el)
3110                    && self.control_valid(n) == Some(false)
3111            })),
3112            Tag::Fieldset => {
3113                let mut stack: Vec<NodeId> = self.doc.children(el).collect();
3114                while let Some(n) = stack.pop() {
3115                    if self.control_valid(n) == Some(false) {
3116                        return Some(false);
3117                    }
3118                    stack.extend(self.doc.children(n));
3119                }
3120                Some(true)
3121            }
3122            _ => self.control_valid(el),
3123        }
3124    }
3125
3126    /// Whether a form control satisfies its constraints, None when it's
3127    /// barred from validation. The static document's value is the `value`
3128    /// attribute, or a textarea's text. Only what the markup decides is
3129    /// checked: not too long, too short or bad input, which only someone
3130    /// typing can cause.
3131    fn control_valid(&self, el: NodeId) -> Option<bool> {
3132        let e = self.doc.element(el)?;
3133        if e.ns != Ns::Html || self.disabled(el, e.tag) || self.in_datalist(el) {
3134            return None;
3135        }
3136        let required = self.attr(el, "required").is_some();
3137        match e.tag {
3138            Tag::Input => {
3139                let typ = input_type_state(self.attr(el, "type"));
3140                if matches!(typ, "hidden" | "reset" | "button")
3141                    || (readonly_applies(typ) && self.attr(el, "readonly").is_some())
3142                {
3143                    return None;
3144                }
3145                Some(self.input_valid(el, typ, required))
3146            }
3147            Tag::Textarea => {
3148                if self.attr(el, "readonly").is_some() {
3149                    return None;
3150                }
3151                Some(!required || !self.doc.text(el).is_empty())
3152            }
3153            Tag::Select => Some(!required || self.select_has_value(el)),
3154            Tag::Button => self.submit_button(el, Tag::Button).then_some(true),
3155            _ => None,
3156        }
3157    }
3158
3159    fn input_valid(&self, el: NodeId, typ: &str, required: bool) -> bool {
3160        match typ {
3161            "checkbox" => !required || self.attr(el, "checked").is_some(),
3162            "radio" => !self.radio_value_missing(el),
3163            // A static page has no files chosen.
3164            "file" => !required,
3165            "submit" | "image" | "color" | "range" => true,
3166            _ => {
3167                let value = sanitized(
3168                    typ,
3169                    self.attr(el, "value").unwrap_or(""),
3170                    self.attr(el, "multiple").is_some(),
3171                );
3172                if value.is_empty() {
3173                    return !required;
3174                }
3175                let multiple = typ == "email" && self.attr(el, "multiple").is_some();
3176                if !self.pattern_fits(el, typ, &value, multiple) {
3177                    return false;
3178                }
3179                match typ {
3180                    "email" if self.attr(el, "multiple").is_some() => {
3181                        value.split(',').all(valid_email)
3182                    }
3183                    "email" => valid_email(&value),
3184                    "url" => url::Url::parse(&value).is_ok(),
3185                    "number" | "date" | "month" | "week" | "time" | "datetime-local" => {
3186                        self.in_range(el) != Some(false) && self.step_fits(el, typ, &value)
3187                    }
3188                    _ => true,
3189                }
3190            }
3191        }
3192    }
3193
3194    /// Whether the value matches `pattern`, for the types it applies to:
3195    /// each value of a multiple email. A pattern that doesn't compile counts
3196    /// as none, as the standard says.
3197    fn pattern_fits(&self, el: NodeId, typ: &str, value: &str, multiple: bool) -> bool {
3198        if !matches!(
3199            typ,
3200            "text" | "search" | "tel" | "url" | "email" | "password"
3201        ) {
3202            return true;
3203        }
3204        let Some(pattern) = self.attr(el, "pattern").and_then(Pattern::compile) else {
3205            return true;
3206        };
3207        if multiple {
3208            value
3209                .split(',')
3210                .all(|v| pattern.matches(v, &self.pattern_budget))
3211        } else {
3212            pattern.matches(value, &self.pattern_budget)
3213        }
3214    }
3215
3216    /// Whether the value lands on a step from `min`. With no valid `min` the
3217    /// step base is the value itself, so any value fits.
3218    fn step_fits(&self, el: NodeId, typ: &str, value: &str) -> bool {
3219        let (default, scale) = match typ {
3220            "week" => (1.0, 7.0),
3221            "time" | "datetime-local" => (60.0, 1000.0),
3222            _ => (1.0, 1.0),
3223        };
3224        let step = match self.attr(el, "step") {
3225            Some(s) if s.eq_ignore_ascii_case("any") => return true,
3226            Some(s) => parse_float_value(s).filter(|&s| s > 0.0).unwrap_or(default),
3227            None => default,
3228        };
3229        let (Some(value), Some(base)) = (
3230            input_number(typ, value),
3231            self.attr(el, "min").and_then(|m| input_number(typ, m)),
3232        ) else {
3233            return true;
3234        };
3235        let steps = (value - base) / (step * scale);
3236        (steps - steps.round()).abs() < 1e-9
3237    }
3238
3239    /// Whether `el`'s radio group is required and has nothing checked.
3240    fn radio_value_missing(&self, el: NodeId) -> bool {
3241        let Some(name) = self.attr(el, "name").filter(|n| !n.is_empty()) else {
3242            return self.attr(el, "required").is_some() && self.attr(el, "checked").is_none();
3243        };
3244        let form = self.form_owner(el);
3245        let group: Vec<NodeId> = self
3246            .tree_of(el)
3247            .into_iter()
3248            .filter(|&n| {
3249                self.html_tag(n, Tag::Input)
3250                    && self.input_type(n, &["radio"])
3251                    && self.attr(n, "name") == Some(name)
3252                    && self.form_owner(n) == form
3253            })
3254            .collect();
3255        group.iter().any(|&n| self.attr(n, "required").is_some())
3256            && group.iter().all(|&n| self.attr(n, "checked").is_none())
3257    }
3258
3259    /// Whether a select has a value to submit: an option selected, and in a
3260    /// one-line single select not the placeholder (a first child option
3261    /// whose value is empty).
3262    fn select_has_value(&self, el: NodeId) -> bool {
3263        let mut options = Vec::new();
3264        let mut stack: Vec<NodeId> = self.doc.children(el).collect();
3265        stack.reverse();
3266        while let Some(n) = stack.pop() {
3267            if self.html_tag(n, Tag::Option) {
3268                options.push(n);
3269            } else if self.html_tag(n, Tag::Optgroup) {
3270                let at = stack.len();
3271                stack.extend(self.doc.children(n));
3272                stack[at..].reverse();
3273            }
3274        }
3275        let marked = |n: &&NodeId| self.attr(**n, "selected").is_some();
3276        let multiple = self.attr(el, "multiple").is_some();
3277        let size = self
3278            .attr(el, "size")
3279            .and_then(parse_non_negative)
3280            .filter(|&s| s > 0)
3281            .unwrap_or(if multiple { 4 } else { 1 });
3282        if multiple {
3283            return options.iter().any(|n| marked(&n));
3284        }
3285        // The last one marked selected wins. With none, a one-line select
3286        // shows its first option that isn't disabled; a list box shows none.
3287        let selected = options.iter().rev().find(marked).or_else(|| {
3288            options
3289                .iter()
3290                .filter(|_| size == 1)
3291                .find(|&&n| self.attr(n, "disabled").is_none() && !self.disabled(n, Tag::Option))
3292        });
3293        let Some(&selected) = selected else {
3294            return false;
3295        };
3296        let placeholder = size == 1
3297            && options.first() == Some(&selected)
3298            && self.doc.parent(selected) == Some(el)
3299            && self.option_value(selected).is_empty();
3300        !placeholder
3301    }
3302
3303    fn option_value(&self, el: NodeId) -> String {
3304        match self.attr(el, "value") {
3305            Some(v) => v.to_string(),
3306            None => self
3307                .doc
3308                .text(el)
3309                .split_ascii_whitespace()
3310                .collect::<Vec<_>>()
3311                .join(" "),
3312        }
3313    }
3314
3315    fn in_datalist(&self, el: NodeId) -> bool {
3316        let mut at = self.parent_element(el);
3317        while let Some(p) = at {
3318            if self.html_named(p, "datalist") {
3319                return true;
3320            }
3321            at = self.parent_element(p);
3322        }
3323        false
3324    }
3325
3326    fn attr(&self, el: NodeId, name: &str) -> Option<&str> {
3327        self.doc
3328            .attrs(el)
3329            .find(|(ns, n, _)| *ns == AttrNs::None && *n == name)
3330            .map(|(_, _, v)| v)
3331    }
3332
3333    fn attr_matches(&self, el: NodeId, ns: Ns, a: &AttrSelector) -> bool {
3334        let doc = self.doc;
3335        if ns == Ns::Xml {
3336            return self.xml_attr_matches(el, a);
3337        }
3338        let html = ns == Ns::Html;
3339        let insensitive = match a.case {
3340            Case::Insensitive => true,
3341            Case::Sensitive => false,
3342            Case::Default => html && case_insensitive_attr(&a.lower),
3343        };
3344        let want = if html { &a.lower } else { &a.exact };
3345        // The raw attributes, so a value is only looked at once the name
3346        // matches.
3347        doc.attrs_of(el).iter().any(|attr| {
3348            // A browser matches SVG's `viewBox` with its case.
3349            let name = doc.written_name(ns, attr);
3350            // A namespaced attribute is stored as written (`xlink:href`);
3351            // `[*|href]` names its local part.
3352            let name = match attr.ns {
3353                AttrNs::None => name,
3354                _ => name.split_once(':').map_or(name, |(_, local)| local),
3355            };
3356            let in_ns = match a.in_ns {
3357                Some(ns) => attr.ns == ns,
3358                None => attr.ns == AttrNs::None || a.any_ns,
3359            };
3360            in_ns
3361                && name == want.as_str()
3362                && (a.op == AttrOp::Exists
3363                    || value_matches(a.op, doc.str(attr.value), &a.value, insensitive))
3364        })
3365    }
3366
3367    /// An attribute selector in XML: the attribute is found by its local
3368    /// name in any case, one written exactly as asked winning over others
3369    /// (`id` over `ID`), and only that one is compared.
3370    fn xml_attr_matches(&self, el: NodeId, a: &AttrSelector) -> bool {
3371        let doc = self.doc;
3372        let range = doc
3373            .element(el)
3374            .map_or(0..0, |e| e.attrs.start as usize..e.attrs.end as usize);
3375        let attrs = &doc.attrs[range];
3376        let local = |attr: &crate::dom::Attr| xml_local(doc.str(attr.name));
3377        let found = attrs
3378            .iter()
3379            .find(|attr| local(attr) == a.exact)
3380            .or_else(|| {
3381                attrs
3382                    .iter()
3383                    .find(|attr| local(attr).eq_ignore_ascii_case(&a.lower))
3384            });
3385        let insensitive = a.case == Case::Insensitive;
3386        found.is_some_and(|attr| {
3387            a.op == AttrOp::Exists
3388                || value_matches(a.op, doc.str(attr.value), &a.value, insensitive)
3389        })
3390    }
3391
3392    fn pseudo(&self, p: &Pseudo, el: NodeId, anchor: NodeId) -> bool {
3393        let doc = self.doc;
3394        let e = doc.element(el).expect("an element");
3395        let html = e.ns == Ns::Html;
3396        let tag = if html { e.tag } else { Tag::Other };
3397        match p {
3398            Pseudo::Not(list) => !list.0.iter().any(|c| self.nested(c, el, anchor)),
3399            Pseudo::Is(list) | Pseudo::Where(list) => {
3400                list.0.iter().any(|c| self.nested(c, el, anchor))
3401            }
3402            Pseudo::Has(list) => list.0.iter().any(|c| self.has(c, el)),
3403            Pseudo::Nth {
3404                a,
3405                b,
3406                last,
3407                of_type,
3408                of,
3409            } => {
3410                let same = |other: NodeId| {
3411                    if *of_type {
3412                        same_type(doc, doc.element(other).unwrap(), e)
3413                    } else if let Some(of) = of {
3414                        of.0.iter().any(|c| self.complex(c, other, other))
3415                    } else {
3416                        true
3417                    }
3418                };
3419                if !same(el) {
3420                    return false;
3421                }
3422                // The walk below could go through every sibling, for every
3423                // sibling: take the positions worked out once per parent
3424                // instead, for S as well when there's `of S`.
3425                if let Some(of) = of
3426                    && let Some((index, count)) = self.of_place(of, el)
3427                {
3428                    let index = if *last { count - index + 1 } else { index };
3429                    return nth_matches(*a as i64, *b as i64, index as i64);
3430                }
3431                if *a > 0
3432                    && let Some(m) = self.nth_by_place(el, *a, *b, *last, *of_type)
3433                {
3434                    return m;
3435                }
3436                // With a <= 0 the walk stops at b, which is usually soon;
3437                // a walk that goes on, past other types or to a large b,
3438                // takes the positions too.
3439                let mut walked = 0;
3440                let mut index = 1i64;
3441                let mut at = if *last {
3442                    self.next_element(el)
3443                } else {
3444                    self.prev_element(el)
3445                };
3446                while let Some(s) = at {
3447                    walked += 1;
3448                    if walked > 32
3449                        && let Some(m) = self.nth_by_place(el, *a, *b, *last, *of_type)
3450                    {
3451                        return m;
3452                    }
3453                    if same(s) {
3454                        index += 1;
3455                        // With a <= 0 the positions that match end at b, so
3456                        // counting further can't help: `:last-child` looks
3457                        // at one sibling, not all of them.
3458                        if *a <= 0 && index > *b as i64 {
3459                            return false;
3460                        }
3461                    }
3462                    at = if *last {
3463                        self.next_element(s)
3464                    } else {
3465                        self.prev_element(s)
3466                    };
3467                }
3468                nth_matches(*a as i64, *b as i64, index)
3469            }
3470            Pseudo::Only { of_type } => {
3471                let same =
3472                    |other: NodeId| !*of_type || same_type(doc, doc.element(other).unwrap(), e);
3473                // Of-type, the walks can pass any number of other types:
3474                // one that goes on takes the counts worked out per parent.
3475                let mut walked = 0;
3476                for step in [Self::prev_element, Self::next_element] {
3477                    let mut at = step(self, el);
3478                    while let Some(s) = at {
3479                        walked += 1;
3480                        if walked > 32
3481                            && let Some(pl) = self.place(el)
3482                        {
3483                            return pl.type_count == 1;
3484                        }
3485                        if same(s) {
3486                            return false;
3487                        }
3488                        at = step(self, s);
3489                    }
3490                }
3491                true
3492            }
3493            Pseudo::Empty => doc.children(el).all(|c| {
3494                matches!(
3495                    doc.nodes[c as usize].data,
3496                    Data::Comment(_) | Data::ProcessingInstruction { .. }
3497                ) || matches!(doc.kind(c), crate::Kind::Text(t) if t.is_empty())
3498            }),
3499            Pseudo::Root => doc
3500                .parent(el)
3501                .is_some_and(|p| matches!(doc.nodes[p as usize].data, Data::Document)),
3502            Pseudo::Scope => match self.scope {
3503                Some(s) if doc.element(s).is_some() => el == s,
3504                _ => doc
3505                    .parent(el)
3506                    .is_some_and(|p| matches!(doc.nodes[p as usize].data, Data::Document)),
3507            },
3508            Pseudo::AnyLink => matches!(tag, Tag::A | Tag::Area) && self.attr(el, "href").is_some(),
3509            Pseudo::Target => self.page.as_ref().is_some_and(|p| p.target == Some(el)),
3510            Pseudo::TargetWithin => self.page.as_ref().and_then(|p| p.target).is_some_and(|t| {
3511                let mut at = Some(t);
3512                while let Some(n) = at {
3513                    if n == el {
3514                        return true;
3515                    }
3516                    at = self.doc.parent(n);
3517                }
3518                false
3519            }),
3520            Pseudo::LocalLink => {
3521                matches!(tag, Tag::A | Tag::Area)
3522                    && self.page.as_ref().is_some_and(|p| {
3523                        self.attr(el, "href")
3524                            .and_then(|href| p.base.join(href).ok())
3525                            .is_some_and(|mut link| {
3526                                link.set_fragment(None);
3527                                link == p.url
3528                            })
3529                    })
3530            }
3531            Pseudo::Checked => match tag {
3532                Tag::Input => {
3533                    self.attr(el, "checked").is_some()
3534                        && self.attr(el, "type").is_some_and(|t| {
3535                            t.eq_ignore_ascii_case("checkbox") || t.eq_ignore_ascii_case("radio")
3536                        })
3537                }
3538                Tag::Option => self.attr(el, "selected").is_some(),
3539                _ => false,
3540            },
3541            Pseudo::Default => match tag {
3542                Tag::Input if self.input_type(el, &["checkbox", "radio"]) => {
3543                    self.attr(el, "checked").is_some()
3544                }
3545                Tag::Option => self.attr(el, "selected").is_some(),
3546                Tag::Button | Tag::Input => self.default_button(el, tag),
3547                _ => false,
3548            },
3549            Pseudo::Indeterminate => match tag {
3550                Tag::Input if self.input_type(el, &["radio"]) => self.radio_group_unchecked(el),
3551                // A checkbox is only indeterminate when a script says so.
3552                _ => self.html_named(el, "progress") && self.attr(el, "value").is_none(),
3553            },
3554            Pseudo::InRange => tag == Tag::Input && self.in_range(el) == Some(true),
3555            Pseudo::OutOfRange => tag == Tag::Input && self.in_range(el) == Some(false),
3556            Pseudo::Valid => self.valid(el, tag) == Some(true),
3557            Pseudo::Invalid => self.valid(el, tag) == Some(false),
3558            Pseudo::Disabled => self.disabled(el, tag),
3559            Pseudo::Enabled => self.form_control(tag) && !self.disabled(el, tag),
3560            Pseudo::Required => {
3561                matches!(tag, Tag::Input | Tag::Select | Tag::Textarea)
3562                    && self.attr(el, "required").is_some()
3563            }
3564            Pseudo::Optional => {
3565                matches!(tag, Tag::Input | Tag::Select | Tag::Textarea)
3566                    && self.attr(el, "required").is_none()
3567            }
3568            Pseudo::ReadWrite => self.read_write(el, tag),
3569            Pseudo::ReadOnly => !self.read_write(el, tag),
3570            Pseudo::PlaceholderShown => match tag {
3571                Tag::Input => {
3572                    self.attr(el, "placeholder").is_some()
3573                        && self.attr(el, "value").is_none_or(str::is_empty)
3574                }
3575                Tag::Textarea => self.attr(el, "placeholder").is_some() && doc.text(el).is_empty(),
3576                _ => false,
3577            },
3578            // The current draft's meaning: :placeholder-shown without the
3579            // placeholder, on the fields placeholder applies to.
3580            Pseudo::Blank => match tag {
3581                Tag::Input => {
3582                    text_entry(input_type_state(self.attr(el, "type")))
3583                        && self.attr(el, "value").is_none_or(str::is_empty)
3584                }
3585                Tag::Textarea => doc.text(el).is_empty(),
3586                _ => false,
3587            },
3588            // The DOM gives an HTML element made with a custom element's
3589            // name, or with is=, the state "undefined" until a definition
3590            // upgrades it, and nothing here defines one.
3591            Pseudo::Defined => {
3592                !(html
3593                    && (self.attr(el, "is").is_some()
3594                        || doc.lower_name(el).is_some_and(custom_element_name)))
3595            }
3596            Pseudo::Lang(ranges) => self.lang(el).is_some_and(|tag| {
3597                let tag = tag.to_ascii_lowercase();
3598                ranges.iter().any(|range| lang_matches(range, &tag))
3599            }),
3600            Pseudo::Dir(rtl) => self.is_rtl(el) == *rtl,
3601            Pseudo::Heading(levels) => {
3602                let level = match tag {
3603                    Tag::H1 => 1,
3604                    Tag::H2 => 2,
3605                    Tag::H3 => 3,
3606                    Tag::H4 => 4,
3607                    Tag::H5 => 5,
3608                    Tag::H6 => 6,
3609                    _ => return false,
3610                };
3611                levels.is_empty() || levels.contains(&level)
3612            }
3613            Pseudo::Never | Pseudo::Element => false,
3614            Pseudo::Host(arg) => {
3615                el == self.host && arg.as_ref().is_none_or(|c| self.simples(&c.0, el, anchor))
3616            }
3617            Pseudo::HostContext(c) => {
3618                el == self.host && {
3619                    let mut at = Some(el);
3620                    while let Some(n) = at {
3621                        if doc.element(n).is_some() && self.simples(&c.0, n, anchor) {
3622                            return true;
3623                        }
3624                        at = doc.shadow_including_parent(n);
3625                    }
3626                    false
3627                }
3628            }
3629            // Matched in `slotted`, before the compound's other parts.
3630            Pseudo::Slotted(_) => false,
3631            // A cell's columns are a run of positions, so one sum says
3632            // whether any of them fits, however many it spans.
3633            Pseudo::NthCol { a, b, last } => self.cell_columns(el).is_some_and(|(t, x, n)| {
3634                let (lo, hi) = if *last {
3635                    (t.width - (x + n) + 1, t.width - x)
3636                } else {
3637                    (x + 1, x + n)
3638                };
3639                nth_in_range(*a as i64, *b as i64, lo as i64, hi as i64)
3640            }),
3641        }
3642    }
3643
3644    /// A selector in `:is()`, `:where()` or `:not()`. One of several
3645    /// compounds is remembered for each element: it can't depend on a
3646    /// `:has()` anchor, which only the relative selector's own last part
3647    /// reads.
3648    fn nested(&self, c: &Complex, el: NodeId, anchor: NodeId) -> bool {
3649        if c.parts.len() == 1 {
3650            return self.complex(c, el, anchor);
3651        }
3652        let key = (std::ptr::from_ref(c) as usize, el);
3653        if let Some(&known) = self.nested_seen.borrow().get(&key) {
3654            return known;
3655        }
3656        let found = self.complex(c, el, anchor);
3657        self.nested_seen.borrow_mut().insert(key, found);
3658        found
3659    }
3660
3661    /// `:has()`: some element related to `el` as the relative selector
3662    /// says matches it, with `el` as its anchor.
3663    fn has(&self, c: &Complex, el: NodeId) -> bool {
3664        let doc = self.doc;
3665        // The combinator next to the anchor decides where to look: below
3666        // it, or among its later siblings and below them.
3667        let first = c.parts[c.parts.len() - 2].1;
3668        // One compound, the usual shape: only the elements the combinator
3669        // reaches can match, and the compound doesn't depend on the
3670        // anchor, so what lies below or after an element is worth keeping.
3671        if let [(compound, _), _] = c.parts.as_slice()
3672            && first != Combinator::Column
3673        {
3674            let key = std::ptr::from_ref(c) as usize;
3675            return match first {
3676                Combinator::Child => doc
3677                    .children(el)
3678                    .any(|k| doc.element(k).is_some() && self.compound(compound, k, el)),
3679                Combinator::NextSibling => self
3680                    .next_element(el)
3681                    .is_some_and(|s| self.compound(compound, s, el)),
3682                Combinator::SubsequentSibling => self.later_holds(key, compound, el),
3683                _ => self.below_holds(key, compound, el),
3684            };
3685        }
3686        // More than one: an element whose parent (for a descendant
3687        // combinator) or previous sibling (for `~`) has no match has none
3688        // either, since everything it could find, that one could too.
3689        let key = std::ptr::from_ref(c) as usize;
3690        let before = match first {
3691            Combinator::Descendant => doc.parent(el),
3692            Combinator::SubsequentSibling => self.prev_element(el),
3693            _ => None,
3694        };
3695        let remember = matches!(
3696            first,
3697            Combinator::Descendant | Combinator::SubsequentSibling
3698        );
3699        if before.is_some_and(|b| self.has_seen.borrow().get(&(key, b)) == Some(&false)) {
3700            self.has_seen.borrow_mut().insert((key, el), false);
3701            return false;
3702        }
3703        let found = self.has_anywhere(c, el, first);
3704        if remember {
3705            self.has_seen.borrow_mut().insert((key, el), found);
3706        }
3707        found
3708    }
3709
3710    /// `:has()` of more than one compound, looking at every element the
3711    /// first combinator can reach.
3712    fn has_anywhere(&self, c: &Complex, el: NodeId, first: Combinator) -> bool {
3713        let doc = self.doc;
3714        let mut stack: Vec<NodeId> = Vec::new();
3715        match first {
3716            // One sibling and what's below it at a time, nearest first: a
3717            // match is usually close, and gathering every later sibling
3718            // first cost each element of a long list the whole list.
3719            Combinator::NextSibling | Combinator::SubsequentSibling => {
3720                let mut at = self.next_element(el);
3721                while let Some(s) = at {
3722                    stack.push(s);
3723                    if self.found_below(c, el, &mut stack) {
3724                        return true;
3725                    }
3726                    at = self.next_element(s);
3727                }
3728                return false;
3729            }
3730            // A col's cells are elsewhere in its table.
3731            Combinator::Column => {
3732                let table = doc.parent(el).and_then(|g| doc.parent(g));
3733                if self.html_tag_of(el) == Some(Tag::Col)
3734                    && let Some(t) = table.filter(|&t| self.html_tag_of(t) == Some(Tag::Table))
3735                {
3736                    push_children_reversed(doc, t, &mut stack);
3737                }
3738            }
3739            _ => push_children_reversed(doc, el, &mut stack),
3740        }
3741        self.found_below(c, el, &mut stack)
3742    }
3743
3744    /// Whether an element on `stack`, or below one, matches `c` with `el`
3745    /// as its anchor, walking them in document order.
3746    fn found_below(&self, c: &Complex, el: NodeId, stack: &mut Vec<NodeId>) -> bool {
3747        let doc = self.doc;
3748        while let Some(n) = stack.pop() {
3749            if doc.element(n).is_none() {
3750                continue;
3751            }
3752            if self.complex(c, n, el) {
3753                return true;
3754            }
3755            push_children_reversed(doc, n, stack);
3756        }
3757        false
3758    }
3759
3760    /// Whether an element below `el` matches `compound`. A subtree walked
3761    /// is remembered as holding a match or not, so in a deep chain each
3762    /// element is looked at once, not once per ancestor.
3763    fn below_holds(&self, key: usize, compound: &Compound, el: NodeId) -> bool {
3764        let doc = self.doc;
3765        if self.has_seen.borrow().get(&(key, el)) == Some(&false) {
3766            return false;
3767        }
3768        // A node comes off twice: on the way down, then marked done once
3769        // its subtree is through, with nothing in it matching.
3770        let mut stack: Vec<(NodeId, bool)> = Vec::new();
3771        let at = stack.len();
3772        stack.extend(doc.children(el).map(|k| (k, false)));
3773        stack[at..].reverse();
3774        while let Some((n, done)) = stack.pop() {
3775            if done {
3776                self.has_seen.borrow_mut().insert((key, n), false);
3777                continue;
3778            }
3779            if doc.element(n).is_none() {
3780                continue;
3781            }
3782            let known = self.has_seen.borrow().get(&(key, n)).copied();
3783            if known == Some(false) {
3784                continue;
3785            }
3786            if known == Some(true) || self.compound(compound, n, el) {
3787                // n holds a match, and so does everything up to `el`.
3788                let mut seen = self.has_seen.borrow_mut();
3789                let mut up = Some(n);
3790                while let Some(u) = up {
3791                    seen.insert((key, u), true);
3792                    up = doc.parent(u).filter(|_| u != el);
3793                }
3794                return true;
3795            }
3796            stack.push((n, true));
3797            let at = stack.len();
3798            stack.extend(doc.children(n).map(|k| (k, false)));
3799            stack[at..].reverse();
3800        }
3801        false
3802    }
3803
3804    /// Whether an element after `el` among its siblings matches
3805    /// `compound`, remembered for each sibling walked past.
3806    fn later_holds(&self, key: usize, compound: &Compound, el: NodeId) -> bool {
3807        let mut walked = Vec::new();
3808        let mut at = self.next_element(el);
3809        let found = loop {
3810            let Some(s) = at else { break false };
3811            if let Some(&known) = self.has_seen.borrow().get(&(key, s)) {
3812                break known;
3813            }
3814            walked.push(s);
3815            if self.compound(compound, s, el) {
3816                break true;
3817            }
3818            at = self.next_element(s);
3819        };
3820        let mut seen = self.has_seen.borrow_mut();
3821        for s in walked {
3822            seen.insert((key, s), found);
3823        }
3824        found
3825    }
3826
3827    fn form_control(&self, tag: Tag) -> bool {
3828        matches!(
3829            tag,
3830            Tag::Button
3831                | Tag::Input
3832                | Tag::Select
3833                | Tag::Textarea
3834                | Tag::Optgroup
3835                | Tag::Option
3836                | Tag::Fieldset
3837        )
3838    }
3839
3840    /// The HTML Standard's "actually disabled".
3841    fn disabled(&self, el: NodeId, tag: Tag) -> bool {
3842        let doc = self.doc;
3843        match tag {
3844            Tag::Optgroup => self.attr(el, "disabled").is_some(),
3845            Tag::Option => {
3846                self.attr(el, "disabled").is_some()
3847                    || self.parent_element(el).is_some_and(|p| {
3848                        doc.element(p)
3849                            .is_some_and(|e| e.ns == Ns::Html && e.tag == Tag::Optgroup)
3850                            && self.attr(p, "disabled").is_some()
3851                    })
3852            }
3853            Tag::Button | Tag::Input | Tag::Select | Tag::Textarea | Tag::Fieldset => {
3854                if self.attr(el, "disabled").is_some() {
3855                    return true;
3856                }
3857                // A descendant of a disabled fieldset, outside its first
3858                // legend.
3859                let mut child = el;
3860                let mut at = self.parent_element(el);
3861                while let Some(p) = at {
3862                    let pe = doc.element(p).unwrap();
3863                    if pe.ns == Ns::Html
3864                        && pe.tag == Tag::Fieldset
3865                        && self.attr(p, "disabled").is_some()
3866                    {
3867                        let first_legend = doc.children(p).find(|&c| {
3868                            doc.element(c).is_some_and(|e| {
3869                                e.ns == Ns::Html && doc.element_name(e) == "legend"
3870                            })
3871                        });
3872                        if first_legend != Some(child) {
3873                            return true;
3874                        }
3875                    }
3876                    child = p;
3877                    at = self.parent_element(p);
3878                }
3879                false
3880            }
3881            _ => false,
3882        }
3883    }
3884
3885    fn read_write(&self, el: NodeId, tag: Tag) -> bool {
3886        match tag {
3887            Tag::Input => {
3888                let typ = self.attr(el, "type").unwrap_or("text").to_ascii_lowercase();
3889                let mutable = matches!(
3890                    typ.as_str(),
3891                    "text"
3892                        | "search"
3893                        | "url"
3894                        | "tel"
3895                        | "email"
3896                        | "password"
3897                        | "date"
3898                        | "month"
3899                        | "week"
3900                        | "time"
3901                        | "datetime-local"
3902                        | "number"
3903                        | ""
3904                );
3905                mutable && self.attr(el, "readonly").is_none() && !self.disabled(el, tag)
3906            }
3907            Tag::Textarea => self.attr(el, "readonly").is_none() && !self.disabled(el, tag),
3908            _ => self.editable(el),
3909        }
3910    }
3911
3912    /// Inside an element whose contenteditable says it's editable.
3913    fn editable(&self, el: NodeId) -> bool {
3914        let mut at = Some(el);
3915        while let Some(n) = at {
3916            if let Some(v) = self.attr(n, "contenteditable") {
3917                return !v.eq_ignore_ascii_case("false");
3918            }
3919            at = self.parent_element(n);
3920        }
3921        false
3922    }
3923}
3924
3925/// Same namespace and name: by tag number when the parser knows the tag.
3926fn same_type(doc: &Document, a: &crate::dom::Element, b: &crate::dom::Element) -> bool {
3927    a.ns == b.ns
3928        && if a.tag != Tag::Other || b.tag != Tag::Other {
3929            a.tag == b.tag && (a.ns == Ns::Html || doc.element_name(a) == doc.element_name(b))
3930        } else {
3931            doc.element_name(a) == doc.element_name(b)
3932        }
3933}
3934
3935/// An XML name without its prefix.
3936fn xml_local(name: &str) -> &str {
3937    name.split_once(':').map_or(name, |(_, local)| local)
3938}
3939
3940fn nth_matches(a: i64, b: i64, index: i64) -> bool {
3941    if a == 0 {
3942        return index == b;
3943    }
3944    let diff = index - b;
3945    diff % a == 0 && diff / a >= 0
3946}
3947
3948/// Whether some position from `lo` to `hi` is `a`n+`b` for an n >= 0.
3949fn nth_in_range(a: i64, b: i64, lo: i64, hi: i64) -> bool {
3950    match a.cmp(&0) {
3951        std::cmp::Ordering::Equal => (lo..=hi).contains(&b),
3952        // The first matching position at or after lo, if it's by hi.
3953        std::cmp::Ordering::Greater => {
3954            let from = lo.max(b);
3955            from + (b - from).rem_euclid(a) <= hi
3956        }
3957        // The last matching position at or before hi, if it's from lo.
3958        std::cmp::Ordering::Less => {
3959            let to = hi.min(b);
3960            to - (to - b).rem_euclid(-a) >= lo
3961        }
3962    }
3963}
3964
3965fn value_matches(op: AttrOp, value: &str, want: &str, insensitive: bool) -> bool {
3966    let eq = |x: &str, y: &str| {
3967        if insensitive {
3968            x.eq_ignore_ascii_case(y)
3969        } else {
3970            x == y
3971        }
3972    };
3973    match op {
3974        AttrOp::Exists => true,
3975        AttrOp::Equals => eq(value, want),
3976        AttrOp::Includes => {
3977            !want.is_empty()
3978                && !want.contains(is_space_char)
3979                && value.split(is_space_char).any(|w| eq(w, want))
3980        }
3981        AttrOp::DashMatch => {
3982            eq(value, want)
3983                || (value.len() > want.len()
3984                    && value.as_bytes()[want.len()] == b'-'
3985                    && value.is_char_boundary(want.len())
3986                    && eq(&value[..want.len()], want))
3987        }
3988        AttrOp::Prefix => {
3989            !want.is_empty()
3990                && value.len() >= want.len()
3991                && value.is_char_boundary(want.len())
3992                && eq(&value[..want.len()], want)
3993        }
3994        AttrOp::Suffix => {
3995            !want.is_empty()
3996                && value.len() >= want.len()
3997                && value.is_char_boundary(value.len() - want.len())
3998                && eq(&value[value.len() - want.len()..], want)
3999        }
4000        AttrOp::Substring => {
4001            !want.is_empty()
4002                && if insensitive {
4003                    value
4004                        .to_ascii_lowercase()
4005                        .contains(&want.to_ascii_lowercase())
4006                } else {
4007                    value.contains(want)
4008                }
4009        }
4010    }
4011}
4012
4013#[cfg(test)]
4014mod nth_range_tests {
4015    #[test]
4016    fn nth_in_range_agrees_with_each_position() {
4017        for a in -4..=4 {
4018            for b in -6..=8 {
4019                for lo in 1..=7 {
4020                    for hi in lo..=9 {
4021                        let each = (lo..=hi).any(|i| super::nth_matches(a, b, i));
4022                        assert_eq!(
4023                            super::nth_in_range(a, b, lo, hi),
4024                            each,
4025                            "{a}n+{b} in {lo}..={hi}"
4026                        );
4027                    }
4028                }
4029            }
4030        }
4031    }
4032}