Upgrade rayon to 1.8.1 am: 4b03aeaf3bHEADmastermainemu-34-2-dev

Original change: https://android-review.googlesource.com/c/platform/external/rust/crates/rayon/+/2953067

Change-Id: I6867003952f5bca678cb00c5b30391e8cf572919
Signed-off-by: Automerger Merge Worker <android-build-automerger-merge-worker@system.gserviceaccount.com>

16 files changed, 167 insertions, 55 deletions

diff --git a/.cargo_vcs_info.json b/.cargo_vcs_info.json
index 34dd103..45c6796 100644
--- a/.cargo_vcs_info.json
+++ b/.cargo_vcs_info.json
@@ -1,6 +1,6 @@
 {
   "git": {
-    "sha1": "6236214d717694917e77aa1c16d91176b9bc2fff"
+    "sha1": "7df6d5b8493a5fdb257565cab26dacdfe08ec8aa"
   },
   "path_in_vcs": ""
 }
\ No newline at end of file
diff --git a/Android.bp b/Android.bp
index db51fec..d0daecf 100644
--- a/Android.bp
+++ b/Android.bp
@@ -42,7 +42,7 @@ rust_library {
     host_supported: true,
     crate_name: "rayon",
     cargo_env_compat: true,
-    cargo_pkg_version: "1.7.0",
+    cargo_pkg_version: "1.8.1",
     srcs: ["src/lib.rs"],
     edition: "2021",
     rustlibs: [
diff --git a/Cargo.toml b/Cargo.toml
index 9b0e7b6..a1761f1 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -11,9 +11,9 @@
 
 [package]
 edition = "2021"
-rust-version = "1.59"
+rust-version = "1.63"
 name = "rayon"
-version = "1.7.0"
+version = "1.8.1"
 authors = [
     "Niko Matsakis <niko@alum.mit.edu>",
     "Josh Stone <cuviper@gmail.com>",
@@ -22,7 +22,6 @@ exclude = [
     "/ci/*",
     "/scripts/*",
     "/.github/*",
-    "/bors.toml",
 ]
 description = "Simple work-stealing parallelism for Rust"
 documentation = "https://docs.rs/rayon/"
@@ -43,10 +42,20 @@ version = "1.0"
 default-features = false
 
 [dependencies.rayon-core]
-version = "1.11.0"
+version = "1.12.1"
+
+[dependencies.wasm_sync]
+version = "0.1.0"
+optional = true
 
 [dev-dependencies.rand]
 version = "0.8"
 
 [dev-dependencies.rand_xorshift]
 version = "0.3"
+
+[features]
+web_spin_lock = [
+    "dep:wasm_sync",
+    "rayon-core/web_spin_lock",
+]
diff --git a/Cargo.toml.orig b/Cargo.toml.orig
index a6ccc97..293e64b 100644
--- a/Cargo.toml.orig
+++ b/Cargo.toml.orig
@@ -1,10 +1,10 @@
 [package]
 name = "rayon"
-version = "1.7.0"
+version = "1.8.1"
 authors = ["Niko Matsakis <niko@alum.mit.edu>",
            "Josh Stone <cuviper@gmail.com>"]
 description = "Simple work-stealing parallelism for Rust"
-rust-version = "1.59"
+rust-version = "1.63"
 edition = "2021"
 license = "MIT OR Apache-2.0"
 repository = "https://github.com/rayon-rs/rayon"
@@ -12,20 +12,28 @@ documentation = "https://docs.rs/rayon/"
 readme = "README.md"
 keywords = ["parallel", "thread", "concurrency", "join", "performance"]
 categories = ["concurrency"]
-exclude = ["/ci/*", "/scripts/*", "/.github/*", "/bors.toml"]
+exclude = ["/ci/*", "/scripts/*", "/.github/*"]
 
 [workspace]
 members = ["rayon-demo", "rayon-core"]
 exclude = ["ci"]
 
 [dependencies]
-rayon-core = { version = "1.11.0", path = "rayon-core" }
+rayon-core = { version = "1.12.1", path = "rayon-core" }
+wasm_sync = { version = "0.1.0", optional = true }
 
 # This is a public dependency!
 [dependencies.either]
 version = "1.0"
 default-features = false
 
+[features]
+# This feature switches to a spin-lock implementation on the browser's
+# main thread to avoid the forbidden `atomics.wait`.
+#
+# Only useful on the `wasm32-unknown-unknown` target.
+web_spin_lock = ["dep:wasm_sync", "rayon-core/web_spin_lock"]
+
 [dev-dependencies]
 rand = "0.8"
 rand_xorshift = "0.3"
diff --git a/METADATA b/METADATA
index 94b529f..4b10622 100644
--- a/METADATA
+++ b/METADATA
@@ -1,23 +1,20 @@
 # This project was upgraded with external_updater.
-# Usage: tools/external_updater/updater.sh update rust/crates/rayon
-# For more info, check https://cs.android.com/android/platform/superproject/+/master:tools/external_updater/README.md
+# Usage: tools/external_updater/updater.sh update external/rust/crates/rayon
+# For more info, check https://cs.android.com/android/platform/superproject/+/main:tools/external_updater/README.md
 
 name: "rayon"
 description: "Simple work-stealing parallelism for Rust"
 third_party {
-  url {
-    type: HOMEPAGE
-    value: "https://crates.io/crates/rayon"
-  }
-  url {
-    type: ARCHIVE
-    value: "https://static.crates.io/crates/rayon/rayon-1.7.0.crate"
-  }
-  version: "1.7.0"
   license_type: NOTICE
   last_upgrade_date {
-    year: 2023
-    month: 4
-    day: 3
+    year: 2024
+    month: 2
+    day: 6
+  }
+  homepage: "https://crates.io/crates/rayon"
+  identifier {
+    type: "Archive"
+    value: "https://static.crates.io/crates/rayon/rayon-1.8.1.crate"
+    version: "1.8.1"
   }
 }
diff --git a/README.md b/README.md
index 7f925bc..082f6a4 100644
--- a/README.md
+++ b/README.md
@@ -2,7 +2,7 @@
 
 [![Rayon crate](https://img.shields.io/crates/v/rayon.svg)](https://crates.io/crates/rayon)
 [![Rayon documentation](https://docs.rs/rayon/badge.svg)](https://docs.rs/rayon)
-![minimum rustc 1.59](https://img.shields.io/badge/rustc-1.59+-red.svg)
+![minimum rustc 1.63](https://img.shields.io/badge/rustc-1.63+-red.svg)
 [![build status](https://github.com/rayon-rs/rayon/workflows/master/badge.svg)](https://github.com/rayon-rs/rayon/actions)
 [![Join the chat at https://gitter.im/rayon-rs/Lobby](https://badges.gitter.im/rayon-rs/Lobby.svg)](https://gitter.im/rayon-rs/Lobby?utm_source=badge&utm_medium=badge&utm_campaign=pr-badge&utm_content=badge)
 
@@ -71,7 +71,7 @@ as:
 
 ```toml
 [dependencies]
-rayon = "1.7"
+rayon = "1.8"
 ```
 
 To use the parallel iterator APIs, a number of traits have to be in
@@ -84,7 +84,7 @@ just add:
 use rayon::prelude::*;
 ```
 
-Rayon currently requires `rustc 1.59.0` or greater.
+Rayon currently requires `rustc 1.63.0` or greater.
 
 ### Usage with WebAssembly
 
diff --git a/RELEASES.md b/RELEASES.md
index 28b476d..9b71516 100644
--- a/RELEASES.md
+++ b/RELEASES.md
@@ -1,3 +1,24 @@
+# Release rayon 1.8.1 / rayon-core 1.12.1 (2024-01-17)
+
+- The new `"web_spin_lock"` crate feature makes mutexes spin on the main
+  browser thread in WebAssembly, rather than suffer an error about forbidden
+  `atomics.wait` if they were to block in that context. Thanks @RReverser!
+
+# Release rayon 1.8.0 / rayon-core 1.12.0 (2023-09-20)
+
+- The minimum supported `rustc` is now 1.63.
+- Added `ThreadPoolBuilder::use_current_thread` to use the builder thread as
+  part of the new thread pool. That thread does not run the pool's main loop,
+  but it may participate in work-stealing if it yields to rayon in some way.
+- Implemented `FromParallelIterator<T>` for `Box<[T]>`, `Rc<[T]>`, and
+  `Arc<[T]>`, as well as `FromParallelIterator<Box<str>>` and
+  `ParallelExtend<Box<str>>` for `String`.
+- `ThreadPoolBuilder::build_scoped` now uses `std::thread::scope`.
+- The default number of threads is now determined using
+  `std::thread::available_parallelism` instead of the `num_cpus` crate.
+- The internal logging facility has been removed, reducing bloat for all users.
+- Many smaller performance tweaks and documentation updates.
+
 # Release rayon 1.7.0 / rayon-core 1.11.0 (2023-03-03)
 
 - The minimum supported `rustc` is now 1.59.
diff --git a/src/iter/extend.rs b/src/iter/extend.rs
index 1769d47..a264528 100644
--- a/src/iter/extend.rs
+++ b/src/iter/extend.rs
@@ -500,6 +500,16 @@ impl ParallelExtend<String> for String {
     }
 }
 
+/// Extends a string with boxed strings from a parallel iterator.
+impl ParallelExtend<Box<str>> for String {
+    fn par_extend<I>(&mut self, par_iter: I)
+    where
+        I: IntoParallelIterator<Item = Box<str>>,
+    {
+        extend!(self, par_iter, string_extend);
+    }
+}
+
 /// Extends a string with string slices from a parallel iterator.
 impl<'a> ParallelExtend<Cow<'a, str>> for String {
     fn par_extend<I>(&mut self, par_iter: I)
diff --git a/src/iter/from_par_iter.rs b/src/iter/from_par_iter.rs
index 3240f32..49afd6c 100644
--- a/src/iter/from_par_iter.rs
+++ b/src/iter/from_par_iter.rs
@@ -6,6 +6,8 @@ use std::collections::LinkedList;
 use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet};
 use std::collections::{BinaryHeap, VecDeque};
 use std::hash::{BuildHasher, Hash};
+use std::rc::Rc;
+use std::sync::Arc;
 
 /// Creates an empty default collection and extends it.
 fn collect_extended<C, I>(par_iter: I) -> C
@@ -31,6 +33,45 @@ where
     }
 }
 
+/// Collects items from a parallel iterator into a boxed slice.
+impl<T> FromParallelIterator<T> for Box<[T]>
+where
+    T: Send,
+{
+    fn from_par_iter<I>(par_iter: I) -> Self
+    where
+        I: IntoParallelIterator<Item = T>,
+    {
+        Vec::from_par_iter(par_iter).into()
+    }
+}
+
+/// Collects items from a parallel iterator into a reference-counted slice.
+impl<T> FromParallelIterator<T> for Rc<[T]>
+where
+    T: Send,
+{
+    fn from_par_iter<I>(par_iter: I) -> Self
+    where
+        I: IntoParallelIterator<Item = T>,
+    {
+        Vec::from_par_iter(par_iter).into()
+    }
+}
+
+/// Collects items from a parallel iterator into an atomically-reference-counted slice.
+impl<T> FromParallelIterator<T> for Arc<[T]>
+where
+    T: Send,
+{
+    fn from_par_iter<I>(par_iter: I) -> Self
+    where
+        I: IntoParallelIterator<Item = T>,
+    {
+        Vec::from_par_iter(par_iter).into()
+    }
+}
+
 /// Collects items from a parallel iterator into a vecdeque.
 impl<T> FromParallelIterator<T> for VecDeque<T>
 where
@@ -174,6 +215,16 @@ impl FromParallelIterator<String> for String {
     }
 }
 
+/// Collects boxed strings from a parallel iterator into one large string.
+impl FromParallelIterator<Box<str>> for String {
+    fn from_par_iter<I>(par_iter: I) -> Self
+    where
+        I: IntoParallelIterator<Item = Box<str>>,
+    {
+        collect_extended(par_iter)
+    }
+}
+
 /// Collects string slices from a parallel iterator into a string.
 impl<'a> FromParallelIterator<Cow<'a, str>> for String {
     fn from_par_iter<I>(par_iter: I) -> Self
diff --git a/src/iter/mod.rs b/src/iter/mod.rs
index e60ea16..7b5a29a 100644
--- a/src/iter/mod.rs
+++ b/src/iter/mod.rs
@@ -1547,7 +1547,7 @@ pub trait ParallelIterator: Sized + Send {
 
     /// Computes the maximum of all the items in the iterator with respect to
     /// the given comparison function. If the iterator is empty, `None` is
-    /// returned; otherwise, `Some(min)` is returned.
+    /// returned; otherwise, `Some(max)` is returned.
     ///
     /// Note that the order in which the items will be reduced is not
     /// specified, so if the comparison function is not associative, then
@@ -2392,7 +2392,7 @@ impl<T: ParallelIterator> IntoParallelIterator for T {
 #[allow(clippy::len_without_is_empty)]
 pub trait IndexedParallelIterator: ParallelIterator {
     /// Collects the results of the iterator into the specified
-    /// vector. The vector is always truncated before execution
+    /// vector. The vector is always cleared before execution
     /// begins. If possible, reusing the vector across calls can lead
     /// to better performance since it reuses the same backing buffer.
     ///
@@ -2401,7 +2401,7 @@ pub trait IndexedParallelIterator: ParallelIterator {
     /// ```
     /// use rayon::prelude::*;
     ///
-    /// // any prior data will be truncated
+    /// // any prior data will be cleared
     /// let mut vec = vec![-1, -2, -3];
     ///
     /// (0..5).into_par_iter()
@@ -2414,7 +2414,7 @@ pub trait IndexedParallelIterator: ParallelIterator {
     }
 
     /// Unzips the results of the iterator into the specified
-    /// vectors. The vectors are always truncated before execution
+    /// vectors. The vectors are always cleared before execution
     /// begins. If possible, reusing the vectors across calls can lead
     /// to better performance since they reuse the same backing buffer.
     ///
@@ -2423,7 +2423,7 @@ pub trait IndexedParallelIterator: ParallelIterator {
     /// ```
     /// use rayon::prelude::*;
     ///
-    /// // any prior data will be truncated
+    /// // any prior data will be cleared
     /// let mut left = vec![42; 10];
     /// let mut right = vec![-1; 10];
     ///
diff --git a/src/iter/par_bridge.rs b/src/iter/par_bridge.rs
index 8398274..17bc15b 100644
--- a/src/iter/par_bridge.rs
+++ b/src/iter/par_bridge.rs
@@ -1,6 +1,11 @@
-use std::sync::atomic::{AtomicBool, AtomicUsize, Ordering};
+#[cfg(not(feature = "web_spin_lock"))]
 use std::sync::Mutex;
 
+#[cfg(feature = "web_spin_lock")]
+use wasm_sync::Mutex;
+
+use std::sync::atomic::{AtomicBool, AtomicUsize, Ordering};
+
 use crate::iter::plumbing::{bridge_unindexed, Folder, UnindexedConsumer, UnindexedProducer};
 use crate::iter::ParallelIterator;
 use crate::{current_num_threads, current_thread_index};
@@ -13,6 +18,11 @@ use crate::{current_num_threads, current_thread_index};
 /// `par_iter` instead. However, it can still be useful for iterators that are difficult to
 /// parallelize by other means, like channels or file or network I/O.
 ///
+/// Iterator items are pulled by `next()` one at a time, synchronized from each thread that is
+/// ready for work, so this may become a bottleneck if the serial iterator can't keep up with the
+/// parallel demand. The items are not buffered by `IterBridge`, so it's fine to use this with
+/// large or even unbounded iterators.
+///
 /// The resulting iterator is not guaranteed to keep the order of the original iterator.
 ///
 /// # Examples
diff --git a/src/iter/product.rs b/src/iter/product.rs
index a3d0727..e081be0 100644
--- a/src/iter/product.rs
+++ b/src/iter/product.rs
@@ -13,7 +13,7 @@ where
 }
 
 fn mul<T: Product>(left: T, right: T) -> T {
-    iter::once(left).chain(iter::once(right)).product()
+    [left, right].into_iter().product()
 }
 
 struct ProductConsumer<P: Send> {
diff --git a/src/iter/sum.rs b/src/iter/sum.rs
index a73e0bf..ddae810 100644
--- a/src/iter/sum.rs
+++ b/src/iter/sum.rs
@@ -13,7 +13,7 @@ where
 }
 
 fn add<T: Sum>(left: T, right: T) -> T {
-    iter::once(left).chain(iter::once(right)).sum()
+    [left, right].into_iter().sum()
 }
 
 struct SumConsumer<S: Send> {
diff --git a/src/iter/test.rs b/src/iter/test.rs
index c72068d..45fb971 100644
--- a/src/iter/test.rs
+++ b/src/iter/test.rs
@@ -654,7 +654,7 @@ fn check_partial_cmp_late_nan_direct() {
 }
 
 #[test]
-fn check_partial_cmp_late_nane_to_seq() {
+fn check_partial_cmp_late_nan_to_seq() {
     let a = vec![0.0, f64::NAN];
     let b = vec![1.0, 1.0];
 
diff --git a/src/lib.rs b/src/lib.rs
index 86f997b..dc7fcc0 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -152,7 +152,7 @@ impl<T> SendPtr<T> {
 // Implement Clone without the T: Clone bound from the derive
 impl<T> Clone for SendPtr<T> {
     fn clone(&self) -> Self {
-        Self(self.0)
+        *self
     }
 }
 
diff --git a/src/slice/quicksort.rs b/src/slice/quicksort.rs
index d71079e..2bfc350 100644
--- a/src/slice/quicksort.rs
+++ b/src/slice/quicksort.rs
@@ -5,16 +5,34 @@
 //! `rayon_core::join`.
 
 use std::cmp;
+use std::marker::PhantomData;
 use std::mem::{self, MaybeUninit};
 use std::ptr;
 
 /// When dropped, copies from `src` into `dest`.
-struct CopyOnDrop<T> {
+#[must_use]
+struct CopyOnDrop<'a, T> {
     src: *const T,
     dest: *mut T,
+    /// `src` is often a local pointer here, make sure we have appropriate
+    /// PhantomData so that dropck can protect us.
+    marker: PhantomData<&'a mut T>,
 }
 
-impl<T> Drop for CopyOnDrop<T> {
+impl<'a, T> CopyOnDrop<'a, T> {
+    /// Construct from a source pointer and a destination
+    /// Assumes dest lives longer than src, since there is no easy way to
+    /// copy down lifetime information from another pointer
+    unsafe fn new(src: &'a T, dest: *mut T) -> Self {
+        CopyOnDrop {
+            src,
+            dest,
+            marker: PhantomData,
+        }
+    }
+}
+
+impl<T> Drop for CopyOnDrop<'_, T> {
     fn drop(&mut self) {
         // SAFETY:  This is a helper class.
         //          Please refer to its usage for correctness.
@@ -54,10 +72,7 @@ where
             // into the slice.
             let tmp = mem::ManuallyDrop::new(ptr::read(v.get_unchecked(0)));
             let v = v.as_mut_ptr();
-            let mut hole = CopyOnDrop {
-                src: &*tmp,
-                dest: v.add(1),
-            };
+            let mut hole = CopyOnDrop::new(&*tmp, v.add(1));
             ptr::copy_nonoverlapping(v.add(1), v.add(0), 1);
 
             for i in 2..len {
@@ -103,10 +118,7 @@ where
             // into the slice.
             let tmp = mem::ManuallyDrop::new(ptr::read(v.get_unchecked(len - 1)));
             let v = v.as_mut_ptr();
-            let mut hole = CopyOnDrop {
-                src: &*tmp,
-                dest: v.add(len - 2),
-            };
+            let mut hole = CopyOnDrop::new(&*tmp, v.add(len - 2));
             ptr::copy_nonoverlapping(v.add(len - 2), v.add(len - 1), 1);
 
             for i in (0..len - 2).rev() {
@@ -510,10 +522,7 @@ where
 
         // SAFETY: `pivot` is a reference to the first element of `v`, so `ptr::read` is safe.
         let tmp = mem::ManuallyDrop::new(unsafe { ptr::read(pivot) });
-        let _pivot_guard = CopyOnDrop {
-            src: &*tmp,
-            dest: pivot,
-        };
+        let _pivot_guard = unsafe { CopyOnDrop::new(&*tmp, pivot) };
         let pivot = &*tmp;
 
         // Find the first pair of out-of-order elements.
@@ -569,10 +578,7 @@ where
     // operation panics, the pivot will be automatically written back into the slice.
     // SAFETY: The pointer here is valid because it is obtained from a reference to a slice.
     let tmp = mem::ManuallyDrop::new(unsafe { ptr::read(pivot) });
-    let _pivot_guard = CopyOnDrop {
-        src: &*tmp,
-        dest: pivot,
-    };
+    let _pivot_guard = unsafe { CopyOnDrop::new(&*tmp, pivot) };
     let pivot = &*tmp;
 
     // Now partition the slice.