From 59e8bec6e7705a89b5d0b9c6ac004b323ffa16b0 Mon Sep 17 00:00:00 2001
From: Ronald Bhuleskar <funronald@google.com>
Date: Tue, 2 Aug 2022 17:17:46 -0700
Subject: [PATCH] Option to pass start RevCommit to be blamed on to the
 BlameGenerator.

This can allow passing a FilteredRevCommit which is the filtered list of
commit graph making it easier for Blame to work on. This can
significantly improve blame performance since blame can skip expensive
RevWalk.

Change-Id: I5dab25301d6aef7df6a0bc25a4c553c730199272
---
 .../jgit/api/blame/BlameGeneratorTest.java    | 329 ++++++++++++++++--
 .../eclipse/jgit/blame/BlameGenerator.java    |  47 ++-
 2 files changed, 337 insertions(+), 39 deletions(-)

diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/api/blame/BlameGeneratorTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/api/blame/BlameGeneratorTest.java
index f47f447375..b175ead8ec 100644
--- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/api/blame/BlameGeneratorTest.java
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/api/blame/BlameGeneratorTest.java
@@ -13,56 +13,330 @@ import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertFalse;
 import static org.junit.Assert.assertTrue;
 
+import java.util.Iterator;
+
 import org.eclipse.jgit.api.Git;
 import org.eclipse.jgit.blame.BlameGenerator;
 import org.eclipse.jgit.blame.BlameResult;
 import org.eclipse.jgit.junit.RepositoryTestCase;
 import org.eclipse.jgit.lib.Constants;
+import org.eclipse.jgit.merge.MergeStrategy;
+import org.eclipse.jgit.revwalk.FilteredRevCommit;
 import org.eclipse.jgit.revwalk.RevCommit;
