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