ReachabilityChecker: Default implementation with a RevWalk

It is common to check if a certain commit is reachable from some
starting points. For example gitiles does it to check if a commit
is visible to a user based on its permissions.

Offer this functionality in JGit.

Split the interface as the next commit will introduce an implementation
using bitmap indices.

Change-Id: I0933b305c8d734f7a64502910ff4d9ef4fc92ae1
Signed-off-by: Ivan Frade <ifrade@google.com>

4 files changed, 413 insertions, 0 deletions

diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/PedestrianReachabilityCheckerTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/PedestrianReachabilityCheckerTest.java
new file mode 100644
index 0000000000..8d3e78c1fe
--- /dev/null
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/PedestrianReachabilityCheckerTest.java
@@ -0,0 +1,57 @@
+/*
+ * Copyright (C) 2019, Google LLC.
+ * and other copyright owners as documented in the project's IP log.
+ *
+ * This program and the accompanying materials are made available
+ * under the terms of the Eclipse Distribution License v1.0 which
+ * accompanies this distribution, is reproduced below, and is
+ * available at http://www.eclipse.org/org/documents/edl-v10.php
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above
+ *   copyright notice, this list of conditions and the following
+ *   disclaimer in the documentation and/or other materials provided
+ *   with the distribution.
+ *
+ * - Neither the name of the Eclipse Foundation, Inc. nor the
+ *   names of its contributors may be used to endorse or promote
+ *   products derived from this software without specific prior
+ *   written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
+ * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+package org.eclipse.jgit.revwalk;
+
+import org.eclipse.jgit.internal.storage.file.FileRepository;
+import org.eclipse.jgit.junit.TestRepository;
+
+public class PedestrianReachabilityCheckerTest
+		extends ReachabilityCheckerTestCase {
+
+	@Override
+	protected ReachabilityChecker getChecker(
+			TestRepository<FileRepository> repository) {
+		return new PedestrianReachabilityChecker(true, repository.getRevWalk());
+	}
+
+}
diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/ReachabilityCheckerTestCase.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/ReachabilityCheckerTestCase.java
new file mode 100644
index 0000000000..dd73e35727
--- /dev/null
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/ReachabilityCheckerTestCase.java
@@ -0,0 +1,168 @@
+/*
+ * Copyright (C) 2019, Google LLC.
+ * and other copyright owners as documented in the project's IP log.
+ *
+ * This program and the accompanying materials are made available
+ * under the terms of the Eclipse Distribution License v1.0 which
+ * accompanies this distribution, is reproduced below, and is
+ * available at http://www.eclipse.org/org/documents/edl-v10.php
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above
+ *   copyright notice, this list of conditions and the following
+ *   disclaimer in the documentation and/or other materials provided
+ *   with the distribution.
+ *
+ * - Neither the name of the Eclipse Foundation, Inc. nor the
+ *   names of its contributors may be used to endorse or promote
+ *   products derived from this software without specific prior
+ *   written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
+ * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+package org.eclipse.jgit.revwalk;
+
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+
+import java.util.Arrays;
+import java.util.Optional;
+
+import org.eclipse.jgit.internal.storage.file.FileRepository;
+import org.eclipse.jgit.junit.LocalDiskRepositoryTestCase;
+import org.eclipse.jgit.junit.TestRepository;
+import org.junit.Before;
+import org.junit.Test;
+
+public abstract class ReachabilityCheckerTestCase
+		extends LocalDiskRepositoryTestCase {
+
+	protected abstract ReachabilityChecker getChecker(
+			TestRepository<FileRepository> repository) throws Exception;
+
+	TestRepository<FileRepository> repo;
+
+	/** {@inheritDoc} */
+	@Override
+	@Before
+	public void setUp() throws Exception {
+		super.setUp();
+		FileRepository db = createWorkRepository();
+		repo = new TestRepository<>(db);
+	}
+
+	@Test
+	public void reachable() throws Exception {
+		RevCommit a = repo.commit().create();
+		RevCommit b1 = repo.commit(a);
+		RevCommit b2 = repo.commit(b1);
+		RevCommit c1 = repo.commit(a);
+		RevCommit c2 = repo.commit(c1);
+		repo.update("refs/heads/checker", b2);
+
+		ReachabilityChecker checker = getChecker(repo);
+
+		assertReachable("reachable from one tip",
+				checker.areAllReachable(Arrays.asList(a), Arrays.asList(c2)));
+		assertReachable("reachable from another tip",
+				checker.areAllReachable(Arrays.asList(a), Arrays.asList(b2)));
+		assertReachable("reachable from itself",
+				checker.areAllReachable(Arrays.asList(a), Arrays.asList(b2)));
+	}
+
+	@Test
+	public void reachable_merge() throws Exception {
+		RevCommit a = repo.commit().create();
+		RevCommit b1 = repo.commit(a);
+		RevCommit b2 = repo.commit(b1);
+		RevCommit c1 = repo.commit(a);
+		RevCommit c2 = repo.commit(c1);
+		RevCommit merge = repo.commit(c2, b2);
+		repo.update("refs/heads/checker", merge);
+
+		ReachabilityChecker checker = getChecker(repo);
+
+		assertReachable("reachable through one branch",
+				checker.areAllReachable(Arrays.asList(b1),
+						Arrays.asList(merge)));
+		assertReachable("reachable through another branch",
+				checker.areAllReachable(Arrays.asList(c1),
+						Arrays.asList(merge)));
+		assertReachable("reachable, before the branching",
+				checker.areAllReachable(Arrays.asList(a),
+						Arrays.asList(merge)));
+	}
+
+	@Test
+	public void unreachable_isLaterCommit() throws Exception {
+		RevCommit a = repo.commit().create();
+		RevCommit b1 = repo.commit(a);
+		RevCommit b2 = repo.commit(b1);
+		repo.update("refs/heads/checker", b2);
+
+		ReachabilityChecker checker = getChecker(repo);
+
+		assertUnreachable("unreachable from the future",
+				checker.areAllReachable(Arrays.asList(b2), Arrays.asList(b1)));
+	}
+
+	@Test
+	public void unreachable_differentBranch() throws Exception {
+		RevCommit a = repo.commit().create();
+		RevCommit b1 = repo.commit(a);
+		RevCommit b2 = repo.commit(b1);
+		RevCommit c1 = repo.commit(a);
+		repo.update("refs/heads/checker", b2);
+
+		ReachabilityChecker checker = getChecker(repo);
+
+		assertUnreachable("unreachable from different branch",
+				checker.areAllReachable(Arrays.asList(c1), Arrays.asList(b2)));
+	}
+
+	@Test
+	public void reachable_longChain() throws Exception {
+		RevCommit root = repo.commit().create();
+		RevCommit head = root;
+		for (int i = 0; i < 10000; i++) {
+			head = repo.commit(head);
+		}
+		repo.update("refs/heads/master", head);
+
+		ReachabilityChecker checker = getChecker(repo);
+
+		assertReachable("reachable with long chain in the middle", checker
+				.areAllReachable(Arrays.asList(root), Arrays.asList(head)));
+	}
+
+	private static void assertReachable(String msg,
+			Optional<RevCommit> result) {
+		assertFalse(msg, result.isPresent());
+	}
+
+	private static void assertUnreachable(String msg,
+			Optional<RevCommit> result) {
+		assertTrue(msg, result.isPresent());
+	}
+
+}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/PedestrianReachabilityChecker.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/PedestrianReachabilityChecker.java
new file mode 100644
index 0000000000..2704b69cb0
--- /dev/null
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/PedestrianReachabilityChecker.java
@@ -0,0 +1,98 @@
+/*
+ * Copyright (C) 2019, Google LLC.
+ * and other copyright owners as documented in the project's IP log.
+ *
+ * This program and the accompanying materials are made available
+ * under the terms of the Eclipse Distribution License v1.0 which
+ * accompanies this distribution, is reproduced below, and is
+ * available at http://www.eclipse.org/org/documents/edl-v10.php
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above
+ *   copyright notice, this list of conditions and the following
+ *   disclaimer in the documentation and/or other materials provided
+ *   with the distribution.
+ *
+ * - Neither the name of the Eclipse Foundation, Inc. nor the
+ *   names of its contributors may be used to endorse or promote
+ *   products derived from this software without specific prior
+ *   written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
+ * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+package org.eclipse.jgit.revwalk;
+
+import java.io.IOException;
+import java.util.Collection;
+import java.util.Optional;
+
+import org.eclipse.jgit.errors.IncorrectObjectTypeException;
+import org.eclipse.jgit.errors.MissingObjectException;
+
+/**
+ * Checks the reachability walking the graph from the starters towards the
+ * target.
+ *
+ * @since 5.5
+ */
+public class PedestrianReachabilityChecker implements ReachabilityChecker {
+
+	private final boolean topoSort;
+
+	private final RevWalk walk;
+
+	/**
+	 * New instance of the reachability checker using a existing walk.
+	 *
+	 * @param topoSort
+	 *            walk commits in topological order
+	 * @param walk
+	 *            RevWalk instance to reuse. Caller retains ownership.
+	 */
+	public PedestrianReachabilityChecker(boolean topoSort,
+			RevWalk walk) {
+		this.topoSort = topoSort;
+		this.walk = walk;
+	}
+
+	@Override
+	public Optional<RevCommit> areAllReachable(Collection<RevCommit> targets,
+			Collection<RevCommit> starters)
+					throws MissingObjectException, IncorrectObjectTypeException,
+					IOException {
+		walk.reset();
+		if (topoSort) {
+			walk.sort(RevSort.TOPO);
+		}
+
+		for (RevCommit target: targets) {
+			walk.markStart(target);
+		}
+
+		for (RevCommit starter : starters) {
+			walk.markUninteresting(starter);
+		}
+
+		return Optional.ofNullable(walk.next());
+	}
+}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/ReachabilityChecker.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/ReachabilityChecker.java
new file mode 100644
index 0000000000..cf5f4a28cf
--- /dev/null
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/ReachabilityChecker.java
@@ -0,0 +1,90 @@
+/*
+ * Copyright (C) 2019, Google LLC.
+ * and other copyright owners as documented in the project's IP log.
+ *
+ * This program and the accompanying materials are made available
+ * under the terms of the Eclipse Distribution License v1.0 which
+ * accompanies this distribution, is reproduced below, and is
+ * available at http://www.eclipse.org/org/documents/edl-v10.php
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above
+ *   copyright notice, this list of conditions and the following
+ *   disclaimer in the documentation and/or other materials provided
+ *   with the distribution.
+ *
+ * - Neither the name of the Eclipse Foundation, Inc. nor the
+ *   names of its contributors may be used to endorse or promote
+ *   products derived from this software without specific prior
+ *   written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
+ * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+package org.eclipse.jgit.revwalk;
+
+import java.io.IOException;
+import java.util.Collection;
+import java.util.Optional;
+
+import org.eclipse.jgit.errors.IncorrectObjectTypeException;
+import org.eclipse.jgit.errors.MissingObjectException;
+
+/**
+ * Check if a commit is reachable from a collection of starting commits.
+ * <p>
+ * Note that this checks the reachability of commits (and tags). Trees, blobs or
+ * any other object will cause IncorrectObjectTypeException exceptions.
+ *
+ * @since 5.5
+ */
+public interface ReachabilityChecker {
+
+	/**
+	 * Check if all targets are reachable from the {@code starter} commits.
+	 * <p>
+	 * Caller should parse the objectIds (preferably with
+	 * {@code walk.parseCommit()} and handle missing/incorrect type objects
+	 * before calling this method.
+	 *
+	 * @param targets
+	 *            commits to reach.
+	 * @param starters
+	 *            known starting points.
+	 * @return An unreachable target if at least one of the targets is
+	 *         unreachable. An empty optional if all targets are reachable from
+	 *         the starters.
+	 *
+	 * @throws MissingObjectException
+	 *             if any of the incoming objects doesn't exist in the
+	 *             repository.
+	 * @throws IncorrectObjectTypeException
+	 *             if any of the incoming objects is not a commit or a tag.
+	 * @throws IOException
+	 *             if any of the underlying indexes or readers can not be
+	 *             opened.
+	 */
+	Optional<RevCommit> areAllReachable(Collection<RevCommit> targets,
+			Collection<RevCommit> starters)
+			throws MissingObjectException, IncorrectObjectTypeException,
+			IOException;
+}