RELNOTES: The string list returned by the skylark 'glob' function is now sorted. Previously, it would return a list formed by concatenating the sorted results of each pattern in the 'includes' list.

A bunch of cleanups and one bug fix:
-Remove the unused-except-for tests GlobCache#globsUpToDate. This code has been dead for a very very long time, ever since we switched to using Skyframe.
-Change the semantics of the 'glob' function as described above.
-Change UnixGlob to return unsorted results. Document this in UnixGlob and GlobCache.
-Change LegacyGlobber to conditionally return sorted results. Have users other than PackageFunction get sorted results (as described above). Have PackageFunction's use case get completely unsorted results, and have PackageFunction do the sorting itself.
-Have PackageFunction's HybridGlobber unconditionally sort the glob result list. This ensure deterministic glob results, fixing a bug where the order of the elements of the result depended on the contents of the Skyframe graph, which of course depends on the sequence of incremental Blaze commands.

--
MOS_MIGRATED_REVID=130540152

1 files changed, 32 insertions, 35 deletions

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 54edcf52e0..733cf5abd3 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
@@ -25,6 +25,7 @@ import com.google.common.collect.Sets;
 import com.google.devtools.build.lib.cmdline.Label;
 import com.google.devtools.build.lib.cmdline.LabelSyntaxException;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
+import com.google.devtools.build.lib.collect.nestedset.NestedSet;
 import com.google.devtools.build.lib.events.Event;
 import com.google.devtools.build.lib.events.Location;
 import com.google.devtools.build.lib.events.StoredEventHandler;
@@ -36,6 +37,7 @@ import com.google.devtools.build.lib.packages.InvalidPackageNameException;
 import com.google.devtools.build.lib.packages.NoSuchPackageException;
 import com.google.devtools.build.lib.packages.Package;
 import com.google.devtools.build.lib.packages.PackageFactory;
+import com.google.devtools.build.lib.packages.PackageFactory.LegacyGlobber;
 import com.google.devtools.build.lib.packages.Preprocessor;
 import com.google.devtools.build.lib.packages.Preprocessor.AstAfterPreprocessing;
 import com.google.devtools.build.lib.packages.RuleVisibility;
@@ -69,6 +71,7 @@ import java.util.ArrayList;
 import java.util.Collection;
 import java.util.Collections;
 import java.util.HashMap;
+import java.util.HashSet;
 import java.util.LinkedHashSet;
 import java.util.List;
 import java.util.Map;
