Pack.java

/*
 * Copyright (C) 2008-2009, Google Inc.
 * Copyright (C) 2007, Robin Rosenberg <robin.rosenberg@dewire.com>
 * Copyright (C) 2006-2008, Shawn O. Pearce <spearce@spearce.org> 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.file;

import static org.eclipse.jgit.internal.storage.pack.PackExt.INDEX;
import static org.eclipse.jgit.internal.storage.pack.PackExt.KEEP;

import java.io.EOFException;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InterruptedIOException;
import java.io.RandomAccessFile;
import java.nio.MappedByteBuffer;
import java.nio.channels.FileChannel.MapMode;
import java.nio.file.AccessDeniedException;
import java.nio.file.NoSuchFileException;
import java.text.MessageFormat;
import java.time.Instant;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.Set;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.zip.CRC32;
import java.util.zip.DataFormatException;
import java.util.zip.Inflater;

import org.eclipse.jgit.annotations.Nullable;
import org.eclipse.jgit.errors.CorruptObjectException;
import org.eclipse.jgit.errors.LargeObjectException;
import org.eclipse.jgit.errors.MissingObjectException;
import org.eclipse.jgit.errors.NoPackSignatureException;
import org.eclipse.jgit.errors.PackInvalidException;
import org.eclipse.jgit.errors.PackMismatchException;
import org.eclipse.jgit.errors.StoredObjectRepresentationNotAvailableException;
import org.eclipse.jgit.errors.UnpackException;
import org.eclipse.jgit.errors.UnsupportedPackIndexVersionException;
import org.eclipse.jgit.errors.UnsupportedPackVersionException;
import org.eclipse.jgit.internal.JGitText;
import org.eclipse.jgit.internal.storage.pack.BinaryDelta;
import org.eclipse.jgit.internal.storage.pack.PackOutputStream;
import org.eclipse.jgit.lib.AbbreviatedObjectId;
import org.eclipse.jgit.lib.AnyObjectId;
import org.eclipse.jgit.lib.Constants;
import org.eclipse.jgit.lib.ObjectId;
import org.eclipse.jgit.lib.ObjectLoader;
import org.eclipse.jgit.util.LongList;
import org.eclipse.jgit.util.NB;
import org.eclipse.jgit.util.RawParseUtils;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * A Git version 2 pack file representation. A pack file contains Git objects in
 * delta packed format yielding high compression of lots of object where some
 * objects are similar.
 */
public class Pack implements Iterable<PackIndex.MutableEntry> {
    private static final Logger LOG = LoggerFactory.getLogger(Pack.class);

    /**
     * Sorts PackFiles to be most recently created to least recently created.
     */
    public static final Comparator<Pack> SORT = (a, b) -> b.packLastModified
            .compareTo(a.packLastModified);

    private final PackFile packFile;

    private PackFile keepFile;

    final int hash;

    private RandomAccessFile fd;

    /** Serializes reads performed against {@link #fd}. */
    private final Object readLock = new Object();

    long length;

    private int activeWindows;

    private int activeCopyRawData;

    Instant packLastModified;

    private PackFileSnapshot fileSnapshot;

    private volatile boolean invalid;

    private volatile Exception invalidatingCause;

    @Nullable
    private PackFile bitmapIdxFile;

    private AtomicInteger transientErrorCount = new AtomicInteger();

    private byte[] packChecksum;

    private volatile PackIndex loadedIdx;

    private PackReverseIndex reverseIdx;

    private PackBitmapIndex bitmapIdx;

    /**
     * Objects we have tried to read, and discovered to be corrupt.
     * <p>
     * The list is allocated after the first corruption is found, and filled in
     * as more entries are discovered. Typically this list is never used, as
     * pack files do not usually contain corrupt objects.
     */
    private volatile LongList corruptObjects;

    /**
     * Construct a reader for an existing, pre-indexed packfile.
     *
     * @param packFile
     *            path of the <code>.pack</code> file holding the data.
     * @param bitmapIdxFile
     *            existing bitmap index file with the same base as the pack
     */
    public Pack(File packFile, @Nullable PackFile bitmapIdxFile) {
        this.packFile = new PackFile(packFile);
        this.fileSnapshot = PackFileSnapshot.save(packFile);
        this.packLastModified = fileSnapshot.lastModifiedInstant();
        this.bitmapIdxFile = bitmapIdxFile;

        // Multiply by 31 here so we can more directly combine with another
        // value in WindowCache.hash(), without doing the multiply there.
        //
        hash = System.identityHashCode(this) * 31;
        length = Long.MAX_VALUE;
    }

