1//! Discover which template type parameters are actually used.
2//!
3//! ### Why do we care?
4//!
5//! C++ allows ignoring template parameters, while Rust does not. Usually we can
6//! blindly stick a `PhantomData<T>` inside a generic Rust struct to make up for
7//! this. That doesn't work for templated type aliases, however:
8//!
9//! ```C++
10//! template <typename T>
11//! using Fml = int;
12//! ```
13//!
14//! If we generate the naive Rust code for this alias, we get:
15//!
16//! ```ignore
17//! pub(crate) type Fml<T> = ::std::os::raw::int;
18//! ```
19//!
20//! And this is rejected by `rustc` due to the unused type parameter.
21//!
22//! (Aside: in these simple cases, `libclang` will often just give us the
23//! aliased type directly, and we will never even know we were dealing with
24//! aliases, let alone templated aliases. It's the more convoluted scenarios
25//! where we get to have some fun...)
26//!
27//! For such problematic template aliases, we could generate a tuple whose
28//! second member is a `PhantomData<T>`. Or, if we wanted to go the extra mile,
29//! we could even generate some smarter wrapper that implements `Deref`,
30//! `DerefMut`, `From`, `Into`, `AsRef`, and `AsMut` to the actually aliased
31//! type. However, this is still lackluster:
32//!
33//! 1. Even with a billion conversion-trait implementations, using the generated
34//! bindings is rather un-ergonomic.
35//! 2. With either of these solutions, we need to keep track of which aliases
36//! we've transformed like this in order to generate correct uses of the
37//! wrapped type.
38//!
39//! Given that we have to properly track which template parameters ended up used
40//! for (2), we might as well leverage that information to make ergonomic
41//! bindings that don't contain any unused type parameters at all, and
42//! completely avoid the pain of (1).
43//!
44//! ### How do we determine which template parameters are used?
45//!
46//! Determining which template parameters are actually used is a trickier
47//! problem than it might seem at a glance. On the one hand, trivial uses are
48//! easy to detect:
49//!
50//! ```C++
51//! template <typename T>
52//! class Foo {
53//! T trivial_use_of_t;
54//! };
55//! ```
56//!
57//! It gets harder when determining if one template parameter is used depends on
58//! determining if another template parameter is used. In this example, whether
59//! `U` is used depends on whether `T` is used.
60//!
61//! ```C++
62//! template <typename T>
63//! class DoesntUseT {
64//! int x;
65//! };
66//!
67//! template <typename U>
68//! class Fml {
69//! DoesntUseT<U> lololol;
70//! };
71//! ```
72//!
73//! We can express the set of used template parameters as a constraint solving
74//! problem (where the set of template parameters used by a given IR item is the
75//! union of its sub-item's used template parameters) and iterate to a
76//! fixed-point.
77//!
78//! We use the `ir::analysis::MonotoneFramework` infrastructure for this
79//! fix-point analysis, where our lattice is the mapping from each IR item to
80//! the powerset of the template parameters that appear in the input C++ header,
81//! our join function is set union. The set of template parameters appearing in
82//! the program is finite, as is the number of IR items. We start at our
83//! lattice's bottom element: every item mapping to an empty set of template
84//! parameters. Our analysis only adds members to each item's set of used
85//! template parameters, never removes them, so it is monotone. Because our
86//! lattice is finite and our constraint function is monotone, iteration to a
87//! fix-point will terminate.
88//!
89//! See `src/ir/analysis.rs` for more.
90
91use super::{ConstrainResult, MonotoneFramework};
92use crate::ir::context::{BindgenContext, ItemId};
93use crate::ir::item::{Item, ItemSet};
94use crate::ir::template::{TemplateInstantiation, TemplateParameters};
95use crate::ir::traversal::{EdgeKind, Trace};
96use crate::ir::ty::TypeKind;
97use crate::{HashMap, HashSet};
98
99/// An analysis that finds for each IR item its set of template parameters that
100/// it uses.
101///
102/// We use the monotone constraint function `template_param_usage`, defined as
103/// follows:
104///
105/// * If `T` is a named template type parameter, it trivially uses itself:
106///
107/// ```ignore
108/// template_param_usage(T) = { T }
109/// ```
110///
111/// * If `inst` is a template instantiation, `inst.args` are the template
112/// instantiation's template arguments, `inst.def` is the template definition
113/// being instantiated, and `inst.def.params` is the template definition's
114/// template parameters, then the instantiation's usage is the union of each
115/// of its arguments' usages *if* the corresponding template parameter is in
116/// turn used by the template definition:
117///
118/// ```ignore
119/// template_param_usage(inst) = union(
120/// template_param_usage(inst.args[i])
121/// for i in 0..length(inst.args.length)
122/// if inst.def.params[i] in template_param_usage(inst.def)
123/// )
124/// ```
125///
126/// * Finally, for all other IR item kinds, we use our lattice's `join`
127/// operation: set union with each successor of the given item's template
128/// parameter usage:
129///
130/// ```ignore
131/// template_param_usage(v) =
132/// union(template_param_usage(w) for w in successors(v))
133/// ```
134///
135/// Note that we ignore certain edges in the graph, such as edges from a
136/// template declaration to its template parameters' definitions for this
137/// analysis. If we didn't, then we would mistakenly determine that ever
138/// template parameter is always used.
139///
140/// The final wrinkle is handling of blocklisted types. Normally, we say that
141/// the set of allowlisted items is the transitive closure of items explicitly
142/// called out for allowlisting, *without* any items explicitly called out as
143/// blocklisted. However, for the purposes of this analysis's correctness, we
144/// simplify and consider run the analysis on the full transitive closure of
145/// allowlisted items. We do, however, treat instantiations of blocklisted items
146/// specially; see `constrain_instantiation_of_blocklisted_template` and its
147/// documentation for details.
148#[derive(Debug, Clone)]
149pub(crate) struct UsedTemplateParameters<'ctx> {
150 ctx: &'ctx BindgenContext,
151
152 // The Option is only there for temporary moves out of the hash map. See the
153 // comments in `UsedTemplateParameters::constrain` below.
154 used: HashMap<ItemId, Option<ItemSet>>,
155
156 dependencies: HashMap<ItemId, Vec<ItemId>>,
157
158 // The set of allowlisted items, without any blocklisted items reachable
159 // from the allowlisted items which would otherwise be considered
160 // allowlisted as well.
161 allowlisted_items: HashSet<ItemId>,
162}
163
164impl UsedTemplateParameters<'_> {
165 fn consider_edge(kind: EdgeKind) -> bool {
166 match kind {
167 // For each of these kinds of edges, if the referent uses a template
168 // parameter, then it should be considered that the origin of the
169 // edge also uses the template parameter.
170 EdgeKind::TemplateArgument |
171 EdgeKind::BaseMember |
172 EdgeKind::Field |
173 EdgeKind::Constructor |
174 EdgeKind::Destructor |
175 EdgeKind::VarType |
176 EdgeKind::FunctionReturn |
177 EdgeKind::FunctionParameter |
178 EdgeKind::TypeReference => true,
179
180 // An inner var or type using a template parameter is orthogonal
181 // from whether we use it. See template-param-usage-{6,11}.hpp.
182 EdgeKind::InnerVar | EdgeKind::InnerType => false,
183
184 // We can't emit machine code for new monomorphizations of class
185 // templates' methods (and don't detect explicit instantiations) so
186 // we must ignore template parameters that are only used by
187 // methods. This doesn't apply to a function type's return or
188 // parameter types, however, because of type aliases of function
189 // pointers that use template parameters, eg
190 // tests/headers/struct_with_typedef_template_arg.hpp
191 EdgeKind::Method => false,
192
193 // If we considered these edges, we would end up mistakenly claiming
194 // that every template parameter always used.
195 EdgeKind::TemplateDeclaration |
196 EdgeKind::TemplateParameterDefinition => false,
197
198 // Since we have to be careful about which edges we consider for
199 // this analysis to be correct, we ignore generic edges. We also
200 // avoid a `_` wild card to force authors of new edge kinds to
201 // determine whether they need to be considered by this analysis.
202 EdgeKind::Generic => false,
203 }
204 }
205
206 fn take_this_id_usage_set<Id: Into<ItemId>>(
207 &mut self,
208 this_id: Id,
209 ) -> ItemSet {
210 let this_id = this_id.into();
211 self.used
212 .get_mut(&this_id)
213 .expect(
214 "Should have a set of used template params for every item \
215 id",
216 )
217 .take()
218 .expect(
219 "Should maintain the invariant that all used template param \
220 sets are `Some` upon entry of `constrain`",
221 )
222 }
223
224 /// We say that blocklisted items use all of their template parameters. The
225 /// blocklisted type is most likely implemented explicitly by the user,
226 /// since it won't be in the generated bindings, and we don't know exactly
227 /// what they'll to with template parameters, but we can push the issue down
228 /// the line to them.
229 fn constrain_instantiation_of_blocklisted_template(
230 &self,
231 this_id: ItemId,
232 used_by_this_id: &mut ItemSet,
233 instantiation: &TemplateInstantiation,
234 ) {
235 trace!(
236 " instantiation of blocklisted template, uses all template \
237 arguments"
238 );
239
240 let args = instantiation
241 .template_arguments()
242 .iter()
243 .map(|a| {
244 a.into_resolver()
245 .through_type_refs()
246 .through_type_aliases()
247 .resolve(self.ctx)
248 .id()
249 })
250 .filter(|a| *a != this_id)
251 .flat_map(|a| {
252 self.used
253 .get(&a)
254 .expect("Should have a used entry for the template arg")
255 .as_ref()
256 .expect(
257 "Because a != this_id, and all used template \
258 param sets other than this_id's are `Some`, \
259 a's used template param set should be `Some`",
260 )
261 .iter()
262 });
263
264 used_by_this_id.extend(args);
265 }
266
267 /// A template instantiation's concrete template argument is only used if
268 /// the template definition uses the corresponding template parameter.
269 fn constrain_instantiation(
270 &self,
271 this_id: ItemId,
272 used_by_this_id: &mut ItemSet,
273 instantiation: &TemplateInstantiation,
274 ) {
275 trace!(" template instantiation");
276
277 let decl = self.ctx.resolve_type(instantiation.template_definition());
278 let args = instantiation.template_arguments();
279
280 let params = decl.self_template_params(self.ctx);
281
282 debug_assert!(this_id != instantiation.template_definition());
283 let used_by_def = self.used
284 .get(&instantiation.template_definition().into())
285 .expect("Should have a used entry for instantiation's template definition")
286 .as_ref()
287 .expect("And it should be Some because only this_id's set is None, and an \
288 instantiation's template definition should never be the \
289 instantiation itself");
290
291 for (arg, param) in args.iter().zip(params.iter()) {
292 trace!(
293 " instantiation's argument {arg:?} is used if definition's \
294 parameter {param:?} is used",
295 );
296
297 if used_by_def.contains(&param.into()) {
298 trace!(" param is used by template definition");
299
300 let arg = arg
301 .into_resolver()
302 .through_type_refs()
303 .through_type_aliases()
304 .resolve(self.ctx)
305 .id();
306
307 if arg == this_id {
308 continue;
309 }
310
311 let used_by_arg = self
312 .used
313 .get(&arg)
314 .expect("Should have a used entry for the template arg")
315 .as_ref()
316 .expect(
317 "Because arg != this_id, and all used template \
318 param sets other than this_id's are `Some`, \
319 arg's used template param set should be \
320 `Some`",
321 )
322 .iter();
323 used_by_this_id.extend(used_by_arg);
324 }
325 }
326 }
327
328 /// The join operation on our lattice: the set union of all of this ID's
329 /// successors.
330 fn constrain_join(&self, used_by_this_id: &mut ItemSet, item: &Item) {
331 trace!(" other item: join with successors' usage");
332
333 item.trace(
334 self.ctx,
335 &mut |sub_id, edge_kind| {
336 // Ignore ourselves, since union with ourself is a
337 // no-op. Ignore edges that aren't relevant to the
338 // analysis.
339 if sub_id == item.id() || !Self::consider_edge(edge_kind) {
340 return;
341 }
342
343 let used_by_sub_id = self
344 .used
345 .get(&sub_id)
346 .expect("Should have a used set for the sub_id successor")
347 .as_ref()
348 .expect(
349 "Because sub_id != id, and all used template \
350 param sets other than id's are `Some`, \
351 sub_id's used template param set should be \
352 `Some`",
353 )
354 .iter();
355
356 trace!(
357 " union with {sub_id:?}'s usage: {:?}",
358 used_by_sub_id.clone().collect::<Vec<_>>()
359 );
360
361 used_by_this_id.extend(used_by_sub_id);
362 },
363 &(),
364 );
365 }
366}
367
368impl<'ctx> MonotoneFramework for UsedTemplateParameters<'ctx> {
369 type Node = ItemId;
370 type Extra = &'ctx BindgenContext;
371 type Output = HashMap<ItemId, ItemSet>;
372
373 fn new(ctx: &'ctx BindgenContext) -> UsedTemplateParameters<'ctx> {
374 let mut used = HashMap::default();
375 let mut dependencies = HashMap::default();
376 let allowlisted_items: HashSet<_> =
377 ctx.allowlisted_items().iter().copied().collect();
378
379 let allowlisted_and_blocklisted_items: ItemSet = allowlisted_items
380 .iter()
381 .copied()
382 .flat_map(|i| {
383 let mut reachable = vec![i];
384 i.trace(
385 ctx,
386 &mut |s, _| {
387 reachable.push(s);
388 },
389 &(),
390 );
391 reachable
392 })
393 .collect();
394
395 for item in allowlisted_and_blocklisted_items {
396 dependencies.entry(item).or_insert_with(Vec::new);
397 used.entry(item).or_insert_with(|| Some(ItemSet::new()));
398
399 {
400 // We reverse our natural IR graph edges to find dependencies
401 // between nodes.
402 item.trace(
403 ctx,
404 &mut |sub_item: ItemId, _| {
405 used.entry(sub_item)
406 .or_insert_with(|| Some(ItemSet::new()));
407 dependencies
408 .entry(sub_item)
409 .or_insert_with(Vec::new)
410 .push(item);
411 },
412 &(),
413 );
414 }
415
416 // Additionally, whether a template instantiation's template
417 // arguments are used depends on whether the template declaration's
418 // generic template parameters are used.
419 let item_kind =
420 ctx.resolve_item(item).as_type().map(|ty| ty.kind());
421 if let Some(TypeKind::TemplateInstantiation(inst)) = item_kind {
422 let decl = ctx.resolve_type(inst.template_definition());
423 let args = inst.template_arguments();
424
425 // Although template definitions should always have
426 // template parameters, there is a single exception:
427 // opaque templates. Hence the unwrap_or.
428 let params = decl.self_template_params(ctx);
429
430 for (arg, param) in args.iter().zip(params.iter()) {
431 let arg = arg
432 .into_resolver()
433 .through_type_aliases()
434 .through_type_refs()
435 .resolve(ctx)
436 .id();
437
438 let param = param
439 .into_resolver()
440 .through_type_aliases()
441 .through_type_refs()
442 .resolve(ctx)
443 .id();
444
445 used.entry(arg).or_insert_with(|| Some(ItemSet::new()));
446 used.entry(param).or_insert_with(|| Some(ItemSet::new()));
447
448 dependencies
449 .entry(arg)
450 .or_insert_with(Vec::new)
451 .push(param);
452 }
453 }
454 }
455
456 if cfg!(feature = "__testing_only_extra_assertions") {
457 // Invariant: The `used` map has an entry for every allowlisted
458 // item, as well as all explicitly blocklisted items that are
459 // reachable from allowlisted items.
460 //
461 // Invariant: the `dependencies` map has an entry for every
462 // allowlisted item.
463 //
464 // (This is so that every item we call `constrain` on is guaranteed
465 // to have a set of template parameters, and we can allow
466 // blocklisted templates to use all of their parameters).
467 for item in &allowlisted_items {
468 extra_assert!(used.contains_key(item));
469 extra_assert!(dependencies.contains_key(item));
470 item.trace(
471 ctx,
472 &mut |sub_item, _| {
473 extra_assert!(used.contains_key(&sub_item));
474 extra_assert!(dependencies.contains_key(&sub_item));
475 },
476 &(),
477 );
478 }
479 }
480
481 UsedTemplateParameters {
482 ctx,
483 used,
484 dependencies,
485 allowlisted_items,
486 }
487 }
488
489 fn initial_worklist(&self) -> Vec<ItemId> {
490 // The transitive closure of all allowlisted items, including explicitly
491 // blocklisted items.
492 self.ctx
493 .allowlisted_items()
494 .iter()
495 .copied()
496 .flat_map(|i| {
497 let mut reachable = vec![i];
498 i.trace(
499 self.ctx,
500 &mut |s, _| {
501 reachable.push(s);
502 },
503 &(),
504 );
505 reachable
506 })
507 .collect()
508 }
509
510 fn constrain(&mut self, id: ItemId) -> ConstrainResult {
511 // Invariant: all hash map entries' values are `Some` upon entering and
512 // exiting this method.
513 extra_assert!(self.used.values().all(|v| v.is_some()));
514
515 // Take the set for this ID out of the hash map while we mutate it based
516 // on other hash map entries. We *must* put it back into the hash map at
517 // the end of this method. This allows us to side-step HashMap's lack of
518 // an analog to slice::split_at_mut.
519 let mut used_by_this_id = self.take_this_id_usage_set(id);
520
521 trace!("constrain {id:?}");
522 trace!(" initially, used set is {used_by_this_id:?}");
523
524 let original_len = used_by_this_id.len();
525
526 let item = self.ctx.resolve_item(id);
527 let ty_kind = item.as_type().map(|ty| ty.kind());
528 match ty_kind {
529 // Named template type parameters trivially use themselves.
530 Some(&TypeKind::TypeParam) => {
531 trace!(" named type, trivially uses itself");
532 used_by_this_id.insert(id);
533 }
534 // Template instantiations only use their template arguments if the
535 // template definition uses the corresponding template parameter.
536 Some(TypeKind::TemplateInstantiation(inst)) => {
537 if self
538 .allowlisted_items
539 .contains(&inst.template_definition().into())
540 {
541 self.constrain_instantiation(
542 id,
543 &mut used_by_this_id,
544 inst,
545 );
546 } else {
547 self.constrain_instantiation_of_blocklisted_template(
548 id,
549 &mut used_by_this_id,
550 inst,
551 );
552 }
553 }
554 // Otherwise, add the union of each of its referent item's template
555 // parameter usage.
556 _ => self.constrain_join(&mut used_by_this_id, item),
557 }
558
559 trace!(" finally, used set is {used_by_this_id:?}");
560
561 let new_len = used_by_this_id.len();
562 assert!(
563 new_len >= original_len,
564 "This is the property that ensures this function is monotone -- \
565 if it doesn't hold, the analysis might never terminate!"
566 );
567
568 // Put the set back in the hash map and restore our invariant.
569 debug_assert!(self.used[&id].is_none());
570 self.used.insert(id, Some(used_by_this_id));
571 extra_assert!(self.used.values().all(|v| v.is_some()));
572
573 if new_len == original_len {
574 ConstrainResult::Same
575 } else {
576 ConstrainResult::Changed
577 }
578 }
579
580 fn each_depending_on<F>(&self, item: ItemId, mut f: F)
581 where
582 F: FnMut(ItemId),
583 {
584 if let Some(edges) = self.dependencies.get(&item) {
585 for item in edges {
586 trace!("enqueue {item:?} into worklist");
587 f(*item);
588 }
589 }
590 }
591}
592
593impl<'ctx> From<UsedTemplateParameters<'ctx>> for HashMap<ItemId, ItemSet> {
594 fn from(used_templ_params: UsedTemplateParameters<'ctx>) -> Self {
595 used_templ_paramsimpl Iterator
596 .used
597 .into_iter()
598 .map(|(k: ItemId, v: Option>)| (k, v.unwrap()))
599 .collect()
600 }
601}
602