Auto merge of #45455 - kennytm:print-extern-impl-for-e0119, r=nikomatsakis

Improve diagnostic of E0119 with extern crate, try to print the conflicting impl.

Closes #27403.
Closes #23563.

Should improve #23980.

The diagnostic now looks like:

```
error[E0119]: conflicting implementations of trait `std::convert::Into<_>` for type `GenX<_>`:
  --> $DIR/issue-27403.rs:15:1
   |
15 | / impl<S> Into<S> for GenX<S> {
16 | |     fn into(self) -> S {
17 | |         self.inner
18 | |     }
19 | | }
   | |_^
   |
   = note: conflicting implementation in crate `core`:
           - impl<T, U> std::convert::Into<U> for T
             where U: std::convert::From<T>;

error: aborting due to previous error
```

16 files changed, 428 insertions, 2 deletions

diff --git a/src/librustc/traits/specialize/mod.rs b/src/librustc/traits/specialize/mod.rs
index 20da4c084f0..d8d0715ff39 100644
--- a/src/librustc/traits/specialize/mod.rs
+++ b/src/librustc/traits/specialize/mod.rs
@@ -20,7 +20,7 @@
 use super::{SelectionContext, FulfillmentContext};
 use super::util::impl_trait_ref_and_oblig;
 
-use rustc_data_structures::fx::FxHashMap;
+use rustc_data_structures::fx::{FxHashMap, FxHashSet};
 use hir::def_id::DefId;
 use infer::{InferCtxt, InferOk};
 use ty::subst::{Subst, Substs};
@@ -335,7 +335,12 @@ pub(super) fn specialization_graph_provider<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx
                                                             |ty| format!(" for `{}`", ty))));
                     }
                     Err(cname) => {
-                        err.note(&format!("conflicting implementation in crate `{}`", cname));
+                        let msg = match to_pretty_impl_header(tcx, overlap.with_impl) {
+                            Some(s) => format!(
+                                "conflicting implementation in crate `{}`:\n- {}", cname, s),
+                            None => format!("conflicting implementation in crate `{}`", cname),
+                        };
+                        err.note(&msg);
                     }
                 }
 
@@ -353,3 +358,56 @@ pub(super) fn specialization_graph_provider<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx
 
     Rc::new(sg)
 }
+
+/// Recovers the "impl X for Y" signature from `impl_def_id` and returns it as a
+/// string.
+fn to_pretty_impl_header(tcx: TyCtxt, impl_def_id: DefId) -> Option<String> {
+    use std::fmt::Write;
+
+    let trait_ref = if let Some(tr) = tcx.impl_trait_ref(impl_def_id) {
+        tr
+    } else {
+        return None;
+    };
+
+    let mut w = "impl".to_owned();
+
+    let substs = Substs::identity_for_item(tcx, impl_def_id);
+
+    // FIXME: Currently only handles ?Sized.
+    //        Needs to support ?Move and ?DynSized when they are implemented.
+    let mut types_without_default_bounds = FxHashSet::default();
+    let sized_trait = tcx.lang_items().sized_trait();
+
+    if !substs.is_noop() {
+        types_without_default_bounds.extend(substs.types());
+        w.push('<');
+        w.push_str(&substs.iter().map(|k| k.to_string()).collect::<Vec<_>>().join(", "));
+        w.push('>');
+    }
+
+    write!(w, " {} for {}", trait_ref, tcx.type_of(impl_def_id)).unwrap();
+
+    // The predicates will contain default bounds like `T: Sized`. We need to
+    // remove these bounds, and add `T: ?Sized` to any untouched type parameters.
+    let predicates = tcx.predicates_of(impl_def_id).predicates;
+    let mut pretty_predicates = Vec::with_capacity(predicates.len());
+    for p in predicates {
+        if let Some(poly_trait_ref) = p.to_opt_poly_trait_ref() {
+            if Some(poly_trait_ref.def_id()) == sized_trait {
+                types_without_default_bounds.remove(poly_trait_ref.self_ty());
+                continue;
+            }
+        }
+        pretty_predicates.push(p.to_string());
+    }
+    for ty in types_without_default_bounds {
+        pretty_predicates.push(format!("{}: ?Sized", ty));
+    }
+    if !pretty_predicates.is_empty() {
+        write!(w, "\n  where {}", pretty_predicates.join(", ")).unwrap();
+    }
+
+    w.push(';');
+    Some(w)
+}
diff --git a/src/librustc/ty/subst.rs b/src/librustc/ty/subst.rs
index e2881ac9b79..83222e79a12 100644
--- a/src/librustc/ty/subst.rs
+++ b/src/librustc/ty/subst.rs
@@ -107,6 +107,19 @@ impl<'tcx> fmt::Debug for Kind<'tcx> {
     }
 }
 
