1 //! Provider for the `implied_outlives_bounds` query.
2 //! Do not call this query directory. See
3 //! [`rustc_trait_selection::traits::query::type_op::implied_outlives_bounds`].
6 use rustc_infer
::infer
::canonical
::{self, Canonical}
;
7 use rustc_infer
::infer
::outlives
::components
::{push_outlives_components, Component}
;
8 use rustc_infer
::infer
::{InferCtxt, TyCtxtInferExt}
;
9 use rustc_infer
::traits
::query
::OutlivesBound
;
10 use rustc_infer
::traits
::TraitEngineExt
as _
;
11 use rustc_middle
::ty
::query
::Providers
;
12 use rustc_middle
::ty
::{self, Ty, TyCtxt, TypeVisitable}
;
13 use rustc_span
::source_map
::DUMMY_SP
;
14 use rustc_trait_selection
::infer
::InferCtxtBuilderExt
;
15 use rustc_trait_selection
::traits
::query
::{CanonicalTyGoal, Fallible, NoSolution}
;
16 use rustc_trait_selection
::traits
::wf
;
17 use rustc_trait_selection
::traits
::{TraitEngine, TraitEngineExt}
;
18 use smallvec
::{smallvec, SmallVec}
;
20 pub(crate) fn provide(p
: &mut Providers
) {
21 *p
= Providers { implied_outlives_bounds, ..*p }
;
24 fn implied_outlives_bounds
<'tcx
>(
26 goal
: CanonicalTyGoal
<'tcx
>,
28 &'tcx Canonical
<'tcx
, canonical
::QueryResponse
<'tcx
, Vec
<OutlivesBound
<'tcx
>>>>,
31 tcx
.infer_ctxt().enter_canonical_trait_query(&goal
, |infcx
, _fulfill_cx
, key
| {
32 let (param_env
, ty
) = key
.into_parts();
33 compute_implied_outlives_bounds(&infcx
, param_env
, ty
)
37 fn compute_implied_outlives_bounds
<'tcx
>(
38 infcx
: &InferCtxt
<'_
, 'tcx
>,
39 param_env
: ty
::ParamEnv
<'tcx
>,
41 ) -> Fallible
<Vec
<OutlivesBound
<'tcx
>>> {
44 // Sometimes when we ask what it takes for T: WF, we get back that
45 // U: WF is required; in that case, we push U onto this stack and
46 // process it next. Because the resulting predicates aren't always
47 // guaranteed to be a subset of the original type, so we need to store the
48 // WF args we've computed in a set.
49 let mut checked_wf_args
= rustc_data_structures
::fx
::FxHashSet
::default();
50 let mut wf_args
= vec
![ty
.into()];
52 let mut implied_bounds
= vec
![];
54 let mut fulfill_cx
= <dyn TraitEngine
<'tcx
>>::new(tcx
);
56 while let Some(arg
) = wf_args
.pop() {
57 if !checked_wf_args
.insert(arg
) {
61 // Compute the obligations for `arg` to be well-formed. If `arg` is
62 // an unresolved inference variable, just substituted an empty set
63 // -- because the return type here is going to be things we *add*
64 // to the environment, it's always ok for this set to be smaller
65 // than the ultimate set. (Note: normally there won't be
66 // unresolved inference variables here anyway, but there might be
67 // during typeck under some circumstances.)
68 let obligations
= wf
::obligations(infcx
, param_env
, hir
::CRATE_HIR_ID
, 0, arg
, DUMMY_SP
)
71 // N.B., all of these predicates *ought* to be easily proven
72 // true. In fact, their correctness is (mostly) implied by
73 // other parts of the program. However, in #42552, we had
74 // an annoying scenario where:
76 // - Some `T::Foo` gets normalized, resulting in a
77 // variable `_1` and a `T: Trait<Foo=_1>` constraint
78 // (not sure why it couldn't immediately get
79 // solved). This result of `_1` got cached.
80 // - These obligations were dropped on the floor here,
81 // rather than being registered.
82 // - Then later we would get a request to normalize
83 // `T::Foo` which would result in `_1` being used from
84 // the cache, but hence without the `T: Trait<Foo=_1>`
85 // constraint. As a result, `_1` never gets resolved,
86 // and we get an ICE (in dropck).
88 // Therefore, we register any predicates involving
89 // inference variables. We restrict ourselves to those
90 // involving inference variables both for efficiency and
91 // to avoids duplicate errors that otherwise show up.
92 fulfill_cx
.register_predicate_obligations(
94 obligations
.iter().filter(|o
| o
.predicate
.has_infer_types_or_consts()).cloned(),
97 // From the full set of obligations, just filter down to the
98 // region relationships.
99 implied_bounds
.extend(obligations
.into_iter().flat_map(|obligation
| {
100 assert
!(!obligation
.has_escaping_bound_vars());
101 match obligation
.predicate
.kind().no_bound_vars() {
103 Some(pred
) => match pred
{
104 ty
::PredicateKind
::Trait(..)
105 | ty
::PredicateKind
::Subtype(..)
106 | ty
::PredicateKind
::Coerce(..)
107 | ty
::PredicateKind
::Projection(..)
108 | ty
::PredicateKind
::ClosureKind(..)
109 | ty
::PredicateKind
::ObjectSafe(..)
110 | ty
::PredicateKind
::ConstEvaluatable(..)
111 | ty
::PredicateKind
::ConstEquate(..)
112 | ty
::PredicateKind
::TypeWellFormedFromEnv(..) => vec
![],
113 ty
::PredicateKind
::WellFormed(arg
) => {
118 ty
::PredicateKind
::RegionOutlives(ty
::OutlivesPredicate(r_a
, r_b
)) => {
119 vec
![OutlivesBound
::RegionSubRegion(r_b
, r_a
)]
122 ty
::PredicateKind
::TypeOutlives(ty
::OutlivesPredicate(ty_a
, r_b
)) => {
123 let ty_a
= infcx
.resolve_vars_if_possible(ty_a
);
124 let mut components
= smallvec
![];
125 push_outlives_components(tcx
, ty_a
, &mut components
);
126 implied_bounds_from_components(r_b
, components
)
133 // Ensure that those obligations that we had to solve
134 // get solved *here*.
135 match fulfill_cx
.select_all_or_error(infcx
).as_slice() {
136 [] => Ok(implied_bounds
),
137 _
=> Err(NoSolution
),
141 /// When we have an implied bound that `T: 'a`, we can further break
142 /// this down to determine what relationships would have to hold for
143 /// `T: 'a` to hold. We get to assume that the caller has validated
144 /// those relationships.
145 fn implied_bounds_from_components
<'tcx
>(
146 sub_region
: ty
::Region
<'tcx
>,
147 sup_components
: SmallVec
<[Component
<'tcx
>; 4]>,
148 ) -> Vec
<OutlivesBound
<'tcx
>> {
151 .filter_map(|component
| {
153 Component
::Region(r
) => Some(OutlivesBound
::RegionSubRegion(sub_region
, r
)),
154 Component
::Param(p
) => Some(OutlivesBound
::RegionSubParam(sub_region
, p
)),
155 Component
::Projection(p
) => Some(OutlivesBound
::RegionSubProjection(sub_region
, p
)),
156 Component
::EscapingProjection(_
) =>
157 // If the projection has escaping regions, don't
158 // try to infer any implied bounds even for its
159 // free components. This is conservative, because
160 // the caller will still have to prove that those
161 // free components outlive `sub_region`. But the
162 // idea is that the WAY that the caller proves
163 // that may change in the future and we want to
164 // give ourselves room to get smarter here.
168 Component
::UnresolvedInferenceVariable(..) => None
,