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

   1 /*
   2  *  Copyright (C) 2006  Shawn Pearce <spearce@spearce.org>
   3  *
   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.
   7  *
   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.
  12  *
  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
  16  */
  17 package org.spearce.jgit.lib;
  18
  19 import java.io.IOException;
  20
  21 import org.spearce.jgit.errors.CorruptObjectException;
  22 import org.spearce.jgit.errors.EntryExistsException;
  23 import org.spearce.jgit.errors.MissingObjectException;
  24
  25 public class Tree extends TreeEntry implements Treeish {
  26         public static final TreeEntry[] EMPTY_TREE = {};
  27
  28         public static final int compareNames(final byte[] a, final byte[] b, final int lasta,final int lastb) {
  29                 return compareNames(a, b, 0, b.length, lasta, lastb);
  30         }
  31
  32         public static final int compareNames(final byte[] a, final byte[] nameUTF8,
  33                         final int nameStart, final int nameEnd, final int lasta, int lastb) {
  34                 int j,k;
  35                 for (j = 0, k = nameStart; j < a.length && k < nameEnd; j++, k++) {
  36                         final int aj = a[j] & 0xff;
  37                         final int bk = nameUTF8[k] & 0xff;
  38                         if (aj < bk)
  39                                 return -1;
  40                         else if (aj > bk)
  41                                 return 1;
  42                 }
  43                 if (j < a.length) {
  44                         int aj = a[j]&0xff;
  45                         if (aj < lastb)
  46                                 return -1;
  47                         else if (aj > lastb)
  48                                 return 1;
  49                         else
  50                                 return 0;
  51                 }
  52                 if (k < nameEnd) {
  53                         int bk = nameUTF8[k] & 0xff;
  54                         if (lasta < bk)
  55                                 return -1;
  56                         else if (lasta > bk)
  57                                 return 1;
  58                         else
  59                                 return 0;
  60                 }
  61                 if (lasta < lastb)
  62                         return -1;
  63                 else if (lasta > lastb)
  64                         return 1;
  65
  66                 final int namelength = nameEnd - nameStart;
  67                 if (a.length == namelength)
  68                         return 0;
  69                 else if (a.length < namelength)
  70                         return -1;
  71                 else
  72                         return 1;
  73         }
  74
  75         private static final byte[] substring(final byte[] s, final int nameStart,
  76                         final int nameEnd) {
  77                 if (nameStart == 0 && nameStart == s.length)
  78                         return s;
  79                 final byte[] n = new byte[nameEnd - nameStart];
  80                 System.arraycopy(s, nameStart, n, 0, n.length);
  81                 return n;
  82         }
  83
  84         private static final int binarySearch(final TreeEntry[] entries,
  85                         final byte[] nameUTF8, final int nameUTF8last, final int nameStart, final int nameEnd) {
  86                 if (entries.length == 0)
  87                         return -1;
  88                 int high = entries.length;
  89                 int low = 0;
  90                 do {
  91                         final int mid = (low + high) / 2;
  92                         final int cmp = compareNames(entries[mid].getNameUTF8(), nameUTF8,
  93                                         nameStart, nameEnd, TreeEntry.lastChar(entries[mid]), nameUTF8last);
  94                         if (cmp < 0)
  95                                 low = mid + 1;
  96                         else if (cmp == 0)
  97                                 return mid;
  98                         else
  99                                 high = mid;
 100                 } while (low < high);
 101                 return -(low + 1);
 102         }
 103
 104         private final Repository db;
 105
 106         private TreeEntry[] contents;
 107
 108         public Tree(final Repository repo) {
 109                 super(null, null, null);
 110                 db = repo;
 111                 contents = EMPTY_TREE;
 112         }
 113
 114         public Tree(final Repository repo, final ObjectId myId, final byte[] raw)
 115                         throws IOException {
 116                 super(null, myId, null);
 117                 db = repo;
 118                 readTree(raw);
 119         }
 120
 121         public Tree(final Tree parent, final byte[] nameUTF8) {
 122                 super(parent, null, nameUTF8);
 123                 db = parent.getRepository();
 124                 contents = EMPTY_TREE;
 125         }
 126
 127         public Tree(final Tree parent, final ObjectId id, final byte[] nameUTF8) {
 128                 super(parent, id, nameUTF8);
 129                 db = parent.getRepository();
 130         }
 131
 132         public FileMode getMode() {
 133                 return FileMode.TREE;
 134         }
 135
 136         public boolean isRoot() {
 137                 return getParent() == null;
 138         }
 139
 140         public Repository getRepository() {
 141                 return db;
 142         }
 143
 144         public final ObjectId getTreeId() {
 145                 return getId();
 146         }
 147
 148         public final Tree getTree() {
 149                 return this;
 150         }
 151
 152         public boolean isLoaded() {
 153                 return contents != null;
 154         }
 155
 156         public void unload() {
 157                 if (isModified())
 158                         throw new IllegalStateException("Cannot unload a modified tree.");
 159                 contents = null;
 160         }
 161
 162         public FileTreeEntry addFile(final String name) throws IOException {
 163                 return addFile(Repository.gitInternalSlash(name.getBytes(Constants.CHARACTER_ENCODING)), 0);
 164         }
 165
 166         public FileTreeEntry addFile(final byte[] s, final int offset)
 167                         throws IOException {
 168                 int slash;
 169                 int p;
 170
 171                 for (slash = offset; slash < s.length && s[slash] != '/'; slash++) {
 172                         // search for path component terminator
 173                 }
 174
 175                 ensureLoaded();
 176                 byte xlast = slash<s.length ? (byte)'/' : 0;
 177                 p = binarySearch(contents, s, xlast, offset, slash);
 178                 if (p >= 0 && slash < s.length && contents[p] instanceof Tree)
 179                         return ((Tree) contents[p]).addFile(s, slash + 1);
 180
 181                 final byte[] newName = substring(s, offset, slash);
 182                 if (p >= 0)
 183                         throw new EntryExistsException(new String(newName,
 184                                         Constants.CHARACTER_ENCODING));
 185                 else if (slash < s.length) {
 186                         final Tree t = new Tree(this, newName);
 187                         insertEntry(p, t);
 188                         return t.addFile(s, slash + 1);
 189                 } else {
 190                         final FileTreeEntry f = new FileTreeEntry(this, null, newName,
 191                                         false);
 192                         insertEntry(p, f);
 193                         return f;
 194                 }
 195         }
 196
 197         public Tree addTree(final String name) throws IOException {
 198                 return addTree(Repository.gitInternalSlash(name.getBytes(Constants.CHARACTER_ENCODING)), 0);
 199         }
 200
 201         public Tree addTree(final byte[] s, final int offset) throws IOException {
 202                 int slash;
 203                 int p;
 204
 205                 for (slash = offset; slash < s.length && s[slash] != '/'; slash++) {
 206                         // search for path component terminator
 207                 }
 208
 209                 ensureLoaded();
 210                 p = binarySearch(contents, s, (byte)'/', offset, slash);
 211                 if (p >= 0 && slash < s.length && contents[p] instanceof Tree)
 212                         return ((Tree) contents[p]).addTree(s, slash + 1);
 213
 214                 final byte[] newName = substring(s, offset, slash);
 215                 if (p >= 0)
 216                         throw new EntryExistsException(new String(newName,
 217                                         Constants.CHARACTER_ENCODING));
 218
 219                 final Tree t = new Tree(this, newName);
 220                 insertEntry(p, t);
 221                 return slash == s.length ? t : t.addTree(s, slash + 1);
 222         }
 223
 224         public void addEntry(final TreeEntry e) throws IOException {
 225                 final int p;
 226
 227                 ensureLoaded();
 228                 p = binarySearch(contents, e.getNameUTF8(), TreeEntry.lastChar(e), 0, e.getNameUTF8().length);
 229                 if (p < 0) {
 230                         e.attachParent(this);
 231                         insertEntry(p, e);
 232                 } else {
 233                         throw new EntryExistsException(new String(e.getNameUTF8(),
 234                                         Constants.CHARACTER_ENCODING));
 235                 }
 236         }
 237
 238         private void insertEntry(int p, final TreeEntry e) {
 239                 final TreeEntry[] c = contents;
 240                 final TreeEntry[] n = new TreeEntry[c.length + 1];
 241                 p = -(p + 1);
 242                 for (int k = c.length - 1; k >= p; k--)
 243                         n[k + 1] = c[k];
 244                 n[p] = e;
 245                 for (int k = p - 1; k >= 0; k--)
 246                         n[k] = c[k];
 247                 contents = n;
 248                 setModified();
 249         }
 250
 251         void removeEntry(final TreeEntry e) {
 252                 final TreeEntry[] c = contents;
 253                 final int p = binarySearch(c, e.getNameUTF8(), TreeEntry.lastChar(e), 0,
 254                                 e.getNameUTF8().length);
 255                 if (p >= 0) {
 256                         final TreeEntry[] n = new TreeEntry[c.length - 1];
 257                         for (int k = c.length - 1; k > p; k--)
 258                                 n[k - 1] = c[k];
 259                         for (int k = p - 1; k >= 0; k--)
 260                                 n[k] = c[k];
 261                         contents = n;
 262                         setModified();
 263                 }
 264         }
 265
 266         public int memberCount() throws IOException {
 267                 ensureLoaded();
 268                 return contents.length;
 269         }
 270
 271         public TreeEntry[] members() throws IOException {
 272                 ensureLoaded();
 273                 final TreeEntry[] c = contents;
 274                 if (c.length != 0) {
 275                         final TreeEntry[] r = new TreeEntry[c.length];
 276                         for (int k = c.length - 1; k >= 0; k--)
 277                                 r[k] = c[k];
 278                         return r;
 279                 } else
 280                         return c;
 281         }
 282
 283         public boolean exists(final String s, byte slast) throws IOException {
 284                 return findMember(s, slast) != null;
 285         }
 286
 287         public boolean existsTree(String path) throws IOException {
 288                 return exists(path,(byte)'/');
 289         }
 290
 291         public boolean existsBlob(String path) throws IOException {
 292                 return exists(path,(byte)0);
 293         }
 294
 295         public TreeEntry findMember(final String s, byte slast) throws IOException {
 296                 return findMember(Repository.gitInternalSlash(s.getBytes(Constants.CHARACTER_ENCODING)), slast, 0);
 297         }
 298
 299         public TreeEntry findMember(final byte[] s, final byte slast, final int offset)
 300                         throws IOException {
 301                 int slash;
 302                 int p;
 303
 304                 for (slash = offset; slash < s.length && s[slash] != '/'; slash++) {
 305                         // search for path component terminator
 306                 }
 307
 308                 ensureLoaded();
 309                 byte xlast = slash<s.length ? (byte)'/' : slast;
 310                 p = binarySearch(contents, s, xlast, offset, slash);
 311                 if (p >= 0) {
 312                         final TreeEntry r = contents[p];
 313                         if (slash < s.length-1)
 314                                 return r instanceof Tree ? ((Tree) r).findMember(s, slast, slash + 1)
 315                                                 : null;
 316                         return r;
 317                 }
 318                 return null;
 319         }
 320
 321         public TreeEntry findBlobMember(String s) throws IOException {
 322                 return findMember(s,(byte)0);
 323         }
 324
 325         public TreeEntry findTreeMember(String s) throws IOException {
 326                 return findMember(s,(byte)'/');
 327         }
 328
 329         public void accept(final TreeVisitor tv, final int flags)
 330                         throws IOException {
 331                 final TreeEntry[] c;
 332
 333                 if ((MODIFIED_ONLY & flags) == MODIFIED_ONLY && !isModified())
 334                         return;
 335
 336                 if ((LOADED_ONLY & flags) == LOADED_ONLY && !isLoaded()) {
 337                         tv.startVisitTree(this);
 338                         tv.endVisitTree(this);
 339                         return;
 340                 }
 341
 342                 ensureLoaded();
 343                 tv.startVisitTree(this);
 344
 345                 if ((CONCURRENT_MODIFICATION & flags) == CONCURRENT_MODIFICATION)
 346                         c = members();
 347                 else
 348                         c = contents;
 349
 350                 for (int k = 0; k < c.length; k++)
 351                         c[k].accept(tv, flags);
 352
 353                 tv.endVisitTree(this);
 354         }
 355
 356         private void ensureLoaded() throws IOException, MissingObjectException {
 357                 if (!isLoaded()) {
 358                         final ObjectLoader or = db.openTree(getId());
 359                         if (or == null)
 360                                 throw new MissingObjectException(getId(), Constants.TYPE_TREE);
 361                         readTree(or.getBytes());
 362                 }
 363         }
 364
 365         private void readTree(final byte[] raw) throws IOException {
 366                 int rawPtr = 0;
 367                 TreeEntry[] temp = new TreeEntry[64];
 368                 int nextIndex = 0;
 369
 370                 while (rawPtr < raw.length) {
 371                         int c = raw[rawPtr++] & 0xff;
 372                         if (c < '0' || c > '7')
 373                                 throw new CorruptObjectException(getId(), "invalid entry mode");
 374                         int mode = c - '0';
 375                         for (;;) {
 376                                 c = raw[rawPtr++] & 0xff;
 377                                 if (' ' == c)
 378                                         break;
 379                                 else if (c < '0' || c > '7')
 380                                         throw new CorruptObjectException(getId(), "invalid mode");
 381                                 mode <<= 3;
 382                                 mode += c - '0';
 383                         }
 384
 385                         int nameLen = 0;
 386                         while ((raw[rawPtr + nameLen] & 0xff) != 0)
 387                                 nameLen++;
 388                         final byte[] name = new byte[nameLen];
 389                         System.arraycopy(raw, rawPtr, name, 0, nameLen);
 390                         rawPtr += nameLen + 1;
 391
 392                         final byte[] entId = new byte[Constants.OBJECT_ID_LENGTH];
 393                         System.arraycopy(raw, rawPtr, entId, 0, Constants.OBJECT_ID_LENGTH);
 394                         final ObjectId id = new ObjectId(entId);
 395                         rawPtr += Constants.OBJECT_ID_LENGTH;
 396
 397                         final TreeEntry ent;
 398                         if (FileMode.REGULAR_FILE.equals(mode))
 399                                 ent = new FileTreeEntry(this, id, name, false);
 400                         else if (FileMode.EXECUTABLE_FILE.equals(mode))
 401                                 ent = new FileTreeEntry(this, id, name, true);
 402                         else if (FileMode.TREE.equals(mode)) {
 403                                 ent = new Tree(this, id, name);
 404                         } else if (FileMode.SYMLINK.equals(mode))
 405                                 ent = new SymlinkTreeEntry(this, id, name);
 406                         else
 407                                 throw new CorruptObjectException(getId(), "Invalid mode: "
 408                                                 + Integer.toOctalString(mode));
 409
 410                         if (nextIndex == temp.length) {
 411                                 final TreeEntry[] n = new TreeEntry[temp.length << 1];
 412                                 for (int k = nextIndex - 1; k >= 0; k--)
 413                                         n[k] = temp[k];
 414                                 temp = n;
 415                         }
 416
 417                         temp[nextIndex++] = ent;
 418                 }
 419
 420                 if (nextIndex == temp.length)
 421                         contents = temp;
 422                 else {
 423                         final TreeEntry[] n = new TreeEntry[nextIndex];
 424                         for (int k = nextIndex - 1; k >= 0; k--)
 425                                 n[k] = temp[k];
 426                         contents = n;
 427                 }
 428
 429         }
 430
 431         public String toString() {
 432                 final StringBuffer r = new StringBuffer();
 433                 r.append(ObjectId.toString(getId()));
 434                 r.append(" T ");
 435                 r.append(getFullName());
 436                 return r.toString();
 437         }
 438
 439 }