]>
Commit | Line | Data |
---|---|---|
ba9703b0 | 1 | use crate::infer::{InferCtxt, TyOrConstInferVar}; |
c295e0f8 | 2 | use rustc_data_structures::fx::FxHashMap; |
dfeec247 | 3 | use rustc_data_structures::obligation_forest::ProcessResult; |
29967ef6 | 4 | use rustc_data_structures::obligation_forest::{Error, ForestObligation, Outcome}; |
a1dfa0c6 | 5 | use rustc_data_structures::obligation_forest::{ObligationForest, ObligationProcessor}; |
a2a8927a | 6 | use rustc_infer::traits::ProjectionCacheKey; |
cdc7bbd5 | 7 | use rustc_infer::traits::{SelectionError, TraitEngine, TraitEngineExt as _, TraitObligation}; |
f9f354fc | 8 | use rustc_middle::mir::interpret::ErrorHandled; |
c295e0f8 | 9 | use rustc_middle::thir::abstract_const::NotConstEvaluatable; |
17df50a5 | 10 | use rustc_middle::ty::error::{ExpectedFound, TypeError}; |
6a06907d | 11 | use rustc_middle::ty::subst::SubstsRef; |
3dfed10e XL |
12 | use rustc_middle::ty::ToPredicate; |
13 | use rustc_middle::ty::{self, Binder, Const, Ty, TypeFoldable}; | |
a7813a04 | 14 | use std::marker::PhantomData; |
1a4d82fc | 15 | |
1b1a35ee | 16 | use super::const_evaluatable; |
5e7ed085 | 17 | use super::project::{self, ProjectAndUnifyResult}; |
dfeec247 XL |
18 | use super::select::SelectionContext; |
19 | use super::wf; | |
1a4d82fc JJ |
20 | use super::CodeAmbiguity; |
21 | use super::CodeProjectionError; | |
22 | use super::CodeSelectionError; | |
a2a8927a | 23 | use super::EvaluationResult; |
cdc7bbd5 | 24 | use super::Unimplemented; |
8bb4bdeb | 25 | use super::{FulfillmentError, FulfillmentErrorCode}; |
0731742a | 26 | use super::{ObligationCause, PredicateObligation}; |
a7813a04 | 27 | |
ba9703b0 | 28 | use crate::traits::error_reporting::InferCtxtExt as _; |
3dfed10e | 29 | use crate::traits::project::PolyProjectionObligation; |
a2a8927a | 30 | use crate::traits::project::ProjectionCacheKeyExt as _; |
ba9703b0 XL |
31 | use crate::traits::query::evaluate_obligation::InferCtxtExt as _; |
32 | ||
a7813a04 | 33 | impl<'tcx> ForestObligation for PendingPredicateObligation<'tcx> { |
74b04a01 XL |
34 | /// Note that we include both the `ParamEnv` and the `Predicate`, |
35 | /// as the `ParamEnv` can influence whether fulfillment succeeds | |
36 | /// or fails. | |
37 | type CacheKey = ty::ParamEnvAnd<'tcx, ty::Predicate<'tcx>>; | |
a7813a04 | 38 | |
74b04a01 XL |
39 | fn as_cache_key(&self) -> Self::CacheKey { |
40 | self.obligation.param_env.and(self.obligation.predicate) | |
dfeec247 | 41 | } |
a7813a04 | 42 | } |
1a4d82fc | 43 | |
9fa01778 | 44 | /// The fulfillment context is used to drive trait resolution. It |
1a4d82fc JJ |
45 | /// consists of a list of obligations that must be (eventually) |
46 | /// satisfied. The job is to track which are satisfied, which yielded | |
47 | /// errors, and which are still pending. At any point, users can call | |
3b2f2976 | 48 | /// `select_where_possible`, and the fulfillment context will try to do |
1a4d82fc JJ |
49 | /// selection, retaining only those obligations that remain |
50 | /// ambiguous. This may be helpful in pushing type inference | |
51 | /// along. Once all type inference constraints have been generated, the | |
52 | /// method `select_all_or_error` can be used to report any remaining | |
53 | /// ambiguous cases as errors. | |
54 | pub struct FulfillmentContext<'tcx> { | |
1a4d82fc JJ |
55 | // A list of all obligations that have been registered with this |
56 | // fulfillment context. | |
a7813a04 | 57 | predicates: ObligationForest<PendingPredicateObligation<'tcx>>, |
c295e0f8 XL |
58 | |
59 | relationships: FxHashMap<ty::TyVid, ty::FoundRelationships>, | |
60 | ||
ff7c6d11 XL |
61 | // Should this fulfillment context register type-lives-for-region |
62 | // obligations on its parent infcx? In some cases, region | |
63 | // obligations are either already known to hold (normalization) or | |
5e7ed085 | 64 | // hopefully verified elsewhere (type-impls-bound), and therefore |
ff7c6d11 XL |
65 | // should not be checked. |
66 | // | |
67 | // Note that if we are normalizing a type that we already | |
68 | // know is well-formed, there should be no harm setting this | |
69 | // to true - all the region variables should be determinable | |
70 | // using the RFC 447 rules, which don't depend on | |
71 | // type-lives-for-region constraints, and because the type | |
72 | // is well-formed, the constraints should hold. | |
73 | register_region_obligations: bool, | |
0731742a XL |
74 | // Is it OK to register obligations into this infcx inside |
75 | // an infcx snapshot? | |
76 | // | |
77 | // The "primary fulfillment" in many cases in typeck lives | |
78 | // outside of any snapshot, so any use of it inside a snapshot | |
79 | // will lead to trouble and therefore is checked against, but | |
80 | // other fulfillment contexts sometimes do live inside of | |
81 | // a snapshot (they don't *straddle* a snapshot, so there | |
82 | // is no trouble there). | |
dfeec247 | 83 | usable_in_snapshot: bool, |
1a4d82fc JJ |
84 | } |
85 | ||
7453a54e SL |
86 | #[derive(Clone, Debug)] |
87 | pub struct PendingPredicateObligation<'tcx> { | |
88 | pub obligation: PredicateObligation<'tcx>, | |
f9f354fc XL |
89 | // This is far more often read than modified, meaning that we |
90 | // should mostly optimize for reading speed, while modifying is not as relevant. | |
91 | // | |
92 | // For whatever reason using a boxed slice is slower than using a `Vec` here. | |
ba9703b0 | 93 | pub stalled_on: Vec<TyOrConstInferVar<'tcx>>, |
7453a54e SL |
94 | } |
95 | ||
e1599b0c | 96 | // `PendingPredicateObligation` is used a lot. Make sure it doesn't unintentionally get bigger. |
6a06907d | 97 | #[cfg(all(target_arch = "x86_64", target_pointer_width = "64"))] |
a2a8927a | 98 | static_assert_size!(PendingPredicateObligation<'_>, 72); |
e1599b0c | 99 | |
dc9dc135 | 100 | impl<'a, 'tcx> FulfillmentContext<'tcx> { |
62682a34 | 101 | /// Creates a new fulfillment context. |
7453a54e | 102 | pub fn new() -> FulfillmentContext<'tcx> { |
1a4d82fc | 103 | FulfillmentContext { |
7453a54e | 104 | predicates: ObligationForest::new(), |
c295e0f8 | 105 | relationships: FxHashMap::default(), |
0731742a XL |
106 | register_region_obligations: true, |
107 | usable_in_snapshot: false, | |
108 | } | |
109 | } | |
110 | ||
111 | pub fn new_in_snapshot() -> FulfillmentContext<'tcx> { | |
112 | FulfillmentContext { | |
113 | predicates: ObligationForest::new(), | |
c295e0f8 | 114 | relationships: FxHashMap::default(), |
0731742a XL |
115 | register_region_obligations: true, |
116 | usable_in_snapshot: true, | |
ff7c6d11 XL |
117 | } |
118 | } | |
119 | ||
120 | pub fn new_ignoring_regions() -> FulfillmentContext<'tcx> { | |
121 | FulfillmentContext { | |
122 | predicates: ObligationForest::new(), | |
c295e0f8 | 123 | relationships: FxHashMap::default(), |
0731742a | 124 | register_region_obligations: false, |
dfeec247 | 125 | usable_in_snapshot: false, |
1a4d82fc JJ |
126 | } |
127 | } | |
128 | ||
8faf50e0 | 129 | /// Attempts to select obligations using `selcx`. |
3c0e092e | 130 | fn select(&mut self, selcx: &mut SelectionContext<'a, 'tcx>) -> Vec<FulfillmentError<'tcx>> { |
29967ef6 XL |
131 | let span = debug_span!("select", obligation_forest_size = ?self.predicates.len()); |
132 | let _enter = span.enter(); | |
0531ce1d XL |
133 | |
134 | let mut errors = Vec::new(); | |
135 | ||
923072b8 FG |
136 | // Process pending obligations. |
137 | let outcome: Outcome<_, _> = self.predicates.process_obligations(&mut FulfillProcessor { | |
138 | selcx, | |
139 | register_region_obligations: self.register_region_obligations, | |
140 | }); | |
0531ce1d | 141 | |
923072b8 FG |
142 | // FIXME: if we kept the original cache key, we could mark projection |
143 | // obligations as complete for the projection cache here. | |
0531ce1d | 144 | |
923072b8 | 145 | errors.extend(outcome.errors.into_iter().map(to_fulfillment_error)); |
0531ce1d | 146 | |
dfeec247 XL |
147 | debug!( |
148 | "select({} predicates remaining, {} errors) done", | |
149 | self.predicates.len(), | |
150 | errors.len() | |
151 | ); | |
0531ce1d | 152 | |
3c0e092e | 153 | errors |
0531ce1d XL |
154 | } |
155 | } | |
156 | ||
157 | impl<'tcx> TraitEngine<'tcx> for FulfillmentContext<'tcx> { | |
1a4d82fc JJ |
158 | /// "Normalize" a projection type `<SomeType as SomeTrait>::X` by |
159 | /// creating a fresh type variable `$0` as well as a projection | |
160 | /// predicate `<SomeType as SomeTrait>::X == $0`. When the | |
161 | /// inference engine runs, it will attempt to find an impl of | |
9fa01778 | 162 | /// `SomeTrait` or a where-clause that lets us unify `$0` with |
1a4d82fc JJ |
163 | /// something concrete. If this fails, we'll unify `$0` with |
164 | /// `projection_ty` again. | |
136023e0 | 165 | #[tracing::instrument(level = "debug", skip(self, infcx, param_env, cause))] |
dc9dc135 XL |
166 | fn normalize_projection_type( |
167 | &mut self, | |
168 | infcx: &InferCtxt<'_, 'tcx>, | |
169 | param_env: ty::ParamEnv<'tcx>, | |
170 | projection_ty: ty::ProjectionTy<'tcx>, | |
171 | cause: ObligationCause<'tcx>, | |
172 | ) -> Ty<'tcx> { | |
a1dfa0c6 | 173 | debug_assert!(!projection_ty.has_escaping_bound_vars()); |
1a4d82fc JJ |
174 | |
175 | // FIXME(#20304) -- cache | |
176 | ||
c1a9b12d | 177 | let mut selcx = SelectionContext::new(infcx); |
94b46f34 | 178 | let mut obligations = vec![]; |
dfeec247 XL |
179 | let normalized_ty = project::normalize_projection_type( |
180 | &mut selcx, | |
181 | param_env, | |
182 | projection_ty, | |
183 | cause, | |
184 | 0, | |
185 | &mut obligations, | |
186 | ); | |
94b46f34 XL |
187 | self.register_predicate_obligations(infcx, obligations); |
188 | ||
29967ef6 | 189 | debug!(?normalized_ty); |
94b46f34 | 190 | |
5099ac24 | 191 | normalized_ty.ty().unwrap() |
1a4d82fc JJ |
192 | } |
193 | ||
dc9dc135 XL |
194 | fn register_predicate_obligation( |
195 | &mut self, | |
196 | infcx: &InferCtxt<'_, 'tcx>, | |
197 | obligation: PredicateObligation<'tcx>, | |
198 | ) { | |
1a4d82fc JJ |
199 | // this helps to reduce duplicate errors, as well as making |
200 | // debug output much nicer to read and so on. | |
fc512014 | 201 | let obligation = infcx.resolve_vars_if_possible(obligation); |
1a4d82fc | 202 | |
29967ef6 | 203 | debug!(?obligation, "register_predicate_obligation"); |
3157f602 | 204 | |
0731742a | 205 | assert!(!infcx.is_in_snapshot() || self.usable_in_snapshot); |
3157f602 | 206 | |
c295e0f8 XL |
207 | super::relationships::update(self, infcx, &obligation); |
208 | ||
dfeec247 XL |
209 | self.predicates |
210 | .register_obligation(PendingPredicateObligation { obligation, stalled_on: vec![] }); | |
a7813a04 XL |
211 | } |
212 | ||
3c0e092e XL |
213 | fn select_all_or_error(&mut self, infcx: &InferCtxt<'_, 'tcx>) -> Vec<FulfillmentError<'tcx>> { |
214 | { | |
215 | let errors = self.select_where_possible(infcx); | |
216 | if !errors.is_empty() { | |
217 | return errors; | |
218 | } | |
219 | } | |
220 | ||
221 | self.predicates.to_errors(CodeAmbiguity).into_iter().map(to_fulfillment_error).collect() | |
1a4d82fc JJ |
222 | } |
223 | ||
dc9dc135 XL |
224 | fn select_where_possible( |
225 | &mut self, | |
226 | infcx: &InferCtxt<'_, 'tcx>, | |
3c0e092e | 227 | ) -> Vec<FulfillmentError<'tcx>> { |
c1a9b12d | 228 | let mut selcx = SelectionContext::new(infcx); |
7453a54e | 229 | self.select(&mut selcx) |
1a4d82fc JJ |
230 | } |
231 | ||
94b46f34 XL |
232 | fn pending_obligations(&self) -> Vec<PredicateObligation<'tcx>> { |
233 | self.predicates.map_pending_obligations(|o| o.obligation.clone()) | |
1a4d82fc | 234 | } |
c295e0f8 XL |
235 | |
236 | fn relationships(&mut self) -> &mut FxHashMap<ty::TyVid, ty::FoundRelationships> { | |
237 | &mut self.relationships | |
238 | } | |
1a4d82fc JJ |
239 | } |
240 | ||
dc9dc135 XL |
241 | struct FulfillProcessor<'a, 'b, 'tcx> { |
242 | selcx: &'a mut SelectionContext<'b, 'tcx>, | |
243 | register_region_obligations: bool, | |
54a0048b SL |
244 | } |
245 | ||
a2a8927a | 246 | fn mk_pending(os: Vec<PredicateObligation<'_>>) -> Vec<PendingPredicateObligation<'_>> { |
dfeec247 XL |
247 | os.into_iter() |
248 | .map(|o| PendingPredicateObligation { obligation: o, stalled_on: vec![] }) | |
249 | .collect() | |
94b46f34 XL |
250 | } |
251 | ||
dc9dc135 | 252 | impl<'a, 'b, 'tcx> ObligationProcessor for FulfillProcessor<'a, 'b, 'tcx> { |
a7813a04 XL |
253 | type Obligation = PendingPredicateObligation<'tcx>; |
254 | type Error = FulfillmentErrorCode<'tcx>; | |
7453a54e | 255 | |
923072b8 | 256 | /// Identifies whether a predicate obligation needs processing. |
94b46f34 XL |
257 | /// |
258 | /// This is always inlined, despite its size, because it has a single | |
259 | /// callsite and it is called *very* frequently. | |
260 | #[inline(always)] | |
923072b8 | 261 | fn needs_process_obligation(&self, pending_obligation: &Self::Obligation) -> bool { |
e74abb32 XL |
262 | // If we were stalled on some unresolved variables, first check whether |
263 | // any of them have been resolved; if not, don't bother doing more work | |
264 | // yet. | |
923072b8 | 265 | match pending_obligation.stalled_on.len() { |
e74abb32 XL |
266 | // Match arms are in order of frequency, which matters because this |
267 | // code is so hot. 1 and 0 dominate; 2+ is fairly rare. | |
268 | 1 => { | |
ba9703b0 XL |
269 | let infer_var = pending_obligation.stalled_on[0]; |
270 | self.selcx.infcx().ty_or_const_infer_var_changed(infer_var) | |
e74abb32 XL |
271 | } |
272 | 0 => { | |
273 | // In this case we haven't changed, but wish to make a change. | |
274 | true | |
e1599b0c | 275 | } |
e74abb32 XL |
276 | _ => { |
277 | // This `for` loop was once a call to `all()`, but this lower-level | |
278 | // form was a perf win. See #64545 for details. | |
279 | (|| { | |
ba9703b0 XL |
280 | for &infer_var in &pending_obligation.stalled_on { |
281 | if self.selcx.infcx().ty_or_const_infer_var_changed(infer_var) { | |
e74abb32 XL |
282 | return true; |
283 | } | |
284 | } | |
285 | false | |
286 | })() | |
94b46f34 | 287 | } |
1b1a35ee XL |
288 | } |
289 | } | |
e74abb32 | 290 | |
923072b8 FG |
291 | /// Processes a predicate obligation and returns either: |
292 | /// - `Changed(v)` if the predicate is true, presuming that `v` are also true | |
293 | /// - `Unchanged` if we don't have enough info to be sure | |
294 | /// - `Error(e)` if the predicate does not hold | |
295 | /// | |
296 | /// This is called much less often than `needs_process_obligation`, so we | |
297 | /// never inline it. | |
1b1a35ee | 298 | #[inline(never)] |
923072b8 | 299 | fn process_obligation( |
1b1a35ee XL |
300 | &mut self, |
301 | pending_obligation: &mut PendingPredicateObligation<'tcx>, | |
302 | ) -> ProcessResult<PendingPredicateObligation<'tcx>, FulfillmentErrorCode<'tcx>> { | |
e74abb32 XL |
303 | pending_obligation.stalled_on.truncate(0); |
304 | ||
94b46f34 | 305 | let obligation = &mut pending_obligation.obligation; |
7453a54e | 306 | |
5e7ed085 FG |
307 | debug!(?obligation, "process_obligation pre-resolve"); |
308 | ||
74b04a01 | 309 | if obligation.predicate.has_infer_types_or_consts() { |
94b46f34 | 310 | obligation.predicate = |
fc512014 | 311 | self.selcx.infcx().resolve_vars_if_possible(obligation.predicate); |
7453a54e | 312 | } |
1a4d82fc | 313 | |
923072b8 FG |
314 | let obligation = &pending_obligation.obligation; |
315 | ||
29967ef6 | 316 | debug!(?obligation, ?obligation.cause, "process_obligation"); |
532ac7d7 | 317 | |
f9f354fc XL |
318 | let infcx = self.selcx.infcx(); |
319 | ||
5e7ed085 FG |
320 | if obligation.predicate.has_projections() { |
321 | let mut obligations = Vec::new(); | |
322 | let predicate = crate::traits::project::try_normalize_with_depth_to( | |
323 | self.selcx, | |
324 | obligation.param_env, | |
325 | obligation.cause.clone(), | |
326 | obligation.recursion_depth + 1, | |
327 | obligation.predicate, | |
328 | &mut obligations, | |
329 | ); | |
330 | if predicate != obligation.predicate { | |
331 | obligations.push(obligation.with(predicate)); | |
332 | return ProcessResult::Changed(mk_pending(obligations)); | |
333 | } | |
334 | } | |
5869c6ff XL |
335 | let binder = obligation.predicate.kind(); |
336 | match binder.no_bound_vars() { | |
337 | None => match binder.skip_binder() { | |
3dfed10e XL |
338 | // Evaluation will discard candidates using the leak check. |
339 | // This means we need to pass it the bound version of our | |
340 | // predicate. | |
94222f64 | 341 | ty::PredicateKind::Trait(trait_ref) => { |
29967ef6 | 342 | let trait_obligation = obligation.with(binder.rebind(trait_ref)); |
3dfed10e XL |
343 | |
344 | self.process_trait_obligation( | |
345 | obligation, | |
346 | trait_obligation, | |
347 | &mut pending_obligation.stalled_on, | |
348 | ) | |
3b2f2976 | 349 | } |
5869c6ff | 350 | ty::PredicateKind::Projection(data) => { |
29967ef6 | 351 | let project_obligation = obligation.with(binder.rebind(data)); |
7453a54e | 352 | |
3dfed10e | 353 | self.process_projection_obligation( |
136023e0 | 354 | obligation, |
3dfed10e XL |
355 | project_obligation, |
356 | &mut pending_obligation.stalled_on, | |
357 | ) | |
358 | } | |
5869c6ff XL |
359 | ty::PredicateKind::RegionOutlives(_) |
360 | | ty::PredicateKind::TypeOutlives(_) | |
361 | | ty::PredicateKind::WellFormed(_) | |
362 | | ty::PredicateKind::ObjectSafe(_) | |
363 | | ty::PredicateKind::ClosureKind(..) | |
364 | | ty::PredicateKind::Subtype(_) | |
94222f64 | 365 | | ty::PredicateKind::Coerce(_) |
5869c6ff XL |
366 | | ty::PredicateKind::ConstEvaluatable(..) |
367 | | ty::PredicateKind::ConstEquate(..) => { | |
c295e0f8 XL |
368 | let pred = |
369 | ty::Binder::dummy(infcx.replace_bound_vars_with_placeholders(binder)); | |
3dfed10e XL |
370 | ProcessResult::Changed(mk_pending(vec![ |
371 | obligation.with(pred.to_predicate(self.selcx.tcx())), | |
372 | ])) | |
373 | } | |
5869c6ff | 374 | ty::PredicateKind::TypeWellFormedFromEnv(..) => { |
1b1a35ee XL |
375 | bug!("TypeWellFormedFromEnv is only used for Chalk") |
376 | } | |
3dfed10e | 377 | }, |
5869c6ff | 378 | Some(pred) => match pred { |
94222f64 | 379 | ty::PredicateKind::Trait(data) => { |
fc512014 | 380 | let trait_obligation = obligation.with(Binder::dummy(data)); |
3dfed10e XL |
381 | |
382 | self.process_trait_obligation( | |
383 | obligation, | |
384 | trait_obligation, | |
385 | &mut pending_obligation.stalled_on, | |
386 | ) | |
387 | } | |
94b46f34 | 388 | |
5869c6ff | 389 | ty::PredicateKind::RegionOutlives(data) => { |
3dfed10e XL |
390 | match infcx.region_outlives_predicate(&obligation.cause, Binder::dummy(data)) { |
391 | Ok(()) => ProcessResult::Changed(vec![]), | |
392 | Err(_) => ProcessResult::Error(CodeSelectionError(Unimplemented)), | |
94b46f34 | 393 | } |
3dfed10e | 394 | } |
5bcae85e | 395 | |
5869c6ff | 396 | ty::PredicateKind::TypeOutlives(ty::OutlivesPredicate(t_a, r_b)) => { |
3dfed10e XL |
397 | if self.register_region_obligations { |
398 | self.selcx.infcx().register_region_obligation_with_cause( | |
399 | t_a, | |
400 | r_b, | |
401 | &obligation.cause, | |
402 | ); | |
94b46f34 | 403 | } |
3dfed10e | 404 | ProcessResult::Changed(vec![]) |
1a4d82fc | 405 | } |
1a4d82fc | 406 | |
5869c6ff | 407 | ty::PredicateKind::Projection(ref data) => { |
3dfed10e XL |
408 | let project_obligation = obligation.with(Binder::dummy(*data)); |
409 | ||
410 | self.process_projection_obligation( | |
136023e0 | 411 | obligation, |
3dfed10e XL |
412 | project_obligation, |
413 | &mut pending_obligation.stalled_on, | |
414 | ) | |
94b46f34 | 415 | } |
1a4d82fc | 416 | |
5869c6ff | 417 | ty::PredicateKind::ObjectSafe(trait_def_id) => { |
3dfed10e XL |
418 | if !self.selcx.tcx().is_object_safe(trait_def_id) { |
419 | ProcessResult::Error(CodeSelectionError(Unimplemented)) | |
420 | } else { | |
94b46f34 | 421 | ProcessResult::Changed(vec![]) |
ff7c6d11 | 422 | } |
c1a9b12d | 423 | } |
1a4d82fc | 424 | |
5869c6ff | 425 | ty::PredicateKind::ClosureKind(_, closure_substs, kind) => { |
3dfed10e XL |
426 | match self.selcx.infcx().closure_kind(closure_substs) { |
427 | Some(closure_kind) => { | |
428 | if closure_kind.extends(kind) { | |
429 | ProcessResult::Changed(vec![]) | |
430 | } else { | |
431 | ProcessResult::Error(CodeSelectionError(Unimplemented)) | |
432 | } | |
433 | } | |
434 | None => ProcessResult::Unchanged, | |
94b46f34 | 435 | } |
1a4d82fc | 436 | } |
1a4d82fc | 437 | |
5869c6ff | 438 | ty::PredicateKind::WellFormed(arg) => { |
3dfed10e XL |
439 | match wf::obligations( |
440 | self.selcx.infcx(), | |
441 | obligation.param_env, | |
442 | obligation.cause.body_id, | |
29967ef6 | 443 | obligation.recursion_depth + 1, |
3dfed10e XL |
444 | arg, |
445 | obligation.cause.span, | |
446 | ) { | |
447 | None => { | |
448 | pending_obligation.stalled_on = | |
449 | vec![TyOrConstInferVar::maybe_from_generic_arg(arg).unwrap()]; | |
450 | ProcessResult::Unchanged | |
94b46f34 | 451 | } |
3dfed10e | 452 | Some(os) => ProcessResult::Changed(mk_pending(os)), |
94b46f34 | 453 | } |
a7813a04 | 454 | } |
a7813a04 | 455 | |
5869c6ff | 456 | ty::PredicateKind::Subtype(subtype) => { |
3dfed10e XL |
457 | match self.selcx.infcx().subtype_predicate( |
458 | &obligation.cause, | |
459 | obligation.param_env, | |
460 | Binder::dummy(subtype), | |
461 | ) { | |
462 | None => { | |
463 | // None means that both are unresolved. | |
464 | pending_obligation.stalled_on = vec![ | |
465 | TyOrConstInferVar::maybe_from_ty(subtype.a).unwrap(), | |
466 | TyOrConstInferVar::maybe_from_ty(subtype.b).unwrap(), | |
467 | ]; | |
468 | ProcessResult::Unchanged | |
469 | } | |
470 | Some(Ok(ok)) => ProcessResult::Changed(mk_pending(ok.obligations)), | |
471 | Some(Err(err)) => { | |
472 | let expected_found = | |
473 | ExpectedFound::new(subtype.a_is_expected, subtype.a, subtype.b); | |
474 | ProcessResult::Error(FulfillmentErrorCode::CodeSubtypeError( | |
475 | expected_found, | |
476 | err, | |
477 | )) | |
478 | } | |
94b46f34 | 479 | } |
e9174d1e | 480 | } |
cc61c64b | 481 | |
94222f64 XL |
482 | ty::PredicateKind::Coerce(coerce) => { |
483 | match self.selcx.infcx().coerce_predicate( | |
484 | &obligation.cause, | |
485 | obligation.param_env, | |
486 | Binder::dummy(coerce), | |
487 | ) { | |
488 | None => { | |
489 | // None means that both are unresolved. | |
490 | pending_obligation.stalled_on = vec![ | |
491 | TyOrConstInferVar::maybe_from_ty(coerce.a).unwrap(), | |
492 | TyOrConstInferVar::maybe_from_ty(coerce.b).unwrap(), | |
493 | ]; | |
494 | ProcessResult::Unchanged | |
495 | } | |
496 | Some(Ok(ok)) => ProcessResult::Changed(mk_pending(ok.obligations)), | |
497 | Some(Err(err)) => { | |
498 | let expected_found = ExpectedFound::new(false, coerce.a, coerce.b); | |
499 | ProcessResult::Error(FulfillmentErrorCode::CodeSubtypeError( | |
500 | expected_found, | |
501 | err, | |
502 | )) | |
503 | } | |
504 | } | |
505 | } | |
506 | ||
507 | ty::PredicateKind::ConstEvaluatable(uv) => { | |
1b1a35ee XL |
508 | match const_evaluatable::is_const_evaluatable( |
509 | self.selcx.infcx(), | |
94222f64 | 510 | uv, |
1b1a35ee XL |
511 | obligation.param_env, |
512 | obligation.cause.span, | |
3dfed10e | 513 | ) { |
1b1a35ee | 514 | Ok(()) => ProcessResult::Changed(vec![]), |
cdc7bbd5 | 515 | Err(NotConstEvaluatable::MentionsInfer) => { |
6a06907d XL |
516 | pending_obligation.stalled_on.clear(); |
517 | pending_obligation.stalled_on.extend( | |
5099ac24 | 518 | uv.substs |
94222f64 XL |
519 | .iter() |
520 | .filter_map(TyOrConstInferVar::maybe_from_generic_arg), | |
6a06907d | 521 | ); |
1b1a35ee XL |
522 | ProcessResult::Unchanged |
523 | } | |
cdc7bbd5 XL |
524 | Err( |
525 | e @ NotConstEvaluatable::MentionsParam | |
526 | | e @ NotConstEvaluatable::Error(_), | |
527 | ) => ProcessResult::Error(CodeSelectionError( | |
528 | SelectionError::NotConstEvaluatable(e), | |
529 | )), | |
94b46f34 | 530 | } |
cc61c64b | 531 | } |
ea8adc8c | 532 | |
5869c6ff | 533 | ty::PredicateKind::ConstEquate(c1, c2) => { |
29967ef6 | 534 | debug!(?c1, ?c2, "equating consts"); |
94222f64 XL |
535 | let tcx = self.selcx.tcx(); |
536 | if tcx.features().generic_const_exprs { | |
1b1a35ee XL |
537 | // FIXME: we probably should only try to unify abstract constants |
538 | // if the constants depend on generic parameters. | |
539 | // | |
540 | // Let's just see where this breaks :shrug: | |
cdc7bbd5 | 541 | if let (ty::ConstKind::Unevaluated(a), ty::ConstKind::Unevaluated(b)) = |
923072b8 | 542 | (c1.kind(), c2.kind()) |
1b1a35ee | 543 | { |
5e7ed085 FG |
544 | if infcx.try_unify_abstract_consts( |
545 | a.shrink(), | |
546 | b.shrink(), | |
547 | obligation.param_env, | |
548 | ) { | |
1b1a35ee XL |
549 | return ProcessResult::Changed(vec![]); |
550 | } | |
551 | } | |
552 | } | |
3dfed10e XL |
553 | |
554 | let stalled_on = &mut pending_obligation.stalled_on; | |
555 | ||
5099ac24 | 556 | let mut evaluate = |c: Const<'tcx>| { |
923072b8 FG |
557 | if let ty::ConstKind::Unevaluated(unevaluated) = c.kind() { |
558 | match self.selcx.infcx().try_const_eval_resolve( | |
3dfed10e | 559 | obligation.param_env, |
cdc7bbd5 | 560 | unevaluated, |
923072b8 | 561 | c.ty(), |
3dfed10e XL |
562 | Some(obligation.cause.span), |
563 | ) { | |
923072b8 FG |
564 | Ok(val) => Ok(val), |
565 | Err(e) => match e { | |
566 | ErrorHandled::TooGeneric => { | |
567 | stalled_on.extend( | |
568 | unevaluated.substs.iter().filter_map( | |
569 | TyOrConstInferVar::maybe_from_generic_arg, | |
570 | ), | |
571 | ); | |
572 | Err(ErrorHandled::TooGeneric) | |
573 | } | |
574 | _ => Err(e), | |
575 | }, | |
f9f354fc | 576 | } |
3dfed10e XL |
577 | } else { |
578 | Ok(c) | |
f9f354fc | 579 | } |
3dfed10e XL |
580 | }; |
581 | ||
582 | match (evaluate(c1), evaluate(c2)) { | |
583 | (Ok(c1), Ok(c2)) => { | |
584 | match self | |
585 | .selcx | |
586 | .infcx() | |
587 | .at(&obligation.cause, obligation.param_env) | |
588 | .eq(c1, c2) | |
589 | { | |
590 | Ok(_) => ProcessResult::Changed(vec![]), | |
591 | Err(err) => ProcessResult::Error( | |
592 | FulfillmentErrorCode::CodeConstEquateError( | |
593 | ExpectedFound::new(true, c1, c2), | |
594 | err, | |
595 | ), | |
596 | ), | |
f9f354fc XL |
597 | } |
598 | } | |
5e7ed085 FG |
599 | (Err(ErrorHandled::Reported(reported)), _) |
600 | | (_, Err(ErrorHandled::Reported(reported))) => ProcessResult::Error( | |
cdc7bbd5 | 601 | CodeSelectionError(SelectionError::NotConstEvaluatable( |
5e7ed085 | 602 | NotConstEvaluatable::Error(reported), |
cdc7bbd5 XL |
603 | )), |
604 | ), | |
3dfed10e XL |
605 | (Err(ErrorHandled::Linted), _) | (_, Err(ErrorHandled::Linted)) => { |
606 | span_bug!( | |
607 | obligation.cause.span(self.selcx.tcx()), | |
608 | "ConstEquate: const_eval_resolve returned an unexpected error" | |
609 | ) | |
610 | } | |
611 | (Err(ErrorHandled::TooGeneric), _) | (_, Err(ErrorHandled::TooGeneric)) => { | |
17df50a5 XL |
612 | if c1.has_infer_types_or_consts() || c2.has_infer_types_or_consts() { |
613 | ProcessResult::Unchanged | |
614 | } else { | |
615 | // Two different constants using generic parameters ~> error. | |
616 | let expected_found = ExpectedFound::new(true, c1, c2); | |
617 | ProcessResult::Error(FulfillmentErrorCode::CodeConstEquateError( | |
618 | expected_found, | |
619 | TypeError::ConstMismatch(expected_found), | |
620 | )) | |
621 | } | |
3dfed10e | 622 | } |
f9f354fc XL |
623 | } |
624 | } | |
5869c6ff | 625 | ty::PredicateKind::TypeWellFormedFromEnv(..) => { |
1b1a35ee XL |
626 | bug!("TypeWellFormedFromEnv is only used for Chalk") |
627 | } | |
3dfed10e | 628 | }, |
ea8adc8c | 629 | } |
1a4d82fc | 630 | } |
94b46f34 | 631 | |
923072b8 FG |
632 | fn process_backedge<'c, I>( |
633 | &mut self, | |
634 | cycle: I, | |
635 | _marker: PhantomData<&'c PendingPredicateObligation<'tcx>>, | |
636 | ) where | |
637 | I: Clone + Iterator<Item = &'c PendingPredicateObligation<'tcx>>, | |
638 | { | |
639 | if self.selcx.coinductive_match(cycle.clone().map(|s| s.obligation.predicate)) { | |
640 | debug!("process_child_obligations: coinductive match"); | |
641 | } else { | |
642 | let cycle: Vec<_> = cycle.map(|c| c.obligation.clone()).collect(); | |
643 | self.selcx.infcx().report_overflow_error_cycle(&cycle); | |
644 | } | |
645 | } | |
646 | } | |
647 | ||
648 | impl<'a, 'b, 'tcx> FulfillProcessor<'a, 'b, '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>> { | |
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( | |
3dfed10e | 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. | |
a2a8927a XL |
714 | if self.selcx.infcx().predicate_must_hold_considering_regions(obligation) { |
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 | |
723 | .infcx() | |
724 | .inner | |
725 | .borrow_mut() | |
726 | .projection_cache() | |
727 | .complete(key, EvaluationResult::EvaluatedToOk); | |
728 | } | |
136023e0 XL |
729 | return ProcessResult::Changed(vec![]); |
730 | } else { | |
731 | tracing::debug!("Does NOT hold: {:?}", obligation); | |
732 | } | |
733 | } | |
734 | ||
3dfed10e | 735 | match project::poly_project_and_unify_type(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( | |
3dfed10e | 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![ |
3dfed10e XL |
747 | project_obligation.with(project_obligation.predicate.to_predicate(tcx)), |
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>( | |
dc9dc135 | 758 | selcx: &mut SelectionContext<'a, 'tcx>, |
cdc7bbd5 | 759 | substs: ty::Binder<'tcx, SubstsRef<'tcx>>, |
6a06907d | 760 | ) -> impl Iterator<Item = TyOrConstInferVar<'tcx>> { |
ba9703b0 XL |
761 | selcx |
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() |
ba9703b0 | 766 | .filter(|arg| arg.has_infer_types_or_consts()) |
5099ac24 FG |
767 | .flat_map(|arg| { |
768 | let mut walker = arg.walk(); | |
6a06907d XL |
769 | while let Some(c) = walker.next() { |
770 | if !c.has_infer_types_or_consts() { | |
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 | } |