diff options
Diffstat (limited to 'vendor/thin-vec')
| -rw-r--r-- | vendor/thin-vec/.cargo-checksum.json | 2 | ||||
| -rw-r--r-- | vendor/thin-vec/Cargo.toml | 2 | ||||
| -rw-r--r-- | vendor/thin-vec/src/lib.rs | 1458 |
3 files changed, 1286 insertions, 176 deletions
diff --git a/vendor/thin-vec/.cargo-checksum.json b/vendor/thin-vec/.cargo-checksum.json index 33ca74234..9e4702880 100644 --- a/vendor/thin-vec/.cargo-checksum.json +++ b/vendor/thin-vec/.cargo-checksum.json @@ -1 +1 @@ -{"files":{"Cargo.toml":"49f429a38e2c6216dfddc1f23af64a3b06cf92217d75cae2a9ac389bc3f76e46","README.md":"9f102f13ccbabe9cdec7a206aa298d65e33dea84da9f08dd17b358ff44fe0286","src/lib.rs":"6a5451d75037e3cb12bde5198266a0db00432e1370cad74b0dda8df8fb64f067"},"package":"ceb05e71730d396f960f8f3901cdb41be2d339b303e9d7d3a07c5ff0536e671b"}
\ No newline at end of file +{"files":{"Cargo.toml":"391230d6db1276baa00856a9ded6ccc426a447d04a23661d7b4461137f398745","README.md":"9f102f13ccbabe9cdec7a206aa298d65e33dea84da9f08dd17b358ff44fe0286","src/lib.rs":"d3367f69119c46ac4ca8bb0a4c86c77606119200aebd56b7a30096c08a22ba40"},"package":"aac81b6fd6beb5884b0cf3321b8117e6e5d47ecb6fc89f414cfdcca8b2fe2dd8"}
\ No newline at end of file diff --git a/vendor/thin-vec/Cargo.toml b/vendor/thin-vec/Cargo.toml index 8361d94d4..01b84e4ca 100644 --- a/vendor/thin-vec/Cargo.toml +++ b/vendor/thin-vec/Cargo.toml @@ -12,7 +12,7 @@ [package] edition = "2018" name = "thin-vec" -version = "0.2.9" +version = "0.2.12" authors = ["Aria Beingessner <a.beingessner@gmail.com>"] description = "A vec that takes up less space on the stack" homepage = "https://github.com/gankra/thin-vec" diff --git a/vendor/thin-vec/src/lib.rs b/vendor/thin-vec/src/lib.rs index a2384c62e..ea24aed2e 100644 --- a/vendor/thin-vec/src/lib.rs +++ b/vendor/thin-vec/src/lib.rs @@ -1,30 +1,32 @@ -//! ThinVec is exactly the same as Vec, except that it stores its `len` and `capacity` in the buffer +#![deny(missing_docs)] + +//! `ThinVec` is exactly the same as `Vec`, except that it stores its `len` and `capacity` in the buffer //! it allocates. //! //! This makes the memory footprint of ThinVecs lower; notably in cases where space is reserved for -//! a non-existence ThinVec<T>. So `Vec<ThinVec<T>>` and `Option<ThinVec<T>>::None` will waste less +//! a non-existence `ThinVec<T>`. So `Vec<ThinVec<T>>` and `Option<ThinVec<T>>::None` will waste less //! space. Being pointer-sized also means it can be passed/stored in registers. //! -//! Of course, any actually constructed ThinVec will theoretically have a bigger allocation, but +//! Of course, any actually constructed `ThinVec` will theoretically have a bigger allocation, but //! the fuzzy nature of allocators means that might not actually be the case. //! -//! Properties of Vec that are preserved: +//! Properties of `Vec` that are preserved: //! * `ThinVec::new()` doesn't allocate (it points to a statically allocated singleton) //! * reallocation can be done in place //! * `size_of::<ThinVec<T>>()` == `size_of::<Option<ThinVec<T>>>()` //! -//! Properties of Vec that aren't preserved: +//! Properties of `Vec` that aren't preserved: //! * `ThinVec<T>` can't ever be zero-cost roundtripped to a `Box<[T]>`, `String`, or `*mut T` //! * `from_raw_parts` doesn't exist -//! * ThinVec currently doesn't bother to not-allocate for Zero Sized Types (e.g. `ThinVec<()>`), +//! * `ThinVec` currently doesn't bother to not-allocate for Zero Sized Types (e.g. `ThinVec<()>`), //! but it could be done if someone cared enough to implement it. //! //! //! //! # Gecko FFI //! -//! If you enable the gecko-ffi feature, ThinVec will verbatim bridge with the nsTArray type in -//! Gecko (Firefox). That is, ThinVec and nsTArray have identical layouts *but not ABIs*, +//! If you enable the gecko-ffi feature, `ThinVec` will verbatim bridge with the nsTArray type in +//! Gecko (Firefox). That is, `ThinVec` and nsTArray have identical layouts *but not ABIs*, //! so nsTArrays/ThinVecs an be natively manipulated by C++ and Rust, and ownership can be //! transferred across the FFI boundary (**IF YOU ARE CAREFUL, SEE BELOW!!**). //! @@ -105,17 +107,17 @@ //! While relocations are generally predictable if you're very careful, **you should avoid using //! types with significant locations with Rust FFI**. //! -//! Specifically, ThinVec will trivially relocate its contents whenever it needs to reallocate its +//! Specifically, `ThinVec` will trivially relocate its contents whenever it needs to reallocate its //! buffer to change its capacity. This is the default reallocation strategy for nsTArray, and is //! suitable for the vast majority of types. Just be aware of this limitation! //! //! ## Auto Arrays Are Dangerous //! -//! ThinVec has *some* support for handling auto arrays which store their buffer on the stack, +//! `ThinVec` has *some* support for handling auto arrays which store their buffer on the stack, //! but this isn't well tested. //! //! Regardless of how much support we provide, Rust won't be aware of the buffer's limited lifetime, -//! so standard auto array safety caveats apply about returning/storing them! ThinVec won't ever +//! so standard auto array safety caveats apply about returning/storing them! `ThinVec` won't ever //! produce an auto array on its own, so this is only an issue for transferring an nsTArray into //! Rust. //! @@ -133,7 +135,7 @@ //! defined. Specifically, we must share the symbol for nsTArray's empty singleton. You will get //! linking errors if that isn't defined. //! -//! The gecko-ffi feature also limits ThinVec to the legacy behaviors of nsTArray. Most notably, +//! The gecko-ffi feature also limits `ThinVec` to the legacy behaviors of nsTArray. Most notably, //! nsTArray has a maximum capacity of i32::MAX (~2.1 billion items). Probably not an issue. //! Probably. //! @@ -144,6 +146,8 @@ use std::alloc::*; use std::borrow::*; use std::cmp::*; +use std::convert::TryFrom; +use std::convert::TryInto; use std::hash::*; use std::iter::FromIterator; use std::marker::PhantomData; @@ -172,7 +176,7 @@ mod impl_details { mod impl_details { // Support for briding a gecko nsTArray verbatim into a ThinVec. // - // ThinVec can't see copy/move/delete implementations + // `ThinVec` can't see copy/move/delete implementations // from C++ // // The actual layout of an nsTArray is: @@ -187,7 +191,7 @@ mod impl_details { // // Rust doesn't natively support bit-fields, so we manually mask // and shift the bit. When the "auto" bit is set, the header and buffer - // are actually on the stack, meaning the ThinVec pointer-to-header + // are actually on the stack, meaning the `ThinVec` pointer-to-header // is essentially an "owned borrow", and therefore dangerous to handle. // There are no safety guards for this situation. // @@ -195,7 +199,7 @@ mod impl_details { // our capacity u32. On big-endian platforms, it will be the low bit. // Hence we need some platform-specific CFGs for the necessary masking/shifting. // - // ThinVec won't ever construct an auto array. They only happen when + // `ThinVec` won't ever construct an auto array. They only happen when // bridging from C++. This means we don't need to ever set/preserve the bit. // We just need to be able to read and handle it if it happens to be there. // @@ -270,10 +274,13 @@ struct Header { } impl Header { + #[inline] + #[allow(clippy::unnecessary_cast)] fn len(&self) -> usize { self._len as usize } + #[inline] fn set_len(&mut self, len: usize) { self._len = assert_size(len); } @@ -303,6 +310,7 @@ impl Header { #[cfg(not(feature = "gecko-ffi"))] impl Header { + #[allow(clippy::unnecessary_cast)] fn cap(&self) -> usize { self._cap as usize } @@ -326,24 +334,40 @@ extern "C" { static EMPTY_HEADER: Header; } -// TODO: overflow checks everywhere - // Utils for computing layouts of allocations +/// Gets the size necessary to allocate a `ThinVec<T>` with the give capacity. +/// +/// # Panics +/// +/// This will panic if isize::MAX is overflowed at any point. fn alloc_size<T>(cap: usize) -> usize { // Compute "real" header size with pointer math - let header_size = mem::size_of::<Header>(); - let elem_size = mem::size_of::<T>(); - let padding = padding::<T>(); - - // TODO: care about isize::MAX overflow? - let data_size = elem_size.checked_mul(cap).expect("capacity overflow"); + // + // We turn everything into isizes here so that we can catch isize::MAX overflow, + // we never want to allow allocations larger than that! + let header_size = mem::size_of::<Header>() as isize; + let padding = padding::<T>() as isize; + + let data_size = if mem::size_of::<T>() == 0 { + // If we're allocating an array for ZSTs we need a header/padding but no actual + // space for items, so we don't care about the capacity that was requested! + 0 + } else { + let cap: isize = cap.try_into().expect("capacity overflow"); + let elem_size = mem::size_of::<T>() as isize; + elem_size.checked_mul(cap).expect("capacity overflow") + }; - data_size + let final_size = data_size .checked_add(header_size + padding) - .expect("capacity overflow") + .expect("capacity overflow"); + + // Ok now we can turn it back into a usize (don't need to worry about negatives) + final_size as usize } +/// Gets the padding necessary for the array of a `ThinVec<T>` fn padding<T>() -> usize { let alloc_align = alloc_align::<T>(); let header_size = mem::size_of::<Header>(); @@ -361,14 +385,25 @@ fn padding<T>() -> usize { } } +/// Gets the align necessary to allocate a `ThinVec<T>` fn alloc_align<T>() -> usize { max(mem::align_of::<T>(), mem::align_of::<Header>()) } +/// Gets the layout necessary to allocate a `ThinVec<T>` +/// +/// # Panics +/// +/// Panics if the required size overflows `isize::MAX`. fn layout<T>(cap: usize) -> Layout { unsafe { Layout::from_size_align_unchecked(alloc_size::<T>(cap), alloc_align::<T>()) } } +/// Allocates a header (and array) for a `ThinVec<T>` with the given capacity. +/// +/// # Panics +/// +/// Panics if the required size overflows `isize::MAX`. fn header_with_capacity<T>(cap: usize) -> NonNull<Header> { debug_assert!(cap > 0); unsafe { @@ -439,10 +474,67 @@ macro_rules! thin_vec { } impl<T> ThinVec<T> { + /// Creates a new empty ThinVec. + /// + /// This will not allocate. pub fn new() -> ThinVec<T> { ThinVec::with_capacity(0) } + /// Constructs a new, empty `ThinVec<T>` with at least the specified capacity. + /// + /// The vector will be able to hold at least `capacity` elements without + /// reallocating. This method is allowed to allocate for more elements than + /// `capacity`. If `capacity` is 0, the vector will not allocate. + /// + /// It is important to note that although the returned vector has the + /// minimum *capacity* specified, the vector will have a zero *length*. + /// + /// If it is important to know the exact allocated capacity of a `ThinVec`, + /// always use the [`capacity`] method after construction. + /// + /// **NOTE**: unlike `Vec`, `ThinVec` **MUST** allocate once to keep track of non-zero + /// lengths. As such, we cannot provide the same guarantees about ThinVecs + /// of ZSTs not allocating. However the allocation never needs to be resized + /// to add more ZSTs, since the underlying array is still length 0. + /// + /// [Capacity and reallocation]: #capacity-and-reallocation + /// [`capacity`]: Vec::capacity + /// + /// # Panics + /// + /// Panics if the new capacity exceeds `isize::MAX` bytes. + /// + /// # Examples + /// + /// ``` + /// use thin_vec::ThinVec; + /// + /// let mut vec = ThinVec::with_capacity(10); + /// + /// // The vector contains no items, even though it has capacity for more + /// assert_eq!(vec.len(), 0); + /// assert!(vec.capacity() >= 10); + /// + /// // These are all done without reallocating... + /// for i in 0..10 { + /// vec.push(i); + /// } + /// assert_eq!(vec.len(), 10); + /// assert!(vec.capacity() >= 10); + /// + /// // ...but this may make the vector reallocate + /// vec.push(11); + /// assert_eq!(vec.len(), 11); + /// assert!(vec.capacity() >= 11); + /// + /// // A vector of a zero-sized type will always over-allocate, since no + /// // space is needed to store the actual elements. + /// let vec_units = ThinVec::<()>::with_capacity(10); + /// + /// // Only true **without** the gecko-ffi feature! + /// // assert_eq!(vec_units.capacity(), usize::MAX); + /// ``` pub fn with_capacity(cap: usize) -> ThinVec<T> { // `padding` contains ~static assertions against types that are // incompatible with the current feature flags. We also call it to @@ -525,16 +617,134 @@ impl<T> ThinVec<T> { &mut *self.ptr() } + /// Returns the number of elements in the vector, also referred to + /// as its 'length'. + /// + /// # Examples + /// + /// ``` + /// use thin_vec::thin_vec; + /// + /// let a = thin_vec![1, 2, 3]; + /// assert_eq!(a.len(), 3); + /// ``` pub fn len(&self) -> usize { self.header().len() } + + /// Returns `true` if the vector contains no elements. + /// + /// # Examples + /// + /// ``` + /// use thin_vec::ThinVec; + /// + /// let mut v = ThinVec::new(); + /// assert!(v.is_empty()); + /// + /// v.push(1); + /// assert!(!v.is_empty()); + /// ``` pub fn is_empty(&self) -> bool { self.len() == 0 } + + /// Returns the number of elements the vector can hold without + /// reallocating. + /// + /// # Examples + /// + /// ``` + /// use thin_vec::ThinVec; + /// + /// let vec: ThinVec<i32> = ThinVec::with_capacity(10); + /// assert_eq!(vec.capacity(), 10); + /// ``` pub fn capacity(&self) -> usize { self.header().cap() } + /// Forces the length of the vector to `new_len`. + /// + /// This is a low-level operation that maintains none of the normal + /// invariants of the type. Normally changing the length of a vector + /// is done using one of the safe operations instead, such as + /// [`truncate`], [`resize`], [`extend`], or [`clear`]. + /// + /// [`truncate`]: ThinVec::truncate + /// [`resize`]: ThinVec::resize + /// [`extend`]: ThinVec::extend + /// [`clear`]: ThinVec::clear + /// + /// # Safety + /// + /// - `new_len` must be less than or equal to [`capacity()`]. + /// - The elements at `old_len..new_len` must be initialized. + /// + /// [`capacity()`]: ThinVec::capacity + /// + /// # Examples + /// + /// This method can be useful for situations in which the vector + /// is serving as a buffer for other code, particularly over FFI: + /// + /// ```no_run + /// use thin_vec::ThinVec; + /// + /// # // This is just a minimal skeleton for the doc example; + /// # // don't use this as a starting point for a real library. + /// # pub struct StreamWrapper { strm: *mut std::ffi::c_void } + /// # const Z_OK: i32 = 0; + /// # extern "C" { + /// # fn deflateGetDictionary( + /// # strm: *mut std::ffi::c_void, + /// # dictionary: *mut u8, + /// # dictLength: *mut usize, + /// # ) -> i32; + /// # } + /// # impl StreamWrapper { + /// pub fn get_dictionary(&self) -> Option<ThinVec<u8>> { + /// // Per the FFI method's docs, "32768 bytes is always enough". + /// let mut dict = ThinVec::with_capacity(32_768); + /// let mut dict_length = 0; + /// // SAFETY: When `deflateGetDictionary` returns `Z_OK`, it holds that: + /// // 1. `dict_length` elements were initialized. + /// // 2. `dict_length` <= the capacity (32_768) + /// // which makes `set_len` safe to call. + /// unsafe { + /// // Make the FFI call... + /// let r = deflateGetDictionary(self.strm, dict.as_mut_ptr(), &mut dict_length); + /// if r == Z_OK { + /// // ...and update the length to what was initialized. + /// dict.set_len(dict_length); + /// Some(dict) + /// } else { + /// None + /// } + /// } + /// } + /// # } + /// ``` + /// + /// While the following example is sound, there is a memory leak since + /// the inner vectors were not freed prior to the `set_len` call: + /// + /// ```no_run + /// use thin_vec::thin_vec; + /// + /// let mut vec = thin_vec![thin_vec![1, 0, 0], + /// thin_vec![0, 1, 0], + /// thin_vec![0, 0, 1]]; + /// // SAFETY: + /// // 1. `old_len..0` is empty so no elements need to be initialized. + /// // 2. `0 <= capacity` always holds whatever `capacity` is. + /// unsafe { + /// vec.set_len(0); + /// } + /// ``` + /// + /// Normally, here, one would use [`clear`] instead to correctly drop + /// the contents and thus not leak memory. pub unsafe fn set_len(&mut self, len: usize) { if self.is_singleton() { // A prerequisite of `Vec::set_len` is that `new_len` must be @@ -550,6 +760,21 @@ impl<T> ThinVec<T> { self.header_mut().set_len(len) } + /// Appends an element to the back of a collection. + /// + /// # Panics + /// + /// Panics if the new capacity exceeds `isize::MAX` bytes. + /// + /// # Examples + /// + /// ``` + /// use thin_vec::thin_vec; + /// + /// let mut vec = thin_vec![1, 2]; + /// vec.push(3); + /// assert_eq!(vec, [1, 2, 3]); + /// ``` pub fn push(&mut self, val: T) { let old_len = self.len(); if old_len == self.capacity() { @@ -561,6 +786,18 @@ impl<T> ThinVec<T> { } } + /// Removes the last element from a vector and returns it, or [`None`] if it + /// is empty. + /// + /// # Examples + /// + /// ``` + /// use thin_vec::thin_vec; + /// + /// let mut vec = thin_vec![1, 2, 3]; + /// assert_eq!(vec.pop(), Some(3)); + /// assert_eq!(vec, [1, 2]); + /// ``` pub fn pop(&mut self) -> Option<T> { let old_len = self.len(); if old_len == 0 { @@ -573,6 +810,24 @@ impl<T> ThinVec<T> { } } + /// Inserts an element at position `index` within the vector, shifting all + /// elements after it to the right. + /// + /// # Panics + /// + /// Panics if `index > len`. + /// + /// # Examples + /// + /// ``` + /// use thin_vec::thin_vec; + /// + /// let mut vec = thin_vec![1, 2, 3]; + /// vec.insert(1, 4); + /// assert_eq!(vec, [1, 4, 2, 3]); + /// vec.insert(4, 5); + /// assert_eq!(vec, [1, 4, 2, 3, 5]); + /// ``` pub fn insert(&mut self, idx: usize, elem: T) { let old_len = self.len(); @@ -588,6 +843,29 @@ impl<T> ThinVec<T> { } } + /// Removes and returns the element at position `index` within the vector, + /// shifting all elements after it to the left. + /// + /// Note: Because this shifts over the remaining elements, it has a + /// worst-case performance of *O*(*n*). If you don't need the order of elements + /// to be preserved, use [`swap_remove`] instead. If you'd like to remove + /// elements from the beginning of the `ThinVec`, consider using `std::collections::VecDeque`. + /// + /// [`swap_remove`]: ThinVec::swap_remove + /// + /// # Panics + /// + /// Panics if `index` is out of bounds. + /// + /// # Examples + /// + /// ``` + /// use thin_vec::thin_vec; + /// + /// let mut v = thin_vec![1, 2, 3]; + /// assert_eq!(v.remove(1), 2); + /// assert_eq!(v, [1, 3]); + /// ``` pub fn remove(&mut self, idx: usize) -> T { let old_len = self.len(); @@ -602,6 +880,32 @@ impl<T> ThinVec<T> { } } + /// Removes an element from the vector and returns it. + /// + /// The removed element is replaced by the last element of the vector. + /// + /// This does not preserve ordering, but is *O*(1). + /// If you need to preserve the element order, use [`remove`] instead. + /// + /// [`remove`]: ThinVec::remove + /// + /// # Panics + /// + /// Panics if `index` is out of bounds. + /// + /// # Examples + /// + /// ``` + /// use thin_vec::thin_vec; + /// + /// let mut v = thin_vec!["foo", "bar", "baz", "qux"]; + /// + /// assert_eq!(v.swap_remove(1), "bar"); + /// assert_eq!(v, ["foo", "qux", "baz"]); + /// + /// assert_eq!(v.swap_remove(0), "foo"); + /// assert_eq!(v, ["baz", "qux"]); + /// ``` pub fn swap_remove(&mut self, idx: usize) -> T { let old_len = self.len(); @@ -615,6 +919,54 @@ impl<T> ThinVec<T> { } } + /// Shortens the vector, keeping the first `len` elements and dropping + /// the rest. + /// + /// If `len` is greater than the vector's current length, this has no + /// effect. + /// + /// The [`drain`] method can emulate `truncate`, but causes the excess + /// elements to be returned instead of dropped. + /// + /// Note that this method has no effect on the allocated capacity + /// of the vector. + /// + /// # Examples + /// + /// Truncating a five element vector to two elements: + /// + /// ``` + /// use thin_vec::thin_vec; + /// + /// let mut vec = thin_vec![1, 2, 3, 4, 5]; + /// vec.truncate(2); + /// assert_eq!(vec, [1, 2]); + /// ``` + /// + /// No truncation occurs when `len` is greater than the vector's current + /// length: + /// + /// ``` + /// use thin_vec::thin_vec; + /// + /// let mut vec = thin_vec![1, 2, 3]; + /// vec.truncate(8); + /// assert_eq!(vec, [1, 2, 3]); + /// ``` + /// + /// Truncating when `len == 0` is equivalent to calling the [`clear`] + /// method. + /// + /// ``` + /// use thin_vec::thin_vec; + /// + /// let mut vec = thin_vec![1, 2, 3]; + /// vec.truncate(0); + /// assert_eq!(vec, []); + /// ``` + /// + /// [`clear`]: ThinVec::clear + /// [`drain`]: ThinVec::drain pub fn truncate(&mut self, len: usize) { unsafe { // drop any extra elements @@ -628,6 +980,20 @@ impl<T> ThinVec<T> { } } + /// Clears the vector, removing all values. + /// + /// Note that this method has no effect on the allocated capacity + /// of the vector. + /// + /// # Examples + /// + /// ``` + /// use thin_vec::thin_vec; + /// + /// let mut v = thin_vec![1, 2, 3]; + /// v.clear(); + /// assert!(v.is_empty()); + /// ``` pub fn clear(&mut self) { unsafe { ptr::drop_in_place(&mut self[..]); @@ -635,10 +1001,34 @@ impl<T> ThinVec<T> { } } + /// Extracts a slice containing the entire vector. + /// + /// Equivalent to `&s[..]`. + /// + /// # Examples + /// + /// ``` + /// use thin_vec::thin_vec; + /// use std::io::{self, Write}; + /// let buffer = thin_vec![1, 2, 3, 5, 8]; + /// io::sink().write(buffer.as_slice()).unwrap(); + /// ``` pub fn as_slice(&self) -> &[T] { unsafe { slice::from_raw_parts(self.data_raw(), self.len()) } } + /// Extracts a mutable slice of the entire vector. + /// + /// Equivalent to `&mut s[..]`. + /// + /// # Examples + /// + /// ``` + /// use thin_vec::thin_vec; + /// use std::io::{self, Read}; + /// let mut buffer = vec![0; 3]; + /// io::repeat(0b101).read_exact(buffer.as_mut_slice()).unwrap(); + /// ``` pub fn as_mut_slice(&mut self) -> &mut [T] { unsafe { slice::from_raw_parts_mut(self.data_raw(), self.len()) } } @@ -751,6 +1141,22 @@ impl<T> ThinVec<T> { } } + /// Shrinks the capacity of the vector as much as possible. + /// + /// It will drop down as close as possible to the length but the allocator + /// may still inform the vector that there is space for a few more elements. + /// + /// # Examples + /// + /// ``` + /// use thin_vec::ThinVec; + /// + /// let mut vec = ThinVec::with_capacity(10); + /// vec.extend([1, 2, 3]); + /// assert_eq!(vec.capacity(), 10); + /// vec.shrink_to_fit(); + /// assert!(vec.capacity() >= 3); + /// ``` pub fn shrink_to_fit(&mut self) { let old_cap = self.capacity(); let new_cap = self.len(); @@ -915,6 +1321,26 @@ impl<T> ThinVec<T> { } } + /// Splits the collection into two at the given index. + /// + /// Returns a newly allocated vector containing the elements in the range + /// `[at, len)`. After the call, the original vector will be left containing + /// the elements `[0, at)` with its previous capacity unchanged. + /// + /// # Panics + /// + /// Panics if `at > len`. + /// + /// # Examples + /// + /// ``` + /// use thin_vec::thin_vec; + /// + /// let mut vec = thin_vec![1, 2, 3]; + /// let vec2 = vec.split_off(1); + /// assert_eq!(vec, [1]); + /// assert_eq!(vec2, [2, 3]); + /// ``` pub fn split_off(&mut self, at: usize) -> ThinVec<T> { let old_len = self.len(); let new_vec_len = old_len - at; @@ -933,14 +1359,64 @@ impl<T> ThinVec<T> { } } + /// Moves all the elements of `other` into `self`, leaving `other` empty. + /// + /// # Panics + /// + /// Panics if the new capacity exceeds `isize::MAX` bytes. + /// + /// # Examples + /// + /// ``` + /// use thin_vec::thin_vec; + /// + /// let mut vec = thin_vec![1, 2, 3]; + /// let mut vec2 = thin_vec![4, 5, 6]; + /// vec.append(&mut vec2); + /// assert_eq!(vec, [1, 2, 3, 4, 5, 6]); + /// assert_eq!(vec2, []); + /// ``` pub fn append(&mut self, other: &mut ThinVec<T>) { self.extend(other.drain(..)) } + /// Removes the specified range from the vector in bulk, returning all + /// removed elements as an iterator. If the iterator is dropped before + /// being fully consumed, it drops the remaining removed elements. + /// + /// The returned iterator keeps a mutable borrow on the vector to optimize + /// its implementation. + /// + /// # Panics + /// + /// Panics if the starting point is greater than the end point or if + /// the end point is greater than the length of the vector. + /// + /// # Leaking + /// + /// If the returned iterator goes out of scope without being dropped (due to + /// [`mem::forget`], for example), the vector may have lost and leaked + /// elements arbitrarily, including elements outside the range. + /// + /// # Examples + /// + /// ``` + /// use thin_vec::{ThinVec, thin_vec}; + /// + /// let mut v = thin_vec![1, 2, 3]; + /// let u: ThinVec<_> = v.drain(1..).collect(); + /// assert_eq!(v, &[1]); + /// assert_eq!(u, &[2, 3]); + /// + /// // A full range clears the vector, like `clear()` does + /// v.drain(..); + /// assert_eq!(v, &[]); + /// ``` pub fn drain<R>(&mut self, range: R) -> Drain<'_, T> where R: RangeBounds<usize>, { + // See comments in the Drain struct itself for details on this let len = self.len(); let start = match range.start_bound() { Bound::Included(&n) => n, @@ -971,6 +1447,53 @@ impl<T> ThinVec<T> { } } + /// Creates a splicing iterator that replaces the specified range in the vector + /// with the given `replace_with` iterator and yields the removed items. + /// `replace_with` does not need to be the same length as `range`. + /// + /// `range` is removed even if the iterator is not consumed until the end. + /// + /// It is unspecified how many elements are removed from the vector + /// if the `Splice` value is leaked. + /// + /// The input iterator `replace_with` is only consumed when the `Splice` value is dropped. + /// + /// This is optimal if: + /// + /// * The tail (elements in the vector after `range`) is empty, + /// * or `replace_with` yields fewer or equal elements than `range`’s length + /// * or the lower bound of its `size_hint()` is exact. + /// + /// Otherwise, a temporary vector is allocated and the tail is moved twice. + /// + /// # Panics + /// + /// Panics if the starting point is greater than the end point or if + /// the end point is greater than the length of the vector. + /// + /// # Examples + /// + /// ``` + /// use thin_vec::{ThinVec, thin_vec}; + /// + /// let mut v = thin_vec![1, 2, 3, 4]; + /// let new = [7, 8, 9]; + /// let u: ThinVec<_> = v.splice(1..3, new).collect(); + /// assert_eq!(v, &[1, 7, 8, 9, 4]); + /// assert_eq!(u, &[2, 3]); + /// ``` + #[inline] + pub fn splice<R, I>(&mut self, range: R, replace_with: I) -> Splice<'_, I::IntoIter> + where + R: RangeBounds<usize>, + I: IntoIterator<Item = T>, + { + Splice { + drain: self.drain(range), + replace_with: replace_with.into_iter(), + } + } + /// Resize the buffer and update its capacity, without changing the length. /// Unsafe because it can cause length to be greater than capacity. unsafe fn reallocate(&mut self, new_cap: usize) { @@ -1018,7 +1541,12 @@ impl<T> ThinVec<T> { #[cfg(feature = "gecko-ffi")] #[inline] + #[allow(unused_unsafe)] fn is_singleton(&self) -> bool { + // NOTE: the tests will complain that this "unsafe" isn't needed, but it *IS*! + // In production this refers to an *extern static* which *is* unsafe to reference. + // In tests this refers to a local static because we don't have Firefox's codebase + // providing the symbol! unsafe { self.ptr.as_ptr() as *const Header == &EMPTY_HEADER } } @@ -1082,6 +1610,27 @@ impl<T: Clone> ThinVec<T> { } } + /// Clones and appends all elements in a slice to the `ThinVec`. + /// + /// Iterates over the slice `other`, clones each element, and then appends + /// it to this `ThinVec`. The `other` slice is traversed in-order. + /// + /// Note that this function is same as [`extend`] except that it is + /// specialized to work with slices instead. If and when Rust gets + /// specialization this function will likely be deprecated (but still + /// available). + /// + /// # Examples + /// + /// ``` + /// use thin_vec::thin_vec; + /// + /// let mut vec = thin_vec![1]; + /// vec.extend_from_slice(&[2, 3, 4]); + /// assert_eq!(vec, [1, 2, 3, 4]); + /// ``` + /// + /// [`extend`]: ThinVec::extend pub fn extend_from_slice(&mut self, other: &[T]) { self.extend(other.iter().cloned()) } @@ -1415,16 +1964,256 @@ impl<T> FromIterator<T> for ThinVec<T> { } } +impl<T: Clone> From<&[T]> for ThinVec<T> { + /// Allocate a `ThinVec<T>` and fill it by cloning `s`'s items. + /// + /// # Examples + /// + /// ``` + /// use thin_vec::{ThinVec, thin_vec}; + /// + /// assert_eq!(ThinVec::from(&[1, 2, 3][..]), thin_vec![1, 2, 3]); + /// ``` + fn from(s: &[T]) -> ThinVec<T> { + s.iter().cloned().collect() + } +} + +#[cfg(not(no_global_oom_handling))] +impl<T: Clone> From<&mut [T]> for ThinVec<T> { + /// Allocate a `ThinVec<T>` and fill it by cloning `s`'s items. + /// + /// # Examples + /// + /// ``` + /// use thin_vec::{ThinVec, thin_vec}; + /// + /// assert_eq!(ThinVec::from(&mut [1, 2, 3][..]), thin_vec![1, 2, 3]); + /// ``` + fn from(s: &mut [T]) -> ThinVec<T> { + s.iter().cloned().collect() + } +} + +impl<T, const N: usize> From<[T; N]> for ThinVec<T> { + /// Allocate a `ThinVec<T>` and move `s`'s items into it. + /// + /// # Examples + /// + /// ``` + /// use thin_vec::{ThinVec, thin_vec}; + /// + /// assert_eq!(ThinVec::from([1, 2, 3]), thin_vec![1, 2, 3]); + /// ``` + fn from(s: [T; N]) -> ThinVec<T> { + std::iter::IntoIterator::into_iter(s).collect() + } +} + +impl<T> From<Box<[T]>> for ThinVec<T> { + /// Convert a boxed slice into a vector by transferring ownership of + /// the existing heap allocation. + /// + /// **NOTE:** unlike `std`, this must reallocate to change the layout! + /// + /// # Examples + /// + /// ``` + /// use thin_vec::{ThinVec, thin_vec}; + /// + /// let b: Box<[i32]> = thin_vec![1, 2, 3].into_iter().collect(); + /// assert_eq!(ThinVec::from(b), thin_vec![1, 2, 3]); + /// ``` + fn from(s: Box<[T]>) -> Self { + // Can just lean on the fact that `Box<[T]>` -> `Vec<T>` is Free. + Vec::from(s).into_iter().collect() + } +} + +impl<T> From<Vec<T>> for ThinVec<T> { + /// Convert a `std::Vec` into a `ThinVec`. + /// + /// **NOTE:** this must reallocate to change the layout! + /// + /// # Examples + /// + /// ``` + /// use thin_vec::{ThinVec, thin_vec}; + /// + /// let b: Vec<i32> = vec![1, 2, 3]; + /// assert_eq!(ThinVec::from(b), thin_vec![1, 2, 3]); + /// ``` + fn from(s: Vec<T>) -> Self { + s.into_iter().collect() + } +} + +impl<T> From<ThinVec<T>> for Vec<T> { + /// Convert a `ThinVec` into a `std::Vec`. + /// + /// **NOTE:** this must reallocate to change the layout! + /// + /// # Examples + /// + /// ``` + /// use thin_vec::{ThinVec, thin_vec}; + /// + /// let b: ThinVec<i32> = thin_vec![1, 2, 3]; + /// assert_eq!(Vec::from(b), vec![1, 2, 3]); + /// ``` + fn from(s: ThinVec<T>) -> Self { + s.into_iter().collect() + } +} + +impl<T> From<ThinVec<T>> for Box<[T]> { + /// Convert a vector into a boxed slice. + /// + /// If `v` has excess capacity, its items will be moved into a + /// newly-allocated buffer with exactly the right capacity. + /// + /// **NOTE:** unlike `std`, this must reallocate to change the layout! + /// + /// # Examples + /// + /// ``` + /// use thin_vec::{ThinVec, thin_vec}; + /// assert_eq!(Box::from(thin_vec![1, 2, 3]), thin_vec![1, 2, 3].into_iter().collect()); + /// ``` + fn from(v: ThinVec<T>) -> Self { + v.into_iter().collect() + } +} + +impl From<&str> for ThinVec<u8> { + /// Allocate a `ThinVec<u8>` and fill it with a UTF-8 string. + /// + /// # Examples + /// + /// ``` + /// use thin_vec::{ThinVec, thin_vec}; + /// + /// assert_eq!(ThinVec::from("123"), thin_vec![b'1', b'2', b'3']); + /// ``` + fn from(s: &str) -> ThinVec<u8> { + From::from(s.as_bytes()) + } +} + +impl<T, const N: usize> TryFrom<ThinVec<T>> for [T; N] { + type Error = ThinVec<T>; + + /// Gets the entire contents of the `ThinVec<T>` as an array, + /// if its size exactly matches that of the requested array. + /// + /// # Examples + /// + /// ``` + /// use thin_vec::{ThinVec, thin_vec}; + /// use std::convert::TryInto; + /// + /// assert_eq!(thin_vec![1, 2, 3].try_into(), Ok([1, 2, 3])); + /// assert_eq!(<ThinVec<i32>>::new().try_into(), Ok([])); + /// ``` + /// + /// If the length doesn't match, the input comes back in `Err`: + /// ``` + /// use thin_vec::{ThinVec, thin_vec}; + /// use std::convert::TryInto; + /// + /// let r: Result<[i32; 4], _> = (0..10).collect::<ThinVec<_>>().try_into(); + /// assert_eq!(r, Err(thin_vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9])); + /// ``` + /// + /// If you're fine with just getting a prefix of the `ThinVec<T>`, + /// you can call [`.truncate(N)`](ThinVec::truncate) first. + /// ``` + /// use thin_vec::{ThinVec, thin_vec}; + /// use std::convert::TryInto; + /// + /// let mut v = ThinVec::from("hello world"); + /// v.sort(); + /// v.truncate(2); + /// let [a, b]: [_; 2] = v.try_into().unwrap(); + /// assert_eq!(a, b' '); + /// assert_eq!(b, b'd'); + /// ``` + fn try_from(mut vec: ThinVec<T>) -> Result<[T; N], ThinVec<T>> { + if vec.len() != N { + return Err(vec); + } + + // SAFETY: `.set_len(0)` is always sound. + unsafe { vec.set_len(0) }; + + // SAFETY: A `ThinVec`'s pointer is always aligned properly, and + // the alignment the array needs is the same as the items. + // We checked earlier that we have sufficient items. + // The items will not double-drop as the `set_len` + // tells the `ThinVec` not to also drop them. + let array = unsafe { ptr::read(vec.data_raw() as *const [T; N]) }; + Ok(array) + } +} + +/// An iterator that moves out of a vector. +/// +/// This `struct` is created by the [`ThinVec::into_iter`][] +/// (provided by the [`IntoIterator`] trait). +/// +/// # Example +/// +/// ``` +/// use thin_vec::thin_vec; +/// +/// let v = thin_vec![0, 1, 2]; +/// let iter: thin_vec::IntoIter<_> = v.into_iter(); +/// ``` pub struct IntoIter<T> { vec: ThinVec<T>, start: usize, } -pub struct Drain<'a, T> { - iter: IterMut<'a, T>, - vec: *mut ThinVec<T>, - end: usize, - tail: usize, +impl<T> IntoIter<T> { + /// Returns the remaining items of this iterator as a slice. + /// + /// # Examples + /// + /// ``` + /// use thin_vec::thin_vec; + /// + /// let vec = thin_vec!['a', 'b', 'c']; + /// let mut into_iter = vec.into_iter(); + /// assert_eq!(into_iter.as_slice(), &['a', 'b', 'c']); + /// let _ = into_iter.next().unwrap(); + /// assert_eq!(into_iter.as_slice(), &['b', 'c']); + /// ``` + pub fn as_slice(&self) -> &[T] { + unsafe { slice::from_raw_parts(self.vec.data_raw().add(self.start), self.len()) } + } + + /// Returns the remaining items of this iterator as a mutable slice. + /// + /// # Examples + /// + /// ``` + /// use thin_vec::thin_vec; + /// + /// let vec = thin_vec!['a', 'b', 'c']; + /// let mut into_iter = vec.into_iter(); + /// assert_eq!(into_iter.as_slice(), &['a', 'b', 'c']); + /// into_iter.as_mut_slice()[2] = 'z'; + /// assert_eq!(into_iter.next().unwrap(), 'a'); + /// assert_eq!(into_iter.next().unwrap(), 'b'); + /// assert_eq!(into_iter.next().unwrap(), 'z'); + /// ``` + pub fn as_mut_slice(&mut self) -> &mut [T] { + unsafe { &mut *self.as_raw_mut_slice() } + } + + fn as_raw_mut_slice(&mut self) -> *mut [T] { + unsafe { ptr::slice_from_raw_parts_mut(self.vec.data_raw().add(self.start), self.len()) } + } } impl<T> Iterator for IntoIter<T> { @@ -1452,12 +2241,19 @@ impl<T> DoubleEndedIterator for IntoIter<T> { if self.start == self.vec.len() { None } else { - // FIXME?: extra bounds check self.vec.pop() } } } +impl<T> ExactSizeIterator for IntoIter<T> {} + +impl<T> std::iter::FusedIterator for IntoIter<T> {} + +// SAFETY: the length calculation is trivial, we're an array! And if it's wrong we're So Screwed. +#[cfg(feature = "unstable")] +unsafe impl<T> std::iter::TrustedLen for IntoIter<T> {} + impl<T> Drop for IntoIter<T> { #[inline] fn drop(&mut self) { @@ -1477,6 +2273,126 @@ impl<T> Drop for IntoIter<T> { } } +impl<T: fmt::Debug> fmt::Debug for IntoIter<T> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_tuple("IntoIter").field(&self.as_slice()).finish() + } +} + +impl<T> AsRef<[T]> for IntoIter<T> { + fn as_ref(&self) -> &[T] { + self.as_slice() + } +} + +impl<T: Clone> Clone for IntoIter<T> { + #[allow(clippy::into_iter_on_ref)] + fn clone(&self) -> Self { + // Just create a new `ThinVec` from the remaining elements and IntoIter it + self.as_slice() + .into_iter() + .cloned() + .collect::<ThinVec<_>>() + .into_iter() + } +} + +/// A draining iterator for `ThinVec<T>`. +/// +/// This `struct` is created by [`ThinVec::drain`]. +/// See its documentation for more. +/// +/// # Example +/// +/// ``` +/// use thin_vec::thin_vec; +/// +/// let mut v = thin_vec![0, 1, 2]; +/// let iter: thin_vec::Drain<_> = v.drain(..); +/// ``` +pub struct Drain<'a, T> { + // Ok so ThinVec::drain takes a range of the ThinVec and yields the contents by-value, + // then backshifts the array. During iteration the array is in an unsound state + // (big deinitialized hole in it), and this is very dangerous. + // + // Our first line of defense is the borrow checker: we have a mutable borrow, so nothing + // can access the ThinVec while we exist. As long as we make sure the ThinVec is in a valid + // state again before we release the borrow, everything should be A-OK! We do this cleanup + // in our Drop impl. + // + // Unfortunately, that's unsound, because mem::forget exists and The Leakpocalypse Is Real. + // So we can't actually guarantee our destructor runs before our borrow expires. Thankfully + // this isn't fatal: we can just set the ThinVec's len to 0 at the start, so if anyone + // leaks the Drain, we just leak everything the ThinVec contained out of spite! If they + // *don't* leak us then we can properly repair the len in our Drop impl. This is known + // as "leak amplification", and is the same approach std uses. + // + // But we can do slightly better than setting the len to 0! The drain breaks us up into + // these parts: + // + // ```text + // + // [A, B, C, D, E, F, G, H, _, _] + // ____ __________ ____ ____ + // | | | | + // prefix drain tail spare-cap + // ``` + // + // As the drain iterator is consumed from both ends (DoubleEnded!), we'll start to look + // like this: + // + // ```text + // [A, B, _, _, E, _, G, H, _, _] + // ____ __________ ____ ____ + // | | | | + // prefix drain tail spare-cap + // ``` + // + // Note that the prefix is always valid and untouched, as such we can set the len + // to the prefix when doing leak-amplification. As a bonus, we can use this value + // to remember where the drain range starts. At the end we'll look like this + // (we exhaust ourselves in our Drop impl): + // + // ```text + // [A, B, _, _, _, _, G, H, _, _] + // _____ __________ _____ ____ + // | | | | + // len drain tail spare-cap + // ``` + // + // And need to become this: + // + // ```text + // [A, B, G, H, _, _, _, _, _, _] + // ___________ ________________ + // | | + // len spare-cap + // ``` + // + // All this requires is moving the tail back to the prefix (stored in `len`) + // and setting `len` to `len + tail_len` to undo the leak amplification. + /// An iterator over the elements we're removing. + /// + /// As we go we'll be `read`ing out of the mutable refs yielded by this. + /// It's ok to use IterMut here because it promises to only take mutable + /// refs to the parts we haven't yielded yet. + /// + /// A downside of this (and the *mut below) is that it makes this type invariant, when + /// technically it could be covariant? + iter: IterMut<'a, T>, + /// The actual ThinVec, which we need to hold onto to undo the leak amplification + /// and backshift the tail into place. This should only be accessed when we're + /// completely done with the IterMut in the `drop` impl of this type (or miri will get mad). + /// + /// Since we set the `len` of this to be before `IterMut`, we can use that `len` + /// to retrieve the index of the start of the drain range later. + vec: *mut ThinVec<T>, + /// The one-past-the-end index of the drain range, or equivalently the start of the tail. + end: usize, + /// The length of the tail. + tail: usize, +} + impl<'a, T> Iterator for Drain<'a, T> { type Item = T; fn next(&mut self) -> Option<T> { @@ -1496,6 +2412,12 @@ impl<'a, T> DoubleEndedIterator for Drain<'a, T> { impl<'a, T> ExactSizeIterator for Drain<'a, T> {} +// SAFETY: we need to keep track of this perfectly Or Else anyway! +#[cfg(feature = "unstable")] +unsafe impl<T> std::iter::TrustedLen for Drain<'_, T> {} + +impl<T> std::iter::FusedIterator for Drain<'_, T> {} + impl<'a, T> Drop for Drain<'a, T> { fn drop(&mut self) { // Consume the rest of the iterator. @@ -1517,6 +2439,167 @@ impl<'a, T> Drop for Drain<'a, T> { } } +impl<T: fmt::Debug> fmt::Debug for Drain<'_, T> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_tuple("Drain").field(&self.iter.as_slice()).finish() + } +} + +impl<'a, T> Drain<'a, T> { + /// Returns the remaining items of this iterator as a slice. + /// + /// # Examples + /// + /// ``` + /// use thin_vec::thin_vec; + /// + /// let mut vec = thin_vec!['a', 'b', 'c']; + /// let mut drain = vec.drain(..); + /// assert_eq!(drain.as_slice(), &['a', 'b', 'c']); + /// let _ = drain.next().unwrap(); + /// assert_eq!(drain.as_slice(), &['b', 'c']); + /// ``` + #[must_use] + pub fn as_slice(&self) -> &[T] { + // SAFETY: this is A-OK because the elements that the underlying + // iterator still points at are still logically initialized and contiguous. + self.iter.as_slice() + } +} + +impl<'a, T> AsRef<[T]> for Drain<'a, T> { + fn as_ref(&self) -> &[T] { + self.as_slice() + } +} + +/// A splicing iterator for `ThinVec`. +/// +/// This struct is created by [`ThinVec::splice`][]. +/// See its documentation for more. +/// +/// # Example +/// +/// ``` +/// use thin_vec::thin_vec; +/// +/// let mut v = thin_vec![0, 1, 2]; +/// let new = [7, 8]; +/// let iter: thin_vec::Splice<_> = v.splice(1.., new); +/// ``` +#[derive(Debug)] +pub struct Splice<'a, I: Iterator + 'a> { + drain: Drain<'a, I::Item>, + replace_with: I, +} + +impl<I: Iterator> Iterator for Splice<'_, I> { + type Item = I::Item; + + fn next(&mut self) -> Option<Self::Item> { + self.drain.next() + } + + fn size_hint(&self) -> (usize, Option<usize>) { + self.drain.size_hint() + } +} + +impl<I: Iterator> DoubleEndedIterator for Splice<'_, I> { + fn next_back(&mut self) -> Option<Self::Item> { + self.drain.next_back() + } +} + +impl<I: Iterator> ExactSizeIterator for Splice<'_, I> {} + +impl<I: Iterator> Drop for Splice<'_, I> { + fn drop(&mut self) { + // Ensure we've fully drained out the range + self.drain.by_ref().for_each(drop); + + unsafe { + // If there's no tail elements, then the inner ThinVec is already + // correct and we can just extend it like normal. + if self.drain.tail == 0 { + (*self.drain.vec).extend(self.replace_with.by_ref()); + return; + } + + // First fill the range left by drain(). + if !self.drain.fill(&mut self.replace_with) { + return; + } + + // There may be more elements. Use the lower bound as an estimate. + let (lower_bound, _upper_bound) = self.replace_with.size_hint(); + if lower_bound > 0 { + self.drain.move_tail(lower_bound); + if !self.drain.fill(&mut self.replace_with) { + return; + } + } + + // Collect any remaining elements. + // This is a zero-length vector which does not allocate if `lower_bound` was exact. + let mut collected = self + .replace_with + .by_ref() + .collect::<Vec<I::Item>>() + .into_iter(); + // Now we have an exact count. + if collected.len() > 0 { + self.drain.move_tail(collected.len()); + let filled = self.drain.fill(&mut collected); + debug_assert!(filled); + debug_assert_eq!(collected.len(), 0); + } + } + // Let `Drain::drop` move the tail back if necessary and restore `vec.len`. + } +} + +/// Private helper methods for `Splice::drop` +impl<T> Drain<'_, T> { + /// The range from `self.vec.len` to `self.tail_start` contains elements + /// that have been moved out. + /// Fill that range as much as possible with new elements from the `replace_with` iterator. + /// Returns `true` if we filled the entire range. (`replace_with.next()` didn’t return `None`.) + unsafe fn fill<I: Iterator<Item = T>>(&mut self, replace_with: &mut I) -> bool { + let vec = unsafe { &mut *self.vec }; + let range_start = vec.len(); + let range_end = self.end; + let range_slice = unsafe { + slice::from_raw_parts_mut(vec.data_raw().add(range_start), range_end - range_start) + }; + + for place in range_slice { + if let Some(new_item) = replace_with.next() { + unsafe { ptr::write(place, new_item) }; + vec.set_len(vec.len() + 1); + } else { + return false; + } + } + true + } + + /// Makes room for inserting more elements before the tail. + unsafe fn move_tail(&mut self, additional: usize) { + let vec = unsafe { &mut *self.vec }; + let len = self.end + self.tail; + vec.reserve(len.checked_add(additional).expect("capacity overflow")); + + let new_tail_start = self.end + additional; + unsafe { + let src = vec.data_raw().add(self.end); + let dst = vec.data_raw().add(new_tail_start); + ptr::copy(src, dst, self.tail); + } + self.end = new_tail_start; + } +} + /// Write is implemented for `ThinVec<u8>` by appending to the vector. /// The vector will grow as needed. /// This implementation is identical to the one for `Vec<u8>`. @@ -1755,6 +2838,19 @@ mod tests { { let mut v = ThinVec::<i32>::new(); + assert_eq!(v.splice(.., []).len(), 0); + + for _ in v.splice(.., []) { + unreachable!() + } + + assert_eq!(v.len(), 0); + assert_eq!(v.capacity(), 0); + assert_eq!(&v[..], &[]); + } + + { + let mut v = ThinVec::<i32>::new(); v.truncate(1); assert_eq!(v.len(), 0); assert_eq!(v.capacity(), 0); @@ -2507,70 +3603,76 @@ mod std_tests { v.drain(5..=5); } - /* TODO: implement splice? - #[test] - fn test_splice() { - let mut v = thin_vec![1, 2, 3, 4, 5]; - let a = [10, 11, 12]; - v.splice(2..4, a.iter().cloned()); - assert_eq!(v, &[1, 2, 10, 11, 12, 5]); - v.splice(1..3, Some(20)); - assert_eq!(v, &[1, 20, 11, 12, 5]); - } + #[test] + fn test_splice() { + let mut v = thin_vec![1, 2, 3, 4, 5]; + let a = [10, 11, 12]; + v.splice(2..4, a.iter().cloned()); + assert_eq!(v, &[1, 2, 10, 11, 12, 5]); + v.splice(1..3, Some(20)); + assert_eq!(v, &[1, 20, 11, 12, 5]); + } - #[test] - fn test_splice_inclusive_range() { - let mut v = thin_vec![1, 2, 3, 4, 5]; - let a = [10, 11, 12]; - let t1: ThinVec<_> = v.splice(2..=3, a.iter().cloned()).collect(); - assert_eq!(v, &[1, 2, 10, 11, 12, 5]); - assert_eq!(t1, &[3, 4]); - let t2: ThinVec<_> = v.splice(1..=2, Some(20)).collect(); - assert_eq!(v, &[1, 20, 11, 12, 5]); - assert_eq!(t2, &[2, 10]); - } + #[test] + fn test_splice_inclusive_range() { + let mut v = thin_vec![1, 2, 3, 4, 5]; + let a = [10, 11, 12]; + let t1: ThinVec<_> = v.splice(2..=3, a.iter().cloned()).collect(); + assert_eq!(v, &[1, 2, 10, 11, 12, 5]); + assert_eq!(t1, &[3, 4]); + let t2: ThinVec<_> = v.splice(1..=2, Some(20)).collect(); + assert_eq!(v, &[1, 20, 11, 12, 5]); + assert_eq!(t2, &[2, 10]); + } - #[test] - #[should_panic] - fn test_splice_out_of_bounds() { - let mut v = thin_vec![1, 2, 3, 4, 5]; - let a = [10, 11, 12]; - v.splice(5..6, a.iter().cloned()); - } + #[test] + #[should_panic] + fn test_splice_out_of_bounds() { + let mut v = thin_vec![1, 2, 3, 4, 5]; + let a = [10, 11, 12]; + v.splice(5..6, a.iter().cloned()); + } - #[test] - #[should_panic] - fn test_splice_inclusive_out_of_bounds() { - let mut v = thin_vec![1, 2, 3, 4, 5]; - let a = [10, 11, 12]; - v.splice(5..=5, a.iter().cloned()); - } + #[test] + #[should_panic] + fn test_splice_inclusive_out_of_bounds() { + let mut v = thin_vec![1, 2, 3, 4, 5]; + let a = [10, 11, 12]; + v.splice(5..=5, a.iter().cloned()); + } - #[test] - fn test_splice_items_zero_sized() { - let mut vec = thin_vec![(), (), ()]; - let vec2 = thin_vec![]; - let t: ThinVec<_> = vec.splice(1..2, vec2.iter().cloned()).collect(); - assert_eq!(vec, &[(), ()]); - assert_eq!(t, &[()]); - } + #[test] + fn test_splice_items_zero_sized() { + let mut vec = thin_vec![(), (), ()]; + let vec2 = thin_vec![]; + let t: ThinVec<_> = vec.splice(1..2, vec2.iter().cloned()).collect(); + assert_eq!(vec, &[(), ()]); + assert_eq!(t, &[()]); + } - #[test] - fn test_splice_unbounded() { - let mut vec = thin_vec![1, 2, 3, 4, 5]; - let t: ThinVec<_> = vec.splice(.., None).collect(); - assert_eq!(vec, &[]); - assert_eq!(t, &[1, 2, 3, 4, 5]); - } + #[test] + fn test_splice_unbounded() { + let mut vec = thin_vec![1, 2, 3, 4, 5]; + let t: ThinVec<_> = vec.splice(.., None).collect(); + assert_eq!(vec, &[]); + assert_eq!(t, &[1, 2, 3, 4, 5]); + } - #[test] - fn test_splice_forget() { - let mut v = thin_vec![1, 2, 3, 4, 5]; - let a = [10, 11, 12]; - ::std::mem::forget(v.splice(2..4, a.iter().cloned())); - assert_eq!(v, &[1, 2]); - } - */ + #[test] + fn test_splice_forget() { + let mut v = thin_vec![1, 2, 3, 4, 5]; + let a = [10, 11, 12]; + ::std::mem::forget(v.splice(2..4, a.iter().cloned())); + assert_eq!(v, &[1, 2]); + } + + #[test] + fn test_splice_from_empty() { + let mut v = thin_vec![]; + let a = [10, 11, 12]; + v.splice(.., a.iter().cloned()); + assert_eq!(v, &[10, 11, 12]); + } /* probs won't ever impl this #[test] @@ -2598,81 +3700,59 @@ mod std_tests { assert_eq!(vec2, [5, 6]); } - /* TODO: implement into_iter methods? - #[test] - fn test_into_iter_as_slice() { - let vec = thin_vec!['a', 'b', 'c']; - let mut into_iter = vec.into_iter(); - assert_eq!(into_iter.as_slice(), &['a', 'b', 'c']); - let _ = into_iter.next().unwrap(); - assert_eq!(into_iter.as_slice(), &['b', 'c']); - let _ = into_iter.next().unwrap(); - let _ = into_iter.next().unwrap(); - assert_eq!(into_iter.as_slice(), &[]); - } - - #[test] - fn test_into_iter_as_mut_slice() { - let vec = thin_vec!['a', 'b', 'c']; - let mut into_iter = vec.into_iter(); - assert_eq!(into_iter.as_slice(), &['a', 'b', 'c']); - into_iter.as_mut_slice()[0] = 'x'; - into_iter.as_mut_slice()[1] = 'y'; - assert_eq!(into_iter.next().unwrap(), 'x'); - assert_eq!(into_iter.as_slice(), &['y', 'c']); - } - - #[test] - fn test_into_iter_debug() { - let vec = thin_vec!['a', 'b', 'c']; - let into_iter = vec.into_iter(); - let debug = format!("{:?}", into_iter); - assert_eq!(debug, "IntoIter(['a', 'b', 'c'])"); - } + #[test] + fn test_into_iter_as_slice() { + let vec = thin_vec!['a', 'b', 'c']; + let mut into_iter = vec.into_iter(); + assert_eq!(into_iter.as_slice(), &['a', 'b', 'c']); + let _ = into_iter.next().unwrap(); + assert_eq!(into_iter.as_slice(), &['b', 'c']); + let _ = into_iter.next().unwrap(); + let _ = into_iter.next().unwrap(); + assert_eq!(into_iter.as_slice(), &[]); + } - #[test] - fn test_into_iter_count() { - assert_eq!(thin_vec![1, 2, 3].into_iter().count(), 3); - } + #[test] + fn test_into_iter_as_mut_slice() { + let vec = thin_vec!['a', 'b', 'c']; + let mut into_iter = vec.into_iter(); + assert_eq!(into_iter.as_slice(), &['a', 'b', 'c']); + into_iter.as_mut_slice()[0] = 'x'; + into_iter.as_mut_slice()[1] = 'y'; + assert_eq!(into_iter.next().unwrap(), 'x'); + assert_eq!(into_iter.as_slice(), &['y', 'c']); + } - #[test] - fn test_into_iter_clone() { - fn iter_equal<I: Iterator<Item = i32>>(it: I, slice: &[i32]) { - let v: ThinVec<i32> = it.collect(); - assert_eq!(&v[..], slice); - } - let mut it = thin_vec![1, 2, 3].into_iter(); - iter_equal(it.clone(), &[1, 2, 3]); - assert_eq!(it.next(), Some(1)); - let mut it = it.rev(); - iter_equal(it.clone(), &[3, 2]); - assert_eq!(it.next(), Some(3)); - iter_equal(it.clone(), &[2]); - assert_eq!(it.next(), Some(2)); - iter_equal(it.clone(), &[]); - assert_eq!(it.next(), None); - } - */ + #[test] + fn test_into_iter_debug() { + let vec = thin_vec!['a', 'b', 'c']; + let into_iter = vec.into_iter(); + let debug = format!("{:?}", into_iter); + assert_eq!(debug, "IntoIter(['a', 'b', 'c'])"); + } - /* TODO: implement CoW interop? - #[test] - fn test_cow_from() { - let borrowed: &[_] = &["borrowed", "(slice)"]; - let owned = thin_vec!["owned", "(vec)"]; - match (Cow::from(owned.clone()), Cow::from(borrowed)) { - (Cow::Owned(o), Cow::Borrowed(b)) => assert!(o == owned && b == borrowed), - _ => panic!("invalid `Cow::from`"), - } - } + #[test] + fn test_into_iter_count() { + assert_eq!(thin_vec![1, 2, 3].into_iter().count(), 3); + } - #[test] - fn test_from_cow() { - let borrowed: &[_] = &["borrowed", "(slice)"]; - let owned = thin_vec!["owned", "(vec)"]; - assert_eq!(ThinVec::from(Cow::Borrowed(borrowed)), thin_vec!["borrowed", "(slice)"]); - assert_eq!(ThinVec::from(Cow::Owned(owned)), thin_vec!["owned", "(vec)"]); + #[test] + fn test_into_iter_clone() { + fn iter_equal<I: Iterator<Item = i32>>(it: I, slice: &[i32]) { + let v: ThinVec<i32> = it.collect(); + assert_eq!(&v[..], slice); } - */ + let mut it = thin_vec![1, 2, 3].into_iter(); + iter_equal(it.clone(), &[1, 2, 3]); + assert_eq!(it.next(), Some(1)); + let mut it = it.rev(); + iter_equal(it.clone(), &[3, 2]); + assert_eq!(it.next(), Some(3)); + iter_equal(it.clone(), &[2]); + assert_eq!(it.next(), Some(2)); + iter_equal(it.clone(), &[]); + assert_eq!(it.next(), None); + } /* TODO: make drain covariant #[allow(dead_code)] @@ -2704,22 +3784,21 @@ mod std_tests { } */ - /* TODO: implement higher than 16 alignment - #[test] - fn overaligned_allocations() { - #[repr(align(256))] - struct Foo(usize); - let mut v = thin_vec![Foo(273)]; - for i in 0..0x1000 { - v.reserve_exact(i); - assert!(v[0].0 == 273); - assert!(v.as_ptr() as usize & 0xff == 0); - v.shrink_to_fit(); - assert!(v[0].0 == 273); - assert!(v.as_ptr() as usize & 0xff == 0); - } + #[test] + #[cfg_attr(feature = "gecko-ffi", ignore)] + fn overaligned_allocations() { + #[repr(align(256))] + struct Foo(usize); + let mut v = thin_vec![Foo(273)]; + for i in 0..0x1000 { + v.reserve_exact(i); + assert!(v[0].0 == 273); + assert!(v.as_ptr() as usize & 0xff == 0); + v.shrink_to_fit(); + assert!(v[0].0 == 273); + assert!(v.as_ptr() as usize & 0xff == 0); } - */ + } /* TODO: implement drain_filter? #[test] @@ -3175,4 +4254,35 @@ mod std_tests { vec.set_len(1); } } + + #[test] + #[should_panic(expected = "capacity overflow")] + fn test_capacity_overflow_header_too_big() { + let vec: ThinVec<u8> = ThinVec::with_capacity(isize::MAX as usize - 2); + assert!(vec.capacity() > 0); + } + #[test] + #[should_panic(expected = "capacity overflow")] + fn test_capacity_overflow_cap_too_big() { + let vec: ThinVec<u8> = ThinVec::with_capacity(isize::MAX as usize + 1); + assert!(vec.capacity() > 0); + } + #[test] + #[should_panic(expected = "capacity overflow")] + fn test_capacity_overflow_size_mul1() { + let vec: ThinVec<u16> = ThinVec::with_capacity(isize::MAX as usize + 1); + assert!(vec.capacity() > 0); + } + #[test] + #[should_panic(expected = "capacity overflow")] + fn test_capacity_overflow_size_mul2() { + let vec: ThinVec<u16> = ThinVec::with_capacity(isize::MAX as usize / 2 + 1); + assert!(vec.capacity() > 0); + } + #[test] + #[should_panic(expected = "capacity overflow")] + fn test_capacity_overflow_cap_really_isnt_isize() { + let vec: ThinVec<u8> = ThinVec::with_capacity(isize::MAX as usize); + assert!(vec.capacity() > 0); + } } |