servo: Merge #17078 - stylo: Avoid restyling the whole document when adding stylesheets (from emilio:stylesheet-invalidation-scopes); r=heycam
authorEmilio Cobos Álvarez <emilio@crisal.io>
Mon, 29 May 2017 14:19:16 -0500
changeset 361128 759183f38bbfc001fd0de9a766e222488dd5b5ef
parent 361127 69a878129f887b64a0e9646f3fa9fd5f8942dfdd
child 361129 3deb86de58ce1103d3ec566bcbeee886aafc9cc0
push id31917
push usercbook@mozilla.com
push dateTue, 30 May 2017 09:14:52 +0000
treeherdermozilla-central@0c712d76d598 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersheycam
bugs1357583
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 #17078 - stylo: Avoid restyling the whole document when adding stylesheets (from emilio:stylesheet-invalidation-scopes); r=heycam This is for bug 1357583. Source-Repo: https://github.com/servo/servo Source-Revision: 939716a7bc2ba2fbd8dcfe8b64d2f61edfa99c95
servo/components/style/data.rs
servo/components/style/gecko/data.rs
servo/components/style/gecko/generated/bindings.rs
servo/components/style/invalidation/mod.rs
servo/components/style/lib.rs
servo/components/style/restyle_hints.rs
servo/components/style/stylesheet_set.rs
servo/components/style/stylesheets.rs
servo/components/style/stylist.rs
servo/ports/geckolib/glue.rs
servo/tests/unit/style/media_queries.rs
--- a/servo/components/style/data.rs
+++ b/servo/components/style/data.rs
@@ -383,16 +383,21 @@ impl StoredRestyleHint {
         self.0.is_empty()
     }
 
     /// Insert another restyle hint, effectively resulting in the union of both.
     pub fn insert(&mut self, other: Self) {
         self.0.insert(other.0)
     }
 
