2 * Copyright (C) 2008 Shawn Pearce <spearce@spearce.org>
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public
6 * License, version 2, as published by the Free Software Foundation.
8 * This library is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
11 * General Public License for more details.
13 * You should have received a copy of the GNU General Public
14 * License along with this library; if not, write to the Free Software
15 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301
17 package org
.spearce
.jgit
.revwalk
;
19 import java
.io
.IOException
;
20 import java
.util
.ArrayList
;
21 import java
.util
.Collection
;
22 import java
.util
.EnumSet
;
23 import java
.util
.Iterator
;
25 import org
.spearce
.jgit
.errors
.IncorrectObjectTypeException
;
26 import org
.spearce
.jgit
.errors
.MissingObjectException
;
27 import org
.spearce
.jgit
.errors
.RevWalkException
;
28 import org
.spearce
.jgit
.lib
.AnyObjectId
;
29 import org
.spearce
.jgit
.lib
.Constants
;
30 import org
.spearce
.jgit
.lib
.MutableObjectId
;
31 import org
.spearce
.jgit
.lib
.ObjectId
;
32 import org
.spearce
.jgit
.lib
.ObjectIdSubclassMap
;
33 import org
.spearce
.jgit
.lib
.ObjectLoader
;
34 import org
.spearce
.jgit
.lib
.Repository
;
35 import org
.spearce
.jgit
.lib
.WindowCursor
;
36 import org
.spearce
.jgit
.revwalk
.filter
.RevFilter
;
37 import org
.spearce
.jgit
.treewalk
.filter
.TreeFilter
;
40 * Walks a commit graph and produces the matching commits in order.
42 * A RevWalk instance can only be used once to generate results. Running a
43 * second time requires creating a new RevWalk instance, or invoking
44 * {@link #reset()} before starting again. Resetting an existing instance may be
45 * faster for some applications as commit body parsing can be avoided on the
48 * RevWalk instances are not thread-safe. Applications must either restrict
49 * usage of a RevWalk instance to a single thread, or implement their own
50 * synchronization at a higher level.
52 * Multiple simultaneous RevWalk instances per {@link Repository} are permitted,
53 * even from concurrent threads. Equality of {@link RevCommit}s from two
54 * different RevWalk instances is never true, even if their {@link ObjectId}s
55 * are equal (and thus they describe the same commit).
57 * The offered iterator is over the list of RevCommits described by the
58 * configuration of this instance. Applications should restrict themselves to
59 * using either the provided Iterator or {@link #next()}, but never use both on
60 * the same RevWalk at the same time. The Iterator may buffer RevCommits, while
61 * {@link #next()} does not.
63 public class RevWalk
implements Iterable
<RevCommit
> {
65 * Set on objects whose important header data has been loaded.
67 * For a RevCommit this indicates we have pulled apart the tree and parent
68 * references from the raw bytes available in the repository and translated
69 * those to our own local RevTree and RevCommit instances. The raw buffer is
70 * also available for message and other header filtering.
72 * For a RevTag this indicates we have pulled part the tag references to
73 * find out who the tag refers to, and what that object's type is.
75 static final int PARSED
= 1 << 0;
78 * Set on RevCommit instances added to our {@link #pending} queue.
80 * We use this flag to avoid adding the same commit instance twice to our
81 * queue, especially if we reached it by more than one path.
83 static final int SEEN
= 1 << 1;
86 * Set on RevCommit instances the caller does not want output.
88 * We flag commits as uninteresting if the caller does not want commits
89 * reachable from a commit given to {@link #markUninteresting(RevCommit)}.
90 * This flag is always carried into the commit's parents and is a key part
91 * of the "rev-list B --not A" feature; A is marked UNINTERESTING.
93 static final int UNINTERESTING
= 1 << 2;
96 * Set on a RevCommit that can collapse out of the history.
98 * If the {@link #treeFilter} concluded that this commit matches his
99 * parents' for all of the paths that the filter is interested in then we
100 * mark the commit REWRITE. Later we can rewrite the parents of a REWRITE
101 * child to remove chains of REWRITE commits before we produce the child to
104 * @see RewriteGenerator
106 static final int REWRITE
= 1 << 3;
109 * Temporary mark for use within generators or filters.
111 * This mark is only for local use within a single scope. If someone sets
112 * the mark they must unset it before any other code can see the mark.
114 static final int TEMP_MARK
= 1 << 4;
117 * Temporary mark for use within {@link TopoSortGenerator}.
119 * This mark indicates the commit could not produce when it wanted to, as at
120 * least one child was behind it. Commits with this flag are delayed until
121 * all children have been output first.
123 static final int TOPO_DELAY
= 1 << 5;
125 /** Number of flag bits we keep internal for our own use. See above flags. */
126 static final int RESERVED_FLAGS
= 6;
128 private static final int APP_FLAGS
= -1 & ~
((1 << RESERVED_FLAGS
) - 1);
132 final WindowCursor curs
;
134 final MutableObjectId idBuffer
;
136 private final ObjectIdSubclassMap
<RevObject
> objects
;
138 private int freeFlags
= APP_FLAGS
;
142 private final ArrayList
<RevCommit
> roots
;
144 AbstractRevQueue queue
;
148 private final EnumSet
<RevSort
> sorting
;
150 private RevFilter filter
;
152 private TreeFilter treeFilter
;
155 * Create a new revision walker for a given repository.
158 * the repository the walker will obtain data from.
160 public RevWalk(final Repository repo
) {
162 curs
= new WindowCursor();
163 idBuffer
= new MutableObjectId();
164 objects
= new ObjectIdSubclassMap
<RevObject
>();
165 roots
= new ArrayList
<RevCommit
>();
166 queue
= new FIFORevQueue();
167 pending
= new StartGenerator(this);
168 sorting
= EnumSet
.of(RevSort
.NONE
);
169 filter
= RevFilter
.ALL
;
170 treeFilter
= TreeFilter
.ALL
;
174 * Get the repository this walker loads objects from.
176 * @return the repository this walker was created to read.
178 public Repository
getRepository() {
183 * Mark a commit to start graph traversal from.
185 * Callers are encouraged to use {@link #parseCommit(AnyObjectId)} to obtain
186 * the commit reference, rather than {@link #lookupCommit(AnyObjectId)}, as
187 * this method requires the commit to be parsed before it can be added as a
188 * root for the traversal.
190 * The method will automatically parse an unparsed commit, but error
191 * handling may be more difficult for the application to explain why a
192 * RevCommit is not actually a commit. The object pool of this walker would
193 * also be 'poisoned' by the non-commit RevCommit.
196 * the commit to start traversing from. The commit passed must be
197 * from this same revision walker.
198 * @throws MissingObjectException
199 * the commit supplied is not available from the object
200 * database. This usually indicates the supplied commit is
201 * invalid, but the reference was constructed during an earlier
202 * invocation to {@link #lookupCommit(AnyObjectId)}.
203 * @throws IncorrectObjectTypeException
204 * the object was not parsed yet and it was discovered during
205 * parsing that it is not actually a commit. This usually
206 * indicates the caller supplied a non-commit SHA-1 to
207 * {@link #lookupCommit(AnyObjectId)}.
208 * @throws IOException
209 * a pack file or loose object could not be read.
211 public void markStart(final RevCommit c
) throws MissingObjectException
,
212 IncorrectObjectTypeException
, IOException
{
213 if ((c
.flags
& SEEN
) != 0)
215 if ((c
.flags
& PARSED
) == 0)
223 * Mark a commit to not produce in the output.
225 * Uninteresting commits denote not just themselves but also their entire
226 * ancestry chain, back until the merge base of an uninteresting commit and
227 * an otherwise interesting commit.
229 * Callers are encouraged to use {@link #parseCommit(AnyObjectId)} to obtain
230 * the commit reference, rather than {@link #lookupCommit(AnyObjectId)}, as
231 * this method requires the commit to be parsed before it can be added as a
232 * root for the traversal.
234 * The method will automatically parse an unparsed commit, but error
235 * handling may be more difficult for the application to explain why a
236 * RevCommit is not actually a commit. The object pool of this walker would
237 * also be 'poisoned' by the non-commit RevCommit.
240 * the commit to start traversing from. The commit passed must be
241 * from this same revision walker.
242 * @throws MissingObjectException
243 * the commit supplied is not available from the object
244 * database. This usually indicates the supplied commit is
245 * invalid, but the reference was constructed during an earlier
246 * invocation to {@link #lookupCommit(AnyObjectId)}.
247 * @throws IncorrectObjectTypeException
248 * the object was not parsed yet and it was discovered during
249 * parsing that it is not actually a commit. This usually
250 * indicates the caller supplied a non-commit SHA-1 to
251 * {@link #lookupCommit(AnyObjectId)}.
252 * @throws IOException
253 * a pack file or loose object could not be read.
255 public void markUninteresting(final RevCommit c
)
256 throws MissingObjectException
, IncorrectObjectTypeException
,
258 c
.flags
|= UNINTERESTING
;
259 c
.carryFlags(UNINTERESTING
);
264 * Pop the next most recent commit.
266 * @return next most recent commit; null if traversal is over.
267 * @throws MissingObjectException
268 * one or or more of the next commit's parents are not available
269 * from the object database, but were thought to be candidates
270 * for traversal. This usually indicates a broken link.
271 * @throws IncorrectObjectTypeException
272 * one or or more of the next commit's parents are not actually
274 * @throws IOException
275 * a pack file or loose object could not be read.
277 public RevCommit
next() throws MissingObjectException
,
278 IncorrectObjectTypeException
, IOException
{
279 return pending
.next();
283 * Obtain the sort types applied to the commits returned.
285 * @return the sorting strategies employed. At least one strategy is always
286 * used, but that strategy may be {@link RevSort#NONE}.
288 public EnumSet
<RevSort
> getRevSort() {
289 return sorting
.clone();
293 * Add or remove a sorting strategy for the returned commits.
295 * Multiple strategies can be applied at once, in which case some strategies
296 * may take precedence over others. As an example, {@link RevSort#TOPO} must
297 * take precedence over {@link RevSort#COMMIT_TIME_DESC}, otherwise it
298 * cannot enforce its ordering.
301 * a sorting strategy to enable or disable.
303 * true if this strategy should be used, false if it should be
306 public void sort(final RevSort s
, final boolean use
) {
313 if (sorting
.size() > 1)
314 sorting
.remove(RevSort
.NONE
);
315 else if (sorting
.size() == 0)
316 sorting
.add(RevSort
.NONE
);
320 * Get the currently configured commit filter.
322 * @return the current filter. Never null as a filter is always needed.
324 public RevFilter
getRevFilter() {
329 * Set the commit filter for this walker.
331 * Multiple filters may be combined by constructing an arbitrary tree of
332 * <code>AndRevFilter</code> or <code>OrRevFilter</code> instances to
333 * describe the boolean expression required by the application. Custom
334 * filter implementations may also be constructed by applications.
336 * Note that filters are not thread-safe and may not be shared by concurrent
337 * RevWalk instances. Every RevWalk must be supplied its own unique filter,
338 * unless the filter implementation specifically states it is (and always
339 * will be) thread-safe. Callers may use {@link RevFilter#clone()} to create
340 * a unique filter tree for this RevWalk instance.
343 * the new filter. If null the special {@link RevFilter#ALL}
344 * filter will be used instead, as it matches every commit.
345 * @see org.spearce.jgit.revwalk.filter.AndRevFilter
346 * @see org.spearce.jgit.revwalk.filter.OrRevFilter
348 public void setRevFilter(final RevFilter newFilter
) {
350 filter
= newFilter
!= null ? newFilter
: RevFilter
.ALL
;
354 * Get the tree filter used to simplify commits by modified paths.
356 * @return the current filter. Never null as a filter is always needed. If
357 * no filter is being applied {@link TreeFilter#ALL} is returned.
359 public TreeFilter
getTreeFilter() {
364 * Set the tree filter used to simplify commits by modified paths.
366 * If null or {@link TreeFilter#ALL} the path limiter is removed. Commits
367 * will not be simplified.
369 * If non-null and not {@link TreeFilter#ALL} then the tree filter will be
370 * installed and commits will have their ancestry simplified to hide commits
371 * that do not contain tree entries matched by the filter.
373 * Usually callers should be inserting a filter graph including
374 * {@link TreeFilter#ANY_DIFF} along with one or more
375 * {@link org.spearce.jgit.treewalk.filter.PathFilter} instances.
378 * new filter. If null the special {@link TreeFilter#ALL} filter
379 * will be used instead, as it matches everything.
380 * @see org.spearce.jgit.treewalk.filter.PathFilter
382 public void setTreeFilter(final TreeFilter newFilter
) {
384 treeFilter
= newFilter
!= null ? newFilter
: TreeFilter
.ALL
;
388 * Locate a reference to a tree without loading it.
390 * The tree may or may not exist in the repository. It is impossible to tell
391 * from this method's return value.
394 * name of the tree object.
395 * @return reference to the tree object. Never null.
397 public RevTree
lookupTree(final AnyObjectId id
) {
398 RevTree c
= (RevTree
) objects
.get(id
);
407 * Locate a reference to a commit without loading it.
409 * The commit may or may not exist in the repository. It is impossible to
410 * tell from this method's return value.
413 * name of the commit object.
414 * @return reference to the commit object. Never null.
416 public RevCommit
lookupCommit(final AnyObjectId id
) {
417 RevCommit c
= (RevCommit
) objects
.get(id
);
419 c
= createCommit(id
);
426 * Locate a reference to any object without loading it.
428 * The object may or may not exist in the repository. It is impossible to
429 * tell from this method's return value.
432 * name of the object.
434 * type of the object. Must be a valid Git object type.
435 * @return reference to the object. Never null.
437 public RevObject
lookupAny(final AnyObjectId id
, final int type
) {
438 RevObject r
= objects
.get(id
);
441 case Constants
.OBJ_COMMIT
:
442 r
= createCommit(id
);
444 case Constants
.OBJ_TREE
:
447 case Constants
.OBJ_BLOB
:
450 case Constants
.OBJ_TAG
:
454 throw new IllegalArgumentException("invalid git type: " + type
);
462 * Locate a reference to a commit and immediately parse its content.
464 * Unlike {@link #lookupCommit(AnyObjectId)} this method only returns
465 * successfully if the commit object exists, is verified to be a commit, and
466 * was parsed without error.
469 * name of the commit object.
470 * @return reference to the commit object. Never null.
471 * @throws MissingObjectException
472 * the supplied commit does not exist.
473 * @throws IncorrectObjectTypeException
474 * the supplied id is not a commit or an annotated tag.
475 * @throws IOException
476 * a pack file or loose object could not be read.
478 public RevCommit
parseCommit(final AnyObjectId id
)
479 throws MissingObjectException
, IncorrectObjectTypeException
,
481 RevObject c
= parseAny(id
);
482 while (c
instanceof RevTag
) {
483 c
= ((RevTag
) c
).getObject();
486 return (RevCommit
) c
;
490 * Locate a reference to any object and immediately parse its content.
492 * This method only returns successfully if the object exists and was parsed
493 * without error. Parsing an object can be expensive as the type must be
494 * determined. For blobs this may mean the blob content was unpacked
495 * unnecessarily, and thrown away.
498 * name of the object.
499 * @return reference to the object. Never null.
500 * @throws MissingObjectException
501 * the supplied does not exist.
502 * @throws IOException
503 * a pack file or loose object could not be read.
505 public RevObject
parseAny(final AnyObjectId id
)
506 throws MissingObjectException
, IOException
{
507 RevObject r
= objects
.get(id
);
509 final ObjectLoader ldr
= db
.openObject(id
);
511 throw new MissingObjectException(id
.toObjectId(), "unknown");
512 final byte[] data
= ldr
.getCachedBytes();
513 final int type
= ldr
.getType();
515 case Constants
.OBJ_COMMIT
: {
516 final RevCommit c
= createCommit(ldr
.getId());
517 c
.parseCanonical(this, data
);
521 case Constants
.OBJ_TREE
: {
522 r
= new RevTree(ldr
.getId());
525 case Constants
.OBJ_BLOB
: {
526 r
= new RevBlob(ldr
.getId());
529 case Constants
.OBJ_TAG
: {
530 final RevTag t
= new RevTag(ldr
.getId());
531 t
.parseCanonical(this, data
);
536 throw new IllegalArgumentException("Bad object type: " + type
);
539 } else if ((r
.flags
& PARSED
) == 0)
545 * Ensure the object's content has been parsed.
547 * This method only returns successfully if the object exists and was parsed
551 * the object the caller needs to be parsed.
552 * @throws MissingObjectException
553 * the supplied does not exist.
554 * @throws IOException
555 * a pack file or loose object could not be read.
557 public void parse(final RevObject obj
) throws MissingObjectException
,
559 if ((obj
.flags
& PARSED
) != 0)
565 * Create a new flag for application use during walking.
567 * Applications are only assured to be able to create 24 unique flags on any
568 * given revision walker instance. Any flags beyond 24 are offered only if
569 * the implementation has extra free space within its internal storage.
572 * description of the flag, primarily useful for debugging.
573 * @return newly constructed flag instance.
574 * @throws IllegalArgumentException
575 * too many flags have been reserved on this revision walker.
577 public RevFlag
newFlag(final String name
) {
579 throw new IllegalArgumentException(32 - RESERVED_FLAGS
580 + " flags already created.");
581 final int m
= Integer
.lowestOneBit(freeFlags
);
583 return new RevFlag(this, name
, m
);
587 * Automatically carry a flag from a child commit to its parents.
589 * A carried flag is copied from the child commit onto its parents when the
590 * child commit is popped from the lowest level of walk's internal graph.
593 * the flag to carry onto parents, if set on a descendant.
595 public void carry(final RevFlag flag
) {
596 if ((freeFlags
& flag
.mask
) != 0)
597 throw new IllegalArgumentException(flag
.name
+ " is disposed.");
598 if (flag
.walker
!= this)
599 throw new IllegalArgumentException(flag
.name
+ " not from this.");
600 carryFlags
|= flag
.mask
;
604 * Automatically carry flags from a child commit to its parents.
606 * A carried flag is copied from the child commit onto its parents when the
607 * child commit is popped from the lowest level of walk's internal graph.
610 * the flags to carry onto parents, if set on a descendant.
612 public void carry(final Collection
<RevFlag
> set
) {
613 for (final RevFlag flag
: set
)
618 * Allow a flag to be recycled for a different use.
620 * Recycled flags always come back as a different Java object instance when
621 * assigned again by {@link #newFlag(String)}.
623 * If the flag was previously being carried, the carrying request is
624 * removed. Disposing of a carried flag while a traversal is in progress has
625 * an undefined behavior.
630 public void disposeFlag(final RevFlag flag
) {
631 freeFlags
|= flag
.mask
;
632 carryFlags
&= ~flag
.mask
;
636 * Resets internal state and allows this instance to be used again.
638 * Unlike {@link #dispose()} previously acquired RevObject (and RevCommit)
639 * instances are not invalidated. RevFlag instances are not invalidated, but
640 * are removed from all RevObjects.
642 public void reset() {
647 * Resets internal state and allows this instance to be used again.
649 * Unlike {@link #dispose()} previously acquired RevObject (and RevCommit)
650 * instances are not invalidated. RevFlag instances are not invalidated, but
651 * are removed from all RevObjects.
654 * application flags that should <b>not</b> be cleared from
655 * existing commit objects.
657 public void resetRetain(final RevFlagSet retainFlags
) {
658 reset(retainFlags
.mask
);
662 * Resets internal state and allows this instance to be used again.
664 * Unlike {@link #dispose()} previously acquired RevObject (and RevCommit)
665 * instances are not invalidated. RevFlag instances are not invalidated, but
666 * are removed from all RevObjects.
669 * application flags that should <b>not</b> be cleared from
670 * existing commit objects.
672 public void resetRetain(final RevFlag
... retainFlags
) {
674 for (final RevFlag flag
: retainFlags
)
679 private void reset(int retainFlags
) {
680 retainFlags
|= PARSED
;
682 final FIFORevQueue q
= new FIFORevQueue();
683 for (final RevCommit c
: roots
) {
684 if ((c
.flags
& SEEN
) == 0)
686 c
.flags
&= retainFlags
;
692 final RevCommit c
= q
.next();
695 for (final RevCommit p
: c
.parents
) {
696 if ((p
.flags
& SEEN
) == 0)
698 p
.flags
&= retainFlags
;
705 queue
= new FIFORevQueue();
706 pending
= new StartGenerator(this);
710 * Dispose all internal state and invalidate all RevObject instances.
712 * All RevObject (and thus RevCommit, etc.) instances previously acquired
713 * from this RevWalk are invalidated by a dispose call. Applications must
714 * not retain or use RevObject instances obtained prior to the dispose call.
715 * All RevFlag instances are also invalidated, and must not be reused.
717 public void dispose() {
718 freeFlags
= APP_FLAGS
;
723 queue
= new FIFORevQueue();
724 pending
= new StartGenerator(this);
728 * Returns an Iterator over the commits of this walker.
730 * The returned iterator is only useful for one walk. If this RevWalk gets
731 * reset a new iterator must be obtained to walk over the new results.
733 * Applications must not use both the Iterator and the {@link #next()} API
734 * at the same time. Pick one API and use that for the entire walk.
736 * If a checked exception is thrown during the walk (see {@link #next()})
737 * it is rethrown from the Iterator as a {@link RevWalkException}.
739 * @return an iterator over this walker's commits.
740 * @see RevWalkException
742 public Iterator
<RevCommit
> iterator() {
743 final RevCommit first
;
745 first
= RevWalk
.this.next();
746 } catch (MissingObjectException e
) {
747 throw new RevWalkException(e
);
748 } catch (IncorrectObjectTypeException e
) {
749 throw new RevWalkException(e
);
750 } catch (IOException e
) {
751 throw new RevWalkException(e
);
754 return new Iterator
<RevCommit
>() {
755 RevCommit next
= first
;
757 public boolean hasNext() {
761 public RevCommit
next() {
763 final RevCommit r
= next
;
764 next
= RevWalk
.this.next();
766 } catch (MissingObjectException e
) {
767 throw new RevWalkException(e
);
768 } catch (IncorrectObjectTypeException e
) {
769 throw new RevWalkException(e
);
770 } catch (IOException e
) {
771 throw new RevWalkException(e
);
775 public void remove() {
776 throw new UnsupportedOperationException();
781 /** Throws an exception if we have started producing output. */
782 protected void assertNotStarted() {
783 if (pending
instanceof StartGenerator
)
785 throw new IllegalStateException("Output has already been started.");
789 * Construct a new unparsed commit for the given object.
792 * the object this walker requires a commit reference for.
793 * @return a new unparsed reference for the object.
795 protected RevCommit
createCommit(final AnyObjectId id
) {
796 return new RevCommit(id
);