diff --git a/java/com/google/gitiles/VisibilityChecker.java b/java/com/google/gitiles/VisibilityChecker.java
index ccd5cf1..da45248 100644
--- a/java/com/google/gitiles/VisibilityChecker.java
+++ b/java/com/google/gitiles/VisibilityChecker.java
@@ -42,6 +42,7 @@
  */
 package com.google.gitiles;
 
+import com.google.common.collect.ImmutableList;
 import java.io.IOException;
 import java.util.Collection;
 import org.eclipse.jgit.errors.IncorrectObjectTypeException;
@@ -49,7 +50,6 @@
 import org.eclipse.jgit.lib.ObjectId;
 import org.eclipse.jgit.lib.RefDatabase;
 import org.eclipse.jgit.revwalk.RevCommit;
-import org.eclipse.jgit.revwalk.RevSort;
 import org.eclipse.jgit.revwalk.RevWalk;
 
 /**
@@ -59,6 +59,8 @@
  */
 public class VisibilityChecker {
 
+  // TODO(ifrade): Right now we are using always topoSort, but we should respect this parameter
+  // or delete it.
   private final boolean topoSort;
 
   /**
@@ -90,7 +92,7 @@
    * @param walk The walk to use for the reachability check
    * @param commit The starting commit. It *MUST* come from the walk in use
    * @param starters visible commits. Anything reachable from these commits is visible. Missing ids
-   *     or ids pointing to wrong kind of objects are ignored.
+   *     or ids referring to other kinds of objects are ignored.
    * @return true if we can get to {@code commit} from the {@code starters}
    * @throws IOException a pack file or loose object could not be read
    */
@@ -101,28 +103,29 @@
       return false;
     }
 
-    walk.reset();
-    if (topoSort) {
-      walk.sort(RevSort.TOPO);
+    ImmutableList<RevCommit> startCommits = objectIdsToCommits(walk, starters);
+    if (startCommits.isEmpty()) {
+      return false;
     }
 
-    walk.markStart(commit);
-    for (ObjectId id : starters) {
-      markUninteresting(walk, id);
-    }
-    // If the commit is reachable from any given tip, it will appear to be
-    // uninteresting to the RevWalk and no output will be produced.
-    return walk.next() == null;
+    return !walk.createReachabilityChecker()
+        .areAllReachable(ImmutableList.of(commit), startCommits)
+        .isPresent();
   }
 
-  private static void markUninteresting(RevWalk walk, ObjectId id) throws IOException {
-    if (id == null) {
-      return;
+  private static ImmutableList<RevCommit> objectIdsToCommits(RevWalk walk, Collection<ObjectId> ids)
+      throws IOException {
+    ImmutableList.Builder<RevCommit> commits = ImmutableList.builder();
+    for (ObjectId id : ids) {
+      try {
+        commits.add(walk.parseCommit(id));
+      } catch (MissingObjectException e) {
+        // TODO(ifrade): ResolveParser has already checked that the object exists in the repo.
+        // Report as AssertionError.
+      } catch (IncorrectObjectTypeException e) {
+        // Ignore, doesn't affect commit reachability
+      }
     }
-    try {
-      walk.markUninteresting(walk.parseCommit(id));
-    } catch (IncorrectObjectTypeException | MissingObjectException e) {
-      // Do nothing, doesn't affect reachability.
-    }
+    return commits.build();
   }
 }