{"thread":{"id":"15078","subject":"[JGIT PATCH 01/14] Detect path names which overflow the name length field in the index","startedAt":"2008-08-18T23:53:08Z","lastAt":"2008-08-19T19:57:35Z","messageCount":20,"participants":["Shawn O. Pearce","Junio C Hamano","David Woodhouse","Robin Rosenberg"],"isPatch":true,"patchVersion":1,"patchTotal":14},"messages":[{"id":"87599","messageId":"1219103602-32222-1-git-send-email-spearce@spearce.org","threadId":"15078","inReplyTo":null,"subject":"[JGIT PATCH 00/14] TreeWalk D/F conflict detection","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-08-18T23:53:08Z","receivedAt":"2008-08-18T23:53:08Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"This series is about fixing the \"mistake\" in Git trees where\nsubtrees sort as through their name is \"path/\" and not \"path\".\n\nWithin a TreeWalk this is a problem because the tree contents:\n\n Tree 1 Tree 2\n ------------------------\n 100644 a\n 100644 a.c\n 040000 a\n 100644 b\n\nneeds to merge together both \"a\" paths from tree 1 and tree 2, but\nthese appear at different points in time when we merge-sort the two\ntrees together.\n\nWe use an infinite look-ahead and look-behind to identify these cases\nand make the iteration look like this instead:\n\n Tree 1 Tree 2\n ------------------------\n 100644 a 040000 a\n 100644 a.c\n 100644 b\n\nwhich allows the application to handle the D/F conflict in a single\nstep, even though the contents of \"a\" may now be out-of-order within\nthe DirCache. Fortunately DirCacheBuilder can automatically fix this\nsort of ordering problem.\n\n\nShawn O. Pearce (14):\n Detect path names which overflow the name length field in the index\n Fix NB.decodeUInt16 to correctly handle the high byte\n Add test cases for NB.encode and NB.decode family of routines\n Fix DirCache's skip over null byte padding when reading a DIRC file\n Fix usage of assertEquals in DirCacheIteratorTest\n Refactor AbstractTreeIterator.pathCompare to force another mode\n Micro-optimize AbstractTreeIterator.pathCompare\n Optimize path comparsion within subtrees during TreeWalk\n Refactor AbstractTreeIterator semantics to start on first entry\n Make all AbstractTreeIterator implementations bi-directional\n Expose beginning of iterator indication from AbstractTreeIterator\n Allow application code to set ObjectIds in DirCacheEntry\n Create NameConflictTreeWalk to transparently detect D/F conflicts\n Add test case for NameConflictTreeWalk\n\n .../spearce/egit/core/ContainerTreeIterator.java | 9 +-\n .../jgit/dircache/DirCacheBuilderIteratorTest.java | 2 +-\n .../jgit/dircache/DirCacheIteratorTest.java | 28 +-\n .../jgit/treewalk/CanonicalTreeParserTest.java | 261 ++++++++++++++++\n .../jgit/treewalk/NameConflictTreeWalkTest.java | 205 ++++++++++++\n .../tst/org/spearce/jgit/util/NBTest.java | 328 ++++++++++++++++++++\n .../src/org/spearce/jgit/dircache/DirCache.java | 2 +-\n .../jgit/dircache/DirCacheBuildIterator.java | 9 +-\n .../org/spearce/jgit/dircache/DirCacheEntry.java | 41 +++-\n .../spearce/jgit/dircache/DirCacheIterator.java | 84 +++--\n .../jgit/treewalk/AbstractTreeIterator.java | 129 +++++---\n .../spearce/jgit/treewalk/CanonicalTreeParser.java | 94 +++++-\n .../spearce/jgit/treewalk/EmptyTreeIterator.java | 12 +-\n .../spearce/jgit/treewalk/FileTreeIterator.java | 5 +-\n .../jgit/treewalk/NameConflictTreeWalk.java | 237 ++++++++++++++\n .../src/org/spearce/jgit/treewalk/TreeWalk.java | 18 +-\n .../spearce/jgit/treewalk/WorkingTreeIterator.java | 132 ++++-----\n org.spearce.jgit/src/org/spearce/jgit/util/NB.java | 29 ++-\n 18 files changed, 1418 insertions(+), 207 deletions(-)\n create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/treewalk/CanonicalTreeParserTest.java\n create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/treewalk/NameConflictTreeWalkTest.java\n create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/util/NBTest.java\n create mode 100644 org.spearce.jgit/src/org/spearce/jgit/treewalk/NameConflictTreeWalk.java\n"},{"id":"87598","messageId":"1219103602-32222-2-git-send-email-spearce@spearce.org","threadId":"15078","inReplyTo":"1219103602-32222-1-git-send-email-spearce@spearce.org","subject":"[JGIT PATCH 01/14] Detect path names which overflow the name length field in the index","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-08-18T23:53:09Z","receivedAt":"2008-08-18T23:53:09Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"C Git allows a path name to be longer than 4095 bytes by storing 4095\ninto the path name length field within flags and then searching for a\nnull terminator at the end of the path name, instead of relying on the\nlength indicatior. We cannot do this (easily) from an InputStream so\nwe are currently going to just abort with an exception if we find such\nan extremely long path name.\n\nSigned-off-by: Shawn O. Pearce \n---\n .../org/spearce/jgit/dircache/DirCacheEntry.java | 13 ++++++++++---\n 1 files changed, 10 insertions(+), 3 deletions(-)\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheEntry.java b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheEntry.java\nindex c481e43..bcf5596 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheEntry.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheEntry.java\n@@ -81,6 +81,9 @@\n \n \tprivate static final int P_FLAGS = 60;\n \n+\t/** Mask applied to data in {@link #P_FLAGS} to get the name length. */\n+\tprivate static final int NAME_MASK = 0xfff;\n+\n \tstatic final int INFO_LEN = 62;\n \n \tprivate static final int ASSUME_VALID = 0x80;\n@@ -101,7 +104,9 @@ DirCacheEntry(final byte[] sharedInfo, final int infoAt,\n \n \t\tNB.readFully(in, info, infoOffset, INFO_LEN);\n \n-\t\tint pathLen = NB.decodeUInt16(info, infoOffset + P_FLAGS) & 0xfff;\n+\t\tint pathLen = NB.decodeUInt16(info, infoOffset + P_FLAGS) & NAME_MASK;\n+\t\tif (pathLen == NAME_MASK)\n+\t\t\tthrow new IOException(\"Path name too long for jgit\");\n \t\tpath = new byte[pathLen];\n \t\tNB.readFully(in, path, 0, pathLen);\n \n@@ -135,6 +140,8 @@ public DirCacheEntry(final byte[] newPath) {\n \t\tinfoOffset = 0;\n \n \t\tpath = newPath;\n+\t\tif (path.length >= NAME_MASK)\n+\t\t\tthrow new IllegalArgumentException(\"Path name too long for jgit\");\n \t\tNB.encodeInt16(info, infoOffset + P_FLAGS, path.length);\n \t}\n \n@@ -364,10 +371,10 @@ public String getPathString() {\n \t * the entry to copy ObjectId and meta fields from.\n \t */\n \tpublic void copyMetaData(final DirCacheEntry src) {\n-\t\tfinal int pLen = NB.decodeUInt16(info, infoOffset + P_FLAGS) & 0xfff;\n+\t\tfinal int pLen = NB.decodeUInt16(info, infoOffset + P_FLAGS) & NAME_MASK;\n \t\tSystem.arraycopy(src.info, src.infoOffset, info, infoOffset, INFO_LEN);\n \t\tNB.encodeInt16(info, infoOffset + P_FLAGS, pLen\n-\t\t\t\t| NB.decodeUInt16(info, infoOffset + P_FLAGS) & ~0xfff);\n+\t\t\t\t| NB.decodeUInt16(info, infoOffset + P_FLAGS) & ~NAME_MASK);\n \t}\n \n \tprivate long decodeTS(final int pIdx) {\n-- \n1.6.0.87.g2858d\n"},{"id":"87600","messageId":"1219103602-32222-3-git-send-email-spearce@spearce.org","threadId":"15078","inReplyTo":"1219103602-32222-2-git-send-email-spearce@spearce.org","subject":"[JGIT PATCH 02/14] Fix NB.decodeUInt16 to correctly handle the high byte","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-08-18T23:53:10Z","receivedAt":"2008-08-18T23:53:10Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Our decodeUInt16 method was buggy and always cleared the high byte\nof the pair. This meant we always lost the upper 8 bits when we\nread in a 16 bit unsigned integer, possibly causing us to misread\nthe data associated with that pair.\n\nSigned-off-by: Shawn O. Pearce \n---\n org.spearce.jgit/src/org/spearce/jgit/util/NB.java | 2 +-\n 1 files changed, 1 insertions(+), 1 deletions(-)\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/util/NB.java b/org.spearce.jgit/src/org/spearce/jgit/util/NB.java\nindex c6176f8..fa13354 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/util/NB.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/util/NB.java\n@@ -102,7 +102,7 @@ public static int compareUInt32(final int a, final int b) {\n \t * @return unsigned integer value that matches the 16 bits read.\n \t */\n \tpublic static int decodeUInt16(final byte[] intbuf, final int offset) {\n-\t\tint r = (intbuf[offset] << 8) & 0xff;\n+\t\tint r = (intbuf[offset] & 0xff) << 8;\n \t\treturn r | (intbuf[offset + 1] & 0xff);\n \t}\n \n-- \n1.6.0.87.g2858d\n"},{"id":"87601","messageId":"1219103602-32222-4-git-send-email-spearce@spearce.org","threadId":"15078","inReplyTo":"1219103602-32222-3-git-send-email-spearce@spearce.org","subject":"[JGIT PATCH 03/14] Add test cases for NB.encode and NB.decode family of routines","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-08-18T23:53:11Z","receivedAt":"2008-08-18T23:53:11Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"We really need to ensure these methods work correctly, and since\nwe just suffered from a bug in NB.decodeUInt16 we now have a set\nof test cases for the corner conditions of each encode and decode\nmethod pair we support.\n\nSigned-off-by: Shawn O. Pearce \n---\n .../tst/org/spearce/jgit/util/NBTest.java | 328 ++++++++++++++++++++\n 1 files changed, 328 insertions(+), 0 deletions(-)\n create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/util/NBTest.java\n\ndiff --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\nnew file mode 100644\nindex 0000000..217db7f\n--- /dev/null\n+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/util/NBTest.java\n@@ -0,0 +1,328 @@\n+/*\n+ * Copyright (C) 2008, Google Inc.\n+ *\n+ * All rights reserved.\n+ *\n+ * Redistribution and use in source and binary forms, with or\n+ * without modification, are permitted provided that the following\n+ * conditions are met:\n+ *\n+ * - Redistributions of source code must retain the above copyright\n+ * notice, this list of conditions and the following disclaimer.\n+ *\n+ * - Redistributions in binary form must reproduce the above\n+ * copyright notice, this list of conditions and the following\n+ * disclaimer in the documentation and/or other materials provided\n+ * with the distribution.\n+ *\n+ * - Neither the name of the Git Development Community nor the\n+ * names of its contributors may be used to endorse or promote\n+ * products derived from this software without specific prior\n+ * written permission.\n+ *\n+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND\n+ * CONTRIBUTORS \"AS IS\" AND ANY EXPRESS OR IMPLIED WARRANTIES,\n+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES\n+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE\n+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR\n+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,\n+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT\n+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;\n+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER\n+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,\n+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)\n+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF\n+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.\n+ */\n+\n+package org.spearce.jgit.util;\n+\n+import junit.framework.TestCase;\n+\n+public class NBTest extends TestCase {\n+\tpublic void testCompareUInt32() {\n+\t\tassertTrue(NB.compareUInt32(0, 0) == 0);\n+\t\tassertTrue(NB.compareUInt32(1, 0) > 0);\n+\t\tassertTrue(NB.compareUInt32(0, 1) < 0);\n+\t\tassertTrue(NB.compareUInt32(-1, 0) > 0);\n+\t\tassertTrue(NB.compareUInt32(0, -1) < 0);\n+\t\tassertTrue(NB.compareUInt32(-1, 1) > 0);\n+\t\tassertTrue(NB.compareUInt32(1, -1) < 0);\n+\t}\n+\n+\tpublic void testDecodeUInt16() {\n+\t\tassertEquals(0, NB.decodeUInt16(b(0, 0), 0));\n+\t\tassertEquals(0, NB.decodeUInt16(padb(3, 0, 0), 3));\n+\n+\t\tassertEquals(3, NB.decodeUInt16(b(0, 3), 0));\n+\t\tassertEquals(3, NB.decodeUInt16(padb(3, 0, 3), 3));\n+\n+\t\tassertEquals(0xde03, NB.decodeUInt16(b(0xde, 3), 0));\n+\t\tassertEquals(0xde03, NB.decodeUInt16(padb(3, 0xde, 3), 3));\n+\n+\t\tassertEquals(0x03de, NB.decodeUInt16(b(3, 0xde), 0));\n+\t\tassertEquals(0x03de, NB.decodeUInt16(padb(3, 3, 0xde), 3));\n+\n+\t\tassertEquals(0xffff, NB.decodeUInt16(b(0xff, 0xff), 0));\n+\t\tassertEquals(0xffff, NB.decodeUInt16(padb(3, 0xff, 0xff), 3));\n+\t}\n+\n+\tpublic void testDecodeInt32() {\n+\t\tassertEquals(0, NB.decodeInt32(b(0, 0, 0, 0), 0));\n+\t\tassertEquals(0, NB.decodeInt32(padb(3, 0, 0, 0, 0), 3));\n+\n+\t\tassertEquals(3, NB.decodeInt32(b(0, 0, 0, 3), 0));\n+\t\tassertEquals(3, NB.decodeInt32(padb(3, 0, 0, 0, 3), 3));\n+\n+\t\tassertEquals(0xdeadbeef, NB.decodeInt32(b(0xde, 0xad, 0xbe, 0xef), 0));\n+\t\tassertEquals(0xdeadbeef, NB.decodeInt32(\n+\t\t\t\tpadb(3, 0xde, 0xad, 0xbe, 0xef), 3));\n+\n+\t\tassertEquals(0x0310adef, NB.decodeInt32(b(0x03, 0x10, 0xad, 0xef), 0));\n+\t\tassertEquals(0x0310adef, NB.decodeInt32(\n+\t\t\t\tpadb(3, 0x03, 0x10, 0xad, 0xef), 3));\n+\n+\t\tassertEquals(0xffffffff, NB.decodeInt32(b(0xff, 0xff, 0xff, 0xff), 0));\n+\t\tassertEquals(0xffffffff, NB.decodeInt32(\n+\t\t\t\tpadb(3, 0xff, 0xff, 0xff, 0xff), 3));\n+\t}\n+\n+\tpublic void testDecodeUInt32() {\n+\t\tassertEquals(0L, NB.decodeUInt32(b(0, 0, 0, 0), 0));\n+\t\tassertEquals(0L, NB.decodeUInt32(padb(3, 0, 0, 0, 0), 3));\n+\n+\t\tassertEquals(3L, NB.decodeUInt32(b(0, 0, 0, 3), 0));\n+\t\tassertEquals(3L, NB.decodeUInt32(padb(3, 0, 0, 0, 3), 3));\n+\n+\t\tassertEquals(0xdeadbeefL, NB.decodeUInt32(b(0xde, 0xad, 0xbe, 0xef), 0));\n+\t\tassertEquals(0xdeadbeefL, NB.decodeUInt32(padb(3, 0xde, 0xad, 0xbe,\n+\t\t\t\t0xef), 3));\n+\n+\t\tassertEquals(0x0310adefL, NB.decodeUInt32(b(0x03, 0x10, 0xad, 0xef), 0));\n+\t\tassertEquals(0x0310adefL, NB.decodeUInt32(padb(3, 0x03, 0x10, 0xad,\n+\t\t\t\t0xef), 3));\n+\n+\t\tassertEquals(0xffffffffL, NB.decodeUInt32(b(0xff, 0xff, 0xff, 0xff), 0));\n+\t\tassertEquals(0xffffffffL, NB.decodeUInt32(padb(3, 0xff, 0xff, 0xff,\n+\t\t\t\t0xff), 3));\n+\t}\n+\n+\tpublic void testDecodeUInt64() {\n+\t\tassertEquals(0L, NB.decodeUInt64(b(0, 0, 0, 0, 0, 0, 0, 0), 0));\n+\t\tassertEquals(0L, NB.decodeUInt64(padb(3, 0, 0, 0, 0, 0, 0, 0, 0), 3));\n+\n+\t\tassertEquals(3L, NB.decodeUInt64(b(0, 0, 0, 0, 0, 0, 0, 3), 0));\n+\t\tassertEquals(3L, NB.decodeUInt64(padb(3, 0, 0, 0, 0, 0, 0, 0, 3), 3));\n+\n+\t\tassertEquals(0xdeadbeefL, NB.decodeUInt64(b(0, 0, 0, 0, 0xde, 0xad,\n+\t\t\t\t0xbe, 0xef), 0));\n+\t\tassertEquals(0xdeadbeefL, NB.decodeUInt64(padb(3, 0, 0, 0, 0, 0xde,\n+\t\t\t\t0xad, 0xbe, 0xef), 3));\n+\n+\t\tassertEquals(0x0310adefL, NB.decodeUInt64(b(0, 0, 0, 0, 0x03, 0x10,\n+\t\t\t\t0xad, 0xef), 0));\n+\t\tassertEquals(0x0310adefL, NB.decodeUInt64(padb(3, 0, 0, 0, 0, 0x03,\n+\t\t\t\t0x10, 0xad, 0xef), 3));\n+\n+\t\tassertEquals(0xc0ffee78deadbeefL, NB.decodeUInt64(b(0xc0, 0xff, 0xee,\n+\t\t\t\t0x78, 0xde, 0xad, 0xbe, 0xef), 0));\n+\t\tassertEquals(0xc0ffee78deadbeefL, NB.decodeUInt64(padb(3, 0xc0, 0xff,\n+\t\t\t\t0xee, 0x78, 0xde, 0xad, 0xbe, 0xef), 3));\n+\n+\t\tassertEquals(0x00000000ffffffffL, NB.decodeUInt64(b(0, 0, 0, 0, 0xff,\n+\t\t\t\t0xff, 0xff, 0xff), 0));\n+\t\tassertEquals(0x00000000ffffffffL, NB.decodeUInt64(padb(3, 0, 0, 0, 0,\n+\t\t\t\t0xff, 0xff, 0xff, 0xff), 3));\n+\t\tassertEquals(0xffffffffffffffffL, NB.decodeUInt64(b(0xff, 0xff, 0xff,\n+\t\t\t\t0xff, 0xff, 0xff, 0xff, 0xff), 0));\n+\t\tassertEquals(0xffffffffffffffffL, NB.decodeUInt64(padb(3, 0xff, 0xff,\n+\t\t\t\t0xff, 0xff, 0xff, 0xff, 0xff, 0xff), 3));\n+\t}\n+\n+\tpublic void testEncodeInt16() {\n+\t\tfinal byte[] out = new byte[16];\n+\n+\t\tprepareOutput(out);\n+\t\tNB.encodeInt16(out, 0, 0);\n+\t\tassertOutput(b(0, 0), out, 0);\n+\n+\t\tprepareOutput(out);\n+\t\tNB.encodeInt16(out, 3, 0);\n+\t\tassertOutput(b(0, 0), out, 3);\n+\n+\t\tprepareOutput(out);\n+\t\tNB.encodeInt16(out, 0, 3);\n+\t\tassertOutput(b(0, 3), out, 0);\n+\n+\t\tprepareOutput(out);\n+\t\tNB.encodeInt16(out, 3, 3);\n+\t\tassertOutput(b(0, 3), out, 3);\n+\n+\t\tprepareOutput(out);\n+\t\tNB.encodeInt16(out, 0, 0xdeac);\n+\t\tassertOutput(b(0xde, 0xac), out, 0);\n+\n+\t\tprepareOutput(out);\n+\t\tNB.encodeInt16(out, 3, 0xdeac);\n+\t\tassertOutput(b(0xde, 0xac), out, 3);\n+\n+\t\tprepareOutput(out);\n+\t\tNB.encodeInt16(out, 3, -1);\n+\t\tassertOutput(b(0xff, 0xff), out, 3);\n+\t}\n+\n+\tpublic void testEncodeInt32() {\n+\t\tfinal byte[] out = new byte[16];\n+\n+\t\tprepareOutput(out);\n+\t\tNB.encodeInt32(out, 0, 0);\n+\t\tassertOutput(b(0, 0, 0, 0), out, 0);\n+\n+\t\tprepareOutput(out);\n+\t\tNB.encodeInt32(out, 3, 0);\n+\t\tassertOutput(b(0, 0, 0, 0), out, 3);\n+\n+\t\tprepareOutput(out);\n+\t\tNB.encodeInt32(out, 0, 3);\n+\t\tassertOutput(b(0, 0, 0, 3), out, 0);\n+\n+\t\tprepareOutput(out);\n+\t\tNB.encodeInt32(out, 3, 3);\n+\t\tassertOutput(b(0, 0, 0, 3), out, 3);\n+\n+\t\tprepareOutput(out);\n+\t\tNB.encodeInt32(out, 0, 0xdeac);\n+\t\tassertOutput(b(0, 0, 0xde, 0xac), out, 0);\n+\n+\t\tprepareOutput(out);\n+\t\tNB.encodeInt32(out, 3, 0xdeac);\n+\t\tassertOutput(b(0, 0, 0xde, 0xac), out, 3);\n+\n+\t\tprepareOutput(out);\n+\t\tNB.encodeInt32(out, 0, 0xdeac9853);\n+\t\tassertOutput(b(0xde, 0xac, 0x98, 0x53), out, 0);\n+\n+\t\tprepareOutput(out);\n+\t\tNB.encodeInt32(out, 3, 0xdeac9853);\n+\t\tassertOutput(b(0xde, 0xac, 0x98, 0x53), out, 3);\n+\n+\t\tprepareOutput(out);\n+\t\tNB.encodeInt32(out, 3, -1);\n+\t\tassertOutput(b(0xff, 0xff, 0xff, 0xff), out, 3);\n+\t}\n+\n+\tpublic void testEncodeInt64() {\n+\t\tfinal byte[] out = new byte[16];\n+\n+\t\tprepareOutput(out);\n+\t\tNB.encodeInt64(out, 0, 0L);\n+\t\tassertOutput(b(0, 0, 0, 0, 0, 0, 0, 0), out, 0);\n+\n+\t\tprepareOutput(out);\n+\t\tNB.encodeInt64(out, 3, 0L);\n+\t\tassertOutput(b(0, 0, 0, 0, 0, 0, 0, 0), out, 3);\n+\n+\t\tprepareOutput(out);\n+\t\tNB.encodeInt64(out, 0, 3L);\n+\t\tassertOutput(b(0, 0, 0, 0, 0, 0, 0, 3), out, 0);\n+\n+\t\tprepareOutput(out);\n+\t\tNB.encodeInt64(out, 3, 3L);\n+\t\tassertOutput(b(0, 0, 0, 0, 0, 0, 0, 3), out, 3);\n+\n+\t\tprepareOutput(out);\n+\t\tNB.encodeInt64(out, 0, 0xdeacL);\n+\t\tassertOutput(b(0, 0, 0, 0, 0, 0, 0xde, 0xac), out, 0);\n+\n+\t\tprepareOutput(out);\n+\t\tNB.encodeInt64(out, 3, 0xdeacL);\n+\t\tassertOutput(b(0, 0, 0, 0, 0, 0, 0xde, 0xac), out, 3);\n+\n+\t\tprepareOutput(out);\n+\t\tNB.encodeInt64(out, 0, 0xdeac9853L);\n+\t\tassertOutput(b(0, 0, 0, 0, 0xde, 0xac, 0x98, 0x53), out, 0);\n+\n+\t\tprepareOutput(out);\n+\t\tNB.encodeInt64(out, 3, 0xdeac9853L);\n+\t\tassertOutput(b(0, 0, 0, 0, 0xde, 0xac, 0x98, 0x53), out, 3);\n+\n+\t\tprepareOutput(out);\n+\t\tNB.encodeInt64(out, 0, 0xac431242deac9853L);\n+\t\tassertOutput(b(0xac, 0x43, 0x12, 0x42, 0xde, 0xac, 0x98, 0x53), out, 0);\n+\n+\t\tprepareOutput(out);\n+\t\tNB.encodeInt64(out, 3, 0xac431242deac9853L);\n+\t\tassertOutput(b(0xac, 0x43, 0x12, 0x42, 0xde, 0xac, 0x98, 0x53), out, 3);\n+\n+\t\tprepareOutput(out);\n+\t\tNB.encodeInt64(out, 3, -1L);\n+\t\tassertOutput(b(0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff), out, 3);\n+\t}\n+\n+\tprivate static void prepareOutput(final byte[] buf) {\n+\t\tfor (int i = 0; i < buf.length; i++)\n+\t\t\tbuf[i] = (byte) (0x77 + i);\n+\t}\n+\n+\tprivate static void assertOutput(final byte[] expect, final byte[] buf,\n+\t\t\tfinal int offset) {\n+\t\tfor (int i = 0; i < offset; i++)\n+\t\t\tassertEquals((byte) (0x77 + i), buf[i]);\n+\t\tfor (int i = 0; i < expect.length; i++)\n+\t\t\tassertEquals(expect[i], buf[offset + i]);\n+\t\tfor (int i = offset + expect.length; i < buf.length; i++)\n+\t\t\tassertEquals((byte) (0x77 + i), buf[i]);\n+\t}\n+\n+\tprivate static byte[] b(final int a, final int b) {\n+\t\treturn new byte[] { (byte) a, (byte) b };\n+\t}\n+\n+\tprivate static byte[] padb(final int len, final int a, final int b) {\n+\t\tfinal byte[] r = new byte[len + 2];\n+\t\tfor (int i = 0; i < len; i++)\n+\t\t\tr[i] = (byte) 0xaf;\n+\t\tr[len] = (byte) a;\n+\t\tr[len + 1] = (byte) b;\n+\t\treturn r;\n+\t}\n+\n+\tprivate static byte[] b(final int a, final int b, final int c, final int d) {\n+\t\treturn new byte[] { (byte) a, (byte) b, (byte) c, (byte) d };\n+\t}\n+\n+\tprivate static byte[] padb(final int len, final int a, final int b,\n+\t\t\tfinal int c, final int d) {\n+\t\tfinal byte[] r = new byte[len + 4];\n+\t\tfor (int i = 0; i < len; i++)\n+\t\t\tr[i] = (byte) 0xaf;\n+\t\tr[len] = (byte) a;\n+\t\tr[len + 1] = (byte) b;\n+\t\tr[len + 2] = (byte) c;\n+\t\tr[len + 3] = (byte) d;\n+\t\treturn r;\n+\t}\n+\n+\tprivate static byte[] b(final int a, final int b, final int c, final int d,\n+\t\t\tfinal int e, final int f, final int g, final int h) {\n+\t\treturn new byte[] { (byte) a, (byte) b, (byte) c, (byte) d, (byte) e,\n+\t\t\t\t(byte) f, (byte) g, (byte) h };\n+\t}\n+\n+\tprivate static byte[] padb(final int len, final int a, final int b,\n+\t\t\tfinal int c, final int d, final int e, final int f, final int g,\n+\t\t\tfinal int h) {\n+\t\tfinal byte[] r = new byte[len + 8];\n+\t\tfor (int i = 0; i < len; i++)\n+\t\t\tr[i] = (byte) 0xaf;\n+\t\tr[len] = (byte) a;\n+\t\tr[len + 1] = (byte) b;\n+\t\tr[len + 2] = (byte) c;\n+\t\tr[len + 3] = (byte) d;\n+\t\tr[len + 4] = (byte) e;\n+\t\tr[len + 5] = (byte) f;\n+\t\tr[len + 6] = (byte) g;\n+\t\tr[len + 7] = (byte) h;\n+\t\treturn r;\n+\t}\n+}\n-- \n1.6.0.87.g2858d\n"},{"id":"87603","messageId":"1219103602-32222-5-git-send-email-spearce@spearce.org","threadId":"15078","inReplyTo":"1219103602-32222-4-git-send-email-spearce@spearce.org","subject":"[JGIT PATCH 04/14] Fix DirCache's skip over null byte padding when reading a DIRC file","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-08-18T23:53:12Z","receivedAt":"2008-08-18T23:53:12Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Sometimes we hit EOFException while reading from a 'DIRC' file with\nthe new DirCache API. This was caused by BufferedInputStream.skip\nskipping only part of the range we asked it to skip if the range we\nasked it to skip spanned over the end of the current buffer block.\nTwo skip requests are necessary in this case: one to force the stream\nto skip to the end of the buffer, and another to skip over data in\nthe source stream before reading the next buffer block into memory.\n\nNB.skipFully handles this by abstracting the necessary loop into\na utility function, much like NB.readFully handles the necessary\nread loop to ensure we read a full block of data.\n\nDirCacheEntry and DirCache both need to use this routine to skip\nover the parts of the DIRC file they do not wish to read.\n\nSigned-off-by: Shawn O. Pearce \n---\n .../src/org/spearce/jgit/dircache/DirCache.java | 2 +-\n .../org/spearce/jgit/dircache/DirCacheEntry.java | 2 +-\n org.spearce.jgit/src/org/spearce/jgit/util/NB.java | 27 ++++++++++++++++++++\n 3 files changed, 29 insertions(+), 2 deletions(-)\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCache.java b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCache.java\nindex 995942c..76657c4 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCache.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCache.java\n@@ -370,7 +370,7 @@ private void readFrom(final FileInputStream inStream) throws IOException,\n \t\t\t\t\t// a performance optimization. Since we do not\n \t\t\t\t\t// understand it, we can safely skip past it.\n \t\t\t\t\t//\n-\t\t\t\t\tin.skip(NB.decodeInt32(hdr, 4));\n+\t\t\t\t\tNB.skipFully(in, NB.decodeUInt32(hdr, 4));\n \t\t\t\t} else {\n \t\t\t\t\t// The extension is not an optimization and is\n \t\t\t\t\t// _required_ to understand this index format.\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheEntry.java b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheEntry.java\nindex bcf5596..011bc16 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheEntry.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheEntry.java\n@@ -116,7 +116,7 @@ DirCacheEntry(final byte[] sharedInfo, final int infoAt,\n \t\tfinal int actLen = INFO_LEN + pathLen;\n \t\tfinal int expLen = (actLen + 8) & ~7;\n \t\tif (actLen != expLen)\n-\t\t\tin.skip(expLen - actLen);\n+\t\t\tNB.skipFully(in, expLen - actLen);\n \t}\n \n \t/**\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/util/NB.java b/org.spearce.jgit/src/org/spearce/jgit/util/NB.java\nindex fa13354..759caf5 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/util/NB.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/util/NB.java\n@@ -71,6 +71,33 @@ public static void readFully(final InputStream fd, final byte[] dst,\n \t}\n \n \t/**\n+\t * Skip an entire region of an input stream.\n+\t *

\n+\t * The input stream's position is moved forward by the number of requested\n+\t * bytes, discarding them from the input. This method does not return until\n+\t * the exact number of bytes requested has been skipped.\n+\t * \n+\t * @param fd\n+\t * the stream to skip bytes from.\n+\t * @param toSkip\n+\t * total number of bytes to be discarded. Must be >= 0.\n+\t * @throws EOFException\n+\t * the stream ended before the requested number of bytes were\n+\t * skipped.\n+\t * @throws IOException\n+\t * there was an error reading from the stream.\n+\t */\n+\tpublic static void skipFully(final InputStream fd, long toSkip)\n+\t\t\tthrows IOException {\n+\t\twhile (toSkip > 0) {\n+\t\t\tfinal long r = fd.skip(toSkip);\n+\t\t\tif (r <= 0)\n+\t\t\t\tthrow new EOFException(\"Short skip of block\");\n+\t\t\ttoSkip -= r;\n+\t\t}\n+\t}\n+\n+\t/**\n \t * Compare a 32 bit unsigned integer stored in a 32 bit signed integer.\n \t *

\n \t * This function performs an unsigned compare operation, even though Java\n-- \n1.6.0.87.g2858d\n"},{"id":"87602","messageId":"1219103602-32222-6-git-send-email-spearce@spearce.org","threadId":"15078","inReplyTo":"1219103602-32222-5-git-send-email-spearce@spearce.org","subject":"[JGIT PATCH 05/14] Fix usage of assertEquals in DirCacheIteratorTest","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-08-18T23:53:13Z","receivedAt":"2008-08-18T23:53:13Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"I had the expected/actual values reversed so error messages from\nJUnit were a bit difficult to read.\n\nSigned-off-by: Shawn O. Pearce \n---\n .../jgit/dircache/DirCacheIteratorTest.java | 10 +++++-----\n 1 files changed, 5 insertions(+), 5 deletions(-)\n\ndiff --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\nindex 7d4e6bb..62a162f 100644\n--- a/org.spearce.jgit.test/tst/org/spearce/jgit/dircache/DirCacheIteratorTest.java\n+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/dircache/DirCacheIteratorTest.java\n@@ -87,7 +87,7 @@ public void testNoSubtree_NoTreeWalk() throws Exception {\n \t\t\tassertSame(ents[pathIdx], i.getDirCacheEntry());\n \t\t\tpathIdx++;\n \t\t}\n-\t\tassertEquals(pathIdx, paths.length);\n+\t\tassertEquals(paths.length, pathIdx);\n \t}\n \n \tpublic void testNoSubtree_WithTreeWalk() throws Exception {\n@@ -120,7 +120,7 @@ public void testNoSubtree_WithTreeWalk() throws Exception {\n \t\t\tassertSame(modes[pathIdx], tw.getFileMode(0));\n \t\t\tpathIdx++;\n \t\t}\n-\t\tassertEquals(pathIdx, paths.length);\n+\t\tassertEquals(paths.length, pathIdx);\n \t}\n \n \tpublic void testSingleSubtree_NoRecursion() throws Exception {\n@@ -164,7 +164,7 @@ public void testSingleSubtree_NoRecursion() throws Exception {\n \n \t\t\tpathIdx++;\n \t\t}\n-\t\tassertEquals(pathIdx, expPaths.length);\n+\t\tassertEquals(expPaths.length, pathIdx);\n \t}\n \n \tpublic void testSingleSubtree_Recursive() throws Exception {\n@@ -199,7 +199,7 @@ public void testSingleSubtree_Recursive() throws Exception {\n \t\t\tassertSame(mode, tw.getFileMode(0));\n \t\t\tpathIdx++;\n \t\t}\n-\t\tassertEquals(pathIdx, paths.length);\n+\t\tassertEquals(paths.length, pathIdx);\n \t}\n \n \tpublic void testTwoLevelSubtree_Recursive() throws Exception {\n@@ -233,7 +233,7 @@ public void testTwoLevelSubtree_Recursive() throws Exception {\n \t\t\tassertSame(mode, tw.getFileMode(0));\n \t\t\tpathIdx++;\n \t\t}\n-\t\tassertEquals(pathIdx, paths.length);\n+\t\tassertEquals(paths.length, pathIdx);\n \t}\n \n \tpublic void testTwoLevelSubtree_FilterPath() throws Exception {\n-- \n1.6.0.87.g2858d\n"},{"id":"87604","messageId":"1219103602-32222-7-git-send-email-spearce@spearce.org","threadId":"15078","inReplyTo":"1219103602-32222-6-git-send-email-spearce@spearce.org","subject":"[JGIT PATCH 06/14] Refactor AbstractTreeIterator.pathCompare to force another mode","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-08-18T23:53:14Z","receivedAt":"2008-08-18T23:53:14Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"When handling D/F (directory/file) conflicts we need to pretend that one\nof the two iterators has the other \"type\" of mode so we can search for\npossible matches. Rather than editing the mode instance member we now\noverload pathCompare to accept the 2nd iterator's mode as an argument.\n\nWe can now force a tree entry to compare as a normal file by passing\nin a mode of 0, or we can force a file entry to compare as a tree by\npassing in FileMode.TREE.getBits().\n\nSigned-off-by: Shawn O. Pearce \n---\n .../jgit/treewalk/AbstractTreeIterator.java | 14 +++++++++-----\n 1 files changed, 9 insertions(+), 5 deletions(-)\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java\nindex 232204a..bd75d2d 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java\n@@ -227,6 +227,10 @@ protected void growPath(final int len) {\n \t * p's entry sorts first.\n \t */\n \tpublic int pathCompare(final AbstractTreeIterator p) {\n+\t\treturn pathCompare(p, p.mode);\n+\t}\n+\n+\tint pathCompare(final AbstractTreeIterator p, final int pMode) {\n \t\tfinal byte[] a = path;\n \t\tfinal byte[] b = p.path;\n \t\tfinal int aLen = pathLen;\n@@ -241,7 +245,7 @@ public int pathCompare(final AbstractTreeIterator p) {\n \n \t\tif (cPos < aLen) {\n \t\t\tfinal int aj = a[cPos] & 0xff;\n-\t\t\tfinal int lastb = p.lastPathChar();\n+\t\t\tfinal int lastb = lastPathChar(pMode);\n \t\t\tif (aj < lastb)\n \t\t\t\treturn -1;\n \t\t\telse if (aj > lastb)\n@@ -254,7 +258,7 @@ else if (cPos == aLen - 1)\n \n \t\tif (cPos < bLen) {\n \t\t\tfinal int bk = b[cPos] & 0xff;\n-\t\t\tfinal int lasta = lastPathChar();\n+\t\t\tfinal int lasta = lastPathChar(mode);\n \t\t\tif (lasta < bk)\n \t\t\t\treturn -1;\n \t\t\telse if (lasta > bk)\n@@ -265,8 +269,8 @@ else if (cPos == bLen - 1)\n \t\t\t\treturn 1;\n \t\t}\n \n-\t\tfinal int lasta = lastPathChar();\n-\t\tfinal int lastb = p.lastPathChar();\n+\t\tfinal int lasta = lastPathChar(mode);\n+\t\tfinal int lastb = lastPathChar(pMode);\n \t\tif (lasta < lastb)\n \t\t\treturn -1;\n \t\telse if (lasta > lastb)\n@@ -280,7 +284,7 @@ else if (aLen < bLen)\n \t\t\treturn 1;\n \t}\n \n-\tprivate int lastPathChar() {\n+\tprivate static int lastPathChar(final int mode) {\n \t\treturn FileMode.TREE.equals(mode) ? '/' : '\\0';\n \t}\n \n-- \n1.6.0.87.g2858d\n"},{"id":"87605","messageId":"1219103602-32222-8-git-send-email-spearce@spearce.org","threadId":"15078","inReplyTo":"1219103602-32222-7-git-send-email-spearce@spearce.org","subject":"[JGIT PATCH 07/14] Micro-optimize AbstractTreeIterator.pathCompare","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-08-18T23:53:15Z","receivedAt":"2008-08-18T23:53:15Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"We were doing far too much work in pathCompare to handle\ncases that just cannot ever happen, such as if the paths\nwere the same length but had different \"last path char\"\nand then somehow had different lengths.\n\nWe also had the JVM doing a lot of comparsion ops just\nto return -1/0/1 when really we can get away with the\nnon-zero result returned to the caller. Issuing just\nthe subtraction and one comparsion to 0 is much quicker,\nJIT or not.\n\nSigned-off-by: Shawn O. Pearce \n---\n .../jgit/treewalk/AbstractTreeIterator.java | 44 ++-----------------\n 1 files changed, 5 insertions(+), 39 deletions(-)\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java\nindex bd75d2d..31257b5 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java\n@@ -243,45 +243,11 @@ int pathCompare(final AbstractTreeIterator p, final int pMode) {\n \t\t\t\treturn cmp;\n \t\t}\n \n-\t\tif (cPos < aLen) {\n-\t\t\tfinal int aj = a[cPos] & 0xff;\n-\t\t\tfinal int lastb = lastPathChar(pMode);\n-\t\t\tif (aj < lastb)\n-\t\t\t\treturn -1;\n-\t\t\telse if (aj > lastb)\n-\t\t\t\treturn 1;\n-\t\t\telse if (cPos == aLen - 1)\n-\t\t\t\treturn 0;\n-\t\t\telse\n-\t\t\t\treturn -1;\n-\t\t}\n-\n-\t\tif (cPos < bLen) {\n-\t\t\tfinal int bk = b[cPos] & 0xff;\n-\t\t\tfinal int lasta = lastPathChar(mode);\n-\t\t\tif (lasta < bk)\n-\t\t\t\treturn -1;\n-\t\t\telse if (lasta > bk)\n-\t\t\t\treturn 1;\n-\t\t\telse if (cPos == bLen - 1)\n-\t\t\t\treturn 0;\n-\t\t\telse\n-\t\t\t\treturn 1;\n-\t\t}\n-\n-\t\tfinal int lasta = lastPathChar(mode);\n-\t\tfinal int lastb = lastPathChar(pMode);\n-\t\tif (lasta < lastb)\n-\t\t\treturn -1;\n-\t\telse if (lasta > lastb)\n-\t\t\treturn 1;\n-\n-\t\tif (aLen == bLen)\n-\t\t\treturn 0;\n-\t\telse if (aLen < bLen)\n-\t\t\treturn -1;\n-\t\telse\n-\t\t\treturn 1;\n+\t\tif (cPos < aLen)\n+\t\t\treturn (a[cPos] & 0xff) - lastPathChar(pMode);\n+\t\tif (cPos < bLen)\n+\t\t\treturn lastPathChar(mode) - (b[cPos] & 0xff);\n+\t\treturn lastPathChar(mode) - lastPathChar(pMode);\n \t}\n \n \tprivate static int lastPathChar(final int mode) {\n-- \n1.6.0.87.g2858d\n"},{"id":"87606","messageId":"1219103602-32222-9-git-send-email-spearce@spearce.org","threadId":"15078","inReplyTo":"1219103602-32222-8-git-send-email-spearce@spearce.org","subject":"[JGIT PATCH 08/14] Optimize path comparsion within subtrees during TreeWalk","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-08-18T23:53:16Z","receivedAt":"2008-08-18T23:53:16Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"If we are comparing two entries whose parents both match the same\ntree iterator we know the path up through pathOffset must all\nbe identical, as the parents can only match if their paths up to\npathOffset were equal and they were both trees.\n\nSigned-off-by: Shawn O. Pearce \n---\n .../jgit/treewalk/AbstractTreeIterator.java | 22 +++++++++++++++++++-\n 1 files changed, 21 insertions(+), 1 deletions(-)\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java\nindex 31257b5..e6aa338 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java\n@@ -237,7 +237,13 @@ int pathCompare(final AbstractTreeIterator p, final int pMode) {\n \t\tfinal int bLen = p.pathLen;\n \t\tint cPos;\n \n-\t\tfor (cPos = 0; cPos < aLen && cPos < bLen; cPos++) {\n+\t\t// Its common when we are a subtree for both parents to match;\n+\t\t// when this happens everything in path[0..cPos] is known to\n+\t\t// be equal and does not require evaluation again.\n+\t\t//\n+\t\tcPos = alreadyMatch(this, p);\n+\n+\t\tfor (; cPos < aLen && cPos < bLen; cPos++) {\n \t\t\tfinal int cmp = (a[cPos] & 0xff) - (b[cPos] & 0xff);\n \t\t\tif (cmp != 0)\n \t\t\t\treturn cmp;\n@@ -250,6 +256,20 @@ int pathCompare(final AbstractTreeIterator p, final int pMode) {\n \t\treturn lastPathChar(mode) - lastPathChar(pMode);\n \t}\n \n+\tprivate static int alreadyMatch(AbstractTreeIterator a,\n+\t\t\tAbstractTreeIterator b) {\n+\t\tfor (;;) {\n+\t\t\tfinal AbstractTreeIterator ap = a.parent;\n+\t\t\tfinal AbstractTreeIterator bp = b.parent;\n+\t\t\tif (ap == null || bp == null)\n+\t\t\t\treturn 0;\n+\t\t\tif (ap.matches == bp.matches)\n+\t\t\t\treturn a.pathOffset;\n+\t\t\ta = ap;\n+\t\t\tb = bp;\n+\t\t}\n+\t}\n+\n \tprivate static int lastPathChar(final int mode) {\n \t\treturn FileMode.TREE.equals(mode) ? '/' : '\\0';\n \t}\n-- \n1.6.0.87.g2858d\n"},{"id":"87607","messageId":"1219103602-32222-10-git-send-email-spearce@spearce.org","threadId":"15078","inReplyTo":"1219103602-32222-9-git-send-email-spearce@spearce.org","subject":"[JGIT PATCH 09/14] Refactor AbstractTreeIterator semantics to start on first entry","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-08-18T23:53:17Z","receivedAt":"2008-08-18T23:53:17Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"The AbstractTreeIterator implementations now start on their first\nentry at construction time, instead of relying on TreeWalk to do\nan initial \"next()\" invocation. This cleans up some of the code\nand makes the iterators more consistent with each other.\n\nIn all implementations the refactoring splits out the advance\nportion of next() from the entry parsing portion. This change\n(along with the position semantic change) will permit us to do\nreverse iteration in the future, making the iterators all able\nto be bi-directional.\n\nSigned-off-by: Shawn O. Pearce \n---\n .../spearce/egit/core/ContainerTreeIterator.java | 9 +-\n .../jgit/dircache/DirCacheBuilderIteratorTest.java | 2 +-\n .../jgit/dircache/DirCacheIteratorTest.java | 18 +--\n .../jgit/dircache/DirCacheBuildIterator.java | 7 +-\n .../spearce/jgit/dircache/DirCacheIterator.java | 63 +++++------\n .../jgit/treewalk/AbstractTreeIterator.java | 5 +-\n .../spearce/jgit/treewalk/CanonicalTreeParser.java | 27 +++--\n .../spearce/jgit/treewalk/FileTreeIterator.java | 5 +-\n .../src/org/spearce/jgit/treewalk/TreeWalk.java | 4 -\n .../spearce/jgit/treewalk/WorkingTreeIterator.java | 119 ++++++++------------\n 10 files changed, 112 insertions(+), 147 deletions(-)\n\ndiff --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\nindex c4af788..2b7ff3b 100644\n--- a/org.spearce.egit.core/src/org/spearce/egit/core/ContainerTreeIterator.java\n+++ b/org.spearce.egit.core/src/org/spearce/egit/core/ContainerTreeIterator.java\n@@ -67,12 +67,14 @@ private static String computePrefix(final IContainer base) {\n \tpublic ContainerTreeIterator(final IContainer base) {\n \t\tsuper(computePrefix(base));\n \t\tnode = base;\n+\t\tinit(entries());\n \t}\n \n \tprivate ContainerTreeIterator(final WorkingTreeIterator p,\n \t\t\tfinal IContainer base) {\n \t\tsuper(p);\n \t\tnode = base;\n+\t\tinit(entries());\n \t}\n \n \t@Override\n@@ -86,16 +88,13 @@ public AbstractTreeIterator createSubtreeIterator(final Repository db)\n \t\t\t\t\tConstants.TYPE_TREE);\n \t}\n \n-\t@Override\n-\tprotected Entry[] getEntries() throws IOException {\n+\tprivate Entry[] entries() {\n \t\tfinal IResource[] all;\n \t\ttry {\n //\t\t\tall = node.members(IContainer.INCLUDE_HIDDEN); 3.4 flag\n \t\t\tall = node.members(0);\n \t\t} catch (CoreException err) {\n-\t\t\tfinal IOException ioe = new IOException(err.getMessage());\n-\t\t\tioe.initCause(err);\n-\t\t\tthrow ioe;\n+\t\t\treturn EOF;\n \t\t}\n \n \t\tfinal Entry[] r = new Entry[all.length];\ndiff --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\nindex cbcdeb5..162f4ba 100644\n--- a/org.spearce.jgit.test/tst/org/spearce/jgit/dircache/DirCacheBuilderIteratorTest.java\n+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/dircache/DirCacheBuilderIteratorTest.java\n@@ -74,7 +74,7 @@ public void testPathFilterGroup_DoesNotSkipTail() throws Exception {\n \t\tassertTrue(\"found \" + paths[expIdx], tw.next());\n \t\tfinal DirCacheIterator c = tw.getTree(0, DirCacheIterator.class);\n \t\tassertNotNull(c);\n-\t\tassertEquals(expIdx, c.cachePos);\n+\t\tassertEquals(expIdx, c.ptr);\n \t\tassertSame(ents[expIdx], c.getDirCacheEntry());\n \t\tassertEquals(paths[expIdx], tw.getPathString());\n \t\tassertEquals(mode.getBits(), tw.getRawMode(0));\ndiff --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\nindex 62a162f..51b3c5a 100644\n--- a/org.spearce.jgit.test/tst/org/spearce/jgit/dircache/DirCacheIteratorTest.java\n+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/dircache/DirCacheIteratorTest.java\n@@ -50,7 +50,6 @@ public void testEmptyTree_NoTreeWalk() throws Exception {\n \t\tassertEquals(0, dc.getEntryCount());\n \n \t\tfinal DirCacheIterator i = new DirCacheIterator(dc);\n-\t\ti.next();\n \t\tassertTrue(i.eof());\n \t}\n \n@@ -79,11 +78,8 @@ public void testNoSubtree_NoTreeWalk() throws Exception {\n \n \t\tfinal DirCacheIterator i = new DirCacheIterator(dc);\n \t\tint pathIdx = 0;\n-\t\tfor (;;) {\n-\t\t\ti.next();\n-\t\t\tif (i.eof())\n-\t\t\t\tbreak;\n-\t\t\tassertEquals(pathIdx, i.cachePos);\n+\t\tfor (; !i.eof(); i.next()) {\n+\t\t\tassertEquals(pathIdx, i.ptr);\n \t\t\tassertSame(ents[pathIdx], i.getDirCacheEntry());\n \t\t\tpathIdx++;\n \t\t}\n@@ -113,7 +109,7 @@ public void testNoSubtree_WithTreeWalk() throws Exception {\n \t\tint pathIdx = 0;\n \t\twhile (tw.next()) {\n \t\t\tassertSame(i, tw.getTree(0, DirCacheIterator.class));\n-\t\t\tassertEquals(pathIdx, i.cachePos);\n+\t\t\tassertEquals(pathIdx, i.ptr);\n \t\t\tassertSame(ents[pathIdx], i.getDirCacheEntry());\n \t\t\tassertEquals(paths[pathIdx], tw.getPathString());\n \t\t\tassertEquals(modes[pathIdx].getBits(), tw.getRawMode(0));\n@@ -156,7 +152,7 @@ public void testSingleSubtree_NoRecursion() throws Exception {\n \t\t\tassertEquals(expPaths[pathIdx], tw.getPathString());\n \n \t\t\tif (expPos[pathIdx] >= 0) {\n-\t\t\t\tassertEquals(expPos[pathIdx], i.cachePos);\n+\t\t\t\tassertEquals(expPos[pathIdx], i.ptr);\n \t\t\t\tassertSame(ents[expPos[pathIdx]], i.getDirCacheEntry());\n \t\t\t} else {\n \t\t\t\tassertSame(FileMode.TREE, tw.getFileMode(0));\n@@ -192,7 +188,7 @@ public void testSingleSubtree_Recursive() throws Exception {\n \t\twhile (tw.next()) {\n \t\t\tfinal DirCacheIterator c = tw.getTree(0, DirCacheIterator.class);\n \t\t\tassertNotNull(c);\n-\t\t\tassertEquals(pathIdx, c.cachePos);\n+\t\t\tassertEquals(pathIdx, c.ptr);\n \t\t\tassertSame(ents[pathIdx], c.getDirCacheEntry());\n \t\t\tassertEquals(paths[pathIdx], tw.getPathString());\n \t\t\tassertEquals(mode.getBits(), tw.getRawMode(0));\n@@ -226,7 +222,7 @@ public void testTwoLevelSubtree_Recursive() throws Exception {\n \t\twhile (tw.next()) {\n \t\t\tfinal DirCacheIterator c = tw.getTree(0, DirCacheIterator.class);\n \t\t\tassertNotNull(c);\n-\t\t\tassertEquals(pathIdx, c.cachePos);\n+\t\t\tassertEquals(pathIdx, c.ptr);\n \t\t\tassertSame(ents[pathIdx], c.getDirCacheEntry());\n \t\t\tassertEquals(paths[pathIdx], tw.getPathString());\n \t\t\tassertEquals(mode.getBits(), tw.getRawMode(0));\n@@ -262,7 +258,7 @@ public void testTwoLevelSubtree_FilterPath() throws Exception {\n \t\t\tassertTrue(tw.next());\n \t\t\tfinal DirCacheIterator c = tw.getTree(0, DirCacheIterator.class);\n \t\t\tassertNotNull(c);\n-\t\t\tassertEquals(victimIdx, c.cachePos);\n+\t\t\tassertEquals(victimIdx, c.ptr);\n \t\t\tassertSame(ents[victimIdx], c.getDirCacheEntry());\n \t\t\tassertEquals(paths[victimIdx], tw.getPathString());\n \t\t\tassertEquals(mode.getBits(), tw.getRawMode(0));\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheBuildIterator.java b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheBuildIterator.java\nindex 227b64c..aaec4fc 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheBuildIterator.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheBuildIterator.java\n@@ -109,7 +109,7 @@ public AbstractTreeIterator createSubtreeIterator(final Repository repo)\n \t@Override\n \tpublic void skip() throws CorruptObjectException {\n \t\tif (currentSubtree != null)\n-\t\t\tbuilder.keep(cachePos, currentSubtree.getEntrySpan());\n+\t\t\tbuilder.keep(ptr, currentSubtree.getEntrySpan());\n \t\telse\n \t\t\tbuilder.add(currentEntry);\n \t\tnext();\n@@ -117,8 +117,9 @@ public void skip() throws CorruptObjectException {\n \n \t@Override\n \tpublic void stopWalk() {\n+\t\tfinal int cur = ptr;\n \t\tfinal int cnt = cache.getEntryCount();\n-\t\tif (cachePos < cnt)\n-\t\t\tbuilder.keep(cachePos, cnt - cachePos);\n+\t\tif (cur < cnt)\n+\t\t\tbuilder.keep(cur, cnt - cur);\n \t}\n }\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheIterator.java b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheIterator.java\nindex c093bb2..248ae1e 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheIterator.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheIterator.java\n@@ -40,7 +40,6 @@\n import java.io.IOException;\n import java.util.Arrays;\n \n-import org.spearce.jgit.errors.CorruptObjectException;\n import org.spearce.jgit.errors.IncorrectObjectTypeException;\n import org.spearce.jgit.lib.Constants;\n import org.spearce.jgit.lib.FileMode;\n@@ -65,19 +64,19 @@\n \t/** The tree this iterator is walking. */\n \tprivate final DirCacheTree tree;\n \n+\t/** Last position in this tree. */\n+\tprivate final int treeEnd;\n+\n \t/** Special buffer to hold the ObjectId of {@link #currentSubtree}. */\n \tprivate final byte[] subtreeId;\n \n \t/** Index of entry within {@link #cache}. */\n-\tprotected int cachePos;\n-\n-\t/** Position of entry within {@link #tree}'s entry span. */\n-\tprivate int treePos;\n+\tprotected int ptr;\n \n \t/** Next subtree to consider within {@link #tree}. */\n-\tprivate int subtreeIdx;\n+\tprivate int nextSubtreePos;\n \n-\t/** The current file entry from {@link #cache}, matching {@link #cachePos}. */\n+\t/** The current file entry from {@link #cache}. */\n \tprotected DirCacheEntry currentEntry;\n \n \t/** The subtree containing {@link #currentEntry} if this is first entry. */\n@@ -96,18 +95,20 @@\n \tpublic DirCacheIterator(final DirCache dc) {\n \t\tcache = dc;\n \t\ttree = dc.getCacheTree(true);\n+\t\ttreeEnd = tree.getEntrySpan();\n \t\tsubtreeId = new byte[Constants.OBJECT_ID_LENGTH];\n-\t\tcachePos = -1;\n-\t\ttreePos = -1;\n+\t\tif (!eof())\n+\t\t\tparseEntry();\n \t}\n \n \tprotected DirCacheIterator(final DirCacheIterator p, final DirCacheTree dct) {\n \t\tsuper(p, p.path, p.pathLen + 1);\n \t\tcache = p.cache;\n \t\ttree = dct;\n+\t\ttreeEnd = p.ptr + tree.getEntrySpan();\n \t\tsubtreeId = p.subtreeId;\n-\t\tcachePos = p.cachePos - 1; // back up so first next() call enters it\n-\t\ttreePos = -1;\n+\t\tptr = p.ptr;\n+\t\tparseEntry();\n \t}\n \n \t@Override\n@@ -139,40 +140,31 @@ public int idOffset() {\n \n \t@Override\n \tpublic boolean eof() {\n-\t\treturn treePos >= tree.getEntrySpan();\n+\t\treturn ptr == treeEnd;\n \t}\n \n \t@Override\n-\tpublic void next() throws CorruptObjectException {\n-\t\tif (currentSubtree != null) {\n-\t\t\t// If our last position was a subtree we need to skip over\n-\t\t\t// its entire span to get to the item after the subtree.\n-\t\t\t//\n-\t\t\tfinal int n = currentSubtree.getEntrySpan();\n-\t\t\tcachePos += n;\n-\t\t\ttreePos += n;\n-\t\t\tcurrentSubtree = null;\n-\t\t} else {\n-\t\t\t// Our last position was a file/symlink/gitlink, so we\n-\t\t\t// only skip the one entry.\n-\t\t\t//\n-\t\t\tcachePos++;\n-\t\t\ttreePos++;\n-\t\t}\n-\n-\t\tif (treePos >= tree.getEntrySpan())\n-\t\t\treturn; // this iterator is now at EOF.\n+\tpublic void next() {\n+\t\tif (currentSubtree != null)\n+\t\t\tptr += currentSubtree.getEntrySpan();\n+\t\telse\n+\t\t\tptr++;\n+\t\tif (!eof())\n+\t\t\tparseEntry();\n+\t}\n \n-\t\tcurrentEntry = cache.getEntry(cachePos);\n+\tprivate void parseEntry() {\n+\t\tcurrentEntry = cache.getEntry(ptr);\n \t\tfinal byte[] cep = currentEntry.path;\n-\t\tif (subtreeIdx < tree.getChildCount()) {\n-\t\t\tfinal DirCacheTree s = tree.getChild(subtreeIdx);\n+\n+\t\tif (nextSubtreePos != tree.getChildCount()) {\n+\t\t\tfinal DirCacheTree s = tree.getChild(nextSubtreePos);\n \t\t\tif (s.contains(cep, pathOffset, cep.length)) {\n \t\t\t\t// The current position is the first file of this subtree.\n \t\t\t\t// Use the subtree instead as the current position.\n \t\t\t\t//\n \t\t\t\tcurrentSubtree = s;\n-\t\t\t\tsubtreeIdx++;\n+\t\t\t\tnextSubtreePos++;\n \n \t\t\t\tif (s.isValid())\n \t\t\t\t\ts.getObjectId().copyRawTo(subtreeId, 0);\n@@ -191,6 +183,7 @@ public void next() throws CorruptObjectException {\n \t\tmode = currentEntry.getRawMode();\n \t\tpath = cep;\n \t\tpathLen = cep.length;\n+\t\tcurrentSubtree = null;\n \t}\n \n \t/**\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java\nindex e6aa338..208adc7 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java\n@@ -53,9 +53,8 @@\n /**\n * Walks a Git tree (directory) in Git sort order.\n *

\n- * A new iterator instance should be positioned before the first entry. The data\n- * about the first entry is not available until after the first call to\n- * {@link #next()} is made.\n+ * A new iterator instance should be positioned on the first entry, or at eof.\n+ * Data for the first entry (if not at eof) should be available immediately.\n *

\n * Implementors must walk a tree in the Git sort order, which has the following\n * odd sorting:\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/CanonicalTreeParser.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/CanonicalTreeParser.java\nindex 55942ed..ebcc787 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/CanonicalTreeParser.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/CanonicalTreeParser.java\n@@ -52,7 +52,11 @@\n public class CanonicalTreeParser extends AbstractTreeIterator {\n \tprivate byte[] raw;\n \n-\tprivate int rawPtr;\n+\t/** First offset within {@link #raw} of the current entry's data. */\n+\tprivate int currPtr;\n+\n+\t/** Offset one past the current entry (first byte of next entry. */\n+\tprivate int nextPtr;\n \n \t/** Create a new parser. */\n \tpublic CanonicalTreeParser() {\n@@ -71,7 +75,9 @@ private CanonicalTreeParser(final CanonicalTreeParser p) {\n \t */\n \tpublic void reset(final byte[] treeData) {\n \t\traw = treeData;\n-\t\trawPtr = 0;\n+\t\tcurrPtr = 0;\n+\t\tif (!eof())\n+\t\t\tparseEntry();\n \t}\n \n \t/**\n@@ -118,20 +124,21 @@ public CanonicalTreeParser createSubtreeIterator(final Repository repo)\n \n \t@Override\n \tpublic int idOffset() {\n-\t\treturn rawPtr - Constants.OBJECT_ID_LENGTH;\n+\t\treturn nextPtr - Constants.OBJECT_ID_LENGTH;\n \t}\n \n \tpublic boolean eof() {\n-\t\treturn raw == null;\n+\t\treturn currPtr == raw.length;\n \t}\n \n \tpublic void next() throws CorruptObjectException {\n-\t\tint ptr = rawPtr;\n-\t\tif (ptr >= raw.length) {\n-\t\t\traw = null;\n-\t\t\treturn;\n-\t\t}\n+\t\tcurrPtr = nextPtr;\n+\t\tif (!eof())\n+\t\t\tparseEntry();\n+\t}\n \n+\tprivate void parseEntry() {\n+\t\tint ptr = currPtr;\n \t\tbyte c = raw[ptr++];\n \t\tint tmp = c - '0';\n \t\tfor (;;) {\n@@ -156,6 +163,6 @@ public void next() throws CorruptObjectException {\n \t\t\t}\n \t\t}\n \t\tpathLen = tmp;\n-\t\trawPtr = ptr + Constants.OBJECT_ID_LENGTH;\n+\t\tnextPtr = ptr + Constants.OBJECT_ID_LENGTH;\n \t}\n }\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/FileTreeIterator.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/FileTreeIterator.java\nindex 25425dd..2c71151 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/FileTreeIterator.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/FileTreeIterator.java\n@@ -66,6 +66,7 @@\n \t */\n \tpublic FileTreeIterator(final File root) {\n \t\tdirectory = root;\n+\t\tinit(entries());\n \t}\n \n \t/**\n@@ -80,6 +81,7 @@ public FileTreeIterator(final File root) {\n \tprotected FileTreeIterator(final FileTreeIterator p, final File root) {\n \t\tsuper(p);\n \t\tdirectory = root;\n+\t\tinit(entries());\n \t}\n \n \t@Override\n@@ -88,8 +90,7 @@ public AbstractTreeIterator createSubtreeIterator(final Repository repo)\n \t\treturn new FileTreeIterator(this, ((FileEntry) current()).file);\n \t}\n \n-\t@Override\n-\tprotected Entry[] getEntries() {\n+\tprivate Entry[] entries() {\n \t\tfinal File[] all = directory.listFiles();\n \t\tif (all == null)\n \t\t\treturn EOF;\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java\nindex 5aabc19..3bdef22 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java\n@@ -276,14 +276,12 @@ public void reset(final ObjectId[] ids) throws MissingObjectException,\n \t\t\t\tif (o instanceof CanonicalTreeParser) {\n \t\t\t\t\to.matches = null;\n \t\t\t\t\t((CanonicalTreeParser) o).reset(db, ids[i]);\n-\t\t\t\t\to.next();\n \t\t\t\t\tr[i] = o;\n \t\t\t\t\tcontinue;\n \t\t\t\t}\n \t\t\t}\n \n \t\t\to = parserFor(ids[i]);\n-\t\t\to.next();\n \t\t\tr[i] = o;\n \t\t}\n \n@@ -340,7 +338,6 @@ public int addTree(final AbstractTreeIterator p)\n \t\tSystem.arraycopy(trees, 0, newTrees, 0, n);\n \t\tnewTrees[n] = p;\n \t\tp.matches = null;\n-\t\tp.next();\n \n \t\ttrees = newTrees;\n \t\treturn n;\n@@ -617,7 +614,6 @@ public void enterSubtree() throws MissingObjectException,\n \t\t\t\tn = t.createSubtreeIterator(db);\n \t\t\telse\n \t\t\t\tn = new EmptyTreeIterator(t);\n-\t\t\tn.next();\n \t\t\ttmp[i] = n;\n \t\t}\n \t\tdepth++;\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/WorkingTreeIterator.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/WorkingTreeIterator.java\nindex f66b5e9..e81ff4a 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/WorkingTreeIterator.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/WorkingTreeIterator.java\n@@ -63,7 +63,7 @@\n * @see FileTreeIterator\n */\n public abstract class WorkingTreeIterator extends AbstractTreeIterator {\n-\t/** An empty entry array, suitable for return from {@link #getEntries()}. */\n+\t/** An empty entry array, suitable for {@link #init(Entry[])}. */\n \tprotected static final Entry[] EOF = {};\n \n \t/** Size we perform file IO in if we have to read and hash a file. */\n@@ -72,7 +72,7 @@\n \t/** The {@link #idBuffer()} for the current entry. */\n \tprivate byte[] contentId;\n \n-\t/** Value of {@link #ptr} when {@link #contentId} was last populated. */\n+\t/** Index within {@link #entries} that {@link #contentId} came from. */\n \tprivate int contentIdFromPtr;\n \n \t/** Buffer used to perform {@link #contentId} computations. */\n@@ -132,15 +132,12 @@ protected WorkingTreeIterator(final WorkingTreeIterator p) {\n \n \t@Override\n \tpublic byte[] idBuffer() {\n-\t\tif (contentIdFromPtr == ptr - 1)\n+\t\tif (contentIdFromPtr == ptr)\n \t\t\treturn contentId;\n-\t\tif (entries == EOF)\n-\t\t\treturn zeroid;\n-\n \t\tswitch (mode & 0170000) {\n \t\tcase 0100000: /* normal files */\n-\t\t\tcontentIdFromPtr = ptr - 1;\n-\t\t\treturn contentId = idBufferBlob(entries[contentIdFromPtr]);\n+\t\t\tcontentIdFromPtr = ptr;\n+\t\t\treturn contentId = idBufferBlob(entries[ptr]);\n \t\tcase 0120000: /* symbolic links */\n \t\t\t// Java does not support symbolic links, so we should not\n \t\t\t// have reached this particular part of the walk code.\n@@ -235,21 +232,18 @@ public int idOffset() {\n \n \t@Override\n \tpublic boolean eof() {\n-\t\treturn entries == EOF;\n+\t\treturn ptr == entryCnt;\n \t}\n \n \t@Override\n \tpublic void next() throws CorruptObjectException {\n-\t\tif (entries == null)\n-\t\t\tloadEntries();\n-\t\tif (ptr == entryCnt) {\n-\t\t\tentries = EOF;\n-\t\t\treturn;\n-\t\t}\n-\t\tif (entries == EOF)\n-\t\t\treturn;\n+\t\tptr++;\n+\t\tif (!eof())\n+\t\t\tparseEntry();\n+\t}\n \n-\t\tfinal Entry e = entries[ptr++];\n+\tprivate void parseEntry() {\n+\t\tfinal Entry e = entries[ptr];\n \t\tmode = e.getMode().getBits();\n \n \t\tfinal int nameLen = e.encodedNameLen;\n@@ -338,43 +332,35 @@ static int lastPathChar(final Entry e) {\n \t\treturn e.getMode() == FileMode.TREE ? '/' : '\\0';\n \t}\n \n-\tprivate void loadEntries() throws CorruptObjectException {\n+\tprotected void init(final Entry[] list) {\n \t\t// Filter out nulls, . and .. as these are not valid tree entries,\n \t\t// also cache the encoded forms of the path names for efficient use\n \t\t// later on during sorting and iteration.\n \t\t//\n-\t\ttry {\n-\t\t\tentries = getEntries();\n-\t\t\tint i, o;\n-\n-\t\t\tfor (i = 0, o = 0; i < entries.length; i++) {\n-\t\t\t\tfinal Entry e = entries[i];\n-\t\t\t\tif (e == null)\n-\t\t\t\t\tcontinue;\n-\t\t\t\tfinal String name = e.getName();\n-\t\t\t\tif (\".\".equals(name) || \"..\".equals(name))\n-\t\t\t\t\tcontinue;\n-\t\t\t\tif (parent == null && \".git\".equals(name))\n-\t\t\t\t\tcontinue;\n-\t\t\t\tif (i != o)\n-\t\t\t\t\tentries[o] = e;\n-\t\t\t\te.encodeName(nameEncoder);\n-\t\t\t\to++;\n-\t\t\t}\n-\t\t\tentryCnt = o;\n-\t\t\tcontentIdFromPtr = -1;\n-\t\t\tArrays.sort(entries, 0, entryCnt, ENTRY_CMP);\n-\t\t} catch (CharacterCodingException e) {\n-\t\t\tfinal CorruptObjectException why;\n-\t\t\twhy = new CorruptObjectException(\"Invalid file name encoding\");\n-\t\t\twhy.initCause(e);\n-\t\t\tthrow why;\n-\t\t} catch (IOException e) {\n-\t\t\tfinal CorruptObjectException why;\n-\t\t\twhy = new CorruptObjectException(\"Error reading directory\");\n-\t\t\twhy.initCause(e);\n-\t\t\tthrow why;\n+\t\tentries = list;\n+\t\tint i, o;\n+\n+\t\tfor (i = 0, o = 0; i < entries.length; i++) {\n+\t\t\tfinal Entry e = entries[i];\n+\t\t\tif (e == null)\n+\t\t\t\tcontinue;\n+\t\t\tfinal String name = e.getName();\n+\t\t\tif (\".\".equals(name) || \"..\".equals(name))\n+\t\t\t\tcontinue;\n+\t\t\tif (parent == null && \".git\".equals(name))\n+\t\t\t\tcontinue;\n+\t\t\tif (i != o)\n+\t\t\t\tentries[o] = e;\n+\t\t\te.encodeName(nameEncoder);\n+\t\t\to++;\n \t\t}\n+\t\tentryCnt = o;\n+\t\tArrays.sort(entries, 0, entryCnt, ENTRY_CMP);\t\t\n+\n+\t\tcontentIdFromPtr = -1;\n+\t\tptr = 0;\n+\t\tif (!eof())\n+\t\t\tparseEntry();\n \t}\n \n \t/**\n@@ -383,37 +369,24 @@ private void loadEntries() throws CorruptObjectException {\n \t * @return the currently selected entry.\n \t */\n \tprotected Entry current() {\n-\t\treturn entries[ptr - 1];\n+\t\treturn entries[ptr];\n \t}\n \n-\t/**\n-\t * Obtain an unsorted list of this iterator's contents.\n-\t *

\n-\t * Implementations only need to provide the unsorted contents of their lower\n-\t * level directory. The caller will automatically prune out \".\", \"..\",\n-\t * \".git\", as well as null entries as necessary, and then sort the array\n-\t * for iteration within a TreeWalk instance.\n-\t *

\n-\t * The returned array will be modified by the caller.\n-\t *

\n-\t * This method is only invoked once per iterator instance.\n-\t * \n-\t * @return unsorted list of the immediate children. Never null, but may be\n-\t * {@link #EOF} if no items can be obtained.\n-\t * @throws IOException\n-\t * reading the contents failed due to IO errors.\n-\t */\n-\tprotected abstract Entry[] getEntries() throws IOException;\n-\n \t/** A single entry within a working directory tree. */\n \tprotected static abstract class Entry {\n \t\tbyte[] encodedName;\n \n \t\tint encodedNameLen;\n \n-\t\tvoid encodeName(final CharsetEncoder enc)\n-\t\t\t\tthrows CharacterCodingException {\n-\t\t\tfinal ByteBuffer b = enc.encode(CharBuffer.wrap(getName()));\n+\t\tvoid encodeName(final CharsetEncoder enc) {\n+\t\t\tfinal ByteBuffer b;\t\t\t\n+\t\t\ttry {\n+\t\t\t\tb = enc.encode(CharBuffer.wrap(getName()));\n+\t\t\t} catch (CharacterCodingException e) {\n+\t\t\t\t// This should so never happen.\n+\t\t\t\tthrow new RuntimeException(\"Unencodeable file: \" + getName());\n+\t\t\t}\n+\n \t\t\tencodedNameLen = b.limit();\n \t\t\tif (b.hasArray() && b.arrayOffset() == 0)\n \t\t\t\tencodedName = b.array();\n-- \n1.6.0.87.g2858d\n"},{"id":"87610","messageId":"1219103602-32222-11-git-send-email-spearce@spearce.org","threadId":"15078","inReplyTo":"1219103602-32222-10-git-send-email-spearce@spearce.org","subject":"[JGIT PATCH 10/14] Make all AbstractTreeIterator implementations bi-directional","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-08-18T23:53:18Z","receivedAt":"2008-08-18T23:53:18Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"To support scanning ahead and then rewinding back to our prior\nlocation we need to allow all tree iterators to be moved both\nforward and backwards through their entries. The next(int)\nAPI replaces the simple next() by supplying the amount that\nthe iterator needs to move forward. A corresponding back(int)\nmethod supplies the opposite direction of travel.\n\nSome iterators like WorkingTreeIterator can efficiently move\nfoward and backwards any step because they have a direct 1:1\nmapping between positions of the iterator and an array index.\nOthers like CanonicalTreeParser must scan through their input\nbuffer, but can try to reduce the work needed on larger steps\nas they move past the undesired entries. DirCacheIterator is\na challenge because it needs to match each entry up onto the\nDirCacheTrees available at this level.\n\nThis API (and its implements) is really meant for peeking at\nthe next entry (or two) forward to see if there is a name (but\nnot mode) match during a TreeWalk. This is to help TreeWalk\ncatch a directory/file mode conflict and report it, despite\nthe directory and file variants of a name appearing at two\nvery different positions in the trees.\n\nSigned-off-by: Shawn O. Pearce \n---\n .../jgit/dircache/DirCacheIteratorTest.java | 2 +-\n .../jgit/treewalk/CanonicalTreeParserTest.java | 261 ++++++++++++++++++++\n .../jgit/dircache/DirCacheBuildIterator.java | 2 +-\n .../spearce/jgit/dircache/DirCacheIterator.java | 27 ++-\n .../jgit/treewalk/AbstractTreeIterator.java | 38 +++-\n .../spearce/jgit/treewalk/CanonicalTreeParser.java | 68 +++++-\n .../spearce/jgit/treewalk/EmptyTreeIterator.java | 7 +-\n .../src/org/spearce/jgit/treewalk/TreeWalk.java | 2 +-\n .../spearce/jgit/treewalk/WorkingTreeIterator.java | 10 +-\n 9 files changed, 398 insertions(+), 19 deletions(-)\n create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/treewalk/CanonicalTreeParserTest.java\n\ndiff --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\nindex 51b3c5a..047c989 100644\n--- a/org.spearce.jgit.test/tst/org/spearce/jgit/dircache/DirCacheIteratorTest.java\n+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/dircache/DirCacheIteratorTest.java\n@@ -78,7 +78,7 @@ public void testNoSubtree_NoTreeWalk() throws Exception {\n \n \t\tfinal DirCacheIterator i = new DirCacheIterator(dc);\n \t\tint pathIdx = 0;\n-\t\tfor (; !i.eof(); i.next()) {\n+\t\tfor (; !i.eof(); i.next(1)) {\n \t\t\tassertEquals(pathIdx, i.ptr);\n \t\t\tassertSame(ents[pathIdx], i.getDirCacheEntry());\n \t\t\tpathIdx++;\ndiff --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\nnew file mode 100644\nindex 0000000..fd92844\n--- /dev/null\n+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/treewalk/CanonicalTreeParserTest.java\n@@ -0,0 +1,261 @@\n+/*\n+ * Copyright (C) 2008, Google Inc.\n+ *\n+ * All rights reserved.\n+ *\n+ * Redistribution and use in source and binary forms, with or\n+ * without modification, are permitted provided that the following\n+ * conditions are met:\n+ *\n+ * - Redistributions of source code must retain the above copyright\n+ * notice, this list of conditions and the following disclaimer.\n+ *\n+ * - Redistributions in binary form must reproduce the above\n+ * copyright notice, this list of conditions and the following\n+ * disclaimer in the documentation and/or other materials provided\n+ * with the distribution.\n+ *\n+ * - Neither the name of the Git Development Community nor the\n+ * names of its contributors may be used to endorse or promote\n+ * products derived from this software without specific prior\n+ * written permission.\n+ *\n+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND\n+ * CONTRIBUTORS \"AS IS\" AND ANY EXPRESS OR IMPLIED WARRANTIES,\n+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES\n+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE\n+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR\n+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,\n+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT\n+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;\n+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER\n+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,\n+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)\n+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF\n+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.\n+ */\n+\n+package org.spearce.jgit.treewalk;\n+\n+import java.io.ByteArrayOutputStream;\n+\n+import junit.framework.TestCase;\n+\n+import org.spearce.jgit.lib.Constants;\n+import org.spearce.jgit.lib.FileMode;\n+import org.spearce.jgit.lib.ObjectId;\n+import org.spearce.jgit.util.RawParseUtils;\n+\n+public class CanonicalTreeParserTest extends TestCase {\n+\tprivate final CanonicalTreeParser ctp = new CanonicalTreeParser();\n+\n+\tprivate final FileMode m644 = FileMode.REGULAR_FILE;\n+\n+\tprivate final FileMode mt = FileMode.TREE;\n+\n+\tprivate final ObjectId hash_a = ObjectId\n+\t\t\t.fromString(\"6b9c715d21d5486e59083fb6071566aa6ecd4d42\");\n+\n+\tprivate final ObjectId hash_foo = ObjectId\n+\t\t\t.fromString(\"a213e8e25bb2442326e86cbfb9ef56319f482869\");\n+\n+\tprivate final ObjectId hash_sometree = ObjectId\n+\t\t\t.fromString(\"daf4bdb0d7bb24319810fe0e73aa317663448c93\");\n+\n+\tprivate byte[] tree1;\n+\n+\tprivate byte[] tree2;\n+\n+\tprivate byte[] tree3;\n+\n+\tpublic void setUp() throws Exception {\n+\t\tsuper.setUp();\n+\n+\t\ttree1 = mkree(entry(m644, \"a\", hash_a));\n+\t\ttree2 = mkree(entry(m644, \"a\", hash_a), entry(m644, \"foo\", hash_foo));\n+\t\ttree3 = mkree(entry(m644, \"a\", hash_a), entry(mt, \"b_sometree\",\n+\t\t\t\thash_sometree), entry(m644, \"foo\", hash_foo));\n+\t}\n+\n+\tprivate static byte[] mkree(final byte[]... data) throws Exception {\n+\t\tfinal ByteArrayOutputStream out = new ByteArrayOutputStream();\n+\t\tfor (final byte[] e : data)\n+\t\t\tout.write(e);\n+\t\treturn out.toByteArray();\n+\t}\n+\n+\tprivate static byte[] entry(final FileMode mode, final String name,\n+\t\t\tfinal ObjectId id) throws Exception {\n+\t\tfinal ByteArrayOutputStream out = new ByteArrayOutputStream();\n+\t\tmode.copyTo(out);\n+\t\tout.write(' ');\n+\t\tout.write(Constants.encode(name));\n+\t\tout.write(0);\n+\t\tid.copyRawTo(out);\n+\t\treturn out.toByteArray();\n+\t}\n+\n+\tprivate String path() {\n+\t\treturn RawParseUtils.decode(Constants.CHARSET, ctp.path,\n+\t\t\t\tctp.pathOffset, ctp.pathLen);\n+\t}\n+\n+\tpublic void testEmptyTree_AtEOF() throws Exception {\n+\t\tctp.reset(new byte[0]);\n+\t\tassertTrue(ctp.eof());\n+\t}\n+\n+\tpublic void testOneEntry_Forward() throws Exception {\n+\t\tctp.reset(tree1);\n+\n+\t\tassertFalse(ctp.eof());\n+\t\tassertEquals(m644.getBits(), ctp.mode);\n+\t\tassertEquals(\"a\", path());\n+\t\tassertEquals(hash_a, ctp.getEntryObjectId());\n+\n+\t\tctp.next(1);\n+\t\tassertTrue(ctp.eof());\n+\t}\n+\n+\tpublic void testTwoEntries_ForwardOneAtATime() throws Exception {\n+\t\tctp.reset(tree2);\n+\n+\t\tassertFalse(ctp.eof());\n+\t\tassertEquals(m644.getBits(), ctp.mode);\n+\t\tassertEquals(\"a\", path());\n+\t\tassertEquals(hash_a, ctp.getEntryObjectId());\n+\n+\t\tctp.next(1);\n+\t\tassertFalse(ctp.eof());\n+\t\tassertEquals(m644.getBits(), ctp.mode);\n+\t\tassertEquals(\"foo\", path());\n+\t\tassertEquals(hash_foo, ctp.getEntryObjectId());\n+\n+\t\tctp.next(1);\n+\t\tassertTrue(ctp.eof());\n+\t}\n+\n+\tpublic void testOneEntry_Seek1IsEOF() throws Exception {\n+\t\tctp.reset(tree1);\n+\t\tctp.next(1);\n+\t\tassertTrue(ctp.eof());\n+\t}\n+\n+\tpublic void testTwoEntries_Seek2IsEOF() throws Exception {\n+\t\tctp.reset(tree2);\n+\t\tctp.next(2);\n+\t\tassertTrue(ctp.eof());\n+\t}\n+\n+\tpublic void testThreeEntries_Seek3IsEOF() throws Exception {\n+\t\tctp.reset(tree3);\n+\t\tctp.next(3);\n+\t\tassertTrue(ctp.eof());\n+\t}\n+\n+\tpublic void testThreeEntries_Seek2() throws Exception {\n+\t\tctp.reset(tree3);\n+\n+\t\tctp.next(2);\n+\t\tassertFalse(ctp.eof());\n+\t\tassertFalse(ctp.eof());\n+\t\tassertEquals(m644.getBits(), ctp.mode);\n+\t\tassertEquals(\"foo\", path());\n+\t\tassertEquals(hash_foo, ctp.getEntryObjectId());\n+\n+\t\tctp.next(1);\n+\t\tassertTrue(ctp.eof());\n+\t}\n+\n+\tpublic void testOneEntry_Backwards() throws Exception {\n+\t\tctp.reset(tree1);\n+\t\tctp.next(1);\n+\t\tassertTrue(ctp.eof());\n+\n+\t\tctp.back(1);\n+\t\tassertFalse(ctp.eof());\n+\t\tassertEquals(m644.getBits(), ctp.mode);\n+\t\tassertEquals(\"a\", path());\n+\t\tassertEquals(hash_a, ctp.getEntryObjectId());\n+\t}\n+\n+\tpublic void testTwoEntries_BackwardsOneAtATime() throws Exception {\n+\t\tctp.reset(tree2);\n+\t\tctp.next(2);\n+\t\tassertTrue(ctp.eof());\n+\n+\t\tctp.back(1);\n+\t\tassertFalse(ctp.eof());\n+\t\tassertEquals(m644.getBits(), ctp.mode);\n+\t\tassertEquals(\"foo\", path());\n+\t\tassertEquals(hash_foo, ctp.getEntryObjectId());\n+\n+\t\tctp.back(1);\n+\t\tassertFalse(ctp.eof());\n+\t\tassertEquals(m644.getBits(), ctp.mode);\n+\t\tassertEquals(\"a\", path());\n+\t\tassertEquals(hash_a, ctp.getEntryObjectId());\n+\t}\n+\n+\tpublic void testTwoEntries_BackwardsTwo() throws Exception {\n+\t\tctp.reset(tree2);\n+\t\tctp.next(2);\n+\t\tassertTrue(ctp.eof());\n+\n+\t\tctp.back(2);\n+\t\tassertFalse(ctp.eof());\n+\t\tassertEquals(m644.getBits(), ctp.mode);\n+\t\tassertEquals(\"a\", path());\n+\t\tassertEquals(hash_a, ctp.getEntryObjectId());\n+\n+\t\tctp.next(1);\n+\t\tassertFalse(ctp.eof());\n+\t\tassertEquals(m644.getBits(), ctp.mode);\n+\t\tassertEquals(\"foo\", path());\n+\t\tassertEquals(hash_foo, ctp.getEntryObjectId());\n+\n+\t\tctp.next(1);\n+\t\tassertTrue(ctp.eof());\n+\t}\n+\n+\tpublic void testThreeEntries_BackwardsTwo() throws Exception {\n+\t\tctp.reset(tree3);\n+\t\tctp.next(3);\n+\t\tassertTrue(ctp.eof());\n+\n+\t\tctp.back(2);\n+\t\tassertFalse(ctp.eof());\n+\t\tassertEquals(mt.getBits(), ctp.mode);\n+\t\tassertEquals(\"b_sometree\", path());\n+\t\tassertEquals(hash_sometree, ctp.getEntryObjectId());\n+\n+\t\tctp.next(1);\n+\t\tassertFalse(ctp.eof());\n+\t\tassertEquals(m644.getBits(), ctp.mode);\n+\t\tassertEquals(\"foo\", path());\n+\t\tassertEquals(hash_foo, ctp.getEntryObjectId());\n+\n+\t\tctp.next(1);\n+\t\tassertTrue(ctp.eof());\n+\t}\n+\n+\tpublic void testBackwards_ConfusingPathName() throws Exception {\n+\t\tfinal String aVeryConfusingName = \"confusing 644 entry 755 and others\";\n+\t\tctp.reset(mkree(entry(m644, \"a\", hash_a), entry(mt, aVeryConfusingName,\n+\t\t\t\thash_sometree), entry(m644, \"foo\", hash_foo)));\n+\t\tctp.next(3);\n+\t\tassertTrue(ctp.eof());\n+\n+\t\tctp.back(2);\n+\t\tassertFalse(ctp.eof());\n+\t\tassertEquals(mt.getBits(), ctp.mode);\n+\t\tassertEquals(aVeryConfusingName, path());\n+\t\tassertEquals(hash_sometree, ctp.getEntryObjectId());\n+\n+\t\tctp.back(1);\n+\t\tassertFalse(ctp.eof());\n+\t\tassertEquals(m644.getBits(), ctp.mode);\n+\t\tassertEquals(\"a\", path());\n+\t\tassertEquals(hash_a, ctp.getEntryObjectId());\n+\t}\n+}\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheBuildIterator.java b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheBuildIterator.java\nindex aaec4fc..234ffd2 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheBuildIterator.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheBuildIterator.java\n@@ -112,7 +112,7 @@ public void skip() throws CorruptObjectException {\n \t\t\tbuilder.keep(ptr, currentSubtree.getEntrySpan());\n \t\telse\n \t\t\tbuilder.add(currentEntry);\n-\t\tnext();\n+\t\tnext(1);\n \t}\n \n \t@Override\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheIterator.java b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheIterator.java\nindex 248ae1e..84cefa5 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheIterator.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheIterator.java\n@@ -144,13 +144,28 @@ public boolean eof() {\n \t}\n \n \t@Override\n-\tpublic void next() {\n-\t\tif (currentSubtree != null)\n-\t\t\tptr += currentSubtree.getEntrySpan();\n-\t\telse\n-\t\t\tptr++;\n-\t\tif (!eof())\n+\tpublic void next(int delta) {\n+\t\twhile (--delta >= 0) {\n+\t\t\tif (currentSubtree != null)\n+\t\t\t\tptr += currentSubtree.getEntrySpan();\n+\t\t\telse\n+\t\t\t\tptr++;\n+\t\t\tif (eof())\n+\t\t\t\tbreak;\n+\t\t\tparseEntry();\n+\t\t}\n+\t}\n+\n+\t@Override\n+\tpublic void back(int delta) {\n+\t\twhile (--delta >= 0) {\n+\t\t\tif (currentSubtree != null)\n+\t\t\t\tnextSubtreePos--;\n+\t\t\tptr--;\n \t\t\tparseEntry();\n+\t\t\tif (currentSubtree != null)\n+\t\t\t\tptr -= currentSubtree.getEntrySpan() - 1;\n+\t\t}\n \t}\n \n \tprivate void parseEntry() {\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java\nindex 208adc7..8ec506c 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java\n@@ -349,7 +349,34 @@ public abstract AbstractTreeIterator createSubtreeIterator(Repository repo)\n \tpublic abstract boolean eof();\n \n \t/**\n-\t * Advance to the next tree entry, populating this iterator with its data.\n+\t * Move to next entry, populating this iterator with the entry data.\n+\t *

\n+\t * The delta indicates how many moves forward should occur. The most common\n+\t * delta is 1 to move to the next entry.\n+\t *

\n+\t * Implementations must populate the following members:\n+\t *

    \n+\t *
  • {@link #mode}
    • \n+\t *
  • {@link #path} (from {@link #pathOffset} to {@link #pathLen})
    • \n+\t *
  • {@link #pathLen}
    • \n+\t *
\n+\t * as well as any implementation dependent information necessary to\n+\t * accurately return data from {@link #idBuffer()} and {@link #idOffset()}\n+\t * when demanded.\n+\t * \n+\t * @param delta\n+\t * number of entries to move the iterator by. Must be a positive,\n+\t * non-zero integer.\n+\t * @throws CorruptObjectException\n+\t * the tree is invalid.\n+\t */\n+\tpublic abstract void next(int delta) throws CorruptObjectException;\n+\n+\t/**\n+\t * Move to prior entry, populating this iterator with the entry data.\n+\t *

\n+\t * The delta indicates how many moves backward should occur.The most common\n+\t * delta is 1 to move to the prior entry.\n \t *

\n \t * Implementations must populate the following members:\n \t *

    \n@@ -361,15 +388,18 @@ public abstract AbstractTreeIterator createSubtreeIterator(Repository repo)\n \t * accurately return data from {@link #idBuffer()} and {@link #idOffset()}\n \t * when demanded.\n \t * \n+\t * @param delta\n+\t * number of entries to move the iterator by. Must be a positive,\n+\t * non-zero integer.\n \t * @throws CorruptObjectException\n \t * the tree is invalid.\n \t */\n-\tpublic abstract void next() throws CorruptObjectException;\n+\tpublic abstract void back(int delta) throws CorruptObjectException;\n \n \t/**\n \t * Advance to the next tree entry, populating this iterator with its data.\n \t *

    \n-\t * This method behaves like {@link #next()} but is called by\n+\t * This method behaves like seek(1) but is called by\n \t * {@link TreeWalk} only if a {@link TreeFilter} was used and ruled out the\n \t * current entry from the results. In such cases this tree iterator may\n \t * perform special behavior.\n@@ -378,7 +408,7 @@ public abstract AbstractTreeIterator createSubtreeIterator(Repository repo)\n \t * the tree is invalid.\n \t */\n \tpublic void skip() throws CorruptObjectException {\n-\t\tnext();\n+\t\tnext(1);\n \t}\n \n \t/**\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/CanonicalTreeParser.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/CanonicalTreeParser.java\nindex ebcc787..111d03b 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/CanonicalTreeParser.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/CanonicalTreeParser.java\n@@ -39,7 +39,6 @@\n \n import java.io.IOException;\n \n-import org.spearce.jgit.errors.CorruptObjectException;\n import org.spearce.jgit.errors.IncorrectObjectTypeException;\n import org.spearce.jgit.errors.MissingObjectException;\n import org.spearce.jgit.lib.Constants;\n@@ -131,12 +130,75 @@ public boolean eof() {\n \t\treturn currPtr == raw.length;\n \t}\n \n-\tpublic void next() throws CorruptObjectException {\n-\t\tcurrPtr = nextPtr;\n+\t@Override\n+\tpublic void next(int delta) {\n+\t\tif (delta == 1) {\n+\t\t\t// Moving forward one is the most common case.\n+\t\t\t//\n+\t\t\tcurrPtr = nextPtr;\n+\t\t\tif (!eof())\n+\t\t\t\tparseEntry();\n+\t\t\treturn;\n+\t\t}\n+\n+\t\t// Fast skip over records, then parse the last one.\n+\t\t//\n+\t\tfinal int end = raw.length;\n+\t\tint ptr = nextPtr;\n+\t\twhile (--delta > 0 && ptr != end) {\n+\t\t\twhile (raw[ptr] != 0)\n+\t\t\t\tptr++;\n+\t\t\tptr += Constants.OBJECT_ID_LENGTH + 1;\n+\t\t}\n+\t\tif (delta != 0)\n+\t\t\tthrow new ArrayIndexOutOfBoundsException(delta);\n+\t\tcurrPtr = ptr;\n \t\tif (!eof())\n \t\t\tparseEntry();\n \t}\n \n+\t@Override\n+\tpublic void back(int delta) {\n+\t\tint ptr = currPtr;\n+\t\twhile (--delta >= 0) {\n+\t\t\tif (ptr == 0)\n+\t\t\t\tthrow new ArrayIndexOutOfBoundsException(delta);\n+\n+\t\t\t// Rewind back beyond the id and the null byte. Find the\n+\t\t\t// last space, this _might_ be the split between the mode\n+\t\t\t// and the path. Most paths in most trees do not contain a\n+\t\t\t// space so this prunes our search more quickly.\n+\t\t\t//\n+\t\t\tptr -= Constants.OBJECT_ID_LENGTH;\n+\t\t\twhile (raw[--ptr] != ' ')\n+\t\t\t\t/* nothing */;\n+\t\t\tif (--ptr < Constants.OBJECT_ID_LENGTH) {\n+\t\t\t\tif (delta != 0)\n+\t\t\t\t\tthrow new ArrayIndexOutOfBoundsException(delta);\n+\t\t\t\tptr = 0;\n+\t\t\t\tbreak;\n+\t\t\t}\n+\n+\t\t\t// Locate a position that matches \"\\0.{20}[0-7]\" such that\n+\t\t\t// the ptr will rest on the [0-7]. This must be the first\n+\t\t\t// byte of the mode. This search works because the path in\n+\t\t\t// the prior record must have a non-zero length and must not\n+\t\t\t// contain a null byte.\n+\t\t\t//\n+\t\t\tfor (int n;; ptr = n) {\n+\t\t\t\tn = ptr - 1;\n+\t\t\t\tfinal byte b = raw[n];\n+\t\t\t\tif ('0' <= b && b <= '7')\n+\t\t\t\t\tcontinue;\n+\t\t\t\tif (raw[n - Constants.OBJECT_ID_LENGTH] != 0)\n+\t\t\t\t\tcontinue;\n+\t\t\t\tbreak;\n+\t\t\t}\n+\t\t}\n+\t\tcurrPtr = ptr;\n+\t\tparseEntry();\n+\t}\n+\n \tprivate void parseEntry() {\n \t\tint ptr = currPtr;\n \t\tbyte c = raw[ptr++];\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/EmptyTreeIterator.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/EmptyTreeIterator.java\nindex c5dc4ad..232e3b1 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/EmptyTreeIterator.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/EmptyTreeIterator.java\n@@ -84,7 +84,12 @@ public boolean eof() {\n \t}\n \n \t@Override\n-\tpublic void next() throws CorruptObjectException {\n+\tpublic void next(final int delta) throws CorruptObjectException {\n+\t\t// Do nothing.\n+\t}\n+\n+\t@Override\n+\tpublic void back(final int delta) throws CorruptObjectException {\n \t\t// Do nothing.\n \t}\n \ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java\nindex 3bdef22..10cdebd 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java\n@@ -651,7 +651,7 @@ private void popEntriesEqual() throws CorruptObjectException {\n \t\tfor (int i = 0; i < trees.length; i++) {\n \t\t\tfinal AbstractTreeIterator t = trees[i];\n \t\t\tif (t.matches == ch) {\n-\t\t\t\tt.next();\n+\t\t\t\tt.next(1);\n \t\t\t\tt.matches = null;\n \t\t\t}\n \t\t}\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/WorkingTreeIterator.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/WorkingTreeIterator.java\nindex e81ff4a..41fd47b 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/WorkingTreeIterator.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/WorkingTreeIterator.java\n@@ -236,12 +236,18 @@ public boolean eof() {\n \t}\n \n \t@Override\n-\tpublic void next() throws CorruptObjectException {\n-\t\tptr++;\n+\tpublic void next(final int delta) throws CorruptObjectException {\n+\t\tptr += delta;\n \t\tif (!eof())\n \t\t\tparseEntry();\n \t}\n \n+\t@Override\n+\tpublic void back(final int delta) throws CorruptObjectException {\n+\t\tptr -= delta;\n+\t\tparseEntry();\n+\t}\n+\n \tprivate void parseEntry() {\n \t\tfinal Entry e = entries[ptr];\n \t\tmode = e.getMode().getBits();\n-- \n1.6.0.87.g2858d\n"},{"id":"87608","messageId":"1219103602-32222-12-git-send-email-spearce@spearce.org","threadId":"15078","inReplyTo":"1219103602-32222-11-git-send-email-spearce@spearce.org","subject":"[JGIT PATCH 11/14] Expose beginning of iterator indication from AbstractTreeIterator","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-08-18T23:53:19Z","receivedAt":"2008-08-18T23:53:19Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Callers like TreeWalk need to know if back(1) is going to be a valid\noperation for a given AbstractTreeIterator before they try to make a\ncall to move the iterator backwards. The new method first() returns\ntrue only if the iterator is already positioned on its first entry,\nin which case a call to back(n) (for any n) is invalid.\n\nSigned-off-by: Shawn O. Pearce \n---\n .../spearce/jgit/dircache/DirCacheIterator.java | 12 +++++++++++-\n .../jgit/treewalk/AbstractTreeIterator.java | 13 +++++++++++++\n .../spearce/jgit/treewalk/CanonicalTreeParser.java | 5 +++++\n .../spearce/jgit/treewalk/EmptyTreeIterator.java | 5 +++++\n .../spearce/jgit/treewalk/WorkingTreeIterator.java | 5 +++++\n 5 files changed, 39 insertions(+), 1 deletions(-)\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheIterator.java b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheIterator.java\nindex 84cefa5..8384723 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheIterator.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheIterator.java\n@@ -64,6 +64,9 @@\n \t/** The tree this iterator is walking. */\n \tprivate final DirCacheTree tree;\n \n+\t/** First position in this tree. */\n+\tprivate final int treeStart;\n+\n \t/** Last position in this tree. */\n \tprivate final int treeEnd;\n \n@@ -95,6 +98,7 @@\n \tpublic DirCacheIterator(final DirCache dc) {\n \t\tcache = dc;\n \t\ttree = dc.getCacheTree(true);\n+\t\ttreeStart = 0;\n \t\ttreeEnd = tree.getEntrySpan();\n \t\tsubtreeId = new byte[Constants.OBJECT_ID_LENGTH];\n \t\tif (!eof())\n@@ -105,7 +109,8 @@ protected DirCacheIterator(final DirCacheIterator p, final DirCacheTree dct) {\n \t\tsuper(p, p.path, p.pathLen + 1);\n \t\tcache = p.cache;\n \t\ttree = dct;\n-\t\ttreeEnd = p.ptr + tree.getEntrySpan();\n+\t\ttreeStart = p.ptr;\n+\t\ttreeEnd = treeStart + tree.getEntrySpan();\n \t\tsubtreeId = p.subtreeId;\n \t\tptr = p.ptr;\n \t\tparseEntry();\n@@ -139,6 +144,11 @@ public int idOffset() {\n \t}\n \n \t@Override\n+\tpublic boolean first() {\n+\t\treturn ptr == treeStart;\n+\t}\n+\n+\t@Override\n \tpublic boolean eof() {\n \t\treturn ptr == treeEnd;\n \t}\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java\nindex 8ec506c..c1b7ad8 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java\n@@ -340,6 +340,19 @@ public abstract AbstractTreeIterator createSubtreeIterator(Repository repo)\n \t\t\tthrows IncorrectObjectTypeException, IOException;\n \n \t/**\n+\t * Is this tree iterator positioned on its first entry?\n+\t *

    \n+\t * An iterator is positioned on the first entry if back(1)\n+\t * would be an invalid request as there is no entry before the current one.\n+\t *

    \n+\t * An empty iterator (one with no entries) will be\n+\t * first() && eof().\n+\t * \n+\t * @return true if the iterator is positioned on the first entry.\n+\t */\n+\tpublic abstract boolean first();\n+\n+\t/**\n \t * Is this tree iterator at its EOF point (no more entries)?\n \t *

    \n \t * An iterator is at EOF if there is no current entry.\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/CanonicalTreeParser.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/CanonicalTreeParser.java\nindex 111d03b..dcc53cd 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/CanonicalTreeParser.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/CanonicalTreeParser.java\n@@ -126,6 +126,11 @@ public int idOffset() {\n \t\treturn nextPtr - Constants.OBJECT_ID_LENGTH;\n \t}\n \n+\t@Override\n+\tpublic boolean first() {\n+\t\treturn currPtr == 0;\n+\t}\n+\n \tpublic boolean eof() {\n \t\treturn currPtr == raw.length;\n \t}\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/EmptyTreeIterator.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/EmptyTreeIterator.java\nindex 232e3b1..eaca04e 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/EmptyTreeIterator.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/EmptyTreeIterator.java\n@@ -79,6 +79,11 @@ public int idOffset() {\n \t}\n \n \t@Override\n+\tpublic boolean first() {\n+\t\treturn true;\n+\t}\n+\n+\t@Override\n \tpublic boolean eof() {\n \t\treturn true;\n \t}\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/WorkingTreeIterator.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/WorkingTreeIterator.java\nindex 41fd47b..9c53224 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/WorkingTreeIterator.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/WorkingTreeIterator.java\n@@ -231,6 +231,11 @@ public int idOffset() {\n \t}\n \n \t@Override\n+\tpublic boolean first() {\n+\t\treturn ptr == 0;\n+\t}\n+\n+\t@Override\n \tpublic boolean eof() {\n \t\treturn ptr == entryCnt;\n \t}\n-- \n1.6.0.87.g2858d\n"},{"id":"87609","messageId":"1219103602-32222-13-git-send-email-spearce@spearce.org","threadId":"15078","inReplyTo":"1219103602-32222-12-git-send-email-spearce@spearce.org","subject":"[JGIT PATCH 12/14] Allow application code to set ObjectIds in DirCacheEntry","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-08-18T23:53:20Z","receivedAt":"2008-08-18T23:53:20Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"We support setting the ObjectId both from AnyObjectId (as we copy it)\nand from a raw byte[] (as we are really copying into a raw byte[]).\nThe latter form is the most efficient as it probably permits callers\nto avoid unnecessary conversion to some form of AnyObjectId.\n\nSigned-off-by: Shawn O. Pearce \n---\n .../org/spearce/jgit/dircache/DirCacheEntry.java | 26 ++++++++++++++++++++\n 1 files changed, 26 insertions(+), 0 deletions(-)\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheEntry.java b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheEntry.java\nindex 011bc16..a83cc78 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheEntry.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheEntry.java\n@@ -43,6 +43,7 @@\n import java.nio.ByteBuffer;\n import java.util.Arrays;\n \n+import org.spearce.jgit.lib.AnyObjectId;\n import org.spearce.jgit.lib.Constants;\n import org.spearce.jgit.lib.FileMode;\n import org.spearce.jgit.lib.ObjectId;\n@@ -346,6 +347,31 @@ public ObjectId getObjectId() {\n \t}\n \n \t/**\n+\t * Set the ObjectId for the entry.\n+\t * \n+\t * @param id\n+\t * new object identifier for the entry. May be\n+\t * {@link ObjectId#zeroId()} to remove the current identifier.\n+\t */\n+\tpublic void setObjectId(final AnyObjectId id) {\n+\t\tid.copyRawTo(idBuffer(), idOffset());\n+\t}\n+\n+\t/**\n+\t * Set the ObjectId for the entry from the raw binary representation.\n+\t * \n+\t * @param bs\n+\t * the raw byte buffer to read from. At least 20 bytes after p\n+\t * must be available within this byte array.\n+\t * @param p\n+\t * position to read the first byte of data from.\n+\t */\n+\tpublic void setObjectIdFromRaw(final byte[] bs, final int p) {\n+\t\tfinal int n = Constants.OBJECT_ID_LENGTH;\n+\t\tSystem.arraycopy(bs, p, idBuffer(), idOffset(), n);\n+\t}\n+\n+\t/**\n \t * Get the entry's complete path.\n \t *

    \n \t * This method is not very efficient and is primarily meant for debugging\n-- \n1.6.0.87.g2858d\n"},{"id":"87612","messageId":"1219103602-32222-14-git-send-email-spearce@spearce.org","threadId":"15078","inReplyTo":"1219103602-32222-13-git-send-email-spearce@spearce.org","subject":"[JGIT PATCH 13/14] Create NameConflictTreeWalk to transparently detect D/F conflicts","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-08-18T23:53:21Z","receivedAt":"2008-08-18T23:53:21Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"When performing a merge between two or more tree iterators we really\nneed to be able to detect a directory-file conflict and handle it as\na single step of the TreeWalk iteration. This way we can merge say\nthree iterators together:\n\n - commit $A\n - commit $B\n - working tree\n\nWhere the working tree is moving from $A to $B and the file path\n\"foo\" has been changed from being a file in $A to a directory in\ncommit $B. To make this change effective we must delete \"foo\"\nand then enter the \"foo\" subtree to create the directory and\nthe paths within it.\n\nThis walk implementation is outside of TreeWalk as it is not a\ntrivial operation. Applications should only use this variant\nwhen conflict handling is absolutely necessary. Basic commit\nfiltering (such as done by RevWalk) does not need this support\nso we really don't want to bog down RevWalk's critical loop.\n\nSigned-off-by: Shawn O. Pearce \n---\n .../jgit/treewalk/AbstractTreeIterator.java | 7 +\n .../jgit/treewalk/NameConflictTreeWalk.java | 237 ++++++++++++++++++++\n .../src/org/spearce/jgit/treewalk/TreeWalk.java | 12 +-\n 3 files changed, 251 insertions(+), 5 deletions(-)\n create mode 100644 org.spearce.jgit/src/org/spearce/jgit/treewalk/NameConflictTreeWalk.java\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java\nindex c1b7ad8..31ccebe 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java\n@@ -83,6 +83,13 @@\n \tAbstractTreeIterator matches;\n \n \t/**\n+\t * Number of entries we moved forward to force a D/F conflict match.\n+\t * \n+\t * @see NameConflictTreeWalk\n+\t */\n+\tint matchShift;\n+\n+\t/**\n \t * Mode bits for the current entry.\n \t *

    \n \t * A numerical value from FileMode is usually faster for an iterator to\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/NameConflictTreeWalk.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/NameConflictTreeWalk.java\nnew file mode 100644\nindex 0000000..fdfba4e\n--- /dev/null\n+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/NameConflictTreeWalk.java\n@@ -0,0 +1,237 @@\n+/*\n+ * Copyright (C) 2008, Google Inc.\n+ *\n+ * All rights reserved.\n+ *\n+ * Redistribution and use in source and binary forms, with or\n+ * without modification, are permitted provided that the following\n+ * conditions are met:\n+ *\n+ * - Redistributions of source code must retain the above copyright\n+ * notice, this list of conditions and the following disclaimer.\n+ *\n+ * - Redistributions in binary form must reproduce the above\n+ * copyright notice, this list of conditions and the following\n+ * disclaimer in the documentation and/or other materials provided\n+ * with the distribution.\n+ *\n+ * - Neither the name of the Git Development Community nor the\n+ * names of its contributors may be used to endorse or promote\n+ * products derived from this software without specific prior\n+ * written permission.\n+ *\n+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND\n+ * CONTRIBUTORS \"AS IS\" AND ANY EXPRESS OR IMPLIED WARRANTIES,\n+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES\n+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE\n+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR\n+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,\n+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT\n+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;\n+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER\n+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,\n+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)\n+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF\n+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.\n+ */\n+\n+package org.spearce.jgit.treewalk;\n+\n+import org.spearce.jgit.dircache.DirCacheBuilder;\n+import org.spearce.jgit.errors.CorruptObjectException;\n+import org.spearce.jgit.lib.FileMode;\n+import org.spearce.jgit.lib.Repository;\n+\n+/**\n+ * Specialized TreeWalk to detect directory-file (D/F) name conflicts.\n+ *

    \n+ * Due to the way a Git tree is organized the standard {@link TreeWalk} won't\n+ * easily find a D/F conflict when merging two or more trees together. In the\n+ * standard TreeWalk the file will be returned first, and then much later the\n+ * directory will be returned. This makes it impossible for the application to\n+ * efficiently detect and handle the conflict.\n+ *

    \n+ * Using this walk implementation causes the directory to report earlier than\n+ * usual, at the same time as the non-directory entry. This permits the\n+ * application to handle the D/F conflict in a single step. The directory is\n+ * returned only once, so it does not get returned later in the iteration.\n+ *

    \n+ * When a D/F conflict is detected {@link TreeWalk#isSubtree()} will return true\n+ * and {@link TreeWalk#enterSubtree()} will recurse into the subtree, no matter\n+ * which iterator originally supplied the subtree.\n+ *

    \n+ * Because conflicted directories report early, using this walk implementation\n+ * to populate a {@link DirCacheBuilder} may cause the automatic resorting to\n+ * run and fix the entry ordering.\n+ *

    \n+ * This walk implementation requires more CPU to implement a look-ahead and a\n+ * look-behind to merge a D/F pair together, or to skip a previously reported\n+ * directory. In typical Git repositories the look-ahead cost is 0 and the\n+ * look-behind doesn't trigger, as users tend not to create trees which contain\n+ * both \"foo\" as a directory and \"foo.c\" as a file.\n+ *

    \n+ * In the worst-case however several thousand look-ahead steps per walk step may\n+ * be necessary, making the overhead quite significant. Since this worst-case\n+ * should never happen this walk implementation has made the time/space tradeoff\n+ * in favor of more-time/less-space, as that better suits the typical case.\n+ */\n+public class NameConflictTreeWalk extends TreeWalk {\n+\tprivate static final int TREE_MODE = FileMode.TREE.getBits();\n+\n+\t/**\n+\t * Create a new tree walker for a given repository.\n+\t * \n+\t * @param repo\n+\t * the repository the walker will obtain data from.\n+\t */\n+\tpublic NameConflictTreeWalk(final Repository repo) {\n+\t\tsuper(repo);\n+\t}\n+\n+\t@Override\n+\tAbstractTreeIterator min() throws CorruptObjectException {\n+\t\tfor (;;) {\n+\t\t\tfinal AbstractTreeIterator minRef = super.min();\n+\t\t\tif (minRef.eof())\n+\t\t\t\treturn minRef;\n+\n+\t\t\tif (FileMode.TREE.equals(minRef.mode)) {\n+\t\t\t\tif (skipEntry(minRef)) {\n+\t\t\t\t\tfor (final AbstractTreeIterator t : trees) {\n+\t\t\t\t\t\tif (t.matches == minRef) {\n+\t\t\t\t\t\t\tt.next(1);\n+\t\t\t\t\t\t\tt.matches = null;\n+\t\t\t\t\t\t}\n+\t\t\t\t\t}\n+\t\t\t\t\tcontinue;\n+\t\t\t\t}\n+\t\t\t\treturn minRef;\n+\t\t\t}\n+\n+\t\t\treturn combineDF(minRef);\n+\t\t}\n+\t}\n+\n+\tprivate boolean skipEntry(final AbstractTreeIterator minRef)\n+\t\t\tthrows CorruptObjectException {\n+\t\t// A tree D/F may have been handled earlier. We need to\n+\t\t// not report this path if it has already been reported.\n+\t\t//\n+\t\tfor (final AbstractTreeIterator t : trees) {\n+\t\t\tif (t.matches == minRef || t.first())\n+\t\t\t\tcontinue;\n+\n+\t\t\tint stepsBack = 0;\n+\t\t\tfor (;;) {\n+\t\t\t\tstepsBack++;\n+\t\t\t\tt.back(1);\n+\n+\t\t\t\tfinal int cmp = t.pathCompare(minRef, 0);\n+\t\t\t\tif (cmp == 0) {\n+\t\t\t\t\t// We have already seen this \"$path\" before. Skip it.\n+\t\t\t\t\t//\n+\t\t\t\t\tt.next(stepsBack);\n+\t\t\t\t\treturn true;\n+\t\t\t\t} else if (cmp < 0 || t.first()) {\n+\t\t\t\t\t// We cannot find \"$path\" in t; it will never appear.\n+\t\t\t\t\t//\n+\t\t\t\t\tt.next(stepsBack);\n+\t\t\t\t\tbreak;\n+\t\t\t\t}\n+\t\t\t}\n+\t\t}\n+\n+\t\t// We have never seen the current path before.\n+\t\t//\n+\t\treturn false;\n+\t}\n+\n+\tprivate AbstractTreeIterator combineDF(final AbstractTreeIterator minRef)\n+\t\t\tthrows CorruptObjectException {\n+\t\t// Look for a possible D/F conflict forward in the tree(s)\n+\t\t// as there may be a \"$path/\" which matches \"$path\". Make\n+\t\t// such entries match this entry.\n+\t\t//\n+\t\tAbstractTreeIterator treeMatch = null;\n+\t\tfor (final AbstractTreeIterator t : trees) {\n+\t\t\tif (t.matches == minRef || t.eof())\n+\t\t\t\tcontinue;\n+\n+\t\t\tfor (;;) {\n+\t\t\t\tfinal int cmp = t.pathCompare(minRef, TREE_MODE);\n+\t\t\t\tif (cmp < 0) {\n+\t\t\t\t\t// The \"$path/\" may still appear later.\n+\t\t\t\t\t//\n+\t\t\t\t\tt.matchShift++;\n+\t\t\t\t\tt.next(1);\n+\t\t\t\t\tif (t.eof()) {\n+\t\t\t\t\t\tt.back(t.matchShift);\n+\t\t\t\t\t\tt.matchShift = 0;\n+\t\t\t\t\t\tbreak;\n+\t\t\t\t\t}\n+\t\t\t\t} else if (cmp == 0) {\n+\t\t\t\t\t// We have a conflict match here.\n+\t\t\t\t\t//\n+\t\t\t\t\tt.matches = minRef;\n+\t\t\t\t\ttreeMatch = t;\n+\t\t\t\t\tbreak;\n+\t\t\t\t} else {\n+\t\t\t\t\t// A conflict match is not possible.\n+\t\t\t\t\t//\n+\t\t\t\t\tif (t.matchShift != 0) {\n+\t\t\t\t\t\tt.back(t.matchShift);\n+\t\t\t\t\t\tt.matchShift = 0;\n+\t\t\t\t\t}\n+\t\t\t\t\tbreak;\n+\t\t\t\t}\n+\t\t\t}\n+\t\t}\n+\n+\t\tif (treeMatch != null) {\n+\t\t\t// If we do have a conflict use one of the directory\n+\t\t\t// matching iterators instead of the file iterator.\n+\t\t\t// This way isSubtree is true and isRecursive works.\n+\t\t\t//\n+\t\t\tfor (final AbstractTreeIterator t : trees)\n+\t\t\t\tif (t.matches == minRef)\n+\t\t\t\t\tt.matches = treeMatch;\n+\t\t\treturn treeMatch;\n+\t\t}\n+\n+\t\treturn minRef;\n+\t}\n+\n+\t@Override\n+\tvoid popEntriesEqual() throws CorruptObjectException {\n+\t\tfinal AbstractTreeIterator ch = currentHead;\n+\t\tfor (int i = 0; i < trees.length; i++) {\n+\t\t\tfinal AbstractTreeIterator t = trees[i];\n+\t\t\tif (t.matches == ch) {\n+\t\t\t\tif (t.matchShift == 0)\n+\t\t\t\t\tt.next(1);\n+\t\t\t\telse {\n+\t\t\t\t\tt.back(t.matchShift);\n+\t\t\t\t\tt.matchShift = 0;\n+\t\t\t\t}\n+\t\t\t\tt.matches = null;\n+\t\t\t}\n+\t\t}\n+\t}\n+\n+\t@Override\n+\tvoid skipEntriesEqual() throws CorruptObjectException {\n+\t\tfinal AbstractTreeIterator ch = currentHead;\n+\t\tfor (int i = 0; i < trees.length; i++) {\n+\t\t\tfinal AbstractTreeIterator t = trees[i];\n+\t\t\tif (t.matches == ch) {\n+\t\t\t\tif (t.matchShift == 0)\n+\t\t\t\t\tt.skip();\n+\t\t\t\telse {\n+\t\t\t\t\tt.back(t.matchShift);\n+\t\t\t\t\tt.matchShift = 0;\n+\t\t\t\t}\n+\t\t\t\tt.matches = null;\n+\t\t\t}\n+\t\t}\n+\t}\n+}\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java\nindex 10cdebd..7a09878 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java\n@@ -143,7 +143,7 @@ public static TreeWalk forPath(final Repository db, final String path,\n \n \tprivate TreeFilter filter;\n \n-\tprivate AbstractTreeIterator[] trees;\n+\tAbstractTreeIterator[] trees;\n \n \tprivate boolean recursive;\n \n@@ -151,7 +151,7 @@ public static TreeWalk forPath(final Repository db, final String path,\n \n \tprivate boolean advance;\n \n-\tprivate AbstractTreeIterator currentHead;\n+\tAbstractTreeIterator currentHead;\n \n \t/**\n \t * Create a new tree walker for a given repository.\n@@ -275,6 +275,7 @@ public void reset(final ObjectId[] ids) throws MissingObjectException,\n \t\t\t\t\to = o.parent;\n \t\t\t\tif (o instanceof CanonicalTreeParser) {\n \t\t\t\t\to.matches = null;\n+\t\t\t\t\to.matchShift = 0;\n \t\t\t\t\t((CanonicalTreeParser) o).reset(db, ids[i]);\n \t\t\t\t\tr[i] = o;\n \t\t\t\t\tcontinue;\n@@ -338,6 +339,7 @@ public int addTree(final AbstractTreeIterator p)\n \t\tSystem.arraycopy(trees, 0, newTrees, 0, n);\n \t\tnewTrees[n] = p;\n \t\tp.matches = null;\n+\t\tp.matchShift = 0;\n \n \t\ttrees = newTrees;\n \t\treturn n;\n@@ -621,7 +623,7 @@ public void enterSubtree() throws MissingObjectException,\n \t\tSystem.arraycopy(tmp, 0, trees, 0, trees.length);\n \t}\n \n-\tprivate AbstractTreeIterator min() {\n+\tAbstractTreeIterator min() throws CorruptObjectException {\n \t\tint i = 0;\n \t\tAbstractTreeIterator minRef = trees[i];\n \t\twhile (minRef.eof() && ++i < trees.length)\n@@ -646,7 +648,7 @@ private AbstractTreeIterator min() {\n \t\treturn minRef;\n \t}\n \n-\tprivate void popEntriesEqual() throws CorruptObjectException {\n+\tvoid popEntriesEqual() throws CorruptObjectException {\n \t\tfinal AbstractTreeIterator ch = currentHead;\n \t\tfor (int i = 0; i < trees.length; i++) {\n \t\t\tfinal AbstractTreeIterator t = trees[i];\n@@ -657,7 +659,7 @@ private void popEntriesEqual() throws CorruptObjectException {\n \t\t}\n \t}\n \n-\tprivate void skipEntriesEqual() throws CorruptObjectException {\n+\tvoid skipEntriesEqual() throws CorruptObjectException {\n \t\tfinal AbstractTreeIterator ch = currentHead;\n \t\tfor (int i = 0; i < trees.length; i++) {\n \t\t\tfinal AbstractTreeIterator t = trees[i];\n-- \n1.6.0.87.g2858d\n"},{"id":"87611","messageId":"1219103602-32222-15-git-send-email-spearce@spearce.org","threadId":"15078","inReplyTo":"1219103602-32222-14-git-send-email-spearce@spearce.org","subject":"[JGIT PATCH 14/14] Add test case for NameConflictTreeWalk","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-08-18T23:53:22Z","receivedAt":"2008-08-18T23:53:22Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Signed-off-by: Shawn O. Pearce \n---\n .../jgit/treewalk/NameConflictTreeWalkTest.java | 205 ++++++++++++++++++++\n 1 files changed, 205 insertions(+), 0 deletions(-)\n create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/treewalk/NameConflictTreeWalkTest.java\n\ndiff --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\nnew file mode 100644\nindex 0000000..8ab7f93\n--- /dev/null\n+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/treewalk/NameConflictTreeWalkTest.java\n@@ -0,0 +1,205 @@\n+/*\n+ * Copyright (C) 2008, Google Inc.\n+ *\n+ * All rights reserved.\n+ *\n+ * Redistribution and use in source and binary forms, with or\n+ * without modification, are permitted provided that the following\n+ * conditions are met:\n+ *\n+ * - Redistributions of source code must retain the above copyright\n+ * notice, this list of conditions and the following disclaimer.\n+ *\n+ * - Redistributions in binary form must reproduce the above\n+ * copyright notice, this list of conditions and the following\n+ * disclaimer in the documentation and/or other materials provided\n+ * with the distribution.\n+ *\n+ * - Neither the name of the Git Development Community nor the\n+ * names of its contributors may be used to endorse or promote\n+ * products derived from this software without specific prior\n+ * written permission.\n+ *\n+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND\n+ * CONTRIBUTORS \"AS IS\" AND ANY EXPRESS OR IMPLIED WARRANTIES,\n+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES\n+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE\n+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR\n+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,\n+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT\n+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;\n+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER\n+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,\n+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)\n+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF\n+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.\n+ */\n+\n+package org.spearce.jgit.treewalk;\n+\n+import java.io.ByteArrayInputStream;\n+\n+import org.spearce.jgit.dircache.DirCache;\n+import org.spearce.jgit.dircache.DirCacheBuilder;\n+import org.spearce.jgit.dircache.DirCacheEntry;\n+import org.spearce.jgit.dircache.DirCacheIterator;\n+import org.spearce.jgit.lib.Constants;\n+import org.spearce.jgit.lib.FileMode;\n+import org.spearce.jgit.lib.ObjectWriter;\n+import org.spearce.jgit.lib.RepositoryTestCase;\n+\n+public class NameConflictTreeWalkTest extends RepositoryTestCase {\n+\tprivate static final FileMode TREE = FileMode.TREE;\n+\n+\tprivate static final FileMode SYMLINK = FileMode.SYMLINK;\n+\n+\tprivate static final FileMode MISSING = FileMode.MISSING;\n+\n+\tprivate static final FileMode REGULAR_FILE = FileMode.REGULAR_FILE;\n+\n+\tprivate static final FileMode EXECUTABLE_FILE = FileMode.EXECUTABLE_FILE;\n+\n+\tpublic void testNoDF_NoGap() throws Exception {\n+\t\tfinal DirCache tree0 = DirCache.read(db);\n+\t\tfinal DirCache tree1 = DirCache.read(db);\n+\t\t{\n+\t\t\tfinal DirCacheBuilder b0 = tree0.builder();\n+\t\t\tfinal DirCacheBuilder b1 = tree1.builder();\n+\n+\t\t\tb0.add(makeEntry(\"a\", REGULAR_FILE));\n+\t\t\tb0.add(makeEntry(\"a.b\", EXECUTABLE_FILE));\n+\t\t\tb1.add(makeEntry(\"a/b\", REGULAR_FILE));\n+\t\t\tb0.add(makeEntry(\"a0b\", SYMLINK));\n+\n+\t\t\tb0.finish();\n+\t\t\tb1.finish();\n+\t\t\tassertEquals(3, tree0.getEntryCount());\n+\t\t\tassertEquals(1, tree1.getEntryCount());\n+\t\t}\n+\n+\t\tfinal TreeWalk tw = new TreeWalk(db);\n+\t\ttw.reset();\n+\t\ttw.addTree(new DirCacheIterator(tree0));\n+\t\ttw.addTree(new DirCacheIterator(tree1));\n+\n+\t\tassertModes(\"a\", REGULAR_FILE, MISSING, tw);\n+\t\tassertModes(\"a.b\", EXECUTABLE_FILE, MISSING, tw);\n+\t\tassertModes(\"a\", MISSING, TREE, tw);\n+\t\ttw.enterSubtree();\n+\t\tassertModes(\"a/b\", MISSING, REGULAR_FILE, tw);\n+\t\tassertModes(\"a0b\", SYMLINK, MISSING, tw);\n+\t}\n+\n+\tpublic void testDF_NoGap() throws Exception {\n+\t\tfinal DirCache tree0 = DirCache.read(db);\n+\t\tfinal DirCache tree1 = DirCache.read(db);\n+\t\t{\n+\t\t\tfinal DirCacheBuilder b0 = tree0.builder();\n+\t\t\tfinal DirCacheBuilder b1 = tree1.builder();\n+\n+\t\t\tb0.add(makeEntry(\"a\", REGULAR_FILE));\n+\t\t\tb0.add(makeEntry(\"a.b\", EXECUTABLE_FILE));\n+\t\t\tb1.add(makeEntry(\"a/b\", REGULAR_FILE));\n+\t\t\tb0.add(makeEntry(\"a0b\", SYMLINK));\n+\n+\t\t\tb0.finish();\n+\t\t\tb1.finish();\n+\t\t\tassertEquals(3, tree0.getEntryCount());\n+\t\t\tassertEquals(1, tree1.getEntryCount());\n+\t\t}\n+\n+\t\tfinal NameConflictTreeWalk tw = new NameConflictTreeWalk(db);\n+\t\ttw.reset();\n+\t\ttw.addTree(new DirCacheIterator(tree0));\n+\t\ttw.addTree(new DirCacheIterator(tree1));\n+\n+\t\tassertModes(\"a\", REGULAR_FILE, TREE, tw);\n+\t\tassertTrue(tw.isSubtree());\n+\t\ttw.enterSubtree();\n+\t\tassertModes(\"a/b\", MISSING, REGULAR_FILE, tw);\n+\t\tassertModes(\"a.b\", EXECUTABLE_FILE, MISSING, tw);\n+\t\tassertModes(\"a0b\", SYMLINK, MISSING, tw);\n+\t}\n+\n+\tpublic void testDF_GapByOne() throws Exception {\n+\t\tfinal DirCache tree0 = DirCache.read(db);\n+\t\tfinal DirCache tree1 = DirCache.read(db);\n+\t\t{\n+\t\t\tfinal DirCacheBuilder b0 = tree0.builder();\n+\t\t\tfinal DirCacheBuilder b1 = tree1.builder();\n+\n+\t\t\tb0.add(makeEntry(\"a\", REGULAR_FILE));\n+\t\t\tb0.add(makeEntry(\"a.b\", EXECUTABLE_FILE));\n+\t\t\tb1.add(makeEntry(\"a.b\", EXECUTABLE_FILE));\n+\t\t\tb1.add(makeEntry(\"a/b\", REGULAR_FILE));\n+\t\t\tb0.add(makeEntry(\"a0b\", SYMLINK));\n+\n+\t\t\tb0.finish();\n+\t\t\tb1.finish();\n+\t\t\tassertEquals(3, tree0.getEntryCount());\n+\t\t\tassertEquals(2, tree1.getEntryCount());\n+\t\t}\n+\n+\t\tfinal NameConflictTreeWalk tw = new NameConflictTreeWalk(db);\n+\t\ttw.reset();\n+\t\ttw.addTree(new DirCacheIterator(tree0));\n+\t\ttw.addTree(new DirCacheIterator(tree1));\n+\n+\t\tassertModes(\"a\", REGULAR_FILE, TREE, tw);\n+\t\tassertTrue(tw.isSubtree());\n+\t\ttw.enterSubtree();\n+\t\tassertModes(\"a/b\", MISSING, REGULAR_FILE, tw);\n+\t\tassertModes(\"a.b\", EXECUTABLE_FILE, EXECUTABLE_FILE, tw);\n+\t\tassertModes(\"a0b\", SYMLINK, MISSING, tw);\n+\t}\n+\n+\tpublic void testDF_SkipsSeenSubtree() throws Exception {\n+\t\tfinal DirCache tree0 = DirCache.read(db);\n+\t\tfinal DirCache tree1 = DirCache.read(db);\n+\t\t{\n+\t\t\tfinal DirCacheBuilder b0 = tree0.builder();\n+\t\t\tfinal DirCacheBuilder b1 = tree1.builder();\n+\n+\t\t\tb0.add(makeEntry(\"a\", REGULAR_FILE));\n+\t\t\tb1.add(makeEntry(\"a.b\", EXECUTABLE_FILE));\n+\t\t\tb1.add(makeEntry(\"a/b\", REGULAR_FILE));\n+\t\t\tb0.add(makeEntry(\"a0b\", SYMLINK));\n+\t\t\tb1.add(makeEntry(\"a0b\", SYMLINK));\n+\n+\t\t\tb0.finish();\n+\t\t\tb1.finish();\n+\t\t\tassertEquals(2, tree0.getEntryCount());\n+\t\t\tassertEquals(3, tree1.getEntryCount());\n+\t\t}\n+\n+\t\tfinal NameConflictTreeWalk tw = new NameConflictTreeWalk(db);\n+\t\ttw.reset();\n+\t\ttw.addTree(new DirCacheIterator(tree0));\n+\t\ttw.addTree(new DirCacheIterator(tree1));\n+\n+\t\tassertModes(\"a\", REGULAR_FILE, TREE, tw);\n+\t\tassertTrue(tw.isSubtree());\n+\t\ttw.enterSubtree();\n+\t\tassertModes(\"a/b\", MISSING, REGULAR_FILE, tw);\n+\t\tassertModes(\"a.b\", MISSING, EXECUTABLE_FILE, tw);\n+\t\tassertModes(\"a0b\", SYMLINK, SYMLINK, tw);\n+\t}\n+\n+\tprivate DirCacheEntry makeEntry(final String path, final FileMode mode)\n+\t\t\tthrows Exception {\n+\t\tfinal byte[] pathBytes = Constants.encode(path);\n+\t\tfinal DirCacheEntry ent = new DirCacheEntry(path);\n+\t\tent.setFileMode(mode);\n+\t\tent.setObjectId(new ObjectWriter(db).computeBlobSha1(pathBytes.length,\n+\t\t\t\tnew ByteArrayInputStream(pathBytes)));\n+\t\treturn ent;\n+\t}\n+\n+\tprivate static void assertModes(final String path, final FileMode mode0,\n+\t\t\tfinal FileMode mode1, final TreeWalk tw) throws Exception {\n+\t\tassertTrue(\"has \" + path, tw.next());\n+\t\tassertEquals(path, tw.getPathString());\n+\t\tassertEquals(mode0, tw.getFileMode(0));\n+\t\tassertEquals(mode1, tw.getFileMode(1));\n+\t}\n+}\n-- \n1.6.0.87.g2858d\n"},{"id":"87618","messageId":"7v7iadlv7c.fsf@gitster.siamese.dyndns.org","threadId":"15078","inReplyTo":"1219103602-32222-2-git-send-email-spearce@spearce.org","subject":"Re: [JGIT PATCH 01/14] Detect path names which overflow the name length field in the index","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2008-08-19T00:11:51Z","receivedAt":"2008-08-19T00:11:51Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Shawn O. Pearce\" writes:\n\n> C Git allows a path name to be longer than 4095 bytes by storing 4095\n> into the path name length field within flags and then searching for a\n> null terminator at the end of the path name, instead of relying on the\n> length indicatior.\n\nThis reminds me.\n\nIn the longer term, we should make this \"CE_NAMEMASK gives the real length\nfor sane names but otherwise we need to count\" merely a property of the\non-disk index structure. In-core index should gain a new ce_namelen field\nthat records the real name (even when it is longer than the mask would\npermit). IOW, the knowledge of CE_NAMEMASK should be confined to\nread_index_from() and ce_write_entry().\n\nI expect this to be a relatively easy janitor project; hint, hint...\n"},{"id":"87666","messageId":"1219135931.3184.473.camel@pmac.infradead.org","threadId":"15078","inReplyTo":"1219103602-32222-1-git-send-email-spearce@spearce.org","subject":"Re: [JGIT PATCH 00/14] TreeWalk D/F conflict detection","fromName":"David Woodhouse","fromEmail":"dwmw2@infradead.org","sentAt":"2008-08-19T08:52:11Z","receivedAt":"2008-08-19T08:52:11Z","isPatch":true,"sender":{"key":"dwmw2@infradead.org","avatar":"https://gravatar.com/avatar/7afd4f07e0cf7d7e046ae2d23678296b37777c96488e6f3451e78a5514154ebd?d=mp&s=160"},"body":"On Mon, 2008-08-18 at 16:53 -0700, Shawn O. Pearce wrote:\n> This series is about fixing the \"mistake\" in Git trees where\n> subtrees sort as through their name is \"path/\" and not \"path\".\n\nEr, really? Does that mean this commit is broken, then?\n\nhttp://git.kernel.org/?p=linux/kernel/git/dwmw2/misc-git-hacks.git;a=commitdiff;h=fc1b73da\n\nI shouldn't need to know that -- I'd _really_ like a version of\n'git-hash-object -t tree' which validates and sorts its input for me.\nAnd maybe even takes input in _text_ form, so I don't have to convert\nthe sha1 to binary.\n\n-- \nDavid Woodhouse Open Source Technology Centre\nDavid.Woodhouse@intel.com Intel Corporation\n"},{"id":"87696","messageId":"20080819142445.GB20947@spearce.org","threadId":"15078","inReplyTo":"1219135931.3184.473.camel@pmac.infradead.org","subject":"Re: [JGIT PATCH 00/14] TreeWalk D/F conflict detection","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-08-19T14:24:45Z","receivedAt":"2008-08-19T14:24:45Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"David Woodhouse wrote:\n> On Mon, 2008-08-18 at 16:53 -0700, Shawn O. Pearce wrote:\n> > This series is about fixing the \"mistake\" in Git trees where\n> > subtrees sort as through their name is \"path/\" and not \"path\".\n> \n> Er, really? Does that mean this commit is broken, then?\n> \n> http://git.kernel.org/?p=linux/kernel/git/dwmw2/misc-git-hacks.git;a=commitdiff;h=fc1b73da\n\nYes, that is broken.\n \n> I shouldn't need to know that -- I'd _really_ like a version of\n> 'git-hash-object -t tree' which validates and sorts its input for me.\n> And maybe even takes input in _text_ form, so I don't have to convert\n> the sha1 to binary.\n\nTry `git mktree` instead. It uses a text form, and it corrects\nthe sorting for you. Though funny names that contain an LF may be\nharder to send to mktree.\n\n-- \nShawn.\n"},{"id":"87727","messageId":"200808192032.44078.robin.rosenberg.lists@dewire.com","threadId":"15078","inReplyTo":"1219103602-32222-2-git-send-email-spearce@spearce.org","subject":"Re: [JGIT PATCH 01/14] Detect path names which overflow the name length field in the index","fromName":"Robin Rosenberg","fromEmail":"robin.rosenberg.lists@dewire.com","sentAt":"2008-08-19T18:32:40Z","receivedAt":"2008-08-19T18:32:40Z","isPatch":true,"sender":{"key":"robin.rosenberg@dewire.com","avatar":"https://avatars.githubusercontent.com/u/46357?v=4"},"body":"tisdagen den 19 augusti 2008 01.53.09 skrev Shawn O. Pearce:\n> C Git allows a path name to be longer than 4095 bytes by storing 4095\n> into the path name length field within flags and then searching for a\n> null terminator at the end of the path name, instead of relying on the\n> length indicatior. We cannot do this (easily) from an InputStream so\n> we are currently going to just abort with an exception if we find such\n> an extremely long path name.\n\nWhat's hard? read bytes until we get a 0 shouldn't be hard. It has no\nspecial meaning to an InputStream.\n\n-- robin\n"},{"id":"87749","messageId":"20080819195735.GA24212@spearce.org","threadId":"15078","inReplyTo":"200808192032.44078.robin.rosenberg.lists@dewire.com","subject":"Re: [JGIT PATCH 01/14] Detect path names which overflow the name length field in the index","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-08-19T19:57:35Z","receivedAt":"2008-08-19T19:57:35Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Robin Rosenberg wrote:\n> tisdagen den 19 augusti 2008 01.53.09 skrev Shawn O. Pearce:\n> > C Git allows a path name to be longer than 4095 bytes by storing 4095\n> > into the path name length field within flags and then searching for a\n> > null terminator at the end of the path name, instead of relying on the\n> > length indicatior. We cannot do this (easily) from an InputStream so\n> > we are currently going to just abort with an exception if we find such\n> > an extremely long path name.\n> \n> What's hard? read bytes until we get a 0 shouldn't be hard. It has no\n> special meaning to an InputStream.\n\nYea, I forgot this stream is a BufferedInputStream and that pulling\nbytes one at a time isn't that much of a problem. I'll rework this\npatch and post a v2 today.\n\n-- \nShawn.\n"}]}