diff options
Diffstat (limited to 'third_party/rust/bindgen/ir/analysis/derive.rs')
| -rw-r--r-- | third_party/rust/bindgen/ir/analysis/derive.rs | 732 |
1 files changed, 732 insertions, 0 deletions
diff --git a/third_party/rust/bindgen/ir/analysis/derive.rs b/third_party/rust/bindgen/ir/analysis/derive.rs new file mode 100644 index 0000000000..d888cd558b --- /dev/null +++ b/third_party/rust/bindgen/ir/analysis/derive.rs @@ -0,0 +1,732 @@ +//! Determining which types for which we cannot emit `#[derive(Trait)]`. + +use std::fmt; + +use super::{generate_dependencies, ConstrainResult, MonotoneFramework}; +use crate::ir::analysis::has_vtable::HasVtable; +use crate::ir::comp::CompKind; +use crate::ir::context::{BindgenContext, ItemId}; +use crate::ir::derive::CanDerive; +use crate::ir::function::FunctionSig; +use crate::ir::item::{IsOpaque, Item}; +use crate::ir::layout::Layout; +use crate::ir::template::TemplateParameters; +use crate::ir::traversal::{EdgeKind, Trace}; +use crate::ir::ty::RUST_DERIVE_IN_ARRAY_LIMIT; +use crate::ir::ty::{Type, TypeKind}; +use crate::{Entry, HashMap, HashSet}; + +/// Which trait to consider when doing the `CannotDerive` analysis. +#[derive(Debug, Copy, Clone, Hash, PartialEq, Eq)] +pub enum DeriveTrait { + /// The `Copy` trait. + Copy, + /// The `Debug` trait. + Debug, + /// The `Default` trait. + Default, + /// The `Hash` trait. + Hash, + /// The `PartialEq` and `PartialOrd` traits. + PartialEqOrPartialOrd, +} + +/// An analysis that finds for each IR item whether a trait cannot be derived. +/// +/// We use the monotone constraint function `cannot_derive`, defined as follows +/// for type T: +/// +/// * If T is Opaque and the layout of the type is known, get this layout as an +/// opaquetype and check whether it can derive using trivial checks. +/// +/// * If T is Array, a trait cannot be derived if the array is incomplete, +/// if the length of the array is larger than the limit (unless the trait +/// allows it), or the trait cannot be derived for the type of data the array +/// contains. +/// +/// * If T is Vector, a trait cannot be derived if the trait cannot be derived +/// for the type of data the vector contains. +/// +/// * If T is a type alias, a templated alias or an indirection to another type, +/// the trait cannot be derived if the trait cannot be derived for type T +/// refers to. +/// +/// * If T is a compound type, the trait cannot be derived if the trait cannot +/// be derived for any of its base members or fields. +/// +/// * If T is an instantiation of an abstract template definition, the trait +/// cannot be derived if any of the template arguments or template definition +/// cannot derive the trait. +/// +/// * For all other (simple) types, compiler and standard library limitations +/// dictate whether the trait is implemented. +#[derive(Debug, Clone)] +pub struct CannotDerive<'ctx> { + ctx: &'ctx BindgenContext, + + derive_trait: DeriveTrait, + + // The incremental result of this analysis's computation. + // Contains information whether particular item can derive `derive_trait` + can_derive: HashMap<ItemId, CanDerive>, + + // Dependencies saying that if a key ItemId has been inserted into the + // `cannot_derive_partialeq_or_partialord` set, then each of the ids + // in Vec<ItemId> need to be considered again. + // + // This is a subset of the natural IR graph with reversed edges, where we + // only include the edges from the IR graph that can affect whether a type + // can derive `derive_trait`. + dependencies: HashMap<ItemId, Vec<ItemId>>, +} + +type EdgePredicate = fn(EdgeKind) -> bool; + +fn consider_edge_default(kind: EdgeKind) -> bool { + match kind { + // These are the only edges that can affect whether a type can derive + EdgeKind::BaseMember | + EdgeKind::Field | + EdgeKind::TypeReference | + EdgeKind::VarType | + EdgeKind::TemplateArgument | + EdgeKind::TemplateDeclaration | + EdgeKind::TemplateParameterDefinition => true, + + EdgeKind::Constructor | + EdgeKind::Destructor | + EdgeKind::FunctionReturn | + EdgeKind::FunctionParameter | + EdgeKind::InnerType | + EdgeKind::InnerVar | + EdgeKind::Method | + EdgeKind::Generic => false, + } +} + +impl<'ctx> CannotDerive<'ctx> { + fn insert<Id: Into<ItemId>>( + &mut self, + id: Id, + can_derive: CanDerive, + ) -> ConstrainResult { + let id = id.into(); + trace!( + "inserting {:?} can_derive<{}>={:?}", + id, + self.derive_trait, + can_derive + ); + + if let CanDerive::Yes = can_derive { + return ConstrainResult::Same; + } + + match self.can_derive.entry(id) { + Entry::Occupied(mut entry) => { + if *entry.get() < can_derive { + entry.insert(can_derive); + ConstrainResult::Changed + } else { + ConstrainResult::Same + } + } + Entry::Vacant(entry) => { + entry.insert(can_derive); + ConstrainResult::Changed + } + } + } + + fn constrain_type(&mut self, item: &Item, ty: &Type) -> CanDerive { + if !self.ctx.allowlisted_items().contains(&item.id()) { + let can_derive = self + .ctx + .blocklisted_type_implements_trait(item, self.derive_trait); + match can_derive { + CanDerive::Yes => trace!( + " blocklisted type explicitly implements {}", + self.derive_trait + ), + CanDerive::Manually => trace!( + " blocklisted type requires manual implementation of {}", + self.derive_trait + ), + CanDerive::No => trace!( + " cannot derive {} for blocklisted type", + self.derive_trait + ), + } + return can_derive; + } + + if self.derive_trait.not_by_name(self.ctx, item) { + trace!( + " cannot derive {} for explicitly excluded type", + self.derive_trait + ); + return CanDerive::No; + } + + trace!("ty: {:?}", ty); + if item.is_opaque(self.ctx, &()) { + if !self.derive_trait.can_derive_union() && + ty.is_union() && + self.ctx.options().rust_features().untagged_union + { + trace!( + " cannot derive {} for Rust unions", + self.derive_trait + ); + return CanDerive::No; + } + + let layout_can_derive = + ty.layout(self.ctx).map_or(CanDerive::Yes, |l| { + l.opaque().array_size_within_derive_limit(self.ctx) + }); + + match layout_can_derive { + CanDerive::Yes => { + trace!( + " we can trivially derive {} for the layout", + self.derive_trait + ); + } + _ => { + trace!( + " we cannot derive {} for the layout", + self.derive_trait + ); + } + }; + return layout_can_derive; + } + + match *ty.kind() { + // Handle the simple cases. These can derive traits without further + // information. + TypeKind::Void | + TypeKind::NullPtr | + TypeKind::Int(..) | + TypeKind::Complex(..) | + TypeKind::Float(..) | + TypeKind::Enum(..) | + TypeKind::TypeParam | + TypeKind::UnresolvedTypeRef(..) | + TypeKind::Reference(..) | + TypeKind::ObjCInterface(..) | + TypeKind::ObjCId | + TypeKind::ObjCSel => { + return self.derive_trait.can_derive_simple(ty.kind()); + } + TypeKind::Pointer(inner) => { + let inner_type = + self.ctx.resolve_type(inner).canonical_type(self.ctx); + if let TypeKind::Function(ref sig) = *inner_type.kind() { + self.derive_trait.can_derive_fnptr(sig) + } else { + self.derive_trait.can_derive_pointer() + } + } + TypeKind::Function(ref sig) => { + self.derive_trait.can_derive_fnptr(sig) + } + + // Complex cases need more information + TypeKind::Array(t, len) => { + let inner_type = + self.can_derive.get(&t.into()).cloned().unwrap_or_default(); + if inner_type != CanDerive::Yes { + trace!( + " arrays of T for which we cannot derive {} \ + also cannot derive {}", + self.derive_trait, + self.derive_trait + ); + return CanDerive::No; + } + + if len == 0 && !self.derive_trait.can_derive_incomplete_array() + { + trace!( + " cannot derive {} for incomplete arrays", + self.derive_trait + ); + return CanDerive::No; + } + + if self.derive_trait.can_derive_large_array(self.ctx) { + trace!(" array can derive {}", self.derive_trait); + return CanDerive::Yes; + } + + if len > RUST_DERIVE_IN_ARRAY_LIMIT { + trace!( + " array is too large to derive {}, but it may be implemented", self.derive_trait + ); + return CanDerive::Manually; + } + trace!( + " array is small enough to derive {}", + self.derive_trait + ); + CanDerive::Yes + } + TypeKind::Vector(t, len) => { + let inner_type = + self.can_derive.get(&t.into()).cloned().unwrap_or_default(); + if inner_type != CanDerive::Yes { + trace!( + " vectors of T for which we cannot derive {} \ + also cannot derive {}", + self.derive_trait, + self.derive_trait + ); + return CanDerive::No; + } + assert_ne!(len, 0, "vectors cannot have zero length"); + self.derive_trait.can_derive_vector() + } + + TypeKind::Comp(ref info) => { + assert!( + !info.has_non_type_template_params(), + "The early ty.is_opaque check should have handled this case" + ); + + if !self.derive_trait.can_derive_compound_forward_decl() && + info.is_forward_declaration() + { + trace!( + " cannot derive {} for forward decls", + self.derive_trait + ); + return CanDerive::No; + } + + // NOTE: Take into account that while unions in C and C++ are copied by + // default, the may have an explicit destructor in C++, so we can't + // defer this check just for the union case. + if !self.derive_trait.can_derive_compound_with_destructor() && + self.ctx.lookup_has_destructor( + item.id().expect_type_id(self.ctx), + ) + { + trace!( + " comp has destructor which cannot derive {}", + self.derive_trait + ); + return CanDerive::No; + } + + if info.kind() == CompKind::Union { + if self.derive_trait.can_derive_union() { + if self.ctx.options().rust_features().untagged_union && + // https://github.com/rust-lang/rust/issues/36640 + (!info.self_template_params(self.ctx).is_empty() || + !item.all_template_params(self.ctx).is_empty()) + { + trace!( + " cannot derive {} for Rust union because issue 36640", self.derive_trait + ); + return CanDerive::No; + } + // fall through to be same as non-union handling + } else { + if self.ctx.options().rust_features().untagged_union { + trace!( + " cannot derive {} for Rust unions", + self.derive_trait + ); + return CanDerive::No; + } + + let layout_can_derive = + ty.layout(self.ctx).map_or(CanDerive::Yes, |l| { + l.opaque() + .array_size_within_derive_limit(self.ctx) + }); + match layout_can_derive { + CanDerive::Yes => { + trace!( + " union layout can trivially derive {}", + self.derive_trait + ); + } + _ => { + trace!( + " union layout cannot derive {}", + self.derive_trait + ); + } + }; + return layout_can_derive; + } + } + + if !self.derive_trait.can_derive_compound_with_vtable() && + item.has_vtable(self.ctx) + { + trace!( + " cannot derive {} for comp with vtable", + self.derive_trait + ); + return CanDerive::No; + } + + // Bitfield units are always represented as arrays of u8, but + // they're not traced as arrays, so we need to check here + // instead. + if !self.derive_trait.can_derive_large_array(self.ctx) && + info.has_too_large_bitfield_unit() && + !item.is_opaque(self.ctx, &()) + { + trace!( + " cannot derive {} for comp with too large bitfield unit", + self.derive_trait + ); + return CanDerive::No; + } + + let pred = self.derive_trait.consider_edge_comp(); + self.constrain_join(item, pred) + } + + TypeKind::ResolvedTypeRef(..) | + TypeKind::TemplateAlias(..) | + TypeKind::Alias(..) | + TypeKind::BlockPointer(..) => { + let pred = self.derive_trait.consider_edge_typeref(); + self.constrain_join(item, pred) + } + + TypeKind::TemplateInstantiation(..) => { + let pred = self.derive_trait.consider_edge_tmpl_inst(); + self.constrain_join(item, pred) + } + + TypeKind::Opaque => unreachable!( + "The early ty.is_opaque check should have handled this case" + ), + } + } + + fn constrain_join( + &mut self, + item: &Item, + consider_edge: EdgePredicate, + ) -> CanDerive { + let mut candidate = None; + + item.trace( + self.ctx, + &mut |sub_id, edge_kind| { + // Ignore ourselves, since union with ourself is a + // no-op. Ignore edges that aren't relevant to the + // analysis. + if sub_id == item.id() || !consider_edge(edge_kind) { + return; + } + + let can_derive = self.can_derive + .get(&sub_id) + .cloned() + .unwrap_or_default(); + + match can_derive { + CanDerive::Yes => trace!(" member {:?} can derive {}", sub_id, self.derive_trait), + CanDerive::Manually => trace!(" member {:?} cannot derive {}, but it may be implemented", sub_id, self.derive_trait), + CanDerive::No => trace!(" member {:?} cannot derive {}", sub_id, self.derive_trait), + } + + *candidate.get_or_insert(CanDerive::Yes) |= can_derive; + }, + &(), + ); + + if candidate.is_none() { + trace!( + " can derive {} because there are no members", + self.derive_trait + ); + } + candidate.unwrap_or_default() + } +} + +impl DeriveTrait { + fn not_by_name(&self, ctx: &BindgenContext, item: &Item) -> bool { + match self { + DeriveTrait::Copy => ctx.no_copy_by_name(item), + DeriveTrait::Debug => ctx.no_debug_by_name(item), + DeriveTrait::Default => ctx.no_default_by_name(item), + DeriveTrait::Hash => ctx.no_hash_by_name(item), + DeriveTrait::PartialEqOrPartialOrd => { + ctx.no_partialeq_by_name(item) + } + } + } + + fn consider_edge_comp(&self) -> EdgePredicate { + match self { + DeriveTrait::PartialEqOrPartialOrd => consider_edge_default, + _ => |kind| matches!(kind, EdgeKind::BaseMember | EdgeKind::Field), + } + } + + fn consider_edge_typeref(&self) -> EdgePredicate { + match self { + DeriveTrait::PartialEqOrPartialOrd => consider_edge_default, + _ => |kind| kind == EdgeKind::TypeReference, + } + } + + fn consider_edge_tmpl_inst(&self) -> EdgePredicate { + match self { + DeriveTrait::PartialEqOrPartialOrd => consider_edge_default, + _ => |kind| { + matches!( + kind, + EdgeKind::TemplateArgument | EdgeKind::TemplateDeclaration + ) + }, + } + } + + fn can_derive_large_array(&self, ctx: &BindgenContext) -> bool { + if ctx.options().rust_features().larger_arrays { + !matches!(self, DeriveTrait::Default) + } else { + matches!(self, DeriveTrait::Copy) + } + } + + fn can_derive_union(&self) -> bool { + matches!(self, DeriveTrait::Copy) + } + + fn can_derive_compound_with_destructor(&self) -> bool { + !matches!(self, DeriveTrait::Copy) + } + + fn can_derive_compound_with_vtable(&self) -> bool { + !matches!(self, DeriveTrait::Default) + } + + fn can_derive_compound_forward_decl(&self) -> bool { + matches!(self, DeriveTrait::Copy | DeriveTrait::Debug) + } + + fn can_derive_incomplete_array(&self) -> bool { + !matches!( + self, + DeriveTrait::Copy | + DeriveTrait::Hash | + DeriveTrait::PartialEqOrPartialOrd + ) + } + + fn can_derive_fnptr(&self, f: &FunctionSig) -> CanDerive { + match (self, f.function_pointers_can_derive()) { + (DeriveTrait::Copy, _) | (DeriveTrait::Default, _) | (_, true) => { + trace!(" function pointer can derive {}", self); + CanDerive::Yes + } + (DeriveTrait::Debug, false) => { + trace!(" function pointer cannot derive {}, but it may be implemented", self); + CanDerive::Manually + } + (_, false) => { + trace!(" function pointer cannot derive {}", self); + CanDerive::No + } + } + } + + fn can_derive_vector(&self) -> CanDerive { + match self { + DeriveTrait::PartialEqOrPartialOrd => { + // FIXME: vectors always can derive PartialEq, but they should + // not derive PartialOrd: + // https://github.com/rust-lang-nursery/packed_simd/issues/48 + trace!(" vectors cannot derive PartialOrd"); + CanDerive::No + } + _ => { + trace!(" vector can derive {}", self); + CanDerive::Yes + } + } + } + + fn can_derive_pointer(&self) -> CanDerive { + match self { + DeriveTrait::Default => { + trace!(" pointer cannot derive Default"); + CanDerive::No + } + _ => { + trace!(" pointer can derive {}", self); + CanDerive::Yes + } + } + } + + fn can_derive_simple(&self, kind: &TypeKind) -> CanDerive { + match (self, kind) { + // === Default === + (DeriveTrait::Default, TypeKind::Void) | + (DeriveTrait::Default, TypeKind::NullPtr) | + (DeriveTrait::Default, TypeKind::Enum(..)) | + (DeriveTrait::Default, TypeKind::Reference(..)) | + (DeriveTrait::Default, TypeKind::TypeParam) | + (DeriveTrait::Default, TypeKind::ObjCInterface(..)) | + (DeriveTrait::Default, TypeKind::ObjCId) | + (DeriveTrait::Default, TypeKind::ObjCSel) => { + trace!(" types that always cannot derive Default"); + CanDerive::No + } + (DeriveTrait::Default, TypeKind::UnresolvedTypeRef(..)) => { + unreachable!( + "Type with unresolved type ref can't reach derive default" + ) + } + // === Hash === + (DeriveTrait::Hash, TypeKind::Float(..)) | + (DeriveTrait::Hash, TypeKind::Complex(..)) => { + trace!(" float cannot derive Hash"); + CanDerive::No + } + // === others === + _ => { + trace!(" simple type that can always derive {}", self); + CanDerive::Yes + } + } + } +} + +impl fmt::Display for DeriveTrait { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + let s = match self { + DeriveTrait::Copy => "Copy", + DeriveTrait::Debug => "Debug", + DeriveTrait::Default => "Default", + DeriveTrait::Hash => "Hash", + DeriveTrait::PartialEqOrPartialOrd => "PartialEq/PartialOrd", + }; + s.fmt(f) + } +} + +impl<'ctx> MonotoneFramework for CannotDerive<'ctx> { + type Node = ItemId; + type Extra = (&'ctx BindgenContext, DeriveTrait); + type Output = HashMap<ItemId, CanDerive>; + + fn new( + (ctx, derive_trait): (&'ctx BindgenContext, DeriveTrait), + ) -> CannotDerive<'ctx> { + let can_derive = HashMap::default(); + let dependencies = generate_dependencies(ctx, consider_edge_default); + + CannotDerive { + ctx, + derive_trait, + can_derive, + dependencies, + } + } + + fn initial_worklist(&self) -> Vec<ItemId> { + // The transitive closure of all allowlisted items, including explicitly + // blocklisted items. + self.ctx + .allowlisted_items() + .iter() + .cloned() + .flat_map(|i| { + let mut reachable = vec![i]; + i.trace( + self.ctx, + &mut |s, _| { + reachable.push(s); + }, + &(), + ); + reachable + }) + .collect() + } + + fn constrain(&mut self, id: ItemId) -> ConstrainResult { + trace!("constrain: {:?}", id); + + if let Some(CanDerive::No) = self.can_derive.get(&id).cloned() { + trace!(" already know it cannot derive {}", self.derive_trait); + return ConstrainResult::Same; + } + + let item = self.ctx.resolve_item(id); + let can_derive = match item.as_type() { + Some(ty) => { + let mut can_derive = self.constrain_type(item, ty); + if let CanDerive::Yes = can_derive { + let is_reached_limit = + |l: Layout| l.align > RUST_DERIVE_IN_ARRAY_LIMIT; + if !self.derive_trait.can_derive_large_array(self.ctx) && + ty.layout(self.ctx).map_or(false, is_reached_limit) + { + // We have to be conservative: the struct *could* have enough + // padding that we emit an array that is longer than + // `RUST_DERIVE_IN_ARRAY_LIMIT`. If we moved padding calculations + // into the IR and computed them before this analysis, then we could + // be precise rather than conservative here. + can_derive = CanDerive::Manually; + } + } + can_derive + } + None => self.constrain_join(item, consider_edge_default), + }; + + self.insert(id, can_derive) + } + + fn each_depending_on<F>(&self, id: ItemId, mut f: F) + where + F: FnMut(ItemId), + { + if let Some(edges) = self.dependencies.get(&id) { + for item in edges { + trace!("enqueue {:?} into worklist", item); + f(*item); + } + } + } +} + +impl<'ctx> From<CannotDerive<'ctx>> for HashMap<ItemId, CanDerive> { + fn from(analysis: CannotDerive<'ctx>) -> Self { + extra_assert!(analysis + .can_derive + .values() + .all(|v| *v != CanDerive::Yes)); + + analysis.can_derive + } +} + +/// Convert a `HashMap<ItemId, CanDerive>` into a `HashSet<ItemId>`. +/// +/// Elements that are not `CanDerive::Yes` are kept in the set, so that it +/// represents all items that cannot derive. +pub fn as_cannot_derive_set( + can_derive: HashMap<ItemId, CanDerive>, +) -> HashSet<ItemId> { + can_derive + .into_iter() + .filter_map(|(k, v)| if v != CanDerive::Yes { Some(k) } else { None }) + .collect() +} |