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.limit(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.limit(options);
1642 let found = self.0.iter().any(|c| cx.complex(c, el, el));
1643 timeout(&cx, options)?;
1644 Ok(found)
1645 }
1646
1647 fn iter_with<'a>(
1648 &'a self,
1649 doc: &'a Document,
1650 scope: NodeId,
1651 options: &MatchOptions<'_>,
1652 ) -> Select<'a> {
1653 Select {
1654 list: self,
1655 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 pub max_steps: Option<u64>,
1834}
1835
1836#[derive(Debug, Clone, Copy, PartialEq, Eq)]
1839pub struct MatchTimeout {
1840 pub budget: Duration,
1842 pub max_steps: Option<u64>,
1844}
1845
1846impl std::fmt::Display for MatchTimeout {
1847 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
1848 match self.max_steps {
1849 Some(steps) => write!(f, "matching took more than {steps} steps"),
1850 None => write!(f, "matching took longer than {:?}", self.budget),
1851 }
1852 }
1853}
1854
1855impl std::error::Error for MatchTimeout {}
1856
1857fn deadline(options: &MatchOptions<'_>) -> Option<Instant> {
1860 options.budget.and_then(|b| Instant::now().checked_add(b))
1861}
1862
1863fn timeout(cx: &Cx<'_>, options: &MatchOptions<'_>) -> Result<(), MatchTimeout> {
1864 if !cx.timed_out.get() {
1865 return Ok(());
1866 }
1867 let max_steps = options.max_steps.filter(|&m| cx.steps.get() > m);
1868 Err(MatchTimeout {
1869 budget: match max_steps {
1870 Some(_) => Duration::ZERO,
1871 None => options.budget.unwrap_or_default(),
1872 },
1873 max_steps,
1874 })
1875}
1876
1877struct Page {
1879 url: url::Url,
1881 base: url::Url,
1883 target: Option<NodeId>,
1885}
1886
1887impl Page {
1888 fn new(doc: &Document, url: Option<&str>) -> Option<Page> {
1890 let mut url = url::Url::parse(url?).ok()?;
1891 let fragment = url.fragment().map(str::to_string);
1892 url.set_fragment(None);
1893 let elements = tree_elements(doc);
1894 let base = elements
1895 .iter()
1896 .find(|&&n| html_element_named(doc, n, "base") && attr_of(doc, n, "href").is_some())
1897 .and_then(|&n| url.join(attr_of(doc, n, "href")?).ok())
1898 .unwrap_or_else(|| url.clone());
1899 let target = fragment.and_then(|f| indicated(doc, &elements, &f));
1900 Some(Page { url, base, target })
1901 }
1902}
1903
1904fn tree_elements(doc: &Document) -> Vec<NodeId> {
1906 let (mut out, mut stack) = (Vec::new(), vec![doc.root()]);
1907 while let Some(n) = stack.pop() {
1908 if doc.element(n).is_some() {
1909 out.push(n);
1910 }
1911 push_children_reversed(doc, n, &mut stack);
1912 }
1913 out
1914}
1915
1916fn html_element_named(doc: &Document, n: NodeId, name: &str) -> bool {
1917 doc.element(n).is_some_and(|e| e.ns == Ns::Html) && doc.lower_name(n) == Some(name)
1918}
1919
1920fn attr_of<'a>(doc: &'a Document, n: NodeId, name: &str) -> Option<&'a str> {
1921 doc.attrs(n)
1922 .find(|(ns, a, _)| *ns == AttrNs::None && *a == name)
1923 .map(|(_, _, v)| v)
1924}
1925
1926fn indicated(doc: &Document, elements: &[NodeId], fragment: &str) -> Option<NodeId> {
1931 if fragment.is_empty() {
1932 return None;
1933 }
1934 let find = |f: &str| {
1935 elements
1936 .iter()
1937 .copied()
1938 .find(|&n| attr_of(doc, n, "id") == Some(f))
1939 .or_else(|| {
1940 elements.iter().copied().find(|&n| {
1941 html_element_named(doc, n, "a") && attr_of(doc, n, "name") == Some(f)
1942 })
1943 })
1944 };
1945 find(fragment).or_else(|| find(&percent_decode(fragment)))
1946}
1947
1948fn percent_decode(s: &str) -> String {
1950 let b = s.as_bytes();
1951 let mut out = Vec::with_capacity(b.len());
1952 let mut i = 0;
1953 while i < b.len() {
1954 let hex = |c: u8| (c as char).to_digit(16);
1955 match (
1956 b[i],
1957 b.get(i + 1).and_then(|&c| hex(c)),
1958 b.get(i + 2).and_then(|&c| hex(c)),
1959 ) {
1960 (b'%', Some(h), Some(l)) => {
1961 out.push((h * 16 + l) as u8);
1962 i += 3;
1963 }
1964 (c, _, _) => {
1965 out.push(c);
1966 i += 1;
1967 }
1968 }
1969 }
1970 String::from_utf8_lossy(&out).into_owned()
1971}
1972
1973struct Cx<'a> {
1974 doc: &'a Document,
1975 scope: Option<NodeId>,
1976 shadow: NodeId,
1981 host: NodeId,
1982 page: Option<Page>,
1983 pattern_budget: Cell<u32>,
1985 deadline: Option<Instant>,
1988 max_steps: u64,
1989 limited: bool,
1990 steps: Cell<u64>,
1992 timed_out: Cell<bool>,
1993 places: RefCell<IdMap<NodeId, Place>>,
1997 of_places: RefCell<IdMap<(usize, NodeId), (u32, u32)>>,
2001 has_seen: RefCell<IdMap<(usize, NodeId), bool>>,
2007 nested_seen: RefCell<IdMap<(usize, NodeId), bool>>,
2013 tables: RefCell<IdMap<NodeId, Rc<Columns>>>,
2016}
2017
2018type IdMap<K, V> = HashMap<K, V, std::hash::BuildHasherDefault<IdHasher>>;
2023
2024#[derive(Default)]
2025struct IdHasher(u64);
2026
2027impl std::hash::Hasher for IdHasher {
2028 fn write(&mut self, bytes: &[u8]) {
2029 for &b in bytes {
2030 self.write_u64(b as u64);
2031 }
2032 }
2033
2034 fn write_u32(&mut self, n: u32) {
2035 self.write_u64(n as u64);
2036 }
2037
2038 fn write_usize(&mut self, n: usize) {
2039 self.write_u64(n as u64);
2040 }
2041
2042 fn write_u64(&mut self, n: u64) {
2043 self.0 = (self.0.rotate_left(5) ^ n).wrapping_mul(0x51_7c_c1_b7_27_22_0a_95);
2044 }
2045
2046 fn finish(&self) -> u64 {
2047 self.0
2048 }
2049}
2050
2051#[derive(Clone, Copy, PartialEq, Eq)]
2053enum Fail {
2054 Sibling,
2056 Descendant,
2059 Global,
2061}
2062
2063impl Fail {
2064 fn exhausted(combinator: Combinator) -> Fail {
2066 match combinator {
2067 Combinator::NextSibling | Combinator::SubsequentSibling => Fail::Descendant,
2068 Combinator::Column => Fail::Sibling,
2071 _ => Fail::Global,
2072 }
2073 }
2074}
2075
2076#[derive(Default)]
2079struct Columns {
2080 cells: HashMap<NodeId, (u32, u32)>,
2081 cols: Vec<(NodeId, u32, u32)>,
2083 col_index: HashMap<NodeId, usize>,
2085 width: u32,
2086}
2087
2088#[derive(Default)]
2093struct Cover {
2094 row: u32,
2096 runs: BTreeMap<u32, (u32, u32)>,
2099 blocks: BTreeMap<u32, u32>,
2103 ends: BinaryHeap<Reverse<(u32, u32)>>,
2106}
2107
2108impl Cover {
2109 fn advance(&mut self, row: u32) {
2111 while let Some(&Reverse((until, start))) = self.ends.peek() {
2112 if until > row {
2113 break;
2114 }
2115 self.ends.pop();
2116 if let Some(&(end, u)) = self.runs.get(&start)
2117 && u == until
2118 {
2119 self.runs.remove(&start);
2120 let (&bs, &be) = self
2121 .blocks
2122 .range(..=start)
2123 .next_back()
2124 .expect("a run's block");
2125 self.blocks.remove(&bs);
2126 if bs < start {
2127 self.blocks.insert(bs, start);
2128 }
2129 if end < be {
2130 self.blocks.insert(end, be);
2131 }
2132 }
2133 }
2134 }
2135
2136 fn free(&self, x: u32) -> u32 {
2138 match self.blocks.range(..=x).next_back() {
2139 Some((_, &end)) if end > x => end,
2140 _ => x,
2141 }
2142 }
2143
2144 fn add(&mut self, start: u32, end: u32, until: u32) {
2147 let mut over: Vec<(u32, u32, u32)> = Vec::new();
2148 if let Some((&rs, &(re, ru))) = self.runs.range(..start).next_back()
2149 && re > start
2150 {
2151 over.push((rs, re, ru));
2152 }
2153 over.extend(
2154 self.runs
2155 .range(start..end)
2156 .map(|(&rs, &(re, ru))| (rs, re, ru)),
2157 );
2158 let mut pieces = Vec::new();
2159 let mut at = start;
2160 for &(rs, re, ru) in &over {
2161 self.runs.remove(&rs);
2162 if rs < start {
2163 pieces.push((rs, start, ru));
2164 }
2165 let (os, oe) = (rs.max(start), re.min(end));
2166 if at < os {
2167 pieces.push((at, os, until));
2168 }
2169 pieces.push((os, oe, ru.max(until)));
2170 if re > end {
2171 pieces.push((end, re, ru));
2172 }
2173 at = oe;
2174 }
2175 if at < end {
2176 pieces.push((at, end, until));
2177 }
2178 for (ps, pe, pu) in pieces {
2179 self.runs.insert(ps, (pe, pu));
2180 self.ends.push(Reverse((pu, ps)));
2181 }
2182 let (mut bs, mut be) = (start, end);
2185 if let Some((&s, &e)) = self.blocks.range(..=start).next_back()
2186 && e >= start
2187 {
2188 bs = s;
2189 be = be.max(e);
2190 self.blocks.remove(&s);
2191 }
2192 while let Some((&s, &e)) = self.blocks.range(bs..=be).next() {
2193 self.blocks.remove(&s);
2194 be = be.max(e);
2195 }
2196 self.blocks.insert(bs, be);
2197 }
2198}
2199
2200#[derive(Clone, Copy)]
2203struct Place {
2204 index: u32,
2205 count: u32,
2206 type_index: u32,
2207 type_count: u32,
2208}
2209
2210fn case_insensitive_attr(name: &str) -> bool {
2213 matches!(
2214 name,
2215 "accept"
2216 | "accept-charset"
2217 | "align"
2218 | "alink"
2219 | "axis"
2220 | "bgcolor"
2221 | "charset"
2222 | "checked"
2223 | "clear"
2224 | "codetype"
2225 | "color"
2226 | "compact"
2227 | "declare"
2228 | "defer"
2229 | "dir"
2230 | "direction"
2231 | "disabled"
2232 | "enctype"
2233 | "face"
2234 | "frame"
2235 | "hreflang"
2236 | "http-equiv"
2237 | "lang"
2238 | "language"
2239 | "link"
2240 | "media"
2241 | "method"
2242 | "multiple"
2243 | "nohref"
2244 | "noresize"
2245 | "noshade"
2246 | "nowrap"
2247 | "readonly"
2248 | "rel"
2249 | "rev"
2250 | "rules"
2251 | "scope"
2252 | "scrolling"
2253 | "selected"
2254 | "shape"
2255 | "target"
2256 | "text"
2257 | "type"
2258 | "valign"
2259 | "valuetype"
2260 | "vlink"
2261 )
2262}
2263
2264fn is_space_char(c: char) -> bool {
2265 matches!(c, ' ' | '\t' | '\n' | '\r' | '\x0C')
2266}
2267
2268impl<'a> Cx<'a> {
2269 fn new(doc: &'a Document, scope: Option<NodeId>, in_tree: NodeId, page: Option<Page>) -> Self {
2271 let (shadow, host) = match doc.shadow_roots.is_empty() {
2273 true => (NONE, NONE),
2274 false => {
2275 let root = doc.tree_root(in_tree);
2276 doc.shadow_host(root).map_or((NONE, NONE), |h| (root, h))
2277 }
2278 };
2279 Cx {
2280 doc,
2281 scope,
2282 shadow,
2283 host,
2284 page,
2285 pattern_budget: Cell::new(crate::pattern::SELECT_STEP_LIMIT),
2286 deadline: None,
2287 max_steps: u64::MAX,
2288 limited: false,
2289 steps: Cell::new(0),
2290 timed_out: Cell::new(false),
2291 places: RefCell::default(),
2292 of_places: RefCell::default(),
2293 has_seen: RefCell::default(),
2294 nested_seen: RefCell::default(),
2295 tables: RefCell::default(),
2296 }
2297 }
2298
2299 fn html_tag_of(&self, n: NodeId) -> Option<Tag> {
2300 self.doc
2301 .element(n)
2302 .filter(|e| e.ns == Ns::Html)
2303 .map(|e| e.tag)
2304 }
2305
2306 fn table_of_cell(&self, cell: NodeId) -> Option<NodeId> {
2309 if !matches!(self.html_tag_of(cell), Some(Tag::Td | Tag::Th)) {
2310 return None;
2311 }
2312 let tr = self
2313 .doc
2314 .parent(cell)
2315 .filter(|&p| self.html_tag_of(p) == Some(Tag::Tr))?;
2316 let p = self.doc.parent(tr)?;
2317 match self.html_tag_of(p)? {
2318 Tag::Table => Some(p),
2319 Tag::Thead | Tag::Tbody | Tag::Tfoot => self
2320 .doc
2321 .parent(p)
2322 .filter(|&t| self.html_tag_of(t) == Some(Tag::Table)),
2323 _ => None,
2324 }
2325 }
2326
2327 fn cell_columns(&self, cell: NodeId) -> Option<(Rc<Columns>, u32, u32)> {
2329 let table = self.table_of_cell(cell)?;
2330 let columns = self.columns(table);
2331 let &(x, n) = columns.cells.get(&cell)?;
2332 Some((columns, x, n))
2333 }
2334
2335 fn columns(&self, table: NodeId) -> Rc<Columns> {
2336 if let Some(c) = self.tables.borrow().get(&table) {
2337 return c.clone();
2338 }
2339 let c = Rc::new(self.lay_out(table));
2340 self.tables.borrow_mut().insert(table, c.clone());
2341 c
2342 }
2343
2344 fn span(&self, el: NodeId, name: &str, max: u32) -> u32 {
2347 self.attr(el, name)
2348 .and_then(parse_non_negative)
2349 .filter(|&n| n > 0)
2350 .map_or(1, |n| n.min(max))
2351 }
2352
2353 fn lay_out(&self, table: NodeId) -> Columns {
2358 let doc = self.doc;
2359 let mut out = Columns::default();
2360 let mut col_x = 0;
2361 let mut rows_started = false;
2362 let mut cover = Cover::default();
2363 for child in doc.children(table) {
2364 match self.html_tag_of(child) {
2365 Some(Tag::Colgroup) if !rows_started => {
2366 let mut has_cols = false;
2367 for c in doc.children(child) {
2368 if self.html_tag_of(c) == Some(Tag::Col) {
2369 has_cols = true;
2370 let n = self.span(c, "span", 1000);
2371 out.col_index.insert(c, out.cols.len());
2372 out.cols.push((c, col_x, n));
2373 col_x += n;
2374 }
2375 }
2376 if !has_cols {
2377 col_x += self.span(child, "span", 1000);
2378 }
2379 }
2380 Some(Tag::Tr) => {
2381 rows_started = true;
2382 self.lay_out_row(child, &mut cover, &mut out);
2383 }
2384 Some(Tag::Thead | Tag::Tbody | Tag::Tfoot) => {
2385 rows_started = true;
2386 cover = Cover::default();
2388 for r in doc.children(child) {
2389 if self.html_tag_of(r) == Some(Tag::Tr) {
2390 self.lay_out_row(r, &mut cover, &mut out);
2391 }
2392 }
2393 cover = Cover::default();
2394 }
2395 _ => {}
2396 }
2397 }
2398 out.width = out.width.max(col_x);
2399 out
2400 }
2401
2402 fn lay_out_row(&self, tr: NodeId, cover: &mut Cover, out: &mut Columns) {
2403 let row = cover.row;
2404 cover.advance(row);
2405 let mut x = 0;
2406 for cell in self.doc.children(tr) {
2407 if !matches!(self.html_tag_of(cell), Some(Tag::Td | Tag::Th)) {
2408 continue;
2409 }
2410 x = cover.free(x);
2411 let span = self.span(cell, "colspan", 1000);
2412 let until = match self.attr(cell, "rowspan").and_then(parse_non_negative) {
2413 Some(0) => u32::MAX,
2414 n => row.saturating_add(n.map_or(1, |n| n.min(65534))),
2415 };
2416 cover.add(x, x + span, until);
2417 out.cells.insert(cell, (x, span));
2418 x += span;
2419 out.width = out.width.max(x);
2420 }
2421 cover.row += 1;
2422 }
2423
2424 fn place(&self, el: NodeId) -> Option<Place> {
2426 if let Some(&p) = self.places.borrow().get(&el) {
2427 return Some(p);
2428 }
2429 let doc = self.doc;
2430 let parent = doc.parent(el)?;
2431 let kids: Vec<NodeId> = doc
2432 .children(parent)
2433 .filter(|&k| doc.element(k).is_some())
2434 .collect();
2435 let mut types: Vec<(NodeId, u32)> = Vec::new();
2442 let mut keyed = false;
2443 let mut by_tag: IdMap<Tag, usize> = IdMap::default();
2444 let mut by_name: HashMap<(u8, Tag, &str), usize> = HashMap::new();
2445 fn file<'d>(
2446 doc: &'d Document,
2447 by_tag: &mut IdMap<Tag, usize>,
2448 by_name: &mut HashMap<(u8, Tag, &'d str), usize>,
2449 e: &'d crate::dom::Element,
2450 t: usize,
2451 ) {
2452 if e.ns == Ns::Html && e.tag != Tag::Other {
2453 by_tag.insert(e.tag, t);
2454 } else {
2455 by_name.insert((e.ns as u8, e.tag, doc.element_name(e)), t);
2456 }
2457 }
2458 let mut of_type = Vec::with_capacity(kids.len());
2459 for &k in &kids {
2460 let e = doc.element(k).unwrap();
2461 let found = if !keyed {
2462 types
2463 .iter()
2464 .position(|&(rep, _)| same_type(doc, doc.element(rep).unwrap(), e))
2465 } else if e.ns == Ns::Html && e.tag != Tag::Other {
2466 by_tag.get(&e.tag).copied()
2467 } else {
2468 by_name
2469 .get(&(e.ns as u8, e.tag, doc.element_name(e)))
2470 .copied()
2471 };
2472 let t = match found {
2473 Some(t) => t,
2474 None => {
2475 types.push((k, 0));
2476 if keyed {
2477 file(doc, &mut by_tag, &mut by_name, e, types.len() - 1);
2478 } else if types.len() > 16 {
2479 keyed = true;
2480 for (i, &(rep, _)) in types.iter().enumerate() {
2481 let rep = doc.element(rep).unwrap();
2482 file(doc, &mut by_tag, &mut by_name, rep, i);
2483 }
2484 }
2485 types.len() - 1
2486 }
2487 };
2488 types[t].1 += 1;
2489 of_type.push((t, types[t].1));
2490 }
2491 let mut places = self.places.borrow_mut();
2492 places.reserve(kids.len());
2493 for (i, (&k, &(t, type_index))) in kids.iter().zip(&of_type).enumerate() {
2494 places.insert(
2495 k,
2496 Place {
2497 index: i as u32 + 1,
2498 count: kids.len() as u32,
2499 type_index,
2500 type_count: types[t].1,
2501 },
2502 );
2503 }
2504 places.get(&el).copied()
2505 }
2506
2507 fn of_place(&self, of: &SelectorList, el: NodeId) -> Option<(u32, u32)> {
2511 let key = std::ptr::from_ref(of) as usize;
2512 if let Some(&p) = self.of_places.borrow().get(&(key, el)) {
2513 return Some(p);
2514 }
2515 let doc = self.doc;
2516 let parent = doc.parent(el)?;
2517 let kids: Vec<NodeId> = doc
2518 .children(parent)
2519 .filter(|&k| doc.element(k).is_some() && of.0.iter().any(|c| self.complex(c, k, k)))
2520 .collect();
2521 let mut places = self.of_places.borrow_mut();
2522 for (i, &k) in kids.iter().enumerate() {
2523 places.insert((key, k), (i as u32 + 1, kids.len() as u32));
2524 }
2525 places.get(&(key, el)).copied()
2526 }
2527
2528 #[inline(never)]
2531 fn nth_by_place(&self, el: NodeId, a: i32, b: i32, last: bool, of_type: bool) -> Option<bool> {
2532 let pl = self.place(el)?;
2533 let (index, count) = if of_type {
2534 (pl.type_index, pl.type_count)
2535 } else {
2536 (pl.index, pl.count)
2537 };
2538 let index = if last { count - index + 1 } else { index };
2539 Some(nth_matches(a as i64, b as i64, index as i64))
2540 }
2541
2542 fn parent_element(&self, n: NodeId) -> Option<NodeId> {
2543 self.doc
2544 .parent(n)
2545 .filter(|&p| self.doc.element(p).is_some())
2546 }
2547
2548 fn prev_element(&self, n: NodeId) -> Option<NodeId> {
2549 let mut at = self.doc.prev_sibling(n);
2550 while let Some(p) = at {
2551 if self.doc.element(p).is_some() {
2552 return Some(p);
2553 }
2554 at = self.doc.prev_sibling(p);
2555 }
2556 None
2557 }
2558
2559 fn next_element(&self, n: NodeId) -> Option<NodeId> {
2560 let mut at = self.doc.next_sibling(n);
2561 while let Some(p) = at {
2562 if self.doc.element(p).is_some() {
2563 return Some(p);
2564 }
2565 at = self.doc.next_sibling(p);
2566 }
2567 None
2568 }
2569
2570 fn complex(&self, c: &Complex, el: NodeId, anchor: NodeId) -> bool {
2581 if let Some(Simple::Pseudo(Pseudo::Slotted(arg))) = c.parts[0].0.0.first() {
2582 return self.slotted(c, arg, el, anchor);
2583 }
2584 self.compound(&c.parts[0].0, el, anchor)
2586 && (c.parts.len() == 1 || self.complex_rest(c, el, anchor))
2587 }
2588
2589 #[cold]
2593 fn slotted(&self, c: &Complex, arg: &Compound, el: NodeId, anchor: NodeId) -> bool {
2594 if self.shadow == NONE || self.doc.element(el).is_none() {
2595 return false;
2596 }
2597 let mut slot = self.doc.assigned_slot(el);
2598 while let Some(s) = slot {
2599 if self.doc.tree_root(s) == self.shadow {
2600 break;
2601 }
2602 slot = self.doc.assigned_slot(s);
2603 }
2604 let Some(slot) = slot else {
2605 return false;
2606 };
2607 self.simples(&arg.0, el, anchor)
2608 && self.compound_of(&c.parts[0].0.0[1..], slot, anchor)
2609 && (c.parts.len() == 1 || self.complex_rest(c, slot, anchor))
2610 }
2611
2612 #[inline(never)]
2614 fn complex_rest(&self, c: &Complex, el: NodeId, anchor: NodeId) -> bool {
2615 let parts = &c.parts;
2616 if let [(_, combinator), (left, _)] = parts.as_slice() {
2619 let mut at = self.step(*combinator, el);
2620 while let Some(p) = at {
2621 if self.compound(left, p, anchor) {
2622 return true;
2623 }
2624 if matches!(combinator, Combinator::Child | Combinator::NextSibling) {
2625 return false;
2626 }
2627 at = self.next_step(*combinator, el, p);
2628 }
2629 return false;
2630 }
2631 let mut inline = [0; 16];
2633 let mut spilled;
2634 let matched: &mut [NodeId] = if parts.len() <= inline.len() {
2635 &mut inline
2636 } else {
2637 spilled = vec![0; parts.len()];
2638 &mut spilled
2639 };
2640 matched[0] = el;
2641 let Some(next) = self.step(parts[0].1, el) else {
2642 return false;
2643 };
2644 let fence = matches!(parts.last(), Some((Compound(s), _)) if matches!(s.as_slice(), [Simple::Anchor]))
2650 .then(|| (anchor, self.step(Combinator::Child, anchor)));
2651 let fenced = |i: usize, at: NodeId| {
2652 i + 1 < parts.len() && fence.is_some_and(|(a, up)| at == a || Some(at) == up)
2653 };
2654 let (mut i, mut at) = (1, next);
2655 loop {
2656 let mut fail = if fenced(i, at) {
2657 Fail::exhausted(parts[i - 1].1)
2658 } else if !self.compound(&parts[i].0, at, anchor) {
2659 Fail::Sibling
2660 } else if i + 1 == parts.len() {
2661 return true;
2662 } else {
2663 let combinator = parts[i].1;
2664 match self.step(combinator, at) {
2665 Some(next) => {
2666 matched[i] = at;
2667 (i, at) = (i + 1, next);
2668 continue;
2669 }
2670 None => Fail::exhausted(combinator),
2671 }
2672 };
2673 loop {
2675 if i == 0 || fail == Fail::Global {
2676 return false;
2677 }
2678 i -= 1;
2679 let combinator = parts[i].1;
2680 let retry = match (fail, combinator) {
2681 (_, Combinator::Child) => {
2682 fail = Fail::Descendant;
2683 false
2684 }
2685 (_, Combinator::NextSibling)
2686 | (Fail::Descendant, Combinator::SubsequentSibling) => false,
2687 _ => true,
2688 };
2689 if retry {
2690 if let Some(next) = self.next_step(combinator, matched[i], at) {
2691 (i, at) = (i + 1, next);
2692 break;
2693 }
2694 fail = Fail::exhausted(combinator);
2695 }
2696 at = matched[i];
2697 }
2698 }
2699 }
2700
2701 #[inline]
2704 fn step(&self, combinator: Combinator, el: NodeId) -> Option<NodeId> {
2705 if el == self.host {
2708 return None;
2709 }
2710 match combinator {
2711 Combinator::Child | Combinator::Descendant => {
2712 let parent = self.doc.parent(el);
2713 if parent == Some(self.shadow) {
2714 Some(self.host)
2715 } else {
2716 parent
2717 }
2718 }
2719 Combinator::NextSibling | Combinator::SubsequentSibling => self.prev_element(el),
2720 Combinator::Column => self.col_after(el, None),
2721 Combinator::None => None,
2722 }
2723 }
2724
2725 fn next_step(&self, combinator: Combinator, origin: NodeId, prev: NodeId) -> Option<NodeId> {
2729 match combinator {
2730 Combinator::Column => self.col_after(origin, Some(prev)),
2731 _ => self.step(combinator, prev),
2732 }
2733 }
2734
2735 fn col_after(&self, cell: NodeId, prev: Option<NodeId>) -> Option<NodeId> {
2738 let (t, x, n) = self.cell_columns(cell)?;
2739 let i = match prev {
2740 None => t.cols.partition_point(|&(_, cx, cn)| cx + cn <= x),
2741 Some(p) => t.col_index.get(&p)? + 1,
2742 };
2743 t.cols
2744 .get(i)
2745 .filter(|&&(_, cx, _)| cx < x + n)
2746 .map(|&(col, ..)| col)
2747 }
2748
2749 #[cold]
2753 #[inline(never)]
2754 fn out_of_time(&self) -> bool {
2755 let steps = self.steps.get().saturating_add(1);
2756 self.steps.set(steps);
2757 if steps > self.max_steps
2758 || steps.is_multiple_of(1024) && self.deadline.is_some_and(|d| Instant::now() >= d)
2759 {
2760 self.timed_out.set(true);
2761 }
2762 self.timed_out.get()
2763 }
2764
2765 fn limit(&mut self, options: &MatchOptions<'_>) {
2767 self.deadline = deadline(options);
2768 self.max_steps = options.max_steps.unwrap_or(u64::MAX);
2769 self.limited = self.deadline.is_some() || options.max_steps.is_some();
2770 }
2771
2772 fn compound(&self, compound: &Compound, el: NodeId, anchor: NodeId) -> bool {
2773 self.compound_of(&compound.0, el, anchor)
2774 }
2775
2776 fn compound_of(&self, simples: &[Simple], el: NodeId, anchor: NodeId) -> bool {
2777 if el == self.host
2781 && !matches!(simples, [Simple::Anchor])
2782 && (simples.is_empty()
2783 || !simples.iter().all(|s| {
2784 matches!(
2785 s,
2786 Simple::Pseudo(
2787 Pseudo::Host(_)
2788 | Pseudo::HostContext(_)
2789 | Pseudo::Is(_)
2790 | Pseudo::Where(_)
2791 )
2792 )
2793 }))
2794 {
2795 return false;
2796 }
2797 self.simples(simples, el, anchor)
2798 }
2799
2800 fn simples(&self, simples: &[Simple], el: NodeId, anchor: NodeId) -> bool {
2803 if self.limited && self.out_of_time() {
2804 return false;
2805 }
2806 if matches!(simples, [Simple::Anchor]) {
2807 return el == anchor;
2808 }
2809 let Some(e) = self.doc.element(el) else {
2810 return false;
2811 };
2812 simples.iter().all(|s| match s {
2813 Simple::Type { lower, exact, tag } => {
2814 if e.ns == Ns::Html {
2815 if *tag != Tag::Other || e.tag != Tag::Other {
2816 e.tag == *tag
2817 } else {
2818 self.doc.element_name(e) == lower
2819 }
2820 } else if e.ns == Ns::Xml {
2821 xml_local(self.doc.element_name(e)).eq_ignore_ascii_case(lower)
2824 } else {
2825 self.doc.element_name(e) == exact
2826 }
2827 }
2828 Simple::Id(id) => self.attr(el, "id").is_some_and(|v| self.quirks_eq(v, id)),
2829 Simple::Class(class) => self.attr(el, "class").is_some_and(|v| {
2830 v.split(is_space_char)
2831 .any(|c| !c.is_empty() && self.quirks_eq(c, class))
2832 }),
2833 Simple::Attr(a) => self.attr_matches(el, e.ns, a),
2834 Simple::Pseudo(p) => self.pseudo(p, el, anchor),
2835 Simple::Anchor => el == anchor,
2836 Simple::Ns(ns) => e.ns == *ns,
2837 })
2838 }
2839
2840 fn quirks_eq(&self, a: &str, b: &str) -> bool {
2841 if self.doc.quirks() == Quirks::Quirks {
2842 a.eq_ignore_ascii_case(b)
2843 } else {
2844 a == b
2845 }
2846 }
2847
2848 fn lang(&self, el: NodeId) -> Option<&str> {
2851 let mut at = Some(el);
2852 while let Some(n) = at {
2853 let mut plain = None;
2854 for (ns, name, value) in self.doc.attrs(n) {
2855 match (ns, name) {
2856 (AttrNs::Xml, "lang") => return Some(value),
2857 (AttrNs::None, "lang") => plain = Some(value),
2858 _ => {}
2859 }
2860 }
2861 if plain.is_some() {
2862 return plain;
2863 }
2864 at = self.doc.parent(n);
2865 }
2866 None
2867 }
2868
2869 fn is_rtl(&self, el: NodeId) -> bool {
2874 let mut at = Some(el);
2875 while let Some(n) = at {
2876 let Some(e) = self.doc.element(n) else {
2877 return false;
2878 };
2879 if e.ns == Ns::Html {
2880 match self.dir(n).as_deref() {
2881 Some("ltr") => return false,
2882 Some("rtl") => return true,
2883 Some("auto") => return self.auto_rtl(n),
2884 _ if self.doc.lower_name(n) == Some("bdi") => return self.auto_rtl(n),
2885 _ => {}
2886 }
2887 }
2888 at = self.doc.parent(n);
2889 }
2890 false
2891 }
2892
2893 fn dir(&self, el: NodeId) -> Option<String> {
2895 self.attr(el, "dir")
2896 .map(|d| d.to_ascii_lowercase())
2897 .filter(|d| matches!(d.as_str(), "ltr" | "rtl" | "auto"))
2898 }
2899
2900 fn auto_rtl(&self, el: NodeId) -> bool {
2905 let tag = self.doc.element(el).map(|e| e.tag);
2906 if tag == Some(Tag::Textarea) {
2907 return first_strong_rtl(&self.doc.text(el)).unwrap_or(false);
2908 }
2909 if tag == Some(Tag::Input) {
2910 let text_field = self.attr(el, "type").is_none_or(|t| {
2911 matches!(
2912 t.to_ascii_lowercase().as_str(),
2913 "text" | "search" | "tel" | "url" | "email"
2914 )
2915 });
2916 return text_field
2917 && first_strong_rtl(self.attr(el, "value").unwrap_or("")).unwrap_or(false);
2918 }
2919 let mut stack: Vec<NodeId> = self.doc.children(el).collect();
2920 stack.reverse();
2921 while let Some(n) = stack.pop() {
2922 match self.doc.kind(n) {
2923 crate::Kind::Text(t) => {
2924 if let Some(rtl) = first_strong_rtl(t) {
2925 return rtl;
2926 }
2927 }
2928 crate::Kind::Element { ns, .. } => {
2929 let skip = ns == Ns::Html
2930 && (self.dir(n).is_some()
2931 || matches!(
2932 self.doc.element(n).map(|e| e.tag),
2933 Some(Tag::Script | Tag::Style | Tag::Textarea)
2934 )
2935 || self.doc.lower_name(n) == Some("bdi"));
2936 if !skip {
2937 let at = stack.len();
2938 stack.extend(self.doc.children(n));
2939 stack[at..].reverse();
2940 }
2941 }
2942 _ => {}
2943 }
2944 }
2945 false
2946 }
2947
2948 fn input_type(&self, el: NodeId, types: &[&str]) -> bool {
2950 self.attr(el, "type")
2951 .is_some_and(|t| types.iter().any(|w| t.eq_ignore_ascii_case(w)))
2952 }
2953
2954 fn html_tag(&self, n: NodeId, tag: Tag) -> bool {
2955 self.doc
2956 .element(n)
2957 .is_some_and(|e| e.ns == Ns::Html && e.tag == tag)
2958 }
2959
2960 fn html_named(&self, n: NodeId, name: &str) -> bool {
2961 self.doc.element(n).is_some_and(|e| e.ns == Ns::Html)
2962 && self.doc.lower_name(n) == Some(name)
2963 }
2964
2965 fn tree_of(&self, el: NodeId) -> Vec<NodeId> {
2971 let mut root = el;
2972 while let Some(p) = self.doc.parent(root) {
2973 root = p;
2974 }
2975 let (mut out, mut stack) = (Vec::new(), vec![root]);
2976 while let Some(n) = stack.pop() {
2977 out.push(n);
2978 let at = stack.len();
2979 stack.extend(self.doc.children(n));
2980 stack[at..].reverse();
2981 }
2982 out
2983 }
2984
2985 fn form_owner(&self, el: NodeId) -> Option<NodeId> {
2988 if let Some(id) = self.attr(el, "form") {
2989 return self
2990 .tree_of(el)
2991 .into_iter()
2992 .find(|&n| self.doc.element(n).is_some() && self.attr(n, "id") == Some(id))
2993 .filter(|&f| self.html_tag(f, Tag::Form));
2994 }
2995 let mut at = self.parent_element(el);
2996 while let Some(p) = at {
2997 if self.html_tag(p, Tag::Form) {
2998 return Some(p);
2999 }
3000 at = self.parent_element(p);
3001 }
3002 None
3003 }
3004
3005 fn submit_button(&self, el: NodeId, tag: Tag) -> bool {
3006 match tag {
3007 Tag::Button => self.attr(el, "type").is_none_or(|t| {
3009 !t.eq_ignore_ascii_case("reset") && !t.eq_ignore_ascii_case("button")
3010 }),
3011 Tag::Input => self.input_type(el, &["submit", "image"]),
3012 _ => false,
3013 }
3014 }
3015
3016 fn default_button(&self, el: NodeId, tag: Tag) -> bool {
3019 if !self.submit_button(el, tag) {
3020 return false;
3021 }
3022 let Some(form) = self.form_owner(el) else {
3023 return false;
3024 };
3025 self.tree_of(el).into_iter().find(|&n| {
3026 self.doc.element(n).is_some_and(|e| {
3027 e.ns == Ns::Html && self.submit_button(n, e.tag) && self.form_owner(n) == Some(form)
3028 })
3029 }) == Some(el)
3030 }
3031
3032 fn radio_group_unchecked(&self, el: NodeId) -> bool {
3036 if self.attr(el, "checked").is_some() {
3037 return false;
3038 }
3039 let Some(name) = self.attr(el, "name").filter(|n| !n.is_empty()) else {
3040 return true;
3041 };
3042 let form = self.form_owner(el);
3043 !self.tree_of(el).into_iter().any(|n| {
3044 self.html_tag(n, Tag::Input)
3045 && self.input_type(n, &["radio"])
3046 && self.attr(n, "name") == Some(name)
3047 && self.attr(n, "checked").is_some()
3048 && self.form_owner(n) == form
3049 })
3050 }
3051
3052 fn in_range(&self, el: NodeId) -> Option<bool> {
3057 let typ = self.attr(el, "type")?.to_ascii_lowercase();
3058 let read = |name: &str| self.attr(el, name).and_then(|v| input_number(&typ, v));
3059 let (min, max) = match typ.as_str() {
3060 "range" => (read("min").or(Some(0.0)), read("max").or(Some(100.0))),
3061 "number" | "date" | "month" | "week" | "time" | "datetime-local" => {
3062 (read("min"), read("max"))
3063 }
3064 _ => return None,
3065 };
3066 if min.is_none() && max.is_none() {
3067 return None;
3068 }
3069 let in_datalist = {
3072 let mut at = self.parent_element(el);
3073 let mut found = false;
3074 while let Some(p) = at {
3075 if self.html_named(p, "datalist") {
3076 found = true;
3077 break;
3078 }
3079 at = self.parent_element(p);
3080 }
3081 found
3082 };
3083 if self.disabled(el, Tag::Input)
3084 || (typ != "range" && self.attr(el, "readonly").is_some())
3085 || in_datalist
3086 {
3087 return None;
3088 }
3089 if typ == "range" {
3090 return Some(true);
3091 }
3092 let Some(value) = read("value") else {
3093 return Some(true);
3094 };
3095 Some(match (min, max) {
3096 (Some(lo), Some(hi)) if typ == "time" && lo > hi => value >= lo || value <= hi,
3098 _ => min.is_none_or(|lo| value >= lo) && max.is_none_or(|hi| value <= hi),
3099 })
3100 }
3101
3102 fn valid(&self, el: NodeId, tag: Tag) -> Option<bool> {
3106 match tag {
3107 Tag::Form => Some(!self.tree_of(el).into_iter().any(|n| {
3108 self.doc.element(n).is_some_and(|e| e.ns == Ns::Html)
3109 && self.form_owner(n) == Some(el)
3110 && self.control_valid(n) == Some(false)
3111 })),
3112 Tag::Fieldset => {
3113 let mut stack: Vec<NodeId> = self.doc.children(el).collect();
3114 while let Some(n) = stack.pop() {
3115 if self.control_valid(n) == Some(false) {
3116 return Some(false);
3117 }
3118 stack.extend(self.doc.children(n));
3119 }
3120 Some(true)
3121 }
3122 _ => self.control_valid(el),
3123 }
3124 }
3125
3126 fn control_valid(&self, el: NodeId) -> Option<bool> {
3132 let e = self.doc.element(el)?;
3133 if e.ns != Ns::Html || self.disabled(el, e.tag) || self.in_datalist(el) {
3134 return None;
3135 }
3136 let required = self.attr(el, "required").is_some();
3137 match e.tag {
3138 Tag::Input => {
3139 let typ = input_type_state(self.attr(el, "type"));
3140 if matches!(typ, "hidden" | "reset" | "button")
3141 || (readonly_applies(typ) && self.attr(el, "readonly").is_some())
3142 {
3143 return None;
3144 }
3145 Some(self.input_valid(el, typ, required))
3146 }
3147 Tag::Textarea => {
3148 if self.attr(el, "readonly").is_some() {
3149 return None;
3150 }
3151 Some(!required || !self.doc.text(el).is_empty())
3152 }
3153 Tag::Select => Some(!required || self.select_has_value(el)),
3154 Tag::Button => self.submit_button(el, Tag::Button).then_some(true),
3155 _ => None,
3156 }
3157 }
3158
3159 fn input_valid(&self, el: NodeId, typ: &str, required: bool) -> bool {
3160 match typ {
3161 "checkbox" => !required || self.attr(el, "checked").is_some(),
3162 "radio" => !self.radio_value_missing(el),
3163 "file" => !required,
3165 "submit" | "image" | "color" | "range" => true,
3166 _ => {
3167 let value = sanitized(
3168 typ,
3169 self.attr(el, "value").unwrap_or(""),
3170 self.attr(el, "multiple").is_some(),
3171 );
3172 if value.is_empty() {
3173 return !required;
3174 }
3175 let multiple = typ == "email" && self.attr(el, "multiple").is_some();
3176 if !self.pattern_fits(el, typ, &value, multiple) {
3177 return false;
3178 }
3179 match typ {
3180 "email" if self.attr(el, "multiple").is_some() => {
3181 value.split(',').all(valid_email)
3182 }
3183 "email" => valid_email(&value),
3184 "url" => url::Url::parse(&value).is_ok(),
3185 "number" | "date" | "month" | "week" | "time" | "datetime-local" => {
3186 self.in_range(el) != Some(false) && self.step_fits(el, typ, &value)
3187 }
3188 _ => true,
3189 }
3190 }
3191 }
3192 }
3193
3194 fn pattern_fits(&self, el: NodeId, typ: &str, value: &str, multiple: bool) -> bool {
3198 if !matches!(
3199 typ,
3200 "text" | "search" | "tel" | "url" | "email" | "password"
3201 ) {
3202 return true;
3203 }
3204 let Some(pattern) = self.attr(el, "pattern").and_then(Pattern::compile) else {
3205 return true;
3206 };
3207 if multiple {
3208 value
3209 .split(',')
3210 .all(|v| pattern.matches(v, &self.pattern_budget))
3211 } else {
3212 pattern.matches(value, &self.pattern_budget)
3213 }
3214 }
3215
3216 fn step_fits(&self, el: NodeId, typ: &str, value: &str) -> bool {
3219 let (default, scale) = match typ {
3220 "week" => (1.0, 7.0),
3221 "time" | "datetime-local" => (60.0, 1000.0),
3222 _ => (1.0, 1.0),
3223 };
3224 let step = match self.attr(el, "step") {
3225 Some(s) if s.eq_ignore_ascii_case("any") => return true,
3226 Some(s) => parse_float_value(s).filter(|&s| s > 0.0).unwrap_or(default),
3227 None => default,
3228 };
3229 let (Some(value), Some(base)) = (
3230 input_number(typ, value),
3231 self.attr(el, "min").and_then(|m| input_number(typ, m)),
3232 ) else {
3233 return true;
3234 };
3235 let steps = (value - base) / (step * scale);
3236 (steps - steps.round()).abs() < 1e-9
3237 }
3238
3239 fn radio_value_missing(&self, el: NodeId) -> bool {
3241 let Some(name) = self.attr(el, "name").filter(|n| !n.is_empty()) else {
3242 return self.attr(el, "required").is_some() && self.attr(el, "checked").is_none();
3243 };
3244 let form = self.form_owner(el);
3245 let group: Vec<NodeId> = self
3246 .tree_of(el)
3247 .into_iter()
3248 .filter(|&n| {
3249 self.html_tag(n, Tag::Input)
3250 && self.input_type(n, &["radio"])
3251 && self.attr(n, "name") == Some(name)
3252 && self.form_owner(n) == form
3253 })
3254 .collect();
3255 group.iter().any(|&n| self.attr(n, "required").is_some())
3256 && group.iter().all(|&n| self.attr(n, "checked").is_none())
3257 }
3258
3259 fn select_has_value(&self, el: NodeId) -> bool {
3263 let mut options = Vec::new();
3264 let mut stack: Vec<NodeId> = self.doc.children(el).collect();
3265 stack.reverse();
3266 while let Some(n) = stack.pop() {
3267 if self.html_tag(n, Tag::Option) {
3268 options.push(n);
3269 } else if self.html_tag(n, Tag::Optgroup) {
3270 let at = stack.len();
3271 stack.extend(self.doc.children(n));
3272 stack[at..].reverse();
3273 }
3274 }
3275 let marked = |n: &&NodeId| self.attr(**n, "selected").is_some();
3276 let multiple = self.attr(el, "multiple").is_some();
3277 let size = self
3278 .attr(el, "size")
3279 .and_then(parse_non_negative)
3280 .filter(|&s| s > 0)
3281 .unwrap_or(if multiple { 4 } else { 1 });
3282 if multiple {
3283 return options.iter().any(|n| marked(&n));
3284 }
3285 let selected = options.iter().rev().find(marked).or_else(|| {
3288 options
3289 .iter()
3290 .filter(|_| size == 1)
3291 .find(|&&n| self.attr(n, "disabled").is_none() && !self.disabled(n, Tag::Option))
3292 });
3293 let Some(&selected) = selected else {
3294 return false;
3295 };
3296 let placeholder = size == 1
3297 && options.first() == Some(&selected)
3298 && self.doc.parent(selected) == Some(el)
3299 && self.option_value(selected).is_empty();
3300 !placeholder
3301 }
3302
3303 fn option_value(&self, el: NodeId) -> String {
3304 match self.attr(el, "value") {
3305 Some(v) => v.to_string(),
3306 None => self
3307 .doc
3308 .text(el)
3309 .split_ascii_whitespace()
3310 .collect::<Vec<_>>()
3311 .join(" "),
3312 }
3313 }
3314
3315 fn in_datalist(&self, el: NodeId) -> bool {
3316 let mut at = self.parent_element(el);
3317 while let Some(p) = at {
3318 if self.html_named(p, "datalist") {
3319 return true;
3320 }
3321 at = self.parent_element(p);
3322 }
3323 false
3324 }
3325
3326 fn attr(&self, el: NodeId, name: &str) -> Option<&str> {
3327 self.doc
3328 .attrs(el)
3329 .find(|(ns, n, _)| *ns == AttrNs::None && *n == name)
3330 .map(|(_, _, v)| v)
3331 }
3332
3333 fn attr_matches(&self, el: NodeId, ns: Ns, a: &AttrSelector) -> bool {
3334 let doc = self.doc;
3335 if ns == Ns::Xml {
3336 return self.xml_attr_matches(el, a);
3337 }
3338 let html = ns == Ns::Html;
3339 let insensitive = match a.case {
3340 Case::Insensitive => true,
3341 Case::Sensitive => false,
3342 Case::Default => html && case_insensitive_attr(&a.lower),
3343 };
3344 let want = if html { &a.lower } else { &a.exact };
3345 doc.attrs_of(el).iter().any(|attr| {
3348 let name = doc.written_name(ns, attr);
3350 let name = match attr.ns {
3353 AttrNs::None => name,
3354 _ => name.split_once(':').map_or(name, |(_, local)| local),
3355 };
3356 let in_ns = match a.in_ns {
3357 Some(ns) => attr.ns == ns,
3358 None => attr.ns == AttrNs::None || a.any_ns,
3359 };
3360 in_ns
3361 && name == want.as_str()
3362 && (a.op == AttrOp::Exists
3363 || value_matches(a.op, doc.str(attr.value), &a.value, insensitive))
3364 })
3365 }
3366
3367 fn xml_attr_matches(&self, el: NodeId, a: &AttrSelector) -> bool {
3371 let doc = self.doc;
3372 let range = doc
3373 .element(el)
3374 .map_or(0..0, |e| e.attrs.start as usize..e.attrs.end as usize);
3375 let attrs = &doc.attrs[range];
3376 let local = |attr: &crate::dom::Attr| xml_local(doc.str(attr.name));
3377 let found = attrs
3378 .iter()
3379 .find(|attr| local(attr) == a.exact)
3380 .or_else(|| {
3381 attrs
3382 .iter()
3383 .find(|attr| local(attr).eq_ignore_ascii_case(&a.lower))
3384 });
3385 let insensitive = a.case == Case::Insensitive;
3386 found.is_some_and(|attr| {
3387 a.op == AttrOp::Exists
3388 || value_matches(a.op, doc.str(attr.value), &a.value, insensitive)
3389 })
3390 }
3391
3392 fn pseudo(&self, p: &Pseudo, el: NodeId, anchor: NodeId) -> bool {
3393 let doc = self.doc;
3394 let e = doc.element(el).expect("an element");
3395 let html = e.ns == Ns::Html;
3396 let tag = if html { e.tag } else { Tag::Other };
3397 match p {
3398 Pseudo::Not(list) => !list.0.iter().any(|c| self.nested(c, el, anchor)),
3399 Pseudo::Is(list) | Pseudo::Where(list) => {
3400 list.0.iter().any(|c| self.nested(c, el, anchor))
3401 }
3402 Pseudo::Has(list) => list.0.iter().any(|c| self.has(c, el)),
3403 Pseudo::Nth {
3404 a,
3405 b,
3406 last,
3407 of_type,
3408 of,
3409 } => {
3410 let same = |other: NodeId| {
3411 if *of_type {
3412 same_type(doc, doc.element(other).unwrap(), e)
3413 } else if let Some(of) = of {
3414 of.0.iter().any(|c| self.complex(c, other, other))
3415 } else {
3416 true
3417 }
3418 };
3419 if !same(el) {
3420 return false;
3421 }
3422 if let Some(of) = of
3426 && let Some((index, count)) = self.of_place(of, el)
3427 {
3428 let index = if *last { count - index + 1 } else { index };
3429 return nth_matches(*a as i64, *b as i64, index as i64);
3430 }
3431 if *a > 0
3432 && let Some(m) = self.nth_by_place(el, *a, *b, *last, *of_type)
3433 {
3434 return m;
3435 }
3436 let mut walked = 0;
3440 let mut index = 1i64;
3441 let mut at = if *last {
3442 self.next_element(el)
3443 } else {
3444 self.prev_element(el)
3445 };
3446 while let Some(s) = at {
3447 walked += 1;
3448 if walked > 32
3449 && let Some(m) = self.nth_by_place(el, *a, *b, *last, *of_type)
3450 {
3451 return m;
3452 }
3453 if same(s) {
3454 index += 1;
3455 if *a <= 0 && index > *b as i64 {
3459 return false;
3460 }
3461 }
3462 at = if *last {
3463 self.next_element(s)
3464 } else {
3465 self.prev_element(s)
3466 };
3467 }
3468 nth_matches(*a as i64, *b as i64, index)
3469 }
3470 Pseudo::Only { of_type } => {
3471 let same =
3472 |other: NodeId| !*of_type || same_type(doc, doc.element(other).unwrap(), e);
3473 let mut walked = 0;
3476 for step in [Self::prev_element, Self::next_element] {
3477 let mut at = step(self, el);
3478 while let Some(s) = at {
3479 walked += 1;
3480 if walked > 32
3481 && let Some(pl) = self.place(el)
3482 {
3483 return pl.type_count == 1;
3484 }
3485 if same(s) {
3486 return false;
3487 }
3488 at = step(self, s);
3489 }
3490 }
3491 true
3492 }
3493 Pseudo::Empty => doc.children(el).all(|c| {
3494 matches!(
3495 doc.nodes[c as usize].data,
3496 Data::Comment(_) | Data::ProcessingInstruction { .. }
3497 ) || matches!(doc.kind(c), crate::Kind::Text(t) if t.is_empty())
3498 }),
3499 Pseudo::Root => doc
3500 .parent(el)
3501 .is_some_and(|p| matches!(doc.nodes[p as usize].data, Data::Document)),
3502 Pseudo::Scope => match self.scope {
3503 Some(s) if doc.element(s).is_some() => el == s,
3504 _ => doc
3505 .parent(el)
3506 .is_some_and(|p| matches!(doc.nodes[p as usize].data, Data::Document)),
3507 },
3508 Pseudo::AnyLink => matches!(tag, Tag::A | Tag::Area) && self.attr(el, "href").is_some(),
3509 Pseudo::Target => self.page.as_ref().is_some_and(|p| p.target == Some(el)),
3510 Pseudo::TargetWithin => self.page.as_ref().and_then(|p| p.target).is_some_and(|t| {
3511 let mut at = Some(t);
3512 while let Some(n) = at {
3513 if n == el {
3514 return true;
3515 }
3516 at = self.doc.parent(n);
3517 }
3518 false
3519 }),
3520 Pseudo::LocalLink => {
3521 matches!(tag, Tag::A | Tag::Area)
3522 && self.page.as_ref().is_some_and(|p| {
3523 self.attr(el, "href")
3524 .and_then(|href| p.base.join(href).ok())
3525 .is_some_and(|mut link| {
3526 link.set_fragment(None);
3527 link == p.url
3528 })
3529 })
3530 }
3531 Pseudo::Checked => match tag {
3532 Tag::Input => {
3533 self.attr(el, "checked").is_some()
3534 && self.attr(el, "type").is_some_and(|t| {
3535 t.eq_ignore_ascii_case("checkbox") || t.eq_ignore_ascii_case("radio")
3536 })
3537 }
3538 Tag::Option => self.attr(el, "selected").is_some(),
3539 _ => false,
3540 },
3541 Pseudo::Default => match tag {
3542 Tag::Input if self.input_type(el, &["checkbox", "radio"]) => {
3543 self.attr(el, "checked").is_some()
3544 }
3545 Tag::Option => self.attr(el, "selected").is_some(),
3546 Tag::Button | Tag::Input => self.default_button(el, tag),
3547 _ => false,
3548 },
3549 Pseudo::Indeterminate => match tag {
3550 Tag::Input if self.input_type(el, &["radio"]) => self.radio_group_unchecked(el),
3551 _ => self.html_named(el, "progress") && self.attr(el, "value").is_none(),
3553 },
3554 Pseudo::InRange => tag == Tag::Input && self.in_range(el) == Some(true),
3555 Pseudo::OutOfRange => tag == Tag::Input && self.in_range(el) == Some(false),
3556 Pseudo::Valid => self.valid(el, tag) == Some(true),
3557 Pseudo::Invalid => self.valid(el, tag) == Some(false),
3558 Pseudo::Disabled => self.disabled(el, tag),
3559 Pseudo::Enabled => self.form_control(tag) && !self.disabled(el, tag),
3560 Pseudo::Required => {
3561 matches!(tag, Tag::Input | Tag::Select | Tag::Textarea)
3562 && self.attr(el, "required").is_some()
3563 }
3564 Pseudo::Optional => {
3565 matches!(tag, Tag::Input | Tag::Select | Tag::Textarea)
3566 && self.attr(el, "required").is_none()
3567 }
3568 Pseudo::ReadWrite => self.read_write(el, tag),
3569 Pseudo::ReadOnly => !self.read_write(el, tag),
3570 Pseudo::PlaceholderShown => match tag {
3571 Tag::Input => {
3572 self.attr(el, "placeholder").is_some()
3573 && self.attr(el, "value").is_none_or(str::is_empty)
3574 }
3575 Tag::Textarea => self.attr(el, "placeholder").is_some() && doc.text(el).is_empty(),
3576 _ => false,
3577 },
3578 Pseudo::Blank => match tag {
3581 Tag::Input => {
3582 text_entry(input_type_state(self.attr(el, "type")))
3583 && self.attr(el, "value").is_none_or(str::is_empty)
3584 }
3585 Tag::Textarea => doc.text(el).is_empty(),
3586 _ => false,
3587 },
3588 Pseudo::Defined => {
3592 !(html
3593 && (self.attr(el, "is").is_some()
3594 || doc.lower_name(el).is_some_and(custom_element_name)))
3595 }
3596 Pseudo::Lang(ranges) => self.lang(el).is_some_and(|tag| {
3597 let tag = tag.to_ascii_lowercase();
3598 ranges.iter().any(|range| lang_matches(range, &tag))
3599 }),
3600 Pseudo::Dir(rtl) => self.is_rtl(el) == *rtl,
3601 Pseudo::Heading(levels) => {
3602 let level = match tag {
3603 Tag::H1 => 1,
3604 Tag::H2 => 2,
3605 Tag::H3 => 3,
3606 Tag::H4 => 4,
3607 Tag::H5 => 5,
3608 Tag::H6 => 6,
3609 _ => return false,
3610 };
3611 levels.is_empty() || levels.contains(&level)
3612 }
3613 Pseudo::Never | Pseudo::Element => false,
3614 Pseudo::Host(arg) => {
3615 el == self.host && arg.as_ref().is_none_or(|c| self.simples(&c.0, el, anchor))
3616 }
3617 Pseudo::HostContext(c) => {
3618 el == self.host && {
3619 let mut at = Some(el);
3620 while let Some(n) = at {
3621 if doc.element(n).is_some() && self.simples(&c.0, n, anchor) {
3622 return true;
3623 }
3624 at = doc.shadow_including_parent(n);
3625 }
3626 false
3627 }
3628 }
3629 Pseudo::Slotted(_) => false,
3631 Pseudo::NthCol { a, b, last } => self.cell_columns(el).is_some_and(|(t, x, n)| {
3634 let (lo, hi) = if *last {
3635 (t.width - (x + n) + 1, t.width - x)
3636 } else {
3637 (x + 1, x + n)
3638 };
3639 nth_in_range(*a as i64, *b as i64, lo as i64, hi as i64)
3640 }),
3641 }
3642 }
3643
3644 fn nested(&self, c: &Complex, el: NodeId, anchor: NodeId) -> bool {
3649 if c.parts.len() == 1 {
3650 return self.complex(c, el, anchor);
3651 }
3652 let key = (std::ptr::from_ref(c) as usize, el);
3653 if let Some(&known) = self.nested_seen.borrow().get(&key) {
3654 return known;
3655 }
3656 let found = self.complex(c, el, anchor);
3657 self.nested_seen.borrow_mut().insert(key, found);
3658 found
3659 }
3660
3661 fn has(&self, c: &Complex, el: NodeId) -> bool {
3664 let doc = self.doc;
3665 let first = c.parts[c.parts.len() - 2].1;
3668 if let [(compound, _), _] = c.parts.as_slice()
3672 && first != Combinator::Column
3673 {
3674 let key = std::ptr::from_ref(c) as usize;
3675 return match first {
3676 Combinator::Child => doc
3677 .children(el)
3678 .any(|k| doc.element(k).is_some() && self.compound(compound, k, el)),
3679 Combinator::NextSibling => self
3680 .next_element(el)
3681 .is_some_and(|s| self.compound(compound, s, el)),
3682 Combinator::SubsequentSibling => self.later_holds(key, compound, el),
3683 _ => self.below_holds(key, compound, el),
3684 };
3685 }
3686 let key = std::ptr::from_ref(c) as usize;
3690 let before = match first {
3691 Combinator::Descendant => doc.parent(el),
3692 Combinator::SubsequentSibling => self.prev_element(el),
3693 _ => None,
3694 };
3695 let remember = matches!(
3696 first,
3697 Combinator::Descendant | Combinator::SubsequentSibling
3698 );
3699 if before.is_some_and(|b| self.has_seen.borrow().get(&(key, b)) == Some(&false)) {
3700 self.has_seen.borrow_mut().insert((key, el), false);
3701 return false;
3702 }
3703 let found = self.has_anywhere(c, el, first);
3704 if remember {
3705 self.has_seen.borrow_mut().insert((key, el), found);
3706 }
3707 found
3708 }
3709
3710 fn has_anywhere(&self, c: &Complex, el: NodeId, first: Combinator) -> bool {
3713 let doc = self.doc;
3714 let mut stack: Vec<NodeId> = Vec::new();
3715 match first {
3716 Combinator::NextSibling | Combinator::SubsequentSibling => {
3720 let mut at = self.next_element(el);
3721 while let Some(s) = at {
3722 stack.push(s);
3723 if self.found_below(c, el, &mut stack) {
3724 return true;
3725 }
3726 at = self.next_element(s);
3727 }
3728 return false;
3729 }
3730 Combinator::Column => {
3732 let table = doc.parent(el).and_then(|g| doc.parent(g));
3733 if self.html_tag_of(el) == Some(Tag::Col)
3734 && let Some(t) = table.filter(|&t| self.html_tag_of(t) == Some(Tag::Table))
3735 {
3736 push_children_reversed(doc, t, &mut stack);
3737 }
3738 }
3739 _ => push_children_reversed(doc, el, &mut stack),
3740 }
3741 self.found_below(c, el, &mut stack)
3742 }
3743
3744 fn found_below(&self, c: &Complex, el: NodeId, stack: &mut Vec<NodeId>) -> bool {
3747 let doc = self.doc;
3748 while let Some(n) = stack.pop() {
3749 if doc.element(n).is_none() {
3750 continue;
3751 }
3752 if self.complex(c, n, el) {
3753 return true;
3754 }
3755 push_children_reversed(doc, n, stack);
3756 }
3757 false
3758 }
3759
3760 fn below_holds(&self, key: usize, compound: &Compound, el: NodeId) -> bool {
3764 let doc = self.doc;
3765 if self.has_seen.borrow().get(&(key, el)) == Some(&false) {
3766 return false;
3767 }
3768 let mut stack: Vec<(NodeId, bool)> = Vec::new();
3771 let at = stack.len();
3772 stack.extend(doc.children(el).map(|k| (k, false)));
3773 stack[at..].reverse();
3774 while let Some((n, done)) = stack.pop() {
3775 if done {
3776 self.has_seen.borrow_mut().insert((key, n), false);
3777 continue;
3778 }
3779 if doc.element(n).is_none() {
3780 continue;
3781 }
3782 let known = self.has_seen.borrow().get(&(key, n)).copied();
3783 if known == Some(false) {
3784 continue;
3785 }
3786 if known == Some(true) || self.compound(compound, n, el) {
3787 let mut seen = self.has_seen.borrow_mut();
3789 let mut up = Some(n);
3790 while let Some(u) = up {
3791 seen.insert((key, u), true);
3792 up = doc.parent(u).filter(|_| u != el);
3793 }
3794 return true;
3795 }
3796 stack.push((n, true));
3797 let at = stack.len();
3798 stack.extend(doc.children(n).map(|k| (k, false)));
3799 stack[at..].reverse();
3800 }
3801 false
3802 }
3803
3804 fn later_holds(&self, key: usize, compound: &Compound, el: NodeId) -> bool {
3807 let mut walked = Vec::new();
3808 let mut at = self.next_element(el);
3809 let found = loop {
3810 let Some(s) = at else { break false };
3811 if let Some(&known) = self.has_seen.borrow().get(&(key, s)) {
3812 break known;
3813 }
3814 walked.push(s);
3815 if self.compound(compound, s, el) {
3816 break true;
3817 }
3818 at = self.next_element(s);
3819 };
3820 let mut seen = self.has_seen.borrow_mut();
3821 for s in walked {
3822 seen.insert((key, s), found);
3823 }
3824 found
3825 }
3826
3827 fn form_control(&self, tag: Tag) -> bool {
3828 matches!(
3829 tag,
3830 Tag::Button
3831 | Tag::Input
3832 | Tag::Select
3833 | Tag::Textarea
3834 | Tag::Optgroup
3835 | Tag::Option
3836 | Tag::Fieldset
3837 )
3838 }
3839
3840 fn disabled(&self, el: NodeId, tag: Tag) -> bool {
3842 let doc = self.doc;
3843 match tag {
3844 Tag::Optgroup => self.attr(el, "disabled").is_some(),
3845 Tag::Option => {
3846 self.attr(el, "disabled").is_some()
3847 || self.parent_element(el).is_some_and(|p| {
3848 doc.element(p)
3849 .is_some_and(|e| e.ns == Ns::Html && e.tag == Tag::Optgroup)
3850 && self.attr(p, "disabled").is_some()
3851 })
3852 }
3853 Tag::Button | Tag::Input | Tag::Select | Tag::Textarea | Tag::Fieldset => {
3854 if self.attr(el, "disabled").is_some() {
3855 return true;
3856 }
3857 let mut child = el;
3860 let mut at = self.parent_element(el);
3861 while let Some(p) = at {
3862 let pe = doc.element(p).unwrap();
3863 if pe.ns == Ns::Html
3864 && pe.tag == Tag::Fieldset
3865 && self.attr(p, "disabled").is_some()
3866 {
3867 let first_legend = doc.children(p).find(|&c| {
3868 doc.element(c).is_some_and(|e| {
3869 e.ns == Ns::Html && doc.element_name(e) == "legend"
3870 })
3871 });
3872 if first_legend != Some(child) {
3873 return true;
3874 }
3875 }
3876 child = p;
3877 at = self.parent_element(p);
3878 }
3879 false
3880 }
3881 _ => false,
3882 }
3883 }
3884
3885 fn read_write(&self, el: NodeId, tag: Tag) -> bool {
3886 match tag {
3887 Tag::Input => {
3888 let typ = self.attr(el, "type").unwrap_or("text").to_ascii_lowercase();
3889 let mutable = matches!(
3890 typ.as_str(),
3891 "text"
3892 | "search"
3893 | "url"
3894 | "tel"
3895 | "email"
3896 | "password"
3897 | "date"
3898 | "month"
3899 | "week"
3900 | "time"
3901 | "datetime-local"
3902 | "number"
3903 | ""
3904 );
3905 mutable && self.attr(el, "readonly").is_none() && !self.disabled(el, tag)
3906 }
3907 Tag::Textarea => self.attr(el, "readonly").is_none() && !self.disabled(el, tag),
3908 _ => self.editable(el),
3909 }
3910 }
3911
3912 fn editable(&self, el: NodeId) -> bool {
3914 let mut at = Some(el);
3915 while let Some(n) = at {
3916 if let Some(v) = self.attr(n, "contenteditable") {
3917 return !v.eq_ignore_ascii_case("false");
3918 }
3919 at = self.parent_element(n);
3920 }
3921 false
3922 }
3923}
3924
3925fn same_type(doc: &Document, a: &crate::dom::Element, b: &crate::dom::Element) -> bool {
3927 a.ns == b.ns
3928 && if a.tag != Tag::Other || b.tag != Tag::Other {
3929 a.tag == b.tag && (a.ns == Ns::Html || doc.element_name(a) == doc.element_name(b))
3930 } else {
3931 doc.element_name(a) == doc.element_name(b)
3932 }
3933}
3934
3935fn xml_local(name: &str) -> &str {
3937 name.split_once(':').map_or(name, |(_, local)| local)
3938}
3939
3940fn nth_matches(a: i64, b: i64, index: i64) -> bool {
3941 if a == 0 {
3942 return index == b;
3943 }
3944 let diff = index - b;
3945 diff % a == 0 && diff / a >= 0
3946}
3947
3948fn nth_in_range(a: i64, b: i64, lo: i64, hi: i64) -> bool {
3950 match a.cmp(&0) {
3951 std::cmp::Ordering::Equal => (lo..=hi).contains(&b),
3952 std::cmp::Ordering::Greater => {
3954 let from = lo.max(b);
3955 from + (b - from).rem_euclid(a) <= hi
3956 }
3957 std::cmp::Ordering::Less => {
3959 let to = hi.min(b);
3960 to - (to - b).rem_euclid(-a) >= lo
3961 }
3962 }
3963}
3964
3965fn value_matches(op: AttrOp, value: &str, want: &str, insensitive: bool) -> bool {
3966 let eq = |x: &str, y: &str| {
3967 if insensitive {
3968 x.eq_ignore_ascii_case(y)
3969 } else {
3970 x == y
3971 }
3972 };
3973 match op {
3974 AttrOp::Exists => true,
3975 AttrOp::Equals => eq(value, want),
3976 AttrOp::Includes => {
3977 !want.is_empty()
3978 && !want.contains(is_space_char)
3979 && value.split(is_space_char).any(|w| eq(w, want))
3980 }
3981 AttrOp::DashMatch => {
3982 eq(value, want)
3983 || (value.len() > want.len()
3984 && value.as_bytes()[want.len()] == b'-'
3985 && value.is_char_boundary(want.len())
3986 && eq(&value[..want.len()], want))
3987 }
3988 AttrOp::Prefix => {
3989 !want.is_empty()
3990 && value.len() >= want.len()
3991 && value.is_char_boundary(want.len())
3992 && eq(&value[..want.len()], want)
3993 }
3994 AttrOp::Suffix => {
3995 !want.is_empty()
3996 && value.len() >= want.len()
3997 && value.is_char_boundary(value.len() - want.len())
3998 && eq(&value[value.len() - want.len()..], want)
3999 }
4000 AttrOp::Substring => {
4001 !want.is_empty()
4002 && if insensitive {
4003 value
4004 .to_ascii_lowercase()
4005 .contains(&want.to_ascii_lowercase())
4006 } else {
4007 value.contains(want)
4008 }
4009 }
4010 }
4011}
4012
4013#[cfg(test)]
4014mod nth_range_tests {
4015 #[test]
4016 fn nth_in_range_agrees_with_each_position() {
4017 for a in -4..=4 {
4018 for b in -6..=8 {
4019 for lo in 1..=7 {
4020 for hi in lo..=9 {
4021 let each = (lo..=hi).any(|i| super::nth_matches(a, b, i));
4022 assert_eq!(
4023 super::nth_in_range(a, b, lo, hi),
4024 each,
4025 "{a}n+{b} in {lo}..={hi}"
4026 );
4027 }
4028 }
4029 }
4030 }
4031 }
4032}