    private PackIndex idx() throws IOException {
        PackIndex idx = loadedIdx;
        if (idx == null) {
            synchronized (this) {
                idx = loadedIdx;
                if (idx == null) {
                    if (invalid) {
                        throw new PackInvalidException(packFile,
                                invalidatingCause);
                    }
                    try {
                        long start = System.currentTimeMillis();
                        PackFile idxFile = packFile.create(INDEX);
                        idx = PackIndex.open(idxFile);
                        if (LOG.isDebugEnabled()) {
                            LOG.debug(String.format(
                                    "Opening pack index %s, size %.3f MB took %d ms", //$NON-NLS-1$
                                    idxFile.getAbsolutePath(),
                                    Float.valueOf(idxFile.length()
                                            / (1024f * 1024)),
                                    Long.valueOf(System.currentTimeMillis()
                                            - start)));
                        }

                        if (packChecksum == null) {
                            packChecksum = idx.packChecksum;
                            fileSnapshot.setChecksum(
                                    ObjectId.fromRaw(packChecksum));
                        } else if (!Arrays.equals(packChecksum,
                                idx.packChecksum)) {
                            throw new PackMismatchException(MessageFormat
                                    .format(JGitText.get().packChecksumMismatch,
                                            packFile.getPath(),
                                            ObjectId.fromRaw(packChecksum)
                                                    .name(),
                                            ObjectId.fromRaw(idx.packChecksum)
                                                    .name()));
                        }
                        loadedIdx = idx;
                    } catch (InterruptedIOException e) {
                        // don't invalidate the pack, we are interrupted from
                        // another thread
                        throw e;
                    } catch (IOException e) {
                        invalid = true;
                        invalidatingCause = e;
                        throw e;
                    }
                }
            }
        }
        return idx;
    }
    /**
     * Get the File object which locates this pack on disk.
     *
     * @return the File object which locates this pack on disk.
     */
    public PackFile getPackFile() {
        return packFile;
    }

    /**
     * Get the index for this pack file.
     *
     * @return the index for this pack file.
     * @throws java.io.IOException
     */
    public PackIndex getIndex() throws IOException {
        return idx();
    }

    /**
     * Get name extracted from {@code pack-*.pack} pattern.
     *
     * @return name extracted from {@code pack-*.pack} pattern.
     */
    public String getPackName() {
        return packFile.getId();
    }

    /**
     * Determine if an object is contained within the pack file.
     * <p>
     * For performance reasons only the index file is searched; the main pack
     * content is ignored entirely.
     * </p>
     *
     * @param id
     *            the object to look for. Must not be null.
     * @return true if the object is in this pack; false otherwise.
     * @throws java.io.IOException
     *             the index file cannot be loaded into memory.
     */
    public boolean hasObject(AnyObjectId id) throws IOException {
        final long offset = idx().findOffset(id);
        return 0 < offset && !isCorrupt(offset);
    }

    /**
     * Determines whether a .keep file exists for this pack file.
     *
     * @return true if a .keep file exist.
     */
    public boolean shouldBeKept() {
        if (keepFile == null) {
            keepFile = packFile.create(KEEP);
        }
        return keepFile.exists();
    }

    /**
     * Get an object from this pack.
     *
     * @param curs
     *            temporary working space associated with the calling thread.
     * @param id
     *            the object to obtain from the pack. Must not be null.
     * @return the object loader for the requested object if it is contained in
     *         this pack; null if the object was not found.
     * @throws IOException
     *             the pack file or the index could not be read.
     */
    ObjectLoader get(WindowCursor curs, AnyObjectId id)
            throws IOException {
        final long offset = idx().findOffset(id);
        return 0 < offset && !isCorrupt(offset) ? load(curs, offset) : null;
    }

    void resolve(Set<ObjectId> matches, AbbreviatedObjectId id, int matchLimit)
            throws IOException {
        idx().resolve(matches, id, matchLimit);
    }

    /**
     * Close the resources utilized by this repository
     */
    public void close() {
        WindowCache.purge(this);
        synchronized (this) {
            loadedIdx = null;
            reverseIdx = null;
        }
    }

    /**
     * {@inheritDoc}
     * <p>
     * Provide iterator over entries in associated pack index, that should also
     * exist in this pack file. Objects returned by such iterator are mutable
     * during iteration.
     * <p>
     * Iterator returns objects in SHA-1 lexicographical order.
     * </p>
     *
     * @see PackIndex#iterator()
     */
    @Override
    public Iterator<PackIndex.MutableEntry> iterator() {
        try {
            return idx().iterator();
        } catch (IOException e) {
            return Collections.<PackIndex.MutableEntry> emptyList().iterator();
        }
    }

