Add Vec::splice and String::splice

6 files changed, 313 insertions, 7 deletions

diff --git a/src/libcollections/slice.rs b/src/libcollections/slice.rs
index 7c3c825cfd1..2eef132374e 100644
--- a/src/libcollections/slice.rs
+++ b/src/libcollections/slice.rs
@@ -1519,13 +1519,9 @@ impl<T: Clone> ToOwned for [T] {
         self.to_vec()
     }
 
-    // HACK(japaric): with cfg(test) the inherent `[T]::to_vec`, which is required for this method
-    // definition, is not available. Since we don't require this method for testing purposes, I'll
-    // just stub it
-    // NB see the slice::hack module in slice.rs for more information
     #[cfg(test)]
     fn to_owned(&self) -> Vec<T> {
-        panic!("not available with cfg(test)")
+        hack::to_vec(self)
     }
 
     fn clone_into(&self, target: &mut Vec<T>) {
diff --git a/src/libcollections/string.rs b/src/libcollections/string.rs
index 8d6cf305112..8090bc1996e 100644
--- a/src/libcollections/string.rs
+++ b/src/libcollections/string.rs
@@ -1316,7 +1316,7 @@ impl String {
         self.vec.clear()
     }
 
-    /// Create a draining iterator that removes the specified range in the string
+    /// Creates a draining iterator that removes the specified range in the string
     /// and yields the removed chars.
     ///
     /// Note: The element range is removed even if the iterator is not
@@ -1382,6 +1382,63 @@ impl String {
         }
     }
 
+    /// Creates a splicing iterator that removes the specified range in the string,
+    /// replaces with the given string, and yields the removed chars.
+    /// The given string doesn’t need to be the same length as the range.
+    ///
+    /// Note: The element range is removed even if the iterator is not
+    /// consumed until the end.
+    ///
+    /// # Panics
+    ///
+    /// Panics if the starting point or end point do not lie on a [`char`]
+    /// boundary, or if they're out of bounds.
+    ///
+    /// [`char`]: ../../std/primitive.char.html
+    ///
+    /// # Examples
+    ///
+    /// Basic usage:
+    ///
+    /// ```
+    /// #![feature(splice)]
+    /// let mut s = String::from("α is alpha, β is beta");
+    /// let beta_offset = s.find('β').unwrap_or(s.len());
+    ///
+    /// // Replace the range up until the β from the string
+    /// let t: String = s.splice(..beta_offset, "Α is capital alpha; ").collect();
+    /// assert_eq!(t, "α is alpha, ");
+    /// assert_eq!(s, "Α is capital alpha; β is beta");
+    /// ```
+    #[unstable(feature = "splice", reason = "recently added", issue = "32310")]
+    pub fn splice<'a, 'b, R>(&'a mut self, range: R, replace_with: &'b str) -> Splice<'a, 'b>
+        where R: RangeArgument<usize>
+    {
+        // Memory safety
+        //
+        // The String version of Splice does not have the memory safety issues
+        // of the vector version. The data is just plain bytes.
+        // Because the range removal happens in Drop, if the Splice iterator is leaked,
+        // the removal will not happen.
+        let len = self.len();
+        let start = *range.start().unwrap_or(&0);
+        let end = *range.end().unwrap_or(&len);
+
+        // Take out two simultaneous borrows. The &mut String won't be accessed
+        // until iteration is over, in Drop.
+        let self_ptr = self as *mut _;
+        // slicing does the appropriate bounds checks
+        let chars_iter = self[start..end].chars();
+
+        Splice {
+            start: start,
+            end: end,
+            iter: chars_iter,
+            string: self_ptr,
+            replace_with: replace_with
+        }
+    }
+
     /// Converts this `String` into a `Box<str>`.
     ///
     /// This will drop any excess capacity.
