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