Rollup merge of #41309 - frewsxcv:sg-implement-rfc-1268, r=nikomatsakis

Implement RFC 1268.

Rebased version of https://github.com/rust-lang/rust/pull/40097.

Tracking issue: https://github.com/rust-lang/rust/issues/29864.

28 files changed, 203 insertions, 22 deletions

diff --git a/src/doc/unstable-book/src/SUMMARY.md b/src/doc/unstable-book/src/SUMMARY.md
index a5599395f79..a9796fdf01e 100644
--- a/src/doc/unstable-book/src/SUMMARY.md
+++ b/src/doc/unstable-book/src/SUMMARY.md
@@ -136,6 +136,7 @@
 - [optin_builtin_traits](optin-builtin-traits.md)
 - [option_entry](option-entry.md)
 - [osstring_shrink_to_fit](osstring-shrink-to-fit.md)
+- [overlapping_marker_traits](overlapping-marker-traits.md)
 - [panic_abort](panic-abort.md)
 - [panic_runtime](panic-runtime.md)
 - [panic_unwind](panic-unwind.md)
diff --git a/src/doc/unstable-book/src/overlapping-marker-traits.md b/src/doc/unstable-book/src/overlapping-marker-traits.md
new file mode 100644
index 00000000000..a4920839c6c
--- /dev/null
+++ b/src/doc/unstable-book/src/overlapping-marker-traits.md
@@ -0,0 +1,7 @@
+# `overlapping_marker_traits`
+
+The tracking issue for this feature is: [#29864]
+
+[#29864]: https://github.com/rust-lang/rust/issues/29864
+
+------------------------
diff --git a/src/librustc/traits/select.rs b/src/librustc/traits/select.rs
index 67d50210ba3..410eb2b8484 100644
--- a/src/librustc/traits/select.rs
+++ b/src/librustc/traits/select.rs
@@ -1736,7 +1736,8 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
                 if other.evaluation == EvaluatedToOk {
                     if let ImplCandidate(victim_def) = victim.candidate {
                         let tcx = self.tcx().global_tcx();
-                        return traits::specializes(tcx, other_def, victim_def);
+                        return traits::specializes(tcx, other_def, victim_def) ||
+                            tcx.impls_are_allowed_to_overlap(other_def, victim_def);
                     }
                 }
 
diff --git a/src/librustc/traits/specialize/specialization_graph.rs b/src/librustc/traits/specialize/specialization_graph.rs
index 40eb6939567..6e2c16c82ae 100644
--- a/src/librustc/traits/specialize/specialization_graph.rs
+++ b/src/librustc/traits/specialize/specialization_graph.rs
@@ -113,6 +113,10 @@ impl<'a, 'gcx, 'tcx> Children {
                                                         possible_sibling,
                                                         impl_def_id);
                 if let Some(impl_header) = overlap {
+                    if tcx.impls_are_allowed_to_overlap(impl_def_id, possible_sibling) {
+                        return Ok((false, false));
+                    }
+
                     let le = specializes(tcx, impl_def_id, possible_sibling);
                     let ge = specializes(tcx, possible_sibling, impl_def_id);
 
diff --git a/src/librustc/ty/mod.rs b/src/librustc/ty/mod.rs
index 8ff91583d08..3da9383762b 100644
--- a/src/librustc/ty/mod.rs
+++ b/src/librustc/ty/mod.rs
@@ -2227,6 +2227,25 @@ impl<'a, 'gcx, 'tcx> TyCtxt<'a, 'gcx, 'tcx> {
         queries::impl_trait_ref::get(self, DUMMY_SP, id)
     }
 
+    /// Returns true if the impls are the same polarity and are implementing
+    /// a trait which contains no items
+    pub fn impls_are_allowed_to_overlap(self, def_id1: DefId, def_id2: DefId) -> bool {
+        if !self.sess.features.borrow().overlapping_marker_traits {
+            return false;
+        }
+        let trait1_is_empty = self.impl_trait_ref(def_id1)
+            .map_or(false, |trait_ref| {
+                self.associated_item_def_ids(trait_ref.def_id).is_empty()
+            });
+        let trait2_is_empty = self.impl_trait_ref(def_id2)
+            .map_or(false, |trait_ref| {
+                self.associated_item_def_ids(trait_ref.def_id).is_empty()
+            });
+        self.trait_impl_polarity(def_id1) == self.trait_impl_polarity(def_id2)
+            && trait1_is_empty
+            && trait2_is_empty
+    }
+
     // Returns `ty::VariantDef` if `def` refers to a struct,
     // or variant or their constructors, panics otherwise.
     pub fn expect_variant_def(self, def: Def) -> &'tcx VariantDef {
diff --git a/src/libsyntax/feature_gate.rs b/src/libsyntax/feature_gate.rs
index 8b62416dcbd..6e455234196 100644
--- a/src/libsyntax/feature_gate.rs
+++ b/src/libsyntax/feature_gate.rs
@@ -349,6 +349,9 @@ declare_features! (
 
     // Allows module-level inline assembly by way of global_asm!()
     (active, global_asm, "1.18.0", Some(35119)),
+
+    // Allows overlapping impls of marker traits
+    (active, overlapping_marker_traits, "1.18.0", Some(29864)),
 );
 
 declare_features! (
diff --git a/src/test/compile-fail/E0120.rs b/src/test/compile-fail/E0120.rs
index 3fdeb753175..80cc0d2680f 100644
--- a/src/test/compile-fail/E0120.rs
+++ b/src/test/compile-fail/E0120.rs
@@ -8,7 +8,7 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-trait MyTrait {}
+trait MyTrait { fn foo() {} }
 
 impl Drop for MyTrait {
               //~^ ERROR E0120
diff --git a/src/test/compile-fail/auxiliary/trait_impl_conflict.rs b/src/test/compile-fail/auxiliary/trait_impl_conflict.rs
index c3ecbb014dc..3190ce430ad 100644
--- a/src/test/compile-fail/auxiliary/trait_impl_conflict.rs
+++ b/src/test/compile-fail/auxiliary/trait_impl_conflict.rs
@@ -9,6 +9,7 @@
 // except according to those terms.
 
 pub trait Foo {
+    fn foo() {}
 }
 
 impl Foo for isize {
diff --git a/src/test/compile-fail/coherence-conflicting-negative-trait-impl.rs b/src/test/compile-fail/coherence-conflicting-negative-trait-impl.rs
index 7fd1b17f296..8e9d1eff345 100644
--- a/src/test/compile-fail/coherence-conflicting-negative-trait-impl.rs
+++ b/src/test/compile-fail/coherence-conflicting-negative-trait-impl.rs
@@ -9,6 +9,7 @@
 // except according to those terms.
 
 #![feature(optin_builtin_traits)]
+#![feature(overlapping_marker_traits)]
 
 trait MyTrait {}
 
@@ -20,8 +21,8 @@ impl<T: MyTrait> !Send for TestType<T> {}
 //~^ ERROR conflicting implementations of trait `std::marker::Send`
 
 unsafe impl<T:'static> Send for TestType<T> {}
-//~^ ERROR conflicting implementations of trait `std::marker::Send`
 
 impl !Send for TestType<i32> {}
+//~^ ERROR conflicting implementations of trait `std::marker::Send`
 
 fn main() {}
diff --git a/src/test/compile-fail/coherence-default-trait-impl.rs b/src/test/compile-fail/coherence-default-trait-impl.rs
index 15a80c64f8b..e6bf068156c 100644
--- a/src/test/compile-fail/coherence-default-trait-impl.rs
+++ b/src/test/compile-fail/coherence-default-trait-impl.rs
@@ -10,7 +10,7 @@
 
 #![feature(optin_builtin_traits)]
 
-trait MyTrait {}
+trait MyTrait { fn foo() {} }
 
 impl MyTrait for .. {}
 //~^ ERROR redundant default implementations of trait `MyTrait`
diff --git a/src/test/compile-fail/coherence-impls-send.rs b/src/test/compile-fail/coherence-impls-send.rs
index f130a935351..9caaee41aeb 100644
--- a/src/test/compile-fail/coherence-impls-send.rs
+++ b/src/test/compile-fail/coherence-impls-send.rs
@@ -9,6 +9,7 @@
 // except according to those terms.
 
 #![feature(optin_builtin_traits)]
+#![feature(overlapping_marker_traits)]
 
 use std::marker::Copy;
 
@@ -34,7 +35,6 @@ unsafe impl Send for [MyType] {}
 
 unsafe impl Send for &'static [NotSync] {}
 //~^ ERROR E0117
-//~| ERROR E0119
 
 fn main() {
 }
diff --git a/src/test/compile-fail/coherence-no-direct-lifetime-dispatch.rs b/src/test/compile-fail/coherence-no-direct-lifetime-dispatch.rs
index 6de338f1db0..47026cd32d4 100644
--- a/src/test/compile-fail/coherence-no-direct-lifetime-dispatch.rs
+++ b/src/test/compile-fail/coherence-no-direct-lifetime-dispatch.rs
@@ -10,7 +10,7 @@
 
 // Test that you cannot *directly* dispatch on lifetime requirements
 
-trait MyTrait {}
+trait MyTrait { fn foo() {} }
 
 impl<T> MyTrait for T {}
 impl<T: 'static> MyTrait for T {} //~ ERROR E0119
diff --git a/src/test/compile-fail/coherence-overlap-all-t-and-tuple.rs b/src/test/compile-fail/coherence-overlap-all-t-and-tuple.rs
index 928ba7a36db..1fad608db6c 100644
--- a/src/test/compile-fail/coherence-overlap-all-t-and-tuple.rs
+++ b/src/test/compile-fail/coherence-overlap-all-t-and-tuple.rs
@@ -17,6 +17,7 @@
 // Seems pretty basic, but then there was issue #24241. :)
 
 trait From<U> {
+    fn foo() {}
 }
 
 impl <T> From<T> for T {
diff --git a/src/test/compile-fail/coherence-overlap-messages.rs b/src/test/compile-fail/coherence-overlap-messages.rs
index 0ae8135221c..a10deeafbe6 100644
--- a/src/test/compile-fail/coherence-overlap-messages.rs
+++ b/src/test/compile-fail/coherence-overlap-messages.rs
@@ -8,22 +8,22 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-trait Foo {}
+trait Foo { fn foo() {} }
 
 impl<T> Foo for T {}
 impl<U> Foo for U {} //~ ERROR conflicting implementations of trait `Foo`:
 
-trait Bar {}
+trait Bar { fn bar() {} }
 
 impl<T> Bar for (T, u8) {}
 impl<T> Bar for (u8, T) {} //~ ERROR conflicting implementations of trait `Bar` for type `(u8, u8)`:
 
-trait Baz<T> {}
+trait Baz<T> { fn baz() {} }
 
 impl<T> Baz<u8> for T {}
 impl<T> Baz<T> for u8 {} //~ ERROR conflicting implementations of trait `Baz<u8>` for type `u8`:
 
-trait Quux<U, V> {}
+trait Quux<U, V> { fn quux() {} }
 
 impl<T, U, V> Quux<U, V> for T {}
 impl<T, U> Quux<U, U> for T {} //~ ERROR conflicting implementations of trait `Quux<_, _>`:
diff --git a/src/test/compile-fail/coherence-projection-conflict-orphan.rs b/src/test/compile-fail/coherence-projection-conflict-orphan.rs
index 3ed3549de89..784ff0cd5e0 100644
--- a/src/test/compile-fail/coherence-projection-conflict-orphan.rs
+++ b/src/test/compile-fail/coherence-projection-conflict-orphan.rs
@@ -15,7 +15,7 @@
 // due to the orphan rules. Therefore, `A::Item` may yet turn out to
 // be `i32`.
 
-pub trait Foo<P> {}
+pub trait Foo<P> { fn foo() {} }
 
 pub trait Bar {
     type Output: 'static;
diff --git a/src/test/compile-fail/coherence-projection-conflict-ty-param.rs b/src/test/compile-fail/coherence-projection-conflict-ty-param.rs
index f04902a70f6..120d9046389 100644
--- a/src/test/compile-fail/coherence-projection-conflict-ty-param.rs
+++ b/src/test/compile-fail/coherence-projection-conflict-ty-param.rs
@@ -13,7 +13,7 @@
 
 use std::marker::PhantomData;
 
-pub trait Foo<P> {}
+pub trait Foo<P> { fn foo() {} }
 
 impl <P, T: Foo<P>> Foo<P> for Option<T> {}
 
diff --git a/src/test/compile-fail/coherence-projection-conflict.rs b/src/test/compile-fail/coherence-projection-conflict.rs
index 6d3ab32f06f..3c32ab38b93 100644
--- a/src/test/compile-fail/coherence-projection-conflict.rs
+++ b/src/test/compile-fail/coherence-projection-conflict.rs
@@ -10,7 +10,7 @@
 
 use std::marker::PhantomData;
 
-pub trait Foo<P> {}
+pub trait Foo<P> { fn foo() {} }
 
 pub trait Bar {
     type Output: 'static;
diff --git a/src/test/compile-fail/coherence_copy_like_err_fundamental_struct.rs b/src/test/compile-fail/coherence_copy_like_err_fundamental_struct.rs
index fcd6e5c4952..9fbb7aa4cb1 100644
--- a/src/test/compile-fail/coherence_copy_like_err_fundamental_struct.rs
+++ b/src/test/compile-fail/coherence_copy_like_err_fundamental_struct.rs
@@ -20,7 +20,7 @@ extern crate coherence_copy_like_lib as lib;
 
 struct MyType { x: i32 }
 
-trait MyTrait { }
+trait MyTrait { fn foo() {} }
 impl<T: lib::MyCopy> MyTrait for T { }
 
 // `MyFundamentalStruct` is declared fundamental, so we can test that
diff --git a/src/test/compile-fail/coherence_copy_like_err_fundamental_struct_ref.rs b/src/test/compile-fail/coherence_copy_like_err_fundamental_struct_ref.rs
index b5c0a7fb5f5..2f6dca4f3c2 100644
--- a/src/test/compile-fail/coherence_copy_like_err_fundamental_struct_ref.rs
+++ b/src/test/compile-fail/coherence_copy_like_err_fundamental_struct_ref.rs
@@ -20,7 +20,7 @@ extern crate coherence_copy_like_lib as lib;
 
 struct MyType { x: i32 }
 
-trait MyTrait { }
+trait MyTrait { fn foo() {} }
 impl<T: lib::MyCopy> MyTrait for T { }
 
 // `MyFundamentalStruct` is declared fundamental, so we can test that
diff --git a/src/test/compile-fail/coherence_copy_like_err_fundamental_struct_tuple.rs b/src/test/compile-fail/coherence_copy_like_err_fundamental_struct_tuple.rs
index 8e3e3f31cb5..f424e887201 100644
--- a/src/test/compile-fail/coherence_copy_like_err_fundamental_struct_tuple.rs
+++ b/src/test/compile-fail/coherence_copy_like_err_fundamental_struct_tuple.rs
@@ -19,7 +19,7 @@ extern crate coherence_copy_like_lib as lib;
 
 struct MyType { x: i32 }
 
-trait MyTrait { }
+trait MyTrait { fn foo() {} }
 
 impl<T: lib::MyCopy> MyTrait for T { }
 
diff --git a/src/test/compile-fail/coherence_copy_like_err_struct.rs b/src/test/compile-fail/coherence_copy_like_err_struct.rs
index 35bc17b8e88..04262e65c5a 100644
--- a/src/test/compile-fail/coherence_copy_like_err_struct.rs
+++ b/src/test/compile-fail/coherence_copy_like_err_struct.rs
@@ -17,7 +17,7 @@ extern crate coherence_copy_like_lib as lib;
 
 struct MyType { x: i32 }
 
-trait MyTrait { }
+trait MyTrait { fn foo() {} }
 impl<T: lib::MyCopy> MyTrait for T { }
 
 // `MyStruct` is not declared fundamental, therefore this would
diff --git a/src/test/compile-fail/coherence_copy_like_err_tuple.rs b/src/test/compile-fail/coherence_copy_like_err_tuple.rs
index a70cc92955f..378a70864f0 100644
--- a/src/test/compile-fail/coherence_copy_like_err_tuple.rs
+++ b/src/test/compile-fail/coherence_copy_like_err_tuple.rs
@@ -17,7 +17,7 @@ extern crate coherence_copy_like_lib as lib;
 
 struct MyType { x: i32 }
 
-trait MyTrait { }
+trait MyTrait { fn foo() {} }
 impl<T: lib::MyCopy> MyTrait for T { }
 
 // Tuples are not fundamental, therefore this would require that
diff --git a/src/test/compile-fail/feature-gate-overlapping_marker_traits.rs b/src/test/compile-fail/feature-gate-overlapping_marker_traits.rs
new file mode 100644
index 00000000000..d2aa4e59b5b
--- /dev/null
+++ b/src/test/compile-fail/feature-gate-overlapping_marker_traits.rs
@@ -0,0 +1,19 @@
+// Copyright 2017 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.
+
+use std::fmt::{Debug, Display};
+
+trait MyMarker {}
+
+impl<T: Display> MyMarker for T {}
+impl<T: Debug> MyMarker for T {}
+//~^ ERROR E0119
+
+fn main() {}
diff --git a/src/test/compile-fail/overlap-marker-trait.rs b/src/test/compile-fail/overlap-marker-trait.rs
new file mode 100644
index 00000000000..a649ae25f34
--- /dev/null
+++ b/src/test/compile-fail/overlap-marker-trait.rs
@@ -0,0 +1,41 @@
+// Copyright 2017 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.
+
+// Test for RFC 1268: we allow overlapping impls of marker traits,
+// that is, traits without items. In this case, a type `T` is
+// `MyMarker` if it is either `Debug` or `Display`. This test just
+// checks that we don't consider **all** types to be `MyMarker`.  See
+// also the companion test in
+// `run-pass/overlap-permitted-for-marker-traits.rs`.
+
+#![feature(overlapping_marker_traits)]
+#![feature(optin_builtin_traits)]
+
+use std::fmt::{Debug, Display};
+
+trait Marker {}
+
+impl<T: Debug> Marker for T {}
+impl<T: Display> Marker for T {}
+
+fn is_marker<T: Marker>() { }
+
+struct NotDebugOrDisplay;
+
+fn main() {
+    // Debug && Display:
+    is_marker::<i32>();
+
+    // Debug && !Display:
+    is_marker::<Vec<i32>>();
+
+    // !Debug && !Display
+    is_marker::<NotDebugOrDisplay>(); //~ ERROR
+}
diff --git a/src/test/compile-fail/specialization/specialization-overlap.rs b/src/test/compile-fail/specialization/specialization-overlap.rs
index f5798171001..ff12a82db5b 100644
--- a/src/test/compile-fail/specialization/specialization-overlap.rs
+++ b/src/test/compile-fail/specialization/specialization-overlap.rs
@@ -10,19 +10,19 @@
 
 #![feature(specialization)]
 
-trait Foo {}
+trait Foo { fn foo() {} }
 impl<T: Clone> Foo for T {}
 impl<T> Foo for Vec<T> {} //~ ERROR E0119
 
-trait Bar {}
+trait Bar { fn bar() {} }
 impl<T> Bar for (T, u8) {}
 impl<T> Bar for (u8, T) {} //~ ERROR E0119
 
-trait Baz<U> {}
+trait Baz<U> { fn baz() {} }
 impl<T> Baz<T> for u8 {}
 impl<T> Baz<u8> for T {} //~ ERROR E0119
 
-trait Qux {}
+trait Qux { fn qux() {} }
 impl<T: Clone> Qux for T {}
 impl<T: Eq> Qux for T {} //~ ERROR E0119
 
diff --git a/src/test/run-pass/overlap-doesnt-conflict-with-specialization.rs b/src/test/run-pass/overlap-doesnt-conflict-with-specialization.rs
new file mode 100644
index 00000000000..ed45d81c0d6
--- /dev/null
+++ b/src/test/run-pass/overlap-doesnt-conflict-with-specialization.rs
@@ -0,0 +1,27 @@
+// Copyright 2017 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.
+
+#![feature(overlapping_marker_traits)]
+#![feature(specialization)]
+
+trait MyMarker {}
+
+impl<T> MyMarker for T {}
+impl<T> MyMarker for Vec<T> {}
+
+fn foo<T: MyMarker>(t: T) -> T {
+    t
+}
+
+fn main() {
+    assert_eq!(1, foo(1));
+    assert_eq!(2.0, foo(2.0));
+    assert_eq!(vec![1], foo(vec![1]));
+}
diff --git a/src/test/run-pass/overlap-permitted-for-marker-traits-neg.rs b/src/test/run-pass/overlap-permitted-for-marker-traits-neg.rs
new file mode 100644
index 00000000000..740d5d22ab5
--- /dev/null
+++ b/src/test/run-pass/overlap-permitted-for-marker-traits-neg.rs
@@ -0,0 +1,20 @@
+// Copyright 2017 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.
+
+#![feature(overlapping_marker_traits)]
+#![feature(optin_builtin_traits)]
+
+// Overlapping negative impls for `MyStruct` are permitted:
+struct MyStruct;
+impl !Send for MyStruct {}
+impl !Send for MyStruct {}
+
+fn main() {
+}
diff --git a/src/test/run-pass/overlap-permitted-for-marker-traits.rs b/src/test/run-pass/overlap-permitted-for-marker-traits.rs
new file mode 100644
index 00000000000..11a46299d8c
--- /dev/null
+++ b/src/test/run-pass/overlap-permitted-for-marker-traits.rs
@@ -0,0 +1,36 @@
+// Copyright 2017 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 for RFC 1268: we allow overlapping impls of marker traits,
+// that is, traits without items. In this case, a type `T` is
+// `MyMarker` if it is either `Debug` or `Display`.
+
+#![feature(overlapping_marker_traits)]
+#![feature(optin_builtin_traits)]
+
+use std::fmt::{Debug, Display};
+
+trait MyMarker {}
+
+impl<T: Debug> MyMarker for T {}
+impl<T: Display> MyMarker for T {}
+
+fn foo<T: MyMarker>(t: T) -> T {
+    t
+}
+
+fn main() {
+    // Debug && Display:
+    assert_eq!(1, foo(1));
+    assert_eq!(2.0, foo(2.0));
+
+    // Debug && !Display:
+    assert_eq!(vec![1], foo(vec![1]));
+}