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 -->

6 files changed, 380 insertions, 782 deletions

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);