]>
Commit | Line | Data |
---|---|---|
ba9703b0 | 1 | use crate::infer::{InferCtxt, TyOrConstInferVar}; |
dfeec247 | 2 | use rustc_data_structures::obligation_forest::ProcessResult; |
29967ef6 | 3 | use rustc_data_structures::obligation_forest::{Error, ForestObligation, Outcome}; |
a1dfa0c6 | 4 | use rustc_data_structures::obligation_forest::{ObligationForest, ObligationProcessor}; |
a2a8927a | 5 | use rustc_infer::traits::ProjectionCacheKey; |
487cf647 | 6 | use rustc_infer::traits::{SelectionError, TraitEngine, TraitObligation}; |
f9f354fc | 7 | use rustc_middle::mir::interpret::ErrorHandled; |
064997fb | 8 | use rustc_middle::ty::abstract_const::NotConstEvaluatable; |
17df50a5 | 9 | use rustc_middle::ty::error::{ExpectedFound, TypeError}; |
6a06907d | 10 | use rustc_middle::ty::subst::SubstsRef; |
9ffffee4 | 11 | use rustc_middle::ty::{self, Binder, Const, TypeVisitableExt}; |
a7813a04 | 12 | use std::marker::PhantomData; |
1a4d82fc | 13 | |
1b1a35ee | 14 | use super::const_evaluatable; |
5e7ed085 | 15 | use super::project::{self, ProjectAndUnifyResult}; |
dfeec247 XL |
16 | use super::select::SelectionContext; |
17 | use super::wf; | |
1a4d82fc JJ |
18 | use super::CodeAmbiguity; |
19 | use super::CodeProjectionError; | |
20 | use super::CodeSelectionError; | |
a2a8927a | 21 | use super::EvaluationResult; |
487cf647 | 22 | use super::PredicateObligation; |
cdc7bbd5 | 23 | use super::Unimplemented; |
8bb4bdeb | 24 | use super::{FulfillmentError, FulfillmentErrorCode}; |
a7813a04 | 25 | |
3dfed10e | 26 | use crate::traits::project::PolyProjectionObligation; |
a2a8927a | 27 | use crate::traits::project::ProjectionCacheKeyExt as _; |
2b03887a | 28 | use crate::traits::query::evaluate_obligation::InferCtxtExt; |
ba9703b0 | 29 | |
a7813a04 | 30 | impl<'tcx> ForestObligation for PendingPredicateObligation<'tcx> { |
74b04a01 XL |
31 | /// Note that we include both the `ParamEnv` and the `Predicate`, |
32 | /// as the `ParamEnv` can influence whether fulfillment succeeds | |
33 | /// or fails. | |
34 | type CacheKey = ty::ParamEnvAnd<'tcx, ty::Predicate<'tcx>>; | |
a7813a04 | 35 | |
74b04a01 XL |
36 | fn as_cache_key(&self) -> Self::CacheKey { |
37 | self.obligation.param_env.and(self.obligation.predicate) | |
dfeec247 | 38 | } |
a7813a04 | 39 | } |
1a4d82fc | 40 | |
9fa01778 | 41 | /// The fulfillment context is used to drive trait resolution. It |
1a4d82fc JJ |
42 | /// consists of a list of obligations that must be (eventually) |
43 | /// satisfied. The job is to track which are satisfied, which yielded | |
44 | /// errors, and which are still pending. At any point, users can call | |
3b2f2976 | 45 | /// `select_where_possible`, and the fulfillment context will try to do |
1a4d82fc JJ |
46 | /// selection, retaining only those obligations that remain |
47 | /// ambiguous. This may be helpful in pushing type inference | |
48 | /// along. Once all type inference constraints have been generated, the | |
49 | /// method `select_all_or_error` can be used to report any remaining | |
50 | /// ambiguous cases as errors. | |
51 | pub struct FulfillmentContext<'tcx> { | |
1a4d82fc JJ |
52 | // A list of all obligations that have been registered with this |
53 | // fulfillment context. | |
a7813a04 | 54 | predicates: ObligationForest<PendingPredicateObligation<'tcx>>, |
c295e0f8 | 55 | |
0731742a XL |
56 | // Is it OK to register obligations into this infcx inside |
57 | // an infcx snapshot? | |
58 | // | |
59 | // The "primary fulfillment" in many cases in typeck lives | |
60 | // outside of any snapshot, so any use of it inside a snapshot | |
61 | // will lead to trouble and therefore is checked against, but | |
62 | // other fulfillment contexts sometimes do live inside of | |
63 | // a snapshot (they don't *straddle* a snapshot, so there | |
64 | // is no trouble there). | |
dfeec247 | 65 | usable_in_snapshot: bool, |
1a4d82fc JJ |
66 | } |
67 | ||
7453a54e SL |
68 | #[derive(Clone, Debug)] |
69 | pub struct PendingPredicateObligation<'tcx> { | |
70 | pub obligation: PredicateObligation<'tcx>, | |
f9f354fc XL |
71 | // This is far more often read than modified, meaning that we |
72 | // should mostly optimize for reading speed, while modifying is not as relevant. | |
73 | // | |
74 | // For whatever reason using a boxed slice is slower than using a `Vec` here. | |
ba9703b0 | 75 | pub stalled_on: Vec<TyOrConstInferVar<'tcx>>, |
7453a54e SL |
76 | } |
77 | ||
e1599b0c | 78 | // `PendingPredicateObligation` is used a lot. Make sure it doesn't unintentionally get bigger. |
6a06907d | 79 | #[cfg(all(target_arch = "x86_64", target_pointer_width = "64"))] |
a2a8927a | 80 | static_assert_size!(PendingPredicateObligation<'_>, 72); |
e1599b0c | 81 | |
dc9dc135 | 82 | impl<'a, 'tcx> FulfillmentContext<'tcx> { |
62682a34 | 83 | /// Creates a new fulfillment context. |
487cf647 | 84 | pub(super) fn new() -> FulfillmentContext<'tcx> { |
9ffffee4 | 85 | FulfillmentContext { predicates: ObligationForest::new(), usable_in_snapshot: false } |
0731742a XL |
86 | } |
87 | ||
487cf647 | 88 | pub(super) fn new_in_snapshot() -> FulfillmentContext<'tcx> { |
9ffffee4 | 89 | FulfillmentContext { predicates: ObligationForest::new(), usable_in_snapshot: true } |
ff7c6d11 XL |
90 | } |
91 | ||
8faf50e0 | 92 | /// Attempts to select obligations using `selcx`. |
2b03887a | 93 | fn select(&mut self, selcx: SelectionContext<'a, 'tcx>) -> Vec<FulfillmentError<'tcx>> { |
29967ef6 XL |
94 | let span = debug_span!("select", obligation_forest_size = ?self.predicates.len()); |
95 | let _enter = span.enter(); | |
0531ce1d | 96 | |
923072b8 | 97 | // Process pending obligations. |
064997fb FG |
98 | let outcome: Outcome<_, _> = |
99 | self.predicates.process_obligations(&mut FulfillProcessor { selcx }); | |
0531ce1d | 100 | |
923072b8 FG |
101 | // FIXME: if we kept the original cache key, we could mark projection |
102 | // obligations as complete for the projection cache here. | |
0531ce1d | 103 | |
064997fb FG |
104 | let errors: Vec<FulfillmentError<'tcx>> = |
105 | outcome.errors.into_iter().map(to_fulfillment_error).collect(); | |
0531ce1d | 106 | |
dfeec247 XL |
107 | debug!( |
108 | "select({} predicates remaining, {} errors) done", | |
109 | self.predicates.len(), | |
110 | errors.len() | |
111 | ); | |
0531ce1d | 112 | |
3c0e092e | 113 | errors |
0531ce1d XL |
114 | } |
115 | } | |
116 | ||
117 | impl<'tcx> TraitEngine<'tcx> for FulfillmentContext<'tcx> { | |
dc9dc135 XL |
118 | fn register_predicate_obligation( |
119 | &mut self, | |
2b03887a | 120 | infcx: &InferCtxt<'tcx>, |
dc9dc135 XL |
121 | obligation: PredicateObligation<'tcx>, |
122 | ) { | |
1a4d82fc JJ |
123 | // this helps to reduce duplicate errors, as well as making |
124 | // debug output much nicer to read and so on. | |
fc512014 | 125 | let obligation = infcx.resolve_vars_if_possible(obligation); |
1a4d82fc | 126 | |
29967ef6 | 127 | debug!(?obligation, "register_predicate_obligation"); |
3157f602 | 128 | |
0731742a | 129 | assert!(!infcx.is_in_snapshot() || self.usable_in_snapshot); |
3157f602 | 130 | |
dfeec247 XL |
131 | self.predicates |
132 | .register_obligation(PendingPredicateObligation { obligation, stalled_on: vec![] }); | |
a7813a04 XL |
133 | } |
134 | ||
9ffffee4 | 135 | fn collect_remaining_errors(&mut self) -> Vec<FulfillmentError<'tcx>> { |
3c0e092e | 136 | self.predicates.to_errors(CodeAmbiguity).into_iter().map(to_fulfillment_error).collect() |
1a4d82fc JJ |
137 | } |
138 | ||
2b03887a FG |
139 | fn select_where_possible(&mut self, infcx: &InferCtxt<'tcx>) -> Vec<FulfillmentError<'tcx>> { |
140 | let selcx = SelectionContext::new(infcx); | |
141 | self.select(selcx) | |
1a4d82fc JJ |
142 | } |
143 | ||
9ffffee4 FG |
144 | fn drain_unstalled_obligations( |
145 | &mut self, | |
146 | infcx: &InferCtxt<'tcx>, | |
147 | ) -> Vec<PredicateObligation<'tcx>> { | |
148 | let mut processor = DrainProcessor { removed_predicates: Vec::new(), infcx }; | |
149 | let outcome: Outcome<_, _> = self.predicates.process_obligations(&mut processor); | |
150 | assert!(outcome.errors.is_empty()); | |
151 | return processor.removed_predicates; | |
152 | ||
153 | struct DrainProcessor<'a, 'tcx> { | |
154 | infcx: &'a InferCtxt<'tcx>, | |
155 | removed_predicates: Vec<PredicateObligation<'tcx>>, | |
156 | } | |
157 | ||
158 | impl<'tcx> ObligationProcessor for DrainProcessor<'_, 'tcx> { | |
159 | type Obligation = PendingPredicateObligation<'tcx>; | |
160 | type Error = !; | |
161 | type OUT = Outcome<Self::Obligation, Self::Error>; | |
162 | ||
163 | fn needs_process_obligation(&self, pending_obligation: &Self::Obligation) -> bool { | |
164 | pending_obligation | |
165 | .stalled_on | |
166 | .iter() | |
167 | .any(|&var| self.infcx.ty_or_const_infer_var_changed(var)) | |
168 | } | |
169 | ||
170 | fn process_obligation( | |
171 | &mut self, | |
172 | pending_obligation: &mut PendingPredicateObligation<'tcx>, | |
173 | ) -> ProcessResult<PendingPredicateObligation<'tcx>, !> { | |
174 | assert!(self.needs_process_obligation(pending_obligation)); | |
175 | self.removed_predicates.push(pending_obligation.obligation.clone()); | |
176 | ProcessResult::Changed(vec![]) | |
177 | } | |
178 | ||
179 | fn process_backedge<'c, I>( | |
180 | &mut self, | |
181 | cycle: I, | |
182 | _marker: PhantomData<&'c PendingPredicateObligation<'tcx>>, | |
183 | ) -> Result<(), !> | |
184 | where | |
185 | I: Clone + Iterator<Item = &'c PendingPredicateObligation<'tcx>>, | |
186 | { | |
187 | self.removed_predicates.extend(cycle.map(|c| c.obligation.clone())); | |
188 | Ok(()) | |
189 | } | |
190 | } | |
1a4d82fc | 191 | } |
c295e0f8 | 192 | |
9ffffee4 FG |
193 | fn pending_obligations(&self) -> Vec<PredicateObligation<'tcx>> { |
194 | self.predicates.map_pending_obligations(|o| o.obligation.clone()) | |
c295e0f8 | 195 | } |
1a4d82fc JJ |
196 | } |
197 | ||
2b03887a FG |
198 | struct FulfillProcessor<'a, 'tcx> { |
199 | selcx: SelectionContext<'a, 'tcx>, | |
54a0048b SL |
200 | } |
201 | ||
a2a8927a | 202 | fn mk_pending(os: Vec<PredicateObligation<'_>>) -> Vec<PendingPredicateObligation<'_>> { |
dfeec247 XL |
203 | os.into_iter() |
204 | .map(|o| PendingPredicateObligation { obligation: o, stalled_on: vec![] }) | |
205 | .collect() | |
94b46f34 XL |
206 | } |
207 | ||
2b03887a | 208 | impl<'a, 'tcx> ObligationProcessor for FulfillProcessor<'a, 'tcx> { |
a7813a04 XL |
209 | type Obligation = PendingPredicateObligation<'tcx>; |
210 | type Error = FulfillmentErrorCode<'tcx>; | |
2b03887a | 211 | type OUT = Outcome<Self::Obligation, Self::Error>; |
7453a54e | 212 | |
923072b8 | 213 | /// Identifies whether a predicate obligation needs processing. |
94b46f34 | 214 | /// |
9ffffee4 FG |
215 | /// This is always inlined because it has a single callsite and it is |
216 | /// called *very* frequently. Be careful modifying this code! Several | |
217 | /// compile-time benchmarks are very sensitive to even small changes. | |
94b46f34 | 218 | #[inline(always)] |
923072b8 | 219 | fn needs_process_obligation(&self, pending_obligation: &Self::Obligation) -> bool { |
e74abb32 XL |
220 | // If we were stalled on some unresolved variables, first check whether |
221 | // any of them have been resolved; if not, don't bother doing more work | |
222 | // yet. | |
9ffffee4 FG |
223 | let stalled_on = &pending_obligation.stalled_on; |
224 | match stalled_on.len() { | |
225 | // This case is the hottest most of the time, being hit up to 99% | |
226 | // of the time. `keccak` and `cranelift-codegen-0.82.1` are | |
227 | // benchmarks that particularly stress this path. | |
228 | 1 => self.selcx.infcx.ty_or_const_infer_var_changed(stalled_on[0]), | |
229 | ||
230 | // In this case we haven't changed, but wish to make a change. Note | |
231 | // that this is a special case, and is not equivalent to the `_` | |
232 | // case below, which would return `false` for an empty `stalled_on` | |
233 | // vector. | |
234 | // | |
235 | // This case is usually hit only 1% of the time or less, though it | |
236 | // reaches 20% in `wasmparser-0.101.0`. | |
237 | 0 => true, | |
238 | ||
239 | // This case is usually hit only 1% of the time or less, though it | |
240 | // reaches 95% in `mime-0.3.16`, 64% in `wast-54.0.0`, and 12% in | |
241 | // `inflate-0.4.5`. | |
242 | // | |
243 | // The obvious way of writing this, with a call to `any()` and no | |
244 | // closure, is currently slower than this version. | |
245 | _ => (|| { | |
246 | for &infer_var in stalled_on { | |
247 | if self.selcx.infcx.ty_or_const_infer_var_changed(infer_var) { | |
248 | return true; | |
e74abb32 | 249 | } |
9ffffee4 FG |
250 | } |
251 | false | |
252 | })(), | |
1b1a35ee XL |
253 | } |
254 | } | |
e74abb32 | 255 | |
923072b8 FG |
256 | /// Processes a predicate obligation and returns either: |
257 | /// - `Changed(v)` if the predicate is true, presuming that `v` are also true | |
258 | /// - `Unchanged` if we don't have enough info to be sure | |
259 | /// - `Error(e)` if the predicate does not hold | |
260 | /// | |
261 | /// This is called much less often than `needs_process_obligation`, so we | |
262 | /// never inline it. | |
1b1a35ee | 263 | #[inline(never)] |
064997fb | 264 | #[instrument(level = "debug", skip(self, pending_obligation))] |
923072b8 | 265 | fn process_obligation( |
1b1a35ee XL |
266 | &mut self, |
267 | pending_obligation: &mut PendingPredicateObligation<'tcx>, | |
268 | ) -> ProcessResult<PendingPredicateObligation<'tcx>, FulfillmentErrorCode<'tcx>> { | |
e74abb32 XL |
269 | pending_obligation.stalled_on.truncate(0); |
270 | ||
94b46f34 | 271 | let obligation = &mut pending_obligation.obligation; |
7453a54e | 272 | |
064997fb | 273 | debug!(?obligation, "pre-resolve"); |
5e7ed085 | 274 | |
2b03887a | 275 | if obligation.predicate.has_non_region_infer() { |
487cf647 | 276 | obligation.predicate = self.selcx.infcx.resolve_vars_if_possible(obligation.predicate); |
7453a54e | 277 | } |
1a4d82fc | 278 | |
923072b8 FG |
279 | let obligation = &pending_obligation.obligation; |
280 | ||
487cf647 | 281 | let infcx = self.selcx.infcx; |
f9f354fc | 282 | |
5e7ed085 FG |
283 | if obligation.predicate.has_projections() { |
284 | let mut obligations = Vec::new(); | |
285 | let predicate = crate::traits::project::try_normalize_with_depth_to( | |
2b03887a | 286 | &mut self.selcx, |
5e7ed085 FG |
287 | obligation.param_env, |
288 | obligation.cause.clone(), | |
289 | obligation.recursion_depth + 1, | |
290 | obligation.predicate, | |
291 | &mut obligations, | |
292 | ); | |
293 | if predicate != obligation.predicate { | |
487cf647 | 294 | obligations.push(obligation.with(infcx.tcx, predicate)); |
5e7ed085 FG |
295 | return ProcessResult::Changed(mk_pending(obligations)); |
296 | } | |
297 | } | |
5869c6ff XL |
298 | let binder = obligation.predicate.kind(); |
299 | match binder.no_bound_vars() { | |
300 | None => match binder.skip_binder() { | |
3dfed10e XL |
301 | // Evaluation will discard candidates using the leak check. |
302 | // This means we need to pass it the bound version of our | |
303 | // predicate. | |
487cf647 FG |
304 | ty::PredicateKind::Clause(ty::Clause::Trait(trait_ref)) => { |
305 | let trait_obligation = obligation.with(infcx.tcx, binder.rebind(trait_ref)); | |
3dfed10e XL |
306 | |
307 | self.process_trait_obligation( | |
308 | obligation, | |
309 | trait_obligation, | |
310 | &mut pending_obligation.stalled_on, | |
311 | ) | |
3b2f2976 | 312 | } |
487cf647 FG |
313 | ty::PredicateKind::Clause(ty::Clause::Projection(data)) => { |
314 | let project_obligation = obligation.with(infcx.tcx, binder.rebind(data)); | |
7453a54e | 315 | |
3dfed10e | 316 | self.process_projection_obligation( |
136023e0 | 317 | obligation, |
3dfed10e XL |
318 | project_obligation, |
319 | &mut pending_obligation.stalled_on, | |
320 | ) | |
321 | } | |
487cf647 FG |
322 | ty::PredicateKind::Clause(ty::Clause::RegionOutlives(_)) |
323 | | ty::PredicateKind::Clause(ty::Clause::TypeOutlives(_)) | |
9ffffee4 | 324 | | ty::PredicateKind::Clause(ty::Clause::ConstArgHasType(..)) |
5869c6ff XL |
325 | | ty::PredicateKind::WellFormed(_) |
326 | | ty::PredicateKind::ObjectSafe(_) | |
327 | | ty::PredicateKind::ClosureKind(..) | |
328 | | ty::PredicateKind::Subtype(_) | |
94222f64 | 329 | | ty::PredicateKind::Coerce(_) |
5869c6ff XL |
330 | | ty::PredicateKind::ConstEvaluatable(..) |
331 | | ty::PredicateKind::ConstEquate(..) => { | |
c295e0f8 | 332 | let pred = |
9ffffee4 | 333 | ty::Binder::dummy(infcx.instantiate_binder_with_placeholders(binder)); |
487cf647 | 334 | ProcessResult::Changed(mk_pending(vec![obligation.with(infcx.tcx, pred)])) |
3dfed10e | 335 | } |
487cf647 | 336 | ty::PredicateKind::Ambiguous => ProcessResult::Unchanged, |
5869c6ff | 337 | ty::PredicateKind::TypeWellFormedFromEnv(..) => { |
1b1a35ee XL |
338 | bug!("TypeWellFormedFromEnv is only used for Chalk") |
339 | } | |
9ffffee4 FG |
340 | ty::PredicateKind::AliasEq(..) => { |
341 | bug!("AliasEq is only used for new solver") | |
342 | } | |
3dfed10e | 343 | }, |
5869c6ff | 344 | Some(pred) => match pred { |
487cf647 FG |
345 | ty::PredicateKind::Clause(ty::Clause::Trait(data)) => { |
346 | let trait_obligation = obligation.with(infcx.tcx, Binder::dummy(data)); | |
3dfed10e XL |
347 | |
348 | self.process_trait_obligation( | |
349 | obligation, | |
350 | trait_obligation, | |
351 | &mut pending_obligation.stalled_on, | |
352 | ) | |
353 | } | |
94b46f34 | 354 | |
487cf647 | 355 | ty::PredicateKind::Clause(ty::Clause::RegionOutlives(data)) => { |
2b03887a | 356 | if infcx.considering_regions { |
064997fb | 357 | infcx.region_outlives_predicate(&obligation.cause, Binder::dummy(data)); |
94b46f34 | 358 | } |
064997fb FG |
359 | |
360 | ProcessResult::Changed(vec![]) | |
3dfed10e | 361 | } |
5bcae85e | 362 | |
487cf647 FG |
363 | ty::PredicateKind::Clause(ty::Clause::TypeOutlives(ty::OutlivesPredicate( |
364 | t_a, | |
365 | r_b, | |
366 | ))) => { | |
064997fb FG |
367 | if infcx.considering_regions { |
368 | infcx.register_region_obligation_with_cause(t_a, r_b, &obligation.cause); | |
94b46f34 | 369 | } |
3dfed10e | 370 | ProcessResult::Changed(vec![]) |
1a4d82fc | 371 | } |
1a4d82fc | 372 | |
487cf647 FG |
373 | ty::PredicateKind::Clause(ty::Clause::Projection(ref data)) => { |
374 | let project_obligation = obligation.with(infcx.tcx, Binder::dummy(*data)); | |
3dfed10e XL |
375 | |
376 | self.process_projection_obligation( | |
136023e0 | 377 | obligation, |
3dfed10e XL |
378 | project_obligation, |
379 | &mut pending_obligation.stalled_on, | |
380 | ) | |
94b46f34 | 381 | } |
1a4d82fc | 382 | |
5869c6ff | 383 | ty::PredicateKind::ObjectSafe(trait_def_id) => { |
9ffffee4 | 384 | if !self.selcx.tcx().check_is_object_safe(trait_def_id) { |
3dfed10e XL |
385 | ProcessResult::Error(CodeSelectionError(Unimplemented)) |
386 | } else { | |
94b46f34 | 387 | ProcessResult::Changed(vec![]) |
ff7c6d11 | 388 | } |
c1a9b12d | 389 | } |
1a4d82fc | 390 | |
5869c6ff | 391 | ty::PredicateKind::ClosureKind(_, closure_substs, kind) => { |
487cf647 | 392 | match self.selcx.infcx.closure_kind(closure_substs) { |
3dfed10e XL |
393 | Some(closure_kind) => { |
394 | if closure_kind.extends(kind) { | |
395 | ProcessResult::Changed(vec![]) | |
396 | } else { | |
397 | ProcessResult::Error(CodeSelectionError(Unimplemented)) | |
398 | } | |
399 | } | |
400 | None => ProcessResult::Unchanged, | |
94b46f34 | 401 | } |
1a4d82fc | 402 | } |
1a4d82fc | 403 | |
5869c6ff | 404 | ty::PredicateKind::WellFormed(arg) => { |
3dfed10e | 405 | match wf::obligations( |
487cf647 | 406 | self.selcx.infcx, |
3dfed10e XL |
407 | obligation.param_env, |
408 | obligation.cause.body_id, | |
29967ef6 | 409 | obligation.recursion_depth + 1, |
3dfed10e XL |
410 | arg, |
411 | obligation.cause.span, | |
412 | ) { | |
413 | None => { | |
414 | pending_obligation.stalled_on = | |
415 | vec![TyOrConstInferVar::maybe_from_generic_arg(arg).unwrap()]; | |
416 | ProcessResult::Unchanged | |
94b46f34 | 417 | } |
3dfed10e | 418 | Some(os) => ProcessResult::Changed(mk_pending(os)), |
94b46f34 | 419 | } |
a7813a04 | 420 | } |
a7813a04 | 421 | |
5869c6ff | 422 | ty::PredicateKind::Subtype(subtype) => { |
487cf647 | 423 | match self.selcx.infcx.subtype_predicate( |
3dfed10e XL |
424 | &obligation.cause, |
425 | obligation.param_env, | |
426 | Binder::dummy(subtype), | |
427 | ) { | |
f2b60f7d | 428 | Err((a, b)) => { |
3dfed10e | 429 | // None means that both are unresolved. |
f2b60f7d FG |
430 | pending_obligation.stalled_on = |
431 | vec![TyOrConstInferVar::Ty(a), TyOrConstInferVar::Ty(b)]; | |
3dfed10e XL |
432 | ProcessResult::Unchanged |
433 | } | |
f2b60f7d FG |
434 | Ok(Ok(ok)) => ProcessResult::Changed(mk_pending(ok.obligations)), |
435 | Ok(Err(err)) => { | |
3dfed10e XL |
436 | let expected_found = |
437 | ExpectedFound::new(subtype.a_is_expected, subtype.a, subtype.b); | |
438 | ProcessResult::Error(FulfillmentErrorCode::CodeSubtypeError( | |
439 | expected_found, | |
440 | err, | |
441 | )) | |
442 | } | |
94b46f34 | 443 | } |
e9174d1e | 444 | } |
cc61c64b | 445 | |
94222f64 | 446 | ty::PredicateKind::Coerce(coerce) => { |
487cf647 | 447 | match self.selcx.infcx.coerce_predicate( |
94222f64 XL |
448 | &obligation.cause, |
449 | obligation.param_env, | |
450 | Binder::dummy(coerce), | |
451 | ) { | |
f2b60f7d | 452 | Err((a, b)) => { |
94222f64 | 453 | // None means that both are unresolved. |
f2b60f7d FG |
454 | pending_obligation.stalled_on = |
455 | vec![TyOrConstInferVar::Ty(a), TyOrConstInferVar::Ty(b)]; | |
94222f64 XL |
456 | ProcessResult::Unchanged |
457 | } | |
f2b60f7d FG |
458 | Ok(Ok(ok)) => ProcessResult::Changed(mk_pending(ok.obligations)), |
459 | Ok(Err(err)) => { | |
94222f64 XL |
460 | let expected_found = ExpectedFound::new(false, coerce.a, coerce.b); |
461 | ProcessResult::Error(FulfillmentErrorCode::CodeSubtypeError( | |
462 | expected_found, | |
463 | err, | |
464 | )) | |
465 | } | |
466 | } | |
467 | } | |
468 | ||
469 | ty::PredicateKind::ConstEvaluatable(uv) => { | |
1b1a35ee | 470 | match const_evaluatable::is_const_evaluatable( |
487cf647 | 471 | self.selcx.infcx, |
94222f64 | 472 | uv, |
1b1a35ee XL |
473 | obligation.param_env, |
474 | obligation.cause.span, | |
3dfed10e | 475 | ) { |
1b1a35ee | 476 | Ok(()) => ProcessResult::Changed(vec![]), |
cdc7bbd5 | 477 | Err(NotConstEvaluatable::MentionsInfer) => { |
6a06907d XL |
478 | pending_obligation.stalled_on.clear(); |
479 | pending_obligation.stalled_on.extend( | |
2b03887a | 480 | uv.walk().filter_map(TyOrConstInferVar::maybe_from_generic_arg), |
6a06907d | 481 | ); |
1b1a35ee XL |
482 | ProcessResult::Unchanged |
483 | } | |
cdc7bbd5 XL |
484 | Err( |
485 | e @ NotConstEvaluatable::MentionsParam | |
486 | | e @ NotConstEvaluatable::Error(_), | |
487 | ) => ProcessResult::Error(CodeSelectionError( | |
488 | SelectionError::NotConstEvaluatable(e), | |
489 | )), | |
94b46f34 | 490 | } |
cc61c64b | 491 | } |
ea8adc8c | 492 | |
5869c6ff | 493 | ty::PredicateKind::ConstEquate(c1, c2) => { |
487cf647 | 494 | let tcx = self.selcx.tcx(); |
2b03887a | 495 | assert!( |
487cf647 | 496 | tcx.features().generic_const_exprs, |
2b03887a FG |
497 | "`ConstEquate` without a feature gate: {c1:?} {c2:?}", |
498 | ); | |
2b03887a FG |
499 | // FIXME: we probably should only try to unify abstract constants |
500 | // if the constants depend on generic parameters. | |
501 | // | |
502 | // Let's just see where this breaks :shrug: | |
2b03887a | 503 | { |
487cf647 FG |
504 | let c1 = tcx.expand_abstract_consts(c1); |
505 | let c2 = tcx.expand_abstract_consts(c2); | |
506 | debug!("equating consts:\nc1= {:?}\nc2= {:?}", c1, c2); | |
507 | ||
508 | use rustc_hir::def::DefKind; | |
509 | use ty::ConstKind::Unevaluated; | |
510 | match (c1.kind(), c2.kind()) { | |
511 | (Unevaluated(a), Unevaluated(b)) | |
512 | if a.def.did == b.def.did | |
513 | && tcx.def_kind(a.def.did) == DefKind::AssocConst => | |
514 | { | |
515 | if let Ok(new_obligations) = infcx | |
516 | .at(&obligation.cause, obligation.param_env) | |
517 | .trace(c1, c2) | |
518 | .eq(a.substs, b.substs) | |
519 | { | |
520 | return ProcessResult::Changed(mk_pending( | |
521 | new_obligations.into_obligations(), | |
522 | )); | |
523 | } | |
524 | } | |
525 | (_, Unevaluated(_)) | (Unevaluated(_), _) => (), | |
526 | (_, _) => { | |
527 | if let Ok(new_obligations) = | |
528 | infcx.at(&obligation.cause, obligation.param_env).eq(c1, c2) | |
529 | { | |
530 | return ProcessResult::Changed(mk_pending( | |
531 | new_obligations.into_obligations(), | |
532 | )); | |
533 | } | |
534 | } | |
1b1a35ee XL |
535 | } |
536 | } | |
3dfed10e XL |
537 | |
538 | let stalled_on = &mut pending_obligation.stalled_on; | |
539 | ||
5099ac24 | 540 | let mut evaluate = |c: Const<'tcx>| { |
923072b8 | 541 | if let ty::ConstKind::Unevaluated(unevaluated) = c.kind() { |
487cf647 | 542 | match self.selcx.infcx.try_const_eval_resolve( |
3dfed10e | 543 | obligation.param_env, |
cdc7bbd5 | 544 | unevaluated, |
923072b8 | 545 | c.ty(), |
3dfed10e XL |
546 | Some(obligation.cause.span), |
547 | ) { | |
923072b8 FG |
548 | Ok(val) => Ok(val), |
549 | Err(e) => match e { | |
550 | ErrorHandled::TooGeneric => { | |
551 | stalled_on.extend( | |
552 | unevaluated.substs.iter().filter_map( | |
553 | TyOrConstInferVar::maybe_from_generic_arg, | |
554 | ), | |
555 | ); | |
556 | Err(ErrorHandled::TooGeneric) | |
557 | } | |
558 | _ => Err(e), | |
559 | }, | |
f9f354fc | 560 | } |
3dfed10e XL |
561 | } else { |
562 | Ok(c) | |
f9f354fc | 563 | } |
3dfed10e XL |
564 | }; |
565 | ||
566 | match (evaluate(c1), evaluate(c2)) { | |
567 | (Ok(c1), Ok(c2)) => { | |
568 | match self | |
569 | .selcx | |
487cf647 | 570 | .infcx |
3dfed10e XL |
571 | .at(&obligation.cause, obligation.param_env) |
572 | .eq(c1, c2) | |
573 | { | |
487cf647 FG |
574 | Ok(inf_ok) => { |
575 | ProcessResult::Changed(mk_pending(inf_ok.into_obligations())) | |
576 | } | |
3dfed10e XL |
577 | Err(err) => ProcessResult::Error( |
578 | FulfillmentErrorCode::CodeConstEquateError( | |
579 | ExpectedFound::new(true, c1, c2), | |
580 | err, | |
581 | ), | |
582 | ), | |
f9f354fc XL |
583 | } |
584 | } | |
5e7ed085 FG |
585 | (Err(ErrorHandled::Reported(reported)), _) |
586 | | (_, Err(ErrorHandled::Reported(reported))) => ProcessResult::Error( | |
cdc7bbd5 | 587 | CodeSelectionError(SelectionError::NotConstEvaluatable( |
5e7ed085 | 588 | NotConstEvaluatable::Error(reported), |
cdc7bbd5 XL |
589 | )), |
590 | ), | |
3dfed10e | 591 | (Err(ErrorHandled::TooGeneric), _) | (_, Err(ErrorHandled::TooGeneric)) => { |
2b03887a | 592 | if c1.has_non_region_infer() || c2.has_non_region_infer() { |
17df50a5 XL |
593 | ProcessResult::Unchanged |
594 | } else { | |
595 | // Two different constants using generic parameters ~> error. | |
596 | let expected_found = ExpectedFound::new(true, c1, c2); | |
597 | ProcessResult::Error(FulfillmentErrorCode::CodeConstEquateError( | |
598 | expected_found, | |
599 | TypeError::ConstMismatch(expected_found), | |
600 | )) | |
601 | } | |
3dfed10e | 602 | } |
f9f354fc XL |
603 | } |
604 | } | |
487cf647 | 605 | ty::PredicateKind::Ambiguous => ProcessResult::Unchanged, |
5869c6ff | 606 | ty::PredicateKind::TypeWellFormedFromEnv(..) => { |
1b1a35ee XL |
607 | bug!("TypeWellFormedFromEnv is only used for Chalk") |
608 | } | |
9ffffee4 FG |
609 | ty::PredicateKind::AliasEq(..) => { |
610 | bug!("AliasEq is only used for new solver") | |
611 | } | |
612 | ty::PredicateKind::Clause(ty::Clause::ConstArgHasType(ct, ty)) => { | |
613 | match self | |
614 | .selcx | |
615 | .infcx | |
616 | .at(&obligation.cause, obligation.param_env) | |
617 | .eq(ct.ty(), ty) | |
618 | { | |
619 | Ok(inf_ok) => ProcessResult::Changed(mk_pending(inf_ok.into_obligations())), | |
620 | Err(_) => ProcessResult::Error(FulfillmentErrorCode::CodeSelectionError( | |
621 | SelectionError::Unimplemented, | |
622 | )), | |
623 | } | |
624 | } | |
3dfed10e | 625 | }, |
ea8adc8c | 626 | } |
1a4d82fc | 627 | } |
94b46f34 | 628 | |
f2b60f7d | 629 | #[inline(never)] |
923072b8 FG |
630 | fn process_backedge<'c, I>( |
631 | &mut self, | |
632 | cycle: I, | |
633 | _marker: PhantomData<&'c PendingPredicateObligation<'tcx>>, | |
2b03887a FG |
634 | ) -> Result<(), FulfillmentErrorCode<'tcx>> |
635 | where | |
923072b8 FG |
636 | I: Clone + Iterator<Item = &'c PendingPredicateObligation<'tcx>>, |
637 | { | |
638 | if self.selcx.coinductive_match(cycle.clone().map(|s| s.obligation.predicate)) { | |
639 | debug!("process_child_obligations: coinductive match"); | |
2b03887a | 640 | Ok(()) |
923072b8 FG |
641 | } else { |
642 | let cycle: Vec<_> = cycle.map(|c| c.obligation.clone()).collect(); | |
2b03887a | 643 | Err(FulfillmentErrorCode::CodeCycle(cycle)) |
923072b8 FG |
644 | } |
645 | } | |
646 | } | |
647 | ||
2b03887a | 648 | impl<'a, 'tcx> FulfillProcessor<'a, 'tcx> { |
29967ef6 | 649 | #[instrument(level = "debug", skip(self, obligation, stalled_on))] |
3dfed10e XL |
650 | fn process_trait_obligation( |
651 | &mut self, | |
652 | obligation: &PredicateObligation<'tcx>, | |
653 | trait_obligation: TraitObligation<'tcx>, | |
654 | stalled_on: &mut Vec<TyOrConstInferVar<'tcx>>, | |
655 | ) -> ProcessResult<PendingPredicateObligation<'tcx>, FulfillmentErrorCode<'tcx>> { | |
487cf647 | 656 | let infcx = self.selcx.infcx; |
5099ac24 | 657 | if obligation.predicate.is_global() { |
3dfed10e XL |
658 | // no type variables present, can use evaluation for better caching. |
659 | // FIXME: consider caching errors too. | |
a2a8927a | 660 | if infcx.predicate_must_hold_considering_regions(obligation) { |
3dfed10e | 661 | debug!( |
29967ef6 XL |
662 | "selecting trait at depth {} evaluated to holds", |
663 | obligation.recursion_depth | |
3dfed10e XL |
664 | ); |
665 | return ProcessResult::Changed(vec![]); | |
666 | } | |
667 | } | |
668 | ||
669 | match self.selcx.select(&trait_obligation) { | |
670 | Ok(Some(impl_source)) => { | |
29967ef6 | 671 | debug!("selecting trait at depth {} yielded Ok(Some)", obligation.recursion_depth); |
3dfed10e XL |
672 | ProcessResult::Changed(mk_pending(impl_source.nested_obligations())) |
673 | } | |
674 | Ok(None) => { | |
29967ef6 | 675 | debug!("selecting trait at depth {} yielded Ok(None)", obligation.recursion_depth); |
3dfed10e XL |
676 | |
677 | // This is a bit subtle: for the most part, the | |
678 | // only reason we can fail to make progress on | |
679 | // trait selection is because we don't have enough | |
680 | // information about the types in the trait. | |
6a06907d XL |
681 | stalled_on.clear(); |
682 | stalled_on.extend(substs_infer_vars( | |
2b03887a | 683 | &self.selcx, |
6a06907d XL |
684 | trait_obligation.predicate.map_bound(|pred| pred.trait_ref.substs), |
685 | )); | |
3dfed10e XL |
686 | |
687 | debug!( | |
688 | "process_predicate: pending obligation {:?} now stalled on {:?}", | |
fc512014 | 689 | infcx.resolve_vars_if_possible(obligation.clone()), |
3dfed10e XL |
690 | stalled_on |
691 | ); | |
692 | ||
693 | ProcessResult::Unchanged | |
694 | } | |
695 | Err(selection_err) => { | |
6a06907d | 696 | debug!("selecting trait at depth {} yielded Err", obligation.recursion_depth); |
3dfed10e XL |
697 | |
698 | ProcessResult::Error(CodeSelectionError(selection_err)) | |
699 | } | |
700 | } | |
701 | } | |
702 | ||
703 | fn process_projection_obligation( | |
704 | &mut self, | |
136023e0 | 705 | obligation: &PredicateObligation<'tcx>, |
3dfed10e XL |
706 | project_obligation: PolyProjectionObligation<'tcx>, |
707 | stalled_on: &mut Vec<TyOrConstInferVar<'tcx>>, | |
708 | ) -> ProcessResult<PendingPredicateObligation<'tcx>, FulfillmentErrorCode<'tcx>> { | |
709 | let tcx = self.selcx.tcx(); | |
136023e0 | 710 | |
5099ac24 | 711 | if obligation.predicate.is_global() { |
136023e0 XL |
712 | // no type variables present, can use evaluation for better caching. |
713 | // FIXME: consider caching errors too. | |
487cf647 | 714 | if self.selcx.infcx.predicate_must_hold_considering_regions(obligation) { |
a2a8927a XL |
715 | if let Some(key) = ProjectionCacheKey::from_poly_projection_predicate( |
716 | &mut self.selcx, | |
717 | project_obligation.predicate, | |
718 | ) { | |
719 | // If `predicate_must_hold_considering_regions` succeeds, then we've | |
720 | // evaluated all sub-obligations. We can therefore mark the 'root' | |
721 | // obligation as complete, and skip evaluating sub-obligations. | |
722 | self.selcx | |
487cf647 | 723 | .infcx |
a2a8927a XL |
724 | .inner |
725 | .borrow_mut() | |
726 | .projection_cache() | |
727 | .complete(key, EvaluationResult::EvaluatedToOk); | |
728 | } | |
136023e0 XL |
729 | return ProcessResult::Changed(vec![]); |
730 | } else { | |
064997fb | 731 | debug!("Does NOT hold: {:?}", obligation); |
136023e0 XL |
732 | } |
733 | } | |
734 | ||
2b03887a | 735 | match project::poly_project_and_unify_type(&mut self.selcx, &project_obligation) { |
5e7ed085 FG |
736 | ProjectAndUnifyResult::Holds(os) => ProcessResult::Changed(mk_pending(os)), |
737 | ProjectAndUnifyResult::FailedNormalization => { | |
6a06907d XL |
738 | stalled_on.clear(); |
739 | stalled_on.extend(substs_infer_vars( | |
2b03887a | 740 | &self.selcx, |
6a06907d XL |
741 | project_obligation.predicate.map_bound(|pred| pred.projection_ty.substs), |
742 | )); | |
3dfed10e XL |
743 | ProcessResult::Unchanged |
744 | } | |
745 | // Let the caller handle the recursion | |
5e7ed085 | 746 | ProjectAndUnifyResult::Recursive => ProcessResult::Changed(mk_pending(vec![ |
487cf647 | 747 | project_obligation.with(tcx, project_obligation.predicate), |
3dfed10e | 748 | ])), |
5e7ed085 FG |
749 | ProjectAndUnifyResult::MismatchedProjectionTypes(e) => { |
750 | ProcessResult::Error(CodeProjectionError(e)) | |
751 | } | |
3dfed10e XL |
752 | } |
753 | } | |
754 | } | |
755 | ||
6a06907d XL |
756 | /// Returns the set of inference variables contained in `substs`. |
757 | fn substs_infer_vars<'a, 'tcx>( | |
2b03887a | 758 | selcx: &SelectionContext<'a, 'tcx>, |
cdc7bbd5 | 759 | substs: ty::Binder<'tcx, SubstsRef<'tcx>>, |
6a06907d | 760 | ) -> impl Iterator<Item = TyOrConstInferVar<'tcx>> { |
ba9703b0 | 761 | selcx |
487cf647 | 762 | .infcx |
6a06907d XL |
763 | .resolve_vars_if_possible(substs) |
764 | .skip_binder() // ok because this check doesn't care about regions | |
ba9703b0 | 765 | .iter() |
2b03887a | 766 | .filter(|arg| arg.has_non_region_infer()) |
5099ac24 FG |
767 | .flat_map(|arg| { |
768 | let mut walker = arg.walk(); | |
6a06907d | 769 | while let Some(c) = walker.next() { |
2b03887a | 770 | if !c.has_non_region_infer() { |
6a06907d XL |
771 | walker.visited.remove(&c); |
772 | walker.skip_current_subtree(); | |
773 | } | |
774 | } | |
775 | walker.visited.into_iter() | |
776 | }) | |
ba9703b0 | 777 | .filter_map(TyOrConstInferVar::maybe_from_generic_arg) |
1a4d82fc JJ |
778 | } |
779 | ||
7453a54e | 780 | fn to_fulfillment_error<'tcx>( |
dfeec247 XL |
781 | error: Error<PendingPredicateObligation<'tcx>, FulfillmentErrorCode<'tcx>>, |
782 | ) -> FulfillmentError<'tcx> { | |
136023e0 XL |
783 | let mut iter = error.backtrace.into_iter(); |
784 | let obligation = iter.next().unwrap().obligation; | |
785 | // The root obligation is the last item in the backtrace - if there's only | |
786 | // one item, then it's the same as the main obligation | |
787 | let root_obligation = iter.next_back().map_or_else(|| obligation.clone(), |e| e.obligation); | |
788 | FulfillmentError::new(obligation, error.error, root_obligation) | |
7453a54e | 789 | } |