rustc_trait_selection/traits/
implied_outlives_bounds.rs

1use std::ops::ControlFlow;
2
3use rustc_infer::infer::TypeOutlivesConstraint;
4use rustc_infer::infer::canonical::{CanonicalQueryInput, CanonicalQueryResponse};
5use rustc_infer::traits::query::OutlivesBound;
6use rustc_infer::traits::query::type_op::ImpliedOutlivesBounds;
7use rustc_middle::traits::ObligationCause;
8use rustc_middle::ty::outlives::{Component, push_outlives_components};
9use rustc_middle::ty::{self, ParamEnvAnd, Ty, TyCtxt, TypeVisitable, TypeVisitor, Unnormalized};
10use rustc_span::def_id::CRATE_DEF_ID;
11use rustc_span::{DUMMY_SP, Span, sym};
12use smallvec::{SmallVec, smallvec};
13
14use crate::traits::query::NoSolution;
15use crate::traits::query::type_op::QueryTypeOp;
16use crate::traits::{ObligationCtxt, wf};
17
18// FIXME(#160491): Remove this once the new implied bounds impl is through FCP.
19impl<'tcx> QueryTypeOp<'tcx> for ImpliedOutlivesBounds<'tcx> {
20    type QueryResponse = Vec<OutlivesBound<'tcx>>;
21
22    fn try_fast_path(
23        _tcx: TyCtxt<'tcx>,
24        key: &ParamEnvAnd<'tcx, Self>,
25    ) -> Option<Self::QueryResponse> {
26        // Don't go into the query for things that can't possibly have lifetimes.
27        match key.value.ty.kind() {
28            ty::Tuple(elems) if elems.is_empty() => Some(::alloc::vec::Vec::new()vec![]),
29            ty::Never | ty::Str | ty::Bool | ty::Char | ty::Int(_) | ty::Uint(_) | ty::Float(_) => {
30                Some(::alloc::vec::Vec::new()vec![])
31            }
32            _ => None,
33        }
34    }
35
36    fn perform_query(
37        tcx: TyCtxt<'tcx>,
38        canonicalized: CanonicalQueryInput<'tcx, ParamEnvAnd<'tcx, Self>>,
39    ) -> Result<CanonicalQueryResponse<'tcx, Self::QueryResponse>, NoSolution> {
40        tcx.implied_outlives_bounds((canonicalized, false))
41    }
42
43    fn perform_locally_with_next_solver(
44        ocx: &ObligationCtxt<'_, 'tcx>,
45        key: ParamEnvAnd<'tcx, Self>,
46        _span: Span,
47    ) -> Result<Self::QueryResponse, NoSolution> {
48        query_compute_implied_outlives_bounds(ocx, key.param_env, key.value.ty, false)
49    }
50}
51
52pub fn compute_implied_outlives_bounds_inner<'tcx>(
53    ocx: &ObligationCtxt<'_, 'tcx>,
54    param_env: ty::ParamEnv<'tcx>,
55    ty: Ty<'tcx>,
56    normalized_ty: Ty<'tcx>,
57    span: Span,
58) -> Result<Vec<OutlivesBound<'tcx>>, NoSolution> {
59    let tcx = ocx.infcx.tcx;
60    // Sometimes when we ask what it takes for T: WF, we get back that
61    // U: WF is required; in that case, we push U onto this stack and
62    // process it next. Because the resulting predicates aren't always
63    // guaranteed to be a subset of the original type, so we need to store the
64    // WF args we've computed in a set.
65    let mut checked_wf_args = rustc_data_structures::fx::FxHashSet::default();
66    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()];
67
68    let mut outlives_bounds: Vec<OutlivesBound<'tcx>> = ::alloc::vec::Vec::new()vec![];
69
70    while let Some(arg) = wf_args.pop() {
71        if !checked_wf_args.insert(arg) {
72            continue;
73        }
74
75        let arg = ocx.infcx.resolve_vars_if_possible(arg);
76        // From the full set of obligations, just filter down to the region relationships.
77        for obligation in
78            wf::unnormalized_obligations(ocx.infcx, param_env, arg, DUMMY_SP, CRATE_DEF_ID)
79                .into_flat_iter()
80        {
81            let pred = ocx
82                .deeply_normalize(
83                    &ObligationCause::dummy_with_span(span),
84                    param_env,
85                    Unnormalized::new_wip(obligation.predicate),
86                )
87                .map_err(|_| NoSolution)?;
88            let Some(pred) = pred.kind().no_bound_vars() else {
89                continue;
90            };
91            match pred {
92                // FIXME(generic_const_parameter_types): Make sure that `<'a, 'b, const N: &'a &'b u32>`
93                // is sound if we ever support that
94                ty::PredicateKind::Clause(ty::ClauseKind::Trait(..))
95                | ty::PredicateKind::Clause(ty::ClauseKind::HostEffect(..))
96                | ty::PredicateKind::Clause(ty::ClauseKind::ConstArgHasType(..))
97                | ty::PredicateKind::Subtype(..)
98                | ty::PredicateKind::Coerce(..)
99                | ty::PredicateKind::Clause(ty::ClauseKind::Projection(..))
100                | ty::PredicateKind::DynCompatible(..)
101                | ty::PredicateKind::Clause(ty::ClauseKind::ConstEvaluatable(..))
102                | ty::PredicateKind::ConstEquate(..)
103                | ty::PredicateKind::Ambiguous
104                | ty::PredicateKind::NormalizesTo(..)
105                | ty::PredicateKind::Clause(ty::ClauseKind::UnstableFeature(_)) => {}
106
107                // We need to search through *all* WellFormed predicates
108                ty::PredicateKind::Clause(ty::ClauseKind::WellFormed(term)) => {
109                    wf_args.push(term);
110                }
111
112                // We need to register region relationships
113                ty::PredicateKind::Clause(ty::ClauseKind::RegionOutlives(ty::OutlivesClause(
114                    r_a,
115                    r_b,
116                ))) => outlives_bounds.push(OutlivesBound::RegionSubRegion(r_b, r_a)),
117
118                ty::PredicateKind::Clause(ty::ClauseKind::TypeOutlives(ty::OutlivesClause(
119                    ty_a,
120                    r_b,
121                ))) => {
122                    let mut components = ::smallvec::SmallVec::new()smallvec![];
123                    push_outlives_components(tcx, ty_a, &mut components);
124                    outlives_bounds.extend(implied_bounds_from_components(tcx, r_b, components))
125                }
126            }
127        }
128    }
129
130    Ok(outlives_bounds)
131}
132
133/// If we're at a callsite which should apply the bevy implied bounds hack and
134/// `-Zno-implied-bounds-compat` has not been set, then use the registered outlives
135/// obligations as implied bounds if we detect `bevy_ecs::*::ParamSet` in the arg.
136///
137/// cc #119956
138pub fn consider_implied_bounds_hack_for_ty<'tcx>(
139    ocx: &ObligationCtxt<'_, 'tcx>,
140    ty: Ty<'tcx>,
141    region_constraints: impl FnOnce() -> Vec<TypeOutlivesConstraint<'tcx>>,
142) -> Vec<OutlivesBound<'tcx>> {
143    let tcx = ocx.infcx.tcx;
144    if !ocx.infcx.tcx.sess.opts.unstable_opts.no_implied_bounds_compat
145        && ty.visit_with(&mut ContainsBevyParamSet { tcx }).is_break()
146    {
147        let mut outlives_bounds = ::alloc::vec::Vec::new()vec![];
148        for TypeOutlivesConstraint { sup_type, sub_region, .. } in region_constraints() {
149            let mut components = ::smallvec::SmallVec::new()smallvec![];
150            push_outlives_components(tcx, sup_type, &mut components);
151            outlives_bounds.extend(implied_bounds_from_components(tcx, sub_region, components));
152        }
153        outlives_bounds
154    } else {
155        ::alloc::vec::Vec::new()vec![]
156    }
157}
158
159pub fn query_compute_implied_outlives_bounds<'tcx>(
160    ocx: &ObligationCtxt<'_, 'tcx>,
161    param_env: ty::ParamEnv<'tcx>,
162    ty: Ty<'tcx>,
163    disable_implied_bounds_hack: bool,
164) -> Result<Vec<OutlivesBound<'tcx>>, NoSolution> {
165    // When computing implied bounds by looking at types in the signature,
166    // we must be careful to never reveal the hidden types of opaques which
167    // the caller can not. That would be unsound as it may give us implied
168    // bounds which the caller never actually proves.
169    //
170    // FIXME(impl_trait_in_assoc_type): We currently do this incorrectly in
171    // `fn check_opaque_meets_bounds`, see trait-system-refactor-initiative#159.
172    /* if cfg!(debug_assertions) {
173        match ocx.infcx.typing_mode_raw() {
174            TypingMode::Typeck { defining_opaque_types_and_generators: opaque_types }
175            | TypingMode::PostTypeckUntilBorrowck { defining_opaque_types: opaque_types }
176            | TypingMode::PostBorrowck { defined_opaque_types: opaque_types } => {
177                assert!(opaque_types.is_empty())
178            }
179
180            TypingMode::Coherence
181            | TypingMode::Reflection
182            | TypingMode::PostAnalysis
183            | TypingMode::Codegen
184            | TypingMode::ErasedNotCoherence(_) => unreachable!(),
185        }
186    } */
187
188    // FIXME: This doesn't seem right. All call sites already normalize `ty`.
189    // We have to normalize in the caller as computing implied bounds from unnormalized
190    // types would be unsound. See #100989
191    //
192    // We must normalize the type so we can compute the right outlives components.
193    // for example, if we have some constrained param type like `T: Trait<Out = U>`,
194    // and we know that `&'a T::Out` is WF, then we want to imply `U: 'a`.
195    let normalized_ty = ocx
196        .deeply_normalize(&ObligationCause::dummy(), param_env, Unnormalized::new_wip(ty))
197        .map_err(|_| NoSolution)?;
198
199    let mut outlives_bounds =
200        compute_implied_outlives_bounds_inner(ocx, param_env, ty, normalized_ty, DUMMY_SP)?;
201
202    if !disable_implied_bounds_hack {
203        outlives_bounds.extend(consider_implied_bounds_hack_for_ty(ocx, ty, || {
204            ocx.infcx.clone_registered_region_obligations()
205        }));
206    }
207
208    Ok(outlives_bounds)
209}
210
211struct ContainsBevyParamSet<'tcx> {
212    tcx: TyCtxt<'tcx>,
213}
214
215impl<'tcx> TypeVisitor<TyCtxt<'tcx>> for ContainsBevyParamSet<'tcx> {
216    type Result = ControlFlow<()>;
217
218    fn visit_ty(&mut self, t: Ty<'tcx>) -> Self::Result {
219        // We only care to match `ParamSet<T>` or `&ParamSet<T>`.
220        match t.kind() {
221            ty::Adt(def, _) => {
222                if self.tcx.item_name(def.did()) == sym::ParamSet
223                    && self.tcx.crate_name(def.did().krate) == sym::bevy_ecs
224                {
225                    return ControlFlow::Break(());
226                }
227            }
228            ty::Ref(_, ty, _) => ty.visit_with(self)?,
229            _ => {}
230        }
231
232        ControlFlow::Continue(())
233    }
234}
235
236/// When we have an implied bound that `T: 'a`, we can further break
237/// this down to determine what relationships would have to hold for
238/// `T: 'a` to hold. We get to assume that the caller has validated
239/// those relationships.
240fn implied_bounds_from_components<'tcx>(
241    tcx: TyCtxt<'tcx>,
242    sub_region: ty::Region<'tcx>,
243    sup_components: SmallVec<[Component<TyCtxt<'tcx>>; 4]>,
244) -> Vec<OutlivesBound<'tcx>> {
245    sup_components
246        .into_iter()
247        .filter_map(|component| {
248            match component {
249                Component::Region(r) => Some(OutlivesBound::RegionSubRegion(sub_region, r)),
250                Component::Param(p) => Some(OutlivesBound::RegionSubParam(sub_region, p)),
251                Component::Alias(is_rigid, p) => {
252                    // We expect them to be already deeply normalized.
253                    if true {
    {
        match (&is_rigid, &ty::IsRigid::yes_if_next_solver(tcx)) {
            (left_val, right_val) => {
                if !(*left_val == *right_val) {
                    let kind = ::core::panicking::AssertKind::Eq;
                    ::core::panicking::assert_failed(kind, &*left_val,
                        &*right_val, ::core::option::Option::None);
                }
            }
        }
    };
};debug_assert_eq!(is_rigid, ty::IsRigid::yes_if_next_solver(tcx));
254                    Some(OutlivesBound::RegionSubAlias(sub_region, p))
255                }
256                Component::Placeholder(_p) => {
257                    // FIXME(non_lifetime_binders): Placeholders don't currently
258                    // imply anything for outlives, though they could easily.
259                    None
260                }
261                Component::EscapingAlias(_) =>
262                // If the projection has escaping regions, don't
263                // try to infer any implied bounds even for its
264                // free components. This is conservative, because
265                // the caller will still have to prove that those
266                // free components outlive `sub_region`. But the
267                // idea is that the WAY that the caller proves
268                // that may change in the future and we want to
269                // give ourselves room to get smarter here.
270                {
271                    None
272                }
273                Component::UnresolvedInferenceVariable(..) => None,
274            }
275        })
276        .collect()
277}
rustc_trait_selection/traits/implied_outlives_bounds.rs

rustc_trait_selection/traits/
implied_outlives_bounds.rs
