--- a/servo/components/script/dom/element.rs
+++ b/servo/components/script/dom/element.rs
@@ -82,17 +82,18 @@ use html5ever::serialize::SerializeOpts;
 use html5ever::serialize::TraversalScope;
 use html5ever::serialize::TraversalScope::{ChildrenOnly, IncludeNode};
 use js::jsapi::{HandleValue, JSAutoCompartment};
 use net_traits::request::CorsSettings;
 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::{RelevantLinkStatus, matches_selector_list};
 use selectors::matching::{HAS_EDGE_CHILD_SELECTOR, HAS_SLOW_SELECTOR, HAS_SLOW_SELECTOR_LATER_SIBLINGS};
 use servo_atoms::Atom;
 use std::ascii::AsciiExt;
 use std::borrow::Cow;
 use std::cell::{Cell, Ref};
 use std::convert::TryFrom;
 use std::default::Default;
 use std::fmt;
@@ -2424,16 +2425,17 @@ impl<'a> ::selectors::Element for Root<E
 
     fn get_namespace(&self) -> &Namespace {
         self.namespace()
     }
 
     fn match_non_ts_pseudo_class<F>(&self,
                                     pseudo_class: &NonTSPseudoClass,
                                     _: &mut MatchingContext,
+                                    _: &RelevantLinkStatus,
                                     _: &mut F)
                                     -> bool
         where F: FnMut(&Self, ElementSelectorFlags),
     {
         match *pseudo_class {
             // https://github.com/servo/servo/issues/8718
             NonTSPseudoClass::Link |
             NonTSPseudoClass::AnyLink => self.is_link(),
@@ -2473,16 +2475,30 @@ impl<'a> ::selectors::Element for Root<E
             NonTSPseudoClass::Indeterminate |
             NonTSPseudoClass::ReadWrite |
             NonTSPseudoClass::PlaceholderShown |
             NonTSPseudoClass::Target =>
                 Element::state(self).contains(pseudo_class.state_flag()),
         }
     }
 
+    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()
     }
 
     fn has_class(&self, name: &Atom) -> bool {
         Element::has_class(&**self, name)
     }
 
@@ -2587,30 +2603,16 @@ impl Element {
                         }
                     }
                 }
                 None
             }
         }
     }
 
-    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
     ///
     /// Use an element's synthetic click activation (or handle_event) for any script-triggered clicks.
     /// If the spec says otherwise, check with Manishearth first
     pub fn authentic_click_activation(&self, event: &Event) {
         // Not explicitly part of the spec, however this helps enforce the invariants

--- a/servo/components/script/layout_wrapper.rs
+++ b/servo/components/script/layout_wrapper.rs
@@ -46,17 +46,17 @@ use gfx_traits::ByteIndex;
 use html5ever::{LocalName, Namespace};
 use msg::constellation_msg::{BrowsingContextId, PipelineId};
 use range::Range;
 use script_layout_interface::{HTMLCanvasData, LayoutNodeType, SVGSVGData, TrustedNodeAddress};
 use script_layout_interface::{OpaqueStyleAndLayoutData, PartialPersistentLayoutData};
 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;
 use std::fmt::Debug;
 use std::hash::{Hash, Hasher};
 use std::marker::PhantomData;
 use std::mem::transmute;
 use std::sync::atomic::Ordering;
@@ -675,33 +675,25 @@ impl<'le> ::selectors::Element for Servo
                             -> bool
     {
         false
     }
 
     fn match_non_ts_pseudo_class<F>(&self,
                                     pseudo_class: &NonTSPseudoClass,
                                     _: &mut MatchingContext,
+                                    _: &RelevantLinkStatus,
                                     _: &mut F)
                                     -> bool
         where F: FnMut(&Self, ElementSelectorFlags),
     {
         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
             //                https://tools.ietf.org/html/rfc4647#section-3.3.2
             NonTSPseudoClass::Lang(ref lang) => extended_filtering(&*self.element.get_lang_for_layout(), &*lang),
 
             NonTSPseudoClass::ServoNonZeroBorder => unsafe {
                 match (*self.element.unsafe_get()).get_attr_for_layout(&ns!(), &local_name!("border")) {
@@ -727,16 +719,30 @@ impl<'le> ::selectors::Element for Servo
             NonTSPseudoClass::ReadWrite |
             NonTSPseudoClass::PlaceholderShown |
             NonTSPseudoClass::Target =>
                 self.element.get_state_for_layout().contains(pseudo_class.state_flag())
         }
     }
 
     #[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()
         }
     }
 
     #[inline]
     fn has_class(&self, name: &Atom) -> bool {
@@ -1180,25 +1186,31 @@ impl<'le> ::selectors::Element for Servo
                 values.iter().any(|v| v.eval_selector(operation))
             }
         }
     }
 
     fn match_non_ts_pseudo_class<F>(&self,
                                     _: &NonTSPseudoClass,
                                     _: &mut MatchingContext,
+                                    _: &RelevantLinkStatus,
                                     _: &mut F)
                                     -> bool
         where F: FnMut(&Self, ElementSelectorFlags),
     {
         // NB: This could maybe be implemented
         warn!("ServoThreadSafeLayoutElement::match_non_ts_pseudo_class called");
         false
     }
 
