--- 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, StyleData};
 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, RelevantLinkStatus};
+use selectors::matching::{ElementSelectorFlags, MatchingContext, RelevantLinkStatus, VisitedHandlingMode};
 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;
@@ -359,17 +359,19 @@ impl<'le> fmt::Debug for ServoLayoutElem
         if let &Some(ref id) = unsafe { &*self.element.id_attribute() } {
             try!(write!(f, " id={}", id));
         }
         write!(f, "> ({:#x})", self.as_node().opaque().0)
     }
 }
 
 impl<'le> PresentationalHintsSynthesizer for ServoLayoutElement<'le> {
-    fn synthesize_presentational_hints_for_legacy_attributes<V>(&self, hints: &mut V)
+    fn synthesize_presentational_hints_for_legacy_attributes<V>(&self,
+                                                                _visited_handling: VisitedHandlingMode,
+                                                                hints: &mut V)
         where V: Push<ApplicableDeclarationBlock>
     {
         unsafe {
             self.element.synthesize_presentational_hints_for_legacy_attributes(hints);
         }
     }
 }
 
@@ -1223,11 +1225,13 @@ impl<'le> ::selectors::Element for Servo
 
     fn is_root(&self) -> bool {
         warn!("ServoThreadSafeLayoutElement::is_root called");
         false
     }
 }
 
 impl<'le> PresentationalHintsSynthesizer for ServoThreadSafeLayoutElement<'le> {
-    fn synthesize_presentational_hints_for_legacy_attributes<V>(&self, _hints: &mut V)
+    fn synthesize_presentational_hints_for_legacy_attributes<V>(&self,
+                                                                _visited_handling: VisitedHandlingMode,
+                                                                _hints: &mut V)
         where V: Push<ApplicableDeclarationBlock> {}
 }

--- a/servo/components/style/dom.rs
+++ b/servo/components/style/dom.rs
@@ -13,17 +13,17 @@ use atomic_refcell::{AtomicRef, AtomicRe
 use data::ElementData;
 use element_state::ElementState;
 use font_metrics::FontMetricsProvider;
 use properties::{ComputedValues, PropertyDeclarationBlock};
 #[cfg(feature = "gecko")] use properties::animated_properties::AnimationValue;
 #[cfg(feature = "gecko")] use properties::animated_properties::TransitionProperty;
 use rule_tree::CascadeLevel;
 use selector_parser::{ElementExt, PreExistingComputedValues, PseudoElement};
-use selectors::matching::ElementSelectorFlags;
+use selectors::matching::{ElementSelectorFlags, VisitedHandlingMode};
 use shared_lock::Locked;
 use sink::Push;
 use std::fmt;
 #[cfg(feature = "gecko")] use std::collections::HashMap;
 use std::fmt::Debug;
 use std::hash::Hash;
 use std::ops::Deref;
 use stylearc::Arc;
@@ -265,17 +265,19 @@ pub unsafe fn raw_note_descendants<E, B>
 
     curr.is_none()
 }
 
 /// A trait used to synthesize presentational hints for HTML element attributes.
 pub trait PresentationalHintsSynthesizer {
     /// Generate the proper applicable declarations due to presentational hints,
     /// and insert them into `hints`.
-    fn synthesize_presentational_hints_for_legacy_attributes<V>(&self, hints: &mut V)
+    fn synthesize_presentational_hints_for_legacy_attributes<V>(&self,
+                                                                visited_handling: VisitedHandlingMode,
+                                                                hints: &mut V)
         where V: Push<ApplicableDeclarationBlock>;
 }
 
 /// The element trait, the main abstraction the style crate acts over.
 pub trait TElement : Eq + PartialEq + Debug + Hash + Sized + Copy + Clone +
                      ElementExt + PresentationalHintsSynthesizer {
     /// The concrete node type.
     type ConcreteNode: TNode<ConcreteElement = Self>;

--- a/servo/components/style/gecko/wrapper.rs
+++ b/servo/components/style/gecko/wrapper.rs
@@ -30,22 +30,25 @@ use gecko_bindings::bindings;
 use gecko_bindings::bindings::{Gecko_DropStyleChildrenIterator, Gecko_MaybeCreateStyleChildrenIterator};
 use gecko_bindings::bindings::{Gecko_ElementState, Gecko_GetLastChild, Gecko_GetNextStyleChild};
 use gecko_bindings::bindings::{Gecko_IsRootElement, Gecko_MatchesElement, Gecko_Namespace};
 use gecko_bindings::bindings::{Gecko_SetNodeFlags, Gecko_UnsetNodeFlags};
 use gecko_bindings::bindings::Gecko_ClassOrClassList;
 use gecko_bindings::bindings::Gecko_ElementHasAnimations;
 use gecko_bindings::bindings::Gecko_ElementHasCSSAnimations;
 use gecko_bindings::bindings::Gecko_ElementHasCSSTransitions;
+use gecko_bindings::bindings::Gecko_GetActiveLinkAttrDeclarationBlock;
 use gecko_bindings::bindings::Gecko_GetAnimationRule;
 use gecko_bindings::bindings::Gecko_GetExtraContentStyleDeclarations;
 use gecko_bindings::bindings::Gecko_GetHTMLPresentationAttrDeclarationBlock;
 use gecko_bindings::bindings::Gecko_GetSMILOverrideDeclarationBlock;
 use gecko_bindings::bindings::Gecko_GetStyleAttrDeclarationBlock;
 use gecko_bindings::bindings::Gecko_GetStyleContext;
+use gecko_bindings::bindings::Gecko_GetUnvisitedLinkAttrDeclarationBlock;
+use gecko_bindings::bindings::Gecko_GetVisitedLinkAttrDeclarationBlock;
 use gecko_bindings::bindings::Gecko_IsSignificantChild;
 use gecko_bindings::bindings::Gecko_MatchStringArgPseudo;
 use gecko_bindings::bindings::Gecko_UnsetDirtyStyleAttr;
 use gecko_bindings::bindings::Gecko_UpdateAnimations;
 use gecko_bindings::structs;
 use gecko_bindings::structs::{RawGeckoElement, RawGeckoNode};
 use gecko_bindings::structs::{nsIAtom, nsIContent, nsINode_BooleanFlag, nsStyleContext};
 use gecko_bindings::structs::ELEMENT_HANDLED_SNAPSHOT;
@@ -61,17 +64,18 @@ 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, RelevantLinkStatus};
+use selectors::matching::{ElementSelectorFlags, MatchingContext, MatchingMode};
+use selectors::matching::{RelevantLinkStatus, VisitedHandlingMode};
 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::mem;
 use std::ops::DerefMut;
