rustc_trait_selection/traits/query/type_op/
implied_outlives_bounds.rs

1use std::ops::ControlFlow;
2
3use rustc_infer::infer::TypeOutlivesConstraint;
4use rustc_infer::infer::canonical::CanonicalQueryInput;
5use rustc_infer::traits::query::OutlivesBound;
6use rustc_infer::traits::query::type_op::ImpliedOutlivesBounds;
7use rustc_middle::infer::canonical::CanonicalQueryResponse;
8use rustc_middle::traits::ObligationCause;
9use rustc_middle::ty::outlives::{Component, push_outlives_components};
10use rustc_middle::ty::{self, ParamEnvAnd, Ty, TyCtxt, TypeVisitable, TypeVisitor, Unnormalized};
11use rustc_span::def_id::CRATE_DEF_ID;
12use rustc_span::{DUMMY_SP, Span, sym};
13use smallvec::{SmallVec, smallvec};
14
15use crate::traits::query::NoSolution;
16use crate::traits::{ObligationCtxt, wf};
17
18impl<'tcx> super::QueryTypeOp<'tcx> for ImpliedOutlivesBounds<'tcx> {
19    type QueryResponse = Vec<OutlivesBound<'tcx>>;
20
21    fn try_fast_path(
22        _tcx: TyCtxt<'tcx>,
23        key: &ParamEnvAnd<'tcx, Self>,
24    ) -> Option<Self::QueryResponse> {
25        // Don't go into the query for things that can't possibly have lifetimes.
26        match key.value.ty.kind() {
27            ty::Tuple(elems) if elems.is_empty() => Some(::alloc::vec::Vec::new()vec![]),
28            ty::Never | ty::Str | ty::Bool | ty::Char | ty::Int(_) | ty::Uint(_) | ty::Float(_) => {
29                Some(::alloc::vec::Vec::new()vec![])
30            }
31            _ => None,
32        }
33    }
34
35    fn perform_query(
36        tcx: TyCtxt<'tcx>,
37        canonicalized: CanonicalQueryInput<'tcx, ParamEnvAnd<'tcx, Self>>,
38    ) -> Result<CanonicalQueryResponse<'tcx, Self::QueryResponse>, NoSolution> {
39        tcx.implied_outlives_bounds((canonicalized, false))
40    }
41
42    fn perform_locally_with_next_solver(
43        ocx: &ObligationCtxt<'_, 'tcx>,
44        key: ParamEnvAnd<'tcx, Self>,
45        span: Span,
46    ) -> Result<Self::QueryResponse, NoSolution> {
47        compute_implied_outlives_bounds_inner(ocx, key.param_env, key.value.ty, span, false)
48    }
49}
50
51pub fn compute_implied_outlives_bounds_inner<'tcx>(
52    ocx: &ObligationCtxt<'_, 'tcx>,
53    param_env: ty::ParamEnv<'tcx>,
54    ty: Ty<'tcx>,
55    span: Span,
56    disable_implied_bounds_hack: bool,
57) -> Result<Vec<OutlivesBound<'tcx>>, NoSolution> {
58    // Inside mir borrowck, each computation starts with an empty list.
59    if !ocx.infcx.inner.borrow().region_obligations().is_empty() {
    {
        ::core::panicking::panic_fmt(format_args!("compute_implied_outlives_bounds assumes region obligations are empty before starting"));
    }
};assert!(
60        ocx.infcx.inner.borrow().region_obligations().is_empty(),
61        "compute_implied_outlives_bounds assumes region obligations are empty before starting"
62    );
63
64    // FIXME: This doesn't seem right. All call sites already normalize `ty`:
65    // - `Ty`s from the `DefiningTy` in Borrowck: we have to normalize in the caller
66    //      in order to get implied bounds involving any unconstrained region vars
67    //      created as part of normalizing the sig. See #136547
68    // - `Ty`s from impl headers in Borrowck and in Non-Borrowck contexts: we have
69    //      to normalize in the caller as computing implied bounds from unnormalized
70    //      types would be unsound. See #100989
71    //
72    // We must normalize the type so we can compute the right outlives components.
73    // for example, if we have some constrained param type like `T: Trait<Out = U>`,
74    // and we know that `&'a T::Out` is WF, then we want to imply `U: 'a`.
75    let normalized_ty = ocx
76        .deeply_normalize(
77            &ObligationCause::dummy_with_span(span),
78            param_env,
79            Unnormalized::new_wip(ty),
80        )
81        .map_err(|_| NoSolution)?;
82
83    // Sometimes when we ask what it takes for T: WF, we get back that
84    // U: WF is required; in that case, we push U onto this stack and
85    // process it next. Because the resulting predicates aren't always
86    // guaranteed to be a subset of the original type, so we need to store the
87    // WF args we've computed in a set.
88    let mut checked_wf_args = rustc_data_structures::fx::FxHashSet::default();
89    let mut wf_args = ::alloc::boxed::box_assume_init_into_vec_unsafe(::alloc::intrinsics::write_box_via_move(::alloc::boxed::Box::new_uninit(),
        [ty.into(), normalized_ty.into()]))vec![ty.into(), normalized_ty.into()];
