[JGIT PATCH 00/14] TreeWalk D/F conflict detection

[JGIT PATCH 00/14] TreeWalk D/F conflict detection

[Shawn O. Pearce]

This series is about fixing the "mistake" in Git trees where
subtrees sort as through their name is "path/" and not "path".

Within a TreeWalk this is a problem because the tree contents:

    Tree 1     Tree 2
  ------------------------
    100644 a
               100644 a.c
               040000 a
    100644 b

needs to merge together both "a" paths from tree 1 and tree 2, but
these appear at different points in time when we merge-sort the two
trees together.

We use an infinite look-ahead and look-behind to identify these cases
and make the iteration look like this instead:

    Tree 1     Tree 2
  ------------------------
    100644 a   040000 a
               100644 a.c
    100644 b

which allows the application to handle the D/F conflict in a single
step, even though the contents of "a" may now be out-of-order within
the DirCache.  Fortunately DirCacheBuilder can automatically fix this
sort of ordering problem.


Shawn O. Pearce (14):
  Detect path names which overflow the name length field in the index
  Fix NB.decodeUInt16 to correctly handle the high byte
  Add test cases for NB.encode and NB.decode family of routines
  Fix DirCache's skip over null byte padding when reading a DIRC file
  Fix usage of assertEquals in DirCacheIteratorTest
  Refactor AbstractTreeIterator.pathCompare to force another mode
  Micro-optimize AbstractTreeIterator.pathCompare
  Optimize path comparsion within subtrees during TreeWalk
  Refactor AbstractTreeIterator semantics to start on first entry
  Make all AbstractTreeIterator implementations bi-directional
  Expose beginning of iterator indication from AbstractTreeIterator
  Allow application code to set ObjectIds in DirCacheEntry
  Create NameConflictTreeWalk to transparently detect D/F conflicts
  Add test case for NameConflictTreeWalk

 .../spearce/egit/core/ContainerTreeIterator.java   |    9 +-
 .../jgit/dircache/DirCacheBuilderIteratorTest.java |    2 +-
 .../jgit/dircache/DirCacheIteratorTest.java        |   28 +-
 .../jgit/treewalk/CanonicalTreeParserTest.java     |  261 ++++++++++++++++
 .../jgit/treewalk/NameConflictTreeWalkTest.java    |  205 ++++++++++++
 .../tst/org/spearce/jgit/util/NBTest.java          |  328 ++++++++++++++++++++
 .../src/org/spearce/jgit/dircache/DirCache.java    |    2 +-
 .../jgit/dircache/DirCacheBuildIterator.java       |    9 +-
 .../org/spearce/jgit/dircache/DirCacheEntry.java   |   41 +++-
 .../spearce/jgit/dircache/DirCacheIterator.java    |   84 +++--
 .../jgit/treewalk/AbstractTreeIterator.java        |  129 +++++---
 .../spearce/jgit/treewalk/CanonicalTreeParser.java |   94 +++++-
 .../spearce/jgit/treewalk/EmptyTreeIterator.java   |   12 +-
 .../spearce/jgit/treewalk/FileTreeIterator.java    |    5 +-
 .../jgit/treewalk/NameConflictTreeWalk.java        |  237 ++++++++++++++
 .../src/org/spearce/jgit/treewalk/TreeWalk.java    |   18 +-
 .../spearce/jgit/treewalk/WorkingTreeIterator.java |  132 ++++-----
 org.spearce.jgit/src/org/spearce/jgit/util/NB.java |   29 ++-
 18 files changed, 1418 insertions(+), 207 deletions(-)
 create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/treewalk/CanonicalTreeParserTest.java
 create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/treewalk/NameConflictTreeWalkTest.java
 create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/util/NBTest.java
 create mode 100644 org.spearce.jgit/src/org/spearce/jgit/treewalk/NameConflictTreeWalk.java

[JGIT PATCH 01/14] Detect path names which overflow the name length field in the index

[Shawn O. Pearce]

C Git allows a path name to be longer than 4095 bytes by storing 4095
into the path name length field within flags and then searching for a
null terminator at the end of the path name, instead of relying on the
length indicatior.  We cannot do this (easily) from an InputStream so
we are currently going to just abort with an exception if we find such
an extremely long path name.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../org/spearce/jgit/dircache/DirCacheEntry.java   |   13 ++++++++++---
 1 files changed, 10 insertions(+), 3 deletions(-)

diff --git a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheEntry.java b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheEntry.java
index c481e43..bcf5596 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheEntry.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheEntry.java
@@ -81,6 +81,9 @@
 
 	private static final int P_FLAGS = 60;
 
+	/** Mask applied to data in {@link #P_FLAGS} to get the name length. */
+	private static final int NAME_MASK = 0xfff;
+
 	static final int INFO_LEN = 62;
 
 	private static final int ASSUME_VALID = 0x80;
