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