Rewrite has_vtable checks as either graph traversal or fix-point analysis

[fitzgen]

See #536 for details.

[SirVer]

I started taking a look at this to understand bindgen a bit better. I am interested in its approach to understand better if it can be useful to me in future projects. Since I do not know how much time I'll have for this, I wanted to provide incremental improvements instead of one huge refactoring.

Finding a test case

For this I started looking into ir::ty::Type::has_vtable. First, I tried to get tests running. On my MacBook cargo test --features testing_only_libclang_3_8 was all green on master, but also stayed all green on master when I added an assert(!self.detect_has_vtable_cycle.get()), i.e. the recursion case seems not triggered in the test suite. Maybe this is worth a new issue?

I then changed has_vtable to always return false. This made header_virtual_inheritance_hpp fail. Trying to run this test in isolation led me to send #782 since the script running one test case did not work for me.

Coding

1. I wanted to replace the homegrown recursion in ir::ty::Type::has_vtable through using code in ir::traversal. My idea was to launch a ItemTraversal::new, but this requires an Iterator<ItemId> but it seems ir::ty::Type::has_vtable is already too deep in the call stack to still have an ItemId generally available?

2. My second attempt was to look how ir::context::Context::used_template_parameters was populated. My understanding is that it runs a fix point analysis for every item in the IR AST and caches the results. This seems attractive for the has_vtable call as well. But while I think I grasped the core concepts of the monotone framework and what a fixpoint analysis is from the documentation in ir::named, the code of UsedTemplateParameters is way over my head at my current understanding.

@fitzgen I'd like to try doing 1) first, since it seems a smaller commitment and something I can reasonably achieve on my 3h train ride on Sunday. I think 2) is the better implementation, but I'd require a lot more guidance to attempt that.

[fitzgen]

Hey @SirVer! Thanks for writing up your questions for me :)

when I added an assert(!self.detect_has_vtable_cycle.get()), i.e. the recursion case seems not triggered in the test suite. Maybe this is worth a new issue?

It's possible that we simply don't have test coverage here. I would have expected some of the CRTP test cases to have caught this, but... shrugs

I wanted to replace the homegrown recursion in ir::ty::Type::has_vtable through using code in ir::traversal. My idea was to launch a ItemTraversal::new, but this requires an Iterator but it seems ir::ty::Type::has_vtable is already too deep in the call stack to still have an ItemId generally available?

We're in a situation where ItemId::has_vtable calls Item::has_vtable calls Type::has_vtable.

We can make Type::has_vtable take another parameter: the ItemId. Then we explicitly pass the id through each call.

My second attempt was to look how ir::context::Context::used_template_parameters was populated. My understanding is that it runs a fix point analysis for every item in the IR AST and caches the results. This seems attractive for the has_vtable call as well. But while I think I grasped the core concepts of the monotone framework and what a fixpoint analysis is from the documentation in ir::named, the code of UsedTemplateParameters is way over my head at my current understanding.

You got pretty far into the UsedTemplateParameters! It's definitely not light stuff :)

I agree that the fix-point analysis + caching is attractive for has_vtable as well. We don't need to jump here immediately, though, so if you would prefer to start with individual traversals for each has_vtable call, then we can do that for sure.

That said... did you follow the psuedocode for the template analysis? https://github.com/servo/rust-bindgen/blob/master/src/ir/named.rs#L212-L260

If I were to write similar pseudocode for a monotone has_vtable constraint function, it would be something like this:

fn has_vtable(comp: Type with TypeKind::Comp) -> bool {
    for base in comp.base_members() {
        // Look at currently computed value.
        if has_vtable(base) {
            return true;
        }
    }

    // Property access on `Comp` member, not recursive call or cache lookup.
    comp.has_vtable
}

fn has_vtable(_: any other item) -> bool {
    false
}

And the recursive has_vtable(...) calls would be looking up the currently calculated value in the HashMap<ItemId, bool> (or just a HashSet<ItemId> where not in the set == false, I guess).

I'd like to try doing 1) first, since it seems a smaller commitment and something I can reasonably achieve on my 3h train ride on Sunday. I think 2) is the better implementation, but I'd require a lot more guidance to attempt that.

That sounds like an A+ plan. 👍

Let me know if I've helped elucidate the fixpoint stuff at all or if I've simply muddied the waters.

Cheers!

Nick

[SirVer]

[recursive case in Type::has_vtable]

