Community
Participate
Working Groups
Build Identifier: 3.4.2 Eclipse three-way merge wrongly detects a conflict, when the changes are adjoining each other (even when the changes are not overlapping). The table below is a sample scenario. Base file contains 4 lines (A, B, C, D). The left-side change is on line 2 B->B1. The right-side change is on line 3 C->C1. These changes are not overlapping, but when compare these files, current merge tool reports conflict on line 2 and line 3. Expected (desired) behavior is, the tool reports left change on line 2 and right change on line 3, which can be auto-merged. # | base | left | right | merge (cur) | merge (expected) --+---------+---------+---------+---------------+----------------- 1 | A | A | A | | 2 | B | B1 | B | <-conflict | <-left changed 3 | C | C | C1 | <-conflict | <-right changed 4 | D | D | D | | Reproducible: Always Steps to Reproduce: 1. import attachement files (0_base.txt, 1_left.txt, 2_right.txt). 2. select above 3 files, right-click and select "Compare With" -> "Each Other". 3. select "0_base.txt" as base file. 4. see the result.
Created attachment 162374 [details] Test case text files (0_base.txt, 1_left.txt, 2_right.txt)
I investigated the source code (of Eclipse 3.4.2) and analyze the behavior. Could you kindly review my analysis? I suspect that the cause of this problem would be on overlapping detection logic in org.eclipse.compare.rangedifferencer.RangeDifferencer class. In findDifferences(IProgressMonitor pm, IRangeComparator ancestor, IRangeComparator left, IRangeComparator right) method, while loop that checking the overlapping ranges is using "<=" to compare range start location of candidate change with the range end location of current change (changeRangeEnd). The value of changeRangeEnd is almost the next index of the range, so it should use "<" to compare the value. ------------------------------------------- << /* 171 */ while (other.fDifference != null && other.fDifference.fLeftStart <= changeRangeEnd) { >> /* 171 */ while (other.fDifference != null && other.fDifference.fLeftStart < changeRangeEnd) { ------------------------------------------- But this modification causes regression that could not detect conflict of "insertion". Insertion scenario 1 (conflict) # | base | left | right | merge (cur) | merge (expected?) --+---------+---------+---------+---------------+----------------- 1 | A | A | A | | 2 | B | B | B | | 3 | C | X | Y | <-conflict | <-conflict 4 | | C | C | | When the left-side and right-side are inserting lines into the same position, it should be detected as conflict. In this case, the changeRangeEnd is the same value of other's fLeftStart value. I thought the meaning of "conflict" should be cleared on "inserting" changes and summarize the behavior of current implementation and expected behavior. [Change types] (A) Change to line N (B) Insert lines between line N and line N+1 (C) Change to line N+1 (D) Change to lines including N and N+1 [Table of conbination of change types and conflict detection behavior] | left | right | conflict(cur) | conflict (expected) -------+-------+---------------+---------- | (A) | (A) | yes | yes | (A) | (B) | yes | no | (A) | (C) | yes | no | (A) | (D) | yes | yes | (B) | (B) | yes | yes | (B) | (C) | yes | no | (B) | (D) | yes | yes | (C) | (C) | yes | yes | (C) | (D) | yes | yes | (D) | (D) | yes | yes For example, a senario like below I thought, the changes should not be detected as conflict. This is a conbination of (B) Insert "X" between line 2 and 3 (C) Change to line 3. Insertion scenario 2 (not conflict?) # | base | left | right | merge (cur) | merge (expected?) --+---------+---------+---------+---------------+----------------- 1 | A | A | A | | 2 | B | B | B | | 3 | C | X | C1 | <-conflict | <-left changed (inserted) 4 | | C | | | <-right changed To make RangeDifferencer behave like above, I implemented expected logic and attached a patch (for Eclipse 3.4.2). 1. use "<" instead of "<=" in overlap detection while loop. 2. treat "insert" changes (fLeftLength = 0) differently from "modification or deletion" changes.
Created attachment 162377 [details] draft patch of RangeDifferencer class
Shuichi, thanks for the patch. I'll look closer at it in the current milestone.
> To make RangeDifferencer behave like above, I implemented expected logic and > attached a patch (for Eclipse 3.4.2). Shuichi, thanks for the investigation. Could you please update the patch to HEAD? The fix will not be backported into the maintenance streams. Also please provide a test in org.eclipse.compare.tests project.
Created attachment 164655 [details] Patch to HEAD (13/04/2010) (testcase included) Pawel, I have created a patch to HEAD (13/04/2010). This is multi project patch (rooted on workspace) that includes: 1. RangeDifferencer.java patch (in org.eclipse.compare.core) 2. new testcase class RangeDifferencer3WayDiffTest.java (in org.eclipse.compare.tests).
Created attachment 165466 [details] Patch_v01 Patch from comment 6 with minor update.
Patch_v01 in HEAD, marking as FIXED. Thanks Shuichi.
