org.spearce.jgit/src/org/spearce/jgit/lib/Tree.java

   1 /*
   2  * Copyright (C) 2007, Robin Rosenberg <me@lathund.dewire.com>
   3  * Copyright (C) 2008, Robin Rosenberg <robin.rosenberg@dewire.com>
   4  * Copyright (C) 2008, Shawn O. Pearce <spearce@spearce.org>
   5  *
   6  * All rights reserved.
   7  *
   8  * Redistribution and use in source and binary forms, with or
   9  * without modification, are permitted provided that the following
  10  * conditions are met:
  11  *
  12  * - Redistributions of source code must retain the above copyright
  13  *   notice, this list of conditions and the following disclaimer.
  14  *
  15  * - Redistributions in binary form must reproduce the above
  16  *   copyright notice, this list of conditions and the following
  17  *   disclaimer in the documentation and/or other materials provided
  18  *   with the distribution.
  19  *
  20  * - Neither the name of the Git Development Community nor the
  21  *   names of its contributors may be used to endorse or promote
  22  *   products derived from this software without specific prior
  23  *   written permission.
  24  *
  25  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
  26  * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
  27  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  28  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  29  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
  30  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  31  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  32  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  33  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  34  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  35  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  36  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
  37  * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  38  */
  39
  40 package org.spearce.jgit.lib;
  41
  42 import java.io.IOException;
  43
  44 import org.spearce.jgit.errors.CorruptObjectException;
  45 import org.spearce.jgit.errors.EntryExistsException;
  46 import org.spearce.jgit.errors.MissingObjectException;
  47
  48 /**
  49  * A representation of a Git tree entry. A Tree is a directory in Git.
  50  */
  51 public class Tree extends TreeEntry implements Treeish {
  52         private static final TreeEntry[] EMPTY_TREE = {};
  53
  54         /**
  55          * Compare two names represented as bytes. Since git treats names of trees and
  56          * blobs differently we have one parameter that represents a '/' for trees. For
  57          * other objects the value should be NUL. The names are compare by their positive
  58          * byte value (0..255).
  59          *
  60          * A blob and a tree with the same name will not compare equal.
  61          *
  62          * @param a name
  63          * @param b name
  64          * @param lasta '/' if a is a tree, else NUL
  65          * @param lastb '/' if b is a tree, else NUL
  66          *
  67          * @return < 0 if a is sorted before b, 0 if they are the same, else b
  68          */
  69         public static final int compareNames(final byte[] a, final byte[] b, final int lasta,final int lastb) {
  70                 return compareNames(a, b, 0, b.length, lasta, lastb);
  71         }
  72
  73         private static final int compareNames(final byte[] a, final byte[] nameUTF8,
  74                         final int nameStart, final int nameEnd, final int lasta, int lastb) {
  75                 int j,k;
  76                 for (j = 0, k = nameStart; j < a.length && k < nameEnd; j++, k++) {
  77                         final int aj = a[j] & 0xff;
  78                         final int bk = nameUTF8[k] & 0xff;
  79                         if (aj < bk)
  80                                 return -1;
  81                         else if (aj > bk)
  82                                 return 1;
  83                 }
  84                 if (j < a.length) {
  85                         int aj = a[j]&0xff;
  86                         if (aj < lastb)
  87                                 return -1;
  88                         else if (aj > lastb)
  89                                 return 1;
  90                         else
  91                                 if (j == a.length - 1)
  92                                         return 0;
  93                                 else
  94                                         return -1;
  95                 }
  96                 if (k < nameEnd) {
  97                         int bk = nameUTF8[k] & 0xff;
  98                         if (lasta < bk)
  99                                 return -1;
 100                         else if (lasta > bk)
 101                                 return 1;
 102                         else
 103                                 if (k == nameEnd - 1)
 104                                         return 0;
 105                                 else
 106                                         return 1;
 107                 }
 108                 if (lasta < lastb)
 109                         return -1;
 110                 else if (lasta > lastb)
 111                         return 1;
 112
 113                 final int namelength = nameEnd - nameStart;
 114                 if (a.length == namelength)
 115                         return 0;
 116                 else if (a.length < namelength)
 117                         return -1;
 118                 else
 119                         return 1;
 120         }
 121
 122         private static final byte[] substring(final byte[] s, final int nameStart,
 123                         final int nameEnd) {
 124                 if (nameStart == 0 && nameStart == s.length)
 125                         return s;
 126                 final byte[] n = new byte[nameEnd - nameStart];
 127                 System.arraycopy(s, nameStart, n, 0, n.length);
 128                 return n;
 129         }
 130
 131         private static final int binarySearch(final TreeEntry[] entries,
 132                         final byte[] nameUTF8, final int nameUTF8last, final int nameStart, final int nameEnd) {
 133                 if (entries.length == 0)
 134                         return -1;
 135                 int high = entries.length;
 136                 int low = 0;
 137                 do {
 138                         final int mid = (low + high) / 2;
 139                         final int cmp = compareNames(entries[mid].getNameUTF8(), nameUTF8,
 140                                         nameStart, nameEnd, TreeEntry.lastChar(entries[mid]), nameUTF8last);
 141                         if (cmp < 0)
 142                                 low = mid + 1;
 143                         else if (cmp == 0)
 144                                 return mid;
 145                         else
 146                                 high = mid;
 147                 } while (low < high);
 148                 return -(low + 1);
 149         }
 150
 151         private final Repository db;
 152
 153         private TreeEntry[] contents;
 154
 155         /**
 156          * Constructor for a new Tree
 157          *
 158          * @param repo The repository that owns the Tree.
 159          */
 160         public Tree(final Repository repo) {
 161                 super(null, null, null);
 162                 db = repo;
 163                 contents = EMPTY_TREE;
 164         }
 165
 166         /**
 167          * Construct a Tree object with known content and hash value
 168          *
 169          * @param repo
 170          * @param myId
 171          * @param raw
 172          * @throws IOException
 173          */
 174         public Tree(final Repository repo, final ObjectId myId, final byte[] raw)
 175                         throws IOException {
 176                 super(null, myId, null);
 177                 db = repo;
 178                 readTree(raw);
 179         }
 180
 181         /**
 182          * Construct a new Tree under another Tree
 183          *
 184          * @param parent
 185          * @param nameUTF8
 186          */
 187         public Tree(final Tree parent, final byte[] nameUTF8) {
 188                 super(parent, null, nameUTF8);
 189                 db = parent.getRepository();
 190                 contents = EMPTY_TREE;
 191         }
 192
 193         /**
 194          * Construct a Tree with a known SHA-1 under another tree. Data is not yet
 195          * specified and will have to be loaded on demand.
 196          *
 197          * @param parent
 198          * @param id
 199          * @param nameUTF8
 200          */
 201         public Tree(final Tree parent, final ObjectId id, final byte[] nameUTF8) {
 202                 super(parent, id, nameUTF8);
 203                 db = parent.getRepository();
 204         }
 205
 206         public FileMode getMode() {
 207                 return FileMode.TREE;
 208         }
 209
 210         /**
 211          * @return true if this Tree is the top level Tree.
 212          */
 213         public boolean isRoot() {
 214                 return getParent() == null;
 215         }
 216
 217         public Repository getRepository() {
 218                 return db;
 219         }
 220
 221         public final ObjectId getTreeId() {
 222                 return getId();
 223         }
 224
 225         public final Tree getTree() {
 226                 return this;
 227         }
 228
 229         /**
 230          * @return true of the data of this Tree is loaded
 231          */
 232         public boolean isLoaded() {
 233                 return contents != null;
 234         }
 235
 236         /**
 237          * Forget the in-memory data for this tree.
 238          */
 239         public void unload() {
 240                 if (isModified())
 241                         throw new IllegalStateException("Cannot unload a modified tree.");
 242                 contents = null;
 243         }
 244
 245         /**
 246          * Adds a new or existing file with the specified name to this tree.
 247          * Trees are added if necessary as the name may contain '/':s.
 248          *
 249          * @param name Name
 250          * @return a {@link FileTreeEntry} for the added file.
 251          * @throws IOException
 252          */
 253         public FileTreeEntry addFile(final String name) throws IOException {
 254                 return addFile(Repository.gitInternalSlash(name.getBytes(Constants.CHARACTER_ENCODING)), 0);
 255         }
 256
 257         /**
 258          * Adds a new or existing file with the specified name to this tree.
 259          * Trees are added if necessary as the name may contain '/':s.
 260          *
 261          * @param s an array containing the name
 262          * @param offset when the name starts in the tree.
 263          *
 264          * @return a {@link FileTreeEntry} for the added file.
 265          * @throws IOException
 266          */
 267         public FileTreeEntry addFile(final byte[] s, final int offset)
 268                         throws IOException {
 269                 int slash;
 270                 int p;
 271
 272                 for (slash = offset; slash < s.length && s[slash] != '/'; slash++) {
 273                         // search for path component terminator
 274                 }
 275
 276                 ensureLoaded();
 277                 byte xlast = slash<s.length ? (byte)'/' : 0;
 278                 p = binarySearch(contents, s, xlast, offset, slash);
 279                 if (p >= 0 && slash < s.length && contents[p] instanceof Tree)
 280                         return ((Tree) contents[p]).addFile(s, slash + 1);
 281
 282                 final byte[] newName = substring(s, offset, slash);
 283                 if (p >= 0)
 284                         throw new EntryExistsException(new String(newName,
 285                                         Constants.CHARACTER_ENCODING));
 286                 else if (slash < s.length) {
 287                         final Tree t = new Tree(this, newName);
 288                         insertEntry(p, t);
 289                         return t.addFile(s, slash + 1);
 290                 } else {
 291                         final FileTreeEntry f = new FileTreeEntry(this, null, newName,
 292                                         false);
 293                         insertEntry(p, f);
 294                         return f;
 295                 }
 296         }
 297
 298         /**
 299          * Adds a new or existing Tree with the specified name to this tree.
 300          * Trees are added if necessary as the name may contain '/':s.
 301          *
 302          * @param name Name
 303          * @return a {@link FileTreeEntry} for the added tree.
 304          * @throws IOException
 305          */
 306         public Tree addTree(final String name) throws IOException {
 307                 return addTree(Repository.gitInternalSlash(name.getBytes(Constants.CHARACTER_ENCODING)), 0);
 308         }
 309
 310         /**
 311          * Adds a new or existing Tree with the specified name to this tree.
 312          * Trees are added if necessary as the name may contain '/':s.
 313          *
 314          * @param s an array containing the name
 315          * @param offset when the name starts in the tree.
 316          *
 317          * @return a {@link FileTreeEntry} for the added tree.
 318          * @throws IOException
 319          */
 320         public Tree addTree(final byte[] s, final int offset) throws IOException {
 321                 int slash;
 322                 int p;
 323
 324                 for (slash = offset; slash < s.length && s[slash] != '/'; slash++) {
 325                         // search for path component terminator
 326                 }
 327
 328                 ensureLoaded();
 329                 p = binarySearch(contents, s, (byte)'/', offset, slash);
 330                 if (p >= 0 && slash < s.length && contents[p] instanceof Tree)
 331                         return ((Tree) contents[p]).addTree(s, slash + 1);
 332
 333                 final byte[] newName = substring(s, offset, slash);
 334                 if (p >= 0)
 335                         throw new EntryExistsException(new String(newName,
 336                                         Constants.CHARACTER_ENCODING));
 337
 338                 final Tree t = new Tree(this, newName);
 339                 insertEntry(p, t);
 340                 return slash == s.length ? t : t.addTree(s, slash + 1);
 341         }
 342
 343         /**
 344          * Add the specified tree entry to this tree.
 345          *
 346          * @param e
 347          * @throws IOException
 348          */
 349         public void addEntry(final TreeEntry e) throws IOException {
 350                 final int p;
 351
 352                 ensureLoaded();
 353                 p = binarySearch(contents, e.getNameUTF8(), TreeEntry.lastChar(e), 0, e.getNameUTF8().length);
 354                 if (p < 0) {
 355                         e.attachParent(this);
 356                         insertEntry(p, e);
 357                 } else {
 358                         throw new EntryExistsException(new String(e.getNameUTF8(),
 359                                         Constants.CHARACTER_ENCODING));
 360                 }
 361         }
 362
 363         private void insertEntry(int p, final TreeEntry e) {
 364                 final TreeEntry[] c = contents;
 365                 final TreeEntry[] n = new TreeEntry[c.length + 1];
 366                 p = -(p + 1);
 367                 for (int k = c.length - 1; k >= p; k--)
 368                         n[k + 1] = c[k];
 369                 n[p] = e;
 370                 for (int k = p - 1; k >= 0; k--)
 371                         n[k] = c[k];
 372                 contents = n;
 373                 setModified();
 374         }
 375
 376         void removeEntry(final TreeEntry e) {
 377                 final TreeEntry[] c = contents;
 378                 final int p = binarySearch(c, e.getNameUTF8(), TreeEntry.lastChar(e), 0,
 379                                 e.getNameUTF8().length);
 380                 if (p >= 0) {
 381                         final TreeEntry[] n = new TreeEntry[c.length - 1];
 382                         for (int k = c.length - 1; k > p; k--)
 383                                 n[k - 1] = c[k];
 384                         for (int k = p - 1; k >= 0; k--)
 385                                 n[k] = c[k];
 386                         contents = n;
 387                         setModified();
 388                 }
 389         }
 390
 391         /**
 392          * @return number of members in this tree
 393          * @throws IOException
 394          */
 395         public int memberCount() throws IOException {
 396                 ensureLoaded();
 397                 return contents.length;
 398         }
 399
 400         /**
 401          * Return all members of the tree sorted in Git order.
 402          *
 403          * Entries are sorted by the numerical unsigned byte
 404          * values with (sub)trees having an implicit '/'. An
 405          * example of a tree with three entries. a:b is an
 406          * actual file name here.
 407          *
 408          * <p>
 409          * 100644 blob e69de29bb2d1d6434b8b29ae775ad8c2e48c5391    a.b
 410          * 040000 tree 4277b6e69d25e5efa77c455340557b384a4c018a    a
 411          * 100644 blob e69de29bb2d1d6434b8b29ae775ad8c2e48c5391    a:b
 412          *
 413          * @return all entries in this Tree, sorted.
 414          * @throws IOException
 415          */
 416         public TreeEntry[] members() throws IOException {
 417                 ensureLoaded();
 418                 final TreeEntry[] c = contents;
 419                 if (c.length != 0) {
 420                         final TreeEntry[] r = new TreeEntry[c.length];
 421                         for (int k = c.length - 1; k >= 0; k--)
 422                                 r[k] = c[k];
 423                         return r;
 424                 } else
 425                         return c;
 426         }
 427
 428         private boolean exists(final String s, byte slast) throws IOException {
 429                 return findMember(s, slast) != null;
 430         }
 431
 432         /**
 433          * @param path
 434          * @return true if a tree with the specified path can be found under this
 435          *         tree.
 436          * @throws IOException
 437          */
 438         public boolean existsTree(String path) throws IOException {
 439                 return exists(path,(byte)'/');
 440         }
 441
 442         /**
 443          * @param path
 444          * @return true if a blob or symlink with the specified name can be found
 445          *         under this tree.
 446          * @throws IOException
 447          */
 448         public boolean existsBlob(String path) throws IOException {
 449                 return exists(path,(byte)0);
 450         }
 451
 452         private TreeEntry findMember(final String s, byte slast) throws IOException {
 453                 return findMember(Repository.gitInternalSlash(s.getBytes(Constants.CHARACTER_ENCODING)), slast, 0);
 454         }
 455
 456         private TreeEntry findMember(final byte[] s, final byte slast, final int offset)
 457                         throws IOException {
 458                 int slash;
 459                 int p;
 460
 461                 for (slash = offset; slash < s.length && s[slash] != '/'; slash++) {
 462                         // search for path component terminator
 463                 }
 464
 465                 ensureLoaded();
 466                 byte xlast = slash<s.length ? (byte)'/' : slast;
 467                 p = binarySearch(contents, s, xlast, offset, slash);
 468                 if (p >= 0) {
 469                         final TreeEntry r = contents[p];
 470                         if (slash < s.length-1)
 471                                 return r instanceof Tree ? ((Tree) r).findMember(s, slast, slash + 1)
 472                                                 : null;
 473                         return r;
 474                 }
 475                 return null;
 476         }
 477
 478         /**
 479          * @param s
 480          *            blob name
 481          * @return a {@link TreeEntry} representing an object with the specified
 482          *         relative path.
 483          * @throws IOException
 484          */
 485         public TreeEntry findBlobMember(String s) throws IOException {
 486                 return findMember(s,(byte)0);
 487         }
 488
 489         /**
 490          * @param s Tree Name
 491          * @return a Tree with the name s or null
 492          * @throws IOException
 493          */
 494         public TreeEntry findTreeMember(String s) throws IOException {
 495                 return findMember(s,(byte)'/');
 496         }
 497
 498         public void accept(final TreeVisitor tv, final int flags)
 499                         throws IOException {
 500                 final TreeEntry[] c;
 501
 502                 if ((MODIFIED_ONLY & flags) == MODIFIED_ONLY && !isModified())
 503                         return;
 504
 505                 if ((LOADED_ONLY & flags) == LOADED_ONLY && !isLoaded()) {
 506                         tv.startVisitTree(this);
 507                         tv.endVisitTree(this);
 508                         return;
 509                 }
 510
 511                 ensureLoaded();
 512                 tv.startVisitTree(this);
 513
 514                 if ((CONCURRENT_MODIFICATION & flags) == CONCURRENT_MODIFICATION)
 515                         c = members();
 516                 else
 517                         c = contents;
 518
 519                 for (int k = 0; k < c.length; k++)
 520                         c[k].accept(tv, flags);
 521
 522                 tv.endVisitTree(this);
 523         }
 524
 525         private void ensureLoaded() throws IOException, MissingObjectException {
 526                 if (!isLoaded()) {
 527                         final ObjectLoader or = db.openTree(getId());
 528                         if (or == null)
 529                                 throw new MissingObjectException(getId(), Constants.TYPE_TREE);
 530                         readTree(or.getBytes());
 531                 }
 532         }
 533
 534         private void readTree(final byte[] raw) throws IOException {
 535                 final int rawSize = raw.length;
 536                 int rawPtr = 0;
 537                 TreeEntry[] temp;
 538                 int nextIndex = 0;
 539
 540                 while (rawPtr < rawSize) {
 541                         while (rawPtr < rawSize && raw[rawPtr] != 0)
 542                                 rawPtr++;
 543                         rawPtr++;
 544                         rawPtr += Constants.OBJECT_ID_LENGTH;
 545                         nextIndex++;
 546                 }
 547
 548                 temp = new TreeEntry[nextIndex];
 549                 rawPtr = 0;
 550                 nextIndex = 0;
 551                 while (rawPtr < rawSize) {
 552                         int c = raw[rawPtr++];
 553                         if (c < '0' || c > '7')
 554                                 throw new CorruptObjectException(getId(), "invalid entry mode");
 555                         int mode = c - '0';
 556                         for (;;) {
 557                                 c = raw[rawPtr++];
 558                                 if (' ' == c)
 559                                         break;
 560                                 else if (c < '0' || c > '7')
 561                                         throw new CorruptObjectException(getId(), "invalid mode");
 562                                 mode <<= 3;
 563                                 mode += c - '0';
 564                         }
 565
 566                         int nameLen = 0;
 567                         while (raw[rawPtr + nameLen] != 0)
 568                                 nameLen++;
 569                         final byte[] name = new byte[nameLen];
 570                         System.arraycopy(raw, rawPtr, name, 0, nameLen);
 571                         rawPtr += nameLen + 1;
 572
 573                         final ObjectId id = ObjectId.fromRaw(raw, rawPtr);
 574                         rawPtr += Constants.OBJECT_ID_LENGTH;
 575
 576                         final TreeEntry ent;
 577                         if (FileMode.REGULAR_FILE.equals(mode))
 578                                 ent = new FileTreeEntry(this, id, name, false);
 579                         else if (FileMode.EXECUTABLE_FILE.equals(mode))
 580                                 ent = new FileTreeEntry(this, id, name, true);
 581                         else if (FileMode.TREE.equals(mode)) {
 582                                 ent = new Tree(this, id, name);
 583                         } else if (FileMode.SYMLINK.equals(mode))
 584                                 ent = new SymlinkTreeEntry(this, id, name);
 585                         else
 586                                 throw new CorruptObjectException(getId(), "Invalid mode: "
 587                                                 + Integer.toOctalString(mode));
 588                         temp[nextIndex++] = ent;
 589                 }
 590
 591                 contents = temp;
 592         }
 593
 594         public String toString() {
 595                 final StringBuffer r = new StringBuffer();
 596                 r.append(ObjectId.toString(getId()));
 597                 r.append(" T ");
 598                 r.append(getFullName());
 599                 return r.toString();
 600         }
 601
 602 }