Auto merge of #93288 - matthiaskrgr:rollup-uu4uwd1, r=matthiaskrgr

Rollup of 8 pull requests

Successful merges:

 - #88794 (Add a `try_clone()` function to `OwnedFd`.)
 - #93064 (Properly track `DepNode`s in trait evaluation provisional cache)
 - #93118 (Move param count error emission to end of `check_argument_types`)
 - #93144 (Work around missing code coverage data causing llvm-cov failures)
 - #93169 (Fix inconsistency of local blanket impls)
 - #93175 (Implement stable overlap check considering negative traits)
 - #93251 (rustdoc settings: use radio buttons for theme)
 - #93269 (Use error-on-mismatch policy for PAuth module flags.)

Failed merges:

r? `@ghost`
`@rustbot` modify labels: rollup

10 files changed, 484 insertions, 225 deletions

diff --git a/compiler/rustc_codegen_llvm/src/context.rs b/compiler/rustc_codegen_llvm/src/context.rs
index bb16bc5dccd..8672459b5da 100644
--- a/compiler/rustc_codegen_llvm/src/context.rs
+++ b/compiler/rustc_codegen_llvm/src/context.rs
@@ -215,16 +215,19 @@ pub unsafe fn create_module<'ll>(
     // to ensure intrinsic calls don't use it.
     if !sess.needs_plt() {
         let avoid_plt = "RtLibUseGOT\0".as_ptr().cast();
-        llvm::LLVMRustAddModuleFlag(llmod, avoid_plt, 1);
+        llvm::LLVMRustAddModuleFlag(llmod, llvm::LLVMModFlagBehavior::Warning, avoid_plt, 1);
     }
 
     if sess.is_sanitizer_cfi_enabled() {
         // FIXME(rcvalle): Add support for non canonical jump tables.
         let canonical_jump_tables = "CFI Canonical Jump Tables\0".as_ptr().cast();
-        // FIXME(rcvalle): Add it with Override behavior flag--LLVMRustAddModuleFlag adds it with
-        // Warning behavior flag. Add support for specifying the behavior flag to
-        // LLVMRustAddModuleFlag.
-        llvm::LLVMRustAddModuleFlag(llmod, canonical_jump_tables, 1);
+        // FIXME(rcvalle): Add it with Override behavior flag.
+        llvm::LLVMRustAddModuleFlag(
+            llmod,
+            llvm::LLVMModFlagBehavior::Warning,
+            canonical_jump_tables,
+            1,
+        );
     }
 
     // Control Flow Guard is currently only supported by the MSVC linker on Windows.
@@ -233,11 +236,21 @@ pub unsafe fn create_module<'ll>(
             CFGuard::Disabled => {}
             CFGuard::NoChecks => {
                 // Set `cfguard=1` module flag to emit metadata only.
-                llvm::LLVMRustAddModuleFlag(llmod, "cfguard\0".as_ptr() as *const _, 1)
+                llvm::LLVMRustAddModuleFlag(
+                    llmod,
+                    llvm::LLVMModFlagBehavior::Warning,
+                    "cfguard\0".as_ptr() as *const _,
+                    1,
+                )
             }
             CFGuard::Checks => {
                 // Set `cfguard=2` module flag to emit metadata and checks.
-                llvm::LLVMRustAddModuleFlag(llmod, "cfguard\0".as_ptr() as *const _, 2)
+                llvm::LLVMRustAddModuleFlag(
+                    llmod,
+                    llvm::LLVMModFlagBehavior::Warning,
+                    "cfguard\0".as_ptr() as *const _,
+                    2,
+                )
             }
         }
     }
@@ -247,24 +260,28 @@ pub unsafe fn create_module<'ll>(
 
         llvm::LLVMRustAddModuleFlag(
             llmod,
+            llvm::LLVMModFlagBehavior::Error,
             "branch-target-enforcement\0".as_ptr().cast(),
             bti.into(),
         );
 
         llvm::LLVMRustAddModuleFlag(
             llmod,
+            llvm::LLVMModFlagBehavior::Error,
             "sign-return-address\0".as_ptr().cast(),
             pac.is_some().into(),
         );
         let pac_opts = pac.unwrap_or(PacRet { leaf: false, key: PAuthKey::A });
         llvm::LLVMRustAddModuleFlag(
             llmod,
+            llvm::LLVMModFlagBehavior::Error,
             "sign-return-address-all\0".as_ptr().cast(),
             pac_opts.leaf.into(),
         );
         let is_bkey = if pac_opts.key == PAuthKey::A { false } else { true };
         llvm::LLVMRustAddModuleFlag(
             llmod,
+            llvm::LLVMModFlagBehavior::Error,
             "sign-return-address-with-bkey\0".as_ptr().cast(),
             is_bkey.into(),
         );
diff --git a/compiler/rustc_codegen_llvm/src/coverageinfo/mapgen.rs b/compiler/rustc_codegen_llvm/src/coverageinfo/mapgen.rs
index 32f18419753..3014d2f1930 100644
--- a/compiler/rustc_codegen_llvm/src/coverageinfo/mapgen.rs
+++ b/compiler/rustc_codegen_llvm/src/coverageinfo/mapgen.rs
@@ -9,6 +9,7 @@ use rustc_data_structures::fx::FxIndexSet;
 use rustc_hir::def::DefKind;
 use rustc_hir::def_id::DefIdSet;
 use rustc_llvm::RustString;
+use rustc_middle::bug;
 use rustc_middle::middle::codegen_fn_attrs::CodegenFnAttrFlags;
 use rustc_middle::mir::coverage::CodeRegion;
 use rustc_middle::ty::TyCtxt;
@@ -76,10 +77,18 @@ pub fn finalize<'ll, 'tcx>(cx: &CodegenCx<'ll, 'tcx>) {
         let coverage_mapping_buffer = llvm::build_byte_buffer(|coverage_mapping_buffer| {
             mapgen.write_coverage_mapping(expressions, counter_regions, coverage_mapping_buffer);
         });
-        debug_assert!(
-            !coverage_mapping_buffer.is_empty(),
-            "Every `FunctionCoverage` should have at least one counter"
-        );
+
+        if coverage_mapping_buffer.is_empty() {
+            if function_coverage.is_used() {
+                bug!(
+                    "A used function should have had coverage mapping data but did not: {}",
+                    mangled_function_name
+                );
+            } else {
+                debug!("unused function had no coverage mapping data: {}", mangled_function_name);
+                continue;
+            }
+        }
 
         function_data.push((mangled_function_name, source_hash, is_used, coverage_mapping_buffer));
     }
