[
Date Prev][
Date Next][
Thread Prev][
Thread Next][
Date Index][
Thread Index]
[
List Home]
|
Re: [jgit-dev] "instable" diff algorithms lead to wrong merge results
|
Hi,
> 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.
I also think we have a bug in the merge algorithm. But I have not yet
found out where it is. My merge algorithm fails because the diffs
don't report an insertion at the same point in the original file.
Maybe I explain how the current jgit merge works with the real-world
example mentioned above (take egit repo and merge 3e494ae and cb2e630,
look at org.eclipse.egit.ui/src/org/eclipse/egit/ui/internal/EgitUiEditorUtils.java).
During that merge I get the following sets of Edits:
base - ours (called baseToOurs): INSERT(19-19,19-20),
INSERT(27-27,28-29), INSERT(28-28,30-31), INSERT(60-60,63-97)
base - theirs (called baseToTheirs): INSERT(63-63,63-83)
Lets call the 4 numbers for an EDIT beginA, endA, beginB, endB. beginA
and endA are line numbers in the common base. beginB, endB are the
line numbers in commits to be merged. The edits are always sorted by
beginA
The current merge algorithm goes through that main loop:
while (...) {
if (oursEdit.getEndA() <= theirsEdit.getBeginA()) {
// applyOurs
oursEdit = baseToOurs.next();
} else if (theirsEdit.getEndA() <= oursEdit.getBeginA()) {
// applyTheirs
theirsEdit = baseToTheirs.next();
} else {
// a potential conflict found ... do a lot of magic to harmonize
// starts of edits, combine edits, find out that edits are not
// conflicting because they introduce the same content ...
oursEdit = baseToOurs.next();
theirsEdit = baseToTheirs.next();
}
In our example I never fall into the conflict case --- all the edits
are independent because they don't touch the same lines in the
original text.
> 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
That's where I don't see it, sorry. Look at the edits: they are not
inserting at the same position.
