Absence of conflict in delete/modify case

[wetneb]

I found a case where spork doesn't produce any conflict while I intuitively think it should. Informally:

• On the left side, you replace (or delete) a node n
• On the right side, you make a change to some descendant of n

In this scenario, as a user I would intuitively expect to be presented with a conflict, because automatically choosing the version of the left side silently discards changes from the right side.

The example below is quite minimalistic, but I think it's a real problem in real usage scenarios. For instance, say the left side inlines a method and the right side makes changes to the method's body. In such a case I don't want the merge driver to silently discard the changes of the right side, especially if the inlining is happening across multiple files, in which case there is no chance spork is able to replicate the changes to the method body in places where the method was used.

This seems to be a rather fundamental problem of the algorithm as it stands: I don't see how to tweak the procedure to reconstruct a tree from a change set to fix this issue. What do you think @slarse?

Base.java

class MyCls {
     public void foo(int t) {
          int a = (t + 8) * 5 - 3;
     }
}

Left.java

class MyCls {
     public void foo(int t) {
          int a = 23 - 3;
     }
}

Right.java

class MyCls {
     public void foo(int t) {
          int a = t * 5 - 3;
     }
}

Current output

class MyCls {
    public void foo(int t) {
        int a = 23 - 3;
    }
}

Expected output

Something along the lines of what git merge-file produces (or with a narrower conflict):

class MyCls {
     public void foo(int t) {
<<<<<<< Left.java
          int a = 23 - 3;
||||||| Base.java
          int a = (t + 8) * 5 - 3;
=======
          int a = t * 5 - 3;
>>>>>>> Right.java
     }
}

[slarse]

Hi @wetneb,

This falls under the category of delete/edit conflicts (one revision deletes a subtree, the other revision edits said subtree). 3DM-merge cannot detect this kind of conflict, and Spork hasn't changed this. See section 6.1 of the whitepaper. Section 5.6.4 of my master's thesis contains a more elaborate description of the problem.

In theory, it should be possible to detect these kinds of conflicts with some post processing. After the merge is done, scan all deleted subtrees. If there are PCS triples in any deleted subtree that does not exist in the base revision, then a delete/edit conflict has taken place. Then one could locate the parent of the deleted subtree and do a textual merge of it instead of a structured merge, and then patch the merged AST.

It's probably rather tricky to accomplish.

[wetneb]

Thanks a lot! I missed that part of the paper apparently. I'm experimenting with the approach you describe above, with a slight twist: keeping track of deleted subtrees can happen during reconstruction of the tree from the PCS triples already (when scanning the children of a node, check which ones from the base revision don't end up in the final reconstruction).
It seems to work okay so far! I'll share the code once it's ready.