DirCache: support index V4

Index format version 4 was introduced in C git in 2012. It's about
time that JGit can deal with it.

Version 4 added prefix path compression. Instead of writing the full
path for each index entry to disk, only the difference to the previous
entry's path is written: a variable-encoded int telling how many bytes
to remove from the previous entry's path to get the common prefix,
followed by the new suffix.

Also, cache entries in a version 4 index are not padded anymore.

Internally, version 3 and version 4 index entries are identical; it's
only the stored format that changes.

Implement this path compression, and make sure we write an index file
that we read previously in the same format. (Only changing from version
2 to version 3 if there are extended flags.)

Add support for the "feature.manyFiles" and the "index.version" git
configs, and honor them when writing a new index file.

Add tests, including a compatibility test that verifies that JGit can
read a version 4 index generated by C git and write an identical
version 4 index.

Bug: 565774
Change-Id: Id83241cf009e50f950eb42f8d56b834fb47da1ed
Signed-off-by: Thomas Wolf <thomas.wolf@paranor.ch>

4 files changed, 266 insertions, 2 deletions

diff --git a/org.eclipse.jgit.test/tst-rsrc/org/eclipse/jgit/test/resources/gitgit.index.v4 b/org.eclipse.jgit.test/tst-rsrc/org/eclipse/jgit/test/resources/gitgit.index.v4
new file mode 100644
index 0000000000..de49e56249
--- /dev/null
+++ b/org.eclipse.jgit.test/tst-rsrc/org/eclipse/jgit/test/resources/gitgit.index.v4
diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/dircache/DirCacheAfterCloneTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/dircache/DirCacheAfterCloneTest.java
new file mode 100644
index 0000000000..f210760bf5
--- /dev/null
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/dircache/DirCacheAfterCloneTest.java
@@ -0,0 +1,134 @@
+/*
+ * Copyright (C) 2020 Thomas Wolf <thomas.wolf@paranor.ch> 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 org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertNotNull;
+import static org.junit.Assert.assertTrue;
+
+import java.io.File;
+import java.util.EnumSet;
+import java.util.Set;
+
+import org.eclipse.jgit.api.CloneCommand;
+import org.eclipse.jgit.api.Git;
+import org.eclipse.jgit.api.ResetCommand.ResetType;
+import org.eclipse.jgit.dircache.DirCache.DirCacheVersion;
+import org.eclipse.jgit.junit.RepositoryTestCase;
+import org.eclipse.jgit.lib.StoredConfig;
+import org.eclipse.jgit.util.FileUtils;
+import org.eclipse.jgit.util.SystemReader;
+import org.junit.Test;
+
+/**
+ * Tests for initial DirCache version after a clone or after a mixed or hard
+ * reset.
+ */
+public class DirCacheAfterCloneTest extends RepositoryTestCase {
+
+	@Override
+	public void setUp() throws Exception {
+		super.setUp();
+		try (Git git = new Git(db)) {
+			writeTrashFile("Test.txt", "Hello world");
+			git.add().addFilepattern("Test.txt").call();
+			git.commit().setMessage("Initial commit").call();
+		}
+	}
+
+	private DirCacheVersion cloneAndCheck(Set<DirCacheVersion> expected)
+			throws Exception {
+		File directory = createTempDirectory("testCloneRepository");
+		CloneCommand command = Git.cloneRepository();
+		command.setDirectory(directory);
+		command.setURI("file://" + db.getWorkTree().getAbsolutePath());
+		Git git2 = command.call();
+		addRepoToClose(git2.getRepository());
+		assertNotNull(git2);
+		DirCache dc = DirCache.read(git2.getRepository());
+		DirCacheVersion version = dc.getVersion();
+		assertTrue(expected.contains(version));
+		return version;
+	}
+
+	@Test
+	public void testCloneV3OrV2() throws Exception {
+		cloneAndCheck(EnumSet.of(DirCacheVersion.DIRC_VERSION_MINIMUM,
+				DirCacheVersion.DIRC_VERSION_EXTENDED));
+	}
+
+	@Test
+	public void testCloneV4() throws Exception {
+		StoredConfig cfg = SystemReader.getInstance().getUserConfig();
+		cfg.load();
+		cfg.setInt("index", null, "version", 4);
+		cfg.save();
+		cloneAndCheck(EnumSet.of(DirCacheVersion.DIRC_VERSION_PATHCOMPRESS));
+	}
+
+	@Test
+	public void testCloneV4manyFiles() throws Exception {
+		StoredConfig cfg = SystemReader.getInstance().getUserConfig();
+		cfg.load();
+		cfg.setBoolean("feature", null, "manyFiles", true);
+		cfg.save();
+		cloneAndCheck(EnumSet.of(DirCacheVersion.DIRC_VERSION_PATHCOMPRESS));
+	}
+
+	@Test
+	public void testCloneV3CommitNoVersionChange() throws Exception {
+		DirCacheVersion initial = cloneAndCheck(
+				EnumSet.of(DirCacheVersion.DIRC_VERSION_MINIMUM,
+						DirCacheVersion.DIRC_VERSION_EXTENDED));
+		StoredConfig cfg = db.getConfig();
+		cfg.setInt("index", null, "version", 4);
+		cfg.save();
+		try (Git git = new Git(db)) {
+			writeTrashFile("Test.txt2", "Hello again");
+			git.add().addFilepattern("Test.txt2").call();
+			git.commit().setMessage("Second commit").call();
+		}
+		assertEquals("DirCache version should be unchanged", initial,
+				DirCache.read(db).getVersion());
+	}
+
+	@Test
+	public void testCloneV3ResetHardVersionChange() throws Exception {
+		cloneAndCheck(EnumSet.of(DirCacheVersion.DIRC_VERSION_MINIMUM,
+						DirCacheVersion.DIRC_VERSION_EXTENDED));
+		StoredConfig cfg = db.getConfig();
+		cfg.setInt("index", null, "version", 4);
+		cfg.save();
+		FileUtils.delete(new File(db.getDirectory(), "index"));
+		try (Git git = new Git(db)) {
+			git.reset().setMode(ResetType.HARD).call();
+		}
+		assertEquals("DirCache version should have changed",
+				DirCacheVersion.DIRC_VERSION_PATHCOMPRESS,
+				DirCache.read(db).getVersion());
+	}
+
+	@Test
+	public void testCloneV3ResetMixedVersionChange() throws Exception {
+		cloneAndCheck(EnumSet.of(DirCacheVersion.DIRC_VERSION_MINIMUM,
+				DirCacheVersion.DIRC_VERSION_EXTENDED));
+		StoredConfig cfg = db.getConfig();
+		cfg.setInt("index", null, "version", 4);
+		cfg.save();
+		FileUtils.delete(new File(db.getDirectory(), "index"));
+		try (Git git = new Git(db)) {
+			git.reset().setMode(ResetType.MIXED).call();
+		}
+		assertEquals("DirCache version should have changed",
+				DirCacheVersion.DIRC_VERSION_PATHCOMPRESS,
+				DirCache.read(db).getVersion());
+	}
+}
diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/dircache/DirCacheCGitCompatabilityTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/dircache/DirCacheCGitCompatabilityTest.java
index c57cb263d1..6d4d0b4ab3 100644
--- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/dircache/DirCacheCGitCompatabilityTest.java
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/dircache/DirCacheCGitCompatabilityTest.java
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2008-2010, Google Inc. and others
+ * Copyright (C) 2008, 2020, Google Inc. and others
  *
  * This program and the accompanying materials are made available under the
  * terms of the Eclipse Distribution License v. 1.0 which is available at
