rustc_trait_selection/traits/
fulfill.rs

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, thin_vec};
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, const_evaluatable, wf,
24};
25use crate::error_reporting::InferCtxtErrorExt;
26use crate::infer::{InferCtxt, TyOrConstInferVar};
27use crate::traits::normalize::normalize_with_depth_to;
28use crate::traits::project::{PolyProjectionObligation, ProjectionCacheKeyExt as _};
29use crate::traits::query::evaluate_obligation::InferCtxtExt;
30use crate::traits::{EvaluateConstErr, sizedness_fast_path};
31
32pub(crate) type PendingPredicateObligations<'tcx> = ThinVec<PendingPredicateObligation<'tcx>>;
33
34impl<'tcx> ForestObligation for PendingPredicateObligation<'tcx> {
35    /// Note that we include both the `ParamEnv` and the `Predicate`,
36    /// as the `ParamEnv` can influence whether fulfillment succeeds
37    /// or fails.
38    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
45/// The fulfillment context is used to drive trait resolution. It
46/// consists of a list of obligations that must be (eventually)
47/// satisfied. The job is to track which are satisfied, which yielded
48/// errors, and which are still pending. At any point, users can call
49/// `select_where_possible`, and the fulfillment context will try to do
50/// selection, retaining only those obligations that remain
51/// ambiguous. This may be helpful in pushing type inference
52/// along. Once all type inference constraints have been generated, the
53/// method `select_all_or_error` can be used to report any remaining
54/// ambiguous cases as errors.
55pub struct FulfillmentContext<'tcx, E: 'tcx> {
56    /// A list of all obligations that have been registered with this
57    /// fulfillment context.
58    predicates: ObligationForest<PendingPredicateObligation<'tcx>>,
59
60    /// The snapshot in which this context was created. Using the context
61    /// outside of this snapshot leads to subtle bugs if the snapshot
62    /// gets rolled back. Because of this we explicitly check that we only
63    /// use the context in exactly this snapshot.
64    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    // This is far more often read than modified, meaning that we
73    // should mostly optimize for reading speed, while modifying is not as relevant.
74    //
75    // For whatever reason using a boxed slice is slower than using a `Vec` here.
76    pub stalled_on: Vec<TyOrConstInferVar>,
77}
78
79// `PendingPredicateObligation` is used a lot. Make sure it doesn't unintentionally get bigger.
80#[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    /// Creates a new fulfillment context.
88    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    /// Attempts to select obligations using `selcx`.
102    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        // Process pending obligations.
108        let outcome: Outcome<_, _> =
109            self.predicates.process_obligations(&mut FulfillProcessor { selcx });
110
111        // FIXME: if we kept the original cache key, we could mark projection
112        // obligations as complete for the projection cache here.
113
114        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        // this helps to reduce duplicate errors, as well as making
142        // debug output much nicer to read and so on.
143        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_stalled_obligations_for_coroutines(
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>(
229    parent: &PredicateObligation<'tcx>,
230    os: PredicateObligations<'tcx>,
231) -> PendingPredicateObligations<'tcx> {
232    os.into_iter()
233        .map(|mut o| {
234            o.set_depth_from_parent(parent.recursion_depth);
235            PendingPredicateObligation { obligation: o, stalled_on: vec![] }
236        })
237        .collect()
238}
239
240impl<'a, 'tcx> ObligationProcessor for FulfillProcessor<'a, 'tcx> {
241    type Obligation = PendingPredicateObligation<'tcx>;
242    type Error = FulfillmentErrorCode<'tcx>;
243    type OUT = Outcome<Self::Obligation, Self::Error>;
244
245    /// Compared to `needs_process_obligation` this and its callees
246    /// contain some optimizations that come at the price of false negatives.
247    ///
248    /// They
249    /// - reduce branching by covering only the most common case
250    /// - take a read-only view of the unification tables which allows skipping undo_log
251    ///   construction.
252    /// - bail out on value-cache misses in ena to avoid pointer chasing
253    /// - hoist RefCell locking out of the loop
254    #[inline]
255    fn skippable_obligations<'b>(
256        &'b self,
257        it: impl Iterator<Item = &'b Self::Obligation>,
258    ) -> usize {
259        let is_unchanged = self.selcx.infcx.is_ty_infer_var_definitely_unchanged();
260
261        it.take_while(|o| match o.stalled_on.as_slice() {
262            [o] => is_unchanged(*o),
263            _ => false,
264        })
265        .count()
266    }
267
268    /// Identifies whether a predicate obligation needs processing.
269    ///
270    /// This is always inlined because it has a single callsite and it is
271    /// called *very* frequently. Be careful modifying this code! Several
272    /// compile-time benchmarks are very sensitive to even small changes.
273    #[inline(always)]
274    fn needs_process_obligation(&self, pending_obligation: &Self::Obligation) -> bool {
275        // If we were stalled on some unresolved variables, first check whether
276        // any of them have been resolved; if not, don't bother doing more work
277        // yet.
278        let stalled_on = &pending_obligation.stalled_on;
279        match stalled_on.len() {
280            // This case is the hottest most of the time, being hit up to 99%
281            // of the time. `keccak` and `cranelift-codegen-0.82.1` are
282            // benchmarks that particularly stress this path.
283            1 => self.selcx.infcx.ty_or_const_infer_var_changed(stalled_on[0]),
284
285            // In this case we haven't changed, but wish to make a change. Note
286            // that this is a special case, and is not equivalent to the `_`
287            // case below, which would return `false` for an empty `stalled_on`
288            // vector.
289            //
290            // This case is usually hit only 1% of the time or less, though it
291            // reaches 20% in `wasmparser-0.101.0`.
292            0 => true,
293
294            // This case is usually hit only 1% of the time or less, though it
295            // reaches 95% in `mime-0.3.16`, 64% in `wast-54.0.0`, and 12% in
296            // `inflate-0.4.5`.
297            //
298            // The obvious way of writing this, with a call to `any()` and no
299            // closure, is currently slower than this version.
300            _ => (|| {
301                for &infer_var in stalled_on {
302                    if self.selcx.infcx.ty_or_const_infer_var_changed(infer_var) {
303                        return true;
304                    }
305                }
306                false
307            })(),
308        }
309    }
310
311    /// Processes a predicate obligation and returns either:
312    /// - `Changed(v)` if the predicate is true, presuming that `v` are also true
313    /// - `Unchanged` if we don't have enough info to be sure
314    /// - `Error(e)` if the predicate does not hold
315    ///
316    /// This is called much less often than `needs_process_obligation`, so we
317    /// never inline it.
318    #[inline(never)]
319    #[instrument(level = "debug", skip(self, pending_obligation))]
320    fn process_obligation(
321        &mut self,
322        pending_obligation: &mut PendingPredicateObligation<'tcx>,
323    ) -> ProcessResult<PendingPredicateObligation<'tcx>, FulfillmentErrorCode<'tcx>> {
324        pending_obligation.stalled_on.truncate(0);
325
326        let obligation = &mut pending_obligation.obligation;
327
328        debug!(?obligation, "pre-resolve");
329
330        if obligation.predicate.has_non_region_infer() {
331            obligation.predicate = self.selcx.infcx.resolve_vars_if_possible(obligation.predicate);
332        }
333
334        let obligation = &pending_obligation.obligation;
335
336        let infcx = self.selcx.infcx;
337
338        if sizedness_fast_path(infcx.tcx, obligation.predicate) {
339            return ProcessResult::Changed(thin_vec![]);
340        }
341
342        if obligation.predicate.has_aliases() {
343            let mut obligations = PredicateObligations::new();
344            let predicate = normalize_with_depth_to(
345                &mut self.selcx,
346                obligation.param_env,
347                obligation.cause.clone(),
348                obligation.recursion_depth + 1,
349                obligation.predicate,
350                &mut obligations,
351            );
352            if predicate != obligation.predicate {
353                obligations.push(obligation.with(infcx.tcx, predicate));
354                return ProcessResult::Changed(mk_pending(obligation, obligations));
355            }
356        }
357        let binder = obligation.predicate.kind();
358        match binder.no_bound_vars() {
359            None => match binder.skip_binder() {
360                // Evaluation will discard candidates using the leak check.
361                // This means we need to pass it the bound version of our
362                // predicate.
363                ty::PredicateKind::Clause(ty::ClauseKind::Trait(trait_ref)) => {
364                    let trait_obligation = obligation.with(infcx.tcx, binder.rebind(trait_ref));
365
366                    self.process_trait_obligation(
367                        obligation,
368                        trait_obligation,
369                        &mut pending_obligation.stalled_on,
370                    )
371                }
372                ty::PredicateKind::Clause(ty::ClauseKind::Projection(data)) => {
373                    let project_obligation = obligation.with(infcx.tcx, binder.rebind(data));
374
375                    self.process_projection_obligation(
376                        obligation,
377                        project_obligation,
378                        &mut pending_obligation.stalled_on,
379                    )
380                }
381                ty::PredicateKind::Clause(ty::ClauseKind::RegionOutlives(_))
382                | ty::PredicateKind::Clause(ty::ClauseKind::TypeOutlives(_))
383                | ty::PredicateKind::Clause(ty::ClauseKind::ConstArgHasType(..))
384                | ty::PredicateKind::Clause(ty::ClauseKind::WellFormed(_))
385                | ty::PredicateKind::DynCompatible(_)
386                | ty::PredicateKind::Subtype(_)
387                | ty::PredicateKind::Coerce(_)
388                | ty::PredicateKind::Clause(ty::ClauseKind::ConstEvaluatable(..))
389                | ty::PredicateKind::ConstEquate(..)
390                // FIXME(const_trait_impl): We may need to do this using the higher-ranked
391                // pred instead of just instantiating it with placeholders b/c of
392                // higher-ranked implied bound issues in the old solver.
393                | ty::PredicateKind::Clause(ty::ClauseKind::HostEffect(..)) => {
394                    let pred = ty::Binder::dummy(infcx.enter_forall_and_leak_universe(binder));
395                    let mut obligations = PredicateObligations::with_capacity(1);
396                    obligations.push(obligation.with(infcx.tcx, pred));
397
398                    ProcessResult::Changed(mk_pending(obligation, obligations))
399                }
400                ty::PredicateKind::Ambiguous => ProcessResult::Unchanged,
401                ty::PredicateKind::NormalizesTo(..) => {
402                    bug!("NormalizesTo is only used by the new solver")
403                }
404                ty::PredicateKind::AliasRelate(..) => {
405                    bug!("AliasRelate is only used by the new solver")
406                }
407            },
408            Some(pred) => match pred {
409                ty::PredicateKind::Clause(ty::ClauseKind::Trait(data)) => {
410                    let trait_obligation = obligation.with(infcx.tcx, Binder::dummy(data));
411
412                    self.process_trait_obligation(
413                        obligation,
414                        trait_obligation,
415                        &mut pending_obligation.stalled_on,
416                    )
417                }
418
419                ty::PredicateKind::Clause(ty::ClauseKind::HostEffect(data)) => {
420                    let host_obligation = obligation.with(infcx.tcx, data);
421
422                    self.process_host_obligation(
423                        obligation,
424                        host_obligation,
425                        &mut pending_obligation.stalled_on,
426                    )
427                }
428
429                ty::PredicateKind::Clause(ty::ClauseKind::RegionOutlives(data)) => {
430                    if infcx.considering_regions {
431                        infcx.register_region_outlives_constraint(data, &obligation.cause);
432                    }
433
434                    ProcessResult::Changed(Default::default())
435                }
436
437                ty::PredicateKind::Clause(ty::ClauseKind::TypeOutlives(ty::OutlivesPredicate(
438                    t_a,
439                    r_b,
440                ))) => {
441                    if infcx.considering_regions {
442                        infcx.register_type_outlives_constraint(t_a, r_b, &obligation.cause);
443                    }
444                    ProcessResult::Changed(Default::default())
445                }
446
447                ty::PredicateKind::Clause(ty::ClauseKind::Projection(ref data)) => {
448                    let project_obligation = obligation.with(infcx.tcx, Binder::dummy(*data));
449
450                    self.process_projection_obligation(
451                        obligation,
452                        project_obligation,
453                        &mut pending_obligation.stalled_on,
454                    )
455                }
456
457                ty::PredicateKind::DynCompatible(trait_def_id) => {
458                    if !self.selcx.tcx().is_dyn_compatible(trait_def_id) {
459                        ProcessResult::Error(FulfillmentErrorCode::Select(
460                            SelectionError::Unimplemented,
461                        ))
462                    } else {
463                        ProcessResult::Changed(Default::default())
464                    }
465                }
466
467                ty::PredicateKind::Ambiguous => ProcessResult::Unchanged,
468                ty::PredicateKind::NormalizesTo(..) => {
469                    bug!("NormalizesTo is only used by the new solver")
470                }
471                ty::PredicateKind::AliasRelate(..) => {
472                    bug!("AliasRelate is only used by the new solver")
473                }
474                // Compute `ConstArgHasType` above the overflow check below.
475                // This is because this is not ever a useful obligation to report
476                // as the cause of an overflow.
477                ty::PredicateKind::Clause(ty::ClauseKind::ConstArgHasType(ct, ty)) => {
478                    let ct = infcx.shallow_resolve_const(ct);
479                    let ct_ty = match ct.kind() {
480                        ty::ConstKind::Infer(var) => {
481                            let var = match var {
482                                ty::InferConst::Var(vid) => TyOrConstInferVar::Const(vid),
483                                ty::InferConst::Fresh(_) => {
484                                    bug!("encountered fresh const in fulfill")
485                                }
486                            };
487                            pending_obligation.stalled_on.clear();
488                            pending_obligation.stalled_on.extend([var]);
489                            return ProcessResult::Unchanged;
490                        }
491                        ty::ConstKind::Error(_) => {
492                            return ProcessResult::Changed(PendingPredicateObligations::new());
493                        }
494                        ty::ConstKind::Value(cv) => cv.ty,
495                        ty::ConstKind::Unevaluated(uv) => {
496                            infcx.tcx.type_of(uv.def).instantiate(infcx.tcx, uv.args)
497                        }
498                        // FIXME(generic_const_exprs): we should construct an alias like
499                        // `<lhs_ty as Add<rhs_ty>>::Output` when this is an `Expr` representing
500                        // `lhs + rhs`.
501                        ty::ConstKind::Expr(_) => {
502                            return ProcessResult::Changed(mk_pending(
503                                obligation,
504                                PredicateObligations::new(),
505                            ));
506                        }
507                        ty::ConstKind::Placeholder(_) => {
508                            bug!("placeholder const {:?} in old solver", ct)
509                        }
510                        ty::ConstKind::Bound(_, _) => bug!("escaping bound vars in {:?}", ct),
511                        ty::ConstKind::Param(param_ct) => {
512                            param_ct.find_const_ty_from_env(obligation.param_env)
513                        }
514                    };
515
516                    match infcx.at(&obligation.cause, obligation.param_env).eq(
517                        // Only really exercised by generic_const_exprs
518                        DefineOpaqueTypes::Yes,
519                        ct_ty,
520                        ty,
521                    ) {
522                        Ok(inf_ok) => ProcessResult::Changed(mk_pending(
523                            obligation,
524                            inf_ok.into_obligations(),
525                        )),
526                        Err(_) => ProcessResult::Error(FulfillmentErrorCode::Select(
527                            SelectionError::ConstArgHasWrongType { ct, ct_ty, expected_ty: ty },
528                        )),
529                    }
530                }
531
532                // General case overflow check. Allow `process_trait_obligation`
533                // and `process_projection_obligation` to handle checking for
534                // the recursion limit themselves. Also don't check some
535                // predicate kinds that don't give further obligations.
536                _ if !self
537                    .selcx
538                    .tcx()
539                    .recursion_limit()
540                    .value_within_limit(obligation.recursion_depth) =>
541                {
542                    self.selcx.infcx.err_ctxt().report_overflow_obligation(&obligation, false);
543                }
544
545                ty::PredicateKind::Clause(ty::ClauseKind::WellFormed(term)) => {
546                    if term.is_trivially_wf(self.selcx.tcx()) {
547                        return ProcessResult::Changed(thin_vec![]);
548                    }
549
550                    match wf::obligations(
551                        self.selcx.infcx,
552                        obligation.param_env,
553                        obligation.cause.body_id,
554                        obligation.recursion_depth + 1,
555                        term,
556                        obligation.cause.span,
557                    ) {
558                        None => {
559                            pending_obligation.stalled_on =
560                                vec![TyOrConstInferVar::maybe_from_term(term).unwrap()];
561                            ProcessResult::Unchanged
562                        }
563                        Some(os) => ProcessResult::Changed(mk_pending(obligation, os)),
564                    }
565                }
566
567                ty::PredicateKind::Subtype(subtype) => {
568                    match self.selcx.infcx.subtype_predicate(
569                        &obligation.cause,
570                        obligation.param_env,
571                        Binder::dummy(subtype),
572                    ) {
573                        Err((a, b)) => {
574                            // None means that both are unresolved.
575                            pending_obligation.stalled_on =
576                                vec![TyOrConstInferVar::Ty(a), TyOrConstInferVar::Ty(b)];
577                            ProcessResult::Unchanged
578                        }
579                        Ok(Ok(ok)) => {
580                            ProcessResult::Changed(mk_pending(obligation, ok.obligations))
581                        }
582                        Ok(Err(err)) => {
583                            let expected_found = if subtype.a_is_expected {
584                                ExpectedFound::new(subtype.a, subtype.b)
585                            } else {
586                                ExpectedFound::new(subtype.b, subtype.a)
587                            };
588                            ProcessResult::Error(FulfillmentErrorCode::Subtype(expected_found, err))
589                        }
590                    }
591                }
592
593                ty::PredicateKind::Coerce(coerce) => {
594                    match self.selcx.infcx.coerce_predicate(
595                        &obligation.cause,
596                        obligation.param_env,
597                        Binder::dummy(coerce),
598                    ) {
599                        Err((a, b)) => {
600                            // None means that both are unresolved.
601                            pending_obligation.stalled_on =
602                                vec![TyOrConstInferVar::Ty(a), TyOrConstInferVar::Ty(b)];
603                            ProcessResult::Unchanged
604                        }
605                        Ok(Ok(ok)) => {
606                            ProcessResult::Changed(mk_pending(obligation, ok.obligations))
607                        }
608                        Ok(Err(err)) => {
609                            let expected_found = ExpectedFound::new(coerce.b, coerce.a);
610                            ProcessResult::Error(FulfillmentErrorCode::Subtype(expected_found, err))
611                        }
612                    }
613                }
614
615                ty::PredicateKind::Clause(ty::ClauseKind::ConstEvaluatable(uv)) => {
616                    match const_evaluatable::is_const_evaluatable(
617                        self.selcx.infcx,
618                        uv,
619                        obligation.param_env,
620                        obligation.cause.span,
621                    ) {
622                        Ok(()) => ProcessResult::Changed(Default::default()),
623                        Err(NotConstEvaluatable::MentionsInfer) => {
624                            pending_obligation.stalled_on.clear();
625                            pending_obligation.stalled_on.extend(
626                                uv.walk().filter_map(TyOrConstInferVar::maybe_from_generic_arg),
627                            );
628                            ProcessResult::Unchanged
629                        }
630                        Err(
631                            e @ NotConstEvaluatable::MentionsParam
632                            | e @ NotConstEvaluatable::Error(_),
633                        ) => ProcessResult::Error(FulfillmentErrorCode::Select(
634                            SelectionError::NotConstEvaluatable(e),
635                        )),
636                    }
637                }
638
639                ty::PredicateKind::ConstEquate(c1, c2) => {
640                    let tcx = self.selcx.tcx();
641                    assert!(
642                        tcx.features().generic_const_exprs(),
643                        "`ConstEquate` without a feature gate: {c1:?} {c2:?}",
644                    );
645                    // FIXME: we probably should only try to unify abstract constants
646                    // if the constants depend on generic parameters.
647                    //
648                    // Let's just see where this breaks :shrug:
649                    {
650                        let c1 = tcx.expand_abstract_consts(c1);
651                        let c2 = tcx.expand_abstract_consts(c2);
652                        debug!("equating consts:\nc1= {:?}\nc2= {:?}", c1, c2);
653
654                        use rustc_hir::def::DefKind;
655                        match (c1.kind(), c2.kind()) {
656                            (ty::ConstKind::Unevaluated(a), ty::ConstKind::Unevaluated(b))
657                                if a.def == b.def && tcx.def_kind(a.def) == DefKind::AssocConst =>
658                            {
659                                if let Ok(new_obligations) = infcx
660                                    .at(&obligation.cause, obligation.param_env)
661                                    // Can define opaque types as this is only reachable with
662                                    // `generic_const_exprs`
663                                    .eq(
664                                        DefineOpaqueTypes::Yes,
665                                        ty::AliasTerm::from(a),
666                                        ty::AliasTerm::from(b),
667                                    )
668                                {
669                                    return ProcessResult::Changed(mk_pending(
670                                        obligation,
671                                        new_obligations.into_obligations(),
672                                    ));
673                                }
674                            }
675                            (_, ty::ConstKind::Unevaluated(_))
676                            | (ty::ConstKind::Unevaluated(_), _) => (),
677                            (_, _) => {
678                                if let Ok(new_obligations) = infcx
679                                    .at(&obligation.cause, obligation.param_env)
680                                    // Can define opaque types as this is only reachable with
681                                    // `generic_const_exprs`
682                                    .eq(DefineOpaqueTypes::Yes, c1, c2)
683                                {
684                                    return ProcessResult::Changed(mk_pending(
685                                        obligation,
686                                        new_obligations.into_obligations(),
687                                    ));
688                                }
689                            }
690                        }
691                    }
692
693                    let stalled_on = &mut pending_obligation.stalled_on;
694
695                    let mut evaluate = |c: Const<'tcx>| {
696                        if let ty::ConstKind::Unevaluated(unevaluated) = c.kind() {
697                            match super::try_evaluate_const(
698                                self.selcx.infcx,
699                                c,
700                                obligation.param_env,
701                            ) {
702                                Ok(val) => Ok(val),
703                                e @ Err(EvaluateConstErr::HasGenericsOrInfers) => {
704                                    stalled_on.extend(
705                                        unevaluated
706                                            .args
707                                            .iter()
708                                            .filter_map(TyOrConstInferVar::maybe_from_generic_arg),
709                                    );
710                                    e
711                                }
712                                e @ Err(
713                                    EvaluateConstErr::EvaluationFailure(_)
714                                    | EvaluateConstErr::InvalidConstParamTy(_),
715                                ) => e,
716                            }
717                        } else {
718                            Ok(c)
719                        }
720                    };
721
722                    match (evaluate(c1), evaluate(c2)) {
723                        (Ok(c1), Ok(c2)) => {
724                            match self.selcx.infcx.at(&obligation.cause, obligation.param_env).eq(
725                                // Can define opaque types as this is only reachable with
726                                // `generic_const_exprs`
727                                DefineOpaqueTypes::Yes,
728                                c1,
729                                c2,
730                            ) {
731                                Ok(inf_ok) => ProcessResult::Changed(mk_pending(
732                                    obligation,
733                                    inf_ok.into_obligations(),
734                                )),
735                                Err(err) => {
736                                    ProcessResult::Error(FulfillmentErrorCode::ConstEquate(
737                                        ExpectedFound::new(c1, c2),
738                                        err,
739                                    ))
740                                }
741                            }
742                        }
743                        (Err(EvaluateConstErr::InvalidConstParamTy(e)), _)
744                        | (_, Err(EvaluateConstErr::InvalidConstParamTy(e))) => {
745                            ProcessResult::Error(FulfillmentErrorCode::Select(
746                                SelectionError::NotConstEvaluatable(NotConstEvaluatable::Error(e)),
747                            ))
748                        }
749                        (Err(EvaluateConstErr::EvaluationFailure(e)), _)
750                        | (_, Err(EvaluateConstErr::EvaluationFailure(e))) => {
751                            ProcessResult::Error(FulfillmentErrorCode::Select(
752                                SelectionError::NotConstEvaluatable(NotConstEvaluatable::Error(e)),
753                            ))
754                        }
755                        (Err(EvaluateConstErr::HasGenericsOrInfers), _)
756                        | (_, Err(EvaluateConstErr::HasGenericsOrInfers)) => {
757                            if c1.has_non_region_infer() || c2.has_non_region_infer() {
758                                ProcessResult::Unchanged
759                            } else {
760                                // Two different constants using generic parameters ~> error.
761                                let expected_found = ExpectedFound::new(c1, c2);
762                                ProcessResult::Error(FulfillmentErrorCode::ConstEquate(
763                                    expected_found,
764                                    TypeError::ConstMismatch(expected_found),
765                                ))
766                            }
767                        }
768                    }
769                }
770            },
771        }
772    }
773
774    #[inline(never)]
775    fn process_backedge<'c, I>(
776        &mut self,
777        cycle: I,
778        _marker: PhantomData<&'c PendingPredicateObligation<'tcx>>,
779    ) -> Result<(), FulfillmentErrorCode<'tcx>>
780    where
781        I: Clone + Iterator<Item = &'c PendingPredicateObligation<'tcx>>,
782    {
783        if self.selcx.coinductive_match(cycle.clone().map(|s| s.obligation.predicate)) {
784            debug!("process_child_obligations: coinductive match");
785            Ok(())
786        } else {
787            let cycle = cycle.map(|c| c.obligation.clone()).collect();
788            Err(FulfillmentErrorCode::Cycle(cycle))
789        }
790    }
791}
792
793impl<'a, 'tcx> FulfillProcessor<'a, 'tcx> {
794    #[instrument(level = "debug", skip(self, obligation, stalled_on))]
795    fn process_trait_obligation(
796        &mut self,
797        obligation: &PredicateObligation<'tcx>,
798        trait_obligation: PolyTraitObligation<'tcx>,
799        stalled_on: &mut Vec<TyOrConstInferVar>,
800    ) -> ProcessResult<PendingPredicateObligation<'tcx>, FulfillmentErrorCode<'tcx>> {
801        let infcx = self.selcx.infcx;
802        if obligation.predicate.is_global() && !matches!(infcx.typing_mode(), TypingMode::Coherence)
803        {
804            // no type variables present, can use evaluation for better caching.
805            // FIXME: consider caching errors too.
806            if infcx.predicate_must_hold_considering_regions(obligation) {
807                debug!(
808                    "selecting trait at depth {} evaluated to holds",
809                    obligation.recursion_depth
810                );
811                return ProcessResult::Changed(Default::default());
812            }
813        }
814
815        match self.selcx.poly_select(&trait_obligation) {
816            Ok(Some(impl_source)) => {
817                debug!("selecting trait at depth {} yielded Ok(Some)", obligation.recursion_depth);
818                ProcessResult::Changed(mk_pending(obligation, impl_source.nested_obligations()))
819            }
820            Ok(None) => {
821                debug!("selecting trait at depth {} yielded Ok(None)", obligation.recursion_depth);
822
823                // This is a bit subtle: for the most part, the
824                // only reason we can fail to make progress on
825                // trait selection is because we don't have enough
826                // information about the types in the trait.
827                stalled_on.clear();
828                stalled_on.extend(args_infer_vars(
829                    &self.selcx,
830                    trait_obligation.predicate.map_bound(|pred| pred.trait_ref.args),
831                ));
832
833                debug!(
834                    "process_predicate: pending obligation {:?} now stalled on {:?}",
835                    infcx.resolve_vars_if_possible(obligation.clone()),
836                    stalled_on
837                );
838
839                ProcessResult::Unchanged
840            }
841            Err(selection_err) => {
842                debug!("selecting trait at depth {} yielded Err", obligation.recursion_depth);
843
844                ProcessResult::Error(FulfillmentErrorCode::Select(selection_err))
845            }
846        }
847    }
848
849    fn process_projection_obligation(
850        &mut self,
851        obligation: &PredicateObligation<'tcx>,
852        project_obligation: PolyProjectionObligation<'tcx>,
853        stalled_on: &mut Vec<TyOrConstInferVar>,
854    ) -> ProcessResult<PendingPredicateObligation<'tcx>, FulfillmentErrorCode<'tcx>> {
855        let tcx = self.selcx.tcx();
856        let infcx = self.selcx.infcx;
857        if obligation.predicate.is_global() && !matches!(infcx.typing_mode(), TypingMode::Coherence)
858        {
859            // no type variables present, can use evaluation for better caching.
860            // FIXME: consider caching errors too.
861            if infcx.predicate_must_hold_considering_regions(obligation) {
862                if let Some(key) = ProjectionCacheKey::from_poly_projection_obligation(
863                    &mut self.selcx,
864                    &project_obligation,
865                ) {
866                    // If `predicate_must_hold_considering_regions` succeeds, then we've
867                    // evaluated all sub-obligations. We can therefore mark the 'root'
868                    // obligation as complete, and skip evaluating sub-obligations.
869                    infcx
870                        .inner
871                        .borrow_mut()
872                        .projection_cache()
873                        .complete(key, EvaluationResult::EvaluatedToOk);
874                }
875                return ProcessResult::Changed(Default::default());
876            } else {
877                debug!("Does NOT hold: {:?}", obligation);
878            }
879        }
880
881        match project::poly_project_and_unify_term(&mut self.selcx, &project_obligation) {
882            ProjectAndUnifyResult::Holds(os) => ProcessResult::Changed(mk_pending(obligation, os)),
883            ProjectAndUnifyResult::FailedNormalization => {
884                stalled_on.clear();
885                stalled_on.extend(args_infer_vars(
886                    &self.selcx,
887                    project_obligation.predicate.map_bound(|pred| pred.projection_term.args),
888                ));
889                ProcessResult::Unchanged
890            }
891            // Let the caller handle the recursion
892            ProjectAndUnifyResult::Recursive => {
893                let mut obligations = PredicateObligations::with_capacity(1);
894                obligations.push(project_obligation.with(tcx, project_obligation.predicate));
895
896                ProcessResult::Changed(mk_pending(obligation, obligations))
897            }
898            ProjectAndUnifyResult::MismatchedProjectionTypes(e) => {
899                ProcessResult::Error(FulfillmentErrorCode::Project(e))
900            }
901        }
902    }
903
904    fn process_host_obligation(
905        &mut self,
906        obligation: &PredicateObligation<'tcx>,
907        host_obligation: HostEffectObligation<'tcx>,
908        stalled_on: &mut Vec<TyOrConstInferVar>,
909    ) -> ProcessResult<PendingPredicateObligation<'tcx>, FulfillmentErrorCode<'tcx>> {
910        match effects::evaluate_host_effect_obligation(&mut self.selcx, &host_obligation) {
911            Ok(nested) => ProcessResult::Changed(mk_pending(obligation, nested)),
912            Err(effects::EvaluationFailure::Ambiguous) => {
913                stalled_on.clear();
914                stalled_on.extend(args_infer_vars(
915                    &self.selcx,
916                    ty::Binder::dummy(host_obligation.predicate.trait_ref.args),
917                ));
918                ProcessResult::Unchanged
919            }
920            Err(effects::EvaluationFailure::NoSolution) => {
921                ProcessResult::Error(FulfillmentErrorCode::Select(SelectionError::Unimplemented))
922            }
923        }
924    }
925}
926
927/// Returns the set of inference variables contained in `args`.
928fn args_infer_vars<'tcx>(
929    selcx: &SelectionContext<'_, 'tcx>,
930    args: ty::Binder<'tcx, GenericArgsRef<'tcx>>,
931) -> impl Iterator<Item = TyOrConstInferVar> {
932    selcx
933        .infcx
934        .resolve_vars_if_possible(args)
935        .skip_binder() // ok because this check doesn't care about regions
936        .iter()
937        .filter(|arg| arg.has_non_region_infer())
938        .flat_map(|arg| {
939            let mut walker = arg.walk();
940            while let Some(c) = walker.next() {
941                if !c.has_non_region_infer() {
942                    walker.visited.remove(&c);
943                    walker.skip_current_subtree();
944                }
945            }
946            walker.visited.into_iter()
947        })
948        .filter_map(TyOrConstInferVar::maybe_from_generic_arg)
949}
950
951#[derive(Debug)]
952pub struct OldSolverError<'tcx>(
953    Error<PendingPredicateObligation<'tcx>, FulfillmentErrorCode<'tcx>>,
954);
955
956impl<'tcx> FromSolverError<'tcx, OldSolverError<'tcx>> for FulfillmentError<'tcx> {
957    fn from_solver_error(_infcx: &InferCtxt<'tcx>, error: OldSolverError<'tcx>) -> Self {
958        let mut iter = error.0.backtrace.into_iter();
959        let obligation = iter.next().unwrap().obligation;
960        // The root obligation is the last item in the backtrace - if there's only
961        // one item, then it's the same as the main obligation
962        let root_obligation = iter.next_back().map_or_else(|| obligation.clone(), |e| e.obligation);
963        FulfillmentError::new(obligation, error.0.error, root_obligation)
964    }
965}
966
967impl<'tcx> FromSolverError<'tcx, OldSolverError<'tcx>> for ScrubbedTraitError<'tcx> {
968    fn from_solver_error(_infcx: &InferCtxt<'tcx>, error: OldSolverError<'tcx>) -> Self {
969        match error.0.error {
970            FulfillmentErrorCode::Select(_)
971            | FulfillmentErrorCode::Project(_)
972            | FulfillmentErrorCode::Subtype(_, _)
973            | FulfillmentErrorCode::ConstEquate(_, _) => ScrubbedTraitError::TrueError,
974            FulfillmentErrorCode::Ambiguity { overflow: _ } => ScrubbedTraitError::Ambiguity,
975            FulfillmentErrorCode::Cycle(cycle) => ScrubbedTraitError::Cycle(cycle),
976        }
977    }
978}