Update from Google.

--
MOE_MIGRATED_REVID=85702957

36 files changed, 5658 insertions, 0 deletions

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
new file mode 100644
index 0000000000..d6c2992a53
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/query2/BlazeQueryEnvironment.java
@@ -0,0 +1,633 @@
+// Copyright 2014 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 static com.google.devtools.build.lib.packages.Type.BOOLEAN;
+import static com.google.devtools.build.lib.packages.Type.TRISTATE;
+
+import com.google.common.base.Preconditions;
+import com.google.common.base.Predicate;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Iterables;
+import com.google.common.collect.Sets;
+import com.google.devtools.build.lib.cmdline.ResolvedTargets;
+import com.google.devtools.build.lib.cmdline.TargetParsingException;
+import com.google.devtools.build.lib.events.ErrorSensingEventHandler;
+import com.google.devtools.build.lib.events.Event;
+import com.google.devtools.build.lib.events.EventHandler;
+import com.google.devtools.build.lib.graph.Digraph;
+import com.google.devtools.build.lib.graph.Node;
+import com.google.devtools.build.lib.packages.AggregatingAttributeMapper;
+import com.google.devtools.build.lib.packages.Attribute;
+import com.google.devtools.build.lib.packages.NoSuchThingException;
+import com.google.devtools.build.lib.packages.NonconfigurableAttributeMapper;
+import com.google.devtools.build.lib.packages.OutputFile;
+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.packages.TargetUtils;
+import com.google.devtools.build.lib.packages.Type;
+import com.google.devtools.build.lib.pkgcache.PackageProvider;
+import com.google.devtools.build.lib.pkgcache.TargetEdgeObserver;
+import com.google.devtools.build.lib.pkgcache.TargetPatternEvaluator;
+import com.google.devtools.build.lib.pkgcache.TargetProvider;
+import com.google.devtools.build.lib.query2.engine.BlazeQueryEvalResult;
+import com.google.devtools.build.lib.query2.engine.QueryEnvironment;
+import com.google.devtools.build.lib.query2.engine.QueryException;
+import com.google.devtools.build.lib.query2.engine.QueryExpression;
+import com.google.devtools.build.lib.query2.engine.SkyframeRestartQueryException;
+import com.google.devtools.build.lib.syntax.Label;
+import com.google.devtools.build.lib.util.BinaryPredicate;
+import com.google.devtools.build.lib.vfs.PathFragment;
+
+import java.util.ArrayList;
+import java.util.Collection;
+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;
+
+/**
+ * The environment of a Blaze query. Not thread-safe.
+ */
+public class BlazeQueryEnvironment implements QueryEnvironment<Target> {
+  protected final ErrorSensingEventHandler eventHandler;
+  private final TargetProvider targetProvider;
+  private final TargetPatternEvaluator targetPatternEvaluator;
+  private final Digraph<Target> graph = new Digraph<>();
+  private final ErrorPrintingTargetEdgeErrorObserver errorObserver;
+  private final LabelVisitor labelVisitor;
+  private final Map<String, Set<Target>> letBindings = new HashMap<>();
+  private final Map<String, ResolvedTargets<Target>> resolvedTargetPatterns = new HashMap<>();
+  protected final boolean keepGoing;
+  private final boolean strictScope;
+  protected final int loadingPhaseThreads;
+
+  private final BinaryPredicate<Rule, Attribute> dependencyFilter;
+  private final Predicate<Label> labelFilter;
+
+  private final Set<Setting> settings;
+  private final List<QueryFunction> extraFunctions;
+  private final BlazeTargetAccessor accessor = new BlazeTargetAccessor();
+
+  /**
+   * Note that the correct operation of this class critically depends on the Reporter being a
+   * singleton object, shared by all cooperating classes contributing to Query.
+   * @param strictScope if true, fail the whole query if a label goes out of scope.
+   * @param loadingPhaseThreads the number of threads to use during loading
+   *     the packages for the query.
+   * @param labelFilter a predicate that determines if a specific label is
+   *     allowed to be visited during query execution. If it returns false,
+   *     the query execution is stopped with an error message.
+   * @param settings a set of enabled settings
+   */
+  public BlazeQueryEnvironment(PackageProvider packageProvider,
+      TargetPatternEvaluator targetPatternEvaluator,
+      boolean keepGoing,
+      boolean strictScope,
+      int loadingPhaseThreads,
+      Predicate<Label> labelFilter,
+      EventHandler eventHandler,
+      Set<Setting> settings,
+      Iterable<QueryFunction> extraFunctions) {
+    this.eventHandler = new ErrorSensingEventHandler(eventHandler);
+    this.targetProvider = packageProvider;
+    this.targetPatternEvaluator = targetPatternEvaluator;
+    this.errorObserver = new ErrorPrintingTargetEdgeErrorObserver(this.eventHandler);
+    this.keepGoing = keepGoing;
+    this.strictScope = strictScope;
+    this.loadingPhaseThreads = loadingPhaseThreads;
+    this.dependencyFilter = constructDependencyFilter(settings);
+    this.labelVisitor = new LabelVisitor(packageProvider, dependencyFilter);
+    this.labelFilter = labelFilter;
+    this.settings = Sets.immutableEnumSet(settings);
+    this.extraFunctions = ImmutableList.copyOf(extraFunctions);
+  }
+
+  /**
+   * Note that the correct operation of this class critically depends on the Reporter being a
+   * singleton object, shared by all cooperating classes contributing to Query.
+   * @param loadingPhaseThreads the number of threads to use during loading
+   *     the packages for the query.
+   * @param settings a set of enabled settings
+   */
+  public BlazeQueryEnvironment(PackageProvider packageProvider,
+      TargetPatternEvaluator targetPatternEvaluator,
+      boolean keepGoing,
+      int loadingPhaseThreads,
+      EventHandler eventHandler,
+      Set<Setting> settings,
+      Iterable<QueryFunction> extraFunctions) {
+    this(packageProvider, targetPatternEvaluator, keepGoing, /*strictScope=*/true,
+        loadingPhaseThreads, Rule.ALL_LABELS, eventHandler, settings, extraFunctions);
+  }
+
+  private static BinaryPredicate<Rule, Attribute> constructDependencyFilter(Set<Setting> settings) {
+    BinaryPredicate<Rule, Attribute> specifiedFilter =
+        settings.contains(Setting.NO_HOST_DEPS) ? Rule.NO_HOST_DEPS : Rule.ALL_DEPS;
+    if (settings.contains(Setting.NO_IMPLICIT_DEPS)) {
+      specifiedFilter = Rule.and(specifiedFilter, Rule.NO_IMPLICIT_DEPS);
+    }
+    if (settings.contains(Setting.NO_NODEP_DEPS)) {
+      specifiedFilter = Rule.and(specifiedFilter, Rule.NO_NODEP_ATTRIBUTES);
+    }
+    return specifiedFilter;
+  }
+
+  /**
+   * Evaluate the specified query expression in this environment.
+   *
+   * @return a {@link BlazeQueryEvalResult} object that contains the resulting set of targets, the
+   *   partial graph, and a bit to indicate whether errors occured during evaluation; note that the
+   *   success status can only be false if {@code --keep_going} was in effect
+   * @throws QueryException if the evaluation failed and {@code --nokeep_going} was in
+   *   effect
+   */
+  public BlazeQueryEvalResult<Target> 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
+    // specified; using a linked hash set here makes sure that the left-most error is reported.
+    Set<String> targetPatternSet = new LinkedHashSet<>();
+    expr.collectTargetPatterns(targetPatternSet);
+    try {
+      resolvedTargetPatterns.putAll(preloadOrThrow(targetPatternSet));
+    } catch (TargetParsingException e) {
+      // Unfortunately, by evaluating the patterns in parallel, we lose some location information.
+      throw new QueryException(expr, e.getMessage());
+    }
+
+    Set<Target> resultNodes;
+    try {
+      resultNodes = expr.eval(this);
+    } catch (QueryException e) {
+      throw new QueryException(e, expr);
+    }
+
+    if (eventHandler.hasErrors()) {
+      if (!keepGoing) {
+        // This case represents loading-phase errors reported during evaluation
+        // of target patterns that don't cause evaluation to fail per se.
+        throw new QueryException("Evaluation of query \"" + expr
+            + "\" failed due to BUILD file errors");
+      } else {
+        eventHandler.handle(Event.warn("--keep_going specified, ignoring errors.  "
+                      + "Results may be inaccurate"));
+      }
+    }
+
+    return new BlazeQueryEvalResult<>(!eventHandler.hasErrors(), resultNodes, graph);
+  }
+
+  public BlazeQueryEvalResult<Target> evaluateQuery(String query) throws QueryException {
+    return evaluateQuery(QueryExpression.parse(query, this));
+  }
+
+  @Override
+  public void reportBuildFileError(QueryExpression caller, String message) throws QueryException {
+    if (!keepGoing) {
+      throw new QueryException(caller, message);
+    } else {
+      // Keep consistent with evaluateQuery() above.
+      eventHandler.handle(Event.error("Evaluation of query \"" + caller + "\" failed: " + message));
+    }
+  }
+
+  @Override
+  public Set<Target> getTargetsMatchingPattern(QueryExpression caller,
+      String pattern) throws QueryException {
+    // We can safely ignore the boolean error flag. The evaluateQuery() method above wraps the
+    // entire query computation in an error sensor.
+
+    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();
+      }
+    }
+
+    Set<PathFragment> packages = new HashSet<>();
+    for (Target target : targets) {
+      packages.add(target.getLabel().getPackageFragment());
+    }
+
+    Set<Target> result = new LinkedHashSet<>();
+    for (Target target : targets) {
+      result.add(getOrCreate(target));
+
+      // Preservation of graph order: it is important that targets obtained via
+      // a wildcard such as p:* are correctly ordered w.r.t. each other, so to
+      // ensure this, we add edges between any pair of directly connected
+      // targets in this set.
+      if (target instanceof OutputFile) {
+        OutputFile outputFile = (OutputFile) target;
+        if (targets.contains(outputFile.getGeneratingRule())) {
+          makeEdge(outputFile, outputFile.getGeneratingRule());
+        }
+      } else if (target instanceof Rule) {
+        Rule rule = (Rule) target;
+        for (Label label : rule.getLabels(dependencyFilter)) {
+          if (!packages.contains(label.getPackageFragment())) {
+            continue;  // don't cause additional package loading
+          }
+          try {
+            if (!validateScope(label, strictScope)) {
+              continue;  // Don't create edges to targets which are out of scope.
+            }
+            Target to = getTargetOrThrow(label);
+            if (targets.contains(to)) {
+              makeEdge(rule, to);
+            }
+          } catch (NoSuchThingException e) {
+            /* ignore */
+          } catch (InterruptedException e) {
+            throw new QueryException("interrupted");
+          }
+        }
+      }
+    }
+    return result;
+  }
+
+  public Node<Target> getTarget(Label label) throws TargetNotFoundException, QueryException {
+    // Can't use strictScope here because we are expecting a target back.
+    validateScope(label, true);
+    try {
+      return getNode(getTargetOrThrow(label));
+    } catch (NoSuchThingException e) {
+      throw new TargetNotFoundException(e);
+    } catch (InterruptedException e) {
+      throw new QueryException("interrupted");
+    }
+  }
+
+  private Node<Target> getNode(Target target) {
+    return graph.createNode(target);
+  }
+
+  private Collection<Node<Target>> getNodes(Iterable<Target> target) {
+    Set<Node<Target>> result = new LinkedHashSet<>();
+    for (Target t : target) {
+      result.add(getNode(t));
+    }
+    return result;
+  }
+
+  @Override
+  public Target getOrCreate(Target target) {
+    return getNode(target).getLabel();
+  }
+
+  @Override
+  public Collection<Target> getFwdDeps(Target target) {
+    return getTargetsFromNodes(getNode(target).getSuccessors());
+  }
+
+  @Override
+  public Collection<Target> getReverseDeps(Target target) {
+    return getTargetsFromNodes(getNode(target).getPredecessors());
+  }
+
+  @Override
+  public Set<Target> getTransitiveClosure(Set<Target> targetNodes) {
+    for (Target node : targetNodes) {
+      checkBuilt(node);
+    }
+    return getTargetsFromNodes(graph.getFwdReachable(getNodes(targetNodes)));
+  }
+
+  /**
+   * Checks that the graph rooted at 'targetNode' has been completely built;
+   * fails if not.  Callers of {@link #getTransitiveClosure} must ensure that
+   * {@link #buildTransitiveClosure} has been called before.
+   *
+   * <p>It would be inefficient and failure-prone to make getTransitiveClosure
+   * call buildTransitiveClosure directly.  Also, it would cause
+   * nondeterministic behavior of the operators, since the set of packages
+   * loaded (and hence errors reported) would depend on the ordering details of
+   * the query operators' implementations.
+   */
+  private void checkBuilt(Target targetNode) {
+    Preconditions.checkState(
+        labelVisitor.hasVisited(targetNode.getLabel()),
+        "getTransitiveClosure(%s) called without prior call to buildTransitiveClosure()",
+        targetNode);
+  }
+
+  protected void preloadTransitiveClosure(Set<Target> targets, int maxDepth) throws QueryException {
+  }
+
+  @Override
+  public void buildTransitiveClosure(QueryExpression caller,
+                                     Set<Target> targetNodes,
+                                     int maxDepth) throws QueryException {
+    Set<Target> targets = targetNodes;
+    preloadTransitiveClosure(targets, maxDepth);
+
+    try {
+      labelVisitor.syncWithVisitor(eventHandler, targets, keepGoing,
+          loadingPhaseThreads, maxDepth, errorObserver, new GraphBuildingObserver());
+    } catch (InterruptedException e) {
+      throw new QueryException(caller, "transitive closure computation was interrupted");
+    }
+
+    if (errorObserver.hasErrors()) {
+      reportBuildFileError(caller, "errors were encountered while computing transitive closure");
+    }
+  }
+
+  @Override
+  public Set<Target> getNodesOnPath(Target from, Target to) {
+    return getTargetsFromNodes(graph.getShortestPath(getNode(from), getNode(to)));
+  }
+
+  @Override
+  public Set<Target> getVariable(String name) {
+    return letBindings.get(name);
+  }
+
+  @Override
+  public Set<Target> setVariable(String name, Set<Target> value) {
+    return letBindings.put(name, value);
+  }
+
+  /**
+   * It suffices to synchronize the modifications of this.graph from within the
+   * GraphBuildingObserver, because that's the only concurrent part.
+   * Concurrency is always encapsulated within the evaluation of a single query
+   * operator (e.g. deps(), somepath(), etc).
+   */
+  private class GraphBuildingObserver implements TargetEdgeObserver {
+
+    @Override
+    public synchronized void edge(Target from, Attribute attribute, Target to) {
+      Preconditions.checkState(attribute == null ||
+          dependencyFilter.apply(((Rule) from), attribute),
+          "Disallowed edge from LabelVisitor: %s --> %s", from, to);
+      makeEdge(from, to);
+    }
+
+    @Override
+    public synchronized void node(Target node) {
+      graph.createNode(node);
+    }
+
+    @Override
+    public void missingEdge(Target target, Label to, NoSuchThingException e) {
+      // No - op.
+    }
+  }
+
+  private void makeEdge(Target from, Target to) {
+    graph.addEdge(from, to);
+  }
+
+  private boolean validateScope(Label label, boolean strict) throws QueryException {
+    if (!labelFilter.apply(label)) {
+      String error = String.format("target '%s' is not within the scope of the query", label);
+      if (strict) {
+        throw new QueryException(error);
+      } else {
+        eventHandler.handle(Event.warn(error + ". Skipping"));
+        return false;
+      }
+    }
+    return true;
+  }
+
+  public Set<Target> evalTargetPattern(QueryExpression caller, String pattern)
+      throws QueryException {
+    if (!resolvedTargetPatterns.containsKey(pattern)) {
+      try {
+        resolvedTargetPatterns.putAll(preloadOrThrow(ImmutableList.of(pattern)));
+      } catch (TargetParsingException e) {
+        // Will skip the target and keep going if -k is specified.
+        resolvedTargetPatterns.put(pattern, ResolvedTargets.<Target>empty());
+        reportBuildFileError(caller, e.getMessage());
+      }
+    }
+    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.
+      return targetPatternEvaluator.preloadTargetPatterns(
+          eventHandler, patterns, keepGoing);
+    } catch (InterruptedException e) {
+      // TODO(bazel-team): Propagate the InterruptedException from here [skyframe-loading].
+      throw new TargetParsingException("interrupted");
+    }
+  }
+
+  private Target getTargetOrThrow(Label label)
+      throws NoSuchThingException, SkyframeRestartQueryException, InterruptedException {
+    Target target = targetProvider.getTarget(eventHandler, label);
+    if (target == null) {
+      throw new SkyframeRestartQueryException();
+    }
+    return target;
+  }
+
+  // TODO(bazel-team): rename this to getDependentFiles when all implementations
+  // of QueryEnvironment is fixed.
+  @Override
+  public Set<Target> getBuildFiles(final 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(getNode(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(Node<Target> node, Set<Label> labels, Set<Target> nodes) {
+    if (labels.add(node.getLabel().getLabel())) {
+      nodes.add(node.getLabel());
+    }
+  }
+
+  private Node<Target> getSubincludeTarget(final Label label, Package pkg) {
+    return getNode(new FakeSubincludeTarget(label, pkg.getBuildFile().getLocation()));
+  }
+
+  @Override
+  public TargetAccessor<Target> getAccessor() {
+    return accessor;
+  }
+
+  @Override
+  public boolean isSettingEnabled(Setting setting) {
+    return settings.contains(Preconditions.checkNotNull(setting));
+  }
+
+  @Override
+  public Iterable<QueryFunction> getFunctions() {
+    ImmutableList.Builder<QueryFunction> builder = ImmutableList.builder();
+    builder.addAll(DEFAULT_QUERY_FUNCTIONS);
+    builder.addAll(extraFunctions);
+    return builder.build();
+  }
+
+  private final class BlazeTargetAccessor implements TargetAccessor<Target> {
+
+    @Override
+    public String getTargetKind(Target target) {
+      return target.getTargetKind();
+    }
+
+    @Override
+    public String getLabel(Target target) {
+      return target.getLabel().toString();
+    }
+
+    @Override
+    public List<Target> getLabelListAttr(QueryExpression caller, Target target, String attrName,
+        String errorMsgPrefix) throws QueryException {
+      Preconditions.checkArgument(target instanceof Rule);
+
+      List<Target> result = new ArrayList<>();
+      Rule rule = (Rule) target;
+
+      AggregatingAttributeMapper attrMap = AggregatingAttributeMapper.of(rule);
+      Type<?> attrType = attrMap.getAttributeType(attrName);
+      if (attrType == null) {
+        // Return an empty list if the attribute isn't defined for this rule.
+        return ImmutableList.of();
+      }
+      for (Object value : attrMap.visitAttribute(attrName, attrType)) {
+        // Computed defaults may have null values.
+        if (value != null) {
+          for (Label label : attrType.getLabels(value)) {
+            try {
+              result.add(getTarget(label).getLabel());
+            } catch (TargetNotFoundException e) {
+              reportBuildFileError(caller, errorMsgPrefix + e.getMessage());
+            }
+          }
+        }
+      }
+
+      return result;
+    }
+
+    @Override
+    public List<String> getStringListAttr(Target target, String attrName) {
+      Preconditions.checkArgument(target instanceof Rule);
+      return NonconfigurableAttributeMapper.of((Rule) target).get(attrName, Type.STRING_LIST);
+    }
+
+    @Override
+    public String getStringAttr(Target target, String attrName) {
+      Preconditions.checkArgument(target instanceof Rule);
+      return NonconfigurableAttributeMapper.of((Rule) target).get(attrName, Type.STRING);
+    }
+
+    @Override
+    public Iterable<String> getAttrAsString(Target target, String attrName) {
+      Preconditions.checkArgument(target instanceof Rule);
+      List<String> values = new ArrayList<>(); // May hold null values.
+      Attribute attribute = ((Rule) target).getAttributeDefinition(attrName);
+      if (attribute != null) {
+        Type<?> attributeType = attribute.getType();
+        for (Object attrValue : AggregatingAttributeMapper.of((Rule) target).visitAttribute(
+            attribute.getName(), attributeType)) {
+
+          // Ugly hack to maintain backward 'attr' query compatibility for BOOLEAN and TRISTATE
+          // attributes. These are internally stored as actual Boolean or TriState objects but were
+          // historically queried as integers. To maintain compatibility, we inspect their actual
+          // value and return the integer equivalent represented as a String. This code is the
+          // opposite of the code in BooleanType and TriStateType respectively.
+          if (attributeType == BOOLEAN) {
+            values.add(Type.BOOLEAN.cast(attrValue) ? "1" : "0");
+          } else if (attributeType == TRISTATE) {
+              switch (Type.TRISTATE.cast(attrValue)) {
+                case AUTO :
+                  values.add("-1");
+                  break;
+                case NO :
+                  values.add("0");
+                  break;
+                case YES :
+                  values.add("1");
+                  break;
+                default :
+                  throw new AssertionError("This can't happen!");
+              }
+          } else {
+            values.add(attrValue == null ? null : attrValue.toString());
+          }
+        }
+      }
+      return values;
+    }
+
+    @Override
+    public boolean isRule(Target target) {
+      return target instanceof Rule;
+    }
+
+    @Override
+    public boolean isTestRule(Target target) {
+      return TargetUtils.isTestRule(target);
+    }
+
+    @Override
+    public boolean isTestSuite(Target target) {
+      return TargetUtils.isTestSuiteRule(target);
+    }
+  }
+
+  /** Given a set of target nodes, returns the targets. */
+  private static Set<Target> getTargetsFromNodes(Iterable<Node<Target>> input) {
+    Set<Target> result = new LinkedHashSet<>();
+    for (Node<Target> node : input) {
+      result.add(node.getLabel());
+    }
+    return result;
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/query2/ErrorPrintingTargetEdgeErrorObserver.java b/src/main/java/com/google/devtools/build/lib/query2/ErrorPrintingTargetEdgeErrorObserver.java
new file mode 100644
index 0000000000..d47b8f3b4f
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/query2/ErrorPrintingTargetEdgeErrorObserver.java
@@ -0,0 +1,53 @@
+// Copyright 2014 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.devtools.build.lib.concurrent.ThreadSafety;
+import com.google.devtools.build.lib.events.Event;
+import com.google.devtools.build.lib.events.EventHandler;
+import com.google.devtools.build.lib.packages.NoSuchThingException;
+import com.google.devtools.build.lib.packages.Target;
+import com.google.devtools.build.lib.packages.TargetUtils;
+import com.google.devtools.build.lib.syntax.Label;
+
+/**
+ * Record errors, such as missing package/target or rules containing errors,
+ * encountered during visitation. Emit an error message upon encountering
+ * missing edges
+ *
+ * The accessor {@link #hasErrors}) may not be called until the concurrent phase
+ * is over, i.e. all external calls to visit() methods have completed.
+ */
+@ThreadSafety.ConditionallyThreadSafe // condition: only call hasErrors
+                                      // once the visitation is complete.
+class ErrorPrintingTargetEdgeErrorObserver extends TargetEdgeErrorObserver {
+
+  private final EventHandler eventHandler;
+
+  /**
+   * @param eventHandler eventHandler to route exceptions to as errors.
+   */
+  public ErrorPrintingTargetEdgeErrorObserver(EventHandler eventHandler) {
+    this.eventHandler = eventHandler;
+  }
+
+  @ThreadSafety.ThreadSafe
+  @Override
+  public void missingEdge(Target target, Label label, NoSuchThingException e) {
+    eventHandler.handle(Event.error(TargetUtils.getLocationMaybe(target),
+        TargetUtils.formatMissingEdge(target, label, e)));
+    super.missingEdge(target, label, e);
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/query2/FakeSubincludeTarget.java b/src/main/java/com/google/devtools/build/lib/query2/FakeSubincludeTarget.java
new file mode 100644
index 0000000000..f1a6469e19
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/query2/FakeSubincludeTarget.java
@@ -0,0 +1,86 @@
+// Copyright 2014 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.collect.ImmutableSet;
+import com.google.devtools.build.lib.events.Location;
+import com.google.devtools.build.lib.packages.ConstantRuleVisibility;
+import com.google.devtools.build.lib.packages.License;
+import com.google.devtools.build.lib.packages.Package;
+import com.google.devtools.build.lib.packages.Rule;
+import com.google.devtools.build.lib.packages.RuleVisibility;
+import com.google.devtools.build.lib.packages.Target;
+import com.google.devtools.build.lib.syntax.Label;
+
+import java.util.Set;
+
+/**
+ * A fake Target - Use only so that "blaze query" can report subincluded files as Targets.
+ */
+public class FakeSubincludeTarget implements Target {
+
+  private final Label label;
+  private final Location location;
+
+  FakeSubincludeTarget(Label label, Location location) {
+    this.label = Preconditions.checkNotNull(label);
+    this.location = Preconditions.checkNotNull(location);
+  }
+
+  @Override
+  public Label getLabel() {
+    return label;
+  }
+
+  @Override
+  public String getName() {
+    return label.getName();
+  }
+
+  @Override
+  public Package getPackage() {
+    throw new UnsupportedOperationException();
+  }
+
+  @Override
+  public String getTargetKind() {
+    return "source file";
+  }
+
+  @Override
+  public Rule getAssociatedRule() {
+    return null;
+  }
+
+  @Override
+  public License getLicense() {
+    throw new UnsupportedOperationException();
+  }
+
+  @Override
+  public Location getLocation() {
+    return location;
+  }
+
+  @Override
+  public Set<License.DistributionType> getDistributions() {
+    return ImmutableSet.of();
+  }
+
+  @Override
+  public RuleVisibility getVisibility() {
+    return ConstantRuleVisibility.PUBLIC;
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/query2/LabelVisitor.java b/src/main/java/com/google/devtools/build/lib/query2/LabelVisitor.java
new file mode 100644
index 0000000000..b72e3aac52
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/query2/LabelVisitor.java
@@ -0,0 +1,481 @@
+// Copyright 2014 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.annotations.VisibleForTesting;
+import com.google.common.base.Throwables;
+import com.google.common.collect.HashMultimap;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.MapMaker;
+import com.google.common.collect.Multimaps;
+import com.google.common.collect.SetMultimap;
+import com.google.devtools.build.lib.concurrent.AbstractQueueVisitor;
+import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
+import com.google.devtools.build.lib.events.EventHandler;
+import com.google.devtools.build.lib.packages.AggregatingAttributeMapper;
+import com.google.devtools.build.lib.packages.Attribute;
+import com.google.devtools.build.lib.packages.AttributeMap;
+import com.google.devtools.build.lib.packages.InputFile;
+import com.google.devtools.build.lib.packages.NoSuchThingException;
+import com.google.devtools.build.lib.packages.OutputFile;
+import com.google.devtools.build.lib.packages.Package;
+import com.google.devtools.build.lib.packages.PackageGroup;
+import com.google.devtools.build.lib.packages.Rule;
+import com.google.devtools.build.lib.packages.Target;
+import com.google.devtools.build.lib.pkgcache.PackageProvider;
+import com.google.devtools.build.lib.pkgcache.TargetEdgeObserver;
+import com.google.devtools.build.lib.syntax.Label;
+import com.google.devtools.build.lib.util.BinaryPredicate;
+
+import java.util.Collection;
+import java.util.concurrent.ConcurrentMap;
+import java.util.concurrent.TimeUnit;
+import java.util.concurrent.atomic.AtomicBoolean;
+
+/**
+ * <p>Visit the transitive closure of a label. Primarily used to "fault in"
+ * packages to the packageProvider and ensure the necessary targets exists, in
+ * advance of the configuration step, which is intolerant of missing
+ * packages/targets.
+ *
+ * <p>LabelVisitor loads packages concurrently where possible, to increase I/O
+ * parallelism.  However, the public interface is not thread-safe: calls to
+ * public methods should not be made concurrently.
+ *
+ * <p>LabelVisitor is stateful: It remembers the previous visitation and can
+ * check its validity on subsequent calls to sync() instead of doing the normal
+ * visitation.
+ *
+ * <p>TODO(bazel-team): (2009) a small further optimization could be achieved if we
+ * create tasks at the package (not individual label) level, since package
+ * loading is the expensive step.  This would require additional bookkeeping to
+ * maintain the list of labels that we need to visit once a package becomes
+ * available.  Profiling suggests that there is still a potential benefit to be
+ * gained: when the set of packages is known a-priori, loading a set of packages
+ * that took 20 seconds can be done under 5 in the sequential case or 7 in the
+ * current (parallel) case.
+ *
+ * <h4>Concurrency</h4>
+ *
+ * <p>The sync() methods of this class is thread-compatible. The accessor
+ * ({@link #hasVisited} and similar must not be called until the concurrent phase
+ * is over, i.e. all external calls to visit() methods have completed.
+ */
+final class LabelVisitor {
+
+  /**
+   * Attributes of a visitation which determine whether it is up-to-date or not.
+   */
+  private class VisitationAttributes {
+    private Collection<Target> targetsToVisit;
+    private boolean success = false;
+    private boolean visitSubincludes = true;
+    private int maxDepth = 0;
+
+    /**
+     * Returns true if and only if this visitation attribute is still up-to-date.
+     */
+    boolean current() {
+      return targetsToVisit.equals(lastVisitation.targetsToVisit)
+          && maxDepth <= lastVisitation.maxDepth
+          && visitSubincludes == lastVisitation.visitSubincludes;
+    }
+  }
+
+  /*
+   * Interrupts during the loading phase ===================================
+   *
+   * Bazel can be interrupted in the middle of the loading phase. The mechanics
+   * of this are far from trivial, so there is an explanation of how they are
+   * supposed to work. For a description how the same thing works in the
+   * execution phase, see ParallelBuilder.java .
+   *
+   * The sequence of events that happen when the user presses Ctrl-C is the
+   * following:
+   *
+   * 1. A SIGINT gets delivered to the Bazel client process.
+   *
+   * 2. The client process delivers the SIGINT to the server process.
+   *
+   * 3. The interruption state of the main thread is set to true.
+   *
+   * 4. Sooner or later, this results in an InterruptedException being thrown.
+   * Usually this takes place because the main thread is interrupted during
+   * AbstractQueueVisitor.awaitTermination(). The only exception to this is when
+   * the interruption occurs during the loading of a package of a label
+   * specified on the command line; in this case, the InterruptedException is
+   * thrown during the loading of an individual package (see below where this
+   * can occur)
+   *
+   * 5. The main thread calls ThreadPoolExecutor.shutdown(), which in turn
+   * interrupts every worker thread. Then the main thread waits for their
+   * termination.
+   *
+   * 6. An InterruptedException is thrown during the loading of an individual
+   * package in the worker threads.
+   *
+   * 7. All worker threads terminate.
+   *
+   * 8. An InterruptedException is thrown from
+   * AbstractQueueVisitor.awaitTermination()
+   *
+   * 9. This exception causes the execution of the currently running command to
+   * terminate prematurely.
+   *
+   * The interruption of the loading of an individual package can happen in two
+   * different ways depending on whether Python preprocessing is in effect or
+   * not.
+   *
+   * If there is no Python preprocessing:
+   *
+   * 1. We periodically check the interruption state of the thread in
+   * UnixGlob.reallyGlob(). If it is interrupted, an InterruptedException is
+   * thrown.
+   *
+   * 2. The stack is unwound until we are out of the part of the call stack
+   * responsible for package loading. This either means that the worker thread
+   * terminates or that the label parsing terminates if the package that is
+   * being loaded was specified on the command line.
+   *
+   * If there is Python preprocessing, events are a bit more complicated. In
+   * this case, the real work happens on the thread the Python preprocessor is
+   * called from, but in a bit more convoluted way: a new thread is spawned by
+   * to handle the input from the Python process and
+   * the output to the Python process is handled on the main thread. The reading
+   * thread parses requests from the preprocessor, and passes them using a queue
+   * to the writing thread (that is, the main thread), so that we can do the
+   * work there. This is important because this way, we don't have any work that
+   * we need to interrupt in a thread that is not spawned by us. So:
+   *
+   * 1. The interrupted state of the main thread is set.
+   *
+   * 2. This results in an InterruptedException during the execution of the task
+   * in PythonStdinInputStream.getNextMessage().
+   *
+   * 3. We exit from RequestParser.Request.run() prematurely, set a flag to
+   * signal that we were interrupted, and throw an InterruptedIOException.
+   *
+   * 4. The Python child process and reading thread are terminated.
+   *
+   * 5. Based on the flag we set in step 3, we realize that the termination was
+   * due to an interruption, and an InterruptedException is thrown. This can
+   * either raise an AbnormalTerminationException, or make Command.execute()
+   * return normally, so we check for both cases.
+   *
+   * 6. This InterruptedException causes the loading of the package to terminate
+   * prematurely.
+   *
+   * Life is not simple.
+   */
+  private final PackageProvider packageProvider;
+  private final BinaryPredicate<Rule, Attribute> edgeFilter;
+  private final SetMultimap<Package, Target> visitedMap =
+      Multimaps.synchronizedSetMultimap(HashMultimap.<Package, Target>create());
+  private final ConcurrentMap<Label, Integer> visitedTargets = new MapMaker().makeMap();
+
+  private VisitationAttributes lastVisitation;
+
+  /**
+   * Constant for limiting the permitted depth of recursion.
+   */
+  private static final int RECURSION_LIMIT = 100;
+
+  /**
+   * Construct a LabelVisitor.
+   *
+   * @param packageProvider how to resolve labels to targets.
+   * @param edgeFilter which edges may be traversed.
+   */
+  public LabelVisitor(PackageProvider packageProvider,
+                      BinaryPredicate<Rule, Attribute> edgeFilter) {
+    this.packageProvider = packageProvider;
+    this.lastVisitation = new VisitationAttributes();
+    this.edgeFilter = edgeFilter;
+  }
+
+  boolean syncWithVisitor(EventHandler eventHandler, Collection<Target> targetsToVisit,
+      boolean keepGoing, int parallelThreads, int maxDepth, TargetEdgeObserver... observers)
+          throws InterruptedException {
+    VisitationAttributes nextVisitation = new VisitationAttributes();
+    nextVisitation.targetsToVisit = targetsToVisit;
+    nextVisitation.maxDepth = maxDepth;
+
+    if (!lastVisitation.success || !nextVisitation.current()) {
+      try {
+        nextVisitation.success = redoVisitation(eventHandler, nextVisitation, keepGoing,
+            parallelThreads, maxDepth, observers);
+        return nextVisitation.success;
+      } finally {
+        lastVisitation = nextVisitation;
+      }
+    } else {
+      return true;
+    }
+  }
+
+  // Does a bounded transitive visitation starting at the given top-level targets.
+  private boolean redoVisitation(EventHandler eventHandler,
+                                 VisitationAttributes visitation,
+                                 boolean keepGoing,
+                                 int parallelThreads,
+                                 int maxDepth,
+                                 TargetEdgeObserver... observers)
+      throws InterruptedException {
+    visitedMap.clear();
+    visitedTargets.clear();
+
+    Visitor visitor = new Visitor(eventHandler, keepGoing, parallelThreads, maxDepth, observers);
+
+    Throwable uncaught = null;
+    boolean result;
+    try {
+      visitor.visitTargets(visitation.targetsToVisit);
+    } catch (Throwable t) {
+      visitor.stopNewActions();
+      uncaught = t;
+    } finally {
+      // Run finish() in finally block to ensure we don't leak threads on exceptions.
+      result = visitor.finish();
+    }
+    Throwables.propagateIfPossible(uncaught);
+    return result;
+  }
+
+  boolean hasVisited(Label target) {
+    return visitedTargets.containsKey(target);
+  }
+
+  @VisibleForTesting class Visitor extends AbstractQueueVisitor {
+
+    private final static String THREAD_NAME = "LabelVisitor";
+
+    private final EventHandler eventHandler;
+    private final boolean keepGoing;
+    private final int maxDepth;
+    private final Iterable<TargetEdgeObserver> observers;
+    private final TargetEdgeErrorObserver errorObserver;
+    private final AtomicBoolean stopNewActions = new AtomicBoolean(false);
+    private static final boolean CONCURRENT = true;
+
+
+    public Visitor(EventHandler eventHandler, boolean keepGoing, int parallelThreads,
+                   int maxDepth, TargetEdgeObserver... observers) {
+      // Observing the loading phase of a typical large package (with all subpackages) shows
+      // maximum thread-level concurrency of ~20. Limiting the total number of threads to 200 is
+      // therefore conservative and should help us avoid hitting native limits.
+      super(CONCURRENT, parallelThreads, parallelThreads, 1L, TimeUnit.SECONDS, !keepGoing,
+          THREAD_NAME);
+      this.eventHandler = eventHandler;
+      this.maxDepth = maxDepth;
+      this.errorObserver = new TargetEdgeErrorObserver();
+      ImmutableList.Builder<TargetEdgeObserver> builder = ImmutableList.builder();
+      for (TargetEdgeObserver observer : observers) {
+        builder.add(observer);
+      }
+      builder.add(errorObserver);
+      this.observers = builder.build();
+      this.keepGoing = keepGoing;
+    }
+
+    /**
+     * Visit the specified labels and follow the transitive closure of their
+     * outbound dependencies.
+     *
+     * @param targets the targets to visit
+     */
+    @ThreadSafe
+    public void visitTargets(Iterable<Target> targets) {
+      for (Target target : targets) {
+        visit(null, null, target, 0, 0);
+      }
+    }
+
+    @ThreadSafe
+    public boolean finish() throws InterruptedException {
+      work(true);
+      return !errorObserver.hasErrors();
+    }
+
+    @Override
+    protected boolean blockNewActions() {
+      return (!keepGoing && errorObserver.hasErrors()) || super.blockNewActions() ||
+          stopNewActions.get();
+    }
+
+    public void stopNewActions() {
+      stopNewActions.set(true);
+    }
+
+    private void enqueueTarget(
+        final Target from, final Attribute attr, final Label label, final int depth,
+        final int count) {
+      // Don't perform the targetProvider lookup if at the maximum depth already.
+      if (depth >= maxDepth) {
+        return;
+      } else if (attr != null && from instanceof Rule) {
+        if (!edgeFilter.apply((Rule) from, attr)) {
+          return;
+        }
+      }
+
+      // Avoid thread-related overhead when not crossing packages.
+      // Can start a new thread when count reaches 100, to prevent infinite recursion.
+      if (from != null && from.getLabel().getPackageFragment() == label.getPackageFragment() &&
+          !blockNewActions() && count < RECURSION_LIMIT) {
+        newVisitRunnable(from, attr, label, depth, count + 1).run();
+      } else {
+        enqueue(newVisitRunnable(from, attr, label, depth, 0));
+      }
+    }
+
+    private Runnable newVisitRunnable(final Target from, final Attribute attr, final Label label,
+        final int depth, final int count) {
+      return new Runnable () {
+        @Override
+        public void run() {
+          try {
+            Target target = packageProvider.getTarget(eventHandler, label);
+            if (target == null) {
+              // Let target visitation continue so we can discover additional unknown inputs.
+              return;
+            }
+            visit(from, attr, packageProvider.getTarget(eventHandler, label), depth + 1, count);
+          } catch (NoSuchThingException e) {
+            observeError(from, label, e);
+          } catch (InterruptedException e) {
+            Thread.currentThread().interrupt();
+          }
+        }
+      };
+    }
+
+    private void visitTargetVisibility(Target target, int depth, int count) {
+      Attribute attribute = null;
+      if (target instanceof Rule) {
+        attribute = ((Rule) target).getRuleClassObject().getAttributeByName("visibility");
+      }
+
+      for (Label label : target.getVisibility().getDependencyLabels()) {
+        enqueueTarget(target, attribute, label, depth, count);
+      }
+    }
+
+    /**
+     * Visit all the labels in a given rule.
+     *
+     * <p>Called in a worker thread if CONCURRENT.
+     *
+     * @param rule the rule to visit
+     */
+    @ThreadSafe
+    private void visitRule(final Rule rule, final int depth, final int count) {
+      // Follow all labels defined by this rule:
+      AggregatingAttributeMapper.of(rule).visitLabels(new AttributeMap.AcceptsLabelAttribute() {
+        @Override
+        public void acceptLabelAttribute(Label label, Attribute attribute) {
+          enqueueTarget(rule, attribute, label, depth, count);
+        }
+      });
+    }
+
+    @ThreadSafe
+    private void visitPackageGroup(PackageGroup packageGroup, int depth, int count) {
+      for (final Label include : packageGroup.getIncludes()) {
+        enqueueTarget(packageGroup, null, include, depth, count);
+      }
+    }
+
+    /**
+     * Visits the target and its package.
+     *
+     * <p>Potentially blocking invocations into the package cache are
+     * enqueued in the worker pool if CONCURRENT.
+     */
+    private void visit(
+        Target from, Attribute attribute, final Target target, int depth, int count) {
+      if (depth > maxDepth) {
+        return;
+      }
+
+      if (from != null) {
+        observeEdge(from, attribute, target);
+      }
+
+      visitedMap.put(target.getPackage(), target);
+      visitTargetNode(target, depth, count);
+    }
+
+    /**
+     * Visit the specified target.
+     * Called in a worker thread if CONCURRENT.
+     *
+     * @param target the target to visit
+     */
+    private void visitTargetNode(Target target, int depth, int count) {
+      Integer minTargetDepth = visitedTargets.putIfAbsent(target.getLabel(), depth);
+      if (minTargetDepth != null) {
+        // The target was already visited at a greater depth.
+        // The closure we are about to build is therefore a subset of what
+        // has already been built, and we can skip it.
+        // Also special case MAX_VALUE, where we never want to revisit targets.
+        // (This avoids loading phase overhead outside of queries).
+        if (maxDepth == Integer.MAX_VALUE || minTargetDepth <= depth) {
+          return;
+        }
+        // Check again in case it was overwritten by another thread.
+        synchronized (visitedTargets) {
+          if (visitedTargets.get(target.getLabel()) <= depth) {
+            return;
+          }
+          visitedTargets.put(target.getLabel(), depth);
+        }
+      }
+
+      observeNode(target);
+      if (target instanceof OutputFile) {
+        Rule rule = ((OutputFile) target).getGeneratingRule();
+        observeEdge(target, null, rule);
+        // This is the only recursive call to visit which doesn't pass through enqueueTarget().
+        visit(null, null, rule, depth + 1, count + 1);
+        visitTargetVisibility(target, depth, count);
+      } else if (target instanceof InputFile) {
+        visitTargetVisibility(target, depth, count);
+      } else if (target instanceof Rule) {
+        visitTargetVisibility(target, depth, count);
+        visitRule((Rule) target, depth, count);
+      } else if (target instanceof PackageGroup) {
+        visitPackageGroup((PackageGroup) target, depth, count);
+      }
+    }
+
+    private void observeEdge(Target from, Attribute attribute, Target to) {
+      for (TargetEdgeObserver observer : observers) {
+        observer.edge(from, attribute, to);
+      }
+    }
+
+    private void observeNode(Target target) {
+      for (TargetEdgeObserver observer : observers) {
+        observer.node(target);
+      }
+    }
+
+    private void observeError(Target from, Label label, NoSuchThingException e) {
+      for (TargetEdgeObserver observer : observers) {
+        observer.missingEdge(from, label, e);
+      }
+    }
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/query2/SkyframeQueryEnvironment.java b/src/main/java/com/google/devtools/build/lib/query2/SkyframeQueryEnvironment.java
new file mode 100644
index 0000000000..318d844aa6
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/query2/SkyframeQueryEnvironment.java
@@ -0,0 +1,58 @@
+// Copyright 2014 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.collect.ImmutableSet;
+import com.google.devtools.build.lib.events.EventHandler;
+import com.google.devtools.build.lib.packages.Target;
+import com.google.devtools.build.lib.pkgcache.PackageProvider;
+import com.google.devtools.build.lib.pkgcache.TargetPatternEvaluator;
+import com.google.devtools.build.lib.pkgcache.TransitivePackageLoader;
+import com.google.devtools.build.lib.query2.engine.QueryException;
+import com.google.devtools.build.lib.syntax.Label;
+
+import java.util.Set;
+
+/**
+ * A BlazeQueryEnvironment for Skyframe builds. Currently, this is used to preload transitive
+ * closures of targets quickly.
+ */
+public final class SkyframeQueryEnvironment extends BlazeQueryEnvironment {
+
+  private final TransitivePackageLoader transitivePackageLoader;
+  private static final int MAX_DEPTH_FULL_SCAN_LIMIT = 20;
+
+  public SkyframeQueryEnvironment(
+      TransitivePackageLoader transitivePackageLoader, PackageProvider packageProvider,
+      TargetPatternEvaluator targetPatternEvaluator, boolean keepGoing, int loadingPhaseThreads,
+      EventHandler eventHandler, Set<Setting> settings, Iterable<QueryFunction> functions) {
+    super(packageProvider, targetPatternEvaluator, keepGoing, loadingPhaseThreads, eventHandler,
+        settings, functions);
+    this.transitivePackageLoader = transitivePackageLoader;
+  }
+
+  @Override
+  protected void preloadTransitiveClosure(Set<Target> targets, int maxDepth) throws QueryException {
+    if (maxDepth >= MAX_DEPTH_FULL_SCAN_LIMIT) {
+      // Only do the full visitation if "maxDepth" is large enough. Otherwise, the benefits of
+      // preloading will be outweighed by the cost of doing more work than necessary.
+      try {
+        transitivePackageLoader.sync(eventHandler, targets, ImmutableSet.<Label>of(), keepGoing,
+            loadingPhaseThreads, -1);
+      } catch (InterruptedException e) {
+        throw new QueryException("interrupted");
+      }
+    }
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/query2/TargetEdgeErrorObserver.java b/src/main/java/com/google/devtools/build/lib/query2/TargetEdgeErrorObserver.java
new file mode 100644
index 0000000000..5a075d2c3c
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/query2/TargetEdgeErrorObserver.java
@@ -0,0 +1,83 @@
+// Copyright 2014 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.devtools.build.lib.concurrent.ThreadSafety;
+import com.google.devtools.build.lib.packages.Attribute;
+import com.google.devtools.build.lib.packages.NoSuchThingException;
+import com.google.devtools.build.lib.packages.Rule;
+import com.google.devtools.build.lib.packages.Target;
+import com.google.devtools.build.lib.pkgcache.TargetEdgeObserver;
+import com.google.devtools.build.lib.syntax.Label;
+
+/**
+ * Record errors, such as missing package/target or rules containing errors,
+ * encountered during visitation. Emit an error message upon encountering
+ * missing edges
+ *
+ * The accessor {@link #hasErrors}) may not be called until the concurrent phase
+ * is over, i.e. all external calls to visit() methods have completed.
+ *
+ * If you need to report errors to the console during visitation, use the
+ * subclass {@link com.google.devtools.build.lib.query2.ErrorPrintingTargetEdgeErrorObserver}.
+ */
+class TargetEdgeErrorObserver implements TargetEdgeObserver {
+
+  /**
+   * True iff errors were encountered.  Note, may be set to "true" during the
+   * concurrent phase.  Volatile, because it is assigned by worker threads and
+   * read by the main thread without monitor synchronization.
+   */
+  private volatile boolean hasErrors = false;
+
+  /**
+   * Reports an unresolved label error and records the fact that an error was
+   * encountered.
+   * @param target the target that referenced the unresolved label
+   * @param label the label that could not be resolved
+   * @param e the exception that was thrown when the label could not be resolved
+   */
+  @ThreadSafety.ThreadSafe
+  @Override
+  public void missingEdge(Target target, Label label, NoSuchThingException e) {
+    hasErrors = true;
+  }
+
+  /**
+   * Returns true iff any errors (such as missing targets or packages, or rules
+   * with errors) have been encountered during any work.
+   *
+   * <p>Not thread-safe; do not call during visitation.
+   *
+   *  @return true iff no errors (such as missing targets or packages, or rules
+   *              with errors) have been encountered during any work.
+   */
+  public boolean hasErrors() {
+    return hasErrors;
+  }
+
+  @Override
+  public void edge(Target from, Attribute attribute, Target to) {
+    // No-op.
+  }
+
+  @Override
+  public void node(Target node) {
+    if (node.getPackage().containsErrors() ||
+        ((node instanceof Rule) && ((Rule) node).containsErrors())) {
+      this.hasErrors = true;  // Note, this is thread-safe.
+    }
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/AllPathsFunction.java b/src/main/java/com/google/devtools/build/lib/query2/engine/AllPathsFunction.java
new file mode 100644
index 0000000000..d2d5f05f9c
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/AllPathsFunction.java
@@ -0,0 +1,96 @@
+// Copyright 2014 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.engine;
+
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Sets;
+import com.google.devtools.build.lib.query2.engine.QueryEnvironment.Argument;
+import com.google.devtools.build.lib.query2.engine.QueryEnvironment.ArgumentType;
+import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryFunction;
+
+import java.util.HashSet;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Set;
+
+/**
+ * Implementation of the <code>allpaths()</code> function.
+ */
+public class AllPathsFunction implements QueryFunction {
+  AllPathsFunction() {
+  }
+
+  @Override
+  public String getName() {
+    return "allpaths";
+  }
+
+  @Override
+  public int getMandatoryArguments() {
+    return 2;
+  }
+
+  @Override
+  public List<ArgumentType> getArgumentTypes() {
+    return ImmutableList.of(ArgumentType.EXPRESSION, ArgumentType.EXPRESSION);
+  }
+
+  @Override
+  public <T> Set<T> eval(QueryEnvironment<T> env, QueryExpression expression, List<Argument> args)
+      throws QueryException {
+    QueryExpression from = args.get(0).getExpression();
+    QueryExpression to = args.get(1).getExpression();
+
+    Set<T> fromValue = from.eval(env);
+    Set<T> toValue = to.eval(env);
+
+    // Algorithm: compute "reachableFromX", the forward transitive closure of
+    // the "from" set, then find the intersection of "reachableFromX" with the
+    // reverse transitive closure of the "to" set.  The reverse transitive
+    // closure and intersection operations are interleaved for efficiency.
+    // "result" holds the intersection.
+
+    env.buildTransitiveClosure(expression, fromValue, Integer.MAX_VALUE);
+
+    Set<T> reachableFromX = env.getTransitiveClosure(fromValue);
+    Set<T> result = intersection(reachableFromX, toValue);
+    LinkedList<T> worklist = new LinkedList<>(result);
+
+    T n;
+    while ((n = worklist.poll()) != null) {
+      for (T np : env.getReverseDeps(n)) {
+        if (reachableFromX.contains(np)) {
+          if (result.add(np)) {
+            worklist.add(np);
+          }
+        }
+      }
+    }
+    return result;
+  }
+
+  /**
+   * Returns a (new, mutable, unordered) set containing the intersection of the
+   * two specified sets.
+   */
+  private static <T> Set<T> intersection(Set<T> x, Set<T> y) {
+    Set<T> result = new HashSet<>();
+    if (x.size() > y.size()) {
+      Sets.intersection(y, x).copyInto(result);
+    } else {
+      Sets.intersection(x, y).copyInto(result);
+    }
+    return result;
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/AttrFunction.java b/src/main/java/com/google/devtools/build/lib/query2/engine/AttrFunction.java
new file mode 100644
index 0000000000..054cf78b55
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/AttrFunction.java
@@ -0,0 +1,78 @@
+// Copyright 2014 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.engine;
+
+import com.google.common.collect.ImmutableList;
+import com.google.devtools.build.lib.query2.engine.QueryEnvironment.Argument;
+import com.google.devtools.build.lib.query2.engine.QueryEnvironment.ArgumentType;
+
+import java.util.List;
+
+/**
+ * An attr(attribute, pattern, argument) filter expression, which computes
+ * the set of subset of nodes in 'argument' which correspond to rules with
+ * defined attribute 'attribute' with attribute value matching the unanchored
+ * regexp 'pattern'. For list attributes, the attribute value will be defined as
+ * a usual List.toString() representation (using '[' as first character, ']' as
+ * last character and ", " as a delimiter between multiple values). Also, all
+ * label-based attributes will use fully-qualified label names instead of
+ * original value specified in the BUILD file.
+ *
+ * <pre>expr ::= ATTR '(' ATTRNAME ',' WORD ',' expr ')'</pre>
+ *
+ * Examples
+ * <pre>
+ * attr(linkshared,1,//project/...)    find all rules under in the //project/... that
+ *                                 have attribute linkshared set to 1.
+ * </pre>
+ */
+class AttrFunction extends RegexFilterExpression {
+  AttrFunction() {
+  }
+
+  @Override
+  public String getName() {
+    return "attr";
+  }
+
+  @Override
+  protected String getPattern(List<Argument> args) {
+    return args.get(1).getWord();
+  }
+
+  @Override
+  public int getMandatoryArguments() {
+    return 3;
+  }
+
+  @Override
+  public List<ArgumentType> getArgumentTypes() {
+    return ImmutableList.of(ArgumentType.WORD, ArgumentType.WORD, ArgumentType.EXPRESSION);
+  }
+
+  @Override
+  protected <T> String getFilterString(QueryEnvironment<T> env, List<Argument> args, T target) {
+    throw new IllegalStateException(
+        "The 'attr' regex filter gets its match values directly from getFilterStrings");
+  }
+
+  @Override
+  protected <T> Iterable<String> getFilterStrings(QueryEnvironment<T> env,
+      List<Argument> args, T target) {
+    if (env.getAccessor().isRule(target)) {
+      return env.getAccessor().getAttrAsString(target, args.get(0).getWord());
+    }
+    return ImmutableList.of();
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/BinaryOperatorExpression.java b/src/main/java/com/google/devtools/build/lib/query2/engine/BinaryOperatorExpression.java
new file mode 100644
index 0000000000..e5e600f831
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/BinaryOperatorExpression.java
@@ -0,0 +1,93 @@
+// Copyright 2014 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.engine;
+
+import com.google.common.base.Preconditions;
+import com.google.common.collect.ImmutableList;
+
+import java.util.Collection;
+import java.util.LinkedHashSet;
+import java.util.List;
+import java.util.Set;
+
+/**
+ * A binary algebraic set operation.
+ *
+ * <pre>
+ * expr ::= expr (INTERSECT expr)+
+ *        | expr ('^' expr)+
+ *        | expr (UNION expr)+
+ *        | expr ('+' expr)+
+ *        | expr (EXCEPT expr)+
+ *        | expr ('-' expr)+
+ * </pre>
+ */
+class BinaryOperatorExpression extends QueryExpression {
+
+  private final Lexer.TokenKind operator; // ::= INTERSECT/CARET | UNION/PLUS | EXCEPT/MINUS
+  private final ImmutableList<QueryExpression> operands;
+
+  BinaryOperatorExpression(Lexer.TokenKind operator,
+                           List<QueryExpression> operands) {
+    Preconditions.checkState(operands.size() > 1);
+    this.operator = operator;
+    this.operands = ImmutableList.copyOf(operands);
+  }
+
+  @Override
+  public <T> Set<T> eval(QueryEnvironment<T> env) throws QueryException {
+    Set<T> lhsValue = new LinkedHashSet<>(operands.get(0).eval(env));
+
+    for (int i = 1; i < operands.size(); i++) {
+      Set<T> rhsValue = operands.get(i).eval(env);
+      switch (operator) {
+        case INTERSECT:
+        case CARET:
+          lhsValue.retainAll(rhsValue);
+          break;
+        case UNION:
+        case PLUS:
+          lhsValue.addAll(rhsValue);
+          break;
+        case EXCEPT:
+        case MINUS:
+          lhsValue.removeAll(rhsValue);
+          break;
+        default:
+          throw new IllegalStateException("operator=" + operator);
+      }
+    }
+    return lhsValue;
+  }
+
+  @Override
+  public void collectTargetPatterns(Collection<String> literals) {
+    for (QueryExpression subExpression : operands) {
+      subExpression.collectTargetPatterns(literals);
+    }
+  }
+
+  @Override
+  public String toString() {
+    StringBuilder result = new StringBuilder();
+    for (int i = 1; i < operands.size(); i++) {
+      result.append("(");
+    }
+    result.append(operands.get(0));
+    for (int i = 1; i < operands.size(); i++) {
+      result.append(" " + operator.getPrettyName() + " " + operands.get(i) + ")");
+    }
+    return result.toString();
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/BlazeQueryEvalResult.java b/src/main/java/com/google/devtools/build/lib/query2/engine/BlazeQueryEvalResult.java
new file mode 100644
index 0000000000..7f2060f176
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/BlazeQueryEvalResult.java
@@ -0,0 +1,36 @@
+// Copyright 2014 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.engine;
+
+import com.google.common.base.Preconditions;
+import com.google.devtools.build.lib.graph.Digraph;
+
+import java.util.Set;
+
+/** {@link QueryEvalResult} along with a digraph giving the structure of the results. */
+public class BlazeQueryEvalResult<T> extends QueryEvalResult<T> {
+
+  private final Digraph<T> graph;
+
+  public BlazeQueryEvalResult(boolean success, Set<T> resultSet, Digraph<T> graph) {
+    super(success, resultSet);
+    this.graph = Preconditions.checkNotNull(graph);
+  }
+
+  /** Returns the result as a directed graph over elements. */
+  public Digraph<T> getResultGraph() {
+    return graph.extractSubgraph(resultSet);
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/BuildFilesFunction.java b/src/main/java/com/google/devtools/build/lib/query2/engine/BuildFilesFunction.java
new file mode 100644
index 0000000000..d606a6acb3
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/BuildFilesFunction.java
@@ -0,0 +1,56 @@
+// Copyright 2014 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.engine;
+
+import com.google.common.collect.ImmutableList;
+import com.google.devtools.build.lib.query2.engine.QueryEnvironment.Argument;
+import com.google.devtools.build.lib.query2.engine.QueryEnvironment.ArgumentType;
+import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryFunction;
+
+import java.util.List;
+import java.util.Set;
+
+/**
+ * A buildfiles(x) query expression, which computes the set of BUILD files and
+ * subincluded files for each target in set x.  The result is unordered.  This
+ * operator is typically used for determinining what files or packages to check
+ * out.
+ *
+ * <pre>expr ::= BUILDFILES '(' expr ')'</pre>
+ */
+class BuildFilesFunction implements QueryFunction {
+  BuildFilesFunction() {
+  }
+
+  @Override
+  public String getName() {
+    return "buildfiles";
+  }
+
+  @Override
+  public <T> Set<T> eval(QueryEnvironment<T> env, QueryExpression expression, List<Argument> args)
+      throws QueryException {
+    return env.getBuildFiles(expression, args.get(0).getExpression().eval(env));
+  }
+
+  @Override
+  public int getMandatoryArguments() {
+    return 1;
+  }
+
+  @Override
+  public List<ArgumentType> getArgumentTypes() {
+    return ImmutableList.of(ArgumentType.EXPRESSION);
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/DepsFunction.java b/src/main/java/com/google/devtools/build/lib/query2/engine/DepsFunction.java
new file mode 100644
index 0000000000..2b693eb8a7
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/DepsFunction.java
@@ -0,0 +1,88 @@
+// Copyright 2014 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.engine;
+
+import com.google.common.collect.ImmutableList;
+import com.google.devtools.build.lib.query2.engine.QueryEnvironment.Argument;
+import com.google.devtools.build.lib.query2.engine.QueryEnvironment.ArgumentType;
+import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryFunction;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.LinkedHashSet;
+import java.util.List;
+import java.util.Set;
+
+/**
+ * A "deps" query expression, which computes the dependencies of the argument. An optional
+ * integer-literal second argument may be specified; its value bounds the search from the arguments.
+ *
+ * <pre>expr ::= DEPS '(' expr ')'</pre>
+ * <pre>       | DEPS '(' expr ',' WORD ')'</pre>
+ */
+final class DepsFunction implements QueryFunction {
+  DepsFunction() {
+  }
+
+  @Override
+  public String getName() {
+    return "deps";
+  }
+
+  @Override
+  public int getMandatoryArguments() {
+    return 1;  // last argument is optional
+  }
+
+  @Override
+  public List<ArgumentType> getArgumentTypes() {
+    return ImmutableList.of(ArgumentType.EXPRESSION, ArgumentType.INTEGER);
+  }
+
+  /**
+   * Breadth-first search from the arguments.
+   */
+  @Override
+  public <T> Set<T> eval(QueryEnvironment<T> env, QueryExpression expression, List<Argument> args)
+      throws QueryException {
+    Set<T> argumentValue = args.get(0).getExpression().eval(env);
+    int depthBound = args.size() > 1 ? args.get(1).getInteger() : Integer.MAX_VALUE;
+    env.buildTransitiveClosure(expression, argumentValue, depthBound);
+
+    Set<T> visited = new LinkedHashSet<>();
+    Collection<T> current = argumentValue;
+
+    // We need to iterate depthBound + 1 times.
+    for (int i = 0; i <= depthBound; i++) {
+      List<T> next = new ArrayList<>();
+      for (T node : current) {
+        if (!visited.add(node)) {
+          // Already visited; if we see a node in a later round, then we don't need to visit it
+          // again, because the depth at which we see it at must be greater than or equal to the
+          // last visit.
+          continue;
+        }
+
+        next.addAll(env.getFwdDeps(node));
+      }
+      if (next.isEmpty()) {
+        // Exit when there are no more nodes to visit.
+        break;
+      }
+      current = next;
+    }
+
+    return visited;
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/FilterFunction.java b/src/main/java/com/google/devtools/build/lib/query2/engine/FilterFunction.java
new file mode 100644
index 0000000000..bd8995082e
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/FilterFunction.java
@@ -0,0 +1,63 @@
+// Copyright 2014 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.engine;
+
+import com.google.common.collect.ImmutableList;
+import com.google.devtools.build.lib.query2.engine.QueryEnvironment.Argument;
+import com.google.devtools.build.lib.query2.engine.QueryEnvironment.ArgumentType;
+
+import java.util.List;
+
+/**
+ * A label(pattern, argument) filter expression, which computes the set of subset
+ * of nodes in 'argument' whose label matches the unanchored regexp 'pattern'.
+ *
+ * <pre>expr ::= FILTER '(' WORD ',' expr ')'</pre>
+ *
+ * Example patterns:
+ * <pre>
+ * '//third_party'      Match all targets in the //third_party/...
+ *                      (equivalent to 'intersect //third_party/...)
+ * '\.jar$'               Match all *.jar targets.
+ * </pre>
+ */
+class FilterFunction extends RegexFilterExpression {
+  FilterFunction() {
+  }
+
+  @Override
+  public String getName() {
+    return "filter";
+  }
+
+  @Override
+  protected String getPattern(List<Argument> args) {
+    return args.get(0).getWord();
+  }
+
+  @Override
+  public int getMandatoryArguments() {
+    return 2;
+  }
+
+  @Override
+  public List<ArgumentType> getArgumentTypes() {
+    return ImmutableList.of(ArgumentType.WORD, ArgumentType.EXPRESSION);
+  }
+
+  @Override
+  protected <T> String getFilterString(QueryEnvironment<T> env, List<Argument> args, T target) {
+    return env.getAccessor().getLabel(target);
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/FunctionExpression.java b/src/main/java/com/google/devtools/build/lib/query2/engine/FunctionExpression.java
new file mode 100644
index 0000000000..62734fd07e
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/FunctionExpression.java
@@ -0,0 +1,59 @@
+// Copyright 2014 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.engine;
+
+import com.google.common.base.Functions;
+import com.google.common.base.Joiner;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Iterables;
+import com.google.devtools.build.lib.query2.engine.QueryEnvironment.Argument;
+import com.google.devtools.build.lib.query2.engine.QueryEnvironment.ArgumentType;
+import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryFunction;
+
+import java.util.Collection;
+import java.util.List;
+import java.util.Set;
+
+/**
+ * A query expression for user-defined query functions.
+ */
+public class FunctionExpression extends QueryExpression {
+  QueryFunction function;
+  List<Argument> args;
+
+  public FunctionExpression(QueryFunction function, List<Argument> args) {
+    this.function = function;
+    this.args = ImmutableList.copyOf(args);
+  }
+
+  @Override
+  public <T> Set<T> eval(QueryEnvironment<T> env) throws QueryException {
+    return function.<T>eval(env, this, args);
+  }
+
+  @Override
+  public void collectTargetPatterns(Collection<String> literals) {
+    for (Argument arg : args) {
+      if (arg.getType() == ArgumentType.EXPRESSION) {
+        arg.getExpression().collectTargetPatterns(literals);
+      }
+    }
+  }
+
+  @Override
+  public String toString() {
+    return function.getName() +
+        "(" + Joiner.on(", ").join(Iterables.transform(args, Functions.toStringFunction())) + ")";
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/KindFunction.java b/src/main/java/com/google/devtools/build/lib/query2/engine/KindFunction.java
new file mode 100644
index 0000000000..7ae80b88db
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/KindFunction.java
@@ -0,0 +1,70 @@
+// Copyright 2014 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.engine;
+
+import com.google.common.collect.ImmutableList;
+import com.google.devtools.build.lib.query2.engine.QueryEnvironment.Argument;
+import com.google.devtools.build.lib.query2.engine.QueryEnvironment.ArgumentType;
+
+import java.util.List;
+
+/**
+ * A kind(pattern, argument) filter expression, which computes the set of subset
+ * of nodes in 'argument' whose kind matches the unanchored regexp 'pattern'.
+ *
+ * <pre>expr ::= KIND '(' WORD ',' expr ')'</pre>
+ *
+ * Example patterns:
+ * <pre>
+ * ' file'              Match all file targets.
+ * 'source file'        Match all test source file targets.
+ * 'generated file'     Match all test generated file targets.
+ * ' rule'              Match all rule targets.
+ * 'foo_*'              Match all rules starting with "foo_",
+ * 'test'               Match all test (rule) targets.
+ * </pre>
+ *
+ * Note, the space before "file" is needed to prevent unwanted matches against
+ * (e.g.) "filegroup rule".
+ */
+class KindFunction extends RegexFilterExpression {
+
+  KindFunction() {
+  }
+
+  @Override
+  public String getName() {
+    return "kind";
+  }
+
+  @Override
+  protected String getPattern(List<Argument> args) {
+    return args.get(0).getWord();
+  }
+
+  @Override
+  public int getMandatoryArguments() {
+    return 2;
+  }
+
+  @Override
+  public List<ArgumentType> getArgumentTypes() {
+    return ImmutableList.of(ArgumentType.WORD, ArgumentType.EXPRESSION);
+  }
+
+  @Override
+  protected <T> String getFilterString(QueryEnvironment<T> env, List<Argument> args, T target) {
+    return env.getAccessor().getTargetKind(target);
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/LabelsFunction.java b/src/main/java/com/google/devtools/build/lib/query2/engine/LabelsFunction.java
new file mode 100644
index 0000000000..1093d85290
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/LabelsFunction.java
@@ -0,0 +1,72 @@
+// Copyright 2014 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.engine;
+
+import com.google.common.collect.ImmutableList;
+import com.google.devtools.build.lib.query2.engine.QueryEnvironment.Argument;
+import com.google.devtools.build.lib.query2.engine.QueryEnvironment.ArgumentType;
+import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryFunction;
+
+import java.util.LinkedHashSet;
+import java.util.List;
+import java.util.Set;
+
+/**
+ * A label(attr_name, argument) expression, which computes the set of targets
+ * whose labels appear in the specified attribute of some rule in 'argument'.
+ *
+ * <pre>expr ::= LABELS '(' WORD ',' expr ')'</pre>
+ *
+ * Example:
+ * <pre>
+ *  labels(srcs, //foo)      The 'srcs' source files to the //foo rule.
+ * </pre>
+ */
+class LabelsFunction implements QueryFunction {
+  LabelsFunction() {
+  }
+
+  @Override
+  public String getName() {
+    return "labels";
+  }
+
+  @Override
+  public int getMandatoryArguments() {
+    return 2;
+  }
+
+  @Override
+  public List<ArgumentType> getArgumentTypes() {
+    return ImmutableList.of(ArgumentType.WORD, ArgumentType.EXPRESSION);
+  }
+
+  @Override
+  public <T> Set<T> eval(QueryEnvironment<T> env, QueryExpression expression, List<Argument> args)
+      throws QueryException {
+    Set<T> inputs = args.get(1).getExpression().eval(env);
+    Set<T> result = new LinkedHashSet<>();
+    String attrName = args.get(0).getWord();
+    for (T input : inputs) {
+      if (env.getAccessor().isRule(input)) {
+        List<T> targets = env.getAccessor().getLabelListAttr(expression, input, attrName,
+            "in '" + attrName + "' of rule " + env.getAccessor().getLabel(input) + ": ");
+        for (T target : targets) {
+          result.add(env.getOrCreate(target));
+        }
+      }
+    }
+    return result;
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/LetExpression.java b/src/main/java/com/google/devtools/build/lib/query2/engine/LetExpression.java
new file mode 100644
index 0000000000..3e17ccebbe
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/LetExpression.java
@@ -0,0 +1,78 @@
+// Copyright 2014 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.engine;
+
+import java.util.Collection;
+import java.util.Set;
+import java.util.regex.Pattern;
+
+/**
+ * A let expression.
+ *
+ * <pre>expr ::= LET WORD = expr IN expr</pre>
+ */
+class LetExpression extends QueryExpression {
+
+  private static final String VAR_NAME_PATTERN = "[a-zA-Z_][a-zA-Z0-9_]*$";
+
+  // Variables names may be any legal identifier in the C programming language
+  private static final Pattern NAME_PATTERN = Pattern.compile("^" + VAR_NAME_PATTERN);
+
+  // Variable references are prepended with the "$" character.
+  // A variable named "x" is referenced as "$x".
+  private static final Pattern REF_PATTERN = Pattern.compile("^\\$" + VAR_NAME_PATTERN);
+
+  static boolean isValidVarReference(String varName) {
+    return REF_PATTERN.matcher(varName).matches();
+  }
+
+  static String getNameFromReference(String reference) {
+    return reference.substring(1);
+  }
+
+  private final String varName;
+  private final QueryExpression varExpr;
+  private final QueryExpression bodyExpr;
+
+  LetExpression(String varName, QueryExpression varExpr, QueryExpression bodyExpr) {
+    this.varName = varName;
+    this.varExpr = varExpr;
+    this.bodyExpr = bodyExpr;
+  }
+
+  @Override
+  public <T> Set<T> eval(QueryEnvironment<T> env) throws QueryException {
+    if (!NAME_PATTERN.matcher(varName).matches()) {
+      throw new QueryException(this, "invalid variable name '" + varName + "' in let expression");
+    }
+    Set<T> varValue = varExpr.eval(env);
+    Set<T> prevValue = env.setVariable(varName, varValue);
+    try {
+      return bodyExpr.eval(env);
+    } finally {
+      env.setVariable(varName, prevValue); // restore
+    }
+  }
+
+  @Override
+  public void collectTargetPatterns(Collection<String> literals) {
+    varExpr.collectTargetPatterns(literals);
+    bodyExpr.collectTargetPatterns(literals);
+  }
+
+  @Override
+  public String toString() {
+    return "let " + varName + " = " + varExpr + " in " + bodyExpr;
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/Lexer.java b/src/main/java/com/google/devtools/build/lib/query2/engine/Lexer.java
new file mode 100644
index 0000000000..45b6f6183e
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/Lexer.java
@@ -0,0 +1,281 @@
+// Copyright 2014 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.engine;
+
+import java.util.ArrayList;
+import java.util.EnumSet;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+/**
+ * A tokenizer for the Blaze query language, revision 2.
+ *
+ * Note, we can avoid a lot of quoting by noting that the characters [() ,] do
+ * not appear in any label, filename, function name, or regular expression we care about.
+ *
+ * No string escapes are allowed ("\").  Given the domain, that's not currently
+ * a problem.
+ */
+final class Lexer {
+
+  /**
+   * Discriminator for different kinds of tokens.
+   */
+  public enum TokenKind {
+    WORD("word"),
+    EOF("EOF"),
+
+    COMMA(","),
+    EQUALS("="),
+    LPAREN("("),
+    MINUS("-"),
+    PLUS("+"),
+    RPAREN(")"),
+    CARET("^"),
+
+    __ALL_IDENTIFIERS_FOLLOW(""), // See below
+
+    IN("in"),
+    LET("let"),
+    SET("set"),
+
+    INTERSECT("intersect"),
+    EXCEPT("except"),
+    UNION("union");
+
+    private final String prettyName;
+
+    private TokenKind(String prettyName) {
+      this.prettyName = prettyName;
+    }
+
+    public String getPrettyName() {
+      return prettyName;
+    }
+  }
+
+  public static final Set<TokenKind> BINARY_OPERATORS = EnumSet.of(
+      TokenKind.INTERSECT,
+      TokenKind.CARET,
+      TokenKind.UNION,
+      TokenKind.PLUS,
+      TokenKind.EXCEPT,
+      TokenKind.MINUS);
+
+  private static final Map<String, TokenKind> keywordMap = new HashMap<>();
+  static {
+    for (TokenKind kind : EnumSet.allOf(TokenKind.class)) {
+      if (kind.ordinal() > TokenKind.__ALL_IDENTIFIERS_FOLLOW.ordinal()) {
+        keywordMap.put(kind.getPrettyName(), kind);
+      }
+    }
+  }
+
+  /**
+   * Returns true iff 'word' is a reserved word of the language.
+   */
+  static boolean isReservedWord(String word) {
+    return keywordMap.containsKey(word);
+  }
+
+  /**
+   * Tokens returned by the Lexer.
+   */
+  static class Token {
+
+    public final TokenKind kind;
+    public final String word;
+
+    Token(TokenKind kind) {
+      this.kind = kind;
+      this.word = null;
+    }
+
+    Token(String word) {
+      this.kind = TokenKind.WORD;
+      this.word = word;
+    }
+
+    @Override
+    public String toString() {
+      return kind == TokenKind.WORD ? word : kind.getPrettyName();
+    }
+  }
+
+  /**
+   * Entry point to the lexer.  Returns the list of tokens for the specified
+   * input, or throws QueryException.
+   */
+  public static List<Token> scan(char[] buffer) throws QueryException {
+    Lexer lexer = new Lexer(buffer);
+    lexer.tokenize();
+    return lexer.tokens;
+  }
+
+  // Input buffer and position
+  private char[] buffer;
+  private int pos;
+
+  private final List<Token> tokens = new ArrayList<>();
+
+  private Lexer(char[] buffer) {
+    this.buffer = buffer;
+    this.pos = 0;
+  }
+
+  private void addToken(Token s) {
+    tokens.add(s);
+  }
+
+  /**
+   * Scans a quoted word delimited by 'quot'.
+   *
+   * ON ENTRY: 'pos' is 1 + the index of the first delimiter
+   * ON EXIT: 'pos' is 1 + the index of the last delimiter.
+   *
+   * @return the word token.
+   */
+  private Token quotedWord(char quot) throws QueryException {
+    int oldPos = pos - 1;
+    while (pos < buffer.length) {
+      char c = buffer[pos++];
+      switch (c) {
+        case '\'':
+        case '"':
+          if (c == quot) {
+            // close-quote, all done.
+            return new Token(bufferSlice(oldPos + 1, pos - 1));
+          }
+      }
+    }
+    throw new QueryException("unclosed quotation");
+  }
+
+  private TokenKind getTokenKindForWord(String word) {
+    TokenKind kind = keywordMap.get(word);
+    return kind == null ? TokenKind.WORD : kind;
+  }
+
+  // Unquoted words may contain [-*$], but not start with them.  For user convenience, unquoted
+  // words must include UNIX filenames, labels and target label patterns, and simple regexps
+  // (e.g. cc_.*). Keep consistent with TargetLiteral.toString()!
+  private String scanWord() {
+    int oldPos = pos - 1;
+    while (pos < buffer.length) {
+      switch (buffer[pos]) {
+        case 'a': case 'b': case 'c': case 'd': case 'e': case 'f':
+        case 'g': case 'h': case 'i': case 'j': case 'k': case 'l':
+        case 'm': case 'n': case 'o': case 'p': case 'q': case 'r':
+        case 's': case 't': case 'u': case 'v': case 'w': case 'x':
+        case 'y': case 'z':
+        case 'A': case 'B': case 'C': case 'D': case 'E': case 'F':
+        case 'G': case 'H': case 'I': case 'J': case 'K': case 'L':
+        case 'M': case 'N': case 'O': case 'P': case 'Q': case 'R':
+        case 'S': case 'T': case 'U': case 'V': case 'W': case 'X':
+        case 'Y': case 'Z':
+        case '0': case '1': case '2': case '3': case '4': case '5':
+        case '6': case '7': case '8': case '9':
+        case '*': case '/': case '@': case '.': case '-': case '_':
+        case ':': case '$':
+          pos++;
+          break;
+       default:
+          return bufferSlice(oldPos, pos);
+      }
+    }
+    return bufferSlice(oldPos, pos);
+  }
+
+  /**
+   * Scans a word or keyword.
+   *
+   * ON ENTRY: 'pos' is 1 + the index of the first char in the word.
+   * ON EXIT: 'pos' is 1 + the index of the last char in the word.
+   *
+   * @return the word or keyword token.
+   */
+  private Token wordOrKeyword() {
+    String word = scanWord();
+    TokenKind kind = getTokenKindForWord(word);
+    return kind == TokenKind.WORD ? new Token(word) : new Token(kind);
+  }
+
+  /**
+   * Performs tokenization of the character buffer of file contents provided to
+   * the constructor.
+   */
+  private void tokenize() throws QueryException {
+    while (pos < buffer.length) {
+      char c = buffer[pos];
+      pos++;
+      switch (c) {
+      case '(': {
+        addToken(new Token(TokenKind.LPAREN));
+        break;
+      }
+      case ')': {
+        addToken(new Token(TokenKind.RPAREN));
+        break;
+      }
+      case ',': {
+        addToken(new Token(TokenKind.COMMA));
+        break;
+      }
+      case '+': {
+        addToken(new Token(TokenKind.PLUS));
+        break;
+      }
+      case '-': {
+        addToken(new Token(TokenKind.MINUS));
+        break;
+      }
+      case '=': {
+        addToken(new Token(TokenKind.EQUALS));
+        break;
+      }
+      case '^': {
+        addToken(new Token(TokenKind.CARET));
+        break;
+      }
+      case '\n':
+      case ' ':
+      case '\t':
+      case '\r': {
+        /* ignore */
+        break;
+      }
+      case '\'':
+      case '\"': {
+        addToken(quotedWord(c));
+        break;
+      }
+      default: {
+        addToken(wordOrKeyword());
+        break;
+      } // default
+      } // switch
+    } // while
+
+    addToken(new Token(TokenKind.EOF));
+
+    this.buffer = null; // release buffer now that we have our tokens
+  }
+
+  private String bufferSlice(int start, int end) {
+    return new String(this.buffer, start, end - start);
+  }
+
+}
diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/QueryEnvironment.java b/src/main/java/com/google/devtools/build/lib/query2/engine/QueryEnvironment.java
new file mode 100644
index 0000000000..46a7afd42d
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/QueryEnvironment.java
@@ -0,0 +1,351 @@
+// Copyright 2014 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.engine;
+
+import com.google.common.collect.ImmutableList;
+
+import java.util.Collection;
+import java.util.List;
+import java.util.Set;
+
+import javax.annotation.Nonnull;
+
+/**
+ * The environment of a Blaze query. Implementations do not need to be thread-safe. The generic type
+ * T represents a node of the graph on which the query runs; as such, there is no restriction on T.
+ * However, query assumes a certain graph model, and the {@link TargetAccessor} class is used to
+ * access properties of these nodes.
+ *
+ * @param <T> the node type of the dependency graph
+ */
+public interface QueryEnvironment<T> {
+  /**
+   * Type of an argument of a user-defined query function.
+   */
+  public enum ArgumentType {
+    EXPRESSION, WORD, INTEGER;
+  }
+
+  /**
+   * Value of an argument of a user-defined query function.
+   */
+  public static class Argument {
+    private final ArgumentType type;
+    private final QueryExpression expression;
+    private final String word;
+    private final int integer;
+
+    private Argument(ArgumentType type, QueryExpression expression, String word, int integer) {
+      this.type = type;
+      this.expression = expression;
+      this.word = word;
+      this.integer = integer;
+    }
+
+    static Argument of(QueryExpression expression) {
+      return new Argument(ArgumentType.EXPRESSION, expression, null, 0);
+    }
+
+    static Argument of(String word) {
+      return new Argument(ArgumentType.WORD, null, word, 0);
+    }
+
+    static Argument of(int integer) {
+      return new Argument(ArgumentType.INTEGER, null, null, integer);
+    }
+
+    public ArgumentType getType() {
+      return type;
+    }
+
+    public QueryExpression getExpression() {
+      return expression;
+    }
+
+    public String getWord() {
+      return word;
+    }
+
+    public int getInteger() {
+      return integer;
+    }
+
+    @Override
+    public String toString() {
+      switch (type) {
+        case WORD: return "'" + word + "'";
+        case EXPRESSION: return expression.toString();
+        case INTEGER: return Integer.toString(integer);
+        default: throw new IllegalStateException();
+      }
+    }
+  }
+
+  /**
+   * A user-defined query function.
+   */
+  public interface QueryFunction {
+    /**
+     * Name of the function as it appears in the query language.
+     */
+    String getName();
+
+    /**
+     * The number of arguments that are required. The rest is optional.
+     *
+     * <p>This should be greater than or equal to zero and at smaller than or equal to the length
+     * of the list returned by {@link #getArgumentTypes}.
+     */
+    int getMandatoryArguments();
+
+    /**
+     * The types of the arguments of the function.
+     */
+    List<ArgumentType> getArgumentTypes();
+
+    /**
+     * Called when a user-defined function is to be evaluated.
+     *
+     * @param env the query environment this function is evaluated in.
+     * @param expression the expression being evaluated.
+     * @param args the input arguments. These are type-checked against the specification returned
+     *     by {@link #getArgumentTypes} and {@link #getMandatoryArguments}
+     */
+    <T> Set<T> eval(QueryEnvironment<T> env, QueryExpression expression, List<Argument> args)
+        throws QueryException;
+  }
+
+  /**
+   * Exception type for the case where a target cannot be found. It's basically a wrapper for
+   * whatever exception is internally thrown.
+   */
+  public static final class TargetNotFoundException extends Exception {
+    public TargetNotFoundException(String msg) {
+      super(msg);
+    }
+
+    public TargetNotFoundException(Throwable cause) {
+      super(cause.getMessage(), cause);
+    }
+  }
+
+  /**
+   * Returns the set of target nodes in the graph for the specified target
+   * pattern, in 'blaze build' syntax.
+   */
+  Set<T> getTargetsMatchingPattern(QueryExpression owner, String pattern)
+      throws QueryException;
+
+  /** Ensures the specified target exists. */
+  // NOTE(bazel-team): this method is left here as scaffolding from a previous refactoring. It may
+  // be possible to remove it.
+  T getOrCreate(T target);
+
+  /** Returns the direct forward dependencies of the specified target. */
+  Collection<T> getFwdDeps(T target);
+
+  /** Returns the direct reverse dependencies of the specified target. */
+  Collection<T> getReverseDeps(T target);
+
+  /**
+   * Returns the forward transitive closure of all of the targets in
+   * "targets".  Callers must ensure that {@link #buildTransitiveClosure}
+   * has been called for the relevant subgraph.
+   */
+  Set<T> getTransitiveClosure(Set<T> targets);
+
+  /**
+   * Construct the dependency graph for a depth-bounded forward transitive closure
+   * of all nodes in "targetNodes".  The identity of the calling expression is
+   * required to produce error messages.
+   *
+   * <p>If a larger transitive closure was already built, returns it to
+   * improve incrementality, since all depth-constrained methods filter it
+   * after it is built anyway.
+   */
+  void buildTransitiveClosure(QueryExpression caller,
+                              Set<T> targetNodes,
+                              int maxDepth) throws QueryException;
+
+  /**
+   * Returns the set of nodes on some path from "from" to "to".
+   */
+  Set<T> getNodesOnPath(T from, T to);
+
+  /**
+   * Returns the value of the specified variable, or null if it is undefined.
+   */
+  Set<T> getVariable(String name);
+
+  /**
+   * Sets the value of the specified variable.  If value is null the variable
+   * becomes undefined.  Returns the previous value, if any.
+   */
+  Set<T> setVariable(String name, Set<T> value);
+
+  void reportBuildFileError(QueryExpression expression, String msg) throws QueryException;
+
+  /**
+   * Returns the set of BUILD, included, sub-included and Skylark files that define the given set of
+   * targets. Each such file is itself represented as a target in the result.
+   */
+  Set<T> getBuildFiles(QueryExpression caller, Set<T> nodes) throws QueryException;
+
+  /**
+   * Returns an object that can be used to query information about targets. Implementations should
+   * create a single instance and return that for all calls. A class can implement both {@code
+   * QueryEnvironment} and {@code TargetAccessor} at the same time, in which case this method simply
+   * returns {@code this}.
+   */
+  TargetAccessor<T> getAccessor();
+
+  /**
+   * Whether the given setting is enabled. The code should default to return {@code false} for all
+   * unknown settings. The enum is used rather than a method for each setting so that adding more
+   * settings is backwards-compatible.
+   *
+   * @throws NullPointerException if setting is null
+   */
+  boolean isSettingEnabled(@Nonnull Setting setting);
+
+  /**
+   * Returns the set of query functions implemented by this query environment.
+   */
+  Iterable<QueryFunction> getFunctions();
+
+  /**
+   * Settings for the query engine. See {@link QueryEnvironment#isSettingEnabled}.
+   */
+  public static enum Setting {
+
+    /**
+     * Whether to evaluate tests() expressions in strict mode. If {@link #isSettingEnabled} returns
+     * true for this setting, then the tests() expression will give an error when expanding tests
+     * suites, if the test suite contains any non-test targets.
+     */
+    TESTS_EXPRESSION_STRICT,
+
+    /**
+     * Do not consider implicit deps (any label that was not explicitly specified in the BUILD file)
+     * when traversing dependency edges.
+     */
+    NO_IMPLICIT_DEPS,
+
+    /**
+     * Do not consider host dependencies when traversing dependency edges.
+     */
+    NO_HOST_DEPS,
+
+    /**
+     * Do not consider nodep attributes when traversing dependency edges.
+     */
+    NO_NODEP_DEPS;
+  }
+
+  /**
+   * An adapter interface giving access to properties of T. There are four types of targets: rules,
+   * package groups, source files, and generated files. Of these, only rules can have attributes.
+   */
+  public static interface TargetAccessor<T> {
+    /**
+     * Returns the target type represented as a string of the form {@code &lt;type&gt; rule} or
+     * {@code package group} or {@code source file} or {@code generated file}. This is widely used
+     * for target filtering, so implementations must use the Blaze rule class naming scheme.
+     */
+    String getTargetKind(T target);
+
+    /**
+     * Returns the full label of the target as a string, e.g. {@code //some:target}.
+     */
+    String getLabel(T target);
+
+    /**
+     * Returns whether the given target is a rule.
+     */
+    boolean isRule(T target);
+
+    /**
+     * Returns whether the given target is a test target. If this returns true, then {@link #isRule}
+     * must also return true for the target.
+     */
+    boolean isTestRule(T target);
+
+    /**
+     * Returns whether the given target is a test suite target. If this returns true, then {@link
+     * #isRule} must also return true for the target, but {@link #isTestRule} must return false;
+     * test suites are not test rules, and vice versa.
+     */
+    boolean isTestSuite(T target);
+
+    /**
+     * If the attribute of the given name on the given target is a label or label list, then this
+     * method returns the list of corresponding target instances. Otherwise returns an empty list.
+     * If an error occurs during resolution, it throws a {@link QueryException} using the caller and
+     * error message prefix.
+     *
+     * @throws IllegalArgumentException if target is not a rule (according to {@link #isRule})
+     */
+    List<T> getLabelListAttr(QueryExpression caller, T target, String attrName,
+        String errorMsgPrefix) throws QueryException;
+
+    /**
+     * If the attribute of the given name on the given target is a string list, then this method
+     * returns it.
+     *
+     * @throws IllegalArgumentException if target is not a rule (according to {@link #isRule}), or
+     *                                  if the target does not have an attribute of type string list
+     *                                  with the given name
+     */
+    List<String> getStringListAttr(T target, String attrName);
+
+    /**
+     * If the attribute of the given name on the given target is a string, then this method returns
+     * it.
+     *
+     * @throws IllegalArgumentException if target is not a rule (according to {@link #isRule}), or
+     *                                  if the target does not have an attribute of type string with
+     *                                  the given name
+     */
+    String getStringAttr(T target, String attrName);
+
+    /**
+     * Returns the given attribute represented as a list of strings. For "normal" attributes,
+     * this should just be a list of size one containing the attribute's value. For configurable
+     * attributes, there should be one entry for each possible value the attribute may take.
+     *
+     *<p>Note that for backwards compatibility, tristate and boolean attributes are returned as
+     * int using the values {@code 0, 1} and {@code -1}. If there is no such attribute, this
+     * method returns an empty list.
+     *
+     * @throws IllegalArgumentException if target is not a rule (according to {@link #isRule})
+     */
+    Iterable<String> getAttrAsString(T target, String attrName);
+  }
+
+  /** List of the default query functions. */
+  public static final List<QueryFunction> DEFAULT_QUERY_FUNCTIONS =
+      ImmutableList.<QueryFunction>of(
+          new AllPathsFunction(),
+          new BuildFilesFunction(),
+          new AttrFunction(),
+          new FilterFunction(),
+          new LabelsFunction(),
+          new KindFunction(),
+          new SomeFunction(),
+          new SomePathFunction(),
+          new TestsFunction(),
+          new DepsFunction(),
+          new RdepsFunction()
+          );
+}
diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/QueryEvalResult.java b/src/main/java/com/google/devtools/build/lib/query2/engine/QueryEvalResult.java
new file mode 100644
index 0000000000..5bcea7e3b3
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/QueryEvalResult.java
@@ -0,0 +1,51 @@
+// 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.engine;
+
+import com.google.common.base.Preconditions;
+
+import java.util.Set;
+
+/**
+ * The result of a query evaluation, containing a set of elements.
+ *
+ * @param <T> the node type of the elements.
+ */
+public class QueryEvalResult<T> {
+
+  protected final boolean success;
+  protected final Set<T> resultSet;
+
+  public QueryEvalResult(
+      boolean success, Set<T> resultSet) {
+    this.success = success;
+    this.resultSet = Preconditions.checkNotNull(resultSet);
+  }
+
+  /**
+   * Whether the query was successful. This can only be false if the query was run with
+   * <code>keep_going</code>, otherwise evaluation will throw a {@link QueryException}.
+   */
+  public boolean getSuccess() {
+    return success;
+  }
+
+  /**
+   * Returns the result as a set of targets.
+   */
+  public Set<T> getResultSet() {
+    return resultSet;
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/QueryException.java b/src/main/java/com/google/devtools/build/lib/query2/engine/QueryException.java
new file mode 100644
index 0000000000..71c1a8a8a6
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/QueryException.java
@@ -0,0 +1,58 @@
+// Copyright 2014 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.engine;
+
+/**
+ */
+public class QueryException extends Exception {
+
+  /**
+   * Returns a better error message for the query.
+   */
+  static String describeFailedQuery(QueryException e, QueryExpression toplevel) {
+    QueryExpression badQuery = e.getFailedExpression();
+    if (badQuery == null) {
+      return "Evaluation failed: " + e.getMessage();
+    }
+    return badQuery == toplevel
+        ? "Evaluation of query \"" + toplevel + "\" failed: " + e.getMessage()
+        : "Evaluation of subquery \"" + badQuery
+            + "\" failed (did you want to use --keep_going?): " + e.getMessage();
+  }
+
+  private final QueryExpression expression;
+
+  public QueryException(QueryException e, QueryExpression toplevel) {
+    super(describeFailedQuery(e, toplevel), e);
+    this.expression = null;
+  }
+
+  public QueryException(QueryExpression expression, String message) {
+    super(message);
+    this.expression = expression;
+  }
+
+  public QueryException(String message) {
+    this(null, message);
+  }
+
+  /**
+   * Returns the subexpression for which evaluation failed, or null if
+   * the failure occurred during lexing/parsing.
+   */
+  public QueryExpression getFailedExpression() {
+    return expression;
+  }
+
+}
diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/QueryExpression.java b/src/main/java/com/google/devtools/build/lib/query2/engine/QueryExpression.java
new file mode 100644
index 0000000000..23603f16ff
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/QueryExpression.java
@@ -0,0 +1,83 @@
+// Copyright 2014 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.engine;
+
+import java.util.Collection;
+import java.util.Set;
+
+/**
+ * Base class for expressions in the Blaze query language, revision 2.
+ *
+ * <p>All queries return a subgraph of the dependency graph, represented
+ * as a set of target nodes.
+ *
+ * <p>All queries must ensure that sufficient graph edges are created in the
+ * QueryEnvironment so that all nodes in the result are correctly ordered
+ * according to the type of query.  For example, "deps" queries require that
+ * all the nodes in the transitive closure of its argument set are correctly
+ * ordered w.r.t. each other; "somepath" queries require that the order of the
+ * nodes on the resulting path are correctly ordered; algebraic set operations
+ * such as intersect and union are inherently unordered.
+ *
+ * <h2>Package overview</h2>
+ *
+ * <p>This package consists of two basic class hierarchies.  The first, {@code
+ * QueryExpression}, is the set of different query expressions in the language,
+ * and the {@link #eval} method of each defines the semantics.  The result of
+ * evaluating a query is set of Blaze {@code Target}s (a file or rule).  The
+ * set may be interpreted as either a set or as nodes of a DAG, depending on
+ * the context.
+ *
+ * <p>The second hierarchy is {@code OutputFormatter}.  Its subclasses define
+ * different ways of printing out the result of a query.  Each accepts a {@code
+ * Digraph} of {@code Target}s, and an output stream.
+ */
+public abstract class QueryExpression {
+
+  /**
+   * Scan and parse the specified query expression.
+   */
+  public static QueryExpression parse(String query, QueryEnvironment<?> env)
+      throws QueryException {
+    return QueryParser.parse(query, env);
+  }
+
+  protected QueryExpression() {}
+
+  /**
+   * Evaluates this query in the specified environment, and returns a subgraph,
+   * concretely represented a new (possibly-immutable) set of target nodes.
+   *
+   * Failures resulting from evaluation of an ill-formed query cause
+   * QueryException to be thrown.
+   *
+   * The reporting of failures arising from errors in BUILD files depends on
+   * the --keep_going flag.  If enabled (the default), then QueryException is
+   * thrown.  If disabled, evaluation will stumble on to produce a (possibly
+   * inaccurate) result, but a result nonetheless.
+   */
+  public abstract <T> Set<T> eval(QueryEnvironment<T> env) throws QueryException;
+
+  /**
+   * Collects all target patterns that are referenced anywhere within this query expression and adds
+   * them to the given collection, which must be mutable.
+   */
+  public abstract void collectTargetPatterns(Collection<String> literals);
+
+  /**
+   * Returns this query expression pretty-printed.
+   */
+  @Override
+  public abstract String toString();
+}
diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/QueryParser.java b/src/main/java/com/google/devtools/build/lib/query2/engine/QueryParser.java
new file mode 100644
index 0000000000..bcd89cc31b
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/QueryParser.java
@@ -0,0 +1,261 @@
+// Copyright 2014 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.engine;
+
+import static com.google.devtools.build.lib.query2.engine.Lexer.BINARY_OPERATORS;
+
+import com.google.devtools.build.lib.query2.engine.Lexer.TokenKind;
+import com.google.devtools.build.lib.query2.engine.QueryEnvironment.Argument;
+import com.google.devtools.build.lib.query2.engine.QueryEnvironment.ArgumentType;
+import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryFunction;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+
+/**
+ * LL(1) recursive descent parser for the Blaze query language, revision 2.
+ *
+ * In the grammar below, non-terminals are lowercase and terminals are
+ * uppercase, or character literals.
+ *
+ * <pre>
+ * expr ::= WORD
+ *        | LET WORD = expr IN expr
+ *        | '(' expr ')'
+ *        | WORD '(' expr ( ',' expr ) * ')'
+ *        | expr INTERSECT expr
+ *        | expr '^' expr
+ *        | expr UNION expr
+ *        | expr '+' expr
+ *        | expr EXCEPT expr
+ *        | expr '-' expr
+ *        | SET '(' WORD * ')'
+ * </pre>
+ */
+final class QueryParser {
+
+  private Lexer.Token token; // current lookahead token
+  private final List<Lexer.Token> tokens;
+  private final Iterator<Lexer.Token> tokenIterator;
+  private final Map<String, QueryFunction> functions;
+
+  /**
+   * Scan and parse the specified query expression.
+   */
+  static QueryExpression parse(String query, QueryEnvironment<?> env) throws QueryException {
+    QueryParser parser = new QueryParser(
+        Lexer.scan(query.toCharArray()), env);
+    QueryExpression expr = parser.parseExpression();
+    if (parser.token.kind != TokenKind.EOF) {
+      throw new QueryException("unexpected token '" + parser.token
+                               + "' after query expression '" + expr +  "'");
+    }
+    return expr;
+  }
+
+  private QueryParser(List<Lexer.Token> tokens, QueryEnvironment<?> env) {
+    this.functions = new HashMap<>();
+    for (QueryFunction queryFunction : env.getFunctions()) {
+      this.functions.put(queryFunction.getName(), queryFunction);
+    }
+    this.tokens = tokens;
+    this.tokenIterator = tokens.iterator();
+    nextToken();
+  }
+
+  /**
+   * Returns an exception.  Don't forget to throw it.
+   */
+  private QueryException syntaxError(Lexer.Token token) {
+    String message = "premature end of input";
+    if (token.kind != TokenKind.EOF) {
+      StringBuilder buf = new StringBuilder("syntax error at '");
+      String sep = "";
+      for (int index = tokens.indexOf(token),
+               max = Math.min(tokens.size() - 1, index + 3); // 3 tokens of context
+               index < max; ++index) {
+        buf.append(sep).append(tokens.get(index));
+        sep = " ";
+      }
+      buf.append("'");
+      message = buf.toString();
+    }
+    return new QueryException(message);
+  }
+
+  /**
+   * Consumes the current token.  If it is not of the specified (expected)
+   * kind, throws QueryException.  Returns the value associated with the
+   * consumed token, if any.
+   */
+  private String consume(TokenKind kind) throws QueryException {
+    if (token.kind != kind) {
+      throw syntaxError(token);
+    }
+    String word = token.word;
+    nextToken();
+    return word;
+  }
+
+  /**
+   * Consumes the current token, which must be a WORD containing an integer
+   * literal.  Returns that integer, or throws a QueryException otherwise.
+   */
+  private int consumeIntLiteral() throws QueryException {
+    String intString = consume(TokenKind.WORD);
+    try {
+      return Integer.parseInt(intString);
+    } catch (NumberFormatException e) {
+      throw new QueryException("expected an integer literal: '" + intString + "'");
+    }
+  }
+
+  private void nextToken() {
+    if (token == null || token.kind != TokenKind.EOF) {
+      token = tokenIterator.next();
+    }
+  }
+
+  /**
+   * expr ::= primary
+   *        | expr INTERSECT expr
+   *        | expr '^' expr
+   *        | expr UNION expr
+   *        | expr '+' expr
+   *        | expr EXCEPT expr
+   *        | expr '-' expr
+   */
+  private QueryExpression parseExpression() throws QueryException {
+    // All operators are left-associative and of equal precedence.
+    return parseBinaryOperatorTail(parsePrimary());
+  }
+
+  /**
+   * tail ::= ( <op> <primary> )*
+   * All operators have equal precedence.
+   * This factoring is required for left-associative binary operators in LL(1).
+   */
+  private QueryExpression parseBinaryOperatorTail(QueryExpression lhs) throws QueryException {
+    if (!BINARY_OPERATORS.contains(token.kind)) {
+      return lhs;
+    }
+
+    List<QueryExpression> operands = new ArrayList<>();
+    operands.add(lhs);
+    TokenKind lastOperator = token.kind;
+
+    while (BINARY_OPERATORS.contains(token.kind)) {
+      TokenKind operator = token.kind;
+      consume(operator);
+      if (operator != lastOperator) {
+        lhs = new BinaryOperatorExpression(lastOperator, operands);
+        operands.clear();
+        operands.add(lhs);
+        lastOperator = operator;
+      }
+      QueryExpression rhs = parsePrimary();
+      operands.add(rhs);
+    }
+    return new BinaryOperatorExpression(lastOperator, operands);
+  }
+
+  /**
+   * primary ::= WORD
+   *           | LET WORD = expr IN expr
+   *           | '(' expr ')'
+   *           | WORD '(' expr ( ',' expr ) * ')'
+   *           | DEPS '(' expr ')'
+   *           | DEPS '(' expr ',' WORD ')'
+   *           | RDEPS '(' expr ',' expr ')'
+   *           | RDEPS '(' expr ',' expr ',' WORD ')'
+   *           | SET '(' WORD * ')'
+   */
+  private QueryExpression parsePrimary() throws QueryException {
+    switch (token.kind) {
+      case WORD: {
+        String word = consume(TokenKind.WORD);
+        if (token.kind == TokenKind.LPAREN) {
+          QueryFunction function = functions.get(word);
+          if (function == null) {
+            throw syntaxError(token);
+          }
+          List<Argument> args = new ArrayList<>();
+          TokenKind tokenKind = TokenKind.LPAREN;
+          int argsSeen = 0;
+          for (ArgumentType type : function.getArgumentTypes()) {
+            if (token.kind == TokenKind.RPAREN && argsSeen >= function.getMandatoryArguments()) {
+              break;
+            }
+
+            consume(tokenKind);
+            tokenKind = TokenKind.COMMA;
+            switch (type) {
+              case EXPRESSION:
+                args.add(Argument.of(parseExpression()));
+                break;
+
+              case WORD:
+                args.add(Argument.of(consume(TokenKind.WORD)));
+                break;
+
+              case INTEGER:
+                args.add(Argument.of(consumeIntLiteral()));
+                break;
+
+              default:
+                throw new IllegalStateException();
+            }
+
+            argsSeen++;
+          }
+
+          consume(TokenKind.RPAREN);
+          return new FunctionExpression(function, args);
+        } else {
+          return new TargetLiteral(word);
+        }
+      }
+      case LET: {
+        consume(TokenKind.LET);
+        String name = consume(TokenKind.WORD);
+        consume(TokenKind.EQUALS);
+        QueryExpression varExpr = parseExpression();
+        consume(TokenKind.IN);
+        QueryExpression bodyExpr = parseExpression();
+        return new LetExpression(name, varExpr, bodyExpr);
+      }
+      case LPAREN: {
+        consume(TokenKind.LPAREN);
+        QueryExpression expr = parseExpression();
+        consume(TokenKind.RPAREN);
+        return expr;
+      }
+      case SET: {
+        nextToken();
+        consume(TokenKind.LPAREN);
+        List<TargetLiteral> words = new ArrayList<>();
+        while (token.kind == TokenKind.WORD) {
+          words.add(new TargetLiteral(consume(TokenKind.WORD)));
+        }
+        consume(TokenKind.RPAREN);
+        return new SetExpression(words);
+      }
+      default:
+        throw syntaxError(token);
+    }
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/RdepsFunction.java b/src/main/java/com/google/devtools/build/lib/query2/engine/RdepsFunction.java
new file mode 100644
index 0000000000..6a8734bb3f
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/RdepsFunction.java
@@ -0,0 +1,99 @@
+// Copyright 2014 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.engine;
+
+import com.google.common.collect.ImmutableList;
+import com.google.devtools.build.lib.query2.engine.QueryEnvironment.Argument;
+import com.google.devtools.build.lib.query2.engine.QueryEnvironment.ArgumentType;
+import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryFunction;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.LinkedHashSet;
+import java.util.List;
+import java.util.Set;
+
+/**
+ * An "rdeps" query expression, which computes the reverse dependencies of the argument within the
+ * transitive closure of the universe. An optional integer-literal third argument may be
+ * specified; its value bounds the search from the arguments.
+ *
+ * <pre>expr ::= RDEPS '(' expr ',' expr ')'</pre>
+ * <pre>       | RDEPS '(' expr ',' expr ',' WORD ')'</pre>
+ */
+final class RdepsFunction implements QueryFunction {
+  RdepsFunction() {
+  }
+
+  @Override
+  public String getName() {
+    return "rdeps";
+  }
+
+  @Override
+  public int getMandatoryArguments() {
+    return 2;  // last argument is optional
+  }
+
+  @Override
+  public List<ArgumentType> getArgumentTypes() {
+    return ImmutableList.of(
+        ArgumentType.EXPRESSION, ArgumentType.EXPRESSION, ArgumentType.INTEGER);
+  }
+
+  /**
+   * Compute the transitive closure of the universe, then breadth-first search from the argument
+   * towards the universe while staying within the transitive closure.
+   */
+  @Override
+  public <T> Set<T> eval(QueryEnvironment<T> env, QueryExpression expression, List<Argument> args)
+      throws QueryException {
+    Set<T> universeValue = args.get(0).getExpression().eval(env);
+    Set<T> argumentValue = args.get(1).getExpression().eval(env);
+    int depthBound = args.size() > 2 ? args.get(2).getInteger() : Integer.MAX_VALUE;
+
+    env.buildTransitiveClosure(expression, universeValue, Integer.MAX_VALUE);
+
+    Set<T> visited = new LinkedHashSet<>();
+    Set<T> reachableFromUniverse = env.getTransitiveClosure(universeValue);
+    Collection<T> current = argumentValue;
+
+    // We need to iterate depthBound + 1 times.
+    for (int i = 0; i <= depthBound; i++) {
+      List<T> next = new ArrayList<>();
+      for (T node : current) {
+        if (!reachableFromUniverse.contains(node)) {
+          // Traversed outside the transitive closure of the universe.
+          continue;
+        }
+
+        if (!visited.add(node)) {
+          // Already visited; if we see a node in a later round, then we don't need to visit it
+          // again, because the depth at which we see it at must be greater than or equal to the
+          // last visit.
+          continue;
+        }
+
+        next.addAll(env.getReverseDeps(node));
+      }
+      if (next.isEmpty()) {
+        // Exit when there are no more nodes to visit.
+        break;
+      }
+      current = next;
+    }
+
+    return visited;
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/RegexFilterExpression.java b/src/main/java/com/google/devtools/build/lib/query2/engine/RegexFilterExpression.java
new file mode 100644
index 0000000000..1dbe5e63d3
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/RegexFilterExpression.java
@@ -0,0 +1,83 @@
+// Copyright 2014 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.engine;
+
+import com.google.common.collect.ImmutableList;
+import com.google.devtools.build.lib.query2.engine.QueryEnvironment.Argument;
+import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryFunction;
+
+import java.util.LinkedHashSet;
+import java.util.List;
+import java.util.Set;
+import java.util.regex.Pattern;
+
+/**
+ * An abstract class that provides generic regex filter expression. Actual
+ * expression are implemented by the subclasses.
+ */
+abstract class RegexFilterExpression implements QueryFunction {
+  protected RegexFilterExpression() {
+  }
+
+  @Override
+  public <T> Set<T> eval(QueryEnvironment<T> env, QueryExpression expression, List<Argument> args)
+      throws QueryException {
+    Pattern compiledPattern;
+    try {
+      compiledPattern = Pattern.compile(getPattern(args));
+    } catch (IllegalArgumentException e) {
+      throw new QueryException(expression, "illegal pattern regexp in '" + this + "': "
+                               + e.getMessage());
+    }
+
+    QueryExpression argument = args.get(args.size() - 1).getExpression();
+
+    Set<T> result = new LinkedHashSet<>();
+    for (T target : argument.eval(env)) {
+      for (String str : getFilterStrings(env, args, target)) {
+        if ((str != null) && compiledPattern.matcher(str).find()) {
+          result.add(target);
+          break;
+        }
+      }
+    }
+    return result;
+  }
+
+  /**
+   * Returns string for the given target that must be matched against pattern.
+   * May return null, in which case matching is guaranteed to fail.
+   */
+  protected abstract <T> String getFilterString(
+      QueryEnvironment<T> env, List<Argument> args, T target);
+
+  /**
+   * Returns a list of strings for the given target that must be matched against
+   * pattern. The filter matches if *any* of these strings matches.
+   *
+   * <p>Unless subclasses have an explicit reason to override this method, it's fine
+   * to keep the default implementation that just delegates to {@link #getFilterString}.
+   * Overriding this method is useful for subclasses that want to match against a
+   * universe of possible values. For example, with configurable attributes, an
+   * attribute might have different values depending on the build configuration. One
+   * may wish the filter to match if *any* of those values matches.
+   */
+  protected <T> Iterable<String> getFilterStrings(
+      QueryEnvironment<T> env, List<Argument> args, T target) {
+    String filterString = getFilterString(env, args, target);
+    return filterString == null ? ImmutableList.<String>of() : ImmutableList.of(filterString);
+  }
+
+  protected abstract String getPattern(List<Argument> args);
+}
diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/SetExpression.java b/src/main/java/com/google/devtools/build/lib/query2/engine/SetExpression.java
new file mode 100644
index 0000000000..a28c679fbb
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/SetExpression.java
@@ -0,0 +1,70 @@
+// Copyright 2014 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.engine;
+
+import com.google.common.base.Joiner;
+
+import java.util.Collection;
+import java.util.LinkedHashSet;
+import java.util.List;
+import java.util.Set;
+
+/**
+ * A set(word, ..., word) expression, which computes the union of zero or more
+ * target patterns separated by whitespace.  This is intended to support the
+ * use-case in which a set of labels written to a file by a previous query
+ * expression can be modified externally, then used as input to another query,
+ * like so:
+ *
+ * <pre>
+ * % blaze query 'somepath(foo, bar)' | grep ... | sed ... | awk ... >file
+ * % blaze query "kind(qux_library, set($(<file)))"
+ * </pre>
+ *
+ * <p>The grammar currently restricts the operands of set() to being zero or
+ * more words (target patterns), with no intervening punctuation.  In principle
+ * this could be extended to arbitrary expressions without grammatical
+ * ambiguity, but this seems excessively general for now.
+ *
+ * <pre>expr ::= SET '(' WORD * ')'</pre>
+ */
+class SetExpression extends QueryExpression {
+
+  private final List<TargetLiteral> words;
+
+  SetExpression(List<TargetLiteral> words) {
+    this.words = words;
+  }
+
+  @Override
+  public <T> Set<T> eval(QueryEnvironment<T> env) throws QueryException {
+    Set<T> result = new LinkedHashSet<>();
+    for (TargetLiteral expr : words) {
+      result.addAll(expr.eval(env));
+    }
+    return result;
+  }
+
+  @Override
+  public void collectTargetPatterns(Collection<String> literals) {
+    for (TargetLiteral expr : words) {
+      expr.collectTargetPatterns(literals);
+    }
+  }
+
+  @Override
+  public String toString() {
+    return "set(" + Joiner.on(' ').join(words) + ")";
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/SkyframeRestartQueryException.java b/src/main/java/com/google/devtools/build/lib/query2/engine/SkyframeRestartQueryException.java
new file mode 100644
index 0000000000..d720ec9e11
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/SkyframeRestartQueryException.java
@@ -0,0 +1,24 @@
+// Copyright 2014 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.engine;
+
+/**
+ * This exception is thrown when a query operation was unable to complete because of a Skyframe
+ * missing dependency.
+ */
+public class SkyframeRestartQueryException extends RuntimeException {
+  public SkyframeRestartQueryException() {
+    super("need skyframe retry. missing dep");
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/SomeFunction.java b/src/main/java/com/google/devtools/build/lib/query2/engine/SomeFunction.java
new file mode 100644
index 0000000000..384b4740ad
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/SomeFunction.java
@@ -0,0 +1,59 @@
+// Copyright 2014 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.engine;
+
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
+import com.google.devtools.build.lib.query2.engine.QueryEnvironment.Argument;
+import com.google.devtools.build.lib.query2.engine.QueryEnvironment.ArgumentType;
+import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryFunction;
+
+import java.util.List;
+import java.util.Set;
+
+/**
+ * A some(x) filter expression, which returns an arbitrary node in set x, or
+ * fails if x is empty.
+ *
+ * <pre>expr ::= SOME '(' expr ')'</pre>
+ */
+class SomeFunction implements QueryFunction {
+  SomeFunction() {
+  }
+
+  @Override
+  public String getName() {
+    return "some";
+  }
+
+  @Override
+  public int getMandatoryArguments() {
+    return 1;
+  }
+
+  @Override
+  public List<ArgumentType> getArgumentTypes() {
+    return ImmutableList.of(ArgumentType.EXPRESSION);
+  }
+
+  @Override
+  public <T> Set<T> eval(QueryEnvironment<T> env, QueryExpression expression, List<Argument> args)
+      throws QueryException {
+    Set<T> argumentValue = args.get(0).getExpression().eval(env);
+    if (argumentValue.isEmpty()) {
+      throw new QueryException(expression, "argument set is empty");
+    }
+    return ImmutableSet.of(argumentValue.iterator().next());
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/SomePathFunction.java b/src/main/java/com/google/devtools/build/lib/query2/engine/SomePathFunction.java
new file mode 100644
index 0000000000..b90bcdfde9
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/SomePathFunction.java
@@ -0,0 +1,87 @@
+// Copyright 2014 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.engine;
+
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Sets;
+import com.google.common.collect.Sets.SetView;
+import com.google.devtools.build.lib.query2.engine.QueryEnvironment.Argument;
+import com.google.devtools.build.lib.query2.engine.QueryEnvironment.ArgumentType;
+import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryFunction;
+
+import java.util.HashSet;
+import java.util.List;
+import java.util.Set;
+
+/**
+ * A somepath(x, y) query expression, which computes the set of nodes
+ * on some arbitrary path from a target in set x to a target in set y.
+ *
+ * <pre>expr ::= SOMEPATH '(' expr ',' expr ')'</pre>
+ */
+class SomePathFunction implements QueryFunction {
+  SomePathFunction() {
+  }
+
+  @Override
+  public String getName() {
+    return "somepath";
+  }
+
+  @Override
+  public int getMandatoryArguments() {
+    return 2;
+  }
+
+  @Override
+  public List<ArgumentType> getArgumentTypes() {
+    return ImmutableList.of(ArgumentType.EXPRESSION, ArgumentType.EXPRESSION);
+  }
+
+  @Override
+  public <T> Set<T> eval(QueryEnvironment<T> env, QueryExpression expression, List<Argument> args)
+      throws QueryException {
+    Set<T> fromValue = args.get(0).getExpression().eval(env);
+    Set<T> toValue = args.get(1).getExpression().eval(env);
+
+    // Implementation strategy: for each x in "from", compute its forward
+    // transitive closure.  If it intersects "to", then do a path search from x
+    // to an arbitrary node in the intersection, and return the path.  This
+    // avoids computing the full transitive closure of "from" in some cases.
+
+    env.buildTransitiveClosure(expression, fromValue, Integer.MAX_VALUE);
+
+    // This set contains all nodes whose TC does not intersect "toValue".
+    Set<T> done = new HashSet<>();
+
+    for (T x : fromValue) {
+      if (done.contains(x)) {
+        continue;
+      }
+      Set<T> xtc = env.getTransitiveClosure(ImmutableSet.of(x));
+      SetView<T> result;
+      if (xtc.size() > toValue.size()) {
+        result = Sets.intersection(toValue, xtc);
+      } else {
+        result = Sets.intersection(xtc, toValue);
+      }
+      if (!result.isEmpty()) {
+        return env.getNodesOnPath(x, result.iterator().next());
+      }
+      done.addAll(xtc);
+    }
+    return ImmutableSet.of();
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/TargetLiteral.java b/src/main/java/com/google/devtools/build/lib/query2/engine/TargetLiteral.java
new file mode 100644
index 0000000000..b6a57cc5a5
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/TargetLiteral.java
@@ -0,0 +1,72 @@
+// Copyright 2014 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.engine;
+
+import com.google.common.base.Preconditions;
+
+import java.util.Collection;
+import java.util.Set;
+
+/**
+ * A literal set of targets, using 'blaze build' syntax.  Or, a reference to a
+ * variable name.  (The syntax of the string "pattern" determines which.)
+ *
+ * TODO(bazel-team): Perhaps we should distinguish NAME from WORD in the parser,
+ * based on the characters in it?  Also, perhaps we should not allow NAMEs to
+ * be quoted like WORDs can be.
+ *
+ * <pre>expr ::= NAME | WORD</pre>
+ */
+final class TargetLiteral extends QueryExpression {
+
+  private final String pattern;
+
+  TargetLiteral(String pattern) {
+    this.pattern = Preconditions.checkNotNull(pattern);
+  }
+
+  public boolean isVariableReference() {
+    return LetExpression.isValidVarReference(pattern);
+  }
+
+  @Override
+  public <T> Set<T> eval(QueryEnvironment<T> env) throws QueryException {
+    if (isVariableReference()) {
+      String varName = LetExpression.getNameFromReference(pattern);
+      Set<T> value = env.getVariable(varName);
+      if (value == null) {
+        throw new QueryException(this, "undefined variable '" + varName + "'");
+      }
+      return env.getVariable(varName);
+    }
+
+    return env.getTargetsMatchingPattern(this, pattern);
+  }
+
+  @Override
+  public void collectTargetPatterns(Collection<String> literals) {
+    if (!isVariableReference()) {
+      literals.add(pattern);
+    }
+  }
+
+  @Override
+  public String toString() {
+    // Keep predicate consistent with Lexer.scanWord!
+    boolean needsQuoting = Lexer.isReservedWord(pattern)
+                        || pattern.isEmpty()
+                        || "$-*".indexOf(pattern.charAt(0)) != -1;
+    return needsQuoting ? ("\"" + pattern + "\"") : pattern;
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/query2/engine/TestsFunction.java b/src/main/java/com/google/devtools/build/lib/query2/engine/TestsFunction.java
new file mode 100644
index 0000000000..c902609b9f
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/query2/engine/TestsFunction.java
@@ -0,0 +1,257 @@
+// Copyright 2014 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.engine;
+
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Sets;
+import com.google.devtools.build.lib.query2.engine.QueryEnvironment.Argument;
+import com.google.devtools.build.lib.query2.engine.QueryEnvironment.ArgumentType;
+import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryFunction;
+import com.google.devtools.build.lib.query2.engine.QueryEnvironment.Setting;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+/**
+ * A tests(x) filter expression, which returns all the tests in set x,
+ * expanding test_suite rules into their constituents.
+ *
+ * <p>Unfortunately this class reproduces a substantial amount of logic from
+ * {@code TestSuiteConfiguredTarget}, albeit in a somewhat simplified form.
+ * This is basically inevitable since the expansion of test_suites cannot be
+ * done during the loading phase, because it involves inter-package references.
+ * We make no attempt to validate the input, or report errors or warnings other
+ * than missing target.
+ *
+ * <pre>expr ::= TESTS '(' expr ')'</pre>
+ */
+class TestsFunction implements QueryFunction {
+  TestsFunction() {
+  }
+
+  @Override
+  public String getName() {
+    return "tests";
+  }
+
+  @Override
+  public int getMandatoryArguments() {
+    return 1;
+  }
+
+  @Override
+  public List<ArgumentType> getArgumentTypes() {
+    return ImmutableList.of(ArgumentType.EXPRESSION);
+  }
+
+  @Override
+  public <T> Set<T> eval(QueryEnvironment<T> env, QueryExpression expression, List<Argument> args)
+      throws QueryException {
+    Closure<T> closure = new Closure<>(expression, env);
+    Set<T> result = new HashSet<>();
+    for (T target : args.get(0).getExpression().eval(env)) {
+      if (env.getAccessor().isTestRule(target)) {
+        result.add(target);
+      } else if (env.getAccessor().isTestSuite(target)) {
+        for (T test : closure.getTestsInSuite(target)) {
+          result.add(env.getOrCreate(test));
+        }
+      }
+    }
+    return result;
+  }
+
+  /**
+   * Decides whether to include a test in a test_suite or not.
+   * @param testTags Collection of all tags exhibited by a given test.
+   * @param positiveTags Tags declared by the suite. A test must match ALL of these.
+   * @param negativeTags Tags declared by the suite. A test must match NONE of these.
+   * @return false is the test is to be removed.
+   */
+  private static boolean includeTest(Collection<String> testTags,
+      Collection<String> positiveTags, Collection<String> negativeTags) {
+    // Add this test if it matches ALL of the positive tags and NONE of the
+    // negative tags in the tags attribute.
+    for (String tag : negativeTags) {
+      if (testTags.contains(tag)) {
+        return false;
+      }
+    }
+    for (String tag : positiveTags) {
+      if (!testTags.contains(tag)) {
+        return false;
+      }
+    }
+    return true;
+  }
+
+  /**
+   * Separates a list of text "tags" into a Pair of Collections, where
+   * the first element are the required or positive tags and the second element
+   * are the excluded or negative tags.
+   * This should work on tag list provided from the command line
+   * --test_tags_filters flag or on tag filters explicitly declared in the
+   * suite.
+   *
+   * Keep this function in sync with the version in
+   *  java.com.google.devtools.build.lib.view.packages.TestTargetUtils.sortTagsBySense
+   *
+   * @param tagList A collection of text tags to separate.
+   */
+  private static void sortTagsBySense(
+      Collection<String> tagList, Set<String> requiredTags, Set<String> excludedTags) {
+    for (String tag : tagList) {
+      if (tag.startsWith("-")) {
+        excludedTags.add(tag.substring(1));
+      } else if (tag.startsWith("+")) {
+        requiredTags.add(tag.substring(1));
+      } else if (tag.equals("manual")) {
+        // Ignore manual attribute because it is an exception: it is not a filter
+        // but a property of test_suite
+        continue;
+      } else {
+        requiredTags.add(tag);
+      }
+    }
+  }
+
+  /**
+   * A closure over the temporary state needed to compute the expression. This makes the evaluation
+   * thread-safe, as long as instances of this class are used only within a single thread.
+   */
+  private final class Closure<T> {
+    private final QueryExpression expression;
+    /** A dynamically-populated mapping from test_suite rules to their tests. */
+    private final Map<T, Set<T>> testsInSuite = new HashMap<>();
+
+    /** The environment in which this query is being evaluated. */
+    private final QueryEnvironment<T> env;
+
+    private final boolean strict;
+
+    private Closure(QueryExpression expression, QueryEnvironment<T> env) {
+      this.expression = expression;
+      this.env = env;
+      this.strict = env.isSettingEnabled(Setting.TESTS_EXPRESSION_STRICT);
+    }
+
+    /**
+     * Computes and returns the set of test rules in a particular suite.  Uses
+     * dynamic programming---a memoized version of {@link #computeTestsInSuite}.
+     *
+     * @precondition env.getAccessor().isTestSuite(testSuite)
+     */
+    private Set<T> getTestsInSuite(T testSuite) throws QueryException {
+      Set<T> tests = testsInSuite.get(testSuite);
+      if (tests == null) {
+        tests = Sets.newHashSet();
+        testsInSuite.put(testSuite, tests); // break cycles by inserting empty set early.
+        computeTestsInSuite(testSuite, tests);
+      }
+      return tests;
+    }
+
+    /**
+     * Populates 'result' with all the tests associated with the specified
+     * 'testSuite'.  Throws an exception if any target is missing.
+     *
+     * <p>CAUTION!  Keep this logic consistent with {@code TestsSuiteConfiguredTarget}!
+     *
+     * @precondition env.getAccessor().isTestSuite(testSuite)
+     */
+    private void computeTestsInSuite(T testSuite, Set<T> result) throws QueryException {
+      List<T> testsAndSuites = new ArrayList<>();
+      // Note that testsAndSuites can contain input file targets; the test_suite rule does not
+      // restrict the set of targets that can appear in tests or suites.
+      testsAndSuites.addAll(getPrerequisites(testSuite, "tests"));
+      testsAndSuites.addAll(getPrerequisites(testSuite, "suites"));
+
+      // 1. Add all tests
+      for (T test : testsAndSuites) {
+        if (env.getAccessor().isTestRule(test)) {
+          result.add(test);
+        } else if (strict && !env.getAccessor().isTestSuite(test)) {
+          // If strict mode is enabled, then give an error for any non-test, non-test-suite targets.
+          env.reportBuildFileError(expression, "The label '"
+              + env.getAccessor().getLabel(test) + "' in the test_suite '"
+              + env.getAccessor().getLabel(testSuite) + "' does not refer to a test or test_suite "
+              + "rule!");
+        }
+      }
+
+      // 2. Add implicit dependencies on tests in same package, if any.
+      for (T target : getPrerequisites(testSuite, "$implicit_tests")) {
+        // The Package construction of $implicit_tests ensures that this check never fails, but we
+        // add it here anyway for compatibility with future code.
+        if (env.getAccessor().isTestRule(target)) {
+          result.add(target);
+        }
+      }
+
+      // 3. Filter based on tags, size, env.
+      filterTests(testSuite, result);
+
+      // 4. Expand all suites recursively.
+      for (T suite : testsAndSuites) {
+        if (env.getAccessor().isTestSuite(suite)) {
+          result.addAll(getTestsInSuite(suite));
+        }
+      }
+    }
+
+    /**
+     * Returns the set of rules named by the attribute 'attrName' of test_suite rule 'testSuite'.
+     * The attribute must be a list of labels. If a target cannot be resolved, then an error is
+     * reported to the environment (which may throw an exception if {@code keep_going} is disabled).
+     *
+     * @precondition env.getAccessor().isTestSuite(testSuite)
+     */
+    private List<T> getPrerequisites(T testSuite, String attrName) throws QueryException {
+      return env.getAccessor().getLabelListAttr(expression, testSuite, attrName,
+          "couldn't expand '" + attrName
+          + "' attribute of test_suite " + env.getAccessor().getLabel(testSuite) + ": ");
+    }
+
+    /**
+     * Filters 'tests' (by mutation) according to the 'tags' attribute, specifically those that
+     * match ALL of the tags in tagsAttribute.
+     *
+     * @precondition {@code env.getAccessor().isTestSuite(testSuite)}
+     * @precondition {@code env.getAccessor().isTestRule(test)} for all test in tests
+     */
+    private void filterTests(T testSuite, Set<T> tests) {
+      List<String> tagsAttribute = env.getAccessor().getStringListAttr(testSuite, "tags");
+      // Split the tags list into positive and negative tags
+      Set<String> requiredTags = new HashSet<>();
+      Set<String> excludedTags = new HashSet<>();
+      sortTagsBySense(tagsAttribute, requiredTags, excludedTags);
+
+      Iterator<T> it = tests.iterator();
+      while (it.hasNext()) {
+        T test = it.next();
+        List<String> testTags = new ArrayList<>(env.getAccessor().getStringListAttr(test, "tags"));
+        testTags.add(env.getAccessor().getStringAttr(test, "size"));
+        if (!includeTest(testTags, requiredTags, excludedTags)) {
+          it.remove();
+        }
+      }
+    }
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/query2/output/GraphOutputFormatter.java b/src/main/java/com/google/devtools/build/lib/query2/output/GraphOutputFormatter.java
new file mode 100644
index 0000000000..5ded5e2266
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/query2/output/GraphOutputFormatter.java
@@ -0,0 +1,174 @@
+// Copyright 2014 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.output;
+
+import com.google.devtools.build.lib.collect.CollectionUtils;
+import com.google.devtools.build.lib.collect.EquivalenceRelation;
+import com.google.devtools.build.lib.graph.Digraph;
+import com.google.devtools.build.lib.graph.DotOutputVisitor;
+import com.google.devtools.build.lib.graph.LabelSerializer;
+import com.google.devtools.build.lib.graph.Node;
+import com.google.devtools.build.lib.packages.Target;
+
+import java.io.PrintStream;
+import java.io.PrintWriter;
+import java.util.Collection;
+import java.util.HashSet;
+import java.util.Set;
+
+/**
+ * An output formatter that prints the result as factored graph in AT&amp;T
+ * GraphViz format.
+ */
+class GraphOutputFormatter extends OutputFormatter {
+
+  private int graphNodeStringLimit;
+  private boolean graphFactored;
+
+  @Override
+  public String getName() {
+    return "graph";
+  }
+
+  @Override
+  public void output(QueryOptions options, Digraph<Target> result, PrintStream out) {
+    this.graphNodeStringLimit = options.graphNodeStringLimit;
+    this.graphFactored = options.graphFactored;
+
+    if (graphFactored) {
+      outputFactored(result, new PrintWriter(out));
+    } else {
+      outputUnfactored(result, new PrintWriter(out));
+    }
+  }
+
+  private void outputUnfactored(Digraph<Target> result, PrintWriter out) {
+    result.visitNodesBeforeEdges(
+        new DotOutputVisitor<Target>(out, LABEL_STRINGIFIER) {
+          @Override
+          public void beginVisit() {
+            super.beginVisit();
+            // TODO(bazel-team): (2009) make this the default in Digraph.
+            out.println("  node [shape=box];");
+          }
+        });
+  }
+
+  private void outputFactored(Digraph<Target> result, PrintWriter out) {
+    EquivalenceRelation<Node<Target>> equivalenceRelation = createEquivalenceRelation();
+
+    // Notes on ordering:
+    // - Digraph.getNodes() returns nodes in no particular order
+    // - CollectionUtils.partition inserts elements into unordered sets
+    // This means partitions may contain nodes in a different order than perhaps expected.
+    // Example (package //foo):
+    //   some_rule(
+    //       name = 'foo',
+    //       srcs = ['a', 'b', 'c'],
+    //   )
+    // Querying for deps('foo') will return (among others) the 'foo' node with successors 'a', 'b'
+    // and 'c' (in this order), however when asking the Digraph for all of its nodes, the returned
+    // collection may be ordered differently.
+    Collection<Set<Node<Target>>> partition =
+        CollectionUtils.partition(result.getNodes(), equivalenceRelation);
+
+    Digraph<Set<Node<Target>>> factoredGraph = result.createImageUnderPartition(partition);
+
+    // Concatenate the labels of all topologically-equivalent nodes.
+    LabelSerializer<Set<Node<Target>>> labelSerializer = new LabelSerializer<Set<Node<Target>>>() {
+      @Override
+      public String serialize(Node<Set<Node<Target>>> node) {
+        int actualLimit = graphNodeStringLimit - RESERVED_LABEL_CHARS;
+        boolean firstItem = true;
+        StringBuffer buf = new StringBuffer();
+        int count = 0;
+        for (Node<Target> eqNode : node.getLabel()) {
+          String labelString = eqNode.getLabel().getLabel().toString();
+          if (!firstItem) {
+            buf.append("\\n");
+
+            // Use -1 to denote no limit, as it is easier than trying to pass MAX_INT on the cmdline
+            if (graphNodeStringLimit != -1 && (buf.length() + labelString.length() > actualLimit)) {
+              buf.append("...and ");
+              buf.append(node.getLabel().size() - count);
+              buf.append(" more items");
+              break;
+            }
+          }
+
+          buf.append(labelString);
+          count++;
+          firstItem = false;
+        }
+        return buf.toString();
+      }
+    };
+
+    factoredGraph.visitNodesBeforeEdges(
+        new DotOutputVisitor<Set<Node<Target>>>(out, labelSerializer) {
+          @Override
+          public void beginVisit() {
+            super.beginVisit();
+            // TODO(bazel-team): (2009) make this the default in Digraph.
+            out.println("  node [shape=box];");
+          }
+        });
+  }
+
+  /**
+   * Returns an equivalence relation for nodes in the specified graph.
+   *
+   * <p>Two nodes are considered equal iff they have equal topology (predecessors and successors).
+   *
+   * TODO(bazel-team): Make this a method of Digraph.
+   */
+  private static <LABEL> EquivalenceRelation<Node<LABEL>> createEquivalenceRelation() {
+    return new EquivalenceRelation<Node<LABEL>>() {
+      @Override
+      public int compare(Node<LABEL> x, Node<LABEL> y) {
+        if (x == y) {
+          return 0;
+        }
+
+        if (x.numPredecessors() != y.numPredecessors()
+            || x.numSuccessors() != y.numSuccessors()) {
+          return -1;
+        }
+
+        Set<Node<LABEL>> xpred = new HashSet<>(x.getPredecessors());
+        Set<Node<LABEL>> ypred = new HashSet<>(y.getPredecessors());
+        if (!xpred.equals(ypred)) {
+          return -1;
+        }
+
+        Set<Node<LABEL>> xsucc = new HashSet<>(x.getSuccessors());
+        Set<Node<LABEL>> ysucc = new HashSet<>(y.getSuccessors());
+        if (!xsucc.equals(ysucc)) {
+          return -1;
+        }
+
+        return 0;
+      }
+    };
+  }
+
+  private static final int RESERVED_LABEL_CHARS = "\\n...and 9999999 more items".length();
+
+  private static final LabelSerializer<Target> LABEL_STRINGIFIER = new LabelSerializer<Target>() {
+    @Override
+    public String serialize(Node<Target> node) {
+      return node.getLabel().getLabel().toString();
+    }
+  };
+}
diff --git a/src/main/java/com/google/devtools/build/lib/query2/output/OutputFormatter.java b/src/main/java/com/google/devtools/build/lib/query2/output/OutputFormatter.java
new file mode 100644
index 0000000000..b7a9d64ed4
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/query2/output/OutputFormatter.java
@@ -0,0 +1,486 @@
+// Copyright 2014 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.output;
+
+import com.google.common.base.Function;
+import com.google.common.base.Joiner;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Iterables;
+import com.google.common.collect.Sets;
+import com.google.devtools.build.lib.events.Location;
+import com.google.devtools.build.lib.graph.Digraph;
+import com.google.devtools.build.lib.graph.Node;
+import com.google.devtools.build.lib.packages.AggregatingAttributeMapper;
+import com.google.devtools.build.lib.packages.Attribute;
+import com.google.devtools.build.lib.packages.Rule;
+import com.google.devtools.build.lib.packages.Target;
+import com.google.devtools.build.lib.syntax.EvalUtils;
+import com.google.devtools.build.lib.syntax.Label;
+import com.google.devtools.build.lib.util.BinaryPredicate;
+import com.google.devtools.build.lib.util.Pair;
+import com.google.devtools.common.options.EnumConverter;
+
+import java.io.IOException;
+import java.io.PrintStream;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.LinkedHashSet;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+/**
+ * Interface for classes which order, format and print the result of a Blaze
+ * graph query.
+ */
+public abstract class OutputFormatter {
+
+  /**
+   * Discriminator for different kinds of OutputFormatter.
+   */
+  public enum Type {
+    LABEL,
+    LABEL_KIND,
+    BUILD,
+    MINRANK,
+    MAXRANK,
+    PACKAGE,
+    LOCATION,
+    GRAPH,
+    XML,
+    PROTO,
+    RECORD,
+  }
+
+  /**
+   * Where the value of an attribute comes from
+   */
+  protected enum AttributeValueSource {
+    RULE,     // Explicitly specified on the rule
+    PACKAGE,  // Package default
+    DEFAULT   // Rule class default
+  }
+
+  public static final Function<Node<Target>, Target> EXTRACT_NODE_LABEL =
+      new Function<Node<Target>, Target>() {
+        @Override
+        public Target apply(Node<Target> input) {
+          return input.getLabel();
+        }
+      };
+
+  /**
+   * Converter from strings to OutputFormatter.Type.
+   */
+  public static class Converter extends EnumConverter<Type> {
+    public Converter() { super(Type.class, "output formatter"); }
+  }
+
+  public static ImmutableList<OutputFormatter> getDefaultFormatters() {
+    return ImmutableList.of(
+        new LabelOutputFormatter(false),
+        new LabelOutputFormatter(true),
+        new BuildOutputFormatter(),
+        new MinrankOutputFormatter(),
+        new MaxrankOutputFormatter(),
+        new PackageOutputFormatter(),
+        new LocationOutputFormatter(),
+        new GraphOutputFormatter(),
+        new XmlOutputFormatter(),
+        new ProtoOutputFormatter());
+  }
+
+  public static String formatterNames(Iterable<OutputFormatter> formatters) {
+    return Joiner.on(", ").join(Iterables.transform(formatters,
+        new Function<OutputFormatter, String>() {
+          @Override
+          public String apply(OutputFormatter input) {
+            return input.getName();
+          }
+    }));
+  }
+
+  /**
+   * Returns the output formatter for the specified command-line options.
+   */
+  public static OutputFormatter getFormatter(
+      Iterable<OutputFormatter> formatters, String type) {
+    for (OutputFormatter formatter : formatters) {
+      if (formatter.getName().equals(type)) {
+        return formatter;
+      }
+    }
+
+    return null;
+  }
+
+  /**
+   * Given a set of query options, returns a BinaryPredicate suitable for
+   * passing to {@link Rule#getLabels()}, {@link XmlOutputFormatter}, etc.
+   */
+  public static BinaryPredicate<Rule, Attribute> getDependencyFilter(QueryOptions queryOptions) {
+    // TODO(bazel-team): Optimize: and(ALL_DEPS, x) -> x, etc.
+    return Rule.and(
+          queryOptions.includeHostDeps ? Rule.ALL_DEPS : Rule.NO_HOST_DEPS,
+          queryOptions.includeImplicitDeps ? Rule.ALL_DEPS : Rule.NO_IMPLICIT_DEPS);
+  }
+
+  /**
+   * Format the result (a set of target nodes implicitly ordered according to
+   * the graph maintained by the QueryEnvironment), and print it to "out".
+   */
+  public abstract void output(QueryOptions options, Digraph<Target> result, PrintStream out)
+      throws IOException;
+
+  /**
+   * Unordered output formatter (wrt. dependency ordering).
+   *
+   * <p>Formatters that support unordered output may be used when only the set of query results is
+   * requested but their ordering is irrelevant.
+   *
+   * <p>The benefit of using a unordered formatter is that we can save the potentially expensive
+   * subgraph extraction step before presenting the query results.
+   */
+  public interface UnorderedFormatter {
+    void outputUnordered(QueryOptions options, Iterable<Target> result, PrintStream out)
+        throws IOException;
+  }
+
+  /**
+   * Returns the user-visible name of the output formatter.
+   */
+  public abstract String getName();
+
+  /**
+   * An output formatter that prints the labels of the resulting target set in
+   * topological order, optionally with the target's kind.
+   */
+  private static class LabelOutputFormatter extends OutputFormatter implements UnorderedFormatter{
+
+    private final boolean showKind;
+
+    public LabelOutputFormatter(boolean showKind) {
+      this.showKind = showKind;
+    }
+
+    @Override
+    public String getName() {
+      return showKind ? "label_kind" : "label";
+    }
+
+    @Override
+    public void outputUnordered(QueryOptions options, Iterable<Target> result, PrintStream out) {
+      for (Target target : result) {
+        if (showKind) {
+          out.print(target.getTargetKind());
+          out.print(' ');
+        }
+        out.println(target.getLabel());
+      }
+    }
+
+    @Override
+    public void output(QueryOptions options, Digraph<Target> result, PrintStream out) {
+      Iterable<Target> ordered = Iterables.transform(
+          result.getTopologicalOrder(new TargetOrdering()), EXTRACT_NODE_LABEL);
+      outputUnordered(options, ordered, out);
+    }
+  }
+
+  /**
+   * An ordering of Targets based on the ordering of their labels.
+   */
+  static class TargetOrdering implements Comparator<Target> {
+    @Override
+    public int compare(Target o1, Target o2) {
+      return o1.getLabel().compareTo(o2.getLabel());
+    }
+  }
+
+  /**
+   * An output formatter that prints the names of the packages of the target
+   * set, in lexicographical order without duplicates.
+   */
+  private static class PackageOutputFormatter extends OutputFormatter implements
+      UnorderedFormatter {
+    @Override
+    public String getName() {
+      return "package";
+    }
+
+    @Override
+    public void outputUnordered(QueryOptions options, Iterable<Target> result, PrintStream out) {
+      Set<String> packageNames = Sets.newTreeSet();
+      for (Target target : result) {
+        packageNames.add(target.getLabel().getPackageName());
+      }
+      for (String packageName : packageNames) {
+        out.println(packageName);
+      }
+    }
+
+    @Override
+    public void output(QueryOptions options, Digraph<Target> result, PrintStream out) {
+      Iterable<Target> ordered = Iterables.transform(
+          result.getTopologicalOrder(new TargetOrdering()), EXTRACT_NODE_LABEL);
+      outputUnordered(options, ordered, out);
+    }
+  }
+
+  /**
+   * An output formatter that prints the labels of the targets, preceded by
+   * their locations and kinds, in topological order.  For output files, the
+   * location of the generating rule is given; for input files, the location of
+   * line 1 is given.
+   */
+  private static class LocationOutputFormatter extends OutputFormatter implements
+      UnorderedFormatter {
+    @Override
+    public String getName() {
+      return "location";
+    }
+
+    @Override
+    public void outputUnordered(QueryOptions options, Iterable<Target> result, PrintStream out) {
+      for (Target target : result) {
+        Location location = target.getLocation();
+        out.println(location.print()  + ": " + target.getTargetKind() + " " + target.getLabel());
+      }
+    }
+
+    @Override
+    public void output(QueryOptions options, Digraph<Target> result, PrintStream out) {
+      Iterable<Target> ordered = Iterables.transform(
+          result.getTopologicalOrder(new TargetOrdering()), EXTRACT_NODE_LABEL);
+      outputUnordered(options, ordered, out);
+    }
+  }
+
+  /**
+   * An output formatter that prints the generating rules using the syntax of
+   * the BUILD files. If multiple targets are generated by the same rule, it is
+   * printed only once.
+   */
+  private static class BuildOutputFormatter extends OutputFormatter implements UnorderedFormatter {
+    @Override
+    public String getName() {
+      return "build";
+    }
+
+    private void outputRule(Rule rule, PrintStream out) {
+      out.println(String.format("# %s", rule.getLocation()));
+      out.println(String.format("%s(", rule.getRuleClass()));
+      out.println(String.format("  name = \"%s\",", rule.getName()));
+
+      for (Attribute attr : rule.getAttributes()) {
+        Pair<Iterable<Object>, AttributeValueSource> values = getAttributeValues(rule, attr);
+        if (Iterables.size(values.first) != 1) {
+          continue;  // TODO(bazel-team): handle configurable attributes.
+        }
+        if (values.second != AttributeValueSource.RULE) {
+          continue;  // Don't print default values.
+        }
+        Object value = Iterables.getOnlyElement(values.first);
+        out.print(String.format("  %s = ", attr.getName()));
+        if (value instanceof Label) {
+          value = value.toString();
+        } else if (value instanceof List<?> && EvalUtils.isImmutable(value)) {
+          // Display it as a list (and not as a tuple). Attributes can never be tuples.
+          value = new ArrayList<>((List<?>) value);
+        }
+        EvalUtils.prettyPrintValue(value, out);
+        out.println(",");
+      }
+      out.println(String.format(")\n"));
+    }
+
+    @Override
+    public void outputUnordered(QueryOptions options, Iterable<Target> result, PrintStream out) {
+      Set<Label> printed = new HashSet<>();
+      for (Target target : result) {
+        Rule rule = target.getAssociatedRule();
+        if (rule == null || printed.contains(rule.getLabel())) {
+          continue;
+        }
+        outputRule(rule, out);
+        printed.add(rule.getLabel());
+      }
+    }
+
+    @Override
+    public void output(QueryOptions options, Digraph<Target> result, PrintStream out) {
+      Iterable<Target> ordered = Iterables.transform(
+          result.getTopologicalOrder(new TargetOrdering()), EXTRACT_NODE_LABEL);
+      outputUnordered(options, ordered, out);
+    }
+  }
+
+  /**
+   * An output formatter that prints the labels in minimum rank order, preceded by
+   * their rank number.  "Roots" have rank 0, their direct prerequisites have
+   * rank 1, etc.  All nodes in a cycle are considered of equal rank.  MINRANK
+   * shows the lowest rank for a given node, i.e. the length of the shortest
+   * path from a zero-rank node to it.
+   *
+   * If the result came from a <code>deps(x)</code> query, then the MINRANKs
+   * correspond to the shortest path from x to each of its prerequisites.
+   */
+  private static class MinrankOutputFormatter extends OutputFormatter {
+    @Override
+    public String getName() {
+      return "minrank";
+    }
+
+    @Override
+    public void output(QueryOptions options, Digraph<Target> result, PrintStream out) {
+      // getRoots() isn't defined for cyclic graphs, so in order to handle
+      // cycles correctly, we need work on the strong component graph, as
+      // cycles should be treated a "clump" of nodes all on the same rank.
+      // Graphs may contain cycles because there are errors in BUILD files.
+
+      Digraph<Set<Node<Target>>> scGraph = result.getStrongComponentGraph();
+      Set<Node<Set<Node<Target>>>> rankNodes = scGraph.getRoots();
+      Set<Node<Set<Node<Target>>>> seen = new HashSet<>();
+      seen.addAll(rankNodes);
+      for (int rank = 0; !rankNodes.isEmpty(); rank++) {
+        // Print out this rank:
+        for (Node<Set<Node<Target>>> xScc : rankNodes) {
+          for (Node<Target> x : xScc.getLabel()) {
+            out.println(rank + " " + x.getLabel().getLabel());
+          }
+        }
+
+        // Find the next rank:
+        Set<Node<Set<Node<Target>>>> nextRankNodes = new LinkedHashSet<>();
+        for (Node<Set<Node<Target>>> x : rankNodes) {
+          for (Node<Set<Node<Target>>> y : x.getSuccessors()) {
+            if (seen.add(y)) {
+              nextRankNodes.add(y);
+            }
+          }
+        }
+        rankNodes = nextRankNodes;
+      }
+    }
+  }
+
+  /**
+   * An output formatter that prints the labels in maximum rank order, preceded
+   * by their rank number.  "Roots" have rank 0, all other nodes have a rank
+   * which is one greater than the maximum rank of each of their predecessors.
+   * All nodes in a cycle are considered of equal rank.  MAXRANK shows the
+   * highest rank for a given node, i.e. the length of the longest non-cyclic
+   * path from a zero-rank node to it.
+   *
+   * If the result came from a <code>deps(x)</code> query, then the MAXRANKs
+   * correspond to the longest path from x to each of its prerequisites.
+   */
+  private static class MaxrankOutputFormatter extends OutputFormatter {
+    @Override
+    public String getName() {
+      return "maxrank";
+    }
+
+    @Override
+    public void output(QueryOptions options, Digraph<Target> result, PrintStream out) {
+      // In order to handle cycles correctly, we need work on the strong
+      // component graph, as cycles should be treated a "clump" of nodes all on
+      // the same rank. Graphs may contain cycles because there are errors in BUILD files.
+
+      // Dynamic programming algorithm:
+      // rank(x) = max(rank(p)) + 1 foreach p in preds(x)
+      // TODO(bazel-team): Move to Digraph.
+      class DP {
+        final Map<Node<Set<Node<Target>>>, Integer> ranks = new HashMap<>();
+
+        int rank(Node<Set<Node<Target>>> node) {
+          Integer rank = ranks.get(node);
+          if (rank == null) {
+            int maxPredRank = -1;
+            for (Node<Set<Node<Target>>> p : node.getPredecessors()) {
+              maxPredRank = Math.max(maxPredRank, rank(p));
+            }
+            rank = maxPredRank + 1;
+            ranks.put(node, rank);
+          }
+          return rank;
+        }
+      }
+      DP dp = new DP();
+
+      // Now sort by rank...
+      List<Pair<Integer, Label>> output = new ArrayList<>();
+      for (Node<Set<Node<Target>>> x : result.getStrongComponentGraph().getNodes()) {
+        int rank = dp.rank(x);
+        for (Node<Target> y : x.getLabel()) {
+          output.add(Pair.of(rank, y.getLabel().getLabel()));
+        }
+      }
+      Collections.sort(output, new Comparator<Pair<Integer, Label>>() {
+          @Override
+          public int compare(Pair<Integer, Label> x, Pair<Integer, Label> y) {
+            return x.first - y.first;
+          }
+        });
+
+      for (Pair<Integer, Label> pair : output) {
+        out.println(pair.first + " " + pair.second);
+      }
+    }
+  }
+
+  /**
+   * Returns the possible values of the specified attribute in the specified rule. For
+   * non-configured attributes, this is a single value. For configurable attributes, this
+   * may be multiple values.
+   *
+   * <p>This is needed because the visibility attribute is replaced with an empty list
+   * during package loading if it is public or private in order not to visit
+   * the package called 'visibility'.
+   *
+   * @return a pair, where the first value is the set of possible values and the
+   *     second is an enum that tells where the values come from (declared on the
+   *     rule, declared as a package level default or a
+   *     global default)
+   */
+  protected static Pair<Iterable<Object>, AttributeValueSource> getAttributeValues(
+      Rule rule, Attribute attr) {
+    List<Object> values = new LinkedList<>(); // Not an ImmutableList: may host null values.
+    AttributeValueSource source;
+
+    if (attr.getName().equals("visibility")) {
+      values.add(rule.getVisibility().getDeclaredLabels());
+      if (rule.isVisibilitySpecified()) {
+        source = AttributeValueSource.RULE;
+      } else if (rule.getPackage().isDefaultVisibilitySet()) {
+        source = AttributeValueSource.PACKAGE;
+      } else {
+        source = AttributeValueSource.DEFAULT;
+      }
+    } else {
+      for (Object o :
+          AggregatingAttributeMapper.of(rule).visitAttribute(attr.getName(), attr.getType())) {
+        values.add(o);
+      }
+      source = rule.isAttributeValueExplicitlySpecified(attr)
+          ? AttributeValueSource.RULE : AttributeValueSource.DEFAULT;
+    }
+
+    return Pair.of((Iterable<Object>) values, source);
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/query2/output/ProtoOutputFormatter.java b/src/main/java/com/google/devtools/build/lib/query2/output/ProtoOutputFormatter.java
new file mode 100644
index 0000000000..53fbb21023
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/query2/output/ProtoOutputFormatter.java
@@ -0,0 +1,491 @@
+// Copyright 2014 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.output;
+
+import static com.google.devtools.build.lib.packages.Type.BOOLEAN;
+import static com.google.devtools.build.lib.packages.Type.DISTRIBUTIONS;
+import static com.google.devtools.build.lib.packages.Type.FILESET_ENTRY_LIST;
+import static com.google.devtools.build.lib.packages.Type.INTEGER;
+import static com.google.devtools.build.lib.packages.Type.INTEGER_LIST;
+import static com.google.devtools.build.lib.packages.Type.LABEL;
+import static com.google.devtools.build.lib.packages.Type.LABEL_LIST;
+import static com.google.devtools.build.lib.packages.Type.LABEL_LIST_DICT;
+import static com.google.devtools.build.lib.packages.Type.LICENSE;
+import static com.google.devtools.build.lib.packages.Type.NODEP_LABEL;
+import static com.google.devtools.build.lib.packages.Type.NODEP_LABEL_LIST;
+import static com.google.devtools.build.lib.packages.Type.OUTPUT;
+import static com.google.devtools.build.lib.packages.Type.OUTPUT_LIST;
+import static com.google.devtools.build.lib.packages.Type.STRING;
+import static com.google.devtools.build.lib.packages.Type.STRING_DICT;
+import static com.google.devtools.build.lib.packages.Type.STRING_DICT_UNARY;
+import static com.google.devtools.build.lib.packages.Type.STRING_LIST;
+import static com.google.devtools.build.lib.packages.Type.STRING_LIST_DICT;
+import static com.google.devtools.build.lib.packages.Type.TRISTATE;
+import static com.google.devtools.build.lib.query2.proto.proto2api.Build.Target.Discriminator.GENERATED_FILE;
+import static com.google.devtools.build.lib.query2.proto.proto2api.Build.Target.Discriminator.PACKAGE_GROUP;
+import static com.google.devtools.build.lib.query2.proto.proto2api.Build.Target.Discriminator.RULE;
+import static com.google.devtools.build.lib.query2.proto.proto2api.Build.Target.Discriminator.SOURCE_FILE;
+
+import com.google.common.collect.Iterables;
+import com.google.devtools.build.lib.events.Location;
+import com.google.devtools.build.lib.graph.Digraph;
+import com.google.devtools.build.lib.packages.Attribute;
+import com.google.devtools.build.lib.packages.InputFile;
+import com.google.devtools.build.lib.packages.License;
+import com.google.devtools.build.lib.packages.OutputFile;
+import com.google.devtools.build.lib.packages.PackageGroup;
+import com.google.devtools.build.lib.packages.ProtoUtils;
+import com.google.devtools.build.lib.packages.Rule;
+import com.google.devtools.build.lib.packages.Target;
+import com.google.devtools.build.lib.packages.TriState;
+import com.google.devtools.build.lib.query2.FakeSubincludeTarget;
+import com.google.devtools.build.lib.query2.output.OutputFormatter.UnorderedFormatter;
+import com.google.devtools.build.lib.query2.proto.proto2api.Build;
+import com.google.devtools.build.lib.syntax.FilesetEntry;
+import com.google.devtools.build.lib.syntax.GlobCriteria;
+import com.google.devtools.build.lib.syntax.GlobList;
+import com.google.devtools.build.lib.syntax.Label;
+import com.google.devtools.build.lib.syntax.SkylarkEnvironment;
+import com.google.devtools.build.lib.util.BinaryPredicate;
+
+import java.io.IOException;
+import java.io.PrintStream;
+import java.util.Collection;
+import java.util.List;
+import java.util.Map;
+
+/**
+ * An output formatter that outputs a protocol buffer representation
+ * of a query result and outputs the proto bytes to the output print stream.
+ * By taking the bytes and calling {@code mergeFrom()} on a
+ * {@code Build.QueryResult} object the full result can be reconstructed.
+ */
+public class ProtoOutputFormatter extends OutputFormatter implements UnorderedFormatter {
+
+  /**
+   * A special attribute name for the rule implementation hash code.
+   */
+  public static final String RULE_IMPLEMENTATION_HASH_ATTR_NAME = "$rule_implementation_hash";
+
+  private BinaryPredicate<Rule, Attribute> dependencyFilter;
+
+  protected void setDependencyFilter(QueryOptions options) {
+    this.dependencyFilter = OutputFormatter.getDependencyFilter(options);
+  }
+
+  @Override
+  public String getName() {
+    return "proto";
+  }
+
+  @Override
+  public void outputUnordered(QueryOptions options, Iterable<Target> result, PrintStream out)
+      throws IOException {
+    setDependencyFilter(options);
+
+    Build.QueryResult.Builder queryResult = Build.QueryResult.newBuilder();
+    for (Target target : result) {
+      addTarget(queryResult, target);
+    }
+
+    queryResult.build().writeTo(out);
+  }
+
+  @Override
+  public void output(QueryOptions options, Digraph<Target> result, PrintStream out)
+      throws IOException {
+    outputUnordered(options, result.getLabels(), out);
+  }
+
+  /**
+   * Add the target to the query result.
+   * @param queryResult The query result that contains all rule, input and
+   *   output targets.
+   * @param target The query target being converted to a protocol buffer.
+   */
+  private void addTarget(Build.QueryResult.Builder queryResult, Target target) {
+    queryResult.addTarget(toTargetProtoBuffer(target));
+  }
+
+  /**
+   * Converts a logical Target object into a Target protobuffer.
+   */
+  protected Build.Target toTargetProtoBuffer(Target target) {
+    Build.Target.Builder targetPb = Build.Target.newBuilder();
+
+    String location = target.getLocation().print();
+    if (target instanceof Rule) {
+      Rule rule = (Rule) target;
+      Build.Rule.Builder rulePb = Build.Rule.newBuilder()
+          .setName(rule.getLabel().toString())
+          .setRuleClass(rule.getRuleClass())
+          .setLocation(location);
+
+      for (Attribute attr : rule.getAttributes()) {
+        addAttributeToProto(rulePb, attr, getAttributeValues(rule, attr).first, null,
+            rule.isAttributeValueExplicitlySpecified(attr), false);
+      }
+
+      SkylarkEnvironment env = rule.getRuleClassObject().getRuleDefinitionEnvironment();
+      if (env != null) {
+        // The RuleDefinitionEnvironment is always defined for Skylark rules and
+        // always null for non Skylark rules.
+        rulePb.addAttribute(
+            Build.Attribute.newBuilder()
+                .setName(RULE_IMPLEMENTATION_HASH_ATTR_NAME)
+                .setType(ProtoUtils.getDiscriminatorFromType(
+                    com.google.devtools.build.lib.packages.Type.STRING))
+                .setStringValue(env.getTransitiveFileContentHashCode()));
+      }
+
+      // Include explicit elements for all direct inputs and outputs of a rule;
+      // this goes beyond what is available from the attributes above, since it
+      // may also (depending on options) include implicit outputs,
+      // host-configuration outputs, and default values.
+      for (Label label : rule.getLabels(dependencyFilter)) {
+        rulePb.addRuleInput(label.toString());
+      }
+      for (OutputFile outputFile : rule.getOutputFiles()) {
+        Label fileLabel = outputFile.getLabel();
+        rulePb.addRuleOutput(fileLabel.toString());
+      }
+      for (String feature : rule.getFeatures()) {
+        rulePb.addDefaultSetting(feature);
+      }
+
+      targetPb.setType(RULE);
+      targetPb.setRule(rulePb);
+    } else if (target instanceof OutputFile) {
+      OutputFile outputFile = (OutputFile) target;
+      Label label = outputFile.getLabel();
+
+      Rule generatingRule = outputFile.getGeneratingRule();
+      Build.GeneratedFile output = Build.GeneratedFile.newBuilder()
+          .setLocation(location)
+          .setGeneratingRule(generatingRule.getLabel().toString())
+          .setName(label.toString())
+          .build();
+
+      targetPb.setType(GENERATED_FILE);
+      targetPb.setGeneratedFile(output);
+    } else if (target instanceof InputFile) {
+      InputFile inputFile = (InputFile) target;
+      Label label = inputFile.getLabel();
+
+      Build.SourceFile.Builder input = Build.SourceFile.newBuilder()
+          .setLocation(location)
+          .setName(label.toString());
+
+      if (inputFile.getName().equals("BUILD")) {
+        for (Label subinclude : inputFile.getPackage().getSubincludeLabels()) {
+          input.addSubinclude(subinclude.toString());
+        }
+
+        for (Label skylarkFileDep : inputFile.getPackage().getSkylarkFileDependencies()) {
+          input.addSubinclude(skylarkFileDep.toString());
+        }
+
+        for (String feature : inputFile.getPackage().getFeatures()) {
+          input.addFeature(feature);
+        }
+      }
+
+      for (Label visibilityDependency : target.getVisibility().getDependencyLabels()) {
+        input.addPackageGroup(visibilityDependency.toString());
+      }
+
+      for (Label visibilityDeclaration : target.getVisibility().getDeclaredLabels()) {
+        input.addVisibilityLabel(visibilityDeclaration.toString());
+      }
+
+      targetPb.setType(SOURCE_FILE);
+      targetPb.setSourceFile(input);
+    } else if (target instanceof FakeSubincludeTarget) {
+      Label label = target.getLabel();
+      Build.SourceFile input = Build.SourceFile.newBuilder()
+          .setLocation(location)
+          .setName(label.toString())
+          .build();
+
+      targetPb.setType(SOURCE_FILE);
+      targetPb.setSourceFile(input);
+    } else if (target instanceof PackageGroup) {
+      PackageGroup packageGroup = (PackageGroup) target;
+      Build.PackageGroup.Builder packageGroupPb = Build.PackageGroup.newBuilder()
+          .setName(packageGroup.getLabel().toString());
+      for (String containedPackage : packageGroup.getContainedPackages()) {
+        packageGroupPb.addContainedPackage(containedPackage);
+      }
+      for (Label include : packageGroup.getIncludes()) {
+        packageGroupPb.addIncludedPackageGroup(include.toString());
+      }
+
+      targetPb.setType(PACKAGE_GROUP);
+      targetPb.setPackageGroup(packageGroupPb);
+    } else {
+      throw new IllegalArgumentException(target.toString());
+    }
+
+    return targetPb.build();
+  }
+
+  /**
+   * Adds the serialized version of the specified attribute to the specified message.
+   *
+   * @param rulePb the message to amend
+   * @param attr the attribute to add
+   * @param value the possible values of the attribute (can be a multi-value list for
+   *              configurable attributes)
+   * @param location the location of the attribute in the source file
+   * @param explicitlySpecified whether the attribute was explicitly specified or not
+   * @param includeGlobs add glob expression for attributes that contain them
+   */
+  @SuppressWarnings("unchecked")
+  public static void addAttributeToProto(
+      Build.Rule.Builder rulePb, Attribute attr, Iterable<Object> values,
+      Location location, Boolean explicitlySpecified, boolean includeGlobs) {
+    // Get the attribute type.  We need to convert and add appropriately
+    com.google.devtools.build.lib.packages.Type<?> type = attr.getType();
+
+    Build.Attribute.Builder attrPb = Build.Attribute.newBuilder();
+
+    // Set the type, name and source
+    attrPb.setName(attr.getName());
+    attrPb.setType(ProtoUtils.getDiscriminatorFromType(type));
+
+    if (location != null) {
+      attrPb.setParseableLocation(serialize(location));
+    }
+
+    if (explicitlySpecified != null) {
+      attrPb.setExplicitlySpecified(explicitlySpecified);
+    }
+
+    // Convenience binding for single-value attributes. Because those attributes can only
+    // have a single value, when we encounter configurable versions of them we need to
+    // react somehow to having multiple possible values to report. We currently just
+    // refrain from setting *any* value in that scenario. This variable is set to null
+    // to indicate that scenario.
+    Object singleAttributeValue = Iterables.size(values) == 1
+        ? Iterables.getOnlyElement(values)
+        : null;
+
+    /*
+     * Set the appropriate type and value.  Since string and string list store
+     * values for multiple types, use the toString() method on the objects
+     * instead of casting them.  Note that Boolean and TriState attributes have
+     * both an integer and string representation.
+     */
+    if (type == INTEGER) {
+      if (singleAttributeValue != null) {
+        attrPb.setIntValue((Integer) singleAttributeValue);
+      }
+    } else if (type == STRING || type == LABEL || type == NODEP_LABEL || type == OUTPUT) {
+      if (singleAttributeValue != null) {
+        attrPb.setStringValue(singleAttributeValue.toString());
+      }
+    } else if (type == STRING_LIST || type == LABEL_LIST || type == NODEP_LABEL_LIST
+        || type == OUTPUT_LIST || type == DISTRIBUTIONS) {
+      for (Object value : values) {
+        for (Object entry : (Collection<?>) value) {
+          attrPb.addStringListValue(entry.toString());
+        }
+      }
+    } else if (type == INTEGER_LIST) {
+      for (Object value : values) {
+        for (Integer entry : (Collection<Integer>) value) {
+          attrPb.addIntListValue(entry);
+        }
+      }
+    } else if (type == BOOLEAN) {
+      if (singleAttributeValue != null) {
+        if ((Boolean) singleAttributeValue) {
+          attrPb.setStringValue("true");
+          attrPb.setBooleanValue(true);
+        } else {
+          attrPb.setStringValue("false");
+          attrPb.setBooleanValue(false);
+        }
+        // This maintains partial backward compatibility for external users of the
+        // protobuf that were expecting an integer field and not a true boolean.
+        attrPb.setIntValue((Boolean) singleAttributeValue ? 1 : 0);
+      }
+    } else if (type == TRISTATE) {
+      if (singleAttributeValue != null) {
+        switch ((TriState) singleAttributeValue) {
+          case AUTO:
+            attrPb.setIntValue(-1);
+            attrPb.setStringValue("auto");
+            attrPb.setTristateValue(Build.Attribute.Tristate.AUTO);
+            break;
+          case NO:
+            attrPb.setIntValue(0);
+            attrPb.setStringValue("no");
+            attrPb.setTristateValue(Build.Attribute.Tristate.NO);
+            break;
+          case YES:
+            attrPb.setIntValue(1);
+            attrPb.setStringValue("yes");
+            attrPb.setTristateValue(Build.Attribute.Tristate.YES);
+            break;
+          default:
+            throw new IllegalStateException("Execpted AUTO/NO/YES to cover all possible cases");
+        }
+      }
+    } else if (type == LICENSE) {
+      if (singleAttributeValue != null) {
+        License license = (License) singleAttributeValue;
+        Build.License.Builder licensePb = Build.License.newBuilder();
+        for (License.LicenseType licenseType : license.getLicenseTypes()) {
+          licensePb.addLicenseType(licenseType.toString());
+        }
+        for (Label exception : license.getExceptions()) {
+          licensePb.addException(exception.toString());
+        }
+        attrPb.setLicense(licensePb);
+      }
+    } else if (type == STRING_DICT) {
+      // TODO(bazel-team): support better de-duping here and in other dictionaries.
+      for (Object value : values) {
+      Map<String, String> dict = (Map<String, String>) value;
+        for (Map.Entry<String, String> keyValueList : dict.entrySet()) {
+          Build.StringDictEntry entry = Build.StringDictEntry.newBuilder()
+              .setKey(keyValueList.getKey())
+              .setValue(keyValueList.getValue())
+              .build();
+          attrPb.addStringDictValue(entry);
+        }
+      }
+    } else if (type == STRING_DICT_UNARY) {
+      for (Object value : values) {
+        Map<String, String> dict = (Map<String, String>) value;
+        for (Map.Entry<String, String> dictEntry : dict.entrySet()) {
+          Build.StringDictUnaryEntry entry = Build.StringDictUnaryEntry.newBuilder()
+              .setKey(dictEntry.getKey())
+              .setValue(dictEntry.getValue())
+              .build();
+          attrPb.addStringDictUnaryValue(entry);
+        }
+      }
+    } else if (type == STRING_LIST_DICT) {
+      for (Object value : values) {
+        Map<String, List<String>> dict = (Map<String, List<String>>) value;
+        for (Map.Entry<String, List<String>> dictEntry : dict.entrySet()) {
+          Build.StringListDictEntry.Builder entry = Build.StringListDictEntry.newBuilder()
+              .setKey(dictEntry.getKey());
+          for (Object dictEntryValue : dictEntry.getValue()) {
+            entry.addValue(dictEntryValue.toString());
+          }
+          attrPb.addStringListDictValue(entry);
+        }
+      }
+    } else if (type == LABEL_LIST_DICT) {
+      for (Object value : values) {
+        Map<String, List<Label>> dict = (Map<String, List<Label>>) value;
+        for (Map.Entry<String, List<Label>> dictEntry : dict.entrySet()) {
+          Build.LabelListDictEntry.Builder entry = Build.LabelListDictEntry.newBuilder()
+              .setKey(dictEntry.getKey());
+          for (Object dictEntryValue : dictEntry.getValue()) {
+            entry.addValue(dictEntryValue.toString());
+          }
+          attrPb.addLabelListDictValue(entry);
+        }
+      }
+    } else if (type == FILESET_ENTRY_LIST) {
+      for (Object value : values) {
+        List<FilesetEntry> filesetEntries = (List<FilesetEntry>) value;
+        for (FilesetEntry filesetEntry : filesetEntries) {
+          Build.FilesetEntry.Builder filesetEntryPb = Build.FilesetEntry.newBuilder()
+              .setSource(filesetEntry.getSrcLabel().toString())
+              .setDestinationDirectory(filesetEntry.getDestDir().getPathString())
+              .setSymlinkBehavior(symlinkBehaviorToPb(filesetEntry.getSymlinkBehavior()))
+              .setStripPrefix(filesetEntry.getStripPrefix())
+              .setFilesPresent(filesetEntry.getFiles() != null);
+
+          if (filesetEntry.getFiles() != null) {
+            for (Label file : filesetEntry.getFiles()) {
+              filesetEntryPb.addFile(file.toString());
+            }
+          }
+
+          if (filesetEntry.getExcludes() != null) {
+            for (String exclude : filesetEntry.getExcludes()) {
+              filesetEntryPb.addExclude(exclude);
+            }
+          }
+
+          attrPb.addFilesetListValue(filesetEntryPb);
+        }
+      }
+    } else {
+      throw new IllegalStateException("Unknown type: " + type);
+    }
+
+    if (includeGlobs) {
+      for (Object value : values) {
+        if (value instanceof GlobList<?>) {
+          GlobList<?> globList = (GlobList<?>) value;
+
+          for (GlobCriteria criteria : globList.getCriteria()) {
+            Build.GlobCriteria.Builder criteriaPb = Build.GlobCriteria.newBuilder()
+                .setGlob(criteria.isGlob());
+            for (String include : criteria.getIncludePatterns()) {
+              criteriaPb.addInclude(include);
+            }
+            for (String exclude : criteria.getExcludePatterns()) {
+              criteriaPb.addExclude(exclude);
+            }
+
+            attrPb.addGlobCriteria(criteriaPb);
+          }
+        }
+      }
+    }
+
+    rulePb.addAttribute(attrPb);
+  }
+
+  // This is needed because I do not want to use the SymlinkBehavior from the
+  // protocol buffer all over the place, so there are two classes that do
+  // essentially the same thing.
+  private static Build.FilesetEntry.SymlinkBehavior symlinkBehaviorToPb(
+      FilesetEntry.SymlinkBehavior symlinkBehavior) {
+    switch (symlinkBehavior) {
+      case COPY:
+        return Build.FilesetEntry.SymlinkBehavior.COPY;
+      case DEREFERENCE:
+        return Build.FilesetEntry.SymlinkBehavior.DEREFERENCE;
+      default:
+        throw new AssertionError("Unhandled FilesetEntry.SymlinkBehavior");
+    }
+  }
+
+  private static Build.Location serialize(Location location) {
+    Build.Location.Builder result = Build.Location.newBuilder();
+
+    result.setStartOffset(location.getStartOffset());
+    if (location.getStartLineAndColumn() != null) {
+      result.setStartLine(location.getStartLineAndColumn().getLine());
+      result.setStartColumn(location.getStartLineAndColumn().getColumn());
+    }
+
+    result.setEndOffset(location.getEndOffset());
+    if (location.getEndLineAndColumn() != null) {
+      result.setEndLine(location.getEndLineAndColumn().getLine());
+      result.setEndColumn(location.getEndLineAndColumn().getColumn());
+    }
+
+    return result.build();
+  }
+}
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
new file mode 100644
index 0000000000..810e8c77e9
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/query2/output/QueryOptions.java
@@ -0,0 +1,136 @@
+// Copyright 2014 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.output;
+
+import com.google.devtools.build.lib.query2.engine.QueryEnvironment.Setting;
+import com.google.devtools.common.options.Option;
+import com.google.devtools.common.options.OptionsBase;
+
+import java.util.EnumSet;
+import java.util.Set;
+
+/**
+ * Command-line options for the Blaze query language, revision 2.
+ */
+public class QueryOptions extends OptionsBase {
+
+  @Option(name = "output",
+      defaultValue = "label",
+      category = "query",
+      help = "The format in which the query results should be printed."
+          + " Allowed values are: label, label_kind, minrank, maxrank, package, location, graph,"
+          + " xml, proto, record.")
+  public String outputFormat;
+
+  @Option(name = "order_results",
+      defaultValue = "true",
+      category = "query",
+      help = "Output the results in dependency-ordered (default) or unordered fashion. The"
+          + " unordered output is faster but only supported when --output is one of label,"
+          + " label_kind, location, package, proto, record, xml.")
+  public boolean orderResults;
+
+  @Option(name = "keep_going",
+      abbrev = 'k',
+      defaultValue = "false",
+      category = "strategy",
+      help = "Continue as much as possible after an error.  While the "
+          + "target that failed, and those that depend on it, cannot be "
+          + "analyzed, other prerequisites of these "
+          + "targets can be.")
+  public boolean keepGoing;
+
+  @Option(name = "loading_phase_threads",
+      defaultValue = "200",
+      category = "undocumented",
+      help = "Number of parallel threads to use for the loading phase.")
+  public int loadingPhaseThreads;
+
+  @Option(name = "host_deps",
+      defaultValue = "true",
+      category = "query",
+          help = "If enabled, dependencies on 'host configuration' targets will be included in "
+          + "the dependency graph over which the query operates.  A 'host configuration' "
+          + "dependency edge, such as the one from any 'proto_library' rule to the Protocol "
+          + "Compiler, usually points to a tool executed during the build (on the host machine) "
+          + "rather than a part of the same 'target' program.  Queries whose purpose is to "
+          + "discover the set of things needed during a build will typically enable this option; "
+          + "queries aimed at revealing the structure of a single program will typically  disable "
+          + "this option.")
+  public boolean includeHostDeps;
+
+  @Option(name = "implicit_deps",
+      defaultValue = "true",
+      category = "query",
+      help = "If enabled, implicit dependencies will be included in the dependency graph over "
+          + "which the query operates. An implicit dependency is one that is not explicitly "
+          + "specified in the BUILD file but added by blaze.")
+  public boolean includeImplicitDeps;
+
+  @Option(name = "graph:node_limit",
+      defaultValue = "512",
+      category = "query",
+      help = "The maximum length of the label string for a graph node in the output.  Longer labels"
+           + " will be truncated; -1 means no truncation.  This option is only applicable to"
+           + " --output=graph.")
+  public int graphNodeStringLimit;
+
+  @Option(name = "graph:factored",
+      defaultValue = "true",
+      category = "query",
+      help = "If true, then the graph will be emitted 'factored', i.e. "
+          + "topologically-equivalent nodes will be merged together and their "
+          + "labels concatenated.    This option is only applicable to "
+          + "--output=graph.")
+  public boolean graphFactored;
+
+  @Option(name = "xml:line_numbers",
+      defaultValue = "true",
+      category = "query",
+      help = "If true, XML output contains line numbers.  Disabling this option "
+          + "may make diffs easier to read.  This option is only applicable to "
+          + "--output=xml.")
+  public boolean xmlLineNumbers;
+
+  @Option(name = "xml:default_values",
+      defaultValue = "false",
+      category = "query",
+      help = "If true, rule attributes whose value is not explicitly specified "
+          + "in the BUILD file are printed; otherwise they are omitted.")
+  public boolean xmlShowDefaultValues;
+
+  @Option(name = "strict_test_suite",
+      defaultValue = "false",
+      category = "query",
+      help = "If true, the tests() expression gives an error if it encounters a test_suite "
+          + "containing non-test targets.")
+  public boolean strictTestSuite;
+
+  /**
+   * Return the current options as a set of QueryEnvironment settings.
+   */
+  public Set<Setting> toSettings() {
+    Set<Setting> settings = EnumSet.noneOf(Setting.class);
+    if (strictTestSuite) {
+      settings.add(Setting.TESTS_EXPRESSION_STRICT);
+    }
+    if (!includeHostDeps) {
+      settings.add(Setting.NO_HOST_DEPS);
+    }
+    if (!includeImplicitDeps) {
+      settings.add(Setting.NO_IMPLICIT_DEPS);
+    }
+    return settings;
+  }
+}
diff --git a/src/main/java/com/google/devtools/build/lib/query2/output/XmlOutputFormatter.java b/src/main/java/com/google/devtools/build/lib/query2/output/XmlOutputFormatter.java
new file mode 100644
index 0000000000..c01c90e465
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/query2/output/XmlOutputFormatter.java
@@ -0,0 +1,352 @@
+// Copyright 2014 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.output;
+
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Iterables;
+import com.google.devtools.build.lib.graph.Digraph;
+import com.google.devtools.build.lib.packages.Attribute;
+import com.google.devtools.build.lib.packages.InputFile;
+import com.google.devtools.build.lib.packages.License;
+import com.google.devtools.build.lib.packages.OutputFile;
+import com.google.devtools.build.lib.packages.PackageGroup;
+import com.google.devtools.build.lib.packages.Rule;
+import com.google.devtools.build.lib.packages.Target;
+import com.google.devtools.build.lib.query2.FakeSubincludeTarget;
+import com.google.devtools.build.lib.syntax.FilesetEntry;
+import com.google.devtools.build.lib.syntax.Label;
+import com.google.devtools.build.lib.util.BinaryPredicate;
+import com.google.devtools.build.lib.util.Pair;
+
+import org.w3c.dom.DOMException;
+import org.w3c.dom.Document;
+import org.w3c.dom.Element;
+
+import java.io.PrintStream;
+import java.util.Collection;
+import java.util.HashSet;
+import java.util.Map;
+import java.util.Set;
+
+import javax.xml.parsers.DocumentBuilderFactory;
+import javax.xml.parsers.ParserConfigurationException;
+import javax.xml.transform.OutputKeys;
+import javax.xml.transform.Transformer;
+import javax.xml.transform.TransformerException;
+import javax.xml.transform.TransformerFactory;
+import javax.xml.transform.TransformerFactoryConfigurationError;
+import javax.xml.transform.dom.DOMSource;
+import javax.xml.transform.stream.StreamResult;
+
+/**
+ * An output formatter that prints the result as XML.
+ */
+class XmlOutputFormatter extends OutputFormatter implements OutputFormatter.UnorderedFormatter {
+
+  private boolean xmlLineNumbers;
+  private boolean showDefaultValues;
+  private BinaryPredicate<Rule, Attribute> dependencyFilter;
+
+  @Override
+  public String getName() {
+    return "xml";
+  }
+
+  @Override
+  public void outputUnordered(QueryOptions options, Iterable<Target> result, PrintStream out) {
+    this.xmlLineNumbers = options.xmlLineNumbers;
+    this.showDefaultValues = options.xmlShowDefaultValues;
+    this.dependencyFilter = OutputFormatter.getDependencyFilter(options);
+
+    Document doc;
+    try {
+      DocumentBuilderFactory factory = DocumentBuilderFactory.newInstance();
+      doc = factory.newDocumentBuilder().newDocument();
+    } catch (ParserConfigurationException e) {
+      // This shouldn't be possible: all the configuration is hard-coded.
+      throw new IllegalStateException("XML output failed",  e);
+    }
+    doc.setXmlVersion("1.1");
+    Element queryElem = doc.createElement("query");
+    queryElem.setAttribute("version", "2");
+    doc.appendChild(queryElem);
+    for (Target target : result) {
+      queryElem.appendChild(createTargetElement(doc, target));
+    }
+    try {
+      Transformer transformer = TransformerFactory.newInstance().newTransformer();
+      transformer.setOutputProperty(OutputKeys.INDENT, "yes");
+      transformer.transform(new DOMSource(doc), new StreamResult(out));
+    } catch (TransformerFactoryConfigurationError | TransformerException e) {
+      // This shouldn't be possible: all the configuration is hard-coded.
+      throw new IllegalStateException("XML output failed",  e);
+    }
+  }
+
+  @Override
+  public void output(QueryOptions options, Digraph<Target> result, PrintStream out) {
+    Iterable<Target> ordered = Iterables.transform(
+        result.getTopologicalOrder(new TargetOrdering()), OutputFormatter.EXTRACT_NODE_LABEL);
+    outputUnordered(options, ordered, out);
+  }
+
+  /**
+   * Creates and returns a new DOM tree for the specified build target.
+   *
+   * XML structure:
+   * - element tag is &lt;source-file>, &lt;generated-file> or &lt;rule
+   *   class="cc_library">, following the terminology of
+   *   {@link Target#getTargetKind()}.
+   * - 'name' attribute is target's label.
+   * - 'location' attribute is consistent with output of --output location.
+   * - rule attributes are represented in the DOM structure.
+   */
+  private Element createTargetElement(Document doc, Target target) {
+    Element elem;
+    if (target instanceof Rule) {
+      Rule rule = (Rule) target;
+      elem = doc.createElement("rule");
+      elem.setAttribute("class", rule.getRuleClass());
+      for (Attribute attr: rule.getAttributes()) {
+        Pair<Iterable<Object>, AttributeValueSource> values = getAttributeValues(rule, attr);
+        if (values.second == AttributeValueSource.RULE || showDefaultValues) {
+          Element attrElem = createValueElement(doc, attr.getType(), values.first);
+          attrElem.setAttribute("name", attr.getName());
+          elem.appendChild(attrElem);
+        }
+      }
+
+      // Include explicit elements for all direct inputs and outputs of a rule;
+      // this goes beyond what is available from the attributes above, since it
+      // may also (depending on options) include implicit outputs,
+      // host-configuration outputs, and default values.
+      for (Label label : rule.getLabels(dependencyFilter)) {
+        Element inputElem = doc.createElement("rule-input");
+        inputElem.setAttribute("name", label.toString());
+        elem.appendChild(inputElem);
+      }
+      for (OutputFile outputFile: rule.getOutputFiles()) {
+        Element outputElem = doc.createElement("rule-output");
+        outputElem.setAttribute("name", outputFile.getLabel().toString());
+        elem.appendChild(outputElem);
+      }
+      for (String feature : rule.getFeatures()) {
+        Element outputElem = doc.createElement("rule-default-setting");
+        outputElem.setAttribute("name", feature);
+        elem.appendChild(outputElem);
+      }
+    } else if (target instanceof PackageGroup) {
+      PackageGroup packageGroup = (PackageGroup) target;
+      elem = doc.createElement("package-group");
+      elem.setAttribute("name", packageGroup.getName());
+      Element includes = createValueElement(doc,
+          com.google.devtools.build.lib.packages.Type.LABEL_LIST,
+          packageGroup.getIncludes());
+      includes.setAttribute("name", "includes");
+      elem.appendChild(includes);
+      Element packages = createValueElement(doc,
+          com.google.devtools.build.lib.packages.Type.STRING_LIST,
+          packageGroup.getContainedPackages());
+      packages.setAttribute("name", "packages");
+      elem.appendChild(packages);
+    } else if (target instanceof OutputFile) {
+      OutputFile outputFile = (OutputFile) target;
+      elem = doc.createElement("generated-file");
+      elem.setAttribute("generating-rule",
+                        outputFile.getGeneratingRule().getLabel().toString());
+    } else if (target instanceof InputFile) {
+      elem = doc.createElement("source-file");
+      InputFile inputFile = (InputFile) target;
+      if (inputFile.getName().equals("BUILD")) {
+        addSubincludedFilesToElement(doc, elem, inputFile);
+        addSkylarkFilesToElement(doc, elem, inputFile);
+        addFeaturesToElement(doc, elem, inputFile);
+      }
+
+      addPackageGroupsToElement(doc, elem, inputFile);
+    } else if (target instanceof FakeSubincludeTarget) {
+      elem = doc.createElement("source-file");
+    } else {
+      throw new IllegalArgumentException(target.toString());
+    }
+
+    elem.setAttribute("name", target.getLabel().toString());
+    String location = target.getLocation().print();
+    if (!xmlLineNumbers) {
+      int firstColon = location.indexOf(":");
+      if (firstColon != -1) {
+        location = location.substring(0, firstColon);
+      }
+    }
+
+    elem.setAttribute("location", location);
+    return elem;
+  }
+
+  private void addPackageGroupsToElement(Document doc, Element parent, Target target) {
+    for (Label visibilityDependency : target.getVisibility().getDependencyLabels()) {
+      Element elem = doc.createElement("package-group");
+      elem.setAttribute("name", visibilityDependency.toString());
+      parent.appendChild(elem);
+    }
+
+    for (Label visibilityDeclaration : target.getVisibility().getDeclaredLabels()) {
+      Element elem = doc.createElement("visibility-label");
+      elem.setAttribute("name", visibilityDeclaration.toString());
+      parent.appendChild(elem);
+    }
+  }
+
+  private void addFeaturesToElement(Document doc, Element parent, InputFile inputFile) {
+    for (String feature : inputFile.getPackage().getFeatures()) {
+      Element elem = doc.createElement("feature");
+      elem.setAttribute("name", feature);
+      parent.appendChild(elem);
+    }
+  }
+
+  private void addSubincludedFilesToElement(Document doc, Element parent, InputFile inputFile) {
+    for (Label subinclude : inputFile.getPackage().getSubincludeLabels()) {
+      Element elem = doc.createElement("subinclude");
+      elem.setAttribute("name", subinclude.toString());
+      parent.appendChild(elem);
+    }
+  }
+
+  private void addSkylarkFilesToElement(Document doc, Element parent, InputFile inputFile) {
+    for (Label skylarkFileDep : inputFile.getPackage().getSkylarkFileDependencies()) {
+      Element elem = doc.createElement("load");
+      elem.setAttribute("name", skylarkFileDep.toString());
+      parent.appendChild(elem);
+    }
+  }
+
+  /**
+   * Creates and returns a new DOM tree for the specified attribute values.
+   * For non-configurable attributes, this is a single value. For configurable
+   * attributes, this contains one value for each configuration.
+   * (Only toplevel values are named attributes; list elements are unnamed.)
+   *
+   * <p>In the case of configurable attributes, multi-value attributes (e.g. lists)
+   * merge all configured lists into an aggregate flattened list. Single-value attributes
+   * simply refrain to set a value and annotate the DOM element as configurable.
+   *
+   * <P>(The ungainly qualified class name is required to avoid ambiguity with
+   * OutputFormatter.Type.)
+   */
+  private static Element createValueElement(Document doc,
+      com.google.devtools.build.lib.packages.Type<?> type, Iterable<Object> values) {
+    // "Import static" with method scope:
+    com.google.devtools.build.lib.packages.Type<?>
+        FILESET_ENTRY = com.google.devtools.build.lib.packages.Type.FILESET_ENTRY,
+        LABEL_LIST    = com.google.devtools.build.lib.packages.Type.LABEL_LIST,
+        LICENSE       = com.google.devtools.build.lib.packages.Type.LICENSE,
+        STRING_LIST   = com.google.devtools.build.lib.packages.Type.STRING_LIST;
+
+    final Element elem;
+    final boolean hasMultipleValues = Iterables.size(values) > 1;
+    com.google.devtools.build.lib.packages.Type<?> elemType = type.getListElementType();
+    if (elemType != null) { // it's a list (includes "distribs")
+      elem = doc.createElement("list");
+      for (Object value : values) {
+        for (Object elemValue : (Collection<?>) value) {
+          elem.appendChild(createValueElement(doc, elemType, elemValue));
+        }
+      }
+    } else if (type instanceof com.google.devtools.build.lib.packages.Type.DictType) {
+      Set<Object> visitedValues = new HashSet<>();
+      elem = doc.createElement("dict");
+      com.google.devtools.build.lib.packages.Type.DictType<?, ?> dictType =
+          (com.google.devtools.build.lib.packages.Type.DictType<?, ?>) type;
+      for (Object value : values) {
+        for (Map.Entry<?, ?> entry : ((Map<?, ?>) value).entrySet()) {
+          if (visitedValues.add(entry.getKey())) {
+            Element pairElem = doc.createElement("pair");
+            elem.appendChild(pairElem);
+            pairElem.appendChild(createValueElement(doc,
+                    dictType.getKeyType(), entry.getKey()));
+            pairElem.appendChild(createValueElement(doc,
+                    dictType.getValueType(), entry.getValue()));
+          }
+        }
+      }
+    } else if (type == LICENSE) {
+      elem = createSingleValueElement(doc, "license", hasMultipleValues);
+      if (!hasMultipleValues) {
+        License license = (License) Iterables.getOnlyElement(values);
+
+        Element exceptions = createValueElement(doc, LABEL_LIST, license.getExceptions());
+        exceptions.setAttribute("name", "exceptions");
+        elem.appendChild(exceptions);
+
+        Element licenseTypes = createValueElement(doc, STRING_LIST, license.getLicenseTypes());
+        licenseTypes.setAttribute("name", "license-types");
+        elem.appendChild(licenseTypes);
+      }
+    } else if (type == FILESET_ENTRY) {
+      // Fileset entries: not configurable.
+      FilesetEntry filesetEntry = (FilesetEntry) Iterables.getOnlyElement(values);
+      elem = doc.createElement("fileset-entry");
+      elem.setAttribute("srcdir",  filesetEntry.getSrcLabel().toString());
+      elem.setAttribute("destdir",  filesetEntry.getDestDir().toString());
+      elem.setAttribute("symlinks", filesetEntry.getSymlinkBehavior().toString());
+      elem.setAttribute("strip_prefix", filesetEntry.getStripPrefix());
+
+      if (filesetEntry.getExcludes() != null) {
+        Element excludes =
+            createValueElement(doc, LABEL_LIST, filesetEntry.getExcludes());
+        excludes.setAttribute("name", "excludes");
+        elem.appendChild(excludes);
+      }
+      if (filesetEntry.getFiles() != null) {
+        Element files = createValueElement(doc, LABEL_LIST, filesetEntry.getFiles());
+        files.setAttribute("name", "files");
+        elem.appendChild(files);
+      }
+    } else { // INTEGER STRING LABEL DISTRIBUTION OUTPUT
+      elem = createSingleValueElement(doc, type.toString(), hasMultipleValues);
+      if (!hasMultipleValues && !Iterables.isEmpty(values)) {
+        Object value = Iterables.getOnlyElement(values);
+        // Values such as those of attribute "linkstamp" may be null.
+        if (value != null) {
+          try {
+            elem.setAttribute("value", value.toString());
+          } catch (DOMException e) {
+            elem.setAttribute("value", "[[[ERROR: could not be encoded as XML]]]");
+          }
+        }
+      }
+    }
+    return elem;
+  }
+
+  private static Element createValueElement(Document doc,
+        com.google.devtools.build.lib.packages.Type<?> type, Object value) {
+    return createValueElement(doc, type, ImmutableList.of(value));
+  }
+
+  /**
+   * Creates the given DOM element, adding <code>configurable="yes"</code> if it represents
+   * a configurable single-value attribute (configurable list attributes simply have their
+   * lists merged into an aggregate flat list).
+   */
+  private static Element createSingleValueElement(Document doc, String name,
+      boolean configurable) {
+    Element elem = doc.createElement(name);
+    if (configurable) {
+      elem.setAttribute("configurable", "yes");
+    }
+    return elem;
+  }
+}