    /**
     * Obtain the total number of objects available in this pack. This method
     * relies on pack index, giving number of effectively available objects.
     *
     * @return number of objects in index of this pack, likewise in this pack
     * @throws IOException
     *             the index file cannot be loaded into memory.
     */
    long getObjectCount() throws IOException {
        return idx().getObjectCount();
    }

    /**
     * Search for object id with the specified start offset in associated pack
     * (reverse) index.
     *
     * @param offset
     *            start offset of object to find
     * @return object id for this offset, or null if no object was found
     * @throws IOException
     *             the index file cannot be loaded into memory.
     */
    ObjectId findObjectForOffset(long offset) throws IOException {
        return getReverseIdx().findObject(offset);
    }

    /**
     * Return the @{@link FileSnapshot} associated to the underlying packfile
     * that has been used when the object was created.
     *
     * @return the packfile @{@link FileSnapshot} that the object is loaded from.
     */
    PackFileSnapshot getFileSnapshot() {
        return fileSnapshot;
    }

    AnyObjectId getPackChecksum() {
        return ObjectId.fromRaw(packChecksum);
    }

    private final byte[] decompress(final long position, final int sz,
            final WindowCursor curs) throws IOException, DataFormatException {
        byte[] dstbuf;
        try {
            dstbuf = new byte[sz];
        } catch (OutOfMemoryError noMemory) {
            // The size may be larger than our heap allows, return null to
            // let the caller know allocation isn't possible and it should
            // use the large object streaming approach instead.
            //
            // For example, this can occur when sz is 640 MB, and JRE
            // maximum heap size is only 256 MB. Even if the JRE has
            // 200 MB free, it cannot allocate a 640 MB byte array.
            return null;
        }

        if (curs.inflate(this, position, dstbuf, false) != sz)
            throw new EOFException(MessageFormat.format(
                    JGitText.get().shortCompressedStreamAt,
                    Long.valueOf(position)));
        return dstbuf;
    }

    void copyPackAsIs(PackOutputStream out, WindowCursor curs)
            throws IOException {
        // Pin the first window, this ensures the length is accurate.
        curs.pin(this, 0);
        curs.copyPackAsIs(this, length, out);
    }

    final void copyAsIs(PackOutputStream out, LocalObjectToPack src,
            boolean validate, WindowCursor curs) throws IOException,
            StoredObjectRepresentationNotAvailableException {
        beginCopyAsIs();
        try {
            copyAsIs2(out, src, validate, curs);
        } finally {
            endCopyAsIs();
        }
    }

