Auto merge of #46192 - arielb1:locally-coherent, r=nikomatsakis

coherence: fix is_knowable logic

A trait-ref that passes the orphan-check rules can still be implemented in a crate downstream from our crate (for example, `LocalType for LocalTrait<_>` might be matched by a `LocalType for LocalTrait<TypeFromDownstreamCrate>`), and this should be known by the `is_knowable`  logic.

Trait selection had a hackfix for this, but it's an hacky fix that does not handle all cases. This patch removes it.

fixes #43355.

r? @nikomatsakis

Needs a crater run

10 files changed, 453 insertions, 141 deletions

diff --git a/src/librustc/lint/builtin.rs b/src/librustc/lint/builtin.rs
index 1008da1e937..d352d359e20 100644
--- a/src/librustc/lint/builtin.rs
+++ b/src/librustc/lint/builtin.rs
@@ -205,6 +205,12 @@ declare_lint! {
 }
 
 declare_lint! {
+    pub INCOHERENT_FUNDAMENTAL_IMPLS,
+    Warn,
+    "potentially-conflicting impls were erroneously allowed"
+}
+
+declare_lint! {
     pub DEPRECATED,
     Warn,
     "detects use of deprecated items"
@@ -267,6 +273,7 @@ impl LintPass for HardwiredLints {
             MISSING_FRAGMENT_SPECIFIER,
             PARENTHESIZED_PARAMS_IN_TYPES_AND_MODULES,
             LATE_BOUND_LIFETIME_ARGUMENTS,
+            INCOHERENT_FUNDAMENTAL_IMPLS,
             DEPRECATED,
             UNUSED_UNSAFE,
             UNUSED_MUT,
diff --git a/src/librustc/traits/coherence.rs b/src/librustc/traits/coherence.rs
index 10a32c26e74..7d1f3b31bfc 100644
--- a/src/librustc/traits/coherence.rs
+++ b/src/librustc/traits/coherence.rs
@@ -13,14 +13,27 @@
 use hir::def_id::{DefId, LOCAL_CRATE};
 use syntax_pos::DUMMY_SP;
 use traits::{self, Normalized, SelectionContext, Obligation, ObligationCause, Reveal};
+use traits::IntercrateMode;
 use traits::select::IntercrateAmbiguityCause;
 use ty::{self, Ty, TyCtxt};
+use ty::fold::TypeFoldable;
 use ty::subst::Subst;
 
 use infer::{InferCtxt, InferOk};
 
-#[derive(Copy, Clone)]
-struct InferIsLocal(bool);
+/// Whether we do the orphan check relative to this crate or
+/// to some remote crate.
+#[derive(Copy, Clone, Debug)]
+enum InCrate {
+    Local,
+    Remote
+}
+
+#[derive(Debug, Copy, Clone)]
+pub enum Conflict {
+    Upstream,
+    Downstream { used_to_be_broken: bool }
+}
 
 pub struct OverlapResult<'tcx> {
     pub impl_header: ty::ImplHeader<'tcx>,
@@ -31,16 +44,19 @@ pub struct OverlapResult<'tcx> {
 /// `ImplHeader` with those types substituted
 pub fn overlapping_impls<'cx, 'gcx, 'tcx>(infcx: &InferCtxt<'cx, 'gcx, 'tcx>,
                                           impl1_def_id: DefId,
-                                          impl2_def_id: DefId)
+                                          impl2_def_id: DefId,
+                                          intercrate_mode: IntercrateMode)
                                           -> Option<OverlapResult<'tcx>>
 {
     debug!("impl_can_satisfy(\
            impl1_def_id={:?}, \
-           impl2_def_id={:?})",
+           impl2_def_id={:?},
+           intercrate_mode={:?})",
            impl1_def_id,
-           impl2_def_id);
+           impl2_def_id,
+           intercrate_mode);
 
-    let selcx = &mut SelectionContext::intercrate(infcx);
+    let selcx = &mut SelectionContext::intercrate(infcx, intercrate_mode);
     overlap(selcx, impl1_def_id, impl2_def_id)
 }
 
@@ -126,32 +142,49 @@ fn overlap<'cx, 'gcx, 'tcx>(selcx: &mut SelectionContext<'cx, 'gcx, 'tcx>,
 }
 
 pub fn trait_ref_is_knowable<'a, 'gcx, 'tcx>(tcx: TyCtxt<'a, 'gcx, 'tcx>,