+    /// Contains whether the whole subtree is invalid.
+    pub fn contains_subtree(&self) -> bool {
+        self.0.contains(&RestyleHint::subtree())
+    }
+
     /// Insert another restyle hint, effectively resulting in the union of both.
     pub fn insert_from(&mut self, other: &Self) {
         self.0.insert_from(&other.0)
     }
 
     /// Returns true if the hint has animation-only restyle.
     pub fn has_animation_hint(&self) -> bool {
         self.0.has_animation_hint()
--- a/servo/components/style/gecko/data.rs
+++ b/servo/components/style/gecko/data.rs
@@ -1,18 +1,20 @@
 /* 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/. */
 
 //! Data needed to style a Gecko document.
 
 use Atom;
 use atomic_refcell::{AtomicRef, AtomicRefCell, AtomicRefMut};
+use dom::TElement;
 use fnv::FnvHashMap;
 use gecko::rules::{CounterStyleRule, FontFaceRule};
+use gecko::wrapper::GeckoElement;
 use gecko_bindings::bindings::RawServoStyleSet;
 use gecko_bindings::structs::RawGeckoPresContextOwned;
 use gecko_bindings::structs::nsIDocument;
 use gecko_bindings::sugar::ownership::{HasBoxFFI, HasFFI, HasSimpleFFI};
 use media_queries::Device;
 use properties::ComputedValues;
 use shared_lock::{Locked, StylesheetGuards, SharedRwLockReadGuard};
 use stylearc::Arc;
@@ -67,35 +69,40 @@ impl PerDocumentStyleData {
     }
 }
 
 impl PerDocumentStyleDataImpl {
     /// Reset the device state because it may have changed.
     ///
     /// Implies also a stylesheet flush.
     pub fn reset_device(&mut self, guard: &SharedRwLockReadGuard) {
-        Arc::get_mut(self.stylist.device_mut()).unwrap().reset();
+        self.stylist.device_mut().reset();
         self.stylesheets.force_dirty();
-        self.flush_stylesheets(guard);
+        self.flush_stylesheets::<GeckoElement>(guard, None);
     }
 
     /// Recreate the style data if the stylesheets have changed.
-    pub fn flush_stylesheets(&mut self, guard: &SharedRwLockReadGuard) {
+    pub fn flush_stylesheets<E>(&mut self,
+                                guard: &SharedRwLockReadGuard,
+                                document_element: Option<E>)
+        where E: TElement,
+    {
         if !self.stylesheets.has_changed() {
             return;
         }
 
         let mut extra_data = ExtraStyleData {
             font_faces: &mut self.font_faces,
             counter_styles: &mut self.counter_styles,
         };
 
         let author_style_disabled = self.stylesheets.author_style_disabled();
         self.stylist.clear();
-        self.stylist.rebuild(self.stylesheets.flush(),
+        let iter = self.stylesheets.flush(document_element);
+        self.stylist.rebuild(iter,
                              &StylesheetGuards::same(guard),
                              /* ua_sheets = */ None,
                              /* stylesheets_changed = */ true,
                              author_style_disabled,
                              &mut extra_data);
     }
 
     /// Get the default computed values for this document.
--- a/servo/components/style/gecko/generated/bindings.rs
+++ b/servo/components/style/gecko/generated/bindings.rs
@@ -1799,17 +1799,19 @@ extern "C" {
     pub fn Servo_StyleSet_InsertStyleSheetBefore(set:
                                                      RawServoStyleSetBorrowed,
                                                  sheet:
                                                      RawServoStyleSheetBorrowed,
                                                  unique_id: u64,
                                                  before_unique_id: u64);
 }
 extern "C" {
-    pub fn Servo_StyleSet_FlushStyleSheets(set: RawServoStyleSetBorrowed);
+    pub fn Servo_StyleSet_FlushStyleSheets(set: RawServoStyleSetBorrowed,
+                                           doc_elem:
+                                               RawGeckoElementBorrowedOrNull);
 }
 extern "C" {
     pub fn Servo_StyleSet_NoteStyleSheetsChanged(set:
                                                      RawServoStyleSetBorrowed,
                                                  author_style_disabled: bool);
 }
 extern "C" {
     pub fn Servo_StyleSet_GetKeyframesForName(set: RawServoStyleSetBorrowed,
new file mode 100644
--- /dev/null
+++ b/servo/components/style/invalidation/mod.rs
@@ -0,0 +1,296 @@
+/* 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/. */
+
+//! A collection of invalidations due to changes in which stylesheets affect a
+//! document.
+
+#![deny(unsafe_code)]
+
+use Atom;
+use data::StoredRestyleHint;
+use dom::{TElement, TNode};
+use fnv::FnvHashSet;
+use selector_parser::SelectorImpl;
+use selectors::parser::{Component, Selector};
+use shared_lock::SharedRwLockReadGuard;
+use stylesheets::{CssRule, Stylesheet};
+use stylist::Stylist;
+
+/// An invalidation scope represents a kind of subtree that may need to be
+/// restyled.
+#[derive(Debug, Hash, Eq, PartialEq)]
+enum InvalidationScope {
+    /// All the descendants of an element with a given id.
+    ID(Atom),
+    /// All the descendants of an element with a given class name.
+    Class(Atom),
+}
+
+impl InvalidationScope {
+    fn is_id(&self) -> bool {
+        matches!(*self, InvalidationScope::ID(..))
+    }
+
+    fn matches<E>(&self, element: E) -> bool
+        where E: TElement,
+    {
+        match *self {
+            InvalidationScope::Class(ref class) => {
+                element.has_class(class)
+            }
+            InvalidationScope::ID(ref id) => {
+                match element.get_id() {
+                    Some(element_id) => element_id == *id,
+                    None => false,
+                }
+            }
+        }
+    }
+}
+
+/// A set of invalidations due to stylesheet additions.
+///
+/// TODO(emilio): We might be able to do the same analysis for removals and
+/// media query changes too?
+pub struct StylesheetInvalidationSet {
+    /// The style scopes we know we have to restyle so far.
+    invalid_scopes: FnvHashSet<InvalidationScope>,
+    /// Whether the whole document should be invalid.
+    fully_invalid: bool,
+}
+
+impl StylesheetInvalidationSet {
+    /// Create an empty `StylesheetInvalidationSet`.
+    pub fn new() -> Self {
+        Self {
+            invalid_scopes: FnvHashSet::default(),
+            fully_invalid: false,
+        }
+    }
+
+    /// Mark the DOM tree styles' as fully invalid.
+    pub fn invalidate_fully(&mut self) {
+        debug!("StylesheetInvalidationSet::invalidate_fully");
+        self.invalid_scopes.clear();
+        self.fully_invalid = true;
+    }
+
+    /// Analyze the given stylesheet, and collect invalidations from their
+    /// rules, in order to avoid doing a full restyle when we style the document
+    /// next time.
+    pub fn collect_invalidations_for(
+        &mut self,
+        stylist: &Stylist,
+        stylesheet: &Stylesheet,
+        guard: &SharedRwLockReadGuard)
+    {
+        debug!("StylesheetInvalidationSet::collect_invalidations_for");
+        if self.fully_invalid {
+            debug!(" > Fully invalid already");
+            return;
+        }
+
+        if stylesheet.disabled() ||
+           !stylesheet.is_effective_for_device(stylist.device(), guard) {
+            debug!(" > Stylesheet was not effective");
+            return; // Nothing to do here.
+        }
+
+        for rule in stylesheet.effective_rules(stylist.device(), guard) {
+            self.collect_invalidations_for_rule(rule, guard);
+            if self.fully_invalid {
+                self.invalid_scopes.clear();
+                break;
+            }
+        }
+
+        debug!(" > resulting invalidations: {:?}", self.invalid_scopes);
+        debug!(" > fully_invalid: {}", self.fully_invalid);
+    }
+
+    /// Clears the invalidation set, invalidating elements as needed if
+    /// `document_element` is provided.
+    pub fn flush<E>(&mut self, document_element: Option<E>)
+        where E: TElement,
+    {
+        if let Some(e) = document_element {
+            self.process_invalidations_in_subtree(e);
+        }
+        self.invalid_scopes.clear();
+        self.fully_invalid = false;
+    }
+
+    /// Process style invalidations in a given subtree, that is, look for all
+    /// the relevant scopes in the subtree, and mark as dirty only the relevant
+    /// ones.
+    ///
+    /// Returns whether it invalidated at least one element's style.
+    #[allow(unsafe_code)]
+    fn process_invalidations_in_subtree<E>(&self, element: E) -> bool
+        where E: TElement,
+    {
+        let mut data = match element.mutate_data() {
+            Some(data) => data,
+            None => return false,
+        };
+
+        if !data.has_styles() {
+            return false;
+        }
+
+        if let Some(ref r) = data.get_restyle() {
+            if r.hint.contains_subtree() {
+                debug!("process_invalidations_in_subtree: {:?} was already invalid",
+                       element);
+                return false;
+            }
+        }
+
+        if self.fully_invalid {
+            debug!("process_invalidations_in_subtree: fully_invalid({:?})",
+                   element);
+            data.ensure_restyle().hint.insert(StoredRestyleHint::subtree());
+            return true;
+        }
+
+        for scope in &self.invalid_scopes {
+            if scope.matches(element) {
+                debug!("process_invalidations_in_subtree: {:?} matched {:?}",
+                       element, scope);
+                data.ensure_restyle().hint.insert(StoredRestyleHint::subtree());
+                return true;
+            }
+        }
+
+
+        let mut any_children_invalid = false;
+
+        for child in element.as_node().children() {
+            let child = match child.as_element() {
+                Some(e) => e,
+                None => continue,
+            };
+
+            any_children_invalid |= self.process_invalidations_in_subtree(child);
+        }
+
+        if any_children_invalid {
+            debug!("Children of {:?} changed, setting dirty descendants",
+                   element);
+            unsafe { element.set_dirty_descendants() }
+        }
+
+        return any_children_invalid
+    }
+
+    fn scan_component(
+        component: &Component<SelectorImpl>,
+        scope: &mut Option<InvalidationScope>)
+    {
+        match *component {
+            Component::Class(ref class) => {
+                if scope.as_ref().map_or(true, |s| !s.is_id()) {
+                    *scope = Some(InvalidationScope::Class(class.clone()));
+                }
+            }
+            Component::ID(ref id) => {
+                if scope.is_none() {
+                    *scope = Some(InvalidationScope::ID(id.clone()));
+                }
+            }
+            _ => {
+                // Ignore everything else, at least for now.
+            }
+        }
+    }
+
+    /// Collect a style scopes for a given selector.
+    ///
+    /// We look at the outermost class or id selector to the left of an ancestor
+    /// combinator, in order to restyle only a given subtree.
+    ///
+    /// We prefer id scopes to class scopes, and outermost scopes to innermost
+    /// scopes (to reduce the amount of traversal we need to do).
+    fn collect_scopes(&mut self, selector: &Selector<SelectorImpl>) {
+        debug!("StylesheetInvalidationSet::collect_scopes({:?})", selector);
+
+        let mut scope: Option<InvalidationScope> = None;
+
+        let mut scan = true;
+        let mut iter = selector.inner.complex.iter();
+
+        loop {
+            for component in &mut iter {
+                if scan {
+                    Self::scan_component(component, &mut scope);
+                }
+            }
+            match iter.next_sequence() {
+                None => break,
+                Some(combinator) => {
+                    scan = combinator.is_ancestor();
+                }
+            }
+        }
+
+        match scope {
+            Some(s) => {
+                debug!(" > Found scope: {:?}", s);
+                self.invalid_scopes.insert(s);
+            }
+            None => {
+                debug!(" > Scope not found");
+
+                // If we didn't find a scope, any element could match this, so
+                // let's just bail out.
+                self.fully_invalid = true;
+            }
+        }
+    }
+
+    /// Collects invalidations for a given CSS rule.
+    fn collect_invalidations_for_rule(
+        &mut self,
+        rule: &CssRule,
+        guard: &SharedRwLockReadGuard)
+    {
+        use stylesheets::CssRule::*;
+        debug!("StylesheetInvalidationSet::collect_invalidations_for_rule");
+        debug_assert!(!self.fully_invalid, "Not worth to be here!");
+
+        match *rule {
+            Style(ref lock) => {
+                let style_rule = lock.read_with(guard);
+                for selector in &style_rule.selectors.0 {
+                    self.collect_scopes(selector);
+                    if self.fully_invalid {
+                        return;
+                    }
+                }
+            }
+            Document(..) |
+            Namespace(..) |
+            Import(..) |
+            Media(..) |
+            Supports(..) => {
+                // Do nothing, relevant nested rules are visited as part of the
+                // iteration.
+            }
+            FontFace(..) |
+            CounterStyle(..) |
+            Keyframes(..) |
+            Page(..) |
+            Viewport(..) => {
+                debug!(" > Found unsupported rule, marking the whole subtree \
+                       invalid.");
+
+                // TODO(emilio): Can we do better here?
+                //
+                // At least in `@page`, we could check the relevant media, I
+                // guess.
+                self.fully_invalid = true;
+            }
+        }
+    }
+}
--- a/servo/components/style/lib.rs
+++ b/servo/components/style/lib.rs
@@ -105,16 +105,17 @@ pub mod document_condition;
 pub mod dom;
 pub mod element_state;
 #[cfg(feature = "servo")] mod encoding_support;
 pub mod error_reporting;
 pub mod font_face;
 pub mod font_metrics;
 #[cfg(feature = "gecko")] #[allow(unsafe_code)] pub mod gecko;
 #[cfg(feature = "gecko")] #[allow(unsafe_code)] pub mod gecko_bindings;
+pub mod invalidation;
 pub mod keyframes;
 #[allow(missing_docs)] // TODO.
 pub mod logical_geometry;
 pub mod matching;
 pub mod media_queries;
 pub mod parallel;
 pub mod parser;
 pub mod restyle_hints;
--- a/servo/components/style/restyle_hints.rs
+++ b/servo/components/style/restyle_hints.rs
@@ -363,17 +363,17 @@ impl RestyleHint {
         // A later patch should make it worthwhile to have an insert() function
         // that consumes its argument.
         self.insert_from(&other)
     }
 
     /// Returns whether this `RestyleHint` represents at least as much restyle
     /// work as the specified one.
     #[inline]
-    pub fn contains(&mut self, other: &Self) -> bool {
+    pub fn contains(&self, other: &Self) -> bool {
         self.match_under_self.contains(other.match_under_self) &&
         (self.match_later_siblings & other.match_later_siblings) == other.match_later_siblings &&
         self.replacements.contains(other.replacements)
     }
 }
 
 impl RestyleReplacements {
     /// The replacements for the animation cascade levels.
--- a/servo/components/style/stylesheet_set.rs
+++ b/servo/components/style/stylesheet_set.rs
@@ -1,17 +1,21 @@
 /* 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/. */
 
 //! A centralized set of stylesheets for a document.
 
+use dom::TElement;
+use invalidation::StylesheetInvalidationSet;
+use shared_lock::SharedRwLockReadGuard;
 use std::slice;
 use stylearc::Arc;
 use stylesheets::Stylesheet;
+use stylist::Stylist;
 
 /// Entry for a StylesheetSet. We don't bother creating a constructor, because
 /// there's no sensible defaults for the member variables.
 pub struct StylesheetSetEntry {
     unique_id: u64,
     sheet: Arc<Stylesheet>,
 }
 
@@ -35,103 +39,151 @@ pub struct StylesheetSet {
     /// include recursive `@import` rules.
     entries: Vec<StylesheetSetEntry>,
 
     /// Whether the entries list above has changed since the last restyle.
     dirty: bool,
 
     /// Has author style been disabled?
     author_style_disabled: bool,
+
+    /// The style invalidations that we still haven't processed.
+    invalidations: StylesheetInvalidationSet,
 }
 
 impl StylesheetSet {
     /// Create a new empty StylesheetSet.
     pub fn new() -> Self {
         StylesheetSet {
             entries: vec![],
             dirty: false,
             author_style_disabled: false,
+            invalidations: StylesheetInvalidationSet::new(),
         }
     }
 
     /// Returns whether author styles have been disabled for the current
     /// stylesheet set.
     pub fn author_style_disabled(&self) -> bool {
         self.author_style_disabled
     }
 
     fn remove_stylesheet_if_present(&mut self, unique_id: u64) {
         self.entries.retain(|x| x.unique_id != unique_id);
     }
 
     /// Appends a new stylesheet to the current set.
-    pub fn append_stylesheet(&mut self, sheet: &Arc<Stylesheet>,
-                             unique_id: u64) {
+    pub fn append_stylesheet(
+        &mut self,
+        stylist: &Stylist,
+        sheet: &Arc<Stylesheet>,
+        unique_id: u64,
+        guard: &SharedRwLockReadGuard)
+    {
+        debug!("StylesheetSet::append_stylesheet");
         self.remove_stylesheet_if_present(unique_id);
         self.entries.push(StylesheetSetEntry {
             unique_id: unique_id,
             sheet: sheet.clone(),
         });
         self.dirty = true;
+        self.invalidations.collect_invalidations_for(
+            stylist,
+            sheet,
+            guard)
     }
 
     /// Prepend a new stylesheet to the current set.
-    pub fn prepend_stylesheet(&mut self, sheet: &Arc<Stylesheet>,
-                              unique_id: u64) {
+    pub fn prepend_stylesheet(
+        &mut self,
+        stylist: &Stylist,
+        sheet: &Arc<Stylesheet>,
+        unique_id: u64,
+        guard: &SharedRwLockReadGuard)
+    {
+        debug!("StylesheetSet::prepend_stylesheet");
         self.remove_stylesheet_if_present(unique_id);
         self.entries.insert(0, StylesheetSetEntry {
             unique_id: unique_id,
             sheet: sheet.clone(),
         });
         self.dirty = true;
+        self.invalidations.collect_invalidations_for(
+            stylist,
+            sheet,
+            guard)
     }
 
     /// Insert a given stylesheet before another stylesheet in the document.
-    pub fn insert_stylesheet_before(&mut self,
-                                    sheet: &Arc<Stylesheet>,
-                                    unique_id: u64,
-                                    before_unique_id: u64) {
+    pub fn insert_stylesheet_before(
+        &mut self,
+        stylist: &Stylist,
+        sheet: &Arc<Stylesheet>,
+        unique_id: u64,
+        before_unique_id: u64,
+        guard: &SharedRwLockReadGuard)
+    {
+        debug!("StylesheetSet::insert_stylesheet_before");
         self.remove_stylesheet_if_present(unique_id);
         let index = self.entries.iter().position(|x| {
             x.unique_id == before_unique_id
         }).expect("`before_unique_id` stylesheet not found");
         self.entries.insert(index, StylesheetSetEntry {
             unique_id: unique_id,
             sheet: sheet.clone(),
         });
         self.dirty = true;
+        self.invalidations.collect_invalidations_for(
+            stylist,
+            sheet,
+            guard)
     }
 
     /// Remove a given stylesheet from the set.
     pub fn remove_stylesheet(&mut self, unique_id: u64) {
+        debug!("StylesheetSet::remove_stylesheet");
         self.remove_stylesheet_if_present(unique_id);
         self.dirty = true;
+        // FIXME(emilio): We can do better!
+        self.invalidations.invalidate_fully();
     }
 
     /// Notes that the author style has been disabled for this document.
     pub fn set_author_style_disabled(&mut self, disabled: bool) {
+        debug!("StylesheetSet::set_author_style_disabled");
         if self.author_style_disabled == disabled {
             return;
         }
         self.author_style_disabled = disabled;
         self.dirty = true;
+        self.invalidations.invalidate_fully();
     }
 
     /// Returns whether the given set has changed from the last flush.
     pub fn has_changed(&self) -> bool {
         self.dirty
     }
 
     /// Flush the current set, unmarking it as dirty, and returns an iterator
     /// over the new stylesheet list.
-    pub fn flush(&mut self) -> StylesheetIterator {
+    pub fn flush<E>(&mut self,
+                    document_element: Option<E>)
+                    -> StylesheetIterator
+        where E: TElement,
+    {
+        debug!("StylesheetSet::flush");
+        debug_assert!(self.dirty);
+
         self.dirty = false;
+        self.invalidations.flush(document_element);
+
         StylesheetIterator(self.entries.iter())
     }
 
     /// Mark the stylesheets as dirty, because something external may have
     /// invalidated it.
     ///
     /// FIXME(emilio): Make this more granular.
     pub fn force_dirty(&mut self) {
         self.dirty = true;
+        self.invalidations.invalidate_fully();
     }
 }
--- a/servo/components/style/stylesheets.rs
+++ b/servo/components/style/stylesheets.rs
@@ -32,21 +32,23 @@ use parser::{PARSING_MODE_DEFAULT, Parse
 use properties::{PropertyDeclarationBlock, parse_property_declaration_list};
 use selector_parser::{SelectorImpl, SelectorParser};
 use selectors::parser::SelectorList;
 #[cfg(feature = "servo")]
 use servo_config::prefs::PREFS;
 #[cfg(not(feature = "gecko"))]
 use servo_url::ServoUrl;
 use shared_lock::{SharedRwLock, Locked, ToCssWithGuard, SharedRwLockReadGuard};
+use smallvec::SmallVec;
 use std::borrow::Borrow;
 use std::cell::Cell;
 use std::fmt;
 use std::mem::align_of;
 use std::os::raw::c_void;
+use std::slice;
 use std::sync::atomic::{AtomicBool, Ordering};
 use str::starts_with_ignore_ascii_case;
 use style_traits::ToCss;
 use stylearc::Arc;
 use stylist::FnvHashMap;
 use supports::SupportsCondition;
 use values::{CustomIdent, KeyframesName};
 use values::specified::url::SpecifiedUrl;
@@ -427,26 +429,16 @@ pub enum CssRuleType {
     // https://www.w3.org/TR/2012/WD-css3-conditional-20120911/#extentions-to-cssrule-interface
     Document            = 13,
     // https://drafts.csswg.org/css-fonts-3/#om-fontfeaturevalues
     FontFeatureValues   = 14,
     // https://drafts.csswg.org/css-device-adapt/#css-rule-interface
     Viewport            = 15,
 }
 
-/// Result type for with_nested_rules_mq_and_doc_rule()
-pub enum NestedRulesResult<'a> {
-    /// Only rules
-    Rules(&'a [CssRule]),
-    /// Rules with media queries
-    RulesWithMediaQueries(&'a [CssRule], &'a MediaList),
-    /// Rules with document rule
-    RulesWithDocument(&'a [CssRule], &'a DocumentRule)
-}
-
 #[allow(missing_docs)]
 pub enum SingleRuleParseError {
     Syntax,
     Hierarchy,
 }
 
 impl CssRule {
     #[allow(missing_docs)]
@@ -470,70 +462,16 @@ impl CssRule {
         match *self {
             // CssRule::Charset(..) => State::Start,
             CssRule::Import(..) => State::Imports,
             CssRule::Namespace(..) => State::Namespaces,
             _ => State::Body,
         }
     }
 
-    /// Call `f` with the slice of rules directly contained inside this rule.
-    ///
-    /// Note that only some types of rules can contain rules. An empty slice is
-    /// used for others.
-    ///
-    /// This will not recurse down unsupported @supports rules
-    pub fn with_nested_rules_mq_and_doc_rule<F, R>(&self, guard: &SharedRwLockReadGuard, mut f: F) -> R
-    where F: FnMut(NestedRulesResult) -> R {
-        match *self {
-            CssRule::Import(ref lock) => {
-                let rule = lock.read_with(guard);
-                let media = rule.stylesheet.media.read_with(guard);
-                let rules = rule.stylesheet.rules.read_with(guard);
-                // FIXME(emilio): Include the nested rules if the stylesheet is
-                // loaded.
-                f(NestedRulesResult::RulesWithMediaQueries(&rules.0, &media))
-            }
-            CssRule::Namespace(_) |
-            CssRule::Style(_) |
-            CssRule::FontFace(_) |
-            CssRule::CounterStyle(_) |
-            CssRule::Viewport(_) |
-            CssRule::Keyframes(_) |
-            CssRule::Page(_) => {
-                f(NestedRulesResult::Rules(&[]))
-            }
-            CssRule::Media(ref lock) => {
-                let media_rule = lock.read_with(guard);
-                let mq = media_rule.media_queries.read_with(guard);
-                let rules = &media_rule.rules.read_with(guard).0;
-                f(NestedRulesResult::RulesWithMediaQueries(rules, &mq))
-            }
-            CssRule::Supports(ref lock) => {
-                let supports_rule = lock.read_with(guard);
-                let enabled = supports_rule.enabled;
-                if enabled {
-                    let rules = &supports_rule.rules.read_with(guard).0;
-                    f(NestedRulesResult::Rules(rules))
-                } else {
-                    f(NestedRulesResult::Rules(&[]))
-                }
-            }
-            CssRule::Document(ref lock) => {
-                if cfg!(feature = "gecko") {
-                    let document_rule = lock.read_with(guard);
-                    let rules = &document_rule.rules.read_with(guard).0;
-                    f(NestedRulesResult::RulesWithDocument(rules, &document_rule))
-                } else {
-                    unimplemented!()
-                }
-            }
-        }
-    }
-
     // input state is None for a nested rule
     // Returns a parsed CSS rule and the final state of the parser
     #[allow(missing_docs)]
     pub fn parse(css: &str,
                  parent_stylesheet: &Stylesheet,
                  state: Option<State>,
                  loader: Option<&StylesheetLoader>)
                  -> Result<(Self, State), SingleRuleParseError> {
@@ -998,16 +936,273 @@ impl DocumentRule {
         DocumentRule {
             condition: self.condition.clone(),
             rules: Arc::new(lock.wrap(rules.deep_clone_with_lock(lock))),
             source_location: self.source_location.clone(),
         }
     }
 }
 
+/// A trait that describes statically which rules are iterated for a given
+/// RulesIterator.
+pub trait NestedRuleIterationCondition {
+    /// Whether we should process the nested rules in a given `@import` rule.
+    fn process_import(
+        guard: &SharedRwLockReadGuard,
+        device: &Device,
+        quirks_mode: QuirksMode,
+        rule: &ImportRule)
+        -> bool;
+
+    /// Whether we should process the nested rules in a given `@media` rule.
+    fn process_media(
+        guard: &SharedRwLockReadGuard,
+        device: &Device,
+        quirks_mode: QuirksMode,
+        rule: &MediaRule)
+        -> bool;
+
+    /// Whether we should process the nested rules in a given `@-moz-document` rule.
+    fn process_document(
+        guard: &SharedRwLockReadGuard,
+        device: &Device,
+        quirks_mode: QuirksMode,
+        rule: &DocumentRule)
+        -> bool;
+
+    /// Whether we should process the nested rules in a given `@supports` rule.
+    fn process_supports(
+        guard: &SharedRwLockReadGuard,
+        device: &Device,
+        quirks_mode: QuirksMode,
+        rule: &SupportsRule)
+        -> bool;
+}
+
+/// A struct that represents the condition that a rule applies to the document.
+pub struct EffectiveRules;
+
+impl NestedRuleIterationCondition for EffectiveRules {
+    fn process_import(
+        guard: &SharedRwLockReadGuard,
+        device: &Device,
+        quirks_mode: QuirksMode,
+        rule: &ImportRule)
+        -> bool
+    {
+        rule.stylesheet.media.read_with(guard).evaluate(device, quirks_mode)
+    }
+
+    fn process_media(
+        guard: &SharedRwLockReadGuard,
+        device: &Device,
+        quirks_mode: QuirksMode,
+        rule: &MediaRule)
+        -> bool
+    {
+        rule.media_queries.read_with(guard).evaluate(device, quirks_mode)
+    }
+
+    fn process_document(
+        _: &SharedRwLockReadGuard,
+        device: &Device,
+        _: QuirksMode,
+        rule: &DocumentRule)
+        -> bool
+    {
+        rule.condition.evaluate(device)
+    }
+
+    fn process_supports(
+        _: &SharedRwLockReadGuard,
+        _: &Device,
+        _: QuirksMode,
+        rule: &SupportsRule)
+        -> bool
+    {
+        rule.enabled
+    }
+}
+
+/// A filter that processes all the rules in a rule list.
+pub struct AllRules;
+
+impl NestedRuleIterationCondition for AllRules {
+    fn process_import(
+        _: &SharedRwLockReadGuard,
+        _: &Device,
+        _: QuirksMode,
+        _: &ImportRule)
+        -> bool
+    {
+        true
+    }
+
+    /// Whether we should process the nested rules in a given `@media` rule.
+    fn process_media(
+        _: &SharedRwLockReadGuard,
+        _: &Device,
+        _: QuirksMode,
+        _: &MediaRule)
+        -> bool
+    {
+        true
+    }
+
+    /// Whether we should process the nested rules in a given `@-moz-document` rule.
+    fn process_document(
+        _: &SharedRwLockReadGuard,
+        _: &Device,
+        _: QuirksMode,
+        _: &DocumentRule)
+        -> bool
+    {
+        true
+    }
+
+    /// Whether we should process the nested rules in a given `@supports` rule.
+    fn process_supports(
+        _: &SharedRwLockReadGuard,
+        _: &Device,
+        _: QuirksMode,
+        _: &SupportsRule)
+        -> bool
+    {
+        true
+    }
+}
+
+/// An iterator over all the effective rules of a stylesheet.
+///
+/// NOTE: This iterator recurses into `@import` rules.
+pub type EffectiveRulesIterator<'a, 'b> = RulesIterator<'a, 'b, EffectiveRules>;
+
+/// An iterator over a list of rules.
+pub struct RulesIterator<'a, 'b, C>
+    where 'b: 'a,
+          C: NestedRuleIterationCondition + 'static,
+{
+    device: &'a Device,
+    quirks_mode: QuirksMode,
+    guard: &'a SharedRwLockReadGuard<'b>,
+    stack: SmallVec<[slice::Iter<'a, CssRule>; 3]>,
+    _phantom: ::std::marker::PhantomData<C>,
+}
+
+impl<'a, 'b, C> RulesIterator<'a, 'b, C>
+    where 'b: 'a,
+          C: NestedRuleIterationCondition + 'static,
+{
+    /// Creates a new `RulesIterator` to iterate over `rules`.
+    pub fn new(
+        device: &'a Device,
+        quirks_mode: QuirksMode,
+        guard: &'a SharedRwLockReadGuard<'b>,
+        rules: &'a CssRules)
+        -> Self
+    {
+        let mut stack = SmallVec::new();
+        stack.push(rules.0.iter());
+        Self {
+            device: device,
+            quirks_mode: quirks_mode,
+            guard: guard,
+            stack: stack,
+            _phantom: ::std::marker::PhantomData,
+        }
+    }
+
+    /// Skips all the remaining children of the last nested rule processed.
+    pub fn skip_children(&mut self) {
+        self.stack.pop();
+    }
+}
+
+impl<'a, 'b, C> Iterator for RulesIterator<'a, 'b, C>
+    where 'b: 'a,
+          C: NestedRuleIterationCondition + 'static,
+{
+    type Item = &'a CssRule;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        let mut nested_iter_finished = false;
+        while !self.stack.is_empty() {
+            if nested_iter_finished {
+                self.stack.pop();
+                nested_iter_finished = false;
+                continue;
+            }
+
+            let rule;
+            let sub_iter;
+            {
+                let mut nested_iter = self.stack.last_mut().unwrap();
+                rule = match nested_iter.next() {
+                    Some(r) => r,
+                    None => {
+                        nested_iter_finished = true;
+                        continue
+                    }
+                };
+
+                sub_iter = match *rule {
+                    CssRule::Import(ref import_rule) => {
+                        let import_rule = import_rule.read_with(self.guard);
+
+                        if C::process_import(self.guard, self.device, self.quirks_mode, import_rule) {
+                            Some(import_rule.stylesheet.rules.read_with(self.guard).0.iter())
+                        } else {
+                            None
+                        }
+                    }
+                    CssRule::Document(ref doc_rule) => {
+                        let doc_rule = doc_rule.read_with(self.guard);
+                        if C::process_document(self.guard, self.device, self.quirks_mode, doc_rule) {
+                            Some(doc_rule.rules.read_with(self.guard).0.iter())
+                        } else {
+                            None
+                        }
+                    }
+                    CssRule::Media(ref lock) => {
+                        let media_rule = lock.read_with(self.guard);
+                        if C::process_media(self.guard, self.device, self.quirks_mode, media_rule) {
+                            Some(media_rule.rules.read_with(self.guard).0.iter())
+                        } else {
+                            None
+                        }
+                    }
+                    CssRule::Supports(ref lock) => {
+                        let supports_rule = lock.read_with(self.guard);
+                        if C::process_supports(self.guard, self.device, self.quirks_mode, supports_rule) {
+                            Some(supports_rule.rules.read_with(self.guard).0.iter())
+                        } else {
+                            None
+                        }
+                    }
+                    CssRule::Namespace(_) |
+                    CssRule::Style(_) |
+                    CssRule::FontFace(_) |
+                    CssRule::CounterStyle(_) |
+                    CssRule::Viewport(_) |
+                    CssRule::Keyframes(_) |
+                    CssRule::Page(_) => None,
+                };
+            }
+
+            if let Some(sub_iter) = sub_iter {
+                self.stack.push(sub_iter);
+            }
+
+            return Some(rule);
+        }
+
+        None
+    }
+}
+
 impl Stylesheet {
     /// Updates an empty stylesheet from a given string of text.
     pub fn update_from_str(existing: &Stylesheet,
                            css: &str,
                            url_data: &UrlExtraData,
                            stylesheet_loader: Option<&StylesheetLoader>,
                            error_reporter: &ParseErrorReporter,
                            line_number_offset: u64) {
@@ -1127,24 +1322,40 @@ impl Stylesheet {
     ///
     /// Always true if no associated MediaList exists.
     pub fn is_effective_for_device(&self, device: &Device, guard: &SharedRwLockReadGuard) -> bool {
         self.media.read_with(guard).evaluate(device, self.quirks_mode)
     }
 
     /// Return an iterator over the effective rules within the style-sheet, as
     /// according to the supplied `Device`.
-    ///
-    /// If a condition does not hold, its associated conditional group rule and
-    /// nested rules will be skipped. Use `rules` if all rules need to be
-    /// examined.
+    #[inline]
+    pub fn effective_rules<'a, 'b>(
+        &'a self,
+        device: &'a Device,
+        guard: &'a SharedRwLockReadGuard<'b>)
+        -> EffectiveRulesIterator<'a, 'b>
+    {
+        self.iter_rules::<'a, 'b, EffectiveRules>(device, guard)
+    }
+
+    /// Return an iterator using the condition `C`.
     #[inline]
-    pub fn effective_rules<F>(&self, device: &Device, guard: &SharedRwLockReadGuard, mut f: F)
-    where F: FnMut(&CssRule) {
-        effective_rules(&self.rules.read_with(guard).0, device, self.quirks_mode, guard, &mut f);
+    pub fn iter_rules<'a, 'b, C>(
+        &'a self,
+        device: &'a Device,
+        guard: &'a SharedRwLockReadGuard<'b>)
+        -> RulesIterator<'a, 'b, C>
+        where C: NestedRuleIterationCondition,
+    {
+        RulesIterator::new(
+            device,
+            self.quirks_mode,
+            guard,
+            &self.rules.read_with(guard))
     }
 
     /// Returns whether the stylesheet has been explicitly disabled through the
     /// CSSOM.
     pub fn disabled(&self) -> bool {
         self.disabled.load(Ordering::SeqCst)
     }
 
@@ -1184,61 +1395,30 @@ impl Clone for Stylesheet {
             dirty_on_viewport_size_change: AtomicBool::new(
                 self.dirty_on_viewport_size_change.load(Ordering::SeqCst)),
             disabled: AtomicBool::new(self.disabled.load(Ordering::SeqCst)),
             quirks_mode: self.quirks_mode,
         }
     }
 }
 
-fn effective_rules<F>(rules: &[CssRule],
-                      device: &Device,
-                      quirks_mode: QuirksMode,
-                      guard: &SharedRwLockReadGuard,
-                      f: &mut F)
-    where F: FnMut(&CssRule)
-{
-    for rule in rules {
-        f(rule);
-        rule.with_nested_rules_mq_and_doc_rule(guard, |result| {
-            let rules = match result {
-                NestedRulesResult::Rules(rules) => {
-                    rules
-                },
-                NestedRulesResult::RulesWithMediaQueries(rules, media_queries) => {
-                    if !media_queries.evaluate(device, quirks_mode) {
-                        return;
-                    }
-                    rules
-                },
-                NestedRulesResult::RulesWithDocument(rules, doc_rule) => {
-                    if !doc_rule.condition.evaluate(device) {
-                        return;
-                    }
-                    rules
-                },
-            };
-            effective_rules(rules, device, quirks_mode, guard, f)
-        })
-    }
-}
-
 macro_rules! rule_filter {
     ($( $method: ident($variant:ident => $rule_type: ident), )+) => {
         impl Stylesheet {
             $(
                 #[allow(missing_docs)]
                 pub fn $method<F>(&self, device: &Device, guard: &SharedRwLockReadGuard, mut f: F)
-                where F: FnMut(&$rule_type) {
-                    self.effective_rules(device, guard, |rule| {
+                    where F: FnMut(&$rule_type),
+                {
+                    for rule in self.effective_rules(device, guard) {
                         if let CssRule::$variant(ref lock) = *rule {
                             let rule = lock.read_with(guard);
                             f(&rule)
                         }
-                    })
+                    }
                 }
             )+
         }
     }
 }
 
 rule_filter! {
     effective_style_rules(Style => StyleRule),
--- a/servo/components/style/stylist.rs
+++ b/servo/components/style/stylist.rs
@@ -34,20 +34,19 @@ use shared_lock::{Locked, SharedRwLockRe
 use sink::Push;
 use smallvec::{SmallVec, VecLike};
 #[cfg(feature = "servo")]
 use std::marker::PhantomData;
 use style_traits::viewport::ViewportConstraints;
 use stylearc::Arc;
 #[cfg(feature = "gecko")]
 use stylesheets::{CounterStyleRule, FontFaceRule};
-use stylesheets::{CssRule, Origin};
-use stylesheets::{StyleRule, Stylesheet, UserAgentStylesheets};
-#[cfg(feature = "servo")]
-use stylesheets::NestedRulesResult;
+use stylesheets::{CssRule, DocumentRule, ImportRule, MediaRule, StyleRule, SupportsRule};
+use stylesheets::{Stylesheet, Origin, UserAgentStylesheets};
+use stylesheets::NestedRuleIterationCondition;
 use thread_state;
 use viewport::{self, MaybeNew, ViewportRule};
 
 pub use ::fnv::FnvHashMap;
 
 /// List of applicable declaration. This is a transient structure that shuttles
 /// declarations between selector matching and inserting into the rule tree, and
 /// therefore we want to avoid heap-allocation where possible.
@@ -74,20 +73,17 @@ pub struct Stylist {
     ///
     /// With Gecko, the device is never changed. Gecko manually tracks whether
     /// the device data should be reconstructed, and "resets" the state of the
     /// device.
     ///
     /// On Servo, on the other hand, the device is a really cheap representation
     /// that is recreated each time some constraint changes and calling
     /// `set_device`.
-    ///
-    /// In both cases, the device is actually _owned_ by the Stylist, and it's
-    /// only an `Arc` so we can implement `add_stylesheet` more idiomatically.
-    device: Arc<Device>,
+    device: Device,
 
     /// Viewport constraints based on the current device.
     viewport_constraints: Option<ViewportConstraints>,
 
     /// If true, the quirks-mode stylesheet is applied.
     quirks_mode: QuirksMode,
 
     /// If true, the device has changed, and the stylist needs to be updated.
@@ -221,25 +217,76 @@ impl From<StyleRuleInclusion> for RuleIn
     fn from(value: StyleRuleInclusion) -> Self {
         match value {
             StyleRuleInclusion::All => RuleInclusion::All,
             StyleRuleInclusion::DefaultOnly => RuleInclusion::DefaultOnly,
         }
     }
 }
 
+/// A filter that filters over effective rules, but allowing all potentially
+/// effective `@media` rules.
+pub struct PotentiallyEffectiveMediaRules;
+
+impl NestedRuleIterationCondition for PotentiallyEffectiveMediaRules {
+    fn process_import(
+        _: &SharedRwLockReadGuard,
+        _: &Device,
+        _: QuirksMode,
+        _: &ImportRule)
+        -> bool
+    {
+        true
+    }
+
+    fn process_media(
+        _: &SharedRwLockReadGuard,
+        _: &Device,
+        _: QuirksMode,
+        _: &MediaRule)
+        -> bool
+    {
+        true
+    }
+
+    /// Whether we should process the nested rules in a given `@-moz-document` rule.
+    fn process_document(
+        guard: &SharedRwLockReadGuard,
+        device: &Device,
+        quirks_mode: QuirksMode,
+        rule: &DocumentRule)
+        -> bool
+    {
+        use stylesheets::EffectiveRules;
+        EffectiveRules::process_document(guard, device, quirks_mode, rule)
+    }
+
+    /// Whether we should process the nested rules in a given `@supports` rule.
+    fn process_supports(
+        guard: &SharedRwLockReadGuard,
+        device: &Device,
+        quirks_mode: QuirksMode,
+        rule: &SupportsRule)
+        -> bool
+    {
+        use stylesheets::EffectiveRules;
+        EffectiveRules::process_supports(guard, device, quirks_mode, rule)
+    }
+}
+
+
 impl Stylist {
     /// Construct a new `Stylist`, using given `Device` and `QuirksMode`.
     /// If more members are added here, think about whether they should
     /// be reset in clear().
     #[inline]
     pub fn new(device: Device, quirks_mode: QuirksMode) -> Self {
         let mut stylist = Stylist {
             viewport_constraints: None,
-            device: Arc::new(device),
+            device: device,
             is_device_dirty: true,
             is_cleared: true,
             quirks_mode: quirks_mode,
 
             element_map: PerPseudoElementSelectorMap::new(),
             pseudos_map: Default::default(),
             animations: Default::default(),
             precomputed_pseudo_element_decls: Default::default(),
@@ -359,18 +406,17 @@ impl Stylist {
                 doc_stylesheets.clone(), guards.author, &self.device
             ).finish(),
         };
 
         self.viewport_constraints =
             ViewportConstraints::maybe_new(&self.device, &cascaded_rule, self.quirks_mode);
 
         if let Some(ref constraints) = self.viewport_constraints {
-            Arc::get_mut(&mut self.device).unwrap()
-                .account_for_viewport_rule(constraints);
+            self.device.account_for_viewport_rule(constraints);
         }
 
         SelectorImpl::each_eagerly_cascaded_pseudo_element(|pseudo| {
             self.pseudos_map.insert(pseudo, PerPseudoElementSelectorMap::new());
         });
 
         extra_data.clear();
 
@@ -426,41 +472,57 @@ impl Stylist {
         self.clear();
         self.rebuild(doc_stylesheets, guards, ua_stylesheets, stylesheets_changed,
                      author_style_disabled, extra_data)
     }
 
     fn add_stylesheet<'a>(&mut self,
                           stylesheet: &Stylesheet,
                           guard: &SharedRwLockReadGuard,
-                          extra_data: &mut ExtraStyleData<'a>) {
+                          _extra_data: &mut ExtraStyleData<'a>) {
         if stylesheet.disabled() || !stylesheet.is_effective_for_device(&self.device, guard) {
             return;
         }
 
-        // Cheap `Arc` clone so that the closure below can borrow `&mut Stylist`.
-        let device = self.device.clone();
-
-        stylesheet.effective_rules(&device, guard, |rule| {
+        for rule in stylesheet.effective_rules(&self.device, guard) {
             match *rule {
                 CssRule::Style(ref locked) => {
                     let style_rule = locked.read_with(&guard);
                     self.num_declarations += style_rule.block.read_with(&guard).len();
                     for selector in &style_rule.selectors.0 {
                         self.num_selectors += 1;
-                        self.add_rule_to_map(selector, locked, stylesheet);
+
+                        let map = if let Some(pseudo) = selector.pseudo_element() {
+                            self.pseudos_map
+                                .entry(pseudo.canonical())
+                                .or_insert_with(PerPseudoElementSelectorMap::new)
+                                .borrow_for_origin(&stylesheet.origin)
+                        } else {
+                            self.element_map.borrow_for_origin(&stylesheet.origin)
+                        };
+
+                        map.insert(Rule::new(selector.clone(),
+                                             locked.clone(),
+                                             self.rules_source_order));
+
                         self.dependencies.note_selector(selector);
-                        self.note_for_revalidation(selector);
-                        self.note_attribute_and_state_dependencies(selector);
+                        if needs_revalidation(selector) {
+                            self.selectors_for_cache_revalidation.insert(selector.inner.clone());
+                        }
+                        selector.visit(&mut AttributeAndStateDependencyVisitor {
+                            attribute_dependencies: &mut self.attribute_dependencies,
+                            style_attribute_dependency: &mut self.style_attribute_dependency,
+                            state_dependencies: &mut self.state_dependencies,
+                        });
                     }
                     self.rules_source_order += 1;
                 }
-                CssRule::Import(ref import) => {
-                    let import = import.read_with(guard);
-                    self.add_stylesheet(&import.stylesheet, guard, extra_data)
+                CssRule::Import(..) => {
+                    // effective_rules visits the inner stylesheet if
+                    // appropriate.
                 }
                 CssRule::Keyframes(ref keyframes_rule) => {
                     let keyframes_rule = keyframes_rule.read_with(guard);
                     debug!("Found valid keyframes rule: {:?}", *keyframes_rule);
 
                     // Don't let a prefixed keyframes animation override a non-prefixed one.
                     let needs_insertion = keyframes_rule.vendor_prefix.is_none() ||
                         self.animations.get(keyframes_rule.name.as_atom()).map_or(true, |rule|
@@ -469,83 +531,46 @@ impl Stylist {
                         let animation = KeyframesAnimation::from_keyframes(
                             &keyframes_rule.keyframes, keyframes_rule.vendor_prefix.clone(), guard);
                         debug!("Found valid keyframe animation: {:?}", animation);
                         self.animations.insert(keyframes_rule.name.as_atom().clone(), animation);
                     }
                 }
                 #[cfg(feature = "gecko")]
                 CssRule::FontFace(ref rule) => {
-                    extra_data.add_font_face(&rule, stylesheet.origin);
+                    _extra_data.add_font_face(&rule, stylesheet.origin);
                 }
                 #[cfg(feature = "gecko")]
                 CssRule::CounterStyle(ref rule) => {
-                    extra_data.add_counter_style(guard, &rule);
+                    _extra_data.add_counter_style(guard, &rule);
                 }
                 // We don't care about any other rule.
                 _ => {}
             }
-        });
-    }
-
-    #[inline]
-    fn add_rule_to_map(&mut self,
-                       selector: &Selector<SelectorImpl>,
-                       rule: &Arc<Locked<StyleRule>>,
-                       stylesheet: &Stylesheet)
-    {
-        let map = if let Some(pseudo) = selector.pseudo_element() {
-            self.pseudos_map
-                .entry(pseudo.canonical())
-                .or_insert_with(PerPseudoElementSelectorMap::new)
-                .borrow_for_origin(&stylesheet.origin)
-        } else {
-            self.element_map.borrow_for_origin(&stylesheet.origin)
-        };
-
-        map.insert(Rule::new(selector.clone(),
-                             rule.clone(),
-                             self.rules_source_order));
-    }
-
-    #[inline]
-    fn note_for_revalidation(&mut self, selector: &Selector<SelectorImpl>) {
-        if needs_revalidation(selector) {
-            self.selectors_for_cache_revalidation.insert(selector.inner.clone());
         }
     }
 
     /// Returns whether the given attribute might appear in an attribute
     /// selector of some rule in the stylist.
     pub fn might_have_attribute_dependency(&self,
                                            local_name: &LocalName)
                                            -> bool {
-        #[cfg(feature = "servo")]
-        let style_lower_name = local_name!("style");
-        #[cfg(feature = "gecko")]
-        let style_lower_name = atom!("style");
-
-        if *local_name == style_lower_name {
+        if *local_name == local_name!("style") {
             self.style_attribute_dependency
         } else {
             self.attribute_dependencies.might_contain(local_name)
         }
     }
 
     /// Returns whether the given ElementState bit is relied upon by a selector
     /// of some rule in the stylist.
     pub fn has_state_dependency(&self, state: ElementState) -> bool {
         self.state_dependencies.intersects(state)
     }
 
-    #[inline]
-    fn note_attribute_and_state_dependencies(&mut self, selector: &Selector<SelectorImpl>) {
-        selector.visit(&mut AttributeAndStateDependencyVisitor(self));
-    }
-
     /// Computes the style for a given "precomputed" pseudo-element, taking the
     /// universal rules and applying them.
     ///
     /// If `inherit_all` is true, then all properties are inherited from the
     /// parent; otherwise, non-inherited properties are reset to their initial
     /// values. The flow constructor uses this flag when constructing anonymous
     /// flows.
     pub fn precomputed_values_for_pseudo(&self,
@@ -786,54 +811,72 @@ impl Stylist {
 
         self.viewport_constraints =
             ViewportConstraints::maybe_new(&device, &cascaded_rule, self.quirks_mode);
 
         if let Some(ref constraints) = self.viewport_constraints {
             device.account_for_viewport_rule(constraints);
         }
 
-        fn mq_eval_changed(guard: &SharedRwLockReadGuard, rules: &[CssRule],
-                           before: &Device, after: &Device, quirks_mode: QuirksMode) -> bool {
-            for rule in rules {
-                let changed = rule.with_nested_rules_mq_and_doc_rule(guard,
-                                                                     |result| {
-                    let rules = match result {
-                        NestedRulesResult::Rules(rules) => rules,
-                        NestedRulesResult::RulesWithMediaQueries(rules, mq) => {
-                            if mq.evaluate(before, quirks_mode) != mq.evaluate(after, quirks_mode) {
-                                return true;
-                            }
-                            rules
-                        },
-                        NestedRulesResult::RulesWithDocument(rules, doc_rule) => {
-                            if !doc_rule.condition.evaluate(before) {
-                                return false;
-                            }
-                            rules
-                        },
-                    };
-                    mq_eval_changed(guard, rules, before, after, quirks_mode)
-                });
-                if changed {
-                    return true
-                }
-            }
-            false
-        }
         self.is_device_dirty |= stylesheets.iter().any(|stylesheet| {
             let mq = stylesheet.media.read_with(guard);
             if mq.evaluate(&self.device, self.quirks_mode) != mq.evaluate(&device, self.quirks_mode) {
                 return true
             }
 
-            mq_eval_changed(guard, &stylesheet.rules.read_with(guard).0, &self.device, &device, self.quirks_mode)
+            let mut iter =
+                stylesheet.iter_rules::<PotentiallyEffectiveMediaRules>(
+                    &self.device,
+                    guard);
+
+            while let Some(rule) = iter.next() {
+                match *rule {
+                    CssRule::Style(..) |
+                    CssRule::Namespace(..) |
+                    CssRule::FontFace(..) |
+                    CssRule::CounterStyle(..) |
+                    CssRule::Supports(..) |
+                    CssRule::Keyframes(..) |
+                    CssRule::Page(..) |
+                    CssRule::Viewport(..) |
+                    CssRule::Document(..) => {
+                        // Not affected by device changes.
+                        continue;
+                    }
+                    CssRule::Import(ref lock) => {
+                        let import_rule = lock.read_with(guard);
+                        let mq = import_rule.stylesheet.media.read_with(guard);
+                        let effective_now = mq.evaluate(&self.device, self.quirks_mode);
+                        if effective_now != mq.evaluate(&device, self.quirks_mode) {
+                            return true;
+                        }
+
+                        if !effective_now {
+                            iter.skip_children();
+                        }
+                    }
+                    CssRule::Media(ref lock) => {
+                        let media_rule = lock.read_with(guard);
+                        let mq = media_rule.media_queries.read_with(guard);
+                        let effective_now = mq.evaluate(&self.device, self.quirks_mode);
+                        if effective_now != mq.evaluate(&device, self.quirks_mode) {
+                            return true;
+                        }
+
+                        if !effective_now {
+                            iter.skip_children();
+                        }
+                    }
+                }
+            }
+
+            return false;
         });
 
-        self.device = Arc::new(device);
+        self.device = device;
     }
 
     /// Returns the viewport constraints that apply to this document because of
     /// a @viewport rule.
     pub fn viewport_constraints(&self) -> Option<&ViewportConstraints> {
         self.viewport_constraints.as_ref()
     }
 
@@ -1114,17 +1157,17 @@ impl Stylist {
     }
 
     /// Accessor for a shared reference to the device.
     pub fn device(&self) -> &Device {
         &self.device
     }
 
     /// Accessor for a mutable reference to the device.
-    pub fn device_mut(&mut self) -> &mut Arc<Device> {
+    pub fn device_mut(&mut self) -> &mut Device {
         &mut self.device
     }
 
     /// Accessor for a shared reference to the rule tree.
     pub fn rule_tree(&self) -> &RuleTree {
         &self.rule_tree
     }
 }
@@ -1141,41 +1184,45 @@ impl Drop for Stylist {
         // TODO(emilio): We can at least assert all the elements in the free
         // list are indeed free.
         unsafe { self.rule_tree.gc(); }
     }
 }
 
 /// Visitor to collect names that appear in attribute selectors and any
 /// dependencies on ElementState bits.
-struct AttributeAndStateDependencyVisitor<'a>(&'a mut Stylist);
+struct AttributeAndStateDependencyVisitor<'a> {
+    attribute_dependencies: &'a mut BloomFilter,
+    style_attribute_dependency: &'a mut bool,
+    state_dependencies: &'a mut ElementState,
+}
 
 impl<'a> SelectorVisitor for AttributeAndStateDependencyVisitor<'a> {
     type Impl = SelectorImpl;
 
     fn visit_attribute_selector(&mut self, _ns: &NamespaceConstraint<&Namespace>,
                                 name: &LocalName, lower_name: &LocalName)
                                 -> bool {
         #[cfg(feature = "servo")]
         let style_lower_name = local_name!("style");
         #[cfg(feature = "gecko")]
         let style_lower_name = atom!("style");
 
         if *lower_name == style_lower_name {
-            self.0.style_attribute_dependency = true;
+            *self.style_attribute_dependency = true;
         } else {
-            self.0.attribute_dependencies.insert(&name);
-            self.0.attribute_dependencies.insert(&lower_name);
+            self.attribute_dependencies.insert(&name);
+            self.attribute_dependencies.insert(&lower_name);
         }
         true
     }
 
     fn visit_simple_selector(&mut self, s: &Component<SelectorImpl>) -> bool {
         if let Component::NonTSPseudoClass(ref p) = *s {
-            self.0.state_dependencies.insert(p.state_flag());
+            self.state_dependencies.insert(p.state_flag());
         }
         true
     }
 }
 
 /// Visitor determine whether a selector requires cache revalidation.
 ///
 /// Note that we just check simple selectors and eagerly return when the first
--- a/servo/ports/geckolib/glue.rs
+++ b/servo/ports/geckolib/glue.rs
@@ -21,16 +21,17 @@ use style::error_reporting::RustLogRepor
 use style::font_metrics::get_metrics_provider_for_product;
 use style::gecko::data::{PerDocumentStyleData, PerDocumentStyleDataImpl};
 use style::gecko::global_style_data::{GLOBAL_STYLE_DATA, GlobalStyleData};
 use style::gecko::restyle_damage::GeckoRestyleDamage;
 use style::gecko::selector_parser::PseudoElement;
 use style::gecko::traversal::RecalcStyleOnly;
 use style::gecko::wrapper::GeckoElement;
 use style::gecko_bindings::bindings;
+use style::gecko_bindings::bindings::{RawGeckoElementBorrowed, RawGeckoElementBorrowedOrNull};
 use style::gecko_bindings::bindings::{RawGeckoKeyframeListBorrowed, RawGeckoKeyframeListBorrowedMut};
 use style::gecko_bindings::bindings::{RawServoDeclarationBlockBorrowed, RawServoDeclarationBlockStrong};
 use style::gecko_bindings::bindings::{RawServoDocumentRule, RawServoDocumentRuleBorrowed};
 use style::gecko_bindings::bindings::{RawServoKeyframe, RawServoKeyframeBorrowed, RawServoKeyframeStrong};
 use style::gecko_bindings::bindings::{RawServoKeyframesRule, RawServoKeyframesRuleBorrowed};
 use style::gecko_bindings::bindings::{RawServoMediaList, RawServoMediaListBorrowed, RawServoMediaListStrong};
 use style::gecko_bindings::bindings::{RawServoMediaRule, RawServoMediaRuleBorrowed};
 use style::gecko_bindings::bindings::{RawServoNamespaceRule, RawServoNamespaceRuleBorrowed};
@@ -45,17 +46,16 @@ use style::gecko_bindings::bindings::Gec
 use style::gecko_bindings::bindings::Gecko_GetOrCreateFinalKeyframe;
 use style::gecko_bindings::bindings::Gecko_GetOrCreateInitialKeyframe;
 use style::gecko_bindings::bindings::Gecko_GetOrCreateKeyframeAtStart;
 use style::gecko_bindings::bindings::Gecko_NewNoneTransform;
 use style::gecko_bindings::bindings::RawGeckoAnimationPropertySegmentBorrowed;
 use style::gecko_bindings::bindings::RawGeckoCSSPropertyIDListBorrowed;
 use style::gecko_bindings::bindings::RawGeckoComputedKeyframeValuesListBorrowedMut;
 use style::gecko_bindings::bindings::RawGeckoComputedTimingBorrowed;
-use style::gecko_bindings::bindings::RawGeckoElementBorrowed;
 use style::gecko_bindings::bindings::RawGeckoFontFaceRuleListBorrowedMut;
 use style::gecko_bindings::bindings::RawGeckoServoStyleRuleListBorrowedMut;
 use style::gecko_bindings::bindings::RawServoAnimationValueBorrowed;
 use style::gecko_bindings::bindings::RawServoAnimationValueMapBorrowedMut;
 use style::gecko_bindings::bindings::RawServoAnimationValueStrong;
 use style::gecko_bindings::bindings::RawServoImportRuleBorrowed;
 use style::gecko_bindings::bindings::RawServoStyleRuleBorrowed;
 use style::gecko_bindings::bindings::ServoComputedValuesBorrowedOrNull;
@@ -727,62 +727,90 @@ pub extern "C" fn Servo_StyleSheet_Clear
     Stylesheet::update_from_str(&sheet, input, url_data, loader,
                                 &RustLogReporter, line_number_offset as u64);
 }
 
 #[no_mangle]
 pub extern "C" fn Servo_StyleSet_AppendStyleSheet(raw_data: RawServoStyleSetBorrowed,
                                                   raw_sheet: RawServoStyleSheetBorrowed,
                                                   unique_id: u64) {
+    let global_style_data = &*GLOBAL_STYLE_DATA;
     let mut data = PerDocumentStyleData::from_ffi(raw_data).borrow_mut();
+    let mut data = &mut *data;
     let sheet = HasArcFFI::as_arc(&raw_sheet);
-    data.stylesheets.append_stylesheet(sheet, unique_id);
+    let guard = global_style_data.shared_lock.read();
+    data.stylesheets.append_stylesheet(
+        &data.stylist,
+        sheet,
+        unique_id,
+        &guard);
     data.clear_stylist();
 }
 
 #[no_mangle]
 pub extern "C" fn Servo_StyleSet_PrependStyleSheet(raw_data: RawServoStyleSetBorrowed,
                                                    raw_sheet: RawServoStyleSheetBorrowed,
                                                    unique_id: u64) {
+    let global_style_data = &*GLOBAL_STYLE_DATA;
     let mut data = PerDocumentStyleData::from_ffi(raw_data).borrow_mut();
+    let mut data = &mut *data;
     let sheet = HasArcFFI::as_arc(&raw_sheet);
-    data.stylesheets.prepend_stylesheet(sheet, unique_id);
+    let guard = global_style_data.shared_lock.read();
+    data.stylesheets.prepend_stylesheet(
+        &data.stylist,
+        sheet,
+        unique_id,
+        &guard);
     data.clear_stylist();
 }
 
 #[no_mangle]
 pub extern "C" fn Servo_StyleSet_InsertStyleSheetBefore(raw_data: RawServoStyleSetBorrowed,
                                                         raw_sheet: RawServoStyleSheetBorrowed,
                                                         unique_id: u64,
                                                         before_unique_id: u64) {
+    let global_style_data = &*GLOBAL_STYLE_DATA;
     let mut data = PerDocumentStyleData::from_ffi(raw_data).borrow_mut();
+    let mut data = &mut *data;
     let sheet = HasArcFFI::as_arc(&raw_sheet);
-    data.stylesheets.insert_stylesheet_before(sheet, unique_id, before_unique_id);
+    let guard = global_style_data.shared_lock.read();
+    data.stylesheets.insert_stylesheet_before(
+        &data.stylist,
+        sheet,
+        unique_id,
+        before_unique_id,
+        &guard);
     data.clear_stylist();
 }
 
 #[no_mangle]
 pub extern "C" fn Servo_StyleSet_RemoveStyleSheet(raw_data: RawServoStyleSetBorrowed,
                                                   unique_id: u64) {
     let mut data = PerDocumentStyleData::from_ffi(raw_data).borrow_mut();
     data.stylesheets.remove_stylesheet(unique_id);
     data.clear_stylist();
 }
 
 #[no_mangle]
-pub extern "C" fn Servo_StyleSet_FlushStyleSheets(raw_data: RawServoStyleSetBorrowed) {
+pub extern "C" fn Servo_StyleSet_FlushStyleSheets(
+    raw_data: RawServoStyleSetBorrowed,
+    doc_element: RawGeckoElementBorrowedOrNull)
+{
     let global_style_data = &*GLOBAL_STYLE_DATA;
     let guard = global_style_data.shared_lock.read();
     let mut data = PerDocumentStyleData::from_ffi(raw_data).borrow_mut();
-    data.flush_stylesheets(&guard);
+    let doc_element = doc_element.map(GeckoElement);
+    data.flush_stylesheets(&guard, doc_element);
 }
 
 #[no_mangle]
-pub extern "C" fn Servo_StyleSet_NoteStyleSheetsChanged(raw_data: RawServoStyleSetBorrowed,
-                                                        author_style_disabled: bool) {
+pub extern "C" fn Servo_StyleSet_NoteStyleSheetsChanged(
+    raw_data: RawServoStyleSetBorrowed,
+    author_style_disabled: bool)
+{
     let mut data = PerDocumentStyleData::from_ffi(raw_data).borrow_mut();
     data.stylesheets.force_dirty();
     data.stylesheets.set_author_style_disabled(author_style_disabled);
     data.clear_stylist();
 }
 
 #[no_mangle]
 pub extern "C" fn Servo_StyleSheet_HasRules(raw_sheet: RawServoStyleSheetBorrowed) -> bool {
--- a/servo/tests/unit/style/media_queries.rs
+++ b/servo/tests/unit/style/media_queries.rs
@@ -8,17 +8,17 @@ use servo_url::ServoUrl;
 use std::borrow::ToOwned;
 use style::Atom;
 use style::context::QuirksMode;
 use style::error_reporting::ParseErrorReporter;
 use style::media_queries::*;
 use style::servo::media_queries::*;
 use style::shared_lock::{SharedRwLock, SharedRwLockReadGuard};
 use style::stylearc::Arc;
-use style::stylesheets::{Stylesheet, Origin, CssRule, NestedRulesResult};
+use style::stylesheets::{AllRules, Stylesheet, Origin, CssRule};
 use style::values::specified;
 use style_traits::ToCss;
 
 pub struct CSSErrorReporterTest;
 
 impl ParseErrorReporter for CSSErrorReporterTest {
     fn report_error(&self,
                     _input: &mut Parser,
@@ -34,43 +34,28 @@ fn test_media_rule<F>(css: &str, callbac
 {
     let url = ServoUrl::parse("http://localhost").unwrap();
     let css_str = css.to_owned();
     let lock = SharedRwLock::new();
     let media_list = Arc::new(lock.wrap(MediaList::empty()));
     let stylesheet = Stylesheet::from_str(
         css, url, Origin::Author, media_list, lock,
         None, &CSSErrorReporterTest, QuirksMode::NoQuirks, 0u64);
+    let dummy = Device::new(MediaType::Screen, TypedSize2D::new(200.0, 100.0));
     let mut rule_count = 0;
     let guard = stylesheet.shared_lock.read();
-    media_queries(&guard, &stylesheet.rules.read_with(&guard).0, &mut |mq| {
-        rule_count += 1;
-        callback(mq, css);
-    });
+    for rule in stylesheet.iter_rules::<AllRules>(&dummy, &guard) {
+        if let CssRule::Media(ref lock) = *rule {
+            rule_count += 1;
+            callback(&lock.read_with(&guard).media_queries.read_with(&guard), css);
+        }
+    }
     assert!(rule_count > 0, css_str);
 }
 
-fn media_queries<F>(guard: &SharedRwLockReadGuard, rules: &[CssRule], f: &mut F)
-    where F: FnMut(&MediaList),
-{
-    for rule in rules {
-        rule.with_nested_rules_mq_and_doc_rule(guard, |result| {
-            match result {
-                NestedRulesResult::Rules(rules) |
-                NestedRulesResult::RulesWithDocument(rules, _) => {
-                    media_queries(guard, rules, f)
-                },
-                NestedRulesResult::RulesWithMediaQueries(_, mq) => {
-                    f(mq)
-                }
-            }
-        })
-    }
-}
-
 fn media_query_test(device: &Device, css: &str, expected_rule_count: usize) {
     let url = ServoUrl::parse("http://localhost").unwrap();
     let lock = SharedRwLock::new();
     let media_list = Arc::new(lock.wrap(MediaList::empty()));
     let ss = Stylesheet::from_str(
         css, url, Origin::Author, media_list, lock,
         None, &CSSErrorReporterTest, QuirksMode::NoQuirks, 0u64);
     let mut rule_count = 0;