Paths.pathCompare: Utility to sort paths from byte[]

Consolidate copies of this function into one location.

Add some unit tests to prevent bugs that were accidentally
introduced while trying to make this refactoring.

Change-Id: I82f64bbb8601ca2d8316ca57ae8119df32bb5c08

7 files changed, 137 insertions, 111 deletions

diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/dircache/BaseDirCacheEditor.java b/org.eclipse.jgit/src/org/eclipse/jgit/dircache/BaseDirCacheEditor.java
index fc789b3d17..0fbc1f8acf 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/dircache/BaseDirCacheEditor.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/dircache/BaseDirCacheEditor.java
@@ -44,8 +44,8 @@
 
 package org.eclipse.jgit.dircache;
 
-import static org.eclipse.jgit.lib.FileMode.TREE;
 import static org.eclipse.jgit.lib.FileMode.TYPE_TREE;
+import static org.eclipse.jgit.util.Paths.compareSameName;
 
 import java.io.IOException;
 
@@ -207,8 +207,8 @@ abstract class BaseDirCacheEditor {
 
 				int s = nextSlash(nPath, prefixLen);
 				int m = s < nPath.length ? TYPE_TREE : n.getRawMode();
-				int cmp = pathCompare(
-						ePath, prefixLen, ePath.length, TYPE_TREE,
+				int cmp = compareSameName(
+						ePath, prefixLen, ePath.length,
 						nPath, prefixLen, s, m);
 				if (cmp < 0) {
 					break;
@@ -252,28 +252,6 @@ abstract class BaseDirCacheEditor {
 		return true;
 	}
 
-	static int pathCompare(byte[] aPath, int aPos, int aEnd, int aMode,
-			byte[] bPath, int bPos, int bEnd, int bMode) {
-		while (aPos < aEnd && bPos < bEnd) {
-			int cmp = (aPath[aPos++] & 0xff) - (bPath[bPos++] & 0xff);
-			if (cmp != 0) {
-				return cmp;
-			}
-		}
-
-		if (aPos < aEnd) {
-			return (aPath[aPos] & 0xff) - lastPathChar(bMode);
-		}
-		if (bPos < bEnd) {
-			return lastPathChar(aMode) - (bPath[bPos] & 0xff);
-		}
-		return 0;
-	}
-
-	private static int lastPathChar(int mode) {
-		return TREE.equals(mode) ? '/' : '\0';
-	}
-
 	/**
 	 * Finish, write, commit this change, and release the index lock.
 	 * <p>
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/dircache/DirCacheEditor.java b/org.eclipse.jgit/src/org/eclipse/jgit/dircache/DirCacheEditor.java
index 889e194224..c987c964c4 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/dircache/DirCacheEditor.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/dircache/DirCacheEditor.java
@@ -57,6 +57,7 @@ import java.util.List;
 
 import org.eclipse.jgit.internal.JGitText;
 import org.eclipse.jgit.lib.Constants;
+import org.eclipse.jgit.util.Paths;
 
 /**
  * Updates a {@link DirCache} by supplying discrete edit commands.
@@ -215,7 +216,7 @@ public class DirCacheEditor extends BaseDirCacheEditor {
 		}
 
 		DirCacheEntry next = cache.getEntry(eIdx);
-		if (pathCompare(next.path, 0, next.path.length, 0,
+		if (Paths.compare(next.path, 0, next.path.length, 0,
 				entPath, 0, entLen, TYPE_TREE) < 0) {
 			// Next DirCacheEntry sorts before new entry as tree. Defer a
 			// DeleteTree command to delete any entries if they exist. This
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/lib/ObjectChecker.java b/org.eclipse.jgit/src/org/eclipse/jgit/lib/ObjectChecker.java
index 858a0385d0..0b5efd77d4 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/lib/ObjectChecker.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/lib/ObjectChecker.java
@@ -77,6 +77,8 @@ import static org.eclipse.jgit.lib.ObjectChecker.ErrorType.TREE_NOT_SORTED;
 import static org.eclipse.jgit.lib.ObjectChecker.ErrorType.UNKNOWN_TYPE;
 import static org.eclipse.jgit.lib.ObjectChecker.ErrorType.WIN32_BAD_NAME;
 import static org.eclipse.jgit.lib.ObjectChecker.ErrorType.ZERO_PADDED_FILEMODE;
+import static org.eclipse.jgit.util.Paths.compare;
+import static org.eclipse.jgit.util.Paths.compareSameName;
 import static org.eclipse.jgit.util.RawParseUtils.nextLF;
 import static org.eclipse.jgit.util.RawParseUtils.parseBase10;
 
@@ -541,25 +543,6 @@ public class ObjectChecker {
 		}
 	}
 
-	private static int lastPathChar(final int mode) {
-		return FileMode.TREE.equals(mode) ? '/' : '\0';
-	}
-
-	private static int pathCompare(final byte[] raw, int aPos, final int aEnd,
-			final int aMode, int bPos, final int bEnd, final int bMode) {
-		while (aPos < aEnd && bPos < bEnd) {
-			final int cmp = (raw[aPos++] & 0xff) - (raw[bPos++] & 0xff);
-			if (cmp != 0)
-				return cmp;
-		}
-
-		if (aPos < aEnd)
-			return (raw[aPos] & 0xff) - lastPathChar(bMode);
-		if (bPos < bEnd)
-			return lastPathChar(aMode) - (raw[bPos] & 0xff);
-		return 0;
-	}
-
 	private static boolean duplicateName(final byte[] raw,
 			final int thisNamePos, final int thisNameEnd) {
 		final int sz = raw.length;
@@ -587,8 +570,9 @@ public class ObjectChecker {
 			if (nextNamePos + 1 == nextPtr)
 				return false;
 
-			final int cmp = pathCompare(raw, thisNamePos, thisNameEnd,
-					FileMode.TREE.getBits(), nextNamePos, nextPtr - 1, nextMode);
+			int cmp = compareSameName(
+					raw, thisNamePos, thisNameEnd,
+					raw, nextNamePos, nextPtr - 1, nextMode);
 			if (cmp < 0)
 				return false;
 			else if (cmp == 0)
@@ -676,8 +660,9 @@ public class ObjectChecker {
 			}
 
 			if (lastNameB != 0) {
-				final int cmp = pathCompare(raw, lastNameB, lastNameE,
-						lastMode, thisNameB, ptr, thisMode);
+				int cmp = compare(
+						raw, lastNameB, lastNameE, lastMode,
+						raw, thisNameB, ptr, thisMode);
 				if (cmp > 0) {
 					report(TREE_NOT_SORTED, id,
 							JGitText.get().corruptObjectIncorrectSorting);
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/notes/NonNoteEntry.java b/org.eclipse.jgit/src/org/eclipse/jgit/notes/NonNoteEntry.java
index 6a2d44bca9..362328a963 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/notes/NonNoteEntry.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/notes/NonNoteEntry.java
@@ -47,6 +47,7 @@ import org.eclipse.jgit.lib.AnyObjectId;
 import org.eclipse.jgit.lib.FileMode;
 import org.eclipse.jgit.lib.ObjectId;
 import org.eclipse.jgit.lib.TreeFormatter;
+import org.eclipse.jgit.util.Paths;
 
 /** A tree entry found in a note branch that isn't a valid note. */
 class NonNoteEntry extends ObjectId {
@@ -74,27 +75,8 @@ class NonNoteEntry extends ObjectId {
 	}
 
 	int pathCompare(byte[] bBuf, int bPos, int bLen, FileMode bMode) {
-		return pathCompare(name, 0, name.length, mode, //
-				bBuf, bPos, bLen, bMode);
-	}
-
-	private static int pathCompare(final byte[] aBuf, int aPos, final int aEnd,
-			final FileMode aMode, final byte[] bBuf, int bPos, final int bEnd,
-			final FileMode bMode) {
-		while (aPos < aEnd && bPos < bEnd) {
-			int cmp = (aBuf[aPos++] & 0xff) - (bBuf[bPos++] & 0xff);
-			if (cmp != 0)
-				return cmp;
-		}
-
-		if (aPos < aEnd)
-			return (aBuf[aPos] & 0xff) - lastPathChar(bMode);
-		if (bPos < bEnd)
-			return lastPathChar(aMode) - (bBuf[bPos] & 0xff);
-		return 0;
-	}
-
-	private static int lastPathChar(final FileMode mode) {
-		return FileMode.TREE.equals(mode.getBits()) ? '/' : '\0';
+		return Paths.compare(
+				name, 0, name.length, mode.getBits(),
+				bBuf, bPos, bLen, bMode.getBits());
 	}
 }
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 27d0f7b58c..58136355eb 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/treewalk/AbstractTreeIterator.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/treewalk/AbstractTreeIterator.java
@@ -59,6 +59,7 @@ import org.eclipse.jgit.lib.MutableObjectId;
 import org.eclipse.jgit.lib.ObjectId;
 import org.eclipse.jgit.lib.ObjectReader;
 import org.eclipse.jgit.treewalk.filter.TreeFilter;
+import org.eclipse.jgit.util.Paths;
 
 /**
  * Walks a Git tree (directory) in Git sort order.
@@ -382,20 +383,9 @@ public abstract class AbstractTreeIterator {
 	}
 
 	private int pathCompare(byte[] b, int bPos, int bEnd, int bMode, int aPos) {
-		final byte[] a = path;
-		final int aEnd = pathLen;
-
-		for (; aPos < aEnd && bPos < bEnd; aPos++, bPos++) {
-			final int cmp = (a[aPos] & 0xff) - (b[bPos] & 0xff);
-			if (cmp != 0)
-				return cmp;
-		}
-
-		if (aPos < aEnd)
-			return (a[aPos] & 0xff) - lastPathChar(bMode);
-		if (bPos < bEnd)
-			return lastPathChar(mode) - (b[bPos] & 0xff);
-		return lastPathChar(mode) - lastPathChar(bMode);
+		return Paths.compare(
+				path, aPos, pathLen, mode,
+				b, bPos, bEnd, bMode);
 	}
 
 	private static int alreadyMatch(AbstractTreeIterator a,
@@ -412,10 +402,6 @@ public abstract class AbstractTreeIterator {
 		}
 	}
 
-	private static int lastPathChar(final int mode) {
-		return FileMode.TREE.equals(mode) ? '/' : '\0';
-	}
-
 	/**
 	 * Check if the current entry of both iterators has the same id.
 	 * <p>
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/treewalk/WorkingTreeIterator.java b/org.eclipse.jgit/src/org/eclipse/jgit/treewalk/WorkingTreeIterator.java
index 94beeeb56f..0d617ee7f9 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/treewalk/WorkingTreeIterator.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/treewalk/WorkingTreeIterator.java
@@ -89,6 +89,7 @@ import org.eclipse.jgit.submodule.SubmoduleWalk;
 import org.eclipse.jgit.util.FS;
 import org.eclipse.jgit.util.FS.ExecutionResult;
 import org.eclipse.jgit.util.IO;
+import org.eclipse.jgit.util.Paths;
 import org.eclipse.jgit.util.RawParseUtils;
 import org.eclipse.jgit.util.io.EolCanonicalizingInputStream;
 
@@ -692,31 +693,13 @@ public abstract class WorkingTreeIterator extends AbstractTreeIterator {
 	}
 
 	private static final Comparator<Entry> ENTRY_CMP = new Comparator<Entry>() {
-		public int compare(final Entry o1, final Entry o2) {
-			final byte[] a = o1.encodedName;
-			final byte[] b = o2.encodedName;
-			final int aLen = o1.encodedNameLen;
-			final int bLen = o2.encodedNameLen;
-			int cPos;
-
-			for (cPos = 0; cPos < aLen && cPos < bLen; cPos++) {
-				final int cmp = (a[cPos] & 0xff) - (b[cPos] & 0xff);
-				if (cmp != 0)
-					return cmp;
-			}
-
-			if (cPos < aLen)
-				return (a[cPos] & 0xff) - lastPathChar(o2);
-			if (cPos < bLen)
-				return lastPathChar(o1) - (b[cPos] & 0xff);
-			return lastPathChar(o1) - lastPathChar(o2);
+		public int compare(Entry a, Entry b) {
+			return Paths.compare(
+					a.encodedName, 0, a.encodedNameLen, a.getMode().getBits(),
+					b.encodedName, 0, b.encodedNameLen, b.getMode().getBits());
 		}
 	};
 
-	static int lastPathChar(final Entry e) {
-		return e.getMode() == FileMode.TREE ? '/' : '\0';
-	}
-
 	/**
 	 * Constructor helper.
 	 *
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/util/Paths.java b/org.eclipse.jgit/src/org/eclipse/jgit/util/Paths.java
index ce2cbc4d3d..6be7ddbe12 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/util/Paths.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/util/Paths.java
@@ -43,6 +43,9 @@
 
 package org.eclipse.jgit.util;
 
+import static org.eclipse.jgit.lib.FileMode.TYPE_MASK;
+import static org.eclipse.jgit.lib.FileMode.TYPE_TREE;
+
 /**
  * Utility functions for paths inside of a Git repository.
  *
@@ -72,6 +75,114 @@ public class Paths {
 		return path.substring(0, i);
 	}
 
+	/**
+	 * Compare two paths according to Git path sort ordering rules.
+	 *
+	 * @param aPath
+	 *            first path buffer. The range {@code [aPos, aEnd)} is used.
+	 * @param aPos
+	 *            index into {@code aPath} where the first path starts.
+	 * @param aEnd
+	 *            1 past last index of {@code aPath}.
+	 * @param aMode
+	 *            mode of the first file. Trees are sorted as though
+	 *            {@code aPath[aEnd] == '/'}, even if aEnd does not exist.
+	 * @param bPath
+	 *            second path buffer. The range {@code [bPos, bEnd)} is used.
+	 * @param bPos
+	 *            index into {@code bPath} where the second path starts.
+	 * @param bEnd
+	 *            1 past last index of {@code bPath}.
+	 * @param bMode
+	 *            mode of the second file. Trees are sorted as though
+	 *            {@code bPath[bEnd] == '/'}, even if bEnd does not exist.
+	 * @return &lt;0 if {@code aPath} sorts before {@code bPath};
+	 *         0 if the paths are the same;
+	 *         &gt;0 if {@code aPath} sorts after {@code bPath}.
+	 */
+	public static int compare(byte[] aPath, int aPos, int aEnd, int aMode,
+			byte[] bPath, int bPos, int bEnd, int bMode) {
+		int cmp = coreCompare(
+				aPath, aPos, aEnd, aMode,
+				bPath, bPos, bEnd, bMode);
+		if (cmp == 0) {
+			cmp = lastPathChar(aMode) - lastPathChar(bMode);
+		}
+		return cmp;
+	}
+
+	/**
+	 * Compare two paths, checking for identical name.
+	 * <p>
+	 * Unlike {@code compare} this method returns {@code 0} when the paths have
+	 * the same characters in their names, even if the mode differs. It is
+	 * intended for use in validation routines detecting duplicate entries.
+	 * <p>
+	 * Returns {@code 0} if the names are identical and a conflict exists
+	 * between {@code aPath} and {@code bPath}, as they share the same name.
+	 * <p>
+	 * Returns {@code <0} if all possibles occurrences of {@code aPath} sort
+	 * before {@code bPath} and no conflict can happen. In a properly sorted
+	 * tree there are no other occurrences of {@code aPath} and therefore there
+	 * are no duplicate names.
+	 * <p>
+	 * Returns {@code >0} when it is possible for a duplicate occurrence of
+	 * {@code aPath} to appear later, after {@code bPath}. Callers should
+	 * continue to examine candidates for {@code bPath} until the method returns
+	 * one of the other return values.
+	 *
+	 * @param aPath
+	 *            first path buffer. The range {@code [aPos, aEnd)} is used.
+	 * @param aPos
+	 *            index into {@code aPath} where the first path starts.
+	 * @param aEnd
+	 *            1 past last index of {@code aPath}.
+	 * @param bPath
+	 *            second path buffer. The range {@code [bPos, bEnd)} is used.
+	 * @param bPos
+	 *            index into {@code bPath} where the second path starts.
+	 * @param bEnd
+	 *            1 past last index of {@code bPath}.
+	 * @param bMode
+	 *            mode of the second file. Trees are sorted as though
+	 *            {@code bPath[bEnd] == '/'}, even if bEnd does not exist.
+	 * @return &lt;0 if no duplicate name could exist;
+	 *         0 if the paths have the same name;
+	 *         &gt;0 other {@code bPath} should still be checked by caller.
+	 */
+	public static int compareSameName(
+			byte[] aPath, int aPos, int aEnd,
+			byte[] bPath, int bPos, int bEnd, int bMode) {
+		return coreCompare(
+				aPath, aPos, aEnd, TYPE_TREE,
+				bPath, bPos, bEnd, bMode);
+	}
+
+	private static int coreCompare(
+			byte[] aPath, int aPos, int aEnd, int aMode,
+			byte[] bPath, int bPos, int bEnd, int bMode) {
+		while (aPos < aEnd && bPos < bEnd) {
+			int cmp = (aPath[aPos++] & 0xff) - (bPath[bPos++] & 0xff);
+			if (cmp != 0) {
+				return cmp;
+			}
+		}
+		if (aPos < aEnd) {
+			return (aPath[aPos] & 0xff) - lastPathChar(bMode);
+		}
+		if (bPos < bEnd) {
+			return lastPathChar(aMode) - (bPath[bPos] & 0xff);
+		}
+		return 0;
+	}
+
+	private static int lastPathChar(int mode) {
+		if ((mode & TYPE_MASK) == TYPE_TREE) {
+			return '/';
+		}
+		return 0;
+	}
+
 	private Paths() {
 	}
 }