Don't merge distinct impl candidates

@@ -622,6 +622,10 @@ impl<'tcx> Interner for TyCtxt<'tcx> {         self.trait_is_auto(trait_def_id)     } +    fn trait_is_marker(self, trait_def_id: DefId) -> bool {+        self.trait_def(trait_def_id).is_marker+    }+     fn trait_is_coinductive(self, trait_def_id: DefId) -> bool {         self.trait_is_coinductive(trait_def_id)     }

@@ -1052,8 +1052,12 @@ where                 // we still use modulo regions here. This is fine as specialization currently                 // assumes that specializing impls have to be always applicable, meaning that                 // the only allowed region constraints may be constraints also present on the default impl.+                //+                // If both impls have the same response, dropping victim doesn't change the+                // result. We need to do so here as we don't merge distinct impl candidates.                 if matches!(allow_inference_constraints, AllowInferenceConstraints::Yes)                     || has_only_region_constraints(c.result)+                    || c.result == candidates[i].result                 {                     if self.cx().impl_specializes(other_def_id, victim_def_id) {                         candidates.remove(i);

@@ -1493,19 +1493,77 @@ where         }     } +    /// Like `try_merge_candidates`, but returns `None` if there are multiple user-written+    /// impls, or a user-written impl and a builtin impl, in which case we bail with ambiguity.+    ///+    /// Candidates with equal responses can still come from conflicting impls, ex - two+    /// overlapping impls which both apply due to impossible where-clauses. We don't want+    /// to merge these. Multiple builtin impls are still merged as usual. This is not+    /// done for marker traits, as their impls are allowed to overlap.+    #[instrument(level = "trace", skip(self), ret)]+    fn try_merge_impl_candidates(+        &mut self,+        trait_def_id: I::TraitId,+        candidates: &[Candidate<I>],+    ) -> Option<CanonicalResponse<I>> {+        let is_marker = self.cx().trait_is_marker(trait_def_id);+        let all_builtin = candidates+            .iter()+            .all(|candidate| matches!(candidate.source, CandidateSource::BuiltinImpl(_)));++        if is_marker || all_builtin {+            self.try_merge_candidates(candidates).map(|(response, _)| response)+        } else if candidates.len() > 1 {+            None+        } else {+            candidates.first().map(|candidate| candidate.result)+        }+    }++    fn merge_candidates_or_bail_with_ambiguity(+        &mut self,+        candidates: &[Candidate<I>],+        proven_via: TraitGoalProvenVia,+    ) -> (CanonicalResponse<I>, Option<TraitGoalProvenVia>) {+        if let Some((response, _)) = self.try_merge_candidates(candidates) {+            (response, Some(proven_via))+        } else {+            (self.bail_with_ambiguity(candidates), None)+        }+    }++    fn merge_impl_candidates_or_bail_with_ambiguity(+        &mut self,+        trait_def_id: I::TraitId,+        candidates: &[Candidate<I>],+    ) -> (CanonicalResponse<I>, Option<TraitGoalProvenVia>) {+        debug_assert!(candidates.iter().all(|c| matches!(+            c.source,+            CandidateSource::Impl(_) | CandidateSource::BuiltinImpl(_)+        )));+        match self.try_merge_impl_candidates(trait_def_id, candidates) {+            Some(response) => (response, Some(TraitGoalProvenVia::Misc)),+            None => (self.bail_with_ambiguity(candidates), None),+        }+    }+     #[instrument(level = "debug", skip(self), ret)]     pub(super) fn merge_trait_candidates(         &mut self,-        candidate_preference_mode: CandidatePreferenceMode,+        trait_def_id: I::TraitId,         mut candidates: Vec<Candidate<I>>,         failed_candidate_info: FailedCandidateInfo,     ) -> Result<(CanonicalResponse<I>, Option<TraitGoalProvenVia>), NoSolution> {+        if candidates.is_empty() {+            return Err(NoSolution);+        }++        let candidate_preference_mode = CandidatePreferenceMode::compute(self.cx(), trait_def_id);         if self.typing_mode().is_coherence() {-            return if let Some((response, _)) = self.try_merge_candidates(&candidates) {-                Ok((response, Some(TraitGoalProvenVia::Misc)))-            } else {-                self.flounder(&candidates).map(|r| (r, None))-            };+            return Ok(match self.try_merge_impl_candidates(trait_def_id, &candidates) {+                Some(response) => (response, Some(TraitGoalProvenVia::Misc)),+                None => (self.bail_with_ambiguity(&candidates), None),+            });         }          // We prefer trivial builtin candidates, i.e. builtin impls without any@@ -1532,11 +1590,10 @@ where             let alias_bounds: Vec<_> = candidates                 .extract_if(.., |c| matches!(c.source, CandidateSource::AliasBound(..)))                 .collect();-            return if let Some((response, _)) = self.try_merge_candidates(&alias_bounds) {-                Ok((response, Some(TraitGoalProvenVia::AliasBound)))-            } else {-                Ok((self.bail_with_ambiguity(&alias_bounds), None))-            };+            return Ok(self.merge_candidates_or_bail_with_ambiguity(+                &alias_bounds,+                TraitGoalProvenVia::AliasBound,+            ));         }          // If there are non-global where-bounds, prefer where-bounds@@ -1588,11 +1645,10 @@ where             let alias_bounds: Vec<_> = candidates                 .extract_if(.., |c| matches!(c.source, CandidateSource::AliasBound(_)))                 .collect();-            return if let Some((response, _)) = self.try_merge_candidates(&alias_bounds) {-                Ok((response, Some(TraitGoalProvenVia::AliasBound)))-            } else {-                Ok((self.bail_with_ambiguity(&alias_bounds), None))-            };+            return Ok(self.merge_candidates_or_bail_with_ambiguity(+                &alias_bounds,+                TraitGoalProvenVia::AliasBound,+            ));         }          self.filter_specialized_impls(AllowInferenceConstraints::No, &mut candidates);@@ -1602,21 +1658,16 @@ where         // is still reported as being proven-via the param-env so that rigid projections         // operate correctly. Otherwise, drop all global where-bounds before merging the         // remaining candidates.-        let proven_via = if candidates+        let only_global_where_bounds = candidates             .iter()-            .all(|c| matches!(c.source, CandidateSource::ParamEnv(ParamEnvSource::Global)))-        {-            TraitGoalProvenVia::ParamEnv+            .all(|c| matches!(c.source, CandidateSource::ParamEnv(ParamEnvSource::Global)));+        if only_global_where_bounds {+            Ok(self+                .merge_candidates_or_bail_with_ambiguity(&candidates, TraitGoalProvenVia::ParamEnv))         } else {             candidates                 .retain(|c| !matches!(c.source, CandidateSource::ParamEnv(ParamEnvSource::Global)));-            TraitGoalProvenVia::Misc-        };--        if let Some((response, _)) = self.try_merge_candidates(&candidates) {-            Ok((response, Some(proven_via)))-        } else {-            self.flounder(&candidates).map(|r| (r, None))+            Ok(self.merge_impl_candidates_or_bail_with_ambiguity(trait_def_id, &candidates))         }     } @@ -1628,9 +1679,7 @@ where     {         let (candidates, failed_candidate_info) =             self.assemble_and_evaluate_candidates(goal, AssembleCandidatesFrom::All)?;-        let candidate_preference_mode =-            CandidatePreferenceMode::compute(self.cx(), goal.predicate.def_id());-        self.merge_trait_candidates(candidate_preference_mode, candidates, failed_candidate_info)+        self.merge_trait_candidates(goal.predicate.def_id(), candidates, failed_candidate_info)             .map_err(Into::into)     } 

