CommitGraphWriter: write changed-path filters

Add support for writing the BIDX and BDAT chunks of the commit graph
file, as described in man gitformat-commit-graph(5). The ability to read
such chunks will be added in a subsequent commit.

This work is based on earlier work by Kyle Zhao
(Ib863782af209f26381e3ca0a2c119b99e84b679c).

Change-Id: Ic18e6f0eeec7da1e1ff31751aabda5e6952dbe6e
Signed-off-by: kylezhao <kylezhao@tencent.com>
Signed-off-by: Jonathan Tan <jonathantanmy@google.com>

1 files changed, 219 insertions, 10 deletions

diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/commitgraph/CommitGraphWriterTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/commitgraph/CommitGraphWriterTest.java
index 6c5e5e5605..e7f49496ad 100644
--- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/commitgraph/CommitGraphWriterTest.java
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/internal/storage/commitgraph/CommitGraphWriterTest.java
@@ -10,19 +10,24 @@
 
 package org.eclipse.jgit.internal.storage.commitgraph;
 
+import static org.hamcrest.MatcherAssert.assertThat;
+import static org.hamcrest.Matchers.containsInAnyOrder;
 import static org.junit.Assert.assertArrayEquals;
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertTrue;
 
 import java.io.ByteArrayOutputStream;
 import java.util.Collections;
+import java.util.HashSet;
 import java.util.Set;
 
+import org.eclipse.jgit.dircache.DirCacheEntry;
 import org.eclipse.jgit.internal.storage.file.FileRepository;
 import org.eclipse.jgit.junit.RepositoryTestCase;
 import org.eclipse.jgit.junit.TestRepository;
 import org.eclipse.jgit.lib.NullProgressMonitor;
 import org.eclipse.jgit.lib.ObjectId;
+import org.eclipse.jgit.revwalk.RevBlob;
 import org.eclipse.jgit.revwalk.RevCommit;
 import org.eclipse.jgit.revwalk.RevWalk;
 import org.eclipse.jgit.util.NB;
@@ -76,11 +81,20 @@ public class CommitGraphWriterTest extends RepositoryTestCase {
 		assertTrue(data.length > 0);
 		byte[] headers = new byte[8];
 		System.arraycopy(data, 0, headers, 0, 8);
-		assertArrayEquals(new byte[] {'C', 'G', 'P', 'H', 1, 1, 4, 0}, headers);
-		assertEquals(CommitGraphConstants.CHUNK_ID_OID_FANOUT, NB.decodeInt32(data, 8));
-		assertEquals(CommitGraphConstants.CHUNK_ID_OID_LOOKUP, NB.decodeInt32(data, 20));
-		assertEquals(CommitGraphConstants.CHUNK_ID_COMMIT_DATA, NB.decodeInt32(data, 32));
-		assertEquals(CommitGraphConstants.CHUNK_ID_EXTRA_EDGE_LIST, NB.decodeInt32(data, 44));
+		assertArrayEquals(new byte[] { 'C', 'G', 'P', 'H', 1, 1, 6, 0 },
+				headers);
+		assertEquals(CommitGraphConstants.CHUNK_ID_OID_FANOUT,
+				NB.decodeInt32(data, 8));
+		assertEquals(CommitGraphConstants.CHUNK_ID_OID_LOOKUP,
+				NB.decodeInt32(data, 20));
+		assertEquals(CommitGraphConstants.CHUNK_ID_COMMIT_DATA,
+				NB.decodeInt32(data, 32));
+		assertEquals(CommitGraphConstants.CHUNK_ID_EXTRA_EDGE_LIST,
+				NB.decodeInt32(data, 44));
+		assertEquals(CommitGraphConstants.CHUNK_ID_BLOOM_FILTER_INDEX,
+				NB.decodeInt32(data, 56));
+		assertEquals(CommitGraphConstants.CHUNK_ID_BLOOM_FILTER_DATA,
+				NB.decodeInt32(data, 68));
 	}
 
 	@Test