@@ -28,6 +28,7 @@ import java.util.Iterator;
 import java.util.LinkedHashMap;
 import java.util.Map;
 
+import org.eclipse.jgit.dircache.DirCache.DirCacheVersion;
 import org.eclipse.jgit.errors.CorruptObjectException;
 import org.eclipse.jgit.junit.JGitTestUtil;
 import org.eclipse.jgit.junit.LocalDiskRepositoryTestCase;
@@ -188,6 +189,28 @@ public class DirCacheCGitCompatabilityTest extends LocalDiskRepositoryTestCase {
 		assertArrayEquals(expectedBytes, indexBytes);
 	}
 
+	@Test
+	public void testReadWriteV4() throws Exception {
+		final File file = pathOf("gitgit.index.v4");
+		final DirCache dc = new DirCache(file, FS.DETECTED);
+		dc.read();
+		assertEquals(DirCacheVersion.DIRC_VERSION_PATHCOMPRESS,
+				dc.getVersion());
+		assertEquals(5, dc.getEntryCount());
+		assertV4TreeEntry(0, "src/org/eclipse/jgit/atest/foo.txt", false, dc);
+		assertV4TreeEntry(1, "src/org/eclipse/jgit/atest/foobar.txt", false,
+				dc);
+		assertV4TreeEntry(2, "src/org/eclipse/jgit/other/bar.txt", true, dc);
+		assertV4TreeEntry(3, "test.txt", false, dc);
+		assertV4TreeEntry(4, "test.txt2", false, dc);
+
+		final ByteArrayOutputStream bos = new ByteArrayOutputStream();
+		dc.writeTo(null, bos);
+		final byte[] indexBytes = bos.toByteArray();
+		final byte[] expectedBytes = IO.readFully(file);
+		assertArrayEquals(expectedBytes, indexBytes);
+	}
+
 	private static void assertV3TreeEntry(int indexPosition, String path,
 			boolean skipWorkTree, boolean intentToAdd, DirCache dc) {
 		final DirCacheEntry entry = dc.getEntry(indexPosition);
@@ -196,6 +219,13 @@ public class DirCacheCGitCompatabilityTest extends LocalDiskRepositoryTestCase {
 		assertEquals(intentToAdd, entry.isIntentToAdd());
 	}
 
+	private static void assertV4TreeEntry(int indexPosition, String path,
+			boolean skipWorkTree, DirCache dc) {
+		final DirCacheEntry entry = dc.getEntry(indexPosition);
+		assertEquals(path, entry.getPathString());
+		assertEquals(skipWorkTree, entry.isSkipWorkTree());
+	}
+
 	private static File pathOf(String name) {
 		return JGitTestUtil.getTestResourceFile(name);
 	}
diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/dircache/DirCacheEntryTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/dircache/DirCacheEntryTest.java
index f21c7f854f..5477f565f4 100644
--- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/dircache/DirCacheEntryTest.java
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/dircache/DirCacheEntryTest.java
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2009, Google Inc. and others
+ * Copyright (C) 2009, 2020 Google Inc. and others
  *
  * This program and the accompanying materials are made available under the
  * terms of the Eclipse Distribution License v. 1.0 which is available at
@@ -11,14 +11,25 @@
 package org.eclipse.jgit.dircache;
 
 import static java.time.Instant.EPOCH;
+import static org.junit.Assert.assertArrayEquals;
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertFalse;
 import static org.junit.Assert.assertSame;
 import static org.junit.Assert.assertTrue;
 import static org.junit.Assert.fail;
 
+import java.io.ByteArrayInputStream;
+import java.io.ByteArrayOutputStream;
+import java.io.IOException;
+import java.security.MessageDigest;
+import java.time.Instant;
+import java.util.concurrent.TimeUnit;
+
+import org.eclipse.jgit.dircache.DirCache.DirCacheVersion;
+import org.eclipse.jgit.lib.Constants;
 import org.eclipse.jgit.lib.FileMode;
 import org.eclipse.jgit.lib.ObjectId;
+import org.eclipse.jgit.util.MutableInteger;
 import org.junit.Test;
 
 public class DirCacheEntryTest {
@@ -47,6 +58,95 @@ public class DirCacheEntryTest {
 		}
 	}
 
+	private static void checkPath(DirCacheVersion indexVersion,
+			DirCacheEntry previous, String name) throws IOException {
+		DirCacheEntry dce = new DirCacheEntry(name);
+		long now = System.currentTimeMillis();
+		long anHourAgo = now - TimeUnit.HOURS.toMillis(1);
+		dce.setLastModified(Instant.ofEpochMilli(anHourAgo));
+		ByteArrayOutputStream out = new ByteArrayOutputStream();
+		dce.write(out, indexVersion, previous);
+		byte[] raw = out.toByteArray();
+		MessageDigest md0 = Constants.newMessageDigest();
+		md0.update(raw);
+		ByteArrayInputStream in = new ByteArrayInputStream(raw);
+		MutableInteger infoAt = new MutableInteger();
+		byte[] sharedInfo = new byte[raw.length];
+		MessageDigest md = Constants.newMessageDigest();
+		DirCacheEntry read = new DirCacheEntry(sharedInfo, infoAt, in, md,
+				Instant.ofEpochMilli(now), indexVersion, previous);
+		assertEquals("Paths of length " + name.length() + " should match", name,
+				read.getPathString());
+		assertEquals("Should have been fully read", -1, in.read());
+		assertArrayEquals("Digests should match", md0.digest(),
+				md.digest());
+	}
+
+	@Test
+	public void testLongPath() throws Exception {
+		StringBuilder name = new StringBuilder(4094 + 16);
+		for (int i = 0; i < 4094; i++) {
+			name.append('a');
+		}
+		for (int j = 0; j < 16; j++) {
+			checkPath(DirCacheVersion.DIRC_VERSION_EXTENDED, null,
+					name.toString());
+			name.append('b');
+		}
+	}
+
+	@Test
+	public void testLongPathV4() throws Exception {
+		StringBuilder name = new StringBuilder(4094 + 16);
+		for (int i = 0; i < 4094; i++) {
+			name.append('a');
+		}
+		DirCacheEntry previous = new DirCacheEntry(name.toString());
+		for (int j = 0; j < 16; j++) {
+			checkPath(DirCacheVersion.DIRC_VERSION_PATHCOMPRESS, previous,
+					name.toString());
+			name.append('b');
+		}
+	}
+
+	@Test
+	public void testShortPath() throws Exception {
+		StringBuilder name = new StringBuilder(1 + 16);
+		name.append('a');
+		for (int j = 0; j < 16; j++) {
+			checkPath(DirCacheVersion.DIRC_VERSION_EXTENDED, null,
+					name.toString());
+			name.append('b');
+		}
+	}
+
+	@Test
+	public void testShortPathV4() throws Exception {
+		StringBuilder name = new StringBuilder(1 + 16);
+		name.append('a');
+		DirCacheEntry previous = new DirCacheEntry(name.toString());
+		for (int j = 0; j < 16; j++) {
+			checkPath(DirCacheVersion.DIRC_VERSION_PATHCOMPRESS, previous,
+					name.toString());
+			name.append('b');
+		}
+	}
+
+	@Test
+	public void testPathV4() throws Exception {
+		StringBuilder name = new StringBuilder();
+		for (int i = 0; i < 20; i++) {
+			name.append('a');
+		}
+		DirCacheEntry previous = new DirCacheEntry(name.toString());
+		for (int j = 0; j < 20; j++) {
+			name.setLength(name.length() - 1);
+			String newName = name.toString() + "bbb";
+			checkPath(DirCacheVersion.DIRC_VERSION_PATHCOMPRESS, previous,
+					newName);
+		}
+	}
+
 	@SuppressWarnings("unused")
 	@Test
 	public void testCreate_ByStringPath() {