@@ -2145,3 +2202,74 @@ impl<'a> DoubleEndedIterator for Drain<'a> {
 
 #[unstable(feature = "fused", issue = "35602")]
 impl<'a> FusedIterator for Drain<'a> {}
+
+/// A splicing iterator for `String`.
+///
+/// This struct is created by the [`splice()`] method on [`String`]. See its
+/// documentation for more.
+///
+/// [`splice()`]: struct.String.html#method.splice
+/// [`String`]: struct.String.html
+#[unstable(feature = "splice", reason = "recently added", issue = "32310")]
+pub struct Splice<'a, 'b> {
+    /// Will be used as &'a mut String in the destructor
+    string: *mut String,
+    /// Start of part to remove
+    start: usize,
+    /// End of part to remove
+    end: usize,
+    /// Current remaining range to remove
+    iter: Chars<'a>,
+    replace_with: &'b str,
+}
+
+#[unstable(feature = "splice", reason = "recently added", issue = "32310")]
+unsafe impl<'a, 'b> Sync for Splice<'a, 'b> {}
+#[unstable(feature = "splice", reason = "recently added", issue = "32310")]
+unsafe impl<'a, 'b> Send for Splice<'a, 'b> {}
+
+#[unstable(feature = "splice", reason = "recently added", issue = "32310")]
+impl<'a, 'b> Drop for Splice<'a, 'b> {
+    fn drop(&mut self) {
+        unsafe {
+            let vec = (*self.string).as_mut_vec();
+            let range_len = self.end - self.start;
+            let replacement_len = self.replace_with.len();
+            let tail_len = vec.len() - self.end;
+            if replacement_len > range_len {
+                vec.reserve(replacement_len - range_len);
+            }
+            if replacement_len != range_len {
+                let src = vec.as_ptr().offset(self.end as isize);
+                let dst = vec.as_mut_ptr().offset((self.start + replacement_len) as isize);
+                ptr::copy(src, dst, tail_len);
+            }
+            let src = self.replace_with.as_ptr();
+            let dst = vec.as_mut_ptr().offset(self.start as isize);
+            ptr::copy(src, dst, replacement_len);
+            vec.set_len(self.start + replacement_len + tail_len);
+        }
+    }
+}
+
+#[unstable(feature = "splice", reason = "recently added", issue = "32310")]
+impl<'a, 'b> Iterator for Splice<'a, 'b> {
+    type Item = char;
+
+    #[inline]
+    fn next(&mut self) -> Option<char> {
+        self.iter.next()
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.iter.size_hint()
+    }
+}
+
+#[unstable(feature = "splice", reason = "recently added", issue = "32310")]
+impl<'a, 'b> DoubleEndedIterator for Splice<'a, 'b> {
+    #[inline]
+    fn next_back(&mut self) -> Option<char> {
+        self.iter.next_back()
+    }
+}
diff --git a/src/libcollections/tests/lib.rs b/src/libcollections/tests/lib.rs
index 9c6e31d70a5..eae3bf3915f 100644
--- a/src/libcollections/tests/lib.rs
+++ b/src/libcollections/tests/lib.rs
@@ -20,6 +20,7 @@
 #![feature(pattern)]
 #![feature(placement_in_syntax)]
 #![feature(rand)]
+#![feature(splice)]
 #![feature(step_by)]
 #![feature(str_escape)]
 #![feature(test)]
diff --git a/src/libcollections/tests/string.rs b/src/libcollections/tests/string.rs
index 2f021b9935d..faaa9a1830b 100644
--- a/src/libcollections/tests/string.rs
+++ b/src/libcollections/tests/string.rs
@@ -420,6 +420,14 @@ fn test_drain() {
 }
 
 #[test]
+fn test_splice() {
+    let mut s = "Hello, world!".to_owned();
+    let t: String = s.splice(7..12, "世界").collect();
+    assert_eq!(s, "Hello, 世界!");
+    assert_eq!(t, "world");
+}
+
+#[test]
 fn test_extend_ref() {
     let mut a = "foo".to_string();
     a.extend(&['b', 'a', 'r']);
diff --git a/src/libcollections/tests/vec.rs b/src/libcollections/tests/vec.rs
index 64c76142b59..e3453c70aba 100644
--- a/src/libcollections/tests/vec.rs
+++ b/src/libcollections/tests/vec.rs
@@ -580,6 +580,16 @@ fn test_drain_inclusive_out_of_bounds() {
 }
 
 #[test]
+fn splice() {
+    let mut v = vec![1, 2, 3, 4, 5];
+    let a = [10, 11, 12];
+    v.splice(2..4, a.iter().cloned());
+    assert_eq!(v, &[1, 2, 10, 11, 12, 5]);
+    v.splice(1..3, Some(20));
+    assert_eq!(v, &[1, 20, 11, 12, 5]);
+}
+
+#[test]
 fn test_into_boxed_slice() {
     let xs = vec![1, 2, 3];
     let ys = xs.into_boxed_slice();
diff --git a/src/libcollections/vec.rs b/src/libcollections/vec.rs
index 6deb87ae772..bbb067ca4e3 100644
--- a/src/libcollections/vec.rs
+++ b/src/libcollections/vec.rs
@@ -1057,7 +1057,7 @@ 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
@@ -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,118 @@ impl<'a, T> InPlace<T> for PlaceBack<'a, T> {
         &mut *ptr
     }
 }
+
+
+/// A splicing iterator for `Vec<T>`. See the [`Vec::splice`](struct.Vec.html#method.splice) method.
+#[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;
+                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;
+        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;
+        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;
+    }
+}