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?