From cb9f058f9b260dfa0878f7b8bf42936a7e330d35 Mon Sep 17 00:00:00 2001 From: Dmitrii Filippov Date: Mon, 27 Jun 2022 20:03:53 +0200 Subject: [PATCH] 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 --- .../org/eclipse/jgit/merge/MergerTest.java | 26 +++ .../treewalk/NameConflictTreeWalkTest.java | 171 ++++++++++++++++++ .../jgit/treewalk/NameConflictTreeWalk.java | 23 ++- 3 files changed, 216 insertions(+), 4 deletions(-) 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 dc119c90ff..022e8cd55e 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 @@ -1035,6 +1035,32 @@ public class MergerTest extends RepositoryTestCase { } } + /** + * 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 f03163d491..69d90aae90 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 @@ public class NameConflictTreeWalkTest extends RepositoryTestCase { } } + /** + * 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 2fd945b03f..ffb41379bd 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 @@ import org.eclipse.jgit.lib.Repository; 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 @@ public class NameConflictTreeWalk extends TreeWalk { 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 @@ public class NameConflictTreeWalk extends TreeWalk { // 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 -- 2.39.5