    private void copyAsIs2(PackOutputStream out, LocalObjectToPack src,
            boolean validate, WindowCursor curs) throws IOException,
            StoredObjectRepresentationNotAvailableException {
        final CRC32 crc1 = validate ? new CRC32() : null;
        final CRC32 crc2 = validate ? new CRC32() : null;
        final byte[] buf = out.getCopyBuffer();

        // Rip apart the header so we can discover the size.
        //
        readFully(src.offset, buf, 0, 20, curs);
        int c = buf[0] & 0xff;
        final int typeCode = (c >> 4) & 7;
        long inflatedLength = c & 15;
        int shift = 4;
        int headerCnt = 1;
        while ((c & 0x80) != 0) {
            c = buf[headerCnt++] & 0xff;
            inflatedLength += ((long) (c & 0x7f)) << shift;
            shift += 7;
        }

        if (typeCode == Constants.OBJ_OFS_DELTA) {
            do {
                c = buf[headerCnt++] & 0xff;
            } while ((c & 128) != 0);
            if (validate) {
                assert(crc1 != null && crc2 != null);
                crc1.update(buf, 0, headerCnt);
                crc2.update(buf, 0, headerCnt);
            }
        } else if (typeCode == Constants.OBJ_REF_DELTA) {
            if (validate) {
                assert(crc1 != null && crc2 != null);
                crc1.update(buf, 0, headerCnt);
                crc2.update(buf, 0, headerCnt);
            }

            readFully(src.offset + headerCnt, buf, 0, 20, curs);
            if (validate) {
                assert(crc1 != null && crc2 != null);
                crc1.update(buf, 0, 20);
                crc2.update(buf, 0, 20);
            }
            headerCnt += 20;
        } else if (validate) {
            assert(crc1 != null && crc2 != null);
            crc1.update(buf, 0, headerCnt);
            crc2.update(buf, 0, headerCnt);
        }

        final long dataOffset = src.offset + headerCnt;
        final long dataLength = src.length;
        final long expectedCRC;
        final ByteArrayWindow quickCopy;

        // Verify the object isn't corrupt before sending. If it is,
        // we report it missing instead.
        //
        try {
            quickCopy = curs.quickCopy(this, dataOffset, dataLength);

            if (validate && idx().hasCRC32Support()) {
                assert(crc1 != null);
                // Index has the CRC32 code cached, validate the object.
                //
                expectedCRC = idx().findCRC32(src);
                if (quickCopy != null) {
                    quickCopy.crc32(crc1, dataOffset, (int) dataLength);
                } else {
                    long pos = dataOffset;
                    long cnt = dataLength;
                    while (cnt > 0) {
                        final int n = (int) Math.min(cnt, buf.length);
                        readFully(pos, buf, 0, n, curs);
                        crc1.update(buf, 0, n);
                        pos += n;
                        cnt -= n;
                    }
                }
                if (crc1.getValue() != expectedCRC) {
                    setCorrupt(src.offset);
                    throw new CorruptObjectException(MessageFormat.format(
                            JGitText.get().objectAtHasBadZlibStream,
                            Long.valueOf(src.offset), getPackFile()));
                }
            } else if (validate) {
                // We don't have a CRC32 code in the index, so compute it
                // now while inflating the raw data to get zlib to tell us
                // whether or not the data is safe.
                //
                Inflater inf = curs.inflater();
                byte[] tmp = new byte[1024];
                if (quickCopy != null) {
                    quickCopy.check(inf, tmp, dataOffset, (int) dataLength);
                } else {
                    assert(crc1 != null);
                    long pos = dataOffset;
                    long cnt = dataLength;
                    while (cnt > 0) {
                        final int n = (int) Math.min(cnt, buf.length);
                        readFully(pos, buf, 0, n, curs);
                        crc1.update(buf, 0, n);
                        inf.setInput(buf, 0, n);
                        while (inf.inflate(tmp, 0, tmp.length) > 0)
                            continue;
                        pos += n;
                        cnt -= n;
                    }
                }
                if (!inf.finished() || inf.getBytesRead() != dataLength) {
                    setCorrupt(src.offset);
                    throw new EOFException(MessageFormat.format(
                            JGitText.get().shortCompressedStreamAt,
                            Long.valueOf(src.offset)));
                }
                assert(crc1 != null);
                expectedCRC = crc1.getValue();
            } else {
                expectedCRC = -1;
            }
        } catch (DataFormatException dataFormat) {
            setCorrupt(src.offset);

            CorruptObjectException corruptObject = new CorruptObjectException(
                    MessageFormat.format(
                            JGitText.get().objectAtHasBadZlibStream,
                            Long.valueOf(src.offset), getPackFile()),
                    dataFormat);

            throw new StoredObjectRepresentationNotAvailableException(
                    corruptObject);

        } catch (IOException ioError) {
            throw new StoredObjectRepresentationNotAvailableException(ioError);
        }

        if (quickCopy != null) {
            // The entire object fits into a single byte array window slice,
            // and we have it pinned.  Write this out without copying.
            //
            out.writeHeader(src, inflatedLength);
            quickCopy.write(out, dataOffset, (int) dataLength);

        } else if (dataLength <= buf.length) {
            // Tiny optimization: Lots of objects are very small deltas or
            // deflated commits that are likely to fit in the copy buffer.
            //
            if (!validate) {
                long pos = dataOffset;
                long cnt = dataLength;
                while (cnt > 0) {
                    final int n = (int) Math.min(cnt, buf.length);
                    readFully(pos, buf, 0, n, curs);
                    pos += n;
                    cnt -= n;
                }
            }
            out.writeHeader(src, inflatedLength);
            out.write(buf, 0, (int) dataLength);
        } else {
            // Now we are committed to sending the object. As we spool it out,
            // check its CRC32 code to make sure there wasn't corruption between
            // the verification we did above, and us actually outputting it.
            //
            out.writeHeader(src, inflatedLength);
            long pos = dataOffset;
            long cnt = dataLength;
            while (cnt > 0) {
                final int n = (int) Math.min(cnt, buf.length);
                readFully(pos, buf, 0, n, curs);
                if (validate) {
                    assert(crc2 != null);
                    crc2.update(buf, 0, n);
                }
                out.write(buf, 0, n);
                pos += n;
                cnt -= n;
            }
            if (validate) {
                assert(crc2 != null);
                if (crc2.getValue() != expectedCRC) {
                    throw new CorruptObjectException(MessageFormat.format(
                            JGitText.get().objectAtHasBadZlibStream,
                            Long.valueOf(src.offset), getPackFile()));
                }
            }
        }
    }

    boolean invalid() {
        return invalid;
    }