@@ -101,7 +104,9 @@ DirCacheEntry(final byte[] sharedInfo, final int infoAt,
 
 		NB.readFully(in, info, infoOffset, INFO_LEN);
 
-		int pathLen = NB.decodeUInt16(info, infoOffset + P_FLAGS) & 0xfff;
+		int pathLen = NB.decodeUInt16(info, infoOffset + P_FLAGS) & NAME_MASK;
+		if (pathLen == NAME_MASK)
+			throw new IOException("Path name too long for jgit");
 		path = new byte[pathLen];
 		NB.readFully(in, path, 0, pathLen);
 
@@ -135,6 +140,8 @@ public DirCacheEntry(final byte[] newPath) {
 		infoOffset = 0;
 
 		path = newPath;
+		if (path.length >= NAME_MASK)
+			throw new IllegalArgumentException("Path name too long for jgit");
 		NB.encodeInt16(info, infoOffset + P_FLAGS, path.length);
 	}
 
@@ -364,10 +371,10 @@ public String getPathString() {
 	 *            the entry to copy ObjectId and meta fields from.
 	 */
 	public void copyMetaData(final DirCacheEntry src) {
-		final int pLen = NB.decodeUInt16(info, infoOffset + P_FLAGS) & 0xfff;
+		final int pLen = NB.decodeUInt16(info, infoOffset + P_FLAGS) & NAME_MASK;
 		System.arraycopy(src.info, src.infoOffset, info, infoOffset, INFO_LEN);
 		NB.encodeInt16(info, infoOffset + P_FLAGS, pLen
-				| NB.decodeUInt16(info, infoOffset + P_FLAGS) & ~0xfff);
+				| NB.decodeUInt16(info, infoOffset + P_FLAGS) & ~NAME_MASK);
 	}
 
 	private long decodeTS(final int pIdx) {
-- 
1.6.0.87.g2858d

[JGIT PATCH 02/14] Fix NB.decodeUInt16 to correctly handle the high byte

[Shawn O. Pearce]

Our decodeUInt16 method was buggy and always cleared the high byte
of the pair.  This meant we always lost the upper 8 bits when we
read in a 16 bit unsigned integer, possibly causing us to misread
the data associated with that pair.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 org.spearce.jgit/src/org/spearce/jgit/util/NB.java |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/org.spearce.jgit/src/org/spearce/jgit/util/NB.java b/org.spearce.jgit/src/org/spearce/jgit/util/NB.java
index c6176f8..fa13354 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/util/NB.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/util/NB.java
@@ -102,7 +102,7 @@ public static int compareUInt32(final int a, final int b) {
 	 * @return unsigned integer value that matches the 16 bits read.
 	 */
 	public static int decodeUInt16(final byte[] intbuf, final int offset) {
-		int r = (intbuf[offset] << 8) & 0xff;
+		int r = (intbuf[offset] & 0xff) << 8;
 		return r | (intbuf[offset + 1] & 0xff);
 	}
 
-- 
1.6.0.87.g2858d

[JGIT PATCH 03/14] Add test cases for NB.encode and NB.decode family of routines

[Shawn O. Pearce]

We really need to ensure these methods work correctly, and since
we just suffered from a bug in NB.decodeUInt16 we now have a set
of test cases for the corner conditions of each encode and decode
method pair we support.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../tst/org/spearce/jgit/util/NBTest.java          |  328 ++++++++++++++++++++
 1 files changed, 328 insertions(+), 0 deletions(-)
 create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/util/NBTest.java

diff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/util/NBTest.java b/org.spearce.jgit.test/tst/org/spearce/jgit/util/NBTest.java
new file mode 100644
index 0000000..217db7f
--- /dev/null
+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/util/NBTest.java
@@ -0,0 +1,328 @@
+/*
+ * Copyright (C) 2008, Google Inc.
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above
+ *   copyright notice, this list of conditions and the following
+ *   disclaimer in the documentation and/or other materials provided
+ *   with the distribution.
+ *
+ * - Neither the name of the Git Development Community nor the
+ *   names of its contributors may be used to endorse or promote
+ *   products derived from this software without specific prior
+ *   written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
+ * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+package org.spearce.jgit.util;
+
+import junit.framework.TestCase;
+
+public class NBTest extends TestCase {
+	public void testCompareUInt32() {
+		assertTrue(NB.compareUInt32(0, 0) == 0);
+		assertTrue(NB.compareUInt32(1, 0) > 0);
+		assertTrue(NB.compareUInt32(0, 1) < 0);
+		assertTrue(NB.compareUInt32(-1, 0) > 0);
+		assertTrue(NB.compareUInt32(0, -1) < 0);
+		assertTrue(NB.compareUInt32(-1, 1) > 0);
+		assertTrue(NB.compareUInt32(1, -1) < 0);
+	}
+
+	public void testDecodeUInt16() {
+		assertEquals(0, NB.decodeUInt16(b(0, 0), 0));
+		assertEquals(0, NB.decodeUInt16(padb(3, 0, 0), 3));
+
+		assertEquals(3, NB.decodeUInt16(b(0, 3), 0));
+		assertEquals(3, NB.decodeUInt16(padb(3, 0, 3), 3));
+
+		assertEquals(0xde03, NB.decodeUInt16(b(0xde, 3), 0));
+		assertEquals(0xde03, NB.decodeUInt16(padb(3, 0xde, 3), 3));
+
+		assertEquals(0x03de, NB.decodeUInt16(b(3, 0xde), 0));
+		assertEquals(0x03de, NB.decodeUInt16(padb(3, 3, 0xde), 3));
+
+		assertEquals(0xffff, NB.decodeUInt16(b(0xff, 0xff), 0));
+		assertEquals(0xffff, NB.decodeUInt16(padb(3, 0xff, 0xff), 3));
+	}
+
+	public void testDecodeInt32() {
+		assertEquals(0, NB.decodeInt32(b(0, 0, 0, 0), 0));
+		assertEquals(0, NB.decodeInt32(padb(3, 0, 0, 0, 0), 3));
+
+		assertEquals(3, NB.decodeInt32(b(0, 0, 0, 3), 0));
+		assertEquals(3, NB.decodeInt32(padb(3, 0, 0, 0, 3), 3));
+
+		assertEquals(0xdeadbeef, NB.decodeInt32(b(0xde, 0xad, 0xbe, 0xef), 0));
+		assertEquals(0xdeadbeef, NB.decodeInt32(
+				padb(3, 0xde, 0xad, 0xbe, 0xef), 3));
+
+		assertEquals(0x0310adef, NB.decodeInt32(b(0x03, 0x10, 0xad, 0xef), 0));
+		assertEquals(0x0310adef, NB.decodeInt32(
+				padb(3, 0x03, 0x10, 0xad, 0xef), 3));
+
+		assertEquals(0xffffffff, NB.decodeInt32(b(0xff, 0xff, 0xff, 0xff), 0));
+		assertEquals(0xffffffff, NB.decodeInt32(
+				padb(3, 0xff, 0xff, 0xff, 0xff), 3));
+	}
+
+	public void testDecodeUInt32() {
+		assertEquals(0L, NB.decodeUInt32(b(0, 0, 0, 0), 0));
+		assertEquals(0L, NB.decodeUInt32(padb(3, 0, 0, 0, 0), 3));
+
+		assertEquals(3L, NB.decodeUInt32(b(0, 0, 0, 3), 0));
+		assertEquals(3L, NB.decodeUInt32(padb(3, 0, 0, 0, 3), 3));
+
+		assertEquals(0xdeadbeefL, NB.decodeUInt32(b(0xde, 0xad, 0xbe, 0xef), 0));
+		assertEquals(0xdeadbeefL, NB.decodeUInt32(padb(3, 0xde, 0xad, 0xbe,
+				0xef), 3));
+
+		assertEquals(0x0310adefL, NB.decodeUInt32(b(0x03, 0x10, 0xad, 0xef), 0));
+		assertEquals(0x0310adefL, NB.decodeUInt32(padb(3, 0x03, 0x10, 0xad,
+				0xef), 3));
+
+		assertEquals(0xffffffffL, NB.decodeUInt32(b(0xff, 0xff, 0xff, 0xff), 0));
+		assertEquals(0xffffffffL, NB.decodeUInt32(padb(3, 0xff, 0xff, 0xff,
+				0xff), 3));
+	}
+
+	public void testDecodeUInt64() {
+		assertEquals(0L, NB.decodeUInt64(b(0, 0, 0, 0, 0, 0, 0, 0), 0));
+		assertEquals(0L, NB.decodeUInt64(padb(3, 0, 0, 0, 0, 0, 0, 0, 0), 3));
+
+		assertEquals(3L, NB.decodeUInt64(b(0, 0, 0, 0, 0, 0, 0, 3), 0));
+		assertEquals(3L, NB.decodeUInt64(padb(3, 0, 0, 0, 0, 0, 0, 0, 3), 3));
+
+		assertEquals(0xdeadbeefL, NB.decodeUInt64(b(0, 0, 0, 0, 0xde, 0xad,
+				0xbe, 0xef), 0));
+		assertEquals(0xdeadbeefL, NB.decodeUInt64(padb(3, 0, 0, 0, 0, 0xde,
+				0xad, 0xbe, 0xef), 3));
+
+		assertEquals(0x0310adefL, NB.decodeUInt64(b(0, 0, 0, 0, 0x03, 0x10,
+				0xad, 0xef), 0));
+		assertEquals(0x0310adefL, NB.decodeUInt64(padb(3, 0, 0, 0, 0, 0x03,
+				0x10, 0xad, 0xef), 3));
+
+		assertEquals(0xc0ffee78deadbeefL, NB.decodeUInt64(b(0xc0, 0xff, 0xee,
+				0x78, 0xde, 0xad, 0xbe, 0xef), 0));
+		assertEquals(0xc0ffee78deadbeefL, NB.decodeUInt64(padb(3, 0xc0, 0xff,
+				0xee, 0x78, 0xde, 0xad, 0xbe, 0xef), 3));
+
+		assertEquals(0x00000000ffffffffL, NB.decodeUInt64(b(0, 0, 0, 0, 0xff,
+				0xff, 0xff, 0xff), 0));
+		assertEquals(0x00000000ffffffffL, NB.decodeUInt64(padb(3, 0, 0, 0, 0,
+				0xff, 0xff, 0xff, 0xff), 3));
+		assertEquals(0xffffffffffffffffL, NB.decodeUInt64(b(0xff, 0xff, 0xff,
+				0xff, 0xff, 0xff, 0xff, 0xff), 0));
+		assertEquals(0xffffffffffffffffL, NB.decodeUInt64(padb(3, 0xff, 0xff,
+				0xff, 0xff, 0xff, 0xff, 0xff, 0xff), 3));
+	}
+
+	public void testEncodeInt16() {
+		final byte[] out = new byte[16];
+
+		prepareOutput(out);
+		NB.encodeInt16(out, 0, 0);
+		assertOutput(b(0, 0), out, 0);
+
+		prepareOutput(out);
+		NB.encodeInt16(out, 3, 0);
+		assertOutput(b(0, 0), out, 3);
+
+		prepareOutput(out);
+		NB.encodeInt16(out, 0, 3);
+		assertOutput(b(0, 3), out, 0);
+
+		prepareOutput(out);
+		NB.encodeInt16(out, 3, 3);
+		assertOutput(b(0, 3), out, 3);
+
+		prepareOutput(out);
+		NB.encodeInt16(out, 0, 0xdeac);
+		assertOutput(b(0xde, 0xac), out, 0);
+
+		prepareOutput(out);
+		NB.encodeInt16(out, 3, 0xdeac);
+		assertOutput(b(0xde, 0xac), out, 3);
+
+		prepareOutput(out);
+		NB.encodeInt16(out, 3, -1);
+		assertOutput(b(0xff, 0xff), out, 3);
+	}
+
+	public void testEncodeInt32() {
+		final byte[] out = new byte[16];
+
+		prepareOutput(out);
+		NB.encodeInt32(out, 0, 0);
+		assertOutput(b(0, 0, 0, 0), out, 0);
+
+		prepareOutput(out);
+		NB.encodeInt32(out, 3, 0);
+		assertOutput(b(0, 0, 0, 0), out, 3);
+
+		prepareOutput(out);
+		NB.encodeInt32(out, 0, 3);
+		assertOutput(b(0, 0, 0, 3), out, 0);
+
+		prepareOutput(out);
+		NB.encodeInt32(out, 3, 3);
+		assertOutput(b(0, 0, 0, 3), out, 3);
+
+		prepareOutput(out);
+		NB.encodeInt32(out, 0, 0xdeac);
+		assertOutput(b(0, 0, 0xde, 0xac), out, 0);
+
+		prepareOutput(out);
+		NB.encodeInt32(out, 3, 0xdeac);
+		assertOutput(b(0, 0, 0xde, 0xac), out, 3);
+
+		prepareOutput(out);
+		NB.encodeInt32(out, 0, 0xdeac9853);
+		assertOutput(b(0xde, 0xac, 0x98, 0x53), out, 0);
+
+		prepareOutput(out);
+		NB.encodeInt32(out, 3, 0xdeac9853);
+		assertOutput(b(0xde, 0xac, 0x98, 0x53), out, 3);
+
+		prepareOutput(out);
+		NB.encodeInt32(out, 3, -1);
+		assertOutput(b(0xff, 0xff, 0xff, 0xff), out, 3);
+	}
+
+	public void testEncodeInt64() {
+		final byte[] out = new byte[16];
+
+		prepareOutput(out);
+		NB.encodeInt64(out, 0, 0L);
+		assertOutput(b(0, 0, 0, 0, 0, 0, 0, 0), out, 0);
+
+		prepareOutput(out);
+		NB.encodeInt64(out, 3, 0L);
+		assertOutput(b(0, 0, 0, 0, 0, 0, 0, 0), out, 3);
+
+		prepareOutput(out);
+		NB.encodeInt64(out, 0, 3L);
+		assertOutput(b(0, 0, 0, 0, 0, 0, 0, 3), out, 0);
+
+		prepareOutput(out);
+		NB.encodeInt64(out, 3, 3L);
+		assertOutput(b(0, 0, 0, 0, 0, 0, 0, 3), out, 3);
+
+		prepareOutput(out);
+		NB.encodeInt64(out, 0, 0xdeacL);
+		assertOutput(b(0, 0, 0, 0, 0, 0, 0xde, 0xac), out, 0);
+
+		prepareOutput(out);
+		NB.encodeInt64(out, 3, 0xdeacL);
+		assertOutput(b(0, 0, 0, 0, 0, 0, 0xde, 0xac), out, 3);
+
+		prepareOutput(out);
+		NB.encodeInt64(out, 0, 0xdeac9853L);
+		assertOutput(b(0, 0, 0, 0, 0xde, 0xac, 0x98, 0x53), out, 0);
+
+		prepareOutput(out);
+		NB.encodeInt64(out, 3, 0xdeac9853L);
+		assertOutput(b(0, 0, 0, 0, 0xde, 0xac, 0x98, 0x53), out, 3);
+
+		prepareOutput(out);
+		NB.encodeInt64(out, 0, 0xac431242deac9853L);
+		assertOutput(b(0xac, 0x43, 0x12, 0x42, 0xde, 0xac, 0x98, 0x53), out, 0);
+
+		prepareOutput(out);
+		NB.encodeInt64(out, 3, 0xac431242deac9853L);
+		assertOutput(b(0xac, 0x43, 0x12, 0x42, 0xde, 0xac, 0x98, 0x53), out, 3);
+
+		prepareOutput(out);
+		NB.encodeInt64(out, 3, -1L);
+		assertOutput(b(0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff), out, 3);
+	}
+
+	private static void prepareOutput(final byte[] buf) {
+		for (int i = 0; i < buf.length; i++)
+			buf[i] = (byte) (0x77 + i);
+	}
+
+	private static void assertOutput(final byte[] expect, final byte[] buf,
+			final int offset) {
+		for (int i = 0; i < offset; i++)
+			assertEquals((byte) (0x77 + i), buf[i]);
+		for (int i = 0; i < expect.length; i++)
+			assertEquals(expect[i], buf[offset + i]);
+		for (int i = offset + expect.length; i < buf.length; i++)
+			assertEquals((byte) (0x77 + i), buf[i]);
+	}
+
+	private static byte[] b(final int a, final int b) {
+		return new byte[] { (byte) a, (byte) b };
+	}
+
+	private static byte[] padb(final int len, final int a, final int b) {
+		final byte[] r = new byte[len + 2];
+		for (int i = 0; i < len; i++)
+			r[i] = (byte) 0xaf;
+		r[len] = (byte) a;
+		r[len + 1] = (byte) b;
+		return r;
+	}
+
+	private static byte[] b(final int a, final int b, final int c, final int d) {
+		return new byte[] { (byte) a, (byte) b, (byte) c, (byte) d };
+	}
+
+	private static byte[] padb(final int len, final int a, final int b,
+			final int c, final int d) {
+		final byte[] r = new byte[len + 4];
+		for (int i = 0; i < len; i++)
+			r[i] = (byte) 0xaf;
+		r[len] = (byte) a;
+		r[len + 1] = (byte) b;
+		r[len + 2] = (byte) c;
+		r[len + 3] = (byte) d;
+		return r;
+	}
+
+	private static byte[] b(final int a, final int b, final int c, final int d,
+			final int e, final int f, final int g, final int h) {
+		return new byte[] { (byte) a, (byte) b, (byte) c, (byte) d, (byte) e,
+				(byte) f, (byte) g, (byte) h };
+	}
+
+	private static byte[] padb(final int len, final int a, final int b,
+			final int c, final int d, final int e, final int f, final int g,
+			final int h) {
+		final byte[] r = new byte[len + 8];
+		for (int i = 0; i < len; i++)
+			r[i] = (byte) 0xaf;
+		r[len] = (byte) a;
+		r[len + 1] = (byte) b;
+		r[len + 2] = (byte) c;
+		r[len + 3] = (byte) d;
+		r[len + 4] = (byte) e;
+		r[len + 5] = (byte) f;
+		r[len + 6] = (byte) g;
+		r[len + 7] = (byte) h;
+		return r;
+	}
+}
-- 
1.6.0.87.g2858d

[JGIT PATCH 04/14] Fix DirCache's skip over null byte padding when reading a DIRC file

[Shawn O. Pearce]

Sometimes we hit EOFException while reading from a 'DIRC' file with
the new DirCache API.  This was caused by BufferedInputStream.skip
skipping only part of the range we asked it to skip if the range we
asked it to skip spanned over the end of the current buffer block.
Two skip requests are necessary in this case: one to force the stream
to skip to the end of the buffer, and another to skip over data in
the source stream before reading the next buffer block into memory.

NB.skipFully handles this by abstracting the necessary loop into
a utility function, much like NB.readFully handles the necessary
read loop to ensure we read a full block of data.

DirCacheEntry and DirCache both need to use this routine to skip
over the parts of the DIRC file they do not wish to read.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../src/org/spearce/jgit/dircache/DirCache.java    |    2 +-
 .../org/spearce/jgit/dircache/DirCacheEntry.java   |    2 +-
 org.spearce.jgit/src/org/spearce/jgit/util/NB.java |   27 ++++++++++++++++++++
 3 files changed, 29 insertions(+), 2 deletions(-)

diff --git a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCache.java b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCache.java
index 995942c..76657c4 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCache.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCache.java
@@ -370,7 +370,7 @@ private void readFrom(final FileInputStream inStream) throws IOException,
 					// a performance optimization. Since we do not
 					// understand it, we can safely skip past it.
 					//
-					in.skip(NB.decodeInt32(hdr, 4));
+					NB.skipFully(in, NB.decodeUInt32(hdr, 4));
 				} else {
 					// The extension is not an optimization and is
 					// _required_ to understand this index format.
diff --git a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheEntry.java b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheEntry.java
index bcf5596..011bc16 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheEntry.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheEntry.java
@@ -116,7 +116,7 @@ DirCacheEntry(final byte[] sharedInfo, final int infoAt,
 		final int actLen = INFO_LEN + pathLen;
 		final int expLen = (actLen + 8) & ~7;
 		if (actLen != expLen)
-			in.skip(expLen - actLen);
+			NB.skipFully(in, expLen - actLen);
 	}
 
 	/**
diff --git a/org.spearce.jgit/src/org/spearce/jgit/util/NB.java b/org.spearce.jgit/src/org/spearce/jgit/util/NB.java
index fa13354..759caf5 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/util/NB.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/util/NB.java
@@ -71,6 +71,33 @@ public static void readFully(final InputStream fd, final byte[] dst,
 	}
 
 	/**
+	 * Skip an entire region of an input stream.
+	 * <p>
+	 * The input stream's position is moved forward by the number of requested
+	 * bytes, discarding them from the input. This method does not return until
+	 * the exact number of bytes requested has been skipped.
+	 * 
+	 * @param fd
+	 *            the stream to skip bytes from.
+	 * @param toSkip
+	 *            total number of bytes to be discarded. Must be >= 0.
+	 * @throws EOFException
+	 *             the stream ended before the requested number of bytes were
+	 *             skipped.
+	 * @throws IOException
+	 *             there was an error reading from the stream.
+	 */
+	public static void skipFully(final InputStream fd, long toSkip)
+			throws IOException {
+		while (toSkip > 0) {
+			final long r = fd.skip(toSkip);
+			if (r <= 0)
+				throw new EOFException("Short skip of block");
+			toSkip -= r;
+		}
+	}
+
+	/**
 	 * Compare a 32 bit unsigned integer stored in a 32 bit signed integer.
 	 * <p>
 	 * This function performs an unsigned compare operation, even though Java
-- 
1.6.0.87.g2858d

[JGIT PATCH 05/14] Fix usage of assertEquals in DirCacheIteratorTest

[Shawn O. Pearce]

I had the expected/actual values reversed so error messages from
JUnit were a bit difficult to read.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../jgit/dircache/DirCacheIteratorTest.java        |   10 +++++-----
 1 files changed, 5 insertions(+), 5 deletions(-)

diff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/dircache/DirCacheIteratorTest.java b/org.spearce.jgit.test/tst/org/spearce/jgit/dircache/DirCacheIteratorTest.java
index 7d4e6bb..62a162f 100644
--- a/org.spearce.jgit.test/tst/org/spearce/jgit/dircache/DirCacheIteratorTest.java
+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/dircache/DirCacheIteratorTest.java
@@ -87,7 +87,7 @@ public void testNoSubtree_NoTreeWalk() throws Exception {
 			assertSame(ents[pathIdx], i.getDirCacheEntry());
 			pathIdx++;
 		}
-		assertEquals(pathIdx, paths.length);
+		assertEquals(paths.length, pathIdx);
 	}
 
 	public void testNoSubtree_WithTreeWalk() throws Exception {
@@ -120,7 +120,7 @@ public void testNoSubtree_WithTreeWalk() throws Exception {
 			assertSame(modes[pathIdx], tw.getFileMode(0));
 			pathIdx++;
 		}
-		assertEquals(pathIdx, paths.length);
+		assertEquals(paths.length, pathIdx);
 	}
 
 	public void testSingleSubtree_NoRecursion() throws Exception {
@@ -164,7 +164,7 @@ public void testSingleSubtree_NoRecursion() throws Exception {
 
 			pathIdx++;
 		}
-		assertEquals(pathIdx, expPaths.length);
+		assertEquals(expPaths.length, pathIdx);
 	}
 
 	public void testSingleSubtree_Recursive() throws Exception {
@@ -199,7 +199,7 @@ public void testSingleSubtree_Recursive() throws Exception {
 			assertSame(mode, tw.getFileMode(0));
 			pathIdx++;
 		}
-		assertEquals(pathIdx, paths.length);
+		assertEquals(paths.length, pathIdx);
 	}
 
 	public void testTwoLevelSubtree_Recursive() throws Exception {
@@ -233,7 +233,7 @@ public void testTwoLevelSubtree_Recursive() throws Exception {
 			assertSame(mode, tw.getFileMode(0));
 			pathIdx++;
 		}
-		assertEquals(pathIdx, paths.length);
+		assertEquals(paths.length, pathIdx);
 	}
 
 	public void testTwoLevelSubtree_FilterPath() throws Exception {
-- 
1.6.0.87.g2858d

[JGIT PATCH 06/14] Refactor AbstractTreeIterator.pathCompare to force another mode

[Shawn O. Pearce]

When handling D/F (directory/file) conflicts we need to pretend that one
of the two iterators has the other "type" of mode so we can search for
possible matches.  Rather than editing the mode instance member we now
overload pathCompare to accept the 2nd iterator's mode as an argument.

We can now force a tree entry to compare as a normal file by passing
in a mode of 0, or we can force a file entry to compare as a tree by
passing in FileMode.TREE.getBits().

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../jgit/treewalk/AbstractTreeIterator.java        |   14 +++++++++-----
 1 files changed, 9 insertions(+), 5 deletions(-)

diff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java
index 232204a..bd75d2d 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java
@@ -227,6 +227,10 @@ protected void growPath(final int len) {
 	 *         p's entry sorts first.
 	 */
 	public int pathCompare(final AbstractTreeIterator p) {
+		return pathCompare(p, p.mode);
+	}
+
+	int pathCompare(final AbstractTreeIterator p, final int pMode) {
 		final byte[] a = path;
 		final byte[] b = p.path;
 		final int aLen = pathLen;
@@ -241,7 +245,7 @@ public int pathCompare(final AbstractTreeIterator p) {
 
 		if (cPos < aLen) {
 			final int aj = a[cPos] & 0xff;
-			final int lastb = p.lastPathChar();
+			final int lastb = lastPathChar(pMode);
 			if (aj < lastb)
 				return -1;
 			else if (aj > lastb)
@@ -254,7 +258,7 @@ else if (cPos == aLen - 1)
 
 		if (cPos < bLen) {
 			final int bk = b[cPos] & 0xff;
-			final int lasta = lastPathChar();
+			final int lasta = lastPathChar(mode);
 			if (lasta < bk)
 				return -1;
 			else if (lasta > bk)
@@ -265,8 +269,8 @@ else if (cPos == bLen - 1)
 				return 1;
 		}
 
-		final int lasta = lastPathChar();
-		final int lastb = p.lastPathChar();
+		final int lasta = lastPathChar(mode);
+		final int lastb = lastPathChar(pMode);
 		if (lasta < lastb)
 			return -1;
 		else if (lasta > lastb)
@@ -280,7 +284,7 @@ else if (aLen < bLen)
 			return 1;
 	}
 
-	private int lastPathChar() {
+	private static int lastPathChar(final int mode) {
 		return FileMode.TREE.equals(mode) ? '/' : '\0';
 	}
 
-- 
1.6.0.87.g2858d

[JGIT PATCH 07/14] Micro-optimize AbstractTreeIterator.pathCompare

[Shawn O. Pearce]

We were doing far too much work in pathCompare to handle
cases that just cannot ever happen, such as if the paths
were the same length but had different "last path char"
and then somehow had different lengths.

We also had the JVM doing a lot of comparsion ops just
to return -1/0/1 when really we can get away with the
non-zero result returned to the caller.  Issuing just
the subtraction and one comparsion to 0 is much quicker,
JIT or not.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../jgit/treewalk/AbstractTreeIterator.java        |   44 ++-----------------
 1 files changed, 5 insertions(+), 39 deletions(-)

diff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java
index bd75d2d..31257b5 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java
@@ -243,45 +243,11 @@ int pathCompare(final AbstractTreeIterator p, final int pMode) {
 				return cmp;
 		}
 
-		if (cPos < aLen) {
-			final int aj = a[cPos] & 0xff;
-			final int lastb = lastPathChar(pMode);
-			if (aj < lastb)
-				return -1;
-			else if (aj > lastb)
-				return 1;
-			else if (cPos == aLen - 1)
-				return 0;
-			else
-				return -1;
-		}
-
-		if (cPos < bLen) {
-			final int bk = b[cPos] & 0xff;
-			final int lasta = lastPathChar(mode);
-			if (lasta < bk)
-				return -1;
-			else if (lasta > bk)
-				return 1;
-			else if (cPos == bLen - 1)
-				return 0;
-			else
-				return 1;
-		}
-
-		final int lasta = lastPathChar(mode);
-		final int lastb = lastPathChar(pMode);
-		if (lasta < lastb)
-			return -1;
-		else if (lasta > lastb)
-			return 1;
-
-		if (aLen == bLen)
-			return 0;
-		else if (aLen < bLen)
-			return -1;
-		else
-			return 1;
+		if (cPos < aLen)
+			return (a[cPos] & 0xff) - lastPathChar(pMode);
+		if (cPos < bLen)
+			return lastPathChar(mode) - (b[cPos] & 0xff);
+		return lastPathChar(mode) - lastPathChar(pMode);
 	}
 
 	private static int lastPathChar(final int mode) {
-- 
1.6.0.87.g2858d

[JGIT PATCH 08/14] Optimize path comparsion within subtrees during TreeWalk

[Shawn O. Pearce]

If we are comparing two entries whose parents both match the same
tree iterator we know the path up through pathOffset must all
be identical, as the parents can only match if their paths up to
pathOffset were equal and they were both trees.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../jgit/treewalk/AbstractTreeIterator.java        |   22 +++++++++++++++++++-
 1 files changed, 21 insertions(+), 1 deletions(-)

diff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java
index 31257b5..e6aa338 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java
@@ -237,7 +237,13 @@ int pathCompare(final AbstractTreeIterator p, final int pMode) {
 		final int bLen = p.pathLen;
 		int cPos;
 
-		for (cPos = 0; cPos < aLen && cPos < bLen; cPos++) {
+		// Its common when we are a subtree for both parents to match;
+		// when this happens everything in path[0..cPos] is known to
+		// be equal and does not require evaluation again.
+		//
+		cPos = alreadyMatch(this, p);
+
+		for (; cPos < aLen && cPos < bLen; cPos++) {
 			final int cmp = (a[cPos] & 0xff) - (b[cPos] & 0xff);
 			if (cmp != 0)
 				return cmp;
@@ -250,6 +256,20 @@ int pathCompare(final AbstractTreeIterator p, final int pMode) {
 		return lastPathChar(mode) - lastPathChar(pMode);
 	}
 
+	private static int alreadyMatch(AbstractTreeIterator a,
+			AbstractTreeIterator b) {
+		for (;;) {
+			final AbstractTreeIterator ap = a.parent;
+			final AbstractTreeIterator bp = b.parent;
+			if (ap == null || bp == null)
+				return 0;
+			if (ap.matches == bp.matches)
+				return a.pathOffset;
+			a = ap;
+			b = bp;
+		}
+	}
+
 	private static int lastPathChar(final int mode) {
 		return FileMode.TREE.equals(mode) ? '/' : '\0';
 	}
-- 
1.6.0.87.g2858d

[JGIT PATCH 09/14] Refactor AbstractTreeIterator semantics to start on first entry

[Shawn O. Pearce]

The AbstractTreeIterator implementations now start on their first
entry at construction time, instead of relying on TreeWalk to do
an initial "next()" invocation.  This cleans up some of the code
and makes the iterators more consistent with each other.

In all implementations the refactoring splits out the advance
portion of next() from the entry parsing portion.  This change
(along with the position semantic change) will permit us to do
reverse iteration in the future, making the iterators all able
to be bi-directional.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../spearce/egit/core/ContainerTreeIterator.java   |    9 +-
 .../jgit/dircache/DirCacheBuilderIteratorTest.java |    2 +-
 .../jgit/dircache/DirCacheIteratorTest.java        |   18 +--
 .../jgit/dircache/DirCacheBuildIterator.java       |    7 +-
 .../spearce/jgit/dircache/DirCacheIterator.java    |   63 +++++------
 .../jgit/treewalk/AbstractTreeIterator.java        |    5 +-
 .../spearce/jgit/treewalk/CanonicalTreeParser.java |   27 +++--
 .../spearce/jgit/treewalk/FileTreeIterator.java    |    5 +-
 .../src/org/spearce/jgit/treewalk/TreeWalk.java    |    4 -
 .../spearce/jgit/treewalk/WorkingTreeIterator.java |  119 ++++++++------------
 10 files changed, 112 insertions(+), 147 deletions(-)

diff --git a/org.spearce.egit.core/src/org/spearce/egit/core/ContainerTreeIterator.java b/org.spearce.egit.core/src/org/spearce/egit/core/ContainerTreeIterator.java
index c4af788..2b7ff3b 100644
--- a/org.spearce.egit.core/src/org/spearce/egit/core/ContainerTreeIterator.java
+++ b/org.spearce.egit.core/src/org/spearce/egit/core/ContainerTreeIterator.java
@@ -67,12 +67,14 @@ private static String computePrefix(final IContainer base) {
 	public ContainerTreeIterator(final IContainer base) {
 		super(computePrefix(base));
 		node = base;
+		init(entries());
 	}
 
 	private ContainerTreeIterator(final WorkingTreeIterator p,
 			final IContainer base) {
 		super(p);
 		node = base;
+		init(entries());
 	}
 
 	@Override
@@ -86,16 +88,13 @@ public AbstractTreeIterator createSubtreeIterator(final Repository db)
 					Constants.TYPE_TREE);
 	}
 
-	@Override
-	protected Entry[] getEntries() throws IOException {
+	private Entry[] entries() {
 		final IResource[] all;
 		try {
 //			all = node.members(IContainer.INCLUDE_HIDDEN); 3.4 flag
 			all = node.members(0);
 		} catch (CoreException err) {
-			final IOException ioe = new IOException(err.getMessage());
-			ioe.initCause(err);
-			throw ioe;
+			return EOF;
 		}
 
 		final Entry[] r = new Entry[all.length];
diff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/dircache/DirCacheBuilderIteratorTest.java b/org.spearce.jgit.test/tst/org/spearce/jgit/dircache/DirCacheBuilderIteratorTest.java
index cbcdeb5..162f4ba 100644
--- a/org.spearce.jgit.test/tst/org/spearce/jgit/dircache/DirCacheBuilderIteratorTest.java
+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/dircache/DirCacheBuilderIteratorTest.java
@@ -74,7 +74,7 @@ public void testPathFilterGroup_DoesNotSkipTail() throws Exception {
 		assertTrue("found " + paths[expIdx], tw.next());
 		final DirCacheIterator c = tw.getTree(0, DirCacheIterator.class);
 		assertNotNull(c);
-		assertEquals(expIdx, c.cachePos);
+		assertEquals(expIdx, c.ptr);
 		assertSame(ents[expIdx], c.getDirCacheEntry());
 		assertEquals(paths[expIdx], tw.getPathString());
 		assertEquals(mode.getBits(), tw.getRawMode(0));
diff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/dircache/DirCacheIteratorTest.java b/org.spearce.jgit.test/tst/org/spearce/jgit/dircache/DirCacheIteratorTest.java
index 62a162f..51b3c5a 100644
--- a/org.spearce.jgit.test/tst/org/spearce/jgit/dircache/DirCacheIteratorTest.java
+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/dircache/DirCacheIteratorTest.java
@@ -50,7 +50,6 @@ public void testEmptyTree_NoTreeWalk() throws Exception {
 		assertEquals(0, dc.getEntryCount());
 
 		final DirCacheIterator i = new DirCacheIterator(dc);
-		i.next();
 		assertTrue(i.eof());
 	}
 
@@ -79,11 +78,8 @@ public void testNoSubtree_NoTreeWalk() throws Exception {
 
 		final DirCacheIterator i = new DirCacheIterator(dc);
 		int pathIdx = 0;
-		for (;;) {
-			i.next();
-			if (i.eof())
-				break;
-			assertEquals(pathIdx, i.cachePos);
+		for (; !i.eof(); i.next()) {
+			assertEquals(pathIdx, i.ptr);
 			assertSame(ents[pathIdx], i.getDirCacheEntry());
 			pathIdx++;
 		}
@@ -113,7 +109,7 @@ public void testNoSubtree_WithTreeWalk() throws Exception {
 		int pathIdx = 0;
 		while (tw.next()) {
 			assertSame(i, tw.getTree(0, DirCacheIterator.class));
-			assertEquals(pathIdx, i.cachePos);
+			assertEquals(pathIdx, i.ptr);
 			assertSame(ents[pathIdx], i.getDirCacheEntry());
 			assertEquals(paths[pathIdx], tw.getPathString());
 			assertEquals(modes[pathIdx].getBits(), tw.getRawMode(0));
@@ -156,7 +152,7 @@ public void testSingleSubtree_NoRecursion() throws Exception {
 			assertEquals(expPaths[pathIdx], tw.getPathString());
 
 			if (expPos[pathIdx] >= 0) {
-				assertEquals(expPos[pathIdx], i.cachePos);
+				assertEquals(expPos[pathIdx], i.ptr);
 				assertSame(ents[expPos[pathIdx]], i.getDirCacheEntry());
 			} else {
 				assertSame(FileMode.TREE, tw.getFileMode(0));
@@ -192,7 +188,7 @@ public void testSingleSubtree_Recursive() throws Exception {
 		while (tw.next()) {
 			final DirCacheIterator c = tw.getTree(0, DirCacheIterator.class);
 			assertNotNull(c);
-			assertEquals(pathIdx, c.cachePos);
+			assertEquals(pathIdx, c.ptr);
 			assertSame(ents[pathIdx], c.getDirCacheEntry());
 			assertEquals(paths[pathIdx], tw.getPathString());
 			assertEquals(mode.getBits(), tw.getRawMode(0));
@@ -226,7 +222,7 @@ public void testTwoLevelSubtree_Recursive() throws Exception {
 		while (tw.next()) {
 			final DirCacheIterator c = tw.getTree(0, DirCacheIterator.class);
 			assertNotNull(c);
-			assertEquals(pathIdx, c.cachePos);
+			assertEquals(pathIdx, c.ptr);
 			assertSame(ents[pathIdx], c.getDirCacheEntry());
 			assertEquals(paths[pathIdx], tw.getPathString());
 			assertEquals(mode.getBits(), tw.getRawMode(0));
@@ -262,7 +258,7 @@ public void testTwoLevelSubtree_FilterPath() throws Exception {
 			assertTrue(tw.next());
 			final DirCacheIterator c = tw.getTree(0, DirCacheIterator.class);
 			assertNotNull(c);
-			assertEquals(victimIdx, c.cachePos);
+			assertEquals(victimIdx, c.ptr);
 			assertSame(ents[victimIdx], c.getDirCacheEntry());
 			assertEquals(paths[victimIdx], tw.getPathString());
 			assertEquals(mode.getBits(), tw.getRawMode(0));
diff --git a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheBuildIterator.java b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheBuildIterator.java
index 227b64c..aaec4fc 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheBuildIterator.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheBuildIterator.java
@@ -109,7 +109,7 @@ public AbstractTreeIterator createSubtreeIterator(final Repository repo)
 	@Override
 	public void skip() throws CorruptObjectException {
 		if (currentSubtree != null)
-			builder.keep(cachePos, currentSubtree.getEntrySpan());
+			builder.keep(ptr, currentSubtree.getEntrySpan());
 		else
 			builder.add(currentEntry);
 		next();
@@ -117,8 +117,9 @@ public void skip() throws CorruptObjectException {
 
 	@Override
 	public void stopWalk() {
+		final int cur = ptr;
 		final int cnt = cache.getEntryCount();
-		if (cachePos < cnt)
-			builder.keep(cachePos, cnt - cachePos);
+		if (cur < cnt)
+			builder.keep(cur, cnt - cur);
 	}
 }
diff --git a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheIterator.java b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheIterator.java
index c093bb2..248ae1e 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheIterator.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheIterator.java
@@ -40,7 +40,6 @@
 import java.io.IOException;
 import java.util.Arrays;
 
-import org.spearce.jgit.errors.CorruptObjectException;
 import org.spearce.jgit.errors.IncorrectObjectTypeException;
 import org.spearce.jgit.lib.Constants;
 import org.spearce.jgit.lib.FileMode;
@@ -65,19 +64,19 @@
 	/** The tree this iterator is walking. */
 	private final DirCacheTree tree;
 
+	/** Last position in this tree. */
+	private final int treeEnd;
+
 	/** Special buffer to hold the ObjectId of {@link #currentSubtree}. */
 	private final byte[] subtreeId;
 
 	/** Index of entry within {@link #cache}. */
-	protected int cachePos;
-
-	/** Position of entry within {@link #tree}'s entry span. */
-	private int treePos;
+	protected int ptr;
 
 	/** Next subtree to consider within {@link #tree}. */
-	private int subtreeIdx;
+	private int nextSubtreePos;
 
-	/** The current file entry from {@link #cache}, matching {@link #cachePos}. */
+	/** The current file entry from {@link #cache}. */
 	protected DirCacheEntry currentEntry;
 
 	/** The subtree containing {@link #currentEntry} if this is first entry. */
@@ -96,18 +95,20 @@
 	public DirCacheIterator(final DirCache dc) {
 		cache = dc;
 		tree = dc.getCacheTree(true);
+		treeEnd = tree.getEntrySpan();
 		subtreeId = new byte[Constants.OBJECT_ID_LENGTH];
-		cachePos = -1;
-		treePos = -1;
+		if (!eof())
+			parseEntry();
 	}
 
 	protected DirCacheIterator(final DirCacheIterator p, final DirCacheTree dct) {
 		super(p, p.path, p.pathLen + 1);
 		cache = p.cache;
 		tree = dct;
+		treeEnd = p.ptr + tree.getEntrySpan();
 		subtreeId = p.subtreeId;
-		cachePos = p.cachePos - 1; // back up so first next() call enters it
-		treePos = -1;
+		ptr = p.ptr;
+		parseEntry();
 	}
 
 	@Override
@@ -139,40 +140,31 @@ public int idOffset() {
 
 	@Override
 	public boolean eof() {
-		return treePos >= tree.getEntrySpan();
+		return ptr == treeEnd;
 	}
 
 	@Override
-	public void next() throws CorruptObjectException {
-		if (currentSubtree != null) {
-			// If our last position was a subtree we need to skip over
-			// its entire span to get to the item after the subtree.
-			//
-			final int n = currentSubtree.getEntrySpan();
-			cachePos += n;
-			treePos += n;
-			currentSubtree = null;
-		} else {
-			// Our last position was a file/symlink/gitlink, so we
-			// only skip the one entry.
-			//
-			cachePos++;
-			treePos++;
-		}
-
-		if (treePos >= tree.getEntrySpan())
-			return; // this iterator is now at EOF.
+	public void next() {
+		if (currentSubtree != null)
+			ptr += currentSubtree.getEntrySpan();
+		else
+			ptr++;
+		if (!eof())
+			parseEntry();
+	}
 
-		currentEntry = cache.getEntry(cachePos);
+	private void parseEntry() {
+		currentEntry = cache.getEntry(ptr);
 		final byte[] cep = currentEntry.path;
-		if (subtreeIdx < tree.getChildCount()) {
-			final DirCacheTree s = tree.getChild(subtreeIdx);
+
+		if (nextSubtreePos != tree.getChildCount()) {
+			final DirCacheTree s = tree.getChild(nextSubtreePos);
 			if (s.contains(cep, pathOffset, cep.length)) {
 				// The current position is the first file of this subtree.
 				// Use the subtree instead as the current position.
 				//
 				currentSubtree = s;
-				subtreeIdx++;
+				nextSubtreePos++;
 
 				if (s.isValid())
 					s.getObjectId().copyRawTo(subtreeId, 0);
@@ -191,6 +183,7 @@ public void next() throws CorruptObjectException {
 		mode = currentEntry.getRawMode();
 		path = cep;
 		pathLen = cep.length;
+		currentSubtree = null;
 	}
 
 	/**
diff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java
index e6aa338..208adc7 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java
@@ -53,9 +53,8 @@
 /**
  * Walks a Git tree (directory) in Git sort order.
  * <p>
- * A new iterator instance should be positioned before the first entry. The data
- * about the first entry is not available until after the first call to
- * {@link #next()} is made.
+ * A new iterator instance should be positioned on the first entry, or at eof.
+ * Data for the first entry (if not at eof) should be available immediately.
  * <p>
  * Implementors must walk a tree in the Git sort order, which has the following
  * odd sorting:
diff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/CanonicalTreeParser.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/CanonicalTreeParser.java
index 55942ed..ebcc787 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/CanonicalTreeParser.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/CanonicalTreeParser.java
@@ -52,7 +52,11 @@
 public class CanonicalTreeParser extends AbstractTreeIterator {
 	private byte[] raw;
 
-	private int rawPtr;
+	/** First offset within {@link #raw} of the current entry's data. */
+	private int currPtr;
+
+	/** Offset one past the current entry (first byte of next entry. */
+	private int nextPtr;
 
 	/** Create a new parser. */
 	public CanonicalTreeParser() {
@@ -71,7 +75,9 @@ private CanonicalTreeParser(final CanonicalTreeParser p) {
 	 */
 	public void reset(final byte[] treeData) {
 		raw = treeData;
-		rawPtr = 0;
+		currPtr = 0;
+		if (!eof())
+			parseEntry();
 	}
 
 	/**
@@ -118,20 +124,21 @@ public CanonicalTreeParser createSubtreeIterator(final Repository repo)
 
 	@Override
 	public int idOffset() {
-		return rawPtr - Constants.OBJECT_ID_LENGTH;
+		return nextPtr - Constants.OBJECT_ID_LENGTH;
 	}
 
 	public boolean eof() {
-		return raw == null;
+		return currPtr == raw.length;
 	}
 
 	public void next() throws CorruptObjectException {
-		int ptr = rawPtr;
-		if (ptr >= raw.length) {
-			raw = null;
-			return;
-		}
+		currPtr = nextPtr;
+		if (!eof())
+			parseEntry();
+	}
 
+	private void parseEntry() {
+		int ptr = currPtr;
 		byte c = raw[ptr++];
 		int tmp = c - '0';
 		for (;;) {
@@ -156,6 +163,6 @@ public void next() throws CorruptObjectException {
 			}
 		}
 		pathLen = tmp;
-		rawPtr = ptr + Constants.OBJECT_ID_LENGTH;
+		nextPtr = ptr + Constants.OBJECT_ID_LENGTH;
 	}
 }
diff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/FileTreeIterator.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/FileTreeIterator.java
index 25425dd..2c71151 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/FileTreeIterator.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/FileTreeIterator.java
@@ -66,6 +66,7 @@
 	 */
 	public FileTreeIterator(final File root) {
 		directory = root;
+		init(entries());
 	}
 
 	/**
@@ -80,6 +81,7 @@ public FileTreeIterator(final File root) {
 	protected FileTreeIterator(final FileTreeIterator p, final File root) {
 		super(p);
 		directory = root;
+		init(entries());
 	}
 
 	@Override
@@ -88,8 +90,7 @@ public AbstractTreeIterator createSubtreeIterator(final Repository repo)
 		return new FileTreeIterator(this, ((FileEntry) current()).file);
 	}
 
-	@Override
-	protected Entry[] getEntries() {
+	private Entry[] entries() {
 		final File[] all = directory.listFiles();
 		if (all == null)
 			return EOF;
diff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java
index 5aabc19..3bdef22 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java
@@ -276,14 +276,12 @@ public void reset(final ObjectId[] ids) throws MissingObjectException,
 				if (o instanceof CanonicalTreeParser) {
 					o.matches = null;
 					((CanonicalTreeParser) o).reset(db, ids[i]);
-					o.next();
 					r[i] = o;
 					continue;
 				}
 			}
 
 			o = parserFor(ids[i]);
-			o.next();
 			r[i] = o;
 		}
 
@@ -340,7 +338,6 @@ public int addTree(final AbstractTreeIterator p)
 		System.arraycopy(trees, 0, newTrees, 0, n);
 		newTrees[n] = p;
 		p.matches = null;
-		p.next();
 
 		trees = newTrees;
 		return n;
@@ -617,7 +614,6 @@ public void enterSubtree() throws MissingObjectException,
 				n = t.createSubtreeIterator(db);
 			else
 				n = new EmptyTreeIterator(t);
-			n.next();
 			tmp[i] = n;
 		}
 		depth++;
diff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/WorkingTreeIterator.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/WorkingTreeIterator.java
index f66b5e9..e81ff4a 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/WorkingTreeIterator.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/WorkingTreeIterator.java
@@ -63,7 +63,7 @@
  * @see FileTreeIterator
  */
 public abstract class WorkingTreeIterator extends AbstractTreeIterator {
-	/** An empty entry array, suitable for return from {@link #getEntries()}. */
+	/** An empty entry array, suitable for {@link #init(Entry[])}. */
 	protected static final Entry[] EOF = {};
 
 	/** Size we perform file IO in if we have to read and hash a file. */
@@ -72,7 +72,7 @@
 	/** The {@link #idBuffer()} for the current entry. */
 	private byte[] contentId;
 
-	/** Value of {@link #ptr} when {@link #contentId} was last populated. */
+	/** Index within {@link #entries} that {@link #contentId} came from. */
 	private int contentIdFromPtr;
 
 	/** Buffer used to perform {@link #contentId} computations. */
@@ -132,15 +132,12 @@ protected WorkingTreeIterator(final WorkingTreeIterator p) {
 
 	@Override
 	public byte[] idBuffer() {
-		if (contentIdFromPtr == ptr - 1)
+		if (contentIdFromPtr == ptr)
 			return contentId;
-		if (entries == EOF)
-			return zeroid;
-
 		switch (mode & 0170000) {
 		case 0100000: /* normal files */
-			contentIdFromPtr = ptr - 1;
-			return contentId = idBufferBlob(entries[contentIdFromPtr]);
+			contentIdFromPtr = ptr;
+			return contentId = idBufferBlob(entries[ptr]);
 		case 0120000: /* symbolic links */
 			// Java does not support symbolic links, so we should not
 			// have reached this particular part of the walk code.
@@ -235,21 +232,18 @@ public int idOffset() {
 
 	@Override
 	public boolean eof() {
-		return entries == EOF;
+		return ptr == entryCnt;
 	}
 
 	@Override
 	public void next() throws CorruptObjectException {
-		if (entries == null)
-			loadEntries();
-		if (ptr == entryCnt) {
-			entries = EOF;
-			return;
-		}
-		if (entries == EOF)
-			return;
+		ptr++;
+		if (!eof())
+			parseEntry();
+	}
 
-		final Entry e = entries[ptr++];
+	private void parseEntry() {
+		final Entry e = entries[ptr];
 		mode = e.getMode().getBits();
 
 		final int nameLen = e.encodedNameLen;
@@ -338,43 +332,35 @@ static int lastPathChar(final Entry e) {
 		return e.getMode() == FileMode.TREE ? '/' : '\0';
 	}
 
-	private void loadEntries() throws CorruptObjectException {
+	protected void init(final Entry[] list) {
 		// Filter out nulls, . and .. as these are not valid tree entries,
 		// also cache the encoded forms of the path names for efficient use
 		// later on during sorting and iteration.
 		//
-		try {
-			entries = getEntries();
-			int i, o;
-
-			for (i = 0, o = 0; i < entries.length; i++) {
-				final Entry e = entries[i];
-				if (e == null)
-					continue;
-				final String name = e.getName();
-				if (".".equals(name) || "..".equals(name))
-					continue;
-				if (parent == null && ".git".equals(name))
-					continue;
-				if (i != o)
-					entries[o] = e;
-				e.encodeName(nameEncoder);
-				o++;
-			}
-			entryCnt = o;
-			contentIdFromPtr = -1;
-			Arrays.sort(entries, 0, entryCnt, ENTRY_CMP);
-		} catch (CharacterCodingException e) {
-			final CorruptObjectException why;
-			why = new CorruptObjectException("Invalid file name encoding");
-			why.initCause(e);
-			throw why;
-		} catch (IOException e) {
-			final CorruptObjectException why;
-			why = new CorruptObjectException("Error reading directory");
-			why.initCause(e);
-			throw why;
+		entries = list;
+		int i, o;
+
+		for (i = 0, o = 0; i < entries.length; i++) {
+			final Entry e = entries[i];
+			if (e == null)
+				continue;
+			final String name = e.getName();
+			if (".".equals(name) || "..".equals(name))
+				continue;
+			if (parent == null && ".git".equals(name))
+				continue;
+			if (i != o)
+				entries[o] = e;
+			e.encodeName(nameEncoder);
+			o++;
 		}
+		entryCnt = o;
+		Arrays.sort(entries, 0, entryCnt, ENTRY_CMP);		
+
+		contentIdFromPtr = -1;
+		ptr = 0;
+		if (!eof())
+			parseEntry();
 	}
 
 	/**
@@ -383,37 +369,24 @@ private void loadEntries() throws CorruptObjectException {
 	 * @return the currently selected entry.
 	 */
 	protected Entry current() {
-		return entries[ptr - 1];
+		return entries[ptr];
 	}
 
-	/**
-	 * Obtain an unsorted list of this iterator's contents.
-	 * <p>
-	 * Implementations only need to provide the unsorted contents of their lower
-	 * level directory. The caller will automatically prune out ".", "..",
-	 * ".git", as well as null entries as necessary, and then sort the array
-	 * for iteration within a TreeWalk instance.
-	 * <p>
-	 * The returned array will be modified by the caller.
-	 * <p>
-	 * This method is only invoked once per iterator instance.
-	 * 
-	 * @return unsorted list of the immediate children. Never null, but may be
-	 *         {@link #EOF} if no items can be obtained.
-	 * @throws IOException
-	 *             reading the contents failed due to IO errors.
-	 */
-	protected abstract Entry[] getEntries() throws IOException;
-
 	/** A single entry within a working directory tree. */
 	protected static abstract class Entry {
 		byte[] encodedName;
 
 		int encodedNameLen;
 
-		void encodeName(final CharsetEncoder enc)
-				throws CharacterCodingException {
-			final ByteBuffer b = enc.encode(CharBuffer.wrap(getName()));
+		void encodeName(final CharsetEncoder enc) {
+			final ByteBuffer b;			
+			try {
+				b = enc.encode(CharBuffer.wrap(getName()));
+			} catch (CharacterCodingException e) {
+				// This should so never happen.
+				throw new RuntimeException("Unencodeable file: " + getName());
+			}
+
 			encodedNameLen = b.limit();
 			if (b.hasArray() && b.arrayOffset() == 0)
 				encodedName = b.array();
-- 
1.6.0.87.g2858d

[JGIT PATCH 10/14] Make all AbstractTreeIterator implementations bi-directional

[Shawn O. Pearce]

To support scanning ahead and then rewinding back to our prior
location we need to allow all tree iterators to be moved both
forward and backwards through their entries.  The next(int)
API replaces the simple next() by supplying the amount that
the iterator needs to move forward. A corresponding back(int)
method supplies the opposite direction of travel.

Some iterators like WorkingTreeIterator can efficiently move
foward and backwards any step because they have a direct 1:1
mapping between positions of the iterator and an array index.
Others like CanonicalTreeParser must scan through their input
buffer, but can try to reduce the work needed on larger steps
as they move past the undesired entries.  DirCacheIterator is
a challenge because it needs to match each entry up onto the
DirCacheTrees available at this level.

This API (and its implements) is really meant for peeking at
the next entry (or two) forward to see if there is a name (but
not mode) match during a TreeWalk.  This is to help TreeWalk
catch a directory/file mode conflict and report it, despite
the directory and file variants of a name appearing at two
very different positions in the trees.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../jgit/dircache/DirCacheIteratorTest.java        |    2 +-
 .../jgit/treewalk/CanonicalTreeParserTest.java     |  261 ++++++++++++++++++++
 .../jgit/dircache/DirCacheBuildIterator.java       |    2 +-
 .../spearce/jgit/dircache/DirCacheIterator.java    |   27 ++-
 .../jgit/treewalk/AbstractTreeIterator.java        |   38 +++-
 .../spearce/jgit/treewalk/CanonicalTreeParser.java |   68 +++++-
 .../spearce/jgit/treewalk/EmptyTreeIterator.java   |    7 +-
 .../src/org/spearce/jgit/treewalk/TreeWalk.java    |    2 +-
 .../spearce/jgit/treewalk/WorkingTreeIterator.java |   10 +-
 9 files changed, 398 insertions(+), 19 deletions(-)
 create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/treewalk/CanonicalTreeParserTest.java

diff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/dircache/DirCacheIteratorTest.java b/org.spearce.jgit.test/tst/org/spearce/jgit/dircache/DirCacheIteratorTest.java
index 51b3c5a..047c989 100644
--- a/org.spearce.jgit.test/tst/org/spearce/jgit/dircache/DirCacheIteratorTest.java
+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/dircache/DirCacheIteratorTest.java
@@ -78,7 +78,7 @@ public void testNoSubtree_NoTreeWalk() throws Exception {
 
 		final DirCacheIterator i = new DirCacheIterator(dc);
 		int pathIdx = 0;
-		for (; !i.eof(); i.next()) {
+		for (; !i.eof(); i.next(1)) {
 			assertEquals(pathIdx, i.ptr);
 			assertSame(ents[pathIdx], i.getDirCacheEntry());
 			pathIdx++;
diff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/treewalk/CanonicalTreeParserTest.java b/org.spearce.jgit.test/tst/org/spearce/jgit/treewalk/CanonicalTreeParserTest.java
new file mode 100644
index 0000000..fd92844
--- /dev/null
+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/treewalk/CanonicalTreeParserTest.java
@@ -0,0 +1,261 @@
+/*
+ * Copyright (C) 2008, Google Inc.
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above
+ *   copyright notice, this list of conditions and the following
+ *   disclaimer in the documentation and/or other materials provided
+ *   with the distribution.
+ *
+ * - Neither the name of the Git Development Community nor the
+ *   names of its contributors may be used to endorse or promote
+ *   products derived from this software without specific prior
+ *   written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
+ * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+package org.spearce.jgit.treewalk;
+
+import java.io.ByteArrayOutputStream;
+
+import junit.framework.TestCase;
+
+import org.spearce.jgit.lib.Constants;
+import org.spearce.jgit.lib.FileMode;
+import org.spearce.jgit.lib.ObjectId;
+import org.spearce.jgit.util.RawParseUtils;
+
+public class CanonicalTreeParserTest extends TestCase {
+	private final CanonicalTreeParser ctp = new CanonicalTreeParser();
+
+	private final FileMode m644 = FileMode.REGULAR_FILE;
+
+	private final FileMode mt = FileMode.TREE;
+
+	private final ObjectId hash_a = ObjectId
+			.fromString("6b9c715d21d5486e59083fb6071566aa6ecd4d42");
+
+	private final ObjectId hash_foo = ObjectId
+			.fromString("a213e8e25bb2442326e86cbfb9ef56319f482869");
+
+	private final ObjectId hash_sometree = ObjectId
+			.fromString("daf4bdb0d7bb24319810fe0e73aa317663448c93");
+
+	private byte[] tree1;
+
+	private byte[] tree2;
+
+	private byte[] tree3;
+
+	public void setUp() throws Exception {
+		super.setUp();
+
+		tree1 = mkree(entry(m644, "a", hash_a));
+		tree2 = mkree(entry(m644, "a", hash_a), entry(m644, "foo", hash_foo));
+		tree3 = mkree(entry(m644, "a", hash_a), entry(mt, "b_sometree",
+				hash_sometree), entry(m644, "foo", hash_foo));
+	}
+
+	private static byte[] mkree(final byte[]... data) throws Exception {
+		final ByteArrayOutputStream out = new ByteArrayOutputStream();
+		for (final byte[] e : data)
+			out.write(e);
+		return out.toByteArray();
+	}
+
+	private static byte[] entry(final FileMode mode, final String name,
+			final ObjectId id) throws Exception {
+		final ByteArrayOutputStream out = new ByteArrayOutputStream();
+		mode.copyTo(out);
+		out.write(' ');
+		out.write(Constants.encode(name));
+		out.write(0);
+		id.copyRawTo(out);
+		return out.toByteArray();
+	}
+
+	private String path() {
+		return RawParseUtils.decode(Constants.CHARSET, ctp.path,
+				ctp.pathOffset, ctp.pathLen);
+	}
+
+	public void testEmptyTree_AtEOF() throws Exception {
+		ctp.reset(new byte[0]);
+		assertTrue(ctp.eof());
+	}
+
+	public void testOneEntry_Forward() throws Exception {
+		ctp.reset(tree1);
+
+		assertFalse(ctp.eof());
+		assertEquals(m644.getBits(), ctp.mode);
+		assertEquals("a", path());
+		assertEquals(hash_a, ctp.getEntryObjectId());
+
+		ctp.next(1);
+		assertTrue(ctp.eof());
+	}
+
+	public void testTwoEntries_ForwardOneAtATime() throws Exception {
+		ctp.reset(tree2);
+
+		assertFalse(ctp.eof());
+		assertEquals(m644.getBits(), ctp.mode);
+		assertEquals("a", path());
+		assertEquals(hash_a, ctp.getEntryObjectId());
+
+		ctp.next(1);
+		assertFalse(ctp.eof());
+		assertEquals(m644.getBits(), ctp.mode);
+		assertEquals("foo", path());
+		assertEquals(hash_foo, ctp.getEntryObjectId());
+
+		ctp.next(1);
+		assertTrue(ctp.eof());
+	}
+
+	public void testOneEntry_Seek1IsEOF() throws Exception {
+		ctp.reset(tree1);
+		ctp.next(1);
+		assertTrue(ctp.eof());
+	}
+
+	public void testTwoEntries_Seek2IsEOF() throws Exception {
+		ctp.reset(tree2);
+		ctp.next(2);
+		assertTrue(ctp.eof());
+	}
+
+	public void testThreeEntries_Seek3IsEOF() throws Exception {
+		ctp.reset(tree3);
+		ctp.next(3);
+		assertTrue(ctp.eof());
+	}
+
+	public void testThreeEntries_Seek2() throws Exception {
+		ctp.reset(tree3);
+
+		ctp.next(2);
+		assertFalse(ctp.eof());
+		assertFalse(ctp.eof());
+		assertEquals(m644.getBits(), ctp.mode);
+		assertEquals("foo", path());
+		assertEquals(hash_foo, ctp.getEntryObjectId());
+
+		ctp.next(1);
+		assertTrue(ctp.eof());
+	}
+
+	public void testOneEntry_Backwards() throws Exception {
+		ctp.reset(tree1);
+		ctp.next(1);
+		assertTrue(ctp.eof());
+
+		ctp.back(1);
+		assertFalse(ctp.eof());
+		assertEquals(m644.getBits(), ctp.mode);
+		assertEquals("a", path());
+		assertEquals(hash_a, ctp.getEntryObjectId());
+	}
+
+	public void testTwoEntries_BackwardsOneAtATime() throws Exception {
+		ctp.reset(tree2);
+		ctp.next(2);
+		assertTrue(ctp.eof());
+
+		ctp.back(1);
+		assertFalse(ctp.eof());
+		assertEquals(m644.getBits(), ctp.mode);
+		assertEquals("foo", path());
+		assertEquals(hash_foo, ctp.getEntryObjectId());
+
+		ctp.back(1);
+		assertFalse(ctp.eof());
+		assertEquals(m644.getBits(), ctp.mode);
+		assertEquals("a", path());
+		assertEquals(hash_a, ctp.getEntryObjectId());
+	}
+
+	public void testTwoEntries_BackwardsTwo() throws Exception {
+		ctp.reset(tree2);
+		ctp.next(2);
+		assertTrue(ctp.eof());
+
+		ctp.back(2);
+		assertFalse(ctp.eof());
+		assertEquals(m644.getBits(), ctp.mode);
+		assertEquals("a", path());
+		assertEquals(hash_a, ctp.getEntryObjectId());
+
+		ctp.next(1);
+		assertFalse(ctp.eof());
+		assertEquals(m644.getBits(), ctp.mode);
+		assertEquals("foo", path());
+		assertEquals(hash_foo, ctp.getEntryObjectId());
+
+		ctp.next(1);
+		assertTrue(ctp.eof());
+	}
+
+	public void testThreeEntries_BackwardsTwo() throws Exception {
+		ctp.reset(tree3);
+		ctp.next(3);
+		assertTrue(ctp.eof());
+
+		ctp.back(2);
+		assertFalse(ctp.eof());
+		assertEquals(mt.getBits(), ctp.mode);
+		assertEquals("b_sometree", path());
+		assertEquals(hash_sometree, ctp.getEntryObjectId());
+
+		ctp.next(1);
+		assertFalse(ctp.eof());
+		assertEquals(m644.getBits(), ctp.mode);
+		assertEquals("foo", path());
+		assertEquals(hash_foo, ctp.getEntryObjectId());
+
+		ctp.next(1);
+		assertTrue(ctp.eof());
+	}
+
+	public void testBackwards_ConfusingPathName() throws Exception {
+		final String aVeryConfusingName = "confusing 644 entry 755 and others";
+		ctp.reset(mkree(entry(m644, "a", hash_a), entry(mt, aVeryConfusingName,
+				hash_sometree), entry(m644, "foo", hash_foo)));
+		ctp.next(3);
+		assertTrue(ctp.eof());
+
+		ctp.back(2);
+		assertFalse(ctp.eof());
+		assertEquals(mt.getBits(), ctp.mode);
+		assertEquals(aVeryConfusingName, path());
+		assertEquals(hash_sometree, ctp.getEntryObjectId());
+
+		ctp.back(1);
+		assertFalse(ctp.eof());
+		assertEquals(m644.getBits(), ctp.mode);
+		assertEquals("a", path());
+		assertEquals(hash_a, ctp.getEntryObjectId());
+	}
+}
diff --git a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheBuildIterator.java b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheBuildIterator.java
index aaec4fc..234ffd2 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheBuildIterator.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheBuildIterator.java
@@ -112,7 +112,7 @@ public void skip() throws CorruptObjectException {
 			builder.keep(ptr, currentSubtree.getEntrySpan());
 		else
 			builder.add(currentEntry);
-		next();
+		next(1);
 	}
 
 	@Override
diff --git a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheIterator.java b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheIterator.java
index 248ae1e..84cefa5 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheIterator.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheIterator.java
@@ -144,13 +144,28 @@ public boolean eof() {
 	}
 
 	@Override
-	public void next() {
-		if (currentSubtree != null)
-			ptr += currentSubtree.getEntrySpan();
-		else
-			ptr++;
-		if (!eof())
+	public void next(int delta) {
+		while (--delta >= 0) {
+			if (currentSubtree != null)
+				ptr += currentSubtree.getEntrySpan();
+			else
+				ptr++;
+			if (eof())
+				break;
+			parseEntry();
+		}
+	}
+
+	@Override
+	public void back(int delta) {
+		while (--delta >= 0) {
+			if (currentSubtree != null)
+				nextSubtreePos--;
+			ptr--;
 			parseEntry();
+			if (currentSubtree != null)
+				ptr -= currentSubtree.getEntrySpan() - 1;
+		}
 	}
 
 	private void parseEntry() {
diff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java
index 208adc7..8ec506c 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java
@@ -349,7 +349,34 @@ public abstract AbstractTreeIterator createSubtreeIterator(Repository repo)
 	public abstract boolean eof();
 
 	/**
-	 * Advance to the next tree entry, populating this iterator with its data.
+	 * Move to next entry, populating this iterator with the entry data.
+	 * <p>
+	 * The delta indicates how many moves forward should occur. The most common
+	 * delta is 1 to move to the next entry.
+	 * <p>
+	 * Implementations must populate the following members:
+	 * <ul>
+	 * <li>{@link #mode}</li>
+	 * <li>{@link #path} (from {@link #pathOffset} to {@link #pathLen})</li>
+	 * <li>{@link #pathLen}</li>
+	 * </ul>
+	 * as well as any implementation dependent information necessary to
+	 * accurately return data from {@link #idBuffer()} and {@link #idOffset()}
+	 * when demanded.
+	 * 
+	 * @param delta
+	 *            number of entries to move the iterator by. Must be a positive,
+	 *            non-zero integer.
+	 * @throws CorruptObjectException
+	 *             the tree is invalid.
+	 */
+	public abstract void next(int delta) throws CorruptObjectException;
+
+	/**
+	 * Move to prior entry, populating this iterator with the entry data.
+	 * <p>
+	 * The delta indicates how many moves backward should occur.The most common
+	 * delta is 1 to move to the prior entry.
 	 * <p>
 	 * Implementations must populate the following members:
 	 * <ul>
@@ -361,15 +388,18 @@ public abstract AbstractTreeIterator createSubtreeIterator(Repository repo)
 	 * accurately return data from {@link #idBuffer()} and {@link #idOffset()}
 	 * when demanded.
 	 * 
+	 * @param delta
+	 *            number of entries to move the iterator by. Must be a positive,
+	 *            non-zero integer.
 	 * @throws CorruptObjectException
 	 *             the tree is invalid.
 	 */
-	public abstract void next() throws CorruptObjectException;
+	public abstract void back(int delta) throws CorruptObjectException;
 
 	/**
 	 * Advance to the next tree entry, populating this iterator with its data.
 	 * <p>
-	 * This method behaves like {@link #next()} but is called by
+	 * This method behaves like <code>seek(1)</code> but is called by
 	 * {@link TreeWalk} only if a {@link TreeFilter} was used and ruled out the
 	 * current entry from the results. In such cases this tree iterator may
 	 * perform special behavior.
@@ -378,7 +408,7 @@ public abstract AbstractTreeIterator createSubtreeIterator(Repository repo)
 	 *             the tree is invalid.
 	 */
 	public void skip() throws CorruptObjectException {
-		next();
+		next(1);
 	}
 
 	/**
diff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/CanonicalTreeParser.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/CanonicalTreeParser.java
index ebcc787..111d03b 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/CanonicalTreeParser.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/CanonicalTreeParser.java
@@ -39,7 +39,6 @@
 
 import java.io.IOException;
 
-import org.spearce.jgit.errors.CorruptObjectException;
 import org.spearce.jgit.errors.IncorrectObjectTypeException;
 import org.spearce.jgit.errors.MissingObjectException;
 import org.spearce.jgit.lib.Constants;
@@ -131,12 +130,75 @@ public boolean eof() {
 		return currPtr == raw.length;
 	}
 
-	public void next() throws CorruptObjectException {
-		currPtr = nextPtr;
+	@Override
+	public void next(int delta) {
+		if (delta == 1) {
+			// Moving forward one is the most common case.
+			//
+			currPtr = nextPtr;
+			if (!eof())
+				parseEntry();
+			return;
+		}
+
+		// Fast skip over records, then parse the last one.
+		//
+		final int end = raw.length;
+		int ptr = nextPtr;
+		while (--delta > 0 && ptr != end) {
+			while (raw[ptr] != 0)
+				ptr++;
+			ptr += Constants.OBJECT_ID_LENGTH + 1;
+		}
+		if (delta != 0)
+			throw new ArrayIndexOutOfBoundsException(delta);
+		currPtr = ptr;
 		if (!eof())
 			parseEntry();
 	}
 
+	@Override
+	public void back(int delta) {
+		int ptr = currPtr;
+		while (--delta >= 0) {
+			if (ptr == 0)
+				throw new ArrayIndexOutOfBoundsException(delta);
+
+			// Rewind back beyond the id and the null byte. Find the
+			// last space, this _might_ be the split between the mode
+			// and the path. Most paths in most trees do not contain a
+			// space so this prunes our search more quickly.
+			//
+			ptr -= Constants.OBJECT_ID_LENGTH;
+			while (raw[--ptr] != ' ')
+				/* nothing */;
+			if (--ptr < Constants.OBJECT_ID_LENGTH) {
+				if (delta != 0)
+					throw new ArrayIndexOutOfBoundsException(delta);
+				ptr = 0;
+				break;
+			}
+
+			// Locate a position that matches "\0.{20}[0-7]" such that
+			// the ptr will rest on the [0-7]. This must be the first
+			// byte of the mode. This search works because the path in
+			// the prior record must have a non-zero length and must not
+			// contain a null byte.
+			//
+			for (int n;; ptr = n) {
+				n = ptr - 1;
+				final byte b = raw[n];
+				if ('0' <= b && b <= '7')
+					continue;
+				if (raw[n - Constants.OBJECT_ID_LENGTH] != 0)
+					continue;
+				break;
+			}
+		}
+		currPtr = ptr;
+		parseEntry();
+	}
+
 	private void parseEntry() {
 		int ptr = currPtr;
 		byte c = raw[ptr++];
diff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/EmptyTreeIterator.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/EmptyTreeIterator.java
index c5dc4ad..232e3b1 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/EmptyTreeIterator.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/EmptyTreeIterator.java
@@ -84,7 +84,12 @@ public boolean eof() {
 	}
 
 	@Override
-	public void next() throws CorruptObjectException {
+	public void next(final int delta) throws CorruptObjectException {
+		// Do nothing.
+	}
+
+	@Override
+	public void back(final int delta) throws CorruptObjectException {
 		// Do nothing.
 	}
 
diff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java
index 3bdef22..10cdebd 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java
@@ -651,7 +651,7 @@ private void popEntriesEqual() throws CorruptObjectException {
 		for (int i = 0; i < trees.length; i++) {
 			final AbstractTreeIterator t = trees[i];
 			if (t.matches == ch) {
-				t.next();
+				t.next(1);
 				t.matches = null;
 			}
 		}
diff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/WorkingTreeIterator.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/WorkingTreeIterator.java
index e81ff4a..41fd47b 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/WorkingTreeIterator.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/WorkingTreeIterator.java
@@ -236,12 +236,18 @@ public boolean eof() {
 	}
 
 	@Override
-	public void next() throws CorruptObjectException {
-		ptr++;
+	public void next(final int delta) throws CorruptObjectException {
+		ptr += delta;
 		if (!eof())
 			parseEntry();
 	}
 
+	@Override
+	public void back(final int delta) throws CorruptObjectException {
+		ptr -= delta;
+		parseEntry();
+	}
+
 	private void parseEntry() {
 		final Entry e = entries[ptr];
 		mode = e.getMode().getBits();
-- 
1.6.0.87.g2858d

[JGIT PATCH 11/14] Expose beginning of iterator indication from AbstractTreeIterator

[Shawn O. Pearce]

Callers like TreeWalk need to know if back(1) is going to be a valid
operation for a given AbstractTreeIterator before they try to make a
call to move the iterator backwards.  The new method first() returns
true only if the iterator is already positioned on its first entry,
in which case a call to back(n) (for any n) is invalid.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../spearce/jgit/dircache/DirCacheIterator.java    |   12 +++++++++++-
 .../jgit/treewalk/AbstractTreeIterator.java        |   13 +++++++++++++
 .../spearce/jgit/treewalk/CanonicalTreeParser.java |    5 +++++
 .../spearce/jgit/treewalk/EmptyTreeIterator.java   |    5 +++++
 .../spearce/jgit/treewalk/WorkingTreeIterator.java |    5 +++++
 5 files changed, 39 insertions(+), 1 deletions(-)

diff --git a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheIterator.java b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheIterator.java
index 84cefa5..8384723 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheIterator.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheIterator.java
@@ -64,6 +64,9 @@
 	/** The tree this iterator is walking. */
 	private final DirCacheTree tree;
 
+	/** First position in this tree. */
+	private final int treeStart;
+
 	/** Last position in this tree. */
 	private final int treeEnd;
 
@@ -95,6 +98,7 @@
 	public DirCacheIterator(final DirCache dc) {
 		cache = dc;
 		tree = dc.getCacheTree(true);
+		treeStart = 0;
 		treeEnd = tree.getEntrySpan();
 		subtreeId = new byte[Constants.OBJECT_ID_LENGTH];
 		if (!eof())
@@ -105,7 +109,8 @@ protected DirCacheIterator(final DirCacheIterator p, final DirCacheTree dct) {
 		super(p, p.path, p.pathLen + 1);
 		cache = p.cache;
 		tree = dct;
-		treeEnd = p.ptr + tree.getEntrySpan();
+		treeStart = p.ptr;
+		treeEnd = treeStart + tree.getEntrySpan();
 		subtreeId = p.subtreeId;
 		ptr = p.ptr;
 		parseEntry();
@@ -139,6 +144,11 @@ public int idOffset() {
 	}
 
 	@Override
+	public boolean first() {
+		return ptr == treeStart;
+	}
+
+	@Override
 	public boolean eof() {
 		return ptr == treeEnd;
 	}
diff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java
index 8ec506c..c1b7ad8 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java
@@ -340,6 +340,19 @@ public abstract AbstractTreeIterator createSubtreeIterator(Repository repo)
 			throws IncorrectObjectTypeException, IOException;
 
 	/**
+	 * Is this tree iterator positioned on its first entry?
+	 * <p>
+	 * An iterator is positioned on the first entry if <code>back(1)</code>
+	 * would be an invalid request as there is no entry before the current one.
+	 * <p>
+	 * An empty iterator (one with no entries) will be
+	 * <code>first() &amp;&amp; eof()</code>.
+	 * 
+	 * @return true if the iterator is positioned on the first entry.
+	 */
+	public abstract boolean first();
+
+	/**
 	 * Is this tree iterator at its EOF point (no more entries)?
 	 * <p>
 	 * An iterator is at EOF if there is no current entry.
diff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/CanonicalTreeParser.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/CanonicalTreeParser.java
index 111d03b..dcc53cd 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/CanonicalTreeParser.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/CanonicalTreeParser.java
@@ -126,6 +126,11 @@ public int idOffset() {
 		return nextPtr - Constants.OBJECT_ID_LENGTH;
 	}
 
+	@Override
+	public boolean first() {
+		return currPtr == 0;
+	}
+
 	public boolean eof() {
 		return currPtr == raw.length;
 	}
diff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/EmptyTreeIterator.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/EmptyTreeIterator.java
index 232e3b1..eaca04e 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/EmptyTreeIterator.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/EmptyTreeIterator.java
@@ -79,6 +79,11 @@ public int idOffset() {
 	}
 
 	@Override
+	public boolean first() {
+		return true;
+	}
+
+	@Override
 	public boolean eof() {
 		return true;
 	}
diff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/WorkingTreeIterator.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/WorkingTreeIterator.java
index 41fd47b..9c53224 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/WorkingTreeIterator.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/WorkingTreeIterator.java
@@ -231,6 +231,11 @@ public int idOffset() {
 	}
 
 	@Override
+	public boolean first() {
+		return ptr == 0;
+	}
+
+	@Override
 	public boolean eof() {
 		return ptr == entryCnt;
 	}
-- 
1.6.0.87.g2858d

[JGIT PATCH 12/14] Allow application code to set ObjectIds in DirCacheEntry

[Shawn O. Pearce]

We support setting the ObjectId both from AnyObjectId (as we copy it)
and from a raw byte[] (as we are really copying into a raw byte[]).
The latter form is the most efficient as it probably permits callers
to avoid unnecessary conversion to some form of AnyObjectId.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../org/spearce/jgit/dircache/DirCacheEntry.java   |   26 ++++++++++++++++++++
 1 files changed, 26 insertions(+), 0 deletions(-)

diff --git a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheEntry.java b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheEntry.java
index 011bc16..a83cc78 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheEntry.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheEntry.java
@@ -43,6 +43,7 @@
 import java.nio.ByteBuffer;
 import java.util.Arrays;
 
+import org.spearce.jgit.lib.AnyObjectId;
 import org.spearce.jgit.lib.Constants;
 import org.spearce.jgit.lib.FileMode;
 import org.spearce.jgit.lib.ObjectId;
@@ -346,6 +347,31 @@ public ObjectId getObjectId() {
 	}
 
 	/**
+	 * Set the ObjectId for the entry.
+	 * 
+	 * @param id
+	 *            new object identifier for the entry. May be
+	 *            {@link ObjectId#zeroId()} to remove the current identifier.
+	 */
+	public void setObjectId(final AnyObjectId id) {
+		id.copyRawTo(idBuffer(), idOffset());
+	}
+
+	/**
+	 * Set the ObjectId for the entry from the raw binary representation.
+	 * 
+	 * @param bs
+	 *            the raw byte buffer to read from. At least 20 bytes after p
+	 *            must be available within this byte array.
+	 * @param p
+	 *            position to read the first byte of data from.
+	 */
+	public void setObjectIdFromRaw(final byte[] bs, final int p) {
+		final int n = Constants.OBJECT_ID_LENGTH;
+		System.arraycopy(bs, p, idBuffer(), idOffset(), n);
+	}
+
+	/**
 	 * Get the entry's complete path.
 	 * <p>
 	 * This method is not very efficient and is primarily meant for debugging
-- 
1.6.0.87.g2858d

[JGIT PATCH 13/14] Create NameConflictTreeWalk to transparently detect D/F conflicts

[Shawn O. Pearce]

When performing a merge between two or more tree iterators we really
need to be able to detect a directory-file conflict and handle it as
a single step of the TreeWalk iteration.  This way we can merge say
three iterators together:

  - commit $A
  - commit $B
  - working tree

Where the working tree is moving from $A to $B and the file path
"foo" has been changed from being a file in $A to a directory in
commit $B.  To make this change effective we must delete "foo"
and then enter the "foo" subtree to create the directory and
the paths within it.

This walk implementation is outside of TreeWalk as it is not a
trivial operation.  Applications should only use this variant
when conflict handling is absolutely necessary.  Basic commit
filtering (such as done by RevWalk) does not need this support
so we really don't want to bog down RevWalk's critical loop.

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../jgit/treewalk/AbstractTreeIterator.java        |    7 +
 .../jgit/treewalk/NameConflictTreeWalk.java        |  237 ++++++++++++++++++++
 .../src/org/spearce/jgit/treewalk/TreeWalk.java    |   12 +-
 3 files changed, 251 insertions(+), 5 deletions(-)
 create mode 100644 org.spearce.jgit/src/org/spearce/jgit/treewalk/NameConflictTreeWalk.java

diff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java
index c1b7ad8..31ccebe 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java
@@ -83,6 +83,13 @@
 	AbstractTreeIterator matches;
 
 	/**
+	 * Number of entries we moved forward to force a D/F conflict match.
+	 * 
+	 * @see NameConflictTreeWalk
+	 */
+	int matchShift;
+
+	/**
 	 * Mode bits for the current entry.
 	 * <p>
 	 * A numerical value from FileMode is usually faster for an iterator to
diff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/NameConflictTreeWalk.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/NameConflictTreeWalk.java
new file mode 100644
index 0000000..fdfba4e
--- /dev/null
+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/NameConflictTreeWalk.java
@@ -0,0 +1,237 @@
+/*
+ * Copyright (C) 2008, Google Inc.
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above
+ *   copyright notice, this list of conditions and the following
+ *   disclaimer in the documentation and/or other materials provided
+ *   with the distribution.
+ *
+ * - Neither the name of the Git Development Community nor the
+ *   names of its contributors may be used to endorse or promote
+ *   products derived from this software without specific prior
+ *   written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
+ * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+package org.spearce.jgit.treewalk;
+
+import org.spearce.jgit.dircache.DirCacheBuilder;
+import org.spearce.jgit.errors.CorruptObjectException;
+import org.spearce.jgit.lib.FileMode;
+import org.spearce.jgit.lib.Repository;
+
+/**
+ * Specialized TreeWalk to detect directory-file (D/F) name conflicts.
+ * <p>
+ * Due to the way a Git tree is organized the standard {@link TreeWalk} won't
+ * easily find a D/F conflict when merging two or more trees together. In the
+ * standard TreeWalk the file will be returned first, and then much later the
+ * directory will be returned. This makes it impossible for the application to
+ * efficiently detect and handle the conflict.
+ * <p>
+ * Using this walk implementation causes the directory to report earlier than
+ * usual, at the same time as the non-directory entry. This permits the
+ * application to handle the D/F conflict in a single step. The directory is
+ * returned only once, so it does not get returned later in the iteration.
+ * <p>
+ * When a D/F conflict is detected {@link TreeWalk#isSubtree()} will return true
+ * and {@link TreeWalk#enterSubtree()} will recurse into the subtree, no matter
+ * which iterator originally supplied the subtree.
+ * <p>
+ * Because conflicted directories report early, using this walk implementation
+ * to populate a {@link DirCacheBuilder} may cause the automatic resorting to
+ * run and fix the entry ordering.
+ * <p>
+ * This walk implementation requires more CPU to implement a look-ahead and a
+ * look-behind to merge a D/F pair together, or to skip a previously reported
+ * directory. In typical Git repositories the look-ahead cost is 0 and the
+ * look-behind doesn't trigger, as users tend not to create trees which contain
+ * both "foo" as a directory and "foo.c" as a file.
+ * <p>
+ * In the worst-case however several thousand look-ahead steps per walk step may
+ * be necessary, making the overhead quite significant. Since this worst-case
+ * should never happen this walk implementation has made the time/space tradeoff
+ * in favor of more-time/less-space, as that better suits the typical case.
+ */
+public class NameConflictTreeWalk extends TreeWalk {
+	private static final int TREE_MODE = FileMode.TREE.getBits();
+
+	/**
+	 * Create a new tree walker for a given repository.
+	 * 
+	 * @param repo
+	 *            the repository the walker will obtain data from.
+	 */
+	public NameConflictTreeWalk(final Repository repo) {
+		super(repo);
+	}
+
+	@Override
+	AbstractTreeIterator min() throws CorruptObjectException {
+		for (;;) {
+			final AbstractTreeIterator minRef = super.min();
+			if (minRef.eof())
+				return minRef;
+
+			if (FileMode.TREE.equals(minRef.mode)) {
+				if (skipEntry(minRef)) {
+					for (final AbstractTreeIterator t : trees) {
+						if (t.matches == minRef) {
+							t.next(1);
+							t.matches = null;
+						}
+					}
+					continue;
+				}
+				return minRef;
+			}
+
+			return combineDF(minRef);
+		}
+	}
+
+	private boolean skipEntry(final AbstractTreeIterator minRef)
+			throws CorruptObjectException {
+		// A tree D/F may have been handled earlier. We need to
+		// not report this path if it has already been reported.
+		//
+		for (final AbstractTreeIterator t : trees) {
+			if (t.matches == minRef || t.first())
+				continue;
+
+			int stepsBack = 0;
+			for (;;) {
+				stepsBack++;
+				t.back(1);
+
+				final int cmp = t.pathCompare(minRef, 0);
+				if (cmp == 0) {
+					// We have already seen this "$path" before. Skip it.
+					//
+					t.next(stepsBack);
+					return true;
+				} else if (cmp < 0 || t.first()) {
+					// We cannot find "$path" in t; it will never appear.
+					//
+					t.next(stepsBack);
+					break;
+				}
+			}
+		}
+
+		// We have never seen the current path before.
+		//
+		return false;
+	}
+
+	private AbstractTreeIterator combineDF(final AbstractTreeIterator minRef)
+			throws CorruptObjectException {
+		// Look for a possible D/F conflict forward in the tree(s)
+		// as there may be a "$path/" which matches "$path". Make
+		// such entries match this entry.
+		//
+		AbstractTreeIterator treeMatch = null;
+		for (final AbstractTreeIterator t : trees) {
+			if (t.matches == minRef || t.eof())
+				continue;
+
+			for (;;) {
+				final int cmp = t.pathCompare(minRef, TREE_MODE);
+				if (cmp < 0) {
+					// The "$path/" may still appear later.
+					//
+					t.matchShift++;
+					t.next(1);
+					if (t.eof()) {
+						t.back(t.matchShift);
+						t.matchShift = 0;
+						break;
+					}
+				} else if (cmp == 0) {
+					// We have a conflict match here.
+					//
+					t.matches = minRef;
+					treeMatch = t;
+					break;
+				} else {
+					// A conflict match is not possible.
+					//
+					if (t.matchShift != 0) {
+						t.back(t.matchShift);
+						t.matchShift = 0;
+					}
+					break;
+				}
+			}
+		}
+
+		if (treeMatch != null) {
+			// If we do have a conflict use one of the directory
+			// matching iterators instead of the file iterator.
+			// This way isSubtree is true and isRecursive works.
+			//
+			for (final AbstractTreeIterator t : trees)
+				if (t.matches == minRef)
+					t.matches = treeMatch;
+			return treeMatch;
+		}
+
+		return minRef;
+	}
+
+	@Override
+	void popEntriesEqual() throws CorruptObjectException {
+		final AbstractTreeIterator ch = currentHead;
+		for (int i = 0; i < trees.length; i++) {
+			final AbstractTreeIterator t = trees[i];
+			if (t.matches == ch) {
+				if (t.matchShift == 0)
+					t.next(1);
+				else {
+					t.back(t.matchShift);
+					t.matchShift = 0;
+				}
+				t.matches = null;
+			}
+		}
+	}
+
+	@Override
+	void skipEntriesEqual() throws CorruptObjectException {
+		final AbstractTreeIterator ch = currentHead;
+		for (int i = 0; i < trees.length; i++) {
+			final AbstractTreeIterator t = trees[i];
+			if (t.matches == ch) {
+				if (t.matchShift == 0)
+					t.skip();
+				else {
+					t.back(t.matchShift);
+					t.matchShift = 0;
+				}
+				t.matches = null;
+			}
+		}
+	}
+}
diff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java
index 10cdebd..7a09878 100644
--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java
+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java
@@ -143,7 +143,7 @@ public static TreeWalk forPath(final Repository db, final String path,
 
 	private TreeFilter filter;
 
-	private AbstractTreeIterator[] trees;
+	AbstractTreeIterator[] trees;
 
 	private boolean recursive;
 
@@ -151,7 +151,7 @@ public static TreeWalk forPath(final Repository db, final String path,
 
 	private boolean advance;
 
-	private AbstractTreeIterator currentHead;
+	AbstractTreeIterator currentHead;
 
 	/**
 	 * Create a new tree walker for a given repository.
@@ -275,6 +275,7 @@ public void reset(final ObjectId[] ids) throws MissingObjectException,
 					o = o.parent;
 				if (o instanceof CanonicalTreeParser) {
 					o.matches = null;
+					o.matchShift = 0;
 					((CanonicalTreeParser) o).reset(db, ids[i]);
 					r[i] = o;
 					continue;
@@ -338,6 +339,7 @@ public int addTree(final AbstractTreeIterator p)
 		System.arraycopy(trees, 0, newTrees, 0, n);
 		newTrees[n] = p;
 		p.matches = null;
+		p.matchShift = 0;
 
 		trees = newTrees;
 		return n;
@@ -621,7 +623,7 @@ public void enterSubtree() throws MissingObjectException,
 		System.arraycopy(tmp, 0, trees, 0, trees.length);
 	}
 
-	private AbstractTreeIterator min() {
+	AbstractTreeIterator min() throws CorruptObjectException {
 		int i = 0;
 		AbstractTreeIterator minRef = trees[i];
 		while (minRef.eof() && ++i < trees.length)
@@ -646,7 +648,7 @@ private AbstractTreeIterator min() {
 		return minRef;
 	}
 
-	private void popEntriesEqual() throws CorruptObjectException {
+	void popEntriesEqual() throws CorruptObjectException {
 		final AbstractTreeIterator ch = currentHead;
 		for (int i = 0; i < trees.length; i++) {
 			final AbstractTreeIterator t = trees[i];
@@ -657,7 +659,7 @@ private void popEntriesEqual() throws CorruptObjectException {
 		}
 	}
 
-	private void skipEntriesEqual() throws CorruptObjectException {
+	void skipEntriesEqual() throws CorruptObjectException {
 		final AbstractTreeIterator ch = currentHead;
 		for (int i = 0; i < trees.length; i++) {
 			final AbstractTreeIterator t = trees[i];
-- 
1.6.0.87.g2858d

[JGIT PATCH 14/14] Add test case for NameConflictTreeWalk

[Shawn O. Pearce]

Signed-off-by: Shawn O. Pearce <spearce@spearce.org>
---
 .../jgit/treewalk/NameConflictTreeWalkTest.java    |  205 ++++++++++++++++++++
 1 files changed, 205 insertions(+), 0 deletions(-)
 create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/treewalk/NameConflictTreeWalkTest.java

diff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/treewalk/NameConflictTreeWalkTest.java b/org.spearce.jgit.test/tst/org/spearce/jgit/treewalk/NameConflictTreeWalkTest.java
new file mode 100644
index 0000000..8ab7f93
--- /dev/null
+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/treewalk/NameConflictTreeWalkTest.java
@@ -0,0 +1,205 @@
+/*
+ * Copyright (C) 2008, Google Inc.
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above
+ *   copyright notice, this list of conditions and the following
+ *   disclaimer in the documentation and/or other materials provided
+ *   with the distribution.
+ *
+ * - Neither the name of the Git Development Community nor the
+ *   names of its contributors may be used to endorse or promote
+ *   products derived from this software without specific prior
+ *   written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
+ * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+package org.spearce.jgit.treewalk;
+
+import java.io.ByteArrayInputStream;
+
+import org.spearce.jgit.dircache.DirCache;
+import org.spearce.jgit.dircache.DirCacheBuilder;
+import org.spearce.jgit.dircache.DirCacheEntry;
+import org.spearce.jgit.dircache.DirCacheIterator;
+import org.spearce.jgit.lib.Constants;
+import org.spearce.jgit.lib.FileMode;
+import org.spearce.jgit.lib.ObjectWriter;
+import org.spearce.jgit.lib.RepositoryTestCase;
+
+public class NameConflictTreeWalkTest extends RepositoryTestCase {
+	private static final FileMode TREE = FileMode.TREE;
+
+	private static final FileMode SYMLINK = FileMode.SYMLINK;
+
+	private static final FileMode MISSING = FileMode.MISSING;
+
+	private static final FileMode REGULAR_FILE = FileMode.REGULAR_FILE;
+
+	private static final FileMode EXECUTABLE_FILE = FileMode.EXECUTABLE_FILE;
+
+	public void testNoDF_NoGap() throws Exception {
+		final DirCache tree0 = DirCache.read(db);
+		final DirCache tree1 = DirCache.read(db);
+		{
+			final DirCacheBuilder b0 = tree0.builder();
+			final DirCacheBuilder b1 = tree1.builder();
+
+			b0.add(makeEntry("a", REGULAR_FILE));
+			b0.add(makeEntry("a.b", EXECUTABLE_FILE));
+			b1.add(makeEntry("a/b", REGULAR_FILE));
+			b0.add(makeEntry("a0b", SYMLINK));
+
+			b0.finish();
+			b1.finish();
+			assertEquals(3, tree0.getEntryCount());
+			assertEquals(1, tree1.getEntryCount());
+		}
+
+		final TreeWalk tw = new TreeWalk(db);
+		tw.reset();
+		tw.addTree(new DirCacheIterator(tree0));
+		tw.addTree(new DirCacheIterator(tree1));
+
+		assertModes("a", REGULAR_FILE, MISSING, tw);
+		assertModes("a.b", EXECUTABLE_FILE, MISSING, tw);
+		assertModes("a", MISSING, TREE, tw);
+		tw.enterSubtree();
+		assertModes("a/b", MISSING, REGULAR_FILE, tw);
+		assertModes("a0b", SYMLINK, MISSING, tw);
+	}
+
+	public void testDF_NoGap() throws Exception {
+		final DirCache tree0 = DirCache.read(db);
+		final DirCache tree1 = DirCache.read(db);
+		{
+			final DirCacheBuilder b0 = tree0.builder();
+			final DirCacheBuilder b1 = tree1.builder();
+
+			b0.add(makeEntry("a", REGULAR_FILE));
+			b0.add(makeEntry("a.b", EXECUTABLE_FILE));
+			b1.add(makeEntry("a/b", REGULAR_FILE));
+			b0.add(makeEntry("a0b", SYMLINK));
+
+			b0.finish();
+			b1.finish();
+			assertEquals(3, tree0.getEntryCount());
+			assertEquals(1, tree1.getEntryCount());
+		}
+
+		final NameConflictTreeWalk tw = new NameConflictTreeWalk(db);
+		tw.reset();
+		tw.addTree(new DirCacheIterator(tree0));
+		tw.addTree(new DirCacheIterator(tree1));
+
+		assertModes("a", REGULAR_FILE, TREE, tw);
+		assertTrue(tw.isSubtree());
+		tw.enterSubtree();
+		assertModes("a/b", MISSING, REGULAR_FILE, tw);
+		assertModes("a.b", EXECUTABLE_FILE, MISSING, tw);
+		assertModes("a0b", SYMLINK, MISSING, tw);
+	}
+
+	public void testDF_GapByOne() throws Exception {
+		final DirCache tree0 = DirCache.read(db);
+		final DirCache tree1 = DirCache.read(db);
+		{
+			final DirCacheBuilder b0 = tree0.builder();
+			final DirCacheBuilder b1 = tree1.builder();
+
+			b0.add(makeEntry("a", REGULAR_FILE));
+			b0.add(makeEntry("a.b", EXECUTABLE_FILE));
+			b1.add(makeEntry("a.b", EXECUTABLE_FILE));
+			b1.add(makeEntry("a/b", REGULAR_FILE));
+			b0.add(makeEntry("a0b", SYMLINK));
+
+			b0.finish();
+			b1.finish();
+			assertEquals(3, tree0.getEntryCount());
+			assertEquals(2, tree1.getEntryCount());
+		}
+
+		final NameConflictTreeWalk tw = new NameConflictTreeWalk(db);
+		tw.reset();
+		tw.addTree(new DirCacheIterator(tree0));
+		tw.addTree(new DirCacheIterator(tree1));
+
+		assertModes("a", REGULAR_FILE, TREE, tw);
+		assertTrue(tw.isSubtree());
+		tw.enterSubtree();
+		assertModes("a/b", MISSING, REGULAR_FILE, tw);
+		assertModes("a.b", EXECUTABLE_FILE, EXECUTABLE_FILE, tw);
+		assertModes("a0b", SYMLINK, MISSING, tw);
+	}
+
+	public void testDF_SkipsSeenSubtree() throws Exception {
+		final DirCache tree0 = DirCache.read(db);
+		final DirCache tree1 = DirCache.read(db);
+		{
+			final DirCacheBuilder b0 = tree0.builder();
+			final DirCacheBuilder b1 = tree1.builder();
+
+			b0.add(makeEntry("a", REGULAR_FILE));
+			b1.add(makeEntry("a.b", EXECUTABLE_FILE));
+			b1.add(makeEntry("a/b", REGULAR_FILE));
+			b0.add(makeEntry("a0b", SYMLINK));
+			b1.add(makeEntry("a0b", SYMLINK));
+
+			b0.finish();
+			b1.finish();
+			assertEquals(2, tree0.getEntryCount());
+			assertEquals(3, tree1.getEntryCount());
+		}
+
+		final NameConflictTreeWalk tw = new NameConflictTreeWalk(db);
+		tw.reset();
+		tw.addTree(new DirCacheIterator(tree0));
+		tw.addTree(new DirCacheIterator(tree1));
+
+		assertModes("a", REGULAR_FILE, TREE, tw);
+		assertTrue(tw.isSubtree());
+		tw.enterSubtree();
+		assertModes("a/b", MISSING, REGULAR_FILE, tw);
+		assertModes("a.b", MISSING, EXECUTABLE_FILE, tw);
+		assertModes("a0b", SYMLINK, SYMLINK, tw);
+	}
+
+	private DirCacheEntry makeEntry(final String path, final FileMode mode)
+			throws Exception {
+		final byte[] pathBytes = Constants.encode(path);
+		final DirCacheEntry ent = new DirCacheEntry(path);
+		ent.setFileMode(mode);
+		ent.setObjectId(new ObjectWriter(db).computeBlobSha1(pathBytes.length,
+				new ByteArrayInputStream(pathBytes)));
+		return ent;
+	}
+
+	private static void assertModes(final String path, final FileMode mode0,
+			final FileMode mode1, final TreeWalk tw) throws Exception {
+		assertTrue("has " + path, tw.next());
+		assertEquals(path, tw.getPathString());
+		assertEquals(mode0, tw.getFileMode(0));
+		assertEquals(mode1, tw.getFileMode(1));
+	}
+}
-- 
1.6.0.87.g2858d

Re: [JGIT PATCH 01/14] Detect path names which overflow the name length field in the index

[Junio C Hamano]

"Shawn O. Pearce" <spearce@spearce.org> writes:

> C Git allows a path name to be longer than 4095 bytes by storing 4095
> into the path name length field within flags and then searching for a
> null terminator at the end of the path name, instead of relying on the
> length indicatior.

This reminds me.

In the longer term, we should make this "CE_NAMEMASK gives the real length
for sane names but otherwise we need to count" merely a property of the
on-disk index structure.  In-core index should gain a new ce_namelen field
that records the real name (even when it is longer than the mask would
permit).  IOW, the knowledge of CE_NAMEMASK should be confined to
read_index_from() and ce_write_entry().

I expect this to be a relatively easy janitor project; hint, hint...

Re: [JGIT PATCH 01/14] Detect path names which overflow the name length field in the index

[Robin Rosenberg]

tisdagen den 19 augusti 2008 01.53.09 skrev Shawn O. Pearce:
> C Git allows a path name to be longer than 4095 bytes by storing 4095
> into the path name length field within flags and then searching for a
> null terminator at the end of the path name, instead of relying on the
> length indicatior.  We cannot do this (easily) from an InputStream so
> we are currently going to just abort with an exception if we find such
> an extremely long path name.

What's hard? read bytes until we get a 0 shouldn't be hard. It has no
special meaning to an InputStream.

-- robin

Re: [JGIT PATCH 01/14] Detect path names which overflow the name length field in the index

[Shawn O. Pearce]

Robin Rosenberg <robin.rosenberg.lists@dewire.com> wrote:
> tisdagen den 19 augusti 2008 01.53.09 skrev Shawn O. Pearce:
> > C Git allows a path name to be longer than 4095 bytes by storing 4095
> > into the path name length field within flags and then searching for a
> > null terminator at the end of the path name, instead of relying on the
> > length indicatior.  We cannot do this (easily) from an InputStream so
> > we are currently going to just abort with an exception if we find such
> > an extremely long path name.
> 
> What's hard? read bytes until we get a 0 shouldn't be hard. It has no
> special meaning to an InputStream.

Yea, I forgot this stream is a BufferedInputStream and that pulling
bytes one at a time isn't that much of a problem.  I'll rework this
patch and post a v2 today.

-- 
Shawn.

Re: [JGIT PATCH 00/14] TreeWalk D/F conflict detection

[David Woodhouse]

On Mon, 2008-08-18 at 16:53 -0700, Shawn O. Pearce wrote:
> This series is about fixing the "mistake" in Git trees where
> subtrees sort as through their name is "path/" and not "path".

Er, really? Does that mean this commit is broken, then?

http://git.kernel.org/?p=linux/kernel/git/dwmw2/misc-git-hacks.git;a=commitdiff;h=fc1b73da

I shouldn't need to know that -- I'd _really_ like a version of
'git-hash-object -t tree' which validates and sorts its input for me.
And maybe even takes input in _text_ form, so I don't have to convert
the sha1 to binary.

-- 
David Woodhouse                            Open Source Technology Centre
David.Woodhouse@intel.com                              Intel Corporation

Re: [JGIT PATCH 00/14] TreeWalk D/F conflict detection

[Shawn O. Pearce]

David Woodhouse <dwmw2@infradead.org> wrote:
> On Mon, 2008-08-18 at 16:53 -0700, Shawn O. Pearce wrote:
> > This series is about fixing the "mistake" in Git trees where
> > subtrees sort as through their name is "path/" and not "path".
> 
> Er, really? Does that mean this commit is broken, then?
> 
> http://git.kernel.org/?p=linux/kernel/git/dwmw2/misc-git-hacks.git;a=commitdiff;h=fc1b73da

Yes, that is broken.
 
> I shouldn't need to know that -- I'd _really_ like a version of
> 'git-hash-object -t tree' which validates and sorts its input for me.
> And maybe even takes input in _text_ form, so I don't have to convert
> the sha1 to binary.

Try `git mktree` instead.  It uses a text form, and it corrects
the sorting for you.  Though funny names that contain an LF may be
harder to send to mktree.

-- 
Shawn.

[JGIT PATCH 00/14] TreeWalk D/F conflict detection

[Shawn O. Pearce]

This series is about fixing the "mistake" in Git trees where
subtrees sort as through their name is "path/" and not "path".

Within a TreeWalk this is a problem because the tree contents:

    Tree 1     Tree 2
  ------------------------
    100644 a
               100644 a.c
               040000 a
    100644 b

needs to merge together both "a" paths from tree 1 and tree 2, but
these appear at different points in time when we merge-sort the two
trees together.

We use an infinite look-ahead and look-behind to identify these cases
and make the iteration look like this instead:

    Tree 1     Tree 2
  ------------------------
    100644 a   040000 a
               100644 a.c
    100644 b

which allows the application to handle the D/F conflict in a single
step, even though the contents of "a" may now be out-of-order within
the DirCache.  Fortunately DirCacheBuilder can automatically fix this
sort of ordering problem.


Shawn O. Pearce (14):
  Detect path names which overflow the name length field in the index
  Fix NB.decodeUInt16 to correctly handle the high byte
  Add test cases for NB.encode and NB.decode family of routines
  Fix DirCache's skip over null byte padding when reading a DIRC file
  Fix usage of assertEquals in DirCacheIteratorTest
  Refactor AbstractTreeIterator.pathCompare to force another mode
  Micro-optimize AbstractTreeIterator.pathCompare
  Optimize path comparsion within subtrees during TreeWalk
  Refactor AbstractTreeIterator semantics to start on first entry
  Make all AbstractTreeIterator implementations bi-directional
  Expose beginning of iterator indication from AbstractTreeIterator
  Allow application code to set ObjectIds in DirCacheEntry
  Create NameConflictTreeWalk to transparently detect D/F conflicts
  Add test case for NameConflictTreeWalk

 .../spearce/egit/core/ContainerTreeIterator.java   |    9 +-
 .../jgit/dircache/DirCacheBuilderIteratorTest.java |    2 +-
 .../jgit/dircache/DirCacheIteratorTest.java        |   28 +-
 .../jgit/treewalk/CanonicalTreeParserTest.java     |  261 ++++++++++++++++
 .../jgit/treewalk/NameConflictTreeWalkTest.java    |  205 ++++++++++++
 .../tst/org/spearce/jgit/util/NBTest.java          |  328 ++++++++++++++++++++
 .../src/org/spearce/jgit/dircache/DirCache.java    |    2 +-
 .../jgit/dircache/DirCacheBuildIterator.java       |    9 +-
 .../org/spearce/jgit/dircache/DirCacheEntry.java   |   41 +++-
 .../spearce/jgit/dircache/DirCacheIterator.java    |   84 +++--
 .../jgit/treewalk/AbstractTreeIterator.java        |  129 +++++---
 .../spearce/jgit/treewalk/CanonicalTreeParser.java |   94 +++++-
 .../spearce/jgit/treewalk/EmptyTreeIterator.java   |   12 +-
 .../spearce/jgit/treewalk/FileTreeIterator.java    |    5 +-
 .../jgit/treewalk/NameConflictTreeWalk.java        |  237 ++++++++++++++
 .../src/org/spearce/jgit/treewalk/TreeWalk.java    |   18 +-
 .../spearce/jgit/treewalk/WorkingTreeIterator.java |  132 ++++-----
 org.spearce.jgit/src/org/spearce/jgit/util/NB.java |   29 ++-
 18 files changed, 1418 insertions(+), 207 deletions(-)
 create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/treewalk/CanonicalTreeParserTest.java
 create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/treewalk/NameConflictTreeWalkTest.java
 create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/util/NBTest.java
 create mode 100644 org.spearce.jgit/src/org/spearce/jgit/treewalk/NameConflictTreeWalk.java

Re: [JGIT PATCH 00/14] TreeWalk D/F conflict detection

[Shawn O. Pearce]

Sorry about that, my git-send-email directory had this cover letter
laying around in it from last time.  There is no series, I only meant
to post the single patch "Support path names longer than 4095...".

> Shawn O. Pearce (14):
>   Detect path names which overflow the name length field in the index
>   Fix NB.decodeUInt16 to correctly handle the high byte
>   Add test cases for NB.encode and NB.decode family of routines
>   Fix DirCache's skip over null byte padding when reading a DIRC file
>   Fix usage of assertEquals in DirCacheIteratorTest
>   Refactor AbstractTreeIterator.pathCompare to force another mode
>   Micro-optimize AbstractTreeIterator.pathCompare
>   Optimize path comparsion within subtrees during TreeWalk
>   Refactor AbstractTreeIterator semantics to start on first entry
>   Make all AbstractTreeIterator implementations bi-directional
>   Expose beginning of iterator indication from AbstractTreeIterator
>   Allow application code to set ObjectIds in DirCacheEntry
>   Create NameConflictTreeWalk to transparently detect D/F conflicts
>   Add test case for NameConflictTreeWalk
...
>  18 files changed, 1418 insertions(+), 207 deletions(-)

-- 
Shawn.