heapless/
vec.rs

1use core::{cmp::Ordering, fmt, hash, iter::FromIterator, mem::MaybeUninit, ops, ptr, slice};
2
3/// A fixed capacity [`Vec`](https://doc.rust-lang.org/std/vec/struct.Vec.html)
4///
5/// # Examples
6///
7/// ```
8/// use heapless::Vec;
9///
10///
11/// // A vector with a fixed capacity of 8 elements allocated on the stack
12/// let mut vec = Vec::<_, 8>::new();
13/// vec.push(1);
14/// vec.push(2);
15///
16/// assert_eq!(vec.len(), 2);
17/// assert_eq!(vec[0], 1);
18///
19/// assert_eq!(vec.pop(), Some(2));
20/// assert_eq!(vec.len(), 1);
21///
22/// vec[0] = 7;
23/// assert_eq!(vec[0], 7);
24///
25/// vec.extend([1, 2, 3].iter().cloned());
26///
27/// for x in &vec {
28///     println!("{}", x);
29/// }
30/// assert_eq!(*vec, [7, 1, 2, 3]);
31/// ```
32pub struct Vec<T, const N: usize> {
33    // NOTE order is important for optimizations. the `len` first layout lets the compiler optimize
34    // `new` to: reserve stack space and zero the first word. With the fields in the reverse order
35    // the compiler optimizes `new` to `memclr`-ing the *entire* stack space, including the `buffer`
36    // field which should be left uninitialized. Optimizations were last checked with Rust 1.60
37    len: usize,
38
39    buffer: [MaybeUninit<T>; N],
40}
41
42impl<T, const N: usize> Vec<T, N> {
43    const ELEM: MaybeUninit<T> = MaybeUninit::uninit();
44    const INIT: [MaybeUninit<T>; N] = [Self::ELEM; N]; // important for optimization of `new`
45
46    /// Constructs a new, empty vector with a fixed capacity of `N`
47    ///
48    /// # Examples
49    ///
50    /// ```
51    /// use heapless::Vec;
52    ///
53    /// // allocate the vector on the stack
54    /// let mut x: Vec<u8, 16> = Vec::new();
55    ///
56    /// // allocate the vector in a static variable
57    /// static mut X: Vec<u8, 16> = Vec::new();
58    /// ```
59    /// `Vec` `const` constructor; wrap the returned value in [`Vec`].
60    pub const fn new() -> Self {
61        Self {
62            len: 0,
63            buffer: Self::INIT,
64        }
65    }
66
67    /// Constructs a new vector with a fixed capacity of `N` and fills it
68    /// with the provided slice.
69    ///
70    /// This is equivalent to the following code:
71    ///
72    /// ```
73    /// use heapless::Vec;
74    ///
75    /// let mut v: Vec<u8, 16> = Vec::new();
76    /// v.extend_from_slice(&[1, 2, 3]).unwrap();
77    /// ```
78    #[inline]
79    pub fn from_slice(other: &[T]) -> Result<Self, ()>
80    where
81        T: Clone,
82    {
83        let mut v = Vec::new();
84        v.extend_from_slice(other)?;
85        Ok(v)
86    }
87
88    /// Clones a vec into a new vec
89    pub(crate) fn clone(&self) -> Self
90    where
91        T: Clone,
92    {
93        let mut new = Self::new();
94        // avoid `extend_from_slice` as that introduces a runtime check / panicking branch
95        for elem in self {
96            unsafe {
97                new.push_unchecked(elem.clone());
98            }
99        }
100        new
101    }
102
103    /// Returns a raw pointer to the vector’s buffer.
104    pub fn as_ptr(&self) -> *const T {
105        self.buffer.as_ptr() as *const T
106    }
107
108    /// Returns a raw pointer to the vector’s buffer, which may be mutated through.
109    pub fn as_mut_ptr(&mut self) -> *mut T {
110        self.buffer.as_mut_ptr() as *mut T
111    }
112
113    /// Extracts a slice containing the entire vector.
114    ///
115    /// Equivalent to `&s[..]`.
116    ///
117    /// # Examples
118    ///
119    /// ```
120    /// use heapless::Vec;
121    /// let buffer: Vec<u8, 5> = Vec::from_slice(&[1, 2, 3, 5, 8]).unwrap();
122    /// assert_eq!(buffer.as_slice(), &[1, 2, 3, 5, 8]);
123    /// ```
124    pub fn as_slice(&self) -> &[T] {
125        // NOTE(unsafe) avoid bound checks in the slicing operation
126        // &buffer[..self.len]
127        unsafe { slice::from_raw_parts(self.buffer.as_ptr() as *const T, self.len) }
128    }
129
130    /// Returns the contents of the vector as an array of length `M` if the length
131    /// of the vector is exactly `M`, otherwise returns `Err(self)`.
132    ///
133    /// # Examples
134    ///
135    /// ```
136    /// use heapless::Vec;
137    /// let buffer: Vec<u8, 42> = Vec::from_slice(&[1, 2, 3, 5, 8]).unwrap();
138    /// let array: [u8; 5] = buffer.into_array().unwrap();
139    /// assert_eq!(array, [1, 2, 3, 5, 8]);
140    /// ```
141    pub fn into_array<const M: usize>(self) -> Result<[T; M], Self> {
142        if self.len() == M {
143            // This is how the unstable `MaybeUninit::array_assume_init` method does it
144            let array = unsafe { (&self.buffer as *const _ as *const [T; M]).read() };
145
146            // We don't want `self`'s destructor to be called because that would drop all the
147            // items in the array
148            core::mem::forget(self);
149
150            Ok(array)
151        } else {
152            Err(self)
153        }
154    }
155
156    /// Extracts a mutable slice containing the entire vector.
157    ///
158    /// Equivalent to `&mut s[..]`.
159    ///
160    /// # Examples
161    ///
162    /// ```
163    /// use heapless::Vec;
164    /// let mut buffer: Vec<u8, 5> = Vec::from_slice(&[1, 2, 3, 5, 8]).unwrap();
165    /// buffer[0] = 9;
166    /// assert_eq!(buffer.as_slice(), &[9, 2, 3, 5, 8]);
167    /// ```
168    pub fn as_mut_slice(&mut self) -> &mut [T] {
169        // NOTE(unsafe) avoid bound checks in the slicing operation
170        // &mut buffer[..self.len]
171        unsafe { slice::from_raw_parts_mut(self.buffer.as_mut_ptr() as *mut T, self.len) }
172    }
173
174    /// Returns the maximum number of elements the vector can hold.
175    pub const fn capacity(&self) -> usize {
176        N
177    }
178
179    /// Clears the vector, removing all values.
180    pub fn clear(&mut self) {
181        self.truncate(0);
182    }
183
184    /// Extends the vec from an iterator.
185    ///
186    /// # Panic
187    ///
188    /// Panics if the vec cannot hold all elements of the iterator.
189    pub fn extend<I>(&mut self, iter: I)
190    where
191        I: IntoIterator<Item = T>,
192    {
193        for elem in iter {
194            self.push(elem).ok().unwrap()
195        }
196    }
197
198    /// Clones and appends all elements in a slice to the `Vec`.
199    ///
200    /// Iterates over the slice `other`, clones each element, and then appends
201    /// it to this `Vec`. The `other` vector is traversed in-order.
202    ///
203    /// # Examples
204    ///
205    /// ```
206    /// use heapless::Vec;
207    ///
208    /// let mut vec = Vec::<u8, 8>::new();
209    /// vec.push(1).unwrap();
210    /// vec.extend_from_slice(&[2, 3, 4]).unwrap();
211    /// assert_eq!(*vec, [1, 2, 3, 4]);
212    /// ```
213    pub fn extend_from_slice(&mut self, other: &[T]) -> Result<(), ()>
214    where
215        T: Clone,
216    {
217        if self.len + other.len() > self.capacity() {
218            // won't fit in the `Vec`; don't modify anything and return an error
219            Err(())
220        } else {
221            for elem in other {
222                unsafe {
223                    self.push_unchecked(elem.clone());
224                }
225            }
226            Ok(())
227        }
228    }
229
230    /// Removes the last element from a vector and returns it, or `None` if it's empty
231    pub fn pop(&mut self) -> Option<T> {
232        if self.len != 0 {
233            Some(unsafe { self.pop_unchecked() })
234        } else {
235            None
236        }
237    }
238
239    /// Appends an `item` to the back of the collection
240    ///
241    /// Returns back the `item` if the vector is full
242    pub fn push(&mut self, item: T) -> Result<(), T> {
243        if self.len < self.capacity() {
244            unsafe { self.push_unchecked(item) }
245            Ok(())
246        } else {
247            Err(item)
248        }
249    }
250
251    /// Removes the last element from a vector and returns it
252    ///
253    /// # Safety
254    ///
255    /// This assumes the vec to have at least one element.
256    pub unsafe fn pop_unchecked(&mut self) -> T {
257        debug_assert!(!self.is_empty());
258
259        self.len -= 1;
260        (self.buffer.get_unchecked_mut(self.len).as_ptr() as *const T).read()
261    }
262
263    /// Appends an `item` to the back of the collection
264    ///
265    /// # Safety
266    ///
267    /// This assumes the vec is not full.
268    pub unsafe fn push_unchecked(&mut self, item: T) {
269        // NOTE(ptr::write) the memory slot that we are about to write to is uninitialized. We
270        // use `ptr::write` to avoid running `T`'s destructor on the uninitialized memory
271        debug_assert!(!self.is_full());
272
273        *self.buffer.get_unchecked_mut(self.len) = MaybeUninit::new(item);
274
275        self.len += 1;
276    }
277
278    /// Shortens the vector, keeping the first `len` elements and dropping the rest.
279    pub fn truncate(&mut self, len: usize) {
280        // This is safe because:
281        //
282        // * the slice passed to `drop_in_place` is valid; the `len > self.len`
283        //   case avoids creating an invalid slice, and
284        // * the `len` of the vector is shrunk before calling `drop_in_place`,
285        //   such that no value will be dropped twice in case `drop_in_place`
286        //   were to panic once (if it panics twice, the program aborts).
287        unsafe {
288            // Note: It's intentional that this is `>` and not `>=`.
289            //       Changing it to `>=` has negative performance
290            //       implications in some cases. See rust-lang/rust#78884 for more.
291            if len > self.len {
292                return;
293            }
294            let remaining_len = self.len - len;
295            let s = ptr::slice_from_raw_parts_mut(self.as_mut_ptr().add(len), remaining_len);
296            self.len = len;
297            ptr::drop_in_place(s);
298        }
299    }
300
301    /// Resizes the Vec in-place so that len is equal to new_len.
302    ///
303    /// If new_len is greater than len, the Vec is extended by the
304    /// difference, with each additional slot filled with value. If
305    /// new_len is less than len, the Vec is simply truncated.
306    ///
307    /// See also [`resize_default`](Self::resize_default).
308    pub fn resize(&mut self, new_len: usize, value: T) -> Result<(), ()>
309    where
310        T: Clone,
311    {
312        if new_len > self.capacity() {
313            return Err(());
314        }
315
316        if new_len > self.len {
317            while self.len < new_len {
318                self.push(value.clone()).ok();
319            }
320        } else {
321            self.truncate(new_len);
322        }
323
324        Ok(())
325    }
326
327    /// Resizes the `Vec` in-place so that `len` is equal to `new_len`.
328    ///
329    /// If `new_len` is greater than `len`, the `Vec` is extended by the
330    /// difference, with each additional slot filled with `Default::default()`.
331    /// If `new_len` is less than `len`, the `Vec` is simply truncated.
332    ///
333    /// See also [`resize`](Self::resize).
334    pub fn resize_default(&mut self, new_len: usize) -> Result<(), ()>
335    where
336        T: Clone + Default,
337    {
338        self.resize(new_len, T::default())
339    }
340
341    /// Forces the length of the vector to `new_len`.
342    ///
343    /// This is a low-level operation that maintains none of the normal
344    /// invariants of the type. Normally changing the length of a vector
345    /// is done using one of the safe operations instead, such as
346    /// [`truncate`], [`resize`], [`extend`], or [`clear`].
347    ///
348    /// [`truncate`]: Self::truncate
349    /// [`resize`]: Self::resize
350    /// [`extend`]: core::iter::Extend
351    /// [`clear`]: Self::clear
352    ///
353    /// # Safety
354    ///
355    /// - `new_len` must be less than or equal to [`capacity()`].
356    /// - The elements at `old_len..new_len` must be initialized.
357    ///
358    /// [`capacity()`]: Self::capacity
359    ///
360    /// # Examples
361    ///
362    /// This method can be useful for situations in which the vector
363    /// is serving as a buffer for other code, particularly over FFI:
364    ///
365    /// ```no_run
366    /// # #![allow(dead_code)]
367    /// use heapless::Vec;
368    ///
369    /// # // This is just a minimal skeleton for the doc example;
370    /// # // don't use this as a starting point for a real library.
371    /// # pub struct StreamWrapper { strm: *mut core::ffi::c_void }
372    /// # const Z_OK: i32 = 0;
373    /// # extern "C" {
374    /// #     fn deflateGetDictionary(
375    /// #         strm: *mut core::ffi::c_void,
376    /// #         dictionary: *mut u8,
377    /// #         dictLength: *mut usize,
378    /// #     ) -> i32;
379    /// # }
380    /// # impl StreamWrapper {
381    /// pub fn get_dictionary(&self) -> Option<Vec<u8, 32768>> {
382    ///     // Per the FFI method's docs, "32768 bytes is always enough".
383    ///     let mut dict = Vec::new();
384    ///     let mut dict_length = 0;
385    ///     // SAFETY: When `deflateGetDictionary` returns `Z_OK`, it holds that:
386    ///     // 1. `dict_length` elements were initialized.
387    ///     // 2. `dict_length` <= the capacity (32_768)
388    ///     // which makes `set_len` safe to call.
389    ///     unsafe {
390    ///         // Make the FFI call...
391    ///         let r = deflateGetDictionary(self.strm, dict.as_mut_ptr(), &mut dict_length);
392    ///         if r == Z_OK {
393    ///             // ...and update the length to what was initialized.
394    ///             dict.set_len(dict_length);
395    ///             Some(dict)
396    ///         } else {
397    ///             None
398    ///         }
399    ///     }
400    /// }
401    /// # }
402    /// ```
403    ///
404    /// While the following example is sound, there is a memory leak since
405    /// the inner vectors were not freed prior to the `set_len` call:
406    ///
407    /// ```
408    /// use core::iter::FromIterator;
409    /// use heapless::Vec;
410    ///
411    /// let mut vec = Vec::<Vec<u8, 3>, 3>::from_iter(
412    ///     [
413    ///         Vec::from_iter([1, 0, 0].iter().cloned()),
414    ///         Vec::from_iter([0, 1, 0].iter().cloned()),
415    ///         Vec::from_iter([0, 0, 1].iter().cloned()),
416    ///     ]
417    ///     .iter()
418    ///     .cloned()
419    /// );
420    /// // SAFETY:
421    /// // 1. `old_len..0` is empty so no elements need to be initialized.
422    /// // 2. `0 <= capacity` always holds whatever `capacity` is.
423    /// unsafe {
424    ///     vec.set_len(0);
425    /// }
426    /// ```
427    ///
428    /// Normally, here, one would use [`clear`] instead to correctly drop
429    /// the contents and thus not leak memory.
430    pub unsafe fn set_len(&mut self, new_len: usize) {
431        debug_assert!(new_len <= self.capacity());
432
433        self.len = new_len
434    }
435
436    /// Removes an element from the vector and returns it.
437    ///
438    /// The removed element is replaced by the last element of the vector.
439    ///
440    /// This does not preserve ordering, but is O(1).
441    ///
442    /// # Panics
443    ///
444    /// Panics if `index` is out of bounds.
445    ///
446    /// # Examples
447    ///
448    /// ```
449    /// use heapless::Vec;
450    ///// use heapless::consts::*;
451    ///
452    /// let mut v: Vec<_, 8> = Vec::new();
453    /// v.push("foo").unwrap();
454    /// v.push("bar").unwrap();
455    /// v.push("baz").unwrap();
456    /// v.push("qux").unwrap();
457    ///
458    /// assert_eq!(v.swap_remove(1), "bar");
459    /// assert_eq!(&*v, ["foo", "qux", "baz"]);
460    ///
461    /// assert_eq!(v.swap_remove(0), "foo");
462    /// assert_eq!(&*v, ["baz", "qux"]);
463    /// ```
464    pub fn swap_remove(&mut self, index: usize) -> T {
465        assert!(index < self.len);
466        unsafe { self.swap_remove_unchecked(index) }
467    }
468
469    /// Removes an element from the vector and returns it.
470    ///
471    /// The removed element is replaced by the last element of the vector.
472    ///
473    /// This does not preserve ordering, but is O(1).
474    ///
475    /// # Safety
476    ///
477    ///  Assumes `index` within bounds.
478    ///
479    /// # Examples
480    ///
481    /// ```
482    /// use heapless::Vec;
483    ///
484    /// let mut v: Vec<_, 8> = Vec::new();
485    /// v.push("foo").unwrap();
486    /// v.push("bar").unwrap();
487    /// v.push("baz").unwrap();
488    /// v.push("qux").unwrap();
489    ///
490    /// assert_eq!(unsafe { v.swap_remove_unchecked(1) }, "bar");
491    /// assert_eq!(&*v, ["foo", "qux", "baz"]);
492    ///
493    /// assert_eq!(unsafe { v.swap_remove_unchecked(0) }, "foo");
494    /// assert_eq!(&*v, ["baz", "qux"]);
495    /// ```
496    pub unsafe fn swap_remove_unchecked(&mut self, index: usize) -> T {
497        let length = self.len();
498        debug_assert!(index < length);
499        let value = ptr::read(self.as_ptr().add(index));
500        let base_ptr = self.as_mut_ptr();
501        ptr::copy(base_ptr.add(length - 1), base_ptr.add(index), 1);
502        self.len -= 1;
503        value
504    }
505
506    /// Returns true if the vec is full
507    #[inline]
508    pub fn is_full(&self) -> bool {
509        self.len == self.capacity()
510    }
511
512    /// Returns true if the vec is empty
513    #[inline]
514    pub fn is_empty(&self) -> bool {
515        self.len == 0
516    }
517
518    /// Returns `true` if `needle` is a prefix of the Vec.
519    ///
520    /// Always returns `true` if `needle` is an empty slice.
521    ///
522    /// # Examples
523    ///
524    /// ```
525    /// use heapless::Vec;
526    ///
527    /// let v: Vec<_, 8> = Vec::from_slice(b"abc").unwrap();
528    /// assert_eq!(v.starts_with(b""), true);
529    /// assert_eq!(v.starts_with(b"ab"), true);
530    /// assert_eq!(v.starts_with(b"bc"), false);
531    /// ```
532    #[inline]
533    pub fn starts_with(&self, needle: &[T]) -> bool
534    where
535        T: PartialEq,
536    {
537        let n = needle.len();
538        self.len >= n && needle == &self[..n]
539    }
540
541    /// Returns `true` if `needle` is a suffix of the Vec.
542    ///
543    /// Always returns `true` if `needle` is an empty slice.
544    ///
545    /// # Examples
546    ///
547    /// ```
548    /// use heapless::Vec;
549    ///
550    /// let v: Vec<_, 8> = Vec::from_slice(b"abc").unwrap();
551    /// assert_eq!(v.ends_with(b""), true);
552    /// assert_eq!(v.ends_with(b"ab"), false);
553    /// assert_eq!(v.ends_with(b"bc"), true);
554    /// ```
555    #[inline]
556    pub fn ends_with(&self, needle: &[T]) -> bool
557    where
558        T: PartialEq,
559    {
560        let (v, n) = (self.len(), needle.len());
561        v >= n && needle == &self[v - n..]
562    }
563
564    /// Inserts an element at position `index` within the vector, shifting all
565    /// elements after it to the right.
566    ///
567    /// Returns back the `element` if the vector is full.
568    ///
569    /// # Panics
570    ///
571    /// Panics if `index > len`.
572    ///
573    /// # Examples
574    ///
575    /// ```
576    /// use heapless::Vec;
577    ///
578    /// let mut vec: Vec<_, 8> = Vec::from_slice(&[1, 2, 3]).unwrap();
579    /// vec.insert(1, 4);
580    /// assert_eq!(vec, [1, 4, 2, 3]);
581    /// vec.insert(4, 5);
582    /// assert_eq!(vec, [1, 4, 2, 3, 5]);
583    /// ```
584    pub fn insert(&mut self, index: usize, element: T) -> Result<(), T> {
585        let len = self.len();
586        if index > len {
587            panic!(
588                "insertion index (is {}) should be <= len (is {})",
589                index, len
590            );
591        }
592
593        // check there's space for the new element
594        if self.is_full() {
595            return Err(element);
596        }
597
598        unsafe {
599            // infallible
600            // The spot to put the new value
601            {
602                let p = self.as_mut_ptr().add(index);
603                // Shift everything over to make space. (Duplicating the
604                // `index`th element into two consecutive places.)
605                ptr::copy(p, p.offset(1), len - index);
606                // Write it in, overwriting the first copy of the `index`th
607                // element.
608                ptr::write(p, element);
609            }
610            self.set_len(len + 1);
611        }
612
613        Ok(())
614    }
615
616    /// Removes and returns the element at position `index` within the vector,
617    /// shifting all elements after it to the left.
618    ///
619    /// Note: Because this shifts over the remaining elements, it has a
620    /// worst-case performance of *O*(*n*). If you don't need the order of
621    /// elements to be preserved, use [`swap_remove`] instead. If you'd like to
622    /// remove elements from the beginning of the `Vec`, consider using
623    /// [`Deque::pop_front`] instead.
624    ///
625    /// [`swap_remove`]: Vec::swap_remove
626    /// [`Deque::pop_front`]: crate::Deque::pop_front
627    ///
628    /// # Panics
629    ///
630    /// Panics if `index` is out of bounds.
631    ///
632    /// # Examples
633    ///
634    /// ```
635    /// use heapless::Vec;
636    ///
637    /// let mut v: Vec<_, 8> = Vec::from_slice(&[1, 2, 3]).unwrap();
638    /// assert_eq!(v.remove(1), 2);
639    /// assert_eq!(v, [1, 3]);
640    /// ```
641    pub fn remove(&mut self, index: usize) -> T {
642        let len = self.len();
643        if index >= len {
644            panic!("removal index (is {}) should be < len (is {})", index, len);
645        }
646        unsafe {
647            // infallible
648            let ret;
649            {
650                // the place we are taking from.
651                let ptr = self.as_mut_ptr().add(index);
652                // copy it out, unsafely having a copy of the value on
653                // the stack and in the vector at the same time.
654                ret = ptr::read(ptr);
655
656                // Shift everything down to fill in that spot.
657                ptr::copy(ptr.offset(1), ptr, len - index - 1);
658            }
659            self.set_len(len - 1);
660            ret
661        }
662    }
663
664    /// Retains only the elements specified by the predicate.
665    ///
666    /// In other words, remove all elements `e` for which `f(&e)` returns `false`.
667    /// This method operates in place, visiting each element exactly once in the
668    /// original order, and preserves the order of the retained elements.
669    ///
670    /// # Examples
671    ///
672    /// ```
673    /// use heapless::Vec;
674    ///
675    /// let mut vec: Vec<_, 8> = Vec::from_slice(&[1, 2, 3, 4]).unwrap();
676    /// vec.retain(|&x| x % 2 == 0);
677    /// assert_eq!(vec, [2, 4]);
678    /// ```
679    ///
680    /// Because the elements are visited exactly once in the original order,
681    /// external state may be used to decide which elements to keep.
682    ///
683    /// ```
684    /// use heapless::Vec;
685    ///
686    /// let mut vec: Vec<_, 8> = Vec::from_slice(&[1, 2, 3, 4, 5]).unwrap();
687    /// let keep = [false, true, true, false, true];
688    /// let mut iter = keep.iter();
689    /// vec.retain(|_| *iter.next().unwrap());
690    /// assert_eq!(vec, [2, 3, 5]);
691    /// ```
692    pub fn retain<F>(&mut self, mut f: F)
693    where
694        F: FnMut(&T) -> bool,
695    {
696        self.retain_mut(|elem| f(elem));
697    }
698
699    /// Retains only the elements specified by the predicate, passing a mutable reference to it.
700    ///
701    /// In other words, remove all elements `e` such that `f(&mut e)` returns `false`.
702    /// This method operates in place, visiting each element exactly once in the
703    /// original order, and preserves the order of the retained elements.
704    ///
705    /// # Examples
706    ///
707    /// ```
708    /// use heapless::Vec;
709    ///
710    /// let mut vec: Vec<_, 8> = Vec::from_slice(&[1, 2, 3, 4]).unwrap();
711    /// vec.retain_mut(|x| if *x <= 3 {
712    ///     *x += 1;
713    ///     true
714    /// } else {
715    ///     false
716    /// });
717    /// assert_eq!(vec, [2, 3, 4]);
718    /// ```
719    pub fn retain_mut<F>(&mut self, mut f: F)
720    where
721        F: FnMut(&mut T) -> bool,
722    {
723        let original_len = self.len();
724        // Avoid double drop if the drop guard is not executed,
725        // since we may make some holes during the process.
726        unsafe { self.set_len(0) };
727
728        // Vec: [Kept, Kept, Hole, Hole, Hole, Hole, Unchecked, Unchecked]
729        //      |<-              processed len   ->| ^- next to check
730        //                  |<-  deleted cnt     ->|
731        //      |<-              original_len                          ->|
732        // Kept: Elements which predicate returns true on.
733        // Hole: Moved or dropped element slot.
734        // Unchecked: Unchecked valid elements.
735        //
736        // This drop guard will be invoked when predicate or `drop` of element panicked.
737        // It shifts unchecked elements to cover holes and `set_len` to the correct length.
738        // In cases when predicate and `drop` never panick, it will be optimized out.
739        struct BackshiftOnDrop<'a, T, const N: usize> {
740            v: &'a mut Vec<T, N>,
741            processed_len: usize,
742            deleted_cnt: usize,
743            original_len: usize,
744        }
745
746        impl<T, const N: usize> Drop for BackshiftOnDrop<'_, T, N> {
747            fn drop(&mut self) {
748                if self.deleted_cnt > 0 {
749                    // SAFETY: Trailing unchecked items must be valid since we never touch them.
750                    unsafe {
751                        ptr::copy(
752                            self.v.as_ptr().add(self.processed_len),
753                            self.v
754                                .as_mut_ptr()
755                                .add(self.processed_len - self.deleted_cnt),
756                            self.original_len - self.processed_len,
757                        );
758                    }
759                }
760                // SAFETY: After filling holes, all items are in contiguous memory.
761                unsafe {
762                    self.v.set_len(self.original_len - self.deleted_cnt);
763                }
764            }
765        }
766
767        let mut g = BackshiftOnDrop {
768            v: self,
769            processed_len: 0,
770            deleted_cnt: 0,
771            original_len,
772        };
773
774        fn process_loop<F, T, const N: usize, const DELETED: bool>(
775            original_len: usize,
776            f: &mut F,
777            g: &mut BackshiftOnDrop<'_, T, N>,
778        ) where
779            F: FnMut(&mut T) -> bool,
780        {
781            while g.processed_len != original_len {
782                let p = g.v.as_mut_ptr();
783                // SAFETY: Unchecked element must be valid.
784                let cur = unsafe { &mut *p.add(g.processed_len) };
785                if !f(cur) {
786                    // Advance early to avoid double drop if `drop_in_place` panicked.
787                    g.processed_len += 1;
788                    g.deleted_cnt += 1;
789                    // SAFETY: We never touch this element again after dropped.
790                    unsafe { ptr::drop_in_place(cur) };
791                    // We already advanced the counter.
792                    if DELETED {
793                        continue;
794                    } else {
795                        break;
796                    }
797                }
798                if DELETED {
799                    // SAFETY: `deleted_cnt` > 0, so the hole slot must not overlap with current element.
800                    // We use copy for move, and never touch this element again.
801                    unsafe {
802                        let hole_slot = p.add(g.processed_len - g.deleted_cnt);
803                        ptr::copy_nonoverlapping(cur, hole_slot, 1);
804                    }
805                }
806                g.processed_len += 1;
807            }
808        }
809
810        // Stage 1: Nothing was deleted.
811        process_loop::<F, T, N, false>(original_len, &mut f, &mut g);
812
813        // Stage 2: Some elements were deleted.
814        process_loop::<F, T, N, true>(original_len, &mut f, &mut g);
815
816        // All item are processed. This can be optimized to `set_len` by LLVM.
817        drop(g);
818    }
819}
820
821// Trait implementations
822
823impl<T, const N: usize> Default for Vec<T, N> {
824    fn default() -> Self {
825        Self::new()
826    }
827}
828
829impl<T, const N: usize> fmt::Debug for Vec<T, N>
830where
831    T: fmt::Debug,
832{
833    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
834        <[T] as fmt::Debug>::fmt(self, f)
835    }
836}
837
838impl<const N: usize> fmt::Write for Vec<u8, N> {
839    fn write_str(&mut self, s: &str) -> fmt::Result {
840        match self.extend_from_slice(s.as_bytes()) {
841            Ok(()) => Ok(()),
842            Err(_) => Err(fmt::Error),
843        }
844    }
845}
846
847impl<T, const N: usize> Drop for Vec<T, N> {
848    fn drop(&mut self) {
849        // We drop each element used in the vector by turning into a &mut[T]
850        unsafe {
851            ptr::drop_in_place(self.as_mut_slice());
852        }
853    }
854}
855
856impl<'a, T: Clone, const N: usize> TryFrom<&'a [T]> for Vec<T, N> {
857    type Error = ();
858
859    fn try_from(slice: &'a [T]) -> Result<Self, Self::Error> {
860        Vec::from_slice(slice)
861    }
862}
863
864impl<T, const N: usize> Extend<T> for Vec<T, N> {
865    fn extend<I>(&mut self, iter: I)
866    where
867        I: IntoIterator<Item = T>,
868    {
869        self.extend(iter)
870    }
871}
872
873impl<'a, T, const N: usize> Extend<&'a T> for Vec<T, N>
874where
875    T: 'a + Copy,
876{
877    fn extend<I>(&mut self, iter: I)
878    where
879        I: IntoIterator<Item = &'a T>,
880    {
881        self.extend(iter.into_iter().cloned())
882    }
883}
884
885impl<T, const N: usize> hash::Hash for Vec<T, N>
886where
887    T: core::hash::Hash,
888{
889    fn hash<H: hash::Hasher>(&self, state: &mut H) {
890        <[T] as hash::Hash>::hash(self, state)
891    }
892}
893
894impl<'a, T, const N: usize> IntoIterator for &'a Vec<T, N> {
895    type Item = &'a T;
896    type IntoIter = slice::Iter<'a, T>;
897
898    fn into_iter(self) -> Self::IntoIter {
899        self.iter()
900    }
901}
902
903impl<'a, T, const N: usize> IntoIterator for &'a mut Vec<T, N> {
904    type Item = &'a mut T;
905    type IntoIter = slice::IterMut<'a, T>;
906
907    fn into_iter(self) -> Self::IntoIter {
908        self.iter_mut()
909    }
910}
911
912impl<T, const N: usize> FromIterator<T> for Vec<T, N> {
913    fn from_iter<I>(iter: I) -> Self
914    where
915        I: IntoIterator<Item = T>,
916    {
917        let mut vec = Vec::new();
918        for i in iter {
919            vec.push(i).ok().expect("Vec::from_iter overflow");
920        }
921        vec
922    }
923}
924
925/// An iterator that moves out of an [`Vec`][`Vec`].
926///
927/// This struct is created by calling the `into_iter` method on [`Vec`][`Vec`].
928pub struct IntoIter<T, const N: usize> {
929    vec: Vec<T, N>,
930    next: usize,
931}
932
933impl<T, const N: usize> Iterator for IntoIter<T, N> {
934    type Item = T;
935    fn next(&mut self) -> Option<Self::Item> {
936        if self.next < self.vec.len() {
937            let item = unsafe {
938                (self.vec.buffer.get_unchecked_mut(self.next).as_ptr() as *const T).read()
939            };
940            self.next += 1;
941            Some(item)
942        } else {
943            None
944        }
945    }
946}
947
948impl<T, const N: usize> Clone for IntoIter<T, N>
949where
950    T: Clone,
951{
952    fn clone(&self) -> Self {
953        let mut vec = Vec::new();
954
955        if self.next < self.vec.len() {
956            let s = unsafe {
957                slice::from_raw_parts(
958                    (self.vec.buffer.as_ptr() as *const T).add(self.next),
959                    self.vec.len() - self.next,
960                )
961            };
962            vec.extend_from_slice(s).ok();
963        }
964
965        Self { vec, next: 0 }
966    }
967}
968
969impl<T, const N: usize> Drop for IntoIter<T, N> {
970    fn drop(&mut self) {
971        unsafe {
972            // Drop all the elements that have not been moved out of vec
973            ptr::drop_in_place(&mut self.vec.as_mut_slice()[self.next..]);
974            // Prevent dropping of other elements
975            self.vec.len = 0;
976        }
977    }
978}
979
980impl<T, const N: usize> IntoIterator for Vec<T, N> {
981    type Item = T;
982    type IntoIter = IntoIter<T, N>;
983
984    fn into_iter(self) -> Self::IntoIter {
985        IntoIter { vec: self, next: 0 }
986    }
987}
988
989impl<A, B, const N1: usize, const N2: usize> PartialEq<Vec<B, N2>> for Vec<A, N1>
990where
991    A: PartialEq<B>,
992{
993    fn eq(&self, other: &Vec<B, N2>) -> bool {
994        <[A]>::eq(self, &**other)
995    }
996}
997
998// Vec<A, N> == [B]
999impl<A, B, const N: usize> PartialEq<[B]> for Vec<A, N>
1000where
1001    A: PartialEq<B>,
1002{
1003    fn eq(&self, other: &[B]) -> bool {
1004        <[A]>::eq(self, &other[..])
1005    }
1006}
1007
1008// [B] == Vec<A, N>
1009impl<A, B, const N: usize> PartialEq<Vec<A, N>> for [B]
1010where
1011    A: PartialEq<B>,
1012{
1013    fn eq(&self, other: &Vec<A, N>) -> bool {
1014        <[A]>::eq(other, &self[..])
1015    }
1016}
1017
1018// Vec<A, N> == &[B]
1019impl<A, B, const N: usize> PartialEq<&[B]> for Vec<A, N>
1020where
1021    A: PartialEq<B>,
1022{
1023    fn eq(&self, other: &&[B]) -> bool {
1024        <[A]>::eq(self, &other[..])
1025    }
1026}
1027
1028// &[B] == Vec<A, N>
1029impl<A, B, const N: usize> PartialEq<Vec<A, N>> for &[B]
1030where
1031    A: PartialEq<B>,
1032{
1033    fn eq(&self, other: &Vec<A, N>) -> bool {
1034        <[A]>::eq(other, &self[..])
1035    }
1036}
1037
1038// Vec<A, N> == &mut [B]
1039impl<A, B, const N: usize> PartialEq<&mut [B]> for Vec<A, N>
1040where
1041    A: PartialEq<B>,
1042{
1043    fn eq(&self, other: &&mut [B]) -> bool {
1044        <[A]>::eq(self, &other[..])
1045    }
1046}
1047
1048// &mut [B] == Vec<A, N>
1049impl<A, B, const N: usize> PartialEq<Vec<A, N>> for &mut [B]
1050where
1051    A: PartialEq<B>,
1052{
1053    fn eq(&self, other: &Vec<A, N>) -> bool {
1054        <[A]>::eq(other, &self[..])
1055    }
1056}
1057
1058// Vec<A, N> == [B; M]
1059// Equality does not require equal capacity
1060impl<A, B, const N: usize, const M: usize> PartialEq<[B; M]> for Vec<A, N>
1061where
1062    A: PartialEq<B>,
1063{
1064    fn eq(&self, other: &[B; M]) -> bool {
1065        <[A]>::eq(self, &other[..])
1066    }
1067}
1068
1069// [B; M] == Vec<A, N>
1070// Equality does not require equal capacity
1071impl<A, B, const N: usize, const M: usize> PartialEq<Vec<A, N>> for [B; M]
1072where
1073    A: PartialEq<B>,
1074{
1075    fn eq(&self, other: &Vec<A, N>) -> bool {
1076        <[A]>::eq(other, &self[..])
1077    }
1078}
1079
1080// Vec<A, N> == &[B; M]
1081// Equality does not require equal capacity
1082impl<A, B, const N: usize, const M: usize> PartialEq<&[B; M]> for Vec<A, N>
1083where
1084    A: PartialEq<B>,
1085{
1086    fn eq(&self, other: &&[B; M]) -> bool {
1087        <[A]>::eq(self, &other[..])
1088    }
1089}
1090
1091// &[B; M] == Vec<A, N>
1092// Equality does not require equal capacity
1093impl<A, B, const N: usize, const M: usize> PartialEq<Vec<A, N>> for &[B; M]
1094where
1095    A: PartialEq<B>,
1096{
1097    fn eq(&self, other: &Vec<A, N>) -> bool {
1098        <[A]>::eq(other, &self[..])
1099    }
1100}
1101
1102// Implements Eq if underlying data is Eq
1103impl<T, const N: usize> Eq for Vec<T, N> where T: Eq {}
1104
1105impl<T, const N1: usize, const N2: usize> PartialOrd<Vec<T, N2>> for Vec<T, N1>
1106where
1107    T: PartialOrd,
1108{
1109    fn partial_cmp(&self, other: &Vec<T, N2>) -> Option<Ordering> {
1110        PartialOrd::partial_cmp(&**self, &**other)
1111    }
1112}
1113
1114impl<T, const N: usize> Ord for Vec<T, N>
1115where
1116    T: Ord,
1117{
1118    #[inline]
1119    fn cmp(&self, other: &Self) -> Ordering {
1120        Ord::cmp(&**self, &**other)
1121    }
1122}
1123
1124impl<T, const N: usize> ops::Deref for Vec<T, N> {
1125    type Target = [T];
1126
1127    fn deref(&self) -> &[T] {
1128        self.as_slice()
1129    }
1130}
1131
1132impl<T, const N: usize> ops::DerefMut for Vec<T, N> {
1133    fn deref_mut(&mut self) -> &mut [T] {
1134        self.as_mut_slice()
1135    }
1136}
1137
1138impl<T, const N: usize> AsRef<Vec<T, N>> for Vec<T, N> {
1139    #[inline]
1140    fn as_ref(&self) -> &Self {
1141        self
1142    }
1143}
1144
1145impl<T, const N: usize> AsMut<Vec<T, N>> for Vec<T, N> {
1146    #[inline]
1147    fn as_mut(&mut self) -> &mut Self {
1148        self
1149    }
1150}
1151
1152impl<T, const N: usize> AsRef<[T]> for Vec<T, N> {
1153    #[inline]
1154    fn as_ref(&self) -> &[T] {
1155        self
1156    }
1157}
1158
1159impl<T, const N: usize> AsMut<[T]> for Vec<T, N> {
1160    #[inline]
1161    fn as_mut(&mut self) -> &mut [T] {
1162        self
1163    }
1164}
1165
1166impl<T, const N: usize> Clone for Vec<T, N>
1167where
1168    T: Clone,
1169{
1170    fn clone(&self) -> Self {
1171        self.clone()
1172    }
1173}
1174
1175#[cfg(test)]
1176mod tests {
1177    use crate::Vec;
1178    use core::fmt::Write;
1179
1180    #[test]
1181    fn static_new() {
1182        static mut _V: Vec<i32, 4> = Vec::new();
1183    }
1184
1185    #[test]
1186    fn stack_new() {
1187        let mut _v: Vec<i32, 4> = Vec::new();
1188    }
1189
1190    #[test]
1191    fn is_full_empty() {
1192        let mut v: Vec<i32, 4> = Vec::new();
1193
1194        assert!(v.is_empty());
1195        assert!(!v.is_full());
1196
1197        v.push(1).unwrap();
1198        assert!(!v.is_empty());
1199        assert!(!v.is_full());
1200
1201        v.push(1).unwrap();
1202        assert!(!v.is_empty());
1203        assert!(!v.is_full());
1204
1205        v.push(1).unwrap();
1206        assert!(!v.is_empty());
1207        assert!(!v.is_full());
1208
1209        v.push(1).unwrap();
1210        assert!(!v.is_empty());
1211        assert!(v.is_full());
1212    }
1213
1214    #[test]
1215    fn drop() {
1216        droppable!();
1217
1218        {
1219            let mut v: Vec<Droppable, 2> = Vec::new();
1220            v.push(Droppable::new()).ok().unwrap();
1221            v.push(Droppable::new()).ok().unwrap();
1222            v.pop().unwrap();
1223        }
1224
1225        assert_eq!(Droppable::count(), 0);
1226
1227        {
1228            let mut v: Vec<Droppable, 2> = Vec::new();
1229            v.push(Droppable::new()).ok().unwrap();
1230            v.push(Droppable::new()).ok().unwrap();
1231        }
1232
1233        assert_eq!(Droppable::count(), 0);
1234    }
1235
1236    #[test]
1237    fn eq() {
1238        let mut xs: Vec<i32, 4> = Vec::new();
1239        let mut ys: Vec<i32, 8> = Vec::new();
1240
1241        assert_eq!(xs, ys);
1242
1243        xs.push(1).unwrap();
1244        ys.push(1).unwrap();
1245
1246        assert_eq!(xs, ys);
1247    }
1248
1249    #[test]
1250    fn cmp() {
1251        let mut xs: Vec<i32, 4> = Vec::new();
1252        let mut ys: Vec<i32, 4> = Vec::new();
1253
1254        assert_eq!(xs, ys);
1255
1256        xs.push(1).unwrap();
1257        ys.push(2).unwrap();
1258
1259        assert!(xs < ys);
1260    }
1261
1262    #[test]
1263    fn cmp_heterogenous_size() {
1264        let mut xs: Vec<i32, 4> = Vec::new();
1265        let mut ys: Vec<i32, 8> = Vec::new();
1266
1267        assert_eq!(xs, ys);
1268
1269        xs.push(1).unwrap();
1270        ys.push(2).unwrap();
1271
1272        assert!(xs < ys);
1273    }
1274
1275    #[test]
1276    fn cmp_with_arrays_and_slices() {
1277        let mut xs: Vec<i32, 12> = Vec::new();
1278        xs.push(1).unwrap();
1279
1280        let array = [1];
1281
1282        assert_eq!(xs, array);
1283        assert_eq!(array, xs);
1284
1285        assert_eq!(xs, array.as_slice());
1286        assert_eq!(array.as_slice(), xs);
1287
1288        assert_eq!(xs, &array);
1289        assert_eq!(&array, xs);
1290
1291        let longer_array = [1; 20];
1292
1293        assert_ne!(xs, longer_array);
1294        assert_ne!(longer_array, xs);
1295    }
1296
1297    #[test]
1298    fn full() {
1299        let mut v: Vec<i32, 4> = Vec::new();
1300
1301        v.push(0).unwrap();
1302        v.push(1).unwrap();
1303        v.push(2).unwrap();
1304        v.push(3).unwrap();
1305
1306        assert!(v.push(4).is_err());
1307    }
1308
1309    #[test]
1310    fn iter() {
1311        let mut v: Vec<i32, 4> = Vec::new();
1312
1313        v.push(0).unwrap();
1314        v.push(1).unwrap();
1315        v.push(2).unwrap();
1316        v.push(3).unwrap();
1317
1318        let mut items = v.iter();
1319
1320        assert_eq!(items.next(), Some(&0));
1321        assert_eq!(items.next(), Some(&1));
1322        assert_eq!(items.next(), Some(&2));
1323        assert_eq!(items.next(), Some(&3));
1324        assert_eq!(items.next(), None);
1325    }
1326
1327    #[test]
1328    fn iter_mut() {
1329        let mut v: Vec<i32, 4> = Vec::new();
1330
1331        v.push(0).unwrap();
1332        v.push(1).unwrap();
1333        v.push(2).unwrap();
1334        v.push(3).unwrap();
1335
1336        let mut items = v.iter_mut();
1337
1338        assert_eq!(items.next(), Some(&mut 0));
1339        assert_eq!(items.next(), Some(&mut 1));
1340        assert_eq!(items.next(), Some(&mut 2));
1341        assert_eq!(items.next(), Some(&mut 3));
1342        assert_eq!(items.next(), None);
1343    }
1344
1345    #[test]
1346    fn collect_from_iter() {
1347        let slice = &[1, 2, 3];
1348        let vec: Vec<i32, 4> = slice.iter().cloned().collect();
1349        assert_eq!(&vec, slice);
1350    }
1351
1352    #[test]
1353    #[should_panic]
1354    fn collect_from_iter_overfull() {
1355        let slice = &[1, 2, 3];
1356        let _vec = slice.iter().cloned().collect::<Vec<_, 2>>();
1357    }
1358
1359    #[test]
1360    fn iter_move() {
1361        let mut v: Vec<i32, 4> = Vec::new();
1362        v.push(0).unwrap();
1363        v.push(1).unwrap();
1364        v.push(2).unwrap();
1365        v.push(3).unwrap();
1366
1367        let mut items = v.into_iter();
1368
1369        assert_eq!(items.next(), Some(0));
1370        assert_eq!(items.next(), Some(1));
1371        assert_eq!(items.next(), Some(2));
1372        assert_eq!(items.next(), Some(3));
1373        assert_eq!(items.next(), None);
1374    }
1375
1376    #[test]
1377    fn iter_move_drop() {
1378        droppable!();
1379
1380        {
1381            let mut vec: Vec<Droppable, 2> = Vec::new();
1382            vec.push(Droppable::new()).ok().unwrap();
1383            vec.push(Droppable::new()).ok().unwrap();
1384            let mut items = vec.into_iter();
1385            // Move all
1386            let _ = items.next();
1387            let _ = items.next();
1388        }
1389
1390        assert_eq!(Droppable::count(), 0);
1391
1392        {
1393            let mut vec: Vec<Droppable, 2> = Vec::new();
1394            vec.push(Droppable::new()).ok().unwrap();
1395            vec.push(Droppable::new()).ok().unwrap();
1396            let _items = vec.into_iter();
1397            // Move none
1398        }
1399
1400        assert_eq!(Droppable::count(), 0);
1401
1402        {
1403            let mut vec: Vec<Droppable, 2> = Vec::new();
1404            vec.push(Droppable::new()).ok().unwrap();
1405            vec.push(Droppable::new()).ok().unwrap();
1406            let mut items = vec.into_iter();
1407            let _ = items.next(); // Move partly
1408        }
1409
1410        assert_eq!(Droppable::count(), 0);
1411    }
1412
1413    #[test]
1414    fn push_and_pop() {
1415        let mut v: Vec<i32, 4> = Vec::new();
1416        assert_eq!(v.len(), 0);
1417
1418        assert_eq!(v.pop(), None);
1419        assert_eq!(v.len(), 0);
1420
1421        v.push(0).unwrap();
1422        assert_eq!(v.len(), 1);
1423
1424        assert_eq!(v.pop(), Some(0));
1425        assert_eq!(v.len(), 0);
1426
1427        assert_eq!(v.pop(), None);
1428        assert_eq!(v.len(), 0);
1429    }
1430
1431    #[test]
1432    fn resize_size_limit() {
1433        let mut v: Vec<u8, 4> = Vec::new();
1434
1435        v.resize(0, 0).unwrap();
1436        v.resize(4, 0).unwrap();
1437        v.resize(5, 0).err().expect("full");
1438    }
1439
1440    #[test]
1441    fn resize_length_cases() {
1442        let mut v: Vec<u8, 4> = Vec::new();
1443
1444        assert_eq!(v.len(), 0);
1445
1446        // Grow by 1
1447        v.resize(1, 0).unwrap();
1448        assert_eq!(v.len(), 1);
1449
1450        // Grow by 2
1451        v.resize(3, 0).unwrap();
1452        assert_eq!(v.len(), 3);
1453
1454        // Resize to current size
1455        v.resize(3, 0).unwrap();
1456        assert_eq!(v.len(), 3);
1457
1458        // Shrink by 1
1459        v.resize(2, 0).unwrap();
1460        assert_eq!(v.len(), 2);
1461
1462        // Shrink by 2
1463        v.resize(0, 0).unwrap();
1464        assert_eq!(v.len(), 0);
1465    }
1466
1467    #[test]
1468    fn resize_contents() {
1469        let mut v: Vec<u8, 4> = Vec::new();
1470
1471        // New entries take supplied value when growing
1472        v.resize(1, 17).unwrap();
1473        assert_eq!(v[0], 17);
1474
1475        // Old values aren't changed when growing
1476        v.resize(2, 18).unwrap();
1477        assert_eq!(v[0], 17);
1478        assert_eq!(v[1], 18);
1479
1480        // Old values aren't changed when length unchanged
1481        v.resize(2, 0).unwrap();
1482        assert_eq!(v[0], 17);
1483        assert_eq!(v[1], 18);
1484
1485        // Old values aren't changed when shrinking
1486        v.resize(1, 0).unwrap();
1487        assert_eq!(v[0], 17);
1488    }
1489
1490    #[test]
1491    fn resize_default() {
1492        let mut v: Vec<u8, 4> = Vec::new();
1493
1494        // resize_default is implemented using resize, so just check the
1495        // correct value is being written.
1496        v.resize_default(1).unwrap();
1497        assert_eq!(v[0], 0);
1498    }
1499
1500    #[test]
1501    fn write() {
1502        let mut v: Vec<u8, 4> = Vec::new();
1503        write!(v, "{:x}", 1234).unwrap();
1504        assert_eq!(&v[..], b"4d2");
1505    }
1506
1507    #[test]
1508    fn extend_from_slice() {
1509        let mut v: Vec<u8, 4> = Vec::new();
1510        assert_eq!(v.len(), 0);
1511        v.extend_from_slice(&[1, 2]).unwrap();
1512        assert_eq!(v.len(), 2);
1513        assert_eq!(v.as_slice(), &[1, 2]);
1514        v.extend_from_slice(&[3]).unwrap();
1515        assert_eq!(v.len(), 3);
1516        assert_eq!(v.as_slice(), &[1, 2, 3]);
1517        assert!(v.extend_from_slice(&[4, 5]).is_err());
1518        assert_eq!(v.len(), 3);
1519        assert_eq!(v.as_slice(), &[1, 2, 3]);
1520    }
1521
1522    #[test]
1523    fn from_slice() {
1524        // Successful construction
1525        let v: Vec<u8, 4> = Vec::from_slice(&[1, 2, 3]).unwrap();
1526        assert_eq!(v.len(), 3);
1527        assert_eq!(v.as_slice(), &[1, 2, 3]);
1528
1529        // Slice too large
1530        assert!(Vec::<u8, 2>::from_slice(&[1, 2, 3]).is_err());
1531    }
1532
1533    #[test]
1534    fn starts_with() {
1535        let v: Vec<_, 8> = Vec::from_slice(b"ab").unwrap();
1536        assert!(v.starts_with(&[]));
1537        assert!(v.starts_with(b""));
1538        assert!(v.starts_with(b"a"));
1539        assert!(v.starts_with(b"ab"));
1540        assert!(!v.starts_with(b"abc"));
1541        assert!(!v.starts_with(b"ba"));
1542        assert!(!v.starts_with(b"b"));
1543    }
1544
1545    #[test]
1546    fn ends_with() {
1547        let v: Vec<_, 8> = Vec::from_slice(b"ab").unwrap();
1548        assert!(v.ends_with(&[]));
1549        assert!(v.ends_with(b""));
1550        assert!(v.ends_with(b"b"));
1551        assert!(v.ends_with(b"ab"));
1552        assert!(!v.ends_with(b"abc"));
1553        assert!(!v.ends_with(b"ba"));
1554        assert!(!v.ends_with(b"a"));
1555    }
1556
1557    #[test]
1558    fn zero_capacity() {
1559        let mut v: Vec<u8, 0> = Vec::new();
1560        // Validate capacity
1561        assert_eq!(v.capacity(), 0);
1562
1563        // Make sure there is no capacity
1564        assert!(v.push(1).is_err());
1565
1566        // Validate length
1567        assert_eq!(v.len(), 0);
1568
1569        // Validate pop
1570        assert_eq!(v.pop(), None);
1571
1572        // Validate slice
1573        assert_eq!(v.as_slice(), &[]);
1574
1575        // Validate empty
1576        assert!(v.is_empty());
1577
1578        // Validate full
1579        assert!(v.is_full());
1580    }
1581}