Merge changes from topic 'reachability-2'

* changes:
  UploadPack: Use reachability checker to validate non-advertised wants
  BitmappedReachabilityChecker: Reachability check using bitmaps
  BitmapCalculator: Get the reachability bitmap of a commit
  ReachabilityChecker: Default implementation with a RevWalk

9 files changed, 914 insertions, 44 deletions

diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/BitmapCalculatorTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/BitmapCalculatorTest.java
new file mode 100644
index 0000000000..3a78e1e623
--- /dev/null
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/BitmapCalculatorTest.java
@@ -0,0 +1,139 @@
+package org.eclipse.jgit.revwalk;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+
+import org.eclipse.jgit.internal.storage.file.FileRepository;
+import org.eclipse.jgit.internal.storage.file.GC;
+import org.eclipse.jgit.junit.LocalDiskRepositoryTestCase;
+import org.eclipse.jgit.junit.TestRepository;
+import org.eclipse.jgit.lib.BitmapIndex.BitmapBuilder;
+import org.eclipse.jgit.lib.NullProgressMonitor;
+import org.eclipse.jgit.lib.ProgressMonitor;
+import org.junit.Before;
+import org.junit.Test;
+
+public class BitmapCalculatorTest extends LocalDiskRepositoryTestCase {
+	TestRepository<FileRepository> repo;
+
+	/** {@inheritDoc} */
+	@Override
+	@Before
+	public void setUp() throws Exception {
+		super.setUp();
+		FileRepository db = createWorkRepository();
+		repo = new TestRepository<>(db);
+	}
+
+	@Test
+	public void addOnlyCommits() throws Exception {
+		RevBlob abBlob = repo.blob("a_b_content");
+		RevCommit root = repo.commit().add("a/b", abBlob).create();
+		repo.update("refs/heads/master", root);
+
+		// GC creates bitmap index with ALL objects
+		GC gc = new GC(repo.getRepository());
+		gc.setAuto(false);
+		gc.gc();
+
+		// These objects are not in the bitmap index.
+		RevBlob acBlob = repo.blob("a_c_content");
+		RevCommit head = repo.commit().parent(root).add("a/c", acBlob).create();
+		repo.update("refs/heads/master", head);
+
+		BitmapCalculator bitmapWalker = new BitmapCalculator(repo.getRevWalk());
+		BitmapBuilder bitmap = bitmapWalker
+				.getBitmap(head, NullProgressMonitor.INSTANCE);
+
+		assertTrue(bitmap.contains(root.getId()));
+		assertTrue(bitmap.contains(root.getTree().getId()));
+		assertTrue(bitmap.contains(abBlob.getId()));
+
+		// BitmapCalculator added only the commit, no other objects.
+		assertTrue(bitmap.contains(head.getId()));
+		assertFalse(bitmap.contains(head.getTree().getId()));
+		assertFalse(bitmap.contains(acBlob.getId()));
+	}
+
+	@Test
+	public void walkUntilBitmap() throws Exception {
+		RevCommit root = repo.commit().create();
+		repo.update("refs/heads/master", root);
+
+		// GC creates bitmap index with ALL objects
+		GC gc = new GC(repo.getRepository());
+		gc.setAuto(false);
+		gc.gc();
+
+		// These objects are not in the bitmap index.
+		RevCommit commit1 = repo.commit(root);
+		RevCommit commit2 = repo.commit(commit1);
+		repo.update("refs/heads/master", commit2);
+
+		CounterProgressMonitor monitor = new CounterProgressMonitor();
+		BitmapCalculator bitmapWalker = new BitmapCalculator(repo.getRevWalk());
+		BitmapBuilder bitmap = bitmapWalker.getBitmap(commit2, monitor);
+
+		assertTrue(bitmap.contains(root));
+		assertTrue(bitmap.contains(commit1));
+		assertTrue(bitmap.contains(commit2));
+		assertEquals(2, monitor.getUpdates());
+	}
+
+	@Test
+	public void noNeedToWalk() throws Exception {
+		RevCommit root = repo.commit().create();
+		RevCommit commit1 = repo.commit(root);
+		RevCommit commit2 = repo.commit(commit1);
+		repo.update("refs/heads/master", commit2);
+
+		// GC creates bitmap index with ALL objects
+		GC gc = new GC(repo.getRepository());
+		gc.setAuto(false);
+		gc.gc();
+
+		CounterProgressMonitor monitor = new CounterProgressMonitor();
+		BitmapCalculator bitmapWalker = new BitmapCalculator(repo.getRevWalk());
+		BitmapBuilder bitmap = bitmapWalker.getBitmap(commit2, monitor);
+
+		assertTrue(bitmap.contains(root));
+		assertTrue(bitmap.contains(commit1));
+		assertTrue(bitmap.contains(commit2));
+		assertEquals(0, monitor.getUpdates());
+	}
+
+	private static class CounterProgressMonitor implements ProgressMonitor {
+
+		private int counter;
+
+		@Override
+		public void start(int totalTasks) {
+			// Nothing to do in tests
+		}
+
+		@Override
+		public void beginTask(String title, int totalWork) {
+			// Nothing to to in tests
+		}
+
+		@Override
+		public void update(int completed) {
+			counter += 1;
+		}
+
+		@Override
+		public void endTask() {
+			// Nothing to do in tests
+		}
+
+		@Override
+		public boolean isCancelled() {
+			return false;
+		}
+
+		int getUpdates() {
+			return counter;
+		}
+	}
+}
\ No newline at end of file
diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/BitmappedReachabilityCheckerTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/BitmappedReachabilityCheckerTest.java
new file mode 100644
index 0000000000..5d3adf5eab
--- /dev/null
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/BitmappedReachabilityCheckerTest.java
@@ -0,0 +1,69 @@
+/*
+ * 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.assertNotNull;
+
+import org.eclipse.jgit.internal.storage.file.FileRepository;
+import org.eclipse.jgit.internal.storage.file.GC;
+import org.eclipse.jgit.junit.TestRepository;
+
+public class BitmappedReachabilityCheckerTest
+		extends ReachabilityCheckerTestCase {
+
+	@Override
+	protected ReachabilityChecker getChecker(
+			TestRepository<FileRepository> repository) throws Exception {
+		// GC generates the bitmaps
+		GC gc = new GC(repo.getRepository());
+		gc.setAuto(false);
+		gc.gc();
+
+		// This is null when the test didn't create any branch
+		assertNotNull("Probably the test didn't define any ref",
+				repo.getRevWalk().getObjectReader().getBitmapIndex());
+
+		return new BitmappedReachabilityChecker(repository.getRevWalk());
+	}
+
+}
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/BitmapCalculator.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/BitmapCalculator.java
new file mode 100644
index 0000000000..e1d5d4adad
--- /dev/null
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/BitmapCalculator.java
@@ -0,0 +1,93 @@
+package org.eclipse.jgit.revwalk;
+
+import static java.util.Objects.requireNonNull;
+
+import java.io.IOException;
+
+import org.eclipse.jgit.errors.IncorrectObjectTypeException;
+import org.eclipse.jgit.errors.MissingObjectException;
+import org.eclipse.jgit.internal.revwalk.AddToBitmapFilter;
+import org.eclipse.jgit.lib.BitmapIndex;
+import org.eclipse.jgit.lib.BitmapIndex.Bitmap;
+import org.eclipse.jgit.lib.BitmapIndex.BitmapBuilder;
+import org.eclipse.jgit.lib.ProgressMonitor;
+
+/**
+ * Calculate the bitmap indicating what other commits are reachable from certain
+ * commit.
+ * <p>
+ * This bitmap refers only to commits. For a bitmap with ALL objects reachable
+ * from certain object, see {@code BitmapWalker}.
+ */
+class BitmapCalculator {
+
+	private final RevWalk walk;
+	private final BitmapIndex bitmapIndex;
+
+	BitmapCalculator(RevWalk walk) throws IOException {
+		this.walk = walk;
+		this.bitmapIndex = requireNonNull(
+				walk.getObjectReader().getBitmapIndex());
+	}
+
+	/**
+	 * Get the reachability bitmap from certain commit to other commits.
+	 * <p>
+	 * This will return a precalculated bitmap if available or walk building one
+	 * until finding a precalculated bitmap (and returning the union).
+	 * <p>
+	 * Beware that the returned bitmap it is guaranteed to include ONLY the
+	 * commits reachable from the initial commit. It COULD include other objects
+	 * (because precalculated bitmaps have them) but caller shouldn't count on
+	 * that. See {@link BitmapWalker} for a full reachability bitmap.
+	 *
+	 * @param start
+	 *            the commit. Use {@code walk.parseCommit(objectId)} to get this
+	 *            object from the id.
+	 * @param pm
+	 *            progress monitor. Updated by one per commit browsed in the
+	 *            graph
+	 * @return the bitmap of reachable commits (and maybe some extra objects)
+	 *         for the commit
+	 * @throws MissingObjectException
+	 *             the supplied id doesn't exist
+	 * @throws IncorrectObjectTypeException
+	 *             the supplied id doens't refer to a commit or a tag
+	 * @throws IOException
+	 */
+	BitmapBuilder getBitmap(RevCommit start, ProgressMonitor pm)
+			throws MissingObjectException,
+			IncorrectObjectTypeException, IOException {
+		Bitmap precalculatedBitmap = bitmapIndex.getBitmap(start);
+		if (precalculatedBitmap != null) {
+			return asBitmapBuilder(precalculatedBitmap);
+		}
+
+		walk.reset();
+		walk.sort(RevSort.TOPO);
+		walk.markStart(start);
+		// Unbounded walk. If the repo has bitmaps, it should bump into one at
+		// some point.
+
+		BitmapBuilder bitmapResult = bitmapIndex.newBitmapBuilder();
+		walk.setRevFilter(new AddToBitmapFilter(bitmapResult));
+		while (walk.next() != null) {
+			// Iterate through all of the commits. The BitmapRevFilter does
+			// the work.
+			//
+			// filter.include returns true for commits that do not have
+			// a bitmap in bitmapIndex and are not reachable from a
+			// bitmap in bitmapIndex encountered earlier in the walk.
+			// Thus the number of commits returned by next() measures how
+			// much history was traversed without being able to make use
+			// of bitmaps.
+			pm.update(1);
+		}
+
+		return bitmapResult;
+	}
+
+	private BitmapBuilder asBitmapBuilder(Bitmap bitmap) {
+		return bitmapIndex.newBitmapBuilder().or(bitmap);
+	}
+}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/BitmappedReachabilityChecker.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/BitmappedReachabilityChecker.java
new file mode 100644
index 0000000000..e4d28458a8
--- /dev/null
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/BitmappedReachabilityChecker.java
@@ -0,0 +1,122 @@
+/*
+ * 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.ArrayList;
+import java.util.Collection;
+import java.util.List;
+import java.util.Optional;
+
+import org.eclipse.jgit.errors.IncorrectObjectTypeException;
+import org.eclipse.jgit.errors.MissingObjectException;
+import org.eclipse.jgit.lib.BitmapIndex.BitmapBuilder;
+import org.eclipse.jgit.lib.NullProgressMonitor;
+
+/**
+ * Checks the reachability using bitmaps.
+ *
+ * @since 5.5
+ */
+public class BitmappedReachabilityChecker implements ReachabilityChecker {
+
+	private final RevWalk walk;
+
+	/**
+	 * @param walk
+	 *            walk on the repository to get or create the bitmaps for the
+	 *            commits. It must have bitmaps.
+	 * @throws AssertionError
+	 *             runtime exception if walk is over a repository without
+	 *             bitmaps
+	 * @throws IOException
+	 *             if the index or the object reader cannot be opened.
+	 */
+	public BitmappedReachabilityChecker(RevWalk walk)
+			throws IOException {
+		this.walk = walk;
+		if (walk.getObjectReader().getBitmapIndex() == null) {
+			throw new AssertionError(
+					"Trying to use bitmapped reachability check " //$NON-NLS-1$
+							+ "on a repository without bitmaps"); //$NON-NLS-1$
+		}
+	}
+
+	/**
+	 * Check all targets are reachable from the starters.
+	 * <p>
+	 * In this implementation, it is recommended to put the most popular
+	 * starters (e.g. refs/heads tips) at the beginning of the collection
+	 */
+	@Override
+	public Optional<RevCommit> areAllReachable(Collection<RevCommit> targets,
+			Collection<RevCommit> starters) throws MissingObjectException,
+			IncorrectObjectTypeException, IOException {
+		BitmapCalculator calculator = new BitmapCalculator(walk);
+
+		/**
+		 * Iterate over starters bitmaps and remove targets as they become
+		 * reachable.
+		 *
+		 * Building the total starters bitmap has the same cost (iterating over
+		 * all starters adding the bitmaps) and this gives us the chance to
+		 * shorcut the loop.
+		 *
+		 * This is based on the assuption that most of the starters will have
+		 * the reachability bitmap precalculated. If many require a walk, the
+		 * walk.reset() could start to take too much time.
+		 */
+		List<RevCommit> remainingTargets = new ArrayList<>(targets);
+		for (RevCommit starter : starters) {
+			BitmapBuilder starterBitmap = calculator.getBitmap(starter,
+					NullProgressMonitor.INSTANCE);
+			remainingTargets.removeIf(starterBitmap::contains);
+			if (remainingTargets.isEmpty()) {
+				return Optional.empty();
+			}
+		}
+
+		return Optional.of(remainingTargets.get(0));
+	}
+
+}
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;
+}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/transport/UploadPack.java b/org.eclipse.jgit/src/org/eclipse/jgit/transport/UploadPack.java
index 27090f4383..dff0f9c29a 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/transport/UploadPack.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/transport/UploadPack.java
@@ -44,12 +44,11 @@
 package org.eclipse.jgit.transport;
 
 import static java.util.Collections.unmodifiableMap;
