--- a/servo/components/style/invalidation/element/invalidator.rs
+++ b/servo/components/style/invalidation/element/invalidator.rs
@@ -4,17 +4,17 @@
 
 //! The struct that takes care of encapsulating all the logic on where and how
 //! element styles need to be invalidated.
 
 use Atom;
 use context::SharedStyleContext;
 use data::ElementData;
 use dom::{TElement, TNode};
-use element_state::ElementState;
+use element_state::{ElementState, IN_VISITED_OR_UNVISITED_STATE};
 use invalidation::element::element_wrapper::{ElementSnapshot, ElementWrapper};
 use invalidation::element::invalidation_map::*;
 use invalidation::element::restyle_hints::*;
 use selector_map::SelectorMap;
 use selectors::matching::{CompoundSelectorMatchingResult};
 use selectors::matching::{MatchingContext, MatchingMode, VisitedHandlingMode};
 use selectors::matching::{matches_selector, matches_compound_selector};
 use selectors::parser::{Combinator, Component, Selector};
@@ -99,16 +99,28 @@ impl<'a, 'b: 'a, E> TreeStyleInvalidator
             ElementWrapper::new(self.element, shared_context.snapshot_map);
         let state_changes = wrapper.state_changes();
         let snapshot = wrapper.snapshot().expect("has_snapshot lied");
 
         if !snapshot.has_attrs() && state_changes.is_empty() {
             return;
         }
 
+        // 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.
+            let mut data = self.data.as_mut().unwrap();
+            data.ensure_restyle().hint.insert(RestyleHint::restyle_subtree().into());
+        }
+
         let mut classes_removed = SmallVec::<[Atom; 8]>::new();
         let mut classes_added = SmallVec::<[Atom; 8]>::new();
         if snapshot.class_changed() {
             // TODO(emilio): Do this more efficiently!
             snapshot.each_class(|c| {
                 if !self.element.has_class(c) {
                     classes_removed.push(c.clone())
                 }
@@ -518,17 +530,20 @@ impl<'a, 'b: 'a, E> InvalidationCollecto
         &mut self,
         map: &SelectorMap<Dependency>,
     ) {
         map.lookup_with_additional(
             self.lookup_element,
             self.removed_id,
             self.classes_removed,
             &mut |dependency| {
-                self.scan_dependency(dependency);
+                self.scan_dependency(
+                    dependency,
+                    /* is_visited_dependent = */ false
+                );
                 true
             }
         );
     }
     fn collect_state_dependencies(
         &mut self,
         map: &SelectorMap<StateDependency>,
         state_changes: ElementState,
@@ -536,23 +551,30 @@ impl<'a, 'b: 'a, E> InvalidationCollecto
         map.lookup_with_additional(
             self.lookup_element,
             self.removed_id,
             self.classes_removed,
             &mut |dependency| {
                 if !dependency.state.intersects(state_changes) {
                     return true;
                 }
-                self.scan_dependency(&dependency.dep);
+                self.scan_dependency(
+                    &dependency.dep,
+                    dependency.state.intersects(IN_VISITED_OR_UNVISITED_STATE)
+                );
                 true
             }
         );
     }
 
-    fn scan_dependency(&mut self, dependency: &Dependency) {
+    fn scan_dependency(
+        &mut self,
+        dependency: &Dependency,
+        is_visited_dependent: bool
+    ) {
         if !self.dependency_may_be_relevant(dependency) {
             return;
         }
 
         // TODO(emilio): Add a bloom filter here?
         //
         // If we decide to do so, we can't use the bloom filter for snapshots,
         // given that arbitrary elements in the parent chain may have mutated
@@ -586,17 +608,56 @@ impl<'a, 'b: 'a, E> InvalidationCollecto
                              &self.element,
                              &mut now_context,
                              &mut |_, _| {});
 
         // 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 {
-            self.note_dependency(dependency);
+            return self.note_dependency(dependency);
+        }
+
+        // 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 state or attribute change of
+        // this element (for example, for things like [foo]:visited).
+        //
+        // NOTE: This thing is actually untested because testing it is flaky,
+        // see the tests that were added and then backed out in bug 1328509.
+        if is_visited_dependent && now_context.relevant_link_found {
+            then_context.visited_handling = VisitedHandlingMode::RelevantLinkVisited;
+            let matched_then =
+                matches_selector(&dependency.selector,
+                                 dependency.selector_offset,
+                                 &dependency.hashes,
+                                 &self.wrapper,
+                                 &mut then_context,
+                                 &mut |_, _| {});
+
+            now_context.visited_handling = VisitedHandlingMode::RelevantLinkVisited;
+            let matches_now =
+                matches_selector(&dependency.selector,
+                                 dependency.selector_offset,
+                                 &dependency.hashes,
+                                 &self.element,
+                                 &mut now_context,
+                                 &mut |_, _| {});
+            if matched_then != matches_now {
+                return self.note_dependency(dependency);
+            }
         }
     }
 
     fn note_dependency(&mut self, dependency: &Dependency) {
         if dependency.affects_self() {
             self.invalidates_self = true;
         }