--- a/servo/components/servo_arc/lib.rs
+++ b/servo/components/servo_arc/lib.rs
@@ -117,16 +117,22 @@ impl<T: ?Sized + 'static> fmt::Debug for
 impl<T: ?Sized + 'static> PartialEq for NonZeroPtrMut<T> {
     fn eq(&self, other: &Self) -> bool {
         self.ptr() == other.ptr()
     }
 }
 
 impl<T: ?Sized + 'static> Eq for NonZeroPtrMut<T> {}
 
+impl<T: Sized + 'static> Hash for NonZeroPtrMut<T> {
+    fn hash<H: Hasher>(&self, state: &mut H) {
+        self.ptr().hash(state)
+    }
+}
+
 pub struct Arc<T: ?Sized + 'static> {
     p: NonZeroPtrMut<ArcInner<T>>,
 }
 
 /// An Arc that is known to be uniquely owned
 ///
 /// This lets us build arcs that we can mutate before
 /// freezing, without needing to change the allocation

--- a/servo/components/style/context.rs
+++ b/servo/components/style/context.rs
@@ -15,16 +15,17 @@ use euclid::ScaleFactor;
 use euclid::Size2D;
 use fnv::FnvHashMap;
 use font_metrics::FontMetricsProvider;
 #[cfg(feature = "gecko")] use gecko_bindings::structs;
 use parallel::{STACK_SAFETY_MARGIN_KB, STYLE_THREAD_STACK_SIZE_KB};
 #[cfg(feature = "servo")] use parking_lot::RwLock;
 use properties::ComputedValues;
 #[cfg(feature = "servo")] use properties::PropertyId;
+use rule_cache::RuleCache;
 use rule_tree::StrongRuleNode;
 use selector_parser::{EAGER_PSEUDO_COUNT, SnapshotMap};
 use selectors::matching::ElementSelectorFlags;
 use servo_arc::Arc;
 #[cfg(feature = "servo")] use servo_atoms::Atom;
 use shared_lock::StylesheetGuards;
 use sharing::StyleSharingCache;
 use std::fmt;
