Cache effective media query results.

This patch also makes RulesIterator not iterate over rules for which we don't
process nested rules.

There's nothing depending on this behavior right now afaik, and this will make
us duplicate less code in following patches.

Bug: https://bugzilla.mozilla.org/show_bug.cgi?id=1357461
MozReview-Commit-ID: CaMFQtAVnJF

5 files changed, 223 insertions, 87 deletions

diff --git a/components/style/invalidation/media_queries.rs b/components/style/invalidation/media_queries.rs
new file mode 100644
index 00000000000..46eca61a3a1
--- /dev/null
+++ b/components/style/invalidation/media_queries.rs
@@ -0,0 +1,133 @@
+/* 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/. */
+
+//! Code related to the invalidation of media-query-affected rules.
+
+use context::QuirksMode;
+use fnv::FnvHashSet;
+use media_queries::Device;
+use shared_lock::SharedRwLockReadGuard;
+use stylesheets::{DocumentRule, ImportRule, MediaRule,  SupportsRule};
+use stylesheets::{NestedRuleIterationCondition, Stylesheet};
+
+/// A key for a given media query result.
+///
+/// NOTE: It happens to be the case that all the media lists we care about
+/// happen to have a stable address, so we can just use an opaque pointer to
+/// represent them.
+///
+/// Also, note that right now when a rule or stylesheet is removed, we do a full
+/// style flush, so there's no need to worry about other item created with the
+/// same pointer address.
+///
+/// If this changes, though, we may need to remove the item from the cache if
+/// present before it goes away.
+#[derive(Debug, Copy, Clone, Hash, Eq, PartialEq)]
+#[cfg_attr(feature = "servo", derive(HeapSizeOf))]
+pub struct MediaListKey(usize);
+
+/// A trait to get a given `MediaListKey` for a given item that can hold a
+/// `MediaList`.
+pub trait ToMediaListKey : Sized {
+    /// Get a `MediaListKey` for this item. This key needs to uniquely identify
+    /// the item.
+    #[allow(unsafe_code)]
+    fn to_media_list_key(&self) -> MediaListKey {
+        use std::mem;
+        MediaListKey(unsafe { mem::transmute(self as *const Self) })
+    }
+}
+
+impl ToMediaListKey for Stylesheet {}
+impl ToMediaListKey for ImportRule {}
+impl ToMediaListKey for MediaRule {}
+
+/// A struct that holds the result of a media query evaluation pass for the
+/// media queries that evaluated successfully.
+#[cfg_attr(feature = "servo", derive(HeapSizeOf))]
+pub struct EffectiveMediaQueryResults {
+    /// The set of media lists that matched last time.
+    set: FnvHashSet<MediaListKey>,
+}
+
+impl EffectiveMediaQueryResults {
+    /// Trivially constructs an empty `EffectiveMediaQueryResults`.
+    pub fn new() -> Self {
+        Self {
+            set: FnvHashSet::default(),
+        }
+    }
+
+    /// Resets the results, using an empty key.
+    pub fn clear(&mut self) {
+        self.set.clear()
+    }
+
+    /// Returns whether a given item was known to be effective when the results
+    /// were cached.
+    pub fn was_effective<T>(&self, item: &T) -> bool
+        where T: ToMediaListKey,
+    {
+        self.set.contains(&item.to_media_list_key())
+    }
+
+    /// Notices that an effective item has been seen, and caches it as matching.
+    pub fn saw_effective<T>(&mut self, item: &T)
+        where T: ToMediaListKey,
+    {
+        // NOTE(emilio): We can't assert that we don't cache the same item twice
+        // because of stylesheet reusing... shrug.
+        self.set.insert(item.to_media_list_key());
+    }
+}
+
+/// 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)
+    }
+}
diff --git a/components/style/invalidation/mod.rs b/components/style/invalidation/mod.rs
index 6107894b00d..4b7f9c3cd65 100644
--- a/components/style/invalidation/mod.rs
+++ b/components/style/invalidation/mod.rs
@@ -4,4 +4,5 @@
 
 //! Different bits of code related to invalidating style.
 
+pub mod media_queries;
 pub mod stylesheets;
