Move rust-selectors in-tree.

16 files changed, 2616 insertions, 18 deletions

diff --git a/Cargo.lock b/Cargo.lock
index c9b451b143d..d4fc618a95b 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -934,7 +934,7 @@ dependencies = [
  "log 0.3.6 (registry+https://github.com/rust-lang/crates.io-index)",
  "num_cpus 1.2.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "parking_lot 0.3.7 (registry+https://github.com/rust-lang/crates.io-index)",
- "selectors 0.17.0 (registry+https://github.com/rust-lang/crates.io-index)",
+ "selectors 0.17.0",
  "servo_url 0.0.1",
  "style 0.0.1",
  "style_traits 0.0.1",
@@ -1355,7 +1355,7 @@ dependencies = [
  "rayon 0.6.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "script_layout_interface 0.0.1",
  "script_traits 0.0.1",
- "selectors 0.17.0 (registry+https://github.com/rust-lang/crates.io-index)",
+ "selectors 0.17.0",
  "serde 0.8.20 (registry+https://github.com/rust-lang/crates.io-index)",
  "serde_derive 0.8.23 (registry+https://github.com/rust-lang/crates.io-index)",
  "serde_json 0.8.4 (registry+https://github.com/rust-lang/crates.io-index)",
@@ -1401,7 +1401,7 @@ dependencies = [
  "script 0.0.1",
  "script_layout_interface 0.0.1",
  "script_traits 0.0.1",
- "selectors 0.17.0 (registry+https://github.com/rust-lang/crates.io-index)",
+ "selectors 0.17.0",
  "serde_derive 0.8.23 (registry+https://github.com/rust-lang/crates.io-index)",
  "serde_json 0.8.4 (registry+https://github.com/rust-lang/crates.io-index)",
  "servo_config 0.0.1",
@@ -2292,7 +2292,7 @@ dependencies = [
  "rustc-serialize 0.3.22 (registry+https://github.com/rust-lang/crates.io-index)",
  "script_layout_interface 0.0.1",
  "script_traits 0.0.1",
- "selectors 0.17.0 (registry+https://github.com/rust-lang/crates.io-index)",
+ "selectors 0.17.0",
  "serde 0.8.20 (registry+https://github.com/rust-lang/crates.io-index)",
  "serde_json 0.8.4 (registry+https://github.com/rust-lang/crates.io-index)",
  "servo_atoms 0.0.1",
@@ -2336,7 +2336,7 @@ dependencies = [
  "profile_traits 0.0.1",
  "range 0.0.1",
  "script_traits 0.0.1",
- "selectors 0.17.0 (registry+https://github.com/rust-lang/crates.io-index)",
+ "selectors 0.17.0",
  "servo_url 0.0.1",
  "style 0.0.1",
 ]
@@ -2387,7 +2387,6 @@ dependencies = [
 [[package]]
 name = "selectors"
 version = "0.17.0"
-source = "registry+https://github.com/rust-lang/crates.io-index"
 dependencies = [
  "bitflags 0.7.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "cssparser 0.7.3 (registry+https://github.com/rust-lang/crates.io-index)",
@@ -2767,7 +2766,7 @@ dependencies = [
  "rayon 0.6.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "regex 0.2.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "rustc-serialize 0.3.22 (registry+https://github.com/rust-lang/crates.io-index)",
- "selectors 0.17.0 (registry+https://github.com/rust-lang/crates.io-index)",
+ "selectors 0.17.0",
  "serde 0.8.20 (registry+https://github.com/rust-lang/crates.io-index)",
  "serde_derive 0.8.23 (registry+https://github.com/rust-lang/crates.io-index)",
  "servo_atoms 0.0.1",
@@ -2793,7 +2792,7 @@ dependencies = [
  "parking_lot 0.3.7 (registry+https://github.com/rust-lang/crates.io-index)",
  "rayon 0.6.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "rustc-serialize 0.3.22 (registry+https://github.com/rust-lang/crates.io-index)",
- "selectors 0.17.0 (registry+https://github.com/rust-lang/crates.io-index)",
+ "selectors 0.17.0",
  "servo_atoms 0.0.1",
  "servo_config 0.0.1",
  "servo_url 0.0.1",
@@ -2830,7 +2829,7 @@ dependencies = [
  "log 0.3.6 (registry+https://github.com/rust-lang/crates.io-index)",
  "num_cpus 1.2.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "parking_lot 0.3.7 (registry+https://github.com/rust-lang/crates.io-index)",
- "selectors 0.17.0 (registry+https://github.com/rust-lang/crates.io-index)",
+ "selectors 0.17.0",
  "servo_url 0.0.1",
  "style 0.0.1",
  "style_traits 0.0.1",
@@ -3517,7 +3516,6 @@ dependencies = [
 "checksum rustc_version 0.1.7 (registry+https://github.com/rust-lang/crates.io-index)" = "c5f5376ea5e30ce23c03eb77cbe4962b988deead10910c372b226388b594c084"
 "checksum same-file 0.1.3 (registry+https://github.com/rust-lang/crates.io-index)" = "d931a44fdaa43b8637009e7632a02adc4f2b2e0733c08caa4cf00e8da4a117a7"
 "checksum scoped_threadpool 0.1.7 (registry+https://github.com/rust-lang/crates.io-index)" = "3ef399c8893e8cb7aa9696e895427fab3a6bf265977bb96e126f24ddd2cda85a"
-"checksum selectors 0.17.0 (registry+https://github.com/rust-lang/crates.io-index)" = "48ed8bbe599ed52966241c818c92dc024702666f51b4e8ab538b2108c1d6d43a"
 "checksum semver 0.1.20 (registry+https://github.com/rust-lang/crates.io-index)" = "d4f410fedcf71af0345d7607d246e7ad15faaadd49d240ee3b24e5dc21a820ac"
 "checksum semver 0.2.3 (registry+https://github.com/rust-lang/crates.io-index)" = "2d5b7638a1f03815d94e88cb3b3c08e87f0db4d683ef499d1836aaf70a45623f"
 "checksum serde 0.8.20 (registry+https://github.com/rust-lang/crates.io-index)" = "793aa8d4a777e46a68bbf88998cd957e638427ba5bfb0de22c92ff277b65bd21"
diff --git a/components/layout/Cargo.toml b/components/layout/Cargo.toml
index 359d8619c7f..7072372aeb0 100644
--- a/components/layout/Cargo.toml
+++ b/components/layout/Cargo.toml
@@ -34,7 +34,7 @@ range = {path = "../range"}
 rayon = "0.6"
 script_layout_interface = {path = "../script_layout_interface"}
 script_traits = {path = "../script_traits"}
-selectors = "0.17"
+selectors = { path = "../selectors" }
 serde = "0.8"
 serde_derive = "0.8"
 servo_geometry = {path = "../geometry"}
diff --git a/components/layout_thread/Cargo.toml b/components/layout_thread/Cargo.toml
index fd721e0c935..05e682c0ef4 100644
--- a/components/layout_thread/Cargo.toml
+++ b/components/layout_thread/Cargo.toml
@@ -30,7 +30,7 @@ rayon = "0.6"
 script = {path = "../script"}
 script_layout_interface = {path = "../script_layout_interface"}
 script_traits = {path = "../script_traits"}
-selectors = "0.17"
+selectors = { path = "../selectors" }
 serde_derive = "0.8"
 serde_json = "0.8"
 servo_config = {path = "../config"}
diff --git a/components/script/Cargo.toml b/components/script/Cargo.toml
index 1d565715d25..57ea9b4b648 100644
--- a/components/script/Cargo.toml
+++ b/components/script/Cargo.toml
@@ -70,7 +70,7 @@ regex = "0.2"
 rustc-serialize = "0.3"
 script_layout_interface = {path = "../script_layout_interface"}
 script_traits = {path = "../script_traits"}
-selectors = "0.17"
+selectors = { path = "../selectors" }
 serde = "0.8"
 servo_atoms = {path = "../atoms"}
 servo_config = {path = "../config", features = ["servo"] }
diff --git a/components/script_layout_interface/Cargo.toml b/components/script_layout_interface/Cargo.toml
index 1440755e769..d7892f4962d 100644
--- a/components/script_layout_interface/Cargo.toml
+++ b/components/script_layout_interface/Cargo.toml
@@ -28,6 +28,6 @@ plugins = {path = "../plugins"}
 profile_traits = {path = "../profile_traits"}
 range = {path = "../range"}
 script_traits = {path = "../script_traits"}
-selectors = "0.17"
+selectors = { path = "../selectors" }
 servo_url = {path = "../url"}
 style = {path = "../style"}
diff --git a/components/selectors/Cargo.toml b/components/selectors/Cargo.toml
new file mode 100644
index 00000000000..b34c6648a15
--- /dev/null
+++ b/components/selectors/Cargo.toml
@@ -0,0 +1,22 @@
+[package]
+
+name = "selectors"
+version = "0.17.0"
+authors = ["Simon Sapin <simon.sapin@exyr.org>", "Alan Jeffrey <ajeffrey@mozilla.com>"]
+documentation = "https://docs.rs/selectors/"
+
+description = "CSS Selectors matching for Rust"
+repository = "https://github.com/servo/servo"
+readme = "README.md"
+keywords = ["css", "selectors"]
+license = "MPL-2.0"
+
+[lib]
+name = "selectors"
+path = "lib.rs"
+
+[dependencies]
+bitflags = "0.7"
+matches = "0.1"
+cssparser = ">=0.6, <0.8"
+fnv = "1.0"
diff --git a/components/selectors/README.md b/components/selectors/README.md
new file mode 100644
index 00000000000..352c8dfb693
--- /dev/null
+++ b/components/selectors/README.md
@@ -0,0 +1,25 @@
+rust-selectors
+==============
+
+* [![Build Status](https://travis-ci.org/servo/rust-selectors.svg?branch=master)](
+  https://travis-ci.org/servo/rust-selectors)
+* [Documentation](https://docs.rs/selectors/)
+* [crates.io](https://crates.io/crates/selectors)
+
+CSS Selectors library for Rust.
+Includes parsing and serilization of selectors,
+as well as matching against a generic tree of elements.
+Pseudo-elements and most pseudo-classes are generic as well.
+
+**Warning:** breaking changes are made to this library fairly frequently
+(13 times in 2016, for example).
+However you can use this crate without updating it that often,
+old versions stay available on crates.io and Cargo will only automatically update
+to versions that are numbered as compatible.
+
+To see how to use this library with your own tree representation,
+see [Kuchiki’s `src/select.rs`](https://github.com/SimonSapin/kuchiki/blob/master/src/select.rs).
+(Note however that Kuchiki is not always up to date with the latest rust-selectors version,
+so that code may need to be tweaked.)
+If you don’t already have a tree data structure,
+consider using [Kuchiki](https://github.com/SimonSapin/kuchiki) itself.
diff --git a/components/selectors/bloom.rs b/components/selectors/bloom.rs
new file mode 100644
index 00000000000..9d64391346d
--- /dev/null
+++ b/components/selectors/bloom.rs
@@ -0,0 +1,312 @@
+/* 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/. */
+
+//! Simple counting bloom filters.
+
+use fnv::FnvHasher;
+use std::hash::{Hash, Hasher};
+
+const KEY_SIZE: usize = 12;
+const ARRAY_SIZE: usize = 1 << KEY_SIZE;
+const KEY_MASK: u32 = (1 << KEY_SIZE) - 1;
+const KEY_SHIFT: usize = 16;
+
+/// A counting Bloom filter with 8-bit counters.  For now we assume
+/// that having two hash functions is enough, but we may revisit that
+/// decision later.
+///
+/// The filter uses an array with 2**KeySize entries.
+///
+/// Assuming a well-distributed hash function, a Bloom filter with
+/// array size M containing N elements and
+/// using k hash function has expected false positive rate exactly
+///
+/// $  (1 - (1 - 1/M)^{kN})^k  $
+///
+/// because each array slot has a
+///
+/// $  (1 - 1/M)^{kN}  $
+///
+/// chance of being 0, and the expected false positive rate is the
+/// probability that all of the k hash functions will hit a nonzero
+/// slot.
+///
+/// For reasonable assumptions (M large, kN large, which should both
+/// hold if we're worried about false positives) about M and kN this
+/// becomes approximately
+///
+/// $$  (1 - \exp(-kN/M))^k   $$
+///
+/// For our special case of k == 2, that's $(1 - \exp(-2N/M))^2$,
+/// or in other words
+///
+/// $$    N/M = -0.5 * \ln(1 - \sqrt(r))   $$
+///
+/// where r is the false positive rate.  This can be used to compute
+/// the desired KeySize for a given load N and false positive rate r.
+///
+/// If N/M is assumed small, then the false positive rate can
+/// further be approximated as 4*N^2/M^2.  So increasing KeySize by
+/// 1, which doubles M, reduces the false positive rate by about a
+/// factor of 4, and a false positive rate of 1% corresponds to
+/// about M/N == 20.
+///
+/// What this means in practice is that for a few hundred keys using a
+/// KeySize of 12 gives false positive rates on the order of 0.25-4%.
+///
+/// Similarly, using a KeySize of 10 would lead to a 4% false
+/// positive rate for N == 100 and to quite bad false positive
+/// rates for larger N.
+pub struct BloomFilter {
+    counters: [u8; ARRAY_SIZE],
+}
+
+impl Clone for BloomFilter {
+    #[inline]
+    fn clone(&self) -> BloomFilter {
+        BloomFilter {
+            counters: self.counters,
+        }
+    }
+}
+
+impl BloomFilter {
+    /// Creates a new bloom filter.
+    #[inline]
+    pub fn new() -> BloomFilter {
+        BloomFilter {
+            counters: [0; ARRAY_SIZE],
+        }
+    }
+
+    #[inline]
+    fn first_slot(&self, hash: u32) -> &u8 {
+        &self.counters[hash1(hash) as usize]
+    }
+
+    #[inline]
+    fn first_mut_slot(&mut self, hash: u32) -> &mut u8 {
+        &mut self.counters[hash1(hash) as usize]
+    }
+
+    #[inline]
+    fn second_slot(&self, hash: u32) -> &u8 {
+        &self.counters[hash2(hash) as usize]
+    }
+
+    #[inline]
+    fn second_mut_slot(&mut self, hash: u32) -> &mut u8 {
+        &mut self.counters[hash2(hash) as usize]
+    }
+
+    #[inline]
+    pub fn clear(&mut self) {
+        self.counters = [0; ARRAY_SIZE]
+    }
+
+    #[inline]
+    fn insert_hash(&mut self, hash: u32) {
+        {
+            let slot1 = self.first_mut_slot(hash);
+            if !full(slot1) {
+                *slot1 += 1
+            }
+        }
+        {
+            let slot2 = self.second_mut_slot(hash);
+            if !full(slot2) {
+                *slot2 += 1
+            }
+        }
+    }
+
+    /// Inserts an item into the bloom filter.
+    #[inline]
+    pub fn insert<T: Hash>(&mut self, elem: &T) {
+        self.insert_hash(hash(elem))
+
+    }
+
+    #[inline]
+    fn remove_hash(&mut self, hash: u32) {
+        {
+            let slot1 = self.first_mut_slot(hash);
+            if !full(slot1) {
+                *slot1 -= 1
+            }
+        }
+        {
+            let slot2 = self.second_mut_slot(hash);
+            if !full(slot2) {
+                *slot2 -= 1
+            }
+        }
+    }
+
+    /// Removes an item from the bloom filter.
+    #[inline]
+    pub fn remove<T: Hash>(&mut self, elem: &T) {
+        self.remove_hash(hash(elem))
+    }
+
+    #[inline]
+    fn might_contain_hash(&self, hash: u32) -> bool {
+        *self.first_slot(hash) != 0 && *self.second_slot(hash) != 0
+    }
+
+    /// Check whether the filter might contain an item.  This can
+    /// sometimes return true even if the item is not in the filter,
+    /// but will never return false for items that are actually in the
+    /// filter.
+    #[inline]
+    pub fn might_contain<T: Hash>(&self, elem: &T) -> bool {
+        self.might_contain_hash(hash(elem))
+    }
+}
+
+#[inline]
+fn full(slot: &u8) -> bool {
+    *slot == 0xff
+}
+
+#[inline]
+fn hash<T: Hash>(elem: &T) -> u32 {
+    let mut hasher = FnvHasher::default();
+    elem.hash(&mut hasher);
+    let hash: u64 = hasher.finish();
+    (hash >> 32) as u32 ^ (hash as u32)
+}
+
+#[inline]
+fn hash1(hash: u32) -> u32 {
+    hash & KEY_MASK
+}
+
+#[inline]
+fn hash2(hash: u32) -> u32 {
+    (hash >> KEY_SHIFT) & KEY_MASK
+}
+
+#[test]
+fn create_and_insert_some_stuff() {
+    let mut bf = BloomFilter::new();
+
+    for i in 0_usize .. 1000 {
+        bf.insert(&i);
+    }
+
+    for i in 0_usize .. 1000 {
+        assert!(bf.might_contain(&i));
+    }
+
+    let false_positives =
+        (1001_usize .. 2000).filter(|i| bf.might_contain(i)).count();
+
+    assert!(false_positives < 150, "{} is not < 150", false_positives); // 15%.
+
+    for i in 0_usize .. 100 {
+        bf.remove(&i);
+    }
+
+    for i in 100_usize .. 1000 {
+        assert!(bf.might_contain(&i));
+    }
+
+    let false_positives = (0_usize .. 100).filter(|i| bf.might_contain(i)).count();
+
+    assert!(false_positives < 20, "{} is not < 20", false_positives); // 20%.
+
+    bf.clear();
+
+    for i in 0_usize .. 2000 {
+        assert!(!bf.might_contain(&i));
+    }
+}
+
+#[cfg(feature = "unstable")]
+#[cfg(test)]
+mod bench {
+    extern crate test;
+
+    use std::hash::{Hash, Hasher, SipHasher};
+    use super::BloomFilter;
+
+    #[bench]
+    fn create_insert_1000_remove_100_lookup_100(b: &mut test::Bencher) {
+        b.iter(|| {
+            let mut bf = BloomFilter::new();
+            for i in 0_usize .. 1000 {
+                bf.insert(&i);
+            }
+            for i in 0_usize .. 100 {
+                bf.remove(&i);
+            }
+            for i in 100_usize .. 200 {
+                test::black_box(bf.might_contain(&i));
+            }
+        });
+    }
+
+    #[bench]
+    fn might_contain(b: &mut test::Bencher) {
+        let mut bf = BloomFilter::new();
+
+        for i in 0_usize .. 1000 {
+            bf.insert(&i);
+        }
+
+        let mut i = 0_usize;
+
+        b.bench_n(1000, |b| {
+            b.iter(|| {
+                test::black_box(bf.might_contain(&i));
+                i += 1;
+            });
+        });
+    }
+
+    #[bench]
+    fn insert(b: &mut test::Bencher) {
+        let mut bf = BloomFilter::new();
+
+        b.bench_n(1000, |b| {
+            let mut i = 0_usize;
+
+            b.iter(|| {
+                test::black_box(bf.insert(&i));
+                i += 1;
+            });
+        });
+    }
+
+    #[bench]
+    fn remove(b: &mut test::Bencher) {
+        let mut bf = BloomFilter::new();
+        for i in 0_usize .. 1000 {
+            bf.insert(&i);
+        }
+
+        b.bench_n(1000, |b| {
+            let mut i = 0_usize;
+
+            b.iter(|| {
+                bf.remove(&i);
+                i += 1;
+            });
+        });
+
+        test::black_box(bf.might_contain(&0_usize));
+    }
+
+    #[bench]
+    fn hash_a_uint(b: &mut test::Bencher) {
+        let mut i = 0_usize;
+        b.iter(|| {
+            let mut hasher = SipHasher::default();
+            i.hash(&mut hasher);
+            test::black_box(hasher.finish());
+            i += 1;
+        })
+    }
+}
diff --git a/components/selectors/lib.rs b/components/selectors/lib.rs
new file mode 100644
index 00000000000..247902074b9
--- /dev/null
+++ b/components/selectors/lib.rs
@@ -0,0 +1,17 @@
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#[macro_use] extern crate bitflags;
+#[macro_use] extern crate cssparser;
+#[macro_use] extern crate matches;
+extern crate fnv;
+
+pub mod bloom;
+pub mod matching;
+pub mod parser;
+mod tree;
+
+pub use parser::{SelectorImpl, Parser, SelectorList};
+pub use tree::Element;
+pub use tree::{MatchAttr, MatchAttrGeneric};
diff --git a/components/selectors/matching.rs b/components/selectors/matching.rs
new file mode 100644
index 00000000000..72d3a21ebf2
--- /dev/null
+++ b/components/selectors/matching.rs
@@ -0,0 +1,573 @@
+/* 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 std::borrow::Borrow;
+
+use bloom::BloomFilter;
+
+use parser::{CaseSensitivity, Combinator, ComplexSelector, LocalName};
+use parser::{SimpleSelector, Selector, SelectorImpl};
+use tree::Element;
+
+/// The reason why we're doing selector matching.
+///
+/// If this is for styling, this will include the flags in the parent element.
+///
+/// This is done because Servo doesn't need those flags at all when it's not
+/// styling (e.g., when you're doing document.querySelector). For example, a
+/// slow selector in an API like querySelector doesn't imply that the parent
+/// could match it.
+#[derive(Copy, Clone, Debug, PartialEq, Eq)]
+pub enum MatchingReason {
+    ForStyling,
+    Other,
+}
+
+impl MatchingReason {
+    #[inline]
+    fn for_styling(&self) -> bool {
+        *self == MatchingReason::ForStyling
+    }
+}
+
+// The bloom filter for descendant CSS selectors will have a <1% false
+// positive rate until it has this many selectors in it, then it will
+// rapidly increase.
+pub static RECOMMENDED_SELECTOR_BLOOM_FILTER_SIZE: usize = 4096;
+
+bitflags! {
+    /// Set of flags that determine the different kind of elements affected by
+    /// the selector matching process.
+    ///
+    /// This is used to implement efficient sharing.
+    pub flags StyleRelations: u16 {
+        /// Whether this element has matched any rule that is determined by a
+        /// sibling (when using the `+` or `~` combinators).
+        const AFFECTED_BY_SIBLINGS = 1 << 0,
+
+        /// Whether this element has matched any rule whose matching is
+        /// determined by its position in the tree (i.e., first-child,
+        /// nth-child, etc.).
+        const AFFECTED_BY_CHILD_INDEX = 1 << 1,
+
+        /// Whether this flag is affected by any state (i.e., non
+        /// tree-structural pseudo-class).
+        const AFFECTED_BY_STATE = 1 << 2,
+
+        /// Whether this element is affected by an ID selector.
+        const AFFECTED_BY_ID_SELECTOR = 1 << 3,
+
+        /// Whether this element is affected by a non-common style-affecting
+        /// attribute.
+        const AFFECTED_BY_NON_COMMON_STYLE_AFFECTING_ATTRIBUTE_SELECTOR = 1 << 4,
+
+        /// Whether this element matches the :empty pseudo class.
+        const AFFECTED_BY_EMPTY = 1 << 5,
+
+        /// Whether this element has a style attribute. Computed
+        /// externally.
+        const AFFECTED_BY_STYLE_ATTRIBUTE = 1 << 6,
+
+        /// Whether this element is affected by presentational hints. This is
+        /// computed externally (that is, in Servo).
+        const AFFECTED_BY_PRESENTATIONAL_HINTS = 1 << 7,
+
+        /// Whether this element has pseudo-element styles. Computed externally.
+        const AFFECTED_BY_PSEUDO_ELEMENTS = 1 << 8,
+
+        /// Whether this element has effective animation styles. Computed
+        /// externally.
+        const AFFECTED_BY_ANIMATIONS = 1 << 9,
+
+        /// Whether this element has effective transition styles. Computed
+        /// externally.
+        const AFFECTED_BY_TRANSITIONS = 1 << 10,
+    }
+}
+
+bitflags! {
+    /// Set of flags that are set on the parent depending on whether a child
+    /// could potentially match a selector.
+    ///
+    /// These setters, in the case of Servo, must be atomic, due to the parallel
+    /// traversal.
+    pub flags ElementFlags: u8 {
+        /// When a child is added or removed from this element, all the children
+        /// must be restyled, because they may match :nth-last-child,
+        /// :last-of-type, :nth-last-of-type, or :only-of-type.
+        const HAS_SLOW_SELECTOR = 1 << 0,
+
+        /// When a child is added or removed from this element, any later
+        /// children must be restyled, because they may match :nth-child,
+        /// :first-of-type, or :nth-of-type.
+        const HAS_SLOW_SELECTOR_LATER_SIBLINGS = 1 << 1,
+
+        /// When a child is added or removed from this element, the first and
+        /// last children must be restyled, because they may match :first-child,
+        /// :last-child, or :only-child.
+        const HAS_EDGE_CHILD_SELECTOR = 1 << 2,
+
+        /// The element has an empty selector, so when a child is appended we
+        /// might need to restyle the parent completely.
+        const HAS_EMPTY_SELECTOR = 1 << 3,
+    }
+}
+
+pub fn matches<E>(selector_list: &[Selector<E::Impl>],
+                  element: &E,
+                  parent_bf: Option<&BloomFilter>,
+                  reason: MatchingReason)
+                  -> bool
+    where E: Element
+{
+    selector_list.iter().any(|selector| {
+        selector.pseudo_element.is_none() &&
+        matches_complex_selector(&*selector.complex_selector, element, parent_bf, &mut StyleRelations::empty(), reason)
+    })
+}
+
+/// Determines whether the given element matches the given complex selector.
+///
+/// NB: If you add support for any new kinds of selectors to this routine, be sure to set
+/// `shareable` to false unless you are willing to update the style sharing logic. Otherwise things
+/// will almost certainly break as elements will start mistakenly sharing styles. (See
+/// `can_share_style_with` in `servo/components/style/matching.rs`.)
+pub fn matches_complex_selector<E>(selector: &ComplexSelector<E::Impl>,
+                                   element: &E,
+                                   parent_bf: Option<&BloomFilter>,
+                                   relations: &mut StyleRelations,
+                                   reason: MatchingReason)
+                                   -> bool
+    where E: Element
+{
+    match matches_complex_selector_internal(selector, element, parent_bf, relations, reason) {
+        SelectorMatchingResult::Matched => {
+            match selector.next {
+                Some((_, Combinator::NextSibling)) |
+                Some((_, Combinator::LaterSibling)) => *relations |= AFFECTED_BY_SIBLINGS,
+                _ => {}
+            }
+
+            true
+        }
+        _ => false
+    }
+}
+
+/// A result of selector matching, includes 3 failure types,
+///
+///   NotMatchedAndRestartFromClosestLaterSibling
+///   NotMatchedAndRestartFromClosestDescendant
+///   NotMatchedGlobally
+///
+/// When NotMatchedGlobally appears, stop selector matching completely since
+/// the succeeding selectors never matches.
+/// It is raised when
+///   Child combinator cannot find the candidate element.
+///   Descendant combinator cannot find the candidate element.
+///
+/// When NotMatchedAndRestartFromClosestDescendant appears, the selector
+/// matching does backtracking and restarts from the closest Descendant
+/// combinator.
+/// It is raised when
+///   NextSibling combinator cannot find the candidate element.
+///   LaterSibling combinator cannot find the candidate element.
+///   Child combinator doesn't match on the found element.
+///
+/// When NotMatchedAndRestartFromClosestLaterSibling appears, the selector
+/// matching does backtracking and restarts from the closest LaterSibling
+/// combinator.
+/// It is raised when
+///   NextSibling combinator doesn't match on the found element.
+///
+/// For example, when the selector "d1 d2 a" is provided and we cannot *find*
+/// an appropriate ancestor element for "d1", this selector matching raises
+/// NotMatchedGlobally since even if "d2" is moved to more upper element, the
+/// candidates for "d1" becomes less than before and d1 .
+///
+/// The next example is siblings. When the selector "b1 + b2 ~ d1 a" is
+/// provided and we cannot *find* an appropriate brother element for b1,
+/// the selector matching raises NotMatchedAndRestartFromClosestDescendant.
+/// The selectors ("b1 + b2 ~") doesn't match and matching restart from "d1".
+///
+/// The additional example is child and sibling. When the selector
+/// "b1 + c1 > b2 ~ d1 a" is provided and the selector "b1" doesn't match on
+/// the element, this "b1" raises NotMatchedAndRestartFromClosestLaterSibling.
+/// However since the selector "c1" raises
+/// NotMatchedAndRestartFromClosestDescendant. So the selector
+/// "b1 + c1 > b2 ~ " doesn't match and restart matching from "d1".
+#[derive(PartialEq, Eq, Copy, Clone)]
+enum SelectorMatchingResult {
+    Matched,
+    NotMatchedAndRestartFromClosestLaterSibling,
+    NotMatchedAndRestartFromClosestDescendant,
+    NotMatchedGlobally,
+}
+
+/// Quickly figures out whether or not the complex selector is worth doing more
+/// work on. If the simple selectors don't match, or there's a child selector
+/// that does not appear in the bloom parent bloom filter, we can exit early.
+fn can_fast_reject<E>(mut selector: &ComplexSelector<E::Impl>,
+                      element: &E,
+                      parent_bf: Option<&BloomFilter>,
+                      relations: &mut StyleRelations,
+                      reason: MatchingReason)
+                      -> Option<SelectorMatchingResult>
+    where E: Element
+{
+    if !selector.compound_selector.iter().all(|simple_selector| {
+      matches_simple_selector(simple_selector, element, parent_bf, relations, reason) }) {
+        return Some(SelectorMatchingResult::NotMatchedAndRestartFromClosestLaterSibling);
+    }
+
+    let bf: &BloomFilter = match parent_bf {
+        None => return None,
+        Some(ref bf) => bf,
+    };
+
+    // See if the bloom filter can exclude any of the descendant selectors, and
+    // reject if we can.
+    loop {
+         match selector.next {
+             None => break,
+             Some((ref cs, Combinator::Descendant)) => selector = &**cs,
+             Some((ref cs, _)) => {
+                 selector = &**cs;
+                 continue;
+             }
+         };
+
+        for ss in selector.compound_selector.iter() {
+            match *ss {
+                SimpleSelector::LocalName(LocalName { ref name, ref lower_name })  => {
+                    if !bf.might_contain(name)
+                    && !bf.might_contain(lower_name) {
+                        return Some(SelectorMatchingResult::NotMatchedGlobally);
+                    }
+                },
+                SimpleSelector::Namespace(ref namespace) => {
+                    if !bf.might_contain(&namespace.url) {
+                        return Some(SelectorMatchingResult::NotMatchedGlobally);
+                    }
+                },
+                SimpleSelector::ID(ref id) => {
+                    if !bf.might_contain(id) {
+                        return Some(SelectorMatchingResult::NotMatchedGlobally);
+                    }
+                },
+                SimpleSelector::Class(ref class) => {
+                    if !bf.might_contain(class) {
+                        return Some(SelectorMatchingResult::NotMatchedGlobally);
+                    }
+                },
+                _ => {},
+            }
+        }
+    }
+
+    // Can't fast reject.
+    None
+}
+
+fn matches_complex_selector_internal<E>(selector: &ComplexSelector<E::Impl>,
+                                         element: &E,
+                                         parent_bf: Option<&BloomFilter>,
+                                         relations: &mut StyleRelations,
+                                         reason: MatchingReason)
+                                         -> SelectorMatchingResult
+     where E: Element
+{
+    if let Some(result) = can_fast_reject(selector, element, parent_bf, relations, reason) {
+        return result;
+    }
+
+    match selector.next {
+        None => SelectorMatchingResult::Matched,
+        Some((ref next_selector, combinator)) => {
+            let (siblings, candidate_not_found) = match combinator {
+                Combinator::Child => (false, SelectorMatchingResult::NotMatchedGlobally),
+                Combinator::Descendant => (false, SelectorMatchingResult::NotMatchedGlobally),
+                Combinator::NextSibling => (true, SelectorMatchingResult::NotMatchedAndRestartFromClosestDescendant),
+                Combinator::LaterSibling => (true, SelectorMatchingResult::NotMatchedAndRestartFromClosestDescendant),
+            };
+            let mut next_element = if siblings {
+                element.prev_sibling_element()
+            } else {
+                element.parent_element()
+            };
+            loop {
+                let element = match next_element {
+                    None => return candidate_not_found,
+                    Some(next_element) => next_element,
+                };
+                let result = matches_complex_selector_internal(&**next_selector,
+                                                                &element,
+                                                                parent_bf,
+                                                                relations,
+                                                                reason);
+                match (result, combinator) {
+                    // Return the status immediately.
+                    (SelectorMatchingResult::Matched, _) => return result,
+                    (SelectorMatchingResult::NotMatchedGlobally, _) => return result,
+
+                    // Upgrade the failure status to
+                    // NotMatchedAndRestartFromClosestDescendant.
+                    (_, Combinator::Child) => return SelectorMatchingResult::NotMatchedAndRestartFromClosestDescendant,
+
+                    // Return the status directly.
+                    (_, Combinator::NextSibling) => return result,
+
+                    // If the failure status is NotMatchedAndRestartFromClosestDescendant
+                    // and combinator is Combinator::LaterSibling, give up this Combinator::LaterSibling matching
+                    // and restart from the closest descendant combinator.
+                    (SelectorMatchingResult::NotMatchedAndRestartFromClosestDescendant, Combinator::LaterSibling) => return result,
+
+                    // The Combinator::Descendant combinator and the status is
+                    // NotMatchedAndRestartFromClosestLaterSibling or
+                    // NotMatchedAndRestartFromClosestDescendant,
+                    // or the Combinator::LaterSibling combinator and the status is
+                    // NotMatchedAndRestartFromClosestDescendant
+                    // can continue to matching on the next candidate element.
+                    _ => {},
+                }
+                next_element = if siblings {
+                    element.prev_sibling_element()
+                } else {
+                    element.parent_element()
+                };
+            }
+        }
+    }
+}
+
+/// Determines whether the given element matches the given single selector.
+#[inline]
+fn matches_simple_selector<E>(
+        selector: &SimpleSelector<E::Impl>,
+        element: &E,
+        parent_bf: Option<&BloomFilter>,
+        relations: &mut StyleRelations,
+        reason: MatchingReason)
+        -> bool
+    where E: Element
+{
+    macro_rules! relation_if {
+        ($ex:expr, $flag:ident) => {
+            if $ex {
+                *relations |= $flag;
+                true
+            } else {
+                false
+            }
+        }
+    }
+
+    match *selector {
+        SimpleSelector::LocalName(LocalName { ref name, ref lower_name }) => {
+            let name = if element.is_html_element_in_html_document() { lower_name } else { name };
+            element.get_local_name() == name.borrow()
+        }
+        SimpleSelector::Namespace(ref namespace) => {
+            element.get_namespace() == namespace.url.borrow()
+        }
+        // TODO: case-sensitivity depends on the document type and quirks mode
+        SimpleSelector::ID(ref id) => {
+            relation_if!(element.get_id().map_or(false, |attr| attr == *id),
+                         AFFECTED_BY_ID_SELECTOR)
+        }
+        SimpleSelector::Class(ref class) => {
+            element.has_class(class)
+        }
+        SimpleSelector::AttrExists(ref attr) => {
+            let matches = element.match_attr_has(attr);
+
+            if matches && !E::Impl::attr_exists_selector_is_shareable(attr) {
+                *relations |= AFFECTED_BY_NON_COMMON_STYLE_AFFECTING_ATTRIBUTE_SELECTOR;
+            }
+
+            matches
+        }
+        SimpleSelector::AttrEqual(ref attr, ref value, case_sensitivity) => {
+            let matches = match case_sensitivity {
+                CaseSensitivity::CaseSensitive => element.match_attr_equals(attr, value),
+                CaseSensitivity::CaseInsensitive => element.match_attr_equals_ignore_ascii_case(attr, value),
+            };
+
+            if matches && !E::Impl::attr_equals_selector_is_shareable(attr, value) {
+                *relations |= AFFECTED_BY_NON_COMMON_STYLE_AFFECTING_ATTRIBUTE_SELECTOR;
+            }
+
+            matches
+        }
+        SimpleSelector::AttrIncludes(ref attr, ref value) => {
+            relation_if!(element.match_attr_includes(attr, value),
+                         AFFECTED_BY_NON_COMMON_STYLE_AFFECTING_ATTRIBUTE_SELECTOR)
+        }
+        SimpleSelector::AttrDashMatch(ref attr, ref value) => {
+            relation_if!(element.match_attr_dash(attr, value),
+                         AFFECTED_BY_NON_COMMON_STYLE_AFFECTING_ATTRIBUTE_SELECTOR)
+        }
+        SimpleSelector::AttrPrefixMatch(ref attr, ref value) => {
+            relation_if!(element.match_attr_prefix(attr, value),
+                         AFFECTED_BY_NON_COMMON_STYLE_AFFECTING_ATTRIBUTE_SELECTOR)
+        }
+        SimpleSelector::AttrSubstringMatch(ref attr, ref value) => {
+            relation_if!(element.match_attr_substring(attr, value),
+                         AFFECTED_BY_NON_COMMON_STYLE_AFFECTING_ATTRIBUTE_SELECTOR)
+        }
+        SimpleSelector::AttrSuffixMatch(ref attr, ref value) => {
+            relation_if!(element.match_attr_suffix(attr, value),
+                         AFFECTED_BY_NON_COMMON_STYLE_AFFECTING_ATTRIBUTE_SELECTOR)
+        }
+        SimpleSelector::AttrIncludesNeverMatch(..) |
+        SimpleSelector::AttrPrefixNeverMatch(..) |
+        SimpleSelector::AttrSubstringNeverMatch(..) |
+        SimpleSelector::AttrSuffixNeverMatch(..) => {
+            false
+        }
+        SimpleSelector::NonTSPseudoClass(ref pc) => {
+            relation_if!(element.match_non_ts_pseudo_class(pc),
+                         AFFECTED_BY_STATE)
+        }
+        SimpleSelector::FirstChild => {
+            relation_if!(matches_first_child(element, reason), AFFECTED_BY_CHILD_INDEX)
+        }
+        SimpleSelector::LastChild => {
+            relation_if!(matches_last_child(element, reason), AFFECTED_BY_CHILD_INDEX)
+        }
+        SimpleSelector::OnlyChild => {
+            relation_if!(matches_first_child(element, reason) && matches_last_child(element, reason), AFFECTED_BY_CHILD_INDEX)
+        }
+        SimpleSelector::Root => {
+            // We never share styles with an element with no parent, so no point
+            // in creating a new StyleRelation.
+            element.is_root()
+        }
+        SimpleSelector::Empty => {
+            if reason.for_styling() {
+                element.insert_flags(HAS_EMPTY_SELECTOR);
+            }
+            relation_if!(element.is_empty(), AFFECTED_BY_EMPTY)
+        }
+        SimpleSelector::NthChild(a, b) => {
+            relation_if!(matches_generic_nth_child(element, a, b, false, false, reason),
+                         AFFECTED_BY_CHILD_INDEX)
+        }
+        SimpleSelector::NthLastChild(a, b) => {
+            relation_if!(matches_generic_nth_child(element, a, b, false, true, reason),
+                         AFFECTED_BY_CHILD_INDEX)
+        }
+        SimpleSelector::NthOfType(a, b) => {
+            relation_if!(matches_generic_nth_child(element, a, b, true, false, reason),
+                         AFFECTED_BY_CHILD_INDEX)
+        }
+        SimpleSelector::NthLastOfType(a, b) => {
+            relation_if!(matches_generic_nth_child(element, a, b, true, true, reason),
+                         AFFECTED_BY_CHILD_INDEX)
+        }
+        SimpleSelector::FirstOfType => {
+            relation_if!(matches_generic_nth_child(element, 0, 1, true, false, reason),
+                         AFFECTED_BY_CHILD_INDEX)
+        }
+        SimpleSelector::LastOfType => {
+            relation_if!(matches_generic_nth_child(element, 0, 1, true, true, reason),
+                         AFFECTED_BY_CHILD_INDEX)
+        }
+        SimpleSelector::OnlyOfType => {
+            relation_if!(matches_generic_nth_child(element, 0, 1, true, false, reason) &&
+                         matches_generic_nth_child(element, 0, 1, true, true, reason),
+                         AFFECTED_BY_CHILD_INDEX)
+        }
+        SimpleSelector::Negation(ref negated) => {
+            !negated.iter().all(|s| {
+                matches_complex_selector(s, element, parent_bf, relations, reason)
+            })
+        }
+    }
+}
+
+#[inline]
+fn matches_generic_nth_child<E>(element: &E,
+                                a: i32,
+                                b: i32,
+                                is_of_type: bool,
+                                is_from_end: bool,
+                                reason: MatchingReason) -> bool
+    where E: Element
+{
+    // Selectors Level 4 changed from Level 3:
+    // This can match without a parent element:
+    // https://drafts.csswg.org/selectors-4/#child-index
+
+    if reason.for_styling() {
+        if let Some(parent) = element.parent_element() {
+            parent.insert_flags(if is_from_end {
+                HAS_SLOW_SELECTOR
+            } else {
+                HAS_SLOW_SELECTOR_LATER_SIBLINGS
+            });
+        }
+    }
+
+    let mut index = 1;
+    let mut next_sibling = if is_from_end {
+        element.next_sibling_element()
+    } else {
+        element.prev_sibling_element()
+    };
+
+    loop {
+        let sibling = match next_sibling {
+            None => break,
+            Some(next_sibling) => next_sibling
+        };
+
+        if is_of_type {
+            if element.get_local_name() == sibling.get_local_name() &&
+                element.get_namespace() == sibling.get_namespace() {
+                index += 1;
+            }
+        } else {
+          index += 1;
+        }
+        next_sibling = if is_from_end {
+            sibling.next_sibling_element()
+        } else {
+            sibling.prev_sibling_element()
+        };
+    }
+
+    if a == 0 {
+        b == index
+    } else {
+        (index - b) / a >= 0 &&
+        (index - b) % a == 0
+    }
+}
+
+#[inline]
+fn matches_first_child<E>(element: &E, reason: MatchingReason) -> bool where E: Element {
+    // Selectors Level 4 changed from Level 3:
+    // This can match without a parent element:
+    // https://drafts.csswg.org/selectors-4/#child-index
+    if reason.for_styling() {
+        if let Some(parent) = element.parent_element() {
+            parent.insert_flags(HAS_EDGE_CHILD_SELECTOR);
+        }
+    }
+    element.prev_sibling_element().is_none()
+}
+
+#[inline]
+fn matches_last_child<E>(element: &E, reason: MatchingReason) -> bool where E: Element {
+    // Selectors Level 4 changed from Level 3:
+    // This can match without a parent element:
+    // https://drafts.csswg.org/selectors-4/#child-index
+    if reason.for_styling() {
+        if let Some(parent) = element.parent_element() {
+            parent.insert_flags(HAS_EDGE_CHILD_SELECTOR);
+        }
+    }
+
+    element.next_sibling_element().is_none()
+}
diff --git a/components/selectors/parser.rs b/components/selectors/parser.rs
new file mode 100644
index 00000000000..a3862265bda
--- /dev/null
+++ b/components/selectors/parser.rs
@@ -0,0 +1,1473 @@
+/* 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 cssparser::{Token, Parser as CssParser, parse_nth, ToCss, serialize_identifier, CssStringWriter};
+use std::ascii::AsciiExt;
+use std::borrow::{Borrow, Cow};
+use std::cmp;
+use std::fmt::{self, Display, Debug, Write};
+use std::hash::Hash;
+use std::ops::Add;
+use std::sync::Arc;
+use tree::SELECTOR_WHITESPACE;
+
+macro_rules! with_all_bounds {
+    (
+        [ $( $InSelector: tt )* ]
+        [ $( $CommonBounds: tt )* ]
+        [ $( $FromStr: tt )* ]
+    ) => {
+        fn from_cow_str<T>(cow: Cow<str>) -> T where T: $($FromStr)* {
+            match cow {
+                Cow::Borrowed(s) => T::from(s),
+                Cow::Owned(s) => T::from(s),
+            }
+        }
+
+        fn from_ascii_lowercase<T>(s: &str) -> T where T: $($FromStr)* {
+            if let Some(first_uppercase) = s.bytes().position(|byte| byte >= b'A' && byte <= b'Z') {
+                let mut string = s.to_owned();
+                string[first_uppercase..].make_ascii_lowercase();
+                T::from(string)
+            } else {
+                T::from(s)
+            }
+        }
+
+        /// This trait allows to define the parser implementation in regards
+        /// of pseudo-classes/elements
+        pub trait SelectorImpl: Sized {
+            type AttrValue: $($InSelector)*;
+            type Identifier: $($InSelector)*;
+            type ClassName: $($InSelector)*;
+            type LocalName: $($InSelector)* + Borrow<Self::BorrowedLocalName>;
+            type NamespaceUrl: $($CommonBounds)* + Default + Borrow<Self::BorrowedNamespaceUrl>;
+            type NamespacePrefix: $($InSelector)* + Default;
+            type BorrowedNamespaceUrl: ?Sized + Eq;
+            type BorrowedLocalName: ?Sized + Eq + Hash;
+
+            /// non tree-structural pseudo-classes
+            /// (see: https://drafts.csswg.org/selectors/#structural-pseudos)
+            type NonTSPseudoClass: $($CommonBounds)* + Sized + ToCss;
+
+            /// pseudo-elements
+            type PseudoElement: $($CommonBounds)* + Sized + ToCss;
+
+            /// Declares if the following "attribute exists" selector is considered
+            /// "common" enough to be shareable. If that's not the case, when matching
+            /// over an element, the relation
+            /// AFFECTED_BY_NON_COMMON_STYLE_AFFECTING_ATTRIBUTE would be set.
+            fn attr_exists_selector_is_shareable(_attr_selector: &AttrSelector<Self>) -> bool {
+                false
+            }
+
+            /// Declares if the following "equals" attribute selector is considered
+            /// "common" enough to be shareable.
+            fn attr_equals_selector_is_shareable(_attr_selector: &AttrSelector<Self>,
+                                                 _value: &Self::AttrValue)
+                                                 -> bool {
+                false
+            }
+        }
+    }
+}
+
+macro_rules! with_bounds {
+    ( [ $( $CommonBounds: tt )* ] [ $( $FromStr: tt )* ]) => {
+        with_all_bounds! {
+            [$($CommonBounds)* + $($FromStr)* + Display]
+            [$($CommonBounds)*]
+            [$($FromStr)*]
+        }
+    }
+}
+
+with_bounds! {
+    [Clone + Eq + Hash]
+    [From<String> + for<'a> From<&'a str>]
+}
+
+pub trait Parser {
+    type Impl: SelectorImpl;
+
+    /// This function can return an "Err" pseudo-element in order to support CSS2.1
+    /// pseudo-elements.
+    fn parse_non_ts_pseudo_class(&self, _name: Cow<str>)
+                                 -> Result<<Self::Impl as SelectorImpl>::NonTSPseudoClass, ()> {
+        Err(())
+    }
+
+    fn parse_non_ts_functional_pseudo_class
+        (&self, _name: Cow<str>, _arguments: &mut CssParser)
+        -> Result<<Self::Impl as SelectorImpl>::NonTSPseudoClass, ()>
+    {
+        Err(())
+    }
+
+    fn parse_pseudo_element(&self, _name: Cow<str>)
+                            -> Result<<Self::Impl as SelectorImpl>::PseudoElement, ()> {
+        Err(())
+    }
+
+    fn default_namespace(&self) -> Option<<Self::Impl as SelectorImpl>::NamespaceUrl> {
+        None
+    }
+
+    fn namespace_for_prefix(&self, _prefix: &<Self::Impl as SelectorImpl>::NamespacePrefix)
+                            -> Option<<Self::Impl as SelectorImpl>::NamespaceUrl> {
+        None
+    }
+}
+
+#[derive(PartialEq, Clone, Debug)]
+pub struct SelectorList<Impl: SelectorImpl>(pub Vec<Selector<Impl>>);
+
+impl<Impl: SelectorImpl> SelectorList<Impl> {
+    /// Parse a comma-separated list of Selectors.
+    /// https://drafts.csswg.org/selectors/#grouping
+    ///
+    /// Return the Selectors or Err if there is an invalid selector.
+    pub fn parse<P>(parser: &P, input: &mut CssParser) -> Result<Self, ()>
+    where P: Parser<Impl=Impl> {
+        input.parse_comma_separated(|input| parse_selector(parser, input))
+             .map(SelectorList)
+    }
+}
+
+#[derive(PartialEq, Clone)]
+pub struct Selector<Impl: SelectorImpl> {
+    pub complex_selector: Arc<ComplexSelector<Impl>>,
+    pub pseudo_element: Option<Impl::PseudoElement>,
+    pub specificity: u32,
+}
+
+fn affects_sibling<Impl: SelectorImpl>(simple_selector: &SimpleSelector<Impl>) -> bool {
+    match *simple_selector {
+        SimpleSelector::Negation(ref negated) => {
+            negated.iter().any(|ref selector| selector.affects_siblings())
+        }
+
+        SimpleSelector::FirstChild |
+        SimpleSelector::LastChild |
+        SimpleSelector::OnlyChild |
+        SimpleSelector::NthChild(..) |
+        SimpleSelector::NthLastChild(..) |
+        SimpleSelector::NthOfType(..) |
+        SimpleSelector::NthLastOfType(..) |
+        SimpleSelector::FirstOfType |
+        SimpleSelector::LastOfType |
+        SimpleSelector::OnlyOfType => true,
+
+        _ => false,
+    }
+}
+
+fn matches_non_common_style_affecting_attribute<Impl: SelectorImpl>(simple_selector: &SimpleSelector<Impl>) -> bool {
+    match *simple_selector {
+        SimpleSelector::Negation(ref negated) => {
+            negated.iter().any(|ref selector| selector.matches_non_common_style_affecting_attribute())
+        }
+        SimpleSelector::AttrEqual(ref attr, ref val, _) => {
+            !Impl::attr_equals_selector_is_shareable(attr, val)
+        }
+        SimpleSelector::AttrExists(ref attr) => {
+            !Impl::attr_exists_selector_is_shareable(attr)
+        }
+        SimpleSelector::AttrIncludes(..) |
+        SimpleSelector::AttrDashMatch(..) |
+        SimpleSelector::AttrPrefixMatch(..) |
+        SimpleSelector::AttrSuffixMatch(..) |
+        SimpleSelector::AttrSubstringMatch(..) => true,
+
+        // This deliberately includes Attr*NeverMatch
+        // which never match regardless of element attributes.
+        _ => false,
+    }
+}
+
+impl<Impl: SelectorImpl> Selector<Impl> {
+    /// Whether this selector, if matching on a set of siblings, could affect
+    /// other sibling's style.
+    pub fn affects_siblings(&self) -> bool {
+        self.complex_selector.affects_siblings()
+    }
+
+    pub fn matches_non_common_style_affecting_attribute(&self) -> bool {
+        self.complex_selector.matches_non_common_style_affecting_attribute()
+    }
+}
+
+impl<Impl: SelectorImpl> ComplexSelector<Impl> {
+    /// Whether this complex selector, if matching on a set of siblings,
+    /// could affect other sibling's style.
+    pub fn affects_siblings(&self) -> bool {
+        match self.next {
+            Some((_, Combinator::NextSibling)) |
+            Some((_, Combinator::LaterSibling)) => return true,
+            _ => {},
+        }
+
+        match self.compound_selector.last() {
+            Some(ref selector) => affects_sibling(selector),
+            None => false,
+        }
+    }
+
+    pub fn matches_non_common_style_affecting_attribute(&self) -> bool {
+        match self.compound_selector.last() {
+            Some(ref selector) => matches_non_common_style_affecting_attribute(selector),
+            None => false,
+        }
+    }
+}
+
+#[derive(Clone, Eq, Hash, PartialEq)]
+pub struct ComplexSelector<Impl: SelectorImpl> {
+    pub compound_selector: Vec<SimpleSelector<Impl>>,
+    pub next: Option<(Arc<ComplexSelector<Impl>>, Combinator)>,  // c.next is left of c
+}
+
+#[derive(Eq, PartialEq, Clone, Copy, Debug, Hash)]
+pub enum Combinator {
+    Child,  //  >
+    Descendant,  // space
+    NextSibling,  // +
+    LaterSibling,  // ~
+}
+
+#[derive(Eq, PartialEq, Clone, Hash)]
+pub enum SimpleSelector<Impl: SelectorImpl> {
+    ID(Impl::Identifier),
+    Class(Impl::ClassName),
+    LocalName(LocalName<Impl>),
+    Namespace(Namespace<Impl>),
+
+    // Attribute selectors
+    AttrExists(AttrSelector<Impl>),  // [foo]
+    AttrEqual(AttrSelector<Impl>, Impl::AttrValue, CaseSensitivity),  // [foo=bar]
+    AttrIncludes(AttrSelector<Impl>, Impl::AttrValue),  // [foo~=bar]
+    AttrDashMatch(AttrSelector<Impl>, Impl::AttrValue), // [foo|=bar]
+    AttrPrefixMatch(AttrSelector<Impl>, Impl::AttrValue),  // [foo^=bar]
+    AttrSubstringMatch(AttrSelector<Impl>, Impl::AttrValue),  // [foo*=bar]
+    AttrSuffixMatch(AttrSelector<Impl>, Impl::AttrValue),  // [foo$=bar]
+
+    AttrIncludesNeverMatch(AttrSelector<Impl>, Impl::AttrValue),  // empty value or with whitespace
+    AttrPrefixNeverMatch(AttrSelector<Impl>, Impl::AttrValue),  // empty value
+    AttrSubstringNeverMatch(AttrSelector<Impl>, Impl::AttrValue),  // empty value
+    AttrSuffixNeverMatch(AttrSelector<Impl>, Impl::AttrValue),  // empty value
+
+    // Pseudo-classes
+    Negation(Vec<Arc<ComplexSelector<Impl>>>),
+    FirstChild, LastChild, OnlyChild,
+    Root,
+    Empty,
+    NthChild(i32, i32),
+    NthLastChild(i32, i32),
+    NthOfType(i32, i32),
+    NthLastOfType(i32, i32),
+    FirstOfType,
+    LastOfType,
+    OnlyOfType,
+    NonTSPseudoClass(Impl::NonTSPseudoClass),
+    // ...
+}
+
+#[derive(Eq, PartialEq, Clone, Hash, Copy, Debug)]
+pub enum CaseSensitivity {
+    CaseSensitive,  // Selectors spec says language-defined, but HTML says sensitive.
+    CaseInsensitive,
+}
+
+
+#[derive(Eq, PartialEq, Clone, Hash)]
+pub struct LocalName<Impl: SelectorImpl> {
+    pub name: Impl::LocalName,
+    pub lower_name: Impl::LocalName,
+}
+
+#[derive(Eq, PartialEq, Clone, Hash)]
+pub struct AttrSelector<Impl: SelectorImpl> {
+    pub name: Impl::LocalName,
+    pub lower_name: Impl::LocalName,
+    pub namespace: NamespaceConstraint<Impl>,
+}
+
+#[derive(Eq, PartialEq, Clone, Hash, Debug)]
+pub enum NamespaceConstraint<Impl: SelectorImpl> {
+    Any,
+    Specific(Namespace<Impl>),
+}
+
+/// FIXME(SimonSapin): should Hash only hash the URL? What is it used for?
+#[derive(Eq, PartialEq, Clone, Hash)]
+pub struct Namespace<Impl: SelectorImpl> {
+    pub prefix: Option<Impl::NamespacePrefix>,
+    pub url: Impl::NamespaceUrl,
+}
+
+impl<Impl: SelectorImpl> Default for Namespace<Impl> {
+    fn default() -> Self {
+        Namespace {
+            prefix: None,
+            url: Impl::NamespaceUrl::default(),  // empty string
+        }
+    }
+}
+
+
+impl<Impl: SelectorImpl> Debug for Selector<Impl> {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        f.write_str("Selector(")?;
+        self.to_css(f)?;
+        write!(f, ", specificity = 0x{:x})", self.specificity)
+    }
+}
+
+impl<Impl: SelectorImpl> Debug for ComplexSelector<Impl> {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { self.to_css(f) }
+}
+impl<Impl: SelectorImpl> Debug for SimpleSelector<Impl> {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { self.to_css(f) }
+}
+impl<Impl: SelectorImpl> Debug for AttrSelector<Impl> {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { self.to_css(f) }
+}
+impl<Impl: SelectorImpl> Debug for Namespace<Impl> {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { self.to_css(f) }
+}
+impl<Impl: SelectorImpl> Debug for LocalName<Impl> {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { self.to_css(f) }
+}
+
+impl<Impl: SelectorImpl> ToCss for SelectorList<Impl> {
+    fn to_css<W>(&self, dest: &mut W) -> fmt::Result where W: fmt::Write {
+        let mut iter = self.0.iter();
+        let first = iter.next()
+            .expect("Empty SelectorList, should contain at least one selector");
+        first.to_css(dest)?;
+        for selector in iter {
+            dest.write_str(", ")?;
+            selector.to_css(dest)?;
+        }
+        Ok(())
+    }
+}
+
+impl<Impl: SelectorImpl> ToCss for Selector<Impl> {
+    fn to_css<W>(&self, dest: &mut W) -> fmt::Result where W: fmt::Write {
+        self.complex_selector.to_css(dest)?;
+        if let Some(ref pseudo) = self.pseudo_element {
+            pseudo.to_css(dest)?;
+        }
+        Ok(())
+    }
+}
+
+impl<Impl: SelectorImpl> ToCss for ComplexSelector<Impl> {
+    fn to_css<W>(&self, dest: &mut W) -> fmt::Result where W: fmt::Write {
+        if let Some((ref next, ref combinator)) = self.next {
+            next.to_css(dest)?;
+            combinator.to_css(dest)?;
+        }
+        for simple in &self.compound_selector {
+            simple.to_css(dest)?;
+        }
+        Ok(())
+    }
+}
+
+impl ToCss for Combinator {
+    fn to_css<W>(&self, dest: &mut W) -> fmt::Result where W: fmt::Write {
+        match *self {
+            Combinator::Child => dest.write_str(" > "),
+            Combinator::Descendant => dest.write_str(" "),
+            Combinator::NextSibling => dest.write_str(" + "),
+            Combinator::LaterSibling => dest.write_str(" ~ "),
+        }
+    }
+}
+
+impl<Impl: SelectorImpl> ToCss for SimpleSelector<Impl> {
+    fn to_css<W>(&self, dest: &mut W) -> fmt::Result where W: fmt::Write {
+        use self::SimpleSelector::*;
+        match *self {
+            ID(ref s) => {
+                dest.write_char('#')?;
+                display_to_css_identifier(s, dest)
+            }
+            Class(ref s) => {
+                dest.write_char('.')?;
+                display_to_css_identifier(s, dest)
+            }
+            LocalName(ref s) => s.to_css(dest),
+            Namespace(ref ns) => ns.to_css(dest),
+
+            // Attribute selectors
+            AttrExists(ref a) => {
+                dest.write_char('[')?;
+                a.to_css(dest)?;
+                dest.write_char(']')
+            }
+            AttrEqual(ref a, ref v, case) => {
+                attr_selector_to_css(a, " = ", v, match case {
+                    CaseSensitivity::CaseSensitive => None,
+                    CaseSensitivity::CaseInsensitive => Some(" i"),
+                 }, dest)
+            }
+            AttrDashMatch(ref a, ref v) => attr_selector_to_css(a, " |= ", v, None, dest),
+            AttrIncludesNeverMatch(ref a, ref v) |
+            AttrIncludes(ref a, ref v) => attr_selector_to_css(a, " ~= ", v, None, dest),
+            AttrPrefixNeverMatch(ref a, ref v) |
+            AttrPrefixMatch(ref a, ref v) => attr_selector_to_css(a, " ^= ", v, None, dest),
+            AttrSubstringNeverMatch(ref a, ref v) |
+            AttrSubstringMatch(ref a, ref v) => attr_selector_to_css(a, " *= ", v, None, dest),
+            AttrSuffixNeverMatch(ref a, ref v) |
+            AttrSuffixMatch(ref a, ref v) => attr_selector_to_css(a, " $= ", v, None, dest),
+
+            // Pseudo-classes
+            Negation(ref args) => {
+                dest.write_str(":not(")?;
+                let mut args = args.iter();
+                let first = args.next().unwrap();
+                first.to_css(dest)?;
+                for arg in args {
+                    dest.write_str(", ")?;
+                    arg.to_css(dest)?;
+                }
+                dest.write_str(")")
+            }
+
+            FirstChild => dest.write_str(":first-child"),
+            LastChild => dest.write_str(":last-child"),
+            OnlyChild => dest.write_str(":only-child"),
+            Root => dest.write_str(":root"),
+            Empty => dest.write_str(":empty"),
+            FirstOfType => dest.write_str(":first-of-type"),
+            LastOfType => dest.write_str(":last-of-type"),
+            OnlyOfType => dest.write_str(":only-of-type"),
+            NthChild(a, b) => write!(dest, ":nth-child({}n{:+})", a, b),
+            NthLastChild(a, b) => write!(dest, ":nth-last-child({}n{:+})", a, b),
+            NthOfType(a, b) => write!(dest, ":nth-of-type({}n{:+})", a, b),
+            NthLastOfType(a, b) => write!(dest, ":nth-last-of-type({}n{:+})", a, b),
+            NonTSPseudoClass(ref pseudo) => pseudo.to_css(dest),
+        }
+    }
+}
+
+impl<Impl: SelectorImpl> ToCss for AttrSelector<Impl> {
+    fn to_css<W>(&self, dest: &mut W) -> fmt::Result where W: fmt::Write {
+        if let NamespaceConstraint::Specific(ref ns) = self.namespace {
+            ns.to_css(dest)?;
+        }
+        display_to_css_identifier(&self.name, dest)
+    }
+}
+
+impl<Impl: SelectorImpl> ToCss for Namespace<Impl> {
+    fn to_css<W>(&self, dest: &mut W) -> fmt::Result where W: fmt::Write {
+        if let Some(ref prefix) = self.prefix {
+            display_to_css_identifier(prefix, dest)?;
+            dest.write_char('|')?;
+        }
+        Ok(())
+    }
+}
+
+impl<Impl: SelectorImpl> ToCss for LocalName<Impl> {
+    fn to_css<W>(&self, dest: &mut W) -> fmt::Result where W: fmt::Write {
+        display_to_css_identifier(&self.name, dest)
+    }
+}
+
+fn attr_selector_to_css<Impl, W>(attr: &AttrSelector<Impl>,
+                                 operator: &str,
+                                 value: &Impl::AttrValue,
+                                 modifier: Option<&str>,
+                                 dest: &mut W)
+                                 -> fmt::Result
+where Impl: SelectorImpl, W: fmt::Write
+{
+    dest.write_char('[')?;
+    attr.to_css(dest)?;
+    dest.write_str(operator)?;
+    dest.write_char('"')?;
+    write!(CssStringWriter::new(dest), "{}", value)?;
+    dest.write_char('"')?;
+    if let Some(m) = modifier {
+        dest.write_str(m)?;
+    }
+    dest.write_char(']')
+}
+
+/// Serialize the output of Display as a CSS identifier
+fn display_to_css_identifier<T: Display, W: fmt::Write>(x: &T, dest: &mut W) -> fmt::Result {
+    // FIXME(SimonSapin): it is possible to avoid this heap allocation
+    // by creating a stream adapter like cssparser::CssStringWriter
+    // that holds and writes to `&mut W` and itself implements `fmt::Write`.
+    //
+    // I haven’t done this yet because it would require somewhat complex and fragile state machine
+    // to support in `fmt::Write::write_char` cases that,
+    // in `serialize_identifier` (which has the full value as a `&str` slice),
+    // can be expressed as
+    // `string.starts_with("--")`, `string == "-"`, `string.starts_with("-")`, etc.
+    //
+    // And I don’t even know if this would be a performance win: jemalloc is good at what it does
+    // and the state machine might be slower than `serialize_identifier` as currently written.
+    let string = x.to_string();
+
+    serialize_identifier(&string, dest)
+}
+
+const MAX_10BIT: u32 = (1u32 << 10) - 1;
+
+#[derive(Clone, Copy, Eq, Ord, PartialEq, PartialOrd)]
+struct Specificity {
+    id_selectors: u32,
+    class_like_selectors: u32,
+    element_selectors: u32,
+}
+
+impl Add for Specificity {
+    type Output = Specificity;
+
+    fn add(self, rhs: Specificity) -> Specificity {
+        Specificity {
+            id_selectors: self.id_selectors + rhs.id_selectors,
+            class_like_selectors:
+                self.class_like_selectors + rhs.class_like_selectors,
+            element_selectors:
+                self.element_selectors + rhs.element_selectors,
+        }
+    }
+}
+
+impl Default for Specificity {
+    fn default() -> Specificity {
+        Specificity {
+            id_selectors: 0,
+            class_like_selectors: 0,
+            element_selectors: 0,
+        }
+    }
+}
+
+impl From<u32> for Specificity {
+    fn from(value: u32) -> Specificity {
+        assert!(value <= MAX_10BIT << 20 | MAX_10BIT << 10 | MAX_10BIT);
+        Specificity {
+            id_selectors: value >> 20,
+            class_like_selectors: (value >> 10) & MAX_10BIT,
+            element_selectors: value & MAX_10BIT,
+        }
+    }
+}
+
+impl From<Specificity> for u32 {
+    fn from(specificity: Specificity) -> u32 {
+        cmp::min(specificity.id_selectors, MAX_10BIT) << 20
+        | cmp::min(specificity.class_like_selectors, MAX_10BIT) << 10
+        | cmp::min(specificity.element_selectors, MAX_10BIT)
+    }
+}
+
+fn specificity<Impl>(complex_selector: &ComplexSelector<Impl>,
+                     pseudo_element: Option<&Impl::PseudoElement>)
+                     -> u32
+				     where Impl: SelectorImpl {
+    let mut specificity = complex_selector_specificity(complex_selector);
+    if pseudo_element.is_some() {
+        specificity.element_selectors += 1;
+    }
+    specificity.into()
+}
+
+fn complex_selector_specificity<Impl>(mut selector: &ComplexSelector<Impl>)
+                                      -> Specificity
+                                      where Impl: SelectorImpl {
+    fn compound_selector_specificity<Impl>(compound_selector: &[SimpleSelector<Impl>],
+                                           specificity: &mut Specificity)
+                                           where Impl: SelectorImpl {
+        for simple_selector in compound_selector.iter() {
+            match *simple_selector {
+                SimpleSelector::LocalName(..) =>
+                    specificity.element_selectors += 1,
+                SimpleSelector::ID(..) =>
+                    specificity.id_selectors += 1,
+                SimpleSelector::Class(..) |
+                SimpleSelector::AttrExists(..) |
+                SimpleSelector::AttrEqual(..) |
+                SimpleSelector::AttrIncludes(..) |
+                SimpleSelector::AttrDashMatch(..) |
+                SimpleSelector::AttrPrefixMatch(..) |
+                SimpleSelector::AttrSubstringMatch(..) |
+                SimpleSelector::AttrSuffixMatch(..) |
+
+                SimpleSelector::AttrIncludesNeverMatch(..) |
+                SimpleSelector::AttrPrefixNeverMatch(..) |
+                SimpleSelector::AttrSubstringNeverMatch(..) |
+                SimpleSelector::AttrSuffixNeverMatch(..) |
+
+                SimpleSelector::FirstChild | SimpleSelector::LastChild |
+                SimpleSelector::OnlyChild | SimpleSelector::Root |
+                SimpleSelector::Empty |
+                SimpleSelector::NthChild(..) |
+                SimpleSelector::NthLastChild(..) |
+                SimpleSelector::NthOfType(..) |
+                SimpleSelector::NthLastOfType(..) |
+                SimpleSelector::FirstOfType | SimpleSelector::LastOfType |
+                SimpleSelector::OnlyOfType |
+                SimpleSelector::NonTSPseudoClass(..) =>
+                    specificity.class_like_selectors += 1,
+
+                SimpleSelector::Namespace(..) => (),
+                SimpleSelector::Negation(ref negated) => {
+                    let max =
+                        negated.iter().map(|s| complex_selector_specificity(&s))
+                               .max().unwrap();
+                    *specificity = *specificity + max;
+                }
+            }
+        }
+    }
+
+    let mut specificity = Default::default();
+    compound_selector_specificity(&selector.compound_selector,
+                              &mut specificity);
+    loop {
+        match selector.next {
+            None => break,
+            Some((ref next_selector, _)) => {
+                selector = &**next_selector;
+                compound_selector_specificity(&selector.compound_selector,
+                                          &mut specificity)
+            }
+        }
+    }
+    specificity
+}
+
+/// Build up a Selector.
+/// selector : simple_selector_sequence [ combinator simple_selector_sequence ]* ;
+///
+/// `Err` means invalid selector.
+fn parse_selector<P, Impl>(parser: &P, input: &mut CssParser) -> Result<Selector<Impl>, ()>
+    where P: Parser<Impl=Impl>, Impl: SelectorImpl
+{
+    let (complex, pseudo_element) =
+        parse_complex_selector_and_pseudo_element(parser, input)?;
+    Ok(Selector {
+        specificity: specificity(&complex, pseudo_element.as_ref()),
+        complex_selector: Arc::new(complex),
+        pseudo_element: pseudo_element,
+    })
+}
+
+fn parse_complex_selector_and_pseudo_element<P, Impl>(
+        parser: &P,
+        input: &mut CssParser)
+        -> Result<(ComplexSelector<Impl>, Option<Impl::PseudoElement>), ()>
+    where P: Parser<Impl=Impl>, Impl: SelectorImpl
+{
+    let (first, mut pseudo_element) = parse_compound_selector(parser, input)?;
+    let mut complex = ComplexSelector{ compound_selector: first, next: None };
+
+    'outer_loop: while pseudo_element.is_none() {
+        let combinator;
+        let mut any_whitespace = false;
+        loop {
+            let position = input.position();
+            match input.next_including_whitespace() {
+                Err(()) => break 'outer_loop,
+                Ok(Token::WhiteSpace(_)) => any_whitespace = true,
+                Ok(Token::Delim('>')) => {
+                    combinator = Combinator::Child;
+                    break
+                }
+                Ok(Token::Delim('+')) => {
+                    combinator = Combinator::NextSibling;
+                    break
+                }
+                Ok(Token::Delim('~')) => {
+                    combinator = Combinator::LaterSibling;
+                    break
+                }
+                Ok(_) => {
+                    input.reset(position);
+                    if any_whitespace {
+                        combinator = Combinator::Descendant;
+                        break
+                    } else {
+                        break 'outer_loop
+                    }
+                }
+            }
+        }
+        let (compound_selector, pseudo) = parse_compound_selector(parser, input)?;
+        complex = ComplexSelector {
+            compound_selector: compound_selector,
+            next: Some((Arc::new(complex), combinator))
+        };
+        pseudo_element = pseudo;
+    }
+
+    Ok((complex, pseudo_element))
+}
+
+fn parse_complex_selector<P, Impl>(
+        parser: &P,
+        input: &mut CssParser)
+        -> Result<ComplexSelector<Impl>, ()>
+    where P: Parser<Impl=Impl>, Impl: SelectorImpl
+{
+    let (complex, pseudo_element) =
+        parse_complex_selector_and_pseudo_element(parser, input)?;
+    if pseudo_element.is_some() {
+        return Err(())
+    }
+    Ok(complex)
+}
+
+/// * `Err(())`: Invalid selector, abort
+/// * `Ok(None)`: Not a type selector, could be something else. `input` was not consumed.
+/// * `Ok(Some(vec))`: Length 0 (`*|*`), 1 (`*|E` or `ns|*`) or 2 (`|E` or `ns|E`)
+fn parse_type_selector<P, Impl>(parser: &P, input: &mut CssParser)
+                       -> Result<Option<Vec<SimpleSelector<Impl>>>, ()>
+    where P: Parser<Impl=Impl>, Impl: SelectorImpl
+{
+    match parse_qualified_name(parser, input, /* in_attr_selector = */ false)? {
+        None => Ok(None),
+        Some((namespace, local_name)) => {
+            let mut compound_selector = vec!();
+            match namespace {
+                NamespaceConstraint::Specific(ns) => {
+                    compound_selector.push(SimpleSelector::Namespace(ns))
+                },
+                NamespaceConstraint::Any => (),
+            }
+            match local_name {
+                Some(name) => {
+                    compound_selector.push(SimpleSelector::LocalName(LocalName {
+                        lower_name: from_ascii_lowercase(&name),
+                        name: from_cow_str(name),
+                    }))
+                }
+                None => (),
+            }
+            Ok(Some(compound_selector))
+        }
+    }
+}
+
+#[derive(Debug)]
+enum SimpleSelectorParseResult<Impl: SelectorImpl> {
+    SimpleSelector(SimpleSelector<Impl>),
+    PseudoElement(Impl::PseudoElement),
+}
+
+/// * `Err(())`: Invalid selector, abort
+/// * `Ok(None)`: Not a simple selector, could be something else. `input` was not consumed.
+/// * `Ok(Some((namespace, local_name)))`: `None` for the local name means a `*` universal selector
+fn parse_qualified_name<'i, 't, P, Impl>
+                       (parser: &P, input: &mut CssParser<'i, 't>,
+                        in_attr_selector: bool)
+                        -> Result<Option<(NamespaceConstraint<Impl>, Option<Cow<'i, str>>)>, ()>
+    where P: Parser<Impl=Impl>, Impl: SelectorImpl
+{
+    let default_namespace = |local_name| {
+        let namespace = match parser.default_namespace() {
+            Some(url) => NamespaceConstraint::Specific(Namespace {
+                prefix: None,
+                url: url
+            }),
+            None => NamespaceConstraint::Any,
+        };
+        Ok(Some((namespace, local_name)))
+    };
+
+    let explicit_namespace = |input: &mut CssParser<'i, 't>, namespace| {
+        match input.next_including_whitespace() {
+            Ok(Token::Delim('*')) if !in_attr_selector => {
+                Ok(Some((namespace, None)))
+            },
+            Ok(Token::Ident(local_name)) => {
+                Ok(Some((namespace, Some(local_name))))
+            },
+            _ => Err(()),
+        }
+    };
+
+    let position = input.position();
+    match input.next_including_whitespace() {
+        Ok(Token::Ident(value)) => {
+            let position = input.position();
+            match input.next_including_whitespace() {
+                Ok(Token::Delim('|')) => {
+                    let prefix = from_cow_str(value);
+                    let result = parser.namespace_for_prefix(&prefix);
+                    let url = result.ok_or(())?;
+                    explicit_namespace(input, NamespaceConstraint::Specific(Namespace {
+                        prefix: Some(prefix),
+                        url: url
+                    }))
+                },
+                _ => {
+                    input.reset(position);
+                    if in_attr_selector {
+                        Ok(Some((NamespaceConstraint::Specific(Default::default()), Some(value))))
+                    } else {
+                        default_namespace(Some(value))
+                    }
+                }
+            }
+        },
+        Ok(Token::Delim('*')) => {
+            let position = input.position();
+            match input.next_including_whitespace() {
+                Ok(Token::Delim('|')) => explicit_namespace(input, NamespaceConstraint::Any),
+                _ => {
+                    input.reset(position);
+                    if in_attr_selector {
+                        Err(())
+                    } else {
+                        default_namespace(None)
+                    }
+                },
+            }
+        },
+        Ok(Token::Delim('|')) => {
+            explicit_namespace(input, NamespaceConstraint::Specific(Default::default()))
+        }
+        _ => {
+            input.reset(position);
+            Ok(None)
+        }
+    }
+}
+
+
+fn parse_attribute_selector<P, Impl>(parser: &P, input: &mut CssParser)
+                                     -> Result<SimpleSelector<Impl>, ()>
+    where P: Parser<Impl=Impl>, Impl: SelectorImpl
+{
+    let attr = match parse_qualified_name(parser, input, /* in_attr_selector = */ true)? {
+        None => return Err(()),
+        Some((_, None)) => unreachable!(),
+        Some((namespace, Some(local_name))) => AttrSelector {
+            namespace: namespace,
+            lower_name: from_ascii_lowercase(&local_name),
+            name: from_cow_str(local_name),
+        },
+    };
+
+    match input.next() {
+        // [foo]
+        Err(()) => Ok(SimpleSelector::AttrExists(attr)),
+
+        // [foo=bar]
+        Ok(Token::Delim('=')) => {
+            let value = input.expect_ident_or_string()?;
+            let flags = parse_attribute_flags(input)?;
+            Ok(SimpleSelector::AttrEqual(attr, from_cow_str(value), flags))
+        }
+        // [foo~=bar]
+        Ok(Token::IncludeMatch) => {
+            let value = input.expect_ident_or_string()?;
+            if value.is_empty() || value.contains(SELECTOR_WHITESPACE) {
+                Ok(SimpleSelector::AttrIncludesNeverMatch(attr, from_cow_str(value)))
+            } else {
+                Ok(SimpleSelector::AttrIncludes(attr, from_cow_str(value)))
+            }
+        }
+        // [foo|=bar]
+        Ok(Token::DashMatch) => {
+            let value = input.expect_ident_or_string()?;
+            Ok(SimpleSelector::AttrDashMatch(attr, from_cow_str(value)))
+        }
+        // [foo^=bar]
+        Ok(Token::PrefixMatch) => {
+            let value = input.expect_ident_or_string()?;
+            if value.is_empty() {
+                Ok(SimpleSelector::AttrPrefixNeverMatch(attr, from_cow_str(value)))
+            } else {
+                Ok(SimpleSelector::AttrPrefixMatch(attr, from_cow_str(value)))
+            }
+        }
+        // [foo*=bar]
+        Ok(Token::SubstringMatch) => {
+            let value = input.expect_ident_or_string()?;
+            if value.is_empty() {
+                Ok(SimpleSelector::AttrSubstringNeverMatch(attr, from_cow_str(value)))
+            } else {
+                Ok(SimpleSelector::AttrSubstringMatch(attr, from_cow_str(value)))
+            }
+        }
+        // [foo$=bar]
+        Ok(Token::SuffixMatch) => {
+            let value = input.expect_ident_or_string()?;
+            if value.is_empty() {
+                Ok(SimpleSelector::AttrSuffixNeverMatch(attr, from_cow_str(value)))
+            } else {
+                Ok(SimpleSelector::AttrSuffixMatch(attr, from_cow_str(value)))
+            }
+        }
+        _ => Err(())
+    }
+}
+
+
+fn parse_attribute_flags(input: &mut CssParser) -> Result<CaseSensitivity, ()> {
+    match input.next() {
+        Err(()) => Ok(CaseSensitivity::CaseSensitive),
+        Ok(Token::Ident(ref value)) if value.eq_ignore_ascii_case("i") => {
+            Ok(CaseSensitivity::CaseInsensitive)
+        }
+        _ => Err(())
+    }
+}
+
+
+/// Level 3: Parse **one** simple_selector.  (Though we might insert a second
+/// implied "<defaultns>|*" type selector.)
+fn parse_negation<P, Impl>(parser: &P,
+                           input: &mut CssParser)
+                           -> Result<SimpleSelector<Impl>, ()>
+    where P: Parser<Impl=Impl>, Impl: SelectorImpl
+{
+    input.parse_comma_separated(|input| parse_complex_selector(parser, input).map(Arc::new))
+         .map(SimpleSelector::Negation)
+}
+
+/// simple_selector_sequence
+/// : [ type_selector | universal ] [ HASH | class | attrib | pseudo | negation ]*
+/// | [ HASH | class | attrib | pseudo | negation ]+
+///
+/// `Err(())` means invalid selector
+fn parse_compound_selector<P, Impl>(
+    parser: &P,
+    input: &mut CssParser)
+    -> Result<(Vec<SimpleSelector<Impl>>, Option<Impl::PseudoElement>), ()>
+    where P: Parser<Impl=Impl>, Impl: SelectorImpl
+{
+    // Consume any leading whitespace.
+    loop {
+        let position = input.position();
+        if !matches!(input.next_including_whitespace(), Ok(Token::WhiteSpace(_))) {
+            input.reset(position);
+            break
+        }
+    }
+    let mut empty = true;
+    let mut compound_selector = match parse_type_selector(parser, input)? {
+        None => {
+            match parser.default_namespace() {
+                // If there was no explicit type selector, but there is a
+                // default namespace, there is an implicit "<defaultns>|*" type
+                // selector.
+                Some(url) => vec![SimpleSelector::Namespace(Namespace {
+                    prefix: None,
+                    url: url
+                })],
+                None => vec![],
+            }
+        }
+        Some(s) => { empty = false; s }
+    };
+
+    let mut pseudo_element = None;
+    loop {
+        match parse_one_simple_selector(parser, input, /* inside_negation = */ false)? {
+            None => break,
+            Some(SimpleSelectorParseResult::SimpleSelector(s)) => {
+                compound_selector.push(s);
+                empty = false
+            }
+            Some(SimpleSelectorParseResult::PseudoElement(p)) => {
+                pseudo_element = Some(p);
+                empty = false;
+                break
+            }
+        }
+    }
+    if empty {
+        // An empty selector is invalid.
+        Err(())
+    } else {
+        Ok((compound_selector, pseudo_element))
+    }
+}
+
+fn parse_functional_pseudo_class<P, Impl>(parser: &P,
+                                          input: &mut CssParser,
+                                          name: Cow<str>,
+                                          inside_negation: bool)
+                                          -> Result<SimpleSelector<Impl>, ()>
+    where P: Parser<Impl=Impl>, Impl: SelectorImpl
+{
+    match_ignore_ascii_case! { &name,
+        "nth-child" => return parse_nth_pseudo_class(input, SimpleSelector::NthChild),
+        "nth-of-type" => return parse_nth_pseudo_class(input, SimpleSelector::NthOfType),
+        "nth-last-child" => return parse_nth_pseudo_class(input, SimpleSelector::NthLastChild),
+        "nth-last-of-type" => return parse_nth_pseudo_class(input, SimpleSelector::NthLastOfType),
+        "not" => {
+            if inside_negation {
+                return Err(())
+            } else {
+                return parse_negation(parser, input)
+            }
+        },
+        _ => {}
+    }
+    P::parse_non_ts_functional_pseudo_class(parser, name, input)
+        .map(SimpleSelector::NonTSPseudoClass)
+}
+
+
+fn parse_nth_pseudo_class<Impl, F>(input: &mut CssParser, selector: F)
+                                   -> Result<SimpleSelector<Impl>, ()>
+where Impl: SelectorImpl, F: FnOnce(i32, i32) -> SimpleSelector<Impl> {
+    let (a, b) = parse_nth(input)?;
+    Ok(selector(a, b))
+}
+
+
+/// Parse a simple selector other than a type selector.
+///
+/// * `Err(())`: Invalid selector, abort
+/// * `Ok(None)`: Not a simple selector, could be something else. `input` was not consumed.
+/// * `Ok(Some(_))`: Parsed a simple selector or pseudo-element
+fn parse_one_simple_selector<P, Impl>(parser: &P,
+                                      input: &mut CssParser,
+                                      inside_negation: bool)
+                                      -> Result<Option<SimpleSelectorParseResult<Impl>>, ()>
+    where P: Parser<Impl=Impl>, Impl: SelectorImpl
+{
+    let start_position = input.position();
+    match input.next_including_whitespace() {
+        Ok(Token::IDHash(id)) => {
+            let id = SimpleSelector::ID(from_cow_str(id));
+            Ok(Some(SimpleSelectorParseResult::SimpleSelector(id)))
+        }
+        Ok(Token::Delim('.')) => {
+            match input.next_including_whitespace() {
+                Ok(Token::Ident(class)) => {
+                    let class = SimpleSelector::Class(from_cow_str(class));
+                    Ok(Some(SimpleSelectorParseResult::SimpleSelector(class)))
+                }
+                _ => Err(()),
+            }
+        }
+        Ok(Token::SquareBracketBlock) => {
+            let attr = input.parse_nested_block(|input| parse_attribute_selector(parser, input))?;
+            Ok(Some(SimpleSelectorParseResult::SimpleSelector(attr)))
+        }
+        Ok(Token::Colon) => {
+            match input.next_including_whitespace() {
+                Ok(Token::Ident(name)) => {
+                    // Supported CSS 2.1 pseudo-elements only.
+                    // ** Do not add to this list! **
+                    if name.eq_ignore_ascii_case("before") ||
+                       name.eq_ignore_ascii_case("after") ||
+                       name.eq_ignore_ascii_case("first-line") ||
+                       name.eq_ignore_ascii_case("first-letter") {
+                        let pseudo_element = P::parse_pseudo_element(parser, name)?;
+                        Ok(Some(SimpleSelectorParseResult::PseudoElement(pseudo_element)))
+                    } else {
+                        let pseudo_class = parse_simple_pseudo_class(parser, name)?;
+                        Ok(Some(SimpleSelectorParseResult::SimpleSelector(pseudo_class)))
+                    }
+                }
+                Ok(Token::Function(name)) => {
+                    let pseudo = input.parse_nested_block(|input| {
+                        parse_functional_pseudo_class(parser, input, name, inside_negation)
+                    })?;
+                    Ok(Some(SimpleSelectorParseResult::SimpleSelector(pseudo)))
+                }
+                Ok(Token::Colon) => {
+                    match input.next_including_whitespace() {
+                        Ok(Token::Ident(name)) => {
+                            let pseudo = P::parse_pseudo_element(parser, name)?;
+                            Ok(Some(SimpleSelectorParseResult::PseudoElement(pseudo)))
+                        }
+                        _ => Err(())
+                    }
+                }
+                _ => Err(())
+            }
+        }
+        _ => {
+            input.reset(start_position);
+            Ok(None)
+        }
+    }
+}
+
+fn parse_simple_pseudo_class<P, Impl>(parser: &P, name: Cow<str>) -> Result<SimpleSelector<Impl>, ()>
+    where P: Parser<Impl=Impl>, Impl: SelectorImpl
+{
+    (match_ignore_ascii_case! { &name,
+        "first-child" => Ok(SimpleSelector::FirstChild),
+        "last-child"  => Ok(SimpleSelector::LastChild),
+        "only-child"  => Ok(SimpleSelector::OnlyChild),
+        "root" => Ok(SimpleSelector::Root),
+        "empty" => Ok(SimpleSelector::Empty),
+        "first-of-type" => Ok(SimpleSelector::FirstOfType),
+        "last-of-type"  => Ok(SimpleSelector::LastOfType),
+        "only-of-type"  => Ok(SimpleSelector::OnlyOfType),
+        _ => Err(())
+    }).or_else(|()| {
+        P::parse_non_ts_pseudo_class(parser, name).map(|pc| SimpleSelector::NonTSPseudoClass(pc))
+    })
+}
+
+// NB: pub module in order to access the DummyParser
+#[cfg(test)]
+pub mod tests {
+    use std::borrow::Cow;
+    use std::collections::HashMap;
+    use std::fmt;
+    use std::sync::Arc;
+    use cssparser::{Parser as CssParser, ToCss, serialize_identifier};
+    use super::*;
+
+    #[derive(PartialEq, Clone, Debug, Hash, Eq)]
+    pub enum PseudoClass {
+        Hover,
+        Lang(String),
+    }
+
+    #[derive(Eq, PartialEq, Clone, Debug, Hash)]
+    pub enum PseudoElement {
+        Before,
+        After,
+    }
+
+    impl ToCss for PseudoClass {
+        fn to_css<W>(&self, dest: &mut W) -> fmt::Result where W: fmt::Write {
+            match *self {
+                PseudoClass::Hover => dest.write_str(":hover"),
+                PseudoClass::Lang(ref lang) => {
+                    dest.write_str(":lang(")?;
+                    serialize_identifier(lang, dest)?;
+                    dest.write_char(')')
+                }
+            }
+        }
+    }
+
+    impl ToCss for PseudoElement {
+        fn to_css<W>(&self, dest: &mut W) -> fmt::Result where W: fmt::Write {
+            match *self {
+                PseudoElement::Before => dest.write_str("::before"),
+                PseudoElement::After => dest.write_str("::after"),
+            }
+        }
+    }
+
+    #[derive(PartialEq, Debug)]
+    pub struct DummySelectorImpl;
+
+    #[derive(Default)]
+    pub struct DummyParser {
+        default_ns: Option<String>,
+        ns_prefixes: HashMap<String, String>,
+    }
+
+    impl SelectorImpl for DummySelectorImpl {
+        type AttrValue = String;
+        type Identifier = String;
+        type ClassName = String;
+        type LocalName = String;
+        type NamespaceUrl = String;
+        type NamespacePrefix = String;
+        type BorrowedLocalName = str;
+        type BorrowedNamespaceUrl = str;
+        type NonTSPseudoClass = PseudoClass;
+        type PseudoElement = PseudoElement;
+    }
+
+    impl Parser for DummyParser {
+        type Impl = DummySelectorImpl;
+
+        fn parse_non_ts_pseudo_class(&self, name: Cow<str>)
+                                     -> Result<PseudoClass, ()> {
+            match_ignore_ascii_case! { &name,
+                "hover" => Ok(PseudoClass::Hover),
+                _ => Err(())
+            }
+        }
+
+        fn parse_non_ts_functional_pseudo_class(&self, name: Cow<str>,
+                                                parser: &mut CssParser)
+                                                -> Result<PseudoClass, ()> {
+            match_ignore_ascii_case! { &name,
+                "lang" => Ok(PseudoClass::Lang(try!(parser.expect_ident_or_string()).into_owned())),
+                _ => Err(())
+            }
+        }
+
+        fn parse_pseudo_element(&self, name: Cow<str>)
+                                -> Result<PseudoElement, ()> {
+            match_ignore_ascii_case! { &name,
+                "before" => Ok(PseudoElement::Before),
+                "after" => Ok(PseudoElement::After),
+                _ => Err(())
+            }
+        }
+
+        fn default_namespace(&self) -> Option<String> {
+            self.default_ns.clone()
+        }
+
+        fn namespace_for_prefix(&self, prefix: &String) -> Option<String> {
+            self.ns_prefixes.get(prefix).cloned()
+        }
+    }
+
+    fn parse(input: &str) -> Result<SelectorList<DummySelectorImpl>, ()> {
+        parse_ns(input, &DummyParser::default())
+    }
+
+    fn parse_ns(input: &str, parser: &DummyParser)
+                -> Result<SelectorList<DummySelectorImpl>, ()> {
+        let result = SelectorList::parse(parser, &mut CssParser::new(input));
+        if let Ok(ref selectors) = result {
+            assert_eq!(selectors.0.len(), 1);
+            assert_eq!(selectors.0[0].to_css_string(), input);
+        }
+        result
+    }
+
+    fn specificity(a: u32, b: u32, c: u32) -> u32 {
+        a << 20 | b << 10 | c
+    }
+
+    #[test]
+    fn test_empty() {
+        let list = SelectorList::parse(&DummyParser::default(), &mut CssParser::new(":empty"));
+        assert!(list.is_ok());
+    }
+
+    const MATHML: &'static str = "http://www.w3.org/1998/Math/MathML";
+    const SVG: &'static str = "http://www.w3.org/2000/svg";
+
+    #[test]
+    fn test_parsing() {
+        assert_eq!(parse(""), Err(())) ;
+        assert_eq!(parse(":lang(4)"), Err(())) ;
+        assert_eq!(parse(":lang(en US)"), Err(())) ;
+        assert_eq!(parse("EeÉ"), Ok(SelectorList(vec!(Selector {
+            complex_selector: Arc::new(ComplexSelector {
+                compound_selector: vec!(SimpleSelector::LocalName(LocalName {
+                    name: String::from("EeÉ"),
+                    lower_name: String::from("eeÉ") })),
+                next: None,
+            }),
+            pseudo_element: None,
+            specificity: specificity(0, 0, 1),
+        }))));
+        assert_eq!(parse(".foo:lang(en-US)"), Ok(SelectorList(vec!(Selector {
+            complex_selector: Arc::new(ComplexSelector {
+                compound_selector: vec![
+                    SimpleSelector::Class(String::from("foo")),
+                    SimpleSelector::NonTSPseudoClass(PseudoClass::Lang("en-US".to_owned()))
+                ],
+                next: None,
+            }),
+            pseudo_element: None,
+            specificity: specificity(0, 2, 0),
+        }))));
+        assert_eq!(parse("#bar"), Ok(SelectorList(vec!(Selector {
+            complex_selector: Arc::new(ComplexSelector {
+                compound_selector: vec!(SimpleSelector::ID(String::from("bar"))),
+                next: None,
+            }),
+            pseudo_element: None,
+            specificity: specificity(1, 0, 0),
+        }))));
+        assert_eq!(parse("e.foo#bar"), Ok(SelectorList(vec!(Selector {
+            complex_selector: Arc::new(ComplexSelector {
+                compound_selector: vec!(SimpleSelector::LocalName(LocalName {
+                                            name: String::from("e"),
+                                            lower_name: String::from("e") }),
+                                       SimpleSelector::Class(String::from("foo")),
+                                       SimpleSelector::ID(String::from("bar"))),
+                next: None,
+            }),
+            pseudo_element: None,
+            specificity: specificity(1, 1, 1),
+        }))));
+        assert_eq!(parse("e.foo #bar"), Ok(SelectorList(vec!(Selector {
+            complex_selector: Arc::new(ComplexSelector {
+                compound_selector: vec!(SimpleSelector::ID(String::from("bar"))),
+                next: Some((Arc::new(ComplexSelector {
+                    compound_selector: vec!(SimpleSelector::LocalName(LocalName {
+                                                name: String::from("e"),
+                                                lower_name: String::from("e") }),
+                                           SimpleSelector::Class(String::from("foo"))),
+                    next: None,
+                }), Combinator::Descendant)),
+            }),
+            pseudo_element: None,
+            specificity: specificity(1, 1, 1),
+        }))));
+        // Default namespace does not apply to attribute selectors
+        // https://github.com/mozilla/servo/pull/1652
+        let mut parser = DummyParser::default();
+        assert_eq!(parse_ns("[Foo]", &parser), Ok(SelectorList(vec!(Selector {
+            complex_selector: Arc::new(ComplexSelector {
+                compound_selector: vec!(SimpleSelector::AttrExists(AttrSelector {
+                    name: String::from("Foo"),
+                    lower_name: String::from("foo"),
+                    namespace: NamespaceConstraint::Specific(Namespace {
+                        prefix: None,
+                        url: "".into(),
+                    }),
+                })),
+                next: None,
+            }),
+            pseudo_element: None,
+            specificity: specificity(0, 1, 0),
+        }))));
+        assert_eq!(parse_ns("svg|circle", &parser), Err(()));
+        parser.ns_prefixes.insert("svg".into(), SVG.into());
+        assert_eq!(parse_ns("svg|circle", &parser), Ok(SelectorList(vec![Selector {
+            complex_selector: Arc::new(ComplexSelector {
+                compound_selector: vec![
+                    SimpleSelector::Namespace(Namespace {
+                        prefix: Some("svg".into()),
+                        url: SVG.into(),
+                    }),
+                    SimpleSelector::LocalName(LocalName {
+                        name: String::from("circle"),
+                        lower_name: String::from("circle")
+                    })
+                ],
+                next: None,
+            }),
+            pseudo_element: None,
+            specificity: specificity(0, 0, 1),
+        }])));
+        // Default namespace does not apply to attribute selectors
+        // https://github.com/mozilla/servo/pull/1652
+        // but it does apply to implicit type selectors
+        // https://github.com/servo/rust-selectors/pull/82
+        parser.default_ns = Some(MATHML.into());
+        assert_eq!(parse_ns("[Foo]", &parser), Ok(SelectorList(vec!(Selector {
+            complex_selector: Arc::new(ComplexSelector {
+                compound_selector: vec![
+                    SimpleSelector::Namespace(Namespace {
+                        prefix: None,
+                        url: MATHML.into(),
+                    }),
+                    SimpleSelector::AttrExists(AttrSelector {
+                        name: String::from("Foo"),
+                        lower_name: String::from("foo"),
+                        namespace: NamespaceConstraint::Specific(Namespace {
+                            prefix: None,
+                            url: "".into(),
+                        }),
+                    }),
+                ],
+                next: None,
+            }),
+            pseudo_element: None,
+            specificity: specificity(0, 1, 0),
+        }))));
+        // Default namespace does apply to type selectors
+        assert_eq!(parse_ns("e", &parser), Ok(SelectorList(vec!(Selector {
+            complex_selector: Arc::new(ComplexSelector {
+                compound_selector: vec!(
+                    SimpleSelector::Namespace(Namespace {
+                        prefix: None,
+                        url: MATHML.into(),
+                    }),
+                    SimpleSelector::LocalName(LocalName {
+                        name: String::from("e"),
+                        lower_name: String::from("e") }),
+                ),
+                next: None,
+            }),
+            pseudo_element: None,
+            specificity: specificity(0, 0, 1),
+        }))));
+        assert_eq!(parse("[attr |= \"foo\"]"), Ok(SelectorList(vec![Selector {
+            complex_selector: Arc::new(ComplexSelector {
+                compound_selector: vec![
+                    SimpleSelector::AttrDashMatch(AttrSelector {
+                        name: String::from("attr"),
+                        lower_name: String::from("attr"),
+                        namespace: NamespaceConstraint::Specific(Namespace {
+                            prefix: None,
+                            url: "".into(),
+                        }),
+                    }, "foo".to_owned())
+                ],
+                next: None,
+            }),
+            pseudo_element: None,
+            specificity: specificity(0, 1, 0),
+        }])));
+        // https://github.com/mozilla/servo/issues/1723
+        assert_eq!(parse("::before"), Ok(SelectorList(vec!(Selector {
+            complex_selector: Arc::new(ComplexSelector {
+                compound_selector: vec!(),
+                next: None,
+            }),
+            pseudo_element: Some(PseudoElement::Before),
+            specificity: specificity(0, 0, 1),
+        }))));
+        // https://github.com/servo/servo/issues/15335
+        assert_eq!(parse(":: before"), Err(()));
+        assert_eq!(parse("div ::after"), Ok(SelectorList(vec!(Selector {
+            complex_selector: Arc::new(ComplexSelector {
+                compound_selector: vec!(),
+                next: Some((Arc::new(ComplexSelector {
+                    compound_selector: vec!(SimpleSelector::LocalName(LocalName {
+                        name: String::from("div"),
+                        lower_name: String::from("div") })),
+                    next: None,
+                }), Combinator::Descendant)),
+            }),
+            pseudo_element: Some(PseudoElement::After),
+            specificity: specificity(0, 0, 2),
+        }))));
+        assert_eq!(parse("#d1 > .ok"), Ok(SelectorList(vec![Selector {
+            complex_selector: Arc::new(ComplexSelector {
+                compound_selector: vec![
+                    SimpleSelector::Class(String::from("ok")),
+                ],
+                next: Some((Arc::new(ComplexSelector {
+                    compound_selector: vec![
+                        SimpleSelector::ID(String::from("d1")),
+                    ],
+                    next: None,
+                }), Combinator::Child)),
+            }),
+            pseudo_element: None,
+            specificity: (1 << 20) + (1 << 10) + (0 << 0),
+        }])));
+        assert_eq!(parse(":not(.babybel, #provel.old)"), Ok(SelectorList(vec!(Selector {
+            complex_selector: Arc::new(ComplexSelector {
+                compound_selector: vec!(SimpleSelector::Negation(
+                    vec!(
+                        Arc::new(ComplexSelector {
+                            compound_selector: vec!(SimpleSelector::Class(String::from("babybel"))),
+                            next: None
+                        }),
+                        Arc::new(ComplexSelector {
+                            compound_selector: vec!(
+                                SimpleSelector::ID(String::from("provel")),
+                                SimpleSelector::Class(String::from("old")),
+                            ),
+                            next: None
+                        }),
+                    )
+                )),
+                next: None,
+            }),
+            pseudo_element: None,
+            specificity: specificity(1, 1, 0),
+        }))));
+    }
+}
diff --git a/components/selectors/tree.rs b/components/selectors/tree.rs
new file mode 100644
index 00000000000..0ef48b4eec3
--- /dev/null
+++ b/components/selectors/tree.rs
@@ -0,0 +1,178 @@
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+//! Traits that nodes must implement. Breaks the otherwise-cyclic dependency between layout and
+//! style.
+
+use matching::ElementFlags;
+use parser::{AttrSelector, SelectorImpl};
+use std::ascii::AsciiExt;
+
+/// The definition of whitespace per CSS Selectors Level 3 § 4.
+pub static SELECTOR_WHITESPACE: &'static [char] = &[' ', '\t', '\n', '\r', '\x0C'];
+
+// Attribute matching routines. Consumers with simple implementations can implement
+// MatchAttrGeneric instead.
+pub trait MatchAttr {
+    type Impl: SelectorImpl;
+
+    fn match_attr_has(
+        &self,
+        attr: &AttrSelector<Self::Impl>) -> bool;
+
+    fn match_attr_equals(
+        &self,
+        attr: &AttrSelector<Self::Impl>,
+        value: &<Self::Impl as SelectorImpl>::AttrValue) -> bool;
+
+    fn match_attr_equals_ignore_ascii_case(
+        &self,
+        attr: &AttrSelector<Self::Impl>,
+        value: &<Self::Impl as SelectorImpl>::AttrValue) -> bool;
+
+    fn match_attr_includes(
+        &self,
+        attr: &AttrSelector<Self::Impl>,
+        value: &<Self::Impl as SelectorImpl>::AttrValue) -> bool;
+
+    fn match_attr_dash(
+        &self,
+        attr: &AttrSelector<Self::Impl>,
+        value: &<Self::Impl as SelectorImpl>::AttrValue) -> bool;
+
+    fn match_attr_prefix(
+        &self,
+        attr: &AttrSelector<Self::Impl>,
+        value: &<Self::Impl as SelectorImpl>::AttrValue) -> bool;
+
+    fn match_attr_substring(
+        &self,
+        attr: &AttrSelector<Self::Impl>,
+        value: &<Self::Impl as SelectorImpl>::AttrValue) -> bool;
+
+    fn match_attr_suffix(
+        &self,
+        attr: &AttrSelector<Self::Impl>,
+        value: &<Self::Impl as SelectorImpl>::AttrValue) -> bool;
+}
+
+pub trait MatchAttrGeneric {
+    type Impl: SelectorImpl;
+    fn match_attr<F>(&self, attr: &AttrSelector<Self::Impl>, test: F) -> bool where F: Fn(&str) -> bool;
+}
+
+impl<T> MatchAttr for T where T: MatchAttrGeneric, T::Impl: SelectorImpl<AttrValue = String> {
+    type Impl = T::Impl;
+
+    fn match_attr_has(&self, attr: &AttrSelector<Self::Impl>) -> bool {
+        self.match_attr(attr, |_| true)
+    }
+
+    fn match_attr_equals(&self, attr: &AttrSelector<Self::Impl>, value: &String) -> bool {
+        self.match_attr(attr, |v| v == value)
+    }
+
+    fn match_attr_equals_ignore_ascii_case(&self, attr: &AttrSelector<Self::Impl>,
+                                           value: &String) -> bool {
+        self.match_attr(attr, |v| v.eq_ignore_ascii_case(value))
+    }
+
+    fn match_attr_includes(&self, attr: &AttrSelector<Self::Impl>, value: &String) -> bool {
+        self.match_attr(attr, |attr_value| {
+            attr_value.split(SELECTOR_WHITESPACE).any(|v| v == value)
+        })
+    }
+
+    fn match_attr_dash(&self, attr: &AttrSelector<Self::Impl>, value: &String) -> bool {
+        self.match_attr(attr, |attr_value| {
+
+            // The attribute must start with the pattern.
+            if !attr_value.starts_with(value) {
+                return false
+            }
+
+            // If the strings are the same, we're done.
+            if attr_value.len() == value.len() {
+                return true
+            }
+
+            // The attribute is long than the pattern, so the next character must be '-'.
+            attr_value.as_bytes()[value.len()] == '-' as u8
+        })
+    }
+
+    fn match_attr_prefix(&self, attr: &AttrSelector<Self::Impl>, value: &String) -> bool {
+        self.match_attr(attr, |attr_value| {
+            attr_value.starts_with(value)
+        })
+    }
+
+    fn match_attr_substring(&self, attr: &AttrSelector<Self::Impl>, value: &String) -> bool {
+        self.match_attr(attr, |attr_value| {
+            attr_value.contains(value)
+        })
+    }
+
+    fn match_attr_suffix(&self, attr: &AttrSelector<Self::Impl>, value: &String) -> bool {
+        self.match_attr(attr, |attr_value| {
+            attr_value.ends_with(value)
+        })
+    }
+}
+
+pub trait Element: MatchAttr + Sized {
+    fn parent_element(&self) -> Option<Self>;
+
+    // Skips non-element nodes
+    fn first_child_element(&self) -> Option<Self>;
+
+    // Skips non-element nodes
+    fn last_child_element(&self) -> Option<Self>;
+
+    // Skips non-element nodes
+    fn prev_sibling_element(&self) -> Option<Self>;
+
+    // Skips non-element nodes
+    fn next_sibling_element(&self) -> Option<Self>;
+
+    fn is_html_element_in_html_document(&self) -> bool;
+    fn get_local_name(&self) -> &<Self::Impl as SelectorImpl>::BorrowedLocalName;
+    fn get_namespace(&self) -> &<Self::Impl as SelectorImpl>::BorrowedNamespaceUrl;
+
+    fn match_non_ts_pseudo_class(&self, pc: &<Self::Impl as SelectorImpl>::NonTSPseudoClass) -> bool;
+
+    fn get_id(&self) -> Option<<Self::Impl as SelectorImpl>::Identifier>;
+    fn has_class(&self, name: &<Self::Impl as SelectorImpl>::ClassName) -> bool;
+
+    /// Returns whether this element matches `:empty`.
+    ///
+    /// That is, whether it does not contain any child element or any non-zero-length text node.
+    /// See http://dev.w3.org/csswg/selectors-3/#empty-pseudo
+    fn is_empty(&self) -> bool;
+
+    /// Returns whether this element matches `:root`,
+    /// i.e. whether it is the root element of a document.
+    ///
+    /// Note: this can be false even if `.parent_element()` is `None`
+    /// if the parent node is a `DocumentFragment`.
+    fn is_root(&self) -> bool;
+
+    // Ordinarily I wouldn't use callbacks like this, but the alternative is
+    // really messy, since there is a `JSRef` and a `RefCell` involved. Maybe
+    // in the future when we have associated types and/or a more convenient
+    // JS GC story... --pcwalton
+    fn each_class<F>(&self, callback: F) where F: FnMut(&<Self::Impl as SelectorImpl>::ClassName);
+
+    /// Add flags to the element. See the `ElementFlags` docs for details.
+    ///
+    /// This may be called while the element *or one of its children* is being
+    /// matched. Therefore the implementation must be thread-safe if children
+    /// may be matched in parallel.
+    fn insert_flags(&self, _flags: ElementFlags) {}
+
+    /// Clears the relevant ElementFlags. This is *not* called from
+    /// rust-selectors, but provided as part of the Element interface since it
+    /// makes sense.
+    fn clear_flags(&self) {}
+}
diff --git a/components/style/Cargo.toml b/components/style/Cargo.toml
index fcbab890135..312c40099f5 100644
--- a/components/style/Cargo.toml
+++ b/components/style/Cargo.toml
@@ -46,7 +46,7 @@ phf = "0.7.20"
 pdqsort = "0.1.0"
 rayon = "0.6"
 rustc-serialize = "0.3"
-selectors = "0.17"
+selectors = { path = "../selectors" }
 serde = {version = "0.8", optional = true}
 serde_derive = {version = "0.8", optional = true}
 servo_atoms = {path = "../atoms", optional = true}
diff --git a/ports/geckolib/Cargo.toml b/ports/geckolib/Cargo.toml
index e8c4facafca..377710171ac 100644
--- a/ports/geckolib/Cargo.toml
+++ b/ports/geckolib/Cargo.toml
@@ -23,7 +23,7 @@ libc = "0.2"
 log = {version = "0.3.5", features = ["release_max_level_info"]}
 num_cpus = "1.1.0"
 parking_lot = "0.3"
-selectors = "0.17"
+selectors = {path = "../../components/selectors"}
 servo_url = {path = "../../components/url"}
 style = {path = "../../components/style", features = ["gecko"]}
 style_traits = {path = "../../components/style_traits"}
diff --git a/tests/unit/style/Cargo.toml b/tests/unit/style/Cargo.toml
index 9d932d2207d..28ef6b55065 100644
--- a/tests/unit/style/Cargo.toml
+++ b/tests/unit/style/Cargo.toml
@@ -22,7 +22,7 @@ owning_ref = "0.2.2"
 parking_lot = "0.3"
 rayon = "0.6"
 rustc-serialize = "0.3"
-selectors = "0.17"
+selectors = {path = "../../../components/selectors"}
 servo_atoms = {path = "../../../components/atoms"}
 servo_config = {path = "../../../components/config"}
 style = {path = "../../../components/style"}
diff --git a/tests/unit/stylo/Cargo.toml b/tests/unit/stylo/Cargo.toml
index ec3960b520f..c53df85dc79 100644
--- a/tests/unit/stylo/Cargo.toml
+++ b/tests/unit/stylo/Cargo.toml
@@ -22,7 +22,7 @@ libc = "0.2"
 log = {version = "0.3.5", features = ["release_max_level_info"]}
 num_cpus = "1.1.0"
 parking_lot = "0.3"
-selectors = "0.17"
+selectors = {path = "../../../components/selectors"}
 servo_url = {path = "../../../components/url"}
 style_traits = {path = "../../../components/style_traits"}
 geckoservo = {path = "../../../ports/geckolib"}