Optimize RevWalk.getMergedInto()

Transitive Relation Definition:
On the DAG of commit history, if A can reach B, C can reach A, then C
can reach B.

Example:
As is shown in the graph below:

  1 - 2 - 3 - 4 (side)
            \
             5 -  6^ (master) - 7 (topic)

Find out which branches is 2 merged into:
After we calculated that master contains 2, we can mark 6 as TEMP_MARK
to avoid unwanted walks.
When we want to figure out if 2 is merge into the topic, the traversal
path would be [7, 6] instead of [7, 6, 5, 3, 2].

Test:
This change can significantly improve performance for tags.
On a copy of the Linux repository, the command 'git tag --contains
<commit>' had the following performance improvement:

commit      | Before   | After   | Rel %
47a44d27ca  | 29251ms  | 6687ms  | -77%
90327e7dff  | 21388ms  | 6256ms  | -70%
f85fac0efa  | 11150ms  | 7338ms  | -34%

The current version ignores tags, even though the tag is a type of
the ref.
Follow-up commits I'll fix it.

Change-Id: Ie6295ca4d16070499912af462239e679a97cce47
Signed-off-by: kylezhao <kylezhao@tencent.com>
Reviewed-by: Christian Halstrick <christian.halstrick@sap.com>
Reviewed-by: Martin Fick <mfick@codeaurora.org>

1 files changed, 15 insertions, 2 deletions

diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/RevWalkUtilsReachableTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/RevWalkUtilsReachableTest.java
index 200cb6a4fe..0a045c917b 100644
--- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/RevWalkUtilsReachableTest.java
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/RevWalkUtilsReachableTest.java
@@ -82,20 +82,33 @@ public class RevWalkUtilsReachableTest extends RevWalkTestCase {
 		 *  a   b
 		 *  |   |
 		 *  c   d
+		 *      | \
+		 *      f  e
+		 *      | /
+		 *      g
 		 */
 		RevCommit a = commit();
 		RevCommit b = commit();
 		RevCommit c = commit(a);
 		RevCommit d = commit(b);
+		RevCommit f = commit(d);
+		RevCommit e = commit(d);
+		RevCommit g = commit(f, e);
 		Ref branchA = branch("a", a);
 		Ref branchB = branch("b", b);
 		Ref branchC = branch("c", c);
 		Ref branchD = branch("d", d);
+		Ref branchE = branch("e", e);
+		Ref branchF = branch("f", f);
+		Ref branchG = branch("g", g);
 
 		assertContains(a, asList(branchA, branchC));
-		assertContains(b, asList(branchB, branchD));
+		assertContains(b, asList(branchB, branchD, branchE, branchF, branchG));
 		assertContains(c, asList(branchC));
-		assertContains(d, asList(branchD));
+		assertContains(d, asList(branchD, branchE, branchF, branchG));
+		assertContains(e, asList(branchE, branchG));
+		assertContains(f, asList(branchF, branchG));
+		assertContains(g, asList(branchG));
 	}
 
 	private Ref branch(String name, RevCommit dst) throws Exception {