1 use rustc_data_structures::fx::FxIndexSet;
3 use rustc_hir::def_id::DefId;
4 use rustc_middle::ty::subst::Subst;
5 use rustc_middle::ty::{self, Binder, Predicate, PredicateKind, ToPredicate, Ty, TyCtxt};
6 use rustc_span::{sym, Span};
7 use rustc_trait_selection::traits;
9 fn sized_constraint_for_ty<'tcx>(
16 let result = match ty.kind() {
17 Bool | Char | Int(..) | Uint(..) | Float(..) | RawPtr(..) | Ref(..) | FnDef(..)
18 | FnPtr(_) | Array(..) | Closure(..) | Generator(..) | Never => vec![],
20 Str | Dynamic(..) | Slice(_) | Foreign(..) | Error(_) | GeneratorWitness(..) => {
21 // these are never sized - return the target type
25 Tuple(ref tys) => match tys.last() {
27 Some(ty) => sized_constraint_for_ty(tcx, adtdef, ty.expect_ty()),
32 let adt_tys = adt.sized_constraint(tcx);
33 debug!("sized_constraint_for_ty({:?}) intermediate = {:?}", ty, adt_tys);
36 .map(|ty| ty.subst(tcx, substs))
37 .flat_map(|ty| sized_constraint_for_ty(tcx, adtdef, ty))
41 Projection(..) | Opaque(..) => {
42 // must calculate explicitly.
43 // FIXME: consider special-casing always-Sized projections
48 // perf hack: if there is a `T: Sized` bound, then
49 // we know that `T` is Sized and do not need to check
52 let sized_trait = match tcx.lang_items().sized_trait() {
56 let sized_predicate = ty::Binder::dummy(ty::TraitRef {
58 substs: tcx.mk_substs_trait(ty, &[]),
62 let predicates = tcx.predicates_of(adtdef.did).predicates;
63 if predicates.iter().any(|(p, _)| *p == sized_predicate) { vec![] } else { vec![ty] }
66 Placeholder(..) | Bound(..) | Infer(..) => {
67 bug!("unexpected type `{:?}` in sized_constraint_for_ty", ty)
70 debug!("sized_constraint_for_ty({:?}) = {:?}", ty, result);
74 fn impl_defaultness(tcx: TyCtxt<'_>, def_id: DefId) -> hir::Defaultness {
75 let item = tcx.hir().expect_item(def_id.expect_local());
76 if let hir::ItemKind::Impl(impl_) = &item.kind {
79 bug!("`impl_defaultness` called on {:?}", item);
83 fn impl_constness(tcx: TyCtxt<'_>, def_id: DefId) -> hir::Constness {
84 let item = tcx.hir().expect_item(def_id.expect_local());
85 if let hir::ItemKind::Impl(impl_) = &item.kind {
88 bug!("`impl_constness` called on {:?}", item);
92 /// Calculates the `Sized` constraint.
94 /// In fact, there are only a few options for the types in the constraint:
95 /// - an obviously-unsized type
96 /// - a type parameter or projection whose Sizedness can't be known
97 /// - a tuple of type parameters or projections, if there are multiple
99 /// - an Error, if a type contained itself. The representability
100 /// check should catch this case.
101 fn adt_sized_constraint(tcx: TyCtxt<'_>, def_id: DefId) -> ty::AdtSizedConstraint<'_> {
102 let def = tcx.adt_def(def_id);
104 let result = tcx.mk_type_list(
107 .flat_map(|v| v.fields.last())
108 .flat_map(|f| sized_constraint_for_ty(tcx, def, tcx.type_of(f.did))),
111 debug!("adt_sized_constraint: {:?} => {:?}", def, result);
113 ty::AdtSizedConstraint(result)
116 fn def_ident_span(tcx: TyCtxt<'_>, def_id: DefId) -> Option<Span> {
118 .get_if_local(def_id)
119 .and_then(|node| match node {
120 // A `Ctor` doesn't have an identifier itself, but its parent
121 // struct/variant does. Compare with `hir::Map::opt_span`.
122 hir::Node::Ctor(ctor) => ctor
124 .and_then(|ctor_id| tcx.hir().find(tcx.hir().get_parent_node(ctor_id)))
125 .and_then(|parent| parent.ident()),
128 .map(|ident| ident.span)
131 /// See `ParamEnv` struct definition for details.
132 #[instrument(level = "debug", skip(tcx))]
133 fn param_env(tcx: TyCtxt<'_>, def_id: DefId) -> ty::ParamEnv<'_> {
134 // The param_env of an impl Trait type is its defining function's param_env
135 if let Some(parent) = ty::is_impl_trait_defn(tcx, def_id) {
136 return param_env(tcx, parent.to_def_id());
138 // Compute the bounds on Self and the type parameters.
140 let ty::InstantiatedPredicates { mut predicates, .. } =
141 tcx.predicates_of(def_id).instantiate_identity(tcx);
143 // Finally, we have to normalize the bounds in the environment, in
144 // case they contain any associated type projections. This process
145 // can yield errors if the put in illegal associated types, like
146 // `<i32 as Foo>::Bar` where `i32` does not implement `Foo`. We
147 // report these errors right here; this doesn't actually feel
148 // right to me, because constructing the environment feels like a
149 // kind of an "idempotent" action, but I'm not sure where would be
150 // a better place. In practice, we construct environments for
151 // every fn once during type checking, and we'll abort if there
152 // are any errors at that point, so after type checking you can be
153 // sure that this will succeed without errors anyway.
155 if tcx.sess.opts.debugging_opts.chalk {
156 let environment = well_formed_types_in_env(tcx, def_id);
157 predicates.extend(environment);
160 let local_did = def_id.as_local();
161 let hir_id = local_did.map(|def_id| tcx.hir().local_def_id_to_hir_id(def_id));
163 let constness = match hir_id {
164 Some(hir_id) => match tcx.hir().get(hir_id) {
165 hir::Node::TraitItem(hir::TraitItem { kind: hir::TraitItemKind::Fn(..), .. })
166 if tcx.has_attr(def_id, sym::default_method_body_is_const) =>
168 hir::Constness::Const
171 hir::Node::Item(hir::Item { kind: hir::ItemKind::Const(..), .. })
172 | hir::Node::Item(hir::Item { kind: hir::ItemKind::Static(..), .. })
173 | hir::Node::TraitItem(hir::TraitItem {
174 kind: hir::TraitItemKind::Const(..), ..
176 | hir::Node::AnonConst(_)
177 | hir::Node::ImplItem(hir::ImplItem { kind: hir::ImplItemKind::Const(..), .. })
178 | hir::Node::ImplItem(hir::ImplItem {
180 hir::ImplItemKind::Fn(
182 header: hir::FnHeader { constness: hir::Constness::Const, .. },
188 }) => hir::Constness::Const,
190 hir::Node::ImplItem(hir::ImplItem {
191 kind: hir::ImplItemKind::TyAlias(..) | hir::ImplItemKind::Fn(..),
194 let parent_hir_id = tcx.hir().get_parent_node(hir_id);
195 match tcx.hir().get(parent_hir_id) {
196 hir::Node::Item(hir::Item {
197 kind: hir::ItemKind::Impl(hir::Impl { constness, .. }),
201 tcx.def_span(parent_hir_id.owner),
202 "impl item's parent node is not an impl",
207 hir::Node::Item(hir::Item {
209 hir::ItemKind::Fn(hir::FnSig { header: hir::FnHeader { constness, .. }, .. }, ..),
212 | hir::Node::TraitItem(hir::TraitItem {
214 hir::TraitItemKind::Fn(
215 hir::FnSig { header: hir::FnHeader { constness, .. }, .. },
220 | hir::Node::Item(hir::Item {
221 kind: hir::ItemKind::Impl(hir::Impl { constness, .. }),
225 _ => hir::Constness::NotConst,
227 None => hir::Constness::NotConst,
230 let unnormalized_env = ty::ParamEnv::new(
231 tcx.intern_predicates(&predicates),
232 traits::Reveal::UserFacing,
236 let body_id = hir_id.map_or(hir::CRATE_HIR_ID, |id| {
237 tcx.hir().maybe_body_owned_by(id).map_or(id, |body| body.hir_id)
239 let cause = traits::ObligationCause::misc(tcx.def_span(def_id), body_id);
240 traits::normalize_param_env_or_error(tcx, def_id, unnormalized_env, cause)
243 /// Elaborate the environment.
245 /// Collect a list of `Predicate`'s used for building the `ParamEnv`. Adds `TypeWellFormedFromEnv`'s
246 /// that are assumed to be well-formed (because they come from the environment).
248 /// Used only in chalk mode.
249 fn well_formed_types_in_env<'tcx>(
252 ) -> &'tcx ty::List<Predicate<'tcx>> {
253 use rustc_hir::{ForeignItemKind, ImplItemKind, ItemKind, Node, TraitItemKind};
254 use rustc_middle::ty::subst::GenericArgKind;
256 debug!("environment(def_id = {:?})", def_id);
258 // The environment of an impl Trait type is its defining function's environment.
259 if let Some(parent) = ty::is_impl_trait_defn(tcx, def_id) {
260 return well_formed_types_in_env(tcx, parent.to_def_id());
263 // Compute the bounds on `Self` and the type parameters.
264 let ty::InstantiatedPredicates { predicates, .. } =
265 tcx.predicates_of(def_id).instantiate_identity(tcx);
267 let clauses = predicates.into_iter();
269 if !def_id.is_local() {
270 return ty::List::empty();
272 let node = tcx.hir().get_by_def_id(def_id.expect_local());
281 let node_kind = match node {
282 Node::TraitItem(item) => match item.kind {
283 TraitItemKind::Fn(..) => NodeKind::Fn,
284 _ => NodeKind::Other,
287 Node::ImplItem(item) => match item.kind {
288 ImplItemKind::Fn(..) => NodeKind::Fn,
289 _ => NodeKind::Other,
292 Node::Item(item) => match item.kind {
293 ItemKind::Impl(hir::Impl { of_trait: Some(_), .. }) => NodeKind::TraitImpl,
294 ItemKind::Impl(hir::Impl { of_trait: None, .. }) => NodeKind::InherentImpl,
295 ItemKind::Fn(..) => NodeKind::Fn,
296 _ => NodeKind::Other,
299 Node::ForeignItem(item) => match item.kind {
300 ForeignItemKind::Fn(..) => NodeKind::Fn,
301 _ => NodeKind::Other,
305 _ => NodeKind::Other,
308 // FIXME(eddyb) isn't the unordered nature of this a hazard?
309 let mut inputs = FxIndexSet::default();
312 // In a trait impl, we assume that the header trait ref and all its
313 // constituents are well-formed.
314 NodeKind::TraitImpl => {
315 let trait_ref = tcx.impl_trait_ref(def_id).expect("not an impl");
317 // FIXME(chalk): this has problems because of late-bound regions
318 //inputs.extend(trait_ref.substs.iter().flat_map(|arg| arg.walk()));
319 inputs.extend(trait_ref.substs.iter());
322 // In an inherent impl, we assume that the receiver type and all its
323 // constituents are well-formed.
324 NodeKind::InherentImpl => {
325 let self_ty = tcx.type_of(def_id);
326 inputs.extend(self_ty.walk());
329 // In an fn, we assume that the arguments and all their constituents are
332 let fn_sig = tcx.fn_sig(def_id);
333 let fn_sig = tcx.liberate_late_bound_regions(def_id, fn_sig);
335 inputs.extend(fn_sig.inputs().iter().flat_map(|ty| ty.walk()));
338 NodeKind::Other => (),
340 let input_clauses = inputs.into_iter().filter_map(|arg| {
342 GenericArgKind::Type(ty) => {
343 let binder = Binder::dummy(PredicateKind::TypeWellFormedFromEnv(ty));
344 Some(tcx.mk_predicate(binder))
347 // FIXME(eddyb) no WF conditions from lifetimes?
348 GenericArgKind::Lifetime(_) => None,
350 // FIXME(eddyb) support const generics in Chalk
351 GenericArgKind::Const(_) => None,
355 tcx.mk_predicates(clauses.chain(input_clauses))
358 fn param_env_reveal_all_normalized(tcx: TyCtxt<'_>, def_id: DefId) -> ty::ParamEnv<'_> {
359 tcx.param_env(def_id).with_reveal_all_normalized(tcx)
362 fn instance_def_size_estimate<'tcx>(
364 instance_def: ty::InstanceDef<'tcx>,
369 InstanceDef::Item(..) | InstanceDef::DropGlue(..) => {
370 let mir = tcx.instance_mir(instance_def);
371 mir.basic_blocks().iter().map(|bb| bb.statements.len() + 1).sum()
373 // Estimate the size of other compiler-generated shims to be 1.
378 /// If `def_id` is an issue 33140 hack impl, returns its self type; otherwise, returns `None`.
380 /// See [`ty::ImplOverlapKind::Issue33140`] for more details.
381 fn issue33140_self_ty(tcx: TyCtxt<'_>, def_id: DefId) -> Option<Ty<'_>> {
382 debug!("issue33140_self_ty({:?})", def_id);
385 .impl_trait_ref(def_id)
386 .unwrap_or_else(|| bug!("issue33140_self_ty called on inherent impl {:?}", def_id));
388 debug!("issue33140_self_ty({:?}), trait-ref={:?}", def_id, trait_ref);
390 let is_marker_like = tcx.impl_polarity(def_id) == ty::ImplPolarity::Positive
391 && tcx.associated_item_def_ids(trait_ref.def_id).is_empty();
393 // Check whether these impls would be ok for a marker trait.
395 debug!("issue33140_self_ty - not marker-like!");
399 // impl must be `impl Trait for dyn Marker1 + Marker2 + ...`
400 if trait_ref.substs.len() != 1 {
401 debug!("issue33140_self_ty - impl has substs!");
405 let predicates = tcx.predicates_of(def_id);
406 if predicates.parent.is_some() || !predicates.predicates.is_empty() {
407 debug!("issue33140_self_ty - impl has predicates {:?}!", predicates);
411 let self_ty = trait_ref.self_ty();
412 let self_ty_matches = match self_ty.kind() {
413 ty::Dynamic(ref data, ty::ReStatic) => data.principal().is_none(),
418 debug!("issue33140_self_ty - MATCHES!");
421 debug!("issue33140_self_ty - non-matching self type");
426 /// Check if a function is async.
427 fn asyncness(tcx: TyCtxt<'_>, def_id: DefId) -> hir::IsAsync {
428 let node = tcx.hir().get_by_def_id(def_id.expect_local());
430 let fn_kind = node.fn_kind().unwrap_or_else(|| {
431 bug!("asyncness: expected fn-like node but got `{:?}`", def_id);
437 /// Don't call this directly: use ``tcx.conservative_is_privately_uninhabited`` instead.
438 #[instrument(level = "debug", skip(tcx))]
439 pub fn conservative_is_privately_uninhabited_raw<'tcx>(
441 param_env_and: ty::ParamEnvAnd<'tcx, Ty<'tcx>>,
443 let (param_env, ty) = param_env_and.into_parts();
446 debug!("ty::Never =>");
449 ty::Adt(def, _) if def.is_union() => {
450 debug!("ty::Adt(def, _) if def.is_union() =>");
451 // For now, `union`s are never considered uninhabited.
454 ty::Adt(def, substs) => {
455 debug!("ty::Adt(def, _) if def.is_not_union() =>");
456 // Any ADT is uninhabited if either:
457 // (a) It has no variants (i.e. an empty `enum`);
458 // (b) Each of its variants (a single one in the case of a `struct`) has at least
459 // one uninhabited field.
460 def.variants.iter().all(|var| {
461 var.fields.iter().any(|field| {
462 let ty = tcx.type_of(field.did).subst(tcx, substs);
463 tcx.conservative_is_privately_uninhabited(param_env.and(ty))
468 debug!("ty::Tuple(..) =>");
469 ty.tuple_fields().any(|ty| tcx.conservative_is_privately_uninhabited(param_env.and(ty)))
471 ty::Array(ty, len) => {
472 debug!("ty::Array(ty, len) =>");
473 match len.try_eval_usize(tcx, param_env) {
474 Some(0) | None => false,
475 // If the array is definitely non-empty, it's uninhabited if
476 // the type of its elements is uninhabited.
477 Some(1..) => tcx.conservative_is_privately_uninhabited(param_env.and(ty)),
481 debug!("ty::Ref(..) =>");
482 // References to uninitialised memory is valid for any type, including
483 // uninhabited types, in unsafe code, so we treat all references as
494 pub fn provide(providers: &mut ty::query::Providers) {
495 *providers = ty::query::Providers {
497 adt_sized_constraint,
500 param_env_reveal_all_normalized,
501 instance_def_size_estimate,
505 conservative_is_privately_uninhabited: conservative_is_privately_uninhabited_raw,