lib.rs source code [crates/thin_vec/src/lib.rs]

1	#![deny(missing_docs)]
2
3	//! `ThinVec` is exactly the same as `Vec`, except that it stores its `len` and `capacity` in the buffer
4	//! it allocates.
5	//!
6	//! This makes the memory footprint of ThinVecs lower; notably in cases where space is reserved for
7	//! a non-existence `ThinVec<T>`. So `Vec<ThinVec<T>>` and `Option<ThinVec<T>>::None` will waste less
8	//! space. Being pointer-sized also means it can be passed/stored in registers.
9	//!
10	//! Of course, any actually constructed `ThinVec` will theoretically have a bigger allocation, but
11	//! the fuzzy nature of allocators means that might not actually be the case.
12	//!
13	//! Properties of `Vec` that are preserved:
14	//! `ThinVec::new()` doesn't allocate (it points to a statically allocated singleton)*
15	//! reallocation can be done in place*
16	//! `size_of::<ThinVec<T>>()` == `size_of::<Option<ThinVec<T>>>()`*
17	//!
18	//! Properties of `Vec` that aren't preserved:
19	//! `ThinVec<T>` can't ever be zero-cost roundtripped to a `Box<[T]>`, `String`, or `mut T`
20	//! `from_raw_parts` doesn't exist*
21	//! `ThinVec` currently doesn't bother to not-allocate for Zero Sized Types (e.g. `ThinVec<()>`),*
22	//! but it could be done if someone cared enough to implement it.
23	//!
24	//!
25	//!
26	//! # Gecko FFI
27	//!
28	//! If you enable the gecko-ffi feature, `ThinVec` will verbatim bridge with the nsTArray type in
29	//! Gecko (Firefox). That is, `ThinVec` and nsTArray have identical layouts but not ABIs,
30	//! so nsTArrays/ThinVecs an be natively manipulated by C++ and Rust, and ownership can be
31	//! transferred across the FFI boundary (IF YOU ARE CAREFUL, SEE BELOW!!).
32	//!
33	//! While this feature is handy, it is also inherently dangerous to use because Rust and C++ do not
34	//! know about each other. Specifically, this can be an issue with non-POD types (types which
35	//! have destructors, move constructors, or are `!Copy`).
36	//!
37	//! ## Do Not Pass By Value
38	//!
39	//! The biggest thing to keep in mind is that FFI functions cannot pass ThinVec/nsTArray
40	//! by-value. That is, these are busted APIs:
41	//!
42	//! ```rust,ignore
43	//! // BAD WRONG
44	//! extern fn process_data(data: ThinVec<u32>) { ... }
45	//! // BAD WRONG
46	//! extern fn get_data() -> ThinVec<u32> { ... }
47	//! ```
48	//!
49	//! You must instead pass by-reference:
50	//!
51	//! ```rust
52	//! # use thin_vec::*;
53	//! # use std::mem;
54	//!
55	//! // Read-only access, ok!
56	//! extern fn process_data(data: &ThinVec<u32>) {
57	//! for val in data {
58	//! println!("{}", val);
59	//! }
60	//! }
61	//!
62	//! // Replace with empty instance to take ownership, ok!
63	//! extern fn consume_data(data: &mut ThinVec<u32>) {
64	//! let owned = mem::replace(data, ThinVec::new());
65	//! mem::drop(owned);
66	//! }
67	//!
68	//! // Mutate input, ok!
69	//! extern fn add_data(dataset: &mut ThinVec<u32>) {
70	//! dataset.push(`37`);
71	//! dataset.push(`12`);
72	//! }
73	//!
74	//! // Return via out-param, usually ok!
75	//! //
76	//! // WARNING: output must be initialized! (Empty nsTArrays are free, so just do it!)
77	//! extern fn get_data(output: &mut ThinVec<u32>) {
78	//! *output = thin_vec![`1`, `2`, `3`, `4`, `5`];
79	//! }
80	//! ```
81	//!
82	//! Ignorable Explanation For Those Who Really Want To Know Why:
83	//!
84	//! > The fundamental issue is that Rust and C++ can't currently communicate about destructors, and
85	//! > the semantics of C++ require destructors of function arguments to be run when the function
86	//! > returns. Whether the callee or caller is responsible for this is also platform-specific, so
87	//! > trying to hack around it manually would be messy.
88	//! >
89	//! > Also a type having a destructor changes its C++ ABI, because that type must actually exist
90	//! > in memory (unlike a trivial struct, which is often passed in registers). We don't currently
91	//! > have a way to communicate to Rust that this is happening, so even if we worked out the
92	//! > destructor issue with say, MaybeUninit, it would still be a non-starter without some RFCs
93	//! > to add explicit rustc support.
94	//! >
95	//! > Realistically, the best answer here is to have a "heavier" bindgen that can secretly
96	//! > generate FFI glue so we can pass things "by value" and have it generate by-reference code
97	//! > behind our back (like the cxx crate does). This would muddy up debugging/searchfox though.
98	//!
99	//! ## Types Should Be Trivially Relocatable
100	//!
101	//! Types in Rust are always trivially relocatable (unless suitably borrowed/[pinned][]/hidden).
102	//! This means all Rust types are legal to relocate with a bitwise copy, you cannot provide
103	//! copy or move constructors to execute when this happens, and the old location won't have its
104	//! destructor run. This will cause problems for types which have a significant location
105	//! (types that intrusively point into themselves or have their location registered with a service).
106	//!
107	//! While relocations are generally predictable if you're very careful, you should avoid using
108	//! types with significant locations with Rust FFI.
109	//!
110	//! Specifically, `ThinVec` will trivially relocate its contents whenever it needs to reallocate its
111	//! buffer to change its capacity. This is the default reallocation strategy for nsTArray, and is
112	//! suitable for the vast majority of types. Just be aware of this limitation!
113	//!
114	//! ## Auto Arrays Are Dangerous
115	//!
116	//! `ThinVec` has some* support for handling auto arrays which store their buffer on the stack,*
117	//! but this isn't well tested.
118	//!
119	//! Regardless of how much support we provide, Rust won't be aware of the buffer's limited lifetime,
120	//! so standard auto array safety caveats apply about returning/storing them! `ThinVec` won't ever
121	//! produce an auto array on its own, so this is only an issue for transferring an nsTArray into
122	//! Rust.
123	//!
124	//! ## Other Issues
125	//!
126	//! Standard FFI caveats also apply:
127	//!
128	//! Rust is more strict about POD types being initialized (use MaybeUninit if you must)*
129	//! `ThinVec<T>` has no idea if the C++ version of `T` has move/copy/assign/delete overloads*
130	//! `nsTArray<T>` has no idea if the Rust version of `T` has a Drop/Clone impl*
131	//! C++ can do all sorts of unsound things that Rust can't catch*
132	//! C++ and Rust don't agree on how zero-sized/empty types should be handled*
133	//!
134	//! The gecko-ffi feature will not work if you aren't linking with code that has nsTArray
135	//! defined. Specifically, we must share the symbol for nsTArray's empty singleton. You will get
136	//! linking errors if that isn't defined.
137	//!
138	//! The gecko-ffi feature also limits `ThinVec` to the legacy behaviors of nsTArray. Most notably,
139	//! nsTArray has a maximum capacity of i32::MAX (~2.1 billion items). Probably not an issue.
140	//! Probably.
141	//!
142	//! [pinned]: https://doc.rust-lang.org/std/pin/index.html
143
144	#![cfg_attr(not(feature = "std"), no_std)]
145	#![allow(clippy::comparison_chain, clippy::missing_safety_doc)]
146
147	extern crate alloc;
148
149	use alloc::alloc::*;
150	use alloc::{boxed::Box, vec::Vec};
151	use core::borrow::*;
152	use core::cmp::*;
153	use core::convert::TryFrom;
154	use core::convert::TryInto;
155	use core::hash::*;
156	use core::iter::FromIterator;
157	use core::marker::PhantomData;
158	use core::ops::Bound;
159	use core::ops::{Deref, DerefMut, RangeBounds};
160	use core::ptr::NonNull;
161	use core::slice::IterMut;
162	use core::{fmt, mem, ptr, slice};
163
164	use impl_details::*;
165
166	// modules: a simple way to cfg a whole bunch of impl details at once
167
168	#[cfg(not(feature = "gecko-ffi"))]
169	mod impl_details {
170	pub type SizeType = usize;
171	pub const MAX_CAP: usize = !`0`;
172
173	#[inline(always)]
174	pub fn assert_size(x: usize) -> SizeType {
175	x
176	}
177	}
178
179	#[cfg(feature = "gecko-ffi")]
180	mod impl_details {
181	// Support for briding a gecko nsTArray verbatim into a ThinVec.
182	//
183	// `ThinVec` can't see copy/move/delete implementations
184	// from C++
185	//
186	// The actual layout of an nsTArray is:
187	//
188	// ```cpp
189	// struct {
190	// uint32_t mLength;
191	// uint32_t mCapacity: 31;
192	// uint32_t mIsAutoArray: 1;
193	// }
194	// ```
195	//
196	// Rust doesn't natively support bit-fields, so we manually mask
197	// and shift the bit. When the "auto" bit is set, the header and buffer
198	// are actually on the stack, meaning the `ThinVec` pointer-to-header
199	// is essentially an "owned borrow", and therefore dangerous to handle.
200	// There are no safety guards for this situation.
201	//
202	// On little-endian platforms, the auto bit will be the high-bit of
203	// our capacity u32. On big-endian platforms, it will be the low bit.
204	// Hence we need some platform-specific CFGs for the necessary masking/shifting.
205	//
206	// `ThinVec` won't ever construct an auto array. They only happen when
207	// bridging from C++. This means we don't need to ever set/preserve the bit.
208	// We just need to be able to read and handle it if it happens to be there.
209	//
210	// Handling the auto bit mostly just means not freeing/reallocating the buffer.
211
212	pub type SizeType = u32;
213
214	pub const MAX_CAP: usize = i32::max_value() as usize;
215
216	// Little endian: the auto bit is the high bit, and the capacity is
217	// verbatim. So we just need to mask off the high bit. Note that
218	// this masking is unnecessary when packing, because assert_size
219	// guards against the high bit being set.
220	#[cfg(target_endian = "little")]
221	pub fn pack_capacity(cap: SizeType) -> SizeType {
222	cap as SizeType
223	}
224	#[cfg(target_endian = "little")]
225	pub fn unpack_capacity(cap: SizeType) -> usize {
226	(cap as usize) & !(`1` << `31`)
227	}
228	#[cfg(target_endian = "little")]
229	pub fn is_auto(cap: SizeType) -> bool {
230	(cap & (`1` << `31`)) != `0`
231	}
232
233	// Big endian: the auto bit is the low bit, and the capacity is
234	// shifted up one bit. Masking out the auto bit is unnecessary,
235	// as rust shifts always shift in 0's for unsigned integers.
236	#[cfg(target_endian = "big")]
237	pub fn pack_capacity(cap: SizeType) -> SizeType {
238	(cap as SizeType) << `1`
239	}
240	#[cfg(target_endian = "big")]
241	pub fn unpack_capacity(cap: SizeType) -> usize {
242	(cap >> `1`) as usize
243	}
244	#[cfg(target_endian = "big")]
245	pub fn is_auto(cap: SizeType) -> bool {
246	(cap & `1`) != `0`
247	}
248
249	#[inline]
250	pub fn assert_size(x: usize) -> SizeType {
251	if x > MAX_CAP as usize {
252	panic!("nsTArray size may not exceed the capacity of a 32-bit sized int");
253	}
254	x as SizeType
255	}
256	}
257
258	// The header of a ThinVec.
259	//
260	// The _cap can be a bitfield, so use accessors to avoid trouble.
261	//
262	// In "real" gecko-ffi mode, the empty singleton will be aligned
263	// to 8 by gecko. But in tests we have to provide the singleton
264	// ourselves, and Rust makes it hard to "just" align a static.
265	// To avoid messing around with a wrapper type around the
266	// singleton just* for tests, we just force all headers to be*
267	// aligned to 8 in this weird "zombie" gecko mode.
268	//
269	// This shouldn't affect runtime layout (padding), but it will
270	// result in us asking the allocator to needlessly overalign
271	// non-empty ThinVecs containing align < 8 types in
272	// zombie-mode, but not in "real" geck-ffi mode. Minor.
273	#[cfg_attr(all(feature = "gecko-ffi", any(test, miri)), repr(align(`8`)))]
274	#[repr(C)]
275	struct Header {
276	_len: SizeType,
277	_cap: SizeType,
278	}
279
280	impl Header {
281	#[inline]
282	#[allow(clippy::unnecessary_cast)]
283	fn len(&self) -> usize {
284	self._len as usize
285	}
286
287	#[inline]
288	fn set_len(&mut self, len: usize) {
289	self._len = assert_size(len);
290	}
291	}
292
293	#[cfg(feature = "gecko-ffi")]
294	impl Header {
295	fn cap(&self) -> usize {
296	unpack_capacity(self._cap)
297	}
298
299	fn set_cap(&mut self, cap: usize) {
300	// debug check that our packing is working
301	debug_assert_eq!(unpack_capacity(pack_capacity(cap as SizeType)), cap);
302	// FIXME: this assert is busted because it reads uninit memory
303	// debug_assert!(!self.uses_stack_allocated_buffer());
304
305	// NOTE: this always stores a cleared auto bit, because set_cap
306	// is only invoked by Rust, and Rust doesn't create auto arrays.
307	self._cap = pack_capacity(assert_size(cap));
308	}
309
310	fn uses_stack_allocated_buffer(&self) -> bool {
311	is_auto(self._cap)
312	}
313	}
314
315	#[cfg(not(feature = "gecko-ffi"))]
316	impl Header {
317	#[inline]
318	#[allow(clippy::unnecessary_cast)]
319	fn cap(&self) -> usize {
320	self._cap as usize
321	}
322
323	#[inline]
324	fn set_cap(&mut self, cap: usize) {
325	self._cap = assert_size(cap);
326	}
327	}
328
329	/// Singleton that all empty collections share.
330	/// Note: can't store non-zero ZSTs, we allocate in that case. We could
331	/// optimize everything to not do that (basically, make ptr == len and branch
332	/// on size == 0 in every method), but it's a bunch of work for something that
333	/// doesn't matter much.
334	#[cfg(any(not(feature = "gecko-ffi"), test, miri))]
335	static EMPTY_HEADER: Header = Header { _len: `0`, _cap: `0` };
336
337	#[cfg(all(feature = "gecko-ffi", not(test), not(miri)))]
338	extern "C" {
339	#[link_name = "sEmptyTArrayHeader"]
340	static EMPTY_HEADER: Header;
341	}
342
343	// Utils for computing layouts of allocations
344
345	/// Gets the size necessary to allocate a `ThinVec<T>` with the give capacity.
346	///
347	/// # Panics
348	///
349	/// This will panic if isize::MAX is overflowed at any point.
350	fn alloc_size<T>(cap: usize) -> usize {
351	// Compute "real" header size with pointer math
352	//
353	// We turn everything into isizes here so that we can catch isize::MAX overflow,
354	// we never want to allow allocations larger than that!
355	let header_size = mem::size_of::<Header>() as isize;
356	let padding = padding::<T>() as isize;
357
358	let data_size = if mem::size_of::<T>() == `0` {
359	// If we're allocating an array for ZSTs we need a header/padding but no actual
360	// space for items, so we don't care about the capacity that was requested!
361	`0`
362	} else {
363	let cap: isize = cap.try_into().expect("capacity overflow");
364	let elem_size = mem::size_of::<T>() as isize;
365	elem_size.checked_mul(cap).expect("capacity overflow")
366	};
367
368	let final_size = data_size
369	.checked_add(header_size + padding)
370	.expect("capacity overflow");
371
372	// Ok now we can turn it back into a usize (don't need to worry about negatives)
373	final_size as usize
374	}
375
376	/// Gets the padding necessary for the array of a `ThinVec<T>`
377	fn padding<T>() -> usize {
378	let alloc_align: usize = alloc_align::<T>();
379	let header_size: usize = mem::size_of::<Header>();
380
381	if alloc_align > header_size {
382	if cfg!(feature = "gecko-ffi") {
383	panic!(
384	"nsTArray does not handle alignment above > {} correctly",
385	header_size
386	);
387	}
388	alloc_align - header_size
389	} else {
390	`0`
391	}
392	}
393
394	/// Gets the align necessary to allocate a `ThinVec<T>`
395	fn alloc_align<T>() -> usize {
396	max(v1:mem::align_of::<T>(), v2:mem::align_of::<Header>())
397	}
398
399	/// Gets the layout necessary to allocate a `ThinVec<T>`
400	///
401	/// # Panics
402	///
403	/// Panics if the required size overflows `isize::MAX`.
404	fn layout<T>(cap: usize) -> Layout {
405	unsafe { Layout::from_size_align_unchecked(alloc_size::<T>(cap), alloc_align::<T>()) }
406	}
407
408	/// Allocates a header (and array) for a `ThinVec<T>` with the given capacity.
409	///
410	/// # Panics
411	///
412	/// Panics if the required size overflows `isize::MAX`.
413	fn header_with_capacity<T>(cap: usize) -> NonNull<Header> {
414	debug_assert!(cap > `0`);
415	unsafe {
416	let layout: Layout = layout::<T>(cap);
417	let header: mut Header = alloc(layout) as mut Header;
418
419	if header.is_null() {
420	handle_alloc_error(layout)
421	}
422
423	// "Infinite" capacity for zero-sized types:
424	(*header).set_cap(if mem::size_of::<T>() == `0` {
425	MAX_CAP
426	} else {
427	cap
428	});
429	(*header).set_len(`0`);
430
431	NonNull::new_unchecked(ptr:header)
432	}
433	}
434
435	/// See the crate's top level documentation for a description of this type.
436	#[repr(C)]
437	pub struct ThinVec<T> {
438	ptr: NonNull<Header>,
439	boo: PhantomData<T>,
440	}
441
442	unsafe impl<T: Sync> Sync for ThinVec<T> {}
443	unsafe impl<T: Send> Send for ThinVec<T> {}
444
445	/// Creates a `ThinVec` containing the arguments.
446	///
447	// A hack to avoid linking problems with `cargo test --features=gecko-ffi`.
448	#[cfg_attr(not(feature = "gecko-ffi"), doc = "```")]
449	#[cfg_attr(feature = "gecko-ffi", doc = "```ignore")]
450	/// #[macro_use] extern crate thin_vec;
451	///
452	/// fn main() {
453	/// let v = thin_vec![`1`, `2`, `3`];
454	/// assert_eq!(v.len(), `3`);
455	/// assert_eq!(v[`0`], `1`);
456	/// assert_eq!(v[`1`], `2`);
457	/// assert_eq!(v[`2`], `3`);
458	///
459	/// let v = thin_vec![`1`; `3`];
460	/// assert_eq!(v, [`1`, `1`, `1`]);
461	/// }
462	/// ```
463	#[macro_export]
464	macro_rules! thin_vec {
465	(@UNIT $($t:tt)*) => (());
466
467	($elem:expr; $n:expr) => ({
468	let mut vec = $crate::ThinVec::new();
469	vec.resize($n, $elem);
470	vec
471	});
472	() => {$crate::ThinVec::new()};
473	($($x:expr),*) => ({
474	let len = [$(thin_vec!(@UNIT $x)),*].len();
475	let mut vec = $crate::ThinVec::with_capacity(len);
476	$(vec.push($x);)*
477	vec
478	});
479	($($x:expr,)) => (thin_vec![$($x),]);
480	}
481
482	impl<T> ThinVec<T> {
483	/// Creates a new empty ThinVec.
484	///
485	/// This will not allocate.
486	pub fn new() -> ThinVec<T> {
487	ThinVec::with_capacity(`0`)
488	}
489
490	/// Constructs a new, empty `ThinVec<T>` with at least the specified capacity.
491	///
492	/// The vector will be able to hold at least `capacity` elements without
493	/// reallocating. This method is allowed to allocate for more elements than
494	/// `capacity`. If `capacity` is 0, the vector will not allocate.
495	///
496	/// It is important to note that although the returned vector has the
497	/// minimum capacity* specified, the vector will have a zero length.*
498	///
499	/// If it is important to know the exact allocated capacity of a `ThinVec`,
500	/// always use the [`capacity`] method after construction.
501	///
502	/// NOTE: unlike `Vec`, `ThinVec` MUST* allocate once to keep track of non-zero*
503	/// lengths. As such, we cannot provide the same guarantees about ThinVecs
504	/// of ZSTs not allocating. However the allocation never needs to be resized
505	/// to add more ZSTs, since the underlying array is still length 0.
506	///
507	/// [Capacity and reallocation]: #capacity-and-reallocation
508	/// [`capacity`]: Vec::capacity
509	///
510	/// # Panics
511	///
512	/// Panics if the new capacity exceeds `isize::MAX` bytes.
513	///
514	/// # Examples
515	///
516	/// ```
517	/// use thin_vec::ThinVec;
518	///
519	/// let mut vec = ThinVec::with_capacity(`10`);
520	///
521	/// // The vector contains no items, even though it has capacity for more
522	/// assert_eq!(vec.len(), `0`);
523	/// assert!(vec.capacity() >= `10`);
524	///
525	/// // These are all done without reallocating...
526	/// for i in `0`..`10` {
527	/// vec.push(i);
528	/// }
529	/// assert_eq!(vec.len(), `10`);
530	/// assert!(vec.capacity() >= `10`);
531	///
532	/// // ...but this may make the vector reallocate
533	/// vec.push(`11`);
534	/// assert_eq!(vec.len(), `11`);
535	/// assert!(vec.capacity() >= `11`);
536	///
537	/// // A vector of a zero-sized type will always over-allocate, since no
538	/// // space is needed to store the actual elements.
539	/// let vec_units = ThinVec::<()>::with_capacity(`10`);
540	///
541	/// // Only true without* the gecko-ffi feature!*
542	/// // assert_eq!(vec_units.capacity(), usize::MAX);
543	/// ```
544	pub fn with_capacity(cap: usize) -> ThinVec<T> {
545	// `padding` contains ~static assertions against types that are
546	// incompatible with the current feature flags. We also call it to
547	// invoke these assertions when getting a pointer to the `ThinVec`
548	// contents, but since we also get a pointer to the contents in the
549	// `Drop` impl, trippng an assertion along that code path causes a
550	// double panic. We duplicate the assertion here so that it is
551	// testable,
552	let _ = padding::<T>();
553
554	if cap == `0` {
555	unsafe {
556	ThinVec {
557	ptr: NonNull::new_unchecked(&EMPTY_HEADER as *const Header as *mut Header),
558	boo: PhantomData,
559	}
560	}
561	} else {
562	ThinVec {
563	ptr: header_with_capacity::<T>(cap),
564	boo: PhantomData,
565	}
566	}
567	}
568
569	// Accessor conveniences
570
571	fn ptr(&self) -> *mut Header {
572	self.ptr.as_ptr()
573	}
574	fn header(&self) -> &Header {
575	unsafe { self.ptr.as_ref() }
576	}
577	fn data_raw(&self) -> *mut T {
578	// `padding` contains ~static assertions against types that are
579	// incompatible with the current feature flags. Even if we don't
580	// care about its result, we should always call it before getting
581	// a data pointer to guard against invalid types!
582	let padding = padding::<T>();
583
584	// Although we ensure the data array is aligned when we allocate,
585	// we can't do that with the empty singleton. So when it might not
586	// be properly aligned, we substitute in the NonNull::dangling
587	// which is* aligned.*
588	//
589	// To minimize dynamic branches on `cap` for all accesses
590	// to the data, we include this guard which should only involve
591	// compile-time constants. Ideally this should result in the branch
592	// only be included for types with excessive alignment.
593	let empty_header_is_aligned = if cfg!(feature = "gecko-ffi") {
594	// in gecko-ffi mode `padding` will ensure this under
595	// the assumption that the header has size 8 and the
596	// static empty singleton is aligned to 8.
597	`true`
598	} else {
599	// In non-gecko-ffi mode, the empty singleton is just
600	// naturally aligned to the Header. If the Header is at
601	// least as aligned as T and* the padding would have*
602	// been 0, then one-past-the-end of the empty singleton
603	// is* a valid data pointer and we can remove the*
604	// `dangling` special case.
605	mem::align_of::<Header>() >= mem::align_of::<T>() && padding == `0`
606	};
607
608	unsafe {
609	if !empty_header_is_aligned && self.header().cap() == `0` {
610	NonNull::dangling().as_ptr()
611	} else {
612	// This could technically result in overflow, but padding
613	// would have to be absurdly large for this to occur.
614	let header_size = mem::size_of::<Header>();
615	let ptr = self.ptr.as_ptr() as *mut u8;
616	ptr.add(header_size + padding) as *mut T
617	}
618	}
619	}
620
621	// This is unsafe when the header is EMPTY_HEADER.
622	unsafe fn header_mut(&mut self) -> &mut Header {
623	&mut *self.ptr()
624	}
625
626	/// Returns the number of elements in the vector, also referred to
627	/// as its 'length'.
628	///
629	/// # Examples
630	///
631	/// ```
632	/// use thin_vec::thin_vec;
633	///
634	/// let a = thin_vec![`1`, `2`, `3`];
635	/// assert_eq!(a.len(), `3`);
636	/// ```
637	pub fn len(&self) -> usize {
638	self.header().len()
639	}
640
641	/// Returns `true` if the vector contains no elements.
642	///
643	/// # Examples
644	///
645	/// ```
646	/// use thin_vec::ThinVec;
647	///
648	/// let mut v = ThinVec::new();
649	/// assert!(v.is_empty());
650	///
651	/// v.push(`1`);
652	/// assert!(!v.is_empty());
653	/// ```
654	pub fn is_empty(&self) -> bool {
655	self.len() == `0`
656	}
657
658	/// Returns the number of elements the vector can hold without
659	/// reallocating.
660	///
661	/// # Examples
662	///
663	/// ```
664	/// use thin_vec::ThinVec;
665	///
666	/// let vec: ThinVec<i32> = ThinVec::with_capacity(`10`);
667	/// assert_eq!(vec.capacity(), `10`);
668	/// ```
669	pub fn capacity(&self) -> usize {
670	self.header().cap()
671	}
672
673	/// Returns `true` if the vector has the capacity to hold any element.
674	pub fn has_capacity(&self) -> bool {
675	!self.is_singleton()
676	}
677
678	/// Forces the length of the vector to `new_len`.
679	///
680	/// This is a low-level operation that maintains none of the normal
681	/// invariants of the type. Normally changing the length of a vector
682	/// is done using one of the safe operations instead, such as
683	/// [`truncate`], [`resize`], [`extend`], or [`clear`].
684	///
685	/// [`truncate`]: ThinVec::truncate
686	/// [`resize`]: ThinVec::resize
687	/// [`extend`]: ThinVec::extend
688	/// [`clear`]: ThinVec::clear
689	///
690	/// # Safety
691	///
692	/// - `new_len` must be less than or equal to [`capacity()`].
693	/// - The elements at `old_len..new_len` must be initialized.
694	///
695	/// [`capacity()`]: ThinVec::capacity
696	///
697	/// # Examples
698	///
699	/// This method can be useful for situations in which the vector
700	/// is serving as a buffer for other code, particularly over FFI:
701	///
702	/// ```no_run
703	/// use thin_vec::ThinVec;
704	///
705	/// # // This is just a minimal skeleton for the doc example;
706	/// # // don't use this as a starting point for a real library.
707	/// # pub struct StreamWrapper { strm: *mut std::ffi::c_void }
708	/// # const Z_OK: i32 = `0`;
709	/// # extern "C" {
710	/// # fn deflateGetDictionary(
711	/// # strm: *mut std::ffi::c_void,
712	/// # dictionary: *mut u8,
713	/// # dictLength: *mut usize,
714	/// # ) -> i32;
715	/// # }
716	/// # impl StreamWrapper {
717	/// pub fn get_dictionary(&self) -> Option<ThinVec<u8>> {
718	/// // Per the FFI method's docs, "32768 bytes is always enough".
719	/// let mut dict = ThinVec::with_capacity(`32_768`);
720	/// let mut dict_length = `0`;
721	/// // SAFETY: When `deflateGetDictionary` returns `Z_OK`, it holds that:
722	/// // 1. `dict_length` elements were initialized.
723	/// // 2. `dict_length` <= the capacity (32_768)
724	/// // which makes `set_len` safe to call.
725	/// unsafe {
726	/// // Make the FFI call...
727	/// let r = deflateGetDictionary(self.strm, dict.as_mut_ptr(), &mut dict_length);
728	/// if r == Z_OK {
729	/// // ...and update the length to what was initialized.
730	/// dict.set_len(dict_length);
731	/// Some(dict)
732	/// } else {
733	/// None
734	/// }
735	/// }
736	/// }
737	/// # }
738	/// ```
739	///
740	/// While the following example is sound, there is a memory leak since
741	/// the inner vectors were not freed prior to the `set_len` call:
742	///
743	/// ```no_run
744	/// use thin_vec::thin_vec;
745	///
746	/// let mut vec = thin_vec![thin_vec![`1`, `0`, `0`],
747	/// thin_vec![`0`, `1`, `0`],
748	/// thin_vec![`0`, `0`, `1`]];
749	/// // SAFETY:
750	/// // 1. `old_len..0` is empty so no elements need to be initialized.
751	/// // 2. `0 <= capacity` always holds whatever `capacity` is.
752	/// unsafe {
753	/// vec.set_len(`0`);
754	/// }
755	/// ```
756	///
757	/// Normally, here, one would use [`clear`] instead to correctly drop
758	/// the contents and thus not leak memory.
759	pub unsafe fn set_len(&mut self, len: usize) {
760	if self.is_singleton() {
761	// A prerequisite of `Vec::set_len` is that `new_len` must be
762	// less than or equal to capacity(). The same applies here.
763	debug_assert!(len == `0`, "invalid set_len({}) on empty ThinVec", len);
764	} else {
765	self.header_mut().set_len(len)
766	}
767	}
768
769	// For internal use only, when setting the length and it's known to be the non-singleton.
770	unsafe fn set_len_non_singleton(&mut self, len: usize) {
771	self.header_mut().set_len(len)
772	}
773
774	/// Appends an element to the back of a collection.
775	///
776	/// # Panics
777	///
778	/// Panics if the new capacity exceeds `isize::MAX` bytes.
779	///
780	/// # Examples
781	///
782	/// ```
783	/// use thin_vec::thin_vec;
784	///
785	/// let mut vec = thin_vec![`1`, `2`];
786	/// vec.push(`3`);
787	/// assert_eq!(vec, [`1`, `2`, `3`]);
788	/// ```
789	pub fn push(&mut self, val: T) {
790	let old_len = self.len();
791	if old_len == self.capacity() {
792	self.reserve(`1`);
793	}
794	unsafe {
795	ptr::write(self.data_raw().add(old_len), val);
796	self.set_len_non_singleton(old_len + `1`);
797	}
798	}
799
800	/// Removes the last element from a vector and returns it, or [`None`] if it
801	/// is empty.
802	///
803	/// # Examples
804	///
805	/// ```
806	/// use thin_vec::thin_vec;
807	///
808	/// let mut vec = thin_vec![`1`, `2`, `3`];
809	/// assert_eq!(vec.pop(), Some(`3`));
810	/// assert_eq!(vec, [`1`, `2`]);
811	/// ```
812	pub fn pop(&mut self) -> Option<T> {
813	let old_len = self.len();
814	if old_len == `0` {
815	return None;
816	}
817
818	unsafe {
819	self.set_len_non_singleton(old_len - `1`);
820	Some(ptr::read(self.data_raw().add(old_len - `1`)))
821	}
822	}
823
824	/// Inserts an element at position `index` within the vector, shifting all
825	/// elements after it to the right.
826	///
827	/// # Panics
828	///
829	/// Panics if `index > len`.
830	///
831	/// # Examples
832	///
833	/// ```
834	/// use thin_vec::thin_vec;
835	///
836	/// let mut vec = thin_vec![`1`, `2`, `3`];
837	/// vec.insert(`1`, `4`);
838	/// assert_eq!(vec, [`1`, `4`, `2`, `3`]);
839	/// vec.insert(`4`, `5`);
840	/// assert_eq!(vec, [`1`, `4`, `2`, `3`, `5`]);
841	/// ```
842	pub fn insert(&mut self, idx: usize, elem: T) {
843	let old_len = self.len();
844
845	assert!(idx <= old_len, "Index out of bounds");
846	if old_len == self.capacity() {
847	self.reserve(`1`);
848	}
849	unsafe {
850	let ptr = self.data_raw();
851	ptr::copy(ptr.add(idx), ptr.add(idx + `1`), old_len - idx);
852	ptr::write(ptr.add(idx), elem);
853	self.set_len_non_singleton(old_len + `1`);
854	}
855	}
856
857	/// Removes and returns the element at position `index` within the vector,
858	/// shifting all elements after it to the left.
859	///
860	/// Note: Because this shifts over the remaining elements, it has a
861	/// worst-case performance of O(n). If you don't need the order of elements
862	/// to be preserved, use [`swap_remove`] instead. If you'd like to remove
863	/// elements from the beginning of the `ThinVec`, consider using `std::collections::VecDeque`.
864	///
865	/// [`swap_remove`]: ThinVec::swap_remove
866	///
867	/// # Panics
868	///
869	/// Panics if `index` is out of bounds.
870	///
871	/// # Examples
872	///
873	/// ```
874	/// use thin_vec::thin_vec;
875	///
876	/// let mut v = thin_vec![`1`, `2`, `3`];
877	/// assert_eq!(v.remove(`1`), `2`);
878	/// assert_eq!(v, [`1`, `3`]);
879	/// ```
880	pub fn remove(&mut self, idx: usize) -> T {
881	let old_len = self.len();
882
883	assert!(idx < old_len, "Index out of bounds");
884
885	unsafe {
886	self.set_len_non_singleton(old_len - `1`);
887	let ptr = self.data_raw();
888	let val = ptr::read(self.data_raw().add(idx));
889	ptr::copy(ptr.add(idx + `1`), ptr.add(idx), old_len - idx - `1`);
890	val
891	}
892	}
893
894	/// Removes an element from the vector and returns it.
895	///
896	/// The removed element is replaced by the last element of the vector.
897	///
898	/// This does not preserve ordering, but is O(1).
899	/// If you need to preserve the element order, use [`remove`] instead.
900	///
901	/// [`remove`]: ThinVec::remove
902	///
903	/// # Panics
904	///
905	/// Panics if `index` is out of bounds.
906	///
907	/// # Examples
908	///
909	/// ```
910	/// use thin_vec::thin_vec;
911	///
912	/// let mut v = thin_vec!["foo", "bar", "baz", "qux"];
913	///
914	/// assert_eq!(v.swap_remove(`1`), "bar");
915	/// assert_eq!(v, ["foo", "qux", "baz"]);
916	///
917	/// assert_eq!(v.swap_remove(`0`), "foo");
918	/// assert_eq!(v, ["baz", "qux"]);
919	/// ```
920	pub fn swap_remove(&mut self, idx: usize) -> T {
921	let old_len = self.len();
922
923	assert!(idx < old_len, "Index out of bounds");
924
925	unsafe {
926	let ptr = self.data_raw();
927	ptr::swap(ptr.add(idx), ptr.add(old_len - `1`));
928	self.set_len_non_singleton(old_len - `1`);
929	ptr::read(ptr.add(old_len - `1`))
930	}
931	}
932
933	/// Shortens the vector, keeping the first `len` elements and dropping
934	/// the rest.
935	///
936	/// If `len` is greater than the vector's current length, this has no
937	/// effect.
938	///
939	/// The [`drain`] method can emulate `truncate`, but causes the excess
940	/// elements to be returned instead of dropped.
941	///
942	/// Note that this method has no effect on the allocated capacity
943	/// of the vector.
944	///
945	/// # Examples
946	///
947	/// Truncating a five element vector to two elements:
948	///
949	/// ```
950	/// use thin_vec::thin_vec;
951	///
952	/// let mut vec = thin_vec![`1`, `2`, `3`, `4`, `5`];
953	/// vec.truncate(`2`);
954	/// assert_eq!(vec, [`1`, `2`]);
955	/// ```
956	///
957	/// No truncation occurs when `len` is greater than the vector's current
958	/// length:
959	///
960	/// ```
961	/// use thin_vec::thin_vec;
962	///
963	/// let mut vec = thin_vec![`1`, `2`, `3`];
964	/// vec.truncate(`8`);
965	/// assert_eq!(vec, [`1`, `2`, `3`]);
966	/// ```
967	///
968	/// Truncating when `len == 0` is equivalent to calling the [`clear`]
969	/// method.
970	///
971	/// ```
972	/// use thin_vec::thin_vec;
973	///
974	/// let mut vec = thin_vec![`1`, `2`, `3`];
975	/// vec.truncate(`0`);
976	/// assert_eq!(vec, []);
977	/// ```
978	///
979	/// [`clear`]: ThinVec::clear
980	/// [`drain`]: ThinVec::drain
981	pub fn truncate(&mut self, len: usize) {
982	unsafe {
983	// drop any extra elements
984	while len < self.len() {
985	// decrement len before the drop_in_place(), so a panic on Drop
986	// doesn't re-drop the just-failed value.
987	let new_len = self.len() - `1`;
988	self.set_len_non_singleton(new_len);
989	ptr::drop_in_place(self.data_raw().add(new_len));
990	}
991	}
992	}
993
994	/// Clears the vector, removing all values.
995	///
996	/// Note that this method has no effect on the allocated capacity
997	/// of the vector.
998	///
999	/// # Examples
1000	///
1001	/// ```
1002	/// use thin_vec::thin_vec;
1003	///
1004	/// let mut v = thin_vec![`1`, `2`, `3`];
1005	/// v.clear();
1006	/// assert!(v.is_empty());
1007	/// ```
1008	pub fn clear(&mut self) {
1009	unsafe {
1010	ptr::drop_in_place(&mut self[..]);
1011	self.set_len(`0`); // could be the singleton
1012	}
1013	}
1014
1015	/// Extracts a slice containing the entire vector.
1016	///
1017	/// Equivalent to `&s[..]`.
1018	///
1019	/// # Examples
1020	///
1021	/// ```
1022	/// use thin_vec::thin_vec;
1023	/// use std::io::{self, Write};
1024	/// let buffer = thin_vec![`1`, `2`, `3`, `5`, `8`];
1025	/// io::sink().write(buffer.as_slice()).unwrap();
1026	/// ```
1027	pub fn as_slice(&self) -> &[T] {
1028	unsafe { slice::from_raw_parts(self.data_raw(), self.len()) }
1029	}
1030
1031	/// Extracts a mutable slice of the entire vector.
1032	///
1033	/// Equivalent to `&mut s[..]`.
1034	///
1035	/// # Examples
1036	///
1037	/// ```
1038	/// use thin_vec::thin_vec;
1039	/// use std::io::{self, Read};
1040	/// let mut buffer = vec![`0`; `3`];
1041	/// io::repeat(`0b101`).read_exact(buffer.as_mut_slice()).unwrap();
1042	/// ```
1043	pub fn as_mut_slice(&mut self) -> &mut [T] {
1044	unsafe { slice::from_raw_parts_mut(self.data_raw(), self.len()) }
1045	}
1046
1047	/// Reserve capacity for at least `additional` more elements to be inserted.
1048	///
1049	/// May reserve more space than requested, to avoid frequent reallocations.
1050	///
1051	/// Panics if the new capacity overflows `usize`.
1052	///
1053	/// Re-allocates only if `self.capacity() < self.len() + additional`.
1054	#[cfg(not(feature = "gecko-ffi"))]
1055	pub fn reserve(&mut self, additional: usize) {
1056	let len = self.len();
1057	let old_cap = self.capacity();
1058	let min_cap = len.checked_add(additional).expect("capacity overflow");
1059	if min_cap <= old_cap {
1060	return;
1061	}
1062	// Ensure the new capacity is at least double, to guarantee exponential growth.
1063	let double_cap = if old_cap == `0` {
1064	// skip to 4 because tiny ThinVecs are dumb; but not if that would cause overflow
1065	if mem::size_of::<T>() > (!`0`) / `8` {
1066	`1`
1067	} else {
1068	`4`
1069	}
1070	} else {
1071	old_cap.saturating_mul(`2`)
1072	};
1073	let new_cap = max(min_cap, double_cap);
1074	unsafe {
1075	self.reallocate(new_cap);
1076	}
1077	}
1078
1079	/// Reserve capacity for at least `additional` more elements to be inserted.
1080	///
1081	/// This method mimics the growth algorithm used by the C++ implementation
1082	/// of nsTArray.
1083	#[cfg(feature = "gecko-ffi")]
1084	pub fn reserve(&mut self, additional: usize) {
1085	let elem_size = mem::size_of::<T>();
1086
1087	let len = self.len();
1088	let old_cap = self.capacity();
1089	let min_cap = len.checked_add(additional).expect("capacity overflow");
1090	if min_cap <= old_cap {
1091	return;
1092	}
1093
1094	// The growth logic can't handle zero-sized types, so we have to exit
1095	// early here.
1096	if elem_size == `0` {
1097	unsafe {
1098	self.reallocate(min_cap);
1099	}
1100	return;
1101	}
1102
1103	let min_cap_bytes = assert_size(min_cap)
1104	.checked_mul(assert_size(elem_size))
1105	.and_then(\|x\| x.checked_add(assert_size(mem::size_of::<Header>())))
1106	.unwrap();
1107
1108	// Perform some checked arithmetic to ensure all of the numbers we
1109	// compute will end up in range.
1110	let will_fit = min_cap_bytes.checked_mul(`2`).is_some();
1111	if !will_fit {
1112	panic!("Exceeded maximum nsTArray size");
1113	}
1114
1115	const SLOW_GROWTH_THRESHOLD: usize = `8` * `1024` * `1024`;
1116
1117	let bytes = if min_cap > SLOW_GROWTH_THRESHOLD {
1118	// Grow by a minimum of 1.125x
1119	let old_cap_bytes = old_cap * elem_size + mem::size_of::<Header>();
1120	let min_growth = old_cap_bytes + (old_cap_bytes >> `3`);
1121	let growth = max(min_growth, min_cap_bytes as usize);
1122
1123	// Round up to the next megabyte.
1124	const MB: usize = `1` << `20`;
1125	MB * ((growth + MB - `1`) / MB)
1126	} else {
1127	// Try to allocate backing buffers in powers of two.
1128	min_cap_bytes.next_power_of_two() as usize
1129	};
1130
1131	let cap = (bytes - core::mem::size_of::<Header>()) / elem_size;
1132	unsafe {
1133	self.reallocate(cap);
1134	}
1135	}
1136
1137	/// Reserves the minimum capacity for `additional` more elements to be inserted.
1138	///
1139	/// Panics if the new capacity overflows `usize`.
1140	///
1141	/// Re-allocates only if `self.capacity() < self.len() + additional`.
1142	pub fn reserve_exact(&mut self, additional: usize) {
1143	let new_cap = self
1144	.len()
1145	.checked_add(additional)
1146	.expect("capacity overflow");
1147	let old_cap = self.capacity();
1148	if new_cap > old_cap {
1149	unsafe {
1150	self.reallocate(new_cap);
1151	}
1152	}
1153	}
1154
1155	/// Shrinks the capacity of the vector as much as possible.
1156	///
1157	/// It will drop down as close as possible to the length but the allocator
1158	/// may still inform the vector that there is space for a few more elements.
1159	///
1160	/// # Examples
1161	///
1162	/// ```
1163	/// use thin_vec::ThinVec;
1164	///
1165	/// let mut vec = ThinVec::with_capacity(`10`);
1166	/// vec.extend([`1`, `2`, `3`]);
1167	/// assert_eq!(vec.capacity(), `10`);
1168	/// vec.shrink_to_fit();
1169	/// assert!(vec.capacity() >= `3`);
1170	/// ```
1171	pub fn shrink_to_fit(&mut self) {
1172	let old_cap = self.capacity();
1173	let new_cap = self.len();
1174	if new_cap < old_cap {
1175	if new_cap == `0` {
1176	*self = ThinVec::new();
1177	} else {
1178	unsafe {
1179	self.reallocate(new_cap);
1180	}
1181	}
1182	}
1183	}
1184
1185	/// Retains only the elements specified by the predicate.
1186	///
1187	/// In other words, remove all elements `e` such that `f(&e)` returns `false`.
1188	/// This method operates in place and preserves the order of the retained
1189	/// elements.
1190	///
1191	/// # Examples
1192	///
1193	// A hack to avoid linking problems with `cargo test --features=gecko-ffi`.
1194	#[cfg_attr(not(feature = "gecko-ffi"), doc = "```")]
1195	#[cfg_attr(feature = "gecko-ffi", doc = "```ignore")]
1196	/// # #[macro_use] extern crate thin_vec;
1197	/// # fn main() {
1198	/// let mut vec = thin_vec![`1`, `2`, `3`, `4`];
1199	/// vec.retain(\|&x\| x%`2` == `0`);
1200	/// assert_eq!(vec, [`2`, `4`]);
1201	/// # }
1202	/// ```
1203	pub fn retain<F>(&mut self, mut f: F)
1204	where
1205	F: FnMut(&T) -> bool,
1206	{
1207	self.retain_mut(\|x\| f(&*x));
1208	}
1209
1210	/// Retains only the elements specified by the predicate, passing a mutable reference to it.
1211	///
1212	/// In other words, remove all elements `e` such that `f(&mut e)` returns `false`.
1213	/// This method operates in place and preserves the order of the retained
1214	/// elements.
1215	///
1216	/// # Examples
1217	///
1218	// A hack to avoid linking problems with `cargo test --features=gecko-ffi`.
1219	#[cfg_attr(not(feature = "gecko-ffi"), doc = "```")]
1220	#[cfg_attr(feature = "gecko-ffi", doc = "```ignore")]
1221	/// # #[macro_use] extern crate thin_vec;
1222	/// # fn main() {
1223	/// let mut vec = thin_vec![`1`, `2`, `3`, `4`, `5`];
1224	/// vec.retain_mut(\|x\| {
1225	/// *x += `1`;
1226	/// (*x)%`2` == `0`
1227	/// });
1228	/// assert_eq!(vec, [`2`, `4`, `6`]);
1229	/// # }
1230	/// ```
1231	pub fn retain_mut<F>(&mut self, mut f: F)
1232	where
1233	F: FnMut(&mut T) -> bool,
1234	{
1235	let len = self.len();
1236	let mut del = `0`;
1237	{
1238	let v = &mut self[..];
1239
1240	for i in `0`..len {
1241	if !f(&mut v[i]) {
1242	del += `1`;
1243	} else if del > `0` {
1244	v.swap(i - del, i);
1245	}
1246	}
1247	}
1248	if del > `0` {
1249	self.truncate(len - del);
1250	}
1251	}
1252
1253	/// Removes consecutive elements in the vector that resolve to the same key.
1254	///
1255	/// If the vector is sorted, this removes all duplicates.
1256	///
1257	/// # Examples
1258	///
1259	// A hack to avoid linking problems with `cargo test --features=gecko-ffi`.
1260	#[cfg_attr(not(feature = "gecko-ffi"), doc = "```")]
1261	#[cfg_attr(feature = "gecko-ffi", doc = "```ignore")]
1262	/// # #[macro_use] extern crate thin_vec;
1263	/// # fn main() {
1264	/// let mut vec = thin_vec![`10`, `20`, `21`, `30`, `20`];
1265	///
1266	/// vec.dedup_by_key(\|i\| *i / `10`);
1267	///
1268	/// assert_eq!(vec, [`10`, `20`, `30`, `20`]);
1269	/// # }
1270	/// ```
1271	pub fn dedup_by_key<F, K>(&mut self, mut key: F)
1272	where
1273	F: FnMut(&mut T) -> K,
1274	K: PartialEq<K>,
1275	{
1276	self.dedup_by(\|a, b\| key(a) == key(b))
1277	}
1278
1279	/// Removes consecutive elements in the vector according to a predicate.
1280	///
1281	/// The `same_bucket` function is passed references to two elements from the vector, and
1282	/// returns `true` if the elements compare equal, or `false` if they do not. Only the first
1283	/// of adjacent equal items is kept.
1284	///
1285	/// If the vector is sorted, this removes all duplicates.
1286	///
1287	/// # Examples
1288	///
1289	// A hack to avoid linking problems with `cargo test --features=gecko-ffi`.
1290	#[cfg_attr(not(feature = "gecko-ffi"), doc = "```")]
1291	#[cfg_attr(feature = "gecko-ffi", doc = "```ignore")]
1292	/// # #[macro_use] extern crate thin_vec;
1293	/// # fn main() {
1294	/// let mut vec = thin_vec!["foo", "bar", "Bar", "baz", "bar"];
1295	///
1296	/// vec.dedup_by(\|a, b\| a.eq_ignore_ascii_case(b));
1297	///
1298	/// assert_eq!(vec, ["foo", "bar", "baz", "bar"]);
1299	/// # }
1300	/// ```
1301	#[allow(clippy::swap_ptr_to_ref)]
1302	pub fn dedup_by<F>(&mut self, mut same_bucket: F)
1303	where
1304	F: FnMut(&mut T, &mut T) -> bool,
1305	{
1306	// See the comments in `Vec::dedup` for a detailed explanation of this code.
1307	unsafe {
1308	let ln = self.len();
1309	if ln <= `1` {
1310	return;
1311	}
1312
1313	// Avoid bounds checks by using raw pointers.
1314	let p = self.as_mut_ptr();
1315	let mut r: usize = `1`;
1316	let mut w: usize = `1`;
1317
1318	while r < ln {
1319	let p_r = p.add(r);
1320	let p_wm1 = p.add(w - `1`);
1321	if !same_bucket(&mut p_r, &mut* *p_wm1) {
1322	if r != w {
1323	let p_w = p_wm1.add(`1`);
1324	mem::swap(&mut p_r, &mut* *p_w);
1325	}
1326	w += `1`;
1327	}
1328	r += `1`;
1329	}
1330
1331	self.truncate(w);
1332	}
1333	}
1334
1335	/// Splits the collection into two at the given index.
1336	///
1337	/// Returns a newly allocated vector containing the elements in the range
1338	/// `[at, len)`. After the call, the original vector will be left containing
1339	/// the elements `[0, at)` with its previous capacity unchanged.
1340	///
1341	/// # Panics
1342	///
1343	/// Panics if `at > len`.
1344	///
1345	/// # Examples
1346	///
1347	/// ```
1348	/// use thin_vec::thin_vec;
1349	///
1350	/// let mut vec = thin_vec![`1`, `2`, `3`];
1351	/// let vec2 = vec.split_off(`1`);
1352	/// assert_eq!(vec, [`1`]);
1353	/// assert_eq!(vec2, [`2`, `3`]);
1354	/// ```
1355	pub fn split_off(&mut self, at: usize) -> ThinVec<T> {
1356	let old_len = self.len();
1357	let new_vec_len = old_len - at;
1358
1359	assert!(at <= old_len, "Index out of bounds");
1360
1361	unsafe {
1362	let mut new_vec = ThinVec::with_capacity(new_vec_len);
1363
1364	ptr::copy_nonoverlapping(self.data_raw().add(at), new_vec.data_raw(), new_vec_len);
1365
1366	new_vec.set_len(new_vec_len); // could be the singleton
1367	self.set_len(at); // could be the singleton
1368
1369	new_vec
1370	}
1371	}
1372
1373	/// Moves all the elements of `other` into `self`, leaving `other` empty.
1374	///
1375	/// # Panics
1376	///
1377	/// Panics if the new capacity exceeds `isize::MAX` bytes.
1378	///
1379	/// # Examples
1380	///
1381	/// ```
1382	/// use thin_vec::thin_vec;
1383	///
1384	/// let mut vec = thin_vec![`1`, `2`, `3`];
1385	/// let mut vec2 = thin_vec![`4`, `5`, `6`];
1386	/// vec.append(&mut vec2);
1387	/// assert_eq!(vec, [`1`, `2`, `3`, `4`, `5`, `6`]);
1388	/// assert_eq!(vec2, []);
1389	/// ```
1390	pub fn append(&mut self, other: &mut ThinVec<T>) {
1391	self.extend(other.drain(..))
1392	}
1393
1394	/// Removes the specified range from the vector in bulk, returning all
1395	/// removed elements as an iterator. If the iterator is dropped before
1396	/// being fully consumed, it drops the remaining removed elements.
1397	///
1398	/// The returned iterator keeps a mutable borrow on the vector to optimize
1399	/// its implementation.
1400	///
1401	/// # Panics
1402	///
1403	/// Panics if the starting point is greater than the end point or if
1404	/// the end point is greater than the length of the vector.
1405	///
1406	/// # Leaking
1407	///
1408	/// If the returned iterator goes out of scope without being dropped (due to
1409	/// [`mem::forget`], for example), the vector may have lost and leaked
1410	/// elements arbitrarily, including elements outside the range.
1411	///
1412	/// # Examples
1413	///
1414	/// ```
1415	/// use thin_vec::{ThinVec, thin_vec};
1416	///
1417	/// let mut v = thin_vec![`1`, `2`, `3`];
1418	/// let u: ThinVec<_> = v.drain(`1`..).collect();
1419	/// assert_eq!(v, &[`1`]);
1420	/// assert_eq!(u, &[`2`, `3`]);
1421	///
1422	/// // A full range clears the vector, like `clear()` does
1423	/// v.drain(..);
1424	/// assert_eq!(v, &[]);
1425	/// ```
1426	pub fn drain<R>(&mut self, range: R) -> Drain<'_, T>
1427	where
1428	R: RangeBounds<usize>,
1429	{
1430	// See comments in the Drain struct itself for details on this
1431	let len = self.len();
1432	let start = match range.start_bound() {
1433	Bound::Included(&n) => n,
1434	Bound::Excluded(&n) => n + `1`,
1435	Bound::Unbounded => `0`,
1436	};
1437	let end = match range.end_bound() {
1438	Bound::Included(&n) => n + `1`,
1439	Bound::Excluded(&n) => n,
1440	Bound::Unbounded => len,
1441	};
1442	assert!(start <= end);
1443	assert!(end <= len);
1444
1445	unsafe {
1446	// Set our length to the start bound
1447	self.set_len(start); // could be the singleton
1448
1449	let iter =
1450	slice::from_raw_parts_mut(self.data_raw().add(start), end - start).iter_mut();
1451
1452	Drain {
1453	iter,
1454	vec: self,
1455	end,
1456	tail: len - end,
1457	}
1458	}
1459	}
1460
1461	/// Creates a splicing iterator that replaces the specified range in the vector
1462	/// with the given `replace_with` iterator and yields the removed items.
1463	/// `replace_with` does not need to be the same length as `range`.
1464	///
1465	/// `range` is removed even if the iterator is not consumed until the end.
1466	///
1467	/// It is unspecified how many elements are removed from the vector
1468	/// if the `Splice` value is leaked.
1469	///
1470	/// The input iterator `replace_with` is only consumed when the `Splice` value is dropped.
1471	///
1472	/// This is optimal if:
1473	///
1474	/// The tail (elements in the vector after `range`) is empty,*
1475	/// or `replace_with` yields fewer or equal elements than `range`’s length*
1476	/// or the lower bound of its `size_hint()` is exact.*
1477	///
1478	/// Otherwise, a temporary vector is allocated and the tail is moved twice.
1479	///
1480	/// # Panics
1481	///
1482	/// Panics if the starting point is greater than the end point or if
1483	/// the end point is greater than the length of the vector.
1484	///
1485	/// # Examples
1486	///
1487	/// ```
1488	/// use thin_vec::{ThinVec, thin_vec};
1489	///
1490	/// let mut v = thin_vec![`1`, `2`, `3`, `4`];
1491	/// let new = [`7`, `8`, `9`];
1492	/// let u: ThinVec<_> = v.splice(`1`..`3`, new).collect();
1493	/// assert_eq!(v, &[`1`, `7`, `8`, `9`, `4`]);
1494	/// assert_eq!(u, &[`2`, `3`]);
1495	/// ```
1496	#[inline]
1497	pub fn splice<R, I>(&mut self, range: R, replace_with: I) -> Splice<'_, I::IntoIter>
1498	where
1499	R: RangeBounds<usize>,
1500	I: IntoIterator<Item = T>,
1501	{
1502	Splice {
1503	drain: self.drain(range),
1504	replace_with: replace_with.into_iter(),
1505	}
1506	}
1507
1508	/// Resize the buffer and update its capacity, without changing the length.
1509	/// Unsafe because it can cause length to be greater than capacity.
1510	unsafe fn reallocate(&mut self, new_cap: usize) {
1511	debug_assert!(new_cap > `0`);
1512	if self.has_allocation() {
1513	let old_cap = self.capacity();
1514	let ptr = realloc(
1515	self.ptr() as *mut u8,
1516	layout::<T>(old_cap),
1517	alloc_size::<T>(new_cap),
1518	) as *mut Header;
1519
1520	if ptr.is_null() {
1521	handle_alloc_error(layout::<T>(new_cap))
1522	}
1523	(*ptr).set_cap(new_cap);
1524	self.ptr = NonNull::new_unchecked(ptr);
1525	} else {
1526	let new_header = header_with_capacity::<T>(new_cap);
1527
1528	// If we get here and have a non-zero len, then we must be handling
1529	// a gecko auto array, and we have items in a stack buffer. We shouldn't
1530	// free it, but we should memcopy the contents out of it and mark it as empty.
1531	//
1532	// T is assumed to be trivially relocatable, as this is ~required
1533	// for Rust compatibility anyway. Furthermore, we assume C++ won't try
1534	// to unconditionally destroy the contents of the stack allocated buffer
1535	// (i.e. it's obfuscated behind a union).
1536	//
1537	// In effect, we are partially reimplementing the auto array move constructor
1538	// by leaving behind a valid empty instance.
1539	let len = self.len();
1540	if cfg!(feature = "gecko-ffi") && len > `0` {
1541	new_header
1542	.as_ptr()
1543	.add(`1`)
1544	.cast::<T>()
1545	.copy_from_nonoverlapping(self.data_raw(), len);
1546	self.set_len_non_singleton(`0`);
1547	}
1548
1549	self.ptr = new_header;
1550	}
1551	}
1552
1553	#[cfg(feature = "gecko-ffi")]
1554	#[inline]
1555	#[allow(unused_unsafe)]
1556	fn is_singleton(&self) -> bool {
1557	// NOTE: the tests will complain that this "unsafe" isn't needed, but it IS!
1558	// In production this refers to an extern static* which is unsafe to reference.*
1559	// In tests this refers to a local static because we don't have Firefox's codebase
1560	// providing the symbol!
1561	unsafe { self.ptr.as_ptr() as *const Header == &EMPTY_HEADER }
1562	}
1563
1564	#[cfg(not(feature = "gecko-ffi"))]
1565	#[inline]
1566	fn is_singleton(&self) -> bool {
1567	self.ptr.as_ptr() as *const Header == &EMPTY_HEADER
1568	}
1569
1570	#[cfg(feature = "gecko-ffi")]
1571	#[inline]
1572	fn has_allocation(&self) -> bool {
1573	unsafe { !self.is_singleton() && !self.ptr.as_ref().uses_stack_allocated_buffer() }
1574	}
1575
1576	#[cfg(not(feature = "gecko-ffi"))]
1577	#[inline]
1578	fn has_allocation(&self) -> bool {
1579	!self.is_singleton()
1580	}
1581	}
1582
1583	impl<T: Clone> ThinVec<T> {
1584	/// Resizes the `Vec` in-place so that `len()` is equal to `new_len`.
1585	///
1586	/// If `new_len` is greater than `len()`, the `Vec` is extended by the
1587	/// difference, with each additional slot filled with `value`.
1588	/// If `new_len` is less than `len()`, the `Vec` is simply truncated.
1589	///
1590	/// # Examples
1591	///
1592	// A hack to avoid linking problems with `cargo test --features=gecko-ffi`.
1593	#[cfg_attr(not(feature = "gecko-ffi"), doc = "```")]
1594	#[cfg_attr(feature = "gecko-ffi", doc = "```ignore")]
1595	/// # #[macro_use] extern crate thin_vec;
1596	/// # fn main() {
1597	/// let mut vec = thin_vec!["hello"];
1598	/// vec.resize(`3`, "world");
1599	/// assert_eq!(vec, ["hello", "world", "world"]);
1600	///
1601	/// let mut vec = thin_vec![`1`, `2`, `3`, `4`];
1602	/// vec.resize(`2`, `0`);
1603	/// assert_eq!(vec, [`1`, `2`]);
1604	/// # }
1605	/// ```
1606	pub fn resize(&mut self, new_len: usize, value: T) {
1607	let old_len = self.len();
1608
1609	if new_len > old_len {
1610	let additional = new_len - old_len;
1611	self.reserve(additional);
1612	for _ in `1`..additional {
1613	self.push(value.clone());
1614	}
1615	// We can write the last element directly without cloning needlessly
1616	if additional > `0` {
1617	self.push(value);
1618	}
1619	} else if new_len < old_len {
1620	self.truncate(new_len);
1621	}
1622	}
1623
1624	/// Clones and appends all elements in a slice to the `ThinVec`.
1625	///
1626	/// Iterates over the slice `other`, clones each element, and then appends
1627	/// it to this `ThinVec`. The `other` slice is traversed in-order.
1628	///
1629	/// Note that this function is same as [`extend`] except that it is
1630	/// specialized to work with slices instead. If and when Rust gets
1631	/// specialization this function will likely be deprecated (but still
1632	/// available).
1633	///
1634	/// # Examples
1635	///
1636	/// ```
1637	/// use thin_vec::thin_vec;
1638	///
1639	/// let mut vec = thin_vec![`1`];
1640	/// vec.extend_from_slice(&[`2`, `3`, `4`]);
1641	/// assert_eq!(vec, [`1`, `2`, `3`, `4`]);
1642	/// ```
1643	///
1644	/// [`extend`]: ThinVec::extend
1645	pub fn extend_from_slice(&mut self, other: &[T]) {
1646	self.extend(other.iter().cloned())
1647	}
1648	}
1649
1650	impl<T: PartialEq> ThinVec<T> {
1651	/// Removes consecutive repeated elements in the vector.
1652	///
1653	/// If the vector is sorted, this removes all duplicates.
1654	///
1655	/// # Examples
1656	///
1657	// A hack to avoid linking problems with `cargo test --features=gecko-ffi`.
1658	#[cfg_attr(not(feature = "gecko-ffi"), doc = "```")]
1659	#[cfg_attr(feature = "gecko-ffi", doc = "```ignore")]
1660	/// # #[macro_use] extern crate thin_vec;
1661	/// # fn main() {
1662	/// let mut vec = thin_vec![`1`, `2`, `2`, `3`, `2`];
1663	///
1664	/// vec.dedup();
1665	///
1666	/// assert_eq!(vec, [`1`, `2`, `3`, `2`]);
1667	/// # }
1668	/// ```
1669	pub fn dedup(&mut self) {
1670	self.dedup_by(\|a: &mut T, b: &mut T\| a == b)
1671	}
1672	}
1673
1674	impl<T> Drop for ThinVec<T> {
1675	#[inline]
1676	fn drop(&mut self) {
1677	#[cold]
1678	#[inline(never)]
1679	fn drop_non_singleton<T>(this: &mut ThinVec<T>) {
1680	unsafe {
1681	ptr::drop_in_place(&mut this[..]);
1682
1683	#[cfg(feature = "gecko-ffi")]
1684	if this.ptr.as_ref().uses_stack_allocated_buffer() {
1685	return;
1686	}
1687
1688	dealloc(this.ptr() as *mut u8, layout::<T>(cap:this.capacity()))
1689	}
1690	}
1691
1692	if !self.is_singleton() {
1693	drop_non_singleton(self);
1694	}
1695	}
1696	}
1697
1698	impl<T> Deref for ThinVec<T> {
1699	type Target = [T];
1700
1701	fn deref(&self) -> &[T] {
1702	self.as_slice()
1703	}
1704	}
1705
1706	impl<T> DerefMut for ThinVec<T> {
1707	fn deref_mut(&mut self) -> &mut [T] {
1708	self.as_mut_slice()
1709	}
1710	}
1711
1712	impl<T> Borrow<[T]> for ThinVec<T> {
1713	fn borrow(&self) -> &[T] {
1714	self.as_slice()
1715	}
1716	}
1717
1718	impl<T> BorrowMut<[T]> for ThinVec<T> {
1719	fn borrow_mut(&mut self) -> &mut [T] {
1720	self.as_mut_slice()
1721	}
1722	}
1723
1724	impl<T> AsRef<[T]> for ThinVec<T> {
1725	fn as_ref(&self) -> &[T] {
1726	self.as_slice()
1727	}
1728	}
1729
1730	impl<T> Extend<T> for ThinVec<T> {
1731	#[inline]
1732	fn extend<I>(&mut self, iter: I)
1733	where
1734	I: IntoIterator<Item = T>,
1735	{
1736	let iter: ::IntoIter = iter.into_iter();
1737	let hint: usize = iter.size_hint().0;
1738	if hint > `0` {
1739	self.reserve(additional:hint);
1740	}
1741	for x: T in iter {
1742	self.push(val:x);
1743	}
1744	}
1745	}
1746
1747	impl<T: fmt::Debug> fmt::Debug for ThinVec<T> {
1748	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1749	fmt::Debug::fmt(&**self, f)
1750	}
1751	}
1752
1753	impl<T> Hash for ThinVec<T>
1754	where
1755	T: Hash,
1756	{
1757	fn hash<H>(&self, state: &mut H)
1758	where
1759	H: Hasher,
1760	{
1761	self[..].hash(state);
1762	}
1763	}
1764
1765	impl<T> PartialOrd for ThinVec<T>
1766	where
1767	T: PartialOrd,
1768	{
1769	#[inline]
1770	fn partial_cmp(&self, other: &ThinVec<T>) -> Option<Ordering> {
1771	self[..].partial_cmp(&other[..])
1772	}
1773	}
1774
1775	impl<T> Ord for ThinVec<T>
1776	where
1777	T: Ord,
1778	{
1779	#[inline]
1780	fn cmp(&self, other: &ThinVec<T>) -> Ordering {
1781	self[..].cmp(&other[..])
1782	}
1783	}
1784
1785	impl<A, B> PartialEq<ThinVec<B>> for ThinVec<A>
1786	where
1787	A: PartialEq<B>,
1788	{
1789	#[inline]
1790	fn eq(&self, other: &ThinVec<B>) -> bool {
1791	self[..] == other[..]
1792	}
1793	}
1794
1795	impl<A, B> PartialEq<Vec<B>> for ThinVec<A>
1796	where
1797	A: PartialEq<B>,
1798	{
1799	#[inline]
1800	fn eq(&self, other: &Vec<B>) -> bool {
1801	self[..] == other[..]
1802	}
1803	}
1804
1805	impl<A, B> PartialEq<[B]> for ThinVec<A>
1806	where
1807	A: PartialEq<B>,
1808	{
1809	#[inline]
1810	fn eq(&self, other: &[B]) -> bool {
1811	self[..] == other[..]
1812	}
1813	}
1814
1815	impl<'a, A, B> PartialEq<&'a [B]> for ThinVec<A>
1816	where
1817	A: PartialEq<B>,
1818	{
1819	#[inline]
1820	fn eq(&self, other: &&'a [B]) -> bool {
1821	self[..] == other[..]
1822	}
1823	}
1824
1825	// Serde impls based on
1826	// https://github.com/bluss/arrayvec/blob/67ec907a98c0f40c4b76066fed3c1af59d35cf6a/src/arrayvec.rs#L1222-L1267
1827	#[cfg(feature = "serde")]
1828	impl<T: serde::Serialize> serde::Serialize for ThinVec<T> {
1829	fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
1830	where
1831	S: serde::Serializer,
1832	{
1833	serializer.collect_seq(self.as_slice())
1834	}
1835	}
1836
1837	#[cfg(feature = "serde")]
1838	impl<'de, T: serde::Deserialize<'de>> serde::Deserialize<'de> for ThinVec<T> {
1839	fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
1840	where
1841	D: serde::Deserializer<'de>,
1842	{
1843	use serde::de::{SeqAccess, Visitor};
1844	use serde::Deserialize;
1845
1846	struct ThinVecVisitor<T>(PhantomData<T>);
1847
1848	impl<'de, T: Deserialize<'de>> Visitor<'de> for ThinVecVisitor<T> {
1849	type Value = ThinVec<T>;
1850
1851	fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
1852	write!(formatter, "a sequence")
1853	}
1854
1855	fn visit_seq<SA>(self, mut seq: SA) -> Result<Self::Value, SA::Error>
1856	where
1857	SA: SeqAccess<'de>,
1858	{
1859	// Same policy as
1860	// https://github.com/serde-rs/serde/blob/ce0844b9ecc32377b5e4545d759d385a8c46bc6a/serde/src/private/size_hint.rs#L13
1861	let initial_capacity = seq.size_hint().unwrap_or_default().min(`4096`);
1862	let mut values = ThinVec::<T>::with_capacity(initial_capacity);
1863
1864	while let Some(value) = seq.next_element()? {
1865	values.push(value);
1866	}
1867
1868	Ok(values)
1869	}
1870	}
1871
1872	deserializer.deserialize_seq(ThinVecVisitor::<T>(PhantomData))
1873	}
1874	}
1875
1876	macro_rules! array_impls {
1877	($($N:expr)*) => {$(
1878	impl<A, B> PartialEq<[B; $N]> for ThinVec<A> where A: PartialEq<B> {
1879	#[inline]
1880	fn eq(&self, other: &[B; $N]) -> bool { self[..] == other[..] }
1881	}
1882
1883	impl<'a, A, B> PartialEq<&'a [B; $N]> for ThinVec<A> where A: PartialEq<B> {
1884	#[inline]
1885	fn eq(&self, other: &&'a [B; $N]) -> bool { self[..] == other[..] }
1886	}
1887	)*}
1888	}
1889
1890	array_impls! {
1891	`0` `1` `2` `3` `4` `5` `6` `7` `8` `9`
1892	`10` `11` `12` `13` `14` `15` `16` `17` `18` `19`
1893	`20` `21` `22` `23` `24` `25` `26` `27` `28` `29`
1894	`30` `31` `32`
1895	}
1896
1897	impl<T> Eq for ThinVec<T> where T: Eq {}
1898
1899	impl<T> IntoIterator for ThinVec<T> {
1900	type Item = T;
1901	type IntoIter = IntoIter<T>;
1902
1903	fn into_iter(self) -> IntoIter<T> {
1904	IntoIter {
1905	vec: self,
1906	start: `0`,
1907	}
1908	}
1909	}
1910
1911	impl<'a, T> IntoIterator for &'a ThinVec<T> {
1912	type Item = &'a T;
1913	type IntoIter = slice::Iter<'a, T>;
1914
1915	fn into_iter(self) -> slice::Iter<'a, T> {
1916	self.iter()
1917	}
1918	}
1919
1920	impl<'a, T> IntoIterator for &'a mut ThinVec<T> {
1921	type Item = &'a mut T;
1922	type IntoIter = slice::IterMut<'a, T>;
1923
1924	fn into_iter(self) -> slice::IterMut<'a, T> {
1925	self.iter_mut()
1926	}
1927	}
1928
1929	impl<T> Clone for ThinVec<T>
1930	where
1931	T: Clone,
1932	{
1933	#[inline]
1934	fn clone(&self) -> ThinVec<T> {
1935	#[cold]
1936	#[inline(never)]
1937	fn clone_non_singleton<T: Clone>(this: &ThinVec<T>) -> ThinVec<T> {
1938	let len = this.len();
1939	let mut new_vec = ThinVec::<T>::with_capacity(len);
1940	let mut data_raw = new_vec.data_raw();
1941	for x in this.iter() {
1942	unsafe {
1943	ptr::write(data_raw, x.clone());
1944	data_raw = data_raw.add(`1`);
1945	}
1946	}
1947	unsafe {
1948	// `this` is not the singleton, but `new_vec` will be if
1949	// `this` is empty.
1950	new_vec.set_len(len); // could be the singleton
1951	}
1952	new_vec
1953	}
1954
1955	if self.is_singleton() {
1956	ThinVec::new()
1957	} else {
1958	clone_non_singleton(self)
1959	}
1960	}
1961	}
1962
1963	impl<T> Default for ThinVec<T> {
1964	fn default() -> ThinVec<T> {
1965	ThinVec::new()
1966	}
1967	}
1968
1969	impl<T> FromIterator<T> for ThinVec<T> {
1970	#[inline]
1971	fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> ThinVec<T> {
1972	let mut vec: ThinVec = ThinVec::new();
1973	vec.extend(iter);
1974	vec
1975	}
1976	}
1977
1978	impl<T: Clone> From<&[T]> for ThinVec<T> {
1979	/// Allocate a `ThinVec<T>` and fill it by cloning `s`'s items.
1980	///
1981	/// # Examples
1982	///
1983	/// ```
1984	/// use thin_vec::{ThinVec, thin_vec};
1985	///
1986	/// assert_eq!(ThinVec::from(&[`1`, `2`, `3`][..]), thin_vec![`1`, `2`, `3`]);
1987	/// ```
1988	fn from(s: &[T]) -> ThinVec<T> {
1989	s.iter().cloned().collect()
1990	}
1991	}
1992
1993	#[cfg(not(no_global_oom_handling))]
1994	impl<T: Clone> From<&mut [T]> for ThinVec<T> {
1995	/// Allocate a `ThinVec<T>` and fill it by cloning `s`'s items.
1996	///
1997	/// # Examples
1998	///
1999	/// ```
2000	/// use thin_vec::{ThinVec, thin_vec};
2001	///
2002	/// assert_eq!(ThinVec::from(&mut [`1`, `2`, `3`][..]), thin_vec![`1`, `2`, `3`]);
2003	/// ```
2004	fn from(s: &mut [T]) -> ThinVec<T> {
2005	s.iter().cloned().collect()
2006	}
2007	}
2008
2009	impl<T, const N: usize> From<[T; N]> for ThinVec<T> {
2010	/// Allocate a `ThinVec<T>` and move `s`'s items into it.
2011	///
2012	/// # Examples
2013	///
2014	/// ```
2015	/// use thin_vec::{ThinVec, thin_vec};
2016	///
2017	/// assert_eq!(ThinVec::from([`1`, `2`, `3`]), thin_vec![`1`, `2`, `3`]);
2018	/// ```
2019	fn from(s: [T; N]) -> ThinVec<T> {
2020	core::iter::IntoIterator::into_iter(self:s).collect()
2021	}
2022	}
2023
2024	impl<T> From<Box<[T]>> for ThinVec<T> {
2025	/// Convert a boxed slice into a vector by transferring ownership of
2026	/// the existing heap allocation.
2027	///
2028	/// NOTE:* unlike `std`, this must reallocate to change the layout!*
2029	///
2030	/// # Examples
2031	///
2032	/// ```
2033	/// use thin_vec::{ThinVec, thin_vec};
2034	///
2035	/// let b: Box<[i32]> = thin_vec![`1`, `2`, `3`].into_iter().collect();
2036	/// assert_eq!(ThinVec::from(b), thin_vec![`1`, `2`, `3`]);
2037	/// ```
2038	fn from(s: Box<[T]>) -> Self {
2039	// Can just lean on the fact that `Box<[T]>` -> `Vec<T>` is Free.
2040	Vec::from(s).into_iter().collect()
2041	}
2042	}
2043
2044	impl<T> From<Vec<T>> for ThinVec<T> {
2045	/// Convert a `std::Vec` into a `ThinVec`.
2046	///
2047	/// NOTE:* this must reallocate to change the layout!*
2048	///
2049	/// # Examples
2050	///
2051	/// ```
2052	/// use thin_vec::{ThinVec, thin_vec};
2053	///
2054	/// let b: Vec<i32> = vec![`1`, `2`, `3`];
2055	/// assert_eq!(ThinVec::from(b), thin_vec![`1`, `2`, `3`]);
2056	/// ```
2057	fn from(s: Vec<T>) -> Self {
2058	s.into_iter().collect()
2059	}
2060	}
2061
2062	impl<T> From<ThinVec<T>> for Vec<T> {
2063	/// Convert a `ThinVec` into a `std::Vec`.
2064	///
2065	/// NOTE:* this must reallocate to change the layout!*
2066	///
2067	/// # Examples
2068	///
2069	/// ```
2070	/// use thin_vec::{ThinVec, thin_vec};
2071	///
2072	/// let b: ThinVec<i32> = thin_vec![`1`, `2`, `3`];
2073	/// assert_eq!(Vec::from(b), vec![`1`, `2`, `3`]);
2074	/// ```
2075	fn from(s: ThinVec<T>) -> Self {
2076	s.into_iter().collect()
2077	}
2078	}
2079
2080	impl<T> From<ThinVec<T>> for Box<[T]> {
2081	/// Convert a vector into a boxed slice.
2082	///
2083	/// If `v` has excess capacity, its items will be moved into a
2084	/// newly-allocated buffer with exactly the right capacity.
2085	///
2086	/// NOTE:* unlike `std`, this must reallocate to change the layout!*
2087	///
2088	/// # Examples
2089	///
2090	/// ```
2091	/// use thin_vec::{ThinVec, thin_vec};
2092	/// assert_eq!(Box::from(thin_vec![`1`, `2`, `3`]), thin_vec![`1`, `2`, `3`].into_iter().collect());
2093	/// ```
2094	fn from(v: ThinVec<T>) -> Self {
2095	v.into_iter().collect()
2096	}
2097	}
2098
2099	impl From<&str> for ThinVec<u8> {
2100	/// Allocate a `ThinVec<u8>` and fill it with a UTF-8 string.
2101	///
2102	/// # Examples
2103	///
2104	/// ```
2105	/// use thin_vec::{ThinVec, thin_vec};
2106	///
2107	/// assert_eq!(ThinVec::from("123"), thin_vec![b'1', b'2', b'3']);
2108	/// ```
2109	fn from(s: &str) -> ThinVec<u8> {
2110	From::from(s.as_bytes())
2111	}
2112	}
2113
2114	impl<T, const N: usize> TryFrom<ThinVec<T>> for [T; N] {
2115	type Error = ThinVec<T>;
2116
2117	/// Gets the entire contents of the `ThinVec<T>` as an array,
2118	/// if its size exactly matches that of the requested array.
2119	///
2120	/// # Examples
2121	///
2122	/// ```
2123	/// use thin_vec::{ThinVec, thin_vec};
2124	/// use std::convert::TryInto;
2125	///
2126	/// assert_eq!(thin_vec![`1`, `2`, `3`].try_into(), Ok([`1`, `2`, `3`]));
2127	/// assert_eq!(<ThinVec<i32>>::new().try_into(), Ok([]));
2128	/// ```
2129	///
2130	/// If the length doesn't match, the input comes back in `Err`:
2131	/// ```
2132	/// use thin_vec::{ThinVec, thin_vec};
2133	/// use std::convert::TryInto;
2134	///
2135	/// let r: Result<[i32; `4`], _> = (`0`..`10`).collect::<ThinVec<_>>().try_into();
2136	/// assert_eq!(r, Err(thin_vec![`0`, `1`, `2`, `3`, `4`, `5`, `6`, `7`, `8`, `9`]));
2137	/// ```
2138	///
2139	/// If you're fine with just getting a prefix of the `ThinVec<T>`,
2140	/// you can call [`.truncate(N)`](ThinVec::truncate) first.
2141	/// ```
2142	/// use thin_vec::{ThinVec, thin_vec};
2143	/// use std::convert::TryInto;
2144	///
2145	/// let mut v = ThinVec::from("hello world");
2146	/// v.sort();
2147	/// v.truncate(`2`);
2148	/// let [a, b]: [_; `2`] = v.try_into().unwrap();
2149	/// assert_eq!(a, b' ');
2150	/// assert_eq!(b, b'd');
2151	/// ```
2152	fn try_from(mut vec: ThinVec<T>) -> Result<[T; N], ThinVec<T>> {
2153	if vec.len() != N {
2154	return Err(vec);
2155	}
2156
2157	// SAFETY: `.set_len(0)` is always sound.
2158	unsafe { vec.set_len(`0`) };
2159
2160	// SAFETY: A `ThinVec`'s pointer is always aligned properly, and
2161	// the alignment the array needs is the same as the items.
2162	// We checked earlier that we have sufficient items.
2163	// The items will not double-drop as the `set_len`
2164	// tells the `ThinVec` not to also drop them.
2165	let array = unsafe { ptr::read(vec.data_raw() as *const [T; N]) };
2166	Ok(array)
2167	}
2168	}
2169
2170	/// An iterator that moves out of a vector.
2171	///
2172	/// This `struct` is created by the [`ThinVec::into_iter`][]
2173	/// (provided by the [`IntoIterator`] trait).
2174	///
2175	/// # Example
2176	///
2177	/// ```
2178	/// use thin_vec::thin_vec;
2179	///
2180	/// let v = thin_vec![`0`, `1`, `2`];
2181	/// let iter: thin_vec::IntoIter<_> = v.into_iter();
2182	/// ```
2183	pub struct IntoIter<T> {
2184	vec: ThinVec<T>,
2185	start: usize,
2186	}
2187
2188	impl<T> IntoIter<T> {
2189	/// Returns the remaining items of this iterator as a slice.
2190	///
2191	/// # Examples
2192	///
2193	/// ```
2194	/// use thin_vec::thin_vec;
2195	///
2196	/// let vec = thin_vec!['a', 'b', 'c'];
2197	/// let mut into_iter = vec.into_iter();
2198	/// assert_eq!(into_iter.as_slice(), &['a', 'b', 'c']);
2199	/// let _ = into_iter.next().unwrap();
2200	/// assert_eq!(into_iter.as_slice(), &['b', 'c']);
2201	/// ```
2202	pub fn as_slice(&self) -> &[T] {
2203	unsafe { slice::from_raw_parts(self.vec.data_raw().add(self.start), self.len()) }
2204	}
2205
2206	/// Returns the remaining items of this iterator as a mutable slice.
2207	///
2208	/// # Examples
2209	///
2210	/// ```
2211	/// use thin_vec::thin_vec;
2212	///
2213	/// let vec = thin_vec!['a', 'b', 'c'];
2214	/// let mut into_iter = vec.into_iter();
2215	/// assert_eq!(into_iter.as_slice(), &['a', 'b', 'c']);
2216	/// into_iter.as_mut_slice()[`2`] = 'z';
2217	/// assert_eq!(into_iter.next().unwrap(), 'a');
2218	/// assert_eq!(into_iter.next().unwrap(), 'b');
2219	/// assert_eq!(into_iter.next().unwrap(), 'z');
2220	/// ```
2221	pub fn as_mut_slice(&mut self) -> &mut [T] {
2222	unsafe { &mut *self.as_raw_mut_slice() }
2223	}
2224
2225	fn as_raw_mut_slice(&mut self) -> *mut [T] {
2226	unsafe { ptr::slice_from_raw_parts_mut(self.vec.data_raw().add(self.start), self.len()) }
2227	}
2228	}
2229
2230	impl<T> Iterator for IntoIter<T> {
2231	type Item = T;
2232	fn next(&mut self) -> Option<T> {
2233	if self.start == self.vec.len() {
2234	None
2235	} else {
2236	unsafe {
2237	let old_start: usize = self.start;
2238	self.start += `1`;
2239	Some(ptr::read(self.vec.data_raw().add(count:old_start)))
2240	}
2241	}
2242	}
2243
2244	fn size_hint(&self) -> (usize, Option<usize>) {
2245	let len: usize = self.vec.len() - self.start;
2246	(len, Some(len))
2247	}
2248	}
2249
2250	impl<T> DoubleEndedIterator for IntoIter<T> {
2251	fn next_back(&mut self) -> Option<T> {
2252	if self.start == self.vec.len() {
2253	None
2254	} else {
2255	self.vec.pop()
2256	}
2257	}
2258	}
2259
2260	impl<T> ExactSizeIterator for IntoIter<T> {}
2261
2262	impl<T> core::iter::FusedIterator for IntoIter<T> {}
2263
2264	// SAFETY: the length calculation is trivial, we're an array! And if it's wrong we're So Screwed.
2265	#[cfg(feature = "unstable")]
2266	unsafe impl<T> core::iter::TrustedLen for IntoIter<T> {}
2267
2268	impl<T> Drop for IntoIter<T> {
2269	#[inline]
2270	fn drop(&mut self) {
2271	#[cold]
2272	#[inline(never)]
2273	fn drop_non_singleton<T>(this: &mut IntoIter<T>) {
2274	unsafe {
2275	let mut vec: ThinVec = mem::replace(&mut this.vec, src:ThinVec::new());
2276	ptr::drop_in_place(&mut vec[this.start..]);
2277	vec.set_len_non_singleton(len:`0`)
2278	}
2279	}
2280
2281	if !self.vec.is_singleton() {
2282	drop_non_singleton(self);
2283	}
2284	}
2285	}
2286
2287	impl<T: fmt::Debug> fmt::Debug for IntoIter<T> {
2288	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2289	f.debug_tuple(name:"IntoIter").field(&self.as_slice()).finish()
2290	}
2291	}
2292
2293	impl<T> AsRef<[T]> for IntoIter<T> {
2294	fn as_ref(&self) -> &[T] {
2295	self.as_slice()
2296	}
2297	}
2298
2299	impl<T: Clone> Clone for IntoIter<T> {
2300	#[allow(clippy::into_iter_on_ref)]
2301	fn clone(&self) -> Self {
2302	// Just create a new `ThinVec` from the remaining elements and IntoIter it
2303	self.as_slice()
2304	.into_iter()
2305	.cloned()
2306	.collect::<ThinVec<_>>()
2307	.into_iter()
2308	}
2309	}
2310
2311	/// A draining iterator for `ThinVec<T>`.
2312	///
2313	/// This `struct` is created by [`ThinVec::drain`].
2314	/// See its documentation for more.
2315	///
2316	/// # Example
2317	///
2318	/// ```
2319	/// use thin_vec::thin_vec;
2320	///
2321	/// let mut v = thin_vec![`0`, `1`, `2`];
2322	/// let iter: thin_vec::Drain<_> = v.drain(..);
2323	/// ```
2324	pub struct Drain<'a, T> {
2325	// Ok so ThinVec::drain takes a range of the ThinVec and yields the contents by-value,
2326	// then backshifts the array. During iteration the array is in an unsound state
2327	// (big deinitialized hole in it), and this is very dangerous.
2328	//
2329	// Our first line of defense is the borrow checker: we have a mutable borrow, so nothing
2330	// can access the ThinVec while we exist. As long as we make sure the ThinVec is in a valid
2331	// state again before we release the borrow, everything should be A-OK! We do this cleanup
2332	// in our Drop impl.
2333	//
2334	// Unfortunately, that's unsound, because mem::forget exists and The Leakpocalypse Is Real.
2335	// So we can't actually guarantee our destructor runs before our borrow expires. Thankfully
2336	// this isn't fatal: we can just set the ThinVec's len to 0 at the start, so if anyone
2337	// leaks the Drain, we just leak everything the ThinVec contained out of spite! If they
2338	// don't* leak us then we can properly repair the len in our Drop impl. This is known*
2339	// as "leak amplification", and is the same approach std uses.
2340	//
2341	// But we can do slightly better than setting the len to 0! The drain breaks us up into
2342	// these parts:
2343	//
2344	// ```text
2345	//
2346	// [A, B, C, D, E, F, G, H, _, _]
2347	// ____ __________ ____ ____
2348	// \| \| \| \|
2349	// prefix drain tail spare-cap
2350	// ```
2351	//
2352	// As the drain iterator is consumed from both ends (DoubleEnded!), we'll start to look
2353	// like this:
2354	//
2355	// ```text
2356	// [A, B, _, _, E, _, G, H, _, _]
2357	// ____ __________ ____ ____
2358	// \| \| \| \|
2359	// prefix drain tail spare-cap
2360	// ```
2361	//
2362	// Note that the prefix is always valid and untouched, as such we can set the len
2363	// to the prefix when doing leak-amplification. As a bonus, we can use this value
2364	// to remember where the drain range starts. At the end we'll look like this
2365	// (we exhaust ourselves in our Drop impl):
2366	//
2367	// ```text
2368	// [A, B, _, _, _, _, G, H, _, _]
2369	// _____ __________ _____ ____
2370	// \| \| \| \|
2371	// len drain tail spare-cap
2372	// ```
2373	//
2374	// And need to become this:
2375	//
2376	// ```text
2377	// [A, B, G, H, _, _, _, _, _, _]
2378	// ___________ ________________
2379	// \| \|
2380	// len spare-cap
2381	// ```
2382	//
2383	// All this requires is moving the tail back to the prefix (stored in `len`)
2384	// and setting `len` to `len + tail_len` to undo the leak amplification.
2385	/// An iterator over the elements we're removing.
2386	///
2387	/// As we go we'll be `read`ing out of the mutable refs yielded by this.
2388	/// It's ok to use IterMut here because it promises to only take mutable
2389	/// refs to the parts we haven't yielded yet.
2390	///
2391	/// A downside of this (and the mut below) is that it makes this type invariant, when*
2392	/// technically it could be covariant?
2393	iter: IterMut<'a, T>,
2394	/// The actual ThinVec, which we need to hold onto to undo the leak amplification
2395	/// and backshift the tail into place. This should only be accessed when we're
2396	/// completely done with the IterMut in the `drop` impl of this type (or miri will get mad).
2397	///
2398	/// Since we set the `len` of this to be before `IterMut`, we can use that `len`
2399	/// to retrieve the index of the start of the drain range later.
2400	vec: *mut ThinVec<T>,
2401	/// The one-past-the-end index of the drain range, or equivalently the start of the tail.
2402	end: usize,
2403	/// The length of the tail.
2404	tail: usize,
2405	}
2406
2407	impl<'a, T> Iterator for Drain<'a, T> {
2408	type Item = T;
2409	fn next(&mut self) -> Option<T> {
2410	self.iter.next().map(\|x: &'a mut T\| unsafe { ptr::read(src:x) })
2411	}
2412
2413	fn size_hint(&self) -> (usize, Option<usize>) {
2414	self.iter.size_hint()
2415	}
2416	}
2417
2418	impl<'a, T> DoubleEndedIterator for Drain<'a, T> {
2419	fn next_back(&mut self) -> Option<T> {
2420	self.iter.next_back().map(\|x: &'a mut T\| unsafe { ptr::read(src:x) })
2421	}
2422	}
2423
2424	impl<'a, T> ExactSizeIterator for Drain<'a, T> {}
2425
2426	// SAFETY: we need to keep track of this perfectly Or Else anyway!
2427	#[cfg(feature = "unstable")]
2428	unsafe impl<T> core::iter::TrustedLen for Drain<'_, T> {}
2429
2430	impl<T> core::iter::FusedIterator for Drain<'_, T> {}
2431
2432	impl<'a, T> Drop for Drain<'a, T> {
2433	fn drop(&mut self) {
2434	// Consume the rest of the iterator.
2435	for _ in self.by_ref() {}
2436
2437	// Move the tail over the drained items, and update the length.
2438	unsafe {
2439	let vec: &mut ThinVec = &mut *self.vec;
2440
2441	// Don't mutate the empty singleton!
2442	if !vec.is_singleton() {
2443	let old_len: usize = vec.len();
2444	let start: *mut T = vec.data_raw().add(count:old_len);
2445	let end: *mut T = vec.data_raw().add(self.end);
2446	ptr::copy(src:end, dst:start, self.tail);
2447	vec.set_len_non_singleton(len:old_len + self.tail);
2448	}
2449	}
2450	}
2451	}
2452
2453	impl<T: fmt::Debug> fmt::Debug for Drain<'_, T> {
2454	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2455	f.debug_tuple(name:"Drain").field(&self.iter.as_slice()).finish()
2456	}
2457	}
2458
2459	impl<'a, T> Drain<'a, T> {
2460	/// Returns the remaining items of this iterator as a slice.
2461	///
2462	/// # Examples
2463	///
2464	/// ```
2465	/// use thin_vec::thin_vec;
2466	///
2467	/// let mut vec = thin_vec!['a', 'b', 'c'];
2468	/// let mut drain = vec.drain(..);
2469	/// assert_eq!(drain.as_slice(), &['a', 'b', 'c']);
2470	/// let _ = drain.next().unwrap();
2471	/// assert_eq!(drain.as_slice(), &['b', 'c']);
2472	/// ```
2473	#[must_use]
2474	pub fn as_slice(&self) -> &[T] {
2475	// SAFETY: this is A-OK because the elements that the underlying
2476	// iterator still points at are still logically initialized and contiguous.
2477	self.iter.as_slice()
2478	}
2479	}
2480
2481	impl<'a, T> AsRef<[T]> for Drain<'a, T> {
2482	fn as_ref(&self) -> &[T] {
2483	self.as_slice()
2484	}
2485	}
2486
2487	/// A splicing iterator for `ThinVec`.
2488	///
2489	/// This struct is created by [`ThinVec::splice`][].
2490	/// See its documentation for more.
2491	///
2492	/// # Example
2493	///
2494	/// ```
2495	/// use thin_vec::thin_vec;
2496	///
2497	/// let mut v = thin_vec![`0`, `1`, `2`];
2498	/// let new = [`7`, `8`];
2499	/// let iter: thin_vec::Splice<_> = v.splice(`1`.., new);
2500	/// ```
2501	#[derive(Debug)]
2502	pub struct Splice<'a, I: Iterator + 'a> {
2503	drain: Drain<'a, I::Item>,
2504	replace_with: I,
2505	}
2506
2507	impl<I: Iterator> Iterator for Splice<'_, I> {
2508	type Item = I::Item;
2509
2510	fn next(&mut self) -> Option<Self::Item> {
2511	self.drain.next()
2512	}
2513
2514	fn size_hint(&self) -> (usize, Option<usize>) {
2515	self.drain.size_hint()
2516	}
2517	}
2518
2519	impl<I: Iterator> DoubleEndedIterator for Splice<'_, I> {
2520	fn next_back(&mut self) -> Option<Self::Item> {
2521	self.drain.next_back()
2522	}
2523	}
2524
2525	impl<I: Iterator> ExactSizeIterator for Splice<'_, I> {}
2526
2527	impl<I: Iterator> Drop for Splice<'_, I> {
2528	fn drop(&mut self) {
2529	// Ensure we've fully drained out the range
2530	self.drain.by_ref().for_each(drop);
2531
2532	unsafe {
2533	// If there's no tail elements, then the inner ThinVec is already
2534	// correct and we can just extend it like normal.
2535	if self.drain.tail == `0` {
2536	(*self.drain.vec).extend(self.replace_with.by_ref());
2537	return;
2538	}
2539
2540	// First fill the range left by drain().
2541	if !self.drain.fill(&mut self.replace_with) {
2542	return;
2543	}
2544
2545	// There may be more elements. Use the lower bound as an estimate.
2546	let (lower_bound, _upper_bound) = self.replace_with.size_hint();
2547	if lower_bound > `0` {
2548	self.drain.move_tail(lower_bound);
2549	if !self.drain.fill(&mut self.replace_with) {
2550	return;
2551	}
2552	}
2553
2554	// Collect any remaining elements.
2555	// This is a zero-length vector which does not allocate if `lower_bound` was exact.
2556	let mut collected = self
2557	.replace_with
2558	.by_ref()
2559	.collect::<Vec<I::Item>>()
2560	.into_iter();
2561	// Now we have an exact count.
2562	if collected.len() > `0` {
2563	self.drain.move_tail(collected.len());
2564	let filled = self.drain.fill(&mut collected);
2565	debug_assert!(filled);
2566	debug_assert_eq!(collected.len(), `0`);
2567	}
2568	}
2569	// Let `Drain::drop` move the tail back if necessary and restore `vec.len`.
2570	}
2571	}
2572
2573	/// Private helper methods for `Splice::drop`
2574	impl<T> Drain<'_, T> {
2575	/// The range from `self.vec.len` to `self.tail_start` contains elements
2576	/// that have been moved out.
2577	/// Fill that range as much as possible with new elements from the `replace_with` iterator.
2578	/// Returns `true` if we filled the entire range. (`replace_with.next()` didn’t return `None`.)
2579	unsafe fn fill<I: Iterator<Item = T>>(&mut self, replace_with: &mut I) -> bool {
2580	let vec = unsafe { &mut *self.vec };
2581	let range_start = vec.len();
2582	let range_end = self.end;
2583	let range_slice = unsafe {
2584	slice::from_raw_parts_mut(vec.data_raw().add(range_start), range_end - range_start)
2585	};
2586
2587	for place in range_slice {
2588	if let Some(new_item) = replace_with.next() {
2589	unsafe { ptr::write(place, new_item) };
2590	vec.set_len(vec.len() + `1`);
2591	} else {
2592	return `false`;
2593	}
2594	}
2595	`true`
2596	}
2597
2598	/// Makes room for inserting more elements before the tail.
2599	unsafe fn move_tail(&mut self, additional: usize) {
2600	let vec = unsafe { &mut *self.vec };
2601	let len = self.end + self.tail;
2602	vec.reserve(len.checked_add(additional).expect("capacity overflow"));
2603
2604	let new_tail_start = self.end + additional;
2605	unsafe {
2606	let src = vec.data_raw().add(self.end);
2607	let dst = vec.data_raw().add(new_tail_start);
2608	ptr::copy(src, dst, self.tail);
2609	}
2610	self.end = new_tail_start;
2611	}
2612	}
2613
2614	/// Write is implemented for `ThinVec<u8>` by appending to the vector.
2615	/// The vector will grow as needed.
2616	/// This implementation is identical to the one for `Vec<u8>`.
2617	#[cfg(feature = "std")]
2618	impl std::io::Write for ThinVec<u8> {
2619	#[inline]
2620	fn write(&mut self, buf: &[u8]) -> std::io::Result<usize> {
2621	self.extend_from_slice(buf);
2622	Ok(buf.len())
2623	}
2624
2625	#[inline]
2626	fn write_all(&mut self, buf: &[u8]) -> std::io::Result<()> {
2627	self.extend_from_slice(buf);
2628	Ok(())
2629	}
2630
2631	#[inline]
2632	fn flush(&mut self) -> std::io::Result<()> {
2633	Ok(())
2634	}
2635	}
2636
2637	// TODO: a million Index impls
2638
2639	#[cfg(test)]
2640	mod tests {
2641	use super::{ThinVec, MAX_CAP};
2642	use crate::alloc::{string::ToString, vec};
2643
2644	#[test]
2645	fn test_size_of() {
2646	use core::mem::size_of;
2647	assert_eq!(size_of::<ThinVec<u8>>(), size_of::<&u8>());
2648
2649	assert_eq!(size_of::<Option<ThinVec<u8>>>(), size_of::<&u8>());
2650	}
2651
2652	#[test]
2653	fn test_drop_empty() {
2654	ThinVec::<u8>::new();
2655	}
2656
2657	#[test]
2658	fn test_data_ptr_alignment() {
2659	let v = ThinVec::<u16>::new();
2660	assert!(v.data_raw() as usize % `2` == `0`);
2661
2662	let v = ThinVec::<u32>::new();
2663	assert!(v.data_raw() as usize % `4` == `0`);
2664
2665	let v = ThinVec::<u64>::new();
2666	assert!(v.data_raw() as usize % `8` == `0`);
2667	}
2668
2669	#[test]
2670	#[cfg_attr(feature = "gecko-ffi", should_panic)]
2671	fn test_overaligned_type_is_rejected_for_gecko_ffi_mode() {
2672	#[repr(align(`16`))]
2673	struct Align16(u8);
2674
2675	let v = ThinVec::<Align16>::new();
2676	assert!(v.data_raw() as usize % `16` == `0`);
2677	}
2678
2679	#[test]
2680	fn test_partial_eq() {
2681	assert_eq!(thin_vec![`0`], thin_vec![`0`]);
2682	assert_ne!(thin_vec![`0`], thin_vec![`1`]);
2683	assert_eq!(thin_vec![`1`, `2`, `3`], vec![`1`, `2`, `3`]);
2684	}
2685
2686	#[test]
2687	fn test_alloc() {
2688	let mut v = ThinVec::new();
2689	assert!(!v.has_allocation());
2690	v.push(`1`);
2691	assert!(v.has_allocation());
2692	v.pop();
2693	assert!(v.has_allocation());
2694	v.shrink_to_fit();
2695	assert!(!v.has_allocation());
2696	v.reserve(`64`);
2697	assert!(v.has_allocation());
2698	v = ThinVec::with_capacity(`64`);
2699	assert!(v.has_allocation());
2700	v = ThinVec::with_capacity(`0`);
2701	assert!(!v.has_allocation());
2702	}
2703
2704	#[test]
2705	fn test_drain_items() {
2706	let mut vec = thin_vec![`1`, `2`, `3`];
2707	let mut vec2 = thin_vec![];
2708	for i in vec.drain(..) {
2709	vec2.push(i);
2710	}
2711	assert_eq!(vec, []);
2712	assert_eq!(vec2, [`1`, `2`, `3`]);
2713	}
2714
2715	#[test]
2716	fn test_drain_items_reverse() {
2717	let mut vec = thin_vec![`1`, `2`, `3`];
2718	let mut vec2 = thin_vec![];
2719	for i in vec.drain(..).rev() {
2720	vec2.push(i);
2721	}
2722	assert_eq!(vec, []);
2723	assert_eq!(vec2, [`3`, `2`, `1`]);
2724	}
2725
2726	#[test]
2727	fn test_drain_items_zero_sized() {
2728	let mut vec = thin_vec![(), (), ()];
2729	let mut vec2 = thin_vec![];
2730	for i in vec.drain(..) {
2731	vec2.push(i);
2732	}
2733	assert_eq!(vec, []);
2734	assert_eq!(vec2, [(), (), ()]);
2735	}
2736
2737	#[test]
2738	#[should_panic]
2739	fn test_drain_out_of_bounds() {
2740	let mut v = thin_vec![`1`, `2`, `3`, `4`, `5`];
2741	v.drain(`5`..`6`);
2742	}
2743
2744	#[test]
2745	fn test_drain_range() {
2746	let mut v = thin_vec![`1`, `2`, `3`, `4`, `5`];
2747	for _ in v.drain(`4`..) {}
2748	assert_eq!(v, &[`1`, `2`, `3`, `4`]);
2749
2750	let mut v: ThinVec<_> = (`1`..`6`).map(\|x\| x.to_string()).collect();
2751	for _ in v.drain(`1`..`4`) {}
2752	assert_eq!(v, &[`1`.to_string(), `5`.to_string()]);
2753
2754	let mut v: ThinVec<_> = (`1`..`6`).map(\|x\| x.to_string()).collect();
2755	for _ in v.drain(`1`..`4`).rev() {}
2756	assert_eq!(v, &[`1`.to_string(), `5`.to_string()]);
2757
2758	let mut v: ThinVec<_> = thin_vec![(); `5`];
2759	for _ in v.drain(`1`..`4`).rev() {}
2760	assert_eq!(v, &[(), ()]);
2761	}
2762
2763	#[test]
2764	fn test_drain_max_vec_size() {
2765	let mut v = ThinVec::<()>::with_capacity(MAX_CAP);
2766	unsafe {
2767	v.set_len(MAX_CAP);
2768	}
2769	for _ in v.drain(MAX_CAP - `1`..) {}
2770	assert_eq!(v.len(), MAX_CAP - `1`);
2771	}
2772
2773	#[test]
2774	fn test_clear() {
2775	let mut v = ThinVec::<i32>::new();
2776	assert_eq!(v.len(), `0`);
2777	assert_eq!(v.capacity(), `0`);
2778	assert_eq!(&v[..], &[]);
2779
2780	v.clear();
2781	assert_eq!(v.len(), `0`);
2782	assert_eq!(v.capacity(), `0`);
2783	assert_eq!(&v[..], &[]);
2784
2785	v.push(`1`);
2786	v.push(`2`);
2787	assert_eq!(v.len(), `2`);
2788	assert!(v.capacity() >= `2`);
2789	assert_eq!(&v[..], &[`1`, `2`]);
2790
2791	v.clear();
2792	assert_eq!(v.len(), `0`);
2793	assert!(v.capacity() >= `2`);
2794	assert_eq!(&v[..], &[]);
2795
2796	v.push(`3`);
2797	v.push(`4`);
2798	assert_eq!(v.len(), `2`);
2799	assert!(v.capacity() >= `2`);
2800	assert_eq!(&v[..], &[`3`, `4`]);
2801
2802	v.clear();
2803	assert_eq!(v.len(), `0`);
2804	assert!(v.capacity() >= `2`);
2805	assert_eq!(&v[..], &[]);
2806
2807	v.clear();
2808	assert_eq!(v.len(), `0`);
2809	assert!(v.capacity() >= `2`);
2810	assert_eq!(&v[..], &[]);
2811	}
2812
2813	#[test]
2814	fn test_empty_singleton_torture() {
2815	{
2816	let mut v = ThinVec::<i32>::new();
2817	assert_eq!(v.len(), `0`);
2818	assert_eq!(v.capacity(), `0`);
2819	assert!(v.is_empty());
2820	assert_eq!(&v[..], &[]);
2821	assert_eq!(&mut v[..], &mut []);
2822
2823	assert_eq!(v.pop(), None);
2824	assert_eq!(v.len(), `0`);
2825	assert_eq!(v.capacity(), `0`);
2826	assert_eq!(&v[..], &[]);
2827	}
2828
2829	{
2830	let v = ThinVec::<i32>::new();
2831	assert_eq!(v.into_iter().count(), `0`);
2832
2833	let v = ThinVec::<i32>::new();
2834	#[allow(clippy::never_loop)]
2835	for _ in v.into_iter() {
2836	unreachable!();
2837	}
2838	}
2839
2840	{
2841	let mut v = ThinVec::<i32>::new();
2842	assert_eq!(v.drain(..).len(), `0`);
2843
2844	#[allow(clippy::never_loop)]
2845	for _ in v.drain(..) {
2846	unreachable!()
2847	}
2848
2849	assert_eq!(v.len(), `0`);
2850	assert_eq!(v.capacity(), `0`);
2851	assert_eq!(&v[..], &[]);
2852	}
2853
2854	{
2855	let mut v = ThinVec::<i32>::new();
2856	assert_eq!(v.splice(.., []).len(), `0`);
2857
2858	#[allow(clippy::never_loop)]
2859	for _ in v.splice(.., []) {
2860	unreachable!()
2861	}
2862
2863	assert_eq!(v.len(), `0`);
2864	assert_eq!(v.capacity(), `0`);
2865	assert_eq!(&v[..], &[]);
2866	}
2867
2868	{
2869	let mut v = ThinVec::<i32>::new();
2870	v.truncate(`1`);
2871	assert_eq!(v.len(), `0`);
2872	assert_eq!(v.capacity(), `0`);
2873	assert_eq!(&v[..], &[]);
2874
2875	v.truncate(`0`);
2876	assert_eq!(v.len(), `0`);
2877	assert_eq!(v.capacity(), `0`);
2878	assert_eq!(&v[..], &[]);
2879	}
2880
2881	{
2882	let mut v = ThinVec::<i32>::new();
2883	v.shrink_to_fit();
2884	assert_eq!(v.len(), `0`);
2885	assert_eq!(v.capacity(), `0`);
2886	assert_eq!(&v[..], &[]);
2887	}
2888
2889	{
2890	let mut v = ThinVec::<i32>::new();
2891	let new = v.split_off(`0`);
2892	assert_eq!(v.len(), `0`);
2893	assert_eq!(v.capacity(), `0`);
2894	assert_eq!(&v[..], &[]);
2895
2896	assert_eq!(new.len(), `0`);
2897	assert_eq!(new.capacity(), `0`);
2898	assert_eq!(&new[..], &[]);
2899	}
2900
2901	{
2902	let mut v = ThinVec::<i32>::new();
2903	let mut other = ThinVec::<i32>::new();
2904	v.append(&mut other);
2905
2906	assert_eq!(v.len(), `0`);
2907	assert_eq!(v.capacity(), `0`);
2908	assert_eq!(&v[..], &[]);
2909
2910	assert_eq!(other.len(), `0`);
2911	assert_eq!(other.capacity(), `0`);
2912	assert_eq!(&other[..], &[]);
2913	}
2914
2915	{
2916	let mut v = ThinVec::<i32>::new();
2917	v.reserve(`0`);
2918
2919	assert_eq!(v.len(), `0`);
2920	assert_eq!(v.capacity(), `0`);
2921	assert_eq!(&v[..], &[]);
2922	}
2923
2924	{
2925	let mut v = ThinVec::<i32>::new();
2926	v.reserve_exact(`0`);
2927
2928	assert_eq!(v.len(), `0`);
2929	assert_eq!(v.capacity(), `0`);
2930	assert_eq!(&v[..], &[]);
2931	}
2932
2933	{
2934	let mut v = ThinVec::<i32>::new();
2935	v.reserve(`0`);
2936
2937	assert_eq!(v.len(), `0`);
2938	assert_eq!(v.capacity(), `0`);
2939	assert_eq!(&v[..], &[]);
2940	}
2941
2942	{
2943	let v = ThinVec::<i32>::with_capacity(`0`);
2944
2945	assert_eq!(v.len(), `0`);
2946	assert_eq!(v.capacity(), `0`);
2947	assert_eq!(&v[..], &[]);
2948	}
2949
2950	{
2951	let v = ThinVec::<i32>::default();
2952
2953	assert_eq!(v.len(), `0`);
2954	assert_eq!(v.capacity(), `0`);
2955	assert_eq!(&v[..], &[]);
2956	}
2957
2958	{
2959	let mut v = ThinVec::<i32>::new();
2960	v.retain(\|_\| unreachable!());
2961
2962	assert_eq!(v.len(), `0`);
2963	assert_eq!(v.capacity(), `0`);
2964	assert_eq!(&v[..], &[]);
2965	}
2966
2967	{
2968	let mut v = ThinVec::<i32>::new();
2969	v.retain_mut(\|_\| unreachable!());
2970
2971	assert_eq!(v.len(), `0`);
2972	assert_eq!(v.capacity(), `0`);
2973	assert_eq!(&v[..], &[]);
2974	}
2975
2976	{
2977	let mut v = ThinVec::<i32>::new();
2978	v.dedup_by_key(\|x\| *x);
2979
2980	assert_eq!(v.len(), `0`);
2981	assert_eq!(v.capacity(), `0`);
2982	assert_eq!(&v[..], &[]);
2983	}
2984
2985	{
2986	let mut v = ThinVec::<i32>::new();
2987	v.dedup_by(\|_, _\| unreachable!());
2988
2989	assert_eq!(v.len(), `0`);
2990	assert_eq!(v.capacity(), `0`);
2991	assert_eq!(&v[..], &[]);
2992	}
2993
2994	{
2995	let v = ThinVec::<i32>::new();
2996	let v = v.clone();
2997
2998	assert_eq!(v.len(), `0`);
2999	assert_eq!(v.capacity(), `0`);
3000	assert_eq!(&v[..], &[]);
3001	}
3002	}
3003
3004	#[test]
3005	fn test_clone() {
3006	let mut v = ThinVec::<i32>::new();
3007	assert!(v.is_singleton());
3008	v.push(`0`);
3009	v.pop();
3010	assert!(!v.is_singleton());
3011
3012	let v2 = v.clone();
3013	assert!(v2.is_singleton());
3014	}
3015	}
3016
3017	#[cfg(test)]
3018	mod std_tests {
3019	#![allow(clippy::reversed_empty_ranges)]
3020
3021	use super::*;
3022	use crate::alloc::{
3023	format,
3024	string::{String, ToString},
3025	};
3026	use core::mem::size_of;
3027	use core::usize;
3028
3029	struct DropCounter<'a> {
3030	count: &'a mut u32,
3031	}
3032
3033	impl<'a> Drop for DropCounter<'a> {
3034	fn drop(&mut self) {
3035	*self.count += `1`;
3036	}
3037	}
3038
3039	#[test]
3040	fn test_small_vec_struct() {
3041	assert!(size_of::<ThinVec<u8>>() == size_of::<usize>());
3042	}
3043
3044	#[test]
3045	fn test_double_drop() {
3046	struct TwoVec<T> {
3047	x: ThinVec<T>,
3048	y: ThinVec<T>,
3049	}
3050
3051	let (mut count_x, mut count_y) = (`0`, `0`);
3052	{
3053	let mut tv = TwoVec {
3054	x: ThinVec::new(),
3055	y: ThinVec::new(),
3056	};
3057	tv.x.push(DropCounter {
3058	count: &mut count_x,
3059	});
3060	tv.y.push(DropCounter {
3061	count: &mut count_y,
3062	});
3063
3064	// If ThinVec had a drop flag, here is where it would be zeroed.
3065	// Instead, it should rely on its internal state to prevent
3066	// doing anything significant when dropped multiple times.
3067	drop(tv.x);
3068
3069	// Here tv goes out of scope, tv.y should be dropped, but not tv.x.
3070	}
3071
3072	assert_eq!(count_x, `1`);
3073	assert_eq!(count_y, `1`);
3074	}
3075
3076	#[test]
3077	fn test_reserve() {
3078	let mut v = ThinVec::new();
3079	assert_eq!(v.capacity(), `0`);
3080
3081	v.reserve(`2`);
3082	assert!(v.capacity() >= `2`);
3083
3084	for i in `0`..`16` {
3085	v.push(i);
3086	}
3087
3088	assert!(v.capacity() >= `16`);
3089	v.reserve(`16`);
3090	assert!(v.capacity() >= `32`);
3091
3092	v.push(`16`);
3093
3094	v.reserve(`16`);
3095	assert!(v.capacity() >= `33`)
3096	}
3097
3098	#[test]
3099	fn test_extend() {
3100	let mut v = ThinVec::<usize>::new();
3101	let mut w = ThinVec::new();
3102	v.extend(w.clone());
3103	assert_eq!(v, &[]);
3104
3105	v.extend(`0`..`3`);
3106	for i in `0`..`3` {
3107	w.push(i)
3108	}
3109
3110	assert_eq!(v, w);
3111
3112	v.extend(`3`..`10`);
3113	for i in `3`..`10` {
3114	w.push(i)
3115	}
3116
3117	assert_eq!(v, w);
3118
3119	v.extend(w.clone()); // specializes to `append`
3120	assert!(v.iter().eq(w.iter().chain(w.iter())));
3121
3122	// Zero sized types
3123	#[derive(PartialEq, Debug)]
3124	struct Foo;
3125
3126	let mut a = ThinVec::new();
3127	let b = thin_vec![Foo, Foo];
3128
3129	a.extend(b);
3130	assert_eq!(a, &[Foo, Foo]);
3131
3132	// Double drop
3133	let mut count_x = `0`;
3134	{
3135	let mut x = ThinVec::new();
3136	let y = thin_vec![DropCounter {
3137	count: &mut count_x
3138	}];
3139	x.extend(y);
3140	}
3141
3142	assert_eq!(count_x, `1`);
3143	}
3144
3145	/ TODO: implement extend for Iter<&Copy>*
3146	#[test]
3147	fn test_extend_ref() {
3148	let mut v = thin_vec![1, 2];
3149	v.extend(&[3, 4, 5]);
3150
3151	assert_eq!(v.len(), 5);
3152	assert_eq!(v, [1, 2, 3, 4, 5]);
3153
3154	let w = thin_vec![6, 7];
3155	v.extend(&w);
3156
3157	assert_eq!(v.len(), 7);
3158	assert_eq!(v, [1, 2, 3, 4, 5, 6, 7]);
3159	}
3160	*/
3161
3162	#[test]
3163	fn test_slice_from_mut() {
3164	let mut values = thin_vec![`1`, `2`, `3`, `4`, `5`];
3165	{
3166	let slice = &mut values[`2`..];
3167	assert!(slice == [`3`, `4`, `5`]);
3168	for p in slice {
3169	*p += `2`;
3170	}
3171	}
3172
3173	assert!(values == [`1`, `2`, `5`, `6`, `7`]);
3174	}
3175
3176	#[test]
3177	fn test_slice_to_mut() {
3178	let mut values = thin_vec![`1`, `2`, `3`, `4`, `5`];
3179	{
3180	let slice = &mut values[..`2`];
3181	assert!(slice == [`1`, `2`]);
3182	for p in slice {
3183	*p += `1`;
3184	}
3185	}
3186
3187	assert!(values == [`2`, `3`, `3`, `4`, `5`]);
3188	}
3189
3190	#[test]
3191	fn test_split_at_mut() {
3192	let mut values = thin_vec![`1`, `2`, `3`, `4`, `5`];
3193	{
3194	let (left, right) = values.split_at_mut(`2`);
3195	{
3196	let left: &[_] = left;
3197	assert!(left[..left.len()] == [`1`, `2`]);
3198	}
3199	for p in left {
3200	*p += `1`;
3201	}
3202
3203	{
3204	let right: &[_] = right;
3205	assert!(right[..right.len()] == [`3`, `4`, `5`]);
3206	}
3207	for p in right {
3208	*p += `2`;
3209	}
3210	}
3211
3212	assert_eq!(values, [`2`, `3`, `5`, `6`, `7`]);
3213	}
3214
3215	#[test]
3216	fn test_clone() {
3217	let v: ThinVec<i32> = thin_vec![];
3218	let w = thin_vec![`1`, `2`, `3`];
3219
3220	assert_eq!(v, v.clone());
3221
3222	let z = w.clone();
3223	assert_eq!(w, z);
3224	// they should be disjoint in memory.
3225	assert!(w.as_ptr() != z.as_ptr())
3226	}
3227
3228	#[test]
3229	fn test_clone_from() {
3230	let mut v = thin_vec![];
3231	let three: ThinVec<Box<_>> = thin_vec![Box::new(`1`), Box::new(`2`), Box::new(`3`)];
3232	let two: ThinVec<Box<_>> = thin_vec![Box::new(`4`), Box::new(`5`)];
3233	// zero, long
3234	v.clone_from(&three);
3235	assert_eq!(v, three);
3236
3237	// equal
3238	v.clone_from(&three);
3239	assert_eq!(v, three);
3240
3241	// long, short
3242	v.clone_from(&two);
3243	assert_eq!(v, two);
3244
3245	// short, long
3246	v.clone_from(&three);
3247	assert_eq!(v, three)
3248	}
3249
3250	#[test]
3251	fn test_retain() {
3252	let mut vec = thin_vec![`1`, `2`, `3`, `4`];
3253	vec.retain(\|&x\| x % `2` == `0`);
3254	assert_eq!(vec, [`2`, `4`]);
3255	}
3256
3257	#[test]
3258	fn test_retain_mut() {
3259	let mut vec = thin_vec![`9`, `9`, `9`, `9`];
3260	let mut i = `0`;
3261	vec.retain_mut(\|x\| {
3262	i += `1`;
3263	*x = i;
3264	i != `4`
3265	});
3266	assert_eq!(vec, [`1`, `2`, `3`]);
3267	}
3268
3269	#[test]
3270	fn test_dedup() {
3271	fn case(a: ThinVec<i32>, b: ThinVec<i32>) {
3272	let mut v = a;
3273	v.dedup();
3274	assert_eq!(v, b);
3275	}
3276	case(thin_vec![], thin_vec![]);
3277	case(thin_vec![`1`], thin_vec![`1`]);
3278	case(thin_vec![`1`, `1`], thin_vec![`1`]);
3279	case(thin_vec![`1`, `2`, `3`], thin_vec![`1`, `2`, `3`]);
3280	case(thin_vec![`1`, `1`, `2`, `3`], thin_vec![`1`, `2`, `3`]);
3281	case(thin_vec![`1`, `2`, `2`, `3`], thin_vec![`1`, `2`, `3`]);
3282	case(thin_vec![`1`, `2`, `3`, `3`], thin_vec![`1`, `2`, `3`]);
3283	case(thin_vec![`1`, `1`, `2`, `2`, `2`, `3`, `3`], thin_vec![`1`, `2`, `3`]);
3284	}
3285
3286	#[test]
3287	fn test_dedup_by_key() {
3288	fn case(a: ThinVec<i32>, b: ThinVec<i32>) {
3289	let mut v = a;
3290	v.dedup_by_key(\|i\| *i / `10`);
3291	assert_eq!(v, b);
3292	}
3293	case(thin_vec![], thin_vec![]);
3294	case(thin_vec![`10`], thin_vec![`10`]);
3295	case(thin_vec![`10`, `11`], thin_vec![`10`]);
3296	case(thin_vec![`10`, `20`, `30`], thin_vec![`10`, `20`, `30`]);
3297	case(thin_vec![`10`, `11`, `20`, `30`], thin_vec![`10`, `20`, `30`]);
3298	case(thin_vec![`10`, `20`, `21`, `30`], thin_vec![`10`, `20`, `30`]);
3299	case(thin_vec![`10`, `20`, `30`, `31`], thin_vec![`10`, `20`, `30`]);
3300	case(thin_vec![`10`, `11`, `20`, `21`, `22`, `30`, `31`], thin_vec![`10`, `20`, `30`]);
3301	}
3302
3303	#[test]
3304	fn test_dedup_by() {
3305	let mut vec = thin_vec!["foo", "bar", "Bar", "baz", "bar"];
3306	vec.dedup_by(\|a, b\| a.eq_ignore_ascii_case(b));
3307
3308	assert_eq!(vec, ["foo", "bar", "baz", "bar"]);
3309
3310	let mut vec = thin_vec![("foo", `1`), ("foo", `2`), ("bar", `3`), ("bar", `4`), ("bar", `5`)];
3311	vec.dedup_by(\|a, b\| {
3312	a.0 == b.0 && {
3313	b.1 += a.1;
3314	`true`
3315	}
3316	});
3317
3318	assert_eq!(vec, [("foo", `3`), ("bar", `12`)]);
3319	}
3320
3321	#[test]
3322	fn test_dedup_unique() {
3323	let mut v0: ThinVec<Box<_>> = thin_vec![Box::new(`1`), Box::new(`1`), Box::new(`2`), Box::new(`3`)];
3324	v0.dedup();
3325	let mut v1: ThinVec<Box<_>> = thin_vec![Box::new(`1`), Box::new(`2`), Box::new(`2`), Box::new(`3`)];
3326	v1.dedup();
3327	let mut v2: ThinVec<Box<_>> = thin_vec![Box::new(`1`), Box::new(`2`), Box::new(`3`), Box::new(`3`)];
3328	v2.dedup();
3329	// If the boxed pointers were leaked or otherwise misused, valgrind
3330	// and/or rt should raise errors.
3331	}
3332
3333	#[test]
3334	fn zero_sized_values() {
3335	let mut v = ThinVec::new();
3336	assert_eq!(v.len(), `0`);
3337	v.push(());
3338	assert_eq!(v.len(), `1`);
3339	v.push(());
3340	assert_eq!(v.len(), `2`);
3341	assert_eq!(v.pop(), Some(()));
3342	assert_eq!(v.pop(), Some(()));
3343	assert_eq!(v.pop(), None);
3344
3345	assert_eq!(v.iter().count(), `0`);
3346	v.push(());
3347	assert_eq!(v.iter().count(), `1`);
3348	v.push(());
3349	assert_eq!(v.iter().count(), `2`);
3350
3351	for &() in &v {}
3352
3353	assert_eq!(v.iter_mut().count(), `2`);
3354	v.push(());
3355	assert_eq!(v.iter_mut().count(), `3`);
3356	v.push(());
3357	assert_eq!(v.iter_mut().count(), `4`);
3358
3359	for &mut () in &mut v {}
3360	unsafe {
3361	v.set_len(`0`);
3362	}
3363	assert_eq!(v.iter_mut().count(), `0`);
3364	}
3365
3366	#[test]
3367	fn test_partition() {
3368	assert_eq!(
3369	thin_vec![].into_iter().partition(\|x: &i32\| *x < `3`),
3370	(thin_vec![], thin_vec![])
3371	);
3372	assert_eq!(
3373	thin_vec![`1`, `2`, `3`].into_iter().partition(\|x\| *x < `4`),
3374	(thin_vec![`1`, `2`, `3`], thin_vec![])
3375	);
3376	assert_eq!(
3377	thin_vec![`1`, `2`, `3`].into_iter().partition(\|x\| *x < `2`),
3378	(thin_vec![`1`], thin_vec![`2`, `3`])
3379	);
3380	assert_eq!(
3381	thin_vec![`1`, `2`, `3`].into_iter().partition(\|x\| *x < `0`),
3382	(thin_vec![], thin_vec![`1`, `2`, `3`])
3383	);
3384	}
3385
3386	#[test]
3387	fn test_zip_unzip() {
3388	let z1 = thin_vec![(`1`, `4`), (`2`, `5`), (`3`, `6`)];
3389
3390	let (left, right): (ThinVec<_>, ThinVec<_>) = z1.iter().cloned().unzip();
3391
3392	assert_eq!((`1`, `4`), (left[`0`], right[`0`]));
3393	assert_eq!((`2`, `5`), (left[`1`], right[`1`]));
3394	assert_eq!((`3`, `6`), (left[`2`], right[`2`]));
3395	}
3396
3397	#[test]
3398	fn test_vec_truncate_drop() {
3399	static mut DROPS: u32 = `0`;
3400	struct Elem(i32);
3401	impl Drop for Elem {
3402	fn drop(&mut self) {
3403	unsafe {
3404	DROPS += `1`;
3405	}
3406	}
3407	}
3408
3409	let mut v = thin_vec![Elem(`1`), Elem(`2`), Elem(`3`), Elem(`4`), Elem(`5`)];
3410	assert_eq!(unsafe { DROPS }, `0`);
3411	v.truncate(`3`);
3412	assert_eq!(unsafe { DROPS }, `2`);
3413	v.truncate(`0`);
3414	assert_eq!(unsafe { DROPS }, `5`);
3415	}
3416
3417	#[test]
3418	#[should_panic]
3419	fn test_vec_truncate_fail() {
3420	struct BadElem(i32);
3421	impl Drop for BadElem {
3422	fn drop(&mut self) {
3423	let BadElem(ref mut x) = *self;
3424	if *x == `0xbadbeef` {
3425	panic!("BadElem panic: 0xbadbeef")
3426	}
3427	}
3428	}
3429
3430	let mut v = thin_vec![BadElem(`1`), BadElem(`2`), BadElem(`0xbadbeef`), BadElem(`4`)];
3431	v.truncate(`0`);
3432	}
3433
3434	#[test]
3435	fn test_index() {
3436	let vec = thin_vec![`1`, `2`, `3`];
3437	assert!(vec[`1`] == `2`);
3438	}
3439
3440	#[test]
3441	#[should_panic]
3442	fn test_index_out_of_bounds() {
3443	let vec = thin_vec![`1`, `2`, `3`];
3444	let _ = vec[`3`];
3445	}
3446
3447	#[test]
3448	#[should_panic]
3449	fn test_slice_out_of_bounds_1() {
3450	let x = thin_vec![`1`, `2`, `3`, `4`, `5`];
3451	let _ = &x[!`0`..];
3452	}
3453
3454	#[test]
3455	#[should_panic]
3456	fn test_slice_out_of_bounds_2() {
3457	let x = thin_vec![`1`, `2`, `3`, `4`, `5`];
3458	let _ = &x[..`6`];
3459	}
3460
3461	#[test]
3462	#[should_panic]
3463	fn test_slice_out_of_bounds_3() {
3464	let x = thin_vec![`1`, `2`, `3`, `4`, `5`];
3465	let _ = &x[!`0`..`4`];
3466	}
3467
3468	#[test]
3469	#[should_panic]
3470	fn test_slice_out_of_bounds_4() {
3471	let x = thin_vec![`1`, `2`, `3`, `4`, `5`];
3472	let _ = &x[`1`..`6`];
3473	}
3474
3475	#[test]
3476	#[should_panic]
3477	fn test_slice_out_of_bounds_5() {
3478	let x = thin_vec![`1`, `2`, `3`, `4`, `5`];
3479	let _ = &x[`3`..`2`];
3480	}
3481
3482	#[test]
3483	#[should_panic]
3484	fn test_swap_remove_empty() {
3485	let mut vec = ThinVec::<i32>::new();
3486	vec.swap_remove(`0`);
3487	}
3488
3489	#[test]
3490	fn test_move_items() {
3491	let vec = thin_vec![`1`, `2`, `3`];
3492	let mut vec2 = thin_vec![];
3493	for i in vec {
3494	vec2.push(i);
3495	}
3496	assert_eq!(vec2, [`1`, `2`, `3`]);
3497	}
3498
3499	#[test]
3500	fn test_move_items_reverse() {
3501	let vec = thin_vec![`1`, `2`, `3`];
3502	let mut vec2 = thin_vec![];
3503	for i in vec.into_iter().rev() {
3504	vec2.push(i);
3505	}
3506	assert_eq!(vec2, [`3`, `2`, `1`]);
3507	}
3508
3509	#[test]
3510	fn test_move_items_zero_sized() {
3511	let vec = thin_vec![(), (), ()];
3512	let mut vec2 = thin_vec![];
3513	for i in vec {
3514	vec2.push(i);
3515	}
3516	assert_eq!(vec2, [(), (), ()]);
3517	}
3518
3519	#[test]
3520	fn test_drain_items() {
3521	let mut vec = thin_vec![`1`, `2`, `3`];
3522	let mut vec2 = thin_vec![];
3523	for i in vec.drain(..) {
3524	vec2.push(i);
3525	}
3526	assert_eq!(vec, []);
3527	assert_eq!(vec2, [`1`, `2`, `3`]);
3528	}
3529
3530	#[test]
3531	fn test_drain_items_reverse() {
3532	let mut vec = thin_vec![`1`, `2`, `3`];
3533	let mut vec2 = thin_vec![];
3534	for i in vec.drain(..).rev() {
3535	vec2.push(i);
3536	}
3537	assert_eq!(vec, []);
3538	assert_eq!(vec2, [`3`, `2`, `1`]);
3539	}
3540
3541	#[test]
3542	fn test_drain_items_zero_sized() {
3543	let mut vec = thin_vec![(), (), ()];
3544	let mut vec2 = thin_vec![];
3545	for i in vec.drain(..) {
3546	vec2.push(i);
3547	}
3548	assert_eq!(vec, []);
3549	assert_eq!(vec2, [(), (), ()]);
3550	}
3551
3552	#[test]
3553	#[should_panic]
3554	fn test_drain_out_of_bounds() {
3555	let mut v = thin_vec![`1`, `2`, `3`, `4`, `5`];
3556	v.drain(`5`..`6`);
3557	}
3558
3559	#[test]
3560	fn test_drain_range() {
3561	let mut v = thin_vec![`1`, `2`, `3`, `4`, `5`];
3562	for _ in v.drain(`4`..) {}
3563	assert_eq!(v, &[`1`, `2`, `3`, `4`]);
3564
3565	let mut v: ThinVec<_> = (`1`..`6`).map(\|x\| x.to_string()).collect();
3566	for _ in v.drain(`1`..`4`) {}
3567	assert_eq!(v, &[`1`.to_string(), `5`.to_string()]);
3568
3569	let mut v: ThinVec<_> = (`1`..`6`).map(\|x\| x.to_string()).collect();
3570	for _ in v.drain(`1`..`4`).rev() {}
3571	assert_eq!(v, &[`1`.to_string(), `5`.to_string()]);
3572
3573	let mut v: ThinVec<_> = thin_vec![(); `5`];
3574	for _ in v.drain(`1`..`4`).rev() {}
3575	assert_eq!(v, &[(), ()]);
3576	}
3577
3578	#[test]
3579	fn test_drain_inclusive_range() {
3580	let mut v = thin_vec!['a', 'b', 'c', 'd', 'e'];
3581	for _ in v.drain(`1`..=`3`) {}
3582	assert_eq!(v, &['a', 'e']);
3583
3584	let mut v: ThinVec<_> = (`0`..=`5`).map(\|x\| x.to_string()).collect();
3585	for _ in v.drain(`1`..=`5`) {}
3586	assert_eq!(v, &["0".to_string()]);
3587
3588	let mut v: ThinVec<String> = (`0`..=`5`).map(\|x\| x.to_string()).collect();
3589	for _ in v.drain(`0`..=`5`) {}
3590	assert_eq!(v, ThinVec::<String>::new());
3591
3592	let mut v: ThinVec<_> = (`0`..=`5`).map(\|x\| x.to_string()).collect();
3593	for _ in v.drain(`0`..=`3`) {}
3594	assert_eq!(v, &["4".to_string(), "5".to_string()]);
3595
3596	let mut v: ThinVec<_> = (`0`..=`1`).map(\|x\| x.to_string()).collect();
3597	for _ in v.drain(..=`0`) {}
3598	assert_eq!(v, &["1".to_string()]);
3599	}
3600
3601	#[test]
3602	#[cfg(not(feature = "gecko-ffi"))]
3603	fn test_drain_max_vec_size() {
3604	let mut v = ThinVec::<()>::with_capacity(usize::max_value());
3605	unsafe {
3606	v.set_len(usize::max_value());
3607	}
3608	for _ in v.drain(usize::max_value() - `1`..) {}
3609	assert_eq!(v.len(), usize::max_value() - `1`);
3610
3611	let mut v = ThinVec::<()>::with_capacity(usize::max_value());
3612	unsafe {
3613	v.set_len(usize::max_value());
3614	}
3615	for _ in v.drain(usize::max_value() - `1`..=usize::max_value() - `1`) {}
3616	assert_eq!(v.len(), usize::max_value() - `1`);
3617	}
3618
3619	#[test]
3620	#[should_panic]
3621	fn test_drain_inclusive_out_of_bounds() {
3622	let mut v = thin_vec![`1`, `2`, `3`, `4`, `5`];
3623	v.drain(`5`..=`5`);
3624	}
3625
3626	#[test]
3627	fn test_splice() {
3628	let mut v = thin_vec![`1`, `2`, `3`, `4`, `5`];
3629	let a = [`10`, `11`, `12`];
3630	v.splice(`2`..`4`, a.iter().cloned());
3631	assert_eq!(v, &[`1`, `2`, `10`, `11`, `12`, `5`]);
3632	v.splice(`1`..`3`, Some(`20`));
3633	assert_eq!(v, &[`1`, `20`, `11`, `12`, `5`]);
3634	}
3635
3636	#[test]
3637	fn test_splice_inclusive_range() {
3638	let mut v = thin_vec![`1`, `2`, `3`, `4`, `5`];
3639	let a = [`10`, `11`, `12`];
3640	let t1: ThinVec<_> = v.splice(`2`..=`3`, a.iter().cloned()).collect();
3641	assert_eq!(v, &[`1`, `2`, `10`, `11`, `12`, `5`]);
3642	assert_eq!(t1, &[`3`, `4`]);
3643	let t2: ThinVec<_> = v.splice(`1`..=`2`, Some(`20`)).collect();
3644	assert_eq!(v, &[`1`, `20`, `11`, `12`, `5`]);
3645	assert_eq!(t2, &[`2`, `10`]);
3646	}
3647
3648	#[test]
3649	#[should_panic]
3650	fn test_splice_out_of_bounds() {
3651	let mut v = thin_vec![`1`, `2`, `3`, `4`, `5`];
3652	let a = [`10`, `11`, `12`];
3653	v.splice(`5`..`6`, a.iter().cloned());
3654	}
3655
3656	#[test]
3657	#[should_panic]
3658	fn test_splice_inclusive_out_of_bounds() {
3659	let mut v = thin_vec![`1`, `2`, `3`, `4`, `5`];
3660	let a = [`10`, `11`, `12`];
3661	v.splice(`5`..=`5`, a.iter().cloned());
3662	}
3663
3664	#[test]
3665	fn test_splice_items_zero_sized() {
3666	let mut vec = thin_vec![(), (), ()];
3667	let vec2 = thin_vec![];
3668	let t: ThinVec<_> = vec.splice(`1`..`2`, vec2.iter().cloned()).collect();
3669	assert_eq!(vec, &[(), ()]);
3670	assert_eq!(t, &[()]);
3671	}
3672
3673	#[test]
3674	fn test_splice_unbounded() {
3675	let mut vec = thin_vec![`1`, `2`, `3`, `4`, `5`];
3676	let t: ThinVec<_> = vec.splice(.., None).collect();
3677	assert_eq!(vec, &[]);
3678	assert_eq!(t, &[`1`, `2`, `3`, `4`, `5`]);
3679	}
3680
3681	#[test]
3682	fn test_splice_forget() {
3683	let mut v = thin_vec![`1`, `2`, `3`, `4`, `5`];
3684	let a = [`10`, `11`, `12`];
3685	::core::mem::forget(v.splice(`2`..`4`, a.iter().cloned()));
3686	assert_eq!(v, &[`1`, `2`]);
3687	}
3688
3689	#[test]
3690	fn test_splice_from_empty() {
3691	let mut v = thin_vec![];
3692	let a = [`10`, `11`, `12`];
3693	v.splice(.., a.iter().cloned());
3694	assert_eq!(v, &[`10`, `11`, `12`]);
3695	}
3696
3697	/ probs won't ever impl this*
3698	#[test]
3699	fn test_into_boxed_slice() {
3700	let xs = thin_vec![1, 2, 3];
3701	let ys = xs.into_boxed_slice();
3702	assert_eq!(&ys, [1, 2, 3]);*
3703	}
3704	*/
3705
3706	#[test]
3707	fn test_append() {
3708	let mut vec = thin_vec![`1`, `2`, `3`];
3709	let mut vec2 = thin_vec![`4`, `5`, `6`];
3710	vec.append(&mut vec2);
3711	assert_eq!(vec, [`1`, `2`, `3`, `4`, `5`, `6`]);
3712	assert_eq!(vec2, []);
3713	}
3714
3715	#[test]
3716	fn test_split_off() {
3717	let mut vec = thin_vec![`1`, `2`, `3`, `4`, `5`, `6`];
3718	let vec2 = vec.split_off(`4`);
3719	assert_eq!(vec, [`1`, `2`, `3`, `4`]);
3720	assert_eq!(vec2, [`5`, `6`]);
3721	}
3722
3723	#[test]
3724	fn test_into_iter_as_slice() {
3725	let vec = thin_vec!['a', 'b', 'c'];
3726	let mut into_iter = vec.into_iter();
3727	assert_eq!(into_iter.as_slice(), &['a', 'b', 'c']);
3728	let _ = into_iter.next().unwrap();
3729	assert_eq!(into_iter.as_slice(), &['b', 'c']);
3730	let _ = into_iter.next().unwrap();
3731	let _ = into_iter.next().unwrap();
3732	assert_eq!(into_iter.as_slice(), &[]);
3733	}
3734
3735	#[test]
3736	fn test_into_iter_as_mut_slice() {
3737	let vec = thin_vec!['a', 'b', 'c'];
3738	let mut into_iter = vec.into_iter();
3739	assert_eq!(into_iter.as_slice(), &['a', 'b', 'c']);
3740	into_iter.as_mut_slice()[`0`] = 'x';
3741	into_iter.as_mut_slice()[`1`] = 'y';
3742	assert_eq!(into_iter.next().unwrap(), 'x');
3743	assert_eq!(into_iter.as_slice(), &['y', 'c']);
3744	}
3745
3746	#[test]
3747	fn test_into_iter_debug() {
3748	let vec = thin_vec!['a', 'b', 'c'];
3749	let into_iter = vec.into_iter();
3750	let debug = format!("{:?}", into_iter);
3751	assert_eq!(debug, "IntoIter(['a', 'b', 'c'])");
3752	}
3753
3754	#[test]
3755	fn test_into_iter_count() {
3756	assert_eq!(thin_vec![`1`, `2`, `3`].into_iter().count(), `3`);
3757	}
3758
3759	#[test]
3760	fn test_into_iter_clone() {
3761	fn iter_equal<I: Iterator<Item = i32>>(it: I, slice: &[i32]) {
3762	let v: ThinVec<i32> = it.collect();
3763	assert_eq!(&v[..], slice);
3764	}
3765	let mut it = thin_vec![`1`, `2`, `3`].into_iter();
3766	iter_equal(it.clone(), &[`1`, `2`, `3`]);
3767	assert_eq!(it.next(), Some(`1`));
3768	let mut it = it.rev();
3769	iter_equal(it.clone(), &[`3`, `2`]);
3770	assert_eq!(it.next(), Some(`3`));
3771	iter_equal(it.clone(), &[`2`]);
3772	assert_eq!(it.next(), Some(`2`));
3773	iter_equal(it.clone(), &[]);
3774	assert_eq!(it.next(), None);
3775	}
3776
3777	/ TODO: make drain covariant*
3778	#[allow(dead_code)]
3779	fn assert_covariance() {
3780	fn drain<'new>(d: Drain<'static, &'static str>) -> Drain<'new, &'new str> {
3781	d
3782	}
3783	fn into_iter<'new>(i: IntoIter<&'static str>) -> IntoIter<&'new str> {
3784	i
3785	}
3786	}
3787	*/
3788
3789	/ TODO: specialize vec.into_iter().collect::<ThinVec<_>>();*
3790	#[test]
3791	fn from_into_inner() {
3792	let vec = thin_vec![1, 2, 3];
3793	let ptr = vec.as_ptr();
3794	let vec = vec.into_iter().collect::<ThinVec<_>>();
3795	assert_eq!(vec, [1, 2, 3]);
3796	assert_eq!(vec.as_ptr(), ptr);
3797
3798	let ptr = &vec[1] as const _;*
3799	let mut it = vec.into_iter();
3800	it.next().unwrap();
3801	let vec = it.collect::<ThinVec<_>>();
3802	assert_eq!(vec, [2, 3]);
3803	assert!(ptr != vec.as_ptr());
3804	}
3805	*/
3806
3807	#[test]
3808	#[cfg_attr(feature = "gecko-ffi", ignore)]
3809	fn overaligned_allocations() {
3810	#[repr(align(`256`))]
3811	struct Foo(usize);
3812	let mut v = thin_vec![Foo(`273`)];
3813	for i in `0`..`0x1000` {
3814	v.reserve_exact(i);
3815	assert!(v[`0`].`0` == `273`);
3816	assert!(v.as_ptr() as usize & `0xff` == `0`);
3817	v.shrink_to_fit();
3818	assert!(v[`0`].`0` == `273`);
3819	assert!(v.as_ptr() as usize & `0xff` == `0`);
3820	}
3821	}
3822
3823	/ TODO: implement drain_filter?*
3824	#[test]
3825	fn drain_filter_empty() {
3826	let mut vec: ThinVec<i32> = thin_vec![];
3827
3828	{
3829	let mut iter = vec.drain_filter(\|_\| true);
3830	assert_eq!(iter.size_hint(), (0, Some(0)));
3831	assert_eq!(iter.next(), None);
3832	assert_eq!(iter.size_hint(), (0, Some(0)));
3833	assert_eq!(iter.next(), None);
3834	assert_eq!(iter.size_hint(), (0, Some(0)));
3835	}
3836	assert_eq!(vec.len(), 0);
3837	assert_eq!(vec, thin_vec![]);
3838	}
3839
3840	#[test]
3841	fn drain_filter_zst() {
3842	let mut vec = thin_vec![(), (), (), (), ()];
3843	let initial_len = vec.len();
3844	let mut count = 0;
3845	{
3846	let mut iter = vec.drain_filter(\|_\| true);
3847	assert_eq!(iter.size_hint(), (0, Some(initial_len)));
3848	while let Some(_) = iter.next() {
3849	count += 1;
3850	assert_eq!(iter.size_hint(), (0, Some(initial_len - count)));
3851	}
3852	assert_eq!(iter.size_hint(), (0, Some(0)));
3853	assert_eq!(iter.next(), None);
3854	assert_eq!(iter.size_hint(), (0, Some(0)));
3855	}
3856
3857	assert_eq!(count, initial_len);
3858	assert_eq!(vec.len(), 0);
3859	assert_eq!(vec, thin_vec![]);
3860	}
3861
3862	#[test]
3863	fn drain_filter_false() {
3864	let mut vec = thin_vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
3865
3866	let initial_len = vec.len();
3867	let mut count = 0;
3868	{
3869	let mut iter = vec.drain_filter(\|_\| false);
3870	assert_eq!(iter.size_hint(), (0, Some(initial_len)));
3871	for _ in iter.by_ref() {
3872	count += 1;
3873	}
3874	assert_eq!(iter.size_hint(), (0, Some(0)));
3875	assert_eq!(iter.next(), None);
3876	assert_eq!(iter.size_hint(), (0, Some(0)));
3877	}
3878
3879	assert_eq!(count, 0);
3880	assert_eq!(vec.len(), initial_len);
3881	assert_eq!(vec, thin_vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
3882	}
3883
3884	#[test]
3885	fn drain_filter_true() {
3886	let mut vec = thin_vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
3887
3888	let initial_len = vec.len();
3889	let mut count = 0;
3890	{
3891	let mut iter = vec.drain_filter(\|_\| true);
3892	assert_eq!(iter.size_hint(), (0, Some(initial_len)));
3893	while let Some(_) = iter.next() {
3894	count += 1;
3895	assert_eq!(iter.size_hint(), (0, Some(initial_len - count)));
3896	}
3897	assert_eq!(iter.size_hint(), (0, Some(0)));
3898	assert_eq!(iter.next(), None);
3899	assert_eq!(iter.size_hint(), (0, Some(0)));
3900	}
3901
3902	assert_eq!(count, initial_len);
3903	assert_eq!(vec.len(), 0);
3904	assert_eq!(vec, thin_vec![]);
3905	}
3906
3907	#[test]
3908	fn drain_filter_complex() {
3909
3910	{ // [+xxx++++++xxxxx++++x+x++]
3911	let mut vec = thin_vec![1,
3912	2, 4, 6,
3913	7, 9, 11, 13, 15, 17,
3914	18, 20, 22, 24, 26,
3915	27, 29, 31, 33,
3916	34,
3917	35,
3918	36,
3919	37, 39];
3920
3921	let removed = vec.drain_filter(\|x\| x % 2 == 0).collect::<ThinVec<_>>();*
3922	assert_eq!(removed.len(), 10);
3923	assert_eq!(removed, thin_vec![2, 4, 6, 18, 20, 22, 24, 26, 34, 36]);
3924
3925	assert_eq!(vec.len(), 14);
3926	assert_eq!(vec, thin_vec![1, 7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35, 37, 39]);
3927	}
3928
3929	{ // [xxx++++++xxxxx++++x+x++]
3930	let mut vec = thin_vec![2, 4, 6,
3931	7, 9, 11, 13, 15, 17,
3932	18, 20, 22, 24, 26,
3933	27, 29, 31, 33,
3934	34,
3935	35,
3936	36,
3937	37, 39];
3938
3939	let removed = vec.drain_filter(\|x\| x % 2 == 0).collect::<ThinVec<_>>();*
3940	assert_eq!(removed.len(), 10);
3941	assert_eq!(removed, thin_vec![2, 4, 6, 18, 20, 22, 24, 26, 34, 36]);
3942
3943	assert_eq!(vec.len(), 13);
3944	assert_eq!(vec, thin_vec![7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35, 37, 39]);
3945	}
3946
3947	{ // [xxx++++++xxxxx++++x+x]
3948	let mut vec = thin_vec![2, 4, 6,
3949	7, 9, 11, 13, 15, 17,
3950	18, 20, 22, 24, 26,
3951	27, 29, 31, 33,
3952	34,
3953	35,
3954	36];
3955
3956	let removed = vec.drain_filter(\|x\| x % 2 == 0).collect::<ThinVec<_>>();*
3957	assert_eq!(removed.len(), 10);
3958	assert_eq!(removed, thin_vec![2, 4, 6, 18, 20, 22, 24, 26, 34, 36]);
3959
3960	assert_eq!(vec.len(), 11);
3961	assert_eq!(vec, thin_vec![7, 9, 11, 13, 15, 17, 27, 29, 31, 33, 35]);
3962	}
3963
3964	{ // [xxxxxxxxxx+++++++++++]
3965	let mut vec = thin_vec![2, 4, 6, 8, 10, 12, 14, 16, 18, 20,
3966	1, 3, 5, 7, 9, 11, 13, 15, 17, 19];
3967
3968	let removed = vec.drain_filter(\|x\| x % 2 == 0).collect::<ThinVec<_>>();*
3969	assert_eq!(removed.len(), 10);
3970	assert_eq!(removed, thin_vec![2, 4, 6, 8, 10, 12, 14, 16, 18, 20]);
3971
3972	assert_eq!(vec.len(), 10);
3973	assert_eq!(vec, thin_vec![1, 3, 5, 7, 9, 11, 13, 15, 17, 19]);
3974	}
3975
3976	{ // [+++++++++++xxxxxxxxxx]
3977	let mut vec = thin_vec![1, 3, 5, 7, 9, 11, 13, 15, 17, 19,
3978	2, 4, 6, 8, 10, 12, 14, 16, 18, 20];
3979
3980	let removed = vec.drain_filter(\|x\| x % 2 == 0).collect::<ThinVec<_>>();*
3981	assert_eq!(removed.len(), 10);
3982	assert_eq!(removed, thin_vec![2, 4, 6, 8, 10, 12, 14, 16, 18, 20]);
3983
3984	assert_eq!(vec.len(), 10);
3985	assert_eq!(vec, thin_vec![1, 3, 5, 7, 9, 11, 13, 15, 17, 19]);
3986	}
3987	}
3988	*/
3989	#[test]
3990	fn test_reserve_exact() {
3991	// This is all the same as test_reserve
3992
3993	let mut v = ThinVec::new();
3994	assert_eq!(v.capacity(), `0`);
3995
3996	v.reserve_exact(`2`);
3997	assert!(v.capacity() >= `2`);
3998
3999	for i in `0`..`16` {
4000	v.push(i);
4001	}
4002
4003	assert!(v.capacity() >= `16`);
4004	v.reserve_exact(`16`);
4005	assert!(v.capacity() >= `32`);
4006
4007	v.push(`16`);
4008
4009	v.reserve_exact(`16`);
4010	assert!(v.capacity() >= `33`)
4011	}
4012
4013	/ TODO: implement try_reserve*
4014	#[test]
4015	fn test_try_reserve() {
4016
4017	// These are the interesting cases:
4018	// exactly isize::MAX should never trigger a CapacityOverflow (can be OOM)*
4019	// > isize::MAX should always fail*
4020	// On 16/32-bit should CapacityOverflow*
4021	// On 64-bit should OOM*
4022	// overflow may trigger when adding `len` to `cap` (in number of elements)*
4023	// overflow may trigger when multiplying `new_cap` by size_of::<T> (to get bytes)*
4024
4025	const MAX_CAP: usize = isize::MAX as usize;
4026	const MAX_USIZE: usize = usize::MAX;
4027
4028	// On 16/32-bit, we check that allocations don't exceed isize::MAX,
4029	// on 64-bit, we assume the OS will give an OOM for such a ridiculous size.
4030	// Any platform that succeeds for these requests is technically broken with
4031	// ptr::offset because LLVM is the worst.
4032	let guards_against_isize = size_of::<usize>() < 8;
4033
4034	{
4035	// Note: basic stuff is checked by test_reserve
4036	let mut empty_bytes: ThinVec<u8> = ThinVec::new();
4037
4038	// Check isize::MAX doesn't count as an overflow
4039	if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_CAP) {
4040	panic!("isize::MAX shouldn't trigger an overflow!");
4041	}
4042	// Play it again, frank! (just to be sure)
4043	if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_CAP) {
4044	panic!("isize::MAX shouldn't trigger an overflow!");
4045	}
4046
4047	if guards_against_isize {
4048	// Check isize::MAX + 1 does count as overflow
4049	if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_CAP + 1) {
4050	} else { panic!("isize::MAX + 1 should trigger an overflow!") }
4051
4052	// Check usize::MAX does count as overflow
4053	if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_USIZE) {
4054	} else { panic!("usize::MAX should trigger an overflow!") }
4055	} else {
4056	// Check isize::MAX + 1 is an OOM
4057	if let Err(AllocErr) = empty_bytes.try_reserve(MAX_CAP + 1) {
4058	} else { panic!("isize::MAX + 1 should trigger an OOM!") }
4059
4060	// Check usize::MAX is an OOM
4061	if let Err(AllocErr) = empty_bytes.try_reserve(MAX_USIZE) {
4062	} else { panic!("usize::MAX should trigger an OOM!") }
4063	}
4064	}
4065
4066
4067	{
4068	// Same basic idea, but with non-zero len
4069	let mut ten_bytes: ThinVec<u8> = thin_vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
4070
4071	if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_CAP - 10) {
4072	panic!("isize::MAX shouldn't trigger an overflow!");
4073	}
4074	if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_CAP - 10) {
4075	panic!("isize::MAX shouldn't trigger an overflow!");
4076	}
4077	if guards_against_isize {
4078	if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_CAP - 9) {
4079	} else { panic!("isize::MAX + 1 should trigger an overflow!"); }
4080	} else {
4081	if let Err(AllocErr) = ten_bytes.try_reserve(MAX_CAP - 9) {
4082	} else { panic!("isize::MAX + 1 should trigger an OOM!") }
4083	}
4084	// Should always overflow in the add-to-len
4085	if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_USIZE) {
4086	} else { panic!("usize::MAX should trigger an overflow!") }
4087	}
4088
4089
4090	{
4091	// Same basic idea, but with interesting type size
4092	let mut ten_u32s: ThinVec<u32> = thin_vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
4093
4094	if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_CAP/4 - 10) {
4095	panic!("isize::MAX shouldn't trigger an overflow!");
4096	}
4097	if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_CAP/4 - 10) {
4098	panic!("isize::MAX shouldn't trigger an overflow!");
4099	}
4100	if guards_against_isize {
4101	if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_CAP/4 - 9) {
4102	} else { panic!("isize::MAX + 1 should trigger an overflow!"); }
4103	} else {
4104	if let Err(AllocErr) = ten_u32s.try_reserve(MAX_CAP/4 - 9) {
4105	} else { panic!("isize::MAX + 1 should trigger an OOM!") }
4106	}
4107	// Should fail in the mul-by-size
4108	if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_USIZE - 20) {
4109	} else {
4110	panic!("usize::MAX should trigger an overflow!");
4111	}
4112	}
4113
4114	}
4115
4116	#[test]
4117	fn test_try_reserve_exact() {
4118
4119	// This is exactly the same as test_try_reserve with the method changed.
4120	// See that test for comments.
4121
4122	const MAX_CAP: usize = isize::MAX as usize;
4123	const MAX_USIZE: usize = usize::MAX;
4124
4125	let guards_against_isize = size_of::<usize>() < 8;
4126
4127	{
4128	let mut empty_bytes: ThinVec<u8> = ThinVec::new();
4129
4130	if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_CAP) {
4131	panic!("isize::MAX shouldn't trigger an overflow!");
4132	}
4133	if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_CAP) {
4134	panic!("isize::MAX shouldn't trigger an overflow!");
4135	}
4136
4137	if guards_against_isize {
4138	if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_CAP + 1) {
4139	} else { panic!("isize::MAX + 1 should trigger an overflow!") }
4140
4141	if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_USIZE) {
4142	} else { panic!("usize::MAX should trigger an overflow!") }
4143	} else {
4144	if let Err(AllocErr) = empty_bytes.try_reserve_exact(MAX_CAP + 1) {
4145	} else { panic!("isize::MAX + 1 should trigger an OOM!") }
4146
4147	if let Err(AllocErr) = empty_bytes.try_reserve_exact(MAX_USIZE) {
4148	} else { panic!("usize::MAX should trigger an OOM!") }
4149	}
4150	}
4151
4152
4153	{
4154	let mut ten_bytes: ThinVec<u8> = thin_vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
4155
4156	if let Err(CapacityOverflow) = ten_bytes.try_reserve_exact(MAX_CAP - 10) {
4157	panic!("isize::MAX shouldn't trigger an overflow!");
4158	}
4159	if let Err(CapacityOverflow) = ten_bytes.try_reserve_exact(MAX_CAP - 10) {
4160	panic!("isize::MAX shouldn't trigger an overflow!");
4161	}
4162	if guards_against_isize {
4163	if let Err(CapacityOverflow) = ten_bytes.try_reserve_exact(MAX_CAP - 9) {
4164	} else { panic!("isize::MAX + 1 should trigger an overflow!"); }
4165	} else {
4166	if let Err(AllocErr) = ten_bytes.try_reserve_exact(MAX_CAP - 9) {
4167	} else { panic!("isize::MAX + 1 should trigger an OOM!") }
4168	}
4169	if let Err(CapacityOverflow) = ten_bytes.try_reserve_exact(MAX_USIZE) {
4170	} else { panic!("usize::MAX should trigger an overflow!") }
4171	}
4172
4173
4174	{
4175	let mut ten_u32s: ThinVec<u32> = thin_vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
4176
4177	if let Err(CapacityOverflow) = ten_u32s.try_reserve_exact(MAX_CAP/4 - 10) {
4178	panic!("isize::MAX shouldn't trigger an overflow!");
4179	}
4180	if let Err(CapacityOverflow) = ten_u32s.try_reserve_exact(MAX_CAP/4 - 10) {
4181	panic!("isize::MAX shouldn't trigger an overflow!");
4182	}
4183	if guards_against_isize {
4184	if let Err(CapacityOverflow) = ten_u32s.try_reserve_exact(MAX_CAP/4 - 9) {
4185	} else { panic!("isize::MAX + 1 should trigger an overflow!"); }
4186	} else {
4187	if let Err(AllocErr) = ten_u32s.try_reserve_exact(MAX_CAP/4 - 9) {
4188	} else { panic!("isize::MAX + 1 should trigger an OOM!") }
4189	}
4190	if let Err(CapacityOverflow) = ten_u32s.try_reserve_exact(MAX_USIZE - 20) {
4191	} else { panic!("usize::MAX should trigger an overflow!") }
4192	}
4193	}
4194	*/
4195
4196	#[test]
4197	#[cfg_attr(feature = "gecko-ffi", ignore)]
4198	fn test_header_data() {
4199	macro_rules! assert_aligned_head_ptr {
4200	($typename:ty) => {{
4201	let v: ThinVec<$typename> = ThinVec::with_capacity(`1` / ensure allocation /);
4202	let head_ptr: *mut $typename = v.data_raw();
4203	assert_eq!(
4204	head_ptr as usize % core::mem::align_of::<$typename>(),
4205	`0`,
4206	"expected Header::data<{}> to be aligned",
4207	stringify!($typename)
4208	);
4209	}};
4210	}
4211
4212	const HEADER_SIZE: usize = core::mem::size_of::<Header>();
4213	assert_eq!(`2` * core::mem::size_of::<usize>(), HEADER_SIZE);
4214
4215	#[repr(C, align(`128`))]
4216	struct Funky<T>(T);
4217	assert_eq!(padding::<Funky<()>>(), `128` - HEADER_SIZE);
4218	assert_aligned_head_ptr!(Funky<()>);
4219
4220	assert_eq!(padding::<Funky<u8>>(), `128` - HEADER_SIZE);
4221	assert_aligned_head_ptr!(Funky<u8>);
4222
4223	assert_eq!(padding::<Funky<[(); `1024`]>>(), `128` - HEADER_SIZE);
4224	assert_aligned_head_ptr!(Funky<[(); `1024`]>);
4225
4226	assert_eq!(padding::<Funky<[*mut usize; `1024`]>>(), `128` - HEADER_SIZE);
4227	assert_aligned_head_ptr!(Funky<[*mut usize; `1024`]>);
4228	}
4229
4230	#[cfg(feature = "serde")]
4231	use serde_test::{assert_tokens, Token};
4232
4233	#[test]
4234	#[cfg(feature = "serde")]
4235	fn test_ser_de_empty() {
4236	let vec = ThinVec::<u32>::new();
4237
4238	assert_tokens(&vec, &[Token::Seq { len: Some(`0`) }, Token::SeqEnd]);
4239	}
4240
4241	#[test]
4242	#[cfg(feature = "serde")]
4243	fn test_ser_de() {
4244	let mut vec = ThinVec::<u32>::new();
4245	vec.push(`20`);
4246	vec.push(`55`);
4247	vec.push(`123`);
4248
4249	assert_tokens(
4250	&vec,
4251	&[
4252	Token::Seq { len: Some(`3`) },
4253	Token::U32(`20`),
4254	Token::U32(`55`),
4255	Token::U32(`123`),
4256	Token::SeqEnd,
4257	],
4258	);
4259	}
4260
4261	#[test]
4262	fn test_set_len() {
4263	let mut vec: ThinVec<u32> = thin_vec![];
4264	unsafe {
4265	vec.set_len(`0`); // at one point this caused a crash
4266	}
4267	}
4268
4269	#[test]
4270	#[should_panic(expected = "invalid set_len(1) on empty ThinVec")]
4271	fn test_set_len_invalid() {
4272	let mut vec: ThinVec<u32> = thin_vec![];
4273	unsafe {
4274	vec.set_len(`1`);
4275	}
4276	}
4277
4278	#[test]
4279	#[should_panic(expected = "capacity overflow")]
4280	fn test_capacity_overflow_header_too_big() {
4281	let vec: ThinVec<u8> = ThinVec::with_capacity(isize::MAX as usize - `2`);
4282	assert!(vec.capacity() > `0`);
4283	}
4284	#[test]
4285	#[should_panic(expected = "capacity overflow")]
4286	fn test_capacity_overflow_cap_too_big() {
4287	let vec: ThinVec<u8> = ThinVec::with_capacity(isize::MAX as usize + `1`);
4288	assert!(vec.capacity() > `0`);
4289	}
4290	#[test]
4291	#[should_panic(expected = "capacity overflow")]
4292	fn test_capacity_overflow_size_mul1() {
4293	let vec: ThinVec<u16> = ThinVec::with_capacity(isize::MAX as usize + `1`);
4294	assert!(vec.capacity() > `0`);
4295	}
4296	#[test]
4297	#[should_panic(expected = "capacity overflow")]
4298	fn test_capacity_overflow_size_mul2() {
4299	let vec: ThinVec<u16> = ThinVec::with_capacity(isize::MAX as usize / `2` + `1`);
4300	assert!(vec.capacity() > `0`);
4301	}
4302	#[test]
4303	#[should_panic(expected = "capacity overflow")]
4304	fn test_capacity_overflow_cap_really_isnt_isize() {
4305	let vec: ThinVec<u8> = ThinVec::with_capacity(isize::MAX as usize);
4306	assert!(vec.capacity() > `0`);
4307	}
4308	}
4309