BitmappedReachabilityChecker: Use only one bitmap for the whole check

The checker is creating a new bitmap per branch leading to excessive
memory consumption. For the reachability check one bitmap with the
reachability of all branches aggregated is enough.

Build the reachability bitmap with a filter. The filter itself uses it
to emit only commits not reached before and the caller to check what
targets have been reached already.

BitmapCalculator is not required anymore.

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

3 files changed, 95 insertions, 339 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
deleted file mode 100644
index c5d4d4238d..0000000000
--- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/revwalk/BitmapCalculatorTest.java
+++ /dev/null
@@ -1,181 +0,0 @@
-/*
- * 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.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/src/org/eclipse/jgit/revwalk/BitmapCalculator.java b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/BitmapCalculator.java
deleted file mode 100644
index 14e95670aa..0000000000
--- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/BitmapCalculator.java
+++ /dev/null
@@ -1,136 +0,0 @@
-/*
- * 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 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 doesn't refer to a commit or a tag
-	 * @throws IOException
-	 *             if the walk cannot open a packfile or loose object
-	 */
-	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
index 2a8b295d97..bf831e3313 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/BitmappedReachabilityChecker.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/revwalk/BitmappedReachabilityChecker.java
@@ -52,8 +52,11 @@ import java.util.stream.Stream;
 
 import org.eclipse.jgit.errors.IncorrectObjectTypeException;
 import org.eclipse.jgit.errors.MissingObjectException;
+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.NullProgressMonitor;
+import org.eclipse.jgit.lib.Constants;
+import org.eclipse.jgit.revwalk.filter.RevFilter;
 
 /**
  * Checks the reachability using bitmaps.
@@ -86,38 +89,108 @@ class BitmappedReachabilityChecker implements ReachabilityChecker {
 	 * 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
+	 * starters (e.g. refs/heads tips) at the beginning.
 	 */
 	@Override
 	public Optional<RevCommit> areAllReachable(Collection<RevCommit> targets,
 			Stream<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);
-		Iterator<RevCommit> it = starters.iterator();
-		while (it.hasNext()) {
-			BitmapBuilder starterBitmap = calculator.getBitmap(it.next(),
-					NullProgressMonitor.INSTANCE);
-			remainingTargets.removeIf(starterBitmap::contains);
-			if (remainingTargets.isEmpty()) {
-				return Optional.empty();
+
+		walk.reset();
+		walk.sort(RevSort.TOPO);
+
+		// Filter emits only commits that are unreachable from previously
+		// visited commits. Internally it keeps a bitmap of everything
+		// reachable so far, which we use to discard reachable targets.
+		BitmapIndex repoBitmaps = walk.getObjectReader().getBitmapIndex();
+		ReachedFilter reachedFilter = new ReachedFilter(repoBitmaps);
+		walk.setRevFilter(reachedFilter);
+
+		Iterator<RevCommit> startersIter = starters.iterator();
+		while (startersIter.hasNext()) {
+			walk.markStart(startersIter.next());
+			while (walk.next() != null) {
+				remainingTargets.removeIf(reachedFilter::isReachable);
+
+				if (remainingTargets.isEmpty()) {
+					return Optional.empty();
+				}
 			}
+			walk.reset();
 		}
 
 		return Optional.of(remainingTargets.get(0));
 	}
 
+	/**
+	 * This filter emits commits that were not bitmap-reachable from anything
+	 * visited before. Or in other words, commits that add something (themselves
+	 * or their bitmap) to the "reached" bitmap.
+	 *
+	 * Current progress can be queried via {@link #isReachable(RevCommit)}.
+	 */
+	private static class ReachedFilter extends RevFilter {
+
+		private final BitmapIndex repoBitmaps;
+		private final BitmapBuilder reached;
+
+		/**
+		 * Create a filter that emits only previously unreachable commits.
+		 *
+		 * @param repoBitmaps
+		 *            bitmap index of the repo
+		 */
+		public ReachedFilter(BitmapIndex repoBitmaps) {
+			this.repoBitmaps = repoBitmaps;
+			this.reached = repoBitmaps.newBitmapBuilder();
+		}
+
+		/** {@inheritDoc} */
+		@Override
+		public final boolean include(RevWalk walker, RevCommit cmit) {
+			Bitmap commitBitmap;
+
+			if (reached.contains(cmit)) {
+				// already seen or included
+				dontFollow(cmit);
+				return false;
+			}
+
+			if ((commitBitmap = repoBitmaps.getBitmap(cmit)) != null) {
+				reached.or(commitBitmap);
+				// Emit the commit because there are new contents in the bitmap
+				// but don't follow parents (they are already in the bitmap)
+				dontFollow(cmit);
+				return true;
+			}
+
+			// No bitmaps, keep going
+			reached.addObject(cmit, Constants.OBJ_COMMIT);
+			return true;
+		}
+
+		private static final void dontFollow(RevCommit cmit) {
+			for (RevCommit p : cmit.getParents()) {
+				p.add(RevFlag.SEEN);
+			}
+		}
+
+		/** {@inheritDoc} */
+		@Override
+		public final RevFilter clone() {
+			throw new UnsupportedOperationException();
+		}
+
+		/** {@inheritDoc} */
+		@Override
+		public final boolean requiresCommitBody() {
+			return false;
+		}
+
+		boolean isReachable(RevCommit commit) {
+			return reached.contains(commit);
+		}
+	}
 }