@@ -675,16 +676,18 @@ impl StackLimitChecker {
 /// A thread-local style context.
 ///
 /// This context contains data that needs to be used during restyling, but is
 /// not required to be unique among worker threads, so we create one per worker
 /// thread in order to be able to mutate it without locking.
 pub struct ThreadLocalStyleContext<E: TElement> {
     /// A cache to share style among siblings.
     pub sharing_cache: StyleSharingCache<E>,
+    /// A cache from matched properties to elements that match those.
+    pub rule_cache: RuleCache,
     /// The bloom filter used to fast-reject selector-matching.
     pub bloom_filter: StyleBloom<E>,
     /// A channel on which new animations that have been triggered by style
     /// recalculation can be sent.
     #[cfg(feature = "servo")]
     pub new_animations_sender: Sender<Animation>,
     /// A set of tasks to be run (on the parent thread) in sequential mode after
     /// the rest of the styling is complete. This is useful for
@@ -712,16 +715,17 @@ pub struct ThreadLocalStyleContext<E: TE
 }
 
 impl<E: TElement> ThreadLocalStyleContext<E> {
     /// Creates a new `ThreadLocalStyleContext` from a shared one.
     #[cfg(feature = "servo")]
     pub fn new(shared: &SharedStyleContext) -> Self {
         ThreadLocalStyleContext {
             sharing_cache: StyleSharingCache::new(),
+            rule_cache: RuleCache::new(),
             bloom_filter: StyleBloom::new(),
             new_animations_sender: shared.local_context_creation_data.lock().unwrap().new_animations_sender.clone(),
             tasks: SequentialTaskList(Vec::new()),
             selector_flags: SelectorFlagsMap::new(),
             statistics: TraversalStatistics::default(),
             current_element_info: None,
             font_metrics_provider: E::FontMetricsProvider::create_from(shared),
             stack_limit_checker: StackLimitChecker::new(
@@ -729,16 +733,17 @@ impl<E: TElement> ThreadLocalStyleContex
         }
     }
 
     #[cfg(feature = "gecko")]
     /// Creates a new `ThreadLocalStyleContext` from a shared one.
     pub fn new(shared: &SharedStyleContext) -> Self {
         ThreadLocalStyleContext {
             sharing_cache: StyleSharingCache::new(),
+            rule_cache: RuleCache::new(),
             bloom_filter: StyleBloom::new(),
             tasks: SequentialTaskList(Vec::new()),
             selector_flags: SelectorFlagsMap::new(),
             statistics: TraversalStatistics::default(),
             current_element_info: None,
             font_metrics_provider: E::FontMetricsProvider::create_from(shared),
             stack_limit_checker: StackLimitChecker::new(
                 (STYLE_THREAD_STACK_SIZE_KB - STACK_SAFETY_MARGIN_KB) * 1024),

--- a/servo/components/style/gecko/media_queries.rs
+++ b/servo/components/style/gecko/media_queries.rs
@@ -18,17 +18,19 @@ use gecko_bindings::structs::{nsCSSKeywo
 use gecko_bindings::structs::{nsMediaExpression_Range, nsMediaFeature};
 use gecko_bindings::structs::{nsMediaFeature_ValueType, nsMediaFeature_RangeType, nsMediaFeature_RequirementFlags};
 use gecko_bindings::structs::{nsPresContext, RawGeckoPresContextOwned};
 use gecko_bindings::structs::nsIAtom;
 use media_queries::MediaType;
 use parser::ParserContext;
 use properties::{ComputedValues, StyleBuilder};
 use properties::longhands::font_size;
+use rule_cache::RuleCacheConditions;
 use servo_arc::Arc;
+use std::cell::RefCell;
 use std::fmt::{self, Write};
 use std::sync::atomic::{AtomicBool, AtomicIsize, Ordering};
 use str::starts_with_ignore_ascii_case;
 use string_cache::Atom;
 use style_traits::{CSSPixel, DevicePixel};
 use style_traits::{ToCss, ParseError, StyleParseError};
 use style_traits::viewport::ViewportConstraints;
 use values::{CSSFloat, CustomIdent, serialize_dimension};
@@ -689,25 +691,27 @@ impl Expression {
 
         let default_values = device.default_computed_values();
 
 
         let provider = get_metrics_provider_for_product();
 
         // http://dev.w3.org/csswg/mediaqueries3/#units
         // em units are relative to the initial font-size.
+        let mut conditions = RuleCacheConditions::default();
         let context = computed::Context {
             is_root_element: false,
             builder: StyleBuilder::for_derived_style(device, default_values, None, None),
             font_metrics_provider: &provider,
             cached_system_font: None,
             in_media_query: true,
             // TODO: pass the correct value here.
             quirks_mode: quirks_mode,
             for_smil_animation: false,
+            rule_cache_conditions: RefCell::new(&mut conditions),
         };
 
         let required_value = match self.value {
             Some(ref v) => v,
             None => {
                 // If there's no value, always match unless it's a zero length
                 // or a zero integer or boolean.
                 return match *actual_value {

--- a/servo/components/style/lib.rs
+++ b/servo/components/style/lib.rs
@@ -120,16 +120,17 @@ pub mod hash;
 pub mod invalidation;
 #[allow(missing_docs)] // TODO.
 pub mod logical_geometry;
 pub mod matching;
 pub mod media_queries;
 pub mod parallel;
 pub mod parser;
 pub mod rule_tree;
+pub mod rule_cache;
 pub mod scoped_tls;
 pub mod selector_map;
 pub mod selector_parser;
 pub mod shared_lock;
 pub mod sharing;
 pub mod style_resolver;
 pub mod stylist;
 #[cfg(feature = "servo")] #[allow(unsafe_code)] pub mod servo;

--- a/servo/components/style/properties/computed_value_flags.rs
+++ b/servo/components/style/properties/computed_value_flags.rs
@@ -54,10 +54,13 @@ bitflags! {
 
         /// Whether this style inherits the `content` property.
         ///
         /// Important because of the same reason.
         const INHERITS_CONTENT = 1 << 7,
 
         /// Whether the child explicitly inherits any reset property.
         const INHERITS_RESET_STYLE = 1 << 8,
+
+        /// A flag to mark a style which is a visited style.
+        const IS_STYLE_IF_VISITED = 1 << 9,
     }
 }

--- a/servo/components/style/properties/gecko.mako.rs
+++ b/servo/components/style/properties/gecko.mako.rs
@@ -47,17 +47,17 @@ use gecko_bindings::structs::root::NS_ST
 use gecko_bindings::sugar::ns_style_coord::{CoordDataValue, CoordData, CoordDataMut};
 use gecko::values::convert_nscolor_to_rgba;
 use gecko::values::convert_rgba_to_nscolor;
 use gecko::values::GeckoStyleCoordConvertible;
 use gecko::values::round_border_to_device_pixels;
 use logical_geometry::WritingMode;
 use media_queries::Device;
 use properties::animated_properties::TransitionProperty;
-use properties::computed_value_flags::ComputedValueFlags;
+use properties::computed_value_flags::*;
 use properties::{default_font_size_keyword, longhands, FontComputationData, Importance, LonghandId};
 use properties::{PropertyDeclaration, PropertyDeclarationBlock, PropertyDeclarationId};
 use rule_tree::StrongRuleNode;
 use selector_parser::PseudoElement;
 use servo_arc::{Arc, RawOffsetArc};
 use std::mem::{forget, uninitialized, transmute, zeroed};
 use std::{cmp, ops, ptr};
 use values::{self, Auto, CustomIdent, Either, KeyframesName, None_};
@@ -254,16 +254,21 @@ impl ops::Deref for ComputedValues {
 
 impl ops::DerefMut for ComputedValues {
     fn deref_mut(&mut self) -> &mut ComputedValuesInner {
         &mut self.0.mSource
     }
 }
 
 impl ComputedValuesInner {
+    /// Whether we're a visited style.
+    pub fn is_style_if_visited(&self) -> bool {
+        self.flags.contains(IS_STYLE_IF_VISITED)
+    }
+
     #[inline]
     pub fn is_display_contents(&self) -> bool {
         self.get_box().clone_display() == longhands::display::computed_value::T::contents
     }
 
     /// Returns true if the value of the `content` property would make a
     /// pseudo-element not rendered.
     #[inline]

--- a/servo/components/style/properties/helpers.mako.rs
+++ b/servo/components/style/properties/helpers.mako.rs
@@ -317,16 +317,20 @@
             % if not property.derived_from:
                 match value {
                     DeclaredValue::Value(specified_value) => {
                         % if property.ident in SYSTEM_FONT_LONGHANDS and product == "gecko":
                             if let Some(sf) = specified_value.get_system() {
                                 longhands::system_font::resolve_system_font(sf, context);
                             }
                         % endif
+                        % if property.logical:
+                            context.rule_cache_conditions.borrow_mut()
+                                .set_writing_mode_dependency(context.builder.writing_mode);
+                        % endif
                         % if property.is_vector:
                             // In the case of a vector property we want to pass
                             // down an iterator so that this can be computed
                             // without allocation
                             //
                             // However, computing requires a context, but the
                             // style struct being mutated is on the context. We
                             // temporarily remove it, mutate it, and then put it
@@ -358,16 +362,17 @@
                         % endif
                     }
                     DeclaredValue::WithVariables(_) => unreachable!(),
                     DeclaredValue::CSSWideKeyword(keyword) => match keyword {
                         % if not data.current_style_struct.inherited:
                         CSSWideKeyword::Unset |
                         % endif
                         CSSWideKeyword::Initial => {
+                            context.rule_cache_conditions.borrow_mut().set_uncacheable();
                             % if property.ident == "font_size":
                                 longhands::font_size::cascade_initial_font_size(context);
                             % else:
                                 context.builder.reset_${property.ident}();
                             % endif
                         },
                         % if data.current_style_struct.inherited:
                         CSSWideKeyword::Unset |

--- a/servo/components/style/properties/properties.mako.rs
+++ b/servo/components/style/properties/properties.mako.rs
@@ -11,16 +11,17 @@
 <%namespace name="helpers" file="/helpers.mako.rs" />
 
 use app_units::Au;
 use servo_arc::{Arc, UniqueArc};
 use smallbitvec::SmallBitVec;
 use std::borrow::Cow;
 use hash::HashSet;
 use std::{fmt, mem, ops};
+use std::cell::RefCell;
 #[cfg(feature = "gecko")] use std::ptr;
 
 #[cfg(feature = "servo")] use cssparser::RGBA;
 use cssparser::{CowRcStr, Parser, TokenSerializationType, serialize_identifier};
 use cssparser::ParserInput;
 #[cfg(feature = "servo")] use euclid::SideOffsets2D;
 use computed_values;
 use context::QuirksMode;
@@ -29,29 +30,30 @@ use font_metrics::FontMetricsProvider;
 #[cfg(feature = "gecko")] use gecko_bindings::structs::{self, nsCSSPropertyID};
 #[cfg(feature = "servo")] use logical_geometry::{LogicalMargin, PhysicalSide};
 use logical_geometry::WritingMode;
 #[cfg(feature = "gecko")] use malloc_size_of::{MallocShallowSizeOf, MallocSizeOf, MallocSizeOfOps};
 use media_queries::Device;
 use parser::ParserContext;
 use properties::animated_properties::AnimatableLonghand;
 #[cfg(feature = "gecko")] use properties::longhands::system_font::SystemFont;
+use rule_cache::{RuleCache, RuleCacheConditions};
 use selector_parser::PseudoElement;
 use selectors::parser::SelectorParseError;
 #[cfg(feature = "servo")] use servo_config::prefs::PREFS;
 use shared_lock::StylesheetGuards;
 use style_traits::{PARSING_MODE_DEFAULT, ToCss, ParseError};
 use style_traits::{PropertyDeclarationParseError, StyleParseError, ValueParseError};
 use stylesheets::{CssRuleType, Origin, UrlExtraData};
 #[cfg(feature = "servo")] use values::Either;
 use values::generics::text::LineHeight;
 use values::computed;
 use values::computed::NonNegativeLength;
 use rule_tree::{CascadeLevel, StrongRuleNode};
-use self::computed_value_flags::ComputedValueFlags;
+use self::computed_value_flags::*;
 use style_adjuster::StyleAdjuster;
 #[cfg(feature = "servo")] use values::specified::BorderStyle;
 
 pub use self::declaration_block::*;
 
 #[cfg(feature = "gecko")]
 #[macro_export]
 macro_rules! property_name {
@@ -2546,17 +2548,17 @@ pub struct StyleBuilder<'a> {
     reset_style: &'a ComputedValues,
 
     /// The style we're inheriting from explicitly, or none if we're the root of
     /// a subtree.
     parent_style: Option<<&'a ComputedValues>,
 
     /// The rule node representing the ordered list of rules matched for this
     /// node.
-    rules: Option<StrongRuleNode>,
+    pub rules: Option<StrongRuleNode>,
 
     custom_properties: Option<Arc<::custom_properties::CustomPropertiesMap>>,
 
     /// The pseudo-element this style will represent.
     pseudo: Option<<&'a PseudoElement>,
 
     /// The writing mode flags.
     ///
@@ -2582,17 +2584,17 @@ impl<'a> StyleBuilder<'a> {
         parent_style: Option<<&'a ComputedValues>,
         parent_style_ignoring_first_line: Option<<&'a ComputedValues>,
         pseudo: Option<<&'a PseudoElement>,
         cascade_flags: CascadeFlags,
         rules: Option<StrongRuleNode>,
         custom_properties: Option<Arc<::custom_properties::CustomPropertiesMap>>,
         writing_mode: WritingMode,
         font_size_keyword: FontComputationData,
-        flags: ComputedValueFlags,
+        mut flags: ComputedValueFlags,
         visited_style: Option<Arc<ComputedValues>>,
     ) -> Self {
         debug_assert_eq!(parent_style.is_some(), parent_style_ignoring_first_line.is_some());
         #[cfg(feature = "gecko")]
         debug_assert!(parent_style.is_none() ||
                       ptr::eq(parent_style.unwrap(),
                               parent_style_ignoring_first_line.unwrap()) ||
                       parent_style.unwrap().pseudo() == Some(PseudoElement::FirstLine));
@@ -2604,16 +2606,20 @@ impl<'a> StyleBuilder<'a> {
         // backgrounds, for example.  This code doesn't attempt to make it play
         // nice with inherited_style_ignoring_first_line.
         let reset_style = if cascade_flags.contains(INHERIT_ALL) {
             inherited_style
         } else {
             reset_style
         };
 
+        if cascade_flags.contains(VISITED_DEPENDENT_ONLY) {
+            flags.insert(IS_STYLE_IF_VISITED);
+        }
+
         StyleBuilder {
             device,
             parent_style,
             inherited_style,
             inherited_style_ignoring_first_line,
             reset_style,
             pseudo,
             rules,
@@ -2627,16 +2633,21 @@ impl<'a> StyleBuilder<'a> {
             ${style_struct.ident}: StyleStructRef::Borrowed(inherited_style.${style_struct.name_lower}_arc()),
             % else:
             ${style_struct.ident}: StyleStructRef::Borrowed(reset_style.${style_struct.name_lower}_arc()),
             % endif
             % endfor
         }
     }
 
+    /// Whether we're a visited style.
+    pub fn is_style_if_visited(&self) -> bool {
+        self.flags.contains(IS_STYLE_IF_VISITED)
+    }
+
     /// Creates a StyleBuilder holding only references to the structs of `s`, in
     /// order to create a derived style.
     pub fn for_derived_style(
         device: &'a Device,
         style_to_derive_from: &'a ComputedValues,
         parent_style: Option<<&'a ComputedValues>,
         pseudo: Option<<&'a PseudoElement>,
     ) -> Self {
@@ -2662,26 +2673,37 @@ impl<'a> StyleBuilder<'a> {
             % for style_struct in data.active_style_structs():
             ${style_struct.ident}: StyleStructRef::Borrowed(
                 style_to_derive_from.${style_struct.name_lower}_arc()
             ),
             % endfor
         }
     }
 
+    /// Copy the reset properties from `style`.
+    pub fn copy_reset_from(&mut self, style: &'a ComputedValues) {
+        % for style_struct in data.active_style_structs():
+        % if not style_struct.inherited:
+        self.${style_struct.ident} =
+            StyleStructRef::Borrowed(style.${style_struct.name_lower}_arc());
+        % endif
+        % endfor
+    }
+
     % for property in data.longhands:
     % if property.ident != "font_size":
     /// Inherit `${property.ident}` from our parent style.
     #[allow(non_snake_case)]
     pub fn inherit_${property.ident}(&mut self) {
         let inherited_struct =
         % if property.style_struct.inherited:
             self.inherited_style.get_${property.style_struct.name_lower}();
         % else:
-            self.inherited_style_ignoring_first_line.get_${property.style_struct.name_lower}();
+            self.inherited_style_ignoring_first_line
+                .get_${property.style_struct.name_lower}();
         % endif
 
         % if not property.style_struct.inherited:
         self.flags.insert(::properties::computed_value_flags::INHERITS_RESET_STYLE);
         % endif
 
         % if property.ident == "content":
         self.flags.insert(::properties::computed_value_flags::INHERITS_CONTENT);
@@ -3017,17 +3039,19 @@ pub fn cascade(
     rule_node: &StrongRuleNode,
     guards: &StylesheetGuards,
     parent_style: Option<<&ComputedValues>,
     parent_style_ignoring_first_line: Option<<&ComputedValues>,
     layout_parent_style: Option<<&ComputedValues>,
     visited_style: Option<Arc<ComputedValues>>,
     font_metrics_provider: &FontMetricsProvider,
     flags: CascadeFlags,
-    quirks_mode: QuirksMode
+    quirks_mode: QuirksMode,
+    rule_cache: Option<<&RuleCache>,
+    rule_cache_conditions: &mut RuleCacheConditions,
 ) -> Arc<ComputedValues> {
     debug_assert_eq!(parent_style.is_some(), parent_style_ignoring_first_line.is_some());
     #[cfg(feature = "gecko")]
     debug_assert!(parent_style.is_none() ||
                   ptr::eq(parent_style.unwrap(),
                           parent_style_ignoring_first_line.unwrap()) ||
                   parent_style.unwrap().pseudo() == Some(PseudoElement::FirstLine));
     let empty = SmallBitVec::new();
@@ -3077,16 +3101,18 @@ pub fn cascade(
         iter_declarations,
         parent_style,
         parent_style_ignoring_first_line,
         layout_parent_style,
         visited_style,
         font_metrics_provider,
         flags,
         quirks_mode,
+        rule_cache,
+        rule_cache_conditions,
     )
 }
 
 /// NOTE: This function expects the declaration with more priority to appear
 /// first.
 #[allow(unused_mut)] // conditionally compiled code for "position"
 pub fn apply_declarations<'a, F, I>(
     device: &Device,
@@ -3095,16 +3121,18 @@ pub fn apply_declarations<'a, F, I>(
     iter_declarations: F,
     parent_style: Option<<&ComputedValues>,
     parent_style_ignoring_first_line: Option<<&ComputedValues>,
     layout_parent_style: Option<<&ComputedValues>,
     visited_style: Option<Arc<ComputedValues>>,
     font_metrics_provider: &FontMetricsProvider,
     flags: CascadeFlags,
     quirks_mode: QuirksMode,
+    rule_cache: Option<<&RuleCache>,
+    rule_cache_conditions: &mut RuleCacheConditions,
 ) -> Arc<ComputedValues>
 where
     F: Fn() -> I,
     I: Iterator<Item = (&'a PropertyDeclaration, CascadeLevel)>,
 {
     debug_assert!(layout_parent_style.is_none() || parent_style.is_some());
     debug_assert_eq!(parent_style.is_some(), parent_style_ignoring_first_line.is_some());
     #[cfg(feature = "gecko")]
@@ -3151,21 +3179,22 @@ where
             flags,
             Some(rules.clone()),
             custom_properties,
             WritingMode::empty(),
             inherited_style.font_computation_data,
             ComputedValueFlags::empty(),
             visited_style,
         ),
-        font_metrics_provider: font_metrics_provider,
         cached_system_font: None,
         in_media_query: false,
-        quirks_mode: quirks_mode,
         for_smil_animation: false,
+        font_metrics_provider,
+        quirks_mode,
+        rule_cache_conditions: RefCell::new(rule_cache_conditions),
     };
 
     let ignore_colors = !device.use_document_colors();
     let default_background_color_decl = if ignore_colors {
         let color = device.default_background_color();
         Some(PropertyDeclaration::BackgroundColor(color.into()))
     } else {
         None
@@ -3178,16 +3207,17 @@ where
     // Declaration blocks are stored in increasing precedence order, we want
     // them in decreasing order here.
     //
     // We could (and used to) use a pattern match here, but that bloats this
     // function to over 100K of compiled code!
     //
     // To improve i-cache behavior, we outline the individual functions and use
     // virtual dispatch instead.
+    let mut apply_reset = true;
     % for category_to_cascade_now in ["early", "other"]:
         % if category_to_cascade_now == "early":
             // Pull these out so that we can compute them in a specific order
             // without introducing more iterations.
             let mut font_size = None;
             let mut font_family = None;
         % endif
         for (declaration, cascade_level) in iter_declarations() {
@@ -3210,16 +3240,20 @@ where
             // Only a few properties are allowed to depend on the visited state
             // of links.  When cascading visited styles, we can save time by
             // only processing these properties.
             if flags.contains(VISITED_DEPENDENT_ONLY) &&
                !longhand_id.is_visited_dependent() {
                 continue
             }
 
+            if !apply_reset && !longhand_id.inherited() {
+                continue;
+            }
+
             // When document colors are disabled, skip properties that are
             // marked as ignored in that mode, if they come from a UA or
             // user style sheet.
             if ignore_colors &&
                longhand_id.is_ignored_when_document_colors_disabled() &&
                !matches!(cascade_level,
                          CascadeLevel::UANormal |
                          CascadeLevel::UserNormal |
@@ -3377,17 +3411,22 @@ where
                       font_family.is_some() {
                 let discriminant = LonghandId::FontSize as usize;
                 let size = PropertyDeclaration::CSSWideKeyword(
                     LonghandId::FontSize, CSSWideKeyword::Inherit);
 
                 (CASCADE_PROPERTY[discriminant])(&size, &mut context);
             % endif
             }
-        % endif
+
+            if let Some(style) = rule_cache.and_then(|c| c.find(&context.builder)) {
+                context.builder.copy_reset_from(style);
+                apply_reset = false;
+            }
+        % endif // category == "early"
     % endfor
 
     let mut builder = context.builder;
 
     {
         StyleAdjuster::new(&mut builder)
             .adjust(layout_parent_style, flags);
     }

new file mode 100644
--- /dev/null
+++ b/servo/components/style/rule_cache.rs
@@ -0,0 +1,143 @@
+/* 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 cache from rule node to computed values, in order to cache reset
+//! properties.
+
+use values::computed::NonNegativeLength;
+use fnv::FnvHashMap;
+use logical_geometry::WritingMode;
+use properties::{ComputedValues, StyleBuilder};
+use rule_tree::StrongRuleNode;
+use servo_arc::Arc;
+use smallvec::SmallVec;
+
+/// The conditions for caching and matching a style in the rule cache.
+#[derive(Debug, Default, Clone)]
+pub struct RuleCacheConditions {
+    uncacheable: bool,
+    font_size: Option<NonNegativeLength>,
+    writing_mode: Option<WritingMode>,
+}
+
+impl RuleCacheConditions {
+    /// Sets the style as depending in the font-size value.
+    pub fn set_font_size_dependency(&mut self, font_size: NonNegativeLength) {
+        debug_assert!(self.font_size.map_or(true, |f| f == font_size));
+        self.font_size = Some(font_size);
+    }
+
+    /// Sets the style as uncacheable.
+    pub fn set_uncacheable(&mut self) {
+        self.uncacheable = true;
+    }
+
+    /// Sets the style as depending in the writing-mode value `writing_mode`.
+    pub fn set_writing_mode_dependency(&mut self, writing_mode: WritingMode) {
+        debug_assert!(self.writing_mode.map_or(true, |wm| wm == writing_mode));
+        self.writing_mode = Some(writing_mode);
+    }
+
+    /// Returns whether the current style's reset properties are cacheable.
+    fn cacheable(&self) -> bool {
+        !self.uncacheable
+    }
+
+    /// Returns whether `style` matches the conditions.
+    fn matches(&self, style: &StyleBuilder) -> bool {
+        if self.uncacheable {
+            return false;
+        }
+
+        if let Some(fs) = self.font_size {
+            if style.get_font().clone_font_size() != fs {
+                return false;
+            }
+        }
+
+        if let Some(wm) = self.writing_mode {
+            if style.writing_mode != wm {
+                return false;
+            }
+        }
+
+        true
+    }
+}
+
+/// A TLS cache from rules matched to computed values.
+pub struct RuleCache {
+    // FIXME(emilio): Consider using LRUCache or something like that?
+    map: FnvHashMap<StrongRuleNode, SmallVec<[(RuleCacheConditions, Arc<ComputedValues>); 1]>>,
+}
+
+impl RuleCache {
+    /// Creates an empty `RuleCache`.
+    pub fn new() -> Self {
+        Self {
+            map: FnvHashMap::default(),
+        }
+    }
+
+    /// Finds a node in the properties matched cache.
+    ///
+    /// This needs to receive a `StyleBuilder` with the `early` properties
+    /// already applied.
+    pub fn find(
+        &self,
+        builder_with_early_props: &StyleBuilder,
+    ) -> Option<&ComputedValues> {
+        if builder_with_early_props.is_style_if_visited() {
+            // FIXME(emilio): We can probably do better, does it matter much?
+            return None;
+        }
+
+        let rules = match builder_with_early_props.rules {
+            Some(ref rules) => rules,
+            None => return None,
+        };
+
+        self.map.get(rules).and_then(|cached_values| {
+            for &(ref conditions, ref values) in cached_values.iter() {
+                if conditions.matches(builder_with_early_props) {
+                    debug!("Using cached reset style with conditions {:?}", conditions);
+                    return Some(&**values)
+                }
+            }
+            None
+        })
+    }
+
+    /// Inserts a node into the rules cache if possible.
+    ///
+    /// Returns whether the style was inserted into the cache.
+    pub fn insert_if_possible(
+        &mut self,
+        style: &Arc<ComputedValues>,
+        conditions: &RuleCacheConditions,
+    ) -> bool {
+        if !conditions.cacheable() {
+            return false;
+        }
+
+        if style.is_style_if_visited() {
+            // FIXME(emilio): We can probably do better, does it matter much?
+            return false;
+        }
+
+        let rules = match style.rules {
+            Some(ref r) => r.clone(),
+            None => return false,
+        };
+
+        debug!("Inserting cached reset style with conditions {:?}", conditions);
+        self.map
+            .entry(rules)
+            .or_insert_with(SmallVec::new)
+            .push((conditions.clone(), style.clone()));
+
+        true
+    }
+
+}

--- a/servo/components/style/rule_tree/mod.rs
+++ b/servo/components/style/rule_tree/mod.rs
@@ -814,17 +814,17 @@ impl MallocSizeOf for RuleNode {
 }
 
 #[derive(Clone)]
 struct WeakRuleNode {
     p: NonZeroPtrMut<RuleNode>,
 }
 
 /// A strong reference to a rule node.
-#[derive(Debug, PartialEq)]
+#[derive(Debug, PartialEq, Eq, Hash)]
 pub struct StrongRuleNode {
     p: NonZeroPtrMut<RuleNode>,
 }
 
 #[cfg(feature = "servo")]
 impl HeapSizeOf for StrongRuleNode {
     fn heap_size_of_children(&self) -> usize { 0 }
 }

--- a/servo/components/style/style_resolver.rs
+++ b/servo/components/style/style_resolver.rs
@@ -513,26 +513,34 @@ where
         }
         if self.element.is_native_anonymous() || pseudo.is_some() {
             cascade_flags.insert(PROHIBIT_DISPLAY_CONTENTS);
         } else if self.element.is_root() {
             cascade_flags.insert(IS_ROOT_ELEMENT);
         }
 
         let implemented_pseudo = self.element.implemented_pseudo_element();
+        let mut conditions = Default::default();
         let values =
             cascade(
                 self.context.shared.stylist.device(),
                 pseudo.or(implemented_pseudo.as_ref()),
                 rules.unwrap_or(self.context.shared.stylist.rule_tree().root()),
                 &self.context.shared.guards,
                 parent_style,
                 parent_style,
                 layout_parent_style,
                 style_if_visited,
                 &self.context.thread_local.font_metrics_provider,
                 cascade_flags,
                 self.context.shared.quirks_mode(),
+                Some(&self.context.thread_local.rule_cache),
+                &mut conditions,
             );
 
+        self.context
+            .thread_local
+            .rule_cache
+            .insert_if_possible(&values, &conditions);
+
         values
     }
 }

--- a/servo/components/style/stylesheets/viewport_rule.rs
+++ b/servo/components/style/stylesheets/viewport_rule.rs
@@ -12,20 +12,22 @@ use context::QuirksMode;
 use cssparser::{AtRuleParser, DeclarationListParser, DeclarationParser, Parser, parse_important};
 use cssparser::{CowRcStr, ToCss as ParserToCss};
 use error_reporting::{ContextualParseError, ParseErrorReporter};
 use euclid::TypedSize2D;
 use font_metrics::get_metrics_provider_for_product;
 use media_queries::Device;
 use parser::{ParserContext, ParserErrorContext};
 use properties::StyleBuilder;
+use rule_cache::RuleCacheConditions;
 use selectors::parser::SelectorParseError;
 use shared_lock::{SharedRwLockReadGuard, ToCssWithGuard};
 use std::ascii::AsciiExt;
 use std::borrow::Cow;
+use std::cell::RefCell;
 use std::fmt;
 use std::iter::Enumerate;
 use std::str::Chars;
 use style_traits::{PinchZoomFactor, ToCss, ParseError, StyleParseError};
 use style_traits::viewport::{Orientation, UserZoom, ViewportConstraints, Zoom};
 use stylesheets::{StylesheetInDocument, Origin};
 use values::computed::{Context, ToComputedValue};
 use values::specified::{NoCalcLength, LengthOrPercentageOrAuto, ViewportPercentageLength};
@@ -702,24 +704,26 @@ impl MaybeNew for ViewportConstraints {
         // Note: DEVICE-ADAPT § 5. states that relative length values are
         // resolved against initial values
         let initial_viewport = device.au_viewport_size();
 
         let provider = get_metrics_provider_for_product();
 
         let default_values = device.default_computed_values();
 
+        let mut conditions = RuleCacheConditions::default();
         let context = Context {
             is_root_element: false,
             builder: StyleBuilder::for_derived_style(device, default_values, None, None),
             font_metrics_provider: &provider,
             cached_system_font: None,
             in_media_query: false,
             quirks_mode: quirks_mode,
             for_smil_animation: false,
+            rule_cache_conditions: RefCell::new(&mut conditions),
         };
 
         // DEVICE-ADAPT § 9.3 Resolving 'extend-to-zoom'
         let extend_width;
         let extend_height;
         if let Some(extend_zoom) = max!(initial_zoom, max_zoom) {
             let scale_factor = 1. / extend_zoom;
             extend_width = Some(initial_viewport.width.scale_by(scale_factor));

--- a/servo/components/style/stylist.rs
+++ b/servo/components/style/stylist.rs
@@ -766,16 +766,18 @@ impl Stylist {
             guards,
             parent,
             parent,
             parent,
             None,
             font_metrics,
             cascade_flags,
             self.quirks_mode,
+            /* rule_cache = */ None,
+            &mut Default::default(),
         )
     }
 
     /// Returns the rule node for given precomputed pseudo-element.
     ///
     /// If we want to include extra declarations to this precomputed pseudo-element,
     /// we can provide a vector of ApplicableDeclarationBlock to extra_declarations
     /// argument. This is useful for providing extra @page rules.
@@ -982,16 +984,18 @@ impl Stylist {
                 guards,
                 Some(inherited_style),
                 Some(inherited_style_ignoring_first_line),
                 Some(layout_parent_style_for_visited),
                 None,
                 font_metrics,
                 cascade_flags,
                 self.quirks_mode,
+                /* rule_cache = */ None,
+                &mut Default::default(),
             ))
         } else {
             None
         };
 
         // We may not have non-visited rules, if we only had visited ones.  In
         // that case we want to use the root rulenode for our non-visited rules.
         let rules = inputs.rules.as_ref().unwrap_or(self.rule_tree.root());
@@ -1007,16 +1011,18 @@ impl Stylist {
             guards,
             Some(parent_style),
             Some(parent_style_ignoring_first_line),
             Some(layout_parent_style),
             visited_values,
             font_metrics,
             cascade_flags,
             self.quirks_mode,
+            /* rule_cache = */ None,
+            &mut Default::default(),
         )
     }
 
     fn has_rules_for_pseudo(&self, pseudo: &PseudoElement) -> bool {
         self.cascade_data
             .iter_origins()
             .any(|(d, _)| d.has_rules_for_pseudo(pseudo))
     }
@@ -1620,16 +1626,18 @@ impl Stylist {
             guards,
             Some(parent_style),
             Some(parent_style),
             Some(parent_style),
             None,
             &metrics,
             CascadeFlags::empty(),
             self.quirks_mode,
+            /* rule_cache = */ None,
+            &mut Default::default(),
         )
     }
 
     /// Accessor for a shared reference to the device.
     pub fn device(&self) -> &Device {
         &self.device
     }
 

--- a/servo/components/style/values/computed/mod.rs
+++ b/servo/components/style/values/computed/mod.rs
@@ -7,19 +7,21 @@
 use {Atom, Namespace};
 use context::QuirksMode;
 use euclid::Size2D;
 use font_metrics::FontMetricsProvider;
 use media_queries::Device;
 #[cfg(feature = "gecko")]
 use properties;
 use properties::{ComputedValues, StyleBuilder};
+use rule_cache::RuleCacheConditions;
 #[cfg(feature = "servo")]
 use servo_url::ServoUrl;
 use std::{f32, fmt};
+use std::cell::RefCell;
 #[cfg(feature = "servo")]
 use std::sync::Arc;
 use style_traits::ToCss;
 use style_traits::cursor::Cursor;
 use super::{CSSFloat, CSSInteger};
 use super::generics::{GreaterThanOrEqualToOne, NonNegative};
 use super::generics::grid::{GridLine as GenericGridLine, TrackBreadth as GenericTrackBreadth};
 use super::generics::grid::{TrackSize as GenericTrackSize, TrackList as GenericTrackList};
@@ -111,16 +113,21 @@ pub struct Context<'a> {
     /// The quirks mode of this context.
     pub quirks_mode: QuirksMode,
 
     /// Whether this computation is being done for a SMIL animation.
     ///
     /// This is used to allow certain properties to generate out-of-range
     /// values, which SMIL allows.
     pub for_smil_animation: bool,
+
+    /// The conditions to cache a rule node on the rule cache.
+    ///
+    /// FIXME(emilio): Drop the refcell.
+    pub rule_cache_conditions: RefCell<&'a mut RuleCacheConditions>,
 }
 
 impl<'a> Context<'a> {
     /// Whether the current element is the root element.
     pub fn is_root_element(&self) -> bool {
         self.is_root_element
     }
 

--- a/servo/components/style/values/specified/length.rs
+++ b/servo/components/style/values/specified/length.rs
@@ -126,16 +126,22 @@ impl FontRelativeLength {
                                                 context.in_media_query,
                                                 context.device())
         }
 
         let reference_font_size = base_size.resolve(context);
 
         match *self {
             FontRelativeLength::Em(length) => {
+                if !matches!(base_size, FontBaseSize::InheritedStyle) {
+                    context.rule_cache_conditions.borrow_mut()
+                        .set_font_size_dependency(
+                            reference_font_size.into()
+                        );
+                }
                 (reference_font_size, length)
             },
             FontRelativeLength::Ex(length) => {
                 let reference_size = match query_font_metrics(context, reference_font_size) {
                     FontMetricsQueryResult::Available(metrics) => {
                         metrics.x_height
                     },
                     // https://drafts.csswg.org/css-values/#ex

--- a/servo/ports/geckolib/glue.rs
+++ b/servo/ports/geckolib/glue.rs
@@ -4,16 +4,17 @@
 
 use cssparser::{Parser, ParserInput};
 use cssparser::ToCss as ParserToCss;
 use env_logger::LogBuilder;
 use malloc_size_of::MallocSizeOfOps;
 use selectors::Element;
 use selectors::matching::{MatchingContext, MatchingMode, matches_selector};
 use servo_arc::{Arc, ArcBorrow, RawOffsetArc};
+use std::cell::RefCell;
 use std::env;
 use std::fmt::Write;
 use std::iter;
 use std::ptr;
 use style::applicable_declarations::ApplicableDeclarationBlock;
 use style::context::{CascadeInputs, QuirksMode, SharedStyleContext, StyleContext};
 use style::context::ThreadLocalStyleContext;
 use style::data::ElementStyles;
@@ -112,16 +113,17 @@ use style::properties::{CascadeFlags, Co
 use style::properties::{IS_FIELDSET_CONTENT, IS_LINK, IS_VISITED_LINK, LonghandIdSet};
 use style::properties::{PropertyDeclaration, PropertyDeclarationBlock, PropertyId, ShorthandId};
 use style::properties::{SKIP_ROOT_AND_ITEM_BASED_DISPLAY_FIXUP, SourcePropertyDeclaration, StyleBuilder};
 use style::properties::PROHIBIT_DISPLAY_CONTENTS;
 use style::properties::animated_properties::{AnimatableLonghand, AnimationValue};
 use style::properties::animated_properties::compare_property_priority;
 use style::properties::parse_one_declaration_into;
 use style::rule_tree::{CascadeLevel, StyleSource};
+use style::rule_cache::RuleCacheConditions;
 use style::selector_parser::PseudoElementCascadeType;
 use style::shared_lock::{SharedRwLockReadGuard, StylesheetGuards, ToCssWithGuard, Locked};
 use style::string_cache::Atom;
 use style::style_adjuster::StyleAdjuster;
 use style::stylesheets::{CssRule, CssRules, CssRuleType, CssRulesHelpers, DocumentRule};
 use style::stylesheets::{FontFeatureValuesRule, ImportRule, KeyframesRule, MediaRule};
 use style::stylesheets::{NamespaceRule, Origin, OriginSet, PageRule, StyleRule};
 use style::stylesheets::{StylesheetContents, SupportsRule};
@@ -3179,30 +3181,32 @@ fn simulate_compute_values_failure(_: &P
 
 fn create_context<'a>(
     per_doc_data: &'a PerDocumentStyleDataImpl,
     font_metrics_provider: &'a FontMetricsProvider,
     style: &'a ComputedValues,
     parent_style: Option<&'a ComputedValues>,
     pseudo: Option<&'a PseudoElement>,
     for_smil_animation: bool,
+    rule_cache_conditions: &'a mut RuleCacheConditions,
 ) -> Context<'a> {
     Context {
         is_root_element: false,
         builder: StyleBuilder::for_derived_style(
             per_doc_data.stylist.device(),
             style,
             parent_style,
             pseudo,
         ),
         font_metrics_provider: font_metrics_provider,
         cached_system_font: None,
         in_media_query: false,
         quirks_mode: per_doc_data.stylist.quirks_mode(),
         for_smil_animation,
+        rule_cache_conditions: RefCell::new(rule_cache_conditions),
     }
 }
 
 struct PropertyAndIndex {
     property: PropertyId,
     index: usize,
 }
 
@@ -3262,23 +3266,25 @@ pub extern "C" fn Servo_GetComputedKeyfr
     let metrics = get_metrics_provider_for_product();
 
     let element = GeckoElement(element);
     let parent_element = element.inheritance_parent();
     let parent_data = parent_element.as_ref().and_then(|e| e.borrow_data());
     let parent_style = parent_data.as_ref().map(|d| d.styles.primary()).map(|x| &**x);
 
     let pseudo = style.pseudo();
+    let mut conditions = Default::default();
     let mut context = create_context(
         &data,
         &metrics,
         &style,
         parent_style,
         pseudo.as_ref(),
         /* for_smil_animation = */ false,
+        &mut conditions,
     );
 
     let global_style_data = &*GLOBAL_STYLE_DATA;
     let guard = global_style_data.shared_lock.read();
     let default_values = data.default_computed_values();
 
     for (index, keyframe) in keyframes.iter().enumerate() {
         let ref mut animation_values = computed_keyframes[index];
@@ -3349,23 +3355,25 @@ pub extern "C" fn Servo_GetAnimationValu
     let metrics = get_metrics_provider_for_product();
 
     let element = GeckoElement(element);
     let parent_element = element.inheritance_parent();
     let parent_data = parent_element.as_ref().and_then(|e| e.borrow_data());
     let parent_style = parent_data.as_ref().map(|d| d.styles.primary()).map(|x| &**x);
 
     let pseudo = style.pseudo();
+    let mut conditions = Default::default();
     let mut context = create_context(
         &data,
         &metrics,
         &style,
         parent_style,
         pseudo.as_ref(),
-        /* for_smil_animation = */ true
+        /* for_smil_animation = */ true,
+        &mut conditions,
     );
 
     let default_values = data.default_computed_values();
     let global_style_data = &*GLOBAL_STYLE_DATA;
     let guard = global_style_data.shared_lock.read();
 
     let declarations = Locked::<PropertyDeclarationBlock>::as_arc(&declarations);
     let guard = declarations.read_with(&guard);
@@ -3385,23 +3393,25 @@ pub extern "C" fn Servo_AnimationValue_C
     let metrics = get_metrics_provider_for_product();
 
     let element = GeckoElement(element);
     let parent_element = element.inheritance_parent();
     let parent_data = parent_element.as_ref().and_then(|e| e.borrow_data());
     let parent_style = parent_data.as_ref().map(|d| d.styles.primary()).map(|x| &**x);
 
     let pseudo = style.pseudo();
+    let mut conditions = Default::default();
     let mut context = create_context(
         &data,
         &metrics,
         style,
         parent_style,
         pseudo.as_ref(),
-        /* for_smil_animation = */ false
+        /* for_smil_animation = */ false,
+        &mut conditions,
     );
 
     let default_values = data.default_computed_values();
     let global_style_data = &*GLOBAL_STYLE_DATA;
     let guard = global_style_data.shared_lock.read();
     let declarations = Locked::<PropertyDeclarationBlock>::as_arc(&declarations);
     // We only compute the first element in declarations.
     match declarations.read_with(&guard).declaration_importance_iter().next() {