]>
Commit | Line | Data |
---|---|---|
ba9703b0 | 1 | //! Candidate selection. See the [rustc dev guide] for more information on how this works. |
74b04a01 | 2 | //! |
ba9703b0 | 3 | //! [rustc dev guide]: https://rustc-dev-guide.rust-lang.org/traits/resolution.html#selection |
74b04a01 XL |
4 | |
5 | use self::EvaluationResult::*; | |
6 | use self::SelectionCandidate::*; | |
7 | ||
8 | use super::coherence::{self, Conflict}; | |
1b1a35ee | 9 | use super::const_evaluatable; |
74b04a01 | 10 | use super::project; |
f035d41b | 11 | use super::project::normalize_with_depth_to; |
29967ef6 | 12 | use super::project::ProjectionTyObligation; |
74b04a01 XL |
13 | use super::util; |
14 | use super::util::{closure_trait_ref_and_return_type, predicate_for_trait_def}; | |
15 | use super::wf; | |
ee023bcb FG |
16 | use super::{ |
17 | DerivedObligationCause, ErrorReporting, ImplDerivedObligation, ImplDerivedObligationCause, | |
18 | Normalized, Obligation, ObligationCause, ObligationCauseCode, Overflow, PredicateObligation, | |
19 | Selection, SelectionError, SelectionResult, TraitObligation, TraitQueryMode, | |
20 | }; | |
f035d41b XL |
21 | |
22 | use crate::infer::{InferCtxt, InferOk, TypeFreshener}; | |
ba9703b0 | 23 | use crate::traits::error_reporting::InferCtxtExt; |
ee023bcb | 24 | use crate::traits::project::ProjectAndUnifyResult; |
a2a8927a XL |
25 | use crate::traits::project::ProjectionCacheKeyExt; |
26 | use crate::traits::ProjectionCacheKey; | |
74b04a01 | 27 | use rustc_data_structures::fx::{FxHashMap, FxHashSet}; |
f9f354fc | 28 | use rustc_data_structures::stack::ensure_sufficient_stack; |
ee023bcb | 29 | use rustc_errors::{Diagnostic, ErrorGuaranteed}; |
74b04a01 XL |
30 | use rustc_hir as hir; |
31 | use rustc_hir::def_id::DefId; | |
6a06907d | 32 | use rustc_infer::infer::LateBoundRegionConversionTime; |
ba9703b0 | 33 | use rustc_middle::dep_graph::{DepKind, DepNodeIndex}; |
f9f354fc | 34 | use rustc_middle::mir::interpret::ErrorHandled; |
c295e0f8 | 35 | use rustc_middle::thir::abstract_const::NotConstEvaluatable; |
ee023bcb FG |
36 | use rustc_middle::ty::fast_reject::{self, TreatParams}; |
37 | use rustc_middle::ty::fold::BottomUpFolder; | |
1b1a35ee | 38 | use rustc_middle::ty::print::with_no_trimmed_paths; |
ba9703b0 | 39 | use rustc_middle::ty::relate::TypeRelation; |
f035d41b | 40 | use rustc_middle::ty::subst::{GenericArgKind, Subst, SubstsRef}; |
29967ef6 | 41 | use rustc_middle::ty::{self, PolyProjectionPredicate, ToPolyTraitRef, ToPredicate}; |
94222f64 | 42 | use rustc_middle::ty::{Ty, TyCtxt, TypeFoldable}; |
74b04a01 | 43 | use rustc_span::symbol::sym; |
74b04a01 XL |
44 | |
45 | use std::cell::{Cell, RefCell}; | |
46 | use std::cmp; | |
47 | use std::fmt::{self, Display}; | |
48 | use std::iter; | |
74b04a01 | 49 | |
ba9703b0 | 50 | pub use rustc_middle::traits::select::*; |
74b04a01 | 51 | |
f035d41b XL |
52 | mod candidate_assembly; |
53 | mod confirmation; | |
54 | ||
3dfed10e XL |
55 | #[derive(Clone, Debug)] |
56 | pub enum IntercrateAmbiguityCause { | |
57 | DownstreamCrate { trait_desc: String, self_desc: Option<String> }, | |
58 | UpstreamCrateUpdate { trait_desc: String, self_desc: Option<String> }, | |
59 | ReservationImpl { message: String }, | |
60 | } | |
61 | ||
62 | impl IntercrateAmbiguityCause { | |
63 | /// Emits notes when the overlap is caused by complex intercrate ambiguities. | |
64 | /// See #23980 for details. | |
ee023bcb | 65 | pub fn add_intercrate_ambiguity_hint(&self, err: &mut Diagnostic) { |
3dfed10e XL |
66 | err.note(&self.intercrate_ambiguity_hint()); |
67 | } | |
68 | ||
69 | pub fn intercrate_ambiguity_hint(&self) -> String { | |
70 | match self { | |
5869c6ff XL |
71 | IntercrateAmbiguityCause::DownstreamCrate { trait_desc, self_desc } => { |
72 | let self_desc = if let Some(ty) = self_desc { | |
3dfed10e XL |
73 | format!(" for type `{}`", ty) |
74 | } else { | |
75 | String::new() | |
76 | }; | |
77 | format!("downstream crates may implement trait `{}`{}", trait_desc, self_desc) | |
78 | } | |
5869c6ff XL |
79 | IntercrateAmbiguityCause::UpstreamCrateUpdate { trait_desc, self_desc } => { |
80 | let self_desc = if let Some(ty) = self_desc { | |
3dfed10e XL |
81 | format!(" for type `{}`", ty) |
82 | } else { | |
83 | String::new() | |
84 | }; | |
85 | format!( | |
86 | "upstream crates may add a new impl of trait `{}`{} \ | |
87 | in future versions", | |
88 | trait_desc, self_desc | |
89 | ) | |
90 | } | |
5869c6ff | 91 | IntercrateAmbiguityCause::ReservationImpl { message } => message.clone(), |
3dfed10e XL |
92 | } |
93 | } | |
94 | } | |
95 | ||
74b04a01 XL |
96 | pub struct SelectionContext<'cx, 'tcx> { |
97 | infcx: &'cx InferCtxt<'cx, 'tcx>, | |
98 | ||
99 | /// Freshener used specifically for entries on the obligation | |
100 | /// stack. This ensures that all entries on the stack at one time | |
101 | /// will have the same set of placeholder entries, which is | |
102 | /// important for checking for trait bounds that recursively | |
103 | /// require themselves. | |
104 | freshener: TypeFreshener<'cx, 'tcx>, | |
105 | ||
106 | /// If `true`, indicates that the evaluation should be conservative | |
107 | /// and consider the possibility of types outside this crate. | |
108 | /// This comes up primarily when resolving ambiguity. Imagine | |
109 | /// there is some trait reference `$0: Bar` where `$0` is an | |
110 | /// inference variable. If `intercrate` is true, then we can never | |
111 | /// say for sure that this reference is not implemented, even if | |
112 | /// there are *no impls at all for `Bar`*, because `$0` could be | |
113 | /// bound to some type that in a downstream crate that implements | |
114 | /// `Bar`. This is the suitable mode for coherence. Elsewhere, | |
115 | /// though, we set this to false, because we are only interested | |
116 | /// in types that the user could actually have written --- in | |
117 | /// other words, we consider `$0: Bar` to be unimplemented if | |
118 | /// there is no type that the user could *actually name* that | |
119 | /// would satisfy it. This avoids crippling inference, basically. | |
120 | intercrate: bool, | |
121 | ||
122 | intercrate_ambiguity_causes: Option<Vec<IntercrateAmbiguityCause>>, | |
123 | ||
74b04a01 XL |
124 | /// The mode that trait queries run in, which informs our error handling |
125 | /// policy. In essence, canonicalized queries need their errors propagated | |
126 | /// rather than immediately reported because we do not have accurate spans. | |
127 | query_mode: TraitQueryMode, | |
128 | } | |
129 | ||
74b04a01 XL |
130 | // A stack that walks back up the stack frame. |
131 | struct TraitObligationStack<'prev, 'tcx> { | |
132 | obligation: &'prev TraitObligation<'tcx>, | |
133 | ||
a2a8927a | 134 | /// The trait predicate from `obligation` but "freshened" with the |
74b04a01 | 135 | /// selection-context's freshener. Used to check for recursion. |
a2a8927a | 136 | fresh_trait_pred: ty::PolyTraitPredicate<'tcx>, |
74b04a01 XL |
137 | |
138 | /// Starts out equal to `depth` -- if, during evaluation, we | |
139 | /// encounter a cycle, then we will set this flag to the minimum | |
140 | /// depth of that cycle for all participants in the cycle. These | |
141 | /// participants will then forego caching their results. This is | |
142 | /// not the most efficient solution, but it addresses #60010. The | |
143 | /// problem we are trying to prevent: | |
144 | /// | |
145 | /// - If you have `A: AutoTrait` requires `B: AutoTrait` and `C: NonAutoTrait` | |
146 | /// - `B: AutoTrait` requires `A: AutoTrait` (coinductive cycle, ok) | |
147 | /// - `C: NonAutoTrait` requires `A: AutoTrait` (non-coinductive cycle, not ok) | |
148 | /// | |
149 | /// you don't want to cache that `B: AutoTrait` or `A: AutoTrait` | |
150 | /// is `EvaluatedToOk`; this is because they were only considered | |
151 | /// ok on the premise that if `A: AutoTrait` held, but we indeed | |
152 | /// encountered a problem (later on) with `A: AutoTrait. So we | |
153 | /// currently set a flag on the stack node for `B: AutoTrait` (as | |
154 | /// well as the second instance of `A: AutoTrait`) to suppress | |
155 | /// caching. | |
156 | /// | |
157 | /// This is a simple, targeted fix. A more-performant fix requires | |
158 | /// deeper changes, but would permit more caching: we could | |
159 | /// basically defer caching until we have fully evaluated the | |
160 | /// tree, and then cache the entire tree at once. In any case, the | |
161 | /// performance impact here shouldn't be so horrible: every time | |
162 | /// this is hit, we do cache at least one trait, so we only | |
163 | /// evaluate each member of a cycle up to N times, where N is the | |
164 | /// length of the cycle. This means the performance impact is | |
165 | /// bounded and we shouldn't have any terrible worst-cases. | |
166 | reached_depth: Cell<usize>, | |
167 | ||
168 | previous: TraitObligationStackList<'prev, 'tcx>, | |
169 | ||
170 | /// The number of parent frames plus one (thus, the topmost frame has depth 1). | |
171 | depth: usize, | |
172 | ||
173 | /// The depth-first number of this node in the search graph -- a | |
174 | /// pre-order index. Basically, a freshly incremented counter. | |
175 | dfn: usize, | |
176 | } | |
177 | ||
178 | struct SelectionCandidateSet<'tcx> { | |
179 | // A list of candidates that definitely apply to the current | |
180 | // obligation (meaning: types unify). | |
181 | vec: Vec<SelectionCandidate<'tcx>>, | |
182 | ||
183 | // If `true`, then there were candidates that might or might | |
184 | // not have applied, but we couldn't tell. This occurs when some | |
185 | // of the input types are type variables, in which case there are | |
186 | // various "builtin" rules that might or might not trigger. | |
187 | ambiguous: bool, | |
188 | } | |
189 | ||
190 | #[derive(PartialEq, Eq, Debug, Clone)] | |
191 | struct EvaluatedCandidate<'tcx> { | |
192 | candidate: SelectionCandidate<'tcx>, | |
193 | evaluation: EvaluationResult, | |
194 | } | |
195 | ||
196 | /// When does the builtin impl for `T: Trait` apply? | |
5099ac24 | 197 | #[derive(Debug)] |
74b04a01 XL |
198 | enum BuiltinImplConditions<'tcx> { |
199 | /// The impl is conditional on `T1, T2, ...: Trait`. | |
cdc7bbd5 | 200 | Where(ty::Binder<'tcx, Vec<Ty<'tcx>>>), |
74b04a01 XL |
201 | /// There is no built-in impl. There may be some other |
202 | /// candidate (a where-clause or user-defined impl). | |
203 | None, | |
204 | /// It is unknown whether there is an impl. | |
205 | Ambiguous, | |
206 | } | |
207 | ||
208 | impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { | |
209 | pub fn new(infcx: &'cx InferCtxt<'cx, 'tcx>) -> SelectionContext<'cx, 'tcx> { | |
210 | SelectionContext { | |
211 | infcx, | |
136023e0 | 212 | freshener: infcx.freshener_keep_static(), |
74b04a01 XL |
213 | intercrate: false, |
214 | intercrate_ambiguity_causes: None, | |
74b04a01 XL |
215 | query_mode: TraitQueryMode::Standard, |
216 | } | |
217 | } | |
218 | ||
219 | pub fn intercrate(infcx: &'cx InferCtxt<'cx, 'tcx>) -> SelectionContext<'cx, 'tcx> { | |
220 | SelectionContext { | |
221 | infcx, | |
136023e0 | 222 | freshener: infcx.freshener_keep_static(), |
74b04a01 XL |
223 | intercrate: true, |
224 | intercrate_ambiguity_causes: None, | |
74b04a01 XL |
225 | query_mode: TraitQueryMode::Standard, |
226 | } | |
227 | } | |
228 | ||
229 | pub fn with_query_mode( | |
230 | infcx: &'cx InferCtxt<'cx, 'tcx>, | |
231 | query_mode: TraitQueryMode, | |
232 | ) -> SelectionContext<'cx, 'tcx> { | |
29967ef6 | 233 | debug!(?query_mode, "with_query_mode"); |
74b04a01 XL |
234 | SelectionContext { |
235 | infcx, | |
136023e0 | 236 | freshener: infcx.freshener_keep_static(), |
74b04a01 XL |
237 | intercrate: false, |
238 | intercrate_ambiguity_causes: None, | |
74b04a01 XL |
239 | query_mode, |
240 | } | |
241 | } | |
242 | ||
243 | /// Enables tracking of intercrate ambiguity causes. These are | |
244 | /// used in coherence to give improved diagnostics. We don't do | |
245 | /// this until we detect a coherence error because it can lead to | |
246 | /// false overflow results (#47139) and because it costs | |
247 | /// computation time. | |
248 | pub fn enable_tracking_intercrate_ambiguity_causes(&mut self) { | |
249 | assert!(self.intercrate); | |
250 | assert!(self.intercrate_ambiguity_causes.is_none()); | |
251 | self.intercrate_ambiguity_causes = Some(vec![]); | |
252 | debug!("selcx: enable_tracking_intercrate_ambiguity_causes"); | |
253 | } | |
254 | ||
255 | /// Gets the intercrate ambiguity causes collected since tracking | |
256 | /// was enabled and disables tracking at the same time. If | |
257 | /// tracking is not enabled, just returns an empty vector. | |
258 | pub fn take_intercrate_ambiguity_causes(&mut self) -> Vec<IntercrateAmbiguityCause> { | |
259 | assert!(self.intercrate); | |
29967ef6 | 260 | self.intercrate_ambiguity_causes.take().unwrap_or_default() |
74b04a01 XL |
261 | } |
262 | ||
263 | pub fn infcx(&self) -> &'cx InferCtxt<'cx, 'tcx> { | |
264 | self.infcx | |
265 | } | |
266 | ||
267 | pub fn tcx(&self) -> TyCtxt<'tcx> { | |
268 | self.infcx.tcx | |
269 | } | |
270 | ||
94222f64 XL |
271 | pub fn is_intercrate(&self) -> bool { |
272 | self.intercrate | |
273 | } | |
274 | ||
74b04a01 XL |
275 | /////////////////////////////////////////////////////////////////////////// |
276 | // Selection | |
277 | // | |
278 | // The selection phase tries to identify *how* an obligation will | |
279 | // be resolved. For example, it will identify which impl or | |
280 | // parameter bound is to be used. The process can be inconclusive | |
281 | // if the self type in the obligation is not fully inferred. Selection | |
282 | // can result in an error in one of two ways: | |
283 | // | |
284 | // 1. If no applicable impl or parameter bound can be found. | |
285 | // 2. If the output type parameters in the obligation do not match | |
286 | // those specified by the impl/bound. For example, if the obligation | |
287 | // is `Vec<Foo>: Iterable<Bar>`, but the impl specifies | |
288 | // `impl<T> Iterable<T> for Vec<T>`, than an error would result. | |
289 | ||
290 | /// Attempts to satisfy the obligation. If successful, this will affect the surrounding | |
291 | /// type environment by performing unification. | |
29967ef6 | 292 | #[instrument(level = "debug", skip(self))] |
74b04a01 XL |
293 | pub fn select( |
294 | &mut self, | |
295 | obligation: &TraitObligation<'tcx>, | |
296 | ) -> SelectionResult<'tcx, Selection<'tcx>> { | |
3c0e092e | 297 | let candidate = match self.select_from_obligation(obligation) { |
ee023bcb | 298 | Err(SelectionError::Overflow(OverflowError::Canonical)) => { |
74b04a01 XL |
299 | // In standard mode, overflow must have been caught and reported |
300 | // earlier. | |
301 | assert!(self.query_mode == TraitQueryMode::Canonical); | |
ee023bcb | 302 | return Err(SelectionError::Overflow(OverflowError::Canonical)); |
74b04a01 | 303 | } |
3c0e092e XL |
304 | Err(SelectionError::Ambiguous(_)) => { |
305 | return Ok(None); | |
306 | } | |
74b04a01 XL |
307 | Err(e) => { |
308 | return Err(e); | |
309 | } | |
310 | Ok(None) => { | |
311 | return Ok(None); | |
312 | } | |
313 | Ok(Some(candidate)) => candidate, | |
314 | }; | |
315 | ||
316 | match self.confirm_candidate(obligation, candidate) { | |
ee023bcb | 317 | Err(SelectionError::Overflow(OverflowError::Canonical)) => { |
74b04a01 | 318 | assert!(self.query_mode == TraitQueryMode::Canonical); |
ee023bcb | 319 | Err(SelectionError::Overflow(OverflowError::Canonical)) |
74b04a01 XL |
320 | } |
321 | Err(e) => Err(e), | |
29967ef6 | 322 | Ok(candidate) => { |
5099ac24 | 323 | debug!(?candidate, "confirmed"); |
29967ef6 XL |
324 | Ok(Some(candidate)) |
325 | } | |
74b04a01 XL |
326 | } |
327 | } | |
328 | ||
3c0e092e XL |
329 | crate fn select_from_obligation( |
330 | &mut self, | |
331 | obligation: &TraitObligation<'tcx>, | |
332 | ) -> SelectionResult<'tcx, SelectionCandidate<'tcx>> { | |
333 | debug_assert!(!obligation.predicate.has_escaping_bound_vars()); | |
334 | ||
335 | let pec = &ProvisionalEvaluationCache::default(); | |
336 | let stack = self.push_stack(TraitObligationStackList::empty(pec), obligation); | |
337 | ||
338 | self.candidate_from_obligation(&stack) | |
339 | } | |
340 | ||
74b04a01 XL |
341 | /////////////////////////////////////////////////////////////////////////// |
342 | // EVALUATION | |
343 | // | |
344 | // Tests whether an obligation can be selected or whether an impl | |
345 | // can be applied to particular types. It skips the "confirmation" | |
346 | // step and hence completely ignores output type parameters. | |
347 | // | |
348 | // The result is "true" if the obligation *may* hold and "false" if | |
349 | // we can be sure it does not. | |
350 | ||
351 | /// Evaluates whether the obligation `obligation` can be satisfied (by any means). | |
352 | pub fn predicate_may_hold_fatal(&mut self, obligation: &PredicateObligation<'tcx>) -> bool { | |
29967ef6 | 353 | debug!(?obligation, "predicate_may_hold_fatal"); |
74b04a01 XL |
354 | |
355 | // This fatal query is a stopgap that should only be used in standard mode, | |
356 | // where we do not expect overflow to be propagated. | |
357 | assert!(self.query_mode == TraitQueryMode::Standard); | |
358 | ||
359 | self.evaluate_root_obligation(obligation) | |
360 | .expect("Overflow should be caught earlier in standard query mode") | |
361 | .may_apply() | |
362 | } | |
363 | ||
364 | /// Evaluates whether the obligation `obligation` can be satisfied | |
365 | /// and returns an `EvaluationResult`. This is meant for the | |
366 | /// *initial* call. | |
367 | pub fn evaluate_root_obligation( | |
368 | &mut self, | |
369 | obligation: &PredicateObligation<'tcx>, | |
370 | ) -> Result<EvaluationResult, OverflowError> { | |
371 | self.evaluation_probe(|this| { | |
372 | this.evaluate_predicate_recursively( | |
373 | TraitObligationStackList::empty(&ProvisionalEvaluationCache::default()), | |
374 | obligation.clone(), | |
375 | ) | |
376 | }) | |
377 | } | |
378 | ||
379 | fn evaluation_probe( | |
380 | &mut self, | |
381 | op: impl FnOnce(&mut Self) -> Result<EvaluationResult, OverflowError>, | |
382 | ) -> Result<EvaluationResult, OverflowError> { | |
383 | self.infcx.probe(|snapshot| -> Result<EvaluationResult, OverflowError> { | |
384 | let result = op(self)?; | |
f035d41b XL |
385 | |
386 | match self.infcx.leak_check(true, snapshot) { | |
387 | Ok(()) => {} | |
388 | Err(_) => return Ok(EvaluatedToErr), | |
389 | } | |
390 | ||
74b04a01 XL |
391 | match self.infcx.region_constraints_added_in_snapshot(snapshot) { |
392 | None => Ok(result), | |
393 | Some(_) => Ok(result.max(EvaluatedToOkModuloRegions)), | |
394 | } | |
395 | }) | |
396 | } | |
397 | ||
398 | /// Evaluates the predicates in `predicates` recursively. Note that | |
399 | /// this applies projections in the predicates, and therefore | |
400 | /// is run within an inference probe. | |
c295e0f8 | 401 | #[instrument(skip(self, stack), level = "debug")] |
74b04a01 XL |
402 | fn evaluate_predicates_recursively<'o, I>( |
403 | &mut self, | |
404 | stack: TraitObligationStackList<'o, 'tcx>, | |
405 | predicates: I, | |
406 | ) -> Result<EvaluationResult, OverflowError> | |
407 | where | |
29967ef6 | 408 | I: IntoIterator<Item = PredicateObligation<'tcx>> + std::fmt::Debug, |
74b04a01 XL |
409 | { |
410 | let mut result = EvaluatedToOk; | |
411 | for obligation in predicates { | |
412 | let eval = self.evaluate_predicate_recursively(stack, obligation.clone())?; | |
74b04a01 XL |
413 | if let EvaluatedToErr = eval { |
414 | // fast-path - EvaluatedToErr is the top of the lattice, | |
415 | // so we don't need to look on the other predicates. | |
416 | return Ok(EvaluatedToErr); | |
417 | } else { | |
418 | result = cmp::max(result, eval); | |
419 | } | |
420 | } | |
421 | Ok(result) | |
422 | } | |
423 | ||
29967ef6 XL |
424 | #[instrument( |
425 | level = "debug", | |
426 | skip(self, previous_stack), | |
427 | fields(previous_stack = ?previous_stack.head()) | |
428 | )] | |
74b04a01 XL |
429 | fn evaluate_predicate_recursively<'o>( |
430 | &mut self, | |
431 | previous_stack: TraitObligationStackList<'o, 'tcx>, | |
432 | obligation: PredicateObligation<'tcx>, | |
433 | ) -> Result<EvaluationResult, OverflowError> { | |
3dfed10e | 434 | // `previous_stack` stores a `TraitObligation`, while `obligation` is |
74b04a01 XL |
435 | // a `PredicateObligation`. These are distinct types, so we can't |
436 | // use any `Option` combinator method that would force them to be | |
437 | // the same. | |
438 | match previous_stack.head() { | |
439 | Some(h) => self.check_recursion_limit(&obligation, h.obligation)?, | |
440 | None => self.check_recursion_limit(&obligation, &obligation)?, | |
441 | } | |
442 | ||
29967ef6 | 443 | let result = ensure_sufficient_stack(|| { |
5869c6ff | 444 | let bound_predicate = obligation.predicate.kind(); |
29967ef6 | 445 | match bound_predicate.skip_binder() { |
94222f64 | 446 | ty::PredicateKind::Trait(t) => { |
29967ef6 | 447 | let t = bound_predicate.rebind(t); |
1b1a35ee XL |
448 | debug_assert!(!t.has_escaping_bound_vars()); |
449 | let obligation = obligation.with(t); | |
450 | self.evaluate_trait_predicate_recursively(previous_stack, obligation) | |
451 | } | |
452 | ||
5869c6ff | 453 | ty::PredicateKind::Subtype(p) => { |
29967ef6 | 454 | let p = bound_predicate.rebind(p); |
1b1a35ee XL |
455 | // Does this code ever run? |
456 | match self.infcx.subtype_predicate(&obligation.cause, obligation.param_env, p) { | |
457 | Some(Ok(InferOk { mut obligations, .. })) => { | |
458 | self.add_depth(obligations.iter_mut(), obligation.recursion_depth); | |
459 | self.evaluate_predicates_recursively( | |
460 | previous_stack, | |
461 | obligations.into_iter(), | |
462 | ) | |
463 | } | |
464 | Some(Err(_)) => Ok(EvaluatedToErr), | |
465 | None => Ok(EvaluatedToAmbig), | |
466 | } | |
467 | } | |
74b04a01 | 468 | |
94222f64 XL |
469 | ty::PredicateKind::Coerce(p) => { |
470 | let p = bound_predicate.rebind(p); | |
471 | // Does this code ever run? | |
472 | match self.infcx.coerce_predicate(&obligation.cause, obligation.param_env, p) { | |
473 | Some(Ok(InferOk { mut obligations, .. })) => { | |
474 | self.add_depth(obligations.iter_mut(), obligation.recursion_depth); | |
475 | self.evaluate_predicates_recursively( | |
476 | previous_stack, | |
477 | obligations.into_iter(), | |
478 | ) | |
479 | } | |
480 | Some(Err(_)) => Ok(EvaluatedToErr), | |
481 | None => Ok(EvaluatedToAmbig), | |
482 | } | |
483 | } | |
484 | ||
5869c6ff | 485 | ty::PredicateKind::WellFormed(arg) => match wf::obligations( |
1b1a35ee XL |
486 | self.infcx, |
487 | obligation.param_env, | |
488 | obligation.cause.body_id, | |
29967ef6 | 489 | obligation.recursion_depth + 1, |
1b1a35ee XL |
490 | arg, |
491 | obligation.cause.span, | |
492 | ) { | |
493 | Some(mut obligations) => { | |
74b04a01 | 494 | self.add_depth(obligations.iter_mut(), obligation.recursion_depth); |
29967ef6 | 495 | self.evaluate_predicates_recursively(previous_stack, obligations) |
74b04a01 | 496 | } |
74b04a01 | 497 | None => Ok(EvaluatedToAmbig), |
1b1a35ee | 498 | }, |
74b04a01 | 499 | |
136023e0 | 500 | ty::PredicateKind::TypeOutlives(pred) => { |
a2a8927a XL |
501 | // A global type with no late-bound regions can only |
502 | // contain the "'static" lifetime (any other lifetime | |
503 | // would either be late-bound or local), so it is guaranteed | |
504 | // to outlive any other lifetime | |
5099ac24 | 505 | if pred.0.is_global() && !pred.0.has_late_bound_regions() { |
136023e0 XL |
506 | Ok(EvaluatedToOk) |
507 | } else { | |
508 | Ok(EvaluatedToOkModuloRegions) | |
509 | } | |
510 | } | |
511 | ||
512 | ty::PredicateKind::RegionOutlives(..) => { | |
1b1a35ee XL |
513 | // We do not consider region relationships when evaluating trait matches. |
514 | Ok(EvaluatedToOkModuloRegions) | |
74b04a01 | 515 | } |
74b04a01 | 516 | |
5869c6ff | 517 | ty::PredicateKind::ObjectSafe(trait_def_id) => { |
1b1a35ee XL |
518 | if self.tcx().is_object_safe(trait_def_id) { |
519 | Ok(EvaluatedToOk) | |
520 | } else { | |
521 | Ok(EvaluatedToErr) | |
522 | } | |
74b04a01 | 523 | } |
74b04a01 | 524 | |
5869c6ff | 525 | ty::PredicateKind::Projection(data) => { |
29967ef6 | 526 | let data = bound_predicate.rebind(data); |
1b1a35ee XL |
527 | let project_obligation = obligation.with(data); |
528 | match project::poly_project_and_unify_type(self, &project_obligation) { | |
ee023bcb | 529 | ProjectAndUnifyResult::Holds(mut subobligations) => { |
a2a8927a | 530 | 'compute_res: { |
ee023bcb | 531 | // If we've previously marked this projection as 'complete', then |
a2a8927a XL |
532 | // use the final cached result (either `EvaluatedToOk` or |
533 | // `EvaluatedToOkModuloRegions`), and skip re-evaluating the | |
534 | // sub-obligations. | |
535 | if let Some(key) = | |
536 | ProjectionCacheKey::from_poly_projection_predicate(self, data) | |
537 | { | |
538 | if let Some(cached_res) = self | |
539 | .infcx | |
540 | .inner | |
541 | .borrow_mut() | |
542 | .projection_cache() | |
543 | .is_complete(key) | |
544 | { | |
545 | break 'compute_res Ok(cached_res); | |
546 | } | |
547 | } | |
548 | ||
549 | self.add_depth( | |
550 | subobligations.iter_mut(), | |
551 | obligation.recursion_depth, | |
552 | ); | |
553 | let res = self.evaluate_predicates_recursively( | |
554 | previous_stack, | |
555 | subobligations, | |
556 | ); | |
ee023bcb FG |
557 | if let Ok(eval_rslt) = res |
558 | && (eval_rslt == EvaluatedToOk || eval_rslt == EvaluatedToOkModuloRegions) | |
559 | && let Some(key) = | |
560 | ProjectionCacheKey::from_poly_projection_predicate( | |
561 | self, data, | |
562 | ) | |
563 | { | |
564 | // If the result is something that we can cache, then mark this | |
565 | // entry as 'complete'. This will allow us to skip evaluating the | |
566 | // subobligations at all the next time we evaluate the projection | |
567 | // predicate. | |
568 | self.infcx | |
569 | .inner | |
570 | .borrow_mut() | |
571 | .projection_cache() | |
572 | .complete(key, eval_rslt); | |
a2a8927a XL |
573 | } |
574 | res | |
575 | } | |
74b04a01 | 576 | } |
ee023bcb FG |
577 | ProjectAndUnifyResult::FailedNormalization => Ok(EvaluatedToAmbig), |
578 | ProjectAndUnifyResult::Recursive => Ok(EvaluatedToRecur), | |
579 | ProjectAndUnifyResult::MismatchedProjectionTypes(_) => Ok(EvaluatedToErr), | |
74b04a01 | 580 | } |
74b04a01 | 581 | } |
74b04a01 | 582 | |
5869c6ff | 583 | ty::PredicateKind::ClosureKind(_, closure_substs, kind) => { |
1b1a35ee XL |
584 | match self.infcx.closure_kind(closure_substs) { |
585 | Some(closure_kind) => { | |
586 | if closure_kind.extends(kind) { | |
587 | Ok(EvaluatedToOk) | |
588 | } else { | |
589 | Ok(EvaluatedToErr) | |
590 | } | |
74b04a01 | 591 | } |
1b1a35ee | 592 | None => Ok(EvaluatedToAmbig), |
74b04a01 | 593 | } |
74b04a01 | 594 | } |
74b04a01 | 595 | |
94222f64 | 596 | ty::PredicateKind::ConstEvaluatable(uv) => { |
1b1a35ee XL |
597 | match const_evaluatable::is_const_evaluatable( |
598 | self.infcx, | |
94222f64 | 599 | uv, |
1b1a35ee XL |
600 | obligation.param_env, |
601 | obligation.cause.span, | |
602 | ) { | |
603 | Ok(()) => Ok(EvaluatedToOk), | |
cdc7bbd5 XL |
604 | Err(NotConstEvaluatable::MentionsInfer) => Ok(EvaluatedToAmbig), |
605 | Err(NotConstEvaluatable::MentionsParam) => Ok(EvaluatedToErr), | |
1b1a35ee XL |
606 | Err(_) => Ok(EvaluatedToErr), |
607 | } | |
74b04a01 | 608 | } |
f9f354fc | 609 | |
5869c6ff | 610 | ty::PredicateKind::ConstEquate(c1, c2) => { |
29967ef6 | 611 | debug!(?c1, ?c2, "evaluate_predicate_recursively: equating consts"); |
f9f354fc | 612 | |
94222f64 | 613 | if self.tcx().features().generic_const_exprs { |
17df50a5 XL |
614 | // FIXME: we probably should only try to unify abstract constants |
615 | // if the constants depend on generic parameters. | |
616 | // | |
617 | // Let's just see where this breaks :shrug: | |
618 | if let (ty::ConstKind::Unevaluated(a), ty::ConstKind::Unevaluated(b)) = | |
5099ac24 | 619 | (c1.val(), c2.val()) |
17df50a5 | 620 | { |
ee023bcb FG |
621 | if self.infcx.try_unify_abstract_consts( |
622 | a.shrink(), | |
623 | b.shrink(), | |
624 | obligation.param_env, | |
625 | ) { | |
17df50a5 XL |
626 | return Ok(EvaluatedToOk); |
627 | } | |
628 | } | |
629 | } | |
630 | ||
5099ac24 FG |
631 | let evaluate = |c: ty::Const<'tcx>| { |
632 | if let ty::ConstKind::Unevaluated(unevaluated) = c.val() { | |
1b1a35ee XL |
633 | self.infcx |
634 | .const_eval_resolve( | |
635 | obligation.param_env, | |
cdc7bbd5 | 636 | unevaluated, |
1b1a35ee XL |
637 | Some(obligation.cause.span), |
638 | ) | |
5099ac24 | 639 | .map(|val| ty::Const::from_value(self.tcx(), val, c.ty())) |
1b1a35ee XL |
640 | } else { |
641 | Ok(c) | |
642 | } | |
643 | }; | |
644 | ||
645 | match (evaluate(c1), evaluate(c2)) { | |
646 | (Ok(c1), Ok(c2)) => { | |
647 | match self | |
648 | .infcx() | |
649 | .at(&obligation.cause, obligation.param_env) | |
650 | .eq(c1, c2) | |
651 | { | |
652 | Ok(_) => Ok(EvaluatedToOk), | |
653 | Err(_) => Ok(EvaluatedToErr), | |
654 | } | |
655 | } | |
ee023bcb FG |
656 | (Err(ErrorHandled::Reported(_)), _) |
657 | | (_, Err(ErrorHandled::Reported(_))) => Ok(EvaluatedToErr), | |
1b1a35ee XL |
658 | (Err(ErrorHandled::Linted), _) | (_, Err(ErrorHandled::Linted)) => { |
659 | span_bug!( | |
660 | obligation.cause.span(self.tcx()), | |
661 | "ConstEquate: const_eval_resolve returned an unexpected error" | |
662 | ) | |
663 | } | |
664 | (Err(ErrorHandled::TooGeneric), _) | (_, Err(ErrorHandled::TooGeneric)) => { | |
17df50a5 XL |
665 | if c1.has_infer_types_or_consts() || c2.has_infer_types_or_consts() { |
666 | Ok(EvaluatedToAmbig) | |
667 | } else { | |
668 | // Two different constants using generic parameters ~> error. | |
669 | Ok(EvaluatedToErr) | |
670 | } | |
f9f354fc | 671 | } |
f9f354fc XL |
672 | } |
673 | } | |
5869c6ff | 674 | ty::PredicateKind::TypeWellFormedFromEnv(..) => { |
1b1a35ee XL |
675 | bug!("TypeWellFormedFromEnv is only used for chalk") |
676 | } | |
f9f354fc | 677 | } |
29967ef6 XL |
678 | }); |
679 | ||
94222f64 | 680 | debug!("finished: {:?} from {:?}", result, obligation); |
29967ef6 XL |
681 | |
682 | result | |
74b04a01 XL |
683 | } |
684 | ||
c295e0f8 | 685 | #[instrument(skip(self, previous_stack), level = "debug")] |
74b04a01 XL |
686 | fn evaluate_trait_predicate_recursively<'o>( |
687 | &mut self, | |
688 | previous_stack: TraitObligationStackList<'o, 'tcx>, | |
689 | mut obligation: TraitObligation<'tcx>, | |
690 | ) -> Result<EvaluationResult, OverflowError> { | |
74b04a01 | 691 | if !self.intercrate |
5099ac24 FG |
692 | && obligation.is_global() |
693 | && obligation.param_env.caller_bounds().iter().all(|bound| bound.needs_subst()) | |
74b04a01 XL |
694 | { |
695 | // If a param env has no global bounds, global obligations do not | |
696 | // depend on its particular value in order to work, so we can clear | |
697 | // out the param env and get better caching. | |
c295e0f8 | 698 | debug!("in global"); |
74b04a01 XL |
699 | obligation.param_env = obligation.param_env.without_caller_bounds(); |
700 | } | |
701 | ||
702 | let stack = self.push_stack(previous_stack, &obligation); | |
a2a8927a XL |
703 | let mut fresh_trait_pred = stack.fresh_trait_pred; |
704 | let mut param_env = obligation.param_env; | |
29967ef6 | 705 | |
a2a8927a XL |
706 | fresh_trait_pred = fresh_trait_pred.map_bound(|mut pred| { |
707 | pred.remap_constness(self.tcx(), &mut param_env); | |
708 | pred | |
709 | }); | |
29967ef6 | 710 | |
a2a8927a XL |
711 | debug!(?fresh_trait_pred); |
712 | ||
713 | if let Some(result) = self.check_evaluation_cache(param_env, fresh_trait_pred) { | |
29967ef6 | 714 | debug!(?result, "CACHE HIT"); |
74b04a01 XL |
715 | return Ok(result); |
716 | } | |
717 | ||
a2a8927a | 718 | if let Some(result) = stack.cache().get_provisional(fresh_trait_pred) { |
29967ef6 | 719 | debug!(?result, "PROVISIONAL CACHE HIT"); |
17df50a5 XL |
720 | stack.update_reached_depth(result.reached_depth); |
721 | return Ok(result.result); | |
74b04a01 XL |
722 | } |
723 | ||
724 | // Check if this is a match for something already on the | |
725 | // stack. If so, we don't want to insert the result into the | |
726 | // main cache (it is cycle dependent) nor the provisional | |
727 | // cache (which is meant for things that have completed but | |
728 | // for a "backedge" -- this result *is* the backedge). | |
729 | if let Some(cycle_result) = self.check_evaluation_cycle(&stack) { | |
730 | return Ok(cycle_result); | |
731 | } | |
732 | ||
733 | let (result, dep_node) = self.in_task(|this| this.evaluate_stack(&stack)); | |
734 | let result = result?; | |
735 | ||
736 | if !result.must_apply_modulo_regions() { | |
737 | stack.cache().on_failure(stack.dfn); | |
738 | } | |
739 | ||
740 | let reached_depth = stack.reached_depth.get(); | |
741 | if reached_depth >= stack.depth { | |
29967ef6 | 742 | debug!(?result, "CACHE MISS"); |
a2a8927a | 743 | self.insert_evaluation_cache(param_env, fresh_trait_pred, dep_node, result); |
74b04a01 | 744 | |
5099ac24 FG |
745 | stack.cache().on_completion( |
746 | stack.dfn, | |
747 | |fresh_trait_pred, provisional_result, provisional_dep_node| { | |
748 | // Create a new `DepNode` that has dependencies on: | |
749 | // * The `DepNode` for the original evaluation that resulted in a provisional cache | |
750 | // entry being crated | |
751 | // * The `DepNode` for the *current* evaluation, which resulted in us completing | |
752 | // provisional caches entries and inserting them into the evaluation cache | |
753 | // | |
754 | // This ensures that when a query reads this entry from the evaluation cache, | |
ee023bcb | 755 | // it will end up (transitively) depending on all of the incr-comp dependencies |
5099ac24 FG |
756 | // created during the evaluation of this trait. For example, evaluating a trait |
757 | // will usually require us to invoke `type_of(field_def_id)` to determine the | |
758 | // constituent types, and we want any queries reading from this evaluation | |
759 | // cache entry to end up with a transitive `type_of(field_def_id`)` dependency. | |
760 | // | |
761 | // By using `in_task`, we're also creating an edge from the *current* query | |
762 | // to the newly-created `combined_dep_node`. This is probably redundant, | |
763 | // but it's better to add too many dep graph edges than to add too few | |
764 | // dep graph edges. | |
765 | let ((), combined_dep_node) = self.in_task(|this| { | |
766 | this.tcx().dep_graph.read_index(provisional_dep_node); | |
767 | this.tcx().dep_graph.read_index(dep_node); | |
768 | }); | |
769 | self.insert_evaluation_cache( | |
770 | param_env, | |
771 | fresh_trait_pred, | |
772 | combined_dep_node, | |
773 | provisional_result.max(result), | |
774 | ); | |
775 | }, | |
776 | ); | |
74b04a01 | 777 | } else { |
29967ef6 | 778 | debug!(?result, "PROVISIONAL"); |
74b04a01 | 779 | debug!( |
c295e0f8 | 780 | "caching provisionally because {:?} \ |
74b04a01 | 781 | is a cycle participant (at depth {}, reached depth {})", |
a2a8927a | 782 | fresh_trait_pred, stack.depth, reached_depth, |
74b04a01 XL |
783 | ); |
784 | ||
5099ac24 FG |
785 | stack.cache().insert_provisional( |
786 | stack.dfn, | |
787 | reached_depth, | |
788 | fresh_trait_pred, | |
789 | result, | |
790 | dep_node, | |
791 | ); | |
74b04a01 XL |
792 | } |
793 | ||
794 | Ok(result) | |
795 | } | |
796 | ||
797 | /// If there is any previous entry on the stack that precisely | |
798 | /// matches this obligation, then we can assume that the | |
799 | /// obligation is satisfied for now (still all other conditions | |
800 | /// must be met of course). One obvious case this comes up is | |
801 | /// marker traits like `Send`. Think of a linked list: | |
802 | /// | |
803 | /// struct List<T> { data: T, next: Option<Box<List<T>>> } | |
804 | /// | |
805 | /// `Box<List<T>>` will be `Send` if `T` is `Send` and | |
806 | /// `Option<Box<List<T>>>` is `Send`, and in turn | |
807 | /// `Option<Box<List<T>>>` is `Send` if `Box<List<T>>` is | |
808 | /// `Send`. | |
809 | /// | |
810 | /// Note that we do this comparison using the `fresh_trait_ref` | |
811 | /// fields. Because these have all been freshened using | |
812 | /// `self.freshener`, we can be sure that (a) this will not | |
813 | /// affect the inferencer state and (b) that if we see two | |
814 | /// fresh regions with the same index, they refer to the same | |
815 | /// unbound type variable. | |
816 | fn check_evaluation_cycle( | |
817 | &mut self, | |
818 | stack: &TraitObligationStack<'_, 'tcx>, | |
819 | ) -> Option<EvaluationResult> { | |
820 | if let Some(cycle_depth) = stack | |
821 | .iter() | |
822 | .skip(1) // Skip top-most frame. | |
823 | .find(|prev| { | |
824 | stack.obligation.param_env == prev.obligation.param_env | |
a2a8927a | 825 | && stack.fresh_trait_pred == prev.fresh_trait_pred |
74b04a01 XL |
826 | }) |
827 | .map(|stack| stack.depth) | |
828 | { | |
29967ef6 | 829 | debug!("evaluate_stack --> recursive at depth {}", cycle_depth); |
74b04a01 XL |
830 | |
831 | // If we have a stack like `A B C D E A`, where the top of | |
832 | // the stack is the final `A`, then this will iterate over | |
833 | // `A, E, D, C, B` -- i.e., all the participants apart | |
834 | // from the cycle head. We mark them as participating in a | |
835 | // cycle. This suppresses caching for those nodes. See | |
836 | // `in_cycle` field for more details. | |
837 | stack.update_reached_depth(cycle_depth); | |
838 | ||
839 | // Subtle: when checking for a coinductive cycle, we do | |
840 | // not compare using the "freshened trait refs" (which | |
841 | // have erased regions) but rather the fully explicit | |
842 | // trait refs. This is important because it's only a cycle | |
843 | // if the regions match exactly. | |
844 | let cycle = stack.iter().skip(1).take_while(|s| s.depth >= cycle_depth); | |
f9f354fc | 845 | let tcx = self.tcx(); |
94222f64 | 846 | let cycle = cycle.map(|stack| stack.obligation.predicate.to_predicate(tcx)); |
74b04a01 | 847 | if self.coinductive_match(cycle) { |
29967ef6 | 848 | debug!("evaluate_stack --> recursive, coinductive"); |
74b04a01 XL |
849 | Some(EvaluatedToOk) |
850 | } else { | |
29967ef6 | 851 | debug!("evaluate_stack --> recursive, inductive"); |
74b04a01 XL |
852 | Some(EvaluatedToRecur) |
853 | } | |
854 | } else { | |
855 | None | |
856 | } | |
857 | } | |
858 | ||
859 | fn evaluate_stack<'o>( | |
860 | &mut self, | |
861 | stack: &TraitObligationStack<'o, 'tcx>, | |
862 | ) -> Result<EvaluationResult, OverflowError> { | |
ba9703b0 | 863 | // In intercrate mode, whenever any of the generics are unbound, |
74b04a01 XL |
864 | // there can always be an impl. Even if there are no impls in |
865 | // this crate, perhaps the type would be unified with | |
866 | // something from another crate that does provide an impl. | |
867 | // | |
868 | // In intra mode, we must still be conservative. The reason is | |
869 | // that we want to avoid cycles. Imagine an impl like: | |
870 | // | |
871 | // impl<T:Eq> Eq for Vec<T> | |
872 | // | |
873 | // and a trait reference like `$0 : Eq` where `$0` is an | |
874 | // unbound variable. When we evaluate this trait-reference, we | |
875 | // will unify `$0` with `Vec<$1>` (for some fresh variable | |
876 | // `$1`), on the condition that `$1 : Eq`. We will then wind | |
877 | // up with many candidates (since that are other `Eq` impls | |
878 | // that apply) and try to winnow things down. This results in | |
879 | // a recursive evaluation that `$1 : Eq` -- as you can | |
880 | // imagine, this is just where we started. To avoid that, we | |
881 | // check for unbound variables and return an ambiguous (hence possible) | |
882 | // match if we've seen this trait before. | |
883 | // | |
884 | // This suffices to allow chains like `FnMut` implemented in | |
885 | // terms of `Fn` etc, but we could probably make this more | |
886 | // precise still. | |
887 | let unbound_input_types = | |
a2a8927a | 888 | stack.fresh_trait_pred.skip_binder().trait_ref.substs.types().any(|ty| ty.is_fresh()); |
3c0e092e XL |
889 | |
890 | if stack.obligation.polarity() != ty::ImplPolarity::Negative { | |
891 | // This check was an imperfect workaround for a bug in the old | |
892 | // intercrate mode; it should be removed when that goes away. | |
893 | if unbound_input_types && self.intercrate { | |
894 | debug!("evaluate_stack --> unbound argument, intercrate --> ambiguous",); | |
895 | // Heuristics: show the diagnostics when there are no candidates in crate. | |
896 | if self.intercrate_ambiguity_causes.is_some() { | |
897 | debug!("evaluate_stack: intercrate_ambiguity_causes is some"); | |
898 | if let Ok(candidate_set) = self.assemble_candidates(stack) { | |
899 | if !candidate_set.ambiguous && candidate_set.vec.is_empty() { | |
900 | let trait_ref = stack.obligation.predicate.skip_binder().trait_ref; | |
901 | let self_ty = trait_ref.self_ty(); | |
ee023bcb | 902 | let cause = with_no_trimmed_paths!({ |
3c0e092e XL |
903 | IntercrateAmbiguityCause::DownstreamCrate { |
904 | trait_desc: trait_ref.print_only_trait_path().to_string(), | |
905 | self_desc: if self_ty.has_concrete_skeleton() { | |
906 | Some(self_ty.to_string()) | |
907 | } else { | |
908 | None | |
909 | }, | |
910 | } | |
1b1a35ee XL |
911 | }); |
912 | ||
3c0e092e XL |
913 | debug!(?cause, "evaluate_stack: pushing cause"); |
914 | self.intercrate_ambiguity_causes.as_mut().unwrap().push(cause); | |
915 | } | |
74b04a01 XL |
916 | } |
917 | } | |
3c0e092e | 918 | return Ok(EvaluatedToAmbig); |
74b04a01 | 919 | } |
74b04a01 | 920 | } |
3c0e092e | 921 | |
74b04a01 XL |
922 | if unbound_input_types |
923 | && stack.iter().skip(1).any(|prev| { | |
924 | stack.obligation.param_env == prev.obligation.param_env | |
925 | && self.match_fresh_trait_refs( | |
a2a8927a XL |
926 | stack.fresh_trait_pred, |
927 | prev.fresh_trait_pred, | |
74b04a01 XL |
928 | prev.obligation.param_env, |
929 | ) | |
930 | }) | |
931 | { | |
29967ef6 | 932 | debug!("evaluate_stack --> unbound argument, recursive --> giving up",); |
74b04a01 XL |
933 | return Ok(EvaluatedToUnknown); |
934 | } | |
935 | ||
936 | match self.candidate_from_obligation(stack) { | |
937 | Ok(Some(c)) => self.evaluate_candidate(stack, &c), | |
3c0e092e | 938 | Err(SelectionError::Ambiguous(_)) => Ok(EvaluatedToAmbig), |
74b04a01 | 939 | Ok(None) => Ok(EvaluatedToAmbig), |
ee023bcb | 940 | Err(Overflow(OverflowError::Canonical)) => Err(OverflowError::Canonical), |
c295e0f8 | 941 | Err(ErrorReporting) => Err(OverflowError::ErrorReporting), |
74b04a01 XL |
942 | Err(..) => Ok(EvaluatedToErr), |
943 | } | |
944 | } | |
945 | ||
946 | /// For defaulted traits, we use a co-inductive strategy to solve, so | |
947 | /// that recursion is ok. This routine returns `true` if the top of the | |
948 | /// stack (`cycle[0]`): | |
949 | /// | |
950 | /// - is a defaulted trait, | |
951 | /// - it also appears in the backtrace at some position `X`, | |
952 | /// - all the predicates at positions `X..` between `X` and the top are | |
953 | /// also defaulted traits. | |
fc512014 | 954 | pub fn coinductive_match<I>(&mut self, mut cycle: I) -> bool |
74b04a01 XL |
955 | where |
956 | I: Iterator<Item = ty::Predicate<'tcx>>, | |
957 | { | |
74b04a01 XL |
958 | cycle.all(|predicate| self.coinductive_predicate(predicate)) |
959 | } | |
960 | ||
961 | fn coinductive_predicate(&self, predicate: ty::Predicate<'tcx>) -> bool { | |
5869c6ff | 962 | let result = match predicate.kind().skip_binder() { |
94222f64 | 963 | ty::PredicateKind::Trait(ref data) => self.tcx().trait_is_auto(data.def_id()), |
74b04a01 XL |
964 | _ => false, |
965 | }; | |
29967ef6 | 966 | debug!(?predicate, ?result, "coinductive_predicate"); |
74b04a01 XL |
967 | result |
968 | } | |
969 | ||
970 | /// Further evaluates `candidate` to decide whether all type parameters match and whether nested | |
971 | /// obligations are met. Returns whether `candidate` remains viable after this further | |
972 | /// scrutiny. | |
29967ef6 XL |
973 | #[instrument( |
974 | level = "debug", | |
975 | skip(self, stack), | |
976 | fields(depth = stack.obligation.recursion_depth) | |
977 | )] | |
74b04a01 XL |
978 | fn evaluate_candidate<'o>( |
979 | &mut self, | |
980 | stack: &TraitObligationStack<'o, 'tcx>, | |
981 | candidate: &SelectionCandidate<'tcx>, | |
982 | ) -> Result<EvaluationResult, OverflowError> { | |
cdc7bbd5 | 983 | let mut result = self.evaluation_probe(|this| { |
74b04a01 XL |
984 | let candidate = (*candidate).clone(); |
985 | match this.confirm_candidate(stack.obligation, candidate) { | |
29967ef6 XL |
986 | Ok(selection) => { |
987 | debug!(?selection); | |
988 | this.evaluate_predicates_recursively( | |
989 | stack.list(), | |
990 | selection.nested_obligations().into_iter(), | |
991 | ) | |
992 | } | |
74b04a01 XL |
993 | Err(..) => Ok(EvaluatedToErr), |
994 | } | |
995 | })?; | |
cdc7bbd5 XL |
996 | |
997 | // If we erased any lifetimes, then we want to use | |
998 | // `EvaluatedToOkModuloRegions` instead of `EvaluatedToOk` | |
999 | // as your final result. The result will be cached using | |
1000 | // the freshened trait predicate as a key, so we need | |
1001 | // our result to be correct by *any* choice of original lifetimes, | |
1002 | // not just the lifetime choice for this particular (non-erased) | |
1003 | // predicate. | |
1004 | // See issue #80691 | |
a2a8927a | 1005 | if stack.fresh_trait_pred.has_erased_regions() { |
cdc7bbd5 XL |
1006 | result = result.max(EvaluatedToOkModuloRegions); |
1007 | } | |
1008 | ||
29967ef6 | 1009 | debug!(?result); |
74b04a01 XL |
1010 | Ok(result) |
1011 | } | |
1012 | ||
1013 | fn check_evaluation_cache( | |
1014 | &self, | |
1015 | param_env: ty::ParamEnv<'tcx>, | |
a2a8927a | 1016 | trait_pred: ty::PolyTraitPredicate<'tcx>, |
74b04a01 | 1017 | ) -> Option<EvaluationResult> { |
94222f64 XL |
1018 | // Neither the global nor local cache is aware of intercrate |
1019 | // mode, so don't do any caching. In particular, we might | |
1020 | // re-use the same `InferCtxt` with both an intercrate | |
1021 | // and non-intercrate `SelectionContext` | |
1022 | if self.intercrate { | |
1023 | return None; | |
1024 | } | |
1025 | ||
74b04a01 XL |
1026 | let tcx = self.tcx(); |
1027 | if self.can_use_global_caches(param_env) { | |
ee023bcb | 1028 | if let Some(res) = tcx.evaluation_cache.get(&(param_env, trait_pred), tcx) { |
3dfed10e | 1029 | return Some(res); |
74b04a01 XL |
1030 | } |
1031 | } | |
ee023bcb | 1032 | self.infcx.evaluation_cache.get(&(param_env, trait_pred), tcx) |
74b04a01 XL |
1033 | } |
1034 | ||
1035 | fn insert_evaluation_cache( | |
1036 | &mut self, | |
1037 | param_env: ty::ParamEnv<'tcx>, | |
a2a8927a | 1038 | trait_pred: ty::PolyTraitPredicate<'tcx>, |
74b04a01 XL |
1039 | dep_node: DepNodeIndex, |
1040 | result: EvaluationResult, | |
1041 | ) { | |
1042 | // Avoid caching results that depend on more than just the trait-ref | |
1043 | // - the stack can create recursion. | |
1044 | if result.is_stack_dependent() { | |
1045 | return; | |
1046 | } | |
1047 | ||
94222f64 XL |
1048 | // Neither the global nor local cache is aware of intercrate |
1049 | // mode, so don't do any caching. In particular, we might | |
1050 | // re-use the same `InferCtxt` with both an intercrate | |
1051 | // and non-intercrate `SelectionContext` | |
1052 | if self.intercrate { | |
1053 | return; | |
1054 | } | |
1055 | ||
74b04a01 | 1056 | if self.can_use_global_caches(param_env) { |
a2a8927a XL |
1057 | if !trait_pred.needs_infer() { |
1058 | debug!(?trait_pred, ?result, "insert_evaluation_cache global"); | |
74b04a01 XL |
1059 | // This may overwrite the cache with the same value |
1060 | // FIXME: Due to #50507 this overwrites the different values | |
1061 | // This should be changed to use HashMapExt::insert_same | |
1062 | // when that is fixed | |
ee023bcb | 1063 | self.tcx().evaluation_cache.insert((param_env, trait_pred), dep_node, result); |
74b04a01 XL |
1064 | return; |
1065 | } | |
1066 | } | |
1067 | ||
a2a8927a | 1068 | debug!(?trait_pred, ?result, "insert_evaluation_cache"); |
ee023bcb | 1069 | self.infcx.evaluation_cache.insert((param_env, trait_pred), dep_node, result); |
74b04a01 XL |
1070 | } |
1071 | ||
1072 | /// For various reasons, it's possible for a subobligation | |
1073 | /// to have a *lower* recursion_depth than the obligation used to create it. | |
1074 | /// Projection sub-obligations may be returned from the projection cache, | |
1075 | /// which results in obligations with an 'old' `recursion_depth`. | |
29967ef6 XL |
1076 | /// Additionally, methods like `InferCtxt.subtype_predicate` produce |
1077 | /// subobligations without taking in a 'parent' depth, causing the | |
1078 | /// generated subobligations to have a `recursion_depth` of `0`. | |
74b04a01 | 1079 | /// |
cdc7bbd5 | 1080 | /// To ensure that obligation_depth never decreases, we force all subobligations |
74b04a01 XL |
1081 | /// to have at least the depth of the original obligation. |
1082 | fn add_depth<T: 'cx, I: Iterator<Item = &'cx mut Obligation<'tcx, T>>>( | |
1083 | &self, | |
1084 | it: I, | |
1085 | min_depth: usize, | |
1086 | ) { | |
1087 | it.for_each(|o| o.recursion_depth = cmp::max(min_depth, o.recursion_depth) + 1); | |
1088 | } | |
1089 | ||
c295e0f8 | 1090 | fn check_recursion_depth<T: Display + TypeFoldable<'tcx>>( |
74b04a01 | 1091 | &self, |
c295e0f8 XL |
1092 | depth: usize, |
1093 | error_obligation: &Obligation<'tcx, T>, | |
74b04a01 | 1094 | ) -> Result<(), OverflowError> { |
c295e0f8 | 1095 | if !self.infcx.tcx.recursion_limit().value_within_limit(depth) { |
74b04a01 XL |
1096 | match self.query_mode { |
1097 | TraitQueryMode::Standard => { | |
c295e0f8 | 1098 | if self.infcx.is_tainted_by_errors() { |
ee023bcb FG |
1099 | return Err(OverflowError::Error( |
1100 | ErrorGuaranteed::unchecked_claim_error_was_emitted(), | |
1101 | )); | |
c295e0f8 XL |
1102 | } |
1103 | self.infcx.report_overflow_error(error_obligation, true); | |
74b04a01 XL |
1104 | } |
1105 | TraitQueryMode::Canonical => { | |
c295e0f8 | 1106 | return Err(OverflowError::Canonical); |
74b04a01 XL |
1107 | } |
1108 | } | |
1109 | } | |
1110 | Ok(()) | |
1111 | } | |
1112 | ||
c295e0f8 XL |
1113 | /// Checks that the recursion limit has not been exceeded. |
1114 | /// | |
1115 | /// The weird return type of this function allows it to be used with the `try` (`?`) | |
1116 | /// operator within certain functions. | |
1117 | #[inline(always)] | |
1118 | fn check_recursion_limit<T: Display + TypeFoldable<'tcx>, V: Display + TypeFoldable<'tcx>>( | |
1119 | &self, | |
1120 | obligation: &Obligation<'tcx, T>, | |
1121 | error_obligation: &Obligation<'tcx, V>, | |
1122 | ) -> Result<(), OverflowError> { | |
1123 | self.check_recursion_depth(obligation.recursion_depth, error_obligation) | |
1124 | } | |
1125 | ||
74b04a01 XL |
1126 | fn in_task<OP, R>(&mut self, op: OP) -> (R, DepNodeIndex) |
1127 | where | |
1128 | OP: FnOnce(&mut Self) -> R, | |
1129 | { | |
1130 | let (result, dep_node) = | |
cdc7bbd5 | 1131 | self.tcx().dep_graph.with_anon_task(self.tcx(), DepKind::TraitSelect, || op(self)); |
74b04a01 XL |
1132 | self.tcx().dep_graph.read_index(dep_node); |
1133 | (result, dep_node) | |
1134 | } | |
1135 | ||
3c0e092e XL |
1136 | /// filter_impls filters constant trait obligations and candidates that have a positive impl |
1137 | /// for a negative goal and a negative impl for a positive goal | |
94222f64 XL |
1138 | #[instrument(level = "debug", skip(self))] |
1139 | fn filter_impls( | |
74b04a01 | 1140 | &mut self, |
3c0e092e | 1141 | candidates: Vec<SelectionCandidate<'tcx>>, |
94222f64 | 1142 | obligation: &TraitObligation<'tcx>, |
3c0e092e | 1143 | ) -> Vec<SelectionCandidate<'tcx>> { |
94222f64 | 1144 | let tcx = self.tcx(); |
3c0e092e XL |
1145 | let mut result = Vec::with_capacity(candidates.len()); |
1146 | ||
1147 | for candidate in candidates { | |
1148 | // Respect const trait obligations | |
a2a8927a | 1149 | if obligation.is_const() { |
3c0e092e XL |
1150 | match candidate { |
1151 | // const impl | |
1152 | ImplCandidate(def_id) | |
1153 | if tcx.impl_constness(def_id) == hir::Constness::Const => {} | |
1154 | // const param | |
5099ac24 | 1155 | ParamCandidate(trait_pred) if trait_pred.is_const_if_const() => {} |
3c0e092e XL |
1156 | // auto trait impl |
1157 | AutoImplCandidate(..) => {} | |
1158 | // generator, this will raise error in other places | |
1159 | // or ignore error with const_async_blocks feature | |
1160 | GeneratorCandidate => {} | |
1161 | // FnDef where the function is const | |
1162 | FnPointerCandidate { is_const: true } => {} | |
ee023bcb | 1163 | ConstDestructCandidate(_) => {} |
3c0e092e XL |
1164 | _ => { |
1165 | // reject all other types of candidates | |
1166 | continue; | |
1167 | } | |
94222f64 XL |
1168 | } |
1169 | } | |
3c0e092e XL |
1170 | |
1171 | if let ImplCandidate(def_id) = candidate { | |
1172 | if ty::ImplPolarity::Reservation == tcx.impl_polarity(def_id) | |
1173 | || obligation.polarity() == tcx.impl_polarity(def_id) | |
3c0e092e XL |
1174 | { |
1175 | result.push(candidate); | |
1176 | } | |
1177 | } else { | |
1178 | result.push(candidate); | |
1179 | } | |
94222f64 | 1180 | } |
3c0e092e XL |
1181 | |
1182 | result | |
1183 | } | |
1184 | ||
1185 | /// filter_reservation_impls filter reservation impl for any goal as ambiguous | |
1186 | #[instrument(level = "debug", skip(self))] | |
1187 | fn filter_reservation_impls( | |
1188 | &mut self, | |
1189 | candidate: SelectionCandidate<'tcx>, | |
1190 | obligation: &TraitObligation<'tcx>, | |
1191 | ) -> SelectionResult<'tcx, SelectionCandidate<'tcx>> { | |
1192 | let tcx = self.tcx(); | |
1193 | // Treat reservation impls as ambiguity. | |
74b04a01 | 1194 | if let ImplCandidate(def_id) = candidate { |
3c0e092e XL |
1195 | if let ty::ImplPolarity::Reservation = tcx.impl_polarity(def_id) { |
1196 | if let Some(intercrate_ambiguity_clauses) = &mut self.intercrate_ambiguity_causes { | |
1197 | let attrs = tcx.get_attrs(def_id); | |
1198 | let attr = tcx.sess.find_by_name(&attrs, sym::rustc_reservation_impl); | |
1199 | let value = attr.and_then(|a| a.value_str()); | |
1200 | if let Some(value) = value { | |
1201 | debug!( | |
1202 | "filter_reservation_impls: \ | |
74b04a01 | 1203 | reservation impl ambiguity on {:?}", |
3c0e092e XL |
1204 | def_id |
1205 | ); | |
1206 | intercrate_ambiguity_clauses.push( | |
1207 | IntercrateAmbiguityCause::ReservationImpl { | |
1208 | message: value.to_string(), | |
1209 | }, | |
1210 | ); | |
74b04a01 | 1211 | } |
74b04a01 | 1212 | } |
3c0e092e XL |
1213 | return Ok(None); |
1214 | } | |
74b04a01 XL |
1215 | } |
1216 | Ok(Some(candidate)) | |
1217 | } | |
1218 | ||
74b04a01 XL |
1219 | fn is_knowable<'o>(&mut self, stack: &TraitObligationStack<'o, 'tcx>) -> Option<Conflict> { |
1220 | debug!("is_knowable(intercrate={:?})", self.intercrate); | |
1221 | ||
3c0e092e | 1222 | if !self.intercrate || stack.obligation.polarity() == ty::ImplPolarity::Negative { |
74b04a01 XL |
1223 | return None; |
1224 | } | |
1225 | ||
1226 | let obligation = &stack.obligation; | |
fc512014 | 1227 | let predicate = self.infcx().resolve_vars_if_possible(obligation.predicate); |
74b04a01 XL |
1228 | |
1229 | // Okay to skip binder because of the nature of the | |
1230 | // trait-ref-is-knowable check, which does not care about | |
1231 | // bound regions. | |
1232 | let trait_ref = predicate.skip_binder().trait_ref; | |
1233 | ||
1234 | coherence::trait_ref_is_knowable(self.tcx(), trait_ref) | |
1235 | } | |
1236 | ||
1237 | /// Returns `true` if the global caches can be used. | |
74b04a01 | 1238 | fn can_use_global_caches(&self, param_env: ty::ParamEnv<'tcx>) -> bool { |
ba9703b0 | 1239 | // If there are any inference variables in the `ParamEnv`, then we |
74b04a01 XL |
1240 | // always use a cache local to this particular scope. Otherwise, we |
1241 | // switch to a global cache. | |
ba9703b0 | 1242 | if param_env.needs_infer() { |
74b04a01 XL |
1243 | return false; |
1244 | } | |
1245 | ||
1246 | // Avoid using the master cache during coherence and just rely | |
1247 | // on the local cache. This effectively disables caching | |
1248 | // during coherence. It is really just a simplification to | |
1249 | // avoid us having to fear that coherence results "pollute" | |
1250 | // the master cache. Since coherence executes pretty quickly, | |
1251 | // it's not worth going to more trouble to increase the | |
1252 | // hit-rate, I don't think. | |
1253 | if self.intercrate { | |
1254 | return false; | |
1255 | } | |
1256 | ||
1257 | // Otherwise, we can use the global cache. | |
1258 | true | |
1259 | } | |
1260 | ||
1261 | fn check_candidate_cache( | |
1262 | &mut self, | |
a2a8927a | 1263 | mut param_env: ty::ParamEnv<'tcx>, |
f9f354fc | 1264 | cache_fresh_trait_pred: ty::PolyTraitPredicate<'tcx>, |
74b04a01 | 1265 | ) -> Option<SelectionResult<'tcx, SelectionCandidate<'tcx>>> { |
94222f64 XL |
1266 | // Neither the global nor local cache is aware of intercrate |
1267 | // mode, so don't do any caching. In particular, we might | |
1268 | // re-use the same `InferCtxt` with both an intercrate | |
1269 | // and non-intercrate `SelectionContext` | |
1270 | if self.intercrate { | |
1271 | return None; | |
1272 | } | |
74b04a01 | 1273 | let tcx = self.tcx(); |
a2a8927a XL |
1274 | let mut pred = cache_fresh_trait_pred.skip_binder(); |
1275 | pred.remap_constness(tcx, &mut param_env); | |
1276 | ||
74b04a01 | 1277 | if self.can_use_global_caches(param_env) { |
ee023bcb | 1278 | if let Some(res) = tcx.selection_cache.get(&(param_env, pred), tcx) { |
3dfed10e | 1279 | return Some(res); |
74b04a01 XL |
1280 | } |
1281 | } | |
ee023bcb | 1282 | self.infcx.selection_cache.get(&(param_env, pred), tcx) |
74b04a01 XL |
1283 | } |
1284 | ||
1285 | /// Determines whether can we safely cache the result | |
1286 | /// of selecting an obligation. This is almost always `true`, | |
1287 | /// except when dealing with certain `ParamCandidate`s. | |
1288 | /// | |
1289 | /// Ordinarily, a `ParamCandidate` will contain no inference variables, | |
1290 | /// since it was usually produced directly from a `DefId`. However, | |
1291 | /// certain cases (currently only librustdoc's blanket impl finder), | |
1292 | /// a `ParamEnv` may be explicitly constructed with inference types. | |
1293 | /// When this is the case, we do *not* want to cache the resulting selection | |
1294 | /// candidate. This is due to the fact that it might not always be possible | |
1295 | /// to equate the obligation's trait ref and the candidate's trait ref, | |
1296 | /// if more constraints end up getting added to an inference variable. | |
1297 | /// | |
1298 | /// Because of this, we always want to re-run the full selection | |
1299 | /// process for our obligation the next time we see it, since | |
1300 | /// we might end up picking a different `SelectionCandidate` (or none at all). | |
1301 | fn can_cache_candidate( | |
1302 | &self, | |
1303 | result: &SelectionResult<'tcx, SelectionCandidate<'tcx>>, | |
1304 | ) -> bool { | |
94222f64 XL |
1305 | // Neither the global nor local cache is aware of intercrate |
1306 | // mode, so don't do any caching. In particular, we might | |
1307 | // re-use the same `InferCtxt` with both an intercrate | |
1308 | // and non-intercrate `SelectionContext` | |
1309 | if self.intercrate { | |
1310 | return false; | |
1311 | } | |
74b04a01 | 1312 | match result { |
ba9703b0 | 1313 | Ok(Some(SelectionCandidate::ParamCandidate(trait_ref))) => !trait_ref.needs_infer(), |
74b04a01 XL |
1314 | _ => true, |
1315 | } | |
1316 | } | |
1317 | ||
ee023bcb | 1318 | #[instrument(skip(self, param_env, cache_fresh_trait_pred, dep_node), level = "debug")] |
74b04a01 XL |
1319 | fn insert_candidate_cache( |
1320 | &mut self, | |
a2a8927a | 1321 | mut param_env: ty::ParamEnv<'tcx>, |
74b04a01 XL |
1322 | cache_fresh_trait_pred: ty::PolyTraitPredicate<'tcx>, |
1323 | dep_node: DepNodeIndex, | |
1324 | candidate: SelectionResult<'tcx, SelectionCandidate<'tcx>>, | |
1325 | ) { | |
1326 | let tcx = self.tcx(); | |
a2a8927a XL |
1327 | let mut pred = cache_fresh_trait_pred.skip_binder(); |
1328 | ||
1329 | pred.remap_constness(tcx, &mut param_env); | |
74b04a01 XL |
1330 | |
1331 | if !self.can_cache_candidate(&candidate) { | |
a2a8927a | 1332 | debug!(?pred, ?candidate, "insert_candidate_cache - candidate is not cacheable"); |
74b04a01 XL |
1333 | return; |
1334 | } | |
1335 | ||
1336 | if self.can_use_global_caches(param_env) { | |
ee023bcb | 1337 | if let Err(Overflow(OverflowError::Canonical)) = candidate { |
74b04a01 | 1338 | // Don't cache overflow globally; we only produce this in certain modes. |
a2a8927a | 1339 | } else if !pred.needs_infer() { |
ba9703b0 | 1340 | if !candidate.needs_infer() { |
a2a8927a | 1341 | debug!(?pred, ?candidate, "insert_candidate_cache global"); |
74b04a01 | 1342 | // This may overwrite the cache with the same value. |
ee023bcb | 1343 | tcx.selection_cache.insert((param_env, pred), dep_node, candidate); |
74b04a01 XL |
1344 | return; |
1345 | } | |
1346 | } | |
1347 | } | |
1348 | ||
a2a8927a | 1349 | debug!(?pred, ?candidate, "insert_candidate_cache local"); |
ee023bcb | 1350 | self.infcx.selection_cache.insert((param_env, pred), dep_node, candidate); |
74b04a01 XL |
1351 | } |
1352 | ||
29967ef6 XL |
1353 | /// Matches a predicate against the bounds of its self type. |
1354 | /// | |
1355 | /// Given an obligation like `<T as Foo>::Bar: Baz` where the self type is | |
1356 | /// a projection, look at the bounds of `T::Bar`, see if we can find a | |
1357 | /// `Baz` bound. We return indexes into the list returned by | |
1358 | /// `tcx.item_bounds` for any applicable bounds. | |
ee023bcb | 1359 | #[instrument(level = "debug", skip(self))] |
74b04a01 XL |
1360 | fn match_projection_obligation_against_definition_bounds( |
1361 | &mut self, | |
1362 | obligation: &TraitObligation<'tcx>, | |
29967ef6 | 1363 | ) -> smallvec::SmallVec<[usize; 2]> { |
fc512014 | 1364 | let poly_trait_predicate = self.infcx().resolve_vars_if_possible(obligation.predicate); |
29967ef6 | 1365 | let placeholder_trait_predicate = |
fc512014 | 1366 | self.infcx().replace_bound_vars_with_placeholders(poly_trait_predicate); |
ee023bcb | 1367 | debug!(?placeholder_trait_predicate); |
74b04a01 | 1368 | |
f035d41b | 1369 | let tcx = self.infcx.tcx; |
29967ef6 XL |
1370 | let (def_id, substs) = match *placeholder_trait_predicate.trait_ref.self_ty().kind() { |
1371 | ty::Projection(ref data) => (data.item_def_id, data.substs), | |
1372 | ty::Opaque(def_id, substs) => (def_id, substs), | |
74b04a01 XL |
1373 | _ => { |
1374 | span_bug!( | |
1375 | obligation.cause.span, | |
1376 | "match_projection_obligation_against_definition_bounds() called \ | |
1377 | but self-ty is not a projection: {:?}", | |
1378 | placeholder_trait_predicate.trait_ref.self_ty() | |
1379 | ); | |
1380 | } | |
1381 | }; | |
29967ef6 | 1382 | let bounds = tcx.item_bounds(def_id).subst(tcx, substs); |
74b04a01 | 1383 | |
29967ef6 XL |
1384 | // The bounds returned by `item_bounds` may contain duplicates after |
1385 | // normalization, so try to deduplicate when possible to avoid | |
1386 | // unnecessary ambiguity. | |
1387 | let mut distinct_normalized_bounds = FxHashSet::default(); | |
1388 | ||
1389 | let matching_bounds = bounds | |
1390 | .iter() | |
1391 | .enumerate() | |
1392 | .filter_map(|(idx, bound)| { | |
5869c6ff | 1393 | let bound_predicate = bound.kind(); |
94222f64 | 1394 | if let ty::PredicateKind::Trait(pred) = bound_predicate.skip_binder() { |
29967ef6 XL |
1395 | let bound = bound_predicate.rebind(pred.trait_ref); |
1396 | if self.infcx.probe(|_| { | |
1397 | match self.match_normalize_trait_ref( | |
1398 | obligation, | |
1399 | bound, | |
1400 | placeholder_trait_predicate.trait_ref, | |
1401 | ) { | |
1402 | Ok(None) => true, | |
1403 | Ok(Some(normalized_trait)) | |
1404 | if distinct_normalized_bounds.insert(normalized_trait) => | |
1405 | { | |
1406 | true | |
1407 | } | |
1408 | _ => false, | |
1409 | } | |
1410 | }) { | |
1411 | return Some(idx); | |
1412 | } | |
f035d41b | 1413 | } |
29967ef6 XL |
1414 | None |
1415 | }) | |
1416 | .collect(); | |
74b04a01 | 1417 | |
ee023bcb | 1418 | debug!(?matching_bounds); |
29967ef6 | 1419 | matching_bounds |
74b04a01 XL |
1420 | } |
1421 | ||
29967ef6 XL |
1422 | /// Equates the trait in `obligation` with trait bound. If the two traits |
1423 | /// can be equated and the normalized trait bound doesn't contain inference | |
1424 | /// variables or placeholders, the normalized bound is returned. | |
1425 | fn match_normalize_trait_ref( | |
74b04a01 XL |
1426 | &mut self, |
1427 | obligation: &TraitObligation<'tcx>, | |
1428 | trait_bound: ty::PolyTraitRef<'tcx>, | |
1429 | placeholder_trait_ref: ty::TraitRef<'tcx>, | |
29967ef6 | 1430 | ) -> Result<Option<ty::PolyTraitRef<'tcx>>, ()> { |
74b04a01 | 1431 | debug_assert!(!placeholder_trait_ref.has_escaping_bound_vars()); |
29967ef6 XL |
1432 | if placeholder_trait_ref.def_id != trait_bound.def_id() { |
1433 | // Avoid unnecessary normalization | |
1434 | return Err(()); | |
1435 | } | |
1436 | ||
1437 | let Normalized { value: trait_bound, obligations: _ } = ensure_sufficient_stack(|| { | |
1438 | project::normalize_with_depth( | |
1439 | self, | |
1440 | obligation.param_env, | |
1441 | obligation.cause.clone(), | |
1442 | obligation.recursion_depth + 1, | |
fc512014 | 1443 | trait_bound, |
29967ef6 XL |
1444 | ) |
1445 | }); | |
74b04a01 XL |
1446 | self.infcx |
1447 | .at(&obligation.cause, obligation.param_env) | |
ee023bcb | 1448 | .define_opaque_types(false) |
74b04a01 | 1449 | .sup(ty::Binder::dummy(placeholder_trait_ref), trait_bound) |
29967ef6 XL |
1450 | .map(|InferOk { obligations: _, value: () }| { |
1451 | // This method is called within a probe, so we can't have | |
1452 | // inference variables and placeholders escape. | |
1453 | if !trait_bound.needs_infer() && !trait_bound.has_placeholders() { | |
1454 | Some(trait_bound) | |
1455 | } else { | |
1456 | None | |
1457 | } | |
1458 | }) | |
1459 | .map_err(|_| ()) | |
74b04a01 XL |
1460 | } |
1461 | ||
ee023bcb | 1462 | fn where_clause_may_apply<'o>( |
74b04a01 XL |
1463 | &mut self, |
1464 | stack: &TraitObligationStack<'o, 'tcx>, | |
1465 | where_clause_trait_ref: ty::PolyTraitRef<'tcx>, | |
1466 | ) -> Result<EvaluationResult, OverflowError> { | |
1467 | self.evaluation_probe(|this| { | |
1468 | match this.match_where_clause_trait_ref(stack.obligation, where_clause_trait_ref) { | |
29967ef6 | 1469 | Ok(obligations) => this.evaluate_predicates_recursively(stack.list(), obligations), |
74b04a01 XL |
1470 | Err(()) => Ok(EvaluatedToErr), |
1471 | } | |
1472 | }) | |
1473 | } | |
1474 | ||
5099ac24 FG |
1475 | /// Return `Yes` if the obligation's predicate type applies to the env_predicate, and |
1476 | /// `No` if it does not. Return `Ambiguous` in the case that the projection type is a GAT, | |
1477 | /// and applying this env_predicate constrains any of the obligation's GAT substitutions. | |
1478 | /// | |
ee023bcb | 1479 | /// This behavior is a somewhat of a hack to prevent over-constraining inference variables |
5099ac24 | 1480 | /// in cases like #91762. |
29967ef6 XL |
1481 | pub(super) fn match_projection_projections( |
1482 | &mut self, | |
1483 | obligation: &ProjectionTyObligation<'tcx>, | |
6a06907d | 1484 | env_predicate: PolyProjectionPredicate<'tcx>, |
29967ef6 | 1485 | potentially_unnormalized_candidates: bool, |
5099ac24 | 1486 | ) -> ProjectionMatchesProjection { |
29967ef6 | 1487 | let mut nested_obligations = Vec::new(); |
6a06907d XL |
1488 | let (infer_predicate, _) = self.infcx.replace_bound_vars_with_fresh_vars( |
1489 | obligation.cause.span, | |
1490 | LateBoundRegionConversionTime::HigherRankedType, | |
1491 | env_predicate, | |
1492 | ); | |
1493 | let infer_projection = if potentially_unnormalized_candidates { | |
29967ef6 XL |
1494 | ensure_sufficient_stack(|| { |
1495 | project::normalize_with_depth_to( | |
1496 | self, | |
1497 | obligation.param_env, | |
1498 | obligation.cause.clone(), | |
1499 | obligation.recursion_depth + 1, | |
6a06907d | 1500 | infer_predicate.projection_ty, |
29967ef6 XL |
1501 | &mut nested_obligations, |
1502 | ) | |
1503 | }) | |
1504 | } else { | |
6a06907d | 1505 | infer_predicate.projection_ty |
29967ef6 XL |
1506 | }; |
1507 | ||
5099ac24 FG |
1508 | let is_match = self |
1509 | .infcx | |
29967ef6 | 1510 | .at(&obligation.cause, obligation.param_env) |
ee023bcb | 1511 | .define_opaque_types(false) |
6a06907d | 1512 | .sup(obligation.predicate, infer_projection) |
29967ef6 XL |
1513 | .map_or(false, |InferOk { obligations, value: () }| { |
1514 | self.evaluate_predicates_recursively( | |
1515 | TraitObligationStackList::empty(&ProvisionalEvaluationCache::default()), | |
1516 | nested_obligations.into_iter().chain(obligations), | |
1517 | ) | |
1518 | .map_or(false, |res| res.may_apply()) | |
5099ac24 FG |
1519 | }); |
1520 | ||
1521 | if is_match { | |
1522 | let generics = self.tcx().generics_of(obligation.predicate.item_def_id); | |
1523 | // FIXME(generic-associated-types): Addresses aggressive inference in #92917. | |
1524 | // If this type is a GAT, and of the GAT substs resolve to something new, | |
1525 | // that means that we must have newly inferred something about the GAT. | |
1526 | // We should give up in that case. | |
1527 | if !generics.params.is_empty() | |
1528 | && obligation.predicate.substs[generics.parent_count..] | |
1529 | .iter() | |
1530 | .any(|&p| p.has_infer_types_or_consts() && self.infcx.shallow_resolve(p) != p) | |
1531 | { | |
1532 | ProjectionMatchesProjection::Ambiguous | |
1533 | } else { | |
1534 | ProjectionMatchesProjection::Yes | |
1535 | } | |
1536 | } else { | |
1537 | ProjectionMatchesProjection::No | |
1538 | } | |
29967ef6 XL |
1539 | } |
1540 | ||
74b04a01 XL |
1541 | /////////////////////////////////////////////////////////////////////////// |
1542 | // WINNOW | |
1543 | // | |
1544 | // Winnowing is the process of attempting to resolve ambiguity by | |
1545 | // probing further. During the winnowing process, we unify all | |
1546 | // type variables and then we also attempt to evaluate recursive | |
1547 | // bounds to see if they are satisfied. | |
1548 | ||
1549 | /// Returns `true` if `victim` should be dropped in favor of | |
1550 | /// `other`. Generally speaking we will drop duplicate | |
1551 | /// candidates and prefer where-clause candidates. | |
1552 | /// | |
1553 | /// See the comment for "SelectionCandidate" for more details. | |
1554 | fn candidate_should_be_dropped_in_favor_of( | |
1555 | &mut self, | |
1556 | victim: &EvaluatedCandidate<'tcx>, | |
1557 | other: &EvaluatedCandidate<'tcx>, | |
1558 | needs_infer: bool, | |
1559 | ) -> bool { | |
1560 | if victim.candidate == other.candidate { | |
1561 | return true; | |
1562 | } | |
1563 | ||
1564 | // Check if a bound would previously have been removed when normalizing | |
1565 | // the param_env so that it can be given the lowest priority. See | |
1566 | // #50825 for the motivation for this. | |
a2a8927a | 1567 | let is_global = |cand: &ty::PolyTraitPredicate<'tcx>| { |
5099ac24 | 1568 | cand.is_global() && !cand.has_late_bound_regions() |
3c0e092e | 1569 | }; |
74b04a01 | 1570 | |
6a06907d | 1571 | // (*) Prefer `BuiltinCandidate { has_nested: false }`, `PointeeCandidate`, |
ee023bcb | 1572 | // `DiscriminantKindCandidate`, and `ConstDestructCandidate` to anything else. |
f9f354fc XL |
1573 | // |
1574 | // This is a fix for #53123 and prevents winnowing from accidentally extending the | |
1575 | // lifetime of a variable. | |
29967ef6 XL |
1576 | match (&other.candidate, &victim.candidate) { |
1577 | (_, AutoImplCandidate(..)) | (AutoImplCandidate(..), _) => { | |
1578 | bug!( | |
1579 | "default implementations shouldn't be recorded \ | |
1580 | when there are other valid candidates" | |
1581 | ); | |
1582 | } | |
1583 | ||
f9f354fc | 1584 | // (*) |
6a06907d XL |
1585 | ( |
1586 | BuiltinCandidate { has_nested: false } | |
1587 | | DiscriminantKindCandidate | |
c295e0f8 | 1588 | | PointeeCandidate |
ee023bcb | 1589 | | ConstDestructCandidate(_), |
6a06907d XL |
1590 | _, |
1591 | ) => true, | |
1592 | ( | |
1593 | _, | |
1594 | BuiltinCandidate { has_nested: false } | |
1595 | | DiscriminantKindCandidate | |
c295e0f8 | 1596 | | PointeeCandidate |
ee023bcb | 1597 | | ConstDestructCandidate(_), |
6a06907d | 1598 | ) => false, |
29967ef6 | 1599 | |
a2a8927a XL |
1600 | (ParamCandidate(other), ParamCandidate(victim)) => { |
1601 | let same_except_bound_vars = other.skip_binder().trait_ref | |
1602 | == victim.skip_binder().trait_ref | |
1603 | && other.skip_binder().constness == victim.skip_binder().constness | |
1604 | && other.skip_binder().polarity == victim.skip_binder().polarity | |
1605 | && !other.skip_binder().trait_ref.has_escaping_bound_vars(); | |
c295e0f8 | 1606 | if same_except_bound_vars { |
cdc7bbd5 XL |
1607 | // See issue #84398. In short, we can generate multiple ParamCandidates which are |
1608 | // the same except for unused bound vars. Just pick the one with the fewest bound vars | |
1609 | // or the current one if tied (they should both evaluate to the same answer). This is | |
1610 | // probably best characterized as a "hack", since we might prefer to just do our | |
1611 | // best to *not* create essentially duplicate candidates in the first place. | |
a2a8927a XL |
1612 | other.bound_vars().len() <= victim.bound_vars().len() |
1613 | } else if other.skip_binder().trait_ref == victim.skip_binder().trait_ref | |
1614 | && victim.skip_binder().constness == ty::BoundConstness::NotConst | |
1615 | && other.skip_binder().polarity == victim.skip_binder().polarity | |
94222f64 | 1616 | { |
fc512014 XL |
1617 | // Drop otherwise equivalent non-const candidates in favor of const candidates. |
1618 | true | |
1619 | } else { | |
1620 | false | |
1621 | } | |
1622 | } | |
29967ef6 | 1623 | |
c295e0f8 XL |
1624 | // Drop otherwise equivalent non-const fn pointer candidates |
1625 | (FnPointerCandidate { .. }, FnPointerCandidate { is_const: false }) => true, | |
1626 | ||
29967ef6 XL |
1627 | // Global bounds from the where clause should be ignored |
1628 | // here (see issue #50825). Otherwise, we have a where | |
1629 | // clause so don't go around looking for impls. | |
1630 | // Arbitrarily give param candidates priority | |
1631 | // over projection and object candidates. | |
1632 | ( | |
1633 | ParamCandidate(ref cand), | |
74b04a01 XL |
1634 | ImplCandidate(..) |
1635 | | ClosureCandidate | |
1636 | | GeneratorCandidate | |
c295e0f8 | 1637 | | FnPointerCandidate { .. } |
74b04a01 XL |
1638 | | BuiltinObjectCandidate |
1639 | | BuiltinUnsizeCandidate | |
94222f64 | 1640 | | TraitUpcastingUnsizeCandidate(_) |
74b04a01 | 1641 | | BuiltinCandidate { .. } |
ee023bcb FG |
1642 | | TraitAliasCandidate(..) |
1643 | | ObjectCandidate(_) | |
1644 | | ProjectionCandidate(_), | |
a2a8927a | 1645 | ) => !is_global(cand), |
ee023bcb FG |
1646 | (ObjectCandidate(_) | ProjectionCandidate(_), ParamCandidate(ref cand)) => { |
1647 | // Prefer these to a global where-clause bound | |
1648 | // (see issue #50825). | |
1649 | is_global(cand) | |
1650 | } | |
29967ef6 XL |
1651 | ( |
1652 | ImplCandidate(_) | |
1653 | | ClosureCandidate | |
1654 | | GeneratorCandidate | |
c295e0f8 | 1655 | | FnPointerCandidate { .. } |
29967ef6 XL |
1656 | | BuiltinObjectCandidate |
1657 | | BuiltinUnsizeCandidate | |
94222f64 | 1658 | | TraitUpcastingUnsizeCandidate(_) |
29967ef6 XL |
1659 | | BuiltinCandidate { has_nested: true } |
1660 | | TraitAliasCandidate(..), | |
1661 | ParamCandidate(ref cand), | |
1662 | ) => { | |
1663 | // Prefer these to a global where-clause bound | |
1664 | // (see issue #50825). | |
a2a8927a | 1665 | is_global(cand) && other.evaluation.must_apply_modulo_regions() |
29967ef6 XL |
1666 | } |
1667 | ||
1668 | (ProjectionCandidate(i), ProjectionCandidate(j)) | |
1669 | | (ObjectCandidate(i), ObjectCandidate(j)) => { | |
1670 | // Arbitrarily pick the lower numbered candidate for backwards | |
1671 | // compatibility reasons. Don't let this affect inference. | |
1672 | i < j && !needs_infer | |
1673 | } | |
1674 | (ObjectCandidate(_), ProjectionCandidate(_)) | |
1675 | | (ProjectionCandidate(_), ObjectCandidate(_)) => { | |
1676 | bug!("Have both object and projection candidate") | |
1677 | } | |
1678 | ||
1679 | // Arbitrarily give projection and object candidates priority. | |
1680 | ( | |
1681 | ObjectCandidate(_) | ProjectionCandidate(_), | |
74b04a01 XL |
1682 | ImplCandidate(..) |
1683 | | ClosureCandidate | |
1684 | | GeneratorCandidate | |
c295e0f8 | 1685 | | FnPointerCandidate { .. } |
74b04a01 XL |
1686 | | BuiltinObjectCandidate |
1687 | | BuiltinUnsizeCandidate | |
94222f64 | 1688 | | TraitUpcastingUnsizeCandidate(_) |
74b04a01 | 1689 | | BuiltinCandidate { .. } |
29967ef6 XL |
1690 | | TraitAliasCandidate(..), |
1691 | ) => true, | |
1692 | ||
1693 | ( | |
1694 | ImplCandidate(..) | |
1695 | | ClosureCandidate | |
1696 | | GeneratorCandidate | |
c295e0f8 | 1697 | | FnPointerCandidate { .. } |
29967ef6 XL |
1698 | | BuiltinObjectCandidate |
1699 | | BuiltinUnsizeCandidate | |
94222f64 | 1700 | | TraitUpcastingUnsizeCandidate(_) |
29967ef6 XL |
1701 | | BuiltinCandidate { .. } |
1702 | | TraitAliasCandidate(..), | |
1703 | ObjectCandidate(_) | ProjectionCandidate(_), | |
1704 | ) => false, | |
1705 | ||
1706 | (&ImplCandidate(other_def), &ImplCandidate(victim_def)) => { | |
74b04a01 XL |
1707 | // See if we can toss out `victim` based on specialization. |
1708 | // This requires us to know *for sure* that the `other` impl applies | |
1709 | // i.e., `EvaluatedToOk`. | |
94222f64 XL |
1710 | // |
1711 | // FIXME(@lcnr): Using `modulo_regions` here seems kind of scary | |
1712 | // to me but is required for `std` to compile, so I didn't change it | |
1713 | // for now. | |
1714 | let tcx = self.tcx(); | |
74b04a01 | 1715 | if other.evaluation.must_apply_modulo_regions() { |
29967ef6 XL |
1716 | if tcx.specializes((other_def, victim_def)) { |
1717 | return true; | |
74b04a01 | 1718 | } |
94222f64 XL |
1719 | } |
1720 | ||
1721 | if other.evaluation.must_apply_considering_regions() { | |
1722 | match tcx.impls_are_allowed_to_overlap(other_def, victim_def) { | |
29967ef6 XL |
1723 | Some(ty::ImplOverlapKind::Permitted { marker: true }) => { |
1724 | // Subtle: If the predicate we are evaluating has inference | |
1725 | // variables, do *not* allow discarding candidates due to | |
1726 | // marker trait impls. | |
1727 | // | |
1728 | // Without this restriction, we could end up accidentally | |
ee023bcb | 1729 | // constraining inference variables based on an arbitrarily |
29967ef6 XL |
1730 | // chosen trait impl. |
1731 | // | |
1732 | // Imagine we have the following code: | |
1733 | // | |
1734 | // ```rust | |
1735 | // #[marker] trait MyTrait {} | |
1736 | // impl MyTrait for u8 {} | |
1737 | // impl MyTrait for bool {} | |
1738 | // ``` | |
1739 | // | |
1740 | // And we are evaluating the predicate `<_#0t as MyTrait>`. | |
1741 | // | |
1742 | // During selection, we will end up with one candidate for each | |
1743 | // impl of `MyTrait`. If we were to discard one impl in favor | |
1744 | // of the other, we would be left with one candidate, causing | |
1745 | // us to "successfully" select the predicate, unifying | |
1746 | // _#0t with (for example) `u8`. | |
1747 | // | |
1748 | // However, we have no reason to believe that this unification | |
1749 | // is correct - we've essentially just picked an arbitrary | |
1750 | // *possibility* for _#0t, and required that this be the *only* | |
1751 | // possibility. | |
1752 | // | |
1753 | // Eventually, we will either: | |
1754 | // 1) Unify all inference variables in the predicate through | |
1755 | // some other means (e.g. type-checking of a function). We will | |
1756 | // then be in a position to drop marker trait candidates | |
1757 | // without constraining inference variables (since there are | |
ee023bcb | 1758 | // none left to constrain) |
29967ef6 XL |
1759 | // 2) Be left with some unconstrained inference variables. We |
1760 | // will then correctly report an inference error, since the | |
1761 | // existence of multiple marker trait impls tells us nothing | |
1762 | // about which one should actually apply. | |
1763 | !needs_infer | |
1764 | } | |
1765 | Some(_) => true, | |
1766 | None => false, | |
94222f64 | 1767 | } |
29967ef6 XL |
1768 | } else { |
1769 | false | |
74b04a01 XL |
1770 | } |
1771 | } | |
29967ef6 XL |
1772 | |
1773 | // Everything else is ambiguous | |
1774 | ( | |
1775 | ImplCandidate(_) | |
1776 | | ClosureCandidate | |
1777 | | GeneratorCandidate | |
c295e0f8 | 1778 | | FnPointerCandidate { .. } |
29967ef6 XL |
1779 | | BuiltinObjectCandidate |
1780 | | BuiltinUnsizeCandidate | |
94222f64 | 1781 | | TraitUpcastingUnsizeCandidate(_) |
29967ef6 XL |
1782 | | BuiltinCandidate { has_nested: true } |
1783 | | TraitAliasCandidate(..), | |
1784 | ImplCandidate(_) | |
1785 | | ClosureCandidate | |
1786 | | GeneratorCandidate | |
c295e0f8 | 1787 | | FnPointerCandidate { .. } |
29967ef6 XL |
1788 | | BuiltinObjectCandidate |
1789 | | BuiltinUnsizeCandidate | |
94222f64 | 1790 | | TraitUpcastingUnsizeCandidate(_) |
29967ef6 XL |
1791 | | BuiltinCandidate { has_nested: true } |
1792 | | TraitAliasCandidate(..), | |
1793 | ) => false, | |
74b04a01 XL |
1794 | } |
1795 | } | |
1796 | ||
74b04a01 XL |
1797 | fn sized_conditions( |
1798 | &mut self, | |
1799 | obligation: &TraitObligation<'tcx>, | |
1800 | ) -> BuiltinImplConditions<'tcx> { | |
1801 | use self::BuiltinImplConditions::{Ambiguous, None, Where}; | |
1802 | ||
1803 | // NOTE: binder moved to (*) | |
1804 | let self_ty = self.infcx.shallow_resolve(obligation.predicate.skip_binder().self_ty()); | |
1805 | ||
1b1a35ee | 1806 | match self_ty.kind() { |
ba9703b0 | 1807 | ty::Infer(ty::IntVar(_) | ty::FloatVar(_)) |
74b04a01 XL |
1808 | | ty::Uint(_) |
1809 | | ty::Int(_) | |
1810 | | ty::Bool | |
1811 | | ty::Float(_) | |
1812 | | ty::FnDef(..) | |
1813 | | ty::FnPtr(_) | |
1814 | | ty::RawPtr(..) | |
1815 | | ty::Char | |
1816 | | ty::Ref(..) | |
1817 | | ty::Generator(..) | |
1818 | | ty::GeneratorWitness(..) | |
1819 | | ty::Array(..) | |
1820 | | ty::Closure(..) | |
1821 | | ty::Never | |
f035d41b | 1822 | | ty::Error(_) => { |
74b04a01 XL |
1823 | // safe for everything |
1824 | Where(ty::Binder::dummy(Vec::new())) | |
1825 | } | |
1826 | ||
1827 | ty::Str | ty::Slice(_) | ty::Dynamic(..) | ty::Foreign(..) => None, | |
1828 | ||
29967ef6 | 1829 | ty::Tuple(tys) => Where( |
ee023bcb | 1830 | obligation.predicate.rebind(tys.last().map_or_else(Vec::new, |&last| vec![last])), |
29967ef6 | 1831 | ), |
74b04a01 XL |
1832 | |
1833 | ty::Adt(def, substs) => { | |
1834 | let sized_crit = def.sized_constraint(self.tcx()); | |
1835 | // (*) binder moved here | |
29967ef6 XL |
1836 | Where( |
1837 | obligation.predicate.rebind({ | |
1838 | sized_crit.iter().map(|ty| ty.subst(self.tcx(), substs)).collect() | |
1839 | }), | |
1840 | ) | |
74b04a01 XL |
1841 | } |
1842 | ||
1843 | ty::Projection(_) | ty::Param(_) | ty::Opaque(..) => None, | |
1844 | ty::Infer(ty::TyVar(_)) => Ambiguous, | |
1845 | ||
f9f354fc | 1846 | ty::Placeholder(..) |
74b04a01 | 1847 | | ty::Bound(..) |
ba9703b0 | 1848 | | ty::Infer(ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => { |
74b04a01 XL |
1849 | bug!("asked to assemble builtin bounds of unexpected type: {:?}", self_ty); |
1850 | } | |
1851 | } | |
1852 | } | |
1853 | ||
1854 | fn copy_clone_conditions( | |
1855 | &mut self, | |
1856 | obligation: &TraitObligation<'tcx>, | |
1857 | ) -> BuiltinImplConditions<'tcx> { | |
1858 | // NOTE: binder moved to (*) | |
1859 | let self_ty = self.infcx.shallow_resolve(obligation.predicate.skip_binder().self_ty()); | |
1860 | ||
1861 | use self::BuiltinImplConditions::{Ambiguous, None, Where}; | |
1862 | ||
29967ef6 | 1863 | match *self_ty.kind() { |
74b04a01 XL |
1864 | ty::Infer(ty::IntVar(_)) |
1865 | | ty::Infer(ty::FloatVar(_)) | |
1866 | | ty::FnDef(..) | |
1867 | | ty::FnPtr(_) | |
f035d41b | 1868 | | ty::Error(_) => Where(ty::Binder::dummy(Vec::new())), |
74b04a01 XL |
1869 | |
1870 | ty::Uint(_) | |
1871 | | ty::Int(_) | |
1872 | | ty::Bool | |
1873 | | ty::Float(_) | |
1874 | | ty::Char | |
1875 | | ty::RawPtr(..) | |
1876 | | ty::Never | |
3c0e092e XL |
1877 | | ty::Ref(_, _, hir::Mutability::Not) |
1878 | | ty::Array(..) => { | |
74b04a01 XL |
1879 | // Implementations provided in libcore |
1880 | None | |
1881 | } | |
1882 | ||
1883 | ty::Dynamic(..) | |
1884 | | ty::Str | |
1885 | | ty::Slice(..) | |
1886 | | ty::Generator(..) | |
1887 | | ty::GeneratorWitness(..) | |
1888 | | ty::Foreign(..) | |
1889 | | ty::Ref(_, _, hir::Mutability::Mut) => None, | |
1890 | ||
74b04a01 XL |
1891 | ty::Tuple(tys) => { |
1892 | // (*) binder moved here | |
ee023bcb | 1893 | Where(obligation.predicate.rebind(tys.iter().collect())) |
74b04a01 XL |
1894 | } |
1895 | ||
ba9703b0 | 1896 | ty::Closure(_, substs) => { |
74b04a01 | 1897 | // (*) binder moved here |
29967ef6 XL |
1898 | let ty = self.infcx.shallow_resolve(substs.as_closure().tupled_upvars_ty()); |
1899 | if let ty::Infer(ty::TyVar(_)) = ty.kind() { | |
1900 | // Not yet resolved. | |
1901 | Ambiguous | |
1902 | } else { | |
1903 | Where(obligation.predicate.rebind(substs.as_closure().upvar_tys().collect())) | |
1904 | } | |
74b04a01 XL |
1905 | } |
1906 | ||
1907 | ty::Adt(..) | ty::Projection(..) | ty::Param(..) | ty::Opaque(..) => { | |
1908 | // Fallback to whatever user-defined impls exist in this case. | |
1909 | None | |
1910 | } | |
1911 | ||
1912 | ty::Infer(ty::TyVar(_)) => { | |
1913 | // Unbound type variable. Might or might not have | |
1914 | // applicable impls and so forth, depending on what | |
1915 | // those type variables wind up being bound to. | |
1916 | Ambiguous | |
1917 | } | |
1918 | ||
f9f354fc | 1919 | ty::Placeholder(..) |
74b04a01 | 1920 | | ty::Bound(..) |
ba9703b0 | 1921 | | ty::Infer(ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => { |
74b04a01 XL |
1922 | bug!("asked to assemble builtin bounds of unexpected type: {:?}", self_ty); |
1923 | } | |
1924 | } | |
1925 | } | |
1926 | ||
1927 | /// For default impls, we need to break apart a type into its | |
1928 | /// "constituent types" -- meaning, the types that it contains. | |
1929 | /// | |
1930 | /// Here are some (simple) examples: | |
1931 | /// | |
1932 | /// ``` | |
1933 | /// (i32, u32) -> [i32, u32] | |
1934 | /// Foo where struct Foo { x: i32, y: u32 } -> [i32, u32] | |
1935 | /// Bar<i32> where struct Bar<T> { x: T, y: u32 } -> [i32, u32] | |
1936 | /// Zed<i32> where enum Zed { A(T), B(u32) } -> [i32, u32] | |
1937 | /// ``` | |
cdc7bbd5 XL |
1938 | fn constituent_types_for_ty( |
1939 | &self, | |
1940 | t: ty::Binder<'tcx, Ty<'tcx>>, | |
1941 | ) -> ty::Binder<'tcx, Vec<Ty<'tcx>>> { | |
fc512014 | 1942 | match *t.skip_binder().kind() { |
74b04a01 XL |
1943 | ty::Uint(_) |
1944 | | ty::Int(_) | |
1945 | | ty::Bool | |
1946 | | ty::Float(_) | |
1947 | | ty::FnDef(..) | |
1948 | | ty::FnPtr(_) | |
1949 | | ty::Str | |
f035d41b | 1950 | | ty::Error(_) |
ba9703b0 | 1951 | | ty::Infer(ty::IntVar(_) | ty::FloatVar(_)) |
74b04a01 | 1952 | | ty::Never |
fc512014 | 1953 | | ty::Char => ty::Binder::dummy(Vec::new()), |
74b04a01 | 1954 | |
f9f354fc | 1955 | ty::Placeholder(..) |
74b04a01 XL |
1956 | | ty::Dynamic(..) |
1957 | | ty::Param(..) | |
1958 | | ty::Foreign(..) | |
1959 | | ty::Projection(..) | |
1960 | | ty::Bound(..) | |
ba9703b0 | 1961 | | ty::Infer(ty::TyVar(_) | ty::FreshTy(_) | ty::FreshIntTy(_) | ty::FreshFloatTy(_)) => { |
74b04a01 XL |
1962 | bug!("asked to assemble constituent types of unexpected type: {:?}", t); |
1963 | } | |
1964 | ||
1965 | ty::RawPtr(ty::TypeAndMut { ty: element_ty, .. }) | ty::Ref(_, element_ty, _) => { | |
fc512014 | 1966 | t.rebind(vec![element_ty]) |
74b04a01 XL |
1967 | } |
1968 | ||
fc512014 | 1969 | ty::Array(element_ty, _) | ty::Slice(element_ty) => t.rebind(vec![element_ty]), |
74b04a01 XL |
1970 | |
1971 | ty::Tuple(ref tys) => { | |
1972 | // (T1, ..., Tn) -- meets any bound that all of T1...Tn meet | |
ee023bcb | 1973 | t.rebind(tys.iter().collect()) |
74b04a01 XL |
1974 | } |
1975 | ||
29967ef6 XL |
1976 | ty::Closure(_, ref substs) => { |
1977 | let ty = self.infcx.shallow_resolve(substs.as_closure().tupled_upvars_ty()); | |
fc512014 | 1978 | t.rebind(vec![ty]) |
29967ef6 | 1979 | } |
74b04a01 | 1980 | |
ba9703b0 | 1981 | ty::Generator(_, ref substs, _) => { |
29967ef6 | 1982 | let ty = self.infcx.shallow_resolve(substs.as_generator().tupled_upvars_ty()); |
ba9703b0 | 1983 | let witness = substs.as_generator().witness(); |
5099ac24 | 1984 | t.rebind([ty].into_iter().chain(iter::once(witness)).collect()) |
74b04a01 XL |
1985 | } |
1986 | ||
1987 | ty::GeneratorWitness(types) => { | |
fc512014 XL |
1988 | debug_assert!(!types.has_escaping_bound_vars()); |
1989 | types.map_bound(|types| types.to_vec()) | |
74b04a01 XL |
1990 | } |
1991 | ||
1992 | // For `PhantomData<T>`, we pass `T`. | |
fc512014 | 1993 | ty::Adt(def, substs) if def.is_phantom_data() => t.rebind(substs.types().collect()), |
74b04a01 | 1994 | |
fc512014 XL |
1995 | ty::Adt(def, substs) => { |
1996 | t.rebind(def.all_fields().map(|f| f.ty(self.tcx(), substs)).collect()) | |
1997 | } | |
74b04a01 XL |
1998 | |
1999 | ty::Opaque(def_id, substs) => { | |
2000 | // We can resolve the `impl Trait` to its concrete type, | |
2001 | // which enforces a DAG between the functions requiring | |
2002 | // the auto trait bounds in question. | |
fc512014 | 2003 | t.rebind(vec![self.tcx().type_of(def_id).subst(self.tcx(), substs)]) |
74b04a01 XL |
2004 | } |
2005 | } | |
2006 | } | |
2007 | ||
2008 | fn collect_predicates_for_types( | |
2009 | &mut self, | |
2010 | param_env: ty::ParamEnv<'tcx>, | |
2011 | cause: ObligationCause<'tcx>, | |
2012 | recursion_depth: usize, | |
2013 | trait_def_id: DefId, | |
cdc7bbd5 | 2014 | types: ty::Binder<'tcx, Vec<Ty<'tcx>>>, |
74b04a01 XL |
2015 | ) -> Vec<PredicateObligation<'tcx>> { |
2016 | // Because the types were potentially derived from | |
2017 | // higher-ranked obligations they may reference late-bound | |
f035d41b XL |
2018 | // regions. For example, `for<'a> Foo<&'a i32> : Copy` would |
2019 | // yield a type like `for<'a> &'a i32`. In general, we | |
74b04a01 XL |
2020 | // maintain the invariant that we never manipulate bound |
2021 | // regions, so we have to process these bound regions somehow. | |
2022 | // | |
2023 | // The strategy is to: | |
2024 | // | |
2025 | // 1. Instantiate those regions to placeholder regions (e.g., | |
f035d41b XL |
2026 | // `for<'a> &'a i32` becomes `&0 i32`. |
2027 | // 2. Produce something like `&'0 i32 : Copy` | |
2028 | // 3. Re-bind the regions back to `for<'a> &'a i32 : Copy` | |
74b04a01 XL |
2029 | |
2030 | types | |
fc512014 | 2031 | .as_ref() |
f035d41b | 2032 | .skip_binder() // binder moved -\ |
74b04a01 XL |
2033 | .iter() |
2034 | .flat_map(|ty| { | |
5099ac24 | 2035 | let ty: ty::Binder<'tcx, Ty<'tcx>> = types.rebind(*ty); // <----/ |
74b04a01 XL |
2036 | |
2037 | self.infcx.commit_unconditionally(|_| { | |
fc512014 | 2038 | let placeholder_ty = self.infcx.replace_bound_vars_with_placeholders(ty); |
74b04a01 | 2039 | let Normalized { value: normalized_ty, mut obligations } = |
f9f354fc XL |
2040 | ensure_sufficient_stack(|| { |
2041 | project::normalize_with_depth( | |
2042 | self, | |
2043 | param_env, | |
2044 | cause.clone(), | |
2045 | recursion_depth, | |
fc512014 | 2046 | placeholder_ty, |
f9f354fc XL |
2047 | ) |
2048 | }); | |
f035d41b | 2049 | let placeholder_obligation = predicate_for_trait_def( |
74b04a01 XL |
2050 | self.tcx(), |
2051 | param_env, | |
2052 | cause.clone(), | |
2053 | trait_def_id, | |
2054 | recursion_depth, | |
2055 | normalized_ty, | |
2056 | &[], | |
2057 | ); | |
f035d41b | 2058 | obligations.push(placeholder_obligation); |
74b04a01 XL |
2059 | obligations |
2060 | }) | |
2061 | }) | |
2062 | .collect() | |
2063 | } | |
2064 | ||
74b04a01 XL |
2065 | /////////////////////////////////////////////////////////////////////////// |
2066 | // Matching | |
2067 | // | |
2068 | // Matching is a common path used for both evaluation and | |
2069 | // confirmation. It basically unifies types that appear in impls | |
2070 | // and traits. This does affect the surrounding environment; | |
2071 | // therefore, when used during evaluation, match routines must be | |
2072 | // run inside of a `probe()` so that their side-effects are | |
2073 | // contained. | |
2074 | ||
2075 | fn rematch_impl( | |
2076 | &mut self, | |
2077 | impl_def_id: DefId, | |
2078 | obligation: &TraitObligation<'tcx>, | |
74b04a01 | 2079 | ) -> Normalized<'tcx, SubstsRef<'tcx>> { |
f035d41b | 2080 | match self.match_impl(impl_def_id, obligation) { |
74b04a01 XL |
2081 | Ok(substs) => substs, |
2082 | Err(()) => { | |
ee023bcb FG |
2083 | self.infcx.tcx.sess.delay_span_bug( |
2084 | obligation.cause.span, | |
2085 | &format!( | |
2086 | "Impl {:?} was matchable against {:?} but now is not", | |
2087 | impl_def_id, obligation | |
2088 | ), | |
74b04a01 | 2089 | ); |
ee023bcb FG |
2090 | let value = self.infcx.fresh_substs_for_item(obligation.cause.span, impl_def_id); |
2091 | let err = self.tcx().ty_error(); | |
2092 | let value = value.fold_with(&mut BottomUpFolder { | |
2093 | tcx: self.tcx(), | |
2094 | ty_op: |_| err, | |
2095 | lt_op: |l| l, | |
2096 | ct_op: |c| c, | |
2097 | }); | |
2098 | Normalized { value, obligations: vec![] } | |
74b04a01 XL |
2099 | } |
2100 | } | |
2101 | } | |
2102 | ||
136023e0 | 2103 | #[tracing::instrument(level = "debug", skip(self))] |
74b04a01 XL |
2104 | fn match_impl( |
2105 | &mut self, | |
2106 | impl_def_id: DefId, | |
2107 | obligation: &TraitObligation<'tcx>, | |
74b04a01 XL |
2108 | ) -> Result<Normalized<'tcx, SubstsRef<'tcx>>, ()> { |
2109 | let impl_trait_ref = self.tcx().impl_trait_ref(impl_def_id).unwrap(); | |
2110 | ||
2111 | // Before we create the substitutions and everything, first | |
2112 | // consider a "quick reject". This avoids creating more types | |
2113 | // and so forth that we need to. | |
2114 | if self.fast_reject_trait_refs(obligation, &impl_trait_ref) { | |
2115 | return Err(()); | |
2116 | } | |
2117 | ||
29967ef6 | 2118 | let placeholder_obligation = |
fc512014 | 2119 | self.infcx().replace_bound_vars_with_placeholders(obligation.predicate); |
f035d41b | 2120 | let placeholder_obligation_trait_ref = placeholder_obligation.trait_ref; |
74b04a01 XL |
2121 | |
2122 | let impl_substs = self.infcx.fresh_substs_for_item(obligation.cause.span, impl_def_id); | |
2123 | ||
2124 | let impl_trait_ref = impl_trait_ref.subst(self.tcx(), impl_substs); | |
2125 | ||
136023e0 XL |
2126 | debug!(?impl_trait_ref); |
2127 | ||
74b04a01 | 2128 | let Normalized { value: impl_trait_ref, obligations: mut nested_obligations } = |
f9f354fc XL |
2129 | ensure_sufficient_stack(|| { |
2130 | project::normalize_with_depth( | |
2131 | self, | |
2132 | obligation.param_env, | |
2133 | obligation.cause.clone(), | |
2134 | obligation.recursion_depth + 1, | |
fc512014 | 2135 | impl_trait_ref, |
f9f354fc XL |
2136 | ) |
2137 | }); | |
74b04a01 | 2138 | |
29967ef6 | 2139 | debug!(?impl_trait_ref, ?placeholder_obligation_trait_ref); |
74b04a01 | 2140 | |
136023e0 XL |
2141 | let cause = ObligationCause::new( |
2142 | obligation.cause.span, | |
2143 | obligation.cause.body_id, | |
c295e0f8 | 2144 | ObligationCauseCode::MatchImpl(obligation.cause.clone(), impl_def_id), |
136023e0 XL |
2145 | ); |
2146 | ||
74b04a01 XL |
2147 | let InferOk { obligations, .. } = self |
2148 | .infcx | |
136023e0 | 2149 | .at(&cause, obligation.param_env) |
ee023bcb | 2150 | .define_opaque_types(false) |
f035d41b | 2151 | .eq(placeholder_obligation_trait_ref, impl_trait_ref) |
74b04a01 XL |
2152 | .map_err(|e| debug!("match_impl: failed eq_trait_refs due to `{}`", e))?; |
2153 | nested_obligations.extend(obligations); | |
2154 | ||
74b04a01 XL |
2155 | if !self.intercrate |
2156 | && self.tcx().impl_polarity(impl_def_id) == ty::ImplPolarity::Reservation | |
2157 | { | |
2158 | debug!("match_impl: reservation impls only apply in intercrate mode"); | |
2159 | return Err(()); | |
2160 | } | |
2161 | ||
136023e0 | 2162 | debug!(?impl_substs, ?nested_obligations, "match_impl: success"); |
74b04a01 XL |
2163 | Ok(Normalized { value: impl_substs, obligations: nested_obligations }) |
2164 | } | |
2165 | ||
2166 | fn fast_reject_trait_refs( | |
2167 | &mut self, | |
ee023bcb FG |
2168 | obligation: &TraitObligation<'tcx>, |
2169 | impl_trait_ref: &ty::TraitRef<'tcx>, | |
74b04a01 XL |
2170 | ) -> bool { |
2171 | // We can avoid creating type variables and doing the full | |
2172 | // substitution if we find that any of the input types, when | |
2173 | // simplified, do not match. | |
2174 | ||
cdc7bbd5 | 2175 | iter::zip(obligation.predicate.skip_binder().trait_ref.substs, impl_trait_ref.substs).any( |
ba9703b0 XL |
2176 | |(obligation_arg, impl_arg)| { |
2177 | match (obligation_arg.unpack(), impl_arg.unpack()) { | |
2178 | (GenericArgKind::Type(obligation_ty), GenericArgKind::Type(impl_ty)) => { | |
a2a8927a XL |
2179 | // Note, we simplify parameters for the obligation but not the |
2180 | // impl so that we do not reject a blanket impl but do reject | |
2181 | // more concrete impls if we're searching for `T: Trait`. | |
2182 | let simplified_obligation_ty = fast_reject::simplify_type( | |
2183 | self.tcx(), | |
2184 | obligation_ty, | |
ee023bcb FG |
2185 | TreatParams::AsBoundTypes, |
2186 | ); | |
2187 | let simplified_impl_ty = fast_reject::simplify_type( | |
2188 | self.tcx(), | |
2189 | impl_ty, | |
2190 | TreatParams::AsPlaceholders, | |
a2a8927a | 2191 | ); |
ba9703b0 XL |
2192 | |
2193 | simplified_obligation_ty.is_some() | |
2194 | && simplified_impl_ty.is_some() | |
2195 | && simplified_obligation_ty != simplified_impl_ty | |
2196 | } | |
2197 | (GenericArgKind::Lifetime(_), GenericArgKind::Lifetime(_)) => { | |
2198 | // Lifetimes can never cause a rejection. | |
2199 | false | |
2200 | } | |
2201 | (GenericArgKind::Const(_), GenericArgKind::Const(_)) => { | |
2202 | // Conservatively ignore consts (i.e. assume they might | |
2203 | // unify later) until we have `fast_reject` support for | |
2204 | // them (if we'll ever need it, even). | |
2205 | false | |
2206 | } | |
2207 | _ => unreachable!(), | |
2208 | } | |
74b04a01 XL |
2209 | }, |
2210 | ) | |
2211 | } | |
2212 | ||
2213 | /// Normalize `where_clause_trait_ref` and try to match it against | |
2214 | /// `obligation`. If successful, return any predicates that | |
29967ef6 | 2215 | /// result from the normalization. |
74b04a01 XL |
2216 | fn match_where_clause_trait_ref( |
2217 | &mut self, | |
2218 | obligation: &TraitObligation<'tcx>, | |
2219 | where_clause_trait_ref: ty::PolyTraitRef<'tcx>, | |
2220 | ) -> Result<Vec<PredicateObligation<'tcx>>, ()> { | |
2221 | self.match_poly_trait_ref(obligation, where_clause_trait_ref) | |
2222 | } | |
2223 | ||
2224 | /// Returns `Ok` if `poly_trait_ref` being true implies that the | |
2225 | /// obligation is satisfied. | |
c295e0f8 | 2226 | #[instrument(skip(self), level = "debug")] |
74b04a01 XL |
2227 | fn match_poly_trait_ref( |
2228 | &mut self, | |
2229 | obligation: &TraitObligation<'tcx>, | |
2230 | poly_trait_ref: ty::PolyTraitRef<'tcx>, | |
2231 | ) -> Result<Vec<PredicateObligation<'tcx>>, ()> { | |
74b04a01 XL |
2232 | self.infcx |
2233 | .at(&obligation.cause, obligation.param_env) | |
ee023bcb FG |
2234 | // We don't want predicates for opaque types to just match all other types, |
2235 | // if there is an obligation on the opaque type, then that obligation must be met | |
2236 | // opaquely. Otherwise we'd match any obligation to the opaque type and then error | |
2237 | // out later. | |
2238 | .define_opaque_types(false) | |
74b04a01 XL |
2239 | .sup(obligation.predicate.to_poly_trait_ref(), poly_trait_ref) |
2240 | .map(|InferOk { obligations, .. }| obligations) | |
2241 | .map_err(|_| ()) | |
2242 | } | |
2243 | ||
2244 | /////////////////////////////////////////////////////////////////////////// | |
2245 | // Miscellany | |
2246 | ||
2247 | fn match_fresh_trait_refs( | |
2248 | &self, | |
a2a8927a XL |
2249 | previous: ty::PolyTraitPredicate<'tcx>, |
2250 | current: ty::PolyTraitPredicate<'tcx>, | |
74b04a01 XL |
2251 | param_env: ty::ParamEnv<'tcx>, |
2252 | ) -> bool { | |
2253 | let mut matcher = ty::_match::Match::new(self.tcx(), param_env); | |
2254 | matcher.relate(previous, current).is_ok() | |
2255 | } | |
2256 | ||
2257 | fn push_stack<'o>( | |
2258 | &mut self, | |
2259 | previous_stack: TraitObligationStackList<'o, 'tcx>, | |
2260 | obligation: &'o TraitObligation<'tcx>, | |
2261 | ) -> TraitObligationStack<'o, 'tcx> { | |
a2a8927a | 2262 | let fresh_trait_pred = obligation.predicate.fold_with(&mut self.freshener); |
74b04a01 XL |
2263 | |
2264 | let dfn = previous_stack.cache.next_dfn(); | |
2265 | let depth = previous_stack.depth() + 1; | |
2266 | TraitObligationStack { | |
2267 | obligation, | |
a2a8927a | 2268 | fresh_trait_pred, |
74b04a01 XL |
2269 | reached_depth: Cell::new(depth), |
2270 | previous: previous_stack, | |
2271 | dfn, | |
2272 | depth, | |
2273 | } | |
2274 | } | |
2275 | ||
c295e0f8 | 2276 | #[instrument(skip(self), level = "debug")] |
74b04a01 XL |
2277 | fn closure_trait_ref_unnormalized( |
2278 | &mut self, | |
2279 | obligation: &TraitObligation<'tcx>, | |
74b04a01 XL |
2280 | substs: SubstsRef<'tcx>, |
2281 | ) -> ty::PolyTraitRef<'tcx> { | |
ba9703b0 | 2282 | let closure_sig = substs.as_closure().sig(); |
74b04a01 | 2283 | |
29967ef6 | 2284 | debug!(?closure_sig); |
74b04a01 XL |
2285 | |
2286 | // (1) Feels icky to skip the binder here, but OTOH we know | |
2287 | // that the self-type is an unboxed closure type and hence is | |
2288 | // in fact unparameterized (or at least does not reference any | |
2289 | // regions bound in the obligation). Still probably some | |
2290 | // refactoring could make this nicer. | |
2291 | closure_trait_ref_and_return_type( | |
2292 | self.tcx(), | |
2293 | obligation.predicate.def_id(), | |
2294 | obligation.predicate.skip_binder().self_ty(), // (1) | |
ba9703b0 | 2295 | closure_sig, |
74b04a01 XL |
2296 | util::TupleArgumentsFlag::No, |
2297 | ) | |
2298 | .map_bound(|(trait_ref, _)| trait_ref) | |
2299 | } | |
2300 | ||
2301 | fn generator_trait_ref_unnormalized( | |
2302 | &mut self, | |
2303 | obligation: &TraitObligation<'tcx>, | |
74b04a01 XL |
2304 | substs: SubstsRef<'tcx>, |
2305 | ) -> ty::PolyTraitRef<'tcx> { | |
ba9703b0 | 2306 | let gen_sig = substs.as_generator().poly_sig(); |
74b04a01 XL |
2307 | |
2308 | // (1) Feels icky to skip the binder here, but OTOH we know | |
2309 | // that the self-type is an generator type and hence is | |
2310 | // in fact unparameterized (or at least does not reference any | |
2311 | // regions bound in the obligation). Still probably some | |
2312 | // refactoring could make this nicer. | |
2313 | ||
2314 | super::util::generator_trait_ref_and_outputs( | |
2315 | self.tcx(), | |
2316 | obligation.predicate.def_id(), | |
2317 | obligation.predicate.skip_binder().self_ty(), // (1) | |
2318 | gen_sig, | |
2319 | ) | |
2320 | .map_bound(|(trait_ref, ..)| trait_ref) | |
2321 | } | |
2322 | ||
2323 | /// Returns the obligations that are implied by instantiating an | |
2324 | /// impl or trait. The obligations are substituted and fully | |
2325 | /// normalized. This is used when confirming an impl or default | |
2326 | /// impl. | |
136023e0 | 2327 | #[tracing::instrument(level = "debug", skip(self, cause, param_env))] |
74b04a01 XL |
2328 | fn impl_or_trait_obligations( |
2329 | &mut self, | |
ee023bcb | 2330 | cause: &ObligationCause<'tcx>, |
74b04a01 XL |
2331 | recursion_depth: usize, |
2332 | param_env: ty::ParamEnv<'tcx>, | |
2333 | def_id: DefId, // of impl or trait | |
2334 | substs: SubstsRef<'tcx>, // for impl or trait | |
ee023bcb | 2335 | parent_trait_pred: ty::Binder<'tcx, ty::TraitPredicate<'tcx>>, |
74b04a01 | 2336 | ) -> Vec<PredicateObligation<'tcx>> { |
74b04a01 XL |
2337 | let tcx = self.tcx(); |
2338 | ||
2339 | // To allow for one-pass evaluation of the nested obligation, | |
2340 | // each predicate must be preceded by the obligations required | |
2341 | // to normalize it. | |
2342 | // for example, if we have: | |
2343 | // impl<U: Iterator<Item: Copy>, V: Iterator<Item = U>> Foo for V | |
2344 | // the impl will have the following predicates: | |
2345 | // <V as Iterator>::Item = U, | |
2346 | // U: Iterator, U: Sized, | |
2347 | // V: Iterator, V: Sized, | |
2348 | // <U as Iterator>::Item: Copy | |
2349 | // When we substitute, say, `V => IntoIter<u32>, U => $0`, the last | |
2350 | // obligation will normalize to `<$0 as Iterator>::Item = $1` and | |
2351 | // `$1: Copy`, so we must ensure the obligations are emitted in | |
2352 | // that order. | |
2353 | let predicates = tcx.predicates_of(def_id); | |
136023e0 | 2354 | debug!(?predicates); |
74b04a01 XL |
2355 | assert_eq!(predicates.parent, None); |
2356 | let mut obligations = Vec::with_capacity(predicates.predicates.len()); | |
ee023bcb FG |
2357 | let parent_code = cause.clone_code(); |
2358 | for (predicate, span) in predicates.predicates { | |
2359 | let span = *span; | |
2360 | let derived = | |
2361 | DerivedObligationCause { parent_trait_pred, parent_code: parent_code.clone() }; | |
2362 | let code = ImplDerivedObligation(Box::new(ImplDerivedObligationCause { | |
2363 | derived, | |
2364 | impl_def_id: def_id, | |
2365 | span, | |
2366 | })); | |
2367 | let cause = ObligationCause::new(cause.span, cause.body_id, code); | |
74b04a01 XL |
2368 | let predicate = normalize_with_depth_to( |
2369 | self, | |
2370 | param_env, | |
2371 | cause.clone(), | |
2372 | recursion_depth, | |
fc512014 | 2373 | predicate.subst(tcx, substs), |
74b04a01 XL |
2374 | &mut obligations, |
2375 | ); | |
ee023bcb | 2376 | obligations.push(Obligation { cause, recursion_depth, param_env, predicate }); |
74b04a01 XL |
2377 | } |
2378 | ||
2379 | obligations | |
2380 | } | |
2381 | } | |
2382 | ||
ba9703b0 XL |
2383 | trait TraitObligationExt<'tcx> { |
2384 | fn derived_cause( | |
2385 | &self, | |
2386 | variant: fn(DerivedObligationCause<'tcx>) -> ObligationCauseCode<'tcx>, | |
2387 | ) -> ObligationCause<'tcx>; | |
2388 | } | |
2389 | ||
2390 | impl<'tcx> TraitObligationExt<'tcx> for TraitObligation<'tcx> { | |
ba9703b0 | 2391 | fn derived_cause( |
74b04a01 XL |
2392 | &self, |
2393 | variant: fn(DerivedObligationCause<'tcx>) -> ObligationCauseCode<'tcx>, | |
2394 | ) -> ObligationCause<'tcx> { | |
2395 | /*! | |
2396 | * Creates a cause for obligations that are derived from | |
2397 | * `obligation` by a recursive search (e.g., for a builtin | |
2398 | * bound, or eventually a `auto trait Foo`). If `obligation` | |
2399 | * is itself a derived obligation, this is just a clone, but | |
2400 | * otherwise we create a "derived obligation" cause so as to | |
2401 | * keep track of the original root obligation for error | |
2402 | * reporting. | |
2403 | */ | |
2404 | ||
2405 | let obligation = self; | |
2406 | ||
2407 | // NOTE(flaper87): As of now, it keeps track of the whole error | |
2408 | // chain. Ideally, we should have a way to configure this either | |
2409 | // by using -Z verbose or just a CLI argument. | |
2410 | let derived_cause = DerivedObligationCause { | |
5099ac24 | 2411 | parent_trait_pred: obligation.predicate, |
a2a8927a | 2412 | parent_code: obligation.cause.clone_code(), |
74b04a01 XL |
2413 | }; |
2414 | let derived_code = variant(derived_cause); | |
2415 | ObligationCause::new(obligation.cause.span, obligation.cause.body_id, derived_code) | |
2416 | } | |
2417 | } | |
2418 | ||
2419 | impl<'o, 'tcx> TraitObligationStack<'o, 'tcx> { | |
2420 | fn list(&'o self) -> TraitObligationStackList<'o, 'tcx> { | |
2421 | TraitObligationStackList::with(self) | |
2422 | } | |
2423 | ||
2424 | fn cache(&self) -> &'o ProvisionalEvaluationCache<'tcx> { | |
2425 | self.previous.cache | |
2426 | } | |
2427 | ||
2428 | fn iter(&'o self) -> TraitObligationStackList<'o, 'tcx> { | |
2429 | self.list() | |
2430 | } | |
2431 | ||
2432 | /// Indicates that attempting to evaluate this stack entry | |
2433 | /// required accessing something from the stack at depth `reached_depth`. | |
2434 | fn update_reached_depth(&self, reached_depth: usize) { | |
2435 | assert!( | |
17df50a5 | 2436 | self.depth >= reached_depth, |
74b04a01 XL |
2437 | "invoked `update_reached_depth` with something under this stack: \ |
2438 | self.depth={} reached_depth={}", | |
2439 | self.depth, | |
2440 | reached_depth, | |
2441 | ); | |
29967ef6 | 2442 | debug!(reached_depth, "update_reached_depth"); |
74b04a01 XL |
2443 | let mut p = self; |
2444 | while reached_depth < p.depth { | |
a2a8927a | 2445 | debug!(?p.fresh_trait_pred, "update_reached_depth: marking as cycle participant"); |
74b04a01 XL |
2446 | p.reached_depth.set(p.reached_depth.get().min(reached_depth)); |
2447 | p = p.previous.head.unwrap(); | |
2448 | } | |
2449 | } | |
2450 | } | |
2451 | ||
2452 | /// The "provisional evaluation cache" is used to store intermediate cache results | |
2453 | /// when solving auto traits. Auto traits are unusual in that they can support | |
2454 | /// cycles. So, for example, a "proof tree" like this would be ok: | |
2455 | /// | |
2456 | /// - `Foo<T>: Send` :- | |
2457 | /// - `Bar<T>: Send` :- | |
2458 | /// - `Foo<T>: Send` -- cycle, but ok | |
2459 | /// - `Baz<T>: Send` | |
2460 | /// | |
2461 | /// Here, to prove `Foo<T>: Send`, we have to prove `Bar<T>: Send` and | |
2462 | /// `Baz<T>: Send`. Proving `Bar<T>: Send` in turn required `Foo<T>: Send`. | |
2463 | /// For non-auto traits, this cycle would be an error, but for auto traits (because | |
2464 | /// they are coinductive) it is considered ok. | |
2465 | /// | |
2466 | /// However, there is a complication: at the point where we have | |
2467 | /// "proven" `Bar<T>: Send`, we have in fact only proven it | |
2468 | /// *provisionally*. In particular, we proved that `Bar<T>: Send` | |
2469 | /// *under the assumption* that `Foo<T>: Send`. But what if we later | |
2470 | /// find out this assumption is wrong? Specifically, we could | |
2471 | /// encounter some kind of error proving `Baz<T>: Send`. In that case, | |
2472 | /// `Bar<T>: Send` didn't turn out to be true. | |
2473 | /// | |
2474 | /// In Issue #60010, we found a bug in rustc where it would cache | |
2475 | /// these intermediate results. This was fixed in #60444 by disabling | |
2476 | /// *all* caching for things involved in a cycle -- in our example, | |
2477 | /// that would mean we don't cache that `Bar<T>: Send`. But this led | |
2478 | /// to large slowdowns. | |
2479 | /// | |
2480 | /// Specifically, imagine this scenario, where proving `Baz<T>: Send` | |
2481 | /// first requires proving `Bar<T>: Send` (which is true: | |
2482 | /// | |
2483 | /// - `Foo<T>: Send` :- | |
2484 | /// - `Bar<T>: Send` :- | |
2485 | /// - `Foo<T>: Send` -- cycle, but ok | |
2486 | /// - `Baz<T>: Send` | |
2487 | /// - `Bar<T>: Send` -- would be nice for this to be a cache hit! | |
2488 | /// - `*const T: Send` -- but what if we later encounter an error? | |
2489 | /// | |
2490 | /// The *provisional evaluation cache* resolves this issue. It stores | |
2491 | /// cache results that we've proven but which were involved in a cycle | |
2492 | /// in some way. We track the minimal stack depth (i.e., the | |
2493 | /// farthest from the top of the stack) that we are dependent on. | |
2494 | /// The idea is that the cache results within are all valid -- so long as | |
2495 | /// none of the nodes in between the current node and the node at that minimum | |
2496 | /// depth result in an error (in which case the cached results are just thrown away). | |
2497 | /// | |
2498 | /// During evaluation, we consult this provisional cache and rely on | |
2499 | /// it. Accessing a cached value is considered equivalent to accessing | |
2500 | /// a result at `reached_depth`, so it marks the *current* solution as | |
2501 | /// provisional as well. If an error is encountered, we toss out any | |
2502 | /// provisional results added from the subtree that encountered the | |
2503 | /// error. When we pop the node at `reached_depth` from the stack, we | |
2504 | /// can commit all the things that remain in the provisional cache. | |
2505 | struct ProvisionalEvaluationCache<'tcx> { | |
2506 | /// next "depth first number" to issue -- just a counter | |
2507 | dfn: Cell<usize>, | |
2508 | ||
74b04a01 XL |
2509 | /// Map from cache key to the provisionally evaluated thing. |
2510 | /// The cache entries contain the result but also the DFN in which they | |
2511 | /// were added. The DFN is used to clear out values on failure. | |
2512 | /// | |
2513 | /// Imagine we have a stack like: | |
2514 | /// | |
2515 | /// - `A B C` and we add a cache for the result of C (DFN 2) | |
2516 | /// - Then we have a stack `A B D` where `D` has DFN 3 | |
2517 | /// - We try to solve D by evaluating E: `A B D E` (DFN 4) | |
ee023bcb | 2518 | /// - `E` generates various cache entries which have cyclic dependencies on `B` |
74b04a01 XL |
2519 | /// - `A B D E F` and so forth |
2520 | /// - the DFN of `F` for example would be 5 | |
2521 | /// - then we determine that `E` is in error -- we will then clear | |
2522 | /// all cache values whose DFN is >= 4 -- in this case, that | |
2523 | /// means the cached value for `F`. | |
a2a8927a | 2524 | map: RefCell<FxHashMap<ty::PolyTraitPredicate<'tcx>, ProvisionalEvaluation>>, |
74b04a01 XL |
2525 | } |
2526 | ||
2527 | /// A cache value for the provisional cache: contains the depth-first | |
2528 | /// number (DFN) and result. | |
2529 | #[derive(Copy, Clone, Debug)] | |
2530 | struct ProvisionalEvaluation { | |
2531 | from_dfn: usize, | |
17df50a5 | 2532 | reached_depth: usize, |
74b04a01 | 2533 | result: EvaluationResult, |
5099ac24 FG |
2534 | /// The `DepNodeIndex` created for the `evaluate_stack` call for this provisional |
2535 | /// evaluation. When we create an entry in the evaluation cache using this provisional | |
2536 | /// cache entry (see `on_completion`), we use this `dep_node` to ensure that future reads from | |
2537 | /// the cache will have all of the necessary incr comp dependencies tracked. | |
2538 | dep_node: DepNodeIndex, | |
74b04a01 XL |
2539 | } |
2540 | ||
2541 | impl<'tcx> Default for ProvisionalEvaluationCache<'tcx> { | |
2542 | fn default() -> Self { | |
17df50a5 | 2543 | Self { dfn: Cell::new(0), map: Default::default() } |
74b04a01 XL |
2544 | } |
2545 | } | |
2546 | ||
2547 | impl<'tcx> ProvisionalEvaluationCache<'tcx> { | |
2548 | /// Get the next DFN in sequence (basically a counter). | |
2549 | fn next_dfn(&self) -> usize { | |
2550 | let result = self.dfn.get(); | |
2551 | self.dfn.set(result + 1); | |
2552 | result | |
2553 | } | |
2554 | ||
2555 | /// Check the provisional cache for any result for | |
2556 | /// `fresh_trait_ref`. If there is a hit, then you must consider | |
2557 | /// it an access to the stack slots at depth | |
17df50a5 XL |
2558 | /// `reached_depth` (from the returned value). |
2559 | fn get_provisional( | |
2560 | &self, | |
a2a8927a | 2561 | fresh_trait_pred: ty::PolyTraitPredicate<'tcx>, |
17df50a5 | 2562 | ) -> Option<ProvisionalEvaluation> { |
74b04a01 | 2563 | debug!( |
a2a8927a | 2564 | ?fresh_trait_pred, |
29967ef6 | 2565 | "get_provisional = {:#?}", |
a2a8927a | 2566 | self.map.borrow().get(&fresh_trait_pred), |
74b04a01 | 2567 | ); |
a2a8927a | 2568 | Some(*self.map.borrow().get(&fresh_trait_pred)?) |
74b04a01 XL |
2569 | } |
2570 | ||
2571 | /// Insert a provisional result into the cache. The result came | |
2572 | /// from the node with the given DFN. It accessed a minimum depth | |
a2a8927a | 2573 | /// of `reached_depth` to compute. It evaluated `fresh_trait_pred` |
74b04a01 XL |
2574 | /// and resulted in `result`. |
2575 | fn insert_provisional( | |
2576 | &self, | |
2577 | from_dfn: usize, | |
2578 | reached_depth: usize, | |
a2a8927a | 2579 | fresh_trait_pred: ty::PolyTraitPredicate<'tcx>, |
74b04a01 | 2580 | result: EvaluationResult, |
5099ac24 | 2581 | dep_node: DepNodeIndex, |
74b04a01 | 2582 | ) { |
a2a8927a | 2583 | debug!(?from_dfn, ?fresh_trait_pred, ?result, "insert_provisional"); |
74b04a01 | 2584 | |
17df50a5 XL |
2585 | let mut map = self.map.borrow_mut(); |
2586 | ||
2587 | // Subtle: when we complete working on the DFN `from_dfn`, anything | |
2588 | // that remains in the provisional cache must be dependent on some older | |
2589 | // stack entry than `from_dfn`. We have to update their depth with our transitive | |
2590 | // depth in that case or else it would be referring to some popped note. | |
2591 | // | |
2592 | // Example: | |
2593 | // A (reached depth 0) | |
2594 | // ... | |
2595 | // B // depth 1 -- reached depth = 0 | |
2596 | // C // depth 2 -- reached depth = 1 (should be 0) | |
2597 | // B | |
2598 | // A // depth 0 | |
2599 | // D (reached depth 1) | |
2600 | // C (cache -- reached depth = 2) | |
2601 | for (_k, v) in &mut *map { | |
2602 | if v.from_dfn >= from_dfn { | |
2603 | v.reached_depth = reached_depth.min(v.reached_depth); | |
2604 | } | |
2605 | } | |
74b04a01 | 2606 | |
5099ac24 FG |
2607 | map.insert( |
2608 | fresh_trait_pred, | |
2609 | ProvisionalEvaluation { from_dfn, reached_depth, result, dep_node }, | |
2610 | ); | |
74b04a01 XL |
2611 | } |
2612 | ||
2613 | /// Invoked when the node with dfn `dfn` does not get a successful | |
2614 | /// result. This will clear out any provisional cache entries | |
2615 | /// that were added since `dfn` was created. This is because the | |
2616 | /// provisional entries are things which must assume that the | |
2617 | /// things on the stack at the time of their creation succeeded -- | |
2618 | /// since the failing node is presently at the top of the stack, | |
2619 | /// these provisional entries must either depend on it or some | |
2620 | /// ancestor of it. | |
2621 | fn on_failure(&self, dfn: usize) { | |
29967ef6 | 2622 | debug!(?dfn, "on_failure"); |
74b04a01 XL |
2623 | self.map.borrow_mut().retain(|key, eval| { |
2624 | if !eval.from_dfn >= dfn { | |
2625 | debug!("on_failure: removing {:?}", key); | |
2626 | false | |
2627 | } else { | |
2628 | true | |
2629 | } | |
2630 | }); | |
2631 | } | |
2632 | ||
2633 | /// Invoked when the node at depth `depth` completed without | |
2634 | /// depending on anything higher in the stack (if that completion | |
2635 | /// was a failure, then `on_failure` should have been invoked | |
2636 | /// already). The callback `op` will be invoked for each | |
2637 | /// provisional entry that we can now confirm. | |
17df50a5 XL |
2638 | /// |
2639 | /// Note that we may still have provisional cache items remaining | |
2640 | /// in the cache when this is done. For example, if there is a | |
2641 | /// cycle: | |
2642 | /// | |
2643 | /// * A depends on... | |
2644 | /// * B depends on A | |
2645 | /// * C depends on... | |
2646 | /// * D depends on C | |
2647 | /// * ... | |
2648 | /// | |
2649 | /// Then as we complete the C node we will have a provisional cache | |
2650 | /// with results for A, B, C, and D. This method would clear out | |
2651 | /// the C and D results, but leave A and B provisional. | |
2652 | /// | |
2653 | /// This is determined based on the DFN: we remove any provisional | |
2654 | /// results created since `dfn` started (e.g., in our example, dfn | |
2655 | /// would be 2, representing the C node, and hence we would | |
2656 | /// remove the result for D, which has DFN 3, but not the results for | |
2657 | /// A and B, which have DFNs 0 and 1 respectively). | |
74b04a01 XL |
2658 | fn on_completion( |
2659 | &self, | |
17df50a5 | 2660 | dfn: usize, |
5099ac24 | 2661 | mut op: impl FnMut(ty::PolyTraitPredicate<'tcx>, EvaluationResult, DepNodeIndex), |
74b04a01 | 2662 | ) { |
17df50a5 | 2663 | debug!(?dfn, "on_completion"); |
74b04a01 | 2664 | |
a2a8927a | 2665 | for (fresh_trait_pred, eval) in |
17df50a5 XL |
2666 | self.map.borrow_mut().drain_filter(|_k, eval| eval.from_dfn >= dfn) |
2667 | { | |
a2a8927a | 2668 | debug!(?fresh_trait_pred, ?eval, "on_completion"); |
74b04a01 | 2669 | |
5099ac24 | 2670 | op(fresh_trait_pred, eval.result, eval.dep_node); |
74b04a01 | 2671 | } |
74b04a01 XL |
2672 | } |
2673 | } | |
2674 | ||
2675 | #[derive(Copy, Clone)] | |
2676 | struct TraitObligationStackList<'o, 'tcx> { | |
2677 | cache: &'o ProvisionalEvaluationCache<'tcx>, | |
2678 | head: Option<&'o TraitObligationStack<'o, 'tcx>>, | |
2679 | } | |
2680 | ||
2681 | impl<'o, 'tcx> TraitObligationStackList<'o, 'tcx> { | |
2682 | fn empty(cache: &'o ProvisionalEvaluationCache<'tcx>) -> TraitObligationStackList<'o, 'tcx> { | |
2683 | TraitObligationStackList { cache, head: None } | |
2684 | } | |
2685 | ||
2686 | fn with(r: &'o TraitObligationStack<'o, 'tcx>) -> TraitObligationStackList<'o, 'tcx> { | |
2687 | TraitObligationStackList { cache: r.cache(), head: Some(r) } | |
2688 | } | |
2689 | ||
2690 | fn head(&self) -> Option<&'o TraitObligationStack<'o, 'tcx>> { | |
2691 | self.head | |
2692 | } | |
2693 | ||
2694 | fn depth(&self) -> usize { | |
2695 | if let Some(head) = self.head { head.depth } else { 0 } | |
2696 | } | |
2697 | } | |
2698 | ||
2699 | impl<'o, 'tcx> Iterator for TraitObligationStackList<'o, 'tcx> { | |
2700 | type Item = &'o TraitObligationStack<'o, 'tcx>; | |
2701 | ||
2702 | fn next(&mut self) -> Option<&'o TraitObligationStack<'o, 'tcx>> { | |
fc512014 XL |
2703 | let o = self.head?; |
2704 | *self = o.previous; | |
2705 | Some(o) | |
74b04a01 XL |
2706 | } |
2707 | } | |
2708 | ||
2709 | impl<'o, 'tcx> fmt::Debug for TraitObligationStack<'o, 'tcx> { | |
2710 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
2711 | write!(f, "TraitObligationStack({:?})", self.obligation) | |
2712 | } | |
2713 | } | |
5099ac24 FG |
2714 | |
2715 | pub enum ProjectionMatchesProjection { | |
2716 | Yes, | |
2717 | Ambiguous, | |
2718 | No, | |
2719 | } |