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<'ctx> UsedTemplateParameters<'ctx> {
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 .cloned()
263 });
264
265 used_by_this_id.extend(args);
266 }
267
268 /// A template instantiation's concrete template argument is only used if
269 /// the template definition uses the corresponding template parameter.
270 fn constrain_instantiation(
271 &self,
272 this_id: ItemId,
273 used_by_this_id: &mut ItemSet,
274 instantiation: &TemplateInstantiation,
275 ) {
276 trace!(" template instantiation");
277
278 let decl = self.ctx.resolve_type(instantiation.template_definition());
279 let args = instantiation.template_arguments();
280
281 let params = decl.self_template_params(self.ctx);
282
283 debug_assert!(this_id != instantiation.template_definition());
284 let used_by_def = self.used
285 .get(&instantiation.template_definition().into())
286 .expect("Should have a used entry for instantiation's template definition")
287 .as_ref()
288 .expect("And it should be Some because only this_id's set is None, and an \
289 instantiation's template definition should never be the \
290 instantiation itself");
291
292 for (arg, param) in args.iter().zip(params.iter()) {
293 trace!(
294 " instantiation's argument {:?} is used if definition's \
295 parameter {:?} is used",
296 arg,
297 param
298 );
299
300 if used_by_def.contains(&param.into()) {
301 trace!(" param is used by template definition");
302
303 let arg = arg
304 .into_resolver()
305 .through_type_refs()
306 .through_type_aliases()
307 .resolve(self.ctx)
308 .id();
309
310 if arg == this_id {
311 continue;
312 }
313
314 let used_by_arg = self
315 .used
316 .get(&arg)
317 .expect("Should have a used entry for the template arg")
318 .as_ref()
319 .expect(
320 "Because arg != this_id, and all used template \
321 param sets other than this_id's are `Some`, \
322 arg's used template param set should be \
323 `Some`",
324 )
325 .iter()
326 .cloned();
327 used_by_this_id.extend(used_by_arg);
328 }
329 }
330 }
331
332 /// The join operation on our lattice: the set union of all of this ID's
333 /// successors.
334 fn constrain_join(&self, used_by_this_id: &mut ItemSet, item: &Item) {
335 trace!(" other item: join with successors' usage");
336
337 item.trace(
338 self.ctx,
339 &mut |sub_id, edge_kind| {
340 // Ignore ourselves, since union with ourself is a
341 // no-op. Ignore edges that aren't relevant to the
342 // analysis.
343 if sub_id == item.id() || !Self::consider_edge(edge_kind) {
344 return;
345 }
346
347 let used_by_sub_id = self
348 .used
349 .get(&sub_id)
350 .expect("Should have a used set for the sub_id successor")
351 .as_ref()
352 .expect(
353 "Because sub_id != id, and all used template \
354 param sets other than id's are `Some`, \
355 sub_id's used template param set should be \
356 `Some`",
357 )
358 .iter()
359 .cloned();
360
361 trace!(
362 " union with {:?}'s usage: {:?}",
363 sub_id,
364 used_by_sub_id.clone().collect::<Vec<_>>()
365 );
366
367 used_by_this_id.extend(used_by_sub_id);
368 },
369 &(),
370 );
371 }
372}
373
374impl<'ctx> MonotoneFramework for UsedTemplateParameters<'ctx> {
375 type Node = ItemId;
376 type Extra = &'ctx BindgenContext;
377 type Output = HashMap<ItemId, ItemSet>;
378
379 fn new(ctx: &'ctx BindgenContext) -> UsedTemplateParameters<'ctx> {
380 let mut used = HashMap::default();
381 let mut dependencies = HashMap::default();
382 let allowlisted_items: HashSet<_> =
383 ctx.allowlisted_items().iter().cloned().collect();
384
385 let allowlisted_and_blocklisted_items: ItemSet = allowlisted_items
386 .iter()
387 .cloned()
388 .flat_map(|i| {
389 let mut reachable = vec![i];
390 i.trace(
391 ctx,
392 &mut |s, _| {
393 reachable.push(s);
394 },
395 &(),
396 );
397 reachable
398 })
399 .collect();
400
401 for item in allowlisted_and_blocklisted_items {
402 dependencies.entry(item).or_insert_with(Vec::new);
403 used.entry(item).or_insert_with(|| Some(ItemSet::new()));
404
405 {
406 // We reverse our natural IR graph edges to find dependencies
407 // between nodes.
408 item.trace(
409 ctx,
410 &mut |sub_item: ItemId, _| {
411 used.entry(sub_item)
412 .or_insert_with(|| Some(ItemSet::new()));
413 dependencies
414 .entry(sub_item)
415 .or_insert_with(Vec::new)
416 .push(item);
417 },
418 &(),
419 );
420 }
421
422 // Additionally, whether a template instantiation's template
423 // arguments are used depends on whether the template declaration's
424 // generic template parameters are used.
425 let item_kind =
426 ctx.resolve_item(item).as_type().map(|ty| ty.kind());
427 if let Some(TypeKind::TemplateInstantiation(inst)) = item_kind {
428 let decl = ctx.resolve_type(inst.template_definition());
429 let args = inst.template_arguments();
430
431 // Although template definitions should always have
432 // template parameters, there is a single exception:
433 // opaque templates. Hence the unwrap_or.
434 let params = decl.self_template_params(ctx);
435
436 for (arg, param) in args.iter().zip(params.iter()) {
437 let arg = arg
438 .into_resolver()
439 .through_type_aliases()
440 .through_type_refs()
441 .resolve(ctx)
442 .id();
443
444 let param = param
445 .into_resolver()
446 .through_type_aliases()
447 .through_type_refs()
448 .resolve(ctx)
449 .id();
450
451 used.entry(arg).or_insert_with(|| Some(ItemSet::new()));
452 used.entry(param).or_insert_with(|| Some(ItemSet::new()));
453
454 dependencies
455 .entry(arg)
456 .or_insert_with(Vec::new)
457 .push(param);
458 }
459 }
460 }
461
462 if cfg!(feature = "__testing_only_extra_assertions") {
463 // Invariant: The `used` map has an entry for every allowlisted
464 // item, as well as all explicitly blocklisted items that are
465 // reachable from allowlisted items.
466 //
467 // Invariant: the `dependencies` map has an entry for every
468 // allowlisted item.
469 //
470 // (This is so that every item we call `constrain` on is guaranteed
471 // to have a set of template parameters, and we can allow
472 // blocklisted templates to use all of their parameters).
473 for item in allowlisted_items.iter() {
474 extra_assert!(used.contains_key(item));
475 extra_assert!(dependencies.contains_key(item));
476 item.trace(
477 ctx,
478 &mut |sub_item, _| {
479 extra_assert!(used.contains_key(&sub_item));
480 extra_assert!(dependencies.contains_key(&sub_item));
481 },
482 &(),
483 )
484 }
485 }
486
487 UsedTemplateParameters {
488 ctx,
489 used,
490 dependencies,
491 allowlisted_items,
492 }
493 }
494
495 fn initial_worklist(&self) -> Vec<ItemId> {
496 // The transitive closure of all allowlisted items, including explicitly
497 // blocklisted items.
498 self.ctx
499 .allowlisted_items()
500 .iter()
501 .cloned()
502 .flat_map(|i| {
503 let mut reachable = vec![i];
504 i.trace(
505 self.ctx,
506 &mut |s, _| {
507 reachable.push(s);
508 },
509 &(),
510 );
511 reachable
512 })
513 .collect()
514 }
515
516 fn constrain(&mut self, id: ItemId) -> ConstrainResult {
517 // Invariant: all hash map entries' values are `Some` upon entering and
518 // exiting this method.
519 extra_assert!(self.used.values().all(|v| v.is_some()));
520
521 // Take the set for this ID out of the hash map while we mutate it based
522 // on other hash map entries. We *must* put it back into the hash map at
523 // the end of this method. This allows us to side-step HashMap's lack of
524 // an analog to slice::split_at_mut.
525 let mut used_by_this_id = self.take_this_id_usage_set(id);
526
527 trace!("constrain {:?}", id);
528 trace!(" initially, used set is {:?}", used_by_this_id);
529
530 let original_len = used_by_this_id.len();
531
532 let item = self.ctx.resolve_item(id);
533 let ty_kind = item.as_type().map(|ty| ty.kind());
534 match ty_kind {
535 // Named template type parameters trivially use themselves.
536 Some(&TypeKind::TypeParam) => {
537 trace!(" named type, trivially uses itself");
538 used_by_this_id.insert(id);
539 }
540 // Template instantiations only use their template arguments if the
541 // template definition uses the corresponding template parameter.
542 Some(TypeKind::TemplateInstantiation(inst)) => {
543 if self
544 .allowlisted_items
545 .contains(&inst.template_definition().into())
546 {
547 self.constrain_instantiation(
548 id,
549 &mut used_by_this_id,
550 inst,
551 );
552 } else {
553 self.constrain_instantiation_of_blocklisted_template(
554 id,
555 &mut used_by_this_id,
556 inst,
557 );
558 }
559 }
560 // Otherwise, add the union of each of its referent item's template
561 // parameter usage.
562 _ => self.constrain_join(&mut used_by_this_id, item),
563 }
564
565 trace!(" finally, used set is {:?}", used_by_this_id);
566
567 let new_len = used_by_this_id.len();
568 assert!(
569 new_len >= original_len,
570 "This is the property that ensures this function is monotone -- \
571 if it doesn't hold, the analysis might never terminate!"
572 );
573
574 // Put the set back in the hash map and restore our invariant.
575 debug_assert!(self.used[&id].is_none());
576 self.used.insert(id, Some(used_by_this_id));
577 extra_assert!(self.used.values().all(|v| v.is_some()));
578
579 if new_len != original_len {
580 ConstrainResult::Changed
581 } else {
582 ConstrainResult::Same
583 }
584 }
585
586 fn each_depending_on<F>(&self, item: ItemId, mut f: F)
587 where
588 F: FnMut(ItemId),
589 {
590 if let Some(edges) = self.dependencies.get(&item) {
591 for item in edges {
592 trace!("enqueue {:?} into worklist", item);
593 f(*item);
594 }
595 }
596 }
597}
598
599impl<'ctx> From<UsedTemplateParameters<'ctx>> for HashMap<ItemId, ItemSet> {
600 fn from(used_templ_params: UsedTemplateParameters<'ctx>) -> Self {
601 used_templ_paramsimpl Iterator
602 .used
603 .into_iter()
604 .map(|(k: ItemId, v: Option>)| (k, v.unwrap()))
605 .collect()
606 }
607}
608