| derive.rs |
Determining which types for which we cannot emit `#[derive(Trait)]`. |
26218 |
| has_destructor.rs |
Determining which types have destructors |
6412 |
| has_float.rs |
Determining which types has float. |
8663 |
| has_type_param_in_array.rs |
Determining which types has typed parameters in array. |
8996 |
| has_vtable.rs |
Determining which types has vtable |
7562 |
| mod.rs |
Fix-point analyses on the IR using the "monotone framework".
A lattice is a set with a partial ordering between elements, where there is
a single least upper bound and a single greatest least bound for every
subset. We are dealing with finite lattices, which means that it has a
finite number of elements, and it follows that there exists a single top and
a single bottom member of the lattice. For example, the power set of a
finite set forms a finite lattice where partial ordering is defined by set
inclusion, that is `a <= b` if `a` is a subset of `b`. Here is the finite
lattice constructed from the set {0,1,2}:
```text
.----- Top = {0,1,2} -----.
/ | \
/ | \
/ | \
{0,1} -------. {0,2} .--------- {1,2}
| \ / \ / |
| / \ |
| / \ / \ |
{0} --------' {1} `---------- {2}
\ | /
\ | /
\ | /
`------ Bottom = {} ------'
```
A monotone function `f` is a function where if `x <= y`, then it holds that
`f(x) <= f(y)`. It should be clear that running a monotone function to a
fix-point on a finite lattice will always terminate: `f` can only "move"
along the lattice in a single direction, and therefore can only either find
a fix-point in the middle of the lattice or continue to the top or bottom
depending if it is ascending or descending the lattice respectively.
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 |
13925 |
| sizedness.rs |
Determining the sizedness of types (as base classes and otherwise). |
11685 |
| template_params.rs |
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(crate) 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. |
23187 |