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
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156

use core::iter::{InPlaceIterable, SourceIter, TrustedRandomAccessNoCoerce};
use core::mem::{self, ManuallyDrop};
use core::ptr::{self};

use super::{AsIntoIter, InPlaceDrop, SpecFromIter, SpecFromIterNested, Vec};

/// 专业化标记，用于在重用源分配时将迭代器管道收集到 Vec 中，即
/// 在适当的位置执行管道。
#[rustc_unsafe_specialization_marker]
pub(super) trait InPlaceIterableMarker {}

impl<T> InPlaceIterableMarker for T where T: InPlaceIterable {}

impl<T, I> SpecFromIter<T, I> for Vec<T>
where
    I: Iterator<Item = T> + SourceIter<Source: AsIntoIter> + InPlaceIterableMarker,
{
    default fn from_iter(mut iterator: I) -> Self {
        // 无法通过 trait bounds 表示的附加要求。我们转而依赖 const eval：
        // a) 没有 ZST，因为没有可重用的分配，指针算法会 panic b) 与 Alloc 契约 c 要求的大小匹配) 与 Alloc 契约要求的对齐匹配
        //
        //
        //
        if mem::size_of::<T>() == 0
            || mem::size_of::<T>()
                != mem::size_of::<<<I as SourceIter>::Source as AsIntoIter>::Item>()
            || mem::align_of::<T>()
                != mem::align_of::<<<I as SourceIter>::Source as AsIntoIter>::Item>()
        {
            // 回退到更通用的实现
            return SpecFromIterNested::from_iter(iterator);
        }

        let (src_buf, src_ptr, dst_buf, dst_end, cap) = unsafe {
            let inner = iterator.as_inner().as_into_iter();
            (
                inner.buf.as_ptr(),
                inner.ptr,
                inner.buf.as_ptr() as *mut T,
                inner.end as *const T,
                inner.cap,
            )
        };

        let len = SpecInPlaceCollect::collect_in_place(&mut iterator, dst_buf, dst_end);

        let src = unsafe { iterator.as_inner().as_into_iter() };
        // 检查 SourceIter 契约是否得到维护警告：如果不是，我们甚至可能无法做到这一点
        //
        debug_assert_eq!(src_buf, src.buf.as_ptr());
        // 检查 InPlaceIterable 契约。只有迭代器推进了源指针，这才是可能的。
        // 如果它通过 TrustedRandomAccess 使用未经检查的访问，则源指针将停留在其初始位置，我们不能将其用作引用
        //
        if src.ptr != src_ptr {
            debug_assert!(
                unsafe { dst_buf.add(len) as *const _ } <= src.ptr,
                "InPlaceIterable contract violation, write pointer advanced beyond read pointer"
            );
        }

        // 丢弃源末尾的任何剩余值，但一旦 IntoIter 离开作用域，则防止丢弃分配本身，如果丢弃时出现 panic，那么我们也会泄露收集到 dst_buf 中的任何元素
        //
        // FIXME: 由于上面的 `SpecInPlaceCollect::collect_in_place` 可能在内部使用 `__iterator_get_unchecked`，因此此调用可能在 `vec::IntoIter` 上运行，内部状态不正确，即哪些元素已被 `消耗`。
        // 但是，`vec::IntoIter` 的 `TrustedRandomIteratorNoCoerce` 实现仅在 `Vec` 元素没有析构函数时才存在，因此在这种情况下元素是否被 `多次丢弃` 并不重要。
        // 这个参数在技术上目前缺乏 `SourceIter`/`InPlaceIterable` 或者 `TrustedRandomAccess` 的 `# Safety` 文档的理由，所以可能有人可能无意中创建了新的库不健全涉及这个 `.forget_allocation_drop_remaining()` 调用。
        //
        //
        //
        //
        //
        //
        //
        //
        //
        //
        src.forget_allocation_drop_remaining();

        let vec = unsafe { Vec::from_raw_parts(dst_buf, len, cap) };

        vec
    }
}

fn write_in_place_with_drop<T>(
    src_end: *const T,
) -> impl FnMut(InPlaceDrop<T>, T) -> Result<InPlaceDrop<T>, !> {
    move |mut sink, item| {
        unsafe {
            // 这里的 InPlaceIterable 契约无法精确验证，因为 try_fold 对源指针有一个唯一的引用，我们所能做的就是检查它是否仍在范围内
            //
            //
            debug_assert!(sink.dst as *const _ <= src_end, "InPlaceIterable contract violation");
            ptr::write(sink.dst, item);
            // 由于这会执行用户代码，这可能会导致 panic，因此我们必须在每一步之后 bump 指针。
            //
            sink.dst = sink.dst.add(1);
        }
        Ok(sink)
    }
}

/// 一个用于保存就地迭代收集循环的专用实现的 Helper trait
trait SpecInPlaceCollect<T, I>: Iterator<Item = T> {
    /// 将迭代器 (`self`) 收集到目标缓冲区 (`dst`) 中并返回收集的项数。`end` 是分配的最后一个可写元素，用于边界检查。
    ///
    /// 这个方法是专门的，它的一个实现使用 `Iterator::__iterator_get_unchecked` 调用，`TrustedRandomAccessNoCoerce` 绑定在 `I` 上，这意味着这个方法的调用者必须考虑 trait 的安全条件。
    ///
    ///
    ///
    ///
    fn collect_in_place(&mut self, dst: *mut T, end: *const T) -> usize;
}

impl<T, I> SpecInPlaceCollect<T, I> for I
where
    I: Iterator<Item = T>,
{
    #[inline]
    default fn collect_in_place(&mut self, dst_buf: *mut T, end: *const T) -> usize {
        // 使用 try-fold，因为
        // - 对于某些迭代器适配器，它可以更好地进行矢量化
        // - 与大多数内部迭代方法不同，它只需要一个 &mut self
        // - 它让我们把写指针穿进它的内部，最后把它拿回来
        let sink = InPlaceDrop { inner: dst_buf, dst: dst_buf };
        let sink =
            self.try_fold::<_, _, Result<_, !>>(sink, write_in_place_with_drop(end)).unwrap();
        // 迭代成功，不要丢弃 head
        unsafe { ManuallyDrop::new(sink).dst.offset_from(dst_buf) as usize }
    }
}

impl<T, I> SpecInPlaceCollect<T, I> for I
where
    I: Iterator<Item = T> + TrustedRandomAccessNoCoerce,
{
    #[inline]
    fn collect_in_place(&mut self, dst_buf: *mut T, end: *const T) -> usize {
        let len = self.size();
        let mut drop_guard = InPlaceDrop { inner: dst_buf, dst: dst_buf };
        for i in 0..len {
            // 安全性: InplaceIterable 契约保证，对于我们读取的每个元素，底层存储中的一个插槽将被释放，我们可以立即写回结果。
            //
            //
            unsafe {
                let dst = dst_buf.offset(i as isize);
                debug_assert!(dst as *const _ <= end, "InPlaceIterable contract violation");
                ptr::write(dst, self.__iterator_get_unchecked(i));
                // 由于这会执行用户代码，这可能会导致 panic，因此我们必须在每一步之后 bump 指针。
                //
                drop_guard.dst = dst.add(1);
            }
        }
        mem::forget(drop_guard);
        len
    }
}