+    fn is_link(&self) -> bool {
+        warn!("ServoThreadSafeLayoutElement::is_link called");
+        false
+    }
+
     fn get_id(&self) -> Option<Atom> {
         debug!("ServoThreadSafeLayoutElement::get_id called");
         None
     }
 
     fn has_class(&self, _name: &Atom) -> bool {
         debug!("ServoThreadSafeLayoutElement::has_class called");
         false

--- a/servo/components/selectors/matching.rs
+++ b/servo/components/selectors/matching.rs
@@ -89,40 +89,59 @@ pub enum MatchingMode {
     /// For example, in presence of `::before:hover`, it would never match, but
     /// `::before` would be ignored as in "matching".
     ///
     /// It's required for all the selectors you match using this mode to have a
     /// pseudo-element.
     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.
 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.
     pub matching_mode: MatchingMode,
     /// The bloom filter used to fast-reject selectors.
     pub bloom_filter: Option<&'a BloomFilter>,
+    /// Input that controls how matching for links is handled.
+    pub visited_handling: VisitedHandlingMode,
+    /// Output that records whether we encountered a "relevant link" while
+    /// matching _any_ selector for this element. (This differs from
+    /// `RelevantLinkStatus` which tracks the status for the _current_ selector
+    /// only.)
+    relevant_link_found: bool,
 }
 
 impl<'a> MatchingContext<'a> {
     /// Constructs a new `MatchingContext`.
     pub fn new(matching_mode: MatchingMode,
                bloom_filter: Option<&'a BloomFilter>)
                -> Self
     {
         Self {
             relations: StyleRelations::empty(),
             matching_mode: matching_mode,
             bloom_filter: bloom_filter,
+            visited_handling: VisitedHandlingMode::AllLinksUnvisited,
+            relevant_link_found: false,
         }
     }
 }
 
 pub fn matches_selector_list<E>(selector_list: &[Selector<E::Impl>],
                                 element: &E,
                                 context: &mut MatchingContext)
                                 -> bool
@@ -151,16 +170,110 @@ fn may_match<E>(sel: &SelectorInner<E::I
         if !bf.might_contain_hash(*hash) {
             return false;
         }
     }
 
     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
 ///   NotMatchedAndRestartFromClosestDescendant
 ///   NotMatchedGlobally
 ///
 /// When NotMatchedGlobally appears, stop selector matching completely since
 /// the succeeding selectors never matches.
@@ -262,32 +375,36 @@ pub fn matches_complex_selector<E, F>(co
             }
             _ => panic!("Used MatchingMode::ForStatelessPseudoElement in a non-pseudo selector"),
         }
     }
 
     match matches_complex_selector_internal(iter,
                                             element,
                                             context,
+                                            RelevantLinkStatus::Looking,
                                             flags_setter) {
         SelectorMatchingResult::Matched => true,
         _ => false
     }
 }
 
 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();
     let siblings = combinator.map_or(false, |c| c.is_sibling());
     if siblings {
         flags_setter(element, HAS_SLOW_SELECTOR_LATER_SIBLINGS);
     }
 
