Auto merge of #26955 - Gankro:raw-vec, r=bluss,alexcrichton

Per the top level comment:

A low-level utility for more ergonomically allocating, reallocating, and deallocating a
a buffer of memory on the heap without having to worry about all the corner cases
involved. This type is excellent for building your own data structures like Vec and VecDeque.
In particular:

* Produces heap::EMPTY on zero-sized types
* Produces heap::EMPTY on zero-length allocations
* Catches all overflows in capacity computations (promotes them to "capacity overflow" panics)
* Guards against 32-bit systems allocating more than isize::MAX bytes
* Guards against overflowing your length
* Aborts on OOM
* Avoids freeing heap::EMPTY
* Contains a ptr::Unique and thus endows the user with all related benefits

This type does not in anyway inspect the memory that it manages. When dropped it *will*
free its memory, but it *won't* try to Drop its contents. It is up to the user of RawVec
to handle the actual things *stored* inside of a RawVec.

Note that a RawVec always forces its capacity to be usize::MAX for zero-sized types.
This enables you to use capacity growing logic catch the overflows in your length
that might occur with zero-sized types.

However this means that you need to be careful when roundtripping this type
with a `Box<[T]>`: `cap()` won't yield the len. However `with_capacity`,
`shrink_to_fit`, and `from_box` will actually set RawVec's private capacity
field. This allows zero-sized types to not be special-cased by consumers of
this type.

Edit: 
fixes #18726 and fixes #23842

3 files changed, 456 insertions, 1 deletions

diff --git a/src/liballoc/boxed.rs b/src/liballoc/boxed.rs
index c941629b871..d9653cecc73 100644
--- a/src/liballoc/boxed.rs
+++ b/src/liballoc/boxed.rs
@@ -62,7 +62,7 @@ use core::hash::{self, Hash};
 use core::marker::Unsize;
 use core::mem;
 use core::ops::{CoerceUnsized, Deref, DerefMut};
-use core::ptr::{Unique};
+use core::ptr::Unique;
 use core::raw::{TraitObject};
 
 /// A value that represents the heap. This is the default place that the `box`
diff --git a/src/liballoc/lib.rs b/src/liballoc/lib.rs
index 905012bbb64..5c1fd2a1aa1 100644
--- a/src/liballoc/lib.rs
+++ b/src/liballoc/lib.rs
@@ -88,6 +88,7 @@
 #![feature(unique)]
 #![feature(unsafe_no_drop_flag, filling_drop)]
 #![feature(unsize)]
+#![feature(core_slice_ext)]
 
 #![cfg_attr(test, feature(test, alloc, rustc_private, box_raw))]
 #![cfg_attr(all(not(feature = "external_funcs"), not(feature = "external_crate")),
@@ -122,6 +123,7 @@ mod boxed { pub use std::boxed::{Box, HEAP}; }
 mod boxed_test;
 pub mod arc;
 pub mod rc;
+pub mod raw_vec;
 
 /// Common out-of-memory routine
 #[cold]
