2 * Copyright (C) 2008, Shawn O. Pearce <spearce@spearce.org>
6 * Redistribution and use in source and binary forms, with or
7 * without modification, are permitted provided that the following
10 * - Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
13 * - Redistributions in binary form must reproduce the above
14 * copyright notice, this list of conditions and the following
15 * disclaimer in the documentation and/or other materials provided
16 * with the distribution.
18 * - Neither the name of the Git Development Community nor the
19 * names of its contributors may be used to endorse or promote
20 * products derived from this software without specific prior
23 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
24 * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
25 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
26 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
27 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
28 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
29 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
30 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
31 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
32 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
33 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
34 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
35 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
38 package org
.spearce
.jgit
.treewalk
;
40 import java
.io
.IOException
;
41 import java
.util
.Collections
;
43 import org
.spearce
.jgit
.errors
.CorruptObjectException
;
44 import org
.spearce
.jgit
.errors
.IncorrectObjectTypeException
;
45 import org
.spearce
.jgit
.errors
.MissingObjectException
;
46 import org
.spearce
.jgit
.errors
.StopWalkException
;
47 import org
.spearce
.jgit
.lib
.Constants
;
48 import org
.spearce
.jgit
.lib
.FileMode
;
49 import org
.spearce
.jgit
.lib
.ObjectId
;
50 import org
.spearce
.jgit
.lib
.Repository
;
51 import org
.spearce
.jgit
.revwalk
.RevTree
;
52 import org
.spearce
.jgit
.treewalk
.filter
.PathFilterGroup
;
53 import org
.spearce
.jgit
.treewalk
.filter
.TreeFilter
;
54 import org
.spearce
.jgit
.util
.RawParseUtils
;
57 * Walks one or more {@link AbstractTreeIterator}s in parallel.
59 * This class can perform n-way differences across as many trees as necessary.
61 * A TreeWalk instance can only be used once to generate results. Running a
62 * second time requires creating a new TreeWalk instance, or invoking
63 * {@link #reset()} and adding new trees before starting again. Resetting an
64 * existing instance may be faster for some applications as some internal
65 * buffers may be recycled.
67 * TreeWalk instances are not thread-safe. Applications must either restrict
68 * usage of a TreeWalk instance to a single thread, or implement their own
69 * synchronization at a higher level.
71 * Multiple simultaneous TreeWalk instances per {@link Repository} are
72 * permitted, even from concurrent threads.
74 public class TreeWalk
{
76 * Open a tree walk and filter to exactly one path.
78 * The returned tree walk is already positioned on the requested path, so
79 * the caller should not need to invoke {@link #next()} unless they are
80 * looking for a possible directory/file name conflict.
83 * repository to read tree object data from.
85 * single path to advance the tree walk instance into.
87 * one or more trees to walk through.
88 * @return a new tree walk configured for exactly this one path; null if no
89 * path was found in any of the trees.
91 * reading a pack file or loose object failed.
92 * @throws CorruptObjectException
93 * an tree object could not be read as its data stream did not
94 * appear to be a tree, or could not be inflated.
95 * @throws IncorrectObjectTypeException
96 * an object we expected to be a tree was not a tree.
97 * @throws MissingObjectException
98 * a tree object was not found.
100 public static TreeWalk
forPath(final Repository db
, final String path
,
101 final ObjectId
[] trees
) throws MissingObjectException
,
102 IncorrectObjectTypeException
, CorruptObjectException
, IOException
{
103 final TreeWalk r
= new TreeWalk(db
);
104 r
.setFilter(PathFilterGroup
.createFromStrings(Collections
106 r
.setRecursive(r
.getFilter().shouldBeRecursive());
108 return r
.next() ? r
: null;
112 * Open a tree walk and filter to exactly one path.
114 * The returned tree walk is already positioned on the requested path, so
115 * the caller should not need to invoke {@link #next()} unless they are
116 * looking for a possible directory/file name conflict.
119 * repository to read tree object data from.
121 * single path to advance the tree walk instance into.
123 * the single tree to walk through.
124 * @return a new tree walk configured for exactly this one path; null if no
125 * path was found in any of the trees.
126 * @throws IOException
127 * reading a pack file or loose object failed.
128 * @throws CorruptObjectException
129 * an tree object could not be read as its data stream did not
130 * appear to be a tree, or could not be inflated.
131 * @throws IncorrectObjectTypeException
132 * an object we expected to be a tree was not a tree.
133 * @throws MissingObjectException
134 * a tree object was not found.
136 public static TreeWalk
forPath(final Repository db
, final String path
,
137 final RevTree tree
) throws MissingObjectException
,
138 IncorrectObjectTypeException
, CorruptObjectException
, IOException
{
139 return forPath(db
, path
, new ObjectId
[] { tree
});
142 private final Repository db
;
144 private TreeFilter filter
;
146 private AbstractTreeIterator
[] trees
;
148 private boolean recursive
;
152 private boolean advance
;
154 private AbstractTreeIterator currentHead
;
157 * Create a new tree walker for a given repository.
160 * the repository the walker will obtain data from.
162 public TreeWalk(final Repository repo
) {
164 filter
= TreeFilter
.ALL
;
165 trees
= new AbstractTreeIterator
[] { new EmptyTreeIterator() };
169 * Get the repository this tree walker is reading from.
171 * @return the repository configured when the walker was created.
173 public Repository
getRepository() {
178 * Get the currently configured filter.
180 * @return the current filter. Never null as a filter is always needed.
182 public TreeFilter
getFilter() {
187 * Set the tree entry filter for this walker.
189 * Multiple filters may be combined by constructing an arbitrary tree of
190 * <code>AndTreeFilter</code> or <code>OrTreeFilter</code> instances to
191 * describe the boolean expression required by the application. Custom
192 * filter implementations may also be constructed by applications.
194 * Note that filters are not thread-safe and may not be shared by concurrent
195 * TreeWalk instances. Every TreeWalk must be supplied its own unique
196 * filter, unless the filter implementation specifically states it is (and
197 * always will be) thread-safe. Callers may use {@link TreeFilter#clone()}
198 * to create a unique filter tree for this TreeWalk instance.
201 * the new filter. If null the special {@link TreeFilter#ALL}
202 * filter will be used instead, as it matches every entry.
203 * @see org.spearce.jgit.treewalk.filter.AndTreeFilter
204 * @see org.spearce.jgit.treewalk.filter.OrTreeFilter
206 public void setFilter(final TreeFilter newFilter
) {
207 filter
= newFilter
!= null ? newFilter
: TreeFilter
.ALL
;
211 * Is this walker automatically entering into subtrees?
213 * If the walker is recursive then the caller will not see a subtree node
214 * and instead will only receive file nodes in all relevant subtrees.
216 * @return true if automatically entering subtrees is enabled.
218 public boolean isRecursive() {
223 * Set the walker to enter (or not enter) subtrees automatically.
225 * If recursive mode is enabled the walker will hide subtree nodes from the
226 * calling application and will produce only file level nodes. If a tree
227 * (directory) is deleted then all of the file level nodes will appear to be
228 * deleted, recursively, through as many levels as necessary to account for
232 * true to skip subtree nodes and only obtain files nodes.
234 public void setRecursive(final boolean b
) {
238 /** Reset this walker so new tree iterators can be added to it. */
239 public void reset() {
240 trees
= new AbstractTreeIterator
[0];
246 * Reset this walker to run over a set of existing trees.
249 * the trees we need to parse. The walker will execute over this
250 * many parallel trees if the reset is successful.
251 * @throws MissingObjectException
252 * the given tree object does not exist in this repository.
253 * @throws IncorrectObjectTypeException
254 * the given object id does not denote a tree, but instead names
255 * some other non-tree type of object. Note that commits are not
256 * trees, even if they are sometimes called a "tree-ish".
257 * @throws CorruptObjectException
258 * the object claimed to be a tree, but its contents did not
259 * appear to be a tree. The repository may have data corruption.
260 * @throws IOException
261 * a loose object or pack file could not be read.
263 public void reset(final ObjectId
[] ids
) throws MissingObjectException
,
264 IncorrectObjectTypeException
, CorruptObjectException
, IOException
{
265 final int oldLen
= trees
.length
;
266 final int newLen
= ids
.length
;
267 final AbstractTreeIterator
[] r
= newLen
== oldLen ? trees
268 : new AbstractTreeIterator
[newLen
];
269 for (int i
= 0; i
< newLen
; i
++) {
270 AbstractTreeIterator o
;
274 while (o
.parent
!= null)
276 if (o
instanceof CanonicalTreeParser
) {
278 ((CanonicalTreeParser
) o
).reset(db
, ids
[i
]);
284 o
= parserFor(ids
[i
]);
294 * Add an already existing tree object for walking.
296 * The position of this tree is returned to the caller, in case the caller
297 * has lost track of the order they added the trees into the walker.
300 * identity of the tree object the caller wants walked.
301 * @return position of this tree within the walker.
302 * @throws MissingObjectException
303 * the given tree object does not exist in this repository.
304 * @throws IncorrectObjectTypeException
305 * the given object id does not denote a tree, but instead names
306 * some other non-tree type of object. Note that commits are not
307 * trees, even if they are sometimes called a "tree-ish".
308 * @throws CorruptObjectException
309 * the object claimed to be a tree, but its contents did not
310 * appear to be a tree. The repository may have data corruption.
311 * @throws IOException
312 * a loose object or pack file could not be read.
314 public int addTree(final ObjectId id
) throws MissingObjectException
,
315 IncorrectObjectTypeException
, CorruptObjectException
, IOException
{
316 return addTree(parserFor(id
));
320 * Add an already created tree iterator for walking.
322 * The position of this tree is returned to the caller, in case the caller
323 * has lost track of the order they added the trees into the walker.
326 * an iterator to walk over. The iterator should be new, with no
327 * parent, and should still be positioned before the first entry.
328 * @return position of this tree within the walker.
329 * @throws CorruptObjectException
330 * the iterator was unable to obtain its first entry, due to
331 * possible data corruption within the backing data store.
333 public int addTree(final AbstractTreeIterator p
)
334 throws CorruptObjectException
{
335 final int n
= trees
.length
;
336 final AbstractTreeIterator
[] newTrees
= new AbstractTreeIterator
[n
+ 1];
338 System
.arraycopy(trees
, 0, newTrees
, 0, n
);
347 * Get the number of trees known to this walker.
349 * @return the total number of trees this walker is iterating over.
351 public int getTreeCount() {
356 * Advance this walker to the next relevant entry.
358 * @return true if there is an entry available; false if all entries have
359 * been walked and the walk of this set of tree iterators is over.
360 * @throws MissingObjectException
361 * {@link #isRecursive()} was enabled, a subtree was found, but
362 * the subtree object does not exist in this repository. The
363 * repository may be missing objects.
364 * @throws IncorrectObjectTypeException
365 * {@link #isRecursive()} was enabled, a subtree was found, and
366 * the subtree id does not denote a tree, but instead names some
367 * other non-tree type of object. The repository may have data
369 * @throws CorruptObjectException
370 * the contents of a tree did not appear to be a tree. The
371 * repository may have data corruption.
372 * @throws IOException
373 * a loose object or pack file could not be read.
375 public boolean next() throws MissingObjectException
,
376 IncorrectObjectTypeException
, CorruptObjectException
, IOException
{
384 final AbstractTreeIterator t
= min();
394 if (!filter
.include(this)) {
399 if (recursive
&& FileMode
.TREE
.equals(t
.mode
)) {
407 } catch (StopWalkException stop
) {
408 for (final AbstractTreeIterator t
: trees
)
415 * Obtain the tree iterator for the current entry.
417 * Entering into (or exiting out of) a subtree causes the current tree
418 * iterator instance to be changed for the nth tree. This allows the tree
419 * iterators to manage only one list of items, with the diving handled by
423 * type of the tree iterator expected by the caller.
425 * tree to obtain the current iterator of.
427 * type of the tree iterator expected by the caller.
428 * @return r the current iterator of the requested type; null if the tree
429 * has no entry to match the current path.
431 public <T
extends AbstractTreeIterator
> T
getTree(final int nth
,
432 final Class
<T
> clazz
) {
433 final AbstractTreeIterator t
= trees
[nth
];
434 return t
.matches
== currentHead ?
(T
) t
: null;
438 * Obtain the raw {@link FileMode} bits for the current entry.
440 * Every added tree supplies mode bits, even if the tree does not contain
441 * the current entry. In the latter case {@link FileMode#MISSING}'s mode
442 * bits (0) are returned.
445 * tree to obtain the mode bits from.
446 * @return mode bits for the current entry of the nth tree.
447 * @see FileMode#fromBits(int)
449 public int getRawMode(final int nth
) {
450 final AbstractTreeIterator t
= trees
[nth
];
451 return t
.matches
== currentHead ? t
.mode
: 0;
455 * Obtain the {@link FileMode} for the current entry.
457 * Every added tree supplies a mode, even if the tree does not contain the
458 * current entry. In the latter case {@link FileMode#MISSING} is returned.
461 * tree to obtain the mode from.
462 * @return mode for the current entry of the nth tree.
464 public FileMode
getFileMode(final int nth
) {
465 return FileMode
.fromBits(getRawMode(nth
));
469 * Obtain the ObjectId for the current entry.
471 * Using this method to compare ObjectId values between trees of this walker
472 * is very inefficient. Applications should try to use
473 * {@link #idEqual(int, int)} whenever possible.
475 * Every tree supplies an object id, even if the tree does not contain the
476 * current entry. In the latter case {@link ObjectId#zeroId()} is returned.
479 * tree to obtain the object identifier from.
480 * @return object identifier for the current tree entry.
481 * @see #idEqual(int, int)
483 public ObjectId
getObjectId(final int nth
) {
484 final AbstractTreeIterator t
= trees
[nth
];
485 return t
.matches
== currentHead ? t
.getEntryObjectId() : ObjectId
490 * Compare two tree's current ObjectId values for equality.
493 * first tree to compare the object id from.
495 * second tree to compare the object id from.
497 * <code>getObjectId(nthA).equals(getObjectId(nthB))</code>.
498 * @see #getObjectId(int)
500 public boolean idEqual(final int nthA
, final int nthB
) {
501 final AbstractTreeIterator ch
= currentHead
;
502 final AbstractTreeIterator a
= trees
[nthA
];
503 final AbstractTreeIterator b
= trees
[nthB
];
504 return a
.matches
== ch
&& b
.matches
== ch
&& a
.idEqual(b
);
508 * Get the current entry's complete path.
510 * This method is not very efficient and is primarily meant for debugging
511 * and final output generation. Applications should try to avoid calling it,
512 * and if invoked do so only once per interesting entry, where the name is
513 * absolutely required for correct function.
515 * @return complete path of the current entry, from the root of the
516 * repository. If the current entry is in a subtree there will be at
517 * least one '/' in the returned string.
519 public String
getPathString() {
520 return pathOf(currentHead
);
524 * Test if the supplied path matches the current entry's path.
526 * This method tests that the supplied path is exactly equal to the current
527 * entry, or is one of its parent directories. It is faster to use this
528 * method then to use {@link #getPathString()} to first create a String
529 * object, then test <code>startsWith</code> or some other type of string
533 * path buffer to test. Callers should ensure the path does not
534 * end with '/' prior to invocation.
536 * number of bytes from <code>buf</code> to test.
537 * @return < 0 if p is before the current path; 0 if p matches the current
538 * path; 1 if the current path is past p and p will never match
539 * again on this tree walk.
541 public int isPathPrefix(final byte[] p
, final int pLen
) {
542 final AbstractTreeIterator t
= currentHead
;
543 final byte[] c
= t
.path
;
544 final int cLen
= t
.pathLen
;
547 for (ci
= 0; ci
< cLen
&& ci
< pLen
; ci
++) {
548 final int c_value
= (c
[ci
] & 0xff) - (p
[ci
] & 0xff);
554 // Ran out of pattern but we still had current data.
555 // If c[ci] == '/' then pattern matches the subtree.
556 // Otherwise we cannot be certain so we return -1.
558 return c
[ci
] == '/' ?
0 : -1;
562 // Ran out of current, but we still have pattern data.
563 // If p[ci] == '/' then pattern matches this subtree,
564 // otherwise we cannot be certain so we return -1.
566 return p
[ci
] == '/' ?
0 : -1;
569 // Both strings are identical.
575 * Is the current entry a subtree?
577 * This method is faster then testing the raw mode bits of all trees to see
578 * if any of them are a subtree. If at least one is a subtree then this
579 * method will return true.
581 * @return true if {@link #enterSubtree()} will work on the current node.
583 public boolean isSubtree() {
584 return FileMode
.TREE
.equals(currentHead
.mode
);
588 * Enter into the current subtree.
590 * If the current entry is a subtree this method arranges for its children
591 * to be returned before the next sibling following the subtree is returned.
593 * @throws MissingObjectException
594 * a subtree was found, but the subtree object does not exist in
595 * this repository. The repository may be missing objects.
596 * @throws IncorrectObjectTypeException
597 * a subtree was found, and the subtree id does not denote a
598 * tree, but instead names some other non-tree type of object.
599 * The repository may have data corruption.
600 * @throws CorruptObjectException
601 * the contents of a tree did not appear to be a tree. The
602 * repository may have data corruption.
603 * @throws IOException
604 * a loose object or pack file could not be read.
606 public void enterSubtree() throws MissingObjectException
,
607 IncorrectObjectTypeException
, CorruptObjectException
, IOException
{
608 final AbstractTreeIterator ch
= currentHead
;
609 final AbstractTreeIterator
[] tmp
= new AbstractTreeIterator
[trees
.length
];
610 for (int i
= 0; i
< trees
.length
; i
++) {
611 final AbstractTreeIterator t
= trees
[i
];
612 final AbstractTreeIterator n
;
613 if (t
.matches
== ch
&& !t
.eof() && FileMode
.TREE
.equals(t
.mode
))
614 n
= t
.createSubtreeIterator(db
);
616 n
= new EmptyTreeIterator(t
);
621 System
.arraycopy(tmp
, 0, trees
, 0, trees
.length
);
624 private AbstractTreeIterator
min() {
626 AbstractTreeIterator minRef
= trees
[i
];
627 while (minRef
.eof() && ++i
< trees
.length
)
632 minRef
.matches
= minRef
;
633 while (++i
< trees
.length
) {
634 final AbstractTreeIterator t
= trees
[i
];
637 final int cmp
= t
.pathCompare(minRef
);
641 } else if (cmp
== 0) {
649 private void popEntriesEqual() throws CorruptObjectException
{
650 final AbstractTreeIterator ch
= currentHead
;
651 for (int i
= 0; i
< trees
.length
; i
++) {
652 final AbstractTreeIterator t
= trees
[i
];
653 if (t
.matches
== ch
) {
660 private void skipEntriesEqual() throws CorruptObjectException
{
661 final AbstractTreeIterator ch
= currentHead
;
662 for (int i
= 0; i
< trees
.length
; i
++) {
663 final AbstractTreeIterator t
= trees
[i
];
664 if (t
.matches
== ch
) {
671 private void exitSubtree() throws CorruptObjectException
{
673 for (int i
= 0; i
< trees
.length
; i
++)
674 trees
[i
] = trees
[i
].parent
;
679 private CanonicalTreeParser
parserFor(final ObjectId id
)
680 throws IncorrectObjectTypeException
, IOException
{
681 final CanonicalTreeParser p
= new CanonicalTreeParser();
686 private static String
pathOf(final AbstractTreeIterator t
) {
687 return RawParseUtils
.decode(Constants
.CHARSET
, t
.path
, 0, t
.pathLen
);