Deprecate MaybeOwned[Vector] in favor of Cow

4 files changed, 104 insertions, 28 deletions

diff --git a/src/libcollections/hash/mod.rs b/src/libcollections/hash/mod.rs
index b1ff3da947b..4173ffc5d2f 100644
--- a/src/libcollections/hash/mod.rs
+++ b/src/libcollections/hash/mod.rs
@@ -67,6 +67,7 @@ use core::prelude::*;
 
 use alloc::boxed::Box;
 use alloc::rc::Rc;
+use core::borrow::{Cow, ToOwned};
 use core::intrinsics::TypeId;
 use core::mem;
 use core::num::Int;
@@ -284,6 +285,13 @@ impl<S: Writer, T: Hash<S>, U: Hash<S>> Hash<S> for Result<T, U> {
     }
 }
 
+impl<'a, T, Sized? B, S> Hash<S> for Cow<'a, T, B> where B: Hash<S> + ToOwned<T> {
+    #[inline]
+    fn hash(&self, state: &mut S) {
+        Hash::hash(&**self, state)
+    }
+}
+
 //////////////////////////////////////////////////////////////////////////////
 
 #[cfg(test)]
diff --git a/src/libcollections/str.rs b/src/libcollections/str.rs
index 9982eaefff8..7b53fead6b2 100644
--- a/src/libcollections/str.rs
+++ b/src/libcollections/str.rs
@@ -54,7 +54,7 @@
 pub use self::MaybeOwned::*;
 use self::RecompositionState::*;
 use self::DecompositionType::*;
-use core::borrow::{BorrowFrom, ToOwned};
+use core::borrow::{BorrowFrom, Cow, ToOwned};
 use core::default::Default;
 use core::fmt;
 use core::cmp;
@@ -67,7 +67,7 @@ use core::prelude::{range};
 
 use hash;
 use ring_buf::RingBuf;
-use string::{String, ToString};
+use string::String;
 use unicode;
 use vec::Vec;
 
@@ -425,6 +425,7 @@ Section: MaybeOwned
 /// A string type that can hold either a `String` or a `&str`.
 /// This can be useful as an optimization when an allocation is sometimes
 /// needed but not always.
+#[deprecated = "use std::str::CowString"]
 pub enum MaybeOwned<'a> {
     /// A borrowed string.
     Slice(&'a str),
@@ -432,15 +433,16 @@ pub enum MaybeOwned<'a> {
     Owned(String)
 }
 
-/// A specialization of `MaybeOwned` to be sendable.
-pub type SendStr = MaybeOwned<'static>;
+/// A specialization of `CowString` to be sendable.
+pub type SendStr = CowString<'static>;
 
+#[deprecated = "use std::str::CowString"]
 impl<'a> MaybeOwned<'a> {
     /// Returns `true` if this `MaybeOwned` wraps an owned string.
     ///
     /// # Example
     ///
-    /// ```rust
+    /// ``` ignore
     /// let string = String::from_str("orange");
     /// let maybe_owned_string = string.into_maybe_owned();
     /// assert_eq!(true, maybe_owned_string.is_owned());
@@ -457,7 +459,7 @@ impl<'a> MaybeOwned<'a> {
     ///
     /// # Example
     ///
-    /// ```rust
+    /// ``` ignore
     /// let string = "orange";
     /// let maybe_owned_string = string.as_slice().into_maybe_owned();
     /// assert_eq!(true, maybe_owned_string.is_slice());
@@ -475,46 +477,56 @@ impl<'a> MaybeOwned<'a> {
     pub fn len(&self) -> uint { self.as_slice().len() }
 
     /// Returns true if the string contains no bytes
+    #[allow(deprecated)]
     #[inline]
     pub fn is_empty(&self) -> bool { self.len() == 0 }
 }
 
+#[deprecated = "use std::borrow::IntoCow"]
 /// Trait for moving into a `MaybeOwned`.
 pub trait IntoMaybeOwned<'a> {
     /// Moves `self` into a `MaybeOwned`.
     fn into_maybe_owned(self) -> MaybeOwned<'a>;
 }
 
+#[deprecated = "use std::borrow::IntoCow"]
+#[allow(deprecated)]
 impl<'a> IntoMaybeOwned<'a> for String {
     /// # Example
     ///
-    /// ```rust
+    /// ``` ignore
     /// let owned_string = String::from_str("orange");
     /// let maybe_owned_string = owned_string.into_maybe_owned();
     /// assert_eq!(true, maybe_owned_string.is_owned());
     /// ```
+    #[allow(deprecated)]
     #[inline]
     fn into_maybe_owned(self) -> MaybeOwned<'a> {
         Owned(self)
     }
 }
 
