     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)
        }
    }