Fix crashes on rare combination of file names
The NameConflictTreeWalk class is used in merge for iterating over
entries in commits. The class uses a separate iterator for each
commit's tree. In rare cases it can incorrectly report the same entry
twice. As a result, duplicated entries are added to the merge result
and later jgit throws an exception when it tries to process merge
result.
The problem appears only when there is a directory-file conflict for
the last item in trees. Example from the bug:
Commit 1:
* subtree - file
* subtree-0 - file
Commit 2:
* subtree - directory
* subtree-0 - file
Here the names are ordered like this:
"subtree" file <"subtree-0" file < "subtree" directory.
The NameConflictTreeWalk handles similar cases correctly if there are
other files after subtree... in commits - this is processed in the
AbstractTreeIterator.min function. Existing code has a special
optimization for the case, when all trees are pointed to the same
entry name - it skips additional checks. However, this optimization
incorrectly skips checks if one of trees reached the end.
The fix processes a situation when some trees reached the end, while
others are still point to an entry.
bug: 535919
Change-Id: I62fde3dd89779fac282479c093400448b4ac5c86
diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/merge/MergerTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/merge/MergerTest.java
index dc119c9..022e8cd 100644
--- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/merge/MergerTest.java
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/merge/MergerTest.java
@@ -1036,6 +1036,32 @@
}
/**
+ * This is a high-level test for https://bugs.eclipse.org/bugs/show_bug.cgi?id=535919
+ *
+ * The actual fix was made in {@link org.eclipse.jgit.treewalk.NameConflictTreeWalk}
+ * and tested in {@link org.eclipse.jgit.treewalk.NameConflictTreeWalkTest#tesdDF_LastItemsInTreeHasDFConflictAndSpecialNames}.
+ */
+ @Theory
+ public void checkMergeDoesntCrashWithSpecialFileNames(
+ MergeStrategy strategy) throws Exception {
+ Git git = Git.wrap(db);
+
+ writeTrashFile("subtree", "");
+ writeTrashFile("subtree-0", "");
+ git.add().addFilepattern("subtree").call();
+ git.add().addFilepattern("subtree-0").call();
+ RevCommit toMerge = git.commit().setMessage("commit-1").call();
+
+ git.rm().addFilepattern("subtree").call();
+ writeTrashFile("subtree/file", "");
+ git.add().addFilepattern("subtree").call();
+ RevCommit mergeTip = git.commit().setMessage("commit2").call();
+
+ ResolveMerger merger = (ResolveMerger) strategy.newMerger(db, false);
+ assertTrue(merger.merge(mergeTip, toMerge));
+ }
+
+ /**
* Merging after criss-cross merges. In this case we merge together two
* commits which have two equally good common ancestors
*
diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/treewalk/NameConflictTreeWalkTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/treewalk/NameConflictTreeWalkTest.java
index f03163d..69d90aa 100644
--- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/treewalk/NameConflictTreeWalkTest.java
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/treewalk/NameConflictTreeWalkTest.java
@@ -137,6 +137,177 @@
}
}
+ /**
+ * The test reproduces https://bugs.eclipse.org/bugs/show_bug.cgi?id=535919.
+ */
+ @Test
+ public void tesdDF_LastItemsInTreeHasDFConflictAndSpecialNames()
+ throws Exception {
+
+ final DirCache tree0 = db.readDirCache();
+ final DirCache tree1 = db.readDirCache();
+
+ final DirCacheBuilder b0 = tree0.builder();
+ final DirCacheBuilder b1 = tree1.builder();
+ // The tree0 has the following order in git:
+ // subtree, subtree-0
+ b0.add(createEntry("subtree", REGULAR_FILE));
+ b0.add(createEntry("subtree-0", REGULAR_FILE));
+ // The tree1 has the following order in git:
+ // subtree-0, subtree/file
+ b1.add(createEntry("subtree/file", REGULAR_FILE));
+ b1.add(createEntry("subtree-0", REGULAR_FILE));
+
+ b0.finish();
+ b1.finish();
+
+ try (NameConflictTreeWalk tw = new NameConflictTreeWalk(db)) {
+ tw.addTree(new DirCacheIterator(tree0));
+ tw.addTree(new DirCacheIterator(tree1));
+
+ assertModes("subtree", REGULAR_FILE, TREE, tw);
+ assertTrue(tw.isSubtree());
+ assertTrue(tw.isDirectoryFileConflict());
+ tw.enterSubtree();
+ assertModes("subtree/file", MISSING, REGULAR_FILE, tw);
+ assertFalse(tw.isSubtree());
+ // isDirectoryFileConflict is true, because the conflict is detected
+ // on parent.
+ assertTrue(tw.isDirectoryFileConflict());
+ assertModes("subtree-0", REGULAR_FILE, REGULAR_FILE, tw);
+ assertFalse(tw.isSubtree());
+ assertFalse(tw.isDirectoryFileConflict());
+ assertFalse(tw.next());
+ }
+ }
+
+ /**
+ * The test reproduces https://bugs.eclipse.org/bugs/show_bug.cgi?id=535919.
+ */
+ @Test
+ public void tesdDF_LastItemsInTreeHasDFConflictAndSpecialNames2()
+ throws Exception {
+
+ final DirCache tree0 = db.readDirCache();
+ final DirCache tree1 = db.readDirCache();
+
+ final DirCacheBuilder b0 = tree0.builder();
+ final DirCacheBuilder b1 = tree1.builder();
+ // The tree0 has the following order in git:
+ // subtree-0, subtree/file
+ b0.add(createEntry("subtree/file", REGULAR_FILE));
+ b0.add(createEntry("subtree-0", REGULAR_FILE));
+ // The tree1 has the following order in git:
+ // subtree, subtree-0
+ b1.add(createEntry("subtree", REGULAR_FILE));
+ b1.add(createEntry("subtree-0", REGULAR_FILE));
+
+ b0.finish();
+ b1.finish();
+
+ try (NameConflictTreeWalk tw = new NameConflictTreeWalk(db)) {
+ tw.addTree(new DirCacheIterator(tree0));
+ tw.addTree(new DirCacheIterator(tree1));
+
+ assertModes("subtree", TREE, REGULAR_FILE, tw);
+ assertTrue(tw.isSubtree());
+ assertTrue(tw.isDirectoryFileConflict());
+ tw.enterSubtree();
+ assertModes("subtree/file", REGULAR_FILE, MISSING, tw);
+ assertFalse(tw.isSubtree());
+ // isDirectoryFileConflict is true, because the conflict is detected
+ // on parent.
+ assertTrue(tw.isDirectoryFileConflict());
+ assertModes("subtree-0", REGULAR_FILE, REGULAR_FILE, tw);
+ assertFalse(tw.isSubtree());
+ assertFalse(tw.isDirectoryFileConflict());
+ assertFalse(tw.next());
+ }
+ }
+
+ @Test
+ public void tesdDF_NonLastItemsInTreeHasDFConflictAndSpecialNames()
+ throws Exception {
+ final DirCache tree0 = db.readDirCache();
+ final DirCache tree1 = db.readDirCache();
+
+ final DirCacheBuilder b0 = tree0.builder();
+ final DirCacheBuilder b1 = tree1.builder();
+ b0.add(createEntry("subtree", REGULAR_FILE));
+ b0.add(createEntry("subtree-0", REGULAR_FILE));
+ b0.add(createEntry("x", REGULAR_FILE));
+
+ b1.add(createEntry("subtree/file", REGULAR_FILE));
+ b1.add(createEntry("subtree-0", REGULAR_FILE));
+ b1.add(createEntry("x", REGULAR_FILE));
+
+ b0.finish();
+ b1.finish();
+
+ try (NameConflictTreeWalk tw = new NameConflictTreeWalk(db)) {
+ tw.addTree(new DirCacheIterator(tree0));
+ tw.addTree(new DirCacheIterator(tree1));
+
+ assertModes("subtree", REGULAR_FILE, TREE, tw);
+ assertTrue(tw.isSubtree());
+ assertTrue(tw.isDirectoryFileConflict());
+ tw.enterSubtree();
+ assertModes("subtree/file", MISSING, REGULAR_FILE, tw);
+ assertFalse(tw.isSubtree());
+ // isDirectoryFileConflict is true, because the conflict is detected
+ // on parent.
+ // see JavaDoc for isDirectoryFileConflict for details
+ assertTrue(tw.isDirectoryFileConflict());
+ assertModes("subtree-0", REGULAR_FILE, REGULAR_FILE, tw);
+ assertFalse(tw.isSubtree());
+ assertFalse(tw.isDirectoryFileConflict());
+ assertModes("x", REGULAR_FILE, REGULAR_FILE, tw);
+ assertFalse(tw.isSubtree());
+ assertFalse(tw.isDirectoryFileConflict());
+ assertFalse(tw.next());
+ }
+ }
+
+ @Test
+ public void tesdDF_NoSpecialNames() throws Exception {
+ final DirCache tree0 = db.readDirCache();
+ final DirCache tree1 = db.readDirCache();
+
+ final DirCacheBuilder b0 = tree0.builder();
+ final DirCacheBuilder b1 = tree1.builder();
+ // In this test both trees (tree0 and tree1) have exactly the same order
+ // of entries:
+ // subtree, xubtree-0
+ b0.add(createEntry("subtree", REGULAR_FILE));
+ b0.add(createEntry("xubtree-0", REGULAR_FILE));
+
+ b1.add(createEntry("subtree/file", REGULAR_FILE));
+ b1.add(createEntry("xubtree-0", REGULAR_FILE));
+
+ b0.finish();
+ b1.finish();
+
+ try (NameConflictTreeWalk tw = new NameConflictTreeWalk(db)) {
+ tw.addTree(new DirCacheIterator(tree0));
+ tw.addTree(new DirCacheIterator(tree1));
+
+ assertModes("subtree", REGULAR_FILE, TREE, tw);
+ assertTrue(tw.isSubtree());
+ assertTrue(tw.isDirectoryFileConflict());
+ tw.enterSubtree();
+ assertModes("subtree/file", MISSING, REGULAR_FILE, tw);
+ assertFalse(tw.isSubtree());
+ // isDirectoryFileConflict is true, because the conflict is detected
+ // on parent.
+ // see JavaDoc for isDirectoryFileConflict for details
+ assertTrue(tw.isDirectoryFileConflict());
+ assertModes("xubtree-0", REGULAR_FILE, REGULAR_FILE, tw);
+ assertFalse(tw.isSubtree());
+ assertFalse(tw.isDirectoryFileConflict());
+ assertFalse(tw.next());
+ }
+ }
+
@Test
public void testDF_specialFileNames() throws Exception {
final DirCache tree0 = db.readDirCache();
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/treewalk/NameConflictTreeWalk.java b/org.eclipse.jgit/src/org/eclipse/jgit/treewalk/NameConflictTreeWalk.java
index 2fd945b..ffb4137 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/treewalk/NameConflictTreeWalk.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/treewalk/NameConflictTreeWalk.java
@@ -56,6 +56,13 @@
public class NameConflictTreeWalk extends TreeWalk {
private static final int TREE_MODE = FileMode.TREE.getBits();
+ /**
+ * True if all {@link #trees} point to entries with equal names.
+ *
+ * If at least one tree iterator point to a different name or
+ * reached end of the tree, the value is false.
+ * Note: if all iterators reached end of trees, the value is true.
+ */
private boolean allTreesNamesMatchFastMinRef;
private AbstractTreeIterator dfConflict;
@@ -125,13 +132,20 @@
return trees[trees.length - 1];
}
AbstractTreeIterator minRef = trees[i];
- allTreesNamesMatchFastMinRef = true;
+ // if i > 0 then we already know that only some trees reached the end
+ // (but not all), so it is impossible that ALL trees points to the
+ // minRef entry.
+ // Only if i == 0 it is still possible that all trees points to the same
+ // minRef entry.
+ allTreesNamesMatchFastMinRef = i == 0;
boolean hasConflict = false;
minRef.matches = minRef;
while (++i < trees.length) {
final AbstractTreeIterator t = trees[i];
- if (t.eof())
+ if (t.eof()) {
+ allTreesNamesMatchFastMinRef = false;
continue;
+ }
final int cmp = t.pathCompare(minRef);
if (cmp < 0) {
@@ -152,8 +166,9 @@
// Exact name/mode match is best.
//
t.matches = minRef;
- } else if (allTreesNamesMatchFastMinRef && isTree(t) && !isTree(minRef)
- && !isGitlink(minRef) && nameEqual(t, minRef)) {
+ } else if (allTreesNamesMatchFastMinRef && isTree(t)
+ && !isTree(minRef) && !isGitlink(minRef)
+ && nameEqual(t, minRef)) {
// The minimum is a file (non-tree) but the next entry
// of this iterator is a tree whose name matches our file.
// This is a classic D/F conflict and commonly occurs like