auto merge of #18638 : aturon/rust/as_slice_dst, r=japaric

This PR changes `AsSlice` to work on unsized types, and changes the
`impl` for `&[T]` to `[T]`. Aside from making the trait more general,
this also helps some ongoing work with method resolution changes.

This is a breaking change: code that uses generics bounded by `AsSlice`
will have to change. In particular, such code previously often took
arguments of type `V` where `V: AsSlice<T>` by value. These should now
be taken by reference:

```rust
fn foo<Sized? V: AsSlice<T>>(v: &V) { .. }
```

A few std lib functions have been changed accordingly.

The PR also relaxes constraints on generics and traits within the
`core::ops` module and for the `Equiv` trait.

[breaking-change]

r? @nikomatsakis 
cc @japaric 

7 files changed, 42 insertions, 30 deletions

diff --git a/src/libcollections/slice.rs b/src/libcollections/slice.rs
index 5e341ba8b04..e077f7f6021 100644
--- a/src/libcollections/slice.rs
+++ b/src/libcollections/slice.rs
@@ -121,7 +121,7 @@ pub trait VectorVector<T> for Sized? {
     fn connect_vec(&self, sep: &T) -> Vec<T>;
 }
 
-impl<T: Clone, V: AsSlice<T>> VectorVector<T> for [V] {
+impl<'a, T: Clone, V: AsSlice<T>> VectorVector<T> for [V] {
     fn concat_vec(&self) -> Vec<T> {
         let size = self.iter().fold(0u, |acc, v| acc + v.as_slice().len());
         let mut result = Vec::with_capacity(size);
diff --git a/src/libcollections/vec.rs b/src/libcollections/vec.rs
index 7111a077630..d6a21ef19a2 100644
--- a/src/libcollections/vec.rs
+++ b/src/libcollections/vec.rs
@@ -20,6 +20,7 @@ use core::cmp::max;
 use core::default::Default;
 use core::fmt;
 use core::kinds::marker::{ContravariantLifetime, InvariantType};
+use core::kinds::Sized;
 use core::mem;
 use core::num::{Int, UnsignedInt};
 use core::ops;
@@ -516,7 +517,7 @@ impl<T: PartialOrd> PartialOrd for Vec<T> {
 impl<T: Eq> Eq for Vec<T> {}
 
 #[experimental]
-impl<T: PartialEq, V: AsSlice<T>> Equiv<V> for Vec<T> {
+impl<T: PartialEq, Sized? V: AsSlice<T>> Equiv<V> for Vec<T> {
     #[inline]
     fn equiv(&self, other: &V) -> bool { self.as_slice() == other.as_slice() }
 }
@@ -1181,7 +1182,7 @@ impl<T> AsSlice<T> for Vec<T> {
     }
 }
 
-impl<T: Clone, V: AsSlice<T>> Add<V, Vec<T>> for Vec<T> {
+impl<T: Clone, Sized? V: AsSlice<T>> Add<V, Vec<T>> for Vec<T> {
     #[inline]
     fn add(&self, rhs: &V) -> Vec<T> {
         let mut res = Vec::with_capacity(self.len() + rhs.as_slice().len());
diff --git a/src/libcore/cmp.rs b/src/libcore/cmp.rs
index 59d31a0749f..51122d0a170 100644
--- a/src/libcore/cmp.rs
+++ b/src/libcore/cmp.rs
@@ -241,7 +241,7 @@ pub trait PartialOrd for Sized?: PartialEq {
 /// container types; e.g. it is often desirable to be able to use `&str`
 /// values to look up entries in a container with `String` keys.
 #[experimental = "Better solutions may be discovered."]
-pub trait Equiv<T> for Sized? {
+pub trait Equiv<Sized? T> for Sized? {
     /// Implement this function to decide equivalent values.
     fn equiv(&self, other: &T) -> bool;
 }
diff --git a/src/libcore/ops.rs b/src/libcore/ops.rs
index b4bf5351e59..185c937eb6b 100644
--- a/src/libcore/ops.rs
+++ b/src/libcore/ops.rs
@@ -112,7 +112,7 @@ pub trait Drop {
  * ```
  */
 #[lang="add"]
-pub trait Add<RHS,Result> {
+pub trait Add<Sized? RHS,Result> for Sized? {
     /// The method for the `+` operator
     fn add(&self, rhs: &RHS) -> Result;
 }
@@ -153,7 +153,7 @@ add_impl!(uint u8 u16 u32 u64 int i8 i16 i32 i64 f32 f64)
  * ```
  */
 #[lang="sub"]
-pub trait Sub<RHS,Result> {
+pub trait Sub<Sized? RHS, Result> for Sized? {
     /// The method for the `-` operator
     fn sub(&self, rhs: &RHS) -> Result;
 }
@@ -194,7 +194,7 @@ sub_impl!(uint u8 u16 u32 u64 int i8 i16 i32 i64 f32 f64)
  * ```
  */
 #[lang="mul"]
-pub trait Mul<RHS,Result> {
+pub trait Mul<Sized? RHS, Result>  for Sized? {
     /// The method for the `*` operator
     fn mul(&self, rhs: &RHS) -> Result;
 }
@@ -235,7 +235,7 @@ mul_impl!(uint u8 u16 u32 u64 int i8 i16 i32 i64 f32 f64)
  * ```
  */
 #[lang="div"]
-pub trait Div<RHS,Result> {
+pub trait Div<Sized? RHS, Result> for Sized? {
     /// The method for the `/` operator
     fn div(&self, rhs: &RHS) -> Result;
 }
@@ -276,7 +276,7 @@ div_impl!(uint u8 u16 u32 u64 int i8 i16 i32 i64 f32 f64)
  * ```
  */
 #[lang="rem"]
-pub trait Rem<RHS,Result> {
+pub trait Rem<Sized? RHS, Result>  for Sized? {
     /// The method for the `%` operator
     fn rem(&self, rhs: &RHS) -> Result;
 }
@@ -331,7 +331,7 @@ rem_float_impl!(f64, fmod)
  * ```
  */
 #[lang="neg"]
-pub trait Neg<Result> {
+pub trait Neg<Result> for Sized? {
     /// The method for the unary `-` operator
     fn neg(&self) -> Result;
 }
@@ -388,7 +388,7 @@ neg_uint_impl!(u64, i64)
  * ```
  */
 #[lang="not"]
-pub trait Not<Result> {
+pub trait Not<Result> for Sized? {
     /// The method for the unary `!` operator
     fn not(&self) -> Result;
 }
@@ -430,7 +430,7 @@ not_impl!(bool uint u8 u16 u32 u64 int i8 i16 i32 i64)
  * ```
  */
 #[lang="bitand"]
-pub trait BitAnd<RHS,Result> {
+pub trait BitAnd<Sized? RHS, Result> for Sized? {
     /// The method for the `&` operator
     fn bitand(&self, rhs: &RHS) -> Result;
 }
@@ -471,7 +471,7 @@ bitand_impl!(bool uint u8 u16 u32 u64 int i8 i16 i32 i64)
  * ```
  */
 #[lang="bitor"]
-pub trait BitOr<RHS,Result> {
+pub trait BitOr<Sized? RHS, Result> for Sized? {
     /// The method for the `|` operator
     fn bitor(&self, rhs: &RHS) -> Result;
 }
@@ -512,7 +512,7 @@ bitor_impl!(bool uint u8 u16 u32 u64 int i8 i16 i32 i64)
  * ```
  */
 #[lang="bitxor"]
-pub trait BitXor<RHS,Result> {
+pub trait BitXor<Sized? RHS, Result> for Sized? {
     /// The method for the `^` operator
     fn bitxor(&self, rhs: &RHS) -> Result;
 }
@@ -553,7 +553,7 @@ bitxor_impl!(bool uint u8 u16 u32 u64 int i8 i16 i32 i64)
  * ```
  */
 #[lang="shl"]
-pub trait Shl<RHS,Result> {
+pub trait Shl<Sized? RHS, Result> for Sized? {
     /// The method for the `<<` operator
     fn shl(&self, rhs: &RHS) -> Result;
 }
@@ -596,7 +596,7 @@ shl_impl!(uint u8 u16 u32 u64 int i8 i16 i32 i64)
  * ```
  */
 #[lang="shr"]
-pub trait Shr<RHS,Result> {
+pub trait Shr<Sized? RHS, Result> for Sized? {
     /// The method for the `>>` operator
     fn shr(&self, rhs: &RHS) -> Result;
 }
@@ -669,7 +669,7 @@ pub trait Index<Sized? Index, Sized? Result> for Sized? {
  * ```
  */
 #[lang="index_mut"]
-pub trait IndexMut<Sized? Index, Result> for Sized? {
+pub trait IndexMut<Sized? Index, Sized? Result> for Sized? {
     /// The method for the indexing (`Foo[Bar]`) operation
     fn index_mut<'a>(&'a mut self, index: &Index) -> &'a mut Result;
 }
@@ -712,7 +712,7 @@ pub trait IndexMut<Sized? Index, Result> for Sized? {
  * ```
  */
 #[lang="slice"]
-pub trait Slice<Idx, Sized? Result> for Sized? {
+pub trait Slice<Sized? Idx, Sized? Result> for Sized? {
     /// The method for the slicing operation foo[]
     fn as_slice_<'a>(&'a self) -> &'a Result;
     /// The method for the slicing operation foo[from..]
@@ -761,7 +761,7 @@ pub trait Slice<Idx, Sized? Result> for Sized? {
  * ```
  */
 #[lang="slice_mut"]
-pub trait SliceMut<Idx, Sized? Result> for Sized? {
+pub trait SliceMut<Sized? Idx, Sized? Result> for Sized? {
     /// The method for the slicing operation foo[]
     fn as_mut_slice_<'a>(&'a mut self) -> &'a mut Result;
     /// The method for the slicing operation foo[from..]
@@ -800,7 +800,7 @@ pub trait SliceMut<Idx, Sized? Result> for Sized? {
  * ```
  */
 #[lang="deref"]
-pub trait Deref<Sized? Result> {
+pub trait Deref<Sized? Result> for Sized? {
     /// The method called to dereference a value
     fn deref<'a>(&'a self) -> &'a Result;
 }
@@ -859,21 +859,21 @@ impl<'a, Sized? T> DerefMut<T> for &'a mut T {
 
 /// A version of the call operator that takes an immutable receiver.
 #[lang="fn"]
-pub trait Fn<Args,Result> {
+pub trait Fn<Args,Result> for Sized? {
     /// This is called when the call operator is used.
     extern "rust-call" fn call(&self, args: Args) -> Result;
 }
 
 /// A version of the call operator that takes a mutable receiver.
 #[lang="fn_mut"]
-pub trait FnMut<Args,Result> {
+pub trait FnMut<Args,Result> for Sized? {
     /// This is called when the call operator is used.
     extern "rust-call" fn call_mut(&mut self, args: Args) -> Result;
 }
 
 /// A version of the call operator that takes a by-value receiver.
 #[lang="fn_once"]
-pub trait FnOnce<Args,Result> {
+pub trait FnOnce<Args,Result> for Sized? {
     /// This is called when the call operator is used.
     extern "rust-call" fn call_once(self, args: Args) -> Result;
 }
diff --git a/src/libcore/slice.rs b/src/libcore/slice.rs
index 48e52fab51c..7a3e06e7eb4 100644
--- a/src/libcore/slice.rs
+++ b/src/libcore/slice.rs
@@ -1008,15 +1008,25 @@ impl<T: Clone> CloneSlicePrelude<T> for [T] {
 
 /// Data that is viewable as a slice.
 #[unstable = "may merge with other traits"]
-pub trait AsSlice<T> {
+pub trait AsSlice<T> for Sized? {
     /// Work with `self` as a slice.
     fn as_slice<'a>(&'a self) -> &'a [T];
 }
 
 #[unstable = "trait is unstable"]
-impl<'a,T> AsSlice<T> for &'a [T] {
+impl<T> AsSlice<T> for [T] {
     #[inline(always)]
-    fn as_slice<'a>(&'a self) -> &'a [T] { *self }
+    fn as_slice<'a>(&'a self) -> &'a [T] { self }
+}
+
+impl<'a, T, Sized? U: AsSlice<T>> AsSlice<T> for &'a U {
+    #[inline(always)]
+    fn as_slice<'a>(&'a self) -> &'a [T] { AsSlice::as_slice(*self) }
+}
+
+impl<'a, T, Sized? U: AsSlice<T>> AsSlice<T> for &'a mut U {
+    #[inline(always)]
+    fn as_slice<'a>(&'a self) -> &'a [T] { AsSlice::as_slice(*self) }
 }
 
 #[unstable = "waiting for DST"]
@@ -1681,13 +1691,13 @@ impl<T: PartialEq> PartialEq for [T] {
 impl<T: Eq> Eq for [T] {}
 
 #[unstable = "waiting for DST"]
-impl<T: PartialEq, V: AsSlice<T>> Equiv<V> for [T] {
+impl<T: PartialEq, Sized? V: AsSlice<T>> Equiv<V> for [T] {
     #[inline]
     fn equiv(&self, other: &V) -> bool { self.as_slice() == other.as_slice() }
 }
 
 #[unstable = "waiting for DST"]
-impl<'a,T:PartialEq, V: AsSlice<T>> Equiv<V> for &'a mut [T] {
+impl<'a,T:PartialEq, Sized? V: AsSlice<T>> Equiv<V> for &'a mut [T] {
     #[inline]
     fn equiv(&self, other: &V) -> bool { self.as_slice() == other.as_slice() }
 }
diff --git a/src/libgraphviz/maybe_owned_vec.rs b/src/libgraphviz/maybe_owned_vec.rs
index 5d97e9787e8..70b3971c6b8 100644
--- a/src/libgraphviz/maybe_owned_vec.rs
+++ b/src/libgraphviz/maybe_owned_vec.rs
@@ -89,7 +89,7 @@ impl<'a, T: Ord> Ord for MaybeOwnedVector<'a, T> {
     }
 }
 
-impl<'a, T: PartialEq, V: AsSlice<T>> Equiv<V> for MaybeOwnedVector<'a, T> {
+impl<'a, T: PartialEq, Sized? V: AsSlice<T>> Equiv<V> for MaybeOwnedVector<'a, T> {
     fn equiv(&self, other: &V) -> bool {
         self.as_slice() == other.as_slice()
     }
diff --git a/src/libstd/path/posix.rs b/src/libstd/path/posix.rs
index 3e013ba20c4..2b444fdc32b 100644
--- a/src/libstd/path/posix.rs
+++ b/src/libstd/path/posix.rs
@@ -16,6 +16,7 @@ use cmp::{PartialEq, Eq, PartialOrd, Ord, Ordering};
 use hash;
 use io::Writer;
 use iter::{DoubleEndedIterator, AdditiveIterator, Extend, Iterator, Map};
+use kinds::Sized;
 use option::{Option, None, Some};
 use str::{FromStr, Str};
 use str;
@@ -342,7 +343,7 @@ impl Path {
 
     /// Returns a normalized byte vector representation of a path, by removing all empty
     /// components, and unnecessary . and .. components.
-    fn normalize<V: AsSlice<u8>>(v: V) -> Vec<u8> {
+    fn normalize<Sized? V: AsSlice<u8>>(v: &V) -> Vec<u8> {
         // borrowck is being very picky
         let val = {
             let is_abs = !v.as_slice().is_empty() && v.as_slice()[0] == SEP_BYTE;