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
.treewalk
;
19 import java
.io
.IOException
;
20 import java
.io
.UnsupportedEncodingException
;
21 import java
.util
.Collections
;
23 import org
.spearce
.jgit
.errors
.CorruptObjectException
;
24 import org
.spearce
.jgit
.errors
.IncorrectObjectTypeException
;
25 import org
.spearce
.jgit
.errors
.MissingObjectException
;
26 import org
.spearce
.jgit
.errors
.StopWalkException
;
27 import org
.spearce
.jgit
.lib
.Constants
;
28 import org
.spearce
.jgit
.lib
.FileMode
;
29 import org
.spearce
.jgit
.lib
.ObjectId
;
30 import org
.spearce
.jgit
.lib
.Repository
;
31 import org
.spearce
.jgit
.revwalk
.RevTree
;
32 import org
.spearce
.jgit
.treewalk
.filter
.PathFilterGroup
;
33 import org
.spearce
.jgit
.treewalk
.filter
.TreeFilter
;
36 * Walks one or more {@link AbstractTreeIterator}s in parallel.
38 * This class can perform n-way differences across as many trees as necessary.
40 * A TreeWalk instance can only be used once to generate results. Running a
41 * second time requires creating a new TreeWalk instance, or invoking
42 * {@link #reset()} and adding new trees before starting again. Resetting an
43 * existing instance may be faster for some applications as some internal
44 * buffers may be recycled.
46 * TreeWalk instances are not thread-safe. Applications must either restrict
47 * usage of a TreeWalk instance to a single thread, or implement their own
48 * synchronization at a higher level.
50 * Multiple simultaneous TreeWalk instances per {@link Repository} are
51 * permitted, even from concurrent threads.
53 public class TreeWalk
{
55 * Open a tree walk and filter to exactly one path.
57 * The returned tree walk is already positioned on the requested path, so
58 * the caller should not need to invoke {@link #next()} unless they are
59 * looking for a possible directory/file name conflict.
62 * repository to read tree object data from.
64 * single path to advance the tree walk instance into.
66 * one or more trees to walk through.
67 * @return a new tree walk configured for exactly this one path; null if no
68 * path was found in any of the trees.
70 * reading a pack file or loose object failed.
71 * @throws CorruptObjectException
72 * an tree object could not be read as its data stream did not
73 * appear to be a tree, or could not be inflated.
74 * @throws IncorrectObjectTypeException
75 * an object we expected to be a tree was not a tree.
76 * @throws MissingObjectException
77 * a tree object was not found.
79 public static TreeWalk
forPath(final Repository db
, final String path
,
80 final ObjectId
[] trees
) throws MissingObjectException
,
81 IncorrectObjectTypeException
, CorruptObjectException
, IOException
{
82 final TreeWalk r
= new TreeWalk(db
);
83 r
.setFilter(PathFilterGroup
.createFromStrings(Collections
85 r
.setRecursive(r
.getFilter().shouldBeRecursive());
87 return r
.next() ? r
: null;
91 * Open a tree walk and filter to exactly one path.
93 * The returned tree walk is already positioned on the requested path, so
94 * the caller should not need to invoke {@link #next()} unless they are
95 * looking for a possible directory/file name conflict.
98 * repository to read tree object data from.
100 * single path to advance the tree walk instance into.
102 * the single tree to walk through.
103 * @return a new tree walk configured for exactly this one path; null if no
104 * path was found in any of the trees.
105 * @throws IOException
106 * reading a pack file or loose object failed.
107 * @throws CorruptObjectException
108 * an tree object could not be read as its data stream did not
109 * appear to be a tree, or could not be inflated.
110 * @throws IncorrectObjectTypeException
111 * an object we expected to be a tree was not a tree.
112 * @throws MissingObjectException
113 * a tree object was not found.
115 public static TreeWalk
forPath(final Repository db
, final String path
,
116 final RevTree tree
) throws MissingObjectException
,
117 IncorrectObjectTypeException
, CorruptObjectException
, IOException
{
118 return forPath(db
, path
, new ObjectId
[] { tree
});
121 private final Repository db
;
123 private TreeFilter filter
;
125 private AbstractTreeIterator
[] trees
;
127 private boolean recursive
;
131 private boolean advance
;
133 private AbstractTreeIterator currentHead
;
136 * Create a new tree walker for a given repository.
139 * the repository the walker will obtain data from.
141 public TreeWalk(final Repository repo
) {
143 filter
= TreeFilter
.ALL
;
144 trees
= new AbstractTreeIterator
[] { new EmptyTreeIterator() };
148 * Get the repository this tree walker is reading from.
150 * @return the repository configured when the walker was created.
152 public Repository
getRepository() {
157 * Get the currently configured filter.
159 * @return the current filter. Never null as a filter is always needed.
161 public TreeFilter
getFilter() {
166 * Set the tree entry filter for this walker.
168 * Multiple filters may be combined by constructing an arbitrary tree of
169 * <code>AndTreeFilter</code> or <code>OrTreeFilter</code> instances to
170 * describe the boolean expression required by the application. Custom
171 * filter implementations may also be constructed by applications.
173 * Note that filters are not thread-safe and may not be shared by concurrent
174 * TreeWalk instances. Every TreeWalk must be supplied its own unique
175 * filter, unless the filter implementation specifically states it is (and
176 * always will be) thread-safe. Callers may use {@link TreeFilter#clone()}
177 * to create a unique filter tree for this TreeWalk instance.
180 * the new filter. If null the special {@link TreeFilter#ALL}
181 * filter will be used instead, as it matches every entry.
182 * @see org.spearce.jgit.treewalk.filter.AndTreeFilter
183 * @see org.spearce.jgit.treewalk.filter.OrTreeFilter
185 public void setFilter(final TreeFilter newFilter
) {
186 filter
= newFilter
!= null ? newFilter
: TreeFilter
.ALL
;
190 * Is this walker automatically entering into subtrees?
192 * If the walker is recursive then the caller will not see a subtree node
193 * and instead will only receive file nodes in all relevant subtrees.
195 * @return true if automatically entering subtrees is enabled.
197 public boolean isRecursive() {
202 * Set the walker to enter (or not enter) subtrees automatically.
204 * If recursive mode is enabled the walker will hide subtree nodes from the
205 * calling application and will produce only file level nodes. If a tree
206 * (directory) is deleted then all of the file level nodes will appear to be
207 * deleted, recursively, through as many levels as necessary to account for
211 * true to skip subtree nodes and only obtain files nodes.
213 public void setRecursive(final boolean b
) {
217 /** Reset this walker so new tree iterators can be added to it. */
218 public void reset() {
219 trees
= new AbstractTreeIterator
[0];
225 * Reset this walker to run over a set of existing trees.
228 * the trees we need to parse. The walker will execute over this
229 * many parallel trees if the reset is successful.
230 * @throws MissingObjectException
231 * the given tree object does not exist in this repository.
232 * @throws IncorrectObjectTypeException
233 * the given object id does not denote a tree, but instead names
234 * some other non-tree type of object. Note that commits are not
235 * trees, even if they are sometimes called a "tree-ish".
236 * @throws CorruptObjectException
237 * the object claimed to be a tree, but its contents did not
238 * appear to be a tree. The repository may have data corruption.
239 * @throws IOException
240 * a loose object or pack file could not be read.
242 public void reset(final ObjectId
[] ids
) throws MissingObjectException
,
243 IncorrectObjectTypeException
, CorruptObjectException
, IOException
{
244 final int oldLen
= trees
.length
;
245 final int newLen
= ids
.length
;
246 final AbstractTreeIterator
[] r
= newLen
== oldLen ? trees
247 : new AbstractTreeIterator
[newLen
];
248 for (int i
= 0; i
< newLen
; i
++) {
249 AbstractTreeIterator o
;
253 while (o
.parent
!= null)
255 if (o
instanceof CanonicalTreeParser
) {
257 ((CanonicalTreeParser
) o
).reset(db
, ids
[i
]);
264 o
= parserFor(ids
[i
]);
275 * Add an already existing tree object for walking.
277 * The position of this tree is returned to the caller, in case the caller
278 * has lost track of the order they added the trees into the walker.
281 * identity of the tree object the caller wants walked.
282 * @return position of this tree within the walker.
283 * @throws MissingObjectException
284 * the given tree object does not exist in this repository.
285 * @throws IncorrectObjectTypeException
286 * the given object id does not denote a tree, but instead names
287 * some other non-tree type of object. Note that commits are not
288 * trees, even if they are sometimes called a "tree-ish".
289 * @throws CorruptObjectException
290 * the object claimed to be a tree, but its contents did not
291 * appear to be a tree. The repository may have data corruption.
292 * @throws IOException
293 * a loose object or pack file could not be read.
295 public int addTree(final ObjectId id
) throws MissingObjectException
,
296 IncorrectObjectTypeException
, CorruptObjectException
, IOException
{
297 return addTree(parserFor(id
));
301 * Add an already created tree iterator for walking.
303 * The position of this tree is returned to the caller, in case the caller
304 * has lost track of the order they added the trees into the walker.
307 * an iterator to walk over. The iterator should be new, with no
308 * parent, and should still be positioned before the first entry.
309 * @return position of this tree within the walker.
310 * @throws CorruptObjectException
311 * the iterator was unable to obtain its first entry, due to
312 * possible data corruption within the backing data store.
314 public int addTree(final AbstractTreeIterator p
)
315 throws CorruptObjectException
{
316 final int n
= trees
.length
;
317 final AbstractTreeIterator
[] newTrees
= new AbstractTreeIterator
[n
+ 1];
319 System
.arraycopy(trees
, 0, newTrees
, 0, n
);
329 * Get the number of trees known to this walker.
331 * @return the total number of trees this walker is iterating over.
333 public int getTreeCount() {
338 * Advance this walker to the next relevant entry.
340 * @return true if there is an entry available; false if all entries have
341 * been walked and the walk of this set of tree iterators is over.
342 * @throws MissingObjectException
343 * {@link #isRecursive()} was enabled, a subtree was found, but
344 * the subtree object does not exist in this repository. The
345 * repository may be missing objects.
346 * @throws IncorrectObjectTypeException
347 * {@link #isRecursive()} was enabled, a subtree was found, and
348 * the subtree id does not denote a tree, but instead names some
349 * other non-tree type of object. The repository may have data
351 * @throws CorruptObjectException
352 * the contents of a tree did not appear to be a tree. The
353 * repository may have data corruption.
354 * @throws IOException
355 * a loose object or pack file could not be read.
357 public boolean next() throws MissingObjectException
,
358 IncorrectObjectTypeException
, CorruptObjectException
, IOException
{
366 final AbstractTreeIterator t
= min();
376 if (!filter
.include(this)) {
381 if (recursive
&& FileMode
.TREE
.equals(t
.mode
)) {
389 } catch (StopWalkException stop
) {
395 * Obtain the raw {@link FileMode} bits for the current entry.
397 * Every added tree supplies mode bits, even if the tree does not contain
398 * the current entry. In the latter case {@link FileMode#MISSING}'s mode
399 * bits (0) are returned.
402 * tree to obtain the mode bits from.
403 * @return mode bits for the current entry of the nth tree.
404 * @see FileMode#fromBits(int)
406 public int getRawMode(final int nth
) {
407 final AbstractTreeIterator t
= trees
[nth
];
408 return t
.matches
== currentHead ? t
.mode
: 0;
412 * Obtain the {@link FileMode} for the current entry.
414 * Every added tree supplies a mode, even if the tree does not contain the
415 * current entry. In the latter case {@link FileMode#MISSING} is returned.
418 * tree to obtain the mode from.
419 * @return mode for the current entry of the nth tree.
421 public FileMode
getFileMode(final int nth
) {
422 return FileMode
.fromBits(getRawMode(nth
));
426 * Obtain the ObjectId for the current entry.
428 * Using this method to compare ObjectId values between trees of this walker
429 * is very inefficient. Applications should try to use
430 * {@link #idEqual(int, int)} whenever possible.
432 * Every tree supplies an object id, even if the tree does not contain the
433 * current entry. In the latter case {@link ObjectId#zeroId()} is returned.
436 * tree to obtain the object identifier from.
437 * @return object identifier for the current tree entry.
438 * @see #idEqual(int, int)
440 public ObjectId
getObjectId(final int nth
) {
441 final AbstractTreeIterator t
= trees
[nth
];
442 return t
.matches
== currentHead ? t
.getEntryObjectId() : ObjectId
447 * Compare two tree's current ObjectId values for equality.
450 * first tree to compare the object id from.
452 * second tree to compare the object id from.
454 * <code>getObjectId(nthA).equals(getObjectId(nthB))</code>.
455 * @see #getObjectId(int)
457 public boolean idEqual(final int nthA
, final int nthB
) {
458 final AbstractTreeIterator ch
= currentHead
;
459 final AbstractTreeIterator a
= trees
[nthA
];
460 final AbstractTreeIterator b
= trees
[nthB
];
461 return a
.matches
== ch
&& b
.matches
== ch
&& a
.idEqual(b
);
465 * Get the current entry's complete path.
467 * This method is not very efficient and is primarily meant for debugging
468 * and final output generation. Applications should try to avoid calling it,
469 * and if invoked do so only once per interesting entry, where the name is
470 * absolutely required for correct function.
472 * @return complete path of the current entry, from the root of the
473 * repository. If the current entry is in a subtree there will be at
474 * least one '/' in the returned string.
476 public String
getPathString() {
477 return pathOf(currentHead
);
481 * Test if the supplied path matches the current entry's path.
483 * This method tests that the supplied path is exactly equal to the current
484 * entry, or is one of its parent directories. It is faster to use this
485 * method then to use {@link #getPathString()} to first create a String
486 * object, then test <code>startsWith</code> or some other type of string
490 * path buffer to test. Callers should ensure the path does not
491 * end with '/' prior to invocation.
493 * number of bytes from <code>buf</code> to test.
494 * @return < 0 if p is before the current path; 0 if p matches the current
495 * path; 1 if the current path is past p and p will never match
496 * again on this tree walk.
498 public int isPathPrefix(final byte[] p
, final int pLen
) {
499 final AbstractTreeIterator t
= currentHead
;
500 final byte[] c
= t
.path
;
501 final int cLen
= t
.pathLen
;
504 for (ci
= 0; ci
< cLen
&& ci
< pLen
; ci
++) {
505 final int c_value
= (c
[ci
] & 0xff) - (p
[ci
] & 0xff);
511 // Ran out of pattern but we still had current data.
512 // If c[ci] == '/' then pattern matches the subtree.
513 // Otherwise we cannot be certain so we return -1.
515 return c
[ci
] == '/' ?
0 : -1;
519 // Ran out of current, but we still have pattern data.
520 // If p[ci] == '/' then pattern matches this subtree,
521 // otherwise we cannot be certain so we return -1.
523 return p
[ci
] == '/' ?
0 : -1;
526 // Both strings are identical.
532 * Is the current entry a subtree?
534 * This method is faster then testing the raw mode bits of all trees to see
535 * if any of them are a subtree. If at least one is a subtree then this
536 * method will return true.
538 * @return true if {@link #enterSubtree()} will work on the current node.
540 public boolean isSubtree() {
541 return FileMode
.TREE
.equals(currentHead
.mode
);
545 * Enter into the current subtree.
547 * If the current entry is a subtree this method arranges for its children
548 * to be returned before the next sibling following the subtree is returned.
550 * @throws MissingObjectException
551 * a subtree was found, but the subtree object does not exist in
552 * this repository. The repository may be missing objects.
553 * @throws IncorrectObjectTypeException
554 * a subtree was found, and the subtree id does not denote a
555 * tree, but instead names some other non-tree type of object.
556 * The repository may have data corruption.
557 * @throws CorruptObjectException
558 * the contents of a tree did not appear to be a tree. The
559 * repository may have data corruption.
560 * @throws IOException
561 * a loose object or pack file could not be read.
563 public void enterSubtree() throws MissingObjectException
,
564 IncorrectObjectTypeException
, CorruptObjectException
, IOException
{
565 final AbstractTreeIterator
[] tmp
= new AbstractTreeIterator
[trees
.length
];
566 for (int i
= 0; i
< trees
.length
; i
++) {
567 final AbstractTreeIterator t
= trees
[i
];
568 final AbstractTreeIterator n
;
569 if (!t
.eof() && FileMode
.TREE
.equals(t
.mode
))
570 n
= t
.createSubtreeIterator(db
);
572 n
= new EmptyTreeIterator(t
);
578 System
.arraycopy(tmp
, 0, trees
, 0, trees
.length
);
581 private AbstractTreeIterator
min() {
583 AbstractTreeIterator minRef
= trees
[i
];
584 while (minRef
.eof() && ++i
< trees
.length
)
589 minRef
.matches
= minRef
;
590 while (++i
< trees
.length
) {
591 final AbstractTreeIterator t
= trees
[i
];
594 final int cmp
= t
.pathCompare(minRef
);
598 } else if (cmp
== 0) {
606 private void popEntriesEqual() throws CorruptObjectException
{
607 final AbstractTreeIterator ch
= currentHead
;
608 for (int i
= 0; i
< trees
.length
; i
++) {
609 final AbstractTreeIterator t
= trees
[i
];
610 if (t
.matches
== ch
) {
617 private void exitSubtree() throws CorruptObjectException
{
619 for (int i
= 0; i
< trees
.length
; i
++)
620 trees
[i
] = trees
[i
].parent
;
625 private CanonicalTreeParser
parserFor(final ObjectId id
)
626 throws IncorrectObjectTypeException
, IOException
{
627 final CanonicalTreeParser p
= new CanonicalTreeParser();
632 private static String
pathOf(final AbstractTreeIterator t
) {
634 return new String(t
.path
, 0, t
.pathLen
,
635 Constants
.CHARACTER_ENCODING
);
636 } catch (UnsupportedEncodingException uee
) {
637 throw new RuntimeException("JVM doesn't support "
638 + Constants
.CHARACTER_ENCODING
, uee
);