@@ -151,10 +154,10 @@ public class PackageFunction implements SkyFunction {
     private final T value;
     private final Set<SkyKey> globDepKeys;
     @Nullable
-    private final Globber legacyGlobber;
+    private final LegacyGlobber legacyGlobber;
 
     private CacheEntryWithGlobDeps(T value, Set<SkyKey> globDepKeys,
-        @Nullable Globber legacyGlobber) {
+        @Nullable LegacyGlobber legacyGlobber) {
       this.value = value;
       this.globDepKeys = globDepKeys;
       this.legacyGlobber = legacyGlobber;
@@ -899,15 +902,15 @@ public class PackageFunction implements SkyFunction {
     private final PackageIdentifier packageId;
     private final Path packageRoot;
     private final Environment env;
-    private final Globber delegate;
+    private final LegacyGlobber legacyGlobber;
     private final Set<SkyKey> globDepsRequested = Sets.newConcurrentHashSet();
 
     private SkyframeHybridGlobber(PackageIdentifier packageId, Path packageRoot, Environment env,
-        Globber delegate) {
+        LegacyGlobber legacyGlobber) {
       this.packageId = packageId;
       this.packageRoot = packageRoot;
       this.env = env;
-      this.delegate = delegate;
+      this.legacyGlobber = legacyGlobber;
     }
 
     private Set<SkyKey> getGlobDepsRequested() {
@@ -972,15 +975,15 @@ public class PackageFunction implements SkyFunction {
           excludesKeys.remove(missingKey);
         }
       }
-      Token delegateIncludesToken =
-          delegate.runAsync(includesToDelegate, ImmutableList.<String>of(), excludeDirs);
+      Token legacyIncludesToken =
+          legacyGlobber.runAsync(includesToDelegate, ImmutableList.<String>of(), excludeDirs);
       // See the HybridToken class-comment for why we pass excludesToDelegate as the includes
       // parameter here.
-      Token delegateExcludesToken =
-          delegate.runAsync(excludesToDelegate, ImmutableList.<String>of(), excludeDirs);
+      Token legacyExcludesToken =
+          legacyGlobber.runAsync(excludesToDelegate, ImmutableList.<String>of(), excludeDirs);
 
       return new HybridToken(globValueMap, includesKeys, excludesKeys,
-          delegateIncludesToken, delegateExcludesToken);
+          legacyIncludesToken, legacyExcludesToken);
     }
 
     private Collection<SkyKey> getMissingKeys(Collection<SkyKey> globKeys,
@@ -1008,17 +1011,17 @@ public class PackageFunction implements SkyFunction {
     @Override
     public List<String> fetch(Token token) throws IOException, InterruptedException {
       HybridToken hybridToken = (HybridToken) token;
-      return hybridToken.resolve(delegate);
+      return hybridToken.resolve(legacyGlobber);
     }
 
     @Override
     public void onInterrupt() {
-      delegate.onInterrupt();
+      legacyGlobber.onInterrupt();
     }
 
     @Override
     public void onCompletion() {
-      delegate.onCompletion();
+      legacyGlobber.onCompletion();
     }
 
     /**
@@ -1062,9 +1065,9 @@ public class PackageFunction implements SkyFunction {
       // (this is excludes_sky above).
       private final Iterable<SkyKey> excludesGlobKeys;
       // A token for computing includes_leg.
-      private final Token delegateIncludesToken;
+      private final Token legacyIncludesToken;
       // A token for computing excludes_leg.
-      private final Token delegateExcludesToken;
+      private final Token legacyExcludesToken;
 
       private HybridToken(Map<SkyKey, ValueOrException4<IOException, BuildFileNotFoundException,
           FileSymlinkCycleException, InconsistentFilesystemException>> globValueMap,
@@ -1073,42 +1076,35 @@ public class PackageFunction implements SkyFunction {
         this.globValueMap = globValueMap;
         this.includesGlobKeys = includesGlobKeys;
         this.excludesGlobKeys = excludesGlobKeys;
-        this.delegateIncludesToken = delegateIncludesToken;
-        this.delegateExcludesToken = delegateExcludesToken;
+        this.legacyIncludesToken = delegateIncludesToken;
+        this.legacyExcludesToken = delegateExcludesToken;
       }
 
       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;
+        HashSet<String> matches = new HashSet<>();
         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));
+        matches.addAll(delegate.fetch(legacyIncludesToken));
         for (SkyKey excludeGlobKey : excludesGlobKeys) {
           for (PathFragment match : getGlobMatches(excludeGlobKey, globValueMap)) {
-            needsSorting = true;
             matches.remove(match.getPathString());
           }
         }
-        for (String delegateExcludeMatch : delegate.fetch(delegateExcludesToken)) {
+        for (String delegateExcludeMatch : delegate.fetch(legacyExcludesToken)) {
           matches.remove(delegateExcludeMatch);
         }
         List<String> result = new ArrayList<>(matches);
-        if (needsSorting) {
-          Collections.sort(result);
-        }
+        // Skyframe glob results are unsorted. And we used a LegacyGlobber that doesn't sort.
+        // Therefore, we want to unconditionally sort here.
+        Collections.sort(result);
         return result;
       }
 
-      private static Iterable<PathFragment> getGlobMatches(
+      private static NestedSet<PathFragment> getGlobMatches(
           SkyKey globKey,
           Map<
                   SkyKey,
@@ -1122,7 +1118,6 @@ public class PackageFunction implements SkyFunction {
                 Preconditions.checkNotNull(globValueMap.get(globKey), "%s should not be missing",
                     globKey);
         try {
-          // TODO(bazel-team): NestedSet expansion here is suboptimal.
           return Preconditions.checkNotNull((GlobValue) valueOrException.get(),
               "%s should not be missing", globKey).getMatches();
         } catch (BuildFileNotFoundException | FileSymlinkCycleException
@@ -1173,7 +1168,9 @@ public class PackageFunction implements SkyFunction {
           if (showLoadingProgress.get()) {
             env.getListener().handle(Event.progress("Loading package: " + packageId));
           }
-          Globber legacyGlobber = packageFactory.createLegacyGlobber(
+          // We use a LegacyGlobber that doesn't sort the matches for each individual glob pattern,
+          // since we want to sort the final result anyway.
+          LegacyGlobber legacyGlobber = packageFactory.createLegacyGlobberThatDoesntSort(
               buildFilePath.getParentDirectory(), packageId, packageLocator);
           SkyframeHybridGlobber skyframeGlobber = new SkyframeHybridGlobber(packageId, packageRoot,
               env, legacyGlobber);
@@ -1211,7 +1208,7 @@ public class PackageFunction implements SkyFunction {
           // legacy globber instance during BUILD file evaluation since the performance argument
           // below does not apply.
           Set<SkyKey> globDepsRequested = skyframeGlobber.getGlobDepsRequested();
-          Globber legacyGlobberToStore = globDepsRequested.isEmpty() ? null : legacyGlobber;
+          LegacyGlobber legacyGlobberToStore = globDepsRequested.isEmpty() ? null : legacyGlobber;
           astCacheEntry = new CacheEntryWithGlobDeps<>(
               new AstAfterPreprocessing(preprocessingResult, ast, astParsingEventHandler),
               globDepsRequested, legacyGlobberToStore);
@@ -1237,7 +1234,7 @@ public class PackageFunction implements SkyFunction {
         // If a legacy globber was used to evaluate globs during preprocessing, it's important that
         // we reuse that globber during BUILD file evaluation for performance, in the case that
         // globs were fetched lazily during preprocessing. See Preprocessor.Factory#considersGlobs.
-        Globber legacyGlobber = astCacheEntry.legacyGlobber != null
+        LegacyGlobber legacyGlobber = astCacheEntry.legacyGlobber != null
             ? astCacheEntry.legacyGlobber
             : packageFactory.createLegacyGlobber(
                 buildFilePath.getParentDirectory(), packageId, packageLocator);