style: Hash less stuff in the bloom filter, using the precomputed hashes we have.

9 files changed, 127 insertions, 63 deletions

diff --git a/components/selectors/Cargo.toml b/components/selectors/Cargo.toml
index f99cccf2683..a7145130342 100644
--- a/components/selectors/Cargo.toml
+++ b/components/selectors/Cargo.toml
@@ -20,3 +20,4 @@ bitflags = "0.7"
 matches = "0.1"
 cssparser = "0.12.1"
 fnv = "1.0"
+precomputed-hash = "0.1"
diff --git a/components/selectors/lib.rs b/components/selectors/lib.rs
index 247902074b9..84bfecca058 100644
--- a/components/selectors/lib.rs
+++ b/components/selectors/lib.rs
@@ -6,6 +6,7 @@
 #[macro_use] extern crate cssparser;
 #[macro_use] extern crate matches;
 extern crate fnv;
+extern crate precomputed_hash;
 
 pub mod bloom;
 pub mod matching;
diff --git a/components/selectors/matching.rs b/components/selectors/matching.rs
index 21f070df536..628ec971f5c 100644
--- a/components/selectors/matching.rs
+++ b/components/selectors/matching.rs
@@ -4,6 +4,7 @@
 use bloom::BloomFilter;
 use parser::{CaseSensitivity, Combinator, ComplexSelector, LocalName};
 use parser::{SimpleSelector, Selector, SelectorImpl};
+use precomputed_hash::PrecomputedHash;
 use std::borrow::Borrow;
 use tree::Element;
 
