{"thread":{"id":"19728","subject":"[JGIT PATCH] Fix CanonicalTreeParser.back to parse all trees correctly","startedAt":"2009-06-07T22:01:56Z","lastAt":"2009-06-13T08:06:46Z","messageCount":3,"participants":["Shawn O. Pearce","Ferry Huberts"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"115744","messageId":"1244412116-13294-1-git-send-email-spearce@spearce.org","threadId":"19728","inReplyTo":null,"subject":"[JGIT PATCH] Fix CanonicalTreeParser.back to parse all trees correctly","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2009-06-07T22:01:56Z","receivedAt":"2009-06-07T22:01:56Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"The back(int delta) method needs to walk backwards delta entries in\nthe tree we are iterating.  Unfortunately, despite my attempts to do\nso, there is no reliable way to parse a canonical tree in reverse.\n\nNew test cases testBackwords_Prebuilts1 and testBackwords_Prebuilts2\nshow trees where the parser silently fails and jumps over an entry\nit should not have skipped.  These came from real world trees that\ncaused NameConflictTreeWalk to get stuck in an infinite loop.\n\nThe only reliable way to parse a canonical tree backwards is to\nactually do a parse from the beginning, and keeping track of the N\nprior positions in the tree, until we reach the current position,\nand then use the 0th index from that temporary N position buffer.\n\nMost of the time, we only need to walk a parser back 1 entry, to\nexamine the last path name it produced, before deciding we don't\nneed to handle a D/F conflict, and walk the parser forward again.\n\nThis is typical because most Git trees do not have a potential D/F\nconflict looming during a NameConflictTreeWalk, as it is rare that\ntree entries have the same leading base name such that a directory\ncould appear between two files.  Usually stepping back just one\nentry is sufficient to detemine a D/F conflict can't happen, and\nthe parser runs forward again.  So we optimize for this delta = 1\ncase by saving a prevPtr field.\n\nSigned-off-by: Shawn O. Pearce <spearce@spearce.org>\n---\n\n I should have listened to Dscho.  Last fall during GitTogether '08\n he argued you can't walk a tree backwards.  He was right.  :-)\n\n .../jgit/treewalk/CanonicalTreeParserTest.java     |   78 ++++++++++++++++++-\n .../spearce/jgit/treewalk/CanonicalTreeParser.java |   74 +++++++++---------\n 2 files changed, 110 insertions(+), 42 deletions(-)\n\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\nindex ed3478c..8ab2fc9 100644\n--- a/org.spearce.jgit.test/tst/org/spearce/jgit/treewalk/CanonicalTreeParserTest.java\n+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/treewalk/CanonicalTreeParserTest.java\n@@ -71,13 +71,13 @@\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\ttree1 = mktree(entry(m644, \"a\", hash_a));\n+\t\ttree2 = mktree(entry(m644, \"a\", hash_a), entry(m644, \"foo\", hash_foo));\n+\t\ttree3 = mktree(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+\tprivate static byte[] mktree(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@@ -247,7 +247,7 @@ public void testThreeEntries_BackwardsTwo() throws Exception {\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\tctp.reset(mktree(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@@ -265,6 +265,74 @@ public void testBackwards_ConfusingPathName() throws Exception {\n \t\tassertEquals(hash_a, ctp.getEntryObjectId());\n \t}\n \n+\tpublic void testBackwords_Prebuilts1() throws Exception {\n+\t\t// What is interesting about this test is the ObjectId for the\n+\t\t// \"darwin-x86\" path entry ends in an octal digit (37 == '7').\n+\t\t// Thus when scanning backwards we could over scan and consume\n+\t\t// part of the SHA-1, and miss the path terminator.\n+\t\t//\n+\t\tfinal ObjectId common = ObjectId\n+\t\t\t\t.fromString(\"af7bf97cb9bce3f60f1d651a0ef862e9447dd8bc\");\n+\t\tfinal ObjectId darwinx86 = ObjectId\n+\t\t\t\t.fromString(\"e927f7398240f78face99e1a738dac54ef738e37\");\n+\t\tfinal ObjectId linuxx86 = ObjectId\n+\t\t\t\t.fromString(\"ac08dd97120c7cb7d06e98cd5b152011183baf21\");\n+\t\tfinal ObjectId windows = ObjectId\n+\t\t\t\t.fromString(\"6c4c64c221a022bb973165192cca4812033479df\");\n+\n+\t\tctp.reset(mktree(entry(mt, \"common\", common), entry(mt, \"darwin-x86\",\n+\t\t\t\tdarwinx86), entry(mt, \"linux-x86\", linuxx86), entry(mt,\n+\t\t\t\t\"windows\", windows)));\n+\t\tctp.next(3);\n+\t\tassertEquals(\"windows\", ctp.getEntryPathString());\n+\t\tassertSame(mt, ctp.getEntryFileMode());\n+\t\tassertEquals(windows, ctp.getEntryObjectId());\n+\n+\t\tctp.back(1);\n+\t\tassertEquals(\"linux-x86\", ctp.getEntryPathString());\n+\t\tassertSame(mt, ctp.getEntryFileMode());\n+\t\tassertEquals(linuxx86, ctp.getEntryObjectId());\n+\n+\t\tctp.next(1);\n+\t\tassertEquals(\"windows\", ctp.getEntryPathString());\n+\t\tassertSame(mt, ctp.getEntryFileMode());\n+\t\tassertEquals(windows, ctp.getEntryObjectId());\n+\t}\n+\n+\tpublic void testBackwords_Prebuilts2() throws Exception {\n+\t\t// What is interesting about this test is the ObjectId for the\n+\t\t// \"darwin-x86\" path entry ends in an octal digit (37 == '7').\n+\t\t// Thus when scanning backwards we could over scan and consume\n+\t\t// part of the SHA-1, and miss the path terminator.\n+\t\t//\n+\t\tfinal ObjectId common = ObjectId\n+\t\t\t\t.fromString(\"af7bf97cb9bce3f60f1d651a0ef862e9447dd8bc\");\n+\t\tfinal ObjectId darwinx86 = ObjectId\n+\t\t\t\t.fromString(\"0000000000000000000000000000000000000037\");\n+\t\tfinal ObjectId linuxx86 = ObjectId\n+\t\t\t\t.fromString(\"ac08dd97120c7cb7d06e98cd5b152011183baf21\");\n+\t\tfinal ObjectId windows = ObjectId\n+\t\t\t\t.fromString(\"6c4c64c221a022bb973165192cca4812033479df\");\n+\n+\t\tctp.reset(mktree(entry(mt, \"common\", common), entry(mt, \"darwin-x86\",\n+\t\t\t\tdarwinx86), entry(mt, \"linux-x86\", linuxx86), entry(mt,\n+\t\t\t\t\"windows\", windows)));\n+\t\tctp.next(3);\n+\t\tassertEquals(\"windows\", ctp.getEntryPathString());\n+\t\tassertSame(mt, ctp.getEntryFileMode());\n+\t\tassertEquals(windows, ctp.getEntryObjectId());\n+\n+\t\tctp.back(1);\n+\t\tassertEquals(\"linux-x86\", ctp.getEntryPathString());\n+\t\tassertSame(mt, ctp.getEntryFileMode());\n+\t\tassertEquals(linuxx86, ctp.getEntryObjectId());\n+\n+\t\tctp.next(1);\n+\t\tassertEquals(\"windows\", ctp.getEntryPathString());\n+\t\tassertSame(mt, ctp.getEntryFileMode());\n+\t\tassertEquals(windows, ctp.getEntryObjectId());\n+\t}\n+\n \tpublic void testFreakingHugePathName() throws Exception {\n \t\tfinal int n = AbstractTreeIterator.DEFAULT_PATH_SIZE * 4;\n \t\tfinal StringBuilder b = new StringBuilder(n);\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 ec1cf10..47c3a77 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@@ -38,6 +38,7 @@\n package org.spearce.jgit.treewalk;\n \n import java.io.IOException;\n+import java.util.Arrays;\n \n import org.spearce.jgit.errors.IncorrectObjectTypeException;\n import org.spearce.jgit.errors.MissingObjectException;\n@@ -56,15 +57,18 @@\n \n \tprivate byte[] raw;\n \n+\t/** First offset within {@link #raw} of the prior entry. */\n+\tprivate int prevPtr;\n+\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+\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-\t\traw = EMPTY;\n+\t\treset(EMPTY);\n \t}\n \n \t/**\n@@ -109,6 +113,7 @@ private CanonicalTreeParser(final CanonicalTreeParser p) {\n \t */\n \tpublic void reset(final byte[] treeData) {\n \t\traw = treeData;\n+\t\tprevPtr = -1;\n \t\tcurrPtr = 0;\n \t\tif (!eof())\n \t\t\tparseEntry();\n@@ -265,6 +270,7 @@ public 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\tprevPtr = currPtr;\n \t\t\tcurrPtr = nextPtr;\n \t\t\tif (!eof())\n \t\t\t\tparseEntry();\n@@ -276,6 +282,7 @@ public void next(int delta) {\n \t\tfinal int end = raw.length;\n \t\tint ptr = nextPtr;\n \t\twhile (--delta > 0 && ptr != end) {\n+\t\t\tprevPtr = ptr;\n \t\t\twhile (raw[ptr] != 0)\n \t\t\t\tptr++;\n \t\t\tptr += Constants.OBJECT_ID_LENGTH + 1;\n@@ -289,44 +296,37 @@ public void next(int delta) {\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\tif (delta == 1 && 0 <= prevPtr) {\n+\t\t\t// Moving back one is common in NameTreeWalk, as the average tree\n+\t\t\t// won't have D/F type conflicts to study.\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\t}\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+\t\t\tcurrPtr = prevPtr;\n+\t\t\tprevPtr = -1;\n+\t\t\tif (!eof())\n+\t\t\t\tparseEntry();\n+\t\t\treturn;\n+\t\t} else if (delta <= 0)\n+\t\t\tthrow new ArrayIndexOutOfBoundsException(delta);\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// Fast skip through the records, from the beginning of the tree.\n+\t\t// There is no reliable way to read the tree backwards, so we must\n+\t\t// parse all over again from the beginning. We hold the last \"delta\"\n+\t\t// positions in a buffer, so we can find the correct position later.\n+\t\t//\n+\t\tfinal int[] trace = new int[delta + 1];\n+\t\tArrays.fill(trace, -1);\n+\t\tint ptr = 0;\n+\t\twhile (ptr != currPtr) {\n+\t\t\tSystem.arraycopy(trace, 1, trace, 0, delta);\n+\t\t\ttrace[delta] = ptr;\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\tcurrPtr = ptr;\n+\t\tif (trace[1] == -1)\n+\t\t\tthrow new ArrayIndexOutOfBoundsException(delta);\n+\t\tprevPtr = trace[0];\n+\t\tcurrPtr = trace[1];\n \t\tparseEntry();\n \t}\n \n-- \n1.6.3.2.322.g117de\n"},{"id":"116160","messageId":"20090612150801.GA17538@spearce.org","threadId":"19728","inReplyTo":"1244412116-13294-1-git-send-email-spearce@spearce.org","subject":"Re: [JGIT PATCH] Fix CanonicalTreeParser.back to parse all trees correctly","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2009-06-12T15:08:01Z","receivedAt":"2009-06-12T15:08:01Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"\"Shawn O. Pearce\" <spearce@spearce.org> wrote:\n> The back(int delta) method needs to walk backwards delta entries in\n> the tree we are iterating.  Unfortunately, despite my attempts to do\n> so, there is no reliable way to parse a canonical tree in reverse.\n\nPing?\n\nWithout this patch the NameConflictDirWalk can get into some serious\ntrouble, trouble which can cause Gerrit Code Review to have its\nmemory explode to >8 GiB, because NCDW gets stuck in an infinite\nloop, forever allocating reachable memory inside of a MergeStrategy.\n\nI've made a private build of this and am running it in production\nwithin day-job employer, but I can't make a release of Gerrit until\nI have a stable identifier for this patch.\n \n>  .../jgit/treewalk/CanonicalTreeParserTest.java     |   78 ++++++++++++++++++-\n>  .../spearce/jgit/treewalk/CanonicalTreeParser.java |   74 +++++++++---------\n>  2 files changed, 110 insertions(+), 42 deletions(-)\n\n-- \nShawn.\n"},{"id":"116218","messageId":"4A335E16.1050903@pelagic.nl","threadId":"19728","inReplyTo":"20090612150801.GA17538@spearce.org","subject":"Re: [JGIT PATCH] Fix CanonicalTreeParser.back to parse all trees correctly","fromName":"Ferry Huberts","fromEmail":"ferry.huberts@pelagic.nl","sentAt":"2009-06-13T08:06:46Z","receivedAt":"2009-06-13T08:06:46Z","isPatch":true,"sender":{"key":"ferry.huberts@pelagic.nl","avatar":"https://gravatar.com/avatar/9f63c0289ad23cbdef0f7609a0af85ff0f4b3babfd066de9ff58f62d48cfd6f2?d=mp&s=160"},"body":"Shawn O. Pearce wrote:\n> \"Shawn O. Pearce\" <spearce@spearce.org> wrote:\n>> The back(int delta) method needs to walk backwards delta entries in\n>> the tree we are iterating.  Unfortunately, despite my attempts to do\n>> so, there is no reliable way to parse a canonical tree in reverse.\n> \n> Ping?\n> \n\nlooks good to me\n"}]}