style: [css-nesting] Process nested rules at cascade data rebuild

More nesting plumbing. Still does nothing because we don't parse the
nested rules.

Should be trivial to prove this patch doesn't change any behavior so
far, but I want to land it on its own because it can have performance
implications.

This follows the pattern of what we do with other rules like layers and
container conditions, that is, keep the ancestor selectors in a stack,
and poke at the last one in order to replace the ancestor.

This changes the behavior of replace_parent_selector as with the newer
version of the spec, stuff like:

  div {
    .foo {
      stuff
    }
  }

Should work as `div .foo`. A test is added for this case.

Differential Revision: https://phabricator.services.mozilla.com/D176560

4 files changed, 207 insertions, 129 deletions

diff --git a/components/selectors/parser.rs b/components/selectors/parser.rs
index 0ab8a8767db..1649d821b72 100644
--- a/components/selectors/parser.rs
+++ b/components/selectors/parser.rs
@@ -860,11 +860,7 @@ impl<Impl: SelectorImpl> Selector<Impl> {
         Selector(builder.build_with_specificity_and_flags(spec))
     }
 
-    pub fn replace_parent_selector(&self, parent: &[Selector<Impl>]) -> Cow<Self> {
-        if !self.has_parent_selector() {
-            return Cow::Borrowed(self);
-        }
-
+    pub fn replace_parent_selector(&self, parent: &[Selector<Impl>]) -> Self {
         // FIXME(emilio): Shouldn't allow replacing if parent has a pseudo-element selector
         // or what not.
         let flags = self.flags() - SelectorFlags::HAS_PARENT;
@@ -894,7 +890,7 @@ impl<Impl: SelectorImpl> Selector<Impl> {
                         return s.clone();
                     }
                     any = true;
-                    s.replace_parent_selector(parent).into_owned()
+                    s.replace_parent_selector(parent)
                 })
                 .collect();
 
@@ -925,7 +921,7 @@ impl<Impl: SelectorImpl> Selector<Impl> {
                     any = true;
                     RelativeSelector {
                         match_hint: s.match_hint,
-                        selector: s.selector.replace_parent_selector(parent).into_owned(),
+                        selector: s.selector.replace_parent_selector(parent),
                     }
                 })
                 .collect();
