1 files changed, 87 insertions, 0 deletions
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/internal/revwalk/PedestrianObjectReachabilityChecker.java b/org.eclipse.jgit/src/org/eclipse/jgit/internal/revwalk/PedestrianObjectReachabilityChecker.java
new file mode 100644
index 0000000000..1d1f5fddaf
--- /dev/null
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/internal/revwalk/PedestrianObjectReachabilityChecker.java
@@ -0,0 +1,87 @@
+/*
+ * Copyright (C) 2020, Google LLC and others
+ *
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Distribution License v. 1.0 which is available at
+ * https://www.eclipse.org/org/documents/edl-v10.php.
+ *
+ * SPDX-License-Identifier: BSD-3-Clause
+ */
+package org.eclipse.jgit.internal.revwalk;
+
+import java.io.IOException;
+import java.io.InvalidObjectException;
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.Optional;
+import java.util.stream.Stream;
+
+import org.eclipse.jgit.errors.MissingObjectException;
+import org.eclipse.jgit.revwalk.ObjectReachabilityChecker;
+import org.eclipse.jgit.revwalk.ObjectWalk;
+import org.eclipse.jgit.revwalk.RevCommit;
+import org.eclipse.jgit.revwalk.RevObject;
+import org.eclipse.jgit.revwalk.RevSort;
+
+/**
+ * Checks if all objects are reachable from certain starting points doing a
+ * walk.
+ */
+public class PedestrianObjectReachabilityChecker
+		implements ObjectReachabilityChecker {
+	private final ObjectWalk walk;
+
+	/**
+	 * New instance of the reachability checker using a existing walk.
+	 *
+	 * @param walk
+	 *            ObjectWalk instance to reuse. Caller retains ownership.
+	 */
+	public PedestrianObjectReachabilityChecker(ObjectWalk walk) {
+		this.walk = walk;
+	}
+
+	/**
+	 * {@inheritDoc}
+	 */
+	@Override
+	public Optional<RevObject> areAllReachable(Collection<RevObject> targets,
+			Stream<RevObject> starters) throws IOException {
+		try {
+			walk.reset();
+			walk.sort(RevSort.TOPO);
+			for (RevObject target : targets) {
+				walk.markStart(target);
+			}
+
+			Iterator<RevObject> iterator = starters.iterator();
+			while (iterator.hasNext()) {
+				RevObject o = iterator.next();
+				walk.markUninteresting(o);
+
+				RevObject peeled = walk.peel(o);
+				if (peeled instanceof RevCommit) {
+					// By default, for performance reasons, ObjectWalk does not
+					// mark
+					// a tree as uninteresting when we mark a commit. Mark it
+					// ourselves so that we can determine reachability exactly.
+					walk.markUninteresting(((RevCommit) peeled).getTree());
+				}
+			}
+
+			RevCommit commit = walk.next();
+			if (commit != null) {
+				return Optional.of(commit);
+			}
+
+			RevObject object = walk.nextObject();
+			if (object != null) {
+				return Optional.of(object);
+			}
+
+			return Optional.empty();
+		} catch (MissingObjectException | InvalidObjectException e) {
+			throw new IllegalStateException(e);
+		}
+	}
+}