Add a SkyQueryEnvironment which runs queries by examining the Skyframe graph.

This environment eagerly preloads the transitive closure of a specified query "universe", and so may not be as efficient as the standard query for limited-scope queries. It is activated when the universe is specified and ordered results are not requested (since it is currently unable to order results).

Tests were modified/added to exercise this environment where deemed interesting. Some ugly hacks were done to add coverage in AbstractQueryTest and friends, because currently even if the full depot is loaded (using //...), individual target patterns most likely won't be present in the graph. A better way to deal with this situation, suggested by felly, is probably to extract target pattern resolution logic to an auxiliary function so that query is able to resolve target patterns without mutating the graph, and then call into the read-only graph with the resolved patterns. That may be done in a follow-up, in which case the "scope" of every query could be //... .

--
MOS_MIGRATED_REVID=87257028

10 files changed, 479 insertions, 42 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/graph/Digraph.java b/src/main/java/com/google/devtools/build/lib/graph/Digraph.java
index bea2f5aa05..92e973a2e7 100644
--- a/src/main/java/com/google/devtools/build/lib/graph/Digraph.java
+++ b/src/main/java/com/google/devtools/build/lib/graph/Digraph.java
@@ -597,7 +597,7 @@ public final class Digraph<T> implements Cloneable {
    * starting node, returns the path from the root of the tree to 'node' as a
    * list.
    */
-  private static <X> List<X> getPathToTreeNode(Map<X, X> tree, X node) {
+  public static <X> List<X> getPathToTreeNode(Map<X, X> tree, X node) {
     List<X> path = new ArrayList<X>();
     while (node != null) {
       path.add(node);
diff --git a/src/main/java/com/google/devtools/build/lib/pkgcache/TargetPatternEvaluator.java b/src/main/java/com/google/devtools/build/lib/pkgcache/TargetPatternEvaluator.java
index 94e956b435..7732519404 100644
--- a/src/main/java/com/google/devtools/build/lib/pkgcache/TargetPatternEvaluator.java
+++ b/src/main/java/com/google/devtools/build/lib/pkgcache/TargetPatternEvaluator.java
@@ -43,6 +43,8 @@ import java.util.Map;
  */
 @ThreadSafety.ConditionallyThreadSafe // as long as you don't call updateOffset.
 public interface TargetPatternEvaluator {
+  static FilteringPolicy DEFAULT_FILTERING_POLICY = FilteringPolicies.NO_FILTER;
+
   /**
    * Attempts to parse an ordered list of target patterns, computing the union
    * of the set of targets represented by each pattern, unless it is preceded by
@@ -78,7 +80,6 @@ public interface TargetPatternEvaluator {
       Collection<String> patterns, boolean keepGoing)
           throws TargetParsingException, InterruptedException;
 
-
   /**
    * Update the parser's offset, given the workspace and working directory.
    *
diff --git a/src/main/java/com/google/devtools/build/lib/query2/AbstractBlazeQueryEnvironment.java b/src/main/java/com/google/devtools/build/lib/query2/AbstractBlazeQueryEnvironment.java
index de56c1b41d..96e850977a 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/AbstractBlazeQueryEnvironment.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/AbstractBlazeQueryEnvironment.java
@@ -34,6 +34,7 @@ import com.google.devtools.build.lib.query2.engine.QueryException;
 import com.google.devtools.build.lib.query2.engine.QueryExpression;
 import com.google.devtools.build.lib.syntax.Label;
 import com.google.devtools.build.lib.util.BinaryPredicate;
+import com.google.devtools.build.skyframe.WalkableGraph.WalkableGraphFactory;
 
 import java.util.Collection;
 import java.util.HashMap;
@@ -48,7 +49,6 @@ import java.util.Set;
  */
 public abstract class AbstractBlazeQueryEnvironment<T> implements QueryEnvironment<T> {
   protected final ErrorSensingEventHandler eventHandler;
-  private final TargetPatternEvaluator targetPatternEvaluator;
   private final Map<String, Set<T>> letBindings = new HashMap<>();
   protected final Map<String, ResolvedTargets<Target>> resolvedTargetPatterns = new HashMap<>();
   protected final boolean keepGoing;
@@ -60,15 +60,13 @@ public abstract class AbstractBlazeQueryEnvironment<T> implements QueryEnvironme
   private final Set<Setting> settings;
   private final List<QueryFunction> extraFunctions;
 
-  protected AbstractBlazeQueryEnvironment(TargetPatternEvaluator targetPatternEvaluator,
-      boolean keepGoing,
+  protected AbstractBlazeQueryEnvironment(boolean keepGoing,
       boolean strictScope,
       Predicate<Label> labelFilter,
       EventHandler eventHandler,
       Set<Setting> settings,
       Iterable<QueryFunction> extraFunctions) {
     this.eventHandler = new ErrorSensingEventHandler(eventHandler);
-    this.targetPatternEvaluator = targetPatternEvaluator;
     this.keepGoing = keepGoing;
     this.strictScope = strictScope;
     this.dependencyFilter = constructDependencyFilter(settings);
@@ -90,23 +88,31 @@ public abstract class AbstractBlazeQueryEnvironment<T> implements QueryEnvironme
   }
 
   public static AbstractBlazeQueryEnvironment<Target> newQueryEnvironment(
-      TransitivePackageLoader transitivePackageLoader, PackageProvider packageProvider,
+      TransitivePackageLoader transitivePackageLoader, WalkableGraphFactory graphFactory,
+      PackageProvider packageProvider,
       TargetPatternEvaluator targetPatternEvaluator, boolean keepGoing, boolean orderedResults,
-      int loadingPhaseThreads,
+      List<String> universeScope, int loadingPhaseThreads,
       EventHandler eventHandler, Set<Setting> settings, Iterable<QueryFunction> functions) {
-    return newQueryEnvironment(transitivePackageLoader, packageProvider,
+    return newQueryEnvironment(transitivePackageLoader, graphFactory, packageProvider,
         targetPatternEvaluator, keepGoing, /*strictScope=*/true, orderedResults,
-        loadingPhaseThreads, Rule.ALL_LABELS, eventHandler, settings, functions);
+        universeScope, loadingPhaseThreads, Rule.ALL_LABELS, eventHandler, settings, functions);
   }
 
   public static AbstractBlazeQueryEnvironment<Target> newQueryEnvironment(
-      TransitivePackageLoader transitivePackageLoader, PackageProvider packageProvider,
+      TransitivePackageLoader transitivePackageLoader, WalkableGraphFactory graphFactory,
+      PackageProvider packageProvider,
       TargetPatternEvaluator targetPatternEvaluator, boolean keepGoing, boolean strictScope,
-      boolean orderedResults, int loadingPhaseThreads, Predicate<Label> labelFilter,
+      boolean orderedResults, List<String> universeScope, int loadingPhaseThreads,
+      Predicate<Label> labelFilter,
       EventHandler eventHandler, Set<Setting> settings, Iterable<QueryFunction> functions) {
-    return new BlazeQueryEnvironment(transitivePackageLoader, packageProvider,
+    Preconditions.checkNotNull(universeScope);
+    return orderedResults || universeScope.isEmpty()
+        ? new BlazeQueryEnvironment(transitivePackageLoader, packageProvider,
         targetPatternEvaluator, keepGoing, strictScope, loadingPhaseThreads,
-        labelFilter, eventHandler, settings, functions);
+        labelFilter, eventHandler, settings, functions)
+        : new SkyQueryEnvironment(
+            keepGoing, strictScope, loadingPhaseThreads, labelFilter, eventHandler, settings,
+            functions, targetPatternEvaluator.getOffset(), graphFactory, universeScope);
   }
 
   /**
@@ -119,9 +125,6 @@ public abstract class AbstractBlazeQueryEnvironment<T> implements QueryEnvironme
    *   effect
    */
   public QueryEvalResult<T> evaluateQuery(QueryExpression expr) throws QueryException {
-    // Some errors are reported as QueryExceptions and others as ERROR events
-    // (if --keep_going).
-    eventHandler.resetErrors();
     resolvedTargetPatterns.clear();
 
     // In the --nokeep_going case, errors are reported in the order in which the patterns are
@@ -210,18 +213,8 @@ public abstract class AbstractBlazeQueryEnvironment<T> implements QueryEnvironme
     return getTargetsMatchingPattern(caller, pattern);
   }
 
-  private Map<String, ResolvedTargets<Target>> preloadOrThrow(Collection<String> patterns)
-      throws TargetParsingException {
-    try {
-      // Note that this may throw a RuntimeException if deps are missing in Skyframe and this is
-      // being called from within a SkyFunction.
-      return targetPatternEvaluator.preloadTargetPatterns(
-          eventHandler, patterns, keepGoing);
-    } catch (InterruptedException e) {
-      // TODO(bazel-team): Propagate the InterruptedException from here [skyframe-loading].
-      throw new TargetParsingException("interrupted");
-    }
-  }
+  protected abstract Map<String, ResolvedTargets<Target>> preloadOrThrow(
+      Collection<String> patterns) throws QueryException, TargetParsingException;
 
   @Override
   public boolean isSettingEnabled(Setting setting) {
@@ -235,5 +228,4 @@ public abstract class AbstractBlazeQueryEnvironment<T> implements QueryEnvironme
     builder.addAll(extraFunctions);
     return builder.build();
   }
-
 }
diff --git a/src/main/java/com/google/devtools/build/lib/query2/BlazeQueryEnvironment.java b/src/main/java/com/google/devtools/build/lib/query2/BlazeQueryEnvironment.java
index ede8ecec2e..8c1c2b11d8 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/BlazeQueryEnvironment.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/BlazeQueryEnvironment.java
@@ -17,6 +17,8 @@ import com.google.common.base.Preconditions;
 import com.google.common.base.Predicate;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Iterables;
+import com.google.devtools.build.lib.cmdline.ResolvedTargets;
+import com.google.devtools.build.lib.cmdline.TargetParsingException;
 import com.google.devtools.build.lib.events.EventHandler;
 import com.google.devtools.build.lib.graph.Digraph;
 import com.google.devtools.build.lib.graph.Node;
@@ -43,6 +45,7 @@ import java.util.Collection;
 import java.util.HashSet;
 import java.util.Iterator;
 import java.util.LinkedHashSet;
+import java.util.Map;
 import java.util.Set;
 
 /**
@@ -51,6 +54,7 @@ import java.util.Set;
 public class BlazeQueryEnvironment extends AbstractBlazeQueryEnvironment<Target> {
 
   private static final int MAX_DEPTH_FULL_SCAN_LIMIT = 20;
+  private final TargetPatternEvaluator targetPatternEvaluator;
   private final TransitivePackageLoader transitivePackageLoader;
   private final TargetProvider targetProvider;
   private final Digraph<Target> graph = new Digraph<>();
@@ -81,9 +85,8 @@ public class BlazeQueryEnvironment extends AbstractBlazeQueryEnvironment<Target>
       EventHandler eventHandler,
       Set<Setting> settings,
       Iterable<QueryFunction> extraFunctions) {
-    super(targetPatternEvaluator, keepGoing, strictScope, labelFilter, eventHandler, settings,
-        extraFunctions
-    );
+    super(keepGoing, strictScope, labelFilter, eventHandler, settings, extraFunctions);
+    this.targetPatternEvaluator = targetPatternEvaluator;
     this.transitivePackageLoader = transitivePackageLoader;
     this.targetProvider = packageProvider;
     this.errorObserver = new ErrorPrintingTargetEdgeErrorObserver(this.eventHandler);
@@ -93,6 +96,10 @@ public class BlazeQueryEnvironment extends AbstractBlazeQueryEnvironment<Target>
 
   @Override
   public BlazeQueryEvalResult<Target> evaluateQuery(QueryExpression expr) throws QueryException {
+    // Some errors are reported as QueryExceptions and others as ERROR events (if --keep_going). The
+    // result is set to have an error iff there were errors emitted during the query, so we reset
+    // errors here.
+    eventHandler.resetErrors();
     QueryEvalResult<Target> queryEvalResult = super.evaluateQuery(expr);
     return new BlazeQueryEvalResult<>(queryEvalResult.getSuccess(), queryEvalResult.getResultSet(),
         graph);
@@ -334,6 +341,19 @@ public class BlazeQueryEnvironment extends AbstractBlazeQueryEnvironment<Target>
     return dependentFiles;
   }
 
+  protected Map<String, ResolvedTargets<Target>> preloadOrThrow(Collection<String> patterns)
+      throws TargetParsingException {
+    try {
+      // Note that this may throw a RuntimeException if deps are missing in Skyframe and this is
+      // being called from within a SkyFunction.
+      return targetPatternEvaluator.preloadTargetPatterns(
+          eventHandler, patterns, keepGoing);
+    } catch (InterruptedException e) {
+      // TODO(bazel-team): Propagate the InterruptedException from here [skyframe-loading].
+      throw new TargetParsingException("interrupted");
+    }
+  }
+
   private static void addIfUniqueLabel(Node<Target> node, Set<Label> labels, Set<Target> nodes) {
     if (labels.add(node.getLabel().getLabel())) {
       nodes.add(node.getLabel());
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
new file mode 100644
index 0000000000..4a0dae66c2
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/query2/SkyQueryEnvironment.java
@@ -0,0 +1,351 @@
+// Copyright 2015 Google Inc. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//    http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+package com.google.devtools.build.lib.query2;
+
+import com.google.common.base.Preconditions;
+import com.google.common.base.Predicate;
+import com.google.common.collect.Collections2;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Iterables;
+import com.google.common.collect.Maps;
+import com.google.devtools.build.lib.cmdline.ResolvedTargets;
+import com.google.devtools.build.lib.cmdline.TargetParsingException;
+import com.google.devtools.build.lib.events.EventHandler;
+import com.google.devtools.build.lib.graph.Digraph;
+import com.google.devtools.build.lib.packages.NoSuchThingException;
+import com.google.devtools.build.lib.packages.Package;
+import com.google.devtools.build.lib.packages.Rule;
+import com.google.devtools.build.lib.packages.Target;
+import com.google.devtools.build.lib.pkgcache.TargetPatternEvaluator;
+import com.google.devtools.build.lib.query2.engine.QueryEvalResult;
+import com.google.devtools.build.lib.query2.engine.QueryException;
+import com.google.devtools.build.lib.query2.engine.QueryExpression;
+import com.google.devtools.build.lib.skyframe.PackageValue;
+import com.google.devtools.build.lib.skyframe.SkyFunctions;
+import com.google.devtools.build.lib.skyframe.TargetPatternValue;
+import com.google.devtools.build.lib.skyframe.TransitiveTargetValue;
+import com.google.devtools.build.lib.syntax.Label;
+import com.google.devtools.build.skyframe.SkyFunctionName;
+import com.google.devtools.build.skyframe.SkyKey;
+import com.google.devtools.build.skyframe.WalkableGraph;
+import com.google.devtools.build.skyframe.WalkableGraph.WalkableGraphFactory;
+
+import java.util.ArrayDeque;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Deque;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.LinkedHashSet;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+import javax.annotation.Nullable;
+
+/**
+ * {@link AbstractBlazeQueryEnvironment} that introspects the Skyframe graph to find forward and
+ * reverse edges. Results obtained by calling {@link #evaluateQuery} are not guaranteed to be in
+ * any particular order. As well, this class eagerly loads the full transitive closure of targets,
+ * even if the full closure isn't needed.
+ */
+public class SkyQueryEnvironment extends AbstractBlazeQueryEnvironment<Target> {
+  private WalkableGraph graph;
+
+  private final BlazeTargetAccessor accessor = new BlazeTargetAccessor(this);
+  private final int loadingPhaseThreads;
+  private final WalkableGraphFactory graphFactory;
+  private final List<String> universeScope;
+  private final String parserPrefix;
+
+  public SkyQueryEnvironment(boolean keepGoing, boolean strictScope, int loadingPhaseThreads,
+      Predicate<Label> labelFilter,
+      EventHandler eventHandler,
+      Set<Setting> settings,
+      Iterable<QueryFunction> extraFunctions, String parserPrefix,
+      WalkableGraphFactory graphFactory,
+      List<String> universeScope) {
+    super(keepGoing, strictScope, labelFilter,
+        eventHandler,
+        settings,
+        extraFunctions);
+    this.loadingPhaseThreads = loadingPhaseThreads;
+    this.graphFactory = graphFactory;
+    this.universeScope = Preconditions.checkNotNull(universeScope);
+    this.parserPrefix = parserPrefix;
+    Preconditions.checkState(!universeScope.isEmpty(),
+        "No queries can be performed with an empty universe");
+  }
+
+  private void init() throws InterruptedException {
+    graph = graphFactory.prepareAndGet(universeScope, loadingPhaseThreads, eventHandler);
+  }
+
+  @Override
+  public QueryEvalResult<Target> evaluateQuery(QueryExpression expr)
+      throws QueryException {
+    // Some errors are reported as QueryExceptions and others as ERROR events (if --keep_going). The
+    // result is set to have an error iff there were errors emitted during the query, so we reset
+    // errors here.
+    eventHandler.resetErrors();
+    try {
+      init();
+    } catch (InterruptedException e) {
+      throw new QueryException(e.getMessage());
+    }
+    return super.evaluateQuery(expr);
+  }
+
+  private static SkyKey transformToKey(Target value) {
+    return TransitiveTargetValue.key(value.getLabel());
+  }
+
+  @Nullable
+  private Target transformToValue(SkyKey key) {
+    SkyFunctionName functionName = key.functionName();
+    if (functionName != SkyFunctions.TRANSITIVE_TARGET) {
+      return null;
+    }
+    try {
+      return getTarget(((Label) key.argument()));
+    } catch (QueryException | TargetNotFoundException e) {
+      // Any problems with targets were already reported during #buildTransitiveClosure.
+      return null;
+    }
+  }
+
+  private Collection<Target> getRawFwdDeps(Target target) {
+    return makeTargets(graph.getDirectDeps(transformToKey(target)));
+  }
+
+  private Collection<Target> getRawReverseDeps(Target target) {
+    return makeTargets(graph.getReverseDeps(transformToKey(target)));
+  }
+
+  private Set<Label> getAllowedDeps(Rule rule) {
+    Set<Label> allowedLabels = new HashSet<>(rule.getLabels(dependencyFilter));
+    allowedLabels.addAll(rule.getVisibility().getDependencyLabels());
+    return allowedLabels;
+  }
+
+  public Collection<Target> getFwdDeps(Target target) {
+    Collection<Target> unfilteredDeps = getRawFwdDeps(target);
+    if (!(target instanceof Rule)) {
+      return getRawFwdDeps(target);
+    }
+    final Set<Label> allowedLabels = getAllowedDeps((Rule) target);
+    return Collections2.filter(unfilteredDeps,
+        new Predicate<Target>() {
+          @Override
+          public boolean apply(Target target) {
+            return allowedLabels.contains(target.getLabel());
+          }
+        });
+  }
+
+  public Collection<Target> getReverseDeps(final Target target) {
+    return Collections2.filter(getRawReverseDeps(target), new Predicate<Target>() {
+      @Override
+      public boolean apply(Target parent) {
+        return !(parent instanceof Rule)
+            || getAllowedDeps((Rule) parent).contains(target.getLabel());
+      }
+    });
+  }
+
+  @Override
+  public Set<Target> getTransitiveClosure(Set<Target> targets) {
+    Set<Target> visited = new HashSet<>();
+    List<Target> result = new ArrayList<>(targets);
+    int i = 0;
+    while (i < result.size()) {
+      for (Target dep : getFwdDeps(result.get(i))) {
+        if (visited.add(dep)) {
+          result.add(dep);
+        }
+      }
+      i++;
+    }
+    return ImmutableSet.copyOf(result);
+  }
+
+  // Implemented with a breadth-first search.
+  @Override
+  public Set<Target> getNodesOnPath(Target from, Target to) {
+    // Tree of nodes visited so far.
+    Map<Target, Target> nodeToParent = new HashMap<>();
+    // Contains all nodes left to visit in a (LIFO) stack.
+    Deque<Target> toVisit = new ArrayDeque<>();
+    toVisit.add(from);
+    nodeToParent.put(from, null);
+    while (!toVisit.isEmpty()) {
+      Target current = toVisit.removeFirst();
+      if (to.equals(current)) {
+        return ImmutableSet.copyOf(Digraph.getPathToTreeNode(nodeToParent, to));
+      }
+      for (Target dep : getFwdDeps(current)) {
+        if (!nodeToParent.containsKey(dep)) {
+          nodeToParent.put(dep, current);
+          toVisit.addFirst(dep);
+        }
+      }
+    }
+    // Note that the only current caller of this method checks first to see if there is a path
+    // before calling this method. It is not clear what the return value should be here.
+    return null;
+  }
+
+  @Override
+  public Set<Target> getTargetsMatchingPattern(QueryExpression owner, String pattern)
+      throws QueryException {
+    Set<Target> targets = new LinkedHashSet<>(resolvedTargetPatterns.get(pattern).getTargets());
+
+    // Sets.filter would be more convenient here, but can't deal with exceptions.
+    Iterator<Target> targetIterator = targets.iterator();
+    while (targetIterator.hasNext()) {
+      Target target = targetIterator.next();
+      if (!validateScope(target.getLabel(), strictScope)) {
+        targetIterator.remove();
+      }
+    }
+    return targets;
+  }
+
+  @Override
+  public Set<Target> getBuildFiles(QueryExpression caller, Set<Target> nodes)
+      throws QueryException {
+    Set<Target> dependentFiles = new LinkedHashSet<>();
+    Set<Package> seenPackages = new HashSet<>();
+    // Keep track of seen labels, to avoid adding a fake subinclude label that also exists as a
+    // real target.
+    Set<Label> seenLabels = new HashSet<>();
+
+    // Adds all the package definition files (BUILD files and build
+    // extensions) for package "pkg", to "buildfiles".
+    for (Target x : nodes) {
+      Package pkg = x.getPackage();
+      if (seenPackages.add(pkg)) {
+        addIfUniqueLabel(pkg.getBuildFile(), seenLabels, dependentFiles);
+        for (Label subinclude
+            : Iterables.concat(pkg.getSubincludeLabels(), pkg.getSkylarkFileDependencies())) {
+          addIfUniqueLabel(getSubincludeTarget(subinclude, pkg), seenLabels, dependentFiles);
+
+          // Also add the BUILD file of the subinclude.
+          try {
+            addIfUniqueLabel(getSubincludeTarget(
+                subinclude.getLocalTargetLabel("BUILD"), pkg), seenLabels, dependentFiles);
+          } catch (Label.SyntaxException e) {
+            throw new AssertionError("BUILD should always parse as a target name", e);
+          }
+        }
+      }
+    }
+    return dependentFiles;
+  }
+
+  private static void addIfUniqueLabel(Target node, Set<Label> labels, Set<Target> nodes) {
+    if (labels.add(node.getLabel())) {
+      nodes.add(node);
+    }
+  }
+
+  private static Target getSubincludeTarget(final Label label, Package pkg) {
+    return new FakeSubincludeTarget(label, pkg.getBuildFile().getLocation());
+  }
+
+  @Override
+  public TargetAccessor<Target> getAccessor() {
+    return accessor;
+  }
+
+  @Override
+  public Target getTarget(Label label) throws TargetNotFoundException, QueryException {
+    // Can't use strictScope here because we are expecting a target back.
+    validateScope(label, true);
+    SkyKey packageKey = PackageValue.key(label.getPackageIdentifier());
+    checkExistence(packageKey);
+    try {
+      PackageValue packageValue =
+          (PackageValue) graph.getValue(packageKey);
+      if (packageValue != null) {
+        return packageValue.getPackage().getTarget(label.getName());
+      } else {
+        throw (NoSuchThingException) Preconditions.checkNotNull(
+            graph.getException(packageKey), label);
+      }
+    } catch (NoSuchThingException e) {
+      throw new TargetNotFoundException(e);
+    }
+  }
+
+  @Override
+  public void buildTransitiveClosure(QueryExpression caller, Set<Target> targets, int maxDepth)
+      throws QueryException {
+    // Everything has already been loaded, so here we just check for errors so that we can
+    // pre-emptively throw/report if needed.
+    for (Target target : targets) {
+      SkyKey targetKey = TransitiveTargetValue.key(target.getLabel());
+      checkExistence(targetKey);
+      Exception exception = graph.getException(targetKey);
+      if (exception != null) {
+        reportBuildFileError(caller, exception.getMessage());
+      }
+    }
+  }
+
+  protected Map<String, ResolvedTargets<Target>> preloadOrThrow(Collection<String> patterns)
+      throws QueryException, TargetParsingException {
+    Map<String, ResolvedTargets<Target>> result =
+        Maps.newHashMapWithExpectedSize(patterns.size());
+    for (String pattern : patterns) {
+      SkyKey patternKey = TargetPatternValue.key(pattern,
+          TargetPatternEvaluator.DEFAULT_FILTERING_POLICY, parserPrefix);
+      checkExistence(patternKey);
+      TargetPatternValue value = (TargetPatternValue) graph.getValue(patternKey);
+      if (value != null) {
+        result.put(pattern, value.getTargets());
+      } else if (!keepGoing) {
+        throw (TargetParsingException) Preconditions.checkNotNull(graph.getException(patternKey),
+            pattern);
+      } else {
+        result.put(pattern, ResolvedTargets.<Target>builder().setError().build());
+      }
+    }
+    return result;
+  }
+
+  private Set<Target> makeTargets(Iterable<SkyKey> keys) {
+    ImmutableSet.Builder<Target> builder = ImmutableSet.builder();
+    for (SkyKey key : keys) {
+      Target value = transformToValue(key);
+      if (value != null) {
+        // Some values may be filtered out because they are not Targets.
+        builder.add(value);
+      }
+    }
+    return builder.build();
+  }
+
+  private void checkExistence(SkyKey key) throws QueryException {
+    if (!graph.exists(key)) {
+      throw new QueryException(key + " does not exist in graph");
+    }
+  }
+
+  @Override
+  public Target getOrCreate(Target target) {
+    return target;
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/query2/output/QueryOptions.java b/src/main/java/com/google/devtools/build/lib/query2/output/QueryOptions.java
index 810e8c77e9..c43610b909 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/output/QueryOptions.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/output/QueryOptions.java
@@ -14,10 +14,12 @@
 package com.google.devtools.build.lib.query2.output;
 
 import com.google.devtools.build.lib.query2.engine.QueryEnvironment.Setting;
+import com.google.devtools.common.options.Converters;
 import com.google.devtools.common.options.Option;
 import com.google.devtools.common.options.OptionsBase;
 
 import java.util.EnumSet;
+import java.util.List;
 import java.util.Set;
 
 /**
@@ -117,6 +119,15 @@ public class QueryOptions extends OptionsBase {
           + "containing non-test targets.")
   public boolean strictTestSuite;
 
+  @Option(name = "universe_scope",
+      converter = Converters.CommaSeparatedOptionListConverter.class,
+      defaultValue = "",
+      category = "query",
+      help = "A comma-separated set of target patterns (additive and subtractive). The query will "
+          + "be performed in the universe which is the transitive closure of the specified "
+          + "targets.")
+  public List<String> universeScope;
+
   /**
    * Return the current options as a set of QueryEnvironment settings.
    */
diff --git a/src/main/java/com/google/devtools/build/lib/rules/gen/GenQuery.java b/src/main/java/com/google/devtools/build/lib/rules/gen/GenQuery.java
index 0d639fc37f..ea0d439465 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/gen/GenQuery.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/gen/GenQuery.java
@@ -115,6 +115,10 @@ public class GenQuery implements RuleConfiguredTargetFactory {
       ruleContext.attributeError("opts", "option --keep_going is not allowed");
       return null;
     }
+    if (!queryOptions.universeScope.isEmpty()) {
+      ruleContext.attributeError("opts", "option --universe_scope is not allowed");
+      return null;
+    }
 
     final byte[] result = executeQuery(ruleContext, queryOptions, getScope(ruleContext), query);
     if (result == null || ruleContext.hasErrors()) {
@@ -251,12 +255,12 @@ public class GenQuery implements RuleConfiguredTargetFactory {
           Preconditions.checkNotNull(outputFormatters), queryOptions.outputFormat);
       queryResult = (BlazeQueryEvalResult<Target>) AbstractBlazeQueryEnvironment
           .newQueryEnvironment(
-          /*transitivePackageLoader=*/null, packageProvider,
+          /*transitivePackageLoader=*/null, /*graph=*/null, packageProvider,
               evaluator,
           /* keepGoing = */ false,
               ruleContext.attributes().get("strict", Type.BOOLEAN),
           /*orderedResults=*/QueryOutputUtils.orderResults(queryOptions, formatter),
-              4,
+              /*universeScope=*/ImmutableList.<String>of(), 4,
               labelFilter,
               getEventHandler(ruleContext),
               settings,
diff --git a/src/main/java/com/google/devtools/build/lib/runtime/commands/QueryCommand.java b/src/main/java/com/google/devtools/build/lib/runtime/commands/QueryCommand.java
index 4b5cbf094b..c1d986c2db 100644
--- a/src/main/java/com/google/devtools/build/lib/runtime/commands/QueryCommand.java
+++ b/src/main/java/com/google/devtools/build/lib/runtime/commands/QueryCommand.java
@@ -40,6 +40,7 @@ import com.google.devtools.common.options.OptionsProvider;
 import java.io.IOException;
 import java.io.PrintStream;
 import java.nio.channels.ClosedByInterruptException;
+import java.util.List;
 import java.util.Set;
 
 /**
@@ -105,7 +106,7 @@ public final class QueryCommand implements BlazeCommand {
         runtime,
         queryOptions.keepGoing,
         QueryOutputUtils.orderResults(queryOptions, formatter),
-        queryOptions.loadingPhaseThreads,
+        queryOptions.universeScope, queryOptions.loadingPhaseThreads,
         settings);
 
     // 1. Parse query:
@@ -150,7 +151,15 @@ public final class QueryCommand implements BlazeCommand {
 
   @VisibleForTesting // for com.google.devtools.deps.gquery.test.QueryResultTestUtil
   public static AbstractBlazeQueryEnvironment<Target> newQueryEnvironment(BlazeRuntime runtime,
-      boolean keepGoing, boolean orderedResults,  int loadingPhaseThreads,
+      boolean keepGoing, boolean orderedResults, int loadingPhaseThreads,
+      Set<Setting> settings) {
+    return newQueryEnvironment(runtime, keepGoing, orderedResults, ImmutableList.<String>of(),
+        loadingPhaseThreads, settings);
+  }
+
+  public static AbstractBlazeQueryEnvironment<Target> newQueryEnvironment(BlazeRuntime runtime,
+      boolean keepGoing, boolean orderedResults, List<String> universeScope,
+      int loadingPhaseThreads,
       Set<Setting> settings) {
     ImmutableList.Builder<QueryFunction> functions = ImmutableList.builder();
     for (BlazeModule module : runtime.getBlazeModules()) {
@@ -158,9 +167,11 @@ public final class QueryCommand implements BlazeCommand {
     }
     return AbstractBlazeQueryEnvironment.newQueryEnvironment(
         runtime.getPackageManager().newTransitiveLoader(),
+        runtime.getSkyframeExecutor(),
         runtime.getPackageManager(),
         runtime.getTargetPatternEvaluator(),
-        keepGoing, orderedResults, loadingPhaseThreads, runtime.getReporter(), settings,
+        keepGoing, orderedResults, universeScope, loadingPhaseThreads, runtime.getReporter(),
+        settings,
         functions.build());
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
index 9be7077ce7..0c5b503a89 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeExecutor.java
@@ -57,6 +57,8 @@ import com.google.devtools.build.lib.analysis.config.BuildOptions;
 import com.google.devtools.build.lib.analysis.config.ConfigurationFactory;
 import com.google.devtools.build.lib.analysis.config.ConfigurationFragmentFactory;
 import com.google.devtools.build.lib.analysis.config.InvalidConfigurationException;
+import com.google.devtools.build.lib.cmdline.ResolvedTargets;
+import com.google.devtools.build.lib.cmdline.TargetParsingException;
 import com.google.devtools.build.lib.concurrent.ThreadSafety;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadCompatible;
 import com.google.devtools.build.lib.events.EventHandler;
@@ -70,9 +72,11 @@ import com.google.devtools.build.lib.packages.PackageIdentifier;
 import com.google.devtools.build.lib.packages.Preprocessor;
 import com.google.devtools.build.lib.packages.RuleVisibility;
 import com.google.devtools.build.lib.packages.Target;
+import com.google.devtools.build.lib.pkgcache.FilteringPolicy;
 import com.google.devtools.build.lib.pkgcache.PackageCacheOptions;
 import com.google.devtools.build.lib.pkgcache.PackageManager;
 import com.google.devtools.build.lib.pkgcache.PathPackageLocator;
+import com.google.devtools.build.lib.pkgcache.TargetPatternEvaluator;
 import com.google.devtools.build.lib.pkgcache.TransitivePackageLoader;
 import com.google.devtools.build.lib.skyframe.SkyframeActionExecutor.ActionCompletedReceiver;
 import com.google.devtools.build.lib.skyframe.SkyframeActionExecutor.ProgressSupplier;
@@ -101,6 +105,8 @@ import com.google.devtools.build.skyframe.SkyFunction;
 import com.google.devtools.build.skyframe.SkyFunctionName;
 import com.google.devtools.build.skyframe.SkyKey;
 import com.google.devtools.build.skyframe.SkyValue;
+import com.google.devtools.build.skyframe.WalkableGraph;
+import com.google.devtools.build.skyframe.WalkableGraph.WalkableGraphFactory;
 
 import java.io.IOException;
 import java.io.PrintStream;
@@ -128,7 +134,7 @@ import javax.annotation.Nullable;
  * some additional artifacts (workspace status and build info artifacts) into SkyFunctions
  * for use during the build.
  */
-public abstract class SkyframeExecutor {
+public abstract class SkyframeExecutor implements WalkableGraphFactory {
   private final EvaluatorSupplier evaluatorSupplier;
   protected MemoizingEvaluator memoizingEvaluator;
   private final MemoizingEvaluator.EmittedEventState emittedEventState =
@@ -1163,6 +1169,43 @@ public abstract class SkyframeExecutor {
   }
 
   /**
+   * For internal use in queries: performs two graph updates to make sure the transitive closure of
+   * the specified target {@code patterns} is present in the graph, and returns a traversable view
+   * of the graph.
+   *
+   * <p>The graph updates here are unconditionally done in keep-going mode, so that the query is
+   * guaranteed a complete graph to work on.
+   */
+  @Override
+  public WalkableGraph prepareAndGet(Collection<String> patterns, int numThreads,
+      EventHandler eventHandler) throws InterruptedException {
+    SkyframeTargetPatternEvaluator patternEvaluator =
+        (SkyframeTargetPatternEvaluator) packageManager.getTargetPatternEvaluator();
+    String offset = patternEvaluator.getOffset();
+    FilteringPolicy policy = TargetPatternEvaluator.DEFAULT_FILTERING_POLICY;
+    Iterable<SkyKey> patternSkyKeys = TargetPatternValue.keys(patterns, policy, offset);
+    ResolvedTargets<Target> result;
+    try {
+      result = patternEvaluator.parseTargetPatternKeys(patternSkyKeys, /*keepGoing=*/true,
+          eventHandler);
+    } catch (TargetParsingException e) {
+      // Can't happen, since we ran with keepGoing.
+      throw new IllegalStateException(e);
+    }
+    List<SkyKey> targetKeys = new ArrayList<>();
+    for (Target target : result.getTargets()) {
+      targetKeys.add(TransitiveTargetValue.key(target.getLabel()));
+    }
+    // We request all the keys here, even the ones that were already evaluated, because we want a
+    // single graph that contains all these keys, and if the evaluator keys graphs based on
+    // top-level keys, we must request the union of all our desired keys in a single evaluate call.
+    Iterable<SkyKey> allKeys = ImmutableList.copyOf(Iterables.concat(patternSkyKeys, targetKeys));
+    return Preconditions.checkNotNull(
+        buildDriver.evaluate(allKeys, true, numThreads, eventHandler).getWalkableGraph(),
+        patterns);
+  }
+
+  /**
    * Returns the generating {@link Action} of the given {@link Artifact}.
    *
    * <p>For use for legacy support from {@code BuildView} only.
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeTargetPatternEvaluator.java b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeTargetPatternEvaluator.java
index 9e619e383d..050bdab598 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeTargetPatternEvaluator.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/SkyframeTargetPatternEvaluator.java
@@ -23,7 +23,6 @@ import com.google.devtools.build.lib.cmdline.TargetParsingException;
 import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.events.EventHandler;
 import com.google.devtools.build.lib.packages.Target;
-import com.google.devtools.build.lib.pkgcache.FilteringPolicies;
 import com.google.devtools.build.lib.pkgcache.FilteringPolicy;
 import com.google.devtools.build.lib.pkgcache.ParseFailureListener;
 import com.google.devtools.build.lib.pkgcache.TargetPatternEvaluator;
@@ -58,7 +57,7 @@ final class SkyframeTargetPatternEvaluator implements TargetPatternEvaluator {
   public ResolvedTargets<Target> parseTargetPattern(EventHandler eventHandler,
       String pattern, boolean keepGoing) throws TargetParsingException, InterruptedException {
     return parseTargetPatternList(eventHandler, ImmutableList.of(pattern),
-        FilteringPolicies.NO_FILTER, keepGoing);
+        DEFAULT_FILTERING_POLICY, keepGoing);
   }
 
   @Override
@@ -92,7 +91,12 @@ final class SkyframeTargetPatternEvaluator implements TargetPatternEvaluator {
   ResolvedTargets<Target> parseTargetPatternList(String offset, EventHandler eventHandler,
       List<String> targetPatterns, FilteringPolicy policy, boolean keepGoing)
       throws InterruptedException, TargetParsingException {
-    Iterable<SkyKey> patternSkyKeys = TargetPatternValue.keys(targetPatterns, policy, offset);
+    return parseTargetPatternKeys(TargetPatternValue.keys(targetPatterns, policy, offset),
+        keepGoing, eventHandler);
+  }
+
+  ResolvedTargets<Target> parseTargetPatternKeys(Iterable<SkyKey> patternSkyKeys, boolean keepGoing,
+      EventHandler eventHandler) throws InterruptedException, TargetParsingException {
     EvaluationResult<TargetPatternValue> result =
         skyframeExecutor.targetPatterns(patternSkyKeys, keepGoing, eventHandler);