Sort the results returned by the HybridGlobber if we are using results from Skyframe globbing. This adds a log(n) factor to uses of globs, but getting globs to be returned in a reasonable order that can be emulated by legacy globbing is hard and bug-prone right now, and we must sort anyway if we are merging legacy and Skyframe globs.

Note that this log(n) factor is already present on clean builds with legacy globbing. If we end up seeing performance issues on incremental loading, we can investigate making GlobFunction efficiently return elements in sorted order. (We would still need to sort if merging legacy and Skyframe globs, but that should be a relatively rare occurrence, and can be dealt with by a more efficient merge sort if necessary.)

--
MOS_MIGRATED_REVID=127752554

2 files changed, 24 insertions, 6 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/GlobValue.java b/src/main/java/com/google/devtools/build/lib/skyframe/GlobValue.java
index 5f8eaa90ea..cd4dd85f34 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/GlobValue.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/GlobValue.java
@@ -47,7 +47,8 @@ public final class GlobValue implements SkyValue {
   }
 
   /**
-   * Returns glob matches.
+   * Returns glob matches. The matches will be in a deterministic but unspecified order. If a
+   * particular order is required, the returned iterable should be sorted.
    */
   public NestedSet<PathFragment> getMatches() {
     return matches;
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/PackageFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/PackageFunction.java
index 5d68e3f0dc..ad2f501612 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/PackageFunction.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/PackageFunction.java
@@ -68,6 +68,7 @@ import com.google.devtools.build.skyframe.ValueOrException4;
 import java.io.IOException;
 import java.util.ArrayList;
 import java.util.Collection;
+import java.util.Collections;
 import java.util.HashMap;
 import java.util.LinkedHashSet;
 import java.util.List;
@@ -1079,28 +1080,44 @@ public class PackageFunction implements SkyFunction {
 
       private List<String> resolve(Globber delegate) throws IOException, InterruptedException {
         LinkedHashSet<String> matches = Sets.newLinkedHashSet();
+        // Skyframe globbing does not sort the list of results alphabetically, while legacy globbing
+        // does. To avoid non-deterministic sorting, we sort the result if it has any skyframe
+        // globs. We must also sort if merging legacy and Skyframe globs, since the end result
+        // should be deterministically ordered.
+        boolean needsSorting = false;
         for (SkyKey includeGlobKey : includesGlobKeys) {
           // TODO(bazel-team): NestedSet expansion here is suboptimal.
           for (PathFragment match : getGlobMatches(includeGlobKey, globValueMap)) {
+            needsSorting = true;
             matches.add(match.getPathString());
           }
         }
         matches.addAll(delegate.fetch(delegateIncludesToken));
         for (SkyKey excludeGlobKey : excludesGlobKeys) {
           for (PathFragment match : getGlobMatches(excludeGlobKey, globValueMap)) {
+            needsSorting = true;
             matches.remove(match.getPathString());
           }
         }
         for (String delegateExcludeMatch : delegate.fetch(delegateExcludesToken)) {
           matches.remove(delegateExcludeMatch);
         }
-        return Lists.newArrayList(matches);
+        List<String> result = new ArrayList<>(matches);
+        if (needsSorting) {
+          Collections.sort(result);
+        }
+        return result;
       }
 
-      private Iterable<PathFragment> getGlobMatches(SkyKey globKey,
-          Map<SkyKey, ValueOrException4<IOException, BuildFileNotFoundException,
-              FileSymlinkCycleException, InconsistentFilesystemException>> globValueMap)
-                  throws IOException {
+      private static Iterable<PathFragment> getGlobMatches(
+          SkyKey globKey,
+          Map<
+                  SkyKey,
+                  ValueOrException4<
+                      IOException, BuildFileNotFoundException, FileSymlinkCycleException,
+                      InconsistentFilesystemException>>
+              globValueMap)
+          throws IOException {
         ValueOrException4<IOException, BuildFileNotFoundException, FileSymlinkCycleException,
             InconsistentFilesystemException> valueOrException =
                 Preconditions.checkNotNull(globValueMap.get(globKey), "%s should not be missing",