diff --git a/src/liballoc/raw_vec.rs b/src/liballoc/raw_vec.rs
new file mode 100644
index 00000000000..9311f44d9df
--- /dev/null
+++ b/src/liballoc/raw_vec.rs
@@ -0,0 +1,453 @@
+// Copyright 2015 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// 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.
+
+use core::ptr::Unique;
+use core::mem;
+use core::slice::{self, SliceExt};
+use heap;
+use super::oom;
+use super::boxed::Box;
+use core::ops::Drop;
+
+/// A low-level utility for more ergonomically allocating, reallocating, and deallocating a
+/// a buffer of memory on the heap without having to worry about all the corner cases
+/// involved. This type is excellent for building your own data structures like Vec and VecDeque.
+/// In particular:
+///
+/// * Produces heap::EMPTY on zero-sized types
+/// * Produces heap::EMPTY on zero-length allocations
+/// * Catches all overflows in capacity computations (promotes them to "capacity overflow" panics)
+/// * Guards against 32-bit systems allocating more than isize::MAX bytes
+/// * Guards against overflowing your length
+/// * Aborts on OOM
+/// * Avoids freeing heap::EMPTY
+/// * Contains a ptr::Unique and thus endows the user with all related benefits
+///
+/// This type does not in anyway inspect the memory that it manages. When dropped it *will*
+/// free its memory, but it *won't* try to Drop its contents. It is up to the user of RawVec
+/// to handle the actual things *stored* inside of a RawVec.
+///
+/// Note that a RawVec always forces its capacity to be usize::MAX for zero-sized types.
+/// This enables you to use capacity growing logic catch the overflows in your length
+/// that might occur with zero-sized types.
+///
+/// However this means that you need to be careful when roundtripping this type
+/// with a `Box<[T]>`: `cap()` won't yield the len. However `with_capacity`,
+/// `shrink_to_fit`, and `from_box` will actually set RawVec's private capacity
+/// field. This allows zero-sized types to not be special-cased by consumers of
+/// this type.
+#[unsafe_no_drop_flag]
+pub struct RawVec<T> {
+    ptr: Unique<T>,
+    cap: usize,
+}
+
+impl<T> RawVec<T> {
+    /// Creates the biggest possible RawVec without allocating. If T has positive
+    /// size, then this makes a RawVec with capacity 0. If T has 0 size, then it
+    /// it makes a RawVec with capacity `usize::MAX`. Useful for implementing
+    /// delayed allocation.
+    pub fn new() -> Self {
+        unsafe {
+            // !0 is usize::MAX. This branch should be stripped at compile time.
+            let cap = if mem::size_of::<T>() == 0 { !0 } else { 0 };
+
+            // heap::EMPTY doubles as "unallocated" and "zero-sized allocation"
+            RawVec { ptr: Unique::new(heap::EMPTY as *mut T), cap: cap }
+        }
+    }
+
+    /// Creates a RawVec with exactly the capacity and alignment requirements
+    /// for a `[T; cap]`. This is equivalent to calling RawVec::new when `cap` is 0
+    /// or T is zero-sized. Note that if `T` is zero-sized this means you will *not*
+    /// get a RawVec with the requested capacity!
+    ///
+    /// # Panics
+    ///
+    /// * Panics if the requested capacity exceeds `usize::MAX` bytes.
+    /// * Panics on 32-bit platforms if the requested capacity exceeds
+    ///   `isize::MAX` bytes.
+    ///
+    /// # Aborts
+    ///
+    /// Aborts on OOM
+    pub fn with_capacity(cap: usize) -> Self {
+        unsafe {
+            let elem_size = mem::size_of::<T>();
+
+            let alloc_size = cap.checked_mul(elem_size).expect("capacity overflow");
+            alloc_guard(alloc_size);
+
+            // handles ZSTs and `cap = 0` alike
+            let ptr = if alloc_size == 0 {
+                heap::EMPTY as *mut u8
+            } else {
+                let align = mem::align_of::<T>();
+                let ptr = heap::allocate(alloc_size, align);
+                if ptr.is_null() { oom() }
+                ptr
+            };
+
+            RawVec { ptr: Unique::new(ptr as *mut _), cap: cap }
+        }
+    }
+
+    /// Reconstitutes a RawVec from a pointer and capacity.
+    ///
+    /// # Undefined Behaviour
+    ///
+    /// The ptr must be allocated, and with the given capacity. The
+    /// capacity cannot exceed `isize::MAX` (only a concern on 32-bit systems).
+    /// If the ptr and capacity come from a RawVec, then this is guaranteed.
+    pub unsafe fn from_raw_parts(ptr: *mut T, cap: usize) -> Self {
+        RawVec { ptr: Unique::new(ptr), cap: cap }
+    }
+
+    /// Converts a `Box<[T]>` into a `RawVec<T>`.
+    pub fn from_box(mut slice: Box<[T]>) -> Self {
+        unsafe {
+            let result = RawVec::from_raw_parts(slice.as_mut_ptr(), slice.len());
+            mem::forget(slice);
+            result
+        }
+    }
+}
+
+impl<T> RawVec<T> {
+    /// Gets a raw pointer to the start of the allocation. Note that this is
+    /// heap::EMPTY if `cap = 0` or T is zero-sized. In the former case, you must
+    /// be careful.
+    pub fn ptr(&self) -> *mut T {
+        *self.ptr
+    }
+
+    /// Gets the capacity of the allocation.
+    ///
+    /// This will always be `usize::MAX` if `T` is zero-sized.
+    pub fn cap(&self) -> usize {
+        if mem::size_of::<T>() == 0 { !0 } else { self.cap }
+    }
+
+    /// Doubles the size of the type's backing allocation. This is common enough
+    /// to want to do that it's easiest to just have a dedicated method. Slightly
+    /// more efficient logic can be provided for this than the general case.
+    ///
+    /// This function is ideal for when pushing elements one-at-a-time because
+    /// you don't need to incur the costs of the more general computations
+    /// reserve needs to do to guard against overflow. You do however need to
+    /// manually check if your `len == cap`.
+    ///
+    /// # Panics
+    ///
+    /// * Panics if T is zero-sized on the assumption that you managed to exhaust
+    ///   all `usize::MAX` slots in your imaginary buffer.
+    /// * Panics on 32-bit platforms if the requested capacity exceeds
+    ///   `isize::MAX` bytes.
+    ///
+    /// # Aborts
+    ///
+    /// Aborts on OOM
+    ///
+    /// # Examples
+    ///
+    /// ```ignore
+    /// struct MyVec<T> {
+    ///     buf: RawVec<T>,
+    ///     len: usize,
+    /// }
+    ///
+    /// impl<T> MyVec<T> {
+    ///     pub fn push(&mut self, elem: T) {
+    ///         if self.len == self.buf.cap() { self.buf.double(); }
+    ///         // double would have aborted or panicked if the len exceeded
+    ///         // `isize::MAX` so this is safe to do unchecked now.
+    ///         unsafe {
+    ///             ptr::write(self.buf.ptr().offset(self.len as isize), elem);
+    ///         }
+    ///         self.len += 1;
+    ///     }
+    /// }
+    /// ```
+    #[inline(never)]
+    #[cold]
+    pub fn double(&mut self) {
+        unsafe {
+            let elem_size = mem::size_of::<T>();
+
+            // since we set the capacity to usize::MAX when elem_size is
+            // 0, getting to here necessarily means the RawVec is overfull.
+            assert!(elem_size != 0, "capacity overflow");
+
+            let align = mem::align_of::<T>();
+
+            let (new_cap, ptr) = if self.cap == 0 {
+                // skip to 4 because tiny Vec's are dumb; but not if that would cause overflow
+                let new_cap = if elem_size > (!0) / 8 { 1 } else { 4 };
+                let ptr = heap::allocate(new_cap * elem_size, align);
+                (new_cap, ptr)
+            } else {
+                // Since we guarantee that we never allocate more than isize::MAX bytes,
+                // `elem_size * self.cap <= isize::MAX` as a precondition, so this can't overflow
+                let new_cap = 2 * self.cap;
+                let new_alloc_size = new_cap * elem_size;
+                alloc_guard(new_alloc_size);
+                let ptr = heap::reallocate(self.ptr() as *mut _,
+                                           self.cap * elem_size,
+                                           new_alloc_size,
+                                           align);
+                (new_cap, ptr)
+            };
+
+            // If allocate or reallocate fail, we'll get `null` back
+            if ptr.is_null() { oom() }
+
+            self.ptr = Unique::new(ptr as *mut _);
+            self.cap = new_cap;
+        }
+    }
+
+    /// Ensures that the buffer contains at least enough space to hold
+    /// `used_cap + needed_extra_cap` elements. If it doesn't already,
+    /// will reallocate the minimum possible amount of memory necessary.
+    /// Generally this will be exactly the amount of memory necessary,
+    /// but in principle the allocator is free to give back more than
+    /// we asked for.
+    ///
+    /// If `used_cap` exceeds `self.cap()`, this may fail to actually allocate
+    /// the requested space. This is not really unsafe, but the unsafe
+    /// code *you* write that relies on the behaviour of this function may break.
+    ///
+    /// # Panics
+    ///
+    /// * Panics if the requested capacity exceeds `usize::MAX` bytes.
+    /// * Panics on 32-bit platforms if the requested capacity exceeds
+    ///   `isize::MAX` bytes.
+    ///
+    /// # Aborts
+    ///
+    /// Aborts on OOM
+    pub fn reserve_exact(&mut self, used_cap: usize, needed_extra_cap: usize) {
+        unsafe {
+            let elem_size = mem::size_of::<T>();
+            let align = mem::align_of::<T>();
+
+            // NOTE: we don't early branch on ZSTs here because we want this
+            // to actually catch "asking for more than usize::MAX" in that case.
+            // If we make it past the first branch then we are guaranteed to
+            // panic.
+
+            // Don't actually need any more capacity.
+            // Wrapping in case they gave a bad `used_cap`.
+            if self.cap().wrapping_sub(used_cap) >= needed_extra_cap { return; }
+
+            // Nothing we can really do about these checks :(
+            let new_cap = used_cap.checked_add(needed_extra_cap).expect("capacity overflow");
+            let new_alloc_size = new_cap.checked_mul(elem_size).expect("capacity overflow");
+            alloc_guard(new_alloc_size);
+
+            let ptr = if self.cap == 0 {
+                heap::allocate(new_alloc_size, align)
+            } else {
+                heap::reallocate(self.ptr() as *mut _,
+                                 self.cap * elem_size,
+                                 new_alloc_size,
+                                 align)
+            };
+
+            // If allocate or reallocate fail, we'll get `null` back
+            if ptr.is_null() { oom() }
+
+            self.ptr = Unique::new(ptr as *mut _);
+            self.cap = new_cap;
+        }
+    }
+
+    /// Ensures that the buffer contains at least enough space to hold
+    /// `used_cap + needed_extra_cap` elements. If it doesn't already have
+    /// enough capacity, will reallocate enough space plus comfortable slack
+    /// space to get amortized `O(1)` behaviour. Will limit this behaviour
+    /// if it would needlessly cause itself to panic.
+    ///
+    /// If `used_cap` exceeds `self.cap()`, this may fail to actually allocate
+    /// the requested space. This is not really unsafe, but the unsafe
+    /// code *you* write that relies on the behaviour of this function may break.
+    ///
+    /// This is ideal for implementing a bulk-push operation like `extend`.
+    ///
+    /// # Panics
+    ///
+    /// * Panics if the requested capacity exceeds `usize::MAX` bytes.
+    /// * Panics on 32-bit platforms if the requested capacity exceeds
+    ///   `isize::MAX` bytes.
+    ///
+    /// # Aborts
+    ///
+    /// Aborts on OOM
+    ///
+    /// # Examples
+    ///
+    /// ```ignore
+    /// struct MyVec<T> {
+    ///     buf: RawVec<T>,
+    ///     len: usize,
+    /// }
+    ///
+    /// impl<T> MyVec<T> {
+    ///     pub fn push_all(&mut self, elems: &[T]) {
+    ///         self.buf.reserve(self.len, elems.len());
+    ///         // reserve would have aborted or panicked if the len exceeded
+    ///         // `isize::MAX` so this is safe to do unchecked now.
+    ///         for x in elems {
+    ///             unsafe {
+    ///                 ptr::write(self.buf.ptr().offset(self.len as isize), x.clone());
+    ///             }
+    ///             self.len += 1;
+    ///         }
+    ///     }
+    /// }
+    /// ```
+    pub fn reserve(&mut self, used_cap: usize, needed_extra_cap: usize) {
+        unsafe {
+            let elem_size = mem::size_of::<T>();
+            let align = mem::align_of::<T>();
+
+            // NOTE: we don't early branch on ZSTs here because we want this
+            // to actually catch "asking for more than usize::MAX" in that case.
+            // If we make it past the first branch then we are guaranteed to
+            // panic.
+
+            // Don't actually need any more capacity.
+            // Wrapping in case they give a bas `used_cap`
+            if self.cap().wrapping_sub(used_cap) >= needed_extra_cap { return; }
+
+            // Nothing we can really do about these checks :(
+            let new_cap = used_cap.checked_add(needed_extra_cap)
+                                  .and_then(|cap| cap.checked_mul(2))
+                                  .expect("capacity overflow");
+            let new_alloc_size = new_cap.checked_mul(elem_size).expect("capacity overflow");
+            // FIXME: may crash and burn on over-reserve
+            alloc_guard(new_alloc_size);
+
+            let ptr = if self.cap == 0 {
+                heap::allocate(new_alloc_size, align)
+            } else {
+                heap::reallocate(self.ptr() as *mut _,
+                                 self.cap * elem_size,
+                                 new_alloc_size,
+                                 align)
+            };
+
+            // If allocate or reallocate fail, we'll get `null` back
+            if ptr.is_null() { oom() }
+
+            self.ptr = Unique::new(ptr as *mut _);
+            self.cap = new_cap;
+        }
+    }
+
+    /// Shrinks the allocation down to the specified amount. If the given amount
+    /// is 0, actually completely deallocates.
+    ///
+    /// # Panics
+    ///
+    /// Panics if the given amount is *larger* than the current capacity.
+    ///
+    /// # Aborts
+    ///
+    /// Aborts on OOM.
+    pub fn shrink_to_fit(&mut self, amount: usize) {
+        let elem_size = mem::size_of::<T>();
+        let align = mem::align_of::<T>();
+
+        // Set the `cap` because they might be about to promote to a `Box<[T]>`
+        if elem_size == 0 {
+            self.cap = amount;
+            return;
+        }
+
+        // This check is my waterloo; it's the only thing Vec wouldn't have to do.
+        assert!(self.cap >= amount, "Tried to shrink to a larger capacity");
+
+        if amount == 0 {
+            mem::replace(self, RawVec::new());
+        } else if self.cap != amount {
+            unsafe {
+                // Overflow check is unnecessary as the vector is already at
+                // least this large.
+                let ptr = heap::reallocate(self.ptr() as *mut _,
+                                           self.cap * elem_size,
+                                           amount * elem_size,
+                                           align);
+                if ptr.is_null() { oom() }
+                self.ptr = Unique::new(ptr as *mut _);
+            }
+            self.cap = amount;
+        }
+    }
+
+    /// Converts the entire buffer into `Box<[T]>`.
+    ///
+    /// While it is not *strictly* Undefined Behaviour to call
+    /// this procedure while some of the RawVec is unintialized,
+    /// it cetainly makes it trivial to trigger it.
+    ///
+    /// Note that this will correctly reconstitute any `cap` changes
+    /// that may have been performed. (see description of type for details)
+    pub unsafe fn into_box(self) -> Box<[T]> {
+        // NOTE: not calling `cap()` here, actually using the real `cap` field!
+        let slice = slice::from_raw_parts_mut(self.ptr(), self.cap);
+        let output: Box<[T]> = Box::from_raw(slice);
+        mem::forget(self);
+        output
+    }
+
+    /// This is a stupid name in the hopes that someone will find this in the
+    /// not too distant future and remove it with the rest of
+    /// #[unsafe_no_drop_flag]
+    pub fn unsafe_no_drop_flag_needs_drop(&self) -> bool {
+        self.cap != mem::POST_DROP_USIZE
+    }
+}
+
+impl<T> Drop for RawVec<T> {
+    /// Frees the memory owned by the RawVec *without* trying to Drop its contents.
+    fn drop(&mut self) {
+        let elem_size = mem::size_of::<T>();
+        if elem_size != 0 && self.cap != 0 && self.unsafe_no_drop_flag_needs_drop() {
+            let align = mem::align_of::<T>();
+
+            let num_bytes = elem_size * self.cap;
+            unsafe {
+                heap::deallocate(*self.ptr as *mut _, num_bytes, align);
+            }
+        }
+    }
+}
+
+
+
+// We need to guarantee the following:
+// * We don't ever allocate `> isize::MAX` byte-size objects
+// * We don't overflow `usize::MAX` and actually allocate too little
+//
+// On 64-bit we just need to check for overflow since trying to allocate
+// `> isize::MAX` bytes will surely fail. On 32-bit we need to add an extra
+// guard for this in case we're running on a platform which can use all 4GB in
+// user-space. e.g. PAE or x32
+
+#[inline]
+#[cfg(target_pointer_width = "64")]
+fn alloc_guard(_alloc_size: usize) { }
+
+#[inline]
+#[cfg(target_pointer_width = "32")]
+fn alloc_guard(alloc_size: usize) {
+    assert!(alloc_size <= ::core::isize::MAX as usize, "capacity overflow");
+}