diff options
4 files changed, 181 insertions, 17 deletions
diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/diff/AbstractDiffTestCase.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/diff/AbstractDiffTestCase.java index b8f8dcb5ad..4130b7ee5b 100644 --- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/diff/AbstractDiffTestCase.java +++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/diff/AbstractDiffTestCase.java @@ -196,6 +196,32 @@ public abstract class AbstractDiffTestCase { } @Test + public void testEdit_DeleteNearCommonTail() { + EditList r = diff(t("aCq}nD}nb"), t("aq}nb")); + assertEquals(new Edit(1, 2, 1, 1), r.get(0)); + assertEquals(new Edit(5, 8, 4, 4), r.get(1)); + assertEquals(2, r.size()); + } + + @Test + public void testEdit_DeleteNearCommonCenter() { + EditList r = diff(t("abcd123123uvwxpq"), t("aBcd123uvwxPq")); + assertEquals(new Edit(1, 2, 1, 2), r.get(0)); + assertEquals(new Edit(7, 10, 7, 7), r.get(1)); + assertEquals(new Edit(14, 15, 11, 12), r.get(2)); + assertEquals(3, r.size()); + } + + @Test + public void testEdit_InsertNearCommonCenter() { + EditList r = diff(t("aBcd123uvwxPq"), t("abcd123123uvwxpq")); + assertEquals(new Edit(1, 2, 1, 2), r.get(0)); + assertEquals(new Edit(7, 7, 7, 10), r.get(1)); + assertEquals(new Edit(11, 12, 14, 15), r.get(2)); + assertEquals(3, r.size()); + } + + @Test public void testEdit_LinuxBug() { EditList r = diff(t("a{bcdE}z"), t("a{0bcdEE}z")); assertEquals(new Edit(2, 2, 2, 3), r.get(0)); diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/merge/MergeAlgorithmTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/merge/MergeAlgorithmTest.java index d4a3d62dad..5af62b6704 100644 --- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/merge/MergeAlgorithmTest.java +++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/merge/MergeAlgorithmTest.java @@ -132,6 +132,45 @@ public class MergeAlgorithmTest { } /** + * Merge two modifications with a shared delete at the end. The underlying + * diff algorithm has to provide consistent edit results to get the expected + * merge result. + * + * @throws IOException + */ + @Test + public void testTwoModificationsWithSharedDelete() throws IOException { + assertEquals(t("Cb}n}"), + merge("ab}n}n}", "ab}n}", "Cb}n}")); + } + + /** + * Merge modifications with a shared insert in the middle. The + * underlying diff algorithm has to provide consistent edit + * results to get the expected merge result. + * + * @throws IOException + */ + @Test + public void testModificationsWithMiddleInsert() throws IOException { + assertEquals(t("aBcd123123uvwxPq"), + merge("abcd123uvwxpq", "aBcd123123uvwxPq", "abcd123123uvwxpq")); + } + + /** + * Merge modifications with a shared delete in the middle. The + * underlying diff algorithm has to provide consistent edit + * results to get the expected merge result. + * + * @throws IOException + */ + @Test + public void testModificationsWithMiddleDelete() throws IOException { + assertEquals(t("Abz}z123Q"), + merge("abz}z}z123q", "Abz}z123Q", "abz}z123q")); + } + + /** * Test a conflicting region at the very start of the text. * * @throws IOException diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/diff/DiffAlgorithm.java b/org.eclipse.jgit/src/org/eclipse/jgit/diff/DiffAlgorithm.java index bd6e5c859a..5f01366c47 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/diff/DiffAlgorithm.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/diff/DiffAlgorithm.java @@ -121,23 +121,7 @@ public abstract class DiffAlgorithm { Subsequence<S> as = Subsequence.a(a, region); Subsequence<S> bs = Subsequence.b(b, region); EditList e = Subsequence.toBase(diffNonCommon(cs, as, bs), as, bs); - - // The last insertion may need to be shifted later if it - // inserts elements that were previously reduced out as - // common at the end. - // - Edit last = e.get(e.size() - 1); - if (last.getType() == Edit.Type.INSERT) { - while (last.endB < b.size() - && cmp.equals(b, last.beginB, b, last.endB)) { - last.beginA++; - last.endA++; - last.beginB++; - last.endB++; - } - } - - return e; + return normalize(cmp, e, a, b); } case EMPTY: @@ -153,6 +137,107 @@ public abstract class DiffAlgorithm { } /** + * Reorganize an {@link EditList} for better diff consistency. + * <p> + * {@code DiffAlgorithms} may return {@link Edit.Type#INSERT} or + * {@link Edit.Type#DELETE} edits that can be "shifted". For + * example, the deleted section + * <pre> + * -a + * -b + * -c + * a + * b + * c + * </pre> + * can be shifted down by 1, 2 or 3 locations. + * <p> + * To avoid later merge issues, we shift such edits to a + * consistent location. {@code normalize} uses a simple strategy of + * shifting such edits to their latest possible location. + * <p> + * This strategy may not always produce an aesthetically pleasing + * diff. For instance, it works well with + * <pre> + * function1 { + * ... + * } + * + * +function2 { + * + ... + * +} + * + + * function3 { + * ... + * } + * </pre> + * but less so for + * <pre> + * # + * # comment1 + * # + * function1() { + * } + * + * # + * +# comment3 + * +# + * +function3() { + * +} + * + + * +# + * # comment2 + * # + * function2() { + * } + * </pre> + * <a href="https://github.com/mhagger/diff-slider-tools">More + * sophisticated strategies</a> are possible, say by calculating a + * suitable "aesthetic cost" for each possible position and using + * the lowest cost, but {@code normalize} just shifts edits + * to the end as much as possible. + * + * @param <S> + * type of sequence being compared. + * @param cmp + * the comparator supplying the element equivalence function. + * @param e + * a modifiable edit list comparing the provided sequences. + * @param a + * the first (also known as old or pre-image) sequence. + * @param b + * the second (also known as new or post-image) sequence. + * @return a modifiable edit list with edit regions shifted to their + * latest possible location. The result list is never null. + * @since 4.7 + */ + private static <S extends Sequence> EditList normalize( + SequenceComparator<? super S> cmp, EditList e, S a, S b) { + Edit prev = null; + for (int i = e.size() - 1; i >= 0; i--) { + Edit cur = e.get(i); + Edit.Type curType = cur.getType(); + + int maxA = (prev == null) ? a.size() : prev.beginA; + int maxB = (prev == null) ? b.size() : prev.beginB; + + if (curType == Edit.Type.INSERT) { + while (cur.endA < maxA && cur.endB < maxB + && cmp.equals(b, cur.beginB, b, cur.endB)) { + cur.shift(1); + } + } else if (curType == Edit.Type.DELETE) { + while (cur.endA < maxA && cur.endB < maxB + && cmp.equals(a, cur.beginA, a, cur.endA)) { + cur.shift(1); + } + } + prev = cur; + } + return e; + } + + /** * Compare two sequences and identify a list of edits between them. * * This method should be invoked only after the two sequences have been diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/diff/Edit.java b/org.eclipse.jgit/src/org/eclipse/jgit/diff/Edit.java index 7eecd13513..3ac46ea121 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/diff/Edit.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/diff/Edit.java @@ -170,6 +170,20 @@ public class Edit { } /** + * Move the edit region by the specified amount. + * @param amount + * the region is shifted by this amount, and can be + * positive or negative. + * @since 4.7 + */ + public final void shift(int amount) { + beginA += amount; + endA += amount; + beginB += amount; + endB += amount; + } + + /** * Construct a new edit representing the region before cut. * * @param cut |