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
::TyCtxtInferExt
;
9 use rustc_infer
::traits
::query
::OutlivesBound
;
10 use rustc_middle
::ty
::query
::Providers
;
11 use rustc_middle
::ty
::{self, Ty, TyCtxt, TypeVisitable}
;
12 use rustc_span
::source_map
::DUMMY_SP
;
13 use rustc_trait_selection
::infer
::InferCtxtBuilderExt
;
14 use rustc_trait_selection
::traits
::query
::{CanonicalTyGoal, Fallible, NoSolution}
;
15 use rustc_trait_selection
::traits
::wf
;
16 use rustc_trait_selection
::traits
::ObligationCtxt
;
17 use smallvec
::{smallvec, SmallVec}
;
19 pub(crate) fn provide(p
: &mut Providers
) {
20 *p
= Providers { implied_outlives_bounds, ..*p }
;
23 fn implied_outlives_bounds
<'tcx
>(
25 goal
: CanonicalTyGoal
<'tcx
>,
27 &'tcx Canonical
<'tcx
, canonical
::QueryResponse
<'tcx
, Vec
<OutlivesBound
<'tcx
>>>>,
30 tcx
.infer_ctxt().enter_canonical_trait_query(&goal
, |ocx
, key
| {
31 let (param_env
, ty
) = key
.into_parts();
32 compute_implied_outlives_bounds(ocx
, param_env
, ty
)
36 fn compute_implied_outlives_bounds
<'tcx
>(
37 ocx
: &ObligationCtxt
<'_
, 'tcx
>,
38 param_env
: ty
::ParamEnv
<'tcx
>,
40 ) -> Fallible
<Vec
<OutlivesBound
<'tcx
>>> {
41 let tcx
= ocx
.infcx
.tcx
;
43 // Sometimes when we ask what it takes for T: WF, we get back that
44 // U: WF is required; in that case, we push U onto this stack and
45 // process it next. Because the resulting predicates aren't always
46 // guaranteed to be a subset of the original type, so we need to store the
47 // WF args we've computed in a set.
48 let mut checked_wf_args
= rustc_data_structures
::fx
::FxHashSet
::default();
49 let mut wf_args
= vec
![ty
.into()];
51 let mut outlives_bounds
: Vec
<ty
::OutlivesPredicate
<ty
::GenericArg
<'tcx
>, ty
::Region
<'tcx
>>> =
54 while let Some(arg
) = wf_args
.pop() {
55 if !checked_wf_args
.insert(arg
) {
59 // Compute the obligations for `arg` to be well-formed. If `arg` is
60 // an unresolved inference variable, just substituted an empty set
61 // -- because the return type here is going to be things we *add*
62 // to the environment, it's always ok for this set to be smaller
63 // than the ultimate set. (Note: normally there won't be
64 // unresolved inference variables here anyway, but there might be
65 // during typeck under some circumstances.)
67 // FIXME(@lcnr): It's not really "always fine", having fewer implied
68 // bounds can be backward incompatible, e.g. #101951 was caused by
69 // us not dealing with inference vars in `TypeOutlives` predicates.
71 wf
::obligations(ocx
.infcx
, param_env
, hir
::CRATE_HIR_ID
, 0, arg
, DUMMY_SP
)
74 // While these predicates should all be implied by other parts of
75 // the program, they are still relevant as they may constrain
76 // inference variables, which is necessary to add the correct
77 // implied bounds in some cases, mostly when dealing with projections.
78 ocx
.register_obligations(
79 obligations
.iter().filter(|o
| o
.predicate
.has_non_region_infer()).cloned(),
82 // From the full set of obligations, just filter down to the
83 // region relationships.
84 outlives_bounds
.extend(obligations
.into_iter().filter_map(|obligation
| {
85 assert
!(!obligation
.has_escaping_bound_vars());
86 match obligation
.predicate
.kind().no_bound_vars() {
88 Some(pred
) => match pred
{
89 ty
::PredicateKind
::Clause(ty
::Clause
::Trait(..))
90 | ty
::PredicateKind
::Subtype(..)
91 | ty
::PredicateKind
::Coerce(..)
92 | ty
::PredicateKind
::Clause(ty
::Clause
::Projection(..))
93 | ty
::PredicateKind
::ClosureKind(..)
94 | ty
::PredicateKind
::ObjectSafe(..)
95 | ty
::PredicateKind
::ConstEvaluatable(..)
96 | ty
::PredicateKind
::ConstEquate(..)
97 | ty
::PredicateKind
::Ambiguous
98 | ty
::PredicateKind
::TypeWellFormedFromEnv(..) => None
,
99 ty
::PredicateKind
::WellFormed(arg
) => {
104 ty
::PredicateKind
::Clause(ty
::Clause
::RegionOutlives(
105 ty
::OutlivesPredicate(r_a
, r_b
),
106 )) => Some(ty
::OutlivesPredicate(r_a
.into(), r_b
)),
108 ty
::PredicateKind
::Clause(ty
::Clause
::TypeOutlives(ty
::OutlivesPredicate(
111 ))) => Some(ty
::OutlivesPredicate(ty_a
.into(), r_b
)),
117 // This call to `select_all_or_error` is necessary to constrain inference variables, which we
118 // use further down when computing the implied bounds.
119 match ocx
.select_all_or_error().as_slice() {
121 _
=> return Err(NoSolution
),
124 // We lazily compute the outlives components as
125 // `select_all_or_error` constrains inference variables.
126 let implied_bounds
= outlives_bounds
128 .flat_map(|ty
::OutlivesPredicate(a
, r_b
)| match a
.unpack() {
129 ty
::GenericArgKind
::Lifetime(r_a
) => vec
![OutlivesBound
::RegionSubRegion(r_b
, r_a
)],
130 ty
::GenericArgKind
::Type(ty_a
) => {
131 let ty_a
= ocx
.infcx
.resolve_vars_if_possible(ty_a
);
132 let mut components
= smallvec
![];
133 push_outlives_components(tcx
, ty_a
, &mut components
);
134 implied_bounds_from_components(r_b
, components
)
136 ty
::GenericArgKind
::Const(_
) => unreachable
!(),
143 /// When we have an implied bound that `T: 'a`, we can further break
144 /// this down to determine what relationships would have to hold for
145 /// `T: 'a` to hold. We get to assume that the caller has validated
146 /// those relationships.
147 fn implied_bounds_from_components
<'tcx
>(
148 sub_region
: ty
::Region
<'tcx
>,
149 sup_components
: SmallVec
<[Component
<'tcx
>; 4]>,
150 ) -> Vec
<OutlivesBound
<'tcx
>> {
153 .filter_map(|component
| {
155 Component
::Region(r
) => Some(OutlivesBound
::RegionSubRegion(sub_region
, r
)),
156 Component
::Param(p
) => Some(OutlivesBound
::RegionSubParam(sub_region
, p
)),
157 Component
::Alias(p
) => Some(OutlivesBound
::RegionSubAlias(sub_region
, p
)),
158 Component
::EscapingAlias(_
) =>
159 // If the projection has escaping regions, don't
160 // try to infer any implied bounds even for its
161 // free components. This is conservative, because
162 // the caller will still have to prove that those
163 // free components outlive `sub_region`. But the
164 // idea is that the WAY that the caller proves
165 // that may change in the future and we want to
166 // give ourselves room to get smarter here.
170 Component
::UnresolvedInferenceVariable(..) => None
,