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.deadline = deadline(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.deadline = deadline(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}
1829
1830/// A query that ran past [`MatchOptions::budget`].
1831#[derive(Debug, Clone, Copy, PartialEq, Eq)]
1832pub struct MatchTimeout {
1833    pub budget: Duration,
1834}
1835
1836impl std::fmt::Display for MatchTimeout {
1837    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
1838        write!(f, "matching took longer than {:?}", self.budget)
1839    }
1840}
1841
1842impl std::error::Error for MatchTimeout {}
1843
1844/// When a query with `options` gives up: never for a budget past what
1845/// the clock can count.
1846fn deadline(options: &MatchOptions<'_>) -> Option<Instant> {
1847    options.budget.and_then(|b| Instant::now().checked_add(b))
1848}
1849
1850fn timeout(cx: &Cx<'_>, options: &MatchOptions<'_>) -> Result<(), MatchTimeout> {
1851    if cx.timed_out.get() {
1852        return Err(MatchTimeout {
1853            budget: options.budget.unwrap_or_default(),
1854        });
1855    }
1856    Ok(())
1857}
1858
1859/// The document's URL worked out once per query.
1860struct Page {
1861    /// Without its fragment.
1862    url: url::Url,
1863    /// What links resolve against: a `<base href>`, else the URL.
1864    base: url::Url,
1865    /// The element the fragment indicates.
1866    target: Option<NodeId>,
1867}
1868
1869impl Page {
1870    // Parsec's own WHATWG URL parser (#26) takes the url crate's place when it lands.
1871    fn new(doc: &Document, url: Option<&str>) -> Option<Page> {
1872        let mut url = url::Url::parse(url?).ok()?;
1873        let fragment = url.fragment().map(str::to_string);
1874        url.set_fragment(None);
1875        let elements = tree_elements(doc);
1876        let base = elements
1877            .iter()
1878            .find(|&&n| html_element_named(doc, n, "base") && attr_of(doc, n, "href").is_some())
1879            .and_then(|&n| url.join(attr_of(doc, n, "href")?).ok())
1880            .unwrap_or_else(|| url.clone());
1881        let target = fragment.and_then(|f| indicated(doc, &elements, &f));
1882        Some(Page { url, base, target })
1883    }
1884}
1885
1886/// The document's elements in tree order.
1887fn tree_elements(doc: &Document) -> Vec<NodeId> {
1888    let (mut out, mut stack) = (Vec::new(), vec![doc.root()]);
1889    while let Some(n) = stack.pop() {
1890        if doc.element(n).is_some() {
1891            out.push(n);
1892        }
1893        push_children_reversed(doc, n, &mut stack);
1894    }
1895    out
1896}
1897
1898fn html_element_named(doc: &Document, n: NodeId, name: &str) -> bool {
1899    doc.element(n).is_some_and(|e| e.ns == Ns::Html) && doc.lower_name(n) == Some(name)
1900}
1901
1902fn attr_of<'a>(doc: &'a Document, n: NodeId, name: &str) -> Option<&'a str> {
1903    doc.attrs(n)
1904        .find(|(ns, a, _)| *ns == AttrNs::None && *a == name)
1905        .map(|(_, _, v)| v)
1906}
1907
1908/// The HTML Standard's indicated part: the first element whose `id` is
1909/// the fragment, else the first `<a>` with that `name`; tried as given,
1910/// then percent-decoded. An empty fragment, or `top` with no element of
1911/// that name, indicates the top of the document, which is no element.
1912fn indicated(doc: &Document, elements: &[NodeId], fragment: &str) -> Option<NodeId> {
1913    if fragment.is_empty() {
1914        return None;
1915    }
1916    let find = |f: &str| {
1917        elements
1918            .iter()
1919            .copied()
1920            .find(|&n| attr_of(doc, n, "id") == Some(f))
1921            .or_else(|| {
1922                elements.iter().copied().find(|&n| {
1923                    html_element_named(doc, n, "a") && attr_of(doc, n, "name") == Some(f)
1924                })
1925            })
1926    };
1927    find(fragment).or_else(|| find(&percent_decode(fragment)))
1928}
1929
1930/// %XX escapes as bytes, read as UTF-8 with any bad sequence replaced.
1931fn percent_decode(s: &str) -> String {
1932    let b = s.as_bytes();
1933    let mut out = Vec::with_capacity(b.len());
1934    let mut i = 0;
1935    while i < b.len() {
1936        let hex = |c: u8| (c as char).to_digit(16);
1937        match (
1938            b[i],
1939            b.get(i + 1).and_then(|&c| hex(c)),
1940            b.get(i + 2).and_then(|&c| hex(c)),
1941        ) {
1942            (b'%', Some(h), Some(l)) => {
1943                out.push((h * 16 + l) as u8);
1944                i += 3;
1945            }
1946            (c, _, _) => {
1947                out.push(c);
1948                i += 1;
1949            }
1950        }
1951    }
1952    String::from_utf8_lossy(&out).into_owned()
1953}
1954
1955struct Cx<'a> {
1956    doc: &'a Document,
1957    scope: Option<NodeId>,
1958    /// The shadow root whose tree the selector is matched in, and its
1959    /// host; [`NONE`] for both in any other tree. There the host stands
1960    /// in for the root, as the parent of its top-level nodes, and only
1961    /// `:host` and `:host-context()` match it.
1962    shadow: NodeId,
1963    host: NodeId,
1964    page: Option<Page>,
1965    /// Steps left for `pattern` matches in this query, shared by all of them.
1966    pattern_budget: Cell<u32>,
1967    /// When to give up, for the `try_` queries.
1968    deadline: Option<Instant>,
1969    /// Compounds matched, to read the clock every so often.
1970    steps: Cell<u32>,
1971    timed_out: Cell<bool>,
1972    /// Each element's place among its siblings, worked out for a whole
1973    /// parent the first time `:nth-*` needs one, so a query over a parent
1974    /// with n children counts them once rather than n times.
1975    places: RefCell<IdMap<NodeId, Place>>,
1976    /// The same for `:nth-child(An+B of S)`, keyed by S as well: each
1977    /// element matching S, its place among the siblings that do, and how
1978    /// many do.
1979    of_places: RefCell<IdMap<(usize, NodeId), (u32, u32)>>,
1980    /// For a `:has()` argument of one compound, keyed by it and an
1981    /// element: whether the element's subtree (`:has(x)`), or the element
1982    /// and its later siblings (`:has(~ x)`), hold a match. Every anchor
1983    /// asks the same question of the elements below or after it, so a
1984    /// query asks it of each element once.
1985    has_seen: RefCell<IdMap<(usize, NodeId), bool>>,
1986    /// Each table's columns, worked out the first time `||` or
1987    /// `:nth-col()` needs them, so a big table isn't laid out per cell.
1988    tables: RefCell<IdMap<NodeId, Rc<Columns>>>,
1989}
1990
1991/// A map keyed by node ids and selectors' addresses, numbers the parser
1992/// and the query hand out rather than the page, hashed with a multiply:
1993/// SipHash's guard against chosen keys guards nothing here, and made
1994/// `div:has(img)` half as slow again.
1995type IdMap<K, V> = HashMap<K, V, std::hash::BuildHasherDefault<IdHasher>>;
1996
1997#[derive(Default)]
1998struct IdHasher(u64);
1999
2000impl std::hash::Hasher for IdHasher {
2001    fn write(&mut self, bytes: &[u8]) {
2002        for &b in bytes {
2003            self.write_u64(b as u64);
2004        }
2005    }
2006
2007    fn write_u32(&mut self, n: u32) {
2008        self.write_u64(n as u64);
2009    }
2010
2011    fn write_usize(&mut self, n: usize) {
2012        self.write_u64(n as u64);
2013    }
2014
2015    fn write_u64(&mut self, n: u64) {
2016        self.0 = (self.0.rotate_left(5) ^ n).wrapping_mul(0x51_7c_c1_b7_27_22_0a_95);
2017    }
2018
2019    fn finish(&self) -> u64 {
2020        self.0
2021    }
2022}
2023
2024/// How far a failed part of a complex selector says to back up.
2025#[derive(Clone, Copy, PartialEq, Eq)]
2026enum Fail {
2027    /// The element didn't match: the part to the left may try another.
2028    Sibling,
2029    /// A sibling combinator ran out of siblings: back up to the nearest
2030    /// descendant combinator, which may try a higher ancestor.
2031    Descendant,
2032    /// A combinator ran out of ancestors: no higher one can help.
2033    Global,
2034}
2035
2036impl Fail {
2037    /// What running out of elements to try means for a combinator.
2038    fn exhausted(combinator: Combinator) -> Fail {
2039        match combinator {
2040            Combinator::NextSibling | Combinator::SubsequentSibling => Fail::Descendant,
2041            // Another cell may sit under other cols: the part to the right
2042            // may try one.
2043            Combinator::Column => Fail::Sibling,
2044            _ => Fail::Global,
2045        }
2046    }
2047}
2048
2049/// A table's columns by the HTML table model: the first column and how
2050/// many each cell and each `col` covers, and how many there are in all.
2051#[derive(Default)]
2052struct Columns {
2053    cells: HashMap<NodeId, (u32, u32)>,
2054    /// In column order, side by side.
2055    cols: Vec<(NodeId, u32, u32)>,
2056    /// Where each col is in `cols`, so `||` steps to the next in O(1).
2057    col_index: HashMap<NodeId, usize>,
2058    width: u32,
2059}
2060
2061/// The columns cells from earlier rows of a row group still cover, kept
2062/// as runs rather than slots, so time and memory follow the cells and not
2063/// the table's width, and a row with nothing reaching into it costs
2064/// nothing.
2065#[derive(Default)]
2066struct Cover {
2067    /// The row being laid out, counted from the group's first.
2068    row: u32,
2069    /// Disjoint runs: first column -> (column after the last, first row
2070    /// no longer covered), u32::MAX for rowspan=0.
2071    runs: BTreeMap<u32, (u32, u32)>,
2072    /// The runs' union as maximal contiguous blocks, first column ->
2073    /// column after the last, so finding a free column is one lookup
2074    /// however many runs sit side by side.
2075    blocks: BTreeMap<u32, u32>,
2076    /// Each run's last row, soonest first; an entry whose run has since
2077    /// been split or replaced is skipped.
2078    ends: BinaryHeap<Reverse<(u32, u32)>>,
2079}
2080
2081impl Cover {
2082    /// Drops the runs that stop before `row`.
2083    fn advance(&mut self, row: u32) {
2084        while let Some(&Reverse((until, start))) = self.ends.peek() {
2085            if until > row {
2086                break;
2087            }
2088            self.ends.pop();
2089            if let Some(&(end, u)) = self.runs.get(&start)
2090                && u == until
2091            {
2092                self.runs.remove(&start);
2093                let (&bs, &be) = self
2094                    .blocks
2095                    .range(..=start)
2096                    .next_back()
2097                    .expect("a run's block");
2098                self.blocks.remove(&bs);
2099                if bs < start {
2100                    self.blocks.insert(bs, start);
2101                }
2102                if end < be {
2103                    self.blocks.insert(end, be);
2104                }
2105            }
2106        }
2107    }
2108
2109    /// The first column from `x` that nothing covers.
2110    fn free(&self, x: u32) -> u32 {
2111        match self.blocks.range(..=x).next_back() {
2112            Some((_, &end)) if end > x => end,
2113            _ => x,
2114        }
2115    }
2116
2117    /// Covers `[start, end)` until row `until`. Where a run already covers
2118    /// part of it, a table model error, that part keeps the later row.
2119    fn add(&mut self, start: u32, end: u32, until: u32) {
2120        let mut over: Vec<(u32, u32, u32)> = Vec::new();
2121        if let Some((&rs, &(re, ru))) = self.runs.range(..start).next_back()
2122            && re > start
2123        {
2124            over.push((rs, re, ru));
2125        }
2126        over.extend(
2127            self.runs
2128                .range(start..end)
2129                .map(|(&rs, &(re, ru))| (rs, re, ru)),
2130        );
2131        let mut pieces = Vec::new();
2132        let mut at = start;
2133        for &(rs, re, ru) in &over {
2134            self.runs.remove(&rs);
2135            if rs < start {
2136                pieces.push((rs, start, ru));
2137            }
2138            let (os, oe) = (rs.max(start), re.min(end));
2139            if at < os {
2140                pieces.push((at, os, until));
2141            }
2142            pieces.push((os, oe, ru.max(until)));
2143            if re > end {
2144                pieces.push((end, re, ru));
2145            }
2146            at = oe;
2147        }
2148        if at < end {
2149            pieces.push((at, end, until));
2150        }
2151        for (ps, pe, pu) in pieces {
2152            self.runs.insert(ps, (pe, pu));
2153            self.ends.push(Reverse((pu, ps)));
2154        }
2155        // The union grows by [start, end): merge it with the blocks it
2156        // touches.
2157        let (mut bs, mut be) = (start, end);
2158        if let Some((&s, &e)) = self.blocks.range(..=start).next_back()
2159            && e >= start
2160        {
2161            bs = s;
2162            be = be.max(e);
2163            self.blocks.remove(&s);
2164        }
2165        while let Some((&s, &e)) = self.blocks.range(bs..=be).next() {
2166            self.blocks.remove(&s);
2167            be = be.max(e);
2168        }
2169        self.blocks.insert(bs, be);
2170    }
2171}
2172
2173/// An element's position among its parent's element children, counting
2174/// from 1, and among those of its own type.
2175#[derive(Clone, Copy)]
2176struct Place {
2177    index: u32,
2178    count: u32,
2179    type_index: u32,
2180    type_count: u32,
2181}
2182
2183/// HTML attributes whose values selectors compare without case, unless the
2184/// selector says `s` (the HTML Standard, "case-sensitivity of selectors").
2185fn case_insensitive_attr(name: &str) -> bool {
2186    matches!(
2187        name,
2188        "accept"
2189            | "accept-charset"
2190            | "align"
2191            | "alink"
2192            | "axis"
2193            | "bgcolor"
2194            | "charset"
2195            | "checked"
2196            | "clear"
2197            | "codetype"
2198            | "color"
2199            | "compact"
2200            | "declare"
2201            | "defer"
2202            | "dir"
2203            | "direction"
2204            | "disabled"
2205            | "enctype"
2206            | "face"
2207            | "frame"
2208            | "hreflang"
2209            | "http-equiv"
2210            | "lang"
2211            | "language"
2212            | "link"
2213            | "media"
2214            | "method"
2215            | "multiple"
2216            | "nohref"
2217            | "noresize"
2218            | "noshade"
2219            | "nowrap"
2220            | "readonly"
2221            | "rel"
2222            | "rev"
2223            | "rules"
2224            | "scope"
2225            | "scrolling"
2226            | "selected"
2227            | "shape"
2228            | "target"
2229            | "text"
2230            | "type"
2231            | "valign"
2232            | "valuetype"
2233            | "vlink"
2234    )
2235}
2236
2237fn is_space_char(c: char) -> bool {
2238    matches!(c, ' ' | '\t' | '\n' | '\r' | '\x0C')
2239}
2240
2241impl<'a> Cx<'a> {
2242    /// A context for matching in `in_tree`'s tree.
2243    fn new(doc: &'a Document, scope: Option<NodeId>, in_tree: NodeId, page: Option<Page>) -> Self {
2244        // Free when the document has no shadow roots.
2245        let (shadow, host) = match doc.shadow_roots.is_empty() {
2246            true => (NONE, NONE),
2247            false => {
2248                let root = doc.tree_root(in_tree);
2249                doc.shadow_host(root).map_or((NONE, NONE), |h| (root, h))
2250            }
2251        };
2252        Cx {
2253            doc,
2254            scope,
2255            shadow,
2256            host,
2257            page,
2258            pattern_budget: Cell::new(crate::pattern::SELECT_STEP_LIMIT),
2259            deadline: None,
2260            steps: Cell::new(0),
2261            timed_out: Cell::new(false),
2262            places: RefCell::default(),
2263            of_places: RefCell::default(),
2264            has_seen: RefCell::default(),
2265            tables: RefCell::default(),
2266        }
2267    }
2268
2269    fn html_tag_of(&self, n: NodeId) -> Option<Tag> {
2270        self.doc
2271            .element(n)
2272            .filter(|e| e.ns == Ns::Html)
2273            .map(|e| e.tag)
2274    }
2275
2276    /// The table a cell belongs to: its row's, the row in the table or in
2277    /// one of its row groups.
2278    fn table_of_cell(&self, cell: NodeId) -> Option<NodeId> {
2279        if !matches!(self.html_tag_of(cell), Some(Tag::Td | Tag::Th)) {
2280            return None;
2281        }
2282        let tr = self
2283            .doc
2284            .parent(cell)
2285            .filter(|&p| self.html_tag_of(p) == Some(Tag::Tr))?;
2286        let p = self.doc.parent(tr)?;
2287        match self.html_tag_of(p)? {
2288            Tag::Table => Some(p),
2289            Tag::Thead | Tag::Tbody | Tag::Tfoot => self
2290                .doc
2291                .parent(p)
2292                .filter(|&t| self.html_tag_of(t) == Some(Tag::Table)),
2293            _ => None,
2294        }
2295    }
2296
2297    /// A cell's table's columns, and the cell's first column and span.
2298    fn cell_columns(&self, cell: NodeId) -> Option<(Rc<Columns>, u32, u32)> {
2299        let table = self.table_of_cell(cell)?;
2300        let columns = self.columns(table);
2301        let &(x, n) = columns.cells.get(&cell)?;
2302        Some((columns, x, n))
2303    }
2304
2305    fn columns(&self, table: NodeId) -> Rc<Columns> {
2306        if let Some(c) = self.tables.borrow().get(&table) {
2307            return c.clone();
2308        }
2309        let c = Rc::new(self.lay_out(table));
2310        self.tables.borrow_mut().insert(table, c.clone());
2311        c
2312    }
2313
2314    /// A `span`, `colspan` or `rowspan` as the HTML Standard reads it:
2315    /// missing, unparsable or zero gives 1, and it stops at `max`.
2316    fn span(&self, el: NodeId, name: &str, max: u32) -> u32 {
2317        self.attr(el, name)
2318            .and_then(parse_non_negative)
2319            .filter(|&n| n > 0)
2320            .map_or(1, |n| n.min(max))
2321    }
2322
2323    /// The HTML Standard's "forming a table", as far as columns go:
2324    /// `colgroup`s before the first row give the `col`s their columns,
2325    /// and each cell takes the first column its row leaves free, rows
2326    /// above reaching down with `rowspan` included.
2327    fn lay_out(&self, table: NodeId) -> Columns {
2328        let doc = self.doc;
2329        let mut out = Columns::default();
2330        let mut col_x = 0;
2331        let mut rows_started = false;
2332        let mut cover = Cover::default();
2333        for child in doc.children(table) {
2334            match self.html_tag_of(child) {
2335                Some(Tag::Colgroup) if !rows_started => {
2336                    let mut has_cols = false;
2337                    for c in doc.children(child) {
2338                        if self.html_tag_of(c) == Some(Tag::Col) {
2339                            has_cols = true;
2340                            let n = self.span(c, "span", 1000);
2341                            out.col_index.insert(c, out.cols.len());
2342                            out.cols.push((c, col_x, n));
2343                            col_x += n;
2344                        }
2345                    }
2346                    if !has_cols {
2347                        col_x += self.span(child, "span", 1000);
2348                    }
2349                }
2350                Some(Tag::Tr) => {
2351                    rows_started = true;
2352                    self.lay_out_row(child, &mut cover, &mut out);
2353                }
2354                Some(Tag::Thead | Tag::Tbody | Tag::Tfoot) => {
2355                    rows_started = true;
2356                    // Cells don't reach from one row group into another.
2357                    cover = Cover::default();
2358                    for r in doc.children(child) {
2359                        if self.html_tag_of(r) == Some(Tag::Tr) {
2360                            self.lay_out_row(r, &mut cover, &mut out);
2361                        }
2362                    }
2363                    cover = Cover::default();
2364                }
2365                _ => {}
2366            }
2367        }
2368        out.width = out.width.max(col_x);
2369        out
2370    }
2371
2372    fn lay_out_row(&self, tr: NodeId, cover: &mut Cover, out: &mut Columns) {
2373        let row = cover.row;
2374        cover.advance(row);
2375        let mut x = 0;
2376        for cell in self.doc.children(tr) {
2377            if !matches!(self.html_tag_of(cell), Some(Tag::Td | Tag::Th)) {
2378                continue;
2379            }
2380            x = cover.free(x);
2381            let span = self.span(cell, "colspan", 1000);
2382            let until = match self.attr(cell, "rowspan").and_then(parse_non_negative) {
2383                Some(0) => u32::MAX,
2384                n => row.saturating_add(n.map_or(1, |n| n.min(65534))),
2385            };
2386            cover.add(x, x + span, until);
2387            out.cells.insert(cell, (x, span));
2388            x += span;
2389            out.width = out.width.max(x);
2390        }
2391        cover.row += 1;
2392    }
2393
2394    /// `el`'s place among its siblings, or None if it has no parent.
2395    fn place(&self, el: NodeId) -> Option<Place> {
2396        if let Some(&p) = self.places.borrow().get(&el) {
2397            return Some(p);
2398        }
2399        let doc = self.doc;
2400        let parent = doc.parent(el)?;
2401        let kids: Vec<NodeId> = doc
2402            .children(parent)
2403            .filter(|&k| doc.element(k).is_some())
2404            .collect();
2405        // One entry per element type among the children: an example of it,
2406        // and how many there are so far. A few types are found by a scan;
2407        // past that by a key that's equal when same_type says so, as a
2408        // scan made a parent of n different types cost n²: a known HTML
2409        // tag by its number, any other by its name, which is the page's,
2410        // so hashed as std does.
2411        let mut types: Vec<(NodeId, u32)> = Vec::new();
2412        let mut keyed = false;
2413        let mut by_tag: IdMap<Tag, usize> = IdMap::default();
2414        let mut by_name: HashMap<(u8, Tag, &str), usize> = HashMap::new();
2415        fn file<'d>(
2416            doc: &'d Document,
2417            by_tag: &mut IdMap<Tag, usize>,
2418            by_name: &mut HashMap<(u8, Tag, &'d str), usize>,
2419            e: &'d crate::dom::Element,
2420            t: usize,
2421        ) {
2422            if e.ns == Ns::Html && e.tag != Tag::Other {
2423                by_tag.insert(e.tag, t);
2424            } else {
2425                by_name.insert((e.ns as u8, e.tag, doc.element_name(e)), t);
2426            }
2427        }
2428        let mut of_type = Vec::with_capacity(kids.len());
2429        for &k in &kids {
2430            let e = doc.element(k).unwrap();
2431            let found = if !keyed {
2432                types
2433                    .iter()
2434                    .position(|&(rep, _)| same_type(doc, doc.element(rep).unwrap(), e))
2435            } else if e.ns == Ns::Html && e.tag != Tag::Other {
2436                by_tag.get(&e.tag).copied()
2437            } else {
2438                by_name
2439                    .get(&(e.ns as u8, e.tag, doc.element_name(e)))
2440                    .copied()
2441            };
2442            let t = match found {
2443                Some(t) => t,
2444                None => {
2445                    types.push((k, 0));
2446                    if keyed {
2447                        file(doc, &mut by_tag, &mut by_name, e, types.len() - 1);
2448                    } else if types.len() > 16 {
2449                        keyed = true;
2450                        for (i, &(rep, _)) in types.iter().enumerate() {
2451                            let rep = doc.element(rep).unwrap();
2452                            file(doc, &mut by_tag, &mut by_name, rep, i);
2453                        }
2454                    }
2455                    types.len() - 1
2456                }
2457            };
2458            types[t].1 += 1;
2459            of_type.push((t, types[t].1));
2460        }
2461        let mut places = self.places.borrow_mut();
2462        places.reserve(kids.len());
2463        for (i, (&k, &(t, type_index))) in kids.iter().zip(&of_type).enumerate() {
2464            places.insert(
2465                k,
2466                Place {
2467                    index: i as u32 + 1,
2468                    count: kids.len() as u32,
2469                    type_index,
2470                    type_count: types[t].1,
2471                },
2472            );
2473        }
2474        places.get(&el).copied()
2475    }
2476
2477    /// `el`'s place among its siblings that match `of`, and how many do,
2478    /// worked out for the whole parent at once; None if it has no parent
2479    /// or doesn't match.
2480    fn of_place(&self, of: &SelectorList, el: NodeId) -> Option<(u32, u32)> {
2481        let key = std::ptr::from_ref(of) as usize;
2482        if let Some(&p) = self.of_places.borrow().get(&(key, el)) {
2483            return Some(p);
2484        }
2485        let doc = self.doc;
2486        let parent = doc.parent(el)?;
2487        let kids: Vec<NodeId> = doc
2488            .children(parent)
2489            .filter(|&k| doc.element(k).is_some() && of.0.iter().any(|c| self.complex(c, k, k)))
2490            .collect();
2491        let mut places = self.of_places.borrow_mut();
2492        for (i, &k) in kids.iter().enumerate() {
2493            places.insert((key, k), (i as u32 + 1, kids.len() as u32));
2494        }
2495        places.get(&(key, el)).copied()
2496    }
2497
2498    /// Whether `el` is at an+b among its siblings (of its type), by the
2499    /// places worked out for its parent; None if it has no parent.
2500    #[inline(never)]
2501    fn nth_by_place(&self, el: NodeId, a: i32, b: i32, last: bool, of_type: bool) -> Option<bool> {
2502        let pl = self.place(el)?;
2503        let (index, count) = if of_type {
2504            (pl.type_index, pl.type_count)
2505        } else {
2506            (pl.index, pl.count)
2507        };
2508        let index = if last { count - index + 1 } else { index };
2509        Some(nth_matches(a as i64, b as i64, index as i64))
2510    }
2511
2512    fn parent_element(&self, n: NodeId) -> Option<NodeId> {
2513        self.doc
2514            .parent(n)
2515            .filter(|&p| self.doc.element(p).is_some())
2516    }
2517
2518    fn prev_element(&self, n: NodeId) -> Option<NodeId> {
2519        let mut at = self.doc.prev_sibling(n);
2520        while let Some(p) = at {
2521            if self.doc.element(p).is_some() {
2522                return Some(p);
2523            }
2524            at = self.doc.prev_sibling(p);
2525        }
2526        None
2527    }
2528
2529    fn next_element(&self, n: NodeId) -> Option<NodeId> {
2530        let mut at = self.doc.next_sibling(n);
2531        while let Some(p) = at {
2532            if self.doc.element(p).is_some() {
2533                return Some(p);
2534            }
2535            at = self.doc.next_sibling(p);
2536        }
2537        None
2538    }
2539
2540    /// Does `el` match `c`? `anchor` is the element a relative selector in
2541    /// `:has()` hangs from.
2542    ///
2543    /// A loop over the parts, not a call per part: a selector can chain as
2544    /// many compounds as it likes, and a call each overflowed the stack.
2545    /// When a part fails, it backs up only as far as can help, as browsers
2546    /// do. If the rest found no ancestor at all, no higher one will do; if
2547    /// a sibling failed, the nearest descendant combinator tries the next
2548    /// ancestor. Trying every choice instead made `x div div ...` over a
2549    /// few dozen nested divs take seconds.
2550    fn complex(&self, c: &Complex, el: NodeId, anchor: NodeId) -> bool {
2551        if let Some(Simple::Pseudo(Pseudo::Slotted(arg))) = c.parts[0].0.0.first() {
2552            return self.slotted(c, arg, el, anchor);
2553        }
2554        // The subject first, here, so a one-part selector costs no more.
2555        self.compound(&c.parts[0].0, el, anchor)
2556            && (c.parts.len() == 1 || self.complex_rest(c, el, anchor))
2557    }
2558
2559    /// `X::slotted(arg)`, `el` the subject: an element `arg` matches,
2560    /// assigned after flattening to a slot in this shadow tree, which the
2561    /// rest of the selector matches from there.
2562    #[cold]
2563    fn slotted(&self, c: &Complex, arg: &Compound, el: NodeId, anchor: NodeId) -> bool {
2564        if self.shadow == NONE || self.doc.element(el).is_none() {
2565            return false;
2566        }
2567        let mut slot = self.doc.assigned_slot(el);
2568        while let Some(s) = slot {
2569            if self.doc.tree_root(s) == self.shadow {
2570                break;
2571            }
2572            slot = self.doc.assigned_slot(s);
2573        }
2574        let Some(slot) = slot else {
2575            return false;
2576        };
2577        self.simples(&arg.0, el, anchor)
2578            && self.compound_of(&c.parts[0].0.0[1..], slot, anchor)
2579            && (c.parts.len() == 1 || self.complex_rest(c, slot, anchor))
2580    }
2581
2582    /// The parts after the subject, which `el` matched.
2583    #[inline(never)]
2584    fn complex_rest(&self, c: &Complex, el: NodeId, anchor: NodeId) -> bool {
2585        let parts = &c.parts;
2586        // Two parts, the commonest chain, have no part further left to back
2587        // up to: try each element the combinator reaches, and stop.
2588        if let [(_, combinator), (left, _)] = parts.as_slice() {
2589            let mut at = self.step(*combinator, el);
2590            while let Some(p) = at {
2591                if self.compound(left, p, anchor) {
2592                    return true;
2593                }
2594                if matches!(combinator, Combinator::Child | Combinator::NextSibling) {
2595                    return false;
2596                }
2597                at = self.next_step(*combinator, el, p);
2598            }
2599            return false;
2600        }
2601        // What each part left of the current one matched, to back up to.
2602        let mut inline = [0; 16];
2603        let mut spilled;
2604        let matched: &mut [NodeId] = if parts.len() <= inline.len() {
2605            &mut inline
2606        } else {
2607            spilled = vec![0; parts.len()];
2608            &mut spilled
2609        };
2610        matched[0] = el;
2611        let Some(next) = self.step(parts[0].1, el) else {
2612            return false;
2613        };
2614        let (mut i, mut at) = (1, next);
2615        loop {
2616            let mut fail = if !self.compound(&parts[i].0, at, anchor) {
2617                Fail::Sibling
2618            } else if i + 1 == parts.len() {
2619                return true;
2620            } else {
2621                let combinator = parts[i].1;
2622                match self.step(combinator, at) {
2623                    Some(next) => {
2624                        matched[i] = at;
2625                        (i, at) = (i + 1, next);
2626                        continue;
2627                    }
2628                    None => Fail::exhausted(combinator),
2629                }
2630            };
2631            // `at` failed parts[i]; back up to the part left of it.
2632            loop {
2633                if i == 0 || fail == Fail::Global {
2634                    return false;
2635                }
2636                i -= 1;
2637                let combinator = parts[i].1;
2638                let retry = match (fail, combinator) {
2639                    (_, Combinator::Child) => {
2640                        fail = Fail::Descendant;
2641                        false
2642                    }
2643                    (_, Combinator::NextSibling)
2644                    | (Fail::Descendant, Combinator::SubsequentSibling) => false,
2645                    _ => true,
2646                };
2647                if retry {
2648                    if let Some(next) = self.next_step(combinator, matched[i], at) {
2649                        (i, at) = (i + 1, next);
2650                        break;
2651                    }
2652                    fail = Fail::exhausted(combinator);
2653                }
2654                at = matched[i];
2655            }
2656        }
2657    }
2658
2659    /// The element a combinator looks at next from `el`: its parent, or
2660    /// its previous element sibling.
2661    #[inline]
2662    fn step(&self, combinator: Combinator, el: NodeId) -> Option<NodeId> {
2663        // In a shadow tree the host is the root's stand-in: the parent of
2664        // its top-level nodes, with no parent or siblings of its own.
2665        if el == self.host {
2666            return None;
2667        }
2668        match combinator {
2669            Combinator::Child | Combinator::Descendant => {
2670                let parent = self.doc.parent(el);
2671                if parent == Some(self.shadow) {
2672                    Some(self.host)
2673                } else {
2674                    parent
2675                }
2676            }
2677            Combinator::NextSibling | Combinator::SubsequentSibling => self.prev_element(el),
2678            Combinator::Column => self.col_after(el, None),
2679            Combinator::None => None,
2680        }
2681    }
2682
2683    /// The element after `prev` that `combinator` reaches from `origin`:
2684    /// the next one up or back from `prev`, or for `||`, the next col
2685    /// over `origin`'s columns, which `prev` alone can't say.
2686    fn next_step(&self, combinator: Combinator, origin: NodeId, prev: NodeId) -> Option<NodeId> {
2687        match combinator {
2688            Combinator::Column => self.col_after(origin, Some(prev)),
2689            _ => self.step(combinator, prev),
2690        }
2691    }
2692
2693    /// The cols over any of a cell's columns, in column order: the first,
2694    /// or the one after `prev`.
2695    fn col_after(&self, cell: NodeId, prev: Option<NodeId>) -> Option<NodeId> {
2696        let (t, x, n) = self.cell_columns(cell)?;
2697        let i = match prev {
2698            None => t.cols.partition_point(|&(_, cx, cn)| cx + cn <= x),
2699            Some(p) => t.col_index.get(&p)? + 1,
2700        };
2701        t.cols
2702            .get(i)
2703            .filter(|&&(_, cx, _)| cx < x + n)
2704            .map(|&(col, ..)| col)
2705    }
2706
2707    /// Whether the budget has run out. Once it has, every compound fails,
2708    /// so whatever is matching unwinds quickly. Out of line, so a query
2709    /// without a budget pays one test of `deadline` per compound.
2710    #[cold]
2711    #[inline(never)]
2712    fn out_of_time(&self) -> bool {
2713        let Some(deadline) = self.deadline else {
2714            return false;
2715        };
2716        let steps = self.steps.get().wrapping_add(1);
2717        self.steps.set(steps);
2718        if steps.is_multiple_of(1024) && Instant::now() >= deadline {
2719            self.timed_out.set(true);
2720        }
2721        self.timed_out.get()
2722    }
2723
2724    fn compound(&self, compound: &Compound, el: NodeId, anchor: NodeId) -> bool {
2725        self.compound_of(&compound.0, el, anchor)
2726    }
2727
2728    fn compound_of(&self, simples: &[Simple], el: NodeId, anchor: NodeId) -> bool {
2729        // The host is featureless in its shadow tree: only `:host` and
2730        // `:host-context()`, alone or in `:is()` or `:where()`, match it,
2731        // and a `:has()` inside `:host()` reaching back to it.
2732        if el == self.host
2733            && !matches!(simples, [Simple::Anchor])
2734            && (simples.is_empty()
2735                || !simples.iter().all(|s| {
2736                    matches!(
2737                        s,
2738                        Simple::Pseudo(
2739                            Pseudo::Host(_)
2740                                | Pseudo::HostContext(_)
2741                                | Pseudo::Is(_)
2742                                | Pseudo::Where(_)
2743                        )
2744                    )
2745                }))
2746        {
2747            return false;
2748        }
2749        self.simples(simples, el, anchor)
2750    }
2751
2752    /// Whether `el` matches every one of a compound's simple selectors,
2753    /// as anywhere else: the host isn't featureless here.
2754    fn simples(&self, simples: &[Simple], el: NodeId, anchor: NodeId) -> bool {
2755        if self.deadline.is_some() && self.out_of_time() {
2756            return false;
2757        }
2758        if matches!(simples, [Simple::Anchor]) {
2759            return el == anchor;
2760        }
2761        let Some(e) = self.doc.element(el) else {
2762            return false;
2763        };
2764        simples.iter().all(|s| match s {
2765            Simple::Type { lower, exact, tag } => {
2766                if e.ns == Ns::Html {
2767                    if *tag != Tag::Other || e.tag != Tag::Other {
2768                        e.tag == *tag
2769                    } else {
2770                        self.doc.element_name(e) == lower
2771                    }
2772                } else if e.ns == Ns::Xml {
2773                    // In XML a type selector names the local part, in any
2774                    // case: `creator` finds `dc:creator` and `Creator`.
2775                    xml_local(self.doc.element_name(e)).eq_ignore_ascii_case(lower)
2776                } else {
2777                    self.doc.element_name(e) == exact
2778                }
2779            }
2780            Simple::Id(id) => self.attr(el, "id").is_some_and(|v| self.quirks_eq(v, id)),
2781            Simple::Class(class) => self.attr(el, "class").is_some_and(|v| {
2782                v.split(is_space_char)
2783                    .any(|c| !c.is_empty() && self.quirks_eq(c, class))
2784            }),
2785            Simple::Attr(a) => self.attr_matches(el, e.ns, a),
2786            Simple::Pseudo(p) => self.pseudo(p, el, anchor),
2787            Simple::Anchor => el == anchor,
2788            Simple::Ns(ns) => e.ns == *ns,
2789        })
2790    }
2791
2792    fn quirks_eq(&self, a: &str, b: &str) -> bool {
2793        if self.doc.quirks() == Quirks::Quirks {
2794            a.eq_ignore_ascii_case(b)
2795        } else {
2796            a == b
2797        }
2798    }
2799
2800    /// The element's language: the nearest `xml:lang` or `lang` on it or
2801    /// an ancestor, `xml:lang` first, as HTML has it. None when nothing says.
2802    fn lang(&self, el: NodeId) -> Option<&str> {
2803        let mut at = Some(el);
2804        while let Some(n) = at {
2805            let mut plain = None;
2806            for (ns, name, value) in self.doc.attrs(n) {
2807                match (ns, name) {
2808                    (AttrNs::Xml, "lang") => return Some(value),
2809                    (AttrNs::None, "lang") => plain = Some(value),
2810                    _ => {}
2811                }
2812            }
2813            if plain.is_some() {
2814                return plain;
2815            }
2816            at = self.doc.parent(n);
2817        }
2818        None
2819    }
2820
2821    /// Whether the element's directionality is right to left, by HTML's
2822    /// rules as far as the document decides them: `dir="ltr"` or `"rtl"`,
2823    /// `dir="auto"` and `<bdi>` from their text, and otherwise the parent's,
2824    /// left to right at the top. Only an HTML element's `dir` counts.
2825    fn is_rtl(&self, el: NodeId) -> bool {
2826        let mut at = Some(el);
2827        while let Some(n) = at {
2828            let Some(e) = self.doc.element(n) else {
2829                return false;
2830            };
2831            if e.ns == Ns::Html {
2832                match self.dir(n).as_deref() {
2833                    Some("ltr") => return false,
2834                    Some("rtl") => return true,
2835                    Some("auto") => return self.auto_rtl(n),
2836                    _ if self.doc.lower_name(n) == Some("bdi") => return self.auto_rtl(n),
2837                    _ => {}
2838                }
2839            }
2840            at = self.doc.parent(n);
2841        }
2842        false
2843    }
2844
2845    /// A valid `dir` value, lowercased.
2846    fn dir(&self, el: NodeId) -> Option<String> {
2847        self.attr(el, "dir")
2848            .map(|d| d.to_ascii_lowercase())
2849            .filter(|d| matches!(d.as_str(), "ltr" | "rtl" | "auto"))
2850    }
2851
2852    /// `dir="auto"`: right to left when the first strong character is. A
2853    /// text field reads its value; anything else its text, leaving out
2854    /// `<bdi>`, `<script>`, `<style>`, `<textarea>` and anything with its own
2855    /// `dir`. No strong character at all is left to right.
2856    fn auto_rtl(&self, el: NodeId) -> bool {
2857        let tag = self.doc.element(el).map(|e| e.tag);
2858        if tag == Some(Tag::Textarea) {
2859            return first_strong_rtl(&self.doc.text(el)).unwrap_or(false);
2860        }
2861        if tag == Some(Tag::Input) {
2862            let text_field = self.attr(el, "type").is_none_or(|t| {
2863                matches!(
2864                    t.to_ascii_lowercase().as_str(),
2865                    "text" | "search" | "tel" | "url" | "email"
2866                )
2867            });
2868            return text_field
2869                && first_strong_rtl(self.attr(el, "value").unwrap_or("")).unwrap_or(false);
2870        }
2871        let mut stack: Vec<NodeId> = self.doc.children(el).collect();
2872        stack.reverse();
2873        while let Some(n) = stack.pop() {
2874            match self.doc.kind(n) {
2875                crate::Kind::Text(t) => {
2876                    if let Some(rtl) = first_strong_rtl(t) {
2877                        return rtl;
2878                    }
2879                }
2880                crate::Kind::Element { ns, .. } => {
2881                    let skip = ns == Ns::Html
2882                        && (self.dir(n).is_some()
2883                            || matches!(
2884                                self.doc.element(n).map(|e| e.tag),
2885                                Some(Tag::Script | Tag::Style | Tag::Textarea)
2886                            )
2887                            || self.doc.lower_name(n) == Some("bdi"));
2888                    if !skip {
2889                        let at = stack.len();
2890                        stack.extend(self.doc.children(n));
2891                        stack[at..].reverse();
2892                    }
2893                }
2894                _ => {}
2895            }
2896        }
2897        false
2898    }
2899
2900    /// Whether `el` is an `<input>` whose type, in any case, is one of `types`.
2901    fn input_type(&self, el: NodeId, types: &[&str]) -> bool {
2902        self.attr(el, "type")
2903            .is_some_and(|t| types.iter().any(|w| t.eq_ignore_ascii_case(w)))
2904    }
2905
2906    fn html_tag(&self, n: NodeId, tag: Tag) -> bool {
2907        self.doc
2908            .element(n)
2909            .is_some_and(|e| e.ns == Ns::Html && e.tag == tag)
2910    }
2911
2912    fn html_named(&self, n: NodeId, name: &str) -> bool {
2913        self.doc.element(n).is_some_and(|e| e.ns == Ns::Html)
2914            && self.doc.lower_name(n) == Some(name)
2915    }
2916
2917    /// `el`'s tree in tree order, from its root.
2918    // shortcut: walked afresh for each control matched, so :default or
2919    // :indeterminate over a page of n radio buttons is O(n^2); keep a
2920    // per-select index of forms and radio groups if pages ever have
2921    // thousands.
2922    fn tree_of(&self, el: NodeId) -> Vec<NodeId> {
2923        let mut root = el;
2924        while let Some(p) = self.doc.parent(root) {
2925            root = p;
2926        }
2927        let (mut out, mut stack) = (Vec::new(), vec![root]);
2928        while let Some(n) = stack.pop() {
2929            out.push(n);
2930            let at = stack.len();
2931            stack.extend(self.doc.children(n));
2932            stack[at..].reverse();
2933        }
2934        out
2935    }
2936
2937    /// The form a control belongs to: the one its `form` attribute names,
2938    /// or with no such attribute the nearest form around it.
2939    fn form_owner(&self, el: NodeId) -> Option<NodeId> {
2940        if let Some(id) = self.attr(el, "form") {
2941            return self
2942                .tree_of(el)
2943                .into_iter()
2944                .find(|&n| self.doc.element(n).is_some() && self.attr(n, "id") == Some(id))
2945                .filter(|&f| self.html_tag(f, Tag::Form));
2946        }
2947        let mut at = self.parent_element(el);
2948        while let Some(p) = at {
2949            if self.html_tag(p, Tag::Form) {
2950                return Some(p);
2951            }
2952            at = self.parent_element(p);
2953        }
2954        None
2955    }
2956
2957    fn submit_button(&self, el: NodeId, tag: Tag) -> bool {
2958        match tag {
2959            // A button's type is submit unless it says reset or button.
2960            Tag::Button => self.attr(el, "type").is_none_or(|t| {
2961                !t.eq_ignore_ascii_case("reset") && !t.eq_ignore_ascii_case("button")
2962            }),
2963            Tag::Input => self.input_type(el, &["submit", "image"]),
2964            _ => false,
2965        }
2966    }
2967
2968    /// Whether `el` is its form's default button: the first submit button
2969    /// in tree order that belongs to the same form.
2970    fn default_button(&self, el: NodeId, tag: Tag) -> bool {
2971        if !self.submit_button(el, tag) {
2972            return false;
2973        }
2974        let Some(form) = self.form_owner(el) else {
2975            return false;
2976        };
2977        self.tree_of(el).into_iter().find(|&n| {
2978            self.doc.element(n).is_some_and(|e| {
2979                e.ns == Ns::Html && self.submit_button(n, e.tag) && self.form_owner(n) == Some(form)
2980            })
2981        }) == Some(el)
2982    }
2983
2984    /// Whether no radio button in `el`'s group is checked: the radio
2985    /// buttons with its name and form, in its tree. With no name it's a
2986    /// group of one.
2987    fn radio_group_unchecked(&self, el: NodeId) -> bool {
2988        if self.attr(el, "checked").is_some() {
2989            return false;
2990        }
2991        let Some(name) = self.attr(el, "name").filter(|n| !n.is_empty()) else {
2992            return true;
2993        };
2994        let form = self.form_owner(el);
2995        !self.tree_of(el).into_iter().any(|n| {
2996            self.html_tag(n, Tag::Input)
2997                && self.input_type(n, &["radio"])
2998                && self.attr(n, "name") == Some(name)
2999                && self.attr(n, "checked").is_some()
3000                && self.form_owner(n) == form
3001        })
3002    }
3003
3004    /// For an `<input>` with range limitations that takes part in
3005    /// validation, whether its value is in range; None for any other.
3006    /// An empty or unreadable value isn't out of range, and a range
3007    /// input's value is always brought into range.
3008    fn in_range(&self, el: NodeId) -> Option<bool> {
3009        let typ = self.attr(el, "type")?.to_ascii_lowercase();
3010        let read = |name: &str| self.attr(el, name).and_then(|v| input_number(&typ, v));
3011        let (min, max) = match typ.as_str() {
3012            "range" => (read("min").or(Some(0.0)), read("max").or(Some(100.0))),
3013            "number" | "date" | "month" | "week" | "time" | "datetime-local" => {
3014                (read("min"), read("max"))
3015            }
3016            _ => return None,
3017        };
3018        if min.is_none() && max.is_none() {
3019            return None;
3020        }
3021        // Barred from validation: disabled, read-only where that applies,
3022        // or inside a datalist.
3023        let in_datalist = {
3024            let mut at = self.parent_element(el);
3025            let mut found = false;
3026            while let Some(p) = at {
3027                if self.html_named(p, "datalist") {
3028                    found = true;
3029                    break;
3030                }
3031                at = self.parent_element(p);
3032            }
3033            found
3034        };
3035        if self.disabled(el, Tag::Input)
3036            || (typ != "range" && self.attr(el, "readonly").is_some())
3037            || in_datalist
3038        {
3039            return None;
3040        }
3041        if typ == "range" {
3042            return Some(true);
3043        }
3044        let Some(value) = read("value") else {
3045            return Some(true);
3046        };
3047        Some(match (min, max) {
3048            // A time range may wrap past midnight: 22:00 to 06:00.
3049            (Some(lo), Some(hi)) if typ == "time" && lo > hi => value >= lo || value <= hi,
3050            _ => min.is_none_or(|lo| value >= lo) && max.is_none_or(|hi| value <= hi),
3051        })
3052    }
3053
3054    /// For `:valid` and `:invalid`: whether `el` satisfies its constraints,
3055    /// or for a form or fieldset whether everything in it does; None for an
3056    /// element that doesn't take part in validation.
3057    fn valid(&self, el: NodeId, tag: Tag) -> Option<bool> {
3058        match tag {
3059            Tag::Form => Some(!self.tree_of(el).into_iter().any(|n| {
3060                self.doc.element(n).is_some_and(|e| e.ns == Ns::Html)
3061                    && self.form_owner(n) == Some(el)
3062                    && self.control_valid(n) == Some(false)
3063            })),
3064            Tag::Fieldset => {
3065                let mut stack: Vec<NodeId> = self.doc.children(el).collect();
3066                while let Some(n) = stack.pop() {
3067                    if self.control_valid(n) == Some(false) {
3068                        return Some(false);
3069                    }
3070                    stack.extend(self.doc.children(n));
3071                }
3072                Some(true)
3073            }
3074            _ => self.control_valid(el),
3075        }
3076    }
3077
3078    /// Whether a form control satisfies its constraints, None when it's
3079    /// barred from validation. The static document's value is the `value`
3080    /// attribute, or a textarea's text. Only what the markup decides is
3081    /// checked: not too long, too short or bad input, which only someone
3082    /// typing can cause.
3083    fn control_valid(&self, el: NodeId) -> Option<bool> {
3084        let e = self.doc.element(el)?;
3085        if e.ns != Ns::Html || self.disabled(el, e.tag) || self.in_datalist(el) {
3086            return None;
3087        }
3088        let required = self.attr(el, "required").is_some();
3089        match e.tag {
3090            Tag::Input => {
3091                let typ = input_type_state(self.attr(el, "type"));
3092                if matches!(typ, "hidden" | "reset" | "button")
3093                    || (readonly_applies(typ) && self.attr(el, "readonly").is_some())
3094                {
3095                    return None;
3096                }
3097                Some(self.input_valid(el, typ, required))
3098            }
3099            Tag::Textarea => {
3100                if self.attr(el, "readonly").is_some() {
3101                    return None;
3102                }
3103                Some(!required || !self.doc.text(el).is_empty())
3104            }
3105            Tag::Select => Some(!required || self.select_has_value(el)),
3106            Tag::Button => self.submit_button(el, Tag::Button).then_some(true),
3107            _ => None,
3108        }
3109    }
3110
3111    fn input_valid(&self, el: NodeId, typ: &str, required: bool) -> bool {
3112        match typ {
3113            "checkbox" => !required || self.attr(el, "checked").is_some(),
3114            "radio" => !self.radio_value_missing(el),
3115            // A static page has no files chosen.
3116            "file" => !required,
3117            "submit" | "image" | "color" | "range" => true,
3118            _ => {
3119                let value = sanitized(
3120                    typ,
3121                    self.attr(el, "value").unwrap_or(""),
3122                    self.attr(el, "multiple").is_some(),
3123                );
3124                if value.is_empty() {
3125                    return !required;
3126                }
3127                let multiple = typ == "email" && self.attr(el, "multiple").is_some();
3128                if !self.pattern_fits(el, typ, &value, multiple) {
3129                    return false;
3130                }
3131                match typ {
3132                    "email" if self.attr(el, "multiple").is_some() => {
3133                        value.split(',').all(valid_email)
3134                    }
3135                    "email" => valid_email(&value),
3136                    "url" => url::Url::parse(&value).is_ok(),
3137                    "number" | "date" | "month" | "week" | "time" | "datetime-local" => {
3138                        self.in_range(el) != Some(false) && self.step_fits(el, typ, &value)
3139                    }
3140                    _ => true,
3141                }
3142            }
3143        }
3144    }
3145
3146    /// Whether the value matches `pattern`, for the types it applies to:
3147    /// each value of a multiple email. A pattern that doesn't compile counts
3148    /// as none, as the standard says.
3149    fn pattern_fits(&self, el: NodeId, typ: &str, value: &str, multiple: bool) -> bool {
3150        if !matches!(
3151            typ,
3152            "text" | "search" | "tel" | "url" | "email" | "password"
3153        ) {
3154            return true;
3155        }
3156        let Some(pattern) = self.attr(el, "pattern").and_then(Pattern::compile) else {
3157            return true;
3158        };
3159        if multiple {
3160            value
3161                .split(',')
3162                .all(|v| pattern.matches(v, &self.pattern_budget))
3163        } else {
3164            pattern.matches(value, &self.pattern_budget)
3165        }
3166    }
3167
3168    /// Whether the value lands on a step from `min`. With no valid `min` the
3169    /// step base is the value itself, so any value fits.
3170    fn step_fits(&self, el: NodeId, typ: &str, value: &str) -> bool {
3171        let (default, scale) = match typ {
3172            "week" => (1.0, 7.0),
3173            "time" | "datetime-local" => (60.0, 1000.0),
3174            _ => (1.0, 1.0),
3175        };
3176        let step = match self.attr(el, "step") {
3177            Some(s) if s.eq_ignore_ascii_case("any") => return true,
3178            Some(s) => parse_float_value(s).filter(|&s| s > 0.0).unwrap_or(default),
3179            None => default,
3180        };
3181        let (Some(value), Some(base)) = (
3182            input_number(typ, value),
3183            self.attr(el, "min").and_then(|m| input_number(typ, m)),
3184        ) else {
3185            return true;
3186        };
3187        let steps = (value - base) / (step * scale);
3188        (steps - steps.round()).abs() < 1e-9
3189    }
3190
3191    /// Whether `el`'s radio group is required and has nothing checked.
3192    fn radio_value_missing(&self, el: NodeId) -> bool {
3193        let Some(name) = self.attr(el, "name").filter(|n| !n.is_empty()) else {
3194            return self.attr(el, "required").is_some() && self.attr(el, "checked").is_none();
3195        };
3196        let form = self.form_owner(el);
3197        let group: Vec<NodeId> = self
3198            .tree_of(el)
3199            .into_iter()
3200            .filter(|&n| {
3201                self.html_tag(n, Tag::Input)
3202                    && self.input_type(n, &["radio"])
3203                    && self.attr(n, "name") == Some(name)
3204                    && self.form_owner(n) == form
3205            })
3206            .collect();
3207        group.iter().any(|&n| self.attr(n, "required").is_some())
3208            && group.iter().all(|&n| self.attr(n, "checked").is_none())
3209    }
3210
3211    /// Whether a select has a value to submit: an option selected, and in a
3212    /// one-line single select not the placeholder (a first child option
3213    /// whose value is empty).
3214    fn select_has_value(&self, el: NodeId) -> bool {
3215        let mut options = Vec::new();
3216        let mut stack: Vec<NodeId> = self.doc.children(el).collect();
3217        stack.reverse();
3218        while let Some(n) = stack.pop() {
3219            if self.html_tag(n, Tag::Option) {
3220                options.push(n);
3221            } else if self.html_tag(n, Tag::Optgroup) {
3222                let at = stack.len();
3223                stack.extend(self.doc.children(n));
3224                stack[at..].reverse();
3225            }
3226        }
3227        let marked = |n: &&NodeId| self.attr(**n, "selected").is_some();
3228        let multiple = self.attr(el, "multiple").is_some();
3229        let size = self
3230            .attr(el, "size")
3231            .and_then(parse_non_negative)
3232            .filter(|&s| s > 0)
3233            .unwrap_or(if multiple { 4 } else { 1 });
3234        if multiple {
3235            return options.iter().any(|n| marked(&n));
3236        }
3237        // The last one marked selected wins. With none, a one-line select
3238        // shows its first option that isn't disabled; a list box shows none.
3239        let selected = options.iter().rev().find(marked).or_else(|| {
3240            options
3241                .iter()
3242                .filter(|_| size == 1)
3243                .find(|&&n| self.attr(n, "disabled").is_none() && !self.disabled(n, Tag::Option))
3244        });
3245        let Some(&selected) = selected else {
3246            return false;
3247        };
3248        let placeholder = size == 1
3249            && options.first() == Some(&selected)
3250            && self.doc.parent(selected) == Some(el)
3251            && self.option_value(selected).is_empty();
3252        !placeholder
3253    }
3254
3255    fn option_value(&self, el: NodeId) -> String {
3256        match self.attr(el, "value") {
3257            Some(v) => v.to_string(),
3258            None => self
3259                .doc
3260                .text(el)
3261                .split_ascii_whitespace()
3262                .collect::<Vec<_>>()
3263                .join(" "),
3264        }
3265    }
3266
3267    fn in_datalist(&self, el: NodeId) -> bool {
3268        let mut at = self.parent_element(el);
3269        while let Some(p) = at {
3270            if self.html_named(p, "datalist") {
3271                return true;
3272            }
3273            at = self.parent_element(p);
3274        }
3275        false
3276    }
3277
3278    fn attr(&self, el: NodeId, name: &str) -> Option<&str> {
3279        self.doc
3280            .attrs(el)
3281            .find(|(ns, n, _)| *ns == AttrNs::None && *n == name)
3282            .map(|(_, _, v)| v)
3283    }
3284
3285    fn attr_matches(&self, el: NodeId, ns: Ns, a: &AttrSelector) -> bool {
3286        let doc = self.doc;
3287        if ns == Ns::Xml {
3288            return self.xml_attr_matches(el, a);
3289        }
3290        let html = ns == Ns::Html;
3291        let insensitive = match a.case {
3292            Case::Insensitive => true,
3293            Case::Sensitive => false,
3294            Case::Default => html && case_insensitive_attr(&a.lower),
3295        };
3296        let want = if html { &a.lower } else { &a.exact };
3297        // The raw attributes, so a value is only looked at once the name
3298        // matches.
3299        doc.attrs_of(el).iter().any(|attr| {
3300            // A browser matches SVG's `viewBox` with its case.
3301            let name = doc.written_name(ns, attr);
3302            // A namespaced attribute is stored as written (`xlink:href`);
3303            // `[*|href]` names its local part.
3304            let name = match attr.ns {
3305                AttrNs::None => name,
3306                _ => name.split_once(':').map_or(name, |(_, local)| local),
3307            };
3308            let in_ns = match a.in_ns {
3309                Some(ns) => attr.ns == ns,
3310                None => attr.ns == AttrNs::None || a.any_ns,
3311            };
3312            in_ns
3313                && name == want.as_str()
3314                && (a.op == AttrOp::Exists
3315                    || value_matches(a.op, doc.str(attr.value), &a.value, insensitive))
3316        })
3317    }
3318
3319    /// An attribute selector in XML: the attribute is found by its local
3320    /// name in any case, one written exactly as asked winning over others
3321    /// (`id` over `ID`), and only that one is compared.
3322    fn xml_attr_matches(&self, el: NodeId, a: &AttrSelector) -> bool {
3323        let doc = self.doc;
3324        let range = doc
3325            .element(el)
3326            .map_or(0..0, |e| e.attrs.start as usize..e.attrs.end as usize);
3327        let attrs = &doc.attrs[range];
3328        let local = |attr: &crate::dom::Attr| xml_local(doc.str(attr.name));
3329        let found = attrs
3330            .iter()
3331            .find(|attr| local(attr) == a.exact)
3332            .or_else(|| {
3333                attrs
3334                    .iter()
3335                    .find(|attr| local(attr).eq_ignore_ascii_case(&a.lower))
3336            });
3337        let insensitive = a.case == Case::Insensitive;
3338        found.is_some_and(|attr| {
3339            a.op == AttrOp::Exists
3340                || value_matches(a.op, doc.str(attr.value), &a.value, insensitive)
3341        })
3342    }
3343
3344    fn pseudo(&self, p: &Pseudo, el: NodeId, anchor: NodeId) -> bool {
3345        let doc = self.doc;
3346        let e = doc.element(el).expect("an element");
3347        let html = e.ns == Ns::Html;
3348        let tag = if html { e.tag } else { Tag::Other };
3349        match p {
3350            Pseudo::Not(list) => !list.0.iter().any(|c| self.complex(c, el, anchor)),
3351            Pseudo::Is(list) | Pseudo::Where(list) => {
3352                list.0.iter().any(|c| self.complex(c, el, anchor))
3353            }
3354            Pseudo::Has(list) => list.0.iter().any(|c| self.has(c, el)),
3355            Pseudo::Nth {
3356                a,
3357                b,
3358                last,
3359                of_type,
3360                of,
3361            } => {
3362                let same = |other: NodeId| {
3363                    if *of_type {
3364                        same_type(doc, doc.element(other).unwrap(), e)
3365                    } else if let Some(of) = of {
3366                        of.0.iter().any(|c| self.complex(c, other, other))
3367                    } else {
3368                        true
3369                    }
3370                };
3371                if !same(el) {
3372                    return false;
3373                }
3374                // The walk below could go through every sibling, for every
3375                // sibling: take the positions worked out once per parent
3376                // instead, for S as well when there's `of S`.
3377                if let Some(of) = of
3378                    && let Some((index, count)) = self.of_place(of, el)
3379                {
3380                    let index = if *last { count - index + 1 } else { index };
3381                    return nth_matches(*a as i64, *b as i64, index as i64);
3382                }
3383                if *a > 0
3384                    && let Some(m) = self.nth_by_place(el, *a, *b, *last, *of_type)
3385                {
3386                    return m;
3387                }
3388                // With a <= 0 the walk stops at b, which is usually soon;
3389                // a walk that goes on, past other types or to a large b,
3390                // takes the positions too.
3391                let mut walked = 0;
3392                let mut index = 1i64;
3393                let mut at = if *last {
3394                    self.next_element(el)
3395                } else {
3396                    self.prev_element(el)
3397                };
3398                while let Some(s) = at {
3399                    walked += 1;
3400                    if walked > 32
3401                        && let Some(m) = self.nth_by_place(el, *a, *b, *last, *of_type)
3402                    {
3403                        return m;
3404                    }
3405                    if same(s) {
3406                        index += 1;
3407                        // With a <= 0 the positions that match end at b, so
3408                        // counting further can't help: `:last-child` looks
3409                        // at one sibling, not all of them.
3410                        if *a <= 0 && index > *b as i64 {
3411                            return false;
3412                        }
3413                    }
3414                    at = if *last {
3415                        self.next_element(s)
3416                    } else {
3417                        self.prev_element(s)
3418                    };
3419                }
3420                nth_matches(*a as i64, *b as i64, index)
3421            }
3422            Pseudo::Only { of_type } => {
3423                let same =
3424                    |other: NodeId| !*of_type || same_type(doc, doc.element(other).unwrap(), e);
3425                // Of-type, the walks can pass any number of other types:
3426                // one that goes on takes the counts worked out per parent.
3427                let mut walked = 0;
3428                for step in [Self::prev_element, Self::next_element] {
3429                    let mut at = step(self, el);
3430                    while let Some(s) = at {
3431                        walked += 1;
3432                        if walked > 32
3433                            && let Some(pl) = self.place(el)
3434                        {
3435                            return pl.type_count == 1;
3436                        }
3437                        if same(s) {
3438                            return false;
3439                        }
3440                        at = step(self, s);
3441                    }
3442                }
3443                true
3444            }
3445            Pseudo::Empty => doc.children(el).all(|c| {
3446                matches!(
3447                    doc.nodes[c as usize].data,
3448                    Data::Comment(_) | Data::ProcessingInstruction { .. }
3449                ) || matches!(doc.kind(c), crate::Kind::Text(t) if t.is_empty())
3450            }),
3451            Pseudo::Root => doc
3452                .parent(el)
3453                .is_some_and(|p| matches!(doc.nodes[p as usize].data, Data::Document)),
3454            Pseudo::Scope => match self.scope {
3455                Some(s) if doc.element(s).is_some() => el == s,
3456                _ => doc
3457                    .parent(el)
3458                    .is_some_and(|p| matches!(doc.nodes[p as usize].data, Data::Document)),
3459            },
3460            Pseudo::AnyLink => matches!(tag, Tag::A | Tag::Area) && self.attr(el, "href").is_some(),
3461            Pseudo::Target => self.page.as_ref().is_some_and(|p| p.target == Some(el)),
3462            Pseudo::TargetWithin => self.page.as_ref().and_then(|p| p.target).is_some_and(|t| {
3463                let mut at = Some(t);
3464                while let Some(n) = at {
3465                    if n == el {
3466                        return true;
3467                    }
3468                    at = self.doc.parent(n);
3469                }
3470                false
3471            }),
3472            Pseudo::LocalLink => {
3473                matches!(tag, Tag::A | Tag::Area)
3474                    && self.page.as_ref().is_some_and(|p| {
3475                        self.attr(el, "href")
3476                            .and_then(|href| p.base.join(href).ok())
3477                            .is_some_and(|mut link| {
3478                                link.set_fragment(None);
3479                                link == p.url
3480                            })
3481                    })
3482            }
3483            Pseudo::Checked => match tag {
3484                Tag::Input => {
3485                    self.attr(el, "checked").is_some()
3486                        && self.attr(el, "type").is_some_and(|t| {
3487                            t.eq_ignore_ascii_case("checkbox") || t.eq_ignore_ascii_case("radio")
3488                        })
3489                }
3490                Tag::Option => self.attr(el, "selected").is_some(),
3491                _ => false,
3492            },
3493            Pseudo::Default => match tag {
3494                Tag::Input if self.input_type(el, &["checkbox", "radio"]) => {
3495                    self.attr(el, "checked").is_some()
3496                }
3497                Tag::Option => self.attr(el, "selected").is_some(),
3498                Tag::Button | Tag::Input => self.default_button(el, tag),
3499                _ => false,
3500            },
3501            Pseudo::Indeterminate => match tag {
3502                Tag::Input if self.input_type(el, &["radio"]) => self.radio_group_unchecked(el),
3503                // A checkbox is only indeterminate when a script says so.
3504                _ => self.html_named(el, "progress") && self.attr(el, "value").is_none(),
3505            },
3506            Pseudo::InRange => tag == Tag::Input && self.in_range(el) == Some(true),
3507            Pseudo::OutOfRange => tag == Tag::Input && self.in_range(el) == Some(false),
3508            Pseudo::Valid => self.valid(el, tag) == Some(true),
3509            Pseudo::Invalid => self.valid(el, tag) == Some(false),
3510            Pseudo::Disabled => self.disabled(el, tag),
3511            Pseudo::Enabled => self.form_control(tag) && !self.disabled(el, tag),
3512            Pseudo::Required => {
3513                matches!(tag, Tag::Input | Tag::Select | Tag::Textarea)
3514                    && self.attr(el, "required").is_some()
3515            }
3516            Pseudo::Optional => {
3517                matches!(tag, Tag::Input | Tag::Select | Tag::Textarea)
3518                    && self.attr(el, "required").is_none()
3519            }
3520            Pseudo::ReadWrite => self.read_write(el, tag),
3521            Pseudo::ReadOnly => !self.read_write(el, tag),
3522            Pseudo::PlaceholderShown => match tag {
3523                Tag::Input => {
3524                    self.attr(el, "placeholder").is_some()
3525                        && self.attr(el, "value").is_none_or(str::is_empty)
3526                }
3527                Tag::Textarea => self.attr(el, "placeholder").is_some() && doc.text(el).is_empty(),
3528                _ => false,
3529            },
3530            // The current draft's meaning: :placeholder-shown without the
3531            // placeholder, on the fields placeholder applies to.
3532            Pseudo::Blank => match tag {
3533                Tag::Input => {
3534                    text_entry(input_type_state(self.attr(el, "type")))
3535                        && self.attr(el, "value").is_none_or(str::is_empty)
3536                }
3537                Tag::Textarea => doc.text(el).is_empty(),
3538                _ => false,
3539            },
3540            // The DOM gives an HTML element made with a custom element's
3541            // name, or with is=, the state "undefined" until a definition
3542            // upgrades it, and nothing here defines one.
3543            Pseudo::Defined => {
3544                !(html
3545                    && (self.attr(el, "is").is_some()
3546                        || doc.lower_name(el).is_some_and(custom_element_name)))
3547            }
3548            Pseudo::Lang(ranges) => self.lang(el).is_some_and(|tag| {
3549                let tag = tag.to_ascii_lowercase();
3550                ranges.iter().any(|range| lang_matches(range, &tag))
3551            }),
3552            Pseudo::Dir(rtl) => self.is_rtl(el) == *rtl,
3553            Pseudo::Heading(levels) => {
3554                let level = match tag {
3555                    Tag::H1 => 1,
3556                    Tag::H2 => 2,
3557                    Tag::H3 => 3,
3558                    Tag::H4 => 4,
3559                    Tag::H5 => 5,
3560                    Tag::H6 => 6,
3561                    _ => return false,
3562                };
3563                levels.is_empty() || levels.contains(&level)
3564            }
3565            Pseudo::Never | Pseudo::Element => false,
3566            Pseudo::Host(arg) => {
3567                el == self.host && arg.as_ref().is_none_or(|c| self.simples(&c.0, el, anchor))
3568            }
3569            Pseudo::HostContext(c) => {
3570                el == self.host && {
3571                    let mut at = Some(el);
3572                    while let Some(n) = at {
3573                        if doc.element(n).is_some() && self.simples(&c.0, n, anchor) {
3574                            return true;
3575                        }
3576                        at = doc.shadow_including_parent(n);
3577                    }
3578                    false
3579                }
3580            }
3581            // Matched in `slotted`, before the compound's other parts.
3582            Pseudo::Slotted(_) => false,
3583            // A cell's columns are a run of positions, so one sum says
3584            // whether any of them fits, however many it spans.
3585            Pseudo::NthCol { a, b, last } => self.cell_columns(el).is_some_and(|(t, x, n)| {
3586                let (lo, hi) = if *last {
3587                    (t.width - (x + n) + 1, t.width - x)
3588                } else {
3589                    (x + 1, x + n)
3590                };
3591                nth_in_range(*a as i64, *b as i64, lo as i64, hi as i64)
3592            }),
3593        }
3594    }
3595
3596    /// `:has()`: some element related to `el` as the relative selector
3597    /// says matches it, with `el` as its anchor.
3598    fn has(&self, c: &Complex, el: NodeId) -> bool {
3599        let doc = self.doc;
3600        // The combinator next to the anchor decides where to look: below
3601        // it, or among its later siblings and below them.
3602        let first = c.parts[c.parts.len() - 2].1;
3603        // One compound, the usual shape: only the elements the combinator
3604        // reaches can match, and the compound doesn't depend on the
3605        // anchor, so what lies below or after an element is worth keeping.
3606        if let [(compound, _), _] = c.parts.as_slice()
3607            && first != Combinator::Column
3608        {
3609            let key = std::ptr::from_ref(c) as usize;
3610            return match first {
3611                Combinator::Child => doc
3612                    .children(el)
3613                    .any(|k| doc.element(k).is_some() && self.compound(compound, k, el)),
3614                Combinator::NextSibling => self
3615                    .next_element(el)
3616                    .is_some_and(|s| self.compound(compound, s, el)),
3617                Combinator::SubsequentSibling => self.later_holds(key, compound, el),
3618                _ => self.below_holds(key, compound, el),
3619            };
3620        }
3621        let mut stack: Vec<NodeId> = Vec::new();
3622        match first {
3623            Combinator::NextSibling | Combinator::SubsequentSibling => {
3624                let mut at = self.next_element(el);
3625                while let Some(s) = at {
3626                    stack.push(s);
3627                    at = self.next_element(s);
3628                }
3629            }
3630            // A col's cells are elsewhere in its table.
3631            Combinator::Column => {
3632                let table = doc.parent(el).and_then(|g| doc.parent(g));
3633                if self.html_tag_of(el) == Some(Tag::Col)
3634                    && let Some(t) = table.filter(|&t| self.html_tag_of(t) == Some(Tag::Table))
3635                {
3636                    push_children_reversed(doc, t, &mut stack);
3637                }
3638            }
3639            _ => push_children_reversed(doc, el, &mut stack),
3640        }
3641        while let Some(n) = stack.pop() {
3642            if doc.element(n).is_none() {
3643                continue;
3644            }
3645            if self.complex(c, n, el) {
3646                return true;
3647            }
3648            push_children_reversed(doc, n, &mut stack);
3649        }
3650        false
3651    }
3652
3653    /// Whether an element below `el` matches `compound`. A subtree walked
3654    /// is remembered as holding a match or not, so in a deep chain each
3655    /// element is looked at once, not once per ancestor.
3656    fn below_holds(&self, key: usize, compound: &Compound, el: NodeId) -> bool {
3657        let doc = self.doc;
3658        if self.has_seen.borrow().get(&(key, el)) == Some(&false) {
3659            return false;
3660        }
3661        // A node comes off twice: on the way down, then marked done once
3662        // its subtree is through, with nothing in it matching.
3663        let mut stack: Vec<(NodeId, bool)> = Vec::new();
3664        let at = stack.len();
3665        stack.extend(doc.children(el).map(|k| (k, false)));
3666        stack[at..].reverse();
3667        while let Some((n, done)) = stack.pop() {
3668            if done {
3669                self.has_seen.borrow_mut().insert((key, n), false);
3670                continue;
3671            }
3672            if doc.element(n).is_none() {
3673                continue;
3674            }
3675            let known = self.has_seen.borrow().get(&(key, n)).copied();
3676            if known == Some(false) {
3677                continue;
3678            }
3679            if known == Some(true) || self.compound(compound, n, el) {
3680                // n holds a match, and so does everything up to `el`.
3681                let mut seen = self.has_seen.borrow_mut();
3682                let mut up = Some(n);
3683                while let Some(u) = up {
3684                    seen.insert((key, u), true);
3685                    up = doc.parent(u).filter(|_| u != el);
3686                }
3687                return true;
3688            }
3689            stack.push((n, true));
3690            let at = stack.len();
3691            stack.extend(doc.children(n).map(|k| (k, false)));
3692            stack[at..].reverse();
3693        }
3694        false
3695    }
3696
3697    /// Whether an element after `el` among its siblings matches
3698    /// `compound`, remembered for each sibling walked past.
3699    fn later_holds(&self, key: usize, compound: &Compound, el: NodeId) -> bool {
3700        let mut walked = Vec::new();
3701        let mut at = self.next_element(el);
3702        let found = loop {
3703            let Some(s) = at else { break false };
3704            if let Some(&known) = self.has_seen.borrow().get(&(key, s)) {
3705                break known;
3706            }
3707            walked.push(s);
3708            if self.compound(compound, s, el) {
3709                break true;
3710            }
3711            at = self.next_element(s);
3712        };
3713        let mut seen = self.has_seen.borrow_mut();
3714        for s in walked {
3715            seen.insert((key, s), found);
3716        }
3717        found
3718    }
3719
3720    fn form_control(&self, tag: Tag) -> bool {
3721        matches!(
3722            tag,
3723            Tag::Button
3724                | Tag::Input
3725                | Tag::Select
3726                | Tag::Textarea
3727                | Tag::Optgroup
3728                | Tag::Option
3729                | Tag::Fieldset
3730        )
3731    }
3732
3733    /// The HTML Standard's "actually disabled".
3734    fn disabled(&self, el: NodeId, tag: Tag) -> bool {
3735        let doc = self.doc;
3736        match tag {
3737            Tag::Optgroup => self.attr(el, "disabled").is_some(),
3738            Tag::Option => {
3739                self.attr(el, "disabled").is_some()
3740                    || self.parent_element(el).is_some_and(|p| {
3741                        doc.element(p)
3742                            .is_some_and(|e| e.ns == Ns::Html && e.tag == Tag::Optgroup)
3743                            && self.attr(p, "disabled").is_some()
3744                    })
3745            }
3746            Tag::Button | Tag::Input | Tag::Select | Tag::Textarea | Tag::Fieldset => {
3747                if self.attr(el, "disabled").is_some() {
3748                    return true;
3749                }
3750                // A descendant of a disabled fieldset, outside its first
3751                // legend.
3752                let mut child = el;
3753                let mut at = self.parent_element(el);
3754                while let Some(p) = at {
3755                    let pe = doc.element(p).unwrap();
3756                    if pe.ns == Ns::Html
3757                        && pe.tag == Tag::Fieldset
3758                        && self.attr(p, "disabled").is_some()
3759                    {
3760                        let first_legend = doc.children(p).find(|&c| {
3761                            doc.element(c).is_some_and(|e| {
3762                                e.ns == Ns::Html && doc.element_name(e) == "legend"
3763                            })
3764                        });
3765                        if first_legend != Some(child) {
3766                            return true;
3767                        }
3768                    }
3769                    child = p;
3770                    at = self.parent_element(p);
3771                }
3772                false
3773            }
3774            _ => false,
3775        }
3776    }
3777
3778    fn read_write(&self, el: NodeId, tag: Tag) -> bool {
3779        match tag {
3780            Tag::Input => {
3781                let typ = self.attr(el, "type").unwrap_or("text").to_ascii_lowercase();
3782                let mutable = matches!(
3783                    typ.as_str(),
3784                    "text"
3785                        | "search"
3786                        | "url"
3787                        | "tel"
3788                        | "email"
3789                        | "password"
3790                        | "date"
3791                        | "month"
3792                        | "week"
3793                        | "time"
3794                        | "datetime-local"
3795                        | "number"
3796                        | ""
3797                );
3798                mutable && self.attr(el, "readonly").is_none() && !self.disabled(el, tag)
3799            }
3800            Tag::Textarea => self.attr(el, "readonly").is_none() && !self.disabled(el, tag),
3801            _ => self.editable(el),
3802        }
3803    }
3804
3805    /// Inside an element whose contenteditable says it's editable.
3806    fn editable(&self, el: NodeId) -> bool {
3807        let mut at = Some(el);
3808        while let Some(n) = at {
3809            if let Some(v) = self.attr(n, "contenteditable") {
3810                return !v.eq_ignore_ascii_case("false");
3811            }
3812            at = self.parent_element(n);
3813        }
3814        false
3815    }
3816}
3817
3818/// Same namespace and name: by tag number when the parser knows the tag.
3819fn same_type(doc: &Document, a: &crate::dom::Element, b: &crate::dom::Element) -> bool {
3820    a.ns == b.ns
3821        && if a.tag != Tag::Other || b.tag != Tag::Other {
3822            a.tag == b.tag && (a.ns == Ns::Html || doc.element_name(a) == doc.element_name(b))
3823        } else {
3824            doc.element_name(a) == doc.element_name(b)
3825        }
3826}
3827
3828/// An XML name without its prefix.
3829fn xml_local(name: &str) -> &str {
3830    name.split_once(':').map_or(name, |(_, local)| local)
3831}
3832
3833fn nth_matches(a: i64, b: i64, index: i64) -> bool {
3834    if a == 0 {
3835        return index == b;
3836    }
3837    let diff = index - b;
3838    diff % a == 0 && diff / a >= 0
3839}
3840
3841/// Whether some position from `lo` to `hi` is `a`n+`b` for an n >= 0.
3842fn nth_in_range(a: i64, b: i64, lo: i64, hi: i64) -> bool {
3843    match a.cmp(&0) {
3844        std::cmp::Ordering::Equal => (lo..=hi).contains(&b),
3845        // The first matching position at or after lo, if it's by hi.
3846        std::cmp::Ordering::Greater => {
3847            let from = lo.max(b);
3848            from + (b - from).rem_euclid(a) <= hi
3849        }
3850        // The last matching position at or before hi, if it's from lo.
3851        std::cmp::Ordering::Less => {
3852            let to = hi.min(b);
3853            to - (to - b).rem_euclid(-a) >= lo
3854        }
3855    }
3856}
3857
3858fn value_matches(op: AttrOp, value: &str, want: &str, insensitive: bool) -> bool {
3859    let eq = |x: &str, y: &str| {
3860        if insensitive {
3861            x.eq_ignore_ascii_case(y)
3862        } else {
3863            x == y
3864        }
3865    };
3866    match op {
3867        AttrOp::Exists => true,
3868        AttrOp::Equals => eq(value, want),
3869        AttrOp::Includes => {
3870            !want.is_empty()
3871                && !want.contains(is_space_char)
3872                && value.split(is_space_char).any(|w| eq(w, want))
3873        }
3874        AttrOp::DashMatch => {
3875            eq(value, want)
3876                || (value.len() > want.len()
3877                    && value.as_bytes()[want.len()] == b'-'
3878                    && value.is_char_boundary(want.len())
3879                    && eq(&value[..want.len()], want))
3880        }
3881        AttrOp::Prefix => {
3882            !want.is_empty()
3883                && value.len() >= want.len()
3884                && value.is_char_boundary(want.len())
3885                && eq(&value[..want.len()], want)
3886        }
3887        AttrOp::Suffix => {
3888            !want.is_empty()
3889                && value.len() >= want.len()
3890                && value.is_char_boundary(value.len() - want.len())
3891                && eq(&value[value.len() - want.len()..], want)
3892        }
3893        AttrOp::Substring => {
3894            !want.is_empty()
3895                && if insensitive {
3896                    value
3897                        .to_ascii_lowercase()
3898                        .contains(&want.to_ascii_lowercase())
3899                } else {
3900                    value.contains(want)
3901                }
3902        }
3903    }
3904}
3905
3906#[cfg(test)]
3907mod nth_range_tests {
3908    #[test]
3909    fn nth_in_range_agrees_with_each_position() {
3910        for a in -4..=4 {
3911            for b in -6..=8 {
3912                for lo in 1..=7 {
3913                    for hi in lo..=9 {
3914                        let each = (lo..=hi).any(|i| super::nth_matches(a, b, i));
3915                        assert_eq!(
3916                            super::nth_in_range(a, b, lo, hi),
3917                            each,
3918                            "{a}n+{b} in {lo}..={hi}"
3919                        );
3920                    }
3921                }
3922            }
3923        }
3924    }
3925}