Bug 1328509 - Match and cascade visited styles. r=emilio draft
authorJ. Ryan Stinnett <jryans@gmail.com>
Thu, 04 May 2017 18:54:20 -0500
changeset 583433 49e51d406f1ce6a08231d71d2acd8dac277c4bce
parent 583432 bd5ef4eee3633c7b7ba67b16bcc5858c121b7356
child 583434 3c67f64d49183aabc3ca6be7ede596c1de4cd313
push id60394
push userbmo:jryans@gmail.com
push dateWed, 24 May 2017 02:27:21 +0000
reviewersemilio
bugs1328509
milestone55.0a1
Bug 1328509 - Match and cascade visited styles. r=emilio To support visited styles, we match and cascade a separate set of styles any time we notice that an element has a relevant link. The visited rules and values are held in `ComputedStyle` alongside the regular rules and values, which simplifies supporting various APIs like `cascade_primary_and_pseudos` which expect easy access to previously matched rules. To simplify passing the additional values around, an additional reference to the visited `ComputedValues` is placed inside the regular `ComputedValues`. MozReview-Commit-ID: 2ebbjcfkfWf
servo/components/selectors/matching.rs
servo/components/style/animation.rs
servo/components/style/data.rs
servo/components/style/matching.rs
servo/components/style/properties/gecko.mako.rs
servo/components/style/properties/properties.mako.rs
servo/components/style/rule_tree/mod.rs
servo/components/style/stylist.rs
servo/ports/geckolib/glue.rs
--- a/servo/components/selectors/matching.rs
+++ b/servo/components/selectors/matching.rs
@@ -70,17 +70,17 @@ impl ElementSelectorFlags {
         self & (HAS_SLOW_SELECTOR | HAS_SLOW_SELECTOR_LATER_SIBLINGS | HAS_EDGE_CHILD_SELECTOR)
     }
 }
 
 /// What kind of selector matching mode we should use.
 ///
 /// There are two modes of selector matching. The difference is only noticeable
 /// in presence of pseudo-elements.
-#[derive(Debug, PartialEq)]
+#[derive(Debug, PartialEq, Copy, Clone)]
 pub enum MatchingMode {
     /// Don't ignore any pseudo-element selectors.
     Normal,
 
     /// Ignores any stateless pseudo-element selectors in the rightmost sequence
     /// of simple selectors.
     ///
     /// This is useful, for example, to match against ::before when you aren't a
@@ -103,47 +103,63 @@ pub enum VisitedHandlingMode {
     /// or the nearest ancestor link. The relevant link is matched as though it
     /// is visited, and all other links are matched as if they are unvisited.
     RelevantLinkVisited,
 }
 
 /// Data associated with the matching process for a element.  This context is
 /// used across many selectors for an element, so it's not appropriate for
 /// transient data that applies to only a single selector.
+#[derive(Clone)]
 pub struct MatchingContext<'a> {
     /// Output that records certains relations between elements noticed during
     /// matching (and also extended after matching).
     pub relations: StyleRelations,
-    /// The matching mode we should use when matching selectors.
+    /// Input with the matching mode we should use when matching selectors.
     pub matching_mode: MatchingMode,
-    /// The bloom filter used to fast-reject selectors.
+    /// Input with the bloom filter used to fast-reject selectors.
     pub bloom_filter: Option<&'a BloomFilter>,
     /// Input that controls how matching for links is handled.
     pub visited_handling: VisitedHandlingMode,
     /// Output that records whether we encountered a "relevant link" while
     /// matching _any_ selector for this element. (This differs from
     /// `RelevantLinkStatus` which tracks the status for the _current_ selector
     /// only.)
-    relevant_link_found: bool,
+    pub relevant_link_found: bool,
 }
 
 impl<'a> MatchingContext<'a> {
     /// Constructs a new `MatchingContext`.
     pub fn new(matching_mode: MatchingMode,
                bloom_filter: Option<&'a BloomFilter>)
                -> Self
     {
         Self {
             relations: StyleRelations::empty(),
             matching_mode: matching_mode,
             bloom_filter: bloom_filter,
             visited_handling: VisitedHandlingMode::AllLinksUnvisited,
             relevant_link_found: false,
         }
     }
+
+    /// Constructs a new `MatchingContext` for use in visited matching.
+    pub fn new_for_visited(matching_mode: MatchingMode,
+                           bloom_filter: Option<&'a BloomFilter>,
+                           visited_handling: VisitedHandlingMode)
+                           -> Self
+    {
+        Self {
+            relations: StyleRelations::empty(),
+            matching_mode: matching_mode,
+            bloom_filter: bloom_filter,
+            visited_handling: visited_handling,
+            relevant_link_found: false,
+        }
+    }
 }
 
 pub fn matches_selector_list<E>(selector_list: &[Selector<E::Impl>],
                                 element: &E,
                                 context: &mut MatchingContext)
                                 -> bool
     where E: Element
 {
--- a/servo/components/style/animation.rs
+++ b/servo/components/style/animation.rs
@@ -470,23 +470,26 @@ fn compute_style_for_animation_step(cont
             // No !important in keyframes.
             debug_assert!(guard.declarations().iter()
                             .all(|&(_, importance)| importance == Importance::Normal));
 
             let iter = || {
                 guard.declarations().iter().rev().map(|&(ref decl, _importance)| decl)
             };
 
+            // This currently ignores visited styles, which seems acceptable,
+            // as existing browsers don't appear to animate visited styles.
             let computed =
                 properties::apply_declarations(context.stylist.device(),
                                                /* is_root = */ false,
                                                iter,
                                                previous_style,
                                                previous_style,
                                                /* cascade_info = */ None,
+                                               /* visited_style = */ None,
                                                &*context.error_reporter,
                                                font_metrics_provider,
                                                CascadeFlags::empty(),
                                                context.quirks_mode);
             computed
         }
     }
 }
--- a/servo/components/style/data.rs
+++ b/servo/components/style/data.rs
@@ -4,18 +4,19 @@
 
 //! Per-node data used in style calculation.
 
 use context::SharedStyleContext;
 use dom::TElement;
 use properties::ComputedValues;
 use properties::longhands::display::computed_value as display;
 use restyle_hints::{HintComputationContext, RestyleReplacements, RestyleHint};
-use rule_tree::StrongRuleNode;
+use rule_tree::StrongRuleNode   ;
 use selector_parser::{EAGER_PSEUDO_COUNT, PseudoElement, RestyleDamage};
+use selectors::matching::VisitedHandlingMode;
 use shared_lock::StylesheetGuards;
 #[cfg(feature = "servo")] use std::collections::HashMap;
 use std::fmt;
 #[cfg(feature = "servo")] use std::hash::BuildHasherDefault;
 use stylearc::Arc;
 use traversal::TraversalFlags;
 
 /// The structure that represents the result of style computation. This is
