servo: Merge #19113 - Reland #19108, because it was backed out before its Gecko-side patches could land (from emilio:qsa); r=xidorn,bz
authorEmilio Cobos Álvarez <emilio@crisal.io>
Sat, 04 Nov 2017 05:36:17 -0500
changeset 443448 6c3451eba82a6ba28226c328d6cc0451c9494f74
parent 443447 be1d69e97c5a7d389348ae92ab7361109f23cd8c
child 443449 2d930b3c9a7eecf49a4864d6ab2929fcdf1b25c9
push id1618
push userCallek@gmail.com
push dateThu, 11 Jan 2018 17:45:48 +0000
treeherdermozilla-release@882ca853e05a [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersxidorn, bz
milestone58.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 #19113 - Reland #19108, because it was backed out before its Gecko-side patches could land (from emilio:qsa); r=xidorn,bz Source-Repo: https://github.com/servo/servo Source-Revision: 0f5325d0a7e9b3039c7d5b5f9de5cd2511207d9a
servo/components/layout_thread/dom_wrapper.rs
servo/components/selectors/matching.rs
servo/components/style/dom.rs
servo/components/style/dom_apis.rs
servo/components/style/gecko/generated/bindings.rs
servo/components/style/gecko/wrapper.rs
servo/components/style/invalidation/element/invalidator.rs
servo/ports/geckolib/glue.rs
--- a/servo/components/layout_thread/dom_wrapper.rs
+++ b/servo/components/layout_thread/dom_wrapper.rs
@@ -208,16 +208,20 @@ impl<'ln> TNode for ServoLayoutNode<'ln>
     fn as_document(&self) -> Option<ServoLayoutDocument<'ln>> {
         self.node.downcast().map(ServoLayoutDocument::from_layout_js)
     }
 
     fn can_be_fragmented(&self) -> bool {
         unsafe { self.node.get_flag(NodeFlags::CAN_BE_FRAGMENTED) }
     }
 
+    fn is_in_document(&self) -> bool {
+        unsafe { self.node.get_flag(NodeFlags::IS_IN_DOC) }
+    }
+
     unsafe fn set_can_be_fragmented(&self, value: bool) {
         self.node.set_flag(NodeFlags::CAN_BE_FRAGMENTED, value)
     }
 }
 
 impl<'ln> LayoutNode for ServoLayoutNode<'ln> {
     type ConcreteThreadSafeLayoutNode = ServoThreadSafeLayoutNode<'ln>;
 
@@ -412,17 +416,17 @@ impl<'le> TElement for ServoLayoutElemen
         unsafe { self.as_node().node.get_flag(NodeFlags::HANDLED_SNAPSHOT) }
     }
 
     unsafe fn set_handled_snapshot(&self) {
         self.as_node().node.set_flag(NodeFlags::HANDLED_SNAPSHOT, true);
     }
 
     unsafe fn set_dirty_descendants(&self) {
-        debug_assert!(self.as_node().node.get_flag(NodeFlags::IS_IN_DOC));
+        debug_assert!(self.as_node().is_in_document());
         self.as_node().node.set_flag(NodeFlags::HAS_DIRTY_DESCENDANTS, true)
     }
 
     unsafe fn unset_dirty_descendants(&self) {
         self.as_node().node.set_flag(NodeFlags::HAS_DIRTY_DESCENDANTS, false)
     }
 
     fn store_children_to_process(&self, n: isize) {
--- a/servo/components/selectors/matching.rs
+++ b/servo/components/selectors/matching.rs
@@ -57,16 +57,17 @@ impl ElementSelectorFlags {
 }
 
 /// Holds per-compound-selector data.
 struct LocalMatchingContext<'a, 'b: 'a, Impl: SelectorImpl> {
     shared: &'a mut MatchingContext<'b, Impl>,
     matches_hover_and_active_quirk: bool,
 }
 
+#[inline(always)]
 pub fn matches_selector_list<E>(
     selector_list: &SelectorList<E::Impl>,
     element: &E,
     context: &mut MatchingContext<E::Impl>,
 ) -> bool
 where
     E: Element
 {
@@ -368,30 +369,31 @@ where
 
         from_offset += 1;
     }
 
     CompoundSelectorMatchingResult::FullyMatched
 }
 
 /// Matches a complex selector.
