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;
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    /// 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_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    /// Compared to `needs_process_obligation` this and its callees
240    /// contain some optimizations that come at the price of false negatives.
241    ///
242    /// They
243    /// - reduce branching by covering only the most common case
244    /// - take a read-only view of the unification tables which allows skipping undo_log
245    ///   construction.
246    /// - bail out on value-cache misses in ena to avoid pointer chasing
247    /// - hoist RefCell locking out of the loop
248    #[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    /// Identifies whether a predicate obligation needs processing.
263    ///
264    /// This is always inlined because it has a single callsite and it is
265    /// called *very* frequently. Be careful modifying this code! Several
266    /// compile-time benchmarks are very sensitive to even small changes.
267    #[inline(always)]
268    fn needs_process_obligation(&self, pending_obligation: &Self::Obligation) -> bool {
269        // If we were stalled on some unresolved variables, first check whether
270        // any of them have been resolved; if not, don't bother doing more work
271        // yet.
272        let stalled_on = &pending_obligation.stalled_on;
273        match stalled_on.len() {
274            // This case is the hottest most of the time, being hit up to 99%
275            // of the time. `keccak` and `cranelift-codegen-0.82.1` are
276            // benchmarks that particularly stress this path.
277            1 => self.selcx.infcx.ty_or_const_infer_var_changed(stalled_on[0]),
278
279            // In this case we haven't changed, but wish to make a change. Note
280            // that this is a special case, and is not equivalent to the `_`
281            // case below, which would return `false` for an empty `stalled_on`
282            // vector.
283            //
284            // This case is usually hit only 1% of the time or less, though it
285            // reaches 20% in `wasmparser-0.101.0`.
286            0 => true,
287
288            // This case is usually hit only 1% of the time or less, though it
289            // reaches 95% in `mime-0.3.16`, 64% in `wast-54.0.0`, and 12% in
290            // `inflate-0.4.5`.
291            //
292            // The obvious way of writing this, with a call to `any()` and no
293            // closure, is currently slower than this version.
294            _ => (|| {
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    /// Processes a predicate obligation and returns either:
306    /// - `Changed(v)` if the predicate is true, presuming that `v` are also true
307    /// - `Unchanged` if we don't have enough info to be sure
308    /// - `Error(e)` if the predicate does not hold
309    ///
310    /// This is called much less often than `needs_process_obligation`, so we
311    /// never inline it.
312    #[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                // Evaluation will discard candidates using the leak check.
351                // This means we need to pass it the bound version of our
352                // predicate.
353                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                // FIXME(const_trait_impl): We may need to do this using the higher-ranked
381                // pred instead of just instantiating it with placeholders b/c of
382                // higher-ranked implied bound issues in the old solver.
383                | 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                // Compute `ConstArgHasType` above the overflow check below.
462                // This is because this is not ever a useful obligation to report
463                // as the cause of an overflow.
464                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                        // FIXME(generic_const_exprs): we should construct an alias like
486                        // `<lhs_ty as Add<rhs_ty>>::Output` when this is an `Expr` representing
487                        // `lhs + rhs`.
488                        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                        // Only really exercised by generic_const_exprs
502                        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                // General case overflow check. Allow `process_trait_obligation`
514                // and `process_projection_obligation` to handle checking for
515                // the recursion limit themselves. Also don't check some
516                // predicate kinds that don't give further obligations.
517                _ 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                            // None means that both are unresolved.
552                            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                            // None means that both are unresolved.
581                            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                    // FIXME: we probably should only try to unify abstract constants
624                    // if the constants depend on generic parameters.
625                    //
626                    // Let's just see where this breaks :shrug:
627                    {
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                                    // Can define opaque types as this is only reachable with
640                                    // `generic_const_exprs`
641                                    .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                                    // Can define opaque types as this is only reachable with
658                                    // `generic_const_exprs`
659                                    .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                                // Can define opaque types as this is only reachable with
702                                // `generic_const_exprs`
703                                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                                // Two different constants using generic parameters ~> error.
736                                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            // no type variables present, can use evaluation for better caching.
780            // FIXME: consider caching errors too.
781            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                // This is a bit subtle: for the most part, the
799                // only reason we can fail to make progress on
800                // trait selection is because we don't have enough
801                // information about the types in the trait.
802                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            // no type variables present, can use evaluation for better caching.
835            // FIXME: consider caching errors too.
836            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                    // If `predicate_must_hold_considering_regions` succeeds, then we've
842                    // evaluated all sub-obligations. We can therefore mark the 'root'
843                    // obligation as complete, and skip evaluating sub-obligations.
844                    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            // Let the caller handle the recursion
867            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
901/// Returns the set of inference variables contained in `args`.
902fn 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() // ok because this check doesn't care about regions
910        .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        // The root obligation is the last item in the backtrace - if there's only
935        // one item, then it's the same as the main obligation
936        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}