-import static org.eclipse.jgit.util.RefMap.toRefMap;
 import static org.eclipse.jgit.lib.Constants.R_TAGS;
 import static org.eclipse.jgit.transport.GitProtocolConstants.CAPABILITY_REF_IN_WANT;
+import static org.eclipse.jgit.transport.GitProtocolConstants.CAPABILITY_SERVER_OPTION;
 import static org.eclipse.jgit.transport.GitProtocolConstants.COMMAND_FETCH;
 import static org.eclipse.jgit.transport.GitProtocolConstants.COMMAND_LS_REFS;
-import static org.eclipse.jgit.transport.GitProtocolConstants.CAPABILITY_SERVER_OPTION;
 import static org.eclipse.jgit.transport.GitProtocolConstants.OPTION_AGENT;
 import static org.eclipse.jgit.transport.GitProtocolConstants.OPTION_ALLOW_REACHABLE_SHA1_IN_WANT;
 import static org.eclipse.jgit.transport.GitProtocolConstants.OPTION_ALLOW_TIP_SHA1_IN_WANT;
@@ -65,6 +64,7 @@ import static org.eclipse.jgit.transport.GitProtocolConstants.OPTION_SHALLOW;
 import static org.eclipse.jgit.transport.GitProtocolConstants.OPTION_SIDE_BAND;
 import static org.eclipse.jgit.transport.GitProtocolConstants.OPTION_SIDE_BAND_64K;
 import static org.eclipse.jgit.transport.GitProtocolConstants.OPTION_THIN_PACK;
