servo: Merge #16635 - Too many revalidation selectors (from bholley:too_many_revalidation_selectors); r=emilio
authorBobby Holley <bobbyholley@gmail.com>
Thu, 27 Apr 2017 13:14:01 -0500
changeset 405860 36591b6a2827066ef80351bb3176de7eb8bea52f
parent 405859 dd7a3a0608d7882a03ace1c8d245c0a95fd04c41
child 405861 5a2d5f57d4538291ba3be13fde54b3cb629cf596
push id1490
push usermtabara@mozilla.com
push dateMon, 31 Jul 2017 14:08:16 +0000
treeherdermozilla-release@70e32e6bf15e [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersemilio
milestone55.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
servo: Merge #16635 - Too many revalidation selectors (from bholley:too_many_revalidation_selectors); r=emilio https://bugzilla.mozilla.org/show_bug.cgi?id=1358693 Source-Repo: https://github.com/servo/servo Source-Revision: 2c445169ad7ccf0e4b2be8f1eee2e198c54ee666
servo/components/selectors/parser.rs
servo/components/style/gecko/selector_parser.rs
servo/components/style/restyle_hints.rs
servo/components/style/servo/selector_parser.rs
servo/components/style/stylist.rs
servo/tests/unit/style/stylist.rs
--- a/servo/components/selectors/parser.rs
+++ b/servo/components/selectors/parser.rs
@@ -37,17 +37,21 @@ macro_rules! with_all_bounds {
                 T::from(string)
             } else {
                 T::from(s)
             }
         }
 
         /// This trait allows to define the parser implementation in regards
         /// of pseudo-classes/elements
-        pub trait SelectorImpl: Sized {
+        ///
+        /// NB: We need Clone so that we can derive(Clone) on struct with that
+        /// are parameterized on SelectorImpl. See
+        /// https://github.com/rust-lang/rust/issues/26925
+        pub trait SelectorImpl: Clone + Sized {
             type AttrValue: $($InSelector)*;
             type Identifier: $($InSelector)* + PrecomputedHash;
             type ClassName: $($InSelector)* + PrecomputedHash;
             type LocalName: $($InSelector)* + Borrow<Self::BorrowedLocalName> + PrecomputedHash;
             type NamespaceUrl: $($CommonBounds)* + Default + Borrow<Self::BorrowedNamespaceUrl> + PrecomputedHash;
             type NamespacePrefix: $($InSelector)* + Default;
             type BorrowedNamespaceUrl: ?Sized + Eq;
             type BorrowedLocalName: ?Sized + Eq + Hash;
@@ -160,16 +164,37 @@ impl<Impl: SelectorImpl> SelectorInner<I
         }
 
         SelectorInner {
             complex: c,
             ancestor_hashes: hashes,
         }
     }
 
+    /// Creates a clone of this selector with everything to the left of
+    /// (and including) the rightmost ancestor combinator removed. So
+    /// the selector |span foo > bar + baz| will become |bar + baz|.
+    /// This is used for revalidation selectors in servo.
+    ///
+    /// The bloom filter hashes are copied, even though they correspond to
+    /// parts of the selector that have been stripped out, because they are
+    /// still useful for fast-rejecting the reduced selectors.
+    pub fn slice_to_first_ancestor_combinator(&self) -> Self {
+        let maybe_pos = self.complex.iter_raw()
+                            .position(|s| s.as_combinator()
+                                           .map_or(false, |c| c.is_ancestor()));
+        match maybe_pos {
+            None => self.clone(),
+            Some(index) => SelectorInner {
+                complex: self.complex.slice_to(index),
+                ancestor_hashes: self.ancestor_hashes.clone(),
+            },
+        }
+    }
+
     /// Creates a SelectorInner from a Vec of Components. Used in tests.
     pub fn from_vec(vec: Vec<Component<Impl>>) -> Self {
         let complex = ComplexSelector::from_vec(vec);
         Self::new(complex)
     }
 }
 
 #[derive(PartialEq, Eq, Hash, Clone)]