-                                             trait_ref: ty::TraitRef<'tcx>) -> bool
+                                             trait_ref: ty::TraitRef<'tcx>)
+                                             -> Option<Conflict>
 {
     debug!("trait_ref_is_knowable(trait_ref={:?})", trait_ref);
-
-    // if the orphan rules pass, that means that no ancestor crate can
-    // impl this, so it's up to us.
-    if orphan_check_trait_ref(tcx, trait_ref, InferIsLocal(false)).is_ok() {
-        debug!("trait_ref_is_knowable: orphan check passed");
-        return true;
+    if orphan_check_trait_ref(tcx, trait_ref, InCrate::Remote).is_ok() {
+        // A downstream or cousin crate is allowed to implement some
+        // substitution of this trait-ref.
+
+        // A trait can be implementable for a trait ref by both the current
+        // crate and crates downstream of it. Older versions of rustc
+        // were not aware of this, causing incoherence (issue #43355).
+        let used_to_be_broken =
+            orphan_check_trait_ref(tcx, trait_ref, InCrate::Local).is_ok();
+        if used_to_be_broken {
+            debug!("trait_ref_is_knowable({:?}) - USED TO BE BROKEN", trait_ref);
+        }
+        return Some(Conflict::Downstream { used_to_be_broken });
     }
 
-    // if the trait is not marked fundamental, then it's always possible that
-    // an ancestor crate will impl this in the future, if they haven't
-    // already
-    if !trait_ref_is_local_or_fundamental(tcx, trait_ref) {
-        debug!("trait_ref_is_knowable: trait is neither local nor fundamental");
-        return false;
+    if trait_ref_is_local_or_fundamental(tcx, trait_ref) {
+        // This is a local or fundamental trait, so future-compatibility
+        // is no concern. We know that downstream/cousin crates are not
+        // allowed to implement a substitution of this trait ref, which
+        // means impls could only come from dependencies of this crate,
+        // which we already know about.
+        return None;
     }
 
-    // find out when some downstream (or cousin) crate could impl this
-    // trait-ref, presuming that all the parameters were instantiated
-    // with downstream types. If not, then it could only be
-    // implemented by an upstream crate, which means that the impl
-    // must be visible to us, and -- since the trait is fundamental
-    // -- we can test.
-    orphan_check_trait_ref(tcx, trait_ref, InferIsLocal(true)).is_err()
+    // This is a remote non-fundamental trait, so if another crate
+    // can be the "final owner" of a substitution of this trait-ref,
+    // they are allowed to implement it future-compatibly.
+    //
+    // However, if we are a final owner, then nobody else can be,
+    // and if we are an intermediate owner, then we don't care
+    // about future-compatibility, which means that we're OK if
+    // we are an owner.
+    if orphan_check_trait_ref(tcx, trait_ref, InCrate::Local).is_ok() {
+        debug!("trait_ref_is_knowable: orphan check passed");
+        return None;
+    } else {
+        debug!("trait_ref_is_knowable: nonlocal, nonfundamental, unowned");
+        return Some(Conflict::Upstream);
+    }
 }
 
 pub fn trait_ref_is_local_or_fundamental<'a, 'gcx, 'tcx>(tcx: TyCtxt<'a, 'gcx, 'tcx>,
@@ -189,30 +222,123 @@ pub fn orphan_check<'a, 'gcx, 'tcx>(tcx: TyCtxt<'a, 'gcx, 'tcx>,
         return Ok(());
     }
 
-    orphan_check_trait_ref(tcx, trait_ref, InferIsLocal(false))
+    orphan_check_trait_ref(tcx, trait_ref, InCrate::Local)
 }
 
+/// Check whether a trait-ref is potentially implementable by a crate.
+///
+/// The current rule is that a trait-ref orphan checks in a crate C:
+///
+/// 1. Order the parameters in the trait-ref in subst order - Self first,
+///    others linearly (e.g. `<U as Foo<V, W>>` is U < V < W).
+/// 2. Of these type parameters, there is at least one type parameter
+///    in which, walking the type as a tree, you can reach a type local
+///    to C where all types in-between are fundamental types. Call the
+///    first such parameter the "local key parameter".
+///     - e.g. `Box<LocalType>` is OK, because you can visit LocalType
+///       going through `Box`, which is fundamental.
+///     - similarly, `FundamentalPair<Vec<()>, Box<LocalType>>` is OK for
+///       the same reason.
+///     - but (knowing that `Vec<T>` is non-fundamental, and assuming it's
+///       not local), `Vec<LocalType>` is bad, because `Vec<->` is between
+///       the local type and the type parameter.
+/// 3. Every type parameter before the local key parameter is fully known in C.
+///     - e.g. `impl<T> T: Trait<LocalType>` is bad, because `T` might be
+///       an unknown type.
+///     - but `impl<T> LocalType: Trait<T>` is OK, because `LocalType`
+///       occurs before `T`.
+/// 4. Every type in the local key parameter not known in C, going
+///    through the parameter's type tree, must appear only as a subtree of
+///    a type local to C, with only fundamental types between the type
+///    local to C and the local key parameter.
+///     - e.g. `Vec<LocalType<T>>>` (or equivalently `Box<Vec<LocalType<T>>>`)
+///     is bad, because the only local type with `T` as a subtree is
+///     `LocalType<T>`, and `Vec<->` is between it and the type parameter.
+///     - similarly, `FundamentalPair<LocalType<T>, T>` is bad, because
+///     the second occurence of `T` is not a subtree of *any* local type.
+///     - however, `LocalType<Vec<T>>` is OK, because `T` is a subtree of
+///     `LocalType<Vec<T>>`, which is local and has no types between it and
+///     the type parameter.
+///
+/// The orphan rules actually serve several different purposes:
+///
+/// 1. They enable link-safety - i.e. 2 mutually-unknowing crates (where
+///    every type local to one crate is unknown in the other) can't implement
+///    the same trait-ref. This follows because it can be seen that no such
+///    type can orphan-check in 2 such crates.
+///
+///    To check that a local impl follows the orphan rules, we check it in
+///    InCrate::Local mode, using type parameters for the "generic" types.
+///
+/// 2. They ground negative reasoning for coherence. If a user wants to
+///    write both a conditional blanket impl and a specific impl, we need to
+///    make sure they do not overlap. For example, if we write
+///    ```
+///    impl<T> IntoIterator for Vec<T>
+///    impl<T: Iterator> IntoIterator for T
+///    ```
+///    We need to be able to prove that `Vec<$0>: !Iterator` for every type $0.
+///    We can observe that this holds in the current crate, but we need to make
+///    sure this will also hold in all unknown crates (both "independent" crates,
+///    which we need for link-safety, and also child crates, because we don't want
+///    child crates to get error for impl conflicts in a *dependency*).
+///
+///    For that, we only allow negative reasoning if, for every assignment to the
+///    inference variables, every unknown crate would get an orphan error if they
+///    try to implement this trait-ref. To check for this, we use InCrate::Remote
+///    mode. That is sound because we already know all the impls from known crates.
+///
+/// 3. For non-#[fundamental] traits, they guarantee that parent crates can
+///    add "non-blanket" impls without breaking negative reasoning in dependent
+///    crates. This is the "rebalancing coherence" (RFC 1023) restriction.
+///
+///    For that, we only a allow crate to perform negative reasoning on
+///    non-local-non-#[fundamental] only if there's a local key parameter as per (2).
+///
+///    Because we never perform negative reasoning generically (coherence does
+///    not involve type parameters), this can be interpreted as doing the full
+///    orphan check (using InCrate::Local mode), substituting non-local known
+///    types for all inference variables.
+///
+///    This allows for crates to future-compatibly add impls as long as they
+///    can't apply to types with a key parameter in a child crate - applying
+///    the rules, this basically means that every type parameter in the impl
+///    must appear behind a non-fundamental type (because this is not a
+///    type-system requirement, crate owners might also go for "semantic
+///    future-compatibility" involving things such as sealed traits, but
+///    the above requirement is sufficient, and is necessary in "open world"
+///    cases).
+///
+/// Note that this function is never called for types that have both type
+/// parameters and inference variables.
 fn orphan_check_trait_ref<'tcx>(tcx: TyCtxt,
                                 trait_ref: ty::TraitRef<'tcx>,
