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