+#[inline(always)]
 pub fn matches_complex_selector<E, F>(
     mut iter: SelectorIter<E::Impl>,
     element: &E,
     context: &mut MatchingContext<E::Impl>,
     flags_setter: &mut F,
 ) -> bool
 where
     E: Element,
     F: FnMut(&E, ElementSelectorFlags),
 {
     // If this is the special pseudo-element mode, consume the ::pseudo-element
     // before proceeding, since the caller has already handled that part.
-    if context.nesting_level == 0 &&
-        context.matching_mode == MatchingMode::ForStatelessPseudoElement {
+    if context.matching_mode == MatchingMode::ForStatelessPseudoElement &&
+        context.nesting_level == 0 {
         // Consume the pseudo.
         match *iter.next().unwrap() {
             Component::PseudoElement(ref pseudo) => {
                 if let Some(ref f) = context.pseudo_element_matching_fn {
                     if !f(pseudo) {
                         return false;
                     }
                 }
@@ -566,22 +568,22 @@ where
     };
 
     let candidate_not_found = match combinator {
         Combinator::NextSibling |
         Combinator::LaterSibling => {
             // Only ancestor combinators are allowed while looking for
             // relevant links, so switch to not looking.
             *relevant_link = RelevantLinkStatus::NotLooking;
-             SelectorMatchingResult::NotMatchedAndRestartFromClosestDescendant
+            SelectorMatchingResult::NotMatchedAndRestartFromClosestDescendant
         }
         Combinator::Child |
         Combinator::Descendant |
         Combinator::PseudoElement => {
-             SelectorMatchingResult::NotMatchedGlobally
+            SelectorMatchingResult::NotMatchedGlobally
         }
     };
 
     let mut next_element = next_element_for_combinator(element, combinator);
 
     loop {
         let element = match next_element {
             None => return candidate_not_found,
--- a/servo/components/style/dom.rs
+++ b/servo/components/style/dom.rs
@@ -117,16 +117,17 @@ pub struct DomDescendants<N> {
 }
 
 impl<N> Iterator for DomDescendants<N>
 where
     N: TNode
 {
     type Item = N;
 
+    #[inline]
     fn next(&mut self) -> Option<N> {
         let prev = match self.previous.take() {
             None => return None,
             Some(n) => n,
         };
 
         self.previous = prev.next_in_preorder(Some(self.scope));
         self.previous
@@ -141,16 +142,28 @@ pub trait TDocument : Sized + Copy + Clo
     /// Get this document as a `TNode`.
     fn as_node(&self) -> Self::ConcreteNode;
 
     /// Returns whether this document is an HTML document.
     fn is_html_document(&self) -> bool;
 
     /// Returns the quirks mode of this document.
     fn quirks_mode(&self) -> QuirksMode;
+
+    /// Get a list of elements with a given ID in this document, sorted by
+    /// document position.
+    ///
+    /// Can return an error to signal that this list is not available, or also
+    /// return an empty slice.
+    fn elements_with_id(
+        &self,
+        _id: &Atom,
+    ) -> Result<&[<Self::ConcreteNode as TNode>::ConcreteElement], ()> {
+        Err(())
+    }
 }
 
 /// The `TNode` trait. This is the main generic trait over which the style
 /// system can be implemented.
 pub trait TNode : Sized + Copy + Clone + Debug + NodeInfo + PartialEq {
     /// The concrete `TElement` type.
     type ConcreteElement: TElement<ConcreteNode = Self>;
 
@@ -175,26 +188,30 @@ pub trait TNode : Sized + Copy + Clone +
     /// Get the owner document of this node.
     fn owner_doc(&self) -> Self::ConcreteDocument;
 
     /// Iterate over the DOM children of a node.
     fn dom_children(&self) -> DomChildren<Self> {
         DomChildren(self.first_child())
     }
 
+    /// Returns whether the node is attached to a document.
+    fn is_in_document(&self) -> bool;
+
     /// Iterate over the DOM children of a node, in preorder.
     fn dom_descendants(&self) -> DomDescendants<Self> {
         DomDescendants {
             previous: Some(*self),
             scope: *self,
         }
     }
 
     /// Returns the next children in pre-order, optionally scoped to a subtree
     /// root.
+    #[inline]
     fn next_in_preorder(&self, scoped_to: Option<Self>) -> Option<Self> {
         if let Some(c) = self.first_child() {
             return Some(c);
         }
 
         if Some(*self) == scoped_to {
             return None;
         }
--- a/servo/components/style/dom_apis.rs
+++ b/servo/components/style/dom_apis.rs
@@ -1,21 +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/. */
 
 //! Generic implementations of some DOM APIs so they can be shared between Servo
 //! and Gecko.
 
+use Atom;
 use context::QuirksMode;
 use dom::{TDocument, TElement, TNode};
 use invalidation::element::invalidator::{Invalidation, InvalidationProcessor, InvalidationVector};
 use selectors::{Element, NthIndexCache, SelectorList};
+use selectors::attr::CaseSensitivity;
 use selectors::matching::{self, MatchingContext, MatchingMode};
+use selectors::parser::{Combinator, Component, LocalName};
 use smallvec::SmallVec;
+use std::borrow::Borrow;
 
 /// <https://dom.spec.whatwg.org/#dom-element-matches>
 pub fn element_matches<E>(
     element: &E,
     selector_list: &SelectorList<E::Impl>,
     quirks_mode: QuirksMode,
 ) -> bool
 where
@@ -213,60 +217,132 @@ where
 
         Q::append_element(results, element);
         if Q::should_stop_after_first_match() {
             return;
         }
     }
 }
 
-/// Fast paths for a given selector query.
+/// Returns whether a given element is descendant of a given `root` node.
 ///
-/// FIXME(emilio, nbp): This may very well be a good candidate for code to be
-/// replaced by HolyJit :)
-fn query_selector_fast<E, Q>(
+/// NOTE(emilio): if root == element, this returns false.
+fn element_is_descendant_of<E>(element: E, root: E::ConcreteNode) -> bool
+where
+    E: TElement,
+{
+    if element.as_node().is_in_document() && root == root.owner_doc().as_node() {
+        return true;
+    }
+
+    let mut current = element.as_node().parent_node();
+    while let Some(n) = current.take() {
+        if n == root {
+            return true;
+        }
+
+        current = n.parent_node();
+    }
+    false
+}
+
+/// Fast path for iterating over every element with a given id in the document
+/// that `root` is connected to.
+fn fast_connected_elements_with_id<'a, D>(
+    doc: &'a D,
+    root: D::ConcreteNode,
+    id: &Atom,
+    quirks_mode: QuirksMode,
+) -> Result<&'a [<D::ConcreteNode as TNode>::ConcreteElement], ()>
+where
+    D: TDocument,
+{
+    debug_assert_eq!(root.owner_doc().as_node(), doc.as_node());
+
+    let case_sensitivity = quirks_mode.classes_and_ids_case_sensitivity();
+    if case_sensitivity != CaseSensitivity::CaseSensitive {
+        return Err(());
+    }
+
+    if !root.is_in_document() {
+        return Err(());
+    }
+
+    doc.elements_with_id(id)
+}
+
+/// Collects elements with a given id under `root`, that pass `filter`.
+fn collect_elements_with_id<E, Q, F>(
     root: E::ConcreteNode,
-    selector_list: &SelectorList<E::Impl>,
+    id: &Atom,
+    results: &mut Q::Output,
+    quirks_mode: QuirksMode,
+    mut filter: F,
+)
+where
+    E: TElement,
+    Q: SelectorQuery<E>,
+    F: FnMut(E) -> bool,
+{
+    let doc = root.owner_doc();
+    let elements = match fast_connected_elements_with_id(&doc, root, id, quirks_mode) {
+        Ok(elements) => elements,
+        Err(()) => {
+            let case_sensitivity =
+                quirks_mode.classes_and_ids_case_sensitivity();
+
+            collect_all_elements::<E, Q, _>(root, results, |e| {
+                e.has_id(id, case_sensitivity) && filter(e)
+            });
+
+            return;
+        }
+    };
+
+    for element in elements {
+        // If the element is not an actual descendant of the root, even though
+        // it's connected, we don't really care about it.
+        if !element_is_descendant_of(*element, root) {
+            continue;
+        }
+
+        if !filter(*element) {
+            continue;
+        }
+
+        Q::append_element(results, *element);
+        if Q::should_stop_after_first_match() {
+            break;
+        }
+    }
+}
+
+/// Fast paths for querySelector with a single simple selector.
+fn query_selector_single_query<E, Q>(
+    root: E::ConcreteNode,
+    component: &Component<E::Impl>,
     results: &mut Q::Output,
     quirks_mode: QuirksMode,
 ) -> Result<(), ()>
 where
     E: TElement,
     Q: SelectorQuery<E>,
 {
-    use selectors::parser::{Component, LocalName};
-    use std::borrow::Borrow;
-
-    // We need to return elements in document order, and reordering them
-    // afterwards is kinda silly.
-    if selector_list.0.len() > 1 {
-        return Err(());
-    }
-
-    let selector = &selector_list.0[0];
-
-    // Let's just care about the easy cases for now.
-    //
-    // FIXME(emilio): Blink has a fast path for classes in ancestor combinators
-    // that may be worth stealing.
-    if selector.len() > 1 {
-        return Err(());
-    }
-
-    let component = selector.iter().next().unwrap();
     match *component {
         Component::ExplicitUniversalType => {
             collect_all_elements::<E, Q, _>(root, results, |_| true)
         }
         Component::ID(ref id) => {
-            // TODO(emilio): We may want to reuse Gecko's document ID table.
-            let case_sensitivity = quirks_mode.classes_and_ids_case_sensitivity();
-            collect_all_elements::<E, Q, _>(root, results, |element| {
-                element.has_id(id, case_sensitivity)
-            })
+            collect_elements_with_id::<E, Q, _>(
+                root,
+                id,
+                results,
+                quirks_mode,
+                |_| true,
+            );
         }
         Component::Class(ref class) => {
             let case_sensitivity = quirks_mode.classes_and_ids_case_sensitivity();
             collect_all_elements::<E, Q, _>(root, results, |element| {
                 element.has_class(class, case_sensitivity)
             })
         }
         Component::LocalName(LocalName { ref name, ref lower_name }) => {
@@ -282,77 +358,226 @@ where
         _ => {
             return Err(())
         }
     }
 
     Ok(())
 }
 
+/// Fast paths for a given selector query.
+///
+/// FIXME(emilio, nbp): This may very well be a good candidate for code to be
+/// replaced by HolyJit :)
+fn query_selector_fast<E, Q>(
+    root: E::ConcreteNode,
+    selector_list: &SelectorList<E::Impl>,
+    results: &mut Q::Output,
+    matching_context: &mut MatchingContext<E::Impl>,
+) -> Result<(), ()>
+where
+    E: TElement,
+    Q: SelectorQuery<E>,
+{
+    // We need to return elements in document order, and reordering them
+    // afterwards is kinda silly.
+    if selector_list.0.len() > 1 {
+        return Err(());
+    }
+
+    let selector = &selector_list.0[0];
+    let quirks_mode = matching_context.quirks_mode();
+
+    // Let's just care about the easy cases for now.
+    if selector.len() == 1 {
+        return query_selector_single_query::<E, Q>(
+            root,
+            selector.iter().next().unwrap(),
+            results,
+            quirks_mode,
+        );
+    }
+
+    let mut iter = selector.iter();
+    let mut combinator: Option<Combinator> = None;
+
+    loop {
+        debug_assert!(combinator.map_or(true, |c| !c.is_sibling()));
+
+        'component_loop: for component in &mut iter {
+            match *component {
+                Component::ID(ref id) => {
+                    if combinator.is_none() {
+                        // In the rightmost compound, just find descendants of
+                        // root that match the selector list with that id.
+                        collect_elements_with_id::<E, Q, _>(
+                            root,
+                            id,
+                            results,
+                            quirks_mode,
+                            |e| {
+                                matching::matches_selector_list(
+                                    selector_list,
+                                    &e,
+                                    matching_context,
+                                )
+                            }
+                        );
+
+                        return Ok(());
+                    }
+
+                    let doc = root.owner_doc();
+                    let elements =
+                        fast_connected_elements_with_id(&doc, root, id, quirks_mode)?;
+
+                    if elements.is_empty() {
+                        return Ok(());
+                    }
+
+                    // Results need to be in document order. Let's not bother
+                    // reordering or deduplicating nodes, which we would need to
+                    // do if one element with the given id were a descendant of
+                    // another element with that given id.
+                    if !Q::should_stop_after_first_match() && elements.len() > 1 {
+                        continue;
+                    }
+
+                    for element in elements {
+                        // If the element is not a descendant of the root, then
+                        // it may have descendants that match our selector that
+                        // _are_ descendants of the root, and other descendants
+                        // that match our selector that are _not_.
+                        //
+                        // So we can't just walk over the element's descendants
+                        // and match the selector against all of them, nor can
+                        // we skip looking at this element's descendants.
+                        //
+                        // Give up on trying to optimize based on this id and
+                        // keep walking our selector.
+                        if !element_is_descendant_of(*element, root) {
+                            continue 'component_loop;
+                        }
+
+                        query_selector_slow::<E, Q>(
+                            element.as_node(),
+                            selector_list,
+                            results,
+                            matching_context,
+                        );
+
+                        if Q::should_stop_after_first_match() && !Q::is_empty(&results) {
+                            break;
+                        }
+                    }
+
+                    return Ok(());
+                }
+                _ => {},
+            }
+        }
+
+        loop {
+            let next_combinator = match iter.next_sequence() {
+                None => return Err(()),
+                Some(c) => c,
+            };
+
+            // We don't want to scan stuff affected by sibling combinators,
+            // given we scan the subtree of elements with a given id (and we
+            // don't want to care about scanning the siblings' subtrees).
+            if next_combinator.is_sibling() {
+                // Advance to the next combinator.
+                for _ in &mut iter {}
+                continue;
+            }
+
+            combinator = Some(next_combinator);
+            break;
+        }
+    }
+}
+
 // Slow path for a given selector query.
 fn query_selector_slow<E, Q>(
     root: E::ConcreteNode,
     selector_list: &SelectorList<E::Impl>,
     results: &mut Q::Output,
     matching_context: &mut MatchingContext<E::Impl>,
 )
 where
     E: TElement,
     Q: SelectorQuery<E>,
 {
     collect_all_elements::<E, Q, _>(root, results, |element| {
         matching::matches_selector_list(selector_list, &element, matching_context)
     });
 }
 
+/// Whether the invalidation machinery should be used for this query.
+#[derive(PartialEq)]
+pub enum MayUseInvalidation {
+    /// We may use it if we deem it useful.
+    Yes,
+    /// Don't use it.
+    No,
+}
+
 /// <https://dom.spec.whatwg.org/#dom-parentnode-queryselector>
 pub fn query_selector<E, Q>(
     root: E::ConcreteNode,
     selector_list: &SelectorList<E::Impl>,
     results: &mut Q::Output,
+    may_use_invalidation: MayUseInvalidation,
 )
 where
     E: TElement,
     Q: SelectorQuery<E>,
 {
     use invalidation::element::invalidator::TreeStyleInvalidator;
 
     let quirks_mode = root.owner_doc().quirks_mode();
-    let fast_result = query_selector_fast::<E, Q>(
-        root,
-        selector_list,
-        results,
-        quirks_mode,
-    );
 
-    if fast_result.is_ok() {
-        return;
-    }
-
-    // Slow path: Use the invalidation machinery if we're a root, and tree
-    // traversal otherwise.
-    //
-    // See the comment in collect_invalidations to see why only if we're a root.
     let mut nth_index_cache = NthIndexCache::default();
     let mut matching_context = MatchingContext::new(
         MatchingMode::Normal,
         None,
         Some(&mut nth_index_cache),
         quirks_mode,
     );
 
     let root_element = root.as_element();
     matching_context.scope_element = root_element.map(|e| e.opaque());
 
+    let fast_result = query_selector_fast::<E, Q>(
+        root,
+        selector_list,
+        results,
+        &mut matching_context,
+    );
+
+    if fast_result.is_ok() {
+        return;
+    }
+
+    // Slow path: Use the invalidation machinery if we're a root, and tree
+    // traversal otherwise.
+    //
+    // See the comment in collect_invalidations to see why only if we're a root.
+    //
     // The invalidation mechanism is only useful in presence of combinators.
     //
     // We could do that check properly here, though checking the length of the
     // selectors is a good heuristic.
+    //
+    // A selector with a combinator needs to have a length of at least 3: A
+    // simple selector, a combinator, and another simple selector.
     let invalidation_may_be_useful =
-        selector_list.0.iter().any(|s| s.len() > 1);
+        may_use_invalidation == MayUseInvalidation::Yes &&
+        selector_list.0.iter().any(|s| s.len() > 2);
 
     if root_element.is_some() || !invalidation_may_be_useful {
         query_selector_slow::<E, Q>(
             root,
             selector_list,
             results,
             &mut matching_context,
         );
--- a/servo/components/style/gecko/generated/bindings.rs
+++ b/servo/components/style/gecko/generated/bindings.rs
@@ -25,16 +25,17 @@ use gecko_bindings::structs::nsIContent;
 use gecko_bindings::structs::nsIDocument;
 use gecko_bindings::structs::nsIDocument_DocumentTheme;
 use gecko_bindings::structs::nsSimpleContentList;
 use gecko_bindings::structs::RawGeckoAnimationPropertySegment;
 use gecko_bindings::structs::RawGeckoComputedTiming;
 use gecko_bindings::structs::RawGeckoCSSPropertyIDList;
 use gecko_bindings::structs::RawGeckoDocument;
 use gecko_bindings::structs::RawGeckoElement;
+use gecko_bindings::structs::Element;
 use gecko_bindings::structs::RawGeckoKeyframeList;
 use gecko_bindings::structs::RawGeckoPropertyValuePairList;
 use gecko_bindings::structs::RawGeckoComputedKeyframeValuesList;
 use gecko_bindings::structs::RawGeckoFontFaceRuleList;
 use gecko_bindings::structs::RawGeckoNode;
 use gecko_bindings::structs::RawServoAnimationValue;
 use gecko_bindings::structs::RawGeckoServoAnimationValueList;
 use gecko_bindings::structs::RawServoMediaList;
@@ -1205,32 +1206,34 @@ extern "C" {
  pub fn Servo_StyleSet_ResolveForDeclarations ( set : RawServoStyleSetBorrowed , parent_style : ServoStyleContextBorrowedOrNull , declarations : RawServoDeclarationBlockBorrowed , ) -> ServoStyleContextStrong ; 
 } extern "C" {
  pub fn Servo_SelectorList_Parse ( selector_list : * const nsACString , ) -> * mut RawServoSelectorList ; 
 } extern "C" {
  pub fn Servo_SelectorList_Matches ( arg1 : RawGeckoElementBorrowed , arg2 : RawServoSelectorListBorrowed , ) -> bool ; 
 } extern "C" {
  pub fn Servo_SelectorList_Closest ( arg1 : RawGeckoElementBorrowed , arg2 : RawServoSelectorListBorrowed , ) -> * const RawGeckoElement ; 
 } extern "C" {
- pub fn Servo_SelectorList_QueryFirst ( arg1 : RawGeckoNodeBorrowed , arg2 : RawServoSelectorListBorrowed , ) -> * const RawGeckoElement ; 
+ pub fn Servo_SelectorList_QueryFirst ( arg1 : RawGeckoNodeBorrowed , arg2 : RawServoSelectorListBorrowed , may_use_invalidation : bool , ) -> * const RawGeckoElement ; 
 } extern "C" {
- pub fn Servo_SelectorList_QueryAll ( arg1 : RawGeckoNodeBorrowed , arg2 : RawServoSelectorListBorrowed , content_list : * mut nsSimpleContentList , ) ; 
+ pub fn Servo_SelectorList_QueryAll ( arg1 : RawGeckoNodeBorrowed , arg2 : RawServoSelectorListBorrowed , content_list : * mut nsSimpleContentList , may_use_invalidation : bool , ) ; 
 } extern "C" {
  pub fn Servo_StyleSet_AddSizeOfExcludingThis ( malloc_size_of : MallocSizeOf , malloc_enclosing_size_of : MallocSizeOf , sizes : * mut ServoStyleSetSizes , set : RawServoStyleSetBorrowed , ) ; 
 } extern "C" {
  pub fn Servo_UACache_AddSizeOf ( malloc_size_of : MallocSizeOf , malloc_enclosing_size_of : MallocSizeOf , sizes : * mut ServoStyleSetSizes , ) ; 
 } extern "C" {
  pub fn Servo_StyleContext_AddRef ( ctx : ServoStyleContextBorrowed , ) ; 
 } extern "C" {
  pub fn Servo_StyleContext_Release ( ctx : ServoStyleContextBorrowed , ) ; 
 } extern "C" {
  pub fn Servo_StyleSet_MightHaveAttributeDependency ( set : RawServoStyleSetBorrowed , element : RawGeckoElementBorrowed , local_name : * mut nsAtom , ) -> bool ; 
 } extern "C" {
  pub fn Servo_StyleSet_HasStateDependency ( set : RawServoStyleSetBorrowed , element : RawGeckoElementBorrowed , state : u64 , ) -> bool ; 
 } extern "C" {
+ pub fn Servo_StyleSet_HasDocumentStateDependency ( set : RawServoStyleSetBorrowed , state : u64 , ) -> bool ; 
+} extern "C" {
  pub fn Servo_CssRules_ListTypes ( rules : ServoCssRulesBorrowed , result : nsTArrayBorrowed_uintptr_t , ) ; 
 } extern "C" {
  pub fn Servo_CssRules_InsertRule ( rules : ServoCssRulesBorrowed , sheet : RawServoStyleSheetContentsBorrowed , rule : * const nsACString , index : u32 , nested : bool , loader : * mut Loader , gecko_stylesheet : * mut ServoStyleSheet , rule_type : * mut u16 , ) -> nsresult ; 
 } extern "C" {
  pub fn Servo_CssRules_DeleteRule ( rules : ServoCssRulesBorrowed , index : u32 , ) -> nsresult ; 
 } extern "C" {
  pub fn Servo_CssRules_GetStyleRuleAt ( rules : ServoCssRulesBorrowed , index : u32 , line : * mut u32 , column : * mut u32 , ) -> RawServoStyleRuleStrong ; 
 } extern "C" {
@@ -1568,9 +1571,11 @@ extern "C" {
 } extern "C" {
  pub fn Gecko_CreateCSSErrorReporter ( sheet : * mut ServoStyleSheet , loader : * mut Loader , uri : * mut nsIURI , ) -> * mut ErrorReporter ; 
 } extern "C" {
  pub fn Gecko_DestroyCSSErrorReporter ( reporter : * mut ErrorReporter , ) ; 
 } extern "C" {
  pub fn Gecko_ReportUnexpectedCSSError ( reporter : * mut ErrorReporter , message : * const :: std :: os :: raw :: c_char , param : * const :: std :: os :: raw :: c_char , paramLen : u32 , prefix : * const :: std :: os :: raw :: c_char , prefixParam : * const :: std :: os :: raw :: c_char , prefixParamLen : u32 , suffix : * const :: std :: os :: raw :: c_char , source : * const :: std :: os :: raw :: c_char , sourceLen : u32 , lineNumber : u32 , colNumber : u32 , ) ; 
 } extern "C" {
  pub fn Gecko_ContentList_AppendAll ( aContentList : * mut nsSimpleContentList , aElements : * mut * const RawGeckoElement , aLength : usize , ) ; 
+} extern "C" {
+ pub fn Gecko_GetElementsWithId ( aDocument : * const nsIDocument , aId : * mut nsAtom , ) -> * const nsTArray < * mut Element > ; 
 }
\ No newline at end of file
--- a/servo/components/style/gecko/wrapper.rs
+++ b/servo/components/style/gecko/wrapper.rs
@@ -105,16 +105,36 @@ impl<'ld> TDocument for GeckoDocument<'l
 
     fn is_html_document(&self) -> bool {
         self.0.mType == structs::root::nsIDocument_Type::eHTML
     }
 
     fn quirks_mode(&self) -> QuirksMode {
         self.0.mCompatMode.into()
     }
+
+    fn elements_with_id(&self, id: &Atom) -> Result<&[GeckoElement<'ld>], ()> {
+        unsafe {
+            let array = bindings::Gecko_GetElementsWithId(self.0, id.as_ptr());
+            if array.is_null() {
+                return Ok(&[]);
+            }
+
+            let elements: &[*mut RawGeckoElement] = &**array;
+
+            // NOTE(emilio): We rely on the in-memory representation of
+            // GeckoElement<'ld> and *mut RawGeckoElement being the same.
+            #[allow(dead_code)]
+            unsafe fn static_assert() {
+                mem::transmute::<*mut RawGeckoElement, GeckoElement<'static>>(0xbadc0de as *mut _);
+            }
+
+            Ok(mem::transmute(elements))
+        }
+    }
 }
 
 /// A simple wrapper over a non-null Gecko node (`nsINode`) pointer.
 ///
 /// Important: We don't currently refcount the DOM, because the wrapper lifetime
 /// magic guarantees that our LayoutFoo references won't outlive the root, and
 /// we don't mutate any of the references on the Gecko side during restyle.
 ///
@@ -237,16 +257,17 @@ impl<'ln> NodeInfo for GeckoNode<'ln> {
         self.node_info().mInner.mNodeType == TEXT_NODE
     }
 }
 
 impl<'ln> TNode for GeckoNode<'ln> {
     type ConcreteDocument = GeckoDocument<'ln>;
     type ConcreteElement = GeckoElement<'ln>;
 
+    #[inline]
     fn parent_node(&self) -> Option<Self> {
         unsafe { self.0.mParent.as_ref().map(GeckoNode) }
     }
 
     #[inline]
     fn first_child(&self) -> Option<Self> {
         unsafe { self.0.mFirstChild.as_ref().map(GeckoNode::from_content) }
     }
@@ -267,16 +288,21 @@ impl<'ln> TNode for GeckoNode<'ln> {
     }
 
     #[inline]
     fn owner_doc(&self) -> Self::ConcreteDocument {
         debug_assert!(!self.node_info().mDocument.is_null());
         GeckoDocument(unsafe { &*self.node_info().mDocument })
     }
 
+    #[inline]
+    fn is_in_document(&self) -> bool {
+        self.get_bool_flag(nsINode_BooleanFlag::IsInDocument)
+    }
+
     fn traversal_parent(&self) -> Option<GeckoElement<'ln>> {
         self.flattened_tree_parent().and_then(|n| n.as_element())
     }
 
     fn opaque(&self) -> OpaqueNode {
         let ptr: usize = self.0 as *const _ as usize;
         OpaqueNode(ptr)
     }
@@ -1737,65 +1763,71 @@ impl<'le> Hash for GeckoElement<'le> {
     fn hash<H: Hasher>(&self, state: &mut H) {
         (self.0 as *const _).hash(state);
     }
 }
 
 impl<'le> ::selectors::Element for GeckoElement<'le> {
     type Impl = SelectorImpl;
 
+    #[inline]
     fn opaque(&self) -> OpaqueElement {
         OpaqueElement::new(self.0)
     }
 
+    #[inline]
     fn parent_element(&self) -> Option<Self> {
         // FIXME(emilio): This will need to jump across if the parent node is a
         // shadow root to get the shadow host.
         let parent_node = self.as_node().parent_node();
         parent_node.and_then(|n| n.as_element())
     }
 
     fn pseudo_element_originating_element(&self) -> Option<Self> {
         debug_assert!(self.implemented_pseudo_element().is_some());
         self.closest_non_native_anonymous_ancestor()
     }
 
+    #[inline]
     fn first_child_element(&self) -> Option<Self> {
         let mut child = self.as_node().first_child();
         while let Some(child_node) = child {
             if let Some(el) = child_node.as_element() {
                 return Some(el)
             }
             child = child_node.next_sibling();
         }
         None
     }
 
+    #[inline]
     fn last_child_element(&self) -> Option<Self> {
         let mut child = self.as_node().last_child();
         while let Some(child_node) = child {
             if let Some(el) = child_node.as_element() {
                 return Some(el)
             }
             child = child_node.prev_sibling();
         }
         None
     }
 
+    #[inline]
     fn prev_sibling_element(&self) -> Option<Self> {
         let mut sibling = self.as_node().prev_sibling();
         while let Some(sibling_node) = sibling {
             if let Some(el) = sibling_node.as_element() {
                 return Some(el)
             }
             sibling = sibling_node.prev_sibling();
         }
         None
     }
 
+    #[inline]
     fn next_sibling_element(&self) -> Option<Self> {
         let mut sibling = self.as_node().next_sibling();
         while let Some(sibling_node) = sibling {
             if let Some(el) = sibling_node.as_element() {
                 return Some(el)
             }
             sibling = sibling_node.next_sibling();
         }
@@ -1877,22 +1909,24 @@ impl<'le> ::selectors::Element for Gecko
     }
 
     fn is_empty(&self) -> bool {
         !self.as_node().dom_children().any(|child| unsafe {
             Gecko_IsSignificantChild(child.0, true, true)
         })
     }
 
+    #[inline]
     fn get_local_name(&self) -> &WeakAtom {
         unsafe {
             WeakAtom::new(self.as_node().node_info().mInner.mName)
         }
     }
 
+    #[inline]
     fn get_namespace(&self) -> &WeakNamespace {
         unsafe {
             WeakNamespace::new(Gecko_Namespace(self.0))
         }
     }
 
     fn match_non_ts_pseudo_class<F>(
         &self,
@@ -2049,52 +2083,57 @@ impl<'le> ::selectors::Element for Gecko
         }
     }
 
     #[inline]
     fn is_link(&self) -> bool {
         self.get_state().intersects(NonTSPseudoClass::AnyLink.state_flag())
     }
 
+    #[inline]
     fn has_id(&self, id: &Atom, case_sensitivity: CaseSensitivity) -> bool {
         if !self.has_id() {
             return false
         }
 
         unsafe {
             let ptr = bindings::Gecko_AtomAttrValue(self.0, atom!("id").as_ptr());
 
             if ptr.is_null() {
                 false
             } else {
                 case_sensitivity.eq_atom(WeakAtom::new(ptr), id)
             }
         }
     }
 
+    #[inline]
     fn has_class(&self, name: &Atom, case_sensitivity: CaseSensitivity) -> bool {
         if !self.may_have_class() {
             return false;
         }
 
         snapshot_helpers::has_class(self.0,
                                     name,
                                     case_sensitivity,
                                     Gecko_ClassOrClassList)
     }
 
+    #[inline]
     fn is_html_element_in_html_document(&self) -> bool {
         self.is_html_element() &&
         self.as_node().owner_doc().is_html_document()
     }
 
+    #[inline]
     fn ignores_nth_child_selectors(&self) -> bool {
         self.is_root_of_anonymous_subtree()
     }
 
+    #[inline]
     fn blocks_ancestor_combinators(&self) -> bool {
         if !self.is_root_of_anonymous_subtree() {
             return false
         }
 
         match self.parent_element() {
             Some(e) => {
                 // If this element is the shadow root of an use-element shadow
--- a/servo/components/style/invalidation/element/invalidator.rs
+++ b/servo/components/style/invalidation/element/invalidator.rs
@@ -312,17 +312,17 @@ where
         }
 
         any_invalidated
     }
 
     fn invalidate_pseudo_element_or_nac(
         &mut self,
         child: E,
-        invalidations: &InvalidationVector<'b>,
+        invalidations: &[Invalidation<'b>],
     ) -> bool {
         let mut sibling_invalidations = InvalidationVector::new();
 
         let result = self.invalidate_child(
             child,
             invalidations,
             &mut sibling_invalidations
         );
@@ -337,17 +337,17 @@ where
         result
     }
 
     /// Invalidate a child and recurse down invalidating its descendants if
     /// needed.
     fn invalidate_child(
         &mut self,
         child: E,
-        invalidations: &InvalidationVector<'b>,
+        invalidations: &[Invalidation<'b>],
         sibling_invalidations: &mut InvalidationVector<'b>,
     ) -> bool {
         let mut invalidations_for_descendants = InvalidationVector::new();
 
         let mut invalidated_child = false;
         let invalidated_descendants = {
             let mut child_invalidator = TreeStyleInvalidator::new(
                 child,
@@ -384,17 +384,17 @@ where
             self.processor.invalidated_descendants(self.element, child);
         }
 
         invalidated_child || invalidated_descendants
     }
 
     fn invalidate_nac(
         &mut self,
-        invalidations: &InvalidationVector<'b>,
+        invalidations: &[Invalidation<'b>],
     ) -> bool {
         let mut any_nac_root = false;
 
         let element = self.element;
         element.each_anonymous_content_child(|nac| {
             any_nac_root |=
                 self.invalidate_pseudo_element_or_nac(nac, invalidations);
         });
@@ -402,17 +402,17 @@ where
         any_nac_root
     }
 
     // NB: It's important that this operates on DOM children, which is what
     // selector-matching operates on.
     fn invalidate_dom_descendants_of(
         &mut self,
         parent: E::ConcreteNode,
-        invalidations: &InvalidationVector<'b>,
+        invalidations: &[Invalidation<'b>],
     ) -> bool {
         let mut any_descendant = false;
 
         let mut sibling_invalidations = InvalidationVector::new();
         for child in parent.dom_children() {
             // TODO(emilio): We handle <xbl:children> fine, because they appear
             // in selector-matching (note bug 1374247, though).
             //
@@ -436,17 +436,17 @@ where
 
         any_descendant
     }
 
     /// Given a descendant invalidation list, go through the current element's
     /// descendants, and invalidate style on them.
     fn invalidate_descendants(
         &mut self,
-        invalidations: &InvalidationVector<'b>,
+        invalidations: &[Invalidation<'b>],
     ) -> bool {
         if invalidations.is_empty() {
             return false;
         }
 
         debug!("StyleTreeInvalidator::invalidate_descendants({:?})",
                self.element);
         debug!(" > {:?}", invalidations);
@@ -541,17 +541,17 @@ where
 
     /// Process a given invalidation list coming from our parent,
     /// adding to `descendant_invalidations` and `sibling_invalidations` as
     /// needed.
     ///
     /// Returns whether our style was invalidated as a result.
     fn process_descendant_invalidations(
         &mut self,
-        invalidations: &InvalidationVector<'b>,
+        invalidations: &[Invalidation<'b>],
         descendant_invalidations: &mut InvalidationVector<'b>,
         sibling_invalidations: &mut InvalidationVector<'b>,
     ) -> bool {
         let mut invalidated = false;
 
         for invalidation in invalidations {
             let result = self.process_invalidation(
                 invalidation,
--- a/servo/ports/geckolib/glue.rs
+++ b/servo/ports/geckolib/glue.rs
@@ -1688,50 +1688,69 @@ pub unsafe extern "C" fn Servo_SelectorL
         quirks_mode,
     )
 }
 
 #[no_mangle]
 pub unsafe extern "C" fn Servo_SelectorList_QueryFirst(
     node: RawGeckoNodeBorrowed,
     selectors: RawServoSelectorListBorrowed,
+    may_use_invalidation: bool,
 ) -> *const structs::RawGeckoElement {
     use std::borrow::Borrow;
-    use style::dom_apis::{self, QueryFirst};
+    use style::dom_apis::{self, MayUseInvalidation, QueryFirst};
 
     let node = GeckoNode(node);
     let selectors = ::selectors::SelectorList::from_ffi(selectors).borrow();
     let mut result = None;
+
+    let may_use_invalidation =
+        if may_use_invalidation {
+            MayUseInvalidation::Yes
+        } else {
+            MayUseInvalidation::No
+        };
+
     dom_apis::query_selector::<GeckoElement, QueryFirst>(
         node,
         &selectors,
         &mut result,
+        may_use_invalidation,
     );
 
     result.map_or(ptr::null(), |e| e.0)
 }
 
 #[no_mangle]
 pub unsafe extern "C" fn Servo_SelectorList_QueryAll(
     node: RawGeckoNodeBorrowed,
     selectors: RawServoSelectorListBorrowed,
     content_list: *mut structs::nsSimpleContentList,
+    may_use_invalidation: bool,
 ) {
     use smallvec::SmallVec;
     use std::borrow::Borrow;
-    use style::dom_apis::{self, QueryAll};
+    use style::dom_apis::{self, MayUseInvalidation, QueryAll};
 
     let node = GeckoNode(node);
     let selectors = ::selectors::SelectorList::from_ffi(selectors).borrow();
     let mut result = SmallVec::new();
 
+    let may_use_invalidation =
+        if may_use_invalidation {
+            MayUseInvalidation::Yes
+        } else {
+            MayUseInvalidation::No
+        };
+
     dom_apis::query_selector::<GeckoElement, QueryAll>(
         node,
         &selectors,
         &mut result,
+        may_use_invalidation,
     );
 
     if !result.is_empty() {
         // NOTE(emilio): This relies on a slice of GeckoElement having the same
         // memory representation than a slice of element pointers.
         bindings::Gecko_ContentList_AppendAll(
             content_list,
             result.as_ptr() as *mut *const _,