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