@@ -295,16 +412,19 @@ fn matches_complex_selector_internal<E, 
         return SelectorMatchingResult::NotMatchedAndRestartFromClosestLaterSibling;
     }
 
     match combinator {
         None => SelectorMatchingResult::Matched,
         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)
                 }
                 Combinator::Child | Combinator::Descendant => {
                     (element.parent_element(),
                      SelectorMatchingResult::NotMatchedGlobally)
                 }
                 Combinator::PseudoElement => {
@@ -316,16 +436,17 @@ fn matches_complex_selector_internal<E, 
             loop {
                 let element = match next_element {
                     None => return candidate_not_found,
                     Some(next_element) => next_element,
                 };
                 let result = matches_complex_selector_internal(selector_iter.clone(),
                                                                &element,
                                                                context,
+                                                               relevant_link,
                                                                flags_setter);
                 match (result, c) {
                     // Return the status immediately.
                     (SelectorMatchingResult::Matched, _) => return result,
                     (SelectorMatchingResult::NotMatchedGlobally, _) => return result,
 
                     // Upgrade the failure status to
                     // NotMatchedAndRestartFromClosestDescendant.
@@ -360,16 +481,17 @@ fn matches_complex_selector_internal<E, 
 }
 
 /// Determines whether the given element matches the given single selector.
 #[inline]
 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,
           F: FnMut(&E, ElementSelectorFlags),
 {
     macro_rules! relation_if {
         ($ex:expr, $flag:ident) => {
             if $ex {
@@ -460,17 +582,17 @@ fn matches_simple_selector<E, F>(
                             case_sensitivity: case_sensitivity.to_unconditional(is_html),
                             expected_value: expected_value,
                         }
                     }
                 }
             )
         }
         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)
         }
         Component::LastChild => {
             matches_last_child(element, flags_setter)
         }
         Component::OnlyChild => {
@@ -504,17 +626,17 @@ fn matches_simple_selector<E, F>(
         Component::LastOfType => {
             matches_generic_nth_child(element, 0, 1, true, true, flags_setter)
         }
         Component::OnlyOfType => {
             matches_generic_nth_child(element, 0, 1, true, false, flags_setter) &&
             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))
         }
     }
 }
 
 fn select_name<'a, T>(is_html: bool, local_name: &'a T, local_name_lower: &'a T) -> &'a T {
     if is_html {
         local_name_lower
     } else {

--- a/servo/components/selectors/tree.rs
+++ b/servo/components/selectors/tree.rs
@@ -1,17 +1,17 @@
 /* This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
-//! 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 {
     type Impl: SelectorImpl;
 
     fn parent_element(&self) -> Option<Self>;
 
     /// The parent of a given pseudo-element, after matching a pseudo-element
@@ -45,24 +45,28 @@ pub trait Element: Sized {
                     ns: &NamespaceConstraint<&<Self::Impl as SelectorImpl>::NamespaceUrl>,
                     local_name: &<Self::Impl as SelectorImpl>::LocalName,
                     operation: &AttrSelectorOperation<&<Self::Impl as SelectorImpl>::AttrValue>)
                     -> bool;
 
     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);
 
     fn match_pseudo_element(&self,
                             pe: &<Self::Impl as SelectorImpl>::PseudoElement,
                             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;
 
     /// Returns whether this element matches `:empty`.
     ///
     /// That is, whether it does not contain any child element or any non-zero-length text node.
     /// See http://dev.w3.org/csswg/selectors-3/#empty-pseudo

--- a/servo/components/style/gecko/wrapper.rs
+++ b/servo/components/style/gecko/wrapper.rs
@@ -60,17 +60,17 @@ use media_queries::Device;
 use properties::{ComputedValues, parse_style_attribute};
 use properties::{Importance, PropertyDeclaration, PropertyDeclarationBlock};
 use properties::animated_properties::{AnimationValue, AnimationValueMap, TransitionProperty};
 use properties::style_structs::Font;
 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;
 use std::collections::HashMap;
 use std::fmt;
 use std::hash::{Hash, Hasher};
 use std::ptr;
 use string_cache::{Atom, Namespace, WeakAtom, WeakNamespace};
@@ -1236,25 +1236,24 @@ impl<'le> ::selectors::Element for Gecko
         unsafe {
             WeakNamespace::new(Gecko_Namespace(self.0))
         }
     }
 
     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),
     {
         use selectors::matching::*;
         match *pseudo_class {
             NonTSPseudoClass::AnyLink |
-            NonTSPseudoClass::Link |
-            NonTSPseudoClass::Visited |
             NonTSPseudoClass::Active |
             NonTSPseudoClass::Focus |
             NonTSPseudoClass::Hover |
             NonTSPseudoClass::Enabled |
             NonTSPseudoClass::Disabled |
             NonTSPseudoClass::Checked |
             NonTSPseudoClass::Fullscreen |
             NonTSPseudoClass::Indeterminate |
@@ -1293,16 +1292,18 @@ impl<'le> ::selectors::Element for Gecko
             NonTSPseudoClass::MozMeterSubOptimum |
             NonTSPseudoClass::MozMeterSubSubOptimum |
             NonTSPseudoClass::MozAutofill |
             NonTSPseudoClass::MozAutofillPreview => {
                 // NB: It's important to use `intersect` instead of `contains`
                 // 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();
                 while let Some(prev) = elem.prev_sibling() {
                     if prev.contains_non_whitespace_content() {
                         return false
                     }
                     elem = prev;
@@ -1368,16 +1369,25 @@ impl<'le> ::selectors::Element for Gecko
         // match the proper pseudo-element, given how we rulehash the stuff
         // based on the pseudo.
         match self.implemented_pseudo_element() {
             Some(ref pseudo) => pseudo == pseudo_element,
             None => false,
         }
     }
 
+    #[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;
         }
 
         let ptr = unsafe {
             bindings::Gecko_AtomAttrValue(self.0,
                                           atom!("id").as_ptr())
@@ -1420,20 +1430,12 @@ impl<'a> NamespaceConstraintHelpers for 
             NamespaceConstraint::Any => ptr::null_mut(),
             NamespaceConstraint::Specific(ref ns) => ns.0.as_ptr(),
         }
     }
 }
 
 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
     }
 }

--- a/servo/components/style/restyle_hints.rs
+++ b/servo/components/style/restyle_hints.rs
@@ -14,17 +14,17 @@ use dom::TElement;
 use element_state::*;
 #[cfg(feature = "gecko")]
 use gecko_bindings::structs::nsRestyleHint;
 #[cfg(feature = "servo")]
 use heapsize::HeapSizeOf;
 use selector_parser::{NonTSPseudoClass, PseudoElement, SelectorImpl, Snapshot, SnapshotMap, AttrValue};
 use selectors::Element;
 use selectors::attr::{AttrSelectorOperation, NamespaceConstraint};
-use selectors::matching::{ElementSelectorFlags, MatchingContext, MatchingMode};
+use selectors::matching::{ElementSelectorFlags, MatchingContext, MatchingMode, RelevantLinkStatus};
 use selectors::matching::matches_selector;
 use selectors::parser::{Combinator, Component, Selector, SelectorInner, SelectorMethods};
 use selectors::visitor::SelectorVisitor;
 use smallvec::SmallVec;
 use std::borrow::Borrow;
 use std::cell::Cell;
 use std::clone::Clone;
 use std::cmp;
@@ -531,16 +531,17 @@ fn dir_selector_to_state(s: &[u16]) -> E
 impl<'a, E> Element for ElementWrapper<'a, E>
     where E: TElement,
 {
     type Impl = SelectorImpl;
 
     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),
     {
         // :moz-any is quite special, because we need to keep matching as a
         // snapshot.
         #[cfg(feature = "gecko")]
         {
@@ -576,36 +577,46 @@ impl<'a, E> Element for ElementWrapper<'
                 return state.contains(selector_flag);
             }
         }
 
         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()) {
             Some(snapshot_state) => snapshot_state.intersects(flag),
             None => {
                 self.element.match_non_ts_pseudo_class(pseudo_class,
                                                        context,
+                                                       relevant_link,
                                                        &mut |_, _| {})
             }
         }
     }
 
     fn match_pseudo_element(&self,
                             pseudo_element: &PseudoElement,
                             context: &mut MatchingContext)
                             -> bool
     {
         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))
     }
 
     fn first_child_element(&self) -> Option<Self> {
         self.element.first_child_element()
             .map(|e| ElementWrapper::new(e, self.snapshot_map))

--- a/servo/components/style/selector_parser.rs
+++ b/servo/components/style/selector_parser.rs
@@ -98,19 +98,16 @@ pub enum PseudoElementCascadeType {
     ///
     /// This pseudo-elements are resolved on the fly using *only* global rules
     /// (rules of the form `*|*`), and applying them to the parent style.
     Precomputed,
 }
 
 /// 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.
     fn matches_user_and_author_rules(&self) -> bool;
 }
 
 impl SelectorImpl {
     /// A helper to traverse each precomputed pseudo-element, executing `fun` on

--- a/servo/components/style/servo/selector_parser.rs
+++ b/servo/components/style/servo/selector_parser.rs
@@ -11,17 +11,16 @@ use attr::{AttrIdentifier, AttrValue};
 use cssparser::{Parser as CssParser, ToCss, serialize_identifier};
 use dom::{OpaqueNode, TElement, TNode};
 use element_state::ElementState;
 use fnv::FnvHashMap;
 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;
 use std::fmt;
 use std::fmt::Debug;
 use std::mem;
 use std::ops::{Deref, DerefMut};
 
@@ -590,20 +589,13 @@ impl ServoElementSnapshot {
             NamespaceConstraint::Any => {
                 self.any_attr_ignore_ns(local_name, |value| value.eval_selector(operation))
             }
         }
     }
 }
 
 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
     }
 }