+import org.eclipse.jgit.revwalk.RevWalk;
 import org.junit.Test;
 
 /** Unit tests of {@link BlameGenerator}. */
 public class BlameGeneratorTest extends RepositoryTestCase {
+
+	public static final String OTHER_FILE = "other_file.txt";
+
+	public static final String INTERESTING_FILE = "interesting_file.txt";
+
 	@Test
-	public void testBoundLineDelete() throws Exception {
-		try (Git git = new Git(db)) {
-			String[] content1 = new String[] { "first", "second" };
-			writeTrashFile("file.txt", join(content1));
-			git.add().addFilepattern("file.txt").call();
+	public void testSingleBlame() throws Exception {
+
+		/**
+		 * <pre>
+		 * (ts) 	OTHER_FILE			INTERESTING_FILE
+		 * 1 		a
+		 * 2	 	a, b
+		 * 3							1, 2				c1 <--
+		 * 4	 	a, b, c										 |
+		 * 5							1, 2, 3				c2---
+		 * </pre>
+		 */
+		try (Git git = new Git(db);
+				RevWalk revWalk = new RevWalk(git.getRepository())) {
+			writeTrashFile(OTHER_FILE, join("a"));
+			git.add().addFilepattern(OTHER_FILE).call();
+			git.commit().setMessage("create file").call();
+
+			writeTrashFile(OTHER_FILE, join("a", "b"));
+			git.add().addFilepattern(OTHER_FILE).call();
+			git.commit().setMessage("amend file").call();
+
+			writeTrashFile(INTERESTING_FILE, join("1", "2"));
+			git.add().addFilepattern(INTERESTING_FILE).call();
 			RevCommit c1 = git.commit().setMessage("create file").call();
 
-			String[] content2 = new String[] { "third", "first", "second" };
-			writeTrashFile("file.txt", join(content2));
-			git.add().addFilepattern("file.txt").call();
-			RevCommit c2 = git.commit().setMessage("create file").call();
+			writeTrashFile(OTHER_FILE, join("a", "b", "c"));
+			git.add().addFilepattern(OTHER_FILE).call();
+			git.commit().setMessage("amend file").call();
 
-			try (BlameGenerator generator = new BlameGenerator(db, "file.txt")) {
-				generator.push(null, db.resolve(Constants.HEAD));
+			writeTrashFile(INTERESTING_FILE, join("1", "2", "3"));
+			git.add().addFilepattern(INTERESTING_FILE).call();
+			RevCommit c2 = git.commit().setMessage("amend file").call();
+
+			RevCommit filteredC1 = new FilteredRevCommit(c1);
+			RevCommit filteredC2 = new FilteredRevCommit(c2, filteredC1);
+
+			revWalk.parseHeaders(filteredC2);
+
+			try (BlameGenerator generator = new BlameGenerator(db,
+					INTERESTING_FILE)) {
+				generator.push(filteredC2);
 				assertEquals(3, generator.getResultContents().size());
 
 				assertTrue(generator.next());
 				assertEquals(c2, generator.getSourceCommit());
 				assertEquals(1, generator.getRegionLength());
+				assertEquals(2, generator.getResultStart());
+				assertEquals(3, generator.getResultEnd());
+				assertEquals(2, generator.getSourceStart());
+				assertEquals(3, generator.getSourceEnd());
+				assertEquals(INTERESTING_FILE, generator.getSourcePath());
+
+				assertTrue(generator.next());
+				assertEquals(c1, generator.getSourceCommit());
+				assertEquals(2, generator.getRegionLength());
 				assertEquals(0, generator.getResultStart());
-				assertEquals(1, generator.getResultEnd());
+				assertEquals(2, generator.getResultEnd());
 				assertEquals(0, generator.getSourceStart());
-				assertEquals(1, generator.getSourceEnd());
-				assertEquals("file.txt", generator.getSourcePath());
+				assertEquals(2, generator.getSourceEnd());
+				assertEquals(INTERESTING_FILE, generator.getSourcePath());
+
+				assertFalse(generator.next());
+			}
+		}
+	}
+
+	@Test
+	public void testMergeSingleBlame() throws Exception {
+		try (Git git = new Git(db);
+				RevWalk revWalk = new RevWalk(git.getRepository())) {
+
+			/**
+			 *
+			 *
+			 * <pre>
+			 *  refs/heads/master
+			 *      A
+			 *     / \       		 refs/heads/side
+			 *    /   ---------------->  side
+			 *   /                        |
+			 *  merge <-------------------
+			 * </pre>
+			 */
+
+			writeTrashFile(INTERESTING_FILE, join("1", "2"));
+			git.add().addFilepattern(INTERESTING_FILE).call();
+			RevCommit c1 = git.commit().setMessage("create file").call();
+
+			createBranch(c1, "refs/heads/side");
+			checkoutBranch("refs/heads/side");
+			writeTrashFile(INTERESTING_FILE, join("1", "2", "3", "4"));
+			git.add().addFilepattern(INTERESTING_FILE).call();
+			RevCommit sideCommit = git.commit()
+					.setMessage("amend file in another branch").call();
+
+			checkoutBranch("refs/heads/master");
+			git.merge().setMessage("merge").include(sideCommit)
+					.setStrategy(MergeStrategy.RESOLVE).call();
+
+			Iterator<RevCommit> it = git.log().call().iterator();
+			RevCommit mergeCommit = it.next();
+
+			RevCommit filteredC1 = new FilteredRevCommit(c1);
+			RevCommit filteredSide = new FilteredRevCommit(sideCommit,
+					filteredC1);
+			RevCommit filteredMerge = new FilteredRevCommit(mergeCommit,
+					filteredSide, filteredC1);
+
+			revWalk.parseHeaders(filteredMerge);
+
+			try (BlameGenerator generator = new BlameGenerator(db,
+					INTERESTING_FILE)) {
+				generator.push(filteredMerge);
+				assertEquals(4, generator.getResultContents().size());
 
 				assertTrue(generator.next());
-				assertEquals(c1, generator.getSourceCommit());
+				assertEquals(mergeCommit, generator.getSourceCommit());
 				assertEquals(2, generator.getRegionLength());
-				assertEquals(1, generator.getResultStart());
+				assertEquals(2, generator.getResultStart());
+				assertEquals(4, generator.getResultEnd());
+				assertEquals(2, generator.getSourceStart());
+				assertEquals(4, generator.getSourceEnd());
+				assertEquals(INTERESTING_FILE, generator.getSourcePath());
+
+				assertTrue(generator.next());
+				assertEquals(filteredC1, generator.getSourceCommit());
+				assertEquals(2, generator.getRegionLength());
+				assertEquals(0, generator.getResultStart());
+				assertEquals(2, generator.getResultEnd());
+				assertEquals(0, generator.getSourceStart());
+				assertEquals(2, generator.getSourceEnd());
+				assertEquals(INTERESTING_FILE, generator.getSourcePath());
+
+				assertFalse(generator.next());
+			}
+		}
+	}
+
+	@Test
+	public void testMergeBlame() throws Exception {
+		try (Git git = new Git(db);
+				RevWalk revWalk = new RevWalk(git.getRepository())) {
+
+			/**
+			 *
+			 *
+			 * <pre>
+			 *  refs/heads/master
+			 *      A
+			 *     / \       		 refs/heads/side
+			 *    B   ---------------->  side
+			 *   /                        |
+			 *  merge <-------------------
+			 * </pre>
+			 */
+			writeTrashFile(INTERESTING_FILE, join("1", "2"));
+			git.add().addFilepattern(INTERESTING_FILE).call();
+			RevCommit c1 = git.commit().setMessage("create file").call();
+
+			createBranch(c1, "refs/heads/side");
+			checkoutBranch("refs/heads/side");
+			writeTrashFile(INTERESTING_FILE, join("1", "2", "3"));
+			git.add().addFilepattern(INTERESTING_FILE).call();
+			RevCommit sideCommit = git.commit().setMessage("amend file").call();
+
+			checkoutBranch("refs/heads/master");
+			writeTrashFile(INTERESTING_FILE, join("1", "2", "4"));
+			git.add().addFilepattern(INTERESTING_FILE).call();
+			RevCommit c2 = git.commit().setMessage("delete and amend file")
+					.call();
+
+			git.merge().setMessage("merge").include(sideCommit)
+					.setStrategy(MergeStrategy.RESOLVE).call();
+			writeTrashFile(INTERESTING_FILE, join("1", "2", "3", "4"));
+			git.add().addFilepattern(INTERESTING_FILE).call();
+			RevCommit mergeCommit = git.commit().setMessage("merge commit")
+					.call();
+
+			RevCommit filteredC1 = new FilteredRevCommit(c1);
+			RevCommit filteredSide = new FilteredRevCommit(sideCommit,
+					filteredC1);
+			RevCommit filteredC2 = new FilteredRevCommit(c2, filteredC1);
+
+			RevCommit filteredMerge = new FilteredRevCommit(mergeCommit,
+					filteredSide, filteredC2);
+
+			revWalk.parseHeaders(filteredMerge);
+
+			try (BlameGenerator generator = new BlameGenerator(db,
+					INTERESTING_FILE)) {
+				generator.push(filteredMerge);
+				assertEquals(4, generator.getResultContents().size());
+
+				assertTrue(generator.next());
+				assertEquals(filteredC2, generator.getSourceCommit());
+				assertEquals(1, generator.getRegionLength());
+				assertEquals(3, generator.getResultStart());
+				assertEquals(4, generator.getResultEnd());
+				assertEquals(2, generator.getSourceStart());
+				assertEquals(3, generator.getSourceEnd());
+				assertEquals(INTERESTING_FILE, generator.getSourcePath());
+
+				assertTrue(generator.next());
+				assertEquals(filteredSide, generator.getSourceCommit());
+				assertEquals(1, generator.getRegionLength());
+				assertEquals(2, generator.getResultStart());
 				assertEquals(3, generator.getResultEnd());
+				assertEquals(2, generator.getSourceStart());
+				assertEquals(3, generator.getSourceEnd());
+				assertEquals(INTERESTING_FILE, generator.getSourcePath());
+
+				assertTrue(generator.next());
+				assertEquals(filteredC1, generator.getSourceCommit());
+				assertEquals(2, generator.getRegionLength());
+				assertEquals(0, generator.getResultStart());
+				assertEquals(2, generator.getResultEnd());
 				assertEquals(0, generator.getSourceStart());
 				assertEquals(2, generator.getSourceEnd());
-				assertEquals("file.txt", generator.getSourcePath());
+				assertEquals(INTERESTING_FILE, generator.getSourcePath());
 
 				assertFalse(generator.next());
 			}
 		}
 	}
 
+	@Test
+	public void testSingleBlame_compareWithWalk() throws Exception {
+		/**
+		 * <pre>
+		 * (ts) 	OTHER_FILE			INTERESTING_FILE
+		 * 1 		a
+		 * 2	 	a, b
+		 * 3							1, 2				c1 <--
+		 * 4	 	a, b, c										 |
+		 * 6							3, 1, 2				c2---
+		 * </pre>
+		 */
+		try (Git git = new Git(db);
+				RevWalk revWalk = new RevWalk(git.getRepository())) {
+			writeTrashFile(OTHER_FILE, join("a"));
+			git.add().addFilepattern(OTHER_FILE).call();
+			git.commit().setMessage("create file").call();
+
+			writeTrashFile(OTHER_FILE, join("a", "b"));
+			git.add().addFilepattern(OTHER_FILE).call();
+			git.commit().setMessage("amend file").call();
+
+			writeTrashFile(INTERESTING_FILE, join("1", "2"));
+			git.add().addFilepattern(INTERESTING_FILE).call();
+			RevCommit c1 = git.commit().setMessage("create file").call();
+
+			writeTrashFile(OTHER_FILE, join("a", "b", "c"));
+			git.add().addFilepattern(OTHER_FILE).call();
+			git.commit().setMessage("amend file").call();
+
+			writeTrashFile(INTERESTING_FILE, join("3", "1", "2"));
+			git.add().addFilepattern(INTERESTING_FILE).call();
+			RevCommit c2 = git.commit().setMessage("prepend").call();
+
+			RevCommit filteredC1 = new FilteredRevCommit(c1);
+			RevCommit filteredC2 = new FilteredRevCommit(c2, filteredC1);
+
+			revWalk.parseHeaders(filteredC2);
+
+			try (BlameGenerator g1 = new BlameGenerator(db, INTERESTING_FILE);
+					BlameGenerator g2 = new BlameGenerator(db,
+							INTERESTING_FILE)) {
+				g1.push(null, c2);
+				g2.push(null, filteredC2);
+
+				assertEquals(g1.getResultContents().size(),
+						g2.getResultContents().size()); // 3
+
+				assertTrue(g1.next());
+				assertTrue(g2.next());
+
+				assertEquals(g1.getSourceCommit(), g2.getSourceCommit()); // c2
+				assertEquals(INTERESTING_FILE, g1.getSourcePath());
+				assertEquals(g1.getRegionLength(), g2.getRegionLength()); // 1
+				assertEquals(g1.getResultStart(), g2.getResultStart()); // 0
+				assertEquals(g1.getResultEnd(), g2.getResultEnd()); // 1
+				assertEquals(g1.getSourceStart(), g2.getSourceStart()); // 0
+				assertEquals(g1.getSourceEnd(), g2.getSourceEnd()); // 1
+				assertEquals(g1.getSourcePath(), g2.getSourcePath()); // INTERESTING_FILE
+
+				assertTrue(g1.next());
+				assertTrue(g2.next());
+
+				assertEquals(g1.getSourceCommit(), g2.getSourceCommit()); // c1
+				assertEquals(g1.getRegionLength(), g2.getRegionLength()); // 2
+				assertEquals(g1.getResultStart(), g2.getResultStart()); // 1
+				assertEquals(g1.getResultEnd(), g2.getResultEnd()); // 3
+				assertEquals(g1.getSourceStart(), g2.getSourceStart()); // 0
+				assertEquals(g1.getSourceEnd(), g2.getSourceEnd()); // 2
+				assertEquals(g1.getSourcePath(), g2.getSourcePath()); // INTERESTING_FILE
+
+				assertFalse(g1.next());
+				assertFalse(g2.next());
+			}
+		}
+	}
+
 	@Test
 	public void testRenamedBoundLineDelete() throws Exception {
 		try (Git git = new Git(db)) {
@@ -87,7 +361,8 @@ public class BlameGeneratorTest extends RepositoryTestCase {
 			git.add().addFilepattern(FILENAME_2).call();
 			RevCommit c2 = git.commit().setMessage("change file2").call();
 
-			try (BlameGenerator generator = new BlameGenerator(db, FILENAME_2)) {
+			try (BlameGenerator generator = new BlameGenerator(db,
+					FILENAME_2)) {
 				generator.push(null, db.resolve(Constants.HEAD));
 				assertEquals(3, generator.getResultContents().size());
 
@@ -113,7 +388,8 @@ public class BlameGeneratorTest extends RepositoryTestCase {
 			}
 
 			// and test again with other BlameGenerator API:
-			try (BlameGenerator generator = new BlameGenerator(db, FILENAME_2)) {
+			try (BlameGenerator generator = new BlameGenerator(db,
+					FILENAME_2)) {
 				generator.push(null, db.resolve(Constants.HEAD));
 				BlameResult result = generator.computeBlameResult();
 
@@ -136,21 +412,22 @@ public class BlameGeneratorTest extends RepositoryTestCase {
 		try (Git git = new Git(db)) {
 			String[] content1 = new String[] { "first", "second", "third" };
 
-			writeTrashFile("file.txt", join(content1));
-			git.add().addFilepattern("file.txt").call();
+			writeTrashFile(INTERESTING_FILE, join(content1));
+			git.add().addFilepattern(INTERESTING_FILE).call();
 			git.commit().setMessage("create file").call();
 
 			String[] content2 = new String[] { "" };
 
-			writeTrashFile("file.txt", join(content2));
-			git.add().addFilepattern("file.txt").call();
+			writeTrashFile(INTERESTING_FILE, join(content2));
+			git.add().addFilepattern(INTERESTING_FILE).call();
 			git.commit().setMessage("create file").call();
 
-			writeTrashFile("file.txt", join(content1));
-			git.add().addFilepattern("file.txt").call();
+			writeTrashFile(INTERESTING_FILE, join(content1));
+			git.add().addFilepattern(INTERESTING_FILE).call();
 			RevCommit c3 = git.commit().setMessage("create file").call();
 
-			try (BlameGenerator generator = new BlameGenerator(db, "file.txt")) {
+			try (BlameGenerator generator = new BlameGenerator(db,
+					INTERESTING_FILE)) {
 				generator.push(null, db.resolve(Constants.HEAD));
 				assertEquals(3, generator.getResultContents().size());
 
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/blame/BlameGenerator.java b/org.eclipse.jgit/src/org/eclipse/jgit/blame/BlameGenerator.java
index 77967df2e5..93ddfc6607 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/blame/BlameGenerator.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/blame/BlameGenerator.java
@@ -129,6 +129,7 @@ public class BlameGenerator implements AutoCloseable {
 
 	/** Blame is currently assigned to this source. */
 	private Candidate outCandidate;
+
 	private Region outRegion;
 
 	/**
@@ -395,6 +396,35 @@ public class BlameGenerator implements AutoCloseable {
 		return copy;
 	}
 
+	/**
+	 * Push a candidate object onto the generator's traversal stack.
+	 * <p>
+	 * Candidates should be pushed in history order from oldest-to-newest.
+	 * Applications should push the starting commit first, then the index
+	 * revision (if the index is interesting), and finally the working tree copy
+	 * (if the working tree is interesting).
+	 *
+	 * @param blameCommit
+	 *            ordered commits to use instead of RevWalk.
+	 * @return {@code this}
+	 * @throws java.io.IOException
+	 *             the repository cannot be read.
+	 * @since 6.3
+	 */
+	public BlameGenerator push(RevCommit blameCommit) throws IOException {
+		if (!find(blameCommit, resultPath)) {
+			return this;
+		}
+
+		Candidate c = new Candidate(getRepository(), blameCommit, resultPath);
+		c.sourceBlob = idBuf.toObjectId();
+		c.loadText(reader);
+		c.regionList = new Region(0, 0, c.sourceText.size());
+		remaining = c.sourceText.size();
+		push(c);
+		return this;
+	}
+
 	/**
 	 * Push a candidate object onto the generator's traversal stack.
 	 * <p>
@@ -428,16 +458,7 @@ public class BlameGenerator implements AutoCloseable {
 		}
 
 		RevCommit commit = revPool.parseCommit(id);
-		if (!find(commit, resultPath))
-			return this;
-
-		Candidate c = new Candidate(getRepository(), commit, resultPath);
-		c.sourceBlob = idBuf.toObjectId();
-		c.loadText(reader);
-		c.regionList = new Region(0, 0, c.sourceText.size());
-		remaining = c.sourceText.size();
-		push(c);
-		return this;
+		return push(commit);
 	}
 
 	/**
@@ -605,7 +626,7 @@ public class BlameGenerator implements AutoCloseable {
 				// Do not generate a tip of a reverse. The region
 				// survives and should not appear to be deleted.
 
-			} else /* if (pCnt == 0) */{
+			} else /* if (pCnt == 0) */ {
 				// Root commit, with at least one surviving region.
 				// Assign the remaining blame here.
 				return result(n);
@@ -846,8 +867,8 @@ public class BlameGenerator implements AutoCloseable {
 				editList = new EditList(0);
 			} else {
 				p.loadText(reader);
-				editList = diffAlgorithm.diff(textComparator,
-						p.sourceText, n.sourceText);
+				editList = diffAlgorithm.diff(textComparator, p.sourceText,
+						n.sourceText);
 			}
 
 			if (editList.isEmpty()) {
-- 
2.39.5