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