Auto merge of #17032 - jryans:stylo-visited, r=emilio

Stylo: visited pseudo-class support

Reviewed in https://bugzilla.mozilla.org/show_bug.cgi?id=1328509

<!-- Reviewable:start -->
---
This change is [<img src="https://reviewable.io/review_button.svg" height="34" align="absmiddle" alt="Reviewable"/>](https://reviewable.io/reviews/servo/servo/17032)
<!-- Reviewable:end -->

17 files changed, 1007 insertions, 236 deletions

diff --git a/components/script/dom/element.rs b/components/script/dom/element.rs
index 0dc3db0ebe5..d7f3b89ba2f 100644
--- a/components/script/dom/element.rs
+++ b/components/script/dom/element.rs
@@ -87,8 +87,9 @@ use ref_filter_map::ref_filter_map;
 use script_layout_interface::message::ReflowQueryType;
 use script_thread::Runnable;
 use selectors::attr::{AttrSelectorOperation, NamespaceConstraint};
-use selectors::matching::{ElementSelectorFlags, MatchingContext, MatchingMode, matches_selector_list};
+use selectors::matching::{ElementSelectorFlags, MatchingContext, MatchingMode};
 use selectors::matching::{HAS_EDGE_CHILD_SELECTOR, HAS_SLOW_SELECTOR, HAS_SLOW_SELECTOR_LATER_SIBLINGS};
+use selectors::matching::{RelevantLinkStatus, matches_selector_list};
 use servo_atoms::Atom;
 use std::ascii::AsciiExt;
 use std::borrow::Cow;
@@ -2429,6 +2430,7 @@ impl<'a> ::selectors::Element for Root<Element> {
     fn match_non_ts_pseudo_class<F>(&self,
                                     pseudo_class: &NonTSPseudoClass,
                                     _: &mut MatchingContext,
+                                    _: &RelevantLinkStatus,
                                     _: &mut F)
                                     -> bool
         where F: FnMut(&Self, ElementSelectorFlags),
@@ -2478,6 +2480,20 @@ impl<'a> ::selectors::Element for Root<Element> {
         }
     }
 
+    fn is_link(&self) -> bool {
+        // FIXME: This is HTML only.
+        let node = self.upcast::<Node>();
+        match node.type_id() {
+            // https://html.spec.whatwg.org/multipage/#selector-link
+            NodeTypeId::Element(ElementTypeId::HTMLElement(HTMLElementTypeId::HTMLAnchorElement)) |
+            NodeTypeId::Element(ElementTypeId::HTMLElement(HTMLElementTypeId::HTMLAreaElement)) |
+            NodeTypeId::Element(ElementTypeId::HTMLElement(HTMLElementTypeId::HTMLLinkElement)) => {
+                self.has_attribute(&local_name!("href"))
+            },
+            _ => false,
+        }
+    }
+
     fn get_id(&self) -> Option<Atom> {
         self.id_attribute.borrow().clone()
     }
@@ -2592,20 +2608,6 @@ impl Element {
         }
     }
 
-    fn is_link(&self) -> bool {
-        // FIXME: This is HTML only.
-        let node = self.upcast::<Node>();
-        match node.type_id() {
-            // https://html.spec.whatwg.org/multipage/#selector-link
-            NodeTypeId::Element(ElementTypeId::HTMLElement(HTMLElementTypeId::HTMLAnchorElement)) |
-            NodeTypeId::Element(ElementTypeId::HTMLElement(HTMLElementTypeId::HTMLAreaElement)) |
-            NodeTypeId::Element(ElementTypeId::HTMLElement(HTMLElementTypeId::HTMLLinkElement)) => {
-                self.has_attribute(&local_name!("href"))
-            },
-            _ => false,
-        }
-    }
-
     /// Please call this method *only* for real click events
     ///
     /// https://html.spec.whatwg.org/multipage/#run-authentic-click-activation-steps