    void setInvalid() {
        invalid = true;
    }

    int incrementTransientErrorCount() {
        return transientErrorCount.incrementAndGet();
    }

    void resetTransientErrorCount() {
        transientErrorCount.set(0);
    }

    private void readFully(final long position, final byte[] dstbuf,
            int dstoff, final int cnt, final WindowCursor curs)
            throws IOException {
        if (curs.copy(this, position, dstbuf, dstoff, cnt) != cnt)
            throw new EOFException();
    }

    private synchronized void beginCopyAsIs()
            throws StoredObjectRepresentationNotAvailableException {
        if (++activeCopyRawData == 1 && activeWindows == 0) {
            try {
                doOpen();
            } catch (IOException thisPackNotValid) {
                throw new StoredObjectRepresentationNotAvailableException(
                        thisPackNotValid);
            }
        }
    }

    private synchronized void endCopyAsIs() {
        if (--activeCopyRawData == 0 && activeWindows == 0)
            doClose();
    }

    synchronized boolean beginWindowCache() throws IOException {
        if (++activeWindows == 1) {
            if (activeCopyRawData == 0)
                doOpen();
            return true;
        }
        return false;
    }

    synchronized boolean endWindowCache() {
        final boolean r = --activeWindows == 0;
        if (r && activeCopyRawData == 0)
            doClose();
        return r;
    }

    private void doOpen() throws IOException {
        if (invalid) {
            openFail(true, invalidatingCause);
            throw new PackInvalidException(packFile, invalidatingCause);
        }
        try {
            synchronized (readLock) {
                fd = new RandomAccessFile(packFile, "r"); //$NON-NLS-1$
                length = fd.length();
                onOpenPack();
            }
        } catch (InterruptedIOException e) {
            // don't invalidate the pack, we are interrupted from another thread
            openFail(false, e);
            throw e;
        } catch (FileNotFoundException fn) {
            // don't invalidate the pack if opening an existing file failed
            // since it may be related to a temporary lack of resources (e.g.
            // max open files)
            openFail(!packFile.exists(), fn);
            throw fn;
        } catch (EOFException | AccessDeniedException | NoSuchFileException
                | CorruptObjectException | NoPackSignatureException
                | PackMismatchException | UnpackException
                | UnsupportedPackIndexVersionException
                | UnsupportedPackVersionException pe) {
            // exceptions signaling permanent problems with a pack
            openFail(true, pe);
            throw pe;
        } catch (IOException | RuntimeException ge) {
            // generic exceptions could be transient so we should not mark the
            // pack invalid to avoid false MissingObjectExceptions
            openFail(false, ge);
            throw ge;
        }
    }

    private void openFail(boolean invalidate, Exception cause) {
        activeWindows = 0;
        activeCopyRawData = 0;
        invalid = invalidate;
        invalidatingCause = cause;
        doClose();
    }

    private void doClose() {
        synchronized (readLock) {
            if (fd != null) {
                try {
                    fd.close();
                } catch (IOException err) {
                    // Ignore a close event. We had it open only for reading.
                    // There should not be errors related to network buffers
                    // not flushed, etc.
                }
                fd = null;
            }
        }
    }

    ByteArrayWindow read(long pos, int size) throws IOException {
        synchronized (readLock) {
            if (invalid || fd == null) {
                // Due to concurrency between a read and another packfile invalidation thread
                // one thread could come up to this point and then fail with NPE.
                // Detect the situation and throw a proper exception so that can be properly
                // managed by the main packfile search loop and the Git client won't receive
                // any failures.
                throw new PackInvalidException(packFile, invalidatingCause);
            }
            if (length < pos + size)
                size = (int) (length - pos);
            final byte[] buf = new byte[size];
            fd.seek(pos);
            fd.readFully(buf, 0, size);
            return new ByteArrayWindow(this, pos, buf);
        }
    }

    ByteWindow mmap(long pos, int size) throws IOException {
        synchronized (readLock) {
            if (length < pos + size)
                size = (int) (length - pos);

            MappedByteBuffer map;
            try {
                map = fd.getChannel().map(MapMode.READ_ONLY, pos, size);
            } catch (IOException ioe1) {
                // The most likely reason this failed is the JVM has run out
                // of virtual memory. We need to discard quickly, and try to
                // force the GC to finalize and release any existing mappings.
                //
                System.gc();
                System.runFinalization();
                map = fd.getChannel().map(MapMode.READ_ONLY, pos, size);
            }

            if (map.hasArray())
                return new ByteArrayWindow(this, pos, map.array());
            return new ByteBufferWindow(this, pos, map);
        }
    }