@@ -310,38 +335,36 @@ impl<Impl: SelectorImpl> ComplexSelector
     /// Returns a ComplexSelector identical to |self| but with the rightmost |index|
     /// entries removed.
     pub fn slice_from(&self, index: usize) -> Self {
         // Note that we convert the slice_from to slice_to because selectors are
         // stored left-to-right but logical order is right-to-left.
         ComplexSelector(self.0.clone().slice_to(self.0.len() - index))
     }
 
+    /// Returns a ComplexSelector identical to |self| but with the leftmost
+    /// |len() - index| entries removed.
+    pub fn slice_to(&self, index: usize) -> Self {
+        // Note that we convert the slice_to to slice_from because selectors are
+        // stored left-to-right but logical order is right-to-left.
+        ComplexSelector(self.0.clone().slice_from(self.0.len() - index))
+    }
+
     /// Creates a ComplexSelector from a vec of Components. Used in tests.
     pub fn from_vec(vec: Vec<Component<Impl>>) -> Self {
         ComplexSelector(ArcSlice::new(vec.into_boxed_slice()))
     }
 }
 
+#[derive(Clone)]
 pub struct SelectorIter<'a, Impl: 'a + SelectorImpl> {
     iter: Rev<slice::Iter<'a, Component<Impl>>>,
     next_combinator: Option<Combinator>,
 }
 
-// NB: Deriving this doesn't work for some reason, because it expects Impl to
-// implement Clone.
-impl<'a, Impl: 'a + SelectorImpl> Clone for SelectorIter<'a, Impl> {
-    fn clone(&self) -> Self {
-        SelectorIter {
-            iter: self.iter.clone(),
-            next_combinator: self.next_combinator.clone(),
-        }
-    }
-}
-
 impl<'a, Impl: 'a + SelectorImpl> SelectorIter<'a, Impl> {
     /// Prepares this iterator to point to the next sequence to the left,
     /// returning the combinator if the sequence was found.
     pub fn next_sequence(&mut self) -> Option<Combinator> {
         self.next_combinator.take()
     }
 }
 
@@ -500,16 +523,24 @@ impl<Impl: SelectorImpl> Component<Impl>
             _ => None,
         }
     }
 
     /// Returns true if this is a combinator.
     pub fn is_combinator(&self) -> bool {
         matches!(*self, Component::Combinator(_))
     }
+
+    /// Returns the value as a combinator if applicable, None otherwise.
+    pub fn as_combinator(&self) -> Option<Combinator> {
+        match *self {
+            Component::Combinator(c) => Some(c),
+            _ => None,
+        }
+    }
 }
 
 #[derive(Eq, PartialEq, Clone, Hash, Copy, Debug)]
 pub enum CaseSensitivity {
     CaseSensitive,  // Selectors spec says language-defined, but HTML says sensitive.
     CaseInsensitive,
 }
 
--- a/servo/components/style/gecko/selector_parser.rs
+++ b/servo/components/style/gecko/selector_parser.rs
@@ -337,16 +337,22 @@ impl NonTSPseudoClass {
                     $(NonTSPseudoClass::$s_name(..) => flag!($s_state),)*
                     NonTSPseudoClass::MozAny(..) => ElementState::empty(),
                 }
             }
         }
         apply_non_ts_list!(pseudo_class_state)
     }
 
