AddCommand: Use NameConflictTreeWalk to identify file-dir changes

Adding a path that already exists but is changing type such as
from symlink to subdirectory requires a NameConflictTreeWalk to
match up the two different entry types that share the same name.

NameConflictTreeWalk needs a bug fix to pop conflicting entries
when PathFilterGroup aborts the walk early so that it does not
allow DirCacheBuilderIterator to copy conflicting entries into
the output cache.

Change-Id: I61b49cbe949ca8b4b98f9eb6dbe7b1f82eabb724

6 files changed, 95 insertions, 9 deletions

diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/api/AddCommand.java b/org.eclipse.jgit/src/org/eclipse/jgit/api/AddCommand.java
index 8a2c08c805..3b94f16f1a 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/api/AddCommand.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/api/AddCommand.java
@@ -45,6 +45,7 @@ package org.eclipse.jgit.api;
 
 import static org.eclipse.jgit.lib.Constants.OBJ_BLOB;
 import static org.eclipse.jgit.lib.FileMode.GITLINK;
+import static org.eclipse.jgit.lib.FileMode.TYPE_TREE;
 
 import java.io.IOException;
 import java.io.InputStream;
@@ -66,7 +67,7 @@ import org.eclipse.jgit.lib.ObjectId;
 import org.eclipse.jgit.lib.ObjectInserter;
 import org.eclipse.jgit.lib.Repository;
 import org.eclipse.jgit.treewalk.FileTreeIterator;
-import org.eclipse.jgit.treewalk.TreeWalk;
+import org.eclipse.jgit.treewalk.NameConflictTreeWalk;
 import org.eclipse.jgit.treewalk.TreeWalk.OperationType;
 import org.eclipse.jgit.treewalk.WorkingTreeIterator;
 import org.eclipse.jgit.treewalk.filter.PathFilterGroup;
