BlockReader.java

/*
 * Copyright (C) 2017, Google Inc. and others
 *
 * This program and the accompanying materials are made available under the
 * terms of the Eclipse Distribution License v. 1.0 which is available at
 * https://www.eclipse.org/org/documents/edl-v10.php.
 *
 * SPDX-License-Identifier: BSD-3-Clause
 */

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}. Instances are tied to a
 * specific block in the file so are not reused for other blocks. Instances hold
 * an offset into the block.
 */
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);
    }

    // Matches the key against a name or a prefix. For reflogs, only the
    // refname is matched, and the updateIndex suffix is ignored.
    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();
    }

    long readUpdateIndexDelta() {
        return readVarint64();
    }

    Ref readRef(long minUpdateIndex) throws IOException {
        long updateIndex = minUpdateIndex + readUpdateIndexDelta();
        String name = RawParseUtils.decode(UTF_8, nameBuf, 0, nameLen);
        switch (valueType & VALUE_TYPE_MASK) {
        case VALUE_NONE: // delete
            return newRef(name, updateIndex);

        case VALUE_1ID:
            return new ObjectIdRef.PeeledNonTag(PACKED, name, readValueId(),
                    updateIndex);

        case VALUE_2ID: { // annotated tag
            ObjectId id1 = readValueId();
            ObjectId id2 = readValueId();
            return new ObjectIdRef.PeeledTag(PACKED, name, id1, id2,
                    updateIndex);
        }

        case VALUE_SYMREF: {
            String val = readValueString();
            return new SymbolicRef(name, newRef(val, updateIndex), updateIndex);
        }

        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(long)}
     * <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:
            readVarint64(); // update_index_delta
            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() {
        short result =(short) NB.decodeUInt16(buf, ptr);
        ptr += 2;
        return result;
    }

    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, long updateIndex) {
        return new ObjectIdRef.Unpeeled(NEW, name, null, updateIndex);
    }

    private static IOException invalidBlock() {
        return invalidBlock(null);
    }

    private static IOException invalidBlock(Throwable cause) {
        return new IOException(JGitText.get().invalidReftableBlock, cause);
    }
}