/*
* Copyright (C) 2007, Robin Rosenberg <me@lathund.dewire.com>
* Copyright (C) 2007-2008, Robin Rosenberg <robin.rosenberg@dewire.com>
* Copyright (C) 2006-2008, Shawn O. Pearce <spearce@spearce.org>
* and other copyright owners as documented in the project's IP log.
*
* This program and the accompanying materials are made available
* under the terms of the Eclipse Distribution License v1.0 which
* accompanies this distribution, is reproduced below, and is
* available at http://www.eclipse.org/org/documents/edl-v10.php
*
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or
* without modification, are permitted provided that the following
* conditions are met:
*
* - Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* - Redistributions in binary form must reproduce the above
* copyright notice, this list of conditions and the following
* disclaimer in the documentation and/or other materials provided
* with the distribution.
*
* - Neither the name of the Eclipse Foundation, Inc. nor the
* names of its contributors may be used to endorse or promote
* products derived from this software without specific prior
* written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
* CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
* INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
* CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
* STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
* ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
package org.eclipse.jgit.lib;
import java.io.IOException;
import java.text.MessageFormat;
import org.eclipse.jgit.JGitText;
import org.eclipse.jgit.errors.CorruptObjectException;
import org.eclipse.jgit.errors.EntryExistsException;
import org.eclipse.jgit.errors.MissingObjectException;
import org.eclipse.jgit.errors.ObjectWritingException;
import org.eclipse.jgit.util.RawParseUtils;
/**
* A representation of a Git tree entry. A Tree is a directory in Git.
*
* @deprecated To look up information about a single path, use
* {@link org.eclipse.jgit.treewalk.TreeWalk#forPath(Repository, String, org.eclipse.jgit.revwalk.RevTree)}.
* To lookup information about multiple paths at once, use a
* {@link org.eclipse.jgit.treewalk.TreeWalk} and obtain the current entry's
* information from its getter methods.
*/
@Deprecated
public class Tree extends TreeEntry {
private static final TreeEntry[] EMPTY_TREE = {};
/**
* Compare two names represented as bytes. Since git treats names of trees and
* blobs differently we have one parameter that represents a '/' for trees. For
* other objects the value should be NUL. The names are compare by their positive
* byte value (0..255).
*
* A blob and a tree with the same name will not compare equal.
*
* @param a name
* @param b name
* @param lasta '/' if a is a tree, else NUL
* @param lastb '/' if b is a tree, else NUL
*
* @return < 0 if a is sorted before b, 0 if they are the same, else b
*/
public static final int compareNames(final byte[] a, final byte[] b, final int lasta,final int lastb) {
return compareNames(a, b, 0, b.length, lasta, lastb);
}
private static final int compareNames(final byte[] a, final byte[] nameUTF8,
final int nameStart, final int nameEnd, final int lasta, int lastb) {
int j,k;
for (j = 0, k = nameStart; j < a.length && k < nameEnd; j++, k++) {
final int aj = a[j] & 0xff;
final int bk = nameUTF8[k] & 0xff;
if (aj < bk)
return -1;
else if (aj > bk)
return 1;
}
if (j < a.length) {
int aj = a[j]&0xff;
if (aj < lastb)
return -1;
else if (aj > lastb)
return 1;
else
if (j == a.length - 1)
return 0;
else
return -1;
}
if (k < nameEnd) {
int bk = nameUTF8[k] & 0xff;
if (lasta < bk)
return -1;
else if (lasta > bk)
return 1;
else
if (k == nameEnd - 1)
return 0;
else
return 1;
}
if (lasta < lastb)
return -1;
else if (lasta > lastb)
return 1;
final int namelength = nameEnd - nameStart;
if (a.length == namelength)
return 0;
else if (a.length < namelength)
return -1;
else
return 1;
}
private static final byte[] substring(final byte[] s, final int nameStart,
final int nameEnd) {
if (nameStart == 0 && nameStart == s.length)
return s;
final byte[] n = new byte[nameEnd - nameStart];
System.arraycopy(s, nameStart, n, 0, n.length);
return n;
}
private static final int binarySearch(final TreeEntry[] entries,
final byte[] nameUTF8, final int nameUTF8last, final int nameStart, final int nameEnd) {
if (entries.length == 0)
return -1;
int high = entries.length;
int low = 0;
do {
final int mid = (low + high) >>> 1;
final int cmp = compareNames(entries[mid].getNameUTF8(), nameUTF8,
nameStart, nameEnd, TreeEntry.lastChar(entries[mid]), nameUTF8last);
if (cmp < 0)
low = mid + 1;
else if (cmp == 0)
return mid;
else
high = mid;
} while (low < high);
return -(low + 1);
}
private final Repository db;
private TreeEntry[] contents;
/**
* Constructor for a new Tree
*
* @param repo The repository that owns the Tree.
*/
public Tree(final Repository repo) {
super(null, null, null);
db = repo;
contents = EMPTY_TREE;
}
/**
* Construct a Tree object with known content and hash value
*
* @param repo
* @param myId
* @param raw
* @throws IOException
*/
public Tree(final Repository repo, final ObjectId myId, final byte[] raw)
throws IOException {
super(null, myId, null);
db = repo;
readTree(raw);
}
/**
* Construct a new Tree under another Tree
*
* @param parent
* @param nameUTF8
*/
public Tree(final Tree parent, final byte[] nameUTF8) {
super(parent, null, nameUTF8);
db = parent.getRepository();
contents = EMPTY_TREE;
}
/**
* Construct a Tree with a known SHA-1 under another tree. Data is not yet
* specified and will have to be loaded on demand.
*
* @param parent
* @param id
* @param nameUTF8
*/
public Tree(final Tree parent, final ObjectId id, final byte[] nameUTF8) {
super(parent, id, nameUTF8);
db = parent.getRepository();
}
public FileMode getMode() {
return FileMode.TREE;
}
/**
* @return true if this Tree is the top level Tree.
*/
public boolean isRoot() {
return getParent() == null;
}
public Repository getRepository() {
return db;
}
/**
* @return true of the data of this Tree is loaded
*/
public boolean isLoaded() {
return contents != null;
}
/**
* Forget the in-memory data for this tree.
*/
public void unload() {
if (isModified())
throw new IllegalStateException(JGitText.get().cannotUnloadAModifiedTree);
contents = null;
}
/**
* Adds a new or existing file with the specified name to this tree.
* Trees are added if necessary as the name may contain '/':s.
*
* @param name Name
* @return a {@link FileTreeEntry} for the added file.
* @throws IOException
*/
public FileTreeEntry addFile(final String name) throws IOException {
return addFile(Repository.gitInternalSlash(Constants.encode(name)), 0);
}
/**
* Adds a new or existing file with the specified name to this tree.
* Trees are added if necessary as the name may contain '/':s.
*
* @param s an array containing the name
* @param offset when the name starts in the tree.
*
* @return a {@link FileTreeEntry} for the added file.
* @throws IOException
*/
public FileTreeEntry addFile(final byte[] s, final int offset)
throws IOException {
int slash;
int p;
for (slash = offset; slash < s.length && s[slash] != '/'; slash++) {
// search for path component terminator
}
ensureLoaded();
byte xlast = slash<s.length ? (byte)'/' : 0;
p = binarySearch(contents, s, xlast, offset, slash);
if (p >= 0 && slash < s.length && contents[p] instanceof Tree)
return ((Tree) contents[p]).addFile(s, slash + 1);
final byte[] newName = substring(s, offset, slash);
if (p >= 0)
throw new EntryExistsException(RawParseUtils.decode(newName));
else if (slash < s.length) {
final Tree t = new Tree(this, newName);
insertEntry(p, t);
return t.addFile(s, slash + 1);
} else {
final FileTreeEntry f = new FileTreeEntry(this, null, newName,
false);
insertEntry(p, f);
return f;
}
}
/**
* Adds a new or existing Tree with the specified name to this tree.
* Trees are added if necessary as the name may contain '/':s.
*
* @param name Name
* @return a {@link FileTreeEntry} for the added tree.
* @throws IOException
*/
public Tree addTree(final String name) throws IOException {
return addTree(Repository.gitInternalSlash(Constants.encode(name)), 0);
}
/**
* Adds a new or existing Tree with the specified name to this tree.
* Trees are added if necessary as the name may contain '/':s.
*
* @param s an array containing the name
* @param offset when the name starts in the tree.
*
* @return a {@link FileTreeEntry} for the added tree.
* @throws IOException
*/
public Tree addTree(final byte[] s, final int offset) throws IOException {
int slash;
int p;
for (slash = offset; slash < s.length && s[slash] != '/'; slash++) {
// search for path component terminator
}
ensureLoaded();
p = binarySearch(contents, s, (byte)'/', offset, slash);
if (p >= 0 && slash < s.length && contents[p] instanceof Tree)
return ((Tree) contents[p]).addTree(s, slash + 1);
final byte[] newName = substring(s, offset, slash);
if (p >= 0)
throw new EntryExistsException(RawParseUtils.decode(newName));
final Tree t = new Tree(this, newName);
insertEntry(p, t);
return slash == s.length ? t : t.addTree(s, slash + 1);
}
/**
* Add the specified tree entry to this tree.
*
* @param e
* @throws IOException
*/
public void addEntry(final TreeEntry e) throws IOException {
final int p;
ensureLoaded();
p = binarySearch(contents, e.getNameUTF8(), TreeEntry.lastChar(e), 0, e.getNameUTF8().length);
if (p < 0) {
e.attachParent(this);
insertEntry(p, e);
} else {
throw new EntryExistsException(e.getName());
}
}
private void insertEntry(int p, final TreeEntry e) {
final TreeEntry[] c = contents;
final TreeEntry[] n = new TreeEntry[c.length + 1];
p = -(p + 1);
for (int k = c.length - 1; k >= p; k--)
n[k + 1] = c[k];
n[p] = e;
for (int k = p - 1; k >= 0; k--)
n[k] = c[k];
contents = n;
setModified();
}
void removeEntry(final TreeEntry e) {
final TreeEntry[] c = contents;
final int p = binarySearch(c, e.getNameUTF8(), TreeEntry.lastChar(e), 0,
e.getNameUTF8().length);
if (p >= 0) {
final TreeEntry[] n = new TreeEntry[c.length - 1];
for (int k = c.length - 1; k > p; k--)
n[k - 1] = c[k];
for (int k = p - 1; k >= 0; k--)
n[k] = c[k];
contents = n;
setModified();
}
}
/**
* @return number of members in this tree
* @throws IOException
*/
public int memberCount() throws IOException {
ensureLoaded();
return contents.length;
}
/**
* Return all members of the tree sorted in Git order.
*
* Entries are sorted by the numerical unsigned byte
* values with (sub)trees having an implicit '/'. An
* example of a tree with three entries. a:b is an
* actual file name here.
*
* <p>
* 100644 blob e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 a.b
* 040000 tree 4277b6e69d25e5efa77c455340557b384a4c018a a
* 100644 blob e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 a:b
*
* @return all entries in this Tree, sorted.
* @throws IOException
*/
public TreeEntry[] members() throws IOException {
ensureLoaded();
final TreeEntry[] c = contents;
if (c.length != 0) {
final TreeEntry[] r = new TreeEntry[c.length];
for (int k = c.length - 1; k >= 0; k--)
r[k] = c[k];
return r;
} else
return c;
}
private boolean exists(final String s, byte slast) throws IOException {
return findMember(s, slast) != null;
}
/**
* @param path to the tree.
* @return true if a tree with the specified path can be found under this
* tree.
* @throws IOException
*/
public boolean existsTree(String path) throws IOException {
return exists(path,(byte)'/');
}
/**
* @param path of the non-tree entry.
* @return true if a blob, symlink, or gitlink with the specified name
* can be found under this tree.
* @throws IOException
*/
public boolean existsBlob(String path) throws IOException {
return exists(path,(byte)0);
}
private TreeEntry findMember(final String s, byte slast) throws IOException {
return findMember(Repository.gitInternalSlash(Constants.encode(s)), slast, 0);
}
private TreeEntry findMember(final byte[] s, final byte slast, final int offset)
throws IOException {
int slash;
int p;
for (slash = offset; slash < s.length && s[slash] != '/'; slash++) {
// search for path component terminator
}
ensureLoaded();
byte xlast = slash<s.length ? (byte)'/' : slast;
p = binarySearch(contents, s, xlast, offset, slash);
if (p >= 0) {
final TreeEntry r = contents[p];
if (slash < s.length-1)
return r instanceof Tree ? ((Tree) r).findMember(s, slast, slash + 1)
: null;
return r;
}
return null;
}
/**
* @param s
* blob name
* @return a {@link TreeEntry} representing an object with the specified
* relative path.
* @throws IOException
*/
public TreeEntry findBlobMember(String s) throws IOException {
return findMember(s,(byte)0);
}
/**
* @param s Tree Name
* @return a Tree with the name s or null
* @throws IOException
*/
public TreeEntry findTreeMember(String s) throws IOException {
return findMember(s,(byte)'/');
}
private void ensureLoaded() throws IOException, MissingObjectException {
if (!isLoaded()) {
ObjectLoader ldr = db.open(getId(), Constants.OBJ_TREE);
readTree(ldr.getCachedBytes());
}
}
private void readTree(final byte[] raw) throws IOException {
final int rawSize = raw.length;
int rawPtr = 0;
TreeEntry[] temp;
int nextIndex = 0;
while (rawPtr < rawSize) {
while (rawPtr < rawSize && raw[rawPtr] != 0)
rawPtr++;
rawPtr++;
rawPtr += Constants.OBJECT_ID_LENGTH;
nextIndex++;
}
temp = new TreeEntry[nextIndex];
rawPtr = 0;
nextIndex = 0;
while (rawPtr < rawSize) {
int c = raw[rawPtr++];
if (c < '0' || c > '7')
throw new CorruptObjectException(getId(), JGitText.get().corruptObjectInvalidEntryMode);
int mode = c - '0';
for (;;) {
c = raw[rawPtr++];
if (' ' == c)
break;
else if (c < '0' || c > '7')
throw new CorruptObjectException(getId(), JGitText.get().corruptObjectInvalidMode);
mode <<= 3;
mode += c - '0';
}
int nameLen = 0;
while (raw[rawPtr + nameLen] != 0)
nameLen++;
final byte[] name = new byte[nameLen];
System.arraycopy(raw, rawPtr, name, 0, nameLen);
rawPtr += nameLen + 1;
final ObjectId id = ObjectId.fromRaw(raw, rawPtr);
rawPtr += Constants.OBJECT_ID_LENGTH;
final TreeEntry ent;
if (FileMode.REGULAR_FILE.equals(mode))
ent = new FileTreeEntry(this, id, name, false);
else if (FileMode.EXECUTABLE_FILE.equals(mode))
ent = new FileTreeEntry(this, id, name, true);
else if (FileMode.TREE.equals(mode))
ent = new Tree(this, id, name);
else if (FileMode.SYMLINK.equals(mode))
ent = new SymlinkTreeEntry(this, id, name);
else if (FileMode.GITLINK.equals(mode))
ent = new GitlinkTreeEntry(this, id, name);
else
throw new CorruptObjectException(getId(), MessageFormat.format(
JGitText.get().corruptObjectInvalidMode2, Integer.toOctalString(mode)));
temp[nextIndex++] = ent;
}
contents = temp;
}
/**
* Format this Tree in canonical format.
*
* @return canonical encoding of the tree object.
* @throws IOException
* the tree cannot be loaded, or its not in a writable state.
*/
public byte[] format() throws IOException {
TreeFormatter fmt = new TreeFormatter();
for (TreeEntry e : members()) {
ObjectId id = e.getId();
if (id == null)
throw new ObjectWritingException(MessageFormat.format(JGitText
.get().objectAtPathDoesNotHaveId, e.getFullName()));
fmt.append(e.getNameUTF8(), e.getMode(), id);
}
return fmt.toByteArray();
}
public String toString() {
final StringBuilder r = new StringBuilder();
r.append(ObjectId.toString(getId()));
r.append(" T ");
r.append(getFullName());
return r.toString();
}
}