@@ -946,108 +942,121 @@ impl<Impl: SelectorImpl> Selector<Impl> {
             parent: &[Selector<Impl>],
             specificity: &mut Specificity,
         ) -> Selector<Impl> {
-            let new_selector = orig.replace_parent_selector(parent);
-            if matches!(new_selector, Cow::Owned(..)) {
-                *specificity += Specificity::from(new_selector.specificity() - orig.specificity());
+            if !orig.has_parent_selector() {
+                return orig.clone();
             }
-            new_selector.into_owned()
+            let new_selector = orig.replace_parent_selector(parent);
+            *specificity += Specificity::from(new_selector.specificity() - orig.specificity());
+            new_selector
         }
 
-        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(..) |
-                RelativeSelectorAnchor => component.clone(),
-                ParentSelector => {
-                    specificity += parent_specificity;
-                    Is(parent.to_vec().into_boxed_slice())
-                },
-                Negation(ref selectors) => {
-                    Negation(
-                        replace_parent_on_selector_list(
+        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 += parent_specificity;
+            let iter = iter
+                .cloned()
+                .chain(std::iter::once(Component::Combinator(Combinator::Descendant)))
+                .chain(std::iter::once(Component::Is(parent.to_vec().into_boxed_slice())));
+            let header = HeaderWithLength::new(specificity_and_flags, len);
+            UniqueArc::from_header_and_iter_with_size(header, 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(..) |
+                    RelativeSelectorAnchor => component.clone(),
+                    ParentSelector => {
+                        specificity += parent_specificity;
+                        Is(parent.to_vec().into_boxed_slice())
+                    },
+                    Negation(ref selectors) => {
+                        Negation(
+                            replace_parent_on_selector_list(
+                                selectors,
+                                parent,
+                                &mut specificity,
+                                /* with_specificity = */ true,
+                            )
+                            .into_boxed_slice(),
+                        )
+                    },
+                    Is(ref selectors) => {
+                        Is(replace_parent_on_selector_list(
                             selectors,
                             parent,
                             &mut specificity,
                             /* with_specificity = */ true,
                         )
-                        .into_boxed_slice(),
-                    )
-                },
-                Is(ref selectors) => {
-                    Is(replace_parent_on_selector_list(
+                        .into_boxed_slice())
+                    },
+                    Where(ref selectors) => {
+                        Where(
+                            replace_parent_on_selector_list(
+                                selectors,
+                                parent,
+                                &mut specificity,
+                                /* with_specificity = */ false,
+                            )
+                            .into_boxed_slice(),
+                        )
+                    },
+                    Has(ref selectors) => Has(replace_parent_on_relative_selector_list(
                         selectors,
                         parent,
                         &mut specificity,
-                        /* with_specificity = */ true,
                     )
-                    .into_boxed_slice())
-                },
-                Where(ref selectors) => {
-                    Where(
-                        replace_parent_on_selector_list(
-                            selectors,
+                    .into_boxed_slice()),
+
+                    Host(Some(ref selector)) => Host(Some(replace_parent_on_selector(
+                        selector,
+                        parent,
+                        &mut specificity,
+                    ))),
+                    NthOf(ref data) => {
+                        let selectors = replace_parent_on_selector_list(
+                            data.selectors(),
                             parent,
                             &mut specificity,
-                            /* with_specificity = */ false,
-                        )
-                        .into_boxed_slice(),
-                    )
-                },
-                Has(ref selectors) => Has(replace_parent_on_relative_selector_list(
-                    selectors,
-                    parent,
-                    &mut specificity,
-                )
-                .into_boxed_slice()),
-
-                Host(Some(ref selector)) => Host(Some(replace_parent_on_selector(
-                    selector,
-                    parent,
-                    &mut specificity,
-                ))),
-                NthOf(ref data) => {
-                    let selectors = replace_parent_on_selector_list(
-                        data.selectors(),
+                            /* with_specificity = */ true,
+                        );
+                        NthOf(NthOfSelectorData::new(
+                            data.nth_data(),
+                            selectors.into_iter(),
+                        ))
+                    },
+                    Slotted(ref selector) => Slotted(replace_parent_on_selector(
+                        selector,
                         parent,
                         &mut specificity,
-                        /* with_specificity = */ true,
-                    );
-                    NthOf(NthOfSelectorData::new(
-                        data.nth_data(),
-                        selectors.into_iter(),
-                    ))
-                },
-                Slotted(ref selector) => Slotted(replace_parent_on_selector(
-                    selector,
-                    parent,
-                    &mut specificity,
-                )),
-            }
-        });
-
-        let header = HeaderWithLength::new(specificity_and_flags, iter.len());
-        let mut items = UniqueArc::from_header_and_iter(header, iter);
+                    )),
+                }
+            });
+            let header = HeaderWithLength::new(specificity_and_flags, iter.len());
+            UniqueArc::from_header_and_iter(header, iter)
+        };
         items.header_mut().specificity = specificity.into();
-        Cow::Owned(Selector(items.shareable_thin()))
+        Selector(items.shareable_thin())
     }
 
     /// Returns count of simple selectors and combinators in the Selector.
@@ -4046,7 +4055,7 @@ pub mod tests {
         assert_eq!(
             SelectorList::from_vec(vec![child.0[0]
                 .replace_parent_selector(&parent.0)
-                .into_owned()]),
+            ]),
             parse("#foo :is(.bar, div .baz).bar").unwrap()
         );
 
@@ -4054,9 +4063,17 @@ pub mod tests {
         assert_eq!(
             SelectorList::from_vec(vec![has_child.0[0]
                 .replace_parent_selector(&parent.0)
-                .into_owned()]),
+                ]),
             parse("#foo:has(:is(.bar, div .baz).bar)").unwrap()
         );
