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
.io
.UnsupportedEncodingException
;
42 import java
.util
.Collections
;
44 import org
.spearce
.jgit
.errors
.CorruptObjectException
;
45 import org
.spearce
.jgit
.errors
.IncorrectObjectTypeException
;
46 import org
.spearce
.jgit
.errors
.MissingObjectException
;
47 import org
.spearce
.jgit
.errors
.StopWalkException
;
48 import org
.spearce
.jgit
.lib
.Constants
;
49 import org
.spearce
.jgit
.lib
.FileMode
;
50 import org
.spearce
.jgit
.lib
.ObjectId
;
51 import org
.spearce
.jgit
.lib
.Repository
;
52 import org
.spearce
.jgit
.revwalk
.RevTree
;
53 import org
.spearce
.jgit
.treewalk
.filter
.PathFilterGroup
;
54 import org
.spearce
.jgit
.treewalk
.filter
.TreeFilter
;
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
]);
285 o
= parserFor(ids
[i
]);
296 * Add an already existing tree object for walking.
298 * The position of this tree is returned to the caller, in case the caller
299 * has lost track of the order they added the trees into the walker.
302 * identity of the tree object the caller wants walked.
303 * @return position of this tree within the walker.
304 * @throws MissingObjectException
305 * the given tree object does not exist in this repository.
306 * @throws IncorrectObjectTypeException
307 * the given object id does not denote a tree, but instead names
308 * some other non-tree type of object. Note that commits are not
309 * trees, even if they are sometimes called a "tree-ish".
310 * @throws CorruptObjectException
311 * the object claimed to be a tree, but its contents did not
312 * appear to be a tree. The repository may have data corruption.
313 * @throws IOException
314 * a loose object or pack file could not be read.
316 public int addTree(final ObjectId id
) throws MissingObjectException
,
317 IncorrectObjectTypeException
, CorruptObjectException
, IOException
{
318 return addTree(parserFor(id
));
322 * Add an already created tree iterator for walking.
324 * The position of this tree is returned to the caller, in case the caller
325 * has lost track of the order they added the trees into the walker.
328 * an iterator to walk over. The iterator should be new, with no
329 * parent, and should still be positioned before the first entry.
330 * @return position of this tree within the walker.
331 * @throws CorruptObjectException
332 * the iterator was unable to obtain its first entry, due to
333 * possible data corruption within the backing data store.
335 public int addTree(final AbstractTreeIterator p
)
336 throws CorruptObjectException
{
337 final int n
= trees
.length
;
338 final AbstractTreeIterator
[] newTrees
= new AbstractTreeIterator
[n
+ 1];
340 System
.arraycopy(trees
, 0, newTrees
, 0, n
);
350 * Get the number of trees known to this walker.
352 * @return the total number of trees this walker is iterating over.
354 public int getTreeCount() {
359 * Advance this walker to the next relevant entry.
361 * @return true if there is an entry available; false if all entries have
362 * been walked and the walk of this set of tree iterators is over.
363 * @throws MissingObjectException
364 * {@link #isRecursive()} was enabled, a subtree was found, but
365 * the subtree object does not exist in this repository. The
366 * repository may be missing objects.
367 * @throws IncorrectObjectTypeException
368 * {@link #isRecursive()} was enabled, a subtree was found, and
369 * the subtree id does not denote a tree, but instead names some
370 * other non-tree type of object. The repository may have data
372 * @throws CorruptObjectException
373 * the contents of a tree did not appear to be a tree. The
374 * repository may have data corruption.
375 * @throws IOException
376 * a loose object or pack file could not be read.
378 public boolean next() throws MissingObjectException
,
379 IncorrectObjectTypeException
, CorruptObjectException
, IOException
{
387 final AbstractTreeIterator t
= min();
397 if (!filter
.include(this)) {
402 if (recursive
&& FileMode
.TREE
.equals(t
.mode
)) {
410 } catch (StopWalkException stop
) {
416 * Obtain the raw {@link FileMode} bits for the current entry.
418 * Every added tree supplies mode bits, even if the tree does not contain
419 * the current entry. In the latter case {@link FileMode#MISSING}'s mode
420 * bits (0) are returned.
423 * tree to obtain the mode bits from.
424 * @return mode bits for the current entry of the nth tree.
425 * @see FileMode#fromBits(int)
427 public int getRawMode(final int nth
) {
428 final AbstractTreeIterator t
= trees
[nth
];
429 return t
.matches
== currentHead ? t
.mode
: 0;
433 * Obtain the {@link FileMode} for the current entry.
435 * Every added tree supplies a mode, even if the tree does not contain the
436 * current entry. In the latter case {@link FileMode#MISSING} is returned.
439 * tree to obtain the mode from.
440 * @return mode for the current entry of the nth tree.
442 public FileMode
getFileMode(final int nth
) {
443 return FileMode
.fromBits(getRawMode(nth
));
447 * Obtain the ObjectId for the current entry.
449 * Using this method to compare ObjectId values between trees of this walker
450 * is very inefficient. Applications should try to use
451 * {@link #idEqual(int, int)} whenever possible.
453 * Every tree supplies an object id, even if the tree does not contain the
454 * current entry. In the latter case {@link ObjectId#zeroId()} is returned.
457 * tree to obtain the object identifier from.
458 * @return object identifier for the current tree entry.
459 * @see #idEqual(int, int)
461 public ObjectId
getObjectId(final int nth
) {
462 final AbstractTreeIterator t
= trees
[nth
];
463 return t
.matches
== currentHead ? t
.getEntryObjectId() : ObjectId
468 * Compare two tree's current ObjectId values for equality.
471 * first tree to compare the object id from.
473 * second tree to compare the object id from.
475 * <code>getObjectId(nthA).equals(getObjectId(nthB))</code>.
476 * @see #getObjectId(int)
478 public boolean idEqual(final int nthA
, final int nthB
) {
479 final AbstractTreeIterator ch
= currentHead
;
480 final AbstractTreeIterator a
= trees
[nthA
];
481 final AbstractTreeIterator b
= trees
[nthB
];
482 return a
.matches
== ch
&& b
.matches
== ch
&& a
.idEqual(b
);
486 * Get the current entry's complete path.
488 * This method is not very efficient and is primarily meant for debugging
489 * and final output generation. Applications should try to avoid calling it,
490 * and if invoked do so only once per interesting entry, where the name is
491 * absolutely required for correct function.
493 * @return complete path of the current entry, from the root of the
494 * repository. If the current entry is in a subtree there will be at
495 * least one '/' in the returned string.
497 public String
getPathString() {
498 return pathOf(currentHead
);
502 * Test if the supplied path matches the current entry's path.
504 * This method tests that the supplied path is exactly equal to the current
505 * entry, or is one of its parent directories. It is faster to use this
506 * method then to use {@link #getPathString()} to first create a String
507 * object, then test <code>startsWith</code> or some other type of string
511 * path buffer to test. Callers should ensure the path does not
512 * end with '/' prior to invocation.
514 * number of bytes from <code>buf</code> to test.
515 * @return < 0 if p is before the current path; 0 if p matches the current
516 * path; 1 if the current path is past p and p will never match
517 * again on this tree walk.
519 public int isPathPrefix(final byte[] p
, final int pLen
) {
520 final AbstractTreeIterator t
= currentHead
;
521 final byte[] c
= t
.path
;
522 final int cLen
= t
.pathLen
;
525 for (ci
= 0; ci
< cLen
&& ci
< pLen
; ci
++) {
526 final int c_value
= (c
[ci
] & 0xff) - (p
[ci
] & 0xff);
532 // Ran out of pattern but we still had current data.
533 // If c[ci] == '/' then pattern matches the subtree.
534 // Otherwise we cannot be certain so we return -1.
536 return c
[ci
] == '/' ?
0 : -1;
540 // Ran out of current, but we still have pattern data.
541 // If p[ci] == '/' then pattern matches this subtree,
542 // otherwise we cannot be certain so we return -1.
544 return p
[ci
] == '/' ?
0 : -1;
547 // Both strings are identical.
553 * Is the current entry a subtree?
555 * This method is faster then testing the raw mode bits of all trees to see
556 * if any of them are a subtree. If at least one is a subtree then this
557 * method will return true.
559 * @return true if {@link #enterSubtree()} will work on the current node.
561 public boolean isSubtree() {
562 return FileMode
.TREE
.equals(currentHead
.mode
);
566 * Enter into the current subtree.
568 * If the current entry is a subtree this method arranges for its children
569 * to be returned before the next sibling following the subtree is returned.
571 * @throws MissingObjectException
572 * a subtree was found, but the subtree object does not exist in
573 * this repository. The repository may be missing objects.
574 * @throws IncorrectObjectTypeException
575 * a subtree was found, and the subtree id does not denote a
576 * tree, but instead names some other non-tree type of object.
577 * The repository may have data corruption.
578 * @throws CorruptObjectException
579 * the contents of a tree did not appear to be a tree. The
580 * repository may have data corruption.
581 * @throws IOException
582 * a loose object or pack file could not be read.
584 public void enterSubtree() throws MissingObjectException
,
585 IncorrectObjectTypeException
, CorruptObjectException
, IOException
{
586 final AbstractTreeIterator
[] tmp
= new AbstractTreeIterator
[trees
.length
];
587 for (int i
= 0; i
< trees
.length
; i
++) {
588 final AbstractTreeIterator t
= trees
[i
];
589 final AbstractTreeIterator n
;
590 if (!t
.eof() && FileMode
.TREE
.equals(t
.mode
))
591 n
= t
.createSubtreeIterator(db
);
593 n
= new EmptyTreeIterator(t
);
599 System
.arraycopy(tmp
, 0, trees
, 0, trees
.length
);
602 private AbstractTreeIterator
min() {
604 AbstractTreeIterator minRef
= trees
[i
];
605 while (minRef
.eof() && ++i
< trees
.length
)
610 minRef
.matches
= minRef
;
611 while (++i
< trees
.length
) {
612 final AbstractTreeIterator t
= trees
[i
];
615 final int cmp
= t
.pathCompare(minRef
);
619 } else if (cmp
== 0) {
627 private void popEntriesEqual() throws CorruptObjectException
{
628 final AbstractTreeIterator ch
= currentHead
;
629 for (int i
= 0; i
< trees
.length
; i
++) {
630 final AbstractTreeIterator t
= trees
[i
];
631 if (t
.matches
== ch
) {
638 private void skipEntriesEqual() throws CorruptObjectException
{
639 final AbstractTreeIterator ch
= currentHead
;
640 for (int i
= 0; i
< trees
.length
; i
++) {
641 final AbstractTreeIterator t
= trees
[i
];
642 if (t
.matches
== ch
) {
649 private void exitSubtree() throws CorruptObjectException
{
651 for (int i
= 0; i
< trees
.length
; i
++)
652 trees
[i
] = trees
[i
].parent
;
657 private CanonicalTreeParser
parserFor(final ObjectId id
)
658 throws IncorrectObjectTypeException
, IOException
{
659 final CanonicalTreeParser p
= new CanonicalTreeParser();
664 private static String
pathOf(final AbstractTreeIterator t
) {
666 return new String(t
.path
, 0, t
.pathLen
,
667 Constants
.CHARACTER_ENCODING
);
668 } catch (UnsupportedEncodingException uee
) {
669 throw new RuntimeException("JVM doesn't support "
670 + Constants
.CHARACTER_ENCODING
, uee
);