use crate::fxhash::{FxHashMap, FxHashSet};
use std::hash::{Hash, Hasher};
struct Hashed<T> {
hash: u64,
value: T,
}
impl<T: Hash> Hashed<T> {
#[inline]
fn new(value: T) -> Self {
let mut h = crate::fxhash::FxHasher::default();
value.hash(&mut h);
Hashed {
hash: h.finish(),
value,
}
}
}
impl<T> Hash for Hashed<T> {
#[inline]
fn hash<H: Hasher>(&self, state: &mut H) {
state.write_u64(self.hash);
}
}
impl<T: PartialEq> PartialEq for Hashed<T> {
#[inline]
fn eq(&self, other: &Self) -> bool {
self.hash == other.hash && self.value == other.value
}
}
impl<T: Eq> Eq for Hashed<T> {}
#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
pub(crate) enum Combinator {
Child, NextSibling, FollowingSibling, }
impl Combinator {
pub(crate) fn as_str(self) -> &'static str {
match self {
Combinator::Child => ">",
Combinator::NextSibling => "+",
Combinator::FollowingSibling => "~",
}
}
}
#[derive(Clone, PartialEq, Eq, Hash, Debug)]
pub(crate) enum Simple {
Universal { ns: Option<String> },
Type(String),
Class(String),
Id(String),
Placeholder(String),
Attribute(String),
Pseudo(String),
}
impl Simple {
pub(crate) fn render(&self) -> String {
match self {
Simple::Universal { ns: None } => "*".to_string(),
Simple::Universal { ns: Some(n) } => format!("{n}|*"),
Simple::Type(s) => s.clone(),
Simple::Class(s) => format!(".{s}"),
Simple::Id(s) => format!("#{s}"),
Simple::Placeholder(s) => format!("%{s}"),
Simple::Attribute(s) => s.clone(),
Simple::Pseudo(s) => s.clone(),
}
}
fn is_placeholder(&self) -> bool {
matches!(self, Simple::Placeholder(_))
}
}
pub(crate) fn validate_pseudo_args(sel: &str) -> Result<(), &'static str> {
let chars: Vec<char> = sel.chars().collect();
validate_pseudo_args_inner(&chars)
}
fn validate_pseudo_args_inner(chars: &[char]) -> Result<(), &'static str> {
let mut i = 0usize;
while i < chars.len() {
match chars[i] {
'\\' => {
i += 2;
continue;
}
'"' | '\'' => {
i = skip_quoted(chars, i);
continue;
}
'[' => {
i = skip_attribute(chars, i);
continue;
}
':' => {
let name_start = i + 1 + usize::from(chars.get(i + 1) == Some(&':'));
let mut j = name_start;
while j < chars.len()
&& (chars[j].is_ascii_alphanumeric()
|| chars[j] == '-'
|| chars[j] == '_'
|| (chars[j] as u32) >= 0x80)
{
j += 1;
}
if j < chars.len() && chars[j] == '(' {
let close = matching_paren(chars, j);
let name: String = chars[name_start..j].iter().collect();
let inner = &chars[j + 1..close.min(chars.len())];
validate_one_pseudo_arg(&name, inner)?;
i = if close < chars.len() {
close + 1
} else {
chars.len()
};
continue;
}
i = j;
continue;
}
_ => i += 1,
}
}
Ok(())
}
fn validate_one_pseudo_arg(name: &str, inner: &[char]) -> Result<(), &'static str> {
let unv = unvendor(name);
if unv == "nth-child" || unv == "nth-last-child" {
let arg: String = inner.iter().collect();
validate_nth(&arg)?;
if let Some(of_sel) = nth_of_selector(inner) {
validate_selector_list_arg(&of_sel)?;
}
return Ok(());
}
let is_selector_pseudo = matches!(
unv,
"not" | "is" | "where" | "has" | "matches" | "any" | "host" | "host-context" | "current"
) || unv.ends_with("-any");
if is_selector_pseudo {
let arg: String = inner.iter().collect();
return validate_selector_list_arg(&arg);
}
Ok(())
}
fn validate_selector_list_arg(arg: &str) -> Result<(), &'static str> {
let parts = split_top(arg, ',');
if parts.iter().all(|p| p.trim().is_empty()) {
return Err("expected selector.");
}
if parts.first().is_some_and(|p| p.trim().is_empty()) || parts.last().is_some_and(|p| p.trim().is_empty())
{
return Err("expected selector.");
}
for part in &parts {
if part.trim().is_empty() {
continue;
}
let cs: Vec<char> = part.chars().collect();
validate_pseudo_args_inner(&cs)?;
}
Ok(())
}
fn matching_paren(chars: &[char], open: usize) -> usize {
let mut depth = 0i32;
let mut i = open;
while i < chars.len() {
match chars[i] {
'\\' => i += 2,
'"' | '\'' => i = skip_quoted(chars, i),
'(' => {
depth += 1;
i += 1;
}
')' => {
depth -= 1;
if depth == 0 {
return i;
}
i += 1;
}
_ => i += 1,
}
}
chars.len()
}
fn skip_quoted(chars: &[char], start: usize) -> usize {
let q = chars[start];
let mut i = start + 1;
while i < chars.len() {
match chars[i] {
'\\' => i += 2,
c if c == q => return i + 1,
_ => i += 1,
}
}
chars.len()
}
fn skip_attribute(chars: &[char], start: usize) -> usize {
let mut i = start + 1;
while i < chars.len() {
match chars[i] {
'\\' => i += 2,
'"' | '\'' => i = skip_quoted(chars, i),
']' => return i + 1,
_ => i += 1,
}
}
chars.len()
}
pub(crate) fn normalize_nth(text: &str) -> Option<String> {
let open = text.find('(')?;
if !text.ends_with(')') {
return None;
}
let name = &text[..open];
if name != ":nth-child" && name != ":nth-last-child" {
return None;
}
let arg = &text[open + 1..text.len() - 1];
let lower = arg.to_ascii_lowercase();
let (anb, of_sel) = match find_of_keyword(&lower) {
Some(pos) => (&arg[..pos], Some(arg[pos + 2..].trim())),
None => (arg, None),
};
let anb_norm: String = anb.chars().filter(|c| !c.is_whitespace()).collect::<String>();
if anb_norm.is_empty() {
return None;
}
let anb_norm = anb_norm.to_ascii_lowercase();
Some(match of_sel {
Some(sel) => format!("{name}({anb_norm} of {sel})"),
None => format!("{name}({anb_norm})"),
})
}
pub(crate) fn validate_nth(arg: &str) -> Result<(), &'static str> {
let chars: Vec<char> = arg.chars().collect();
let mut i = 0usize;
let skip_ws = |i: &mut usize| {
while *i < chars.len() && chars[*i].is_whitespace() {
*i += 1;
}
};
skip_ws(&mut i);
match chars.get(i).map(|c| c.to_ascii_lowercase()) {
Some('e') => return finish_nth(&chars, scan_keyword(&chars, &mut i, "even")?),
Some('o') => return finish_nth(&chars, scan_keyword(&chars, &mut i, "odd")?),
_ => {}
}
if matches!(chars.get(i), Some('+' | '-')) {
i += 1;
}
let digits_start = i;
while matches!(chars.get(i), Some(c) if c.is_ascii_digit()) {
i += 1;
}
let saw_digit = i > digits_start;
let mut body_end = i;
if saw_digit {
skip_ws(&mut i);
}
if matches!(chars.get(i), Some('n' | 'N')) {
i += 1;
body_end = i;
skip_ws(&mut i);
if matches!(chars.get(i), Some('+' | '-')) {
i += 1;
skip_ws(&mut i);
if !matches!(chars.get(i), Some(c) if c.is_ascii_digit()) {
return Err("Expected a number.");
}
while matches!(chars.get(i), Some(c) if c.is_ascii_digit()) {
i += 1;
}
body_end = i;
}
return finish_nth(&chars, body_end);
}
if !saw_digit {
return Err("Expected \"n\".");
}
finish_nth(&chars, body_end)
}
fn finish_nth(chars: &[char], mut i: usize) -> Result<(), &'static str> {
let had_ws = i < chars.len() && chars[i].is_whitespace();
while i < chars.len() && chars[i].is_whitespace() {
i += 1;
}
if i >= chars.len() {
return Ok(());
}
if !had_ws {
return Err("expected \")\".");
}
if !(matches!(chars.get(i), Some('o' | 'O')) && matches!(chars.get(i + 1), Some('f' | 'F'))) {
return Err("Expected \"of\".");
}
let of_complete = match chars.get(i + 2) {
None => true,
Some(c) => !(c.is_ascii_alphanumeric() || *c == '-' || *c == '_' || (*c as u32) >= 0x80),
};
if !of_complete {
return Err("Expected \"of\"");
}
i += 2;
while i < chars.len() && chars[i].is_whitespace() {
i += 1;
}
let rest: String = chars[i..].iter().collect();
if rest.trim().is_empty() {
return Err("expected selector.");
}
Ok(())
}
fn nth_of_selector(inner: &[char]) -> Option<String> {
let mut i = 0usize;
while i + 1 < inner.len() {
let before_ws = i > 0 && inner[i - 1].is_whitespace();
let of_complete = match inner.get(i + 2) {
None => true,
Some(c) => !(c.is_ascii_alphanumeric() || *c == '-' || *c == '_' || (*c as u32) >= 0x80),
};
if before_ws && matches!(inner[i], 'o' | 'O') && matches!(inner[i + 1], 'f' | 'F') && of_complete {
let mut j = i + 2;
while j < inner.len() && inner[j].is_whitespace() {
j += 1;
}
return Some(inner[j..].iter().collect());
}
i += 1;
}
None
}
fn scan_keyword(chars: &[char], i: &mut usize, kw: &str) -> Result<usize, &'static str> {
let (mismatch, trailing): (&'static str, &'static str) = match kw {
"even" => ("Expected \"even\".", "Expected \"even\""),
_ => ("Expected \"odd\".", "Expected \"odd\""),
};
for k in kw.chars() {
match chars.get(*i) {
Some(c) if c.to_ascii_lowercase() == k => *i += 1,
_ => return Err(mismatch),
}
}
if matches!(chars.get(*i), Some(c) if c.is_ascii_alphanumeric() || *c == '-' || *c == '_') {
return Err(trailing);
}
Ok(*i)
}
fn nth_of_parts(text: &str) -> Option<(&str, &str, &str)> {
let open = text.find('(')?;
if !text.ends_with(')') {
return None;
}
let name = &text[..open];
if name != ":nth-child" && name != ":nth-last-child" {
return None;
}
let arg = &text[open + 1..text.len() - 1];
let pos = find_of_keyword(&arg.to_ascii_lowercase())?;
Some((name, arg[..pos].trim(), arg[pos + 2..].trim()))
}
fn find_of_keyword(lower: &str) -> Option<usize> {
let bytes = lower.as_bytes();
let mut i = 0;
while let Some(rel) = lower[i..].find("of") {
let pos = i + rel;
let before_ws = pos == 0 || bytes[pos - 1].is_ascii_whitespace();
let after = pos + 2;
let after_ws = after < bytes.len() && bytes[after].is_ascii_whitespace();
if before_ws && after_ws {
return Some(pos);
}
i = pos + 2;
}
None
}
#[derive(Clone, PartialEq, Eq, Hash, Debug)]
pub(crate) struct Compound {
pub simples: Vec<Simple>,
}
impl Compound {
pub(crate) fn render(&self) -> String {
self.simples.iter().map(Simple::render).collect()
}
fn has_placeholder(&self) -> bool {
self.simples.iter().any(Simple::is_placeholder)
}
}
#[derive(Clone, PartialEq, Eq, Hash, Debug)]
pub(crate) struct ComplexComponent {
pub combinators: Vec<Combinator>,
pub compound: Compound,
}
impl ComplexComponent {
pub(crate) fn combinator(&self) -> Option<Combinator> {
match self.combinators.as_slice() {
[c] => Some(*c),
_ => None,
}
}
}
#[derive(Clone, PartialEq, Eq, Hash, Debug, Default)]
pub(crate) struct Complex {
pub components: Vec<ComplexComponent>,
pub trailing: Vec<Combinator>,
}
impl Complex {
pub(crate) fn render(&self) -> String {
let mut out = String::new();
for (i, comp) in self.components.iter().enumerate() {
if i > 0 {
out.push(' ');
}
for c in &comp.combinators {
out.push_str(c.as_str());
out.push(' ');
}
out.push_str(&comp.compound.render());
}
for (j, c) in self.trailing.iter().enumerate() {
if j > 0 || !self.components.is_empty() {
out.push(' ');
}
out.push_str(c.as_str());
}
out
}
fn has_placeholder(&self) -> bool {
self.components.iter().any(|c| c.compound.has_placeholder())
}
}
pub(crate) fn complex_has_placeholder(c: &Complex) -> bool {
c.has_placeholder()
}
#[cfg(debug_assertions)]
pub(crate) fn assert_render_injective(c: &Complex) {
thread_local! {
static SEEN: std::cell::RefCell<FxHashMap<String, Complex>> =
std::cell::RefCell::new(FxHashMap::default());
}
SEEN.with(|seen| {
let key = c.render();
let mut seen = seen.borrow_mut();
match seen.get(&key) {
Some(prev) if prev != c => panic!(
"Phase-1a parity violation (Complex): two structurally distinct \
selectors share render {key:?}\n a = {prev:?}\n b = {c:?}"
),
Some(_) => {}
None => {
seen.insert(key, c.clone());
}
}
});
}
#[cfg(debug_assertions)]
pub(crate) fn assert_simple_render_injective(s: &Simple) {
thread_local! {
static SEEN: std::cell::RefCell<FxHashMap<String, Simple>> =
std::cell::RefCell::new(FxHashMap::default());
}
SEEN.with(|seen| {
let key = s.render();
let mut seen = seen.borrow_mut();
match seen.get(&key) {
Some(prev) if prev != s => panic!(
"Phase-1a parity violation (Simple): two structurally distinct \
simples share render {key:?}\n a = {prev:?}\n b = {s:?}"
),
Some(_) => {}
None => {
seen.insert(key, s.clone());
}
}
});
}
#[cfg(not(debug_assertions))]
#[inline(always)]
pub(crate) fn assert_render_injective(_c: &Complex) {}
#[cfg(not(debug_assertions))]
#[inline(always)]
pub(crate) fn assert_simple_render_injective(_s: &Simple) {}
mod parse;
pub(crate) use parse::{canonicalize_ident, normalize_attribute, parse_complex_one, parse_list};
use parse::{parse_complex, parse_compound, skip_ws, split_top};
#[derive(Clone)]
pub(crate) struct Extension {
pub target: Option<Simple>,
pub extenders: Vec<Complex>,
pub extender_breaks: Vec<bool>,
pub optional: bool,
pub matched: std::rc::Rc<std::cell::Cell<bool>>,
pub origin: String,
pub reg_idx: usize,
pub derived: bool,
pub via_origin: Option<String>,
pub origin_closure: std::rc::Rc<std::collections::HashSet<String>>,
}
pub(crate) fn list_contains_simple(list: &[Complex], target: &Simple) -> bool {
list.iter().any(|c| {
c.components
.iter()
.any(|comp| comp.compound.simples.contains(target))
})
}
pub(crate) enum TargetClass {
Simple(Simple),
Complex,
Compound,
Invalid,
}
pub(crate) fn classify_target(s: &str) -> TargetClass {
let s = s.trim();
if s.is_empty() {
return TargetClass::Invalid;
}
let Some(complex) = parse_complex(s) else {
return TargetClass::Invalid;
};
if complex.components.len() != 1 || complex.components[0].combinator().is_some() {
return TargetClass::Complex;
}
let simples = &complex.components[0].compound.simples;
if simples.len() != 1 {
return TargetClass::Compound;
}
TargetClass::Simple(simples[0].clone())
}
pub(crate) struct ExtendResult {
pub selectors: Vec<Complex>,
pub breaks: Vec<bool>,
pub all_placeholders: bool,
}
pub(crate) struct ExtendPlan {
batches: Vec<Vec<Extension>>,
registry: Vec<Extension>,
batch_registry_marks: Vec<usize>,
batch_reg_idx: Vec<usize>,
batch_origin: Vec<String>,
origin_rank: std::collections::HashMap<String, usize>,
legacy_order: bool,
source_spec: FxHashMap<Simple, u64>,
n_extensions: usize,
single_module: bool,
pseudo_self_ref: bool,
expand_budget_cost: usize,
}
impl ExtendPlan {
pub(crate) fn is_empty(&self) -> bool {
self.n_extensions == 0
}
}
pub(crate) fn build_extend_plan(
extensions: &[Extension],
scope: &str,
origin_rank: std::collections::HashMap<String, usize>,
legacy_order: bool,
) -> ExtendPlan {
let source_spec = source_specificity_map(extensions);
reset_extend_budget();
let budget_before = EXTEND_WORK.with(|w| w.get());
let (raw_batches, registry, raw_marks) = expand_extensions(extensions);
let mut batches: Vec<Vec<Extension>> = Vec::new();
let mut batch_registry_marks: Vec<usize> = Vec::new();
let mut batch_reg_idx: Vec<usize> = Vec::new();
let mut batch_origin: Vec<String> = Vec::new();
let mut last_origin: Option<&str> = None;
for (i, batch) in raw_batches.into_iter().enumerate() {
let origin = extensions[i].origin.as_str();
if origin != scope && last_origin == Some(origin) {
let last = batches.last_mut().expect("non-empty on merge");
last.extend(batch);
*batch_registry_marks.last_mut().expect("mark") = raw_marks[i];
} else {
batches.push(batch);
batch_registry_marks.push(raw_marks[i]);
batch_reg_idx.push(extensions[i].reg_idx);
batch_origin.push(extensions[i].origin.clone());
last_origin = Some(origin);
}
}
let budget_after = EXTEND_WORK.with(|w| w.get());
let expand_budget_cost = budget_before.saturating_sub(budget_after);
let single_module = extensions.iter().all(|e| e.origin == scope);
let targets: FxHashSet<Simple> = extensions.iter().filter_map(|e| e.target.clone()).collect();
let pseudo_self_ref = single_module
&& registry.iter().any(|e| {
e.extenders
.iter()
.any(|c| pseudo_arg_has_target(c, &targets, false))
});
ExtendPlan {
batches,
registry,
batch_registry_marks,
batch_reg_idx,
batch_origin,
origin_rank,
legacy_order,
source_spec,
n_extensions: extensions.len(),
single_module,
pseudo_self_ref,
expand_budget_cost,
}
}
pub(crate) fn extend_selectors(
original: &[Complex],
original_breaks: &[bool],
plan: &ExtendPlan,
scope: &str,
extend_base: usize,
) -> ExtendResult {
reset_extend_budget();
EXTEND_WORK.with(|w| w.set(w.get().saturating_sub(plan.expand_budget_cost)));
let batches = &plan.batches;
let registry = &plan.registry;
let source_spec = &plan.source_spec;
for complex in original {
assert_render_injective(complex);
}
let single_module = plan.single_module;
let order = if single_module
&& extend_base != usize::MAX
&& plan.batch_reg_idx.iter().all(|&r| r < extend_base)
{
CartesianOrder::OneShot
} else {
CartesianOrder::Fold
};
let pseudo_self_ref = plan.pseudo_self_ref;
let result: Vec<(Complex, bool)> = if pseudo_self_ref && order == CartesianOrder::Fold {
let mut current: Vec<(Complex, bool, bool, String)> = original
.iter()
.enumerate()
.map(|(i, c)| {
(
c.clone(),
original_breaks.get(i).copied().unwrap_or(false),
true,
scope.to_string(),
)
})
.collect();
let mut current_simples: FxHashSet<Simple> = FxHashSet::default();
for (c, _, _, _) in ¤t {
collect_match_simples(c, &mut current_simples);
}
for batch in batches.iter() {
let mut any = false;
for e in batch.iter() {
if let Some(t) = &e.target {
if current_simples.contains(t) {
any = true;
break;
}
}
}
if !any {
continue;
}
current = extend_list_batch(¤t, batch, Some(scope), source_spec);
for (c, _, _, _) in ¤t {
collect_match_simples(c, &mut current_simples);
}
}
current.into_iter().map(|(c, f, _, _)| (c, f)).collect()
} else if order == CartesianOrder::OneShot {
let all_orig: Vec<bool> = vec![true; original.len()];
let (result, changed) =
extend_to_fixpoint_breaks(original, original_breaks, &all_orig, Some(scope), registry, order);
if changed {
trim_breaks(result, source_spec)
.into_iter()
.map(|(c, f, _)| (c, f))
.collect()
} else {
original
.iter()
.enumerate()
.map(|(i, c)| (c.clone(), original_breaks.get(i).copied().unwrap_or(false)))
.collect()
}
} else {
let foreign: Vec<usize> = if plan.legacy_order {
Vec::new()
} else {
(0..batches.len())
.filter(|&i| plan.batch_origin.get(i).is_some_and(|o| o != scope))
.collect()
};
let pre_batches: Vec<usize> = if extend_base != usize::MAX && extend_base > 0 {
let mut v: Vec<usize> = (0..batches.len())
.filter(|&i| {
(plan.legacy_order || plan.batch_origin.get(i).is_some_and(|o| o == scope))
&& plan.batch_reg_idx.get(i).copied().unwrap_or(usize::MAX) < extend_base
})
.collect();
v.sort_by_key(|&i| plan.batch_reg_idx[i]);
v
} else {
Vec::new()
};
let mut pre_set: FxHashSet<usize> = pre_batches.iter().copied().collect();
pre_set.extend(foreign.iter().copied());
let seed: Vec<(Complex, bool, bool)> = if !pre_batches.is_empty() {
let one_shot_store: Vec<Extension> = pre_batches
.iter()
.flat_map(|&i| {
let start = if i == 0 {
0
} else {
plan.batch_registry_marks[i - 1]
};
registry[start..plan.batch_registry_marks[i]].iter().cloned()
})
.collect();
let all_orig: Vec<bool> = vec![true; original.len()];
let (res, changed) = extend_to_fixpoint_breaks(
original,
original_breaks,
&all_orig,
Some(scope),
&one_shot_store,
CartesianOrder::OneShot,
);
if changed {
trim_breaks(res, source_spec)
} else {
original
.iter()
.enumerate()
.map(|(i, c)| (c.clone(), original_breaks.get(i).copied().unwrap_or(false), true))
.collect()
}
} else {
original
.iter()
.enumerate()
.map(|(i, c)| (c.clone(), original_breaks.get(i).copied().unwrap_or(false), true))
.collect()
};
let mut current: Vec<(Complex, bool, bool, String)> =
seed.into_iter().map(|(c, f, o)| (c, f, o, scope.to_string())).collect();
let mut current_simples: FxHashSet<Simple> = FxHashSet::default();
for (c, _, _, _) in ¤t {
collect_match_simples(c, &mut current_simples);
}
{
for (bi, batch) in batches.iter().enumerate() {
if pre_set.contains(&bi) {
continue;
}
let mut any = false;
for e in batch.iter() {
if let Some(t) = &e.target {
if current_simples.contains(t) {
any = true;
break;
}
}
}
if !any {
continue;
}
let next = extend_list_batch(¤t, batch, Some(scope), source_spec);
for (c, _, _, _) in &next {
collect_match_simples(c, &mut current_simples);
}
current = next;
}
}
let pre_foreign_snapshot: Vec<Complex> = if foreign.is_empty() {
Vec::new()
} else {
current.iter().map(|(c, _, _, _)| c.clone()).collect()
};
if !foreign.is_empty() {
let mut foreign_entries: Vec<&Extension> =
registry.iter().filter(|e| e.origin != scope).collect();
foreign_entries.sort_by(|a, b| {
let rank = |e: &Extension| plan.origin_rank.get(&e.origin).copied().unwrap_or(usize::MAX);
let via_rank = |e: &Extension| {
e.via_origin
.as_ref()
.and_then(|o| plan.origin_rank.get(o).copied())
.unwrap_or(usize::MAX)
};
rank(a)
.cmp(&rank(b))
.then(a.derived.cmp(&b.derived))
.then(via_rank(a).cmp(&via_rank(b)))
.then(a.reg_idx.cmp(&b.reg_idx))
});
let foreign_store: Vec<Extension> = foreign_entries.into_iter().cloned().collect();
let complexes: Vec<Complex> = current.iter().map(|(c, _, _, _)| c.clone()).collect();
let breaks: Vec<bool> = current.iter().map(|(_, f, _, _)| *f).collect();
let origs: Vec<bool> = current.iter().map(|(_, _, o, _)| *o).collect();
let (res, changed) = extend_to_fixpoint_breaks(
&complexes,
&breaks,
&origs,
Some(scope),
&foreign_store,
CartesianOrder::OneShot,
);
if changed {
current = trim_breaks(res, source_spec)
.into_iter()
.map(|(c, f, o)| (c, f, o, scope.to_string()))
.collect();
}
}
for (&i, snapshot) in pre_batches
.iter()
.map(|i| (i, original))
.chain(foreign.iter().map(|i| (i, pre_foreign_snapshot.as_slice())))
{
for e in &batches[i] {
if e.matched.get() {
continue;
}
if let Some(t) = &e.target {
if list_contains_simple(snapshot, t) {
e.matched.set(true);
}
}
}
}
current.into_iter().map(|(c, f, _, _)| (c, f)).collect()
};
let mut simplified: Vec<(Complex, bool)> = Vec::new();
for (c, f) in result {
if let Some(c) = simplify_pseudo_placeholders(&c) {
simplified.push((c, f));
}
}
let all_placeholders = simplified.iter().all(|(c, _)| c.has_placeholder());
let mut selectors: Vec<Complex> = Vec::new();
let mut breaks: Vec<bool> = Vec::new();
for (c, f) in simplified {
if !c.has_placeholder() {
selectors.push(c);
breaks.push(f);
}
}
ExtendResult {
selectors,
breaks,
all_placeholders,
}
}
fn simplify_pseudo_placeholders(complex: &Complex) -> Option<Complex> {
let mut components = Vec::new();
for comp in &complex.components {
let mut simples: Vec<Simple> = Vec::new();
for s in &comp.compound.simples {
match s {
Simple::Pseudo(text) if text.contains('%') => {
match simplify_one_pseudo(text) {
PseudoResult::Keep(new) => simples.push(Simple::Pseudo(new)),
PseudoResult::Remove => { }
PseudoResult::NeverMatches => return None,
}
}
other => simples.push(other.clone()),
}
}
if simples.is_empty() {
simples.push(Simple::Universal { ns: None });
}
components.push(ComplexComponent {
combinators: comp.combinators.clone(),
compound: Compound { simples },
});
}
Some(Complex {
components,
trailing: Vec::new(),
})
}
enum PseudoResult {
Keep(String),
Remove,
NeverMatches,
}
fn simplify_one_pseudo(text: &str) -> PseudoResult {
let Some(open) = text.find('(') else {
return PseudoResult::Keep(text.to_string());
};
if !text.ends_with(')') {
return PseudoResult::Keep(text.to_string());
}
let head = &text[..open]; let arg = &text[open + 1..text.len() - 1];
let name = head.trim_start_matches(':').to_ascii_lowercase();
let is_matchish =
matches!(unvendor(&name), "is" | "where" | "matches" | "any" | "has") || name.ends_with("-any");
let is_not = unvendor(&name) == "not";
if !is_matchish && !is_not {
return PseudoResult::Keep(text.to_string());
}
let Some(list) = parse_list(arg) else {
return PseudoResult::Keep(text.to_string());
};
let kept: Vec<&Complex> = list.iter().filter(|c| !c.has_placeholder()).collect();
if kept.is_empty() {
return if is_not {
PseudoResult::Remove
} else {
PseudoResult::NeverMatches
};
}
let inner = kept.iter().map(|c| c.render()).collect::<Vec<_>>().join(", ");
PseudoResult::Keep(format!("{head}({inner})"))
}
fn trim(
selectors: Vec<(Complex, bool)>,
source_spec: &FxHashMap<Simple, u64>,
) -> Vec<Complex> {
trim_breaks(
selectors.into_iter().map(|(c, o)| (c, false, o)).collect(),
source_spec,
)
.into_iter()
.map(|(c, _, _)| c)
.collect()
}
fn trim_breaks(
selectors: Vec<(Complex, bool, bool)>,
source_spec: &FxHashMap<Simple, u64>,
) -> Vec<(Complex, bool, bool)> {
if selectors.len() > 100 {
return selectors;
}
let source_spec_for = |c: &Complex| -> u64 {
c.components
.iter()
.map(|comp| {
comp.compound
.simples
.iter()
.map(|s| source_spec.get(s).copied().unwrap_or(0))
.max()
.unwrap_or(0)
})
.max()
.unwrap_or(0)
};
let mut result: Vec<(Complex, bool, bool)> = Vec::new();
let mut num_originals = 0usize;
let n = selectors.len();
'outer: for i in (0..n).rev() {
let (c1, f1, o1) = &selectors[i];
if *o1 {
for j in 0..num_originals {
if result[j].0 == *c1 {
let c = result.remove(j);
result.insert(0, c);
continue 'outer;
}
}
num_originals += 1;
result.insert(0, (c1.clone(), *f1, true));
continue;
}
let max_spec = source_spec_for(c1);
let covers = |c2: &Complex| complex_specificity(c2) >= max_spec && complex_is_superselector(c2, c1);
if result.iter().any(|(c2, _, _)| covers(c2)) || selectors[..i].iter().any(|(c2, _, _)| covers(c2)) {
continue;
}
result.insert(0, (c1.clone(), *f1, false));
}
result
}
fn complex_is_superselector(c1: &Complex, c2: &Complex) -> bool {
let d1 = to_dart(c1);
let d2 = to_dart(c2);
d1.leading.is_empty() && d2.leading.is_empty() && complex_is_superselector_trailing(&d1.comps, &d2.comps)
}
fn complex_is_superselector_trailing(complex1: &[TComp], complex2: &[TComp]) -> bool {
if complex1.last().map(|c| !c.combinators.is_empty()).unwrap_or(true) {
return false;
}
if complex2.last().map(|c| !c.combinators.is_empty()).unwrap_or(true) {
return false;
}
let mut i1 = 0usize;
let mut i2 = 0usize;
let mut previous_combinator: Option<Combinator> = None;
loop {
let remaining1 = complex1.len() - i1;
let remaining2 = complex2.len() - i2;
if remaining1 == 0 || remaining2 == 0 {
return false;
}
if remaining1 > remaining2 {
return false;
}
let component1 = &complex1[i1];
if component1.combinators.len() > 1 {
return false;
}
if remaining1 == 1 {
let parents = &complex2[i2..complex2.len() - 1];
if parents.iter().any(|p| p.combinators.len() > 1) {
return false;
}
let Some(last2) = complex2.last() else {
return false;
};
return compound_is_superselector(&component1.compound, &last2.compound, parents);
}
let mut end = i2;
loop {
let component2 = &complex2[end];
if component2.combinators.len() > 1 {
return false;
}
if compound_is_superselector(&component1.compound, &component2.compound, &[]) {
break;
}
end += 1;
if end == complex2.len() - 1 {
return false;
}
}
if !compatible_with_previous_combinator(previous_combinator, &complex2[i2..end]) {
return false;
}
let component2 = &complex2[end];
let combinator1 = component1.combinators.first().copied();
let combinator2 = component2.combinators.first().copied();
if !is_supercombinator(combinator1, combinator2) {
return false;
}
i1 += 1;
i2 = end + 1;
previous_combinator = combinator1;
if complex1.len() - i1 == 1 {
match combinator1 {
Some(Combinator::FollowingSibling) => {
let upto = complex2.len() - 1;
if !complex2[i2..upto]
.iter()
.all(|c| is_supercombinator(combinator1, c.combinators.first().copied()))
{
return false;
}
}
Some(_) if complex2.len() - i2 > 1 => return false,
_ => {}
}
}
}
}
fn compatible_with_previous_combinator(previous: Option<Combinator>, parents: &[TComp]) -> bool {
if parents.is_empty() {
return true;
}
let Some(prev) = previous else {
return true;
};
if prev != Combinator::FollowingSibling {
return false;
}
parents.iter().all(|c| {
matches!(
c.combinators.first().copied(),
Some(Combinator::FollowingSibling) | Some(Combinator::NextSibling)
)
})
}
fn is_supercombinator(c1: Option<Combinator>, c2: Option<Combinator>) -> bool {
c1 == c2
|| (c1.is_none() && c2 == Some(Combinator::Child))
|| (c1 == Some(Combinator::FollowingSibling) && c2 == Some(Combinator::NextSibling))
}
pub(crate) fn normalize_pseudo_arg(text: &str) -> Option<String> {
let open = text.find('(')?;
if !text.ends_with(')') {
return None;
}
let head = &text[..open];
let name_l = head.trim_start_matches(':').to_ascii_lowercase();
let known = matches!(
unvendor(&name_l),
"not" | "is" | "where" | "matches" | "any" | "has"
) || name_l.ends_with("-any");
if !known {
return None;
}
let raw = &text[open + 1..text.len() - 1];
let list = parse_list(raw)?;
let mut part_breaks: Vec<bool> = Vec::new();
{
let mut paren = 0i32;
let mut bracket = 0i32;
let mut leading = true;
let mut brk = false;
for ch in raw.chars() {
match ch {
'(' => paren += 1,
')' => paren -= 1,
'[' => bracket += 1,
']' => bracket -= 1,
',' if paren == 0 && bracket == 0 => {
part_breaks.push(brk);
leading = true;
brk = false;
continue;
}
_ => {}
}
if leading {
if ch == '\n' {
brk = true;
} else if !ch.is_whitespace() {
leading = false;
}
}
}
part_breaks.push(brk);
}
let mut inner = String::new();
for (i, c) in list.iter().enumerate() {
if i > 0 {
inner.push(',');
inner.push(if part_breaks.get(i).copied().unwrap_or(false) {
'\n'
} else {
' '
});
}
inner.push_str(&c.render());
}
Some(format!("{head}({inner})"))
}
fn parse_selector_pseudo(text: &str) -> Option<(String, Vec<Complex>)> {
let open = text.find('(')?;
if !text.ends_with(')') {
return None;
}
let name = text[..open].trim_start_matches(':').to_ascii_lowercase();
let known = matches!(
unvendor(&name),
"is" | "where" | "matches" | "any" | "has" | "host" | "host-context"
) || name.ends_with("-any");
if !known {
return None;
}
let list = parse_list(&text[open + 1..text.len() - 1])?;
Some((name, list))
}
fn selector_pseudo_is_super(name: &str, branches: &[Complex], b: &Compound, parents: &[TComp]) -> bool {
for s in &b.simples {
if let Simple::Pseudo(t) = s {
if let Some((n2, b_branches)) = parse_selector_pseudo(t) {
if n2 == name
&& !b_branches.is_empty()
&& b_branches
.iter()
.all(|s2| list_is_superselector(branches, std::slice::from_ref(s2)))
{
return true;
}
}
}
}
let matchish = matches!(unvendor(name), "is" | "where" | "matches" | "any") || name.ends_with("-any");
if !matchish {
return false;
}
branches.iter().any(|branch| {
let bd = to_dart(branch);
if !bd.leading.is_empty() {
return false;
}
let mut target: Vec<TComp> = parents.to_vec();
target.push(TComp {
compound: b.clone(),
combinators: Vec::new(),
});
complex_is_superselector_trailing(&bd.comps, &target)
})
}
fn parse_not_pseudo(text: &str) -> Option<(String, Vec<Complex>)> {
let open = text.find('(')?;
if !text.ends_with(')') {
return None;
}
let name = text[..open].trim_start_matches(':').to_ascii_lowercase();
if unvendor(&name) != "not" {
return None;
}
let list = parse_list(&text[open + 1..text.len() - 1])?;
Some((name, list))
}
fn not_pseudo_is_super(name: &str, branches: &[Complex], b: &Compound) -> bool {
branches.iter().all(|complex1| {
b.simples
.iter()
.any(|simple2| not_excludes(complex1, simple2, name))
})
}
fn not_excludes(complex1: &Complex, simple2: &Simple, not_name: &str) -> bool {
let last = complex1.components.last();
let last_simples = || last.map(|c| c.compound.simples.as_slice()).unwrap_or(&[]);
match simple2 {
Simple::Type(t2) => {
let n2 = type_local_name(t2);
last_simples()
.iter()
.any(|s| matches!(s, Simple::Type(t1) if type_local_name(t1) != n2))
}
Simple::Id(id2) => last_simples()
.iter()
.any(|s| matches!(s, Simple::Id(id1) if id1 != id2)),
Simple::Pseudo(t2) => match parse_not_pseudo(t2) {
Some((n2, s2_branches)) => {
n2 == not_name && list_is_superselector(&s2_branches, std::slice::from_ref(complex1))
}
None => false,
},
_ => false,
}
}
fn type_local_name(t: &str) -> &str {
t.rsplit('|').next().unwrap_or(t)
}
fn compound_is_superselector(a: &Compound, b: &Compound, parents: &[TComp]) -> bool {
match (find_pseudo_element(a), find_pseudo_element(b)) {
(Some((pe1, i1)), Some((pe2, i2))) => {
pseudo_element_is_superselector(pe1, pe2)
&& compound_components_is_superselector(&a.simples[..i1], &b.simples[..i2])
&& compound_components_is_superselector(&a.simples[i1 + 1..], &b.simples[i2 + 1..])
}
(Some(_), None) | (None, Some(_)) => false,
(None, None) => a.simples.iter().all(|s1| {
if let Simple::Pseudo(text) = s1 {
if let Some((name, branches)) = parse_selector_pseudo(text) {
return selector_pseudo_is_super(&name, &branches, b, parents);
}
if let Some((name, branches)) = parse_not_pseudo(text) {
return not_pseudo_is_super(&name, &branches, b);
}
if let Some((head, anb, of_sel)) = nth_selector_parts(text) {
return nth_pseudo_is_super(head, anb, of_sel, b);
}
}
b.simples.iter().any(|s2| simple_is_superselector(s1, s2))
}),
}
}
fn pseudo_element_is_superselector(pe1: &Simple, pe2: &Simple) -> bool {
if pe1 == pe2 {
return true;
}
let (Simple::Pseudo(t1), Simple::Pseudo(t2)) = (pe1, pe2) else {
return false;
};
let (Some(p1), Some(p2)) = (parse_pseudo_parts(t1), parse_pseudo_parts(t2)) else {
return false;
};
if unvendor(&p1.name) != "slotted" || p1.head != p2.head {
return false;
}
match (parse_list(&p1.arg), parse_list(&p2.arg)) {
(Some(l1), Some(l2)) => list_is_superselector(&l1, &l2),
_ => false,
}
}
fn nth_selector_parts(text: &str) -> Option<(&str, &str, &str)> {
let open = text.find('(')?;
if !text.ends_with(')') || text.starts_with("::") {
return None;
}
let head = &text[..open];
let name = head.trim_start_matches(':').to_ascii_lowercase();
if !matches!(unvendor(&name), "nth-child" | "nth-last-child") {
return None;
}
let arg = &text[open + 1..text.len() - 1];
let pos = find_of_keyword(&arg.to_ascii_lowercase())?;
Some((head, arg[..pos].trim(), arg[pos + 2..].trim()))
}
fn subselector_pseudo_branches(text: &str) -> Option<Vec<Complex>> {
if let Some((_, _, of_sel)) = nth_selector_parts(text) {
return parse_list(of_sel);
}
let parts = parse_pseudo_parts(text)?;
if parts.head.starts_with("::") {
return None;
}
if !matches!(unvendor(&parts.name), "is" | "matches" | "any" | "where") {
return None;
}
parse_list(&parts.arg)
}
fn nth_pseudo_is_super(head1: &str, anb1: &str, of1: &str, b: &Compound) -> bool {
let Some(list1) = parse_list(of1) else {
return false;
};
b.simples.iter().any(|s2| {
let Simple::Pseudo(t2) = s2 else {
return false;
};
let Some((head2, anb2, of2)) = nth_selector_parts(t2) else {
return false;
};
head2 == head1
&& anb2 == anb1
&& parse_list(of2).is_some_and(|list2| list_is_superselector(&list1, &list2))
})
}
fn compound_components_is_superselector(a: &[Simple], b: &[Simple]) -> bool {
if a.is_empty() {
return true;
}
let universal = [Simple::Universal { ns: None }];
let b = if b.is_empty() { &universal[..] } else { b };
compound_is_superselector(
&Compound { simples: a.to_vec() },
&Compound { simples: b.to_vec() },
&[],
)
}
fn find_pseudo_element(compound: &Compound) -> Option<(&Simple, usize)> {
compound
.simples
.iter()
.enumerate()
.find(|(_, s)| is_pseudo_element(s))
.map(|(i, s)| (s, i))
}
fn simple_is_superselector(a: &Simple, b: &Simple) -> bool {
if a == b {
return true;
}
if let Simple::Pseudo(text) = b {
if let Some(branches) = subselector_pseudo_branches(text) {
return branches.iter().all(|complex| {
to_dart(complex).comps.last().is_some_and(|last| {
last.compound
.simples
.iter()
.any(|s| simple_is_superselector(a, s))
})
});
}
}
match a {
Simple::Universal { ns: None } => true,
Simple::Universal { ns: Some(n) } if n == "*" => true,
Simple::Universal { ns: Some(n) } => match b {
Simple::Type(t) => type_namespace(t).as_deref() == Some(n.as_str()),
Simple::Universal { ns: Some(m) } => n == m,
_ => false,
},
Simple::Type(t) => match b {
Simple::Type(u) => {
let (n1, name1) = split_type(t);
let (n2, name2) = split_type(u);
name1 == name2 && (n1.as_deref() == Some("*") || n1 == n2)
}
_ => false,
},
_ => false,
}
}
fn split_type(t: &str) -> (Option<String>, String) {
match t.split_once('|') {
Some((ns, name)) => (Some(ns.to_string()), name.to_string()),
None => (None, t.to_string()),
}
}
fn type_namespace(t: &str) -> Option<String> {
t.split_once('|').map(|(ns, _)| ns.to_string())
}
fn extend_complex(complex: &Complex, extensions: &[Extension]) -> Vec<Complex> {
let empty: FxHashMap<Complex, bool> = FxHashMap::default();
extend_complex_breaks(complex, false, true, None, extensions, &empty, CartesianOrder::Fold)
.into_iter()
.map(|(c, _, _)| c)
.collect()
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum CartesianOrder {
OneShot,
Fold,
}
fn extend_complex_breaks(
complex: &Complex,
in_break: bool,
in_orig: bool,
orig_scope: Option<&str>,
extensions: &[Extension],
ext_breaks: &FxHashMap<Complex, bool>,
order: CartesianOrder,
) -> Vec<(Complex, bool, bool)> {
let d = to_dart(complex);
if d.leading.len() > 1 {
return vec![(complex.clone(), in_break, in_orig)];
}
let mut per_component: Vec<Vec<(DComplex, bool)>> = Vec::new();
let mut any_extended = false;
for (i, comp) in d.comps.iter().enumerate() {
match extend_component(comp, extensions, ext_breaks, order) {
None => per_component.push(vec![(
DComplex {
leading: if i == 0 { d.leading.clone() } else { Vec::new() },
comps: vec![comp.clone()],
},
false,
)]),
Some(extended) => {
any_extended = true;
if i == 0 && !d.leading.is_empty() {
per_component.push(
extended
.into_iter()
.filter(|(n, _)| n.leading.is_empty() || n.leading == d.leading)
.map(|(n, f)| {
(
DComplex {
leading: d.leading.clone(),
comps: n.comps,
},
f,
)
})
.collect(),
);
} else {
per_component.push(extended);
}
}
}
}
if !any_extended {
return vec![(complex.clone(), in_break, in_orig)];
}
let mut combos: Vec<(Vec<DComplex>, bool)> = vec![(Vec::new(), false)];
for opts in &per_component {
let mut next: Vec<(Vec<DComplex>, bool)> = Vec::new();
for (opt, oflag) in opts {
for (combo, cflag) in &combos {
let mut c = combo.clone();
c.push(opt.clone());
next.push((c, *cflag || *oflag));
}
}
combos = next;
if combos.len() > 100_000 {
break;
}
}
let input_is_bare = d.leading.is_empty()
&& d.comps.len() == 1
&& d.comps[0].combinators.is_empty()
&& d.comps[0].compound.simples.len() == 1;
let bare_extenders: FxHashSet<&Complex> = match (input_is_bare, orig_scope) {
(true, Some(scope)) => extensions
.iter()
.filter(|e| !e.derived && e.origin == scope)
.flat_map(|e| e.extenders.iter())
.collect(),
_ => FxHashSet::default(),
};
let mut out: Vec<(Complex, bool, bool)> = Vec::new();
let mut seen = FxHashSet::default();
for (path, pflag) in combos {
for woven in weave(&path) {
let c = from_dart(&woven);
let r = c.render();
if seen.insert(r) {
let orig = (in_orig && out.is_empty())
|| (input_is_bare && bare_extenders.contains(&c));
out.push((c, in_break || pflag, orig));
}
}
}
out
}
#[derive(Clone, PartialEq, Eq, Debug, Default)]
struct DComplex {
leading: Vec<Combinator>,
comps: Vec<TComp>,
}
impl DComplex {
fn is_useless(&self) -> bool {
self.leading.len() > 1 || self.comps.iter().any(|c| c.combinators.len() > 1)
}
fn with_additional_combinators(mut self, combinators: &[Combinator]) -> DComplex {
if combinators.is_empty() {
return self;
}
match self.comps.last_mut() {
Some(last) => last.combinators.extend_from_slice(combinators),
None => self.leading.extend_from_slice(combinators),
}
self
}
fn concatenate(&self, child: &DComplex) -> DComplex {
if child.leading.is_empty() {
let mut comps = self.comps.clone();
comps.extend(child.comps.iter().cloned());
DComplex {
leading: self.leading.clone(),
comps,
}
} else if !self.comps.is_empty() {
let mut comps = self.comps.clone();
comps
.last_mut()
.expect("non-empty")
.combinators
.extend(child.leading.iter().copied());
comps.extend(child.comps.iter().cloned());
DComplex {
leading: self.leading.clone(),
comps,
}
} else {
let mut leading = self.leading.clone();
leading.extend(child.leading.iter().copied());
DComplex {
leading,
comps: child.comps.clone(),
}
}
}
}
fn to_dart(c: &Complex) -> DComplex {
let Some(first) = c.components.first() else {
return DComplex {
leading: c.trailing.clone(),
comps: Vec::new(),
};
};
let n = c.components.len();
let comps = (0..n)
.map(|i| TComp {
compound: c.components[i].compound.clone(),
combinators: if i + 1 < n {
c.components[i + 1].combinators.clone()
} else {
c.trailing.clone()
},
})
.collect();
DComplex {
leading: first.combinators.clone(),
comps,
}
}
fn from_dart(d: &DComplex) -> Complex {
if d.comps.is_empty() {
return Complex {
components: Vec::new(),
trailing: d.leading.clone(),
};
}
let components = d
.comps
.iter()
.enumerate()
.map(|(i, t)| ComplexComponent {
combinators: if i == 0 {
d.leading.clone()
} else {
d.comps[i - 1].combinators.clone()
},
compound: t.compound.clone(),
})
.collect();
Complex {
components,
trailing: d.comps.last().expect("non-empty").combinators.clone(),
}
}
fn weave(complexes: &[DComplex]) -> Vec<DComplex> {
if complexes.len() <= 1 {
return complexes.to_vec();
}
let mut prefixes: Vec<DComplex> = vec![complexes[0].clone()];
for complex in &complexes[1..] {
if complex.comps.len() == 1 {
for prefix in prefixes.iter_mut() {
*prefix = prefix.concatenate(complex);
}
continue;
}
let Some(last) = complex.comps.last() else {
continue;
};
let mut next: Vec<DComplex> = Vec::new();
for prefix in &prefixes {
for parent_prefix in weave_parents(prefix, complex).unwrap_or_default() {
let mut woven = parent_prefix;
woven.comps.push(last.clone());
next.push(woven);
}
}
prefixes = next;
if prefixes.len() > 100_000 {
break;
}
}
prefixes
}
fn merge_leading_combinators(a: &[Combinator], b: &[Combinator]) -> Option<Vec<Combinator>> {
if a.len() > 1 || b.len() > 1 {
return None;
}
if a.is_empty() {
return Some(b.to_vec());
}
if b.is_empty() || a == b {
return Some(a.to_vec());
}
None
}
#[derive(Clone, PartialEq, Eq, Debug)]
struct TComp {
compound: Compound,
combinators: Vec<Combinator>,
}
fn weave_parents(prefix: &DComplex, base: &DComplex) -> Option<Vec<DComplex>> {
let leading = merge_leading_combinators(&prefix.leading, &base.leading)?;
let mut queue1: std::collections::VecDeque<TComp> = prefix.comps.iter().cloned().collect();
let mut queue2: std::collections::VecDeque<TComp> =
base.comps[..base.comps.len() - 1].iter().cloned().collect();
let trailing_combinators = merge_trailing_combinators(&mut queue1, &mut queue2)?;
let rootish1 = first_if_rootish(&mut queue1);
let rootish2 = first_if_rootish(&mut queue2);
match (rootish1, rootish2) {
(Some(r1), Some(r2)) => {
let rootish = unify_compounds(&r1.compound.simples, &r2.compound.simples)?;
let comp = Compound { simples: rootish };
queue1.push_front(TComp {
compound: comp.clone(),
combinators: r1.combinators,
});
queue2.push_front(TComp {
compound: comp,
combinators: r2.combinators,
});
}
(Some(r), None) | (None, Some(r)) => {
queue1.push_front(r.clone());
queue2.push_front(r);
}
(None, None) => {}
}
let mut groups1 = group_selectors(queue1.iter().cloned());
let mut groups2 = group_selectors(queue2.iter().cloned());
let groups1_vec: Vec<Vec<TComp>> = groups1.iter().cloned().collect();
let groups2_vec: Vec<Vec<TComp>> = groups2.iter().cloned().collect();
let lcs = lcs_groups(&groups2_vec, &groups1_vec);
let mut choices: Vec<Vec<Vec<TComp>>> = Vec::new();
for group in &lcs {
let chunk = chunks_groups(&mut groups1, &mut groups2, |seq| {
seq.front()
.map(|g| complex_is_parent_superselector(g, group))
.unwrap_or(false)
});
let flattened: Vec<Vec<TComp>> = chunk.into_iter().map(flatten_groups).collect();
choices.push(flattened);
choices.push(vec![group.clone()]);
groups1.pop_front();
groups2.pop_front();
}
let tail = chunks_groups(&mut groups1, &mut groups2, |seq| seq.is_empty());
choices.push(tail.into_iter().map(flatten_groups).collect());
for tc in trailing_combinators {
choices.push(tc);
}
let mut results: Vec<Vec<TComp>> = vec![Vec::new()];
for choice in choices.iter().filter(|c| !c.is_empty()) {
let mut next = Vec::new();
for option in choice {
for path in &results {
let mut p = path.clone();
p.extend(option.iter().cloned());
next.push(p);
}
}
results = next;
if results.len() > 100_000 {
break;
}
}
Some(
results
.into_iter()
.map(|comps| DComplex {
leading: leading.clone(),
comps,
})
.collect(),
)
}
fn flatten_groups(groups: Vec<Vec<TComp>>) -> Vec<TComp> {
groups.into_iter().flatten().collect()
}
fn first_if_rootish(queue: &mut std::collections::VecDeque<TComp>) -> Option<TComp> {
let first = queue.front()?;
let is_rootish = first.compound.simples.iter().any(|s| {
if let Simple::Pseudo(text) = s {
is_rootish_pseudo_class(text)
} else {
false
}
});
if is_rootish {
queue.pop_front()
} else {
None
}
}
fn is_rootish_pseudo_class(text: &str) -> bool {
if text.starts_with("::") {
return false;
}
let name = text.trim_start_matches(':');
let base = name.split(['(', ' ']).next().unwrap_or(name).to_ascii_lowercase();
matches!(base.as_str(), "root" | "scope" | "host" | "host-context")
}
#[allow(clippy::type_complexity)]
fn merge_trailing_combinators(
components1: &mut std::collections::VecDeque<TComp>,
components2: &mut std::collections::VecDeque<TComp>,
) -> Option<Vec<Vec<Vec<TComp>>>> {
let mut result: std::collections::VecDeque<Vec<Vec<TComp>>> = std::collections::VecDeque::new();
loop {
let combinators1 = components1
.back()
.map(|c| c.combinators.clone())
.unwrap_or_default();
let combinators2 = components2
.back()
.map(|c| c.combinators.clone())
.unwrap_or_default();
if combinators1.is_empty() && combinators2.is_empty() {
return Some(result.into_iter().collect());
}
if combinators1.len() > 1 || combinators2.len() > 1 {
return None;
}
let c1 = combinators1.first().copied();
let c2 = combinators2.first().copied();
match (c1, c2) {
(Some(Combinator::FollowingSibling), Some(Combinator::FollowingSibling)) => {
let component1 = components1.pop_back()?;
let component2 = components2.pop_back()?;
if compound_is_superselector(&component1.compound, &component2.compound, &[]) {
result.push_front(vec![vec![component2]]);
} else if compound_is_superselector(&component2.compound, &component1.compound, &[]) {
result.push_front(vec![vec![component1]]);
} else {
let mut choices = vec![
vec![component1.clone(), component2.clone()],
vec![component2.clone(), component1.clone()],
];
if let Some(unified) =
unify_compounds(&component1.compound.simples, &component2.compound.simples)
{
choices.push(vec![TComp {
compound: Compound { simples: unified },
combinators: vec![Combinator::FollowingSibling],
}]);
}
result.push_front(choices);
}
}
(Some(Combinator::FollowingSibling), Some(Combinator::NextSibling))
| (Some(Combinator::NextSibling), Some(Combinator::FollowingSibling)) => {
let following_first = c1 == Some(Combinator::FollowingSibling);
let following = if following_first {
components1.pop_back()?
} else {
components2.pop_back()?
};
let next = if following_first {
components2.pop_back()?
} else {
components1.pop_back()?
};
if compound_is_superselector(&following.compound, &next.compound, &[]) {
result.push_front(vec![vec![next]]);
} else {
let mut choices = vec![vec![following.clone(), next.clone()]];
if let Some(unified) =
unify_compounds(&following.compound.simples, &next.compound.simples)
{
choices.push(vec![TComp {
compound: Compound { simples: unified },
combinators: next.combinators.clone(),
}]);
}
result.push_front(choices);
}
}
(Some(Combinator::Child), Some(Combinator::NextSibling))
| (Some(Combinator::Child), Some(Combinator::FollowingSibling)) => {
let sibling = components2.pop_back()?;
result.push_front(vec![vec![sibling]]);
}
(Some(Combinator::NextSibling), Some(Combinator::Child))
| (Some(Combinator::FollowingSibling), Some(Combinator::Child)) => {
let sibling = components1.pop_back()?;
result.push_front(vec![vec![sibling]]);
}
(Some(comb1), Some(comb2)) if comb1 == comb2 => {
let comp1 = components1.pop_back()?;
let comp2 = components2.pop_back()?;
let unified = unify_compounds(&comp1.compound.simples, &comp2.compound.simples)?;
result.push_front(vec![vec![TComp {
compound: Compound { simples: unified },
combinators: vec![comb1],
}]]);
}
(Some(combinator), None) => {
if combinator == Combinator::Child
&& components2
.back()
.map(|d| {
components1
.back()
.map(|c| compound_is_superselector(&d.compound, &c.compound, &[]))
.unwrap_or(false)
})
.unwrap_or(false)
{
components2.pop_back();
}
let comp = components1.pop_back()?;
result.push_front(vec![vec![comp]]);
}
(None, Some(combinator)) => {
if combinator == Combinator::Child
&& components1
.back()
.map(|d| {
components2
.back()
.map(|c| compound_is_superselector(&d.compound, &c.compound, &[]))
.unwrap_or(false)
})
.unwrap_or(false)
{
components1.pop_back();
}
let comp = components2.pop_back()?;
result.push_front(vec![vec![comp]]);
}
_ => return None,
}
}
}
fn group_selectors<I: IntoIterator<Item = TComp>>(components: I) -> std::collections::VecDeque<Vec<TComp>> {
let mut groups: std::collections::VecDeque<Vec<TComp>> = std::collections::VecDeque::new();
let mut group: Vec<TComp> = Vec::new();
for component in components {
let ends_group = component.combinators.is_empty();
group.push(component);
if ends_group {
groups.push_back(std::mem::take(&mut group));
}
}
if !group.is_empty() {
groups.push_back(group);
}
groups
}
fn must_unify(complex1: &[TComp], complex2: &[TComp]) -> bool {
let mut unique: Vec<&Simple> = Vec::new();
for component in complex1 {
for simple in &component.compound.simples {
if is_unique_simple(simple) && !unique.contains(&simple) {
unique.push(simple);
}
}
}
if unique.is_empty() {
return false;
}
complex2.iter().any(|component| {
component
.compound
.simples
.iter()
.any(|simple| is_unique_simple(simple) && unique.contains(&simple))
})
}
fn is_unique_simple(simple: &Simple) -> bool {
matches!(simple, Simple::Id(_)) || is_pseudo_element(simple)
}
fn chunks_groups<F>(
q1: &mut std::collections::VecDeque<Vec<TComp>>,
q2: &mut std::collections::VecDeque<Vec<TComp>>,
done: F,
) -> Vec<Vec<Vec<TComp>>>
where
F: Fn(&std::collections::VecDeque<Vec<TComp>>) -> bool,
{
let mut chunk1: Vec<Vec<TComp>> = Vec::new();
while !done(q1) {
match q1.pop_front() {
Some(g) => chunk1.push(g),
None => break,
}
}
let mut chunk2: Vec<Vec<TComp>> = Vec::new();
while !done(q2) {
match q2.pop_front() {
Some(g) => chunk2.push(g),
None => break,
}
}
match (chunk1.is_empty(), chunk2.is_empty()) {
(true, true) => Vec::new(),
(true, false) => vec![chunk2],
(false, true) => vec![chunk1],
(false, false) => {
let mut a = chunk1.clone();
a.extend(chunk2.clone());
let mut b = chunk2;
b.extend(chunk1);
vec![a, b]
}
}
}
fn lcs_groups(list1: &[Vec<TComp>], list2: &[Vec<TComp>]) -> Vec<Vec<TComp>> {
let n = list1.len();
let m = list2.len();
let mut lengths = vec![vec![0usize; m + 1]; n + 1];
let mut selections: Vec<Vec<Option<Vec<TComp>>>> = vec![vec![None; m]; n];
for i in 0..n {
for j in 0..m {
let sel = lcs_select_groups(&list1[i], &list2[j]);
let has = sel.is_some();
selections[i][j] = sel;
lengths[i + 1][j + 1] = if has {
lengths[i][j] + 1
} else {
lengths[i + 1][j].max(lengths[i][j + 1])
};
}
}
let mut out = Vec::new();
backtrack_groups(n as isize - 1, m as isize - 1, &lengths, &selections, &mut out);
out
}
fn backtrack_groups(
i: isize,
j: isize,
lengths: &[Vec<usize>],
selections: &[Vec<Option<Vec<TComp>>>],
out: &mut Vec<Vec<TComp>>,
) {
if i == -1 || j == -1 {
return;
}
let (ui, uj) = (i as usize, j as usize);
if let Some(sel) = &selections[ui][uj] {
backtrack_groups(i - 1, j - 1, lengths, selections, out);
out.push(sel.clone());
return;
}
if lengths[ui + 1][uj] > lengths[ui][uj + 1] {
backtrack_groups(i, j - 1, lengths, selections, out);
} else {
backtrack_groups(i - 1, j, lengths, selections, out);
}
}
fn lcs_select_groups(group1: &[TComp], group2: &[TComp]) -> Option<Vec<TComp>> {
if group1 == group2 {
return Some(group1.to_vec());
}
if complex_is_parent_superselector(group1, group2) {
return Some(group2.to_vec());
}
if complex_is_parent_superselector(group2, group1) {
return Some(group1.to_vec());
}
if !must_unify(group1, group2) {
return None;
}
let c1 = DComplex {
leading: Vec::new(),
comps: group1.to_vec(),
};
let c2 = DComplex {
leading: Vec::new(),
comps: group2.to_vec(),
};
let unified = unify_complex_list(&[c1, c2])?;
match unified.as_slice() {
[single] => Some(single.comps.clone()),
_ => None,
}
}
fn complex_is_parent_superselector(complex1: &[TComp], complex2: &[TComp]) -> bool {
if complex1.len() > complex2.len() {
return false;
}
let base = TComp {
compound: Compound {
simples: vec![Simple::Placeholder("<temp>".to_string())],
},
combinators: Vec::new(),
};
let mut c1 = complex1.to_vec();
c1.push(base.clone());
let mut c2 = complex2.to_vec();
c2.push(base);
complex_is_superselector_trailing(&c1, &c2)
}
struct PseudoParts {
head: String,
name: String,
arg: String,
}
fn parse_pseudo_parts(text: &str) -> Option<PseudoParts> {
let open = text.find('(')?;
if !text.ends_with(')') {
return None;
}
let head = text[..open].to_string();
let name = head.trim_start_matches(':').to_ascii_lowercase();
let arg = text[open + 1..text.len() - 1].to_string();
Some(PseudoParts { head, name, arg })
}
fn complex_has_selector_pseudo(complex: &Complex) -> bool {
complex.components.iter().any(|comp| {
comp.compound.simples.iter().any(|s| {
let Simple::Pseudo(text) = s else { return false };
parse_pseudo_parts(text).is_some_and(|p| is_selector_pseudo(&p.name))
})
})
}
fn pseudo_arg_has_target(complex: &Complex, targets: &FxHashSet<Simple>, only_not: bool) -> bool {
complex.components.iter().any(|comp| {
comp.compound.simples.iter().any(|s| {
let Simple::Pseudo(text) = s else { return false };
let Some(parts) = parse_pseudo_parts(text) else {
return false;
};
if !is_selector_pseudo(&parts.name) || (only_not && unvendor(&parts.name) != "not") {
return false;
}
parse_list(&parts.arg).is_some_and(|list| {
list.iter().any(|c| {
c.components
.iter()
.any(|cc| cc.compound.simples.iter().any(|inner| targets.contains(inner)))
})
})
})
})
}
fn pseudo_arg_has_target_deep(complex: &Complex, targets: &FxHashSet<Simple>) -> bool {
complex.components.iter().any(|comp| {
comp.compound.simples.iter().any(|s| {
let Simple::Pseudo(text) = s else { return false };
let Some(parts) = parse_pseudo_parts(text) else {
return false;
};
if !is_selector_pseudo(&parts.name) {
return false;
}
parse_list(&parts.arg).is_some_and(|list| {
list.iter().any(|c| {
c.components
.iter()
.any(|cc| cc.compound.simples.iter().any(|inner| targets.contains(inner)))
|| pseudo_arg_has_target_deep(c, targets)
})
})
})
})
}
fn complex_may_match_targets(complex: &Complex, targets: &FxHashSet<Simple>) -> bool {
if targets.is_empty() {
return false;
}
complex
.components
.iter()
.any(|comp| comp.compound.simples.iter().any(|s| targets.contains(s)))
|| pseudo_arg_has_target_deep(complex, targets)
}
fn collect_match_simples(complex: &Complex, out: &mut FxHashSet<Simple>) {
for comp in &complex.components {
for s in &comp.compound.simples {
out.insert(s.clone());
let Simple::Pseudo(text) = s else { continue };
let Some(parts) = parse_pseudo_parts(text) else {
continue;
};
if !is_selector_pseudo(&parts.name) {
continue;
}
if let Some(list) = parse_list(&parts.arg) {
for c in &list {
collect_match_simples(c, out);
}
}
}
}
}
fn is_selector_pseudo(name: &str) -> bool {
matches!(
unvendor(name),
"not" | "is" | "matches" | "where" | "any" | "current" | "has" | "host" | "host-context" | "slotted"
) || name.ends_with("-any")
}
fn unvendor(name: &str) -> &str {
let bytes = name.as_bytes();
if bytes.len() < 2 || bytes[0] != b'-' || bytes[1] == b'-' {
return name;
}
for i in 2..bytes.len() {
if bytes[i] == b'-' {
return &name[i + 1..];
}
}
name
}
fn extend_list(list: &[Complex], extensions: &[Extension]) -> Vec<Complex> {
let all_orig: Vec<bool> = vec![true; list.len()];
let (result, changed) =
extend_to_fixpoint_inner(list, &[], &all_orig, None, extensions, CartesianOrder::Fold, false);
if !changed {
return list.to_vec();
}
let source_spec = source_specificity_map(extensions);
trim(
result.into_iter().map(|(c, _, o)| (c, o)).collect(),
&source_spec,
)
}
fn single_extension(src: &Extension, target: Simple, extender: Complex, break_flag: bool) -> Extension {
Extension {
target: Some(target),
extenders: vec![extender],
extender_breaks: vec![break_flag],
optional: src.optional,
matched: std::rc::Rc::clone(&src.matched),
origin: src.origin.clone(),
reg_idx: src.reg_idx,
derived: false,
via_origin: None,
origin_closure: std::rc::Rc::clone(&src.origin_closure),
}
}
#[allow(clippy::too_many_arguments)]
fn register_derived(
registry: &mut Vec<Extension>,
sources: &mut FxHashMap<Simple, FxHashMap<(Complex, String), usize>>,
by_extender: &mut FxHashMap<Simple, Vec<usize>>,
batch: &mut Vec<Extension>,
batch_target: &Simple,
old: &Extension,
old_target: &Simple,
via: &Extension,
complex: Complex,
) {
assert_render_injective(&complex);
let target_sources = sources.entry(old_target.clone()).or_default();
let source_key = (complex.clone(), old.origin.clone());
if let Some(&idx) = target_sources.get(&source_key) {
if !old.optional {
registry[idx].optional = false;
}
return;
}
let idx = registry.len();
let mut simples = Vec::new();
all_simples_of(&complex, &mut simples);
target_sources.insert(source_key, idx);
let mut derived = single_extension(old, old_target.clone(), complex, false);
derived.derived = true;
derived.via_origin = Some(via.origin.clone());
derived.reg_idx = via.reg_idx;
registry.push(derived.clone());
if old_target == batch_target {
batch.push(derived);
}
for s in simples {
assert_simple_render_injective(&s);
by_extender.entry(s).or_default().push(idx);
}
}
fn expand_extensions(input: &[Extension]) -> (Vec<Vec<Extension>>, Vec<Extension>, Vec<usize>) {
let mut registry: Vec<Extension> = Vec::new();
let mut sources: FxHashMap<Simple, FxHashMap<(Complex, String), usize>> = FxHashMap::default();
let mut by_extender: FxHashMap<Simple, Vec<usize>> = FxHashMap::default();
let mut batches: Vec<Vec<Extension>> = Vec::new();
let mut registry_marks: Vec<usize> = Vec::new();
let source_spec = source_specificity_map(input);
let all_targets: FxHashSet<Simple> = input.iter().filter_map(|e| e.target.clone()).collect();
for ext in input {
let Some(target) = ext.target.clone() else {
continue;
};
let existing: Vec<usize> = by_extender.get(&target).cloned().unwrap_or_default();
let self_ref_extender = ext
.extenders
.iter()
.any(|c| pseudo_arg_has_target_deep(c, &all_targets));
let visible_registry: Vec<Extension> = if registry.is_empty() {
Vec::new()
} else {
registry
.iter()
.filter(|r| ext.origin_closure.contains(&r.origin))
.cloned()
.collect()
};
let pre_extended: Vec<(Complex, bool)> = {
let mut out: Vec<(Complex, bool)> = Vec::new();
let mut seen: FxHashSet<Complex> = FxHashSet::default();
for (j, extender) in ext.extenders.iter().enumerate() {
let flag = ext.extender_breaks.get(j).copied().unwrap_or(false);
let products = if registry.is_empty() {
vec![extender.clone()]
} else if self_ref_extender {
extend_complex(extender, ®istry)
} else if visible_registry.is_empty() {
vec![extender.clone()]
} else {
let empty: FxHashMap<Complex, bool> = FxHashMap::default();
trim(
extend_complex_breaks(
extender,
false,
true,
Some(&ext.origin),
&visible_registry,
&empty,
CartesianOrder::Fold,
)
.into_iter()
.map(|(c, _, o)| (c, o))
.collect(),
&source_spec,
)
};
for c in products {
if seen.insert(c.clone()) {
out.push((c, flag));
}
}
}
out
};
let mut batch: Vec<Extension> = Vec::new();
let mut new_slice: Vec<Extension> = Vec::new();
for (extender, flag) in pre_extended.iter().map(|(c, f)| (c, *f)) {
assert_render_injective(extender);
let target_sources = sources.entry(target.clone()).or_default();
let source_key = (extender.clone(), ext.origin.clone());
if let Some(&idx) = target_sources.get(&source_key) {
if !ext.optional {
registry[idx].optional = false;
}
continue;
}
let idx = registry.len();
target_sources.insert(source_key, idx);
let single = single_extension(ext, target.clone(), extender.clone(), flag);
new_slice.push(single.clone());
batch.push(single.clone());
registry.push(single);
let mut simples = Vec::new();
all_simples_of(extender, &mut simples);
for s in simples {
assert_simple_render_injective(&s);
by_extender.entry(s).or_default().push(idx);
}
}
let process: Vec<usize> = if existing.is_empty() {
Vec::new()
} else {
by_extender.get(&target).cloned().unwrap_or_default()
};
if !new_slice.is_empty() && !process.is_empty() {
for old_idx in process {
if !consume_extend_work() {
break;
}
let old = registry[old_idx].clone();
if !ext.origin_closure.contains(&old.origin) {
continue;
}
let Some(old_target) = old.target.clone() else {
continue;
};
let old_extender = old.extenders[0].clone();
let empty: FxHashMap<Complex, bool> = FxHashMap::default();
let extended = trim(
extend_complex_breaks(
&old_extender,
false,
true,
Some(&old.origin),
&new_slice,
&empty,
CartesianOrder::Fold,
)
.into_iter()
.map(|(c, _, o)| (c, o))
.collect(),
&source_spec,
);
let mut iter = extended.into_iter().peekable();
if iter.peek() == Some(&old_extender) {
iter.next();
}
for complex in iter {
register_derived(
&mut registry,
&mut sources,
&mut by_extender,
&mut batch,
&target,
&old,
&old_target,
ext,
complex,
);
}
}
}
if batch.is_empty() {
batch.push(Extension {
target: Some(target.clone()),
extenders: Vec::new(),
extender_breaks: Vec::new(),
optional: ext.optional,
matched: std::rc::Rc::clone(&ext.matched),
origin: ext.origin.clone(),
reg_idx: ext.reg_idx,
derived: false,
via_origin: None,
origin_closure: std::rc::Rc::clone(&ext.origin_closure),
});
}
batches.push(batch);
registry_marks.push(registry.len());
}
(batches, registry, registry_marks)
}
fn extend_list_batch(
list: &[(Complex, bool, bool, String)],
batch: &[Extension],
orig_scope: Option<&str>,
source_spec: &FxHashMap<Simple, u64>,
) -> Vec<(Complex, bool, bool, String)> {
let Some(rep) = batch.first() else {
return list.to_vec();
};
let batch_origin = rep.origin.clone();
let batch_closure = std::rc::Rc::clone(&rep.origin_closure);
let mut ext_breaks: FxHashMap<Complex, bool> = FxHashMap::default();
for ext in batch {
for (j, c) in ext.extenders.iter().enumerate() {
let flag = ext.extender_breaks.get(j).copied().unwrap_or(false);
let e = ext_breaks.entry(c.clone()).or_insert(false);
*e = *e || flag;
}
}
let batch_targets: FxHashSet<Simple> = batch.iter().filter_map(|e| e.target.clone()).collect();
let mut out: Vec<(Complex, bool, bool)> = Vec::new();
let mut origin_of: FxHashMap<Hashed<Complex>, String> = FxHashMap::default();
let mut changed = false;
for (complex, in_break, c_orig, c_origin) in list {
let visible = batch_closure.contains(c_origin);
let can_match = visible && complex_may_match_targets(complex, &batch_targets);
let products = if can_match && consume_extend_work() && out.len() <= 100_000 {
extend_complex_breaks(complex, *in_break, *c_orig, orig_scope, batch, &ext_breaks, CartesianOrder::Fold)
} else {
vec![(complex.clone(), *in_break, *c_orig)]
};
if can_match && !(products.len() == 1 && products[0].0 == *complex) {
changed = true;
}
for (c, f, o_flag) in products {
use std::collections::hash_map::Entry;
let key = Hashed::new(c.clone());
match origin_of.entry(key) {
Entry::Vacant(slot) => {
let o = if c == *complex {
c_origin.clone()
} else {
batch_origin.clone()
};
slot.insert(o);
out.push((c, f, o_flag));
}
Entry::Occupied(_) => {
if o_flag {
out.push((c, f, o_flag));
}
}
}
}
}
if !changed {
return list.to_vec();
}
trim_breaks(out, source_spec)
.into_iter()
.map(|(c, f, o_flag)| {
let key = Hashed::new(c);
let o = origin_of.remove(&key).unwrap_or_else(|| batch_origin.clone());
(key.value, f, o_flag, o)
})
.collect()
}
fn extend_to_fixpoint_breaks(
list: &[Complex],
list_breaks: &[bool],
list_origs: &[bool],
orig_scope: Option<&str>,
extensions: &[Extension],
order: CartesianOrder,
) -> (Vec<(Complex, bool, bool)>, bool) {
extend_to_fixpoint_inner(list, list_breaks, list_origs, orig_scope, extensions, order, true)
}
fn extend_to_fixpoint_inner(
list: &[Complex],
list_breaks: &[bool],
list_origs: &[bool],
orig_scope: Option<&str>,
extensions: &[Extension],
order: CartesianOrder,
refeed: bool,
) -> (Vec<(Complex, bool, bool)>, bool) {
let mut ext_breaks: FxHashMap<Complex, bool> = FxHashMap::default();
for ext in extensions {
for (j, c) in ext.extenders.iter().enumerate() {
let flag = ext.extender_breaks.get(j).copied().unwrap_or(false);
let e = ext_breaks.entry(c.clone()).or_insert(false);
*e = *e || flag;
}
}
let mut result: Vec<(Complex, bool, bool)> = Vec::new();
let mut seen: FxHashSet<String> = FxHashSet::default();
let mut changed = false;
let mut queue: std::collections::VecDeque<(Complex, bool, bool, bool)> = list
.iter()
.enumerate()
.map(|(i, c)| {
(
c.clone(),
list_breaks.get(i).copied().unwrap_or(false),
true,
list_origs.get(i).copied().unwrap_or(true),
)
})
.collect();
while let Some((complex, in_break, is_input, is_orig)) = queue.pop_front() {
if !consume_extend_work() || result.len() > 100_000 {
break;
}
let products =
extend_complex_breaks(&complex, in_break, is_orig, orig_scope, extensions, &ext_breaks, order);
if is_input && !(products.len() == 1 && products[0].0.render() == complex.render()) {
changed = true;
}
for (c, flag, orig) in products {
let rendered = c.render();
let len = rendered.len();
if seen.insert(rendered) || orig {
if refeed && complex_has_selector_pseudo(&c) && len <= EXTEND_REFEED_MAX_LEN {
queue.push_back((c.clone(), flag, false, false));
}
result.push((c, flag, orig));
}
}
}
(result, changed)
}
const MAX_PSEUDO_DEPTH: usize = 8;
thread_local! {
static PSEUDO_DEPTH: std::cell::Cell<usize> = const { std::cell::Cell::new(0) };
}
const EXTEND_WORK_BUDGET: usize = 20_000;
const EXTEND_REFEED_MAX_LEN: usize = 8_192;
thread_local! {
static EXTEND_WORK: std::cell::Cell<usize> = const { std::cell::Cell::new(EXTEND_WORK_BUDGET) };
}
fn reset_extend_budget() {
if PSEUDO_DEPTH.with(|d| d.get()) == 0 {
EXTEND_WORK.with(|w| w.set(EXTEND_WORK_BUDGET));
}
}
fn consume_extend_work() -> bool {
EXTEND_WORK.with(|w| {
let left = w.get();
if left == 0 {
return false;
}
w.set(left - 1);
true
})
}
fn extend_pseudo(text: &str, extensions: &[Extension]) -> Option<Vec<Simple>> {
let parts = parse_pseudo_parts(text)?;
if !is_selector_pseudo(&parts.name) {
return None;
}
if PSEUDO_DEPTH.with(|d| d.get()) >= MAX_PSEUDO_DEPTH {
return None;
}
let original = parse_list(&parts.arg)?;
PSEUDO_DEPTH.with(|d| d.set(d.get() + 1));
let extended = extend_list(&original, extensions);
PSEUDO_DEPTH.with(|d| d.set(d.get() - 1));
finish_extend_pseudo(&parts, &original, extended)
}
fn extend_pseudo_compound_target(
text: &str,
targets: &[Compound],
extenders: &[Complex],
replace: bool,
) -> Option<Vec<Simple>> {
if PSEUDO_DEPTH.with(|d| d.get()) >= MAX_PSEUDO_DEPTH {
return None;
}
if let Some((name, anb, sel)) = nth_of_parts(text) {
let original = parse_list(sel)?;
PSEUDO_DEPTH.with(|d| d.set(d.get() + 1));
let extended = extend_compound_target(&original, targets, extenders, replace);
PSEUDO_DEPTH.with(|d| d.set(d.get() - 1));
return finish_nth_of(name, anb, &original, extended);
}
let parts = parse_pseudo_parts(text)?;
if !is_selector_pseudo(&parts.name) {
return None;
}
let original = parse_list(&parts.arg)?;
PSEUDO_DEPTH.with(|d| d.set(d.get() + 1));
let extended = extend_compound_target(&original, targets, extenders, replace);
PSEUDO_DEPTH.with(|d| d.set(d.get() - 1));
finish_extend_pseudo(&parts, &original, extended)
}
fn finish_nth_of(name: &str, anb: &str, original: &[Complex], extended: Vec<Complex>) -> Option<Vec<Simple>> {
let mut flattened: Vec<Complex> = Vec::new();
let mut seen: FxHashSet<String> = FxHashSet::default();
let mut push = |c: Complex, flattened: &mut Vec<Complex>| {
if seen.insert(c.render()) {
flattened.push(c);
}
};
for c in extended {
match single_pseudo(&c).and_then(|t| nth_of_parts(t)) {
Some((n, a, inner_sel)) if n == name && a == anb => {
if let Some(list) = parse_list(inner_sel) {
for inner in list {
push(inner, &mut flattened);
}
}
}
Some(_) => {}
None => push(c, &mut flattened),
}
}
if flattened.len() == original.len()
&& flattened
.iter()
.zip(original.iter())
.all(|(a, b)| a.render() == b.render())
{
return None;
}
let inner = flattened
.iter()
.map(|c| c.render())
.collect::<Vec<_>>()
.join(", ");
if inner.is_empty() {
return None;
}
Some(vec![Simple::Pseudo(format!("{name}({anb} of {inner})"))])
}
fn single_pseudo(complex: &Complex) -> Option<&str> {
let [comp] = complex.components.as_slice() else {
return None;
};
let [Simple::Pseudo(text)] = comp.compound.simples.as_slice() else {
return None;
};
Some(text)
}
fn expand_pseudos_compound_target(
compound: &Compound,
targets: &[Compound],
extenders: &[Complex],
replace: bool,
) -> Compound {
let mut simples: Vec<Simple> = Vec::new();
for s in &compound.simples {
match s {
Simple::Pseudo(text) => {
match extend_pseudo_compound_target(text, targets, extenders, replace) {
None => simples.push(s.clone()),
Some(replacement) => {
for r in replacement {
let dup_of_other_original =
r != *s && compound.simples.iter().any(|o| o != s && *o == r);
if dup_of_other_original || simples.contains(&r) {
continue;
}
simples.push(r);
}
}
}
}
other => simples.push(other.clone()),
}
}
Compound { simples }
}
fn finish_extend_pseudo(
parts: &PseudoParts,
original: &[Complex],
extended: Vec<Complex>,
) -> Option<Vec<Simple>> {
if extended.len() == original.len()
&& extended
.iter()
.zip(original.iter())
.all(|(a, b)| a.render() == b.render())
{
return None;
}
let original_has_complex = original.iter().any(|c| c.components.len() > 1);
let mut complexes: Vec<Complex> =
if parts.name == "not" && !original_has_complex && extended.iter().any(|c| c.components.len() == 1) {
extended.into_iter().filter(|c| c.components.len() <= 1).collect()
} else {
extended
};
let mut unwrapped: Vec<Complex> = Vec::new();
for complex in complexes.drain(..) {
let inner = single_pseudo_inner(&complex, &parts.name);
match inner {
PseudoUnwrap::Keep => unwrapped.push(complex),
PseudoUnwrap::Drop => {}
PseudoUnwrap::Replace(list) => unwrapped.extend(list),
}
}
let complexes = unwrapped;
if parts.name == "not" && original.len() == 1 {
let result: Vec<Simple> = complexes
.into_iter()
.map(|c| Simple::Pseudo(format!("{}({})", parts.head, c.render())))
.collect();
if result.is_empty() {
return None;
}
return Some(result);
}
if complexes.is_empty() {
return None;
}
let mut seen: FxHashSet<String> = FxHashSet::default();
let rendered: Vec<String> = complexes
.iter()
.map(|c| c.render())
.filter(|r| seen.insert(r.clone()))
.collect();
if rendered.len() == original.len()
&& rendered
.iter()
.zip(original.iter())
.all(|(a, b)| *a == b.render())
{
return None;
}
Some(vec![Simple::Pseudo(format!(
"{}({})",
parts.head,
rendered.join(", ")
))])
}
enum PseudoUnwrap {
Keep,
Drop,
Replace(Vec<Complex>),
}
fn single_pseudo_inner(complex: &Complex, outer_name: &str) -> PseudoUnwrap {
if complex.components.len() != 1 {
return PseudoUnwrap::Keep;
}
let compound = &complex.components[0].compound;
if compound.simples.len() != 1 {
return PseudoUnwrap::Keep;
}
let Simple::Pseudo(text) = &compound.simples[0] else {
return PseudoUnwrap::Keep;
};
let Some(inner) = parse_pseudo_parts(text) else {
return PseudoUnwrap::Keep;
};
let Some(inner_list) = parse_list(&inner.arg) else {
return PseudoUnwrap::Keep;
};
match unvendor(outer_name) {
"not" => {
if matches!(unvendor(&inner.name), "is" | "matches" | "where") {
PseudoUnwrap::Replace(inner_list)
} else {
PseudoUnwrap::Drop
}
}
"is" | "matches" | "where" | "any" | "current" | "nth-child" | "nth-last-child" => {
if inner.name == outer_name {
PseudoUnwrap::Replace(inner_list)
} else {
PseudoUnwrap::Drop
}
}
_ => PseudoUnwrap::Keep,
}
}
fn expand_pseudos_in_compound(compound: &Compound, extensions: &[Extension]) -> Compound {
let mut simples: Vec<Simple> = Vec::new();
for s in &compound.simples {
match s {
Simple::Pseudo(text) => {
match extend_pseudo(text, extensions) {
None => simples.push(s.clone()),
Some(replacement) => {
for r in replacement {
let dup_of_other_original =
r != *s && compound.simples.iter().any(|o| o != s && *o == r);
if dup_of_other_original || simples.contains(&r) {
continue;
}
simples.push(r);
}
}
}
}
other => simples.push(other.clone()),
}
}
Compound { simples }
}
fn extend_component(
comp: &TComp,
extensions: &[Extension],
ext_breaks: &FxHashMap<Complex, bool>,
order: CartesianOrder,
) -> Option<Vec<(DComplex, bool)>> {
let effective = expand_pseudos_in_compound(&comp.compound, extensions);
let pseudo_changed = effective.simples != comp.compound.simples;
let comp = TComp {
compound: effective,
combinators: comp.combinators.clone(),
};
let comp = ∁
let simples = &comp.compound.simples;
let mut per_simple: Vec<Vec<Option<(Complex, bool)>>> = Vec::new();
let mut any = false;
for s in simples {
let mut opts: Vec<Option<(Complex, bool)>> = vec![None];
let mut seen: FxHashSet<Complex> = FxHashSet::default();
for extender in collect_extenders(s, extensions, &mut Vec::new()) {
if seen.contains(&extender) {
continue;
}
let flag = ext_breaks.get(&extender).copied().unwrap_or(false);
seen.insert(extender.clone());
opts.push(Some((extender, flag)));
any = true;
}
per_simple.push(opts);
}
let options_first = DComplex {
leading: Vec::new(),
comps: vec![comp.clone()],
};
if !any {
return pseudo_changed.then_some(vec![(options_first, false)]);
}
let mut options: Vec<(DComplex, bool)> = vec![(options_first, false)];
let mut paths: Vec<Vec<&Option<(Complex, bool)>>> = vec![Vec::new()];
for opts in &per_simple {
let mut next = Vec::new();
if order == CartesianOrder::OneShot {
for opt in opts {
for path in &paths {
let mut p = path.clone();
p.push(opt);
next.push(p);
}
}
} else {
for path in &paths {
for opt in opts {
let mut p = path.clone();
p.push(opt);
next.push(p);
}
}
}
paths = next;
if paths.len() > 100_000 {
break;
}
}
let mut seen: FxHashSet<String> = FxHashSet::default();
seen.insert(render_dcomplex(&options[0].0));
for path in &paths {
if path.iter().all(|o| o.is_none()) {
continue;
}
let flag = path.iter().any(|o| matches!(o, Some((_, true))));
let plain: Vec<Option<Complex>> = path.iter().map(|o| o.as_ref().map(|(c, _)| c.clone())).collect();
let refs: Vec<&Option<Complex>> = plain.iter().collect();
for d in build_extended_compound(comp, simples, &refs) {
let key = render_dcomplex(&d);
if seen.insert(key) {
options.push((d, flag));
}
}
}
Some(options)
}
fn collect_extenders(target: &Simple, extensions: &[Extension], _stack: &mut Vec<Simple>) -> Vec<Complex> {
let mut out: Vec<Complex> = Vec::new();
for ext in extensions {
let Some(t) = &ext.target else { continue };
if t != target {
continue;
}
ext.matched.set(true);
for extender in &ext.extenders {
out.push(extender.clone());
}
}
out
}
fn build_extended_compound(comp: &TComp, simples: &[Simple], path: &[&Option<Complex>]) -> Vec<DComplex> {
let mut base: Vec<Simple> = Vec::new();
let mut extenders: Vec<&Complex> = Vec::new();
for (i, choice) in path.iter().enumerate() {
match choice {
None => base.push(simples[i].clone()),
Some(ext) => extenders.push(ext),
}
}
let mut to_unify: Vec<DComplex> = Vec::new();
if !base.is_empty() {
to_unify.push(DComplex {
leading: Vec::new(),
comps: vec![TComp {
compound: Compound { simples: base },
combinators: Vec::new(),
}],
});
}
for ext in &extenders {
let d = to_dart(ext);
if d.is_useless() {
return Vec::new();
}
to_unify.push(d);
}
let Some(unified) = unify_complex_list(&to_unify) else {
return Vec::new();
};
unified
.into_iter()
.map(|complex| complex.with_additional_combinators(&comp.combinators))
.filter(|complex| !complex.is_useless())
.collect()
}
fn render_dcomplex(d: &DComplex) -> String {
from_dart(d).render()
}
fn unify_compounds(base: &[Simple], extra: &[Simple]) -> Option<Vec<Simple>> {
if host_unify_invalid(base, extra) {
return None;
}
let mut result: Vec<Simple> = base.to_vec();
let mut pseudo_result: Vec<Simple> = Vec::new();
let mut pseudo_element_found = false;
for simple in extra {
if pseudo_element_found && matches!(simple, Simple::Pseudo(_)) {
pseudo_result = simple_unify(simple, &pseudo_result)?;
} else {
if is_pseudo_element(simple) {
pseudo_element_found = true;
}
result = simple_unify(simple, &result)?;
}
}
result.extend(pseudo_result);
if result.is_empty() {
return None;
}
Some(result)
}
fn simple_unify(this: &Simple, compound: &[Simple]) -> Option<Vec<Simple>> {
match this {
Simple::Universal { .. } => match compound.split_first() {
Some((first @ (Simple::Universal { .. } | Simple::Type(_)), rest)) => {
let unified = unify_universal_and_element(this, first)?;
let mut out = vec![unified];
out.extend_from_slice(rest);
Some(out)
}
None => Some(vec![this.clone()]),
Some(_) => {
if universal_ns_droppable(this) {
Some(compound.to_vec())
} else {
let mut out = vec![this.clone()];
out.extend_from_slice(compound);
Some(out)
}
}
},
Simple::Type(_) => match compound.first() {
Some(first @ (Simple::Universal { .. } | Simple::Type(_))) => {
let unified = unify_universal_and_element(this, first)?;
let mut out = vec![unified];
out.extend_from_slice(&compound[1..]);
Some(out)
}
_ => {
let mut out = vec![this.clone()];
out.extend_from_slice(compound);
Some(out)
}
},
Simple::Pseudo(_) => {
if compound.len() == 1 && matches!(compound[0], Simple::Universal { .. }) {
return simple_unify(&compound[0], std::slice::from_ref(this));
}
if compound.contains(this) {
return Some(compound.to_vec());
}
if is_selector_list_pseudo(this) && !compound.is_empty() && compound.iter().all(is_host_pseudo) {
let mut out = vec![this.clone()];
out.extend_from_slice(compound);
return Some(out);
}
let this_is_element = is_pseudo_element(this);
let mut out = Vec::new();
let mut added = false;
for s in compound {
if !added && is_pseudo_element(s) {
if this_is_element {
if pseudo_elements_equal(this, s) {
return Some(compound.to_vec());
}
return None;
}
out.push(this.clone());
added = true;
}
out.push(s.clone());
}
if !added {
out.push(this.clone());
}
Some(out)
}
_ => {
if let Simple::Id(id) = this {
if compound
.iter()
.any(|s| matches!(s, Simple::Id(other) if other != id))
{
return None;
}
}
if compound.len() == 1 && matches!(compound[0], Simple::Universal { .. }) {
return simple_unify(&compound[0], std::slice::from_ref(this));
}
if compound.contains(this) {
return Some(compound.to_vec());
}
let mut out = Vec::new();
let mut added = false;
for s in compound {
if !added && matches!(s, Simple::Pseudo(_)) {
out.push(this.clone());
added = true;
}
out.push(s.clone());
}
if !added {
out.push(this.clone());
}
Some(out)
}
}
}
fn universal_ns_droppable(s: &Simple) -> bool {
matches!(s, Simple::Universal { ns } if ns.is_none() || ns.as_deref() == Some("*"))
}
fn unify_universal_and_element(a: &Simple, b: &Simple) -> Option<Simple> {
let (ns1, name1) = namespace_and_name(a)?;
let (ns2, name2) = namespace_and_name(b)?;
let namespace = if ns1 == ns2 || ns2.as_deref() == Some("*") {
ns1.clone()
} else if ns1.as_deref() == Some("*") {
ns2.clone()
} else {
return None;
};
let name = if name1 == name2 || name2.is_none() {
name1.clone()
} else if name1.is_none() || name1.as_deref() == Some("*") {
name2.clone()
} else {
return None;
};
Some(match name {
None => Simple::Universal { ns: namespace },
Some(n) => match namespace {
Some(ns) => Simple::Type(format!("{ns}|{n}")),
None => Simple::Type(n),
},
})
}
fn namespace_and_name(s: &Simple) -> Option<(Option<String>, Option<String>)> {
match s {
Simple::Universal { ns } => Some((ns.clone(), None)),
Simple::Type(t) => {
let (ns, name) = split_type(t);
Some((ns, Some(name)))
}
_ => None,
}
}
fn pseudo_base(s: &Simple) -> Option<String> {
let Simple::Pseudo(text) = s else {
return None;
};
let name = text.trim_start_matches(':');
Some(name.split(['(', ' ']).next().unwrap_or(name).to_ascii_lowercase())
}
fn pseudo_elements_equal(a: &Simple, b: &Simple) -> bool {
match (a, b) {
(Simple::Pseudo(ta), Simple::Pseudo(tb)) => {
let norm = |t: &str| format!("::{}", t.trim_start_matches(':'));
norm(ta) == norm(tb)
}
_ => false,
}
}
fn is_host_pseudo(s: &Simple) -> bool {
matches!(pseudo_base(s).as_deref(), Some("host" | "host-context"))
}
fn is_selector_list_pseudo(s: &Simple) -> bool {
matches!(
pseudo_base(s).as_deref(),
Some("is" | "where" | "matches" | "any" | "-moz-any" | "-webkit-any")
)
}
fn host_compatible(s: &Simple) -> bool {
is_host_pseudo(s) || is_pseudo_element(s) || is_selector_list_pseudo(s)
}
fn host_unify_invalid(base: &[Simple], extra: &[Simple]) -> bool {
let all = || base.iter().chain(extra);
all().any(is_host_pseudo) && all().any(|s| !host_compatible(s))
}
fn is_pseudo_element(s: &Simple) -> bool {
let Simple::Pseudo(text) = s else {
return false;
};
if text.starts_with("::") {
return true;
}
let name = text.trim_start_matches(':');
let base = name.split(['(', ' ']).next().unwrap_or(name).to_ascii_lowercase();
matches!(base.as_str(), "before" | "after" | "first-line" | "first-letter")
}
pub(crate) fn list_is_superselector(sup: &[Complex], sub: &[Complex]) -> bool {
sub.iter()
.all(|c2| sup.iter().any(|c1| complex_is_superselector(c1, c2)))
}
pub(crate) fn unify_complex(c1: &Complex, c2: &Complex) -> Option<Vec<Complex>> {
let unified = unify_complex_list(&[to_dart(c1), to_dart(c2)])?;
let mut out = Vec::new();
let mut seen = FxHashSet::default();
for d in unified {
let complex = from_dart(&d);
if seen.insert(complex.render()) {
out.push(complex);
}
}
if out.is_empty() {
return None;
}
Some(out)
}
fn unify_complex_list(complexes: &[DComplex]) -> Option<Vec<DComplex>> {
if complexes.is_empty() {
return None;
}
if complexes.len() == 1 {
return Some(complexes.to_vec());
}
let mut unified_base: Option<Vec<Simple>> = None;
let mut leading_combinator: Option<Combinator> = None;
let mut trailing_combinator: Option<Combinator> = None;
for complex in complexes {
if complex.is_useless() {
return None;
}
if complex.comps.len() == 1 {
if let [new_leading] = complex.leading.as_slice() {
match leading_combinator {
None => leading_combinator = Some(*new_leading),
Some(lc) if lc != *new_leading => return None,
_ => {}
}
}
}
let base = complex.comps.last()?;
if let [new_trailing] = base.combinators.as_slice() {
if trailing_combinator.is_some_and(|tc| tc != *new_trailing) {
return None;
}
trailing_combinator = Some(*new_trailing);
}
match &mut unified_base {
None => unified_base = Some(base.compound.simples.clone()),
Some(acc) => *acc = unify_compounds(acc, &base.compound.simples)?,
}
}
let without_bases: Vec<DComplex> = complexes
.iter()
.filter(|c| c.comps.len() > 1)
.map(|c| DComplex {
leading: c.leading.clone(),
comps: c.comps[..c.comps.len() - 1].to_vec(),
})
.collect();
let base = DComplex {
leading: leading_combinator.into_iter().collect(),
comps: vec![TComp {
compound: Compound {
simples: unified_base?,
},
combinators: trailing_combinator.into_iter().collect(),
}],
};
let path: Vec<DComplex> = match without_bases.split_last() {
None => vec![base],
Some((last, init)) => {
let mut path = init.to_vec();
path.push(last.concatenate(&base));
path
}
};
let woven = weave(&path);
if woven.is_empty() {
None
} else {
Some(woven)
}
}
pub(crate) fn unify_lists(list1: &[Complex], list2: &[Complex]) -> Option<Vec<Complex>> {
let mut out = Vec::new();
let mut seen = FxHashSet::default();
for c1 in list1 {
for c2 in list2 {
if let Some(unified) = unify_complex(c1, c2) {
for c in unified {
if seen.insert(c.render()) {
out.push(c);
}
}
}
}
}
if out.is_empty() {
return None;
}
Some(out)
}
pub(crate) fn complex_to_list_parts(c: &Complex) -> Vec<String> {
let mut parts = Vec::new();
for comp in &c.components {
for comb in &comp.combinators {
parts.push(comb.as_str().to_string());
}
parts.push(comp.compound.render());
}
for comb in &c.trailing {
parts.push(comb.as_str().to_string());
}
parts
}
pub(crate) fn parse_compound_simples(s: &str) -> Option<Vec<String>> {
let chars: Vec<char> = s.trim().chars().collect();
let mut i = 0;
let compound = parse_compound(&chars, &mut i)?;
skip_ws(&chars, &mut i);
if i != chars.len() {
return None; }
Some(compound.simples.iter().map(Simple::render).collect())
}
pub(crate) fn extend_compound_target(
selectors: &[Complex],
targets: &[Compound],
extenders: &[Complex],
replace: bool,
) -> Vec<Complex> {
reset_extend_budget();
let mut originals: FxHashSet<Complex> = FxHashSet::default();
if !replace {
for complex in selectors {
originals.insert(complex.clone());
}
}
let mut result: Vec<Complex> = Vec::new();
let mut seen: FxHashSet<String> = FxHashSet::default();
for complex in selectors {
let mut queue: std::collections::VecDeque<Complex> = std::collections::VecDeque::new();
queue.push_back(complex.clone());
let mut local_seen: FxHashSet<String> = FxHashSet::default();
let mut promote_first = replace;
while let Some(cur) = queue.pop_front() {
if !consume_extend_work() || result.len() > 100_000 {
break;
}
let cur_rendered = cur.render();
let extended = extend_complex_compound(&cur, targets, extenders, replace);
let is_self_only = extended.len() == 1
&& extended.first().map(Complex::render).as_deref() == Some(cur_rendered.as_str());
for c in extended {
let rendered = c.render();
if promote_first {
let re = extend_complex_compound(&c, targets, extenders, replace);
let terminal = re.len() == 1
&& re.first().map(Complex::render).as_deref() == Some(rendered.as_str());
if terminal {
originals.insert(c.clone());
promote_first = false;
}
}
let redundant = result.iter().any(|r| complex_is_superselector(r, &c));
if !is_self_only
&& rendered != cur_rendered
&& !redundant
&& rendered.len() <= EXTEND_REFEED_MAX_LEN
&& local_seen.insert(rendered.clone())
{
queue.push_back(c.clone());
}
if seen.insert(rendered) {
result.push(c);
}
}
}
}
let source_spec: FxHashMap<Simple, u64> = FxHashMap::default();
trim(
result
.into_iter()
.map(|c| {
let o = originals.contains(&c);
(c, o)
})
.collect(),
&source_spec,
)
}
fn extend_complex_compound(
complex: &Complex,
targets: &[Compound],
extenders: &[Complex],
replace: bool,
) -> Vec<Complex> {
let d = to_dart(complex);
if d.leading.len() > 1 {
return vec![complex.clone()];
}
let mut per_component: Vec<Vec<DComplex>> = Vec::new();
let mut any_extended = false;
for (i, comp) in d.comps.iter().enumerate() {
match extend_component_compound(comp, targets, extenders, replace) {
None => per_component.push(vec![DComplex {
leading: if i == 0 { d.leading.clone() } else { Vec::new() },
comps: vec![comp.clone()],
}]),
Some(extended) => {
any_extended = true;
if i == 0 && !d.leading.is_empty() {
per_component.push(
extended
.into_iter()
.filter(|n| n.leading.is_empty() || n.leading == d.leading)
.map(|n| DComplex {
leading: d.leading.clone(),
comps: n.comps,
})
.collect(),
);
} else {
per_component.push(extended);
}
}
}
}
if !any_extended {
return vec![complex.clone()];
}
let mut combos: Vec<Vec<DComplex>> = vec![Vec::new()];
for opts in &per_component {
let mut next: Vec<Vec<DComplex>> = Vec::new();
for opt in opts {
for combo in &combos {
let mut c = combo.clone();
c.push(opt.clone());
next.push(c);
}
}
combos = next;
if combos.len() > 100_000 {
break;
}
}
let mut out = Vec::new();
let mut seen = FxHashSet::default();
for path in combos {
for woven in weave(&path) {
let c = from_dart(&woven);
let r = c.render();
if seen.insert(r) {
out.push(c);
}
}
}
out
}
fn extend_component_compound(
comp: &TComp,
targets: &[Compound],
extenders: &[Complex],
replace: bool,
) -> Option<Vec<DComplex>> {
let effective = expand_pseudos_compound_target(&comp.compound, targets, extenders, replace);
let pseudo_changed = effective.simples != comp.compound.simples;
let comp = TComp {
compound: effective,
combinators: comp.combinators.clone(),
};
let comp = ∁
let original = DComplex {
leading: Vec::new(),
comps: vec![comp.clone()],
};
let matching: Vec<&Compound> = targets
.iter()
.filter(|t| compound_is_superselector(t, &comp.compound, &[]))
.collect();
if matching.is_empty() {
return pseudo_changed.then_some(vec![original]);
}
let mut options: Vec<DComplex> = Vec::new();
if !replace {
options.push(original);
}
let mut seen: FxHashSet<String> = FxHashSet::default();
for target in matching {
let remaining: Vec<Simple> = comp
.compound
.simples
.iter()
.filter(|s| !target.simples.contains(s))
.cloned()
.collect();
for ext in extenders {
let ext_d = to_dart(ext);
if ext_d.is_useless() {
continue;
}
let Some((last, parents)) = ext_d.comps.split_last() else {
if remaining.is_empty() {
let candidate = ext_d.clone().with_additional_combinators(&comp.combinators);
if !candidate.is_useless() && seen.insert(render_dcomplex(&candidate)) {
options.push(candidate);
}
}
continue;
};
let Some(unified) = unify_compounds(&remaining, &last.compound.simples) else {
continue;
};
let mut comps = parents.to_vec();
comps.push(TComp {
compound: Compound { simples: unified },
combinators: last.combinators.clone(),
});
let candidate = DComplex {
leading: ext_d.leading.clone(),
comps,
}
.with_additional_combinators(&comp.combinators);
if candidate.is_useless() {
continue;
}
let key = render_dcomplex(&candidate);
if seen.insert(key) {
options.push(candidate);
}
}
}
if options.is_empty() {
options.push(DComplex {
leading: Vec::new(),
comps: vec![comp.clone()],
});
}
Some(options)
}
pub(crate) fn selector_contains_simple(s: &str, target: &Simple) -> bool {
for part in split_top(s, ',') {
if let Some(complex) = parse_complex(part.trim()) {
for comp in &complex.components {
if comp.compound.simples.iter().any(|x| x == target) {
return true;
}
}
}
}
false
}
fn simple_specificity(s: &Simple) -> u64 {
match s {
Simple::Universal { .. } => 0,
Simple::Type(t) => {
if t.ends_with('*') {
0
} else {
1
}
}
Simple::Id(_) => 1_000_000,
Simple::Class(_) | Simple::Placeholder(_) | Simple::Attribute(_) => 1000,
Simple::Pseudo(text) => pseudo_specificity(text),
}
}
fn pseudo_specificity(text: &str) -> u64 {
let is_element = text.starts_with("::");
let body = text.trim_start_matches(':');
let (name, arg) = match body.split_once('(') {
Some((n, rest)) => (n.to_ascii_lowercase(), Some(rest.trim_end_matches(')'))),
None => (body.to_ascii_lowercase(), None),
};
let base = unvendor(&name).to_string();
if base == "where" {
return 0;
}
if let Some(arg) = arg {
let selectorish =
matches!(base.as_str(), "is" | "matches" | "any" | "not" | "has") || base.ends_with("-any");
if selectorish {
if let Some(list) = parse_list(arg) {
return list.iter().map(complex_specificity).max().unwrap_or(0);
}
}
}
if is_element {
1
} else {
1000
}
}
fn compound_specificity(c: &Compound) -> u64 {
c.simples.iter().map(simple_specificity).sum()
}
pub(crate) fn complex_specificity(c: &Complex) -> u64 {
c.components
.iter()
.map(|comp| compound_specificity(&comp.compound))
.sum()
}
fn all_simples_of(complex: &Complex, out: &mut Vec<Simple>) {
for comp in &complex.components {
for s in &comp.compound.simples {
out.push(s.clone());
if let Simple::Pseudo(text) = s {
if let Some(open) = text.find('(') {
if text.ends_with(')') {
if let Some(list) = parse_list(&text[open + 1..text.len() - 1]) {
for inner in &list {
all_simples_of(inner, out);
}
}
}
}
}
}
}
}
pub(crate) fn source_specificity_map(extensions: &[Extension]) -> FxHashMap<Simple, u64> {
let mut map: FxHashMap<Simple, u64> = FxHashMap::default();
for ext in extensions {
for complex in &ext.extenders {
let spec = complex_specificity(complex);
let mut simples = Vec::new();
all_simples_of(complex, &mut simples);
for s in simples {
map.entry(s).or_insert(spec);
}
}
}
map
}