diff options
Diffstat (limited to 'third_party/rust/bindgen/ir/analysis/template_params.rs')
| -rw-r--r-- | third_party/rust/bindgen/ir/analysis/template_params.rs | 607 |
1 files changed, 607 insertions, 0 deletions
diff --git a/third_party/rust/bindgen/ir/analysis/template_params.rs b/third_party/rust/bindgen/ir/analysis/template_params.rs new file mode 100644 index 0000000000..f4f0c59d71 --- /dev/null +++ b/third_party/rust/bindgen/ir/analysis/template_params.rs @@ -0,0 +1,607 @@ +//! Discover which template type parameters are actually used. +//! +//! ### Why do we care? +//! +//! C++ allows ignoring template parameters, while Rust does not. Usually we can +//! blindly stick a `PhantomData<T>` inside a generic Rust struct to make up for +//! this. That doesn't work for templated type aliases, however: +//! +//! ```C++ +//! template <typename T> +//! using Fml = int; +//! ``` +//! +//! If we generate the naive Rust code for this alias, we get: +//! +//! ```ignore +//! pub type Fml<T> = ::std::os::raw::int; +//! ``` +//! +//! And this is rejected by `rustc` due to the unused type parameter. +//! +//! (Aside: in these simple cases, `libclang` will often just give us the +//! aliased type directly, and we will never even know we were dealing with +//! aliases, let alone templated aliases. It's the more convoluted scenarios +//! where we get to have some fun...) +//! +//! For such problematic template aliases, we could generate a tuple whose +//! second member is a `PhantomData<T>`. Or, if we wanted to go the extra mile, +//! we could even generate some smarter wrapper that implements `Deref`, +//! `DerefMut`, `From`, `Into`, `AsRef`, and `AsMut` to the actually aliased +//! type. However, this is still lackluster: +//! +//! 1. Even with a billion conversion-trait implementations, using the generated +//! bindings is rather un-ergonomic. +//! 2. With either of these solutions, we need to keep track of which aliases +//! we've transformed like this in order to generate correct uses of the +//! wrapped type. +//! +//! Given that we have to properly track which template parameters ended up used +//! for (2), we might as well leverage that information to make ergonomic +//! bindings that don't contain any unused type parameters at all, and +//! completely avoid the pain of (1). +//! +//! ### How do we determine which template parameters are used? +//! +//! Determining which template parameters are actually used is a trickier +//! problem than it might seem at a glance. On the one hand, trivial uses are +//! easy to detect: +//! +//! ```C++ +//! template <typename T> +//! class Foo { +//! T trivial_use_of_t; +//! }; +//! ``` +//! +//! It gets harder when determining if one template parameter is used depends on +//! determining if another template parameter is used. In this example, whether +//! `U` is used depends on whether `T` is used. +//! +//! ```C++ +//! template <typename T> +//! class DoesntUseT { +//! int x; +//! }; +//! +//! template <typename U> +//! class Fml { +//! DoesntUseT<U> lololol; +//! }; +//! ``` +//! +//! We can express the set of used template parameters as a constraint solving +//! problem (where the set of template parameters used by a given IR item is the +//! union of its sub-item's used template parameters) and iterate to a +//! fixed-point. +//! +//! We use the `ir::analysis::MonotoneFramework` infrastructure for this +//! fix-point analysis, where our lattice is the mapping from each IR item to +//! the powerset of the template parameters that appear in the input C++ header, +//! our join function is set union. The set of template parameters appearing in +//! the program is finite, as is the number of IR items. We start at our +//! lattice's bottom element: every item mapping to an empty set of template +//! parameters. Our analysis only adds members to each item's set of used +//! template parameters, never removes them, so it is monotone. Because our +//! lattice is finite and our constraint function is monotone, iteration to a +//! fix-point will terminate. +//! +//! See `src/ir/analysis.rs` for more. + +use super::{ConstrainResult, MonotoneFramework}; +use crate::ir::context::{BindgenContext, ItemId}; +use crate::ir::item::{Item, ItemSet}; +use crate::ir::template::{TemplateInstantiation, TemplateParameters}; +use crate::ir::traversal::{EdgeKind, Trace}; +use crate::ir::ty::TypeKind; +use crate::{HashMap, HashSet}; + +/// An analysis that finds for each IR item its set of template parameters that +/// it uses. +/// +/// We use the monotone constraint function `template_param_usage`, defined as +/// follows: +/// +/// * If `T` is a named template type parameter, it trivially uses itself: +/// +/// ```ignore +/// template_param_usage(T) = { T } +/// ``` +/// +/// * If `inst` is a template instantiation, `inst.args` are the template +/// instantiation's template arguments, `inst.def` is the template definition +/// being instantiated, and `inst.def.params` is the template definition's +/// template parameters, then the instantiation's usage is the union of each +/// of its arguments' usages *if* the corresponding template parameter is in +/// turn used by the template definition: +/// +/// ```ignore +/// template_param_usage(inst) = union( +/// template_param_usage(inst.args[i]) +/// for i in 0..length(inst.args.length) +/// if inst.def.params[i] in template_param_usage(inst.def) +/// ) +/// ``` +/// +/// * Finally, for all other IR item kinds, we use our lattice's `join` +/// operation: set union with each successor of the given item's template +/// parameter usage: +/// +/// ```ignore +/// template_param_usage(v) = +/// union(template_param_usage(w) for w in successors(v)) +/// ``` +/// +/// Note that we ignore certain edges in the graph, such as edges from a +/// template declaration to its template parameters' definitions for this +/// analysis. If we didn't, then we would mistakenly determine that ever +/// template parameter is always used. +/// +/// The final wrinkle is handling of blocklisted types. Normally, we say that +/// the set of allowlisted items is the transitive closure of items explicitly +/// called out for allowlisting, *without* any items explicitly called out as +/// blocklisted. However, for the purposes of this analysis's correctness, we +/// simplify and consider run the analysis on the full transitive closure of +/// allowlisted items. We do, however, treat instantiations of blocklisted items +/// specially; see `constrain_instantiation_of_blocklisted_template` and its +/// documentation for details. +#[derive(Debug, Clone)] +pub struct UsedTemplateParameters<'ctx> { + ctx: &'ctx BindgenContext, + + // The Option is only there for temporary moves out of the hash map. See the + // comments in `UsedTemplateParameters::constrain` below. + used: HashMap<ItemId, Option<ItemSet>>, + + dependencies: HashMap<ItemId, Vec<ItemId>>, + + // The set of allowlisted items, without any blocklisted items reachable + // from the allowlisted items which would otherwise be considered + // allowlisted as well. + allowlisted_items: HashSet<ItemId>, +} + +impl<'ctx> UsedTemplateParameters<'ctx> { + fn consider_edge(kind: EdgeKind) -> bool { + match kind { + // For each of these kinds of edges, if the referent uses a template + // parameter, then it should be considered that the origin of the + // edge also uses the template parameter. + EdgeKind::TemplateArgument | + EdgeKind::BaseMember | + EdgeKind::Field | + EdgeKind::Constructor | + EdgeKind::Destructor | + EdgeKind::VarType | + EdgeKind::FunctionReturn | + EdgeKind::FunctionParameter | + EdgeKind::TypeReference => true, + + // An inner var or type using a template parameter is orthogonal + // from whether we use it. See template-param-usage-{6,11}.hpp. + EdgeKind::InnerVar | EdgeKind::InnerType => false, + + // We can't emit machine code for new monomorphizations of class + // templates' methods (and don't detect explicit instantiations) so + // we must ignore template parameters that are only used by + // methods. This doesn't apply to a function type's return or + // parameter types, however, because of type aliases of function + // pointers that use template parameters, eg + // tests/headers/struct_with_typedef_template_arg.hpp + EdgeKind::Method => false, + + // If we considered these edges, we would end up mistakenly claiming + // that every template parameter always used. + EdgeKind::TemplateDeclaration | + EdgeKind::TemplateParameterDefinition => false, + + // Since we have to be careful about which edges we consider for + // this analysis to be correct, we ignore generic edges. We also + // avoid a `_` wild card to force authors of new edge kinds to + // determine whether they need to be considered by this analysis. + EdgeKind::Generic => false, + } + } + + fn take_this_id_usage_set<Id: Into<ItemId>>( + &mut self, + this_id: Id, + ) -> ItemSet { + let this_id = this_id.into(); + self.used + .get_mut(&this_id) + .expect( + "Should have a set of used template params for every item \ + id", + ) + .take() + .expect( + "Should maintain the invariant that all used template param \ + sets are `Some` upon entry of `constrain`", + ) + } + + /// We say that blocklisted items use all of their template parameters. The + /// blocklisted type is most likely implemented explicitly by the user, + /// since it won't be in the generated bindings, and we don't know exactly + /// what they'll to with template parameters, but we can push the issue down + /// the line to them. + fn constrain_instantiation_of_blocklisted_template( + &self, + this_id: ItemId, + used_by_this_id: &mut ItemSet, + instantiation: &TemplateInstantiation, + ) { + trace!( + " instantiation of blocklisted template, uses all template \ + arguments" + ); + + let args = instantiation + .template_arguments() + .iter() + .map(|a| { + a.into_resolver() + .through_type_refs() + .through_type_aliases() + .resolve(self.ctx) + .id() + }) + .filter(|a| *a != this_id) + .flat_map(|a| { + self.used + .get(&a) + .expect("Should have a used entry for the template arg") + .as_ref() + .expect( + "Because a != this_id, and all used template \ + param sets other than this_id's are `Some`, \ + a's used template param set should be `Some`", + ) + .iter() + .cloned() + }); + + used_by_this_id.extend(args); + } + + /// A template instantiation's concrete template argument is only used if + /// the template definition uses the corresponding template parameter. + fn constrain_instantiation( + &self, + this_id: ItemId, + used_by_this_id: &mut ItemSet, + instantiation: &TemplateInstantiation, + ) { + trace!(" template instantiation"); + + let decl = self.ctx.resolve_type(instantiation.template_definition()); + let args = instantiation.template_arguments(); + + let params = decl.self_template_params(self.ctx); + + debug_assert!(this_id != instantiation.template_definition()); + let used_by_def = self.used + .get(&instantiation.template_definition().into()) + .expect("Should have a used entry for instantiation's template definition") + .as_ref() + .expect("And it should be Some because only this_id's set is None, and an \ + instantiation's template definition should never be the \ + instantiation itself"); + + for (arg, param) in args.iter().zip(params.iter()) { + trace!( + " instantiation's argument {:?} is used if definition's \ + parameter {:?} is used", + arg, + param + ); + + if used_by_def.contains(¶m.into()) { + trace!(" param is used by template definition"); + + let arg = arg + .into_resolver() + .through_type_refs() + .through_type_aliases() + .resolve(self.ctx) + .id(); + + if arg == this_id { + continue; + } + + let used_by_arg = self + .used + .get(&arg) + .expect("Should have a used entry for the template arg") + .as_ref() + .expect( + "Because arg != this_id, and all used template \ + param sets other than this_id's are `Some`, \ + arg's used template param set should be \ + `Some`", + ) + .iter() + .cloned(); + used_by_this_id.extend(used_by_arg); + } + } + } + + /// The join operation on our lattice: the set union of all of this id's + /// successors. + fn constrain_join(&self, used_by_this_id: &mut ItemSet, item: &Item) { + trace!(" other item: join with successors' usage"); + + 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() || !Self::consider_edge(edge_kind) { + return; + } + + let used_by_sub_id = self + .used + .get(&sub_id) + .expect("Should have a used set for the sub_id successor") + .as_ref() + .expect( + "Because sub_id != id, and all used template \ + param sets other than id's are `Some`, \ + sub_id's used template param set should be \ + `Some`", + ) + .iter() + .cloned(); + + trace!( + " union with {:?}'s usage: {:?}", + sub_id, + used_by_sub_id.clone().collect::<Vec<_>>() + ); + + used_by_this_id.extend(used_by_sub_id); + }, + &(), + ); + } +} + +impl<'ctx> MonotoneFramework for UsedTemplateParameters<'ctx> { + type Node = ItemId; + type Extra = &'ctx BindgenContext; + type Output = HashMap<ItemId, ItemSet>; + + fn new(ctx: &'ctx BindgenContext) -> UsedTemplateParameters<'ctx> { + let mut used = HashMap::default(); + let mut dependencies = HashMap::default(); + let allowlisted_items: HashSet<_> = + ctx.allowlisted_items().iter().cloned().collect(); + + let allowlisted_and_blocklisted_items: ItemSet = allowlisted_items + .iter() + .cloned() + .flat_map(|i| { + let mut reachable = vec![i]; + i.trace( + ctx, + &mut |s, _| { + reachable.push(s); + }, + &(), + ); + reachable + }) + .collect(); + + for item in allowlisted_and_blocklisted_items { + dependencies.entry(item).or_insert_with(Vec::new); + used.entry(item).or_insert_with(|| Some(ItemSet::new())); + + { + // We reverse our natural IR graph edges to find dependencies + // between nodes. + item.trace( + ctx, + &mut |sub_item: ItemId, _| { + used.entry(sub_item) + .or_insert_with(|| Some(ItemSet::new())); + dependencies + .entry(sub_item) + .or_insert_with(Vec::new) + .push(item); + }, + &(), + ); + } + + // Additionally, whether a template instantiation's template + // arguments are used depends on whether the template declaration's + // generic template parameters are used. + let item_kind = + ctx.resolve_item(item).as_type().map(|ty| ty.kind()); + if let Some(TypeKind::TemplateInstantiation(inst)) = item_kind { + let decl = ctx.resolve_type(inst.template_definition()); + let args = inst.template_arguments(); + + // Although template definitions should always have + // template parameters, there is a single exception: + // opaque templates. Hence the unwrap_or. + let params = decl.self_template_params(ctx); + + for (arg, param) in args.iter().zip(params.iter()) { + let arg = arg + .into_resolver() + .through_type_aliases() + .through_type_refs() + .resolve(ctx) + .id(); + + let param = param + .into_resolver() + .through_type_aliases() + .through_type_refs() + .resolve(ctx) + .id(); + + used.entry(arg).or_insert_with(|| Some(ItemSet::new())); + used.entry(param).or_insert_with(|| Some(ItemSet::new())); + + dependencies + .entry(arg) + .or_insert_with(Vec::new) + .push(param); + } + } + } + + if cfg!(feature = "testing_only_extra_assertions") { + // Invariant: The `used` map has an entry for every allowlisted + // item, as well as all explicitly blocklisted items that are + // reachable from allowlisted items. + // + // Invariant: the `dependencies` map has an entry for every + // allowlisted item. + // + // (This is so that every item we call `constrain` on is guaranteed + // to have a set of template parameters, and we can allow + // blocklisted templates to use all of their parameters). + for item in allowlisted_items.iter() { + extra_assert!(used.contains_key(item)); + extra_assert!(dependencies.contains_key(item)); + item.trace( + ctx, + &mut |sub_item, _| { + extra_assert!(used.contains_key(&sub_item)); + extra_assert!(dependencies.contains_key(&sub_item)); + }, + &(), + ) + } + } + + UsedTemplateParameters { + ctx, + used, + dependencies, + allowlisted_items, + } + } + + 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 { + // Invariant: all hash map entries' values are `Some` upon entering and + // exiting this method. + extra_assert!(self.used.values().all(|v| v.is_some())); + + // Take the set for this id out of the hash map while we mutate it based + // on other hash map entries. We *must* put it back into the hash map at + // the end of this method. This allows us to side-step HashMap's lack of + // an analog to slice::split_at_mut. + let mut used_by_this_id = self.take_this_id_usage_set(id); + + trace!("constrain {:?}", id); + trace!(" initially, used set is {:?}", used_by_this_id); + + let original_len = used_by_this_id.len(); + + let item = self.ctx.resolve_item(id); + let ty_kind = item.as_type().map(|ty| ty.kind()); + match ty_kind { + // Named template type parameters trivially use themselves. + Some(&TypeKind::TypeParam) => { + trace!(" named type, trivially uses itself"); + used_by_this_id.insert(id); + } + // Template instantiations only use their template arguments if the + // template definition uses the corresponding template parameter. + Some(TypeKind::TemplateInstantiation(inst)) => { + if self + .allowlisted_items + .contains(&inst.template_definition().into()) + { + self.constrain_instantiation( + id, + &mut used_by_this_id, + inst, + ); + } else { + self.constrain_instantiation_of_blocklisted_template( + id, + &mut used_by_this_id, + inst, + ); + } + } + // Otherwise, add the union of each of its referent item's template + // parameter usage. + _ => self.constrain_join(&mut used_by_this_id, item), + } + + trace!(" finally, used set is {:?}", used_by_this_id); + + let new_len = used_by_this_id.len(); + assert!( + new_len >= original_len, + "This is the property that ensures this function is monotone -- \ + if it doesn't hold, the analysis might never terminate!" + ); + + // Put the set back in the hash map and restore our invariant. + debug_assert!(self.used[&id].is_none()); + self.used.insert(id, Some(used_by_this_id)); + extra_assert!(self.used.values().all(|v| v.is_some())); + + if new_len != original_len { + ConstrainResult::Changed + } else { + ConstrainResult::Same + } + } + + fn each_depending_on<F>(&self, item: ItemId, mut f: F) + where + F: FnMut(ItemId), + { + if let Some(edges) = self.dependencies.get(&item) { + for item in edges { + trace!("enqueue {:?} into worklist", item); + f(*item); + } + } + } +} + +impl<'ctx> From<UsedTemplateParameters<'ctx>> for HashMap<ItemId, ItemSet> { + fn from(used_templ_params: UsedTemplateParameters<'ctx>) -> Self { + used_templ_params + .used + .into_iter() + .map(|(k, v)| (k, v.unwrap())) + .collect() + } +} |