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