1 | use core::mem::ManuallyDrop; |
2 | use core::ptr::{self}; |
3 | |
4 | use super::{IntoIter, SpecExtend, SpecFromIterNested, Vec}; |
5 | |
6 | /// Specialization trait used for Vec::from_iter |
7 | /// |
8 | /// ## The delegation graph: |
9 | /// |
10 | /// ```text |
11 | /// +-------------+ |
12 | /// |FromIterator | |
13 | /// +-+-----------+ |
14 | /// | |
15 | /// v |
16 | /// +-+---------------------------------+ +---------------------+ |
17 | /// |SpecFromIter +---->+SpecFromIterNested | |
18 | /// |where I: | | |where I: | |
19 | /// | Iterator (default)------------+ | | Iterator (default) | |
20 | /// | vec::IntoIter | | | TrustedLen | |
21 | /// | InPlaceCollect--(fallback to)-+ | +---------------------+ |
22 | /// +-----------------------------------+ |
23 | /// ``` |
24 | pub(super) trait SpecFromIter<T, I> { |
25 | fn from_iter(iter: I) -> Self; |
26 | } |
27 | |
28 | impl<T, I> SpecFromIter<T, I> for Vec<T> |
29 | where |
30 | I: Iterator<Item = T>, |
31 | { |
32 | #[track_caller ] |
33 | default fn from_iter(iterator: I) -> Self { |
34 | SpecFromIterNested::from_iter(iterator) |
35 | } |
36 | } |
37 | |
38 | impl<T> SpecFromIter<T, IntoIter<T>> for Vec<T> { |
39 | #[track_caller ] |
40 | fn from_iter(iterator: IntoIter<T>) -> Self { |
41 | // A common case is passing a vector into a function which immediately |
42 | // re-collects into a vector. We can short circuit this if the IntoIter |
43 | // has not been advanced at all. |
44 | // When it has been advanced We can also reuse the memory and move the data to the front. |
45 | // But we only do so when the resulting Vec wouldn't have more unused capacity |
46 | // than creating it through the generic FromIterator implementation would. That limitation |
47 | // is not strictly necessary as Vec's allocation behavior is intentionally unspecified. |
48 | // But it is a conservative choice. |
49 | let has_advanced = iterator.buf != iterator.ptr; |
50 | if !has_advanced || iterator.len() >= iterator.cap / 2 { |
51 | unsafe { |
52 | let it = ManuallyDrop::new(iterator); |
53 | if has_advanced { |
54 | ptr::copy(it.ptr.as_ptr(), it.buf.as_ptr(), it.len()); |
55 | } |
56 | return Vec::from_parts(it.buf, it.len(), it.cap); |
57 | } |
58 | } |
59 | |
60 | let mut vec = Vec::new(); |
61 | // must delegate to spec_extend() since extend() itself delegates |
62 | // to spec_from for empty Vecs |
63 | vec.spec_extend(iterator); |
64 | vec |
65 | } |
66 | } |
67 | |