Re: [jgit-dev] "instable" diff algorithms lead to wrong merge results

[Shawn Pearce <spearce@xxxxxxxxxxx>]

On Mon, Nov 8, 2010 at 2:21 PM, Christian Halstrick
<christian.halstrick@xxxxxxxxx> wrote:
> Here is now a concrete real-life example:
> - clone egit from git://egit.eclipse.org/egit.git
> - checkout 3e494ae and then merge cb2e630 (try the merge with native
> git and with EGit)
> - inspect lines 66-118 of file
> org.eclipse.egit.ui/src/org/eclipse/egit/ui/internal/EgitUiEditorUtils.java
>
> Problem: Native git reports a conflict during merge and JGit
> (regardless wether we use Myers- or HistogramDiff) does not
> Reason: Both commits insert a new method at the same position of the
> original text. They don't insert the same method but two different
> methods. But in JGit when comparing BASE and OURS the insertion is at
> line X and when comparing BASE and THEIRS the insertion is at line
> X+2. That means for JGit these insertions are independent and don't
> produce a conflict. Native git seems to produce the same
> insertion-point when comparing BASE and OURS and BASE and THEIRS - and
> therefore report an conflict.

This sounds a lot like we aren't taking into account the inserts made
by one side when computing the matching positions in the other side.
C Git is probably using an algorithm similar to what we do in Gerrit
Code Review when we line the files up in a side-by-side view... use 3
iterators and create the output file by walking through all of the
lines in parallel.  Adjust your iterators based on the two Edit lists
going against the base.

If we did that we would be able to easily see that both sides have an
INSERT at the same position, and the text being INSERT'ed isn't
identical, which results in a conflict.  This simple side-by-side
style iteration would easily identify those cases.

-- 
Shawn.