@fitzgen, I think I require some help here - probably my c++ foo is not strong enough, but I cannot construct a test case that triggers this code path - can you provide a minimal example I could turn into a test case?

My thinking goes like this: a class has a vtable if it contains virtual functions or any of its base classes contains virtual functions. So for this to trigger, we'd require a type that contains itself somehow in one of its base classes? I played around with type aliases and recursive templates, but could not trigger a failure case. Can you help?

We're in a situation where ItemId::has_vtable calls Item::has_vtable calls Type::has_vtable.

You've lost me here. There are only CompInfo::has_vtable, TemplateInstantiation::has_vtable and Type::has_vtable. Neither Item nor ItemId have the method.

That said... did you follow the psuedocode for the template analysis? https://github.com/servo/rust-bindgen/blob/master/src/ir/named.rs#L212-L260. Let me know if I've helped elucidate the fixpoint stuff at all or if I've simply muddied the waters.

I read the pseudocode, but do not feel myself ready to get started hacking on this. Is there an overview of when this analysis is run and some tests/debugging information I could look at?

[fitzgen]

Hi @SirVer !

My thinking goes like this: a class has a vtable if it contains virtual functions or any of its base classes contains virtual functions. So for this to trigger, we'd require a type that contains itself somehow in one of its base classes? I played around with type aliases and recursive templates, but could not trigger a failure case. Can you help?

I think you're right, and I think we don't need the detect-recursion checks for this at all. It was probably a bug that we ever needed them that we have since fixed... and when I say "we" it was definitely "me" who introduced these particular checks, so I must be at fault here :-P

You've lost me here. There are only CompInfo::has_vtable, TemplateInstantiation::has_vtable and Type::has_vtable. Neither Item nor ItemId have the method.

Woops, my bad, I was just going off memory of how most of the others are structured.

I read the pseudocode, but do not feel myself ready to get started hacking on this.

Here is a skeleton of an implementation:

// src/ir/context.rs

struct BindgenContext<'ctx> {
    // ...

    // Populated when we enter codegen by `compute_has_vtable`; always `None`
    // before that and `Some` after.
    have_vtable: Option<HashSet<ItemId>>,
}

impl<'ctx> BindgenContext<'ctx> {
    // ...

    // Right above `find_used_template_parameters` would be a good place for
    // these.

    fn compute_has_vtable(&mut self) {
        assert!(self.have_vtable.is_none());
        self.have_vtable = Some(analyze::<HasVtableAnalysis>(self));
    }

    pub fn lookup_item_id_has_vtable(&self, id: ItemId) -> bool {
        assert!(self.in_codegen_phase(),
                "We only compute vtables when we enter codegen");

        // Look up the computed value for whether the item with `id` has a
        // vtable or not.
        self.have_vtable.as_ref().unwrap().contains(&id)
    }

    // ...
}

// src/ir/has_vtable.rs

// Assuming that this got pulled out into its own module now that it isn't only
// used by the template params analysis...
use super::analysis::MonotoneFramework;

struct HasVtableAnalysis<'ctx, 'gen>
    where 'gen: 'ctx
{
    ctx: &'ctx BindgenContext<'gen>,

    // The incremental result of this analysis's computation. Everything in this
    // set definitely has a vtable.
    have_vtable: HashSet<ItemId>,

    // Dependencies saying that if a key ItemId has been inserted into the
    // `have_vtable` set, then each of the ids in Vec<ItemId> need to be
    // considered again.
    //
    // This is a subset of the natural IR graph with reversed edges, where we
    // only include the edges from the IR graph that can affect whether a type
    // has a vtable or not.
    dependencies: HashMap<ItemId, Vec<ItemId>>,
}

impl<'ctx, 'gen> HasVtableAnalysis<'ctx, 'gen> {
    fn consider_edge(kind: EdgeKind) -> bool {
        match kind {
            // These are the only edges that can affect whether a type has a
            // vtable or not.
            EdgeKind::TypeReference |
            EdgeKind::BaseMember |
            EdgeKind::TemplateDeclaration => true,
            _ => false,
        }
    }
}

impl<'ctx, 'gen> MonotoneFramework for HasVtableAnalysis<'ctx, 'gen> {
    type node = ItemId;
    type Extra = &'ctx BindgenContext<'gen>;
    type Output = HashSet<ItemId>;

    fn new(ctx: &'ctx BindgenContext<'gen>) -> HasVtableAnalysis<'ctx, 'gen> {
        // Construct dependencies... check out how `UsedTemplateParameters` does
        // it.
        unimplemented!()
    }

