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