servo: Merge #18397 - Add fallible append APIs for Vec and SmallVec (from julian-seward1:master); r=Manishearth
authorJulian Seward <jseward@acm.org>
Thu, 07 Sep 2017 05:54:46 -0500
changeset 428939 b9b58cc99f2f434f3536a37cc0cbdce12bef1db7
parent 428938 b4b9eaba235ec71a73bd996f436bcdecfc79bf0c
child 428940 5c74e0d9dffc47a63c7ac2f618e4a01eb4961915
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)
reviewersManishearth
bugs18397
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 #18397 - Add fallible append APIs for Vec and SmallVec (from julian-seward1:master); r=Manishearth …r=manishearth. <!-- 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: c68bc0c145db3ce2df49023c1525dbfc7d252153
servo/Cargo.lock
servo/components/fallible/Cargo.toml
servo/components/fallible/lib.rs
servo/components/style/Cargo.toml
--- a/servo/Cargo.lock
+++ b/servo/Cargo.lock
@@ -968,16 +968,23 @@ dependencies = [
 ]
 
 [[package]]
 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 = [
+ "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 = [
  "libc 0.2.23 (registry+https://github.com/rust-lang/crates.io-index)",
  "miniz-sys 0.1.9 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
 
@@ -3079,16 +3086,17 @@ dependencies = [
  "bindgen 0.29.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "bit-vec 0.4.3 (registry+https://github.com/rust-lang/crates.io-index)",
  "bitflags 0.7.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "byteorder 1.0.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "cfg-if 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)",
  "cssparser 0.20.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "encoding 0.2.33 (registry+https://github.com/rust-lang/crates.io-index)",
  "euclid 0.15.1 (registry+https://github.com/rust-lang/crates.io-index)",
+ "fallible 0.0.1",
  "fnv 1.0.5 (registry+https://github.com/rust-lang/crates.io-index)",
  "hashglobe 0.1.0",
  "heapsize 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "heapsize_derive 0.1.4 (registry+https://github.com/rust-lang/crates.io-index)",
  "html5ever 0.19.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "itertools 0.5.10 (registry+https://github.com/rust-lang/crates.io-index)",
  "itoa 0.3.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "kernel32-sys 0.2.2 (registry+https://github.com/rust-lang/crates.io-index)",
new file mode 100644
--- /dev/null
+++ b/servo/components/fallible/Cargo.toml
@@ -0,0 +1,13 @@
+[package]
+name = "fallible"
+version = "0.0.1"
+authors = ["The Servo Project Developers"]
+license = "MPL-2.0"
+publish = false
+
+[lib]
+name = "fallible"
+path = "lib.rs"
+
+[dependencies]
+smallvec = "0.4"
new file mode 100644
--- /dev/null
+++ b/servo/components/fallible/lib.rs
@@ -0,0 +1,143 @@
+/* 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 smallvec;
+
+use smallvec::Array;
+use smallvec::SmallVec;
+use std::mem;
+use std::ptr::copy_nonoverlapping;
+use std::vec::Vec;
+
+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<(), ()>;
+}
+
+
+/////////////////////////////////////////////////////////////////
+// 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());
+        }
+        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.
+#[inline(never)]
+#[cold]
+fn try_double_vec<T>(vec: &mut Vec<T>) -> Result<(), ()> {
+    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_size_bytes =
+        new_cap.checked_mul(mem::size_of::<T>()).ok_or(()) ? ;
+
+    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(());
+    }
+
+    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());
+        }
+        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.
+#[inline(never)]
+#[cold]
+fn try_double_small_vec<T>(svec: &mut SmallVec<T>) -> Result<(), ()>
+where
+    T: Array,
+{
+    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(()) ? };
+
+    // 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 new_size_bytes =
+        new_cap.checked_mul(mem::size_of::<T>()).ok_or(()) ? ;
+
+    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);
+        }
+    } else {
+        // There's no old block to free.  There may be old contents to copy.
+        unsafe {
+            new_ptr = malloc(new_size_bytes);
+            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(());
+    }
+
+    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));
+    Ok(())
+}
--- a/servo/components/style/Cargo.toml
+++ b/servo/components/style/Cargo.toml
@@ -35,16 +35,17 @@ arraydeque = "0.2.3"
 atomic_refcell = "0.1"
 bitflags = "0.7"
 bit-vec = "0.4.3"
 byteorder = "1.0"
 cfg-if = "0.1.0"
 cssparser = "0.20"
 encoding = {version = "0.2", optional = true}
 euclid = "0.15"
+fallible = { path = "../fallible" }
 fnv = "1.0"
 hashglobe = { path = "../hashglobe" }
 heapsize = {version = "0.4", optional = true}
 heapsize_derive = {version = "0.1", optional = true}
 itertools = "0.5"
 itoa = "0.3"
 html5ever = {version = "0.19", optional = true}
 lazy_static = "0.2"