    fn initial_worklist(&self) -> Vec<ItemId> {
        self.ctx.whitelisted_items().collect()
    }

    fn constrain(&mut self, id: ItemId) -> bool {
        if self.has_vtable.contains(&id) {
            // We've already computed that this type has a vtable and that can't
            // change.
            return false;
        }

        // If this id's item is a Type with TypeKind::Comp, check if we saw a
        // virtual function when parsing it (the `comp.has_vtable` property), or
        // whether any of its base members' ids are contained in
        // `self.have_vtable`. If yes to either, add this id to
        // `self.have_vtable` and return `true` to tell the `analyze` function
        // that dependents need updating now.
        unimplemented!();

        // If this id's item is a Type with TypeKind::TemplateInstantiation,
        // then check if its template declaration is in `self.have_vtable`. If
        // yes, insert this id into `self.have_vtable` and return
        // `true`.
        unimplemented!();

        // If this id's `Item` is a `Type` with `TypeKind::TypeReference`, then
        // check if its referenced inner type is in `self.have_vtable`. If yes,
        // then insert this id and return true.
        unimplemented!();

        // For all other items, and if none of the above returned already, then
        // return false.
        false
    }

    fn each_depending_on<F>(&self, id: ItemId, mut f: F)
        where F: FnMut(ItemId),
    {
        // Same as `UsedTemplateParameters::each_depending_on`...
    }
}

impl<'ctx, 'gen> From<HasVtableAnalysis<'ctx, 'gen>> for HashSet<ItemId> {
    fn from(analysis: HasVtableAnalysis<'ctx, 'gen>) -> Self {
        analysis.have_vtable
    }
}

/// A convenience trait for the things for which we might wonder if they have a
/// vtable during codegen.
///
/// This is not for _computing_ whether the thing has a vtable, it is for
/// looking up the results of the HasVtableAnalysis's computations for a
/// specific thing.
trait HasVtable {
    type Extra;

    fn has_vtable(&self, ctx: &BindgenContext, extra: &Self::Extra) -> bool;
}

// src/ir/item.rs

impl HasVtable for ItemId {
    type Extra = ();

    fn has_vtable(&self, ctx: &BindgenContext, _: &()) -> bool {
        ctx.lookup_item_id_has_vtable(*self)
    }
}

impl HasVtable for Item {
    type Extra = ();

    fn has_vtable(&self, ctx: &BindgenContext, _: &()) -> bool {
        ctx.lookup_item_id_has_vtable(self.id())
    }
}

// src/ir/ty.rs

impl HasVtable for Type {
    // Note that we need the Type's Item to answer this question.
    type Extra = Item;

    fn has_vtable(&self, ctx: &BindgenContext, item: &Item) -> bool {
        // Prevent misuse with something like this...
        debug_assert_eq!(item.expect_type(), self);

        ctx.lookup_item_id_has_vtable(item.id())
    }
}

// Etc...

impl HasVtable for Comp { ... }
impl HasVtable for TemplateInstantiation { ... }

Does this help clear things up? Seem like a good springboard for you to start hacking on this?

Thanks!

[SirVer]

[detect-recursion checks]

So let's get rid of them to simplify the code a bit (#787).

You've lost me here. There are only CompInfo::has_vtable, TemplateInstantiation::has_vtable and Type::has_vtable. Neither Item nor ItemId have the method.

Woops, my bad, I was just going off memory of how most of the others are structured.

I still do not know where the TypeId for the local solution should come from.

[skeleton of monotone analysis]

This is very helpful. My vacations are over though, so I cannot promise if and when I get around to it, but I think this will help anybody tackling any of these issues.

[fitzgen]

I still do not know where the TypeId for the local solution should come from.

The type's ItemId is passed down by callers, that's what the HasVtable::Extra associated type is there for.

Maybe I am misunderstanding?

This is very helpful. My vacations are over though, so I cannot promise if and when I get around to it, but I think this will help anybody tackling any of these issues.

No problem. If you don't think you're going to work on this anytime soon, then let me know so I can mark the issue unassigned and up for grabs again.

Cheers!

[SirVer]

@fitzgen please unassign for now. Should I find some time to work on this, I'll reach out again.

[photoszzt]

@highfive assign me

[highfive]

Hey @photoszzt! Thanks for your interest in working on this issue. It's now assigned to you!