Allow passing arbitrary data from Searchers to Appliers

[rosekunkel]

Currently a Searcher can only pass data to an Applier in a Subst, which limits that data to a map from Vars to Ids. This makes it fairly awkward to create Rewrites that don't work like Patterns. For example, I have a rewrite rule where the Searcher partitions the children of a node into two disjoint sets. So for an enode like (+ 1 2 4 5 11 12) I had two sets like {1, 5, 11} and {2, 4, 12}. To pass this information to the rule's Applier, I had to create a subst like this:

{ ?a0 => 1, ?b1 => 2, ?b2 => 4, ?a3 => 5, ?a4 => 11, ?b5 => 12  }

And then in the Applier create a loop like

for i in 0.. {
    if let Some(arg) = subst.get(format!("?a{}", i).parse().unwrap()) {
        // add to the first set
    } else if Some(arg) = subst.get(format!("?b{}", i).parse().unwrap()) {
        // add to the second set
    } else {
        break;
    }
}

which is not ideal. It would be much nicer if I could just pass the two sets directly, or any other data that might be important for a particular rewrite rule.

[rosekunkel]

Ideally I think Searchers and Appliers would be generic over some type Data, and the current behavior could be recovered by setting Data = Subst.

[mwillsey]

Yeah, that's definitely awkward. I like your proposed design, but it would be a pretty major rework. If Searcher and Applier are generic over Data, then Rewrite must also be. But then we can't have a homogenous collection of Rewrites!

So we'll need a trait ErasedRewrite or something that erases the Data associated type, that way you can have a collection of Box<dyn ErasedRewrite>s or something.

Maybe we could get around this with some TypeId stuff or something, idk.

I also thing the ErasedRewrite will have to provide its own buffer to store substitutions, so rewrites will become stateful. That isn't so bad, but it's a change for sure. I'll try to make a draft of this soonish.

[mwillsey]

I am working on a solution for this. It should help a bunch of other things too.

[rupanshusoi]

Has there been any progress on this? It would be helpful in my use-case too.

[mwillsey]

Nothing has been upstreamed yet, but I have developed a useful change in a fork for another project. I hope to upstream it eventually! https://github.com/mwillsey/egg/tree/varargs