#
alloc/collections/vec_deque/
spec_extend.rs

    1use core::iter::TrustedLen;
    2use core::slice;
    3
    4use super::VecDeque;
    5use crate::alloc::Allocator;
    6#[cfg(not(test))]
    7use crate::vec;
    8
    9// Specialization trait used for VecDeque::extend
    10pub(super) trait SpecExtend<T, I> {
    11    #[track_caller]
    12    fn spec_extend(&mut self, iter: I);
    13}
    14
    15impl<T, I, A: Allocator> SpecExtend<T, I> for VecDeque<T, A>
    16where
    17    I: Iterator<Item = T>,
    18{
    19    #[track_caller]
    20    default fn spec_extend(&mut self, mut iter: I) {
    21        // This function should be the moral equivalent of:
    22        //
    23        // for item in iter {
    24        //     self.push_back(item);
    25        // }
    26
    27        while let Some(element) = iter.next() {
    28            let (lower, _) = iter.size_hint();
    29            self.reserve(lower.saturating_add(1));
    30
    31            // SAFETY: We just reserved space for at least one element.
    32            unsafe { self.push_unchecked(element) };
    33
    34            // Inner loop to avoid repeatedly calling `reserve`.
    35            while self.len < self.capacity() {
    36                let Some(element) = iter.next() else {
    37                    return;
    38                };
    39                // SAFETY: The loop condition guarantees that `self.len() < self.capacity()`.
    40                unsafe { self.push_unchecked(element) };
    41            }
    42        }
    43    }
    44}
    45
    46impl<T, I, A: Allocator> SpecExtend<T, I> for VecDeque<T, A>
    47where
    48    I: TrustedLen<Item = T>,
    49{
    50    #[track_caller]
    51    default fn spec_extend(&mut self, iter: I) {
    52        // This is the case for a TrustedLen iterator.
    53        let (low, high) = iter.size_hint();
    54        if let Some(additional) = high {
    55            debug_assert_eq!(
    56                low,
    57                additional,
    58                "TrustedLen iterator's size hint is not exact: {:?}",
    59                (low, high)
    60            );
    61            self.reserve(additional);
    62
    63            let written = unsafe {
    64                self.write_iter_wrapping(self.to_physical_idx(self.len), iter, additional)
    65            };
    66
    67            debug_assert_eq!(
    68                additional, written,
    69                "The number of items written to VecDeque doesn't match the TrustedLen size hint"
    70            );
    71        } else {
    72            // Per TrustedLen contract a `None` upper bound means that the iterator length
    73            // truly exceeds usize::MAX, which would eventually lead to a capacity overflow anyway.
    74            // Since the other branch already panics eagerly (via `reserve()`) we do the same here.
    75            // This avoids additional codegen for a fallback code path which would eventually
    76            // panic anyway.
    77            panic!("capacity overflow");
    78        }
    79    }
    80}
    81
    82#[cfg(not(test))]
    83impl<T, A: Allocator> SpecExtend<T, vec::IntoIter<T>> for VecDeque<T, A> {
    84    #[track_caller]
    85    fn spec_extend(&mut self, mut iterator: vec::IntoIter<T>) {
    86        let slice = iterator.as_slice();
    87        self.reserve(slice.len());
    88
    89        unsafe {
    90            self.copy_slice(self.to_physical_idx(self.len), slice);
    91            self.len += slice.len();
    92        }
    93        iterator.forget_remaining_elements();
    94    }
    95}
    96
    97impl<'a, T: 'a, I, A: Allocator> SpecExtend<&'a T, I> for VecDeque<T, A>
    98where
    99    I: Iterator<Item = &'a T>,
    100    T: Copy,
    101{
    102    #[track_caller]
    103    default fn spec_extend(&mut self, iterator: I) {
    104        self.spec_extend(iterator.copied())
    105    }
    106}
    107
    108impl<'a, T: 'a, A: Allocator> SpecExtend<&'a T, slice::Iter<'a, T>> for VecDeque<T, A>
    109where
    110    T: Copy,
    111{
    112    #[track_caller]
    113    fn spec_extend(&mut self, iterator: slice::Iter<'a, T>) {
    114        let slice = iterator.as_slice();
    115        self.reserve(slice.len());
    116
    117        unsafe {
    118            self.copy_slice(self.to_physical_idx(self.len), slice);
    119            self.len += slice.len();
    120        }
    121    }
    122}