Implement a new .git/index (aka dircache) read interface

[egit/zawir.git] / org.spearce.jgit / src / org / spearce / jgit / dircache / DirCache.java

/*
 * Copyright (C) 2008, Shawn O. Pearce <spearce@spearce.org>
 *
 * 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 Git Development Community 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.spearce.jgit.dircache;

import java.io.BufferedInputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.nio.ByteBuffer;
import java.nio.channels.FileChannel;
import java.util.Comparator;

import org.spearce.jgit.errors.CorruptObjectException;
import org.spearce.jgit.lib.Constants;
import org.spearce.jgit.lib.Repository;
import org.spearce.jgit.util.NB;

/**
 * Support for the Git dircache (aka index file).
 * <p>
 * The index file keeps track of which objects are currently checked out in the
 * working directory, and the last modified time of those working files. Changes
 * in the working directory can be detected by comparing the modification times
 * to the cached modification time within the index file.
 * <p>
 * Index files are also used during merges, where the merge happens within the
 * index file first, and the working directory is updated as a post-merge step.
 * Conflicts are stored in the index file to allow tool (and human) based
 * resolutions to be easily performed.
 */
public class DirCache {
        private static final byte[] SIG_DIRC = { 'D', 'I', 'R', 'C' };

        private static final int INFO_LEN = DirCacheEntry.INFO_LEN;

        private static final DirCacheEntry[] NO_ENTRIES = {};

        static final Comparator<DirCacheEntry> ENT_CMP = new Comparator<DirCacheEntry>() {
                public int compare(final DirCacheEntry o1, final DirCacheEntry o2) {
                        final int cr = cmp(o1, o2);
                        if (cr != 0)
                                return cr;
                        return o1.getStage() - o2.getStage();
                }
        };

        static int cmp(final DirCacheEntry a, final DirCacheEntry b) {
                return cmp(a.path, a.path.length, b);
        }

        static int cmp(final byte[] aPath, final int aLen, final DirCacheEntry b) {
                return cmp(aPath, aLen, b.path, b.path.length);
        }

        static int cmp(final byte[] aPath, final int aLen, final byte[] bPath,
                        final int bLen) {
                for (int cPos = 0; cPos < aLen && cPos < bLen; cPos++) {
                        final int cmp = (aPath[cPos] & 0xff) - (bPath[cPos] & 0xff);
                        if (cmp != 0)
                                return cmp;
                }
                return aLen - bLen;
        }

        /**
         * Create a new in-core index representation and read an index from disk.
         * <p>
         * The new index will be read before it is returned to the caller. Read
         * failures are reported as exceptions and therefore prevent the method from
         * returning a partially populated index.
         *
         * @param indexLocation
         *            location of the index file on disk.
         * @return a cache representing the contents of the specified index file (if
         *         it exists) or an empty cache if the file does not exist.
         * @throws IOException
         *             the index file is present but could not be read.
         * @throws CorruptObjectException
         *             the index file is using a format or extension that this
         *             library does not support.
         */
        public static DirCache read(final File indexLocation)
                        throws CorruptObjectException, IOException {
                final DirCache c = new DirCache(indexLocation);
                c.read();
                return c;
        }

        /**
         * Create a new in-core index representation and read an index from disk.
         * <p>
         * The new index will be read before it is returned to the caller. Read
         * failures are reported as exceptions and therefore prevent the method from
         * returning a partially populated index.
         *
         * @param db
         *            repository the caller wants to read the default index of.
         * @return a cache representing the contents of the specified index file (if
         *         it exists) or an empty cache if the file does not exist.
         * @throws IOException
         *             the index file is present but could not be read.
         * @throws CorruptObjectException
         *             the index file is using a format or extension that this
         *             library does not support.
         */
        public static DirCache read(final Repository db)
                        throws CorruptObjectException, IOException {
                return read(new File(db.getDirectory(), "index"));
        }

        /** Location of the current version of the index file. */
        private final File liveFile;

        /** Modification time of the file at the last read/write we did. */
        private long lastModified;

        /** Individual file index entries, sorted by path name. */
        private DirCacheEntry[] sortedEntries;

        /** Number of positions within {@link #sortedEntries} that are valid. */
        private int entryCnt;

        /**
         * Create a new in-core index representation.
         * <p>
         * The new index will be empty. Callers may wish to read from the on disk
         * file first with {@link #read()}.
         *
         * @param indexLocation
         *            location of the index file on disk.
         */
        public DirCache(final File indexLocation) {
                liveFile = indexLocation;
                clear();
        }

        /**
         * Read the index from disk, if it has changed on disk.
         * <p>
         * This method tries to avoid loading the index if it has not changed since
         * the last time we consulted it. A missing index file will be treated as
         * though it were present but had no file entries in it.
         *
         * @throws IOException
         *             the index file is present but could not be read. This
         *             DirCache instance may not be populated correctly.
         * @throws CorruptObjectException
         *             the index file is using a format or extension that this
         *             library does not support.
         */
        public void read() throws IOException, CorruptObjectException {
                if (!liveFile.exists())
                        clear();
                else if (liveFile.lastModified() != lastModified) {
                        try {
                                final FileInputStream inStream = new FileInputStream(liveFile);
                                try {
                                        clear();
                                        readFrom(inStream);
                                } finally {
                                        try {
                                                inStream.close();
                                        } catch (IOException err2) {
                                                // Ignore any close failures.
                                        }
                                }
                        } catch (FileNotFoundException fnfe) {
                                // Someone must have deleted it between our exists test
                                // and actually opening the path. That's fine, its empty.
                                //
                                clear();
                        }
                }
        }

