| 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 |
|
| 91 |
use super::{ConstrainResult, MonotoneFramework}; |
| 92 |
use crate::ir::context::{BindgenContext, ItemId}; |
| 93 |
use crate::ir::item::{Item, ItemSet}; |
| 94 |
use crate::ir::template::{TemplateInstantiation, TemplateParameters}; |
| 95 |
use crate::ir::traversal::{EdgeKind, Trace}; |
| 96 |
use crate::ir::ty::TypeKind; |
| 97 |
use 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)] |
| 149 |
pub(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 |
|
| 164 |
impl<'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(¶m.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 |
|
| 374 |
impl<'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 |
|
| 599 |
impl<'ctx> From<UsedTemplateParameters<'ctx>> for HashMap<ItemId, ItemSet> { |
| 600 |
fn from(used_templ_params: UsedTemplateParameters<'ctx>) -> Self { |
| 601 |
used_templ_params |
| 602 |
.used |
| 603 |
.into_iter() |
| 604 |
.map(|(k, v)| (k, v.unwrap())) |
| 605 |
.collect() |
| 606 |
} |
| 607 |
} |