    private void onOpenPack() throws IOException {
        final PackIndex idx = idx();
        final byte[] buf = new byte[20];

        fd.seek(0);
        fd.readFully(buf, 0, 12);
        if (RawParseUtils.match(buf, 0, Constants.PACK_SIGNATURE) != 4) {
            throw new NoPackSignatureException(JGitText.get().notAPACKFile);
        }
        final long vers = NB.decodeUInt32(buf, 4);
        final long packCnt = NB.decodeUInt32(buf, 8);
        if (vers != 2 && vers != 3) {
            throw new UnsupportedPackVersionException(vers);
        }

        if (packCnt != idx.getObjectCount()) {
            throw new PackMismatchException(MessageFormat.format(
                    JGitText.get().packObjectCountMismatch,
                    Long.valueOf(packCnt), Long.valueOf(idx.getObjectCount()),
                    getPackFile()));
        }

        fd.seek(length - 20);
        fd.readFully(buf, 0, 20);
        if (!Arrays.equals(buf, packChecksum)) {
            throw new PackMismatchException(MessageFormat.format(
                    JGitText.get().packChecksumMismatch,
                    getPackFile(),
                    ObjectId.fromRaw(buf).name(),
                    ObjectId.fromRaw(idx.packChecksum).name()));
        }
    }

    ObjectLoader load(WindowCursor curs, long pos)
            throws IOException, LargeObjectException {
        try {
            final byte[] ib = curs.tempId;
            Delta delta = null;
            byte[] data = null;
            int type = Constants.OBJ_BAD;
            boolean cached = false;

            SEARCH: for (;;) {
                readFully(pos, ib, 0, 20, curs);
                int c = ib[0] & 0xff;
                final int typeCode = (c >> 4) & 7;
                long sz = c & 15;
                int shift = 4;
                int p = 1;
                while ((c & 0x80) != 0) {
                    c = ib[p++] & 0xff;
                    sz += ((long) (c & 0x7f)) << shift;
                    shift += 7;
                }

                switch (typeCode) {
                case Constants.OBJ_COMMIT:
                case Constants.OBJ_TREE:
                case Constants.OBJ_BLOB:
                case Constants.OBJ_TAG: {
                    if (delta != null || sz < curs.getStreamFileThreshold()) {
                        data = decompress(pos + p, (int) sz, curs);
                    }

                    if (delta != null) {
                        type = typeCode;
                        break SEARCH;
                    }

                    if (data != null) {
                        return new ObjectLoader.SmallObject(typeCode, data);
                    }
                    return new LargePackedWholeObject(typeCode, sz, pos, p,
                            this, curs.db);
                }

                case Constants.OBJ_OFS_DELTA: {
                    c = ib[p++] & 0xff;
                    long base = c & 127;
                    while ((c & 128) != 0) {
                        base += 1;
                        c = ib[p++] & 0xff;
                        base <<= 7;
                        base += (c & 127);
                    }
                    base = pos - base;
                    delta = new Delta(delta, pos, (int) sz, p, base);
                    if (sz != delta.deltaSize)
                        break SEARCH;

                    DeltaBaseCache.Entry e = curs.getDeltaBaseCache().get(this, base);
                    if (e != null) {
                        type = e.type;
                        data = e.data;
                        cached = true;
                        break SEARCH;
                    }
                    pos = base;
                    continue SEARCH;
                }

                case Constants.OBJ_REF_DELTA: {
                    readFully(pos + p, ib, 0, 20, curs);
                    long base = findDeltaBase(ObjectId.fromRaw(ib));
                    delta = new Delta(delta, pos, (int) sz, p + 20, base);
                    if (sz != delta.deltaSize)
                        break SEARCH;

                    DeltaBaseCache.Entry e = curs.getDeltaBaseCache().get(this, base);
                    if (e != null) {
                        type = e.type;
                        data = e.data;
                        cached = true;
                        break SEARCH;
                    }
                    pos = base;
                    continue SEARCH;
                }

                default:
                    throw new IOException(MessageFormat.format(
                            JGitText.get().unknownObjectType,
                            Integer.valueOf(typeCode)));
                }
            }

            // At this point there is at least one delta to apply to data.
            // (Whole objects with no deltas to apply return early above.)

            if (data == null)
                throw new IOException(JGitText.get().inMemoryBufferLimitExceeded);

            assert(delta != null);
            do {
                // Cache only the base immediately before desired object.
                if (cached)
                    cached = false;
                else if (delta.next == null)
                    curs.getDeltaBaseCache().store(this, delta.basePos, data, type);

                pos = delta.deltaPos;

                final byte[] cmds = decompress(pos + delta.hdrLen,
                        delta.deltaSize, curs);
                if (cmds == null) {
                    data = null; // Discard base in case of OutOfMemoryError
                    throw new LargeObjectException.OutOfMemory(new OutOfMemoryError());
                }

                final long sz = BinaryDelta.getResultSize(cmds);
                if (Integer.MAX_VALUE <= sz)
                    throw new LargeObjectException.ExceedsByteArrayLimit();

                final byte[] result;
                try {
                    result = new byte[(int) sz];
                } catch (OutOfMemoryError tooBig) {
                    data = null; // Discard base in case of OutOfMemoryError
                    throw new LargeObjectException.OutOfMemory(tooBig);
                }

                BinaryDelta.apply(data, cmds, result);
                data = result;
                delta = delta.next;
            } while (delta != null);

            return new ObjectLoader.SmallObject(type, data);

        } catch (DataFormatException dfe) {
            throw new CorruptObjectException(
                    MessageFormat.format(
                            JGitText.get().objectAtHasBadZlibStream,
                            Long.valueOf(pos), getPackFile()),
                    dfe);
        }
    }

