NameConflictTreeWalk: respect git order on multi-tree iteration

The NameConflictTreeWalk class is used in 3-way merge for iterating over
entries in 3 different commits. The class provides information about a
current entry and a state of the entry in commits (e.g entry is file,
entry is directory, entry is missing). In rare cases, the tree walker
can mix information about entries with different name.

The problem appears, because git uses unusual sorting order for
files. Example (this is a simplified real-life example):
Commit 1:
* gradle.properties - file
* gradle - directory (with nested files)
*   gradle/file - file in gradle directory
Commit 2:
* gradle.properties - file
* no entry with the name gradle
Commit 3:
* gradle.properties - file
* gradle - file
Here the names are ordered like this:
"gradle" file <"gradle.properties" file < "gradle/file" file.

NameConflictTreeWalk iterator already have code for processing
git sorting order, however in the example above the code doesn't
work correctly. Before the fix, NameConflictTreeWalk returns:
#next()
"gradle - directory" | "gradle.properties" | "gradle - file" - which is
wrong. The expected result is
#next()
"gradle - directory | MISSED_FILE | "gradle - file"
#next()
"gradle.properties"|"gradle.properties"|"gradle.properties"

Ensure that the "matches" field of tree iterators (which contains the
current path) is kept in sync in the case above.

Change-Id: Ief5aa06d80b358f4080043c8694aa0fd7c60045b
Signed-off-by: Dmitrii Filippov <dmfilippov@google.com>

2 files changed, 90 insertions, 2 deletions

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 36a96b0e2d..f03163d491 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
@@ -138,6 +138,54 @@ public class NameConflictTreeWalkTest extends RepositoryTestCase {
 	}
 
 	@Test
+	public void testDF_specialFileNames() throws Exception {
+		final DirCache tree0 = db.readDirCache();
+		final DirCache tree1 = db.readDirCache();
+		final DirCache tree2 = db.readDirCache();
+		{
+			final DirCacheBuilder b0 = tree0.builder();
+			final DirCacheBuilder b1 = tree1.builder();
+			final DirCacheBuilder b2 = tree2.builder();
+
+			b0.add(createEntry("gradle.properties", REGULAR_FILE));
+			b0.add(createEntry("gradle/nested_file.txt", REGULAR_FILE));
+
+			b1.add(createEntry("gradle.properties", REGULAR_FILE));
+
+			b2.add(createEntry("gradle", REGULAR_FILE));
+			b2.add(createEntry("gradle.properties", REGULAR_FILE));
+
+			b0.finish();
+			b1.finish();
+			b2.finish();
+			assertEquals(2, tree0.getEntryCount());
+			assertEquals(1, tree1.getEntryCount());
+			assertEquals(2, tree2.getEntryCount());
+		}
+
+		try (NameConflictTreeWalk tw = new NameConflictTreeWalk(db)) {
+			tw.addTree(new DirCacheIterator(tree0));
+			tw.addTree(new DirCacheIterator(tree1));
+			tw.addTree(new DirCacheIterator(tree2));
+
+			assertModes("gradle", TREE, MISSING, REGULAR_FILE, tw);
+			assertTrue(tw.isSubtree());
+			assertTrue(tw.isDirectoryFileConflict());
+			tw.enterSubtree();
+			assertModes("gradle/nested_file.txt", REGULAR_FILE, MISSING,
+					MISSING, tw);
+			assertFalse(tw.isSubtree());
+			// isDirectoryFileConflict is true, because the conflict is detected
+			// on parent.
+			assertTrue(tw.isDirectoryFileConflict());
+			assertModes("gradle.properties", REGULAR_FILE, REGULAR_FILE,
+					REGULAR_FILE, tw);
+			assertFalse(tw.isSubtree());
+			assertFalse(tw.isDirectoryFileConflict());
+		}
+	}
+
+	@Test
 	public void testDF_SkipsSeenSubtree() throws Exception {
 		final DirCache tree0 = db.readDirCache();
 		final DirCache tree1 = db.readDirCache();
@@ -218,11 +266,29 @@ public class NameConflictTreeWalkTest extends RepositoryTestCase {
 		}
 	}
 
-	private static void assertModes(final String path, final FileMode mode0,
-			final FileMode mode1, final TreeWalk tw) throws Exception {
+	private static void assertModes(String path, FileMode mode0, FileMode mode1,
+			TreeWalk tw) throws Exception {
 		assertTrue("has " + path, tw.next());
 		assertEquals(path, tw.getPathString());
 		assertEquals(mode0, tw.getFileMode(0));
 		assertEquals(mode1, tw.getFileMode(1));
 	}
+
+	private static void assertModes(String path, FileMode mode0, FileMode mode1,
+			FileMode mode2, TreeWalk tw) throws Exception {
+		assertTrue("has " + path, tw.next());
+		assertEquals(path, tw.getPathString());
+		if (tw.getFileMode(0) != FileMode.MISSING) {
+			assertEquals(path, TreeWalk.pathOf(tw.trees[0]));
+		}
+		if (tw.getFileMode(1) != FileMode.MISSING) {
+			assertEquals(path, TreeWalk.pathOf(tw.trees[1]));
+		}
+		if (tw.getFileMode(2) != FileMode.MISSING) {
+			assertEquals(path, TreeWalk.pathOf(tw.trees[2]));
+		}
+		assertEquals(mode0, tw.getFileMode(0));
+		assertEquals(mode1, tw.getFileMode(1));
+		assertEquals(mode2, tw.getFileMode(2));
+	}
 }
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 28b7423817..3c8553c74f 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/treewalk/NameConflictTreeWalk.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/treewalk/NameConflictTreeWalk.java
@@ -268,6 +268,28 @@ public class NameConflictTreeWalk extends TreeWalk {
 			}
 		}
 
+		// When the combineDF is called, the t.matches field stores other
+		// entry (i.e. tree iterator) with an equal path. However, the
+		// previous loop moves each iterator independently. As a result,
+		// iterators which have had equals path at the start of the
+		// method can have different paths at this point.
+		// Reevaluate existing matches.
+		// The NameConflictTreeWalkTest.testDF_specialFileNames test
+		// cover this situation.
+		for (AbstractTreeIterator t : trees) {
+			// The previous loop doesn't touch tree iterator if it matches
+			// minRef. Skip it here
+			if (t.eof() || t.matches == null || t.matches == minRef)
+				continue;
+			// The t.pathCompare takes into account the entry type (file
+			// or directory) and returns non-zero value if names match
+			// but entry type don't match.
+			// We want to keep such matches (file/directory conflict),
+			// so reset matches only if names are not equal.
+			if (!nameEqual(t, t.matches))
+				t.matches = null;
+		}
+
 		if (treeMatch != null) {
 			// If we do have a conflict use one of the directory
 			// matching iterators instead of the file iterator.