Refactor style to be completely backend-independent

This commit refactors the style crate to be completely independent of
the actual implementation and pseudo-elements supported.

This also adds a gecko backend which introduces parsing for the
anonymous box pseudo-elements[1], although there's still no way of
querying them.

https://mxr.mozilla.org/mozilla-central/source/layout/style/nsCSSAnonBoxList.h

27 files changed, 394 insertions, 272 deletions

diff --git a/components/layout/Cargo.toml b/components/layout/Cargo.toml
index c926475ae41..8ee2de344b7 100644
--- a/components/layout/Cargo.toml
+++ b/components/layout/Cargo.toml
@@ -64,7 +64,7 @@ heapsize_plugin = "0.1.2"
 libc = "0.2"
 log = "0.3"
 rustc-serialize = "0.3"
-selectors = {version = "0.4.2", features = ["heap_size"]}
+selectors = {version = "0.5", features = ["heap_size"]}
 serde = "0.6"
 serde_json = "0.5"
 serde_macros = "0.6"
diff --git a/components/layout/context.rs b/components/layout/context.rs
index 7eb01a68846..953c98797f5 100644
--- a/components/layout/context.rs
+++ b/components/layout/context.rs
@@ -25,8 +25,10 @@ use std::hash::BuildHasherDefault;
 use std::rc::Rc;
 use std::sync::mpsc::Sender;
 use std::sync::{Arc, Mutex};
-use style::context::{LocalStyleContext, SharedStyleContext, StyleContext};
+use style::context::{LocalStyleContext, StyleContext};
 use style::matching::{ApplicableDeclarationsCache, StyleSharingCandidateCache};
+use style::selector_impl::ServoSelectorImpl;
+use style::servo::SharedStyleContext;
 use url::Url;
 use util::opts;
 
@@ -104,7 +106,7 @@ pub struct LayoutContext<'a> {
     cached_local_layout_context: Rc<LocalLayoutContext>,
 }
 
-impl<'a> StyleContext<'a> for LayoutContext<'a> {
+impl<'a> StyleContext<'a, ServoSelectorImpl> for LayoutContext<'a> {
     fn shared_context(&self) -> &'a SharedStyleContext {
         &self.shared.style_context
     }
diff --git a/components/layout/data.rs b/components/layout/data.rs
index 459743cd689..b11e4ebfd05 100644
--- a/components/layout/data.rs
+++ b/components/layout/data.rs
@@ -4,7 +4,7 @@
 
 use construct::ConstructionResult;
 use incremental::RestyleDamage;
