diff options
Diffstat (limited to 'org.eclipse.jgit')
9 files changed, 1878 insertions, 0 deletions
diff --git a/org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties b/org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties index b91b18083a..bf2a4a2e0f 100644 --- a/org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties +++ b/org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties @@ -368,6 +368,9 @@ invalidPathReservedOnWindows=Invalid path (''{0}'' is reserved on Windows): {1} invalidRedirectLocation=Redirect or URI ''{0}'': invalid redirect location {1} -> {2} invalidReflogRevision=Invalid reflog revision: {0} invalidRefName=Invalid ref name: {0} +invalidReftableBlock=Invalid reftable block +invalidReftableCRC=Invalid reftable CRC-32 +invalidReftableFile=Invalid reftable file invalidRemote=Invalid remote: {0} invalidRepositoryStateNoHead=Invalid repository --- cannot read HEAD invalidShallowObject=invalid shallow object {0}, expected commit @@ -702,6 +705,7 @@ unsupportedMark=Mark not supported unsupportedOperationNotAddAtEnd=Not add-at-end: {0} unsupportedPackIndexVersion=Unsupported pack index version {0} unsupportedPackVersion=Unsupported pack version {0}. +unsupportedReftableVersion=Unsupported reftable version {0}. unsupportedRepositoryDescription=Repository description not supported updateRequiresOldIdAndNewId=Update requires both old ID and new ID to be nonzero updatingHeadFailed=Updating HEAD failed diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/JGitText.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/JGitText.java index e4d7e7f6e2..07666eb934 100644 --- a/org.eclipse.jgit/src/org/eclipse/jgit/internal/JGitText.java +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/JGitText.java @@ -427,6 +427,9 @@ public class JGitText extends TranslationBundle { /***/ public String invalidRedirectLocation; /***/ public String invalidReflogRevision; /***/ public String invalidRefName; + /***/ public String invalidReftableBlock; + /***/ public String invalidReftableCRC; + /***/ public String invalidReftableFile; /***/ public String invalidRemote; /***/ public String invalidShallowObject; /***/ public String invalidStageForPath; @@ -761,6 +764,7 @@ public class JGitText extends TranslationBundle { /***/ public String unsupportedOperationNotAddAtEnd; /***/ public String unsupportedPackIndexVersion; /***/ public String unsupportedPackVersion; + /***/ public String unsupportedReftableVersion; /***/ public String unsupportedRepositoryDescription; /***/ public String updateRequiresOldIdAndNewId; /***/ public String updatingHeadFailed; diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/io/BlockSource.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/io/BlockSource.java new file mode 100644 index 0000000000..0a5f9c1a72 --- /dev/null +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/io/BlockSource.java @@ -0,0 +1,185 @@ +/* + * Copyright (C) 2017, Google Inc. + * 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.internal.storage.io; + +import java.io.FileInputStream; +import java.io.IOException; +import java.nio.ByteBuffer; +import java.nio.channels.FileChannel; + +/** + * Provides content blocks of file. + * <p> + * {@code BlockSource} implementations must decide if they will be thread-safe, + * or not. + */ +public abstract class BlockSource implements AutoCloseable { + /** + * Wrap a byte array as a {@code BlockSource}. + * + * @param content + * input file. + * @return block source to read from {@code content}. + */ + public static BlockSource from(byte[] content) { + return new BlockSource() { + @Override + public ByteBuffer read(long pos, int cnt) { + ByteBuffer buf = ByteBuffer.allocate(cnt); + if (pos < content.length) { + int p = (int) pos; + int n = Math.min(cnt, content.length - p); + buf.put(content, p, n); + } + return buf; + } + + @Override + public long size() { + return content.length; + } + + @Override + public void close() { + // Do nothing. + } + }; + } + + /** + * Read from a {@code FileInputStream}. + * <p> + * The returned {@code BlockSource} is not thread-safe, as it must seek the + * file channel to read a block. + * + * @param in + * the file. The {@code BlockSource} will close {@code in}. + * @return wrapper for {@code in}. + */ + public static BlockSource from(FileInputStream in) { + return from(in.getChannel()); + } + + /** + * Read from a {@code FileChannel}. + * <p> + * The returned {@code BlockSource} is not thread-safe, as it must seek the + * file channel to read a block. + * + * @param ch + * the file. The {@code BlockSource} will close {@code ch}. + * @return wrapper for {@code ch}. + */ + public static BlockSource from(FileChannel ch) { + return new BlockSource() { + @Override + public ByteBuffer read(long pos, int blockSize) throws IOException { + ByteBuffer b = ByteBuffer.allocate(blockSize); + ch.position(pos); + int n; + do { + n = ch.read(b); + } while (n > 0 && b.position() < blockSize); + return b; + } + + @Override + public long size() throws IOException { + return ch.size(); + } + + @Override + public void close() { + try { + ch.close(); + } catch (IOException e) { + // Ignore close failures of read-only files. + } + } + }; + } + + /** + * Read a block from the file. + * <p> + * To reduce copying, the returned ByteBuffer should have an accessible + * array and {@code arrayOffset() == 0}. The caller will discard the + * ByteBuffer and directly use the backing array. + * + * @param position + * position of the block in the file, specified in bytes from the + * beginning of the file. + * @param blockSize + * size to read. + * @return buffer containing the block content. + * @throws IOException + * if block cannot be read. + */ + public abstract ByteBuffer read(long position, int blockSize) + throws IOException; + + /** + * Determine the size of the file. + * + * @return total number of bytes in the file. + * @throws IOException + * if size cannot be obtained. + */ + public abstract long size() throws IOException; + + /** + * Advise the {@code BlockSource} a sequential scan is starting. + * + * @param startPos + * starting position. + * @param endPos + * ending position. + */ + public void adviseSequentialRead(long startPos, long endPos) { + // Do nothing by default. + } + + @Override + public abstract void close(); +} diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/BlockReader.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/BlockReader.java new file mode 100644 index 0000000000..a92bedcebd --- /dev/null +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/BlockReader.java @@ -0,0 +1,584 @@ +/* + * Copyright (C) 2017, Google Inc. + * 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.internal.storage.reftable; + +import static java.nio.charset.StandardCharsets.UTF_8; +import static org.eclipse.jgit.internal.storage.reftable.BlockWriter.compare; +import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.FILE_BLOCK_TYPE; +import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.FILE_HEADER_LEN; +import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.INDEX_BLOCK_TYPE; +import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.LOG_BLOCK_TYPE; +import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.LOG_DATA; +import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.LOG_NONE; +import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.OBJ_BLOCK_TYPE; +import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.REF_BLOCK_TYPE; +import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.VALUE_1ID; +import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.VALUE_2ID; +import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.VALUE_NONE; +import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.VALUE_SYMREF; +import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.VALUE_TYPE_MASK; +import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.reverseUpdateIndex; +import static org.eclipse.jgit.lib.Constants.OBJECT_ID_LENGTH; +import static org.eclipse.jgit.lib.Ref.Storage.NEW; +import static org.eclipse.jgit.lib.Ref.Storage.PACKED; + +import java.io.IOException; +import java.nio.ByteBuffer; +import java.util.Arrays; +import java.util.zip.DataFormatException; +import java.util.zip.Inflater; + +import org.eclipse.jgit.annotations.Nullable; +import org.eclipse.jgit.internal.JGitText; +import org.eclipse.jgit.internal.storage.io.BlockSource; +import org.eclipse.jgit.lib.CheckoutEntry; +import org.eclipse.jgit.lib.InflaterCache; +import org.eclipse.jgit.lib.ObjectId; +import org.eclipse.jgit.lib.ObjectIdRef; +import org.eclipse.jgit.lib.PersonIdent; +import org.eclipse.jgit.lib.Ref; +import org.eclipse.jgit.lib.ReflogEntry; +import org.eclipse.jgit.lib.SymbolicRef; +import org.eclipse.jgit.util.LongList; +import org.eclipse.jgit.util.NB; +import org.eclipse.jgit.util.RawParseUtils; + +/** Reads a single block for {@link ReftableReader}. */ +class BlockReader { + private byte blockType; + private long endPosition; + private boolean truncated; + + private byte[] buf; + private int bufLen; + private int ptr; + + private int keysStart; + private int keysEnd; + + private int restartCnt; + private int restartTbl; + + private byte[] nameBuf = new byte[256]; + private int nameLen; + private int valueType; + + byte type() { + return blockType; + } + + boolean truncated() { + return truncated; + } + + long endPosition() { + return endPosition; + } + + boolean next() { + return ptr < keysEnd; + } + + void parseKey() { + int pfx = readVarint32(); + valueType = readVarint32(); + int sfx = valueType >>> 3; + if (pfx + sfx > nameBuf.length) { + int n = Math.max(pfx + sfx, nameBuf.length * 2); + nameBuf = Arrays.copyOf(nameBuf, n); + } + System.arraycopy(buf, ptr, nameBuf, pfx, sfx); + ptr += sfx; + nameLen = pfx + sfx; + } + + String name() { + int len = nameLen; + if (blockType == LOG_BLOCK_TYPE) { + len -= 9; + } + return RawParseUtils.decode(UTF_8, nameBuf, 0, len); + } + + boolean match(byte[] match, boolean matchIsPrefix) { + int len = nameLen; + if (blockType == LOG_BLOCK_TYPE) { + len -= 9; + } + if (matchIsPrefix) { + return len >= match.length + && compare( + match, 0, match.length, + nameBuf, 0, match.length) == 0; + } + return compare(match, 0, match.length, nameBuf, 0, len) == 0; + } + + long readPositionFromIndex() throws IOException { + if (blockType != INDEX_BLOCK_TYPE) { + throw invalidBlock(); + } + + readVarint32(); // skip prefix length + int n = readVarint32() >>> 3; + ptr += n; // skip name + return readVarint64(); + } + + Ref readRef() throws IOException { + String name = RawParseUtils.decode(UTF_8, nameBuf, 0, nameLen); + switch (valueType & VALUE_TYPE_MASK) { + case VALUE_NONE: // delete + return newRef(name); + + case VALUE_1ID: + return new ObjectIdRef.PeeledNonTag(PACKED, name, readValueId()); + + case VALUE_2ID: { // annotated tag + ObjectId id1 = readValueId(); + ObjectId id2 = readValueId(); + return new ObjectIdRef.PeeledTag(PACKED, name, id1, id2); + } + + case VALUE_SYMREF: { + String val = readValueString(); + return new SymbolicRef(name, newRef(val)); + } + + default: + throw invalidBlock(); + } + } + + @Nullable + LongList readBlockPositionList() { + int n = valueType & VALUE_TYPE_MASK; + if (n == 0) { + n = readVarint32(); + if (n == 0) { + return null; + } + } + + LongList b = new LongList(n); + b.add(readVarint64()); + for (int j = 1; j < n; j++) { + long prior = b.get(j - 1); + b.add(prior + readVarint64()); + } + return b; + } + + long readLogUpdateIndex() { + return reverseUpdateIndex(NB.decodeUInt64(nameBuf, nameLen - 8)); + } + + @Nullable + ReflogEntry readLogEntry() { + if ((valueType & VALUE_TYPE_MASK) == LOG_NONE) { + return null; + } + + ObjectId oldId = readValueId(); + ObjectId newId = readValueId(); + PersonIdent who = readPersonIdent(); + String msg = readValueString(); + + return new ReflogEntry() { + @Override + public ObjectId getOldId() { + return oldId; + } + + @Override + public ObjectId getNewId() { + return newId; + } + + @Override + public PersonIdent getWho() { + return who; + } + + @Override + public String getComment() { + return msg; + } + + @Override + public CheckoutEntry parseCheckout() { + return null; + } + }; + } + + private ObjectId readValueId() { + ObjectId id = ObjectId.fromRaw(buf, ptr); + ptr += OBJECT_ID_LENGTH; + return id; + } + + private String readValueString() { + int len = readVarint32(); + int end = ptr + len; + String s = RawParseUtils.decode(UTF_8, buf, ptr, end); + ptr = end; + return s; + } + + private PersonIdent readPersonIdent() { + String name = readValueString(); + String email = readValueString(); + long ms = readVarint64() * 1000; + int tz = readInt16(); + return new PersonIdent(name, email, ms, tz); + } + + void readBlock(BlockSource src, long pos, int fileBlockSize) + throws IOException { + readBlockIntoBuf(src, pos, fileBlockSize); + parseBlockStart(src, pos, fileBlockSize); + } + + private void readBlockIntoBuf(BlockSource src, long pos, int size) + throws IOException { + ByteBuffer b = src.read(pos, size); + bufLen = b.position(); + if (bufLen <= 0) { + throw invalidBlock(); + } + if (b.hasArray() && b.arrayOffset() == 0) { + buf = b.array(); + } else { + buf = new byte[bufLen]; + b.flip(); + b.get(buf); + } + endPosition = pos + bufLen; + } + + private void parseBlockStart(BlockSource src, long pos, int fileBlockSize) + throws IOException { + ptr = 0; + if (pos == 0) { + if (bufLen == FILE_HEADER_LEN) { + setupEmptyFileBlock(); + return; + } + ptr += FILE_HEADER_LEN; // first block begins with file header + } + + int typeAndSize = NB.decodeInt32(buf, ptr); + ptr += 4; + + blockType = (byte) (typeAndSize >>> 24); + int blockLen = decodeBlockLen(typeAndSize); + if (blockType == LOG_BLOCK_TYPE) { + // Log blocks must be inflated after the header. + long deflatedSize = inflateBuf(src, pos, blockLen, fileBlockSize); + endPosition = pos + 4 + deflatedSize; + } + if (bufLen < blockLen) { + if (blockType != INDEX_BLOCK_TYPE) { + throw invalidBlock(); + } + // Its OK during sequential scan for an index block to have been + // partially read and be truncated in-memory. This happens when + // the index block is larger than the file's blockSize. Caller + // will break out of its scan loop once it sees the blockType. + truncated = true; + } else if (bufLen > blockLen) { + bufLen = blockLen; + } + + if (blockType != FILE_BLOCK_TYPE) { + restartCnt = NB.decodeUInt16(buf, bufLen - 2); + restartTbl = bufLen - (restartCnt * 3 + 2); + keysStart = ptr; + keysEnd = restartTbl; + } else { + keysStart = ptr; + keysEnd = ptr; + } + } + + static int decodeBlockLen(int typeAndSize) { + return typeAndSize & 0xffffff; + } + + private long inflateBuf(BlockSource src, long pos, int blockLen, + int fileBlockSize) throws IOException { + byte[] dst = new byte[blockLen]; + System.arraycopy(buf, 0, dst, 0, 4); + + long deflatedSize = 0; + Inflater inf = InflaterCache.get(); + try { + inf.setInput(buf, ptr, bufLen - ptr); + for (int o = 4;;) { + int n = inf.inflate(dst, o, dst.length - o); + o += n; + if (inf.finished()) { + deflatedSize = inf.getBytesRead(); + break; + } else if (n <= 0 && inf.needsInput()) { + long p = pos + 4 + inf.getBytesRead(); + readBlockIntoBuf(src, p, fileBlockSize); + inf.setInput(buf, 0, bufLen); + } else if (n <= 0) { + throw invalidBlock(); + } + } + } catch (DataFormatException e) { + throw invalidBlock(e); + } finally { + InflaterCache.release(inf); + } + + buf = dst; + bufLen = dst.length; + return deflatedSize; + } + + private void setupEmptyFileBlock() { + // An empty reftable has only the file header in first block. + blockType = FILE_BLOCK_TYPE; + ptr = FILE_HEADER_LEN; + restartCnt = 0; + restartTbl = bufLen; + keysStart = bufLen; + keysEnd = bufLen; + } + + void verifyIndex() throws IOException { + if (blockType != INDEX_BLOCK_TYPE || truncated) { + throw invalidBlock(); + } + } + + /** + * Finds a key in the block and positions the current pointer on its record. + * <p> + * As a side-effect this method arranges for the current pointer to be near + * or exactly on {@code key}, allowing other methods to access data from + * that current record: + * <ul> + * <li>{@link #name()} + * <li>{@link #match(byte[], boolean)} + * <li>{@link #readRef()} + * <li>{@link #readLogUpdateIndex()} + * <li>{@link #readLogEntry()} + * <li>{@link #readBlockPositionList()} + * </ul> + * + * @param key + * key to find. + * @return {@code <0} if the key occurs before the start of this block; + * {@code 0} if the block is positioned on the key; {@code >0} if + * the key occurs after the last key of this block. + */ + int seekKey(byte[] key) { + int low = 0; + int end = restartCnt; + for (;;) { + int mid = (low + end) >>> 1; + int p = NB.decodeUInt24(buf, restartTbl + mid * 3); + ptr = p + 1; // skip 0 prefix length + int n = readVarint32() >>> 3; + int cmp = compare(key, 0, key.length, buf, ptr, n); + if (cmp < 0) { + end = mid; + } else if (cmp == 0) { + ptr = p; + return 0; + } else /* if (cmp > 0) */ { + low = mid + 1; + } + if (low >= end) { + return scanToKey(key, p, low, cmp); + } + } + } + + /** + * Performs the linear search step within a restart interval. + * <p> + * Starts at a restart position whose key sorts before (or equal to) + * {@code key} and walks sequentially through the following prefix + * compressed records to find {@code key}. + * + * @param key + * key the caller wants to find. + * @param rPtr + * current record pointer from restart table binary search. + * @param rIdx + * current restart table index. + * @param rCmp + * result of compare from restart table binary search. + * @return {@code <0} if the key occurs before the start of this block; + * {@code 0} if the block is positioned on the key; {@code >0} if + * the key occurs after the last key of this block. + */ + private int scanToKey(byte[] key, int rPtr, int rIdx, int rCmp) { + if (rCmp < 0) { + if (rIdx == 0) { + ptr = keysStart; + return -1; + } + ptr = NB.decodeUInt24(buf, restartTbl + (rIdx - 1) * 3); + } else { + ptr = rPtr; + } + + int cmp; + do { + int savePtr = ptr; + parseKey(); + cmp = compare(key, 0, key.length, nameBuf, 0, nameLen); + if (cmp <= 0) { + // cmp < 0, name should be in this block, but is not. + // cmp = 0, block is positioned at name. + ptr = savePtr; + return cmp < 0 && savePtr == keysStart ? -1 : 0; + } + skipValue(); + } while (ptr < keysEnd); + return cmp; + } + + void skipValue() { + switch (blockType) { + case REF_BLOCK_TYPE: + switch (valueType & VALUE_TYPE_MASK) { + case VALUE_NONE: + return; + case VALUE_1ID: + ptr += OBJECT_ID_LENGTH; + return; + case VALUE_2ID: + ptr += 2 * OBJECT_ID_LENGTH; + return; + case VALUE_SYMREF: + skipString(); + return; + } + break; + + case OBJ_BLOCK_TYPE: { + int n = valueType & VALUE_TYPE_MASK; + if (n == 0) { + n = readVarint32(); + } + while (n-- > 0) { + readVarint32(); + } + return; + } + + case INDEX_BLOCK_TYPE: + readVarint32(); + return; + + case LOG_BLOCK_TYPE: + if ((valueType & VALUE_TYPE_MASK) == LOG_NONE) { + return; + } else if ((valueType & VALUE_TYPE_MASK) == LOG_DATA) { + ptr += 2 * OBJECT_ID_LENGTH; // oldId, newId + skipString(); // name + skipString(); // email + readVarint64(); // time + ptr += 2; // tz + skipString(); // msg + return; + } + } + + throw new IllegalStateException(); + } + + private void skipString() { + int n = readVarint32(); // string length + ptr += n; + } + + private short readInt16() { + return (short) NB.decodeUInt16(buf, ptr += 2); + } + + private int readVarint32() { + byte c = buf[ptr++]; + int val = c & 0x7f; + while ((c & 0x80) != 0) { + c = buf[ptr++]; + val++; + val <<= 7; + val |= (c & 0x7f); + } + return val; + } + + private long readVarint64() { + byte c = buf[ptr++]; + long val = c & 0x7f; + while ((c & 0x80) != 0) { + c = buf[ptr++]; + val++; + val <<= 7; + val |= (c & 0x7f); + } + return val; + } + + private static Ref newRef(String name) { + return new ObjectIdRef.Unpeeled(NEW, name, null); + } + + private static IOException invalidBlock() { + return invalidBlock(null); + } + + private static IOException invalidBlock(Throwable cause) { + return new IOException(JGitText.get().invalidReftableBlock, cause); + } +} diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/EmptyLogCursor.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/EmptyLogCursor.java new file mode 100644 index 0000000000..d7745891a5 --- /dev/null +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/EmptyLogCursor.java @@ -0,0 +1,76 @@ +/* + * Copyright (C) 2017, Google Inc. + * 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.internal.storage.reftable; + +import java.io.IOException; + +import org.eclipse.jgit.lib.ReflogEntry; + +/** Empty {@link LogCursor} with no results. */ +class EmptyLogCursor extends LogCursor { + @Override + public boolean next() throws IOException { + return false; + } + + @Override + public String getRefName() { + return null; + } + + @Override + public long getUpdateIndex() { + return 0; + } + + @Override + public ReflogEntry getReflogEntry() { + return null; + } + + @Override + public void close() { + // Do nothing. + } +} diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/LogCursor.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/LogCursor.java new file mode 100644 index 0000000000..c19968c098 --- /dev/null +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/LogCursor.java @@ -0,0 +1,72 @@ +/* + * Copyright (C) 2017, Google Inc. + * 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.internal.storage.reftable; + +import java.io.IOException; + +import org.eclipse.jgit.lib.ReflogEntry; + +/** Iterator over logs inside a {@link Reftable}. */ +public abstract class LogCursor implements AutoCloseable { + /** + * Check if another log record is available. + * + * @return {@code true} if there is another result. + * @throws IOException + * logs cannot be read. + */ + public abstract boolean next() throws IOException; + + /** @return name of the current reference. */ + public abstract String getRefName(); + + /** @return identifier of the transaction that created the log record. */ + public abstract long getUpdateIndex(); + + /** @return current log entry. */ + public abstract ReflogEntry getReflogEntry(); + + @Override + public abstract void close(); +} diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/RefCursor.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/RefCursor.java new file mode 100644 index 0000000000..786fae1a69 --- /dev/null +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/RefCursor.java @@ -0,0 +1,72 @@ +/* + * Copyright (C) 2017, Google Inc. + * 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.internal.storage.reftable; + +import java.io.IOException; + +import org.eclipse.jgit.lib.Ref; + +/** Iterator over references inside a {@link Reftable}. */ +public abstract class RefCursor implements AutoCloseable { + /** + * Check if another reference is available. + * + * @return {@code true} if there is another result. + * @throws IOException + * references cannot be read. + */ + public abstract boolean next() throws IOException; + + /** @return reference at the current position. */ + public abstract Ref getRef(); + + /** @return {@code true} if the current reference was deleted. */ + public boolean wasDeleted() { + Ref r = getRef(); + return r.getStorage() == Ref.Storage.NEW && r.getObjectId() == null; + } + + @Override + public abstract void close(); +} diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/Reftable.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/Reftable.java new file mode 100644 index 0000000000..e07bd28b69 --- /dev/null +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/Reftable.java @@ -0,0 +1,223 @@ +/* + * Copyright (C) 2017, Google Inc. + * 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.internal.storage.reftable; + +import java.io.ByteArrayOutputStream; +import java.io.IOException; +import java.util.Collection; + +import org.eclipse.jgit.annotations.Nullable; +import org.eclipse.jgit.internal.storage.io.BlockSource; +import org.eclipse.jgit.lib.AnyObjectId; +import org.eclipse.jgit.lib.Ref; + +/** Abstract table of references. */ +public abstract class Reftable implements AutoCloseable { + /** + * @param refs + * references to convert into a reftable; may be empty. + * @return a reader for the supplied references. + */ + public static Reftable from(Collection<Ref> refs) { + try { + ReftableConfig cfg = new ReftableConfig(); + cfg.setIndexObjects(false); + cfg.setAlignBlocks(false); + ByteArrayOutputStream buf = new ByteArrayOutputStream(); + new ReftableWriter() + .setConfig(cfg) + .begin(buf) + .sortAndWriteRefs(refs) + .finish(); + return new ReftableReader(BlockSource.from(buf.toByteArray())); + } catch (IOException e) { + throw new RuntimeException(e); + } + } + + /** {@code true} if deletions should be included in results. */ + protected boolean includeDeletes; + + /** + * @param deletes + * if {@code true} deleted references will be returned. If + * {@code false} (default behavior), deleted references will be + * skipped, and not returned. + */ + public void setIncludeDeletes(boolean deletes) { + includeDeletes = deletes; + } + + /** + * Seek to the first reference, to iterate in order. + * + * @return cursor to iterate. + * @throws IOException + * if references cannot be read. + */ + public abstract RefCursor allRefs() throws IOException; + + /** + * Seek either to a reference, or a reference subtree. + * <p> + * If {@code refName} ends with {@code "/"} the method will seek to the + * subtree of all references starting with {@code refName} as a prefix. If + * no references start with this prefix, an empty cursor is returned. + * <p> + * Otherwise exactly {@code refName} will be looked for. If present, the + * returned cursor will iterate exactly one entry. If not found, an empty + * cursor is returned. + * + * @param refName + * reference name or subtree to find. + * @return cursor to iterate; empty cursor if no references match. + * @throws IOException + * if references cannot be read. + */ + public abstract RefCursor seekRef(String refName) throws IOException; + + /** + * Match references pointing to a specific object. + * + * @param id + * object to find. + * @return cursor to iterate; empty cursor if no references match. + * @throws IOException + * if references cannot be read. + */ + public abstract RefCursor byObjectId(AnyObjectId id) throws IOException; + + /** + * Seek reader to read log records. + * + * @return cursor to iterate; empty cursor if no logs are present. + * @throws IOException + * if logs cannot be read. + */ + public abstract LogCursor allLogs() throws IOException; + + /** + * Read a single reference's log. + * + * @param refName + * exact name of the reference whose log to read. + * @return cursor to iterate; empty cursor if no logs match. + * @throws IOException + * if logs cannot be read. + */ + public LogCursor seekLog(String refName) throws IOException { + return seekLog(refName, Long.MAX_VALUE); + } + + /** + * Seek to an update index in a reference's log. + * + * @param refName + * exact name of the reference whose log to read. + * @param updateIndex + * most recent index to return first in the log cursor. Log + * records at or before {@code updateIndex} will be returned. + * @return cursor to iterate; empty cursor if no logs match. + * @throws IOException + * if logs cannot be read. + */ + public abstract LogCursor seekLog(String refName, long updateIndex) + throws IOException; + + /** + * Lookup a reference, or null if not found. + * + * @param refName + * reference name to find. + * @return the reference, or {@code null} if not found. + * @throws IOException + * if references cannot be read. + */ + @Nullable + public Ref exactRef(String refName) throws IOException { + try (RefCursor rc = seekRef(refName)) { + return rc.next() ? rc.getRef() : null; + } + } + + /** + * Test if a reference or reference subtree exists. + * <p> + * If {@code refName} ends with {@code "/"}, the method tests if any + * reference starts with {@code refName} as a prefix. + * <p> + * Otherwise, the method checks if {@code refName} exists. + * + * @param refName + * reference name or subtree to find. + * @return {@code true} if the reference exists, or at least one reference + * exists in the subtree. + * @throws IOException + * if references cannot be read. + */ + public boolean hasRef(String refName) throws IOException { + try (RefCursor rc = seekRef(refName)) { + return rc.next(); + } + } + + /** + * Test if any reference directly refers to the object. + * + * @param id + * ObjectId to find. + * @return {@code true} if any reference exists directly referencing + * {@code id}, or a annotated tag that peels to {@code id}. + * @throws IOException + * if references cannot be read. + */ + public boolean hasId(AnyObjectId id) throws IOException { + try (RefCursor rc = byObjectId(id)) { + return rc.next(); + } + } + + @Override + public abstract void close() throws IOException; +} diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/ReftableReader.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/ReftableReader.java new file mode 100644 index 0000000000..3d505e3ff5 --- /dev/null +++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/storage/reftable/ReftableReader.java @@ -0,0 +1,658 @@ +/* + * Copyright (C) 2017, Google Inc. + * 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.internal.storage.reftable; + +import static java.nio.charset.StandardCharsets.UTF_8; +import static org.eclipse.jgit.internal.storage.reftable.BlockReader.decodeBlockLen; +import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.FILE_BLOCK_TYPE; +import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.FILE_FOOTER_LEN; +import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.FILE_HEADER_LEN; +import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.INDEX_BLOCK_TYPE; +import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.LOG_BLOCK_TYPE; +import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.REF_BLOCK_TYPE; +import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.VERSION_1; +import static org.eclipse.jgit.internal.storage.reftable.ReftableConstants.isFileHeaderMagic; +import static org.eclipse.jgit.lib.Constants.OBJECT_ID_LENGTH; + +import java.io.IOException; +import java.nio.ByteBuffer; +import java.text.MessageFormat; +import java.util.Arrays; +import java.util.zip.CRC32; + +import org.eclipse.jgit.internal.JGitText; +import org.eclipse.jgit.internal.storage.io.BlockSource; +import org.eclipse.jgit.internal.storage.reftable.BlockWriter.LogEntry; +import org.eclipse.jgit.lib.AnyObjectId; +import org.eclipse.jgit.lib.ObjectId; +import org.eclipse.jgit.lib.Ref; +import org.eclipse.jgit.lib.ReflogEntry; +import org.eclipse.jgit.util.LongList; +import org.eclipse.jgit.util.LongMap; +import org.eclipse.jgit.util.NB; + +/** + * Reads a reftable formatted file. + * <p> + * {@code ReftableReader} is not thread-safe. Concurrent readers need their own + * instance to read from the same file. + */ +public class ReftableReader extends Reftable { + private final BlockSource src; + + private int blockSize = -1; + private long minUpdateIndex; + private long maxUpdateIndex; + + private long refEnd; + private long objPosition; + private long objEnd; + private long logPosition; + private long logEnd; + private int objIdLen; + + private long refIndexPosition = -1; + private long objIndexPosition = -1; + private long logIndexPosition = -1; + + private BlockReader refIndex; + private BlockReader objIndex; + private BlockReader logIndex; + private LongMap<BlockReader> indexCache; + + /** + * Initialize a new reftable reader. + * + * @param src + * the file content to read. + */ + public ReftableReader(BlockSource src) { + this.src = src; + } + + /** + * @return the block size in bytes chosen for this file by the writer. Most + * reads from the {@link BlockSource} will be aligned to the block + * size. + * @throws IOException + * file cannot be read. + */ + public int blockSize() throws IOException { + if (blockSize == -1) { + readFileHeader(); + } + return blockSize; + } + + /** + * @return the minimum update index for log entries that appear in this + * reftable. This should be 1 higher than the prior reftable's + * {@code maxUpdateIndex} if this table is used in a stack. + * @throws IOException + * file cannot be read. + */ + public long minUpdateIndex() throws IOException { + if (blockSize == -1) { + readFileHeader(); + } + return minUpdateIndex; + } + + /** + * @return the maximum update index for log entries that appear in this + * reftable. This should be 1 higher than the prior reftable's + * {@code maxUpdateIndex} if this table is used in a stack. + * @throws IOException + * file cannot be read. + */ + public long maxUpdateIndex() throws IOException { + if (blockSize == -1) { + readFileHeader(); + } + return maxUpdateIndex; + } + + @Override + public RefCursor allRefs() throws IOException { + if (blockSize == -1) { + readFileHeader(); + } + + long end = refEnd > 0 ? refEnd : (src.size() - FILE_FOOTER_LEN); + src.adviseSequentialRead(0, end); + + RefCursorImpl i = new RefCursorImpl(end, null, false); + i.block = readBlock(0, end); + return i; + } + + @Override + public RefCursor seekRef(String refName) throws IOException { + initRefIndex(); + + byte[] key = refName.getBytes(UTF_8); + boolean prefix = key[key.length - 1] == '/'; + + RefCursorImpl i = new RefCursorImpl(refEnd, key, prefix); + i.block = seek(REF_BLOCK_TYPE, key, refIndex, 0, refEnd); + return i; + } + + @Override + public RefCursor byObjectId(AnyObjectId id) throws IOException { + initObjIndex(); + ObjCursorImpl i = new ObjCursorImpl(refEnd, id); + if (objIndex != null) { + i.initSeek(); + } else { + i.initScan(); + } + return i; + } + + @Override + public LogCursor allLogs() throws IOException { + initLogIndex(); + if (logPosition > 0) { + src.adviseSequentialRead(logPosition, logEnd); + LogCursorImpl i = new LogCursorImpl(logEnd, null); + i.block = readBlock(logPosition, logEnd); + return i; + } + return new EmptyLogCursor(); + } + + @Override + public LogCursor seekLog(String refName, long updateIndex) + throws IOException { + initLogIndex(); + if (logPosition > 0) { + byte[] key = LogEntry.key(refName, updateIndex); + byte[] match = refName.getBytes(UTF_8); + LogCursorImpl i = new LogCursorImpl(logEnd, match); + i.block = seek(LOG_BLOCK_TYPE, key, logIndex, logPosition, logEnd); + return i; + } + return new EmptyLogCursor(); + } + + private BlockReader seek(byte blockType, byte[] key, BlockReader idx, + long startPos, long endPos) throws IOException { + if (idx != null) { + // Walk through a possibly multi-level index to a leaf block. + BlockReader block = idx; + do { + if (block.seekKey(key) > 0) { + return null; + } + long pos = block.readPositionFromIndex(); + block = readBlock(pos, endPos); + } while (block.type() == INDEX_BLOCK_TYPE); + block.seekKey(key); + return block; + } + return binarySearch(blockType, key, startPos, endPos); + } + + private BlockReader binarySearch(byte blockType, byte[] key, + long startPos, long endPos) throws IOException { + if (blockSize == 0) { + BlockReader b = readBlock(startPos, endPos); + if (blockType != b.type()) { + return null; + } + b.seekKey(key); + return b; + } + + int low = (int) (startPos / blockSize); + int end = blocksIn(startPos, endPos); + BlockReader block = null; + do { + int mid = (low + end) >>> 1; + block = readBlock(((long) mid) * blockSize, endPos); + if (blockType != block.type()) { + return null; + } + int cmp = block.seekKey(key); + if (cmp < 0) { + end = mid; + } else if (cmp == 0) { + break; + } else /* if (cmp > 0) */ { + low = mid + 1; + } + } while (low < end); + return block; + } + + private void readFileHeader() throws IOException { + readHeaderOrFooter(0, FILE_HEADER_LEN); + } + + private void readFileFooter() throws IOException { + int ftrLen = FILE_FOOTER_LEN; + byte[] ftr = readHeaderOrFooter(src.size() - ftrLen, ftrLen); + + CRC32 crc = new CRC32(); + crc.update(ftr, 0, ftrLen - 4); + if (crc.getValue() != NB.decodeUInt32(ftr, ftrLen - 4)) { + throw new IOException(JGitText.get().invalidReftableCRC); + } + + refIndexPosition = NB.decodeInt64(ftr, 24); + long p = NB.decodeInt64(ftr, 32); + objPosition = p >>> 5; + objIdLen = (int) (p & 0x1f); + objIndexPosition = NB.decodeInt64(ftr, 40); + logPosition = NB.decodeInt64(ftr, 48); + logIndexPosition = NB.decodeInt64(ftr, 56); + + if (refIndexPosition > 0) { + refEnd = refIndexPosition; + } else if (objPosition > 0) { + refEnd = objPosition; + } else if (logPosition > 0) { + refEnd = logPosition; + } else { + refEnd = src.size() - ftrLen; + } + + if (objPosition > 0) { + if (objIndexPosition > 0) { + objEnd = objIndexPosition; + } else if (logPosition > 0) { + objEnd = logPosition; + } else { + objEnd = src.size() - ftrLen; + } + } + + if (logPosition > 0) { + if (logIndexPosition > 0) { + logEnd = logIndexPosition; + } else { + logEnd = src.size() - ftrLen; + } + } + } + + private byte[] readHeaderOrFooter(long pos, int len) throws IOException { + ByteBuffer buf = src.read(pos, len); + if (buf.position() != len) { + throw new IOException(JGitText.get().shortReadOfBlock); + } + + byte[] tmp = new byte[len]; + buf.flip(); + buf.get(tmp); + if (!isFileHeaderMagic(tmp, 0, len)) { + throw new IOException(JGitText.get().invalidReftableFile); + } + + int v = NB.decodeInt32(tmp, 4); + int version = v >>> 24; + if (VERSION_1 != version) { + throw new IOException(MessageFormat.format( + JGitText.get().unsupportedReftableVersion, + Integer.valueOf(version))); + } + if (blockSize == -1) { + blockSize = v & 0xffffff; + } + minUpdateIndex = NB.decodeInt64(tmp, 8); + maxUpdateIndex = NB.decodeInt64(tmp, 16); + return tmp; + } + + private void initRefIndex() throws IOException { + if (refIndexPosition < 0) { + readFileFooter(); + } + if (refIndex == null && refIndexPosition > 0) { + refIndex = readIndex(refIndexPosition); + } + } + + private void initObjIndex() throws IOException { + if (objIndexPosition < 0) { + readFileFooter(); + } + if (objIndex == null && objIndexPosition > 0) { + objIndex = readIndex(objIndexPosition); + } + } + + private void initLogIndex() throws IOException { + if (logIndexPosition < 0) { + readFileFooter(); + } + if (logIndex == null && logIndexPosition > 0) { + logIndex = readIndex(logIndexPosition); + } + } + + private BlockReader readIndex(long pos) throws IOException { + int sz = readBlockLen(pos); + BlockReader i = new BlockReader(); + i.readBlock(src, pos, sz); + i.verifyIndex(); + return i; + } + + private int readBlockLen(long pos) throws IOException { + int sz = pos == 0 ? FILE_HEADER_LEN + 4 : 4; + ByteBuffer tmp = src.read(pos, sz); + if (tmp.position() < sz) { + throw new IOException(JGitText.get().invalidReftableFile); + } + byte[] buf; + if (tmp.hasArray() && tmp.arrayOffset() == 0) { + buf = tmp.array(); + } else { + buf = new byte[sz]; + tmp.flip(); + tmp.get(buf); + } + if (pos == 0 && buf[FILE_HEADER_LEN] == FILE_BLOCK_TYPE) { + return FILE_HEADER_LEN; + } + int p = pos == 0 ? FILE_HEADER_LEN : 0; + return decodeBlockLen(NB.decodeInt32(buf, p)); + } + + private BlockReader readBlock(long pos, long end) throws IOException { + if (indexCache != null) { + BlockReader b = indexCache.get(pos); + if (b != null) { + return b; + } + } + + int sz = blockSize; + if (sz == 0) { + sz = readBlockLen(pos); + } else if (pos + sz > end) { + sz = (int) (end - pos); // last block may omit padding. + } + + BlockReader b = new BlockReader(); + b.readBlock(src, pos, sz); + if (b.type() == INDEX_BLOCK_TYPE && !b.truncated()) { + if (indexCache == null) { + indexCache = new LongMap<>(); + } + indexCache.put(pos, b); + } + return b; + } + + private int blocksIn(long pos, long end) { + int blocks = (int) ((end - pos) / blockSize); + return end % blockSize == 0 ? blocks : (blocks + 1); + } + + @Override + public void close() throws IOException { + src.close(); + } + + private class RefCursorImpl extends RefCursor { + private final long scanEnd; + private final byte[] match; + private final boolean prefix; + + private Ref ref; + BlockReader block; + + RefCursorImpl(long scanEnd, byte[] match, boolean prefix) { + this.scanEnd = scanEnd; + this.match = match; + this.prefix = prefix; + } + + @Override + public boolean next() throws IOException { + for (;;) { + if (block == null || block.type() != REF_BLOCK_TYPE) { + return false; + } else if (!block.next()) { + long pos = block.endPosition(); + if (pos >= scanEnd) { + return false; + } + block = readBlock(pos, scanEnd); + continue; + } + + block.parseKey(); + if (match != null && !block.match(match, prefix)) { + block.skipValue(); + return false; + } + + ref = block.readRef(); + if (!includeDeletes && wasDeleted()) { + continue; + } + return true; + } + } + + @Override + public Ref getRef() { + return ref; + } + + @Override + public void close() { + // Do nothing. + } + } + + private class LogCursorImpl extends LogCursor { + private final long scanEnd; + private final byte[] match; + + private String refName; + private long updateIndex; + private ReflogEntry entry; + BlockReader block; + + LogCursorImpl(long scanEnd, byte[] match) { + this.scanEnd = scanEnd; + this.match = match; + } + + @Override + public boolean next() throws IOException { + for (;;) { + if (block == null || block.type() != LOG_BLOCK_TYPE) { + return false; + } else if (!block.next()) { + long pos = block.endPosition(); + if (pos >= scanEnd) { + return false; + } + block = readBlock(pos, scanEnd); + continue; + } + + block.parseKey(); + if (match != null && !block.match(match, false)) { + block.skipValue(); + return false; + } + + refName = block.name(); + updateIndex = block.readLogUpdateIndex(); + entry = block.readLogEntry(); + if (entry == null && !includeDeletes) { + continue; + } + return true; + } + } + + @Override + public String getRefName() { + return refName; + } + + @Override + public long getUpdateIndex() { + return updateIndex; + } + + @Override + public ReflogEntry getReflogEntry() { + return entry; + } + + @Override + public void close() { + // Do nothing. + } + } + + static final LongList EMPTY_LONG_LIST = new LongList(0); + + private class ObjCursorImpl extends RefCursor { + private final long scanEnd; + private final ObjectId match; + + private Ref ref; + private int listIdx; + + private LongList blockPos; + private BlockReader block; + + ObjCursorImpl(long scanEnd, AnyObjectId id) { + this.scanEnd = scanEnd; + this.match = id.copy(); + } + + void initSeek() throws IOException { + byte[] rawId = new byte[OBJECT_ID_LENGTH]; + match.copyRawTo(rawId, 0); + byte[] key = Arrays.copyOf(rawId, objIdLen); + + BlockReader b = objIndex; + do { + if (b.seekKey(key) > 0) { + blockPos = EMPTY_LONG_LIST; + return; + } + long pos = b.readPositionFromIndex(); + b = readBlock(pos, objEnd); + } while (b.type() == INDEX_BLOCK_TYPE); + b.seekKey(key); + while (b.next()) { + b.parseKey(); + if (b.match(key, false)) { + blockPos = b.readBlockPositionList(); + if (blockPos == null) { + initScan(); + return; + } + break; + } + b.skipValue(); + } + if (blockPos == null) { + blockPos = EMPTY_LONG_LIST; + } + if (blockPos.size() > 0) { + long pos = blockPos.get(listIdx++); + block = readBlock(pos, scanEnd); + } + } + + void initScan() throws IOException { + block = readBlock(0, scanEnd); + } + + @Override + public boolean next() throws IOException { + for (;;) { + if (block == null || block.type() != REF_BLOCK_TYPE) { + return false; + } else if (!block.next()) { + long pos; + if (blockPos != null) { + if (listIdx >= blockPos.size()) { + return false; + } + pos = blockPos.get(listIdx++); + } else { + pos = block.endPosition(); + } + if (pos >= scanEnd) { + return false; + } + block = readBlock(pos, scanEnd); + continue; + } + + block.parseKey(); + ref = block.readRef(); + ObjectId id = ref.getObjectId(); + if (id != null && match.equals(id) + && (includeDeletes || !wasDeleted())) { + return true; + } + } + } + + @Override + public Ref getRef() { + return ref; + } + + @Override + public void close() { + // Do nothing. + } + } +} |