From 91d92e4ae3be3dd78bc9a54680e87b2b3332278b Mon Sep 17 00:00:00 2001 From: "Shawn O. Pearce" Date: Thu, 21 Aug 2008 13:57:36 -0700 Subject: [PATCH] Support post order tree handling during TreeWalk Some (rare) applications need to handle a tree after they have dealt with the tree's children. An example of such an application is one implementing rmdir, where the directory should be cleaned up after all files/subdirectories were already removed. Signed-off-by: Shawn O. Pearce Signed-off-by: Robin Rosenberg --- .../jgit/treewalk/PostOrderTreeWalkTest.java | 189 +++++++++++++++++++++ .../src/org/spearce/jgit/treewalk/TreeWalk.java | 53 +++++- 2 files changed, 241 insertions(+), 1 deletion(-) create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/treewalk/PostOrderTreeWalkTest.java diff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/treewalk/PostOrderTreeWalkTest.java b/org.spearce.jgit.test/tst/org/spearce/jgit/treewalk/PostOrderTreeWalkTest.java new file mode 100644 index 00000000..145a56e2 --- /dev/null +++ b/org.spearce.jgit.test/tst/org/spearce/jgit/treewalk/PostOrderTreeWalkTest.java @@ -0,0 +1,189 @@ +/* + * Copyright (C) 2008, Google Inc. + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or + * without modification, are permitted provided that the following + * conditions are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * - Redistributions in binary form must reproduce the above + * copyright notice, this list of conditions and the following + * disclaimer in the documentation and/or other materials provided + * with the distribution. + * + * - Neither the name of the Git Development Community nor the + * names of its contributors may be used to endorse or promote + * products derived from this software without specific prior + * written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND + * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, + * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF + * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +package org.spearce.jgit.treewalk; + +import java.io.ByteArrayInputStream; + +import org.spearce.jgit.dircache.DirCache; +import org.spearce.jgit.dircache.DirCacheBuilder; +import org.spearce.jgit.dircache.DirCacheEntry; +import org.spearce.jgit.dircache.DirCacheIterator; +import org.spearce.jgit.lib.Constants; +import org.spearce.jgit.lib.FileMode; +import org.spearce.jgit.lib.ObjectWriter; +import org.spearce.jgit.lib.RepositoryTestCase; + +import static org.spearce.jgit.lib.FileMode.REGULAR_FILE; +import static org.spearce.jgit.lib.FileMode.TREE; + +public class PostOrderTreeWalkTest extends RepositoryTestCase { + public void testInitialize_NoPostOrder() throws Exception { + final TreeWalk tw = new TreeWalk(db); + assertFalse(tw.isPostOrderTraversal()); + } + + public void testInitialize_TogglePostOrder() throws Exception { + final TreeWalk tw = new TreeWalk(db); + assertFalse(tw.isPostOrderTraversal()); + tw.setPostOrderTraversal(true); + assertTrue(tw.isPostOrderTraversal()); + tw.setPostOrderTraversal(false); + assertFalse(tw.isPostOrderTraversal()); + } + + public void testResetDoesNotAffectPostOrder() throws Exception { + final TreeWalk tw = new TreeWalk(db); + tw.setPostOrderTraversal(true); + assertTrue(tw.isPostOrderTraversal()); + tw.reset(); + assertTrue(tw.isPostOrderTraversal()); + + tw.setPostOrderTraversal(false); + assertFalse(tw.isPostOrderTraversal()); + tw.reset(); + assertFalse(tw.isPostOrderTraversal()); + } + + public void testNoPostOrder() throws Exception { + final DirCache tree = DirCache.read(db); + { + final DirCacheBuilder b = tree.builder(); + + b.add(makeFile("a")); + b.add(makeFile("b/c")); + b.add(makeFile("b/d")); + b.add(makeFile("q")); + + b.finish(); + assertEquals(4, tree.getEntryCount()); + } + + final TreeWalk tw = new TreeWalk(db); + tw.reset(); + tw.setPostOrderTraversal(false); + tw.addTree(new DirCacheIterator(tree)); + + assertModes("a", REGULAR_FILE, tw); + assertModes("b", TREE, tw); + assertTrue(tw.isSubtree()); + assertFalse(tw.isPostChildren()); + tw.enterSubtree(); + assertModes("b/c", REGULAR_FILE, tw); + assertModes("b/d", REGULAR_FILE, tw); + assertModes("q", REGULAR_FILE, tw); + } + + public void testWithPostOrder_EnterSubtree() throws Exception { + final DirCache tree = DirCache.read(db); + { + final DirCacheBuilder b = tree.builder(); + + b.add(makeFile("a")); + b.add(makeFile("b/c")); + b.add(makeFile("b/d")); + b.add(makeFile("q")); + + b.finish(); + assertEquals(4, tree.getEntryCount()); + } + + final TreeWalk tw = new TreeWalk(db); + tw.reset(); + tw.setPostOrderTraversal(true); + tw.addTree(new DirCacheIterator(tree)); + + assertModes("a", REGULAR_FILE, tw); + + assertModes("b", TREE, tw); + assertTrue(tw.isSubtree()); + assertFalse(tw.isPostChildren()); + tw.enterSubtree(); + assertModes("b/c", REGULAR_FILE, tw); + assertModes("b/d", REGULAR_FILE, tw); + + assertModes("b", TREE, tw); + assertTrue(tw.isSubtree()); + assertTrue(tw.isPostChildren()); + + assertModes("q", REGULAR_FILE, tw); + } + + public void testWithPostOrder_NoEnterSubtree() throws Exception { + final DirCache tree = DirCache.read(db); + { + final DirCacheBuilder b = tree.builder(); + + b.add(makeFile("a")); + b.add(makeFile("b/c")); + b.add(makeFile("b/d")); + b.add(makeFile("q")); + + b.finish(); + assertEquals(4, tree.getEntryCount()); + } + + final TreeWalk tw = new TreeWalk(db); + tw.reset(); + tw.setPostOrderTraversal(true); + tw.addTree(new DirCacheIterator(tree)); + + assertModes("a", REGULAR_FILE, tw); + + assertModes("b", TREE, tw); + assertTrue(tw.isSubtree()); + assertFalse(tw.isPostChildren()); + + assertModes("q", REGULAR_FILE, tw); + } + + private DirCacheEntry makeFile(final String path) throws Exception { + final byte[] pathBytes = Constants.encode(path); + final DirCacheEntry ent = new DirCacheEntry(path); + ent.setFileMode(REGULAR_FILE); + ent.setObjectId(new ObjectWriter(db).computeBlobSha1(pathBytes.length, + new ByteArrayInputStream(pathBytes))); + return ent; + } + + private static void assertModes(final String path, final FileMode mode0, + final TreeWalk tw) throws Exception { + assertTrue("has " + path, tw.next()); + assertEquals(path, tw.getPathString()); + assertEquals(mode0, tw.getFileMode(0)); + } +} 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 7a098787..ac26d3c1 100644 --- a/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java +++ b/org.spearce.jgit/src/org/spearce/jgit/treewalk/TreeWalk.java @@ -147,10 +147,14 @@ public class TreeWalk { private boolean recursive; + private boolean postOrderTraversal; + private int depth; private boolean advance; + private boolean postChildren; + AbstractTreeIterator currentHead; /** @@ -235,6 +239,36 @@ public class TreeWalk { recursive = b; } + /** + * Does this walker return a tree entry after it exits the subtree? + *