@@ -477,6 +477,8 @@ pub trait Interner:      fn trait_is_auto(self, trait_def_id: Self::TraitId) -> bool; +    fn trait_is_marker(self, trait_def_id: Self::TraitId) -> bool;+     fn trait_is_coinductive(self, trait_def_id: Self::TraitId) -> bool;      fn trait_is_alias(self, trait_def_id: Self::TraitId) -> bool;

@@ -4,7 +4,12 @@ error[E0391]: cycle detected when building specialization graph of trait `Trait` LL | trait Trait<T> { type Assoc; }    | ^^^^^^^^^^^^^^    |-   = note: ...which immediately requires building specialization graph of trait `Trait` again+note: ...which requires computing whether impls specialize one another...+  --> $DIR/coherence-inherited-assoc-ty-cycle-err.rs:17:1+   |+LL | impl<T> Trait<T> for String {+   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^+   = note: ...which again requires building specialization graph of trait `Trait`, completing the cycle    = note: cycle used when coherence checking all impls of trait `Trait`    = note: for more information, see <https://rustc-dev-guide.rust-lang.org/overview.html#queries> and <https://rustc-dev-guide.rust-lang.org/query.html> 

@@ -0,0 +1,17 @@+error[E0283]: type annotations needed: cannot satisfy `Option<T>: Overlap`+  --> $DIR/ambiguous-impl-in-resolve.rs:17:6+   |+LL |     <Option<T> as Overlap>::f();+   |      ^^^^^^^^^+   |+note: multiple `impl`s satisfying `Option<T>: Overlap` found+  --> $DIR/ambiguous-impl-in-resolve.rs:10:1+   |+LL | impl<T> Overlap for Option<T> where Self: Clone, { fn f() {} }+   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^+LL | impl<T> Overlap for Option<T> where Self: Local, { fn f() {} }+   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^++error: aborting due to 1 previous error++For more information about this error, try `rustc --explain E0283`.

@@ -0,0 +1,17 @@+error[E0283]: type annotations needed: cannot satisfy `Option<T>: Overlap`+  --> $DIR/ambiguous-impl-in-resolve.rs:17:6+   |+LL |     <Option<T> as Overlap>::f();+   |      ^^^^^^^^^+   |+note: multiple `impl`s satisfying `Option<T>: Overlap` found+  --> $DIR/ambiguous-impl-in-resolve.rs:10:1+   |+LL | impl<T> Overlap for Option<T> where Self: Clone, { fn f() {} }+   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^+LL | impl<T> Overlap for Option<T> where Self: Local, { fn f() {} }+   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^++error: aborting due to 1 previous error++For more information about this error, try `rustc --explain E0283`.

@@ -1,5 +1,8 @@-//@ check-pass-//@ compile-flags: -Znext-solver+//@ revisions: old next+//@[next] compile-flags: -Znext-solver++// Impossible where-clauses can cause multiple overlapping impls to apply+// with the same constraints.  trait Local {} @@ -12,6 +15,7 @@ where     Option<T>: Clone + Local, {     <Option<T> as Overlap>::f();+    //~^ ERROR type annotations needed }  fn main() {}

@@ -19,6 +19,7 @@ impl<'a, 'b, T> Trait<'a, 'b> for A<T> where B<T>: Trait<'a, 'b> {} // not have a cycle with `A<T>`. This candidate never applies because of // the `A<T>: NotImplemented` bound. impl<'a, 'b, T> Trait<'a, 'b> for B<T>+//~^ ERROR: type annotations needed: cannot satisfy `B<T>: Trait<'a, 'b>` [E0283] where     A<T>: Trait<'a, 'b>,     A<T>: NotImplemented,@@ -33,6 +34,7 @@ where // regions in the `A<T>: Trait<'a, 'b>` where-bound. As both the impl above // and the impl below now apply with some constraints, we failed with ambiguity. impl<'a, 'b, T> Trait<'a, 'b> for B<T>+//~^ ERROR: type annotations needed: cannot satisfy `B<T>: Trait<'a, 'b>` [E0283] where     A<T>: NotImplemented, {}

@@ -1,10 +1,65 @@+error[E0283]: type annotations needed: cannot satisfy `B<T>: Trait<'a, 'b>`+  --> $DIR/fixpoint-rerun-all-cycle-heads.rs:21:35+   |+LL | impl<'a, 'b, T> Trait<'a, 'b> for B<T>+   |                                   ^^^^+   |+note: multiple `impl`s satisfying `B<T>: Trait<'a, 'b>` found+  --> $DIR/fixpoint-rerun-all-cycle-heads.rs:21:1+   |+LL | / impl<'a, 'b, T> Trait<'a, 'b> for B<T>+LL | |+LL | | where+LL | |     A<T>: Trait<'a, 'b>,+LL | |     A<T>: NotImplemented,+   | |_________________________^+...+LL | / impl<'a, 'b, T> Trait<'a, 'b> for B<T>+LL | |+LL | | where+LL | |     A<T>: NotImplemented,+   | |_________________________^+...+LL | / impl<'a, T> Trait<'a, 'static> for B<T>+LL | | where+LL | |     C<T>: Trait<'a, 'a>,+   | |________________________^++error[E0283]: type annotations needed: cannot satisfy `B<T>: Trait<'a, 'b>`+  --> $DIR/fixpoint-rerun-all-cycle-heads.rs:36:35+   |+LL | impl<'a, 'b, T> Trait<'a, 'b> for B<T>+   |                                   ^^^^+   |+note: multiple `impl`s satisfying `B<T>: Trait<'a, 'b>` found+  --> $DIR/fixpoint-rerun-all-cycle-heads.rs:21:1+   |+LL | / impl<'a, 'b, T> Trait<'a, 'b> for B<T>+LL | |+LL | | where+LL | |     A<T>: Trait<'a, 'b>,+LL | |     A<T>: NotImplemented,+   | |_________________________^+...+LL | / impl<'a, 'b, T> Trait<'a, 'b> for B<T>+LL | |+LL | | where+LL | |     A<T>: NotImplemented,+   | |_________________________^+...+LL | / impl<'a, T> Trait<'a, 'static> for B<T>+LL | | where+LL | |     C<T>: Trait<'a, 'a>,+   | |________________________^+ error: lifetime may not live long enough-  --> $DIR/fixpoint-rerun-all-cycle-heads.rs:60:5+  --> $DIR/fixpoint-rerun-all-cycle-heads.rs:62:5    | LL | fn check<'a, T>() {    |          -- lifetime `'a` defined here LL |     impls_trait::<'a, 'static, A<T>>();    |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ requires that `'a` must outlive `'static` -error: aborting due to 1 previous error+error: aborting due to 3 previous errors +For more information about this error, try `rustc --explain E0283`.