librustc: Properly compare implementation method type parameter bounds

with the corresponding trait parameter bounds.

This is a version of the patch in PR #12611 by Florian Hahn, modified to
address Niko's feedback.

It does not address the issue of duplicate type parameter bounds, nor
does it address the issue of implementation-defined methods that contain
*fewer* bounds than the trait, because Niko's review indicates that this
should not be necessary (and indeed I believe it is not). A test has
been added to ensure that this works.

This will break code like:

    trait Foo {
        fn bar<T:Baz>();
    }

    impl Foo for Boo {
        fn bar<T:Baz + Quux>() { ... }
        //             ^~~~ ERROR
    }

This will be rejected because the implementation requires *more* bounds
than the trait. It can be fixed by either adding the missing bound to
the trait:

    trait Foo {
        fn bar<T:Baz + Quux>();
        //             ^~~~
    }

    impl Foo for Boo {
        fn bar<T:Baz + Quux>() { ... }  // OK
    }

Or by removing the bound from the impl:

    trait Foo {
        fn bar<T:Baz>();
    }

    impl Foo for Boo {
        fn bar<T:Baz>() { ... }  // OK
        //       ^ remove Quux
    }

This patch imports the relevant tests from #2687, as well as the test
case in #5886, which is fixed as well by this patch.

Closes #2687.
Closes #5886.

[breaking-change]

3 files changed, 136 insertions, 0 deletions

diff --git a/src/test/compile-fail/trait-bounds-impl-comparison-1.rs b/src/test/compile-fail/trait-bounds-impl-comparison-1.rs
new file mode 100644
index 00000000000..eec116855c9
--- /dev/null
+++ b/src/test/compile-fail/trait-bounds-impl-comparison-1.rs
@@ -0,0 +1,78 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+//
+// Make sure rustc checks the type parameter bounds in implementations of traits,
+// see #2687
+
+trait A {}
+
+trait B: A {}
+
+trait C: A {}
+
+trait Foo {
+    fn test_error1_fn<T: Eq>(&self);
+    fn test_error2_fn<T: Eq + Ord>(&self);
+    fn test_error3_fn<T: Eq + Ord>(&self);
+    fn test3_fn<T: Eq + Ord>(&self);
+    fn test4_fn<T: Eq + Ord>(&self);
+    fn test_error5_fn<T: A>(&self);
+    fn test6_fn<T: A + Eq>(&self);
+    fn test_error7_fn<T: A>(&self);
+    fn test_error8_fn<T: B>(&self);
+}
+
+impl Foo for int {
+    // invalid bound for T, was defined as Eq in trait
+    fn test_error1_fn<T: Ord>(&self) {}
+    //~^ ERROR in method `test_error1_fn`, type parameter 0 requires bound `core::cmp::Ord`
+
+    // invalid bound for T, was defined as Eq + Ord in trait
+    fn test_error2_fn<T: Eq + B>(&self) {}
+    //~^ ERROR in method `test_error2_fn`, type parameter 0 requires bound `B`
+
+    // invalid bound for T, was defined as Eq + Ord in trait
+    fn test_error3_fn<T: B + Eq>(&self) {}
+    //~^ ERROR in method `test_error3_fn`, type parameter 0 requires bound `B`
+
+    // multiple bounds, same order as in trait
+    fn test3_fn<T: Ord + Eq>(&self) {}
+
+    // multiple bounds, different order as in trait
+    fn test4_fn<T: Eq + Ord>(&self) {}
+
+    // parameters in impls must be equal or more general than in the defining trait
+    fn test_error5_fn<T: B>(&self) {}
+    //~^ ERROR in method `test_error5_fn`, type parameter 0 requires bound `B`
+
+    // bound `std::cmp::Eq` not enforced by this implementation, but this is OK
+    fn test6_fn<T: A>(&self) {}
+
+    fn test_error7_fn<T: A + Eq>(&self) {}
+    //~^ ERROR in method `test_error7_fn`, type parameter 0 requires bound `core::cmp::Eq`
+
+    fn test_error8_fn<T: C>(&self) {}
+    //~^ ERROR in method `test_error8_fn`, type parameter 0 requires bound `C`
+}
+
+
+trait Getter<T> { }
+
+trait Trait {
+    fn method<G:Getter<int>>();
+}
+
+impl Trait for uint {
+    fn method<G: Getter<uint>>() {}
+    //~^ ERROR in method `method`, type parameter 0 requires bound `Getter<uint>`
+}
+
+fn main() {}
+
diff --git a/src/test/compile-fail/trait-bounds-impl-comparison-2.rs b/src/test/compile-fail/trait-bounds-impl-comparison-2.rs
new file mode 100644
index 00000000000..a970a86408e
--- /dev/null
+++ b/src/test/compile-fail/trait-bounds-impl-comparison-2.rs
@@ -0,0 +1,33 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// Issue #5886: a complex instance of issue #2687.
+
+trait Iterator<A> {
+    fn next(&mut self) -> Option<A>;
+}
+
+trait IteratorUtil<A> {
+    fn zip<B, U: Iterator<U>>(self, other: U) -> ZipIterator<Self, U>;
+}
+
+impl<A, T: Iterator<A>> IteratorUtil<A> for T {
+    fn zip<B, U: Iterator<B>>(self, other: U) -> ZipIterator<T, U> {
+    //~^ ERROR in method `zip`, type parameter 1 requires bound `Iterator<B>`
+        ZipIterator{a: self, b: other}
+    }
+}
+
+struct ZipIterator<T, U> {
+    a: T, b: U
+}
+
+fn main() {}
+
diff --git a/src/test/run-pass/trait-bounds-impl-comparison-duplicates.rs b/src/test/run-pass/trait-bounds-impl-comparison-duplicates.rs
new file mode 100644
index 00000000000..55ad22dd0bf
--- /dev/null
+++ b/src/test/run-pass/trait-bounds-impl-comparison-duplicates.rs
@@ -0,0 +1,25 @@
+// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// Tests that type parameter bounds on an implementation need not match the
+// trait exactly, as long as the implementation doesn't demand *more* bounds
+// than the trait.
+
+trait A {
+    fn foo<T: Eq + Ord>(&self);
+}
+
+impl A for int {
+    fn foo<T: Ord + Ord>(&self) {}
+}
+
+fn main() {}
+
+