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 | default fn from_iter(iterator: I) -> Self { |
33 | SpecFromIterNested::from_iter(iterator) |
34 | } |
35 | } |
36 | |
37 | impl<T> SpecFromIter<T, IntoIter<T>> for Vec<T> { |
38 | fn from_iter(iterator: IntoIter<T>) -> Self { |
39 | // A common case is passing a vector into a function which immediately |
40 | // re-collects into a vector. We can short circuit this if the IntoIter |
41 | // has not been advanced at all. |
42 | // When it has been advanced We can also reuse the memory and move the data to the front. |
43 | // But we only do so when the resulting Vec wouldn't have more unused capacity |
44 | // than creating it through the generic FromIterator implementation would. That limitation |
45 | // is not strictly necessary as Vec's allocation behavior is intentionally unspecified. |
46 | // But it is a conservative choice. |
47 | let has_advanced = iterator.buf != iterator.ptr; |
48 | if !has_advanced || iterator.len() >= iterator.cap / 2 { |
49 | unsafe { |
50 | let it = ManuallyDrop::new(iterator); |
51 | if has_advanced { |
52 | ptr::copy(it.ptr.as_ptr(), it.buf.as_ptr(), it.len()); |
53 | } |
54 | return Vec::from_nonnull(it.buf, it.len(), it.cap); |
55 | } |
56 | } |
57 | |
58 | let mut vec = Vec::new(); |
59 | // must delegate to spec_extend() since extend() itself delegates |
60 | // to spec_from for empty Vecs |
61 | vec.spec_extend(iterator); |
62 | vec |
63 | } |
64 | } |
65 | |