Auto merge of #79895 - Kerollmops:slice-group-by, r=m-ou-se

The return of the GroupBy and GroupByMut iterators on slice

According to https://github.com/rust-lang/rfcs/pull/2477#issuecomment-742034372, I am opening this PR again, this time I implemented it in safe Rust only, it is therefore much easier to read and is completely safe.

This PR proposes to add two new methods to the slice, the `group_by` and `group_by_mut`. These two methods provide a way to iterate over non-overlapping sub-slices of a base slice that are separated by the predicate given by the user (e.g. `Partial::eq`, `|a, b| a.abs() < b.abs()`).

```rust
let slice = &[1, 1, 1, 3, 3, 2, 2, 2];

let mut iter = slice.group_by(|a, b| a == b);
assert_eq!(iter.next(), Some(&[1, 1, 1][..]));
assert_eq!(iter.next(), Some(&[3, 3][..]));
assert_eq!(iter.next(), Some(&[2, 2, 2][..]));
assert_eq!(iter.next(), None);
```

[An RFC](https://github.com/rust-lang/rfcs/pull/2477) was open 2 years ago but wasn't necessary.

4 files changed, 62 insertions, 0 deletions

diff --git a/library/alloc/src/lib.rs b/library/alloc/src/lib.rs
index 54b402faaeb..e6db66ac571 100644
--- a/library/alloc/src/lib.rs
+++ b/library/alloc/src/lib.rs
@@ -139,6 +139,7 @@
 #![feature(try_trait)]
 #![feature(type_alias_impl_trait)]
 #![feature(associated_type_bounds)]
+#![feature(slice_group_by)]
 // Allow testing this library
 
 #[cfg(test)]
diff --git a/library/alloc/src/slice.rs b/library/alloc/src/slice.rs
index 064700fc72c..cb015b94930 100644
--- a/library/alloc/src/slice.rs
+++ b/library/alloc/src/slice.rs
@@ -110,6 +110,8 @@ pub use core::slice::{Chunks, Windows};
 pub use core::slice::{ChunksExact, ChunksExactMut};
 #[stable(feature = "rust1", since = "1.0.0")]
 pub use core::slice::{ChunksMut, Split, SplitMut};
+#[unstable(feature = "slice_group_by", issue = "80552")]
+pub use core::slice::{GroupBy, GroupByMut};
 #[stable(feature = "rust1", since = "1.0.0")]
 pub use core::slice::{Iter, IterMut};
 #[stable(feature = "rchunks", since = "1.31.0")]
diff --git a/library/alloc/tests/lib.rs b/library/alloc/tests/lib.rs
index b56437bd188..cd4174ed400 100644
--- a/library/alloc/tests/lib.rs
+++ b/library/alloc/tests/lib.rs
@@ -20,6 +20,7 @@
 #![feature(iter_map_while)]
 #![feature(int_bits_const)]
 #![feature(vecdeque_binary_search)]
+#![feature(slice_group_by)]
 
 use std::collections::hash_map::DefaultHasher;
 use std::hash::{Hash, Hasher};
diff --git a/library/alloc/tests/slice.rs b/library/alloc/tests/slice.rs
index a4f0fb415fb..777c10b1bf7 100644
--- a/library/alloc/tests/slice.rs
+++ b/library/alloc/tests/slice.rs
@@ -1898,3 +1898,61 @@ fn subslice_patterns() {
     m!(&mut v, [..] => ());
     m!(&mut v, [x, .., y] => c!((x, y), (&mut N, &mut N), (&mut N(0), &mut N(4))));
 }
+
+#[test]
+fn test_group_by() {
+    let slice = &[1, 1, 1, 3, 3, 2, 2, 2, 1, 0];
+
+    let mut iter = slice.group_by(|a, b| a == b);
+    assert_eq!(iter.next(), Some(&[1, 1, 1][..]));
+    assert_eq!(iter.next(), Some(&[3, 3][..]));
+    assert_eq!(iter.next(), Some(&[2, 2, 2][..]));
+    assert_eq!(iter.next(), Some(&[1][..]));
+    assert_eq!(iter.next(), Some(&[0][..]));
+    assert_eq!(iter.next(), None);
+
+    let mut iter = slice.group_by(|a, b| a == b);
+    assert_eq!(iter.next_back(), Some(&[0][..]));
+    assert_eq!(iter.next_back(), Some(&[1][..]));
+    assert_eq!(iter.next_back(), Some(&[2, 2, 2][..]));
+    assert_eq!(iter.next_back(), Some(&[3, 3][..]));
+    assert_eq!(iter.next_back(), Some(&[1, 1, 1][..]));
+    assert_eq!(iter.next_back(), None);
+
+    let mut iter = slice.group_by(|a, b| a == b);
+    assert_eq!(iter.next(), Some(&[1, 1, 1][..]));
+    assert_eq!(iter.next_back(), Some(&[0][..]));
+    assert_eq!(iter.next(), Some(&[3, 3][..]));
+    assert_eq!(iter.next_back(), Some(&[1][..]));
+    assert_eq!(iter.next(), Some(&[2, 2, 2][..]));
+    assert_eq!(iter.next_back(), None);
+}
+
+#[test]
+fn test_group_by_mut() {
+    let slice = &mut [1, 1, 1, 3, 3, 2, 2, 2, 1, 0];
+
+    let mut iter = slice.group_by_mut(|a, b| a == b);
+    assert_eq!(iter.next(), Some(&mut [1, 1, 1][..]));
+    assert_eq!(iter.next(), Some(&mut [3, 3][..]));
+    assert_eq!(iter.next(), Some(&mut [2, 2, 2][..]));
+    assert_eq!(iter.next(), Some(&mut [1][..]));
+    assert_eq!(iter.next(), Some(&mut [0][..]));
+    assert_eq!(iter.next(), None);
+
+    let mut iter = slice.group_by_mut(|a, b| a == b);
+    assert_eq!(iter.next_back(), Some(&mut [0][..]));
+    assert_eq!(iter.next_back(), Some(&mut [1][..]));
+    assert_eq!(iter.next_back(), Some(&mut [2, 2, 2][..]));
+    assert_eq!(iter.next_back(), Some(&mut [3, 3][..]));
+    assert_eq!(iter.next_back(), Some(&mut [1, 1, 1][..]));
+    assert_eq!(iter.next_back(), None);
+
+    let mut iter = slice.group_by_mut(|a, b| a == b);
+    assert_eq!(iter.next(), Some(&mut [1, 1, 1][..]));
+    assert_eq!(iter.next_back(), Some(&mut [0][..]));
+    assert_eq!(iter.next(), Some(&mut [3, 3][..]));
+    assert_eq!(iter.next_back(), Some(&mut [1][..]));
+    assert_eq!(iter.next(), Some(&mut [2, 2, 2][..]));
+    assert_eq!(iter.next_back(), None);
+}