@@ -26,45 +27,113 @@ pub struct ComputedStyle {
     /// The rule node representing the ordered list of rules matched for this
     /// node.
     pub rules: StrongRuleNode,
 
     /// The computed values for each property obtained by cascading the
     /// matched rules. This can only be none during a transient interval of
     /// the styling algorithm, and callers can safely unwrap it.
     pub values: Option<Arc<ComputedValues>>,
+
+    /// The rule node representing the ordered list of rules matched for this
+    /// node if visited, only computed if there's a relevant link for this
+    /// element. A element's "relevant link" is the element being matched if it
+    /// is a link or the nearest ancestor link.
+    visited_rules: Option<StrongRuleNode>,
+
+    /// The element's computed values if visited, only computed if there's a
+    /// relevant link for this element. A element's "relevant link" is the
+    /// element being matched if it is a link or the nearest ancestor link.
+    ///
+    /// We also store a reference to this inside the regular ComputedValues to
+    /// avoid refactoring all APIs to become aware of multiple ComputedValues
+    /// objects.
+    visited_values: Option<Arc<ComputedValues>>,
 }
 
 impl ComputedStyle {
     /// Trivially construct a new `ComputedStyle`.
     pub fn new(rules: StrongRuleNode, values: Arc<ComputedValues>) -> Self {
         ComputedStyle {
             rules: rules,
             values: Some(values),
+            visited_rules: None,
+            visited_values: None,
         }
     }
 
     /// Constructs a partial ComputedStyle, whose ComputedVaues will be filled
     /// in later.
     pub fn new_partial(rules: StrongRuleNode) -> Self {
         ComputedStyle {
             rules: rules,
             values: None,
+            visited_rules: None,
+            visited_values: None,
         }
     }
 
     /// Returns a reference to the ComputedValues. The values can only be null during
     /// the styling algorithm, so this is safe to call elsewhere.
     pub fn values(&self) -> &Arc<ComputedValues> {
         self.values.as_ref().unwrap()
     }
 
-    /// Mutable version of the above.
-    pub fn values_mut(&mut self) -> &mut Arc<ComputedValues> {
-        self.values.as_mut().unwrap()
+    /// Whether there are any visited rules.
+    pub fn has_visited_rules(&self) -> bool {
+        self.visited_rules.is_some()
+    }
+
+    /// Gets a reference to the visited rule node, if any.
+    pub fn get_visited_rules(&self) -> Option<&StrongRuleNode> {
+        self.visited_rules.as_ref()
+    }
+
+    /// Gets a reference to the visited rule node. Panic if the element does not
+    /// have visited rule node.
+    pub fn visited_rules(&self) -> &StrongRuleNode {
+        self.get_visited_rules().unwrap()
+    }
+
+    /// Sets the visited rule node, and returns whether it changed.
+    pub fn set_visited_rules(&mut self, rules: StrongRuleNode) -> bool {
+        if let Some(ref old_rules) = self.visited_rules {
+            if *old_rules == rules {
+                return false
+            }
+        }
+        self.visited_rules = Some(rules);
+        true
+    }
+
+    /// Takes the visited rule node.
+    pub fn take_visited_rules(&mut self) -> Option<StrongRuleNode> {
+        self.visited_rules.take()
+    }
+
+    /// Gets a reference to the visited computed values. Panic if the element
+    /// does not have visited computed values.
+    pub fn visited_values(&self) -> &Arc<ComputedValues> {
+        self.visited_values.as_ref().unwrap()
+    }
+
+    /// Sets the visited computed values.
+    pub fn set_visited_values(&mut self, values: Arc<ComputedValues>) {
+        self.visited_values = Some(values);
+    }
+
+    /// Take the visited computed values.
+    pub fn take_visited_values(&mut self) -> Option<Arc<ComputedValues>> {
+        self.visited_values.take()
+    }
+
+    /// Clone the visited computed values Arc.  Used to store a reference to the
+    /// visited values inside the regular values.
+    pub fn clone_visited_values(&self) -> Option<Arc<ComputedValues>> {
+        self.visited_values.clone()
     }
 }
 
 // We manually implement Debug for ComputedStyle so that we can avoid the
 // verbose stringification of ComputedValues for normal logging.
 impl fmt::Debug for ComputedStyle {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
         write!(f, "ComputedStyle {{ rules: {:?}, values: {{..}} }}", self.rules)
@@ -103,17 +172,17 @@ impl EagerPseudoStyles {
         debug_assert!(!self.has(pseudo));
         if self.0.is_none() {
             self.0 = Some(vec![None; EAGER_PSEUDO_COUNT].into_boxed_slice());
         }
         self.0.as_mut().unwrap()[pseudo.eager_index()] = Some(style);
     }
 
     /// Removes a pseudo-element style if it exists, and returns it.
-    pub fn take(&mut self, pseudo: &PseudoElement) -> Option<ComputedStyle> {
+    fn take(&mut self, pseudo: &PseudoElement) -> Option<ComputedStyle> {
         let result = match self.0.as_mut() {
             None => return None,
             Some(arr) => arr[pseudo.eager_index()].take(),
         };
         let empty = self.0.as_ref().unwrap().iter().all(|x| x.is_none());
         if empty {
             self.0 = None;
         }
@@ -128,25 +197,105 @@ impl EagerPseudoStyles {
                 if arr[i].is_some() {
                     v.push(PseudoElement::from_eager_index(i));
                 }
             }
         }
         v
     }
 
-    /// Sets the rule node for a given pseudo-element, which must already have an entry.
+    /// Adds the unvisited rule node for a given pseudo-element, which may or
+    /// may not exist.
     ///
-    /// Returns true if the rule node changed.
-    pub fn set_rules(&mut self, pseudo: &PseudoElement, rules: StrongRuleNode) -> bool {
+    /// Returns true if the pseudo-element is new.
+    fn add_unvisited_rules(&mut self,
+                           pseudo: &PseudoElement,
+                           rules: StrongRuleNode)
+                           -> bool {
+        if let Some(mut style) = self.get_mut(pseudo) {
+            style.rules = rules;
+            return false
+        }
+        self.insert(pseudo, ComputedStyle::new_partial(rules));
+        true
+    }
+
+    /// Remove the unvisited rule node for a given pseudo-element, which may or
+    /// may not exist. Since removing the rule node implies we don't need any
+    /// other data for the pseudo, take the entire pseudo if found.
+    ///
+    /// Returns true if the psuedo-element was removed.
+    fn remove_unvisited_rules(&mut self, pseudo: &PseudoElement) -> bool {
+        if !self.has(pseudo) {
+            return false
+        }
+        self.take(pseudo);
+        true
+    }
+
+    /// Adds the visited rule node for a given pseudo-element.  It is assumed to
+    /// already exist because unvisited styles should have been added first.
+    ///
+    /// Returns true if the pseudo-element is new.
+    fn add_visited_rules(&mut self,
+                         pseudo: &PseudoElement,
+                         rules: StrongRuleNode)
+                         -> bool {
         debug_assert!(self.has(pseudo));
         let mut style = self.get_mut(pseudo).unwrap();
-        let changed = style.rules != rules;
-        style.rules = rules;
-        changed
+        style.set_visited_rules(rules);
+        false
+    }
+
+    /// Remove the visited rule node for a given pseudo-element, which may or
+    /// may not exist.
+    ///
+    /// Returns true if the psuedo-element was removed.
+    fn remove_visited_rules(&mut self, pseudo: &PseudoElement) -> bool {
+        if let Some(mut style) = self.get_mut(pseudo) {
+            style.take_visited_rules();
+        }
+        false
+    }
+
+    /// Adds a rule node for a given pseudo-element, which may or may not exist.
+    /// The type of rule node depends on the visited mode.
+    ///
+    /// Returns true if the pseudo-element is new.
+    pub fn add_rules(&mut self,
+                     pseudo: &PseudoElement,
+                     visited_handling: VisitedHandlingMode,
+                     rules: StrongRuleNode)
+                     -> bool {
+        match visited_handling {
+            VisitedHandlingMode::AllLinksUnvisited => {
+                self.add_unvisited_rules(&pseudo, rules)
+            },
+            VisitedHandlingMode::RelevantLinkVisited => {
+                self.add_visited_rules(&pseudo, rules)
+            },
+        }
+    }
+
+    /// Removes a rule node for a given pseudo-element, which may or may not
+    /// exist. The type of rule node depends on the visited mode.
+    ///
+    /// Returns true if the psuedo-element was removed.
+    pub fn remove_rules(&mut self,
+                        pseudo: &PseudoElement,
+                        visited_handling: VisitedHandlingMode)
+                        -> bool {
+        match visited_handling {
+            VisitedHandlingMode::AllLinksUnvisited => {
+                self.remove_unvisited_rules(&pseudo)
+            },
+            VisitedHandlingMode::RelevantLinkVisited => {
+                self.remove_visited_rules(&pseudo)
+            },
+        }
     }
 }
 
 /// A cache of precomputed and lazy pseudo-elements, used by servo. This isn't
 /// a very efficient design, but is the result of servo having previously used
 /// the eager pseudo map (when it was a map) for this cache.
 #[cfg(feature = "servo")]
 type PseudoElementCache = HashMap<PseudoElement, ComputedStyle, BuildHasherDefault<::fnv::FnvHasher>>;
--- a/servo/components/style/matching.rs
+++ b/servo/components/style/matching.rs
@@ -13,21 +13,20 @@ use context::{SelectorFlagsMap, SharedSt
 use data::{ComputedStyle, ElementData, RestyleData};
 use dom::{AnimationRules, TElement, TNode};
 use font_metrics::FontMetricsProvider;
 use log::LogLevel::Trace;
 use properties::{CascadeFlags, ComputedValues, SKIP_ROOT_AND_ITEM_BASED_DISPLAY_FIXUP, cascade};
 use properties::longhands::display::computed_value as display;
 use restyle_hints::{RESTYLE_CSS_ANIMATIONS, RESTYLE_CSS_TRANSITIONS, RestyleReplacements};
 use restyle_hints::{RESTYLE_STYLE_ATTRIBUTE, RESTYLE_SMIL};
-use rule_tree::{CascadeLevel, RuleTree, StrongRuleNode};
+use rule_tree::{CascadeLevel, StrongRuleNode};
 use selector_parser::{PseudoElement, RestyleDamage, SelectorImpl};
 use selectors::matching::{ElementSelectorFlags, MatchingContext, MatchingMode, StyleRelations};
-use selectors::matching::AFFECTED_BY_PSEUDO_ELEMENTS;
-use shared_lock::StylesheetGuards;
+use selectors::matching::{VisitedHandlingMode, AFFECTED_BY_PSEUDO_ELEMENTS};
 use sharing::{StyleSharingBehavior, StyleSharingResult};
 use stylearc::Arc;
 use stylist::ApplicableDeclarationList;
 
 /// The way a style should be inherited.
 enum InheritMode {
     /// Inherit from the parent element, as normal CSS dictates, _or_ from the
     /// closest non-Native Anonymous element in case this is Native Anonymous
@@ -88,25 +87,16 @@ impl From<StyleChange> for ChildCascadeR
     fn from(change: StyleChange) -> ChildCascadeRequirement {
         match change {
             StyleChange::Unchanged => ChildCascadeRequirement::CanSkipCascade,
             StyleChange::Changed => ChildCascadeRequirement::MustCascade,
         }
     }
 }
 
-/// The result status for match primary rules.
-#[derive(Debug)]
-pub struct RulesMatchedResult {
-    /// Indicate that the rule nodes are changed.
-    rule_nodes_changed: bool,
-    /// Indicate that there are any changes of important rules overriding animations.
-    important_rules_overriding_animation_changed: bool,
-}
-
 bitflags! {
     /// Flags that represent the result of replace_rules.
     pub flags RulesChanged: u8 {
         /// Normal rules are changed.
         const NORMAL_RULES_CHANGED = 0x01,
         /// Important rules are changed.
         const IMPORTANT_RULES_CHANGED = 0x02,
     }
@@ -121,16 +111,82 @@ impl RulesChanged {
 
     /// Return true if there are any important rules changed.
     #[inline]
     pub fn important_rules_changed(&self) -> bool {
         self.contains(IMPORTANT_RULES_CHANGED)
     }
 }
 
+/// Determines which styles are being cascaded currently.
+#[derive(PartialEq, Eq, Copy, Clone, Debug)]
+pub enum CascadeVisitedMode {
+    /// Cascade the regular, unvisited styles.
+    Unvisited,
+    /// Cascade the styles used when an element's relevant link is visited.  A
+    /// "relevant link" is the element being matched if it is a link or the
+    /// nearest ancestor link.
+    Visited,
+}
+
+/// Various helper methods to ease navigating the style storage locations
+/// depending on the current cascade mode.
+impl CascadeVisitedMode {
+    /// Returns whether there is a rule node based on the cascade mode.
+    fn has_rules(&self, style: &ComputedStyle) -> bool {
+        match *self {
+            CascadeVisitedMode::Unvisited => true,
+            CascadeVisitedMode::Visited => style.has_visited_rules(),
+        }
+    }
+
+    /// Returns the rule node based on the cascade mode.
+    fn rules<'a>(&self, style: &'a ComputedStyle) -> &'a StrongRuleNode {
+        match *self {
+            CascadeVisitedMode::Unvisited => &style.rules,
+            CascadeVisitedMode::Visited => style.visited_rules(),
+        }
+    }
+
+    /// Returns the computed values based on the cascade mode.  In visited mode,
+    /// visited values are only returned if they already exist.  If they don't,
+    /// we fallback to the regular, unvisited styles.
+    fn values<'a>(&self, style: &'a ComputedStyle) -> &'a Arc<ComputedValues> {
+        let mut values = style.values();
+
+        if *self == CascadeVisitedMode::Visited && values.get_visited_style().is_some() {
+            values = values.visited_style();
+        }
+
+        values
+    }
+
+    /// Set the computed values based on the cascade mode.
+    fn set_values(&self, style: &mut ComputedStyle, values: Arc<ComputedValues>) {
+        match *self {
+            CascadeVisitedMode::Unvisited => style.values = Some(values),
+            CascadeVisitedMode::Visited => style.set_visited_values(values),
+        }
+    }
+
+    /// Take the computed values based on the cascade mode.
+    fn take_values(&self, style: &mut ComputedStyle) -> Option<Arc<ComputedValues>> {
+        match *self {
+            CascadeVisitedMode::Unvisited => style.values.take(),
+            CascadeVisitedMode::Visited => style.take_visited_values(),
+        }
+    }
+
+    /// Returns whether there might be visited values that should be inserted
+    /// within the regular computed values based on the cascade mode.
+    fn visited_values_for_insertion(&self) -> bool {
+        *self == CascadeVisitedMode::Unvisited
+    }
+}
+
 trait PrivateMatchMethods: TElement {
     /// Returns the closest parent element that doesn't have a display: contents
     /// style (and thus generates a box).
     ///
     /// This is needed to correctly handle blockification of flex and grid
     /// items.
     ///
     /// Returns itself if the element has no parent. In practice this doesn't
@@ -154,58 +210,59 @@ trait PrivateMatchMethods: TElement {
         }
     }
 
     fn cascade_with_rules(&self,
                           shared_context: &SharedStyleContext,
                           font_metrics_provider: &FontMetricsProvider,
                           rule_node: &StrongRuleNode,
                           primary_style: &ComputedStyle,
-                          inherit_mode: InheritMode)
+                          inherit_mode: InheritMode,
+                          cascade_visited: CascadeVisitedMode,
+                          visited_values_to_insert: Option<Arc<ComputedValues>>)
                           -> Arc<ComputedValues> {
         let mut cascade_info = CascadeInfo::new();
         let mut cascade_flags = CascadeFlags::empty();
         if self.skip_root_and_item_based_display_fixup() {
             cascade_flags.insert(SKIP_ROOT_AND_ITEM_BASED_DISPLAY_FIXUP)
         }
 
         // Grab the inherited values.
         let parent_el;
         let parent_data;
         let style_to_inherit_from = match inherit_mode {
             InheritMode::Normal => {
                 parent_el = self.inheritance_parent();
                 parent_data = parent_el.as_ref().and_then(|e| e.borrow_data());
-                let parent_values = parent_data.as_ref().map(|d| {
+                let parent_style = parent_data.as_ref().map(|d| {
                     // Sometimes Gecko eagerly styles things without processing
                     // pending restyles first. In general we'd like to avoid this,
                     // but there can be good reasons (for example, needing to
                     // construct a frame for some small piece of newly-added
                     // content in order to do something specific with that frame,
                     // but not wanting to flush all of layout).
                     debug_assert!(cfg!(feature = "gecko") ||
                                   parent_el.unwrap().has_current_styles(d));
-                    d.styles().primary.values()
+                    &d.styles().primary
                 });
-
-                parent_values
+                parent_style.map(|s| cascade_visited.values(s))
             }
             InheritMode::FromPrimaryStyle => {
                 parent_el = Some(self.clone());
-                Some(primary_style.values())
+                Some(cascade_visited.values(primary_style))
             }
         };
 
         let mut layout_parent_el = parent_el.clone();
         let layout_parent_data;
         let mut layout_parent_style = style_to_inherit_from;
         if style_to_inherit_from.map_or(false, |s| s.is_display_contents()) {
             layout_parent_el = Some(layout_parent_el.unwrap().layout_parent());
             layout_parent_data = layout_parent_el.as_ref().unwrap().borrow_data().unwrap();
-            layout_parent_style = Some(layout_parent_data.styles().primary.values())
+            layout_parent_style = Some(cascade_visited.values(&layout_parent_data.styles().primary));
         }
 
         let style_to_inherit_from = style_to_inherit_from.map(|x| &**x);
         let layout_parent_style = layout_parent_style.map(|x| &**x);
 
         // Propagate the "can be fragmented" bit. It would be nice to
         // encapsulate this better.
         //
@@ -223,30 +280,32 @@ trait PrivateMatchMethods: TElement {
 
         // Invoke the cascade algorithm.
         let values =
             Arc::new(cascade(shared_context.stylist.device(),
                              rule_node,
                              &shared_context.guards,
                              style_to_inherit_from,
                              layout_parent_style,
+                             visited_values_to_insert,
                              Some(&mut cascade_info),
                              &*shared_context.error_reporter,
                              font_metrics_provider,
                              cascade_flags,
                              shared_context.quirks_mode));
 
         cascade_info.finish(&self.as_node());
         values
     }
 
     fn cascade_internal(&self,
                         context: &StyleContext<Self>,
                         primary_style: &ComputedStyle,
-                        eager_pseudo_style: Option<&ComputedStyle>)
+                        eager_pseudo_style: Option<&ComputedStyle>,
+                        cascade_visited: CascadeVisitedMode)
                         -> Arc<ComputedValues> {
         if let Some(pseudo) = self.implemented_pseudo_element() {
             debug_assert!(eager_pseudo_style.is_none());
 
             // This is an element-backed pseudo, just grab the styles from the
             // parent if it's eager, and recascade otherwise.
             //
             // We also recascade if the eager pseudo-style has any animation
@@ -255,49 +314,73 @@ trait PrivateMatchMethods: TElement {
             // We could make that a bit better if the complexity cost is not too
             // big, but given further restyles are posted directly to
             // pseudo-elements, it doesn't seem worth the effort at a glance.
             if pseudo.is_eager() && self.get_animation_rules().is_empty() {
                 let parent = self.parent_element().unwrap();
                 let parent_data = parent.borrow_data().unwrap();
                 let pseudo_style =
                     parent_data.styles().pseudos.get(&pseudo).unwrap();
-                return pseudo_style.values().clone()
-            }
+                let values = cascade_visited.values(pseudo_style);
+                return values.clone()
+             }
         }
 
+        // Find possible visited computed styles to insert within the regular
+        // computed values we are about to create.
+        let visited_values_to_insert = if cascade_visited.visited_values_for_insertion() {
+            match eager_pseudo_style {
+                Some(ref s) => s.clone_visited_values(),
+                None => primary_style.clone_visited_values(),
+            }
+        } else {
+            None
+        };
+
         // Grab the rule node.
-        let rule_node = &eager_pseudo_style.unwrap_or(primary_style).rules;
+        let style = eager_pseudo_style.unwrap_or(primary_style);
+        let rule_node = cascade_visited.rules(style);
         let inherit_mode = if eager_pseudo_style.is_some() {
             InheritMode::FromPrimaryStyle
         } else {
             InheritMode::Normal
         };
 
         self.cascade_with_rules(context.shared,
                                 &context.thread_local.font_metrics_provider,
                                 rule_node,
                                 primary_style,
-                                inherit_mode)
+                                inherit_mode,
+                                cascade_visited,
+                                visited_values_to_insert)
     }
 
-    /// Computes values and damage for the primary or pseudo style of an element,
-    /// setting them on the ElementData.
+    /// Computes values and damage for the primary style of an element, setting
+    /// them on the ElementData.
     fn cascade_primary(&self,
                        context: &mut StyleContext<Self>,
                        data: &mut ElementData,
-                       important_rules_changed: bool)
+                       important_rules_changed: bool,
+                       cascade_visited: CascadeVisitedMode)
                        -> ChildCascadeRequirement {
+        debug!("Cascade primary for {:?}, visited: {:?}", self, cascade_visited);
+
         // Collect some values.
         let (mut styles, restyle) = data.styles_and_restyle_mut();
         let mut primary_style = &mut styles.primary;
-        let mut old_values = primary_style.values.take();
+        if !cascade_visited.has_rules(primary_style) {
+            return ChildCascadeRequirement::CanSkipCascade
+        }
+        let mut old_values = cascade_visited.take_values(primary_style);
 
         // Compute the new values.
-        let mut new_values = self.cascade_internal(context, primary_style, None);
+        let mut new_values = self.cascade_internal(context,
+                                                   primary_style,
+                                                   None,
+                                                   cascade_visited);
 
         // NB: Animations for pseudo-elements in Gecko are handled while
         // traversing the pseudo-elements themselves.
         if !context.shared.traversal_flags.for_animation_only() {
             self.process_animations(context,
                                     &mut old_values,
                                     &mut new_values,
                                     primary_style,
@@ -307,66 +390,77 @@ trait PrivateMatchMethods: TElement {
         let child_cascade_requirement =
             self.accumulate_damage(&context.shared,
                                    restyle,
                                    old_values.as_ref().map(|v| v.as_ref()),
                                    &new_values,
                                    None);
 
         // Set the new computed values.
-        primary_style.values = Some(new_values);
+        cascade_visited.set_values(primary_style, new_values);
 
         // Return whether the damage indicates we must cascade new inherited
         // values into children.
         child_cascade_requirement
     }
 
+    /// Computes values and damage for the eager pseudo-element styles of an
+    /// element, setting them on the ElementData.
     fn cascade_eager_pseudo(&self,
                             context: &mut StyleContext<Self>,
                             data: &mut ElementData,
-                            pseudo: &PseudoElement) {
+                            pseudo: &PseudoElement,
+                            cascade_visited: CascadeVisitedMode) {
         debug_assert!(pseudo.is_eager());
         let (mut styles, restyle) = data.styles_and_restyle_mut();
         let mut pseudo_style = styles.pseudos.get_mut(pseudo).unwrap();
-        let old_values = pseudo_style.values.take();
+        if !cascade_visited.has_rules(pseudo_style) {
+            return
+        }
+        let old_values = cascade_visited.take_values(pseudo_style);
 
-        let new_values =
-            self.cascade_internal(context, &styles.primary, Some(pseudo_style));
+        let new_values = self.cascade_internal(context,
+                                               &styles.primary,
+                                               Some(pseudo_style),
+                                               cascade_visited);
 
         self.accumulate_damage(&context.shared,
                                restyle,
                                old_values.as_ref().map(|v| &**v),
                                &new_values,
                                Some(pseudo));
 
-        pseudo_style.values = Some(new_values)
+        cascade_visited.set_values(pseudo_style, new_values);
     }
 
-
     /// get_after_change_style removes the transition rules from the ComputedValues.
     /// If there is no transition rule in the ComputedValues, it returns None.
     #[cfg(feature = "gecko")]
     fn get_after_change_style(&self,
                               context: &mut StyleContext<Self>,
                               primary_style: &ComputedStyle)
                               -> Option<Arc<ComputedValues>> {
         let rule_node = &primary_style.rules;
         let without_transition_rules =
             context.shared.stylist.rule_tree().remove_transition_rule_if_applicable(rule_node);
         if without_transition_rules == *rule_node {
             // We don't have transition rule in this case, so return None to let the caller
             // use the original ComputedValues.
             return None;
         }
 
+        // This currently ignores visited styles, which seems acceptable,
+        // as existing browsers don't appear to transition visited styles.
         Some(self.cascade_with_rules(context.shared,
                                      &context.thread_local.font_metrics_provider,
                                      &without_transition_rules,
                                      primary_style,
-                                     InheritMode::Normal))
+                                     InheritMode::Normal,
+                                     CascadeVisitedMode::Unvisited,
+                                     None))
     }
 
     #[cfg(feature = "gecko")]
     fn needs_animations_update(&self,
                                context: &mut StyleContext<Self>,
                                old_values: Option<&Arc<ComputedValues>>,
                                new_values: &ComputedValues)
                                -> bool {
@@ -586,59 +680,116 @@ trait PrivateMatchMethods: TElement {
                         possibly_expired_animations.push(frame.property_animation.clone())
                     }
                 }
             }
         }
     }
 }
 