@@ -141,7 +142,7 @@ public class AddCommand extends GitCommand<DirCache> {
 		boolean addAll = filepatterns.contains("."); //$NON-NLS-1$
 
 		try (ObjectInserter inserter = repo.newObjectInserter();
-				final TreeWalk tw = new TreeWalk(repo)) {
+				NameConflictTreeWalk tw = new NameConflictTreeWalk(repo)) {
 			tw.setOperationType(OperationType.CHECKIN_OP);
 			dc = repo.lockDirCache();
 
@@ -151,7 +152,6 @@ public class AddCommand extends GitCommand<DirCache> {
 				workingTreeIterator = new FileTreeIterator(repo);
 			workingTreeIterator.setDirCacheIterator(tw, 0);
 			tw.addTree(workingTreeIterator);
-			tw.setRecursive(true);
 			if (!addAll)
 				tw.setFilter(PathFilterGroup.createFromStrings(filepatterns));
 
@@ -180,9 +180,14 @@ public class AddCommand extends GitCommand<DirCache> {
 					continue;
 				}
 
+				if (tw.isSubtree() && !tw.isDirectoryFileConflict()) {
+					tw.enterSubtree();
+					continue;
+				}
+
 				if (f == null) { // working tree file does not exist
-					if (c != null
-							&& (!update || GITLINK == c.getEntryFileMode())) {
+					if (entry != null
+							&& (!update || GITLINK == entry.getFileMode())) {
 						builder.add(entry);
 					}
 					continue;
@@ -196,6 +201,14 @@ public class AddCommand extends GitCommand<DirCache> {
 					continue;
 				}
 
+				if (f.getEntryRawMode() == TYPE_TREE) {
+					// Index entry exists and is symlink, gitlink or file,
+					// otherwise the tree would have been entered above.
+					// Replace the index entry by diving into tree of files.
+					tw.enterSubtree();
+					continue;
+				}
+
 				byte[] path = tw.getRawPath();
 				if (entry == null || entry.getStage() > 0) {
 					entry = new DirCacheEntry(path);
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/dircache/DirCacheBuildIterator.java b/org.eclipse.jgit/src/org/eclipse/jgit/dircache/DirCacheBuildIterator.java
index da55306665..c10e416082 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/dircache/DirCacheBuildIterator.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/dircache/DirCacheBuildIterator.java
@@ -130,4 +130,9 @@ public class DirCacheBuildIterator extends DirCacheIterator {
 		if (cur < cnt)
 			builder.keep(cur, cnt - cur);
 	}
+
+	@Override
+	protected boolean needsStopWalk() {
+		return ptr < cache.getEntryCount();
+	}
 }
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/treewalk/AbstractTreeIterator.java b/org.eclipse.jgit/src/org/eclipse/jgit/treewalk/AbstractTreeIterator.java
index 5e71889574..27d0f7b58c 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/treewalk/AbstractTreeIterator.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/treewalk/AbstractTreeIterator.java
@@ -692,6 +692,14 @@ public abstract class AbstractTreeIterator {
 	}
 
 	/**
+	 * @return true if the iterator implements {@link #stopWalk()}.
+	 * @since 4.2
+	 */
+	protected boolean needsStopWalk() {
+		return false;
+	}
+
+	/**
 	 * @return the length of the name component of the path for the current entry
 	 */
 	public int getNameLength() {
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/treewalk/EmptyTreeIterator.java b/org.eclipse.jgit/src/org/eclipse/jgit/treewalk/EmptyTreeIterator.java
index 8dbf80e6a8..ec4a84eff3 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/treewalk/EmptyTreeIterator.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/treewalk/EmptyTreeIterator.java
@@ -142,4 +142,9 @@ public class EmptyTreeIterator extends AbstractTreeIterator {
 		if (parent != null)
 			parent.stopWalk();
 	}
+
+	@Override
+	protected boolean needsStopWalk() {
+		return parent != null && parent.needsStopWalk();
+	}
 }
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 350f563964..d2195a874c 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/treewalk/NameConflictTreeWalk.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/treewalk/NameConflictTreeWalk.java
@@ -43,6 +43,8 @@
 
 package org.eclipse.jgit.treewalk;
 
+import java.io.IOException;
+
 import org.eclipse.jgit.dircache.DirCacheBuilder;
 import org.eclipse.jgit.errors.CorruptObjectException;
 import org.eclipse.jgit.lib.FileMode;
@@ -338,6 +340,41 @@ public class NameConflictTreeWalk extends TreeWalk {
 			dfConflict = null;
 	}
 
+	void stopWalk() throws IOException {
+		if (!needsStopWalk()) {
+			return;
+		}
+
+		// Name conflicts make aborting early difficult. Multiple paths may
+		// exist between the file and directory versions of a name. To ensure
+		// the directory version is skipped over (as it was previously visited
+		// during the file version step) requires popping up the stack and
+		// finishing out each subtree that the walker dove into. Siblings in
+		// parents do not need to be recursed into, bounding the cost.
+		for (;;) {
+			AbstractTreeIterator t = min();
+			if (t.eof()) {
+				if (depth > 0) {
+					exitSubtree();
+					popEntriesEqual();
+					continue;
+				}
+				return;
+			}
+			currentHead = t;
+			skipEntriesEqual();
+		}
+	}
+
+	private boolean needsStopWalk() {
+		for (AbstractTreeIterator t : trees) {
+			if (t.needsStopWalk()) {
+				return true;
+			}
+		}
+		return false;
+	}
+
 	/**
 	 * True if the current entry is covered by a directory/file conflict.
 	 *
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/treewalk/TreeWalk.java b/org.eclipse.jgit/src/org/eclipse/jgit/treewalk/TreeWalk.java
index 438549520e..83fada4f95 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/treewalk/TreeWalk.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/treewalk/TreeWalk.java
@@ -57,6 +57,7 @@ import org.eclipse.jgit.attributes.Attributes;
 import org.eclipse.jgit.attributes.AttributesNode;
 import org.eclipse.jgit.attributes.AttributesNodeProvider;
 import org.eclipse.jgit.attributes.AttributesProvider;
+import org.eclipse.jgit.dircache.DirCacheBuildIterator;
 import org.eclipse.jgit.dircache.DirCacheIterator;
 import org.eclipse.jgit.errors.CorruptObjectException;
 import org.eclipse.jgit.errors.IncorrectObjectTypeException;
@@ -256,7 +257,7 @@ public class TreeWalk implements AutoCloseable, AttributesProvider {
 
 	private boolean postOrderTraversal;
 
-	private int depth;
+	int depth;
 
 	private boolean advance;
 
@@ -665,13 +666,30 @@ public class TreeWalk implements AutoCloseable, AttributesProvider {
 				return true;
 			}
 		} catch (StopWalkException stop) {
-			for (final AbstractTreeIterator t : trees)
-				t.stopWalk();
+			stopWalk();
 			return false;
 		}
 	}
 
 	/**
+	 * Notify iterators the walk is aborting.
+	 * <p>
+	 * Primarily to notify {@link DirCacheBuildIterator} the walk is aborting so
+	 * that it can copy any remaining entries.
+	 *
+	 * @throws IOException
+	 *             if traversal of remaining entries throws an exception during
+	 *             object access. This should never occur as remaining trees
+	 *             should already be in memory, however the methods used to
+	 *             finish traversal are declared to throw IOException.
+	 */
+	void stopWalk() throws IOException {
+		for (AbstractTreeIterator t : trees) {
+			t.stopWalk();
+		}
+	}
+
+	/**
 	 * Obtain the tree iterator for the current entry.
 	 * <p>
 	 * Entering into (or exiting out of) a subtree causes the current tree
@@ -1065,7 +1083,7 @@ public class TreeWalk implements AutoCloseable, AttributesProvider {
 		}
 	}
 
-	private void exitSubtree() {
+	void exitSubtree() {
 		depth--;
 		for (int i = 0; i < trees.length; i++)
 			trees[i] = trees[i].parent;