rustc_ty_utils/
ty.rs

Help
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_middle::bug;
7use rustc_middle::query::Providers;
8use rustc_middle::ty::{
9    self, Ty, TyCtxt, TypeSuperVisitable, TypeVisitable, TypeVisitor, Upcast, fold_regions,
10};
11use rustc_span::DUMMY_SP;
12use rustc_span::def_id::{CRATE_DEF_ID, DefId, LocalDefId};
13use rustc_trait_selection::traits;
14use tracing::instrument;
15
16#[instrument(level = "debug", skip(tcx), ret)]
17fn sized_constraint_for_ty<'tcx>(tcx: TyCtxt<'tcx>, ty: Ty<'tcx>) -> Option<Ty<'tcx>> {
18    match ty.kind() {
19        // these are always sized
20        ty::Bool
21        | ty::Char
22        | ty::Int(..)
23        | ty::Uint(..)
24        | ty::Float(..)
25        | ty::RawPtr(..)
26        | ty::Ref(..)
27        | ty::FnDef(..)
28        | ty::FnPtr(..)
29        | ty::Array(..)
30        | ty::Closure(..)
31        | ty::CoroutineClosure(..)
32        | ty::Coroutine(..)
33        | ty::CoroutineWitness(..)
34        | ty::Never
35        | ty::Dynamic(_, _, ty::DynStar) => None,
36
37        // these are never sized
38        ty::Str | ty::Slice(..) | ty::Dynamic(_, _, ty::Dyn) | ty::Foreign(..) => Some(ty),
39
40        ty::Pat(ty, _) => sized_constraint_for_ty(tcx, *ty),
41
42        ty::Tuple(tys) => tys.last().and_then(|&ty| sized_constraint_for_ty(tcx, ty)),
43
44        // recursive case
45        ty::Adt(adt, args) => adt.sized_constraint(tcx).and_then(|intermediate| {
46            let ty = intermediate.instantiate(tcx, args);
47            sized_constraint_for_ty(tcx, ty)
48        }),
49
50        // these can be sized or unsized.
51        ty::Param(..) | ty::Alias(..) | ty::Error(_) => Some(ty),
52
53        // We cannot instantiate the binder, so just return the *original* type back,
54        // but only if the inner type has a sized constraint. Thus we skip the binder,
55        // but don't actually use the result from `sized_constraint_for_ty`.
56        ty::UnsafeBinder(inner_ty) => {
57            sized_constraint_for_ty(tcx, inner_ty.skip_binder()).map(|_| ty)
58        }
59
60        ty::Placeholder(..) | ty::Bound(..) | ty::Infer(..) => {
61            bug!("unexpected type `{ty:?}` in sized_constraint_for_ty")
62        }
63    }
64}
65
66fn defaultness(tcx: TyCtxt<'_>, def_id: LocalDefId) -> hir::Defaultness {
67    match tcx.hir_node_by_def_id(def_id) {
68        hir::Node::Item(hir::Item { kind: hir::ItemKind::Impl(impl_), .. }) => impl_.defaultness,
69        hir::Node::ImplItem(hir::ImplItem { defaultness, .. })
70        | hir::Node::TraitItem(hir::TraitItem { defaultness, .. }) => *defaultness,
71        node => {
72            bug!("`defaultness` called on {:?}", node);
73        }
74    }
75}
76
77/// Calculates the `Sized` constraint.
78///
79/// In fact, there are only a few options for the types in the constraint:
80///     - an obviously-unsized type
81///     - a type parameter or projection whose sizedness can't be known
82#[instrument(level = "debug", skip(tcx), ret)]
83fn adt_sized_constraint<'tcx>(
84    tcx: TyCtxt<'tcx>,
85    def_id: DefId,
86) -> Option<ty::EarlyBinder<'tcx, Ty<'tcx>>> {
87    if let Some(def_id) = def_id.as_local() {
88        if let ty::Representability::Infinite(_) = tcx.representability(def_id) {
89            return None;
90        }
91    }
92    let def = tcx.adt_def(def_id);
93
94    if !def.is_struct() {
95        bug!("`adt_sized_constraint` called on non-struct type: {def:?}");
96    }
97
98    let tail_def = def.non_enum_variant().tail_opt()?;
99    let tail_ty = tcx.type_of(tail_def.did).instantiate_identity();
100
101    let constraint_ty = sized_constraint_for_ty(tcx, tail_ty)?;
102
103    // perf hack: if there is a `constraint_ty: Sized` bound, then we know
104    // that the type is sized and do not need to check it on the impl.
105    let sized_trait_def_id = tcx.require_lang_item(LangItem::Sized, None);
106    let predicates = tcx.predicates_of(def.did()).predicates;
107    if predicates.iter().any(|(p, _)| {
108        p.as_trait_clause().is_some_and(|trait_pred| {
109            trait_pred.def_id() == sized_trait_def_id
110                && trait_pred.self_ty().skip_binder() == constraint_ty
111        })
112    }) {
113        return None;
114    }
115
116    Some(ty::EarlyBinder::bind(constraint_ty))
117}
118
119/// See `ParamEnv` struct definition for details.
120fn param_env(tcx: TyCtxt<'_>, def_id: DefId) -> ty::ParamEnv<'_> {
121    // Compute the bounds on Self and the type parameters.
122    let ty::InstantiatedPredicates { mut predicates, .. } =
123        tcx.predicates_of(def_id).instantiate_identity(tcx);
124
125    // Finally, we have to normalize the bounds in the environment, in
126    // case they contain any associated type projections. This process
127    // can yield errors if the put in illegal associated types, like
128    // `<i32 as Foo>::Bar` where `i32` does not implement `Foo`. We
129    // report these errors right here; this doesn't actually feel
130    // right to me, because constructing the environment feels like a
131    // kind of an "idempotent" action, but I'm not sure where would be
132    // a better place. In practice, we construct environments for
133    // every fn once during type checking, and we'll abort if there
134    // are any errors at that point, so outside of type inference you can be
135    // sure that this will succeed without errors anyway.
136
137    if tcx.def_kind(def_id) == DefKind::AssocFn
138        && let assoc_item = tcx.associated_item(def_id)
139        && assoc_item.container == ty::AssocItemContainer::Trait
140        && assoc_item.defaultness(tcx).has_value()
141    {
142        let sig = tcx.fn_sig(def_id).instantiate_identity();
143        // We accounted for the binder of the fn sig, so skip the binder.
144        sig.skip_binder().visit_with(&mut ImplTraitInTraitFinder {
145            tcx,
146            fn_def_id: def_id,
147            bound_vars: sig.bound_vars(),
148            predicates: &mut predicates,
149            seen: FxHashSet::default(),
150            depth: ty::INNERMOST,
151        });
152    }
153
154    // We extend the param-env of our item with the const conditions of the item,
155    // since we're allowed to assume `~const` bounds hold within the item itself.
156    if tcx.is_conditionally_const(def_id) {
157        predicates.extend(
158            tcx.const_conditions(def_id).instantiate_identity(tcx).into_iter().map(
159                |(trait_ref, _)| trait_ref.to_host_effect_clause(tcx, ty::BoundConstness::Maybe),
160            ),
161        );
162    }
163
164    let local_did = def_id.as_local();
165
166    let unnormalized_env = ty::ParamEnv::new(tcx.mk_clauses(&predicates));
167
168    let body_id = local_did.unwrap_or(CRATE_DEF_ID);
169    let cause = traits::ObligationCause::misc(tcx.def_span(def_id), body_id);
170    traits::normalize_param_env_or_error(tcx, unnormalized_env, cause)
171}
172
173/// Walk through a function type, gathering all RPITITs and installing a
174/// `NormalizesTo(Projection(RPITIT) -> Opaque(RPITIT))` predicate into the
175/// predicates list. This allows us to observe that an RPITIT projects to
176/// its corresponding opaque within the body of a default-body trait method.
177struct ImplTraitInTraitFinder<'a, 'tcx> {
178    tcx: TyCtxt<'tcx>,
179    predicates: &'a mut Vec<ty::Clause<'tcx>>,
180    fn_def_id: DefId,
181    bound_vars: &'tcx ty::List<ty::BoundVariableKind>,
182    seen: FxHashSet<DefId>,
183    depth: ty::DebruijnIndex,
184}
185
186impl<'tcx> TypeVisitor<TyCtxt<'tcx>> for ImplTraitInTraitFinder<'_, 'tcx> {
187    fn visit_binder<T: TypeVisitable<TyCtxt<'tcx>>>(&mut self, binder: &ty::Binder<'tcx, T>) {
188        self.depth.shift_in(1);
189        binder.super_visit_with(self);
190        self.depth.shift_out(1);
191    }
192
193    fn visit_ty(&mut self, ty: Ty<'tcx>) {
194        if let ty::Alias(ty::Projection, unshifted_alias_ty) = *ty.kind()
195            && let Some(
196                ty::ImplTraitInTraitData::Trait { fn_def_id, .. }
197                | ty::ImplTraitInTraitData::Impl { fn_def_id, .. },
198            ) = self.tcx.opt_rpitit_info(unshifted_alias_ty.def_id)
199            && fn_def_id == self.fn_def_id
200            && self.seen.insert(unshifted_alias_ty.def_id)
201        {
202            // We have entered some binders as we've walked into the
203            // bounds of the RPITIT. Shift these binders back out when
204            // constructing the top-level projection predicate.
205            let shifted_alias_ty = fold_regions(self.tcx, unshifted_alias_ty, |re, depth| {
206                if let ty::ReBound(index, bv) = re.kind() {
207                    if depth != ty::INNERMOST {
208                        return ty::Region::new_error_with_message(
209                            self.tcx,
210                            DUMMY_SP,
211                            "we shouldn't walk non-predicate binders with `impl Trait`...",
212                        );
213                    }
214                    ty::Region::new_bound(self.tcx, index.shifted_out_to_binder(self.depth), bv)
215                } else {
216                    re
217                }
218            });
219
220            // If we're lowering to associated item, install the opaque type which is just
221            // the `type_of` of the trait's associated item. If we're using the old lowering
222            // strategy, then just reinterpret the associated type like an opaque :^)
223            let default_ty = self
224                .tcx
225                .type_of(shifted_alias_ty.def_id)
226                .instantiate(self.tcx, shifted_alias_ty.args);
227
228            self.predicates.push(
229                ty::Binder::bind_with_vars(
230                    ty::ProjectionPredicate {
231                        projection_term: shifted_alias_ty.into(),
232                        term: default_ty.into(),
233                    },
234                    self.bound_vars,
235                )
236                .upcast(self.tcx),
237            );
238
239            // We walk the *un-shifted* alias ty, because we're tracking the de bruijn
240            // binder depth, and if we were to walk `shifted_alias_ty` instead, we'd
241            // have to reset `self.depth` back to `ty::INNERMOST` or something. It's
242            // easier to just do this.
243            for bound in self
244                .tcx
245                .item_bounds(unshifted_alias_ty.def_id)
246                .iter_instantiated(self.tcx, unshifted_alias_ty.args)
247            {
248                bound.visit_with(self);
249            }
250        }
251
252        ty.super_visit_with(self)
253    }
254}
255
256fn param_env_normalized_for_post_analysis(tcx: TyCtxt<'_>, def_id: DefId) -> ty::ParamEnv<'_> {
257    // This is a bit ugly but the easiest way to avoid code duplication.
258    let typing_env = ty::TypingEnv::non_body_analysis(tcx, def_id);
259    typing_env.with_post_analysis_normalized(tcx).param_env
260}
261
262/// Check if a function is async.
263fn asyncness(tcx: TyCtxt<'_>, def_id: LocalDefId) -> ty::Asyncness {
264    let node = tcx.hir_node_by_def_id(def_id);
265    node.fn_sig().map_or(ty::Asyncness::No, |sig| match sig.header.asyncness {
266        hir::IsAsync::Async(_) => ty::Asyncness::Yes,
267        hir::IsAsync::NotAsync => ty::Asyncness::No,
268    })
269}
270
271fn unsizing_params_for_adt<'tcx>(tcx: TyCtxt<'tcx>, def_id: DefId) -> DenseBitSet<u32> {
272    let def = tcx.adt_def(def_id);
273    let num_params = tcx.generics_of(def_id).count();
274
275    let maybe_unsizing_param_idx = |arg: ty::GenericArg<'tcx>| match arg.unpack() {
276        ty::GenericArgKind::Type(ty) => match ty.kind() {
277            ty::Param(p) => Some(p.index),
278            _ => None,
279        },
280
281        // We can't unsize a lifetime
282        ty::GenericArgKind::Lifetime(_) => None,
283
284        ty::GenericArgKind::Const(ct) => match ct.kind() {
285            ty::ConstKind::Param(p) => Some(p.index),
286            _ => None,
287        },
288    };
289
290    // The last field of the structure has to exist and contain type/const parameters.
291    let Some((tail_field, prefix_fields)) = def.non_enum_variant().fields.raw.split_last() else {
292        return DenseBitSet::new_empty(num_params);
293    };
294
295    let mut unsizing_params = DenseBitSet::new_empty(num_params);
296    for arg in tcx.type_of(tail_field.did).instantiate_identity().walk() {
297        if let Some(i) = maybe_unsizing_param_idx(arg) {
298            unsizing_params.insert(i);
299        }
300    }
301
302    // Ensure none of the other fields mention the parameters used
303    // in unsizing.
304    for field in prefix_fields {
305        for arg in tcx.type_of(field.did).instantiate_identity().walk() {
306            if let Some(i) = maybe_unsizing_param_idx(arg) {
307                unsizing_params.remove(i);
308            }
309        }
310    }
311
312    unsizing_params
313}
314
315pub(crate) fn provide(providers: &mut Providers) {
316    *providers = Providers {
317        asyncness,
318        adt_sized_constraint,
319        param_env,
320        param_env_normalized_for_post_analysis,
321        defaultness,
322        unsizing_params_for_adt,
323        ..*providers
324    };
325}
rustc_ty_utils/ty.rs

rustc_ty_utils/
ty.rs