+    /// Returns true if the given pseudoclass should trigger style sharing cache revalidation.
+    pub fn needs_cache_revalidation(&self) -> bool {
+        self.state_flag().is_empty() &&
+        !matches!(*self, NonTSPseudoClass::MozAny(_))
+    }
+
     /// Convert NonTSPseudoClass to Gecko's CSSPseudoClassType.
     pub fn to_gecko_pseudoclasstype(&self) -> Option<CSSPseudoClassType> {
         macro_rules! gecko_type {
             (_) => (None);
             ($gecko_type:ident) =>
                 (Some(::gecko_bindings::structs::CSSPseudoClassType::$gecko_type));
         }
         macro_rules! pseudo_class_geckotype {
--- a/servo/components/style/restyle_hints.rs
+++ b/servo/components/style/restyle_hints.rs
@@ -412,42 +412,16 @@ fn is_attr_selector(sel: &Component<Sele
         Component::AttrDashMatch(_, _) |
         Component::AttrPrefixMatch(_, _) |
         Component::AttrSubstringMatch(_, _) |
         Component::AttrSuffixMatch(_, _) => true,
         _ => false,
     }
 }
 
-/// Whether a selector containing this simple selector needs to be explicitly
-/// matched against both the style sharing cache entry and the candidate.
-///
-///
-/// We use this for selectors that can have different matching behavior between
-/// siblings that are otherwise identical as far as the cache is concerned.
-fn needs_cache_revalidation(sel: &Component<SelectorImpl>) -> bool {
-    match *sel {
-        Component::Empty |
-        Component::FirstChild |
-        Component::LastChild |
-        Component::OnlyChild |
-        Component::NthChild(..) |
-        Component::NthLastChild(..) |
-        Component::NthOfType(..) |
-        Component::NthLastOfType(..) |
-        Component::FirstOfType |
-        Component::LastOfType |
-        Component::OnlyOfType => true,
-        // FIXME(emilio): This sets the "revalidation" flag for :any, which is
-        // probably expensive given we use it a lot in UA sheets.
-        Component::NonTSPseudoClass(ref p) => p.state_flag().is_empty(),
-        _ => false,
-    }
-}
-
 fn combinator_to_restyle_hint(combinator: Option<Combinator>) -> RestyleHint {
     match combinator {
         None => RESTYLE_SELF,
         Some(c) => match c {
             Combinator::Child => RESTYLE_DESCENDANTS,
             Combinator::Descendant => RESTYLE_DESCENDANTS,
             Combinator::NextSibling => RESTYLE_LATER_SIBLINGS,
             Combinator::LaterSibling => RESTYLE_LATER_SIBLINGS,
@@ -504,41 +478,34 @@ struct Dependency {
 
 
 /// The following visitor visits all the simple selectors for a given complex
 /// selector, taking care of :not and :any combinators, collecting whether any
 /// of them is sensitive to attribute or state changes.
 struct SensitivitiesVisitor {
     sensitivities: Sensitivities,
     hint: RestyleHint,
-    needs_revalidation: bool,
 }
 
 impl SelectorVisitor for SensitivitiesVisitor {
     type Impl = SelectorImpl;
 
     fn visit_complex_selector(&mut self,
                               _: SelectorIter<SelectorImpl>,
                               combinator: Option<Combinator>) -> bool {
         self.hint |= combinator_to_restyle_hint(combinator);
-        self.needs_revalidation |= self.hint.contains(RESTYLE_LATER_SIBLINGS);
 
         true
     }
 
     fn visit_simple_selector(&mut self, s: &Component<SelectorImpl>) -> bool {
         self.sensitivities.states.insert(selector_to_state(s));
 
         if !self.sensitivities.attrs {
             self.sensitivities.attrs = is_attr_selector(s);
-            self.needs_revalidation = true;
-        }
-
-        if !self.needs_revalidation {
-            self.needs_revalidation = needs_cache_revalidation(s);
         }
 
         true
     }
 }
 
 /// A set of dependencies for a given stylist.
 ///
@@ -565,32 +532,28 @@ impl DependencySet {
             self.common_deps.push(dep)
         } else if affected_by_attribute {
             self.attr_deps.push(dep)
         } else {
             self.state_deps.push(dep)
         }
     }
 
-    /// Adds a selector to this `DependencySet`, and returns whether it may need
-    /// cache revalidation, that is, whether two siblings of the same "shape"
-    /// may have different style due to this selector.
-    pub fn note_selector(&mut self, selector: &Selector<SelectorImpl>) -> bool {
+    /// Adds a selector to this `DependencySet`.
+    pub fn note_selector(&mut self, selector: &Selector<SelectorImpl>) {
         let mut is_pseudo_element = selector.pseudo_element.is_some();
 
         let mut next = Some(selector.inner.complex.clone());
         let mut combinator = None;
-        let mut needs_revalidation = false;
 
         while let Some(current) = next.take() {
             // Set up our visitor.
             let mut visitor = SensitivitiesVisitor {
                 sensitivities: Sensitivities::new(),
                 hint: combinator_to_restyle_hint(combinator),
-                needs_revalidation: false,
             };
 
             if is_pseudo_element {
                 // TODO(emilio): use more fancy restyle hints to avoid restyling
                 // the whole subtree when pseudos change.
                 //
                 // We currently need is_pseudo_element to handle eager pseudos
                 // (so the style the parent stores doesn't become stale), and
@@ -613,28 +576,25 @@ impl DependencySet {
                 // Prepare the next sequence of simple selectors.
                 if let Some(next_combinator) = iter.next_sequence() {
                     next = Some(current.slice_from(index + 1));
                     combinator = Some(next_combinator);
                 }
             }
 
             // Note what we found.
-            needs_revalidation |= visitor.needs_revalidation;
             if !visitor.sensitivities.is_empty() {
                 self.add_dependency(Dependency {
                     sensitivities: visitor.sensitivities,
                     hint: visitor.hint,
                     selector: SelectorInner::new(current),
                 })
             }
 
         }
-
-        needs_revalidation
     }
 
     /// Create an empty `DependencySet`.
     pub fn new() -> Self {
         DependencySet {
             state_deps: vec![],
             attr_deps: vec![],
             common_deps: vec![],
--- a/servo/components/style/servo/selector_parser.rs
+++ b/servo/components/style/servo/selector_parser.rs
@@ -230,16 +230,21 @@ impl NonTSPseudoClass {
 
             AnyLink |
             Lang(_) |
             Link |
             Visited |
             ServoNonZeroBorder => ElementState::empty(),
         }
     }
+
+    /// Returns true if the given pseudoclass should trigger style sharing cache revalidation.
+    pub fn needs_cache_revalidation(&self) -> bool {
+        self.state_flag().is_empty()
+    }
 }
 
 /// The abstract struct we implement the selector parser implementation on top
 /// of.
 #[derive(Clone, Debug, PartialEq)]
 #[cfg_attr(feature = "servo", derive(HeapSizeOf))]
 pub struct SelectorImpl;
 
--- a/servo/components/style/stylist.rs
+++ b/servo/components/style/stylist.rs
@@ -21,17 +21,18 @@ use properties::INHERIT_ALL;
 use properties::PropertyDeclarationBlock;
 use restyle_hints::{RestyleHint, DependencySet};
 use rule_tree::{CascadeLevel, RuleTree, StrongRuleNode, StyleSource};
 use selector_parser::{SelectorImpl, PseudoElement, Snapshot};
 use selectors::Element;
 use selectors::bloom::BloomFilter;
 use selectors::matching::{AFFECTED_BY_STYLE_ATTRIBUTE, AFFECTED_BY_PRESENTATIONAL_HINTS};
 use selectors::matching::{ElementSelectorFlags, StyleRelations, matches_selector};
-use selectors::parser::{Component, Selector, SelectorInner, LocalName as LocalNameSelector};
+use selectors::parser::{Component, Selector, SelectorInner, SelectorMethods, LocalName as LocalNameSelector};
+use selectors::visitor::SelectorVisitor;
 use shared_lock::{Locked, SharedRwLockReadGuard, StylesheetGuards};
 use sink::Push;
 use smallvec::VecLike;
 use std::borrow::Borrow;
 use std::collections::HashMap;
 use std::fmt;
 use std::hash::Hash;
 #[cfg(feature = "servo")]
@@ -109,17 +110,17 @@ pub struct Stylist {
 
     /// Selector dependencies used to compute restyle hints.
     dependencies: DependencySet,
 
     /// Selectors that require explicit cache revalidation (i.e. which depend
     /// on state that is not otherwise visible to the cache, like attributes or
     /// tree-structural state like child index and pseudos).
     #[cfg_attr(feature = "servo", ignore_heap_size_of = "Arc")]
-    selectors_for_cache_revalidation: Vec<Selector<SelectorImpl>>,
+    selectors_for_cache_revalidation: Vec<SelectorInner<SelectorImpl>>,
 
     /// The total number of selectors.
     num_selectors: usize,
 
     /// The total number of declarations.
     num_declarations: usize,
 
     /// The total number of times the stylist has been rebuilt.
@@ -327,20 +328,33 @@ impl Stylist {
                                              selector.inner.clone(),
                                              locked.clone(),
                                              self.rules_source_order,
                                              selector.specificity));
                     }
                     self.rules_source_order += 1;
 
                     for selector in &style_rule.selectors.0 {
-                        let needs_cache_revalidation =
-                            self.dependencies.note_selector(selector);
-                        if needs_cache_revalidation {
-                            self.selectors_for_cache_revalidation.push(selector.clone());
+                        self.dependencies.note_selector(selector);
+
+                        if needs_revalidation(selector) {
+                            // For revalidation, we can skip everything left of the first ancestor
+                            // combinator.
+                            let revalidation_sel = selector.inner.slice_to_first_ancestor_combinator();
+
+                            // Because of the slicing we do above, we can often end up with
+                            // adjacent duplicate selectors when we have selectors like
+                            // body > foo, td > foo, th > foo, etc. Doing a check for
+                            // adjacent duplicates here reduces the number of revalidation
+                            // selectors for Gecko's UA sheet by 30%.
+                            let duplicate = self.selectors_for_cache_revalidation.last()
+                                                .map_or(false, |x| x.complex == revalidation_sel.complex);
+                            if !duplicate {
+                                self.selectors_for_cache_revalidation.push(revalidation_sel);
+                            }
                         }
                     }
                 }
                 CssRule::Import(ref import) => {
                     let import = import.read_with(guard);
                     self.add_stylesheet(&import.stylesheet, guard, extra_data)
                 }
                 CssRule::Keyframes(ref keyframes_rule) => {
@@ -831,17 +845,17 @@ impl Stylist {
         use selectors::matching::StyleRelations;
         use selectors::matching::matches_selector;
 
         let len = self.selectors_for_cache_revalidation.len();
         let mut results = BitVec::from_elem(len, false);
 
         for (i, ref selector) in self.selectors_for_cache_revalidation
                                      .iter().enumerate() {
-            results.set(i, matches_selector(&selector.inner,
+            results.set(i, matches_selector(selector,
                                             element,
                                             Some(bloom),
                                             &mut StyleRelations::empty(),
                                             flags_setter));
         }
 
         results
     }
@@ -897,16 +911,84 @@ impl Drop for Stylist {
         // after this point.
         //
         // TODO(emilio): We can at least assert all the elements in the free
         // list are indeed free.
         unsafe { self.rule_tree.gc(); }
     }
 }
 
+/// Visitor determine whether a selector requires cache revalidation.
+///
+/// Note that we just check simple selectors and eagerly return when the first
+/// need for revalidation is found, so we don't need to store state on the visitor.
+struct RevalidationVisitor;
+
+impl SelectorVisitor for RevalidationVisitor {
+    type Impl = SelectorImpl;
+
+    /// Check whether a rightmost sequence of simple selectors containing this
+    /// simple selector to be explicitly matched against both the style sharing
+    /// cache entry and the candidate.
+    ///
+    /// We use this for selectors that can have different matching behavior between
+    /// siblings that are otherwise identical as far as the cache is concerned.
+    fn visit_simple_selector(&mut self, s: &Component<SelectorImpl>) -> bool {
+        match *s {
+            Component::AttrExists(_) |
+            Component::AttrEqual(_, _, _) |
+            Component::AttrIncludes(_, _) |
+            Component::AttrDashMatch(_, _) |
+            Component::AttrPrefixMatch(_, _) |
+            Component::AttrSubstringMatch(_, _) |
+            Component::AttrSuffixMatch(_, _) |
+            Component::Empty |
+            Component::FirstChild |
+            Component::LastChild |
+            Component::OnlyChild |
+            Component::NthChild(..) |
+            Component::NthLastChild(..) |
+            Component::NthOfType(..) |
+            Component::NthLastOfType(..) |
+            Component::FirstOfType |
+            Component::LastOfType |
+            Component::OnlyOfType => {
+                false
+            },
+            Component::NonTSPseudoClass(ref p) if p.needs_cache_revalidation() => {
+                false
+            },
+            _ => {
+                true
+            }
+        }
+    }
+}
+
+/// Returns true if the given selector needs cache revalidation.
+pub fn needs_revalidation(selector: &Selector<SelectorImpl>) -> bool {
+    let mut visitor = RevalidationVisitor;
+
+    // We only need to consider the rightmost sequence of simple selectors, so
+    // we can stop at the first combinator. This is because:
+    // * If it's an ancestor combinator, we can ignore everything to the left
+    //   because matching won't differ between siblings.
+    // * If it's a sibling combinator, then we know we need revalidation.
+    let mut iter = selector.inner.complex.iter();
+    for ss in &mut iter {
+        if !ss.visit(&mut visitor) {
+            return true;
+        }
+    }
+
+    // If none of the simple selectors in the rightmost sequence required
+    // revalidaiton, we need revalidation if and only if the combinator is
+    // a sibling combinator.
+    iter.next_sequence().map_or(false, |c| c.is_sibling())
+}
 
 /// Map that contains the CSS rules for a specific PseudoElement
 /// (or lack of PseudoElement).
 #[cfg_attr(feature = "servo", derive(HeapSizeOf))]
 struct PerPseudoElementSelectorMap {
     /// Rules from user agent stylesheets
     user_agent: SelectorMap,
     /// Rules from author stylesheets
--- a/servo/tests/unit/style/stylist.rs
+++ b/servo/tests/unit/style/stylist.rs
@@ -1,23 +1,25 @@
 /* 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 http://mozilla.org/MPL/2.0/. */
 
 use html5ever_atoms::LocalName;
 use selectors::parser::LocalName as LocalNameSelector;
+use selectors::parser::Selector;
 use servo_atoms::Atom;
 use std::sync::Arc;
 use style::properties::{PropertyDeclarationBlock, PropertyDeclaration};
 use style::properties::{longhands, Importance};
 use style::rule_tree::CascadeLevel;
-use style::selector_parser::SelectorParser;
+use style::selector_parser::{SelectorImpl, SelectorParser};
 use style::shared_lock::SharedRwLock;
 use style::stylesheets::StyleRule;
 use style::stylist::{Rule, SelectorMap};
+use style::stylist::needs_revalidation;
 use style::thread_state;
 
 /// Helper method to get some Rules from selector strings.
 /// Each sublist of the result contains the Rules for one StyleRule.
 fn get_mock_rules(css_selectors: &[&str]) -> (Vec<Vec<Rule>>, SharedRwLock) {
     let shared_lock = SharedRwLock::new();
     (css_selectors.iter().enumerate().map(|(i, selectors)| {
         let selectors = SelectorParser::parse_author_origin_no_namespace(selectors).unwrap();
@@ -51,16 +53,119 @@ fn get_mock_map(selectors: &[&str]) -> (
         for rule in rules.into_iter() {
             map.insert(rule)
         }
     }
 
     (map, shared_lock)
 }
 
+fn parse_selectors(selectors: &[&str]) -> Vec<Selector<SelectorImpl>> {
+    selectors.iter()
+             .map(|x| SelectorParser::parse_author_origin_no_namespace(x).unwrap().0
+                                                                         .into_iter()
+                                                                         .nth(0)
+                                                                         .unwrap())
+             .collect()
+}
+
+#[test]
+fn test_revalidation_selectors() {
+    let test = parse_selectors(&[
+        // Not revalidation selectors.
+        "div",
+        "#bar",
+        "div:not(.foo)",
+        "div span",
+        "div > span",
+
+        // Attribute selectors.
+        "div[foo]",
+        "div:not([foo])",
+        "div[foo = \"bar\"]",
+        "div[foo ~= \"bar\"]",
+        "div[foo |= \"bar\"]",
+        "div[foo ^= \"bar\"]",
+        "div[foo $= \"bar\"]",
+        "div[foo *= \"bar\"]",
+        "*|div[foo][bar = \"baz\"]",
+
+        // Non-state-based pseudo-classes.
+        "div:empty",
+        "div:first-child",
+        "div:last-child",
+        "div:only-child",
+        "div:nth-child(2)",
+        "div:nth-last-child(2)",
+        "div:nth-of-type(2)",
+        "div:nth-last-of-type(2)",
+        "div:first-of-type",
+        "div:last-of-type",
+        "div:only-of-type",
+
+        // Note: it would be nice to test :moz-any and the various other non-TS
+        // pseudo classes supported by gecko, but we don't have access to those
+        // in these unit tests. :-(
+
+        // Sibling combinators.
+        "span + div",
+        "span ~ div",
+
+        // Revalidation selectors that will get sliced.
+        "td > h1[dir]",
+        "td > span + h1[dir]",
+        "table td > span + div ~ h1[dir]",
+    ]).into_iter()
+      .filter(|s| needs_revalidation(&s))
+      .map(|s| s.inner.slice_to_first_ancestor_combinator().complex)
+      .collect::<Vec<_>>();
+
+    let reference = parse_selectors(&[
+        // Attribute selectors.
+        "div[foo]",
+        "div:not([foo])",
+        "div[foo = \"bar\"]",
+        "div[foo ~= \"bar\"]",
+        "div[foo |= \"bar\"]",
+        "div[foo ^= \"bar\"]",
+        "div[foo $= \"bar\"]",
+        "div[foo *= \"bar\"]",
+        "*|div[foo][bar = \"baz\"]",
+
+        // Non-state-based pseudo-classes.
+        "div:empty",
+        "div:first-child",
+        "div:last-child",
+        "div:only-child",
+        "div:nth-child(2)",
+        "div:nth-last-child(2)",
+        "div:nth-of-type(2)",
+        "div:nth-last-of-type(2)",
+        "div:first-of-type",
+        "div:last-of-type",
+        "div:only-of-type",
+
+        // Sibling combinators.
+        "span + div",
+        "span ~ div",
+
+        // Revalidation selectors that got sliced.
+        "h1[dir]",
+        "span + h1[dir]",
+        "span + div ~ h1[dir]",
+    ]).into_iter()
+      .map(|s| s.inner.complex)
+      .collect::<Vec<_>>();
+
+    assert_eq!(test.len(), reference.len());
+    for (t, r) in test.into_iter().zip(reference.into_iter()) {
+        assert_eq!(t, r)
+    }
+}
+
 #[test]
 fn test_rule_ordering_same_specificity() {
     let (rules_list, _) = get_mock_rules(&["a.intro", "img.sidebar"]);
     let a = &rules_list[0][0];
     let b = &rules_list[1][0];
     assert!((a.specificity(), a.source_order) < ((b.specificity(), b.source_order)),
             "The rule that comes later should win.");
 }