1use 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#[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#[derive(Debug, Clone)]
45pub struct SelectorList(Vec<Complex>);
46
47#[derive(Debug, Clone)]
50struct Complex {
51 parts: Vec<(Compound, Combinator)>,
52}
53
54#[derive(Debug, Clone, Copy, PartialEq, Eq)]
55enum Combinator {
56 None,
58 Descendant,
59 Child,
60 NextSibling,
61 SubsequentSibling,
62 Column,
64}
65
66#[derive(Debug, Clone, Default)]
67struct Compound(Vec<Simple>);
68
69#[derive(Debug, Clone)]
70enum Simple {
71 Type {
74 lower: String,
75 exact: String,
76 tag: Tag,
79 },
80 Id(String),
81 Class(String),
82 Attr(AttrSelector),
83 Pseudo(Pseudo),
84 Anchor,
86 Ns(Ns),
88}
89
90#[derive(Debug, Clone)]
91struct AttrSelector {
92 lower: String,
93 exact: String,
94 any_ns: bool,
96 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 Default,
120 Insensitive,
121 Sensitive,
122}
123
124#[derive(Debug, Clone)]
125enum Pseudo {
126 Not(SelectorList),
127 Is(SelectorList),
128 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,
155 Defined,
158 Target,
159 TargetWithin,
160 LocalLink,
161 Lang(Vec<String>),
163 Dir(bool),
165 Default,
166 Indeterminate,
167 InRange,
168 OutOfRange,
169 Valid,
170 Invalid,
171 Never,
173 Element,
176 Host(Option<Box<Compound>>),
179 HostContext(Box<Compound>),
182 Slotted(Box<Compound>),
185 Heading(Vec<i64>),
187 NthCol {
190 a: i32,
191 b: i32,
192 last: bool,
193 },
194}
195
196struct Parser<'a> {
199 s: &'a str,
200 pos: usize,
201 depth: u32,
205 in_has: bool,
207 compound_only: bool,
210 opts: &'a ParseOptions<'a>,
211}
212
213const 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 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 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 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 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 fn skip_to_comma(&mut self) -> bool {
393 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 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 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 let mut explicit = false;
500 let mut prefixed = false;
501 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 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 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 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 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 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 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 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 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 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 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 "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 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 "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 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 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 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
1036fn 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
1052fn 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 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
1090fn 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
1122fn text_entry(typ: &str) -> bool {
1125 matches!(
1126 typ,
1127 "text" | "search" | "url" | "tel" | "email" | "password" | "number"
1128 )
1129}
1130
1131pub(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
1177fn 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
1201fn 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
1245fn 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
1254fn 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
1275fn monday_of_week_1(y: i64) -> i64 {
1277 let jan4 = days(y, 1, 4);
1278 let weekday = (jan4 - 1) % 7; jan4 - weekday
1280}
1281
1282fn 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
1311fn 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 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
1351fn 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
1367fn 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
1385fn 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
1400fn weeks_in(y: i64) -> i64 {
1403 let weekday = days(y, 1, 1) % 7; if weekday == 4 || (weekday == 3 && leap(y)) {
1405 53
1406 } else {
1407 52
1408 }
1409}
1410
1411fn 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
1435fn 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
1451fn 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 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#[derive(Debug, Clone, Copy, Default)]
1518pub struct ParseOptions<'a> {
1519 pub namespaces: &'a [(&'a str, Ns)],
1522 pub attr_namespaces: &'a [(&'a str, AttrNs)],
1527 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 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 pub fn matches(&self, doc: &Document, el: NodeId, scope: Option<NodeId>) -> bool {
1584 self.matches_with(doc, el, scope, &MatchOptions::default())
1585 }
1586
1587 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 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 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 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 cx: Cx::new(doc, Some(scope), scope, Page::new(doc, options.url)),
1657 scope,
1658 at: doc.first_child(scope),
1659 }
1660 }
1661
1662 pub fn select(&self, doc: &Document, scope: NodeId) -> Vec<NodeId> {
1666 self.select_iter(doc, scope).collect()
1667 }
1668
1669 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 pub fn select_first(&self, doc: &Document, scope: NodeId) -> Option<NodeId> {
1677 self.select_iter(doc, scope).next()
1678 }
1679
1680 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 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
1760pub 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 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#[derive(Debug, Clone, Copy, Default)]
1817pub struct MatchOptions<'a> {
1818 pub url: Option<&'a str>,
1820 pub budget: Option<Duration>,
1828}
1829
1830#[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
1844fn 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
1859struct Page {
1861 url: url::Url,
1863 base: url::Url,
1865 target: Option<NodeId>,
1867}
1868
1869impl Page {
1870 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
1886fn 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
1908fn 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
1930fn 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 shadow: NodeId,
1963 host: NodeId,
1964 page: Option<Page>,
1965 pattern_budget: Cell<u32>,
1967 deadline: Option<Instant>,
1969 steps: Cell<u32>,
1971 timed_out: Cell<bool>,
1972 places: RefCell<IdMap<NodeId, Place>>,
1976 of_places: RefCell<IdMap<(usize, NodeId), (u32, u32)>>,
1980 has_seen: RefCell<IdMap<(usize, NodeId), bool>>,
1986 tables: RefCell<IdMap<NodeId, Rc<Columns>>>,
1989}
1990
1991type 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#[derive(Clone, Copy, PartialEq, Eq)]
2026enum Fail {
2027 Sibling,
2029 Descendant,
2032 Global,
2034}
2035
2036impl Fail {
2037 fn exhausted(combinator: Combinator) -> Fail {
2039 match combinator {
2040 Combinator::NextSibling | Combinator::SubsequentSibling => Fail::Descendant,
2041 Combinator::Column => Fail::Sibling,
2044 _ => Fail::Global,
2045 }
2046 }
2047}
2048
2049#[derive(Default)]
2052struct Columns {
2053 cells: HashMap<NodeId, (u32, u32)>,
2054 cols: Vec<(NodeId, u32, u32)>,
2056 col_index: HashMap<NodeId, usize>,
2058 width: u32,
2059}
2060
2061#[derive(Default)]
2066struct Cover {
2067 row: u32,
2069 runs: BTreeMap<u32, (u32, u32)>,
2072 blocks: BTreeMap<u32, u32>,
2076 ends: BinaryHeap<Reverse<(u32, u32)>>,
2079}
2080
2081impl Cover {
2082 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 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 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 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#[derive(Clone, Copy)]
2176struct Place {
2177 index: u32,
2178 count: u32,
2179 type_index: u32,
2180 type_count: u32,
2181}
2182
2183fn 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 fn new(doc: &'a Document, scope: Option<NodeId>, in_tree: NodeId, page: Option<Page>) -> Self {
2244 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 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 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 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 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 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 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 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 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 #[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 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 self.compound(&c.parts[0].0, el, anchor)
2556 && (c.parts.len() == 1 || self.complex_rest(c, el, anchor))
2557 }
2558
2559 #[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 #[inline(never)]
2584 fn complex_rest(&self, c: &Complex, el: NodeId, anchor: NodeId) -> bool {
2585 let parts = &c.parts;
2586 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 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 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 #[inline]
2662 fn step(&self, combinator: Combinator, el: NodeId) -> Option<NodeId> {
2663 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 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 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 #[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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 (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 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 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 "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 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 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 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 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 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 doc.attrs_of(el).iter().any(|attr| {
3300 let name = doc.written_name(ns, attr);
3302 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 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 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 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 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 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 _ => 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 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 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 Pseudo::Slotted(_) => false,
3583 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 fn has(&self, c: &Complex, el: NodeId) -> bool {
3599 let doc = self.doc;
3600 let first = c.parts[c.parts.len() - 2].1;
3603 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 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 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 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 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 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 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 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 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
3818fn 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
3828fn 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
3841fn 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 std::cmp::Ordering::Greater => {
3847 let from = lo.max(b);
3848 from + (b - from).rem_euclid(a) <= hi
3849 }
3850 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}