Rewrite various ad-hoc analyses to fix-point computations

[fitzgen]

This is a meta issue, see sub-issues for actual work items to help out.

---

I just spent an embarrassing amount of time debugging a stack overflow (like a dummy, I didn't hit bt immediately...) and it was because has_vtable got caught in an infinite loop (with my local changes).

All of

• has_vtable (Rewrite has_vtable checks as either graph traversal or fix-point analysis #765)
• can_derive_copy[_in_array] (Rewrite can_derive_copy[_in_array] as either a graph traversal or fix-point analysis #766)
• can_derive_debug (Rewrite can_derive_debug as either a graph traversal or fix-point analysis #767)
• is_unsized (Rewrite is_unsized as a fix-point analysis #768)
• can_derive_default (Rewrite can_derive_default as a fix-point analysis #856)
• has_destructor (Rewrite has_destructor as a fixed point analysis #927)

could be rewritten as graph traversals (or fix point computations). We just have to be careful to consider only the correct edges (eg ignore a class's class members, etc).

If they were re-written as graph traversals (or fix point computations), then they wouldn't be recursive and we wouldn't blow the stack. Additionally, some of these things add a Cell<bool> member that gets set during recursion, and we use this to detect cycles and avoid infinite recursion. These members would not be necessary with either a graph traversal or fix-point computation.

Leaving this as a meta issue for rewriting each of these things.

[fitzgen]

Additionally, some of these things add a Cell member that gets set during recursion, and we use this to detect cycles and avoid infinite recursion.

For posterity, this is the detect_whatever_cycle members.

[fitzgen]

Also, if we do this refactoring such that we calculate these things for all types in a single pass, we can avoid re-walking portions of the IR graph repeatedly, like we do now.

[fitzgen]

@chmln, is this something you might be interested in hacking on?

[chmln]

@fitzgen Yes 👍
( unless this is time-critical. I'll need some time to study the project + got some time constraints of my own)

[fitzgen]

@chmln awesome! It's not time critical.

First things first: makes sure you can build bindgen and run the test suite successfully. See CONTRIBUTING.md for more.

As far as these analyses go, let's jsut start with one. has_vtable would be a fine choice. Right now, it is implemented by a bunch of big match statements and has_vtable method calls between different types. This is hard coding a traversal of bindgen's IR (internal representation) graph. This should be plain when you see the detect_has_vtable_cycle cell, which we have to set to make sure we don't go into infinite loops.

However, we already have generic graph traversal infrastructure for our IR, see src/ir/traversal.rs. So why deal with detecting cycles and hard coding a specific graph traversal? Answer is that we shouldn't, and this is where you come in ;)

Additionally, we can do a single pass over the whole IR graph and build a HashMap<ItemId, bool> for whether each item has a vtable or not, and then we won't repeatedly traverse overlapping subsets of the IR graph when determining if two distinct but related types have a vtable or not.

Does that make sense? Don't hesitate to ask questions if anything is confusing, or you get stuck, or anything like that.

[fitzgen]

As far as where to store the HashMap<ItemId, bool>, it should be on the BindgenContext, similar to used_template_parameters (which is a similar kind of analysis that we perform up front for the whole IR graph, and then use the computed values later rather than recomputing them again).

[chmln]

Perfect, thanks @fitzgen 👍
That made things a lot clearer.

[fitzgen]

@chmln how are things going? Can I answer any questions for you?

[chmln]

@fitzgen planning to complete it this weekend (slow progress due to busyness).
But no questions so far, thank you.

[fitzgen]

@chmln how are things going? Still making some slow-but-steady progress? Anything I can do to help or questions I can answer?

[chmln]

@fitzgen only question so far is about the location of the HashTable for vtables. Should it be in BindgenContext, similar to whitelisted items?

[fitzgen]

Should it be in BindgenContext?

Yep! I'd probably put it near the used_template_parameters https://github.com/servo/rust-bindgen/blob/master/src/ir/context.rs#L162

[chmln]

ok @fitzgen I've gotten the traversal and everything working.
Another question - how do we best detect whether an Item has a vtable?

The current has_vtable() function is using a match with TypeKind, while in my traversal Item.kind is an ItemKind

[fitzgen]

@chmln great!

how do we best detect whether an Item has a vtable?

The current has_vtable() function is using a match with TypeKind, while in my traversal Item.kind is an ItemKind

You can use matches something like this:

match item.kind() {
    &ItemKind::Type(ref ty) => {
        // use ty.kind() here...
    }
    // other ItemKind cases ...
}

Or use the Item::as_type() method:

if let Some(ty) = item.as_type() {
    // use ty.kind() here...
}

Does this clear up your question?

[fitzgen]

@Tiwalun this meta issue has some stuff available that you might be able to help with :)

@chmln is refactoring the has_vtable checks to use the generic graph traversal infrastructure -- maybe you could do the same for is_unsized? See the backlog for details, and if anything is unclear, don't hesitate to reach out to me :)

[Tiwalun]

@fitzgen Ok, I'll have a look at the is_unsized part.

[fitzgen]

@chmln @Tiwalun hey folks! How are things coming? Anything I can do to help? Questions I can answer?

[chmln]

@fitzgen nearly done with has_vtable. I'll submit a PR around this weekend

[fitzgen]

@fitzgen nearly done with has_vtable. I'll submit a PR around this weekend

Hi @chmln! Any progress?

If you don't have time to work on it anymore (completely understandable) posting a work-in-progress PR with what you do have could be helpful for me or someone else to take it across the finish line.

[fitzgen]

@Tiwalun still poking at is_unsized? Anything I can do to help?

[fitzgen]

Unassigned due to lack of activity. Also split out each bit of work into its own issue.

[SirVer]

#765 (comment) contains a skeleton for a new sample fixpoint analysis. It could be a good jumpoff point for any of sub-issues.