1use std::ops::ControlFlow;
2
3use rustc_errors::{Applicability, Diag, E0283, E0284, E0790, MultiSpan, struct_span_code_err};
4use rustc_hir as hir;
5use rustc_hir::LangItem;
6use rustc_hir::def::{DefKind, Res};
7use rustc_hir::def_id::DefId;
8use rustc_hir::intravisit::Visitor as _;
9use rustc_infer::infer::{BoundRegionConversionTime, InferCtxt};
10use rustc_infer::traits::util::elaborate;
11use rustc_infer::traits::{
12 Obligation, ObligationCause, ObligationCauseCode, PolyTraitObligation, PredicateObligation,
13};
14use rustc_middle::ty::{self, Ty, TyCtxt, TypeVisitable as _, TypeVisitableExt as _};
15use rustc_span::{DUMMY_SP, ErrorGuaranteed, Span};
16use tracing::{debug, instrument};
17
18use crate::error_reporting::TypeErrCtxt;
19use crate::error_reporting::infer::need_type_info::TypeAnnotationNeeded;
20use crate::error_reporting::traits::{FindExprBySpan, to_pretty_impl_header};
21use crate::traits::ObligationCtxt;
22use crate::traits::query::evaluate_obligation::InferCtxtExt;
23
24#[derive(Debug)]
25pub enum CandidateSource {
26 DefId(DefId),
27 ParamEnv(Span),
28}
29
30pub fn compute_applicable_impls_for_diagnostics<'tcx>(
31 infcx: &InferCtxt<'tcx>,
32 obligation: &PolyTraitObligation<'tcx>,
33) -> Vec<CandidateSource> {
34 let tcx = infcx.tcx;
35 let param_env = obligation.param_env;
36
37 let predicate_polarity = obligation.predicate.skip_binder().polarity;
38
39 let impl_may_apply = |impl_def_id| {
40 let ocx = ObligationCtxt::new(infcx);
41 infcx.enter_forall(obligation.predicate, |placeholder_obligation| {
42 let obligation_trait_ref = ocx.normalize(
43 &ObligationCause::dummy(),
44 param_env,
45 placeholder_obligation.trait_ref,
46 );
47
48 let impl_args = infcx.fresh_args_for_item(DUMMY_SP, impl_def_id);
49 let impl_trait_ref =
50 tcx.impl_trait_ref(impl_def_id).unwrap().instantiate(tcx, impl_args);
51 let impl_trait_ref =
52 ocx.normalize(&ObligationCause::dummy(), param_env, impl_trait_ref);
53
54 if let Err(_) =
55 ocx.eq(&ObligationCause::dummy(), param_env, obligation_trait_ref, impl_trait_ref)
56 {
57 return false;
58 }
59
60 let impl_trait_header = tcx.impl_trait_header(impl_def_id).unwrap();
61 let impl_polarity = impl_trait_header.polarity;
62
63 match (impl_polarity, predicate_polarity) {
64 (ty::ImplPolarity::Positive, ty::PredicatePolarity::Positive)
65 | (ty::ImplPolarity::Negative, ty::PredicatePolarity::Negative) => {}
66 _ => return false,
67 }
68
69 let obligations = tcx
70 .predicates_of(impl_def_id)
71 .instantiate(tcx, impl_args)
72 .into_iter()
73 .map(|(predicate, _)| {
74 Obligation::new(tcx, ObligationCause::dummy(), param_env, predicate)
75 })
76 .filter(|obligation| {
81 infcx.next_trait_solver() || infcx.evaluate_obligation(obligation).is_ok()
82 });
83 ocx.register_obligations(obligations);
84
85 ocx.select_where_possible().is_empty()
86 })
87 };
88
89 let param_env_candidate_may_apply = |poly_trait_predicate: ty::PolyTraitPredicate<'tcx>| {
90 let ocx = ObligationCtxt::new(infcx);
91 infcx.enter_forall(obligation.predicate, |placeholder_obligation| {
92 let obligation_trait_ref = ocx.normalize(
93 &ObligationCause::dummy(),
94 param_env,
95 placeholder_obligation.trait_ref,
96 );
97
98 let param_env_predicate = infcx.instantiate_binder_with_fresh_vars(
99 DUMMY_SP,
100 BoundRegionConversionTime::HigherRankedType,
101 poly_trait_predicate,
102 );
103 let param_env_trait_ref =
104 ocx.normalize(&ObligationCause::dummy(), param_env, param_env_predicate.trait_ref);
105
106 if let Err(_) = ocx.eq(
107 &ObligationCause::dummy(),
108 param_env,
109 obligation_trait_ref,
110 param_env_trait_ref,
111 ) {
112 return false;
113 }
114
115 ocx.select_where_possible().is_empty()
116 })
117 };
118
119 let mut ambiguities = Vec::new();
120
121 tcx.for_each_relevant_impl(
122 obligation.predicate.def_id(),
123 obligation.predicate.skip_binder().trait_ref.self_ty(),
124 |impl_def_id| {
125 if infcx.probe(|_| impl_may_apply(impl_def_id)) {
126 ambiguities.push(CandidateSource::DefId(impl_def_id))
127 }
128 },
129 );
130
131 let predicates =
132 tcx.predicates_of(obligation.cause.body_id.to_def_id()).instantiate_identity(tcx);
133 for (pred, span) in elaborate(tcx, predicates.into_iter()) {
134 let kind = pred.kind();
135 if let ty::ClauseKind::Trait(trait_pred) = kind.skip_binder()
136 && param_env_candidate_may_apply(kind.rebind(trait_pred))
137 {
138 if kind.rebind(trait_pred.trait_ref)
139 == ty::Binder::dummy(ty::TraitRef::identity(tcx, trait_pred.def_id()))
140 {
141 ambiguities.push(CandidateSource::ParamEnv(tcx.def_span(trait_pred.def_id())))
142 } else {
143 ambiguities.push(CandidateSource::ParamEnv(span))
144 }
145 }
146 }
147
148 ambiguities
149}
150
151impl<'a, 'tcx> TypeErrCtxt<'a, 'tcx> {
152 #[instrument(skip(self), level = "debug")]
153 pub(super) fn maybe_report_ambiguity(
154 &self,
155 obligation: &PredicateObligation<'tcx>,
156 ) -> ErrorGuaranteed {
157 let predicate = self.resolve_vars_if_possible(obligation.predicate);
163 let span = obligation.cause.span;
164 let mut file = None;
165
166 debug!(?predicate, obligation.cause.code = ?obligation.cause.code());
167
168 let bound_predicate = predicate.kind();
172 let mut err = match bound_predicate.skip_binder() {
173 ty::PredicateKind::Clause(ty::ClauseKind::Trait(data)) => {
174 let trait_pred = bound_predicate.rebind(data);
175 debug!(?trait_pred);
176
177 if let Err(e) = predicate.error_reported() {
178 return e;
179 }
180
181 if let Err(guar) = self.tcx.ensure_ok().coherent_trait(trait_pred.def_id()) {
182 return guar;
185 }
186
187 if matches!(
203 self.tcx.as_lang_item(trait_pred.def_id()),
204 Some(LangItem::Sized | LangItem::MetaSized)
205 ) {
206 match self.tainted_by_errors() {
207 None => {
208 let err = self.emit_inference_failure_err(
209 obligation.cause.body_id,
210 span,
211 trait_pred.self_ty().skip_binder().into(),
212 TypeAnnotationNeeded::E0282,
213 false,
214 );
215 return err.emit();
216 }
217 Some(e) => return e,
218 }
219 }
220
221 let term = data
235 .trait_ref
236 .args
237 .iter()
238 .filter_map(ty::GenericArg::as_term)
239 .find(|s| s.has_non_region_infer());
240
241 let mut err = if let Some(term) = term {
242 self.emit_inference_failure_err(
243 obligation.cause.body_id,
244 span,
245 term,
246 TypeAnnotationNeeded::E0283,
247 true,
248 )
249 } else {
250 struct_span_code_err!(
251 self.dcx(),
252 span,
253 E0283,
254 "type annotations needed: cannot satisfy `{}`",
255 self.tcx.short_string(predicate, &mut file),
256 )
257 };
258
259 let mut ambiguities = compute_applicable_impls_for_diagnostics(
260 self.infcx,
261 &obligation.with(self.tcx, trait_pred),
262 );
263 let has_non_region_infer = trait_pred
264 .skip_binder()
265 .trait_ref
266 .args
267 .types()
268 .any(|t| !t.is_ty_or_numeric_infer());
269 if ambiguities.len() > 5 {
273 let infcx = self.infcx;
274 if !ambiguities.iter().all(|option| match option {
275 CandidateSource::DefId(did) => infcx.tcx.generics_of(*did).count() == 0,
276 CandidateSource::ParamEnv(_) => true,
277 }) {
278 ambiguities.retain(|option| match option {
280 CandidateSource::DefId(did) => infcx.tcx.generics_of(*did).count() == 0,
281 CandidateSource::ParamEnv(_) => true,
282 });
283 }
284 }
285 if ambiguities.len() > 1 && ambiguities.len() < 10 && has_non_region_infer {
286 if let Some(e) = self.tainted_by_errors()
287 && term.is_none()
288 {
289 err.cancel();
294 return e;
295 }
296 self.annotate_source_of_ambiguity(&mut err, &ambiguities, predicate);
297 } else {
298 if let Some(e) = self.tainted_by_errors() {
299 err.cancel();
300 return e;
301 }
302 let pred = self.tcx.short_string(predicate, &mut file);
303 err.note(format!("cannot satisfy `{pred}`"));
304 let impl_candidates =
305 self.find_similar_impl_candidates(predicate.as_trait_clause().unwrap());
306 if impl_candidates.len() < 40 {
307 self.report_similar_impl_candidates(
308 impl_candidates.as_slice(),
309 trait_pred,
310 obligation.cause.body_id,
311 &mut err,
312 false,
313 obligation.param_env,
314 );
315 }
316 }
317
318 if let ObligationCauseCode::WhereClause(def_id, _)
319 | ObligationCauseCode::WhereClauseInExpr(def_id, ..) = *obligation.cause.code()
320 {
321 self.suggest_fully_qualified_path(&mut err, def_id, span, trait_pred.def_id());
322 }
323
324 if term.is_some_and(|term| term.as_type().is_some())
325 && let Some(body) = self.tcx.hir_maybe_body_owned_by(obligation.cause.body_id)
326 {
327 let mut expr_finder = FindExprBySpan::new(span, self.tcx);
328 expr_finder.visit_expr(&body.value);
329
330 if let Some(hir::Expr {
331 kind:
332 hir::ExprKind::Call(
333 hir::Expr {
334 kind: hir::ExprKind::Path(hir::QPath::Resolved(None, path)),
335 ..
336 },
337 _,
338 )
339 | hir::ExprKind::Path(hir::QPath::Resolved(None, path)),
340 ..
341 }) = expr_finder.result
342 && let [
343 ..,
344 trait_path_segment @ hir::PathSegment {
345 res: Res::Def(DefKind::Trait, trait_id),
346 ..
347 },
348 hir::PathSegment {
349 ident: assoc_item_ident,
350 res: Res::Def(_, item_id),
351 ..
352 },
353 ] = path.segments
354 && data.trait_ref.def_id == *trait_id
355 && self.tcx.trait_of_item(*item_id) == Some(*trait_id)
356 && let None = self.tainted_by_errors()
357 {
358 let (verb, noun) = match self.tcx.associated_item(item_id).kind {
359 ty::AssocKind::Const { .. } => ("refer to the", "constant"),
360 ty::AssocKind::Fn { .. } => ("call", "function"),
361 ty::AssocKind::Type { .. } => ("refer to the", "type"),
364 };
365
366 err.cancel();
368 err = self.dcx().struct_span_err(
369 span,
370 format!(
371 "cannot {verb} associated {noun} on trait without specifying the \
372 corresponding `impl` type",
373 ),
374 );
375 err.code(E0790);
376
377 if let Some(local_def_id) = data.trait_ref.def_id.as_local()
378 && let hir::Node::Item(hir::Item {
379 kind: hir::ItemKind::Trait(_, _, trait_ident, _, _, trait_item_refs),
380 ..
381 }) = self.tcx.hir_node_by_def_id(local_def_id)
382 && let Some(method_ref) = trait_item_refs
383 .iter()
384 .find(|item_ref| item_ref.ident == *assoc_item_ident)
385 {
386 err.span_label(
387 method_ref.span,
388 format!("`{trait_ident}::{assoc_item_ident}` defined here"),
389 );
390 }
391
392 err.span_label(span, format!("cannot {verb} associated {noun} of trait"));
393
394 let trait_impls = self.tcx.trait_impls_of(data.trait_ref.def_id);
395
396 if let Some(impl_def_id) =
397 trait_impls.non_blanket_impls().values().flatten().next()
398 {
399 let non_blanket_impl_count =
400 trait_impls.non_blanket_impls().values().flatten().count();
401 let (message, self_types) = if non_blanket_impl_count == 1 {
404 (
405 "use the fully-qualified path to the only available \
406 implementation",
407 vec![format!(
408 "{}",
409 self.tcx.type_of(impl_def_id).instantiate_identity()
410 )],
411 )
412 } else if non_blanket_impl_count < 20 {
413 (
414 "use a fully-qualified path to one of the available \
415 implementations",
416 trait_impls
417 .non_blanket_impls()
418 .values()
419 .flatten()
420 .map(|id| {
421 format!(
422 "{}",
423 self.tcx.type_of(id).instantiate_identity()
424 )
425 })
426 .collect::<Vec<String>>(),
427 )
428 } else {
429 (
430 "use a fully-qualified path to a specific available \
431 implementation",
432 vec!["/* self type */".to_string()],
433 )
434 };
435 let suggestions: Vec<_> = self_types
436 .into_iter()
437 .map(|self_type| {
438 let mut suggestions = vec![(
439 path.span.shrink_to_lo(),
440 format!("<{self_type} as "),
441 )];
442 if let Some(generic_arg) = trait_path_segment.args {
443 let between_span = trait_path_segment
444 .ident
445 .span
446 .between(generic_arg.span_ext);
447 suggestions.push((between_span, "".to_string()));
450 suggestions.push((
451 generic_arg.span_ext.shrink_to_hi(),
452 ">".to_string(),
453 ));
454 } else {
455 suggestions.push((
456 trait_path_segment.ident.span.shrink_to_hi(),
457 ">".to_string(),
458 ));
459 }
460 suggestions
461 })
462 .collect();
463 err.multipart_suggestions(
464 message,
465 suggestions,
466 Applicability::MaybeIncorrect,
467 );
468 }
469 }
470 };
471
472 err
473 }
474
475 ty::PredicateKind::Clause(ty::ClauseKind::WellFormed(term)) => {
476 if let Err(e) = term.error_reported() {
480 return e;
481 }
482 if let Some(e) = self.tainted_by_errors() {
483 return e;
484 }
485
486 self.emit_inference_failure_err(
487 obligation.cause.body_id,
488 span,
489 term,
490 TypeAnnotationNeeded::E0282,
491 false,
492 )
493 }
494
495 ty::PredicateKind::Subtype(data) => {
496 if let Err(e) = data.error_reported() {
497 return e;
498 }
499 if let Some(e) = self.tainted_by_errors() {
500 return e;
501 }
502 let ty::SubtypePredicate { a_is_expected: _, a, b } = data;
503 assert!(a.is_ty_var() && b.is_ty_var());
505 self.emit_inference_failure_err(
506 obligation.cause.body_id,
507 span,
508 a.into(),
509 TypeAnnotationNeeded::E0282,
510 true,
511 )
512 }
513 ty::PredicateKind::Clause(ty::ClauseKind::Projection(data)) => {
514 if let Err(e) = predicate.error_reported() {
515 return e;
516 }
517 if let Some(e) = self.tainted_by_errors() {
518 return e;
519 }
520
521 if let Err(guar) = self
522 .tcx
523 .ensure_ok()
524 .coherent_trait(self.tcx.parent(data.projection_term.def_id))
525 {
526 return guar;
529 }
530 let term = data
531 .projection_term
532 .args
533 .iter()
534 .filter_map(ty::GenericArg::as_term)
535 .chain([data.term])
536 .find(|g| g.has_non_region_infer());
537 let predicate = self.tcx.short_string(predicate, &mut file);
538 if let Some(term) = term {
539 self.emit_inference_failure_err(
540 obligation.cause.body_id,
541 span,
542 term,
543 TypeAnnotationNeeded::E0284,
544 true,
545 )
546 .with_note(format!("cannot satisfy `{predicate}`"))
547 } else {
548 struct_span_code_err!(
550 self.dcx(),
551 span,
552 E0284,
553 "type annotations needed: cannot satisfy `{predicate}`",
554 )
555 .with_span_label(span, format!("cannot satisfy `{predicate}`"))
556 }
557 }
558
559 ty::PredicateKind::Clause(ty::ClauseKind::ConstEvaluatable(data)) => {
560 if let Err(e) = predicate.error_reported() {
561 return e;
562 }
563 if let Some(e) = self.tainted_by_errors() {
564 return e;
565 }
566 let term =
567 data.walk().filter_map(ty::GenericArg::as_term).find(|term| term.is_infer());
568 if let Some(term) = term {
569 let err = self.emit_inference_failure_err(
570 obligation.cause.body_id,
571 span,
572 term,
573 TypeAnnotationNeeded::E0284,
574 true,
575 );
576 err
577 } else {
578 let predicate = self.tcx.short_string(predicate, &mut file);
580 struct_span_code_err!(
581 self.dcx(),
582 span,
583 E0284,
584 "type annotations needed: cannot satisfy `{predicate}`",
585 )
586 .with_span_label(span, format!("cannot satisfy `{predicate}`"))
587 }
588 }
589
590 ty::PredicateKind::Clause(ty::ClauseKind::ConstArgHasType(ct, ..)) => self
591 .emit_inference_failure_err(
592 obligation.cause.body_id,
593 span,
594 ct.into(),
595 TypeAnnotationNeeded::E0284,
596 true,
597 ),
598 ty::PredicateKind::NormalizesTo(ty::NormalizesTo { alias, term })
599 if term.is_infer() =>
600 {
601 if let Some(e) = self.tainted_by_errors() {
602 return e;
603 }
604 let alias = self.tcx.short_string(alias, &mut file);
605 struct_span_code_err!(
606 self.dcx(),
607 span,
608 E0284,
609 "type annotations needed: cannot normalize `{alias}`",
610 )
611 .with_span_label(span, format!("cannot normalize `{alias}`"))
612 }
613
614 _ => {
615 if let Some(e) = self.tainted_by_errors() {
616 return e;
617 }
618 let predicate = self.tcx.short_string(predicate, &mut file);
619 struct_span_code_err!(
620 self.dcx(),
621 span,
622 E0284,
623 "type annotations needed: cannot satisfy `{predicate}`",
624 )
625 .with_span_label(span, format!("cannot satisfy `{predicate}`"))
626 }
627 };
628 *err.long_ty_path() = file;
629 self.note_obligation_cause(&mut err, obligation);
630 err.emit()
631 }
632
633 fn annotate_source_of_ambiguity(
634 &self,
635 err: &mut Diag<'_>,
636 ambiguities: &[CandidateSource],
637 predicate: ty::Predicate<'tcx>,
638 ) {
639 let mut spans = vec![];
640 let mut crates = vec![];
641 let mut post = vec![];
642 let mut has_param_env = false;
643 for ambiguity in ambiguities {
644 match ambiguity {
645 CandidateSource::DefId(impl_def_id) => match self.tcx.span_of_impl(*impl_def_id) {
646 Ok(span) => spans.push(span),
647 Err(name) => {
648 crates.push(name);
649 if let Some(header) = to_pretty_impl_header(self.tcx, *impl_def_id) {
650 post.push(header);
651 }
652 }
653 },
654 CandidateSource::ParamEnv(span) => {
655 has_param_env = true;
656 spans.push(*span);
657 }
658 }
659 }
660 let mut crate_names: Vec<_> = crates.iter().map(|n| format!("`{n}`")).collect();
661 crate_names.sort();
662 crate_names.dedup();
663 post.sort();
664 post.dedup();
665
666 if self.tainted_by_errors().is_some()
667 && (crate_names.len() == 1
668 && spans.len() == 0
669 && ["`core`", "`alloc`", "`std`"].contains(&crate_names[0].as_str())
670 || predicate.visit_with(&mut HasNumericInferVisitor).is_break())
671 {
672 err.downgrade_to_delayed_bug();
678 return;
679 }
680
681 let msg = format!(
682 "multiple `impl`s{} satisfying `{}` found",
683 if has_param_env { " or `where` clauses" } else { "" },
684 predicate
685 );
686 let post = if post.len() > 1 || (post.len() == 1 && post[0].contains('\n')) {
687 format!(":\n{}", post.iter().map(|p| format!("- {p}")).collect::<Vec<_>>().join("\n"),)
688 } else if post.len() == 1 {
689 format!(": `{}`", post[0])
690 } else {
691 String::new()
692 };
693
694 match (spans.len(), crates.len(), crate_names.len()) {
695 (0, 0, 0) => {
696 err.note(format!("cannot satisfy `{predicate}`"));
697 }
698 (0, _, 1) => {
699 err.note(format!("{} in the `{}` crate{}", msg, crates[0], post,));
700 }
701 (0, _, _) => {
702 err.note(format!(
703 "{} in the following crates: {}{}",
704 msg,
705 crate_names.join(", "),
706 post,
707 ));
708 }
709 (_, 0, 0) => {
710 let span: MultiSpan = spans.into();
711 err.span_note(span, msg);
712 }
713 (_, 1, 1) => {
714 let span: MultiSpan = spans.into();
715 err.span_note(span, msg);
716 err.note(format!("and another `impl` found in the `{}` crate{}", crates[0], post,));
717 }
718 _ => {
719 let span: MultiSpan = spans.into();
720 err.span_note(span, msg);
721 err.note(format!(
722 "and more `impl`s found in the following crates: {}{}",
723 crate_names.join(", "),
724 post,
725 ));
726 }
727 }
728 }
729}
730
731struct HasNumericInferVisitor;
732
733impl<'tcx> ty::TypeVisitor<TyCtxt<'tcx>> for HasNumericInferVisitor {
734 type Result = ControlFlow<()>;
735
736 fn visit_ty(&mut self, ty: Ty<'tcx>) -> Self::Result {
737 if matches!(ty.kind(), ty::Infer(ty::FloatVar(_) | ty::IntVar(_))) {
738 ControlFlow::Break(())
739 } else {
740 ControlFlow::Continue(())
741 }
742 }
743}