diff options
Diffstat (limited to 'org.eclipse.jgit/src/org/eclipse/jgit/revwalk/ObjectWalk.java')
| -rw-r--r-- | org.eclipse.jgit/src/org/eclipse/jgit/revwalk/ObjectWalk.java | 323 |
1 files changed, 203 insertions, 120 deletions
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/ObjectWalk.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/ObjectWalk.java index 9c3af5a5dc..7c763bc9b8 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/ObjectWalk.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/ObjectWalk.java @@ -1,48 +1,16 @@ /* - * Copyright (C) 2008, Shawn O. Pearce <spearce@spearce.org> - * and other copyright owners as documented in the project's IP log. + * Copyright (C) 2008, 2022 Shawn O. Pearce <spearce@spearce.org> and others * - * 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 + * This program and the accompanying materials are made available under the + * terms of the Eclipse Distribution License v. 1.0 which is available at + * https://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. + * SPDX-License-Identifier: BSD-3-Clause */ 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; @@ -75,9 +43,10 @@ import org.eclipse.jgit.util.RawParseUtils; * 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. + * 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; @@ -96,6 +65,55 @@ public class ObjectWalk extends RevWalk { */ 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; @@ -112,14 +130,16 @@ public class ObjectWalk extends RevWalk { 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(final Repository repo) { - this(repo.newObjectReader()); + public ObjectWalk(Repository repo) { + this(repo.newObjectReader(), true); } /** @@ -131,9 +151,13 @@ public class ObjectWalk extends RevWalk { * required. */ public ObjectWalk(ObjectReader or) { - super(or); + this(or, false); + } + + private ObjectWalk(ObjectReader or, boolean closeReader) { + super(or, closeReader); setRetainBody(false); - rootObjects = new ArrayList<RevObject>(); + rootObjects = new ArrayList<>(); pendingObjects = new BlockObjQueue(); objectFilter = ObjectFilter.ALL; pathBuf = new byte[256]; @@ -142,34 +166,39 @@ public class ObjectWalk extends RevWalk { /** * 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. + * 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 RevWalk#markStart(RevCommit)} - * if passed RevCommit instance, or a RevTag that directly (or indirectly) - * references a RevCommit. + * 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 MissingObjectException + * @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 RevWalk#lookupAny(AnyObjectId, int)}. - * @throws IncorrectObjectTypeException + * 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 RevWalk#lookupAny(AnyObjectId, int)} call. - * @throws IOException + * 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, @@ -193,33 +222,38 @@ public class ObjectWalk extends RevWalk { * 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. + * 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 RevWalk#markStart(RevCommit)} - * if passed RevCommit instance, or a RevTag that directly (or indirectly) - * references a RevCommit. + * 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 MissingObjectException + * @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 RevWalk#lookupAny(AnyObjectId, int)}. - * @throws IncorrectObjectTypeException + * 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 RevWalk#lookupAny(AnyObjectId, int)} call. - * @throws IOException + * 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, @@ -243,6 +277,7 @@ public class ObjectWalk extends RevWalk { addObject(o); } + @Override public void sort(RevSort s) { super.sort(s); boundary = hasRevSort(RevSort.BOUNDARY); @@ -258,7 +293,6 @@ public class ObjectWalk extends RevWalk { * Get the currently configured object filter. * * @return the current filter. Never null as a filter is always needed. - * * @since 4.0 */ public ObjectFilter getObjectFilter() { @@ -266,9 +300,9 @@ public class ObjectWalk extends RevWalk { } /** - * 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()}. + * 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. @@ -276,9 +310,9 @@ public class ObjectWalk extends RevWalk { * are known to be uninteresting. * * @param newFilter - * the new filter. If null the special {@link ObjectFilter#ALL} + * 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) { @@ -286,6 +320,18 @@ public class ObjectWalk extends RevWalk { 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); + } + @Override public RevCommit next() throws MissingObjectException, IncorrectObjectTypeException, IOException { @@ -312,17 +358,30 @@ public class ObjectWalk extends RevWalk { } /** + * 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() { + if (currVisit != null) { + currVisit.ptr = currVisit.buf.length; + } + } + + /** * 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 + * @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 IncorrectObjectTypeException - * one or or more of the objects in a tree do not match the type + * @throws org.eclipse.jgit.errors.IncorrectObjectTypeException + * one or more of the objects in a tree do not match the type * indicated. - * @throws IOException + * @throws java.io.IOException * a pack file or loose object could not be read. */ public RevObject nextObject() throws MissingObjectException, @@ -343,24 +402,23 @@ public class ObjectWalk extends RevWalk { } RevObject obj = objects.get(idBuffer); - if (obj != null && (obj.flags & SEEN) != 0) + if (obj != null && !visitationPolicy.shouldVisit(obj)) continue; int mode = parseMode(buf, startPtr, ptr, tv); - int flags; switch (mode >>> TYPE_SHIFT) { case TYPE_FILE: case TYPE_SYMLINK: if (obj == null) { obj = new RevBlob(idBuffer); - obj.flags = SEEN; + visitationPolicy.visited(obj); objects.add(obj); return obj; } if (!(obj instanceof RevBlob)) throw new IncorrectObjectTypeException(obj, OBJ_BLOB); - obj.flags = flags = obj.flags | SEEN; - if ((flags & UNINTERESTING) == 0) + visitationPolicy.visited(obj); + if ((obj.flags & UNINTERESTING) == 0) return obj; if (boundary) return obj; @@ -369,17 +427,17 @@ public class ObjectWalk extends RevWalk { case TYPE_TREE: if (obj == null) { obj = new RevTree(idBuffer); - obj.flags = SEEN; + visitationPolicy.visited(obj); objects.add(obj); - return enterTree(obj); + return pushTree(obj); } if (!(obj instanceof RevTree)) throw new IncorrectObjectTypeException(obj, OBJ_TREE); - obj.flags = flags = obj.flags | SEEN; - if ((flags & UNINTERESTING) == 0) - return enterTree(obj); + visitationPolicy.visited(obj); + if ((obj.flags & UNINTERESTING) == 0) + return pushTree(obj); if (boundary) - return enterTree(obj); + return pushTree(obj); continue; case TYPE_GITLINK: @@ -405,30 +463,23 @@ public class ObjectWalk extends RevWalk { if (o == null) { return null; } - int flags = o.flags; - if ((flags & SEEN) != 0) + if (!visitationPolicy.shouldVisit(o)) { continue; - flags |= SEEN; - o.flags = flags; - if ((flags & UNINTERESTING) == 0 | boundary) { + } + visitationPolicy.visited(o); + if ((o.flags & UNINTERESTING) == 0 || boundary) { if (o instanceof RevTree) { - tv = newTreeVisit(o); - tv.parent = null; - currVisit = tv; + // The previous while loop should have exhausted the stack + // of trees. + assert currVisit == null; + + pushTree(o); } return o; } } } - private RevObject enterTree(RevObject obj) throws MissingObjectException, - IncorrectObjectTypeException, IOException { - TreeVisit tv = newTreeVisit(obj); - tv.parent = currVisit; - currVisit = tv; - return obj; - } - 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. @@ -519,14 +570,14 @@ public class ObjectWalk extends RevWalk { * 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 + * @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 IncorrectObjectTypeException - * one or or more of the objects in a tree do not match the type + * @throws org.eclipse.jgit.errors.IncorrectObjectTypeException + * one or more of the objects in a tree do not match the type * indicated. - * @throws IOException + * @throws java.io.IOException * a pack file or loose object could not be read. */ public void checkConnectivity() throws MissingObjectException, @@ -568,6 +619,19 @@ public class ObjectWalk extends RevWalk { } /** + * Get the current traversal depth from the root tree object + * + * @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 @@ -617,14 +681,22 @@ public class ObjectWalk extends RevWalk { return hash; } - /** @return the internal buffer holding the current path. */ + /** + * 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; } - /** @return length of the path in {@link #getPathBuffer()}. */ + /** + * 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); @@ -675,19 +747,19 @@ public class ObjectWalk extends RevWalk { } @Override - protected void reset(final int retainFlags) { + protected void reset(int retainFlags) { super.reset(retainFlags); for (RevObject obj : rootObjects) obj.flags &= ~IN_PENDING; - rootObjects = new ArrayList<RevObject>(); + rootObjects = new ArrayList<>(); pendingObjects = new BlockObjQueue(); currVisit = null; freeVisit = null; } - private void addObject(final RevObject o) { + private void addObject(RevObject o) { if ((o.flags & IN_PENDING) == 0) { o.flags |= IN_PENDING; rootObjects.add(o); @@ -695,7 +767,7 @@ public class ObjectWalk extends RevWalk { } } - private void markTreeUninteresting(final RevTree tree) + private void markTreeUninteresting(RevTree tree) throws MissingObjectException, IncorrectObjectTypeException, IOException { if ((tree.flags & UNINTERESTING) != 0) @@ -744,7 +816,7 @@ public class ObjectWalk extends RevWalk { } } - private TreeVisit newTreeVisit(RevObject obj) throws LargeObjectException, + private RevObject pushTree(RevObject obj) throws LargeObjectException, MissingObjectException, IncorrectObjectTypeException, IOException { TreeVisit tv = freeVisit; if (tv != null) { @@ -758,7 +830,15 @@ public class ObjectWalk extends RevWalk { } tv.obj = obj; tv.buf = reader.open(obj, OBJ_TREE).getCachedBytes(); - return tv; + 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) { @@ -788,5 +868,8 @@ public class ObjectWalk extends RevWalk { /** 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; } } |