-use style::data::PrivateStyleData;
+use style::servo::PrivateStyleData;
 
 /// Data that layout associates with a node.
 pub struct PrivateLayoutData {
diff --git a/components/layout/layout_thread.rs b/components/layout/layout_thread.rs
index aaa6a1e98c0..a540039c51b 100644
--- a/components/layout/layout_thread.rs
+++ b/components/layout/layout_thread.rs
@@ -62,13 +62,15 @@ use std::sync::mpsc::{channel, Sender, Receiver};
 use std::sync::{Arc, Mutex, MutexGuard, RwLock};
 use style::animation::Animation;
 use style::computed_values::{filter, mix_blend_mode};
-use style::context::{SharedStyleContext, StylistWrapper, ReflowGoal};
+use style::context::{ReflowGoal, StylistWrapper};
 use style::dom::{TDocument, TElement, TNode};
 use style::error_reporting::ParseErrorReporter;
 use style::media_queries::{Device, MediaType};
 use style::parallel::WorkQueueData;
-use style::selector_matching::{Stylist, USER_OR_USER_AGENT_STYLESHEETS};
-use style::stylesheets::{CSSRuleIteratorExt, Stylesheet};
+use style::selector_impl::ServoSelectorImpl;
+use style::selector_matching::USER_OR_USER_AGENT_STYLESHEETS;
+use style::servo::{SharedStyleContext, Stylesheet, Stylist};
+use style::stylesheets::CSSRuleIteratorExt;
 use traversal::RecalcStyleAndConstructFlows;
 use url::Url;
 use util::geometry::MAX_RECT;
@@ -477,7 +479,7 @@ impl LayoutThread {
             style_context: SharedStyleContext {
                 viewport_size: self.viewport_size.clone(),
                 screen_size_changed: screen_size_changed,
-                stylist: StylistWrapper(&*rw_data.stylist),
+                stylist: StylistWrapper::<ServoSelectorImpl>(&*rw_data.stylist),
                 generation: self.generation,
                 goal: goal,
                 new_animations_sender: Mutex::new(self.new_animations_sender.clone()),
diff --git a/components/layout/traversal.rs b/components/layout/traversal.rs
index 69e85c39303..d5febecc483 100644
--- a/components/layout/traversal.rs
+++ b/components/layout/traversal.rs
@@ -16,6 +16,7 @@ use incremental::{BUBBLE_ISIZES, REFLOW, REFLOW_OUT_OF_FLOW, REPAINT, RestyleDam
 use std::mem;
 use style::context::{StyleContext, ReflowGoal};
 use style::matching::MatchMethods;
+use style::selector_impl::ServoSelectorImpl;
 use style::traversal::{DomTraversalContext, STYLE_BLOOM};
 use style::traversal::{put_thread_local_bloom_filter, recalc_style_at};
 use util::opts;
@@ -27,7 +28,8 @@ pub struct RecalcStyleAndConstructFlows<'lc> {
     root: OpaqueNode,
 }
 
-impl<'lc, 'ln, N: LayoutNode<'ln>> DomTraversalContext<'ln, N> for RecalcStyleAndConstructFlows<'lc> {
+impl<'lc, 'ln, N: LayoutNode<'ln>> DomTraversalContext<'ln, N> for RecalcStyleAndConstructFlows<'lc>
+    where N::ConcreteElement: ::selectors::Element<Impl=ServoSelectorImpl> {
     type SharedContext = SharedLayoutContext;
     #[allow(unsafe_code)]
     fn new<'a>(shared: &'a Self::SharedContext, root: OpaqueNode) -> Self {
diff --git a/components/layout/wrapper.rs b/components/layout/wrapper.rs
index 1c8f1ee1d8e..faacdbf44f0 100644
--- a/components/layout/wrapper.rs
+++ b/components/layout/wrapper.rs
@@ -64,13 +64,13 @@ use std::sync::Arc;
 use string_cache::{Atom, Namespace};
 use style::computed_values::content::ContentItem;
 use style::computed_values::{content, display};
-use style::data::PrivateStyleData;
 use style::dom::{TDocument, TElement, TNode, UnsafeNode};
 use style::element_state::*;
 use style::properties::ComputedValues;
 use style::properties::{PropertyDeclaration, PropertyDeclarationBlock};
 use style::restyle_hints::ElementSnapshot;
-use style::selector_impl::{NonTSPseudoClass, ServoSelectorImpl};
+use style::selector_impl::{NonTSPseudoClass, PseudoElement, ServoSelectorImpl};
+use style::servo::PrivateStyleData;
 use url::Url;
 use util::str::{is_whitespace, search_index};
 
@@ -664,16 +664,20 @@ pub trait ThreadSafeLayoutNode<'ln> : Clone + Copy + Sized {
 
     #[inline]
     fn get_before_pseudo(&self) -> Option<Self> {
-        self.borrow_layout_data().unwrap().style_data.before_style.as_ref().map(|style| {
-            self.with_pseudo(PseudoElementType::Before(style.get_box().display))
-        })
+        self.borrow_layout_data().unwrap()
+            .style_data.per_pseudo
+            .get(&PseudoElement::Before).unwrap_or(&None).as_ref().map(|style| {
+                self.with_pseudo(PseudoElementType::Before(style.get_box().display))
+            })
     }
 
     #[inline]
     fn get_after_pseudo(&self) -> Option<Self> {
-        self.borrow_layout_data().unwrap().style_data.after_style.as_ref().map(|style| {
-            self.with_pseudo(PseudoElementType::After(style.get_box().display))
-        })
+        self.borrow_layout_data().unwrap()
+            .style_data.per_pseudo
+            .get(&PseudoElement::After).unwrap_or(&None).as_ref().map(|style| {
+                self.with_pseudo(PseudoElementType::After(style.get_box().display))
+            })
     }
 
     /// Borrows the layout data immutably. Fails on a conflicting borrow.
@@ -696,8 +700,8 @@ pub trait ThreadSafeLayoutNode<'ln> : Clone + Copy + Sized {
     fn style(&self) -> Ref<Arc<ComputedValues>> {
         Ref::map(self.borrow_layout_data().unwrap(), |data| {
             let style = match self.get_pseudo_element_type() {
-                PseudoElementType::Before(_) => &data.style_data.before_style,
-                PseudoElementType::After(_) => &data.style_data.after_style,
+                PseudoElementType::Before(_) => data.style_data.per_pseudo.get(&PseudoElement::Before).unwrap(),
+                PseudoElementType::After(_) => data.style_data.per_pseudo.get(&PseudoElement::After).unwrap(),
                 PseudoElementType::Normal => &data.style_data.style,
             };
             style.as_ref().unwrap()
@@ -711,9 +715,19 @@ pub trait ThreadSafeLayoutNode<'ln> : Clone + Copy + Sized {
         let mut data = self.mutate_layout_data().unwrap();
         let style =
             match self.get_pseudo_element_type() {
-                PseudoElementType::Before(_) => &mut data.style_data.before_style,
-                PseudoElementType::After (_) => &mut data.style_data.after_style,
-                PseudoElementType::Normal    => &mut data.style_data.style,
+                PseudoElementType::Before(_) => {
+                    match data.style_data.per_pseudo.get_mut(&PseudoElement::Before) {
+                        None => return,
+                        Some(style) => style,
+                    }
+                }
+                PseudoElementType::After(_) => {
+                    match data.style_data.per_pseudo.get_mut(&PseudoElement::After) {
+                        None => return,
+                        Some(style) => style,
+                    }
+                }
+                PseudoElementType::Normal => &mut data.style_data.style,
             };
 
         *style = None;
@@ -934,10 +948,11 @@ impl<'ln> ThreadSafeLayoutNode<'ln> for ServoThreadSafeLayoutNode<'ln> {
             let data = &self.borrow_layout_data().unwrap().style_data;
 
             let style = if self.pseudo.is_before() {
-                &data.before_style
+                data.per_pseudo.get(&PseudoElement::Before).unwrap()
             } else {
-                &data.after_style
+                data.per_pseudo.get(&PseudoElement::After).unwrap()
             };
+
             return match style.as_ref().unwrap().get_box().content {
                 content::T::Content(ref value) if !value.is_empty() => {
                     TextContent::GeneratedContent((*value).clone())
diff --git a/components/script/Cargo.toml b/components/script/Cargo.toml
index ef93986c204..1f3b7874d22 100644
--- a/components/script/Cargo.toml
+++ b/components/script/Cargo.toml
@@ -81,7 +81,7 @@ num = "0.1.24"
 rand = "0.3"
 ref_slice = "0.1.0"
 rustc-serialize = "0.3"
-selectors = {version = "0.4.2", features = ["heap_size"]}
+selectors = {version = "0.5", features = ["heap_size"]}
 serde = "0.6"
 smallvec = "0.1"
 string_cache = {version = "0.2.9", features = ["heap_size", "unstable"]}
diff --git a/components/script/dom/document.rs b/components/script/dom/document.rs
index 99a61d2f981..a3af57b0814 100644
--- a/components/script/dom/document.rs
+++ b/components/script/dom/document.rs
@@ -105,7 +105,7 @@ use std::sync::Arc;
 use string_cache::{Atom, QualName};
 use style::context::ReflowGoal;
 use style::restyle_hints::ElementSnapshot;
-use style::stylesheets::Stylesheet;
+use style::servo::Stylesheet;
 use time;
 use url::{Host, Url};
 use util::str::{DOMString, split_html_space_chars, str_join};
diff --git a/components/script/dom/htmllinkelement.rs b/components/script/dom/htmllinkelement.rs
index 38bb2287ac3..683b8cc6a84 100644
--- a/components/script/dom/htmllinkelement.rs
+++ b/components/script/dom/htmllinkelement.rs
@@ -36,7 +36,8 @@ use std::mem;
 use std::sync::{Arc, Mutex};
 use string_cache::Atom;
 use style::media_queries::{MediaQueryList, parse_media_query_list};
-use style::stylesheets::{Origin, Stylesheet};
+use style::servo::Stylesheet;
+use style::stylesheets::Origin;
 use url::Url;
 use util::str::{DOMString, HTML_SPACE_CHARACTERS};
 
diff --git a/components/script/dom/htmlmetaelement.rs b/components/script/dom/htmlmetaelement.rs
index fdba6dc7c3c..779c5c79e07 100644
--- a/components/script/dom/htmlmetaelement.rs
+++ b/components/script/dom/htmlmetaelement.rs
@@ -15,7 +15,8 @@ use dom::virtualmethods::VirtualMethods;
 use std::ascii::AsciiExt;
 use std::sync::Arc;
 use string_cache::Atom;
-use style::stylesheets::{CSSRule, Origin, Stylesheet};
+use style::servo::Stylesheet;
+use style::stylesheets::{CSSRule, Origin};
 use style::viewport::ViewportRule;
 use util::str::{DOMString, HTML_SPACE_CHARACTERS};
 
diff --git a/components/script/dom/htmlstyleelement.rs b/components/script/dom/htmlstyleelement.rs
index 4b423b920b7..067561d4181 100644
--- a/components/script/dom/htmlstyleelement.rs
+++ b/components/script/dom/htmlstyleelement.rs
@@ -17,7 +17,8 @@ use layout_interface::{LayoutChan, Msg};
 use std::sync::Arc;
 use string_cache::Atom;
 use style::media_queries::parse_media_query_list;
-use style::stylesheets::{Origin, Stylesheet};
+use style::servo::Stylesheet;
+use style::stylesheets::Origin;
 use util::str::DOMString;
 
 #[dom_struct]
diff --git a/components/script/layout_interface.rs b/components/script/layout_interface.rs
index c759b358e79..831c04a9516 100644
--- a/components/script/layout_interface.rs
+++ b/components/script/layout_interface.rs
@@ -24,7 +24,7 @@ use std::sync::mpsc::{Receiver, Sender, channel};
 use string_cache::Atom;
 use style::context::ReflowGoal;
 use style::selector_impl::PseudoElement;
-use style::stylesheets::Stylesheet;
+use style::servo::Stylesheet;
 use url::Url;
 use util::ipc::OptionalOpaqueIpcSender;
 
diff --git a/components/servo/Cargo.lock b/components/servo/Cargo.lock
index 4f62b6d95e4..b1dfc4d674b 100644
--- a/components/servo/Cargo.lock
+++ b/components/servo/Cargo.lock
@@ -1003,7 +1003,7 @@ dependencies = [
  "rustc-serialize 0.3.16 (registry+https://github.com/rust-lang/crates.io-index)",
  "script 0.0.1",
  "script_traits 0.0.1",
- "selectors 0.4.2 (registry+https://github.com/rust-lang/crates.io-index)",
+ "selectors 0.5.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "serde 0.6.6 (registry+https://github.com/rust-lang/crates.io-index)",
  "serde_json 0.5.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "serde_macros 0.6.5 (registry+https://github.com/rust-lang/crates.io-index)",
@@ -1590,7 +1590,7 @@ dependencies = [
  "ref_slice 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "rustc-serialize 0.3.16 (registry+https://github.com/rust-lang/crates.io-index)",
  "script_traits 0.0.1",
- "selectors 0.4.2 (registry+https://github.com/rust-lang/crates.io-index)",
+ "selectors 0.5.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "serde 0.6.6 (registry+https://github.com/rust-lang/crates.io-index)",
  "smallvec 0.1.5 (registry+https://github.com/rust-lang/crates.io-index)",
  "string_cache 0.2.9 (registry+https://github.com/rust-lang/crates.io-index)",
@@ -1641,7 +1641,7 @@ dependencies = [
 
 [[package]]
 name = "selectors"
-version = "0.4.2"
+version = "0.5.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 dependencies = [
  "bitflags 0.3.3 (registry+https://github.com/rust-lang/crates.io-index)",
@@ -1850,7 +1850,7 @@ dependencies = [
  "num 0.1.28 (registry+https://github.com/rust-lang/crates.io-index)",
  "plugins 0.0.1",
  "rustc-serialize 0.3.16 (registry+https://github.com/rust-lang/crates.io-index)",
- "selectors 0.4.2 (registry+https://github.com/rust-lang/crates.io-index)",
+ "selectors 0.5.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "serde 0.6.6 (registry+https://github.com/rust-lang/crates.io-index)",
  "serde_macros 0.6.5 (registry+https://github.com/rust-lang/crates.io-index)",
  "smallvec 0.1.5 (registry+https://github.com/rust-lang/crates.io-index)",
@@ -1870,7 +1870,7 @@ dependencies = [
  "euclid 0.6.2 (registry+https://github.com/rust-lang/crates.io-index)",
  "msg 0.0.1",
  "plugins 0.0.1",
- "selectors 0.4.2 (registry+https://github.com/rust-lang/crates.io-index)",
+ "selectors 0.5.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "string_cache 0.2.9 (registry+https://github.com/rust-lang/crates.io-index)",
  "style 0.0.1",
  "style_traits 0.0.1",
@@ -1891,7 +1891,7 @@ dependencies = [
  "num 0.1.28 (registry+https://github.com/rust-lang/crates.io-index)",
  "plugins 0.0.1",
  "rustc-serialize 0.3.16 (registry+https://github.com/rust-lang/crates.io-index)",
- "selectors 0.4.2 (registry+https://github.com/rust-lang/crates.io-index)",
+ "selectors 0.5.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "serde 0.6.6 (registry+https://github.com/rust-lang/crates.io-index)",
  "serde_macros 0.6.5 (registry+https://github.com/rust-lang/crates.io-index)",
  "url 0.5.5 (registry+https://github.com/rust-lang/crates.io-index)",
@@ -2049,7 +2049,7 @@ dependencies = [
  "plugins 0.0.1",
  "rand 0.3.12 (registry+https://github.com/rust-lang/crates.io-index)",
  "rustc-serialize 0.3.16 (registry+https://github.com/rust-lang/crates.io-index)",
- "selectors 0.4.2 (registry+https://github.com/rust-lang/crates.io-index)",
+ "selectors 0.5.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "serde 0.6.6 (registry+https://github.com/rust-lang/crates.io-index)",
  "serde_macros 0.6.5 (registry+https://github.com/rust-lang/crates.io-index)",
  "smallvec 0.1.5 (registry+https://github.com/rust-lang/crates.io-index)",
diff --git a/components/style/Cargo.toml b/components/style/Cargo.toml
index 5ab2db3199b..9e681f94b03 100644
--- a/components/style/Cargo.toml
+++ b/components/style/Cargo.toml
@@ -32,7 +32,7 @@ log = "0.3"
 matches = "0.1"
 num = "0.1.24"
 rustc-serialize = "0.3"
-selectors = {version = "0.4.2", features = ["heap_size", "unstable"]}
+selectors = {version = "0.5", features = ["heap_size", "unstable"]}
 serde = "0.6"
 serde_macros = "0.6"
 smallvec = "0.1"
diff --git a/components/style/context.rs b/components/style/context.rs
index f6b3cf86631..6e4edfd1b52 100644
--- a/components/style/context.rs
+++ b/components/style/context.rs
@@ -8,19 +8,20 @@ use dom::OpaqueNode;
 use error_reporting::ParseErrorReporter;
 use euclid::Size2D;
 use matching::{ApplicableDeclarationsCache, StyleSharingCandidateCache};
+use selector_impl::SelectorImplExt;
 use selector_matching::Stylist;
 use std::cell::RefCell;
 use std::collections::HashMap;
 use std::sync::mpsc::Sender;
 use std::sync::{Arc, Mutex, RwLock};
 
-pub struct StylistWrapper(pub *const Stylist);
+pub struct StylistWrapper<Impl: SelectorImplExt>(pub *const Stylist<Impl>);
 
 // FIXME(#6569) This implementation is unsound.
 #[allow(unsafe_code)]
-unsafe impl Sync for StylistWrapper {}
+unsafe impl<Impl: SelectorImplExt> Sync for StylistWrapper<Impl> {}
 
-pub struct SharedStyleContext {
+pub struct SharedStyleContext<Impl: SelectorImplExt> {
     /// The current viewport size.
     pub viewport_size: Size2D<Au>,
 
@@ -30,7 +31,7 @@ pub struct SharedStyleContext {
     /// The CSS selector stylist.
     ///
     /// FIXME(#2604): Make this no longer an unsafe pointer once we have fast `RWArc`s.
-    pub stylist: StylistWrapper,
+    pub stylist: StylistWrapper<Impl>,
 
     /// Starts at zero, and increased by one every time a layout completes.
     /// This can be used to easily check for invalid stale data.
@@ -58,8 +59,9 @@ pub struct LocalStyleContext {
     pub style_sharing_candidate_cache: RefCell<StyleSharingCandidateCache>,
 }
 
-pub trait StyleContext<'a> {
-    fn shared_context(&self) -> &'a SharedStyleContext;
+pub trait StyleContext<'a, Impl: SelectorImplExt> {
+
+    fn shared_context(&self) -> &'a SharedStyleContext<Impl>;
     fn local_context(&self) -> &LocalStyleContext;
 }
 
diff --git a/components/style/data.rs b/components/style/data.rs
index bfd1cd6113a..244e97e362d 100644
--- a/components/style/data.rs
+++ b/components/style/data.rs
@@ -3,29 +3,27 @@
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 use properties::ComputedValues;
+use selectors::parser::SelectorImpl;
+use std::collections::HashMap;
 use std::sync::Arc;
 use std::sync::atomic::AtomicIsize;
 
-pub struct PrivateStyleData {
+pub struct PrivateStyleData<Impl: SelectorImpl> {
     /// The results of CSS styling for this node.
     pub style: Option<Arc<ComputedValues>>,
 
-    /// The results of CSS styling for this node's `before` pseudo-element, if any.
-    pub before_style: Option<Arc<ComputedValues>>,
-
-    /// The results of CSS styling for this node's `after` pseudo-element, if any.
-    pub after_style: Option<Arc<ComputedValues>>,
+    /// The results of CSS styling for each pseudo-element (if any).
+    pub per_pseudo: HashMap<Impl::PseudoElement, Option<Arc<ComputedValues>>>,
 
     /// Information needed during parallel traversals.
     pub parallel: DomParallelInfo,
 }
 
-impl PrivateStyleData {
-    pub fn new() -> PrivateStyleData {
+impl<Impl: SelectorImpl> PrivateStyleData<Impl> {
+    pub fn new() -> PrivateStyleData<Impl> {
         PrivateStyleData {
             style: None,
-            before_style: None,
-            after_style: None,
+            per_pseudo: HashMap::new(),
             parallel: DomParallelInfo::new(),
         }
     }
diff --git a/components/style/dom.rs b/components/style/dom.rs
index 9b0ce59167d..f4df206d32f 100644
--- a/components/style/dom.rs
+++ b/components/style/dom.rs
@@ -8,7 +8,8 @@ use data::PrivateStyleData;
 use element_state::ElementState;
 use properties::{ComputedValues, PropertyDeclaration, PropertyDeclarationBlock};
 use restyle_hints::{ElementSnapshot, RESTYLE_DESCENDANTS, RESTYLE_LATER_SIBLINGS, RESTYLE_SELF, RestyleHint};
-use selector_impl::ServoSelectorImpl;
+use selector_impl::ElementExt;
+use selectors::Element;
 use selectors::matching::DeclarationBlock;
 use smallvec::VecLike;
 use std::cell::{Ref, RefMut};
@@ -136,15 +137,18 @@ pub trait TNode<'ln> : Sized + Copy + Clone {
 
     /// Borrows the PrivateStyleData without checks.
     #[inline(always)]
-    unsafe fn borrow_data_unchecked(&self) -> Option<*const PrivateStyleData>;
+    unsafe fn borrow_data_unchecked(&self)
+        -> Option<*const PrivateStyleData<<Self::ConcreteElement as Element>::Impl>>;
 
     /// Borrows the PrivateStyleData immutably. Fails on a conflicting borrow.
     #[inline(always)]
-    fn borrow_data(&self) -> Option<Ref<PrivateStyleData>>;
+    fn borrow_data(&self)
+        -> Option<Ref<PrivateStyleData<<Self::ConcreteElement as Element>::Impl>>>;
 
     /// Borrows the PrivateStyleData mutably. Fails on a conflicting borrow.
     #[inline(always)]
-    fn mutate_data(&self) -> Option<RefMut<PrivateStyleData>>;
+    fn mutate_data(&self)
+        -> Option<RefMut<PrivateStyleData<<Self::ConcreteElement as Element>::Impl>>>;
 
     /// Get the description of how to account for recent style changes.
     fn restyle_damage(self) -> Self::ConcreteRestyleDamage;
@@ -165,7 +169,7 @@ pub trait TNode<'ln> : Sized + Copy + Clone {
 
     /// Returns the style results for the given node. If CSS selector matching
     /// has not yet been performed, fails.
-    fn style(&self) -> Ref<Arc<ComputedValues>> {
+    fn style(&'ln self) -> Ref<Arc<ComputedValues>> {
         Ref::map(self.borrow_data().unwrap(), |data| data.style.as_ref().unwrap())
     }
 
@@ -186,7 +190,7 @@ pub trait TDocument<'ld> : Sized + Copy + Clone {
     fn drain_modified_elements(&self) -> Vec<(Self::ConcreteElement, ElementSnapshot)>;
 }
 
-pub trait TElement<'le> : Sized + Copy + Clone + ::selectors::Element<Impl=ServoSelectorImpl> {
+pub trait TElement<'le> : Sized + Copy + Clone + ElementExt {
     type ConcreteNode: TNode<'le, ConcreteElement = Self, ConcreteDocument = Self::ConcreteDocument>;
     type ConcreteDocument: TDocument<'le, ConcreteNode = Self::ConcreteNode, ConcreteElement = Self>;
 
diff --git a/components/style/lib.rs b/components/style/lib.rs
index 6dbb7250ffc..2305b0271cb 100644
--- a/components/style/lib.rs
+++ b/components/style/lib.rs
@@ -62,6 +62,7 @@ pub mod restyle_hints;
 pub mod selector_impl;
 pub mod selector_matching;
 pub mod sequential;
+pub mod servo;
 pub mod stylesheets;
 pub mod traversal;
 #[macro_use]
diff --git a/components/style/matching.rs b/components/style/matching.rs
index 0e7ee4b6453..f4c5cd191cd 100644
--- a/components/style/matching.rs
+++ b/components/style/matching.rs
@@ -9,13 +9,14 @@ use context::SharedStyleContext;
 use data::PrivateStyleData;
 use dom::{TElement, TNode, TRestyleDamage};
 use properties::{ComputedValues, PropertyDeclaration, cascade};
-use selector_impl::{NonTSPseudoClass, PseudoElement};
+use selector_impl::SelectorImplExt;
 use selector_matching::{DeclarationBlock, Stylist};
 use selectors::Element;
 use selectors::bloom::BloomFilter;
 use selectors::matching::{CommonStyleAffectingAttributeMode, CommonStyleAffectingAttributes};
 use selectors::matching::{common_style_affecting_attributes, rare_style_affecting_attributes};
 use smallvec::SmallVec;
+use std::collections::HashMap;
 use std::hash::{Hash, Hasher};
 use std::slice::Iter;
 use std::sync::mpsc::Sender;
@@ -51,23 +52,27 @@ fn create_common_style_affecting_attributes_from_element<'le, E: TElement<'le>>(
     flags
 }
 
-pub struct ApplicableDeclarations {
+pub struct ApplicableDeclarations<Impl: SelectorImplExt> {
     pub normal: SmallVec<[DeclarationBlock; 16]>,
-    pub before: Vec<DeclarationBlock>,
-    pub after: Vec<DeclarationBlock>,
+    pub per_pseudo: HashMap<Impl::PseudoElement, Vec<DeclarationBlock>>,
 
     /// Whether the `normal` declarations are shareable with other nodes.
     pub normal_shareable: bool,
 }
 
-impl ApplicableDeclarations {
-    pub fn new() -> ApplicableDeclarations {
-        ApplicableDeclarations {
+impl<Impl: SelectorImplExt> ApplicableDeclarations<Impl> {
+    pub fn new() -> ApplicableDeclarations<Impl> {
+        let mut applicable_declarations = ApplicableDeclarations {
             normal: SmallVec::new(),
-            before: Vec::new(),
-            after: Vec::new(),
+            per_pseudo: HashMap::new(),
             normal_shareable: false,
-        }
+        };
+
+        Impl::each_eagerly_cascaded_pseudo_element(|pseudo| {
+            applicable_declarations.per_pseudo.insert(pseudo, vec![]);
+        });
+
+        applicable_declarations
     }
 }
 
@@ -246,7 +251,7 @@ impl StyleSharingCandidate {
             local_name: element.get_local_name().clone(),
             class: element.get_attr(&ns!(), &atom!("class"))
                           .map(|string| string.to_owned()),
-            link: element.match_non_ts_pseudo_class(NonTSPseudoClass::AnyLink),
+            link: element.is_link(),
             namespace: (*element.get_namespace()).clone(),
             common_style_affecting_attributes:
                    create_common_style_affecting_attributes_from_element::<'le, E>(&element)
@@ -314,7 +319,7 @@ impl StyleSharingCandidate {
             }
         }
 
-        if element.match_non_ts_pseudo_class(NonTSPseudoClass::AnyLink) != self.link {
+        if element.is_link() != self.link {
             return false
         }
 
@@ -359,9 +364,10 @@ pub enum StyleSharingResult<ConcreteRestyleDamage: TRestyleDamage> {
     StyleWasShared(usize, ConcreteRestyleDamage),
 }
 
-trait PrivateMatchMethods<'ln>: TNode<'ln> {
+trait PrivateMatchMethods<'ln>: TNode<'ln>
+    where <Self::ConcreteElement as Element>::Impl: SelectorImplExt {
     fn cascade_node_pseudo_element(&self,
-                                   context: &SharedStyleContext,
+                                   context: &SharedStyleContext<<Self::ConcreteElement as Element>::Impl>,
                                    parent_style: Option<&Arc<ComputedValues>>,
                                    applicable_declarations: &[DeclarationBlock],
                                    style: &mut Option<Arc<ComputedValues>>,
@@ -434,7 +440,7 @@ trait PrivateMatchMethods<'ln>: TNode<'ln> {
     }
 
     fn update_animations_for_cascade(&self,
-                                     context: &SharedStyleContext,
+                                     context: &SharedStyleContext<<Self::ConcreteElement as Element>::Impl>,
                                      style: &mut Option<Arc<ComputedValues>>)
                                      -> bool {
         let style = match *style {
@@ -478,7 +484,8 @@ trait PrivateMatchMethods<'ln>: TNode<'ln> {
     }
 }
 
-impl<'ln, N: TNode<'ln>> PrivateMatchMethods<'ln> for N {}
+impl<'ln, N: TNode<'ln>> PrivateMatchMethods<'ln> for N
+    where <N::ConcreteElement as Element>::Impl: SelectorImplExt {}
 
 trait PrivateElementMatchMethods<'le>: TElement<'le> {
     fn share_style_with_candidate_if_possible(&self,
@@ -490,7 +497,7 @@ trait PrivateElementMatchMethods<'le>: TElement<'le> {
             Some(_) | None => return None,
         };
 
-        let parent_data: Option<&PrivateStyleData> = unsafe {
+        let parent_data: Option<&PrivateStyleData<_>> = unsafe {
             parent_node.borrow_data_unchecked().map(|d| &*d)
         };
 
@@ -512,11 +519,12 @@ trait PrivateElementMatchMethods<'le>: TElement<'le> {
 
 impl<'le, E: TElement<'le>> PrivateElementMatchMethods<'le> for E {}
 
-pub trait ElementMatchMethods<'le> : TElement<'le> {
+pub trait ElementMatchMethods<'le> : TElement<'le>
+    where Self::Impl: SelectorImplExt {
     fn match_element(&self,
-                     stylist: &Stylist,
+                     stylist: &Stylist<Self::Impl>,
                      parent_bf: Option<&BloomFilter>,
-                     applicable_declarations: &mut ApplicableDeclarations)
+                     applicable_declarations: &mut ApplicableDeclarations<Self::Impl>)
                      -> bool {
         let style_attribute = self.style_attribute().as_ref();
 
@@ -526,20 +534,16 @@ pub trait ElementMatchMethods<'le> : TElement<'le> {
                                                  style_attribute,
                                                  None,
                                                  &mut applicable_declarations.normal);
-        stylist.push_applicable_declarations(self,
-                                             parent_bf,
-                                             None,
-                                             Some(PseudoElement::Before),
-                                             &mut applicable_declarations.before);
-        stylist.push_applicable_declarations(self,
-                                             parent_bf,
-                                             None,
-                                             Some(PseudoElement::After),
-                                             &mut applicable_declarations.after);
+        Self::Impl::each_eagerly_cascaded_pseudo_element(|pseudo| {
+            stylist.push_applicable_declarations(self,
+                                                 parent_bf,
+                                                 None,
+                                                 Some(pseudo.clone()),
+                                                 applicable_declarations.per_pseudo.entry(pseudo).or_insert(vec![]));
+        });
 
         applicable_declarations.normal_shareable &&
-        applicable_declarations.before.is_empty() &&
-        applicable_declarations.after.is_empty()
+        applicable_declarations.per_pseudo.values().all(|v| v.is_empty())
     }
 
     /// Attempts to share a style with another node. This method is unsafe because it depends on
@@ -580,7 +584,8 @@ pub trait ElementMatchMethods<'le> : TElement<'le> {
     }
 }
 
-impl<'le, E: TElement<'le>> ElementMatchMethods<'le> for E {}
+impl<'le, E: TElement<'le>> ElementMatchMethods<'le> for E
+    where E::Impl: SelectorImplExt {}
 
 pub trait MatchMethods<'ln> : TNode<'ln> {
     // The below two functions are copy+paste because I can't figure out how to
@@ -632,11 +637,12 @@ pub trait MatchMethods<'ln> : TNode<'ln> {
     }
 
     unsafe fn cascade_node(&self,
-                           context: &SharedStyleContext,
+                           context: &SharedStyleContext<<Self::ConcreteElement as Element>::Impl>,
                            parent: Option<Self>,
-                           applicable_declarations: &ApplicableDeclarations,
+                           applicable_declarations: &ApplicableDeclarations<<Self::ConcreteElement as Element>::Impl>,
                            applicable_declarations_cache: &mut ApplicableDeclarationsCache,
-                           new_animations_sender: &Mutex<Sender<Animation>>) {
+                           new_animations_sender: &Mutex<Sender<Animation>>)
+                           where <Self::ConcreteElement as Element>::Impl: SelectorImplExt {
         // Get our parent's style. This must be unsafe so that we don't touch the parent's
         // borrow flags.
         //
@@ -673,28 +679,24 @@ pub trait MatchMethods<'ln> : TNode<'ln> {
                     new_animations_sender,
                     applicable_declarations.normal_shareable,
                     true);
-                if !applicable_declarations.before.is_empty() {
-                    damage = damage | self.cascade_node_pseudo_element(
-                        context,
-                        Some(data.style.as_ref().unwrap()),
-                        &*applicable_declarations.before,
-                        &mut data.before_style,
-                        applicable_declarations_cache,
-                        new_animations_sender,
-                        false,
-                        false);
-                }
-                if !applicable_declarations.after.is_empty() {
-                    damage = damage | self.cascade_node_pseudo_element(
-                        context,
-                        Some(data.style.as_ref().unwrap()),
-                        &*applicable_declarations.after,
-                        &mut data.after_style,
-                        applicable_declarations_cache,
-                        new_animations_sender,
-                        false,
-                        false);
-                }
+
+                <Self::ConcreteElement as Element>::Impl::each_eagerly_cascaded_pseudo_element(|pseudo| {
+                    let applicable_declarations_for_this_pseudo =
+                        applicable_declarations.per_pseudo.get(&pseudo).unwrap();
+
+
+                    if !applicable_declarations_for_this_pseudo.is_empty() {
+                        damage = damage | self.cascade_node_pseudo_element(
+                            context,
+                            Some(data.style.as_ref().unwrap()),
+                            &*applicable_declarations_for_this_pseudo,
+                            data.per_pseudo.entry(pseudo).or_insert(None),
+                            applicable_declarations_cache,
+                            new_animations_sender,
+                            false,
+                            false);
+                    }
+                });
             }
 
             // This method needs to borrow the data as mutable, so make sure data_ref goes out of
diff --git a/components/style/restyle_hints.rs b/components/style/restyle_hints.rs
index 1eaccff91e0..7d5a93ab157 100644
--- a/components/style/restyle_hints.rs
+++ b/components/style/restyle_hints.rs
@@ -4,10 +4,10 @@
 
 use attr::{AttrIdentifier, AttrValue};
 use element_state::*;
-use selector_impl::{NonTSPseudoClass, ServoSelectorImpl};
+use selector_impl::SelectorImplExt;
 use selectors::Element;
 use selectors::matching::matches_compound_selector;
-use selectors::parser::{AttrSelector, Combinator, CompoundSelector, NamespaceConstraint, SimpleSelector};
+use selectors::parser::{AttrSelector, Combinator, CompoundSelector, NamespaceConstraint, SelectorImpl, SimpleSelector};
 use std::clone::Clone;
 use std::sync::Arc;
 use string_cache::{Atom, Namespace};
@@ -78,12 +78,16 @@ impl ElementSnapshot {
 
 static EMPTY_SNAPSHOT: ElementSnapshot = ElementSnapshot { state: None, attrs: None };
 
-struct ElementWrapper<'a, E> where E: Element {
+struct ElementWrapper<'a, E>
+    where E: Element,
+          E::Impl: SelectorImplExt {
     element: E,
     snapshot: &'a ElementSnapshot,
 }
 
-impl<'a, E> ElementWrapper<'a, E> where E: Element {
+impl<'a, E> ElementWrapper<'a, E>
+    where E: Element,
+          E::Impl: SelectorImplExt {
     pub fn new(el: E) -> ElementWrapper<'a, E> {
         ElementWrapper { element: el, snapshot: &EMPTY_SNAPSHOT }
     }
@@ -93,16 +97,19 @@ impl<'a, E> ElementWrapper<'a, E> where E: Element {
     }
 }
 
-impl<'a, E> Element for ElementWrapper<'a, E> where E: Element<Impl=ServoSelectorImpl> {
+impl<'a, E> Element for ElementWrapper<'a, E>
+    where E: Element,
+          E::Impl: SelectorImplExt {
     type Impl = E::Impl;
 
-    fn match_non_ts_pseudo_class(&self, pseudo_class: NonTSPseudoClass) -> bool {
-        let flag = pseudo_class.state_flag();
+    fn match_non_ts_pseudo_class(&self,
+                                 pseudo_class: <Self::Impl as SelectorImpl>::NonTSPseudoClass) -> bool {
+        let flag = Self::Impl::pseudo_class_state_flag(&pseudo_class);
         if flag == ElementState::empty() {
             self.element.match_non_ts_pseudo_class(pseudo_class)
         } else {
             match self.snapshot.state {
-                Some(s) => s.contains(pseudo_class.state_flag()),
+                Some(s) => s.contains(flag),
                 None => self.element.match_non_ts_pseudo_class(pseudo_class)
             }
         }
@@ -177,14 +184,14 @@ impl<'a, E> Element for ElementWrapper<'a, E> where E: Element<Impl=ServoSelecto
     }
 }
 
-fn selector_to_state(sel: &SimpleSelector<ServoSelectorImpl>) -> ElementState {
+fn selector_to_state<Impl: SelectorImplExt>(sel: &SimpleSelector<Impl>) -> ElementState {
     match *sel {
-        SimpleSelector::NonTSPseudoClass(ref pc) => pc.state_flag(),
+        SimpleSelector::NonTSPseudoClass(ref pc) => Impl::pseudo_class_state_flag(pc),
         _ => ElementState::empty(),
     }
 }
 
-fn is_attr_selector(sel: &SimpleSelector<ServoSelectorImpl>) -> bool {
+fn is_attr_selector<Impl: SelectorImpl>(sel: &SimpleSelector<Impl>) -> bool {
     match *sel {
         SimpleSelector::ID(_) |
         SimpleSelector::Class(_) |
@@ -249,25 +256,25 @@ impl Sensitivities {
 // maximum effect that a given state or attribute change may have on the style of
 // elements in the document.
 #[derive(Debug)]
-struct Dependency {
-    selector: Arc<CompoundSelector<ServoSelectorImpl>>,
+struct Dependency<Impl: SelectorImplExt> {
+    selector: Arc<CompoundSelector<Impl>>,
     combinator: Option<Combinator>,
     sensitivities: Sensitivities,
 }
 
 #[derive(Debug)]
-pub struct DependencySet {
-    deps: Vec<Dependency>,
+pub struct DependencySet<Impl: SelectorImplExt> {
+    deps: Vec<Dependency<Impl>>,
 }
 
-impl DependencySet {
-    pub fn new() -> DependencySet {
+impl<Impl: SelectorImplExt> DependencySet<Impl> {
+    pub fn new() -> DependencySet<Impl> {
         DependencySet { deps: Vec::new() }
     }
 
     pub fn compute_hint<E>(&self, el: &E, snapshot: &ElementSnapshot, current_state: ElementState)
                           -> RestyleHint
-                          where E: Element<Impl=ServoSelectorImpl> + Clone {
+                          where E: Element<Impl=Impl> + Clone {
         let state_changes = snapshot.state.map_or(ElementState::empty(), |old_state| current_state ^ old_state);
         let attrs_changed = snapshot.attrs.is_some();
         let mut hint = RestyleHint::empty();
@@ -287,7 +294,7 @@ impl DependencySet {
         hint
     }
 
-    pub fn note_selector(&mut self, selector: Arc<CompoundSelector<ServoSelectorImpl>>) {
+    pub fn note_selector(&mut self, selector: Arc<CompoundSelector<Impl>>) {
         let mut cur = selector;
         let mut combinator: Option<Combinator> = None;
         loop {
diff --git a/components/style/selector_impl.rs b/components/style/selector_impl.rs
index 74f2bcde91b..1aa2469b6f5 100644
--- a/components/style/selector_impl.rs
+++ b/components/style/selector_impl.rs
@@ -2,15 +2,33 @@
  * 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/. */
 use element_state::ElementState;
+use selector_matching::{USER_OR_USER_AGENT_STYLESHEETS, QUIRKS_MODE_STYLESHEET};
+use selectors::Element;
 use selectors::parser::{ParserContext, SelectorImpl};
+use stylesheets::Stylesheet;
 
-#[derive(Clone, Debug, PartialEq, HeapSizeOf)]
+pub trait ElementExt: Element {
+    fn is_link(&self) -> bool;
+}
+
+pub trait SelectorImplExt : SelectorImpl + Sized {
+    fn each_eagerly_cascaded_pseudo_element<F>(mut fun: F)
+        where F: FnMut(<Self as SelectorImpl>::PseudoElement);
+
+    fn pseudo_class_state_flag(pc: &Self::NonTSPseudoClass) -> ElementState;
+
+    fn get_user_or_user_agent_stylesheets() -> &'static [Stylesheet<Self>];
+
+    fn get_quirks_mode_stylesheet() -> &'static Stylesheet<Self>;
+}
+
+#[derive(Clone, Debug, PartialEq, Eq, HeapSizeOf, Hash)]
 pub enum PseudoElement {
     Before,
     After,
 }
 
-#[derive(Clone, Debug, PartialEq, HeapSizeOf)]
+#[derive(Clone, Debug, PartialEq, Eq, HeapSizeOf, Hash)]
 pub enum NonTSPseudoClass {
     AnyLink,
     Link,
@@ -82,10 +100,42 @@ impl SelectorImpl for ServoSelectorImpl {
     fn parse_pseudo_element(_context: &ParserContext,
                             name: &str) -> Result<PseudoElement, ()> {
         use self::PseudoElement::*;
-        match_ignore_ascii_case! { name,
-            "before" => Ok(Before),
-            "after" => Ok(After),
-            _ => Err(())
-        }
+        let pseudo_element = match_ignore_ascii_case! { name,
+            "before" => Before,
+            "after" => After,
+            _ => return Err(())
+        };
+
+        Ok(pseudo_element)
+    }
+}
+
+impl<E: Element<Impl=ServoSelectorImpl>> ElementExt for E {
+    fn is_link(&self) -> bool {
+        self.match_non_ts_pseudo_class(NonTSPseudoClass::AnyLink)
+    }
+}
+
+impl SelectorImplExt for ServoSelectorImpl {
+    #[inline]
+    fn each_eagerly_cascaded_pseudo_element<F>(mut fun: F)
+        where F: FnMut(PseudoElement) {
+        fun(PseudoElement::Before);
+        fun(PseudoElement::After);
+    }
+
+    #[inline]
+    fn pseudo_class_state_flag(pc: &NonTSPseudoClass) -> ElementState {
+        pc.state_flag()
+    }
+
+    #[inline]
+    fn get_user_or_user_agent_stylesheets() -> &'static [Stylesheet<Self>] {
+        &*USER_OR_USER_AGENT_STYLESHEETS
+    }
+
+    #[inline]
+    fn get_quirks_mode_stylesheet() -> &'static Stylesheet<Self> {
+        &*QUIRKS_MODE_STYLESHEET
     }
 }
diff --git a/components/style/selector_matching.rs b/components/style/selector_matching.rs
index 6fe34195b90..5fa0d3ab1f3 100644
--- a/components/style/selector_matching.rs
+++ b/components/style/selector_matching.rs
@@ -11,12 +11,14 @@ use error_reporting::{ParseErrorReporter, StdoutErrorReporter};
 use media_queries::{Device, MediaType};
 use properties::{PropertyDeclaration, PropertyDeclarationBlock};
 use restyle_hints::{ElementSnapshot, RestyleHint, DependencySet};
-use selector_impl::{PseudoElement, ServoSelectorImpl};
+use selector_impl::{SelectorImplExt, ServoSelectorImpl};
 use selectors::Element;
 use selectors::bloom::BloomFilter;
 use selectors::matching::DeclarationBlock as GenericDeclarationBlock;
 use selectors::matching::{Rule, SelectorMap};
+use selectors::parser::SelectorImpl;
 use smallvec::VecLike;
+use std::collections::HashMap;
 use std::process;
 use std::sync::Arc;
 use style_traits::viewport::ViewportConstraints;
@@ -30,7 +32,7 @@ use viewport::{MaybeNew, ViewportRuleCascade};
 pub type DeclarationBlock = GenericDeclarationBlock<Vec<PropertyDeclaration>>;
 
 lazy_static! {
-    pub static ref USER_OR_USER_AGENT_STYLESHEETS: Vec<Stylesheet> = {
+    pub static ref USER_OR_USER_AGENT_STYLESHEETS: Vec<Stylesheet<ServoSelectorImpl>> = {
         let mut stylesheets = vec!();
         // FIXME: presentational-hints.css should be at author origin with zero specificity.
         //        (Does it make a difference?)
@@ -61,7 +63,7 @@ lazy_static! {
 }
 
 lazy_static! {
-    pub static ref QUIRKS_MODE_STYLESHEET: Stylesheet = {
+    pub static ref QUIRKS_MODE_STYLESHEET: Stylesheet<ServoSelectorImpl> = {
         match read_resource_file(&["quirks-mode.css"]) {
             Ok(res) => {
                 Stylesheet::from_bytes(
@@ -80,7 +82,7 @@ lazy_static! {
     };
 }
 
-pub struct Stylist {
+pub struct Stylist<Impl: SelectorImplExt> {
     // Device that the stylist is currently evaluating against.
     pub device: Device,
 
@@ -95,50 +97,55 @@ pub struct Stylist {
 
     // The current selector maps, after evaluating media
     // rules against the current device.
-    element_map: PerPseudoElementSelectorMap,
-    before_map: PerPseudoElementSelectorMap,
-    after_map: PerPseudoElementSelectorMap,
+    element_map: PerPseudoElementSelectorMap<Impl>,
+    pseudos_map: HashMap<Impl::PseudoElement, PerPseudoElementSelectorMap<Impl>>,
     rules_source_order: usize,
 
     // Selector dependencies used to compute restyle hints.
-    state_deps: DependencySet,
+    state_deps: DependencySet<Impl>,
 }
 
-impl Stylist {
+impl<Impl: SelectorImplExt> Stylist<Impl> {
     #[inline]
-    pub fn new(device: Device) -> Stylist {
-        Stylist {
+    pub fn new(device: Device) -> Stylist<Impl> {
+        let mut stylist = Stylist {
             viewport_constraints: None,
             device: device,
             is_device_dirty: true,
             quirks_mode: false,
 
             element_map: PerPseudoElementSelectorMap::new(),
-            before_map: PerPseudoElementSelectorMap::new(),
-            after_map: PerPseudoElementSelectorMap::new(),
+            pseudos_map: HashMap::new(),
             rules_source_order: 0,
             state_deps: DependencySet::new(),
-        }
+        };
+
+        Impl::each_eagerly_cascaded_pseudo_element(|pseudo| {
+            stylist.pseudos_map.insert(pseudo, PerPseudoElementSelectorMap::new());
+        });
+
         // FIXME: Add iso-8859-9.css when the document’s encoding is ISO-8859-8.
+
+        stylist
     }
 
-    pub fn update(&mut self, doc_stylesheets: &[Arc<Stylesheet>],
-                      stylesheets_changed: bool) -> bool {
+    pub fn update(&mut self, doc_stylesheets: &[Arc<Stylesheet<Impl>>],
+                  stylesheets_changed: bool) -> bool
+                  where Impl: 'static {
         if !(self.is_device_dirty || stylesheets_changed) {
             return false;
         }
         self.element_map = PerPseudoElementSelectorMap::new();
-        self.before_map = PerPseudoElementSelectorMap::new();
-        self.after_map = PerPseudoElementSelectorMap::new();
+        self.pseudos_map = HashMap::new();
         self.rules_source_order = 0;
         self.state_deps.clear();
 
-        for ref stylesheet in USER_OR_USER_AGENT_STYLESHEETS.iter() {
+        for ref stylesheet in Impl::get_user_or_user_agent_stylesheets().iter() {
             self.add_stylesheet(&stylesheet);
         }
 
         if self.quirks_mode {
-            self.add_stylesheet(&QUIRKS_MODE_STYLESHEET);
+            self.add_stylesheet(&Impl::get_quirks_mode_stylesheet());
         }
 
         for ref stylesheet in doc_stylesheets.iter() {
@@ -149,28 +156,12 @@ impl Stylist {
         true
     }
 
-    fn add_stylesheet(&mut self, stylesheet: &Stylesheet) {
+    fn add_stylesheet(&mut self, stylesheet: &Stylesheet<Impl>) {
         let device = &self.device;
         if !stylesheet.is_effective_for_device(device) {
             return;
         }
-        let (mut element_map, mut before_map, mut after_map) = match stylesheet.origin {
-            Origin::UserAgent => (
-                &mut self.element_map.user_agent,
-                &mut self.before_map.user_agent,
-                &mut self.after_map.user_agent,
-            ),
-            Origin::Author => (
-                &mut self.element_map.author,
-                &mut self.before_map.author,
-                &mut self.after_map.author,
-            ),
-            Origin::User => (
-                &mut self.element_map.user,
-                &mut self.before_map.user,
-                &mut self.after_map.user,
-            ),
-        };
+
         let mut rules_source_order = self.rules_source_order;
 
         // Take apart the StyleRule into individual Rules and insert
@@ -179,11 +170,14 @@ impl Stylist {
             ($style_rule: ident, $priority: ident) => {
                 if $style_rule.declarations.$priority.len() > 0 {
                     for selector in &$style_rule.selectors {
-                        let map = match selector.pseudo_element {
-                            None => &mut element_map,
-                            Some(PseudoElement::Before) => &mut before_map,
-                            Some(PseudoElement::After) => &mut after_map,
+                        let map = if let Some(ref pseudo) = selector.pseudo_element {
+                            self.pseudos_map.entry(pseudo.clone())
+                                            .or_insert_with(PerPseudoElementSelectorMap::new)
+                                            .borrow_for_origin(&stylesheet.origin)
+                        } else {
+                            self.element_map.borrow_for_origin(&stylesheet.origin)
                         };
+
                         map.$priority.insert(Rule {
                                 selector: selector.compound_selectors.clone(),
                                 declarations: DeclarationBlock {
@@ -216,11 +210,11 @@ impl Stylist {
                                    // more expensive than getting it directly from the caller.
                                    current_state: ElementState)
                                    -> RestyleHint
-                                   where E: Element<Impl=ServoSelectorImpl> + Clone {
+                                   where E: Element<Impl=Impl> + Clone {
         self.state_deps.compute_hint(element, snapshot, current_state)
     }
 
-    pub fn set_device(&mut self, mut device: Device, stylesheets: &[Arc<Stylesheet>]) {
+    pub fn set_device(&mut self, mut device: Device, stylesheets: &[Arc<Stylesheet<Impl>>]) {
         let cascaded_rule = stylesheets.iter()
             .flat_map(|s| s.effective_rules(&self.device).viewport())
             .cascade();
@@ -256,19 +250,18 @@ impl Stylist {
                                         element: &E,
                                         parent_bf: Option<&BloomFilter>,
                                         style_attribute: Option<&PropertyDeclarationBlock>,
-                                        pseudo_element: Option<PseudoElement>,
+                                        pseudo_element: Option<Impl::PseudoElement>,
                                         applicable_declarations: &mut V)
                                         -> bool
-                                        where E: Element + TElement<'le>,
+                                        where E: Element<Impl=Impl> + TElement<'le>,
                                               V: VecLike<DeclarationBlock> {
         assert!(!self.is_device_dirty);
         assert!(style_attribute.is_none() || pseudo_element.is_none(),
                 "Style attributes do not apply to pseudo-elements");
 
         let map = match pseudo_element {
+            Some(ref pseudo) => self.pseudos_map.get(pseudo).unwrap(),
             None => &self.element_map,
-            Some(PseudoElement::Before) => &self.before_map,
-            Some(PseudoElement::After) => &self.after_map,
         };
 
         let mut shareable = true;
@@ -336,14 +329,14 @@ impl Stylist {
     }
 }
 
-struct PerOriginSelectorMap {
-    normal: SelectorMap<Vec<PropertyDeclaration>, ServoSelectorImpl>,
-    important: SelectorMap<Vec<PropertyDeclaration>, ServoSelectorImpl>,
+struct PerOriginSelectorMap<Impl: SelectorImpl> {
+    normal: SelectorMap<Vec<PropertyDeclaration>, Impl>,
+    important: SelectorMap<Vec<PropertyDeclaration>, Impl>,
 }
 
-impl PerOriginSelectorMap {
+impl<Impl: SelectorImpl> PerOriginSelectorMap<Impl> {
     #[inline]
-    fn new() -> PerOriginSelectorMap {
+    fn new() -> PerOriginSelectorMap<Impl> {
         PerOriginSelectorMap {
             normal: SelectorMap::new(),
             important: SelectorMap::new(),
@@ -351,19 +344,28 @@ impl PerOriginSelectorMap {
     }
 }
 
-struct PerPseudoElementSelectorMap {
-    user_agent: PerOriginSelectorMap,
-    author: PerOriginSelectorMap,
-    user: PerOriginSelectorMap,
+struct PerPseudoElementSelectorMap<Impl: SelectorImpl> {
+    user_agent: PerOriginSelectorMap<Impl>,
+    author: PerOriginSelectorMap<Impl>,
+    user: PerOriginSelectorMap<Impl>,
 }
 
-impl PerPseudoElementSelectorMap {
+impl<Impl: SelectorImpl> PerPseudoElementSelectorMap<Impl> {
     #[inline]
-    fn new() -> PerPseudoElementSelectorMap {
+    fn new() -> PerPseudoElementSelectorMap<Impl> {
         PerPseudoElementSelectorMap {
             user_agent: PerOriginSelectorMap::new(),
             author: PerOriginSelectorMap::new(),
             user: PerOriginSelectorMap::new(),
         }
     }
+
+    #[inline]
+    fn borrow_for_origin(&mut self, origin: &Origin) -> &mut PerOriginSelectorMap<Impl> {
+        match *origin {
+            Origin::UserAgent => &mut self.user_agent,
+            Origin::Author => &mut self.author,
+            Origin::User => &mut self.user,
+        }
+    }
 }
diff --git a/components/style/servo.rs b/components/style/servo.rs
new file mode 100644
index 00000000000..56aef8f6210
--- /dev/null
+++ b/components/style/servo.rs
@@ -0,0 +1,15 @@
+/* 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/. */
+use context;
+use data;
+use selector_impl::ServoSelectorImpl;
+use selector_matching;
+use stylesheets;
+
+/// Concrete types for servo Style implementation
+pub type Stylesheet = stylesheets::Stylesheet<ServoSelectorImpl>;
+pub type PrivateStyleData = data::PrivateStyleData<ServoSelectorImpl>;
+pub type Stylist = selector_matching::Stylist<ServoSelectorImpl>;
+pub type StylistWrapper = context::StylistWrapper<ServoSelectorImpl>;
+pub type SharedStyleContext = context::SharedStyleContext<ServoSelectorImpl>;
diff --git a/components/style/stylesheets.rs b/components/style/stylesheets.rs
index bc4008040c2..1e5d641ff02 100644
--- a/components/style/stylesheets.rs
+++ b/components/style/stylesheets.rs
@@ -10,12 +10,12 @@ use font_face::{FontFaceRule, parse_font_face_block};
 use media_queries::{Device, MediaQueryList, parse_media_query_list};
 use parser::{ParserContext, log_css_error};
 use properties::{PropertyDeclarationBlock, parse_property_declaration_list};
-use selector_impl::ServoSelectorImpl;
-use selectors::parser::{Selector, parse_selector_list};
+use selectors::parser::{Selector, SelectorImpl, parse_selector_list};
 use smallvec::SmallVec;
 use std::ascii::AsciiExt;
 use std::cell::Cell;
 use std::iter::Iterator;
+use std::marker::PhantomData;
 use std::slice;
 use string_cache::{Atom, Namespace};
 use url::Url;
@@ -39,10 +39,10 @@ pub enum Origin {
 
 
 #[derive(Debug, HeapSizeOf, PartialEq)]
-pub struct Stylesheet {
+pub struct Stylesheet<Impl: SelectorImpl> {
     /// List of rules in the order they were found (important for
     /// cascading order)
-    pub rules: Vec<CSSRule>,
+    pub rules: Vec<CSSRule<Impl>>,
     /// List of media associated with the Stylesheet, if any.
     pub media: Option<MediaQueryList>,
     pub origin: Origin,
@@ -50,22 +50,22 @@ pub struct Stylesheet {
 
 
 #[derive(Debug, HeapSizeOf, PartialEq)]
-pub enum CSSRule {
+pub enum CSSRule<Impl: SelectorImpl> {
     Charset(String),
     Namespace(Option<String>, Namespace),
-    Style(StyleRule),
-    Media(MediaRule),
+    Style(StyleRule<Impl>),
+    Media(MediaRule<Impl>),
     FontFace(FontFaceRule),
     Viewport(ViewportRule),
 }
 
 #[derive(Debug, HeapSizeOf, PartialEq)]
-pub struct MediaRule {
+pub struct MediaRule<Impl: SelectorImpl> {
     pub media_queries: MediaQueryList,
-    pub rules: Vec<CSSRule>,
+    pub rules: Vec<CSSRule<Impl>>,
 }
 
-impl MediaRule {
+impl<Impl: SelectorImpl> MediaRule<Impl> {
     #[inline]
     pub fn evaluate(&self, device: &Device) -> bool {
         self.media_queries.evaluate(device)
@@ -73,17 +73,17 @@ impl MediaRule {
 }
 
 #[derive(Debug, HeapSizeOf, PartialEq)]
-pub struct StyleRule {
-    pub selectors: Vec<Selector<ServoSelectorImpl>>,
+pub struct StyleRule<Impl: SelectorImpl> {
+    pub selectors: Vec<Selector<Impl>>,
     pub declarations: PropertyDeclarationBlock,
 }
 
 
-impl Stylesheet {
+impl<Impl: SelectorImpl> Stylesheet<Impl> {
     pub fn from_bytes_iter<I: Iterator<Item=Vec<u8>>>(
             input: I, base_url: Url, protocol_encoding_label: Option<&str>,
             environment_encoding: Option<EncodingRef>, origin: Origin,
-            error_reporter: Box<ParseErrorReporter + Send>) -> Stylesheet {
+            error_reporter: Box<ParseErrorReporter + Send>) -> Stylesheet<Impl> {
         let mut bytes = vec![];
         // TODO: incremental decoding and tokenization/parsing
         for chunk in input {
@@ -98,7 +98,7 @@ impl Stylesheet {
                       protocol_encoding_label: Option<&str>,
                       environment_encoding: Option<EncodingRef>,
                       origin: Origin, error_reporter: Box<ParseErrorReporter + Send>)
-                      -> Stylesheet {
+                      -> Stylesheet<Impl> {
         // TODO: bytes.as_slice could be bytes.container_as_bytes()
         let (string, _) = decode_stylesheet_bytes(
             bytes, protocol_encoding_label, environment_encoding);
@@ -106,10 +106,11 @@ impl Stylesheet {
     }
 
     pub fn from_str(css: &str, base_url: Url, origin: Origin,
-                    error_reporter: Box<ParseErrorReporter + Send>) -> Stylesheet {
+                    error_reporter: Box<ParseErrorReporter + Send>) -> Stylesheet<Impl> {
         let rule_parser = TopLevelRuleParser {
             context: ParserContext::new(origin, &base_url, error_reporter.clone()),
             state: Cell::new(State::Start),
+            _impl: PhantomData,
         };
         let mut input = Parser::new(css);
         let mut iter = RuleListParser::new_for_stylesheet(&mut input, rule_parser);
@@ -158,7 +159,7 @@ impl Stylesheet {
 
     /// Return an iterator over all the rules within the style-sheet.
     #[inline]
-    pub fn rules(&self) -> Rules {
+    pub fn rules(&self) -> Rules<Impl> {
         Rules::new(self.rules.iter(), None)
     }
 
@@ -169,7 +170,7 @@ impl Stylesheet {
     /// nested rules will be skipped. Use `rules` if all rules need to be
     /// examined.
     #[inline]
-    pub fn effective_rules<'a>(&'a self, device: &'a Device) -> Rules<'a> {
+    pub fn effective_rules<'a>(&'a self, device: &'a Device) -> Rules<'a, Impl> {
         Rules::new(self.rules.iter(), Some(device))
     }
 }
@@ -178,25 +179,25 @@ impl Stylesheet {
 ///
 /// The iteration order is pre-order. Specifically, this implies that a
 /// conditional group rule will come before its nested rules.
-pub struct Rules<'a> {
+pub struct Rules<'a, Impl: SelectorImpl + 'a> {
     // 2 because normal case is likely to be just one level of nesting (@media)
-    stack: SmallVec<[slice::Iter<'a, CSSRule>; 2]>,
+    stack: SmallVec<[slice::Iter<'a, CSSRule<Impl>>; 2]>,
     device: Option<&'a Device>
 }
 
-impl<'a> Rules<'a> {
-    fn new(iter: slice::Iter<'a, CSSRule>, device: Option<&'a Device>) -> Rules<'a> {
-        let mut stack: SmallVec<[slice::Iter<'a, CSSRule>; 2]> = SmallVec::new();
+impl<'a, Impl: SelectorImpl + 'a> Rules<'a, Impl> {
+    fn new(iter: slice::Iter<'a, CSSRule<Impl>>, device: Option<&'a Device>) -> Rules<'a, Impl> {
+        let mut stack: SmallVec<[slice::Iter<'a, CSSRule<Impl>>; 2]> = SmallVec::new();
         stack.push(iter);
 
         Rules { stack: stack, device: device }
     }
 }
 
-impl<'a> Iterator for Rules<'a> {
-    type Item = &'a CSSRule;
+impl<'a, Impl: SelectorImpl + 'a> Iterator for Rules<'a, Impl> {
+    type Item = &'a CSSRule<Impl>;
 
-    fn next(&mut self) -> Option<&'a CSSRule> {
+    fn next(&mut self) -> Option<&'a CSSRule<Impl>> {
         while !self.stack.is_empty() {
             let top = self.stack.len() - 1;
             while let Some(rule) = self.stack[top].next() {
@@ -231,6 +232,7 @@ impl<'a> Iterator for Rules<'a> {
 pub mod rule_filter {
     //! Specific `CSSRule` variant iterators.
 
+    use selectors::parser::SelectorImpl;
     use std::marker::PhantomData;
     use super::super::font_face::FontFaceRule;
     use super::super::viewport::ViewportRule;
@@ -245,7 +247,8 @@ pub mod rule_filter {
                 _lifetime: PhantomData<&'a ()>
             }
 
-            impl<'a, I> $variant<'a, I> where I: Iterator<Item=&'a CSSRule> {
+            impl<'a, I, Impl: SelectorImpl + 'a> $variant<'a, I>
+                where I: Iterator<Item=&'a CSSRule<Impl>> {
                 pub fn new(iter: I) -> $variant<'a, I> {
                     $variant {
                         iter: iter,
@@ -254,7 +257,8 @@ pub mod rule_filter {
                 }
             }
 
-            impl<'a, I> Iterator for $variant<'a, I> where I: Iterator<Item=&'a CSSRule> {
+            impl<'a, I, Impl: SelectorImpl + 'a> Iterator for $variant<'a, I>
+                where I: Iterator<Item=&'a CSSRule<Impl>> {
                 type Item = &'a $value;
 
                 fn next(&mut self) -> Option<&'a $value> {
@@ -275,14 +279,14 @@ pub mod rule_filter {
         }
     }
 
+    rule_filter!(Media -> MediaRule<Impl>);
+    rule_filter!(Style -> StyleRule<Impl>);
     rule_filter!(FontFace -> FontFaceRule);
-    rule_filter!(Media -> MediaRule);
-    rule_filter!(Style -> StyleRule);
     rule_filter!(Viewport -> ViewportRule);
 }
 
 /// Extension methods for `CSSRule` iterators.
-pub trait CSSRuleIteratorExt<'a>: Iterator<Item=&'a CSSRule> + Sized {
+pub trait CSSRuleIteratorExt<'a, Impl: SelectorImpl + 'a>: Iterator<Item=&'a CSSRule<Impl>> + Sized {
     /// Yield only @font-face rules.
     fn font_face(self) -> rule_filter::FontFace<'a, Self>;
 
@@ -296,7 +300,7 @@ pub trait CSSRuleIteratorExt<'a>: Iterator<Item=&'a CSSRule> + Sized {
     fn viewport(self) -> rule_filter::Viewport<'a, Self>;
 }
 
-impl<'a, I> CSSRuleIteratorExt<'a> for I where I: Iterator<Item=&'a CSSRule> {
+impl<'a, I, Impl: SelectorImpl + 'a> CSSRuleIteratorExt<'a, Impl> for I where I: Iterator<Item=&'a CSSRule<Impl>> {
     #[inline]
     fn font_face(self) -> rule_filter::FontFace<'a, I> {
         rule_filter::FontFace::new(self)
@@ -318,8 +322,12 @@ impl<'a, I> CSSRuleIteratorExt<'a> for I where I: Iterator<Item=&'a CSSRule> {
     }
 }
 
-fn parse_nested_rules(context: &ParserContext, input: &mut Parser) -> Vec<CSSRule> {
-    let mut iter = RuleListParser::new_for_nested_rule(input, NestedRuleParser { context: context });
+fn parse_nested_rules<Impl: SelectorImpl>(context: &ParserContext, input: &mut Parser) -> Vec<CSSRule<Impl>> {
+    let mut iter = RuleListParser::new_for_nested_rule(input,
+                                                       NestedRuleParser {
+                                                           context: context,
+                                                           _impl: PhantomData
+                                                       });
     let mut rules = Vec::new();
     while let Some(result) = iter.next() {
         match result {
@@ -335,9 +343,10 @@ fn parse_nested_rules(context: &ParserContext, input: &mut Parser) -> Vec<CSSRul
 }
 
 
-struct TopLevelRuleParser<'a> {
+struct TopLevelRuleParser<'a, Impl: SelectorImpl> {
     context: ParserContext<'a>,
     state: Cell<State>,
+    _impl: PhantomData<Impl>
 }
 
 #[derive(Eq, PartialEq, Ord, PartialOrd, Copy, Clone)]
@@ -356,12 +365,12 @@ enum AtRulePrelude {
 }
 
 
-impl<'a> AtRuleParser for TopLevelRuleParser<'a> {
+impl<'a, Impl: SelectorImpl> AtRuleParser for TopLevelRuleParser<'a, Impl> {
     type Prelude = AtRulePrelude;
-    type AtRule = CSSRule;
+    type AtRule = CSSRule<Impl>;
 
     fn parse_prelude(&self, name: &str, input: &mut Parser)
-                     -> Result<AtRuleType<AtRulePrelude, CSSRule>, ()> {
+                     -> Result<AtRuleType<AtRulePrelude, CSSRule<Impl>>, ()> {
         match_ignore_ascii_case! { name,
             "charset" => {
                 if self.state.get() <= State::Start {
@@ -397,45 +406,46 @@ impl<'a> AtRuleParser for TopLevelRuleParser<'a> {
         }
 
         self.state.set(State::Body);
-        AtRuleParser::parse_prelude(&NestedRuleParser { context: &self.context }, name, input)
+        AtRuleParser::parse_prelude(&NestedRuleParser { context: &self.context, _impl: PhantomData }, name, input)
     }
 
     #[inline]
-    fn parse_block(&self, prelude: AtRulePrelude, input: &mut Parser) -> Result<CSSRule, ()> {
-        AtRuleParser::parse_block(&NestedRuleParser { context: &self.context }, prelude, input)
+    fn parse_block(&self, prelude: AtRulePrelude, input: &mut Parser) -> Result<CSSRule<Impl>, ()> {
+        AtRuleParser::parse_block(&NestedRuleParser { context: &self.context, _impl: PhantomData }, prelude, input)
     }
 }
 
 
-impl<'a> QualifiedRuleParser for TopLevelRuleParser<'a> {
-    type Prelude = Vec<Selector<ServoSelectorImpl>>;
-    type QualifiedRule = CSSRule;
+impl<'a, Impl: SelectorImpl> QualifiedRuleParser for TopLevelRuleParser<'a, Impl> {
+    type Prelude = Vec<Selector<Impl>>;
+    type QualifiedRule = CSSRule<Impl>;
 
     #[inline]
-    fn parse_prelude(&self, input: &mut Parser) -> Result<Vec<Selector<ServoSelectorImpl>>, ()> {
+    fn parse_prelude(&self, input: &mut Parser) -> Result<Vec<Selector<Impl>>, ()> {
         self.state.set(State::Body);
-        QualifiedRuleParser::parse_prelude(&NestedRuleParser { context: &self.context }, input)
+        QualifiedRuleParser::parse_prelude(&NestedRuleParser { context: &self.context, _impl: PhantomData }, input)
     }
 
     #[inline]
-    fn parse_block(&self, prelude: Vec<Selector<ServoSelectorImpl>>, input: &mut Parser) -> Result<CSSRule, ()> {
-        QualifiedRuleParser::parse_block(&NestedRuleParser { context: &self.context },
+    fn parse_block(&self, prelude: Vec<Selector<Impl>>, input: &mut Parser) -> Result<CSSRule<Impl>, ()> {
+        QualifiedRuleParser::parse_block(&NestedRuleParser { context: &self.context, _impl: PhantomData },
                                          prelude, input)
     }
 }
 
 
-struct NestedRuleParser<'a, 'b: 'a> {
+struct NestedRuleParser<'a, 'b: 'a, Impl: SelectorImpl> {
     context: &'a ParserContext<'b>,
+    _impl: PhantomData<Impl>,
 }
 
 
-impl<'a, 'b> AtRuleParser for NestedRuleParser<'a, 'b> {
+impl<'a, 'b, Impl: SelectorImpl> AtRuleParser for NestedRuleParser<'a, 'b, Impl> {
     type Prelude = AtRulePrelude;
-    type AtRule = CSSRule;
+    type AtRule = CSSRule<Impl>;
 
     fn parse_prelude(&self, name: &str, input: &mut Parser)
-                     -> Result<AtRuleType<AtRulePrelude, CSSRule>, ()> {
+                     -> Result<AtRuleType<AtRulePrelude, CSSRule<Impl>>, ()> {
         match_ignore_ascii_case! { name,
             "media" => {
                 let media_queries = parse_media_query_list(input);
@@ -455,7 +465,7 @@ impl<'a, 'b> AtRuleParser for NestedRuleParser<'a, 'b> {
         }
     }
 
-    fn parse_block(&self, prelude: AtRulePrelude, input: &mut Parser) -> Result<CSSRule, ()> {
+    fn parse_block(&self, prelude: AtRulePrelude, input: &mut Parser) -> Result<CSSRule<Impl>, ()> {
         match prelude {
             AtRulePrelude::FontFace => {
                 parse_font_face_block(self.context, input).map(CSSRule::FontFace)
@@ -474,15 +484,15 @@ impl<'a, 'b> AtRuleParser for NestedRuleParser<'a, 'b> {
 }
 
 
-impl<'a, 'b> QualifiedRuleParser for NestedRuleParser<'a, 'b> {
-    type Prelude = Vec<Selector<ServoSelectorImpl>>;
-    type QualifiedRule = CSSRule;
+impl<'a, 'b, Impl: SelectorImpl> QualifiedRuleParser for NestedRuleParser<'a, 'b, Impl> {
+    type Prelude = Vec<Selector<Impl>>;
+    type QualifiedRule = CSSRule<Impl>;
 
-    fn parse_prelude(&self, input: &mut Parser) -> Result<Vec<Selector<ServoSelectorImpl>>, ()> {
+    fn parse_prelude(&self, input: &mut Parser) -> Result<Vec<Selector<Impl>>, ()> {
         parse_selector_list(&self.context.selector_context, input)
     }
 
-    fn parse_block(&self, prelude: Vec<Selector<ServoSelectorImpl>>, input: &mut Parser) -> Result<CSSRule, ()> {
+    fn parse_block(&self, prelude: Vec<Selector<Impl>>, input: &mut Parser) -> Result<CSSRule<Impl>, ()> {
         Ok(CSSRule::Style(StyleRule {
             selectors: prelude,
             declarations: parse_property_declaration_list(self.context, input)
diff --git a/components/style/traversal.rs b/components/style/traversal.rs
index 781c99f619e..78f7cc46308 100644
--- a/components/style/traversal.rs
+++ b/components/style/traversal.rs
@@ -5,6 +5,8 @@
 use context::{SharedStyleContext, StyleContext};
 use dom::{OpaqueNode, TNode, TRestyleDamage, UnsafeNode};
 use matching::{ApplicableDeclarations, ElementMatchMethods, MatchMethods, StyleSharingResult};
+use selector_impl::SelectorImplExt;
+use selectors::Element;
 use selectors::bloom::BloomFilter;
 use std::cell::RefCell;
 use util::opts;
@@ -41,11 +43,11 @@ thread_local!(
 ///
 /// If one does not exist, a new one will be made for you. If it is out of date,
 /// it will be cleared and reused.
-fn take_thread_local_bloom_filter<'ln, N>(parent_node: Option<N>,
-                                        root: OpaqueNode,
-                                        context: &SharedStyleContext)
-                                        -> Box<BloomFilter>
-                                        where N: TNode<'ln> {
+fn take_thread_local_bloom_filter<'ln, N, Impl: SelectorImplExt>(parent_node: Option<N>,
+                                                              root: OpaqueNode,
+                                                              context: &SharedStyleContext<Impl>)
+                                                              -> Box<BloomFilter>
+                                                              where N: TNode<'ln> {
     STYLE_BLOOM.with(|style_bloom| {
         match (parent_node, style_bloom.borrow_mut().take()) {
             // Root node. Needs new bloom filter.
@@ -77,9 +79,9 @@ fn take_thread_local_bloom_filter<'ln, N>(parent_node: Option<N>,
     })
 }
 
-pub fn put_thread_local_bloom_filter(bf: Box<BloomFilter>,
-                               unsafe_node: &UnsafeNode,
-                               context: &SharedStyleContext) {
+pub fn put_thread_local_bloom_filter<Impl: SelectorImplExt>(bf: Box<BloomFilter>,
+                                                            unsafe_node: &UnsafeNode,
+                                                            context: &SharedStyleContext<Impl>) {
     STYLE_BLOOM.with(move |style_bloom| {
         assert!(style_bloom.borrow().is_none(),
                 "Putting into a never-taken thread-local bloom filter");
@@ -117,7 +119,12 @@ pub trait DomTraversalContext<'ln, N: TNode<'ln>>  {
 /// layout computation. This computes the styles applied to each node.
 #[inline]
 #[allow(unsafe_code)]
-pub fn recalc_style_at<'a, 'ln, N: TNode<'ln>, C: StyleContext<'a>> (context: &'a C, root: OpaqueNode, node: N) {
+pub fn recalc_style_at<'a, 'ln, N, C>(context: &'a C,
+                                      root: OpaqueNode,
+                                      node: N)
+    where N: TNode<'ln>,
+          C: StyleContext<'a, <N::ConcreteElement as Element>::Impl>,
+          <N::ConcreteElement as Element>::Impl: SelectorImplExt + 'a {
     // Initialize layout data.
     //
     // FIXME(pcwalton): Stop allocating here. Ideally this should just be done by the HTML
diff --git a/components/style_traits/Cargo.toml b/components/style_traits/Cargo.toml
index 45c5b5c9eaa..17dc272d4ca 100644
--- a/components/style_traits/Cargo.toml
+++ b/components/style_traits/Cargo.toml
@@ -22,7 +22,7 @@ lazy_static = "0.1.10"
 log = "0.3"
 num = "0.1.24"
 rustc-serialize = "0.3"
-selectors = {version = "0.4.2", features = ["heap_size"]}
+selectors = {version = "0.5", features = ["heap_size"]}
 serde = "0.6"
 serde_macros = "0.6"
 url = {version = "0.5.5", features = ["heap_size"]}
diff --git a/components/util/Cargo.toml b/components/util/Cargo.toml
index 34409a5fe9a..b6f8fd15640 100644
--- a/components/util/Cargo.toml
+++ b/components/util/Cargo.toml
@@ -41,7 +41,7 @@ num = "0.1.24"
 num_cpus = "0.2.2"
 rand = "0.3"
 rustc-serialize = "0.3"
-selectors = {version = "0.4.2", features = ["heap_size"]}
+selectors = {version = "0.5", features = ["heap_size"]}
 serde = "0.6"
 serde_macros = "0.6"
 smallvec = "0.1"