    private long findDeltaBase(ObjectId baseId) throws IOException,
            MissingObjectException {
        long ofs = idx().findOffset(baseId);
        if (ofs < 0)
            throw new MissingObjectException(baseId,
                    JGitText.get().missingDeltaBase);
        return ofs;
    }

    private static class Delta {
        /** Child that applies onto this object. */
        final Delta next;

        /** Offset of the delta object. */
        final long deltaPos;

        /** Size of the inflated delta stream. */
        final int deltaSize;

        /** Total size of the delta's pack entry header (including base). */
        final int hdrLen;

        /** Offset of the base object this delta applies onto. */
        final long basePos;

        Delta(Delta next, long ofs, int sz, int hdrLen, long baseOffset) {
            this.next = next;
            this.deltaPos = ofs;
            this.deltaSize = sz;
            this.hdrLen = hdrLen;
            this.basePos = baseOffset;
        }
    }

    byte[] getDeltaHeader(WindowCursor wc, long pos)
            throws IOException, DataFormatException {
        // The delta stream starts as two variable length integers. If we
        // assume they are 64 bits each, we need 16 bytes to encode them,
        // plus 2 extra bytes for the variable length overhead. So 18 is
        // the longest delta instruction header.
        //
        final byte[] hdr = new byte[18];
        wc.inflate(this, pos, hdr, true /* headerOnly */);
        return hdr;
    }

    int getObjectType(WindowCursor curs, long pos) throws IOException {
        final byte[] ib = curs.tempId;
        for (;;) {
            readFully(pos, ib, 0, 20, curs);
            int c = ib[0] & 0xff;
            final int type = (c >> 4) & 7;

            switch (type) {
            case Constants.OBJ_COMMIT:
            case Constants.OBJ_TREE:
            case Constants.OBJ_BLOB:
            case Constants.OBJ_TAG:
                return type;

            case Constants.OBJ_OFS_DELTA: {
                int p = 1;
                while ((c & 0x80) != 0)
                    c = ib[p++] & 0xff;
                c = ib[p++] & 0xff;
                long ofs = c & 127;
                while ((c & 128) != 0) {
                    ofs += 1;
                    c = ib[p++] & 0xff;
                    ofs <<= 7;
                    ofs += (c & 127);
                }
                pos = pos - ofs;
                continue;
            }

            case Constants.OBJ_REF_DELTA: {
                int p = 1;
                while ((c & 0x80) != 0)
                    c = ib[p++] & 0xff;
                readFully(pos + p, ib, 0, 20, curs);
                pos = findDeltaBase(ObjectId.fromRaw(ib));
                continue;
            }

            default:
                throw new IOException(
                        MessageFormat.format(JGitText.get().unknownObjectType,
                                Integer.valueOf(type)));
            }
        }
    }

    long getObjectSize(WindowCursor curs, AnyObjectId id)
            throws IOException {
        final long offset = idx().findOffset(id);
        return 0 < offset ? getObjectSize(curs, offset) : -1;
    }