diff --git a/components/style/stylesheet_set.rs b/components/style/stylesheet_set.rs
index 5746446d2cf..15bbf285a69 100644
--- a/components/style/stylesheet_set.rs
+++ b/components/style/stylesheet_set.rs
@@ -175,6 +175,11 @@ impl StylesheetSet {
         self.dirty = false;
         self.invalidations.flush(document_element);
 
+        self.iter()
+    }
+
+    /// Returns an iterator over the current list of stylesheets.
+    pub fn iter(&self) -> StylesheetIterator {
         StylesheetIterator(self.entries.iter())
     }
 
diff --git a/components/style/stylesheets.rs b/components/style/stylesheets.rs
index 6347e39f0e9..23dad0d1c55 100644
--- a/components/style/stylesheets.rs
+++ b/components/style/stylesheets.rs
@@ -1048,7 +1048,6 @@ impl NestedRuleIterationCondition for AllRules {
         true
     }
 
-    /// Whether we should process the nested rules in a given `@media` rule.
     fn process_media(
         _: &SharedRwLockReadGuard,
         _: &Device,
@@ -1059,7 +1058,6 @@ impl NestedRuleIterationCondition for AllRules {
         true
     }
 
-    /// Whether we should process the nested rules in a given `@-moz-document` rule.
     fn process_document(
         _: &SharedRwLockReadGuard,
         _: &Device,
@@ -1070,7 +1068,6 @@ impl NestedRuleIterationCondition for AllRules {
         true
     }
 
-    /// Whether we should process the nested rules in a given `@supports` rule.
     fn process_supports(
         _: &SharedRwLockReadGuard,
         _: &Device,
@@ -1158,36 +1155,31 @@ impl<'a, 'b, C> Iterator for RulesIterator<'a, 'b, C>
                 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
+                        if !C::process_import(self.guard, self.device, self.quirks_mode, import_rule) {
+                            continue;
                         }
+                        Some(import_rule.stylesheet.rules.read_with(self.guard).0.iter())
                     }
                     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
+                        if !C::process_document(self.guard, self.device, self.quirks_mode, doc_rule) {
+                            continue;
                         }
+                        Some(doc_rule.rules.read_with(self.guard).0.iter())
                     }
                     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
+                        if !C::process_media(self.guard, self.device, self.quirks_mode, media_rule) {
+                            continue;
                         }
+                        Some(media_rule.rules.read_with(self.guard).0.iter())
                     }
                     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
+                        if !C::process_supports(self.guard, self.device, self.quirks_mode, supports_rule) {
+                            continue;
                         }
+                        Some(supports_rule.rules.read_with(self.guard).0.iter())
                     }
                     CssRule::Namespace(_) |
                     CssRule::Style(_) |
diff --git a/components/style/stylist.rs b/components/style/stylist.rs
index eb2d43cf16c..a9087b18812 100644
--- a/components/style/stylist.rs
+++ b/components/style/stylist.rs
@@ -14,6 +14,7 @@ use error_reporting::RustLogReporter;
 use font_metrics::FontMetricsProvider;
 #[cfg(feature = "gecko")]
 use gecko_bindings::structs::{nsIAtom, StyleRuleInclusion};
+use invalidation::media_queries::EffectiveMediaQueryResults;
 use keyframes::KeyframesAnimation;
 use media_queries::Device;
 use properties::{self, CascadeFlags, ComputedValues};
@@ -39,9 +40,8 @@ use style_traits::viewport::ViewportConstraints;
 use stylearc::Arc;
 #[cfg(feature = "gecko")]
 use stylesheets::{CounterStyleRule, FontFaceRule};
-use stylesheets::{CssRule, DocumentRule, ImportRule, MediaRule, StyleRule, SupportsRule};
+use stylesheets::{CssRule, StyleRule};
 use stylesheets::{Stylesheet, Origin, UserAgentStylesheets};
-use stylesheets::NestedRuleIterationCondition;
 use thread_state;
 use viewport::{self, MaybeNew, ViewportRule};
 
@@ -83,6 +83,9 @@ pub struct Stylist {
     /// Viewport constraints based on the current device.
     viewport_constraints: Option<ViewportConstraints>,
 
+    /// Effective media query results cached from the last rebuild.
+    effective_media_query_results: EffectiveMediaQueryResults,
+
     /// If true, the quirks-mode stylesheet is applied.
     quirks_mode: QuirksMode,
 
@@ -222,57 +225,6 @@ impl From<StyleRuleInclusion> for RuleInclusion {
     }
 }
 
