| //! 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(ref 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(ref 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() |
| } |
| } |