Auto merge of #79015 - WaffleLapkin:vec_append_from_within, r=KodrAus

add `Vec::extend_from_within` method under `vec_extend_from_within` feature gate

Implement <https://github.com/rust-lang/rfcs/pull/2714>

### tl;dr

This PR adds a `extend_from_within` method to `Vec` which allows copying elements from a range to the end:

```rust
#![feature(vec_extend_from_within)]

let mut vec = vec![0, 1, 2, 3, 4];

vec.extend_from_within(2..);
assert_eq!(vec, [0, 1, 2, 3, 4, 2, 3, 4]);

vec.extend_from_within(..2);
assert_eq!(vec, [0, 1, 2, 3, 4, 2, 3, 4, 0, 1]);

vec.extend_from_within(4..8);
assert_eq!(vec, [0, 1, 2, 3, 4, 2, 3, 4, 0, 1, 4, 2, 3, 4]);
```

### Implementation notes

Originally I've copied `@Shnatsel's` [implementation](https://github.com/WanzenBug/rle-decode-helper/blob/690742a0de158d391b7bde1a0c71cccfdad33ab3/src/lib.rs#L74) with some minor changes to support other ranges:
```rust
pub fn append_from_within<R>(&mut self, src: R)
where
    T: Copy,
    R: RangeBounds<usize>,
{
    let len = self.len();
    let Range { start, end } = src.assert_len(len);;

    let count = end - start;
    self.reserve(count);
    unsafe {
        // This is safe because `reserve()` above succeeded,
        // so `self.len() + count` did not overflow usize
        ptr::copy_nonoverlapping(
            self.get_unchecked(src.start),
            self.as_mut_ptr().add(len),
            count,
        );
        self.set_len(len + count);
    }
}
```

But then I've realized that this duplicates most of the code from (private) `Vec::append_elements`, so I've used it instead.

Then I've applied `@KodrAus` suggestions from https://github.com/rust-lang/rust/pull/79015#issuecomment-727200852.

1 files changed, 109 insertions, 4 deletions

diff --git a/library/alloc/src/vec/mod.rs b/library/alloc/src/vec/mod.rs
index 9aea19f04c6..ede1601fa33 100644
--- a/library/alloc/src/vec/mod.rs
+++ b/library/alloc/src/vec/mod.rs
@@ -1825,11 +1825,27 @@ impl<T, A: Allocator> Vec<T, A> {
     #[unstable(feature = "vec_spare_capacity", issue = "75017")]
     #[inline]
     pub fn spare_capacity_mut(&mut self) -> &mut [MaybeUninit<T>] {
+        self.split_at_spare_mut().1
+    }
+
+    #[inline]
+    fn split_at_spare_mut(&mut self) -> (&mut [T], &mut [MaybeUninit<T>]) {
+        let ptr = self.as_mut_ptr();
+
+        // Safety:
+        // - `ptr` is guaranteed to be in bounds for `capacity` elements
+        // - `len` is guaranteed to less or equal to `capacity`
+        // - `MaybeUninit<T>` has the same layout as `T`
+        let spare_ptr = unsafe { ptr.cast::<MaybeUninit<T>>().add(self.len) };
+
+        // Safety:
+        // - `ptr` is guaranteed to be valid for `len` elements
+        // - `spare_ptr` is offseted from `ptr` by `len`, so it doesn't overlap `initialized` slice
         unsafe {
-            slice::from_raw_parts_mut(
-                self.as_mut_ptr().add(self.len) as *mut MaybeUninit<T>,
-                self.buf.capacity() - self.len,
-            )
+            let initialized = slice::from_raw_parts_mut(ptr, self.len);
+            let spare = slice::from_raw_parts_mut(spare_ptr, self.buf.capacity() - self.len);
+
+            (initialized, spare)
         }
     }
 }
@@ -1891,6 +1907,39 @@ impl<T: Clone, A: Allocator> Vec<T, A> {
     pub fn extend_from_slice(&mut self, other: &[T]) {
         self.spec_extend(other.iter())
     }
+
+    /// Copies elements from `src` range to the end of the vector.
+    ///
+    /// ## Examples
+    ///
+    /// ```
+    /// #![feature(vec_extend_from_within)]
+    ///
+    /// let mut vec = vec![0, 1, 2, 3, 4];
+    ///
+    /// vec.extend_from_within(2..);
+    /// assert_eq!(vec, [0, 1, 2, 3, 4, 2, 3, 4]);
+    ///
+    /// vec.extend_from_within(..2);
+    /// assert_eq!(vec, [0, 1, 2, 3, 4, 2, 3, 4, 0, 1]);
+    ///
+    /// vec.extend_from_within(4..8);
+    /// assert_eq!(vec, [0, 1, 2, 3, 4, 2, 3, 4, 0, 1, 4, 2, 3, 4]);
+    /// ```
+    #[unstable(feature = "vec_extend_from_within", issue = "81656")]
+    pub fn extend_from_within<R>(&mut self, src: R)
+    where
+        R: RangeBounds<usize>,
+    {
+        let range = src.assert_len(self.len());
+        self.reserve(range.len());
+
+        // SAFETY:
+        // - `assert_len` guarantees  that the given range is valid for indexing self
+        unsafe {
+            self.spec_extend_from_within(range);
+        }
+    }
 }
 
 // This code generalizes `extend_with_{element,default}`.