+#[deprecated = "use std::borrow::IntoCow"]
+#[allow(deprecated)]
 impl<'a> IntoMaybeOwned<'a> for &'a str {
     /// # Example
     ///
-    /// ```rust
+    /// ``` ignore
     /// let string = "orange";
     /// let maybe_owned_str = string.as_slice().into_maybe_owned();
     /// assert_eq!(false, maybe_owned_str.is_owned());
     /// ```
+    #[allow(deprecated)]
     #[inline]
     fn into_maybe_owned(self) -> MaybeOwned<'a> { Slice(self) }
 }
 
+#[allow(deprecated)]
+#[deprecated = "use std::borrow::IntoCow"]
 impl<'a> IntoMaybeOwned<'a> for MaybeOwned<'a> {
     /// # Example
     ///
-    /// ```rust
+    /// ``` ignore
     /// let str = "orange";
     /// let maybe_owned_str = str.as_slice().into_maybe_owned();
     /// let maybe_maybe_owned_str = maybe_owned_str.into_maybe_owned();
@@ -524,6 +536,7 @@ impl<'a> IntoMaybeOwned<'a> for MaybeOwned<'a> {
     fn into_maybe_owned(self) -> MaybeOwned<'a> { self }
 }
 
+#[deprecated = "use std::str::CowString"]
 impl<'a> PartialEq for MaybeOwned<'a> {
     #[inline]
     fn eq(&self, other: &MaybeOwned) -> bool {
@@ -531,8 +544,10 @@ impl<'a> PartialEq for MaybeOwned<'a> {
     }
 }
 
+#[deprecated = "use std::str::CowString"]
 impl<'a> Eq for MaybeOwned<'a> {}
 
+#[deprecated = "use std::str::CowString"]
 impl<'a> PartialOrd for MaybeOwned<'a> {
     #[inline]
     fn partial_cmp(&self, other: &MaybeOwned) -> Option<Ordering> {
@@ -540,6 +555,7 @@ impl<'a> PartialOrd for MaybeOwned<'a> {
     }
 }
 
+#[deprecated = "use std::str::CowString"]
 impl<'a> Ord for MaybeOwned<'a> {
     #[inline]
     fn cmp(&self, other: &MaybeOwned) -> Ordering {
@@ -547,6 +563,7 @@ impl<'a> Ord for MaybeOwned<'a> {
     }
 }
 
+#[deprecated = "use std::str::CowString"]
 impl<'a, S: Str> Equiv<S> for MaybeOwned<'a> {
     #[inline]
     fn equiv(&self, other: &S) -> bool {
@@ -554,7 +571,9 @@ impl<'a, S: Str> Equiv<S> for MaybeOwned<'a> {
     }
 }
 
+#[deprecated = "use std::str::CowString"]
 impl<'a> Str for MaybeOwned<'a> {
+    #[allow(deprecated)]
     #[inline]
     fn as_slice<'b>(&'b self) -> &'b str {
         match *self {
@@ -564,7 +583,9 @@ impl<'a> Str for MaybeOwned<'a> {
     }
 }
 
+#[deprecated = "use std::str::CowString"]
 impl<'a> StrAllocating for MaybeOwned<'a> {
+    #[allow(deprecated)]
     #[inline]
     fn into_string(self) -> String {
         match self {
@@ -574,7 +595,9 @@ impl<'a> StrAllocating for MaybeOwned<'a> {
     }
 }
 
+#[deprecated = "use std::str::CowString"]
 impl<'a> Clone for MaybeOwned<'a> {
+    #[allow(deprecated)]
     #[inline]
     fn clone(&self) -> MaybeOwned<'a> {
         match *self {
@@ -584,11 +607,14 @@ impl<'a> Clone for MaybeOwned<'a> {
     }
 }
 
+#[deprecated = "use std::str::CowString"]
 impl<'a> Default for MaybeOwned<'a> {
+    #[allow(deprecated)]
     #[inline]
     fn default() -> MaybeOwned<'a> { Slice("") }
 }
 
+#[deprecated = "use std::str::CowString"]
 impl<'a, H: hash::Writer> hash::Hash<H> for MaybeOwned<'a> {
     #[inline]
     fn hash(&self, hasher: &mut H) {
@@ -596,6 +622,7 @@ impl<'a, H: hash::Writer> hash::Hash<H> for MaybeOwned<'a> {
     }
 }
 
+#[deprecated = "use std::str::CowString"]
 impl<'a> fmt::Show for MaybeOwned<'a> {
     #[inline]
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
@@ -613,7 +640,7 @@ impl BorrowFrom<String> for str {
 
 #[unstable = "trait is unstable"]
 impl ToOwned<String> for str {
-    fn to_owned(&self) -> String { self.to_string() }
+    fn to_owned(&self) -> String { self.into_string() }
 }
 
 /// Unsafe string operations.
@@ -623,6 +650,13 @@ pub mod raw {
 }
 
 /*
+Section: CowString
+*/
+
+/// A clone-on-write string
+pub type CowString<'a> = Cow<'a, String, str>;
+
+/*
 Section: Trait implementations
 */
 
diff --git a/src/libcollections/string.rs b/src/libcollections/string.rs
index dd9dad9a42f..38b67fbd744 100644
--- a/src/libcollections/string.rs
+++ b/src/libcollections/string.rs
@@ -14,6 +14,7 @@
 
 use core::prelude::*;
 
+use core::borrow::{Cow, IntoCow};
 use core::default::Default;
 use core::fmt;
 use core::mem;
@@ -25,8 +26,7 @@ use core::raw::Slice as RawSlice;
 use hash;
 use slice::CloneSliceAllocPrelude;
 use str;
-use str::{CharRange, FromStr, StrAllocating, MaybeOwned, Owned};
-use str::Slice as MaybeOwnedSlice; // So many `Slice`s...
+use str::{CharRange, CowString, FromStr, StrAllocating, Owned};
 use vec::{DerefVec, Vec, as_vec};
 
 /// A growable string stored as a UTF-8 encoded buffer.
@@ -121,9 +121,9 @@ impl String {
     /// assert_eq!(output.as_slice(), "Hello \uFFFDWorld");
     /// ```
     #[unstable = "return type may change"]
-    pub fn from_utf8_lossy<'a>(v: &'a [u8]) -> MaybeOwned<'a> {
+    pub fn from_utf8_lossy<'a>(v: &'a [u8]) -> CowString<'a> {
         if str::is_utf8(v) {
-            return MaybeOwnedSlice(unsafe { mem::transmute(v) })
+            return Cow::Borrowed(unsafe { mem::transmute(v) })
         }
 
         static TAG_CONT_U8: u8 = 128u8;
@@ -234,7 +234,7 @@ impl String {
                 res.as_mut_vec().push_all(v[subseqidx..total])
             };
         }
-        Owned(res.into_string())
+        Cow::Owned(res.into_string())
     }
 
     /// Decode a UTF-16 encoded vector `v` into a `String`, returning `None`
@@ -868,6 +868,18 @@ impl<T: fmt::Show> ToString for T {
     }
 }
 
+impl IntoCow<'static, String, str> for String {
+    fn into_cow(self) -> CowString<'static> {
+        Cow::Owned(self)
+    }
+}
+
+impl<'a> IntoCow<'a, String, str> for &'a str {
+    fn into_cow(self) -> CowString<'a> {
+        Cow::Borrowed(self)
+    }
+}
+
 /// Unsafe operations
 #[deprecated]
 pub mod raw {
@@ -921,11 +933,11 @@ mod tests {
     use std::prelude::*;
     use test::Bencher;
 
+    use slice::CloneSliceAllocPrelude;
+    use str::{Str, StrPrelude};
     use str;
-    use str::{Str, StrPrelude, Owned};
     use super::{as_string, String, ToString};
     use vec::Vec;
-    use slice::CloneSliceAllocPrelude;
 
     #[test]
     fn test_as_string() {
@@ -955,39 +967,39 @@ mod tests {
     #[test]
     fn test_from_utf8_lossy() {
         let xs = b"hello";
-        assert_eq!(String::from_utf8_lossy(xs), str::Slice("hello"));
+        assert_eq!(String::from_utf8_lossy(xs), "hello".into_cow());
 
         let xs = "ศไทย中华Việt Nam".as_bytes();
-        assert_eq!(String::from_utf8_lossy(xs), str::Slice("ศไทย中华Việt Nam"));
+        assert_eq!(String::from_utf8_lossy(xs), "ศไทย中华Việt Nam".into_cow());
 
         let xs = b"Hello\xC2 There\xFF Goodbye";
         assert_eq!(String::from_utf8_lossy(xs),
-                   Owned(String::from_str("Hello\uFFFD There\uFFFD Goodbye")));
+                   String::from_str("Hello\uFFFD There\uFFFD Goodbye").into_cow());
 
         let xs = b"Hello\xC0\x80 There\xE6\x83 Goodbye";
         assert_eq!(String::from_utf8_lossy(xs),
-                   Owned(String::from_str("Hello\uFFFD\uFFFD There\uFFFD Goodbye")));
+                   String::from_str("Hello\uFFFD\uFFFD There\uFFFD Goodbye").into_cow());
 
         let xs = b"\xF5foo\xF5\x80bar";
         assert_eq!(String::from_utf8_lossy(xs),
-                   Owned(String::from_str("\uFFFDfoo\uFFFD\uFFFDbar")));
+                   String::from_str("\uFFFDfoo\uFFFD\uFFFDbar").into_cow());
 
         let xs = b"\xF1foo\xF1\x80bar\xF1\x80\x80baz";
         assert_eq!(String::from_utf8_lossy(xs),
-                   Owned(String::from_str("\uFFFDfoo\uFFFDbar\uFFFDbaz")));
+                   String::from_str("\uFFFDfoo\uFFFDbar\uFFFDbaz").into_cow());
 
         let xs = b"\xF4foo\xF4\x80bar\xF4\xBFbaz";
         assert_eq!(String::from_utf8_lossy(xs),
-                   Owned(String::from_str("\uFFFDfoo\uFFFDbar\uFFFD\uFFFDbaz")));
+                   String::from_str("\uFFFDfoo\uFFFDbar\uFFFD\uFFFDbaz").into_cow());
 
         let xs = b"\xF0\x80\x80\x80foo\xF0\x90\x80\x80bar";
-        assert_eq!(String::from_utf8_lossy(xs), Owned(String::from_str("\uFFFD\uFFFD\uFFFD\uFFFD\
-                                               foo\U00010000bar")));
+        assert_eq!(String::from_utf8_lossy(xs), String::from_str("\uFFFD\uFFFD\uFFFD\uFFFD\
+                                               foo\U00010000bar").into_cow());
 
         // surrogates
         let xs = b"\xED\xA0\x80foo\xED\xBF\xBFbar";
-        assert_eq!(String::from_utf8_lossy(xs), Owned(String::from_str("\uFFFD\uFFFD\uFFFDfoo\
-                                               \uFFFD\uFFFD\uFFFDbar")));
+        assert_eq!(String::from_utf8_lossy(xs), String::from_str("\uFFFD\uFFFD\uFFFDfoo\
+                                               \uFFFD\uFFFD\uFFFDbar").into_cow());
     }
 
     #[test]
diff --git a/src/libcollections/vec.rs b/src/libcollections/vec.rs
index a3291e01942..ec520a93c1e 100644
--- a/src/libcollections/vec.rs
+++ b/src/libcollections/vec.rs
@@ -16,6 +16,7 @@ use core::prelude::*;
 
 use alloc::boxed::Box;
 use alloc::heap::{EMPTY, allocate, reallocate, deallocate};
+use core::borrow::{Cow, IntoCow};
 use core::cmp::max;
 use core::default::Default;
 use core::fmt;
@@ -107,6 +108,27 @@ pub struct Vec<T> {
     cap: uint,
 }
 
+/// A clone-on-write vector
+pub type CowVec<'a, T> = Cow<'a, Vec<T>, [T]>;
+
+impl<'a, T> FromIterator<T> for CowVec<'a, T> where T: Clone {
+    fn from_iter<I: Iterator<T>>(it: I) -> CowVec<'a, T> {
+        Cow::Owned(FromIterator::from_iter(it))
+    }
+}
+
+impl<'a, T: 'a> IntoCow<'a, Vec<T>, [T]> for Vec<T> where T: Clone {
+    fn into_cow(self) -> CowVec<'a, T> {
+        Cow::Owned(self)
+    }
+}
+
+impl<'a, T> IntoCow<'a, Vec<T>, [T]> for &'a [T] where T: Clone {
+    fn into_cow(self) -> CowVec<'a, T> {
+        Cow::Borrowed(self)
+    }
+}
+
 impl<T> Vec<T> {
     /// Constructs a new, empty `Vec`.
     ///