Panic: Revision set for ExactTree inconsistent with class mapping #521

Here's a minimized version of the test case (via #469).

I was able to minimize this a bit further:

// Base
module.exports = {
  'to be [FAILED]' : function(test) {},
  'to be [FAILED]' : function() {}
}

// Left
module.exports = {
  'to be [FAILED]' : function(test) {},
  'to be [FAILED]' : function() {},
  'to be with message [PASSED]' : function(test) {
    var expect = this.client.api.expect.element('#weblogin').to.be.an('input', 'weblogin should be an input');
    this.client.on('nightwatch:finished', function(results, errors) {})
  }
}

// Right
module.exports = {
  'to be [FAILED]' : function(test) {},
  'to be [FAILED]' : function() {},
}

(removing more of the contents of the last function on the left side removes the panic, most likely has due to matching thresholds)

So the right side just adds a trailing comma to the last function, while the left side adds a whole new function, which in turn requires the function before that to get a trailing comma. So seemingly quite obvious to resolve -- indeed, if I create a line-diff using git merge-file and feed that into mergiraf solve, everything works just fine.

I'll try running mergiraf merge --debug to investigate further

Hm, it's a bit in the weeds.

module.exports is a way to expose functions and whatnot defined in a Node.js module to the outside world -- see https://stackoverflow.com/a/5311377 for more info.

Since module.exports is a dictionary, I'm pretty sure its keys must be unique. One could imagine that the following two calls:

exampleModule.'to be [FAILED]'()
exampleModule.'to be [FAILED]'(test)

could actually get resolved to the first and second function from the repro, respectively, if JS supported method overloading, but it looks like it doesn't: https://stackoverflow.com/q/10855908

So the problem we run into is that after we've constructed the merged tree, we try to postprocess it, and correctly notice a duplicate signature. After that, the following happens:

1. we create a separator_example using find_separator. Due to the logic of find_separator, the separator is searched for in base, left, and right revisions, in this order. The base revision contains a separator, so we return a ,@base
2. later, we call merge_same_sigs, passing the separator there
3. we notice that the left and right sides are actually isomorphic, so we try to output them as-is
4. with add_separators(left_revnodes, separator_example), we create a new list using the separator_example
5. we then call MergedTree::new_exact on each node in this newly created list. The RevisionNESet we pass to that only contains the left and right revisions, because of step 3.
6. In new_exact, we try to class_mapping.node_at_rev(node, revision_set.any()), but that doesn't work when node = ,@Base and revision_set = [left, right]

The fix that came to mind was to adjust the search order in find_separator to match that of RevisionSet::any -- and that did indeed work! Now the return separator is ,@Left, which successfully passes step 6

Wait, something's not right. I need to investigate a bit more

Thanks for the detailed explanation! From this summary, what looks the most fishy to me is the call to MergedTree::new_exact with a RevisionNESet that seems wrong. If the separator is taken from the base revision, we shouldn't pretend it belongs to the left and right ones.

I agree, but it's still weird that, if I try to minimize the repro even more, this issue disappears -- even though separator is still ,@Base, it is now somehow able to be mapped to the node corresponding to it in the left revision. Or do you think that this has only been working by accident?

There is this comment in the code:

Maybe what we could do instead is to first try to find the separator in the given revision (so pass the revision to find_separator), and only if none is found, fall back to separator_example?

So for the left=right case, we could do

let separator = find_separator(Revision::Left).unwrap_or(separator_example);

Given that there can be cases where we have to use a separator that doesn't belong to the corresponding revision, I'd say we need to be able to keep track of where it comes from and to call MergedTree::new_exact with the appropriate revision value, no? (This is all just based on your description of the problem, I haven't debugged it myself, so I'm not sure it makes much sense.) Anyway, I'd aim to make a fix that we believe to be fully bullet proof in all cases, of course.

So for the actual nodes, we'd continue passing [left, right], but for the separators, we'd pass [separator.rev]?

That sounds like a good move, no? Assuming the nodes are indeed both in left and right revisions and are indeed mapped to the same leader in the class mapping…

That sounds like a good move, no?

I mean it did to me, but I wanted to know your opinion as well. It looks like we agree^^

Assuming the nodes are indeed both in left and right revisions and are indeed mapped to the same leader in the class mapping...

I guess AST isomorphism ensures that? I could try to (temporarily) add an assertion there and see if it holds.

I already tried doing this mapping in the left=right branch only, and the result wasn't pretty – I basically needed to inline add_separators and insert the revision-addition logic into that. The comment I linked above was talking about the left!=right branch handling separator somewhat incorrectly as well, so I want to try to see if I can come up with a fix that handles both branches at once. I'll report back with how that worked out

I guess AST isomorphism ensures that? I could try to (temporarily) add an assertion there and see if it holds.

It's possible that some nodes are isomorphic but haven't been matched by the heuristics. For instance, this can happen if different numbers of identical copies of a node are present in both revisions, in which case some of them will stay unmatched.
So generally, we should really just use the class mapping to look up which revisions a given node is part of, and just use that.