Remove WalkableGraph#exists and allow WalkableGraph#getValue and WalkableGraph#getException to be given non-existent keys without crashing. Add WalkableGraph#isCycle to fill the gap in testing for the difference between non-existence and depending on a cycle.

--
PiperOrigin-RevId: 143205289
MOS_MIGRATED_REVID=143205289

src/main/java/com/google/devtools/build/lib/query2/SkyQueryEnvironment.java

diff --git a/src/main/java/com/google/devtools/build/lib/query2/SkyQueryEnvironment.java b/src/main/java/com/google/devtools/build/lib/query2/SkyQueryEnvironment.java
index ae7aa9d..551b098 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/SkyQueryEnvironment.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/SkyQueryEnvironment.java
@@ -43,6 +43,7 @@
 import com.google.devtools.build.lib.graph.Digraph;
 import com.google.devtools.build.lib.packages.BuildFileContainsErrorsException;
 import com.google.devtools.build.lib.packages.DependencyFilter;
+import com.google.devtools.build.lib.packages.NoSuchPackageException;
 import com.google.devtools.build.lib.packages.NoSuchTargetException;
 import com.google.devtools.build.lib.packages.NoSuchThingException;
 import com.google.devtools.build.lib.packages.Package;
@@ -728,9 +729,6 @@
   public Target getTarget(Label label)
       throws TargetNotFoundException, QueryException, InterruptedException {
     SkyKey packageKey = PackageValue.key(label.getPackageIdentifier());
-    if (!graph.exists(packageKey)) {
-      throw new QueryException(packageKey + " does not exist in graph");
-    }
     try {
       PackageValue packageValue = (PackageValue) graph.getValue(packageKey);
       if (packageValue != null) {
@@ -740,8 +738,16 @@
         }
         return packageValue.getPackage().getTarget(label.getName());
       } else {
-        throw (NoSuchThingException) Preconditions.checkNotNull(
-            graph.getException(packageKey), label);
+        NoSuchThingException exception = (NoSuchThingException) graph.getException(packageKey);
+        if (exception != null) {
+          throw exception;
+        }
+        if (graph.isCycle(packageKey)) {
+          throw new NoSuchPackageException(
+              label.getPackageIdentifier(), "Package depends on a cycle");
+        } else {
+          throw new QueryException(packageKey + " does not exist in graph");
+        }
       }
     } catch (NoSuchThingException e) {
       throw new TargetNotFoundException(e);

src/main/java/com/google/devtools/build/lib/skyframe/FilesystemValueChecker.java

diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/FilesystemValueChecker.java b/src/main/java/com/google/devtools/build/lib/skyframe/FilesystemValueChecker.java
index 9a94f3f..6fef55c 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/FilesystemValueChecker.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/FilesystemValueChecker.java
@@ -135,7 +135,7 @@
     @Override
     @Nullable
     public SkyValue get(SkyKey key) throws InterruptedException {
-      return walkableGraph.exists(key) ? walkableGraph.getValue(key) : null;
+      return walkableGraph.getValue(key);
     }
   }
 

src/main/java/com/google/devtools/build/lib/skyframe/GraphBackedRecursivePackageProvider.java

diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/GraphBackedRecursivePackageProvider.java b/src/main/java/com/google/devtools/build/lib/skyframe/GraphBackedRecursivePackageProvider.java
index 5e31b91..337b14d 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/GraphBackedRecursivePackageProvider.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/GraphBackedRecursivePackageProvider.java
@@ -81,22 +81,21 @@
       throws NoSuchPackageException, InterruptedException {
     SkyKey pkgKey = PackageValue.key(packageName);
 
-    PackageValue pkgValue;
-    if (graph.exists(pkgKey)) {
-      pkgValue = (PackageValue) graph.getValue(pkgKey);
-      if (pkgValue == null) {
-        NoSuchPackageException nspe = (NoSuchPackageException) graph.getException(pkgKey);
-        if (nspe != null) {
-          throw nspe;
-        }
-        throw new NoSuchPackageException(packageName, "Package depends on a cycle");
-      }
+    PackageValue pkgValue = (PackageValue) graph.getValue(pkgKey);
+    if (pkgValue != null) {
+      return pkgValue.getPackage();
+    }
+    NoSuchPackageException nspe = (NoSuchPackageException) graph.getException(pkgKey);
+    if (nspe != null) {
+      throw nspe;
+    }
+    if (graph.isCycle(pkgKey)) {
+      throw new NoSuchPackageException(packageName, "Package depends on a cycle");
     } else {
       // If the package key does not exist in the graph, then it must not correspond to any package,
       // because the SkyQuery environment has already loaded the universe.
       throw new BuildFileNotFoundException(packageName, "BUILD file not found on package path");
     }
-    return pkgValue.getPackage();
   }
 
   @Override
@@ -139,22 +138,25 @@
   public boolean isPackage(EventHandler eventHandler, PackageIdentifier packageName)
       throws InterruptedException {
     SkyKey packageLookupKey = PackageLookupValue.key(packageName);
-    if (!graph.exists(packageLookupKey)) {
-      // If the package lookup key does not exist in the graph, then it must not correspond to any
-      // package, because the SkyQuery environment has already loaded the universe.
-      return false;
-    }
     PackageLookupValue packageLookupValue = (PackageLookupValue) graph.getValue(packageLookupKey);
     if (packageLookupValue == null) {
-      Exception exception = Preconditions.checkNotNull(graph.getException(packageLookupKey),
-          "During package lookup for '%s', got null for exception", packageName);
-      if (exception instanceof NoSuchPackageException
-          || exception instanceof InconsistentFilesystemException) {
-        eventHandler.handle(Event.error(exception.getMessage()));
+      // Package lookups can't depend on Skyframe cycles.
+      Preconditions.checkState(!graph.isCycle(packageLookupKey), packageLookupKey);
+      Exception exception = graph.getException(packageLookupKey);
+      if (exception == null) {
+        // If the package lookup key does not exist in the graph, then it must not correspond to any
+        // package, because the SkyQuery environment has already loaded the universe.
         return false;
       } else {
-        throw new IllegalStateException("During package lookup for '" + packageName
-            + "', got unexpected exception type", exception);
+        if (exception instanceof NoSuchPackageException
+            || exception instanceof InconsistentFilesystemException) {
+          eventHandler.handle(Event.error(exception.getMessage()));
+          return false;
+        } else {
+          throw new IllegalStateException(
+              "During package lookup for '" + packageName + "', got unexpected exception type",
+              exception);
+        }
       }
     }
     return packageLookupValue.packageExists();
@@ -190,7 +192,7 @@
       roots.addAll(pkgPath.getPathEntries());
     } else {
       RepositoryDirectoryValue repositoryValue =
-            (RepositoryDirectoryValue) graph.getValue(RepositoryDirectoryValue.key(repository));
+          (RepositoryDirectoryValue) graph.getValue(RepositoryDirectoryValue.key(repository));
       if (repositoryValue == null) {
         // If this key doesn't exist, the repository is outside the universe, so we return
         // "nothing".

src/main/java/com/google/devtools/build/skyframe/DelegatingWalkableGraph.java

diff --git a/src/main/java/com/google/devtools/build/skyframe/DelegatingWalkableGraph.java b/src/main/java/com/google/devtools/build/skyframe/DelegatingWalkableGraph.java
index 27475db..8abf5de 100644
--- a/src/main/java/com/google/devtools/build/skyframe/DelegatingWalkableGraph.java
+++ b/src/main/java/com/google/devtools/build/skyframe/DelegatingWalkableGraph.java
@@ -32,26 +32,18 @@
     this.graph = graph;
   }
 
+  @Nullable
   private NodeEntry getEntryForValue(SkyKey key) throws InterruptedException {
     NodeEntry entry =
-        Preconditions.checkNotNull(
-            graph.getBatch(null, Reason.WALKABLE_GRAPH_VALUE, ImmutableList.of(key)).get(key),
-            key);
-    Preconditions.checkState(entry.isDone(), "%s %s", key, entry);
-    return entry;
-  }
-
-  @Override
-  public boolean exists(SkyKey key) throws InterruptedException {
-    NodeEntry entry =
-        graph.getBatch(null, Reason.EXISTENCE_CHECKING, ImmutableList.of(key)).get(key);
-    return entry != null && entry.isDone();
+        graph.getBatch(null, Reason.WALKABLE_GRAPH_VALUE, ImmutableList.of(key)).get(key);
+    return entry != null && entry.isDone() ? entry : null;
   }
 
   @Nullable
   @Override
   public SkyValue getValue(SkyKey key) throws InterruptedException {
-    return getEntryForValue(key).getValue();
+    NodeEntry entry = getEntryForValue(key);
+    return entry == null ? null : entry.getValue();
   }
 
   private static SkyValue getValue(NodeEntry entry) throws InterruptedException {
@@ -93,10 +85,24 @@
     return result;
   }
 
+  @Override
+  public boolean isCycle(SkyKey key) throws InterruptedException {
+    NodeEntry entry = getEntryForValue(key);
+    if (entry == null) {
+      return false;
+    }
+    ErrorInfo errorInfo = entry.getErrorInfo();
+    return errorInfo != null && errorInfo.getCycleInfo() != null;
+  }
+
   @Nullable
   @Override
   public Exception getException(SkyKey key) throws InterruptedException {
-    ErrorInfo errorInfo = getEntryForValue(key).getErrorInfo();
+    NodeEntry entry = getEntryForValue(key);
+    if (entry == null) {
+      return null;
+    }
+    ErrorInfo errorInfo = entry.getErrorInfo();
     return errorInfo == null ? null : errorInfo.getException();
   }
 

src/main/java/com/google/devtools/build/skyframe/WalkableGraph.java

diff --git a/src/main/java/com/google/devtools/build/skyframe/WalkableGraph.java b/src/main/java/com/google/devtools/build/skyframe/WalkableGraph.java
index 3d7796b..8f3dd04 100644
--- a/src/main/java/com/google/devtools/build/skyframe/WalkableGraph.java
+++ b/src/main/java/com/google/devtools/build/skyframe/WalkableGraph.java
@@ -30,17 +30,17 @@
  */
 @ThreadSafe
 public interface WalkableGraph {
-
-  /**
-   * Returns whether the given key exists as a done node in the graph. If there is a chance that the
-   * given node does not exist, this method should be called before any others, since the others
-   * throw a {@link RuntimeException} on failure to access a node.
-   */
-  boolean exists(SkyKey key) throws InterruptedException;
-
   /**
    * Returns the value of the given key, or {@code null} if it has no value due to an error during
-   * its computation. A node with this key must exist in the graph.
+   * its computation or it is not done in the graph.
+   *
+   * <p>A node that is done in the graph must have either a non-null getValue, a non-null {@link
+   * #getException}, or a true {@link #isCycle}.
+   *
+   * <p>These three methods should all be reading the same {@link
+   * NodeEntry#getValueMaybeWithMetadata} value internally, so once that value is indirectly
+   * retrieved via one of these methods, the others can read it for free. This is relevant for graph
+   * implementations that may throw an {@link InterruptedException} on retrieving entries and value.
    */
   @Nullable
   SkyValue getValue(SkyKey key) throws InterruptedException;
@@ -63,21 +63,27 @@
 
   /**
    * Returns the exception thrown when computing the node with the given key, if any. If the node
-   * was computed successfully, returns null. A node with this key must exist and be done in the
-   * graph.
+   * was computed successfully, depends on a cycle without any other error, or is not done in the
+   * graph, returns null.
    */
   @Nullable
   Exception getException(SkyKey key) throws InterruptedException;
 
   /**
+   * Returns true if the node with the given {@code key} depends on a cycle. Returns false if the
+   * node does not depend on a cycle, or is not done in the graph.
+   */
+  boolean isCycle(SkyKey key) throws InterruptedException;
+
+  /**
    * Returns a map giving the direct dependencies of the nodes with the given keys. A node for each
-   * given key must exist and be done in the graph.
+   * given key must be done in the graph if it exists.
    */
   Map<SkyKey, Iterable<SkyKey>> getDirectDeps(Iterable<SkyKey> keys) throws InterruptedException;
 
   /**
    * Returns a map giving the reverse dependencies of the nodes with the given keys. A node for each
-   * given key must exist and be done in the graph.
+   * given key must be done in the graph if it exists.
    */
   Map<SkyKey, Iterable<SkyKey>> getReverseDeps(Iterable<SkyKey> keys) throws InterruptedException;
 

src/test/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternsFunctionSmartNegationTest.java

diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternsFunctionSmartNegationTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternsFunctionSmartNegationTest.java
index 278567a..dbbcf49 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternsFunctionSmartNegationTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternsFunctionSmartNegationTest.java
@@ -14,6 +14,7 @@
 package com.google.devtools.build.lib.skyframe;
 
 import static com.google.common.truth.Truth.assertThat;
+import static com.google.devtools.build.skyframe.WalkableGraphUtils.exists;
 import static org.junit.Assert.assertFalse;
 import static org.junit.Assert.assertTrue;
 
@@ -27,13 +28,11 @@
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
 import com.google.devtools.build.skyframe.WalkableGraph;
-
+import java.io.IOException;
 import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.junit.runners.JUnit4;
 
-import java.io.IOException;
-
 /** Tests for {@link PrepareDepsOfPatternsFunction}. */
 @RunWith(JUnit4.class)
 public class PrepareDepsOfPatternsFunctionSmartNegationTest extends BuildViewTestCase {
@@ -60,11 +59,11 @@
             patternSequence, /*successExpected=*/ true, /*keepGoing=*/ true);
 
     // Then the graph contains package values for "@//foo" and "@//foo/foo",
-    assertTrue(walkableGraph.exists(PackageValue.key(PackageIdentifier.parse("@//foo"))));
-    assertTrue(walkableGraph.exists(PackageValue.key(PackageIdentifier.parse("@//foo/foo"))));
+    assertTrue(exists(PackageValue.key(PackageIdentifier.parse("@//foo")), walkableGraph));
+    assertTrue(exists(PackageValue.key(PackageIdentifier.parse("@//foo/foo")), walkableGraph));
 
     // But the graph does not contain a value for the target "@//foo/foo:foofoo".
-    assertFalse(walkableGraph.exists(getKeyForLabel(Label.create("@//foo/foo", "foofoo"))));
+    assertFalse(exists(getKeyForLabel(Label.create("@//foo/foo", "foofoo")), walkableGraph));
   }
 
   @Test
@@ -104,14 +103,14 @@
             patternSequence, /*successExpected=*/ true, /*keepGoing=*/ true);
 
     // Then the graph contains a package value for "@//foo",
-    assertTrue(walkableGraph.exists(PackageValue.key(PackageIdentifier.parse("@//foo"))));
+    assertTrue(exists(PackageValue.key(PackageIdentifier.parse("@//foo")), walkableGraph));
 
     // But no package value for "@//foo/foo",
-    assertFalse(walkableGraph.exists(PackageValue.key(PackageIdentifier.parse("@//foo/foo"))));
+    assertFalse(exists(PackageValue.key(PackageIdentifier.parse("@//foo/foo")), walkableGraph));
 
     // And the graph does not contain a value for the target "@//foo/foo:foofoo".
     Label label = Label.create("@//foo/foo", "foofoo");
-    assertFalse(walkableGraph.exists(getKeyForLabel(label)));
+    assertFalse(exists(getKeyForLabel(label), walkableGraph));
   }
 
   @Test

src/test/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternsFunctionTest.java

diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternsFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternsFunctionTest.java
index b29ec04..cda7fbc 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternsFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfPatternsFunctionTest.java
@@ -15,6 +15,7 @@
 
 import static com.google.common.truth.Truth.assertThat;
 import static com.google.devtools.build.skyframe.EvaluationResultSubjectFactory.assertThatEvaluationResult;
+import static com.google.devtools.build.skyframe.WalkableGraphUtils.exists;
 import static org.junit.Assert.assertFalse;
 import static org.junit.Assert.assertNotNull;
 import static org.junit.Assert.assertNull;
@@ -61,7 +62,7 @@
     assertValidValue(walkableGraph, getKeyForLabel(Label.create("@//foo", "foo")));
 
     // And the graph does not contain a value for the target "@//foo:foo2".
-    assertFalse(walkableGraph.exists(getKeyForLabel(Label.create("@//foo", "foo2"))));
+    assertFalse(exists(getKeyForLabel(Label.create("@//foo", "foo2")), walkableGraph));
   }
 
   @Test
