1use std::ops::ControlFlow;
2
3use rustc_hir::LangItem;
4use rustc_infer::infer::InferCtxt;
5use rustc_infer::traits::solve::{CandidateSource, GoalSource, MaybeCause};
6use rustc_infer::traits::{
7 self, MismatchedProjectionTypes, Obligation, ObligationCause, ObligationCauseCode,
8 PredicateObligation, SelectionError,
9};
10use rustc_middle::traits::query::NoSolution;
11use rustc_middle::ty::error::{ExpectedFound, TypeError};
12use rustc_middle::ty::{self, Ty, TyCtxt};
13use rustc_middle::{bug, span_bug};
14use rustc_next_trait_solver::solve::{GoalEvaluation, SolverDelegateEvalExt as _};
15use tracing::{instrument, trace};
16
17use crate::solve::delegate::SolverDelegate;
18use crate::solve::inspect::{self, ProofTreeInferCtxtExt, ProofTreeVisitor};
19use crate::solve::{Certainty, deeply_normalize_for_diagnostics};
20use crate::traits::{FulfillmentError, FulfillmentErrorCode, wf};
21
22pub(super) fn fulfillment_error_for_no_solution<'tcx>(
23 infcx: &InferCtxt<'tcx>,
24 root_obligation: PredicateObligation<'tcx>,
25) -> FulfillmentError<'tcx> {
26 let obligation = find_best_leaf_obligation(infcx, &root_obligation, false);
27
28 let code = match obligation.predicate.kind().skip_binder() {
29 ty::PredicateKind::Clause(ty::ClauseKind::Projection(_)) => {
30 FulfillmentErrorCode::Project(
31 MismatchedProjectionTypes { err: TypeError::Mismatch },
33 )
34 }
35 ty::PredicateKind::Clause(ty::ClauseKind::ConstArgHasType(ct, expected_ty)) => {
36 let ct_ty = match ct.kind() {
37 ty::ConstKind::Unevaluated(uv) => {
38 infcx.tcx.type_of(uv.def).instantiate(infcx.tcx, uv.args)
39 }
40 ty::ConstKind::Param(param_ct) => {
41 param_ct.find_const_ty_from_env(obligation.param_env)
42 }
43 ty::ConstKind::Value(cv) => cv.ty,
44 kind => span_bug!(
45 obligation.cause.span,
46 "ConstArgHasWrongType failed but we don't know how to compute type for {kind:?}"
47 ),
48 };
49 FulfillmentErrorCode::Select(SelectionError::ConstArgHasWrongType {
50 ct,
51 ct_ty,
52 expected_ty,
53 })
54 }
55 ty::PredicateKind::NormalizesTo(..) => {
56 FulfillmentErrorCode::Project(MismatchedProjectionTypes { err: TypeError::Mismatch })
57 }
58 ty::PredicateKind::AliasRelate(_, _, _) => {
59 FulfillmentErrorCode::Project(MismatchedProjectionTypes { err: TypeError::Mismatch })
60 }
61 ty::PredicateKind::Subtype(pred) => {
62 let (a, b) = infcx.enter_forall_and_leak_universe(
63 obligation.predicate.kind().rebind((pred.a, pred.b)),
64 );
65 let expected_found = ExpectedFound::new(a, b);
66 FulfillmentErrorCode::Subtype(expected_found, TypeError::Sorts(expected_found))
67 }
68 ty::PredicateKind::Coerce(pred) => {
69 let (a, b) = infcx.enter_forall_and_leak_universe(
70 obligation.predicate.kind().rebind((pred.a, pred.b)),
71 );
72 let expected_found = ExpectedFound::new(b, a);
73 FulfillmentErrorCode::Subtype(expected_found, TypeError::Sorts(expected_found))
74 }
75 ty::PredicateKind::Clause(_)
76 | ty::PredicateKind::DynCompatible(_)
77 | ty::PredicateKind::Ambiguous => {
78 FulfillmentErrorCode::Select(SelectionError::Unimplemented)
79 }
80 ty::PredicateKind::ConstEquate(..) => {
81 bug!("unexpected goal: {obligation:?}")
82 }
83 };
84
85 FulfillmentError { obligation, code, root_obligation }
86}
87
88pub(super) fn fulfillment_error_for_stalled<'tcx>(
89 infcx: &InferCtxt<'tcx>,
90 root_obligation: PredicateObligation<'tcx>,
91) -> FulfillmentError<'tcx> {
92 let (code, refine_obligation) = infcx.probe(|_| {
93 match <&SolverDelegate<'tcx>>::from(infcx).evaluate_root_goal(
94 root_obligation.as_goal(),
95 root_obligation.cause.span,
96 None,
97 ) {
98 Ok(GoalEvaluation { certainty: Certainty::Maybe(MaybeCause::Ambiguity), .. }) => {
99 (FulfillmentErrorCode::Ambiguity { overflow: None }, true)
100 }
101 Ok(GoalEvaluation {
102 certainty:
103 Certainty::Maybe(MaybeCause::Overflow {
104 suggest_increasing_limit,
105 keep_constraints: _,
106 }),
107 ..
108 }) => (
109 FulfillmentErrorCode::Ambiguity { overflow: Some(suggest_increasing_limit) },
110 false,
117 ),
118 Ok(GoalEvaluation { certainty: Certainty::Yes, .. }) => {
119 span_bug!(
120 root_obligation.cause.span,
121 "did not expect successful goal when collecting ambiguity errors for `{:?}`",
122 infcx.resolve_vars_if_possible(root_obligation.predicate),
123 )
124 }
125 Err(_) => {
126 span_bug!(
127 root_obligation.cause.span,
128 "did not expect selection error when collecting ambiguity errors for `{:?}`",
129 infcx.resolve_vars_if_possible(root_obligation.predicate),
130 )
131 }
132 }
133 });
134
135 FulfillmentError {
136 obligation: if refine_obligation {
137 find_best_leaf_obligation(infcx, &root_obligation, true)
138 } else {
139 root_obligation.clone()
140 },
141 code,
142 root_obligation,
143 }
144}
145
146pub(super) fn fulfillment_error_for_overflow<'tcx>(
147 infcx: &InferCtxt<'tcx>,
148 root_obligation: PredicateObligation<'tcx>,
149) -> FulfillmentError<'tcx> {
150 FulfillmentError {
151 obligation: find_best_leaf_obligation(infcx, &root_obligation, true),
152 code: FulfillmentErrorCode::Ambiguity { overflow: Some(true) },
153 root_obligation,
154 }
155}
156
157#[instrument(level = "debug", skip(infcx), ret)]
158fn find_best_leaf_obligation<'tcx>(
159 infcx: &InferCtxt<'tcx>,
160 obligation: &PredicateObligation<'tcx>,
161 consider_ambiguities: bool,
162) -> PredicateObligation<'tcx> {
163 let obligation = infcx.resolve_vars_if_possible(obligation.clone());
164 let obligation = infcx
170 .fudge_inference_if_ok(|| {
171 infcx
172 .visit_proof_tree(
173 obligation.as_goal(),
174 &mut BestObligation { obligation: obligation.clone(), consider_ambiguities },
175 )
176 .break_value()
177 .ok_or(())
178 })
179 .unwrap_or(obligation);
180 deeply_normalize_for_diagnostics(infcx, obligation.param_env, obligation)
181}
182
183struct BestObligation<'tcx> {
184 obligation: PredicateObligation<'tcx>,
185 consider_ambiguities: bool,
186}
187
188impl<'tcx> BestObligation<'tcx> {
189 fn with_derived_obligation(
190 &mut self,
191 derived_obligation: PredicateObligation<'tcx>,
192 and_then: impl FnOnce(&mut Self) -> <Self as ProofTreeVisitor<'tcx>>::Result,
193 ) -> <Self as ProofTreeVisitor<'tcx>>::Result {
194 let old_obligation = std::mem::replace(&mut self.obligation, derived_obligation);
195 let res = and_then(self);
196 self.obligation = old_obligation;
197 res
198 }
199
200 fn non_trivial_candidates<'a>(
205 &self,
206 goal: &'a inspect::InspectGoal<'a, 'tcx>,
207 ) -> Vec<inspect::InspectCandidate<'a, 'tcx>> {
208 let mut candidates = goal.candidates();
209 match self.consider_ambiguities {
210 true => {
211 candidates.retain(|candidate| candidate.result().is_ok());
215 }
216 false => {
217 candidates.retain(|c| !matches!(c.kind(), inspect::ProbeKind::RigidAlias { .. }));
220 if candidates.len() > 1 {
224 candidates.retain(|candidate| {
225 goal.infcx().probe(|_| {
226 candidate.instantiate_nested_goals(self.span()).iter().any(
227 |nested_goal| {
228 matches!(
229 nested_goal.source(),
230 GoalSource::ImplWhereBound
231 | GoalSource::AliasBoundConstCondition
232 | GoalSource::InstantiateHigherRanked
233 | GoalSource::AliasWellFormed
234 ) && nested_goal.result().is_err()
235 },
236 )
237 })
238 });
239 }
240 }
241 }
242
243 candidates
244 }
245
246 fn visit_well_formed_goal(
250 &mut self,
251 candidate: &inspect::InspectCandidate<'_, 'tcx>,
252 term: ty::Term<'tcx>,
253 ) -> ControlFlow<PredicateObligation<'tcx>> {
254 let infcx = candidate.goal().infcx();
255 let param_env = candidate.goal().goal().param_env;
256 let body_id = self.obligation.cause.body_id;
257
258 for obligation in wf::unnormalized_obligations(infcx, param_env, term, self.span(), body_id)
259 .into_iter()
260 .flatten()
261 {
262 let nested_goal = candidate.instantiate_proof_tree_for_nested_goal(
263 GoalSource::Misc,
264 obligation.as_goal(),
265 self.span(),
266 );
267 match (self.consider_ambiguities, nested_goal.result()) {
269 (true, Ok(Certainty::Maybe(MaybeCause::Ambiguity))) | (false, Err(_)) => {}
270 _ => continue,
271 }
272
273 self.with_derived_obligation(obligation, |this| nested_goal.visit_with(this))?;
274 }
275
276 ControlFlow::Break(self.obligation.clone())
277 }
278
279 fn detect_error_in_self_ty_normalization(
283 &mut self,
284 goal: &inspect::InspectGoal<'_, 'tcx>,
285 self_ty: Ty<'tcx>,
286 ) -> ControlFlow<PredicateObligation<'tcx>> {
287 assert!(!self.consider_ambiguities);
288 let tcx = goal.infcx().tcx;
289 if let ty::Alias(..) = self_ty.kind() {
290 let infer_term = goal.infcx().next_ty_var(self.obligation.cause.span);
291 let pred = ty::PredicateKind::AliasRelate(
292 self_ty.into(),
293 infer_term.into(),
294 ty::AliasRelationDirection::Equate,
295 );
296 let obligation =
297 Obligation::new(tcx, self.obligation.cause.clone(), goal.goal().param_env, pred);
298 self.with_derived_obligation(obligation, |this| {
299 goal.infcx().visit_proof_tree_at_depth(
300 goal.goal().with(tcx, pred),
301 goal.depth() + 1,
302 this,
303 )
304 })
305 } else {
306 ControlFlow::Continue(())
307 }
308 }
309
310 fn detect_trait_error_in_higher_ranked_projection(
318 &mut self,
319 goal: &inspect::InspectGoal<'_, 'tcx>,
320 ) -> ControlFlow<PredicateObligation<'tcx>> {
321 let tcx = goal.infcx().tcx;
322 if let Some(projection_clause) = goal.goal().predicate.as_projection_clause()
323 && !projection_clause.bound_vars().is_empty()
324 {
325 let pred = projection_clause.map_bound(|proj| proj.projection_term.trait_ref(tcx));
326 let obligation = Obligation::new(
327 tcx,
328 self.obligation.cause.clone(),
329 goal.goal().param_env,
330 deeply_normalize_for_diagnostics(goal.infcx(), goal.goal().param_env, pred),
331 );
332 self.with_derived_obligation(obligation, |this| {
333 goal.infcx().visit_proof_tree_at_depth(
334 goal.goal().with(tcx, pred),
335 goal.depth() + 1,
336 this,
337 )
338 })
339 } else {
340 ControlFlow::Continue(())
341 }
342 }
343
344 fn detect_non_well_formed_assoc_item(
351 &mut self,
352 goal: &inspect::InspectGoal<'_, 'tcx>,
353 alias: ty::AliasTerm<'tcx>,
354 ) -> ControlFlow<PredicateObligation<'tcx>> {
355 let tcx = goal.infcx().tcx;
356 let obligation = Obligation::new(
357 tcx,
358 self.obligation.cause.clone(),
359 goal.goal().param_env,
360 alias.trait_ref(tcx),
361 );
362 self.with_derived_obligation(obligation, |this| {
363 goal.infcx().visit_proof_tree_at_depth(
364 goal.goal().with(tcx, alias.trait_ref(tcx)),
365 goal.depth() + 1,
366 this,
367 )
368 })
369 }
370
371 fn detect_error_from_empty_candidates(
374 &mut self,
375 goal: &inspect::InspectGoal<'_, 'tcx>,
376 ) -> ControlFlow<PredicateObligation<'tcx>> {
377 let tcx = goal.infcx().tcx;
378 let pred_kind = goal.goal().predicate.kind();
379
380 match pred_kind.no_bound_vars() {
381 Some(ty::PredicateKind::Clause(ty::ClauseKind::Trait(pred))) => {
382 self.detect_error_in_self_ty_normalization(goal, pred.self_ty())?;
383 }
384 Some(ty::PredicateKind::NormalizesTo(pred))
385 if let ty::AliasTermKind::ProjectionTy | ty::AliasTermKind::ProjectionConst =
386 pred.alias.kind(tcx) =>
387 {
388 self.detect_error_in_self_ty_normalization(goal, pred.alias.self_ty())?;
389 self.detect_non_well_formed_assoc_item(goal, pred.alias)?;
390 }
391 Some(_) | None => {}
392 }
393
394 ControlFlow::Break(self.obligation.clone())
395 }
396}
397
398impl<'tcx> ProofTreeVisitor<'tcx> for BestObligation<'tcx> {
399 type Result = ControlFlow<PredicateObligation<'tcx>>;
400
401 fn span(&self) -> rustc_span::Span {
402 self.obligation.cause.span
403 }
404
405 #[instrument(level = "trace", skip(self, goal), fields(goal = ?goal.goal()))]
406 fn visit_goal(&mut self, goal: &inspect::InspectGoal<'_, 'tcx>) -> Self::Result {
407 let tcx = goal.infcx().tcx;
408 match (self.consider_ambiguities, goal.result()) {
410 (true, Ok(Certainty::Maybe(MaybeCause::Ambiguity))) | (false, Err(_)) => {}
411 _ => return ControlFlow::Continue(()),
412 }
413
414 let pred = goal.goal().predicate;
415
416 let candidates = self.non_trivial_candidates(goal);
417 let candidate = match candidates.as_slice() {
418 [candidate] => candidate,
419 [] => return self.detect_error_from_empty_candidates(goal),
420 _ => return ControlFlow::Break(self.obligation.clone()),
421 };
422
423 if let inspect::ProbeKind::TraitCandidate {
425 source: CandidateSource::Impl(impl_def_id),
426 result: _,
427 } = candidate.kind()
428 && tcx.do_not_recommend_impl(impl_def_id)
429 {
430 trace!("#[do_not_recommend] -> exit");
431 return ControlFlow::Break(self.obligation.clone());
432 }
433
434 let child_mode = match pred.kind().skip_binder() {
437 ty::PredicateKind::Clause(ty::ClauseKind::Trait(trait_pred)) => {
438 ChildMode::Trait(pred.kind().rebind(trait_pred))
439 }
440 ty::PredicateKind::Clause(ty::ClauseKind::HostEffect(host_pred)) => {
441 ChildMode::Host(pred.kind().rebind(host_pred))
442 }
443 ty::PredicateKind::NormalizesTo(normalizes_to)
444 if matches!(
445 normalizes_to.alias.kind(tcx),
446 ty::AliasTermKind::ProjectionTy | ty::AliasTermKind::ProjectionConst
447 ) =>
448 {
449 ChildMode::Trait(pred.kind().rebind(ty::TraitPredicate {
450 trait_ref: normalizes_to.alias.trait_ref(tcx),
451 polarity: ty::PredicatePolarity::Positive,
452 }))
453 }
454 ty::PredicateKind::Clause(ty::ClauseKind::WellFormed(term)) => {
455 return self.visit_well_formed_goal(candidate, term);
456 }
457 _ => ChildMode::PassThrough,
458 };
459
460 let nested_goals = candidate.instantiate_nested_goals(self.span());
461
462 for nested_goal in &nested_goals {
470 if let Some(poly_trait_pred) = nested_goal.goal().predicate.as_trait_clause()
471 && tcx.is_lang_item(poly_trait_pred.def_id(), LangItem::FnPtrTrait)
472 && let Err(NoSolution) = nested_goal.result()
473 {
474 return ControlFlow::Break(self.obligation.clone());
475 }
476 }
477
478 let mut impl_where_bound_count = 0;
479 for nested_goal in nested_goals {
480 trace!(nested_goal = ?(nested_goal.goal(), nested_goal.source(), nested_goal.result()));
481
482 let nested_pred = nested_goal.goal().predicate;
483
484 let make_obligation = |cause| Obligation {
485 cause,
486 param_env: nested_goal.goal().param_env,
487 predicate: nested_pred,
488 recursion_depth: self.obligation.recursion_depth + 1,
489 };
490
491 let obligation;
492 match (child_mode, nested_goal.source()) {
493 (
494 ChildMode::Trait(_) | ChildMode::Host(_),
495 GoalSource::Misc | GoalSource::TypeRelating | GoalSource::NormalizeGoal(_),
496 ) => {
497 continue;
498 }
499 (ChildMode::Trait(parent_trait_pred), GoalSource::ImplWhereBound) => {
500 obligation = make_obligation(derive_cause(
501 tcx,
502 candidate.kind(),
503 self.obligation.cause.clone(),
504 impl_where_bound_count,
505 parent_trait_pred,
506 ));
507 impl_where_bound_count += 1;
508 }
509 (
510 ChildMode::Host(parent_host_pred),
511 GoalSource::ImplWhereBound | GoalSource::AliasBoundConstCondition,
512 ) => {
513 obligation = make_obligation(derive_host_cause(
514 tcx,
515 candidate.kind(),
516 self.obligation.cause.clone(),
517 impl_where_bound_count,
518 parent_host_pred,
519 ));
520 impl_where_bound_count += 1;
521 }
522 (_, GoalSource::InstantiateHigherRanked) => {
524 obligation = self.obligation.clone();
525 }
526 (ChildMode::PassThrough, _)
527 | (_, GoalSource::AliasWellFormed | GoalSource::AliasBoundConstCondition) => {
528 obligation = make_obligation(self.obligation.cause.clone());
529 }
530 }
531
532 self.with_derived_obligation(obligation, |this| nested_goal.visit_with(this))?;
533 }
534
535 if let Some(ty::PredicateKind::AliasRelate(lhs, rhs, _)) = pred.kind().no_bound_vars() {
538 goal.infcx().visit_proof_tree_at_depth(
539 goal.goal().with(tcx, ty::ClauseKind::WellFormed(lhs.into())),
540 goal.depth() + 1,
541 self,
542 )?;
543 goal.infcx().visit_proof_tree_at_depth(
544 goal.goal().with(tcx, ty::ClauseKind::WellFormed(rhs.into())),
545 goal.depth() + 1,
546 self,
547 )?;
548 }
549
550 self.detect_trait_error_in_higher_ranked_projection(goal)?;
551
552 ControlFlow::Break(self.obligation.clone())
553 }
554}
555
556#[derive(Debug, Copy, Clone)]
557enum ChildMode<'tcx> {
558 Trait(ty::PolyTraitPredicate<'tcx>),
562 Host(ty::Binder<'tcx, ty::HostEffectPredicate<'tcx>>),
566 PassThrough,
570}
571
572fn derive_cause<'tcx>(
573 tcx: TyCtxt<'tcx>,
574 candidate_kind: inspect::ProbeKind<TyCtxt<'tcx>>,
575 mut cause: ObligationCause<'tcx>,
576 idx: usize,
577 parent_trait_pred: ty::PolyTraitPredicate<'tcx>,
578) -> ObligationCause<'tcx> {
579 match candidate_kind {
580 inspect::ProbeKind::TraitCandidate {
581 source: CandidateSource::Impl(impl_def_id),
582 result: _,
583 } => {
584 if let Some((_, span)) =
585 tcx.predicates_of(impl_def_id).instantiate_identity(tcx).iter().nth(idx)
586 {
587 cause = cause.derived_cause(parent_trait_pred, |derived| {
588 ObligationCauseCode::ImplDerived(Box::new(traits::ImplDerivedCause {
589 derived,
590 impl_or_alias_def_id: impl_def_id,
591 impl_def_predicate_index: Some(idx),
592 span,
593 }))
594 })
595 }
596 }
597 inspect::ProbeKind::TraitCandidate {
598 source: CandidateSource::BuiltinImpl(..),
599 result: _,
600 } => {
601 cause = cause.derived_cause(parent_trait_pred, ObligationCauseCode::BuiltinDerived);
602 }
603 _ => {}
604 };
605 cause
606}
607
608fn derive_host_cause<'tcx>(
609 tcx: TyCtxt<'tcx>,
610 candidate_kind: inspect::ProbeKind<TyCtxt<'tcx>>,
611 mut cause: ObligationCause<'tcx>,
612 idx: usize,
613 parent_host_pred: ty::Binder<'tcx, ty::HostEffectPredicate<'tcx>>,
614) -> ObligationCause<'tcx> {
615 match candidate_kind {
616 inspect::ProbeKind::TraitCandidate {
617 source: CandidateSource::Impl(impl_def_id),
618 result: _,
619 } => {
620 if let Some((_, span)) = tcx
621 .predicates_of(impl_def_id)
622 .instantiate_identity(tcx)
623 .into_iter()
624 .chain(tcx.const_conditions(impl_def_id).instantiate_identity(tcx).into_iter().map(
625 |(trait_ref, span)| {
626 (
627 trait_ref.to_host_effect_clause(
628 tcx,
629 parent_host_pred.skip_binder().constness,
630 ),
631 span,
632 )
633 },
634 ))
635 .nth(idx)
636 {
637 cause =
638 cause.derived_host_cause(parent_host_pred, |derived| {
639 ObligationCauseCode::ImplDerivedHost(Box::new(
640 traits::ImplDerivedHostCause { derived, impl_def_id, span },
641 ))
642 })
643 }
644 }
645 inspect::ProbeKind::TraitCandidate {
646 source: CandidateSource::BuiltinImpl(..),
647 result: _,
648 } => {
649 cause =
650 cause.derived_host_cause(parent_host_pred, ObligationCauseCode::BuiltinDerivedHost);
651 }
652 _ => {}
653 };
654 cause
655}