1 use rustc_data_structures::fx::FxHashSet;
2 use rustc_hir as hir;
3 use rustc_hir::def::DefKind;
4 use rustc_index::bit_set::BitSet;
5 use rustc_middle::query::Providers;
6 use rustc_middle::ty::{
7 self, EarlyBinder, ToPredicate, Ty, TyCtxt, TypeSuperVisitable, TypeVisitable, TypeVisitor,
8 };
9 use rustc_span::def_id::{DefId, LocalDefId, CRATE_DEF_ID};
10 use rustc_span::DUMMY_SP;
11 use rustc_trait_selection::traits;
12
sized_constraint_for_ty<'tcx>( tcx: TyCtxt<'tcx>, adtdef: ty::AdtDef<'tcx>, ty: Ty<'tcx>, ) -> Vec<Ty<'tcx>>13 fn sized_constraint_for_ty<'tcx>(
14 tcx: TyCtxt<'tcx>,
15 adtdef: ty::AdtDef<'tcx>,
16 ty: Ty<'tcx>,
17 ) -> Vec<Ty<'tcx>> {
18 use rustc_type_ir::sty::TyKind::*;
19
20 let result = match ty.kind() {
21 Bool | Char | Int(..) | Uint(..) | Float(..) | RawPtr(..) | Ref(..) | FnDef(..)
22 | FnPtr(_) | Array(..) | Closure(..) | Generator(..) | Never => vec![],
23
24 Str
25 | Dynamic(..)
26 | Slice(_)
27 | Foreign(..)
28 | Error(_)
29 | GeneratorWitness(..)
30 | GeneratorWitnessMIR(..) => {
31 // these are never sized - return the target type
32 vec![ty]
33 }
34
35 Tuple(ref tys) => match tys.last() {
36 None => vec![],
37 Some(&ty) => sized_constraint_for_ty(tcx, adtdef, ty),
38 },
39
40 Adt(adt, substs) => {
41 // recursive case
42 let adt_tys = adt.sized_constraint(tcx);
43 debug!("sized_constraint_for_ty({:?}) intermediate = {:?}", ty, adt_tys);
44 adt_tys
45 .subst_iter_copied(tcx, substs)
46 .flat_map(|ty| sized_constraint_for_ty(tcx, adtdef, ty))
47 .collect()
48 }
49
50 Alias(..) => {
51 // must calculate explicitly.
52 // FIXME: consider special-casing always-Sized projections
53 vec![ty]
54 }
55
56 Param(..) => {
57 // perf hack: if there is a `T: Sized` bound, then
58 // we know that `T` is Sized and do not need to check
59 // it on the impl.
60
61 let Some(sized_trait) = tcx.lang_items().sized_trait() else { return vec![ty] };
62 let sized_predicate =
63 ty::TraitRef::new(tcx, sized_trait, [ty]).without_const().to_predicate(tcx);
64 let predicates = tcx.predicates_of(adtdef.did()).predicates;
65 if predicates.iter().any(|(p, _)| *p == sized_predicate) { vec![] } else { vec![ty] }
66 }
67
68 Placeholder(..) | Bound(..) | Infer(..) => {
69 bug!("unexpected type `{:?}` in sized_constraint_for_ty", ty)
70 }
71 };
72 debug!("sized_constraint_for_ty({:?}) = {:?}", ty, result);
73 result
74 }
75
defaultness(tcx: TyCtxt<'_>, def_id: LocalDefId) -> hir::Defaultness76 fn defaultness(tcx: TyCtxt<'_>, def_id: LocalDefId) -> hir::Defaultness {
77 match tcx.hir().get_by_def_id(def_id) {
78 hir::Node::Item(hir::Item { kind: hir::ItemKind::Impl(impl_), .. }) => impl_.defaultness,
79 hir::Node::ImplItem(hir::ImplItem { defaultness, .. })
80 | hir::Node::TraitItem(hir::TraitItem { defaultness, .. }) => *defaultness,
81 node => {
82 bug!("`defaultness` called on {:?}", node);
83 }
84 }
85 }
86
87 /// Calculates the `Sized` constraint.
88 ///
89 /// In fact, there are only a few options for the types in the constraint:
90 /// - an obviously-unsized type
91 /// - a type parameter or projection whose Sizedness can't be known
92 /// - a tuple of type parameters or projections, if there are multiple
93 /// such.
94 /// - an Error, if a type is infinitely sized
adt_sized_constraint(tcx: TyCtxt<'_>, def_id: DefId) -> &[Ty<'_>]95 fn adt_sized_constraint(tcx: TyCtxt<'_>, def_id: DefId) -> &[Ty<'_>] {
96 if let Some(def_id) = def_id.as_local() {
97 if matches!(tcx.representability(def_id), ty::Representability::Infinite) {
98 return tcx.mk_type_list(&[Ty::new_misc_error(tcx)]);
99 }
100 }
101 let def = tcx.adt_def(def_id);
102
103 let result = tcx.mk_type_list_from_iter(
104 def.variants()
105 .iter()
106 .filter_map(|v| v.tail_opt())
107 .flat_map(|f| sized_constraint_for_ty(tcx, def, tcx.type_of(f.did).subst_identity())),
108 );
109
110 debug!("adt_sized_constraint: {:?} => {:?}", def, result);
111
112 result
113 }
114
115 /// See `ParamEnv` struct definition for details.
param_env(tcx: TyCtxt<'_>, def_id: DefId) -> ty::ParamEnv<'_>116 fn param_env(tcx: TyCtxt<'_>, def_id: DefId) -> ty::ParamEnv<'_> {
117 // Compute the bounds on Self and the type parameters.
118 let ty::InstantiatedPredicates { mut predicates, .. } =
119 tcx.predicates_of(def_id).instantiate_identity(tcx);
120
121 // Finally, we have to normalize the bounds in the environment, in
122 // case they contain any associated type projections. This process
123 // can yield errors if the put in illegal associated types, like
124 // `<i32 as Foo>::Bar` where `i32` does not implement `Foo`. We
125 // report these errors right here; this doesn't actually feel
126 // right to me, because constructing the environment feels like a
127 // kind of an "idempotent" action, but I'm not sure where would be
128 // a better place. In practice, we construct environments for
129 // every fn once during type checking, and we'll abort if there
130 // are any errors at that point, so outside of type inference you can be
131 // sure that this will succeed without errors anyway.
132
133 if tcx.def_kind(def_id) == DefKind::AssocFn
134 && tcx.associated_item(def_id).container == ty::AssocItemContainer::TraitContainer
135 {
136 let sig = tcx.fn_sig(def_id).subst_identity();
137 // We accounted for the binder of the fn sig, so skip the binder.
138 sig.skip_binder().visit_with(&mut ImplTraitInTraitFinder {
139 tcx,
140 fn_def_id: def_id,
141 bound_vars: sig.bound_vars(),
142 predicates: &mut predicates,
143 seen: FxHashSet::default(),
144 depth: ty::INNERMOST,
145 });
146 }
147
148 let local_did = def_id.as_local();
149 // FIXME(-Zlower-impl-trait-in-trait-to-assoc-ty): This isn't correct for
150 // RPITITs in const trait fn.
151 let hir_id = local_did.and_then(|def_id| tcx.opt_local_def_id_to_hir_id(def_id));
152
153 // FIXME(consts): This is not exactly in line with the constness query.
154 let constness = match hir_id {
155 Some(hir_id) => match tcx.hir().get(hir_id) {
156 hir::Node::TraitItem(hir::TraitItem { kind: hir::TraitItemKind::Fn(..), .. })
157 if tcx.is_const_default_method(def_id) =>
158 {
159 hir::Constness::Const
160 }
161
162 hir::Node::Item(hir::Item { kind: hir::ItemKind::Const(..), .. })
163 | hir::Node::Item(hir::Item { kind: hir::ItemKind::Static(..), .. })
164 | hir::Node::TraitItem(hir::TraitItem {
165 kind: hir::TraitItemKind::Const(..), ..
166 })
167 | hir::Node::AnonConst(_)
168 | hir::Node::ConstBlock(_)
169 | hir::Node::ImplItem(hir::ImplItem { kind: hir::ImplItemKind::Const(..), .. })
170 | hir::Node::ImplItem(hir::ImplItem {
171 kind:
172 hir::ImplItemKind::Fn(
173 hir::FnSig {
174 header: hir::FnHeader { constness: hir::Constness::Const, .. },
175 ..
176 },
177 ..,
178 ),
179 ..
180 }) => hir::Constness::Const,
181
182 hir::Node::ImplItem(hir::ImplItem {
183 kind: hir::ImplItemKind::Type(..) | hir::ImplItemKind::Fn(..),
184 ..
185 }) => {
186 let parent_hir_id = tcx.hir().parent_id(hir_id);
187 match tcx.hir().get(parent_hir_id) {
188 hir::Node::Item(hir::Item {
189 kind: hir::ItemKind::Impl(hir::Impl { constness, .. }),
190 ..
191 }) => *constness,
192 _ => span_bug!(
193 tcx.def_span(parent_hir_id.owner),
194 "impl item's parent node is not an impl",
195 ),
196 }
197 }
198
199 hir::Node::Item(hir::Item {
200 kind:
201 hir::ItemKind::Fn(hir::FnSig { header: hir::FnHeader { constness, .. }, .. }, ..),
202 ..
203 })
204 | hir::Node::TraitItem(hir::TraitItem {
205 kind:
206 hir::TraitItemKind::Fn(
207 hir::FnSig { header: hir::FnHeader { constness, .. }, .. },
208 ..,
209 ),
210 ..
211 })
212 | hir::Node::Item(hir::Item {
213 kind: hir::ItemKind::Impl(hir::Impl { constness, .. }),
214 ..
215 }) => *constness,
216
217 _ => hir::Constness::NotConst,
218 },
219 // FIXME(consts): It's suspicious that a param-env for a foreign item
220 // will always have NotConst param-env, though we don't typically use
221 // that param-env for anything meaningful right now, so it's likely
222 // not an issue.
223 None => hir::Constness::NotConst,
224 };
225
226 let unnormalized_env =
227 ty::ParamEnv::new(tcx.mk_clauses(&predicates), traits::Reveal::UserFacing, constness);
228
229 let body_id = local_did.unwrap_or(CRATE_DEF_ID);
230 let cause = traits::ObligationCause::misc(tcx.def_span(def_id), body_id);
231 traits::normalize_param_env_or_error(tcx, unnormalized_env, cause)
232 }
233
234 /// Walk through a function type, gathering all RPITITs and installing a
235 /// `NormalizesTo(Projection(RPITIT) -> Opaque(RPITIT))` predicate into the
236 /// predicates list. This allows us to observe that an RPITIT projects to
237 /// its corresponding opaque within the body of a default-body trait method.
238 struct ImplTraitInTraitFinder<'a, 'tcx> {
239 tcx: TyCtxt<'tcx>,
240 predicates: &'a mut Vec<ty::Clause<'tcx>>,
241 fn_def_id: DefId,
242 bound_vars: &'tcx ty::List<ty::BoundVariableKind>,
243 seen: FxHashSet<DefId>,
244 depth: ty::DebruijnIndex,
245 }
246
247 impl<'tcx> TypeVisitor<TyCtxt<'tcx>> for ImplTraitInTraitFinder<'_, 'tcx> {
visit_binder<T: TypeVisitable<TyCtxt<'tcx>>>( &mut self, binder: &ty::Binder<'tcx, T>, ) -> std::ops::ControlFlow<Self::BreakTy>248 fn visit_binder<T: TypeVisitable<TyCtxt<'tcx>>>(
249 &mut self,
250 binder: &ty::Binder<'tcx, T>,
251 ) -> std::ops::ControlFlow<Self::BreakTy> {
252 self.depth.shift_in(1);
253 let binder = binder.super_visit_with(self);
254 self.depth.shift_out(1);
255 binder
256 }
257
visit_ty(&mut self, ty: Ty<'tcx>) -> std::ops::ControlFlow<Self::BreakTy>258 fn visit_ty(&mut self, ty: Ty<'tcx>) -> std::ops::ControlFlow<Self::BreakTy> {
259 if let ty::Alias(ty::Projection, unshifted_alias_ty) = *ty.kind()
260 && self.tcx.is_impl_trait_in_trait(unshifted_alias_ty.def_id)
261 && self.tcx.impl_trait_in_trait_parent_fn(unshifted_alias_ty.def_id) == self.fn_def_id
262 && self.seen.insert(unshifted_alias_ty.def_id)
263 {
264 // We have entered some binders as we've walked into the
265 // bounds of the RPITIT. Shift these binders back out when
266 // constructing the top-level projection predicate.
267 let shifted_alias_ty = self.tcx.fold_regions(unshifted_alias_ty, |re, depth| {
268 if let ty::ReLateBound(index, bv) = re.kind() {
269 if depth != ty::INNERMOST {
270 return ty::Region::new_error_with_message(
271 self.tcx,
272 DUMMY_SP,
273 "we shouldn't walk non-predicate binders with `impl Trait`...",
274 );
275 }
276 ty::Region::new_late_bound(self.tcx, index.shifted_out_to_binder(self.depth), bv)
277 } else {
278 re
279 }
280 });
281
282 // If we're lowering to associated item, install the opaque type which is just
283 // the `type_of` of the trait's associated item. If we're using the old lowering
284 // strategy, then just reinterpret the associated type like an opaque :^)
285 let default_ty = if self.tcx.lower_impl_trait_in_trait_to_assoc_ty() {
286 self.tcx.type_of(shifted_alias_ty.def_id).subst(self.tcx, shifted_alias_ty.substs)
287 } else {
288 Ty::new_alias(self.tcx,ty::Opaque, shifted_alias_ty)
289 };
290
291 self.predicates.push(
292 ty::Binder::bind_with_vars(
293 ty::ProjectionPredicate { projection_ty: shifted_alias_ty, term: default_ty.into() },
294 self.bound_vars,
295 )
296 .to_predicate(self.tcx),
297 );
298
299 // We walk the *un-shifted* alias ty, because we're tracking the de bruijn
300 // binder depth, and if we were to walk `shifted_alias_ty` instead, we'd
301 // have to reset `self.depth` back to `ty::INNERMOST` or something. It's
302 // easier to just do this.
303 for bound in self
304 .tcx
305 .item_bounds(unshifted_alias_ty.def_id)
306 .subst_iter(self.tcx, unshifted_alias_ty.substs)
307 {
308 bound.visit_with(self);
309 }
310 }
311
312 ty.super_visit_with(self)
313 }
314 }
315
param_env_reveal_all_normalized(tcx: TyCtxt<'_>, def_id: DefId) -> ty::ParamEnv<'_>316 fn param_env_reveal_all_normalized(tcx: TyCtxt<'_>, def_id: DefId) -> ty::ParamEnv<'_> {
317 tcx.param_env(def_id).with_reveal_all_normalized(tcx)
318 }
319
instance_def_size_estimate<'tcx>( tcx: TyCtxt<'tcx>, instance_def: ty::InstanceDef<'tcx>, ) -> usize320 fn instance_def_size_estimate<'tcx>(
321 tcx: TyCtxt<'tcx>,
322 instance_def: ty::InstanceDef<'tcx>,
323 ) -> usize {
324 use ty::InstanceDef;
325
326 match instance_def {
327 InstanceDef::Item(..) | InstanceDef::DropGlue(..) => {
328 let mir = tcx.instance_mir(instance_def);
329 mir.basic_blocks.iter().map(|bb| bb.statements.len() + 1).sum()
330 }
331 // Estimate the size of other compiler-generated shims to be 1.
332 _ => 1,
333 }
334 }
335
336 /// If `def_id` is an issue 33140 hack impl, returns its self type; otherwise, returns `None`.
337 ///
338 /// See [`ty::ImplOverlapKind::Issue33140`] for more details.
issue33140_self_ty(tcx: TyCtxt<'_>, def_id: DefId) -> Option<EarlyBinder<Ty<'_>>>339 fn issue33140_self_ty(tcx: TyCtxt<'_>, def_id: DefId) -> Option<EarlyBinder<Ty<'_>>> {
340 debug!("issue33140_self_ty({:?})", def_id);
341
342 let trait_ref = tcx
343 .impl_trait_ref(def_id)
344 .unwrap_or_else(|| bug!("issue33140_self_ty called on inherent impl {:?}", def_id))
345 .skip_binder();
346
347 debug!("issue33140_self_ty({:?}), trait-ref={:?}", def_id, trait_ref);
348
349 let is_marker_like = tcx.impl_polarity(def_id) == ty::ImplPolarity::Positive
350 && tcx.associated_item_def_ids(trait_ref.def_id).is_empty();
351
352 // Check whether these impls would be ok for a marker trait.
353 if !is_marker_like {
354 debug!("issue33140_self_ty - not marker-like!");
355 return None;
356 }
357
358 // impl must be `impl Trait for dyn Marker1 + Marker2 + ...`
359 if trait_ref.substs.len() != 1 {
360 debug!("issue33140_self_ty - impl has substs!");
361 return None;
362 }
363
364 let predicates = tcx.predicates_of(def_id);
365 if predicates.parent.is_some() || !predicates.predicates.is_empty() {
366 debug!("issue33140_self_ty - impl has predicates {:?}!", predicates);
367 return None;
368 }
369
370 let self_ty = trait_ref.self_ty();
371 let self_ty_matches = match self_ty.kind() {
372 ty::Dynamic(ref data, re, _) if re.is_static() => data.principal().is_none(),
373 _ => false,
374 };
375
376 if self_ty_matches {
377 debug!("issue33140_self_ty - MATCHES!");
378 Some(EarlyBinder::bind(self_ty))
379 } else {
380 debug!("issue33140_self_ty - non-matching self type");
381 None
382 }
383 }
384
385 /// Check if a function is async.
asyncness(tcx: TyCtxt<'_>, def_id: LocalDefId) -> hir::IsAsync386 fn asyncness(tcx: TyCtxt<'_>, def_id: LocalDefId) -> hir::IsAsync {
387 let node = tcx.hir().get_by_def_id(def_id);
388 node.fn_sig().map_or(hir::IsAsync::NotAsync, |sig| sig.header.asyncness)
389 }
390
unsizing_params_for_adt<'tcx>(tcx: TyCtxt<'tcx>, def_id: DefId) -> BitSet<u32>391 fn unsizing_params_for_adt<'tcx>(tcx: TyCtxt<'tcx>, def_id: DefId) -> BitSet<u32> {
392 let def = tcx.adt_def(def_id);
393 let num_params = tcx.generics_of(def_id).count();
394
395 let maybe_unsizing_param_idx = |arg: ty::GenericArg<'tcx>| match arg.unpack() {
396 ty::GenericArgKind::Type(ty) => match ty.kind() {
397 ty::Param(p) => Some(p.index),
398 _ => None,
399 },
400
401 // We can't unsize a lifetime
402 ty::GenericArgKind::Lifetime(_) => None,
403
404 ty::GenericArgKind::Const(ct) => match ct.kind() {
405 ty::ConstKind::Param(p) => Some(p.index),
406 _ => None,
407 },
408 };
409
410 // The last field of the structure has to exist and contain type/const parameters.
411 let Some((tail_field, prefix_fields)) =
412 def.non_enum_variant().fields.raw.split_last() else
413 {
414 return BitSet::new_empty(num_params);
415 };
416
417 let mut unsizing_params = BitSet::new_empty(num_params);
418 for arg in tcx.type_of(tail_field.did).subst_identity().walk() {
419 if let Some(i) = maybe_unsizing_param_idx(arg) {
420 unsizing_params.insert(i);
421 }
422 }
423
424 // Ensure none of the other fields mention the parameters used
425 // in unsizing.
426 for field in prefix_fields {
427 for arg in tcx.type_of(field.did).subst_identity().walk() {
428 if let Some(i) = maybe_unsizing_param_idx(arg) {
429 unsizing_params.remove(i);
430 }
431 }
432 }
433
434 unsizing_params
435 }
436
provide(providers: &mut Providers)437 pub fn provide(providers: &mut Providers) {
438 *providers = Providers {
439 asyncness,
440 adt_sized_constraint,
441 param_env,
442 param_env_reveal_all_normalized,
443 instance_def_size_estimate,
444 issue33140_self_ty,
445 defaultness,
446 unsizing_params_for_adt,
447 ..*providers
448 };
449 }
450