+ * If post order traversal is enabled then the walker will return a subtree + * after it has returned the last entry within that subtree. This may cause + * a subtree to be seen by the application twice if {@link #isRecursive()} + * is false, as the application will see it once, call + * {@link #enterSubtree()}, and then see it again as it leaves the subtree. + *

+ * If an application does not enable {@link #isRecursive()} and it does not + * call {@link #enterSubtree()} then the tree is returned only once as none + * of the children were processed. + * + * @return true if subtrees are returned after entries within the subtree. + */ + public boolean isPostOrderTraversal() { + return postOrderTraversal; + } + + /** + * Set the walker to return trees after their children. + * + * @param b + * true to get trees after their children. + * @see #isPostOrderTraversal() + */ + public void setPostOrderTraversal(final boolean b) { + postOrderTraversal = b; + } + /** Reset this walker so new tree iterators can be added to it. */ public void reset() { trees = new AbstractTreeIterator[0]; @@ -379,6 +413,7 @@ public class TreeWalk { try { if (advance) { advance = false; + postChildren = false; popEntriesEqual(); } @@ -387,6 +422,12 @@ public class TreeWalk { if (t.eof()) { if (depth > 0) { exitSubtree(); + if (postOrderTraversal) { + advance = true; + postChildren = true; + return true; + } + popEntriesEqual(); continue; } return false; @@ -587,6 +628,17 @@ public class TreeWalk { } /** + * Is the current entry a subtree returned after its children? + * + * @return true if the current node is a tree that has been returned after + * its children were already processed. + * @see #isPostOrderTraversal() + */ + public boolean isPostChildren() { + return postChildren && isSubtree(); + } + + /** * Enter into the current subtree. *

* If the current entry is a subtree this method arranges for its children @@ -675,7 +727,6 @@ public class TreeWalk { for (int i = 0; i < trees.length; i++) trees[i] = trees[i].parent; currentHead = min(); - popEntriesEqual(); } private CanonicalTreeParser parserFor(final ObjectId id) -- 2.11.4.GIT