hir_ty/next_solver/
fulfill.rs

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

hir_ty/next_solver/
fulfill.rs
