/*
    * Copyright (C) 2008, 2010, Google Inc.
    * Copyright (C) 2008, Shawn O. Pearce <spearce@spearce.org>
    * Copyright (C) 2011, 2020, Matthias Sohn <matthias.sohn@sap.com> 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.dircache;
  
  import static java.nio.charset.StandardCharsets.ISO_8859_1;
  
  import java.io.BufferedInputStream;
  import java.io.BufferedOutputStream;
  import java.io.EOFException;
  import java.io.File;
  import java.io.FileNotFoundException;
  import java.io.IOException;
  import java.io.InputStream;
  import java.io.OutputStream;
  import java.security.DigestOutputStream;
  import java.security.MessageDigest;
  import java.text.MessageFormat;
  import java.time.Instant;
  import java.util.ArrayList;
  import java.util.Arrays;
  import java.util.Comparator;
  import java.util.List;
  
  import org.eclipse.jgit.errors.CorruptObjectException;
  import org.eclipse.jgit.errors.IndexReadException;
  import org.eclipse.jgit.errors.LockFailedException;
  import org.eclipse.jgit.errors.UnmergedPathException;
  import org.eclipse.jgit.events.IndexChangedEvent;
  import org.eclipse.jgit.events.IndexChangedListener;
  import org.eclipse.jgit.internal.JGitText;
  import org.eclipse.jgit.internal.storage.file.FileSnapshot;
  import org.eclipse.jgit.internal.storage.file.LockFile;
  import org.eclipse.jgit.lib.AnyObjectId;
  import org.eclipse.jgit.lib.Config;
  import org.eclipse.jgit.lib.Config.ConfigEnum;
  import org.eclipse.jgit.lib.ConfigConstants;
  import org.eclipse.jgit.lib.Constants;
  import org.eclipse.jgit.lib.ObjectId;
  import org.eclipse.jgit.lib.ObjectInserter;
  import org.eclipse.jgit.lib.ObjectReader;
  import org.eclipse.jgit.lib.Repository;
  import org.eclipse.jgit.treewalk.FileTreeIterator;
  import org.eclipse.jgit.treewalk.TreeWalk;
  import org.eclipse.jgit.treewalk.TreeWalk.OperationType;
  import org.eclipse.jgit.treewalk.filter.PathFilterGroup;
  import org.eclipse.jgit.util.FS;
  import org.eclipse.jgit.util.IO;
  import org.eclipse.jgit.util.MutableInteger;
  import org.eclipse.jgit.util.NB;
  import org.eclipse.jgit.util.TemporaryBuffer;
  import org.eclipse.jgit.util.io.SilentFileInputStream;
  
  /**
   * 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 EXT_TREE = 0x54524545 /* 'TREE' */;
  
  	private static final DirCacheEntry[] NO_ENTRIES = {};
  
  	private static final byte[] NO_CHECKSUM = {};
  
  	static final Comparator<DirCacheEntry> ENT_CMP = (DirCacheEntry o1,
  			DirCacheEntry o2) -> {
  		final int cr = cmp(o1, o2);
  		if (cr != 0)
  			return cr;
  		return o1.getStage() - o2.getStage();
  	};
  
  	static int cmp(DirCacheEntry../../../../org/eclipse/jgit/dircache/DirCacheEntry.html#DirCacheEntry">DirCacheEntry a, DirCacheEntry b) {
  		return cmp(a.path, a.path.length, b);
  	}
  
  	static int cmp(byte[] aPath, int aLen, 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 empty index which is never stored on disk.
 	 *
 	 * @return an empty cache which has no backing store file. The cache may not
 	 *         be read or written, but it may be queried and updated (in
 	 *         memory).
 	 */
 	public static DirCache newInCore() {
 		return new DirCache(null, null);
 	}
 
 	/**
 	 * Create a new in memory index read from the contents of a tree.
 	 *
 	 * @param reader
 	 *            reader to access the tree objects from a repository.
 	 * @param treeId
 	 *            tree to read. Must identify a tree, not a tree-ish.
 	 * @return a new cache which has no backing store file, but contains the
 	 *         contents of {@code treeId}.
 	 * @throws java.io.IOException
 	 *             one or more trees not available from the ObjectReader.
 	 * @since 4.2
 	 */
 	public static DirCache read(ObjectReader reader, AnyObjectId treeId)
 			throws IOException {
 		DirCache d = newInCore();
 		DirCacheBuilder b = d.builder();
 		b.addTree(null, DirCacheEntry.STAGE_0, reader, treeId);
 		b.finish();
 		return d;
 	}
 
 	/**
 	 * 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 repository
 	 *            repository containing the index to read
 	 * @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 java.io.IOException
 	 *             the index file is present but could not be read.
 	 * @throws org.eclipse.jgit.errors.CorruptObjectException
 	 *             the index file is using a format or extension that this
 	 *             library does not support.
 	 */
 	public static DirCache read(Repository repository)
 			throws CorruptObjectException, IOException {
 		final DirCache c = read(repository.getIndexFile(), repository.getFS());
 		c.repository = repository;
 		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 indexLocation
 	 *            location of the index file on disk.
 	 * @param fs
 	 *            the file system abstraction which will be necessary to perform
 	 *            certain file system operations.
 	 * @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 java.io.IOException
 	 *             the index file is present but could not be read.
 	 * @throws org.eclipse.jgit.errors.CorruptObjectException
 	 *             the index file is using a format or extension that this
 	 *             library does not support.
 	 */
 	public static DirCache read(File indexLocation, FS fs)
 			throws CorruptObjectException, IOException {
 		final DirCache/DirCache.html#DirCache">DirCache c = new DirCache(indexLocation, fs);
 		c.read();
 		return c;
 	}
 
 	/**
 	 * Create a new in-core index representation, lock it, and read from disk.
 	 * <p>
 	 * The new index will be locked and then 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. On read failure,
 	 * the lock is released.
 	 *
 	 * @param indexLocation
 	 *            location of the index file on disk.
 	 * @param fs
 	 *            the file system abstraction which will be necessary to perform
 	 *            certain file system operations.
 	 * @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 java.io.IOException
 	 *             the index file is present but could not be read, or the lock
 	 *             could not be obtained.
 	 * @throws org.eclipse.jgit.errors.CorruptObjectException
 	 *             the index file is using a format or extension that this
 	 *             library does not support.
 	 */
 	public static DirCache lock(File indexLocation, FS fs)
 			throws CorruptObjectException, IOException {
 		final DirCache/DirCache.html#DirCache">DirCache c = new DirCache(indexLocation, fs);
 		if (!c.lock())
 			throw new LockFailedException(indexLocation);
 
 		try {
 			c.read();
 		} catch (IOException | RuntimeException | Error e) {
 			c.unlock();
 			throw e;
 		}
 
 		return c;
 	}
 
 	/**
 	 * Create a new in-core index representation, lock it, and read from disk.
 	 * <p>
 	 * The new index will be locked and then 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. On read failure,
 	 * the lock is released.
 	 *
 	 * @param repository
 	 *            repository containing the index to lock and read
 	 * @param indexChangedListener
 	 *            listener to be informed when DirCache is committed
 	 * @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 java.io.IOException
 	 *             the index file is present but could not be read, or the lock
 	 *             could not be obtained.
 	 * @throws org.eclipse.jgit.errors.CorruptObjectException
 	 *             the index file is using a format or extension that this
 	 *             library does not support.
 	 * @since 2.0
 	 */
 	public static DirCache lock(final Repository repository,
 			final IndexChangedListener indexChangedListener)
 			throws CorruptObjectException, IOException {
 		DirCache c = lock(repository.getIndexFile(), repository.getFS(),
 				indexChangedListener);
 		c.repository = repository;
 		return c;
 	}
 
 	/**
 	 * Create a new in-core index representation, lock it, and read from disk.
 	 * <p>
 	 * The new index will be locked and then 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. On read failure,
 	 * the lock is released.
 	 *
 	 * @param indexLocation
 	 *            location of the index file on disk.
 	 * @param fs
 	 *            the file system abstraction which will be necessary to perform
 	 *            certain file system operations.
 	 * @param indexChangedListener
 	 *            listener to be informed when DirCache is committed
 	 * @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 java.io.IOException
 	 *             the index file is present but could not be read, or the lock
 	 *             could not be obtained.
 	 * @throws org.eclipse.jgit.errors.CorruptObjectException
 	 *             the index file is using a format or extension that this
 	 *             library does not support.
 	 */
 	public static DirCache lock(final File indexLocation, final FS fs,
 			IndexChangedListener indexChangedListener)
 			throws CorruptObjectException,
 			IOException {
 		DirCache c = lock(indexLocation, fs);
 		c.registerIndexChangedListener(indexChangedListener);
 		return c;
 	}
 
 	/** Location of the current version of the index file. */
 	private final File liveFile;
 
 	/** Individual file index entries, sorted by path name. */
 	private DirCacheEntry[] sortedEntries;
 
 	/** Number of positions within {@link #sortedEntries} that are valid. */
 	private int entryCnt;
 
 	/** Cache tree for this index; null if the cache tree is not available. */
 	private DirCacheTree tree;
 
 	/** Our active lock (if we hold it); null if we don't have it locked. */
 	private LockFile myLock;
 
 	/** Keep track of whether the index has changed or not */
 	private FileSnapshot snapshot;
 
 	/** index checksum when index was read from disk */
 	private byte[] readIndexChecksum;
 
 	/** index checksum when index was written to disk */
 	private byte[] writeIndexChecksum;
 
 	/** listener to be informed on commit */
 	private IndexChangedListener indexChangedListener;
 
 	/** Repository containing this index */
 	private Repository repository;
 
 	/** If we read this index from disk, the original format. */
 	private DirCacheVersion version;
 
 	/**
 	 * 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.
 	 * @param fs
 	 *            the file system abstraction which will be necessary to perform
 	 *            certain file system operations.
 	 */
 	public DirCache(File indexLocation, FS fs) {
 		liveFile = indexLocation;
 		clear();
 	}
 
 	/**
 	 * Create a new builder to update this cache.
 	 * <p>
 	 * Callers should add all entries to the builder, then use
 	 * {@link org.eclipse.jgit.dircache.DirCacheBuilder#finish()} to update this
 	 * instance.
 	 *
 	 * @return a new builder instance for this cache.
 	 */
 	public DirCacheBuilder builder() {
 		return new DirCacheBuilder(this, entryCnt + 16);
 	}
 
 	/**
 	 * Create a new editor to recreate this cache.
 	 * <p>
 	 * Callers should add commands to the editor, then use
 	 * {@link org.eclipse.jgit.dircache.DirCacheEditor#finish()} to update this
 	 * instance.
 	 *
 	 * @return a new builder instance for this cache.
 	 */
 	public DirCacheEditor editor() {
 		return new DirCacheEditor(this, entryCnt + 16);
 	}
 
 	DirCacheVersion getVersion() {
 		return version;
 	}
 
 	void replace(DirCacheEntry[] e, int cnt) {
 		sortedEntries = e;
 		entryCnt = cnt;
 		tree = null;
 	}
 
 	/**
 	 * 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 java.io.IOException
 	 *             the index file is present but could not be read. This
 	 *             DirCache instance may not be populated correctly.
 	 * @throws org.eclipse.jgit.errors.CorruptObjectException
 	 *             the index file is using a format or extension that this
 	 *             library does not support.
 	 */
 	public void read() throws IOException, CorruptObjectException {
 		if (liveFile == null)
 			throw new IOException(JGitText.get().dirCacheDoesNotHaveABackingFile);
 		if (!liveFile.exists())
 			clear();
 		else if (snapshot == null || snapshot.isModified(liveFile)) {
 			try (SilentFileInputStreamm.html#SilentFileInputStream">SilentFileInputStream inStream = new SilentFileInputStream(
 					liveFile)) {
 				clear();
 				readFrom(inStream);
 			} catch (FileNotFoundException fnfe) {
 				if (liveFile.exists()) {
 					// Panic: the index file exists but we can't read it
 					throw new IndexReadException(
 							MessageFormat.format(JGitText.get().cannotReadIndex,
 									liveFile.getAbsolutePath(), fnfe));
 				}
 				// Someone must have deleted it between our exists test
 				// and actually opening the path. That's fine, its empty.
 				//
 				clear();
 			}
 			snapshot = FileSnapshot.save(liveFile);
 		}
 	}
 
 	/**
 	 * Whether the memory state differs from the index file
 	 *
 	 * @return {@code true} if the memory state differs from the index file
 	 * @throws java.io.IOException
 	 */
 	public boolean isOutdated() throws IOException {
 		if (liveFile == null || !liveFile.exists())
 			return false;
 		return snapshot == null || snapshot.isModified(liveFile);
 	}
 
 	/**
 	 * Empty this index, removing all entries.
 	 */
 	public void clear() {
 		snapshot = null;
 		sortedEntries = NO_ENTRIES;
 		entryCnt = 0;
 		tree = null;
 		readIndexChecksum = NO_CHECKSUM;
 	}
 
 	private void readFrom(InputStream inStream) throws IOException,
 			CorruptObjectException {
 		final BufferedInputStream in = new BufferedInputStream(inStream);
 		final MessageDigest md = Constants.newMessageDigest();
 
 		// Read the index header and verify we understand it.
 		//
 		final byte[] hdr = new byte[20];
 		IO.readFully(in, hdr, 0, 12);
 		md.update(hdr, 0, 12);
 		if (!is_DIRC(hdr))
 			throw new CorruptObjectException(JGitText.get().notADIRCFile);
 		int versionCode = NB.decodeInt32(hdr, 4);
 		DirCacheVersion ver = DirCacheVersion.fromInt(versionCode);
 		if (ver == null) {
 			throw new CorruptObjectException(
 					MessageFormat.format(JGitText.get().unknownDIRCVersion,
 							Integer.valueOf(versionCode)));
 		}
 		boolean extended = false;
 		switch (ver) {
 		case DIRC_VERSION_MINIMUM:
 			break;
 		case DIRC_VERSION_EXTENDED:
 		case DIRC_VERSION_PATHCOMPRESS:
 			extended = true;
 			break;
 		default:
 			throw new CorruptObjectException(MessageFormat
 					.format(JGitText.get().unknownDIRCVersion, ver));
 		}
 		version = ver;
 		entryCnt = NB.decodeInt32(hdr, 8);
 		if (entryCnt < 0)
 			throw new CorruptObjectException(JGitText.get().DIRCHasTooManyEntries);
 
 		snapshot = FileSnapshot.save(liveFile);
 		Instant smudge = snapshot.lastModifiedInstant();
 
 		// Load the individual file entries.
 		//
 		final int infoLength = DirCacheEntry.getMaximumInfoLength(extended);
 		final byte[] infos = new byte[infoLength * entryCnt];
 		sortedEntries = new DirCacheEntry[entryCnt];
 
 		final MutableInteger.html#MutableInteger">MutableInteger infoAt = new MutableInteger();
 		for (int i = 0; i < entryCnt; i++) {
 			sortedEntries[i] = new DirCacheEntry(infos, infoAt, in, md, smudge,
 					version, i == 0 ? null : sortedEntries[i - 1]);
 		}
 
 		// After the file entries are index extensions, and then a footer.
 		//
 		for (;;) {
 			in.mark(21);
 			IO.readFully(in, hdr, 0, 20);
 			if (in.read() < 0) {
 				// No extensions present; the file ended where we expected.
 				//
 				break;
 			}
 
 			in.reset();
 			md.update(hdr, 0, 8);
 			IO.skipFully(in, 8);
 
 			long sz = NB.decodeUInt32(hdr, 4);
 			switch (NB.decodeInt32(hdr, 0)) {
 			case EXT_TREE: {
 				if (Integer.MAX_VALUE < sz) {
 					throw new CorruptObjectException(MessageFormat.format(
 							JGitText.get().DIRCExtensionIsTooLargeAt,
 							formatExtensionName(hdr), Long.valueOf(sz)));
 				}
 				final byte[] raw = new byte[(int) sz];
 				IO.readFully(in, raw, 0, raw.length);
 				md.update(raw, 0, raw.length);
 				tree = new DirCacheTree(raw, new MutableInteger(), null);
 				break;
 			}
 			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, after
 					// we include its data in our checksum.
 					//
 					skipOptionalExtension(in, md, hdr, sz);
 				} 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(MessageFormat.format(JGitText.get().DIRCExtensionNotSupportedByThisVersion
 							, formatExtensionName(hdr)));
 				}
 			}
 		}
 
 		readIndexChecksum = md.digest();
 		if (!Arrays.equals(readIndexChecksum, hdr)) {
 			throw new CorruptObjectException(JGitText.get().DIRCChecksumMismatch);
 		}
 	}
 
 	private void skipOptionalExtension(final InputStream in,
 			final MessageDigest md, final byte[] hdr, long sz)
 			throws IOException {
 		final byte[] b = new byte[4096];
 		while (0 < sz) {
 			int n = in.read(b, 0, (int) Math.min(b.length, sz));
 			if (n < 0) {
 				throw new EOFException(
 						MessageFormat.format(
 								JGitText.get().shortReadOfOptionalDIRCExtensionExpectedAnotherBytes,
 								formatExtensionName(hdr), Long.valueOf(sz)));
 			}
 			md.update(b, 0, n);
 			sz -= n;
 		}
 	}
 
 	private static String formatExtensionName(byte[] hdr) {
 		return "'" + new String(hdr, 0, 4, ISO_8859_1) + "'"; //$NON-NLS-1$ //$NON-NLS-2$
 	}
 
 	private static boolean is_DIRC(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;
 	}
 
 	/**
 	 * Try to establish an update lock on the cache file.
 	 *
 	 * @return true if the lock is now held by the caller; false if it is held
 	 *         by someone else.
 	 * @throws java.io.IOException
 	 *             the output file could not be created. The caller does not
 	 *             hold the lock.
 	 */
 	public boolean lock() throws IOException {
 		if (liveFile == null)
 			throw new IOException(JGitText.get().dirCacheDoesNotHaveABackingFile);
 		final LockFiletorage/file/LockFile.html#LockFile">LockFile tmp = new LockFile(liveFile);
 		if (tmp.lock()) {
 			tmp.setNeedStatInformation(true);
 			myLock = tmp;
 			return true;
 		}
 		return false;
 	}
 
 	/**
 	 * Write the entry records from memory to disk.
 	 * <p>
 	 * The cache must be locked first by calling {@link #lock()} and receiving
 	 * true as the return value. Applications are encouraged to lock the index,
 	 * then invoke {@link #read()} to ensure the in-memory data is current,
 	 * prior to updating the in-memory entries.
 	 * <p>
 	 * Once written the lock is closed and must be either committed with
 	 * {@link #commit()} or rolled back with {@link #unlock()}.
 	 *
 	 * @throws java.io.IOException
 	 *             the output file could not be created. The caller no longer
 	 *             holds the lock.
 	 */
 	public void write() throws IOException {
 		final LockFile tmp = myLock;
 		requireLocked(tmp);
 		try (OutputStream o = tmp.getOutputStream();
 				OutputStream bo = new BufferedOutputStream(o)) {
 			writeTo(liveFile.getParentFile(), bo);
 		} catch (IOException | RuntimeException | Error err) {
 			tmp.unlock();
 			throw err;
 		}
 	}
 
 	void writeTo(File dir, OutputStream os) throws IOException {
 		final MessageDigest foot = Constants.newMessageDigest();
 		final DigestOutputStream dos = new DigestOutputStream(os, foot);
 
 		if (version == null && this.repository != null) {
 			// A new DirCache is being written.
 			DirCacheConfig config = repository.getConfig()
 					.get(DirCacheConfig::new);
 			version = config.getIndexVersion();
 		}
 		if (version == null
 				|| version == DirCacheVersion.DIRC_VERSION_MINIMUM) {
 			version = DirCacheVersion.DIRC_VERSION_MINIMUM;
 			for (int i = 0; i < entryCnt; i++) {
 				if (sortedEntries[i].isExtended()) {
 					version = DirCacheVersion.DIRC_VERSION_EXTENDED;
 					break;
 				}
 			}
 		}
 
 		// Write the header.
 		//
 		final byte[] tmp = new byte[128];
 		System.arraycopy(SIG_DIRC, 0, tmp, 0, SIG_DIRC.length);
 		NB.encodeInt32(tmp, 4, version.getVersionCode());
 		NB.encodeInt32(tmp, 8, entryCnt);
 		dos.write(tmp, 0, 12);
 
 		// Write the individual file entries.
 
 		Instant smudge;
 		if (myLock != null) {
 			// For new files we need to smudge the index entry
 			// if they have been modified "now". Ideally we'd
 			// want the timestamp when we're done writing the index,
 			// so we use the current timestamp as a approximation.
 			myLock.createCommitSnapshot();
 			snapshot = myLock.getCommitSnapshot();
 			smudge = snapshot.lastModifiedInstant();
 		} else {
 			// Used in unit tests only
 			smudge = Instant.EPOCH;
 		}
 
 		// Check if tree is non-null here since calling updateSmudgedEntries
 		// will automatically build it via creating a DirCacheIterator
 		final boolean writeTree = tree != null;
 
 		if (repository != null && entryCnt > 0)
 			updateSmudgedEntries();
 
 		for (int i = 0; i < entryCnt; i++) {
 			final DirCacheEntry e = sortedEntries[i];
 			if (e.mightBeRacilyClean(smudge)) {
 				e.smudgeRacilyClean();
 			}
 			e.write(dos, version, i == 0 ? null : sortedEntries[i - 1]);
 		}
 
 		if (writeTree) {
 			@SuppressWarnings("resource") // Explicitly closed in try block, and
 											// destroyed in finally
 			TemporaryBuffer bb = new TemporaryBuffer.LocalFile(dir, 5 << 20);
 			try {
 				tree.write(tmp, bb);
 				bb.close();
 
 				NB.encodeInt32(tmp, 0, EXT_TREE);
 				NB.encodeInt32(tmp, 4, (int) bb.length());
 				dos.write(tmp, 0, 8);
 				bb.writeTo(dos, null);
 			} finally {
 				bb.destroy();
 			}
 		}
 		writeIndexChecksum = foot.digest();
 		os.write(writeIndexChecksum);
 		os.close();
 	}
 
 	/**
 	 * Commit this change and release the lock.
 	 * <p>
 	 * If this method fails (returns false) the lock is still released.
 	 *
 	 * @return true if the commit was successful and the file contains the new
 	 *         data; false if the commit failed and the file remains with the
 	 *         old data.
 	 * @throws java.lang.IllegalStateException
 	 *             the lock is not held.
 	 */
 	public boolean commit() {
 		final LockFile tmp = myLock;
 		requireLocked(tmp);
 		myLock = null;
 		if (!tmp.commit()) {
 			return false;
 		}
 		snapshot = tmp.getCommitSnapshot();
 		if (indexChangedListener != null
 				&& !Arrays.equals(readIndexChecksum, writeIndexChecksum)) {
 			indexChangedListener.onIndexChanged(new IndexChangedEvent(true));
 		}
 		return true;
 	}
 
 	private void requireLocked(LockFile tmp) {
 		if (liveFile == null)
 			throw new IllegalStateException(JGitText.get().dirCacheIsNotLocked);
 		if (tmp == null)
 			throw new IllegalStateException(MessageFormat.format(JGitText.get().dirCacheFileIsNotLocked
 					, liveFile.getAbsolutePath()));
 	}
 
 	/**
 	 * Unlock this file and abort this change.
 	 * <p>
 	 * The temporary file (if created) is deleted before returning.
 	 */
 	public void unlock() {
 		final LockFile tmp = myLock;
 		if (tmp != null) {
 			myLock = null;
 			tmp.unlock();
 		}
 	}
 
 	/**
 	 * Locate the position a path's entry is at in the index. For details refer
 	 * to #findEntry(byte[], int).
 	 *
 	 * @param path
 	 *            the path to search for.
 	 * @return if &gt;= 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 &lt; 0 the entry does not exist in the index.
 	 */
 	public int findEntry(String path) {
 		final byte[] p = Constants.encode(path);
 		return findEntry(p, p.length);
 	}
 
 	/**
 	 * 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 p
 	 *            the byte array starting with the path to search for.
 	 * @param pLen
 	 *            the length of the path in bytes
 	 * @return if &gt;= 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 &lt; 0 the entry does not exist in the index.
 	 * @since 3.4
 	 */
 	public int findEntry(byte[] p, int pLen) {
 		return findEntry(0, p, pLen);
 	}
 
 	int findEntry(int low, byte[] p, int pLen) {
 		int high = entryCnt;
 		while (low < high) {
 			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;
 		}
 		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(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;
 	}
 
 	int nextEntry(byte[] p, int pLen, int nextIdx) {
 		while (nextIdx < entryCnt) {
 			final DirCacheEntry next = sortedEntries[nextIdx];
 			if (!DirCacheTree.peq(p, next.path, pLen))
 				break;
 			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(int i) {
 		return sortedEntries[i];
 	}
 
 	/**
 	 * Get a specific entry.
 	 *
 	 * @param path
 	 *            the path to search for.
 	 * @return the entry for the given <code>path</code>.
 	 */
 	public DirCacheEntry getEntry(String path) {
 		final int i = findEntry(path);
 		return i < 0 ? null : sortedEntries[i];
 	}
 
 	/**
 	 * Recursively get all entries within a subtree.
 	 *
 	 * @param path
 	 *            the subtree path to get all entries within.
 	 * @return all entries recursively contained within the subtree.
 	 */
 	public DirCacheEntry[] getEntriesWithin(String path) {
 		if (path.length() == 0) {
 			DirCacheEntry[] r = new DirCacheEntry[entryCnt];
 			System.arraycopy(sortedEntries, 0, r, 0, entryCnt);
 			return r;
 		}
 		if (!path.endsWith("/")) //$NON-NLS-1$
 			path += "/"; //$NON-NLS-1$
 		final byte[] p = Constants.encode(path);
 		final int pLen = p.length;
 
 		int eIdx = findEntry(p, pLen);
 		if (eIdx < 0)
 			eIdx = -(eIdx + 1);
 		final int lastIdx = nextEntry(p, pLen, eIdx);
 		final DirCacheEntryheEntry.html#DirCacheEntry">DirCacheEntry[] r = new DirCacheEntry[lastIdx - eIdx];
 		System.arraycopy(sortedEntries, eIdx, r, 0, r.length);
 		return r;
 	}
 
 	void toArray(final int i, final DirCacheEntry[] dst, final int off,
 			final int cnt) {
 		System.arraycopy(sortedEntries, i, dst, off, cnt);
 	}
 
 	/**
 	 * Obtain (or build) the current cache tree structure.
 	 * <p>
 	 * This method can optionally recreate the cache tree, without flushing the
 	 * tree objects themselves to disk.
 	 *
 	 * @param build
 	 *            if true and the cache tree is not present in the index it will
 	 *            be generated and returned to the caller.
 	 * @return the cache tree; null if there is no current cache tree available
 	 *         and <code>build</code> was false.
 	 */
 	public DirCacheTree getCacheTree(boolean build) {
 		if (build) {
 			if (tree == null)
 				tree = new DirCacheTree();
 			tree.validate(sortedEntries, entryCnt, 0, 0);
 		}
 		return tree;
 	}
 
 	/**
 	 * Write all index trees to the object store, returning the root tree.
 	 *
 	 * @param ow
 	 *            the writer to use when serializing to the store. The caller is
 	 *            responsible for flushing the inserter before trying to use the
 	 *            returned tree identity.
 	 * @return identity for the root tree.
 	 * @throws org.eclipse.jgit.errors.UnmergedPathException
 	 *             one or more paths contain higher-order stages (stage &gt; 0),
 	 *             which cannot be stored in a tree object.
 	 * @throws java.lang.IllegalStateException
 	 *             one or more paths contain an invalid mode which should never
 	 *             appear in a tree object.
 	 * @throws java.io.IOException
 	 *             an unexpected error occurred writing to the object store.
 	 */
 	public ObjectId writeTree(ObjectInserter ow)
 			throws UnmergedPathException, IOException {
 		return getCacheTree(true).writeTree(sortedEntries, 0, 0, ow);
 	}
 
 	/**
 	 * Tells whether this index contains unmerged paths.
 	 *
 	 * @return {@code true} if this index contains unmerged paths. Means: at
 	 *         least one entry is of a stage different from 0. {@code false}
 	 *         will be returned if all entries are of stage 0.
 	 */
 	public boolean hasUnmergedPaths() {
 		for (int i = 0; i < entryCnt; i++) {
 			if (sortedEntries[i].getStage() > 0) {
 				return true;
 			}
 		}
 		return false;
 	}
 
 	private void registerIndexChangedListener(IndexChangedListener listener) {
 		this.indexChangedListener = listener;
 	}
 
 	/**
 	 * Update any smudged entries with information from the working tree.
 	 *
 	 * @throws IOException
 	 */
 	private void updateSmudgedEntries() throws IOException {
 		List<String> paths = new ArrayList<>(128);
 		try (TreeWalkeeWalk.html#TreeWalk">TreeWalk walk = new TreeWalk(repository)) {
 			walk.setOperationType(OperationType.CHECKIN_OP);
 			for (int i = 0; i < entryCnt; i++)
 				if (sortedEntries[i].isSmudged())
 					paths.add(sortedEntries[i].getPathString());
 			if (paths.isEmpty())
 				return;
 			walk.setFilter(PathFilterGroup.createFromStrings(paths));
 
 			DirCacheIterator iIter = new DirCacheIterator(this);
 			FileTreeIterator fIter = new FileTreeIterator(repository);
 			walk.addTree(iIter);
 			walk.addTree(fIter);
 			fIter.setDirCacheIterator(walk, 0);
 			walk.setRecursive(true);
 			while (walk.next()) {
 				iIter = walk.getTree(0, DirCacheIterator.class);
 				if (iIter == null)
 					continue;
 				fIter = walk.getTree(1, FileTreeIterator.class);
 				if (fIter == null)
 					continue;
 				DirCacheEntry entry = iIter.getDirCacheEntry();
 				if (entry.isSmudged() && iIter.idEqual(fIter)) {
 					entry.setLength(fIter.getEntryLength());
 					entry.setLastModified(fIter.getEntryLastModifiedInstant());
 				}
 			}
 		}
 	}
 
 	enum DirCacheVersion implements ConfigEnum {
 
 		/** Minimum index version on-disk format that we support. */
 		DIRC_VERSION_MINIMUM(2),
 		/** Version 3 supports extended flags. */
 		DIRC_VERSION_EXTENDED(3),
 		/**
 		 * Version 4 adds very simple "path compression": it strips out the
 		 * common prefix between the last entry written and the current entry.
 		 * Instead of writing two entries with paths "foo/bar/baz/a.txt" and
 		 * "foo/bar/baz/b.txt" it only writes "b.txt" for the second entry.
 		 * <p>
 		 * It is also <em>not</em> padded.
 		 * </p>
 		 */
 		DIRC_VERSION_PATHCOMPRESS(4);
 
 		private final int version;
 
 		private DirCacheVersion(int versionCode) {
 			this.version = versionCode;
 		}
 
 		public int getVersionCode() {
 			return version;
 		}
 
 		@Override
 		public String toConfigValue() {
 			return Integer.toString(version);
 		}
 
 		@Override
 		public boolean matchConfigValue(String in) {
 			try {
 				return version == Integer.parseInt(in);
 			} catch (NumberFormatException e) {
 				return false;
 			}
 		}
 
 		public static DirCacheVersion fromInt(int val) {
 			for (DirCacheVersion v : DirCacheVersion.values()) {
 				if (val == v.getVersionCode()) {
 					return v;
 				}
 			}
 			return null;
 		}
 	}
 
 	private static class DirCacheConfig {
 
 		private final DirCacheVersion indexVersion;
 
 		public DirCacheConfig(Config cfg) {
 			boolean manyFiles = cfg.getBoolean(
 					ConfigConstants.CONFIG_FEATURE_SECTION,
 					ConfigConstants.CONFIG_KEY_MANYFILES, false);
 			indexVersion = cfg.getEnum(DirCacheVersion.values(),
 					ConfigConstants.CONFIG_INDEX_SECTION, null,
 					ConfigConstants.CONFIG_KEY_VERSION,
 					manyFiles ? DirCacheVersion.DIRC_VERSION_PATHCOMPRESS
 							: DirCacheVersion.DIRC_VERSION_EXTENDED);
 		}
 
 		public DirCacheVersion getIndexVersion() {
 			return indexVersion;
 		}
 
 	}
 }