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