aboutsummaryrefslogtreecommitdiff
path: root/vendor/rayon/src/iter/collect
diff options
context:
space:
mode:
authorValentin Popov <valentin@popov.link>2024-07-19 15:37:58 +0300
committerValentin Popov <valentin@popov.link>2024-07-19 15:37:58 +0300
commita990de90fe41456a23e58bd087d2f107d321f3a1 (patch)
tree15afc392522a9e85dc3332235e311b7d39352ea9 /vendor/rayon/src/iter/collect
parent3d48cd3f81164bbfc1a755dc1d4a9a02f98c8ddd (diff)
downloadfparkan-a990de90fe41456a23e58bd087d2f107d321f3a1.tar.xz
fparkan-a990de90fe41456a23e58bd087d2f107d321f3a1.zip
Deleted vendor folder
Diffstat (limited to 'vendor/rayon/src/iter/collect')
-rw-r--r--vendor/rayon/src/iter/collect/consumer.rs186
-rw-r--r--vendor/rayon/src/iter/collect/mod.rs116
-rw-r--r--vendor/rayon/src/iter/collect/test.rs373
3 files changed, 0 insertions, 675 deletions
diff --git a/vendor/rayon/src/iter/collect/consumer.rs b/vendor/rayon/src/iter/collect/consumer.rs
deleted file mode 100644
index acd67df..0000000
--- a/vendor/rayon/src/iter/collect/consumer.rs
+++ /dev/null
@@ -1,186 +0,0 @@
-use super::super::plumbing::*;
-use crate::SendPtr;
-use std::marker::PhantomData;
-use std::ptr;
-use std::slice;
-
-pub(super) struct CollectConsumer<'c, T: Send> {
- /// See `CollectResult` for explanation of why this is not a slice
- start: SendPtr<T>,
- len: usize,
- marker: PhantomData<&'c mut T>,
-}
-
-impl<T: Send> CollectConsumer<'_, T> {
- /// Create a collector for `len` items in the unused capacity of the vector.
- pub(super) fn appender(vec: &mut Vec<T>, len: usize) -> CollectConsumer<'_, T> {
- let start = vec.len();
- assert!(vec.capacity() - start >= len);
-
- // SAFETY: We already made sure to have the additional space allocated.
- // The pointer is derived from `Vec` directly, not through a `Deref`,
- // so it has provenance over the whole allocation.
- unsafe { CollectConsumer::new(vec.as_mut_ptr().add(start), len) }
- }
-}
-
-impl<'c, T: Send + 'c> CollectConsumer<'c, T> {
- /// The target memory is considered uninitialized, and will be
- /// overwritten without reading or dropping existing values.
- unsafe fn new(start: *mut T, len: usize) -> Self {
- CollectConsumer {
- start: SendPtr(start),
- len,
- marker: PhantomData,
- }
- }
-}
-
-/// CollectResult represents an initialized part of the target slice.
-///
-/// This is a proxy owner of the elements in the slice; when it drops,
-/// the elements will be dropped, unless its ownership is released before then.
-#[must_use]
-pub(super) struct CollectResult<'c, T> {
- /// This pointer and length has the same representation as a slice,
- /// but retains the provenance of the entire array so that we can merge
- /// these regions together in `CollectReducer`.
- start: SendPtr<T>,
- total_len: usize,
- /// The current initialized length after `start`
- initialized_len: usize,
- /// Lifetime invariance guarantees that the data flows from consumer to result,
- /// especially for the `scope_fn` callback in `Collect::with_consumer`.
- invariant_lifetime: PhantomData<&'c mut &'c mut [T]>,
-}
-
-unsafe impl<'c, T> Send for CollectResult<'c, T> where T: Send {}
-
-impl<'c, T> CollectResult<'c, T> {
- /// The current length of the collect result
- pub(super) fn len(&self) -> usize {
- self.initialized_len
- }
-
- /// Release ownership of the slice of elements, and return the length
- pub(super) fn release_ownership(mut self) -> usize {
- let ret = self.initialized_len;
- self.initialized_len = 0;
- ret
- }
-}
-
-impl<'c, T> Drop for CollectResult<'c, T> {
- fn drop(&mut self) {
- // Drop the first `self.initialized_len` elements, which have been recorded
- // to be initialized by the folder.
- unsafe {
- ptr::drop_in_place(slice::from_raw_parts_mut(
- self.start.0,
- self.initialized_len,
- ));
- }
- }
-}
-
-impl<'c, T: Send + 'c> Consumer<T> for CollectConsumer<'c, T> {
- type Folder = CollectResult<'c, T>;
- type Reducer = CollectReducer;
- type Result = CollectResult<'c, T>;
-
- fn split_at(self, index: usize) -> (Self, Self, CollectReducer) {
- let CollectConsumer { start, len, .. } = self;
-
- // Produce new consumers.
- // SAFETY: This assert checks that `index` is a valid offset for `start`
- unsafe {
- assert!(index <= len);
- (
- CollectConsumer::new(start.0, index),
- CollectConsumer::new(start.0.add(index), len - index),
- CollectReducer,
- )
- }
- }
-
- fn into_folder(self) -> Self::Folder {
- // Create a result/folder that consumes values and writes them
- // into the region after start. The initial result has length 0.
- CollectResult {
- start: self.start,
- total_len: self.len,
- initialized_len: 0,
- invariant_lifetime: PhantomData,
- }
- }
-
- fn full(&self) -> bool {
- false
- }
-}
-
-impl<'c, T: Send + 'c> Folder<T> for CollectResult<'c, T> {
- type Result = Self;
-
- fn consume(mut self, item: T) -> Self {
- assert!(
- self.initialized_len < self.total_len,
- "too many values pushed to consumer"
- );
-
- // SAFETY: The assert above is a bounds check for this write, and we
- // avoid assignment here so we do not drop an uninitialized T.
- unsafe {
- // Write item and increase the initialized length
- self.start.0.add(self.initialized_len).write(item);
- self.initialized_len += 1;
- }
-
- self
- }
-
- fn complete(self) -> Self::Result {
- // NB: We don't explicitly check that the local writes were complete,
- // but Collect will assert the total result length in the end.
- self
- }
-
- fn full(&self) -> bool {
- false
- }
-}
-
-/// Pretend to be unindexed for `special_collect_into_vec`,
-/// but we should never actually get used that way...
-impl<'c, T: Send + 'c> UnindexedConsumer<T> for CollectConsumer<'c, T> {
- fn split_off_left(&self) -> Self {
- unreachable!("CollectConsumer must be indexed!")
- }
- fn to_reducer(&self) -> Self::Reducer {
- CollectReducer
- }
-}
-
-/// CollectReducer combines adjacent chunks; the result must always
-/// be contiguous so that it is one combined slice.
-pub(super) struct CollectReducer;
-
-impl<'c, T> Reducer<CollectResult<'c, T>> for CollectReducer {
- fn reduce(
- self,
- mut left: CollectResult<'c, T>,
- right: CollectResult<'c, T>,
- ) -> CollectResult<'c, T> {
- // Merge if the CollectResults are adjacent and in left to right order
- // else: drop the right piece now and total length will end up short in the end,
- // when the correctness of the collected result is asserted.
- unsafe {
- let left_end = left.start.0.add(left.initialized_len);
- if left_end == right.start.0 {
- left.total_len += right.total_len;
- left.initialized_len += right.release_ownership();
- }
- left
- }
- }
-}
diff --git a/vendor/rayon/src/iter/collect/mod.rs b/vendor/rayon/src/iter/collect/mod.rs
deleted file mode 100644
index 4044a68..0000000
--- a/vendor/rayon/src/iter/collect/mod.rs
+++ /dev/null
@@ -1,116 +0,0 @@
-use super::{IndexedParallelIterator, ParallelIterator};
-
-mod consumer;
-use self::consumer::CollectConsumer;
-use self::consumer::CollectResult;
-use super::unzip::unzip_indexed;
-
-mod test;
-
-/// Collects the results of the exact iterator into the specified vector.
-///
-/// This is called by `IndexedParallelIterator::collect_into_vec`.
-pub(super) fn collect_into_vec<I, T>(pi: I, v: &mut Vec<T>)
-where
- I: IndexedParallelIterator<Item = T>,
- T: Send,
-{
- v.truncate(0); // clear any old data
- let len = pi.len();
- collect_with_consumer(v, len, |consumer| pi.drive(consumer));
-}
-
-/// Collects the results of the iterator into the specified vector.
-///
-/// Technically, this only works for `IndexedParallelIterator`, but we're faking a
-/// bit of specialization here until Rust can do that natively. Callers are
-/// using `opt_len` to find the length before calling this, and only exact
-/// iterators will return anything but `None` there.
-///
-/// Since the type system doesn't understand that contract, we have to allow
-/// *any* `ParallelIterator` here, and `CollectConsumer` has to also implement
-/// `UnindexedConsumer`. That implementation panics `unreachable!` in case
-/// there's a bug where we actually do try to use this unindexed.
-pub(super) fn special_extend<I, T>(pi: I, len: usize, v: &mut Vec<T>)
-where
- I: ParallelIterator<Item = T>,
- T: Send,
-{
- collect_with_consumer(v, len, |consumer| pi.drive_unindexed(consumer));
-}
-
-/// Unzips the results of the exact iterator into the specified vectors.
-///
-/// This is called by `IndexedParallelIterator::unzip_into_vecs`.
-pub(super) fn unzip_into_vecs<I, A, B>(pi: I, left: &mut Vec<A>, right: &mut Vec<B>)
-where
- I: IndexedParallelIterator<Item = (A, B)>,
- A: Send,
- B: Send,
-{
- // clear any old data
- left.truncate(0);
- right.truncate(0);
-
- let len = pi.len();
- collect_with_consumer(right, len, |right_consumer| {
- let mut right_result = None;
- collect_with_consumer(left, len, |left_consumer| {
- let (left_r, right_r) = unzip_indexed(pi, left_consumer, right_consumer);
- right_result = Some(right_r);
- left_r
- });
- right_result.unwrap()
- });
-}
-
-/// Create a consumer on the slice of memory we are collecting into.
-///
-/// The consumer needs to be used inside the scope function, and the
-/// complete collect result passed back.
-///
-/// This method will verify the collect result, and panic if the slice
-/// was not fully written into. Otherwise, in the successful case,
-/// the vector is complete with the collected result.
-fn collect_with_consumer<T, F>(vec: &mut Vec<T>, len: usize, scope_fn: F)
-where
- T: Send,
- F: FnOnce(CollectConsumer<'_, T>) -> CollectResult<'_, T>,
-{
- // Reserve space for `len` more elements in the vector,
- vec.reserve(len);
-
- // Create the consumer and run the callback for collection.
- let result = scope_fn(CollectConsumer::appender(vec, len));
-
- // The `CollectResult` represents a contiguous part of the slice, that has
- // been written to. On unwind here, the `CollectResult` will be dropped. If
- // some producers on the way did not produce enough elements, partial
- // `CollectResult`s may have been dropped without being reduced to the final
- // result, and we will see that as the length coming up short.
- //
- // Here, we assert that added length is fully initialized. This is checked
- // by the following assert, which verifies if a complete `CollectResult`
- // was produced; if the length is correct, it is necessarily covering the
- // target slice. Since we know that the consumer cannot have escaped from
- // `drive` (by parametricity, essentially), we know that any stores that
- // will happen, have happened. Unless some code is buggy, that means we
- // should have seen `len` total writes.
- let actual_writes = result.len();
- assert!(
- actual_writes == len,
- "expected {} total writes, but got {}",
- len,
- actual_writes
- );
-
- // Release the result's mutable borrow and "proxy ownership"
- // of the elements, before the vector takes it over.
- result.release_ownership();
-
- let new_len = vec.len() + len;
-
- unsafe {
- vec.set_len(new_len);
- }
-}
diff --git a/vendor/rayon/src/iter/collect/test.rs b/vendor/rayon/src/iter/collect/test.rs
deleted file mode 100644
index 97bec3f..0000000
--- a/vendor/rayon/src/iter/collect/test.rs
+++ /dev/null
@@ -1,373 +0,0 @@
-#![cfg(test)]
-#![allow(unused_assignments)]
-
-// These tests are primarily targeting "abusive" producers that will
-// try to drive the "collect consumer" incorrectly. These should
-// result in panics.
-
-use super::collect_with_consumer;
-use crate::iter::plumbing::*;
-use rayon_core::join;
-
-use std::fmt;
-use std::panic;
-use std::sync::atomic::{AtomicUsize, Ordering};
-use std::thread::Result as ThreadResult;
-
-/// Promises to produce 2 items, but then produces 3. Does not do any
-/// splits at all.
-#[test]
-#[should_panic(expected = "too many values")]
-fn produce_too_many_items() {
- let mut v = vec![];
- collect_with_consumer(&mut v, 2, |consumer| {
- let mut folder = consumer.into_folder();
- folder = folder.consume(22);
- folder = folder.consume(23);
- folder = folder.consume(24);
- unreachable!("folder does not complete")
- });
-}
-
-/// Produces fewer items than promised. Does not do any
-/// splits at all.
-#[test]
-#[should_panic(expected = "expected 5 total writes, but got 2")]
-fn produce_fewer_items() {
- let mut v = vec![];
- collect_with_consumer(&mut v, 5, |consumer| {
- let mut folder = consumer.into_folder();
- folder = folder.consume(22);
- folder = folder.consume(23);
- folder.complete()
- });
-}
-
-// Complete is not called by the consumer. Hence,the collection vector is not fully initialized.
-#[test]
-#[should_panic(expected = "expected 4 total writes, but got 2")]
-fn left_produces_items_with_no_complete() {
- let mut v = vec![];
- collect_with_consumer(&mut v, 4, |consumer| {
- let (left_consumer, right_consumer, _) = consumer.split_at(2);
- let mut left_folder = left_consumer.into_folder();
- let mut right_folder = right_consumer.into_folder();
- left_folder = left_folder.consume(0).consume(1);
- right_folder = right_folder.consume(2).consume(3);
- right_folder.complete()
- });
-}
-
-// Complete is not called by the right consumer. Hence,the
-// collection vector is not fully initialized.
-#[test]
-#[should_panic(expected = "expected 4 total writes, but got 2")]
-fn right_produces_items_with_no_complete() {
- let mut v = vec![];
- collect_with_consumer(&mut v, 4, |consumer| {
- let (left_consumer, right_consumer, _) = consumer.split_at(2);
- let mut left_folder = left_consumer.into_folder();
- let mut right_folder = right_consumer.into_folder();
- left_folder = left_folder.consume(0).consume(1);
- right_folder = right_folder.consume(2).consume(3);
- left_folder.complete()
- });
-}
-
-// Complete is not called by the consumer. Hence,the collection vector is not fully initialized.
-#[test]
-#[cfg_attr(not(panic = "unwind"), ignore)]
-fn produces_items_with_no_complete() {
- let counter = DropCounter::default();
- let mut v = vec![];
- let panic_result = panic::catch_unwind(panic::AssertUnwindSafe(|| {
- collect_with_consumer(&mut v, 2, |consumer| {
- let mut folder = consumer.into_folder();
- folder = folder.consume(counter.element());
- folder = folder.consume(counter.element());
- panic!("folder does not complete");
- });
- }));
- assert!(v.is_empty());
- assert_is_panic_with_message(&panic_result, "folder does not complete");
- counter.assert_drop_count();
-}
-
-// The left consumer produces too many items while the right
-// consumer produces correct number.
-#[test]
-#[should_panic(expected = "too many values")]
-fn left_produces_too_many_items() {
- let mut v = vec![];
- collect_with_consumer(&mut v, 4, |consumer| {
- let (left_consumer, right_consumer, _) = consumer.split_at(2);
- let mut left_folder = left_consumer.into_folder();
- let mut right_folder = right_consumer.into_folder();
- left_folder = left_folder.consume(0).consume(1).consume(2);
- right_folder = right_folder.consume(2).consume(3);
- let _ = right_folder.complete();
- unreachable!("folder does not complete");
- });
-}
-
-// The right consumer produces too many items while the left
-// consumer produces correct number.
-#[test]
-#[should_panic(expected = "too many values")]
-fn right_produces_too_many_items() {
- let mut v = vec![];
- collect_with_consumer(&mut v, 4, |consumer| {
- let (left_consumer, right_consumer, _) = consumer.split_at(2);
- let mut left_folder = left_consumer.into_folder();
- let mut right_folder = right_consumer.into_folder();
- left_folder = left_folder.consume(0).consume(1);
- right_folder = right_folder.consume(2).consume(3).consume(4);
- let _ = left_folder.complete();
- unreachable!("folder does not complete");
- });
-}
-
-// The left consumer produces fewer items while the right
-// consumer produces correct number.
-#[test]
-#[should_panic(expected = "expected 4 total writes, but got 1")]
-fn left_produces_fewer_items() {
- let mut v = vec![];
- collect_with_consumer(&mut v, 4, |consumer| {
- let reducer = consumer.to_reducer();
- let (left_consumer, right_consumer, _) = consumer.split_at(2);
- let mut left_folder = left_consumer.into_folder();
- let mut right_folder = right_consumer.into_folder();
- left_folder = left_folder.consume(0);
- right_folder = right_folder.consume(2).consume(3);
- let left_result = left_folder.complete();
- let right_result = right_folder.complete();
- reducer.reduce(left_result, right_result)
- });
-}
-
-// The left and right consumer produce the correct number but
-// only left result is returned
-#[test]
-#[should_panic(expected = "expected 4 total writes, but got 2")]
-fn only_left_result() {
- let mut v = vec![];
- collect_with_consumer(&mut v, 4, |consumer| {
- let (left_consumer, right_consumer, _) = consumer.split_at(2);
- let mut left_folder = left_consumer.into_folder();
- let mut right_folder = right_consumer.into_folder();
- left_folder = left_folder.consume(0).consume(1);
- right_folder = right_folder.consume(2).consume(3);
- let left_result = left_folder.complete();
- let _ = right_folder.complete();
- left_result
- });
-}
-
-// The left and right consumer produce the correct number but
-// only right result is returned
-#[test]
-#[should_panic(expected = "expected 4 total writes, but got 2")]
-fn only_right_result() {
- let mut v = vec![];
- collect_with_consumer(&mut v, 4, |consumer| {
- let (left_consumer, right_consumer, _) = consumer.split_at(2);
- let mut left_folder = left_consumer.into_folder();
- let mut right_folder = right_consumer.into_folder();
- left_folder = left_folder.consume(0).consume(1);
- right_folder = right_folder.consume(2).consume(3);
- let _ = left_folder.complete();
- right_folder.complete()
- });
-}
-
-// The left and right consumer produce the correct number but reduce
-// in the wrong order.
-#[test]
-#[should_panic(expected = "expected 4 total writes, but got 2")]
-fn reducer_does_not_preserve_order() {
- let mut v = vec![];
- collect_with_consumer(&mut v, 4, |consumer| {
- let reducer = consumer.to_reducer();
- let (left_consumer, right_consumer, _) = consumer.split_at(2);
- let mut left_folder = left_consumer.into_folder();
- let mut right_folder = right_consumer.into_folder();
- left_folder = left_folder.consume(0).consume(1);
- right_folder = right_folder.consume(2).consume(3);
- let left_result = left_folder.complete();
- let right_result = right_folder.complete();
- reducer.reduce(right_result, left_result)
- });
-}
-
-// The right consumer produces fewer items while the left
-// consumer produces correct number.
-#[test]
-#[should_panic(expected = "expected 4 total writes, but got 3")]
-fn right_produces_fewer_items() {
- let mut v = vec![];
- collect_with_consumer(&mut v, 4, |consumer| {
- let reducer = consumer.to_reducer();
- let (left_consumer, right_consumer, _) = consumer.split_at(2);
- let mut left_folder = left_consumer.into_folder();
- let mut right_folder = right_consumer.into_folder();
- left_folder = left_folder.consume(0).consume(1);
- right_folder = right_folder.consume(2);
- let left_result = left_folder.complete();
- let right_result = right_folder.complete();
- reducer.reduce(left_result, right_result)
- });
-}
-
-// The left consumer panics and the right stops short, like `panic_fuse()`.
-// We should get the left panic without finishing `collect_with_consumer`.
-#[test]
-#[should_panic(expected = "left consumer panic")]
-fn left_panics() {
- let mut v = vec![];
- collect_with_consumer(&mut v, 4, |consumer| {
- let reducer = consumer.to_reducer();
- let (left_consumer, right_consumer, _) = consumer.split_at(2);
- let (left_result, right_result) = join(
- || {
- let mut left_folder = left_consumer.into_folder();
- left_folder = left_folder.consume(0);
- panic!("left consumer panic");
- },
- || {
- let mut right_folder = right_consumer.into_folder();
- right_folder = right_folder.consume(2);
- right_folder.complete() // early return
- },
- );
- reducer.reduce(left_result, right_result)
- });
- unreachable!();
-}
-
-// The right consumer panics and the left stops short, like `panic_fuse()`.
-// We should get the right panic without finishing `collect_with_consumer`.
-#[test]
-#[should_panic(expected = "right consumer panic")]
-fn right_panics() {
- let mut v = vec![];
- collect_with_consumer(&mut v, 4, |consumer| {
- let reducer = consumer.to_reducer();
- let (left_consumer, right_consumer, _) = consumer.split_at(2);
- let (left_result, right_result) = join(
- || {
- let mut left_folder = left_consumer.into_folder();
- left_folder = left_folder.consume(0);
- left_folder.complete() // early return
- },
- || {
- let mut right_folder = right_consumer.into_folder();
- right_folder = right_folder.consume(2);
- panic!("right consumer panic");
- },
- );
- reducer.reduce(left_result, right_result)
- });
- unreachable!();
-}
-
-// The left consumer produces fewer items while the right
-// consumer produces correct number; check that created elements are dropped
-#[test]
-#[cfg_attr(not(panic = "unwind"), ignore)]
-fn left_produces_fewer_items_drops() {
- let counter = DropCounter::default();
- let mut v = vec![];
- let panic_result = panic::catch_unwind(panic::AssertUnwindSafe(|| {
- collect_with_consumer(&mut v, 4, |consumer| {
- let reducer = consumer.to_reducer();
- let (left_consumer, right_consumer, _) = consumer.split_at(2);
- let mut left_folder = left_consumer.into_folder();
- let mut right_folder = right_consumer.into_folder();
- left_folder = left_folder.consume(counter.element());
- right_folder = right_folder
- .consume(counter.element())
- .consume(counter.element());
- let left_result = left_folder.complete();
- let right_result = right_folder.complete();
- reducer.reduce(left_result, right_result)
- });
- }));
- assert!(v.is_empty());
- assert_is_panic_with_message(&panic_result, "expected 4 total writes, but got 1");
- counter.assert_drop_count();
-}
-
-/// This counter can create elements, and then count and verify
-/// the number of which have actually been dropped again.
-#[derive(Default)]
-struct DropCounter {
- created: AtomicUsize,
- dropped: AtomicUsize,
-}
-
-struct Element<'a>(&'a AtomicUsize);
-
-impl DropCounter {
- fn created(&self) -> usize {
- self.created.load(Ordering::SeqCst)
- }
-
- fn dropped(&self) -> usize {
- self.dropped.load(Ordering::SeqCst)
- }
-
- fn element(&self) -> Element<'_> {
- self.created.fetch_add(1, Ordering::SeqCst);
- Element(&self.dropped)
- }
-
- fn assert_drop_count(&self) {
- assert_eq!(
- self.created(),
- self.dropped(),
- "Expected {} dropped elements, but found {}",
- self.created(),
- self.dropped()
- );
- }
-}
-
-impl<'a> Drop for Element<'a> {
- fn drop(&mut self) {
- self.0.fetch_add(1, Ordering::SeqCst);
- }
-}
-
-/// Assert that the result from catch_unwind is a panic that contains expected message
-fn assert_is_panic_with_message<T>(result: &ThreadResult<T>, expected: &str)
-where
- T: fmt::Debug,
-{
- match result {
- Ok(value) => {
- panic!(
- "assertion failure: Expected panic, got successful {:?}",
- value
- );
- }
- Err(error) => {
- let message_str = error.downcast_ref::<&'static str>().cloned();
- let message_string = error.downcast_ref::<String>().map(String::as_str);
- if let Some(message) = message_str.or(message_string) {
- if !message.contains(expected) {
- panic!(
- "assertion failure: Expected {:?}, but found panic with {:?}",
- expected, message
- );
- }
- // assertion passes
- } else {
- panic!(
- "assertion failure: Expected {:?}, but found panic with unknown value",
- expected
- );
- }
- }
- }
-}