    long getObjectSize(WindowCursor curs, long pos)
            throws IOException {
        final byte[] ib = curs.tempId;
        readFully(pos, ib, 0, 20, curs);
        int c = ib[0] & 0xff;
        final int type = (c >> 4) & 7;
        long sz = c & 15;
        int shift = 4;
        int p = 1;
        while ((c & 0x80) != 0) {
            c = ib[p++] & 0xff;
            sz += ((long) (c & 0x7f)) << shift;
            shift += 7;
        }

        long deltaAt;
        switch (type) {
        case Constants.OBJ_COMMIT:
        case Constants.OBJ_TREE:
        case Constants.OBJ_BLOB:
        case Constants.OBJ_TAG:
            return sz;

        case Constants.OBJ_OFS_DELTA:
            c = ib[p++] & 0xff;
            while ((c & 128) != 0)
                c = ib[p++] & 0xff;
            deltaAt = pos + p;
            break;

        case Constants.OBJ_REF_DELTA:
            deltaAt = pos + p + 20;
            break;

        default:
            throw new IOException(MessageFormat.format(
                    JGitText.get().unknownObjectType, Integer.valueOf(type)));
        }

        try {
            return BinaryDelta.getResultSize(getDeltaHeader(curs, deltaAt));
        } catch (DataFormatException e) {
            throw new CorruptObjectException(MessageFormat.format(
                    JGitText.get().objectAtHasBadZlibStream, Long.valueOf(pos),
                    getPackFile()), e);
        }
    }

    LocalObjectRepresentation representation(final WindowCursor curs,
            final AnyObjectId objectId) throws IOException {
        final long pos = idx().findOffset(objectId);
        if (pos < 0)
            return null;

        final byte[] ib = curs.tempId;
        readFully(pos, ib, 0, 20, curs);
        int c = ib[0] & 0xff;
        int p = 1;
        final int typeCode = (c >> 4) & 7;
        while ((c & 0x80) != 0)
            c = ib[p++] & 0xff;

        long len = (findEndOffset(pos) - pos);
        switch (typeCode) {
        case Constants.OBJ_COMMIT:
        case Constants.OBJ_TREE:
        case Constants.OBJ_BLOB:
        case Constants.OBJ_TAG:
            return LocalObjectRepresentation.newWhole(this, pos, len - p);

        case Constants.OBJ_OFS_DELTA: {
            c = ib[p++] & 0xff;
            long ofs = c & 127;
            while ((c & 128) != 0) {
                ofs += 1;
                c = ib[p++] & 0xff;
                ofs <<= 7;
                ofs += (c & 127);
            }
            ofs = pos - ofs;
            return LocalObjectRepresentation.newDelta(this, pos, len - p, ofs);
        }

        case Constants.OBJ_REF_DELTA: {
            len -= p;
            len -= Constants.OBJECT_ID_LENGTH;
            readFully(pos + p, ib, 0, 20, curs);
            ObjectId id = ObjectId.fromRaw(ib);
            return LocalObjectRepresentation.newDelta(this, pos, len, id);
        }

        default:
            throw new IOException(
                    MessageFormat.format(JGitText.get().unknownObjectType,
                            Integer.valueOf(typeCode)));
        }
    }

    private long findEndOffset(long startOffset)
            throws IOException, CorruptObjectException {
        final long maxOffset = length - 20;
        return getReverseIdx().findNextOffset(startOffset, maxOffset);
    }

    synchronized PackBitmapIndex getBitmapIndex() throws IOException {
        if (invalid || bitmapIdxFile == null) {
            return null;
        }
        if (bitmapIdx == null) {
            final PackBitmapIndex idx;
            try {
                idx = PackBitmapIndex.open(bitmapIdxFile, idx(),
                        getReverseIdx());
            } catch (FileNotFoundException e) {
                // Once upon a time this bitmap file existed. Now it
                // has been removed. Most likely an external gc  has
                // removed this packfile and the bitmap
                bitmapIdxFile = null;
                return null;
            }

            // At this point, idx() will have set packChecksum.
            if (Arrays.equals(packChecksum, idx.packChecksum)) {
                bitmapIdx = idx;
            } else {
                bitmapIdxFile = null;
            }
        }
        return bitmapIdx;
    }

    private synchronized PackReverseIndex getReverseIdx() throws IOException {
        if (reverseIdx == null)
            reverseIdx = new PackReverseIndex(idx());
        return reverseIdx;
    }

    private boolean isCorrupt(long offset) {
        LongList list = corruptObjects;
        if (list == null)
            return false;
        synchronized (list) {
            return list.contains(offset);
        }
    }

    private void setCorrupt(long offset) {
        LongList list = corruptObjects;
        if (list == null) {
            synchronized (readLock) {
                list = corruptObjects;
                if (list == null) {
                    list = new LongList();
                    corruptObjects = list;
                }
            }
        }
        synchronized (list) {
            list.add(offset);
        }
    }

    @SuppressWarnings("nls")
    @Override
    public String toString() {
        return "Pack [packFileName=" + packFile.getName() + ", length="
                + packFile.length() + ", packChecksum="
                + ObjectId.fromRaw(packChecksum).name() + "]";
    }
}