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