+import static org.eclipse.jgit.util.RefMap.toRefMap;
 
 import java.io.ByteArrayOutputStream;
 import java.io.EOFException;
@@ -80,8 +80,10 @@ import java.util.HashSet;
 import java.util.List;
 import java.util.Map;
 import java.util.Objects;
+import java.util.Optional;
 import java.util.Set;
 import java.util.TreeMap;
+import java.util.stream.Collectors;
 
 import org.eclipse.jgit.annotations.NonNull;
 import org.eclipse.jgit.annotations.Nullable;
@@ -104,8 +106,11 @@ import org.eclipse.jgit.lib.RefDatabase;
 import org.eclipse.jgit.lib.Repository;
 import org.eclipse.jgit.revwalk.AsyncRevObjectQueue;
 import org.eclipse.jgit.revwalk.BitmapWalker;
+import org.eclipse.jgit.revwalk.BitmappedReachabilityChecker;
 import org.eclipse.jgit.revwalk.DepthWalk;
 import org.eclipse.jgit.revwalk.ObjectWalk;
+import org.eclipse.jgit.revwalk.PedestrianReachabilityChecker;
+import org.eclipse.jgit.revwalk.ReachabilityChecker;
 import org.eclipse.jgit.revwalk.RevCommit;
 import org.eclipse.jgit.revwalk.RevFlag;
 import org.eclipse.jgit.revwalk.RevFlagSet;
