library/alloc/src/vec/spec_from_iter.rs

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