Introduce getMergedInto(RevCommit commit, Collection<Ref> refs)

In cases where we need to determine if a given commit is merged
into many refs, using isMergedInto(base, tip) for each ref would
cause multiple unwanted walks.

getMergedInto() marks the unreachable commits as uninteresting
which would then avoid walking that same path again.

Using the same api, also introduce isMergedIntoAny() and
isMergedIntoAll()

Change-Id: I65de9873dce67af9c415d1d236bf52d31b67e8fe
Signed-off-by: Adithya Chakilam <quic_achakila@quicinc.com>
Signed-off-by: Matthias Sohn <matthias.sohn@sap.com>

3 files changed, 207 insertions, 0 deletions

diff --git a/org.eclipse.jgit.junit/src/org/eclipse/jgit/junit/RepositoryTestCase.java b/org.eclipse.jgit.junit/src/org/eclipse/jgit/junit/RepositoryTestCase.java
index 64556acc1c..5622108dcd 100644
--- a/org.eclipse.jgit.junit/src/org/eclipse/jgit/junit/RepositoryTestCase.java
+++ b/org.eclipse.jgit.junit/src/org/eclipse/jgit/junit/RepositoryTestCase.java
@@ -25,6 +25,7 @@ import java.io.InputStreamReader;
 import java.io.Reader;
 import java.nio.file.Path;
 import java.time.Instant;
+import java.util.List;
 import java.util.Map;
 import java.util.concurrent.TimeUnit;
 
@@ -39,6 +40,7 @@ import org.eclipse.jgit.lib.Constants;
 import org.eclipse.jgit.lib.FileMode;
 import org.eclipse.jgit.lib.ObjectId;
 import org.eclipse.jgit.lib.ObjectInserter;
+import org.eclipse.jgit.lib.Ref;
 import org.eclipse.jgit.lib.RefUpdate;
 import org.eclipse.jgit.lib.Repository;
 import org.eclipse.jgit.revwalk.RevCommit;
@@ -386,6 +388,16 @@ public abstract class RepositoryTestCase extends LocalDiskRepositoryTestCase {
 	}
 
 	/**
+	 * Get all Refs
+	 *
+	 * @return list of refs
+	 * @throws IOException
+	 */
+	public List<Ref> getRefs() throws IOException {
+		return db.getRefDatabase().getRefs();
+	}
+
+	/**
 	 * Checkout a branch
 	 *
 	 * @param branchName
diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/RevWalkMergedIntoTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/RevWalkMergedIntoTest.java
index 2c21eb60d3..2f16aa49e8 100644
--- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/RevWalkMergedIntoTest.java
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/RevWalkMergedIntoTest.java
@@ -11,6 +11,9 @@ package org.eclipse.jgit.revwalk;
 
 import static org.junit.Assert.assertTrue;
 
+import java.util.List;
+import java.util.stream.Collectors;
+import org.eclipse.jgit.lib.Ref;
 import org.junit.Test;
 
 public class RevWalkMergedIntoTest extends RevWalkTestCase {
@@ -44,4 +47,82 @@ public class RevWalkMergedIntoTest extends RevWalkTestCase {
 		final RevCommit t = commit(n, o);
 		assertTrue(rw.isMergedInto(b, t));
 	}
+
+	@Test
+	public void testGetMergedInto() throws Exception {
+		/*
+		 *          i
+		 *         / \
+		 *        A   o
+		 *       / \   \
+		 *      o1  o2  E
+		 *     / \ / \
+		 *    B   C   D
+		 */
+		String b = "refs/heads/b";
+		String c = "refs/heads/c";
+		String d = "refs/heads/d";
+		String e = "refs/heads/e";
+		final RevCommit i = commit();
+		final RevCommit a = commit(i);
+		final RevCommit o1 = commit(a);
+		final RevCommit o2 = commit(a);
+		createBranch(commit(o1), b);
+		createBranch(commit(o1, o2), c);
+		createBranch(commit(o2), d);
+		createBranch(commit(commit(i)), e);
+
+		List<String>  modifiedResult = rw.getMergedInto(a, getRefs())
+				.stream().map(Ref::getName).collect(Collectors.toList());
+
+		assertTrue(modifiedResult.size() == 3);
+		assertTrue(modifiedResult.contains(b));
+		assertTrue(modifiedResult.contains(c));
+		assertTrue(modifiedResult.contains(d));
+	}
+
+	@Test
+	public void testIsMergedIntoAny() throws Exception {
+		/*
+		 *          i
+		 *         / \
+		 *        A   o
+		 *       /     \
+		 *      o       C
+		 *     /
+		 *    B
+		 */
+		String b = "refs/heads/b";
+		String c = "refs/heads/c";
+		final RevCommit i = commit();
+		final RevCommit a = commit(i);
+		createBranch(commit(commit(a)), b);
+		createBranch(commit(commit(i)), c);
+
+		assertTrue( rw.isMergedIntoAny(a, getRefs()));
+	}
+
+	@Test
+	public void testIsMergedIntoAll() throws Exception {
+		/*
+		 *
+		 *        A
+		 *       / \
+		 *      o1  o2
+		 *     / \ / \
+		 *    B   C   D
+		 */
+
+		String b = "refs/heads/b";
+		String c = "refs/heads/c";
+		String d = "refs/heads/c";
+		final RevCommit a = commit();
+		final RevCommit o1 = commit(a);
+		final RevCommit o2 = commit(a);
+		createBranch(commit(o1), b);
+		createBranch(commit(o1, o2), c);
+		createBranch(commit(o2), d);
+
+		assertTrue(rw.isMergedIntoAll(a, getRefs()));
+	}
 }
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 631d861c0d..3ca2ff6033 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevWalk.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/RevWalk.java
@@ -36,6 +36,7 @@ import org.eclipse.jgit.lib.ObjectId;
 import org.eclipse.jgit.lib.ObjectIdOwnerMap;
 import org.eclipse.jgit.lib.ObjectLoader;
 import org.eclipse.jgit.lib.ObjectReader;
