auto merge of #5234 : pcwalton/rust/equiv, r=pcwalton

r? @nikomatsakis 

24 files changed, 111 insertions, 28 deletions

diff --git a/src/libcore/cmp.rs b/src/libcore/cmp.rs
index d00824f8be6..ac2afc920ff 100644
--- a/src/libcore/cmp.rs
+++ b/src/libcore/cmp.rs
@@ -150,6 +150,14 @@ pub pure fn gt<T:Ord>(v1: &T, v2: &T) -> bool {
     (*v1).gt(v2)
 }
 
+/// The equivalence relation. Two values may be equivalent even if they are
+/// of different types. The most common use case for this relation is
+/// container types; e.g. it is often desirable to be able to use `&str`
+/// values to look up entries in a container with `~str` keys.
+pub trait Equiv<T> {
+    pure fn equiv(&self, other: &T) -> bool;
+}
+
 #[inline(always)]
 pub pure fn min<T:Ord>(v1: T, v2: T) -> T {
     if v1 < v2 { v1 } else { v2 }
diff --git a/src/libcore/container.rs b/src/libcore/container.rs
index 36424d1bfaa..d7e05a62c51 100644
--- a/src/libcore/container.rs
+++ b/src/libcore/container.rs
@@ -10,6 +10,7 @@
 
 //! Container traits
 
+use cmp::Equiv;
 use option::Option;
 
 pub trait Container {
diff --git a/src/libcore/hashmap.rs b/src/libcore/hashmap.rs
index b6ba790c300..43ec6294bdc 100644
--- a/src/libcore/hashmap.rs
+++ b/src/libcore/hashmap.rs
@@ -13,7 +13,7 @@
 /// Open addressing with linear probing.
 pub mod linear {
     use container::{Container, Mutable, Map, Set};
-    use cmp::Eq;
+    use cmp::{Eq, Equiv};
     use hash::Hash;
     use to_bytes::IterBytes;
     use iter::BaseIter;
@@ -108,6 +108,15 @@ pub mod linear {
         }
 
         #[inline(always)]
+        pure fn bucket_for_key_equiv<Q:Hash + IterBytes + Equiv<K>>(
+                &self,
+                k: &Q)
+             -> SearchResult {
+            let hash = k.hash_keyed(self.k0, self.k1) as uint;
+            self.bucket_for_key_with_hash_equiv(hash, k)
+        }
+
+        #[inline(always)]
         pure fn bucket_for_key_with_hash(&self,
                                          hash: uint,
                                          k: &K) -> SearchResult {
@@ -122,6 +131,24 @@ pub mod linear {
             TableFull
         }
 
+        #[inline(always)]
+        pure fn bucket_for_key_with_hash_equiv<Q:Equiv<K>>(&self,
+                                                           hash: uint,
+                                                           k: &Q)
+                                                        -> SearchResult {
+            let _ = for self.bucket_sequence(hash) |i| {
+                match self.buckets[i] {
+                    Some(ref bkt) => {
+                        if bkt.hash == hash && k.equiv(&bkt.key) {
+                            return FoundEntry(i);
+                        }
+                    },
+                    None => return FoundHole(i)
+                }
+            };
+            TableFull
+        }
+
         /// Expand the capacity of the array to the next power of two
         /// and re-insert each of the existing buckets.
         #[inline(always)]
@@ -450,6 +477,28 @@ pub mod linear {
                 None => fail!(fmt!("No entry found for key: %?", k)),
             }
         }
+
+        /// Return true if the map contains a value for the specified key,
+        /// using equivalence
+        pure fn contains_key_equiv<Q:Hash + IterBytes + Equiv<K>>(
+                &self,
+                key: &Q)
+             -> bool {
+            match self.bucket_for_key_equiv(key) {
+                FoundEntry(_) => {true}
+                TableFull | FoundHole(_) => {false}
+            }
+        }
+
+        /// Return the value corresponding to the key in the map, using
+        /// equivalence
+        pure fn find_equiv<Q:Hash + IterBytes + Equiv<K>>(&self, k: &Q)
+                                                       -> Option<&self/V> {
+            match self.bucket_for_key_equiv(k) {
+                FoundEntry(idx) => Some(self.value_for_bucket(idx)),
+                TableFull | FoundHole(_) => None,
+            }
+        }
     }
 
     impl<K:Hash + IterBytes + Eq,V:Eq> Eq for LinearMap<K, V> {
diff --git a/src/libcore/str.rs b/src/libcore/str.rs
index 892956e285e..19453c5e96f 100644
--- a/src/libcore/str.rs
+++ b/src/libcore/str.rs
@@ -20,7 +20,7 @@
 use at_vec;
 use cast;
 use char;
-use cmp::{TotalOrd, Ordering, Less, Equal, Greater};
+use cmp::{Equiv, TotalOrd, Ordering, Less, Equal, Greater};
 use libc;
 use option::{None, Option, Some};
 use ptr;
@@ -898,6 +898,12 @@ impl Ord for @str {
     pure fn gt(&self, other: &@str) -> bool { gt((*self), (*other)) }
 }
 
+#[cfg(notest)]
+impl Equiv<~str> for &str {
+    #[inline(always)]
+    pure fn equiv(&self, other: &~str) -> bool { eq_slice(*self, *other) }
+}
+
 /*
 Section: Iterating through strings
 */
diff --git a/src/libcore/vec.rs b/src/libcore/vec.rs
index f7676bd211e..ab5f04ace79 100644
--- a/src/libcore/vec.rs
+++ b/src/libcore/vec.rs
@@ -14,7 +14,7 @@
 
 use container::{Container, Mutable};
 use cast;
-use cmp::{Eq, Ord, TotalOrd, Ordering, Less, Equal, Greater};
+use cmp::{Eq, Equiv, Ord, TotalOrd, Ordering, Less, Equal, Greater};
 use iter::BaseIter;
 use iter;
 use kinds::Copy;
@@ -1572,6 +1572,12 @@ impl<T:Eq> Eq for @[T] {
     pure fn ne(&self, other: &@[T]) -> bool { !(*self).eq(other) }
 }
 
+#[cfg(notest)]
+impl<T:Eq> Equiv<~[T]> for &[T] {
+    #[inline(always)]
+    pure fn equiv(&self, other: &~[T]) -> bool { eq(*self, *other) }
+}
+
 // Lexicographical comparison
 
 pure fn cmp<T: TotalOrd>(a: &[T], b: &[T]) -> Ordering {
diff --git a/src/librustc/middle/typeck/astconv.rs b/src/librustc/middle/typeck/astconv.rs
index 8472d956cd2..a232aa764dd 100644
--- a/src/librustc/middle/typeck/astconv.rs
+++ b/src/librustc/middle/typeck/astconv.rs
@@ -214,7 +214,7 @@ pub fn ast_ty_to_ty<AC:AstConv, RS:region_scope + Copy + Durable>(
                 let mut mt = ast_mt_to_mt(self, rscope, mt);
                 if a_seq_ty.mutbl == ast::m_mutbl ||
                         a_seq_ty.mutbl == ast::m_const {
-                    mt = ty::mt { ty: mt.ty, mutbl: ast::m_mutbl };
+                    mt = ty::mt { ty: mt.ty, mutbl: a_seq_ty.mutbl };
                 }
                 return ty::mk_evec(tcx, mt, vst);
             }
diff --git a/src/libsyntax/parse/parser.rs b/src/libsyntax/parse/parser.rs
index dd179171fce..5013b2c919f 100644
--- a/src/libsyntax/parse/parser.rs
+++ b/src/libsyntax/parse/parser.rs
@@ -3112,7 +3112,7 @@ pub impl Parser {
     fn parse_trait_ref_list(&self, ket: &token::Token) -> ~[@trait_ref] {
         self.parse_seq_to_before_end(
             ket,
-            seq_sep_none(),
+            seq_sep_trailing_disallowed(token::BINOP(token::PLUS)),
             |p| p.parse_trait_ref()
         )
     }
diff --git a/src/libsyntax/print/pprust.rs b/src/libsyntax/print/pprust.rs
index 735344e43be..d307e3964e7 100644
--- a/src/libsyntax/print/pprust.rs
+++ b/src/libsyntax/print/pprust.rs
@@ -600,8 +600,11 @@ pub fn print_item(s: @ps, &&item: @ast::item) {
         print_generics(s, generics);
         if traits.len() != 0u {
             word(s.s, ~":");
-            for traits.each |trait_| {
+            for traits.eachi |i, trait_| {
                 nbsp(s);
+                if i != 0 {
+                    word_space(s, ~"+");
+                }
                 print_path(s, trait_.path, false);
             }
         }
diff --git a/src/test/auxiliary/trait_inheritance_auto_xc_aux.rs b/src/test/auxiliary/trait_inheritance_auto_xc_aux.rs
index 3e26a09fb8f..ecd43686b77 100644
--- a/src/test/auxiliary/trait_inheritance_auto_xc_aux.rs
+++ b/src/test/auxiliary/trait_inheritance_auto_xc_aux.rs
@@ -12,6 +12,6 @@ trait Foo { fn f() -> int; }
 trait Bar { fn g() -> int; }
 trait Baz { fn h() -> int; }
 
-trait Quux: Foo Bar Baz { }
+trait Quux: Foo + Bar + Baz { }
 
 impl<T:Foo + Bar + Baz> Quux for T { }
diff --git a/src/test/auxiliary/trait_inheritance_overloading_xc.rs b/src/test/auxiliary/trait_inheritance_overloading_xc.rs
index 10a7238a3f7..e86f7cfd26a 100644
--- a/src/test/auxiliary/trait_inheritance_overloading_xc.rs
+++ b/src/test/auxiliary/trait_inheritance_overloading_xc.rs
@@ -10,7 +10,7 @@
 
 use core::cmp::Eq;
 
-pub trait MyNum : Add<Self,Self> Sub<Self,Self> Mul<Self,Self> Eq {
+pub trait MyNum : Add<Self,Self> + Sub<Self,Self> + Mul<Self,Self> + Eq {
 }
 
 pub struct MyInt {
diff --git a/src/test/compile-fail/issue-3953.rs b/src/test/compile-fail/issue-3953.rs
index c88a94ef629..afd8cf89233 100644
--- a/src/test/compile-fail/issue-3953.rs
+++ b/src/test/compile-fail/issue-3953.rs
@@ -10,12 +10,15 @@
 
 use core::cmp::Eq;
 
-trait Hahaha: Eq Eq Eq Eq Eq Eq Eq Eq Eq Eq Eq Eq Eq Eq Eq Eq //~ ERROR Duplicate supertrait in trait declaration
-              Eq Eq Eq Eq Eq Eq Eq Eq Eq Eq Eq Eq Eq Eq Eq Eq
-              Eq Eq Eq Eq Eq Eq Eq Eq Eq Eq Eq Eq Eq Eq Eq Eq
-              Eq Eq Eq Eq Eq Eq Eq Eq Eq Eq Eq Eq Eq Eq Eq Eq
-              Eq Eq Eq Eq Eq Eq Eq Eq Eq Eq Eq Eq Eq Eq Eq Eq
-              Eq Eq Eq Eq Eq Eq Eq Eq Eq Eq Eq Eq Eq Eq Eq Eq {}
+trait Hahaha: Eq + Eq + Eq + Eq + Eq + //~ ERROR Duplicate supertrait
+              Eq + Eq + Eq + Eq + Eq + Eq + Eq + Eq + Eq + Eq + Eq + Eq + Eq +
+              Eq + Eq + Eq + Eq + Eq + Eq + Eq + Eq + Eq + Eq + Eq + Eq + Eq +
+              Eq + Eq + Eq + Eq + Eq + Eq + Eq + Eq + Eq + Eq + Eq + Eq + Eq +
+              Eq + Eq + Eq + Eq + Eq + Eq + Eq + Eq + Eq + Eq + Eq + Eq + Eq +
+              Eq + Eq + Eq + Eq + Eq + Eq + Eq + Eq + Eq + Eq + Eq + Eq + Eq +
+              Eq + Eq + Eq + Eq + Eq + Eq + Eq + Eq + Eq + Eq + Eq + Eq + Eq +
+              Eq + Eq + Eq + Eq + Eq + Eq + Eq + Eq + Eq + Eq + Eq + Eq +
+              Eq {}
 
 enum Lol = int;
 
diff --git a/src/test/run-pass/const-vec-syntax.rs b/src/test/run-pass/const-vec-syntax.rs
new file mode 100644
index 00000000000..ec8e04e41ef
--- /dev/null
+++ b/src/test/run-pass/const-vec-syntax.rs
@@ -0,0 +1,7 @@
+fn f(_: &const [int]) {}
+
+fn main() {
+    let v = [ 1, 2, 3 ];
+    f(v);
+}
+
diff --git a/src/test/run-pass/trait-inheritance-auto-xc-2.rs b/src/test/run-pass/trait-inheritance-auto-xc-2.rs
index c3333fa10ab..6b8dd43d58b 100644
--- a/src/test/run-pass/trait-inheritance-auto-xc-2.rs
+++ b/src/test/run-pass/trait-inheritance-auto-xc-2.rs
@@ -17,7 +17,7 @@ extern mod aux(name = "trait_inheritance_auto_xc_2_aux");
 use aux::{Foo, Bar, Baz, A};
 
 // We want to extend all Foo, Bar, Bazes to Quuxes
-pub trait Quux: Foo Bar Baz { }
+pub trait Quux: Foo + Bar + Baz { }
 impl<T:Foo + Bar + Baz> Quux for T { }
 
 fn f<T:Quux>(a: &T) {
diff --git a/src/test/run-pass/trait-inheritance-auto.rs b/src/test/run-pass/trait-inheritance-auto.rs
index 5d576193880..7ebbc8e83cb 100644
--- a/src/test/run-pass/trait-inheritance-auto.rs
+++ b/src/test/run-pass/trait-inheritance-auto.rs
@@ -16,7 +16,7 @@ trait Foo { fn f() -> int; }
 trait Bar { fn g() -> int; }
 trait Baz { fn h() -> int; }
 
-trait Quux: Foo Bar Baz { }
+trait Quux: Foo + Bar + Baz { }
 
 struct A { x: int }
 
diff --git a/src/test/run-pass/trait-inheritance-diamond.rs b/src/test/run-pass/trait-inheritance-diamond.rs
index 1d6e4823091..a4a3991f9e8 100644
--- a/src/test/run-pass/trait-inheritance-diamond.rs
+++ b/src/test/run-pass/trait-inheritance-diamond.rs
@@ -13,7 +13,7 @@
 trait A { fn a(&self) -> int; }
 trait B: A { fn b(&self) -> int; }
 trait C: A { fn c(&self) -> int; }
-trait D: B C { fn d(&self) -> int; }
+trait D: B + C { fn d(&self) -> int; }
 
 struct S { bogus: () }
 
diff --git a/src/test/run-pass/trait-inheritance-num.rs b/src/test/run-pass/trait-inheritance-num.rs
index 36b1e6cd4de..92cb25b8d2b 100644
--- a/src/test/run-pass/trait-inheritance-num.rs
+++ b/src/test/run-pass/trait-inheritance-num.rs
@@ -16,9 +16,9 @@ use core::num::NumCast::from;
 extern mod std;
 use std::cmp::FuzzyEq;
 
-pub trait NumExt: NumCast Eq Ord {}
+pub trait NumExt: NumCast + Eq + Ord {}
 
-pub trait FloatExt: NumExt FuzzyEq<Self> {}
+pub trait FloatExt: NumExt + FuzzyEq<Self> {}
 
 fn greater_than_one<T:NumExt>(n: &T) -> bool { *n > from(1) }
 fn greater_than_one_float<T:FloatExt>(n: &T) -> bool { *n > from(1) }
diff --git a/src/test/run-pass/trait-inheritance-num0.rs b/src/test/run-pass/trait-inheritance-num0.rs
index 70eed496db3..7f0d4d77b62 100644
--- a/src/test/run-pass/trait-inheritance-num0.rs
+++ b/src/test/run-pass/trait-inheritance-num0.rs
@@ -19,7 +19,7 @@ trait Num {
     fn gt(&self, other: &Self) -> bool;
 }
 
-pub trait NumExt: Num NumCast { }
+pub trait NumExt: Num + NumCast { }
 
 fn greater_than_one<T:NumExt>(n: &T) -> bool {
     n.gt(&from(1))
diff --git a/src/test/run-pass/trait-inheritance-num1.rs b/src/test/run-pass/trait-inheritance-num1.rs
index 44b4bd60f1d..07b9772af29 100644
--- a/src/test/run-pass/trait-inheritance-num1.rs
+++ b/src/test/run-pass/trait-inheritance-num1.rs
@@ -11,7 +11,7 @@
 use core::cmp::Ord;
 use core::num::NumCast::from;
 
-pub trait NumExt: NumCast Ord { }
+pub trait NumExt: NumCast + Ord { }
 
 fn greater_than_one<T:NumExt>(n: &T) -> bool {
     *n > from(1)
diff --git a/src/test/run-pass/trait-inheritance-num2.rs b/src/test/run-pass/trait-inheritance-num2.rs
index 5c9d9e6a13b..8f8b83c3d76 100644
--- a/src/test/run-pass/trait-inheritance-num2.rs
+++ b/src/test/run-pass/trait-inheritance-num2.rs
@@ -38,7 +38,7 @@ impl TypeExt for f64 {}
 impl TypeExt for float {}
 
 
-pub trait NumExt: TypeExt Eq Ord NumCast {}
+pub trait NumExt: TypeExt + Eq + Ord + NumCast {}
 
 impl NumExt for u8 {}
 impl NumExt for u16 {}
@@ -94,7 +94,7 @@ impl IntegerExt for i64 {}
 impl IntegerExt for int {}
 
 
-pub trait FloatExt: NumExt FuzzyEq<Self> {}
+pub trait FloatExt: NumExt + FuzzyEq<Self> {}
 
 impl FloatExt for f32 {}
 impl FloatExt for f64 {}
diff --git a/src/test/run-pass/trait-inheritance-num3.rs b/src/test/run-pass/trait-inheritance-num3.rs
index c2cd56ad107..67861709e76 100644
--- a/src/test/run-pass/trait-inheritance-num3.rs
+++ b/src/test/run-pass/trait-inheritance-num3.rs
@@ -11,7 +11,7 @@
 use core::cmp::{Eq, Ord};
 use core::num::NumCast::from;
 
-pub trait NumExt: Eq Ord NumCast {}
+pub trait NumExt: Eq + Ord + NumCast {}
 
 impl NumExt for f32 {}
 
diff --git a/src/test/run-pass/trait-inheritance-num5.rs b/src/test/run-pass/trait-inheritance-num5.rs
index ac8d80359d8..2efe5b23eb5 100644
--- a/src/test/run-pass/trait-inheritance-num5.rs
+++ b/src/test/run-pass/trait-inheritance-num5.rs
@@ -11,7 +11,7 @@
 use core::cmp::{Eq, Ord};
 use core::num::NumCast::from;
 
-pub trait NumExt: Eq NumCast {}
+pub trait NumExt: Eq + NumCast {}
 
 impl NumExt for f32 {}
 impl NumExt for int {}
diff --git a/src/test/run-pass/trait-inheritance-overloading.rs b/src/test/run-pass/trait-inheritance-overloading.rs
index 54a9ea9ad1e..a4d7e33891f 100644
--- a/src/test/run-pass/trait-inheritance-overloading.rs
+++ b/src/test/run-pass/trait-inheritance-overloading.rs
@@ -10,7 +10,7 @@
 
 use core::cmp::Eq;
 
-trait MyNum : Add<Self,Self> Sub<Self,Self> Mul<Self,Self> Eq { }
+trait MyNum : Add<Self,Self> + Sub<Self,Self> + Mul<Self,Self> + Eq { }
 
 struct MyInt { val: int }
 
diff --git a/src/test/run-pass/trait-inheritance-static2.rs b/src/test/run-pass/trait-inheritance-static2.rs
index 6f706ad0be7..ccc7f1fc4c0 100644
--- a/src/test/run-pass/trait-inheritance-static2.rs
+++ b/src/test/run-pass/trait-inheritance-static2.rs
@@ -14,7 +14,7 @@ trait MyNum {
     static fn from_int(int) -> Self;
 }
 
-pub trait NumExt: MyEq MyNum { }
+pub trait NumExt: MyEq + MyNum { }
 
 struct S { v: int }
 
diff --git a/src/test/run-pass/trait-inheritance2.rs b/src/test/run-pass/trait-inheritance2.rs
index 55a63e9099a..5925888650d 100644
--- a/src/test/run-pass/trait-inheritance2.rs
+++ b/src/test/run-pass/trait-inheritance2.rs
@@ -12,7 +12,7 @@ trait Foo { fn f() -> int; }
 trait Bar { fn g() -> int; }
 trait Baz { fn h() -> int; }
 
-trait Quux: Foo Bar Baz { }
+trait Quux: Foo + Bar + Baz { }
 
 struct A { x: int }