libstd: Remove "dual impls" from the language and enforce coherence rules. r=brson

"Dual impls" are impls that are both type implementations and trait
implementations. They can lead to ambiguity and so this patch removes them
from the language.

This also enforces coherence rules. Without this patch, records can implement
traits not defined in the current crate. This patch fixes this, and updates
all of rustc to adhere to the new enforcement. Most of this patch is fixing
rustc to obey the coherence rules, which involves converting a bunch of records
to structs.

6 files changed, 53 insertions, 70 deletions

diff --git a/src/libstd/bigint.rs b/src/libstd/bigint.rs
index fc783429126..4283a7e402b 100644
--- a/src/libstd/bigint.rs
+++ b/src/libstd/bigint.rs
@@ -17,7 +17,7 @@ A BigInt is a combination of BigUint and Sign.
 */
 
 use core::cmp::{Eq, Ord};
-use core::num::{Num, Zero, One};
+use core::num::{IntConvertible, Zero, One};
 use core::*;
 
 /**
@@ -121,7 +121,7 @@ impl BigUint : One {
     static pub pure fn one() -> BigUint { BigUint::new(~[1]) }
 }
 
-impl BigUint : Num {
+impl BigUint : Add<BigUint, BigUint> {
     pure fn add(&self, other: &BigUint) -> BigUint {
         let new_len = uint::max(self.data.len(), other.data.len());
 
@@ -138,7 +138,9 @@ impl BigUint : Num {
         if carry == 0 { return BigUint::new(sum) };
         return BigUint::new(sum + [carry]);
     }
+}
 
+impl BigUint : Sub<BigUint, BigUint> {
     pure fn sub(&self, other: &BigUint) -> BigUint {
         let new_len = uint::max(self.data.len(), other.data.len());
 
@@ -161,7 +163,9 @@ impl BigUint : Num {
         assert borrow == 0;     // <=> assert (self >= other);
         return BigUint::new(diff);
     }
+}
 
+impl BigUint : Mul<BigUint, BigUint> {
     pure fn mul(&self, other: &BigUint) -> BigUint {
         if self.is_zero() || other.is_zero() { return Zero::zero(); }
 
@@ -224,18 +228,27 @@ impl BigUint : Num {
             }
         }
     }
+}
 
+impl BigUint : Div<BigUint, BigUint> {
     pure fn div(&self, other: &BigUint) -> BigUint {
         let (d, _) = self.divmod(other);
         return d;
     }
+}
+
+impl BigUint : Modulo<BigUint, BigUint> {
     pure fn modulo(&self, other: &BigUint) -> BigUint {
         let (_, m) = self.divmod(other);
         return m;
     }
+}
 
+impl BigUint : Neg<BigUint> {
     pure fn neg(&self) -> BigUint { fail }
+}
 
+impl BigUint : IntConvertible {
     pure fn to_int(&self) -> int {
         uint::min(self.to_uint(), int::max_value as uint) as int
     }
@@ -625,7 +638,7 @@ impl BigInt : One {
     }
 }
 
-impl BigInt : Num {
+impl BigInt : Add<BigInt, BigInt> {
     pure fn add(&self, other: &BigInt) -> BigInt {
         match (self.sign, other.sign) {
             (Zero, _)      => copy *other,
@@ -637,6 +650,9 @@ impl BigInt : Num {
             (Minus, Minus) => -((-self) + (-*other))
         }
     }
+}
+
+impl BigInt : Sub<BigInt, BigInt> {
     pure fn sub(&self, other: &BigInt) -> BigInt {
         match (self.sign, other.sign) {
             (Zero, _)    => -other,
@@ -654,6 +670,9 @@ impl BigInt : Num {
             (Minus, Minus) => (-other) - (-*self)
         }
     }
+}
+
+impl BigInt : Mul<BigInt, BigInt> {
     pure fn mul(&self, other: &BigInt) -> BigInt {
         match (self.sign, other.sign) {
             (Zero, _)     | (_,     Zero)  => Zero::zero(),
@@ -665,18 +684,29 @@ impl BigInt : Num {
             }
         }
     }
+}
+
+impl BigInt : Div<BigInt, BigInt> {
     pure fn div(&self, other: &BigInt) -> BigInt {
         let (d, _) = self.divmod(other);
         return d;
     }
+}
+
+impl BigInt : Modulo<BigInt, BigInt> {
     pure fn modulo(&self, other: &BigInt) -> BigInt {
         let (_, m) = self.divmod(other);
         return m;
     }
+}
+
+impl BigInt : Neg<BigInt> {
     pure fn neg(&self) -> BigInt {
         BigInt::from_biguint(self.sign.neg(), copy self.data)
     }
+}
 
+impl BigInt : IntConvertible {
     pure fn to_int(&self) -> int {
         match self.sign {
             Plus  => uint::min(self.to_uint(), int::max_value as uint) as int,
@@ -834,7 +864,7 @@ pub impl BigInt {
 mod biguint_tests {
 
     use core::*;
-    use core::num::{Num, Zero, One};
+    use num::{IntConvertible, Zero, One};
     use super::{BigInt, BigUint, BigDigit};
 
     #[test]
@@ -974,7 +1004,7 @@ mod biguint_tests {
     fn test_convert_int() {
         fn check(v: ~[BigDigit], i: int) {
             let b = BigUint::new(v);
-            assert b == Num::from_int(i);
+            assert b == IntConvertible::from_int(i);
             assert b.to_int() == i;
         }
 
@@ -1244,7 +1274,7 @@ mod bigint_tests {
     use super::{BigInt, BigUint, BigDigit, Sign, Minus, Zero, Plus};
 
     use core::*;
-    use core::num::{Num, Zero, One};
+    use core::num::{IntConvertible, Zero, One};
 
     #[test]
     fn test_from_biguint() {
@@ -1303,7 +1333,7 @@ mod bigint_tests {
     #[test]
     fn test_convert_int() {
         fn check(b: BigInt, i: int) {
-            assert b == Num::from_int(i);
+            assert b == IntConvertible::from_int(i);
             assert b.to_int() == i;
         }
 
@@ -1563,7 +1593,8 @@ mod bigint_tests {
     #[test]
     fn test_to_str_radix() {
         fn check(n: int, ans: &str) {
-            assert ans == Num::from_int::<BigInt>(n).to_str_radix(10);
+            assert ans == IntConvertible::from_int::<BigInt>(
+                n).to_str_radix(10);
         }
         check(10, "10");
         check(1, "1");
@@ -1576,7 +1607,7 @@ mod bigint_tests {
     #[test]
     fn test_from_str_radix() {
         fn check(s: &str, ans: Option<int>) {
-            let ans = ans.map(|&n| Num::from_int(n));
+            let ans = ans.map(|&n| IntConvertible::from_int(n));
             assert BigInt::from_str_radix(s, 10) == ans;
         }
         check("10", Some(10));
diff --git a/src/libstd/deque.rs b/src/libstd/deque.rs
index b4217dfb39d..2abd59523a1 100644
--- a/src/libstd/deque.rs
+++ b/src/libstd/deque.rs
@@ -249,69 +249,19 @@ mod tests {
         assert deq.get(3) == d;
     }
 
+    #[deriving_eq]
     enum Taggy { One(int), Two(int, int), Three(int, int, int), }
 
+    #[deriving_eq]
     enum Taggypar<T> {
         Onepar(int), Twopar(int, int), Threepar(int, int, int),
     }
 
+    #[deriving_eq]
     struct RecCy {
         x: int,
         y: int,
-        t: Taggy,
-    }
-
-    impl Taggy : Eq {
-        pure fn eq(&self, other: &Taggy) -> bool {
-            match (*self) {
-              One(a1) => match (*other) {
-                One(b1) => return a1 == b1,
-                _ => return false
-              },
-              Two(a1, a2) => match (*other) {
-                Two(b1, b2) => return a1 == b1 && a2 == b2,
-                _ => return false
-              },
-              Three(a1, a2, a3) => match (*other) {
-                Three(b1, b2, b3) => return a1 == b1 && a2 == b2 && a3 == b3,
-                _ => return false
-              }
-            }
-        }
-        pure fn ne(&self, other: &Taggy) -> bool { !(*self).eq(other) }
-    }
-
-    impl Taggypar<int> : Eq {
-        //let eq4: EqFn<Taggypar<int>> = |x,y| taggypareq::<int>(x, y);
-        pure fn eq(&self, other: &Taggypar<int>) -> bool {
-                  match (*self) {
-                    Onepar::<int>(a1) => match (*other) {
-                      Onepar::<int>(b1) => return a1 == b1,
-                      _ => return false
-                    },
-                    Twopar::<int>(a1, a2) => match (*other) {
-                      Twopar::<int>(b1, b2) => return a1 == b1 && a2 == b2,
-                      _ => return false
-                    },
-                    Threepar::<int>(a1, a2, a3) => match (*other) {
-                      Threepar::<int>(b1, b2, b3) => {
-                          return a1 == b1 && a2 == b2 && a3 == b3
-                      }
-                      _ => return false
-                    }
-                  }
-        }
-        pure fn ne(&self, other: &Taggypar<int>) -> bool {
-            !(*self).eq(other)
-        }
-    }
-
-    impl RecCy : Eq {
-        pure fn eq(&self, other: &RecCy) -> bool {
-          return (*self).x == (*other).x && (*self).y == (*other).y &&
-                 (*self).t == (*other).t;
-        }
-        pure fn ne(&self, other: &RecCy) -> bool { !(*self).eq(other) }
+        t: Taggy
     }
 
     #[test]
diff --git a/src/libstd/ebml.rs b/src/libstd/ebml.rs
index dc379cec21b..f93705c0c62 100644
--- a/src/libstd/ebml.rs
+++ b/src/libstd/ebml.rs
@@ -676,6 +676,7 @@ pub mod writer {
 mod tests {
     use ebml::reader;
     use ebml::writer;
+    use serialize::Encodable;
     use serialize;
 
     use core::io;
diff --git a/src/libstd/json.rs b/src/libstd/json.rs
index 45d467095fb..1361d8647b5 100644
--- a/src/libstd/json.rs
+++ b/src/libstd/json.rs
@@ -15,6 +15,7 @@
 
 //! json serialization
 
+use serialize::Encodable;
 use serialize;
 use sort::Sort;
 
diff --git a/src/libstd/map.rs b/src/libstd/map.rs
index 3c890ef0654..f3016e9df21 100644
--- a/src/libstd/map.rs
+++ b/src/libstd/map.rs
@@ -28,7 +28,7 @@ pub type Set<K:Eq IterBytes Hash> = HashMap<K, ()>;
 
 pub type HashMap<K:Eq IterBytes Hash, V> = chained::T<K, V>;
 
-pub trait Map<K:Eq IterBytes Hash Copy, V: Copy> {
+pub trait StdMap<K:Eq IterBytes Hash Copy, V: Copy> {
     /// Return the number of elements in the map
     pure fn size() -> uint;
 
@@ -124,7 +124,7 @@ pub mod util {
 // FIXME (#2344): package this up and export it as a datatype usable for
 // external code that doesn't want to pay the cost of a box.
 pub mod chained {
-    use map::{Map, util};
+    use map::{StdMap, util};
 
     use core::io;
     use core::ops;
@@ -239,7 +239,7 @@ pub mod chained {
         }
     }
 
-    impl<K:Eq IterBytes Hash Copy, V: Copy> T<K, V>: Map<K, V> {
+    impl<K:Eq IterBytes Hash Copy, V: Copy> T<K, V>: StdMap<K, V> {
         pure fn size() -> uint { self.count }
 
         pure fn contains_key(k: K) -> bool {
diff --git a/src/libstd/smallintmap.rs b/src/libstd/smallintmap.rs
index 5f16f7155b6..f17fce28ea9 100644
--- a/src/libstd/smallintmap.rs
+++ b/src/libstd/smallintmap.rs
@@ -15,7 +15,7 @@
 #[forbid(deprecated_mode)];
 
 use map;
-use map::Map;
+use map::StdMap;
 
 use core::dvec::DVec;
 use core::ops;
@@ -81,7 +81,7 @@ pub pure fn contains_key<T: Copy>(self: SmallIntMap<T>, key: uint) -> bool {
 }
 
 /// Implements the map::map interface for smallintmap
-impl<V: Copy> SmallIntMap<V>: map::Map<uint, V> {
+impl<V: Copy> SmallIntMap<V>: map::StdMap<uint, V> {
     pure fn size() -> uint {
         let mut sz = 0u;
         for self.v.each |item| {
@@ -165,8 +165,8 @@ impl<V: Copy> SmallIntMap<V>: ops::Index<uint, V> {
 }
 
 /// Cast the given smallintmap to a map::map
-pub fn as_map<V: Copy>(s: SmallIntMap<V>) -> map::Map<uint, V> {
-    s as map::Map::<uint, V>
+pub fn as_map<V: Copy>(s: SmallIntMap<V>) -> map::StdMap<uint, V> {
+    s as map::StdMap::<uint, V>
 }
 
 #[cfg(test)]