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