-fn compute_rule_node<E: TElement>(rule_tree: &RuleTree,
-                                  applicable_declarations: &mut ApplicableDeclarationList,
-                                  guards: &StylesheetGuards)
-                                  -> StrongRuleNode
-{
-    let rules = applicable_declarations.drain().map(|d| (d.source, d.level));
-    let rule_node = rule_tree.insert_ordered_rules_with_important(rules, guards);
-    rule_node
+impl<E: TElement> PrivateMatchMethods for E {}
+
+/// Collects the outputs of the primary matching process, including the rule
+/// node and other associated data.
+#[derive(Debug)]
+pub struct MatchingResults {
+    /// Whether the rules changed.
+    rules_changed: bool,
+    /// Whether there are any changes of important rules overriding animations.
+    important_rules_overriding_animation_changed: bool,
+    /// Records certains relations between elements noticed during matching (and
+    /// also extended after matching).
+    relations: StyleRelations,
+    /// Whether we encountered a "relevant link" while matching _any_ selector
+    /// for this element. (This differs from `RelevantLinkStatus` which tracks
+    /// the status for the _current_ selector only.)
+    relevant_link_found: bool,
 }
 
-impl<E: TElement> PrivateMatchMethods for E {}
+impl MatchingResults {
+    /// Create `MatchingResults` with only the basic required outputs.
+    fn new(rules_changed: bool, important_rules: bool) -> Self {
+        Self {
+            rules_changed: rules_changed,
+            important_rules_overriding_animation_changed: important_rules,
+            relations: StyleRelations::default(),
+            relevant_link_found: false,
+        }
+    }
+
+    /// Create `MatchingResults` from the output fields of `MatchingContext`.
+    fn new_from_context(rules_changed: bool,
+                        important_rules: bool,
+                        context: MatchingContext)
+                        -> Self {
+        Self {
+            rules_changed: rules_changed,
+            important_rules_overriding_animation_changed: important_rules,
+            relations: context.relations,
+            relevant_link_found: context.relevant_link_found,
+        }
+    }
+}
 
 /// The public API that elements expose for selector matching.
 pub trait MatchMethods : TElement {
     /// Performs selector matching and property cascading on an element and its
     /// eager pseudos.
     fn match_and_cascade(&self,
                          context: &mut StyleContext<Self>,
                          data: &mut ElementData,
                          sharing: StyleSharingBehavior)
                          -> ChildCascadeRequirement
     {
+        debug!("Match and cascade for {:?}", self);
+
         // Perform selector matching for the primary style.
-        let mut relations = StyleRelations::empty();
-        let result = self.match_primary(context, data, &mut relations);
+        let mut primary_results =
+            self.match_primary(context, data, VisitedHandlingMode::AllLinksUnvisited);
+        let important_rules_changed =
+            primary_results.important_rules_overriding_animation_changed;
+
+        // If there's a relevant link involved, match and cascade primary styles
+        // as if the link is visited as well.  This is done before the regular
+        // cascade because the visited ComputedValues are placed within the
+        // regular ComputedValues, which is immutable after the cascade.
+        let relevant_link_found = primary_results.relevant_link_found;
+        if relevant_link_found {
+            self.match_primary(context, data, VisitedHandlingMode::RelevantLinkVisited);
+            self.cascade_primary(context, data, important_rules_changed,
+                                 CascadeVisitedMode::Visited);
+        }
 
         // Cascade properties and compute primary values.
         let child_cascade_requirement =
-            self.cascade_primary(
-                context,
-                data,
-                result.important_rules_overriding_animation_changed
-            );
+            self.cascade_primary(context, data, important_rules_changed,
+                                 CascadeVisitedMode::Unvisited);
 
         // Match and cascade eager pseudo-elements.
         if !data.styles().is_display_none() {
-            let _pseudo_rule_nodes_changed = self.match_pseudos(context, data);
-            self.cascade_pseudos(context, data);
+            self.match_pseudos(context, data, VisitedHandlingMode::AllLinksUnvisited);
+
+            // If there's a relevant link involved, match and cascade eager
+            // pseudo-element styles as if the link is visited as well.
+            // This runs after matching for regular styles because matching adds
+            // each pseudo as needed to the PseudoMap, and this runs before
+            // cascade for regular styles because the visited ComputedValues
+            // are placed within the regular ComputedValues, which is immutable
+            // after the cascade.
+            if relevant_link_found {
+                self.match_pseudos(context, data, VisitedHandlingMode::RelevantLinkVisited);
+                self.cascade_pseudos(context, data, CascadeVisitedMode::Visited);
+            }
+
+            self.cascade_pseudos(context, data, CascadeVisitedMode::Unvisited);
         }
 
         // If we have any pseudo elements, indicate so in the primary StyleRelations.
         if !data.styles().pseudos.is_empty() {
-            relations |= AFFECTED_BY_PSEUDO_ELEMENTS;
+            primary_results.relations |= AFFECTED_BY_PSEUDO_ELEMENTS;
         }
 
         // If the style is shareable, add it to the LRU cache.
         if sharing == StyleSharingBehavior::Allow {
             // If we previously tried to match this element against the cache,
             // the revalidation match results will already be cached. Otherwise
             // we'll have None, and compute them later on-demand.
             //
@@ -648,46 +799,58 @@ pub trait MatchMethods : TElement {
                                                     .current_element_info
                                                     .as_mut().unwrap()
                                                     .revalidation_match_results
                                                     .take();
             context.thread_local
                    .style_sharing_candidate_cache
                    .insert_if_possible(self,
                                        data.styles().primary.values(),
-                                       relations,
+                                       primary_results.relations,
                                        revalidation_match_results);
         }
 
         child_cascade_requirement
     }
 
     /// Performs the cascade, without matching.
     fn cascade_primary_and_pseudos(&self,
                                    context: &mut StyleContext<Self>,
                                    mut data: &mut ElementData,
                                    important_rules_changed: bool)
                                    -> ChildCascadeRequirement
     {
+        // If there's a relevant link involved, cascade styles as if the link is
+        // visited as well. This is done before the regular cascade because the
+        // visited ComputedValues are placed within the regular ComputedValues,
+        // which is immutable after the cascade.  If there aren't any visited
+        // rules, these calls will return without cascading.
+        self.cascade_primary(context, &mut data, important_rules_changed,
+                             CascadeVisitedMode::Visited);
         let child_cascade_requirement =
-            self.cascade_primary(context, &mut data, important_rules_changed);
-        self.cascade_pseudos(context, &mut data);
+            self.cascade_primary(context, &mut data, important_rules_changed,
+                                 CascadeVisitedMode::Unvisited);
+        self.cascade_pseudos(context, &mut data, CascadeVisitedMode::Visited);
+        self.cascade_pseudos(context, &mut data, CascadeVisitedMode::Unvisited);
         child_cascade_requirement
     }
 
-    /// Runs selector matching to (re)compute the primary rule node for this element.
+    /// Runs selector matching to (re)compute the primary rule node for this
+    /// element.
     ///
-    /// Returns RulesMatchedResult which indicates whether the primary rule node changed
-    /// and whether the change includes important rules.
+    /// Returns `MatchingResults` with the new rules and other associated data
+    /// from the matching process.
     fn match_primary(&self,
                      context: &mut StyleContext<Self>,
                      data: &mut ElementData,
-                     relations: &mut StyleRelations)
-                     -> RulesMatchedResult
+                     visited_handling: VisitedHandlingMode)
+                     -> MatchingResults
     {
+        debug!("Match primary for {:?}, visited: {:?}", self, visited_handling);
+
         let implemented_pseudo = self.implemented_pseudo_element();
         if let Some(ref pseudo) = implemented_pseudo {
             if pseudo.is_eager() {
                 // If it's an eager element-backed pseudo, just grab the matched
                 // rules from the parent, and update animations.
                 let parent = self.parent_element().unwrap();
                 let parent_data = parent.borrow_data().unwrap();
                 let pseudo_style =
@@ -721,56 +884,61 @@ pub trait MatchMethods : TElement {
                 }
 
                 let important_rules_changed =
                     self.has_animations() &&
                     data.has_styles() &&
                     data.important_rules_are_different(&rules,
                                                        &context.shared.guards);
 
-                return RulesMatchedResult {
-                    rule_nodes_changed: data.set_primary_rules(rules),
-                    important_rules_overriding_animation_changed: important_rules_changed,
+                let rules_changed = match visited_handling {
+                    VisitedHandlingMode::AllLinksUnvisited => {
+                        data.set_primary_rules(rules)
+                    },
+                    VisitedHandlingMode::RelevantLinkVisited => {
+                        data.styles_mut().primary.set_visited_rules(rules)
+                    },
                 };
+
+                return MatchingResults::new(rules_changed, important_rules_changed)
             }
         }
 
         let mut applicable_declarations = ApplicableDeclarationList::new();
 
         let stylist = &context.shared.stylist;
         let style_attribute = self.style_attribute();
         let smil_override = self.get_smil_override();
         let animation_rules = self.get_animation_rules();
-        let bloom = context.thread_local.bloom_filter.filter();
-
 
         let map = &mut context.thread_local.selector_flags;
         let mut set_selector_flags = |element: &Self, flags: ElementSelectorFlags| {
             self.apply_selector_flags(map, element, flags);
         };
 
+        let bloom_filter = context.thread_local.bloom_filter.filter();
         let mut matching_context =
-            MatchingContext::new(MatchingMode::Normal, Some(bloom));
+            MatchingContext::new_for_visited(MatchingMode::Normal,
+                                             Some(bloom_filter),
+                                             visited_handling);
 
         // Compute the primary rule node.
         stylist.push_applicable_declarations(self,
                                              implemented_pseudo.as_ref(),
                                              style_attribute,
                                              smil_override,
                                              animation_rules,
                                              &mut applicable_declarations,
                                              &mut matching_context,
                                              &mut set_selector_flags);
 
-        *relations = matching_context.relations;
-
-        let primary_rule_node =
-            compute_rule_node::<Self>(stylist.rule_tree(),
-                                      &mut applicable_declarations,
-                                      &context.shared.guards);
+        let primary_rule_node = stylist.rule_tree().compute_rule_node(
+            &mut applicable_declarations,
+            &context.shared.guards
+        );
 
         if log_enabled!(Trace) {
             trace!("Matched rules:");
             for rn in primary_rule_node.self_and_ancestors() {
                 if let Some(source) = rn.style_source() {
                     trace!(" > {:?}", source);
                 }
             }
@@ -779,98 +947,110 @@ pub trait MatchMethods : TElement {
         let important_rules_changed =
             self.has_animations() &&
             data.has_styles() &&
             data.important_rules_are_different(
                 &primary_rule_node,
                 &context.shared.guards
             );
 
-        RulesMatchedResult {
-            rule_nodes_changed: data.set_primary_rules(primary_rule_node),
-            important_rules_overriding_animation_changed: important_rules_changed,
-        }
+        let rules_changed = match visited_handling {
+            VisitedHandlingMode::AllLinksUnvisited => {
+                data.set_primary_rules(primary_rule_node)
+            },
+            VisitedHandlingMode::RelevantLinkVisited => {
+                data.styles_mut().primary.set_visited_rules(primary_rule_node)
+            },
+        };
+
+        MatchingResults::new_from_context(rules_changed,
+                                          important_rules_changed,
+                                          matching_context)
     }
 
     /// Runs selector matching to (re)compute eager pseudo-element rule nodes
     /// for this element.
-    ///
-    /// Returns whether any of the pseudo rule nodes changed (including, but not
-    /// limited to, cases where we match different pseudos altogether).
     fn match_pseudos(&self,
                      context: &mut StyleContext<Self>,
-                     data: &mut ElementData)
-                     -> bool
+                     data: &mut ElementData,
+                     visited_handling: VisitedHandlingMode)
     {
+        debug!("Match pseudos for {:?}, visited: {:?}", self, visited_handling);
+
         if self.implemented_pseudo_element().is_some() {
             // Element pseudos can't have any other pseudo.
-            return false;
+            return;
         }
 
         let mut applicable_declarations = ApplicableDeclarationList::new();
 
         let map = &mut context.thread_local.selector_flags;
         let mut set_selector_flags = |element: &Self, flags: ElementSelectorFlags| {
             self.apply_selector_flags(map, element, flags);
         };
 
         // Borrow the stuff we need here so the borrow checker doesn't get mad
         // at us later in the closure.
         let stylist = &context.shared.stylist;
         let guards = &context.shared.guards;
-        let rule_tree = stylist.rule_tree();
+
         let bloom_filter = context.thread_local.bloom_filter.filter();
-
         let mut matching_context =
-            MatchingContext::new(MatchingMode::ForStatelessPseudoElement,
-                                 Some(bloom_filter));
+            MatchingContext::new_for_visited(MatchingMode::ForStatelessPseudoElement,
+                                             Some(bloom_filter),
+                                             visited_handling);
 
         // Compute rule nodes for eagerly-cascaded pseudo-elements.
         let mut matches_different_pseudos = false;
-        let mut rule_nodes_changed = false;
         SelectorImpl::each_eagerly_cascaded_pseudo_element(|pseudo| {
-            let mut pseudos = &mut data.styles_mut().pseudos;
+            // For pseudo-elements, we only try to match visited rules if there
+            // are also unvisited rules.  (This matches Gecko's behavior.)
+            if visited_handling == VisitedHandlingMode::RelevantLinkVisited &&
+               !data.styles().pseudos.has(&pseudo) {
+                return
+            }
+
             debug_assert!(applicable_declarations.is_empty());
             // NB: We handle animation rules for ::before and ::after when
             // traversing them.
             stylist.push_applicable_declarations(self,
                                                  Some(&pseudo),
                                                  None,
                                                  None,
                                                  AnimationRules(None, None),
                                                  &mut applicable_declarations,
                                                  &mut matching_context,
                                                  &mut set_selector_flags);
 
+            let pseudos = &mut data.styles_mut().pseudos;
             if !applicable_declarations.is_empty() {
-                let new_rules =
-                    compute_rule_node::<Self>(rule_tree,
-                                              &mut applicable_declarations,
-                                              &guards);
-                if pseudos.has(&pseudo) {
-                    rule_nodes_changed = pseudos.set_rules(&pseudo, new_rules);
-                } else {
-                    pseudos.insert(&pseudo, ComputedStyle::new_partial(new_rules));
-                    matches_different_pseudos = true;
-                }
-            } else if pseudos.take(&pseudo).is_some() {
-                matches_different_pseudos = true;
+                let rules = stylist.rule_tree().compute_rule_node(
+                    &mut applicable_declarations,
+                    &guards
+                );
+                matches_different_pseudos |= pseudos.add_rules(
+                    &pseudo,
+                    visited_handling,
+                    rules
+                );
+            } else {
+                matches_different_pseudos |= pseudos.remove_rules(
+                    &pseudo,
+                    visited_handling
+                );
             }
         });
 
         if matches_different_pseudos {
-            rule_nodes_changed = true;
             if let Some(r) = data.get_restyle_mut() {
                 // Any changes to the matched pseudo-elements trigger
                 // reconstruction.
                 r.damage |= RestyleDamage::reconstruct();
             }
         }
-
-        rule_nodes_changed
     }
 
     /// Applies selector flags to an element, deferring mutations of the parent
     /// until after the traversal.
     ///
     /// TODO(emilio): This is somewhat inefficient, because of a variety of
     /// reasons:
     ///
@@ -1110,26 +1290,29 @@ pub trait MatchMethods : TElement {
                self, pseudo);
         // Something else. Be conservative for now.
         StyleDifference::new(RestyleDamage::reconstruct(), StyleChange::Changed)
     }
 
     /// Performs the cascade for the element's eager pseudos.
     fn cascade_pseudos(&self,
                        context: &mut StyleContext<Self>,
-                       mut data: &mut ElementData)
+                       mut data: &mut ElementData,
+                       cascade_visited: CascadeVisitedMode)
     {
+        debug!("Cascade pseudos for {:?}, visited: {:?}", self,
+               cascade_visited);
         // Note that we've already set up the map of matching pseudo-elements
         // in match_pseudos (and handled the damage implications of changing
         // which pseudos match), so now we can just iterate what we have. This
         // does mean collecting owned pseudos, so that the borrow checker will
         // let us pass the mutable |data| to the cascade function.
         let matched_pseudos = data.styles().pseudos.keys();
         for pseudo in matched_pseudos {
-            self.cascade_eager_pseudo(context, data, &pseudo);
+            self.cascade_eager_pseudo(context, data, &pseudo, cascade_visited);
         }
     }
 
     /// Returns computed values without animation and transition rules.
     fn get_base_style(&self,
                       shared_context: &SharedStyleContext,
                       font_metrics_provider: &FontMetricsProvider,
                       primary_style: &ComputedStyle,
@@ -1140,18 +1323,22 @@ pub trait MatchMethods : TElement {
         let without_animation_rules =
             shared_context.stylist.rule_tree().remove_animation_rules(rule_node);
         if without_animation_rules == *rule_node {
             // Note that unwrapping here is fine, because the style is
             // only incomplete during the styling process.
             return relevant_style.values.as_ref().unwrap().clone();
         }
 
+        // This currently ignores visited styles, which seems acceptable,
+        // as existing browsers don't appear to animate visited styles.
         self.cascade_with_rules(shared_context,
                                 font_metrics_provider,
                                 &without_animation_rules,
                                 primary_style,
-                                InheritMode::Normal)
+                                InheritMode::Normal,
+                                CascadeVisitedMode::Unvisited,
+                                None)
     }
 
 }
 
 impl<E: TElement> MatchMethods for E {}
--- a/servo/components/style/properties/gecko.mako.rs
+++ b/servo/components/style/properties/gecko.mako.rs
@@ -95,46 +95,54 @@ pub struct ComputedValues {
     /// integer stores the final ratio of the chain of font size relative values.
     /// and is 1 when there was just a keyword and no relative values.
     ///
     /// When this is Some, we compute font sizes by computing the keyword against
     /// the generic font, and then multiplying it by the ratio.
     pub font_size_keyword: Option<(longhands::font_size::KeywordSize, f32)>,
     /// The cached system font. See longhand/font.mako.rs
     pub cached_system_font: Option<longhands::system_font::ComputedSystemFont>,
+
+    /// The element's computed values if visited, only computed if there's a
+    /// relevant link for this element. A element's "relevant link" is the
+    /// element being matched if it is a link or the nearest ancestor link.
+    visited_style: Option<Arc<ComputedValues>>,
 }
 
 impl ComputedValues {
     pub fn new(custom_properties: Option<Arc<ComputedValuesMap>>,
                writing_mode: WritingMode,
                root_font_size: Au,
                font_size_keyword: Option<(longhands::font_size::KeywordSize, f32)>,
+               visited_style: Option<Arc<ComputedValues>>,
                % for style_struct in data.style_structs:
                ${style_struct.ident}: Arc<style_structs::${style_struct.name}>,
                % endfor
     ) -> Self {
         ComputedValues {
             custom_properties: custom_properties,
             writing_mode: writing_mode,
             root_font_size: root_font_size,
             cached_system_font: None,
             font_size_keyword: font_size_keyword,
+            visited_style: visited_style,
             % for style_struct in data.style_structs:
             ${style_struct.ident}: ${style_struct.ident},
             % endfor
         }
     }
 
     pub fn default_values(pres_context: RawGeckoPresContextBorrowed) -> Arc<Self> {
         Arc::new(ComputedValues {
             custom_properties: None,
             writing_mode: WritingMode::empty(), // FIXME(bz): This seems dubious
             root_font_size: longhands::font_size::get_initial_value(), // FIXME(bz): Also seems dubious?
             font_size_keyword: Some((Default::default(), 1.)),
             cached_system_font: None,
+            visited_style: None,
             % for style_struct in data.style_structs:
                 ${style_struct.ident}: style_structs::${style_struct.name}::default(pres_context),
             % endfor
         })
     }
 
     #[inline]
     pub fn is_display_contents(&self) -> bool {
@@ -163,16 +171,33 @@ impl ComputedValues {
     }
 
     #[inline]
     pub fn mutate_${style_struct.name_lower}(&mut self) -> &mut style_structs::${style_struct.name} {
         Arc::make_mut(&mut self.${style_struct.ident})
     }
     % endfor
 
+    /// Gets a reference to the visited computed values, if any.
+    pub fn get_visited_style(&self) -> Option<<&Arc<ComputedValues>> {
+        self.visited_style.as_ref()
+    }
+
+    /// Gets a reference to the visited computed values. Panic if the element
+    /// does not have visited computed values.
+    pub fn visited_style(&self) -> &Arc<ComputedValues> {
+        self.get_visited_style().unwrap()
+    }
+
+    /// Clone the visited computed values Arc.  Used for inheriting parent styles
+    /// in StyleBuilder::for_inheritance.
+    pub fn clone_visited_style(&self) -> Option<Arc<ComputedValues>> {
+        self.visited_style.clone()
+    }
+
     pub fn custom_properties(&self) -> Option<Arc<ComputedValuesMap>> {
         self.custom_properties.clone()
     }
 
     #[allow(non_snake_case)]
     pub fn has_moz_binding(&self) -> bool {
         !self.get_box().gecko.mBinding.mPtr.mRawPtr.is_null()
     }
--- a/servo/components/style/properties/properties.mako.rs
+++ b/servo/components/style/properties/properties.mako.rs
@@ -1738,34 +1738,41 @@ pub struct ComputedValues {
     % endfor
     custom_properties: Option<Arc<::custom_properties::ComputedValuesMap>>,
     /// The writing mode of this computed values struct.
     pub writing_mode: WritingMode,
     /// The root element's computed font size.
     pub root_font_size: Au,
     /// The keyword behind the current font-size property, if any
     pub font_size_keyword: Option<(longhands::font_size::KeywordSize, f32)>,
+
+    /// The element's computed values if visited, only computed if there's a
+    /// relevant link for this element. A element's "relevant link" is the
+    /// element being matched if it is a link or the nearest ancestor link.
+    visited_style: Option<Arc<ComputedValues>>,
 }
 
 #[cfg(feature = "servo")]
 impl ComputedValues {
     /// Construct a `ComputedValues` instance.
     pub fn new(custom_properties: Option<Arc<::custom_properties::ComputedValuesMap>>,
                writing_mode: WritingMode,
                root_font_size: Au,
                font_size_keyword: Option<(longhands::font_size::KeywordSize, f32)>,
+               visited_style: Option<Arc<ComputedValues>>,
             % for style_struct in data.active_style_structs():
                ${style_struct.ident}: Arc<style_structs::${style_struct.name}>,
             % endfor
     ) -> Self {
         ComputedValues {
             custom_properties: custom_properties,
             writing_mode: writing_mode,
             root_font_size: root_font_size,
             font_size_keyword: font_size_keyword,
+            visited_style: visited_style,
         % for style_struct in data.active_style_structs():
             ${style_struct.ident}: ${style_struct.ident},
         % endfor
         }
     }
 
     /// Get the initial computed values.
     pub fn initial_values() -> &'static Self { &*INITIAL_SERVO_VALUES }
@@ -1791,16 +1798,33 @@ impl ComputedValues {
 
         /// Get a mutable reference to the ${style_struct.name} struct.
         #[inline]
         pub fn mutate_${style_struct.name_lower}(&mut self) -> &mut style_structs::${style_struct.name} {
             Arc::make_mut(&mut self.${style_struct.ident})
         }
     % endfor
 
+    /// Gets a reference to the visited computed values, if any.
+    pub fn get_visited_style(&self) -> Option<<&Arc<ComputedValues>> {
+        self.visited_style.as_ref()
+    }
+
+    /// Gets a reference to the visited computed values. Panic if the element
+    /// does not have visited computed values.
+    pub fn visited_style(&self) -> &Arc<ComputedValues> {
+        self.get_visited_style().unwrap()
+    }
+
+    /// Clone the visited computed values Arc.  Used for inheriting parent styles
+    /// in StyleBuilder::for_inheritance.
+    pub fn clone_visited_style(&self) -> Option<Arc<ComputedValues>> {
+        self.visited_style.clone()
+    }
+
     /// Get the custom properties map if necessary.
     ///
     /// Cloning the Arc here is fine because it only happens in the case where
     /// we have custom properties, and those are both rare and expensive.
     fn custom_properties(&self) -> Option<Arc<::custom_properties::ComputedValuesMap>> {
         self.custom_properties.clone()
     }
 
@@ -2178,37 +2202,43 @@ pub struct StyleBuilder<'a> {
     /// The writing mode flags.
     ///
     /// TODO(emilio): Make private.
     pub writing_mode: WritingMode,
     /// The font size of the root element.
     pub root_font_size: Au,
     /// The keyword behind the current font-size property, if any.
     pub font_size_keyword: Option<(longhands::font_size::KeywordSize, f32)>,
+    /// The element's style if visited, only computed if there's a relevant link
+    /// for this element.  A element's "relevant link" is the element being
+    /// matched if it is a link or the nearest ancestor link.
+    visited_style: Option<Arc<ComputedValues>>,
     % for style_struct in data.active_style_structs():
         ${style_struct.ident}: StyleStructRef<'a, style_structs::${style_struct.name}>,
     % endfor
 }
 
 impl<'a> StyleBuilder<'a> {
     /// Trivially construct a `StyleBuilder`.
     pub fn new(
         custom_properties: Option<Arc<::custom_properties::ComputedValuesMap>>,
         writing_mode: WritingMode,
         root_font_size: Au,
         font_size_keyword: Option<(longhands::font_size::KeywordSize, f32)>,
+        visited_style: Option<Arc<ComputedValues>>,
         % for style_struct in data.active_style_structs():
             ${style_struct.ident}: &'a Arc<style_structs::${style_struct.name}>,
         % endfor
     ) -> Self {
         StyleBuilder {
             custom_properties: custom_properties,
             writing_mode: writing_mode,
             root_font_size: root_font_size,
             font_size_keyword: font_size_keyword,
+            visited_style: visited_style,
         % for style_struct in data.active_style_structs():
             ${style_struct.ident}: StyleStructRef::Borrowed(${style_struct.ident}),
         % endfor
         }
     }
 
     /// Creates a StyleBuilder holding only references to the structs of `s`, in
     /// order to create a derived style.
@@ -2218,16 +2248,17 @@ impl<'a> StyleBuilder<'a> {
 
     /// Inherits style from the parent element, accounting for the default
     /// computed values that need to be provided as well.
     pub fn for_inheritance(parent: &'a ComputedValues, default: &'a ComputedValues) -> Self {
         Self::new(parent.custom_properties(),
                   parent.writing_mode,
                   parent.root_font_size,
                   parent.font_size_keyword,
+                  parent.clone_visited_style(),
                   % for style_struct in data.active_style_structs():
                   % if style_struct.inherited:
                   parent.${style_struct.name_lower}_arc(),
                   % else:
                   default.${style_struct.name_lower}_arc(),
                   % endif
                   % endfor
         )
@@ -2291,16 +2322,17 @@ impl<'a> StyleBuilder<'a> {
 
 
     /// Turns this `StyleBuilder` into a proper `ComputedValues` instance.
     pub fn build(self) -> ComputedValues {
         ComputedValues::new(self.custom_properties,
                             self.writing_mode,
                             self.root_font_size,
                             self.font_size_keyword,
+                            self.visited_style,
                             % for style_struct in data.active_style_structs():
                             self.${style_struct.ident}.build(),
                             % endfor
         )
     }
 
     /// Get the custom properties map if necessary.
     ///
@@ -2334,16 +2366,17 @@ mod lazy_static_module {
                         hash: 0,
                     % endif
                 }),
             % endfor
             custom_properties: None,
             writing_mode: WritingMode::empty(),
             root_font_size: longhands::font_size::get_initial_value(),
             font_size_keyword: Some((Default::default(), 1.)),
+            visited_style: None,
         };
     }
 }
 
 /// A per-longhand function that performs the CSS cascade for that longhand.
 pub type CascadePropertyFn =
     extern "Rust" fn(declaration: &PropertyDeclaration,
                      inherited_style: &ComputedValues,
@@ -2387,16 +2420,17 @@ bitflags! {
 /// Returns the computed values.
 ///   * `flags`: Various flags.
 ///
 pub fn cascade(device: &Device,
                rule_node: &StrongRuleNode,
                guards: &StylesheetGuards,
                parent_style: Option<<&ComputedValues>,
                layout_parent_style: Option<<&ComputedValues>,
+               visited_style: Option<Arc<ComputedValues>>,
                cascade_info: Option<<&mut CascadeInfo>,
                error_reporter: &ParseErrorReporter,
                font_metrics_provider: &FontMetricsProvider,
                flags: CascadeFlags,
                quirks_mode: QuirksMode)
                -> ComputedValues {
     debug_assert_eq!(parent_style.is_some(), layout_parent_style.is_some());
     let (is_root_element, inherited_style, layout_parent_style) = match parent_style {
@@ -2433,31 +2467,33 @@ pub fn cascade(device: &Device,
                 })
         })
     };
     apply_declarations(device,
                        is_root_element,
                        iter_declarations,
                        inherited_style,
                        layout_parent_style,
+                       visited_style,
                        cascade_info,
                        error_reporter,
                        font_metrics_provider,
                        flags,
                        quirks_mode)
 }
 
 /// 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,
                                     is_root_element: bool,
                                     iter_declarations: F,
                                     inherited_style: &ComputedValues,
                                     layout_parent_style: &ComputedValues,
+                                    visited_style: Option<Arc<ComputedValues>>,
                                     mut cascade_info: Option<<&mut CascadeInfo>,
                                     error_reporter: &ParseErrorReporter,
                                     font_metrics_provider: &FontMetricsProvider,
                                     flags: CascadeFlags,
                                     quirks_mode: QuirksMode)
                                     -> ComputedValues
     where F: Fn() -> I,
           I: Iterator<Item = &'a PropertyDeclaration>,
@@ -2478,29 +2514,31 @@ pub fn apply_declarations<'a, F, I>(devi
         ::custom_properties::finish_cascade(
             custom_properties, &inherited_custom_properties);
 
     let builder = if !flags.contains(INHERIT_ALL) {
         StyleBuilder::new(custom_properties,
                           WritingMode::empty(),
                           inherited_style.root_font_size,
                           inherited_style.font_size_keyword,
+                          visited_style,
                           % for style_struct in data.active_style_structs():
                               % if style_struct.inherited:
                                   inherited_style.${style_struct.name_lower}_arc(),
                               % else:
                                   default_style.${style_struct.name_lower}_arc(),
                               % endif
                           % endfor
                           )
     } else {
         StyleBuilder::new(custom_properties,
                           WritingMode::empty(),
                           inherited_style.root_font_size,
                           inherited_style.font_size_keyword,
+                          visited_style,
                           % for style_struct in data.active_style_structs():
                               inherited_style.${style_struct.name_lower}_arc(),
                           % endfor
                           )
     };
 
     let mut context = computed::Context {
         is_root_element: is_root_element,
--- a/servo/components/style/rule_tree/mod.rs
+++ b/servo/components/style/rule_tree/mod.rs
@@ -11,16 +11,17 @@ use heapsize::HeapSizeOf;
 use properties::{Importance, LonghandIdSet, PropertyDeclarationBlock};
 use shared_lock::{Locked, StylesheetGuards, SharedRwLockReadGuard};
 use smallvec::SmallVec;
 use std::io::{self, Write};
 use std::ptr;
 use std::sync::atomic::{AtomicPtr, AtomicUsize, Ordering};
 use stylearc::Arc;
 use stylesheets::StyleRule;
+use stylist::ApplicableDeclarationList;
 use thread_state;
 
 /// The rule tree, the structure servo uses to preserve the results of selector
 /// matching.
 ///
 /// This is organized as a tree of rules. When a node matches a set of rules,
 /// they're inserted in order in the tree, starting with the less specific one.
 ///
@@ -210,16 +211,28 @@ impl RuleTree {
 
         if let Some(source) = transition {
             current = current.ensure_child(self.root.downgrade(), source, Transitions);
         }
 
         current
     }
 
+    /// Given a list of applicable declarations, insert the rules and return the
+    /// corresponding rule node.
+    pub fn compute_rule_node(&self,
+                             applicable_declarations: &mut ApplicableDeclarationList,
+                             guards: &StylesheetGuards)
+                             -> StrongRuleNode
+    {
+        let rules = applicable_declarations.drain().map(|d| (d.source, d.level));
+        let rule_node = self.insert_ordered_rules_with_important(rules, guards);
+        rule_node
+    }
+
     /// Insert the given rules, that must be in proper order by specifity, and
     /// return the corresponding rule node representing the last inserted one.
     pub fn insert_ordered_rules<'a, I>(&self, iter: I) -> StrongRuleNode
         where I: Iterator<Item=(StyleSource, CascadeLevel)>,
     {
         self.insert_ordered_rules_from(self.root.clone(), iter)
     }
 
@@ -627,16 +640,18 @@ impl RuleNode {
 #[derive(Clone)]
 struct WeakRuleNode {
     ptr: *mut RuleNode,
 }
 
 /// A strong reference to a rule node.
 #[derive(Debug, PartialEq)]
 pub struct StrongRuleNode {
+    // TODO: Mark this as NonZero once stable to save space inside Option.
+    // https://github.com/rust-lang/rust/issues/27730
     ptr: *mut RuleNode,
 }
 
 #[cfg(feature = "servo")]
 impl HeapSizeOf for StrongRuleNode {
     fn heap_size_of_children(&self) -> usize { 0 }
 }
 
--- a/servo/components/style/stylist.rs
+++ b/servo/components/style/stylist.rs
@@ -567,16 +567,17 @@ impl Stylist {
         // blockification.
         let computed =
             properties::cascade(&self.device,
                                 &rule_node,
                                 guards,
                                 parent.map(|p| &**p),
                                 parent.map(|p| &**p),
                                 None,
+                                None,
                                 &RustLogReporter,
                                 font_metrics,
                                 cascade_flags,
                                 self.quirks_mode);
         ComputedStyle::new(rule_node, Arc::new(computed))
     }
 
     /// Returns the style for an anonymous box of the given type.
@@ -638,23 +639,25 @@ impl Stylist {
                 Some(rule_node) => rule_node,
                 None => return None
             };
 
         // Read the comment on `precomputed_values_for_pseudo` to see why it's
         // difficult to assert that display: contents nodes never arrive here
         // (tl;dr: It doesn't apply for replaced elements and such, but the
         // computed value is still "contents").
+        // Bug 1364242: We need to add visited support for lazy pseudos
         let computed =
             properties::cascade(&self.device,
                                 &rule_node,
                                 guards,
                                 Some(&**parent),
                                 Some(&**parent),
                                 None,
+                                None,
                                 &RustLogReporter,
                                 font_metrics,
                                 CascadeFlags::empty(),
                                 self.quirks_mode);
 
         Some(ComputedStyle::new(rule_node, Arc::new(computed)))
     }
 
@@ -693,16 +696,17 @@ impl Stylist {
             let parent_flags = flags.for_parent();
             if !parent_flags.is_empty() {
                 if let Some(p) = element.parent_element() {
                     unsafe { p.set_selector_flags(parent_flags); }
                 }
             }
         };
 
+        // Bug 1364242: We need to add visited support for lazy pseudos
         let mut declarations = ApplicableDeclarationList::new();
         let mut matching_context =
             MatchingContext::new(MatchingMode::ForStatelessPseudoElement, None);
         self.push_applicable_declarations(element,
                                           Some(pseudo),
                                           None,
                                           None,
                                           AnimationRules(None, None),
@@ -1045,23 +1049,27 @@ impl Stylist {
 
         let v = vec![
             ApplicableDeclarationBlock::from_declarations(declarations.clone(),
                                                           CascadeLevel::StyleAttributeNormal)
         ];
         let rule_node =
             self.rule_tree.insert_ordered_rules(v.into_iter().map(|a| (a.source, a.level)));
 
+        // This currently ignores visited styles.  It appears to be used for
+        // font styles in <canvas> via Servo_StyleSet_ResolveForDeclarations.
+        // It is unclear if visited styles are meaningful for this case.
         let metrics = get_metrics_provider_for_product();
         Arc::new(properties::cascade(&self.device,
                                      &rule_node,
                                      guards,
                                      Some(parent_style),
                                      Some(parent_style),
                                      None,
+                                     None,
                                      &RustLogReporter,
                                      &metrics,
                                      CascadeFlags::empty(),
                                      self.quirks_mode))
     }
 
     /// Accessor for a shared reference to the device.
     pub fn device(&self) -> &Device {
--- a/servo/ports/geckolib/glue.rs
+++ b/servo/ports/geckolib/glue.rs
@@ -1239,16 +1239,25 @@ pub extern "C" fn Servo_ComputedValues_I
     } else {
         debug_assert!(!for_text);
         data.default_computed_values().clone()
     };
 
     style.into_strong()
 }
 
+#[no_mangle]
+pub extern "C" fn Servo_ComputedValues_GetVisitedStyle(values: ServoComputedValuesBorrowed)
+                                                       -> ServoComputedValuesStrong {
+    match ComputedValues::as_arc(&values).get_visited_style() {
+        Some(v) => v.clone().into_strong(),
+        None => Strong::null(),
+    }
+}
+
 /// See the comment in `Device` to see why it's ok to pass an owned reference to
 /// the pres context (hint: the context outlives the StyleSet, that holds the
 /// device alive).
 #[no_mangle]
 pub extern "C" fn Servo_StyleSet_Init(pres_context: RawGeckoPresContextOwned)
   -> RawServoStyleSetOwned {
     let data = Box::new(PerDocumentStyleData::new(pres_context));
     data.into_ffi()