        /** Empty this index, removing all entries. */
        public void clear() {
                lastModified = 0;
                sortedEntries = NO_ENTRIES;
                entryCnt = 0;
        }

        private void readFrom(final FileInputStream inStream) throws IOException,
                        CorruptObjectException {
                final FileChannel fd = inStream.getChannel();
                final long sizeOnDisk = fd.size();
                final BufferedInputStream in = new BufferedInputStream(inStream);

                // Read the index header and verify we understand it.
                //
                final byte[] hdr = new byte[12];
                NB.readFully(in, hdr, 0, 12);
                if (!is_DIRC(hdr))
                        throw new CorruptObjectException("Not a DIRC file.");
                final int ver = NB.decodeInt32(hdr, 4);
                if (ver != 2)
                        throw new CorruptObjectException("Unknown DIRC version " + ver);
                entryCnt = NB.decodeInt32(hdr, 8);
                if (entryCnt < 0)
                        throw new CorruptObjectException("DIRC has too many entries.");

                // Load the individual file entries.
                //
                final byte[] infos = new byte[INFO_LEN * entryCnt];
                sortedEntries = new DirCacheEntry[entryCnt];
                for (int i = 0; i < entryCnt; i++)
                        sortedEntries[i] = new DirCacheEntry(infos, i * INFO_LEN, in);
                lastModified = liveFile.lastModified();

                // After the file entries are index extensions.
                //
                while (fd.position() - in.available() < sizeOnDisk - 20) {
                        NB.readFully(in, hdr, 0, 8);
                        switch (NB.decodeInt32(hdr, 0)) {
                        default:
                                if (hdr[0] >= 'A' && hdr[0] <= 'Z') {
                                        // The extension is optional and is here only as
                                        // a performance optimization. Since we do not
                                        // understand it, we can safely skip past it.
                                        //
                                        in.skip(NB.decodeInt32(hdr, 4));
                                } else {
                                        // The extension is not an optimization and is
                                        // _required_ to understand this index format.
                                        // Since we did not trap it above we must abort.
                                        //
                                        throw new CorruptObjectException("DIRC extension '"
                                                        + Constants.CHARSET.decode(
                                                                        ByteBuffer.wrap(hdr, 0, 4)).toString()
                                                        + "' not supported by this version.");
                                }
                        }
                }
        }

        private static boolean is_DIRC(final byte[] hdr) {
                if (hdr.length < SIG_DIRC.length)
                        return false;
                for (int i = 0; i < SIG_DIRC.length; i++)
                        if (hdr[i] != SIG_DIRC[i])
                                return false;
                return true;
        }

        /**
         * Locate the position a path's entry is at in the index.
         * <p>
         * If there is at least one entry in the index for this path the position of
         * the lowest stage is returned. Subsequent stages can be identified by
         * testing consecutive entries until the path differs.
         * <p>
         * If no path matches the entry -(position+1) is returned, where position is
         * the location it would have gone within the index.
         *
         * @param path
         *            the path to search for.
         * @return if >= 0 then the return value is the position of the entry in the
         *         index; pass to {@link #getEntry(int)} to obtain the entry
         *         information. If < 0 the entry does not exist in the index.
         */
        public int findEntry(final String path) {
                if (entryCnt == 0)
                        return -1;
                final byte[] p = Constants.encode(path);
                return findEntry(p, p.length);
        }

        int findEntry(final byte[] p, final int pLen) {
                int low = 0;
                int high = entryCnt;
                do {
                        int mid = (low + high) >> 1;
                        final int cmp = cmp(p, pLen, sortedEntries[mid]);
                        if (cmp < 0)
                                high = mid;
                        else if (cmp == 0) {
                                while (mid > 0 && cmp(p, pLen, sortedEntries[mid - 1]) == 0)
                                        mid--;
                                return mid;
                        } else
                                low = mid + 1;
                } while (low < high);
                return -(low + 1);
        }

        /**
         * Determine the next index position past all entries with the same name.
         * <p>
         * As index entries are sorted by path name, then stage number, this method
         * advances the supplied position to the first position in the index whose
         * path name does not match the path name of the supplied position's entry.
         *
         * @param position
         *            entry position of the path that should be skipped.
         * @return position of the next entry whose path is after the input.
         */
        public int nextEntry(final int position) {
                DirCacheEntry last = sortedEntries[position];
                int nextIdx = position + 1;
                while (nextIdx < entryCnt) {
                        final DirCacheEntry next = sortedEntries[nextIdx];
                        if (cmp(last, next) != 0)
                                break;
                        last = next;
                        nextIdx++;
                }
                return nextIdx;
        }

        /**
         * Total number of file entries stored in the index.
         * <p>
         * This count includes unmerged stages for a file entry if the file is
         * currently conflicted in a merge. This means the total number of entries
         * in the index may be up to 3 times larger than the number of files in the
         * working directory.
         * <p>
         * Note that this value counts only <i>files</i>.
         *
         * @return number of entries available.
         * @see #getEntry(int)
         */
        public int getEntryCount() {
                return entryCnt;
        }

        /**
         * Get a specific entry.
         *
         * @param i
         *            position of the entry to get.
         * @return the entry at position <code>i</code>.
         */
        public DirCacheEntry getEntry(final int i) {
                return sortedEntries[i];
        }

        /**
         * Get a specific entry.
         *
         * @param path
         *            the path to search for.
         * @return the entry at position <code>i</code>.
         */
        public DirCacheEntry getEntry(final String path) {
                final int i = findEntry(path);
                return i < 0 ? null : sortedEntries[i];
        }
}