Sort output of `query --order_output=auto` lexicographically by default.

The `--incompatible_lexicographical_output` flag has two effects when used together with `--order_output=auto`:
1. It sorts the output lexicographically.
2. It uses the graphless query implementation.

Sorting the output lexicographically allows us to make the outputs of query and genquery consistent.

By using the graphless query implementation, query performance improves by at least ~60% in wall time (from some of our benchmarks).

The flag is ignored when `somepath` is used as a top level function (e.g. `query 'somepath(a,b)'`), and continue to output in dependency order instead of lexicographical order.

Using `--order_output=no` would make query even faster if you do not require a lexicographically sorted or deterministic output.

RELNOTES[INC]: Query `--order_output=auto` will now sort lexicographically. However, when `somepath` is used as a top level function (e.g. `query 'somepath(a, b)'`), it will continue to output in dependency order. If you do not want the lexicographical output ordering, specify another `--order_output` value (`no`, `deps` or `full`) based on what ordering you require.

PiperOrigin-RevId: 356483939

site/docs/query.html

diff --git a/site/docs/query.html b/site/docs/query.html
index 9faf8c6..48ae8a7 100644
--- a/site/docs/query.html
+++ b/site/docs/query.html
@@ -1166,10 +1166,9 @@
   of the <code>--order_output</code> flag and is deprecated.)
 </p>
 <p>
-  The default value of this flag is <code>auto</code>, which is equivalent to
-  <code>full</code> for every output format except for <code>proto</code>,
-  <code>graph</code>, <code>minrank</code>, and <code>maxrank</code>, for which
-  it is equivalent to <code>deps</code>.
+  The default value of this flag is <code>auto</code>, which prints results in <b>lexicographical
+  order</b>. However, when <code>somepath(a,b)</code> is used, the results will be printed in
+  <code>deps</code> order instead.
 </p>
 <p>
   When this flag is <code>no</code> and <code>--output</code> is one of

src/main/java/com/google/devtools/build/lib/query2/query/output/QueryOptions.java

diff --git a/src/main/java/com/google/devtools/build/lib/query2/query/output/QueryOptions.java b/src/main/java/com/google/devtools/build/lib/query2/query/output/QueryOptions.java
index 563e10b..4a7eb35 100644
--- a/src/main/java/com/google/devtools/build/lib/query2/query/output/QueryOptions.java
+++ b/src/main/java/com/google/devtools/build/lib/query2/query/output/QueryOptions.java
@@ -117,7 +117,7 @@
 
   @Option(
       name = "incompatible_lexicographical_output",
-      defaultValue = "false",
+      defaultValue = "true",
       documentationCategory = OptionDocumentationCategory.QUERY,
       effectTags = {OptionEffectTag.TERMINAL_OUTPUT},
       metadataTags = {

src/test/java/com/google/devtools/build/lib/buildtool/QueryIntegrationTest.java

diff --git a/src/test/java/com/google/devtools/build/lib/buildtool/QueryIntegrationTest.java b/src/test/java/com/google/devtools/build/lib/buildtool/QueryIntegrationTest.java
index 3a5bbf3..ab81fd0 100644
--- a/src/test/java/com/google/devtools/build/lib/buildtool/QueryIntegrationTest.java
+++ b/src/test/java/com/google/devtools/build/lib/buildtool/QueryIntegrationTest.java
@@ -212,7 +212,7 @@
       targets += "sh_library(name = '" + dep + "')\n";
     }
     expected.add("//foo:a");
-    Collections.sort(expected, Collections.reverseOrder());
+    Collections.sort(expected);
     write("foo/BUILD", "sh_library(name = 'a', deps = [" + depString + "])", targets);
     List<String> result = getStringQueryResult("deps(//foo:a)");
     assertThat(result).containsExactlyElementsIn(expected).inOrder();

src/test/shell/integration/loading_phase_test.sh

diff --git a/src/test/shell/integration/loading_phase_test.sh b/src/test/shell/integration/loading_phase_test.sh
index 049c64e..5d2609f 100755
--- a/src/test/shell/integration/loading_phase_test.sh
+++ b/src/test/shell/integration/loading_phase_test.sh
@@ -100,8 +100,8 @@
 
     # null terminated:
     bazel query --noshow_progress --null "buildfiles(//$pkg/x)" >$pkg/null.log ||
-        fail "Expected null success"
-    printf "//$pkg/y:rules.bzl\0//$pkg/y:BUILD\0//$pkg/x:BUILD\0" >$pkg/null.ref.log
+        fail "Expected null success"§
+    printf "//$pkg/x:BUILD\0//$pkg/y:BUILD\0//$pkg/y:rules.bzl\0" >$pkg/null.ref.log
     cmp $pkg/null.ref.log $pkg/null.log || fail "Expected match"
 
     # Missing Starlark file: