rustc_trait_selection/solve/
fulfill.rs1use 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
31type PendingObligations<'tcx> =
33 ThinVec<(PredicateObligation<'tcx>, Option<GoalStalledOn<TyCtxt<'tcx>>>)>;
34
35pub struct FulfillmentCtxt<'tcx, E: 'tcx> {
47 obligations: ObligationStorage<'tcx>,
48
49 usable_in_snapshot: usize,
54 _errors: PhantomData<E>,
55}
56
57#[derive(Default, Debug)]
58struct ObligationStorage<'tcx> {
59 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 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 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 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
292struct 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}