Auto merge of #17179 - bholley:one_selector_allocation, r=emilio

shrink Rule and store all heap-allocated selector data inline

https://bugzilla.mozilla.org/show_bug.cgi?id=1370107

<!-- Reviewable:start -->
---
This change is [<img src="https://reviewable.io/review_button.svg" height="34" align="absmiddle" alt="Reviewable"/>](https://reviewable.io/reviews/servo/servo/17179)
<!-- Reviewable:end -->

18 files changed, 780 insertions, 844 deletions

diff --git a/components/script/dom/element.rs b/components/script/dom/element.rs
index be708113def..f875986edd2 100644
--- a/components/script/dom/element.rs
+++ b/components/script/dom/element.rs
@@ -2061,7 +2061,7 @@ impl ElementMethods for Element {
             Err(()) => Err(Error::Syntax),
             Ok(selectors) => {
                 let mut ctx = MatchingContext::new(MatchingMode::Normal, None);
-                Ok(matches_selector_list(&selectors.0, &Root::from_ref(self), &mut ctx))
+                Ok(matches_selector_list(&selectors, &Root::from_ref(self), &mut ctx))
             }
         }
     }
@@ -2080,7 +2080,7 @@ impl ElementMethods for Element {
                 for element in root.inclusive_ancestors() {
                     if let Some(element) = Root::downcast::<Element>(element) {
                         let mut ctx = MatchingContext::new(MatchingMode::Normal, None);
-                        if matches_selector_list(&selectors.0, &element, &mut ctx) {
+                        if matches_selector_list(&selectors, &element, &mut ctx) {
                             return Ok(Some(element));
                         }
                     }
diff --git a/components/script/dom/node.rs b/components/script/dom/node.rs
index cc817587eda..8dde9cc7b01 100644
--- a/components/script/dom/node.rs
+++ b/components/script/dom/node.rs
@@ -345,7 +345,7 @@ impl<'a> Iterator for QuerySelectorIterator {
     type Item = Root<Node>;
 
     fn next(&mut self) -> Option<Root<Node>> {
-        let selectors = &self.selectors.0;
+        let selectors = &self.selectors;
 
         // TODO(cgaebel): Is it worth it to build a bloom filter here
         // (instead of passing `None`)? Probably.
@@ -722,7 +722,7 @@ impl Node {
             Ok(selectors) => {
                 let mut ctx = MatchingContext::new(MatchingMode::Normal, None);
                 Ok(self.traverse_preorder().filter_map(Root::downcast).find(|element| {
-                    matches_selector_list(&selectors.0, element, &mut ctx)
+                    matches_selector_list(&selectors, element, &mut ctx)
                 }))
             }
         }
diff --git a/components/selectors/Cargo.toml b/components/selectors/Cargo.toml
index effb612bb43..15aba3d1811 100644
--- a/components/selectors/Cargo.toml
+++ b/components/selectors/Cargo.toml
@@ -28,6 +28,7 @@ cssparser = "0.13.7"
 fnv = "1.0"
 phf = "0.7.18"
 precomputed-hash = "0.1"
+servo_arc = { path = "../servo_arc" }
 smallvec = "0.4"
 
 [dev-dependencies]
diff --git a/components/selectors/arcslice.rs b/components/selectors/arcslice.rs
deleted file mode 100644
index e5722ba6505..00000000000
--- a/components/selectors/arcslice.rs
+++ /dev/null
@@ -1,326 +0,0 @@
-/* Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
- * http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
- * <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
- * option. This file may not be copied, modified, or distributed
- * except according to those terms.
- *
- * See the COPYRIGHT file at the top-level directory of this distribution */
-//! A thread-safe reference-counted slice type.
-//!
-//! Forked from https://github.com/huonw/shared_slice , which doesn't work on
-//! rust stable.
-
-use std::{cmp, fmt, ops};
-use std::hash::{Hash, Hasher};
-use std::sync::{Arc, Weak};
-
-
-/// A reference-counted slice type.
-pub struct ArcSlice<T> {
-    data: *const [T],
-    counts: Arc<Box<[T]>>,
-}
-
-unsafe impl<T: Send + Sync> Send for ArcSlice<T> {}
-unsafe impl<T: Send + Sync> Sync for ArcSlice<T> {}
-
-/// A non-owning reference-counted slice type.
-///
-/// This is to `ArcSlice` as `std::sync::Weak` is to `std::sync::Arc`, and
-/// allows one to have cyclic references without stopping memory from
-/// being deallocated.
-pub struct WeakSlice<T> {
-    data: *const [T],
-    counts: Weak<Box<[T]>>,
-}
-unsafe impl<T: Send + Sync> Send for WeakSlice<T> {}
-unsafe impl<T: Send + Sync> Sync for WeakSlice<T> {}
-
-impl<T> ArcSlice<T> {
-    /// Construct a new `ArcSlice` containing the elements of `slice`.
-    ///
-    /// This reuses the allocation of `slice`.
-    pub fn new(slice: Box<[T]>) -> ArcSlice<T> {
-        ArcSlice {
-            data: &*slice,
-            counts: Arc::new(slice),
-        }
-    }
-
-    /// Downgrade self into a weak slice.
-    pub fn downgrade(&self) -> WeakSlice<T> {
-        WeakSlice {
-            data: self.data,
-            counts: Arc::downgrade(&self.counts)
-        }
-    }
-
-    /// Construct a new `ArcSlice` that only points to elements at
-    /// indices `lo` (inclusive) through `hi` (exclusive).
-    ///
-    /// This consumes `self` to avoid unnecessary reference-count
-    /// modifications. Use `.clone()` if it is necessary to refer to
-    /// `self` after calling this.
-    ///
-    /// # Panics
-    ///
-    /// Panics if `lo > hi` or if either are strictly greater than
-    /// `self.len()`.
-    pub fn slice(mut self, lo: usize, hi: usize) -> ArcSlice<T> {
-        self.data = &self[lo..hi];
-        self
-    }
-    /// Construct a new `ArcSlice` that only points to elements at
-    /// indices up to `hi` (exclusive).
-    ///
-    /// This consumes `self` to avoid unnecessary reference-count
-    /// modifications. Use `.clone()` if it is necessary to refer to
-    /// `self` after calling this.
-    ///
-    /// # Panics
-    ///
-    /// Panics if `hi > self.len()`.
-    pub fn slice_to(self, hi: usize) -> ArcSlice<T> {
-        self.slice(0, hi)
-    }
-    /// Construct a new `ArcSlice` that only points to elements at
-    /// indices starting at  `lo` (inclusive).
-    ///
-    /// This consumes `self` to avoid unnecessary reference-count
-    /// modifications. Use `.clone()` if it is necessary to refer to
-    /// `self` after calling this.
-    ///
-    /// # Panics
-    ///
-    /// Panics if `lo > self.len()`.
-    pub fn slice_from(self, lo: usize) -> ArcSlice<T> {
-        let hi = self.len();
-        self.slice(lo, hi)
-    }
-}
-
-impl<T> Clone for ArcSlice<T> {
-    fn clone(&self) -> ArcSlice<T> {
-        ArcSlice {
-            data: self.data,
-            counts: self.counts.clone()
-        }
-    }
-}
-
-impl<T> ops::Deref for ArcSlice<T> {
-    type Target = [T];
-    fn deref<'a>(&'a self) -> &'a [T] {
-        unsafe { &*self.data }
-    }
-}
-
-impl<T> AsRef<[T]> for ArcSlice<T> {
-    fn as_ref(&self) -> &[T] { &**self }
-}
-
-impl<T: PartialEq> PartialEq for ArcSlice<T> {
-    fn eq(&self, other: &ArcSlice<T>) -> bool { **self == **other }
-    fn ne(&self, other: &ArcSlice<T>) -> bool { **self != **other }
-}
-impl<T: Eq> Eq for ArcSlice<T> {}
-
-impl<T: PartialOrd> PartialOrd for ArcSlice<T> {
-    fn partial_cmp(&self, other: &ArcSlice<T>) -> Option<cmp::Ordering> {
-        (**self).partial_cmp(&**other)
-    }
-    fn lt(&self, other: &ArcSlice<T>) -> bool { **self < **other }
-    fn le(&self, other: &ArcSlice<T>) -> bool { **self <= **other }
-    fn gt(&self, other: &ArcSlice<T>) -> bool { **self > **other }
-    fn ge(&self, other: &ArcSlice<T>) -> bool { **self >= **other }
-}
-impl<T: Ord> Ord for ArcSlice<T> {
-    fn cmp(&self, other: &ArcSlice<T>) -> cmp::Ordering { (**self).cmp(&**other) }
-}
-
-impl<T: Hash> Hash for ArcSlice<T> {
-    fn hash<H: Hasher>(&self, state: &mut H) {
-        Hash::hash(&**self, state)
-    }
-}
-
-impl<T: fmt::Debug> fmt::Debug for ArcSlice<T> {
-    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
-        fmt::Debug::fmt(&**self, f)
-    }
-}
-
-impl<T> WeakSlice<T> {
-    /// Attempt to upgrade `self` to a strongly-counted `ArcSlice`.
-    ///
-    /// Returns `None` if this is not possible (the data has already
-    /// been freed).
-    pub fn upgrade(&self) -> Option<ArcSlice<T>> {
-        self.counts.upgrade().map(|counts| {
-            ArcSlice {
-                data: self.data,
-                counts: counts
-            }
-        })
-    }
-}
-
-#[cfg(test)]
-mod tests {
-    use std::cell::Cell;
-    use std::cmp::Ordering;
-    use std::sync::{Arc, Mutex};
-    use super::{ArcSlice, WeakSlice};
-    #[test]
-    fn clone() {
-        let x = ArcSlice::new(Box::new([Cell::new(false)]));
-        let y = x.clone();
-
-        assert_eq!(x[0].get(), false);
-        assert_eq!(y[0].get(), false);
-
-        x[0].set(true);
-        assert_eq!(x[0].get(), true);
-        assert_eq!(y[0].get(), true);
-    }
-
-    #[test]
-    fn test_upgrade_downgrade() {
-        let x = ArcSlice::new(Box::new([1]));
-        let y: WeakSlice<_> = x.downgrade();
-
-        assert_eq!(y.upgrade(), Some(x.clone()));
-
-        drop(x);
-
-        assert!(y.upgrade().is_none())
-    }
-
-    #[test]
-    fn test_total_cmp() {
-        let x = ArcSlice::new(Box::new([1, 2, 3]));
-        let y = ArcSlice::new(Box::new([1, 2, 3]));
-        let z = ArcSlice::new(Box::new([1, 2, 4]));
-
-        assert_eq!(x, x);
-        assert_eq!(x, y);
-        assert!(x != z);
-        assert!(y != z);
-
-        assert!(x < z);
-        assert!(x <= z);
-        assert!(!(x > z));
-        assert!(!(x >= z));
-
-        assert!(!(z < x));
-        assert!(!(z <= x));
-        assert!(z > x);
-        assert!(z >= x);
-
-        assert_eq!(x.partial_cmp(&x), Some(Ordering::Equal));
-        assert_eq!(x.partial_cmp(&y), Some(Ordering::Equal));
-        assert_eq!(x.partial_cmp(&z), Some(Ordering::Less));
-        assert_eq!(z.partial_cmp(&y), Some(Ordering::Greater));
-
-        assert_eq!(x.cmp(&x), Ordering::Equal);
-        assert_eq!(x.cmp(&y), Ordering::Equal);
-        assert_eq!(x.cmp(&z), Ordering::Less);
-        assert_eq!(z.cmp(&y), Ordering::Greater);
-    }
-
-    #[test]
-    fn test_partial_cmp() {
-        use std::f64;
-        let x = ArcSlice::new(Box::new([1.0, f64::NAN]));
-        let y = ArcSlice::new(Box::new([1.0, f64::NAN]));
-        let z = ArcSlice::new(Box::new([2.0, f64::NAN]));
-        let w = ArcSlice::new(Box::new([f64::NAN, 1.0]));
-        assert!(!(x == y));
-        assert!(x != y);
-
-        assert!(!(x < y));
-        assert!(!(x <= y));
-        assert!(!(x > y));
-        assert!(!(x >= y));
-
-        assert!(x < z);
-        assert!(x <= z);
-        assert!(!(x > z));
-        assert!(!(x >= z));
-
-        assert!(!(z < w));
-        assert!(!(z <= w));
-        assert!(!(z > w));
-        assert!(!(z >= w));
-
-        assert_eq!(x.partial_cmp(&x), None);
-        assert_eq!(x.partial_cmp(&y), None);
-        assert_eq!(x.partial_cmp(&z), Some(Ordering::Less));
-        assert_eq!(z.partial_cmp(&x), Some(Ordering::Greater));
-
-        assert_eq!(x.partial_cmp(&w), None);
-        assert_eq!(y.partial_cmp(&w), None);
-        assert_eq!(z.partial_cmp(&w), None);
-        assert_eq!(w.partial_cmp(&w), None);
-    }
-
-    #[test]
-    fn test_show() {
-        let x = ArcSlice::new(Box::new([1, 2]));
-        assert_eq!(format!("{:?}", x), "[1, 2]");
-
-        let y: ArcSlice<i32> = ArcSlice::new(Box::new([]));
-        assert_eq!(format!("{:?}", y), "[]");
-    }
-
-    #[test]
-    fn test_slice() {
-        let x = ArcSlice::new(Box::new([1, 2, 3]));
-        let real = [1, 2, 3];
-        for i in 0..3 + 1 {
-            for j in i..3 + 1 {
-                let slice: ArcSlice<_> = x.clone().slice(i, j);
-                assert_eq!(&*slice, &real[i..j]);
-            }
-            assert_eq!(&*x.clone().slice_to(i), &real[..i]);
-            assert_eq!(&*x.clone().slice_from(i), &real[i..]);
-        }
-    }
-
-
-    #[test]
-    fn test_send_sync() {
-        fn assert_send<T: Send>() {}
-        fn assert_sync<T: Send>() {}
-
-        assert_send::<ArcSlice<u8>>();
-        assert_sync::<ArcSlice<u8>>();
-        assert_send::<WeakSlice<u8>>();
-        assert_sync::<WeakSlice<u8>>();
-    }
-
-    #[test]
-    fn test_drop() {
-        let drop_flag = Arc::new(Mutex::new(0));
-        struct Foo(Arc<Mutex<i32>>);
-
-        impl Drop for Foo {
-            fn drop(&mut self) {
-                let mut n = self.0.lock().unwrap();
-                *n += 1;
-            }
-        }
-
-        let whole = ArcSlice::new(Box::new([Foo(drop_flag.clone()), Foo(drop_flag.clone())]));
-
-        drop(whole);
-        assert_eq!(*drop_flag.lock().unwrap(), 2);
-
-        *drop_flag.lock().unwrap() = 0;
-
-        let whole = ArcSlice::new(Box::new([Foo(drop_flag.clone()), Foo(drop_flag.clone())]));
-        let part = whole.slice(1, 2);
-        drop(part);
-        assert_eq!(*drop_flag.lock().unwrap(), 2);
-    }
-}
diff --git a/components/selectors/lib.rs b/components/selectors/lib.rs
index 3e413c0c08b..a6f4acd3d84 100644
--- a/components/selectors/lib.rs
+++ b/components/selectors/lib.rs
@@ -9,9 +9,9 @@ extern crate fnv;
 extern crate phf;
 extern crate precomputed_hash;
 #[cfg(test)] #[macro_use] extern crate size_of_test;
+extern crate servo_arc;
 extern crate smallvec;
 
-pub mod arcslice;
 pub mod attr;
 pub mod bloom;
 pub mod matching;
diff --git a/components/selectors/matching.rs b/components/selectors/matching.rs
index 444d24a7d1c..3a2ddfd998a 100644
--- a/components/selectors/matching.rs
+++ b/components/selectors/matching.rs
@@ -4,8 +4,8 @@
 
 use attr::{ParsedAttrSelectorOperation, AttrSelectorOperation, NamespaceConstraint};
 use bloom::BloomFilter;
-use parser::{Combinator, ComplexSelector, Component, LocalName};
-use parser::{Selector, SelectorInner, SelectorIter};
+use parser::{AncestorHashes, Combinator, Component, LocalName};
+use parser::{Selector, SelectorIter, SelectorList};
 use std::borrow::Borrow;
 use tree::Element;
 
@@ -152,27 +152,30 @@ impl<'a> MatchingContext<'a> {
     }
 }
 