diff --git a/compiler/rustc_codegen_llvm/src/debuginfo/mod.rs b/compiler/rustc_codegen_llvm/src/debuginfo/mod.rs
index 61e49fab6ff..28eb8e2a0a4 100644
--- a/compiler/rustc_codegen_llvm/src/debuginfo/mod.rs
+++ b/compiler/rustc_codegen_llvm/src/debuginfo/mod.rs
@@ -108,18 +108,29 @@ impl<'a, 'tcx> CrateDebugContext<'a, 'tcx> {
             // This can be overridden using --llvm-opts -dwarf-version,N.
             // Android has the same issue (#22398)
             if let Some(version) = sess.target.dwarf_version {
-                llvm::LLVMRustAddModuleFlag(self.llmod, "Dwarf Version\0".as_ptr().cast(), version)
+                llvm::LLVMRustAddModuleFlag(
+                    self.llmod,
+                    llvm::LLVMModFlagBehavior::Warning,
+                    "Dwarf Version\0".as_ptr().cast(),
+                    version,
+                )
             }
 
             // Indicate that we want CodeView debug information on MSVC
             if sess.target.is_like_msvc {
-                llvm::LLVMRustAddModuleFlag(self.llmod, "CodeView\0".as_ptr().cast(), 1)
+                llvm::LLVMRustAddModuleFlag(
+                    self.llmod,
+                    llvm::LLVMModFlagBehavior::Warning,
+                    "CodeView\0".as_ptr().cast(),
+                    1,
+                )
             }
 
             // Prevent bitcode readers from deleting the debug info.
             let ptr = "Debug Info Version\0".as_ptr();
             llvm::LLVMRustAddModuleFlag(
                 self.llmod,
+                llvm::LLVMModFlagBehavior::Warning,
                 ptr.cast(),
                 llvm::LLVMRustDebugMetadataVersion(),
             );
diff --git a/compiler/rustc_codegen_llvm/src/llvm/ffi.rs b/compiler/rustc_codegen_llvm/src/llvm/ffi.rs
index a1c7d2b4f61..2b102188790 100644
--- a/compiler/rustc_codegen_llvm/src/llvm/ffi.rs
+++ b/compiler/rustc_codegen_llvm/src/llvm/ffi.rs
@@ -61,6 +61,26 @@ pub enum LLVMMachineType {
     ARM = 0x01c0,
 }
 
+/// LLVM's Module::ModFlagBehavior, defined in llvm/include/llvm/IR/Module.h.
+///
+/// When merging modules (e.g. during LTO), their metadata flags are combined. Conflicts are
+/// resolved according to the merge behaviors specified here. Flags differing only in merge
+/// behavior are still considered to be in conflict.
+///
+/// In order for Rust-C LTO to work, we must specify behaviors compatible with Clang. Notably,
+/// 'Error' and 'Warning' cannot be mixed for a given flag.
+#[derive(Copy, Clone, PartialEq)]
+#[repr(C)]
+pub enum LLVMModFlagBehavior {
+    Error = 1,
+    Warning = 2,
+    Require = 3,
+    Override = 4,
+    Append = 5,
+    AppendUnique = 6,
+    Max = 7,
+}
+
 // Consts for the LLVM CallConv type, pre-cast to usize.
 
 /// LLVM CallingConv::ID. Should we wrap this?
@@ -1895,7 +1915,16 @@ extern "C" {
 
     pub fn LLVMRustIsRustLLVM() -> bool;
 
-    pub fn LLVMRustAddModuleFlag(M: &Module, name: *const c_char, value: u32);
+    /// Add LLVM module flags.
+    ///
+    /// In order for Rust-C LTO to work, module flags must be compatible with Clang. What
+    /// "compatible" means depends on the merge behaviors involved.
+    pub fn LLVMRustAddModuleFlag(
+        M: &Module,
+        merge_behavior: LLVMModFlagBehavior,
+        name: *const c_char,
+        value: u32,
+    );
 
     pub fn LLVMRustMetadataAsValue<'a>(C: &'a Context, MD: &'a Metadata) -> &'a Value;
 
diff --git a/compiler/rustc_feature/src/builtin_attrs.rs b/compiler/rustc_feature/src/builtin_attrs.rs
index 723cc06864a..0e643ff5998 100644
--- a/compiler/rustc_feature/src/builtin_attrs.rs
+++ b/compiler/rustc_feature/src/builtin_attrs.rs
@@ -697,6 +697,7 @@ pub const BUILTIN_ATTRIBUTES: &[BuiltinAttribute] = &[
     rustc_attr!(TEST, rustc_capture_analysis, Normal, template!(Word), WarnFollowing),
     rustc_attr!(TEST, rustc_insignificant_dtor, Normal, template!(Word), WarnFollowing),
     rustc_attr!(TEST, rustc_strict_coherence, Normal, template!(Word), WarnFollowing),
+    rustc_attr!(TEST, rustc_with_negative_coherence, Normal, template!(Word), WarnFollowing),
     rustc_attr!(TEST, rustc_variance, Normal, template!(Word), WarnFollowing),
     rustc_attr!(TEST, rustc_layout, Normal, template!(List: "field1, field2, ..."), WarnFollowing),
     rustc_attr!(TEST, rustc_regions, Normal, template!(Word), WarnFollowing),
diff --git a/compiler/rustc_llvm/llvm-wrapper/RustWrapper.cpp b/compiler/rustc_llvm/llvm-wrapper/RustWrapper.cpp
index c21e4acbefe..dcd6327c92f 100644
--- a/compiler/rustc_llvm/llvm-wrapper/RustWrapper.cpp
+++ b/compiler/rustc_llvm/llvm-wrapper/RustWrapper.cpp
@@ -722,9 +722,12 @@ extern "C" bool LLVMRustIsRustLLVM() {
 #endif
 }
 
-extern "C" void LLVMRustAddModuleFlag(LLVMModuleRef M, const char *Name,
-                                      uint32_t Value) {
-  unwrap(M)->addModuleFlag(Module::Warning, Name, Value);
+extern "C" void LLVMRustAddModuleFlag(
+    LLVMModuleRef M,
+    Module::ModFlagBehavior MergeBehavior,
+    const char *Name,
+    uint32_t Value) {
+  unwrap(M)->addModuleFlag(MergeBehavior, Name, Value);
 }
 
 extern "C" LLVMValueRef LLVMRustMetadataAsValue(LLVMContextRef C, LLVMMetadataRef MD) {
diff --git a/compiler/rustc_span/src/symbol.rs b/compiler/rustc_span/src/symbol.rs
index ac4729f717d..52d52752b15 100644
--- a/compiler/rustc_span/src/symbol.rs
+++ b/compiler/rustc_span/src/symbol.rs
@@ -1204,6 +1204,7 @@ symbols! {
         rustc_trivial_field_reads,
         rustc_unsafe_specialization_marker,
         rustc_variance,
+        rustc_with_negative_coherence,
         rustdoc,
         rustdoc_internals,
         rustfmt,
diff --git a/compiler/rustc_trait_selection/src/traits/coherence.rs b/compiler/rustc_trait_selection/src/traits/coherence.rs
index af3540386f9..80ed9023d96 100644
--- a/compiler/rustc_trait_selection/src/traits/coherence.rs
+++ b/compiler/rustc_trait_selection/src/traits/coherence.rs
@@ -7,9 +7,11 @@
 use crate::infer::{CombinedSnapshot, InferOk, TyCtxtInferExt};
 use crate::traits::query::evaluate_obligation::InferCtxtExt;
 use crate::traits::select::IntercrateAmbiguityCause;
+use crate::traits::util::impl_trait_ref_and_oblig;
 use crate::traits::SkipLeakCheck;
 use crate::traits::{
-    self, Normalized, Obligation, ObligationCause, PredicateObligation, SelectionContext,
+    self, FulfillmentContext, Normalized, Obligation, ObligationCause, PredicateObligation,
+    PredicateObligations, SelectionContext,
 };
 use rustc_hir::def_id::{DefId, LOCAL_CRATE};
 use rustc_middle::ty::fast_reject::{self, SimplifyParams, StripReferences};
@@ -135,45 +137,83 @@ fn with_fresh_ty_vars<'cx, 'tcx>(
     header
 }
 
+/// What kind of overlap check are we doing -- this exists just for testing and feature-gating
+/// purposes.
+#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)]
+enum OverlapMode {
+    /// The 1.0 rules (either types fail to unify, or where clauses are not implemented for crate-local types)
+    Stable,
+    /// Feature-gated test: Stable, *or* there is an explicit negative impl that rules out one of the where-clauses.
+    WithNegative,
+    /// Just check for negative impls, not for "where clause not implemented": used for testing.
+    Strict,
+}
+
+impl OverlapMode {
+    fn use_negative_impl(&self) -> bool {
+        *self == OverlapMode::Strict || *self == OverlapMode::WithNegative
+    }
+
+    fn use_implicit_negative(&self) -> bool {
+        *self == OverlapMode::Stable || *self == OverlapMode::WithNegative
+    }
+}
+
+fn overlap_mode<'tcx>(tcx: TyCtxt<'tcx>, impl1_def_id: DefId, impl2_def_id: DefId) -> OverlapMode {
+    if tcx.has_attr(impl1_def_id, sym::rustc_strict_coherence)
+        != tcx.has_attr(impl2_def_id, sym::rustc_strict_coherence)
+    {
+        bug!("Use strict coherence on both impls",);
+    }
+
+    if tcx.has_attr(impl1_def_id, sym::rustc_with_negative_coherence)
+        != tcx.has_attr(impl2_def_id, sym::rustc_with_negative_coherence)
+    {
+        bug!("Use with negative coherence on both impls",);
+    }
+
+    if tcx.has_attr(impl1_def_id, sym::rustc_strict_coherence) {
+        OverlapMode::Strict
+    } else if tcx.has_attr(impl1_def_id, sym::rustc_with_negative_coherence) {
+        OverlapMode::WithNegative
+    } else {
+        OverlapMode::Stable
+    }
+}
+
 /// Can both impl `a` and impl `b` be satisfied by a common type (including
 /// where-clauses)? If so, returns an `ImplHeader` that unifies the two impls.
 fn overlap<'cx, 'tcx>(
     selcx: &mut SelectionContext<'cx, 'tcx>,
     skip_leak_check: SkipLeakCheck,
-    a_def_id: DefId,
-    b_def_id: DefId,
+    impl1_def_id: DefId,
+    impl2_def_id: DefId,
 ) -> Option<OverlapResult<'tcx>> {
-    debug!("overlap(a_def_id={:?}, b_def_id={:?})", a_def_id, b_def_id);
+    debug!("overlap(impl1_def_id={:?}, impl2_def_id={:?})", impl1_def_id, impl2_def_id);
 
     selcx.infcx().probe_maybe_skip_leak_check(skip_leak_check.is_yes(), |snapshot| {
-        overlap_within_probe(selcx, skip_leak_check, a_def_id, b_def_id, snapshot)
+        overlap_within_probe(selcx, skip_leak_check, impl1_def_id, impl2_def_id, snapshot)
     })
 }
 
 fn overlap_within_probe<'cx, 'tcx>(
     selcx: &mut SelectionContext<'cx, 'tcx>,
     skip_leak_check: SkipLeakCheck,
-    a_def_id: DefId,
-    b_def_id: DefId,
+    impl1_def_id: DefId,
+    impl2_def_id: DefId,
     snapshot: &CombinedSnapshot<'_, 'tcx>,
 ) -> Option<OverlapResult<'tcx>> {
-    fn loose_check<'cx, 'tcx>(
-        selcx: &mut SelectionContext<'cx, 'tcx>,
-        o: &PredicateObligation<'tcx>,
-    ) -> bool {
-        !selcx.predicate_may_hold_fatal(o)
-    }
+    let infcx = selcx.infcx();
+    let tcx = infcx.tcx;
 
-    fn strict_check<'cx, 'tcx>(
-        selcx: &SelectionContext<'cx, 'tcx>,
-        o: &PredicateObligation<'tcx>,
-    ) -> bool {
-        let infcx = selcx.infcx();
-        let tcx = infcx.tcx;
-        o.flip_polarity(tcx)
-            .as_ref()
-            .map(|o| selcx.infcx().predicate_must_hold_modulo_regions(o))
-            .unwrap_or(false)
+    let overlap_mode = overlap_mode(tcx, impl1_def_id, impl2_def_id);
+
+    if overlap_mode.use_negative_impl() {
+        if negative_impl(selcx, impl1_def_id, impl2_def_id)
+            || negative_impl(selcx, impl2_def_id, impl1_def_id)
+        {
+            return None;
+        }
     }
 
     // For the purposes of this check, we don't bring any placeholder
@@ -182,26 +222,61 @@ fn overlap_within_probe<'cx, 'tcx>(
     // empty environment.
     let param_env = ty::ParamEnv::empty();
 
-    let a_impl_header = with_fresh_ty_vars(selcx, param_env, a_def_id);
-    let b_impl_header = with_fresh_ty_vars(selcx, param_env, b_def_id);
+    let impl1_header = with_fresh_ty_vars(selcx, param_env, impl1_def_id);
+    let impl2_header = with_fresh_ty_vars(selcx, param_env, impl2_def_id);
 
-    debug!("overlap: a_impl_header={:?}", a_impl_header);
-    debug!("overlap: b_impl_header={:?}", b_impl_header);
+    debug!("overlap: impl1_header={:?}", impl1_header);
+    debug!("overlap: impl2_header={:?}", impl2_header);
 
-    // Do `a` and `b` unify? If not, no overlap.
-    let obligations = match selcx
-        .infcx()
-        .at(&ObligationCause::dummy(), param_env)
-        .eq_impl_headers(&a_impl_header, &b_impl_header)
-    {
-        Ok(InferOk { obligations, value: () }) => obligations,
-        Err(_) => {
+    let obligations = equate_impl_headers(selcx, &impl1_header, &impl2_header)?;
+    debug!("overlap: unification check succeeded");
+
+    if overlap_mode.use_implicit_negative() {
+        if implicit_negative(selcx, param_env, &impl1_header, impl2_header, obligations) {
             return None;
         }
-    };
+    }
 
-    debug!("overlap: unification check succeeded");
+    if !skip_leak_check.is_yes() {
+        if infcx.leak_check(true, snapshot).is_err() {
+            debug!("overlap: leak check failed");
+            return None;
+        }
+    }
+
+    let intercrate_ambiguity_causes = selcx.take_intercrate_ambiguity_causes();
+    debug!("overlap: intercrate_ambiguity_causes={:#?}", intercrate_ambiguity_causes);
+
+    let involves_placeholder =
+        matches!(selcx.infcx().region_constraints_added_in_snapshot(snapshot), Some(true));
+
+    let impl_header = selcx.infcx().resolve_vars_if_possible(impl1_header);
+    Some(OverlapResult { impl_header, intercrate_ambiguity_causes, involves_placeholder })
+}
+
+fn equate_impl_headers<'cx, 'tcx>(
+    selcx: &mut SelectionContext<'cx, 'tcx>,
+    impl1_header: &ty::ImplHeader<'tcx>,
+    impl2_header: &ty::ImplHeader<'tcx>,
+) -> Option<PredicateObligations<'tcx>> {
+    // Do `a` and `b` unify? If not, no overlap.
+    selcx
+        .infcx()
+        .at(&ObligationCause::dummy(), ty::ParamEnv::empty())
+        .eq_impl_headers(impl1_header, impl2_header)
+        .map(|infer_ok| infer_ok.obligations)
+        .ok()
+}
 
+/// Given impl1 and impl2 check if both impls can be satisfied by a common type (including
+/// where-clauses) If so, return false, otherwise return true, they are disjoint.
+fn implicit_negative<'cx, 'tcx>(
+    selcx: &mut SelectionContext<'cx, 'tcx>,
+    param_env: ty::ParamEnv<'tcx>,
+    impl1_header: &ty::ImplHeader<'tcx>,
+    impl2_header: ty::ImplHeader<'tcx>,
+    obligations: PredicateObligations<'tcx>,
+) -> bool {
     // There's no overlap if obligations are unsatisfiable or if the obligation negated is
     // satisfied.
     //
@@ -225,11 +300,11 @@ fn overlap_within_probe<'cx, 'tcx>(
     // at some point an impl for `&'?a str: Error` could be added.
     let infcx = selcx.infcx();
     let tcx = infcx.tcx;
-    let opt_failing_obligation = a_impl_header
+    let opt_failing_obligation = impl1_header
         .predicates
         .iter()
         .copied()
-        .chain(b_impl_header.predicates)
+        .chain(impl2_header.predicates)
         .map(|p| infcx.resolve_vars_if_possible(p))
         .map(|p| Obligation {
             cause: ObligationCause::dummy(),
@@ -239,15 +314,7 @@ fn overlap_within_probe<'cx, 'tcx>(
         })
         .chain(obligations)
         .find(|o| {
-            // if both impl headers are set to strict coherence it means that this will be accepted
-            // only if it's stated that T: !Trait. So only prove that the negated obligation holds.
-            if tcx.has_attr(a_def_id, sym::rustc_strict_coherence)
-                && tcx.has_attr(b_def_id, sym::rustc_strict_coherence)
-            {
-                strict_check(selcx, o)
-            } else {
-                loose_check(selcx, o) || tcx.features().negative_impls && strict_check(selcx, o)
-            }
+            loose_check(selcx, o) || tcx.features().negative_impls && negative_impl_exists(selcx, o)
         });
     // FIXME: the call to `selcx.predicate_may_hold_fatal` above should be ported
     // to the canonical trait query form, `infcx.predicate_may_hold`, once
@@ -255,24 +322,97 @@ fn overlap_within_probe<'cx, 'tcx>(
 
     if let Some(failing_obligation) = opt_failing_obligation {
         debug!("overlap: obligation unsatisfiable {:?}", failing_obligation);
-        return None;
+        true
+    } else {
+        false
     }
+}
 
-    if !skip_leak_check.is_yes() {
-        if infcx.leak_check(true, snapshot).is_err() {
-            debug!("overlap: leak check failed");
-            return None;
-        }
-    }
+/// Given impl1 and impl2 check if both impls are never satisfied by a common type (including
+/// where-clauses) If so, return true, they are disjoint and false otherwise.
+fn negative_impl<'cx, 'tcx>(
+    selcx: &mut SelectionContext<'cx, 'tcx>,
+    impl1_def_id: DefId,
+    impl2_def_id: DefId,
+) -> bool {
+    let tcx = selcx.infcx().tcx;
 
-    let impl_header = selcx.infcx().resolve_vars_if_possible(a_impl_header);
-    let intercrate_ambiguity_causes = selcx.take_intercrate_ambiguity_causes();
-    debug!("overlap: intercrate_ambiguity_causes={:#?}", intercrate_ambiguity_causes);
+    // create a parameter environment corresponding to a (placeholder) instantiation of impl1
+    let impl1_env = tcx.param_env(impl1_def_id);
+    let impl1_trait_ref = tcx.impl_trait_ref(impl1_def_id).unwrap();
 
-    let involves_placeholder =
-        matches!(selcx.infcx().region_constraints_added_in_snapshot(snapshot), Some(true));
+    // Create an infcx, taking the predicates of impl1 as assumptions:
+    tcx.infer_ctxt().enter(|infcx| {
+        // Normalize the trait reference. The WF rules ought to ensure
+        // that this always succeeds.
+        let impl1_trait_ref = match traits::fully_normalize(
+            &infcx,
+            FulfillmentContext::new(),
+            ObligationCause::dummy(),
+            impl1_env,
+            impl1_trait_ref,
+        ) {
+            Ok(impl1_trait_ref) => impl1_trait_ref,
+            Err(err) => {
+                bug!("failed to fully normalize {:?}: {:?}", impl1_trait_ref, err);
+            }
+        };
+
+        // Attempt to prove that impl2 applies, given all of the above.
+        let selcx = &mut SelectionContext::new(&infcx);
+        let impl2_substs = infcx.fresh_substs_for_item(DUMMY_SP, impl2_def_id);
+        let (impl2_trait_ref, obligations) =
+            impl_trait_ref_and_oblig(selcx, impl1_env, impl2_def_id, impl2_substs);
+
+        // do the impls unify? If not, not disjoint.
+        let more_obligations = match infcx
+            .at(&ObligationCause::dummy(), impl1_env)
+            .eq(impl1_trait_ref, impl2_trait_ref)
+        {
+            Ok(InferOk { obligations, .. }) => obligations,
+            Err(_) => {
+                debug!(
+                    "explicit_disjoint: {:?} does not unify with {:?}",
+                    impl1_trait_ref, impl2_trait_ref
+                );
+                return false;
+            }
+        };
 
-    Some(OverlapResult { impl_header, intercrate_ambiguity_causes, involves_placeholder })
+        let opt_failing_obligation = obligations
+            .into_iter()
+            .chain(more_obligations)
+            .find(|o| negative_impl_exists(selcx, o));
+
+        if let Some(failing_obligation) = opt_failing_obligation {
+            debug!("overlap: obligation unsatisfiable {:?}", failing_obligation);
+            true
+        } else {
+            false
+        }
+    })
+}
+
+fn loose_check<'cx, 'tcx>(
+    selcx: &mut SelectionContext<'cx, 'tcx>,
+    o: &PredicateObligation<'tcx>,
+) -> bool {
+    !selcx.predicate_may_hold_fatal(o)
+}
+
+fn negative_impl_exists<'cx, 'tcx>(
+    selcx: &SelectionContext<'cx, 'tcx>,
+    o: &PredicateObligation<'tcx>,
+) -> bool {
+    let infcx = selcx.infcx();
+    let tcx = infcx.tcx;
+    o.flip_polarity(tcx)
+        .as_ref()
+        .map(|o| {
+            // FIXME This isn't quite correct, regions should be included
+            selcx.infcx().predicate_must_hold_modulo_regions(o)
+        })
+        .unwrap_or(false)
 }
 
 pub fn trait_ref_is_knowable<'tcx>(
diff --git a/compiler/rustc_trait_selection/src/traits/select/mod.rs b/compiler/rustc_trait_selection/src/traits/select/mod.rs
index 558ecd393b6..ab4fb9607ca 100644
--- a/compiler/rustc_trait_selection/src/traits/select/mod.rs
+++ b/compiler/rustc_trait_selection/src/traits/select/mod.rs
@@ -765,14 +765,38 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
             debug!(?result, "CACHE MISS");
             self.insert_evaluation_cache(param_env, fresh_trait_pred, dep_node, result);
 
-            stack.cache().on_completion(stack.dfn, |fresh_trait_pred, provisional_result| {
-                self.insert_evaluation_cache(
-                    param_env,
-                    fresh_trait_pred,
-                    dep_node,
-                    provisional_result.max(result),
-                );
-            });
+            stack.cache().on_completion(
+                stack.dfn,
+                |fresh_trait_pred, provisional_result, provisional_dep_node| {
+                    // Create a new `DepNode` that has dependencies on:
+                    // * The `DepNode` for the original evaluation that resulted in a provisional cache
+                    // entry being crated
+                    // * The `DepNode` for the *current* evaluation, which resulted in us completing
+                    // provisional caches entries and inserting them into the evaluation cache
+                    //
+                    // This ensures that when a query reads this entry from the evaluation cache,
+                    // it will end up (transitively) dependening on all of the incr-comp dependencies
+                    // created during the evaluation of this trait. For example, evaluating a trait
+                    // will usually require us to invoke `type_of(field_def_id)` to determine the
+                    // constituent types, and we want any queries reading from this evaluation
+                    // cache entry to end up with a transitive `type_of(field_def_id`)` dependency.
+                    //
+                    // By using `in_task`, we're also creating an edge from the *current* query
+                    // to the newly-created `combined_dep_node`. This is probably redundant,
+                    // but it's better to add too many dep graph edges than to add too few
+                    // dep graph edges.
+                    let ((), combined_dep_node) = self.in_task(|this| {
+                        this.tcx().dep_graph.read_index(provisional_dep_node);
+                        this.tcx().dep_graph.read_index(dep_node);
+                    });
+                    self.insert_evaluation_cache(
+                        param_env,
+                        fresh_trait_pred,
+                        combined_dep_node,
+                        provisional_result.max(result),
+                    );
+                },
+            );
         } else {
             debug!(?result, "PROVISIONAL");
             debug!(
@@ -781,7 +805,13 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> {
                 fresh_trait_pred, stack.depth, reached_depth,
             );
 
-            stack.cache().insert_provisional(stack.dfn, reached_depth, fresh_trait_pred, result);
+            stack.cache().insert_provisional(
+                stack.dfn,
+                reached_depth,
+                fresh_trait_pred,
+                result,
+                dep_node,
+            );
         }
 
         Ok(result)
@@ -2506,6 +2536,11 @@ struct ProvisionalEvaluation {
     from_dfn: usize,
     reached_depth: usize,
     result: EvaluationResult,
+    /// The `DepNodeIndex` created for the `evaluate_stack` call for this provisional
+    /// evaluation. When we create an entry in the evaluation cache using this provisional
+    /// cache entry (see `on_completion`), we use this `dep_node` to ensure that future reads from
+    /// the cache will have all of the necessary incr comp dependencies tracked.
+    dep_node: DepNodeIndex,
 }
 
 impl<'tcx> Default for ProvisionalEvaluationCache<'tcx> {
@@ -2548,6 +2583,7 @@ impl<'tcx> ProvisionalEvaluationCache<'tcx> {
         reached_depth: usize,
         fresh_trait_pred: ty::PolyTraitPredicate<'tcx>,
         result: EvaluationResult,
+        dep_node: DepNodeIndex,
     ) {
         debug!(?from_dfn, ?fresh_trait_pred, ?result, "insert_provisional");
 
@@ -2573,7 +2609,10 @@ impl<'tcx> ProvisionalEvaluationCache<'tcx> {
             }
         }
 
-        map.insert(fresh_trait_pred, ProvisionalEvaluation { from_dfn, reached_depth, result });
+        map.insert(
+            fresh_trait_pred,
+            ProvisionalEvaluation { from_dfn, reached_depth, result, dep_node },
+        );
     }
 
     /// Invoked when the node with dfn `dfn` does not get a successful
@@ -2624,7 +2663,7 @@ impl<'tcx> ProvisionalEvaluationCache<'tcx> {
     fn on_completion(
         &self,
         dfn: usize,
-        mut op: impl FnMut(ty::PolyTraitPredicate<'tcx>, EvaluationResult),
+        mut op: impl FnMut(ty::PolyTraitPredicate<'tcx>, EvaluationResult, DepNodeIndex),
     ) {
         debug!(?dfn, "on_completion");
 
@@ -2633,7 +2672,7 @@ impl<'tcx> ProvisionalEvaluationCache<'tcx> {
         {
             debug!(?fresh_trait_pred, ?eval, "on_completion");
 
-            op(fresh_trait_pred, eval.result);
+            op(fresh_trait_pred, eval.result, eval.dep_node);
         }
     }
 }
diff --git a/compiler/rustc_typeck/src/check/fn_ctxt/checks.rs b/compiler/rustc_typeck/src/check/fn_ctxt/checks.rs
index e42d94a6f40..c39199f84b5 100644
--- a/compiler/rustc_typeck/src/check/fn_ctxt/checks.rs
+++ b/compiler/rustc_typeck/src/check/fn_ctxt/checks.rs
@@ -127,136 +127,19 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
 
         let expected_arg_count = formal_input_tys.len();
 
-        let param_count_error = |expected_count: usize,
-                                 arg_count: usize,
-                                 error_code: &str,
-                                 c_variadic: bool,
-                                 sugg_unit: bool| {
-            let (span, start_span, args, ctor_of) = match &call_expr.kind {
-                hir::ExprKind::Call(
-                    hir::Expr {
-                        span,
-                        kind:
-                            hir::ExprKind::Path(hir::QPath::Resolved(
-                                _,
-                                hir::Path { res: Res::Def(DefKind::Ctor(of, _), _), .. },
-                            )),
-                        ..
-                    },
-                    args,
-                ) => (*span, *span, &args[..], Some(of)),
-                hir::ExprKind::Call(hir::Expr { span, .. }, args) => {
-                    (*span, *span, &args[..], None)
-                }
-                hir::ExprKind::MethodCall(path_segment, args, _) => (
-                    path_segment.ident.span,
-                    // `sp` doesn't point at the whole `foo.bar()`, only at `bar`.
-                    path_segment
-                        .args
-                        .and_then(|args| args.args.iter().last())
-                        // Account for `foo.bar::<T>()`.
-                        .map(|arg| {
-                            // Skip the closing `>`.
-                            tcx.sess
-                                .source_map()
-                                .next_point(tcx.sess.source_map().next_point(arg.span()))
-                        })
-                        .unwrap_or(path_segment.ident.span),
-                    &args[1..], // Skip the receiver.
-                    None,       // methods are never ctors
-                ),
-                k => span_bug!(call_span, "checking argument types on a non-call: `{:?}`", k),
-            };
-            let arg_spans = if provided_args.is_empty() {
-                // foo()
-                // ^^^-- supplied 0 arguments
-                // |
-                // expected 2 arguments
-                vec![tcx.sess.source_map().next_point(start_span).with_hi(call_span.hi())]
-            } else {
-                // foo(1, 2, 3)
-                // ^^^ -  -  - supplied 3 arguments
-                // |
-                // expected 2 arguments
-                args.iter().map(|arg| arg.span).collect::<Vec<Span>>()
-            };
-
-            let mut err = tcx.sess.struct_span_err_with_code(
-                span,
-                &format!(
-                    "this {} takes {}{} but {} {} supplied",
-                    match ctor_of {
-                        Some(CtorOf::Struct) => "struct",
-                        Some(CtorOf::Variant) => "enum variant",
-                        None => "function",
-                    },
-                    if c_variadic { "at least " } else { "" },
-                    potentially_plural_count(expected_count, "argument"),
-                    potentially_plural_count(arg_count, "argument"),
-                    if arg_count == 1 { "was" } else { "were" }
-                ),
-                DiagnosticId::Error(error_code.to_owned()),
-            );
-            let label = format!("supplied {}", potentially_plural_count(arg_count, "argument"));
-            for (i, span) in arg_spans.into_iter().enumerate() {
-                err.span_label(
-                    span,
-                    if arg_count == 0 || i + 1 == arg_count { &label } else { "" },
-                );
-            }
-
-            if let Some(def_id) = fn_def_id {
-                if let Some(def_span) = tcx.def_ident_span(def_id) {
-                    let mut spans: MultiSpan = def_span.into();
-
-                    let params = tcx
-                        .hir()
-                        .get_if_local(def_id)
-                        .and_then(|node| node.body_id())
-                        .into_iter()
-                        .map(|id| tcx.hir().body(id).params)
-                        .flatten();
-
-                    for param in params {
-                        spans.push_span_label(param.span, String::new());
-                    }
-
-                    let def_kind = tcx.def_kind(def_id);
-                    err.span_note(spans, &format!("{} defined here", def_kind.descr(def_id)));
-                }
-            }
-
-            if sugg_unit {
-                let sugg_span = tcx.sess.source_map().end_point(call_expr.span);
-                // remove closing `)` from the span
-                let sugg_span = sugg_span.shrink_to_lo();
-                err.span_suggestion(
-                    sugg_span,
-                    "expected the unit value `()`; create it with empty parentheses",
-                    String::from("()"),
-                    Applicability::MachineApplicable,
-                );
-            } else {
-                err.span_label(
-                    span,
-                    format!(
-                        "expected {}{}",
-                        if c_variadic { "at least " } else { "" },
-                        potentially_plural_count(expected_count, "argument")
-                    ),
-                );
-            }
-            err.emit();
-        };
+        // expected_count, arg_count, error_code, sugg_unit
+        let mut error: Option<(usize, usize, &str, bool)> = None;
 
+        // If the arguments should be wrapped in a tuple (ex: closures), unwrap them here
         let (formal_input_tys, expected_input_tys) = if tuple_arguments == TupleArguments {
             let tuple_type = self.structurally_resolved_type(call_span, formal_input_tys[0]);
             match tuple_type.kind() {
-                ty::Tuple(arg_types) if arg_types.len() != provided_args.len() => {
-                    param_count_error(arg_types.len(), provided_args.len(), "E0057", false, false);
-                    (self.err_args(provided_args.len()), vec![])
-                }
+                // We expected a tuple and got a tuple
                 ty::Tuple(arg_types) => {
+                    // Argument length differs
+                    if arg_types.len() != provided_args.len() {
+                        error = Some((arg_types.len(), provided_args.len(), "E0057", false));
+                    }
                     let expected_input_tys = match expected_input_tys.get(0) {
                         Some(&ty) => match ty.kind() {
                             ty::Tuple(ref tys) => tys.iter().map(|k| k.expect_ty()).collect(),
@@ -267,6 +150,8 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
                     (arg_types.iter().map(|k| k.expect_ty()).collect(), expected_input_tys)
                 }
                 _ => {
+                    // Otherwise, there's a mismatch, so clear out what we're expecting, and set
+                    // our input typs to err_args so we don't blow up the error messages
                     struct_span_err!(
                         tcx.sess,
                         call_span,
@@ -284,7 +169,7 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
             if supplied_arg_count >= expected_arg_count {
                 (formal_input_tys.to_vec(), expected_input_tys)
             } else {
-                param_count_error(expected_arg_count, supplied_arg_count, "E0060", true, false);
+                error = Some((expected_arg_count, supplied_arg_count, "E0060", false));
                 (self.err_args(supplied_arg_count), vec![])
             }
         } else {
@@ -296,8 +181,7 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
             } else {
                 false
             };
-            param_count_error(expected_arg_count, supplied_arg_count, "E0061", false, sugg_unit);
-
+            error = Some((expected_arg_count, supplied_arg_count, "E0061", sugg_unit));
             (self.err_args(supplied_arg_count), vec![])
         };
 
@@ -315,13 +199,15 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
 
         assert_eq!(expected_input_tys.len(), formal_input_tys.len());
 
+        let provided_arg_count: usize = provided_args.len();
+
         // Keep track of the fully coerced argument types
-        let mut final_arg_types: Vec<(usize, Ty<'_>, Ty<'_>)> = vec![];
+        let mut final_arg_types: Vec<Option<(Ty<'_>, Ty<'_>)>> = vec![None; provided_arg_count];
 
         // We introduce a helper function to demand that a given argument satisfy a given input
         // This is more complicated than just checking type equality, as arguments could be coerced
         // This version writes those types back so further type checking uses the narrowed types
-        let demand_compatible = |idx, final_arg_types: &mut Vec<(usize, Ty<'tcx>, Ty<'tcx>)>| {
+        let demand_compatible = |idx, final_arg_types: &mut Vec<Option<(Ty<'tcx>, Ty<'tcx>)>>| {
             let formal_input_ty: Ty<'tcx> = formal_input_tys[idx];
             let expected_input_ty: Ty<'tcx> = expected_input_tys[idx];
             let provided_arg = &provided_args[idx];
@@ -340,13 +226,13 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
             let coerced_ty = expectation.only_has_type(self).unwrap_or(formal_input_ty);
 
             // Keep track of these for below
-            final_arg_types.push((idx, checked_ty, coerced_ty));
+            final_arg_types[idx] = Some((checked_ty, coerced_ty));
 
             // Cause selection errors caused by resolving a single argument to point at the
             // argument and not the call. This is otherwise redundant with the `demand_coerce`
             // call immediately after, but it lets us customize the span pointed to in the
             // fulfillment error to be more accurate.
-            let _ =
+            let coerced_ty =
                 self.resolve_vars_with_obligations_and_mutate_fulfillment(coerced_ty, |errors| {
                     self.point_at_type_arg_instead_of_call_if_possible(errors, call_expr);
                     self.point_at_arg_instead_of_call_if_possible(
@@ -358,6 +244,8 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
                     );
                 });
 
+            final_arg_types[idx] = Some((checked_ty, coerced_ty));
+
             // We're processing function arguments so we definitely want to use
             // two-phase borrows.
             self.demand_coerce(&provided_arg, checked_ty, coerced_ty, None, AllowTwoPhase::Yes);
@@ -416,6 +304,123 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
             }
         }
 
+        // If there was an error in parameter count, emit that here
+        if let Some((expected_count, arg_count, err_code, sugg_unit)) = error {
+            let (span, start_span, args, ctor_of) = match &call_expr.kind {
+                hir::ExprKind::Call(
+                    hir::Expr {
+                        span,
+                        kind:
+                            hir::ExprKind::Path(hir::QPath::Resolved(
+                                _,
+                                hir::Path { res: Res::Def(DefKind::Ctor(of, _), _), .. },
+                            )),
+                        ..
+                    },
+                    args,
+                ) => (*span, *span, &args[..], Some(of)),
+                hir::ExprKind::Call(hir::Expr { span, .. }, args) => {
+                    (*span, *span, &args[..], None)
+                }
+                hir::ExprKind::MethodCall(path_segment, args, _) => (
+                    path_segment.ident.span,
+                    // `sp` doesn't point at the whole `foo.bar()`, only at `bar`.
+                    path_segment
+                        .args
+                        .and_then(|args| args.args.iter().last())
+                        // Account for `foo.bar::<T>()`.
+                        .map(|arg| {
+                            // Skip the closing `>`.
+                            tcx.sess
+                                .source_map()
+                                .next_point(tcx.sess.source_map().next_point(arg.span()))
+                        })
+                        .unwrap_or(path_segment.ident.span),
+                    &args[1..], // Skip the receiver.
+                    None,       // methods are never ctors
+                ),
+                k => span_bug!(call_span, "checking argument types on a non-call: `{:?}`", k),
+            };
+            let arg_spans = if provided_args.is_empty() {
+                // foo()
+                // ^^^-- supplied 0 arguments
+                // |
+                // expected 2 arguments
+                vec![tcx.sess.source_map().next_point(start_span).with_hi(call_span.hi())]
+            } else {
+                // foo(1, 2, 3)
+                // ^^^ -  -  - supplied 3 arguments
+                // |
+                // expected 2 arguments
+                args.iter().map(|arg| arg.span).collect::<Vec<Span>>()
+            };
+            let call_name = match ctor_of {
+                Some(CtorOf::Struct) => "struct",
+                Some(CtorOf::Variant) => "enum variant",
+                None => "function",
+            };
+            let mut err = tcx.sess.struct_span_err_with_code(
+                span,
+                &format!(
+                    "this {} takes {}{} but {} {} supplied",
+                    call_name,
+                    if c_variadic { "at least " } else { "" },
+                    potentially_plural_count(expected_count, "argument"),
+                    potentially_plural_count(arg_count, "argument"),
+                    if arg_count == 1 { "was" } else { "were" }
+                ),
+                DiagnosticId::Error(err_code.to_owned()),
+            );
+            let label = format!("supplied {}", potentially_plural_count(arg_count, "argument"));
+            for (i, span) in arg_spans.into_iter().enumerate() {
+                err.span_label(
+                    span,
+                    if arg_count == 0 || i + 1 == arg_count { &label } else { "" },
+                );
+            }
+            if let Some(def_id) = fn_def_id {
+                if let Some(def_span) = tcx.def_ident_span(def_id) {
+                    let mut spans: MultiSpan = def_span.into();
+
+                    let params = tcx
+                        .hir()
+                        .get_if_local(def_id)
+                        .and_then(|node| node.body_id())
+                        .into_iter()
+                        .map(|id| tcx.hir().body(id).params)
+                        .flatten();
+
+                    for param in params {
+                        spans.push_span_label(param.span, String::new());
+                    }
+
+                    let def_kind = tcx.def_kind(def_id);
+                    err.span_note(spans, &format!("{} defined here", def_kind.descr(def_id)));
+                }
+            }
+            if sugg_unit {
+                let sugg_span = tcx.sess.source_map().end_point(call_expr.span);
+                // remove closing `)` from the span
+                let sugg_span = sugg_span.shrink_to_lo();
+                err.span_suggestion(
+                    sugg_span,
+                    "expected the unit value `()`; create it with empty parentheses",
+                    String::from("()"),
+                    Applicability::MachineApplicable,
+                );
+            } else {
+                err.span_label(
+                    span,
+                    format!(
+                        "expected {}{}",
+                        if c_variadic { "at least " } else { "" },
+                        potentially_plural_count(expected_count, "argument")
+                    ),
+                );
+            }
+            err.emit();
+        }
+
         // We also need to make sure we at least write the ty of the other
         // arguments which we skipped above.
         if c_variadic {
@@ -975,7 +980,7 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
     fn point_at_arg_instead_of_call_if_possible(
         &self,
         errors: &mut Vec<traits::FulfillmentError<'tcx>>,
-        final_arg_types: &[(usize, Ty<'tcx>, Ty<'tcx>)],
+        final_arg_types: &[Option<(Ty<'tcx>, Ty<'tcx>)>],
         expr: &'tcx hir::Expr<'tcx>,
         call_sp: Span,
         args: &'tcx [hir::Expr<'tcx>],
@@ -1030,8 +1035,12 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> {
             // `FulfillmentError`.
             let mut referenced_in = final_arg_types
                 .iter()
-                .map(|&(i, checked_ty, _)| (i, checked_ty))
-                .chain(final_arg_types.iter().map(|&(i, _, coerced_ty)| (i, coerced_ty)))
+                .enumerate()
+                .filter_map(|(i, arg)| match arg {
+                    Some((checked_ty, coerce_ty)) => Some([(i, *checked_ty), (i, *coerce_ty)]),
+                    _ => None,
+                })
+                .flatten()
                 .flat_map(|(i, ty)| {
                     let ty = self.resolve_vars_if_possible(ty);
                     // We walk the argument type because the argument's type could have