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

4 files changed, 97 insertions, 104 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/packages/GlobCache.java b/src/main/java/com/google/devtools/build/lib/packages/GlobCache.java
index 45e36ed90b..694601d1c4 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/GlobCache.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/GlobCache.java
@@ -18,7 +18,6 @@ import com.google.common.base.Predicate;
 import com.google.common.base.Throwables;
 import com.google.common.collect.Iterables;
 import com.google.common.collect.Lists;
-import com.google.common.collect.Sets;
 import com.google.common.util.concurrent.SettableFuture;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
 import com.google.devtools.build.lib.concurrent.ThreadSafety;
@@ -32,7 +31,7 @@ import java.io.IOException;
 import java.util.ArrayList;
 import java.util.Collection;
 import java.util.HashMap;
-import java.util.LinkedHashSet;
+import java.util.HashSet;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
@@ -126,26 +125,26 @@ public class GlobCache {
    * @throws BadGlobException if the glob was syntactically invalid, or
    *  contained uplevel references.
    */
-  Future<List<Path>> getGlobAsync(String pattern, boolean excludeDirs)
+  Future<List<Path>> getGlobUnsortedAsync(String pattern, boolean excludeDirs)
       throws BadGlobException {
     Future<List<Path>> cached = globCache.get(Pair.of(pattern, excludeDirs));
     if (cached == null) {
-      cached = safeGlob(pattern, excludeDirs);
+      cached = safeGlobUnsorted(pattern, excludeDirs);
       setGlobPaths(pattern, excludeDirs, cached);
     }
     return cached;
   }
 
   @VisibleForTesting
-  List<String> getGlob(String pattern)
+  List<String> getGlobUnsorted(String pattern)
       throws IOException, BadGlobException, InterruptedException {
-    return getGlob(pattern, false);
+    return getGlobUnsorted(pattern, false);
   }
 
   @VisibleForTesting
-  protected List<String> getGlob(String pattern, boolean excludeDirs)
+  protected List<String> getGlobUnsorted(String pattern, boolean excludeDirs)
       throws IOException, BadGlobException, InterruptedException {
-    Future<List<Path>> futureResult = getGlobAsync(pattern, excludeDirs);
+    Future<List<Path>> futureResult = getGlobUnsortedAsync(pattern, excludeDirs);
     List<Path> globPaths = fromFuture(futureResult);
     // Replace the UnixGlob.GlobFuture with a completed future object, to allow
     // garbage collection of the GlobFuture and GlobVisitor objects.
@@ -168,11 +167,8 @@ public class GlobCache {
     return result;
   }
 
-  /**
-   * Adds glob entries to the cache, making sure they are sorted first.
-   */
-  @VisibleForTesting
-  void setGlobPaths(String pattern, boolean excludeDirectories, Future<List<Path>> result) {
+  /** Adds glob entries to the cache. */
+  private void setGlobPaths(String pattern, boolean excludeDirectories, Future<List<Path>> result) {
     globCache.put(Pair.of(pattern, excludeDirectories), result);
   }
 
@@ -181,7 +177,7 @@ public class GlobCache {
    * getGlob().
    */
   @VisibleForTesting
-  Future<List<Path>> safeGlob(String pattern, boolean excludeDirs) throws BadGlobException {
+  Future<List<Path>> safeGlobUnsorted(String pattern, boolean excludeDirs) throws BadGlobException {
     // Forbidden patterns:
     if (pattern.indexOf('?') != -1) {
       throw new BadGlobException("glob pattern '" + pattern + "' contains forbidden '?' wildcard");
@@ -217,64 +213,28 @@ public class GlobCache {
   }
 
   /**
-   * Returns true iff all this package's globs are up-to-date.  That is,
-   * re-evaluating the package's BUILD file at this moment would yield an
-   * equivalent Package instance.  (This call requires filesystem I/O to
-   * re-evaluate the globs.)
-   */
-  public boolean globsUpToDate() throws InterruptedException {
-    // Start all globs in parallel.
-    Map<Pair<String, Boolean>, Future<List<Path>>> newGlobs = new HashMap<>();
-    try {
-      for (Map.Entry<Pair<String, Boolean>, Future<List<Path>>> entry : globCache.entrySet()) {
-        Pair<String, Boolean> key = entry.getKey();
-        try {
-          newGlobs.put(key, safeGlob(key.first, key.second));
-        } catch (BadGlobException e) {
-          return false;
-        }
-      }
-
-      for (Map.Entry<Pair<String, Boolean>, Future<List<Path>>> entry : globCache.entrySet()) {
-        try {
-          Pair<String, Boolean> key = entry.getKey();
-          List<Path> newGlob = fromFuture(newGlobs.get(key));
-          List<Path> oldGlob = fromFuture(entry.getValue());
-          if (!oldGlob.equals(newGlob)) {
-            return false;
-          }
-        } catch (IOException e) {
-          return false;
-        }
-      }
-
-      return true;
-    } finally {
-      finishBackgroundTasks(newGlobs.values());
-    }
-  }
-
-  /**
-   * Evaluate the build language expression "glob(includes, excludes)" in the
+   * Helper for evaluating the build language expression "glob(includes, excludes)" in the
    * context of this package.
    *
    * <p>Called by PackageFactory via Package.
    */
-  public List<String> glob(List<String> includes, List<String> excludes, boolean excludeDirs)
-      throws IOException, BadGlobException, InterruptedException {
+  public List<String> globUnsorted(
+      List<String> includes,
+      List<String> excludes,
+      boolean excludeDirs) throws IOException, BadGlobException, InterruptedException {
     // Start globbing all patterns in parallel. The getGlob() calls below will
     // block on an individual pattern's results, but the other globs can
     // continue in the background.
     for (String pattern : Iterables.concat(includes, excludes)) {
-      getGlobAsync(pattern, excludeDirs);
+      getGlobUnsortedAsync(pattern, excludeDirs);
     }
 
-    LinkedHashSet<String> results = Sets.newLinkedHashSetWithExpectedSize(includes.size());
+    HashSet<String> results = new HashSet<>();
     for (String pattern : includes) {
-      results.addAll(getGlob(pattern, excludeDirs));
+      results.addAll(getGlobUnsorted(pattern, excludeDirs));
     }
     for (String pattern : excludes) {
-      for (String excludeMatch : getGlob(pattern, excludeDirs)) {
+      for (String excludeMatch : getGlobUnsorted(pattern, excludeDirs)) {
         results.remove(excludeMatch);
       }
     }
diff --git a/src/main/java/com/google/devtools/build/lib/packages/PackageFactory.java b/src/main/java/com/google/devtools/build/lib/packages/PackageFactory.java
index 9c1a5c8a0c..4b8db490f3 100644
--- a/src/main/java/com/google/devtools/build/lib/packages/PackageFactory.java
+++ b/src/main/java/com/google/devtools/build/lib/packages/PackageFactory.java
@@ -70,6 +70,7 @@ import com.google.devtools.build.lib.vfs.UnixGlob;
 import java.io.IOException;
 import java.util.ArrayList;
 import java.util.Collection;
+import java.util.Collections;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
@@ -285,9 +286,11 @@ public final class PackageFactory {
   /** {@link Globber} that uses the legacy GlobCache. */
   public static class LegacyGlobber implements Globber {
     private final GlobCache globCache;
+    private final boolean sort;
 
-    public LegacyGlobber(GlobCache globCache) {
+    private LegacyGlobber(GlobCache globCache, boolean sort) {
       this.globCache = globCache;
+      this.sort = sort;
     }
 
     private static class Token extends Globber.Token {
@@ -306,20 +309,25 @@ public final class PackageFactory {
     public Token runAsync(List<String> includes, List<String> excludes, boolean excludeDirs)
         throws BadGlobException {
       for (String pattern : Iterables.concat(includes, excludes)) {
-        globCache.getGlobAsync(pattern, excludeDirs);
+        globCache.getGlobUnsortedAsync(pattern, excludeDirs);
       }
       return new Token(includes, excludes, excludeDirs);
     }
 
     @Override
     public List<String> fetch(Globber.Token token) throws IOException, InterruptedException {
+      List<String> result;
       Token legacyToken = (Token) token;
       try {
-        return globCache.glob(legacyToken.includes, legacyToken.excludes,
+        result = globCache.globUnsorted(legacyToken.includes, legacyToken.excludes,
             legacyToken.excludeDirs);
       } catch (BadGlobException e) {
         throw new IllegalStateException(e);
       }
+      if (sort) {
+        Collections.sort(result);
+      }
+      return result;
     }
 
     @Override
@@ -1428,12 +1436,33 @@ public final class PackageFactory {
     }
   }
 
-  public LegacyGlobber createLegacyGlobber(Path packageDirectory, PackageIdentifier packageId,
+  /** Returns a new {@link LegacyGlobber}. */
+  public LegacyGlobber createLegacyGlobber(
+      Path packageDirectory,
+      PackageIdentifier packageId,
       CachingPackageLocator locator) {
-    return new LegacyGlobber(new GlobCache(packageDirectory, packageId, locator, syscalls,
+    return createLegacyGlobber(new GlobCache(packageDirectory, packageId, locator, syscalls,
         threadPool));
   }
 
+  /** Returns a new {@link LegacyGlobber}. */
+  public static LegacyGlobber createLegacyGlobber(GlobCache globCache) {
+    return new LegacyGlobber(globCache, /*sort=*/ true);
+  }
+
+  /**
+   * Returns a new {@link LegacyGlobber}, the same as in {@link #createLegacyGlobber}, except that
+   * the implementation of {@link Globber#fetch} intentionally breaks the contract and doesn't
+   * return sorted results.
+   */
+  public LegacyGlobber createLegacyGlobberThatDoesntSort(
+      Path packageDirectory,
+      PackageIdentifier packageId,
+      CachingPackageLocator locator) {
+    return new LegacyGlobber(new GlobCache(packageDirectory, packageId, locator, syscalls,
+        threadPool), /*sort=*/ false);
+  }
+
   @Nullable
   private byte[] maybeGetBuildFileBytes(Path buildFile, EventHandler eventHandler) {
     try {
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);
diff --git a/src/main/java/com/google/devtools/build/lib/vfs/UnixGlob.java b/src/main/java/com/google/devtools/build/lib/vfs/UnixGlob.java
index 6da3925e96..1ea067d20f 100644
--- a/src/main/java/com/google/devtools/build/lib/vfs/UnixGlob.java
+++ b/src/main/java/com/google/devtools/build/lib/vfs/UnixGlob.java
@@ -23,9 +23,9 @@ import com.google.common.base.Throwables;
 import com.google.common.cache.Cache;
 import com.google.common.cache.CacheBuilder;
 import com.google.common.cache.CacheLoader;
+import com.google.common.collect.ImmutableList;
 import com.google.common.collect.Iterables;
 import com.google.common.collect.Lists;
-import com.google.common.collect.Ordering;
 import com.google.common.collect.Sets;
 import com.google.common.util.concurrent.ForwardingListenableFuture;
 import com.google.common.util.concurrent.Futures;
@@ -55,6 +55,8 @@ import java.util.regex.Pattern;
  *
  * <p><code>**</code> gets special treatment in include patterns. If it is used as a complete path
  * segment it matches the filenames in subdirectories recursively.
+ *
+ * <p>Importantly, note that the glob matches are in an unspecified order.
  */
 public final class UnixGlob {
   private UnixGlob() {}
@@ -396,7 +398,7 @@ public final class UnixGlob {
     }
 
     /**
-     * Executes the glob.
+     * Executes the glob and returns the result.
      *
      * @throws InterruptedException if the thread is interrupted.
      */
@@ -499,9 +501,10 @@ public final class UnixGlob {
     }
 
     /**
-     * Performs wildcard globbing: returns the sorted list of filenames that match any of
+     * Performs wildcard globbing: returns the list of filenames that match any of
      * {@code patterns} relative to {@code base}. Directories are traversed if and only if they
-     * match {@code dirPred}. The predicate is also called for the root of the traversal.
+     * match {@code dirPred}. The predicate is also called for the root of the traversal. The order
+     * of the returned list is unspecified.
      *
      * <p>Patterns may include "*" and "?", but not "[a-z]".
      *
@@ -530,6 +533,10 @@ public final class UnixGlob {
       return "**".equals(pattern);
     }
 
+    /**
+     * Same as {@link #glob}, except does so asynchronously and returns a {@link Future} for the
+     * result.
+     */
     public Future<List<Path>> globAsync(Path base, Collection<String> patterns,
         boolean excludeDirectories, Predicate<Path> dirPred, FilesystemCalls syscalls) {
 
@@ -635,7 +642,7 @@ public final class UnixGlob {
         } else if (failure.get() != null) {
           result.setException(failure.get());
         } else {
-          result.set(Ordering.<Path>natural().immutableSortedCopy(results));
+          result.set(ImmutableList.copyOf(results));
         }
       }
     }