@@ -1867,59 +1872,88 @@ public class UploadPack {
 
 	private static void checkNotAdvertisedWants(UploadPack up,
 			List<ObjectId> notAdvertisedWants, Set<ObjectId> reachableFrom)
-			throws MissingObjectException, IncorrectObjectTypeException, IOException {
-		// Walk the requested commits back to the provided set of commits. If any
-		// commit exists, a branch was deleted or rewound and the repository owner
-		// no longer exports that requested item. If the requested commit is merged
-		// into an advertised branch it will be marked UNINTERESTING and no commits
-		// return.
+			throws IOException {
 
 		ObjectReader reader = up.getRevWalk().getObjectReader();
 		try (RevWalk walk = new RevWalk(reader)) {
-			walk.setRetainBody(false);
-			AsyncRevObjectQueue q = walk.parseAny(notAdvertisedWants, true);
-			try {
-				RevObject obj;
-				while ((obj = q.next()) != null) {
-					if (!(obj instanceof RevCommit)) {
-						// If unadvertized non-commits are requested, use
-						// bitmaps. If there are no bitmaps, instead of
-						// incurring the expense of a manual walk, reject
-						// the request.
-						BitmapIndex bitmapIndex = reader.getBitmapIndex();
-						if (bitmapIndex != null) {
-							checkNotAdvertisedWantsUsingBitmap(
-									reader,
-									bitmapIndex,
-									notAdvertisedWants,
-									reachableFrom);
-							return;
-						}
-						throw new WantNotValidException(obj);
-					}
-					walk.markStart((RevCommit) obj);
+			// Missing "wants" throw exception here
+			List<RevObject> wantsAsObjs = objectIdsToRevObjects(walk,
+					notAdvertisedWants);
+			List<RevCommit> wantsAsCommits = wantsAsObjs.stream()
+					.filter(obj -> obj instanceof RevCommit)
+					.map(obj -> (RevCommit) obj)
+					.collect(Collectors.toList());
+			boolean allWantsAreCommits = wantsAsObjs.size() == wantsAsCommits
+					.size();
+			boolean repoHasBitmaps = reader.getBitmapIndex() != null;
+
+			if (!allWantsAreCommits) {
+				if (!repoHasBitmaps) {
+					// If unadvertized non-commits are requested, use
+					// bitmaps. If there are no bitmaps, instead of
+					// incurring the expense of a manual walk, reject
+					// the request.
+					RevObject nonCommit = wantsAsObjs
+							.stream()
+							.filter(obj -> !(obj instanceof RevCommit))
+							.limit(1)
+							.collect(Collectors.toList()).get(0);
+					throw new WantNotValidException(nonCommit);
+
 				}
-			} catch (MissingObjectException notFound) {
-				throw new WantNotValidException(notFound.getObjectId(),
-						notFound);
-			} finally {
-				q.release();
+				checkNotAdvertisedWantsUsingBitmap(reader,
+						reader.getBitmapIndex(), notAdvertisedWants,
+						reachableFrom);
+				return;
 			}
-			for (ObjectId id : reachableFrom) {
-				try {
-					walk.markUninteresting(walk.parseCommit(id));
-				} catch (IncorrectObjectTypeException notCommit) {
-					continue;
-				}
+
+			// All wants are commits, we can use ReachabilityChecker
+			ReachabilityChecker reachabilityChecker = repoHasBitmaps
+					? new BitmappedReachabilityChecker(walk)
+					: new PedestrianReachabilityChecker(true, walk);
+
+			List<RevCommit> starters = objectIdsToRevCommits(walk,
+					reachableFrom);
+			Optional<RevCommit> unreachable = reachabilityChecker
+					.areAllReachable(wantsAsCommits, starters);
+			if (unreachable.isPresent()) {
+				throw new WantNotValidException(unreachable.get());
 			}
 
-			RevCommit bad = walk.next();
-			if (bad != null) {
-				throw new WantNotValidException(bad);
+		} catch (MissingObjectException notFound) {
+			throw new WantNotValidException(notFound.getObjectId(), notFound);
+		}
+	}
+
+	// Resolve the ObjectIds into RevObjects. Any missing object raises an
+	// exception
+	private static List<RevObject> objectIdsToRevObjects(RevWalk walk,
+			Iterable<ObjectId> objectIds)
+			throws MissingObjectException, IOException {
+		List<RevObject> result = new ArrayList<>();
+		for (ObjectId objectId : objectIds) {
+			result.add(walk.parseAny(objectId));
+		}
+		return result;
+	}
+
+	// Get commits from object ids. If the id is not a commit, ignore it. If the
+	// id doesn't exist, report the missing object in a exception.
+	private static List<RevCommit> objectIdsToRevCommits(RevWalk walk,
+			Iterable<ObjectId> objectIds)
+			throws MissingObjectException, IOException {
+		List<RevCommit> result = new ArrayList<>();
+		for (ObjectId objectId : objectIds) {
+			try {
+				result.add(walk.parseCommit(objectId));
+			} catch (IncorrectObjectTypeException e) {
+				continue;
 			}
 		}
+		return result;
 	}
 
+
 	private void addCommonBase(RevObject o) {
 		if (!o.has(COMMON)) {
 			o.add(COMMON);