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.ByteArrayOutputStream;
  20 import java.io.IOException;
  21 import java.io.InputStream;
  22 import java.util.Arrays;
  23
  24 import org.spearce.jgit.errors.CorruptObjectException;
  25 import org.spearce.jgit.errors.EntryExistsException;
  26 import org.spearce.jgit.errors.MissingObjectException;
  27
  28 public class Tree extends TreeEntry implements Treeish
  29 {
  30     public static final TreeEntry[] EMPTY_TREE = {};
  31
  32     public static final int compareNames(final byte[] a, final byte[] b)
  33     {
  34         return compareNames(a, b, 0, b.length);
  35     }
  36
  37     public static final int compareNames(
  38         final byte[] a,
  39         final byte[] nameUTF8,
  40         final int nameStart,
  41         final int nameEnd)
  42     {
  43         for (int j = 0, k = nameStart; j < a.length && k < nameEnd; j++, k++)
  44         {
  45             final int aj = a[j] & 0xff;
  46             final int bk = nameUTF8[k] & 0xff;
  47             if (aj < bk)
  48                 return -1;
  49             else if (aj > bk)
  50                 return 1;
  51         }
  52
  53         final int namelength = nameEnd - nameStart;
  54         if (a.length == namelength)
  55             return 0;
  56         else if (a.length < namelength)
  57             return -1;
  58         else
  59             return 1;
  60     }
  61
  62     private static final byte[] substring(
  63         final byte[] s,
  64         final int nameStart,
  65         final int nameEnd)
  66     {
  67         if (nameStart == 0 && nameStart == s.length)
  68         {
  69             return s;
  70         }
  71
  72         final byte[] n = new byte[nameEnd - nameStart];
  73         System.arraycopy(s, nameStart, n, 0, n.length);
  74         return n;
  75     }
  76
  77     private static final int binarySearch(
  78         final TreeEntry[] entries,
  79         final byte[] nameUTF8,
  80         final int nameStart,
  81         final int nameEnd)
  82     {
  83         if (entries.length == 0)
  84             return -1;
  85         int high = entries.length;
  86         int low = 0;
  87         do
  88         {
  89             final int mid = (low + high) / 2;
  90             final int cmp = compareNames(
  91                 entries[mid].getNameUTF8(),
  92                 nameUTF8,
  93                 nameStart,
  94                 nameEnd);
  95             if (cmp < 0)
  96             {
  97                 low = mid + 1;
  98             }
  99             else if (cmp == 0)
 100             {
 101                 return mid;
 102             }
 103             else
 104             {
 105                 high = mid;
 106             }
 107         }
 108         while (low < high);
 109         return -(low + 1);
 110     }
 111
 112     private final Repository db;
 113
 114     private TreeEntry[] contents;
 115
 116     public Tree(final Repository repo)
 117     {
 118         super(null, null, null);
 119         db = repo;
 120         contents = EMPTY_TREE;
 121     }
 122
 123     public Tree(final Repository repo, final ObjectId myId, final InputStream is)
 124         throws IOException
 125     {
 126         super(null, myId, null);
 127         db = repo;
 128         readTree(is);
 129     }
 130
 131     private Tree(final Tree parent, final byte[] nameUTF8)
 132     {
 133         super(parent, null, nameUTF8);
 134         db = parent.getRepository();
 135         contents = EMPTY_TREE;
 136     }
 137
 138     public Tree(final Repository r, final ObjectId id, final byte[] nameUTF8)
 139     {
 140         super(null, id, nameUTF8);
 141         db = r;
 142     }
 143
 144     public Tree(final Tree parent, final ObjectId id, final byte[] nameUTF8)
 145     {
 146         super(parent, id, nameUTF8);
 147         db = parent.getRepository();
 148     }
 149
 150     public FileMode getMode()
 151     {
 152         return FileMode.TREE;
 153     }
 154
 155     public boolean isRoot()
 156     {
 157         return getParent() == null;
 158     }
 159
 160     public Repository getRepository()
 161     {
 162         return db;
 163     }
 164
 165     public final ObjectId getTreeId()
 166     {
 167         return getId();
 168     }
 169
 170     public final Tree getTree()
 171     {
 172         return this;
 173     }
 174
 175     public boolean isLoaded()
 176     {
 177         return contents != null;
 178     }
 179
 180     public void unload()
 181     {
 182         if (isModified())
 183         {
 184             throw new IllegalStateException("Cannot unload a modified tree.");
 185         }
 186         contents = null;
 187     }
 188
 189     public FileTreeEntry addFile(final String name) throws IOException
 190     {
 191         return addFile(name.getBytes(Constants.CHARACTER_ENCODING), 0);
 192     }
 193
 194     public FileTreeEntry addFile(final byte[] s, final int offset)
 195         throws IOException
 196     {
 197         int slash;
 198         int p;
 199
 200         for (slash = offset; slash < s.length && s[slash] != '/'; slash++)
 201             /* search for path component terminator */;
 202
 203         ensureLoaded();
 204         p = binarySearch(contents, s, offset, slash);
 205         if (p >= 0 && slash < s.length && contents[p] instanceof Tree)
 206         {
 207             return ((Tree) contents[p]).addFile(s, slash + 1);
 208         }
 209
 210         final byte[] newName = substring(s, offset, slash);
 211         if (p >= 0)
 212         {
 213             throw new EntryExistsException(new String(
 214                 newName,
 215                 Constants.CHARACTER_ENCODING));
 216         }
 217         else if (slash < s.length)
 218         {
 219             final Tree t = new Tree(this, newName);
 220             insertEntry(p, t);
 221             return t.addFile(s, slash + 1);
 222         }
 223         else
 224         {
 225             final FileTreeEntry f = new FileTreeEntry(
 226                 this,
 227                 null,
 228                 newName,
 229                 false);
 230             insertEntry(p, f);
 231             return f;
 232         }
 233     }
 234
 235     public Tree addTree(final String name) throws IOException
 236     {
 237         return addTree(name.getBytes(Constants.CHARACTER_ENCODING), 0);
 238     }
 239
 240     public Tree addTree(final byte[] s, final int offset) throws IOException
 241     {
 242         int slash;
 243         int p;
 244
 245         for (slash = offset; slash < s.length && s[slash] != '/'; slash++)
 246             /* search for path component terminator */;
 247
 248         ensureLoaded();
 249         p = binarySearch(contents, s, offset, slash);
 250         if (p >= 0 && slash < s.length && contents[p] instanceof Tree)
 251         {
 252             return ((Tree) contents[p]).addTree(s, slash + 1);
 253         }
 254
 255         final byte[] newName = substring(s, offset, slash);
 256         if (p >= 0)
 257         {
 258             throw new EntryExistsException(new String(
 259                 newName,
 260                 Constants.CHARACTER_ENCODING));
 261         }
 262
 263         final Tree t = new Tree(this, newName);
 264         insertEntry(p, t);
 265         return slash == s.length ? t : t.addTree(s, slash + 1);
 266     }
 267
 268     public void addEntry(final TreeEntry e) throws IOException
 269     {
 270         final int p;
 271
 272         ensureLoaded();
 273         p = binarySearch(contents, e.getNameUTF8(), 0, e.getNameUTF8().length);
 274         if (p < 0)
 275         {
 276             e.attachParent(this);
 277             insertEntry(p, e);
 278         }
 279         else
 280         {
 281             throw new EntryExistsException(new String(
 282                 e.getNameUTF8(),
 283                 Constants.CHARACTER_ENCODING));
 284         }
 285     }
 286
 287     private void insertEntry(int p, final TreeEntry e)
 288     {
 289         final TreeEntry[] c = contents;
 290         final TreeEntry[] n = new TreeEntry[c.length + 1];
 291         p = -(p + 1);
 292         for (int k = c.length - 1; k >= p; k--)
 293         {
 294             n[k + 1] = c[k];
 295         }
 296         n[p] = e;
 297         for (int k = p - 1; k >= 0; k--)
 298         {
 299             n[k] = c[k];
 300         }
 301         contents = n;
 302         setModified();
 303     }
 304
 305     void removeEntry(final TreeEntry e)
 306     {
 307         final TreeEntry[] c = contents;
 308         final int p = binarySearch(
 309             c,
 310             e.getNameUTF8(),
 311             0,
 312             e.getNameUTF8().length);
 313         if (p >= 0)
 314         {
 315             final TreeEntry[] n = new TreeEntry[c.length - 1];
 316             for (int k = c.length - 1; k > p; k--)
 317             {
 318                 n[k - 1] = c[k];
 319             }
 320             for (int k = p - 1; k >= 0; k--)
 321             {
 322                 n[k] = c[k];
 323             }
 324             contents = n;
 325             setModified();
 326         }
 327     }
 328
 329     public int memberCount() throws IOException
 330     {
 331         ensureLoaded();
 332         return contents.length;
 333     }
 334
 335     public TreeEntry[] members() throws IOException
 336     {
 337         ensureLoaded();
 338         final TreeEntry[] c = contents;
 339         if (c.length != 0)
 340         {
 341             final TreeEntry[] r = new TreeEntry[c.length];
 342             for (int k = c.length - 1; k >= 0; k--)
 343             {
 344                 r[k] = c[k];
 345             }
 346             return r;
 347         }
 348         else
 349         {
 350             return c;
 351         }
 352     }
 353
 354     public boolean exists(final String s) throws IOException
 355     {
 356         return findMember(s) != null;
 357     }
 358
 359     public TreeEntry findMember(final String s) throws IOException
 360     {
 361         return findMember(s.getBytes(Constants.CHARACTER_ENCODING), 0);
 362     }
 363
 364     public TreeEntry findMember(final byte[] s, final int offset)
 365         throws IOException
 366     {
 367         int slash;
 368         int p;
 369
 370         for (slash = offset; slash < s.length && s[slash] != '/'; slash++)
 371             /* search for path component terminator */;
 372
 373         ensureLoaded();
 374         p = binarySearch(contents, s, offset, slash);
 375         if (p >= 0)
 376         {
 377             final TreeEntry r = contents[p];
 378             if (slash < s.length)
 379             {
 380                 return r instanceof Tree
 381                     ? ((Tree) r).findMember(s, slash + 1)
 382                     : null;
 383             }
 384             return r;
 385         }
 386         return null;
 387     }
 388
 389     public void accept(final TreeVisitor tv, final int flags)
 390         throws IOException
 391     {
 392         final TreeEntry[] c;
 393
 394         if ((MODIFIED_ONLY & flags) == MODIFIED_ONLY && !isModified())
 395         {
 396             return;
 397         }
 398
 399         if ((LOADED_ONLY & flags) == LOADED_ONLY && !isLoaded())
 400         {
 401             tv.startVisitTree(this);
 402             tv.endVisitTree(this);
 403             return;
 404         }
 405
 406         ensureLoaded();
 407         tv.startVisitTree(this);
 408
 409         if ((CONCURRENT_MODIFICATION & flags) == CONCURRENT_MODIFICATION)
 410         {
 411             c = members();
 412         }
 413         else
 414         {
 415             c = contents;
 416         }
 417
 418         for (int k = 0; k < c.length; k++)
 419         {
 420             c[k].accept(tv, flags);
 421         }
 422
 423         tv.endVisitTree(this);
 424     }
 425
 426     private void ensureLoaded() throws IOException, MissingObjectException
 427     {
 428         if (!isLoaded())
 429         {
 430             final ObjectReader or = db.openTree(getId());
 431             if (or == null)
 432             {
 433                 throw new MissingObjectException(getId(), Constants.TYPE_TREE);
 434             }
 435             try
 436             {
 437                 readTree(or.getInputStream());
 438             }
 439             finally
 440             {
 441                 or.close();
 442             }
 443         }
 444     }
 445
 446     private void readTree(final InputStream is) throws IOException
 447     {
 448         TreeEntry[] temp = new TreeEntry[64];
 449         int nextIndex = 0;
 450
 451         for (;;)
 452         {
 453             int c;
 454             int mode;
 455             final ByteArrayOutputStream nameBuf;
 456             final byte[] entId;
 457             final byte[] name;
 458             final ObjectId id;
 459             final TreeEntry ent;
 460             int entIdLen;
 461
 462             c = is.read();
 463             if (c == -1)
 464             {
 465                 break;
 466             }
 467             else if (c < '0' || c > '7')
 468             {
 469                 throw new CorruptObjectException(getId(), "invalid entry mode");
 470             }
 471             mode = c - '0';
 472             for (;;)
 473             {
 474                 c = is.read();
 475                 if (' ' == c)
 476                 {
 477                     break;
 478                 }
 479                 else if (c < '0' || c > '7')
 480                 {
 481                     throw new CorruptObjectException(getId(), "invalid mode");
 482                 }
 483                 mode *= 8;
 484                 mode += c - '0';
 485             }
 486
 487             nameBuf = new ByteArrayOutputStream(128);
 488             for (;;)
 489             {
 490                 c = is.read();
 491                 if (c == -1)
 492                 {
 493                     throw new CorruptObjectException(getId(), "unexpected eof");
 494                 }
 495                 else if (0 == c)
 496                 {
 497                     break;
 498                 }
 499                 nameBuf.write(c);
 500             }
 501
 502             entId = new byte[Constants.OBJECT_ID_LENGTH];
 503             entIdLen = 0;
 504             while ((c = is.read(entId, entIdLen, entId.length - entIdLen)) > 0)
 505             {
 506                 entIdLen += c;
 507             }
 508             if (entIdLen != entId.length)
 509             {
 510                 throw new CorruptObjectException(getId(), "missing hash");
 511             }
 512
 513             id = new ObjectId(entId);
 514             name = nameBuf.toByteArray();
 515
 516             if (FileMode.REGULAR_FILE.equals(mode))
 517             {
 518                 ent = new FileTreeEntry(this, id, name, false);
 519             }
 520             else if (FileMode.EXECUTABLE_FILE.equals(mode))
 521             {
 522                 ent = new FileTreeEntry(this, id, name, true);
 523             }
 524             else if (FileMode.TREE.equals(mode))
 525             {
 526                 ent = new Tree(this, id, name);
 527             }
 528             else if (FileMode.SYMLINK.equals(mode))
 529             {
 530                 ent = new SymlinkTreeEntry(this, id, name);
 531             }
 532             else
 533             {
 534                 throw new CorruptObjectException(getId(), "Invalid mode: "
 535                     + Integer.toOctalString(mode));
 536             }
 537
 538             if (nextIndex == temp.length)
 539             {
 540                 final TreeEntry[] n = new TreeEntry[temp.length << 1];
 541                 for (int k = nextIndex - 1; k >= 0; k--)
 542                 {
 543                     n[k] = temp[k];
 544                 }
 545                 temp = n;
 546             }
 547
 548             temp[nextIndex++] = ent;
 549         }
 550
 551         if (nextIndex == temp.length)
 552         {
 553             contents = temp;
 554         }
 555         else
 556         {
 557             final TreeEntry[] n = new TreeEntry[nextIndex];
 558             for (int k = nextIndex - 1; k >= 0; k--)
 559             {
 560                 n[k] = temp[k];
 561             }
 562             contents = n;
 563         }
 564
 565         // Resort contents using our internal sorting order. GIT sorts
 566         // subtrees as though their names end in '/' but that's not how
 567         // we sort them in memory. Its all the fault of the index...
 568         //
 569         Arrays.sort(contents);
 570     }
 571
 572     public String toString()
 573     {
 574         final StringBuffer r = new StringBuffer();
 575         r.append(ObjectId.toString(getId()));
 576         r.append(" T ");
 577         r.append(getFullName());
 578         return r.toString();
 579     }
 580 }