@@ -135,23 +136,23 @@ fn may_match<E>(mut selector: &ComplexSelector<E::Impl>,
         for ss in selector.compound_selector.iter() {
             match *ss {
                 SimpleSelector::LocalName(LocalName { ref name, ref lower_name })  => {
-                    if !bf.might_contain(name) &&
-                       !bf.might_contain(lower_name) {
+                    if !bf.might_contain_hash(name.precomputed_hash()) &&
+                       !bf.might_contain_hash(lower_name.precomputed_hash()) {
                        return false
                     }
                 },
                 SimpleSelector::Namespace(ref namespace) => {
-                    if !bf.might_contain(&namespace.url) {
+                    if !bf.might_contain_hash(namespace.url.precomputed_hash()) {
                         return false
                     }
                 },
                 SimpleSelector::ID(ref id) => {
-                    if !bf.might_contain(id) {
+                    if !bf.might_contain_hash(id.precomputed_hash()) {
                         return false
                     }
                 },
                 SimpleSelector::Class(ref class) => {
-                    if !bf.might_contain(class) {
+                    if !bf.might_contain_hash(class.precomputed_hash()) {
                         return false
                     }
                 },
diff --git a/components/selectors/parser.rs b/components/selectors/parser.rs
index 3bbbc681c54..d3987900301 100644
--- a/components/selectors/parser.rs
+++ b/components/selectors/parser.rs
@@ -3,6 +3,7 @@
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 use cssparser::{Token, Parser as CssParser, parse_nth, ToCss, serialize_identifier, CssStringWriter};
+use precomputed_hash::PrecomputedHash;
 use std::ascii::AsciiExt;
 use std::borrow::{Borrow, Cow};
 use std::cmp;
@@ -39,10 +40,10 @@ macro_rules! with_all_bounds {
         /// of pseudo-classes/elements
         pub trait SelectorImpl: Sized {
             type AttrValue: $($InSelector)*;
-            type Identifier: $($InSelector)*;
-            type ClassName: $($InSelector)*;
-            type LocalName: $($InSelector)* + Borrow<Self::BorrowedLocalName>;
-            type NamespaceUrl: $($CommonBounds)* + Default + Borrow<Self::BorrowedNamespaceUrl>;
+            type Identifier: $($InSelector)* + PrecomputedHash;
+            type ClassName: $($InSelector)* + PrecomputedHash;
+            type LocalName: $($InSelector)* + Borrow<Self::BorrowedLocalName> + PrecomputedHash;
+            type NamespaceUrl: $($CommonBounds)* + Default + Borrow<Self::BorrowedNamespaceUrl> + PrecomputedHash;
             type NamespacePrefix: $($InSelector)* + Default;
             type BorrowedNamespaceUrl: ?Sized + Eq;
             type BorrowedLocalName: ?Sized + Eq + Hash;
@@ -1184,24 +1185,49 @@ pub mod tests {
 
     #[derive(Default)]
     pub struct DummyParser {
-        default_ns: Option<String>,
-        ns_prefixes: HashMap<String, String>,
+        default_ns: Option<DummyAtom>,
+        ns_prefixes: HashMap<DummyAtom, DummyAtom>,
     }
 
     impl SelectorImpl for DummySelectorImpl {
-        type AttrValue = String;
-        type Identifier = String;
-        type ClassName = String;
-        type LocalName = String;
-        type NamespaceUrl = String;
-        type NamespacePrefix = String;
-        type BorrowedLocalName = str;
-        type BorrowedNamespaceUrl = str;
+        type AttrValue = DummyAtom;
+        type Identifier = DummyAtom;
+        type ClassName = DummyAtom;
+        type LocalName = DummyAtom;
+        type NamespaceUrl = DummyAtom;
+        type NamespacePrefix = DummyAtom;
+        type BorrowedLocalName = DummyAtom;
+        type BorrowedNamespaceUrl = DummyAtom;
         type NonTSPseudoClass = PseudoClass;
         type PseudoElement = PseudoElement;
     }
 
-    type ShutUpTidy = String;
+    #[derive(Default, Debug, Hash, Clone, PartialEq, Eq)]
+    pub struct DummyAtom(String);
+
+    impl fmt::Display for DummyAtom {
+        fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
+            <String as fmt::Display>::fmt(&self.0, fmt)
+        }
+    }
+
+    impl From<String> for DummyAtom {
+        fn from(string: String) -> Self {
+            DummyAtom(string)
+        }
+    }
+
+    impl<'a> From<&'a str> for DummyAtom {
+        fn from(string: &'a str) -> Self {
+            DummyAtom(string.into())
+        }
+    }
+
+    impl PrecomputedHash for DummyAtom {
+        fn precomputed_hash(&self) -> u32 {
+            return 0
+        }
+    }
 
     impl Parser for DummyParser {
         type Impl = DummySelectorImpl;
@@ -1232,11 +1258,11 @@ pub mod tests {
             }
         }
 
-        fn default_namespace(&self) -> Option<String> {
+        fn default_namespace(&self) -> Option<DummyAtom> {
             self.default_ns.clone()
         }
 
-        fn namespace_for_prefix(&self, prefix: &ShutUpTidy) -> Option<String> {
+        fn namespace_for_prefix(&self, prefix: &DummyAtom) -> Option<DummyAtom> {
             self.ns_prefixes.get(prefix).cloned()
         }
     }
@@ -1276,8 +1302,8 @@ pub mod tests {
         assert_eq!(parse("EeÉ"), Ok(SelectorList(vec!(Selector {
             complex_selector: Arc::new(ComplexSelector {
                 compound_selector: vec!(SimpleSelector::LocalName(LocalName {
-                    name: String::from("EeÉ"),
-                    lower_name: String::from("eeÉ") })),
+                    name: DummyAtom::from("EeÉ"),
+                    lower_name: DummyAtom::from("eeÉ") })),
                 next: None,
             }),
             pseudo_element: None,
@@ -1286,7 +1312,7 @@ pub mod tests {
         assert_eq!(parse(".foo:lang(en-US)"), Ok(SelectorList(vec!(Selector {
             complex_selector: Arc::new(ComplexSelector {
                 compound_selector: vec![
-                    SimpleSelector::Class(String::from("foo")),
+                    SimpleSelector::Class(DummyAtom::from("foo")),
                     SimpleSelector::NonTSPseudoClass(PseudoClass::Lang("en-US".to_owned()))
                 ],
                 next: None,
@@ -1296,7 +1322,7 @@ pub mod tests {
         }))));
         assert_eq!(parse("#bar"), Ok(SelectorList(vec!(Selector {
             complex_selector: Arc::new(ComplexSelector {
-                compound_selector: vec!(SimpleSelector::ID(String::from("bar"))),
+                compound_selector: vec!(SimpleSelector::ID(DummyAtom::from("bar"))),
                 next: None,
             }),
             pseudo_element: None,
@@ -1305,10 +1331,10 @@ pub mod tests {
         assert_eq!(parse("e.foo#bar"), Ok(SelectorList(vec!(Selector {
             complex_selector: Arc::new(ComplexSelector {
                 compound_selector: vec!(SimpleSelector::LocalName(LocalName {
-                                            name: String::from("e"),
-                                            lower_name: String::from("e") }),
-                                       SimpleSelector::Class(String::from("foo")),
-                                       SimpleSelector::ID(String::from("bar"))),
+                                            name: DummyAtom::from("e"),
+                                            lower_name: DummyAtom::from("e") }),
+                                       SimpleSelector::Class(DummyAtom::from("foo")),
+                                       SimpleSelector::ID(DummyAtom::from("bar"))),
                 next: None,
             }),
             pseudo_element: None,
@@ -1316,12 +1342,12 @@ pub mod tests {
         }))));
         assert_eq!(parse("e.foo #bar"), Ok(SelectorList(vec!(Selector {
             complex_selector: Arc::new(ComplexSelector {
-                compound_selector: vec!(SimpleSelector::ID(String::from("bar"))),
+                compound_selector: vec!(SimpleSelector::ID(DummyAtom::from("bar"))),
                 next: Some((Arc::new(ComplexSelector {
                     compound_selector: vec!(SimpleSelector::LocalName(LocalName {
-                                                name: String::from("e"),
-                                                lower_name: String::from("e") }),
-                                           SimpleSelector::Class(String::from("foo"))),
+                                                name: DummyAtom::from("e"),
+                                                lower_name: DummyAtom::from("e") }),
+                                           SimpleSelector::Class(DummyAtom::from("foo"))),
                     next: None,
                 }), Combinator::Descendant)),
             }),
@@ -1334,8 +1360,8 @@ pub mod tests {
         assert_eq!(parse_ns("[Foo]", &parser), Ok(SelectorList(vec!(Selector {
             complex_selector: Arc::new(ComplexSelector {
                 compound_selector: vec!(SimpleSelector::AttrExists(AttrSelector {
-                    name: String::from("Foo"),
-                    lower_name: String::from("foo"),
+                    name: DummyAtom::from("Foo"),
+                    lower_name: DummyAtom::from("foo"),
                     namespace: NamespaceConstraint::Specific(Namespace {
                         prefix: None,
                         url: "".into(),
@@ -1347,17 +1373,17 @@ pub mod tests {
             specificity: specificity(0, 1, 0),
         }))));
         assert_eq!(parse_ns("svg|circle", &parser), Err(()));
-        parser.ns_prefixes.insert("svg".into(), SVG.into());
+        parser.ns_prefixes.insert(DummyAtom("svg".into()), DummyAtom(SVG.into()));
         assert_eq!(parse_ns("svg|circle", &parser), Ok(SelectorList(vec![Selector {
             complex_selector: Arc::new(ComplexSelector {
                 compound_selector: vec![
                     SimpleSelector::Namespace(Namespace {
-                        prefix: Some("svg".into()),
+                        prefix: Some(DummyAtom("svg".into())),
                         url: SVG.into(),
                     }),
                     SimpleSelector::LocalName(LocalName {
-                        name: String::from("circle"),
-                        lower_name: String::from("circle")
+                        name: DummyAtom::from("circle"),
+                        lower_name: DummyAtom::from("circle"),
                     })
                 ],
                 next: None,
@@ -1378,8 +1404,8 @@ pub mod tests {
                         url: MATHML.into(),
                     }),
                     SimpleSelector::AttrExists(AttrSelector {
-                        name: String::from("Foo"),
-                        lower_name: String::from("foo"),
+                        name: DummyAtom::from("Foo"),
+                        lower_name: DummyAtom::from("foo"),
                         namespace: NamespaceConstraint::Specific(Namespace {
                             prefix: None,
                             url: "".into(),
@@ -1400,8 +1426,8 @@ pub mod tests {
                         url: MATHML.into(),
                     }),
                     SimpleSelector::LocalName(LocalName {
-                        name: String::from("e"),
-                        lower_name: String::from("e") }),
+                        name: DummyAtom::from("e"),
+                        lower_name: DummyAtom::from("e") }),
                 ),
                 next: None,
             }),
@@ -1412,13 +1438,13 @@ pub mod tests {
             complex_selector: Arc::new(ComplexSelector {
                 compound_selector: vec![
                     SimpleSelector::AttrDashMatch(AttrSelector {
-                        name: String::from("attr"),
-                        lower_name: String::from("attr"),
+                        name: DummyAtom::from("attr"),
+                        lower_name: DummyAtom::from("attr"),
                         namespace: NamespaceConstraint::Specific(Namespace {
                             prefix: None,
                             url: "".into(),
                         }),
-                    }, "foo".to_owned())
+                    }, DummyAtom::from("foo"))
                 ],
                 next: None,
             }),
@@ -1441,8 +1467,8 @@ pub mod tests {
                 compound_selector: vec!(),
                 next: Some((Arc::new(ComplexSelector {
                     compound_selector: vec!(SimpleSelector::LocalName(LocalName {
-                        name: String::from("div"),
-                        lower_name: String::from("div") })),
+                        name: DummyAtom::from("div"),
+                        lower_name: DummyAtom::from("div") })),
                     next: None,
                 }), Combinator::Descendant)),
             }),
@@ -1452,11 +1478,11 @@ pub mod tests {
         assert_eq!(parse("#d1 > .ok"), Ok(SelectorList(vec![Selector {
             complex_selector: Arc::new(ComplexSelector {
                 compound_selector: vec![
-                    SimpleSelector::Class(String::from("ok")),
+                    SimpleSelector::Class(DummyAtom::from("ok")),
                 ],
                 next: Some((Arc::new(ComplexSelector {
                     compound_selector: vec![
-                        SimpleSelector::ID(String::from("d1")),
+                        SimpleSelector::ID(DummyAtom::from("d1")),
                     ],
                     next: None,
                 }), Combinator::Child)),
@@ -1469,13 +1495,13 @@ pub mod tests {
                 compound_selector: vec!(SimpleSelector::Negation(
                     vec!(
                         Arc::new(ComplexSelector {
-                            compound_selector: vec!(SimpleSelector::Class(String::from("babybel"))),
+                            compound_selector: vec!(SimpleSelector::Class(DummyAtom::from("babybel"))),
                             next: None
                         }),
                         Arc::new(ComplexSelector {
                             compound_selector: vec!(
-                                SimpleSelector::ID(String::from("provel")),
-                                SimpleSelector::Class(String::from("old")),
+                                SimpleSelector::ID(DummyAtom::from("provel")),
+                                SimpleSelector::Class(DummyAtom::from("old")),
                             ),
                             next: None
                         }),
diff --git a/components/style/Cargo.toml b/components/style/Cargo.toml
index ae5291fdc7a..10ed72aaea3 100644
--- a/components/style/Cargo.toml
+++ b/components/style/Cargo.toml
@@ -44,6 +44,7 @@ num-traits = "0.1.32"
 ordered-float = "0.4"
 parking_lot = "0.3.3"
 pdqsort = "0.1.0"
+precomputed-hash = "0.1"
 rayon = "0.6"
 selectors = { path = "../selectors" }
 serde = {version = "0.9", optional = true}
diff --git a/components/style/gecko_string_cache/mod.rs b/components/style/gecko_string_cache/mod.rs
index b6659c6ab91..b10fd58174a 100644
--- a/components/style/gecko_string_cache/mod.rs
+++ b/components/style/gecko_string_cache/mod.rs
@@ -10,6 +10,7 @@ use gecko_bindings::bindings::Gecko_AddRefAtom;
 use gecko_bindings::bindings::Gecko_Atomize;
 use gecko_bindings::bindings::Gecko_ReleaseAtom;
 use gecko_bindings::structs::nsIAtom;
+use precomputed_hash::PrecomputedHash;
 use std::borrow::{Cow, Borrow};
 use std::char::{self, DecodeUtf16};
 use std::fmt::{self, Write};
@@ -56,6 +57,13 @@ impl Deref for Atom {
     }
 }
 
+impl PrecomputedHash for Atom {
+    #[inline]
+    fn precomputed_hash(&self) -> u32 {
+        self.get_hash()
+    }
+}
+
 impl Borrow<WeakAtom> for Atom {
     #[inline]
     fn borrow(&self) -> &WeakAtom {
diff --git a/components/style/gecko_string_cache/namespace.rs b/components/style/gecko_string_cache/namespace.rs
index 117f1923151..9368c16286f 100644
--- a/components/style/gecko_string_cache/namespace.rs
+++ b/components/style/gecko_string_cache/namespace.rs
@@ -5,6 +5,7 @@
 //! A type to represent a namespace.
 
 use gecko_bindings::structs::nsIAtom;
+use precomputed_hash::PrecomputedHash;
 use std::borrow::{Borrow, Cow};
 use std::fmt;
 use std::ops::Deref;
@@ -19,10 +20,27 @@ macro_rules! ns {
 #[derive(Debug, PartialEq, Eq, Clone, Default, Hash)]
 pub struct Namespace(pub Atom);
 
+impl PrecomputedHash for Namespace {
+    #[inline]
+    fn precomputed_hash(&self) -> u32 {
+        self.0.precomputed_hash()
+    }
+}
+
 /// A Gecko WeakNamespace is a wrapped WeakAtom.
 #[derive(Hash)]
 pub struct WeakNamespace(WeakAtom);
 
+impl Deref for WeakNamespace {
+    type Target = WeakAtom;
+
+    #[inline]
+    fn deref(&self) -> &WeakAtom {
+        &self.0
+    }
+}
+
+
 impl Deref for Namespace {
     type Target = WeakNamespace;
 
diff --git a/components/style/lib.rs b/components/style/lib.rs
index d36001b2f3d..171b8081fc2 100644
--- a/components/style/lib.rs
+++ b/components/style/lib.rs
@@ -66,6 +66,7 @@ extern crate num_traits;
 extern crate ordered_float;
 extern crate parking_lot;
 extern crate pdqsort;
+#[cfg(feature = "gecko")] extern crate precomputed_hash;
 extern crate rayon;
 extern crate selectors;
 #[cfg(feature = "servo")] #[macro_use] extern crate serde_derive;
diff --git a/components/style/matching.rs b/components/style/matching.rs
index e6c9de52025..e38bfcb6df0 100644
--- a/components/style/matching.rs
+++ b/components/style/matching.rs
@@ -1175,23 +1175,30 @@ pub trait MatchMethods : TElement {
     /// Therefore, each node must have its matching selectors inserted _after_
     /// its own selector matching and _before_ its children start.
     fn insert_into_bloom_filter(&self, bf: &mut BloomFilter) {
-        bf.insert(&*self.get_local_name());
-        bf.insert(&*self.get_namespace());
-        self.get_id().map(|id| bf.insert(&id));
-
+        bf.insert_hash(self.get_local_name().get_hash());
+        bf.insert_hash(self.get_namespace().get_hash());
+        if let Some(id) = self.get_id() {
+            bf.insert_hash(id.get_hash());
+        }
         // TODO: case-sensitivity depends on the document type and quirks mode
-        self.each_class(|class| bf.insert(class));
+        self.each_class(|class| {
+            bf.insert_hash(class.get_hash())
+        });
     }
 
     /// After all the children are done css selector matching, this must be
     /// called to reset the bloom filter after an `insert`.
     fn remove_from_bloom_filter(&self, bf: &mut BloomFilter) {
-        bf.remove(&*self.get_local_name());
-        bf.remove(&*self.get_namespace());
-        self.get_id().map(|id| bf.remove(&id));
+        bf.remove_hash(self.get_local_name().get_hash());
+        bf.remove_hash(self.get_namespace().get_hash());
+        if let Some(id) = self.get_id() {
+            bf.remove_hash(id.get_hash());
+        }
 
         // TODO: case-sensitivity depends on the document type and quirks mode
-        self.each_class(|class| bf.remove(class));
+        self.each_class(|class| {
+            bf.remove_hash(class.get_hash())
+        });
     }
 
     /// Given the old and new style of this element, and whether it's a