90
91    let mut outlives_bounds: Vec<OutlivesBound<'tcx>> = ::alloc::vec::Vec::new()vec![];
92
93    while let Some(arg) = wf_args.pop() {
94        if !checked_wf_args.insert(arg) {
95            continue;
96        }
97
98        // From the full set of obligations, just filter down to the region relationships.
99        for obligation in
100            wf::unnormalized_obligations(ocx.infcx, param_env, arg, DUMMY_SP, CRATE_DEF_ID)
101                .into_iter()
102                .flatten()
103        {
104            let pred = ocx
105                .deeply_normalize(
106                    &ObligationCause::dummy_with_span(span),
107                    param_env,
108                    Unnormalized::new_wip(obligation.predicate),
109                )
110                .map_err(|_| NoSolution)?;
111            let Some(pred) = pred.kind().no_bound_vars() else {
112                continue;
113            };
114            match pred {
115                // FIXME(generic_const_parameter_types): Make sure that `<'a, 'b, const N: &'a &'b u32>`
116                // is sound if we ever support that
117                ty::PredicateKind::Clause(ty::ClauseKind::Trait(..))
118                | ty::PredicateKind::Clause(ty::ClauseKind::HostEffect(..))
119                | ty::PredicateKind::Clause(ty::ClauseKind::ConstArgHasType(..))
120                | ty::PredicateKind::Subtype(..)
121                | ty::PredicateKind::Coerce(..)
122                | ty::PredicateKind::Clause(ty::ClauseKind::Projection(..))
123                | ty::PredicateKind::DynCompatible(..)
124                | ty::PredicateKind::Clause(ty::ClauseKind::ConstEvaluatable(..))
125                | ty::PredicateKind::ConstEquate(..)
126                | ty::PredicateKind::Ambiguous
127                | ty::PredicateKind::NormalizesTo(..)
128                | ty::PredicateKind::Clause(ty::ClauseKind::UnstableFeature(_))
129                | ty::PredicateKind::AliasRelate(..) => {}
130
131                // We need to search through *all* WellFormed predicates
132                ty::PredicateKind::Clause(ty::ClauseKind::WellFormed(term)) => {
133                    wf_args.push(term);
134                }
135
136                // We need to register region relationships
137                ty::PredicateKind::Clause(ty::ClauseKind::RegionOutlives(
138                    ty::OutlivesPredicate(r_a, r_b),
139                )) => outlives_bounds.push(OutlivesBound::RegionSubRegion(r_b, r_a)),
140
141                ty::PredicateKind::Clause(ty::ClauseKind::TypeOutlives(ty::OutlivesPredicate(
142                    ty_a,
143                    r_b,
144                ))) => {
145                    let mut components = ::smallvec::SmallVec::new()smallvec![];
146                    push_outlives_components(ocx.infcx.tcx, ty_a, &mut components);
147                    outlives_bounds.extend(implied_bounds_from_components(r_b, components))
148                }
149            }
150        }
151    }
152
153    // If we detect `bevy_ecs::*::ParamSet` in the WF args list (and `disable_implied_bounds_hack`
154    // or `-Zno-implied-bounds-compat` are not set), then use the registered outlives obligations
155    // as implied bounds.
156    if !disable_implied_bounds_hack
157        && !ocx.infcx.tcx.sess.opts.unstable_opts.no_implied_bounds_compat
158        && ty.visit_with(&mut ContainsBevyParamSet { tcx: ocx.infcx.tcx }).is_break()
159    {
160        for TypeOutlivesConstraint { sup_type, sub_region, .. } in
161            ocx.infcx.clone_registered_region_obligations()
162        {
163            let mut components = ::smallvec::SmallVec::new()smallvec![];
164            push_outlives_components(ocx.infcx.tcx, sup_type, &mut components);
165            outlives_bounds.extend(implied_bounds_from_components(sub_region, components));
166        }
167    }
168
169    Ok(outlives_bounds)
170}
171
172struct ContainsBevyParamSet<'tcx> {
173    tcx: TyCtxt<'tcx>,
174}
175
176impl<'tcx> TypeVisitor<TyCtxt<'tcx>> for ContainsBevyParamSet<'tcx> {
177    type Result = ControlFlow<()>;
178
179    fn visit_ty(&mut self, t: Ty<'tcx>) -> Self::Result {
180        // We only care to match `ParamSet<T>` or `&ParamSet<T>`.
181        match t.kind() {
182            ty::Adt(def, _) => {
183                if self.tcx.item_name(def.did()) == sym::ParamSet
184                    && self.tcx.crate_name(def.did().krate) == sym::bevy_ecs
185                {
186                    return ControlFlow::Break(());
187                }
188            }
189            ty::Ref(_, ty, _) => ty.visit_with(self)?,
190            _ => {}
191        }
192
193        ControlFlow::Continue(())
194    }
195}
196
197/// When we have an implied bound that `T: 'a`, we can further break
198/// this down to determine what relationships would have to hold for
199/// `T: 'a` to hold. We get to assume that the caller has validated
200/// those relationships.
201fn implied_bounds_from_components<'tcx>(
202    sub_region: ty::Region<'tcx>,
203    sup_components: SmallVec<[Component<TyCtxt<'tcx>>; 4]>,
204) -> Vec<OutlivesBound<'tcx>> {
205    sup_components
206        .into_iter()
207        .filter_map(|component| {
208            match component {
209                Component::Region(r) => Some(OutlivesBound::RegionSubRegion(sub_region, r)),
210                Component::Param(p) => Some(OutlivesBound::RegionSubParam(sub_region, p)),
211                Component::Alias(p) => Some(OutlivesBound::RegionSubAlias(sub_region, p)),
212                Component::Placeholder(_p) => {
213                    // FIXME(non_lifetime_binders): Placeholders don't currently
214                    // imply anything for outlives, though they could easily.
215                    None
216                }
217                Component::EscapingAlias(_) =>
218                // If the projection has escaping regions, don't
219                // try to infer any implied bounds even for its
220                // free components. This is conservative, because
221                // the caller will still have to prove that those
222                // free components outlive `sub_region`. But the
223                // idea is that the WAY that the caller proves
224                // that may change in the future and we want to
225                // give ourselves room to get smarter here.
226                {
227                    None
228                }
229                Component::UnresolvedInferenceVariable(..) => None,
230            }
231        })
232        .collect()
233}
rustc_trait_selection/traits/query/type_op/implied_outlives_bounds.rs

rustc_trait_selection/traits/query/type_op/
implied_outlives_bounds.rs
