1 //! Code for projecting associated types out of trait references.
3 use super::elaborate_predicates
;
4 use super::specialization_graph
;
5 use super::translate_substs
;
7 use super::ObligationCause
;
8 use super::PredicateObligation
;
10 use super::SelectionContext
;
11 use super::SelectionError
;
12 use super::{VtableImplData, VtableClosureData, VtableGeneratorData, VtableFnPointerData}
;
15 use crate::hir
::def_id
::DefId
;
16 use crate::infer
::{InferCtxt, InferOk, LateBoundRegionConversionTime}
;
17 use crate::infer
::type_variable
::{TypeVariableOrigin, TypeVariableOriginKind}
;
18 use rustc_data_structures
::snapshot_map
::{Snapshot, SnapshotMap}
;
19 use rustc_macros
::HashStable
;
20 use syntax
::ast
::Ident
;
21 use syntax
::symbol
::sym
;
22 use crate::ty
::subst
::{Subst, InternalSubsts}
;
23 use crate::ty
::{self, ToPredicate, ToPolyTraitRef, Ty, TyCtxt}
;
24 use crate::ty
::fold
::{TypeFoldable, TypeFolder}
;
25 use crate::util
::common
::FN_OUTPUT_NAME
;
27 /// Depending on the stage of compilation, we want projection to be
28 /// more or less conservative.
29 #[derive(Debug, Copy, Clone, PartialEq, Eq, Hash, HashStable)]
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
46 /// impl<T> Assoc for T {
47 /// default type Output = bool;
51 /// let <() as Assoc>::Output = true;
55 /// At codegen time, all monomorphic projections will succeed.
56 /// Also, `impl Trait` is normalized to the concrete type,
57 /// which has to be already collected by type-checking.
59 /// NOTE: as `impl Trait`'s concrete type should *never*
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.
63 /// There are some exceptions, e.g., around OIBITS and
64 /// transmute-checking, which expose some details, but
65 /// not the whole concrete type of the `impl Trait`.
69 pub type PolyProjectionObligation
<'tcx
> =
70 Obligation
<'tcx
, ty
::PolyProjectionPredicate
<'tcx
>>;
72 pub type ProjectionObligation
<'tcx
> =
73 Obligation
<'tcx
, ty
::ProjectionPredicate
<'tcx
>>;
75 pub type ProjectionTyObligation
<'tcx
> =
76 Obligation
<'tcx
, ty
::ProjectionTy
<'tcx
>>;
78 /// When attempting to resolve `<T as TraitRef>::Name` ...
80 pub enum ProjectionTyError
<'tcx
> {
81 /// ...we found multiple sources of information and couldn't resolve the ambiguity.
84 /// ...an error occurred matching `T : TraitRef`
85 TraitSelectionError(SelectionError
<'tcx
>),
89 pub struct MismatchedProjectionTypes
<'tcx
> {
90 pub err
: ty
::error
::TypeError
<'tcx
>
93 #[derive(PartialEq, Eq, Debug)]
94 enum ProjectionTyCandidate
<'tcx
> {
95 // from a where-clause in the env or object type
96 ParamEnv(ty
::PolyProjectionPredicate
<'tcx
>),
98 // from the definition of `Trait` when you have something like <<A as Trait>::B as Trait2>::C
99 TraitDef(ty
::PolyProjectionPredicate
<'tcx
>),
101 // from a "impl" (or a "pseudo-impl" returned by select)
102 Select(Selection
<'tcx
>),
105 enum ProjectionTyCandidateSet
<'tcx
> {
107 Single(ProjectionTyCandidate
<'tcx
>),
109 Error(SelectionError
<'tcx
>),
112 impl<'tcx
> ProjectionTyCandidateSet
<'tcx
> {
113 fn mark_ambiguous(&mut self) {
114 *self = ProjectionTyCandidateSet
::Ambiguous
;
117 fn mark_error(&mut self, err
: SelectionError
<'tcx
>) {
118 *self = ProjectionTyCandidateSet
::Error(err
);
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
::*;
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.
136 let convert_to_ambiguous
;
140 *self = Single(candidate
);
145 // Duplicates can happen inside ParamEnv. In the case, we
146 // perform a lazy deduplication.
147 if current
== &candidate
{
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
) {
159 (ParamEnv(..), ParamEnv(..)) => convert_to_ambiguous
= (),
160 (ParamEnv(..), _
) => return false,
161 (_
, ParamEnv(..)) => unreachable
!(),
162 (_
, _
) => convert_to_ambiguous
= (),
166 Ambiguous
| Error(..) => {
171 // We only ever get here when we moved from a single candidate
173 let () = convert_to_ambiguous
;
179 /// Evaluates constraints of the form:
181 /// for<...> <T as Trait>::U == V
183 /// If successful, this may result in additional obligations. Also returns
184 /// the projection cache key used to track these additional obligations.
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
>> {
189 debug
!("poly_project_and_unify_type(obligation={:?})",
192 let infcx
= selcx
.infcx();
193 infcx
.commit_if_ok(|snapshot
| {
194 let (placeholder_predicate
, placeholder_map
) =
195 infcx
.replace_bound_vars_with_placeholders(&obligation
.predicate
);
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 }
)?
;
205 /// Evaluates constraints of the form:
207 /// <T as Trait>::U == V
209 /// If successful, this may result in additional obligations.
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
>> {
214 debug
!("project_and_unify_type(obligation={:?})",
217 let mut obligations
= vec
![];
219 match opt_normalize_projection_type(selcx
,
220 obligation
.param_env
,
221 obligation
.predicate
.projection_ty
,
222 obligation
.cause
.clone(),
223 obligation
.recursion_depth
,
226 None
=> return Ok(None
),
229 debug
!("project_and_unify_type: normalized_ty={:?} obligations={:?}",
233 let infcx
= selcx
.infcx();
234 match infcx
.at(&obligation
.cause
, obligation
.param_env
)
235 .eq(normalized_ty
, obligation
.predicate
.ty
) {
236 Ok(InferOk { obligations: inferred_obligations, value: () }
) => {
237 obligations
.extend(inferred_obligations
);
238 Ok(Some(obligations
))
241 debug
!("project_and_unify_type: equating types encountered error {:?}", err
);
242 Err(MismatchedProjectionTypes { err }
)
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.
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
>,
256 ) -> Normalized
<'tcx
, T
>
258 T
: TypeFoldable
<'tcx
>,
260 normalize_with_depth(selcx
, param_env
, cause
, 0, value
)
263 /// As `normalize`, but with a custom depth.
264 pub fn normalize_with_depth
<'a
, 'b
, 'tcx
, T
>(
265 selcx
: &'a
mut SelectionContext
<'b
, 'tcx
>,
266 param_env
: ty
::ParamEnv
<'tcx
>,
267 cause
: ObligationCause
<'tcx
>,
270 ) -> Normalized
<'tcx
, T
>
272 T
: TypeFoldable
<'tcx
>,
274 debug
!("normalize_with_depth(depth={}, value={:?})", depth
, value
);
275 let mut normalizer
= AssocTypeNormalizer
::new(selcx
, param_env
, cause
, depth
);
276 let result
= normalizer
.fold(value
);
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
);
283 obligations
: normalizer
.obligations
,
287 struct AssocTypeNormalizer
<'a
, 'b
, 'tcx
> {
288 selcx
: &'a
mut SelectionContext
<'b
, 'tcx
>,
289 param_env
: ty
::ParamEnv
<'tcx
>,
290 cause
: ObligationCause
<'tcx
>,
291 obligations
: Vec
<PredicateObligation
<'tcx
>>,
295 impl<'a
, 'b
, 'tcx
> AssocTypeNormalizer
<'a
, 'b
, 'tcx
> {
297 selcx
: &'a
mut SelectionContext
<'b
, 'tcx
>,
298 param_env
: ty
::ParamEnv
<'tcx
>,
299 cause
: ObligationCause
<'tcx
>,
301 ) -> AssocTypeNormalizer
<'a
, 'b
, 'tcx
> {
302 AssocTypeNormalizer
{
311 fn fold
<T
:TypeFoldable
<'tcx
>>(&mut self, value
: &T
) -> T
{
312 let value
= self.selcx
.infcx().resolve_vars_if_possible(value
);
314 if !value
.has_projections() {
317 value
.fold_with(self)
322 impl<'a
, 'b
, 'tcx
> TypeFolder
<'tcx
> for AssocTypeNormalizer
<'a
, 'b
, 'tcx
> {
323 fn tcx
<'c
>(&'c
self) -> TyCtxt
<'tcx
> {
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.
333 // for<'a> fn(<T as Foo<&'a>>::A)
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).
339 let ty
= ty
.super_fold_with(self);
341 ty
::Opaque(def_id
, substs
) if !substs
.has_escaping_bound_vars() => { // (*)
342 // Only normalize `impl Trait` after type-checking, usually in codegen.
343 match self.param_env
.reveal
{
344 Reveal
::UserFacing
=> ty
,
347 let recursion_limit
= *self.tcx().sess
.recursion_limit
.get();
348 if self.depth
>= recursion_limit
{
349 let obligation
= Obligation
::with_depth(
355 self.selcx
.infcx().report_overflow_error(&obligation
, true);
358 let generic_ty
= self.tcx().type_of(def_id
);
359 let concrete_ty
= generic_ty
.subst(self.tcx(), substs
);
361 let folded_ty
= self.fold_ty(concrete_ty
);
368 ty
::Projection(ref data
) if !data
.has_escaping_bound_vars() => { // (*)
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.
382 let normalized_ty
= normalize_projection_type(self.selcx
,
387 &mut self.obligations
);
388 debug
!("AssocTypeNormalizer: depth={} normalized {:?} to {:?}, \
389 now with {} obligations",
390 self.depth
, ty
, normalized_ty
, self.obligations
.len());
398 fn fold_const(&mut self, constant
: &'tcx ty
::Const
<'tcx
>) -> &'tcx ty
::Const
<'tcx
> {
399 constant
.eval(self.selcx
.tcx(), self.param_env
)
403 #[derive(Clone, TypeFoldable)]
404 pub struct Normalized
<'tcx
,T
> {
406 pub obligations
: Vec
<PredicateObligation
<'tcx
>>,
409 pub type NormalizedTy
<'tcx
> = Normalized
<'tcx
, Ty
<'tcx
>>;
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 }
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.
423 pub fn normalize_projection_type
<'a
, 'b
, 'tcx
>(
424 selcx
: &'a
mut SelectionContext
<'b
, 'tcx
>,
425 param_env
: ty
::ParamEnv
<'tcx
>,
426 projection_ty
: ty
::ProjectionTy
<'tcx
>,
427 cause
: ObligationCause
<'tcx
>,
429 obligations
: &mut Vec
<PredicateObligation
<'tcx
>>,
431 opt_normalize_projection_type(selcx
, param_env
, projection_ty
.clone(), cause
.clone(), depth
,
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.
438 let tcx
= selcx
.infcx().tcx
;
439 let def_id
= projection_ty
.item_def_id
;
440 let ty_var
= selcx
.infcx().next_ty_var(
442 kind
: TypeVariableOriginKind
::NormalizeProjectionType
,
443 span
: tcx
.def_span(def_id
),
446 let projection
= ty
::Binder
::dummy(ty
::ProjectionPredicate
{
450 let obligation
= Obligation
::with_depth(
451 cause
, depth
+ 1, param_env
, projection
.to_predicate());
452 obligations
.push(obligation
);
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.
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.
467 fn opt_normalize_projection_type
<'a
, 'b
, 'tcx
>(
468 selcx
: &'a
mut SelectionContext
<'b
, 'tcx
>,
469 param_env
: ty
::ParamEnv
<'tcx
>,
470 projection_ty
: ty
::ProjectionTy
<'tcx
>,
471 cause
: ObligationCause
<'tcx
>,
473 obligations
: &mut Vec
<PredicateObligation
<'tcx
>>,
474 ) -> Option
<Ty
<'tcx
>> {
475 let infcx
= selcx
.infcx();
477 let projection_ty
= infcx
.resolve_vars_if_possible(&projection_ty
);
478 let cache_key
= ProjectionCacheKey { ty: projection_ty }
;
480 debug
!("opt_normalize_projection_type(\
481 projection_ty={:?}, \
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.
494 let cache_result
= infcx
.projection_cache
.borrow_mut().try_start(cache_key
);
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.
505 // FIXME(#32286) refactor this so that closure type
507 debug
!("opt_normalize_projection_type: \
508 found cache entry: ambiguous");
509 if !projection_ty
.has_closure_types() {
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
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:
529 // let ty = selcx.tcx().mk_projection(projection_ty.item_def_id,
530 // projection_ty.substs;
531 // return Some(NormalizedTy { value: v, obligations: vec![] });
534 debug
!("opt_normalize_projection_type: \
535 found cache entry: in-progress");
537 // But for now, let's classify this as an overflow:
538 let recursion_limit
= *selcx
.tcx().sess
.recursion_limit
.get();
539 let obligation
= Obligation
::with_depth(cause
,
543 selcx
.infcx().report_overflow_error(&obligation
, false);
545 Err(ProjectionCacheEntry
::NormalizedTy(ty
)) => {
546 // This is the hottest path in this function.
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
556 // evaluations can causes ICEs (e.g., #43132).
557 debug
!("opt_normalize_projection_type: \
558 found normalized ty `{:?}`",
561 // Once we have inferred everything we need to know, we
562 // can ignore the `obligations` from that point on.
563 if infcx
.unresolved_type_vars(&ty
.value
).is_none() {
564 infcx
.projection_cache
.borrow_mut().complete_normalized(cache_key
, &ty
);
565 // No need to extend `obligations`.
567 obligations
.extend(ty
.obligations
);
570 obligations
.push(get_paranoid_cache_value_obligation(infcx
,
575 return Some(ty
.value
);
577 Err(ProjectionCacheEntry
::Error
) => {
578 debug
!("opt_normalize_projection_type: \
580 let result
= normalize_to_error(selcx
, param_env
, projection_ty
, cause
, depth
);
581 obligations
.extend(result
.obligations
);
582 return Some(result
.value
)
586 let obligation
= Obligation
::with_depth(cause
.clone(), depth
, param_env
, projection_ty
);
587 match project_type(selcx
, &obligation
) {
588 Ok(ProjectedTy
::Progress(Progress
{ ty
: projected_ty
,
589 obligations
: mut projected_obligations
})) => {
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
595 debug
!("opt_normalize_projection_type: \
598 projected_obligations={:?}",
601 projected_obligations
);
603 let result
= if projected_ty
.has_projections() {
604 let mut normalizer
= AssocTypeNormalizer
::new(selcx
,
608 let normalized_ty
= normalizer
.fold(&projected_ty
);
610 debug
!("opt_normalize_projection_type: \
611 normalized_ty={:?} depth={}",
615 projected_obligations
.extend(normalizer
.obligations
);
617 value
: normalized_ty
,
618 obligations
: projected_obligations
,
623 obligations
: projected_obligations
,
627 let cache_value
= prune_cache_value_obligations(infcx
, &result
);
628 infcx
.projection_cache
.borrow_mut().insert_ty(cache_key
, cache_value
);
629 obligations
.extend(result
.obligations
);
632 Ok(ProjectedTy
::NoProgress(projected_ty
)) => {
633 debug
!("opt_normalize_projection_type: \
634 projected_ty={:?} no progress",
636 let result
= Normalized
{
640 infcx
.projection_cache
.borrow_mut().insert_ty(cache_key
, result
.clone());
641 // No need to extend `obligations`.
644 Err(ProjectionTyError
::TooManyCandidates
) => {
645 debug
!("opt_normalize_projection_type: \
646 too many candidates");
647 infcx
.projection_cache
.borrow_mut()
648 .ambiguous(cache_key
);
651 Err(ProjectionTyError
::TraitSelectionError(_
)) => {
652 debug
!("opt_normalize_projection_type: ERROR");
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
658 infcx
.projection_cache
.borrow_mut()
660 let result
= normalize_to_error(selcx
, param_env
, projection_ty
, cause
, depth
);
661 obligations
.extend(result
.obligations
);
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.
670 fn prune_cache_value_obligations
<'a
, 'tcx
>(
671 infcx
: &'a InferCtxt
<'a
, 'tcx
>,
672 result
: &NormalizedTy
<'tcx
>,
673 ) -> NormalizedTy
<'tcx
> {
674 if infcx
.unresolved_type_vars(&result
.value
).is_none() {
675 return NormalizedTy { value: result.value, obligations: vec![] }
;
678 let mut obligations
: Vec
<_
> =
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 =
691 ty
::Predicate
::Projection(ref data
) =>
692 infcx
.unresolved_type_vars(&data
.ty()).is_some(),
694 // We are only interested in `T: Foo<X = U>` predicates, whre
695 // `U` references one of `unresolved_type_vars`. =)
701 obligations
.shrink_to_fit();
703 NormalizedTy { value: result.value, obligations }
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,
712 /// and so we take the precautionary measure of including `T: Trait` in
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
724 /// Concern #2. Even within the snapshot, if those original
725 /// obligations are not yet proven, then we are able to do projections
726 /// that may yet turn out to be wrong. This *may* lead to some sort
727 /// of trouble, though we don't have a concrete example of how that
728 /// can occur yet. But it seems risky at best.
729 fn get_paranoid_cache_value_obligation
<'a
, 'tcx
>(
730 infcx
: &'a InferCtxt
<'a
, 'tcx
>,
731 param_env
: ty
::ParamEnv
<'tcx
>,
732 projection_ty
: ty
::ProjectionTy
<'tcx
>,
733 cause
: ObligationCause
<'tcx
>,
735 ) -> PredicateObligation
<'tcx
> {
736 let trait_ref
= projection_ty
.trait_ref(infcx
.tcx
).to_poly_trait_ref();
739 recursion_depth
: depth
,
741 predicate
: trait_ref
.to_predicate(),
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
751 /// Note that we used to return `Error` here, but that was quite
752 /// dubious -- the premise was that an error would *eventually* be
753 /// reported, when the obligation was processed. But in general once
754 /// you see a `Error` you are supposed to be able to assume that an
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
760 /// `<MyType<[type error]> as Trait>::Foo`. We are supposed to report
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.)
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
>,
770 ) -> NormalizedTy
<'tcx
> {
771 let trait_ref
= projection_ty
.trait_ref(selcx
.tcx()).to_poly_trait_ref();
772 let trait_obligation
= Obligation
{ cause
,
773 recursion_depth
: depth
,
775 predicate
: trait_ref
.to_predicate() };
776 let tcx
= selcx
.infcx().tcx
;
777 let def_id
= projection_ty
.item_def_id
;
778 let new_value
= selcx
.infcx().next_ty_var(
780 kind
: TypeVariableOriginKind
::NormalizeProjectionType
,
781 span
: tcx
.def_span(def_id
),
786 obligations
: vec
![trait_obligation
]
790 enum ProjectedTy
<'tcx
> {
791 Progress(Progress
<'tcx
>),
792 NoProgress(Ty
<'tcx
>),
795 struct Progress
<'tcx
> {
797 obligations
: Vec
<PredicateObligation
<'tcx
>>,
800 impl<'tcx
> Progress
<'tcx
> {
801 fn error(tcx
: TyCtxt
<'tcx
>) -> Self {
808 fn with_addl_obligations(mut self,
809 mut obligations
: Vec
<PredicateObligation
<'tcx
>>)
811 debug
!("with_addl_obligations: self.obligations.len={} obligations.len={}",
812 self.obligations
.len(), obligations
.len());
814 debug
!("with_addl_obligations: self.obligations={:?} obligations={:?}",
815 self.obligations
, obligations
);
817 self.obligations
.append(&mut obligations
);
822 /// Computes the result of a projection type (if we can).
825 /// - `obligation` must be fully normalized
826 fn project_type
<'cx
, 'tcx
>(
827 selcx
: &mut SelectionContext
<'cx
, 'tcx
>,
828 obligation
: &ProjectionTyObligation
<'tcx
>,
829 ) -> Result
<ProjectedTy
<'tcx
>, ProjectionTyError
<'tcx
>> {
830 debug
!("project(obligation={:?})",
833 let recursion_limit
= *selcx
.tcx().sess
.recursion_limit
.get();
834 if obligation
.recursion_depth
>= recursion_limit
{
835 debug
!("project: overflow!");
836 return Err(ProjectionTyError
::TraitSelectionError(SelectionError
::Overflow
));
839 let obligation_trait_ref
= &obligation
.predicate
.trait_ref(selcx
.tcx());
841 debug
!("project: obligation_trait_ref={:?}", obligation_trait_ref
);
843 if obligation_trait_ref
.references_error() {
844 return Ok(ProjectedTy
::Progress(Progress
::error(selcx
.tcx())));
847 let mut candidates
= ProjectionTyCandidateSet
::None
;
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.
852 assemble_candidates_from_param_env(selcx
,
854 &obligation_trait_ref
,
857 assemble_candidates_from_trait_def(selcx
,
859 &obligation_trait_ref
,
862 assemble_candidates_from_impls(selcx
,
864 &obligation_trait_ref
,
868 ProjectionTyCandidateSet
::Single(candidate
) => Ok(ProjectedTy
::Progress(
869 confirm_candidate(selcx
,
871 &obligation_trait_ref
,
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
881 ProjectionTyCandidateSet
::Ambiguous
=> Err(ProjectionTyError
::TooManyCandidates
),
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.
889 fn assemble_candidates_from_param_env
<'cx
, 'tcx
>(
890 selcx
: &mut SelectionContext
<'cx
, 'tcx
>,
891 obligation
: &ProjectionTyObligation
<'tcx
>,
892 obligation_trait_ref
: &ty
::TraitRef
<'tcx
>,
893 candidate_set
: &mut ProjectionTyCandidateSet
<'tcx
>,
895 debug
!("assemble_candidates_from_param_env(..)");
896 assemble_candidates_from_predicates(selcx
,
898 obligation_trait_ref
,
900 ProjectionTyCandidate
::ParamEnv
,
901 obligation
.param_env
.caller_bounds
.iter().cloned());
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:
909 /// type FooT : Bar<BarT=i32>
913 /// Here, for example, we could conclude that the result is `i32`.
914 fn assemble_candidates_from_trait_def
<'cx
, 'tcx
>(
915 selcx
: &mut SelectionContext
<'cx
, 'tcx
>,
916 obligation
: &ProjectionTyObligation
<'tcx
>,
917 obligation_trait_ref
: &ty
::TraitRef
<'tcx
>,
918 candidate_set
: &mut ProjectionTyCandidateSet
<'tcx
>,
920 debug
!("assemble_candidates_from_trait_def(..)");
922 let tcx
= selcx
.tcx();
923 // Check whether the self-type is itself a projection.
924 let (def_id
, substs
) = match obligation_trait_ref
.self_ty().kind
{
925 ty
::Projection(ref data
) => {
926 (data
.trait_ref(tcx
).def_id
, data
.substs
)
928 ty
::Opaque(def_id
, substs
) => (def_id
, substs
),
929 ty
::Infer(ty
::TyVar(_
)) => {
930 // If the self-type is an inference variable, then it MAY wind up
931 // being a projected type, so induce an ambiguity.
932 candidate_set
.mark_ambiguous();
938 // If so, extract what we know from the trait and try to come up with a good answer.
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
);
942 assemble_candidates_from_predicates(selcx
,
944 obligation_trait_ref
,
946 ProjectionTyCandidate
::TraitDef
,
950 fn assemble_candidates_from_predicates
<'cx
, 'tcx
, I
>(
951 selcx
: &mut SelectionContext
<'cx
, 'tcx
>,
952 obligation
: &ProjectionTyObligation
<'tcx
>,
953 obligation_trait_ref
: &ty
::TraitRef
<'tcx
>,
954 candidate_set
: &mut ProjectionTyCandidateSet
<'tcx
>,
955 ctor
: fn(ty
::PolyProjectionPredicate
<'tcx
>) -> ProjectionTyCandidate
<'tcx
>,
958 I
: IntoIterator
<Item
= ty
::Predicate
<'tcx
>>,
960 debug
!("assemble_candidates_from_predicates(obligation={:?})",
962 let infcx
= selcx
.infcx();
963 for predicate
in env_predicates
{
964 debug
!("assemble_candidates_from_predicates: predicate={:?}",
966 if let ty
::Predicate
::Projection(data
) = predicate
{
967 let same_def_id
= data
.projection_def_id() == obligation
.predicate
.item_def_id
;
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.
983 debug
!("assemble_candidates_from_predicates: candidate={:?} \
984 is_match={} same_def_id={}",
985 data
, is_match
, same_def_id
);
988 candidate_set
.push_candidate(ctor(data
));
994 fn assemble_candidates_from_impls
<'cx
, 'tcx
>(
995 selcx
: &mut SelectionContext
<'cx
, 'tcx
>,
996 obligation
: &ProjectionTyObligation
<'tcx
>,
997 obligation_trait_ref
: &ty
::TraitRef
<'tcx
>,
998 candidate_set
: &mut ProjectionTyCandidateSet
<'tcx
>,
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());
1004 let _
= selcx
.infcx().commit_if_ok(|_
| {
1005 let vtable
= match selcx
.select(&trait_obligation
) {
1006 Ok(Some(vtable
)) => vtable
,
1008 candidate_set
.mark_ambiguous();
1012 debug
!("assemble_candidates_from_impls: selection error {:?}", e
);
1013 candidate_set
.mark_error(e
);
1018 let eligible
= match &vtable
{
1019 super::VtableClosure(_
) |
1020 super::VtableGenerator(_
) |
1021 super::VtableFnPointer(_
) |
1022 super::VtableObject(_
) |
1023 super::VtableTraitAlias(_
) => {
1024 debug
!("assemble_candidates_from_impls: vtable={:?}",
1028 super::VtableImpl(impl_data
) => {
1029 // We have to be careful when projecting out of an
1030 // impl because of specialization. If we are not in
1031 // codegen (i.e., projection mode is not "any"), and the
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.
1045 // In either case, we handle this by not adding a
1046 // candidate for an impl if it contains a `default`
1048 let node_item
= assoc_ty_def(selcx
,
1049 impl_data
.impl_def_id
,
1050 obligation
.predicate
.item_def_id
);
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:
1059 // trait Foo { type T; }
1060 // impl Foo for Bar { }
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`
1069 node_item
.item
.defaultness
.has_value()
1071 node_item
.item
.defaultness
.is_default() ||
1072 selcx
.tcx().impl_is_default(node_item
.node
.def_id())
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.
1081 } else if obligation
.param_env
.reveal
== Reveal
::All
{
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()
1090 super::VtableParam(..) => {
1091 // This case tell us nothing about the value of an
1092 // associated type. Consider:
1095 // trait SomeTrait { type Foo; }
1096 // fn foo<T:SomeTrait>(...) { }
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).
1104 // But wait, you say! What about an example like this:
1107 // fn bar<T:SomeTrait<Foo=usize>>(...) { ... }
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`.
1118 super::VtableAutoImpl(..) |
1119 super::VtableBuiltin(..) => {
1120 // These traits have no associated types.
1122 obligation
.cause
.span
,
1123 "Cannot project an associated type from `{:?}`",
1129 if candidate_set
.push_candidate(ProjectionTyCandidate
::Select(vtable
)) {
1140 fn confirm_candidate
<'cx
, 'tcx
>(
1141 selcx
: &mut SelectionContext
<'cx
, 'tcx
>,
1142 obligation
: &ProjectionTyObligation
<'tcx
>,
1143 obligation_trait_ref
: &ty
::TraitRef
<'tcx
>,
1144 candidate
: ProjectionTyCandidate
<'tcx
>,
1145 ) -> Progress
<'tcx
> {
1146 debug
!("confirm_candidate(candidate={:?}, obligation={:?})",
1151 ProjectionTyCandidate
::ParamEnv(poly_projection
) |
1152 ProjectionTyCandidate
::TraitDef(poly_projection
) => {
1153 confirm_param_env_candidate(selcx
, obligation
, poly_projection
)
1156 ProjectionTyCandidate
::Select(vtable
) => {
1157 confirm_select_candidate(selcx
, obligation
, obligation_trait_ref
, vtable
)
1162 fn confirm_select_candidate
<'cx
, 'tcx
>(
1163 selcx
: &mut SelectionContext
<'cx
, 'tcx
>,
1164 obligation
: &ProjectionTyObligation
<'tcx
>,
1165 obligation_trait_ref
: &ty
::TraitRef
<'tcx
>,
1166 vtable
: Selection
<'tcx
>,
1167 ) -> Progress
<'tcx
> {
1169 super::VtableImpl(data
) =>
1170 confirm_impl_candidate(selcx
, obligation
, data
),
1171 super::VtableGenerator(data
) =>
1172 confirm_generator_candidate(selcx
, obligation
, data
),
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
),
1179 super::VtableAutoImpl(..) |
1180 super::VtableParam(..) |
1181 super::VtableBuiltin(..) |
1182 super::VtableTraitAlias(..) =>
1183 // we don't create Select candidates with this kind of resolution
1185 obligation
.cause
.span
,
1186 "Cannot project an associated type from `{:?}`",
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
> {
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={:?})",
1200 let data
= match object_ty
.kind
{
1201 ty
::Dynamic(ref data
, ..) => data
,
1204 obligation
.cause
.span
,
1205 "confirm_object_candidate called with non-object: {:?}",
1209 let env_predicates
= data
.projection_bounds().map(|p
| {
1210 p
.with_self_ty(selcx
.tcx(), object_ty
).to_predicate()
1212 let env_predicate
= {
1213 let env_predicates
= elaborate_predicates(selcx
.tcx(), env_predicates
);
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
) =>
1219 if data
.projection_def_id() == obligation
.predicate
.item_def_id
{
1227 // select those with a relevant trait-ref
1228 let mut env_predicates
= env_predicates
.filter(|data
| {
1229 let data_poly_trait_ref
= data
.to_poly_trait_ref(selcx
.tcx());
1230 let obligation_poly_trait_ref
= obligation_trait_ref
.to_poly_trait_ref();
1231 selcx
.infcx().probe(|_
|
1232 selcx
.infcx().at(&obligation
.cause
, obligation
.param_env
)
1233 .sup(obligation_poly_trait_ref
, data_poly_trait_ref
)
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
,
1244 debug
!("confirm_object_candidate: no env-predicate \
1245 found in object type `{:?}`; ill-formed",
1247 return Progress
::error(selcx
.tcx());
1252 confirm_param_env_candidate(selcx
, obligation
, env_predicate
)
1255 fn confirm_generator_candidate
<'cx
, 'tcx
>(
1256 selcx
: &mut SelectionContext
<'cx
, 'tcx
>,
1257 obligation
: &ProjectionTyObligation
<'tcx
>,
1258 vtable
: VtableGeneratorData
<'tcx
, PredicateObligation
<'tcx
>>,
1259 ) -> Progress
<'tcx
> {
1260 let gen_sig
= vtable
.substs
.as_generator().poly_sig(vtable
.generator_def_id
, selcx
.tcx());
1264 } = normalize_with_depth(selcx
,
1265 obligation
.param_env
,
1266 obligation
.cause
.clone(),
1267 obligation
.recursion_depth
+1,
1270 debug
!("confirm_generator_candidate: obligation={:?},gen_sig={:?},obligations={:?}",
1275 let tcx
= selcx
.tcx();
1277 let gen_def_id
= tcx
.lang_items().gen_trait().unwrap();
1280 tcx
.generator_trait_ref_and_outputs(gen_def_id
,
1281 obligation
.predicate
.self_ty(),
1283 .map_bound(|(trait_ref
, yield_ty
, return_ty
)| {
1284 let name
= tcx
.associated_item(obligation
.predicate
.item_def_id
).ident
.name
;
1285 let ty
= if name
== sym
::Return
{
1287 } else if name
== sym
::Yield
{
1293 ty
::ProjectionPredicate
{
1294 projection_ty
: ty
::ProjectionTy
{
1295 substs
: trait_ref
.substs
,
1296 item_def_id
: obligation
.predicate
.item_def_id
,
1302 confirm_param_env_candidate(selcx
, obligation
, predicate
)
1303 .with_addl_obligations(vtable
.nested
)
1304 .with_addl_obligations(obligations
)
1307 fn confirm_fn_pointer_candidate
<'cx
, 'tcx
>(
1308 selcx
: &mut SelectionContext
<'cx
, 'tcx
>,
1309 obligation
: &ProjectionTyObligation
<'tcx
>,
1310 fn_pointer_vtable
: VtableFnPointerData
<'tcx
, PredicateObligation
<'tcx
>>,
1311 ) -> Progress
<'tcx
> {
1312 let fn_type
= selcx
.infcx().shallow_resolve(fn_pointer_vtable
.fn_ty
);
1313 let sig
= fn_type
.fn_sig(selcx
.tcx());
1317 } = normalize_with_depth(selcx
,
1318 obligation
.param_env
,
1319 obligation
.cause
.clone(),
1320 obligation
.recursion_depth
+1,
1323 confirm_callable_candidate(selcx
, obligation
, sig
, util
::TupleArgumentsFlag
::Yes
)
1324 .with_addl_obligations(fn_pointer_vtable
.nested
)
1325 .with_addl_obligations(obligations
)
1328 fn confirm_closure_candidate
<'cx
, 'tcx
>(
1329 selcx
: &mut SelectionContext
<'cx
, 'tcx
>,
1330 obligation
: &ProjectionTyObligation
<'tcx
>,
1331 vtable
: VtableClosureData
<'tcx
, PredicateObligation
<'tcx
>>,
1332 ) -> Progress
<'tcx
> {
1333 let tcx
= selcx
.tcx();
1334 let infcx
= selcx
.infcx();
1335 let closure_sig_ty
= vtable
.substs
1336 .as_closure().sig_ty(vtable
.closure_def_id
, tcx
);
1337 let closure_sig
= infcx
.shallow_resolve(closure_sig_ty
).fn_sig(tcx
);
1341 } = normalize_with_depth(selcx
,
1342 obligation
.param_env
,
1343 obligation
.cause
.clone(),
1344 obligation
.recursion_depth
+1,
1347 debug
!("confirm_closure_candidate: obligation={:?},closure_sig={:?},obligations={:?}",
1352 confirm_callable_candidate(selcx
,
1355 util
::TupleArgumentsFlag
::No
)
1356 .with_addl_obligations(vtable
.nested
)
1357 .with_addl_obligations(obligations
)
1360 fn confirm_callable_candidate
<'cx
, 'tcx
>(
1361 selcx
: &mut SelectionContext
<'cx
, 'tcx
>,
1362 obligation
: &ProjectionTyObligation
<'tcx
>,
1363 fn_sig
: ty
::PolyFnSig
<'tcx
>,
1364 flag
: util
::TupleArgumentsFlag
,
1365 ) -> Progress
<'tcx
> {
1366 let tcx
= selcx
.tcx();
1368 debug
!("confirm_callable_candidate({:?},{:?})",
1372 // the `Output` associated type is declared on `FnOnce`
1373 let fn_once_def_id
= tcx
.lang_items().fn_once_trait().unwrap();
1376 tcx
.closure_trait_ref_and_return_type(fn_once_def_id
,
1377 obligation
.predicate
.self_ty(),
1380 .map_bound(|(trait_ref
, ret_type
)|
1381 ty
::ProjectionPredicate
{
1382 projection_ty
: ty
::ProjectionTy
::from_ref_and_name(
1385 Ident
::with_dummy_span(FN_OUTPUT_NAME
),
1391 confirm_param_env_candidate(selcx
, obligation
, predicate
)
1394 fn confirm_param_env_candidate
<'cx
, 'tcx
>(
1395 selcx
: &mut SelectionContext
<'cx
, 'tcx
>,
1396 obligation
: &ProjectionTyObligation
<'tcx
>,
1397 poly_cache_entry
: ty
::PolyProjectionPredicate
<'tcx
>,
1398 ) -> Progress
<'tcx
> {
1399 let infcx
= selcx
.infcx();
1400 let cause
= &obligation
.cause
;
1401 let param_env
= obligation
.param_env
;
1403 let (cache_entry
, _
) =
1404 infcx
.replace_bound_vars_with_fresh_vars(
1406 LateBoundRegionConversionTime
::HigherRankedType
,
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 }
) => {
1420 "Failed to unify obligation `{:?}` with poly_projection `{:?}`: {:?}",
1425 debug
!("confirm_param_env_candidate: {}", msg
);
1426 infcx
.tcx
.sess
.delay_span_bug(obligation
.cause
.span
, &msg
);
1428 ty
: infcx
.tcx
.types
.err
,
1429 obligations
: vec
![],
1435 fn confirm_impl_candidate
<'cx
, 'tcx
>(
1436 selcx
: &mut SelectionContext
<'cx
, 'tcx
>,
1437 obligation
: &ProjectionTyObligation
<'tcx
>,
1438 impl_vtable
: VtableImplData
<'tcx
, PredicateObligation
<'tcx
>>,
1439 ) -> Progress
<'tcx
> {
1440 let VtableImplData { impl_def_id, substs, nested }
= impl_vtable
;
1442 let tcx
= selcx
.tcx();
1443 let param_env
= obligation
.param_env
;
1444 let assoc_ty
= assoc_ty_def(selcx
, impl_def_id
, obligation
.predicate
.item_def_id
);
1446 if !assoc_ty
.item
.defaultness
.has_value() {
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
1450 // just return Error.
1451 debug
!("confirm_impl_candidate: no associated type {:?} for {:?}",
1452 assoc_ty
.item
.ident
,
1453 obligation
.predicate
);
1456 obligations
: nested
,
1459 let substs
= translate_substs(selcx
.infcx(), param_env
, impl_def_id
, substs
, assoc_ty
.node
);
1460 let ty
= if let ty
::AssocKind
::OpaqueTy
= assoc_ty
.item
.kind
{
1461 let item_substs
= InternalSubsts
::identity_for_item(tcx
, assoc_ty
.item
.def_id
);
1462 tcx
.mk_opaque(assoc_ty
.item
.def_id
, item_substs
)
1464 tcx
.type_of(assoc_ty
.item
.def_id
)
1467 ty
: ty
.subst(tcx
, substs
),
1468 obligations
: nested
,
1472 /// Locate the definition of an associated type in the specialization hierarchy,
1473 /// starting from the given impl.
1475 /// Based on the "projection mode", this lookup may in fact only examine the
1476 /// topmost impl. See the comments for `Reveal` for more details.
1478 selcx
: &SelectionContext
<'_
, '_
>,
1480 assoc_ty_def_id
: DefId
,
1481 ) -> specialization_graph
::NodeItem
<ty
::AssocItem
> {
1482 let tcx
= selcx
.tcx();
1483 let assoc_ty_name
= tcx
.associated_item(assoc_ty_def_id
).ident
;
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
);
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
) {
1495 if item
.kind
== ty
::AssocKind
::Type
&&
1496 tcx
.hygienic_eq(item
.ident
, assoc_ty_name
, trait_def_id
) {
1497 return specialization_graph
::NodeItem
{
1498 node
: specialization_graph
::Node
::Impl(impl_def_id
),
1504 if let Some(assoc_item
) = trait_def
1505 .ancestors(tcx
, impl_def_id
)
1506 .leaf_def(tcx
, assoc_ty_name
, ty
::AssocKind
::Type
) {
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 {}",
1518 tcx
.def_path_str(impl_def_id
))
1524 /// The projection cache. Unlike the standard caches, this can include
1525 /// infcx-dependent type variables, therefore we have to roll the
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.
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).
1535 /// Entries in the projection cache might contain inference variables
1536 /// that will be resolved by obligations on the projection cache entry (e.g.,
1537 /// when a type parameter in the associated type is constrained through
1538 /// an "RFC 447" projection on the impl).
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,
1543 /// users that don't wait for a fixed point (e.g., trait evaluation) have to
1544 /// resolve the obligations themselves to make sure the projected result is
1545 /// ok and avoid issues like #43132.
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.
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.
1554 pub struct ProjectionCache
<'tcx
> {
1555 map
: SnapshotMap
<ProjectionCacheKey
<'tcx
>, ProjectionCacheEntry
<'tcx
>>,
1558 #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)]
1559 pub struct ProjectionCacheKey
<'tcx
> {
1560 ty
: ty
::ProjectionTy
<'tcx
>
1563 impl<'cx
, 'tcx
> ProjectionCacheKey
<'tcx
> {
1564 pub fn from_poly_projection_predicate(
1565 selcx
: &mut SelectionContext
<'cx
, 'tcx
>,
1566 predicate
: &ty
::PolyProjectionPredicate
<'tcx
>,
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
1571 predicate
.no_bound_vars()
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"
1577 ty
: infcx
.resolve_vars_if_possible(&predicate
.projection_ty
)
1582 #[derive(Clone, Debug)]
1583 enum ProjectionCacheEntry
<'tcx
> {
1587 NormalizedTy(NormalizedTy
<'tcx
>),
1590 // N.B., intentionally not Clone
1591 pub struct ProjectionCacheSnapshot
{
1595 impl<'tcx
> ProjectionCache
<'tcx
> {
1596 pub fn clear(&mut self) {
1600 pub fn snapshot(&mut self) -> ProjectionCacheSnapshot
{
1601 ProjectionCacheSnapshot { snapshot: self.map.snapshot() }
1604 pub fn rollback_to(&mut self, snapshot
: ProjectionCacheSnapshot
) {
1605 self.map
.rollback_to(snapshot
.snapshot
);
1608 pub fn rollback_placeholder(&mut self, snapshot
: &ProjectionCacheSnapshot
) {
1609 self.map
.partial_rollback(&snapshot
.snapshot
, &|k
| k
.ty
.has_re_placeholders());
1612 pub fn commit(&mut self, snapshot
: ProjectionCacheSnapshot
) {
1613 self.map
.commit(snapshot
.snapshot
);
1616 /// Try to start normalize `key`; returns an error if
1617 /// normalization already occurred (this error corresponds to a
1618 /// cache hit, so it's actually a good thing).
1619 fn try_start(&mut self, key
: ProjectionCacheKey
<'tcx
>)
1620 -> Result
<(), ProjectionCacheEntry
<'tcx
>> {
1621 if let Some(entry
) = self.map
.get(&key
) {
1622 return Err(entry
.clone());
1625 self.map
.insert(key
, ProjectionCacheEntry
::InProgress
);
1629 /// Indicates that `key` was normalized to `value`.
1630 fn insert_ty(&mut self, key
: ProjectionCacheKey
<'tcx
>, value
: NormalizedTy
<'tcx
>) {
1631 debug
!("ProjectionCacheEntry::insert_ty: adding cache entry: key={:?}, value={:?}",
1633 let fresh_key
= self.map
.insert(key
, ProjectionCacheEntry
::NormalizedTy(value
));
1634 assert
!(!fresh_key
, "never started projecting `{:?}`", key
);
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 {:?}",
1649 // Type inference could "strand behind" old cache entries. Leave
1650 // them alone for now.
1651 debug
!("ProjectionCacheEntry::complete({:?}) - ignoring {:?}",
1657 self.map
.insert(key
, ProjectionCacheEntry
::NormalizedTy(Normalized
{
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
1667 // already has no obligations (as is common) we don't insert anything.
1668 if !ty
.obligations
.is_empty() {
1669 self.map
.insert(key
, ProjectionCacheEntry
::NormalizedTy(Normalized
{
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
1680 fn ambiguous(&mut self, key
: ProjectionCacheKey
<'tcx
>) {
1681 let fresh
= self.map
.insert(key
, ProjectionCacheEntry
::Ambiguous
);
1682 assert
!(!fresh
, "never started projecting `{:?}`", key
);
1685 /// Indicates that trying to normalize `key` resulted in
1687 fn error(&mut self, key
: ProjectionCacheKey
<'tcx
>) {
1688 let fresh
= self.map
.insert(key
, ProjectionCacheEntry
::Error
);
1689 assert
!(!fresh
, "never started projecting `{:?}`", key
);