library/alloc/src/vec/spec_from_iter.rs

   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 /// |  SourceIterMarker---fallback-+  |  +---------------------+
  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.as_ptr() as *const _ != 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, it.buf.as_ptr(), it.len());
  53                 }
  54                 return Vec::from_raw_parts(it.buf.as_ptr(), 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 }