@@ -1998,6 +2047,62 @@ pub fn from_elem_in<T: Clone, A: Allocator>(elem: T, n: usize, alloc: A) -> Vec<
     <T as SpecFromElem>::from_elem(elem, n, alloc)
 }
 
+trait ExtendFromWithinSpec {
+    /// Safety:
+    /// - `src` needs to be valid index
+    /// - `self.capacity() - self.len()` must be `>= src.len()`
+    unsafe fn spec_extend_from_within(&mut self, src: Range<usize>);
+}
+
+impl<T: Clone, A: Allocator> ExtendFromWithinSpec for Vec<T, A> {
+    default unsafe fn spec_extend_from_within(&mut self, src: Range<usize>) {
+        let initialized = {
+            let (this, spare) = self.split_at_spare_mut();
+
+            // Safety:
+            // - caller guaratees that src is a valid index
+            let to_clone = unsafe { this.get_unchecked(src) };
+
+            to_clone.iter().cloned().zip(spare.iter_mut()).map(|(e, s)| s.write(e)).count()
+        };
+
+        // Safety:
+        // - elements were just initialized
+        unsafe {
+            let new_len = self.len() + initialized;
+            self.set_len(new_len);
+        }
+    }
+}
+
+impl<T: Copy, A: Allocator> ExtendFromWithinSpec for Vec<T, A> {
+    unsafe fn spec_extend_from_within(&mut self, src: Range<usize>) {
+        let count = src.len();
+        {
+            let (init, spare) = self.split_at_spare_mut();
+
+            // Safety:
+            // - caller guaratees that `src` is a valid index
+            let source = unsafe { init.get_unchecked(src) };
+
+            // Safety:
+            // - Both pointers are created from unique slice references (`&mut [_]`)
+            //   so they are valid and do not overlap.
+            // - Elements are :Copy so it's OK to to copy them, without doing
+            //   anything with the original values
+            // - `count` is equal to the len of `source`, so source is valid for
+            //   `count` reads
+            // - `.reserve(count)` guarantees that `spare.len() >= count` so spare
+            //   is valid for `count` writes
+            unsafe { ptr::copy_nonoverlapping(source.as_ptr(), spare.as_mut_ptr() as _, count) };
+        }
+
+        // Safety:
+        // - The elements were just initialized by `copy_nonoverlapping`
+        self.len += count;
+    }
+}
+
 ////////////////////////////////////////////////////////////////////////////////
 // Common trait implementations for Vec
 ////////////////////////////////////////////////////////////////////////////////