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, 9 insertions, 2 deletions

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 d5b3643af9..d2ab4a19e8 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevWalk.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevWalk.java
@@ -528,6 +528,7 @@ public class RevWalk implements Iterable<RevCommit>, AutoCloseable {
 				Enum returnStrategy, ProgressMonitor monitor) throws IOException {
 		List<Ref> result = new ArrayList<>();
 		List<RevCommit> uninteresting = new ArrayList<>();
+		List<RevCommit> marked = new ArrayList<>();
 		RevFilter oldRF = filter;
 		TreeFilter oldTF = treeFilter;
 		try {
@@ -545,17 +546,20 @@ public class RevWalk implements Iterable<RevCommit>, AutoCloseable {
 					continue;
 				}
 				RevCommit c = (RevCommit) o;
-				resetRetain(RevFlag.UNINTERESTING);
+				reset(UNINTERESTING | TEMP_MARK);
 				markStart(c);
 				boolean commitFound = false;
 				RevCommit next;
 				while ((next = next()) != null) {
-					if (References.isSameObject(next, needle)) {
+					if (References.isSameObject(next, needle)
+							|| (next.flags & TEMP_MARK) != 0) {
 						result.add(r);
 						if (returnStrategy == GetMergedIntoStrategy.RETURN_ON_FIRST_FOUND) {
 							return result;
 						}
 						commitFound = true;
+						c.flags |= TEMP_MARK;
+						marked.add(c);
 						break;
 					}
 				}
@@ -571,6 +575,9 @@ public class RevWalk implements Iterable<RevCommit>, AutoCloseable {
 			roots.addAll(uninteresting);
 			filter = oldRF;
 			treeFilter = oldTF;
+			for (RevCommit c : marked) {
+				c.flags &= ~TEMP_MARK;
+			}
 		}
 		return result;
 	}