+import org.eclipse.jgit.lib.Ref;
 import org.eclipse.jgit.lib.Repository;
 import org.eclipse.jgit.revwalk.filter.RevFilter;
 import org.eclipse.jgit.treewalk.filter.TreeFilter;
@@ -181,6 +182,12 @@ public class RevWalk implements Iterable<RevCommit>, AutoCloseable {
 
 	boolean shallowCommitsInitialized;
 
+	private enum GetMergedIntoStrategy {
+		RETURN_ON_FIRST_FOUND,
+		RETURN_ON_FIRST_NOT_FOUND,
+		EVALUATE_ALL
+	}
+
 	/**
 	 * Create a new revision walker for a given repository.
 	 *
@@ -425,6 +432,113 @@ public class RevWalk implements Iterable<RevCommit>, AutoCloseable {
 	}
 
 	/**
+	 * Determine the Refs into which a commit is merged.
+	 * <p>
+	 * A commit is merged into a ref if we can find a path of commits that leads
+	 * from that specific ref and ends at <code>commit</code>.
+	 * <p>
+	 *
+	 * @param commit
+	 *            commit the caller thinks is reachable from <code>refs</code>.
+	 * @param refs
+	 *            refs to start iteration from, and which is most likely a
+	 *            descendant (child) of <code>commit</code>.
+	 * @return list of refs that are reachable from <code>commit</code>.
+	 * @throws java.io.IOException
+	 *             a pack file or loose object could not be read.
+	 * @since 5.12
+	 */
+	public List<Ref> getMergedInto(RevCommit commit, Collection<Ref> refs)
+			throws IOException{
+		return getMergedInto(commit, refs, GetMergedIntoStrategy.EVALUATE_ALL);
+	}
+
+	/**
+	 * Determine if a <code>commit</code> is merged into any of the given
+	 * <code>refs</code>.
+	 *
+	 * @param commit
+	 *            commit the caller thinks is reachable from <code>refs</code>.
+	 * @param refs
+	 *            refs to start iteration from, and which is most likely a
+	 *            descendant (child) of <code>commit</code>.
+	 * @return true if commit is merged into any of the refs; false otherwise.
+	 * @throws java.io.IOException
+	 *             a pack file or loose object could not be read.
+	 * @since 5.12
+	 */
+	public boolean isMergedIntoAny(RevCommit commit, Collection<Ref> refs)
+			throws IOException {
+		return getMergedInto(commit, refs,
+				GetMergedIntoStrategy.RETURN_ON_FIRST_FOUND).size() > 0;
+	}
+
+	/**
+	 * Determine if a <code>commit</code> is merged into all of the given
+	 * <code>refs</code>.
+	 *
+	 * @param commit
+	 *            commit the caller thinks is reachable from <code>refs</code>.
+	 * @param refs
+	 *            refs to start iteration from, and which is most likely a
+	 *            descendant (child) of <code>commit</code>.
+	 * @return true if commit is merged into all of the refs; false otherwise.
+	 * @throws java.io.IOException
+	 *             a pack file or loose object could not be read.
+	 * @since 5.12
+	 */
+	public boolean isMergedIntoAll(RevCommit commit, Collection<Ref> refs)
+			throws IOException {
+		return getMergedInto(commit, refs,
+				GetMergedIntoStrategy.RETURN_ON_FIRST_NOT_FOUND).size()
+				== refs.size();
+	}
+
+	private List<Ref> getMergedInto(RevCommit needle, Collection<Ref> haystacks,
+			Enum returnStrategy) throws IOException {
+		List<Ref> result = new ArrayList<>();
+		RevFilter oldRF = filter;
+		TreeFilter oldTF = treeFilter;
+		try {
+			finishDelayedFreeFlags();
+			filter = RevFilter.ALL;
+			treeFilter = TreeFilter.ALL;
+			for (Ref r: haystacks) {
+				RevObject o = parseAny(r.getObjectId());
+				if (!(o instanceof RevCommit)) {
+					continue;
+				}
+				RevCommit c = (RevCommit) o;
+				resetRetain(RevFlag.UNINTERESTING);
+				markStart(c);
+				boolean commitFound = false;
+				RevCommit next;
+				while ((next = next()) != null) {
+					if (References.isSameObject(next, needle)) {
+						result.add(r);
+						if (returnStrategy == GetMergedIntoStrategy.RETURN_ON_FIRST_FOUND) {
+							return result;
+						}
+						commitFound = true;
+						break;
+					}
+				}
+				if(!commitFound){
+					markUninteresting(c);
+					if (returnStrategy == GetMergedIntoStrategy.RETURN_ON_FIRST_NOT_FOUND) {
+						return result;
+					}
+				}
+			}
+		} finally {
+			reset(~freeFlags & APP_FLAGS);
+			filter = oldRF;
+			treeFilter = oldTF;
+		}
+		return result;
+	}
+
+	/**
 	 * Pop the next most recent commit.
 	 *
 	 * @return next most recent commit; null if traversal is over.