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 self.tcx.is_lang_item(trait_pred.def_id(), LangItem::Sized) {
203 match self.tainted_by_errors() {
204 None => {
205 let err = self.emit_inference_failure_err(
206 obligation.cause.body_id,
207 span,
208 trait_pred.self_ty().skip_binder().into(),
209 TypeAnnotationNeeded::E0282,
210 false,
211 );
212 return err.emit();
213 }
214 Some(e) => return e,
215 }
216 }
217
218 let term = data
232 .trait_ref
233 .args
234 .iter()
235 .filter_map(ty::GenericArg::as_term)
236 .find(|s| s.has_non_region_infer());
237
238 let mut err = if let Some(term) = term {
239 self.emit_inference_failure_err(
240 obligation.cause.body_id,
241 span,
242 term,
243 TypeAnnotationNeeded::E0283,
244 true,
245 )
246 } else {
247 struct_span_code_err!(
248 self.dcx(),
249 span,
250 E0283,
251 "type annotations needed: cannot satisfy `{}`",
252 self.tcx.short_string(predicate, &mut file),
253 )
254 };
255
256 let mut ambiguities = compute_applicable_impls_for_diagnostics(
257 self.infcx,
258 &obligation.with(self.tcx, trait_pred),
259 );
260 let has_non_region_infer = trait_pred
261 .skip_binder()
262 .trait_ref
263 .args
264 .types()
265 .any(|t| !t.is_ty_or_numeric_infer());
266 if ambiguities.len() > 5 {
270 let infcx = self.infcx;
271 if !ambiguities.iter().all(|option| match option {
272 CandidateSource::DefId(did) => infcx.tcx.generics_of(*did).count() == 0,
273 CandidateSource::ParamEnv(_) => true,
274 }) {
275 ambiguities.retain(|option| match option {
277 CandidateSource::DefId(did) => infcx.tcx.generics_of(*did).count() == 0,
278 CandidateSource::ParamEnv(_) => true,
279 });
280 }
281 }
282 if ambiguities.len() > 1 && ambiguities.len() < 10 && has_non_region_infer {
283 if let Some(e) = self.tainted_by_errors()
284 && term.is_none()
285 {
286 err.cancel();
291 return e;
292 }
293 self.annotate_source_of_ambiguity(&mut err, &ambiguities, predicate);
294 } else {
295 if let Some(e) = self.tainted_by_errors() {
296 err.cancel();
297 return e;
298 }
299 let pred = self.tcx.short_string(predicate, &mut file);
300 err.note(format!("cannot satisfy `{pred}`"));
301 let impl_candidates =
302 self.find_similar_impl_candidates(predicate.as_trait_clause().unwrap());
303 if impl_candidates.len() < 40 {
304 self.report_similar_impl_candidates(
305 impl_candidates.as_slice(),
306 trait_pred,
307 obligation.cause.body_id,
308 &mut err,
309 false,
310 obligation.param_env,
311 );
312 }
313 }
314
315 if let ObligationCauseCode::WhereClause(def_id, _)
316 | ObligationCauseCode::WhereClauseInExpr(def_id, ..) = *obligation.cause.code()
317 {
318 self.suggest_fully_qualified_path(&mut err, def_id, span, trait_pred.def_id());
319 }
320
321 if term.is_some_and(|term| term.as_type().is_some())
322 && let Some(body) = self.tcx.hir_maybe_body_owned_by(obligation.cause.body_id)
323 {
324 let mut expr_finder = FindExprBySpan::new(span, self.tcx);
325 expr_finder.visit_expr(&body.value);
326
327 if let Some(hir::Expr {
328 kind:
329 hir::ExprKind::Call(
330 hir::Expr {
331 kind: hir::ExprKind::Path(hir::QPath::Resolved(None, path)),
332 ..
333 },
334 _,
335 )
336 | hir::ExprKind::Path(hir::QPath::Resolved(None, path)),
337 ..
338 }) = expr_finder.result
339 && let [
340 ..,
341 trait_path_segment @ hir::PathSegment {
342 res: Res::Def(DefKind::Trait, trait_id),
343 ..
344 },
345 hir::PathSegment {
346 ident: assoc_item_ident,
347 res: Res::Def(_, item_id),
348 ..
349 },
350 ] = path.segments
351 && data.trait_ref.def_id == *trait_id
352 && self.tcx.trait_of_item(*item_id) == Some(*trait_id)
353 && let None = self.tainted_by_errors()
354 {
355 let (verb, noun) = match self.tcx.associated_item(item_id).kind {
356 ty::AssocKind::Const { .. } => ("refer to the", "constant"),
357 ty::AssocKind::Fn { .. } => ("call", "function"),
358 ty::AssocKind::Type { .. } => ("refer to the", "type"),
361 };
362
363 err.cancel();
365 err = self.dcx().struct_span_err(
366 span,
367 format!(
368 "cannot {verb} associated {noun} on trait without specifying the \
369 corresponding `impl` type",
370 ),
371 );
372 err.code(E0790);
373
374 if let Some(local_def_id) = data.trait_ref.def_id.as_local()
375 && let hir::Node::Item(hir::Item {
376 kind: hir::ItemKind::Trait(_, _, trait_ident, _, _, trait_item_refs),
377 ..
378 }) = self.tcx.hir_node_by_def_id(local_def_id)
379 && let Some(method_ref) = trait_item_refs
380 .iter()
381 .find(|item_ref| item_ref.ident == *assoc_item_ident)
382 {
383 err.span_label(
384 method_ref.span,
385 format!("`{trait_ident}::{assoc_item_ident}` defined here"),
386 );
387 }
388
389 err.span_label(span, format!("cannot {verb} associated {noun} of trait"));
390
391 let trait_impls = self.tcx.trait_impls_of(data.trait_ref.def_id);
392
393 if let Some(impl_def_id) =
394 trait_impls.non_blanket_impls().values().flatten().next()
395 {
396 let non_blanket_impl_count =
397 trait_impls.non_blanket_impls().values().flatten().count();
398 let (message, self_types) = if non_blanket_impl_count == 1 {
401 (
402 "use the fully-qualified path to the only available \
403 implementation",
404 vec![format!(
405 "{}",
406 self.tcx.type_of(impl_def_id).instantiate_identity()
407 )],
408 )
409 } else if non_blanket_impl_count < 20 {
410 (
411 "use a fully-qualified path to one of the available \
412 implementations",
413 trait_impls
414 .non_blanket_impls()
415 .values()
416 .flatten()
417 .map(|id| {
418 format!(
419 "{}",
420 self.tcx.type_of(id).instantiate_identity()
421 )
422 })
423 .collect::<Vec<String>>(),
424 )
425 } else {
426 (
427 "use a fully-qualified path to a specific available \
428 implementation",
429 vec!["/* self type */".to_string()],
430 )
431 };
432 let suggestions: Vec<_> = self_types
433 .into_iter()
434 .map(|self_type| {
435 let mut suggestions = vec![(
436 path.span.shrink_to_lo(),
437 format!("<{self_type} as "),
438 )];
439 if let Some(generic_arg) = trait_path_segment.args {
440 let between_span = trait_path_segment
441 .ident
442 .span
443 .between(generic_arg.span_ext);
444 suggestions.push((between_span, "".to_string()));
447 suggestions.push((
448 generic_arg.span_ext.shrink_to_hi(),
449 ">".to_string(),
450 ));
451 } else {
452 suggestions.push((
453 trait_path_segment.ident.span.shrink_to_hi(),
454 ">".to_string(),
455 ));
456 }
457 suggestions
458 })
459 .collect();
460 err.multipart_suggestions(
461 message,
462 suggestions,
463 Applicability::MaybeIncorrect,
464 );
465 }
466 }
467 };
468
469 err
470 }
471
472 ty::PredicateKind::Clause(ty::ClauseKind::WellFormed(term)) => {
473 if let Err(e) = term.error_reported() {
477 return e;
478 }
479 if let Some(e) = self.tainted_by_errors() {
480 return e;
481 }
482
483 self.emit_inference_failure_err(
484 obligation.cause.body_id,
485 span,
486 term,
487 TypeAnnotationNeeded::E0282,
488 false,
489 )
490 }
491
492 ty::PredicateKind::Subtype(data) => {
493 if let Err(e) = data.error_reported() {
494 return e;
495 }
496 if let Some(e) = self.tainted_by_errors() {
497 return e;
498 }
499 let ty::SubtypePredicate { a_is_expected: _, a, b } = data;
500 assert!(a.is_ty_var() && b.is_ty_var());
502 self.emit_inference_failure_err(
503 obligation.cause.body_id,
504 span,
505 a.into(),
506 TypeAnnotationNeeded::E0282,
507 true,
508 )
509 }
510 ty::PredicateKind::Clause(ty::ClauseKind::Projection(data)) => {
511 if let Err(e) = predicate.error_reported() {
512 return e;
513 }
514 if let Some(e) = self.tainted_by_errors() {
515 return e;
516 }
517
518 if let Err(guar) = self
519 .tcx
520 .ensure_ok()
521 .coherent_trait(self.tcx.parent(data.projection_term.def_id))
522 {
523 return guar;
526 }
527 let term = data
528 .projection_term
529 .args
530 .iter()
531 .filter_map(ty::GenericArg::as_term)
532 .chain([data.term])
533 .find(|g| g.has_non_region_infer());
534 let predicate = self.tcx.short_string(predicate, &mut file);
535 if let Some(term) = term {
536 self.emit_inference_failure_err(
537 obligation.cause.body_id,
538 span,
539 term,
540 TypeAnnotationNeeded::E0284,
541 true,
542 )
543 .with_note(format!("cannot satisfy `{predicate}`"))
544 } else {
545 struct_span_code_err!(
547 self.dcx(),
548 span,
549 E0284,
550 "type annotations needed: cannot satisfy `{predicate}`",
551 )
552 .with_span_label(span, format!("cannot satisfy `{predicate}`"))
553 }
554 }
555
556 ty::PredicateKind::Clause(ty::ClauseKind::ConstEvaluatable(data)) => {
557 if let Err(e) = predicate.error_reported() {
558 return e;
559 }
560 if let Some(e) = self.tainted_by_errors() {
561 return e;
562 }
563 let term =
564 data.walk().filter_map(ty::GenericArg::as_term).find(|term| term.is_infer());
565 if let Some(term) = term {
566 let err = self.emit_inference_failure_err(
567 obligation.cause.body_id,
568 span,
569 term,
570 TypeAnnotationNeeded::E0284,
571 true,
572 );
573 err
574 } else {
575 let predicate = self.tcx.short_string(predicate, &mut file);
577 struct_span_code_err!(
578 self.dcx(),
579 span,
580 E0284,
581 "type annotations needed: cannot satisfy `{predicate}`",
582 )
583 .with_span_label(span, format!("cannot satisfy `{predicate}`"))
584 }
585 }
586
587 ty::PredicateKind::Clause(ty::ClauseKind::ConstArgHasType(ct, ..)) => self
588 .emit_inference_failure_err(
589 obligation.cause.body_id,
590 span,
591 ct.into(),
592 TypeAnnotationNeeded::E0284,
593 true,
594 ),
595 ty::PredicateKind::NormalizesTo(ty::NormalizesTo { alias, term })
596 if term.is_infer() =>
597 {
598 if let Some(e) = self.tainted_by_errors() {
599 return e;
600 }
601 let alias = self.tcx.short_string(alias, &mut file);
602 struct_span_code_err!(
603 self.dcx(),
604 span,
605 E0284,
606 "type annotations needed: cannot normalize `{alias}`",
607 )
608 .with_span_label(span, format!("cannot normalize `{alias}`"))
609 }
610
611 _ => {
612 if let Some(e) = self.tainted_by_errors() {
613 return e;
614 }
615 let predicate = self.tcx.short_string(predicate, &mut file);
616 struct_span_code_err!(
617 self.dcx(),
618 span,
619 E0284,
620 "type annotations needed: cannot satisfy `{predicate}`",
621 )
622 .with_span_label(span, format!("cannot satisfy `{predicate}`"))
623 }
624 };
625 *err.long_ty_path() = file;
626 self.note_obligation_cause(&mut err, obligation);
627 err.emit()
628 }
629
630 fn annotate_source_of_ambiguity(
631 &self,
632 err: &mut Diag<'_>,
633 ambiguities: &[CandidateSource],
634 predicate: ty::Predicate<'tcx>,
635 ) {
636 let mut spans = vec![];
637 let mut crates = vec![];
638 let mut post = vec![];
639 let mut has_param_env = false;
640 for ambiguity in ambiguities {
641 match ambiguity {
642 CandidateSource::DefId(impl_def_id) => match self.tcx.span_of_impl(*impl_def_id) {
643 Ok(span) => spans.push(span),
644 Err(name) => {
645 crates.push(name);
646 if let Some(header) = to_pretty_impl_header(self.tcx, *impl_def_id) {
647 post.push(header);
648 }
649 }
650 },
651 CandidateSource::ParamEnv(span) => {
652 has_param_env = true;
653 spans.push(*span);
654 }
655 }
656 }
657 let mut crate_names: Vec<_> = crates.iter().map(|n| format!("`{n}`")).collect();
658 crate_names.sort();
659 crate_names.dedup();
660 post.sort();
661 post.dedup();
662
663 if self.tainted_by_errors().is_some()
664 && (crate_names.len() == 1
665 && spans.len() == 0
666 && ["`core`", "`alloc`", "`std`"].contains(&crate_names[0].as_str())
667 || predicate.visit_with(&mut HasNumericInferVisitor).is_break())
668 {
669 err.downgrade_to_delayed_bug();
675 return;
676 }
677
678 let msg = format!(
679 "multiple `impl`s{} satisfying `{}` found",
680 if has_param_env { " or `where` clauses" } else { "" },
681 predicate
682 );
683 let post = if post.len() > 1 || (post.len() == 1 && post[0].contains('\n')) {
684 format!(":\n{}", post.iter().map(|p| format!("- {p}")).collect::<Vec<_>>().join("\n"),)
685 } else if post.len() == 1 {
686 format!(": `{}`", post[0])
687 } else {
688 String::new()
689 };
690
691 match (spans.len(), crates.len(), crate_names.len()) {
692 (0, 0, 0) => {
693 err.note(format!("cannot satisfy `{predicate}`"));
694 }
695 (0, _, 1) => {
696 err.note(format!("{} in the `{}` crate{}", msg, crates[0], post,));
697 }
698 (0, _, _) => {
699 err.note(format!(
700 "{} in the following crates: {}{}",
701 msg,
702 crate_names.join(", "),
703 post,
704 ));
705 }
706 (_, 0, 0) => {
707 let span: MultiSpan = spans.into();
708 err.span_note(span, msg);
709 }
710 (_, 1, 1) => {
711 let span: MultiSpan = spans.into();
712 err.span_note(span, msg);
713 err.note(format!("and another `impl` found in the `{}` crate{}", crates[0], post,));
714 }
715 _ => {
716 let span: MultiSpan = spans.into();
717 err.span_note(span, msg);
718 err.note(format!(
719 "and more `impl`s found in the following crates: {}{}",
720 crate_names.join(", "),
721 post,
722 ));
723 }
724 }
725 }
726}
727
728struct HasNumericInferVisitor;
729
730impl<'tcx> ty::TypeVisitor<TyCtxt<'tcx>> for HasNumericInferVisitor {
731 type Result = ControlFlow<()>;
732
733 fn visit_ty(&mut self, ty: Ty<'tcx>) -> Self::Result {
734 if matches!(ty.kind(), ty::Infer(ty::FloatVar(_) | ty::IntVar(_))) {
735 ControlFlow::Break(())
736 } else {
737 ControlFlow::Continue(())
738 }
739 }
740}