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

rustc_trait_selection/traits/
implied_outlives_bounds.rs
