1use std::collections::HashSet;
4use std::sync::{Arc, OnceLock};
5
6use crate::engine::css::parser::AttributeSelectorOperator;
7
8use super::parser::{Combinator, ComplexSelector, PseudoClass, Selector};
9
10#[derive(Debug, Clone, Default)]
11pub struct ElementInfo {
12 pub tag_name: String,
13 pub id: Option<String>,
14 pub classes: Vec<String>,
15 pub attributes: Vec<(String, String)>,
16 pub element_index: usize,
18 pub element_count: usize,
20 pub type_index: usize,
22 pub type_count: usize,
24 pub previous_siblings: ElementChain,
28}
29
30#[derive(Debug)]
32struct ChainLink {
33 info: ElementInfo,
34 next: Option<Arc<ChainLink>>,
36 summary: OnceLock<Box<ChainSummary>>,
39}
40
41#[derive(Debug, Default, Clone)]
44struct ChainSummary {
45 tags: HashSet<Box<str>>,
46 ids: HashSet<Box<str>>,
47 classes: HashSet<Box<str>>,
48}
49
50impl ChainSummary {
51 fn collect(start: &ChainLink) -> Box<Self> {
52 let mut summary = match start.next.as_deref().and_then(|next| next.summary.get()) {
54 Some(cached) => (**cached).clone(),
55 None => {
56 let mut summary = Self::default();
57 let mut link = start.next.as_deref();
58 while let Some(current) = link {
59 summary.add(¤t.info);
60 link = current.next.as_deref();
61 }
62 summary
63 }
64 };
65 summary.add(&start.info);
66 Box::new(summary)
67 }
68
69 fn add(&mut self, info: &ElementInfo) {
70 self.tags.insert(info.tag_name.as_str().into());
71 if let Some(id) = &info.id {
72 self.ids.insert(id.as_str().into());
73 }
74 for class in &info.classes {
75 self.classes.insert(class.as_str().into());
76 }
77 }
78
79 fn could_match(&self, selector: &Selector) -> bool {
83 if let Some(tag) = &selector.tag
84 && !self.tags.contains(tag.as_str())
85 {
86 return false;
87 }
88 if let Some(id) = &selector.id
89 && !self.ids.contains(id.as_str())
90 {
91 return false;
92 }
93 selector
94 .classes
95 .iter()
96 .all(|class| self.classes.contains(class.as_str()))
97 }
98}
99
100impl ChainLink {
101 fn summary(&self) -> &ChainSummary {
103 self.summary.get_or_init(|| ChainSummary::collect(self))
104 }
105}
106
107#[derive(Debug, Clone, Default)]
112pub struct ElementChain {
113 head: Option<Arc<ChainLink>>,
114}
115
116impl ElementChain {
117 pub fn prepend(&self, info: Option<ElementInfo>) -> Self {
121 match info {
122 Some(info) => Self {
123 head: Some(Arc::new(ChainLink {
124 info,
125 next: self.head.clone(),
126 summary: OnceLock::new(),
127 })),
128 },
129 None => self.clone(),
130 }
131 }
132
133 pub fn first(&self) -> Option<&ElementInfo> {
135 self.head.as_deref().map(|link| &link.info)
136 }
137
138 pub fn from_vec(elements: Vec<ElementInfo>) -> Self {
140 let mut chain = Self::default();
141 for info in elements.into_iter().rev() {
142 chain = chain.prepend(Some(info));
143 }
144 chain
145 }
146
147 pub fn from_document_order(elements: impl IntoIterator<Item = ElementInfo>) -> Self {
151 let mut chain = Self::default();
152 for info in elements {
153 chain = chain.prepend(Some(info));
154 }
155 chain
156 }
157}
158
159#[derive(Clone, Copy)]
160struct MatchCursor<'a> {
161 link: &'a ChainLink,
162 sibling_link: Option<&'a ChainLink>,
165}
166
167fn matches_an_plus_b(index: usize, a: i32, b: i32) -> bool {
168 let index = index as i32;
169 if a == 0 {
170 return index == b;
171 }
172 let delta = index - b;
173 delta % a == 0 && delta / a >= 0
174}
175
176impl Selector {
177 fn matches_base(&self, element: &ElementInfo) -> bool {
179 if let Some(tag) = &self.tag
181 && tag != &element.tag_name
182 {
183 return false;
184 }
185
186 if let Some(expected_id) = &self.id {
188 match element.id.as_deref() {
189 Some(actual_id) if actual_id == expected_id => {}
190 _ => return false,
191 }
192 }
193
194 for class in &self.classes {
196 if !element.classes.iter().any(|c| c == class) {
197 return false;
198 }
199 }
200
201 for expected in &self.attributes {
202 let actual = element
203 .attributes
204 .iter()
205 .find(|(name, _)| name.eq_ignore_ascii_case(&expected.name));
206
207 match (&expected.operator, &expected.value, actual) {
208 (AttributeSelectorOperator::Exists, _, Some(_)) => {}
209 (
210 AttributeSelectorOperator::Equals,
211 Some(expected_value),
212 Some((_, actual_value)),
213 ) if actual_value == expected_value => {}
214 (
215 AttributeSelectorOperator::Includes,
216 Some(expected_value),
217 Some((_, actual_value)),
218 ) if actual_value
219 .split_ascii_whitespace()
220 .any(|value| value == expected_value) => {}
221 (
222 AttributeSelectorOperator::DashMatch,
223 Some(expected_value),
224 Some((_, actual_value)),
225 ) if actual_value == expected_value
226 || actual_value
227 .strip_prefix(expected_value)
228 .is_some_and(|rest| rest.starts_with('-')) => {}
229 (
230 AttributeSelectorOperator::Prefix,
231 Some(expected_value),
232 Some((_, actual_value)),
233 ) if actual_value.starts_with(expected_value) => {}
234 (
235 AttributeSelectorOperator::Suffix,
236 Some(expected_value),
237 Some((_, actual_value)),
238 ) if actual_value.ends_with(expected_value) => {}
239 (
240 AttributeSelectorOperator::Substring,
241 Some(expected_value),
242 Some((_, actual_value)),
243 ) if actual_value.contains(expected_value) => {}
244
245 _ => return false,
246 }
247 }
248
249 true
250 }
251
252 fn matches_pseudo_classes(&self, cursor: MatchCursor<'_>, is_root: bool) -> bool {
253 let element = ComplexSelector::element_at(cursor);
254 self.pseudo_classes.iter().all(|pseudo| match pseudo {
255 PseudoClass::Simple(pseudo) => {
256 let has_attribute = |name: &str| {
257 element
258 .attributes
259 .iter()
260 .any(|(attribute, _)| attribute.eq_ignore_ascii_case(name))
261 };
262 let is_form_control = matches!(
263 element.tag_name.as_str(),
264 "button" | "fieldset" | "input" | "optgroup" | "option" | "select" | "textarea"
265 );
266 if pseudo.eq_ignore_ascii_case("root") {
267 is_root
268 } else if pseudo.eq_ignore_ascii_case("link")
269 || pseudo.eq_ignore_ascii_case("any-link")
270 {
271 matches!(element.tag_name.as_str(), "a" | "area") && has_attribute("href")
272 } else if pseudo.eq_ignore_ascii_case("disabled") {
273 is_form_control && has_attribute("disabled")
274 } else if pseudo.eq_ignore_ascii_case("enabled") {
275 is_form_control && !has_attribute("disabled")
276 } else if pseudo.eq_ignore_ascii_case("checked") {
277 (element.tag_name == "input" && has_attribute("checked"))
278 || (element.tag_name == "option" && has_attribute("selected"))
279 } else if pseudo.eq_ignore_ascii_case("required") {
280 is_form_control && has_attribute("required")
281 } else if pseudo.eq_ignore_ascii_case("optional") {
282 is_form_control && !has_attribute("required")
283 } else if pseudo.eq_ignore_ascii_case("first-child") {
284 element.element_index == 1
285 } else if pseudo.eq_ignore_ascii_case("last-child") {
286 element.element_index == element.element_count
287 } else if pseudo.eq_ignore_ascii_case("only-child") {
288 element.element_count == 1
289 } else if pseudo.eq_ignore_ascii_case("first-of-type") {
290 element.type_index == 1
291 } else if pseudo.eq_ignore_ascii_case("last-of-type") {
292 element.type_index == element.type_count
293 } else if pseudo.eq_ignore_ascii_case("only-of-type") {
294 element.type_count == 1
295 } else {
296 false
297 }
298 }
299 PseudoClass::SelectorList { name, selectors } => {
300 if selectors.is_empty() {
301 return false;
302 }
303 let any_matches = selectors
304 .iter()
305 .any(|selector| selector.matches_from(cursor, 0));
306 match name.as_str() {
307 "is" | "where" => any_matches,
308 "not" => !any_matches,
309 _ => false,
310 }
311 }
312 PseudoClass::Nth { name, a, b } => {
313 let index = match name.as_str() {
314 "nth-child" => element.element_index,
315 "nth-last-child" => element
316 .element_count
317 .saturating_add(1)
318 .saturating_sub(element.element_index),
319 "nth-of-type" => element.type_index,
320 "nth-last-of-type" => element
321 .type_count
322 .saturating_add(1)
323 .saturating_sub(element.type_index),
324 _ => return false,
325 };
326 matches_an_plus_b(index, *a, *b)
327 }
328 })
329 }
330
331 fn matches_at(&self, cursor: MatchCursor<'_>) -> bool {
332 let element = ComplexSelector::element_at(cursor);
333 let is_root = cursor.sibling_link.is_none() && cursor.link.next.is_none();
334 if !self.matches_base(element) || !self.matches_pseudo_classes(cursor, is_root) {
335 return false;
336 }
337 if let Some(_pseudo) = &self.pseudo_element {
338 return false;
340 }
341
342 true
343 }
344}
345
346impl ComplexSelector {
347 pub fn matches(&self, chain: &ElementChain) -> bool {
348 if self.parts.is_empty() {
349 return false;
350 }
351 let Some(link) = chain.head.as_deref() else {
352 return false;
353 };
354 self.matches_from(
355 MatchCursor {
356 link,
357 sibling_link: None,
358 },
359 0,
360 )
361 }
362
363 fn element_at(cursor: MatchCursor<'_>) -> &ElementInfo {
364 match cursor.sibling_link {
365 Some(link) => &link.info,
366 None => &cursor.link.info,
367 }
368 }
369
370 fn previous_sibling_cursor(cursor: MatchCursor<'_>) -> Option<MatchCursor<'_>> {
371 let farther = match cursor.sibling_link {
372 Some(link) => link.next.as_deref(),
373 None => cursor.link.info.previous_siblings.head.as_deref(),
374 };
375 farther.map(|link| MatchCursor {
376 link: cursor.link,
377 sibling_link: Some(link),
378 })
379 }
380
381 fn matches_from(&self, cursor: MatchCursor<'_>, selector_index: usize) -> bool {
382 let part = &self.parts[selector_index];
383
384 if !part.selector.matches_at(cursor) {
385 return false;
386 }
387
388 if selector_index + 1 == self.parts.len() {
390 return true;
391 }
392
393 match part.combinator {
394 Some(Combinator::Descendant) => {
395 let next_selector = &self.parts[selector_index + 1].selector;
396 let Some(ancestors) = cursor.link.next.as_deref() else {
397 return false;
398 };
399 if !ancestors.summary().could_match(next_selector) {
401 return false;
402 }
403 let mut ancestor = Some(ancestors);
404 while let Some(link) = ancestor {
405 if self.matches_from(
406 MatchCursor {
407 link,
408 sibling_link: None,
409 },
410 selector_index + 1,
411 ) {
412 return true;
413 }
414 ancestor = link.next.as_deref();
415 }
416 false
417 }
418 Some(Combinator::Child) => cursor.link.next.as_deref().is_some_and(|parent| {
419 self.matches_from(
420 MatchCursor {
421 link: parent,
422 sibling_link: None,
423 },
424 selector_index + 1,
425 )
426 }),
427 Some(Combinator::NextSibling) => Self::previous_sibling_cursor(cursor)
428 .is_some_and(|previous| self.matches_from(previous, selector_index + 1)),
429 Some(Combinator::SubsequentSibling) => {
430 let next_selector = &self.parts[selector_index + 1].selector;
431 let remaining = match cursor.sibling_link {
432 Some(link) => link.next.as_deref(),
433 None => cursor.link.info.previous_siblings.head.as_deref(),
434 };
435 if !remaining.is_some_and(|siblings| siblings.summary().could_match(next_selector))
437 {
438 return false;
439 }
440 let mut previous = Self::previous_sibling_cursor(cursor);
441 while let Some(candidate) = previous {
442 if self.matches_from(candidate, selector_index + 1) {
443 return true;
444 }
445 previous = Self::previous_sibling_cursor(candidate);
446 }
447 false
448 }
449 None => false,
450 }
451 }
452
453 pub fn specificity(&self) -> (u32, u32, u32) {
454 let mut a = 0; let mut b = 0; let mut c = 0; for part in &self.parts {
459 let sel = &part.selector;
460
461 if sel.id.is_some() {
462 a += 1;
463 }
464 b += (sel.classes.len() + sel.attributes.len()) as u32;
465 for pseudo in &sel.pseudo_classes {
466 match pseudo {
467 PseudoClass::Simple(_) | PseudoClass::Nth { .. } => b += 1,
468 PseudoClass::SelectorList { name, selectors } if name == "where" => {}
469 PseudoClass::SelectorList { selectors, .. } => {
470 let nested = selectors
471 .iter()
472 .map(ComplexSelector::specificity)
473 .max()
474 .unwrap_or_default();
475 a += nested.0;
476 b += nested.1;
477 c += nested.2;
478 }
479 }
480 }
481 if sel.tag.is_some() {
482 c += 1;
483 }
484 c += u32::from(sel.pseudo_element.is_some());
485 }
486
487 (a, b, c)
488 }
489}
490
491#[cfg(test)]
492mod tests {
493 use super::*;
494 use crate::engine::css::parser::{
495 AttributeSelector, AttributeSelectorOperator, Parser, SelectorPart,
496 };
497
498 fn input_selector(value: Option<&str>) -> ComplexSelector {
499 ComplexSelector {
500 parts: vec![SelectorPart {
501 selector: Selector {
502 is_nesting: false,
503 tag: Some("input".into()),
504 id: None,
505 classes: Vec::new(),
506 attributes: vec![AttributeSelector {
507 name: "type".into(),
508 operator: match value {
509 Some(_) => AttributeSelectorOperator::Includes,
510 None => AttributeSelectorOperator::Exists,
511 },
512 value: value.map(Into::into),
513 }],
514 pseudo_classes: Vec::new(),
515 pseudo_element: None,
516 },
517 combinator: None,
518 }],
519 }
520 }
521
522 fn input(attributes: &[(&str, &str)]) -> ElementInfo {
523 ElementInfo {
524 tag_name: "input".into(),
525 id: None,
526 classes: Vec::new(),
527 attributes: attributes
528 .iter()
529 .map(|(name, value)| ((*name).into(), (*value).into()))
530 .collect(),
531 ..ElementInfo::default()
532 }
533 }
534
535 fn chain(elements: impl IntoIterator<Item = ElementInfo>) -> ElementChain {
536 ElementChain::from_vec(elements.into_iter().collect())
537 }
538
539 #[test]
540 fn exact_attribute_selector_requires_matching_value() {
541 let selector = input_selector(Some("hidden"));
542
543 assert!(selector.matches(&chain([input(&[("type", "hidden")])])));
544 assert!(!selector.matches(&chain([input(&[])])));
545 assert!(!selector.matches(&chain([input(&[("type", "text")])])));
546 }
547
548 #[test]
549 fn presence_attribute_selector_requires_attribute() {
550 let selector = input_selector(None);
551
552 assert!(selector.matches(&chain([input(&[("type", "text")])])));
553 assert!(!selector.matches(&chain([input(&[])])));
554 }
555
556 #[test]
557 fn child_combinator_requires_direct_parent() {
558 let stylesheet = Parser::new("main > p { color: red; }").parse().unwrap();
559 let selector = match stylesheet.children().first().unwrap().node() {
560 crate::engine::css::parser::CssNodeType::Rule { selectors } => &selectors[0],
561 _ => panic!("expected CSS rule"),
562 };
563 let paragraph = ElementInfo {
564 tag_name: "p".into(),
565 id: None,
566 classes: Vec::new(),
567 attributes: Vec::new(),
568 ..ElementInfo::default()
569 };
570 let section = ElementInfo {
571 tag_name: "section".into(),
572 id: None,
573 classes: Vec::new(),
574 attributes: Vec::new(),
575 ..ElementInfo::default()
576 };
577 let main = ElementInfo {
578 tag_name: "main".into(),
579 id: None,
580 classes: Vec::new(),
581 attributes: Vec::new(),
582 ..ElementInfo::default()
583 };
584
585 assert!(selector.matches(&chain([paragraph.clone(), main.clone()])));
586 assert!(!selector.matches(&chain([paragraph, section, main])));
587 }
588
589 fn parse_selector(source: &str) -> ComplexSelector {
590 let stylesheet = Parser::new(&format!("{source} {{ color: red; }}"))
591 .parse()
592 .unwrap();
593 match stylesheet.children().first().unwrap().node() {
594 crate::engine::css::parser::CssNodeType::Rule { selectors } => selectors[0].clone(),
595 _ => panic!("expected CSS rule"),
596 }
597 }
598
599 #[test]
600 fn root_pseudo_class_only_matches_the_root_element() {
601 let selector = parse_selector(":root");
602 let html = ElementInfo {
603 tag_name: "html".into(),
604 id: None,
605 classes: Vec::new(),
606 attributes: Vec::new(),
607 ..ElementInfo::default()
608 };
609 let body = ElementInfo {
610 tag_name: "body".into(),
611 id: None,
612 classes: Vec::new(),
613 attributes: Vec::new(),
614 ..ElementInfo::default()
615 };
616
617 assert!(selector.matches(&chain([html.clone()])));
618 assert!(!selector.matches(&chain([body, html])));
619 }
620
621 #[test]
622 fn link_pseudo_class_requires_an_href() {
623 let selector = parse_selector("a:link");
624
625 assert!(selector.matches(&chain([ElementInfo {
626 tag_name: "a".into(),
627 id: None,
628 classes: Vec::new(),
629 attributes: vec![("href".into(), "/next".into())],
630 ..ElementInfo::default()
631 }])));
632 assert!(!selector.matches(&chain([ElementInfo {
633 tag_name: "a".into(),
634 id: None,
635 classes: Vec::new(),
636 attributes: Vec::new(),
637 ..ElementInfo::default()
638 }])));
639 }
640
641 fn element(
642 tag_name: &str,
643 classes: &[&str],
644 element_index: usize,
645 element_count: usize,
646 type_index: usize,
647 type_count: usize,
648 ) -> ElementInfo {
649 ElementInfo {
650 tag_name: tag_name.into(),
651 classes: classes.iter().map(|class| (*class).into()).collect(),
652 element_index,
653 element_count,
654 type_index,
655 type_count,
656 ..ElementInfo::default()
657 }
658 }
659
660 #[test]
661 fn sibling_combinators_match_preceding_elements() {
662 let heading = element("h2", &[], 1, 3, 1, 1);
663 let aside = element("aside", &[], 2, 3, 1, 1);
664 let mut paragraph = element("p", &[], 3, 3, 1, 1);
665 paragraph.previous_siblings = ElementChain::from_document_order([heading, aside]);
666
667 assert!(parse_selector("aside + p").matches(&chain([paragraph.clone()])));
668 assert!(!parse_selector("h2 + p").matches(&chain([paragraph.clone()])));
669 assert!(parse_selector("h2 ~ p").matches(&chain([paragraph.clone()])));
670 assert!(!parse_selector("nav ~ p").matches(&chain([paragraph])));
671 }
672
673 #[test]
674 fn descendant_combinator_matches_deep_ancestors() {
675 let span = element("span", &[], 1, 1, 1, 1);
676 let section = element("section", &[], 1, 1, 1, 1);
677 let card_body = element("body", &["card"], 1, 1, 1, 1);
678 let html = element("html", &[], 1, 1, 1, 1);
679
680 assert!(parse_selector(".card span").matches(&chain([
681 span.clone(),
682 section.clone(),
683 card_body.clone(),
684 html.clone()
685 ])));
686 assert!(parse_selector("html span").matches(&chain([span, section, card_body, html])));
687 }
688
689 #[test]
690 fn descendant_combinator_rejects_when_no_ancestor_qualifies() {
691 let span = element("span", &[], 1, 1, 1, 1);
692 let div = element("div", &[], 1, 1, 1, 1);
693 let main = ElementInfo {
694 tag_name: "main".into(),
695 id: Some("app".into()),
696 classes: vec!["root".into()],
697 attributes: Vec::new(),
698 ..ElementInfo::default()
699 };
700
701 assert!(!parse_selector(".card span").matches(&chain([
703 span.clone(),
704 div.clone(),
705 main.clone()
706 ])));
707 assert!(!parse_selector("#missing span").matches(&chain([
708 span.clone(),
709 div.clone(),
710 main.clone()
711 ])));
712 assert!(!parse_selector("nav span").matches(&chain([
713 span.clone(),
714 div.clone(),
715 main.clone()
716 ])));
717
718 let mut hidden_main = main.clone();
721 hidden_main.attributes = vec![("hidden".into(), "true".into())];
722 assert!(parse_selector("[hidden] span").matches(&chain([
723 span.clone(),
724 div.clone(),
725 hidden_main
726 ])));
727 assert!(parse_selector("* span").matches(&chain([span, div, main])));
728 }
729
730 #[test]
731 fn subsequent_sibling_rejects_when_no_preceding_element_qualifies() {
732 let heading = element("h2", &[], 1, 2, 1, 1);
733 let mut paragraph = element("p", &[], 2, 2, 1, 1);
734 paragraph.previous_siblings = ElementChain::from_document_order([heading]);
735
736 assert!(!parse_selector(".x ~ p").matches(&chain([paragraph.clone()])));
737 assert!(!parse_selector("aside ~ p").matches(&chain([paragraph])));
738
739 let aside = element("aside", &["x"], 1, 2, 1, 1);
740 let heading = element("h2", &[], 2, 2, 1, 1);
741 let mut paragraph = element("p", &[], 3, 3, 1, 1);
742 paragraph.previous_siblings = ElementChain::from_document_order([aside, heading]);
743 assert!(parse_selector(".x ~ p").matches(&chain([paragraph])));
744 }
745
746 #[test]
747 fn structural_pseudo_classes_use_element_and_type_positions() {
748 let second_paragraph = element("p", &[], 3, 5, 2, 3);
749
750 assert!(parse_selector("p:nth-child(2n+1)").matches(&chain([second_paragraph.clone()])));
751 assert!(parse_selector("p:nth-of-type(even)").matches(&chain([second_paragraph.clone()])));
752 assert!(parse_selector("p:nth-last-child(3)").matches(&chain([second_paragraph.clone()])));
753 assert!(
754 parse_selector("p:nth-last-of-type(2)").matches(&chain([second_paragraph.clone()]))
755 );
756 assert!(parse_selector("p:nth-child(-n+3)").matches(&chain([second_paragraph.clone()])));
757 assert!(!parse_selector("p:first-child").matches(&chain([second_paragraph.clone()])));
758 assert!(!parse_selector("p:last-of-type").matches(&chain([second_paragraph])));
759 }
760
761 #[test]
762 fn selector_list_pseudo_classes_and_multiple_pseudos_match() {
763 let visible_first = element("li", &["item"], 1, 3, 1, 3);
764 let hidden_first = element("li", &["item", "hidden"], 1, 3, 1, 3);
765 let selector = parse_selector("li.item:first-child:not(.hidden)");
766
767 assert!(selector.matches(&chain([visible_first.clone()])));
768 assert!(!selector.matches(&chain([hidden_first])));
769 assert!(parse_selector(":is(article, li.item)").matches(&chain([visible_first.clone()])));
770 assert!(parse_selector(":where(.item, .card)").matches(&chain([visible_first])));
771 }
772
773 #[test]
774 fn selector_list_pseudo_classes_follow_specificity_rules() {
775 assert_eq!(
776 parse_selector(":where(#main, .item)").specificity(),
777 (0, 0, 0)
778 );
779 assert_eq!(parse_selector(":is(#main, .item)").specificity(), (1, 0, 0));
780 assert_eq!(
781 parse_selector("li:not(.hidden):first-child").specificity(),
782 (0, 2, 1)
783 );
784 }
785}