]> git.lizzy.rs Git - rust.git/blob - compiler/rustc_ty_utils/src/ty.rs
Rollup merge of #89876 - AlexApps99:const_ops, r=oli-obk
[rust.git] / compiler / rustc_ty_utils / src / ty.rs
1 use rustc_data_structures::fx::FxIndexSet;
2 use rustc_hir as hir;
3 use rustc_hir::def_id::{DefId, LocalDefId};
4 use rustc_middle::ty::subst::Subst;
5 use rustc_middle::ty::{
6     self, Binder, Predicate, PredicateKind, ToPredicate, Ty, TyCtxt, WithConstness,
7 };
8 use rustc_span::Span;
9 use rustc_trait_selection::traits;
10
11 fn sized_constraint_for_ty<'tcx>(
12     tcx: TyCtxt<'tcx>,
13     adtdef: &ty::AdtDef,
14     ty: Ty<'tcx>,
15 ) -> Vec<Ty<'tcx>> {
16     use ty::TyKind::*;
17
18     let result = match ty.kind() {
19         Bool | Char | Int(..) | Uint(..) | Float(..) | RawPtr(..) | Ref(..) | FnDef(..)
20         | FnPtr(_) | Array(..) | Closure(..) | Generator(..) | Never => vec![],
21
22         Str | Dynamic(..) | Slice(_) | Foreign(..) | Error(_) | GeneratorWitness(..) => {
23             // these are never sized - return the target type
24             vec![ty]
25         }
26
27         Tuple(ref tys) => match tys.last() {
28             None => vec![],
29             Some(ty) => sized_constraint_for_ty(tcx, adtdef, ty.expect_ty()),
30         },
31
32         Adt(adt, substs) => {
33             // recursive case
34             let adt_tys = adt.sized_constraint(tcx);
35             debug!("sized_constraint_for_ty({:?}) intermediate = {:?}", ty, adt_tys);
36             adt_tys
37                 .iter()
38                 .map(|ty| ty.subst(tcx, substs))
39                 .flat_map(|ty| sized_constraint_for_ty(tcx, adtdef, ty))
40                 .collect()
41         }
42
43         Projection(..) | Opaque(..) => {
44             // must calculate explicitly.
45             // FIXME: consider special-casing always-Sized projections
46             vec![ty]
47         }
48
49         Param(..) => {
50             // perf hack: if there is a `T: Sized` bound, then
51             // we know that `T` is Sized and do not need to check
52             // it on the impl.
53
54             let sized_trait = match tcx.lang_items().sized_trait() {
55                 Some(x) => x,
56                 _ => return vec![ty],
57             };
58             let sized_predicate = ty::Binder::dummy(ty::TraitRef {
59                 def_id: sized_trait,
60                 substs: tcx.mk_substs_trait(ty, &[]),
61             })
62             .without_const()
63             .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
76 fn associated_item_from_trait_item_ref(
77     tcx: TyCtxt<'_>,
78     parent_def_id: LocalDefId,
79     trait_item_ref: &hir::TraitItemRef,
80 ) -> ty::AssocItem {
81     let def_id = trait_item_ref.id.def_id;
82     let (kind, has_self) = match trait_item_ref.kind {
83         hir::AssocItemKind::Const => (ty::AssocKind::Const, false),
84         hir::AssocItemKind::Fn { has_self } => (ty::AssocKind::Fn, has_self),
85         hir::AssocItemKind::Type => (ty::AssocKind::Type, false),
86     };
87
88     ty::AssocItem {
89         ident: trait_item_ref.ident,
90         kind,
91         vis: tcx.visibility(def_id),
92         defaultness: trait_item_ref.defaultness,
93         def_id: def_id.to_def_id(),
94         container: ty::TraitContainer(parent_def_id.to_def_id()),
95         fn_has_self_parameter: has_self,
96     }
97 }
98
99 fn associated_item_from_impl_item_ref(
100     tcx: TyCtxt<'_>,
101     parent_def_id: LocalDefId,
102     impl_item_ref: &hir::ImplItemRef,
103 ) -> ty::AssocItem {
104     let def_id = impl_item_ref.id.def_id;
105     let (kind, has_self) = match impl_item_ref.kind {
106         hir::AssocItemKind::Const => (ty::AssocKind::Const, false),
107         hir::AssocItemKind::Fn { has_self } => (ty::AssocKind::Fn, has_self),
108         hir::AssocItemKind::Type => (ty::AssocKind::Type, false),
109     };
110
111     ty::AssocItem {
112         ident: impl_item_ref.ident,
113         kind,
114         vis: tcx.visibility(def_id),
115         defaultness: impl_item_ref.defaultness,
116         def_id: def_id.to_def_id(),
117         container: ty::ImplContainer(parent_def_id.to_def_id()),
118         fn_has_self_parameter: has_self,
119     }
120 }
121
122 fn associated_item(tcx: TyCtxt<'_>, def_id: DefId) -> ty::AssocItem {
123     let id = tcx.hir().local_def_id_to_hir_id(def_id.expect_local());
124     let parent_id = tcx.hir().get_parent_item(id);
125     let parent_def_id = tcx.hir().local_def_id(parent_id);
126     let parent_item = tcx.hir().expect_item(parent_id);
127     match parent_item.kind {
128         hir::ItemKind::Impl(ref impl_) => {
129             if let Some(impl_item_ref) =
130                 impl_.items.iter().find(|i| i.id.def_id.to_def_id() == def_id)
131             {
132                 let assoc_item =
133                     associated_item_from_impl_item_ref(tcx, parent_def_id, impl_item_ref);
134                 debug_assert_eq!(assoc_item.def_id, def_id);
135                 return assoc_item;
136             }
137         }
138
139         hir::ItemKind::Trait(.., ref trait_item_refs) => {
140             if let Some(trait_item_ref) =
141                 trait_item_refs.iter().find(|i| i.id.def_id.to_def_id() == def_id)
142             {
143                 let assoc_item =
144                     associated_item_from_trait_item_ref(tcx, parent_def_id, trait_item_ref);
145                 debug_assert_eq!(assoc_item.def_id, def_id);
146                 return assoc_item;
147             }
148         }
149
150         _ => {}
151     }
152
153     span_bug!(
154         parent_item.span,
155         "unexpected parent of trait or impl item or item not found: {:?}",
156         parent_item.kind
157     )
158 }
159
160 fn impl_defaultness(tcx: TyCtxt<'_>, def_id: DefId) -> hir::Defaultness {
161     let hir_id = tcx.hir().local_def_id_to_hir_id(def_id.expect_local());
162     let item = tcx.hir().expect_item(hir_id);
163     if let hir::ItemKind::Impl(impl_) = &item.kind {
164         impl_.defaultness
165     } else {
166         bug!("`impl_defaultness` called on {:?}", item);
167     }
168 }
169
170 fn impl_constness(tcx: TyCtxt<'_>, def_id: DefId) -> hir::Constness {
171     let hir_id = tcx.hir().local_def_id_to_hir_id(def_id.expect_local());
172     let item = tcx.hir().expect_item(hir_id);
173     if let hir::ItemKind::Impl(impl_) = &item.kind {
174         impl_.constness
175     } else {
176         bug!("`impl_constness` called on {:?}", item);
177     }
178 }
179
180 /// Calculates the `Sized` constraint.
181 ///
182 /// In fact, there are only a few options for the types in the constraint:
183 ///     - an obviously-unsized type
184 ///     - a type parameter or projection whose Sizedness can't be known
185 ///     - a tuple of type parameters or projections, if there are multiple
186 ///       such.
187 ///     - an Error, if a type contained itself. The representability
188 ///       check should catch this case.
189 fn adt_sized_constraint(tcx: TyCtxt<'_>, def_id: DefId) -> ty::AdtSizedConstraint<'_> {
190     let def = tcx.adt_def(def_id);
191
192     let result = tcx.mk_type_list(
193         def.variants
194             .iter()
195             .flat_map(|v| v.fields.last())
196             .flat_map(|f| sized_constraint_for_ty(tcx, def, tcx.type_of(f.did))),
197     );
198
199     debug!("adt_sized_constraint: {:?} => {:?}", def, result);
200
201     ty::AdtSizedConstraint(result)
202 }
203
204 fn associated_item_def_ids(tcx: TyCtxt<'_>, def_id: DefId) -> &[DefId] {
205     let id = tcx.hir().local_def_id_to_hir_id(def_id.expect_local());
206     let item = tcx.hir().expect_item(id);
207     match item.kind {
208         hir::ItemKind::Trait(.., ref trait_item_refs) => tcx.arena.alloc_from_iter(
209             trait_item_refs.iter().map(|trait_item_ref| trait_item_ref.id.def_id.to_def_id()),
210         ),
211         hir::ItemKind::Impl(ref impl_) => tcx.arena.alloc_from_iter(
212             impl_.items.iter().map(|impl_item_ref| impl_item_ref.id.def_id.to_def_id()),
213         ),
214         hir::ItemKind::TraitAlias(..) => &[],
215         _ => span_bug!(item.span, "associated_item_def_ids: not impl or trait"),
216     }
217 }
218
219 fn associated_items(tcx: TyCtxt<'_>, def_id: DefId) -> ty::AssocItems<'_> {
220     let items = tcx.associated_item_def_ids(def_id).iter().map(|did| tcx.associated_item(*did));
221     ty::AssocItems::new(items)
222 }
223
224 fn def_ident_span(tcx: TyCtxt<'_>, def_id: DefId) -> Option<Span> {
225     tcx.hir()
226         .get_if_local(def_id)
227         .and_then(|node| match node {
228             // A `Ctor` doesn't have an identifier itself, but its parent
229             // struct/variant does. Compare with `hir::Map::opt_span`.
230             hir::Node::Ctor(ctor) => ctor
231                 .ctor_hir_id()
232                 .and_then(|ctor_id| tcx.hir().find(tcx.hir().get_parent_node(ctor_id)))
233                 .and_then(|parent| parent.ident()),
234             _ => node.ident(),
235         })
236         .map(|ident| ident.span)
237 }
238
239 /// If the given `DefId` describes an item belonging to a trait,
240 /// returns the `DefId` of the trait that the trait item belongs to;
241 /// otherwise, returns `None`.
242 fn trait_of_item(tcx: TyCtxt<'_>, def_id: DefId) -> Option<DefId> {
243     tcx.opt_associated_item(def_id).and_then(|associated_item| match associated_item.container {
244         ty::TraitContainer(def_id) => Some(def_id),
245         ty::ImplContainer(_) => None,
246     })
247 }
248
249 /// See `ParamEnv` struct definition for details.
250 #[instrument(level = "debug", skip(tcx))]
251 fn param_env(tcx: TyCtxt<'_>, def_id: DefId) -> ty::ParamEnv<'_> {
252     // The param_env of an impl Trait type is its defining function's param_env
253     if let Some(parent) = ty::is_impl_trait_defn(tcx, def_id) {
254         return param_env(tcx, parent);
255     }
256     // Compute the bounds on Self and the type parameters.
257
258     let ty::InstantiatedPredicates { mut predicates, .. } =
259         tcx.predicates_of(def_id).instantiate_identity(tcx);
260
261     // Finally, we have to normalize the bounds in the environment, in
262     // case they contain any associated type projections. This process
263     // can yield errors if the put in illegal associated types, like
264     // `<i32 as Foo>::Bar` where `i32` does not implement `Foo`. We
265     // report these errors right here; this doesn't actually feel
266     // right to me, because constructing the environment feels like a
267     // kind of an "idempotent" action, but I'm not sure where would be
268     // a better place. In practice, we construct environments for
269     // every fn once during type checking, and we'll abort if there
270     // are any errors at that point, so after type checking you can be
271     // sure that this will succeed without errors anyway.
272
273     if tcx.sess.opts.debugging_opts.chalk {
274         let environment = well_formed_types_in_env(tcx, def_id);
275         predicates.extend(environment);
276     }
277
278     // It's important that we include the default substs in unevaluated
279     // constants, since `Unevaluated` instances in predicates whose substs are None
280     // can lead to "duplicate" caller bounds candidates during trait selection,
281     // duplicate in the sense that both have their default substs, but the
282     // candidate that resulted from a superpredicate still uses `None` in its
283     // `substs_` field of `Unevaluated` to indicate that it has its default substs,
284     // whereas the other candidate has `substs_: Some(default_substs)`, see
285     // issue #89334
286     predicates = tcx.expose_default_const_substs(predicates);
287
288     let unnormalized_env =
289         ty::ParamEnv::new(tcx.intern_predicates(&predicates), traits::Reveal::UserFacing);
290
291     debug!("unnormalized_env caller bounds: {:?}", unnormalized_env.caller_bounds());
292     let body_id = def_id
293         .as_local()
294         .map(|def_id| tcx.hir().local_def_id_to_hir_id(def_id))
295         .map_or(hir::CRATE_HIR_ID, |id| {
296             tcx.hir().maybe_body_owned_by(id).map_or(id, |body| body.hir_id)
297         });
298     let cause = traits::ObligationCause::misc(tcx.def_span(def_id), body_id);
299     traits::normalize_param_env_or_error(tcx, def_id, unnormalized_env, cause)
300 }
301
302 /// Elaborate the environment.
303 ///
304 /// Collect a list of `Predicate`'s used for building the `ParamEnv`. Adds `TypeWellFormedFromEnv`'s
305 /// that are assumed to be well-formed (because they come from the environment).
306 ///
307 /// Used only in chalk mode.
308 fn well_formed_types_in_env<'tcx>(
309     tcx: TyCtxt<'tcx>,
310     def_id: DefId,
311 ) -> &'tcx ty::List<Predicate<'tcx>> {
312     use rustc_hir::{ForeignItemKind, ImplItemKind, ItemKind, Node, TraitItemKind};
313     use rustc_middle::ty::subst::GenericArgKind;
314
315     debug!("environment(def_id = {:?})", def_id);
316
317     // The environment of an impl Trait type is its defining function's environment.
318     if let Some(parent) = ty::is_impl_trait_defn(tcx, def_id) {
319         return well_formed_types_in_env(tcx, parent);
320     }
321
322     // Compute the bounds on `Self` and the type parameters.
323     let ty::InstantiatedPredicates { predicates, .. } =
324         tcx.predicates_of(def_id).instantiate_identity(tcx);
325
326     let clauses = predicates.into_iter();
327
328     if !def_id.is_local() {
329         return ty::List::empty();
330     }
331     let hir_id = tcx.hir().local_def_id_to_hir_id(def_id.expect_local());
332     let node = tcx.hir().get(hir_id);
333
334     enum NodeKind {
335         TraitImpl,
336         InherentImpl,
337         Fn,
338         Other,
339     }
340
341     let node_kind = match node {
342         Node::TraitItem(item) => match item.kind {
343             TraitItemKind::Fn(..) => NodeKind::Fn,
344             _ => NodeKind::Other,
345         },
346
347         Node::ImplItem(item) => match item.kind {
348             ImplItemKind::Fn(..) => NodeKind::Fn,
349             _ => NodeKind::Other,
350         },
351
352         Node::Item(item) => match item.kind {
353             ItemKind::Impl(hir::Impl { of_trait: Some(_), .. }) => NodeKind::TraitImpl,
354             ItemKind::Impl(hir::Impl { of_trait: None, .. }) => NodeKind::InherentImpl,
355             ItemKind::Fn(..) => NodeKind::Fn,
356             _ => NodeKind::Other,
357         },
358
359         Node::ForeignItem(item) => match item.kind {
360             ForeignItemKind::Fn(..) => NodeKind::Fn,
361             _ => NodeKind::Other,
362         },
363
364         // FIXME: closures?
365         _ => NodeKind::Other,
366     };
367
368     // FIXME(eddyb) isn't the unordered nature of this a hazard?
369     let mut inputs = FxIndexSet::default();
370
371     match node_kind {
372         // In a trait impl, we assume that the header trait ref and all its
373         // constituents are well-formed.
374         NodeKind::TraitImpl => {
375             let trait_ref = tcx.impl_trait_ref(def_id).expect("not an impl");
376
377             // FIXME(chalk): this has problems because of late-bound regions
378             //inputs.extend(trait_ref.substs.iter().flat_map(|arg| arg.walk()));
379             inputs.extend(trait_ref.substs.iter());
380         }
381
382         // In an inherent impl, we assume that the receiver type and all its
383         // constituents are well-formed.
384         NodeKind::InherentImpl => {
385             let self_ty = tcx.type_of(def_id);
386             inputs.extend(self_ty.walk(tcx));
387         }
388
389         // In an fn, we assume that the arguments and all their constituents are
390         // well-formed.
391         NodeKind::Fn => {
392             let fn_sig = tcx.fn_sig(def_id);
393             let fn_sig = tcx.liberate_late_bound_regions(def_id, fn_sig);
394
395             inputs.extend(fn_sig.inputs().iter().flat_map(|ty| ty.walk(tcx)));
396         }
397
398         NodeKind::Other => (),
399     }
400     let input_clauses = inputs.into_iter().filter_map(|arg| {
401         match arg.unpack() {
402             GenericArgKind::Type(ty) => {
403                 let binder = Binder::dummy(PredicateKind::TypeWellFormedFromEnv(ty));
404                 Some(tcx.mk_predicate(binder))
405             }
406
407             // FIXME(eddyb) no WF conditions from lifetimes?
408             GenericArgKind::Lifetime(_) => None,
409
410             // FIXME(eddyb) support const generics in Chalk
411             GenericArgKind::Const(_) => None,
412         }
413     });
414
415     tcx.mk_predicates(clauses.chain(input_clauses))
416 }
417
418 fn param_env_reveal_all_normalized(tcx: TyCtxt<'_>, def_id: DefId) -> ty::ParamEnv<'_> {
419     tcx.param_env(def_id).with_reveal_all_normalized(tcx)
420 }
421
422 fn instance_def_size_estimate<'tcx>(
423     tcx: TyCtxt<'tcx>,
424     instance_def: ty::InstanceDef<'tcx>,
425 ) -> usize {
426     use ty::InstanceDef;
427
428     match instance_def {
429         InstanceDef::Item(..) | InstanceDef::DropGlue(..) => {
430             let mir = tcx.instance_mir(instance_def);
431             mir.basic_blocks().iter().map(|bb| bb.statements.len() + 1).sum()
432         }
433         // Estimate the size of other compiler-generated shims to be 1.
434         _ => 1,
435     }
436 }
437
438 /// If `def_id` is an issue 33140 hack impl, returns its self type; otherwise, returns `None`.
439 ///
440 /// See [`ty::ImplOverlapKind::Issue33140`] for more details.
441 fn issue33140_self_ty(tcx: TyCtxt<'_>, def_id: DefId) -> Option<Ty<'_>> {
442     debug!("issue33140_self_ty({:?})", def_id);
443
444     let trait_ref = tcx
445         .impl_trait_ref(def_id)
446         .unwrap_or_else(|| bug!("issue33140_self_ty called on inherent impl {:?}", def_id));
447
448     debug!("issue33140_self_ty({:?}), trait-ref={:?}", def_id, trait_ref);
449
450     let is_marker_like = tcx.impl_polarity(def_id) == ty::ImplPolarity::Positive
451         && tcx.associated_item_def_ids(trait_ref.def_id).is_empty();
452
453     // Check whether these impls would be ok for a marker trait.
454     if !is_marker_like {
455         debug!("issue33140_self_ty - not marker-like!");
456         return None;
457     }
458
459     // impl must be `impl Trait for dyn Marker1 + Marker2 + ...`
460     if trait_ref.substs.len() != 1 {
461         debug!("issue33140_self_ty - impl has substs!");
462         return None;
463     }
464
465     let predicates = tcx.predicates_of(def_id);
466     if predicates.parent.is_some() || !predicates.predicates.is_empty() {
467         debug!("issue33140_self_ty - impl has predicates {:?}!", predicates);
468         return None;
469     }
470
471     let self_ty = trait_ref.self_ty();
472     let self_ty_matches = match self_ty.kind() {
473         ty::Dynamic(ref data, ty::ReStatic) => data.principal().is_none(),
474         _ => false,
475     };
476
477     if self_ty_matches {
478         debug!("issue33140_self_ty - MATCHES!");
479         Some(self_ty)
480     } else {
481         debug!("issue33140_self_ty - non-matching self type");
482         None
483     }
484 }
485
486 /// Check if a function is async.
487 fn asyncness(tcx: TyCtxt<'_>, def_id: DefId) -> hir::IsAsync {
488     let hir_id = tcx.hir().local_def_id_to_hir_id(def_id.expect_local());
489
490     let node = tcx.hir().get(hir_id);
491
492     let fn_kind = node.fn_kind().unwrap_or_else(|| {
493         bug!("asyncness: expected fn-like node but got `{:?}`", def_id);
494     });
495
496     fn_kind.asyncness()
497 }
498
499 /// Don't call this directly: use ``tcx.conservative_is_privately_uninhabited`` instead.
500 #[instrument(level = "debug", skip(tcx))]
501 pub fn conservative_is_privately_uninhabited_raw<'tcx>(
502     tcx: TyCtxt<'tcx>,
503     param_env_and: ty::ParamEnvAnd<'tcx, Ty<'tcx>>,
504 ) -> bool {
505     let (param_env, ty) = param_env_and.into_parts();
506     match ty.kind() {
507         ty::Never => {
508             debug!("ty::Never =>");
509             true
510         }
511         ty::Adt(def, _) if def.is_union() => {
512             debug!("ty::Adt(def, _) if def.is_union() =>");
513             // For now, `union`s are never considered uninhabited.
514             false
515         }
516         ty::Adt(def, substs) => {
517             debug!("ty::Adt(def, _) if def.is_not_union() =>");
518             // Any ADT is uninhabited if either:
519             // (a) It has no variants (i.e. an empty `enum`);
520             // (b) Each of its variants (a single one in the case of a `struct`) has at least
521             //     one uninhabited field.
522             def.variants.iter().all(|var| {
523                 var.fields.iter().any(|field| {
524                     let ty = tcx.type_of(field.did).subst(tcx, substs);
525                     tcx.conservative_is_privately_uninhabited(param_env.and(ty))
526                 })
527             })
528         }
529         ty::Tuple(..) => {
530             debug!("ty::Tuple(..) =>");
531             ty.tuple_fields().any(|ty| tcx.conservative_is_privately_uninhabited(param_env.and(ty)))
532         }
533         ty::Array(ty, len) => {
534             debug!("ty::Array(ty, len) =>");
535             match len.try_eval_usize(tcx, param_env) {
536                 Some(0) | None => false,
537                 // If the array is definitely non-empty, it's uninhabited if
538                 // the type of its elements is uninhabited.
539                 Some(1..) => tcx.conservative_is_privately_uninhabited(param_env.and(ty)),
540             }
541         }
542         ty::Ref(..) => {
543             debug!("ty::Ref(..) =>");
544             // References to uninitialised memory is valid for any type, including
545             // uninhabited types, in unsafe code, so we treat all references as
546             // inhabited.
547             false
548         }
549         _ => {
550             debug!("_ =>");
551             false
552         }
553     }
554 }
555
556 pub fn provide(providers: &mut ty::query::Providers) {
557     *providers = ty::query::Providers {
558         asyncness,
559         associated_item,
560         associated_item_def_ids,
561         associated_items,
562         adt_sized_constraint,
563         def_ident_span,
564         param_env,
565         param_env_reveal_all_normalized,
566         trait_of_item,
567         instance_def_size_estimate,
568         issue33140_self_ty,
569         impl_defaultness,
570         impl_constness,
571         conservative_is_privately_uninhabited: conservative_is_privately_uninhabited_raw,
572         ..*providers
573     };
574 }