From 0644b345edc12273e8d07cb472ee58a044cfaab0 Mon Sep 17 00:00:00 2001 From: "Shawn O. Pearce" Date: Wed, 14 May 2008 21:24:59 -0400 Subject: [PATCH] Implement rev-list --objects for tree and blob traversal To verify connectivity and pack file generation we need to produce a complete list of objects reachable from one or more starting points. The new ObjectWalk class supports doing that by tracking which RevTrees are associated with a RevCommit that we returned to the application, and then also walk through those tree objects and return them, including any referenced blob or subtree that were also not yet returned. Signed-off-by: Shawn O. Pearce --- .../src/org/spearce/jgit/pgm/Glog.java | 2 + .../src/org/spearce/jgit/pgm/RevList.java | 19 ++ .../org/spearce/jgit/pgm/RevWalkTextBuiltin.java | 22 ++ .../org/spearce/jgit/revwalk/BlockObjQueue.java | 117 ++++++++ .../src/org/spearce/jgit/revwalk/ObjectWalk.java | 333 +++++++++++++++++++++ .../src/org/spearce/jgit/revwalk/RevWalk.java | 3 +- .../org/spearce/jgit/revwalk/StartGenerator.java | 7 + 7 files changed, 502 insertions(+), 1 deletion(-) create mode 100644 org.spearce.jgit/src/org/spearce/jgit/revwalk/BlockObjQueue.java create mode 100644 org.spearce.jgit/src/org/spearce/jgit/revwalk/ObjectWalk.java diff --git a/org.spearce.jgit/src/org/spearce/jgit/pgm/Glog.java b/org.spearce.jgit/src/org/spearce/jgit/pgm/Glog.java index 25a65cef..30e19fab 100644 --- a/org.spearce.jgit/src/org/spearce/jgit/pgm/Glog.java +++ b/org.spearce.jgit/src/org/spearce/jgit/pgm/Glog.java @@ -72,6 +72,8 @@ class Glog extends RevWalkTextBuiltin { @Override protected RevWalk createWalk() { + if (objects) + throw new Die("Cannot use --objects with glog"); final PlotWalk w = new PlotWalk(db); w.sort(RevSort.BOUNDARY, true); return w; diff --git a/org.spearce.jgit/src/org/spearce/jgit/pgm/RevList.java b/org.spearce.jgit/src/org/spearce/jgit/pgm/RevList.java index 6deeb1e2..3a0b8682 100644 --- a/org.spearce.jgit/src/org/spearce/jgit/pgm/RevList.java +++ b/org.spearce.jgit/src/org/spearce/jgit/pgm/RevList.java @@ -16,8 +16,11 @@ */ package org.spearce.jgit.pgm; +import org.spearce.jgit.revwalk.ObjectWalk; import org.spearce.jgit.revwalk.RevCommit; import org.spearce.jgit.revwalk.RevFlag; +import org.spearce.jgit.revwalk.RevObject; +import org.spearce.jgit.revwalk.RevTree; class RevList extends RevWalkTextBuiltin { @Override @@ -32,4 +35,20 @@ class RevList extends RevWalkTextBuiltin { } out.println(); } + + @Override + protected void show(final ObjectWalk ow, final RevObject obj) + throws Exception { + if (obj.has(RevFlag.UNINTERESTING)) + out.print('-'); + obj.getId().copyTo(outbuffer, out); + final String path = ow.getPathString(); + if (path != null) { + out.print(' '); + out.print(path); + } else if (obj instanceof RevTree) + out.print(' '); + out.println(); + + } } diff --git a/org.spearce.jgit/src/org/spearce/jgit/pgm/RevWalkTextBuiltin.java b/org.spearce.jgit/src/org/spearce/jgit/pgm/RevWalkTextBuiltin.java index 690becf2..c9b2925b 100644 --- a/org.spearce.jgit/src/org/spearce/jgit/pgm/RevWalkTextBuiltin.java +++ b/org.spearce.jgit/src/org/spearce/jgit/pgm/RevWalkTextBuiltin.java @@ -21,7 +21,9 @@ import java.util.EnumSet; import java.util.List; import org.spearce.jgit.lib.Constants; +import org.spearce.jgit.revwalk.ObjectWalk; import org.spearce.jgit.revwalk.RevCommit; +import org.spearce.jgit.revwalk.RevObject; import org.spearce.jgit.revwalk.RevSort; import org.spearce.jgit.revwalk.RevWalk; import org.spearce.jgit.revwalk.filter.AndRevFilter; @@ -37,6 +39,8 @@ import org.spearce.jgit.treewalk.filter.TreeFilter; abstract class RevWalkTextBuiltin extends TextBuiltin { RevWalk walk; + boolean objects = false; + boolean parents = false; boolean count = false; @@ -63,6 +67,8 @@ abstract class RevWalkTextBuiltin extends TextBuiltin { else if (a.startsWith("--grep=")) revLimiter.add(MessageRevFilter.create(a.substring("--grep=" .length()))); + else if ("--objects".equals(a)) + objects = true; else if ("--date-order".equals(a)) sorting.add(RevSort.COMMIT_TIME_DESC); else if ("--topo-order".equals(a)) @@ -129,6 +135,8 @@ abstract class RevWalkTextBuiltin extends TextBuiltin { } protected RevWalk createWalk() { + if (objects) + return new ObjectWalk(db); return new RevWalk(db); } @@ -138,8 +146,22 @@ abstract class RevWalkTextBuiltin extends TextBuiltin { n++; show(c); } + if (walk instanceof ObjectWalk) { + final ObjectWalk ow = (ObjectWalk) walk; + for (;;) { + final RevObject obj = ow.nextObject(); + if (obj == null) + break; + show(ow, obj); + } + } return n; } protected abstract void show(final RevCommit c) throws Exception; + + protected void show(final ObjectWalk objectWalk, + final RevObject currentObject) throws Exception { + // Do nothing by default. Most applications cannot show an object. + } } diff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/BlockObjQueue.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/BlockObjQueue.java new file mode 100644 index 00000000..6d55aa14 --- /dev/null +++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/BlockObjQueue.java @@ -0,0 +1,117 @@ +/* + * Copyright (C) 2008 Shawn Pearce + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public + * License, version 2, as published by the Free Software Foundation. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 + */ +package org.spearce.jgit.revwalk; + +class BlockObjQueue { + private BlockFreeList free; + + private Block head; + + private Block tail; + + /** Create an empty queue. */ + BlockObjQueue() { + free = new BlockFreeList(); + } + + void add(final RevObject c) { + Block b = tail; + if (b == null) { + b = free.newBlock(); + b.add(c); + head = b; + tail = b; + return; + } else if (b.isFull()) { + b = free.newBlock(); + tail.next = b; + tail = b; + } + b.add(c); + } + + RevObject next() { + final Block b = head; + if (b == null) + return null; + + final RevObject c = b.pop(); + if (b.isEmpty()) { + head = b.next; + if (head == null) + tail = null; + free.freeBlock(b); + } + return c; + } + + static final class BlockFreeList { + private Block next; + + Block newBlock() { + Block b = next; + if (b == null) + return new Block(); + next = b.next; + b.clear(); + return b; + } + + void freeBlock(final Block b) { + b.next = next; + next = b; + } + } + + static final class Block { + private static final int BLOCK_SIZE = 256; + + /** Next block in our chain of blocks; null if we are the last. */ + Block next; + + /** Our table of queued objects. */ + final RevObject[] objects = new RevObject[BLOCK_SIZE]; + + /** Next valid entry in {@link #objects}. */ + int headIndex; + + /** Next free entry in {@link #objects} for addition at. */ + int tailIndex; + + boolean isFull() { + return tailIndex == BLOCK_SIZE; + } + + boolean isEmpty() { + return headIndex == tailIndex; + } + + void add(final RevObject c) { + objects[tailIndex++] = c; + } + + RevObject pop() { + return objects[headIndex++]; + } + + void clear() { + next = null; + headIndex = 0; + tailIndex = 0; + } + } +} diff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/ObjectWalk.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/ObjectWalk.java new file mode 100644 index 00000000..4ab76878 --- /dev/null +++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/ObjectWalk.java @@ -0,0 +1,333 @@ +/* + * Copyright (C) 2008 Shawn Pearce + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public + * License, version 2, as published by the Free Software Foundation. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 + */ +package org.spearce.jgit.revwalk; + +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.AnyObjectId; +import org.spearce.jgit.lib.Constants; +import org.spearce.jgit.lib.FileMode; +import org.spearce.jgit.lib.ObjectId; +import org.spearce.jgit.lib.Repository; +import org.spearce.jgit.treewalk.TreeWalk; + +/** + * Specialized subclass of RevWalk to include trees, blobs and tags. + *

+ * Unlike RevWalk this subclass is able to remember starting roots that include + * annotated tags, or arbitrary trees or blobs. Once commit generation is + * complete and all commits have been popped by the application, individual + * annotated tag, tree and blob objects can be popped through the additional + * method {@link #nextObject()}. + *

+ * Tree and blob objects reachable from interesting commits are automatically + * scheduled for inclusion in the results of {@link #nextObject()}, returning + * each object exactly once. Objects are sorted and returned according to the + * the commits that reference them and the order they appear within a tree. + * Ordering can be affected by changing the {@link RevSort} used to order the + * commits that are returned first. + */ +public class ObjectWalk extends RevWalk { + private static final int SEEN_OR_UNINTERESTING = SEEN | UNINTERESTING; + + private final TreeWalk treeWalk; + + private BlockObjQueue objects; + + private RevTree currentTree; + + private boolean fromTreeWalk; + + private boolean enterSubtree; + + /** + * Create a new revision and object walker for a given repository. + * + * @param repo + * the repository the walker will obtain data from. + */ + public ObjectWalk(final Repository repo) { + super(repo); + treeWalk = new TreeWalk(repo); + objects = new BlockObjQueue(); + } + + /** + * Mark an object or commit to start graph traversal from. + *

+ * Callers are encouraged to use {@link RevWalk#parseAny(AnyObjectId)} + * instead of {@link RevWalk#lookupAny(AnyObjectId, int)}, as this method + * requires the object to be parsed before it can be added as a root for the + * traversal. + *

+ * The method will automatically parse an unparsed object, but error + * handling may be more difficult for the application to explain why a + * RevObject is not actually valid. The object pool of this walker would + * also be 'poisoned' by the invalid RevObject. + *

+ * This method will automatically call {@link RevWalk#markStart(RevCommit)} + * if passed RevCommit instance, or a RevTag that directly (or indirectly) + * references a RevCommit. + * + * @param o + * the object to start traversing from. The object passed must be + * from this same revision walker. + * @throws MissingObjectException + * the object supplied is not available from the object + * database. This usually indicates the supplied object is + * invalid, but the reference was constructed during an earlier + * invocation to {@link RevWalk#lookupAny(AnyObjectId, int)}. + * @throws IncorrectObjectTypeException + * the object was not parsed yet and it was discovered during + * parsing that it is not actually the type of the instance + * passed in. This usually indicates the caller used the wrong + * type in a {@link RevWalk#lookupAny(AnyObjectId, int)} call. + * @throws IOException + * a pack file or loose object could not be read. + */ + public void markStart(RevObject o) throws MissingObjectException, + IncorrectObjectTypeException, IOException { + while (o instanceof RevTag) { + addObject(o); + o = ((RevTag) o).getObject(); + parse(o); + } + + if (o instanceof RevCommit) + super.markStart((RevCommit) o); + else + addObject(o); + } + + /** + * Mark an object to not produce in the output. + *

+ * Uninteresting objects denote not just themselves but also their entire + * reachable chain, back until the merge base of an uninteresting commit and + * an otherwise interesting commit. + *

+ * Callers are encouraged to use {@link RevWalk#parseAny(AnyObjectId)} + * instead of {@link RevWalk#lookupAny(AnyObjectId, int)}, as this method + * requires the object to be parsed before it can be added as a root for the + * traversal. + *

+ * The method will automatically parse an unparsed object, but error + * handling may be more difficult for the application to explain why a + * RevObject is not actually valid. The object pool of this walker would + * also be 'poisoned' by the invalid RevObject. + *

+ * This method will automatically call {@link RevWalk#markStart(RevCommit)} + * if passed RevCommit instance, or a RevTag that directly (or indirectly) + * references a RevCommit. + * + * @param o + * the object to start traversing from. The object passed must be + * @throws MissingObjectException + * the object supplied is not available from the object + * database. This usually indicates the supplied object is + * invalid, but the reference was constructed during an earlier + * invocation to {@link RevWalk#lookupAny(AnyObjectId, int)}. + * @throws IncorrectObjectTypeException + * the object was not parsed yet and it was discovered during + * parsing that it is not actually the type of the instance + * passed in. This usually indicates the caller used the wrong + * type in a {@link RevWalk#lookupAny(AnyObjectId, int)} call. + * @throws IOException + * a pack file or loose object could not be read. + */ + public void markUninteresting(RevObject o) throws MissingObjectException, + IncorrectObjectTypeException, IOException { + while (o instanceof RevTag) { + o.flags |= UNINTERESTING; + o = ((RevTag) o).getObject(); + parse(o); + } + + if (o instanceof RevCommit) + super.markUninteresting((RevCommit) o); + else if (o instanceof RevTree) + markTreeUninteresting((RevTree) o); + else + o.flags |= UNINTERESTING; + } + + @Override + public RevCommit next() throws MissingObjectException, + IncorrectObjectTypeException, IOException { + for (;;) { + final RevCommit r = super.next(); + if (r == null) + return null; + if ((r.flags & UNINTERESTING) != 0) { + markTreeUninteresting(r.getTree()); + if (getRevSort().contains(RevSort.BOUNDARY)) + return r; + continue; + } + objects.add(r.getTree()); + return r; + } + } + + /** + * Pop the next most recent object. + * + * @return next most recent object; null if traversal is over. + * @throws MissingObjectException + * one or or more of the next objects are not available from the + * object database, but were thought to be candidates for + * traversal. This usually indicates a broken link. + * @throws IncorrectObjectTypeException + * one or or more of the objects in a tree do not match the type + * indicated. + * @throws IOException + * a pack file or loose object could not be read. + */ + public RevObject nextObject() throws MissingObjectException, + IncorrectObjectTypeException, IOException { + fromTreeWalk = false; + + if (enterSubtree) { + treeWalk.enterSubtree(); + enterSubtree = false; + } + + while (treeWalk.next()) { + final FileMode mode = treeWalk.getFileMode(0); + final int sType = mode.getObjectType(); + + switch (sType) { + case Constants.OBJ_BLOB: { + final RevObject o = lookupAny(treeWalk.getObjectId(0), sType); + if ((o.flags & SEEN_OR_UNINTERESTING) != 0) + continue; + o.flags |= SEEN; + fromTreeWalk = true; + return o; + } + case Constants.OBJ_TREE: { + final RevObject o = lookupAny(treeWalk.getObjectId(0), sType); + if ((o.flags & SEEN_OR_UNINTERESTING) != 0) + continue; + o.flags |= SEEN; + enterSubtree = true; + fromTreeWalk = true; + return o; + } + default: + if (FileMode.GITLINK.equals(mode)) + continue; + throw new CorruptObjectException("Invalid mode " + mode + + " for " + treeWalk.getObjectId(0) + " " + + treeWalk.getPathString() + " in " + currentTree + "."); + } + } + + for (;;) { + final RevObject o = objects.next(); + if (o == null) + return null; + if ((o.flags & SEEN_OR_UNINTERESTING) != 0) + continue; + o.flags |= SEEN; + if (o instanceof RevTree) { + currentTree = (RevTree) o; + treeWalk.reset(new ObjectId[] { currentTree }); + } + return o; + } + } + + /** + * Get the current object's complete path. + *

+ * This method is not very efficient and is primarily meant for debugging + * and final output generation. Applications should try to avoid calling it, + * and if invoked do so only once per interesting entry, where the name is + * absolutely required for correct function. + * + * @return complete path of the current entry, from the root of the + * repository. If the current entry is in a subtree there will be at + * least one '/' in the returned string. Null if the current entry + * has no path, such as for annotated tags or root level trees. + */ + public String getPathString() { + return fromTreeWalk ? treeWalk.getPathString() : null; + } + + @Override + public void dispose() { + super.dispose(); + objects = new BlockObjQueue(); + enterSubtree = false; + currentTree = null; + } + + @Override + protected void reset(final int retainFlags) { + super.reset(retainFlags); + objects = new BlockObjQueue(); + enterSubtree = false; + } + + private void addObject(final RevObject o) { + if ((o.flags & SEEN) == 0) { + o.flags |= SEEN; + objects.add(o); + } + } + + private void markTreeUninteresting(final RevTree tree) + throws MissingObjectException, IncorrectObjectTypeException, + IOException { + if ((tree.flags & UNINTERESTING) != 0) + return; + tree.flags |= UNINTERESTING; + + treeWalk.reset(new ObjectId[] { tree }); + while (treeWalk.next()) { + final FileMode mode = treeWalk.getFileMode(0); + final int sType = mode.getObjectType(); + + switch (sType) { + case Constants.OBJ_BLOB: { + final ObjectId sid = treeWalk.getObjectId(0); + lookupAny(sid, sType).flags |= UNINTERESTING; + continue; + } + case Constants.OBJ_TREE: { + final ObjectId sid = treeWalk.getObjectId(0); + final RevObject subtree = lookupAny(sid, sType); + if ((subtree.flags & UNINTERESTING) == 0) { + subtree.flags |= UNINTERESTING; + treeWalk.enterSubtree(); + } + continue; + } + default: + if (FileMode.GITLINK.equals(mode)) + continue; + throw new CorruptObjectException("Invalid mode " + mode + + " for " + treeWalk.getObjectId(0) + " " + + treeWalk.getPathString() + " in " + tree + "."); + } + } + } +} diff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevWalk.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevWalk.java index 411e8854..544341c8 100644 --- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevWalk.java +++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevWalk.java @@ -926,7 +926,8 @@ public class RevWalk implements Iterable { return new RevCommit(id); } - void carryFlagsImpl(final RevCommit c) { + void carryFlagsImpl(final RevCommit c) throws MissingObjectException, + IncorrectObjectTypeException, IOException { final int carry = c.flags & carryFlags; if (carry != 0) RevCommit.carryFlags(c, carry); diff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/StartGenerator.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/StartGenerator.java index ab3be719..50fe4fcd 100644 --- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/StartGenerator.java +++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/StartGenerator.java @@ -73,6 +73,13 @@ class StartGenerator extends Generator { final EnumSet sort = w.getRevSort(); boolean boundary = sort.contains(RevSort.BOUNDARY); + if (!boundary && walker instanceof ObjectWalk) { + // The object walker requires boundary support to color + // trees and blobs at the boundary uninteresting so it + // does not produce those in the result. + // + boundary = true; + } if (boundary && !q.anybodyHasFlag(RevWalk.UNINTERESTING)) { // If we were not fed uninteresting commits we will never // construct a boundary. There is no reason to include the -- 2.11.4.GIT