-                                infer_is_local: InferIsLocal)
+                                in_crate: InCrate)
                                 -> Result<(), OrphanCheckErr<'tcx>>
 {
-    debug!("orphan_check_trait_ref(trait_ref={:?}, infer_is_local={})",
-           trait_ref, infer_is_local.0);
+    debug!("orphan_check_trait_ref(trait_ref={:?}, in_crate={:?})",
+           trait_ref, in_crate);
+
+    if trait_ref.needs_infer() && trait_ref.needs_subst() {
+        bug!("can't orphan check a trait ref with both params and inference variables {:?}",
+             trait_ref);
+    }
 
     // First, create an ordered iterator over all the type parameters to the trait, with the self
     // type appearing first.
     // Find the first input type that either references a type parameter OR
     // some local type.
     for input_ty in trait_ref.input_types() {
-        if ty_is_local(tcx, input_ty, infer_is_local) {
+        if ty_is_local(tcx, input_ty, in_crate) {
             debug!("orphan_check_trait_ref: ty_is_local `{:?}`", input_ty);
 
             // First local input type. Check that there are no
             // uncovered type parameters.
-            let uncovered_tys = uncovered_tys(tcx, input_ty, infer_is_local);
+            let uncovered_tys = uncovered_tys(tcx, input_ty, in_crate);
             for uncovered_ty in uncovered_tys {
-                if let Some(param) = uncovered_ty.walk().find(|t| is_type_parameter(t)) {
+                if let Some(param) = uncovered_ty.walk()
+                    .find(|t| is_possibly_remote_type(t, in_crate))
+                {
                     debug!("orphan_check_trait_ref: uncovered type `{:?}`", param);
                     return Err(OrphanCheckErr::UncoveredTy(param));
                 }
@@ -224,11 +350,11 @@ fn orphan_check_trait_ref<'tcx>(tcx: TyCtxt,
 
         // Otherwise, enforce invariant that there are no type
         // parameters reachable.
-        if !infer_is_local.0 {
-            if let Some(param) = input_ty.walk().find(|t| is_type_parameter(t)) {
-                debug!("orphan_check_trait_ref: uncovered type `{:?}`", param);
-                return Err(OrphanCheckErr::UncoveredTy(param));
-            }
+        if let Some(param) = input_ty.walk()
+            .find(|t| is_possibly_remote_type(t, in_crate))
+        {
+            debug!("orphan_check_trait_ref: uncovered type `{:?}`", param);
+            return Err(OrphanCheckErr::UncoveredTy(param));
         }
     }
 
@@ -237,29 +363,29 @@ fn orphan_check_trait_ref<'tcx>(tcx: TyCtxt,
     return Err(OrphanCheckErr::NoLocalInputType);
 }
 
-fn uncovered_tys<'tcx>(tcx: TyCtxt, ty: Ty<'tcx>, infer_is_local: InferIsLocal)
+fn uncovered_tys<'tcx>(tcx: TyCtxt, ty: Ty<'tcx>, in_crate: InCrate)
                        -> Vec<Ty<'tcx>> {
-    if ty_is_local_constructor(ty, infer_is_local) {
+    if ty_is_local_constructor(ty, in_crate) {
         vec![]
     } else if fundamental_ty(tcx, ty) {
         ty.walk_shallow()
-          .flat_map(|t| uncovered_tys(tcx, t, infer_is_local))
+          .flat_map(|t| uncovered_tys(tcx, t, in_crate))
           .collect()
     } else {
         vec![ty]
     }
 }
 
-fn is_type_parameter(ty: Ty) -> bool {
+fn is_possibly_remote_type(ty: Ty, _in_crate: InCrate) -> bool {
     match ty.sty {
         ty::TyProjection(..) | ty::TyParam(..) => true,
         _ => false,
     }
 }
 
-fn ty_is_local(tcx: TyCtxt, ty: Ty, infer_is_local: InferIsLocal) -> bool {
-    ty_is_local_constructor(ty, infer_is_local) ||
-        fundamental_ty(tcx, ty) && ty.walk_shallow().any(|t| ty_is_local(tcx, t, infer_is_local))
+fn ty_is_local(tcx: TyCtxt, ty: Ty, in_crate: InCrate) -> bool {
+    ty_is_local_constructor(ty, in_crate) ||
+        fundamental_ty(tcx, ty) && ty.walk_shallow().any(|t| ty_is_local(tcx, t, in_crate))
 }
 
 fn fundamental_ty(tcx: TyCtxt, ty: Ty) -> bool {
@@ -273,7 +399,16 @@ fn fundamental_ty(tcx: TyCtxt, ty: Ty) -> bool {
     }
 }
 
-fn ty_is_local_constructor(ty: Ty, infer_is_local: InferIsLocal)-> bool {
+fn def_id_is_local(def_id: DefId, in_crate: InCrate) -> bool {
+    match in_crate {
+        // The type is local to *this* crate - it will not be
+        // local in any other crate.
+        InCrate::Remote => false,
+        InCrate::Local => def_id.is_local()
+    }
+}
+
+fn ty_is_local_constructor(ty: Ty, in_crate: InCrate) -> bool {
     debug!("ty_is_local_constructor({:?})", ty);
 
     match ty.sty {
@@ -296,20 +431,20 @@ fn ty_is_local_constructor(ty: Ty, infer_is_local: InferIsLocal)-> bool {
             false
         }
 
-        ty::TyInfer(..) => {
-            infer_is_local.0
-        }
+        ty::TyInfer(..) => match in_crate {
+            InCrate::Local => false,
+            // The inference variable might be unified with a local
+            // type in that remote crate.
+            InCrate::Remote => true,
+        },
 
-        ty::TyAdt(def, _) => {
-            def.did.is_local()
-        }
-
-        ty::TyForeign(did) => {
-            did.is_local()
-        }
+        ty::TyAdt(def, _) => def_id_is_local(def.did, in_crate),
+        ty::TyForeign(did) => def_id_is_local(did, in_crate),
 
         ty::TyDynamic(ref tt, ..) => {
-            tt.principal().map_or(false, |p| p.def_id().is_local())
+            tt.principal().map_or(false, |p| {
+                def_id_is_local(p.def_id(), in_crate)
+            })
         }
 
         ty::TyError => {
diff --git a/src/librustc/traits/mod.rs b/src/librustc/traits/mod.rs
index d6f8a5f9cc6..94605d895a5 100644
--- a/src/librustc/traits/mod.rs
+++ b/src/librustc/traits/mod.rs
@@ -60,6 +60,13 @@ mod structural_impls;
 pub mod trans;
 mod util;
 
+// Whether to enable bug compatibility with issue #43355
+#[derive(Copy, Clone, PartialEq, Eq, Debug)]
+pub enum IntercrateMode {
+    Issue43355,
+    Fixed
+}
+
 /// An `Obligation` represents some trait reference (e.g. `int:Eq`) for
 /// which the vtable must be found.  The process of finding a vtable is
 /// called "resolving" the `Obligation`. This process consists of
diff --git a/src/librustc/traits/select.rs b/src/librustc/traits/select.rs
index 91e6c4270b3..0c4071b8b5d 100644
--- a/src/librustc/traits/select.rs
+++ b/src/librustc/traits/select.rs
@@ -13,8 +13,9 @@
 use self::SelectionCandidate::*;
 use self::EvaluationResult::*;
 
-use super::coherence;
+use super::coherence::{self, Conflict};
 use super::DerivedObligationCause;
+use super::IntercrateMode;
 use super::project;
 use super::project::{normalize_with_depth, Normalized, ProjectionCacheKey};
 use super::{PredicateObligation, TraitObligation, ObligationCause};
@@ -87,7 +88,7 @@ pub struct SelectionContext<'cx, 'gcx: 'cx+'tcx, 'tcx: 'cx> {
     /// other words, we consider `$0 : Bar` to be unimplemented if
     /// there is no type that the user could *actually name* that
     /// would satisfy it. This avoids crippling inference, basically.
-    intercrate: bool,
+    intercrate: Option<IntercrateMode>,
 
     inferred_obligations: SnapshotVec<InferredObligationsSnapshotVecDelegate<'tcx>>,
 
@@ -111,21 +112,24 @@ impl IntercrateAmbiguityCause {
     /// See #23980 for details.
     pub fn add_intercrate_ambiguity_hint<'a, 'tcx>(&self,
                                                    err: &mut ::errors::DiagnosticBuilder) {
+        err.note(&self.intercrate_ambiguity_hint());
+    }
+
+    pub fn intercrate_ambiguity_hint(&self) -> String {
         match self {
             &IntercrateAmbiguityCause::DownstreamCrate { ref trait_desc, ref self_desc } => {
                 let self_desc = if let &Some(ref ty) = self_desc {
                     format!(" for type `{}`", ty)
                 } else { "".to_string() };
-                err.note(&format!("downstream crates may implement trait `{}`{}",
-                                  trait_desc, self_desc));
+                format!("downstream crates may implement trait `{}`{}", trait_desc, self_desc)
             }
             &IntercrateAmbiguityCause::UpstreamCrateUpdate { ref trait_desc, ref self_desc } => {
                 let self_desc = if let &Some(ref ty) = self_desc {
                     format!(" for type `{}`", ty)
                 } else { "".to_string() };
-                err.note(&format!("upstream crates may add new impl of trait `{}`{} \
-                                  in future versions",
-                                  trait_desc, self_desc));
+                format!("upstream crates may add new impl of trait `{}`{} \
+                         in future versions",
+                        trait_desc, self_desc)
             }
         }
     }
@@ -417,17 +421,19 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
         SelectionContext {
             infcx,
             freshener: infcx.freshener(),
-            intercrate: false,
+            intercrate: None,
             inferred_obligations: SnapshotVec::new(),
             intercrate_ambiguity_causes: Vec::new(),
         }
     }
 
-    pub fn intercrate(infcx: &'cx InferCtxt<'cx, 'gcx, 'tcx>) -> SelectionContext<'cx, 'gcx, 'tcx> {
+    pub fn intercrate(infcx: &'cx InferCtxt<'cx, 'gcx, 'tcx>,
+                      mode: IntercrateMode) -> SelectionContext<'cx, 'gcx, 'tcx> {
+        debug!("intercrate({:?})", mode);
         SelectionContext {
             infcx,
             freshener: infcx.freshener(),
-            intercrate: true,
+            intercrate: Some(mode),
             inferred_obligations: SnapshotVec::new(),
             intercrate_ambiguity_causes: Vec::new(),
         }
@@ -758,7 +764,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
         debug!("evaluate_trait_predicate_recursively({:?})",
                obligation);
 
-        if !self.intercrate && obligation.is_global() {
+        if !self.intercrate.is_some() && obligation.is_global() {
             // If a param env is consistent, global obligations do not depend on its particular
             // value in order to work, so we can clear out the param env and get better
             // caching. (If the current param env is inconsistent, we don't care what happens).
@@ -814,7 +820,11 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
         // terms of `Fn` etc, but we could probably make this more
         // precise still.
         let unbound_input_types = stack.fresh_trait_ref.input_types().any(|ty| ty.is_fresh());
-        if unbound_input_types && self.intercrate {
+        // this check was an imperfect workaround for a bug n the old
+        // intercrate mode, it should be removed when that goes away.
+        if unbound_input_types &&
+            self.intercrate == Some(IntercrateMode::Issue43355)
+        {
             debug!("evaluate_stack({:?}) --> unbound argument, intercrate -->  ambiguous",
                    stack.fresh_trait_ref);
             // Heuristics: show the diagnostics when there are no candidates in crate.
@@ -1077,28 +1087,32 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
             return Ok(None);
         }
 
-        if !self.is_knowable(stack) {
-            debug!("coherence stage: not knowable");
-            // Heuristics: show the diagnostics when there are no candidates in crate.
-            let candidate_set = self.assemble_candidates(stack)?;
-            if !candidate_set.ambiguous && candidate_set.vec.is_empty() {
-                let trait_ref = stack.obligation.predicate.skip_binder().trait_ref;
-                let self_ty = trait_ref.self_ty();
-                let trait_desc = trait_ref.to_string();
-                let self_desc = if self_ty.has_concrete_skeleton() {
-                    Some(self_ty.to_string())
-                } else {
-                    None
-                };
-                let cause = if !coherence::trait_ref_is_local_or_fundamental(self.tcx(),
-                                                                             trait_ref) {
-                    IntercrateAmbiguityCause::UpstreamCrateUpdate { trait_desc, self_desc }
-                } else {
-                    IntercrateAmbiguityCause::DownstreamCrate { trait_desc, self_desc }
-                };
-                self.intercrate_ambiguity_causes.push(cause);
+        match self.is_knowable(stack) {
+            None => {}
+            Some(conflict) => {
+                debug!("coherence stage: not knowable");
+                // Heuristics: show the diagnostics when there are no candidates in crate.
+                let candidate_set = self.assemble_candidates(stack)?;
+                if !candidate_set.ambiguous && candidate_set.vec.iter().all(|c| {
+                    !self.evaluate_candidate(stack, &c).may_apply()
+                }) {
+                    let trait_ref = stack.obligation.predicate.skip_binder().trait_ref;
+                    let self_ty = trait_ref.self_ty();
+                    let trait_desc = trait_ref.to_string();
+                    let self_desc = if self_ty.has_concrete_skeleton() {
+                        Some(self_ty.to_string())
+                    } else {
+                        None
+                    };
+                    let cause = if let Conflict::Upstream = conflict {
+                        IntercrateAmbiguityCause::UpstreamCrateUpdate { trait_desc, self_desc }
+                    } else {
+                        IntercrateAmbiguityCause::DownstreamCrate { trait_desc, self_desc }
+                    };
+                    self.intercrate_ambiguity_causes.push(cause);
+                }
+                return Ok(None);
             }
-            return Ok(None);
         }
 
         let candidate_set = self.assemble_candidates(stack)?;
@@ -1205,12 +1219,12 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
 
     fn is_knowable<'o>(&mut self,
                        stack: &TraitObligationStack<'o, 'tcx>)
-                       -> bool
+                       -> Option<Conflict>
     {
-        debug!("is_knowable(intercrate={})", self.intercrate);
+        debug!("is_knowable(intercrate={:?})", self.intercrate);
 
-        if !self.intercrate {
-            return true;
+        if !self.intercrate.is_some() {
+            return None;
         }
 
         let obligation = &stack.obligation;
@@ -1221,7 +1235,14 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
         // bound regions
         let trait_ref = predicate.skip_binder().trait_ref;
 
-        coherence::trait_ref_is_knowable(self.tcx(), trait_ref)
+        let result = coherence::trait_ref_is_knowable(self.tcx(), trait_ref);
+        if let (Some(Conflict::Downstream { used_to_be_broken: true }),
+                Some(IntercrateMode::Issue43355)) = (result, self.intercrate) {
+            debug!("is_knowable: IGNORING conflict to be bug-compatible with #43355");
+            None
+        } else {
+            result
+        }
     }
 
     /// Returns true if the global caches can be used.
@@ -1246,7 +1267,7 @@ impl<'cx, 'gcx, 'tcx> SelectionContext<'cx, 'gcx, 'tcx> {
         // the master cache. Since coherence executes pretty quickly,
         // it's not worth going to more trouble to increase the
         // hit-rate I don't think.
-        if self.intercrate {
+        if self.intercrate.is_some() {
             return false;
         }
 
diff --git a/src/librustc/traits/specialize/mod.rs b/src/librustc/traits/specialize/mod.rs
index 1b5b0d35ba3..6a96d01d5f9 100644
--- a/src/librustc/traits/specialize/mod.rs
+++ b/src/librustc/traits/specialize/mod.rs
@@ -30,6 +30,8 @@ use ty::{self, TyCtxt, TypeFoldable};
 use syntax_pos::DUMMY_SP;
 use std::rc::Rc;
 
+use lint;
+
 pub mod specialization_graph;
 
 /// Information pertinent to an overlapping impl error.
@@ -325,16 +327,33 @@ pub(super) fn specialization_graph_provider<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx
             // This is where impl overlap checking happens:
             let insert_result = sg.insert(tcx, impl_def_id);
             // Report error if there was one.
-            if let Err(overlap) = insert_result {
-                let mut err = struct_span_err!(tcx.sess,
-                                               tcx.span_of_impl(impl_def_id).unwrap(),
-                                               E0119,
-                                               "conflicting implementations of trait `{}`{}:",
-                                               overlap.trait_desc,
-                                               overlap.self_desc.clone().map_or(String::new(),
-                                                                                |ty| {
-                    format!(" for type `{}`", ty)
-                }));
+            let (overlap, used_to_be_allowed) = match insert_result {
+                Err(overlap) => (Some(overlap), false),
+                Ok(opt_overlap) => (opt_overlap, true)
+            };
+
+            if let Some(overlap) = overlap {
+                let msg = format!("conflicting implementations of trait `{}`{}:{}",
+                    overlap.trait_desc,
+                    overlap.self_desc.clone().map_or(
+                        String::new(), |ty| {
+                            format!(" for type `{}`", ty)
+                        }),
+                    if used_to_be_allowed { " (E0119)" } else { "" }
+                );
+                let mut err = if used_to_be_allowed {
+                    tcx.struct_span_lint_node(
+                        lint::builtin::INCOHERENT_FUNDAMENTAL_IMPLS,
+                        tcx.hir.as_local_node_id(impl_def_id).unwrap(),
+                        tcx.span_of_impl(impl_def_id).unwrap(),
+                        &msg)
+                } else {
+                    struct_span_err!(tcx.sess,
+                                     tcx.span_of_impl(impl_def_id).unwrap(),
+                                     E0119,
+                                     "{}",
+                                     msg)
+                };
 
                 match tcx.span_of_impl(overlap.with_impl) {
                     Ok(span) => {
diff --git a/src/librustc/traits/specialize/specialization_graph.rs b/src/librustc/traits/specialize/specialization_graph.rs
index da9dbc0e2c9..834389e5d00 100644
--- a/src/librustc/traits/specialize/specialization_graph.rs
+++ b/src/librustc/traits/specialize/specialization_graph.rs
@@ -68,7 +68,7 @@ struct Children {
 /// The result of attempting to insert an impl into a group of children.
 enum Inserted {
     /// The impl was inserted as a new child in this group of children.
-    BecameNewSibling,
+    BecameNewSibling(Option<OverlapError>),
 
     /// The impl replaced an existing impl that specializes it.
     Replaced(DefId),
@@ -105,17 +105,39 @@ impl<'a, 'gcx, 'tcx> Children {
               simplified_self: Option<SimplifiedType>)
               -> Result<Inserted, OverlapError>
     {
+        let mut last_lint = None;
+
         for slot in match simplified_self {
             Some(sty) => self.filtered_mut(sty),
             None => self.iter_mut(),
         } {
             let possible_sibling = *slot;
 
+            let overlap_error = |overlap: traits::coherence::OverlapResult| {
+                // overlap, but no specialization; error out
+                let trait_ref = overlap.impl_header.trait_ref.unwrap();
+                let self_ty = trait_ref.self_ty();
+                OverlapError {
+                    with_impl: possible_sibling,
+                    trait_desc: trait_ref.to_string(),
+                    // only report the Self type if it has at least
+                    // some outer concrete shell; otherwise, it's
+                    // not adding much information.
+                    self_desc: if self_ty.has_concrete_skeleton() {
+                        Some(self_ty.to_string())
+                    } else {
+                        None
+                    },
+                    intercrate_ambiguity_causes: overlap.intercrate_ambiguity_causes,
+                }
+            };
+
             let tcx = tcx.global_tcx();
             let (le, ge) = tcx.infer_ctxt().enter(|infcx| {
                 let overlap = traits::overlapping_impls(&infcx,
                                                         possible_sibling,
-                                                        impl_def_id);
+                                                        impl_def_id,
+                                                        traits::IntercrateMode::Issue43355);
                 if let Some(overlap) = overlap {
                     if tcx.impls_are_allowed_to_overlap(impl_def_id, possible_sibling) {
                         return Ok((false, false));
@@ -125,22 +147,7 @@ impl<'a, 'gcx, 'tcx> Children {
                     let ge = tcx.specializes((possible_sibling, impl_def_id));
 
                     if le == ge {
-                        // overlap, but no specialization; error out
-                        let trait_ref = overlap.impl_header.trait_ref.unwrap();
-                        let self_ty = trait_ref.self_ty();
-                        Err(OverlapError {
-                            with_impl: possible_sibling,
-                            trait_desc: trait_ref.to_string(),
-                            // only report the Self type if it has at least
-                            // some outer concrete shell; otherwise, it's
-                            // not adding much information.
-                            self_desc: if self_ty.has_concrete_skeleton() {
-                                Some(self_ty.to_string())
-                            } else {
-                                None
-                            },
-                            intercrate_ambiguity_causes: overlap.intercrate_ambiguity_causes,
-                        })
+                        Err(overlap_error(overlap))
                     } else {
                         Ok((le, ge))
                     }
@@ -163,6 +170,19 @@ impl<'a, 'gcx, 'tcx> Children {
                     *slot = impl_def_id;
                 return Ok(Inserted::Replaced(possible_sibling));
             } else {
+                if !tcx.impls_are_allowed_to_overlap(impl_def_id, possible_sibling) {
+                    tcx.infer_ctxt().enter(|infcx| {
+                        if let Some(overlap) = traits::overlapping_impls(
+                            &infcx,
+                            possible_sibling,
+                            impl_def_id,
+                            traits::IntercrateMode::Fixed)
+                        {
+                            last_lint = Some(overlap_error(overlap));
+                        }
+                    });
+                }
+
                 // no overlap (error bailed already via ?)
             }
         }
@@ -170,7 +190,7 @@ impl<'a, 'gcx, 'tcx> Children {
         // no overlap with any potential siblings, so add as a new sibling
         debug!("placing as new sibling");
         self.insert_blindly(tcx, impl_def_id);
-        Ok(Inserted::BecameNewSibling)
+        Ok(Inserted::BecameNewSibling(last_lint))
     }
 
     fn iter_mut(&'a mut self) -> Box<Iterator<Item = &'a mut DefId> + 'a> {
@@ -199,7 +219,7 @@ impl<'a, 'gcx, 'tcx> Graph {
     pub fn insert(&mut self,
                   tcx: TyCtxt<'a, 'gcx, 'tcx>,
                   impl_def_id: DefId)
-                  -> Result<(), OverlapError> {
+                  -> Result<Option<OverlapError>, OverlapError> {
         assert!(impl_def_id.is_local());
 
         let trait_ref = tcx.impl_trait_ref(impl_def_id).unwrap();
@@ -220,10 +240,11 @@ impl<'a, 'gcx, 'tcx> Graph {
             self.parent.insert(impl_def_id, trait_def_id);
             self.children.entry(trait_def_id).or_insert(Children::new())
                 .insert_blindly(tcx, impl_def_id);
-            return Ok(());
+            return Ok(None);
         }
 
         let mut parent = trait_def_id;
+        let mut last_lint = None;
         let simplified = fast_reject::simplify_type(tcx, trait_ref.self_ty(), false);
 
         // Descend the specialization tree, where `parent` is the current parent node
@@ -234,7 +255,8 @@ impl<'a, 'gcx, 'tcx> Graph {
                 .insert(tcx, impl_def_id, simplified)?;
 
             match insert_result {
-                BecameNewSibling => {
+                BecameNewSibling(opt_lint) => {
+                    last_lint = opt_lint;
                     break;
                 }
                 Replaced(new_child) => {
@@ -251,7 +273,7 @@ impl<'a, 'gcx, 'tcx> Graph {
         }
 
         self.parent.insert(impl_def_id, parent);
-        Ok(())
+        Ok(last_lint)
     }
 
     /// Insert cached metadata mapping from a child impl back to its parent.
diff --git a/src/librustc_lint/lib.rs b/src/librustc_lint/lib.rs
index fc05f8f0dc2..8b41dd62742 100644
--- a/src/librustc_lint/lib.rs
+++ b/src/librustc_lint/lib.rs
@@ -248,10 +248,13 @@ pub fn register_builtins(store: &mut lint::LintStore, sess: Option<&Session>) {
             reference: "issue #46043 <https://github.com/rust-lang/rust/issues/46043>",
         },
         FutureIncompatibleInfo {
+            id: LintId::of(INCOHERENT_FUNDAMENTAL_IMPLS),
+            reference: "issue #46205 <https://github.com/rust-lang/rust/issues/46205>",
+        },
+        FutureIncompatibleInfo {
             id: LintId::of(COERCE_NEVER),
             reference: "issue #46325 <https://github.com/rust-lang/rust/issues/46325>",
         },
-
         ]);
 
     // Register renamed and removed lints
diff --git a/src/librustc_typeck/coherence/inherent_impls_overlap.rs b/src/librustc_typeck/coherence/inherent_impls_overlap.rs
index 1355f711a4b..07d5f813cbb 100644
--- a/src/librustc_typeck/coherence/inherent_impls_overlap.rs
+++ b/src/librustc_typeck/coherence/inherent_impls_overlap.rs
@@ -12,9 +12,11 @@ use namespace::Namespace;
 use rustc::hir::def_id::{CrateNum, DefId, LOCAL_CRATE};
 use rustc::hir;
 use rustc::hir::itemlikevisit::ItemLikeVisitor;
-use rustc::traits;
+use rustc::traits::{self, IntercrateMode};
 use rustc::ty::TyCtxt;
 
+use lint;
+
 pub fn crate_inherent_impls_overlap_check<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
                                                     crate_num: CrateNum) {
     assert_eq!(crate_num, LOCAL_CRATE);
@@ -28,7 +30,8 @@ struct InherentOverlapChecker<'a, 'tcx: 'a> {
 
 impl<'a, 'tcx> InherentOverlapChecker<'a, 'tcx> {
     fn check_for_common_items_in_impls(&self, impl1: DefId, impl2: DefId,
-                                       overlap: traits::OverlapResult) {
+                                       overlap: traits::OverlapResult,
+                                       used_to_be_allowed: bool) {
 
         let name_and_namespace = |def_id| {
             let item = self.tcx.associated_item(def_id);
@@ -43,11 +46,21 @@ impl<'a, 'tcx> InherentOverlapChecker<'a, 'tcx> {
 
             for &item2 in &impl_items2[..] {
                 if (name, namespace) == name_and_namespace(item2) {
-                    let mut err = struct_span_err!(self.tcx.sess,
-                                                   self.tcx.span_of_impl(item1).unwrap(),
-                                                   E0592,
-                                                   "duplicate definitions with name `{}`",
-                                                   name);
+                    let node_id = self.tcx.hir.as_local_node_id(impl1);
+                    let mut err = if used_to_be_allowed && node_id.is_some() {
+                        self.tcx.struct_span_lint_node(
+                            lint::builtin::INCOHERENT_FUNDAMENTAL_IMPLS,
+                            node_id.unwrap(),
+                            self.tcx.span_of_impl(item1).unwrap(),
+                            &format!("duplicate definitions with name `{}` (E0592)", name)
+                        )
+                    } else {
+                        struct_span_err!(self.tcx.sess,
+                                         self.tcx.span_of_impl(item1).unwrap(),
+                                         E0592,
+                                         "duplicate definitions with name `{}`",
+                                         name)
+                    };
 
                     err.span_label(self.tcx.span_of_impl(item1).unwrap(),
                                    format!("duplicate definitions for `{}`", name));
@@ -69,12 +82,30 @@ impl<'a, 'tcx> InherentOverlapChecker<'a, 'tcx> {
 
         for (i, &impl1_def_id) in impls.iter().enumerate() {
             for &impl2_def_id in &impls[(i + 1)..] {
-                self.tcx.infer_ctxt().enter(|infcx| {
+                let used_to_be_allowed = self.tcx.infer_ctxt().enter(|infcx| {
                     if let Some(overlap) =
-                            traits::overlapping_impls(&infcx, impl1_def_id, impl2_def_id) {
-                        self.check_for_common_items_in_impls(impl1_def_id, impl2_def_id, overlap)
+                        traits::overlapping_impls(&infcx, impl1_def_id, impl2_def_id,
+                                                  IntercrateMode::Issue43355)
+                    {
+                        self.check_for_common_items_in_impls(
+                            impl1_def_id, impl2_def_id, overlap, false);
+                        false
+                    } else {
+                        true
                     }
                 });
+
+                if used_to_be_allowed {
+                    self.tcx.infer_ctxt().enter(|infcx| {
+                        if let Some(overlap) =
+                            traits::overlapping_impls(&infcx, impl1_def_id, impl2_def_id,
+                                                      IntercrateMode::Fixed)
+                        {
+                            self.check_for_common_items_in_impls(
+                                impl1_def_id, impl2_def_id, overlap, true);
+                        }
+                    });
+                }
             }
         }
     }
@@ -100,4 +131,3 @@ impl<'a, 'tcx, 'v> ItemLikeVisitor<'v> for InherentOverlapChecker<'a, 'tcx> {
     fn visit_impl_item(&mut self, _impl_item: &hir::ImplItem) {
     }
 }
-
diff --git a/src/test/compile-fail/issue-43355.rs b/src/test/compile-fail/issue-43355.rs
new file mode 100644
index 00000000000..4db5c84df9a
--- /dev/null
+++ b/src/test/compile-fail/issue-43355.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.
+
+#![deny(incoherent_fundamental_impls)]
+
+pub trait Trait1<X> {
+    type Output;
+}
+
+pub trait Trait2<X> {}
+
+pub struct A;
+
+impl<X, T> Trait1<X> for T where T: Trait2<X> {
+    type Output = ();
+}
+
+impl<X> Trait1<Box<X>> for A {
+//~^ ERROR conflicting implementations of trait
+//~| hard error
+//~| downstream crates may implement trait `Trait2<std::boxed::Box<_>>` for type `A`
+    type Output = i32;
+}
+
+fn main() {}
diff --git a/src/test/run-pass/issue-43355.rs b/src/test/run-pass/issue-43355.rs
new file mode 100644
index 00000000000..19431a6a429
--- /dev/null
+++ b/src/test/run-pass/issue-43355.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.
+
+// Check that the code for issue #43355 can run without an ICE, please remove
+// this test when it becomes an hard error.
+
+pub trait Trait1<X> {
+    type Output;
+}
+pub trait Trait2<X> {}
+
+impl<X, T> Trait1<X> for T where T: Trait2<X> {
+    type Output = ();
+}
+impl<X> Trait1<Box<X>> for A {
+    type Output = i32;
+}
+
+pub struct A;
+
+fn f<X, T: Trait1<Box<X>>>() {
+    println!("k: {}", ::std::mem::size_of::<<T as Trait1<Box<X>>>::Output>());
+}
+
+pub fn g<X, T: Trait2<Box<X>>>() {
+    f::<X, T>();
+}
+
+fn main() {}