]>
Commit | Line | Data |
---|---|---|
ba9703b0 XL |
1 | //! Code for projecting associated types out of trait references. |
2 | ||
ba9703b0 XL |
3 | use super::specialization_graph; |
4 | use super::translate_substs; | |
5 | use super::util; | |
6 | use super::MismatchedProjectionTypes; | |
7 | use super::Obligation; | |
8 | use super::ObligationCause; | |
9 | use super::PredicateObligation; | |
10 | use super::Selection; | |
11 | use super::SelectionContext; | |
12 | use super::SelectionError; | |
f9f354fc | 13 | use super::{ |
f035d41b | 14 | ImplSourceClosureData, ImplSourceDiscriminantKindData, ImplSourceFnPointerData, |
6a06907d | 15 | ImplSourceGeneratorData, ImplSourcePointeeData, ImplSourceUserDefinedData, |
f9f354fc | 16 | }; |
f035d41b | 17 | use super::{Normalized, NormalizedTy, ProjectionCacheEntry, ProjectionCacheKey}; |
ba9703b0 XL |
18 | |
19 | use crate::infer::type_variable::{TypeVariableOrigin, TypeVariableOriginKind}; | |
20 | use crate::infer::{InferCtxt, InferOk, LateBoundRegionConversionTime}; | |
21 | use crate::traits::error_reporting::InferCtxtExt; | |
f9f354fc | 22 | use rustc_data_structures::stack::ensure_sufficient_stack; |
ba9703b0 XL |
23 | use rustc_errors::ErrorReported; |
24 | use rustc_hir::def_id::DefId; | |
3dfed10e | 25 | use rustc_hir::lang_items::LangItem; |
f035d41b | 26 | use rustc_infer::infer::resolve::OpportunisticRegionResolver; |
ba9703b0 | 27 | use rustc_middle::ty::fold::{TypeFoldable, TypeFolder}; |
f035d41b | 28 | use rustc_middle::ty::subst::Subst; |
ba9703b0 | 29 | use rustc_middle::ty::{self, ToPolyTraitRef, ToPredicate, Ty, TyCtxt, WithConstness}; |
f035d41b | 30 | use rustc_span::symbol::sym; |
ba9703b0 XL |
31 | |
32 | pub use rustc_middle::traits::Reveal; | |
33 | ||
34 | pub type PolyProjectionObligation<'tcx> = Obligation<'tcx, ty::PolyProjectionPredicate<'tcx>>; | |
35 | ||
36 | pub type ProjectionObligation<'tcx> = Obligation<'tcx, ty::ProjectionPredicate<'tcx>>; | |
37 | ||
38 | pub type ProjectionTyObligation<'tcx> = Obligation<'tcx, ty::ProjectionTy<'tcx>>; | |
39 | ||
f9652781 XL |
40 | pub(super) struct InProgress; |
41 | ||
ba9703b0 XL |
42 | /// When attempting to resolve `<T as TraitRef>::Name` ... |
43 | #[derive(Debug)] | |
44 | pub enum ProjectionTyError<'tcx> { | |
45 | /// ...we found multiple sources of information and couldn't resolve the ambiguity. | |
46 | TooManyCandidates, | |
47 | ||
48 | /// ...an error occurred matching `T : TraitRef` | |
49 | TraitSelectionError(SelectionError<'tcx>), | |
50 | } | |
51 | ||
52 | #[derive(PartialEq, Eq, Debug)] | |
53 | enum ProjectionTyCandidate<'tcx> { | |
29967ef6 | 54 | /// From a where-clause in the env or object type |
ba9703b0 XL |
55 | ParamEnv(ty::PolyProjectionPredicate<'tcx>), |
56 | ||
29967ef6 | 57 | /// From the definition of `Trait` when you have something like <<A as Trait>::B as Trait2>::C |
ba9703b0 XL |
58 | TraitDef(ty::PolyProjectionPredicate<'tcx>), |
59 | ||
29967ef6 XL |
60 | /// Bounds specified on an object type |
61 | Object(ty::PolyProjectionPredicate<'tcx>), | |
62 | ||
63 | /// From a "impl" (or a "pseudo-impl" returned by select) | |
ba9703b0 XL |
64 | Select(Selection<'tcx>), |
65 | } | |
66 | ||
67 | enum ProjectionTyCandidateSet<'tcx> { | |
68 | None, | |
69 | Single(ProjectionTyCandidate<'tcx>), | |
70 | Ambiguous, | |
71 | Error(SelectionError<'tcx>), | |
72 | } | |
73 | ||
74 | impl<'tcx> ProjectionTyCandidateSet<'tcx> { | |
75 | fn mark_ambiguous(&mut self) { | |
76 | *self = ProjectionTyCandidateSet::Ambiguous; | |
77 | } | |
78 | ||
79 | fn mark_error(&mut self, err: SelectionError<'tcx>) { | |
80 | *self = ProjectionTyCandidateSet::Error(err); | |
81 | } | |
82 | ||
83 | // Returns true if the push was successful, or false if the candidate | |
84 | // was discarded -- this could be because of ambiguity, or because | |
85 | // a higher-priority candidate is already there. | |
86 | fn push_candidate(&mut self, candidate: ProjectionTyCandidate<'tcx>) -> bool { | |
87 | use self::ProjectionTyCandidate::*; | |
88 | use self::ProjectionTyCandidateSet::*; | |
89 | ||
90 | // This wacky variable is just used to try and | |
91 | // make code readable and avoid confusing paths. | |
92 | // It is assigned a "value" of `()` only on those | |
93 | // paths in which we wish to convert `*self` to | |
94 | // ambiguous (and return false, because the candidate | |
95 | // was not used). On other paths, it is not assigned, | |
96 | // and hence if those paths *could* reach the code that | |
97 | // comes after the match, this fn would not compile. | |
98 | let convert_to_ambiguous; | |
99 | ||
100 | match self { | |
101 | None => { | |
102 | *self = Single(candidate); | |
103 | return true; | |
104 | } | |
105 | ||
106 | Single(current) => { | |
107 | // Duplicates can happen inside ParamEnv. In the case, we | |
108 | // perform a lazy deduplication. | |
109 | if current == &candidate { | |
110 | return false; | |
111 | } | |
112 | ||
113 | // Prefer where-clauses. As in select, if there are multiple | |
114 | // candidates, we prefer where-clause candidates over impls. This | |
115 | // may seem a bit surprising, since impls are the source of | |
116 | // "truth" in some sense, but in fact some of the impls that SEEM | |
117 | // applicable are not, because of nested obligations. Where | |
118 | // clauses are the safer choice. See the comment on | |
119 | // `select::SelectionCandidate` and #21974 for more details. | |
120 | match (current, candidate) { | |
121 | (ParamEnv(..), ParamEnv(..)) => convert_to_ambiguous = (), | |
122 | (ParamEnv(..), _) => return false, | |
123 | (_, ParamEnv(..)) => unreachable!(), | |
124 | (_, _) => convert_to_ambiguous = (), | |
125 | } | |
126 | } | |
127 | ||
128 | Ambiguous | Error(..) => { | |
129 | return false; | |
130 | } | |
131 | } | |
132 | ||
133 | // We only ever get here when we moved from a single candidate | |
134 | // to ambiguous. | |
135 | let () = convert_to_ambiguous; | |
136 | *self = Ambiguous; | |
137 | false | |
138 | } | |
139 | } | |
140 | ||
141 | /// Evaluates constraints of the form: | |
142 | /// | |
143 | /// for<...> <T as Trait>::U == V | |
144 | /// | |
145 | /// If successful, this may result in additional obligations. Also returns | |
146 | /// the projection cache key used to track these additional obligations. | |
f9652781 XL |
147 | /// |
148 | /// ## Returns | |
149 | /// | |
150 | /// - `Err(_)`: the projection can be normalized, but is not equal to the | |
151 | /// expected type. | |
152 | /// - `Ok(Err(InProgress))`: this is called recursively while normalizing | |
153 | /// the same projection. | |
154 | /// - `Ok(Ok(None))`: The projection cannot be normalized due to ambiguity | |
155 | /// (resolving some inference variables in the projection may fix this). | |
156 | /// - `Ok(Ok(Some(obligations)))`: The projection bound holds subject to | |
157 | /// the given obligations. If the projection cannot be normalized because | |
158 | /// the required trait bound doesn't hold this returned with `obligations` | |
159 | /// being a predicate that cannot be proven. | |
29967ef6 | 160 | #[instrument(level = "debug", skip(selcx))] |
f9652781 | 161 | pub(super) fn poly_project_and_unify_type<'cx, 'tcx>( |
ba9703b0 XL |
162 | selcx: &mut SelectionContext<'cx, 'tcx>, |
163 | obligation: &PolyProjectionObligation<'tcx>, | |
f9652781 XL |
164 | ) -> Result< |
165 | Result<Option<Vec<PredicateObligation<'tcx>>>, InProgress>, | |
166 | MismatchedProjectionTypes<'tcx>, | |
167 | > { | |
ba9703b0 | 168 | let infcx = selcx.infcx(); |
f035d41b | 169 | infcx.commit_if_ok(|_snapshot| { |
29967ef6 | 170 | let placeholder_predicate = |
fc512014 | 171 | infcx.replace_bound_vars_with_placeholders(obligation.predicate); |
ba9703b0 XL |
172 | |
173 | let placeholder_obligation = obligation.with(placeholder_predicate); | |
174 | let result = project_and_unify_type(selcx, &placeholder_obligation)?; | |
ba9703b0 XL |
175 | Ok(result) |
176 | }) | |
177 | } | |
178 | ||
179 | /// Evaluates constraints of the form: | |
180 | /// | |
181 | /// <T as Trait>::U == V | |
182 | /// | |
183 | /// If successful, this may result in additional obligations. | |
f9652781 XL |
184 | /// |
185 | /// See [poly_project_and_unify_type] for an explanation of the return value. | |
ba9703b0 XL |
186 | fn project_and_unify_type<'cx, 'tcx>( |
187 | selcx: &mut SelectionContext<'cx, 'tcx>, | |
188 | obligation: &ProjectionObligation<'tcx>, | |
f9652781 XL |
189 | ) -> Result< |
190 | Result<Option<Vec<PredicateObligation<'tcx>>>, InProgress>, | |
191 | MismatchedProjectionTypes<'tcx>, | |
192 | > { | |
29967ef6 | 193 | debug!(?obligation, "project_and_unify_type"); |
ba9703b0 XL |
194 | |
195 | let mut obligations = vec![]; | |
196 | let normalized_ty = match opt_normalize_projection_type( | |
197 | selcx, | |
198 | obligation.param_env, | |
199 | obligation.predicate.projection_ty, | |
200 | obligation.cause.clone(), | |
201 | obligation.recursion_depth, | |
202 | &mut obligations, | |
203 | ) { | |
f9652781 XL |
204 | Ok(Some(n)) => n, |
205 | Ok(None) => return Ok(Ok(None)), | |
206 | Err(InProgress) => return Ok(Err(InProgress)), | |
ba9703b0 XL |
207 | }; |
208 | ||
29967ef6 | 209 | debug!(?normalized_ty, ?obligations, "project_and_unify_type result"); |
ba9703b0 XL |
210 | |
211 | let infcx = selcx.infcx(); | |
212 | match infcx | |
213 | .at(&obligation.cause, obligation.param_env) | |
214 | .eq(normalized_ty, obligation.predicate.ty) | |
215 | { | |
216 | Ok(InferOk { obligations: inferred_obligations, value: () }) => { | |
217 | obligations.extend(inferred_obligations); | |
f9652781 | 218 | Ok(Ok(Some(obligations))) |
ba9703b0 XL |
219 | } |
220 | Err(err) => { | |
221 | debug!("project_and_unify_type: equating types encountered error {:?}", err); | |
222 | Err(MismatchedProjectionTypes { err }) | |
223 | } | |
224 | } | |
225 | } | |
226 | ||
227 | /// Normalizes any associated type projections in `value`, replacing | |
228 | /// them with a fully resolved type where possible. The return value | |
229 | /// combines the normalized result and any additional obligations that | |
230 | /// were incurred as result. | |
231 | pub fn normalize<'a, 'b, 'tcx, T>( | |
232 | selcx: &'a mut SelectionContext<'b, 'tcx>, | |
233 | param_env: ty::ParamEnv<'tcx>, | |
234 | cause: ObligationCause<'tcx>, | |
fc512014 | 235 | value: T, |
ba9703b0 XL |
236 | ) -> Normalized<'tcx, T> |
237 | where | |
238 | T: TypeFoldable<'tcx>, | |
239 | { | |
240 | let mut obligations = Vec::new(); | |
241 | let value = normalize_to(selcx, param_env, cause, value, &mut obligations); | |
242 | Normalized { value, obligations } | |
243 | } | |
244 | ||
245 | pub fn normalize_to<'a, 'b, 'tcx, T>( | |
246 | selcx: &'a mut SelectionContext<'b, 'tcx>, | |
247 | param_env: ty::ParamEnv<'tcx>, | |
248 | cause: ObligationCause<'tcx>, | |
fc512014 | 249 | value: T, |
ba9703b0 XL |
250 | obligations: &mut Vec<PredicateObligation<'tcx>>, |
251 | ) -> T | |
252 | where | |
253 | T: TypeFoldable<'tcx>, | |
254 | { | |
255 | normalize_with_depth_to(selcx, param_env, cause, 0, value, obligations) | |
256 | } | |
257 | ||
258 | /// As `normalize`, but with a custom depth. | |
259 | pub fn normalize_with_depth<'a, 'b, 'tcx, T>( | |
260 | selcx: &'a mut SelectionContext<'b, 'tcx>, | |
261 | param_env: ty::ParamEnv<'tcx>, | |
262 | cause: ObligationCause<'tcx>, | |
263 | depth: usize, | |
fc512014 | 264 | value: T, |
ba9703b0 XL |
265 | ) -> Normalized<'tcx, T> |
266 | where | |
267 | T: TypeFoldable<'tcx>, | |
268 | { | |
269 | let mut obligations = Vec::new(); | |
270 | let value = normalize_with_depth_to(selcx, param_env, cause, depth, value, &mut obligations); | |
271 | Normalized { value, obligations } | |
272 | } | |
273 | ||
29967ef6 | 274 | #[instrument(level = "debug", skip(selcx, param_env, cause, obligations))] |
ba9703b0 XL |
275 | pub fn normalize_with_depth_to<'a, 'b, 'tcx, T>( |
276 | selcx: &'a mut SelectionContext<'b, 'tcx>, | |
277 | param_env: ty::ParamEnv<'tcx>, | |
278 | cause: ObligationCause<'tcx>, | |
279 | depth: usize, | |
fc512014 | 280 | value: T, |
ba9703b0 XL |
281 | obligations: &mut Vec<PredicateObligation<'tcx>>, |
282 | ) -> T | |
283 | where | |
284 | T: TypeFoldable<'tcx>, | |
285 | { | |
ba9703b0 | 286 | let mut normalizer = AssocTypeNormalizer::new(selcx, param_env, cause, depth, obligations); |
f9f354fc | 287 | let result = ensure_sufficient_stack(|| normalizer.fold(value)); |
29967ef6 XL |
288 | debug!(?result, obligations.len = normalizer.obligations.len()); |
289 | debug!(?normalizer.obligations,); | |
ba9703b0 XL |
290 | result |
291 | } | |
292 | ||
293 | struct AssocTypeNormalizer<'a, 'b, 'tcx> { | |
294 | selcx: &'a mut SelectionContext<'b, 'tcx>, | |
295 | param_env: ty::ParamEnv<'tcx>, | |
296 | cause: ObligationCause<'tcx>, | |
297 | obligations: &'a mut Vec<PredicateObligation<'tcx>>, | |
298 | depth: usize, | |
299 | } | |
300 | ||
301 | impl<'a, 'b, 'tcx> AssocTypeNormalizer<'a, 'b, 'tcx> { | |
302 | fn new( | |
303 | selcx: &'a mut SelectionContext<'b, 'tcx>, | |
304 | param_env: ty::ParamEnv<'tcx>, | |
305 | cause: ObligationCause<'tcx>, | |
306 | depth: usize, | |
307 | obligations: &'a mut Vec<PredicateObligation<'tcx>>, | |
308 | ) -> AssocTypeNormalizer<'a, 'b, 'tcx> { | |
309 | AssocTypeNormalizer { selcx, param_env, cause, obligations, depth } | |
310 | } | |
311 | ||
fc512014 | 312 | fn fold<T: TypeFoldable<'tcx>>(&mut self, value: T) -> T { |
ba9703b0 XL |
313 | let value = self.selcx.infcx().resolve_vars_if_possible(value); |
314 | ||
315 | if !value.has_projections() { value } else { value.fold_with(self) } | |
316 | } | |
317 | } | |
318 | ||
319 | impl<'a, 'b, 'tcx> TypeFolder<'tcx> for AssocTypeNormalizer<'a, 'b, 'tcx> { | |
320 | fn tcx<'c>(&'c self) -> TyCtxt<'tcx> { | |
321 | self.selcx.tcx() | |
322 | } | |
323 | ||
324 | fn fold_ty(&mut self, ty: Ty<'tcx>) -> Ty<'tcx> { | |
325 | if !ty.has_projections() { | |
326 | return ty; | |
327 | } | |
328 | // We don't want to normalize associated types that occur inside of region | |
329 | // binders, because they may contain bound regions, and we can't cope with that. | |
330 | // | |
331 | // Example: | |
332 | // | |
333 | // for<'a> fn(<T as Foo<&'a>>::A) | |
334 | // | |
335 | // Instead of normalizing `<T as Foo<&'a>>::A` here, we'll | |
336 | // normalize it when we instantiate those bound regions (which | |
337 | // should occur eventually). | |
338 | ||
339 | let ty = ty.super_fold_with(self); | |
1b1a35ee XL |
340 | match *ty.kind() { |
341 | ty::Opaque(def_id, substs) if !substs.has_escaping_bound_vars() => { | |
ba9703b0 | 342 | // Only normalize `impl Trait` after type-checking, usually in codegen. |
f035d41b | 343 | match self.param_env.reveal() { |
ba9703b0 XL |
344 | Reveal::UserFacing => ty, |
345 | ||
346 | Reveal::All => { | |
f9f354fc XL |
347 | let recursion_limit = self.tcx().sess.recursion_limit(); |
348 | if !recursion_limit.value_within_limit(self.depth) { | |
ba9703b0 XL |
349 | let obligation = Obligation::with_depth( |
350 | self.cause.clone(), | |
f9f354fc | 351 | recursion_limit.0, |
ba9703b0 XL |
352 | self.param_env, |
353 | ty, | |
354 | ); | |
355 | self.selcx.infcx().report_overflow_error(&obligation, true); | |
356 | } | |
357 | ||
358 | let generic_ty = self.tcx().type_of(def_id); | |
359 | let concrete_ty = generic_ty.subst(self.tcx(), substs); | |
360 | self.depth += 1; | |
361 | let folded_ty = self.fold_ty(concrete_ty); | |
362 | self.depth -= 1; | |
363 | folded_ty | |
364 | } | |
365 | } | |
366 | } | |
367 | ||
fc512014 | 368 | ty::Projection(data) if !data.has_escaping_bound_vars() => { |
f9652781 | 369 | // This is kind of hacky -- we need to be able to |
ba9703b0 XL |
370 | // handle normalization within binders because |
371 | // otherwise we wind up a need to normalize when doing | |
372 | // trait matching (since you can have a trait | |
f035d41b | 373 | // obligation like `for<'a> T::B: Fn(&'a i32)`), but |
ba9703b0 XL |
374 | // we can't normalize with bound regions in scope. So |
375 | // far now we just ignore binders but only normalize | |
376 | // if all bound regions are gone (and then we still | |
377 | // have to renormalize whenever we instantiate a | |
378 | // binder). It would be better to normalize in a | |
379 | // binding-aware fashion. | |
380 | ||
381 | let normalized_ty = normalize_projection_type( | |
382 | self.selcx, | |
383 | self.param_env, | |
fc512014 | 384 | data, |
ba9703b0 XL |
385 | self.cause.clone(), |
386 | self.depth, | |
387 | &mut self.obligations, | |
388 | ); | |
389 | debug!( | |
29967ef6 XL |
390 | ?self.depth, |
391 | ?ty, | |
392 | ?normalized_ty, | |
393 | obligations.len = ?self.obligations.len(), | |
394 | "AssocTypeNormalizer: normalized type" | |
ba9703b0 XL |
395 | ); |
396 | normalized_ty | |
397 | } | |
398 | ||
399 | _ => ty, | |
400 | } | |
401 | } | |
402 | ||
403 | fn fold_const(&mut self, constant: &'tcx ty::Const<'tcx>) -> &'tcx ty::Const<'tcx> { | |
f9f354fc XL |
404 | if self.selcx.tcx().lazy_normalization() { |
405 | constant | |
406 | } else { | |
407 | let constant = constant.super_fold_with(self); | |
408 | constant.eval(self.selcx.tcx(), self.param_env) | |
409 | } | |
ba9703b0 XL |
410 | } |
411 | } | |
412 | ||
413 | /// The guts of `normalize`: normalize a specific projection like `<T | |
414 | /// as Trait>::Item`. The result is always a type (and possibly | |
415 | /// additional obligations). If ambiguity arises, which implies that | |
416 | /// there are unresolved type variables in the projection, we will | |
417 | /// substitute a fresh type variable `$X` and generate a new | |
418 | /// obligation `<T as Trait>::Item == $X` for later. | |
419 | pub fn normalize_projection_type<'a, 'b, 'tcx>( | |
420 | selcx: &'a mut SelectionContext<'b, 'tcx>, | |
421 | param_env: ty::ParamEnv<'tcx>, | |
422 | projection_ty: ty::ProjectionTy<'tcx>, | |
423 | cause: ObligationCause<'tcx>, | |
424 | depth: usize, | |
425 | obligations: &mut Vec<PredicateObligation<'tcx>>, | |
426 | ) -> Ty<'tcx> { | |
427 | opt_normalize_projection_type( | |
428 | selcx, | |
429 | param_env, | |
430 | projection_ty, | |
431 | cause.clone(), | |
432 | depth, | |
433 | obligations, | |
434 | ) | |
f9652781 XL |
435 | .ok() |
436 | .flatten() | |
ba9703b0 XL |
437 | .unwrap_or_else(move || { |
438 | // if we bottom out in ambiguity, create a type variable | |
439 | // and a deferred predicate to resolve this when more type | |
440 | // information is available. | |
441 | ||
442 | let tcx = selcx.infcx().tcx; | |
443 | let def_id = projection_ty.item_def_id; | |
444 | let ty_var = selcx.infcx().next_ty_var(TypeVariableOrigin { | |
445 | kind: TypeVariableOriginKind::NormalizeProjectionType, | |
446 | span: tcx.def_span(def_id), | |
447 | }); | |
448 | let projection = ty::Binder::dummy(ty::ProjectionPredicate { projection_ty, ty: ty_var }); | |
449 | let obligation = | |
f9f354fc | 450 | Obligation::with_depth(cause, depth + 1, param_env, projection.to_predicate(tcx)); |
ba9703b0 XL |
451 | obligations.push(obligation); |
452 | ty_var | |
453 | }) | |
454 | } | |
455 | ||
456 | /// The guts of `normalize`: normalize a specific projection like `<T | |
457 | /// as Trait>::Item`. The result is always a type (and possibly | |
458 | /// additional obligations). Returns `None` in the case of ambiguity, | |
459 | /// which indicates that there are unbound type variables. | |
460 | /// | |
461 | /// This function used to return `Option<NormalizedTy<'tcx>>`, which contains a | |
462 | /// `Ty<'tcx>` and an obligations vector. But that obligation vector was very | |
463 | /// often immediately appended to another obligations vector. So now this | |
464 | /// function takes an obligations vector and appends to it directly, which is | |
465 | /// slightly uglier but avoids the need for an extra short-lived allocation. | |
29967ef6 | 466 | #[instrument(level = "debug", skip(selcx, param_env, cause, obligations))] |
ba9703b0 XL |
467 | fn opt_normalize_projection_type<'a, 'b, 'tcx>( |
468 | selcx: &'a mut SelectionContext<'b, 'tcx>, | |
469 | param_env: ty::ParamEnv<'tcx>, | |
470 | projection_ty: ty::ProjectionTy<'tcx>, | |
471 | cause: ObligationCause<'tcx>, | |
472 | depth: usize, | |
473 | obligations: &mut Vec<PredicateObligation<'tcx>>, | |
f9652781 | 474 | ) -> Result<Option<Ty<'tcx>>, InProgress> { |
ba9703b0 XL |
475 | let infcx = selcx.infcx(); |
476 | ||
fc512014 | 477 | let projection_ty = infcx.resolve_vars_if_possible(projection_ty); |
ba9703b0 XL |
478 | let cache_key = ProjectionCacheKey::new(projection_ty); |
479 | ||
ba9703b0 XL |
480 | // FIXME(#20304) For now, I am caching here, which is good, but it |
481 | // means we don't capture the type variables that are created in | |
482 | // the case of ambiguity. Which means we may create a large stream | |
483 | // of such variables. OTOH, if we move the caching up a level, we | |
484 | // would not benefit from caching when proving `T: Trait<U=Foo>` | |
485 | // bounds. It might be the case that we want two distinct caches, | |
486 | // or else another kind of cache entry. | |
487 | ||
f9f354fc | 488 | let cache_result = infcx.inner.borrow_mut().projection_cache().try_start(cache_key); |
ba9703b0 XL |
489 | match cache_result { |
490 | Ok(()) => {} | |
491 | Err(ProjectionCacheEntry::Ambiguous) => { | |
492 | // If we found ambiguity the last time, that means we will continue | |
493 | // to do so until some type in the key changes (and we know it | |
494 | // hasn't, because we just fully resolved it). | |
29967ef6 | 495 | debug!("found cache entry: ambiguous"); |
f9652781 | 496 | return Ok(None); |
ba9703b0 XL |
497 | } |
498 | Err(ProjectionCacheEntry::InProgress) => { | |
ba9703b0 XL |
499 | // Under lazy normalization, this can arise when |
500 | // bootstrapping. That is, imagine an environment with a | |
501 | // where-clause like `A::B == u32`. Now, if we are asked | |
502 | // to normalize `A::B`, we will want to check the | |
503 | // where-clauses in scope. So we will try to unify `A::B` | |
504 | // with `A::B`, which can trigger a recursive | |
f9652781 | 505 | // normalization. |
ba9703b0 | 506 | |
29967ef6 | 507 | debug!("found cache entry: in-progress"); |
ba9703b0 | 508 | |
b9856134 XL |
509 | // Cache that normalizing this projection resulted in a cycle. This |
510 | // should ensure that, unless this happens within a snapshot that's | |
511 | // rolled back, fulfillment or evaluation will notice the cycle. | |
512 | ||
513 | infcx.inner.borrow_mut().projection_cache().recur(cache_key); | |
514 | return Err(InProgress); | |
515 | } | |
516 | Err(ProjectionCacheEntry::Recur) => { | |
f9652781 | 517 | return Err(InProgress); |
ba9703b0 XL |
518 | } |
519 | Err(ProjectionCacheEntry::NormalizedTy(ty)) => { | |
520 | // This is the hottest path in this function. | |
521 | // | |
522 | // If we find the value in the cache, then return it along | |
523 | // with the obligations that went along with it. Note | |
524 | // that, when using a fulfillment context, these | |
525 | // obligations could in principle be ignored: they have | |
526 | // already been registered when the cache entry was | |
527 | // created (and hence the new ones will quickly be | |
528 | // discarded as duplicated). But when doing trait | |
529 | // evaluation this is not the case, and dropping the trait | |
530 | // evaluations can causes ICEs (e.g., #43132). | |
29967ef6 | 531 | debug!(?ty, "found normalized ty"); |
ba9703b0 XL |
532 | |
533 | // Once we have inferred everything we need to know, we | |
534 | // can ignore the `obligations` from that point on. | |
535 | if infcx.unresolved_type_vars(&ty.value).is_none() { | |
f9f354fc | 536 | infcx.inner.borrow_mut().projection_cache().complete_normalized(cache_key, &ty); |
ba9703b0 XL |
537 | // No need to extend `obligations`. |
538 | } else { | |
539 | obligations.extend(ty.obligations); | |
540 | } | |
f9652781 | 541 | return Ok(Some(ty.value)); |
ba9703b0 XL |
542 | } |
543 | Err(ProjectionCacheEntry::Error) => { | |
29967ef6 | 544 | debug!("opt_normalize_projection_type: found error"); |
ba9703b0 XL |
545 | let result = normalize_to_error(selcx, param_env, projection_ty, cause, depth); |
546 | obligations.extend(result.obligations); | |
f9652781 | 547 | return Ok(Some(result.value)); |
ba9703b0 XL |
548 | } |
549 | } | |
550 | ||
551 | let obligation = Obligation::with_depth(cause.clone(), depth, param_env, projection_ty); | |
552 | match project_type(selcx, &obligation) { | |
553 | Ok(ProjectedTy::Progress(Progress { | |
554 | ty: projected_ty, | |
555 | obligations: mut projected_obligations, | |
556 | })) => { | |
557 | // if projection succeeded, then what we get out of this | |
558 | // is also non-normalized (consider: it was derived from | |
559 | // an impl, where-clause etc) and hence we must | |
560 | // re-normalize it | |
561 | ||
29967ef6 | 562 | debug!(?projected_ty, ?depth, ?projected_obligations); |
ba9703b0 XL |
563 | |
564 | let result = if projected_ty.has_projections() { | |
565 | let mut normalizer = AssocTypeNormalizer::new( | |
566 | selcx, | |
567 | param_env, | |
568 | cause, | |
569 | depth + 1, | |
570 | &mut projected_obligations, | |
571 | ); | |
fc512014 | 572 | let normalized_ty = normalizer.fold(projected_ty); |
ba9703b0 | 573 | |
29967ef6 | 574 | debug!(?normalized_ty, ?depth); |
ba9703b0 XL |
575 | |
576 | Normalized { value: normalized_ty, obligations: projected_obligations } | |
577 | } else { | |
578 | Normalized { value: projected_ty, obligations: projected_obligations } | |
579 | }; | |
580 | ||
581 | let cache_value = prune_cache_value_obligations(infcx, &result); | |
f9f354fc | 582 | infcx.inner.borrow_mut().projection_cache().insert_ty(cache_key, cache_value); |
ba9703b0 | 583 | obligations.extend(result.obligations); |
f9652781 | 584 | Ok(Some(result.value)) |
ba9703b0 XL |
585 | } |
586 | Ok(ProjectedTy::NoProgress(projected_ty)) => { | |
29967ef6 | 587 | debug!(?projected_ty, "opt_normalize_projection_type: no progress"); |
ba9703b0 | 588 | let result = Normalized { value: projected_ty, obligations: vec![] }; |
f9f354fc | 589 | infcx.inner.borrow_mut().projection_cache().insert_ty(cache_key, result.clone()); |
ba9703b0 | 590 | // No need to extend `obligations`. |
f9652781 | 591 | Ok(Some(result.value)) |
ba9703b0 XL |
592 | } |
593 | Err(ProjectionTyError::TooManyCandidates) => { | |
29967ef6 | 594 | debug!("opt_normalize_projection_type: too many candidates"); |
f9f354fc | 595 | infcx.inner.borrow_mut().projection_cache().ambiguous(cache_key); |
f9652781 | 596 | Ok(None) |
ba9703b0 XL |
597 | } |
598 | Err(ProjectionTyError::TraitSelectionError(_)) => { | |
599 | debug!("opt_normalize_projection_type: ERROR"); | |
600 | // if we got an error processing the `T as Trait` part, | |
601 | // just return `ty::err` but add the obligation `T : | |
602 | // Trait`, which when processed will cause the error to be | |
603 | // reported later | |
604 | ||
f9f354fc | 605 | infcx.inner.borrow_mut().projection_cache().error(cache_key); |
ba9703b0 XL |
606 | let result = normalize_to_error(selcx, param_env, projection_ty, cause, depth); |
607 | obligations.extend(result.obligations); | |
f9652781 | 608 | Ok(Some(result.value)) |
ba9703b0 XL |
609 | } |
610 | } | |
611 | } | |
612 | ||
613 | /// If there are unresolved type variables, then we need to include | |
614 | /// any subobligations that bind them, at least until those type | |
615 | /// variables are fully resolved. | |
616 | fn prune_cache_value_obligations<'a, 'tcx>( | |
617 | infcx: &'a InferCtxt<'a, 'tcx>, | |
618 | result: &NormalizedTy<'tcx>, | |
619 | ) -> NormalizedTy<'tcx> { | |
620 | if infcx.unresolved_type_vars(&result.value).is_none() { | |
621 | return NormalizedTy { value: result.value, obligations: vec![] }; | |
622 | } | |
623 | ||
624 | let mut obligations: Vec<_> = result | |
625 | .obligations | |
626 | .iter() | |
3dfed10e | 627 | .filter(|obligation| { |
5869c6ff | 628 | let bound_predicate = obligation.predicate.kind(); |
29967ef6 | 629 | match bound_predicate.skip_binder() { |
3dfed10e XL |
630 | // We found a `T: Foo<X = U>` predicate, let's check |
631 | // if `U` references any unresolved type | |
632 | // variables. In principle, we only care if this | |
633 | // projection can help resolve any of the type | |
634 | // variables found in `result.value` -- but we just | |
635 | // check for any type variables here, for fear of | |
636 | // indirect obligations (e.g., we project to `?0`, | |
637 | // but we have `T: Foo<X = ?1>` and `?1: Bar<X = | |
638 | // ?0>`). | |
5869c6ff | 639 | ty::PredicateKind::Projection(data) => { |
29967ef6 | 640 | infcx.unresolved_type_vars(&bound_predicate.rebind(data.ty)).is_some() |
3dfed10e | 641 | } |
ba9703b0 | 642 | |
3dfed10e XL |
643 | // We are only interested in `T: Foo<X = U>` predicates, whre |
644 | // `U` references one of `unresolved_type_vars`. =) | |
645 | _ => false, | |
646 | } | |
ba9703b0 XL |
647 | }) |
648 | .cloned() | |
649 | .collect(); | |
650 | ||
651 | obligations.shrink_to_fit(); | |
652 | ||
653 | NormalizedTy { value: result.value, obligations } | |
654 | } | |
655 | ||
ba9703b0 XL |
656 | /// If we are projecting `<T as Trait>::Item`, but `T: Trait` does not |
657 | /// hold. In various error cases, we cannot generate a valid | |
658 | /// normalized projection. Therefore, we create an inference variable | |
659 | /// return an associated obligation that, when fulfilled, will lead to | |
660 | /// an error. | |
661 | /// | |
662 | /// Note that we used to return `Error` here, but that was quite | |
663 | /// dubious -- the premise was that an error would *eventually* be | |
664 | /// reported, when the obligation was processed. But in general once | |
665 | /// you see a `Error` you are supposed to be able to assume that an | |
666 | /// error *has been* reported, so that you can take whatever heuristic | |
667 | /// paths you want to take. To make things worse, it was possible for | |
668 | /// cycles to arise, where you basically had a setup like `<MyType<$0> | |
669 | /// as Trait>::Foo == $0`. Here, normalizing `<MyType<$0> as | |
670 | /// Trait>::Foo> to `[type error]` would lead to an obligation of | |
671 | /// `<MyType<[type error]> as Trait>::Foo`. We are supposed to report | |
672 | /// an error for this obligation, but we legitimately should not, | |
673 | /// because it contains `[type error]`. Yuck! (See issue #29857 for | |
674 | /// one case where this arose.) | |
675 | fn normalize_to_error<'a, 'tcx>( | |
676 | selcx: &mut SelectionContext<'a, 'tcx>, | |
677 | param_env: ty::ParamEnv<'tcx>, | |
678 | projection_ty: ty::ProjectionTy<'tcx>, | |
679 | cause: ObligationCause<'tcx>, | |
680 | depth: usize, | |
681 | ) -> NormalizedTy<'tcx> { | |
682 | let trait_ref = projection_ty.trait_ref(selcx.tcx()).to_poly_trait_ref(); | |
683 | let trait_obligation = Obligation { | |
684 | cause, | |
685 | recursion_depth: depth, | |
686 | param_env, | |
f9f354fc | 687 | predicate: trait_ref.without_const().to_predicate(selcx.tcx()), |
ba9703b0 XL |
688 | }; |
689 | let tcx = selcx.infcx().tcx; | |
690 | let def_id = projection_ty.item_def_id; | |
691 | let new_value = selcx.infcx().next_ty_var(TypeVariableOrigin { | |
692 | kind: TypeVariableOriginKind::NormalizeProjectionType, | |
693 | span: tcx.def_span(def_id), | |
694 | }); | |
695 | Normalized { value: new_value, obligations: vec![trait_obligation] } | |
696 | } | |
697 | ||
698 | enum ProjectedTy<'tcx> { | |
699 | Progress(Progress<'tcx>), | |
700 | NoProgress(Ty<'tcx>), | |
701 | } | |
702 | ||
703 | struct Progress<'tcx> { | |
704 | ty: Ty<'tcx>, | |
705 | obligations: Vec<PredicateObligation<'tcx>>, | |
706 | } | |
707 | ||
708 | impl<'tcx> Progress<'tcx> { | |
709 | fn error(tcx: TyCtxt<'tcx>) -> Self { | |
f035d41b | 710 | Progress { ty: tcx.ty_error(), obligations: vec![] } |
ba9703b0 XL |
711 | } |
712 | ||
713 | fn with_addl_obligations(mut self, mut obligations: Vec<PredicateObligation<'tcx>>) -> Self { | |
714 | debug!( | |
29967ef6 XL |
715 | self.obligations.len = ?self.obligations.len(), |
716 | obligations.len = obligations.len(), | |
717 | "with_addl_obligations" | |
ba9703b0 XL |
718 | ); |
719 | ||
29967ef6 | 720 | debug!(?self.obligations, ?obligations, "with_addl_obligations"); |
ba9703b0 XL |
721 | |
722 | self.obligations.append(&mut obligations); | |
723 | self | |
724 | } | |
725 | } | |
726 | ||
727 | /// Computes the result of a projection type (if we can). | |
728 | /// | |
729 | /// IMPORTANT: | |
730 | /// - `obligation` must be fully normalized | |
731 | fn project_type<'cx, 'tcx>( | |
732 | selcx: &mut SelectionContext<'cx, 'tcx>, | |
733 | obligation: &ProjectionTyObligation<'tcx>, | |
734 | ) -> Result<ProjectedTy<'tcx>, ProjectionTyError<'tcx>> { | |
29967ef6 | 735 | debug!(?obligation, "project_type"); |
ba9703b0 | 736 | |
f9f354fc | 737 | if !selcx.tcx().sess.recursion_limit().value_within_limit(obligation.recursion_depth) { |
ba9703b0 | 738 | debug!("project: overflow!"); |
fc512014 XL |
739 | // This should really be an immediate error, but some existing code |
740 | // relies on being able to recover from this. | |
741 | return Err(ProjectionTyError::TraitSelectionError(SelectionError::Overflow)); | |
ba9703b0 XL |
742 | } |
743 | ||
6a06907d | 744 | if obligation.predicate.references_error() { |
ba9703b0 XL |
745 | return Ok(ProjectedTy::Progress(Progress::error(selcx.tcx()))); |
746 | } | |
747 | ||
748 | let mut candidates = ProjectionTyCandidateSet::None; | |
749 | ||
750 | // Make sure that the following procedures are kept in order. ParamEnv | |
751 | // needs to be first because it has highest priority, and Select checks | |
752 | // the return value of push_candidate which assumes it's ran at last. | |
6a06907d | 753 | assemble_candidates_from_param_env(selcx, obligation, &mut candidates); |
ba9703b0 | 754 | |
6a06907d | 755 | assemble_candidates_from_trait_def(selcx, obligation, &mut candidates); |
ba9703b0 | 756 | |
6a06907d | 757 | assemble_candidates_from_object_ty(selcx, obligation, &mut candidates); |
29967ef6 XL |
758 | |
759 | if let ProjectionTyCandidateSet::Single(ProjectionTyCandidate::Object(_)) = candidates { | |
760 | // Avoid normalization cycle from selection (see | |
761 | // `assemble_candidates_from_object_ty`). | |
762 | // FIXME(lazy_normalization): Lazy normalization should save us from | |
6a06907d | 763 | // having to special case this. |
29967ef6 | 764 | } else { |
6a06907d | 765 | assemble_candidates_from_impls(selcx, obligation, &mut candidates); |
29967ef6 | 766 | }; |
ba9703b0 XL |
767 | |
768 | match candidates { | |
29967ef6 XL |
769 | ProjectionTyCandidateSet::Single(candidate) => { |
770 | Ok(ProjectedTy::Progress(confirm_candidate(selcx, obligation, candidate))) | |
771 | } | |
ba9703b0 XL |
772 | ProjectionTyCandidateSet::None => Ok(ProjectedTy::NoProgress( |
773 | selcx | |
774 | .tcx() | |
775 | .mk_projection(obligation.predicate.item_def_id, obligation.predicate.substs), | |
776 | )), | |
777 | // Error occurred while trying to processing impls. | |
778 | ProjectionTyCandidateSet::Error(e) => Err(ProjectionTyError::TraitSelectionError(e)), | |
779 | // Inherent ambiguity that prevents us from even enumerating the | |
780 | // candidates. | |
781 | ProjectionTyCandidateSet::Ambiguous => Err(ProjectionTyError::TooManyCandidates), | |
782 | } | |
783 | } | |
784 | ||
785 | /// The first thing we have to do is scan through the parameter | |
786 | /// environment to see whether there are any projection predicates | |
787 | /// there that can answer this question. | |
788 | fn assemble_candidates_from_param_env<'cx, 'tcx>( | |
789 | selcx: &mut SelectionContext<'cx, 'tcx>, | |
790 | obligation: &ProjectionTyObligation<'tcx>, | |
ba9703b0 XL |
791 | candidate_set: &mut ProjectionTyCandidateSet<'tcx>, |
792 | ) { | |
793 | debug!("assemble_candidates_from_param_env(..)"); | |
794 | assemble_candidates_from_predicates( | |
795 | selcx, | |
796 | obligation, | |
ba9703b0 XL |
797 | candidate_set, |
798 | ProjectionTyCandidate::ParamEnv, | |
f035d41b | 799 | obligation.param_env.caller_bounds().iter(), |
29967ef6 | 800 | false, |
ba9703b0 XL |
801 | ); |
802 | } | |
803 | ||
804 | /// In the case of a nested projection like <<A as Foo>::FooT as Bar>::BarT, we may find | |
805 | /// that the definition of `Foo` has some clues: | |
806 | /// | |
807 | /// ``` | |
808 | /// trait Foo { | |
809 | /// type FooT : Bar<BarT=i32> | |
810 | /// } | |
811 | /// ``` | |
812 | /// | |
813 | /// Here, for example, we could conclude that the result is `i32`. | |
814 | fn assemble_candidates_from_trait_def<'cx, 'tcx>( | |
815 | selcx: &mut SelectionContext<'cx, 'tcx>, | |
816 | obligation: &ProjectionTyObligation<'tcx>, | |
ba9703b0 XL |
817 | candidate_set: &mut ProjectionTyCandidateSet<'tcx>, |
818 | ) { | |
819 | debug!("assemble_candidates_from_trait_def(..)"); | |
820 | ||
821 | let tcx = selcx.tcx(); | |
822 | // Check whether the self-type is itself a projection. | |
f035d41b | 823 | // If so, extract what we know from the trait and try to come up with a good answer. |
6a06907d | 824 | let bounds = match *obligation.predicate.self_ty().kind() { |
29967ef6 XL |
825 | ty::Projection(ref data) => tcx.item_bounds(data.item_def_id).subst(tcx, data.substs), |
826 | ty::Opaque(def_id, substs) => tcx.item_bounds(def_id).subst(tcx, substs), | |
ba9703b0 XL |
827 | ty::Infer(ty::TyVar(_)) => { |
828 | // If the self-type is an inference variable, then it MAY wind up | |
829 | // being a projected type, so induce an ambiguity. | |
830 | candidate_set.mark_ambiguous(); | |
831 | return; | |
832 | } | |
833 | _ => return, | |
834 | }; | |
835 | ||
ba9703b0 XL |
836 | assemble_candidates_from_predicates( |
837 | selcx, | |
838 | obligation, | |
ba9703b0 XL |
839 | candidate_set, |
840 | ProjectionTyCandidate::TraitDef, | |
f035d41b | 841 | bounds.iter(), |
29967ef6 | 842 | true, |
ba9703b0 XL |
843 | ) |
844 | } | |
845 | ||
29967ef6 XL |
846 | /// In the case of a trait object like |
847 | /// `<dyn Iterator<Item = ()> as Iterator>::Item` we can use the existential | |
848 | /// predicate in the trait object. | |
849 | /// | |
850 | /// We don't go through the select candidate for these bounds to avoid cycles: | |
851 | /// In the above case, `dyn Iterator<Item = ()>: Iterator` would create a | |
852 | /// nested obligation of `<dyn Iterator<Item = ()> as Iterator>::Item: Sized`, | |
853 | /// this then has to be normalized without having to prove | |
854 | /// `dyn Iterator<Item = ()>: Iterator` again. | |
855 | fn assemble_candidates_from_object_ty<'cx, 'tcx>( | |
856 | selcx: &mut SelectionContext<'cx, 'tcx>, | |
857 | obligation: &ProjectionTyObligation<'tcx>, | |
29967ef6 XL |
858 | candidate_set: &mut ProjectionTyCandidateSet<'tcx>, |
859 | ) { | |
860 | debug!("assemble_candidates_from_object_ty(..)"); | |
861 | ||
862 | let tcx = selcx.tcx(); | |
863 | ||
6a06907d | 864 | let self_ty = obligation.predicate.self_ty(); |
29967ef6 XL |
865 | let object_ty = selcx.infcx().shallow_resolve(self_ty); |
866 | let data = match object_ty.kind() { | |
867 | ty::Dynamic(data, ..) => data, | |
868 | ty::Infer(ty::TyVar(_)) => { | |
869 | // If the self-type is an inference variable, then it MAY wind up | |
870 | // being an object type, so induce an ambiguity. | |
871 | candidate_set.mark_ambiguous(); | |
872 | return; | |
873 | } | |
874 | _ => return, | |
875 | }; | |
876 | let env_predicates = data | |
877 | .projection_bounds() | |
878 | .filter(|bound| bound.item_def_id() == obligation.predicate.item_def_id) | |
879 | .map(|p| p.with_self_ty(tcx, object_ty).to_predicate(tcx)); | |
880 | ||
881 | assemble_candidates_from_predicates( | |
882 | selcx, | |
883 | obligation, | |
29967ef6 XL |
884 | candidate_set, |
885 | ProjectionTyCandidate::Object, | |
886 | env_predicates, | |
887 | false, | |
888 | ); | |
889 | } | |
890 | ||
ba9703b0 XL |
891 | fn assemble_candidates_from_predicates<'cx, 'tcx>( |
892 | selcx: &mut SelectionContext<'cx, 'tcx>, | |
893 | obligation: &ProjectionTyObligation<'tcx>, | |
ba9703b0 XL |
894 | candidate_set: &mut ProjectionTyCandidateSet<'tcx>, |
895 | ctor: fn(ty::PolyProjectionPredicate<'tcx>) -> ProjectionTyCandidate<'tcx>, | |
896 | env_predicates: impl Iterator<Item = ty::Predicate<'tcx>>, | |
29967ef6 | 897 | potentially_unnormalized_candidates: bool, |
ba9703b0 | 898 | ) { |
29967ef6 XL |
899 | debug!(?obligation, "assemble_candidates_from_predicates"); |
900 | ||
ba9703b0 XL |
901 | let infcx = selcx.infcx(); |
902 | for predicate in env_predicates { | |
29967ef6 | 903 | debug!(?predicate); |
5869c6ff XL |
904 | let bound_predicate = predicate.kind(); |
905 | if let ty::PredicateKind::Projection(data) = predicate.kind().skip_binder() { | |
29967ef6 | 906 | let data = bound_predicate.rebind(data); |
ba9703b0 XL |
907 | let same_def_id = data.projection_def_id() == obligation.predicate.item_def_id; |
908 | ||
909 | let is_match = same_def_id | |
910 | && infcx.probe(|_| { | |
29967ef6 XL |
911 | selcx.match_projection_projections( |
912 | obligation, | |
6a06907d | 913 | data, |
29967ef6 XL |
914 | potentially_unnormalized_candidates, |
915 | ) | |
ba9703b0 XL |
916 | }); |
917 | ||
29967ef6 | 918 | debug!(?data, ?is_match, ?same_def_id); |
ba9703b0 XL |
919 | |
920 | if is_match { | |
921 | candidate_set.push_candidate(ctor(data)); | |
29967ef6 XL |
922 | |
923 | if potentially_unnormalized_candidates | |
924 | && !obligation.predicate.has_infer_types_or_consts() | |
925 | { | |
926 | // HACK: Pick the first trait def candidate for a fully | |
927 | // inferred predicate. This is to allow duplicates that | |
928 | // differ only in normalization. | |
929 | return; | |
930 | } | |
ba9703b0 XL |
931 | } |
932 | } | |
933 | } | |
934 | } | |
935 | ||
936 | fn assemble_candidates_from_impls<'cx, 'tcx>( | |
937 | selcx: &mut SelectionContext<'cx, 'tcx>, | |
938 | obligation: &ProjectionTyObligation<'tcx>, | |
ba9703b0 XL |
939 | candidate_set: &mut ProjectionTyCandidateSet<'tcx>, |
940 | ) { | |
29967ef6 XL |
941 | debug!("assemble_candidates_from_impls"); |
942 | ||
ba9703b0 XL |
943 | // If we are resolving `<T as TraitRef<...>>::Item == Type`, |
944 | // start out by selecting the predicate `T as TraitRef<...>`: | |
6a06907d | 945 | let poly_trait_ref = obligation.predicate.trait_ref(selcx.tcx()).to_poly_trait_ref(); |
ba9703b0 XL |
946 | let trait_obligation = obligation.with(poly_trait_ref.to_poly_trait_predicate()); |
947 | let _ = selcx.infcx().commit_if_ok(|_| { | |
f035d41b XL |
948 | let impl_source = match selcx.select(&trait_obligation) { |
949 | Ok(Some(impl_source)) => impl_source, | |
ba9703b0 XL |
950 | Ok(None) => { |
951 | candidate_set.mark_ambiguous(); | |
952 | return Err(()); | |
953 | } | |
954 | Err(e) => { | |
29967ef6 | 955 | debug!(error = ?e, "selection error"); |
ba9703b0 XL |
956 | candidate_set.mark_error(e); |
957 | return Err(()); | |
958 | } | |
959 | }; | |
960 | ||
f035d41b | 961 | let eligible = match &impl_source { |
1b1a35ee XL |
962 | super::ImplSource::Closure(_) |
963 | | super::ImplSource::Generator(_) | |
964 | | super::ImplSource::FnPointer(_) | |
1b1a35ee | 965 | | super::ImplSource::TraitAlias(_) => { |
29967ef6 | 966 | debug!(?impl_source); |
ba9703b0 XL |
967 | true |
968 | } | |
1b1a35ee | 969 | super::ImplSource::UserDefined(impl_data) => { |
ba9703b0 XL |
970 | // We have to be careful when projecting out of an |
971 | // impl because of specialization. If we are not in | |
972 | // codegen (i.e., projection mode is not "any"), and the | |
973 | // impl's type is declared as default, then we disable | |
974 | // projection (even if the trait ref is fully | |
975 | // monomorphic). In the case where trait ref is not | |
976 | // fully monomorphic (i.e., includes type parameters), | |
977 | // this is because those type parameters may | |
978 | // ultimately be bound to types from other crates that | |
979 | // may have specialized impls we can't see. In the | |
980 | // case where the trait ref IS fully monomorphic, this | |
981 | // is a policy decision that we made in the RFC in | |
982 | // order to preserve flexibility for the crate that | |
983 | // defined the specializable impl to specialize later | |
984 | // for existing types. | |
985 | // | |
986 | // In either case, we handle this by not adding a | |
987 | // candidate for an impl if it contains a `default` | |
988 | // type. | |
989 | // | |
990 | // NOTE: This should be kept in sync with the similar code in | |
fc512014 | 991 | // `rustc_ty_utils::instance::resolve_associated_item()`. |
ba9703b0 XL |
992 | let node_item = |
993 | assoc_ty_def(selcx, impl_data.impl_def_id, obligation.predicate.item_def_id) | |
994 | .map_err(|ErrorReported| ())?; | |
995 | ||
996 | if node_item.is_final() { | |
997 | // Non-specializable items are always projectable. | |
998 | true | |
999 | } else { | |
1000 | // Only reveal a specializable default if we're past type-checking | |
1001 | // and the obligation is monomorphic, otherwise passes such as | |
1002 | // transmute checking and polymorphic MIR optimizations could | |
1003 | // get a result which isn't correct for all monomorphizations. | |
f035d41b | 1004 | if obligation.param_env.reveal() == Reveal::All { |
ba9703b0 XL |
1005 | // NOTE(eddyb) inference variables can resolve to parameters, so |
1006 | // assume `poly_trait_ref` isn't monomorphic, if it contains any. | |
fc512014 | 1007 | let poly_trait_ref = selcx.infcx().resolve_vars_if_possible(poly_trait_ref); |
ba9703b0 XL |
1008 | !poly_trait_ref.still_further_specializable() |
1009 | } else { | |
1010 | debug!( | |
29967ef6 XL |
1011 | assoc_ty = ?selcx.tcx().def_path_str(node_item.item.def_id), |
1012 | ?obligation.predicate, | |
1013 | "assemble_candidates_from_impls: not eligible due to default", | |
ba9703b0 XL |
1014 | ); |
1015 | false | |
1016 | } | |
1017 | } | |
1018 | } | |
1b1a35ee | 1019 | super::ImplSource::DiscriminantKind(..) => { |
f9f354fc XL |
1020 | // While `DiscriminantKind` is automatically implemented for every type, |
1021 | // the concrete discriminant may not be known yet. | |
1022 | // | |
1023 | // Any type with multiple potential discriminant types is therefore not eligible. | |
1024 | let self_ty = selcx.infcx().shallow_resolve(obligation.predicate.self_ty()); | |
1025 | ||
1b1a35ee | 1026 | match self_ty.kind() { |
f9f354fc XL |
1027 | ty::Bool |
1028 | | ty::Char | |
1029 | | ty::Int(_) | |
1030 | | ty::Uint(_) | |
1031 | | ty::Float(_) | |
1032 | | ty::Adt(..) | |
1033 | | ty::Foreign(_) | |
1034 | | ty::Str | |
1035 | | ty::Array(..) | |
1036 | | ty::Slice(_) | |
1037 | | ty::RawPtr(..) | |
1038 | | ty::Ref(..) | |
1039 | | ty::FnDef(..) | |
1040 | | ty::FnPtr(..) | |
1041 | | ty::Dynamic(..) | |
1042 | | ty::Closure(..) | |
1043 | | ty::Generator(..) | |
1044 | | ty::GeneratorWitness(..) | |
1045 | | ty::Never | |
1046 | | ty::Tuple(..) | |
1047 | // Integers and floats always have `u8` as their discriminant. | |
1048 | | ty::Infer(ty::InferTy::IntVar(_) | ty::InferTy::FloatVar(..)) => true, | |
1049 | ||
1050 | ty::Projection(..) | |
1051 | | ty::Opaque(..) | |
1052 | | ty::Param(..) | |
1053 | | ty::Bound(..) | |
1054 | | ty::Placeholder(..) | |
1055 | | ty::Infer(..) | |
f035d41b | 1056 | | ty::Error(_) => false, |
f9f354fc XL |
1057 | } |
1058 | } | |
6a06907d XL |
1059 | super::ImplSource::Pointee(..) => { |
1060 | // While `Pointee` is automatically implemented for every type, | |
1061 | // the concrete metadata type may not be known yet. | |
1062 | // | |
1063 | // Any type with multiple potential metadata types is therefore not eligible. | |
1064 | let self_ty = selcx.infcx().shallow_resolve(obligation.predicate.self_ty()); | |
1065 | ||
1066 | // FIXME:Â should this normalize? | |
1067 | let tail = selcx.tcx().struct_tail_without_normalization(self_ty); | |
1068 | match tail.kind() { | |
1069 | ty::Bool | |
1070 | | ty::Char | |
1071 | | ty::Int(_) | |
1072 | | ty::Uint(_) | |
1073 | | ty::Float(_) | |
1074 | | ty::Foreign(_) | |
1075 | | ty::Str | |
1076 | | ty::Array(..) | |
1077 | | ty::Slice(_) | |
1078 | | ty::RawPtr(..) | |
1079 | | ty::Ref(..) | |
1080 | | ty::FnDef(..) | |
1081 | | ty::FnPtr(..) | |
1082 | | ty::Dynamic(..) | |
1083 | | ty::Closure(..) | |
1084 | | ty::Generator(..) | |
1085 | | ty::GeneratorWitness(..) | |
1086 | | ty::Never | |
1087 | // If returned by `struct_tail_without_normalization` this is a unit struct | |
1088 | // without any fields, or not a struct, and therefore is Sized. | |
1089 | | ty::Adt(..) | |
1090 | // If returned by `struct_tail_without_normalization` this is the empty tuple. | |
1091 | | ty::Tuple(..) | |
1092 | // Integers and floats are always Sized, and so have unit type metadata. | |
1093 | | ty::Infer(ty::InferTy::IntVar(_) | ty::InferTy::FloatVar(..)) => true, | |
1094 | ||
1095 | ty::Projection(..) | |
1096 | | ty::Opaque(..) | |
1097 | | ty::Param(..) | |
1098 | | ty::Bound(..) | |
1099 | | ty::Placeholder(..) | |
1100 | | ty::Infer(..) | |
1101 | | ty::Error(_) => false, | |
1102 | } | |
1103 | } | |
1b1a35ee | 1104 | super::ImplSource::Param(..) => { |
ba9703b0 XL |
1105 | // This case tell us nothing about the value of an |
1106 | // associated type. Consider: | |
1107 | // | |
1108 | // ``` | |
1109 | // trait SomeTrait { type Foo; } | |
1110 | // fn foo<T:SomeTrait>(...) { } | |
1111 | // ``` | |
1112 | // | |
1113 | // If the user writes `<T as SomeTrait>::Foo`, then the `T | |
1114 | // : SomeTrait` binding does not help us decide what the | |
1115 | // type `Foo` is (at least, not more specifically than | |
1116 | // what we already knew). | |
1117 | // | |
1118 | // But wait, you say! What about an example like this: | |
1119 | // | |
1120 | // ``` | |
1121 | // fn bar<T:SomeTrait<Foo=usize>>(...) { ... } | |
1122 | // ``` | |
1123 | // | |
1124 | // Doesn't the `T : Sometrait<Foo=usize>` predicate help | |
1125 | // resolve `T::Foo`? And of course it does, but in fact | |
1126 | // that single predicate is desugared into two predicates | |
1127 | // in the compiler: a trait predicate (`T : SomeTrait`) and a | |
1128 | // projection. And the projection where clause is handled | |
1129 | // in `assemble_candidates_from_param_env`. | |
1130 | false | |
1131 | } | |
29967ef6 XL |
1132 | super::ImplSource::Object(_) => { |
1133 | // Handled by the `Object` projection candidate. See | |
1134 | // `assemble_candidates_from_object_ty` for an explanation of | |
1135 | // why we special case object types. | |
1136 | false | |
1137 | } | |
1b1a35ee | 1138 | super::ImplSource::AutoImpl(..) | super::ImplSource::Builtin(..) => { |
ba9703b0 | 1139 | // These traits have no associated types. |
f9652781 | 1140 | selcx.tcx().sess.delay_span_bug( |
ba9703b0 | 1141 | obligation.cause.span, |
f9652781 | 1142 | &format!("Cannot project an associated type from `{:?}`", impl_source), |
ba9703b0 | 1143 | ); |
f9652781 | 1144 | return Err(()); |
ba9703b0 XL |
1145 | } |
1146 | }; | |
1147 | ||
1148 | if eligible { | |
f035d41b | 1149 | if candidate_set.push_candidate(ProjectionTyCandidate::Select(impl_source)) { |
ba9703b0 XL |
1150 | Ok(()) |
1151 | } else { | |
1152 | Err(()) | |
1153 | } | |
1154 | } else { | |
1155 | Err(()) | |
1156 | } | |
1157 | }); | |
1158 | } | |
1159 | ||
1160 | fn confirm_candidate<'cx, 'tcx>( | |
1161 | selcx: &mut SelectionContext<'cx, 'tcx>, | |
1162 | obligation: &ProjectionTyObligation<'tcx>, | |
ba9703b0 XL |
1163 | candidate: ProjectionTyCandidate<'tcx>, |
1164 | ) -> Progress<'tcx> { | |
29967ef6 | 1165 | debug!(?obligation, ?candidate, "confirm_candidate"); |
f035d41b | 1166 | let mut progress = match candidate { |
ba9703b0 | 1167 | ProjectionTyCandidate::ParamEnv(poly_projection) |
29967ef6 XL |
1168 | | ProjectionTyCandidate::Object(poly_projection) => { |
1169 | confirm_param_env_candidate(selcx, obligation, poly_projection, false) | |
1170 | } | |
1171 | ||
1172 | ProjectionTyCandidate::TraitDef(poly_projection) => { | |
1173 | confirm_param_env_candidate(selcx, obligation, poly_projection, true) | |
ba9703b0 XL |
1174 | } |
1175 | ||
f035d41b | 1176 | ProjectionTyCandidate::Select(impl_source) => { |
29967ef6 | 1177 | confirm_select_candidate(selcx, obligation, impl_source) |
ba9703b0 | 1178 | } |
f035d41b XL |
1179 | }; |
1180 | // When checking for cycle during evaluation, we compare predicates with | |
1181 | // "syntactic" equality. Since normalization generally introduces a type | |
1182 | // with new region variables, we need to resolve them to existing variables | |
1183 | // when possible for this to work. See `auto-trait-projection-recursion.rs` | |
1184 | // for a case where this matters. | |
1185 | if progress.ty.has_infer_regions() { | |
1186 | progress.ty = OpportunisticRegionResolver::new(selcx.infcx()).fold_ty(progress.ty); | |
ba9703b0 | 1187 | } |
f035d41b | 1188 | progress |
ba9703b0 XL |
1189 | } |
1190 | ||
1191 | fn confirm_select_candidate<'cx, 'tcx>( | |
1192 | selcx: &mut SelectionContext<'cx, 'tcx>, | |
1193 | obligation: &ProjectionTyObligation<'tcx>, | |
f035d41b | 1194 | impl_source: Selection<'tcx>, |
ba9703b0 | 1195 | ) -> Progress<'tcx> { |
f035d41b | 1196 | match impl_source { |
1b1a35ee XL |
1197 | super::ImplSource::UserDefined(data) => confirm_impl_candidate(selcx, obligation, data), |
1198 | super::ImplSource::Generator(data) => confirm_generator_candidate(selcx, obligation, data), | |
1199 | super::ImplSource::Closure(data) => confirm_closure_candidate(selcx, obligation, data), | |
1200 | super::ImplSource::FnPointer(data) => confirm_fn_pointer_candidate(selcx, obligation, data), | |
1201 | super::ImplSource::DiscriminantKind(data) => { | |
f9f354fc XL |
1202 | confirm_discriminant_kind_candidate(selcx, obligation, data) |
1203 | } | |
6a06907d | 1204 | super::ImplSource::Pointee(data) => confirm_pointee_candidate(selcx, obligation, data), |
29967ef6 XL |
1205 | super::ImplSource::Object(_) |
1206 | | super::ImplSource::AutoImpl(..) | |
1b1a35ee XL |
1207 | | super::ImplSource::Param(..) |
1208 | | super::ImplSource::Builtin(..) | |
29967ef6 XL |
1209 | | super::ImplSource::TraitAlias(..) => { |
1210 | // we don't create Select candidates with this kind of resolution | |
ba9703b0 XL |
1211 | span_bug!( |
1212 | obligation.cause.span, | |
1213 | "Cannot project an associated type from `{:?}`", | |
f035d41b | 1214 | impl_source |
ba9703b0 XL |
1215 | ) |
1216 | } | |
1217 | } | |
1218 | } | |
1219 | ||
ba9703b0 XL |
1220 | fn confirm_generator_candidate<'cx, 'tcx>( |
1221 | selcx: &mut SelectionContext<'cx, 'tcx>, | |
1222 | obligation: &ProjectionTyObligation<'tcx>, | |
f035d41b | 1223 | impl_source: ImplSourceGeneratorData<'tcx, PredicateObligation<'tcx>>, |
ba9703b0 | 1224 | ) -> Progress<'tcx> { |
f035d41b | 1225 | let gen_sig = impl_source.substs.as_generator().poly_sig(); |
ba9703b0 XL |
1226 | let Normalized { value: gen_sig, obligations } = normalize_with_depth( |
1227 | selcx, | |
1228 | obligation.param_env, | |
1229 | obligation.cause.clone(), | |
1230 | obligation.recursion_depth + 1, | |
fc512014 | 1231 | gen_sig, |
ba9703b0 XL |
1232 | ); |
1233 | ||
29967ef6 | 1234 | debug!(?obligation, ?gen_sig, ?obligations, "confirm_generator_candidate"); |
ba9703b0 XL |
1235 | |
1236 | let tcx = selcx.tcx(); | |
1237 | ||
3dfed10e | 1238 | let gen_def_id = tcx.require_lang_item(LangItem::Generator, None); |
ba9703b0 XL |
1239 | |
1240 | let predicate = super::util::generator_trait_ref_and_outputs( | |
1241 | tcx, | |
1242 | gen_def_id, | |
1243 | obligation.predicate.self_ty(), | |
1244 | gen_sig, | |
1245 | ) | |
1246 | .map_bound(|(trait_ref, yield_ty, return_ty)| { | |
1247 | let name = tcx.associated_item(obligation.predicate.item_def_id).ident.name; | |
1248 | let ty = if name == sym::Return { | |
1249 | return_ty | |
1250 | } else if name == sym::Yield { | |
1251 | yield_ty | |
1252 | } else { | |
1253 | bug!() | |
1254 | }; | |
1255 | ||
1256 | ty::ProjectionPredicate { | |
1257 | projection_ty: ty::ProjectionTy { | |
1258 | substs: trait_ref.substs, | |
1259 | item_def_id: obligation.predicate.item_def_id, | |
1260 | }, | |
1261 | ty, | |
1262 | } | |
1263 | }); | |
1264 | ||
29967ef6 | 1265 | confirm_param_env_candidate(selcx, obligation, predicate, false) |
f035d41b | 1266 | .with_addl_obligations(impl_source.nested) |
ba9703b0 XL |
1267 | .with_addl_obligations(obligations) |
1268 | } | |
1269 | ||
f9f354fc XL |
1270 | fn confirm_discriminant_kind_candidate<'cx, 'tcx>( |
1271 | selcx: &mut SelectionContext<'cx, 'tcx>, | |
1272 | obligation: &ProjectionTyObligation<'tcx>, | |
f035d41b | 1273 | _: ImplSourceDiscriminantKindData, |
f9f354fc XL |
1274 | ) -> Progress<'tcx> { |
1275 | let tcx = selcx.tcx(); | |
1276 | ||
1277 | let self_ty = selcx.infcx().shallow_resolve(obligation.predicate.self_ty()); | |
1278 | let substs = tcx.mk_substs([self_ty.into()].iter()); | |
1279 | ||
3dfed10e | 1280 | let discriminant_def_id = tcx.require_lang_item(LangItem::Discriminant, None); |
f9f354fc XL |
1281 | |
1282 | let predicate = ty::ProjectionPredicate { | |
1283 | projection_ty: ty::ProjectionTy { substs, item_def_id: discriminant_def_id }, | |
3dfed10e | 1284 | ty: self_ty.discriminant_ty(tcx), |
f9f354fc XL |
1285 | }; |
1286 | ||
fc512014 XL |
1287 | // We get here from `poly_project_and_unify_type` which replaces bound vars |
1288 | // with placeholders, so dummy is okay here. | |
1289 | confirm_param_env_candidate(selcx, obligation, ty::Binder::dummy(predicate), false) | |
f9f354fc XL |
1290 | } |
1291 | ||
6a06907d XL |
1292 | fn confirm_pointee_candidate<'cx, 'tcx>( |
1293 | selcx: &mut SelectionContext<'cx, 'tcx>, | |
1294 | obligation: &ProjectionTyObligation<'tcx>, | |
1295 | _: ImplSourcePointeeData, | |
1296 | ) -> Progress<'tcx> { | |
1297 | let tcx = selcx.tcx(); | |
1298 | ||
1299 | let self_ty = selcx.infcx().shallow_resolve(obligation.predicate.self_ty()); | |
1300 | let substs = tcx.mk_substs([self_ty.into()].iter()); | |
1301 | ||
1302 | let metadata_def_id = tcx.require_lang_item(LangItem::Metadata, None); | |
1303 | ||
1304 | let predicate = ty::ProjectionPredicate { | |
1305 | projection_ty: ty::ProjectionTy { substs, item_def_id: metadata_def_id }, | |
1306 | ty: self_ty.ptr_metadata_ty(tcx), | |
1307 | }; | |
1308 | ||
1309 | confirm_param_env_candidate(selcx, obligation, ty::Binder::bind(predicate), false) | |
1310 | } | |
1311 | ||
ba9703b0 XL |
1312 | fn confirm_fn_pointer_candidate<'cx, 'tcx>( |
1313 | selcx: &mut SelectionContext<'cx, 'tcx>, | |
1314 | obligation: &ProjectionTyObligation<'tcx>, | |
f035d41b | 1315 | fn_pointer_impl_source: ImplSourceFnPointerData<'tcx, PredicateObligation<'tcx>>, |
ba9703b0 | 1316 | ) -> Progress<'tcx> { |
f035d41b | 1317 | let fn_type = selcx.infcx().shallow_resolve(fn_pointer_impl_source.fn_ty); |
ba9703b0 XL |
1318 | let sig = fn_type.fn_sig(selcx.tcx()); |
1319 | let Normalized { value: sig, obligations } = normalize_with_depth( | |
1320 | selcx, | |
1321 | obligation.param_env, | |
1322 | obligation.cause.clone(), | |
1323 | obligation.recursion_depth + 1, | |
fc512014 | 1324 | sig, |
ba9703b0 XL |
1325 | ); |
1326 | ||
1327 | confirm_callable_candidate(selcx, obligation, sig, util::TupleArgumentsFlag::Yes) | |
f035d41b | 1328 | .with_addl_obligations(fn_pointer_impl_source.nested) |
ba9703b0 XL |
1329 | .with_addl_obligations(obligations) |
1330 | } | |
1331 | ||
1332 | fn confirm_closure_candidate<'cx, 'tcx>( | |
1333 | selcx: &mut SelectionContext<'cx, 'tcx>, | |
1334 | obligation: &ProjectionTyObligation<'tcx>, | |
f035d41b | 1335 | impl_source: ImplSourceClosureData<'tcx, PredicateObligation<'tcx>>, |
ba9703b0 | 1336 | ) -> Progress<'tcx> { |
f035d41b | 1337 | let closure_sig = impl_source.substs.as_closure().sig(); |
ba9703b0 XL |
1338 | let Normalized { value: closure_sig, obligations } = normalize_with_depth( |
1339 | selcx, | |
1340 | obligation.param_env, | |
1341 | obligation.cause.clone(), | |
1342 | obligation.recursion_depth + 1, | |
fc512014 | 1343 | closure_sig, |
ba9703b0 XL |
1344 | ); |
1345 | ||
29967ef6 | 1346 | debug!(?obligation, ?closure_sig, ?obligations, "confirm_closure_candidate"); |
ba9703b0 XL |
1347 | |
1348 | confirm_callable_candidate(selcx, obligation, closure_sig, util::TupleArgumentsFlag::No) | |
f035d41b | 1349 | .with_addl_obligations(impl_source.nested) |
ba9703b0 XL |
1350 | .with_addl_obligations(obligations) |
1351 | } | |
1352 | ||
1353 | fn confirm_callable_candidate<'cx, 'tcx>( | |
1354 | selcx: &mut SelectionContext<'cx, 'tcx>, | |
1355 | obligation: &ProjectionTyObligation<'tcx>, | |
1356 | fn_sig: ty::PolyFnSig<'tcx>, | |
1357 | flag: util::TupleArgumentsFlag, | |
1358 | ) -> Progress<'tcx> { | |
1359 | let tcx = selcx.tcx(); | |
1360 | ||
29967ef6 | 1361 | debug!(?obligation, ?fn_sig, "confirm_callable_candidate"); |
ba9703b0 | 1362 | |
3dfed10e XL |
1363 | let fn_once_def_id = tcx.require_lang_item(LangItem::FnOnce, None); |
1364 | let fn_once_output_def_id = tcx.require_lang_item(LangItem::FnOnceOutput, None); | |
ba9703b0 XL |
1365 | |
1366 | let predicate = super::util::closure_trait_ref_and_return_type( | |
1367 | tcx, | |
1368 | fn_once_def_id, | |
1369 | obligation.predicate.self_ty(), | |
1370 | fn_sig, | |
1371 | flag, | |
1372 | ) | |
1373 | .map_bound(|(trait_ref, ret_type)| ty::ProjectionPredicate { | |
f035d41b XL |
1374 | projection_ty: ty::ProjectionTy { |
1375 | substs: trait_ref.substs, | |
1376 | item_def_id: fn_once_output_def_id, | |
1377 | }, | |
ba9703b0 XL |
1378 | ty: ret_type, |
1379 | }); | |
1380 | ||
29967ef6 | 1381 | confirm_param_env_candidate(selcx, obligation, predicate, false) |
ba9703b0 XL |
1382 | } |
1383 | ||
1384 | fn confirm_param_env_candidate<'cx, 'tcx>( | |
1385 | selcx: &mut SelectionContext<'cx, 'tcx>, | |
1386 | obligation: &ProjectionTyObligation<'tcx>, | |
1387 | poly_cache_entry: ty::PolyProjectionPredicate<'tcx>, | |
29967ef6 | 1388 | potentially_unnormalized_candidate: bool, |
ba9703b0 XL |
1389 | ) -> Progress<'tcx> { |
1390 | let infcx = selcx.infcx(); | |
1391 | let cause = &obligation.cause; | |
1392 | let param_env = obligation.param_env; | |
1393 | ||
1394 | let (cache_entry, _) = infcx.replace_bound_vars_with_fresh_vars( | |
1395 | cause.span, | |
1396 | LateBoundRegionConversionTime::HigherRankedType, | |
fc512014 | 1397 | poly_cache_entry, |
ba9703b0 XL |
1398 | ); |
1399 | ||
6a06907d XL |
1400 | let cache_projection = cache_entry.projection_ty; |
1401 | let obligation_projection = obligation.predicate; | |
29967ef6 | 1402 | let mut nested_obligations = Vec::new(); |
6a06907d | 1403 | let cache_projection = if potentially_unnormalized_candidate { |
29967ef6 XL |
1404 | ensure_sufficient_stack(|| { |
1405 | normalize_with_depth_to( | |
1406 | selcx, | |
1407 | obligation.param_env, | |
1408 | obligation.cause.clone(), | |
1409 | obligation.recursion_depth + 1, | |
6a06907d | 1410 | cache_projection, |
29967ef6 XL |
1411 | &mut nested_obligations, |
1412 | ) | |
1413 | }) | |
1414 | } else { | |
6a06907d | 1415 | cache_projection |
29967ef6 XL |
1416 | }; |
1417 | ||
6a06907d | 1418 | match infcx.at(cause, param_env).eq(cache_projection, obligation_projection) { |
29967ef6 XL |
1419 | Ok(InferOk { value: _, obligations }) => { |
1420 | nested_obligations.extend(obligations); | |
1421 | assoc_ty_own_obligations(selcx, obligation, &mut nested_obligations); | |
1422 | Progress { ty: cache_entry.ty, obligations: nested_obligations } | |
1423 | } | |
ba9703b0 XL |
1424 | Err(e) => { |
1425 | let msg = format!( | |
1426 | "Failed to unify obligation `{:?}` with poly_projection `{:?}`: {:?}", | |
1427 | obligation, poly_cache_entry, e, | |
1428 | ); | |
1429 | debug!("confirm_param_env_candidate: {}", msg); | |
f035d41b XL |
1430 | let err = infcx.tcx.ty_error_with_message(obligation.cause.span, &msg); |
1431 | Progress { ty: err, obligations: vec![] } | |
ba9703b0 XL |
1432 | } |
1433 | } | |
1434 | } | |
1435 | ||
1436 | fn confirm_impl_candidate<'cx, 'tcx>( | |
1437 | selcx: &mut SelectionContext<'cx, 'tcx>, | |
1438 | obligation: &ProjectionTyObligation<'tcx>, | |
f035d41b | 1439 | impl_impl_source: ImplSourceUserDefinedData<'tcx, PredicateObligation<'tcx>>, |
ba9703b0 XL |
1440 | ) -> Progress<'tcx> { |
1441 | let tcx = selcx.tcx(); | |
1442 | ||
29967ef6 | 1443 | let ImplSourceUserDefinedData { impl_def_id, substs, mut nested } = impl_impl_source; |
ba9703b0 XL |
1444 | let assoc_item_id = obligation.predicate.item_def_id; |
1445 | let trait_def_id = tcx.trait_id_of_impl(impl_def_id).unwrap(); | |
1446 | ||
1447 | let param_env = obligation.param_env; | |
1448 | let assoc_ty = match assoc_ty_def(selcx, impl_def_id, assoc_item_id) { | |
1449 | Ok(assoc_ty) => assoc_ty, | |
f035d41b | 1450 | Err(ErrorReported) => return Progress { ty: tcx.ty_error(), obligations: nested }, |
ba9703b0 XL |
1451 | }; |
1452 | ||
1453 | if !assoc_ty.item.defaultness.has_value() { | |
1454 | // This means that the impl is missing a definition for the | |
1455 | // associated type. This error will be reported by the type | |
1456 | // checker method `check_impl_items_against_trait`, so here we | |
1457 | // just return Error. | |
1458 | debug!( | |
1459 | "confirm_impl_candidate: no associated type {:?} for {:?}", | |
1460 | assoc_ty.item.ident, obligation.predicate | |
1461 | ); | |
f035d41b | 1462 | return Progress { ty: tcx.ty_error(), obligations: nested }; |
ba9703b0 | 1463 | } |
f035d41b XL |
1464 | // If we're trying to normalize `<Vec<u32> as X>::A<S>` using |
1465 | //`impl<T> X for Vec<T> { type A<Y> = Box<Y>; }`, then: | |
1466 | // | |
1467 | // * `obligation.predicate.substs` is `[Vec<u32>, S]` | |
1468 | // * `substs` is `[u32]` | |
1469 | // * `substs` ends up as `[u32, S]` | |
ba9703b0 XL |
1470 | let substs = obligation.predicate.substs.rebase_onto(tcx, trait_def_id, substs); |
1471 | let substs = | |
1472 | translate_substs(selcx.infcx(), param_env, impl_def_id, substs, assoc_ty.defining_node); | |
f035d41b | 1473 | let ty = tcx.type_of(assoc_ty.item.def_id); |
ba9703b0 | 1474 | if substs.len() != tcx.generics_of(assoc_ty.item.def_id).count() { |
f035d41b | 1475 | let err = tcx.ty_error_with_message( |
29967ef6 | 1476 | obligation.cause.span, |
f035d41b XL |
1477 | "impl item and trait item have different parameter counts", |
1478 | ); | |
1479 | Progress { ty: err, obligations: nested } | |
ba9703b0 | 1480 | } else { |
29967ef6 | 1481 | assoc_ty_own_obligations(selcx, obligation, &mut nested); |
ba9703b0 XL |
1482 | Progress { ty: ty.subst(tcx, substs), obligations: nested } |
1483 | } | |
1484 | } | |
1485 | ||
29967ef6 XL |
1486 | // Get obligations corresponding to the predicates from the where-clause of the |
1487 | // associated type itself. | |
1488 | // Note: `feature(generic_associated_types)` is required to write such | |
1489 | // predicates, even for non-generic associcated types. | |
1490 | fn assoc_ty_own_obligations<'cx, 'tcx>( | |
1491 | selcx: &mut SelectionContext<'cx, 'tcx>, | |
1492 | obligation: &ProjectionTyObligation<'tcx>, | |
1493 | nested: &mut Vec<PredicateObligation<'tcx>>, | |
1494 | ) { | |
1495 | let tcx = selcx.tcx(); | |
1496 | for predicate in tcx | |
1497 | .predicates_of(obligation.predicate.item_def_id) | |
1498 | .instantiate_own(tcx, obligation.predicate.substs) | |
1499 | .predicates | |
1500 | { | |
1501 | let normalized = normalize_with_depth_to( | |
1502 | selcx, | |
1503 | obligation.param_env, | |
1504 | obligation.cause.clone(), | |
1505 | obligation.recursion_depth + 1, | |
fc512014 | 1506 | predicate, |
29967ef6 XL |
1507 | nested, |
1508 | ); | |
1509 | nested.push(Obligation::with_depth( | |
1510 | obligation.cause.clone(), | |
1511 | obligation.recursion_depth + 1, | |
1512 | obligation.param_env, | |
1513 | normalized, | |
1514 | )); | |
1515 | } | |
1516 | } | |
1517 | ||
ba9703b0 XL |
1518 | /// Locate the definition of an associated type in the specialization hierarchy, |
1519 | /// starting from the given impl. | |
1520 | /// | |
1521 | /// Based on the "projection mode", this lookup may in fact only examine the | |
1522 | /// topmost impl. See the comments for `Reveal` for more details. | |
1523 | fn assoc_ty_def( | |
1524 | selcx: &SelectionContext<'_, '_>, | |
1525 | impl_def_id: DefId, | |
1526 | assoc_ty_def_id: DefId, | |
1527 | ) -> Result<specialization_graph::LeafDef, ErrorReported> { | |
1528 | let tcx = selcx.tcx(); | |
1529 | let assoc_ty_name = tcx.associated_item(assoc_ty_def_id).ident; | |
1530 | let trait_def_id = tcx.impl_trait_ref(impl_def_id).unwrap().def_id; | |
1531 | let trait_def = tcx.trait_def(trait_def_id); | |
1532 | ||
1533 | // This function may be called while we are still building the | |
1534 | // specialization graph that is queried below (via TraitDef::ancestors()), | |
1535 | // so, in order to avoid unnecessary infinite recursion, we manually look | |
1536 | // for the associated item at the given impl. | |
1537 | // If there is no such item in that impl, this function will fail with a | |
1538 | // cycle error if the specialization graph is currently being built. | |
1539 | let impl_node = specialization_graph::Node::Impl(impl_def_id); | |
1540 | for item in impl_node.items(tcx) { | |
f035d41b | 1541 | if matches!(item.kind, ty::AssocKind::Type) |
ba9703b0 XL |
1542 | && tcx.hygienic_eq(item.ident, assoc_ty_name, trait_def_id) |
1543 | { | |
1544 | return Ok(specialization_graph::LeafDef { | |
1545 | item: *item, | |
1546 | defining_node: impl_node, | |
1547 | finalizing_node: if item.defaultness.is_default() { None } else { Some(impl_node) }, | |
1548 | }); | |
1549 | } | |
1550 | } | |
1551 | ||
1552 | let ancestors = trait_def.ancestors(tcx, impl_def_id)?; | |
1553 | if let Some(assoc_item) = ancestors.leaf_def(tcx, assoc_ty_name, ty::AssocKind::Type) { | |
1554 | Ok(assoc_item) | |
1555 | } else { | |
1556 | // This is saying that neither the trait nor | |
1557 | // the impl contain a definition for this | |
1558 | // associated type. Normally this situation | |
1559 | // could only arise through a compiler bug -- | |
1560 | // if the user wrote a bad item name, it | |
1561 | // should have failed in astconv. | |
1562 | bug!("No associated type `{}` for {}", assoc_ty_name, tcx.def_path_str(impl_def_id)) | |
1563 | } | |
1564 | } | |
1565 | ||
1566 | crate trait ProjectionCacheKeyExt<'tcx>: Sized { | |
1567 | fn from_poly_projection_predicate( | |
1568 | selcx: &mut SelectionContext<'cx, 'tcx>, | |
f9f354fc | 1569 | predicate: ty::PolyProjectionPredicate<'tcx>, |
ba9703b0 XL |
1570 | ) -> Option<Self>; |
1571 | } | |
1572 | ||
1573 | impl<'tcx> ProjectionCacheKeyExt<'tcx> for ProjectionCacheKey<'tcx> { | |
1574 | fn from_poly_projection_predicate( | |
1575 | selcx: &mut SelectionContext<'cx, 'tcx>, | |
f9f354fc | 1576 | predicate: ty::PolyProjectionPredicate<'tcx>, |
ba9703b0 XL |
1577 | ) -> Option<Self> { |
1578 | let infcx = selcx.infcx(); | |
1579 | // We don't do cross-snapshot caching of obligations with escaping regions, | |
1580 | // so there's no cache key to use | |
1581 | predicate.no_bound_vars().map(|predicate| { | |
1582 | ProjectionCacheKey::new( | |
1583 | // We don't attempt to match up with a specific type-variable state | |
1584 | // from a specific call to `opt_normalize_projection_type` - if | |
1585 | // there's no precise match, the original cache entry is "stranded" | |
1586 | // anyway. | |
fc512014 | 1587 | infcx.resolve_vars_if_possible(predicate.projection_ty), |
ba9703b0 XL |
1588 | ) |
1589 | }) | |
1590 | } | |
1591 | } |