From def92d1b8e9d373e2f6f27c366d578d97d8960c6 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 15 May 2024 05:34:50 +0200 Subject: Merging upstream version 126.0. Signed-off-by: Daniel Baumann --- servo/components/selectors/attr.rs | 17 +- servo/components/selectors/builder.rs | 198 ++++++++-------- servo/components/selectors/context.rs | 36 ++- servo/components/selectors/kleene_value.rs | 131 +++++++++++ servo/components/selectors/lib.rs | 1 + servo/components/selectors/matching.rs | 350 ++++++++++++++++++++--------- servo/components/selectors/parser.rs | 257 +++++++++++---------- servo/components/selectors/tree.rs | 5 + 8 files changed, 657 insertions(+), 338 deletions(-) create mode 100644 servo/components/selectors/kleene_value.rs (limited to 'servo/components/selectors') diff --git a/servo/components/selectors/attr.rs b/servo/components/selectors/attr.rs index fee2962237..70a0c5ea95 100644 --- a/servo/components/selectors/attr.rs +++ b/servo/components/selectors/attr.rs @@ -111,16 +111,21 @@ impl AttrSelectorOperator { let case = case_sensitivity; match self { AttrSelectorOperator::Equal => case.eq(e, s), - AttrSelectorOperator::Prefix => e.len() >= s.len() && case.eq(&e[..s.len()], s), + AttrSelectorOperator::Prefix => { + !s.is_empty() && e.len() >= s.len() && case.eq(&e[..s.len()], s) + }, AttrSelectorOperator::Suffix => { - e.len() >= s.len() && case.eq(&e[(e.len() - s.len())..], s) + !s.is_empty() && e.len() >= s.len() && case.eq(&e[(e.len() - s.len())..], s) }, AttrSelectorOperator::Substring => { - case.contains(element_attr_value, attr_selector_value) + !s.is_empty() && case.contains(element_attr_value, attr_selector_value) + }, + AttrSelectorOperator::Includes => { + !s.is_empty() && + element_attr_value + .split(SELECTOR_WHITESPACE) + .any(|part| case.eq(part.as_bytes(), s)) }, - AttrSelectorOperator::Includes => element_attr_value - .split(SELECTOR_WHITESPACE) - .any(|part| case.eq(part.as_bytes(), s)), AttrSelectorOperator::DashMatch => { case.eq(e, s) || (e.get(s.len()) == Some(&b'-') && case.eq(&e[..s.len()], s)) }, diff --git a/servo/components/selectors/builder.rs b/servo/components/selectors/builder.rs index 2406cd84f6..c706554185 100644 --- a/servo/components/selectors/builder.rs +++ b/servo/components/selectors/builder.rs @@ -6,59 +6,45 @@ //! //! Our selector representation is designed to optimize matching, and has //! several requirements: -//! * All simple selectors and combinators are stored inline in the same buffer -//! as Component instances. -//! * We store the top-level compound selectors from right to left, i.e. in -//! matching order. -//! * We store the simple selectors for each combinator from left to right, so -//! that we match the cheaper simple selectors first. +//! * All simple selectors and combinators are stored inline in the same buffer as Component +//! instances. +//! * We store the top-level compound selectors from right to left, i.e. in matching order. +//! * We store the simple selectors for each combinator from left to right, so that we match the +//! cheaper simple selectors first. //! -//! Meeting all these constraints without extra memmove traffic during parsing -//! is non-trivial. This module encapsulates those details and presents an -//! easy-to-use API for the parser. +//! For example, the selector: +//! +//! .bar:hover > .baz:nth-child(2) + .qux +//! +//! Gets stored as: +//! +//! [.qux, + , .baz, :nth-child(2), > , .bar, :hover] +//! +//! Meeting all these constraints without extra memmove traffic during parsing is non-trivial. This +//! module encapsulates those details and presents an easy-to-use API for the parser. -use crate::parser::{Combinator, Component, RelativeSelector, Selector, SelectorImpl}; +use crate::parser::{Combinator, Component, RelativeSelector, Selector, SelectorImpl, ParseRelative}; use crate::sink::Push; use servo_arc::{Arc, ThinArc}; -use smallvec::{self, SmallVec}; +use smallvec::SmallVec; use std::cmp; -use std::iter; -use std::ptr; use std::slice; -/// Top-level SelectorBuilder struct. This should be stack-allocated by the -/// consumer and never moved (because it contains a lot of inline data that -/// would be slow to memmov). +/// Top-level SelectorBuilder struct. This should be stack-allocated by the consumer and never +/// moved (because it contains a lot of inline data that would be slow to memmove). /// -/// After instantation, callers may call the push_simple_selector() and -/// push_combinator() methods to append selector data as it is encountered -/// (from left to right). Once the process is complete, callers should invoke -/// build(), which transforms the contents of the SelectorBuilder into a heap- -/// allocated Selector and leaves the builder in a drained state. +/// After instantiation, callers may call the push_simple_selector() and push_combinator() methods +/// to append selector data as it is encountered (from left to right). Once the process is +/// complete, callers should invoke build(), which transforms the contents of the SelectorBuilder +/// into a heap- allocated Selector and leaves the builder in a drained state. #[derive(Debug)] pub struct SelectorBuilder { - /// The entire sequence of simple selectors, from left to right, without combinators. - /// - /// We make this large because the result of parsing a selector is fed into a new - /// Arc-ed allocation, so any spilled vec would be a wasted allocation. Also, - /// Components are large enough that we don't have much cache locality benefit - /// from reserving stack space for fewer of them. - simple_selectors: SmallVec<[Component; 32]>, - /// The combinators, and the length of the compound selector to their left. - combinators: SmallVec<[(Combinator, usize); 16]>, - /// The length of the current compount selector. - current_len: usize, -} - -impl Default for SelectorBuilder { - #[inline(always)] - fn default() -> Self { - SelectorBuilder { - simple_selectors: SmallVec::new(), - combinators: SmallVec::new(), - current_len: 0, - } - } + /// The entire sequence of components. We make this large because the result of parsing a + /// selector is fed into a new Arc-ed allocation, so any spilled vec would be a wasted + /// allocation. Also, Components are large enough that we don't have much cache locality + /// benefit from reserving stack space for fewer of them. + components: SmallVec<[Component; 32]>, + last_compound_start: Option, } impl Push> for SelectorBuilder { @@ -71,101 +57,115 @@ impl SelectorBuilder { /// Pushes a simple selector onto the current compound selector. #[inline(always)] pub fn push_simple_selector(&mut self, ss: Component) { - assert!(!ss.is_combinator()); - self.simple_selectors.push(ss); - self.current_len += 1; + debug_assert!(!ss.is_combinator()); + self.components.push(ss); } - /// Completes the current compound selector and starts a new one, delimited - /// by the given combinator. + /// Completes the current compound selector and starts a new one, delimited by the given + /// combinator. #[inline(always)] pub fn push_combinator(&mut self, c: Combinator) { - self.combinators.push((c, self.current_len)); - self.current_len = 0; + self.reverse_last_compound(); + self.components.push(Component::Combinator(c)); + self.last_compound_start = Some(self.components.len()); + } + + fn reverse_last_compound(&mut self) { + let start = self.last_compound_start.unwrap_or(0); + self.components[start..].reverse(); } /// Returns true if combinators have ever been pushed to this builder. #[inline(always)] pub fn has_combinators(&self) -> bool { - !self.combinators.is_empty() + self.last_compound_start.is_some() } /// Consumes the builder, producing a Selector. #[inline(always)] - pub fn build(&mut self) -> ThinArc> { + pub fn build(&mut self, parse_relative: ParseRelative) -> ThinArc> { // Compute the specificity and flags. - let sf = specificity_and_flags(self.simple_selectors.iter()); - self.build_with_specificity_and_flags(sf) + let sf = specificity_and_flags(self.components.iter()); + self.build_with_specificity_and_flags(sf, parse_relative) } - /// Builds with an explicit SpecificityAndFlags. This is separated from build() so - /// that unit tests can pass an explicit specificity. + /// Builds with an explicit SpecificityAndFlags. This is separated from build() so that unit + /// tests can pass an explicit specificity. #[inline(always)] pub(crate) fn build_with_specificity_and_flags( &mut self, - spec: SpecificityAndFlags, + mut spec: SpecificityAndFlags, + parse_relative: ParseRelative, ) -> ThinArc> { - // Create the Arc using an iterator that drains our buffers. - // Panic-safety: if SelectorBuilderIter is not iterated to the end, some simple selectors - // will safely leak. - let raw_simple_selectors = unsafe { - let simple_selectors_len = self.simple_selectors.len(); - self.simple_selectors.set_len(0); - std::slice::from_raw_parts(self.simple_selectors.as_ptr(), simple_selectors_len) - }; - let (rest, current) = split_from_end(raw_simple_selectors, self.current_len); - let iter = SelectorBuilderIter { - current_simple_selectors: current.iter(), - rest_of_simple_selectors: rest, - combinators: self.combinators.drain(..).rev(), + let implicit_parent = parse_relative.needs_implicit_parent_selector() && + !spec.flags.contains(SelectorFlags::HAS_PARENT); + + let parent_selector_and_combinator; + let implicit_parent = if implicit_parent { + spec.flags.insert(SelectorFlags::HAS_PARENT); + parent_selector_and_combinator = [ + Component::Combinator(Combinator::Descendant), + Component::ParentSelector, + ]; + &parent_selector_and_combinator[..] + } else { + &[] }; - Arc::from_header_and_iter(spec, iter) + // As an optimization, for a selector without combinators, we can just keep the order + // as-is. + if self.last_compound_start.is_none() { + return Arc::from_header_and_iter(spec, ExactChain(self.components.drain(..), implicit_parent.iter().cloned())); + } + + self.reverse_last_compound(); + Arc::from_header_and_iter(spec, ExactChain(self.components.drain(..).rev(), implicit_parent.iter().cloned())) } } -struct SelectorBuilderIter<'a, Impl: SelectorImpl> { - current_simple_selectors: slice::Iter<'a, Component>, - rest_of_simple_selectors: &'a [Component], - combinators: iter::Rev>, + +impl Default for SelectorBuilder { + #[inline(always)] + fn default() -> Self { + SelectorBuilder { + components: SmallVec::new(), + last_compound_start: None, + } + } } -impl<'a, Impl: SelectorImpl> ExactSizeIterator for SelectorBuilderIter<'a, Impl> { +// This is effectively a Chain<>, but Chain isn't an ExactSizeIterator, see +// https://github.com/rust-lang/rust/issues/34433 +struct ExactChain(A, B); + +impl ExactSizeIterator for ExactChain +where + A: ExactSizeIterator, + B: ExactSizeIterator, +{ fn len(&self) -> usize { - self.current_simple_selectors.len() + - self.rest_of_simple_selectors.len() + - self.combinators.len() + self.0.len() + self.1.len() } } -impl<'a, Impl: SelectorImpl> Iterator for SelectorBuilderIter<'a, Impl> { - type Item = Component; +impl Iterator for ExactChain +where + A: ExactSizeIterator, + B: ExactSizeIterator, +{ + type Item = Item; + #[inline(always)] fn next(&mut self) -> Option { - if let Some(simple_selector_ref) = self.current_simple_selectors.next() { - // Move a simple selector out of this slice iterator. - // This is safe because we’ve called SmallVec::set_len(0) above, - // so SmallVec::drop won’t drop this simple selector. - unsafe { Some(ptr::read(simple_selector_ref)) } - } else { - self.combinators.next().map(|(combinator, len)| { - let (rest, current) = split_from_end(self.rest_of_simple_selectors, len); - self.rest_of_simple_selectors = rest; - self.current_simple_selectors = current.iter(); - Component::Combinator(combinator) - }) - } + self.0.next().or_else(|| self.1.next()) } fn size_hint(&self) -> (usize, Option) { - (self.len(), Some(self.len())) + let len = self.len(); + (len, Some(len)) } } -fn split_from_end(s: &[T], at: usize) -> (&[T], &[T]) { - s.split_at(s.len() - at) -} - /// Flags that indicate at which point of parsing a selector are we. #[derive(Clone, Copy, Default, Eq, PartialEq, ToShmem)] pub(crate) struct SelectorFlags(u8); diff --git a/servo/components/selectors/context.rs b/servo/components/selectors/context.rs index 84ee262dfe..289b081b64 100644 --- a/servo/components/selectors/context.rs +++ b/servo/components/selectors/context.rs @@ -79,10 +79,18 @@ pub enum NeedsSelectorFlags { } /// Whether we're matching in the contect of invalidation. -#[derive(PartialEq)] +#[derive(Clone, Copy, PartialEq)] pub enum MatchingForInvalidation { No, Yes, + YesForComparison, +} + +impl MatchingForInvalidation { + /// Are we matching for invalidation? + pub fn is_for_invalidation(&self) -> bool { + matches!(*self, Self::Yes | Self::YesForComparison) + } } /// Which quirks mode is this document in. @@ -314,7 +322,31 @@ where /// Whether or not we're matching to invalidate. #[inline] pub fn matching_for_invalidation(&self) -> bool { - self.matching_for_invalidation == MatchingForInvalidation::Yes + self.matching_for_invalidation.is_for_invalidation() + } + + /// Whether or not we're comparing for invalidation, if we are matching for invalidation. + #[inline] + pub fn matching_for_invalidation_comparison(&self) -> Option { + match self.matching_for_invalidation { + MatchingForInvalidation::No => None, + MatchingForInvalidation::Yes => Some(false), + MatchingForInvalidation::YesForComparison => Some(true), + } + } + + /// Run the given matching function for before/after invalidation comparison. + #[inline] + pub fn for_invalidation_comparison(&mut self, f: F) -> R + where + F: FnOnce(&mut Self) -> R, + { + debug_assert!(self.matching_for_invalidation(), "Not matching for invalidation?"); + let prev = self.matching_for_invalidation; + self.matching_for_invalidation = MatchingForInvalidation::YesForComparison; + let result = f(self); + self.matching_for_invalidation = prev; + result } /// The case-sensitivity for class and ID selectors diff --git a/servo/components/selectors/kleene_value.rs b/servo/components/selectors/kleene_value.rs new file mode 100644 index 0000000000..58141c1156 --- /dev/null +++ b/servo/components/selectors/kleene_value.rs @@ -0,0 +1,131 @@ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at https://mozilla.org/MPL/2.0/. */ + +//! Kleen logic: https://en.wikipedia.org/wiki/Three-valued_logic#Kleene_and_Priest_logics + +/// A "trilean" value based on Kleen logic. +#[derive(Clone, Copy, Debug, Eq, PartialEq)] +pub enum KleeneValue { + /// False + False = 0, + /// True + True = 1, + /// Either true or false, but we’re not sure which yet. + Unknown, +} + +impl From for KleeneValue { + fn from(b: bool) -> Self { + if b { + Self::True + } else { + Self::False + } + } +} + +impl KleeneValue { + /// Turns this Kleene value to a bool, taking the unknown value as an + /// argument. + pub fn to_bool(self, unknown: bool) -> bool { + match self { + Self::True => true, + Self::False => false, + Self::Unknown => unknown, + } + } + + /// Return true if any result of f() is true. Otherwise, return the strongest value seen. + /// Returns false if empty, like that of `Iterator`. + pub fn any( + iter: impl Iterator, + f: impl FnMut(T) -> Self, + ) -> Self { + Self::any_value(iter, Self::True, Self::False, f) + } + + /// Return false if any results of f() is false. Otherwise, return the strongest value seen. + /// Returns true if empty, opposite of `Iterator`. + pub fn any_false( + iter: impl Iterator, + f: impl FnMut(T) -> Self, + ) -> Self { + Self::any_value(iter, Self::False, Self::True, f) + } + + fn any_value( + iter: impl Iterator, + value: Self, + on_empty: Self, + mut f: impl FnMut(T) -> Self, + ) -> Self { + let mut result = None; + for item in iter { + let r = f(item); + if r == value { + return r; + } + if let Some(v) = result.as_mut() { + *v = *v & r; + } else { + result = Some(r); + } + } + result.unwrap_or(on_empty) + } +} + +impl std::ops::Not for KleeneValue { + type Output = Self; + + fn not(self) -> Self { + match self { + Self::True => Self::False, + Self::False => Self::True, + Self::Unknown => Self::Unknown, + } + } +} + +// Implements the logical and operation. +impl std::ops::BitAnd for KleeneValue { + type Output = Self; + + fn bitand(self, other: Self) -> Self { + if self == Self::False || other == Self::False { + return Self::False; + } + if self == Self::Unknown || other == Self::Unknown { + return Self::Unknown; + } + Self::True + } +} + +// Implements the logical or operation. +impl std::ops::BitOr for KleeneValue { + type Output = Self; + + fn bitor(self, other: Self) -> Self { + if self == Self::True || other == Self::True { + return Self::True; + } + if self == Self::Unknown || other == Self::Unknown { + return Self::Unknown; + } + Self::False + } +} + +impl std::ops::BitOrAssign for KleeneValue { + fn bitor_assign(&mut self, other: Self) { + *self = *self | other; + } +} + +impl std::ops::BitAndAssign for KleeneValue { + fn bitand_assign(&mut self, other: Self) { + *self = *self & other; + } +} diff --git a/servo/components/selectors/lib.rs b/servo/components/selectors/lib.rs index d909059ccf..6e300893d2 100644 --- a/servo/components/selectors/lib.rs +++ b/servo/components/selectors/lib.rs @@ -35,6 +35,7 @@ pub mod relative_selector; pub mod sink; mod tree; pub mod visitor; +pub mod kleene_value; pub use crate::nth_index_cache::NthIndexCache; pub use crate::parser::{Parser, SelectorImpl, SelectorList}; diff --git a/servo/components/selectors/matching.rs b/servo/components/selectors/matching.rs index 763f65d547..282d04064b 100644 --- a/servo/components/selectors/matching.rs +++ b/servo/components/selectors/matching.rs @@ -7,6 +7,7 @@ use crate::attr::{ ParsedAttrSelectorOperation, ParsedCaseSensitivity, }; use crate::bloom::{BloomFilter, BLOOM_HASH_MASK}; +use crate::kleene_value::KleeneValue; use crate::parser::{ AncestorHashes, Combinator, Component, LocalName, NthSelectorData, RelativeSelectorMatchHint, }; @@ -200,12 +201,39 @@ fn may_match(hashes: &AncestorHashes, bf: &BloomFilter) -> bool { /// However since the selector "c1" raises /// NotMatchedAndRestartFromClosestDescendant. So the selector /// "b1 + c1 > b2 ~ " doesn't match and restart matching from "d1". +/// +/// There is also the unknown result, which is used during invalidation when +/// specific selector is being tested for before/after comparison. More specifically, +/// selectors that are too expensive to correctly compute during invalidation may +/// return unknown, as the computation will be thrown away and only to be recomputed +/// during styling. For most cases, the unknown result can be treated as matching. +/// This is because a compound of selectors acts like &&, and unknown && matched +/// == matched and unknown && not-matched == not-matched. However, some selectors, +/// like `:is()`, behave like || i.e. `:is(.a, .b)` == a || b. Treating unknown +/// == matching then causes these selectors to always return matching, which undesired +/// for before/after comparison. Coercing to not-matched doesn't work since each +/// inner selector may have compounds: e.g. Toggling `.foo` in `:is(.foo:has(..))` +/// with coersion to not-matched would result in an invalid before/after comparison +/// of not-matched/not-matched. #[derive(Clone, Copy, Eq, PartialEq)] enum SelectorMatchingResult { Matched, NotMatchedAndRestartFromClosestLaterSibling, NotMatchedAndRestartFromClosestDescendant, NotMatchedGlobally, + Unknown, +} + +impl From for KleeneValue { + fn from(value: SelectorMatchingResult) -> Self { + match value { + SelectorMatchingResult::Matched => KleeneValue::True, + SelectorMatchingResult::Unknown => KleeneValue::Unknown, + SelectorMatchingResult::NotMatchedAndRestartFromClosestLaterSibling | + SelectorMatchingResult::NotMatchedAndRestartFromClosestDescendant | + SelectorMatchingResult::NotMatchedGlobally => KleeneValue::False, + } + } } /// Matches a selector, fast-rejecting against a bloom filter. @@ -224,6 +252,28 @@ pub fn matches_selector( element: &E, context: &mut MatchingContext, ) -> bool +where + E: Element, +{ + let result = matches_selector_kleene(selector, offset, hashes, element, context); + if cfg!(debug_assertions) && result == KleeneValue::Unknown { + debug_assert!( + context.matching_for_invalidation_comparison().unwrap_or(false), + "How did we return unknown?" + ); + } + result.to_bool(true) +} + +/// Same as matches_selector, but returns the Kleene value as-is. +#[inline(always)] +pub fn matches_selector_kleene( + selector: &Selector, + offset: usize, + hashes: Option<&AncestorHashes>, + element: &E, + context: &mut MatchingContext, +) -> KleeneValue where E: Element, { @@ -231,7 +281,7 @@ where if let Some(hashes) = hashes { if let Some(filter) = context.bloom_filter { if !may_match(hashes, filter) { - return false; + return KleeneValue::False; } } } @@ -275,6 +325,12 @@ pub fn matches_compound_selector_from( where E: Element, { + debug_assert!( + !context + .matching_for_invalidation_comparison() + .unwrap_or(false), + "CompoundSelectorMatchingResult doesn't support unknown" + ); if cfg!(debug_assertions) && from_offset != 0 { selector.combinator_at_parse_order(from_offset - 1); // This asserts. } @@ -320,7 +376,9 @@ where ); for component in iter { - if !matches_simple_selector(component, element, &mut local_context) { + let result = matches_simple_selector(component, element, &mut local_context); + debug_assert!(result != KleeneValue::Unknown, "Returned unknown in non invalidation context?"); + if !result.to_bool(true) { return CompoundSelectorMatchingResult::NotMatched; } } @@ -341,7 +399,7 @@ fn matches_complex_selector( element: &E, context: &mut MatchingContext, rightmost: SubjectOrPseudoElement, -) -> bool +) -> KleeneValue where E: Element, { @@ -353,7 +411,7 @@ where Component::PseudoElement(ref pseudo) => { if let Some(ref f) = context.pseudo_element_matching_fn { if !f(pseudo) { - return false; + return KleeneValue::False; } } }, @@ -364,12 +422,12 @@ where in a non-pseudo selector {:?}", other ); - return false; + return KleeneValue::False; }, } if !iter.matches_for_stateless_pseudo_element() { - return false; + return KleeneValue::False; } // Advance to the non-pseudo-element part of the selector. @@ -377,9 +435,14 @@ where debug_assert_eq!(next_sequence, Combinator::PseudoElement); } - let result = matches_complex_selector_internal(iter, element, context, rightmost); - - matches!(result, SelectorMatchingResult::Matched) + matches_complex_selector_internal( + iter, + element, + context, + rightmost, + SubjectOrPseudoElement::Yes, + ) + .into() } /// Matches each selector of a list as a complex selector @@ -388,13 +451,16 @@ fn matches_complex_selector_list( element: &E, context: &mut MatchingContext, rightmost: SubjectOrPseudoElement, -) -> bool { - for selector in list { - if matches_complex_selector(selector.iter(), element, context, rightmost) { - return true; - } - } - false +) -> KleeneValue { + KleeneValue::any( + list.iter(), + |selector| matches_complex_selector( + selector.iter(), + element, + context, + rightmost + ) + ) } fn matches_relative_selector( @@ -423,7 +489,8 @@ fn matches_relative_selector( &el, context, rightmost, - ); + ) + .to_bool(true); if !matched && relative_selector.match_hint.is_subtree() { matched = matches_relative_selector_subtree( &relative_selector.selector, @@ -472,6 +539,7 @@ fn matches_relative_selector( ) } else { matches_complex_selector(relative_selector.selector.iter(), &el, context, rightmost) + .to_bool(true) }; if matched { return true; @@ -490,12 +558,6 @@ fn relative_selector_match_early( element: &E, context: &mut MatchingContext, ) -> Option { - if context.matching_for_invalidation() { - // In the context of invalidation, we can't use caching/filtering due to - // now/then matches. DOM structure also may have changed, so just pretend - // that we always match. - return Some(!context.in_negation()); - } // See if we can return a cached result. if let Some(cached) = context .selector_caches @@ -526,18 +588,28 @@ fn match_relative_selectors( element: &E, context: &mut MatchingContext, rightmost: SubjectOrPseudoElement, -) -> bool { +) -> KleeneValue { if context.relative_selector_anchor().is_some() { // FIXME(emilio): This currently can happen with nesting, and it's not fully // correct, arguably. But the ideal solution isn't super-clear either. For now, // cope with it and explicitly reject it at match time. See [1] for discussion. // // [1]: https://github.com/w3c/csswg-drafts/issues/9600 - return false; + return KleeneValue::False; + } + if let Some(may_return_unknown) = context.matching_for_invalidation_comparison() { + // In the context of invalidation, :has is expensive, especially because we + // can't use caching/filtering due to now/then matches. DOM structure also + // may have changed. + return if may_return_unknown { + KleeneValue::Unknown + } else { + KleeneValue::from(!context.in_negation()) + }; } context.nest_for_relative_selector(element.opaque(), |context| { do_match_relative_selectors(selectors, element, context, rightmost) - }) + }).into() } /// Matches a relative selector in a list of relative selectors. @@ -604,7 +676,7 @@ fn matches_relative_selector_subtree( ElementSelectorFlags::RELATIVE_SELECTOR_SEARCH_DIRECTION_ANCESTOR, ); } - if matches_complex_selector(selector.iter(), &el, context, rightmost) { + if matches_complex_selector(selector.iter(), &el, context, rightmost).to_bool(true) { return true; } @@ -643,19 +715,8 @@ fn hover_and_active_quirk_applies( } selector_iter.clone().all(|simple| match *simple { - Component::LocalName(_) | - Component::AttributeInNoNamespaceExists { .. } | - Component::AttributeInNoNamespace { .. } | - Component::AttributeOther(_) | - Component::ID(_) | - Component::Class(_) | - Component::PseudoElement(_) | - Component::Negation(_) | - Component::Empty | - Component::Nth(_) | - Component::NthOf(_) => false, Component::NonTSPseudoClass(ref pseudo_class) => pseudo_class.is_active_or_hover(), - _ => true, + _ => false, }) } @@ -753,6 +814,7 @@ fn matches_complex_selector_internal( element: &E, context: &mut MatchingContext, rightmost: SubjectOrPseudoElement, + first_subject_compound: SubjectOrPseudoElement, ) -> SelectorMatchingResult where E: Element, @@ -762,8 +824,24 @@ where selector_iter, element ); - let matches_compound_selector = - matches_compound_selector(&mut selector_iter, element, context, rightmost); + let matches_compound_selector = { + let result = matches_compound_selector(&mut selector_iter, element, context, rightmost); + // We only care for unknown match in the first subject in compound - in the context of comparison + // invalidation, ancestors/previous sibling being an unknown match doesn't matter - we must + // invalidate to guarantee correctness. + if result == KleeneValue::Unknown && first_subject_compound == SubjectOrPseudoElement::No { + debug_assert!( + context + .matching_for_invalidation_comparison() + .unwrap_or(false), + "How did we return unknown?" + ); + // Coerce the result to matched. + KleeneValue::True + } else { + result + } + }; let combinator = selector_iter.next_sequence(); if combinator.map_or(false, |c| c.is_sibling()) { @@ -772,24 +850,42 @@ where } } - if !matches_compound_selector { + // We don't short circuit unknown here, since the rest of the selector + // to the left of this compound may return false. + if matches_compound_selector == KleeneValue::False { return SelectorMatchingResult::NotMatchedAndRestartFromClosestLaterSibling; } let combinator = match combinator { - None => return SelectorMatchingResult::Matched, + None => { + return match matches_compound_selector { + KleeneValue::True => SelectorMatchingResult::Matched, + KleeneValue::Unknown => SelectorMatchingResult::Unknown, + KleeneValue::False => unreachable!(), + } + }, Some(c) => c, }; - let (candidate_not_found, mut rightmost) = match combinator { - Combinator::NextSibling | Combinator::LaterSibling => { - (SelectorMatchingResult::NotMatchedAndRestartFromClosestDescendant, SubjectOrPseudoElement::No) - }, + let (candidate_not_found, rightmost, first_subject_compound) = match combinator { + Combinator::NextSibling | Combinator::LaterSibling => ( + SelectorMatchingResult::NotMatchedAndRestartFromClosestDescendant, + SubjectOrPseudoElement::No, + SubjectOrPseudoElement::No, + ), Combinator::Child | Combinator::Descendant | Combinator::SlotAssignment | - Combinator::Part => (SelectorMatchingResult::NotMatchedGlobally, SubjectOrPseudoElement::No), - Combinator::PseudoElement => (SelectorMatchingResult::NotMatchedGlobally, rightmost), + Combinator::Part => ( + SelectorMatchingResult::NotMatchedGlobally, + SubjectOrPseudoElement::No, + SubjectOrPseudoElement::No, + ), + Combinator::PseudoElement => ( + SelectorMatchingResult::NotMatchedGlobally, + rightmost, + first_subject_compound, + ), }; // Stop matching :visited as soon as we find a link, or a combinator for @@ -818,18 +914,27 @@ where &element, context, rightmost, + first_subject_compound, ) }); - if !matches!(combinator, Combinator::PseudoElement) { - rightmost = SubjectOrPseudoElement::No; - } - match (result, combinator) { // Return the status immediately. - (SelectorMatchingResult::Matched, _) | - (SelectorMatchingResult::NotMatchedGlobally, _) | - (_, Combinator::NextSibling) => { + (SelectorMatchingResult::Matched | SelectorMatchingResult::Unknown, _) => { + debug_assert!( + matches_compound_selector.to_bool(true), + "Compound didn't match?" + ); + if result == SelectorMatchingResult::Matched && + matches_compound_selector.to_bool(false) + { + // Matches without question + return result; + } + // Something returned unknown, so return unknown. + return SelectorMatchingResult::Unknown; + }, + (SelectorMatchingResult::NotMatchedGlobally, _) | (_, Combinator::NextSibling) => { return result; }, @@ -921,18 +1026,18 @@ fn matches_host( selector: Option<&Selector>, context: &mut MatchingContext, rightmost: SubjectOrPseudoElement, -) -> bool +) -> KleeneValue where E: Element, { let host = match context.shadow_host() { Some(h) => h, - None => return false, + None => return KleeneValue::False, }; if host != element.opaque() { - return false; + return KleeneValue::False; } - selector.map_or(true, |selector| { + selector.map_or(KleeneValue::True, |selector| { context .nest(|context| matches_complex_selector(selector.iter(), element, context, rightmost)) }) @@ -943,13 +1048,13 @@ fn matches_slotted( selector: &Selector, context: &mut MatchingContext, rightmost: SubjectOrPseudoElement, -) -> bool +) -> KleeneValue where E: Element, { // are never flattened tree slottables. if element.is_html_slot_element() { - return false; + return KleeneValue::False; } context.nest(|context| matches_complex_selector(selector.iter(), element, context, rightmost)) } @@ -994,7 +1099,7 @@ fn matches_compound_selector( element: &E, context: &mut MatchingContext, rightmost: SubjectOrPseudoElement, -) -> bool +) -> KleeneValue where E: Element, { @@ -1008,7 +1113,14 @@ where rightmost, quirks_data, }; - selector_iter.all(|simple| matches_simple_selector(simple, element, &mut local_context)) + KleeneValue::any_false( + selector_iter, + |simple| matches_simple_selector( + simple, + element, + &mut local_context + ) + ) } /// Determines whether the given element matches the given single selector. @@ -1016,13 +1128,13 @@ fn matches_simple_selector( selector: &Component, element: &E, context: &mut LocalMatchingContext, -) -> bool +) -> KleeneValue where E: Element, { debug_assert!(context.shared.is_nested() || !context.shared.in_negation()); let rightmost = context.rightmost; - match *selector { + KleeneValue::from(match *selector { Component::ID(ref id) => { element.has_id(id, context.shared.classes_and_ids_case_sensitivity()) }, @@ -1053,7 +1165,7 @@ where }, Component::Part(ref parts) => matches_part(element, parts, &mut context.shared), Component::Slotted(ref selector) => { - matches_slotted(element, selector, &mut context.shared, rightmost) + return matches_slotted(element, selector, &mut context.shared, rightmost); }, Component::PseudoElement(ref pseudo) => { element.match_pseudo_element(pseudo, context.shared) @@ -1072,7 +1184,7 @@ where !element.is_link() && hover_and_active_quirk_applies(iter, context.shared, context.rightmost) { - return false; + return KleeneValue::False; } } element.match_non_ts_pseudo_class(pc, &mut context.shared) @@ -1085,32 +1197,43 @@ where element.is_empty() }, Component::Host(ref selector) => { - matches_host(element, selector.as_ref(), &mut context.shared, rightmost) + return matches_host(element, selector.as_ref(), &mut context.shared, rightmost); }, Component::ParentSelector | Component::Scope => match context.shared.scope_element { Some(ref scope_element) => element.opaque() == *scope_element, None => element.is_root(), }, Component::Nth(ref nth_data) => { - matches_generic_nth_child(element, context.shared, nth_data, &[], rightmost) + return matches_generic_nth_child(element, context.shared, nth_data, &[], rightmost); }, - Component::NthOf(ref nth_of_data) => context.shared.nest(|context| { - matches_generic_nth_child( + Component::NthOf(ref nth_of_data) => { + return context.shared.nest(|context| { + matches_generic_nth_child( + element, + context, + nth_of_data.nth_data(), + nth_of_data.selectors(), + rightmost, + ) + }) + }, + Component::Is(ref list) | Component::Where(ref list) => { + return context.shared.nest(|context| { + matches_complex_selector_list(list.slice(), element, context, rightmost) + }) + }, + Component::Negation(ref list) => { + return context.shared.nest_for_negation(|context| { + !matches_complex_selector_list(list.slice(), element, context, rightmost) + }) + }, + Component::Has(ref relative_selectors) => { + return match_relative_selectors( + relative_selectors, element, - context, - nth_of_data.nth_data(), - nth_of_data.selectors(), + context.shared, rightmost, - ) - }), - Component::Is(ref list) | Component::Where(ref list) => context.shared.nest(|context| { - matches_complex_selector_list(list.slice(), element, context, rightmost) - }), - Component::Negation(ref list) => context.shared.nest_for_negation(|context| { - !matches_complex_selector_list(list.slice(), element, context, rightmost) - }), - Component::Has(ref relative_selectors) => { - match_relative_selectors(relative_selectors, element, context.shared, rightmost) + ); }, Component::Combinator(_) => unsafe { debug_unreachable!("Shouldn't try to selector-match combinators") @@ -1121,7 +1244,7 @@ where anchor.map_or(true, |a| a == element.opaque()) }, Component::Invalid(..) => false, - } + }) } #[inline(always)] @@ -1163,19 +1286,23 @@ fn matches_generic_nth_child( nth_data: &NthSelectorData, selectors: &[Selector], rightmost: SubjectOrPseudoElement, -) -> bool +) -> KleeneValue where E: Element, { if element.ignores_nth_child_selectors() { - return false; + return KleeneValue::False; } let has_selectors = !selectors.is_empty(); - let selectors_match = - !has_selectors || matches_complex_selector_list(selectors, element, context, rightmost); - if context.matching_for_invalidation() { + let selectors_match = !has_selectors || + matches_complex_selector_list(selectors, element, context, rightmost).to_bool(true); + if let Some(may_return_unknown) = context.matching_for_invalidation_comparison() { // Skip expensive indexing math in invalidation. - return selectors_match && !context.in_negation(); + return if selectors_match && may_return_unknown { + KleeneValue::Unknown + } else { + KleeneValue::from(selectors_match && !context.in_negation()) + }; } let NthSelectorData { ty, a, b, .. } = *nth_data; @@ -1185,18 +1312,23 @@ where !has_selectors, ":only-child and :only-of-type cannot have a selector list!" ); - return matches_generic_nth_child( - element, - context, - &NthSelectorData::first(is_of_type), - selectors, - rightmost, - ) && matches_generic_nth_child( - element, - context, - &NthSelectorData::last(is_of_type), - selectors, - rightmost, + return KleeneValue::from( + matches_generic_nth_child( + element, + context, + &NthSelectorData::first(is_of_type), + selectors, + rightmost, + ) + .to_bool(true) && + matches_generic_nth_child( + element, + context, + &NthSelectorData::last(is_of_type), + selectors, + rightmost, + ) + .to_bool(true), ); } @@ -1223,7 +1355,7 @@ where } if !selectors_match { - return false; + return KleeneValue::False; } // :first/last-child are rather trivial to match, don't bother with the @@ -1234,7 +1366,8 @@ where } else { element.prev_sibling_element() } - .is_none(); + .is_none() + .into(); } // Lookup or compute the index. @@ -1280,6 +1413,7 @@ where None /* a == 0 */ => an == 0, }, } + .into() } #[inline] @@ -1314,7 +1448,7 @@ where let matches = if is_of_type { element.is_same_type(&curr) } else if !selectors.is_empty() { - matches_complex_selector_list(selectors, &curr, context, rightmost) + matches_complex_selector_list(selectors, &curr, context, rightmost).to_bool(true) } else { true }; @@ -1345,7 +1479,7 @@ where let matches = if is_of_type { element.is_same_type(&curr) } else if !selectors.is_empty() { - matches_complex_selector_list(selectors, &curr, context, rightmost) + matches_complex_selector_list(selectors, &curr, context, rightmost).to_bool(true) } else { true }; diff --git a/servo/components/selectors/parser.rs b/servo/components/selectors/parser.rs index 9b0acb0671..37b2b00ca5 100644 --- a/servo/components/selectors/parser.rs +++ b/servo/components/selectors/parser.rs @@ -438,10 +438,20 @@ pub enum ParseRelative { /// Allow selectors to start with a combinator, prepending a parent selector if so. Do nothing /// otherwise ForNesting, + /// Allow selectors to start with a combinator, prepending a scope selector if so. Do nothing + /// otherwise + ForScope, /// Treat as parse error if any selector begins with a combinator. No, } +impl ParseRelative { + #[inline] + pub(crate) fn needs_implicit_parent_selector(self) -> bool { + matches!(self, Self::ForNesting) + } +} + impl SelectorList { /// Returns a selector list with a single `&` pub fn ampersand() -> Self { @@ -469,6 +479,23 @@ impl SelectorList { ) } + pub fn parse_forgiving<'i, 't, P>( + parser: &P, + input: &mut CssParser<'i, 't>, + parse_relative: ParseRelative, + ) -> Result> + where + P: Parser<'i, Impl = Impl>, + { + Self::parse_with_state( + parser, + input, + SelectorParsingState::empty(), + ForgivingParsing::Yes, + parse_relative, + ) + } + #[inline] fn parse_with_state<'i, 't, P>( parser: &P, @@ -932,7 +959,7 @@ impl Selector { } } let spec = SpecificityAndFlags { specificity, flags }; - Selector(builder.build_with_specificity_and_flags(spec)) + Selector(builder.build_with_specificity_and_flags(spec, ParseRelative::No)) } #[inline] @@ -960,9 +987,6 @@ impl Selector { } let result = SelectorList::from_iter(orig.iter().map(|s| { - if !s.has_parent_selector() { - return s.clone(); - } s.replace_parent_selector(parent) })); @@ -1030,82 +1054,53 @@ impl Selector { flags: &mut SelectorFlags, flags_to_propagate: SelectorFlags, ) -> Selector { - if !orig.has_parent_selector() { - return orig.clone(); - } let new_selector = orig.replace_parent_selector(parent); *specificity += Specificity::from(new_selector.specificity() - orig.specificity()); flags.insert(new_selector.flags().intersection(flags_to_propagate)); new_selector } - let mut items = if !self.has_parent_selector() { - // Implicit `&` plus descendant combinator. - let iter = self.iter_raw_match_order(); - let len = iter.len() + 2; - specificity += Specificity::from(parent_specificity_and_flags.specificity); - flags.insert( - parent_specificity_and_flags - .flags - .intersection(SelectorFlags::for_nesting()), - ); - let iter = iter - .cloned() - .chain(std::iter::once(Component::Combinator( - Combinator::Descendant, - ))) - .chain(std::iter::once(Component::Is(parent.clone()))); - UniqueArc::from_header_and_iter_with_size(Default::default(), iter, len) - } else { - let iter = self.iter_raw_match_order().map(|component| { - use self::Component::*; - match *component { - LocalName(..) | - ID(..) | - Class(..) | - AttributeInNoNamespaceExists { .. } | - AttributeInNoNamespace { .. } | - AttributeOther(..) | - ExplicitUniversalType | - ExplicitAnyNamespace | - ExplicitNoNamespace | - DefaultNamespace(..) | - Namespace(..) | - Root | - Empty | - Scope | - Nth(..) | - NonTSPseudoClass(..) | - PseudoElement(..) | - Combinator(..) | - Host(None) | - Part(..) | - Invalid(..) | - RelativeSelectorAnchor => component.clone(), - ParentSelector => { - specificity += Specificity::from(parent_specificity_and_flags.specificity); - flags.insert( - parent_specificity_and_flags - .flags - .intersection(SelectorFlags::for_nesting()), - ); - Is(parent.clone()) - }, - Negation(ref selectors) => { - Negation( - replace_parent_on_selector_list( - selectors.slice(), - parent, - &mut specificity, - &mut flags, - /* propagate_specificity = */ true, - SelectorFlags::for_nesting(), - ) - .unwrap_or_else(|| selectors.clone()), - ) - }, - Is(ref selectors) => { - Is(replace_parent_on_selector_list( + if !self.has_parent_selector() { + return self.clone(); + } + + let iter = self.iter_raw_match_order().map(|component| { + use self::Component::*; + match *component { + LocalName(..) | + ID(..) | + Class(..) | + AttributeInNoNamespaceExists { .. } | + AttributeInNoNamespace { .. } | + AttributeOther(..) | + ExplicitUniversalType | + ExplicitAnyNamespace | + ExplicitNoNamespace | + DefaultNamespace(..) | + Namespace(..) | + Root | + Empty | + Scope | + Nth(..) | + NonTSPseudoClass(..) | + PseudoElement(..) | + Combinator(..) | + Host(None) | + Part(..) | + Invalid(..) | + RelativeSelectorAnchor => component.clone(), + ParentSelector => { + specificity += Specificity::from(parent_specificity_and_flags.specificity); + flags.insert( + parent_specificity_and_flags + .flags + .intersection(SelectorFlags::for_nesting()), + ); + Is(parent.clone()) + }, + Negation(ref selectors) => { + Negation( + replace_parent_on_selector_list( selectors.slice(), parent, &mut specificity, @@ -1113,64 +1108,75 @@ impl Selector { /* propagate_specificity = */ true, SelectorFlags::for_nesting(), ) - .unwrap_or_else(|| selectors.clone())) - }, - Where(ref selectors) => { - Where( - replace_parent_on_selector_list( - selectors.slice(), - parent, - &mut specificity, - &mut flags, - /* propagate_specificity = */ false, - SelectorFlags::for_nesting(), - ) - .unwrap_or_else(|| selectors.clone()), - ) - }, - Has(ref selectors) => Has(replace_parent_on_relative_selector_list( - selectors, + .unwrap_or_else(|| selectors.clone()), + ) + }, + Is(ref selectors) => { + Is(replace_parent_on_selector_list( + selectors.slice(), parent, &mut specificity, &mut flags, + /* propagate_specificity = */ true, SelectorFlags::for_nesting(), ) - .into_boxed_slice()), - - Host(Some(ref selector)) => Host(Some(replace_parent_on_selector( - selector, - parent, - &mut specificity, - &mut flags, - SelectorFlags::for_nesting() - SelectorFlags::HAS_NON_FEATURELESS_COMPONENT, - ))), - NthOf(ref data) => { - let selectors = replace_parent_on_selector_list( - data.selectors(), + .unwrap_or_else(|| selectors.clone())) + }, + Where(ref selectors) => { + Where( + replace_parent_on_selector_list( + selectors.slice(), parent, &mut specificity, &mut flags, - /* propagate_specificity = */ true, + /* propagate_specificity = */ false, SelectorFlags::for_nesting(), - ); - NthOf(match selectors { - Some(s) => { - NthOfSelectorData::new(data.nth_data(), s.slice().iter().cloned()) - }, - None => data.clone(), - }) - }, - Slotted(ref selector) => Slotted(replace_parent_on_selector( - selector, + ) + .unwrap_or_else(|| selectors.clone()), + ) + }, + Has(ref selectors) => Has(replace_parent_on_relative_selector_list( + selectors, + parent, + &mut specificity, + &mut flags, + SelectorFlags::for_nesting(), + ) + .into_boxed_slice()), + + Host(Some(ref selector)) => Host(Some(replace_parent_on_selector( + selector, + parent, + &mut specificity, + &mut flags, + SelectorFlags::for_nesting() - SelectorFlags::HAS_NON_FEATURELESS_COMPONENT, + ))), + NthOf(ref data) => { + let selectors = replace_parent_on_selector_list( + data.selectors(), parent, &mut specificity, &mut flags, + /* propagate_specificity = */ true, SelectorFlags::for_nesting(), - )), - } - }); - UniqueArc::from_header_and_iter(Default::default(), iter) - }; + ); + NthOf(match selectors { + Some(s) => { + NthOfSelectorData::new(data.nth_data(), s.slice().iter().cloned()) + }, + None => data.clone(), + }) + }, + Slotted(ref selector) => Slotted(replace_parent_on_selector( + selector, + parent, + &mut specificity, + &mut flags, + SelectorFlags::for_nesting(), + )), + } + }); + let mut items = UniqueArc::from_header_and_iter(Default::default(), iter); *items.header_mut() = SpecificityAndFlags { specificity: specificity.into(), flags, @@ -2602,9 +2608,14 @@ where // combinator. builder.push_combinator(combinator.unwrap_or(Combinator::Descendant)); }, - ParseRelative::ForNesting => { + ParseRelative::ForNesting | ParseRelative::ForScope => { if let Ok(combinator) = combinator { - builder.push_simple_selector(Component::ParentSelector); + let selector = match parse_relative { + ParseRelative::ForHas | ParseRelative::No => unreachable!(), + ParseRelative::ForNesting => Component::ParentSelector, + ParseRelative::ForScope => Component::Scope, + }; + builder.push_simple_selector(selector); builder.push_combinator(combinator); } }, @@ -2643,7 +2654,7 @@ where builder.push_combinator(combinator); } - return Ok(Selector(builder.build())); + return Ok(Selector(builder.build(parse_relative))); } fn try_parse_combinator<'i, 't, P, Impl>(input: &mut CssParser<'i, 't>) -> Result { @@ -4375,7 +4386,7 @@ pub mod tests { parse("#foo:has(:is(.bar, div .baz).bar)").unwrap() ); - let child = parse("#foo").unwrap(); + let child = parse_relative_expected("#foo", ParseRelative::ForNesting, Some("& #foo")).unwrap(); assert_eq!( child.replace_parent_selector(&parent), parse(":is(.bar, div .baz) #foo").unwrap() diff --git a/servo/components/selectors/tree.rs b/servo/components/selectors/tree.rs index c1ea8ff5ae..1c440a124d 100644 --- a/servo/components/selectors/tree.rs +++ b/servo/components/selectors/tree.rs @@ -134,6 +134,11 @@ pub trait Element: Sized + Clone + Debug { case_sensitivity: CaseSensitivity, ) -> bool; + fn has_custom_state( + &self, + name: &::Identifier, + ) -> bool; + /// Returns the mapping from the `exportparts` attribute in the reverse /// direction, that is, in an outer-tree -> inner-tree direction. fn imported_part( -- cgit v1.2.3