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