rustc_trait_selection/solve/
fulfill.rs

1use std::marker::PhantomData;
2use std::mem;
3use std::ops::ControlFlow;
4
5use rustc_data_structures::thinvec::ExtractIf;
6use rustc_hir::def_id::LocalDefId;
7use rustc_infer::infer::InferCtxt;
8use rustc_infer::traits::query::NoSolution;
9use rustc_infer::traits::{
10    FromSolverError, PredicateObligation, PredicateObligations, TraitEngine,
11};
12use rustc_middle::ty::{
13    self, DelayedSet, Ty, TyCtxt, TypeSuperVisitable, TypeVisitable, TypeVisitor, TypingMode,
14};
15use rustc_next_trait_solver::delegate::SolverDelegate as _;
16use rustc_next_trait_solver::solve::{
17    GoalEvaluation, GoalStalledOn, HasChanged, SolverDelegateEvalExt as _,
18};
19use rustc_span::Span;
20use thin_vec::ThinVec;
21use tracing::instrument;
22
23use self::derive_errors::*;
24use super::Certainty;
25use super::delegate::SolverDelegate;
26use super::inspect::{self, ProofTreeInferCtxtExt};
27use crate::traits::{FulfillmentError, ScrubbedTraitError};
28
29mod derive_errors;
30
31// FIXME: Do we need to use a `ThinVec` here?
32type PendingObligations<'tcx> =
33    ThinVec<(PredicateObligation<'tcx>, Option<GoalStalledOn<TyCtxt<'tcx>>>)>;
34
35/// A trait engine using the new trait solver.
36///
37/// This is mostly identical to how `evaluate_all` works inside of the
38/// solver, except that the requirements are slightly different.
39///
40/// Unlike `evaluate_all` it is possible to add new obligations later on
41/// and we also have to track diagnostics information by using `Obligation`
42/// instead of `Goal`.
43///
44/// It is also likely that we want to use slightly different datastructures
45/// here as this will have to deal with far more root goals than `evaluate_all`.
46pub struct FulfillmentCtxt<'tcx, E: 'tcx> {
47    obligations: ObligationStorage<'tcx>,
48
49    /// The snapshot in which this context was created. Using the context
50    /// outside of this snapshot leads to subtle bugs if the snapshot
51    /// gets rolled back. Because of this we explicitly check that we only
52    /// use the context in exactly this snapshot.
53    usable_in_snapshot: usize,
54    _errors: PhantomData<E>,
55}
56
57#[derive(Default, Debug)]
58struct ObligationStorage<'tcx> {
59    /// Obligations which resulted in an overflow in fulfillment itself.
60    ///
61    /// We cannot eagerly return these as error so we instead store them here
62    /// to avoid recomputing them each time `select_where_possible` is called.
63    /// This also allows us to return the correct `FulfillmentError` for them.
64    overflowed: Vec<PredicateObligation<'tcx>>,
65    pending: PendingObligations<'tcx>,
66}
67
68impl<'tcx> ObligationStorage<'tcx> {
69    fn register(
70        &mut self,
71        obligation: PredicateObligation<'tcx>,
72        stalled_on: Option<GoalStalledOn<TyCtxt<'tcx>>>,
73    ) {
74        self.pending.push((obligation, stalled_on));
75    }
76
77    fn has_pending_obligations(&self) -> bool {
78        !self.pending.is_empty() || !self.overflowed.is_empty()
79    }
80
81    fn clone_pending(&self) -> PredicateObligations<'tcx> {
82        let mut obligations: PredicateObligations<'tcx> =
83            self.pending.iter().map(|(o, _)| o.clone()).collect();
84        obligations.extend(self.overflowed.iter().cloned());
85        obligations
86    }
87
88    fn drain_pending(
89        &mut self,
90        cond: impl Fn(&PredicateObligation<'tcx>) -> bool,
91    ) -> PendingObligations<'tcx> {
92        let (unstalled, pending) =
93            mem::take(&mut self.pending).into_iter().partition(|(o, _)| cond(o));
94        self.pending = pending;
95        unstalled
96    }
97
98    fn on_fulfillment_overflow(&mut self, infcx: &InferCtxt<'tcx>) {
99        infcx.probe(|_| {
100            // IMPORTANT: we must not use solve any inference variables in the obligations
101            // as this is all happening inside of a probe. We use a probe to make sure
102            // we get all obligations involved in the overflow. We pretty much check: if
103            // we were to do another step of `select_where_possible`, which goals would
104            // change.
105            // FIXME: <https://github.com/Gankra/thin-vec/pull/66> is merged, this can be removed.
106            self.overflowed.extend(
107                ExtractIf::new(&mut self.pending, |(o, stalled_on)| {
108                    let goal = o.as_goal();
109                    let result = <&SolverDelegate<'tcx>>::from(infcx).evaluate_root_goal(
110                        goal,
111                        o.cause.span,
112                        stalled_on.take(),
113                    );
114                    matches!(result, Ok(GoalEvaluation { has_changed: HasChanged::Yes, .. }))
115                })
116                .map(|(o, _)| o),
117            );
118        })
119    }
120}
121
122impl<'tcx, E: 'tcx> FulfillmentCtxt<'tcx, E> {
123    pub fn new(infcx: &InferCtxt<'tcx>) -> FulfillmentCtxt<'tcx, E> {
124        assert!(
125            infcx.next_trait_solver(),
126            "new trait solver fulfillment context created when \
127            infcx is set up for old trait solver"
128        );
129        FulfillmentCtxt {
130            obligations: Default::default(),
131            usable_in_snapshot: infcx.num_open_snapshots(),
132            _errors: PhantomData,
133        }
134    }
135
136    fn inspect_evaluated_obligation(
137        &self,
138        infcx: &InferCtxt<'tcx>,
139        obligation: &PredicateObligation<'tcx>,
140        result: &Result<GoalEvaluation<TyCtxt<'tcx>>, NoSolution>,
141    ) {
142        if let Some(inspector) = infcx.obligation_inspector.get() {
143            let result = match result {
144                Ok(GoalEvaluation { certainty, .. }) => Ok(*certainty),
145                Err(NoSolution) => Err(NoSolution),
146            };
147            (inspector)(infcx, &obligation, result);
148        }
149    }
150}
151
152impl<'tcx, E> TraitEngine<'tcx, E> for FulfillmentCtxt<'tcx, E>
153where
154    E: FromSolverError<'tcx, NextSolverError<'tcx>>,
155{
156    #[instrument(level = "trace", skip(self, infcx))]
157    fn register_predicate_obligation(
158        &mut self,
159        infcx: &InferCtxt<'tcx>,
160        obligation: PredicateObligation<'tcx>,
161    ) {
162        assert_eq!(self.usable_in_snapshot, infcx.num_open_snapshots());
163        self.obligations.register(obligation, None);
164    }
165
166    fn collect_remaining_errors(&mut self, infcx: &InferCtxt<'tcx>) -> Vec<E> {
167        self.obligations
168            .pending
169            .drain(..)
170            .map(|(obligation, _)| NextSolverError::Ambiguity(obligation))
171            .chain(
172                self.obligations
173                    .overflowed
174                    .drain(..)
175                    .map(|obligation| NextSolverError::Overflow(obligation)),
176            )
177            .map(|e| E::from_solver_error(infcx, e))
178            .collect()
179    }
180
181    fn select_where_possible(&mut self, infcx: &InferCtxt<'tcx>) -> Vec<E> {
182        assert_eq!(self.usable_in_snapshot, infcx.num_open_snapshots());
183        let mut errors = Vec::new();
184        loop {
185            let mut any_changed = false;
186            for (mut obligation, stalled_on) in self.obligations.drain_pending(|_| true) {
187                if !infcx.tcx.recursion_limit().value_within_limit(obligation.recursion_depth) {
188                    self.obligations.on_fulfillment_overflow(infcx);
189                    // Only return true errors that we have accumulated while processing.
190                    return errors;
191                }
192
193                let goal = obligation.as_goal();
194                let delegate = <&SolverDelegate<'tcx>>::from(infcx);
195                if let Some(certainty) =
196                    delegate.compute_goal_fast_path(goal, obligation.cause.span)
197                {
198                    match certainty {
199                        Certainty::Yes => {}
200                        Certainty::Maybe(_) => {
201                            self.obligations.register(obligation, None);
202                        }
203                    }
204                    continue;
205                }
206
207                let result = delegate.evaluate_root_goal(goal, obligation.cause.span, stalled_on);
208                self.inspect_evaluated_obligation(infcx, &obligation, &result);
209                let GoalEvaluation { certainty, has_changed, stalled_on } = match result {
210                    Ok(result) => result,
211                    Err(NoSolution) => {
212                        errors.push(E::from_solver_error(
213                            infcx,
214                            NextSolverError::TrueError(obligation),
215                        ));
216                        continue;
217                    }
218                };
219
220                if has_changed == HasChanged::Yes {
221                    // We increment the recursion depth here to track the number of times
222                    // this goal has resulted in inference progress. This doesn't precisely
223                    // model the way that we track recursion depth in the old solver due
224                    // to the fact that we only process root obligations, but it is a good
225                    // approximation and should only result in fulfillment overflow in
226                    // pathological cases.
227                    obligation.recursion_depth += 1;
228                    any_changed = true;
229                }
230
231                match certainty {
232                    Certainty::Yes => {}
233                    Certainty::Maybe(_) => self.obligations.register(obligation, stalled_on),
234                }
235            }
236
237            if !any_changed {
238                break;
239            }
240        }
241
242        errors
243    }
244
245    fn has_pending_obligations(&self) -> bool {
246        self.obligations.has_pending_obligations()
247    }
248
249    fn pending_obligations(&self) -> PredicateObligations<'tcx> {
250        self.obligations.clone_pending()
251    }
252
253    fn drain_stalled_obligations_for_coroutines(
254        &mut self,
255        infcx: &InferCtxt<'tcx>,
256    ) -> PredicateObligations<'tcx> {
257        let stalled_generators = match infcx.typing_mode() {
258            TypingMode::Analysis { defining_opaque_types_and_generators } => {
259                defining_opaque_types_and_generators
260            }
261            TypingMode::Coherence
262            | TypingMode::Borrowck { defining_opaque_types: _ }
263            | TypingMode::PostBorrowckAnalysis { defined_opaque_types: _ }
264            | TypingMode::PostAnalysis => return Default::default(),
265        };
266
267        if stalled_generators.is_empty() {
268            return Default::default();
269        }
270
271        self.obligations
272            .drain_pending(|obl| {
273                infcx.probe(|_| {
274                    infcx
275                        .visit_proof_tree(
276                            obl.as_goal(),
277                            &mut StalledOnCoroutines {
278                                stalled_generators,
279                                span: obl.cause.span,
280                                cache: Default::default(),
281                            },
282                        )
283                        .is_break()
284                })
285            })
286            .into_iter()
287            .map(|(o, _)| o)
288            .collect()
289    }
290}
291
292/// Detect if a goal is stalled on a coroutine that is owned by the current typeck root.
293///
294/// This function can (erroneously) fail to detect a predicate, i.e. it doesn't need to
295/// be complete. However, this will lead to ambiguity errors, so we want to make it
296/// accurate.
297///
298/// This function can be also return false positives, which will lead to poor diagnostics
299/// so we want to keep this visitor *precise* too.
300struct StalledOnCoroutines<'tcx> {
301    stalled_generators: &'tcx ty::List<LocalDefId>,
302    span: Span,
303    cache: DelayedSet<Ty<'tcx>>,
304}
305
306impl<'tcx> inspect::ProofTreeVisitor<'tcx> for StalledOnCoroutines<'tcx> {
307    type Result = ControlFlow<()>;
308
309    fn span(&self) -> rustc_span::Span {
310        self.span
311    }
312
313    fn visit_goal(&mut self, inspect_goal: &super::inspect::InspectGoal<'_, 'tcx>) -> Self::Result {
314        inspect_goal.goal().predicate.visit_with(self)?;
315
316        if let Some(candidate) = inspect_goal.unique_applicable_candidate() {
317            candidate.visit_nested_no_probe(self)
318        } else {
319            ControlFlow::Continue(())
320        }
321    }
322}
323
324impl<'tcx> TypeVisitor<TyCtxt<'tcx>> for StalledOnCoroutines<'tcx> {
325    type Result = ControlFlow<()>;
326
327    fn visit_ty(&mut self, ty: Ty<'tcx>) -> Self::Result {
328        if !self.cache.insert(ty) {
329            return ControlFlow::Continue(());
330        }
331
332        if let ty::CoroutineWitness(def_id, _) = *ty.kind()
333            && def_id.as_local().is_some_and(|def_id| self.stalled_generators.contains(&def_id))
334        {
335            return ControlFlow::Break(());
336        }
337
338        ty.super_visit_with(self)
339    }
340}
341
342pub enum NextSolverError<'tcx> {
343    TrueError(PredicateObligation<'tcx>),
344    Ambiguity(PredicateObligation<'tcx>),
345    Overflow(PredicateObligation<'tcx>),
346}
347
348impl<'tcx> FromSolverError<'tcx, NextSolverError<'tcx>> for FulfillmentError<'tcx> {
349    fn from_solver_error(infcx: &InferCtxt<'tcx>, error: NextSolverError<'tcx>) -> Self {
350        match error {
351            NextSolverError::TrueError(obligation) => {
352                fulfillment_error_for_no_solution(infcx, obligation)
353            }
354            NextSolverError::Ambiguity(obligation) => {
355                fulfillment_error_for_stalled(infcx, obligation)
356            }
357            NextSolverError::Overflow(obligation) => {
358                fulfillment_error_for_overflow(infcx, obligation)
359            }
360        }
361    }
362}
363
364impl<'tcx> FromSolverError<'tcx, NextSolverError<'tcx>> for ScrubbedTraitError<'tcx> {
365    fn from_solver_error(_infcx: &InferCtxt<'tcx>, error: NextSolverError<'tcx>) -> Self {
366        match error {
367            NextSolverError::TrueError(_) => ScrubbedTraitError::TrueError,
368            NextSolverError::Ambiguity(_) | NextSolverError::Overflow(_) => {
369                ScrubbedTraitError::Ambiguity
370            }
371        }
372    }
373}