/*
 * 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 static java.util.Objects.requireNonNull;
import static org.eclipse.jgit.lib.Constants.OBJ_BLOB;
import static org.eclipse.jgit.lib.Constants.OBJ_COMMIT;
import static org.eclipse.jgit.lib.Constants.OBJ_TREE;

import java.io.IOException;
import java.text.MessageFormat;
import java.util.ArrayList;
import java.util.List;

import org.eclipse.jgit.errors.CorruptObjectException;
import org.eclipse.jgit.errors.IncorrectObjectTypeException;
import org.eclipse.jgit.errors.LargeObjectException;
import org.eclipse.jgit.errors.MissingObjectException;
import org.eclipse.jgit.internal.JGitText;
import org.eclipse.jgit.lib.AnyObjectId;
import org.eclipse.jgit.lib.ObjectReader;
import org.eclipse.jgit.lib.Repository;
import org.eclipse.jgit.revwalk.filter.ObjectFilter;
import org.eclipse.jgit.util.RawParseUtils;

/**
 * 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 org.eclipse.jgit.revwalk.RevSort} used to order the commits that are
 * returned first.
 */
public class ObjectWalk extends RevWalk {
	private static final int ID_SZ = 20;
	private static final int TYPE_SHIFT = 12;
	private static final int TYPE_TREE = 0040000 >>> TYPE_SHIFT;
	private static final int TYPE_SYMLINK = 0120000 >>> TYPE_SHIFT;
	private static final int TYPE_FILE = 0100000 >>> TYPE_SHIFT;
	private static final int TYPE_GITLINK = 0160000 >>> TYPE_SHIFT;

	/**
	 * 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;

	/**
	 * When walking over a tree and blob graph, objects are usually marked as
	 * seen as they are visited and this "seen" status is checked upon the next
	 * visit. If they are already "seen" then they are not processed (returned
	 * by {@link ObjectWalk#nextObject()}) again. However, this behavior can be
	 * overridden by supplying a different implementation of this class.
	 *
	 * @since 5.4
	 */
	public interface VisitationPolicy {
		/**
		 * Whenever the rev or object walk reaches a Git object, if that object
		 * already exists as a RevObject, this method is called to determine if
		 * that object should be visited.
		 *
		 * @param o
		 *            the object to check if it should be visited
		 * @return true if the object should be visited
		 */
		boolean shouldVisit(RevObject o);

		/**
		 * Called when an object is visited.
		 *
		 * @param o
		 *            the object that was visited
		 */
		void visited(RevObject o);
	}

	/**
	 * The default visitation policy: causes all objects to be visited exactly
	 * once.
	 *
	 * @since 5.4
	 */
	public static final VisitationPolicy SIMPLE_VISITATION_POLICY =
			new VisitationPolicy() {
		@Override
		public boolean shouldVisit(RevObject o) {
			return (o.flags & SEEN) == 0;
		}

		@Override
		public void visited(RevObject o) {
			o.flags |= SEEN;
		}
	};

	private List<RevObject> rootObjects;

	private BlockObjQueue pendingObjects;

	private ObjectFilter objectFilter;

	private TreeVisit freeVisit;

	private TreeVisit currVisit;

	private byte[] pathBuf;

	private int pathLen;

	private boolean boundary;

	private VisitationPolicy visitationPolicy = SIMPLE_VISITATION_POLICY;

