Dirty elements whose selectors are affected by sibling changes

This fixes incremental layout of nodes that match pseudo-class selectors such
as :first-child, :nth-child, :last-child, :first-of-type, etc.

* Fixes #8191
* Fixes #9063
* Fixes #9303
* Fixes #9448

This code is based on the following flags from Gecko:
https://hg.mozilla.org/mozilla-central/file/e1cf617a1f28/dom/base/nsINode.h#l134

3 files changed, 111 insertions, 5 deletions

diff --git a/components/script/dom/bindings/trace.rs b/components/script/dom/bindings/trace.rs
index f892b1f955b..a318ca00cb5 100644
--- a/components/script/dom/bindings/trace.rs
+++ b/components/script/dom/bindings/trace.rs
@@ -79,7 +79,7 @@ use std::mem;
 use std::ops::{Deref, DerefMut};
 use std::rc::Rc;
 use std::sync::Arc;
-use std::sync::atomic::AtomicBool;
+use std::sync::atomic::{AtomicBool, AtomicUsize};
 use std::sync::mpsc::{Receiver, Sender};
 use string_cache::{Atom, Namespace, QualName};
 use style::attr::{AttrIdentifier, AttrValue};
@@ -265,7 +265,7 @@ impl<A: JSTraceable, B: JSTraceable, C: JSTraceable> JSTraceable for (A, B, C) {
     }
 }
 
-no_jsmanaged_fields!(bool, f32, f64, String, Url, AtomicBool, Uuid);
+no_jsmanaged_fields!(bool, f32, f64, String, Url, AtomicBool, AtomicUsize, Uuid);
 no_jsmanaged_fields!(usize, u8, u16, u32, u64);
 no_jsmanaged_fields!(isize, i8, i16, i32, i64);
 no_jsmanaged_fields!(Sender<T>);
diff --git a/components/script/dom/element.rs b/components/script/dom/element.rs
index 3cdf3f6ba43..60ed7338e9e 100644
--- a/components/script/dom/element.rs
+++ b/components/script/dom/element.rs
@@ -54,7 +54,7 @@ use dom::htmltablesectionelement::{HTMLTableSectionElement, HTMLTableSectionElem
 use dom::htmltemplateelement::HTMLTemplateElement;
 use dom::htmltextareaelement::{HTMLTextAreaElement, LayoutHTMLTextAreaElementHelpers};
 use dom::namednodemap::NamedNodeMap;
-use dom::node::{CLICK_IN_PROGRESS, LayoutNodeHelpers, Node};
+use dom::node::{CLICK_IN_PROGRESS, ChildrenMutation, LayoutNodeHelpers, Node};
 use dom::node::{NodeDamage, SEQUENTIALLY_FOCUSABLE, UnbindContext};
 use dom::node::{document_from_node, window_from_node};
 use dom::nodelist::NodeList;
@@ -65,7 +65,8 @@ use html5ever::serialize::SerializeOpts;
 use html5ever::serialize::TraversalScope;
 use html5ever::serialize::TraversalScope::{ChildrenOnly, IncludeNode};
 use html5ever::tree_builder::{LimitedQuirks, NoQuirks, Quirks};
-use selectors::matching::{DeclarationBlock, matches};
+use selectors::matching::{DeclarationBlock, ElementFlags, matches};
+use selectors::matching::{HAS_SLOW_SELECTOR, HAS_EDGE_CHILD_SELECTOR, HAS_SLOW_SELECTOR_LATER_SIBLINGS};
 use selectors::matching::{common_style_affecting_attributes, rare_style_affecting_attributes};
 use selectors::parser::{AttrSelector, NamespaceConstraint, parse_author_origin_selector_list_from_str};
 use smallvec::VecLike;
@@ -75,6 +76,7 @@ use std::cell::{Cell, Ref};
 use std::default::Default;
 use std::mem;
 use std::sync::Arc;
+use std::sync::atomic::{AtomicUsize, Ordering};
 use string_cache::{Atom, Namespace, QualName};
 use style::element_state::*;
 use style::error_reporting::ParseErrorReporter;
@@ -102,6 +104,7 @@ pub struct Element {
     attr_list: MutNullableHeap<JS<NamedNodeMap>>,
     class_list: MutNullableHeap<JS<DOMTokenList>>,
     state: Cell<ElementState>,
+    atomic_flags: AtomicElementFlags,
 }
 
 #[derive(PartialEq, HeapSizeOf)]
@@ -143,6 +146,7 @@ impl Element {
             attr_list: Default::default(),
             class_list: Default::default(),
             state: Cell::new(state),
+            atomic_flags: AtomicElementFlags::new(),
         }
     }
 
@@ -229,8 +233,8 @@ pub trait LayoutElementHelpers {
     fn namespace(&self) -> &Namespace;
     fn get_checked_state_for_layout(&self) -> bool;
     fn get_indeterminate_state_for_layout(&self) -> bool;
-
     fn get_state_for_layout(&self) -> ElementState;
+    fn insert_atomic_flags(&self, flags: ElementFlags);
 }
 
 impl LayoutElementHelpers for LayoutJS<Element> {
@@ -583,6 +587,14 @@ impl LayoutElementHelpers for LayoutJS<Element> {
             (*self.unsafe_get()).state.get()
         }
     }
