servo: Merge #18434 - Bug 1395064 - stylo: Add uses of fallible Vec, SmallVec and HashMap f… (from julian-seward1:master); r=bholley
authorEmilio Cobos Álvarez <emilio@crisal.io>
Sun, 10 Sep 2017 12:30:39 -0500
changeset 429462 903b743e407ebb7cd5ffbcebd5268588d5b31b02
parent 429461 ecd75d0e0a2f5215aa4c3a08502e4434192b4ab3
child 429463 8b7a5231e2a46ee425ad637caba96960de6e6a72
push id7761
push userjlund@mozilla.com
push dateFri, 15 Sep 2017 00:19:52 +0000
treeherdermozilla-beta@c38455951db4 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersbholley
bugs1395064
milestone57.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
servo: Merge #18434 - Bug 1395064 - stylo: Add uses of fallible Vec, SmallVec and HashMap f… (from julian-seward1:master); r=bholley …acilities. r=emilio@crisal.io. <!-- Please describe your changes on the following line: --> --- <!-- Thank you for contributing to Servo! Please replace each `[ ]` by `[X]` when the step is complete, and replace `__` with appropriate data: --> - [ ] `./mach build -d` does not report any errors - [ ] `./mach test-tidy` does not report any errors - [ ] These changes fix #__ (github issue number if applicable). <!-- Either: --> - [ ] There are tests for these changes OR - [ ] These changes do not require tests because _____ <!-- Also, please make sure that "Allow edits from maintainers" checkbox is checked, so that we can help you if you get stuck somewhere along the way.--> <!-- Pull requests that do not address these steps are welcome, but they will require additional verification as part of the review process. --> Source-Repo: https://github.com/servo/servo Source-Revision: be804a8155b0a942324f564df569233d13c97dcd
servo/Cargo.lock
servo/components/fallible/Cargo.toml
servo/components/fallible/lib.rs
servo/components/hashglobe/src/lib.rs
servo/components/style/Cargo.toml
servo/components/style/invalidation/element/invalidation_map.rs
servo/components/style/lib.rs
servo/components/style/selector_map.rs
servo/components/style/stylesheets/stylesheet.rs
servo/components/style/stylist.rs
servo/tests/unit/style/stylist.rs
--- a/servo/Cargo.lock
+++ b/servo/Cargo.lock
@@ -971,16 +971,17 @@ dependencies = [
 name = "extra-default"
 version = "0.2.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 
 [[package]]
 name = "fallible"
 version = "0.0.1"
 dependencies = [
+ "hashglobe 0.1.0",
  "smallvec 0.4.3 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
 [[package]]
 name = "flate2"
 version = "0.2.19"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 dependencies = [
--- a/servo/components/fallible/Cargo.toml
+++ b/servo/components/fallible/Cargo.toml
@@ -6,8 +6,20 @@ license = "MPL-2.0"
 publish = false
 
 [lib]
 name = "fallible"
 path = "lib.rs"
 
 [dependencies]
 smallvec = "0.4"
+hashglobe = { path = "../hashglobe" }
+
+# This crate effectively does nothing except if the `known_system_malloc`
+# feature is specified.
+#
+# In that case, we actually call the system malloc functions to reserve space,
+# otherwise we just let rust do its thing (aborting on OOM).
+#
+# This is effectively a stop-gap measure until we can do this properly in
+# stable rust.
+[features]
+known_system_malloc = []
--- a/servo/components/fallible/lib.rs
+++ b/servo/components/fallible/lib.rs
@@ -1,120 +1,150 @@
 /* This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
+extern crate hashglobe;
 extern crate smallvec;
 
+use hashglobe::FailedAllocationError;
 use smallvec::Array;
 use smallvec::SmallVec;
-use std::mem;
-use std::ptr::copy_nonoverlapping;
 use std::vec::Vec;
 
+#[cfg(feature = "known_system_malloc")]
 extern "C" {
     fn realloc(ptr: *mut u8, bytes: usize) -> *mut u8;
     fn malloc(bytes: usize) -> *mut u8;
 }
 
 pub trait FallibleVec<T> {
     /// Append |val| to the end of |vec|.  Returns Ok(()) on success,
-    /// Err(()) if it fails, which can only be due to lack of memory.
-    fn try_push(&mut self, value: T) -> Result<(), ()>;
+    /// Err(reason) if it fails, with |reason| describing the failure.
+    fn try_push(&mut self, value: T) -> Result<(), FailedAllocationError>;
 }
 
 
 /////////////////////////////////////////////////////////////////
 // Vec
 
 impl<T> FallibleVec<T> for Vec<T> {
     #[inline]
-    fn try_push(&mut self, val: T) -> Result<(), ()> {
-        if self.capacity() == self.len() {
-            try_double_vec(self)?;
-            debug_assert!(self.capacity() > self.len());
+    fn try_push(&mut self, val: T) -> Result<(), FailedAllocationError> {
+        #[cfg(feature = "known_system_malloc")]
+        {
+            if self.capacity() == self.len() {
+                try_double_vec(self)?;
+                debug_assert!(self.capacity() > self.len());
+            }
         }
         self.push(val);
         Ok(())
     }
 }
 
 // Double the capacity of |vec|, or fail to do so due to lack of memory.
-// Returns Ok(()) on success, Err(()) on failure.
+// Returns Ok(()) on success, Err(..) on failure.
+#[cfg(feature = "known_system_malloc")]
 #[inline(never)]
 #[cold]
-fn try_double_vec<T>(vec: &mut Vec<T>) -> Result<(), ()> {
+fn try_double_vec<T>(vec: &mut Vec<T>) -> Result<(), FailedAllocationError> {
+    use std::mem;
+
     let old_ptr = vec.as_mut_ptr();
     let old_len = vec.len();
 
     let old_cap: usize = vec.capacity();
-    let new_cap: usize =
-        if old_cap == 0 { 4 } else { old_cap.checked_mul(2).ok_or(()) ? };
+    let new_cap: usize = if old_cap == 0 {
+        4
+    } else {
+        old_cap.checked_mul(2).ok_or(FailedAllocationError::new(
+            "capacity overflow for Vec",
+        ))?
+    };
 
-    let new_size_bytes =
-        new_cap.checked_mul(mem::size_of::<T>()).ok_or(()) ? ;
+    let new_size_bytes = new_cap.checked_mul(mem::size_of::<T>()).ok_or(
+        FailedAllocationError::new("capacity overflow for Vec"),
+    )?;
 
     let new_ptr = unsafe {
         if old_cap == 0 {
             malloc(new_size_bytes)
         } else {
             realloc(old_ptr as *mut u8, new_size_bytes)
         }
     };
 
     if new_ptr.is_null() {
-        return Err(());
+        return Err(FailedAllocationError::new(
+            "out of memory when allocating Vec",
+        ));
     }
 
     let new_vec = unsafe {
         Vec::from_raw_parts(new_ptr as *mut T, old_len, new_cap)
     };
 
     mem::forget(mem::replace(vec, new_vec));
     Ok(())
 }
 
 
 /////////////////////////////////////////////////////////////////
 // SmallVec
 
 impl<T: Array> FallibleVec<T::Item> for SmallVec<T> {
     #[inline]
-    fn try_push(&mut self, val: T::Item) -> Result<(), ()> {
-        if self.capacity() == self.len() {
-            try_double_small_vec(self)?;
-            debug_assert!(self.capacity() > self.len());
+    fn try_push(&mut self, val: T::Item) -> Result<(), FailedAllocationError> {
+        #[cfg(feature = "known_system_malloc")]
+        {
+            if self.capacity() == self.len() {
+                try_double_small_vec(self)?;
+                debug_assert!(self.capacity() > self.len());
+            }
         }
         self.push(val);
         Ok(())
     }
 }
 
-// Double the capacity of |vec|, or fail to do so due to lack of memory.
-// Returns Ok(()) on success, Err(()) on failure.
+// Double the capacity of |svec|, or fail to do so due to lack of memory.
+// Returns Ok(()) on success, Err(..) on failure.
+#[cfg(feature = "known_system_malloc")]
 #[inline(never)]
 #[cold]
-fn try_double_small_vec<T>(svec: &mut SmallVec<T>) -> Result<(), ()>
+fn try_double_small_vec<T>(svec: &mut SmallVec<T>)
+-> Result<(), FailedAllocationError>
 where
     T: Array,
 {
+    use std::mem;
+    use std::ptr::copy_nonoverlapping;
+
     let old_ptr = svec.as_mut_ptr();
     let old_len = svec.len();
 
     let old_cap: usize = svec.capacity();
-    let new_cap: usize =
-        if old_cap == 0 { 4 } else { old_cap.checked_mul(2).ok_or(()) ? };
+    let new_cap: usize = if old_cap == 0 {
+        4
+    } else {
+        old_cap.checked_mul(2).ok_or(FailedAllocationError::new(
+            "capacity overflow for SmallVec",
+        ))?
+    };
 
     // This surely shouldn't fail, if |old_cap| was previously accepted as a
     // valid value.  But err on the side of caution.
-    let old_size_bytes =
-        old_cap.checked_mul(mem::size_of::<T>()).ok_or(()) ? ;
+    let old_size_bytes = old_cap.checked_mul(mem::size_of::<T>()).ok_or(
+        FailedAllocationError::new("capacity overflow for SmallVec"),
+    )?;
 
-    let new_size_bytes =
-        new_cap.checked_mul(mem::size_of::<T>()).ok_or(()) ? ;
+    let new_size_bytes = new_cap.checked_mul(mem::size_of::<T>()).ok_or(
+        FailedAllocationError::new("capacity overflow for SmallVec"),
+    )?;
 
     let new_ptr;
     if svec.spilled() {
         // There's an old block to free, and, presumably, old contents to
         // copy.  realloc takes care of both aspects.
         unsafe {
             new_ptr = realloc(old_ptr as *mut u8, new_size_bytes);
         }
@@ -125,17 +155,19 @@ where
             if !new_ptr.is_null() && old_size_bytes > 0 {
                 copy_nonoverlapping(old_ptr as *const u8,
                                     new_ptr as *mut u8, old_size_bytes);
             }
         }
     }
 
     if new_ptr.is_null() {
-        return Err(());
+        return Err(FailedAllocationError::new(
+            "out of memory when allocating SmallVec",
+        ));
     }
 
     let new_vec = unsafe {
         Vec::from_raw_parts(new_ptr as *mut T::Item, old_len, new_cap)
     };
 
     let new_svec = SmallVec::from_vec(new_vec);
     mem::forget(mem::replace(svec, new_svec));
--- a/servo/components/hashglobe/src/lib.rs
+++ b/servo/components/hashglobe/src/lib.rs
@@ -28,16 +28,23 @@ trait Recover<Q: ?Sized> {
     fn replace(&mut self, key: Self::Key) -> Option<Self::Key>;
 }
 
 #[derive(Debug)]
 pub struct FailedAllocationError {
     reason: &'static str,
 }
 
+impl FailedAllocationError {
+    #[inline]
+    pub fn new(reason: &'static str) -> Self {
+        Self { reason }
+    }
+}
+
 impl error::Error for FailedAllocationError {
     fn description(&self) -> &str {
         self.reason
     }
 }
 
 impl fmt::Display for FailedAllocationError {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
--- a/servo/components/style/Cargo.toml
+++ b/servo/components/style/Cargo.toml
@@ -11,17 +11,17 @@ build = "build.rs"
 links = "for some reason the links key is required to pass data around between build scripts"
 
 [lib]
 name = "style"
 path = "lib.rs"
 doctest = false
 
 [features]
-gecko = ["nsstring_vendor", "num_cpus", "style_traits/gecko"]
+gecko = ["nsstring_vendor", "num_cpus", "style_traits/gecko", "fallible/known_system_malloc"]
 use_bindgen = ["bindgen", "regex", "toml"]
 servo = ["serde", "heapsize", "heapsize_derive",
          "style_traits/servo", "servo_atoms", "servo_config", "html5ever",
          "cssparser/heapsize", "cssparser/serde", "encoding", "smallvec/heapsizeof",
 
          # FIXME: Uncomment when https://github.com/servo/servo/pull/16953 has landed:
          #"arrayvec/use_union"
 
--- a/servo/components/style/invalidation/element/invalidation_map.rs
+++ b/servo/components/style/invalidation/element/invalidation_map.rs
@@ -2,16 +2,18 @@
  * 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/. */
 
 //! Code for invalidations due to state or attribute changes.
 
 use {Atom, LocalName, Namespace};
 use context::QuirksMode;
 use element_state::ElementState;
+use fallible::FallibleVec;
+use hashglobe::FailedAllocationError;
 use selector_map::{MaybeCaseInsensitiveHashMap, SelectorMap, SelectorMapEntry};
 use selector_parser::SelectorImpl;
 use selectors::attr::NamespaceConstraint;
 use selectors::parser::{Combinator, Component};
 use selectors::parser::{Selector, SelectorIter, SelectorMethods};
 use selectors::visitor::SelectorVisitor;
 use smallvec::SmallVec;
 #[cfg(feature = "gecko")]
@@ -179,40 +181,42 @@ impl InvalidationMap {
         self.id_to_selector.iter().fold(0, |accum, (_, ref v)| {
             accum + v.len()
         }) +
         self.class_to_selector.iter().fold(0, |accum, (_, ref v)| {
             accum + v.len()
         })
     }
 
-    /// Adds a selector to this `InvalidationMap`.
+    /// Adds a selector to this `InvalidationMap`.  Returns Err(..) to
+    /// signify OOM.
     pub fn note_selector(
         &mut self,
         selector: &Selector<SelectorImpl>,
-        quirks_mode: QuirksMode)
-    {
+        quirks_mode: QuirksMode
+    ) -> Result<(), FailedAllocationError> {
         self.collect_invalidations_for(selector, quirks_mode)
     }
 
     /// Clears this map, leaving it empty.
     pub fn clear(&mut self) {
         self.class_to_selector.clear();
         self.id_to_selector.clear();
         self.state_affecting_selectors.clear();
         self.other_attribute_affecting_selectors.clear();
         self.has_id_attribute_selectors = false;
         self.has_class_attribute_selectors = false;
     }
 
+    // Returns Err(..) to signify OOM.
     fn collect_invalidations_for(
         &mut self,
         selector: &Selector<SelectorImpl>,
-        quirks_mode: QuirksMode)
-    {
+        quirks_mode: QuirksMode
+    ) -> Result<(), FailedAllocationError> {
         debug!("InvalidationMap::collect_invalidations_for({:?})", selector);
 
         let mut iter = selector.iter();
         let mut combinator;
         let mut index = 0;
 
         loop {
             let sequence_start = index;
@@ -241,58 +245,60 @@ impl InvalidationMap {
 
             self.has_id_attribute_selectors |= compound_visitor.has_id_attribute_selectors;
             self.has_class_attribute_selectors |= compound_visitor.has_class_attribute_selectors;
 
             for class in compound_visitor.classes {
                 self.class_to_selector
                     .entry(class, quirks_mode)
                     .or_insert_with(SmallVec::new)
-                    .push(Dependency {
+                    .try_push(Dependency {
                         selector: selector.clone(),
                         selector_offset: sequence_start,
-                    })
+                    })?;
             }
 
             for id in compound_visitor.ids {
                 self.id_to_selector
                     .entry(id, quirks_mode)
                     .or_insert_with(SmallVec::new)
-                    .push(Dependency {
+                    .try_push(Dependency {
                         selector: selector.clone(),
                         selector_offset: sequence_start,
-                    })
+                    })?;
             }
 
             if !compound_visitor.state.is_empty() {
                 self.state_affecting_selectors
                     .insert(StateDependency {
                         dep: Dependency {
                             selector: selector.clone(),
                             selector_offset: sequence_start,
                         },
                         state: compound_visitor.state,
-                    }, quirks_mode);
+                    }, quirks_mode)?;
             }
 
             if compound_visitor.other_attributes {
                 self.other_attribute_affecting_selectors
                     .insert(Dependency {
                         selector: selector.clone(),
                         selector_offset: sequence_start,
-                    }, quirks_mode);
+                    }, quirks_mode)?;
             }
 
             combinator = iter.next_sequence();
             if combinator.is_none() {
                 break;
             }
 
             index += 1; // Account for the combinator.
         }
+
+        Ok(())
     }
 
     /// Measures heap usage.
     #[cfg(feature = "gecko")]
     pub fn malloc_size_of_children(&self, malloc_size_of: MallocSizeOfFn,
                                    malloc_enclosing_size_of: MallocEnclosingSizeOfFn)
                                    -> usize {
         // Currently we measure the HashMap storage, but not things pointed to
--- a/servo/components/style/lib.rs
+++ b/servo/components/style/lib.rs
@@ -42,16 +42,17 @@ extern crate arrayvec;
 extern crate atomic_refcell;
 extern crate bit_vec;
 #[macro_use]
 extern crate bitflags;
 #[allow(unused_extern_crates)] extern crate byteorder;
 #[cfg(feature = "gecko")] #[macro_use] #[no_link] extern crate cfg_if;
 #[macro_use] extern crate cssparser;
 extern crate euclid;
+extern crate fallible;
 extern crate fnv;
 #[cfg(feature = "gecko")] #[macro_use] pub mod gecko_string_cache;
 extern crate hashglobe;
 #[cfg(feature = "servo")] extern crate heapsize;
 #[cfg(feature = "servo")] #[macro_use] extern crate heapsize_derive;
 extern crate itertools;
 extern crate itoa;
 #[cfg(feature = "servo")] #[macro_use] extern crate html5ever;
--- a/servo/components/style/selector_map.rs
+++ b/servo/components/style/selector_map.rs
@@ -4,18 +4,20 @@
 
 //! A data structure to efficiently index structs containing selectors by local
 //! name, ids and hash.
 
 use {Atom, LocalName};
 use applicable_declarations::ApplicableDeclarationBlock;
 use context::QuirksMode;
 use dom::TElement;
+use fallible::FallibleVec;
 use hash::{HashMap, HashSet};
 use hash::map as hash_map;
+use hashglobe::FailedAllocationError;
 use pdqsort::sort_by;
 use precomputed_hash::PrecomputedHash;
 use rule_tree::CascadeLevel;
 use selector_parser::SelectorImpl;
 use selectors::matching::{matches_selector, MatchingContext, ElementSelectorFlags};
 use selectors::parser::{Component, Combinator, SelectorIter};
 use smallvec::{SmallVec, VecLike};
 use std::hash::{BuildHasherDefault, Hash, Hasher};
@@ -267,58 +269,59 @@ impl SelectorMap<Rule> {
                     rule.to_applicable_declaration_block(cascade_level));
             }
         }
     }
 }
 
 impl<T: SelectorMapEntry> SelectorMap<T> {
     /// Inserts into the correct hash, trying id, class, and localname.
-    pub fn insert(&mut self, entry: T, quirks_mode: QuirksMode) {
+    pub fn insert(
+        &mut self,
+        entry: T,
+        quirks_mode: QuirksMode
+    ) -> Result<(), FailedAllocationError> {
         self.count += 1;
 
         let vector = match find_bucket(entry.selector()) {
             Bucket::ID(id) => {
-                self.id_hash
-                    .entry(id.clone(), quirks_mode)
+                self.id_hash.try_entry(id.clone(), quirks_mode)?
                     .or_insert_with(SmallVec::new)
             }
             Bucket::Class(class) => {
-                self.class_hash
-                    .entry(class.clone(), quirks_mode)
+                self.class_hash.try_entry(class.clone(), quirks_mode)?
                     .or_insert_with(SmallVec::new)
             }
             Bucket::LocalName { name, lower_name } => {
                 // If the local name in the selector isn't lowercase, insert it
                 // into the rule hash twice. This means that, during lookup, we
                 // can always find the rules based on the local name of the
                 // element, regardless of whether it's an html element in an
                 // html document (in which case we match against lower_name) or
                 // not (in which case we match against name).
                 //
                 // In the case of a non-html-element-in-html-document with a
                 // lowercase localname and a non-lowercase selector, the
                 // rulehash lookup may produce superfluous selectors, but the
                 // subsequent selector matching work will filter them out.
                 if name != lower_name {
                     self.local_name_hash
-                        .entry(lower_name.clone())
+                        .try_entry(lower_name.clone())?
                         .or_insert_with(SmallVec::new)
-                        .push(entry.clone());
+                        .try_push(entry.clone())?;
                 }
-                self.local_name_hash
-                    .entry(name.clone())
+                self.local_name_hash.try_entry(name.clone())?
                     .or_insert_with(SmallVec::new)
             }
             Bucket::Universal => {
                 &mut self.other
             }
         };
 
-        vector.push(entry);
+        vector.try_push(entry)
     }
 
     /// Looks up entries by id, class, local name, and other (in order).
     ///
     /// Each entry is passed to the callback, which returns true to continue
     /// iterating entries, or false to terminate the lookup.
     ///
     /// Returns false if the callback ever returns false.
@@ -505,16 +508,28 @@ impl<V: 'static> MaybeCaseInsensitiveHas
     /// HashMap::entry
     pub fn entry(&mut self, mut key: Atom, quirks_mode: QuirksMode) -> hash_map::Entry<Atom, V> {
         if quirks_mode == QuirksMode::Quirks {
             key = key.to_ascii_lowercase()
         }
         self.0.entry(key)
     }
 
+    /// HashMap::try_entry
+    pub fn try_entry(
+        &mut self,
+        mut key: Atom,
+        quirks_mode: QuirksMode
+    ) -> Result<hash_map::Entry<Atom, V>, FailedAllocationError> {
+        if quirks_mode == QuirksMode::Quirks {
+            key = key.to_ascii_lowercase()
+        }
+        self.0.try_entry(key)
+    }
+
     /// HashMap::iter
     pub fn iter(&self) -> hash_map::Iter<Atom, V> {
         self.0.iter()
     }
 
     /// HashMap::clear
     pub fn clear(&mut self) {
         self.0.clear()
--- a/servo/components/style/stylesheets/stylesheet.rs
+++ b/servo/components/style/stylesheets/stylesheet.rs
@@ -1,16 +1,17 @@
 /* This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 use {Prefix, Namespace};
 use context::QuirksMode;
 use cssparser::{Parser, RuleListParser, ParserInput};
 use error_reporting::{ParseErrorReporter, ContextualParseError};
+use fallible::FallibleVec;
 use fnv::FnvHashMap;
 use invalidation::media_queries::{MediaListKey, ToMediaListKey};
 use media_queries::{MediaList, Device};
 use parking_lot::RwLock;
 use parser::{ParserContext, ParserErrorContext};
 use servo_arc::Arc;
 use shared_lock::{DeepCloneParams, DeepCloneWithLock, Locked, SharedRwLock, SharedRwLockReadGuard};
 use std::mem;
@@ -377,17 +378,24 @@ impl Stylesheet {
         };
 
         {
             let mut iter =
                 RuleListParser::new_for_stylesheet(&mut input, rule_parser);
 
             while let Some(result) = iter.next() {
                 match result {
-                    Ok(rule) => rules.push(rule),
+                    Ok(rule) => {
+                        // Use a fallible push here, and if it fails, just
+                        // fall out of the loop.  This will cause the page to
+                        // be shown incorrectly, but it's better than OOMing.
+                        if rules.try_push(rule).is_err() {
+                            break;
+                        }
+                    },
                     Err(err) => {
                         let error = ContextualParseError::InvalidRule(err.slice, err.error);
                         iter.parser.context.log_css_error(&iter.parser.error_context,
                                                           err.location, error);
                     }
                 }
             }
         }
--- a/servo/components/style/stylist.rs
+++ b/servo/components/style/stylist.rs
@@ -8,16 +8,17 @@ use {Atom, LocalName, Namespace};
 use applicable_declarations::{ApplicableDeclarationBlock, ApplicableDeclarationList};
 use bit_vec::BitVec;
 use context::{CascadeInputs, QuirksMode};
 use dom::TElement;
 use element_state::ElementState;
 use font_metrics::FontMetricsProvider;
 #[cfg(feature = "gecko")]
 use gecko_bindings::structs::{nsIAtom, ServoStyleSetSizes, StyleRuleInclusion};
+use hashglobe::FailedAllocationError;
 use invalidation::element::invalidation_map::InvalidationMap;
 use invalidation::media_queries::{EffectiveMediaQueryResults, ToMediaListKey};
 use media_queries::Device;
 use properties::{self, CascadeFlags, ComputedValues};
 use properties::{AnimationRules, PropertyDeclarationBlock};
 #[cfg(feature = "servo")]
 use properties::INHERIT_ALL;
 use properties::IS_LINK;
@@ -82,26 +83,27 @@ struct DocumentCascadeData {
 }
 
 impl DocumentCascadeData {
     fn iter_origins(&self) -> PerOriginIter<CascadeData> {
         self.per_origin.iter_origins()
     }
 
     /// Rebuild the cascade data for the given document stylesheets, and
-    /// optionally with a set of user agent stylesheets.
+    /// optionally with a set of user agent stylesheets.  Returns Err(..)
+    /// to signify OOM.
     fn rebuild<'a, 'b, S>(
         &mut self,
         device: &Device,
         quirks_mode: QuirksMode,
         flusher: StylesheetFlusher<'a, 'b, S>,
         guards: &StylesheetGuards,
         ua_stylesheets: Option<&UserAgentStylesheets>,
         extra_data: &mut PerOrigin<ExtraStyleData>,
-    )
+    ) -> Result<(), FailedAllocationError>
     where
         'b: 'a,
         S: StylesheetInDocument + ToMediaListKey + PartialEq + 'static,
     {
         debug_assert!(!flusher.nothing_to_do());
 
         for (cascade_data, origin) in self.per_origin.iter_mut_origins() {
             let validity = flusher.origin_validity(origin);
@@ -149,17 +151,17 @@ impl DocumentCascadeData {
 
                 self.add_stylesheet(
                     device,
                     quirks_mode,
                     stylesheet,
                     guards.ua_or_user,
                     extra_data,
                     SheetRebuildKind::Full,
-                );
+                )?;
             }
 
             if quirks_mode != QuirksMode::NoQuirks {
                 let stylesheet = &ua_stylesheets.quirks_mode_stylesheet;
                 let sheet_origin =
                     stylesheet.contents(guards.ua_or_user).origin;
 
                 debug_assert!(matches!(
@@ -178,48 +180,51 @@ impl DocumentCascadeData {
                 if validity != OriginValidity::Valid {
                     self.add_stylesheet(
                         device,
                         quirks_mode,
                         &ua_stylesheets.quirks_mode_stylesheet,
                         guards.ua_or_user,
                         extra_data,
                         SheetRebuildKind::Full,
-                    );
+                    )?;
                 }
             }
         }
 
         for (stylesheet, rebuild_kind) in flusher {
             self.add_stylesheet(
                 device,
                 quirks_mode,
                 stylesheet,
                 guards.author,
                 extra_data,
                 rebuild_kind,
-            );
+            )?;
         }
+
+        Ok(())
     }
 
+    // Returns Err(..) to signify OOM
     fn add_stylesheet<S>(
         &mut self,
         device: &Device,
         quirks_mode: QuirksMode,
         stylesheet: &S,
         guard: &SharedRwLockReadGuard,
         _extra_data: &mut PerOrigin<ExtraStyleData>,
         rebuild_kind: SheetRebuildKind,
-    )
+    ) -> Result<(), FailedAllocationError>
     where
         S: StylesheetInDocument + ToMediaListKey + 'static,
     {
         if !stylesheet.enabled() ||
            !stylesheet.is_effective_for_device(device, guard) {
-            return;
+            return Ok(());
         }
 
         let origin = stylesheet.origin(guard);
         let origin_cascade_data =
             self.per_origin.borrow_mut_for_origin(&origin);
 
         if rebuild_kind.should_rebuild_invalidation() {
             origin_cascade_data
@@ -272,38 +277,38 @@ impl DocumentCascadeData {
 
                         let rule = Rule::new(
                             selector.clone(),
                             hashes.clone(),
                             locked.clone(),
                             origin_cascade_data.rules_source_order
                         );
 
-                        map.insert(rule, quirks_mode);
+                        map.insert(rule, quirks_mode)?;
 
                         if rebuild_kind.should_rebuild_invalidation() {
                             origin_cascade_data
                                 .invalidation_map
-                                .note_selector(selector, quirks_mode);
+                                .note_selector(selector, quirks_mode)?;
                             let mut visitor = StylistSelectorVisitor {
                                 needs_revalidation: false,
                                 passed_rightmost_selector: false,
                                 attribute_dependencies: &mut origin_cascade_data.attribute_dependencies,
                                 style_attribute_dependency: &mut origin_cascade_data.style_attribute_dependency,
                                 state_dependencies: &mut origin_cascade_data.state_dependencies,
                                 mapped_ids: &mut origin_cascade_data.mapped_ids,
                             };
 
                             selector.visit(&mut visitor);
 
                             if visitor.needs_revalidation {
                                 origin_cascade_data.selectors_for_cache_revalidation.insert(
                                     RevalidationSelectorAndHashes::new(selector.clone(), hashes),
                                     quirks_mode
-                                );
+                                )?;
                             }
                         }
                     }
                     origin_cascade_data.rules_source_order += 1;
                 }
                 CssRule::Import(ref lock) => {
                     if rebuild_kind.should_rebuild_invalidation() {
                         let import_rule = lock.read_with(guard);
@@ -331,17 +336,18 @@ impl DocumentCascadeData {
                     let needs_insertion =
                         keyframes_rule.vendor_prefix.is_none() ||
                         origin_cascade_data.animations.get(keyframes_rule.name.as_atom())
                             .map_or(true, |rule| rule.vendor_prefix.is_some());
                     if needs_insertion {
                         let animation = KeyframesAnimation::from_keyframes(
                             &keyframes_rule.keyframes, keyframes_rule.vendor_prefix.clone(), guard);
                         debug!("Found valid keyframe animation: {:?}", animation);
-                        origin_cascade_data.animations.insert(keyframes_rule.name.as_atom().clone(), animation);
+                        origin_cascade_data.animations
+                            .try_insert(keyframes_rule.name.as_atom().clone(), animation)?;
                     }
                 }
                 #[cfg(feature = "gecko")]
                 CssRule::FontFace(ref rule) => {
                     _extra_data
                         .borrow_mut_for_origin(&origin)
                         .add_font_face(rule);
                 }
@@ -362,16 +368,18 @@ impl DocumentCascadeData {
                     _extra_data
                         .borrow_mut_for_origin(&origin)
                         .add_page(rule);
                 }
                 // We don't care about any other rule.
                 _ => {}
             }
         }
+
+        Ok(())
     }
 
     /// Measures heap usage.
     #[cfg(feature = "gecko")]
     pub fn malloc_add_size_of_children(&self, malloc_size_of: MallocSizeOfFn,
                                        malloc_enclosing_size_of: MallocEnclosingSizeOfFn,
                                        sizes: &mut ServoStyleSetSizes) {
         self.per_origin.user_agent.malloc_add_size_of_children(malloc_size_of,
@@ -599,17 +607,17 @@ impl Stylist {
 
         self.cascade_data.rebuild(
             &self.device,
             self.quirks_mode,
             flusher,
             guards,
             ua_sheets,
             extra_data,
-        );
+        ).unwrap_or_else(|_| warn!("OOM in Stylist::flush"));
 
         had_invalidations
     }
 
     /// Insert a given stylesheet before another stylesheet in the document.
     pub fn insert_stylesheet_before(
         &mut self,
         sheet: StylistSheet,
--- a/servo/tests/unit/style/stylist.rs
+++ b/servo/tests/unit/style/stylist.rs
@@ -164,19 +164,21 @@ fn test_rule_ordering_same_specificity()
     assert!((a.specificity(), a.source_order) < ((b.specificity(), b.source_order)),
             "The rule that comes later should win.");
 }
 
 #[test]
 fn test_insert() {
     let (rules_list, _) = get_mock_rules(&[".intro.foo", "#top"]);
     let mut selector_map = SelectorMap::new();
-    selector_map.insert(rules_list[1][0].clone(), QuirksMode::NoQuirks);
+    selector_map.insert(rules_list[1][0].clone(), QuirksMode::NoQuirks)
+                .expect("OOM");
     assert_eq!(1, selector_map.id_hash.get(&Atom::from("top"), QuirksMode::NoQuirks).unwrap()[0].source_order);
-    selector_map.insert(rules_list[0][0].clone(), QuirksMode::NoQuirks);
+    selector_map.insert(rules_list[0][0].clone(), QuirksMode::NoQuirks)
+                .expect("OOM");
     assert_eq!(0, selector_map.class_hash.get(&Atom::from("foo"), QuirksMode::NoQuirks).unwrap()[0].source_order);
     assert!(selector_map.class_hash.get(&Atom::from("intro"), QuirksMode::NoQuirks).is_none());
 }
 
 fn mock_stylist() -> Stylist {
     let device = Device::new(MediaType::screen(), TypedSize2D::new(0f32, 0f32), ScaleFactor::new(1.0));
     Stylist::new(device, QuirksMode::NoQuirks)
 }