+
+        let child = parse("#foo").unwrap();
+        assert_eq!(
+            SelectorList::from_vec(vec![child.0[0]
+                .replace_parent_selector(&parent.0)
+                ]),
+            parse(":is(.bar, div .baz) #foo").unwrap()
+        );
     }
 
     #[test]
diff --git a/components/servo_arc/lib.rs b/components/servo_arc/lib.rs
index 505d7d51c89..24d79cef68a 100644
--- a/components/servo_arc/lib.rs
+++ b/components/servo_arc/lib.rs
@@ -688,10 +688,16 @@ impl<H, T> Arc<HeaderSlice<H, [T]>> {
     /// then `alloc` must return an allocation that can be dellocated
     /// by calling Box::from_raw::<ArcInner<HeaderSlice<H, T>>> on it.
     #[inline]
-    fn from_header_and_iter_alloc<F, I>(alloc: F, header: H, mut items: I, is_static: bool) -> Self
+    fn from_header_and_iter_alloc<F, I>(
+        alloc: F,
+        header: H,
+        mut items: I,
+        num_items: usize,
+        is_static: bool,
+    ) -> Self
     where
         F: FnOnce(Layout) -> *mut u8,
-        I: Iterator<Item = T> + ExactSizeIterator,
+        I: Iterator<Item = T>,
     {
         assert_ne!(size_of::<T>(), 0, "Need to think about ZST");
 
@@ -699,7 +705,6 @@ impl<H, T> Arc<HeaderSlice<H, [T]>> {
         debug_assert!(inner_align >= align_of::<T>());
 
         // Compute the required size for the allocation.
-        let num_items = items.len();
         let size = {
             // Next, synthesize a totally garbage (but properly aligned) pointer
             // to a sequence of T.
@@ -770,8 +775,7 @@ impl<H, T> Arc<HeaderSlice<H, [T]>> {
                 // We should have consumed the buffer exactly, maybe accounting
                 // for some padding from the alignment.
                 debug_assert!(
-                    (buffer.add(size) as usize - current as *mut u8 as usize) <
-                        inner_align
+                    (buffer.add(size) as usize - current as *mut u8 as usize) < inner_align
                 );
             }
             assert!(
@@ -779,7 +783,6 @@ impl<H, T> Arc<HeaderSlice<H, [T]>> {
                 "ExactSizeIterator under-reported length"
             );
         }
-
         #[cfg(feature = "gecko_refcount_logging")]
         unsafe {
             if !is_static {
@@ -803,12 +806,12 @@ impl<H, T> Arc<HeaderSlice<H, [T]>> {
         }
     }
 
-    /// Creates an Arc for a HeaderSlice using the given header struct and
-    /// iterator to generate the slice. The resulting Arc will be fat.
+    /// Creates an Arc for a HeaderSlice using the given header struct and iterator to generate the
+    /// slice. Panics if num_items doesn't match the number of items.
     #[inline]
-    pub fn from_header_and_iter<I>(header: H, items: I) -> Self
+    pub fn from_header_and_iter_with_size<I>(header: H, items: I, num_items: usize) -> Self
     where
-        I: Iterator<Item = T> + ExactSizeIterator,
+        I: Iterator<Item = T>,
     {
         Arc::from_header_and_iter_alloc(
             |layout| {
@@ -825,12 +828,22 @@ impl<H, T> Arc<HeaderSlice<H, [T]>> {
             },
             header,
             items,
+            num_items,
             /* is_static = */ false,
         )
     }
 
+    /// Creates an Arc for a HeaderSlice using the given header struct and
+    /// iterator to generate the slice. The resulting Arc will be fat.
+    pub fn from_header_and_iter<I>(header: H, items: I) -> Self
+    where
+        I: Iterator<Item = T> + ExactSizeIterator,
+    {
+        let len = items.len();
+        Self::from_header_and_iter_with_size(header, items, len)
+    }
+
     #[inline]
-    #[allow(clippy::uninit_vec)]
     unsafe fn allocate_buffer<W>(size: usize) -> *mut u8 {
         // We use Vec because the underlying allocation machinery isn't
         // available in stable Rust. To avoid alignment issues, we allocate
@@ -857,10 +870,7 @@ pub struct HeaderWithLength<H> {
 impl<H> HeaderWithLength<H> {
     /// Creates a new HeaderWithLength.
     pub fn new(header: H, length: usize) -> Self {
-        HeaderWithLength {
-            header,
-            length,
-        }
+        HeaderWithLength { header, length }
     }
 }
 
@@ -958,9 +968,10 @@ impl<H, T> ThinArc<H, T> {
         F: FnOnce(Layout) -> *mut u8,
         I: Iterator<Item = T> + ExactSizeIterator,
     {
-        let header = HeaderWithLength::new(header, items.len());
+        let len = items.len();
+        let header = HeaderWithLength::new(header, len);
         Arc::into_thin(Arc::from_header_and_iter_alloc(
-            alloc, header, items, /* is_static = */ true,
+            alloc, header, items, len, /* is_static = */ true,
         ))
     }
 
@@ -1057,6 +1068,14 @@ impl<H, T> UniqueArc<HeaderSliceWithLength<H, [T]>> {
         Self(Arc::from_header_and_iter(header, items))
     }
 
+    #[inline]
+    pub fn from_header_and_iter_with_size<I>(header: HeaderWithLength<H>, items: I, num_items: usize) -> Self
+    where
+        I: Iterator<Item = T>,
+    {
+        Self(Arc::from_header_and_iter_with_size(header, items, num_items))
+    }
+
     /// Returns a mutable reference to the header.
     pub fn header_mut(&mut self) -> &mut H {
         // We know this to be uniquely owned
diff --git a/components/style/stylesheets/rules_iterator.rs b/components/style/stylesheets/rules_iterator.rs
index 00c095bb8b8..59736ab09e0 100644
--- a/components/style/stylesheets/rules_iterator.rs
+++ b/components/style/stylesheets/rules_iterator.rs
@@ -63,7 +63,6 @@ where
         *effective = true;
         match *rule {
             CssRule::Namespace(_) |
-            CssRule::Style(_) |
             CssRule::FontFace(_) |
             CssRule::CounterStyle(_) |
             CssRule::Viewport(_) |
@@ -72,6 +71,10 @@ where
             CssRule::LayerStatement(_) |
             CssRule::FontFeatureValues(_) |
             CssRule::FontPaletteValues(_) => None,
+            CssRule::Style(ref style_rule) => {
+                let style_rule = style_rule.read_with(guard);
+                style_rule.rules.as_ref().map(|r| r.read_with(guard).0.iter())
+            },
             CssRule::Import(ref import_rule) => {
                 let import_rule = import_rule.read_with(guard);
                 if !C::process_import(guard, device, quirks_mode, import_rule) {
diff --git a/components/style/stylist.rs b/components/style/stylist.rs
index 5d7551e81b1..ed1765e1ab6 100644
--- a/components/style/stylist.rs
+++ b/components/style/stylist.rs
@@ -49,12 +49,13 @@ use selectors::attr::{CaseSensitivity, NamespaceConstraint};
 use selectors::bloom::BloomFilter;
 use selectors::matching::VisitedHandlingMode;
 use selectors::matching::{matches_selector, MatchingContext, MatchingMode, NeedsSelectorFlags};
-use selectors::parser::{AncestorHashes, Combinator, Component, Selector, SelectorIter};
+use selectors::parser::{AncestorHashes, Combinator, Component, Selector, SelectorList, SelectorIter};
 use selectors::visitor::{SelectorListKind, SelectorVisitor};
 use selectors::NthIndexCache;
 use servo_arc::{Arc, ArcBorrow};
 use smallbitvec::SmallBitVec;
 use smallvec::SmallVec;
+use std::borrow::Cow;
 use std::cmp::Ordering;
 use std::hash::{Hash, Hasher};
 use std::sync::Mutex;
@@ -549,33 +550,39 @@ impl From<StyleRuleInclusion> for RuleInclusion {
     }
 }
 
+type AncestorSelectorList<'a> = Cow<'a, SelectorList<SelectorImpl>>;
+
 /// A struct containing state from ancestor rules like @layer / @import /
-/// @container.
-struct ContainingRuleState {
+/// @container / nesting.
+struct ContainingRuleState<'a> {
     layer_name: LayerName,
     layer_id: LayerId,
     container_condition_id: ContainerConditionId,
+    ancestor_selector_lists: SmallVec<[AncestorSelectorList<'a>; 2]>,
 }
 
-impl Default for ContainingRuleState {
+impl<'a> Default for ContainingRuleState<'a> {
     fn default() -> Self {
         Self {
             layer_name: LayerName::new_empty(),
             layer_id: LayerId::root(),
             container_condition_id: ContainerConditionId::none(),
+            ancestor_selector_lists: Default::default(),
         }
     }
 }
 
 struct SavedContainingRuleState {
+    ancestor_selector_lists_len: usize,
     layer_name_len: usize,
     layer_id: LayerId,
     container_condition_id: ContainerConditionId,
 }
 
-impl ContainingRuleState {
+impl<'a> ContainingRuleState<'a> {
     fn save(&self) -> SavedContainingRuleState {
         SavedContainingRuleState {
+            ancestor_selector_lists_len: self.ancestor_selector_lists.len(),
             layer_name_len: self.layer_name.0.len(),
             layer_id: self.layer_id,
             container_condition_id: self.container_condition_id,
@@ -584,6 +591,8 @@ impl ContainingRuleState {
 
     fn restore(&mut self, saved: &SavedContainingRuleState) {
         debug_assert!(self.layer_name.0.len() >= saved.layer_name_len);
+        debug_assert!(self.ancestor_selector_lists.len() >= saved.ancestor_selector_lists_len);
+        self.ancestor_selector_lists.truncate(saved.ancestor_selector_lists_len);
         self.layer_name.0.truncate(saved.layer_name_len);
         self.layer_id = saved.layer_id;
         self.container_condition_id = saved.container_condition_id;
@@ -2630,15 +2639,15 @@ impl CascadeData {
         }
     }
 
-    fn add_rule_list<S>(
+    fn add_rule_list<'a, S>(
         &mut self,
-        rules: std::slice::Iter<'_, CssRule>,
-        device: &Device,
+        rules: std::slice::Iter<'a, CssRule>,
+        device: &'a Device,
         quirks_mode: QuirksMode,
         stylesheet: &S,
-        guard: &SharedRwLockReadGuard,
+        guard: &'a SharedRwLockReadGuard,
         rebuild_kind: SheetRebuildKind,
-        containing_rule_state: &mut ContainingRuleState,
+        containing_rule_state: &mut ContainingRuleState<'a>,
         mut precomputed_pseudo_element_decls: Option<&mut PrecomputedPseudoElementDeclarations>,
     ) -> Result<(), AllocErr>
     where
@@ -2648,18 +2657,33 @@ impl CascadeData {
             // Handle leaf rules first, as those are by far the most common
             // ones, and are always effective, so we can skip some checks.
             let mut handled = true;
+            let mut selectors_for_nested_rules = None;
             match *rule {
                 CssRule::Style(ref locked) => {
-                    let style_rule = locked.read_with(&guard);
+                    let style_rule = locked.read_with(guard);
                     self.num_declarations += style_rule.block.read_with(&guard).len();
+
+                    let has_nested_rules = style_rule.rules.is_some();
+                    let ancestor_selectors = containing_rule_state.ancestor_selector_lists.last();
+                    if has_nested_rules {
+                        selectors_for_nested_rules = Some(
+                            if ancestor_selectors.is_some() {
+                                Cow::Owned(SelectorList(Default::default()))
+                            } else {
+                                Cow::Borrowed(&style_rule.selectors)
+                            }
+                        );
+                    }
+
                     for selector in &style_rule.selectors.0 {
                         self.num_selectors += 1;
 
                         let pseudo_element = selector.pseudo_element();
-
                         if let Some(pseudo) = pseudo_element {
                             if pseudo.is_precomputed() {
                                 debug_assert!(selector.is_universal());
+                                debug_assert!(ancestor_selectors.is_none());
+                                debug_assert!(!has_nested_rules);
                                 debug_assert_eq!(stylesheet.contents().origin, Origin::UserAgent);
                                 debug_assert_eq!(containing_rule_state.layer_id, LayerId::root());
 
@@ -2681,10 +2705,15 @@ impl CascadeData {
                             }
                         }
 
+                        let selector = match ancestor_selectors {
+                            Some(s) => selector.replace_parent_selector(&s.0),
+                            None => selector.clone(),
+                        };
+
                         let hashes = AncestorHashes::new(&selector, quirks_mode);
 
                         let rule = Rule::new(
-                            selector.clone(),
+                            selector,
                             hashes,
                             locked.clone(),
                             self.rules_source_order,
@@ -2692,8 +2721,12 @@ impl CascadeData {
                             containing_rule_state.container_condition_id,
                         );
 
+                        if let Some(Cow::Owned(ref mut nested_selectors)) = selectors_for_nested_rules {
+                            nested_selectors.0.push(rule.selector.clone())
+                        }
+
                         if rebuild_kind.should_rebuild_invalidation() {
-                            self.invalidation_map.note_selector(selector, quirks_mode)?;
+                            self.invalidation_map.note_selector(&rule.selector, quirks_mode)?;
                             let mut needs_revalidation = false;
                             let mut visitor = StylistSelectorVisitor {
                                 needs_revalidation: &mut needs_revalidation,
@@ -2725,7 +2758,7 @@ impl CascadeData {
                         // Part is special, since given it doesn't have any
                         // selectors inside, it's not worth using a whole
                         // SelectorMap for it.
-                        if let Some(parts) = selector.parts() {
+                        if let Some(parts) = rule.selector.parts() {
                             // ::part() has all semantics, so we just need to
                             // put any of them in the selector map.
                             //
@@ -2745,10 +2778,10 @@ impl CascadeData {
                             // ::slotted(..), since :host::slotted(..) could never
                             // possibly match, as <slot> is not a valid shadow host.
                             let rules =
-                                if selector.is_featureless_host_selector_or_pseudo_element() {
+                                if rule.selector.is_featureless_host_selector_or_pseudo_element() {
                                     self.host_rules
                                         .get_or_insert_with(|| Box::new(Default::default()))
-                                } else if selector.is_slotted() {
+                                } else if rule.selector.is_slotted() {
                                     self.slotted_rules
                                         .get_or_insert_with(|| Box::new(Default::default()))
                                 } else {
@@ -2759,6 +2792,7 @@ impl CascadeData {
                         }
                     }
                     self.rules_source_order += 1;
+                    handled = !has_nested_rules;
                 },
                 CssRule::Keyframes(ref keyframes_rule) => {
                     debug!("Found valid keyframes rule: {:?}", *keyframes_rule);
@@ -2932,6 +2966,11 @@ impl CascadeData {
                         containing_rule_state.restore(&saved_containing_rule_state);
                     }
                 },
+                CssRule::Style(..) => {
+                    if let Some(s) = selectors_for_nested_rules {
+                        containing_rule_state.ancestor_selector_lists.push(s);
+                    }
+                }
                 CssRule::Container(ref lock) => {
                     let container_rule = lock.read_with(guard);
                     let id = ContainerConditionId(self.container_conditions.len() as u16);