+
+    #[inline]
+    #[allow(unsafe_code)]
+    fn insert_atomic_flags(&self, flags: ElementFlags) {
+        unsafe {
+            (*self.unsafe_get()).atomic_flags.insert(flags);
+        }
+    }
 }
 
 #[derive(PartialEq, Eq, Copy, Clone, HeapSizeOf)]
@@ -1687,6 +1699,33 @@ impl VirtualMethods for Element {
             doc.unregister_named_element(self, value.clone());
         }
     }
+
+    fn children_changed(&self, mutation: &ChildrenMutation) {
+        if let Some(ref s) = self.super_type() {
+            s.children_changed(mutation);
+        }
+
+        let flags = self.atomic_flags.get();
+        if flags.intersects(HAS_SLOW_SELECTOR) {
+            // All children of this node need to be restyled when any child changes.
+            self.upcast::<Node>().dirty(NodeDamage::OtherNodeDamage);
+        } else {
+            if flags.intersects(HAS_SLOW_SELECTOR_LATER_SIBLINGS) {
+                if let Some(next_child) = mutation.next_child() {
+                    for child in next_child.inclusively_following_siblings() {
+                        if child.is::<Element>() {
+                            child.dirty(NodeDamage::OtherNodeDamage);
+                        }
+                    }
+                }
+            }
+            if flags.intersects(HAS_EDGE_CHILD_SELECTOR) {
+                if let Some(child) = mutation.modified_edge_element() {
+                    child.dirty(NodeDamage::OtherNodeDamage);
+                }
+            }
+        }
+    }
 }
 
 impl<'a> ::selectors::Element for Root<Element> {
@@ -2071,3 +2110,22 @@ impl<'a> AttributeMutation<'a> {
         }
     }
 }
+
+/// Thread-safe wrapper for ElementFlags set during selector matching
+#[derive(JSTraceable, HeapSizeOf)]
+struct AtomicElementFlags(AtomicUsize);
+
+impl AtomicElementFlags {
+    fn new() -> Self {
+        AtomicElementFlags(AtomicUsize::new(0))
+    }
+
+    fn get(&self) -> ElementFlags {
+        ElementFlags::from_bits_truncate(self.0.load(Ordering::Relaxed) as u8)
+    }
+
+    fn insert(&self, flags: ElementFlags) {
+        self.0.fetch_or(flags.bits() as usize, Ordering::Relaxed);
+    }
+}
+
diff --git a/components/script/dom/node.rs b/components/script/dom/node.rs
index c2221408b13..f1ebf6f9965 100644
--- a/components/script/dom/node.rs
+++ b/components/script/dom/node.rs
@@ -2399,6 +2399,54 @@ impl<'a> ChildrenMutation<'a> {
                    -> ChildrenMutation<'a> {
         ChildrenMutation::ReplaceAll { removed: removed, added: added }
     }
+
+    /// Get the child that follows the added or removed children.
+    pub fn next_child(&self) -> Option<&Node> {
+        match *self {
+            ChildrenMutation::Append { .. } => None,
+            ChildrenMutation::Insert { next, .. } => Some(next),
+            ChildrenMutation::Prepend { next, .. } => Some(next),
+            ChildrenMutation::Replace { next, .. } => next,
+            ChildrenMutation::ReplaceAll { .. } => None,
+        }
+    }
+
+    /// If nodes were added or removed at the start or end of a container, return any
+    /// previously-existing child whose ":first-child" or ":last-child" status *may* have changed.
+    ///
+    /// NOTE: This does not check whether the inserted/removed nodes were elements, so in some
+    /// cases it will return a false positive.  This doesn't matter for correctness, because at
+    /// worst the returned element will be restyled unnecessarily.
+    pub fn modified_edge_element(&self) -> Option<Root<Node>> {
+        match *self {
+            // Add/remove at start of container: Return the first following element.
+            ChildrenMutation::Prepend { next, .. } |
+            ChildrenMutation::Replace { prev: None, next: Some(next), .. } => {
+                next.inclusively_following_siblings().filter(|node| node.is::<Element>()).next()
+            }
+            // Add/remove at end of container: Return the last preceding element.
+            ChildrenMutation::Append { prev, .. } |
+            ChildrenMutation::Replace { prev: Some(prev), next: None, .. } => {
+                prev.inclusively_preceding_siblings().filter(|node| node.is::<Element>()).next()
+            }
+            // Insert or replace in the middle:
+            ChildrenMutation::Insert { prev, next, .. } |
+            ChildrenMutation::Replace { prev: Some(prev), next: Some(next), .. } => {
+                if prev.inclusively_preceding_siblings().all(|node| !node.is::<Element>()) {
+                    // Before the first element: Return the first following element.
+                    next.inclusively_following_siblings().filter(|node| node.is::<Element>()).next()
+                } else if next.inclusively_following_siblings().all(|node| !node.is::<Element>()) {
+                    // After the last element: Return the last preceding element.
+                    prev.inclusively_preceding_siblings().filter(|node| node.is::<Element>()).next()
+                } else {
+                    None
+                }
+            }
+
+            ChildrenMutation::Replace { prev: None, next: None, .. } => unreachable!(),
+            ChildrenMutation::ReplaceAll { .. } => None,
+        }
+    }
 }
 
 /// The context of the unbinding from a tree of a node when one of its