@@ -101,13 +115,208 @@ public class CommitGraphWriterTest extends RepositoryTestCase {
 		assertTrue(data.length > 0);
 		byte[] headers = new byte[8];
 		System.arraycopy(data, 0, headers, 0, 8);
-		assertArrayEquals(new byte[] {'C', 'G', 'P', 'H', 1, 1, 3, 0}, headers);
-		assertEquals(CommitGraphConstants.CHUNK_ID_OID_FANOUT, NB.decodeInt32(data, 8));
-		assertEquals(CommitGraphConstants.CHUNK_ID_OID_LOOKUP, NB.decodeInt32(data, 20));
-		assertEquals(CommitGraphConstants.CHUNK_ID_COMMIT_DATA, NB.decodeInt32(data, 32));
+		assertArrayEquals(new byte[] { 'C', 'G', 'P', 'H', 1, 1, 5, 0 },
+				headers);
+		assertEquals(CommitGraphConstants.CHUNK_ID_OID_FANOUT,
+				NB.decodeInt32(data, 8));
+		assertEquals(CommitGraphConstants.CHUNK_ID_OID_LOOKUP,
+				NB.decodeInt32(data, 20));
+		assertEquals(CommitGraphConstants.CHUNK_ID_COMMIT_DATA,
+				NB.decodeInt32(data, 32));
+		assertEquals(CommitGraphConstants.CHUNK_ID_BLOOM_FILTER_INDEX,
+				NB.decodeInt32(data, 44));
+		assertEquals(CommitGraphConstants.CHUNK_ID_BLOOM_FILTER_DATA,
+				NB.decodeInt32(data, 56));
+	}
+
+	static HashSet<String> changedPathStrings(byte[] data) {
+		int oidf_offset = -1;
+		int bidx_offset = -1;
+		int bdat_offset = -1;
+		for (int i = 8; i < data.length - 4; i += 12) {
+			switch (NB.decodeInt32(data, i)) {
+			case CommitGraphConstants.CHUNK_ID_OID_FANOUT:
+				oidf_offset = (int) NB.decodeInt64(data, i + 4);
+				break;
+			case CommitGraphConstants.CHUNK_ID_BLOOM_FILTER_INDEX:
+				bidx_offset = (int) NB.decodeInt64(data, i + 4);
+				break;
+			case CommitGraphConstants.CHUNK_ID_BLOOM_FILTER_DATA:
+				bdat_offset = (int) NB.decodeInt64(data, i + 4);
+				break;
+			}
+		}
+		assertTrue(oidf_offset > 0);
+		assertTrue(bidx_offset > 0);
+		assertTrue(bdat_offset > 0);
+		bdat_offset += 12; // skip version, hash count, bits per entry
+		int commit_count = NB.decodeInt32(data, oidf_offset + 255 * 4);
+		int[] changed_path_length_cumuls = new int[commit_count];
+		for (int i = 0; i < commit_count; i++) {
+			changed_path_length_cumuls[i] = NB.decodeInt32(data,
+					bidx_offset + i * 4);
+		}
+		HashSet<String> changed_paths = new HashSet<>();
+		for (int i = 0; i < commit_count; i++) {
+			int prior_cumul = i == 0 ? 0 : changed_path_length_cumuls[i - 1];
+			String changed_path = "";
+			for (int j = prior_cumul; j < changed_path_length_cumuls[i]; j++) {
+				changed_path += data[bdat_offset + j] + ",";
+			}
+			changed_paths.add(changed_path);
+		}
+		return changed_paths;
+	}
+
+	/**
+	 * Expected value generated using the following:
+	 *
+	 * <pre>
+	 * # apply into git-repo: https://lore.kernel.org/git/cover.1684790529.git.jonathantanmy@google.com/
+	 * (cd git-repo; make)
+	 * git-repo/bin-wrappers/git init tested
+	 * (cd tested; touch foo.txt; mkdir -p onedir/twodir; touch onedir/twodir/bar.txt)
+	 * git-repo/bin-wrappers/git -C tested add foo.txt onedir
+	 * git-repo/bin-wrappers/git -C tested commit -m first_commit
+	 * (cd tested; mv foo.txt foo-new.txt; mv onedir/twodir/bar.txt onedir/twodir/bar-new.txt)
+	 * git-repo/bin-wrappers/git -C tested add foo-new.txt onedir
+	 * git-repo/bin-wrappers/git -C tested commit -a -m second_commit
+	 * git-repo/bin-wrappers/git -C tested maintenance run
+	 * git-repo/bin-wrappers/git -C tested commit-graph write --changed-paths
+	 * (cd tested; $JGIT debug-read-changed-path-filter .git/objects/info/commit-graph)
+	 * </pre>
+	 *
+	 * @throws Exception
+	 */
+	@Test
+	public void testChangedPathFilterRootAndNested() throws Exception {
+		RevBlob emptyBlob = tr.blob(new byte[] {});
+		RevCommit root = tr.commit(tr.tree(tr.file("foo.txt", emptyBlob),
+				tr.file("onedir/twodir/bar.txt", emptyBlob)));
+		RevCommit tip = tr.commit(tr.tree(tr.file("foo-new.txt", emptyBlob),
+				tr.file("onedir/twodir/bar-new.txt", emptyBlob)), root);
+
+		Set<ObjectId> wants = Collections.singleton(tip);
+		NullProgressMonitor m = NullProgressMonitor.INSTANCE;
+		GraphCommits graphCommits = GraphCommits.fromWalk(m, wants, walk);
+		writer = new CommitGraphWriter(graphCommits);
+		writer.write(m, os);
+
+		HashSet<String> changedPaths = changedPathStrings(os.toByteArray());
+		assertThat(changedPaths, containsInAnyOrder(
+				"109,-33,2,60,20,79,-11,116,",
+				"119,69,63,-8,0,"));
+	}
+
+	/**
+	 * Expected value generated using the following:
+	 *
+	 * <pre>
+	 * git -C git-repo checkout todo get version number when it is merged
+	 * (cd git-repo; make)
+	 * git-repo/bin-wrappers/git init tested
+	 * (cd tested; mkdir -p onedir/twodir; touch onedir/twodir/a.txt; touch onedir/twodir/b.txt)
+	 * git-repo/bin-wrappers/git -C tested add onedir
+	 * git-repo/bin-wrappers/git -C tested commit -m first_commit
+	 * (cd tested; mv onedir/twodir/a.txt onedir/twodir/c.txt; mv onedir/twodir/b.txt onedir/twodir/d.txt)
+	 * git-repo/bin-wrappers/git -C tested add onedir
+	 * git-repo/bin-wrappers/git -C tested commit -a -m second_commit
+	 * git-repo/bin-wrappers/git -C tested maintenance run
+	 * git-repo/bin-wrappers/git -C tested commit-graph write --changed-paths
+	 * (cd tested; $JGIT debug-read-changed-path-filter .git/objects/info/commit-graph)
+	 * </pre>
+	 *
+	 * @throws Exception
+	 */
+	@Test
+	public void testChangedPathFilterOverlappingNested() throws Exception {
+		RevBlob emptyBlob = tr.blob(new byte[] {});
+		RevCommit root = tr
+				.commit(tr.tree(tr.file("onedir/twodir/a.txt", emptyBlob),
+						tr.file("onedir/twodir/b.txt", emptyBlob)));
+		RevCommit tip = tr
+				.commit(tr.tree(tr.file("onedir/twodir/c.txt", emptyBlob),
+						tr.file("onedir/twodir/d.txt", emptyBlob)), root);
+
+		Set<ObjectId> wants = Collections.singleton(tip);
+		NullProgressMonitor m = NullProgressMonitor.INSTANCE;
+		GraphCommits graphCommits = GraphCommits.fromWalk(m, wants, walk);
+		writer = new CommitGraphWriter(graphCommits);
+		writer.write(m, os);
+
+		HashSet<String> changedPaths = changedPathStrings(os.toByteArray());
+		assertThat(changedPaths, containsInAnyOrder("61,30,23,-24,1,",
+				"-58,-51,-46,60,29,-121,113,90,"));
+	}
+
+	/**
+	 * Expected value generated using the following:
+	 *
+	 * <pre>
+	 * git -C git-repo checkout todo get version number when it is merged
+	 * (cd git-repo; make)
+	 * git-repo/bin-wrappers/git init tested
+	 * (cd tested; touch 你好)
+	 * git-repo/bin-wrappers/git -C tested add 你好
+	 * git-repo/bin-wrappers/git -C tested commit -m first_commit
+	 * git-repo/bin-wrappers/git -C tested maintenance run
+	 * git-repo/bin-wrappers/git -C tested commit-graph write --changed-paths
+	 * (cd tested; $JGIT debug-read-changed-path-filter .git/objects/info/commit-graph)
+	 * </pre>
+	 *
+	 * @throws Exception
+	 */
+	@Test
+	public void testChangedPathFilterHighBit() throws Exception {
+		RevBlob emptyBlob = tr.blob(new byte[] {});
+		// tr.file encodes using UTF-8
+		RevCommit root = tr.commit(tr.tree(tr.file("你好", emptyBlob)));
+
+		Set<ObjectId> wants = Collections.singleton(root);
+		NullProgressMonitor m = NullProgressMonitor.INSTANCE;
+		GraphCommits graphCommits = GraphCommits.fromWalk(m, wants, walk);
+		writer = new CommitGraphWriter(graphCommits);
+		writer.write(m, os);
+
+		HashSet<String> changedPaths = changedPathStrings(os.toByteArray());
+		assertThat(changedPaths, containsInAnyOrder("16,16,"));
+	}
+
+	@Test
+	public void testChangedPathFilterEmptyChange() throws Exception {
+		RevCommit root = commit();
+
+		Set<ObjectId> wants = Collections.singleton(root);
+		NullProgressMonitor m = NullProgressMonitor.INSTANCE;
+		GraphCommits graphCommits = GraphCommits.fromWalk(m, wants, walk);
+		writer = new CommitGraphWriter(graphCommits);
+		writer.write(m, os);
+
+		HashSet<String> changedPaths = changedPathStrings(os.toByteArray());
+		assertThat(changedPaths, containsInAnyOrder("0,"));
+	}
+
+	@Test
+	public void testChangedPathFilterManyChanges() throws Exception {
+		RevBlob emptyBlob = tr.blob(new byte[] {});
+		DirCacheEntry[] entries = new DirCacheEntry[513];
+		for (int i = 0; i < entries.length; i++) {
+			entries[i] = tr.file(i + ".txt", emptyBlob);
+		}
+
+		RevCommit root = tr.commit(tr.tree(entries));
+
+		Set<ObjectId> wants = Collections.singleton(root);
+		NullProgressMonitor m = NullProgressMonitor.INSTANCE;
+		GraphCommits graphCommits = GraphCommits.fromWalk(m, wants, walk);
+		writer = new CommitGraphWriter(graphCommits);
+		writer.write(m, os);
+
+		HashSet<String> changedPaths = changedPathStrings(os.toByteArray());
+		assertThat(changedPaths, containsInAnyOrder("-1,"));
 	}
 
 	RevCommit commit(RevCommit... parents) throws Exception {
 		return tr.commit(parents);
 	}
-}
+}
\ No newline at end of file