Discover which template type parameters are actually used

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).

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 "monotone framework" for this fix-point analysis where our
lattice is the powerset of the template parameters that appear in the input
C++ header, our join function is set union, and we use the
`ir::traversal::Trace` trait to implement the work-list optimization so we
don't have to revisit every node in the graph when for every iteration
towards the fix-point.

For a deeper introduction to the general form of this kind of analysis, see
[Static Program Analysis by Anders Møller and Michael I. Schwartzbach][spa].

[spa]: https://cs.au.dk/~amoeller/spa/spa.pdf

0 files changed, 0 insertions, 0 deletions