1 files changed, 172 insertions, 2 deletions
diff --git a/src/libcollections/vec.rs b/src/libcollections/vec.rs
index 6deb87ae772..e5964385b12 100644
--- a/src/libcollections/vec.rs
+++ b/src/libcollections/vec.rs
@@ -1057,13 +1057,13 @@ impl<T> Vec<T> {
         self.len += count;
     }
 
-    /// Create a draining iterator that removes the specified range in the vector
+    /// Creates a draining iterator that removes the specified range in the vector
     /// and yields the removed items.
     ///
     /// Note 1: The element range is removed even if the iterator is only
     /// partially consumed or not consumed at all.
     ///
-    /// Note 2: It is unspecified how many elements are removed from the vector,
+    /// Note 2: It is unspecified how many elements are removed from the vector
     /// if the `Drain` value is leaked.
     ///
     /// # Panics
@@ -1845,6 +1845,54 @@ impl<T> Vec<T> {
             }
         }
     }
+
+    /// Creates a splicing iterator that replaces the specified range in the vector
+    /// with the given `replace_with` iterator and yields the removed items.
+    /// `replace_with` does not need to be the same length as `range`.
+    ///
+    /// Note 1: The element range is removed even if the iterator is not
+    /// consumed until the end.
+    ///
+    /// Note 2: It is unspecified how many elements are removed from the vector,
+    /// if the `Splice` value is leaked.
+    ///
+    /// Note 3: The input iterator `replace_with` is only consumed
+    /// when the `Splice` value is dropped.
+    ///
+    /// Note 4: This is optimal if:
+    ///
+    /// * The tail (elements in the vector after `range`) is empty,
+    /// * or `replace_with` yields fewer elements than `range`’s length
+    /// * or the lower bound of its `size_hint()` is exact.
+    ///
+    /// Otherwise, a temporary vector is allocated and the tail is moved twice.
+    ///
+    /// # Panics
+    ///
+    /// Panics if the starting point is greater than the end point or if
+    /// the end point is greater than the length of the vector.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// #![feature(splice)]
+    /// let mut v = vec![1, 2, 3];
+    /// let new = [7, 8];
+    /// let u: Vec<_> = v.splice(..2, new.iter().cloned()).collect();
+    /// assert_eq!(v, &[7, 8, 3]);
+    /// assert_eq!(u, &[1, 2]);
+    /// ```
+    #[inline]
+    #[unstable(feature = "splice", reason = "recently added", issue = "32310")]
+    pub fn splice<R, I>(&mut self, range: R, replace_with: I) -> Splice<I::IntoIter>
+        where R: RangeArgument<usize>, I: IntoIterator<Item=T>
+    {
+        Splice {
+            drain: self.drain(range),
+            replace_with: replace_with.into_iter(),
+        }
+    }
+
 }
 
 #[stable(feature = "extend_ref", since = "1.2.0")]
@@ -2344,3 +2392,125 @@ impl<'a, T> InPlace<T> for PlaceBack<'a, T> {
         &mut *ptr
     }
 }
+
+
+/// A splicing iterator for `Vec`.
+///
+/// This struct is created by the [`splice()`] method on [`Vec`]. See its
+/// documentation for more.
+///
+/// [`splice()`]: struct.Vec.html#method.splice
+/// [`Vec`]: struct.Vec.html
+#[derive(Debug)]
+#[unstable(feature = "splice", reason = "recently added", issue = "32310")]
+pub struct Splice<'a, I: Iterator + 'a> {
+    drain: Drain<'a, I::Item>,
+    replace_with: I,
+}
+
+#[unstable(feature = "splice", reason = "recently added", issue = "32310")]
+impl<'a, I: Iterator> Iterator for Splice<'a, I> {
+    type Item = I::Item;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        self.drain.next()
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.drain.size_hint()
+    }
+}
+
+#[unstable(feature = "splice", reason = "recently added", issue = "32310")]
+impl<'a, I: Iterator> DoubleEndedIterator for Splice<'a, I> {
+    fn next_back(&mut self) -> Option<Self::Item> {
+        self.drain.next_back()
+    }
+}
+
+#[unstable(feature = "splice", reason = "recently added", issue = "32310")]
+impl<'a, I: Iterator> ExactSizeIterator for Splice<'a, I> {}
+
+
+#[unstable(feature = "splice", reason = "recently added", issue = "32310")]
+impl<'a, I: Iterator> Drop for Splice<'a, I> {
+    fn drop(&mut self) {
+        // exhaust drain first
+        while let Some(_) = self.drain.next() {}
+
+
+        unsafe {
+            if self.drain.tail_len == 0 {
+                let vec = &mut *self.drain.vec.as_mut_ptr();
+                vec.extend(self.replace_with.by_ref());
+                return
+            }
+
+            // First fill the range left by drain().
+            if !self.drain.fill(&mut self.replace_with) {
+                return
+            }
+
+            // There may be more elements. Use the lower bound as an estimate.
+            // FIXME: Is the upper bound a better guess? Or something else?
+            let (lower_bound, _upper_bound) = self.replace_with.size_hint();
+            if lower_bound > 0  {
+                self.drain.move_tail(lower_bound);
+                if !self.drain.fill(&mut self.replace_with) {
+                    return
+                }
+            }
+
+            // Collect any remaining elements.
+            // This is a zero-length vector which does not allocate if `lower_bound` was exact.
+            let mut collected = self.replace_with.by_ref().collect::<Vec<I::Item>>().into_iter();
+            // Now we have an exact count.
+            if collected.len() > 0 {
+                self.drain.move_tail(collected.len());
+                let filled = self.drain.fill(&mut collected);
+                debug_assert!(filled);
+                debug_assert_eq!(collected.len(), 0);
+            }
+        }
+        // Let `Drain::drop` move the tail back if necessary and restore `vec.len`.
+    }
+}
+
+/// Private helper methods for `Splice::drop`
+impl<'a, T> Drain<'a, T> {
+    /// The range from `self.vec.len` to `self.tail_start` contains elements
+    /// that have been moved out.
+    /// Fill that range as much as possible with new elements from the `replace_with` iterator.
+    /// Return whether we filled the entire range. (`replace_with.next()` didn’t return `None`.)
+    unsafe fn fill<I: Iterator<Item=T>>(&mut self, replace_with: &mut I) -> bool {
+        let vec = &mut *self.vec.as_mut_ptr();
+        let range_start = vec.len;
+        let range_end = self.tail_start;
+        let range_slice = slice::from_raw_parts_mut(
+            vec.as_mut_ptr().offset(range_start as isize),
+            range_end - range_start);
+
+        for place in range_slice {
+            if let Some(new_item) = replace_with.next() {
+                ptr::write(place, new_item);
+                vec.len += 1;
+            } else {
+                return false
+            }
+        }
+        true
+    }
+
+    /// Make room for inserting more elements before the tail.
+    unsafe fn move_tail(&mut self, extra_capacity: usize) {
+        let vec = &mut *self.vec.as_mut_ptr();
+        let used_capacity = self.tail_start + self.tail_len;
+        vec.buf.reserve(used_capacity, extra_capacity);
+
+        let new_tail_start = self.tail_start + extra_capacity;
+        let src = vec.as_ptr().offset(self.tail_start as isize);
+        let dst = vec.as_mut_ptr().offset(new_tail_start as isize);
+        ptr::copy(src, dst, self.tail_len);
+        self.tail_start = new_tail_start;
+    }
+}