bumpalo/collections/
vec.rs

1// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
2// file at the top-level directory of this distribution and at
3// http://rust-lang.org/COPYRIGHT.
4//
5// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8// option. This file may not be copied, modified, or distributed
9// except according to those terms.
10
11//! A contiguous growable array type with heap-allocated contents, written
12//! [`Vec<'bump, T>`].
13//!
14//! Vectors have `O(1)` indexing, amortized `O(1)` push (to the end) and
15//! `O(1)` pop (from the end).
16//!
17//! This module is a fork of the [`std::vec`] module, that uses a bump allocator.
18//!
19//! [`std::vec`]: https://doc.rust-lang.org/std/vec/index.html
20//!
21//! # Examples
22//!
23//! You can explicitly create a [`Vec<'bump, T>`] with [`new_in`]:
24//!
25//! ```
26//! use bumpalo::{Bump, collections::Vec};
27//!
28//! let b = Bump::new();
29//! let v: Vec<i32> = Vec::new_in(&b);
30//! ```
31//!
32//! ... or by using the [`vec!`] macro:
33//!
34//! ```
35//! use bumpalo::{Bump, collections::Vec};
36//!
37//! let b = Bump::new();
38//!
39//! let v: Vec<i32> = bumpalo::vec![in &b];
40//!
41//! let v = bumpalo::vec![in &b; 1, 2, 3, 4, 5];
42//!
43//! let v = bumpalo::vec![in &b; 0; 10]; // ten zeroes
44//! ```
45//!
46//! You can [`push`] values onto the end of a vector (which will grow the vector
47//! as needed):
48//!
49//! ```
50//! use bumpalo::{Bump, collections::Vec};
51//!
52//! let b = Bump::new();
53//!
54//! let mut v = bumpalo::vec![in &b; 1, 2];
55//!
56//! v.push(3);
57//! ```
58//!
59//! Popping values works in much the same way:
60//!
61//! ```
62//! use bumpalo::{Bump, collections::Vec};
63//!
64//! let b = Bump::new();
65//!
66//! let mut v = bumpalo::vec![in &b; 1, 2];
67//!
68//! assert_eq!(v.pop(), Some(2));
69//! ```
70//!
71//! Vectors also support indexing (through the [`Index`] and [`IndexMut`] traits):
72//!
73//! ```
74//! use bumpalo::{Bump, collections::Vec};
75//!
76//! let b = Bump::new();
77//!
78//! let mut v = bumpalo::vec![in &b; 1, 2, 3];
79//! assert_eq!(v[2], 3);
80//! v[1] += 5;
81//! assert_eq!(v, [1, 7, 3]);
82//! ```
83//!
84//! [`Vec<'bump, T>`]: struct.Vec.html
85//! [`new_in`]: struct.Vec.html#method.new_in
86//! [`push`]: struct.Vec.html#method.push
87//! [`Index`]: https://doc.rust-lang.org/std/ops/trait.Index.html
88//! [`IndexMut`]: https://doc.rust-lang.org/std/ops/trait.IndexMut.html
89//! [`vec!`]: ../../macro.vec.html
90
91use super::raw_vec::RawVec;
92use crate::collections::CollectionAllocErr;
93use crate::Bump;
94use core::borrow::{Borrow, BorrowMut};
95use core::cmp::Ordering;
96use core::fmt;
97use core::hash::{self, Hash};
98use core::iter::FusedIterator;
99use core::marker::PhantomData;
100use core::mem;
101use core::ops;
102use core::ops::Bound::{Excluded, Included, Unbounded};
103use core::ops::{Index, IndexMut, RangeBounds};
104use core::ptr;
105use core::ptr::NonNull;
106use core::slice;
107#[cfg(feature = "std")]
108use std::io;
109
110unsafe fn arith_offset<T>(p: *const T, offset: isize) -> *const T {
111    p.offset(offset)
112}
113
114fn partition_dedup_by<T, F>(s: &mut [T], mut same_bucket: F) -> (&mut [T], &mut [T])
115where
116    F: FnMut(&mut T, &mut T) -> bool,
117{
118    // Although we have a mutable reference to `s`, we cannot make
119    // *arbitrary* changes. The `same_bucket` calls could panic, so we
120    // must ensure that the slice is in a valid state at all times.
121    //
122    // The way that we handle this is by using swaps; we iterate
123    // over all the elements, swapping as we go so that at the end
124    // the elements we wish to keep are in the front, and those we
125    // wish to reject are at the back. We can then split the slice.
126    // This operation is still O(n).
127    //
128    // Example: We start in this state, where `r` represents "next
129    // read" and `w` represents "next_write`.
130    //
131    //           r
132    //     +---+---+---+---+---+---+
133    //     | 0 | 1 | 1 | 2 | 3 | 3 |
134    //     +---+---+---+---+---+---+
135    //           w
136    //
137    // Comparing s[r] against s[w-1], this is not a duplicate, so
138    // we swap s[r] and s[w] (no effect as r==w) and then increment both
139    // r and w, leaving us with:
140    //
141    //               r
142    //     +---+---+---+---+---+---+
143    //     | 0 | 1 | 1 | 2 | 3 | 3 |
144    //     +---+---+---+---+---+---+
145    //               w
146    //
147    // Comparing s[r] against s[w-1], this value is a duplicate,
148    // so we increment `r` but leave everything else unchanged:
149    //
150    //                   r
151    //     +---+---+---+---+---+---+
152    //     | 0 | 1 | 1 | 2 | 3 | 3 |
153    //     +---+---+---+---+---+---+
154    //               w
155    //
156    // Comparing s[r] against s[w-1], this is not a duplicate,
157    // so swap s[r] and s[w] and advance r and w:
158    //
159    //                       r
160    //     +---+---+---+---+---+---+
161    //     | 0 | 1 | 2 | 1 | 3 | 3 |
162    //     +---+---+---+---+---+---+
163    //                   w
164    //
165    // Not a duplicate, repeat:
166    //
167    //                           r
168    //     +---+---+---+---+---+---+
169    //     | 0 | 1 | 2 | 3 | 1 | 3 |
170    //     +---+---+---+---+---+---+
171    //                       w
172    //
173    // Duplicate, advance r. End of slice. Split at w.
174
175    let len = s.len();
176    if len <= 1 {
177        return (s, &mut []);
178    }
179
180    let ptr = s.as_mut_ptr();
181    let mut next_read: usize = 1;
182    let mut next_write: usize = 1;
183
184    unsafe {
185        // Avoid bounds checks by using raw pointers.
186        while next_read < len {
187            let ptr_read = ptr.add(next_read);
188            let prev_ptr_write = ptr.add(next_write - 1);
189            if !same_bucket(&mut *ptr_read, &mut *prev_ptr_write) {
190                if next_read != next_write {
191                    let ptr_write = prev_ptr_write.offset(1);
192                    mem::swap(&mut *ptr_read, &mut *ptr_write);
193                }
194                next_write += 1;
195            }
196            next_read += 1;
197        }
198    }
199
200    s.split_at_mut(next_write)
201}
202
203unsafe fn offset_from<T>(p: *const T, origin: *const T) -> isize
204where
205    T: Sized,
206{
207    let pointee_size = mem::size_of::<T>();
208    assert!(0 < pointee_size && pointee_size <= isize::max_value() as usize);
209
210    // This is the same sequence that Clang emits for pointer subtraction.
211    // It can be neither `nsw` nor `nuw` because the input is treated as
212    // unsigned but then the output is treated as signed, so neither works.
213    let d = isize::wrapping_sub(p as _, origin as _);
214    d / (pointee_size as isize)
215}
216
217/// Creates a [`Vec`] containing the arguments.
218///
219/// `vec!` allows `Vec`s to be defined with the same syntax as array expressions.
220/// There are two forms of this macro:
221///
222/// - Create a [`Vec`] containing a given list of elements:
223///
224/// ```
225/// use bumpalo::Bump;
226///
227/// let b = Bump::new();
228/// let v = bumpalo::vec![in &b; 1, 2, 3];
229/// assert_eq!(v, [1, 2, 3]);
230/// ```
231///
232/// - Create a [`Vec`] from a given element and size:
233///
234/// ```
235/// use bumpalo::Bump;
236///
237/// let b = Bump::new();
238/// let v = bumpalo::vec![in &b; 1; 3];
239/// assert_eq!(v, [1, 1, 1]);
240/// ```
241///
242/// Note that unlike array expressions, this syntax supports all elements
243/// which implement [`Clone`] and the number of elements doesn't have to be
244/// a constant.
245///
246/// This will use `clone` to duplicate an expression, so one should be careful
247/// using this with types having a non-standard `Clone` implementation. For
248/// example, `bumpalo::vec![in &bump; Rc::new(1); 5]` will create a vector of five references
249/// to the same boxed integer value, not five references pointing to independently
250/// boxed integers.
251///
252/// [`Vec`]: collections/vec/struct.Vec.html
253/// [`Clone`]: https://doc.rust-lang.org/std/clone/trait.Clone.html
254#[macro_export]
255macro_rules! vec {
256    (in $bump:expr; $elem:expr; $n:expr) => {{
257        let n = $n;
258        let mut v = $crate::collections::Vec::with_capacity_in(n, $bump);
259        if n > 0 {
260            let elem = $elem;
261            for _ in 0..n - 1 {
262                v.push(elem.clone());
263            }
264            v.push(elem);
265        }
266        v
267    }};
268    (in $bump:expr) => { $crate::collections::Vec::new_in($bump) };
269    (in $bump:expr; $($x:expr),*) => {{
270        let mut v = $crate::collections::Vec::new_in($bump);
271        $( v.push($x); )*
272        v
273    }};
274    (in $bump:expr; $($x:expr,)*) => (bumpalo::vec![in $bump; $($x),*])
275}
276
277/// A contiguous growable array type, written `Vec<'bump, T>` but pronounced 'vector'.
278///
279/// # Examples
280///
281/// ```
282/// use bumpalo::{Bump, collections::Vec};
283///
284/// let b = Bump::new();
285///
286/// let mut vec = Vec::new_in(&b);
287/// vec.push(1);
288/// vec.push(2);
289///
290/// assert_eq!(vec.len(), 2);
291/// assert_eq!(vec[0], 1);
292///
293/// assert_eq!(vec.pop(), Some(2));
294/// assert_eq!(vec.len(), 1);
295///
296/// vec[0] = 7;
297/// assert_eq!(vec[0], 7);
298///
299/// vec.extend([1, 2, 3].iter().cloned());
300///
301/// for x in &vec {
302///     println!("{}", x);
303/// }
304/// assert_eq!(vec, [7, 1, 2, 3]);
305/// ```
306///
307/// The [`vec!`] macro is provided to make initialization more convenient:
308///
309/// ```
310/// use bumpalo::{Bump, collections::Vec};
311///
312/// let b = Bump::new();
313///
314/// let mut vec = bumpalo::vec![in &b; 1, 2, 3];
315/// vec.push(4);
316/// assert_eq!(vec, [1, 2, 3, 4]);
317/// ```
318///
319/// It can also initialize each element of a `Vec<'bump, T>` with a given value.
320/// This may be more efficient than performing allocation and initialization
321/// in separate steps, especially when initializing a vector of zeros:
322///
323/// ```
324/// use bumpalo::{Bump, collections::Vec};
325///
326/// let b = Bump::new();
327///
328/// let vec = bumpalo::vec![in &b; 0; 5];
329/// assert_eq!(vec, [0, 0, 0, 0, 0]);
330///
331/// // The following is equivalent, but potentially slower:
332/// let mut vec1 = Vec::with_capacity_in(5, &b);
333/// vec1.resize(5, 0);
334/// ```
335///
336/// Use a `Vec<'bump, T>` as an efficient stack:
337///
338/// ```
339/// use bumpalo::{Bump, collections::Vec};
340///
341/// let b = Bump::new();
342///
343/// let mut stack = Vec::new_in(&b);
344///
345/// stack.push(1);
346/// stack.push(2);
347/// stack.push(3);
348///
349/// while let Some(top) = stack.pop() {
350///     // Prints 3, 2, 1
351///     println!("{}", top);
352/// }
353/// ```
354///
355/// # Indexing
356///
357/// The `Vec` type allows to access values by index, because it implements the
358/// [`Index`] trait. An example will be more explicit:
359///
360/// ```
361/// use bumpalo::{Bump, collections::Vec};
362///
363/// let b = Bump::new();
364///
365/// let v = bumpalo::vec![in &b; 0, 2, 4, 6];
366/// println!("{}", v[1]); // it will display '2'
367/// ```
368///
369/// However be careful: if you try to access an index which isn't in the `Vec`,
370/// your software will panic! You cannot do this:
371///
372/// ```should_panic
373/// use bumpalo::{Bump, collections::Vec};
374///
375/// let b = Bump::new();
376///
377/// let v = bumpalo::vec![in &b; 0, 2, 4, 6];
378/// println!("{}", v[6]); // it will panic!
379/// ```
380///
381/// In conclusion: always check if the index you want to get really exists
382/// before doing it.
383///
384/// # Slicing
385///
386/// A `Vec` can be mutable. Slices, on the other hand, are read-only objects.
387/// To get a slice, use `&`. Example:
388///
389/// ```
390/// use bumpalo::{Bump, collections::Vec};
391///
392/// fn read_slice(slice: &[usize]) {
393///     // ...
394/// }
395///
396/// let b = Bump::new();
397///
398/// let v = bumpalo::vec![in &b; 0, 1];
399/// read_slice(&v);
400///
401/// // ... and that's all!
402/// // you can also do it like this:
403/// let x : &[usize] = &v;
404/// ```
405///
406/// In Rust, it's more common to pass slices as arguments rather than vectors
407/// when you just want to provide a read access. The same goes for [`String`] and
408/// [`&str`].
409///
410/// # Capacity and reallocation
411///
412/// The capacity of a vector is the amount of space allocated for any future
413/// elements that will be added onto the vector. This is not to be confused with
414/// the *length* of a vector, which specifies the number of actual elements
415/// within the vector. If a vector's length exceeds its capacity, its capacity
416/// will automatically be increased, but its elements will have to be
417/// reallocated.
418///
419/// For example, a vector with capacity 10 and length 0 would be an empty vector
420/// with space for 10 more elements. Pushing 10 or fewer elements onto the
421/// vector will not change its capacity or cause reallocation to occur. However,
422/// if the vector's length is increased to 11, it will have to reallocate, which
423/// can be slow. For this reason, it is recommended to use [`Vec::with_capacity_in`]
424/// whenever possible to specify how big the vector is expected to get.
425///
426/// # Guarantees
427///
428/// Due to its incredibly fundamental nature, `Vec` makes a lot of guarantees
429/// about its design. This ensures that it's as low-overhead as possible in
430/// the general case, and can be correctly manipulated in primitive ways
431/// by unsafe code. Note that these guarantees refer to an unqualified `Vec<'bump, T>`.
432/// If additional type parameters are added (e.g. to support custom allocators),
433/// overriding their defaults may change the behavior.
434///
435/// Most fundamentally, `Vec` is and always will be a (pointer, capacity, length)
436/// triplet. No more, no less. The order of these fields is completely
437/// unspecified, and you should use the appropriate methods to modify these.
438/// The pointer will never be null, so this type is null-pointer-optimized.
439///
440/// However, the pointer may not actually point to allocated memory. In particular,
441/// if you construct a `Vec` with capacity 0 via [`Vec::new_in`], [`bumpalo::vec![in bump]`][`vec!`],
442/// [`Vec::with_capacity_in(0)`][`Vec::with_capacity_in`], or by calling [`shrink_to_fit`]
443/// on an empty Vec, it will not allocate memory. Similarly, if you store zero-sized
444/// types inside a `Vec`, it will not allocate space for them. *Note that in this case
445/// the `Vec` may not report a [`capacity`] of 0*. `Vec` will allocate if and only
446/// if <code>[`mem::size_of::<T>`]\() * capacity() > 0</code>. In general, `Vec`'s allocation
447/// details are very subtle &mdash; if you intend to allocate memory using a `Vec`
448/// and use it for something else (either to pass to unsafe code, or to build your
449/// own memory-backed collection), be sure to deallocate this memory by using
450/// `from_raw_parts` to recover the `Vec` and then dropping it.
451///
452/// If a `Vec` *has* allocated memory, then the memory it points to is
453/// in the [`Bump`] arena used to construct it, and its
454/// pointer points to [`len`] initialized, contiguous elements in order (what
455/// you would see if you coerced it to a slice), followed by <code>[`capacity`] -
456/// [`len`]</code> logically uninitialized, contiguous elements.
457///
458/// `Vec` will never perform a "small optimization" where elements are actually
459/// stored on the stack for two reasons:
460///
461/// * It would make it more difficult for unsafe code to correctly manipulate
462///   a `Vec`. The contents of a `Vec` wouldn't have a stable address if it were
463///   only moved, and it would be more difficult to determine if a `Vec` had
464///   actually allocated memory.
465///
466/// * It would penalize the general case, incurring an additional branch
467///   on every access.
468///
469/// `Vec` will never automatically shrink itself, even if completely empty. This
470/// ensures no unnecessary allocations or deallocations occur. Emptying a `Vec`
471/// and then filling it back up to the same [`len`] should incur no calls to
472/// the allocator. If you wish to free up unused memory, use
473/// [`shrink_to_fit`][`shrink_to_fit`].
474///
475/// [`push`] and [`insert`] will never (re)allocate if the reported capacity is
476/// sufficient. [`push`] and [`insert`] *will* (re)allocate if
477/// <code>[`len`] == [`capacity`]</code>. That is, the reported capacity is completely
478/// accurate, and can be relied on. It can even be used to manually free the memory
479/// allocated by a `Vec` if desired. Bulk insertion methods *may* reallocate, even
480/// when not necessary.
481///
482/// `Vec` does not guarantee any particular growth strategy when reallocating
483/// when full, nor when [`reserve`] is called. The current strategy is basic
484/// and it may prove desirable to use a non-constant growth factor. Whatever
485/// strategy is used will of course guarantee `O(1)` amortized [`push`].
486///
487/// `bumpalo::vec![in bump; x; n]`, `bumpalo::vec![in bump; a, b, c, d]`, and
488/// [`Vec::with_capacity_in(n)`][`Vec::with_capacity_in`], will all produce a
489/// `Vec` with exactly the requested capacity. If <code>[`len`] == [`capacity`]</code>, (as
490/// is the case for the [`vec!`] macro), then a `Vec<'bump, T>` can be converted
491/// to and from a [`Box<[T]>`][owned slice] without reallocating or moving the
492/// elements.
493///
494/// `Vec` will not specifically overwrite any data that is removed from it,
495/// but also won't specifically preserve it. Its uninitialized memory is
496/// scratch space that it may use however it wants. It will generally just do
497/// whatever is most efficient or otherwise easy to implement. Do not rely on
498/// removed data to be erased for security purposes. Even if you drop a `Vec`, its
499/// buffer may simply be reused by another `Vec`. Even if you zero a `Vec`'s memory
500/// first, that may not actually happen because the optimizer does not consider
501/// this a side-effect that must be preserved. There is one case which we will
502/// not break, however: using `unsafe` code to write to the excess capacity,
503/// and then increasing the length to match, is always valid.
504///
505/// `Vec` does not currently guarantee the order in which elements are dropped.
506/// The order has changed in the past and may change again.
507///
508/// [`vec!`]: ../../macro.vec.html
509/// [`Index`]: https://doc.rust-lang.org/std/ops/trait.Index.html
510/// [`String`]: ../string/struct.String.html
511/// [`&str`]: https://doc.rust-lang.org/std/primitive.str.html
512/// [`Vec::with_capacity_in`]: struct.Vec.html#method.with_capacity_in
513/// [`Vec::new_in`]: struct.Vec.html#method.new_in
514/// [`shrink_to_fit`]: struct.Vec.html#method.shrink_to_fit
515/// [`capacity`]: struct.Vec.html#method.capacity
516/// [`mem::size_of::<T>`]: https://doc.rust-lang.org/std/mem/fn.size_of.html
517/// [`len`]: struct.Vec.html#method.len
518/// [`push`]: struct.Vec.html#method.push
519/// [`insert`]: struct.Vec.html#method.insert
520/// [`reserve`]: struct.Vec.html#method.reserve
521/// [owned slice]: https://doc.rust-lang.org/std/boxed/struct.Box.html
522pub struct Vec<'bump, T: 'bump> {
523    buf: RawVec<'bump, T>,
524    len: usize,
525}
526
527////////////////////////////////////////////////////////////////////////////////
528// Inherent methods
529////////////////////////////////////////////////////////////////////////////////
530
531impl<'bump, T: 'bump> Vec<'bump, T> {
532    /// Constructs a new, empty `Vec<'bump, T>`.
533    ///
534    /// The vector will not allocate until elements are pushed onto it.
535    ///
536    /// # Examples
537    ///
538    /// ```
539    /// # #![allow(unused_mut)]
540    /// use bumpalo::{Bump, collections::Vec};
541    ///
542    /// let b = Bump::new();
543    /// let mut vec: Vec<i32> = Vec::new_in(&b);
544    /// ```
545    #[inline]
546    pub fn new_in(bump: &'bump Bump) -> Vec<'bump, T> {
547        Vec {
548            buf: RawVec::new_in(bump),
549            len: 0,
550        }
551    }
552
553    /// Constructs a new, empty `Vec<'bump, T>` with the specified capacity.
554    ///
555    /// The vector will be able to hold exactly `capacity` elements without
556    /// reallocating. If `capacity` is 0, the vector will not allocate.
557    ///
558    /// It is important to note that although the returned vector has the
559    /// *capacity* specified, the vector will have a zero *length*. For an
560    /// explanation of the difference between length and capacity, see
561    /// *[Capacity and reallocation]*.
562    ///
563    /// [Capacity and reallocation]: #capacity-and-reallocation
564    ///
565    /// # Examples
566    ///
567    /// ```
568    /// use bumpalo::{Bump, collections::Vec};
569    ///
570    /// let b = Bump::new();
571    ///
572    /// let mut vec = Vec::with_capacity_in(10, &b);
573    ///
574    /// // The vector contains no items, even though it has capacity for more
575    /// assert_eq!(vec.len(), 0);
576    ///
577    /// // These are all done without reallocating...
578    /// for i in 0..10 {
579    ///     vec.push(i);
580    /// }
581    ///
582    /// // ...but this may make the vector reallocate
583    /// vec.push(11);
584    /// ```
585    #[inline]
586    pub fn with_capacity_in(capacity: usize, bump: &'bump Bump) -> Vec<'bump, T> {
587        Vec {
588            buf: RawVec::with_capacity_in(capacity, bump),
589            len: 0,
590        }
591    }
592
593    /// Construct a new `Vec` from the given iterator's items.
594    ///
595    /// # Examples
596    ///
597    /// ```
598    /// use bumpalo::{Bump, collections::Vec};
599    /// use std::iter;
600    ///
601    /// let b = Bump::new();
602    /// let v = Vec::from_iter_in(iter::repeat(7).take(3), &b);
603    /// assert_eq!(v, [7, 7, 7]);
604    /// ```
605    pub fn from_iter_in<I: IntoIterator<Item = T>>(iter: I, bump: &'bump Bump) -> Vec<'bump, T> {
606        let mut v = Vec::new_in(bump);
607        v.extend(iter);
608        v
609    }
610
611    /// Creates a `Vec<'bump, T>` directly from the raw components of another vector.
612    ///
613    /// # Safety
614    ///
615    /// This is highly unsafe, due to the number of invariants that aren't
616    /// checked:
617    ///
618    /// * `ptr` needs to have been previously allocated via [`String`]/`Vec<'bump, T>`
619    ///   (at least, it's highly likely to be incorrect if it wasn't).
620    /// * `ptr`'s `T` needs to have the same size and alignment as it was allocated with.
621    /// * `length` needs to be less than or equal to `capacity`.
622    /// * `capacity` needs to be the capacity that the pointer was allocated with.
623    ///
624    /// Violating these may cause problems like corrupting the allocator's
625    /// internal data structures. For example it is **not** safe
626    /// to build a `Vec<u8>` from a pointer to a C `char` array and a `size_t`.
627    ///
628    /// The ownership of `ptr` is effectively transferred to the
629    /// `Vec<'bump, T>` which may then deallocate, reallocate or change the
630    /// contents of memory pointed to by the pointer at will. Ensure
631    /// that nothing else uses the pointer after calling this
632    /// function.
633    ///
634    /// [`String`]: ../string/struct.String.html
635    ///
636    /// # Examples
637    ///
638    /// ```
639    /// use bumpalo::{Bump, collections::Vec};
640    ///
641    /// use std::ptr;
642    /// use std::mem;
643    ///
644    /// let b = Bump::new();
645    ///
646    /// let mut v = bumpalo::vec![in &b; 1, 2, 3];
647    ///
648    /// // Pull out the various important pieces of information about `v`
649    /// let p = v.as_mut_ptr();
650    /// let len = v.len();
651    /// let cap = v.capacity();
652    ///
653    /// unsafe {
654    ///     // Cast `v` into the void: no destructor run, so we are in
655    ///     // complete control of the allocation to which `p` points.
656    ///     mem::forget(v);
657    ///
658    ///     // Overwrite memory with 4, 5, 6
659    ///     for i in 0..len as isize {
660    ///         ptr::write(p.offset(i), 4 + i);
661    ///     }
662    ///
663    ///     // Put everything back together into a Vec
664    ///     let rebuilt = Vec::from_raw_parts_in(p, len, cap, &b);
665    ///     assert_eq!(rebuilt, [4, 5, 6]);
666    /// }
667    /// ```
668    pub unsafe fn from_raw_parts_in(
669        ptr: *mut T,
670        length: usize,
671        capacity: usize,
672        bump: &'bump Bump,
673    ) -> Vec<'bump, T> {
674        Vec {
675            buf: RawVec::from_raw_parts_in(ptr, capacity, bump),
676            len: length,
677        }
678    }
679
680    /// Returns a shared reference to the allocator backing this `Vec`.
681    ///
682    /// # Examples
683    ///
684    /// ```
685    /// use bumpalo::{Bump, collections::Vec};
686    ///
687    /// // uses the same allocator as the provided `Vec`
688    /// fn add_strings<'bump>(vec: &mut Vec<'bump, &'bump str>) {
689    ///     for string in ["foo", "bar", "baz"] {
690    ///         vec.push(vec.bump().alloc_str(string));
691    ///     }
692    /// }
693    /// ```
694    #[inline]
695    #[must_use]
696    pub fn bump(&self) -> &'bump Bump {
697        self.buf.bump()
698    }
699
700    /// Returns the number of elements the vector can hold without
701    /// reallocating.
702    ///
703    /// # Examples
704    ///
705    /// ```
706    /// use bumpalo::{Bump, collections::Vec};
707    ///
708    /// let b = Bump::new();
709    /// let vec: Vec<i32> = Vec::with_capacity_in(10, &b);
710    /// assert_eq!(vec.capacity(), 10);
711    /// ```
712    #[inline]
713    pub fn capacity(&self) -> usize {
714        self.buf.cap()
715    }
716
717    /// Reserves capacity for at least `additional` more elements to be inserted
718    /// in the given `Vec<'bump, T>`. The collection may reserve more space to avoid
719    /// frequent reallocations. After calling `reserve`, capacity will be
720    /// greater than or equal to `self.len() + additional`. Does nothing if
721    /// capacity is already sufficient.
722    ///
723    /// # Panics
724    ///
725    /// Panics if the new capacity overflows `usize`.
726    ///
727    /// # Examples
728    ///
729    /// ```
730    /// use bumpalo::{Bump, collections::Vec};
731    ///
732    /// let b = Bump::new();
733    /// let mut vec = bumpalo::vec![in &b; 1];
734    /// vec.reserve(10);
735    /// assert!(vec.capacity() >= 11);
736    /// ```
737    pub fn reserve(&mut self, additional: usize) {
738        self.buf.reserve(self.len, additional);
739    }
740
741    /// Reserves the minimum capacity for exactly `additional` more elements to
742    /// be inserted in the given `Vec<'bump, T>`. After calling `reserve_exact`,
743    /// capacity will be greater than or equal to `self.len() + additional`.
744    /// Does nothing if the capacity is already sufficient.
745    ///
746    /// Note that the allocator may give the collection more space than it
747    /// requests. Therefore capacity can not be relied upon to be precisely
748    /// minimal. Prefer `reserve` if future insertions are expected.
749    ///
750    /// # Panics
751    ///
752    /// Panics if the new capacity overflows `usize`.
753    ///
754    /// # Examples
755    ///
756    /// ```
757    /// use bumpalo::{Bump, collections::Vec};
758    ///
759    /// let b = Bump::new();
760    /// let mut vec = bumpalo::vec![in &b; 1];
761    /// vec.reserve_exact(10);
762    /// assert!(vec.capacity() >= 11);
763    /// ```
764    pub fn reserve_exact(&mut self, additional: usize) {
765        self.buf.reserve_exact(self.len, additional);
766    }
767
768    /// Attempts to reserve capacity for at least `additional` more elements to be inserted
769    /// in the given `Vec<'bump, T>`. The collection may reserve more space to avoid
770    /// frequent reallocations. After calling `try_reserve`, capacity will be
771    /// greater than or equal to `self.len() + additional`. Does nothing if
772    /// capacity is already sufficient.
773    ///
774    /// # Panics
775    ///
776    /// Panics if the new capacity overflows `usize`.
777    ///
778    /// # Examples
779    ///
780    /// ```
781    /// use bumpalo::{Bump, collections::Vec};
782    ///
783    /// let b = Bump::new();
784    /// let mut vec = bumpalo::vec![in &b; 1];
785    /// vec.try_reserve(10).unwrap();
786    /// assert!(vec.capacity() >= 11);
787    /// ```
788    pub fn try_reserve(&mut self, additional: usize) -> Result<(), CollectionAllocErr> {
789        self.buf.try_reserve(self.len, additional)
790    }
791
792    /// Attempts to reserve the minimum capacity for exactly `additional` more elements to
793    /// be inserted in the given `Vec<'bump, T>`. After calling `try_reserve_exact`,
794    /// capacity will be greater than or equal to `self.len() + additional`.
795    /// Does nothing if the capacity is already sufficient.
796    ///
797    /// Note that the allocator may give the collection more space than it
798    /// requests. Therefore capacity can not be relied upon to be precisely
799    /// minimal. Prefer `try_reserve` if future insertions are expected.
800    ///
801    /// # Panics
802    ///
803    /// Panics if the new capacity overflows `usize`.
804    ///
805    /// # Examples
806    ///
807    /// ```
808    /// use bumpalo::{Bump, collections::Vec};
809    ///
810    /// let b = Bump::new();
811    /// let mut vec = bumpalo::vec![in &b; 1];
812    /// vec.try_reserve_exact(10).unwrap();
813    /// assert!(vec.capacity() >= 11);
814    /// ```
815    pub fn try_reserve_exact(&mut self, additional: usize) -> Result<(), CollectionAllocErr> {
816        self.buf.try_reserve_exact(self.len, additional)
817    }
818
819    /// Shrinks the capacity of the vector as much as possible.
820    ///
821    /// It will drop down as close as possible to the length but the allocator
822    /// may still inform the vector that there is space for a few more elements.
823    ///
824    /// # Examples
825    ///
826    /// ```
827    /// use bumpalo::{Bump, collections::Vec};
828    ///
829    /// let b = Bump::new();
830    ///
831    /// let mut vec = Vec::with_capacity_in(10, &b);
832    /// vec.extend([1, 2, 3].iter().cloned());
833    /// assert_eq!(vec.capacity(), 10);
834    /// vec.shrink_to_fit();
835    /// assert!(vec.capacity() >= 3);
836    /// ```
837    pub fn shrink_to_fit(&mut self) {
838        if self.capacity() != self.len {
839            self.buf.shrink_to_fit(self.len);
840        }
841    }
842
843    /// Converts the vector into `&'bump [T]`.
844    ///
845    /// # Examples
846    ///
847    /// ```
848    /// use bumpalo::{Bump, collections::Vec};
849    ///
850    /// let b = Bump::new();
851    /// let v = bumpalo::vec![in &b; 1, 2, 3];
852    ///
853    /// let slice = v.into_bump_slice();
854    /// assert_eq!(slice, [1, 2, 3]);
855    /// ```
856    pub fn into_bump_slice(self) -> &'bump [T] {
857        unsafe {
858            let ptr = self.as_ptr();
859            let len = self.len();
860            mem::forget(self);
861            slice::from_raw_parts(ptr, len)
862        }
863    }
864
865    /// Converts the vector into `&'bump mut [T]`.
866    ///
867    /// # Examples
868    ///
869    /// ```
870    /// use bumpalo::{Bump, collections::Vec};
871    ///
872    /// let b = Bump::new();
873    /// let v = bumpalo::vec![in &b; 1, 2, 3];
874    ///
875    /// let mut slice = v.into_bump_slice_mut();
876    ///
877    /// slice[0] = 3;
878    /// slice[2] = 1;
879    ///
880    /// assert_eq!(slice, [3, 2, 1]);
881    /// ```
882    pub fn into_bump_slice_mut(mut self) -> &'bump mut [T] {
883        let ptr = self.as_mut_ptr();
884        let len = self.len();
885        mem::forget(self);
886
887        unsafe { slice::from_raw_parts_mut(ptr, len) }
888    }
889
890    /// Shortens the vector, keeping the first `len` elements and dropping
891    /// the rest.
892    ///
893    /// If `len` is greater than the vector's current length, this has no
894    /// effect.
895    ///
896    /// The [`drain`] method can emulate `truncate`, but causes the excess
897    /// elements to be returned instead of dropped.
898    ///
899    /// Note that this method has no effect on the allocated capacity
900    /// of the vector.
901    ///
902    /// # Examples
903    ///
904    /// Truncating a five element vector to two elements:
905    ///
906    /// ```
907    /// use bumpalo::{Bump, collections::Vec};
908    ///
909    /// let b = Bump::new();
910    ///
911    /// let mut vec = bumpalo::vec![in &b; 1, 2, 3, 4, 5];
912    /// vec.truncate(2);
913    /// assert_eq!(vec, [1, 2]);
914    /// ```
915    ///
916    /// No truncation occurs when `len` is greater than the vector's current
917    /// length:
918    ///
919    /// ```
920    /// use bumpalo::{Bump, collections::Vec};
921    ///
922    /// let b = Bump::new();
923    ///
924    /// let mut vec = bumpalo::vec![in &b; 1, 2, 3];
925    /// vec.truncate(8);
926    /// assert_eq!(vec, [1, 2, 3]);
927    /// ```
928    ///
929    /// Truncating when `len == 0` is equivalent to calling the [`clear`]
930    /// method.
931    ///
932    /// ```
933    /// use bumpalo::{Bump, collections::Vec};
934    ///
935    /// let b = Bump::new();
936    ///
937    /// let mut vec = bumpalo::vec![in &b; 1, 2, 3];
938    /// vec.truncate(0);
939    /// assert_eq!(vec, []);
940    /// ```
941    ///
942    /// [`clear`]: #method.clear
943    /// [`drain`]: #method.drain
944    pub fn truncate(&mut self, len: usize) {
945        let current_len = self.len;
946        unsafe {
947            let mut ptr = self.as_mut_ptr().add(self.len);
948            // Set the final length at the end, keeping in mind that
949            // dropping an element might panic. Works around a missed
950            // optimization, as seen in the following issue:
951            // https://github.com/rust-lang/rust/issues/51802
952            let mut local_len = SetLenOnDrop::new(&mut self.len);
953
954            // drop any extra elements
955            for _ in len..current_len {
956                local_len.decrement_len(1);
957                ptr = ptr.offset(-1);
958                ptr::drop_in_place(ptr);
959            }
960        }
961    }
962
963    /// Extracts a slice containing the entire vector.
964    ///
965    /// Equivalent to `&s[..]`.
966    ///
967    /// # Examples
968    ///
969    /// ```
970    /// use bumpalo::{Bump, collections::Vec};
971    /// use std::io::{self, Write};
972    ///
973    /// let b = Bump::new();
974    ///
975    /// let buffer = bumpalo::vec![in &b; 1, 2, 3, 5, 8];
976    /// io::sink().write(buffer.as_slice()).unwrap();
977    /// ```
978    #[inline]
979    pub fn as_slice(&self) -> &[T] {
980        self
981    }
982
983    /// Extracts a mutable slice of the entire vector.
984    ///
985    /// Equivalent to `&mut s[..]`.
986    ///
987    /// # Examples
988    ///
989    /// ```
990    /// use bumpalo::{Bump, collections::Vec};
991    /// use std::io::{self, Read};
992    ///
993    /// let b = Bump::new();
994    /// let mut buffer = bumpalo::vec![in &b; 0; 3];
995    /// io::repeat(0b101).read_exact(buffer.as_mut_slice()).unwrap();
996    /// ```
997    #[inline]
998    pub fn as_mut_slice(&mut self) -> &mut [T] {
999        self
1000    }
1001
1002    /// Returns a raw pointer to the vector's buffer, or a dangling raw pointer
1003    /// valid for zero sized reads if the vector didn't allocate.
1004    ///
1005    /// The caller must ensure that the vector outlives the pointer this
1006    /// function returns, or else it will end up pointing to garbage.
1007    /// Modifying the vector may cause its buffer to be reallocated,
1008    /// which would also make any pointers to it invalid.
1009    ///
1010    /// The caller must also ensure that the memory the pointer (non-transitively) points to
1011    /// is never written to (except inside an `UnsafeCell`) using this pointer or any pointer
1012    /// derived from it. If you need to mutate the contents of the slice, use [`as_mut_ptr`].
1013    ///
1014    /// # Examples
1015    ///
1016    /// ```
1017    /// use bumpalo::{Bump, collections::Vec};
1018    ///
1019    /// let bump = Bump::new();
1020    ///
1021    /// let x = bumpalo::vec![in &bump; 1, 2, 4];
1022    /// let x_ptr = x.as_ptr();
1023    ///
1024    /// unsafe {
1025    ///     for i in 0..x.len() {
1026    ///         assert_eq!(*x_ptr.add(i), 1 << i);
1027    ///     }
1028    /// }
1029    /// ```
1030    ///
1031    /// [`as_mut_ptr`]: Vec::as_mut_ptr
1032    #[inline]
1033    pub fn as_ptr(&self) -> *const T {
1034        // We shadow the slice method of the same name to avoid going through
1035        // `deref`, which creates an intermediate reference.
1036        let ptr = self.buf.ptr();
1037        unsafe {
1038            if ptr.is_null() {
1039                core::hint::unreachable_unchecked();
1040            }
1041        }
1042        ptr
1043    }
1044
1045    /// Returns an unsafe mutable pointer to the vector's buffer, or a dangling
1046    /// raw pointer valid for zero sized reads if the vector didn't allocate.
1047    ///
1048    /// The caller must ensure that the vector outlives the pointer this
1049    /// function returns, or else it will end up pointing to garbage.
1050    /// Modifying the vector may cause its buffer to be reallocated,
1051    /// which would also make any pointers to it invalid.
1052    ///
1053    /// # Examples
1054    ///
1055    /// ```
1056    /// use bumpalo::{Bump, collections::Vec};
1057    ///
1058    /// let bump = Bump::new();
1059    ///
1060    /// // Allocate vector big enough for 4 elements.
1061    /// let size = 4;
1062    /// let mut x: Vec<i32> = Vec::with_capacity_in(size, &bump);
1063    /// let x_ptr = x.as_mut_ptr();
1064    ///
1065    /// // Initialize elements via raw pointer writes, then set length.
1066    /// unsafe {
1067    ///     for i in 0..size {
1068    ///         x_ptr.add(i).write(i as i32);
1069    ///     }
1070    ///     x.set_len(size);
1071    /// }
1072    /// assert_eq!(&*x, &[0, 1, 2, 3]);
1073    /// ```
1074    #[inline]
1075    pub fn as_mut_ptr(&mut self) -> *mut T {
1076        // We shadow the slice method of the same name to avoid going through
1077        // `deref_mut`, which creates an intermediate reference.
1078        let ptr = self.buf.ptr();
1079        unsafe {
1080            if ptr.is_null() {
1081                core::hint::unreachable_unchecked();
1082            }
1083        }
1084        ptr
1085    }
1086
1087    /// Sets the length of a vector.
1088    ///
1089    /// This will explicitly set the size of the vector, without actually
1090    /// modifying its buffers, so it is up to the caller to ensure that the
1091    /// vector is actually the specified size.
1092    ///
1093    /// # Safety
1094    ///
1095    /// - `new_len` must be less than or equal to [`capacity()`].
1096    /// - The elements at `old_len..new_len` must be initialized.
1097    ///
1098    /// [`capacity()`]: struct.Vec.html#method.capacity
1099    ///
1100    /// # Examples
1101    ///
1102    /// ```
1103    /// use bumpalo::{Bump, collections::Vec};
1104    ///
1105    /// use std::ptr;
1106    ///
1107    /// let b = Bump::new();
1108    ///
1109    /// let mut vec = bumpalo::vec![in &b; 'r', 'u', 's', 't'];
1110    ///
1111    /// unsafe {
1112    ///     ptr::drop_in_place(&mut vec[3]);
1113    ///     vec.set_len(3);
1114    /// }
1115    /// assert_eq!(vec, ['r', 'u', 's']);
1116    /// ```
1117    ///
1118    /// In this example, there is a memory leak since the memory locations
1119    /// owned by the inner vectors were not freed prior to the `set_len` call:
1120    ///
1121    /// ```
1122    /// use bumpalo::{Bump, collections::Vec};
1123    ///
1124    /// let b = Bump::new();
1125    ///
1126    /// let mut vec = bumpalo::vec![in &b;
1127    ///                             bumpalo::vec![in &b; 1, 0, 0],
1128    ///                             bumpalo::vec![in &b; 0, 1, 0],
1129    ///                             bumpalo::vec![in &b; 0, 0, 1]];
1130    /// unsafe {
1131    ///     vec.set_len(0);
1132    /// }
1133    /// ```
1134    ///
1135    /// In this example, the vector gets expanded from zero to four items
1136    /// but we directly initialize uninitialized memory:
1137    ///
1138    // TODO: rely upon `spare_capacity_mut`
1139    /// ```
1140    /// use bumpalo::{Bump, collections::Vec};
1141    ///
1142    /// let len = 4;
1143    /// let b = Bump::new();
1144    ///
1145    /// let mut vec: Vec<u8> = Vec::with_capacity_in(len, &b);
1146    ///
1147    /// for i in 0..len {
1148    ///     // SAFETY: we initialize memory via `pointer::write`
1149    ///     unsafe { vec.as_mut_ptr().add(i).write(b'a') }
1150    /// }
1151    ///
1152    /// unsafe {
1153    ///     vec.set_len(len);
1154    /// }
1155    ///
1156    /// assert_eq!(b"aaaa", &*vec);
1157    /// ```
1158    #[inline]
1159    pub unsafe fn set_len(&mut self, new_len: usize) {
1160        self.len = new_len;
1161    }
1162
1163    /// Removes an element from the vector and returns it.
1164    ///
1165    /// The removed element is replaced by the last element of the vector.
1166    ///
1167    /// This does not preserve ordering, but is O(1).
1168    ///
1169    /// # Panics
1170    ///
1171    /// Panics if `index` is out of bounds.
1172    ///
1173    /// # Examples
1174    ///
1175    /// ```
1176    /// use bumpalo::{Bump, collections::Vec};
1177    ///
1178    /// let b = Bump::new();
1179    ///
1180    /// let mut v = bumpalo::vec![in &b; "foo", "bar", "baz", "qux"];
1181    ///
1182    /// assert_eq!(v.swap_remove(1), "bar");
1183    /// assert_eq!(v, ["foo", "qux", "baz"]);
1184    ///
1185    /// assert_eq!(v.swap_remove(0), "foo");
1186    /// assert_eq!(v, ["baz", "qux"]);
1187    /// ```
1188    #[inline]
1189    pub fn swap_remove(&mut self, index: usize) -> T {
1190        unsafe {
1191            // We replace self[index] with the last element. Note that if the
1192            // bounds check on hole succeeds there must be a last element (which
1193            // can be self[index] itself).
1194            let hole: *mut T = &mut self[index];
1195            let last = ptr::read(self.get_unchecked(self.len - 1));
1196            self.len -= 1;
1197            ptr::replace(hole, last)
1198        }
1199    }
1200
1201    /// Inserts an element at position `index` within the vector, shifting all
1202    /// elements after it to the right.
1203    ///
1204    /// # Panics
1205    ///
1206    /// Panics if `index > len`.
1207    ///
1208    /// # Examples
1209    ///
1210    /// ```
1211    /// use bumpalo::{Bump, collections::Vec};
1212    ///
1213    /// let b = Bump::new();
1214    ///
1215    /// let mut vec = bumpalo::vec![in &b; 1, 2, 3];
1216    /// vec.insert(1, 4);
1217    /// assert_eq!(vec, [1, 4, 2, 3]);
1218    /// vec.insert(4, 5);
1219    /// assert_eq!(vec, [1, 4, 2, 3, 5]);
1220    /// ```
1221    pub fn insert(&mut self, index: usize, element: T) {
1222        let len = self.len();
1223        assert!(index <= len);
1224
1225        // space for the new element
1226        if len == self.buf.cap() {
1227            self.reserve(1);
1228        }
1229
1230        unsafe {
1231            // infallible
1232            // The spot to put the new value
1233            {
1234                let p = self.as_mut_ptr().add(index);
1235                // Shift everything over to make space. (Duplicating the
1236                // `index`th element into two consecutive places.)
1237                ptr::copy(p, p.offset(1), len - index);
1238                // Write it in, overwriting the first copy of the `index`th
1239                // element.
1240                ptr::write(p, element);
1241            }
1242            self.set_len(len + 1);
1243        }
1244    }
1245
1246    /// Removes and returns the element at position `index` within the vector,
1247    /// shifting all elements after it to the left.
1248    ///
1249    /// # Panics
1250    ///
1251    /// Panics if `index` is out of bounds.
1252    ///
1253    /// # Examples
1254    ///
1255    /// ```
1256    /// use bumpalo::{Bump, collections::Vec};
1257    ///
1258    /// let b = Bump::new();
1259    ///
1260    /// let mut v = bumpalo::vec![in &b; 1, 2, 3];
1261    /// assert_eq!(v.remove(1), 2);
1262    /// assert_eq!(v, [1, 3]);
1263    /// ```
1264    pub fn remove(&mut self, index: usize) -> T {
1265        let len = self.len();
1266        assert!(index < len);
1267        unsafe {
1268            // infallible
1269            let ret;
1270            {
1271                // the place we are taking from.
1272                let ptr = self.as_mut_ptr().add(index);
1273                // copy it out, unsafely having a copy of the value on
1274                // the stack and in the vector at the same time.
1275                ret = ptr::read(ptr);
1276
1277                // Shift everything down to fill in that spot.
1278                ptr::copy(ptr.offset(1), ptr, len - index - 1);
1279            }
1280            self.set_len(len - 1);
1281            ret
1282        }
1283    }
1284
1285    /// Retains only the elements specified by the predicate.
1286    ///
1287    /// In other words, remove all elements `e` such that `f(&e)` returns `false`.
1288    /// This method operates in place and preserves the order of the retained
1289    /// elements.
1290    ///
1291    /// # Examples
1292    ///
1293    /// ```
1294    /// use bumpalo::{Bump, collections::Vec};
1295    ///
1296    /// let b = Bump::new();
1297    ///
1298    /// let mut vec = bumpalo::vec![in &b; 1, 2, 3, 4];
1299    /// vec.retain(|&x| x % 2 == 0);
1300    /// assert_eq!(vec, [2, 4]);
1301    /// ```
1302    pub fn retain<F>(&mut self, mut f: F)
1303    where
1304        F: FnMut(&T) -> bool,
1305    {
1306        self.drain_filter(|x| !f(x));
1307    }
1308
1309    /// Creates an iterator that removes the elements in the vector
1310    /// for which the predicate returns `true` and yields the removed items.
1311    ///
1312    /// # Examples
1313    ///
1314    /// ```
1315    /// use bumpalo::Bump;
1316    /// use bumpalo::collections::{CollectIn, Vec};
1317    ///
1318    /// let b = Bump::new();
1319    ///
1320    /// let mut numbers = bumpalo::vec![in &b; 1, 2, 3, 4, 5];
1321    ///
1322    /// let evens: Vec<_> = numbers.drain_filter(|x| *x % 2 == 0).collect_in(&b);
1323    ///
1324    /// assert_eq!(numbers, &[1, 3, 5]);
1325    /// assert_eq!(evens, &[2, 4]);
1326    /// ```
1327    pub fn drain_filter<'a, F>(&'a mut self, filter: F) -> DrainFilter<'a, 'bump, T, F>
1328    where
1329        F: FnMut(&mut T) -> bool,
1330    {
1331        let old_len = self.len();
1332
1333        // Guard against us getting leaked (leak amplification)
1334        unsafe {
1335            self.set_len(0);
1336        }
1337
1338        DrainFilter {
1339            vec: self,
1340            idx: 0,
1341            del: 0,
1342            old_len,
1343            pred: filter,
1344        }
1345    }
1346
1347    /// Removes all but the first of consecutive elements in the vector that resolve to the same
1348    /// key.
1349    ///
1350    /// If the vector is sorted, this removes all duplicates.
1351    ///
1352    /// # Examples
1353    ///
1354    /// ```
1355    /// use bumpalo::{Bump, collections::Vec};
1356    ///
1357    /// let b = Bump::new();
1358    ///
1359    /// let mut vec = bumpalo::vec![in &b; 10, 20, 21, 30, 20];
1360    ///
1361    /// vec.dedup_by_key(|i| *i / 10);
1362    ///
1363    /// assert_eq!(vec, [10, 20, 30, 20]);
1364    /// ```
1365    #[inline]
1366    pub fn dedup_by_key<F, K>(&mut self, mut key: F)
1367    where
1368        F: FnMut(&mut T) -> K,
1369        K: PartialEq,
1370    {
1371        self.dedup_by(|a, b| key(a) == key(b))
1372    }
1373
1374    /// Removes all but the first of consecutive elements in the vector satisfying a given equality
1375    /// relation.
1376    ///
1377    /// The `same_bucket` function is passed references to two elements from the vector and
1378    /// must determine if the elements compare equal. The elements are passed in opposite order
1379    /// from their order in the slice, so if `same_bucket(a, b)` returns `true`, `a` is removed.
1380    ///
1381    /// If the vector is sorted, this removes all duplicates.
1382    ///
1383    /// # Examples
1384    ///
1385    /// ```
1386    /// use bumpalo::{Bump, collections::Vec};
1387    ///
1388    /// let b = Bump::new();
1389    ///
1390    /// let mut vec = bumpalo::vec![in &b; "foo", "bar", "Bar", "baz", "bar"];
1391    ///
1392    /// vec.dedup_by(|a, b| a.eq_ignore_ascii_case(b));
1393    ///
1394    /// assert_eq!(vec, ["foo", "bar", "baz", "bar"]);
1395    /// ```
1396    pub fn dedup_by<F>(&mut self, same_bucket: F)
1397    where
1398        F: FnMut(&mut T, &mut T) -> bool,
1399    {
1400        let len = {
1401            let (dedup, _) = partition_dedup_by(self.as_mut_slice(), same_bucket);
1402            dedup.len()
1403        };
1404        self.truncate(len);
1405    }
1406
1407    /// Appends an element to the back of a vector.
1408    ///
1409    /// # Panics
1410    ///
1411    /// Panics if the number of elements in the vector overflows a `usize`.
1412    ///
1413    /// # Examples
1414    ///
1415    /// ```
1416    /// use bumpalo::{Bump, collections::Vec};
1417    ///
1418    /// let b = Bump::new();
1419    ///
1420    /// let mut vec = bumpalo::vec![in &b; 1, 2];
1421    /// vec.push(3);
1422    /// assert_eq!(vec, [1, 2, 3]);
1423    /// ```
1424    #[inline]
1425    pub fn push(&mut self, value: T) {
1426        // This will panic or abort if we would allocate > isize::MAX bytes
1427        // or if the length increment would overflow for zero-sized types.
1428        if self.len == self.buf.cap() {
1429            self.reserve(1);
1430        }
1431        unsafe {
1432            let end = self.buf.ptr().add(self.len);
1433            ptr::write(end, value);
1434            self.len += 1;
1435        }
1436    }
1437
1438    /// Removes the last element from a vector and returns it, or [`None`] if it
1439    /// is empty.
1440    ///
1441    /// [`None`]: https://doc.rust-lang.org/std/option/enum.Option.html#variant.None
1442    ///
1443    /// # Examples
1444    ///
1445    /// ```
1446    /// use bumpalo::{Bump, collections::Vec};
1447    ///
1448    /// let b = Bump::new();
1449    ///
1450    /// let mut vec = bumpalo::vec![in &b; 1, 2, 3];
1451    /// assert_eq!(vec.pop(), Some(3));
1452    /// assert_eq!(vec, [1, 2]);
1453    /// ```
1454    #[inline]
1455    pub fn pop(&mut self) -> Option<T> {
1456        if self.len == 0 {
1457            None
1458        } else {
1459            unsafe {
1460                self.len -= 1;
1461                Some(ptr::read(self.as_ptr().add(self.len())))
1462            }
1463        }
1464    }
1465
1466    /// Moves all the elements of `other` into `Self`, leaving `other` empty.
1467    ///
1468    /// # Panics
1469    ///
1470    /// Panics if the number of elements in the vector overflows a `usize`.
1471    ///
1472    /// # Examples
1473    ///
1474    /// ```
1475    /// use bumpalo::{Bump, collections::Vec};
1476    ///
1477    /// let b = Bump::new();
1478    ///
1479    /// let mut vec = bumpalo::vec![in &b; 1, 2, 3];
1480    /// let mut vec2 = bumpalo::vec![in &b; 4, 5, 6];
1481    /// vec.append(&mut vec2);
1482    /// assert_eq!(vec, [1, 2, 3, 4, 5, 6]);
1483    /// assert_eq!(vec2, []);
1484    /// ```
1485    #[inline]
1486    pub fn append(&mut self, other: &mut Self) {
1487        unsafe {
1488            self.append_elements(other.as_slice() as _);
1489            other.set_len(0);
1490        }
1491    }
1492
1493    /// Appends elements to `Self` from other buffer.
1494    #[inline]
1495    unsafe fn append_elements(&mut self, other: *const [T]) {
1496        let count = (*other).len();
1497        self.reserve(count);
1498        let len = self.len();
1499        ptr::copy_nonoverlapping(other as *const T, self.as_mut_ptr().add(len), count);
1500        self.len += count;
1501    }
1502
1503    /// Creates a draining iterator that removes the specified range in the vector
1504    /// and yields the removed items.
1505    ///
1506    /// Note 1: The element range is removed even if the iterator is only
1507    /// partially consumed or not consumed at all.
1508    ///
1509    /// Note 2: It is unspecified how many elements are removed from the vector
1510    /// if the `Drain` value is leaked.
1511    ///
1512    /// # Panics
1513    ///
1514    /// Panics if the starting point is greater than the end point or if
1515    /// the end point is greater than the length of the vector.
1516    ///
1517    /// # Examples
1518    ///
1519    /// ```
1520    /// use bumpalo::Bump;
1521    /// use bumpalo::collections::{CollectIn, Vec};
1522    ///
1523    /// let b = Bump::new();
1524    ///
1525    /// let mut v = bumpalo::vec![in &b; 1, 2, 3];
1526    ///
1527    /// let u: Vec<_> = v.drain(1..).collect_in(&b);
1528    ///
1529    /// assert_eq!(v, &[1]);
1530    /// assert_eq!(u, &[2, 3]);
1531    ///
1532    /// // A full range clears the vector
1533    /// v.drain(..);
1534    /// assert_eq!(v, &[]);
1535    /// ```
1536    pub fn drain<R>(&mut self, range: R) -> Drain<T>
1537    where
1538        R: RangeBounds<usize>,
1539    {
1540        // Memory safety
1541        //
1542        // When the Drain is first created, it shortens the length of
1543        // the source vector to make sure no uninitialized or moved-from elements
1544        // are accessible at all if the Drain's destructor never gets to run.
1545        //
1546        // Drain will ptr::read out the values to remove.
1547        // When finished, remaining tail of the vec is copied back to cover
1548        // the hole, and the vector length is restored to the new length.
1549        //
1550        let len = self.len();
1551        let start = match range.start_bound() {
1552            Included(&n) => n,
1553            Excluded(&n) => n + 1,
1554            Unbounded => 0,
1555        };
1556        let end = match range.end_bound() {
1557            Included(&n) => n + 1,
1558            Excluded(&n) => n,
1559            Unbounded => len,
1560        };
1561        assert!(start <= end);
1562        assert!(end <= len);
1563
1564        unsafe {
1565            // set self.vec length's to start, to be safe in case Drain is leaked
1566            self.set_len(start);
1567            // Use the borrow in the IterMut to indicate borrowing behavior of the
1568            // whole Drain iterator (like &mut T).
1569            let range_slice = slice::from_raw_parts_mut(self.as_mut_ptr().add(start), end - start);
1570            Drain {
1571                tail_start: end,
1572                tail_len: len - end,
1573                iter: range_slice.iter(),
1574                vec: NonNull::from(self),
1575            }
1576        }
1577    }
1578
1579    /// Clears the vector, removing all values.
1580    ///
1581    /// Note that this method has no effect on the allocated capacity
1582    /// of the vector.
1583    ///
1584    /// # Examples
1585    ///
1586    /// ```
1587    /// use bumpalo::{Bump, collections::Vec};
1588    ///
1589    /// let b = Bump::new();
1590    ///
1591    /// let mut v = bumpalo::vec![in &b; 1, 2, 3];
1592    ///
1593    /// v.clear();
1594    ///
1595    /// assert!(v.is_empty());
1596    /// ```
1597    #[inline]
1598    pub fn clear(&mut self) {
1599        self.truncate(0)
1600    }
1601
1602    /// Returns the number of elements in the vector, also referred to
1603    /// as its 'length'.
1604    ///
1605    /// # Examples
1606    ///
1607    /// ```
1608    /// use bumpalo::{Bump, collections::Vec};
1609    ///
1610    /// let b = Bump::new();
1611    ///
1612    /// let a = bumpalo::vec![in &b; 1, 2, 3];
1613    /// assert_eq!(a.len(), 3);
1614    /// ```
1615    #[inline]
1616    pub fn len(&self) -> usize {
1617        self.len
1618    }
1619
1620    /// Returns `true` if the vector contains no elements.
1621    ///
1622    /// # Examples
1623    ///
1624    /// ```
1625    /// use bumpalo::{Bump, collections::Vec};
1626    ///
1627    /// let b = Bump::new();
1628    ///
1629    /// let mut v = Vec::new_in(&b);
1630    /// assert!(v.is_empty());
1631    ///
1632    /// v.push(1);
1633    /// assert!(!v.is_empty());
1634    /// ```
1635    pub fn is_empty(&self) -> bool {
1636        self.len() == 0
1637    }
1638
1639    /// Splits the collection into two at the given index.
1640    ///
1641    /// Returns a newly allocated vector. `self` contains elements `[0, at)`,
1642    /// and the returned vector contains elements `[at, len)`.
1643    ///
1644    /// Note that the capacity of `self` does not change.
1645    ///
1646    /// # Panics
1647    ///
1648    /// Panics if `at > len`.
1649    ///
1650    /// # Examples
1651    ///
1652    /// ```
1653    /// use bumpalo::{Bump, collections::Vec};
1654    ///
1655    /// let b = Bump::new();
1656    ///
1657    /// let mut vec = bumpalo::vec![in &b; 1, 2, 3];
1658    /// let vec2 = vec.split_off(1);
1659    /// assert_eq!(vec, [1]);
1660    /// assert_eq!(vec2, [2, 3]);
1661    /// ```
1662    #[inline]
1663    pub fn split_off(&mut self, at: usize) -> Self {
1664        assert!(at <= self.len(), "`at` out of bounds");
1665
1666        let other_len = self.len - at;
1667        let mut other = Vec::with_capacity_in(other_len, self.buf.bump());
1668
1669        // Unsafely `set_len` and copy items to `other`.
1670        unsafe {
1671            self.set_len(at);
1672            other.set_len(other_len);
1673
1674            ptr::copy_nonoverlapping(self.as_ptr().add(at), other.as_mut_ptr(), other.len());
1675        }
1676        other
1677    }
1678}
1679
1680#[cfg(feature = "boxed")]
1681impl<'bump, T> Vec<'bump, T> {
1682    /// Converts the vector into [`Box<[T]>`][owned slice].
1683    ///
1684    /// Note that this will drop any excess capacity.
1685    ///
1686    /// [owned slice]: ../../boxed/struct.Box.html
1687    ///
1688    /// # Examples
1689    ///
1690    /// ```
1691    /// use bumpalo::{Bump, collections::Vec, vec};
1692    ///
1693    /// let b = Bump::new();
1694    ///
1695    /// let v = vec![in &b; 1, 2, 3];
1696    ///
1697    /// let slice = v.into_boxed_slice();
1698    /// ```
1699    pub fn into_boxed_slice(mut self) -> crate::boxed::Box<'bump, [T]> {
1700        use crate::boxed::Box;
1701
1702        // Unlike `alloc::vec::Vec` shrinking here isn't necessary as `bumpalo::boxed::Box` doesn't own memory.
1703        unsafe {
1704            let slice = slice::from_raw_parts_mut(self.as_mut_ptr(), self.len);
1705            let output: Box<'bump, [T]> = Box::from_raw(slice);
1706            mem::forget(self);
1707            output
1708        }
1709    }
1710}
1711
1712impl<'bump, T: 'bump + Clone> Vec<'bump, T> {
1713    /// Resizes the `Vec` in-place so that `len` is equal to `new_len`.
1714    ///
1715    /// If `new_len` is greater than `len`, the `Vec` is extended by the
1716    /// difference, with each additional slot filled with `value`.
1717    /// If `new_len` is less than `len`, the `Vec` is simply truncated.
1718    ///
1719    /// This method requires [`Clone`] to be able clone the passed value. If
1720    /// you need more flexibility (or want to rely on [`Default`] instead of
1721    /// [`Clone`]), use [`resize_with`].
1722    ///
1723    /// # Examples
1724    ///
1725    /// ```
1726    /// use bumpalo::{Bump, collections::Vec};
1727    ///
1728    /// let b = Bump::new();
1729    ///
1730    /// let mut vec = bumpalo::vec![in &b; "hello"];
1731    /// vec.resize(3, "world");
1732    /// assert_eq!(vec, ["hello", "world", "world"]);
1733    ///
1734    /// let mut vec = bumpalo::vec![in &b; 1, 2, 3, 4];
1735    /// vec.resize(2, 0);
1736    /// assert_eq!(vec, [1, 2]);
1737    /// ```
1738    ///
1739    /// [`Clone`]: https://doc.rust-lang.org/std/clone/trait.Clone.html
1740    /// [`Default`]: https://doc.rust-lang.org/std/default/trait.Default.html
1741    /// [`resize_with`]: #method.resize_with
1742    pub fn resize(&mut self, new_len: usize, value: T) {
1743        let len = self.len();
1744
1745        if new_len > len {
1746            self.extend_with(new_len - len, ExtendElement(value))
1747        } else {
1748            self.truncate(new_len);
1749        }
1750    }
1751
1752    /// Clones and appends all elements in a slice to the `Vec`.
1753    ///
1754    /// Iterates over the slice `other`, clones each element, and then appends
1755    /// it to this `Vec`. The `other` vector is traversed in-order.
1756    ///
1757    /// Note that this function is same as [`extend`] except that it is
1758    /// specialized to work with slices instead. If and when Rust gets
1759    /// specialization this function will likely be deprecated (but still
1760    /// available).
1761    ///
1762    /// # Examples
1763    ///
1764    /// ```
1765    /// use bumpalo::{Bump, collections::Vec};
1766    ///
1767    /// let b = Bump::new();
1768    ///
1769    /// let mut vec = bumpalo::vec![in &b; 1];
1770    /// vec.extend_from_slice(&[2, 3, 4]);
1771    /// assert_eq!(vec, [1, 2, 3, 4]);
1772    /// ```
1773    ///
1774    /// [`extend`]: #method.extend
1775    pub fn extend_from_slice(&mut self, other: &[T]) {
1776        self.extend(other.iter().cloned())
1777    }
1778}
1779
1780impl<'bump, T: 'bump + Copy> Vec<'bump, T> {
1781    /// Helper method to copy all of the items in `other` and append them to the end of `self`.
1782    ///
1783    /// SAFETY:
1784    ///   * The caller is responsible for:
1785    ///       * calling [`reserve`](Self::reserve) beforehand to guarantee that there is enough
1786    ///         capacity to store `other.len()` more items.
1787    ///       * guaranteeing that `self` and `other` do not overlap.
1788    unsafe fn extend_from_slice_copy_unchecked(&mut self, other: &[T]) {
1789        let old_len = self.len();
1790        debug_assert!(old_len + other.len() <= self.capacity());
1791
1792        // SAFETY:
1793        // * `src` is valid for reads of `other.len()` values by virtue of being a `&[T]`.
1794        // * `dst` is valid for writes of `other.len()` bytes because the caller of this
1795        //   method is required to `reserve` capacity to store at least `other.len()` items
1796        //   beforehand.
1797        // * Because `src` is a `&[T]` and dst is a `&[T]` within the `Vec<T>`,
1798        //   `copy_nonoverlapping`'s alignment requirements are met.
1799        // * Caller is required to guarantee that the source and destination ranges cannot overlap
1800        unsafe {
1801            let src = other.as_ptr();
1802            let dst = self.as_mut_ptr().add(old_len);
1803            ptr::copy_nonoverlapping(src, dst, other.len());
1804            self.set_len(old_len + other.len());
1805        }
1806    }
1807
1808
1809    /// Copies all elements in the slice `other` and appends them to the `Vec`.
1810    ///
1811    /// Note that this function is same as [`extend_from_slice`] except that it is optimized for
1812    /// slices of types that implement the `Copy` trait. If and when Rust gets specialization
1813    /// this function will likely be deprecated (but still available).
1814    ///
1815    /// To copy and append the data from multiple source slices at once, see
1816    /// [`extend_from_slices_copy`].
1817    ///
1818    /// # Examples
1819    ///
1820    /// ```
1821    /// use bumpalo::{Bump, collections::Vec};
1822    ///
1823    /// let b = Bump::new();
1824    ///
1825    /// let mut vec = bumpalo::vec![in &b; 1];
1826    /// vec.extend_from_slice_copy(&[2, 3, 4]);
1827    /// assert_eq!(vec, [1, 2, 3, 4]);
1828    /// ```
1829    ///
1830    /// ```
1831    /// use bumpalo::{Bump, collections::Vec};
1832    ///
1833    /// let b = Bump::new();
1834    ///
1835    /// let mut vec = bumpalo::vec![in &b; 'H' as u8];
1836    /// vec.extend_from_slice_copy("ello, world!".as_bytes());
1837    /// assert_eq!(vec, "Hello, world!".as_bytes());
1838    /// ```
1839    ///
1840    /// [`extend_from_slice`]: #method.extend_from_slice
1841    /// [`extend_from_slices`]: #method.extend_from_slices
1842    pub fn extend_from_slice_copy(&mut self, other: &[T]) {
1843        // Reserve space in the Vec for the values to be added
1844        self.reserve(other.len());
1845
1846        // Copy values into the space that was just reserved
1847        // SAFETY:
1848        // * `self` has enough capacity to store `other.len()` more items as `self.reserve(other.len())`
1849        //   above guarantees that.
1850        // * Source and destination data ranges cannot overlap as we just reserved the destination
1851        //   range from the bump.
1852        unsafe {
1853            self.extend_from_slice_copy_unchecked(other);
1854        }
1855    }
1856
1857    /// For each slice in `slices`, copies all elements in the slice and appends them to the `Vec`.
1858    ///
1859    /// This method is equivalent to calling [`extend_from_slice_copy`] in a loop, but is able
1860    /// to precompute the total amount of space to reserve in advance. This reduces the potential
1861    /// maximum number of reallocations needed from one-per-slice to just one.
1862    ///
1863    /// # Examples
1864    ///
1865    /// ```
1866    /// use bumpalo::{Bump, collections::Vec};
1867    ///
1868    /// let b = Bump::new();
1869    ///
1870    /// let mut vec = bumpalo::vec![in &b; 1];
1871    /// vec.extend_from_slices_copy(&[&[2, 3], &[], &[4]]);
1872    /// assert_eq!(vec, [1, 2, 3, 4]);
1873    /// ```
1874    ///
1875    /// ```
1876    /// use bumpalo::{Bump, collections::Vec};
1877    ///
1878    /// let b = Bump::new();
1879    ///
1880    /// let mut vec = bumpalo::vec![in &b; 'H' as u8];
1881    /// vec.extend_from_slices_copy(&["ello,".as_bytes(), &[], " world!".as_bytes()]);
1882    /// assert_eq!(vec, "Hello, world!".as_bytes());
1883    /// ```
1884    ///
1885    /// [`extend_from_slice_copy`]: #method.extend_from_slice_copy
1886    pub fn extend_from_slices_copy(&mut self, slices: &[&[T]]) {
1887        // Reserve the total amount of capacity we'll need to safely append the aggregated contents
1888        // of each slice in `slices`.
1889        let capacity_to_reserve: usize = slices.iter().map(|slice| slice.len()).sum();
1890        self.reserve(capacity_to_reserve);
1891
1892        // SAFETY:
1893        // * `dst` is valid for writes of `capacity_to_reserve` items as
1894        //   `self.reserve(capacity_to_reserve)` above guarantees that.
1895        // * Source and destination ranges cannot overlap as we just reserved the destination
1896        //   range from the bump.
1897        unsafe {
1898            // Copy the contents of each slice onto the end of `self`
1899            slices.iter().for_each(|slice| {
1900                self.extend_from_slice_copy_unchecked(slice);
1901            });
1902        }
1903    }
1904}
1905
1906// This code generalises `extend_with_{element,default}`.
1907trait ExtendWith<T> {
1908    fn next(&mut self) -> T;
1909    fn last(self) -> T;
1910}
1911
1912struct ExtendElement<T>(T);
1913impl<T: Clone> ExtendWith<T> for ExtendElement<T> {
1914    fn next(&mut self) -> T {
1915        self.0.clone()
1916    }
1917    fn last(self) -> T {
1918        self.0
1919    }
1920}
1921
1922impl<'bump, T: 'bump> Vec<'bump, T> {
1923    /// Extend the vector by `n` values, using the given generator.
1924    fn extend_with<E: ExtendWith<T>>(&mut self, n: usize, mut value: E) {
1925        self.reserve(n);
1926
1927        unsafe {
1928            let mut ptr = self.as_mut_ptr().add(self.len());
1929            // Use SetLenOnDrop to work around bug where compiler
1930            // may not realize the store through `ptr` through self.set_len()
1931            // don't alias.
1932            let mut local_len = SetLenOnDrop::new(&mut self.len);
1933
1934            // Write all elements except the last one
1935            for _ in 1..n {
1936                ptr::write(ptr, value.next());
1937                ptr = ptr.offset(1);
1938                // Increment the length in every step in case next() panics
1939                local_len.increment_len(1);
1940            }
1941
1942            if n > 0 {
1943                // We can write the last element directly without cloning needlessly
1944                ptr::write(ptr, value.last());
1945                local_len.increment_len(1);
1946            }
1947
1948            // len set by scope guard
1949        }
1950    }
1951}
1952
1953// Set the length of the vec when the `SetLenOnDrop` value goes out of scope.
1954//
1955// The idea is: The length field in SetLenOnDrop is a local variable
1956// that the optimizer will see does not alias with any stores through the Vec's data
1957// pointer. This is a workaround for alias analysis issue #32155
1958struct SetLenOnDrop<'a> {
1959    len: &'a mut usize,
1960    local_len: usize,
1961}
1962
1963impl<'a> SetLenOnDrop<'a> {
1964    #[inline]
1965    fn new(len: &'a mut usize) -> Self {
1966        SetLenOnDrop {
1967            local_len: *len,
1968            len,
1969        }
1970    }
1971
1972    #[inline]
1973    fn increment_len(&mut self, increment: usize) {
1974        self.local_len += increment;
1975    }
1976
1977    #[inline]
1978    fn decrement_len(&mut self, decrement: usize) {
1979        self.local_len -= decrement;
1980    }
1981}
1982
1983impl<'a> Drop for SetLenOnDrop<'a> {
1984    #[inline]
1985    fn drop(&mut self) {
1986        *self.len = self.local_len;
1987    }
1988}
1989
1990impl<'bump, T: 'bump + PartialEq> Vec<'bump, T> {
1991    /// Removes consecutive repeated elements in the vector according to the
1992    /// [`PartialEq`] trait implementation.
1993    ///
1994    /// If the vector is sorted, this removes all duplicates.
1995    ///
1996    /// # Examples
1997    ///
1998    /// ```
1999    /// use bumpalo::{Bump, collections::Vec};
2000    ///
2001    /// let b = Bump::new();
2002    ///
2003    /// let mut vec = bumpalo::vec![in &b; 1, 2, 2, 3, 2];
2004    ///
2005    /// vec.dedup();
2006    ///
2007    /// assert_eq!(vec, [1, 2, 3, 2]);
2008    /// ```
2009    #[inline]
2010    pub fn dedup(&mut self) {
2011        self.dedup_by(|a, b| a == b)
2012    }
2013}
2014
2015////////////////////////////////////////////////////////////////////////////////
2016// Common trait implementations for Vec
2017////////////////////////////////////////////////////////////////////////////////
2018
2019impl<'bump, T: 'bump + Clone> Clone for Vec<'bump, T> {
2020    #[cfg(not(test))]
2021    fn clone(&self) -> Vec<'bump, T> {
2022        let mut v = Vec::with_capacity_in(self.len(), self.buf.bump());
2023        v.extend(self.iter().cloned());
2024        v
2025    }
2026
2027    // HACK(japaric): with cfg(test) the inherent `[T]::to_vec` method, which is
2028    // required for this method definition, is not available. Instead use the
2029    // `slice::to_vec`  function which is only available with cfg(test)
2030    // NB see the slice::hack module in slice.rs for more information
2031    #[cfg(test)]
2032    fn clone(&self) -> Vec<'bump, T> {
2033        let mut v = Vec::new_in(self.buf.bump());
2034        v.extend(self.iter().cloned());
2035        v
2036    }
2037}
2038
2039impl<'bump, T: 'bump + Hash> Hash for Vec<'bump, T> {
2040    #[inline]
2041    fn hash<H: hash::Hasher>(&self, state: &mut H) {
2042        Hash::hash(&**self, state)
2043    }
2044}
2045
2046impl<'bump, T, I> Index<I> for Vec<'bump, T>
2047where
2048    I: ::core::slice::SliceIndex<[T]>,
2049{
2050    type Output = I::Output;
2051
2052    #[inline]
2053    fn index(&self, index: I) -> &Self::Output {
2054        Index::index(&**self, index)
2055    }
2056}
2057
2058impl<'bump, T, I> IndexMut<I> for Vec<'bump, T>
2059where
2060    I: ::core::slice::SliceIndex<[T]>,
2061{
2062    #[inline]
2063    fn index_mut(&mut self, index: I) -> &mut Self::Output {
2064        IndexMut::index_mut(&mut **self, index)
2065    }
2066}
2067
2068impl<'bump, T: 'bump> ops::Deref for Vec<'bump, T> {
2069    type Target = [T];
2070
2071    fn deref(&self) -> &[T] {
2072        unsafe {
2073            let p = self.buf.ptr();
2074            // assume(!p.is_null());
2075            slice::from_raw_parts(p, self.len)
2076        }
2077    }
2078}
2079
2080impl<'bump, T: 'bump> ops::DerefMut for Vec<'bump, T> {
2081    fn deref_mut(&mut self) -> &mut [T] {
2082        unsafe {
2083            let ptr = self.buf.ptr();
2084            // assume(!ptr.is_null());
2085            slice::from_raw_parts_mut(ptr, self.len)
2086        }
2087    }
2088}
2089
2090impl<'bump, T: 'bump> IntoIterator for Vec<'bump, T> {
2091    type Item = T;
2092    type IntoIter = IntoIter<'bump, T>;
2093
2094    /// Creates a consuming iterator, that is, one that moves each value out of
2095    /// the vector (from start to end). The vector cannot be used after calling
2096    /// this.
2097    ///
2098    /// # Examples
2099    ///
2100    /// ```
2101    /// use bumpalo::{Bump, collections::Vec};
2102    ///
2103    /// let b = Bump::new();
2104    ///
2105    /// let v = bumpalo::vec![in &b; "a".to_string(), "b".to_string()];
2106    /// for s in v.into_iter() {
2107    ///     // s has type String, not &String
2108    ///     println!("{}", s);
2109    /// }
2110    /// ```
2111    #[inline]
2112    fn into_iter(mut self) -> IntoIter<'bump, T> {
2113        unsafe {
2114            let begin = self.as_mut_ptr();
2115            // assume(!begin.is_null());
2116            let end = if mem::size_of::<T>() == 0 {
2117                arith_offset(begin as *const i8, self.len() as isize) as *const T
2118            } else {
2119                begin.add(self.len()) as *const T
2120            };
2121            mem::forget(self);
2122            IntoIter {
2123                phantom: PhantomData,
2124                ptr: begin,
2125                end,
2126            }
2127        }
2128    }
2129}
2130
2131impl<'a, 'bump, T> IntoIterator for &'a Vec<'bump, T> {
2132    type Item = &'a T;
2133    type IntoIter = slice::Iter<'a, T>;
2134
2135    fn into_iter(self) -> slice::Iter<'a, T> {
2136        self.iter()
2137    }
2138}
2139
2140impl<'a, 'bump, T> IntoIterator for &'a mut Vec<'bump, T> {
2141    type Item = &'a mut T;
2142    type IntoIter = slice::IterMut<'a, T>;
2143
2144    fn into_iter(self) -> slice::IterMut<'a, T> {
2145        self.iter_mut()
2146    }
2147}
2148
2149impl<'bump, T: 'bump> Extend<T> for Vec<'bump, T> {
2150    #[inline]
2151    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
2152        let iter = iter.into_iter();
2153        self.reserve(iter.size_hint().0);
2154
2155        for t in iter {
2156            self.push(t);
2157        }
2158    }
2159}
2160
2161impl<'bump, T: 'bump> Vec<'bump, T> {
2162    /// Creates a splicing iterator that replaces the specified range in the vector
2163    /// with the given `replace_with` iterator and yields the removed items.
2164    /// `replace_with` does not need to be the same length as `range`.
2165    ///
2166    /// Note 1: The element range is removed even if the iterator is not
2167    /// consumed until the end.
2168    ///
2169    /// Note 2: It is unspecified how many elements are removed from the vector,
2170    /// if the `Splice` value is leaked.
2171    ///
2172    /// Note 3: The input iterator `replace_with` is only consumed
2173    /// when the `Splice` value is dropped.
2174    ///
2175    /// Note 4: This is optimal if:
2176    ///
2177    /// * The tail (elements in the vector after `range`) is empty,
2178    /// * or `replace_with` yields fewer elements than `range`’s length
2179    /// * or the lower bound of its `size_hint()` is exact.
2180    ///
2181    /// Otherwise, a temporary vector is allocated and the tail is moved twice.
2182    ///
2183    /// # Panics
2184    ///
2185    /// Panics if the starting point is greater than the end point or if
2186    /// the end point is greater than the length of the vector.
2187    ///
2188    /// # Examples
2189    ///
2190    /// ```
2191    /// use bumpalo::{Bump, collections::Vec};
2192    ///
2193    /// let b = Bump::new();
2194    ///
2195    /// let mut v = bumpalo::vec![in &b; 1, 2, 3];
2196    /// let new = [7, 8];
2197    /// let u: Vec<_> = Vec::from_iter_in(v.splice(..2, new.iter().cloned()), &b);
2198    /// assert_eq!(v, &[7, 8, 3]);
2199    /// assert_eq!(u, &[1, 2]);
2200    /// ```
2201    #[inline]
2202    pub fn splice<R, I>(&mut self, range: R, replace_with: I) -> Splice<I::IntoIter>
2203    where
2204        R: RangeBounds<usize>,
2205        I: IntoIterator<Item = T>,
2206    {
2207        Splice {
2208            drain: self.drain(range),
2209            replace_with: replace_with.into_iter(),
2210        }
2211    }
2212}
2213
2214/// Extend implementation that copies elements out of references before pushing them onto the Vec.
2215///
2216/// This implementation is specialized for slice iterators, where it uses [`copy_from_slice`] to
2217/// append the entire slice at once.
2218///
2219/// [`copy_from_slice`]: https://doc.rust-lang.org/std/primitive.slice.html#method.copy_from_slice
2220impl<'a, 'bump, T: 'a + Copy> Extend<&'a T> for Vec<'bump, T> {
2221    fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
2222        self.extend(iter.into_iter().cloned())
2223    }
2224}
2225
2226macro_rules! __impl_slice_eq1 {
2227    ($Lhs: ty, $Rhs: ty) => {
2228        __impl_slice_eq1! { $Lhs, $Rhs, Sized }
2229    };
2230    ($Lhs: ty, $Rhs: ty, $Bound: ident) => {
2231        impl<'a, 'b, A: $Bound, B> PartialEq<$Rhs> for $Lhs
2232        where
2233            A: PartialEq<B>,
2234        {
2235            #[inline]
2236            fn eq(&self, other: &$Rhs) -> bool {
2237                self[..] == other[..]
2238            }
2239        }
2240    };
2241}
2242
2243__impl_slice_eq1! { Vec<'a, A>, Vec<'b, B> }
2244__impl_slice_eq1! { Vec<'a, A>, &'b [B] }
2245__impl_slice_eq1! { Vec<'a, A>, &'b mut [B] }
2246// __impl_slice_eq1! { Cow<'a, [A]>, Vec<'b, B>, Clone }
2247
2248macro_rules! __impl_slice_eq1_array {
2249    ($Lhs: ty, $Rhs: ty) => {
2250        impl<'a, 'b, A, B, const N: usize> PartialEq<$Rhs> for $Lhs
2251        where
2252            A: PartialEq<B>,
2253        {
2254            #[inline]
2255            fn eq(&self, other: &$Rhs) -> bool {
2256                self[..] == other[..]
2257            }
2258        }
2259    };
2260}
2261
2262__impl_slice_eq1_array! { Vec<'a, A>, [B; N] }
2263__impl_slice_eq1_array! { Vec<'a, A>, &'b [B; N] }
2264__impl_slice_eq1_array! { Vec<'a, A>, &'b mut [B; N] }
2265
2266/// Implements comparison of vectors, lexicographically.
2267impl<'bump, T: 'bump + PartialOrd> PartialOrd for Vec<'bump, T> {
2268    #[inline]
2269    fn partial_cmp(&self, other: &Vec<'bump, T>) -> Option<Ordering> {
2270        PartialOrd::partial_cmp(&**self, &**other)
2271    }
2272}
2273
2274impl<'bump, T: 'bump + Eq> Eq for Vec<'bump, T> {}
2275
2276/// Implements ordering of vectors, lexicographically.
2277impl<'bump, T: 'bump + Ord> Ord for Vec<'bump, T> {
2278    #[inline]
2279    fn cmp(&self, other: &Vec<'bump, T>) -> Ordering {
2280        Ord::cmp(&**self, &**other)
2281    }
2282}
2283
2284impl<'bump, T: 'bump + fmt::Debug> fmt::Debug for Vec<'bump, T> {
2285    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
2286        fmt::Debug::fmt(&**self, f)
2287    }
2288}
2289
2290impl<'bump, T: 'bump> AsRef<Vec<'bump, T>> for Vec<'bump, T> {
2291    fn as_ref(&self) -> &Vec<'bump, T> {
2292        self
2293    }
2294}
2295
2296impl<'bump, T: 'bump> AsMut<Vec<'bump, T>> for Vec<'bump, T> {
2297    fn as_mut(&mut self) -> &mut Vec<'bump, T> {
2298        self
2299    }
2300}
2301
2302impl<'bump, T: 'bump> AsRef<[T]> for Vec<'bump, T> {
2303    fn as_ref(&self) -> &[T] {
2304        self
2305    }
2306}
2307
2308impl<'bump, T: 'bump> AsMut<[T]> for Vec<'bump, T> {
2309    fn as_mut(&mut self) -> &mut [T] {
2310        self
2311    }
2312}
2313
2314#[cfg(feature = "boxed")]
2315impl<'bump, T: 'bump> From<Vec<'bump, T>> for crate::boxed::Box<'bump, [T]> {
2316    fn from(v: Vec<'bump, T>) -> crate::boxed::Box<'bump, [T]> {
2317        v.into_boxed_slice()
2318    }
2319}
2320
2321impl<'bump, T: 'bump> Borrow<[T]> for Vec<'bump, T> {
2322    #[inline]
2323    fn borrow(&self) -> &[T] {
2324        &self[..]
2325    }
2326}
2327
2328impl<'bump, T: 'bump> BorrowMut<[T]> for Vec<'bump, T> {
2329    #[inline]
2330    fn borrow_mut(&mut self) -> &mut [T] {
2331        &mut self[..]
2332    }
2333}
2334
2335impl<'bump, T> Drop for Vec<'bump, T> {
2336    fn drop(&mut self) {
2337        unsafe {
2338            // use drop for [T]
2339            // use a raw slice to refer to the elements of the vector as weakest necessary type;
2340            // could avoid questions of validity in certain cases
2341            ptr::drop_in_place(ptr::slice_from_raw_parts_mut(self.as_mut_ptr(), self.len))
2342        }
2343        // RawVec handles deallocation
2344    }
2345}
2346
2347////////////////////////////////////////////////////////////////////////////////
2348// Clone-on-write
2349////////////////////////////////////////////////////////////////////////////////
2350
2351// impl<'a, 'bump, T: Clone> From<Vec<'bump, T>> for Cow<'a, [T]> {
2352//     fn from(v: Vec<'bump, T>) -> Cow<'a, [T]> {
2353//         Cow::Owned(v)
2354//     }
2355// }
2356
2357// impl<'a, 'bump, T: Clone> From<&'a Vec<'bump, T>> for Cow<'a, [T]> {
2358//     fn from(v: &'a Vec<'bump, T>) -> Cow<'a, [T]> {
2359//         Cow::Borrowed(v.as_slice())
2360//     }
2361// }
2362
2363////////////////////////////////////////////////////////////////////////////////
2364// Iterators
2365////////////////////////////////////////////////////////////////////////////////
2366
2367/// An iterator that moves out of a vector.
2368///
2369/// This `struct` is created by the [`Vec::into_iter`] method
2370/// (provided by the [`IntoIterator`] trait).
2371///
2372/// [`IntoIterator`]: https://doc.rust-lang.org/std/iter/trait.IntoIterator.html
2373pub struct IntoIter<'bump, T> {
2374    phantom: PhantomData<&'bump [T]>,
2375    ptr: *const T,
2376    end: *const T,
2377}
2378
2379impl<'bump, T: fmt::Debug> fmt::Debug for IntoIter<'bump, T> {
2380    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
2381        f.debug_tuple("IntoIter").field(&self.as_slice()).finish()
2382    }
2383}
2384
2385impl<'bump, T: 'bump> IntoIter<'bump, T> {
2386    /// Returns the remaining items of this iterator as a slice.
2387    ///
2388    /// # Examples
2389    ///
2390    /// ```
2391    /// use bumpalo::{Bump, collections::Vec};
2392    ///
2393    /// let b = Bump::new();
2394    ///
2395    /// let vec = bumpalo::vec![in &b; 'a', 'b', 'c'];
2396    /// let mut into_iter = vec.into_iter();
2397    /// assert_eq!(into_iter.as_slice(), &['a', 'b', 'c']);
2398    /// let _ = into_iter.next().unwrap();
2399    /// assert_eq!(into_iter.as_slice(), &['b', 'c']);
2400    /// ```
2401    pub fn as_slice(&self) -> &[T] {
2402        unsafe { slice::from_raw_parts(self.ptr, self.len()) }
2403    }
2404
2405    /// Returns the remaining items of this iterator as a mutable slice.
2406    ///
2407    /// # Examples
2408    ///
2409    /// ```
2410    /// use bumpalo::{Bump, collections::Vec};
2411    ///
2412    /// let b = Bump::new();
2413    ///
2414    /// let vec = bumpalo::vec![in &b; 'a', 'b', 'c'];
2415    /// let mut into_iter = vec.into_iter();
2416    /// assert_eq!(into_iter.as_slice(), &['a', 'b', 'c']);
2417    /// into_iter.as_mut_slice()[2] = 'z';
2418    /// assert_eq!(into_iter.next().unwrap(), 'a');
2419    /// assert_eq!(into_iter.next().unwrap(), 'b');
2420    /// assert_eq!(into_iter.next().unwrap(), 'z');
2421    /// ```
2422    pub fn as_mut_slice(&mut self) -> &mut [T] {
2423        unsafe { slice::from_raw_parts_mut(self.ptr as *mut T, self.len()) }
2424    }
2425}
2426
2427unsafe impl<'bump, T: Send> Send for IntoIter<'bump, T> {}
2428unsafe impl<'bump, T: Sync> Sync for IntoIter<'bump, T> {}
2429
2430impl<'bump, T: 'bump> Iterator for IntoIter<'bump, T> {
2431    type Item = T;
2432
2433    #[inline]
2434    fn next(&mut self) -> Option<T> {
2435        unsafe {
2436            if self.ptr as *const _ == self.end {
2437                None
2438            } else if mem::size_of::<T>() == 0 {
2439                // purposefully don't use 'ptr.offset' because for
2440                // vectors with 0-size elements this would return the
2441                // same pointer.
2442                self.ptr = arith_offset(self.ptr as *const i8, 1) as *mut T;
2443
2444                // Make up a value of this ZST.
2445                Some(mem::zeroed())
2446            } else {
2447                let old = self.ptr;
2448                self.ptr = self.ptr.offset(1);
2449
2450                Some(ptr::read(old))
2451            }
2452        }
2453    }
2454
2455    #[inline]
2456    fn size_hint(&self) -> (usize, Option<usize>) {
2457        let exact = if mem::size_of::<T>() == 0 {
2458            (self.end as usize).wrapping_sub(self.ptr as usize)
2459        } else {
2460            unsafe { offset_from(self.end, self.ptr) as usize }
2461        };
2462        (exact, Some(exact))
2463    }
2464
2465    #[inline]
2466    fn count(self) -> usize {
2467        self.len()
2468    }
2469}
2470
2471impl<'bump, T: 'bump> DoubleEndedIterator for IntoIter<'bump, T> {
2472    #[inline]
2473    fn next_back(&mut self) -> Option<T> {
2474        unsafe {
2475            if self.end == self.ptr {
2476                None
2477            } else if mem::size_of::<T>() == 0 {
2478                // See above for why 'ptr.offset' isn't used
2479                self.end = arith_offset(self.end as *const i8, -1) as *mut T;
2480
2481                // Make up a value of this ZST.
2482                Some(mem::zeroed())
2483            } else {
2484                self.end = self.end.offset(-1);
2485
2486                Some(ptr::read(self.end))
2487            }
2488        }
2489    }
2490}
2491
2492impl<'bump, T: 'bump> ExactSizeIterator for IntoIter<'bump, T> {}
2493
2494impl<'bump, T: 'bump> FusedIterator for IntoIter<'bump, T> {}
2495
2496impl<'bump, T> Drop for IntoIter<'bump, T> {
2497    fn drop(&mut self) {
2498        // drop all remaining elements
2499        self.for_each(drop);
2500    }
2501}
2502
2503/// A draining iterator for `Vec<'bump, T>`.
2504///
2505/// This `struct` is created by the [`Vec::drain`] method.
2506pub struct Drain<'a, 'bump, T: 'a + 'bump> {
2507    /// Index of tail to preserve
2508    tail_start: usize,
2509    /// Length of tail
2510    tail_len: usize,
2511    /// Current remaining range to remove
2512    iter: slice::Iter<'a, T>,
2513    vec: NonNull<Vec<'bump, T>>,
2514}
2515
2516impl<'a, 'bump, T: 'a + 'bump + fmt::Debug> fmt::Debug for Drain<'a, 'bump, T> {
2517    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
2518        f.debug_tuple("Drain").field(&self.iter.as_slice()).finish()
2519    }
2520}
2521
2522unsafe impl<'a, 'bump, T: Sync> Sync for Drain<'a, 'bump, T> {}
2523unsafe impl<'a, 'bump, T: Send> Send for Drain<'a, 'bump, T> {}
2524
2525impl<'a, 'bump, T> Iterator for Drain<'a, 'bump, T> {
2526    type Item = T;
2527
2528    #[inline]
2529    fn next(&mut self) -> Option<T> {
2530        self.iter
2531            .next()
2532            .map(|elt| unsafe { ptr::read(elt as *const _) })
2533    }
2534
2535    fn size_hint(&self) -> (usize, Option<usize>) {
2536        self.iter.size_hint()
2537    }
2538}
2539
2540impl<'a, 'bump, T> DoubleEndedIterator for Drain<'a, 'bump, T> {
2541    #[inline]
2542    fn next_back(&mut self) -> Option<T> {
2543        self.iter
2544            .next_back()
2545            .map(|elt| unsafe { ptr::read(elt as *const _) })
2546    }
2547}
2548
2549impl<'a, 'bump, T> Drop for Drain<'a, 'bump, T> {
2550    fn drop(&mut self) {
2551        // exhaust self first
2552        self.for_each(drop);
2553
2554        if self.tail_len > 0 {
2555            unsafe {
2556                let source_vec = self.vec.as_mut();
2557                // memmove back untouched tail, update to new length
2558                let start = source_vec.len();
2559                let tail = self.tail_start;
2560                if tail != start {
2561                    let src = source_vec.as_ptr().add(tail);
2562                    let dst = source_vec.as_mut_ptr().add(start);
2563                    ptr::copy(src, dst, self.tail_len);
2564                }
2565                source_vec.set_len(start + self.tail_len);
2566            }
2567        }
2568    }
2569}
2570
2571impl<'a, 'bump, T> ExactSizeIterator for Drain<'a, 'bump, T> {}
2572
2573impl<'a, 'bump, T> FusedIterator for Drain<'a, 'bump, T> {}
2574
2575/// A splicing iterator for `Vec`.
2576///
2577/// This struct is created by the [`Vec::splice`] method. See its
2578/// documentation for more information.
2579#[derive(Debug)]
2580pub struct Splice<'a, 'bump, I: Iterator + 'a + 'bump> {
2581    drain: Drain<'a, 'bump, I::Item>,
2582    replace_with: I,
2583}
2584
2585impl<'a, 'bump, I: Iterator> Iterator for Splice<'a, 'bump, I> {
2586    type Item = I::Item;
2587
2588    fn next(&mut self) -> Option<Self::Item> {
2589        self.drain.next()
2590    }
2591
2592    fn size_hint(&self) -> (usize, Option<usize>) {
2593        self.drain.size_hint()
2594    }
2595}
2596
2597impl<'a, 'bump, I: Iterator> DoubleEndedIterator for Splice<'a, 'bump, I> {
2598    fn next_back(&mut self) -> Option<Self::Item> {
2599        self.drain.next_back()
2600    }
2601}
2602
2603impl<'a, 'bump, I: Iterator> ExactSizeIterator for Splice<'a, 'bump, I> {}
2604
2605impl<'a, 'bump, I: Iterator> Drop for Splice<'a, 'bump, I> {
2606    fn drop(&mut self) {
2607        self.drain.by_ref().for_each(drop);
2608
2609        unsafe {
2610            if self.drain.tail_len == 0 {
2611                self.drain.vec.as_mut().extend(self.replace_with.by_ref());
2612                return;
2613            }
2614
2615            // First fill the range left by drain().
2616            if !self.drain.fill(&mut self.replace_with) {
2617                return;
2618            }
2619
2620            // There may be more elements. Use the lower bound as an estimate.
2621            // FIXME: Is the upper bound a better guess? Or something else?
2622            let (lower_bound, _upper_bound) = self.replace_with.size_hint();
2623            if lower_bound > 0 {
2624                self.drain.move_tail(lower_bound);
2625                if !self.drain.fill(&mut self.replace_with) {
2626                    return;
2627                }
2628            }
2629
2630            // Collect any remaining elements.
2631            // This is a zero-length vector which does not allocate if `lower_bound` was exact.
2632            let mut collected = Vec::new_in(self.drain.vec.as_ref().buf.bump());
2633            collected.extend(self.replace_with.by_ref());
2634            let mut collected = collected.into_iter();
2635            // Now we have an exact count.
2636            if collected.len() > 0 {
2637                self.drain.move_tail(collected.len());
2638                let filled = self.drain.fill(&mut collected);
2639                debug_assert!(filled);
2640                debug_assert_eq!(collected.len(), 0);
2641            }
2642        }
2643        // Let `Drain::drop` move the tail back if necessary and restore `vec.len`.
2644    }
2645}
2646
2647/// Private helper methods for `Splice::drop`
2648impl<'a, 'bump, T> Drain<'a, 'bump, T> {
2649    /// The range from `self.vec.len` to `self.tail_start` contains elements
2650    /// that have been moved out.
2651    /// Fill that range as much as possible with new elements from the `replace_with` iterator.
2652    /// Return whether we filled the entire range. (`replace_with.next()` didn’t return `None`.)
2653    unsafe fn fill<I: Iterator<Item = T>>(&mut self, replace_with: &mut I) -> bool {
2654        let vec = self.vec.as_mut();
2655        let range_start = vec.len;
2656        let range_end = self.tail_start;
2657        let range_slice =
2658            slice::from_raw_parts_mut(vec.as_mut_ptr().add(range_start), range_end - range_start);
2659
2660        for place in range_slice {
2661            if let Some(new_item) = replace_with.next() {
2662                ptr::write(place, new_item);
2663                vec.len += 1;
2664            } else {
2665                return false;
2666            }
2667        }
2668        true
2669    }
2670
2671    /// Make room for inserting more elements before the tail.
2672    unsafe fn move_tail(&mut self, extra_capacity: usize) {
2673        let vec = self.vec.as_mut();
2674        let used_capacity = self.tail_start + self.tail_len;
2675        vec.buf.reserve(used_capacity, extra_capacity);
2676
2677        let new_tail_start = self.tail_start + extra_capacity;
2678        let src = vec.as_ptr().add(self.tail_start);
2679        let dst = vec.as_mut_ptr().add(new_tail_start);
2680        ptr::copy(src, dst, self.tail_len);
2681        self.tail_start = new_tail_start;
2682    }
2683}
2684
2685/// An iterator produced by calling [`Vec::drain_filter`].
2686#[derive(Debug)]
2687pub struct DrainFilter<'a, 'bump: 'a, T: 'a + 'bump, F>
2688where
2689    F: FnMut(&mut T) -> bool,
2690{
2691    vec: &'a mut Vec<'bump, T>,
2692    idx: usize,
2693    del: usize,
2694    old_len: usize,
2695    pred: F,
2696}
2697
2698impl<'a, 'bump, T, F> Iterator for DrainFilter<'a, 'bump, T, F>
2699where
2700    F: FnMut(&mut T) -> bool,
2701{
2702    type Item = T;
2703
2704    fn next(&mut self) -> Option<T> {
2705        unsafe {
2706            while self.idx != self.old_len {
2707                let i = self.idx;
2708                self.idx += 1;
2709                let v = slice::from_raw_parts_mut(self.vec.as_mut_ptr(), self.old_len);
2710                if (self.pred)(&mut v[i]) {
2711                    self.del += 1;
2712                    return Some(ptr::read(&v[i]));
2713                } else if self.del > 0 {
2714                    let del = self.del;
2715                    let src: *const T = &v[i];
2716                    let dst: *mut T = &mut v[i - del];
2717                    // This is safe because self.vec has length 0
2718                    // thus its elements will not have Drop::drop
2719                    // called on them in the event of a panic.
2720                    ptr::copy_nonoverlapping(src, dst, 1);
2721                }
2722            }
2723            None
2724        }
2725    }
2726
2727    fn size_hint(&self) -> (usize, Option<usize>) {
2728        (0, Some(self.old_len - self.idx))
2729    }
2730}
2731
2732impl<'a, 'bump, T, F> Drop for DrainFilter<'a, 'bump, T, F>
2733where
2734    F: FnMut(&mut T) -> bool,
2735{
2736    fn drop(&mut self) {
2737        self.for_each(drop);
2738        unsafe {
2739            self.vec.set_len(self.old_len - self.del);
2740        }
2741    }
2742}
2743
2744#[cfg(feature = "std")]
2745impl<'bump> io::Write for Vec<'bump, u8> {
2746    #[inline]
2747    fn write(&mut self, buf: &[u8]) -> io::Result<usize> {
2748        self.extend_from_slice_copy(buf);
2749        Ok(buf.len())
2750    }
2751
2752    #[inline]
2753    fn write_all(&mut self, buf: &[u8]) -> io::Result<()> {
2754        self.extend_from_slice_copy(buf);
2755        Ok(())
2756    }
2757
2758    #[inline]
2759    fn flush(&mut self) -> io::Result<()> {
2760        Ok(())
2761    }
2762}
2763
2764#[cfg(feature = "serde")]
2765mod serialize {
2766    use super::*;
2767
2768    use serde::{ser::SerializeSeq, Serialize, Serializer};
2769
2770    impl<'a, T> Serialize for Vec<'a, T>
2771    where
2772        T: Serialize,
2773    {
2774        fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
2775        where
2776            S: Serializer,
2777        {
2778            let mut seq = serializer.serialize_seq(Some(self.len))?;
2779            for e in self.iter() {
2780                seq.serialize_element(e)?;
2781            }
2782            seq.end()
2783        }
2784    }
2785
2786}