use std::cell::{Cell, RefCell};
use std::cmp::Reverse;
use std::collections::{BTreeMap, BinaryHeap, HashMap};
use std::rc::Rc;
use std::time::{Duration, Instant};
use crate::dom::{AttrNs, Data, Document, NONE, NodeId, Ns, Quirks};
use crate::pattern::Pattern;
use crate::tags::Tag;
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct SelectorError {
pub reason: String,
}
impl std::fmt::Display for SelectorError {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.write_str(&self.reason)
}
}
impl std::error::Error for SelectorError {}
fn error<T>(reason: impl Into<String>) -> Result<T, SelectorError> {
Err(SelectorError {
reason: reason.into(),
})
}
#[derive(Debug, Clone)]
pub struct SelectorList(Vec<Complex>);
#[derive(Debug, Clone)]
struct Complex {
parts: Vec<(Compound, Combinator)>,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Combinator {
None,
Descendant,
Child,
NextSibling,
SubsequentSibling,
Column,
}
#[derive(Debug, Clone, Default)]
struct Compound(Vec<Simple>);
#[derive(Debug, Clone)]
enum Simple {
Type {
lower: String,
exact: String,
tag: Tag,
},
Id(String),
Class(String),
Attr(AttrSelector),
Pseudo(Pseudo),
Anchor,
Ns(Ns),
}
#[derive(Debug, Clone)]
struct AttrSelector {
lower: String,
exact: String,
any_ns: bool,
in_ns: Option<AttrNs>,
op: AttrOp,
value: String,
case: Case,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum AttrOp {
Exists,
Equals,
Includes,
DashMatch,
Prefix,
Suffix,
Substring,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Case {
Default,
Insensitive,
Sensitive,
}
#[derive(Debug, Clone)]
enum Pseudo {
Not(SelectorList),
Is(SelectorList),
Where(SelectorList),
Has(SelectorList),
Nth {
a: i32,
b: i32,
last: bool,
of_type: bool,
of: Option<SelectorList>,
},
Only {
of_type: bool,
},
Empty,
Root,
Scope,
AnyLink,
Checked,
Disabled,
Enabled,
Required,
Optional,
ReadWrite,
ReadOnly,
PlaceholderShown,
Blank,
Defined,
Target,
TargetWithin,
LocalLink,
Lang(Vec<String>),
Dir(bool),
Default,
Indeterminate,
InRange,
OutOfRange,
Valid,
Invalid,
Never,
Element,
Host(Option<Box<Compound>>),
HostContext(Box<Compound>),
Slotted(Box<Compound>),
Heading(Vec<i64>),
NthCol {
a: i32,
b: i32,
last: bool,
},
}
struct Parser<'a> {
s: &'a str,
pos: usize,
depth: u32,
in_has: bool,
compound_only: bool,
opts: &'a ParseOptions<'a>,
}
const MAX_DEPTH: u32 = 32;
fn is_name_start(c: char) -> bool {
c.is_ascii_alphabetic() || c == '_' || !c.is_ascii()
}
fn is_name(c: char) -> bool {
is_name_start(c) || c.is_ascii_digit() || c == '-'
}
impl<'a> Parser<'a> {
fn peek(&self) -> Option<char> {
self.s[self.pos..].chars().next()
}
fn peek_at(&self, n: usize) -> Option<char> {
self.s[self.pos..].chars().nth(n)
}
fn bump(&mut self) -> Option<char> {
let c = self.peek()?;
self.pos += c.len_utf8();
Some(c)
}
fn eat(&mut self, c: char) -> bool {
if self.peek() == Some(c) {
self.pos += c.len_utf8();
true
} else {
false
}
}
fn skip_space(&mut self) -> bool {
let mut space = false;
loop {
if matches!(self.peek(), Some(' ' | '\t' | '\n' | '\r' | '\x0C')) {
self.pos += 1;
space = true;
} else if !self.skip_comment() {
return space;
}
}
}
fn skip_comment(&mut self) -> bool {
if !self.s[self.pos..].starts_with("/*") {
return false;
}
match self.s[self.pos + 2..].find("*/") {
Some(end) => self.pos += end + 4,
None => self.pos = self.s.len(),
}
true
}
fn at_end(&self) -> bool {
self.pos >= self.s.len()
}
fn escape(&mut self) -> Result<char, SelectorError> {
let Some(c) = self.peek() else {
return Ok('\u{FFFD}');
};
if c == '\n' {
return error("a backslash before a newline");
}
if c.is_ascii_hexdigit() {
let start = self.pos;
while self.pos - start < 6 && self.peek().is_some_and(|c| c.is_ascii_hexdigit()) {
self.pos += 1;
}
let code = u32::from_str_radix(&self.s[start..self.pos], 16).unwrap();
if matches!(self.peek(), Some(' ' | '\t' | '\n' | '\x0C')) {
self.pos += 1;
}
return Ok(match code {
0 | 0xD800..=0xDFFF | 0x11_0000.. => '\u{FFFD}',
_ => char::from_u32(code).unwrap_or('\u{FFFD}'),
});
}
self.pos += c.len_utf8();
Ok(c)
}
fn starts_name(&self) -> bool {
match self.peek() {
Some('\\') => self.peek_at(1).is_some_and(|c| c != '\n'),
Some('-') => match self.peek_at(1) {
Some(c) if is_name_start(c) || c == '-' => true,
Some('\\') => self.peek_at(2).is_some_and(|c| c != '\n'),
_ => false,
},
Some(c) => is_name_start(c),
None => false,
}
}
fn name(&mut self) -> Result<String, SelectorError> {
let mut out = String::new();
loop {
match self.peek() {
Some('\\') if self.peek_at(1).is_some_and(|c| c != '\n') => {
self.pos += 1;
out.push(self.escape()?);
}
Some(c) if is_name(c) => {
self.pos += c.len_utf8();
out.push(c);
}
_ => return Ok(out),
}
}
}
fn ident(&mut self) -> Result<String, SelectorError> {
if !self.starts_name() {
return error(format!("expected a name at {:?}", &self.s[self.pos..]));
}
self.name()
}
fn string(&mut self, quote: char) -> Result<String, SelectorError> {
let mut out = String::new();
loop {
match self.bump() {
None => return Ok(out),
Some(c) if c == quote => return Ok(out),
Some('\n') => return error("a newline in a string"),
Some('\\') => match self.peek() {
Some('\n') => self.pos += 1,
None => {}
Some(_) => out.push(self.escape()?),
},
Some(c) => out.push(c),
}
}
}
fn selector_list(&mut self, forgiving: bool) -> Result<SelectorList, SelectorError> {
let mut out = Vec::new();
loop {
self.skip_space();
let start = self.pos;
match self.complex(false) {
Ok(c) => out.push(c),
Err(e) if !forgiving => return Err(e),
Err(e) => {
self.pos = start;
if self.skip_to_comma() {
return Err(e);
}
}
}
self.skip_space();
if !self.eat(',') {
break;
}
}
if out.is_empty() && !forgiving {
return error("an empty selector");
}
Ok(SelectorList(out))
}
fn skip_to_comma(&mut self) -> bool {
let mut open: Vec<char> = Vec::new();
while let Some(c) = self.peek() {
match c {
'(' => open.push(')'),
'[' => open.push(']'),
')' | ']' | ',' if open.is_empty() => return false,
')' | ']' if open.last() == Some(&c) => {
open.pop();
}
'"' | '\'' => {
self.pos += 1;
let _ = self.string(c);
continue;
}
'\\' => self.pos += 1,
_ => {}
}
self.bump();
}
!open.is_empty()
}
fn complex(&mut self, relative: bool) -> Result<Complex, SelectorError> {
let mut parts: Vec<(Compound, Combinator)> = Vec::new();
let mut pending = Combinator::None;
if relative {
self.skip_space();
pending = self.combinator().unwrap_or(Combinator::Descendant);
parts.push((Compound(vec![Simple::Anchor]), Combinator::None));
self.skip_space();
}
loop {
let compound = self.compound()?;
let has_element = compound
.0
.iter()
.any(|s| matches!(s, Simple::Pseudo(Pseudo::Element | Pseudo::Slotted(_))));
if let Some(last) = parts.last_mut() {
last.1 = pending;
}
parts.push((compound, Combinator::None));
let space = self.skip_space();
if self.at_end() || matches!(self.peek(), Some(',' | ')')) {
break;
}
if has_element {
return error("a pseudo-element must end the selector");
}
if self.compound_only && !relative {
return error(
"only a compound selector can go in :host(), :host-context() or ::slotted()",
);
}
pending = match self.combinator() {
Some(c) => {
self.skip_space();
c
}
None if space => Combinator::Descendant,
None => return error(format!("unexpected {:?}", &self.s[self.pos..])),
};
}
let mut combinators: Vec<Combinator> = parts.iter().map(|p| p.1).collect();
combinators.pop();
parts.reverse();
combinators.reverse();
for (i, c) in combinators.into_iter().enumerate() {
parts[i].1 = c;
}
let last = parts.len() - 1;
parts[last].1 = Combinator::None;
Ok(Complex { parts })
}
fn combinator(&mut self) -> Option<Combinator> {
match self.peek()? {
'>' => {
self.pos += 1;
Some(Combinator::Child)
}
'+' => {
self.pos += 1;
Some(Combinator::NextSibling)
}
'~' => {
self.pos += 1;
Some(Combinator::SubsequentSibling)
}
'|' if self.peek_at(1) == Some('|') => {
self.pos += 2;
Some(Combinator::Column)
}
_ => None,
}
}
fn compound(&mut self) -> Result<Compound, SelectorError> {
let mut simple = Vec::new();
let mut universal = false;
let mut explicit = false;
let mut prefixed = false;
let bar = |p: &Self| p.peek() == Some('|') && p.peek_at(1) != Some('|');
if self.peek() == Some('*') || self.starts_name() || bar(self) {
explicit = true;
let star = self.eat('*');
universal = star;
let name = if star || self.peek() == Some('|') {
String::new()
} else {
self.name()?
};
if bar(self) && self.peek_at(1) != Some('=') {
self.pos += 1;
prefixed = true;
let ns = match (star, name.is_empty()) {
(true, _) => None,
(false, true) => {
simple.push(Simple::Pseudo(Pseudo::Never));
None
}
(false, false) => Some(self.namespace(&name)?),
};
if !self.eat('*') {
let local = self.ident()?;
simple.push(type_selector(local));
}
if let Some(ns) = ns {
simple.push(Simple::Ns(ns));
}
} else if !star {
simple.push(type_selector(name));
}
}
let mut after_element: Option<bool> = None;
loop {
while self.skip_comment() {}
if after_element.is_some() && matches!(self.peek(), Some('#' | '.' | '[')) {
return error("only a pseudo-class can follow a pseudo-element");
}
match self.peek() {
Some('#') => {
self.pos += 1;
if !self.starts_name() {
return error(match self.peek() {
Some(c) if c.is_ascii_digit() => "an ID can't start with a digit",
Some('-') if self.peek_at(1).is_some_and(|c| c.is_ascii_digit()) => {
"an ID can't start with a hyphen and a digit"
}
_ => "a # with no ID after it",
});
}
simple.push(Simple::Id(self.name()?));
}
Some('.') => {
self.pos += 1;
simple.push(Simple::Class(self.ident()?));
}
Some('[') => {
self.pos += 1;
let declared = self.declared_attr_prefix();
let mut attr = self.attr()?;
simple.push(match declared {
Some(None) => Simple::Pseudo(Pseudo::Never),
Some(Some(ns)) => {
attr.in_ns = Some(ns);
Simple::Attr(attr)
}
None => Simple::Attr(attr),
});
}
Some(':') if self.peek_at(1) == Some(':') => {
if self.depth > 0 {
return error("a pseudo-element can't go inside a pseudo-class");
}
self.pos += 2;
match self.pseudo_element()? {
Some(arg) => {
simple.insert(0, Simple::Pseudo(Pseudo::Slotted(Box::new(arg))));
after_element = Some(true);
}
None => {
simple.push(Simple::Pseudo(Pseudo::Element));
after_element = Some(false);
}
}
}
Some(':') => {
self.pos += 1;
let pseudo = self.pseudo()?;
let element = matches!(pseudo, Pseudo::Element);
match after_element {
Some(true) if !element => {
return error("only a pseudo-element can follow ::slotted()");
}
Some(_) if pseudo.reads_the_tree() => {
return error(
"a tree-structural pseudo-class can't follow a pseudo-element",
);
}
_ => {}
}
if element {
after_element = Some(false);
}
simple.push(Simple::Pseudo(pseudo));
}
_ => break,
}
}
if simple.is_empty() && !universal {
return error(match self.peek() {
Some(c) => format!("unexpected {c:?}"),
None => "a selector ends early".to_string(),
});
}
if let Some(ns) = self.opts.default
&& !prefixed
&& (explicit || self.depth == 0)
{
simple.push(Simple::Ns(ns));
}
Ok(Compound(simple))
}
fn namespace(&self, prefix: &str) -> Result<Ns, SelectorError> {
match self.opts.namespaces.iter().find(|(p, _)| *p == prefix) {
Some(&(_, ns)) => Ok(ns),
None => error(format!("namespace prefix {prefix:?} isn't declared")),
}
}
fn declared_attr_prefix(&mut self) -> Option<Option<AttrNs>> {
let start = self.pos;
self.skip_space();
if self.starts_name()
&& let Ok(name) = self.ident()
&& self.peek() == Some('|')
&& self.peek_at(1) != Some('=')
{
let attr = self.opts.attr_namespaces.iter().find(|(p, _)| *p == name);
if let Some(&(_, ns)) = attr {
self.pos += 1;
return Some(Some(ns));
}
if self.opts.namespaces.iter().any(|(p, _)| *p == name) {
self.pos += 1;
return Some(None);
}
}
self.pos = start;
None
}
fn attr(&mut self) -> Result<AttrSelector, SelectorError> {
self.skip_space();
let mut any_ns = false;
if self.peek() == Some('*') && self.peek_at(1) == Some('|') {
self.pos += 2;
any_ns = true;
} else if self.peek() == Some('|') {
self.pos += 1;
}
let name = self.ident()?;
if self.peek() == Some('|') && self.peek_at(1) != Some('=') {
return error(format!("namespace prefix {name:?} isn't declared"));
}
self.skip_space();
let op = match self.peek() {
Some(']') | None => {
self.eat(']');
return Ok(AttrSelector {
lower: name.to_ascii_lowercase(),
exact: name,
any_ns,
in_ns: None,
op: AttrOp::Exists,
value: String::new(),
case: Case::Default,
});
}
Some('=') => {
self.pos += 1;
AttrOp::Equals
}
Some(c @ ('~' | '|' | '^' | '$' | '*')) if self.peek_at(1) == Some('=') => {
self.pos += 2;
match c {
'~' => AttrOp::Includes,
'|' => AttrOp::DashMatch,
'^' => AttrOp::Prefix,
'$' => AttrOp::Suffix,
_ => AttrOp::Substring,
}
}
_ => return error("a bad attribute selector"),
};
self.skip_space();
let value = match self.peek() {
Some(q @ ('"' | '\'')) => {
self.pos += 1;
self.string(q)?
}
_ => self.ident()?,
};
self.skip_space();
let mut case = Case::Default;
if let Some(c) = self.peek()
&& c.is_ascii_alphabetic()
{
let flag = self.ident()?;
case = match flag.to_ascii_lowercase().as_str() {
"i" => Case::Insensitive,
"s" => Case::Sensitive,
_ => return error(format!("unknown attribute flag {flag:?}")),
};
self.skip_space();
}
if !self.eat(']') && !self.at_end() {
return error("an attribute selector without its ]");
}
Ok(AttrSelector {
lower: name.to_ascii_lowercase(),
exact: name,
any_ns,
in_ns: None,
op,
value,
case,
})
}
fn pseudo_element(&mut self) -> Result<Option<Compound>, SelectorError> {
let name = self.ident()?.to_ascii_lowercase();
if self.eat('(') {
self.skip_space();
match name.as_str() {
"part" => {
self.ident()?;
while self.skip_space() && self.starts_name() {
self.ident()?;
}
}
"slotted" => {
let compound = self.compound_argument()?;
self.skip_space();
if !self.eat(')') && !self.at_end() {
return error("::slotted() without its )");
}
return Ok(Some(compound));
}
"highlight" => {
self.ident()?;
}
_ => return error(format!("::{name}() isn't a pseudo-element")),
}
self.skip_space();
if !self.eat(')') && !self.at_end() {
return error(format!("::{name}() without its )"));
}
return Ok(None);
}
match name.as_str() {
"before"
| "after"
| "marker"
| "placeholder"
| "selection"
| "first-line"
| "first-letter"
| "backdrop"
| "file-selector-button"
| "cue"
| "spelling-error"
| "grammar-error"
| "target-text"
| "details-content"
| "checkmark"
| "picker-icon"
| "scroll-marker"
| "scroll-marker-group"
| "scroll-button"
| "column"
| "view-transition" => Ok(None),
_ => error(format!("::{name} isn't a pseudo-element")),
}
}
fn pseudo(&mut self) -> Result<Pseudo, SelectorError> {
let name = self.ident()?.to_ascii_lowercase();
if self.eat('(') {
let p = self.pseudo_function(&name)?;
self.skip_space();
if !self.eat(')') && !self.at_end() {
return error(format!(":{name}() without its )"));
}
return Ok(p);
}
Ok(match name.as_str() {
"first-child" => nth(0, 1, false, false),
"last-child" => nth(0, 1, true, false),
"only-child" => Pseudo::Only { of_type: false },
"first-of-type" => nth(0, 1, false, true),
"last-of-type" => nth(0, 1, true, true),
"only-of-type" => Pseudo::Only { of_type: true },
"empty" => Pseudo::Empty,
"heading" => Pseudo::Heading(Vec::new()),
"root" => Pseudo::Root,
"scope" => Pseudo::Scope,
"link" | "any-link" => Pseudo::AnyLink,
"checked" => Pseudo::Checked,
"disabled" => Pseudo::Disabled,
"enabled" => Pseudo::Enabled,
"required" => Pseudo::Required,
"optional" => Pseudo::Optional,
"read-write" => Pseudo::ReadWrite,
"read-only" => Pseudo::ReadOnly,
"placeholder-shown" => Pseudo::PlaceholderShown,
"blank" => Pseudo::Blank,
"defined" => Pseudo::Defined,
"target" => Pseudo::Target,
"target-within" => Pseudo::TargetWithin,
"local-link" => Pseudo::LocalLink,
"default" => Pseudo::Default,
"indeterminate" => Pseudo::Indeterminate,
"in-range" => Pseudo::InRange,
"out-of-range" => Pseudo::OutOfRange,
"valid" => Pseudo::Valid,
"invalid" => Pseudo::Invalid,
"hover" | "active" | "focus" | "focus-visible" | "focus-within" | "visited"
| "user-invalid" | "user-valid" => Pseudo::Never,
"before" | "after" | "first-line" | "first-letter" => Pseudo::Element,
"host" => Pseudo::Host(None),
_ => return error(format!(":{name} isn't supported")),
})
}
fn pseudo_function(&mut self, name: &str) -> Result<Pseudo, SelectorError> {
if self.depth >= MAX_DEPTH {
return error(format!("selectors nest more than {MAX_DEPTH} deep"));
}
self.depth += 1;
let result = self.pseudo_function_body(name);
self.depth -= 1;
result
}
fn pseudo_function_body(&mut self, name: &str) -> Result<Pseudo, SelectorError> {
Ok(match name {
"not" => Pseudo::Not(self.selector_list(false)?),
"host" => Pseudo::Host(Some(Box::new(self.compound_argument()?))),
"host-context" => Pseudo::HostContext(Box::new(self.compound_argument()?)),
"is" | "matches" => Pseudo::Is(self.selector_list(true)?),
"where" => Pseudo::Where(self.selector_list(true)?),
"has" => {
if self.in_has {
return error(":has() can't go inside :has()");
}
self.in_has = true;
let list = self.has_list();
self.in_has = false;
Pseudo::Has(list?)
}
"nth-child" | "nth-last-child" | "nth-of-type" | "nth-last-of-type" => {
let of_type = name.ends_with("of-type");
let last = name.starts_with("nth-last");
let close = self.close_paren();
let arg = &self.s[self.pos..close];
let (anb, rest) = match split_of(arg) {
Some((anb, rest)) if !of_type => (anb, Some(rest)),
Some(_) => return error("`of` only goes in :nth-child and :nth-last-child"),
None => (arg, None),
};
let (a, b) = an_plus_b(anb)?;
let of = rest
.map(|rest| SelectorList::parse_at(rest, self.depth, self.in_has, self.opts))
.transpose()?;
self.pos = close;
Pseudo::Nth {
a,
b,
last,
of_type,
of,
}
}
"nth-col" | "nth-last-col" => {
let close = self.close_paren();
let (a, b) = an_plus_b(&self.s[self.pos..close])?;
self.pos = close;
Pseudo::NthCol {
a,
b,
last: name == "nth-last-col",
}
}
"lang" => {
let mut ranges = Vec::new();
loop {
self.skip_space();
let range = match self.peek() {
Some(q @ ('"' | '\'')) => {
self.pos += 1;
self.string(q)?
}
_ => self.ident()?,
};
ranges.push(range.to_ascii_lowercase());
self.skip_space();
if !self.eat(',') {
break;
}
}
Pseudo::Lang(ranges)
}
"heading" => {
let mut levels = Vec::new();
loop {
self.skip_space();
let start = self.pos;
if matches!(self.peek(), Some('+' | '-')) {
self.pos += 1;
}
while self.peek().is_some_and(|c| c.is_ascii_digit()) {
self.pos += 1;
}
let whole = !self.peek().is_some_and(|c| is_name(c) || c == '.');
match self.s[start..self.pos].parse() {
Ok(level) if whole => levels.push(level),
_ => return error(":heading() takes integers, like :heading(1, 3)"),
}
self.skip_space();
if !self.eat(',') {
break;
}
}
Pseudo::Heading(levels)
}
"dir" => {
self.skip_space();
let dir = self.ident()?.to_ascii_lowercase();
self.skip_space();
match dir.as_str() {
"ltr" => Pseudo::Dir(false),
"rtl" => Pseudo::Dir(true),
_ => Pseudo::Never,
}
}
_ => return error(format!(":{name}() isn't supported")),
})
}
fn compound_argument(&mut self) -> Result<Compound, SelectorError> {
if self.depth >= MAX_DEPTH {
return error(format!("selectors nest more than {MAX_DEPTH} deep"));
}
self.skip_space();
let outer = std::mem::replace(&mut self.compound_only, true);
self.depth += 1;
let compound = self.compound();
self.depth -= 1;
self.compound_only = outer;
compound
}
fn has_list(&mut self) -> Result<SelectorList, SelectorError> {
let mut out = Vec::new();
loop {
out.push(self.complex(true)?);
self.skip_space();
if !self.eat(',') {
return Ok(SelectorList(out));
}
}
}
fn close_paren(&self) -> usize {
let b = self.s.as_bytes();
let mut depth = 0;
let mut i = self.pos;
while i < b.len() {
match b[i] {
b'\\' => i += 1,
q @ (b'"' | b'\'') => {
i += 1;
while i < b.len() && b[i] != q {
if b[i] == b'\\' {
i += 1;
}
i += 1;
}
}
b'(' => depth += 1,
b')' if depth == 0 => return i,
b')' => depth -= 1,
_ => {}
}
i += 1;
}
b.len()
}
}
fn first_strong_rtl(text: &str) -> Option<bool> {
text.chars()
.filter(|c| c.is_alphabetic())
.map(|c| {
matches!(c as u32,
0x0590..=0x08FF | 0xFB1D..=0xFDFF | 0xFE70..=0xFEFF
| 0x10800..=0x10FFF | 0x1E800..=0x1EFFF)
})
.next()
}
fn lang_matches(range: &str, tag: &str) -> bool {
if range.is_empty() || tag.is_empty() {
return range == tag;
}
let r: Vec<&str> = range.split('-').collect();
let t: Vec<&str> = tag.split('-').collect();
if t.iter()
.any(|s| s.is_empty() || s.len() > 8 || !s.bytes().all(|b| b.is_ascii_alphanumeric()))
{
return false;
}
if r[0] != "*" && r[0] != t[0] {
return false;
}
let (mut i, mut j) = (1, 1);
while i < r.len() {
if r[i] == "*" {
i += 1;
} else if j >= t.len() {
return false;
} else if r[i] == t[j] {
i += 1;
j += 1;
} else if t[j].len() == 1 {
return false;
} else {
j += 1;
}
}
true
}
fn input_type_state(typ: Option<&str>) -> &'static str {
const TYPES: [&str; 22] = [
"hidden",
"text",
"search",
"tel",
"url",
"email",
"password",
"date",
"month",
"week",
"time",
"datetime-local",
"number",
"range",
"color",
"checkbox",
"radio",
"file",
"submit",
"image",
"reset",
"button",
];
typ.and_then(|t| TYPES.iter().find(|k| k.eq_ignore_ascii_case(t)))
.copied()
.unwrap_or("text")
}
fn text_entry(typ: &str) -> bool {
matches!(
typ,
"text" | "search" | "url" | "tel" | "email" | "password" | "number"
)
}
pub(crate) fn custom_element_name(name: &str) -> bool {
const RESERVED: [&str; 8] = [
"annotation-xml",
"color-profile",
"font-face",
"font-face-src",
"font-face-uri",
"font-face-format",
"font-face-name",
"missing-glyph",
];
let pcen = |c: char| {
matches!(c,
'-' | '.' | '0'..='9' | '_' | 'a'..='z' | '\u{B7}'
| '\u{C0}'..='\u{D6}' | '\u{D8}'..='\u{F6}' | '\u{F8}'..='\u{37D}'
| '\u{37F}'..='\u{1FFF}' | '\u{200C}'..='\u{200D}' | '\u{203F}'..='\u{2040}'
| '\u{2070}'..='\u{218F}' | '\u{2C00}'..='\u{2FEF}' | '\u{3001}'..='\u{D7FF}'
| '\u{F900}'..='\u{FDCF}' | '\u{FDF0}'..='\u{FFFD}' | '\u{10000}'..='\u{EFFFF}')
};
name.starts_with(|c: char| c.is_ascii_lowercase())
&& name.contains('-')
&& name.chars().all(pcen)
&& !RESERVED.contains(&name)
}
fn readonly_applies(typ: &str) -> bool {
matches!(
typ,
"text"
| "search"
| "url"
| "tel"
| "email"
| "password"
| "date"
| "month"
| "week"
| "time"
| "datetime-local"
| "number"
)
}
fn sanitized(typ: &str, value: &str, multiple: bool) -> String {
let no_breaks: String = value.chars().filter(|&c| c != '\n' && c != '\r').collect();
let trim = |s: &str| {
s.trim_matches(|c: char| c.is_ascii_whitespace())
.to_string()
};
match typ {
"url" => trim(&no_breaks),
"email" if multiple => value.split(',').map(trim).collect::<Vec<_>>().join(","),
"email" => trim(&no_breaks),
"number" | "date" | "month" | "week" | "time" | "datetime-local" => {
if input_number(typ, value).is_some() {
value.to_string()
} else {
String::new()
}
}
_ => no_breaks,
}
}
fn parse_float_value(s: &str) -> Option<f64> {
let s = s.trim_start_matches(|c: char| c.is_ascii_whitespace());
let b = s.as_bytes();
let mut i = usize::from(matches!(b.first(), Some(b'-' | b'+')));
let digits = |i: &mut usize| {
let at = *i;
while b.get(*i).is_some_and(u8::is_ascii_digit) {
*i += 1;
}
*i > at
};
let mut end;
let whole = digits(&mut i);
end = i;
if b.get(i) == Some(&b'.') {
let mut j = i + 1;
if digits(&mut j) {
i = j;
end = i;
} else if !whole {
return None;
}
}
if !whole && end == usize::from(matches!(b.first(), Some(b'-' | b'+'))) {
return None;
}
if matches!(b.get(end), Some(b'e' | b'E')) {
let mut j = end + 1;
if matches!(b.get(j), Some(b'+' | b'-')) {
j += 1;
}
if digits(&mut j) {
end = j;
}
}
s[..end]
.trim_start_matches('+')
.parse::<f64>()
.ok()
.filter(|n| n.is_finite())
}
fn parse_non_negative(s: &str) -> Option<u32> {
let s = s.trim_start_matches(|c: char| c.is_ascii_whitespace());
let s = s.strip_prefix('+').unwrap_or(s);
let end = s.find(|c: char| !c.is_ascii_digit()).unwrap_or(s.len());
s[..end].parse().ok()
}
fn valid_email(address: &str) -> bool {
let Some((local, domain)) = address.split_once('@') else {
return false;
};
let local_ok = !local.is_empty()
&& local
.chars()
.all(|c| c.is_ascii_alphanumeric() || ".!#$%&'*+/=?^_`{|}~-".contains(c));
let label_ok = |l: &str| {
!l.is_empty()
&& l.len() <= 63
&& l.chars().all(|c| c.is_ascii_alphanumeric() || c == '-')
&& !l.starts_with('-')
&& !l.ends_with('-')
};
local_ok && domain.split('.').all(label_ok)
}
fn monday_of_week_1(y: i64) -> i64 {
let jan4 = days(y, 1, 4);
let weekday = (jan4 - 1) % 7; jan4 - weekday
}
fn input_number(typ: &str, v: &str) -> Option<f64> {
match typ {
"number" | "range" => float_number(v),
"date" => date(v).map(|(y, m, d)| days(y, m, d) as f64),
"month" => {
let (y, m) = v.split_once('-')?;
let (y, m) = (year(y)?, two_digits(m)?);
(1..=12).contains(&m).then(|| (y * 12 + m - 1) as f64)
}
"week" => {
let (y, w) = v.split_once("-W")?;
let (y, w) = (year(y)?, two_digits(w)?);
(1..=weeks_in(y))
.contains(&w)
.then(|| (monday_of_week_1(y) + (w - 1) * 7) as f64)
}
"time" => time_ms(v),
"datetime-local" => {
let at = v.find(['T', ' '])?;
let (y, m, d) = date(&v[..at])?;
Some(days(y, m, d) as f64 * 86_400_000.0 + time_ms(&v[at + 1..])?)
}
_ => None,
}
}
fn float_number(v: &str) -> Option<f64> {
let b = v.as_bytes();
let mut i = usize::from(b.first() == Some(&b'-'));
let digits = |i: &mut usize| {
let at = *i;
while b.get(*i).is_some_and(u8::is_ascii_digit) {
*i += 1;
}
*i > at
};
let whole = digits(&mut i);
let point = b.get(i) == Some(&b'.');
if point {
i += 1;
}
let fraction = point && digits(&mut i);
if point && !fraction {
return None;
}
if !whole && !fraction {
return None;
}
if matches!(b.get(i), Some(b'e' | b'E')) {
i += 1;
if matches!(b.get(i), Some(b'+' | b'-')) {
i += 1;
}
if !digits(&mut i) {
return None;
}
}
if i != b.len() {
return None;
}
v.parse().ok().filter(|n: &f64| n.is_finite())
}
fn year(s: &str) -> Option<i64> {
(s.len() >= 4 && s.bytes().all(|c| c.is_ascii_digit()))
.then(|| s.parse().ok())
.flatten()
.filter(|&y| y > 0)
}
fn two_digits(s: &str) -> Option<i64> {
(s.len() == 2 && s.bytes().all(|c| c.is_ascii_digit())).then(|| s.parse().ok())?
}
fn leap(y: i64) -> bool {
(y % 4 == 0 && y % 100 != 0) || y % 400 == 0
}
fn date(v: &str) -> Option<(i64, i64, i64)> {
let mut parts = v.splitn(3, '-');
let (y, m, d) = (
year(parts.next()?)?,
two_digits(parts.next()?)?,
two_digits(parts.next()?)?,
);
let last = match m {
1 | 3 | 5 | 7 | 8 | 10 | 12 => 31,
4 | 6 | 9 | 11 => 30,
2 if leap(y) => 29,
2 => 28,
_ => return None,
};
(1..=last).contains(&d).then_some((y, m, d))
}
fn days(y: i64, m: i64, d: i64) -> i64 {
let before = y - 1;
let mut n = before * 365 + before / 4 - before / 100 + before / 400;
for month in 1..m {
n += match month {
1 | 3 | 5 | 7 | 8 | 10 | 12 => 31,
4 | 6 | 9 | 11 => 30,
_ if leap(y) => 29,
_ => 28,
};
}
n + d
}
fn weeks_in(y: i64) -> i64 {
let weekday = days(y, 1, 1) % 7; if weekday == 4 || (weekday == 3 && leap(y)) {
53
} else {
52
}
}
fn time_ms(v: &str) -> Option<f64> {
let mut parts = v.splitn(3, ':');
let (h, m) = (two_digits(parts.next()?)?, two_digits(parts.next()?)?);
if h > 23 || m > 59 {
return None;
}
let seconds = match parts.next() {
None => 0.0,
Some(s) => {
let (whole, frac) = s.split_once('.').unwrap_or((s, ""));
let sec = two_digits(whole)?;
let frac_ok = frac.len() <= 3
&& frac.bytes().all(|c| c.is_ascii_digit())
&& (!s.contains('.') || !frac.is_empty());
if sec > 59 || !frac_ok {
return None;
}
s.parse::<f64>().ok()?
}
};
Some(((h * 60 + m) as f64 * 60.0 + seconds) * 1000.0)
}
fn split_of(arg: &str) -> Option<(&str, &str)> {
let lower = arg.to_ascii_lowercase();
let mut from = 0;
while let Some(i) = lower[from..].find("of") {
let at = from + i;
let before = lower[..at].chars().next_back();
let after = lower[at + 2..].chars().next();
if before.is_some_and(is_space_char) && after.is_some_and(is_space_char) {
return Some((&arg[..at], &arg[at + 2..]));
}
from = at + 2;
}
None
}
fn an_plus_b(text: &str) -> Result<(i32, i32), SelectorError> {
let text = text.trim().to_ascii_lowercase();
let bad = || SelectorError {
reason: format!("{text:?} isn't An+B"),
};
match text.as_str() {
"odd" => return Ok((2, 1)),
"even" => return Ok((2, 0)),
"" => return Err(bad()),
_ => {}
}
let Some(i) = text.find('n') else {
return text.parse::<i32>().map(|b| (0, b)).map_err(|_| bad());
};
let compact: String = text[i + 1..].split_whitespace().collect();
let a = match &text[..i] {
"" | "+" => 1,
"-" => -1,
s => s.parse::<i32>().map_err(|_| bad())?,
};
let rest = compact.as_str();
let b = if rest.is_empty() {
0
} else if rest.len() > 1
&& rest.starts_with(['+', '-'])
&& rest[1..].bytes().all(|c| c.is_ascii_digit())
{
rest.parse::<i32>().map_err(|_| bad())?
} else {
return Err(bad());
};
Ok((a, b))
}
fn type_selector(name: String) -> Simple {
let lower = name.to_ascii_lowercase();
Simple::Type {
tag: Tag::from_name(&lower),
lower,
exact: name,
}
}
fn nth(a: i32, b: i32, last: bool, of_type: bool) -> Pseudo {
Pseudo::Nth {
a,
b,
last,
of_type,
of: None,
}
}
#[derive(Debug, Clone, Copy, Default)]
pub struct ParseOptions<'a> {
pub namespaces: &'a [(&'a str, Ns)],
pub attr_namespaces: &'a [(&'a str, AttrNs)],
pub default: Option<Ns>,
}
impl SelectorList {
pub fn parse(selector: &str) -> Result<SelectorList, SelectorError> {
SelectorList::parse_with(selector, &ParseOptions::default())
}
pub fn parse_with(selector: &str, opts: &ParseOptions) -> Result<SelectorList, SelectorError> {
let declared = opts
.namespaces
.iter()
.map(|&(_, ns)| ns)
.chain(opts.default);
if declared.into_iter().any(|ns| ns == Ns::Xml) {
return error("Ns::Xml isn't a namespace a selector can declare");
}
if opts
.attr_namespaces
.iter()
.any(|(_, ns)| matches!(ns, AttrNs::Host(_)))
{
return error("AttrNs::Host isn't a namespace a selector can declare");
}
SelectorList::parse_at(selector, 0, false, opts)
}
fn parse_at(
selector: &str,
depth: u32,
in_has: bool,
opts: &ParseOptions,
) -> Result<SelectorList, SelectorError> {
let mut p = Parser {
s: selector,
pos: 0,
depth,
in_has,
compound_only: false,
opts,
};
let list = p.selector_list(false)?;
p.skip_space();
if !p.at_end() {
return error(format!("unexpected {:?}", &selector[p.pos..]));
}
Ok(list)
}
pub fn matches(&self, doc: &Document, el: NodeId, scope: Option<NodeId>) -> bool {
self.matches_with(doc, el, scope, &MatchOptions::default())
}
pub fn matches_with(
&self,
doc: &Document,
el: NodeId,
scope: Option<NodeId>,
options: &MatchOptions<'_>,
) -> bool {
if doc.is_removed(el) {
return false;
}
let cx = Cx::new(doc, scope, scope.unwrap_or(el), Page::new(doc, options.url));
self.0.iter().any(|c| cx.complex(c, el, el))
}
pub fn select_with(
&self,
doc: &Document,
scope: NodeId,
options: &MatchOptions<'_>,
) -> Vec<NodeId> {
self.iter_with(doc, scope, options).collect()
}
pub fn try_select_with(
&self,
doc: &Document,
scope: NodeId,
options: &MatchOptions<'_>,
) -> Result<Vec<NodeId>, MatchTimeout> {
let mut select = self.iter_with(doc, scope, options);
select.cx.limit(options);
let found = select.by_ref().collect();
timeout(&select.cx, options)?;
Ok(found)
}
pub fn try_matches_with(
&self,
doc: &Document,
el: NodeId,
scope: Option<NodeId>,
options: &MatchOptions<'_>,
) -> Result<bool, MatchTimeout> {
if doc.is_removed(el) {
return Ok(false);
}
let mut cx = Cx::new(doc, scope, scope.unwrap_or(el), Page::new(doc, options.url));
cx.limit(options);
let found = self.0.iter().any(|c| cx.complex(c, el, el));
timeout(&cx, options)?;
Ok(found)
}
fn iter_with<'a>(
&'a self,
doc: &'a Document,
scope: NodeId,
options: &MatchOptions<'_>,
) -> Select<'a> {
Select {
list: self,
cx: Cx::new(doc, Some(scope), scope, Page::new(doc, options.url)),
scope,
at: doc.first_child(scope),
}
}
pub fn select(&self, doc: &Document, scope: NodeId) -> Vec<NodeId> {
self.select_iter(doc, scope).collect()
}
pub fn select_iter<'a>(&'a self, doc: &'a Document, scope: NodeId) -> Select<'a> {
self.iter_with(doc, scope, &MatchOptions::default())
}
pub fn select_first(&self, doc: &Document, scope: NodeId) -> Option<NodeId> {
self.select_iter(doc, scope).next()
}
pub fn specificity(&self) -> (u32, u32, u32) {
self.0
.iter()
.map(Complex::specificity)
.max()
.unwrap_or((0, 0, 0))
}
}
impl Complex {
fn specificity(&self) -> (u32, u32, u32) {
self.parts.iter().fold((0, 0, 0), |sum, (compound, _)| {
compound.0.iter().fold(sum, |(a, b, c), simple| {
let (x, y, z) = simple.specificity();
(a + x, b + y, c + z)
})
})
}
}
impl Compound {
fn specificity(&self) -> (u32, u32, u32) {
self.0.iter().fold((0, 0, 0), |(a, b, c), simple| {
let (x, y, z) = simple.specificity();
(a + x, b + y, c + z)
})
}
}
impl Pseudo {
fn reads_the_tree(&self) -> bool {
matches!(
self,
Pseudo::Nth { .. }
| Pseudo::Only { .. }
| Pseudo::Empty
| Pseudo::Root
| Pseudo::Scope
| Pseudo::Has(_)
| Pseudo::Heading(_)
)
}
}
impl Simple {
fn specificity(&self) -> (u32, u32, u32) {
match self {
Simple::Id(_) => (1, 0, 0),
Simple::Class(_) | Simple::Attr(_) => (0, 1, 0),
Simple::Type { .. } => (0, 0, 1),
Simple::Anchor | Simple::Ns(_) => (0, 0, 0),
Simple::Pseudo(p) => match p {
Pseudo::Is(list) | Pseudo::Not(list) | Pseudo::Has(list) => list.specificity(),
Pseudo::Where(_) => (0, 0, 0),
Pseudo::Nth { of: Some(list), .. } => {
let (a, b, c) = list.specificity();
(a, b + 1, c)
}
Pseudo::Element => (0, 0, 1),
Pseudo::Host(Some(c)) | Pseudo::HostContext(c) => {
let (a, b, c) = c.specificity();
(a, b + 1, c)
}
Pseudo::Slotted(c) => {
let (a, b, c) = c.specificity();
(a, b, c + 1)
}
_ => (0, 1, 0),
},
}
}
}
pub struct Select<'a> {
list: &'a SelectorList,
cx: Cx<'a>,
scope: NodeId,
at: Option<NodeId>,
}
impl Iterator for Select<'_> {
type Item = NodeId;
fn next(&mut self) -> Option<NodeId> {
let doc = self.cx.doc;
while let Some(n) = self.at {
if self.cx.timed_out.get() {
return None;
}
let element = doc.element(n).is_some();
self.at = match doc.first_child(n).filter(|_| element) {
Some(child) => Some(child),
None => {
let mut up = Some(n);
let mut next = None;
while let Some(u) = up {
if u == self.scope {
break;
}
if let Some(s) = doc.next_sibling(u) {
next = Some(s);
break;
}
up = doc.parent(u);
}
next
}
};
if element && self.list.0.iter().any(|c| self.cx.complex(c, n, n)) {
return Some(n);
}
}
None
}
}
fn push_children_reversed(doc: &Document, n: NodeId, stack: &mut Vec<NodeId>) {
let at = stack.len();
stack.extend(doc.children(n));
stack[at..].reverse();
}
#[derive(Debug, Clone, Copy, Default)]
pub struct MatchOptions<'a> {
pub url: Option<&'a str>,
pub budget: Option<Duration>,
pub max_steps: Option<u64>,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct MatchTimeout {
pub budget: Duration,
pub max_steps: Option<u64>,
}
impl std::fmt::Display for MatchTimeout {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self.max_steps {
Some(steps) => write!(f, "matching took more than {steps} steps"),
None => write!(f, "matching took longer than {:?}", self.budget),
}
}
}
impl std::error::Error for MatchTimeout {}
fn deadline(options: &MatchOptions<'_>) -> Option<Instant> {
options.budget.and_then(|b| Instant::now().checked_add(b))
}
fn timeout(cx: &Cx<'_>, options: &MatchOptions<'_>) -> Result<(), MatchTimeout> {
if !cx.timed_out.get() {
return Ok(());
}
let max_steps = options.max_steps.filter(|&m| cx.steps.get() > m);
Err(MatchTimeout {
budget: match max_steps {
Some(_) => Duration::ZERO,
None => options.budget.unwrap_or_default(),
},
max_steps,
})
}
struct Page {
url: url::Url,
base: url::Url,
target: Option<NodeId>,
}
impl Page {
fn new(doc: &Document, url: Option<&str>) -> Option<Page> {
let mut url = url::Url::parse(url?).ok()?;
let fragment = url.fragment().map(str::to_string);
url.set_fragment(None);
let elements = tree_elements(doc);
let base = elements
.iter()
.find(|&&n| html_element_named(doc, n, "base") && attr_of(doc, n, "href").is_some())
.and_then(|&n| url.join(attr_of(doc, n, "href")?).ok())
.unwrap_or_else(|| url.clone());
let target = fragment.and_then(|f| indicated(doc, &elements, &f));
Some(Page { url, base, target })
}
}
fn tree_elements(doc: &Document) -> Vec<NodeId> {
let (mut out, mut stack) = (Vec::new(), vec![doc.root()]);
while let Some(n) = stack.pop() {
if doc.element(n).is_some() {
out.push(n);
}
push_children_reversed(doc, n, &mut stack);
}
out
}
fn html_element_named(doc: &Document, n: NodeId, name: &str) -> bool {
doc.element(n).is_some_and(|e| e.ns == Ns::Html) && doc.lower_name(n) == Some(name)
}
fn attr_of<'a>(doc: &'a Document, n: NodeId, name: &str) -> Option<&'a str> {
doc.attrs(n)
.find(|(ns, a, _)| *ns == AttrNs::None && *a == name)
.map(|(_, _, v)| v)
}
fn indicated(doc: &Document, elements: &[NodeId], fragment: &str) -> Option<NodeId> {
if fragment.is_empty() {
return None;
}
let find = |f: &str| {
elements
.iter()
.copied()
.find(|&n| attr_of(doc, n, "id") == Some(f))
.or_else(|| {
elements.iter().copied().find(|&n| {
html_element_named(doc, n, "a") && attr_of(doc, n, "name") == Some(f)
})
})
};
find(fragment).or_else(|| find(&percent_decode(fragment)))
}
fn percent_decode(s: &str) -> String {
let b = s.as_bytes();
let mut out = Vec::with_capacity(b.len());
let mut i = 0;
while i < b.len() {
let hex = |c: u8| (c as char).to_digit(16);
match (
b[i],
b.get(i + 1).and_then(|&c| hex(c)),
b.get(i + 2).and_then(|&c| hex(c)),
) {
(b'%', Some(h), Some(l)) => {
out.push((h * 16 + l) as u8);
i += 3;
}
(c, _, _) => {
out.push(c);
i += 1;
}
}
}
String::from_utf8_lossy(&out).into_owned()
}
struct Cx<'a> {
doc: &'a Document,
scope: Option<NodeId>,
shadow: NodeId,
host: NodeId,
page: Option<Page>,
pattern_budget: Cell<u32>,
deadline: Option<Instant>,
max_steps: u64,
limited: bool,
steps: Cell<u64>,
timed_out: Cell<bool>,
places: RefCell<IdMap<NodeId, Place>>,
of_places: RefCell<IdMap<(usize, NodeId), (u32, u32)>>,
has_seen: RefCell<IdMap<(usize, NodeId), bool>>,
nested_seen: RefCell<IdMap<(usize, NodeId), bool>>,
tables: RefCell<IdMap<NodeId, Rc<Columns>>>,
}
type IdMap<K, V> = HashMap<K, V, std::hash::BuildHasherDefault<IdHasher>>;
#[derive(Default)]
struct IdHasher(u64);
impl std::hash::Hasher for IdHasher {
fn write(&mut self, bytes: &[u8]) {
for &b in bytes {
self.write_u64(b as u64);
}
}
fn write_u32(&mut self, n: u32) {
self.write_u64(n as u64);
}
fn write_usize(&mut self, n: usize) {
self.write_u64(n as u64);
}
fn write_u64(&mut self, n: u64) {
self.0 = (self.0.rotate_left(5) ^ n).wrapping_mul(0x51_7c_c1_b7_27_22_0a_95);
}
fn finish(&self) -> u64 {
self.0
}
}
#[derive(Clone, Copy, PartialEq, Eq)]
enum Fail {
Sibling,
Descendant,
Global,
}
impl Fail {
fn exhausted(combinator: Combinator) -> Fail {
match combinator {
Combinator::NextSibling | Combinator::SubsequentSibling => Fail::Descendant,
Combinator::Column => Fail::Sibling,
_ => Fail::Global,
}
}
}
#[derive(Default)]
struct Columns {
cells: HashMap<NodeId, (u32, u32)>,
cols: Vec<(NodeId, u32, u32)>,
col_index: HashMap<NodeId, usize>,
width: u32,
}
#[derive(Default)]
struct Cover {
row: u32,
runs: BTreeMap<u32, (u32, u32)>,
blocks: BTreeMap<u32, u32>,
ends: BinaryHeap<Reverse<(u32, u32)>>,
}
impl Cover {
fn advance(&mut self, row: u32) {
while let Some(&Reverse((until, start))) = self.ends.peek() {
if until > row {
break;
}
self.ends.pop();
if let Some(&(end, u)) = self.runs.get(&start)
&& u == until
{
self.runs.remove(&start);
let (&bs, &be) = self
.blocks
.range(..=start)
.next_back()
.expect("a run's block");
self.blocks.remove(&bs);
if bs < start {
self.blocks.insert(bs, start);
}
if end < be {
self.blocks.insert(end, be);
}
}
}
}
fn free(&self, x: u32) -> u32 {
match self.blocks.range(..=x).next_back() {
Some((_, &end)) if end > x => end,
_ => x,
}
}
fn add(&mut self, start: u32, end: u32, until: u32) {
let mut over: Vec<(u32, u32, u32)> = Vec::new();
if let Some((&rs, &(re, ru))) = self.runs.range(..start).next_back()
&& re > start
{
over.push((rs, re, ru));
}
over.extend(
self.runs
.range(start..end)
.map(|(&rs, &(re, ru))| (rs, re, ru)),
);
let mut pieces = Vec::new();
let mut at = start;
for &(rs, re, ru) in &over {
self.runs.remove(&rs);
if rs < start {
pieces.push((rs, start, ru));
}
let (os, oe) = (rs.max(start), re.min(end));
if at < os {
pieces.push((at, os, until));
}
pieces.push((os, oe, ru.max(until)));
if re > end {
pieces.push((end, re, ru));
}
at = oe;
}
if at < end {
pieces.push((at, end, until));
}
for (ps, pe, pu) in pieces {
self.runs.insert(ps, (pe, pu));
self.ends.push(Reverse((pu, ps)));
}
let (mut bs, mut be) = (start, end);
if let Some((&s, &e)) = self.blocks.range(..=start).next_back()
&& e >= start
{
bs = s;
be = be.max(e);
self.blocks.remove(&s);
}
while let Some((&s, &e)) = self.blocks.range(bs..=be).next() {
self.blocks.remove(&s);
be = be.max(e);
}
self.blocks.insert(bs, be);
}
}
#[derive(Clone, Copy)]
struct Place {
index: u32,
count: u32,
type_index: u32,
type_count: u32,
}
fn case_insensitive_attr(name: &str) -> bool {
matches!(
name,
"accept"
| "accept-charset"
| "align"
| "alink"
| "axis"
| "bgcolor"
| "charset"
| "checked"
| "clear"
| "codetype"
| "color"
| "compact"
| "declare"
| "defer"
| "dir"
| "direction"
| "disabled"
| "enctype"
| "face"
| "frame"
| "hreflang"
| "http-equiv"
| "lang"
| "language"
| "link"
| "media"
| "method"
| "multiple"
| "nohref"
| "noresize"
| "noshade"
| "nowrap"
| "readonly"
| "rel"
| "rev"
| "rules"
| "scope"
| "scrolling"
| "selected"
| "shape"
| "target"
| "text"
| "type"
| "valign"
| "valuetype"
| "vlink"
)
}
fn is_space_char(c: char) -> bool {
matches!(c, ' ' | '\t' | '\n' | '\r' | '\x0C')
}
impl<'a> Cx<'a> {
fn new(doc: &'a Document, scope: Option<NodeId>, in_tree: NodeId, page: Option<Page>) -> Self {
let (shadow, host) = match doc.shadow_roots.is_empty() {
true => (NONE, NONE),
false => {
let root = doc.tree_root(in_tree);
doc.shadow_host(root).map_or((NONE, NONE), |h| (root, h))
}
};
Cx {
doc,
scope,
shadow,
host,
page,
pattern_budget: Cell::new(crate::pattern::SELECT_STEP_LIMIT),
deadline: None,
max_steps: u64::MAX,
limited: false,
steps: Cell::new(0),
timed_out: Cell::new(false),
places: RefCell::default(),
of_places: RefCell::default(),
has_seen: RefCell::default(),
nested_seen: RefCell::default(),
tables: RefCell::default(),
}
}
fn html_tag_of(&self, n: NodeId) -> Option<Tag> {
self.doc
.element(n)
.filter(|e| e.ns == Ns::Html)
.map(|e| e.tag)
}
fn table_of_cell(&self, cell: NodeId) -> Option<NodeId> {
if !matches!(self.html_tag_of(cell), Some(Tag::Td | Tag::Th)) {
return None;
}
let tr = self
.doc
.parent(cell)
.filter(|&p| self.html_tag_of(p) == Some(Tag::Tr))?;
let p = self.doc.parent(tr)?;
match self.html_tag_of(p)? {
Tag::Table => Some(p),
Tag::Thead | Tag::Tbody | Tag::Tfoot => self
.doc
.parent(p)
.filter(|&t| self.html_tag_of(t) == Some(Tag::Table)),
_ => None,
}
}
fn cell_columns(&self, cell: NodeId) -> Option<(Rc<Columns>, u32, u32)> {
let table = self.table_of_cell(cell)?;
let columns = self.columns(table);
let &(x, n) = columns.cells.get(&cell)?;
Some((columns, x, n))
}
fn columns(&self, table: NodeId) -> Rc<Columns> {
if let Some(c) = self.tables.borrow().get(&table) {
return c.clone();
}
let c = Rc::new(self.lay_out(table));
self.tables.borrow_mut().insert(table, c.clone());
c
}
fn span(&self, el: NodeId, name: &str, max: u32) -> u32 {
self.attr(el, name)
.and_then(parse_non_negative)
.filter(|&n| n > 0)
.map_or(1, |n| n.min(max))
}
fn lay_out(&self, table: NodeId) -> Columns {
let doc = self.doc;
let mut out = Columns::default();
let mut col_x = 0;
let mut rows_started = false;
let mut cover = Cover::default();
for child in doc.children(table) {
match self.html_tag_of(child) {
Some(Tag::Colgroup) if !rows_started => {
let mut has_cols = false;
for c in doc.children(child) {
if self.html_tag_of(c) == Some(Tag::Col) {
has_cols = true;
let n = self.span(c, "span", 1000);
out.col_index.insert(c, out.cols.len());
out.cols.push((c, col_x, n));
col_x += n;
}
}
if !has_cols {
col_x += self.span(child, "span", 1000);
}
}
Some(Tag::Tr) => {
rows_started = true;
self.lay_out_row(child, &mut cover, &mut out);
}
Some(Tag::Thead | Tag::Tbody | Tag::Tfoot) => {
rows_started = true;
cover = Cover::default();
for r in doc.children(child) {
if self.html_tag_of(r) == Some(Tag::Tr) {
self.lay_out_row(r, &mut cover, &mut out);
}
}
cover = Cover::default();
}
_ => {}
}
}
out.width = out.width.max(col_x);
out
}
fn lay_out_row(&self, tr: NodeId, cover: &mut Cover, out: &mut Columns) {
let row = cover.row;
cover.advance(row);
let mut x = 0;
for cell in self.doc.children(tr) {
if !matches!(self.html_tag_of(cell), Some(Tag::Td | Tag::Th)) {
continue;
}
x = cover.free(x);
let span = self.span(cell, "colspan", 1000);
let until = match self.attr(cell, "rowspan").and_then(parse_non_negative) {
Some(0) => u32::MAX,
n => row.saturating_add(n.map_or(1, |n| n.min(65534))),
};
cover.add(x, x + span, until);
out.cells.insert(cell, (x, span));
x += span;
out.width = out.width.max(x);
}
cover.row += 1;
}
fn place(&self, el: NodeId) -> Option<Place> {
if let Some(&p) = self.places.borrow().get(&el) {
return Some(p);
}
let doc = self.doc;
let parent = doc.parent(el)?;
let kids: Vec<NodeId> = doc
.children(parent)
.filter(|&k| doc.element(k).is_some())
.collect();
let mut types: Vec<(NodeId, u32)> = Vec::new();
let mut keyed = false;
let mut by_tag: IdMap<Tag, usize> = IdMap::default();
let mut by_name: HashMap<(u8, Tag, &str), usize> = HashMap::new();
fn file<'d>(
doc: &'d Document,
by_tag: &mut IdMap<Tag, usize>,
by_name: &mut HashMap<(u8, Tag, &'d str), usize>,
e: &'d crate::dom::Element,
t: usize,
) {
if e.ns == Ns::Html && e.tag != Tag::Other {
by_tag.insert(e.tag, t);
} else {
by_name.insert((e.ns as u8, e.tag, doc.element_name(e)), t);
}
}
let mut of_type = Vec::with_capacity(kids.len());
for &k in &kids {
let e = doc.element(k).unwrap();
let found = if !keyed {
types
.iter()
.position(|&(rep, _)| same_type(doc, doc.element(rep).unwrap(), e))
} else if e.ns == Ns::Html && e.tag != Tag::Other {
by_tag.get(&e.tag).copied()
} else {
by_name
.get(&(e.ns as u8, e.tag, doc.element_name(e)))
.copied()
};
let t = match found {
Some(t) => t,
None => {
types.push((k, 0));
if keyed {
file(doc, &mut by_tag, &mut by_name, e, types.len() - 1);
} else if types.len() > 16 {
keyed = true;
for (i, &(rep, _)) in types.iter().enumerate() {
let rep = doc.element(rep).unwrap();
file(doc, &mut by_tag, &mut by_name, rep, i);
}
}
types.len() - 1
}
};
types[t].1 += 1;
of_type.push((t, types[t].1));
}
let mut places = self.places.borrow_mut();
places.reserve(kids.len());
for (i, (&k, &(t, type_index))) in kids.iter().zip(&of_type).enumerate() {
places.insert(
k,
Place {
index: i as u32 + 1,
count: kids.len() as u32,
type_index,
type_count: types[t].1,
},
);
}
places.get(&el).copied()
}
fn of_place(&self, of: &SelectorList, el: NodeId) -> Option<(u32, u32)> {
let key = std::ptr::from_ref(of) as usize;
if let Some(&p) = self.of_places.borrow().get(&(key, el)) {
return Some(p);
}
let doc = self.doc;
let parent = doc.parent(el)?;
let kids: Vec<NodeId> = doc
.children(parent)
.filter(|&k| doc.element(k).is_some() && of.0.iter().any(|c| self.complex(c, k, k)))
.collect();
let mut places = self.of_places.borrow_mut();
for (i, &k) in kids.iter().enumerate() {
places.insert((key, k), (i as u32 + 1, kids.len() as u32));
}
places.get(&(key, el)).copied()
}
#[inline(never)]
fn nth_by_place(&self, el: NodeId, a: i32, b: i32, last: bool, of_type: bool) -> Option<bool> {
let pl = self.place(el)?;
let (index, count) = if of_type {
(pl.type_index, pl.type_count)
} else {
(pl.index, pl.count)
};
let index = if last { count - index + 1 } else { index };
Some(nth_matches(a as i64, b as i64, index as i64))
}
fn parent_element(&self, n: NodeId) -> Option<NodeId> {
self.doc
.parent(n)
.filter(|&p| self.doc.element(p).is_some())
}
fn prev_element(&self, n: NodeId) -> Option<NodeId> {
let mut at = self.doc.prev_sibling(n);
while let Some(p) = at {
if self.doc.element(p).is_some() {
return Some(p);
}
at = self.doc.prev_sibling(p);
}
None
}
fn next_element(&self, n: NodeId) -> Option<NodeId> {
let mut at = self.doc.next_sibling(n);
while let Some(p) = at {
if self.doc.element(p).is_some() {
return Some(p);
}
at = self.doc.next_sibling(p);
}
None
}
fn complex(&self, c: &Complex, el: NodeId, anchor: NodeId) -> bool {
if let Some(Simple::Pseudo(Pseudo::Slotted(arg))) = c.parts[0].0.0.first() {
return self.slotted(c, arg, el, anchor);
}
self.compound(&c.parts[0].0, el, anchor)
&& (c.parts.len() == 1 || self.complex_rest(c, el, anchor))
}
#[cold]
fn slotted(&self, c: &Complex, arg: &Compound, el: NodeId, anchor: NodeId) -> bool {
if self.shadow == NONE || self.doc.element(el).is_none() {
return false;
}
let mut slot = self.doc.assigned_slot(el);
while let Some(s) = slot {
if self.doc.tree_root(s) == self.shadow {
break;
}
slot = self.doc.assigned_slot(s);
}
let Some(slot) = slot else {
return false;
};
self.simples(&arg.0, el, anchor)
&& self.compound_of(&c.parts[0].0.0[1..], slot, anchor)
&& (c.parts.len() == 1 || self.complex_rest(c, slot, anchor))
}
#[inline(never)]
fn complex_rest(&self, c: &Complex, el: NodeId, anchor: NodeId) -> bool {
let parts = &c.parts;
if let [(_, combinator), (left, _)] = parts.as_slice() {
let mut at = self.step(*combinator, el);
while let Some(p) = at {
if self.compound(left, p, anchor) {
return true;
}
if matches!(combinator, Combinator::Child | Combinator::NextSibling) {
return false;
}
at = self.next_step(*combinator, el, p);
}
return false;
}
let mut inline = [0; 16];
let mut spilled;
let matched: &mut [NodeId] = if parts.len() <= inline.len() {
&mut inline
} else {
spilled = vec![0; parts.len()];
&mut spilled
};
matched[0] = el;
let Some(next) = self.step(parts[0].1, el) else {
return false;
};
let fence = matches!(parts.last(), Some((Compound(s), _)) if matches!(s.as_slice(), [Simple::Anchor]))
.then(|| (anchor, self.step(Combinator::Child, anchor)));
let fenced = |i: usize, at: NodeId| {
i + 1 < parts.len() && fence.is_some_and(|(a, up)| at == a || Some(at) == up)
};
let (mut i, mut at) = (1, next);
loop {
let mut fail = if fenced(i, at) {
Fail::exhausted(parts[i - 1].1)
} else if !self.compound(&parts[i].0, at, anchor) {
Fail::Sibling
} else if i + 1 == parts.len() {
return true;
} else {
let combinator = parts[i].1;
match self.step(combinator, at) {
Some(next) => {
matched[i] = at;
(i, at) = (i + 1, next);
continue;
}
None => Fail::exhausted(combinator),
}
};
loop {
if i == 0 || fail == Fail::Global {
return false;
}
i -= 1;
let combinator = parts[i].1;
let retry = match (fail, combinator) {
(_, Combinator::Child) => {
fail = Fail::Descendant;
false
}
(_, Combinator::NextSibling)
| (Fail::Descendant, Combinator::SubsequentSibling) => false,
_ => true,
};
if retry {
if let Some(next) = self.next_step(combinator, matched[i], at) {
(i, at) = (i + 1, next);
break;
}
fail = Fail::exhausted(combinator);
}
at = matched[i];
}
}
}
#[inline]
fn step(&self, combinator: Combinator, el: NodeId) -> Option<NodeId> {
if el == self.host {
return None;
}
match combinator {
Combinator::Child | Combinator::Descendant => {
let parent = self.doc.parent(el);
if parent == Some(self.shadow) {
Some(self.host)
} else {
parent
}
}
Combinator::NextSibling | Combinator::SubsequentSibling => self.prev_element(el),
Combinator::Column => self.col_after(el, None),
Combinator::None => None,
}
}
fn next_step(&self, combinator: Combinator, origin: NodeId, prev: NodeId) -> Option<NodeId> {
match combinator {
Combinator::Column => self.col_after(origin, Some(prev)),
_ => self.step(combinator, prev),
}
}
fn col_after(&self, cell: NodeId, prev: Option<NodeId>) -> Option<NodeId> {
let (t, x, n) = self.cell_columns(cell)?;
let i = match prev {
None => t.cols.partition_point(|&(_, cx, cn)| cx + cn <= x),
Some(p) => t.col_index.get(&p)? + 1,
};
t.cols
.get(i)
.filter(|&&(_, cx, _)| cx < x + n)
.map(|&(col, ..)| col)
}
#[cold]
#[inline(never)]
fn out_of_time(&self) -> bool {
let steps = self.steps.get().saturating_add(1);
self.steps.set(steps);
if steps > self.max_steps
|| steps.is_multiple_of(1024) && self.deadline.is_some_and(|d| Instant::now() >= d)
{
self.timed_out.set(true);
}
self.timed_out.get()
}
fn limit(&mut self, options: &MatchOptions<'_>) {
self.deadline = deadline(options);
self.max_steps = options.max_steps.unwrap_or(u64::MAX);
self.limited = self.deadline.is_some() || options.max_steps.is_some();
}
fn compound(&self, compound: &Compound, el: NodeId, anchor: NodeId) -> bool {
self.compound_of(&compound.0, el, anchor)
}
fn compound_of(&self, simples: &[Simple], el: NodeId, anchor: NodeId) -> bool {
if el == self.host
&& !matches!(simples, [Simple::Anchor])
&& (simples.is_empty()
|| !simples.iter().all(|s| {
matches!(
s,
Simple::Pseudo(
Pseudo::Host(_)
| Pseudo::HostContext(_)
| Pseudo::Is(_)
| Pseudo::Where(_)
)
)
}))
{
return false;
}
self.simples(simples, el, anchor)
}
fn simples(&self, simples: &[Simple], el: NodeId, anchor: NodeId) -> bool {
if self.limited && self.out_of_time() {
return false;
}
if matches!(simples, [Simple::Anchor]) {
return el == anchor;
}
let Some(e) = self.doc.element(el) else {
return false;
};
simples.iter().all(|s| match s {
Simple::Type { lower, exact, tag } => {
if e.ns == Ns::Html {
if *tag != Tag::Other || e.tag != Tag::Other {
e.tag == *tag
} else {
self.doc.element_name(e) == lower
}
} else if e.ns == Ns::Xml {
xml_local(self.doc.element_name(e)).eq_ignore_ascii_case(lower)
} else {
self.doc.element_name(e) == exact
}
}
Simple::Id(id) => self.attr(el, "id").is_some_and(|v| self.quirks_eq(v, id)),
Simple::Class(class) => self.attr(el, "class").is_some_and(|v| {
v.split(is_space_char)
.any(|c| !c.is_empty() && self.quirks_eq(c, class))
}),
Simple::Attr(a) => self.attr_matches(el, e.ns, a),
Simple::Pseudo(p) => self.pseudo(p, el, anchor),
Simple::Anchor => el == anchor,
Simple::Ns(ns) => e.ns == *ns,
})
}
fn quirks_eq(&self, a: &str, b: &str) -> bool {
if self.doc.quirks() == Quirks::Quirks {
a.eq_ignore_ascii_case(b)
} else {
a == b
}
}
fn lang(&self, el: NodeId) -> Option<&str> {
let mut at = Some(el);
while let Some(n) = at {
let mut plain = None;
for (ns, name, value) in self.doc.attrs(n) {
match (ns, name) {
(AttrNs::Xml, "lang") => return Some(value),
(AttrNs::None, "lang") => plain = Some(value),
_ => {}
}
}
if plain.is_some() {
return plain;
}
at = self.doc.parent(n);
}
None
}
fn is_rtl(&self, el: NodeId) -> bool {
let mut at = Some(el);
while let Some(n) = at {
let Some(e) = self.doc.element(n) else {
return false;
};
if e.ns == Ns::Html {
match self.dir(n).as_deref() {
Some("ltr") => return false,
Some("rtl") => return true,
Some("auto") => return self.auto_rtl(n),
_ if self.doc.lower_name(n) == Some("bdi") => return self.auto_rtl(n),
_ => {}
}
}
at = self.doc.parent(n);
}
false
}
fn dir(&self, el: NodeId) -> Option<String> {
self.attr(el, "dir")
.map(|d| d.to_ascii_lowercase())
.filter(|d| matches!(d.as_str(), "ltr" | "rtl" | "auto"))
}
fn auto_rtl(&self, el: NodeId) -> bool {
let tag = self.doc.element(el).map(|e| e.tag);
if tag == Some(Tag::Textarea) {
return first_strong_rtl(&self.doc.text(el)).unwrap_or(false);
}
if tag == Some(Tag::Input) {
let text_field = self.attr(el, "type").is_none_or(|t| {
matches!(
t.to_ascii_lowercase().as_str(),
"text" | "search" | "tel" | "url" | "email"
)
});
return text_field
&& first_strong_rtl(self.attr(el, "value").unwrap_or("")).unwrap_or(false);
}
let mut stack: Vec<NodeId> = self.doc.children(el).collect();
stack.reverse();
while let Some(n) = stack.pop() {
match self.doc.kind(n) {
crate::Kind::Text(t) => {
if let Some(rtl) = first_strong_rtl(t) {
return rtl;
}
}
crate::Kind::Element { ns, .. } => {
let skip = ns == Ns::Html
&& (self.dir(n).is_some()
|| matches!(
self.doc.element(n).map(|e| e.tag),
Some(Tag::Script | Tag::Style | Tag::Textarea)
)
|| self.doc.lower_name(n) == Some("bdi"));
if !skip {
let at = stack.len();
stack.extend(self.doc.children(n));
stack[at..].reverse();
}
}
_ => {}
}
}
false
}
fn input_type(&self, el: NodeId, types: &[&str]) -> bool {
self.attr(el, "type")
.is_some_and(|t| types.iter().any(|w| t.eq_ignore_ascii_case(w)))
}
fn html_tag(&self, n: NodeId, tag: Tag) -> bool {
self.doc
.element(n)
.is_some_and(|e| e.ns == Ns::Html && e.tag == tag)
}
fn html_named(&self, n: NodeId, name: &str) -> bool {
self.doc.element(n).is_some_and(|e| e.ns == Ns::Html)
&& self.doc.lower_name(n) == Some(name)
}
fn tree_of(&self, el: NodeId) -> Vec<NodeId> {
let mut root = el;
while let Some(p) = self.doc.parent(root) {
root = p;
}
let (mut out, mut stack) = (Vec::new(), vec![root]);
while let Some(n) = stack.pop() {
out.push(n);
let at = stack.len();
stack.extend(self.doc.children(n));
stack[at..].reverse();
}
out
}
fn form_owner(&self, el: NodeId) -> Option<NodeId> {
if let Some(id) = self.attr(el, "form") {
return self
.tree_of(el)
.into_iter()
.find(|&n| self.doc.element(n).is_some() && self.attr(n, "id") == Some(id))
.filter(|&f| self.html_tag(f, Tag::Form));
}
let mut at = self.parent_element(el);
while let Some(p) = at {
if self.html_tag(p, Tag::Form) {
return Some(p);
}
at = self.parent_element(p);
}
None
}
fn submit_button(&self, el: NodeId, tag: Tag) -> bool {
match tag {
Tag::Button => self.attr(el, "type").is_none_or(|t| {
!t.eq_ignore_ascii_case("reset") && !t.eq_ignore_ascii_case("button")
}),
Tag::Input => self.input_type(el, &["submit", "image"]),
_ => false,
}
}
fn default_button(&self, el: NodeId, tag: Tag) -> bool {
if !self.submit_button(el, tag) {
return false;
}
let Some(form) = self.form_owner(el) else {
return false;
};
self.tree_of(el).into_iter().find(|&n| {
self.doc.element(n).is_some_and(|e| {
e.ns == Ns::Html && self.submit_button(n, e.tag) && self.form_owner(n) == Some(form)
})
}) == Some(el)
}
fn radio_group_unchecked(&self, el: NodeId) -> bool {
if self.attr(el, "checked").is_some() {
return false;
}
let Some(name) = self.attr(el, "name").filter(|n| !n.is_empty()) else {
return true;
};
let form = self.form_owner(el);
!self.tree_of(el).into_iter().any(|n| {
self.html_tag(n, Tag::Input)
&& self.input_type(n, &["radio"])
&& self.attr(n, "name") == Some(name)
&& self.attr(n, "checked").is_some()
&& self.form_owner(n) == form
})
}
fn in_range(&self, el: NodeId) -> Option<bool> {
let typ = self.attr(el, "type")?.to_ascii_lowercase();
let read = |name: &str| self.attr(el, name).and_then(|v| input_number(&typ, v));
let (min, max) = match typ.as_str() {
"range" => (read("min").or(Some(0.0)), read("max").or(Some(100.0))),
"number" | "date" | "month" | "week" | "time" | "datetime-local" => {
(read("min"), read("max"))
}
_ => return None,
};
if min.is_none() && max.is_none() {
return None;
}
let in_datalist = {
let mut at = self.parent_element(el);
let mut found = false;
while let Some(p) = at {
if self.html_named(p, "datalist") {
found = true;
break;
}
at = self.parent_element(p);
}
found
};
if self.disabled(el, Tag::Input)
|| (typ != "range" && self.attr(el, "readonly").is_some())
|| in_datalist
{
return None;
}
if typ == "range" {
return Some(true);
}
let Some(value) = read("value") else {
return Some(true);
};
Some(match (min, max) {
(Some(lo), Some(hi)) if typ == "time" && lo > hi => value >= lo || value <= hi,
_ => min.is_none_or(|lo| value >= lo) && max.is_none_or(|hi| value <= hi),
})
}
fn valid(&self, el: NodeId, tag: Tag) -> Option<bool> {
match tag {
Tag::Form => Some(!self.tree_of(el).into_iter().any(|n| {
self.doc.element(n).is_some_and(|e| e.ns == Ns::Html)
&& self.form_owner(n) == Some(el)
&& self.control_valid(n) == Some(false)
})),
Tag::Fieldset => {
let mut stack: Vec<NodeId> = self.doc.children(el).collect();
while let Some(n) = stack.pop() {
if self.control_valid(n) == Some(false) {
return Some(false);
}
stack.extend(self.doc.children(n));
}
Some(true)
}
_ => self.control_valid(el),
}
}
fn control_valid(&self, el: NodeId) -> Option<bool> {
let e = self.doc.element(el)?;
if e.ns != Ns::Html || self.disabled(el, e.tag) || self.in_datalist(el) {
return None;
}
let required = self.attr(el, "required").is_some();
match e.tag {
Tag::Input => {
let typ = input_type_state(self.attr(el, "type"));
if matches!(typ, "hidden" | "reset" | "button")
|| (readonly_applies(typ) && self.attr(el, "readonly").is_some())
{
return None;
}
Some(self.input_valid(el, typ, required))
}
Tag::Textarea => {
if self.attr(el, "readonly").is_some() {
return None;
}
Some(!required || !self.doc.text(el).is_empty())
}
Tag::Select => Some(!required || self.select_has_value(el)),
Tag::Button => self.submit_button(el, Tag::Button).then_some(true),
_ => None,
}
}
fn input_valid(&self, el: NodeId, typ: &str, required: bool) -> bool {
match typ {
"checkbox" => !required || self.attr(el, "checked").is_some(),
"radio" => !self.radio_value_missing(el),
"file" => !required,
"submit" | "image" | "color" | "range" => true,
_ => {
let value = sanitized(
typ,
self.attr(el, "value").unwrap_or(""),
self.attr(el, "multiple").is_some(),
);
if value.is_empty() {
return !required;
}
let multiple = typ == "email" && self.attr(el, "multiple").is_some();
if !self.pattern_fits(el, typ, &value, multiple) {
return false;
}
match typ {
"email" if self.attr(el, "multiple").is_some() => {
value.split(',').all(valid_email)
}
"email" => valid_email(&value),
"url" => url::Url::parse(&value).is_ok(),
"number" | "date" | "month" | "week" | "time" | "datetime-local" => {
self.in_range(el) != Some(false) && self.step_fits(el, typ, &value)
}
_ => true,
}
}
}
}
fn pattern_fits(&self, el: NodeId, typ: &str, value: &str, multiple: bool) -> bool {
if !matches!(
typ,
"text" | "search" | "tel" | "url" | "email" | "password"
) {
return true;
}
let Some(pattern) = self.attr(el, "pattern").and_then(Pattern::compile) else {
return true;
};
if multiple {
value
.split(',')
.all(|v| pattern.matches(v, &self.pattern_budget))
} else {
pattern.matches(value, &self.pattern_budget)
}
}
fn step_fits(&self, el: NodeId, typ: &str, value: &str) -> bool {
let (default, scale) = match typ {
"week" => (1.0, 7.0),
"time" | "datetime-local" => (60.0, 1000.0),
_ => (1.0, 1.0),
};
let step = match self.attr(el, "step") {
Some(s) if s.eq_ignore_ascii_case("any") => return true,
Some(s) => parse_float_value(s).filter(|&s| s > 0.0).unwrap_or(default),
None => default,
};
let (Some(value), Some(base)) = (
input_number(typ, value),
self.attr(el, "min").and_then(|m| input_number(typ, m)),
) else {
return true;
};
let steps = (value - base) / (step * scale);
(steps - steps.round()).abs() < 1e-9
}
fn radio_value_missing(&self, el: NodeId) -> bool {
let Some(name) = self.attr(el, "name").filter(|n| !n.is_empty()) else {
return self.attr(el, "required").is_some() && self.attr(el, "checked").is_none();
};
let form = self.form_owner(el);
let group: Vec<NodeId> = self
.tree_of(el)
.into_iter()
.filter(|&n| {
self.html_tag(n, Tag::Input)
&& self.input_type(n, &["radio"])
&& self.attr(n, "name") == Some(name)
&& self.form_owner(n) == form
})
.collect();
group.iter().any(|&n| self.attr(n, "required").is_some())
&& group.iter().all(|&n| self.attr(n, "checked").is_none())
}
fn select_has_value(&self, el: NodeId) -> bool {
let mut options = Vec::new();
let mut stack: Vec<NodeId> = self.doc.children(el).collect();
stack.reverse();
while let Some(n) = stack.pop() {
if self.html_tag(n, Tag::Option) {
options.push(n);
} else if self.html_tag(n, Tag::Optgroup) {
let at = stack.len();
stack.extend(self.doc.children(n));
stack[at..].reverse();
}
}
let marked = |n: &&NodeId| self.attr(**n, "selected").is_some();
let multiple = self.attr(el, "multiple").is_some();
let size = self
.attr(el, "size")
.and_then(parse_non_negative)
.filter(|&s| s > 0)
.unwrap_or(if multiple { 4 } else { 1 });
if multiple {
return options.iter().any(|n| marked(&n));
}
let selected = options.iter().rev().find(marked).or_else(|| {
options
.iter()
.filter(|_| size == 1)
.find(|&&n| self.attr(n, "disabled").is_none() && !self.disabled(n, Tag::Option))
});
let Some(&selected) = selected else {
return false;
};
let placeholder = size == 1
&& options.first() == Some(&selected)
&& self.doc.parent(selected) == Some(el)
&& self.option_value(selected).is_empty();
!placeholder
}
fn option_value(&self, el: NodeId) -> String {
match self.attr(el, "value") {
Some(v) => v.to_string(),
None => self
.doc
.text(el)
.split_ascii_whitespace()
.collect::<Vec<_>>()
.join(" "),
}
}
fn in_datalist(&self, el: NodeId) -> bool {
let mut at = self.parent_element(el);
while let Some(p) = at {
if self.html_named(p, "datalist") {
return true;
}
at = self.parent_element(p);
}
false
}
fn attr(&self, el: NodeId, name: &str) -> Option<&str> {
self.doc
.attrs(el)
.find(|(ns, n, _)| *ns == AttrNs::None && *n == name)
.map(|(_, _, v)| v)
}
fn attr_matches(&self, el: NodeId, ns: Ns, a: &AttrSelector) -> bool {
let doc = self.doc;
if ns == Ns::Xml {
return self.xml_attr_matches(el, a);
}
let html = ns == Ns::Html;
let insensitive = match a.case {
Case::Insensitive => true,
Case::Sensitive => false,
Case::Default => html && case_insensitive_attr(&a.lower),
};
let want = if html { &a.lower } else { &a.exact };
doc.attrs_of(el).iter().any(|attr| {
let name = doc.written_name(ns, attr);
let name = match attr.ns {
AttrNs::None => name,
_ => name.split_once(':').map_or(name, |(_, local)| local),
};
let in_ns = match a.in_ns {
Some(ns) => attr.ns == ns,
None => attr.ns == AttrNs::None || a.any_ns,
};
in_ns
&& name == want.as_str()
&& (a.op == AttrOp::Exists
|| value_matches(a.op, doc.str(attr.value), &a.value, insensitive))
})
}
fn xml_attr_matches(&self, el: NodeId, a: &AttrSelector) -> bool {
let doc = self.doc;
let range = doc
.element(el)
.map_or(0..0, |e| e.attrs.start as usize..e.attrs.end as usize);
let attrs = &doc.attrs[range];
let local = |attr: &crate::dom::Attr| xml_local(doc.str(attr.name));
let found = attrs
.iter()
.find(|attr| local(attr) == a.exact)
.or_else(|| {
attrs
.iter()
.find(|attr| local(attr).eq_ignore_ascii_case(&a.lower))
});
let insensitive = a.case == Case::Insensitive;
found.is_some_and(|attr| {
a.op == AttrOp::Exists
|| value_matches(a.op, doc.str(attr.value), &a.value, insensitive)
})
}
fn pseudo(&self, p: &Pseudo, el: NodeId, anchor: NodeId) -> bool {
let doc = self.doc;
let e = doc.element(el).expect("an element");
let html = e.ns == Ns::Html;
let tag = if html { e.tag } else { Tag::Other };
match p {
Pseudo::Not(list) => !list.0.iter().any(|c| self.nested(c, el, anchor)),
Pseudo::Is(list) | Pseudo::Where(list) => {
list.0.iter().any(|c| self.nested(c, el, anchor))
}
Pseudo::Has(list) => list.0.iter().any(|c| self.has(c, el)),
Pseudo::Nth {
a,
b,
last,
of_type,
of,
} => {
let same = |other: NodeId| {
if *of_type {
same_type(doc, doc.element(other).unwrap(), e)
} else if let Some(of) = of {
of.0.iter().any(|c| self.complex(c, other, other))
} else {
true
}
};
if !same(el) {
return false;
}
if let Some(of) = of
&& let Some((index, count)) = self.of_place(of, el)
{
let index = if *last { count - index + 1 } else { index };
return nth_matches(*a as i64, *b as i64, index as i64);
}
if *a > 0
&& let Some(m) = self.nth_by_place(el, *a, *b, *last, *of_type)
{
return m;
}
let mut walked = 0;
let mut index = 1i64;
let mut at = if *last {
self.next_element(el)
} else {
self.prev_element(el)
};
while let Some(s) = at {
walked += 1;
if walked > 32
&& let Some(m) = self.nth_by_place(el, *a, *b, *last, *of_type)
{
return m;
}
if same(s) {
index += 1;
if *a <= 0 && index > *b as i64 {
return false;
}
}
at = if *last {
self.next_element(s)
} else {
self.prev_element(s)
};
}
nth_matches(*a as i64, *b as i64, index)
}
Pseudo::Only { of_type } => {
let same =
|other: NodeId| !*of_type || same_type(doc, doc.element(other).unwrap(), e);
let mut walked = 0;
for step in [Self::prev_element, Self::next_element] {
let mut at = step(self, el);
while let Some(s) = at {
walked += 1;
if walked > 32
&& let Some(pl) = self.place(el)
{
return pl.type_count == 1;
}
if same(s) {
return false;
}
at = step(self, s);
}
}
true
}
Pseudo::Empty => doc.children(el).all(|c| {
matches!(
doc.nodes[c as usize].data,
Data::Comment(_) | Data::ProcessingInstruction { .. }
) || matches!(doc.kind(c), crate::Kind::Text(t) if t.is_empty())
}),
Pseudo::Root => doc
.parent(el)
.is_some_and(|p| matches!(doc.nodes[p as usize].data, Data::Document)),
Pseudo::Scope => match self.scope {
Some(s) if doc.element(s).is_some() => el == s,
_ => doc
.parent(el)
.is_some_and(|p| matches!(doc.nodes[p as usize].data, Data::Document)),
},
Pseudo::AnyLink => matches!(tag, Tag::A | Tag::Area) && self.attr(el, "href").is_some(),
Pseudo::Target => self.page.as_ref().is_some_and(|p| p.target == Some(el)),
Pseudo::TargetWithin => self.page.as_ref().and_then(|p| p.target).is_some_and(|t| {
let mut at = Some(t);
while let Some(n) = at {
if n == el {
return true;
}
at = self.doc.parent(n);
}
false
}),
Pseudo::LocalLink => {
matches!(tag, Tag::A | Tag::Area)
&& self.page.as_ref().is_some_and(|p| {
self.attr(el, "href")
.and_then(|href| p.base.join(href).ok())
.is_some_and(|mut link| {
link.set_fragment(None);
link == p.url
})
})
}
Pseudo::Checked => match tag {
Tag::Input => {
self.attr(el, "checked").is_some()
&& self.attr(el, "type").is_some_and(|t| {
t.eq_ignore_ascii_case("checkbox") || t.eq_ignore_ascii_case("radio")
})
}
Tag::Option => self.attr(el, "selected").is_some(),
_ => false,
},
Pseudo::Default => match tag {
Tag::Input if self.input_type(el, &["checkbox", "radio"]) => {
self.attr(el, "checked").is_some()
}
Tag::Option => self.attr(el, "selected").is_some(),
Tag::Button | Tag::Input => self.default_button(el, tag),
_ => false,
},
Pseudo::Indeterminate => match tag {
Tag::Input if self.input_type(el, &["radio"]) => self.radio_group_unchecked(el),
_ => self.html_named(el, "progress") && self.attr(el, "value").is_none(),
},
Pseudo::InRange => tag == Tag::Input && self.in_range(el) == Some(true),
Pseudo::OutOfRange => tag == Tag::Input && self.in_range(el) == Some(false),
Pseudo::Valid => self.valid(el, tag) == Some(true),
Pseudo::Invalid => self.valid(el, tag) == Some(false),
Pseudo::Disabled => self.disabled(el, tag),
Pseudo::Enabled => self.form_control(tag) && !self.disabled(el, tag),
Pseudo::Required => {
matches!(tag, Tag::Input | Tag::Select | Tag::Textarea)
&& self.attr(el, "required").is_some()
}
Pseudo::Optional => {
matches!(tag, Tag::Input | Tag::Select | Tag::Textarea)
&& self.attr(el, "required").is_none()
}
Pseudo::ReadWrite => self.read_write(el, tag),
Pseudo::ReadOnly => !self.read_write(el, tag),
Pseudo::PlaceholderShown => match tag {
Tag::Input => {
self.attr(el, "placeholder").is_some()
&& self.attr(el, "value").is_none_or(str::is_empty)
}
Tag::Textarea => self.attr(el, "placeholder").is_some() && doc.text(el).is_empty(),
_ => false,
},
Pseudo::Blank => match tag {
Tag::Input => {
text_entry(input_type_state(self.attr(el, "type")))
&& self.attr(el, "value").is_none_or(str::is_empty)
}
Tag::Textarea => doc.text(el).is_empty(),
_ => false,
},
Pseudo::Defined => {
!(html
&& (self.attr(el, "is").is_some()
|| doc.lower_name(el).is_some_and(custom_element_name)))
}
Pseudo::Lang(ranges) => self.lang(el).is_some_and(|tag| {
let tag = tag.to_ascii_lowercase();
ranges.iter().any(|range| lang_matches(range, &tag))
}),
Pseudo::Dir(rtl) => self.is_rtl(el) == *rtl,
Pseudo::Heading(levels) => {
let level = match tag {
Tag::H1 => 1,
Tag::H2 => 2,
Tag::H3 => 3,
Tag::H4 => 4,
Tag::H5 => 5,
Tag::H6 => 6,
_ => return false,
};
levels.is_empty() || levels.contains(&level)
}
Pseudo::Never | Pseudo::Element => false,
Pseudo::Host(arg) => {
el == self.host && arg.as_ref().is_none_or(|c| self.simples(&c.0, el, anchor))
}
Pseudo::HostContext(c) => {
el == self.host && {
let mut at = Some(el);
while let Some(n) = at {
if doc.element(n).is_some() && self.simples(&c.0, n, anchor) {
return true;
}
at = doc.shadow_including_parent(n);
}
false
}
}
Pseudo::Slotted(_) => false,
Pseudo::NthCol { a, b, last } => self.cell_columns(el).is_some_and(|(t, x, n)| {
let (lo, hi) = if *last {
(t.width - (x + n) + 1, t.width - x)
} else {
(x + 1, x + n)
};
nth_in_range(*a as i64, *b as i64, lo as i64, hi as i64)
}),
}
}
fn nested(&self, c: &Complex, el: NodeId, anchor: NodeId) -> bool {
if c.parts.len() == 1 {
return self.complex(c, el, anchor);
}
let key = (std::ptr::from_ref(c) as usize, el);
if let Some(&known) = self.nested_seen.borrow().get(&key) {
return known;
}
let found = self.complex(c, el, anchor);
self.nested_seen.borrow_mut().insert(key, found);
found
}
fn has(&self, c: &Complex, el: NodeId) -> bool {
let doc = self.doc;
let first = c.parts[c.parts.len() - 2].1;
if let [(compound, _), _] = c.parts.as_slice()
&& first != Combinator::Column
{
let key = std::ptr::from_ref(c) as usize;
return match first {
Combinator::Child => doc
.children(el)
.any(|k| doc.element(k).is_some() && self.compound(compound, k, el)),
Combinator::NextSibling => self
.next_element(el)
.is_some_and(|s| self.compound(compound, s, el)),
Combinator::SubsequentSibling => self.later_holds(key, compound, el),
_ => self.below_holds(key, compound, el),
};
}
let key = std::ptr::from_ref(c) as usize;
let before = match first {
Combinator::Descendant => doc.parent(el),
Combinator::SubsequentSibling => self.prev_element(el),
_ => None,
};
let remember = matches!(
first,
Combinator::Descendant | Combinator::SubsequentSibling
);
if before.is_some_and(|b| self.has_seen.borrow().get(&(key, b)) == Some(&false)) {
self.has_seen.borrow_mut().insert((key, el), false);
return false;
}
let found = self.has_anywhere(c, el, first);
if remember {
self.has_seen.borrow_mut().insert((key, el), found);
}
found
}
fn has_anywhere(&self, c: &Complex, el: NodeId, first: Combinator) -> bool {
let doc = self.doc;
let mut stack: Vec<NodeId> = Vec::new();
match first {
Combinator::NextSibling | Combinator::SubsequentSibling => {
let mut at = self.next_element(el);
while let Some(s) = at {
stack.push(s);
if self.found_below(c, el, &mut stack) {
return true;
}
at = self.next_element(s);
}
return false;
}
Combinator::Column => {
let table = doc.parent(el).and_then(|g| doc.parent(g));
if self.html_tag_of(el) == Some(Tag::Col)
&& let Some(t) = table.filter(|&t| self.html_tag_of(t) == Some(Tag::Table))
{
push_children_reversed(doc, t, &mut stack);
}
}
_ => push_children_reversed(doc, el, &mut stack),
}
self.found_below(c, el, &mut stack)
}
fn found_below(&self, c: &Complex, el: NodeId, stack: &mut Vec<NodeId>) -> bool {
let doc = self.doc;
while let Some(n) = stack.pop() {
if doc.element(n).is_none() {
continue;
}
if self.complex(c, n, el) {
return true;
}
push_children_reversed(doc, n, stack);
}
false
}
fn below_holds(&self, key: usize, compound: &Compound, el: NodeId) -> bool {
let doc = self.doc;
if self.has_seen.borrow().get(&(key, el)) == Some(&false) {
return false;
}
let mut stack: Vec<(NodeId, bool)> = Vec::new();
let at = stack.len();
stack.extend(doc.children(el).map(|k| (k, false)));
stack[at..].reverse();
while let Some((n, done)) = stack.pop() {
if done {
self.has_seen.borrow_mut().insert((key, n), false);
continue;
}
if doc.element(n).is_none() {
continue;
}
let known = self.has_seen.borrow().get(&(key, n)).copied();
if known == Some(false) {
continue;
}
if known == Some(true) || self.compound(compound, n, el) {
let mut seen = self.has_seen.borrow_mut();
let mut up = Some(n);
while let Some(u) = up {
seen.insert((key, u), true);
up = doc.parent(u).filter(|_| u != el);
}
return true;
}
stack.push((n, true));
let at = stack.len();
stack.extend(doc.children(n).map(|k| (k, false)));
stack[at..].reverse();
}
false
}
fn later_holds(&self, key: usize, compound: &Compound, el: NodeId) -> bool {
let mut walked = Vec::new();
let mut at = self.next_element(el);
let found = loop {
let Some(s) = at else { break false };
if let Some(&known) = self.has_seen.borrow().get(&(key, s)) {
break known;
}
walked.push(s);
if self.compound(compound, s, el) {
break true;
}
at = self.next_element(s);
};
let mut seen = self.has_seen.borrow_mut();
for s in walked {
seen.insert((key, s), found);
}
found
}
fn form_control(&self, tag: Tag) -> bool {
matches!(
tag,
Tag::Button
| Tag::Input
| Tag::Select
| Tag::Textarea
| Tag::Optgroup
| Tag::Option
| Tag::Fieldset
)
}
fn disabled(&self, el: NodeId, tag: Tag) -> bool {
let doc = self.doc;
match tag {
Tag::Optgroup => self.attr(el, "disabled").is_some(),
Tag::Option => {
self.attr(el, "disabled").is_some()
|| self.parent_element(el).is_some_and(|p| {
doc.element(p)
.is_some_and(|e| e.ns == Ns::Html && e.tag == Tag::Optgroup)
&& self.attr(p, "disabled").is_some()
})
}
Tag::Button | Tag::Input | Tag::Select | Tag::Textarea | Tag::Fieldset => {
if self.attr(el, "disabled").is_some() {
return true;
}
let mut child = el;
let mut at = self.parent_element(el);
while let Some(p) = at {
let pe = doc.element(p).unwrap();
if pe.ns == Ns::Html
&& pe.tag == Tag::Fieldset
&& self.attr(p, "disabled").is_some()
{
let first_legend = doc.children(p).find(|&c| {
doc.element(c).is_some_and(|e| {
e.ns == Ns::Html && doc.element_name(e) == "legend"
})
});
if first_legend != Some(child) {
return true;
}
}
child = p;
at = self.parent_element(p);
}
false
}
_ => false,
}
}
fn read_write(&self, el: NodeId, tag: Tag) -> bool {
match tag {
Tag::Input => {
let typ = self.attr(el, "type").unwrap_or("text").to_ascii_lowercase();
let mutable = matches!(
typ.as_str(),
"text"
| "search"
| "url"
| "tel"
| "email"
| "password"
| "date"
| "month"
| "week"
| "time"
| "datetime-local"
| "number"
| ""
);
mutable && self.attr(el, "readonly").is_none() && !self.disabled(el, tag)
}
Tag::Textarea => self.attr(el, "readonly").is_none() && !self.disabled(el, tag),
_ => self.editable(el),
}
}
fn editable(&self, el: NodeId) -> bool {
let mut at = Some(el);
while let Some(n) = at {
if let Some(v) = self.attr(n, "contenteditable") {
return !v.eq_ignore_ascii_case("false");
}
at = self.parent_element(n);
}
false
}
}
fn same_type(doc: &Document, a: &crate::dom::Element, b: &crate::dom::Element) -> bool {
a.ns == b.ns
&& if a.tag != Tag::Other || b.tag != Tag::Other {
a.tag == b.tag && (a.ns == Ns::Html || doc.element_name(a) == doc.element_name(b))
} else {
doc.element_name(a) == doc.element_name(b)
}
}
fn xml_local(name: &str) -> &str {
name.split_once(':').map_or(name, |(_, local)| local)
}
fn nth_matches(a: i64, b: i64, index: i64) -> bool {
if a == 0 {
return index == b;
}
let diff = index - b;
diff % a == 0 && diff / a >= 0
}
fn nth_in_range(a: i64, b: i64, lo: i64, hi: i64) -> bool {
match a.cmp(&0) {
std::cmp::Ordering::Equal => (lo..=hi).contains(&b),
std::cmp::Ordering::Greater => {
let from = lo.max(b);
from + (b - from).rem_euclid(a) <= hi
}
std::cmp::Ordering::Less => {
let to = hi.min(b);
to - (to - b).rem_euclid(-a) >= lo
}
}
}
fn value_matches(op: AttrOp, value: &str, want: &str, insensitive: bool) -> bool {
let eq = |x: &str, y: &str| {
if insensitive {
x.eq_ignore_ascii_case(y)
} else {
x == y
}
};
match op {
AttrOp::Exists => true,
AttrOp::Equals => eq(value, want),
AttrOp::Includes => {
!want.is_empty()
&& !want.contains(is_space_char)
&& value.split(is_space_char).any(|w| eq(w, want))
}
AttrOp::DashMatch => {
eq(value, want)
|| (value.len() > want.len()
&& value.as_bytes()[want.len()] == b'-'
&& value.is_char_boundary(want.len())
&& eq(&value[..want.len()], want))
}
AttrOp::Prefix => {
!want.is_empty()
&& value.len() >= want.len()
&& value.is_char_boundary(want.len())
&& eq(&value[..want.len()], want)
}
AttrOp::Suffix => {
!want.is_empty()
&& value.len() >= want.len()
&& value.is_char_boundary(value.len() - want.len())
&& eq(&value[value.len() - want.len()..], want)
}
AttrOp::Substring => {
!want.is_empty()
&& if insensitive {
value
.to_ascii_lowercase()
.contains(&want.to_ascii_lowercase())
} else {
value.contains(want)
}
}
}
}
#[cfg(test)]
mod nth_range_tests {
#[test]
fn nth_in_range_agrees_with_each_position() {
for a in -4..=4 {
for b in -6..=8 {
for lo in 1..=7 {
for hi in lo..=9 {
let each = (lo..=hi).any(|i| super::nth_matches(a, b, i));
assert_eq!(
super::nth_in_range(a, b, lo, hi),
each,
"{a}n+{b} in {lo}..={hi}"
);
}
}
}
}
}
}