	/**
	 * Create a new revision and object walker for a given repository.
	 *
	 * @param repo
	 *            the repository the walker will obtain data from.
	 */
	public ObjectWalk(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);
		setRetainBody(false);
		rootObjects = new ArrayList<>();
		pendingObjects = new BlockObjQueue();
		objectFilter = ObjectFilter.ALL;
		pathBuf = new byte[256];
	}

	/**
	 * Mark an object or commit to start graph traversal from.
	 * <p>
	 * Callers are encouraged to use
	 * {@link org.eclipse.jgit.revwalk.RevWalk#parseAny(AnyObjectId)} instead of
	 * {@link org.eclipse.jgit.revwalk.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 org.eclipse.jgit.revwalk.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 org.eclipse.jgit.errors.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 org.eclipse.jgit.revwalk.RevWalk#lookupAny(AnyObjectId, int)}.
	 * @throws org.eclipse.jgit.errors.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 org.eclipse.jgit.revwalk.RevWalk#lookupAny(AnyObjectId, int)}
	 *             call.
	 * @throws java.io.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 org.eclipse.jgit.revwalk.RevWalk#parseAny(AnyObjectId)} instead of
	 * {@link org.eclipse.jgit.revwalk.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 org.eclipse.jgit.revwalk.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 org.eclipse.jgit.errors.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 org.eclipse.jgit.revwalk.RevWalk#lookupAny(AnyObjectId, int)}.
	 * @throws org.eclipse.jgit.errors.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 org.eclipse.jgit.revwalk.RevWalk#lookupAny(AnyObjectId, int)}
	 *             call.
	 * @throws java.io.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 (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() != OBJ_COMMIT && boundary)
			addObject(o);
	}

	/** {@inheritDoc} */
	@Override
	public void sort(RevSort s) {
		super.sort(s);
		boundary = hasRevSort(RevSort.BOUNDARY);
	}

	/** {@inheritDoc} */
	@Override
	public void sort(RevSort s, boolean use) {
		super.sort(s, use);
		boundary = hasRevSort(RevSort.BOUNDARY);
	}

	/**
	 * Get the currently configured object filter.
	 *
	 * @return the current filter. Never null as a filter is always needed.
	 * @since 4.0
	 */
	public ObjectFilter getObjectFilter() {
		return objectFilter;
	}

	/**
	 * Set the object filter for this walker. This filter affects the objects
	 * visited by {@link #nextObject()}. It does not affect the commits listed
	 * by {@link #next()}.
	 * <p>
	 * If the filter returns false for an object, then that object is skipped
	 * and objects reachable from it are not enqueued to be walked recursively.
	 * This can be used to speed up the object walk by skipping subtrees that
	 * are known to be uninteresting.
	 *
	 * @param newFilter
	 *            the new filter. If null the special
	 *            {@link org.eclipse.jgit.revwalk.filter.ObjectFilter#ALL}
	 *            filter will be used instead, as it matches every object.
	 * @since 4.0
	 */
	public void setObjectFilter(ObjectFilter newFilter) {
		assertNotStarted();
		objectFilter = newFilter != null ? newFilter : ObjectFilter.ALL;
	}

	/**
	 * Sets the visitation policy to use during this walk.
	 *
	 * @param policy
	 *            the {@code VisitationPolicy} to use
	 * @since 5.4
	 */
	public void setVisitationPolicy(VisitationPolicy policy) {
		assertNotStarted();
		visitationPolicy = requireNonNull(policy);
	}

	/** {@inheritDoc} */
	@Override
	public RevCommit next() throws MissingObjectException,
			IncorrectObjectTypeException, IOException {
		for (;;) {
			final RevCommit r = super.next();
			if (r == null) {
				return null;
			}
			final RevTree t = r.getTree();
			if ((r.flags & UNINTERESTING) != 0) {
				if (objectFilter.include(this, t)) {
					markTreeUninteresting(t);
				}
				if (boundary) {
					return r;
				}
				continue;
			}
			if (objectFilter.include(this, t)) {
				pendingObjects.add(t);
			}
			return r;
		}
	}

	/**
	 * Skips the current tree such that {@link #nextObject()} does not return
	 * any objects inside it. This should be called right after
	 * {@link #nextObject()} returns the tree.
	 *
	 * @since 5.4
	 */
	public void skipTree() {
		currVisit.ptr = currVisit.buf.length;
	}

	/**
	 * Pop the next most recent object.
	 *
	 * @return next most recent object; null if traversal is over.
	 * @throws org.eclipse.jgit.errors.MissingObjectException
	 *             one 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 org.eclipse.jgit.errors.IncorrectObjectTypeException
	 *             one or more of the objects in a tree do not match the type
	 *             indicated.
	 * @throws java.io.IOException
	 *             a pack file or loose object could not be read.
	 */
	public RevObject nextObject() throws MissingObjectException,
			IncorrectObjectTypeException, IOException {
		pathLen = 0;

		TreeVisit tv = currVisit;
		while (tv != null) {
			byte[] buf = tv.buf;
			for (int ptr = tv.ptr; ptr < buf.length;) {
				int startPtr = ptr;
				ptr = findObjectId(buf, ptr);
				idBuffer.fromRaw(buf, ptr);
				ptr += ID_SZ;

				if (!objectFilter.include(this, idBuffer)) {
					continue;
				}

				RevObject obj = objects.get(idBuffer);
				if (obj != null && !visitationPolicy.shouldVisit(obj))
					continue;

				int mode = parseMode(buf, startPtr, ptr, tv);
				switch (mode >>> TYPE_SHIFT) {
				case TYPE_FILE:
				case TYPE_SYMLINK:
					if (obj == null) {
						obj = new RevBlob(idBuffer);
						visitationPolicy.visited(obj);
						objects.add(obj);
						return obj;
					}
					if (!(obj instanceof RevBlob))
						throw new IncorrectObjectTypeException(obj, OBJ_BLOB);
					visitationPolicy.visited(obj);
					if ((obj.flags & UNINTERESTING) == 0)
						return obj;
					if (boundary)
						return obj;
					continue;

				case TYPE_TREE:
					if (obj == null) {
						obj = new RevTree(idBuffer);
						visitationPolicy.visited(obj);
						objects.add(obj);
						return pushTree(obj);
					}
					if (!(obj instanceof RevTree))
						throw new IncorrectObjectTypeException(obj, OBJ_TREE);
					visitationPolicy.visited(obj);
					if ((obj.flags & UNINTERESTING) == 0)
						return pushTree(obj);
					if (boundary)
						return pushTree(obj);
					continue;

				case TYPE_GITLINK:
					continue;

				default:
					throw new CorruptObjectException(MessageFormat.format(
							JGitText.get().corruptObjectInvalidMode3,
							String.format("%o", Integer.valueOf(mode)), //$NON-NLS-1$
							idBuffer.name(),
							RawParseUtils.decode(buf, tv.namePtr, tv.nameEnd),
							tv.obj));
				}
			}

			currVisit = tv.parent;
			releaseTreeVisit(tv);
			tv = currVisit;
		}

		for (;;) {
			RevObject o = pendingObjects.next();
			if (o == null) {
				return null;
			}
			if (!visitationPolicy.shouldVisit(o)) {
				continue;
			}
			visitationPolicy.visited(o);
			if ((o.flags & UNINTERESTING) == 0 || boundary) {
				if (o instanceof RevTree) {
					// The previous while loop should have exhausted the stack
					// of trees.
					assert currVisit == null;

					pushTree(o);
				}
				return o;
			}
		}
	}

	private static int findObjectId(byte[] buf, int ptr) {
		// Skip over the mode and name until the NUL before the ObjectId
		// can be located. Skip the NUL as the function returns.
		for (;;) {
			if (buf[++ptr] == 0) return ++ptr;
			if (buf[++ptr] == 0) return ++ptr;
			if (buf[++ptr] == 0) return ++ptr;
			if (buf[++ptr] == 0) return ++ptr;

			if (buf[++ptr] == 0) return ++ptr;
			if (buf[++ptr] == 0) return ++ptr;
			if (buf[++ptr] == 0) return ++ptr;
			if (buf[++ptr] == 0) return ++ptr;

			if (buf[++ptr] == 0) return ++ptr;
			if (buf[++ptr] == 0) return ++ptr;
			if (buf[++ptr] == 0) return ++ptr;
			if (buf[++ptr] == 0) return ++ptr;

			if (buf[++ptr] == 0) return ++ptr;
			if (buf[++ptr] == 0) return ++ptr;
			if (buf[++ptr] == 0) return ++ptr;
			if (buf[++ptr] == 0) return ++ptr;
		}
	}

	private static int parseMode(byte[] buf, int startPtr, int recEndPtr, TreeVisit tv) {
		int mode = buf[startPtr] - '0';
		for (;;) {
			byte c = buf[++startPtr];
			if (' ' == c)
				break;
			mode <<= 3;
			mode += c - '0';

			c = buf[++startPtr];
			if (' ' == c)
				break;
			mode <<= 3;
			mode += c - '0';

			c = buf[++startPtr];
			if (' ' == c)
				break;
			mode <<= 3;
			mode += c - '0';

			c = buf[++startPtr];
			if (' ' == c)
				break;
			mode <<= 3;
			mode += c - '0';

			c = buf[++startPtr];
			if (' ' == c)
				break;
			mode <<= 3;
			mode += c - '0';

			c = buf[++startPtr];
			if (' ' == c)
				break;
			mode <<= 3;
			mode += c - '0';

			c = buf[++startPtr];
			if (' ' == c)
				break;
			mode <<= 3;
			mode += c - '0';
		}

		tv.ptr = recEndPtr;
		tv.namePtr = startPtr + 1;
		tv.nameEnd = recEndPtr - (ID_SZ + 1);
		return mode;
	}

	/**
	 * 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 org.eclipse.jgit.errors.MissingObjectException
	 *             one 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 org.eclipse.jgit.errors.IncorrectObjectTypeException
	 *             one or more of the objects in a tree do not match the type
	 *             indicated.
	 * @throws java.io.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, OBJ_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() {
		if (pathLen == 0) {
			pathLen = updatePathBuf(currVisit);
			if (pathLen == 0)
				return null;
		}
		return RawParseUtils.decode(pathBuf, 0, pathLen);
	}

	/**
	 * @return the current traversal depth from the root tree object
	 * @since 5.4
	 */
	public int getTreeDepth() {
		if (currVisit == null) {
			return 0;
		}
		return currVisit.depth;
	}

	/**
	 * 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() {
		TreeVisit tv = currVisit;
		if (tv == null)
			return 0;

		int nameEnd = tv.nameEnd;
		if (nameEnd == 0) {
			// When nameEnd == 0 the subtree is itself the current path
			// being visited. The name hash must be obtained from its
			// parent tree. If there is no parent, this is a root tree with
			// a hash code of 0.
			tv = tv.parent;
			if (tv == null)
				return 0;
			nameEnd = tv.nameEnd;
		}

		byte[] buf;
		int ptr;

		if (16 <= (nameEnd - tv.namePtr)) {
			buf = tv.buf;
			ptr = nameEnd - 16;
		} else {
			nameEnd = pathLen;
			if (nameEnd == 0) {
				nameEnd = updatePathBuf(currVisit);
				pathLen = nameEnd;
			}
			buf = pathBuf;
			ptr = Math.max(0, nameEnd - 16);
		}

		int hash = 0;
		for (; ptr < nameEnd; ptr++) {
			byte c = buf[ptr];
			if (c != ' ')
				hash = (hash >>> 2) + (c << 24);
		}
		return hash;
	}

	/**
	 * Get the internal buffer holding the current path.
	 *
	 * @return the internal buffer holding the current path.
	 */
	public byte[] getPathBuffer() {
		if (pathLen == 0)
			pathLen = updatePathBuf(currVisit);
		return pathBuf;
	}

	/**
	 * Get length of the path in {@link #getPathBuffer()}.
	 *
	 * @return length of the path in {@link #getPathBuffer()}.
	 */
	public int getPathLength() {
		if (pathLen == 0)
			pathLen = updatePathBuf(currVisit);
		return pathLen;
	}

	private int updatePathBuf(TreeVisit tv) {
		if (tv == null)
			return 0;

		// If nameEnd == 0 this tree has not yet contributed an entry.
		// Update only for the parent, which if null will be empty.
		int nameEnd = tv.nameEnd;
		if (nameEnd == 0)
			return updatePathBuf(tv.parent);

		int ptr = tv.pathLen;
		if (ptr == 0) {
			ptr = updatePathBuf(tv.parent);
			if (ptr == pathBuf.length)
				growPathBuf(ptr);
			if (ptr != 0)
				pathBuf[ptr++] = '/';
			tv.pathLen = ptr;
		}

		int namePtr = tv.namePtr;
		int nameLen = nameEnd - namePtr;
		int end = ptr + nameLen;
		while (pathBuf.length < end)
			growPathBuf(ptr);
		System.arraycopy(tv.buf, namePtr, pathBuf, ptr, nameLen);
		return end;
	}

	private void growPathBuf(int ptr) {
		byte[] newBuf = new byte[pathBuf.length << 1];
		System.arraycopy(pathBuf, 0, newBuf, 0, ptr);
		pathBuf = newBuf;
	}

	/** {@inheritDoc} */
	@Override
	public void dispose() {
		super.dispose();
		pendingObjects = new BlockObjQueue();
		currVisit = null;
		freeVisit = null;
	}

	/** {@inheritDoc} */
	@Override
	protected void reset(int retainFlags) {
		super.reset(retainFlags);

		for (RevObject obj : rootObjects)
			obj.flags &= ~IN_PENDING;

		rootObjects = new ArrayList<>();
		pendingObjects = new BlockObjQueue();
		currVisit = null;
		freeVisit = null;
	}

	private void addObject(RevObject o) {
		if ((o.flags & IN_PENDING) == 0) {
			o.flags |= IN_PENDING;
			rootObjects.add(o);
			pendingObjects.add(o);
		}
	}

	private void markTreeUninteresting(RevTree tree)
			throws MissingObjectException, IncorrectObjectTypeException,
			IOException {
		if ((tree.flags & UNINTERESTING) != 0)
			return;
		tree.flags |= UNINTERESTING;

		byte[] raw = reader.open(tree, OBJ_TREE).getCachedBytes();
		for (int ptr = 0; ptr < raw.length;) {
			byte c = raw[ptr];
			int mode = c - '0';
			for (;;) {
				c = raw[++ptr];
				if (' ' == c)
					break;
				mode <<= 3;
				mode += c - '0';
			}
			while (raw[++ptr] != 0) {
				// Skip entry name.
			}
			ptr++; // Skip NUL after entry name.

			switch (mode >>> TYPE_SHIFT) {
			case TYPE_FILE:
			case TYPE_SYMLINK:
				idBuffer.fromRaw(raw, ptr);
				lookupBlob(idBuffer).flags |= UNINTERESTING;
				break;

			case TYPE_TREE:
				idBuffer.fromRaw(raw, ptr);
				markTreeUninteresting(lookupTree(idBuffer));
				break;

			case TYPE_GITLINK:
				break;

			default:
				idBuffer.fromRaw(raw, ptr);
				throw new CorruptObjectException(MessageFormat.format(
						JGitText.get().corruptObjectInvalidMode3,
						String.format("%o", Integer.valueOf(mode)), //$NON-NLS-1$
						idBuffer.name(), "", tree)); //$NON-NLS-1$
			}
			ptr += ID_SZ;
		}
	}

	private RevObject pushTree(RevObject obj) throws LargeObjectException,
			MissingObjectException, IncorrectObjectTypeException, IOException {
		TreeVisit tv = freeVisit;
		if (tv != null) {
			freeVisit = tv.parent;
			tv.ptr = 0;
			tv.namePtr = 0;
			tv.nameEnd = 0;
			tv.pathLen = 0;
		} else {
			tv = new TreeVisit();
		}
		tv.obj = obj;
		tv.buf = reader.open(obj, OBJ_TREE).getCachedBytes();
		tv.parent = currVisit;
		currVisit = tv;
		if (tv.parent == null) {
			tv.depth = 1;
		} else {
			tv.depth = tv.parent.depth + 1;
		}

		return obj;
	}

	private void releaseTreeVisit(TreeVisit tv) {
		tv.buf = null;
		tv.parent = freeVisit;
		freeVisit = tv;
	}

	private static class TreeVisit {
		/** Parent tree visit that entered this tree, null if root tree. */
		TreeVisit parent;

		/** The RevTree currently being iterated through. */
		RevObject obj;

		/** Canonical encoding of the tree named by {@link #obj}. */
		byte[] buf;

		/** Index of next entry to parse in {@link #buf}. */
		int ptr;

		/** Start of the current name entry in {@link #buf}. */
		int namePtr;

		/** One past end of name, {@code nameEnd - namePtr} is the length. */
		int nameEnd;

		/** Number of bytes in the path leading up to this tree. */
		int pathLen;

		/** Number of levels deep from the root tree. 0 for root tree. */
		int depth;
	}
}