Automated [] rollback of commit 846a5ab98fc26d72024890fdb79a5d3bc6a5a1ba + manual rollback of []

*** Reason for rollback ***

Depot has been fixed / is in the process of being fixed. See the work tracked on []

*** Original change description ***

Automated [] rollback of commit bb5d5efb4b50710241b5b374eb67084f4bf08278.

--
MOS_MIGRATED_REVID=131095905

5 files changed, 98 insertions, 105 deletions

diff --git a/src/main/java/com/google/devtools/build/docgen/templates/be/functions.vm b/src/main/java/com/google/devtools/build/docgen/templates/be/functions.vm
index 780716cfe1..33e0a4634a 100644
--- a/src/main/java/com/google/devtools/build/docgen/templates/be/functions.vm
+++ b/src/main/java/com/google/devtools/build/docgen/templates/be/functions.vm
@@ -402,7 +402,7 @@ This wildcard can only be used as a complete path segment. For example,
 and <code>"**.java"</code> are both illegal. No other wildcards are supported.
 </p>
 <p>
-Glob returns a list of every file in the current package that:
+Glob returns a sorted list of every file in the current package that:
 </p>
 <ul>
   <li>Matches at least one pattern in <code>include</code>. </li>
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));
         }
       }
     }