@@ -1031,17 +1035,19 @@ impl<'le> Eq for GeckoElement<'le> {}
 
 impl<'le> Hash for GeckoElement<'le> {
     fn hash<H: Hasher>(&self, state: &mut H) {
         (self.0 as *const _).hash(state);
     }
 }
 
 impl<'le> PresentationalHintsSynthesizer for GeckoElement<'le> {
-    fn synthesize_presentational_hints_for_legacy_attributes<V>(&self, hints: &mut V)
+    fn synthesize_presentational_hints_for_legacy_attributes<V>(&self,
+                                                                visited_handling: VisitedHandlingMode,
+                                                                hints: &mut V)
         where V: Push<ApplicableDeclarationBlock>,
     {
         use properties::longhands::_x_lang::SpecifiedValue as SpecifiedLang;
         use properties::longhands::color::SpecifiedValue as SpecifiedColor;
         use properties::longhands::text_align::SpecifiedValue as SpecifiedTextAlign;
         use values::specified::color::Color;
         lazy_static! {
             static ref TH_RULE: ApplicableDeclarationBlock = {
@@ -1093,16 +1099,47 @@ impl<'le> PresentationalHintsSynthesizer
         let declarations = unsafe { Gecko_GetExtraContentStyleDeclarations(self.0) };
         let declarations = declarations.and_then(|s| s.as_arc_opt());
         if let Some(decl) = declarations {
             hints.push(
                 ApplicableDeclarationBlock::from_declarations(Clone::clone(decl), ServoCascadeLevel::PresHints)
             );
         }
 
+        // Support for link, vlink, and alink presentation hints on <body>
+        if self.is_link() {
+            // Unvisited vs. visited styles are computed up-front based on the
+            // visited mode (not the element's actual state).
+            let declarations = match visited_handling {
+                VisitedHandlingMode::AllLinksUnvisited => unsafe {
+                    Gecko_GetUnvisitedLinkAttrDeclarationBlock(self.0)
+                },
+                VisitedHandlingMode::RelevantLinkVisited => unsafe {
+                    Gecko_GetVisitedLinkAttrDeclarationBlock(self.0)
+                },
+            };
+            let declarations = declarations.and_then(|s| s.as_arc_opt());
+            if let Some(decl) = declarations {
+                hints.push(
+                    ApplicableDeclarationBlock::from_declarations(Clone::clone(decl), ServoCascadeLevel::PresHints)
+                );
+            }
+
+            let active = self.get_state().intersects(NonTSPseudoClass::Active.state_flag());
+            if active {
+                let declarations = unsafe { Gecko_GetActiveLinkAttrDeclarationBlock(self.0) };
+                let declarations = declarations.and_then(|s| s.as_arc_opt());
+                if let Some(decl) = declarations {
+                    hints.push(
+                        ApplicableDeclarationBlock::from_declarations(Clone::clone(decl), ServoCascadeLevel::PresHints)
+                    );
+                }
+            }
+        }
+
         // xml:lang has precedence over lang, which can be
         // set by Gecko_GetHTMLPresentationAttrDeclarationBlock
         //
         // http://www.whatwg.org/specs/web-apps/current-work/multipage/elements.html#language
         let ptr = unsafe {
             bindings::Gecko_GetXMLLangValue(self.0)
         };
         if !ptr.is_null() {

--- a/servo/components/style/sharing/mod.rs
+++ b/servo/components/style/sharing/mod.rs
@@ -9,17 +9,17 @@ use Atom;
 use bit_vec::BitVec;
 use cache::{LRUCache, LRUCacheMutIterator};
 use context::{SelectorFlagsMap, SharedStyleContext, StyleContext};
 use data::{ComputedStyle, ElementData, ElementStyles};
 use dom::{TElement, SendElement};
 use matching::{ChildCascadeRequirement, MatchMethods};
 use properties::ComputedValues;
 use selectors::bloom::BloomFilter;
-use selectors::matching::{ElementSelectorFlags, StyleRelations};
+use selectors::matching::{ElementSelectorFlags, VisitedHandlingMode, StyleRelations};
 use smallvec::SmallVec;
 use std::mem;
 use std::ops::Deref;
 use stylist::{ApplicableDeclarationBlock, Stylist};
 
 mod checks;
 
 /// The amount of nodes that the style sharing candidate cache should hold at
@@ -61,17 +61,20 @@ impl ValidationData {
 
     /// Get or compute the list of presentational attributes associated with
     /// this element.
     pub fn pres_hints<E>(&mut self, element: E) -> &[ApplicableDeclarationBlock]
         where E: TElement,
     {
         if self.pres_hints.is_none() {
             let mut pres_hints = SmallVec::new();
-            element.synthesize_presentational_hints_for_legacy_attributes(&mut pres_hints);
+            element.synthesize_presentational_hints_for_legacy_attributes(
+                VisitedHandlingMode::AllLinksUnvisited,
+                &mut pres_hints
+            );
             self.pres_hints = Some(pres_hints);
         }
         &*self.pres_hints.as_ref().unwrap()
     }
 
     /// Get or compute the class-list associated with this element.
     pub fn class_list<E>(&mut self, element: E) -> &[Atom]
         where E: TElement,

--- a/servo/components/style/stylist.rs
+++ b/servo/components/style/stylist.rs
@@ -954,17 +954,20 @@ impl Stylist {
                                               context,
                                               flags_setter,
                                               CascadeLevel::UANormal);
         debug!("UA normal: {:?}", context.relations);
 
         if pseudo_element.is_none() && !only_default_rules {
             // Step 2: Presentational hints.
             let length_before_preshints = applicable_declarations.len();
-            element.synthesize_presentational_hints_for_legacy_attributes(applicable_declarations);
+            element.synthesize_presentational_hints_for_legacy_attributes(
+                context.visited_handling,
+                applicable_declarations
+            );
             if applicable_declarations.len() != length_before_preshints {
                 if cfg!(debug_assertions) {
                     for declaration in &applicable_declarations[length_before_preshints..] {
                         assert_eq!(declaration.level, CascadeLevel::PresHints);
                     }
                 }
                 // Note the existence of presentational attributes so that the
                 // style sharing cache can avoid re-querying them if they don't