@@ -106,7 +107,7 @@
     WalkableGraph walkableGraph = getGraphFromPatternsEvaluation(patternSequence);
 
     // Then the graph does not contain an entry for ":foo",
-    assertFalse(walkableGraph.exists(getKeyForLabel(Label.create("@//foo", "foo"))));
+    assertFalse(exists(getKeyForLabel(Label.create("@//foo", "foo")), walkableGraph));
   }
 
   @Test
@@ -188,7 +189,7 @@
     assertContainsEvent("Skipping '" + bogusPattern + "': ");
 
     // And then the graph contains a value for the legit target pattern's target "@//foo:foo".
-    assertTrue(walkableGraph.exists(getKeyForLabel(Label.create("@//foo", "foo"))));
+    assertTrue(exists(getKeyForLabel(Label.create("@//foo", "foo")), walkableGraph));
   }
 
   // Helpers:
@@ -260,7 +261,6 @@
   private static void assertValidValue(
       WalkableGraph graph, SkyKey key, boolean expectTransitiveException)
       throws InterruptedException {
-    assertTrue(graph.exists(key));
     assertNotNull(graph.getValue(key));
     if (expectTransitiveException) {
       assertNotNull(graph.getException(key));
@@ -271,7 +271,6 @@
 
   private static Exception assertException(WalkableGraph graph, SkyKey key)
       throws InterruptedException {
-    assertTrue(graph.exists(key));
     assertNull(graph.getValue(key));
     Exception exception = graph.getException(key);
     assertNotNull(exception);

src/test/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfTargetsUnderDirectoryFunctionTest.java

diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfTargetsUnderDirectoryFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfTargetsUnderDirectoryFunctionTest.java
index 0a8aed0..169a3fc 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfTargetsUnderDirectoryFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/PrepareDepsOfTargetsUnderDirectoryFunctionTest.java
@@ -15,6 +15,7 @@
 package com.google.devtools.build.lib.skyframe;
 
 import static com.google.common.truth.Truth.assertThat;
+import static com.google.devtools.build.skyframe.WalkableGraphUtils.exists;
 import static org.junit.Assert.assertFalse;
 import static org.junit.Assert.assertTrue;
 
@@ -34,14 +35,12 @@
 import com.google.devtools.build.skyframe.EvaluationResult;
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.WalkableGraph;
-
+import java.io.IOException;
 import org.junit.Before;
 import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.junit.runners.JUnit4;
 
-import java.io.IOException;
-
 /**
  * Tests for {@link PrepareDepsOfTargetsUnderDirectoryFunction}. Insert excuses here.
  */
@@ -104,7 +103,7 @@
 
     // Then the TransitiveTraversalValue for "@//a:a" is evaluated,
     SkyKey aaKey = TransitiveTraversalValue.key(Label.create("@//a", "a"));
-    assertThat(graph.exists(aaKey)).isTrue();
+    assertThat(exists(aaKey, graph)).isTrue();
 
     // And that TransitiveTraversalValue depends on "@//b:b.txt".
     Iterable<SkyKey> depsOfAa =
@@ -113,7 +112,7 @@
     assertThat(depsOfAa).contains(bTxtKey);
 
     // And the TransitiveTraversalValue for "b:b.txt" is evaluated.
-    assertThat(graph.exists(bTxtKey)).isTrue();
+    assertThat(exists(bTxtKey, graph)).isTrue();
   }
 
   @Test
@@ -130,11 +129,11 @@
 
     // Then the TransitiveTraversalValue for "@//a:a" is not evaluated,
     SkyKey aaKey = TransitiveTraversalValue.key(Label.create("@//a", "a"));
-    assertThat(graph.exists(aaKey)).isFalse();
+    assertThat(exists(aaKey, graph)).isFalse();
 
     // But the TransitiveTraversalValue for "@//a:aTest" is.
     SkyKey aaTestKey = TransitiveTraversalValue.key(Label.create("@//a", "aTest"));
-    assertThat(graph.exists(aaTestKey)).isTrue();
+    assertThat(exists(aaTestKey, graph)).isTrue();
   }
 
   /**
@@ -188,13 +187,18 @@
 
     // Also, the computation graph does not contain a cached value for "a/b".
     WalkableGraph graph = Preconditions.checkNotNull(evaluationResult.getWalkableGraph());
-    assertFalse(graph.exists(createPrepDepsKey(rootDirectory, excludedPathFragment,
-        ImmutableSet.<PathFragment>of())));
+    assertFalse(
+        exists(
+            createPrepDepsKey(rootDirectory, excludedPathFragment, ImmutableSet.<PathFragment>of()),
+            graph));
 
     // And the computation graph does contain a cached value for "a/c" with the empty set excluded,
     // because that key was evaluated.
-    assertTrue(graph.exists(createPrepDepsKey(rootDirectory, new PathFragment("a/c"),
-        ImmutableSet.<PathFragment>of())));
+    assertTrue(
+        exists(
+            createPrepDepsKey(
+                rootDirectory, new PathFragment("a/c"), ImmutableSet.<PathFragment>of()),
+            graph));
   }
 
   @Test
@@ -233,7 +237,7 @@
     // "a/b/c" does live underneath "a/b".
     WalkableGraph graph = Preconditions.checkNotNull(evaluationResult.getWalkableGraph());
     SkyKey abKey = createCollectPackagesKey(rootDirectory, new PathFragment("a/b"), excludedPaths);
-    assertThat(graph.exists(abKey)).isTrue();
+    assertThat(exists(abKey, graph)).isTrue();
     CollectPackagesUnderDirectoryValue abValue =
         (CollectPackagesUnderDirectoryValue) Preconditions.checkNotNull(graph.getValue(abKey));
 

src/test/java/com/google/devtools/build/lib/skyframe/RecursivePkgFunctionTest.java

diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/RecursivePkgFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/RecursivePkgFunctionTest.java
index d6c6459..89f961a 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/RecursivePkgFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/RecursivePkgFunctionTest.java
@@ -14,6 +14,7 @@
 package com.google.devtools.build.lib.skyframe;
 
 import static com.google.common.truth.Truth.assertThat;
+import static com.google.devtools.build.skyframe.WalkableGraphUtils.exists;
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertFalse;
 import static org.junit.Assert.assertTrue;
@@ -31,7 +32,6 @@
 import com.google.devtools.build.skyframe.EvaluationResult;
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.WalkableGraph;
-
 import org.junit.Before;
 import org.junit.Test;
 import org.junit.runner.RunWith;
@@ -140,16 +140,18 @@
     // Also, the computation graph does not contain a cached value for "a/b".
     WalkableGraph graph = Preconditions.checkNotNull(evaluationResult.getWalkableGraph());
     assertFalse(
-        graph.exists(
+        exists(
             buildRecursivePkgKey(
-                rootDirectory, excludedPathFragment, ImmutableSet.<PathFragment>of())));
+                rootDirectory, excludedPathFragment, ImmutableSet.<PathFragment>of()),
+            graph));
 
     // And the computation graph does contain a cached value for "a/c" with the empty set excluded,
     // because that key was evaluated.
     assertTrue(
-        graph.exists(
+        exists(
             buildRecursivePkgKey(
-                rootDirectory, new PathFragment("a/c"), ImmutableSet.<PathFragment>of())));
+                rootDirectory, new PathFragment("a/c"), ImmutableSet.<PathFragment>of()),
+            graph));
   }
 
   @Test
@@ -176,6 +178,6 @@
     // "a/b/c" does live underneath "a/b".
     WalkableGraph graph = Preconditions.checkNotNull(evaluationResult.getWalkableGraph());
     assertTrue(
-        graph.exists(buildRecursivePkgKey(rootDirectory, new PathFragment("a/b"), excludedPaths)));
+        exists(buildRecursivePkgKey(rootDirectory, new PathFragment("a/b"), excludedPaths), graph));
   }
 }

src/test/java/com/google/devtools/build/lib/skyframe/SkyframeLabelVisitorTestCase.java

diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/SkyframeLabelVisitorTestCase.java b/src/test/java/com/google/devtools/build/lib/skyframe/SkyframeLabelVisitorTestCase.java
index 80650fd..1fd0b74 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/SkyframeLabelVisitorTestCase.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/SkyframeLabelVisitorTestCase.java
@@ -14,6 +14,7 @@
 package com.google.devtools.build.lib.skyframe;
 
 import static com.google.common.truth.Truth.assertThat;
+import static com.google.devtools.build.skyframe.WalkableGraphUtils.exists;
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertNotSame;
 
@@ -191,7 +192,7 @@
     while (!Iterables.isEmpty(nodesToVisit)) {
       List<SkyKey> existingNodes = new ArrayList<>();
       for (SkyKey key : nodesToVisit) {
-        if (graph.exists(key) && graph.getValue(key) != null && visitedNodes.add(key)) {
+        if (exists(key, graph) && graph.getValue(key) != null && visitedNodes.add(key)) {
           existingNodes.add(key);
         }
       }

src/test/java/com/google/devtools/build/skyframe/WalkableGraphUtils.java

diff --git a/src/test/java/com/google/devtools/build/skyframe/WalkableGraphUtils.java b/src/test/java/com/google/devtools/build/skyframe/WalkableGraphUtils.java
index 7095371..05d11bf 100644
--- a/src/test/java/com/google/devtools/build/skyframe/WalkableGraphUtils.java
+++ b/src/test/java/com/google/devtools/build/skyframe/WalkableGraphUtils.java
@@ -16,7 +16,7 @@
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.Iterables;
 
-/** Utility methods for querying (r)deps of nodes from {@link WalkableGraph}s more concisely. */
+/** Utility methods for querying {@link WalkableGraph}s more concisely. */
 public class WalkableGraphUtils {
 
   public static Iterable<SkyKey> getDirectDeps(WalkableGraph graph, SkyKey key)
@@ -28,4 +28,8 @@
       throws InterruptedException {
     return Iterables.getOnlyElement(graph.getReverseDeps(ImmutableList.of(key)).values());
   }
+
+  public static boolean exists(SkyKey key, WalkableGraph graph) throws InterruptedException {
+    return graph.getValue(key) != null || graph.getException(key) != null || graph.isCycle(key);
+  }
 }