Replace query option --order_results with --order_output, which can take three values for a given output formatter: 'no', 'deps', or 'full'. A fourth value, 'auto', means either 'deps' or 'full' depending on the formatter.

The option 'no' is equivalent to --noorder_results. 'full' means that output will be deterministically ordered, using alphabetization if necessary. 'deps' means that graph order will be preserved (where applicable), but further efforts to order the output may not be undertaken. 'auto' is equivalent to 'full' for all output formatters except for proto, minrank, maxrank, and graph, for which it is equivalent to 'deps'.

The purpose of this cl is to enable genquery to force completely deterministic output, which requires that it be able to specify a total ordering on the graph that is consistent across runs. Which ordering doesn't matter very much, so depending on the output formatter, or even within the same one, there may be some groups of nodes that are ordered alphabetically, and some reverse alphabetically.

--
MOS_MIGRATED_REVID=101512292

9 files changed, 261 insertions, 71 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/graph/DFS.java b/src/main/java/com/google/devtools/build/lib/graph/DFS.java
index 66d10739a0..7930a2faa4 100644
--- a/src/main/java/com/google/devtools/build/lib/graph/DFS.java
+++ b/src/main/java/com/google/devtools/build/lib/graph/DFS.java
@@ -63,7 +63,7 @@ public class DFS<T> {
    *  @param transpose iff true, the graph is implicitly transposed during
    *  visitation.
    */
-  public DFS(Order order, final Comparator<T> edgeOrder, boolean transpose) {
+  public DFS(Order order, final Comparator<? super T> edgeOrder, boolean transpose) {
     this.order = order;
     this.transpose = transpose;
 
diff --git a/src/main/java/com/google/devtools/build/lib/graph/Digraph.java b/src/main/java/com/google/devtools/build/lib/graph/Digraph.java
index 3371a3684b..1dc178be42 100644
--- a/src/main/java/com/google/devtools/build/lib/graph/Digraph.java
+++ b/src/main/java/com/google/devtools/build/lib/graph/Digraph.java
@@ -30,6 +30,8 @@ import java.util.Map;
 import java.util.PriorityQueue;
 import java.util.Set;
 
+import javax.annotation.Nullable;
+
 /**
  * <p> {@code Digraph} a generic directed graph or "digraph", suitable for
  * modeling asymmetric binary relations. </p>
@@ -246,23 +248,27 @@ public final class Digraph<T> implements Cloneable {
   @Override
   public Digraph<T> clone() {
     final Digraph<T> that = new Digraph<T>();
-    visitNodesBeforeEdges(new AbstractGraphVisitor<T>() {
-      @Override
-      public void visitEdge(Node<T> lhs, Node<T> rhs) {
-        that.addEdge(lhs.getLabel(), rhs.getLabel());
-      }
-      @Override
-      public void visitNode(Node<T> node) {
-        that.createNode(node.getLabel());
-      }
-    });
+    visitNodesBeforeEdges(
+        new AbstractGraphVisitor<T>() {
+          @Override
+          public void visitEdge(Node<T> lhs, Node<T> rhs) {
+            that.addEdge(lhs.getLabel(), rhs.getLabel());
+          }
+
+          @Override
+          public void visitNode(Node<T> node) {
+            that.createNode(node.getLabel());
+          }
+        },
+        nodes.values(),
+        null);
     return that;
   }
 
   /**
    * Returns a deterministic immutable view of the nodes of this graph.
    */
-  public Collection<Node<T>> getNodes(final Comparator<T> comparator) {
+  public Collection<Node<T>> getNodes(final Comparator<? super T> comparator) {
     Ordering<Node<T>> ordering = new Ordering<Node<T>>() {
       @Override
       public int compare(Node<T> o1, Node<T> o2) {
@@ -636,8 +642,7 @@ public final class Digraph<T> implements Cloneable {
    *     are visited.
    * @return The nodes of the graph, in a topological order
    */
-  public List<Node<T>> getTopologicalOrder(
-      Comparator<T> edgeOrder) {
+  public List<Node<T>> getTopologicalOrder(Comparator<? super T> edgeOrder) {
     CollectingVisitor<T> visitor = new CollectingVisitor<T>();
     DFS<T> visitation = new DFS<T>(DFS.Order.POSTORDER, edgeOrder, false);
     visitor.beginVisit();
@@ -1034,12 +1039,39 @@ public final class Digraph<T> implements Cloneable {
     visitor.endVisit();
   }
 
-  private void visitNodesBeforeEdges(GraphVisitor<T> visitor,
-                                    Iterable<Node<T>> startNodes) {
+  private static <T> Comparator<Node<T>> makeNodeComparator(
+      final Comparator<? super T> comparator) {
+    return new Comparator<Node<T>>() {
+      @Override
+      public int compare(Node<T> o1, Node<T> o2) {
+        return comparator.compare(o1.getLabel(), o2.getLabel());
+      }
+    };
+  }
+
+  /**
+   * Given {@param unordered}, a collection of nodes and a (possibly null) {@param comparator} for
+   * their labels, returns a sorted collection if {@param comparator} is non-null, otherwise returns
+   * {@param unordered}.
+   */
+  private static <T> Collection<Node<T>> maybeOrderCollection(
+      Collection<Node<T>> unordered, @Nullable final Comparator<? super T> comparator) {
+    if (comparator == null) {
+      return unordered;
+    }
+    List<Node<T>> result = new ArrayList<>(unordered);
+    Collections.sort(result, makeNodeComparator(comparator));
+    return result;
+  }
+
+  private void visitNodesBeforeEdges(
+      GraphVisitor<T> visitor,
+      Iterable<Node<T>> startNodes,
+      @Nullable Comparator<? super T> comparator) {
     visitor.beginVisit();
     for (Node<T> fromNode: startNodes) {
       visitor.visitNode(fromNode);
-      for (Node<T> toNode: fromNode.getSuccessors()) {
+      for (Node<T> toNode : maybeOrderCollection(fromNode.getSuccessors(), comparator)) {
         visitor.visitEdge(fromNode, toNode);
       }
     }
@@ -1047,12 +1079,16 @@ public final class Digraph<T> implements Cloneable {
   }
 
   /**
-   * A visitation over the graph that visits all nodes and edges in some order
-   * such that each node is visited before any edge coming out of that node;
-   * the order is otherwise unspecified.
+   * A visitation over the graph that visits all nodes and edges in topological order
+   * such that each node is visited before any edge coming out of that node; ties among nodes are
+   * broken using the provided {@param comparator} if not null; edges are visited in order specified
+   * by the comparator, <b>not</b> topological order of the target nodes.
    */
-  public void visitNodesBeforeEdges(GraphVisitor<T> visitor) {
-    visitNodesBeforeEdges(visitor, nodes.values());
+  public void visitNodesBeforeEdges(
+      GraphVisitor<T> visitor, @Nullable Comparator<? super T> comparator) {
+    visitNodesBeforeEdges(
+        visitor,
+        comparator == null ? getTopologicalOrder() : getTopologicalOrder(comparator),
+        comparator);
   }
-
 }
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
index 0cfcceac5b..ba46ddd317 100644
--- 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
@@ -13,6 +13,8 @@
 // limitations under the License.
 package com.google.devtools.build.lib.query2.output;
 
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Ordering;
 import com.google.devtools.build.lib.collect.CollectionUtils;
 import com.google.devtools.build.lib.collect.EquivalenceRelation;
 import com.google.devtools.build.lib.graph.Digraph;
@@ -20,11 +22,16 @@ 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 com.google.devtools.build.lib.query2.output.QueryOptions.OrderOutput;
 
 import java.io.PrintStream;
 import java.io.PrintWriter;
+import java.util.ArrayList;
 import java.util.Collection;
+import java.util.Collections;
+import java.util.Comparator;
 import java.util.HashSet;
+import java.util.List;
 import java.util.Set;
 
 /**
@@ -34,7 +41,6 @@ import java.util.Set;
 class GraphOutputFormatter extends OutputFormatter {
 
   private int graphNodeStringLimit;
-  private boolean graphFactored;
 
   @Override
   public String getName() {
@@ -45,16 +51,16 @@ class GraphOutputFormatter extends OutputFormatter {
   public void output(QueryOptions options, Digraph<Target> result, PrintStream out,
       AspectResolver aspectProvider) {
     this.graphNodeStringLimit = options.graphNodeStringLimit;
-    this.graphFactored = options.graphFactored;
 
-    if (graphFactored) {
-      outputFactored(result, new PrintWriter(out));
+    boolean sortLabels = options.orderOutput == OrderOutput.FULL;
+    if (options.graphFactored) {
+      outputFactored(result, new PrintWriter(out), sortLabels);
     } else {
-      outputUnfactored(result, new PrintWriter(out));
+      outputUnfactored(result, new PrintWriter(out), sortLabels);
     }
   }
 
-  private void outputUnfactored(Digraph<Target> result, PrintWriter out) {
+  private void outputUnfactored(Digraph<Target> result, PrintWriter out, boolean sortLabels) {
     result.visitNodesBeforeEdges(
         new DotOutputVisitor<Target>(out, LABEL_STRINGIFIER) {
           @Override
@@ -63,26 +69,42 @@ class GraphOutputFormatter extends OutputFormatter {
             // TODO(bazel-team): (2009) make this the default in Digraph.
             out.println("  node [shape=box];");
           }
-        });
+        },
+        sortLabels ? new TargetOrdering() : null);
   }
 
-  private void outputFactored(Digraph<Target> result, PrintWriter out) {
+  private static final Ordering<Node<Target>> NODE_COMPARATOR =
+      Ordering.from(new TargetOrdering()).onResultOf(EXTRACT_NODE_LABEL);
+
+  private static final Comparator<Iterable<Node<Target>>> ITERABLE_COMPARATOR =
+      NODE_COMPARATOR.lexicographical();
+
+  /**
+   * Given {@param collectionOfUnorderedSets}, a collection of sets of nodes, returns a collection
+   * of sets with the same elements as {@param collectionOfUnorderedSets} but with a stable
+   * iteration order within each set given by the target ordering, and the collection ordered by the
+   * same induced order.
+   */
+  private static Collection<Set<Node<Target>>> orderPartition(
+      Collection<Set<Node<Target>>> collectionOfUnorderedSets) {
+    List<Set<Node<Target>>> result = new ArrayList<>();
+    for (Set<Node<Target>> part : collectionOfUnorderedSets) {
+      List<Node<Target>> toSort = new ArrayList<>(part);
+      Collections.sort(toSort, NODE_COMPARATOR);
+      result.add(ImmutableSet.copyOf(toSort));
+    }
+    Collections.sort(result, ITERABLE_COMPARATOR);
+    return result;
+  }
+
+  private void outputFactored(Digraph<Target> result, PrintWriter out, final boolean sortLabels) {
     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);
+    if (sortLabels) {
+      partition = orderPartition(partition);
+    }
 
     Digraph<Set<Node<Target>>> factoredGraph = result.createImageUnderPartition(partition);
 
@@ -124,7 +146,8 @@ class GraphOutputFormatter extends OutputFormatter {
             // TODO(bazel-team): (2009) make this the default in Digraph.
             out.println("  node [shape=box];");
           }
-        });
+        },
+        sortLabels ? ITERABLE_COMPARATOR : null);
   }
 
   /**
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
index 259cf4cf5a..ea35aaab91 100644
--- 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
@@ -25,6 +25,7 @@ import com.google.devtools.build.lib.packages.Attribute;
 import com.google.devtools.build.lib.packages.PackageSerializer;
 import com.google.devtools.build.lib.packages.Rule;
 import com.google.devtools.build.lib.packages.Target;
+import com.google.devtools.build.lib.query2.output.QueryOptions.OrderOutput;
 import com.google.devtools.build.lib.syntax.EvalUtils;
 import com.google.devtools.build.lib.syntax.Label;
 import com.google.devtools.build.lib.syntax.Printer;
@@ -45,6 +46,8 @@ import java.util.List;
 import java.util.Map;
 import java.util.Set;
 
+import javax.annotation.Nullable;
+
 /**
  * Interface for classes which order, format and print the result of a Blaze
  * graph query.
@@ -169,9 +172,13 @@ public abstract class OutputFormatter implements Serializable {
 
   abstract static class AbstractUnorderedFormatter extends OutputFormatter
       implements UnorderedFormatter {
-    private static Iterable<Target> getOrderedTargets(Digraph<Target> result) {
-      return Iterables.transform(
-          result.getTopologicalOrder(new TargetOrdering()), EXTRACT_NODE_LABEL);
+    private static Iterable<Target> getOrderedTargets(
+        Digraph<Target> result, QueryOptions options) {
+      Iterable<Node<Target>> orderedResult =
+          options.orderOutput == OrderOutput.DEPS
+              ? result.getTopologicalOrder()
+              : result.getTopologicalOrder(new TargetOrdering());
+      return Iterables.transform(orderedResult, EXTRACT_NODE_LABEL);
     }
 
     @Override
@@ -181,7 +188,7 @@ public abstract class OutputFormatter implements Serializable {
         PrintStream out,
         AspectResolver aspectResolver)
         throws IOException, InterruptedException {
-      outputUnordered(options, getOrderedTargets(result), out, aspectResolver);
+      outputUnordered(options, getOrderedTargets(result, options), out, aspectResolver);
     }
   }
 
@@ -323,6 +330,29 @@ public abstract class OutputFormatter implements Serializable {
     }
   }
 
+  private static class RankAndLabel implements Comparable<RankAndLabel> {
+    private final int rank;
+    private final Label label;
+
+    private RankAndLabel(int rank, Label label) {
+      this.rank = rank;
+      this.label = label;
+    }
+
+    @Override
+    public int compareTo(RankAndLabel o) {
+      if (this.rank != o.rank) {
+        return this.rank - o.rank;
+      }
+      return this.label.compareTo(o.label);
+    }
+
+    @Override
+    public String toString() {
+      return rank + " " + label;
+    }
+  }
+
   /**
    * An output formatter that prints the labels in minimum rank order, preceded by
    * their rank number.  "Roots" have rank 0, their direct prerequisites have
@@ -339,6 +369,15 @@ public abstract class OutputFormatter implements Serializable {
       return "minrank";
     }
 
+    private static void outputToStreamOrSave(
+        int rank, Label label, PrintStream out, @Nullable List<RankAndLabel> toSave) {
+      if (toSave != null) {
+        toSave.add(new RankAndLabel(rank, label));
+      } else {
+        out.println(rank + " " + label);
+      }
+    }
+
     @Override
     public void output(QueryOptions options, Digraph<Target> result, PrintStream out,
         AspectResolver aspectResolver) {
@@ -347,6 +386,8 @@ public abstract class OutputFormatter implements Serializable {
       // cycles should be treated a "clump" of nodes all on the same rank.
       // Graphs may contain cycles because there are errors in BUILD files.
 
+      List<RankAndLabel> outputToOrder =
+          options.orderOutput == OrderOutput.FULL ? new ArrayList<RankAndLabel>() : null;
       Digraph<Set<Node<Target>>> scGraph = result.getStrongComponentGraph();
       Set<Node<Set<Node<Target>>>> rankNodes = scGraph.getRoots();
       Set<Node<Set<Node<Target>>>> seen = new HashSet<>();
@@ -355,7 +396,7 @@ public abstract class OutputFormatter implements Serializable {
         // Print out this rank:
         for (Node<Set<Node<Target>>> xScc : rankNodes) {
           for (Node<Target> x : xScc.getLabel()) {
-            out.println(rank + " " + x.getLabel().getLabel());
+            outputToStreamOrSave(rank, x.getLabel().getLabel(), out, outputToOrder);
           }
         }
 
@@ -370,6 +411,12 @@ public abstract class OutputFormatter implements Serializable {
         }
         rankNodes = nextRankNodes;
       }
+      if (outputToOrder != null) {
+        Collections.sort(outputToOrder);
+        for (RankAndLabel item : outputToOrder) {
+          out.println(item);
+        }
+      }
     }
   }
 
@@ -419,22 +466,28 @@ public abstract class OutputFormatter implements Serializable {
       DP dp = new DP();
 
       // Now sort by rank...
-      List<Pair<Integer, Label>> output = new ArrayList<>();
+      List<RankAndLabel> 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()));
+          output.add(new RankAndLabel(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);
+      if (options.orderOutput == OrderOutput.FULL) {
+        // Use the natural order for RankAndLabels, which breaks ties alphabetically.
+        Collections.sort(output);
+      } else {
+        Collections.sort(
+            output,
+            new Comparator<RankAndLabel>() {
+              @Override
+              public int compare(RankAndLabel o1, RankAndLabel o2) {
+                return o1.rank - o2.rank;
+              }
+            });
+      }
+      for (RankAndLabel item : output) {
+        out.println(item);
       }
     }
   }
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
index 1525d867cf..fe85ba0968 100644
--- 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
@@ -20,6 +20,7 @@ import static com.google.devtools.build.lib.query2.proto.proto2api.Build.Target.
 import static com.google.devtools.build.lib.query2.proto.proto2api.Build.Target.Discriminator.SOURCE_FILE;
 
 import com.google.common.collect.ImmutableMultimap;
+import com.google.common.collect.Iterables;
 import com.google.common.collect.Lists;
 import com.google.devtools.build.lib.graph.Digraph;
 import com.google.devtools.build.lib.packages.Attribute;
@@ -34,6 +35,7 @@ import com.google.devtools.build.lib.packages.Target;
 import com.google.devtools.build.lib.query2.FakeSubincludeTarget;
 import com.google.devtools.build.lib.query2.output.AspectResolver.BuildFileDependencyMode;
 import com.google.devtools.build.lib.query2.output.OutputFormatter.UnorderedFormatter;
+import com.google.devtools.build.lib.query2.output.QueryOptions.OrderOutput;
 import com.google.devtools.build.lib.query2.proto.proto2api.Build;
 import com.google.devtools.build.lib.syntax.Label;
 import com.google.devtools.build.lib.syntax.SkylarkEnvironment;
@@ -89,10 +91,19 @@ public class ProtoOutputFormatter extends OutputFormatter implements UnorderedFo
     queryResult.build().writeTo(out);
   }
 
+  private static Iterable<Target> getSortedLabels(Digraph<Target> result) {
+    return Iterables.transform(
+        result.getTopologicalOrder(new TargetOrdering()), EXTRACT_NODE_LABEL);
+  }
+
   @Override
   public void output(QueryOptions options, Digraph<Target> result, PrintStream out,
       AspectResolver aspectResolver) throws IOException, InterruptedException {
-    outputUnordered(options, result.getLabels(), out, aspectResolver);
+    outputUnordered(
+        options,
+        options.orderOutput == OrderOutput.FULL ? getSortedLabels(result) : result.getLabels(),
+        out,
+        aspectResolver);
   }
 
   /**
diff --git a/src/main/java/com/google/devtools/build/lib/query2/output/QueryOptions.java b/src/main/java/com/google/devtools/build/lib/query2/output/QueryOptions.java
index 6513dab973..4dd8bc77aa 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/output/QueryOptions.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/output/QueryOptions.java
@@ -34,6 +34,13 @@ public class QueryOptions extends OptionsBase {
     }
   }
 
+  /** An enum converter for {@code OrderOutput} . Should be used internally only. */
+  public static class OrderOutputConverter extends EnumConverter<OrderOutput> {
+    public OrderOutputConverter() {
+      super(OrderOutput.class, "Order output setting");
+    }
+  }
+
   @Option(name = "output",
       defaultValue = "label",
       category = "query",
@@ -42,13 +49,54 @@ public class QueryOptions extends OptionsBase {
           + " 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 = "order_results",
+    defaultValue = "null",
+    category = "query",
+    deprecationWarning = "Please use --order_output=auto or --order_output=no instead of this flag",
+    expansion = {"--order_output=auto"},
+    help =
+        "Output the results in dependency-ordered (default) or unordered fashion. The "
+            + "unordered output is faster but only supported when --output is not minrank, "
+            + "maxrank, or graph."
+  )
+  public Void orderResults;
+
+  @Option(
+    name = "noorder_results",
+    defaultValue = "null",
+    category = "query",
+    deprecationWarning = "Please use --order_output=no or --order_output=auto instead of this flag",
+    expansion = {"--order_output=no"},
+    help =
+        "Output the results in dependency-ordered (default) or unordered fashion. The "
+            + "unordered output is faster but only supported when --output is not minrank, "
+            + "maxrank, or graph."
+  )
+  public Void noOrderResults;
+
+  /** Whether and how output should be ordered. */
+  public enum OrderOutput {
+    NO, /** Make no effort to order output besides that required by output formatter. */
+    DEPS, /** Output in dependency order when compatible with output formatter. */
+    AUTO, /** Same as full unless formatter is proto, minrank, maxrank, or graph, then deps. */
+    FULL /** Output in dependency order, breaking ties with alphabetical order when needed. */
+  }
+
+  @Option(
+    name = "order_output",
+    converter = OrderOutputConverter.class,
+    defaultValue = "auto",
+    category = "query",
+    help =
+        "Output the results unordered (no), dependency-ordered (deps), or fully ordered (full). "
+            + "The default is 'auto', meaning that results are output either dependency-ordered or "
+            + "fully ordered, depending on the output formatter (dependency-ordered for proto, "
+            + "minrank, maxrank, and graph, fully ordered for all others). When output is fully "
+            + "ordered, nodes that would otherwise be unordered by the output formatter are "
+            + "alphabetized before output."
+  )
+  public OrderOutput orderOutput;
 
   @Option(name = "keep_going",
       abbrev = 'k',
diff --git a/src/main/java/com/google/devtools/build/lib/query2/output/QueryOutputUtils.java b/src/main/java/com/google/devtools/build/lib/query2/output/QueryOutputUtils.java
index 078b937a55..b85cf66694 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/output/QueryOutputUtils.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/output/QueryOutputUtils.java
@@ -17,6 +17,7 @@ import com.google.devtools.build.lib.packages.Target;
 import com.google.devtools.build.lib.query2.engine.BlazeQueryEvalResult;
 import com.google.devtools.build.lib.query2.engine.QueryEvalResult;
 import com.google.devtools.build.lib.query2.output.OutputFormatter.UnorderedFormatter;
+import com.google.devtools.build.lib.query2.output.QueryOptions.OrderOutput;
 
 import java.io.IOException;
 import java.io.PrintStream;
@@ -27,7 +28,7 @@ public class QueryOutputUtils {
   private QueryOutputUtils() {}
 
   public static boolean orderResults(QueryOptions queryOptions, OutputFormatter formatter) {
-    return queryOptions.orderResults || !(formatter instanceof UnorderedFormatter);
+    return queryOptions.orderOutput != OrderOutput.NO || !(formatter instanceof UnorderedFormatter);
   }
 
   public static void output(QueryOptions queryOptions, QueryEvalResult<Target> result,
diff --git a/src/main/java/com/google/devtools/build/lib/rules/genquery/GenQuery.java b/src/main/java/com/google/devtools/build/lib/rules/genquery/GenQuery.java
index 4920ed5c31..c89b574c3c 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/genquery/GenQuery.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/genquery/GenQuery.java
@@ -55,6 +55,7 @@ import com.google.devtools.build.lib.query2.engine.QueryException;
 import com.google.devtools.build.lib.query2.engine.SkyframeRestartQueryException;
 import com.google.devtools.build.lib.query2.output.OutputFormatter;
 import com.google.devtools.build.lib.query2.output.QueryOptions;
+import com.google.devtools.build.lib.query2.output.QueryOptions.OrderOutput;
 import com.google.devtools.build.lib.query2.output.QueryOutputUtils;
 import com.google.devtools.build.lib.rules.RuleConfiguredTargetFactory;
 import com.google.devtools.build.lib.skyframe.PackageValue;
@@ -119,6 +120,20 @@ public class GenQuery implements RuleConfiguredTargetFactory {
       ruleContext.attributeError("opts", "option --universe_scope is not allowed");
       return null;
     }
+    if (optionsParser.containsExplicitOption("order_results")) {
+      ruleContext.attributeError("opts", "option --order_results is not allowed");
+      return null;
+    }
+    if (optionsParser.containsExplicitOption("noorder_results")) {
+      ruleContext.attributeError("opts", "option --noorder_results is not allowed");
+      return null;
+    }
+    if (optionsParser.containsExplicitOption("order_output")) {
+      ruleContext.attributeError("opts", "option --order_output is not allowed");
+      return null;
+    }
+    // Force results to be deterministic.
+    queryOptions.orderOutput = OrderOutput.FULL;
 
     // force relative_locations to true so it has a deterministic output across machines.
     queryOptions.relativeLocations = true;
diff --git a/src/main/java/com/google/devtools/build/lib/rules/genquery/GenQueryRule.java b/src/main/java/com/google/devtools/build/lib/rules/genquery/GenQueryRule.java
index 40647fbeea..fdff1115ec 100644
--- a/src/main/java/com/google/devtools/build/lib/rules/genquery/GenQueryRule.java
+++ b/src/main/java/com/google/devtools/build/lib/rules/genquery/GenQueryRule.java
@@ -55,8 +55,8 @@ public final class GenQueryRule implements RuleDefinition {
         /* <!-- #BLAZE_RULE(genquery).ATTRIBUTE(opts) -->
         The options that are passed to the query engine.
         These correspond to the command line options that can be passed to
-        <code>blaze query</code>. The only query option that is not allowed here
-        is <code>--keep_going</code>.
+        <code>blaze query</code>. The only query options that are not allowed here
+        are <code>--keep_going</code> and <code>--order_output</code>.
         ${SYNOPSIS}
         <!-- #END_BLAZE_RULE.ATTRIBUTE --> */
         .add(attr("opts", STRING_LIST))
@@ -95,6 +95,9 @@ ${ATTRIBUTE_SIGNATURE}
     <code>//pkg:all</code>) are not allowed here.
   </p>
   <p>
+    The genquery's output is ordered using <code>--order_output=full</code> in
+    order to enforce deterministic output.
+  <p>
     The name of the output file is the name of the rule.
   </p>