-/// 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
@@ -285,6 +237,7 @@ impl Stylist {
             is_device_dirty: true,
             is_cleared: true,
             quirks_mode: quirks_mode,
+            effective_media_query_results: EffectiveMediaQueryResults::new(),
 
             element_map: PerPseudoElementSelectorMap::new(),
             pseudos_map: Default::default(),
@@ -355,6 +308,7 @@ impl Stylist {
 
         self.is_cleared = true;
 
+        self.effective_media_query_results.clear();
         self.viewport_constraints = None;
         // preserve current device
         self.is_device_dirty = true;
@@ -482,6 +436,8 @@ impl Stylist {
             return;
         }
 
+        self.effective_media_query_results.saw_effective(stylesheet);
+
         for rule in stylesheet.effective_rules(&self.device, guard) {
             match *rule {
                 CssRule::Style(ref locked) => {
@@ -515,10 +471,17 @@ impl Stylist {
                     }
                     self.rules_source_order += 1;
                 }
-                CssRule::Import(..) => {
-                    // effective_rules visits the inner stylesheet if
+                CssRule::Import(ref lock) => {
+                    let import_rule = lock.read_with(guard);
+                    self.effective_media_query_results.saw_effective(import_rule);
+
+                    // NOTE: effective_rules visits the inner stylesheet if
                     // appropriate.
                 }
+                CssRule::Media(ref lock) => {
+                    let media_rule = lock.read_with(guard);
+                    self.effective_media_query_results.saw_effective(media_rule);
+                }
                 CssRule::Keyframes(ref keyframes_rule) => {
                     let keyframes_rule = keyframes_rule.read_with(guard);
                     debug!("Found valid keyframes rule: {:?}", *keyframes_rule);
@@ -816,16 +779,50 @@ impl Stylist {
             device.account_for_viewport_rule(constraints);
         }
 
-        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) {
+        self.device = device;
+        let features_changed = self.media_features_change_changed_style(
+            stylesheets.iter(),
+            guard
+        );
+        self.is_device_dirty |= features_changed;
+    }
+
+    /// Returns whether, given a media feature change, any previously-applicable
+    /// style has become non-applicable, or vice-versa.
+    pub fn media_features_change_changed_style<'a, I>(
+        &self,
+        stylesheets: I,
+        guard: &SharedRwLockReadGuard,
+    ) -> bool
+        where I: Iterator<Item = &'a Arc<Stylesheet>>
+    {
+        use invalidation::media_queries::PotentiallyEffectiveMediaRules;
+
+        debug!("Stylist::media_features_change_changed_style");
+
+        for stylesheet in stylesheets {
+            let effective_now =
+                stylesheet.media.read_with(guard)
+                    .evaluate(&self.device, self.quirks_mode);
+
+            let effective_then =
+                self.effective_media_query_results.was_effective(&**stylesheet);
+
+            if effective_now != effective_then {
+                debug!(" > Stylesheet changed -> {}, {}",
+                       effective_then, effective_now);
                 return true
             }
 
+            if !effective_now {
+                continue;
+            }
+
             let mut iter =
                 stylesheet.iter_rules::<PotentiallyEffectiveMediaRules>(
                     &self.device,
-                    guard);
+                    guard
+                );
 
             while let Some(rule) = iter.next() {
                 match *rule {
@@ -844,8 +841,13 @@ impl Stylist {
                     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) {
+                        let effective_now =
+                            mq.evaluate(&self.device, self.quirks_mode);
+                        let effective_then =
+                            self.effective_media_query_results.was_effective(import_rule);
+                        if effective_now != effective_then {
+                            debug!(" > @import rule changed {} -> {}",
+                                   effective_then, effective_now);
                             return true;
                         }
 
@@ -856,8 +858,13 @@ impl Stylist {
                     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) {
+                        let effective_now =
+                            mq.evaluate(&self.device, self.quirks_mode);
+                        let effective_then =
+                            self.effective_media_query_results.was_effective(media_rule);
+                        if effective_now != effective_then {
+                            debug!(" > @media rule changed {} -> {}",
+                                   effective_then, effective_now);
                             return true;
                         }
 
@@ -867,11 +874,9 @@ impl Stylist {
                     }
                 }
             }
+        }
 
-            return false;
-        });
-
-        self.device = device;
+        return false;
     }
 
     /// Returns the viewport constraints that apply to this document because of