/*
* Copyright (C) 2008, Shawn O. Pearce <spearce@spearce.org>
* and other copyright owners as documented in the project's IP log.
*
* This program and the accompanying materials are made available
* under the terms of the Eclipse Distribution License v1.0 which
* accompanies this distribution, is reproduced below, and is
* available at http://www.eclipse.org/org/documents/edl-v10.php
*
* 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 Eclipse Foundation, Inc. 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.eclipse.jgit.revwalk;
import java.io.IOException;
import java.text.MessageFormat;
import java.util.ArrayList;
import java.util.List;
import org.eclipse.jgit.JGitText;
import org.eclipse.jgit.errors.CorruptObjectException;
import org.eclipse.jgit.errors.IncorrectObjectTypeException;
import org.eclipse.jgit.errors.MissingObjectException;
import org.eclipse.jgit.lib.AnyObjectId;
import org.eclipse.jgit.lib.Constants;
import org.eclipse.jgit.lib.FileMode;
import org.eclipse.jgit.lib.ObjectReader;
import org.eclipse.jgit.lib.Repository;
import org.eclipse.jgit.treewalk.CanonicalTreeParser;
/**
* Specialized subclass of RevWalk to include trees, blobs and tags.
* <p>
* 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()}.
* <p>
* 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 {
/**
* Indicates a non-RevCommit is in {@link #pendingObjects}.
* <p>
* We can safely reuse {@link RevWalk#REWRITE} here for the same value as it
* is only set on RevCommit and {@link #pendingObjects} never has RevCommit
* instances inserted into it.
*/
private static final int IN_PENDING = RevWalk.REWRITE;
private static final byte[] EMPTY_PATH = {};
private CanonicalTreeParser treeWalk;
private List<RevObject> rootObjects;
private BlockObjQueue pendingObjects;
private RevTree currentTree;
private RevObject last;
private RevCommit firstCommit;
private RevCommit lastCommit;
/**
* 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) {
this(repo.newObjectReader());
}
/**
* Create a new revision and object walker for a given repository.
*
* @param or
* the reader the walker will obtain data from. The reader should
* be released by the caller when the walker is no longer
* required.
*/
public ObjectWalk(ObjectReader or) {
super(or);
rootObjects = new ArrayList<RevObject>();
pendingObjects = new BlockObjQueue();
treeWalk = new CanonicalTreeParser();
}
/**
* Mark an object or commit to start graph traversal from.
* <p>
* 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.
* <p>
* 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.
* <p>
* 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();
parseHeaders(o);
}
if (o instanceof RevCommit)
super.markStart((RevCommit) o);
else
addObject(o);
}
/**
* Mark an object to not produce in the output.
* <p>
* 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.
* <p>
* 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.
* <p>
* 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.
* <p>
* 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;
if (hasRevSort(RevSort.BOUNDARY))
addObject(o);
o = ((RevTag) o).getObject();
parseHeaders(o);
}
if (o instanceof RevCommit)
super.markUninteresting((RevCommit) o);
else if (o instanceof RevTree)
markTreeUninteresting((RevTree) o);
else
o.flags |= UNINTERESTING;
if (o.getType() != Constants.OBJ_COMMIT && hasRevSort(RevSort.BOUNDARY)) {
addObject(o);
}
}
@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 (hasRevSort(RevSort.BOUNDARY))
return r;
continue;
}
if (firstCommit == null)
firstCommit = r;
lastCommit = r;
pendingObjects.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 {
if (last != null)
treeWalk = last instanceof RevTree ? enter(last) : treeWalk.next();
while (!treeWalk.eof()) {
final FileMode mode = treeWalk.getEntryFileMode();
switch (mode.getObjectType()) {
case Constants.OBJ_BLOB: {
treeWalk.getEntryObjectId(idBuffer);
final RevBlob o = lookupBlob(idBuffer);
if ((o.flags & SEEN) != 0)
break;
o.flags |= SEEN;
if (shouldSkipObject(o))
break;
last = o;
return o;
}
case Constants.OBJ_TREE: {
treeWalk.getEntryObjectId(idBuffer);
final RevTree o = lookupTree(idBuffer);
if ((o.flags & SEEN) != 0)
break;
o.flags |= SEEN;
if (shouldSkipObject(o))
break;
last = o;
return o;
}
default:
if (FileMode.GITLINK.equals(mode))
break;
treeWalk.getEntryObjectId(idBuffer);
throw new CorruptObjectException(MessageFormat.format(JGitText.get().corruptObjectInvalidMode3
, mode , idBuffer.name() , treeWalk.getEntryPathString() , currentTree.name()));
}
treeWalk = treeWalk.next();
}
if (firstCommit != null) {
reader.walkAdviceBeginTrees(this, firstCommit, lastCommit);
firstCommit = null;
lastCommit = null;
}
last = null;
for (;;) {
final RevObject o = pendingObjects.next();
if (o == null) {
reader.walkAdviceEnd();
return null;
}
if ((o.flags & SEEN) != 0)
continue;
o.flags |= SEEN;
if (shouldSkipObject(o))
continue;
if (o instanceof RevTree) {
currentTree = (RevTree) o;
treeWalk = treeWalk.resetRoot(reader, currentTree);
}
return o;
}
}
private CanonicalTreeParser enter(RevObject tree) throws IOException {
CanonicalTreeParser p = treeWalk.createSubtreeIterator0(reader, tree);
if (p.eof()) {
// We can't tolerate the subtree being an empty tree, as
// that will break us out early before we visit all names.
// If it is, advance to the parent's next record.
//
return treeWalk.next();
}
return p;
}
private final boolean shouldSkipObject(final RevObject o) {
return (o.flags & UNINTERESTING) != 0 && !hasRevSort(RevSort.BOUNDARY);
}
/**
* Verify all interesting objects are available, and reachable.
* <p>
* Callers should populate starting points and ending points with
* {@link #markStart(RevObject)} and {@link #markUninteresting(RevObject)}
* and then use this method to verify all objects between those two points
* exist in the repository and are readable.
* <p>
* This method returns successfully if everything is connected; it throws an
* exception if there is a connectivity problem. The exception message
* provides some detail about the connectivity failure.
*
* @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 void checkConnectivity() throws MissingObjectException,
IncorrectObjectTypeException, IOException {
for (;;) {
final RevCommit c = next();
if (c == null)
break;
}
for (;;) {
final RevObject o = nextObject();
if (o == null)
break;
if (o instanceof RevBlob && !reader.has(o))
throw new MissingObjectException(o, Constants.TYPE_BLOB);
}
}
/**
* Get the current object's complete path.
* <p>
* 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 last != null ? treeWalk.getEntryPathString() : null;
}
/**
* Get the current object's path hash code.
* <p>
* This method computes a hash code on the fly for this path, the hash is
* suitable to cluster objects that may have similar paths together.
*
* @return path hash code; any integer may be returned.
*/
public int getPathHashCode() {
return last != null ? treeWalk.getEntryPathHashCode() : 0;
}
/** @return the internal buffer holding the current path. */
public byte[] getPathBuffer() {
return last != null ? treeWalk.getEntryPathBuffer() : EMPTY_PATH;
}
/** @return length of the path in {@link #getPathBuffer()}. */
public int getPathLength() {
return last != null ? treeWalk.getEntryPathLength() : 0;
}
@Override
public void dispose() {
super.dispose();
pendingObjects = new BlockObjQueue();
treeWalk = new CanonicalTreeParser();
currentTree = null;
last = null;
firstCommit = null;
lastCommit = null;
}
@Override
protected void reset(final int retainFlags) {
super.reset(retainFlags);
for (RevObject obj : rootObjects)
obj.flags &= ~IN_PENDING;
rootObjects = new ArrayList<RevObject>();
pendingObjects = new BlockObjQueue();
treeWalk = new CanonicalTreeParser();
currentTree = null;
last = null;
firstCommit = null;
lastCommit = null;
}
private void addObject(final RevObject o) {
if ((o.flags & IN_PENDING) == 0) {
o.flags |= IN_PENDING;
rootObjects.add(o);
pendingObjects.add(o);
}
}
private void markTreeUninteresting(final RevTree tree)
throws MissingObjectException, IncorrectObjectTypeException,
IOException {
if ((tree.flags & UNINTERESTING) != 0)
return;
tree.flags |= UNINTERESTING;
treeWalk = treeWalk.resetRoot(reader, tree);
while (!treeWalk.eof()) {
final FileMode mode = treeWalk.getEntryFileMode();
final int sType = mode.getObjectType();
switch (sType) {
case Constants.OBJ_BLOB: {
treeWalk.getEntryObjectId(idBuffer);
lookupBlob(idBuffer).flags |= UNINTERESTING;
break;
}
case Constants.OBJ_TREE: {
treeWalk.getEntryObjectId(idBuffer);
final RevTree t = lookupTree(idBuffer);
if ((t.flags & UNINTERESTING) == 0) {
t.flags |= UNINTERESTING;
treeWalk = treeWalk.createSubtreeIterator0(reader, t);
continue;
}
break;
}
default:
if (FileMode.GITLINK.equals(mode))
break;
treeWalk.getEntryObjectId(idBuffer);
throw new CorruptObjectException(MessageFormat.format(JGitText.get().corruptObjectInvalidMode3
, mode , idBuffer.name() , treeWalk.getEntryPathString() , tree));
}
treeWalk = treeWalk.next();
}
}
}