diff --git a/components/script/layout_wrapper.rs b/components/script/layout_wrapper.rs
index 5241d01785d..eab6f2fd9c9 100644
--- a/components/script/layout_wrapper.rs
+++ b/components/script/layout_wrapper.rs
@@ -51,7 +51,7 @@ use script_layout_interface::{OpaqueStyleAndLayoutData, PartialPersistentLayoutD
 use script_layout_interface::wrapper_traits::{DangerousThreadSafeLayoutNode, GetLayoutData, LayoutNode};
 use script_layout_interface::wrapper_traits::{PseudoElementType, ThreadSafeLayoutElement, ThreadSafeLayoutNode};
 use selectors::attr::{AttrSelectorOperation, NamespaceConstraint};
-use selectors::matching::{ElementSelectorFlags, MatchingContext};
+use selectors::matching::{ElementSelectorFlags, MatchingContext, RelevantLinkStatus};
 use servo_atoms::Atom;
 use servo_url::ServoUrl;
 use std::fmt;
@@ -680,6 +680,7 @@ impl<'le> ::selectors::Element for ServoLayoutElement<'le> {
     fn match_non_ts_pseudo_class<F>(&self,
                                     pseudo_class: &NonTSPseudoClass,
                                     _: &mut MatchingContext,
+                                    _: &RelevantLinkStatus,
                                     _: &mut F)
                                     -> bool
         where F: FnMut(&Self, ElementSelectorFlags),
@@ -687,16 +688,7 @@ impl<'le> ::selectors::Element for ServoLayoutElement<'le> {
         match *pseudo_class {
             // https://github.com/servo/servo/issues/8718
             NonTSPseudoClass::Link |
-            NonTSPseudoClass::AnyLink => unsafe {
-                match self.as_node().script_type_id() {
-                    // https://html.spec.whatwg.org/multipage/#selector-link
-                    NodeTypeId::Element(ElementTypeId::HTMLElement(HTMLElementTypeId::HTMLAnchorElement)) |
-                    NodeTypeId::Element(ElementTypeId::HTMLElement(HTMLElementTypeId::HTMLAreaElement)) |
-                    NodeTypeId::Element(ElementTypeId::HTMLElement(HTMLElementTypeId::HTMLLinkElement)) =>
-                        (*self.element.unsafe_get()).get_attr_val_for_layout(&ns!(), &local_name!("href")).is_some(),
-                    _ => false,
-                }
-            },
+            NonTSPseudoClass::AnyLink => self.is_link(),
             NonTSPseudoClass::Visited => false,
 
             // FIXME(#15746): This is wrong, we need to instead use extended filtering as per RFC4647
@@ -732,6 +724,20 @@ impl<'le> ::selectors::Element for ServoLayoutElement<'le> {
     }
 
     #[inline]
+    fn is_link(&self) -> bool {
+        unsafe {
+            match self.as_node().script_type_id() {
+                // https://html.spec.whatwg.org/multipage/#selector-link
+                NodeTypeId::Element(ElementTypeId::HTMLElement(HTMLElementTypeId::HTMLAnchorElement)) |
+                NodeTypeId::Element(ElementTypeId::HTMLElement(HTMLElementTypeId::HTMLAreaElement)) |
+                NodeTypeId::Element(ElementTypeId::HTMLElement(HTMLElementTypeId::HTMLLinkElement)) =>
+                    (*self.element.unsafe_get()).get_attr_val_for_layout(&ns!(), &local_name!("href")).is_some(),
+                _ => false,
+            }
+        }
+    }
+
+    #[inline]
     fn get_id(&self) -> Option<Atom> {
         unsafe {
             (*self.element.id_attribute()).clone()
@@ -1187,6 +1193,7 @@ impl<'le> ::selectors::Element for ServoThreadSafeLayoutElement<'le> {
     fn match_non_ts_pseudo_class<F>(&self,
                                     _: &NonTSPseudoClass,
                                     _: &mut MatchingContext,
+                                    _: &RelevantLinkStatus,
                                     _: &mut F)
                                     -> bool
         where F: FnMut(&Self, ElementSelectorFlags),
@@ -1196,6 +1203,11 @@ impl<'le> ::selectors::Element for ServoThreadSafeLayoutElement<'le> {
         false
     }
 
+    fn is_link(&self) -> bool {
+        warn!("ServoThreadSafeLayoutElement::is_link called");
+        false
+    }
+
     fn get_id(&self) -> Option<Atom> {
         debug!("ServoThreadSafeLayoutElement::get_id called");
         None
diff --git a/components/selectors/matching.rs b/components/selectors/matching.rs
index 50b686f2558..521bcb3b815 100644
--- a/components/selectors/matching.rs
+++ b/components/selectors/matching.rs
@@ -75,7 +75,7 @@ impl ElementSelectorFlags {
 ///
 /// 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,
@@ -94,18 +94,36 @@ pub enum MatchingMode {
     ForStatelessPseudoElement,
 }
 
+/// The mode to use when matching unvisited and visited links.
+#[derive(PartialEq, Eq, Copy, Clone, Debug)]
+pub enum VisitedHandlingMode {
+    /// All links are matched as if they are unvisted.
+    AllLinksUnvisited,
+    /// A element's "relevant link" is the element being matched if it is a link
+    /// 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.)
+    pub relevant_link_found: bool,
 }
 
 impl<'a> MatchingContext<'a> {
@@ -118,6 +136,23 @@ impl<'a> MatchingContext<'a> {
             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,
         }
     }
 }
@@ -156,6 +191,100 @@ fn may_match<E>(sel: &SelectorInner<E::Impl>,
     true
 }
 
+/// Tracks whether we are currently looking for relevant links for a given
+/// complex selector. A "relevant link" is the element being matched if it is a
+/// link or the nearest ancestor link.
+///
+/// `matches_complex_selector` creates a new instance of this for each complex
+/// selector we try to match for an element. This is done because `is_visited`
+/// and `is_unvisited` are based on relevant link state of only the current
+/// complex selector being matched (not the global relevant link status for all
+/// selectors in `MatchingContext`).
+#[derive(PartialEq, Eq, Copy, Clone)]
+pub enum RelevantLinkStatus {
+    /// Looking for a possible relevant link.  This is the initial mode when
+    /// matching a selector.
+    Looking,
+    /// Not looking for a relevant link.  We transition to this mode if we
+    /// encounter a sibiling combinator (since only ancestor combinators are
+    /// allowed for this purpose).
+    NotLooking,
+    /// Found a relevant link for the element being matched.
+    Found,
+}
+
+impl Default for RelevantLinkStatus {
+    fn default() -> Self {
+        RelevantLinkStatus::NotLooking
+    }
+}
+
+impl RelevantLinkStatus {
+    /// If we found the relevant link for this element, record that in the
+    /// overall matching context for the element as a whole and stop looking for
+    /// addtional links.
+    fn examine_potential_link<E>(&self, element: &E, context: &mut MatchingContext)
+                                 -> RelevantLinkStatus
+        where E: Element,
+    {
+        if *self != RelevantLinkStatus::Looking {
+            return *self
+        }
+
+        if !element.is_link() {
+            return *self
+        }
+
+        // We found a relevant link. Record this in the `MatchingContext`,
+        // where we track whether one was found for _any_ selector (meaning
+        // this field might already be true from a previous selector).
+        context.relevant_link_found = true;
+        // Also return `Found` to update the relevant link status for _this_
+        // specific selector's matching process.
+        RelevantLinkStatus::Found
+    }
+
+    /// Returns whether an element is considered visited for the purposes of
+    /// matching.  This is true only if the element is a link, an relevant link
+    /// exists for the element, and the visited handling mode is set to accept
+    /// relevant links as visited.
+    pub fn is_visited<E>(&self, element: &E, context: &MatchingContext) -> bool
+        where E: Element,
+    {
+        if !element.is_link() {
+            return false
+        }
+
+        // Non-relevant links are always unvisited.
+        if *self != RelevantLinkStatus::Found {
+            return false
+        }
+
+        context.visited_handling == VisitedHandlingMode::RelevantLinkVisited
+    }
+
+    /// Returns whether an element is considered unvisited for the purposes of
+    /// matching.  Assuming the element is a link, this is always true for
+    /// non-relevant links, since only relevant links can potentially be treated
+    /// as visited.  If this is a relevant link, then is it unvisited if the
+    /// visited handling mode is set to treat all links as unvisted (including
+    /// relevant links).
+    pub fn is_unvisited<E>(&self, element: &E, context: &MatchingContext) -> bool
+        where E: Element,
+    {
+        if !element.is_link() {
+            return false
+        }
+
+        // Non-relevant links are always unvisited.
+        if *self != RelevantLinkStatus::Found {
+            return true
+        }
+
+        context.visited_handling == VisitedHandlingMode::AllLinksUnvisited
+    }
+}
+
 /// A result of selector matching, includes 3 failure types,
 ///
 ///   NotMatchedAndRestartFromClosestLaterSibling
@@ -267,6 +396,7 @@ pub fn matches_complex_selector<E, F>(complex_selector: &ComplexSelector<E::Impl
     match matches_complex_selector_internal(iter,
                                             element,
                                             context,
+                                            RelevantLinkStatus::Looking,
                                             flags_setter) {
         SelectorMatchingResult::Matched => true,
         _ => false
@@ -276,13 +406,16 @@ pub fn matches_complex_selector<E, F>(complex_selector: &ComplexSelector<E::Impl
 fn matches_complex_selector_internal<E, F>(mut selector_iter: SelectorIter<E::Impl>,
                                            element: &E,
                                            context: &mut MatchingContext,
+                                           relevant_link: RelevantLinkStatus,
                                            flags_setter: &mut F)
                                            -> SelectorMatchingResult
      where E: Element,
            F: FnMut(&E, ElementSelectorFlags),
 {
+    let mut relevant_link = relevant_link.examine_potential_link(element, context);
+
     let matches_all_simple_selectors = selector_iter.all(|simple| {
-        matches_simple_selector(simple, element, context, flags_setter)
+        matches_simple_selector(simple, element, context, &relevant_link, flags_setter)
     });
 
     let combinator = selector_iter.next_sequence();
@@ -300,6 +433,9 @@ fn matches_complex_selector_internal<E, F>(mut selector_iter: SelectorIter<E::Im
         Some(c) => {
             let (mut next_element, candidate_not_found) = match c {
                 Combinator::NextSibling | Combinator::LaterSibling => {
+                    // Only ancestor combinators are allowed while looking for
+                    // relevant links, so switch to not looking.
+                    relevant_link = RelevantLinkStatus::NotLooking;
                     (element.prev_sibling_element(),
                      SelectorMatchingResult::NotMatchedAndRestartFromClosestDescendant)
                 }
@@ -321,6 +457,7 @@ fn matches_complex_selector_internal<E, F>(mut selector_iter: SelectorIter<E::Im
                 let result = matches_complex_selector_internal(selector_iter.clone(),
                                                                &element,
                                                                context,
+                                                               relevant_link,
                                                                flags_setter);
                 match (result, c) {
                     // Return the status immediately.
@@ -365,6 +502,7 @@ fn matches_simple_selector<E, F>(
         selector: &Component<E::Impl>,
         element: &E,
         context: &mut MatchingContext,
+        relevant_link: &RelevantLinkStatus,
         flags_setter: &mut F)
         -> bool
     where E: Element,
@@ -465,7 +603,7 @@ fn matches_simple_selector<E, F>(
             )
         }
         Component::NonTSPseudoClass(ref pc) => {
-            element.match_non_ts_pseudo_class(pc, context, flags_setter)
+            element.match_non_ts_pseudo_class(pc, context, relevant_link, flags_setter)
         }
         Component::FirstChild => {
             matches_first_child(element, flags_setter)
@@ -509,7 +647,7 @@ fn matches_simple_selector<E, F>(
             matches_generic_nth_child(element, 0, 1, true, true, flags_setter)
         }
         Component::Negation(ref negated) => {
-            !negated.iter().all(|ss| matches_simple_selector(ss, element, context, flags_setter))
+            !negated.iter().all(|ss| matches_simple_selector(ss, element, context, relevant_link, flags_setter))
         }
     }
 }
diff --git a/components/selectors/tree.rs b/components/selectors/tree.rs
index 276c788d05b..6122f22490f 100644
--- a/components/selectors/tree.rs
+++ b/components/selectors/tree.rs
@@ -2,11 +2,11 @@
  * 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/. */
 
-//! Traits that nodes must implement. Breaks the otherwise-cyclic dependency between layout and
-//! style.
+//! Traits that nodes must implement. Breaks the otherwise-cyclic dependency
+//! between layout and style.
 
 use attr::{AttrSelectorOperation, NamespaceConstraint};
-use matching::{ElementSelectorFlags, MatchingContext};
+use matching::{ElementSelectorFlags, MatchingContext, RelevantLinkStatus};
 use parser::SelectorImpl;
 
 pub trait Element: Sized {
@@ -50,6 +50,7 @@ pub trait Element: Sized {
     fn match_non_ts_pseudo_class<F>(&self,
                                     pc: &<Self::Impl as SelectorImpl>::NonTSPseudoClass,
                                     context: &mut MatchingContext,
+                                    relevant_link: &RelevantLinkStatus,
                                     flags_setter: &mut F) -> bool
         where F: FnMut(&Self, ElementSelectorFlags);
 
@@ -58,6 +59,9 @@ pub trait Element: Sized {
                             context: &mut MatchingContext)
                             -> bool;
 
+    /// Whether this element is a `link`.
+    fn is_link(&self) -> bool;
+
     fn get_id(&self) -> Option<<Self::Impl as SelectorImpl>::Identifier>;
 
     fn has_class(&self, name: &<Self::Impl as SelectorImpl>::ClassName) -> bool;
diff --git a/components/style/animation.rs b/components/style/animation.rs
index 4761fde0f28..8d670964ec8 100644
--- a/components/style/animation.rs
+++ b/components/style/animation.rs
@@ -475,6 +475,8 @@ fn compute_style_for_animation_step(context: &SharedStyleContext,
                 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,
@@ -482,6 +484,7 @@ fn compute_style_for_animation_step(context: &SharedStyleContext,
                                                previous_style,
                                                previous_style,
                                                /* cascade_info = */ None,
+                                               /* visited_style = */ None,
                                                &*context.error_reporter,
                                                font_metrics_provider,
                                                CascadeFlags::empty(),
diff --git a/components/style/data.rs b/components/style/data.rs
index a0d694b9518..90ca649e461 100644
--- a/components/style/data.rs
+++ b/components/style/data.rs
@@ -11,6 +11,7 @@ use properties::longhands::display::computed_value as display;
 use restyle_hints::{HintComputationContext, RestyleReplacements, RestyleHint};
 use rule_tree::StrongRuleNode;
 use selector_parser::{EAGER_PSEUDO_COUNT, PseudoElement, RestyleDamage};
+use selectors::matching::VisitedHandlingMode;
 use shared_lock::{Locked, StylesheetGuards};
 use std::fmt;
 use stylearc::Arc;
@@ -29,6 +30,21 @@ pub struct ComputedStyle {
     /// 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 {
@@ -37,6 +53,8 @@ impl ComputedStyle {
         ComputedStyle {
             rules: rules,
             values: Some(values),
+            visited_rules: None,
+            visited_values: None,
         }
     }
 
@@ -46,6 +64,8 @@ impl ComputedStyle {
         ComputedStyle {
             rules: rules,
             values: None,
+            visited_rules: None,
+            visited_values: None,
         }
     }
 
@@ -55,9 +75,63 @@ impl ComputedStyle {
         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 mutable reference to the visited rule node, if any.
+    pub fn get_visited_rules_mut(&mut self) -> Option<&mut StrongRuleNode> {
+        self.visited_rules.as_mut()
+    }
+
+    /// 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()
     }
 }
 
@@ -106,7 +180,7 @@ impl EagerPseudoStyles {
     }
 
     /// 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(),
@@ -131,15 +205,93 @@ impl EagerPseudoStyles {
         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 pseudo-element was removed.
+    fn remove_unvisited_rules(&mut self, pseudo: &PseudoElement) -> bool {
+        self.take(pseudo).is_some()
+    }
+
+    /// 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.  (Always false, but returns a
+    /// bool for parity with `add_unvisited_rules`.)
+    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. (Always false, but
+    /// returns a bool for parity with `remove_unvisited_rules`.)
+    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)
+            },
+        }
     }
 }
 
diff --git a/components/style/gecko/wrapper.rs b/components/style/gecko/wrapper.rs
index fc56362810c..638efdf8b78 100644
--- a/components/style/gecko/wrapper.rs
+++ b/components/style/gecko/wrapper.rs
@@ -65,7 +65,7 @@ use rule_tree::CascadeLevel as ServoCascadeLevel;
 use selector_parser::ElementExt;
 use selectors::Element;
 use selectors::attr::{AttrSelectorOperation, AttrSelectorOperator, CaseSensitivity, NamespaceConstraint};
-use selectors::matching::{ElementSelectorFlags, MatchingContext, MatchingMode};
+use selectors::matching::{ElementSelectorFlags, MatchingContext, MatchingMode, RelevantLinkStatus};
 use shared_lock::Locked;
 use sink::Push;
 use std::cell::RefCell;
@@ -1236,6 +1236,7 @@ impl<'le> ::selectors::Element for GeckoElement<'le> {
     fn match_non_ts_pseudo_class<F>(&self,
                                     pseudo_class: &NonTSPseudoClass,
                                     context: &mut MatchingContext,
+                                    relevant_link: &RelevantLinkStatus,
                                     flags_setter: &mut F)
                                     -> bool
         where F: FnMut(&Self, ElementSelectorFlags),
@@ -1243,8 +1244,6 @@ impl<'le> ::selectors::Element for GeckoElement<'le> {
         use selectors::matching::*;
         match *pseudo_class {
             NonTSPseudoClass::AnyLink |
-            NonTSPseudoClass::Link |
-            NonTSPseudoClass::Visited |
             NonTSPseudoClass::Active |
             NonTSPseudoClass::Focus |
             NonTSPseudoClass::Hover |
@@ -1293,6 +1292,8 @@ impl<'le> ::selectors::Element for GeckoElement<'le> {
                 // here, to handle `:any-link` correctly.
                 self.get_state().intersects(pseudo_class.state_flag())
             },
+            NonTSPseudoClass::Link => relevant_link.is_unvisited(self, context),
+            NonTSPseudoClass::Visited => relevant_link.is_visited(self, context),
             NonTSPseudoClass::MozFirstNode => {
                 flags_setter(self, HAS_EDGE_CHILD_SELECTOR);
                 let mut elem = self.as_node();
@@ -1369,6 +1370,15 @@ impl<'le> ::selectors::Element for GeckoElement<'le> {
         }
     }
 
+    #[inline]
+    fn is_link(&self) -> bool {
+        let mut context = MatchingContext::new(MatchingMode::Normal, None);
+        self.match_non_ts_pseudo_class(&NonTSPseudoClass::AnyLink,
+                                       &mut context,
+                                       &RelevantLinkStatus::default(),
+                                       &mut |_, _| {})
+    }
+
     fn get_id(&self) -> Option<Atom> {
         if !self.has_id() {
             return None;
@@ -1421,14 +1431,6 @@ impl<'a> NamespaceConstraintHelpers for NamespaceConstraint<&'a Namespace> {
 
 impl<'le> ElementExt for GeckoElement<'le> {
     #[inline]
-    fn is_link(&self) -> bool {
-        let mut context = MatchingContext::new(MatchingMode::Normal, None);
-        self.match_non_ts_pseudo_class(&NonTSPseudoClass::AnyLink,
-                                       &mut context,
-                                       &mut |_, _| {})
-    }
-
-    #[inline]
     fn matches_user_and_author_rules(&self) -> bool {
         self.flags() & (NODE_IS_IN_NATIVE_ANONYMOUS_SUBTREE as u32) == 0
     }
diff --git a/components/style/matching.rs b/components/style/matching.rs
index df5ac723097..5c68946abee 100644
--- a/components/style/matching.rs
+++ b/components/style/matching.rs
@@ -13,15 +13,15 @@ use data::{ComputedStyle, ElementData, RestyleData};
 use dom::{TElement, TNode};
 use font_metrics::FontMetricsProvider;
 use log::LogLevel::Trace;
-use properties::{AnimationRules, CascadeFlags, ComputedValues, SKIP_ROOT_AND_ITEM_BASED_DISPLAY_FIXUP, cascade};
+use properties::{AnimationRules, CascadeFlags, ComputedValues};
+use properties::{SKIP_ROOT_AND_ITEM_BASED_DISPLAY_FIXUP, VISITED_DEPENDENT_ONLY, 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;
@@ -92,15 +92,6 @@ impl From<StyleChange> for ChildCascadeRequirement {
     }
 }
 
-/// 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 {
@@ -125,6 +116,101 @@ impl RulesChanged {
     }
 }
 
+/// 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 a mutable rules node based on the cascade mode, if any.
+    fn get_rules_mut<'a>(&self, style: &'a mut ComputedStyle) -> Option<&'a mut StrongRuleNode> {
+        match *self {
+            CascadeVisitedMode::Unvisited => Some(&mut style.rules),
+            CascadeVisitedMode::Visited => style.get_visited_rules_mut(),
+        }
+    }
+
+    /// 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
+    }
+
+    /// Returns whether animations should be processed based on the cascade
+    /// mode.  At the moment, it appears we don't need to support animating
+    /// visited styles.
+    fn should_process_animations(&self) -> bool {
+        *self == CascadeVisitedMode::Unvisited
+    }
+
+    /// Returns whether we should accumulate restyle damage based on the cascade
+    /// mode.  At the moment, it appears we don't need to do so for visited
+    /// styles.  TODO: Verify this is correct as part of
+    /// https://bugzilla.mozilla.org/show_bug.cgi?id=1364484.
+    fn should_accumulate_damage(&self) -> bool {
+        *self == CascadeVisitedMode::Unvisited
+    }
+
+    /// Returns whether the cascade should filter to only visited dependent
+    /// properties based on the cascade mode.
+    fn visited_dependent_only(&self) -> bool {
+        *self == CascadeVisitedMode::Visited
+    }
+}
+
 trait PrivateMatchMethods: TElement {
     /// Returns the closest parent element that doesn't have a display: contents
     /// style (and thus generates a box).
@@ -158,13 +244,18 @@ trait PrivateMatchMethods: TElement {
                           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)
         }
+        if cascade_visited.visited_dependent_only() {
+            cascade_flags.insert(VISITED_DEPENDENT_ONLY);
+        }
 
         // Grab the inherited values.
         let parent_el;
@@ -173,7 +264,7 @@ trait PrivateMatchMethods: TElement {
             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
@@ -182,14 +273,13 @@ trait PrivateMatchMethods: TElement {
                     // 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))
             }
         };
 
@@ -199,7 +289,7 @@ trait PrivateMatchMethods: TElement {
         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);
@@ -227,6 +317,7 @@ trait PrivateMatchMethods: TElement {
                              &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,
@@ -240,7 +331,8 @@ trait PrivateMatchMethods: TElement {
     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());
@@ -261,13 +353,26 @@ trait PrivateMatchMethods: TElement {
                     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 {
@@ -278,27 +383,43 @@ trait PrivateMatchMethods: TElement {
                                 &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 there was no relevant link, we won't have any visited rules, so
+        // there may not be anything do for the visited case.  This early return
+        // is especially important for the `cascade_primary_and_pseudos` path
+        // since we rely on the state of some previous matching run.
+        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() {
+        if !context.shared.traversal_flags.for_animation_only() &&
+           cascade_visited.should_process_animations() {
             self.process_animations(context,
                                     &mut old_values,
                                     &mut new_values,
@@ -306,43 +427,60 @@ trait PrivateMatchMethods: TElement {
                                     important_rules_changed);
         }
 
-        let child_cascade_requirement =
-            self.accumulate_damage(&context.shared,
-                                   restyle,
-                                   old_values.as_ref().map(|v| v.as_ref()),
-                                   &new_values,
-                                   None);
+        let mut child_cascade_requirement =
+            ChildCascadeRequirement::CanSkipCascade;
+        if cascade_visited.should_accumulate_damage() {
+            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 there was no relevant link, we won't have any visited rules, so
+        // there may not be anything do for the visited case.  This early return
+        // is especially important for the `cascade_primary_and_pseudos` path
+        // since we rely on the state of some previous matching run.
+        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));
+        if cascade_visited.should_accumulate_damage() {
+            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")]
@@ -359,11 +497,15 @@ trait PrivateMatchMethods: TElement {
             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")]
@@ -593,17 +735,49 @@ trait PrivateMatchMethods: TElement {
     }
 }
 
-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 {
@@ -615,27 +789,52 @@ pub trait MatchMethods : TElement {
                          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.
@@ -655,7 +854,7 @@ pub trait MatchMethods : TElement {
                    .style_sharing_candidate_cache
                    .insert_if_possible(self,
                                        data.styles().primary.values(),
-                                       relations,
+                                       primary_results.relations,
                                        revalidation_match_results);
         }
 
@@ -669,22 +868,34 @@ pub trait MatchMethods : TElement {
                                    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 {
             // We don't expect to match against a non-canonical pseudo-element.
@@ -731,10 +942,16 @@ pub trait MatchMethods : TElement {
                     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)
             }
         }
 
@@ -742,6 +959,18 @@ pub trait MatchMethods : TElement {
 
         let stylist = &context.shared.stylist;
         let style_attribute = self.style_attribute();
+
+        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_for_visited(MatchingMode::Normal,
+                                             Some(bloom_filter),
+                                             visited_handling);
+
         {
             let smil_override = data.get_smil_override();
             let animation_rules = if self.may_have_animations() {
@@ -749,15 +978,6 @@ pub trait MatchMethods : TElement {
             } else {
                 AnimationRules(None, None)
             };
-            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 mut matching_context =
-                MatchingContext::new(MatchingMode::Normal, Some(bloom));
 
             // Compute the primary rule node.
             stylist.push_applicable_declarations(self,
@@ -768,14 +988,12 @@ pub trait MatchMethods : TElement {
                                                  &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:");
@@ -794,25 +1012,32 @@ pub trait MatchMethods : TElement {
                 &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();
@@ -826,18 +1051,23 @@ pub trait MatchMethods : TElement {
         // 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 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.
@@ -850,32 +1080,32 @@ pub trait MatchMethods : TElement {
                                                  &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
@@ -974,17 +1204,40 @@ pub trait MatchMethods : TElement {
     }
 
     /// Updates the rule nodes without re-running selector matching, using just
-    /// the rule tree. Returns true if an !important rule was replaced.
+    /// the rule tree.
+    ///
+    /// Returns true if an !important rule was replaced.
     fn replace_rules(&self,
                      replacements: RestyleReplacements,
                      context: &StyleContext<Self>,
                      data: &mut ElementData)
                      -> bool {
+        let mut result = false;
+        result |= self.replace_rules_internal(replacements, context, data,
+                                              CascadeVisitedMode::Unvisited);
+        result |= self.replace_rules_internal(replacements, context, data,
+                                              CascadeVisitedMode::Visited);
+        result
+    }
+
+    /// Updates the rule nodes without re-running selector matching, using just
+    /// the rule tree, for a specific visited mode.
+    ///
+    /// Returns true if an !important rule was replaced.
+    fn replace_rules_internal(&self,
+                              replacements: RestyleReplacements,
+                              context: &StyleContext<Self>,
+                              data: &mut ElementData,
+                              cascade_visited: CascadeVisitedMode)
+                              -> bool {
         use properties::PropertyDeclarationBlock;
         use shared_lock::Locked;
 
         let element_styles = &mut data.styles_mut();
-        let primary_rules = &mut element_styles.primary.rules;
+        let primary_rules = match cascade_visited.get_rules_mut(&mut element_styles.primary) {
+            Some(r) => r,
+            None => return false,
+        };
 
         let replace_rule_node = |level: CascadeLevel,
                                  pdb: Option<&Arc<Locked<PropertyDeclarationBlock>>>,
@@ -1126,8 +1379,11 @@ pub trait MatchMethods : TElement {
     /// 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
@@ -1135,7 +1391,7 @@ pub trait MatchMethods : TElement {
         // 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);
         }
     }
 
@@ -1156,11 +1412,15 @@ pub trait MatchMethods : TElement {
             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)
     }
 
 }
diff --git a/components/style/properties/gecko.mako.rs b/components/style/properties/gecko.mako.rs
index d5f96ad1bb1..fd4975826d7 100644
--- a/components/style/properties/gecko.mako.rs
+++ b/components/style/properties/gecko.mako.rs
@@ -100,6 +100,11 @@ pub struct ComputedValues {
     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 {
@@ -107,6 +112,7 @@ impl ComputedValues {
                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
@@ -117,6 +123,7 @@ impl ComputedValues {
             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
@@ -130,6 +137,7 @@ impl ComputedValues {
             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
@@ -168,6 +176,23 @@ impl ComputedValues {
     }
     % 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()
     }
diff --git a/components/style/properties/properties.mako.rs b/components/style/properties/properties.mako.rs
index d61f4205773..92429d554dd 100644
--- a/components/style/properties/properties.mako.rs
+++ b/components/style/properties/properties.mako.rs
@@ -576,6 +576,57 @@ impl LonghandId {
             % endfor
         }
     }
+
+    /// 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.
+    fn is_visited_dependent(&self) -> bool {
+        matches!(*self,
+            % if product == "gecko":
+            LonghandId::ColumnRuleColor |
+            LonghandId::TextEmphasisColor |
+            LonghandId::WebkitTextFillColor |
+            LonghandId::WebkitTextStrokeColor |
+            LonghandId::TextDecorationColor |
+            LonghandId::Fill |
+            LonghandId::Stroke |
+            LonghandId::CaretColor |
+            % endif
+            LonghandId::Color |
+            LonghandId::BackgroundColor |
+            LonghandId::BorderTopColor |
+            LonghandId::BorderRightColor |
+            LonghandId::BorderBottomColor |
+            LonghandId::BorderLeftColor |
+            LonghandId::OutlineColor
+        )
+    }
+
+    /// The computed value of some properties depends on the (sometimes
+    /// computed) value of *other* properties.
+    ///
+    /// So we classify properties into "early" and "other", such that the only
+    /// dependencies can be from "other" to "early".
+    ///
+    /// Unfortunately, it’s not easy to check that this classification is
+    /// correct.
+    fn is_early_property(&self) -> bool {
+        matches!(*self,
+            % if product == 'gecko':
+            LonghandId::TextOrientation |
+            LonghandId::AnimationName |
+            LonghandId::TransitionProperty |
+            LonghandId::XLang |
+            LonghandId::MozScriptLevel |
+            % endif
+            LonghandId::FontSize |
+            LonghandId::FontFamily |
+            LonghandId::Color |
+            LonghandId::TextDecorationLine |
+            LonghandId::WritingMode |
+            LonghandId::Direction
+        )
+    }
 }
 
 /// An identifier for a given shorthand property.
@@ -1743,6 +1794,11 @@ pub struct ComputedValues {
     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")]
@@ -1752,6 +1808,7 @@ impl ComputedValues {
                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
@@ -1761,6 +1818,7 @@ impl ComputedValues {
             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
@@ -1796,6 +1854,23 @@ impl ComputedValues {
         }
     % 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
@@ -2183,6 +2258,10 @@ pub struct StyleBuilder<'a> {
     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
@@ -2195,6 +2274,7 @@ impl<'a> StyleBuilder<'a> {
         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
@@ -2204,6 +2284,7 @@ impl<'a> StyleBuilder<'a> {
             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
@@ -2223,6 +2304,7 @@ impl<'a> StyleBuilder<'a> {
                   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(),
@@ -2296,6 +2378,7 @@ impl<'a> StyleBuilder<'a> {
                             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
@@ -2339,6 +2422,7 @@ mod lazy_static_module {
             writing_mode: WritingMode::empty(),
             root_font_size: longhands::font_size::get_initial_value(),
             font_size_keyword: Some((Default::default(), 1.)),
+            visited_style: None,
         };
     }
 }
@@ -2370,6 +2454,8 @@ bitflags! {
         /// Whether to skip any root element and flex/grid item display style
         /// fixup.
         const SKIP_ROOT_AND_ITEM_BASED_DISPLAY_FIXUP = 0x02,
+        /// Whether to only cascade properties that are visited dependent.
+        const VISITED_DEPENDENT_ONLY = 0x04,
     }
 }
 
@@ -2392,6 +2478,7 @@ pub fn cascade(device: &Device,
                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,
@@ -2438,6 +2525,7 @@ pub fn cascade(device: &Device,
                        iter_declarations,
                        inherited_style,
                        layout_parent_style,
+                       visited_style,
                        cascade_info,
                        error_reporter,
                        font_metrics_provider,
@@ -2453,6 +2541,7 @@ pub fn apply_declarations<'a, F, I>(device: &Device,
                                     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,
@@ -2483,6 +2572,7 @@ pub fn apply_declarations<'a, F, I>(device: &Device,
                           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(),
@@ -2496,6 +2586,7 @@ pub fn apply_declarations<'a, F, I>(device: &Device,
                           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
@@ -2544,6 +2635,14 @@ pub fn apply_declarations<'a, F, I>(device: &Device,
                 PropertyDeclarationId::Custom(..) => continue,
             };
 
+            // 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
+            }
+
             // The computed value of some properties depends on the
             // (sometimes computed) value of *other* properties.
             //
@@ -2555,26 +2654,11 @@ pub fn apply_declarations<'a, F, I>(device: &Device,
             //
             // Unfortunately, it’s not easy to check that this
             // classification is correct.
-            let is_early_property = matches!(longhand_id,
-                LonghandId::FontSize |
-                LonghandId::FontFamily |
-                LonghandId::Color |
-                LonghandId::TextDecorationLine |
-                LonghandId::WritingMode |
-                LonghandId::Direction
-                % if product == 'gecko':
-                    | LonghandId::TextOrientation
-                    | LonghandId::AnimationName
-                    | LonghandId::TransitionProperty
-                    | LonghandId::XLang
-                    | LonghandId::MozScriptLevel
-                % endif
-            );
             if
                 % if category_to_cascade_now == "early":
                     !
                 % endif
-                is_early_property
+                longhand_id.is_early_property()
             {
                 continue
             }
diff --git a/components/style/restyle_hints.rs b/components/style/restyle_hints.rs
index 2d5d9aed27c..57c9f13c672 100644
--- a/components/style/restyle_hints.rs
+++ b/components/style/restyle_hints.rs
@@ -21,7 +21,7 @@ use selector_parser::{NonTSPseudoClass, PseudoElement, SelectorImpl, Snapshot, S
 use selectors::Element;
 use selectors::attr::{AttrSelectorOperation, NamespaceConstraint};
 use selectors::matching::{ElementSelectorFlags, MatchingContext, MatchingMode};
-use selectors::matching::matches_selector;
+use selectors::matching::{RelevantLinkStatus, VisitedHandlingMode, matches_selector};
 use selectors::parser::{Combinator, Component, Selector, SelectorInner, SelectorMethods};
 use selectors::visitor::SelectorVisitor;
 use smallvec::SmallVec;
@@ -535,6 +535,7 @@ impl<'a, E> Element for ElementWrapper<'a, E>
     fn match_non_ts_pseudo_class<F>(&self,
                                     pseudo_class: &NonTSPseudoClass,
                                     context: &mut MatchingContext,
+                                    relevant_link: &RelevantLinkStatus,
                                     _setter: &mut F)
                                     -> bool
         where F: FnMut(&Self, ElementSelectorFlags),
@@ -576,10 +577,21 @@ impl<'a, E> Element for ElementWrapper<'a, E>
             }
         }
 
+        // For :link and :visited, we don't actually want to test the element
+        // state directly.  Instead, we use the `relevant_link` to determine if
+        // they match.
+        if *pseudo_class == NonTSPseudoClass::Link {
+            return relevant_link.is_unvisited(self, context)
+        }
+        if *pseudo_class == NonTSPseudoClass::Visited {
+            return relevant_link.is_visited(self, context)
+        }
+
         let flag = pseudo_class.state_flag();
         if flag.is_empty() {
             return self.element.match_non_ts_pseudo_class(pseudo_class,
                                                           context,
+                                                          relevant_link,
                                                           &mut |_, _| {})
         }
         match self.snapshot().and_then(|s| s.state()) {
@@ -587,6 +599,7 @@ impl<'a, E> Element for ElementWrapper<'a, E>
             None => {
                 self.element.match_non_ts_pseudo_class(pseudo_class,
                                                        context,
+                                                       relevant_link,
                                                        &mut |_, _| {})
             }
         }
@@ -600,6 +613,14 @@ impl<'a, E> Element for ElementWrapper<'a, E>
         self.element.match_pseudo_element(pseudo_element, context)
     }
 
+    fn is_link(&self) -> bool {
+        let mut context = MatchingContext::new(MatchingMode::Normal, None);
+        self.match_non_ts_pseudo_class(&NonTSPseudoClass::AnyLink,
+                                       &mut context,
+                                       &RelevantLinkStatus::default(),
+                                       &mut |_, _| {})
+    }
+
     fn parent_element(&self) -> Option<Self> {
         self.element.parent_element()
             .map(|e| ElementWrapper::new(e, self.snapshot_map))
@@ -940,6 +961,17 @@ impl DependencySet {
 
         let mut hint = RestyleHint::empty();
 
+        // If we are sensitive to visitedness and the visited state changed, we
+        // force a restyle here. Matching doesn't depend on the actual visited
+        // state at all, so we can't look at matching results to decide what to
+        // do for this case.
+        if state_changes.intersects(IN_VISITED_OR_UNVISITED_STATE) {
+            trace!(" > visitedness change, force subtree restyle");
+            // We can't just return here because there may also be attribute
+            // changes as well that imply additional hints.
+            hint = RestyleHint::subtree();
+        }
+
         // Compute whether the snapshot has any different id or class attributes
         // from the element. If it does, we need to pass those to the lookup, so
         // that we get all the possible applicable selectors from the rulehash.
@@ -969,21 +1001,6 @@ impl DependencySet {
             }
         };
 
-        let mut element_matching_context =
-            MatchingContext::new(MatchingMode::Normal, bloom_filter);
-
-        // NOTE(emilio): We can't use the bloom filter for snapshots, given that
-        // arbitrary elements in the parent chain may have mutated their
-        // id's/classes, which means that they won't be in the filter, and as
-        // such we may fast-reject selectors incorrectly.
-        //
-        // We may be able to improve this if we record as we go down the tree
-        // whether any parent had a snapshot, and whether those snapshots were
-        // taken due to an element class/id change, but it's not clear we _need_
-        // it right now.
-        let mut snapshot_matching_context =
-            MatchingContext::new(MatchingMode::Normal, None);
-
         let lookup_element = if el.implemented_pseudo_element().is_some() {
             el.closest_non_native_anonymous_ancestor().unwrap()
         } else {
@@ -993,6 +1010,7 @@ impl DependencySet {
         self.dependencies
             .lookup_with_additional(lookup_element, additional_id, &additional_classes, &mut |dep| {
             trace!("scanning dependency: {:?}", dep);
+
             if !dep.sensitivities.sensitive_to(attrs_changed,
                                                state_changes) {
                 trace!(" > non-sensitive");
@@ -1004,19 +1022,63 @@ impl DependencySet {
                 return true;
             }
 
-            // We can ignore the selector flags, since they would have already
-            // been set during original matching for any element that might
-            // change its matching behavior here.
+            // NOTE(emilio): We can't use the bloom filter for snapshots, given
+            // that arbitrary elements in the parent chain may have mutated
+            // their id's/classes, which means that they won't be in the
+            // filter, and as such we may fast-reject selectors incorrectly.
+            //
+            // We may be able to improve this if we record as we go down the
+            // tree whether any parent had a snapshot, and whether those
+            // snapshots were taken due to an element class/id change, but it's
+            // not clear we _need_ it right now.
+            let mut then_context =
+                MatchingContext::new_for_visited(MatchingMode::Normal, None,
+                                                 VisitedHandlingMode::AllLinksUnvisited);
             let matched_then =
                 matches_selector(&dep.selector, &snapshot_el,
-                                 &mut snapshot_matching_context,
+                                 &mut then_context,
                                  &mut |_, _| {});
+            let mut now_context =
+                MatchingContext::new_for_visited(MatchingMode::Normal, bloom_filter,
+                                                 VisitedHandlingMode::AllLinksUnvisited);
             let matches_now =
                 matches_selector(&dep.selector, el,
-                                 &mut element_matching_context,
+                                 &mut now_context,
                                  &mut |_, _| {});
-            if matched_then != matches_now {
+
+            // Check for mismatches in both the match result and also the status
+            // of whether a relevant link was found.
+            if matched_then != matches_now ||
+               then_context.relevant_link_found != now_context.relevant_link_found {
                 hint.insert_from(&dep.hint);
+                return !hint.is_maximum()
+            }
+
+            // If there is a relevant link, then we also matched in visited
+            // mode.  Match again in this mode to ensure this also matches.
+            // Note that we never actually match directly against the element's
+            // true visited state at all, since that would expose us to timing
+            // attacks.  The matching process only considers the relevant link
+            // state and visited handling mode when deciding if visited
+            // matches.  Instead, we are rematching here in case there is some
+            // :visited selector whose matching result changed for some _other_
+            // element state or attribute.
+            if now_context.relevant_link_found &&
+               dep.sensitivities.states.intersects(IN_VISITED_OR_UNVISITED_STATE) {
+                then_context.visited_handling = VisitedHandlingMode::RelevantLinkVisited;
+                let matched_then =
+                    matches_selector(&dep.selector, &snapshot_el,
+                                     &mut then_context,
+                                     &mut |_, _| {});
+                now_context.visited_handling = VisitedHandlingMode::RelevantLinkVisited;
+                let matches_now =
+                    matches_selector(&dep.selector, el,
+                                     &mut now_context,
+                                     &mut |_, _| {});
+                if matched_then != matches_now {
+                    hint.insert_from(&dep.hint);
+                    return !hint.is_maximum()
+                }
             }
 
             !hint.is_maximum()
diff --git a/components/style/rule_tree/mod.rs b/components/style/rule_tree/mod.rs
index 866eb9adab9..bb13836c2a6 100644
--- a/components/style/rule_tree/mod.rs
+++ b/components/style/rule_tree/mod.rs
@@ -16,6 +16,7 @@ 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
@@ -215,6 +216,18 @@ impl RuleTree {
         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
@@ -632,6 +645,8 @@ struct WeakRuleNode {
 /// 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,
 }
 
diff --git a/components/style/selector_parser.rs b/components/style/selector_parser.rs
index 9e4e5deeaeb..e1a7a0aecda 100644
--- a/components/style/selector_parser.rs
+++ b/components/style/selector_parser.rs
@@ -103,9 +103,6 @@ pub enum PseudoElementCascadeType {
 
 /// An extension to rust-selector's `Element` trait.
 pub trait ElementExt: Element<Impl=SelectorImpl> + Debug {
-    /// Whether this element is a `link`.
-    fn is_link(&self) -> bool;
-
     /// Whether this element should match user and author rules.
     ///
     /// We use this for Native Anonymous Content in Gecko.
diff --git a/components/style/servo/selector_parser.rs b/components/style/servo/selector_parser.rs
index 1cae314ddec..34cec12b83f 100644
--- a/components/style/servo/selector_parser.rs
+++ b/components/style/servo/selector_parser.rs
@@ -16,7 +16,6 @@ use restyle_hints::ElementSnapshot;
 use selector_parser::{ElementExt, PseudoElementCascadeType, SelectorParser};
 use selectors::Element;
 use selectors::attr::{AttrSelectorOperation, NamespaceConstraint};
-use selectors::matching::{MatchingContext, MatchingMode};
 use selectors::parser::SelectorMethods;
 use selectors::visitor::SelectorVisitor;
 use std::borrow::Cow;
@@ -601,13 +600,6 @@ impl ServoElementSnapshot {
 }
 
 impl<E: Element<Impl=SelectorImpl> + Debug> ElementExt for E {
-    fn is_link(&self) -> bool {
-        let mut context = MatchingContext::new(MatchingMode::Normal, None);
-        self.match_non_ts_pseudo_class(&NonTSPseudoClass::AnyLink,
-                                       &mut context,
-                                       &mut |_, _| {})
-    }
-
     #[inline]
     fn matches_user_and_author_rules(&self) -> bool {
         true
diff --git a/components/style/sharing/checks.rs b/components/style/sharing/checks.rs
index 5cc5869e509..4ac537e0009 100644
--- a/components/style/sharing/checks.rs
+++ b/components/style/sharing/checks.rs
@@ -8,6 +8,7 @@
 
 use context::{CurrentElementInfo, SelectorFlagsMap, SharedStyleContext};
 use dom::TElement;
+use element_state::*;
 use matching::MatchMethods;
 use selectors::bloom::BloomFilter;
 use selectors::matching::{ElementSelectorFlags, StyleRelations};
@@ -80,6 +81,20 @@ pub fn have_same_class<E>(element: E,
     element_class_attributes == *candidate.class_attributes.as_ref().unwrap()
 }
 
+/// Compare element and candidate state, but ignore visitedness.  Styles don't
+/// actually changed based on visitedness (since both possibilities are computed
+/// up front), so it's safe to share styles if visitedness differs.
+pub fn have_same_state_ignoring_visitedness<E>(element: E,
+                                               candidate: &StyleSharingCandidate<E>)
+                                               -> bool
+    where E: TElement,
+{
+    let state_mask = !IN_VISITED_OR_UNVISITED_STATE;
+    let state = element.get_state() & state_mask;
+    let candidate_state = candidate.element.get_state() & state_mask;
+    state == candidate_state
+}
+
 /// Whether a given element and a candidate match the same set of "revalidation"
 /// selectors.
 ///
diff --git a/components/style/sharing/mod.rs b/components/style/sharing/mod.rs
index 744571ca863..67fde2e047b 100644
--- a/components/style/sharing/mod.rs
+++ b/components/style/sharing/mod.rs
@@ -349,7 +349,7 @@ impl<E: TElement> StyleSharingCandidateCache<E> {
             miss!(UserAndAuthorRules)
         }
 
-        if element.get_state() != candidate.element.get_state() {
+        if !checks::have_same_state_ignoring_visitedness(element, candidate) {
             miss!(State)
         }
 
diff --git a/components/style/stylist.rs b/components/style/stylist.rs
index a453588c469..4b80faaf459 100644
--- a/components/style/stylist.rs
+++ b/components/style/stylist.rs
@@ -568,6 +568,7 @@ impl Stylist {
                                 parent.map(|p| &**p),
                                 parent.map(|p| &**p),
                                 None,
+                                None,
                                 &RustLogReporter,
                                 font_metrics,
                                 cascade_flags,
@@ -639,6 +640,7 @@ impl Stylist {
         // 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,
@@ -646,6 +648,7 @@ impl Stylist {
                                 Some(parent_style),
                                 Some(parent_style),
                                 None,
+                                None,
                                 &RustLogReporter,
                                 font_metrics,
                                 CascadeFlags::empty(),
@@ -695,6 +698,7 @@ impl Stylist {
             }
         };
 
+        // 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);
@@ -1048,6 +1052,9 @@ impl Stylist {
         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,
@@ -1055,6 +1062,7 @@ impl Stylist {
                                      Some(parent_style),
                                      Some(parent_style),
                                      None,
+                                     None,
                                      &RustLogReporter,
                                      &metrics,
                                      CascadeFlags::empty(),