-pub fn matches_selector_list<E>(selector_list: &[Selector<E::Impl>],
+pub fn matches_selector_list<E>(selector_list: &SelectorList<E::Impl>,
                                 element: &E,
                                 context: &mut MatchingContext)
                                 -> bool
     where E: Element
 {
-    selector_list.iter().any(|selector| {
-        matches_selector(&selector.inner,
+    selector_list.0.iter().any(|selector_and_hashes| {
+        matches_selector(&selector_and_hashes.selector,
+                         0,
+                         &selector_and_hashes.hashes,
                          element,
                          context,
                          &mut |_, _| {})
     })
 }
 
-fn may_match<E>(sel: &SelectorInner<E::Impl>,
+#[inline(always)]
+fn may_match<E>(hashes: &AncestorHashes,
                 bf: &BloomFilter)
                 -> bool
     where E: Element,
 {
     // Check against the list of precomputed hashes.
-    for hash in sel.ancestor_hashes.iter() {
+    for hash in hashes.0.iter() {
         // If we hit the 0 sentinel hash, that means the rest are zero as well.
         if *hash == 0 {
             break;
@@ -330,8 +333,18 @@ enum SelectorMatchingResult {
     NotMatchedGlobally,
 }
 
-/// Matches an inner selector.
-pub fn matches_selector<E, F>(selector: &SelectorInner<E::Impl>,
+/// Matches a selector, fast-rejecting against a bloom filter.
+///
+/// We accept an offset to allow consumers to represent and match against partial
+/// selectors (indexed from the right). We use this API design, rather than
+/// having the callers pass a SelectorIter, because creating a SelectorIter
+/// requires dereferencing the selector to get the length, which adds an
+/// unncessary cache miss for cases when we can fast-reject with AncestorHashes
+/// (which the caller can store inline with the selector pointer).
+#[inline(always)]
+pub fn matches_selector<E, F>(selector: &Selector<E::Impl>,
+                              offset: usize,
+                              hashes: &AncestorHashes,
                               element: &E,
                               context: &mut MatchingContext,
                               flags_setter: &mut F)
@@ -341,18 +354,17 @@ pub fn matches_selector<E, F>(selector: &SelectorInner<E::Impl>,
 {
     // Use the bloom filter to fast-reject.
     if let Some(filter) = context.bloom_filter {
-        if !may_match::<E>(&selector, filter) {
+        if !may_match::<E>(hashes, filter) {
             return false;
         }
     }
 
-    matches_complex_selector(&selector.complex, element, context, flags_setter)
+    matches_complex_selector(selector, offset, element, context, flags_setter)
 }
 
 /// Matches a complex selector.
-///
-/// Use `matches_selector` if you need to skip pseudos.
-pub fn matches_complex_selector<E, F>(complex_selector: &ComplexSelector<E::Impl>,
+pub fn matches_complex_selector<E, F>(complex_selector: &Selector<E::Impl>,
+                                      offset: usize,
                                       element: &E,
                                       context: &mut MatchingContext,
                                       flags_setter: &mut F)
@@ -360,11 +372,15 @@ pub fn matches_complex_selector<E, F>(complex_selector: &ComplexSelector<E::Impl
     where E: Element,
           F: FnMut(&E, ElementSelectorFlags),
 {
-    let mut iter = complex_selector.iter();
+    let mut iter = if offset == 0 {
+        complex_selector.iter()
+    } else {
+        complex_selector.iter_from(offset)
+    };
 
     if cfg!(debug_assertions) {
         if context.matching_mode == MatchingMode::ForStatelessPseudoElement {
-            assert!(complex_selector.iter().any(|c| {
+            assert!(iter.clone().any(|c| {
                 matches!(*c, Component::PseudoElement(..))
             }));
         }
diff --git a/components/selectors/parser.rs b/components/selectors/parser.rs
index 197ce4f2629..a7f3d259fbd 100644
--- a/components/selectors/parser.rs
+++ b/components/selectors/parser.rs
@@ -2,11 +2,11 @@
  * 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 arcslice::ArcSlice;
 use attr::{AttrSelectorWithNamespace, ParsedAttrSelectorOperation, AttrSelectorOperator};
 use attr::{ParsedCaseSensitivity, SELECTOR_WHITESPACE, NamespaceConstraint};
 use cssparser::{Token, Parser as CssParser, parse_nth, ToCss, serialize_identifier, CssStringWriter};
 use precomputed_hash::PrecomputedHash;
+use servo_arc::{Arc, HeaderWithLength, ThinArc};
 use smallvec::SmallVec;
 use std::ascii::AsciiExt;
 use std::borrow::{Borrow, Cow};
@@ -130,7 +130,27 @@ pub trait Parser {
 }
 
 #[derive(PartialEq, Eq, Clone, Debug)]
-pub struct SelectorList<Impl: SelectorImpl>(pub Vec<Selector<Impl>>);
+pub struct SelectorAndHashes<Impl: SelectorImpl> {
+    pub selector: Selector<Impl>,
+    pub hashes: AncestorHashes,
+}
+
+impl<Impl: SelectorImpl> SelectorAndHashes<Impl> {
+    pub fn new(selector: Selector<Impl>) -> Self {
+        let hashes = AncestorHashes::new(&selector);
+        Self::new_with_hashes(selector, hashes)
+    }
+
+    pub fn new_with_hashes(selector: Selector<Impl>, hashes: AncestorHashes) -> Self {
+        SelectorAndHashes {
+            selector: selector,
+            hashes: hashes,
+        }
+    }
+}
+
+#[derive(PartialEq, Eq, Clone, Debug)]
+pub struct SelectorList<Impl: SelectorImpl>(pub Vec<SelectorAndHashes<Impl>>);
 
 impl<Impl: SelectorImpl> SelectorList<Impl> {
     /// Parse a comma-separated list of Selectors.
@@ -139,117 +159,52 @@ impl<Impl: SelectorImpl> SelectorList<Impl> {
     /// 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))
+        input.parse_comma_separated(|input| parse_selector(parser, input).map(SelectorAndHashes::new))
              .map(SelectorList)
     }
-}
-
-/// Copied from Gecko, where it was noted to be unmeasured.
-const NUM_ANCESTOR_HASHES: usize = 4;
-
-/// The cores parts of a selector used for matching. This exists to make that
-/// information accessibly separately from the specificity and pseudo-element
-/// information that lives on |Selector| proper. We may want to refactor things
-/// and move that information elsewhere, at which point we could rename this
-/// to |Selector|.
-#[derive(PartialEq, Eq, Clone)]
-pub struct SelectorInner<Impl: SelectorImpl> {
-    /// The selector data.
-    pub complex: ComplexSelector<Impl>,
-    /// Ancestor hashes for the bloom filter. We precompute these and store
-    /// them inline to optimize cache performance during selector matching.
-    /// This matters a lot.
-    pub ancestor_hashes: [u32; NUM_ANCESTOR_HASHES],
-}
-
-impl<Impl: SelectorImpl> SelectorInner<Impl> {
-    pub fn new(c: ComplexSelector<Impl>) -> Self {
-        let mut hashes = [0; NUM_ANCESTOR_HASHES];
-        {
-            // Compute ancestor hashes for the bloom filter.
-            let mut hash_iter = c.iter_ancestors()
-                                 .map(|x| x.ancestor_hash())
-                                 .filter(|x| x.is_some())
-                                 .map(|x| x.unwrap());
-            for i in 0..NUM_ANCESTOR_HASHES {
-                hashes[i] = match hash_iter.next() {
-                    Some(x) => x,
-                    None => break,
-                }
-            }
-        }
-
-        SelectorInner {
-            complex: c,
-            ancestor_hashes: hashes,
-        }
-    }
 
-    /// Creates a SelectorInner from a Vec of Components. Used in tests.
-    pub fn from_vec(vec: Vec<Component<Impl>>) -> Self {
-        let complex = ComplexSelector::from_vec(vec);
-        Self::new(complex)
+    /// Creates a SelectorList from a Vec of selectors. Used in tests.
+    pub fn from_vec(v: Vec<Selector<Impl>>) -> Self {
+        SelectorList(v.into_iter().map(SelectorAndHashes::new).collect())
     }
 }
 
-#[derive(PartialEq, Eq, Clone)]
-pub struct Selector<Impl: SelectorImpl> {
-    pub inner: SelectorInner<Impl>,
-    specificity_and_flags: u32,
-}
-
-impl<Impl: SelectorImpl> ::std::borrow::Borrow<SelectorInner<Impl>> for Selector<Impl> {
-    fn borrow(&self) -> &SelectorInner<Impl> {
-        &self.inner
-    }
-}
-
-const HAS_PSEUDO_BIT: u32 = 1 << 30;
+/// Copied from Gecko, who copied it from WebKit. Note that increasing the
+/// number of hashes here will adversely affect the cache hit when fast-
+/// rejecting long lists of Rules with inline hashes.
+const NUM_ANCESTOR_HASHES: usize = 4;
 
-impl<Impl: SelectorImpl> Selector<Impl> {
-    pub fn specificity(&self) -> u32 {
-        self.specificity_and_flags & !HAS_PSEUDO_BIT
-    }
+/// Ancestor hashes for the bloom filter. We precompute these and store them
+/// inline with selectors to optimize cache performance during matching.
+/// This matters a lot.
+#[derive(Eq, PartialEq, Clone, Debug)]
+pub struct AncestorHashes(pub [u32; NUM_ANCESTOR_HASHES]);
 
-    pub fn new_for_unit_testing(inner: SelectorInner<Impl>, specificity: u32) -> Self {
-        Self {
-            inner: inner,
-            specificity_and_flags: specificity,
-        }
+impl AncestorHashes {
+    pub fn new<Impl: SelectorImpl>(s: &Selector<Impl>) -> Self {
+        Self::from_iter(s.iter())
     }
 
-    pub fn pseudo_element(&self) -> Option<&Impl::PseudoElement> {
-        if !self.has_pseudo_element() {
-            return None
-        }
-
-        for component in self.inner.complex.iter() {
-            if let Component::PseudoElement(ref pseudo) = *component {
-                return Some(pseudo)
+    pub fn from_iter<Impl: SelectorImpl>(iter: SelectorIter<Impl>) -> Self {
+        let mut hashes = [0; NUM_ANCESTOR_HASHES];
+        // Compute ancestor hashes for the bloom filter.
+        let mut hash_iter = AncestorIter::new(iter)
+                             .map(|x| x.ancestor_hash())
+                             .filter(|x| x.is_some())
+                             .map(|x| x.unwrap());
+        for i in 0..NUM_ANCESTOR_HASHES {
+            hashes[i] = match hash_iter.next() {
+                Some(x) => x,
+                None => break,
             }
         }
 
-        debug_assert!(false, "has_pseudo_element lied!");
-        None
-    }
-
-    pub fn has_pseudo_element(&self) -> bool {
-        (self.specificity_and_flags & HAS_PSEUDO_BIT) != 0
-    }
-
-    /// Whether this selector (pseudo-element part excluded) matches every element.
-    ///
-    /// Used for "pre-computed" pseudo-elements in components/style/stylist.rs
-    pub fn is_universal(&self) -> bool {
-        self.inner.complex.iter_raw().all(|c| matches!(*c,
-            Component::ExplicitUniversalType |
-            Component::ExplicitAnyNamespace |
-            Component::Combinator(Combinator::PseudoElement) |
-            Component::PseudoElement(..)
-        ))
+        AncestorHashes(hashes)
     }
 }
 
+const HAS_PSEUDO_BIT: u32 = 1 << 30;
+
 pub trait SelectorMethods {
     type Impl: SelectorImpl;
 
@@ -263,16 +218,6 @@ impl<Impl: SelectorImpl> SelectorMethods for Selector<Impl> {
     fn visit<V>(&self, visitor: &mut V) -> bool
         where V: SelectorVisitor<Impl = Impl>,
     {
-        self.inner.complex.visit(visitor)
-    }
-}
-
-impl<Impl: SelectorImpl> SelectorMethods for ComplexSelector<Impl> {
-    type Impl = Impl;
-
-    fn visit<V>(&self, visitor: &mut V) -> bool
-        where V: SelectorVisitor<Impl = Impl>,
-    {
         let mut current = self.iter();
         let mut combinator = None;
         loop {
@@ -362,7 +307,20 @@ pub fn namespace_empty_string<Impl: SelectorImpl>() -> Impl::NamespaceUrl {
     Impl::NamespaceUrl::default()
 }
 
-/// A ComplexSelectors stores a sequence of simple selectors and combinators. The
+#[derive(Copy, Clone, Debug, Eq, PartialEq)]
+struct SpecificityAndFlags(u32);
+
+impl SpecificityAndFlags {
+    fn specificity(&self) -> u32 {
+        self.0 & !HAS_PSEUDO_BIT
+    }
+
+    fn has_pseudo_element(&self) -> bool {
+        (self.0 & HAS_PSEUDO_BIT) != 0
+    }
+}
+
+/// A Selector stores a sequence of simple selectors and combinators. The
 /// iterator classes allow callers to iterate at either the raw sequence level or
 /// at the level of sequences of simple selectors separated by combinators. Most
 /// callers want the higher-level iterator.
@@ -371,9 +329,45 @@ pub fn namespace_empty_string<Impl: SelectorImpl>() -> Impl::NamespaceUrl {
 /// canonical iteration order is right-to-left (selector matching order). The
 /// iterators abstract over these details.
 #[derive(Clone, Eq, PartialEq)]
-pub struct ComplexSelector<Impl: SelectorImpl>(ArcSlice<Component<Impl>>);
+pub struct Selector<Impl: SelectorImpl>(ThinArc<SpecificityAndFlags, Component<Impl>>);
+
+impl<Impl: SelectorImpl> Selector<Impl> {
+    pub fn specificity(&self) -> u32 {
+        self.0.header.header.specificity()
+    }
+
+    pub fn has_pseudo_element(&self) -> bool {
+        self.0.header.header.has_pseudo_element()
+    }
+
+    pub fn pseudo_element(&self) -> Option<&Impl::PseudoElement> {
+        if !self.has_pseudo_element() {
+            return None
+        }
+
+        for component in self.iter() {
+            if let Component::PseudoElement(ref pseudo) = *component {
+                return Some(pseudo)
+            }
+        }
+
+        debug_assert!(false, "has_pseudo_element lied!");
+        None
+    }
+
+    /// Whether this selector (pseudo-element part excluded) matches every element.
+    ///
+    /// Used for "pre-computed" pseudo-elements in components/style/stylist.rs
+    pub fn is_universal(&self) -> bool {
+        self.iter_raw().all(|c| matches!(*c,
+            Component::ExplicitUniversalType |
+            Component::ExplicitAnyNamespace |
+            Component::Combinator(Combinator::PseudoElement) |
+            Component::PseudoElement(..)
+        ))
+    }
+
 
-impl<Impl: SelectorImpl> ComplexSelector<Impl> {
     /// Returns an iterator over the next sequence of simple selectors. When
     /// a combinator is reached, the iterator will return None, and
     /// next_sequence() may be called to continue to the next sequence.
@@ -384,6 +378,15 @@ impl<Impl: SelectorImpl> ComplexSelector<Impl> {
         }
     }
 
+    pub fn iter_from(&self, offset: usize) -> SelectorIter<Impl> {
+        // Note: selectors are stored left-to-right but logical order is right-to-left.
+        let iter = self.0.slice[..(self.0.slice.len() - offset)].iter().rev();
+        SelectorIter {
+            iter: iter,
+            next_combinator: None,
+        }
+    }
+
     /// Returns an iterator over the entire sequence of simple selectors and combinators,
     /// from right to left.
     pub fn iter_raw(&self) -> Rev<slice::Iter<Component<Impl>>> {
@@ -393,34 +396,13 @@ impl<Impl: SelectorImpl> ComplexSelector<Impl> {
     /// Returns an iterator over the entire sequence of simple selectors and combinators,
     /// from left to right.
     pub fn iter_raw_rev(&self) -> slice::Iter<Component<Impl>> {
-        self.0.iter()
-    }
-
-    /// Returns an iterator over ancestor simple selectors. All combinators and
-    /// non-ancestor simple selectors will be skipped.
-    pub fn iter_ancestors(&self) -> AncestorIter<Impl> {
-        AncestorIter::new(self.iter())
-    }
-
-    /// Returns a ComplexSelector identical to |self| but with the rightmost |index|
-    /// entries removed.
-    pub fn slice_from(&self, index: usize) -> Self {
-        // Note that we convert the slice_from to slice_to because selectors are
-        // stored left-to-right but logical order is right-to-left.
-        ComplexSelector(self.0.clone().slice_to(self.0.len() - index))
-    }
-
-    /// Returns a ComplexSelector identical to |self| but with the leftmost
-    /// |len() - index| entries removed.
-    pub fn slice_to(&self, index: usize) -> Self {
-        // Note that we convert the slice_to to slice_from because selectors are
-        // stored left-to-right but logical order is right-to-left.
-        ComplexSelector(self.0.clone().slice_from(self.0.len() - index))
+        self.0.slice.iter()
     }
 
-    /// Creates a ComplexSelector from a vec of Components. Used in tests.
-    pub fn from_vec(vec: Vec<Component<Impl>>) -> Self {
-        ComplexSelector(ArcSlice::new(vec.into_boxed_slice()))
+    /// Creates a Selector from a vec of Components. Used in tests.
+    pub fn from_vec(vec: Vec<Component<Impl>>, specificity_and_flags: u32) -> Self {
+        let header = HeaderWithLength::new(SpecificityAndFlags(specificity_and_flags), vec.len());
+        Selector(Arc::into_thin(Arc::from_header_and_iter(header, vec.into_iter())))
     }
 }
 
@@ -590,7 +572,7 @@ pub enum Component<Impl: SelectorImpl> {
 
 impl<Impl: SelectorImpl> Component<Impl> {
     /// Compute the ancestor hash to check against the bloom filter.
-    fn ancestor_hash(&self) -> Option<u32> {
+    pub fn ancestor_hash(&self) -> Option<u32> {
         match *self {
             Component::LocalName(LocalName { ref name, ref lower_name }) => {
                 // Only insert the local-name into the filter if it's all lowercase.
@@ -644,12 +626,6 @@ impl<Impl: SelectorImpl> Debug for Selector<Impl> {
     }
 }
 
-impl<Impl: SelectorImpl> Debug for SelectorInner<Impl> {
-    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { self.complex.to_css(f) }
-}
-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 Component<Impl> {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { self.to_css(f) }
 }
@@ -665,10 +641,10 @@ impl<Impl: SelectorImpl> ToCss for SelectorList<Impl> {
         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 {
+        first.selector.to_css(dest)?;
+        for selector_and_hashes in iter {
             dest.write_str(", ")?;
-            selector.to_css(dest)?;
+            selector_and_hashes.selector.to_css(dest)?;
         }
         Ok(())
     }
@@ -676,12 +652,6 @@ impl<Impl: SelectorImpl> ToCss for SelectorList<Impl> {
 
 impl<Impl: SelectorImpl> ToCss for Selector<Impl> {
     fn to_css<W>(&self, dest: &mut W) -> fmt::Result where W: fmt::Write {
-        self.inner.complex.to_css(dest)
-    }
-}
-
-impl<Impl: SelectorImpl> ToCss for ComplexSelector<Impl> {
-    fn to_css<W>(&self, dest: &mut W) -> fmt::Result where W: fmt::Write {
        for item in self.iter_raw_rev() {
            item.to_css(dest)?;
        }
@@ -889,13 +859,13 @@ impl From<Specificity> for u32 {
     }
 }
 
-fn specificity<Impl>(complex_selector: &ComplexSelector<Impl>) -> u32
+fn specificity<Impl>(iter: SelectorIter<Impl>) -> u32
     where Impl: SelectorImpl
 {
-    complex_selector_specificity(complex_selector).into()
+    complex_selector_specificity(iter).into()
 }
 
-fn complex_selector_specificity<Impl>(selector: &ComplexSelector<Impl>)
+fn complex_selector_specificity<Impl>(mut iter: SelectorIter<Impl>)
                                       -> Specificity
     where Impl: SelectorImpl
 {
@@ -944,9 +914,7 @@ fn complex_selector_specificity<Impl>(selector: &ComplexSelector<Impl>)
         }
     }
 
-
     let mut specificity = Default::default();
-    let mut iter = selector.iter();
     loop {
         for simple_selector in &mut iter {
             simple_selector_specificity(&simple_selector, &mut specificity);
@@ -958,43 +926,20 @@ fn complex_selector_specificity<Impl>(selector: &ComplexSelector<Impl>)
     specificity
 }
 
+/// We make this large because the result of parsing a selector is fed into a new
+/// Arc-ed allocation, so any spilled vec would be a wasted allocation. Also,
+/// Components are large enough that we don't have much cache locality benefit
+/// from reserving stack space for fewer of them.
+type ParseVec<Impl> = SmallVec<[Component<Impl>; 32]>;
+
 /// 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, has_pseudo_element) = parse_complex_selector(parser, input)?;
-    let mut specificity = specificity(&complex);
-    if has_pseudo_element {
-        specificity |= HAS_PSEUDO_BIT;
-    }
-    Ok(Selector {
-        specificity_and_flags: specificity,
-        inner: SelectorInner::new(complex),
-    })
-}
-
-/// We use a SmallVec for parsing to avoid extra reallocs compared to using a Vec
-/// directly. When parsing is done, we convert the SmallVec into a Vec (which is
-/// free if the vec has already spilled to the heap, and more cache-friendly if
-/// it hasn't), and then steal the buffer of that vec into a boxed slice.
-///
-/// If we parse N <= 4 entries, we save no reallocations.
-/// If we parse 4 < N <= 8 entries, we save one reallocation.
-/// If we parse N > 8 entries, we save two reallocations.
-type ParseVec<Impl> = SmallVec<[Component<Impl>; 8]>;
-
-/// Parses a complex selector, including any pseudo-element.
-///
-/// For now, it always forces the pseudo-element to be at the end of the
-/// selector, and the boolean represents whether the last thing parsed was a
-/// pseudo-element.
-fn parse_complex_selector<P, Impl>(
+fn parse_selector<P, Impl>(
         parser: &P,
         input: &mut CssParser)
-        -> Result<(ComplexSelector<Impl>, bool), ()>
+        -> Result<Selector<Impl>, ()>
     where P: Parser<Impl=Impl>, Impl: SelectorImpl
 {
     let mut sequence = ParseVec::new();
@@ -1042,21 +987,29 @@ fn parse_complex_selector<P, Impl>(
         sequence.push(Component::Combinator(combinator));
     }
 
-    let complex = ComplexSelector(ArcSlice::new(sequence.into_vec().into_boxed_slice()));
-    Ok((complex, parsed_pseudo_element))
+    let mut spec = SpecificityAndFlags(specificity(SelectorIter {
+        iter: sequence.iter().rev(),
+        next_combinator: None,
+    }));
+    if parsed_pseudo_element {
+        spec.0 |= HAS_PSEUDO_BIT;
+    }
+
+    let header = HeaderWithLength::new(spec, sequence.len());
+    let complex = Selector(Arc::into_thin(Arc::from_header_and_iter(header, sequence.into_iter())));
+    Ok(complex)
 }
 
-impl<Impl: SelectorImpl> ComplexSelector<Impl> {
-    /// Parse a complex selector, without any pseudo-element.
+impl<Impl: SelectorImpl> Selector<Impl> {
+    /// Parse a selector, without any pseudo-element.
     pub fn parse<P>(parser: &P, input: &mut CssParser) -> Result<Self, ()>
         where P: Parser<Impl=Impl>
     {
-        let (complex, has_pseudo_element) =
-            parse_complex_selector(parser, input)?;
-        if has_pseudo_element {
+        let selector = parse_selector(parser, input)?;
+        if selector.has_pseudo_element() {
             return Err(())
         }
-        Ok(complex)
+        Ok(selector)
     }
 }
 
@@ -1761,7 +1714,7 @@ pub mod tests {
         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);
+            assert_eq!(selectors.0[0].selector.to_css_string(), input);
         }
         result
     }
@@ -1784,185 +1737,164 @@ pub mod tests {
         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 {
-            inner: SelectorInner::from_vec(vec!(
+        assert_eq!(parse("EeÉ"), Ok(SelectorList::from_vec(vec!(
+            Selector::from_vec(vec!(
                 Component::LocalName(LocalName {
                     name: DummyAtom::from("EeÉ"),
-                    lower_name: DummyAtom::from("eeÉ") })),
-            ),
-            specificity_and_flags: specificity(0, 0, 1),
-        }))));
-        assert_eq!(parse("|e"), Ok(SelectorList(vec!(Selector {
-            inner: SelectorInner::from_vec(vec!(
+                    lower_name: DummyAtom::from("eeÉ") })
+            ), specificity(0, 0, 1))
+        ))));
+        assert_eq!(parse("|e"), Ok(SelectorList::from_vec(vec!(
+            Selector::from_vec(vec!(
                 Component::ExplicitNoNamespace,
                 Component::LocalName(LocalName {
                     name: DummyAtom::from("e"),
                     lower_name: DummyAtom::from("e")
-                }),
-            )),
-            specificity_and_flags: specificity(0, 0, 1),
-        }))));
+                })), specificity(0, 0, 1))
+        ))));
         // https://github.com/servo/servo/issues/16020
-        assert_eq!(parse("*|e"), Ok(SelectorList(vec!(Selector {
-            inner: SelectorInner::from_vec(vec!(
+        assert_eq!(parse("*|e"), Ok(SelectorList::from_vec(vec!(
+            Selector::from_vec(vec!(
                 Component::ExplicitAnyNamespace,
                 Component::LocalName(LocalName {
                     name: DummyAtom::from("e"),
                     lower_name: DummyAtom::from("e")
-                }),
-            )),
-            specificity_and_flags: specificity(0, 0, 1),
-        }))));
-        assert_eq!(parse("*"), Ok(SelectorList(vec!(Selector {
-            inner: SelectorInner::from_vec(vec!(
+                })
+            ), specificity(0, 0, 1))
+        ))));
+        assert_eq!(parse("*"), Ok(SelectorList::from_vec(vec!(
+            Selector::from_vec(vec!(
                 Component::ExplicitUniversalType,
-            )),
-            specificity_and_flags: specificity(0, 0, 0),
-        }))));
-        assert_eq!(parse("|*"), Ok(SelectorList(vec!(Selector {
-            inner: SelectorInner::from_vec(vec!(
+            ), specificity(0, 0, 0))
+        ))));
+        assert_eq!(parse("|*"), Ok(SelectorList::from_vec(vec!(
+            Selector::from_vec(vec!(
                 Component::ExplicitNoNamespace,
                 Component::ExplicitUniversalType,
-            )),
-            specificity_and_flags: specificity(0, 0, 0),
-        }))));
-        assert_eq!(parse("*|*"), Ok(SelectorList(vec!(Selector {
-            inner: SelectorInner::from_vec(vec!(
+            ), specificity(0, 0, 0))
+        ))));
+        assert_eq!(parse("*|*"), Ok(SelectorList::from_vec(vec!(
+            Selector::from_vec(vec!(
                 Component::ExplicitAnyNamespace,
                 Component::ExplicitUniversalType,
-            )),
-            specificity_and_flags: specificity(0, 0, 0),
-        }))));
-        assert_eq!(parse(".foo:lang(en-US)"), Ok(SelectorList(vec!(Selector {
-            inner: SelectorInner::from_vec(vec![
+            ), specificity(0, 0, 0))
+        ))));
+        assert_eq!(parse(".foo:lang(en-US)"), Ok(SelectorList::from_vec(vec!(
+            Selector::from_vec(vec!(
                     Component::Class(DummyAtom::from("foo")),
                     Component::NonTSPseudoClass(PseudoClass::Lang("en-US".to_owned()))
-            ]),
-            specificity_and_flags: specificity(0, 2, 0),
-        }))));
-        assert_eq!(parse("#bar"), Ok(SelectorList(vec!(Selector {
-            inner: SelectorInner::from_vec(vec!(Component::ID(DummyAtom::from("bar")))),
-            specificity_and_flags: specificity(1, 0, 0),
-        }))));
-        assert_eq!(parse("e.foo#bar"), Ok(SelectorList(vec!(Selector {
-            inner: SelectorInner::from_vec(vec!(Component::LocalName(LocalName {
-                                            name: DummyAtom::from("e"),
-                                            lower_name: DummyAtom::from("e") }),
-                                       Component::Class(DummyAtom::from("foo")),
-                                       Component::ID(DummyAtom::from("bar")))),
-            specificity_and_flags: specificity(1, 1, 1),
-        }))));
-        assert_eq!(parse("e.foo #bar"), Ok(SelectorList(vec!(Selector {
-            inner: SelectorInner::from_vec(vec!(
-                           Component::LocalName(LocalName {
-                               name: DummyAtom::from("e"),
-                               lower_name: DummyAtom::from("e")
-                           }),
-                           Component::Class(DummyAtom::from("foo")),
-                           Component::Combinator(Combinator::Descendant),
-                           Component::ID(DummyAtom::from("bar")),
-                       )),
-            specificity_and_flags: specificity(1, 1, 1),
-        }))));
+            ), specificity(0, 2, 0))
+        ))));
+        assert_eq!(parse("#bar"), Ok(SelectorList::from_vec(vec!(
+            Selector::from_vec(vec!(
+                Component::ID(DummyAtom::from("bar"))
+            ), specificity(1, 0, 0))
+        ))));
+        assert_eq!(parse("e.foo#bar"), Ok(SelectorList::from_vec(vec!(
+            Selector::from_vec(vec!(
+                Component::LocalName(LocalName {
+                    name: DummyAtom::from("e"),
+                    lower_name: DummyAtom::from("e")
+                }),
+                Component::Class(DummyAtom::from("foo")),
+                Component::ID(DummyAtom::from("bar"))
+            ), specificity(1, 1, 1))
+        ))));
+        assert_eq!(parse("e.foo #bar"), Ok(SelectorList::from_vec(vec!(
+            Selector::from_vec(vec!(
+               Component::LocalName(LocalName {
+                   name: DummyAtom::from("e"),
+                   lower_name: DummyAtom::from("e")
+               }),
+               Component::Class(DummyAtom::from("foo")),
+               Component::Combinator(Combinator::Descendant),
+               Component::ID(DummyAtom::from("bar")),
+            ), 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 {
-            inner: SelectorInner::from_vec(vec![
+        assert_eq!(parse_ns("[Foo]", &parser), Ok(SelectorList::from_vec(vec!(
+            Selector::from_vec(vec!(
                 Component::AttributeInNoNamespaceExists {
                     local_name: DummyAtom::from("Foo"),
                     local_name_lower: DummyAtom::from("foo"),
                 }
-            ]),
-            specificity_and_flags: specificity(0, 1, 0),
-        }))));
+            ), specificity(0, 1, 0))
+        ))));
         assert_eq!(parse_ns("svg|circle", &parser), Err(()));
         parser.ns_prefixes.insert(DummyAtom("svg".into()), DummyAtom(SVG.into()));
-        assert_eq!(parse_ns("svg|circle", &parser), Ok(SelectorList(vec![Selector {
-            inner: SelectorInner::from_vec(
-                vec![
-                    Component::Namespace(DummyAtom("svg".into()), SVG.into()),
-                    Component::LocalName(LocalName {
-                        name: DummyAtom::from("circle"),
-                        lower_name: DummyAtom::from("circle"),
-                    })
-                ]),
-            specificity_and_flags: specificity(0, 0, 1),
-        }])));
-        assert_eq!(parse_ns("svg|*", &parser), Ok(SelectorList(vec![Selector {
-            inner: SelectorInner::from_vec(
-                vec![
-                    Component::Namespace(DummyAtom("svg".into()), SVG.into()),
-                    Component::ExplicitUniversalType,
-                ]),
-            specificity_and_flags: specificity(0, 0, 0),
-        }])));
+        assert_eq!(parse_ns("svg|circle", &parser), Ok(SelectorList::from_vec(vec!(
+            Selector::from_vec(vec!(
+                Component::Namespace(DummyAtom("svg".into()), SVG.into()),
+                Component::LocalName(LocalName {
+                    name: DummyAtom::from("circle"),
+                    lower_name: DummyAtom::from("circle"),
+                })
+            ), specificity(0, 0, 1))
+        ))));
+        assert_eq!(parse_ns("svg|*", &parser), Ok(SelectorList::from_vec(vec!(
+            Selector::from_vec(vec!(
+                Component::Namespace(DummyAtom("svg".into()), SVG.into()),
+                Component::ExplicitUniversalType,
+            ), specificity(0, 0, 0))
+        ))));
         // 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 {
-            inner: SelectorInner::from_vec(
-                vec![
-                    Component::DefaultNamespace(MATHML.into()),
-                    Component::AttributeInNoNamespaceExists {
-                        local_name: DummyAtom::from("Foo"),
-                        local_name_lower: DummyAtom::from("foo"),
-                    },
-                ]),
-            specificity_and_flags: specificity(0, 1, 0),
-        }))));
+        assert_eq!(parse_ns("[Foo]", &parser), Ok(SelectorList::from_vec(vec!(
+            Selector::from_vec(vec!(
+                Component::DefaultNamespace(MATHML.into()),
+                Component::AttributeInNoNamespaceExists {
+                    local_name: DummyAtom::from("Foo"),
+                    local_name_lower: DummyAtom::from("foo"),
+                },
+            ), specificity(0, 1, 0))
+        ))));
         // Default namespace does apply to type selectors
-        assert_eq!(parse_ns("e", &parser), Ok(SelectorList(vec!(Selector {
-            inner: SelectorInner::from_vec(
-                vec!(
-                    Component::DefaultNamespace(MATHML.into()),
-                    Component::LocalName(LocalName {
-                        name: DummyAtom::from("e"),
-                        lower_name: DummyAtom::from("e") }),
-                )),
-            specificity_and_flags: specificity(0, 0, 1),
-        }))));
-        assert_eq!(parse_ns("*", &parser), Ok(SelectorList(vec!(Selector {
-            inner: SelectorInner::from_vec(
-                vec!(
-                    Component::DefaultNamespace(MATHML.into()),
-                    Component::ExplicitUniversalType,
-                )),
-            specificity_and_flags: specificity(0, 0, 0),
-        }))));
-        assert_eq!(parse_ns("*|*", &parser), Ok(SelectorList(vec!(Selector {
-            inner: SelectorInner::from_vec(
-                vec!(
-                    Component::ExplicitAnyNamespace,
-                    Component::ExplicitUniversalType,
-                )),
-            specificity_and_flags: specificity(0, 0, 0),
-        }))));
+        assert_eq!(parse_ns("e", &parser), Ok(SelectorList::from_vec(vec!(
+            Selector::from_vec(vec!(
+                Component::DefaultNamespace(MATHML.into()),
+                Component::LocalName(LocalName {
+                    name: DummyAtom::from("e"),
+                    lower_name: DummyAtom::from("e") }),
+            ), specificity(0, 0, 1))
+        ))));
+        assert_eq!(parse_ns("*", &parser), Ok(SelectorList::from_vec(vec!(
+            Selector::from_vec(vec!(
+                Component::DefaultNamespace(MATHML.into()),
+                Component::ExplicitUniversalType,
+            ), specificity(0, 0, 0))
+        ))));
+        assert_eq!(parse_ns("*|*", &parser), Ok(SelectorList::from_vec(vec!(
+            Selector::from_vec(vec!(
+                Component::ExplicitAnyNamespace,
+                Component::ExplicitUniversalType,
+            ), specificity(0, 0, 0))
+        ))));
         // Default namespace applies to universal and type selectors inside :not and :matches,
         // but not otherwise.
-        assert_eq!(parse_ns(":not(.cl)", &parser), Ok(SelectorList(vec!(Selector {
-            inner: SelectorInner::from_vec(vec!(
+        assert_eq!(parse_ns(":not(.cl)", &parser), Ok(SelectorList::from_vec(vec!(
+            Selector::from_vec(vec!(
                 Component::DefaultNamespace(MATHML.into()),
                 Component::Negation(vec![
                     Component::Class(DummyAtom::from("cl"))
                 ].into_boxed_slice()),
-            )),
-            specificity_and_flags: specificity(0, 1, 0),
-        }))));
-        assert_eq!(parse_ns(":not(*)", &parser), Ok(SelectorList(vec!(Selector {
-            inner: SelectorInner::from_vec(vec!(
+            ), specificity(0, 1, 0))
+        ))));
+        assert_eq!(parse_ns(":not(*)", &parser), Ok(SelectorList::from_vec(vec!(
+            Selector::from_vec(vec!(
                 Component::DefaultNamespace(MATHML.into()),
                 Component::Negation(vec![
                     Component::DefaultNamespace(MATHML.into()),
                     Component::ExplicitUniversalType,
                 ].into_boxed_slice()),
-            )),
-            specificity_and_flags: specificity(0, 0, 0),
-        }))));
-        assert_eq!(parse_ns(":not(e)", &parser), Ok(SelectorList(vec!(Selector {
-            inner: SelectorInner::from_vec(vec!(
+            ), specificity(0, 0, 0))
+        ))));
+        assert_eq!(parse_ns(":not(e)", &parser), Ok(SelectorList::from_vec(vec!(
+            Selector::from_vec(vec!(
                 Component::DefaultNamespace(MATHML.into()),
                 Component::Negation(vec![
                     Component::DefaultNamespace(MATHML.into()),
@@ -1971,51 +1903,39 @@ pub mod tests {
                         lower_name: DummyAtom::from("e")
                     }),
                 ].into_boxed_slice())
-            )),
-            specificity_and_flags: specificity(0, 0, 1),
-        }))));
-        assert_eq!(parse("[attr |= \"foo\"]"), Ok(SelectorList(vec![Selector {
-            inner: SelectorInner::from_vec(
-                vec![
-                    Component::AttributeInNoNamespace {
-                        local_name: DummyAtom::from("attr"),
-                        local_name_lower: DummyAtom::from("attr"),
-                        operator: AttrSelectorOperator::DashMatch,
-                        value: DummyAtom::from("foo"),
-                        never_matches: false,
-                        case_sensitivity: ParsedCaseSensitivity::CaseSensitive,
-                    }
-                ]),
-            specificity_and_flags: specificity(0, 1, 0),
-        }])));
+            ), specificity(0, 0, 1))
+        ))));
+        assert_eq!(parse("[attr |= \"foo\"]"), Ok(SelectorList::from_vec(vec!(
+            Selector::from_vec(vec!(
+                Component::AttributeInNoNamespace {
+                    local_name: DummyAtom::from("attr"),
+                    local_name_lower: DummyAtom::from("attr"),
+                    operator: AttrSelectorOperator::DashMatch,
+                    value: DummyAtom::from("foo"),
+                    never_matches: false,
+                    case_sensitivity: ParsedCaseSensitivity::CaseSensitive,
+                }
+            ), specificity(0, 1, 0))
+        ))));
         // https://github.com/mozilla/servo/issues/1723
-        assert_eq!(parse("::before"), Ok(SelectorList(vec!(Selector {
-            inner: SelectorInner::from_vec(
-                vec![
-                    Component::PseudoElement(PseudoElement::Before),
-                ]
-            ),
-            specificity_and_flags: specificity(0, 0, 1) | HAS_PSEUDO_BIT,
-        }))));
-        assert_eq!(parse("::before:hover"), Ok(SelectorList(vec!(Selector {
-            inner: SelectorInner::from_vec(
-                vec![
-                    Component::PseudoElement(PseudoElement::Before),
-                    Component::NonTSPseudoClass(PseudoClass::Hover),
-                ]
-            ),
-            specificity_and_flags: specificity(0, 1, 1) | HAS_PSEUDO_BIT,
-        }))));
-        assert_eq!(parse("::before:hover:hover"), Ok(SelectorList(vec!(Selector {
-            inner: SelectorInner::from_vec(
-                vec![
-                    Component::PseudoElement(PseudoElement::Before),
-                    Component::NonTSPseudoClass(PseudoClass::Hover),
-                    Component::NonTSPseudoClass(PseudoClass::Hover),
-                ]
-            ),
-            specificity_and_flags: specificity(0, 2, 1) | HAS_PSEUDO_BIT,
-        }))));
+        assert_eq!(parse("::before"), Ok(SelectorList::from_vec(vec!(
+            Selector::from_vec(vec!(
+                Component::PseudoElement(PseudoElement::Before),
+            ), specificity(0, 0, 1) | HAS_PSEUDO_BIT)
+        ))));
+        assert_eq!(parse("::before:hover"), Ok(SelectorList::from_vec(vec!(
+            Selector::from_vec(vec!(
+                Component::PseudoElement(PseudoElement::Before),
+                Component::NonTSPseudoClass(PseudoClass::Hover),
+            ), specificity(0, 1, 1) | HAS_PSEUDO_BIT)
+        ))));
+        assert_eq!(parse("::before:hover:hover"), Ok(SelectorList::from_vec(vec!(
+            Selector::from_vec(vec!(
+                Component::PseudoElement(PseudoElement::Before),
+                Component::NonTSPseudoClass(PseudoClass::Hover),
+                Component::NonTSPseudoClass(PseudoClass::Hover),
+            ), specificity(0, 2, 1) | HAS_PSEUDO_BIT)
+        ))));
         assert_eq!(parse("::before:hover:active"), Err(()));
         assert_eq!(parse("::before:hover .foo"), Err(()));
         assert_eq!(parse("::before .foo"), Err(()));
@@ -2024,41 +1944,35 @@ pub mod tests {
 
         // https://github.com/servo/servo/issues/15335
         assert_eq!(parse(":: before"), Err(()));
-        assert_eq!(parse("div ::after"), Ok(SelectorList(vec!(Selector {
-            inner: SelectorInner::from_vec(
-                vec![
-                     Component::LocalName(LocalName {
-                        name: DummyAtom::from("div"),
-                        lower_name: DummyAtom::from("div") }),
-                    Component::Combinator(Combinator::Descendant),
-                    Component::Combinator(Combinator::PseudoElement),
-                    Component::PseudoElement(PseudoElement::After),
-                ]),
-            specificity_and_flags: specificity(0, 0, 2) | HAS_PSEUDO_BIT,
-        }))));
-        assert_eq!(parse("#d1 > .ok"), Ok(SelectorList(vec![Selector {
-            inner: SelectorInner::from_vec(
-                vec![
-                    Component::ID(DummyAtom::from("d1")),
-                    Component::Combinator(Combinator::Child),
-                    Component::Class(DummyAtom::from("ok")),
-                ]),
-            specificity_and_flags: (1 << 20) + (1 << 10) + (0 << 0),
-        }])));
+        assert_eq!(parse("div ::after"), Ok(SelectorList::from_vec(vec!(
+            Selector::from_vec(vec!(
+                 Component::LocalName(LocalName {
+                    name: DummyAtom::from("div"),
+                    lower_name: DummyAtom::from("div") }),
+                Component::Combinator(Combinator::Descendant),
+                Component::Combinator(Combinator::PseudoElement),
+                Component::PseudoElement(PseudoElement::After),
+            ), specificity(0, 0, 2) | HAS_PSEUDO_BIT)
+        ))));
+        assert_eq!(parse("#d1 > .ok"), Ok(SelectorList::from_vec(vec!(
+            Selector::from_vec(vec!(
+                Component::ID(DummyAtom::from("d1")),
+                Component::Combinator(Combinator::Child),
+                Component::Class(DummyAtom::from("ok")),
+            ), (1 << 20) + (1 << 10) + (0 << 0))
+        ))));
         parser.default_ns = None;
         assert_eq!(parse(":not(#provel.old)"), Err(()));
         assert_eq!(parse(":not(#provel > old)"), Err(()));
         assert!(parse("table[rules]:not([rules = \"none\"]):not([rules = \"\"])").is_ok());
-        assert_eq!(parse(":not(#provel)"), Ok(SelectorList(vec!(Selector {
-            inner: SelectorInner::from_vec(vec!(Component::Negation(
-                vec![
+        assert_eq!(parse(":not(#provel)"), Ok(SelectorList::from_vec(vec!(
+            Selector::from_vec(vec!(Component::Negation(vec!(
                     Component::ID(DummyAtom::from("provel")),
-                ].into_boxed_slice()
-            ))),
-            specificity_and_flags: specificity(1, 0, 0),
-        }))));
-        assert_eq!(parse_ns(":not(svg|circle)", &parser), Ok(SelectorList(vec!(Selector {
-            inner: SelectorInner::from_vec(vec!(Component::Negation(
+                ).into_boxed_slice()
+            )), specificity(1, 0, 0))
+        ))));
+        assert_eq!(parse_ns(":not(svg|circle)", &parser), Ok(SelectorList::from_vec(vec!(
+            Selector::from_vec(vec!(Component::Negation(
                 vec![
                     Component::Namespace(DummyAtom("svg".into()), SVG.into()),
                     Component::LocalName(LocalName {
@@ -2066,52 +1980,47 @@ pub mod tests {
                         lower_name: DummyAtom::from("circle")
                     }),
                 ].into_boxed_slice()
-            ))),
-            specificity_and_flags: specificity(0, 0, 1),
-        }))));
+            )), specificity(0, 0, 1))
+        ))));
         // https://github.com/servo/servo/issues/16017
-        assert_eq!(parse_ns(":not(*)", &parser), Ok(SelectorList(vec!(Selector {
-            inner: SelectorInner::from_vec(vec!(Component::Negation(
+        assert_eq!(parse_ns(":not(*)", &parser), Ok(SelectorList::from_vec(vec!(
+            Selector::from_vec(vec!(Component::Negation(
                 vec![
                     Component::ExplicitUniversalType,
                 ].into_boxed_slice()
-            ))),
-            specificity_and_flags: specificity(0, 0, 0),
-        }))));
-        assert_eq!(parse_ns(":not(|*)", &parser), Ok(SelectorList(vec!(Selector {
-            inner: SelectorInner::from_vec(vec!(Component::Negation(
+            )), specificity(0, 0, 0))
+        ))));
+        assert_eq!(parse_ns(":not(|*)", &parser), Ok(SelectorList::from_vec(vec!(
+            Selector::from_vec(vec!(Component::Negation(
                 vec![
                     Component::ExplicitNoNamespace,
                     Component::ExplicitUniversalType,
                 ].into_boxed_slice()
-            ))),
-            specificity_and_flags: specificity(0, 0, 0),
-        }))));
-        assert_eq!(parse_ns(":not(*|*)", &parser), Ok(SelectorList(vec!(Selector {
-            inner: SelectorInner::from_vec(vec!(Component::Negation(
+            )), specificity(0, 0, 0))
+        ))));
+        assert_eq!(parse_ns(":not(*|*)", &parser), Ok(SelectorList::from_vec(vec!(
+            Selector::from_vec(vec!(Component::Negation(
                 vec![
                     Component::ExplicitAnyNamespace,
                     Component::ExplicitUniversalType,
                 ].into_boxed_slice()
-            ))),
-            specificity_and_flags: specificity(0, 0, 0),
-        }))));
-        assert_eq!(parse_ns(":not(svg|*)", &parser), Ok(SelectorList(vec!(Selector {
-            inner: SelectorInner::from_vec(vec!(Component::Negation(
+            )), specificity(0, 0, 0))
+        ))));
+        assert_eq!(parse_ns(":not(svg|*)", &parser), Ok(SelectorList::from_vec(vec!(
+            Selector::from_vec(vec!(Component::Negation(
                 vec![
                     Component::Namespace(DummyAtom("svg".into()), SVG.into()),
                     Component::ExplicitUniversalType,
                 ].into_boxed_slice()
-            ))),
-            specificity_and_flags: specificity(0, 0, 0),
-        }))));
+            )), specificity(0, 0, 0))
+        ))));
     }
 
     #[test]
     fn test_pseudo_iter() {
-        let selector = &parse("q::before").unwrap().0[0];
+        let selector = &parse("q::before").unwrap().0[0].selector;
         assert!(!selector.is_universal());
-        let mut iter = selector.inner.complex.iter();
+        let mut iter = selector.iter();
         assert_eq!(iter.next(), Some(&Component::PseudoElement(PseudoElement::Before)));
         assert_eq!(iter.next(), None);
         let combinator = iter.next_sequence();
@@ -2123,15 +2032,15 @@ pub mod tests {
 
     #[test]
     fn test_universal() {
-        let selector = &parse("*|*::before").unwrap().0[0];
+        let selector = &parse("*|*::before").unwrap().0[0].selector;
         assert!(selector.is_universal());
     }
 
     #[test]
     fn test_empty_pseudo_iter() {
-        let selector = &parse("::before").unwrap().0[0];
+        let selector = &parse("::before").unwrap().0[0].selector;
         assert!(selector.is_universal());
-        let mut iter = selector.inner.complex.iter();
+        let mut iter = selector.iter();
         assert_eq!(iter.next(), Some(&Component::PseudoElement(PseudoElement::Before)));
         assert_eq!(iter.next(), None);
         assert_eq!(iter.next_sequence(), None);
@@ -2155,11 +2064,11 @@ pub mod tests {
     #[test]
     fn visitor() {
         let mut test_visitor = TestVisitor { seen: vec![], };
-        parse(":not(:hover) ~ label").unwrap().0[0].visit(&mut test_visitor);
+        parse(":not(:hover) ~ label").unwrap().0[0].selector.visit(&mut test_visitor);
         assert!(test_visitor.seen.contains(&":hover".into()));
 
         let mut test_visitor = TestVisitor { seen: vec![], };
-        parse("::before:hover").unwrap().0[0].visit(&mut test_visitor);
+        parse("::before:hover").unwrap().0[0].selector.visit(&mut test_visitor);
         assert!(test_visitor.seen.contains(&":hover".into()));
     }
 }
diff --git a/components/selectors/size_of_tests.rs b/components/selectors/size_of_tests.rs
index 5fec3085fcb..d9ed1651cf7 100644
--- a/components/selectors/size_of_tests.rs
+++ b/components/selectors/size_of_tests.rs
@@ -11,10 +11,8 @@ use precomputed_hash::PrecomputedHash;
 use std::fmt;
 use visitor::SelectorVisitor;
 
-size_of_test!(size_of_selector, Selector<Impl>, 48);
+size_of_test!(size_of_selector, Selector<Impl>, 8);
 size_of_test!(size_of_pseudo_element, gecko_like_types::PseudoElement, 1);
-size_of_test!(size_of_selector_inner, SelectorInner<Impl>, 40);
-size_of_test!(size_of_complex_selector, ComplexSelector<Impl>, 24);
 
 size_of_test!(size_of_component, Component<Impl>, 32);
 size_of_test!(size_of_pseudo_class, PseudoClass, 24);
diff --git a/components/servo_arc/Cargo.toml b/components/servo_arc/Cargo.toml
new file mode 100644
index 00000000000..ffb743bd20a
--- /dev/null
+++ b/components/servo_arc/Cargo.toml
@@ -0,0 +1,18 @@
+[package]
+name = "servo_arc"
+version = "0.0.1"
+authors = ["The Servo Project Developers"]
+license = "MPL-2.0"
+publish = false
+
+[lib]
+name = "servo_arc"
+path = "lib.rs"
+
+[features]
+servo = ["serde", "heapsize"]
+
+[dependencies]
+heapsize = {version = "0.4.0", optional = true}
+serde = {version = "0.9", optional = true}
+nodrop = {version = "0.1.8"}
diff --git a/components/style/stylearc.rs b/components/servo_arc/lib.rs
index 9b355e7d211..5d91c9bc44f 100644
--- a/components/style/stylearc.rs
+++ b/components/servo_arc/lib.rs
@@ -8,11 +8,13 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-//! Fork of Arc for the style system. This has the following advantages over std::Arc:
+//! Fork of Arc for Servo. This has the following advantages over std::Arc:
 //! * We don't waste storage on the weak reference count.
 //! * We don't do extra RMU operations to handle the possibility of weak references.
 //! * We can experiment with arena allocation (todo).
 //! * We can add methods to support our custom use cases [1].
+//! * We have support for dynamically-sized types (see from_header_and_iter).
+//! * We have support for thin arcs to unsized types (see ThinArc).
 //!
 //! [1] https://bugzilla.mozilla.org/show_bug.cgi?id=1360883
 
@@ -20,8 +22,12 @@
 // duplicate those here.
 #![allow(missing_docs)]
 
+#[cfg(feature = "servo")] extern crate serde;
+extern crate nodrop;
+
 #[cfg(feature = "servo")]
 use heapsize::HeapSizeOf;
+use nodrop::NoDrop;
 #[cfg(feature = "servo")]
 use serde::{Deserialize, Serialize};
 use std::{isize, usize};
@@ -30,8 +36,11 @@ use std::cmp::Ordering;
 use std::convert::From;
 use std::fmt;
 use std::hash::{Hash, Hasher};
+use std::iter::{ExactSizeIterator, Iterator};
 use std::mem;
 use std::ops::{Deref, DerefMut};
+use std::ptr;
+use std::slice;
 use std::sync::atomic;
 use std::sync::atomic::Ordering::{Acquire, Relaxed, Release};
 
@@ -412,3 +421,257 @@ impl<T: Serialize> Serialize for Arc<T>
         (**self).serialize(serializer)
     }
 }
+
+/// Structure to allow Arc-managing some fixed-sized data and a variably-sized
+/// slice in a single allocation.
+#[derive(Debug, Eq, PartialEq, PartialOrd)]
+pub struct HeaderSlice<H, T: ?Sized> {
+    /// The fixed-sized data.
+    pub header: H,
+
+    /// The dynamically-sized data.
+    pub slice: T,
+}
+
+#[inline(always)]
+fn divide_rounding_up(dividend: usize, divisor: usize) -> usize {
+    (dividend + divisor - 1) / divisor
+}
+
+impl<H, T> Arc<HeaderSlice<H, [T]>> {
+    /// Creates an Arc for a HeaderSlice using the given header struct and
+    /// iterator to generate the slice. The resulting Arc will be fat.
+    #[inline]
+    pub fn from_header_and_iter<I>(header: H, mut items: I) -> Self
+        where I: Iterator<Item=T> + ExactSizeIterator
+    {
+        use ::std::mem::size_of;
+        assert!(size_of::<T>() != 0, "Need to think about ZST");
+
+        // Compute the required size for the allocation.
+        let num_items = items.len();
+        let size = {
+            // First, determine the alignment of a hypothetical pointer to a
+            // HeaderSlice.
+            let fake_slice_ptr_align: usize = mem::align_of::<ArcInner<HeaderSlice<H, [T; 1]>>>();
+
+            // Next, synthesize a totally garbage (but properly aligned) pointer
+            // to a sequence of T.
+            let fake_slice_ptr = fake_slice_ptr_align as *const T;
+
+            // Convert that sequence to a fat pointer. The address component of
+            // the fat pointer will be garbage, but the length will be correct.
+            let fake_slice = unsafe { slice::from_raw_parts(fake_slice_ptr, num_items) };
+
+            // Pretend the garbage address points to our allocation target (with
+            // a trailing sequence of T), rather than just a sequence of T.
+            let fake_ptr = fake_slice as *const [T] as *const ArcInner<HeaderSlice<H, [T]>>;
+            let fake_ref: &ArcInner<HeaderSlice<H, [T]>> = unsafe { &*fake_ptr };
+
+            // Use size_of_val, which will combine static information about the
+            // type with the length from the fat pointer. The garbage address
+            // will not be used.
+            mem::size_of_val(fake_ref)
+        };
+
+        let ptr: *mut ArcInner<HeaderSlice<H, [T]>>;
+        unsafe {
+            // Allocate the buffer. We use Vec because the underlying allocation
+            // machinery isn't available in stable Rust.
+            //
+            // To avoid alignment issues, we allocate words rather than bytes,
+            // rounding up to the nearest word size.
+            let words_to_allocate = divide_rounding_up(size, size_of::<usize>());
+            let mut vec = Vec::<usize>::with_capacity(words_to_allocate);
+            vec.set_len(words_to_allocate);
+            let buffer = Box::into_raw(vec.into_boxed_slice()) as *mut usize as *mut u8;
+
+            // Synthesize the fat pointer. We do this by claiming we have a direct
+            // pointer to a [T], and then changing the type of the borrow. The key
+            // point here is that the length portion of the fat pointer applies
+            // only to the number of elements in the dynamically-sized portion of
+            // the type, so the value will be the same whether it points to a [T]
+            // or something else with a [T] as its last member.
+            let fake_slice: &mut [T] = slice::from_raw_parts_mut(buffer as *mut T, num_items);
+            ptr = fake_slice as *mut [T] as *mut ArcInner<HeaderSlice<H, [T]>>;
+
+            // Write the data.
+            ptr::write(&mut ((*ptr).count), atomic::AtomicUsize::new(1));
+            ptr::write(&mut ((*ptr).data.header), header);
+            let mut current: *mut T = &mut (*ptr).data.slice[0];
+            for _ in 0..num_items {
+                ptr::write(current, items.next().expect("ExactSizeIterator over-reported length"));
+                current = current.offset(1);
+            }
+            assert!(items.next().is_none(), "ExactSizeIterator under-reported length");
+
+            // We should have consumed the buffer exactly.
+            debug_assert!(current as *mut u8 == buffer.offset(size as isize));
+        }
+
+        // Return the fat Arc.
+        assert_eq!(size_of::<Self>(), size_of::<usize>() * 2, "The Arc will be fat");
+        Arc { ptr: ptr }
+    }
+}
+
+/// Header data with an inline length. Consumers that use HeaderWithLength as the
+/// Header type in HeaderSlice can take advantage of ThinArc.
+#[derive(Debug, Eq, PartialEq, PartialOrd)]
+pub struct HeaderWithLength<H> {
+    /// The fixed-sized data.
+    pub header: H,
+
+    /// The slice length.
+    length: usize,
+}
+
+impl<H> HeaderWithLength<H> {
+    /// Creates a new HeaderWithLength.
+    pub fn new(header: H, length: usize) -> Self {
+        HeaderWithLength {
+            header: header,
+            length: length,
+        }
+    }
+}
+
+pub struct ThinArc<H, T> {
+    ptr: *mut ArcInner<HeaderSlice<HeaderWithLength<H>, [T; 1]>>,
+}
+
+unsafe impl<H: Sync + Send, T: Sync + Send> Send for ThinArc<H, T> {}
+unsafe impl<H: Sync + Send, T: Sync + Send> Sync for ThinArc<H, T> {}
+
+// Synthesize a fat pointer from a thin pointer.
+//
+// See the comment around the analogous operation in from_header_and_iter.
+fn thin_to_thick<H, T>(thin: *mut ArcInner<HeaderSlice<HeaderWithLength<H>, [T; 1]>>)
+    -> *mut ArcInner<HeaderSlice<HeaderWithLength<H>, [T]>>
+{
+    let len = unsafe { (*thin).data.header.length };
+    let fake_slice: *mut [T] = unsafe {
+        slice::from_raw_parts_mut(thin as *mut T, len)
+    };
+
+    fake_slice as *mut ArcInner<HeaderSlice<HeaderWithLength<H>, [T]>>
+}
+
+impl<H, T> ThinArc<H, T> {
+    /// Temporarily converts |self| into a bonafide Arc and exposes it to the
+    /// provided callback. The refcount is not modified.
+    #[inline(always)]
+    pub fn with_arc<F, U>(&self, f: F) -> U
+        where F: FnOnce(&Arc<HeaderSlice<HeaderWithLength<H>, [T]>>) -> U
+    {
+        // Synthesize transient Arc, which never touches the refcount of the ArcInner.
+        let transient = NoDrop::new(Arc {
+            ptr: thin_to_thick(self.ptr)
+        });
+
+        // Expose the transient Arc to the callback, which may clone it if it wants.
+        let result = f(&transient);
+
+        // Forget the transient Arc to leave the refcount untouched.
+        mem::forget(transient);
+
+        // Forward the result.
+        result
+    }
+}
+
+impl<H, T> Deref for ThinArc<H, T> {
+    type Target = HeaderSlice<HeaderWithLength<H>, [T]>;
+    fn deref(&self) -> &Self::Target {
+        unsafe { &(*thin_to_thick(self.ptr)).data }
+    }
+}
+
+impl<H, T> Clone for ThinArc<H, T> {
+    fn clone(&self) -> Self {
+        ThinArc::with_arc(self, |a| Arc::into_thin(a.clone()))
+    }
+}
+
+impl<H, T> Drop for ThinArc<H, T> {
+    fn drop(&mut self) {
+        let _ = Arc::from_thin(ThinArc { ptr: self.ptr });
+    }
+}
+
+impl<H, T> Arc<HeaderSlice<HeaderWithLength<H>, [T]>> {
+    /// Converts an Arc into a ThinArc. This consumes the Arc, so the refcount
+    /// is not modified.
+    pub fn into_thin(a: Self) -> ThinArc<H, T> {
+        assert!(a.header.length == a.slice.len(),
+                "Length needs to be correct for ThinArc to work");
+        let fat_ptr: *mut ArcInner<HeaderSlice<HeaderWithLength<H>, [T]>> = a.ptr;
+        mem::forget(a);
+        let thin_ptr = fat_ptr as *mut [usize] as *mut usize;
+        ThinArc {
+            ptr: thin_ptr as *mut ArcInner<HeaderSlice<HeaderWithLength<H>, [T; 1]>>
+        }
+    }
+
+    /// Converts a ThinArc into an Arc. This consumes the ThinArc, so the refcount
+    /// is not modified.
+    pub fn from_thin(a: ThinArc<H, T>) -> Self {
+        let ptr = thin_to_thick(a.ptr);
+        mem::forget(a);
+        Arc {
+            ptr: ptr
+        }
+    }
+}
+
+impl<H: PartialEq, T: PartialEq> PartialEq for ThinArc<H, T> {
+    fn eq(&self, other: &ThinArc<H, T>) -> bool {
+        ThinArc::with_arc(self, |a| {
+            ThinArc::with_arc(other, |b| {
+                *a == *b
+            })
+        })
+    }
+}
+
+impl<H: Eq, T: Eq> Eq for ThinArc<H, T> {}
+
+#[cfg(test)]
+mod tests {
+    use std::clone::Clone;
+    use std::ops::Drop;
+    use std::sync::atomic;
+    use std::sync::atomic::Ordering::{Acquire, SeqCst};
+    use super::{Arc, HeaderWithLength, ThinArc};
+
+    #[derive(PartialEq)]
+    struct Canary(*mut atomic::AtomicUsize);
+
+    impl Drop for Canary {
+        fn drop(&mut self) {
+            unsafe {
+                match *self {
+                    Canary(c) => {
+                        (*c).fetch_add(1, SeqCst);
+                    }
+                }
+            }
+        }
+    }
+
+    #[test]
+    fn slices_and_thin() {
+        let mut canary = atomic::AtomicUsize::new(0);
+        let c = Canary(&mut canary as *mut atomic::AtomicUsize);
+        let v = vec![5, 6];
+        let header = HeaderWithLength::new(c, v.len());
+        {
+            let x = Arc::into_thin(Arc::from_header_and_iter(header, v.into_iter()));
+            let y = ThinArc::with_arc(&x, |q| q.clone());
+            let _ = y.clone();
+            let _ = x == x;
+            Arc::from_thin(x.clone());
+        }
+        assert!(canary.load(Acquire) == 1);
+    }
+}
diff --git a/components/style/Cargo.toml b/components/style/Cargo.toml
index 4b33f660a68..a8751e1646b 100644
--- a/components/style/Cargo.toml
+++ b/components/style/Cargo.toml
@@ -61,6 +61,7 @@ rayon = "0.7.1"
 selectors = { path = "../selectors" }
 serde = {version = "0.9", optional = true}
 serde_derive = {version = "0.9", optional = true}
+servo_arc = { path = "../servo_arc" }
 servo_atoms = {path = "../atoms", optional = true}
 servo_config = {path = "../config", optional = true}
 smallvec = "0.4"
diff --git a/components/style/gecko/selector_parser.rs b/components/style/gecko/selector_parser.rs
index b6051f1f34c..90d503f58ab 100644
--- a/components/style/gecko/selector_parser.rs
+++ b/components/style/gecko/selector_parser.rs
@@ -8,7 +8,7 @@ use cssparser::{Parser, ToCss};
 use element_state::ElementState;
 use gecko_bindings::structs::CSSPseudoClassType;
 use selector_parser::{SelectorParser, PseudoElementCascadeType};
-use selectors::parser::{ComplexSelector, SelectorMethods};
+use selectors::parser::{Selector, SelectorMethods};
 use selectors::visitor::SelectorVisitor;
 use std::borrow::Cow;
 use std::fmt;
@@ -47,7 +47,7 @@ macro_rules! pseudo_class_name {
             ///
             /// TODO(emilio): We disallow combinators and pseudos here, so we
             /// should use SimpleSelector instead
-            MozAny(Box<[ComplexSelector<SelectorImpl>]>),
+            MozAny(Box<[Selector<SelectorImpl>]>),
         }
     }
 }
@@ -273,7 +273,7 @@ impl<'a> ::selectors::Parser for SelectorParser<'a> {
                     }, )*
                     "-moz-any" => {
                         let selectors = parser.parse_comma_separated(|input| {
-                            ComplexSelector::parse(self, input)
+                            Selector::parse(self, input)
                         })?;
                         // Selectors inside `:-moz-any` may not include combinators.
                         if selectors.iter().flat_map(|x| x.iter_raw()).any(|s| s.is_combinator()) {
diff --git a/components/style/gecko/wrapper.rs b/components/style/gecko/wrapper.rs
index d808f148d85..d9baeb79312 100644
--- a/components/style/gecko/wrapper.rs
+++ b/components/style/gecko/wrapper.rs
@@ -1405,7 +1405,7 @@ impl<'le> ::selectors::Element for GeckoElement<'le> {
             NonTSPseudoClass::MozPlaceholder => false,
             NonTSPseudoClass::MozAny(ref sels) => {
                 sels.iter().any(|s| {
-                    matches_complex_selector(s, self, context, flags_setter)
+                    matches_complex_selector(s, 0, self, context, flags_setter)
                 })
             }
             NonTSPseudoClass::MozSystemMetric(ref s) |
diff --git a/components/style/invalidation/stylesheets.rs b/components/style/invalidation/stylesheets.rs
index 93f0d8783ad..a222b611d44 100644
--- a/components/style/invalidation/stylesheets.rs
+++ b/components/style/invalidation/stylesheets.rs
@@ -218,7 +218,7 @@ impl StylesheetInvalidationSet {
         let mut scope: Option<InvalidationScope> = None;
 
         let mut scan = true;
-        let mut iter = selector.inner.complex.iter();
+        let mut iter = selector.iter();
 
         loop {
             for component in &mut iter {
@@ -262,8 +262,8 @@ impl StylesheetInvalidationSet {
         match *rule {
             Style(ref lock) => {
                 let style_rule = lock.read_with(guard);
-                for selector in &style_rule.selectors.0 {
-                    self.collect_scopes(selector);
+                for selector_and_hashes in &style_rule.selectors.0 {
+                    self.collect_scopes(&selector_and_hashes.selector);
                     if self.fully_invalid {
                         return;
                     }
diff --git a/components/style/lib.rs b/components/style/lib.rs
index 4856610b9ed..0cde26b37f0 100644
--- a/components/style/lib.rs
+++ b/components/style/lib.rs
@@ -72,8 +72,8 @@ extern crate pdqsort;
 #[cfg(feature = "gecko")] extern crate precomputed_hash;
 extern crate rayon;
 extern crate selectors;
-#[cfg(feature = "servo")] extern crate serde;
 #[cfg(feature = "servo")] #[macro_use] extern crate serde_derive;
+pub extern crate servo_arc;
 #[cfg(feature = "servo")] #[macro_use] extern crate servo_atoms;
 #[cfg(feature = "servo")] extern crate servo_config;
 #[cfg(feature = "servo")] extern crate servo_url;
@@ -129,7 +129,6 @@ pub mod sequential;
 pub mod sink;
 pub mod str;
 pub mod style_adjuster;
-pub mod stylearc;
 pub mod stylesheet_set;
 pub mod stylesheets;
 pub mod thread_state;
@@ -139,6 +138,10 @@ pub mod traversal;
 #[allow(non_camel_case_types)]
 pub mod values;
 
+// Compat shim for the old name when it lived in the style crate.
+// FIXME(bholley) Remove this.
+pub use servo_arc as stylearc;
+
 use std::fmt;
 use style_traits::ToCss;
 
diff --git a/components/style/restyle_hints.rs b/components/style/restyle_hints.rs
index acca66d6fdb..9c62fbe01b5 100644
--- a/components/style/restyle_hints.rs
+++ b/components/style/restyle_hints.rs
@@ -22,7 +22,8 @@ use selectors::Element;
 use selectors::attr::{AttrSelectorOperation, NamespaceConstraint};
 use selectors::matching::{ElementSelectorFlags, MatchingContext, MatchingMode};
 use selectors::matching::{RelevantLinkStatus, VisitedHandlingMode, matches_selector};
-use selectors::parser::{Combinator, Component, Selector, SelectorInner, SelectorMethods};
+use selectors::parser::{AncestorHashes, Combinator, Component};
+use selectors::parser::{Selector, SelectorAndHashes, SelectorIter, SelectorMethods};
 use selectors::visitor::SelectorVisitor;
 use smallvec::SmallVec;
 use std::cell::Cell;
@@ -642,7 +643,7 @@ impl<'a, E> Element for ElementWrapper<'a, E>
             use selectors::matching::matches_complex_selector;
             if let NonTSPseudoClass::MozAny(ref selectors) = *pseudo_class {
                 return selectors.iter().any(|s| {
-                    matches_complex_selector(s, self, context, _setter)
+                    matches_complex_selector(s, 0, self, context, _setter)
                 })
             }
         }
@@ -866,8 +867,15 @@ impl Sensitivities {
 #[derive(Clone, Debug)]
 #[cfg_attr(feature = "servo", derive(HeapSizeOf))]
 pub struct Dependency {
+    /// The dependency selector.
     #[cfg_attr(feature = "servo", ignore_heap_size_of = "Arc")]
-    selector: SelectorInner<SelectorImpl>,
+    selector: Selector<SelectorImpl>,
+    /// The offset into the selector that we should match on.
+    selector_offset: usize,
+    /// The ancestor hashes associated with the above selector at the given
+    /// offset.
+    #[cfg_attr(feature = "servo", ignore_heap_size_of = "No heap data")]
+    hashes: AncestorHashes,
     /// The hint associated with this dependency.
     pub hint: RestyleHint,
     /// The sensitivities associated with this dependency.
@@ -875,8 +883,12 @@ pub struct Dependency {
 }
 
 impl SelectorMapEntry for Dependency {
-    fn selector(&self) -> &SelectorInner<SelectorImpl> {
-        &self.selector
+    fn selector(&self) -> SelectorIter<SelectorImpl> {
+        self.selector.iter_from(self.selector_offset)
+    }
+
+    fn hashes(&self) -> &AncestorHashes {
+        &self.hashes
     }
 }
 
@@ -940,9 +952,9 @@ pub enum HintComputationContext<'a, E: 'a>
 
 impl DependencySet {
     /// Adds a selector to this `DependencySet`.
-    pub fn note_selector(&mut self, selector: &Selector<SelectorImpl>) {
+    pub fn note_selector(&mut self, selector_and_hashes: &SelectorAndHashes<SelectorImpl>) {
         let mut combinator = None;
-        let mut iter = selector.inner.complex.iter();
+        let mut iter = selector_and_hashes.selector.iter();
         let mut index = 0;
         let mut child_combinators_seen = 0;
         let mut saw_descendant_combinator = false;
@@ -992,17 +1004,21 @@ impl DependencySet {
                     None => RestyleHint::for_self(),
                 };
 
-                let dep_selector = if sequence_start == 0 {
-                    // Reuse the bloom hashes if this is the base selector.
-                    selector.inner.clone()
+                // Reuse the bloom hashes if this is the base selector. Otherwise,
+                // rebuild them.
+                let hashes = if sequence_start == 0 {
+                    selector_and_hashes.hashes.clone()
                 } else {
-                    SelectorInner::new(selector.inner.complex.slice_from(sequence_start))
+                    let seq_iter = selector_and_hashes.selector.iter_from(sequence_start);
+                    AncestorHashes::from_iter(seq_iter)
                 };
 
                 self.dependencies.insert(Dependency {
                     sensitivities: visitor.sensitivities,
                     hint: hint,
-                    selector: dep_selector,
+                    selector: selector_and_hashes.selector.clone(),
+                    selector_offset: sequence_start,
+                    hashes: hashes,
                 });
             }
 
@@ -1130,14 +1146,20 @@ impl DependencySet {
                 MatchingContext::new_for_visited(MatchingMode::Normal, None,
                                                  VisitedHandlingMode::AllLinksUnvisited);
             let matched_then =
-                matches_selector(&dep.selector, &snapshot_el,
+                matches_selector(&dep.selector,
+                                 dep.selector_offset,
+                                 &dep.hashes,
+                                 &snapshot_el,
                                  &mut then_context,
                                  &mut |_, _| {});
             let mut now_context =
                 MatchingContext::new_for_visited(MatchingMode::Normal, bloom_filter,
                                                  VisitedHandlingMode::AllLinksUnvisited);
             let matches_now =
-                matches_selector(&dep.selector, el,
+                matches_selector(&dep.selector,
+                                 dep.selector_offset,
+                                 &dep.hashes,
+                                 el,
                                  &mut now_context,
                                  &mut |_, _| {});
 
@@ -1162,12 +1184,18 @@ impl DependencySet {
                dep.sensitivities.states.intersects(IN_VISITED_OR_UNVISITED_STATE) {
                 then_context.visited_handling = VisitedHandlingMode::RelevantLinkVisited;
                 let matched_then =
-                    matches_selector(&dep.selector, &snapshot_el,
+                    matches_selector(&dep.selector,
+                                     dep.selector_offset,
+                                     &dep.hashes,
+                                     &snapshot_el,
                                      &mut then_context,
                                      &mut |_, _| {});
                 now_context.visited_handling = VisitedHandlingMode::RelevantLinkVisited;
                 let matches_now =
-                    matches_selector(&dep.selector, el,
+                    matches_selector(&dep.selector,
+                                     dep.selector_offset,
+                                     &dep.hashes,
+                                     el,
                                      &mut now_context,
                                      &mut |_, _| {});
                 if matched_then != matches_now {
diff --git a/components/style/selector_map.rs b/components/style/selector_map.rs
index 846d7972811..a65b664ad38 100644
--- a/components/style/selector_map.rs
+++ b/components/style/selector_map.rs
@@ -12,7 +12,7 @@ use pdqsort::sort_by;
 use rule_tree::CascadeLevel;
 use selector_parser::SelectorImpl;
 use selectors::matching::{matches_selector, MatchingContext, ElementSelectorFlags};
-use selectors::parser::{Component, Combinator, SelectorInner};
+use selectors::parser::{AncestorHashes, Component, Combinator, SelectorAndHashes, SelectorIter};
 use selectors::parser::LocalName as LocalNameSelector;
 use smallvec::VecLike;
 use std::borrow::Borrow;
@@ -22,13 +22,20 @@ use stylist::{ApplicableDeclarationBlock, Rule};
 
 /// A trait to abstract over a given selector map entry.
 pub trait SelectorMapEntry : Sized + Clone {
-    /// Get the selector we should use to index in the selector map.
-    fn selector(&self) -> &SelectorInner<SelectorImpl>;
+    /// Gets the selector we should use to index in the selector map.
+    fn selector(&self) -> SelectorIter<SelectorImpl>;
+
+    /// Gets the ancestor hashes associated with the selector.
+    fn hashes(&self) -> &AncestorHashes;
 }
 
-impl SelectorMapEntry for SelectorInner<SelectorImpl> {
-    fn selector(&self) -> &SelectorInner<SelectorImpl> {
-        self
+impl SelectorMapEntry for SelectorAndHashes<SelectorImpl> {
+    fn selector(&self) -> SelectorIter<SelectorImpl> {
+        self.selector.iter()
+    }
+
+    fn hashes(&self) -> &AncestorHashes {
+        &self.hashes
     }
 }
 
@@ -224,7 +231,9 @@ impl SelectorMap<Rule> {
               F: FnMut(&E, ElementSelectorFlags),
     {
         for rule in rules {
-            if matches_selector(&rule.selector.inner,
+            if matches_selector(&rule.selector,
+                                0,
+                                &rule.hashes,
                                 element,
                                 context,
                                 flags_setter) {
@@ -390,12 +399,12 @@ impl<T: SelectorMapEntry> SelectorMap<T> {
 ///
 /// Effectively, pseudo-elements are ignored, given only state pseudo-classes
 /// may appear before them.
-fn find_from_right<F, R>(selector: &SelectorInner<SelectorImpl>,
+#[inline(always)]
+fn find_from_right<F, R>(mut iter: SelectorIter<SelectorImpl>,
                          mut f: F)
                          -> Option<R>
     where F: FnMut(&Component<SelectorImpl>) -> Option<R>,
 {
-    let mut iter = selector.complex.iter();
     for ss in &mut iter {
         if let Some(r) = f(ss) {
             return Some(r)
@@ -414,9 +423,10 @@ fn find_from_right<F, R>(selector: &SelectorInner<SelectorImpl>,
 }
 
 /// Retrieve the first ID name in the selector, or None otherwise.
-pub fn get_id_name(selector: &SelectorInner<SelectorImpl>)
-               -> Option<Atom> {
-    find_from_right(selector, |ss| {
+#[inline(always)]
+pub fn get_id_name(iter: SelectorIter<SelectorImpl>)
+                   -> Option<Atom> {
+    find_from_right(iter, |ss| {
         // TODO(pradeep): Implement case-sensitivity based on the
         // document type and quirks mode.
         if let Component::ID(ref id) = *ss {
@@ -427,9 +437,10 @@ pub fn get_id_name(selector: &SelectorInner<SelectorImpl>)
 }
 
 /// Retrieve the FIRST class name in the selector, or None otherwise.
-pub fn get_class_name(selector: &SelectorInner<SelectorImpl>)
-                  -> Option<Atom> {
-    find_from_right(selector, |ss| {
+#[inline(always)]
+pub fn get_class_name(iter: SelectorIter<SelectorImpl>)
+                      -> Option<Atom> {
+    find_from_right(iter, |ss| {
         // TODO(pradeep): Implement case-sensitivity based on the
         // document type and quirks mode.
         if let Component::Class(ref class) = *ss {
@@ -440,9 +451,10 @@ pub fn get_class_name(selector: &SelectorInner<SelectorImpl>)
 }
 
 /// Retrieve the name if it is a type selector, or None otherwise.
-pub fn get_local_name(selector: &SelectorInner<SelectorImpl>)
-                  -> Option<LocalNameSelector<SelectorImpl>> {
-    find_from_right(selector, |ss| {
+#[inline(always)]
+pub fn get_local_name(iter: SelectorIter<SelectorImpl>)
+                      -> Option<LocalNameSelector<SelectorImpl>> {
+    find_from_right(iter, |ss| {
         if let Component::LocalName(ref n) = *ss {
             return Some(LocalNameSelector {
                 name: n.name.clone(),
diff --git a/components/style/stylist.rs b/components/style/stylist.rs
index 5df0bf2717b..43b29c0275d 100644
--- a/components/style/stylist.rs
+++ b/components/style/stylist.rs
@@ -28,7 +28,8 @@ use selectors::attr::NamespaceConstraint;
 use selectors::bloom::BloomFilter;
 use selectors::matching::{ElementSelectorFlags, matches_selector, MatchingContext, MatchingMode};
 use selectors::matching::AFFECTED_BY_PRESENTATIONAL_HINTS;
-use selectors::parser::{Combinator, Component, Selector, SelectorInner, SelectorIter, SelectorMethods};
+use selectors::parser::{AncestorHashes, Combinator, Component, Selector, SelectorAndHashes};
+use selectors::parser::{SelectorIter, SelectorMethods};
 use selectors::visitor::SelectorVisitor;
 use shared_lock::{Locked, SharedRwLockReadGuard, StylesheetGuards};
 use sink::Push;
@@ -159,7 +160,7 @@ pub struct Stylist {
     /// on state that is not otherwise visible to the cache, like attributes or
     /// tree-structural state like child index and pseudos).
     #[cfg_attr(feature = "servo", ignore_heap_size_of = "Arc")]
-    selectors_for_cache_revalidation: SelectorMap<SelectorInner<SelectorImpl>>,
+    selectors_for_cache_revalidation: SelectorMap<SelectorAndHashes<SelectorImpl>>,
 
     /// The total number of selectors.
     num_selectors: usize,
@@ -454,10 +455,10 @@ impl Stylist {
                 CssRule::Style(ref locked) => {
                     let style_rule = locked.read_with(&guard);
                     self.num_declarations += style_rule.block.read_with(&guard).len();
-                    for selector in &style_rule.selectors.0 {
+                    for selector_and_hashes in &style_rule.selectors.0 {
                         self.num_selectors += 1;
 
-                        let map = if let Some(pseudo) = selector.pseudo_element() {
+                        let map = if let Some(pseudo) = selector_and_hashes.selector.pseudo_element() {
                             self.pseudos_map
                                 .entry(pseudo.canonical())
                                 .or_insert_with(PerPseudoElementSelectorMap::new)
@@ -466,20 +467,21 @@ impl Stylist {
                             self.element_map.borrow_for_origin(&stylesheet.origin)
                         };
 
-                        map.insert(Rule::new(selector.clone(),
+                        map.insert(Rule::new(selector_and_hashes.selector.clone(),
+                                             selector_and_hashes.hashes.clone(),
                                              locked.clone(),
                                              self.rules_source_order));
 
-                        self.dependencies.note_selector(selector);
-                        if needs_revalidation(selector) {
-                            self.selectors_for_cache_revalidation.insert(selector.inner.clone());
+                        self.dependencies.note_selector(selector_and_hashes);
+                        if needs_revalidation(&selector_and_hashes.selector) {
+                            self.selectors_for_cache_revalidation.insert(selector_and_hashes.clone());
                         }
-                        selector.visit(&mut AttributeAndStateDependencyVisitor {
+                        selector_and_hashes.selector.visit(&mut AttributeAndStateDependencyVisitor {
                             attribute_dependencies: &mut self.attribute_dependencies,
                             style_attribute_dependency: &mut self.style_attribute_dependency,
                             state_dependencies: &mut self.state_dependencies,
                         });
-                        selector.visit(&mut MappedIdVisitor {
+                        selector_and_hashes.selector.visit(&mut MappedIdVisitor {
                             mapped_ids: &mut self.mapped_ids,
                         });
                     }
@@ -1130,8 +1132,10 @@ impl Stylist {
         // the lookups, which means that the bitvecs are comparable. We verify
         // this in the caller by asserting that the bitvecs are same-length.
         let mut results = BitVec::new();
-        self.selectors_for_cache_revalidation.lookup(*element, &mut |selector| {
-            results.push(matches_selector(selector,
+        self.selectors_for_cache_revalidation.lookup(*element, &mut |selector_and_hashes| {
+            results.push(matches_selector(&selector_and_hashes.selector,
+                                          0,
+                                          &selector_and_hashes.hashes,
                                           element,
                                           &mut matching_context,
                                           flags_setter));
@@ -1410,6 +1414,9 @@ pub struct Rule {
     /// can ruin performance when there are a lot of rules.
     #[cfg_attr(feature = "servo", ignore_heap_size_of = "Arc")]
     pub selector: Selector<SelectorImpl>,
+    /// The ancestor hashes associated with the selector.
+    #[cfg_attr(feature = "servo", ignore_heap_size_of = "No heap data")]
+    pub hashes: AncestorHashes,
     /// The actual style rule.
     #[cfg_attr(feature = "servo", ignore_heap_size_of = "Arc")]
     pub style_rule: Arc<Locked<StyleRule>>,
@@ -1418,8 +1425,12 @@ pub struct Rule {
 }
 
 impl SelectorMapEntry for Rule {
-    fn selector(&self) -> &SelectorInner<SelectorImpl> {
-        &self.selector.inner
+    fn selector(&self) -> SelectorIter<SelectorImpl> {
+        self.selector.iter()
+    }
+
+    fn hashes(&self) -> &AncestorHashes {
+        &self.hashes
     }
 }
 
@@ -1444,12 +1455,14 @@ impl Rule {
 
     /// Creates a new Rule.
     pub fn new(selector: Selector<SelectorImpl>,
+               hashes: AncestorHashes,
                style_rule: Arc<Locked<StyleRule>>,
                source_order: usize)
                -> Self
     {
         Rule {
             selector: selector,
+            hashes: hashes,
             style_rule: style_rule,
             source_order: source_order,
         }