+impl<'tcx> fmt::Display for Kind<'tcx> {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        if let Some(ty) = self.as_type() {
+            write!(f, "{}", ty)
+        } else if let Some(r) = self.as_region() {
+            write!(f, "{}", r)
+        } else {
+            // FIXME(RFC 2000): extend this if/else chain when we support const generic.
+            unimplemented!();
+        }
+    }
+}
+
 impl<'tcx> TypeFoldable<'tcx> for Kind<'tcx> {
     fn super_fold_with<'gcx: 'tcx, F: TypeFolder<'gcx, 'tcx>>(&self, folder: &mut F) -> Self {
         if let Some(ty) = self.as_type() {
diff --git a/src/test/ui/e0119/auxiliary/complex_impl_support.rs b/src/test/ui/e0119/auxiliary/complex_impl_support.rs
new file mode 100644
index 00000000000..b30db966099
--- /dev/null
+++ b/src/test/ui/e0119/auxiliary/complex_impl_support.rs
@@ -0,0 +1,32 @@
+// 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::marker::PhantomData;
+
+pub trait External {}
+
+pub struct M<'a, 'b, 'c, T, U, V> {
+    a: PhantomData<&'a ()>,
+    b: PhantomData<&'b ()>,
+    c: PhantomData<&'c ()>,
+    d: PhantomData<T>,
+    e: PhantomData<U>,
+    f: PhantomData<V>,
+}
+
+impl<'a, 'b, 'c, T, U, V, W> External for (T, M<'a, 'b, 'c, Box<U>, V, W>)
+where
+    'b: 'a,
+    T: 'a,
+    U: (FnOnce(T) -> V) + 'static,
+    V: Iterator<Item=T> + Clone,
+    W: std::ops::Add,
+    W::Output: Copy,
+{}
diff --git a/src/test/ui/e0119/auxiliary/issue_23563_a.rs b/src/test/ui/e0119/auxiliary/issue_23563_a.rs
new file mode 100644
index 00000000000..57a0da0248d
--- /dev/null
+++ b/src/test/ui/e0119/auxiliary/issue_23563_a.rs
@@ -0,0 +1,35 @@
+// 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.
+
+// Ref: https://github.com/rust-lang/rust/issues/23563#issuecomment-260751672
+
+pub trait LolTo<T> {
+    fn convert_to(&self) -> T;
+}
+
+pub trait LolInto<T>: Sized {
+    fn convert_into(self) -> T;
+}
+
+pub trait LolFrom<T> {
+    fn from(T) -> Self;
+}
+
+impl<'a, T: ?Sized, U> LolInto<U> for &'a T where T: LolTo<U> {
+    fn convert_into(self) -> U {
+        self.convert_to()
+    }
+}
+
+impl<T, U> LolFrom<T> for U where T: LolInto<U> {
+    fn from(t: T) -> U {
+        t.convert_into()
+    }
+}
diff --git a/src/test/ui/e0119/complex-impl.rs b/src/test/ui/e0119/complex-impl.rs
new file mode 100644
index 00000000000..f0d2630b9d0
--- /dev/null
+++ b/src/test/ui/e0119/complex-impl.rs
@@ -0,0 +1,21 @@
+// 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.
+
+// aux-build:complex_impl_support.rs
+
+extern crate complex_impl_support;
+
+use complex_impl_support::{External, M};
+
+struct Q;
+
+impl<R> External for (Q, R) {}
+
+fn main() {}
\ No newline at end of file
diff --git a/src/test/ui/e0119/complex-impl.stderr b/src/test/ui/e0119/complex-impl.stderr
new file mode 100644
index 00000000000..ff7c8a160a4
--- /dev/null
+++ b/src/test/ui/e0119/complex-impl.stderr
@@ -0,0 +1,18 @@
+error[E0119]: conflicting implementations of trait `complex_impl_support::External` for type `(Q, complex_impl_support::M<'_, '_, '_, std::boxed::Box<_>, _, _>)`:
+  --> $DIR/complex-impl.rs:19:1
+   |
+19 | impl<R> External for (Q, R) {}
+   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+   |
+   = note: conflicting implementation in crate `complex_impl_support`:
+           - impl<'a, 'b, 'c, T, U, V, W> complex_impl_support::External for (T, complex_impl_support::M<'a, 'b, 'c, std::boxed::Box<U>, V, W>)
+             where <U as std::ops::FnOnce<(T,)>>::Output == V, <V as std::iter::Iterator>::Item == T, 'b : 'a, T : 'a, U: std::ops::FnOnce<(T,)>, U : 'static, V: std::iter::Iterator, V: std::clone::Clone, W: std::ops::Add, <W as std::ops::Add>::Output: std::marker::Copy;
+
+error[E0210]: type parameter `R` must be used as the type parameter for some local type (e.g. `MyStruct<T>`); only traits defined in the current crate can be implemented for a type parameter
+  --> $DIR/complex-impl.rs:19:1
+   |
+19 | impl<R> External for (Q, R) {}
+   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+error: aborting due to 2 previous errors
+
diff --git a/src/test/ui/e0119/conflict-with-std.rs b/src/test/ui/e0119/conflict-with-std.rs
new file mode 100644
index 00000000000..ead62256a59
--- /dev/null
+++ b/src/test/ui/e0119/conflict-with-std.rs
@@ -0,0 +1,38 @@
+// 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(try_from)]
+
+use std::marker::PhantomData;
+use std::convert::{TryFrom, AsRef};
+
+struct Q;
+impl AsRef<Q> for Box<Q> {
+    fn as_ref(&self) -> &Q {
+        &**self
+    }
+}
+
+struct S;
+impl From<S> for S {
+    fn from(s: S) -> S {
+        s
+    }
+}
+
+struct X;
+impl TryFrom<X> for X {
+    type Error = ();
+    fn try_from(u: X) -> Result<X, ()> {
+        Ok(u)
+    }
+}
+
+fn main() {}
\ No newline at end of file
diff --git a/src/test/ui/e0119/conflict-with-std.stderr b/src/test/ui/e0119/conflict-with-std.stderr
new file mode 100644
index 00000000000..f3e33291ef5
--- /dev/null
+++ b/src/test/ui/e0119/conflict-with-std.stderr
@@ -0,0 +1,44 @@
+error[E0119]: conflicting implementations of trait `std::convert::AsRef<Q>` for type `std::boxed::Box<Q>`:
+  --> $DIR/conflict-with-std.rs:17:1
+   |
+17 | / impl AsRef<Q> for Box<Q> {
+18 | |     fn as_ref(&self) -> &Q {
+19 | |         &**self
+20 | |     }
+21 | | }
+   | |_^
+   |
+   = note: conflicting implementation in crate `alloc`:
+           - impl<T> std::convert::AsRef<T> for std::boxed::Box<T>
+             where T: ?Sized;
+
+error[E0119]: conflicting implementations of trait `std::convert::From<S>` for type `S`:
+  --> $DIR/conflict-with-std.rs:24:1
+   |
+24 | / impl From<S> for S {
+25 | |     fn from(s: S) -> S {
+26 | |         s
+27 | |     }
+28 | | }
+   | |_^
+   |
+   = note: conflicting implementation in crate `core`:
+           - impl<T> std::convert::From<T> for T;
+
+error[E0119]: conflicting implementations of trait `std::convert::TryFrom<X>` for type `X`:
+  --> $DIR/conflict-with-std.rs:31:1
+   |
+31 | / impl TryFrom<X> for X {
+32 | |     type Error = ();
+33 | |     fn try_from(u: X) -> Result<X, ()> {
+34 | |         Ok(u)
+35 | |     }
+36 | | }
+   | |_^
+   |
+   = note: conflicting implementation in crate `core`:
+           - impl<T, U> std::convert::TryFrom<U> for T
+             where T: std::convert::From<U>;
+
+error: aborting due to 3 previous errors
+
diff --git a/src/test/ui/e0119/issue-23563.rs b/src/test/ui/e0119/issue-23563.rs
new file mode 100644
index 00000000000..67710af9369
--- /dev/null
+++ b/src/test/ui/e0119/issue-23563.rs
@@ -0,0 +1,39 @@
+// 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.
+
+// aux-build:issue_23563_a.rs
+
+// Ref: https://github.com/rust-lang/rust/issues/23563#issuecomment-260751672
+
+extern crate issue_23563_a as a;
+
+use a::LolFrom;
+use a::LolInto;
+use a::LolTo;
+
+struct LocalType<T>(Option<T>);
+
+impl<'a, T> LolFrom<&'a [T]> for LocalType<T> {
+    fn from(_: &'a [T]) -> LocalType<T> { LocalType(None) }
+}
+
+impl<T> LolInto<LocalType<T>> for LocalType<T> {
+    fn convert_into(self) -> LocalType<T> {
+        self
+    }
+}
+
+impl LolTo<LocalType<u8>> for [u8] {
+    fn convert_to(&self) -> LocalType<u8> {
+        LocalType(None)
+    }
+}
+
+fn main() {}
\ No newline at end of file
diff --git a/src/test/ui/e0119/issue-23563.stderr b/src/test/ui/e0119/issue-23563.stderr
new file mode 100644
index 00000000000..dcb76d71b3d
--- /dev/null
+++ b/src/test/ui/e0119/issue-23563.stderr
@@ -0,0 +1,14 @@
+error[E0119]: conflicting implementations of trait `a::LolFrom<&[_]>` for type `LocalType<_>`:
+  --> $DIR/issue-23563.rs:23:1
+   |
+23 | / impl<'a, T> LolFrom<&'a [T]> for LocalType<T> {
+24 | |     fn from(_: &'a [T]) -> LocalType<T> { LocalType(None) }
+25 | | }
+   | |_^
+   |
+   = note: conflicting implementation in crate `issue_23563_a`:
+           - impl<T, U> a::LolFrom<T> for U
+             where T: a::LolInto<U>;
+
+error: aborting due to previous error
+
diff --git a/src/test/ui/e0119/issue-27403.rs b/src/test/ui/e0119/issue-27403.rs
new file mode 100644
index 00000000000..c880921b65b
--- /dev/null
+++ b/src/test/ui/e0119/issue-27403.rs
@@ -0,0 +1,21 @@
+// 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.
+
+pub struct GenX<S> {
+    inner: S,
+}
+
+impl<S> Into<S> for GenX<S> {
+    fn into(self) -> S {
+        self.inner
+    }
+}
+
+fn main() {}
\ No newline at end of file
diff --git a/src/test/ui/e0119/issue-27403.stderr b/src/test/ui/e0119/issue-27403.stderr
new file mode 100644
index 00000000000..d03171fc10a
--- /dev/null
+++ b/src/test/ui/e0119/issue-27403.stderr
@@ -0,0 +1,16 @@
+error[E0119]: conflicting implementations of trait `std::convert::Into<_>` for type `GenX<_>`:
+  --> $DIR/issue-27403.rs:15:1
+   |
+15 | / impl<S> Into<S> for GenX<S> {
+16 | |     fn into(self) -> S {
+17 | |         self.inner
+18 | |     }
+19 | | }
+   | |_^
+   |
+   = note: conflicting implementation in crate `core`:
+           - impl<T, U> std::convert::Into<U> for T
+             where U: std::convert::From<T>;
+
+error: aborting due to previous error
+
diff --git a/src/test/ui/e0119/issue-28981.rs b/src/test/ui/e0119/issue-28981.rs
new file mode 100644
index 00000000000..06018286b31
--- /dev/null
+++ b/src/test/ui/e0119/issue-28981.rs
@@ -0,0 +1,17 @@
+// 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::ops::Deref;
+
+struct Foo;
+
+impl<Foo> Deref for Foo { }
+
+fn main() {}
\ No newline at end of file
diff --git a/src/test/ui/e0119/issue-28981.stderr b/src/test/ui/e0119/issue-28981.stderr
new file mode 100644
index 00000000000..c6c7c117a42
--- /dev/null
+++ b/src/test/ui/e0119/issue-28981.stderr
@@ -0,0 +1,18 @@
+error[E0119]: conflicting implementations of trait `std::ops::Deref` for type `&_`:
+  --> $DIR/issue-28981.rs:15:1
+   |
+15 | impl<Foo> Deref for Foo { }
+   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^
+   |
+   = note: conflicting implementation in crate `core`:
+           - impl<'a, T> std::ops::Deref for &'a T
+             where T: ?Sized;
+
+error[E0210]: type parameter `Foo` must be used as the type parameter for some local type (e.g. `MyStruct<T>`); only traits defined in the current crate can be implemented for a type parameter
+  --> $DIR/issue-28981.rs:15:1
+   |
+15 | impl<Foo> Deref for Foo { }
+   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+error: aborting due to 2 previous errors
+
diff --git a/src/test/ui/e0119/so-37347311.rs b/src/test/ui/e0119/so-37347311.rs
new file mode 100644
index 00000000000..0d21120eac3
--- /dev/null
+++ b/src/test/ui/e0119/so-37347311.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.
+
+// Ref: https://stackoverflow.com/q/37347311
+
+trait Storage {
+    type Error;
+}
+
+enum MyError<S: Storage> {
+    StorageProblem(S::Error),
+}
+
+impl<S: Storage> From<S::Error> for MyError<S> {
+    fn from(error: S::Error) -> MyError<S> {
+        MyError::StorageProblem(error)
+    }
+}
+
+fn main() {}
\ No newline at end of file
diff --git a/src/test/ui/e0119/so-37347311.stderr b/src/test/ui/e0119/so-37347311.stderr
new file mode 100644
index 00000000000..8a26597a1c2
--- /dev/null
+++ b/src/test/ui/e0119/so-37347311.stderr
@@ -0,0 +1,15 @@
+error[E0119]: conflicting implementations of trait `std::convert::From<MyError<_>>` for type `MyError<_>`:
+  --> $DIR/so-37347311.rs:21:1
+   |
+21 | / impl<S: Storage> From<S::Error> for MyError<S> {
+22 | |     fn from(error: S::Error) -> MyError<S> {
+23 | |         MyError::StorageProblem(error)
+24 | |     }
+25 | | }
+   | |_^
+   |
+   = note: conflicting implementation in crate `core`:
+           - impl<T> std::convert::From<T> for T;
+
+error: aborting due to previous error
+