1 /* This Source Code Form is subject to the terms of the Mozilla Public
2 * License, v. 2.0. If a copy of the MPL was not distributed with this
3 * file, You can obtain one at https://mozilla.org/MPL/2.0/. */
4
5 use crate::attr::{AttrSelectorOperation, NamespaceConstraint, ParsedAttrSelectorOperation};
6 use crate::bloom::{BloomFilter, BLOOM_HASH_MASK};
7 use crate::nth_index_cache::NthIndexCacheInner;
8 use crate::parser::{AncestorHashes, Combinator, Component, LocalName};
9 use crate::parser::{NonTSPseudoClass, Selector, SelectorImpl, SelectorIter, SelectorList};
10 use crate::tree::Element;
11 use smallvec::SmallVec;
12 use std::borrow::Borrow;
13 use std::iter;
14
15 pub use crate::context::*;
16
17 // The bloom filter for descendant CSS selectors will have a <1% false
18 // positive rate until it has this many selectors in it, then it will
19 // rapidly increase.
20 pub static RECOMMENDED_SELECTOR_BLOOM_FILTER_SIZE: usize = 4096;
21
22 bitflags! {
23 /// Set of flags that are set on either the element or its parent (depending
24 /// on the flag) if the element could potentially match a selector.
25 pub struct ElementSelectorFlags: usize {
26 /// When a child is added or removed from the parent, all the children
27 /// must be restyled, because they may match :nth-last-child,
28 /// :last-of-type, :nth-last-of-type, or :only-of-type.
29 const HAS_SLOW_SELECTOR = 1 << 0;
30
31 /// When a child is added or removed from the parent, any later
32 /// children must be restyled, because they may match :nth-child,
33 /// :first-of-type, or :nth-of-type.
34 const HAS_SLOW_SELECTOR_LATER_SIBLINGS = 1 << 1;
35
36 /// When a child is added or removed from the parent, the first and
37 /// last children must be restyled, because they may match :first-child,
38 /// :last-child, or :only-child.
39 const HAS_EDGE_CHILD_SELECTOR = 1 << 2;
40
41 /// The element has an empty selector, so when a child is appended we
42 /// might need to restyle the parent completely.
43 const HAS_EMPTY_SELECTOR = 1 << 3;
44 }
45 }
46
47 impl ElementSelectorFlags {
48 /// Returns the subset of flags that apply to the element.
for_self(self) -> ElementSelectorFlags49 pub fn for_self(self) -> ElementSelectorFlags {
50 self & (ElementSelectorFlags::HAS_EMPTY_SELECTOR)
51 }
52
53 /// Returns the subset of flags that apply to the parent.
for_parent(self) -> ElementSelectorFlags54 pub fn for_parent(self) -> ElementSelectorFlags {
55 self & (ElementSelectorFlags::HAS_SLOW_SELECTOR |
56 ElementSelectorFlags::HAS_SLOW_SELECTOR_LATER_SIBLINGS |
57 ElementSelectorFlags::HAS_EDGE_CHILD_SELECTOR)
58 }
59 }
60
61 /// Holds per-compound-selector data.
62 struct LocalMatchingContext<'a, 'b: 'a, Impl: SelectorImpl> {
63 shared: &'a mut MatchingContext<'b, Impl>,
64 matches_hover_and_active_quirk: MatchesHoverAndActiveQuirk,
65 }
66
67 #[inline(always)]
matches_selector_list<E>( selector_list: &SelectorList<E::Impl>, element: &E, context: &mut MatchingContext<E::Impl>, ) -> bool where E: Element,68 pub fn matches_selector_list<E>(
69 selector_list: &SelectorList<E::Impl>,
70 element: &E,
71 context: &mut MatchingContext<E::Impl>,
72 ) -> bool
73 where
74 E: Element,
75 {
76 // This is pretty much any(..) but manually inlined because the compiler
77 // refuses to do so from querySelector / querySelectorAll.
78 for selector in &selector_list.0 {
79 let matches = matches_selector(selector, 0, None, element, context, &mut |_, _| {});
80
81 if matches {
82 return true;
83 }
84 }
85
86 false
87 }
88
89 #[inline(always)]
may_match(hashes: &AncestorHashes, bf: &BloomFilter) -> bool90 fn may_match(hashes: &AncestorHashes, bf: &BloomFilter) -> bool {
91 // Check the first three hashes. Note that we can check for zero before
92 // masking off the high bits, since if any of the first three hashes is
93 // zero the fourth will be as well. We also take care to avoid the
94 // special-case complexity of the fourth hash until we actually reach it,
95 // because we usually don't.
96 //
97 // To be clear: this is all extremely hot.
98 for i in 0..3 {
99 let packed = hashes.packed_hashes[i];
100 if packed == 0 {
101 // No more hashes left - unable to fast-reject.
102 return true;
103 }
104
105 if !bf.might_contain_hash(packed & BLOOM_HASH_MASK) {
106 // Hooray! We fast-rejected on this hash.
107 return false;
108 }
109 }
110
111 // Now do the slighty-more-complex work of synthesizing the fourth hash,
112 // and check it against the filter if it exists.
113 let fourth = hashes.fourth_hash();
114 fourth == 0 || bf.might_contain_hash(fourth)
115 }
116
117 /// A result of selector matching, includes 3 failure types,
118 ///
119 /// NotMatchedAndRestartFromClosestLaterSibling
120 /// NotMatchedAndRestartFromClosestDescendant
121 /// NotMatchedGlobally
122 ///
123 /// When NotMatchedGlobally appears, stop selector matching completely since
124 /// the succeeding selectors never matches.
125 /// It is raised when
126 /// Child combinator cannot find the candidate element.
127 /// Descendant combinator cannot find the candidate element.
128 ///
129 /// When NotMatchedAndRestartFromClosestDescendant appears, the selector
130 /// matching does backtracking and restarts from the closest Descendant
131 /// combinator.
132 /// It is raised when
133 /// NextSibling combinator cannot find the candidate element.
134 /// LaterSibling combinator cannot find the candidate element.
135 /// Child combinator doesn't match on the found element.
136 ///
137 /// When NotMatchedAndRestartFromClosestLaterSibling appears, the selector
138 /// matching does backtracking and restarts from the closest LaterSibling
139 /// combinator.
140 /// It is raised when
141 /// NextSibling combinator doesn't match on the found element.
142 ///
143 /// For example, when the selector "d1 d2 a" is provided and we cannot *find*
144 /// an appropriate ancestor element for "d1", this selector matching raises
145 /// NotMatchedGlobally since even if "d2" is moved to more upper element, the
146 /// candidates for "d1" becomes less than before and d1 .
147 ///
148 /// The next example is siblings. When the selector "b1 + b2 ~ d1 a" is
149 /// provided and we cannot *find* an appropriate brother element for b1,
150 /// the selector matching raises NotMatchedAndRestartFromClosestDescendant.
151 /// The selectors ("b1 + b2 ~") doesn't match and matching restart from "d1".
152 ///
153 /// The additional example is child and sibling. When the selector
154 /// "b1 + c1 > b2 ~ d1 a" is provided and the selector "b1" doesn't match on
155 /// the element, this "b1" raises NotMatchedAndRestartFromClosestLaterSibling.
156 /// However since the selector "c1" raises
157 /// NotMatchedAndRestartFromClosestDescendant. So the selector
158 /// "b1 + c1 > b2 ~ " doesn't match and restart matching from "d1".
159 #[derive(Clone, Copy, Eq, PartialEq)]
160 enum SelectorMatchingResult {
161 Matched,
162 NotMatchedAndRestartFromClosestLaterSibling,
163 NotMatchedAndRestartFromClosestDescendant,
164 NotMatchedGlobally,
165 }
166
167 /// Whether the :hover and :active quirk applies.
168 ///
169 /// https://quirks.spec.whatwg.org/#the-active-and-hover-quirk
170 #[derive(Clone, Copy, Debug, PartialEq)]
171 enum MatchesHoverAndActiveQuirk {
172 Yes,
173 No,
174 }
175
176 /// Matches a selector, fast-rejecting against a bloom filter.
177 ///
178 /// We accept an offset to allow consumers to represent and match against
179 /// partial selectors (indexed from the right). We use this API design, rather
180 /// than having the callers pass a SelectorIter, because creating a SelectorIter
181 /// requires dereferencing the selector to get the length, which adds an
182 /// unncessary cache miss for cases when we can fast-reject with AncestorHashes
183 /// (which the caller can store inline with the selector pointer).
184 #[inline(always)]
matches_selector<E, F>( selector: &Selector<E::Impl>, offset: usize, hashes: Option<&AncestorHashes>, element: &E, context: &mut MatchingContext<E::Impl>, flags_setter: &mut F, ) -> bool where E: Element, F: FnMut(&E, ElementSelectorFlags),185 pub fn matches_selector<E, F>(
186 selector: &Selector<E::Impl>,
187 offset: usize,
188 hashes: Option<&AncestorHashes>,
189 element: &E,
190 context: &mut MatchingContext<E::Impl>,
191 flags_setter: &mut F,
192 ) -> bool
193 where
194 E: Element,
195 F: FnMut(&E, ElementSelectorFlags),
196 {
197 // Use the bloom filter to fast-reject.
198 if let Some(hashes) = hashes {
199 if let Some(filter) = context.bloom_filter {
200 if !may_match(hashes, filter) {
201 return false;
202 }
203 }
204 }
205
206 matches_complex_selector(selector.iter_from(offset), element, context, flags_setter)
207 }
208
209 /// Whether a compound selector matched, and whether it was the rightmost
210 /// selector inside the complex selector.
211 pub enum CompoundSelectorMatchingResult {
212 /// The selector was fully matched.
213 FullyMatched,
214 /// The compound selector matched, and the next combinator offset is
215 /// `next_combinator_offset`.
216 Matched { next_combinator_offset: usize },
217 /// The selector didn't match.
218 NotMatched,
219 }
220
221 /// Matches a compound selector belonging to `selector`, starting at offset
222 /// `from_offset`, matching left to right.
223 ///
224 /// Requires that `from_offset` points to a `Combinator`.
225 ///
226 /// NOTE(emilio): This doesn't allow to match in the leftmost sequence of the
227 /// complex selector, but it happens to be the case we don't need it.
matches_compound_selector_from<E>( selector: &Selector<E::Impl>, mut from_offset: usize, context: &mut MatchingContext<E::Impl>, element: &E, ) -> CompoundSelectorMatchingResult where E: Element,228 pub fn matches_compound_selector_from<E>(
229 selector: &Selector<E::Impl>,
230 mut from_offset: usize,
231 context: &mut MatchingContext<E::Impl>,
232 element: &E,
233 ) -> CompoundSelectorMatchingResult
234 where
235 E: Element,
236 {
237 if cfg!(debug_assertions) && from_offset != 0 {
238 selector.combinator_at_parse_order(from_offset - 1); // This asserts.
239 }
240
241 let mut local_context = LocalMatchingContext {
242 shared: context,
243 matches_hover_and_active_quirk: MatchesHoverAndActiveQuirk::No,
244 };
245
246 // Find the end of the selector or the next combinator, then match
247 // backwards, so that we match in the same order as
248 // matches_complex_selector, which is usually faster.
249 let start_offset = from_offset;
250 for component in selector.iter_raw_parse_order_from(from_offset) {
251 if matches!(*component, Component::Combinator(..)) {
252 debug_assert_ne!(from_offset, 0, "Selector started with a combinator?");
253 break;
254 }
255
256 from_offset += 1;
257 }
258
259 debug_assert!(from_offset >= 1);
260 debug_assert!(from_offset <= selector.len());
261
262 let iter = selector.iter_from(selector.len() - from_offset);
263 debug_assert!(
264 iter.clone().next().is_some() ||
265 (from_offset != selector.len() &&
266 matches!(
267 selector.combinator_at_parse_order(from_offset),
268 Combinator::SlotAssignment | Combinator::PseudoElement
269 )),
270 "Got the math wrong: {:?} | {:?} | {} {}",
271 selector,
272 selector.iter_raw_match_order().as_slice(),
273 from_offset,
274 start_offset
275 );
276
277 for component in iter {
278 if !matches_simple_selector(component, element, &mut local_context, &mut |_, _| {}) {
279 return CompoundSelectorMatchingResult::NotMatched;
280 }
281 }
282
283 if from_offset != selector.len() {
284 return CompoundSelectorMatchingResult::Matched {
285 next_combinator_offset: from_offset,
286 };
287 }
288
289 CompoundSelectorMatchingResult::FullyMatched
290 }
291
292 /// Matches a complex selector.
293 #[inline(always)]
matches_complex_selector<E, F>( mut iter: SelectorIter<E::Impl>, element: &E, context: &mut MatchingContext<E::Impl>, flags_setter: &mut F, ) -> bool where E: Element, F: FnMut(&E, ElementSelectorFlags),294 pub fn matches_complex_selector<E, F>(
295 mut iter: SelectorIter<E::Impl>,
296 element: &E,
297 context: &mut MatchingContext<E::Impl>,
298 flags_setter: &mut F,
299 ) -> bool
300 where
301 E: Element,
302 F: FnMut(&E, ElementSelectorFlags),
303 {
304 // If this is the special pseudo-element mode, consume the ::pseudo-element
305 // before proceeding, since the caller has already handled that part.
306 if context.matching_mode() == MatchingMode::ForStatelessPseudoElement && !context.is_nested() {
307 // Consume the pseudo.
308 match *iter.next().unwrap() {
309 Component::PseudoElement(ref pseudo) => {
310 if let Some(ref f) = context.pseudo_element_matching_fn {
311 if !f(pseudo) {
312 return false;
313 }
314 }
315 },
316 _ => {
317 debug_assert!(
318 false,
319 "Used MatchingMode::ForStatelessPseudoElement \
320 in a non-pseudo selector"
321 );
322 },
323 }
324
325 // The only other parser-allowed Component in this sequence is a state
326 // class. We just don't match in that case.
327 if let Some(s) = iter.next() {
328 debug_assert!(
329 matches!(*s, Component::NonTSPseudoClass(..)),
330 "Someone messed up pseudo-element parsing"
331 );
332 return false;
333 }
334
335 // Advance to the non-pseudo-element part of the selector.
336 let next_sequence = iter.next_sequence().unwrap();
337 debug_assert_eq!(next_sequence, Combinator::PseudoElement);
338 }
339
340 let result =
341 matches_complex_selector_internal(iter, element, context, flags_setter, Rightmost::Yes);
342
343 match result {
344 SelectorMatchingResult::Matched => true,
345 _ => false,
346 }
347 }
348
349 #[inline]
matches_hover_and_active_quirk<Impl: SelectorImpl>( selector_iter: &SelectorIter<Impl>, context: &MatchingContext<Impl>, rightmost: Rightmost, ) -> MatchesHoverAndActiveQuirk350 fn matches_hover_and_active_quirk<Impl: SelectorImpl>(
351 selector_iter: &SelectorIter<Impl>,
352 context: &MatchingContext<Impl>,
353 rightmost: Rightmost,
354 ) -> MatchesHoverAndActiveQuirk {
355 if context.quirks_mode() != QuirksMode::Quirks {
356 return MatchesHoverAndActiveQuirk::No;
357 }
358
359 if context.is_nested() {
360 return MatchesHoverAndActiveQuirk::No;
361 }
362
363 // This compound selector had a pseudo-element to the right that we
364 // intentionally skipped.
365 if rightmost == Rightmost::Yes &&
366 context.matching_mode() == MatchingMode::ForStatelessPseudoElement
367 {
368 return MatchesHoverAndActiveQuirk::No;
369 }
370
371 let all_match = selector_iter.clone().all(|simple| match *simple {
372 Component::LocalName(_) |
373 Component::AttributeInNoNamespaceExists { .. } |
374 Component::AttributeInNoNamespace { .. } |
375 Component::AttributeOther(_) |
376 Component::ID(_) |
377 Component::Class(_) |
378 Component::PseudoElement(_) |
379 Component::Negation(_) |
380 Component::FirstChild |
381 Component::LastChild |
382 Component::OnlyChild |
383 Component::Empty |
384 Component::NthChild(_, _) |
385 Component::NthLastChild(_, _) |
386 Component::NthOfType(_, _) |
387 Component::NthLastOfType(_, _) |
388 Component::FirstOfType |
389 Component::LastOfType |
390 Component::OnlyOfType => false,
391 Component::NonTSPseudoClass(ref pseudo_class) => pseudo_class.is_active_or_hover(),
392 _ => true,
393 });
394
395 if all_match {
396 MatchesHoverAndActiveQuirk::Yes
397 } else {
398 MatchesHoverAndActiveQuirk::No
399 }
400 }
401
402 #[derive(Clone, Copy, PartialEq)]
403 enum Rightmost {
404 Yes,
405 No,
406 }
407
408 #[inline(always)]
next_element_for_combinator<E>( element: &E, combinator: Combinator, selector: &SelectorIter<E::Impl>, context: &MatchingContext<E::Impl>, ) -> Option<E> where E: Element,409 fn next_element_for_combinator<E>(
410 element: &E,
411 combinator: Combinator,
412 selector: &SelectorIter<E::Impl>,
413 context: &MatchingContext<E::Impl>,
414 ) -> Option<E>
415 where
416 E: Element,
417 {
418 match combinator {
419 Combinator::NextSibling | Combinator::LaterSibling => element.prev_sibling_element(),
420 Combinator::Child | Combinator::Descendant => {
421 match element.parent_element() {
422 Some(e) => return Some(e),
423 None => {},
424 }
425
426 if !element.parent_node_is_shadow_root() {
427 return None;
428 }
429
430 // https://drafts.csswg.org/css-scoping/#host-element-in-tree:
431 //
432 // For the purpose of Selectors, a shadow host also appears in
433 // its shadow tree, with the contents of the shadow tree treated
434 // as its children. (In other words, the shadow host is treated as
435 // replacing the shadow root node.)
436 //
437 // and also:
438 //
439 // When considered within its own shadow trees, the shadow host is
440 // featureless. Only the :host, :host(), and :host-context()
441 // pseudo-classes are allowed to match it.
442 //
443 // Since we know that the parent is a shadow root, we necessarily
444 // are in a shadow tree of the host, and the next selector will only
445 // match if the selector is a featureless :host selector.
446 if !selector.clone().is_featureless_host_selector() {
447 return None;
448 }
449
450 element.containing_shadow_host()
451 },
452 Combinator::Part => element.containing_shadow_host(),
453 Combinator::SlotAssignment => {
454 debug_assert!(element
455 .assigned_slot()
456 .map_or(true, |s| s.is_html_slot_element()));
457 let scope = context.current_host?;
458 let mut current_slot = element.assigned_slot()?;
459 while current_slot.containing_shadow_host().unwrap().opaque() != scope {
460 current_slot = current_slot.assigned_slot()?;
461 }
462 Some(current_slot)
463 },
464 Combinator::PseudoElement => element.pseudo_element_originating_element(),
465 }
466 }
467
matches_complex_selector_internal<E, F>( mut selector_iter: SelectorIter<E::Impl>, element: &E, context: &mut MatchingContext<E::Impl>, flags_setter: &mut F, rightmost: Rightmost, ) -> SelectorMatchingResult where E: Element, F: FnMut(&E, ElementSelectorFlags),468 fn matches_complex_selector_internal<E, F>(
469 mut selector_iter: SelectorIter<E::Impl>,
470 element: &E,
471 context: &mut MatchingContext<E::Impl>,
472 flags_setter: &mut F,
473 rightmost: Rightmost,
474 ) -> SelectorMatchingResult
475 where
476 E: Element,
477 F: FnMut(&E, ElementSelectorFlags),
478 {
479 debug!(
480 "Matching complex selector {:?} for {:?}",
481 selector_iter, element
482 );
483
484 let matches_compound_selector = matches_compound_selector(
485 &mut selector_iter,
486 element,
487 context,
488 flags_setter,
489 rightmost,
490 );
491
492 let combinator = selector_iter.next_sequence();
493 if combinator.map_or(false, |c| c.is_sibling()) {
494 flags_setter(
495 element,
496 ElementSelectorFlags::HAS_SLOW_SELECTOR_LATER_SIBLINGS,
497 );
498 }
499
500 if !matches_compound_selector {
501 return SelectorMatchingResult::NotMatchedAndRestartFromClosestLaterSibling;
502 }
503
504 let combinator = match combinator {
505 None => return SelectorMatchingResult::Matched,
506 Some(c) => c,
507 };
508
509 let candidate_not_found = match combinator {
510 Combinator::NextSibling | Combinator::LaterSibling => {
511 SelectorMatchingResult::NotMatchedAndRestartFromClosestDescendant
512 },
513 Combinator::Child |
514 Combinator::Descendant |
515 Combinator::SlotAssignment |
516 Combinator::Part |
517 Combinator::PseudoElement => SelectorMatchingResult::NotMatchedGlobally,
518 };
519
520 let mut next_element =
521 next_element_for_combinator(element, combinator, &selector_iter, &context);
522
523 // Stop matching :visited as soon as we find a link, or a combinator for
524 // something that isn't an ancestor.
525 let mut visited_handling = if element.is_link() || combinator.is_sibling() {
526 VisitedHandlingMode::AllLinksUnvisited
527 } else {
528 context.visited_handling()
529 };
530
531 loop {
532 let element = match next_element {
533 None => return candidate_not_found,
534 Some(next_element) => next_element,
535 };
536
537 let result = context.with_visited_handling_mode(visited_handling, |context| {
538 matches_complex_selector_internal(
539 selector_iter.clone(),
540 &element,
541 context,
542 flags_setter,
543 Rightmost::No,
544 )
545 });
546
547 match (result, combinator) {
548 // Return the status immediately.
549 (SelectorMatchingResult::Matched, _) |
550 (SelectorMatchingResult::NotMatchedGlobally, _) |
551 (_, Combinator::NextSibling) => {
552 return result;
553 },
554
555 // Upgrade the failure status to
556 // NotMatchedAndRestartFromClosestDescendant.
557 (_, Combinator::PseudoElement) | (_, Combinator::Child) => {
558 return SelectorMatchingResult::NotMatchedAndRestartFromClosestDescendant;
559 },
560
561 // If the failure status is
562 // NotMatchedAndRestartFromClosestDescendant and combinator is
563 // Combinator::LaterSibling, give up this Combinator::LaterSibling
564 // matching and restart from the closest descendant combinator.
565 (
566 SelectorMatchingResult::NotMatchedAndRestartFromClosestDescendant,
567 Combinator::LaterSibling,
568 ) => {
569 return result;
570 },
571
572 // The Combinator::Descendant combinator and the status is
573 // NotMatchedAndRestartFromClosestLaterSibling or
574 // NotMatchedAndRestartFromClosestDescendant, or the
575 // Combinator::LaterSibling combinator and the status is
576 // NotMatchedAndRestartFromClosestDescendant, we can continue to
577 // matching on the next candidate element.
578 _ => {},
579 }
580
581 if element.is_link() {
582 visited_handling = VisitedHandlingMode::AllLinksUnvisited;
583 }
584
585 next_element = next_element_for_combinator(&element, combinator, &selector_iter, &context);
586 }
587 }
588
589 #[inline]
matches_local_name<E>(element: &E, local_name: &LocalName<E::Impl>) -> bool where E: Element,590 fn matches_local_name<E>(element: &E, local_name: &LocalName<E::Impl>) -> bool
591 where
592 E: Element,
593 {
594 let name = select_name(
595 element.is_html_element_in_html_document(),
596 &local_name.name,
597 &local_name.lower_name,
598 )
599 .borrow();
600 element.has_local_name(name)
601 }
602
603 /// Determines whether the given element matches the given compound selector.
604 #[inline]
matches_compound_selector<E, F>( selector_iter: &mut SelectorIter<E::Impl>, element: &E, context: &mut MatchingContext<E::Impl>, flags_setter: &mut F, rightmost: Rightmost, ) -> bool where E: Element, F: FnMut(&E, ElementSelectorFlags),605 fn matches_compound_selector<E, F>(
606 selector_iter: &mut SelectorIter<E::Impl>,
607 element: &E,
608 context: &mut MatchingContext<E::Impl>,
609 flags_setter: &mut F,
610 rightmost: Rightmost,
611 ) -> bool
612 where
613 E: Element,
614 F: FnMut(&E, ElementSelectorFlags),
615 {
616 let matches_hover_and_active_quirk =
617 matches_hover_and_active_quirk(&selector_iter, context, rightmost);
618
619 // Handle some common cases first.
620 // We may want to get rid of this at some point if we can make the
621 // generic case fast enough.
622 let mut selector = selector_iter.next();
623 if let Some(&Component::LocalName(ref local_name)) = selector {
624 if !matches_local_name(element, local_name) {
625 return false;
626 }
627 selector = selector_iter.next();
628 }
629 let class_and_id_case_sensitivity = context.classes_and_ids_case_sensitivity();
630 if let Some(&Component::ID(ref id)) = selector {
631 if !element.has_id(id, class_and_id_case_sensitivity) {
632 return false;
633 }
634 selector = selector_iter.next();
635 }
636 while let Some(&Component::Class(ref class)) = selector {
637 if !element.has_class(class, class_and_id_case_sensitivity) {
638 return false;
639 }
640 selector = selector_iter.next();
641 }
642 let selector = match selector {
643 Some(s) => s,
644 None => return true,
645 };
646
647 let mut local_context = LocalMatchingContext {
648 shared: context,
649 matches_hover_and_active_quirk,
650 };
651 iter::once(selector)
652 .chain(selector_iter)
653 .all(|simple| matches_simple_selector(simple, element, &mut local_context, flags_setter))
654 }
655
656 /// Determines whether the given element matches the given single selector.
matches_simple_selector<E, F>( selector: &Component<E::Impl>, element: &E, context: &mut LocalMatchingContext<E::Impl>, flags_setter: &mut F, ) -> bool where E: Element, F: FnMut(&E, ElementSelectorFlags),657 fn matches_simple_selector<E, F>(
658 selector: &Component<E::Impl>,
659 element: &E,
660 context: &mut LocalMatchingContext<E::Impl>,
661 flags_setter: &mut F,
662 ) -> bool
663 where
664 E: Element,
665 F: FnMut(&E, ElementSelectorFlags),
666 {
667 debug_assert!(context.shared.is_nested() || !context.shared.in_negation());
668
669 match *selector {
670 Component::Combinator(_) => unreachable!(),
671 Component::Part(ref parts) => {
672 let mut hosts = SmallVec::<[E; 4]>::new();
673
674 let mut host = match element.containing_shadow_host() {
675 Some(h) => h,
676 None => return false,
677 };
678
679 loop {
680 let outer_host = host.containing_shadow_host();
681 if outer_host.as_ref().map(|h| h.opaque()) == context.shared.current_host {
682 break;
683 }
684 let outer_host = match outer_host {
685 Some(h) => h,
686 None => return false,
687 };
688 // TODO(emilio): if worth it, we could early return if
689 // host doesn't have the exportparts attribute.
690 hosts.push(host);
691 host = outer_host;
692 }
693
694 // Translate the part into the right scope.
695 parts.iter().all(|part| {
696 let mut part = part.clone();
697 for host in hosts.iter().rev() {
698 part = match host.imported_part(&part) {
699 Some(p) => p,
700 None => return false,
701 };
702 }
703 element.is_part(&part)
704 })
705 },
706 Component::Slotted(ref selector) => {
707 // <slots> are never flattened tree slottables.
708 !element.is_html_slot_element() &&
709 context.shared.nest(|context| {
710 matches_complex_selector(selector.iter(), element, context, flags_setter)
711 })
712 },
713 Component::PseudoElement(ref pseudo) => {
714 element.match_pseudo_element(pseudo, context.shared)
715 },
716 Component::LocalName(ref local_name) => matches_local_name(element, local_name),
717 Component::ExplicitUniversalType | Component::ExplicitAnyNamespace => true,
718 Component::Namespace(_, ref url) | Component::DefaultNamespace(ref url) => {
719 element.has_namespace(&url.borrow())
720 },
721 Component::ExplicitNoNamespace => {
722 let ns = crate::parser::namespace_empty_string::<E::Impl>();
723 element.has_namespace(&ns.borrow())
724 },
725 Component::ID(ref id) => {
726 element.has_id(id, context.shared.classes_and_ids_case_sensitivity())
727 },
728 Component::Class(ref class) => {
729 element.has_class(class, context.shared.classes_and_ids_case_sensitivity())
730 },
731 Component::AttributeInNoNamespaceExists {
732 ref local_name,
733 ref local_name_lower,
734 } => {
735 let is_html = element.is_html_element_in_html_document();
736 element.attr_matches(
737 &NamespaceConstraint::Specific(&crate::parser::namespace_empty_string::<E::Impl>()),
738 select_name(is_html, local_name, local_name_lower),
739 &AttrSelectorOperation::Exists,
740 )
741 },
742 Component::AttributeInNoNamespace {
743 ref local_name,
744 ref value,
745 operator,
746 case_sensitivity,
747 never_matches,
748 } => {
749 if never_matches {
750 return false;
751 }
752 let is_html = element.is_html_element_in_html_document();
753 element.attr_matches(
754 &NamespaceConstraint::Specific(&crate::parser::namespace_empty_string::<E::Impl>()),
755 local_name,
756 &AttrSelectorOperation::WithValue {
757 operator: operator,
758 case_sensitivity: case_sensitivity.to_unconditional(is_html),
759 expected_value: value,
760 },
761 )
762 },
763 Component::AttributeOther(ref attr_sel) => {
764 if attr_sel.never_matches {
765 return false;
766 }
767 let is_html = element.is_html_element_in_html_document();
768 let empty_string;
769 let namespace = match attr_sel.namespace() {
770 Some(ns) => ns,
771 None => {
772 empty_string = crate::parser::namespace_empty_string::<E::Impl>();
773 NamespaceConstraint::Specific(&empty_string)
774 },
775 };
776 element.attr_matches(
777 &namespace,
778 select_name(is_html, &attr_sel.local_name, &attr_sel.local_name_lower),
779 &match attr_sel.operation {
780 ParsedAttrSelectorOperation::Exists => AttrSelectorOperation::Exists,
781 ParsedAttrSelectorOperation::WithValue {
782 operator,
783 case_sensitivity,
784 ref expected_value,
785 } => AttrSelectorOperation::WithValue {
786 operator: operator,
787 case_sensitivity: case_sensitivity.to_unconditional(is_html),
788 expected_value: expected_value,
789 },
790 },
791 )
792 },
793 Component::NonTSPseudoClass(ref pc) => {
794 if context.matches_hover_and_active_quirk == MatchesHoverAndActiveQuirk::Yes &&
795 !context.shared.is_nested() &&
796 pc.is_active_or_hover() &&
797 !element.is_link()
798 {
799 return false;
800 }
801
802 element.match_non_ts_pseudo_class(pc, &mut context.shared, flags_setter)
803 },
804 Component::FirstChild => matches_first_child(element, flags_setter),
805 Component::LastChild => matches_last_child(element, flags_setter),
806 Component::OnlyChild => {
807 matches_first_child(element, flags_setter) && matches_last_child(element, flags_setter)
808 },
809 Component::Root => element.is_root(),
810 Component::Empty => {
811 flags_setter(element, ElementSelectorFlags::HAS_EMPTY_SELECTOR);
812 element.is_empty()
813 },
814 Component::Host(ref selector) => {
815 context
816 .shared
817 .shadow_host()
818 .map_or(false, |host| host == element.opaque()) &&
819 selector.as_ref().map_or(true, |selector| {
820 context.shared.nest(|context| {
821 matches_complex_selector(selector.iter(), element, context, flags_setter)
822 })
823 })
824 },
825 Component::Scope => match context.shared.scope_element {
826 Some(ref scope_element) => element.opaque() == *scope_element,
827 None => element.is_root(),
828 },
829 Component::NthChild(a, b) => {
830 matches_generic_nth_child(element, context, a, b, false, false, flags_setter)
831 },
832 Component::NthLastChild(a, b) => {
833 matches_generic_nth_child(element, context, a, b, false, true, flags_setter)
834 },
835 Component::NthOfType(a, b) => {
836 matches_generic_nth_child(element, context, a, b, true, false, flags_setter)
837 },
838 Component::NthLastOfType(a, b) => {
839 matches_generic_nth_child(element, context, a, b, true, true, flags_setter)
840 },
841 Component::FirstOfType => {
842 matches_generic_nth_child(element, context, 0, 1, true, false, flags_setter)
843 },
844 Component::LastOfType => {
845 matches_generic_nth_child(element, context, 0, 1, true, true, flags_setter)
846 },
847 Component::OnlyOfType => {
848 matches_generic_nth_child(element, context, 0, 1, true, false, flags_setter) &&
849 matches_generic_nth_child(element, context, 0, 1, true, true, flags_setter)
850 },
851 Component::Negation(ref negated) => context.shared.nest_for_negation(|context| {
852 let mut local_context = LocalMatchingContext {
853 matches_hover_and_active_quirk: MatchesHoverAndActiveQuirk::No,
854 shared: context,
855 };
856 !negated
857 .iter()
858 .all(|ss| matches_simple_selector(ss, element, &mut local_context, flags_setter))
859 }),
860 }
861 }
862
863 #[inline(always)]
select_name<'a, T>(is_html: bool, local_name: &'a T, local_name_lower: &'a T) -> &'a T864 fn select_name<'a, T>(is_html: bool, local_name: &'a T, local_name_lower: &'a T) -> &'a T {
865 if is_html {
866 local_name_lower
867 } else {
868 local_name
869 }
870 }
871
872 #[inline]
matches_generic_nth_child<E, F>( element: &E, context: &mut LocalMatchingContext<E::Impl>, a: i32, b: i32, is_of_type: bool, is_from_end: bool, flags_setter: &mut F, ) -> bool where E: Element, F: FnMut(&E, ElementSelectorFlags),873 fn matches_generic_nth_child<E, F>(
874 element: &E,
875 context: &mut LocalMatchingContext<E::Impl>,
876 a: i32,
877 b: i32,
878 is_of_type: bool,
879 is_from_end: bool,
880 flags_setter: &mut F,
881 ) -> bool
882 where
883 E: Element,
884 F: FnMut(&E, ElementSelectorFlags),
885 {
886 if element.ignores_nth_child_selectors() {
887 return false;
888 }
889
890 flags_setter(
891 element,
892 if is_from_end {
893 ElementSelectorFlags::HAS_SLOW_SELECTOR
894 } else {
895 ElementSelectorFlags::HAS_SLOW_SELECTOR_LATER_SIBLINGS
896 },
897 );
898
899 // Grab a reference to the appropriate cache.
900 let mut cache = context
901 .shared
902 .nth_index_cache
903 .as_mut()
904 .map(|c| c.get(is_of_type, is_from_end));
905
906 // Lookup or compute the index.
907 let index = if let Some(i) = cache.as_mut().and_then(|c| c.lookup(element.opaque())) {
908 i
909 } else {
910 let i = nth_child_index(
911 element,
912 is_of_type,
913 is_from_end,
914 cache.as_mut().map(|s| &mut **s),
915 );
916 cache.as_mut().map(|c| c.insert(element.opaque(), i));
917 i
918 };
919 debug_assert_eq!(
920 index,
921 nth_child_index(element, is_of_type, is_from_end, None),
922 "invalid cache"
923 );
924
925 // Is there a non-negative integer n such that An+B=index?
926 match index.checked_sub(b) {
927 None => false,
928 Some(an) => match an.checked_div(a) {
929 Some(n) => n >= 0 && a * n == an,
930 None /* a == 0 */ => an == 0,
931 },
932 }
933 }
934
935 #[inline]
nth_child_index<E>( element: &E, is_of_type: bool, is_from_end: bool, mut cache: Option<&mut NthIndexCacheInner>, ) -> i32 where E: Element,936 fn nth_child_index<E>(
937 element: &E,
938 is_of_type: bool,
939 is_from_end: bool,
940 mut cache: Option<&mut NthIndexCacheInner>,
941 ) -> i32
942 where
943 E: Element,
944 {
945 // The traversal mostly processes siblings left to right. So when we walk
946 // siblings to the right when computing NthLast/NthLastOfType we're unlikely
947 // to get cache hits along the way. As such, we take the hit of walking the
948 // siblings to the left checking the cache in the is_from_end case (this
949 // matches what Gecko does). The indices-from-the-left is handled during the
950 // regular look further below.
951 if let Some(ref mut c) = cache {
952 if is_from_end && !c.is_empty() {
953 let mut index: i32 = 1;
954 let mut curr = element.clone();
955 while let Some(e) = curr.prev_sibling_element() {
956 curr = e;
957 if !is_of_type || element.is_same_type(&curr) {
958 if let Some(i) = c.lookup(curr.opaque()) {
959 return i - index;
960 }
961 index += 1;
962 }
963 }
964 }
965 }
966
967 let mut index: i32 = 1;
968 let mut curr = element.clone();
969 let next = |e: E| {
970 if is_from_end {
971 e.next_sibling_element()
972 } else {
973 e.prev_sibling_element()
974 }
975 };
976 while let Some(e) = next(curr) {
977 curr = e;
978 if !is_of_type || element.is_same_type(&curr) {
979 // If we're computing indices from the left, check each element in the
980 // cache. We handle the indices-from-the-right case at the top of this
981 // function.
982 if !is_from_end {
983 if let Some(i) = cache.as_mut().and_then(|c| c.lookup(curr.opaque())) {
984 return i + index;
985 }
986 }
987 index += 1;
988 }
989 }
990
991 index
992 }
993
994 #[inline]
matches_first_child<E, F>(element: &E, flags_setter: &mut F) -> bool where E: Element, F: FnMut(&E, ElementSelectorFlags),995 fn matches_first_child<E, F>(element: &E, flags_setter: &mut F) -> bool
996 where
997 E: Element,
998 F: FnMut(&E, ElementSelectorFlags),
999 {
1000 flags_setter(element, ElementSelectorFlags::HAS_EDGE_CHILD_SELECTOR);
1001 element.prev_sibling_element().is_none()
1002 }
1003
1004 #[inline]
matches_last_child<E, F>(element: &E, flags_setter: &mut F) -> bool where E: Element, F: FnMut(&E, ElementSelectorFlags),1005 fn matches_last_child<E, F>(element: &E, flags_setter: &mut F) -> bool
1006 where
1007 E: Element,
1008 F: FnMut(&E, ElementSelectorFlags),
1009 {
1010 flags_setter(element, ElementSelectorFlags::HAS_EDGE_CHILD_SELECTOR);
1011 element.next_sibling_element().is_none()
1012 }
1013