diff options
Diffstat (limited to '')
-rw-r--r-- | compiler/rustc_ty_utils/Cargo.toml | 18 | ||||
-rw-r--r-- | compiler/rustc_ty_utils/src/assoc.rs | 111 | ||||
-rw-r--r-- | compiler/rustc_ty_utils/src/common_traits.rs | 51 | ||||
-rw-r--r-- | compiler/rustc_ty_utils/src/consts.rs | 469 | ||||
-rw-r--r-- | compiler/rustc_ty_utils/src/instance.rs | 407 | ||||
-rw-r--r-- | compiler/rustc_ty_utils/src/lib.rs | 36 | ||||
-rw-r--r-- | compiler/rustc_ty_utils/src/needs_drop.rs | 323 | ||||
-rw-r--r-- | compiler/rustc_ty_utils/src/representability.rs | 386 | ||||
-rw-r--r-- | compiler/rustc_ty_utils/src/ty.rs | 481 |
9 files changed, 2282 insertions, 0 deletions
diff --git a/compiler/rustc_ty_utils/Cargo.toml b/compiler/rustc_ty_utils/Cargo.toml new file mode 100644 index 000000000..caad2ed42 --- /dev/null +++ b/compiler/rustc_ty_utils/Cargo.toml @@ -0,0 +1,18 @@ +[package] +name = "rustc_ty_utils" +version = "0.0.0" +edition = "2021" + +[dependencies] +tracing = "0.1" +rustc_middle = { path = "../rustc_middle" } +rustc_data_structures = { path = "../rustc_data_structures" } +rustc_errors = { path = "../rustc_errors" } +rustc_hir = { path = "../rustc_hir" } +rustc_infer = { path = "../rustc_infer" } +rustc_span = { path = "../rustc_span" } +rustc_session = { path = "../rustc_session" } +rustc_target = { path = "../rustc_target" } +rustc_trait_selection = { path = "../rustc_trait_selection" } +rustc_type_ir = { path = "../rustc_type_ir" } +rustc_index = { path = "../rustc_index" } diff --git a/compiler/rustc_ty_utils/src/assoc.rs b/compiler/rustc_ty_utils/src/assoc.rs new file mode 100644 index 000000000..515a73ead --- /dev/null +++ b/compiler/rustc_ty_utils/src/assoc.rs @@ -0,0 +1,111 @@ +use rustc_data_structures::fx::FxHashMap; +use rustc_hir as hir; +use rustc_hir::def_id::DefId; +use rustc_middle::ty::{self, TyCtxt}; + +pub fn provide(providers: &mut ty::query::Providers) { + *providers = ty::query::Providers { + associated_item, + associated_item_def_ids, + associated_items, + impl_item_implementor_ids, + ..*providers + }; +} + +fn associated_item_def_ids(tcx: TyCtxt<'_>, def_id: DefId) -> &[DefId] { + let item = tcx.hir().expect_item(def_id.expect_local()); + match item.kind { + hir::ItemKind::Trait(.., ref trait_item_refs) => tcx.arena.alloc_from_iter( + trait_item_refs.iter().map(|trait_item_ref| trait_item_ref.id.def_id.to_def_id()), + ), + hir::ItemKind::Impl(ref impl_) => tcx.arena.alloc_from_iter( + impl_.items.iter().map(|impl_item_ref| impl_item_ref.id.def_id.to_def_id()), + ), + hir::ItemKind::TraitAlias(..) => &[], + _ => span_bug!(item.span, "associated_item_def_ids: not impl or trait"), + } +} + +fn associated_items(tcx: TyCtxt<'_>, def_id: DefId) -> ty::AssocItems<'_> { + let items = tcx.associated_item_def_ids(def_id).iter().map(|did| tcx.associated_item(*did)); + ty::AssocItems::new(items) +} + +fn impl_item_implementor_ids(tcx: TyCtxt<'_>, impl_id: DefId) -> FxHashMap<DefId, DefId> { + tcx.associated_items(impl_id) + .in_definition_order() + .filter_map(|item| item.trait_item_def_id.map(|trait_item| (trait_item, item.def_id))) + .collect() +} + +fn associated_item(tcx: TyCtxt<'_>, def_id: DefId) -> ty::AssocItem { + let id = tcx.hir().local_def_id_to_hir_id(def_id.expect_local()); + let parent_def_id = tcx.hir().get_parent_item(id); + let parent_item = tcx.hir().expect_item(parent_def_id); + match parent_item.kind { + hir::ItemKind::Impl(ref impl_) => { + if let Some(impl_item_ref) = + impl_.items.iter().find(|i| i.id.def_id.to_def_id() == def_id) + { + let assoc_item = associated_item_from_impl_item_ref(impl_item_ref); + debug_assert_eq!(assoc_item.def_id, def_id); + return assoc_item; + } + } + + hir::ItemKind::Trait(.., ref trait_item_refs) => { + if let Some(trait_item_ref) = + trait_item_refs.iter().find(|i| i.id.def_id.to_def_id() == def_id) + { + let assoc_item = associated_item_from_trait_item_ref(trait_item_ref); + debug_assert_eq!(assoc_item.def_id, def_id); + return assoc_item; + } + } + + _ => {} + } + + span_bug!( + parent_item.span, + "unexpected parent of trait or impl item or item not found: {:?}", + parent_item.kind + ) +} + +fn associated_item_from_trait_item_ref(trait_item_ref: &hir::TraitItemRef) -> ty::AssocItem { + let def_id = trait_item_ref.id.def_id; + let (kind, has_self) = match trait_item_ref.kind { + hir::AssocItemKind::Const => (ty::AssocKind::Const, false), + hir::AssocItemKind::Fn { has_self } => (ty::AssocKind::Fn, has_self), + hir::AssocItemKind::Type => (ty::AssocKind::Type, false), + }; + + ty::AssocItem { + name: trait_item_ref.ident.name, + kind, + def_id: def_id.to_def_id(), + trait_item_def_id: Some(def_id.to_def_id()), + container: ty::TraitContainer, + fn_has_self_parameter: has_self, + } +} + +fn associated_item_from_impl_item_ref(impl_item_ref: &hir::ImplItemRef) -> ty::AssocItem { + let def_id = impl_item_ref.id.def_id; + let (kind, has_self) = match impl_item_ref.kind { + hir::AssocItemKind::Const => (ty::AssocKind::Const, false), + hir::AssocItemKind::Fn { has_self } => (ty::AssocKind::Fn, has_self), + hir::AssocItemKind::Type => (ty::AssocKind::Type, false), + }; + + ty::AssocItem { + name: impl_item_ref.ident.name, + kind, + def_id: def_id.to_def_id(), + trait_item_def_id: impl_item_ref.trait_item_def_id, + container: ty::ImplContainer, + fn_has_self_parameter: has_self, + } +} diff --git a/compiler/rustc_ty_utils/src/common_traits.rs b/compiler/rustc_ty_utils/src/common_traits.rs new file mode 100644 index 000000000..cedc84d97 --- /dev/null +++ b/compiler/rustc_ty_utils/src/common_traits.rs @@ -0,0 +1,51 @@ +//! Queries for checking whether a type implements one of a few common traits. + +use rustc_hir::lang_items::LangItem; +use rustc_infer::infer::TyCtxtInferExt; +use rustc_middle::ty::{self, Ty, TyCtxt}; +use rustc_span::DUMMY_SP; +use rustc_trait_selection::traits; + +fn is_copy_raw<'tcx>(tcx: TyCtxt<'tcx>, query: ty::ParamEnvAnd<'tcx, Ty<'tcx>>) -> bool { + is_item_raw(tcx, query, LangItem::Copy) +} + +fn is_sized_raw<'tcx>(tcx: TyCtxt<'tcx>, query: ty::ParamEnvAnd<'tcx, Ty<'tcx>>) -> bool { + is_item_raw(tcx, query, LangItem::Sized) +} + +fn is_freeze_raw<'tcx>(tcx: TyCtxt<'tcx>, query: ty::ParamEnvAnd<'tcx, Ty<'tcx>>) -> bool { + is_item_raw(tcx, query, LangItem::Freeze) +} + +fn is_unpin_raw<'tcx>(tcx: TyCtxt<'tcx>, query: ty::ParamEnvAnd<'tcx, Ty<'tcx>>) -> bool { + is_item_raw(tcx, query, LangItem::Unpin) +} + +fn is_item_raw<'tcx>( + tcx: TyCtxt<'tcx>, + query: ty::ParamEnvAnd<'tcx, Ty<'tcx>>, + item: LangItem, +) -> bool { + let (param_env, ty) = query.into_parts(); + let trait_def_id = tcx.require_lang_item(item, None); + tcx.infer_ctxt().enter(|infcx| { + traits::type_known_to_meet_bound_modulo_regions( + &infcx, + param_env, + ty, + trait_def_id, + DUMMY_SP, + ) + }) +} + +pub(crate) fn provide(providers: &mut ty::query::Providers) { + *providers = ty::query::Providers { + is_copy_raw, + is_sized_raw, + is_freeze_raw, + is_unpin_raw, + ..*providers + }; +} diff --git a/compiler/rustc_ty_utils/src/consts.rs b/compiler/rustc_ty_utils/src/consts.rs new file mode 100644 index 000000000..7c2f4db94 --- /dev/null +++ b/compiler/rustc_ty_utils/src/consts.rs @@ -0,0 +1,469 @@ +use rustc_errors::ErrorGuaranteed; +use rustc_hir::def::DefKind; +use rustc_hir::def_id::LocalDefId; +use rustc_index::vec::IndexVec; +use rustc_middle::mir::interpret::{LitToConstError, LitToConstInput}; +use rustc_middle::ty::abstract_const::{CastKind, Node, NodeId}; +use rustc_middle::ty::{self, TyCtxt, TypeVisitable}; +use rustc_middle::{mir, thir}; +use rustc_span::Span; +use rustc_target::abi::VariantIdx; + +use std::iter; + +/// Destructures array, ADT or tuple constants into the constants +/// of their fields. +pub(crate) fn destructure_const<'tcx>( + tcx: TyCtxt<'tcx>, + const_: ty::Const<'tcx>, +) -> ty::DestructuredConst<'tcx> { + let ty::ConstKind::Value(valtree) = const_.kind() else { + bug!("cannot destructure constant {:?}", const_) + }; + + let branches = match valtree { + ty::ValTree::Branch(b) => b, + _ => bug!("cannot destructure constant {:?}", const_), + }; + + let (fields, variant) = match const_.ty().kind() { + ty::Array(inner_ty, _) | ty::Slice(inner_ty) => { + // construct the consts for the elements of the array/slice + let field_consts = branches + .iter() + .map(|b| tcx.mk_const(ty::ConstS { kind: ty::ConstKind::Value(*b), ty: *inner_ty })) + .collect::<Vec<_>>(); + debug!(?field_consts); + + (field_consts, None) + } + ty::Adt(def, _) if def.variants().is_empty() => bug!("unreachable"), + ty::Adt(def, substs) => { + let (variant_idx, branches) = if def.is_enum() { + let (head, rest) = branches.split_first().unwrap(); + (VariantIdx::from_u32(head.unwrap_leaf().try_to_u32().unwrap()), rest) + } else { + (VariantIdx::from_u32(0), branches) + }; + let fields = &def.variant(variant_idx).fields; + let mut field_consts = Vec::with_capacity(fields.len()); + + for (field, field_valtree) in iter::zip(fields, branches) { + let field_ty = field.ty(tcx, substs); + let field_const = tcx.mk_const(ty::ConstS { + kind: ty::ConstKind::Value(*field_valtree), + ty: field_ty, + }); + field_consts.push(field_const); + } + debug!(?field_consts); + + (field_consts, Some(variant_idx)) + } + ty::Tuple(elem_tys) => { + let fields = iter::zip(*elem_tys, branches) + .map(|(elem_ty, elem_valtree)| { + tcx.mk_const(ty::ConstS { + kind: ty::ConstKind::Value(*elem_valtree), + ty: elem_ty, + }) + }) + .collect::<Vec<_>>(); + + (fields, None) + } + _ => bug!("cannot destructure constant {:?}", const_), + }; + + let fields = tcx.arena.alloc_from_iter(fields.into_iter()); + + ty::DestructuredConst { variant, fields } +} + +pub struct AbstractConstBuilder<'a, 'tcx> { + tcx: TyCtxt<'tcx>, + body_id: thir::ExprId, + body: &'a thir::Thir<'tcx>, + /// The current WIP node tree. + nodes: IndexVec<NodeId, Node<'tcx>>, +} + +impl<'a, 'tcx> AbstractConstBuilder<'a, 'tcx> { + fn root_span(&self) -> Span { + self.body.exprs[self.body_id].span + } + + fn error(&mut self, span: Span, msg: &str) -> Result<!, ErrorGuaranteed> { + let reported = self + .tcx + .sess + .struct_span_err(self.root_span(), "overly complex generic constant") + .span_label(span, msg) + .help("consider moving this anonymous constant into a `const` function") + .emit(); + + Err(reported) + } + fn maybe_supported_error(&mut self, span: Span, msg: &str) -> Result<!, ErrorGuaranteed> { + let reported = self + .tcx + .sess + .struct_span_err(self.root_span(), "overly complex generic constant") + .span_label(span, msg) + .help("consider moving this anonymous constant into a `const` function") + .note("this operation may be supported in the future") + .emit(); + + Err(reported) + } + + #[instrument(skip(tcx, body, body_id), level = "debug")] + pub fn new( + tcx: TyCtxt<'tcx>, + (body, body_id): (&'a thir::Thir<'tcx>, thir::ExprId), + ) -> Result<Option<AbstractConstBuilder<'a, 'tcx>>, ErrorGuaranteed> { + let builder = AbstractConstBuilder { tcx, body_id, body, nodes: IndexVec::new() }; + + struct IsThirPolymorphic<'a, 'tcx> { + is_poly: bool, + thir: &'a thir::Thir<'tcx>, + } + + use crate::rustc_middle::thir::visit::Visitor; + use thir::visit; + + impl<'a, 'tcx> IsThirPolymorphic<'a, 'tcx> { + fn expr_is_poly(&mut self, expr: &thir::Expr<'tcx>) -> bool { + if expr.ty.has_param_types_or_consts() { + return true; + } + + match expr.kind { + thir::ExprKind::NamedConst { substs, .. } => substs.has_param_types_or_consts(), + thir::ExprKind::ConstParam { .. } => true, + thir::ExprKind::Repeat { value, count } => { + self.visit_expr(&self.thir()[value]); + count.has_param_types_or_consts() + } + _ => false, + } + } + + fn pat_is_poly(&mut self, pat: &thir::Pat<'tcx>) -> bool { + if pat.ty.has_param_types_or_consts() { + return true; + } + + match pat.kind.as_ref() { + thir::PatKind::Constant { value } => value.has_param_types_or_consts(), + thir::PatKind::Range(thir::PatRange { lo, hi, .. }) => { + lo.has_param_types_or_consts() || hi.has_param_types_or_consts() + } + _ => false, + } + } + } + + impl<'a, 'tcx> visit::Visitor<'a, 'tcx> for IsThirPolymorphic<'a, 'tcx> { + fn thir(&self) -> &'a thir::Thir<'tcx> { + &self.thir + } + + #[instrument(skip(self), level = "debug")] + fn visit_expr(&mut self, expr: &thir::Expr<'tcx>) { + self.is_poly |= self.expr_is_poly(expr); + if !self.is_poly { + visit::walk_expr(self, expr) + } + } + + #[instrument(skip(self), level = "debug")] + fn visit_pat(&mut self, pat: &thir::Pat<'tcx>) { + self.is_poly |= self.pat_is_poly(pat); + if !self.is_poly { + visit::walk_pat(self, pat); + } + } + } + + let mut is_poly_vis = IsThirPolymorphic { is_poly: false, thir: body }; + visit::walk_expr(&mut is_poly_vis, &body[body_id]); + debug!("AbstractConstBuilder: is_poly={}", is_poly_vis.is_poly); + if !is_poly_vis.is_poly { + return Ok(None); + } + + Ok(Some(builder)) + } + + /// We do not allow all binary operations in abstract consts, so filter disallowed ones. + fn check_binop(op: mir::BinOp) -> bool { + use mir::BinOp::*; + match op { + Add | Sub | Mul | Div | Rem | BitXor | BitAnd | BitOr | Shl | Shr | Eq | Lt | Le + | Ne | Ge | Gt => true, + Offset => false, + } + } + + /// While we currently allow all unary operations, we still want to explicitly guard against + /// future changes here. + fn check_unop(op: mir::UnOp) -> bool { + use mir::UnOp::*; + match op { + Not | Neg => true, + } + } + + /// Builds the abstract const by walking the thir and bailing out when + /// encountering an unsupported operation. + pub fn build(mut self) -> Result<&'tcx [Node<'tcx>], ErrorGuaranteed> { + debug!("AbstractConstBuilder::build: body={:?}", &*self.body); + self.recurse_build(self.body_id)?; + + for n in self.nodes.iter() { + if let Node::Leaf(ct) = n { + if let ty::ConstKind::Unevaluated(ct) = ct.kind() { + // `AbstractConst`s should not contain any promoteds as they require references which + // are not allowed. + assert_eq!(ct.promoted, None); + assert_eq!(ct, self.tcx.erase_regions(ct)); + } + } + } + + Ok(self.tcx.arena.alloc_from_iter(self.nodes.into_iter())) + } + + fn recurse_build(&mut self, node: thir::ExprId) -> Result<NodeId, ErrorGuaranteed> { + use thir::ExprKind; + let node = &self.body.exprs[node]; + Ok(match &node.kind { + // I dont know if handling of these 3 is correct + &ExprKind::Scope { value, .. } => self.recurse_build(value)?, + &ExprKind::PlaceTypeAscription { source, .. } + | &ExprKind::ValueTypeAscription { source, .. } => self.recurse_build(source)?, + &ExprKind::Literal { lit, neg} => { + let sp = node.span; + let constant = + match self.tcx.at(sp).lit_to_const(LitToConstInput { lit: &lit.node, ty: node.ty, neg }) { + Ok(c) => c, + Err(LitToConstError::Reported) => { + self.tcx.const_error(node.ty) + } + Err(LitToConstError::TypeError) => { + bug!("encountered type error in lit_to_const") + } + }; + + self.nodes.push(Node::Leaf(constant)) + } + &ExprKind::NonHirLiteral { lit , user_ty: _} => { + let val = ty::ValTree::from_scalar_int(lit); + self.nodes.push(Node::Leaf(ty::Const::from_value(self.tcx, val, node.ty))) + } + &ExprKind::ZstLiteral { user_ty: _ } => { + let val = ty::ValTree::zst(); + self.nodes.push(Node::Leaf(ty::Const::from_value(self.tcx, val, node.ty))) + } + &ExprKind::NamedConst { def_id, substs, user_ty: _ } => { + let uneval = ty::Unevaluated::new(ty::WithOptConstParam::unknown(def_id), substs); + + let constant = self.tcx.mk_const(ty::ConstS { + kind: ty::ConstKind::Unevaluated(uneval), + ty: node.ty, + }); + + self.nodes.push(Node::Leaf(constant)) + } + + ExprKind::ConstParam {param, ..} => { + let const_param = self.tcx.mk_const(ty::ConstS { + kind: ty::ConstKind::Param(*param), + ty: node.ty, + }); + self.nodes.push(Node::Leaf(const_param)) + } + + ExprKind::Call { fun, args, .. } => { + let fun = self.recurse_build(*fun)?; + + let mut new_args = Vec::<NodeId>::with_capacity(args.len()); + for &id in args.iter() { + new_args.push(self.recurse_build(id)?); + } + let new_args = self.tcx.arena.alloc_slice(&new_args); + self.nodes.push(Node::FunctionCall(fun, new_args)) + } + &ExprKind::Binary { op, lhs, rhs } if Self::check_binop(op) => { + let lhs = self.recurse_build(lhs)?; + let rhs = self.recurse_build(rhs)?; + self.nodes.push(Node::Binop(op, lhs, rhs)) + } + &ExprKind::Unary { op, arg } if Self::check_unop(op) => { + let arg = self.recurse_build(arg)?; + self.nodes.push(Node::UnaryOp(op, arg)) + } + // This is necessary so that the following compiles: + // + // ``` + // fn foo<const N: usize>(a: [(); N + 1]) { + // bar::<{ N + 1 }>(); + // } + // ``` + ExprKind::Block { body: thir::Block { stmts: box [], expr: Some(e), .. } } => { + self.recurse_build(*e)? + } + // `ExprKind::Use` happens when a `hir::ExprKind::Cast` is a + // "coercion cast" i.e. using a coercion or is a no-op. + // This is important so that `N as usize as usize` doesnt unify with `N as usize`. (untested) + &ExprKind::Use { source } => { + let arg = self.recurse_build(source)?; + self.nodes.push(Node::Cast(CastKind::Use, arg, node.ty)) + } + &ExprKind::Cast { source } => { + let arg = self.recurse_build(source)?; + self.nodes.push(Node::Cast(CastKind::As, arg, node.ty)) + } + ExprKind::Borrow{ arg, ..} => { + let arg_node = &self.body.exprs[*arg]; + + // Skip reborrows for now until we allow Deref/Borrow/AddressOf + // expressions. + // FIXME(generic_const_exprs): Verify/explain why this is sound + if let ExprKind::Deref { arg } = arg_node.kind { + self.recurse_build(arg)? + } else { + self.maybe_supported_error( + node.span, + "borrowing is not supported in generic constants", + )? + } + } + // FIXME(generic_const_exprs): We may want to support these. + ExprKind::AddressOf { .. } | ExprKind::Deref {..}=> self.maybe_supported_error( + node.span, + "dereferencing or taking the address is not supported in generic constants", + )?, + ExprKind::Repeat { .. } | ExprKind::Array { .. } => self.maybe_supported_error( + node.span, + "array construction is not supported in generic constants", + )?, + ExprKind::Block { .. } => self.maybe_supported_error( + node.span, + "blocks are not supported in generic constant", + )?, + ExprKind::NeverToAny { .. } => self.maybe_supported_error( + node.span, + "converting nevers to any is not supported in generic constant", + )?, + ExprKind::Tuple { .. } => self.maybe_supported_error( + node.span, + "tuple construction is not supported in generic constants", + )?, + ExprKind::Index { .. } => self.maybe_supported_error( + node.span, + "indexing is not supported in generic constant", + )?, + ExprKind::Field { .. } => self.maybe_supported_error( + node.span, + "field access is not supported in generic constant", + )?, + ExprKind::ConstBlock { .. } => self.maybe_supported_error( + node.span, + "const blocks are not supported in generic constant", + )?, + ExprKind::Adt(_) => self.maybe_supported_error( + node.span, + "struct/enum construction is not supported in generic constants", + )?, + // dont know if this is correct + ExprKind::Pointer { .. } => + self.error(node.span, "pointer casts are not allowed in generic constants")?, + ExprKind::Yield { .. } => + self.error(node.span, "generator control flow is not allowed in generic constants")?, + ExprKind::Continue { .. } | ExprKind::Break { .. } | ExprKind::Loop { .. } => self + .error( + node.span, + "loops and loop control flow are not supported in generic constants", + )?, + ExprKind::Box { .. } => + self.error(node.span, "allocations are not allowed in generic constants")?, + + ExprKind::Unary { .. } => unreachable!(), + // we handle valid unary/binary ops above + ExprKind::Binary { .. } => + self.error(node.span, "unsupported binary operation in generic constants")?, + ExprKind::LogicalOp { .. } => + self.error(node.span, "unsupported operation in generic constants, short-circuiting operations would imply control flow")?, + ExprKind::Assign { .. } | ExprKind::AssignOp { .. } => { + self.error(node.span, "assignment is not supported in generic constants")? + } + ExprKind::Closure { .. } | ExprKind::Return { .. } => self.error( + node.span, + "closures and function keywords are not supported in generic constants", + )?, + // let expressions imply control flow + ExprKind::Match { .. } | ExprKind::If { .. } | ExprKind::Let { .. } => + self.error(node.span, "control flow is not supported in generic constants")?, + ExprKind::InlineAsm { .. } => { + self.error(node.span, "assembly is not supported in generic constants")? + } + + // we dont permit let stmts so `VarRef` and `UpvarRef` cant happen + ExprKind::VarRef { .. } + | ExprKind::UpvarRef { .. } + | ExprKind::StaticRef { .. } + | ExprKind::ThreadLocalRef(_) => { + self.error(node.span, "unsupported operation in generic constant")? + } + }) + } +} + +/// Builds an abstract const, do not use this directly, but use `AbstractConst::new` instead. +pub fn thir_abstract_const<'tcx>( + tcx: TyCtxt<'tcx>, + def: ty::WithOptConstParam<LocalDefId>, +) -> Result<Option<&'tcx [Node<'tcx>]>, ErrorGuaranteed> { + if tcx.features().generic_const_exprs { + match tcx.def_kind(def.did) { + // FIXME(generic_const_exprs): We currently only do this for anonymous constants, + // meaning that we do not look into associated constants. I(@lcnr) am not yet sure whether + // we want to look into them or treat them as opaque projections. + // + // Right now we do neither of that and simply always fail to unify them. + DefKind::AnonConst | DefKind::InlineConst => (), + _ => return Ok(None), + } + + let body = tcx.thir_body(def)?; + + AbstractConstBuilder::new(tcx, (&*body.0.borrow(), body.1))? + .map(AbstractConstBuilder::build) + .transpose() + } else { + Ok(None) + } +} + +pub fn provide(providers: &mut ty::query::Providers) { + *providers = ty::query::Providers { + destructure_const, + thir_abstract_const: |tcx, def_id| { + let def_id = def_id.expect_local(); + if let Some(def) = ty::WithOptConstParam::try_lookup(def_id, tcx) { + tcx.thir_abstract_const_of_const_arg(def) + } else { + thir_abstract_const(tcx, ty::WithOptConstParam::unknown(def_id)) + } + }, + thir_abstract_const_of_const_arg: |tcx, (did, param_did)| { + thir_abstract_const( + tcx, + ty::WithOptConstParam { did, const_param_did: Some(param_did) }, + ) + }, + ..*providers + }; +} diff --git a/compiler/rustc_ty_utils/src/instance.rs b/compiler/rustc_ty_utils/src/instance.rs new file mode 100644 index 000000000..bd1d568cd --- /dev/null +++ b/compiler/rustc_ty_utils/src/instance.rs @@ -0,0 +1,407 @@ +use rustc_errors::ErrorGuaranteed; +use rustc_hir::def_id::{DefId, LocalDefId}; +use rustc_infer::infer::TyCtxtInferExt; +use rustc_middle::traits::CodegenObligationError; +use rustc_middle::ty::subst::SubstsRef; +use rustc_middle::ty::{ + self, Binder, Instance, Ty, TyCtxt, TypeSuperVisitable, TypeVisitable, TypeVisitor, +}; +use rustc_span::{sym, DUMMY_SP}; +use rustc_trait_selection::traits; +use traits::{translate_substs, Reveal}; + +use rustc_data_structures::sso::SsoHashSet; +use std::collections::btree_map::Entry; +use std::collections::BTreeMap; +use std::ops::ControlFlow; + +use tracing::debug; + +// FIXME(#86795): `BoundVarsCollector` here should **NOT** be used +// outside of `resolve_associated_item`. It's just to address #64494, +// #83765, and #85848 which are creating bound types/regions that lose +// their `Binder` *unintentionally*. +// It's ideal to remove `BoundVarsCollector` and just use +// `ty::Binder::*` methods but we use this stopgap until we figure out +// the "real" fix. +struct BoundVarsCollector<'tcx> { + binder_index: ty::DebruijnIndex, + vars: BTreeMap<u32, ty::BoundVariableKind>, + // We may encounter the same variable at different levels of binding, so + // this can't just be `Ty` + visited: SsoHashSet<(ty::DebruijnIndex, Ty<'tcx>)>, +} + +impl<'tcx> BoundVarsCollector<'tcx> { + fn new() -> Self { + BoundVarsCollector { + binder_index: ty::INNERMOST, + vars: BTreeMap::new(), + visited: SsoHashSet::default(), + } + } + + fn into_vars(self, tcx: TyCtxt<'tcx>) -> &'tcx ty::List<ty::BoundVariableKind> { + let max = self.vars.iter().map(|(k, _)| *k).max().unwrap_or(0); + for i in 0..max { + if let None = self.vars.get(&i) { + panic!("Unknown variable: {:?}", i); + } + } + + tcx.mk_bound_variable_kinds(self.vars.into_iter().map(|(_, v)| v)) + } +} + +impl<'tcx> TypeVisitor<'tcx> for BoundVarsCollector<'tcx> { + type BreakTy = (); + + fn visit_binder<T: TypeVisitable<'tcx>>( + &mut self, + t: &Binder<'tcx, T>, + ) -> ControlFlow<Self::BreakTy> { + self.binder_index.shift_in(1); + let result = t.super_visit_with(self); + self.binder_index.shift_out(1); + result + } + + fn visit_ty(&mut self, t: Ty<'tcx>) -> ControlFlow<Self::BreakTy> { + if t.outer_exclusive_binder() < self.binder_index + || !self.visited.insert((self.binder_index, t)) + { + return ControlFlow::CONTINUE; + } + match *t.kind() { + ty::Bound(debruijn, bound_ty) if debruijn == self.binder_index => { + match self.vars.entry(bound_ty.var.as_u32()) { + Entry::Vacant(entry) => { + entry.insert(ty::BoundVariableKind::Ty(bound_ty.kind)); + } + Entry::Occupied(entry) => match entry.get() { + ty::BoundVariableKind::Ty(_) => {} + _ => bug!("Conflicting bound vars"), + }, + } + } + + _ => (), + }; + + t.super_visit_with(self) + } + + fn visit_region(&mut self, r: ty::Region<'tcx>) -> ControlFlow<Self::BreakTy> { + match *r { + ty::ReLateBound(index, br) if index == self.binder_index => { + match self.vars.entry(br.var.as_u32()) { + Entry::Vacant(entry) => { + entry.insert(ty::BoundVariableKind::Region(br.kind)); + } + Entry::Occupied(entry) => match entry.get() { + ty::BoundVariableKind::Region(_) => {} + _ => bug!("Conflicting bound vars"), + }, + } + } + + _ => (), + }; + + r.super_visit_with(self) + } +} + +fn resolve_instance<'tcx>( + tcx: TyCtxt<'tcx>, + key: ty::ParamEnvAnd<'tcx, (DefId, SubstsRef<'tcx>)>, +) -> Result<Option<Instance<'tcx>>, ErrorGuaranteed> { + let (param_env, (did, substs)) = key.into_parts(); + if let Some(did) = did.as_local() { + if let Some(param_did) = tcx.opt_const_param_of(did) { + return tcx.resolve_instance_of_const_arg(param_env.and((did, param_did, substs))); + } + } + + inner_resolve_instance(tcx, param_env.and((ty::WithOptConstParam::unknown(did), substs))) +} + +fn resolve_instance_of_const_arg<'tcx>( + tcx: TyCtxt<'tcx>, + key: ty::ParamEnvAnd<'tcx, (LocalDefId, DefId, SubstsRef<'tcx>)>, +) -> Result<Option<Instance<'tcx>>, ErrorGuaranteed> { + let (param_env, (did, const_param_did, substs)) = key.into_parts(); + inner_resolve_instance( + tcx, + param_env.and(( + ty::WithOptConstParam { did: did.to_def_id(), const_param_did: Some(const_param_did) }, + substs, + )), + ) +} + +fn inner_resolve_instance<'tcx>( + tcx: TyCtxt<'tcx>, + key: ty::ParamEnvAnd<'tcx, (ty::WithOptConstParam<DefId>, SubstsRef<'tcx>)>, +) -> Result<Option<Instance<'tcx>>, ErrorGuaranteed> { + let (param_env, (def, substs)) = key.into_parts(); + + let result = if let Some(trait_def_id) = tcx.trait_of_item(def.did) { + debug!(" => associated item, attempting to find impl in param_env {:#?}", param_env); + resolve_associated_item(tcx, def.did, param_env, trait_def_id, substs) + } else { + let ty = tcx.type_of(def.def_id_for_type_of()); + let item_type = tcx.subst_and_normalize_erasing_regions(substs, param_env, ty); + + let def = match *item_type.kind() { + ty::FnDef(def_id, ..) if tcx.is_intrinsic(def_id) => { + debug!(" => intrinsic"); + ty::InstanceDef::Intrinsic(def.did) + } + ty::FnDef(def_id, substs) if Some(def_id) == tcx.lang_items().drop_in_place_fn() => { + let ty = substs.type_at(0); + + if ty.needs_drop(tcx, param_env) { + debug!(" => nontrivial drop glue"); + match *ty.kind() { + ty::Closure(..) + | ty::Generator(..) + | ty::Tuple(..) + | ty::Adt(..) + | ty::Dynamic(..) + | ty::Array(..) + | ty::Slice(..) => {} + // Drop shims can only be built from ADTs. + _ => return Ok(None), + } + + ty::InstanceDef::DropGlue(def_id, Some(ty)) + } else { + debug!(" => trivial drop glue"); + ty::InstanceDef::DropGlue(def_id, None) + } + } + _ => { + debug!(" => free item"); + ty::InstanceDef::Item(def) + } + }; + Ok(Some(Instance { def, substs })) + }; + debug!("inner_resolve_instance: result={:?}", result); + result +} + +fn resolve_associated_item<'tcx>( + tcx: TyCtxt<'tcx>, + trait_item_id: DefId, + param_env: ty::ParamEnv<'tcx>, + trait_id: DefId, + rcvr_substs: SubstsRef<'tcx>, +) -> Result<Option<Instance<'tcx>>, ErrorGuaranteed> { + debug!(?trait_item_id, ?param_env, ?trait_id, ?rcvr_substs, "resolve_associated_item"); + + let trait_ref = ty::TraitRef::from_method(tcx, trait_id, rcvr_substs); + + // See FIXME on `BoundVarsCollector`. + let mut bound_vars_collector = BoundVarsCollector::new(); + trait_ref.visit_with(&mut bound_vars_collector); + let trait_binder = ty::Binder::bind_with_vars(trait_ref, bound_vars_collector.into_vars(tcx)); + let vtbl = match tcx.codegen_fulfill_obligation((param_env, trait_binder)) { + Ok(vtbl) => vtbl, + Err(CodegenObligationError::Ambiguity) => { + let reported = tcx.sess.delay_span_bug( + tcx.def_span(trait_item_id), + &format!( + "encountered ambiguity selecting `{:?}` during codegen, presuming due to \ + overflow or prior type error", + trait_binder + ), + ); + return Err(reported); + } + Err(CodegenObligationError::Unimplemented) => return Ok(None), + Err(CodegenObligationError::FulfillmentError) => return Ok(None), + }; + + // Now that we know which impl is being used, we can dispatch to + // the actual function: + Ok(match vtbl { + traits::ImplSource::UserDefined(impl_data) => { + debug!( + "resolving ImplSource::UserDefined: {:?}, {:?}, {:?}, {:?}", + param_env, trait_item_id, rcvr_substs, impl_data + ); + assert!(!rcvr_substs.needs_infer()); + assert!(!trait_ref.needs_infer()); + + let trait_def_id = tcx.trait_id_of_impl(impl_data.impl_def_id).unwrap(); + let trait_def = tcx.trait_def(trait_def_id); + let leaf_def = trait_def + .ancestors(tcx, impl_data.impl_def_id)? + .leaf_def(tcx, trait_item_id) + .unwrap_or_else(|| { + bug!("{:?} not found in {:?}", trait_item_id, impl_data.impl_def_id); + }); + + let substs = tcx.infer_ctxt().enter(|infcx| { + let param_env = param_env.with_reveal_all_normalized(tcx); + let substs = rcvr_substs.rebase_onto(tcx, trait_def_id, impl_data.substs); + let substs = translate_substs( + &infcx, + param_env, + impl_data.impl_def_id, + substs, + leaf_def.defining_node, + ); + infcx.tcx.erase_regions(substs) + }); + + // Since this is a trait item, we need to see if the item is either a trait default item + // or a specialization because we can't resolve those unless we can `Reveal::All`. + // NOTE: This should be kept in sync with the similar code in + // `rustc_trait_selection::traits::project::assemble_candidates_from_impls()`. + let eligible = if leaf_def.is_final() { + // Non-specializable items are always projectable. + true + } else { + // Only reveal a specializable default if we're past type-checking + // and the obligation is monomorphic, otherwise passes such as + // transmute checking and polymorphic MIR optimizations could + // get a result which isn't correct for all monomorphizations. + if param_env.reveal() == Reveal::All { + !trait_ref.still_further_specializable() + } else { + false + } + }; + + if !eligible { + return Ok(None); + } + + // If the item does not have a value, then we cannot return an instance. + if !leaf_def.item.defaultness(tcx).has_value() { + return Ok(None); + } + + let substs = tcx.erase_regions(substs); + + // Check if we just resolved an associated `const` declaration from + // a `trait` to an associated `const` definition in an `impl`, where + // the definition in the `impl` has the wrong type (for which an + // error has already been/will be emitted elsewhere). + // + // NB: this may be expensive, we try to skip it in all the cases where + // we know the error would've been caught (e.g. in an upstream crate). + // + // A better approach might be to just introduce a query (returning + // `Result<(), ErrorGuaranteed>`) for the check that `rustc_typeck` + // performs (i.e. that the definition's type in the `impl` matches + // the declaration in the `trait`), so that we can cheaply check + // here if it failed, instead of approximating it. + if leaf_def.item.kind == ty::AssocKind::Const + && trait_item_id != leaf_def.item.def_id + && leaf_def.item.def_id.is_local() + { + let normalized_type_of = |def_id, substs| { + tcx.subst_and_normalize_erasing_regions(substs, param_env, tcx.type_of(def_id)) + }; + + let original_ty = normalized_type_of(trait_item_id, rcvr_substs); + let resolved_ty = normalized_type_of(leaf_def.item.def_id, substs); + + if original_ty != resolved_ty { + let msg = format!( + "Instance::resolve: inconsistent associated `const` type: \ + was `{}: {}` but resolved to `{}: {}`", + tcx.def_path_str_with_substs(trait_item_id, rcvr_substs), + original_ty, + tcx.def_path_str_with_substs(leaf_def.item.def_id, substs), + resolved_ty, + ); + let span = tcx.def_span(leaf_def.item.def_id); + let reported = tcx.sess.delay_span_bug(span, &msg); + + return Err(reported); + } + } + + Some(ty::Instance::new(leaf_def.item.def_id, substs)) + } + traits::ImplSource::Generator(generator_data) => Some(Instance { + def: ty::InstanceDef::Item(ty::WithOptConstParam::unknown( + generator_data.generator_def_id, + )), + substs: generator_data.substs, + }), + traits::ImplSource::Closure(closure_data) => { + let trait_closure_kind = tcx.fn_trait_kind_from_lang_item(trait_id).unwrap(); + Instance::resolve_closure( + tcx, + closure_data.closure_def_id, + closure_data.substs, + trait_closure_kind, + ) + } + traits::ImplSource::FnPointer(ref data) => match data.fn_ty.kind() { + ty::FnDef(..) | ty::FnPtr(..) => Some(Instance { + def: ty::InstanceDef::FnPtrShim(trait_item_id, data.fn_ty), + substs: rcvr_substs, + }), + _ => None, + }, + traits::ImplSource::Object(ref data) => { + if let Some(index) = traits::get_vtable_index_of_object_method(tcx, data, trait_item_id) + { + Some(Instance { + def: ty::InstanceDef::Virtual(trait_item_id, index), + substs: rcvr_substs, + }) + } else { + None + } + } + traits::ImplSource::Builtin(..) => { + if Some(trait_ref.def_id) == tcx.lang_items().clone_trait() { + // FIXME(eddyb) use lang items for methods instead of names. + let name = tcx.item_name(trait_item_id); + if name == sym::clone { + let self_ty = trait_ref.self_ty(); + + let is_copy = self_ty.is_copy_modulo_regions(tcx.at(DUMMY_SP), param_env); + match self_ty.kind() { + _ if is_copy => (), + ty::Closure(..) | ty::Tuple(..) => {} + _ => return Ok(None), + }; + + Some(Instance { + def: ty::InstanceDef::CloneShim(trait_item_id, self_ty), + substs: rcvr_substs, + }) + } else { + assert_eq!(name, sym::clone_from); + + // Use the default `fn clone_from` from `trait Clone`. + let substs = tcx.erase_regions(rcvr_substs); + Some(ty::Instance::new(trait_item_id, substs)) + } + } else { + None + } + } + traits::ImplSource::AutoImpl(..) + | traits::ImplSource::Param(..) + | traits::ImplSource::TraitAlias(..) + | traits::ImplSource::DiscriminantKind(..) + | traits::ImplSource::Pointee(..) + | traits::ImplSource::TraitUpcasting(_) + | traits::ImplSource::ConstDestruct(_) => None, + }) +} + +pub fn provide(providers: &mut ty::query::Providers) { + *providers = + ty::query::Providers { resolve_instance, resolve_instance_of_const_arg, ..*providers }; +} diff --git a/compiler/rustc_ty_utils/src/lib.rs b/compiler/rustc_ty_utils/src/lib.rs new file mode 100644 index 000000000..09f5c2a11 --- /dev/null +++ b/compiler/rustc_ty_utils/src/lib.rs @@ -0,0 +1,36 @@ +//! Various checks +//! +//! # Note +//! +//! This API is completely unstable and subject to change. + +#![doc(html_root_url = "https://doc.rust-lang.org/nightly/nightly-rustc/")] +#![feature(control_flow_enum)] +#![feature(let_else)] +#![feature(never_type)] +#![feature(box_patterns)] +#![recursion_limit = "256"] + +#[macro_use] +extern crate rustc_middle; +#[macro_use] +extern crate tracing; + +use rustc_middle::ty::query::Providers; + +mod assoc; +mod common_traits; +mod consts; +pub mod instance; +mod needs_drop; +pub mod representability; +mod ty; + +pub fn provide(providers: &mut Providers) { + assoc::provide(providers); + common_traits::provide(providers); + consts::provide(providers); + needs_drop::provide(providers); + ty::provide(providers); + instance::provide(providers); +} diff --git a/compiler/rustc_ty_utils/src/needs_drop.rs b/compiler/rustc_ty_utils/src/needs_drop.rs new file mode 100644 index 000000000..9ad44d14d --- /dev/null +++ b/compiler/rustc_ty_utils/src/needs_drop.rs @@ -0,0 +1,323 @@ +//! Check whether a type has (potentially) non-trivial drop glue. + +use rustc_data_structures::fx::FxHashSet; +use rustc_hir::def_id::DefId; +use rustc_middle::ty::subst::Subst; +use rustc_middle::ty::subst::SubstsRef; +use rustc_middle::ty::util::{needs_drop_components, AlwaysRequiresDrop}; +use rustc_middle::ty::{self, EarlyBinder, Ty, TyCtxt}; +use rustc_session::Limit; +use rustc_span::{sym, DUMMY_SP}; + +type NeedsDropResult<T> = Result<T, AlwaysRequiresDrop>; + +fn needs_drop_raw<'tcx>(tcx: TyCtxt<'tcx>, query: ty::ParamEnvAnd<'tcx, Ty<'tcx>>) -> bool { + // If we don't know a type doesn't need drop, for example if it's a type + // parameter without a `Copy` bound, then we conservatively return that it + // needs drop. + let adt_has_dtor = + |adt_def: ty::AdtDef<'tcx>| adt_def.destructor(tcx).map(|_| DtorType::Significant); + let res = + drop_tys_helper(tcx, query.value, query.param_env, adt_has_dtor, false).next().is_some(); + + debug!("needs_drop_raw({:?}) = {:?}", query, res); + res +} + +fn has_significant_drop_raw<'tcx>( + tcx: TyCtxt<'tcx>, + query: ty::ParamEnvAnd<'tcx, Ty<'tcx>>, +) -> bool { + let res = drop_tys_helper( + tcx, + query.value, + query.param_env, + adt_consider_insignificant_dtor(tcx), + true, + ) + .next() + .is_some(); + debug!("has_significant_drop_raw({:?}) = {:?}", query, res); + res +} + +struct NeedsDropTypes<'tcx, F> { + tcx: TyCtxt<'tcx>, + param_env: ty::ParamEnv<'tcx>, + query_ty: Ty<'tcx>, + seen_tys: FxHashSet<Ty<'tcx>>, + /// A stack of types left to process, and the recursion depth when we + /// pushed that type. Each round, we pop something from the stack and check + /// if it needs drop. If the result depends on whether some other types + /// need drop we push them onto the stack. + unchecked_tys: Vec<(Ty<'tcx>, usize)>, + recursion_limit: Limit, + adt_components: F, +} + +impl<'tcx, F> NeedsDropTypes<'tcx, F> { + fn new( + tcx: TyCtxt<'tcx>, + param_env: ty::ParamEnv<'tcx>, + ty: Ty<'tcx>, + adt_components: F, + ) -> Self { + let mut seen_tys = FxHashSet::default(); + seen_tys.insert(ty); + Self { + tcx, + param_env, + seen_tys, + query_ty: ty, + unchecked_tys: vec![(ty, 0)], + recursion_limit: tcx.recursion_limit(), + adt_components, + } + } +} + +impl<'tcx, F, I> Iterator for NeedsDropTypes<'tcx, F> +where + F: Fn(ty::AdtDef<'tcx>, SubstsRef<'tcx>) -> NeedsDropResult<I>, + I: Iterator<Item = Ty<'tcx>>, +{ + type Item = NeedsDropResult<Ty<'tcx>>; + + fn next(&mut self) -> Option<NeedsDropResult<Ty<'tcx>>> { + let tcx = self.tcx; + + while let Some((ty, level)) = self.unchecked_tys.pop() { + if !self.recursion_limit.value_within_limit(level) { + // Not having a `Span` isn't great. But there's hopefully some other + // recursion limit error as well. + tcx.sess.span_err( + DUMMY_SP, + &format!("overflow while checking whether `{}` requires drop", self.query_ty), + ); + return Some(Err(AlwaysRequiresDrop)); + } + + let components = match needs_drop_components(ty, &tcx.data_layout) { + Err(e) => return Some(Err(e)), + Ok(components) => components, + }; + debug!("needs_drop_components({:?}) = {:?}", ty, components); + + let queue_type = move |this: &mut Self, component: Ty<'tcx>| { + if this.seen_tys.insert(component) { + this.unchecked_tys.push((component, level + 1)); + } + }; + + for component in components { + match *component.kind() { + _ if component.is_copy_modulo_regions(tcx.at(DUMMY_SP), self.param_env) => (), + + ty::Closure(_, substs) => { + queue_type(self, substs.as_closure().tupled_upvars_ty()); + } + + ty::Generator(def_id, substs, _) => { + let substs = substs.as_generator(); + queue_type(self, substs.tupled_upvars_ty()); + + let witness = substs.witness(); + let interior_tys = match witness.kind() { + &ty::GeneratorWitness(tys) => tcx.erase_late_bound_regions(tys), + _ => { + tcx.sess.delay_span_bug( + tcx.hir().span_if_local(def_id).unwrap_or(DUMMY_SP), + &format!("unexpected generator witness type {:?}", witness), + ); + return Some(Err(AlwaysRequiresDrop)); + } + }; + + for interior_ty in interior_tys { + queue_type(self, interior_ty); + } + } + + // Check for a `Drop` impl and whether this is a union or + // `ManuallyDrop`. If it's a struct or enum without a `Drop` + // impl then check whether the field types need `Drop`. + ty::Adt(adt_def, substs) => { + let tys = match (self.adt_components)(adt_def, substs) { + Err(e) => return Some(Err(e)), + Ok(tys) => tys, + }; + for required_ty in tys { + let required = tcx + .try_normalize_erasing_regions(self.param_env, required_ty) + .unwrap_or(required_ty); + + queue_type(self, required); + } + } + ty::Array(..) | ty::Opaque(..) | ty::Projection(..) | ty::Param(_) => { + if ty == component { + // Return the type to the caller: they may be able + // to normalize further than we can. + return Some(Ok(component)); + } else { + // Store the type for later. We can't return here + // because we would then lose any other components + // of the type. + queue_type(self, component); + } + } + _ => return Some(Err(AlwaysRequiresDrop)), + } + } + } + + None + } +} + +enum DtorType { + /// Type has a `Drop` but it is considered insignificant. + /// Check the query `adt_significant_drop_tys` for understanding + /// "significant" / "insignificant". + Insignificant, + + /// Type has a `Drop` implantation. + Significant, +} + +// This is a helper function for `adt_drop_tys` and `adt_significant_drop_tys`. +// Depending on the implantation of `adt_has_dtor`, it is used to check if the +// ADT has a destructor or if the ADT only has a significant destructor. For +// understanding significant destructor look at `adt_significant_drop_tys`. +fn drop_tys_helper<'tcx>( + tcx: TyCtxt<'tcx>, + ty: Ty<'tcx>, + param_env: rustc_middle::ty::ParamEnv<'tcx>, + adt_has_dtor: impl Fn(ty::AdtDef<'tcx>) -> Option<DtorType>, + only_significant: bool, +) -> impl Iterator<Item = NeedsDropResult<Ty<'tcx>>> { + fn with_query_cache<'tcx>( + tcx: TyCtxt<'tcx>, + iter: impl IntoIterator<Item = Ty<'tcx>>, + ) -> NeedsDropResult<Vec<Ty<'tcx>>> { + iter.into_iter().try_fold(Vec::new(), |mut vec, subty| { + match subty.kind() { + ty::Adt(adt_id, subst) => { + for subty in tcx.adt_drop_tys(adt_id.did())? { + vec.push(EarlyBinder(subty).subst(tcx, subst)); + } + } + _ => vec.push(subty), + }; + Ok(vec) + }) + } + + let adt_components = move |adt_def: ty::AdtDef<'tcx>, substs: SubstsRef<'tcx>| { + if adt_def.is_manually_drop() { + debug!("drop_tys_helper: `{:?}` is manually drop", adt_def); + Ok(Vec::new()) + } else if let Some(dtor_info) = adt_has_dtor(adt_def) { + match dtor_info { + DtorType::Significant => { + debug!("drop_tys_helper: `{:?}` implements `Drop`", adt_def); + Err(AlwaysRequiresDrop) + } + DtorType::Insignificant => { + debug!("drop_tys_helper: `{:?}` drop is insignificant", adt_def); + + // Since the destructor is insignificant, we just want to make sure all of + // the passed in type parameters are also insignificant. + // Eg: Vec<T> dtor is insignificant when T=i32 but significant when T=Mutex. + Ok(substs.types().collect()) + } + } + } else if adt_def.is_union() { + debug!("drop_tys_helper: `{:?}` is a union", adt_def); + Ok(Vec::new()) + } else { + let field_tys = adt_def.all_fields().map(|field| { + let r = tcx.bound_type_of(field.did).subst(tcx, substs); + debug!("drop_tys_helper: Subst into {:?} with {:?} gettng {:?}", field, substs, r); + r + }); + if only_significant { + // We can't recurse through the query system here because we might induce a cycle + Ok(field_tys.collect()) + } else { + // We can use the query system if we consider all drops significant. In that case, + // ADTs are `needs_drop` exactly if they `impl Drop` or if any of their "transitive" + // fields do. There can be no cycles here, because ADTs cannot contain themselves as + // fields. + with_query_cache(tcx, field_tys) + } + } + .map(|v| v.into_iter()) + }; + + NeedsDropTypes::new(tcx, param_env, ty, adt_components) +} + +fn adt_consider_insignificant_dtor<'tcx>( + tcx: TyCtxt<'tcx>, +) -> impl Fn(ty::AdtDef<'tcx>) -> Option<DtorType> + 'tcx { + move |adt_def: ty::AdtDef<'tcx>| { + let is_marked_insig = tcx.has_attr(adt_def.did(), sym::rustc_insignificant_dtor); + if is_marked_insig { + // In some cases like `std::collections::HashMap` where the struct is a wrapper around + // a type that is a Drop type, and the wrapped type (eg: `hashbrown::HashMap`) lies + // outside stdlib, we might choose to still annotate the the wrapper (std HashMap) with + // `rustc_insignificant_dtor`, even if the type itself doesn't have a `Drop` impl. + Some(DtorType::Insignificant) + } else if adt_def.destructor(tcx).is_some() { + // There is a Drop impl and the type isn't marked insignificant, therefore Drop must be + // significant. + Some(DtorType::Significant) + } else { + // No destructor found nor the type is annotated with `rustc_insignificant_dtor`, we + // treat this as the simple case of Drop impl for type. + None + } + } +} + +fn adt_drop_tys<'tcx>( + tcx: TyCtxt<'tcx>, + def_id: DefId, +) -> Result<&ty::List<Ty<'tcx>>, AlwaysRequiresDrop> { + // This is for the "adt_drop_tys" query, that considers all `Drop` impls, therefore all dtors are + // significant. + let adt_has_dtor = + |adt_def: ty::AdtDef<'tcx>| adt_def.destructor(tcx).map(|_| DtorType::Significant); + // `tcx.type_of(def_id)` identical to `tcx.make_adt(def, identity_substs)` + drop_tys_helper(tcx, tcx.type_of(def_id), tcx.param_env(def_id), adt_has_dtor, false) + .collect::<Result<Vec<_>, _>>() + .map(|components| tcx.intern_type_list(&components)) +} +// If `def_id` refers to a generic ADT, the queries above and below act as if they had been handed +// a `tcx.make_ty(def, identity_substs)` and as such it is legal to substitute the generic parameters +// of the ADT into the outputted `ty`s. +fn adt_significant_drop_tys( + tcx: TyCtxt<'_>, + def_id: DefId, +) -> Result<&ty::List<Ty<'_>>, AlwaysRequiresDrop> { + drop_tys_helper( + tcx, + tcx.type_of(def_id), // identical to `tcx.make_adt(def, identity_substs)` + tcx.param_env(def_id), + adt_consider_insignificant_dtor(tcx), + true, + ) + .collect::<Result<Vec<_>, _>>() + .map(|components| tcx.intern_type_list(&components)) +} + +pub(crate) fn provide(providers: &mut ty::query::Providers) { + *providers = ty::query::Providers { + needs_drop_raw, + has_significant_drop_raw, + adt_drop_tys, + adt_significant_drop_tys, + ..*providers + }; +} diff --git a/compiler/rustc_ty_utils/src/representability.rs b/compiler/rustc_ty_utils/src/representability.rs new file mode 100644 index 000000000..eded78916 --- /dev/null +++ b/compiler/rustc_ty_utils/src/representability.rs @@ -0,0 +1,386 @@ +//! Check whether a type is representable. +use rustc_data_structures::fx::FxHashMap; +use rustc_hir as hir; +use rustc_middle::ty::{self, Ty, TyCtxt}; +use rustc_span::Span; +use std::cmp; + +/// Describes whether a type is representable. For types that are not +/// representable, 'SelfRecursive' and 'ContainsRecursive' are used to +/// distinguish between types that are recursive with themselves and types that +/// contain a different recursive type. These cases can therefore be treated +/// differently when reporting errors. +/// +/// The ordering of the cases is significant. They are sorted so that cmp::max +/// will keep the "more erroneous" of two values. +#[derive(Clone, PartialOrd, Ord, Eq, PartialEq, Debug)] +pub enum Representability { + Representable, + ContainsRecursive, + /// Return a list of types that are included in themselves: + /// the spans where they are self-included, and (if found) + /// the HirId of the FieldDef that defines the self-inclusion. + SelfRecursive(Vec<(Span, Option<hir::HirId>)>), +} + +/// Check whether a type is representable. This means it cannot contain unboxed +/// structural recursion. This check is needed for structs and enums. +pub fn ty_is_representable<'tcx>( + tcx: TyCtxt<'tcx>, + ty: Ty<'tcx>, + sp: Span, + field_id: Option<hir::HirId>, +) -> Representability { + debug!("is_type_representable: {:?}", ty); + // To avoid a stack overflow when checking an enum variant or struct that + // contains a different, structurally recursive type, maintain a stack of + // seen types and check recursion for each of them (issues #3008, #3779, + // #74224, #84611). `shadow_seen` contains the full stack and `seen` only + // the one for the current type (e.g. if we have structs A and B, B contains + // a field of type A, and we're currently looking at B, then `seen` will be + // cleared when recursing to check A, but `shadow_seen` won't, so that we + // can catch cases of mutual recursion where A also contains B). + let mut seen: Vec<Ty<'_>> = Vec::new(); + let mut shadow_seen: Vec<ty::AdtDef<'tcx>> = Vec::new(); + let mut representable_cache = FxHashMap::default(); + let mut force_result = false; + let r = is_type_structurally_recursive( + tcx, + &mut seen, + &mut shadow_seen, + &mut representable_cache, + ty, + sp, + field_id, + &mut force_result, + ); + debug!("is_type_representable: {:?} is {:?}", ty, r); + r +} + +// Iterate until something non-representable is found +fn fold_repr<It: Iterator<Item = Representability>>(iter: It) -> Representability { + iter.fold(Representability::Representable, |r1, r2| match (r1, r2) { + (Representability::SelfRecursive(v1), Representability::SelfRecursive(v2)) => { + Representability::SelfRecursive(v1.into_iter().chain(v2).collect()) + } + (r1, r2) => cmp::max(r1, r2), + }) +} + +fn are_inner_types_recursive<'tcx>( + tcx: TyCtxt<'tcx>, + seen: &mut Vec<Ty<'tcx>>, + shadow_seen: &mut Vec<ty::AdtDef<'tcx>>, + representable_cache: &mut FxHashMap<Ty<'tcx>, Representability>, + ty: Ty<'tcx>, + sp: Span, + field_id: Option<hir::HirId>, + force_result: &mut bool, +) -> Representability { + debug!("are_inner_types_recursive({:?}, {:?}, {:?})", ty, seen, shadow_seen); + match ty.kind() { + ty::Tuple(fields) => { + // Find non representable + fold_repr(fields.iter().map(|ty| { + is_type_structurally_recursive( + tcx, + seen, + shadow_seen, + representable_cache, + ty, + sp, + field_id, + force_result, + ) + })) + } + // Fixed-length vectors. + // FIXME(#11924) Behavior undecided for zero-length vectors. + ty::Array(ty, _) => is_type_structurally_recursive( + tcx, + seen, + shadow_seen, + representable_cache, + *ty, + sp, + field_id, + force_result, + ), + ty::Adt(def, substs) => { + // Find non representable fields with their spans + fold_repr(def.all_fields().map(|field| { + let ty = field.ty(tcx, substs); + let (sp, field_id) = match field + .did + .as_local() + .map(|id| tcx.hir().local_def_id_to_hir_id(id)) + .and_then(|id| tcx.hir().find(id)) + { + Some(hir::Node::Field(field)) => (field.ty.span, Some(field.hir_id)), + _ => (sp, field_id), + }; + + let mut result = None; + + // First, we check whether the field type per se is representable. + // This catches cases as in #74224 and #84611. There is a special + // case related to mutual recursion, though; consider this example: + // + // struct A<T> { + // z: T, + // x: B<T>, + // } + // + // struct B<T> { + // y: A<T> + // } + // + // Here, without the following special case, both A and B are + // ContainsRecursive, which is a problem because we only report + // errors for SelfRecursive. We fix this by detecting this special + // case (shadow_seen.first() is the type we are originally + // interested in, and if we ever encounter the same AdtDef again, + // we know that it must be SelfRecursive) and "forcibly" returning + // SelfRecursive (by setting force_result, which tells the calling + // invocations of are_inner_types_representable to forward the + // result without adjusting). + if shadow_seen.len() > seen.len() && shadow_seen.first() == Some(def) { + *force_result = true; + result = Some(Representability::SelfRecursive(vec![(sp, field_id)])); + } + + if result == None { + result = Some(Representability::Representable); + + // Now, we check whether the field types per se are representable, e.g. + // for struct Foo { x: Option<Foo> }, we first check whether Option<_> + // by itself is representable (which it is), and the nesting of Foo + // will be detected later. This is necessary for #74224 and #84611. + + // If we have encountered an ADT definition that we have not seen + // before (no need to check them twice), recurse to see whether that + // definition is SelfRecursive. If so, we must be ContainsRecursive. + if shadow_seen.len() > 1 + && !shadow_seen + .iter() + .take(shadow_seen.len() - 1) + .any(|seen_def| seen_def == def) + { + let adt_def_id = def.did(); + let raw_adt_ty = tcx.type_of(adt_def_id); + debug!("are_inner_types_recursive: checking nested type: {:?}", raw_adt_ty); + + // Check independently whether the ADT is SelfRecursive. If so, + // we must be ContainsRecursive (except for the special case + // mentioned above). + let mut nested_seen: Vec<Ty<'_>> = vec![]; + result = Some( + match is_type_structurally_recursive( + tcx, + &mut nested_seen, + shadow_seen, + representable_cache, + raw_adt_ty, + sp, + field_id, + force_result, + ) { + Representability::SelfRecursive(_) => { + if *force_result { + Representability::SelfRecursive(vec![(sp, field_id)]) + } else { + Representability::ContainsRecursive + } + } + x => x, + }, + ); + } + + // We only enter the following block if the type looks representable + // so far. This is necessary for cases such as this one (#74224): + // + // struct A<T> { + // x: T, + // y: A<A<T>>, + // } + // + // struct B { + // z: A<usize> + // } + // + // When checking B, we recurse into A and check field y of type + // A<A<usize>>. We haven't seen this exact type before, so we recurse + // into A<A<usize>>, which contains, A<A<A<usize>>>, and so forth, + // ad infinitum. We can prevent this from happening by first checking + // A separately (the code above) and only checking for nested Bs if + // A actually looks representable (which it wouldn't in this example). + if result == Some(Representability::Representable) { + // Now, even if the type is representable (e.g. Option<_>), + // it might still contribute to a recursive type, e.g.: + // struct Foo { x: Option<Option<Foo>> } + // These cases are handled by passing the full `seen` + // stack to is_type_structurally_recursive (instead of the + // empty `nested_seen` above): + result = Some( + match is_type_structurally_recursive( + tcx, + seen, + shadow_seen, + representable_cache, + ty, + sp, + field_id, + force_result, + ) { + Representability::SelfRecursive(_) => { + Representability::SelfRecursive(vec![(sp, field_id)]) + } + x => x, + }, + ); + } + } + + result.unwrap() + })) + } + ty::Closure(..) => { + // this check is run on type definitions, so we don't expect + // to see closure types + bug!("requires check invoked on inapplicable type: {:?}", ty) + } + _ => Representability::Representable, + } +} + +fn same_adt<'tcx>(ty: Ty<'tcx>, def: ty::AdtDef<'tcx>) -> bool { + match *ty.kind() { + ty::Adt(ty_def, _) => ty_def == def, + _ => false, + } +} + +// Does the type `ty` directly (without indirection through a pointer) +// contain any types on stack `seen`? +fn is_type_structurally_recursive<'tcx>( + tcx: TyCtxt<'tcx>, + seen: &mut Vec<Ty<'tcx>>, + shadow_seen: &mut Vec<ty::AdtDef<'tcx>>, + representable_cache: &mut FxHashMap<Ty<'tcx>, Representability>, + ty: Ty<'tcx>, + sp: Span, + field_id: Option<hir::HirId>, + force_result: &mut bool, +) -> Representability { + debug!("is_type_structurally_recursive: {:?} {:?} {:?}", ty, sp, field_id); + if let Some(representability) = representable_cache.get(&ty) { + debug!( + "is_type_structurally_recursive: {:?} {:?} {:?} - (cached) {:?}", + ty, sp, field_id, representability + ); + return representability.clone(); + } + + let representability = is_type_structurally_recursive_inner( + tcx, + seen, + shadow_seen, + representable_cache, + ty, + sp, + field_id, + force_result, + ); + + representable_cache.insert(ty, representability.clone()); + representability +} + +fn is_type_structurally_recursive_inner<'tcx>( + tcx: TyCtxt<'tcx>, + seen: &mut Vec<Ty<'tcx>>, + shadow_seen: &mut Vec<ty::AdtDef<'tcx>>, + representable_cache: &mut FxHashMap<Ty<'tcx>, Representability>, + ty: Ty<'tcx>, + sp: Span, + field_id: Option<hir::HirId>, + force_result: &mut bool, +) -> Representability { + match ty.kind() { + ty::Adt(def, _) => { + { + debug!("is_type_structurally_recursive_inner: adt: {:?}, seen: {:?}", ty, seen); + + // Iterate through stack of previously seen types. + let mut iter = seen.iter(); + + // The first item in `seen` is the type we are actually curious about. + // We want to return SelfRecursive if this type contains itself. + // It is important that we DON'T take generic parameters into account + // for this check, so that Bar<T> in this example counts as SelfRecursive: + // + // struct Foo; + // struct Bar<T> { x: Bar<Foo> } + + if let Some(&seen_adt) = iter.next() { + if same_adt(seen_adt, *def) { + debug!("SelfRecursive: {:?} contains {:?}", seen_adt, ty); + return Representability::SelfRecursive(vec![(sp, field_id)]); + } + } + + // We also need to know whether the first item contains other types + // that are structurally recursive. If we don't catch this case, we + // will recurse infinitely for some inputs. + // + // It is important that we DO take generic parameters into account + // here, because nesting e.g. Options is allowed (as long as the + // definition of Option doesn't itself include an Option field, which + // would be a case of SelfRecursive above). The following, too, counts + // as SelfRecursive: + // + // struct Foo { Option<Option<Foo>> } + + for &seen_adt in iter { + if ty == seen_adt { + debug!("ContainsRecursive: {:?} contains {:?}", seen_adt, ty); + return Representability::ContainsRecursive; + } + } + } + + // For structs and enums, track all previously seen types by pushing them + // onto the 'seen' stack. + seen.push(ty); + shadow_seen.push(*def); + let out = are_inner_types_recursive( + tcx, + seen, + shadow_seen, + representable_cache, + ty, + sp, + field_id, + force_result, + ); + shadow_seen.pop(); + seen.pop(); + out + } + _ => { + // No need to push in other cases. + are_inner_types_recursive( + tcx, + seen, + shadow_seen, + representable_cache, + ty, + sp, + field_id, + force_result, + ) + } + } +} diff --git a/compiler/rustc_ty_utils/src/ty.rs b/compiler/rustc_ty_utils/src/ty.rs new file mode 100644 index 000000000..db0d45b86 --- /dev/null +++ b/compiler/rustc_ty_utils/src/ty.rs @@ -0,0 +1,481 @@ +use rustc_data_structures::fx::FxIndexSet; +use rustc_hir as hir; +use rustc_hir::def_id::DefId; +use rustc_middle::ty::subst::Subst; +use rustc_middle::ty::{self, Binder, Predicate, PredicateKind, ToPredicate, Ty, TyCtxt}; +use rustc_trait_selection::traits; + +fn sized_constraint_for_ty<'tcx>( + tcx: TyCtxt<'tcx>, + adtdef: ty::AdtDef<'tcx>, + ty: Ty<'tcx>, +) -> Vec<Ty<'tcx>> { + use rustc_type_ir::sty::TyKind::*; + + let result = match ty.kind() { + Bool | Char | Int(..) | Uint(..) | Float(..) | RawPtr(..) | Ref(..) | FnDef(..) + | FnPtr(_) | Array(..) | Closure(..) | Generator(..) | Never => vec![], + + Str | Dynamic(..) | Slice(_) | Foreign(..) | Error(_) | GeneratorWitness(..) => { + // these are never sized - return the target type + vec![ty] + } + + Tuple(ref tys) => match tys.last() { + None => vec![], + Some(&ty) => sized_constraint_for_ty(tcx, adtdef, ty), + }, + + Adt(adt, substs) => { + // recursive case + let adt_tys = adt.sized_constraint(tcx); + debug!("sized_constraint_for_ty({:?}) intermediate = {:?}", ty, adt_tys); + adt_tys + .0 + .iter() + .map(|ty| adt_tys.rebind(*ty).subst(tcx, substs)) + .flat_map(|ty| sized_constraint_for_ty(tcx, adtdef, ty)) + .collect() + } + + Projection(..) | Opaque(..) => { + // must calculate explicitly. + // FIXME: consider special-casing always-Sized projections + vec![ty] + } + + Param(..) => { + // perf hack: if there is a `T: Sized` bound, then + // we know that `T` is Sized and do not need to check + // it on the impl. + + let Some(sized_trait) = tcx.lang_items().sized_trait() else { return vec![ty] }; + let sized_predicate = ty::Binder::dummy(ty::TraitRef { + def_id: sized_trait, + substs: tcx.mk_substs_trait(ty, &[]), + }) + .without_const() + .to_predicate(tcx); + let predicates = tcx.predicates_of(adtdef.did()).predicates; + if predicates.iter().any(|(p, _)| *p == sized_predicate) { vec![] } else { vec![ty] } + } + + Placeholder(..) | Bound(..) | Infer(..) => { + bug!("unexpected type `{:?}` in sized_constraint_for_ty", ty) + } + }; + debug!("sized_constraint_for_ty({:?}) = {:?}", ty, result); + result +} + +fn impl_defaultness(tcx: TyCtxt<'_>, def_id: DefId) -> hir::Defaultness { + match tcx.hir().get_by_def_id(def_id.expect_local()) { + hir::Node::Item(hir::Item { kind: hir::ItemKind::Impl(impl_), .. }) => impl_.defaultness, + hir::Node::ImplItem(hir::ImplItem { defaultness, .. }) + | hir::Node::TraitItem(hir::TraitItem { defaultness, .. }) => *defaultness, + node => { + bug!("`impl_defaultness` called on {:?}", node); + } + } +} + +/// Calculates the `Sized` constraint. +/// +/// In fact, there are only a few options for the types in the constraint: +/// - an obviously-unsized type +/// - a type parameter or projection whose Sizedness can't be known +/// - a tuple of type parameters or projections, if there are multiple +/// such. +/// - an Error, if a type contained itself. The representability +/// check should catch this case. +fn adt_sized_constraint(tcx: TyCtxt<'_>, def_id: DefId) -> ty::AdtSizedConstraint<'_> { + let def = tcx.adt_def(def_id); + + let result = tcx.mk_type_list( + def.variants() + .iter() + .flat_map(|v| v.fields.last()) + .flat_map(|f| sized_constraint_for_ty(tcx, def, tcx.type_of(f.did))), + ); + + debug!("adt_sized_constraint: {:?} => {:?}", def, result); + + ty::AdtSizedConstraint(result) +} + +/// See `ParamEnv` struct definition for details. +#[instrument(level = "debug", skip(tcx))] +fn param_env(tcx: TyCtxt<'_>, def_id: DefId) -> ty::ParamEnv<'_> { + // The param_env of an impl Trait type is its defining function's param_env + if let Some(parent) = ty::is_impl_trait_defn(tcx, def_id) { + return param_env(tcx, parent.to_def_id()); + } + // Compute the bounds on Self and the type parameters. + + let ty::InstantiatedPredicates { mut predicates, .. } = + tcx.predicates_of(def_id).instantiate_identity(tcx); + + // Finally, we have to normalize the bounds in the environment, in + // case they contain any associated type projections. This process + // can yield errors if the put in illegal associated types, like + // `<i32 as Foo>::Bar` where `i32` does not implement `Foo`. We + // report these errors right here; this doesn't actually feel + // right to me, because constructing the environment feels like a + // kind of an "idempotent" action, but I'm not sure where would be + // a better place. In practice, we construct environments for + // every fn once during type checking, and we'll abort if there + // are any errors at that point, so outside of type inference you can be + // sure that this will succeed without errors anyway. + + if tcx.sess.opts.unstable_opts.chalk { + let environment = well_formed_types_in_env(tcx, def_id); + predicates.extend(environment); + } + + let local_did = def_id.as_local(); + let hir_id = local_did.map(|def_id| tcx.hir().local_def_id_to_hir_id(def_id)); + + let constness = match hir_id { + Some(hir_id) => match tcx.hir().get(hir_id) { + hir::Node::TraitItem(hir::TraitItem { kind: hir::TraitItemKind::Fn(..), .. }) + if tcx.is_const_default_method(def_id) => + { + hir::Constness::Const + } + + hir::Node::Item(hir::Item { kind: hir::ItemKind::Const(..), .. }) + | hir::Node::Item(hir::Item { kind: hir::ItemKind::Static(..), .. }) + | hir::Node::TraitItem(hir::TraitItem { + kind: hir::TraitItemKind::Const(..), .. + }) + | hir::Node::AnonConst(_) + | hir::Node::ImplItem(hir::ImplItem { kind: hir::ImplItemKind::Const(..), .. }) + | hir::Node::ImplItem(hir::ImplItem { + kind: + hir::ImplItemKind::Fn( + hir::FnSig { + header: hir::FnHeader { constness: hir::Constness::Const, .. }, + .. + }, + .., + ), + .. + }) => hir::Constness::Const, + + hir::Node::ImplItem(hir::ImplItem { + kind: hir::ImplItemKind::TyAlias(..) | hir::ImplItemKind::Fn(..), + .. + }) => { + let parent_hir_id = tcx.hir().get_parent_node(hir_id); + match tcx.hir().get(parent_hir_id) { + hir::Node::Item(hir::Item { + kind: hir::ItemKind::Impl(hir::Impl { constness, .. }), + .. + }) => *constness, + _ => span_bug!( + tcx.def_span(parent_hir_id.owner), + "impl item's parent node is not an impl", + ), + } + } + + hir::Node::Item(hir::Item { + kind: + hir::ItemKind::Fn(hir::FnSig { header: hir::FnHeader { constness, .. }, .. }, ..), + .. + }) + | hir::Node::TraitItem(hir::TraitItem { + kind: + hir::TraitItemKind::Fn( + hir::FnSig { header: hir::FnHeader { constness, .. }, .. }, + .., + ), + .. + }) + | hir::Node::Item(hir::Item { + kind: hir::ItemKind::Impl(hir::Impl { constness, .. }), + .. + }) => *constness, + + _ => hir::Constness::NotConst, + }, + None => hir::Constness::NotConst, + }; + + let unnormalized_env = ty::ParamEnv::new( + tcx.intern_predicates(&predicates), + traits::Reveal::UserFacing, + constness, + ); + + let body_id = + local_did.and_then(|id| tcx.hir().maybe_body_owned_by(id).map(|body| body.hir_id)); + let body_id = match body_id { + Some(id) => id, + None if hir_id.is_some() => hir_id.unwrap(), + _ => hir::CRATE_HIR_ID, + }; + + let cause = traits::ObligationCause::misc(tcx.def_span(def_id), body_id); + traits::normalize_param_env_or_error(tcx, unnormalized_env, cause) +} + +/// Elaborate the environment. +/// +/// Collect a list of `Predicate`'s used for building the `ParamEnv`. Adds `TypeWellFormedFromEnv`'s +/// that are assumed to be well-formed (because they come from the environment). +/// +/// Used only in chalk mode. +fn well_formed_types_in_env<'tcx>( + tcx: TyCtxt<'tcx>, + def_id: DefId, +) -> &'tcx ty::List<Predicate<'tcx>> { + use rustc_hir::{ForeignItemKind, ImplItemKind, ItemKind, Node, TraitItemKind}; + use rustc_middle::ty::subst::GenericArgKind; + + debug!("environment(def_id = {:?})", def_id); + + // The environment of an impl Trait type is its defining function's environment. + if let Some(parent) = ty::is_impl_trait_defn(tcx, def_id) { + return well_formed_types_in_env(tcx, parent.to_def_id()); + } + + // Compute the bounds on `Self` and the type parameters. + let ty::InstantiatedPredicates { predicates, .. } = + tcx.predicates_of(def_id).instantiate_identity(tcx); + + let clauses = predicates.into_iter(); + + if !def_id.is_local() { + return ty::List::empty(); + } + let node = tcx.hir().get_by_def_id(def_id.expect_local()); + + enum NodeKind { + TraitImpl, + InherentImpl, + Fn, + Other, + } + + let node_kind = match node { + Node::TraitItem(item) => match item.kind { + TraitItemKind::Fn(..) => NodeKind::Fn, + _ => NodeKind::Other, + }, + + Node::ImplItem(item) => match item.kind { + ImplItemKind::Fn(..) => NodeKind::Fn, + _ => NodeKind::Other, + }, + + Node::Item(item) => match item.kind { + ItemKind::Impl(hir::Impl { of_trait: Some(_), .. }) => NodeKind::TraitImpl, + ItemKind::Impl(hir::Impl { of_trait: None, .. }) => NodeKind::InherentImpl, + ItemKind::Fn(..) => NodeKind::Fn, + _ => NodeKind::Other, + }, + + Node::ForeignItem(item) => match item.kind { + ForeignItemKind::Fn(..) => NodeKind::Fn, + _ => NodeKind::Other, + }, + + // FIXME: closures? + _ => NodeKind::Other, + }; + + // FIXME(eddyb) isn't the unordered nature of this a hazard? + let mut inputs = FxIndexSet::default(); + + match node_kind { + // In a trait impl, we assume that the header trait ref and all its + // constituents are well-formed. + NodeKind::TraitImpl => { + let trait_ref = tcx.impl_trait_ref(def_id).expect("not an impl"); + + // FIXME(chalk): this has problems because of late-bound regions + //inputs.extend(trait_ref.substs.iter().flat_map(|arg| arg.walk())); + inputs.extend(trait_ref.substs.iter()); + } + + // In an inherent impl, we assume that the receiver type and all its + // constituents are well-formed. + NodeKind::InherentImpl => { + let self_ty = tcx.type_of(def_id); + inputs.extend(self_ty.walk()); + } + + // In an fn, we assume that the arguments and all their constituents are + // well-formed. + NodeKind::Fn => { + let fn_sig = tcx.fn_sig(def_id); + let fn_sig = tcx.liberate_late_bound_regions(def_id, fn_sig); + + inputs.extend(fn_sig.inputs().iter().flat_map(|ty| ty.walk())); + } + + NodeKind::Other => (), + } + let input_clauses = inputs.into_iter().filter_map(|arg| { + match arg.unpack() { + GenericArgKind::Type(ty) => { + let binder = Binder::dummy(PredicateKind::TypeWellFormedFromEnv(ty)); + Some(tcx.mk_predicate(binder)) + } + + // FIXME(eddyb) no WF conditions from lifetimes? + GenericArgKind::Lifetime(_) => None, + + // FIXME(eddyb) support const generics in Chalk + GenericArgKind::Const(_) => None, + } + }); + + tcx.mk_predicates(clauses.chain(input_clauses)) +} + +fn param_env_reveal_all_normalized(tcx: TyCtxt<'_>, def_id: DefId) -> ty::ParamEnv<'_> { + tcx.param_env(def_id).with_reveal_all_normalized(tcx) +} + +fn instance_def_size_estimate<'tcx>( + tcx: TyCtxt<'tcx>, + instance_def: ty::InstanceDef<'tcx>, +) -> usize { + use ty::InstanceDef; + + match instance_def { + InstanceDef::Item(..) | InstanceDef::DropGlue(..) => { + let mir = tcx.instance_mir(instance_def); + mir.basic_blocks().iter().map(|bb| bb.statements.len() + 1).sum() + } + // Estimate the size of other compiler-generated shims to be 1. + _ => 1, + } +} + +/// If `def_id` is an issue 33140 hack impl, returns its self type; otherwise, returns `None`. +/// +/// See [`ty::ImplOverlapKind::Issue33140`] for more details. +fn issue33140_self_ty(tcx: TyCtxt<'_>, def_id: DefId) -> Option<Ty<'_>> { + debug!("issue33140_self_ty({:?})", def_id); + + let trait_ref = tcx + .impl_trait_ref(def_id) + .unwrap_or_else(|| bug!("issue33140_self_ty called on inherent impl {:?}", def_id)); + + debug!("issue33140_self_ty({:?}), trait-ref={:?}", def_id, trait_ref); + + let is_marker_like = tcx.impl_polarity(def_id) == ty::ImplPolarity::Positive + && tcx.associated_item_def_ids(trait_ref.def_id).is_empty(); + + // Check whether these impls would be ok for a marker trait. + if !is_marker_like { + debug!("issue33140_self_ty - not marker-like!"); + return None; + } + + // impl must be `impl Trait for dyn Marker1 + Marker2 + ...` + if trait_ref.substs.len() != 1 { + debug!("issue33140_self_ty - impl has substs!"); + return None; + } + + let predicates = tcx.predicates_of(def_id); + if predicates.parent.is_some() || !predicates.predicates.is_empty() { + debug!("issue33140_self_ty - impl has predicates {:?}!", predicates); + return None; + } + + let self_ty = trait_ref.self_ty(); + let self_ty_matches = match self_ty.kind() { + ty::Dynamic(ref data, re) if re.is_static() => data.principal().is_none(), + _ => false, + }; + + if self_ty_matches { + debug!("issue33140_self_ty - MATCHES!"); + Some(self_ty) + } else { + debug!("issue33140_self_ty - non-matching self type"); + None + } +} + +/// Check if a function is async. +fn asyncness(tcx: TyCtxt<'_>, def_id: DefId) -> hir::IsAsync { + let node = tcx.hir().get_by_def_id(def_id.expect_local()); + if let Some(fn_kind) = node.fn_kind() { fn_kind.asyncness() } else { hir::IsAsync::NotAsync } +} + +/// Don't call this directly: use ``tcx.conservative_is_privately_uninhabited`` instead. +#[instrument(level = "debug", skip(tcx))] +pub fn conservative_is_privately_uninhabited_raw<'tcx>( + tcx: TyCtxt<'tcx>, + param_env_and: ty::ParamEnvAnd<'tcx, Ty<'tcx>>, +) -> bool { + let (param_env, ty) = param_env_and.into_parts(); + match ty.kind() { + ty::Never => { + debug!("ty::Never =>"); + true + } + ty::Adt(def, _) if def.is_union() => { + debug!("ty::Adt(def, _) if def.is_union() =>"); + // For now, `union`s are never considered uninhabited. + false + } + ty::Adt(def, substs) => { + debug!("ty::Adt(def, _) if def.is_not_union() =>"); + // Any ADT is uninhabited if either: + // (a) It has no variants (i.e. an empty `enum`); + // (b) Each of its variants (a single one in the case of a `struct`) has at least + // one uninhabited field. + def.variants().iter().all(|var| { + var.fields.iter().any(|field| { + let ty = tcx.bound_type_of(field.did).subst(tcx, substs); + tcx.conservative_is_privately_uninhabited(param_env.and(ty)) + }) + }) + } + ty::Tuple(fields) => { + debug!("ty::Tuple(..) =>"); + fields.iter().any(|ty| tcx.conservative_is_privately_uninhabited(param_env.and(ty))) + } + ty::Array(ty, len) => { + debug!("ty::Array(ty, len) =>"); + match len.try_eval_usize(tcx, param_env) { + Some(0) | None => false, + // If the array is definitely non-empty, it's uninhabited if + // the type of its elements is uninhabited. + Some(1..) => tcx.conservative_is_privately_uninhabited(param_env.and(*ty)), + } + } + ty::Ref(..) => { + debug!("ty::Ref(..) =>"); + // References to uninitialised memory is valid for any type, including + // uninhabited types, in unsafe code, so we treat all references as + // inhabited. + false + } + _ => { + debug!("_ =>"); + false + } + } +} + +pub fn provide(providers: &mut ty::query::Providers) { + *providers = ty::query::Providers { + asyncness, + adt_sized_constraint, + param_env, + param_env_reveal_all_normalized, + instance_def_size_estimate, + issue33140_self_ty, + impl_defaultness, + conservative_is_privately_uninhabited: conservative_is_privately_uninhabited_raw, + ..*providers + }; +} |