1 /* 2 * Copyright (C) 2008-2009, Google Inc. 3 * Copyright (C) 2008, Shawn O. Pearce <spearce@spearce.org> 4 * and other copyright owners as documented in the project's IP log. 5 * 6 * This program and the accompanying materials are made available 7 * under the terms of the Eclipse Distribution License v1.0 which 8 * accompanies this distribution, is reproduced below, and is 9 * available at http://www.eclipse.org/org/documents/edl-v10.php 10 * 11 * All rights reserved. 12 * 13 * Redistribution and use in source and binary forms, with or 14 * without modification, are permitted provided that the following 15 * conditions are met: 16 * 17 * - Redistributions of source code must retain the above copyright 18 * notice, this list of conditions and the following disclaimer. 19 * 20 * - Redistributions in binary form must reproduce the above 21 * copyright notice, this list of conditions and the following 22 * disclaimer in the documentation and/or other materials provided 23 * with the distribution. 24 * 25 * - Neither the name of the Eclipse Foundation, Inc. nor the 26 * names of its contributors may be used to endorse or promote 27 * products derived from this software without specific prior 28 * written permission. 29 * 30 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND 31 * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, 32 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 33 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 34 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR 35 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 36 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 37 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 38 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 39 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 40 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 41 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF 42 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 43 */ 44 45 package org.eclipse.jgit.treewalk; 46 47 import java.io.IOException; 48 49 import org.eclipse.jgit.errors.CorruptObjectException; 50 import org.eclipse.jgit.errors.IncorrectObjectTypeException; 51 import org.eclipse.jgit.errors.MissingObjectException; 52 import org.eclipse.jgit.errors.StopWalkException; 53 import org.eclipse.jgit.lib.AnyObjectId; 54 import org.eclipse.jgit.lib.Constants; 55 import org.eclipse.jgit.lib.FileMode; 56 import org.eclipse.jgit.lib.MutableObjectId; 57 import org.eclipse.jgit.lib.ObjectId; 58 import org.eclipse.jgit.lib.ObjectReader; 59 import org.eclipse.jgit.lib.Repository; 60 import org.eclipse.jgit.revwalk.RevTree; 61 import org.eclipse.jgit.treewalk.filter.PathFilter; 62 import org.eclipse.jgit.treewalk.filter.TreeFilter; 63 import org.eclipse.jgit.util.RawParseUtils; 64 65 /** 66 * Walks one or more {@link AbstractTreeIterator}s in parallel. 67 * <p> 68 * This class can perform n-way differences across as many trees as necessary. 69 * <p> 70 * Each tree added must have the same root as existing trees in the walk. 71 * <p> 72 * A TreeWalk instance can only be used once to generate results. Running a 73 * second time requires creating a new TreeWalk instance, or invoking 74 * {@link #reset()} and adding new trees before starting again. Resetting an 75 * existing instance may be faster for some applications as some internal 76 * buffers may be recycled. 77 * <p> 78 * TreeWalk instances are not thread-safe. Applications must either restrict 79 * usage of a TreeWalk instance to a single thread, or implement their own 80 * synchronization at a higher level. 81 * <p> 82 * Multiple simultaneous TreeWalk instances per {@link Repository} are 83 * permitted, even from concurrent threads. 84 */ 85 public class TreeWalk implements AutoCloseable { 86 private static final AbstractTreeIterator[] NO_TREES = {}; 87 88 /** 89 * Open a tree walk and filter to exactly one path. 90 * <p> 91 * The returned tree walk is already positioned on the requested path, so 92 * the caller should not need to invoke {@link #next()} unless they are 93 * looking for a possible directory/file name conflict. 94 * 95 * @param reader 96 * the reader the walker will obtain tree data from. 97 * @param path 98 * single path to advance the tree walk instance into. 99 * @param trees 100 * one or more trees to walk through, all with the same root. 101 * @return a new tree walk configured for exactly this one path; null if no 102 * path was found in any of the trees. 103 * @throws IOException 104 * reading a pack file or loose object failed. 105 * @throws CorruptObjectException 106 * an tree object could not be read as its data stream did not 107 * appear to be a tree, or could not be inflated. 108 * @throws IncorrectObjectTypeException 109 * an object we expected to be a tree was not a tree. 110 * @throws MissingObjectException 111 * a tree object was not found. 112 */ 113 public static TreeWalk forPath(final ObjectReader reader, final String path, 114 final AnyObjectId... trees) throws MissingObjectException, 115 IncorrectObjectTypeException, CorruptObjectException, IOException { 116 TreeWalk tw = new TreeWalk(reader); 117 PathFilter f = PathFilter.create(path); 118 tw.setFilter(f); 119 tw.reset(trees); 120 tw.setRecursive(false); 121 122 while (tw.next()) { 123 if (f.isDone(tw)) { 124 return tw; 125 } else if (tw.isSubtree()) { 126 tw.enterSubtree(); 127 } 128 } 129 return null; 130 } 131 132 /** 133 * Open a tree walk and filter to exactly one path. 134 * <p> 135 * The returned tree walk is already positioned on the requested path, so 136 * the caller should not need to invoke {@link #next()} unless they are 137 * looking for a possible directory/file name conflict. 138 * 139 * @param db 140 * repository to read tree object data from. 141 * @param path 142 * single path to advance the tree walk instance into. 143 * @param trees 144 * one or more trees to walk through, all with the same root. 145 * @return a new tree walk configured for exactly this one path; null if no 146 * path was found in any of the trees. 147 * @throws IOException 148 * reading a pack file or loose object failed. 149 * @throws CorruptObjectException 150 * an tree object could not be read as its data stream did not 151 * appear to be a tree, or could not be inflated. 152 * @throws IncorrectObjectTypeException 153 * an object we expected to be a tree was not a tree. 154 * @throws MissingObjectException 155 * a tree object was not found. 156 */ 157 public static TreeWalk forPath(final Repository db, final String path, 158 final AnyObjectId... trees) throws MissingObjectException, 159 IncorrectObjectTypeException, CorruptObjectException, IOException { 160 try (ObjectReader reader = db.newObjectReader()) { 161 return forPath(reader, path, trees); 162 } 163 } 164 165 /** 166 * Open a tree walk and filter to exactly one path. 167 * <p> 168 * The returned tree walk is already positioned on the requested path, so 169 * the caller should not need to invoke {@link #next()} unless they are 170 * looking for a possible directory/file name conflict. 171 * 172 * @param db 173 * repository to read tree object data from. 174 * @param path 175 * single path to advance the tree walk instance into. 176 * @param tree 177 * the single tree to walk through. 178 * @return a new tree walk configured for exactly this one path; null if no 179 * path was found in any of the trees. 180 * @throws IOException 181 * reading a pack file or loose object failed. 182 * @throws CorruptObjectException 183 * an tree object could not be read as its data stream did not 184 * appear to be a tree, or could not be inflated. 185 * @throws IncorrectObjectTypeException 186 * an object we expected to be a tree was not a tree. 187 * @throws MissingObjectException 188 * a tree object was not found. 189 */ 190 public static TreeWalk forPath(final Repository db, final String path, 191 final RevTree tree) throws MissingObjectException, 192 IncorrectObjectTypeException, CorruptObjectException, IOException { 193 return forPath(db, path, new ObjectId[] { tree }); 194 } 195 196 private final ObjectReader reader; 197 198 private final boolean closeReader; 199 200 private final MutableObjectId idBuffer = new MutableObjectId(); 201 202 private TreeFilter filter; 203 204 AbstractTreeIterator[] trees; 205 206 private boolean recursive; 207 208 private boolean postOrderTraversal; 209 210 private int depth; 211 212 private boolean advance; 213 214 private boolean postChildren; 215 216 AbstractTreeIterator currentHead; 217 218 /** 219 * Create a new tree walker for a given repository. 220 * 221 * @param repo 222 * the repository the walker will obtain data from. An 223 * ObjectReader will be created by the walker, and will be closed 224 * when the walker is closed. 225 */ 226 public TreeWalk(final Repository repo) { 227 this(repo.newObjectReader(), true); 228 } 229 230 /** 231 * Create a new tree walker for a given repository. 232 * 233 * @param or 234 * the reader the walker will obtain tree data from. The reader 235 * is not closed when the walker is closed. 236 */ 237 public TreeWalk(final ObjectReader or) { 238 this(or, false); 239 } 240 241 private TreeWalk(final ObjectReader or, final boolean closeReader) { 242 reader = or; 243 filter = TreeFilter.ALL; 244 trees = NO_TREES; 245 this.closeReader = closeReader; 246 } 247 248 /** @return the reader this walker is using to load objects. */ 249 public ObjectReader getObjectReader() { 250 return reader; 251 } 252 253 /** 254 * Release any resources used by this walker's reader. 255 * <p> 256 * A walker that has been released can be used again, but may need to be 257 * released after the subsequent usage. 258 * 259 * @since 4.0 260 */ 261 @Override 262 public void close() { 263 if (closeReader) { 264 reader.close(); 265 } 266 } 267 268 /** 269 * Get the currently configured filter. 270 * 271 * @return the current filter. Never null as a filter is always needed. 272 */ 273 public TreeFilter getFilter() { 274 return filter; 275 } 276 277 /** 278 * Set the tree entry filter for this walker. 279 * <p> 280 * Multiple filters may be combined by constructing an arbitrary tree of 281 * <code>AndTreeFilter</code> or <code>OrTreeFilter</code> instances to 282 * describe the boolean expression required by the application. Custom 283 * filter implementations may also be constructed by applications. 284 * <p> 285 * Note that filters are not thread-safe and may not be shared by concurrent 286 * TreeWalk instances. Every TreeWalk must be supplied its own unique 287 * filter, unless the filter implementation specifically states it is (and 288 * always will be) thread-safe. Callers may use {@link TreeFilter#clone()} 289 * to create a unique filter tree for this TreeWalk instance. 290 * 291 * @param newFilter 292 * the new filter. If null the special {@link TreeFilter#ALL} 293 * filter will be used instead, as it matches every entry. 294 * @see org.eclipse.jgit.treewalk.filter.AndTreeFilter 295 * @see org.eclipse.jgit.treewalk.filter.OrTreeFilter 296 */ 297 public void setFilter(final TreeFilter newFilter) { 298 filter = newFilter != null ? newFilter : TreeFilter.ALL; 299 } 300 301 /** 302 * Is this walker automatically entering into subtrees? 303 * <p> 304 * If the walker is recursive then the caller will not see a subtree node 305 * and instead will only receive file nodes in all relevant subtrees. 306 * 307 * @return true if automatically entering subtrees is enabled. 308 */ 309 public boolean isRecursive() { 310 return recursive; 311 } 312 313 /** 314 * Set the walker to enter (or not enter) subtrees automatically. 315 * <p> 316 * If recursive mode is enabled the walker will hide subtree nodes from the 317 * calling application and will produce only file level nodes. If a tree 318 * (directory) is deleted then all of the file level nodes will appear to be 319 * deleted, recursively, through as many levels as necessary to account for 320 * all entries. 321 * 322 * @param b 323 * true to skip subtree nodes and only obtain files nodes. 324 */ 325 public void setRecursive(final boolean b) { 326 recursive = b; 327 } 328 329 /** 330 * Does this walker return a tree entry after it exits the subtree? 331 * <p> 332 * If post order traversal is enabled then the walker will return a subtree 333 * after it has returned the last entry within that subtree. This may cause 334 * a subtree to be seen by the application twice if {@link #isRecursive()} 335 * is false, as the application will see it once, call 336 * {@link #enterSubtree()}, and then see it again as it leaves the subtree. 337 * <p> 338 * If an application does not enable {@link #isRecursive()} and it does not 339 * call {@link #enterSubtree()} then the tree is returned only once as none 340 * of the children were processed. 341 * 342 * @return true if subtrees are returned after entries within the subtree. 343 */ 344 public boolean isPostOrderTraversal() { 345 return postOrderTraversal; 346 } 347 348 /** 349 * Set the walker to return trees after their children. 350 * 351 * @param b 352 * true to get trees after their children. 353 * @see #isPostOrderTraversal() 354 */ 355 public void setPostOrderTraversal(final boolean b) { 356 postOrderTraversal = b; 357 } 358 359 /** Reset this walker so new tree iterators can be added to it. */ 360 public void reset() { 361 trees = NO_TREES; 362 advance = false; 363 depth = 0; 364 } 365 366 /** 367 * Reset this walker to run over a single existing tree. 368 * 369 * @param id 370 * the tree we need to parse. The walker will execute over this 371 * single tree if the reset is successful. 372 * @throws MissingObjectException 373 * the given tree object does not exist in this repository. 374 * @throws IncorrectObjectTypeException 375 * the given object id does not denote a tree, but instead names 376 * some other non-tree type of object. Note that commits are not 377 * trees, even if they are sometimes called a "tree-ish". 378 * @throws CorruptObjectException 379 * the object claimed to be a tree, but its contents did not 380 * appear to be a tree. The repository may have data corruption. 381 * @throws IOException 382 * a loose object or pack file could not be read. 383 */ 384 public void reset(final AnyObjectId id) throws MissingObjectException, 385 IncorrectObjectTypeException, CorruptObjectException, IOException { 386 if (trees.length == 1) { 387 AbstractTreeIterator o = trees[0]; 388 while (o.parent != null) 389 o = o.parent; 390 if (o instanceof CanonicalTreeParser) { 391 o.matches = null; 392 o.matchShift = 0; 393 ((CanonicalTreeParser) o).reset(reader, id); 394 trees[0] = o; 395 } else { 396 trees[0] = parserFor(id); 397 } 398 } else { 399 trees = new AbstractTreeIterator[] { parserFor(id) }; 400 } 401 402 advance = false; 403 depth = 0; 404 } 405 406 /** 407 * Reset this walker to run over a set of existing trees. 408 * 409 * @param ids 410 * the trees we need to parse. The walker will execute over this 411 * many parallel trees if the reset is successful. 412 * @throws MissingObjectException 413 * the given tree object does not exist in this repository. 414 * @throws IncorrectObjectTypeException 415 * the given object id does not denote a tree, but instead names 416 * some other non-tree type of object. Note that commits are not 417 * trees, even if they are sometimes called a "tree-ish". 418 * @throws CorruptObjectException 419 * the object claimed to be a tree, but its contents did not 420 * appear to be a tree. The repository may have data corruption. 421 * @throws IOException 422 * a loose object or pack file could not be read. 423 */ 424 public void reset(final AnyObjectId... ids) throws MissingObjectException, 425 IncorrectObjectTypeException, CorruptObjectException, IOException { 426 final int oldLen = trees.length; 427 final int newLen = ids.length; 428 final AbstractTreeIterator[] r = newLen == oldLen ? trees 429 : new AbstractTreeIterator[newLen]; 430 for (int i = 0; i < newLen; i++) { 431 AbstractTreeIterator o; 432 433 if (i < oldLen) { 434 o = trees[i]; 435 while (o.parent != null) 436 o = o.parent; 437 if (o instanceof CanonicalTreeParser && o.pathOffset == 0) { 438 o.matches = null; 439 o.matchShift = 0; 440 ((CanonicalTreeParser) o).reset(reader, ids[i]); 441 r[i] = o; 442 continue; 443 } 444 } 445 446 o = parserFor(ids[i]); 447 r[i] = o; 448 } 449 450 trees = r; 451 advance = false; 452 depth = 0; 453 } 454 455 /** 456 * Add an already existing tree object for walking. 457 * <p> 458 * The position of this tree is returned to the caller, in case the caller 459 * has lost track of the order they added the trees into the walker. 460 * <p> 461 * The tree must have the same root as existing trees in the walk. 462 * 463 * @param id 464 * identity of the tree object the caller wants walked. 465 * @return position of this tree within the walker. 466 * @throws MissingObjectException 467 * the given tree object does not exist in this repository. 468 * @throws IncorrectObjectTypeException 469 * the given object id does not denote a tree, but instead names 470 * some other non-tree type of object. Note that commits are not 471 * trees, even if they are sometimes called a "tree-ish". 472 * @throws CorruptObjectException 473 * the object claimed to be a tree, but its contents did not 474 * appear to be a tree. The repository may have data corruption. 475 * @throws IOException 476 * a loose object or pack file could not be read. 477 */ 478 public int addTree(final AnyObjectId id) throws MissingObjectException, 479 IncorrectObjectTypeException, CorruptObjectException, IOException { 480 return addTree(parserFor(id)); 481 } 482 483 /** 484 * Add an already created tree iterator for walking. 485 * <p> 486 * The position of this tree is returned to the caller, in case the caller 487 * has lost track of the order they added the trees into the walker. 488 * <p> 489 * The tree which the iterator operates on must have the same root as 490 * existing trees in the walk. 491 * 492 * @param p 493 * an iterator to walk over. The iterator should be new, with no 494 * parent, and should still be positioned before the first entry. 495 * The tree which the iterator operates on must have the same root 496 * as other trees in the walk. 497 * 498 * @return position of this tree within the walker. 499 * @throws CorruptObjectException 500 * the iterator was unable to obtain its first entry, due to 501 * possible data corruption within the backing data store. 502 */ 503 public int addTree(final AbstractTreeIterator p) 504 throws CorruptObjectException { 505 final int n = trees.length; 506 final AbstractTreeIterator[] newTrees = new AbstractTreeIterator[n + 1]; 507 508 System.arraycopy(trees, 0, newTrees, 0, n); 509 newTrees[n] = p; 510 p.matches = null; 511 p.matchShift = 0; 512 513 trees = newTrees; 514 return n; 515 } 516 517 /** 518 * Get the number of trees known to this walker. 519 * 520 * @return the total number of trees this walker is iterating over. 521 */ 522 public int getTreeCount() { 523 return trees.length; 524 } 525 526 /** 527 * Advance this walker to the next relevant entry. 528 * 529 * @return true if there is an entry available; false if all entries have 530 * been walked and the walk of this set of tree iterators is over. 531 * @throws MissingObjectException 532 * {@link #isRecursive()} was enabled, a subtree was found, but 533 * the subtree object does not exist in this repository. The 534 * repository may be missing objects. 535 * @throws IncorrectObjectTypeException 536 * {@link #isRecursive()} was enabled, a subtree was found, and 537 * the subtree id does not denote a tree, but instead names some 538 * other non-tree type of object. The repository may have data 539 * corruption. 540 * @throws CorruptObjectException 541 * the contents of a tree did not appear to be a tree. The 542 * repository may have data corruption. 543 * @throws IOException 544 * a loose object or pack file could not be read. 545 */ 546 public boolean next() throws MissingObjectException, 547 IncorrectObjectTypeException, CorruptObjectException, IOException { 548 try { 549 if (advance) { 550 advance = false; 551 postChildren = false; 552 popEntriesEqual(); 553 } 554 555 for (;;) { 556 final AbstractTreeIterator t = min(); 557 if (t.eof()) { 558 if (depth > 0) { 559 exitSubtree(); 560 if (postOrderTraversal) { 561 advance = true; 562 postChildren = true; 563 return true; 564 } 565 popEntriesEqual(); 566 continue; 567 } 568 return false; 569 } 570 571 currentHead = t; 572 if (!filter.include(this)) { 573 skipEntriesEqual(); 574 continue; 575 } 576 577 if (recursive && FileMode.TREE.equals(t.mode)) { 578 enterSubtree(); 579 continue; 580 } 581 582 advance = true; 583 return true; 584 } 585 } catch (StopWalkException stop) { 586 for (final AbstractTreeIterator t : trees) 587 t.stopWalk(); 588 return false; 589 } 590 } 591 592 /** 593 * Obtain the tree iterator for the current entry. 594 * <p> 595 * Entering into (or exiting out of) a subtree causes the current tree 596 * iterator instance to be changed for the nth tree. This allows the tree 597 * iterators to manage only one list of items, with the diving handled by 598 * recursive trees. 599 * 600 * @param <T> 601 * type of the tree iterator expected by the caller. 602 * @param nth 603 * tree to obtain the current iterator of. 604 * @param clazz 605 * type of the tree iterator expected by the caller. 606 * @return r the current iterator of the requested type; null if the tree 607 * has no entry to match the current path. 608 */ 609 @SuppressWarnings("unchecked") 610 public <T extends AbstractTreeIterator> T getTree(final int nth, 611 final Class<T> clazz) { 612 final AbstractTreeIterator t = trees[nth]; 613 return t.matches == currentHead ? (T) t : null; 614 } 615 616 /** 617 * Obtain the raw {@link FileMode} bits for the current entry. 618 * <p> 619 * Every added tree supplies mode bits, even if the tree does not contain 620 * the current entry. In the latter case {@link FileMode#MISSING}'s mode 621 * bits (0) are returned. 622 * 623 * @param nth 624 * tree to obtain the mode bits from. 625 * @return mode bits for the current entry of the nth tree. 626 * @see FileMode#fromBits(int) 627 */ 628 public int getRawMode(final int nth) { 629 final AbstractTreeIterator t = trees[nth]; 630 return t.matches == currentHead ? t.mode : 0; 631 } 632 633 /** 634 * Obtain the {@link FileMode} for the current entry. 635 * <p> 636 * Every added tree supplies a mode, even if the tree does not contain the 637 * current entry. In the latter case {@link FileMode#MISSING} is returned. 638 * 639 * @param nth 640 * tree to obtain the mode from. 641 * @return mode for the current entry of the nth tree. 642 */ 643 public FileMode getFileMode(final int nth) { 644 return FileMode.fromBits(getRawMode(nth)); 645 } 646 647 /** 648 * Obtain the ObjectId for the current entry. 649 * <p> 650 * Using this method to compare ObjectId values between trees of this walker 651 * is very inefficient. Applications should try to use 652 * {@link #idEqual(int, int)} or {@link #getObjectId(MutableObjectId, int)} 653 * whenever possible. 654 * <p> 655 * Every tree supplies an object id, even if the tree does not contain the 656 * current entry. In the latter case {@link ObjectId#zeroId()} is returned. 657 * 658 * @param nth 659 * tree to obtain the object identifier from. 660 * @return object identifier for the current tree entry. 661 * @see #getObjectId(MutableObjectId, int) 662 * @see #idEqual(int, int) 663 */ 664 public ObjectId getObjectId(final int nth) { 665 final AbstractTreeIterator t = trees[nth]; 666 return t.matches == currentHead ? t.getEntryObjectId() : ObjectId 667 .zeroId(); 668 } 669 670 /** 671 * Obtain the ObjectId for the current entry. 672 * <p> 673 * Every tree supplies an object id, even if the tree does not contain the 674 * current entry. In the latter case {@link ObjectId#zeroId()} is supplied. 675 * <p> 676 * Applications should try to use {@link #idEqual(int, int)} when possible 677 * as it avoids conversion overheads. 678 * 679 * @param out 680 * buffer to copy the object id into. 681 * @param nth 682 * tree to obtain the object identifier from. 683 * @see #idEqual(int, int) 684 */ 685 public void getObjectId(final MutableObjectId out, final int nth) { 686 final AbstractTreeIterator t = trees[nth]; 687 if (t.matches == currentHead) 688 t.getEntryObjectId(out); 689 else 690 out.clear(); 691 } 692 693 /** 694 * Compare two tree's current ObjectId values for equality. 695 * 696 * @param nthA 697 * first tree to compare the object id from. 698 * @param nthB 699 * second tree to compare the object id from. 700 * @return result of 701 * <code>getObjectId(nthA).equals(getObjectId(nthB))</code>. 702 * @see #getObjectId(int) 703 */ 704 public boolean idEqual(final int nthA, final int nthB) { 705 final AbstractTreeIterator ch = currentHead; 706 final AbstractTreeIterator a = trees[nthA]; 707 final AbstractTreeIterator b = trees[nthB]; 708 if (a.matches != ch && b.matches != ch) { 709 // If neither tree matches the current path node then neither 710 // tree has this entry. In such case the ObjectId is zero(), 711 // and zero() is always equal to zero(). 712 // 713 return true; 714 } 715 if (!a.hasId() || !b.hasId()) 716 return false; 717 if (a.matches == ch && b.matches == ch) 718 return a.idEqual(b); 719 return false; 720 } 721 722 /** 723 * Get the current entry's name within its parent tree. 724 * <p> 725 * This method is not very efficient and is primarily meant for debugging 726 * and final output generation. Applications should try to avoid calling it, 727 * and if invoked do so only once per interesting entry, where the name is 728 * absolutely required for correct function. 729 * 730 * @return name of the current entry within the parent tree (or directory). 731 * The name never includes a '/'. 732 */ 733 public String getNameString() { 734 final AbstractTreeIterator t = currentHead; 735 final int off = t.pathOffset; 736 final int end = t.pathLen; 737 return RawParseUtils.decode(Constants.CHARSET, t.path, off, end); 738 } 739 740 /** 741 * Get the current entry's complete path. 742 * <p> 743 * This method is not very efficient and is primarily meant for debugging 744 * and final output generation. Applications should try to avoid calling it, 745 * and if invoked do so only once per interesting entry, where the name is 746 * absolutely required for correct function. 747 * 748 * @return complete path of the current entry, from the root of the 749 * repository. If the current entry is in a subtree there will be at 750 * least one '/' in the returned string. 751 */ 752 public String getPathString() { 753 return pathOf(currentHead); 754 } 755 756 /** 757 * Get the current entry's complete path as a UTF-8 byte array. 758 * 759 * @return complete path of the current entry, from the root of the 760 * repository. If the current entry is in a subtree there will be at 761 * least one '/' in the returned string. 762 */ 763 public byte[] getRawPath() { 764 final AbstractTreeIterator t = currentHead; 765 final int n = t.pathLen; 766 final byte[] r = new byte[n]; 767 System.arraycopy(t.path, 0, r, 0, n); 768 return r; 769 } 770 771 /** 772 * @return The path length of the current entry. 773 */ 774 public int getPathLength() { 775 return currentHead.pathLen; 776 } 777 778 /** 779 * Test if the supplied path matches the current entry's path. 780 * <p> 781 * This method tests that the supplied path is exactly equal to the current 782 * entry, or is one of its parent directories. It is faster to use this 783 * method then to use {@link #getPathString()} to first create a String 784 * object, then test <code>startsWith</code> or some other type of string 785 * match function. 786 * 787 * @param p 788 * path buffer to test. Callers should ensure the path does not 789 * end with '/' prior to invocation. 790 * @param pLen 791 * number of bytes from <code>buf</code> to test. 792 * @return < 0 if p is before the current path; 0 if p matches the current 793 * path; 1 if the current path is past p and p will never match 794 * again on this tree walk. 795 */ 796 public int isPathPrefix(final byte[] p, final int pLen) { 797 final AbstractTreeIterator t = currentHead; 798 final byte[] c = t.path; 799 final int cLen = t.pathLen; 800 int ci; 801 802 for (ci = 0; ci < cLen && ci < pLen; ci++) { 803 final int c_value = (c[ci] & 0xff) - (p[ci] & 0xff); 804 if (c_value != 0) 805 return c_value; 806 } 807 808 if (ci < cLen) { 809 // Ran out of pattern but we still had current data. 810 // If c[ci] == '/' then pattern matches the subtree. 811 // Otherwise we cannot be certain so we return -1. 812 // 813 return c[ci] == '/' ? 0 : -1; 814 } 815 816 if (ci < pLen) { 817 // Ran out of current, but we still have pattern data. 818 // If p[ci] == '/' then pattern matches this subtree, 819 // otherwise we cannot be certain so we return -1. 820 // 821 return p[ci] == '/' ? 0 : -1; 822 } 823 824 // Both strings are identical. 825 // 826 return 0; 827 } 828 829 /** 830 * Test if the supplied path matches (being suffix of) the current entry's 831 * path. 832 * <p> 833 * This method tests that the supplied path is exactly equal to the current 834 * entry, or is relative to one of entry's parent directories. It is faster 835 * to use this method then to use {@link #getPathString()} to first create 836 * a String object, then test <code>endsWith</code> or some other type of 837 * string match function. 838 * 839 * @param p 840 * path buffer to test. 841 * @param pLen 842 * number of bytes from <code>buf</code> to test. 843 * @return true if p is suffix of the current path; 844 * false if otherwise 845 */ 846 public boolean isPathSuffix(final byte[] p, final int pLen) { 847 final AbstractTreeIterator t = currentHead; 848 final byte[] c = t.path; 849 final int cLen = t.pathLen; 850 851 for (int i = 1; i <= pLen; i++) { 852 // Pattern longer than current path 853 if (i > cLen) 854 return false; 855 // Current path doesn't match pattern 856 if (c[cLen - i] != p[pLen - i]) 857 return false; 858 } 859 860 // Whole pattern tested -> matches 861 return true; 862 } 863 864 /** 865 * Get the current subtree depth of this walker. 866 * 867 * @return the current subtree depth of this walker. 868 */ 869 public int getDepth() { 870 return depth; 871 } 872 873 /** 874 * Is the current entry a subtree? 875 * <p> 876 * This method is faster then testing the raw mode bits of all trees to see 877 * if any of them are a subtree. If at least one is a subtree then this 878 * method will return true. 879 * 880 * @return true if {@link #enterSubtree()} will work on the current node. 881 */ 882 public boolean isSubtree() { 883 return FileMode.TREE.equals(currentHead.mode); 884 } 885 886 /** 887 * Is the current entry a subtree returned after its children? 888 * 889 * @return true if the current node is a tree that has been returned after 890 * its children were already processed. 891 * @see #isPostOrderTraversal() 892 */ 893 public boolean isPostChildren() { 894 return postChildren && isSubtree(); 895 } 896 897 /** 898 * Enter into the current subtree. 899 * <p> 900 * If the current entry is a subtree this method arranges for its children 901 * to be returned before the next sibling following the subtree is returned. 902 * 903 * @throws MissingObjectException 904 * a subtree was found, but the subtree object does not exist in 905 * this repository. The repository may be missing objects. 906 * @throws IncorrectObjectTypeException 907 * a subtree was found, and the subtree id does not denote a 908 * tree, but instead names some other non-tree type of object. 909 * The repository may have data corruption. 910 * @throws CorruptObjectException 911 * the contents of a tree did not appear to be a tree. The 912 * repository may have data corruption. 913 * @throws IOException 914 * a loose object or pack file could not be read. 915 */ 916 public void enterSubtree() throws MissingObjectException, 917 IncorrectObjectTypeException, CorruptObjectException, IOException { 918 final AbstractTreeIterator ch = currentHead; 919 final AbstractTreeIterator[] tmp = new AbstractTreeIterator[trees.length]; 920 for (int i = 0; i < trees.length; i++) { 921 final AbstractTreeIterator t = trees[i]; 922 final AbstractTreeIterator n; 923 if (t.matches == ch && !t.eof() && FileMode.TREE.equals(t.mode)) 924 n = t.createSubtreeIterator(reader, idBuffer); 925 else 926 n = t.createEmptyTreeIterator(); 927 tmp[i] = n; 928 } 929 depth++; 930 advance = false; 931 System.arraycopy(tmp, 0, trees, 0, trees.length); 932 } 933 934 @SuppressWarnings("unused") 935 AbstractTreeIterator min() throws CorruptObjectException { 936 int i = 0; 937 AbstractTreeIterator minRef = trees[i]; 938 while (minRef.eof() && ++i < trees.length) 939 minRef = trees[i]; 940 if (minRef.eof()) 941 return minRef; 942 943 minRef.matches = minRef; 944 while (++i < trees.length) { 945 final AbstractTreeIterator t = trees[i]; 946 if (t.eof()) 947 continue; 948 final int cmp = t.pathCompare(minRef); 949 if (cmp < 0) { 950 t.matches = t; 951 minRef = t; 952 } else if (cmp == 0) { 953 t.matches = minRef; 954 } 955 } 956 957 return minRef; 958 } 959 960 void popEntriesEqual() throws CorruptObjectException { 961 final AbstractTreeIterator ch = currentHead; 962 for (int i = 0; i < trees.length; i++) { 963 final AbstractTreeIterator t = trees[i]; 964 if (t.matches == ch) { 965 t.next(1); 966 t.matches = null; 967 } 968 } 969 } 970 971 void skipEntriesEqual() throws CorruptObjectException { 972 final AbstractTreeIterator ch = currentHead; 973 for (int i = 0; i < trees.length; i++) { 974 final AbstractTreeIterator t = trees[i]; 975 if (t.matches == ch) { 976 t.skip(); 977 t.matches = null; 978 } 979 } 980 } 981 982 private void exitSubtree() { 983 depth--; 984 for (int i = 0; i < trees.length; i++) 985 trees[i] = trees[i].parent; 986 987 AbstractTreeIterator minRef = null; 988 for (final AbstractTreeIterator t : trees) { 989 if (t.matches != t) 990 continue; 991 if (minRef == null || t.pathCompare(minRef) < 0) 992 minRef = t; 993 } 994 currentHead = minRef; 995 } 996 997 private CanonicalTreeParser parserFor(final AnyObjectId id) 998 throws IncorrectObjectTypeException, IOException { 999 final CanonicalTreeParser p = new CanonicalTreeParser(); 1000 p.reset(reader, id); 1001 return p; 1002 } 1003 1004 static String pathOf(final AbstractTreeIterator t) { 1005 return RawParseUtils.decode(Constants.CHARSET, t.path, 0, t.pathLen); 1006 } 1007 1008 static String pathOf(final byte[] buf, int pos, int end) { 1009 return RawParseUtils.decode(Constants.CHARSET, buf, pos, end); 1010 } 1011 }