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 import org.spearce.jgit.util.RawParseUtils;
  48
  49 /**
  50  * A representation of a Git tree entry. A Tree is a directory in Git.
  51  */
  52 public class Tree extends TreeEntry implements Treeish {
  53         private static final TreeEntry[] EMPTY_TREE = {};
  54
  55         /**
  56          * Compare two names represented as bytes. Since git treats names of trees and
  57          * blobs differently we have one parameter that represents a '/' for trees. For
  58          * other objects the value should be NUL. The names are compare by their positive
  59          * byte value (0..255).
  60          *
  61          * A blob and a tree with the same name will not compare equal.
  62          *
  63          * @param a name
  64          * @param b name
  65          * @param lasta '/' if a is a tree, else NUL
  66          * @param lastb '/' if b is a tree, else NUL
  67          *
  68          * @return < 0 if a is sorted before b, 0 if they are the same, else b
  69          */
  70         public static final int compareNames(final byte[] a, final byte[] b, final int lasta,final int lastb) {
  71                 return compareNames(a, b, 0, b.length, lasta, lastb);
  72         }
  73
  74         private static final int compareNames(final byte[] a, final byte[] nameUTF8,
  75                         final int nameStart, final int nameEnd, final int lasta, int lastb) {
  76                 int j,k;
  77                 for (j = 0, k = nameStart; j < a.length && k < nameEnd; j++, k++) {
  78                         final int aj = a[j] & 0xff;
  79                         final int bk = nameUTF8[k] & 0xff;
  80                         if (aj < bk)
  81                                 return -1;
  82                         else if (aj > bk)
  83                                 return 1;
  84                 }
  85                 if (j < a.length) {
  86                         int aj = a[j]&0xff;
  87                         if (aj < lastb)
  88                                 return -1;
  89                         else if (aj > lastb)
  90                                 return 1;
  91                         else
  92                                 if (j == a.length - 1)
  93                                         return 0;
  94                                 else
  95                                         return -1;
  96                 }
  97                 if (k < nameEnd) {
  98                         int bk = nameUTF8[k] & 0xff;
  99                         if (lasta < bk)
 100                                 return -1;
 101                         else if (lasta > bk)
 102                                 return 1;
 103                         else
 104                                 if (k == nameEnd - 1)
 105                                         return 0;
 106                                 else
 107                                         return 1;
 108                 }
 109                 if (lasta < lastb)
 110                         return -1;
 111                 else if (lasta > lastb)
 112                         return 1;
 113
 114                 final int namelength = nameEnd - nameStart;
 115                 if (a.length == namelength)
 116                         return 0;
 117                 else if (a.length < namelength)
 118                         return -1;
 119                 else
 120                         return 1;
 121         }
 122
 123         private static final byte[] substring(final byte[] s, final int nameStart,
 124                         final int nameEnd) {
 125                 if (nameStart == 0 && nameStart == s.length)
 126                         return s;
 127                 final byte[] n = new byte[nameEnd - nameStart];
 128                 System.arraycopy(s, nameStart, n, 0, n.length);
 129                 return n;
 130         }
 131
 132         private static final int binarySearch(final TreeEntry[] entries,
 133                         final byte[] nameUTF8, final int nameUTF8last, final int nameStart, final int nameEnd) {
 134                 if (entries.length == 0)
 135                         return -1;
 136                 int high = entries.length;
 137                 int low = 0;
 138                 do {
 139                         final int mid = (low + high) >>> 1;
 140                         final int cmp = compareNames(entries[mid].getNameUTF8(), nameUTF8,
 141                                         nameStart, nameEnd, TreeEntry.lastChar(entries[mid]), nameUTF8last);
 142                         if (cmp < 0)
 143                                 low = mid + 1;
 144                         else if (cmp == 0)
 145                                 return mid;
 146                         else
 147                                 high = mid;
 148                 } while (low < high);
 149                 return -(low + 1);
 150         }
 151
 152         private final Repository db;
 153
 154         private TreeEntry[] contents;
 155
 156         /**
 157          * Constructor for a new Tree
 158          *
 159          * @param repo The repository that owns the Tree.
 160          */
 161         public Tree(final Repository repo) {
 162                 super(null, null, null);
 163                 db = repo;
 164                 contents = EMPTY_TREE;
 165         }
 166
 167         /**
 168          * Construct a Tree object with known content and hash value
 169          *
 170          * @param repo
 171          * @param myId
 172          * @param raw
 173          * @throws IOException
 174          */
 175         public Tree(final Repository repo, final ObjectId myId, final byte[] raw)
 176                         throws IOException {
 177                 super(null, myId, null);
 178                 db = repo;
 179                 readTree(raw);
 180         }
 181
 182         /**
 183          * Construct a new Tree under another Tree
 184          *
 185          * @param parent
 186          * @param nameUTF8
 187          */
 188         public Tree(final Tree parent, final byte[] nameUTF8) {
 189                 super(parent, null, nameUTF8);
 190                 db = parent.getRepository();
 191                 contents = EMPTY_TREE;
 192         }
 193
 194         /**
 195          * Construct a Tree with a known SHA-1 under another tree. Data is not yet
 196          * specified and will have to be loaded on demand.
 197          *
 198          * @param parent
 199          * @param id
 200          * @param nameUTF8
 201          */
 202         public Tree(final Tree parent, final ObjectId id, final byte[] nameUTF8) {
 203                 super(parent, id, nameUTF8);
 204                 db = parent.getRepository();
 205         }
 206
 207         public FileMode getMode() {
 208                 return FileMode.TREE;
 209         }
 210
 211         /**
 212          * @return true if this Tree is the top level Tree.
 213          */
 214         public boolean isRoot() {
 215                 return getParent() == null;
 216         }
 217
 218         public Repository getRepository() {
 219                 return db;
 220         }
 221
 222         public final ObjectId getTreeId() {
 223                 return getId();
 224         }
 225
 226         public final Tree getTree() {
 227                 return this;
 228         }
 229
 230         /**
 231          * @return true of the data of this Tree is loaded
 232          */
 233         public boolean isLoaded() {
 234                 return contents != null;
 235         }
 236
 237         /**
 238          * Forget the in-memory data for this tree.
 239          */
 240         public void unload() {
 241                 if (isModified())
 242                         throw new IllegalStateException("Cannot unload a modified tree.");
 243                 contents = null;
 244         }
 245
 246         /**
 247          * Adds a new or existing file with the specified name to this tree.
 248          * Trees are added if necessary as the name may contain '/':s.
 249          *
 250          * @param name Name
 251          * @return a {@link FileTreeEntry} for the added file.
 252          * @throws IOException
 253          */
 254         public FileTreeEntry addFile(final String name) throws IOException {
 255                 return addFile(Repository.gitInternalSlash(Constants.encode(name)), 0);
 256         }
 257
 258         /**
 259          * Adds a new or existing file with the specified name to this tree.
 260          * Trees are added if necessary as the name may contain '/':s.
 261          *
 262          * @param s an array containing the name
 263          * @param offset when the name starts in the tree.
 264          *
 265          * @return a {@link FileTreeEntry} for the added file.
 266          * @throws IOException
 267          */
 268         public FileTreeEntry addFile(final byte[] s, final int offset)
 269                         throws IOException {
 270                 int slash;
 271                 int p;
 272
 273                 for (slash = offset; slash < s.length && s[slash] != '/'; slash++) {
 274                         // search for path component terminator
 275                 }
 276
 277                 ensureLoaded();
 278                 byte xlast = slash<s.length ? (byte)'/' : 0;
 279                 p = binarySearch(contents, s, xlast, offset, slash);
 280                 if (p >= 0 && slash < s.length && contents[p] instanceof Tree)
 281                         return ((Tree) contents[p]).addFile(s, slash + 1);
 282
 283                 final byte[] newName = substring(s, offset, slash);
 284                 if (p >= 0)
 285                         throw new EntryExistsException(RawParseUtils.decode(newName));
 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(Constants.encode(name)), 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(RawParseUtils.decode(newName));
 336
 337                 final Tree t = new Tree(this, newName);
 338                 insertEntry(p, t);
 339                 return slash == s.length ? t : t.addTree(s, slash + 1);
 340         }
 341
 342         /**
 343          * Add the specified tree entry to this tree.
 344          *
 345          * @param e
 346          * @throws IOException
 347          */
 348         public void addEntry(final TreeEntry e) throws IOException {
 349                 final int p;
 350
 351                 ensureLoaded();
 352                 p = binarySearch(contents, e.getNameUTF8(), TreeEntry.lastChar(e), 0, e.getNameUTF8().length);
 353                 if (p < 0) {
 354                         e.attachParent(this);
 355                         insertEntry(p, e);
 356                 } else {
 357                         throw new EntryExistsException(e.getName());
 358                 }
 359         }
 360
 361         private void insertEntry(int p, final TreeEntry e) {
 362                 final TreeEntry[] c = contents;
 363                 final TreeEntry[] n = new TreeEntry[c.length + 1];
 364                 p = -(p + 1);
 365                 for (int k = c.length - 1; k >= p; k--)
 366                         n[k + 1] = c[k];
 367                 n[p] = e;
 368                 for (int k = p - 1; k >= 0; k--)
 369                         n[k] = c[k];
 370                 contents = n;
 371                 setModified();
 372         }
 373
 374         void removeEntry(final TreeEntry e) {
 375                 final TreeEntry[] c = contents;
 376                 final int p = binarySearch(c, e.getNameUTF8(), TreeEntry.lastChar(e), 0,
 377                                 e.getNameUTF8().length);
 378                 if (p >= 0) {
 379                         final TreeEntry[] n = new TreeEntry[c.length - 1];
 380                         for (int k = c.length - 1; k > p; k--)
 381                                 n[k - 1] = c[k];
 382                         for (int k = p - 1; k >= 0; k--)
 383                                 n[k] = c[k];
 384                         contents = n;
 385                         setModified();
 386                 }
 387         }
 388
 389         /**
 390          * @return number of members in this tree
 391          * @throws IOException
 392          */
 393         public int memberCount() throws IOException {
 394                 ensureLoaded();
 395                 return contents.length;
 396         }
 397
 398         /**
 399          * Return all members of the tree sorted in Git order.
 400          *
 401          * Entries are sorted by the numerical unsigned byte
 402          * values with (sub)trees having an implicit '/'. An
 403          * example of a tree with three entries. a:b is an
 404          * actual file name here.
 405          *
 406          * <p>
 407          * 100644 blob e69de29bb2d1d6434b8b29ae775ad8c2e48c5391    a.b
 408          * 040000 tree 4277b6e69d25e5efa77c455340557b384a4c018a    a
 409          * 100644 blob e69de29bb2d1d6434b8b29ae775ad8c2e48c5391    a:b
 410          *
 411          * @return all entries in this Tree, sorted.
 412          * @throws IOException
 413          */
 414         public TreeEntry[] members() throws IOException {
 415                 ensureLoaded();
 416                 final TreeEntry[] c = contents;
 417                 if (c.length != 0) {
 418                         final TreeEntry[] r = new TreeEntry[c.length];
 419                         for (int k = c.length - 1; k >= 0; k--)
 420                                 r[k] = c[k];
 421                         return r;
 422                 } else
 423                         return c;
 424         }
 425
 426         private boolean exists(final String s, byte slast) throws IOException {
 427                 return findMember(s, slast) != null;
 428         }
 429
 430         /**
 431          * @param path
 432          * @return true if a tree with the specified path can be found under this
 433          *         tree.
 434          * @throws IOException
 435          */
 436         public boolean existsTree(String path) throws IOException {
 437                 return exists(path,(byte)'/');
 438         }
 439
 440         /**
 441          * @param path
 442          * @return true if a blob or symlink with the specified name can be found
 443          *         under this tree.
 444          * @throws IOException
 445          */
 446         public boolean existsBlob(String path) throws IOException {
 447                 return exists(path,(byte)0);
 448         }
 449
 450         private TreeEntry findMember(final String s, byte slast) throws IOException {
 451                 return findMember(Repository.gitInternalSlash(Constants.encode(s)), slast, 0);
 452         }
 453
 454         private TreeEntry findMember(final byte[] s, final byte slast, final int offset)
 455                         throws IOException {
 456                 int slash;
 457                 int p;
 458
 459                 for (slash = offset; slash < s.length && s[slash] != '/'; slash++) {
 460                         // search for path component terminator
 461                 }
 462
 463                 ensureLoaded();
 464                 byte xlast = slash<s.length ? (byte)'/' : slast;
 465                 p = binarySearch(contents, s, xlast, offset, slash);
 466                 if (p >= 0) {
 467                         final TreeEntry r = contents[p];
 468                         if (slash < s.length-1)
 469                                 return r instanceof Tree ? ((Tree) r).findMember(s, slast, slash + 1)
 470                                                 : null;
 471                         return r;
 472                 }
 473                 return null;
 474         }
 475
 476         /**
 477          * @param s
 478          *            blob name
 479          * @return a {@link TreeEntry} representing an object with the specified
 480          *         relative path.
 481          * @throws IOException
 482          */
 483         public TreeEntry findBlobMember(String s) throws IOException {
 484                 return findMember(s,(byte)0);
 485         }
 486
 487         /**
 488          * @param s Tree Name
 489          * @return a Tree with the name s or null
 490          * @throws IOException
 491          */
 492         public TreeEntry findTreeMember(String s) throws IOException {
 493                 return findMember(s,(byte)'/');
 494         }
 495
 496         public void accept(final TreeVisitor tv, final int flags)
 497                         throws IOException {
 498                 final TreeEntry[] c;
 499
 500                 if ((MODIFIED_ONLY & flags) == MODIFIED_ONLY && !isModified())
 501                         return;
 502
 503                 if ((LOADED_ONLY & flags) == LOADED_ONLY && !isLoaded()) {
 504                         tv.startVisitTree(this);
 505                         tv.endVisitTree(this);
 506                         return;
 507                 }
 508
 509                 ensureLoaded();
 510                 tv.startVisitTree(this);
 511
 512                 if ((CONCURRENT_MODIFICATION & flags) == CONCURRENT_MODIFICATION)
 513                         c = members();
 514                 else
 515                         c = contents;
 516
 517                 for (int k = 0; k < c.length; k++)
 518                         c[k].accept(tv, flags);
 519
 520                 tv.endVisitTree(this);
 521         }
 522
 523         private void ensureLoaded() throws IOException, MissingObjectException {
 524                 if (!isLoaded()) {
 525                         final ObjectLoader or = db.openTree(getId());
 526                         if (or == null)
 527                                 throw new MissingObjectException(getId(), Constants.TYPE_TREE);
 528                         readTree(or.getBytes());
 529                 }
 530         }
 531
 532         private void readTree(final byte[] raw) throws IOException {
 533                 final int rawSize = raw.length;
 534                 int rawPtr = 0;
 535                 TreeEntry[] temp;
 536                 int nextIndex = 0;
 537
 538                 while (rawPtr < rawSize) {
 539                         while (rawPtr < rawSize && raw[rawPtr] != 0)
 540                                 rawPtr++;
 541                         rawPtr++;
 542                         rawPtr += Constants.OBJECT_ID_LENGTH;
 543                         nextIndex++;
 544                 }
 545
 546                 temp = new TreeEntry[nextIndex];
 547                 rawPtr = 0;
 548                 nextIndex = 0;
 549                 while (rawPtr < rawSize) {
 550                         int c = raw[rawPtr++];
 551                         if (c < '0' || c > '7')
 552                                 throw new CorruptObjectException(getId(), "invalid entry mode");
 553                         int mode = c - '0';
 554                         for (;;) {
 555                                 c = raw[rawPtr++];
 556                                 if (' ' == c)
 557                                         break;
 558                                 else if (c < '0' || c > '7')
 559                                         throw new CorruptObjectException(getId(), "invalid mode");
 560                                 mode <<= 3;
 561                                 mode += c - '0';
 562                         }
 563
 564                         int nameLen = 0;
 565                         while (raw[rawPtr + nameLen] != 0)
 566                                 nameLen++;
 567                         final byte[] name = new byte[nameLen];
 568                         System.arraycopy(raw, rawPtr, name, 0, nameLen);
 569                         rawPtr += nameLen + 1;
 570
 571                         final ObjectId id = ObjectId.fromRaw(raw, rawPtr);
 572                         rawPtr += Constants.OBJECT_ID_LENGTH;
 573
 574                         final TreeEntry ent;
 575                         if (FileMode.REGULAR_FILE.equals(mode))
 576                                 ent = new FileTreeEntry(this, id, name, false);
 577                         else if (FileMode.EXECUTABLE_FILE.equals(mode))
 578                                 ent = new FileTreeEntry(this, id, name, true);
 579                         else if (FileMode.TREE.equals(mode)) {
 580                                 ent = new Tree(this, id, name);
 581                         } else if (FileMode.SYMLINK.equals(mode))
 582                                 ent = new SymlinkTreeEntry(this, id, name);
 583                         else
 584                                 throw new CorruptObjectException(getId(), "Invalid mode: "
 585                                                 + Integer.toOctalString(mode));
 586                         temp[nextIndex++] = ent;
 587                 }
 588
 589                 contents = temp;
 590         }
 591
 592         public String toString() {
 593                 final StringBuffer r = new StringBuffer();
 594                 r.append(ObjectId.toString(getId()));
 595                 r.append(" T ");
 596                 r.append(getFullName());
 597                 return r.toString();
 598         }
 599
 600 }