From 2923e1357ecb013cacdd23fda025937d7e70e14c Mon Sep 17 00:00:00 2001 From: "Shawn O. Pearce" Date: Mon, 18 Aug 2008 16:53:18 -0700 Subject: [PATCH] Make all AbstractTreeIterator implementations bi-directional To support scanning ahead and then rewinding back to our prior location we need to allow all tree iterators to be moved both forward and backwards through their entries. The next(int) API replaces the simple next() by supplying the amount that the iterator needs to move forward. A corresponding back(int) method supplies the opposite direction of travel. Some iterators, like WorkingTreeIterator, can efficiently move forward and backward any distance because they have a direct 1:1 mapping between positions of the iterator and an array index. Others like CanonicalTreeParser must scan through their input buffer, but can try to reduce the work needed on larger steps as they move past the undesired entries. DirCacheIterator is a challenge because it needs to match each entry to the DirCacheTrees available at this level. This API (and its implementation) is really meant for peeking at the next entry (or two) forward to see if there is a name (but not mode) match during a TreeWalk. This is to help TreeWalk catch a directory/file mode conflict and report it, despite the directory and file variants of a name appearing at two very different positions in the trees. Signed-off-by: Shawn O. Pearce Signed-off-by: Robin Rosenberg --- .../jgit/dircache/DirCacheIteratorTest.java | 2 +- .../jgit/treewalk/CanonicalTreeParserTest.java | 261 +++++++++++++++++++++ .../jgit/dircache/DirCacheBuildIterator.java | 2 +- .../spearce/jgit/dircache/DirCacheIterator.java | 27 ++- .../jgit/treewalk/AbstractTreeIterator.java | 38 ++- .../spearce/jgit/treewalk/CanonicalTreeParser.java | 68 +++++- .../spearce/jgit/treewalk/EmptyTreeIterator.java | 7 +- .../src/org/spearce/jgit/treewalk/TreeWalk.java | 2 +- .../spearce/jgit/treewalk/WorkingTreeIterator.java | 10 +- 9 files changed, 398 insertions(+), 19 deletions(-) create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/treewalk/CanonicalTreeParserTest.java diff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/dircache/DirCacheIteratorTest.java b/org.spearce.jgit.test/tst/org/spearce/jgit/dircache/DirCacheIteratorTest.java index 51b3c5a3..047c9892 100644 --- a/org.spearce.jgit.test/tst/org/spearce/jgit/dircache/DirCacheIteratorTest.java +++ b/org.spearce.jgit.test/tst/org/spearce/jgit/dircache/DirCacheIteratorTest.java @@ -78,7 +78,7 @@ public class DirCacheIteratorTest extends RepositoryTestCase { final DirCacheIterator i = new DirCacheIterator(dc); int pathIdx = 0; - for (; !i.eof(); i.next()) { + for (; !i.eof(); i.next(1)) { assertEquals(pathIdx, i.ptr); assertSame(ents[pathIdx], i.getDirCacheEntry()); pathIdx++; diff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/treewalk/CanonicalTreeParserTest.java b/org.spearce.jgit.test/tst/org/spearce/jgit/treewalk/CanonicalTreeParserTest.java new file mode 100644 index 00000000..fd92844d --- /dev/null +++ b/org.spearce.jgit.test/tst/org/spearce/jgit/treewalk/CanonicalTreeParserTest.java @@ -0,0 +1,261 @@ +/* + * Copyright (C) 2008, Google Inc. + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or + * without modification, are permitted provided that the following + * conditions are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * - Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials provided + * with the distribution. + * + * - Neither the name of the Git Development Community nor the + * names of its contributors may be used to endorse or promote + * products derived from this software without specific prior + * written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND + * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, + * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF + * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +package org.spearce.jgit.treewalk; + +import java.io.ByteArrayOutputStream; + +import junit.framework.TestCase; + +import org.spearce.jgit.lib.Constants; +import org.spearce.jgit.lib.FileMode; +import org.spearce.jgit.lib.ObjectId; +import org.spearce.jgit.util.RawParseUtils; + +public class CanonicalTreeParserTest extends TestCase { + private final CanonicalTreeParser ctp = new CanonicalTreeParser(); + + private final FileMode m644 = FileMode.REGULAR_FILE; + + private final FileMode mt = FileMode.TREE; + + private final ObjectId hash_a = ObjectId + .fromString("6b9c715d21d5486e59083fb6071566aa6ecd4d42"); + + private final ObjectId hash_foo = ObjectId + .fromString("a213e8e25bb2442326e86cbfb9ef56319f482869"); + + private final ObjectId hash_sometree = ObjectId + .fromString("daf4bdb0d7bb24319810fe0e73aa317663448c93"); + + private byte[] tree1; + + private byte[] tree2; + + private byte[] tree3; + + public void setUp() throws Exception { + super.setUp(); + + tree1 = mkree(entry(m644, "a", hash_a)); + tree2 = mkree(entry(m644, "a", hash_a), entry(m644, "foo", hash_foo)); + tree3 = mkree(entry(m644, "a", hash_a), entry(mt, "b_sometree", + hash_sometree), entry(m644, "foo", hash_foo)); + } + + private static byte[] mkree(final byte[]... data) throws Exception { + final ByteArrayOutputStream out = new ByteArrayOutputStream(); + for (final byte[] e : data) + out.write(e); + return out.toByteArray(); + } + + private static byte[] entry(final FileMode mode, final String name, + final ObjectId id) throws Exception { + final ByteArrayOutputStream out = new ByteArrayOutputStream(); + mode.copyTo(out); + out.write(' '); + out.write(Constants.encode(name)); + out.write(0); + id.copyRawTo(out); + return out.toByteArray(); + } + + private String path() { + return RawParseUtils.decode(Constants.CHARSET, ctp.path, + ctp.pathOffset, ctp.pathLen); + } + + public void testEmptyTree_AtEOF() throws Exception { + ctp.reset(new byte[0]); + assertTrue(ctp.eof()); + } + + public void testOneEntry_Forward() throws Exception { + ctp.reset(tree1); + + assertFalse(ctp.eof()); + assertEquals(m644.getBits(), ctp.mode); + assertEquals("a", path()); + assertEquals(hash_a, ctp.getEntryObjectId()); + + ctp.next(1); + assertTrue(ctp.eof()); + } + + public void testTwoEntries_ForwardOneAtATime() throws Exception { + ctp.reset(tree2); + + assertFalse(ctp.eof()); + assertEquals(m644.getBits(), ctp.mode); + assertEquals("a", path()); + assertEquals(hash_a, ctp.getEntryObjectId()); + + ctp.next(1); + assertFalse(ctp.eof()); + assertEquals(m644.getBits(), ctp.mode); + assertEquals("foo", path()); + assertEquals(hash_foo, ctp.getEntryObjectId()); + + ctp.next(1); + assertTrue(ctp.eof()); + } + + public void testOneEntry_Seek1IsEOF() throws Exception { + ctp.reset(tree1); + ctp.next(1); + assertTrue(ctp.eof()); + } + + public void testTwoEntries_Seek2IsEOF() throws Exception { + ctp.reset(tree2); + ctp.next(2); + assertTrue(ctp.eof()); + } + + public void testThreeEntries_Seek3IsEOF() throws Exception { + ctp.reset(tree3); + ctp.next(3); + assertTrue(ctp.eof()); + } + + public void testThreeEntries_Seek2() throws Exception { + ctp.reset(tree3); + + ctp.next(2); + assertFalse(ctp.eof()); + assertFalse(ctp.eof()); + assertEquals(m644.getBits(), ctp.mode); + assertEquals("foo", path()); + assertEquals(hash_foo, ctp.getEntryObjectId()); + + ctp.next(1); + assertTrue(ctp.eof()); + } + + public void testOneEntry_Backwards() throws Exception { + ctp.reset(tree1); + ctp.next(1); + assertTrue(ctp.eof()); + + ctp.back(1); + assertFalse(ctp.eof()); + assertEquals(m644.getBits(), ctp.mode); + assertEquals("a", path()); + assertEquals(hash_a, ctp.getEntryObjectId()); + } + + public void testTwoEntries_BackwardsOneAtATime() throws Exception { + ctp.reset(tree2); + ctp.next(2); + assertTrue(ctp.eof()); + + ctp.back(1); + assertFalse(ctp.eof()); + assertEquals(m644.getBits(), ctp.mode); + assertEquals("foo", path()); + assertEquals(hash_foo, ctp.getEntryObjectId()); + + ctp.back(1); + assertFalse(ctp.eof()); + assertEquals(m644.getBits(), ctp.mode); + assertEquals("a", path()); + assertEquals(hash_a, ctp.getEntryObjectId()); + } + + public void testTwoEntries_BackwardsTwo() throws Exception { + ctp.reset(tree2); + ctp.next(2); + assertTrue(ctp.eof()); + + ctp.back(2); + assertFalse(ctp.eof()); + assertEquals(m644.getBits(), ctp.mode); + assertEquals("a", path()); + assertEquals(hash_a, ctp.getEntryObjectId()); + + ctp.next(1); + assertFalse(ctp.eof()); + assertEquals(m644.getBits(), ctp.mode); + assertEquals("foo", path()); + assertEquals(hash_foo, ctp.getEntryObjectId()); + + ctp.next(1); + assertTrue(ctp.eof()); + } + + public void testThreeEntries_BackwardsTwo() throws Exception { + ctp.reset(tree3); + ctp.next(3); + assertTrue(ctp.eof()); + + ctp.back(2); + assertFalse(ctp.eof()); + assertEquals(mt.getBits(), ctp.mode); + assertEquals("b_sometree", path()); + assertEquals(hash_sometree, ctp.getEntryObjectId()); + + ctp.next(1); + assertFalse(ctp.eof()); + assertEquals(m644.getBits(), ctp.mode); + assertEquals("foo", path()); + assertEquals(hash_foo, ctp.getEntryObjectId()); + + ctp.next(1); + assertTrue(ctp.eof()); + } + + public void testBackwards_ConfusingPathName() throws Exception { + final String aVeryConfusingName = "confusing 644 entry 755 and others"; + ctp.reset(mkree(entry(m644, "a", hash_a), entry(mt, aVeryConfusingName, + hash_sometree), entry(m644, "foo", hash_foo))); + ctp.next(3); + assertTrue(ctp.eof()); + + ctp.back(2); + assertFalse(ctp.eof()); + assertEquals(mt.getBits(), ctp.mode); + assertEquals(aVeryConfusingName, path()); + assertEquals(hash_sometree, ctp.getEntryObjectId()); + + ctp.back(1); + assertFalse(ctp.eof()); + assertEquals(m644.getBits(), ctp.mode); + assertEquals("a", path()); + assertEquals(hash_a, ctp.getEntryObjectId()); + } +} diff --git a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheBuildIterator.java b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheBuildIterator.java index aaec4fcb..234ffd20 100644 --- a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheBuildIterator.java +++ b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheBuildIterator.java @@ -112,7 +112,7 @@ public class DirCacheBuildIterator extends DirCacheIterator { builder.keep(ptr, currentSubtree.getEntrySpan()); else builder.add(currentEntry); - next(); + next(1); } @Override diff --git a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheIterator.java b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheIterator.java index 248ae1e2..84cefa54 100644 --- a/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheIterator.java +++ b/org.spearce.jgit/src/org/spearce/jgit/dircache/DirCacheIterator.java @@ -144,13 +144,28 @@ public class DirCacheIterator extends AbstractTreeIterator { } @Override - public void next() { - if (currentSubtree != null) - ptr += currentSubtree.getEntrySpan(); - else - ptr++; - if (!eof()) + public void next(int delta) { + while (--delta >= 0) { + if (currentSubtree != null) + ptr += currentSubtree.getEntrySpan(); + else + ptr++; + if (eof()) + break; + parseEntry(); + } + } + + @Override + public void back(int delta) { + while (--delta >= 0) { + if (currentSubtree != null) + nextSubtreePos--; + ptr--; parseEntry(); + if (currentSubtree != null) + ptr -= currentSubtree.getEntrySpan() - 1; + } } private void parseEntry() { diff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java index 208adc72..c1c1df3d 100644 --- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java +++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/AbstractTreeIterator.java @@ -349,7 +349,34 @@ public abstract class AbstractTreeIterator { public abstract boolean eof(); /** - * Advance to the next tree entry, populating this iterator with its data. + * Move to next entry, populating this iterator with the entry data. + *

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

+ * Implementations must populate the following members: + *

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

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

* Implementations must populate the following members: *

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

    - * This method behaves like {@link #next()} but is called by + * This method behaves like seek(1) but is called by * {@link TreeWalk} only if a {@link TreeFilter} was used and ruled out the * current entry from the results. In such cases this tree iterator may * perform special behavior. @@ -378,7 +408,7 @@ public abstract class AbstractTreeIterator { * the tree is invalid. */ public void skip() throws CorruptObjectException { - next(); + next(1); } /** diff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/CanonicalTreeParser.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/CanonicalTreeParser.java index ebcc7875..111d03b0 100644 --- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/CanonicalTreeParser.java +++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/CanonicalTreeParser.java @@ -39,7 +39,6 @@ package org.spearce.jgit.treewalk; import java.io.IOException; -import org.spearce.jgit.errors.CorruptObjectException; import org.spearce.jgit.errors.IncorrectObjectTypeException; import org.spearce.jgit.errors.MissingObjectException; import org.spearce.jgit.lib.Constants; @@ -131,12 +130,75 @@ public class CanonicalTreeParser extends AbstractTreeIterator { return currPtr == raw.length; } - public void next() throws CorruptObjectException { - currPtr = nextPtr; + @Override + public void next(int delta) { + if (delta == 1) { + // Moving forward one is the most common case. + // + currPtr = nextPtr; + if (!eof()) + parseEntry(); + return; + } + + // Fast skip over records, then parse the last one. + // + final int end = raw.length; + int ptr = nextPtr; + while (--delta > 0 && ptr != end) { + while (raw[ptr] != 0) + ptr++; + ptr += Constants.OBJECT_ID_LENGTH + 1; + } + if (delta != 0) + throw new ArrayIndexOutOfBoundsException(delta); + currPtr = ptr; if (!eof()) parseEntry(); } + @Override + public void back(int delta) { + int ptr = currPtr; + while (--delta >= 0) { + if (ptr == 0) + throw new ArrayIndexOutOfBoundsException(delta); + + // Rewind back beyond the id and the null byte. Find the + // last space, this _might_ be the split between the mode + // and the path. Most paths in most trees do not contain a + // space so this prunes our search more quickly. + // + ptr -= Constants.OBJECT_ID_LENGTH; + while (raw[--ptr] != ' ') + /* nothing */; + if (--ptr < Constants.OBJECT_ID_LENGTH) { + if (delta != 0) + throw new ArrayIndexOutOfBoundsException(delta); + ptr = 0; + break; + } + + // Locate a position that matches "\0.{20}[0-7]" such that + // the ptr will rest on the [0-7]. This must be the first + // byte of the mode. This search works because the path in + // the prior record must have a non-zero length and must not + // contain a null byte. + // + for (int n;; ptr = n) { + n = ptr - 1; + final byte b = raw[n]; + if ('0' <= b && b <= '7') + continue; + if (raw[n - Constants.OBJECT_ID_LENGTH] != 0) + continue; + break; + } + } + currPtr = ptr; + parseEntry(); + } + private void parseEntry() { int ptr = currPtr; byte c = raw[ptr++]; diff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/EmptyTreeIterator.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/EmptyTreeIterator.java index c5dc4adb..232e3b12 100644 --- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/EmptyTreeIterator.java +++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/EmptyTreeIterator.java @@ -84,7 +84,12 @@ public class EmptyTreeIterator extends AbstractTreeIterator { } @Override - public void next() throws CorruptObjectException { + public void next(final int delta) throws CorruptObjectException { + // Do nothing. + } + + @Override + public void back(final int delta) throws CorruptObjectException { // Do nothing. } diff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java index 3bdef22e..10cdebd6 100644 --- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java +++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java @@ -651,7 +651,7 @@ public class TreeWalk { for (int i = 0; i < trees.length; i++) { final AbstractTreeIterator t = trees[i]; if (t.matches == ch) { - t.next(); + t.next(1); t.matches = null; } } diff --git a/org.spearce.jgit/src/org/spearce/jgit/treewalk/WorkingTreeIterator.java b/org.spearce.jgit/src/org/spearce/jgit/treewalk/WorkingTreeIterator.java index aebc6311..20b1139e 100644 --- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/WorkingTreeIterator.java +++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/WorkingTreeIterator.java @@ -236,12 +236,18 @@ public abstract class WorkingTreeIterator extends AbstractTreeIterator { } @Override - public void next() throws CorruptObjectException { - ptr++; + public void next(final int delta) throws CorruptObjectException { + ptr += delta; if (!eof()) parseEntry(); } + @Override + public void back(final int delta) throws CorruptObjectException { + ptr -= delta; + parseEntry(); + } + private void parseEntry() { final Entry e = entries[ptr]; mode = e.getMode().getBits(); -- 2.11.4.GIT