RevWalk: use generation number to optimize getMergedInto()

A commit A can reach a commit B only if the generation number of A is
strictly larger than the generation number of B. This condition allows
significantly short-circuiting commit-graph walks.

On a copy of the Linux repository where HEAD is contained in v6.3-rc4
but no earlier tag, the command 'git tag --contains HEAD' of
ListTagCommand#call() had the following peformance improvement:
(excluded the startup time of the repo)

Before: 2649ms    (core.commitgraph=true)
        11909ms   (core.commitgraph=false)
After:  91ms     (core.commitgraph=true)
        11934ms   (core.commitgraph=false)

Bug: 574368
Change-Id: Ia2efaa4e9ae598266f72e70eb7e3b27655cbf85b
Signed-off-by: kylezhao <kylezhao@tencent.com>

2 files changed, 103 insertions, 0 deletions

diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/RevWalkCommitGraphTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/RevWalkCommitGraphTest.java
index 97d3f81b9b..3cc0368943 100644
--- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/RevWalkCommitGraphTest.java
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/RevWalkCommitGraphTest.java
@@ -10,6 +10,7 @@
 
 package org.eclipse.jgit.revwalk;
 
+import static java.util.Arrays.asList;
 import static org.eclipse.jgit.internal.storage.commitgraph.CommitGraph.EMPTY;
 import static org.junit.Assert.assertArrayEquals;
 import static org.junit.Assert.assertEquals;
@@ -18,12 +19,15 @@ import static org.junit.Assert.assertNotNull;
 import static org.junit.Assert.assertNull;
 import static org.junit.Assert.assertTrue;
 
+import java.io.IOException;
 import java.util.ArrayList;
 import java.util.Collections;
+import java.util.Comparator;
 import java.util.List;
 
 import org.eclipse.jgit.api.Git;
 import org.eclipse.jgit.internal.storage.file.GC;
+import org.eclipse.jgit.lib.AnyObjectId;
 import org.eclipse.jgit.lib.ConfigConstants;
 import org.eclipse.jgit.lib.Constants;
 import org.eclipse.jgit.lib.Ref;
@@ -254,6 +258,95 @@ public class RevWalkCommitGraphTest extends RevWalkTestCase {
 		testRevWalkBehavior("commits/8", "merge/2");
 	}
 
+	@Test
+	public void testMergedInto() throws Exception {
+		RevCommit c1 = commit();
+		Ref branch1 = branch(c1, "commits/1");
+		RevCommit c2 = commit(c1);
+		Ref branch2 = branch(c2, "commits/2");
+		RevCommit c3 = commit(c2);
+		Ref branch3 = branch(c3, "commits/3");
+		RevCommit c4 = commit(c1);
+		Ref branch4 = branch(c4, "commits/4");
+		RevCommit c5 = commit(c4);
+		Ref branch5 = branch(c5, "commits/5");
+		enableAndWriteCommitGraph();
+		RevCommit c6 = commit(c1);
+		Ref branch6 = branch(c6, "commits/6");
+		RevCommit c7 = commit(c2, c4);
+		Ref branch7 = branch(c7, "commits/7");
+		RevCommit c8 = commit(c5);
+		Ref branch8 = branch(c8, "commits/8");
+		RevCommit c9 = commit(c4, c6);
+		Ref branch9 = branch(c9, "commits/9");
+
+		/*
+		 * <pre>
+		 * current graph structure:
+		 *       8
+		 *       |
+		 *  3  7 5  9
+		 *  |/  \|/  \
+		 *  2    4    6
+		 *  |___/____/
+		 *  1
+		 * </pre>
+		 *
+		 * [6, 7, 8, 9] are not in commit-graph.
+		 */
+
+		reinitializeRevWalk();
+		assertFalse(isObjectIdInGraph(c9));
+		assertRefsEquals(asList(branch9), allMergedInto(c9));
+
+		assertFalse(isObjectIdInGraph(c8));
+		assertRefsEquals(asList(branch8), allMergedInto(c8));
+
+		assertFalse(isObjectIdInGraph(c7));
+		assertRefsEquals(asList(branch7), allMergedInto(c7));
+
+		assertFalse(isObjectIdInGraph(c6));
+		assertRefsEquals(asList(branch6, branch9), allMergedInto(c6));
+
+		assertTrue(isObjectIdInGraph(c5));
+		assertRefsEquals(asList(branch5, branch8), allMergedInto(c5));
+
+		assertTrue(isObjectIdInGraph(c4));
+		assertRefsEquals(asList(branch4, branch5, branch7, branch8, branch9),
+				allMergedInto(c4));
+
+		assertTrue(isObjectIdInGraph(c3));
+		assertRefsEquals(asList(branch3), allMergedInto(c3));
+
+		assertTrue(isObjectIdInGraph(c2));
+		assertRefsEquals(asList(branch2, branch3, branch7), allMergedInto(c2));
+
+		assertTrue(isObjectIdInGraph(c1));
+		assertRefsEquals(asList(branch1, branch2, branch3, branch4, branch5,
+				branch6, branch7, branch8, branch9), allMergedInto(c1));
+	}
+
+	boolean isObjectIdInGraph(AnyObjectId id) {
+		return rw.commitGraph().findGraphPosition(id) >= 0;
+	}
+
+	List<Ref> allMergedInto(RevCommit needle) throws IOException {
+		List<Ref> refs = db.getRefDatabase().getRefs();
+		return rw.getMergedInto(rw.lookupCommit(needle), refs);
+	}
+
+	void assertRefsEquals(List<Ref> expecteds, List<Ref> actuals) {
+		assertEquals(expecteds.size(), actuals.size());
+		Collections.sort(expecteds, Comparator.comparing(Ref::getName));
+		Collections.sort(actuals, Comparator.comparing(Ref::getName));
+		for (int i = 0; i < expecteds.size(); i++) {
+			Ref expected = expecteds.get(i);
+			Ref actual = actuals.get(i);
+			assertEquals(expected.getName(), actual.getName());
+			assertEquals(expected.getObjectId(), actual.getObjectId());
+		}
+	}
+
 	void testRevWalkBehavior(String branch, String compare) throws Exception {
 		assertCommits(
 				travel(TreeFilter.ALL, RevFilter.MERGE_BASE, RevSort.NONE, true,
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevWalk.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevWalk.java
index 9da7105566..3737c6b67b 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevWalk.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevWalk.java
@@ -550,6 +550,12 @@ public class RevWalk implements Iterable<RevCommit>, AutoCloseable {
 			reset(~freeFlags & APP_FLAGS);
 			filter = RevFilter.ALL;
 			treeFilter = TreeFilter.ALL;
+
+			// Make sure commit is parsed from commit-graph
+			if ((needle.flags & PARSED) == 0) {
+				needle.parseHeaders(this);
+			}
+			int cutoff = needle.getGeneration();
 			for (Ref r : haystacks) {
 				if (monitor.isCancelled()) {
 					return result;
@@ -565,6 +571,10 @@ public class RevWalk implements Iterable<RevCommit>, AutoCloseable {
 				boolean commitFound = false;
 				RevCommit next;
 				while ((next = next()) != null) {
+					if (next.getGeneration() < cutoff) {
+						markUninteresting(next);
+						uninteresting.add(next);
+					}
 					if (References.isSameObject(next, needle)
 							|| (next.flags & TEMP_MARK) != 0) {
 						result.add(r);