Initial (partial) implementation of configured target query. Activated by passing the --post_build_query flag to a build command, with a query expression as the argument. Bazel then executes this query on the configured target graph as constructed by the build command.

Since the prepare graph -> query workflow is how SkyQueryEnvironment works, this is mostly just copying that.

Main missing features/code cleanups:
* Recursive target patterns (/...) are not supported.
* There is no way to specify the configuration of the targets in your query.
* Configuration output is totally opaque (just the hash, or null if no configuration).
* More generally, no output options.
* Some features (visibility, label attrs) not supported.
* No edge filtering (host deps, implicit deps).
* Aspects are totally ignored.
* Graceful failure on errors, edge cases, incompatible flags (like the TAP flags that discard edges).
* Code hygiene issues (calling test-only method to get to Skyframe graph, some code duplication across ConfiguredTargetQueryEnvironment and SkyQueryEnvironment).

Most of the features I plan to leave to rules-side people, since I think they won't be too hard for a general Blaze developer to implement, and designing the right features and user interfaces for these things is better left to the rules side.

PiperOrigin-RevId: 165747829

1 files changed, 95 insertions, 0 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/query2/SkyQueryUtils.java b/src/main/java/com/google/devtools/build/lib/query2/SkyQueryUtils.java
new file mode 100644
index 0000000000..002b9c0197
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/query2/SkyQueryUtils.java
@@ -0,0 +1,95 @@
+// Copyright 2017 The Bazel Authors. 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.collect.ImmutableList;
+import com.google.common.collect.Iterables;
+import com.google.devtools.build.lib.cmdline.Label;
+import com.google.devtools.build.lib.graph.Digraph;
+import com.google.devtools.build.lib.packages.Target;
+import com.google.devtools.build.lib.query2.engine.QueryEnvironment.ThreadSafeMutableSet;
+import com.google.devtools.build.lib.util.Preconditions;
+import java.util.ArrayDeque;
+import java.util.Deque;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.function.Function;
+import java.util.stream.Collectors;
+
+/** Utility class for Skyframe-based query implementations. */
+class SkyQueryUtils {
+  interface GetFwdDeps<T> {
+    ThreadSafeMutableSet<T> getFwdDeps(Iterable<T> t) throws InterruptedException;
+  }
+
+  static <T> ThreadSafeMutableSet<T> getTransitiveClosure(
+      ThreadSafeMutableSet<T> targets, GetFwdDeps<T> getFwdDeps, ThreadSafeMutableSet<T> visited)
+      throws InterruptedException {
+    ThreadSafeMutableSet<T> current = targets;
+    while (!current.isEmpty()) {
+      Iterable<T> toVisit =
+          current.stream().filter(obj -> !visited.contains(obj)).collect(Collectors.toList());
+      current = getFwdDeps.getFwdDeps(toVisit);
+      Iterables.addAll(visited, toVisit);
+    }
+    return visited;
+  }
+
+  /**
+   * Gets a path from {@code from} to {@code to}, walking the graph revealed by {@code getFwdDeps}.
+   *
+   * <p>In case the type {@link T} does not implement equality, {@code label} will be used to map
+   * elements of type {@link T} to elements of type {@link L} which does implement equality. {@code
+   * label} should be an injective function. For instance, if {@link T} is of type {@link Target}
+   * then {@link L} could be of type {@link Label} and {@code label} could be {@link
+   * Target::getLabel}.
+   *
+   * <p>Implemented with a breadth-first search.
+   */
+  static <T, L> ImmutableList<T> getNodesOnPath(
+      T from, T to, GetFwdDeps<T> getFwdDeps, Function<T, L> label) throws InterruptedException {
+    // Tree of nodes visited so far.
+    Map<L, L> nodeToParent = new HashMap<>();
+    Map<L, T> labelToTarget = new HashMap<>();
+    // Contains all nodes left to visit in a (LIFO) stack.
+    Deque<T> toVisit = new ArrayDeque<>();
+    toVisit.add(from);
+    nodeToParent.put(label.apply(from), null);
+    labelToTarget.put(label.apply(from), from);
+    while (!toVisit.isEmpty()) {
+      T current = toVisit.removeFirst();
+      if (label.apply(to).equals(label.apply(current))) {
+        List<L> labelPath = Digraph.getPathToTreeNode(nodeToParent, label.apply(to));
+        ImmutableList.Builder<T> targetPathBuilder = ImmutableList.builder();
+        for (L item : labelPath) {
+          targetPathBuilder.add(Preconditions.checkNotNull(labelToTarget.get(item), item));
+        }
+        return targetPathBuilder.build();
+      }
+      for (T dep : getFwdDeps.getFwdDeps(ImmutableList.of(current))) {
+        L depLabel = label.apply(dep);
+        if (!nodeToParent.containsKey(depLabel)) {
+          nodeToParent.put(depLabel, label.apply(current));
+          labelToTarget.put(depLabel, dep);
+          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;
+  }
+}