summaryrefslogtreecommitdiffstats
path: root/vendor/thin-vec
diff options
context:
space:
mode:
Diffstat (limited to 'vendor/thin-vec')
-rw-r--r--vendor/thin-vec/.cargo-checksum.json2
-rw-r--r--vendor/thin-vec/Cargo.toml2
-rw-r--r--vendor/thin-vec/src/lib.rs1458
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);
+ }
}