1use rustc_data_structures::fx::FxHashSet;
2use rustc_hir as hir;
3use rustc_hir::def::DefKind;
4use rustc_index::bit_set::DenseBitSet;
5use rustc_infer::infer::TyCtxtInferExt;
6use rustc_middle::bug;
7use rustc_middle::query::Providers;
8use rustc_middle::ty::{
9 self, SizedTraitKind, Ty, TyCtxt, TypeSuperVisitable, TypeVisitable, TypeVisitor, Upcast,
10 fold_regions,
11};
12use rustc_span::DUMMY_SP;
13use rustc_span::def_id::{CRATE_DEF_ID, DefId, LocalDefId};
14use rustc_trait_selection::traits;
15use tracing::instrument;
16
17#[instrument(level = "debug", skip(tcx), ret)]
20fn sizedness_constraint_for_ty<'tcx>(
21 tcx: TyCtxt<'tcx>,
22 sizedness: SizedTraitKind,
23 ty: Ty<'tcx>,
24) -> Option<Ty<'tcx>> {
25 match ty.kind() {
26 ty::Bool
28 | ty::Char
29 | ty::Int(..)
30 | ty::Uint(..)
31 | ty::Float(..)
32 | ty::RawPtr(..)
33 | ty::Ref(..)
34 | ty::FnDef(..)
35 | ty::FnPtr(..)
36 | ty::Array(..)
37 | ty::Closure(..)
38 | ty::CoroutineClosure(..)
39 | ty::Coroutine(..)
40 | ty::CoroutineWitness(..)
41 | ty::Never => None,
42
43 ty::Str | ty::Slice(..) | ty::Dynamic(_, _, ty::Dyn) => match sizedness {
44 SizedTraitKind::Sized => Some(ty),
46 SizedTraitKind::MetaSized => None,
48 },
49
50 ty::Param(..) | ty::Alias(..) | ty::Error(_) => Some(ty),
52
53 ty::UnsafeBinder(inner_ty) => {
57 sizedness_constraint_for_ty(tcx, sizedness, inner_ty.skip_binder()).map(|_| ty)
58 }
59
60 ty::Foreign(..) => Some(ty),
62
63 ty::Pat(ty, _) => sizedness_constraint_for_ty(tcx, sizedness, *ty),
65
66 ty::Tuple(tys) => {
67 tys.last().and_then(|&ty| sizedness_constraint_for_ty(tcx, sizedness, ty))
68 }
69
70 ty::Adt(adt, args) => adt.sizedness_constraint(tcx, sizedness).and_then(|intermediate| {
71 let ty = intermediate.instantiate(tcx, args);
72 sizedness_constraint_for_ty(tcx, sizedness, ty)
73 }),
74
75 ty::Placeholder(..) | ty::Bound(..) | ty::Infer(..) => {
76 bug!("unexpected type `{ty:?}` in `sizedness_constraint_for_ty`")
77 }
78 }
79}
80
81fn defaultness(tcx: TyCtxt<'_>, def_id: LocalDefId) -> hir::Defaultness {
82 match tcx.hir_node_by_def_id(def_id) {
83 hir::Node::Item(hir::Item { kind: hir::ItemKind::Impl(impl_), .. }) => impl_.defaultness,
84 hir::Node::ImplItem(hir::ImplItem { defaultness, .. })
85 | hir::Node::TraitItem(hir::TraitItem { defaultness, .. }) => *defaultness,
86 node => {
87 bug!("`defaultness` called on {:?}", node);
88 }
89 }
90}
91
92#[instrument(level = "debug", skip(tcx), ret)]
105fn adt_sizedness_constraint<'tcx>(
106 tcx: TyCtxt<'tcx>,
107 (def_id, sizedness): (DefId, SizedTraitKind),
108) -> Option<ty::EarlyBinder<'tcx, Ty<'tcx>>> {
109 if let Some(def_id) = def_id.as_local() {
110 if let ty::Representability::Infinite(_) = tcx.representability(def_id) {
111 return None;
112 }
113 }
114 let def = tcx.adt_def(def_id);
115
116 if !def.is_struct() {
117 bug!("`adt_sizedness_constraint` called on non-struct type: {def:?}");
118 }
119
120 let tail_def = def.non_enum_variant().tail_opt()?;
121 let tail_ty = tcx.type_of(tail_def.did).instantiate_identity();
122
123 let constraint_ty = sizedness_constraint_for_ty(tcx, sizedness, tail_ty)?;
124
125 let sizedness_trait_def_id = sizedness.require_lang_item(tcx);
128 let predicates = tcx.predicates_of(def.did()).predicates;
129 if predicates.iter().any(|(p, _)| {
130 p.as_trait_clause().is_some_and(|trait_pred| {
131 trait_pred.def_id() == sizedness_trait_def_id
132 && trait_pred.self_ty().skip_binder() == constraint_ty
133 })
134 }) {
135 return None;
136 }
137
138 Some(ty::EarlyBinder::bind(constraint_ty))
139}
140
141fn param_env(tcx: TyCtxt<'_>, def_id: DefId) -> ty::ParamEnv<'_> {
143 let ty::InstantiatedPredicates { mut predicates, .. } =
145 tcx.predicates_of(def_id).instantiate_identity(tcx);
146
147 if tcx.def_kind(def_id) == DefKind::AssocFn
160 && let assoc_item = tcx.associated_item(def_id)
161 && assoc_item.container == ty::AssocItemContainer::Trait
162 && assoc_item.defaultness(tcx).has_value()
163 {
164 let sig = tcx.fn_sig(def_id).instantiate_identity();
165 sig.skip_binder().visit_with(&mut ImplTraitInTraitFinder {
167 tcx,
168 fn_def_id: def_id,
169 bound_vars: sig.bound_vars(),
170 predicates: &mut predicates,
171 seen: FxHashSet::default(),
172 depth: ty::INNERMOST,
173 });
174 }
175
176 if tcx.is_conditionally_const(def_id) {
179 predicates.extend(
180 tcx.const_conditions(def_id).instantiate_identity(tcx).into_iter().map(
181 |(trait_ref, _)| trait_ref.to_host_effect_clause(tcx, ty::BoundConstness::Maybe),
182 ),
183 );
184 }
185
186 let local_did = def_id.as_local();
187
188 let unnormalized_env = ty::ParamEnv::new(tcx.mk_clauses(&predicates));
189
190 let body_id = local_did.unwrap_or(CRATE_DEF_ID);
191 let cause = traits::ObligationCause::misc(tcx.def_span(def_id), body_id);
192 traits::normalize_param_env_or_error(tcx, unnormalized_env, cause)
193}
194
195struct ImplTraitInTraitFinder<'a, 'tcx> {
200 tcx: TyCtxt<'tcx>,
201 predicates: &'a mut Vec<ty::Clause<'tcx>>,
202 fn_def_id: DefId,
203 bound_vars: &'tcx ty::List<ty::BoundVariableKind>,
204 seen: FxHashSet<DefId>,
205 depth: ty::DebruijnIndex,
206}
207
208impl<'tcx> TypeVisitor<TyCtxt<'tcx>> for ImplTraitInTraitFinder<'_, 'tcx> {
209 fn visit_binder<T: TypeVisitable<TyCtxt<'tcx>>>(&mut self, binder: &ty::Binder<'tcx, T>) {
210 self.depth.shift_in(1);
211 binder.super_visit_with(self);
212 self.depth.shift_out(1);
213 }
214
215 fn visit_ty(&mut self, ty: Ty<'tcx>) {
216 if let ty::Alias(ty::Projection, unshifted_alias_ty) = *ty.kind()
217 && let Some(
218 ty::ImplTraitInTraitData::Trait { fn_def_id, .. }
219 | ty::ImplTraitInTraitData::Impl { fn_def_id, .. },
220 ) = self.tcx.opt_rpitit_info(unshifted_alias_ty.def_id)
221 && fn_def_id == self.fn_def_id
222 && self.seen.insert(unshifted_alias_ty.def_id)
223 {
224 let shifted_alias_ty = fold_regions(self.tcx, unshifted_alias_ty, |re, depth| {
228 if let ty::ReBound(index, bv) = re.kind() {
229 if depth != ty::INNERMOST {
230 return ty::Region::new_error_with_message(
231 self.tcx,
232 DUMMY_SP,
233 "we shouldn't walk non-predicate binders with `impl Trait`...",
234 );
235 }
236 ty::Region::new_bound(self.tcx, index.shifted_out_to_binder(self.depth), bv)
237 } else {
238 re
239 }
240 });
241
242 let default_ty = self
246 .tcx
247 .type_of(shifted_alias_ty.def_id)
248 .instantiate(self.tcx, shifted_alias_ty.args);
249
250 self.predicates.push(
251 ty::Binder::bind_with_vars(
252 ty::ProjectionPredicate {
253 projection_term: shifted_alias_ty.into(),
254 term: default_ty.into(),
255 },
256 self.bound_vars,
257 )
258 .upcast(self.tcx),
259 );
260
261 for bound in self
266 .tcx
267 .item_bounds(unshifted_alias_ty.def_id)
268 .iter_instantiated(self.tcx, unshifted_alias_ty.args)
269 {
270 bound.visit_with(self);
271 }
272 }
273
274 ty.super_visit_with(self)
275 }
276}
277
278fn typing_env_normalized_for_post_analysis(tcx: TyCtxt<'_>, def_id: DefId) -> ty::TypingEnv<'_> {
279 ty::TypingEnv::non_body_analysis(tcx, def_id).with_post_analysis_normalized(tcx)
280}
281
282fn asyncness(tcx: TyCtxt<'_>, def_id: LocalDefId) -> ty::Asyncness {
284 let node = tcx.hir_node_by_def_id(def_id);
285 node.fn_sig().map_or(ty::Asyncness::No, |sig| match sig.header.asyncness {
286 hir::IsAsync::Async(_) => ty::Asyncness::Yes,
287 hir::IsAsync::NotAsync => ty::Asyncness::No,
288 })
289}
290
291fn unsizing_params_for_adt<'tcx>(tcx: TyCtxt<'tcx>, def_id: DefId) -> DenseBitSet<u32> {
292 let def = tcx.adt_def(def_id);
293 let num_params = tcx.generics_of(def_id).count();
294
295 let maybe_unsizing_param_idx = |arg: ty::GenericArg<'tcx>| match arg.kind() {
296 ty::GenericArgKind::Type(ty) => match ty.kind() {
297 ty::Param(p) => Some(p.index),
298 _ => None,
299 },
300
301 ty::GenericArgKind::Lifetime(_) => None,
303
304 ty::GenericArgKind::Const(ct) => match ct.kind() {
305 ty::ConstKind::Param(p) => Some(p.index),
306 _ => None,
307 },
308 };
309
310 let Some((tail_field, prefix_fields)) = def.non_enum_variant().fields.raw.split_last() else {
312 return DenseBitSet::new_empty(num_params);
313 };
314
315 let mut unsizing_params = DenseBitSet::new_empty(num_params);
316 for arg in tcx.type_of(tail_field.did).instantiate_identity().walk() {
317 if let Some(i) = maybe_unsizing_param_idx(arg) {
318 unsizing_params.insert(i);
319 }
320 }
321
322 for field in prefix_fields {
325 for arg in tcx.type_of(field.did).instantiate_identity().walk() {
326 if let Some(i) = maybe_unsizing_param_idx(arg) {
327 unsizing_params.remove(i);
328 }
329 }
330 }
331
332 unsizing_params
333}
334
335fn impl_self_is_guaranteed_unsized<'tcx>(tcx: TyCtxt<'tcx>, impl_def_id: DefId) -> bool {
336 debug_assert_eq!(tcx.def_kind(impl_def_id), DefKind::Impl { of_trait: true });
337
338 let infcx = tcx.infer_ctxt().ignoring_regions().build(ty::TypingMode::non_body_analysis());
339
340 let ocx = traits::ObligationCtxt::new(&infcx);
341 let cause = traits::ObligationCause::dummy();
342 let param_env = tcx.param_env(impl_def_id);
343
344 let tail = tcx.struct_tail_raw(
345 tcx.type_of(impl_def_id).instantiate_identity(),
346 |ty| {
347 ocx.structurally_normalize_ty(&cause, param_env, ty).unwrap_or_else(|_| {
348 Ty::new_error_with_message(
349 tcx,
350 tcx.def_span(impl_def_id),
351 "struct tail should be computable",
352 )
353 })
354 },
355 || (),
356 );
357
358 match tail.kind() {
359 ty::Dynamic(_, _, ty::Dyn) | ty::Slice(_) | ty::Str => true,
360 ty::Bool
361 | ty::Char
362 | ty::Int(_)
363 | ty::Uint(_)
364 | ty::Float(_)
365 | ty::Adt(_, _)
366 | ty::Foreign(_)
367 | ty::Array(_, _)
368 | ty::Pat(_, _)
369 | ty::RawPtr(_, _)
370 | ty::Ref(_, _, _)
371 | ty::FnDef(_, _)
372 | ty::FnPtr(_, _)
373 | ty::UnsafeBinder(_)
374 | ty::Closure(_, _)
375 | ty::CoroutineClosure(_, _)
376 | ty::Coroutine(_, _)
377 | ty::CoroutineWitness(_, _)
378 | ty::Never
379 | ty::Tuple(_)
380 | ty::Alias(_, _)
381 | ty::Param(_)
382 | ty::Bound(_, _)
383 | ty::Placeholder(_)
384 | ty::Infer(_)
385 | ty::Error(_) => false,
386 }
387}
388
389pub(crate) fn provide(providers: &mut Providers) {
390 *providers = Providers {
391 asyncness,
392 adt_sizedness_constraint,
393 param_env,
394 typing_env_normalized_for_post_analysis,
395 defaultness,
396 unsizing_params_for_adt,
397 impl_self_is_guaranteed_unsized,
398 ..*providers
399 };
400}