1use std::marker::PhantomData;
2
3use rustc_data_structures::obligation_forest::{
4 Error, ForestObligation, ObligationForest, ObligationProcessor, Outcome, ProcessResult,
5};
6use rustc_infer::infer::DefineOpaqueTypes;
7use rustc_infer::traits::{
8 FromSolverError, PolyTraitObligation, PredicateObligations, ProjectionCacheKey, SelectionError,
9 TraitEngine,
10};
11use rustc_middle::bug;
12use rustc_middle::ty::abstract_const::NotConstEvaluatable;
13use rustc_middle::ty::error::{ExpectedFound, TypeError};
14use rustc_middle::ty::{self, Binder, Const, GenericArgsRef, TypeVisitableExt, TypingMode};
15use thin_vec::ThinVec;
16use tracing::{debug, debug_span, instrument};
17
18use super::effects::{self, HostEffectObligation};
19use super::project::{self, ProjectAndUnifyResult};
20use super::select::SelectionContext;
21use super::{
22 EvaluationResult, FulfillmentError, FulfillmentErrorCode, PredicateObligation,
23 ScrubbedTraitError, Unimplemented, const_evaluatable, wf,
24};
25use crate::error_reporting::InferCtxtErrorExt;
26use crate::infer::{InferCtxt, TyOrConstInferVar};
27use crate::traits::EvaluateConstErr;
28use crate::traits::normalize::normalize_with_depth_to;
29use crate::traits::project::{PolyProjectionObligation, ProjectionCacheKeyExt as _};
30use crate::traits::query::evaluate_obligation::InferCtxtExt;
31
32pub(crate) type PendingPredicateObligations<'tcx> = ThinVec<PendingPredicateObligation<'tcx>>;
33
34impl<'tcx> ForestObligation for PendingPredicateObligation<'tcx> {
35 type CacheKey = ty::ParamEnvAnd<'tcx, ty::Predicate<'tcx>>;
39
40 fn as_cache_key(&self) -> Self::CacheKey {
41 self.obligation.param_env.and(self.obligation.predicate)
42 }
43}
44
45pub struct FulfillmentContext<'tcx, E: 'tcx> {
56 predicates: ObligationForest<PendingPredicateObligation<'tcx>>,
59
60 usable_in_snapshot: usize,
65
66 _errors: PhantomData<E>,
67}
68
69#[derive(Clone, Debug)]
70pub struct PendingPredicateObligation<'tcx> {
71 pub obligation: PredicateObligation<'tcx>,
72 pub stalled_on: Vec<TyOrConstInferVar>,
77}
78
79#[cfg(target_pointer_width = "64")]
81rustc_data_structures::static_assert_size!(PendingPredicateObligation<'_>, 72);
82
83impl<'tcx, E> FulfillmentContext<'tcx, E>
84where
85 E: FromSolverError<'tcx, OldSolverError<'tcx>>,
86{
87 pub(super) fn new(infcx: &InferCtxt<'tcx>) -> FulfillmentContext<'tcx, E> {
89 assert!(
90 !infcx.next_trait_solver(),
91 "old trait solver fulfillment context created when \
92 infcx is set up for new trait solver"
93 );
94 FulfillmentContext {
95 predicates: ObligationForest::new(),
96 usable_in_snapshot: infcx.num_open_snapshots(),
97 _errors: PhantomData,
98 }
99 }
100
101 fn select(&mut self, selcx: SelectionContext<'_, 'tcx>) -> Vec<E> {
103 let span = debug_span!("select", obligation_forest_size = ?self.predicates.len());
104 let _enter = span.enter();
105 let infcx = selcx.infcx;
106
107 let outcome: Outcome<_, _> =
109 self.predicates.process_obligations(&mut FulfillProcessor { selcx });
110
111 let errors: Vec<E> = outcome
115 .errors
116 .into_iter()
117 .map(|err| E::from_solver_error(infcx, OldSolverError(err)))
118 .collect();
119
120 debug!(
121 "select({} predicates remaining, {} errors) done",
122 self.predicates.len(),
123 errors.len()
124 );
125
126 errors
127 }
128}
129
130impl<'tcx, E> TraitEngine<'tcx, E> for FulfillmentContext<'tcx, E>
131where
132 E: FromSolverError<'tcx, OldSolverError<'tcx>>,
133{
134 #[inline]
135 fn register_predicate_obligation(
136 &mut self,
137 infcx: &InferCtxt<'tcx>,
138 mut obligation: PredicateObligation<'tcx>,
139 ) {
140 assert_eq!(self.usable_in_snapshot, infcx.num_open_snapshots());
141 debug_assert!(!obligation.param_env.has_non_region_infer());
144 obligation.predicate = infcx.resolve_vars_if_possible(obligation.predicate);
145
146 debug!(?obligation, "register_predicate_obligation");
147
148 self.predicates
149 .register_obligation(PendingPredicateObligation { obligation, stalled_on: vec![] });
150 }
151
152 fn collect_remaining_errors(&mut self, infcx: &InferCtxt<'tcx>) -> Vec<E> {
153 self.predicates
154 .to_errors(FulfillmentErrorCode::Ambiguity { overflow: None })
155 .into_iter()
156 .map(|err| E::from_solver_error(infcx, OldSolverError(err)))
157 .collect()
158 }
159
160 fn select_where_possible(&mut self, infcx: &InferCtxt<'tcx>) -> Vec<E> {
161 let selcx = SelectionContext::new(infcx);
162 self.select(selcx)
163 }
164
165 fn drain_unstalled_obligations(
166 &mut self,
167 infcx: &InferCtxt<'tcx>,
168 ) -> PredicateObligations<'tcx> {
169 let mut processor =
170 DrainProcessor { removed_predicates: PredicateObligations::new(), infcx };
171 let outcome: Outcome<_, _> = self.predicates.process_obligations(&mut processor);
172 assert!(outcome.errors.is_empty());
173 return processor.removed_predicates;
174
175 struct DrainProcessor<'a, 'tcx> {
176 infcx: &'a InferCtxt<'tcx>,
177 removed_predicates: PredicateObligations<'tcx>,
178 }
179
180 impl<'tcx> ObligationProcessor for DrainProcessor<'_, 'tcx> {
181 type Obligation = PendingPredicateObligation<'tcx>;
182 type Error = !;
183 type OUT = Outcome<Self::Obligation, Self::Error>;
184
185 fn needs_process_obligation(&self, pending_obligation: &Self::Obligation) -> bool {
186 pending_obligation
187 .stalled_on
188 .iter()
189 .any(|&var| self.infcx.ty_or_const_infer_var_changed(var))
190 }
191
192 fn process_obligation(
193 &mut self,
194 pending_obligation: &mut PendingPredicateObligation<'tcx>,
195 ) -> ProcessResult<PendingPredicateObligation<'tcx>, !> {
196 assert!(self.needs_process_obligation(pending_obligation));
197 self.removed_predicates.push(pending_obligation.obligation.clone());
198 ProcessResult::Changed(Default::default())
199 }
200
201 fn process_backedge<'c, I>(
202 &mut self,
203 cycle: I,
204 _marker: PhantomData<&'c PendingPredicateObligation<'tcx>>,
205 ) -> Result<(), !>
206 where
207 I: Clone + Iterator<Item = &'c PendingPredicateObligation<'tcx>>,
208 {
209 self.removed_predicates.extend(cycle.map(|c| c.obligation.clone()));
210 Ok(())
211 }
212 }
213 }
214
215 fn has_pending_obligations(&self) -> bool {
216 self.predicates.has_pending_obligations()
217 }
218
219 fn pending_obligations(&self) -> PredicateObligations<'tcx> {
220 self.predicates.map_pending_obligations(|o| o.obligation.clone())
221 }
222}
223
224struct FulfillProcessor<'a, 'tcx> {
225 selcx: SelectionContext<'a, 'tcx>,
226}
227
228fn mk_pending<'tcx>(os: PredicateObligations<'tcx>) -> PendingPredicateObligations<'tcx> {
229 os.into_iter()
230 .map(|o| PendingPredicateObligation { obligation: o, stalled_on: vec![] })
231 .collect()
232}
233
234impl<'a, 'tcx> ObligationProcessor for FulfillProcessor<'a, 'tcx> {
235 type Obligation = PendingPredicateObligation<'tcx>;
236 type Error = FulfillmentErrorCode<'tcx>;
237 type OUT = Outcome<Self::Obligation, Self::Error>;
238
239 #[inline]
249 fn skippable_obligations<'b>(
250 &'b self,
251 it: impl Iterator<Item = &'b Self::Obligation>,
252 ) -> usize {
253 let is_unchanged = self.selcx.infcx.is_ty_infer_var_definitely_unchanged();
254
255 it.take_while(|o| match o.stalled_on.as_slice() {
256 [o] => is_unchanged(*o),
257 _ => false,
258 })
259 .count()
260 }
261
262 #[inline(always)]
268 fn needs_process_obligation(&self, pending_obligation: &Self::Obligation) -> bool {
269 let stalled_on = &pending_obligation.stalled_on;
273 match stalled_on.len() {
274 1 => self.selcx.infcx.ty_or_const_infer_var_changed(stalled_on[0]),
278
279 0 => true,
287
288 _ => (|| {
295 for &infer_var in stalled_on {
296 if self.selcx.infcx.ty_or_const_infer_var_changed(infer_var) {
297 return true;
298 }
299 }
300 false
301 })(),
302 }
303 }
304
305 #[inline(never)]
313 #[instrument(level = "debug", skip(self, pending_obligation))]
314 fn process_obligation(
315 &mut self,
316 pending_obligation: &mut PendingPredicateObligation<'tcx>,
317 ) -> ProcessResult<PendingPredicateObligation<'tcx>, FulfillmentErrorCode<'tcx>> {
318 pending_obligation.stalled_on.truncate(0);
319
320 let obligation = &mut pending_obligation.obligation;
321
322 debug!(?obligation, "pre-resolve");
323
324 if obligation.predicate.has_non_region_infer() {
325 obligation.predicate = self.selcx.infcx.resolve_vars_if_possible(obligation.predicate);
326 }
327
328 let obligation = &pending_obligation.obligation;
329
330 let infcx = self.selcx.infcx;
331
332 if obligation.predicate.has_aliases() {
333 let mut obligations = PredicateObligations::new();
334 let predicate = normalize_with_depth_to(
335 &mut self.selcx,
336 obligation.param_env,
337 obligation.cause.clone(),
338 obligation.recursion_depth + 1,
339 obligation.predicate,
340 &mut obligations,
341 );
342 if predicate != obligation.predicate {
343 obligations.push(obligation.with(infcx.tcx, predicate));
344 return ProcessResult::Changed(mk_pending(obligations));
345 }
346 }
347 let binder = obligation.predicate.kind();
348 match binder.no_bound_vars() {
349 None => match binder.skip_binder() {
350 ty::PredicateKind::Clause(ty::ClauseKind::Trait(trait_ref)) => {
354 let trait_obligation = obligation.with(infcx.tcx, binder.rebind(trait_ref));
355
356 self.process_trait_obligation(
357 obligation,
358 trait_obligation,
359 &mut pending_obligation.stalled_on,
360 )
361 }
362 ty::PredicateKind::Clause(ty::ClauseKind::Projection(data)) => {
363 let project_obligation = obligation.with(infcx.tcx, binder.rebind(data));
364
365 self.process_projection_obligation(
366 obligation,
367 project_obligation,
368 &mut pending_obligation.stalled_on,
369 )
370 }
371 ty::PredicateKind::Clause(ty::ClauseKind::RegionOutlives(_))
372 | ty::PredicateKind::Clause(ty::ClauseKind::TypeOutlives(_))
373 | ty::PredicateKind::Clause(ty::ClauseKind::ConstArgHasType(..))
374 | ty::PredicateKind::Clause(ty::ClauseKind::WellFormed(_))
375 | ty::PredicateKind::DynCompatible(_)
376 | ty::PredicateKind::Subtype(_)
377 | ty::PredicateKind::Coerce(_)
378 | ty::PredicateKind::Clause(ty::ClauseKind::ConstEvaluatable(..))
379 | ty::PredicateKind::ConstEquate(..)
380 | ty::PredicateKind::Clause(ty::ClauseKind::HostEffect(..)) => {
384 let pred = ty::Binder::dummy(infcx.enter_forall_and_leak_universe(binder));
385 let mut obligations = PredicateObligations::with_capacity(1);
386 obligations.push(obligation.with(infcx.tcx, pred));
387
388 ProcessResult::Changed(mk_pending(obligations))
389 }
390 ty::PredicateKind::Ambiguous => ProcessResult::Unchanged,
391 ty::PredicateKind::NormalizesTo(..) => {
392 bug!("NormalizesTo is only used by the new solver")
393 }
394 ty::PredicateKind::AliasRelate(..) => {
395 bug!("AliasRelate is only used by the new solver")
396 }
397 },
398 Some(pred) => match pred {
399 ty::PredicateKind::Clause(ty::ClauseKind::Trait(data)) => {
400 let trait_obligation = obligation.with(infcx.tcx, Binder::dummy(data));
401
402 self.process_trait_obligation(
403 obligation,
404 trait_obligation,
405 &mut pending_obligation.stalled_on,
406 )
407 }
408
409 ty::PredicateKind::Clause(ty::ClauseKind::HostEffect(data)) => {
410 let host_obligation = obligation.with(infcx.tcx, data);
411
412 self.process_host_obligation(
413 host_obligation,
414 &mut pending_obligation.stalled_on,
415 )
416 }
417
418 ty::PredicateKind::Clause(ty::ClauseKind::RegionOutlives(data)) => {
419 if infcx.considering_regions {
420 infcx.region_outlives_predicate(&obligation.cause, Binder::dummy(data));
421 }
422
423 ProcessResult::Changed(Default::default())
424 }
425
426 ty::PredicateKind::Clause(ty::ClauseKind::TypeOutlives(ty::OutlivesPredicate(
427 t_a,
428 r_b,
429 ))) => {
430 if infcx.considering_regions {
431 infcx.register_region_obligation_with_cause(t_a, r_b, &obligation.cause);
432 }
433 ProcessResult::Changed(Default::default())
434 }
435
436 ty::PredicateKind::Clause(ty::ClauseKind::Projection(ref data)) => {
437 let project_obligation = obligation.with(infcx.tcx, Binder::dummy(*data));
438
439 self.process_projection_obligation(
440 obligation,
441 project_obligation,
442 &mut pending_obligation.stalled_on,
443 )
444 }
445
446 ty::PredicateKind::DynCompatible(trait_def_id) => {
447 if !self.selcx.tcx().is_dyn_compatible(trait_def_id) {
448 ProcessResult::Error(FulfillmentErrorCode::Select(Unimplemented))
449 } else {
450 ProcessResult::Changed(Default::default())
451 }
452 }
453
454 ty::PredicateKind::Ambiguous => ProcessResult::Unchanged,
455 ty::PredicateKind::NormalizesTo(..) => {
456 bug!("NormalizesTo is only used by the new solver")
457 }
458 ty::PredicateKind::AliasRelate(..) => {
459 bug!("AliasRelate is only used by the new solver")
460 }
461 ty::PredicateKind::Clause(ty::ClauseKind::ConstArgHasType(ct, ty)) => {
465 let ct = infcx.shallow_resolve_const(ct);
466 let ct_ty = match ct.kind() {
467 ty::ConstKind::Infer(var) => {
468 let var = match var {
469 ty::InferConst::Var(vid) => TyOrConstInferVar::Const(vid),
470 ty::InferConst::Fresh(_) => {
471 bug!("encountered fresh const in fulfill")
472 }
473 };
474 pending_obligation.stalled_on.clear();
475 pending_obligation.stalled_on.extend([var]);
476 return ProcessResult::Unchanged;
477 }
478 ty::ConstKind::Error(_) => {
479 return ProcessResult::Changed(PendingPredicateObligations::new());
480 }
481 ty::ConstKind::Value(cv) => cv.ty,
482 ty::ConstKind::Unevaluated(uv) => {
483 infcx.tcx.type_of(uv.def).instantiate(infcx.tcx, uv.args)
484 }
485 ty::ConstKind::Expr(_) => {
489 return ProcessResult::Changed(mk_pending(PredicateObligations::new()));
490 }
491 ty::ConstKind::Placeholder(_) => {
492 bug!("placeholder const {:?} in old solver", ct)
493 }
494 ty::ConstKind::Bound(_, _) => bug!("escaping bound vars in {:?}", ct),
495 ty::ConstKind::Param(param_ct) => {
496 param_ct.find_ty_from_env(obligation.param_env)
497 }
498 };
499
500 match infcx.at(&obligation.cause, obligation.param_env).eq(
501 DefineOpaqueTypes::Yes,
503 ct_ty,
504 ty,
505 ) {
506 Ok(inf_ok) => ProcessResult::Changed(mk_pending(inf_ok.into_obligations())),
507 Err(_) => ProcessResult::Error(FulfillmentErrorCode::Select(
508 SelectionError::ConstArgHasWrongType { ct, ct_ty, expected_ty: ty },
509 )),
510 }
511 }
512
513 _ if !self
518 .selcx
519 .tcx()
520 .recursion_limit()
521 .value_within_limit(obligation.recursion_depth) =>
522 {
523 self.selcx.infcx.err_ctxt().report_overflow_obligation(&obligation, false);
524 }
525
526 ty::PredicateKind::Clause(ty::ClauseKind::WellFormed(arg)) => {
527 match wf::obligations(
528 self.selcx.infcx,
529 obligation.param_env,
530 obligation.cause.body_id,
531 obligation.recursion_depth + 1,
532 arg,
533 obligation.cause.span,
534 ) {
535 None => {
536 pending_obligation.stalled_on =
537 vec![TyOrConstInferVar::maybe_from_generic_arg(arg).unwrap()];
538 ProcessResult::Unchanged
539 }
540 Some(os) => ProcessResult::Changed(mk_pending(os)),
541 }
542 }
543
544 ty::PredicateKind::Subtype(subtype) => {
545 match self.selcx.infcx.subtype_predicate(
546 &obligation.cause,
547 obligation.param_env,
548 Binder::dummy(subtype),
549 ) {
550 Err((a, b)) => {
551 pending_obligation.stalled_on =
553 vec![TyOrConstInferVar::Ty(a), TyOrConstInferVar::Ty(b)];
554 ProcessResult::Unchanged
555 }
556 Ok(Ok(mut ok)) => {
557 for subobligation in &mut ok.obligations {
558 subobligation.set_depth_from_parent(obligation.recursion_depth);
559 }
560 ProcessResult::Changed(mk_pending(ok.obligations))
561 }
562 Ok(Err(err)) => {
563 let expected_found = if subtype.a_is_expected {
564 ExpectedFound::new(subtype.a, subtype.b)
565 } else {
566 ExpectedFound::new(subtype.b, subtype.a)
567 };
568 ProcessResult::Error(FulfillmentErrorCode::Subtype(expected_found, err))
569 }
570 }
571 }
572
573 ty::PredicateKind::Coerce(coerce) => {
574 match self.selcx.infcx.coerce_predicate(
575 &obligation.cause,
576 obligation.param_env,
577 Binder::dummy(coerce),
578 ) {
579 Err((a, b)) => {
580 pending_obligation.stalled_on =
582 vec![TyOrConstInferVar::Ty(a), TyOrConstInferVar::Ty(b)];
583 ProcessResult::Unchanged
584 }
585 Ok(Ok(ok)) => ProcessResult::Changed(mk_pending(ok.obligations)),
586 Ok(Err(err)) => {
587 let expected_found = ExpectedFound::new(coerce.b, coerce.a);
588 ProcessResult::Error(FulfillmentErrorCode::Subtype(expected_found, err))
589 }
590 }
591 }
592
593 ty::PredicateKind::Clause(ty::ClauseKind::ConstEvaluatable(uv)) => {
594 match const_evaluatable::is_const_evaluatable(
595 self.selcx.infcx,
596 uv,
597 obligation.param_env,
598 obligation.cause.span,
599 ) {
600 Ok(()) => ProcessResult::Changed(Default::default()),
601 Err(NotConstEvaluatable::MentionsInfer) => {
602 pending_obligation.stalled_on.clear();
603 pending_obligation.stalled_on.extend(
604 uv.walk().filter_map(TyOrConstInferVar::maybe_from_generic_arg),
605 );
606 ProcessResult::Unchanged
607 }
608 Err(
609 e @ NotConstEvaluatable::MentionsParam
610 | e @ NotConstEvaluatable::Error(_),
611 ) => ProcessResult::Error(FulfillmentErrorCode::Select(
612 SelectionError::NotConstEvaluatable(e),
613 )),
614 }
615 }
616
617 ty::PredicateKind::ConstEquate(c1, c2) => {
618 let tcx = self.selcx.tcx();
619 assert!(
620 tcx.features().generic_const_exprs(),
621 "`ConstEquate` without a feature gate: {c1:?} {c2:?}",
622 );
623 {
628 let c1 = tcx.expand_abstract_consts(c1);
629 let c2 = tcx.expand_abstract_consts(c2);
630 debug!("equating consts:\nc1= {:?}\nc2= {:?}", c1, c2);
631
632 use rustc_hir::def::DefKind;
633 match (c1.kind(), c2.kind()) {
634 (ty::ConstKind::Unevaluated(a), ty::ConstKind::Unevaluated(b))
635 if a.def == b.def && tcx.def_kind(a.def) == DefKind::AssocConst =>
636 {
637 if let Ok(new_obligations) = infcx
638 .at(&obligation.cause, obligation.param_env)
639 .eq(
642 DefineOpaqueTypes::Yes,
643 ty::AliasTerm::from(a),
644 ty::AliasTerm::from(b),
645 )
646 {
647 return ProcessResult::Changed(mk_pending(
648 new_obligations.into_obligations(),
649 ));
650 }
651 }
652 (_, ty::ConstKind::Unevaluated(_))
653 | (ty::ConstKind::Unevaluated(_), _) => (),
654 (_, _) => {
655 if let Ok(new_obligations) = infcx
656 .at(&obligation.cause, obligation.param_env)
657 .eq(DefineOpaqueTypes::Yes, c1, c2)
660 {
661 return ProcessResult::Changed(mk_pending(
662 new_obligations.into_obligations(),
663 ));
664 }
665 }
666 }
667 }
668
669 let stalled_on = &mut pending_obligation.stalled_on;
670
671 let mut evaluate = |c: Const<'tcx>| {
672 if let ty::ConstKind::Unevaluated(unevaluated) = c.kind() {
673 match super::try_evaluate_const(
674 self.selcx.infcx,
675 c,
676 obligation.param_env,
677 ) {
678 Ok(val) => Ok(val),
679 e @ Err(EvaluateConstErr::HasGenericsOrInfers) => {
680 stalled_on.extend(
681 unevaluated
682 .args
683 .iter()
684 .filter_map(TyOrConstInferVar::maybe_from_generic_arg),
685 );
686 e
687 }
688 e @ Err(
689 EvaluateConstErr::EvaluationFailure(_)
690 | EvaluateConstErr::InvalidConstParamTy(_),
691 ) => e,
692 }
693 } else {
694 Ok(c)
695 }
696 };
697
698 match (evaluate(c1), evaluate(c2)) {
699 (Ok(c1), Ok(c2)) => {
700 match self.selcx.infcx.at(&obligation.cause, obligation.param_env).eq(
701 DefineOpaqueTypes::Yes,
704 c1,
705 c2,
706 ) {
707 Ok(inf_ok) => {
708 ProcessResult::Changed(mk_pending(inf_ok.into_obligations()))
709 }
710 Err(err) => {
711 ProcessResult::Error(FulfillmentErrorCode::ConstEquate(
712 ExpectedFound::new(c1, c2),
713 err,
714 ))
715 }
716 }
717 }
718 (Err(EvaluateConstErr::InvalidConstParamTy(e)), _)
719 | (_, Err(EvaluateConstErr::InvalidConstParamTy(e))) => {
720 ProcessResult::Error(FulfillmentErrorCode::Select(
721 SelectionError::NotConstEvaluatable(NotConstEvaluatable::Error(e)),
722 ))
723 }
724 (Err(EvaluateConstErr::EvaluationFailure(e)), _)
725 | (_, Err(EvaluateConstErr::EvaluationFailure(e))) => {
726 ProcessResult::Error(FulfillmentErrorCode::Select(
727 SelectionError::NotConstEvaluatable(NotConstEvaluatable::Error(e)),
728 ))
729 }
730 (Err(EvaluateConstErr::HasGenericsOrInfers), _)
731 | (_, Err(EvaluateConstErr::HasGenericsOrInfers)) => {
732 if c1.has_non_region_infer() || c2.has_non_region_infer() {
733 ProcessResult::Unchanged
734 } else {
735 let expected_found = ExpectedFound::new(c1, c2);
737 ProcessResult::Error(FulfillmentErrorCode::ConstEquate(
738 expected_found,
739 TypeError::ConstMismatch(expected_found),
740 ))
741 }
742 }
743 }
744 }
745 },
746 }
747 }
748
749 #[inline(never)]
750 fn process_backedge<'c, I>(
751 &mut self,
752 cycle: I,
753 _marker: PhantomData<&'c PendingPredicateObligation<'tcx>>,
754 ) -> Result<(), FulfillmentErrorCode<'tcx>>
755 where
756 I: Clone + Iterator<Item = &'c PendingPredicateObligation<'tcx>>,
757 {
758 if self.selcx.coinductive_match(cycle.clone().map(|s| s.obligation.predicate)) {
759 debug!("process_child_obligations: coinductive match");
760 Ok(())
761 } else {
762 let cycle = cycle.map(|c| c.obligation.clone()).collect();
763 Err(FulfillmentErrorCode::Cycle(cycle))
764 }
765 }
766}
767
768impl<'a, 'tcx> FulfillProcessor<'a, 'tcx> {
769 #[instrument(level = "debug", skip(self, obligation, stalled_on))]
770 fn process_trait_obligation(
771 &mut self,
772 obligation: &PredicateObligation<'tcx>,
773 trait_obligation: PolyTraitObligation<'tcx>,
774 stalled_on: &mut Vec<TyOrConstInferVar>,
775 ) -> ProcessResult<PendingPredicateObligation<'tcx>, FulfillmentErrorCode<'tcx>> {
776 let infcx = self.selcx.infcx;
777 if obligation.predicate.is_global() && !matches!(infcx.typing_mode(), TypingMode::Coherence)
778 {
779 if infcx.predicate_must_hold_considering_regions(obligation) {
782 debug!(
783 "selecting trait at depth {} evaluated to holds",
784 obligation.recursion_depth
785 );
786 return ProcessResult::Changed(Default::default());
787 }
788 }
789
790 match self.selcx.poly_select(&trait_obligation) {
791 Ok(Some(impl_source)) => {
792 debug!("selecting trait at depth {} yielded Ok(Some)", obligation.recursion_depth);
793 ProcessResult::Changed(mk_pending(impl_source.nested_obligations()))
794 }
795 Ok(None) => {
796 debug!("selecting trait at depth {} yielded Ok(None)", obligation.recursion_depth);
797
798 stalled_on.clear();
803 stalled_on.extend(args_infer_vars(
804 &self.selcx,
805 trait_obligation.predicate.map_bound(|pred| pred.trait_ref.args),
806 ));
807
808 debug!(
809 "process_predicate: pending obligation {:?} now stalled on {:?}",
810 infcx.resolve_vars_if_possible(obligation.clone()),
811 stalled_on
812 );
813
814 ProcessResult::Unchanged
815 }
816 Err(selection_err) => {
817 debug!("selecting trait at depth {} yielded Err", obligation.recursion_depth);
818
819 ProcessResult::Error(FulfillmentErrorCode::Select(selection_err))
820 }
821 }
822 }
823
824 fn process_projection_obligation(
825 &mut self,
826 obligation: &PredicateObligation<'tcx>,
827 project_obligation: PolyProjectionObligation<'tcx>,
828 stalled_on: &mut Vec<TyOrConstInferVar>,
829 ) -> ProcessResult<PendingPredicateObligation<'tcx>, FulfillmentErrorCode<'tcx>> {
830 let tcx = self.selcx.tcx();
831 let infcx = self.selcx.infcx;
832 if obligation.predicate.is_global() && !matches!(infcx.typing_mode(), TypingMode::Coherence)
833 {
834 if infcx.predicate_must_hold_considering_regions(obligation) {
837 if let Some(key) = ProjectionCacheKey::from_poly_projection_obligation(
838 &mut self.selcx,
839 &project_obligation,
840 ) {
841 infcx
845 .inner
846 .borrow_mut()
847 .projection_cache()
848 .complete(key, EvaluationResult::EvaluatedToOk);
849 }
850 return ProcessResult::Changed(Default::default());
851 } else {
852 debug!("Does NOT hold: {:?}", obligation);
853 }
854 }
855
856 match project::poly_project_and_unify_term(&mut self.selcx, &project_obligation) {
857 ProjectAndUnifyResult::Holds(os) => ProcessResult::Changed(mk_pending(os)),
858 ProjectAndUnifyResult::FailedNormalization => {
859 stalled_on.clear();
860 stalled_on.extend(args_infer_vars(
861 &self.selcx,
862 project_obligation.predicate.map_bound(|pred| pred.projection_term.args),
863 ));
864 ProcessResult::Unchanged
865 }
866 ProjectAndUnifyResult::Recursive => {
868 let mut obligations = PredicateObligations::with_capacity(1);
869 obligations.push(project_obligation.with(tcx, project_obligation.predicate));
870
871 ProcessResult::Changed(mk_pending(obligations))
872 }
873 ProjectAndUnifyResult::MismatchedProjectionTypes(e) => {
874 ProcessResult::Error(FulfillmentErrorCode::Project(e))
875 }
876 }
877 }
878
879 fn process_host_obligation(
880 &mut self,
881 host_obligation: HostEffectObligation<'tcx>,
882 stalled_on: &mut Vec<TyOrConstInferVar>,
883 ) -> ProcessResult<PendingPredicateObligation<'tcx>, FulfillmentErrorCode<'tcx>> {
884 match effects::evaluate_host_effect_obligation(&mut self.selcx, &host_obligation) {
885 Ok(nested) => ProcessResult::Changed(mk_pending(nested)),
886 Err(effects::EvaluationFailure::Ambiguous) => {
887 stalled_on.clear();
888 stalled_on.extend(args_infer_vars(
889 &self.selcx,
890 ty::Binder::dummy(host_obligation.predicate.trait_ref.args),
891 ));
892 ProcessResult::Unchanged
893 }
894 Err(effects::EvaluationFailure::NoSolution) => {
895 ProcessResult::Error(FulfillmentErrorCode::Select(SelectionError::Unimplemented))
896 }
897 }
898 }
899}
900
901fn args_infer_vars<'tcx>(
903 selcx: &SelectionContext<'_, 'tcx>,
904 args: ty::Binder<'tcx, GenericArgsRef<'tcx>>,
905) -> impl Iterator<Item = TyOrConstInferVar> {
906 selcx
907 .infcx
908 .resolve_vars_if_possible(args)
909 .skip_binder() .iter()
911 .filter(|arg| arg.has_non_region_infer())
912 .flat_map(|arg| {
913 let mut walker = arg.walk();
914 while let Some(c) = walker.next() {
915 if !c.has_non_region_infer() {
916 walker.visited.remove(&c);
917 walker.skip_current_subtree();
918 }
919 }
920 walker.visited.into_iter()
921 })
922 .filter_map(TyOrConstInferVar::maybe_from_generic_arg)
923}
924
925#[derive(Debug)]
926pub struct OldSolverError<'tcx>(
927 Error<PendingPredicateObligation<'tcx>, FulfillmentErrorCode<'tcx>>,
928);
929
930impl<'tcx> FromSolverError<'tcx, OldSolverError<'tcx>> for FulfillmentError<'tcx> {
931 fn from_solver_error(_infcx: &InferCtxt<'tcx>, error: OldSolverError<'tcx>) -> Self {
932 let mut iter = error.0.backtrace.into_iter();
933 let obligation = iter.next().unwrap().obligation;
934 let root_obligation = iter.next_back().map_or_else(|| obligation.clone(), |e| e.obligation);
937 FulfillmentError::new(obligation, error.0.error, root_obligation)
938 }
939}
940
941impl<'tcx> FromSolverError<'tcx, OldSolverError<'tcx>> for ScrubbedTraitError<'tcx> {
942 fn from_solver_error(_infcx: &InferCtxt<'tcx>, error: OldSolverError<'tcx>) -> Self {
943 match error.0.error {
944 FulfillmentErrorCode::Select(_)
945 | FulfillmentErrorCode::Project(_)
946 | FulfillmentErrorCode::Subtype(_, _)
947 | FulfillmentErrorCode::ConstEquate(_, _) => ScrubbedTraitError::TrueError,
948 FulfillmentErrorCode::Ambiguity { overflow: _ } => ScrubbedTraitError::Ambiguity,
949 FulfillmentErrorCode::Cycle(cycle) => ScrubbedTraitError::Cycle(cycle),
950 }
951 }
952}