mirror of
https://gitee.com/openharmony/third_party_rust_bindgen
synced 2025-01-07 15:33:03 +00:00
608 lines
23 KiB
Rust
608 lines
23 KiB
Rust
//! 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()
|
|
}
|
|
}
|