1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97
use core::mem::ManuallyDrop; use core::ptr::{self}; use core::slice::{self}; use super::{IntoIter, SpecExtend, SpecFromIterNested, Vec}; /// Specialization trait used for Vec::from_iter /// /// ## The delegation graph: /// /// ```text /// +-------------+ /// |FromIterator | /// +-+-----------+ /// | /// v /// +-+-------------------------------+ +---------------------+ /// |SpecFromIter +---->+SpecFromIterNested | /// |where I: | | |where I: | /// | Iterator (default)----------+ | | Iterator (default) | /// | vec::IntoIter | | | TrustedLen | /// | SourceIterMarker---fallback-+ | | | /// | slice::Iter | | | /// | Iterator<Item = &Clone> | +---------------------+ /// +---------------------------------+ /// ``` pub(super) trait SpecFromIter<T, I> { fn from_iter(iter: I) -> Self; } impl<T, I> SpecFromIter<T, I> for Vec<T> where I: Iterator<Item = T>, { default fn from_iter(iterator: I) -> Self { SpecFromIterNested::from_iter(iterator) } } impl<T> SpecFromIter<T, IntoIter<T>> for Vec<T> { fn from_iter(iterator: IntoIter<T>) -> Self { // A common case is passing a vector into a function which immediately // re-collects into a vector. We can short circuit this if the IntoIter // has not been advanced at all. // When it has been advanced We can also reuse the memory and move the data to the front. // But we only do so when the resulting Vec wouldn't have more unused capacity // than creating it through the generic FromIterator implementation would. That limitation // is not strictly necessary as Vec's allocation behavior is intentionally unspecified. // But it is a conservative choice. let has_advanced = iterator.buf.as_ptr() as *const _ != iterator.ptr; if !has_advanced || iterator.len() >= iterator.cap / 2 { unsafe { let it = ManuallyDrop::new(iterator); if has_advanced { ptr::copy(it.ptr, it.buf.as_ptr(), it.len()); } return Vec::from_raw_parts(it.buf.as_ptr(), it.len(), it.cap); } } let mut vec = Vec::new(); // must delegate to spec_extend() since extend() itself delegates // to spec_from for empty Vecs vec.spec_extend(iterator); vec } } impl<'a, T: 'a, I> SpecFromIter<&'a T, I> for Vec<T> where I: Iterator<Item = &'a T>, T: Clone, { default fn from_iter(iterator: I) -> Self { SpecFromIter::from_iter(iterator.cloned()) } } // This utilizes `iterator.as_slice().to_vec()` since spec_extend // must take more steps to reason about the final capacity + length // and thus do more work. `to_vec()` directly allocates the correct amount // and fills it exactly. impl<'a, T: 'a + Clone> SpecFromIter<&'a T, slice::Iter<'a, T>> for Vec<T> { #[cfg(not(test))] fn from_iter(iterator: slice::Iter<'a, T>) -> Self { iterator.as_slice().to_vec() } // HACK(japaric): with cfg(test) the inherent `[T]::to_vec` method, which is // required for this method definition, is not available. Instead use the // `slice::to_vec` function which is only available with cfg(test) // NB see the slice::hack module in slice.rs for more information #[cfg(test)] fn from_iter(iterator: slice::Iter<'a, T>) -> Self { crate::slice::to_vec(iterator.as_slice(), crate::alloc::Global) } }