Rollback of commit bb5d5efb4b50710241b5b374eb67084f4bf08278.

--
MOS_MIGRATED_REVID=130941264

5 files changed, 105 insertions, 98 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 33e0a4634a..780716cfe1 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 sorted list of every file in the current package that:
+Glob returns a 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 694601d1c4..45e36ed90b 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,6 +18,7 @@ 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;
@@ -31,7 +32,7 @@ import java.io.IOException;
 import java.util.ArrayList;
 import java.util.Collection;
 import java.util.HashMap;
-import java.util.HashSet;
+import java.util.LinkedHashSet;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
@@ -125,26 +126,26 @@ public class GlobCache {
    * @throws BadGlobException if the glob was syntactically invalid, or
    *  contained uplevel references.
    */
-  Future<List<Path>> getGlobUnsortedAsync(String pattern, boolean excludeDirs)
+  Future<List<Path>> getGlobAsync(String pattern, boolean excludeDirs)
       throws BadGlobException {
     Future<List<Path>> cached = globCache.get(Pair.of(pattern, excludeDirs));
     if (cached == null) {
-      cached = safeGlobUnsorted(pattern, excludeDirs);
+      cached = safeGlob(pattern, excludeDirs);
       setGlobPaths(pattern, excludeDirs, cached);
     }
     return cached;
   }
 
   @VisibleForTesting
-  List<String> getGlobUnsorted(String pattern)
+  List<String> getGlob(String pattern)
       throws IOException, BadGlobException, InterruptedException {
-    return getGlobUnsorted(pattern, false);
+    return getGlob(pattern, false);
   }
 
   @VisibleForTesting
-  protected List<String> getGlobUnsorted(String pattern, boolean excludeDirs)
+  protected List<String> getGlob(String pattern, boolean excludeDirs)
       throws IOException, BadGlobException, InterruptedException {
-    Future<List<Path>> futureResult = getGlobUnsortedAsync(pattern, excludeDirs);
+    Future<List<Path>> futureResult = getGlobAsync(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.
@@ -167,8 +168,11 @@ public class GlobCache {
     return result;
   }
 
-  /** Adds glob entries to the cache. */
-  private void setGlobPaths(String pattern, boolean excludeDirectories, Future<List<Path>> result) {
+  /**
+   * Adds glob entries to the cache, making sure they are sorted first.
+   */
+  @VisibleForTesting
+  void setGlobPaths(String pattern, boolean excludeDirectories, Future<List<Path>> result) {
     globCache.put(Pair.of(pattern, excludeDirectories), result);
   }
 
@@ -177,7 +181,7 @@ public class GlobCache {
    * getGlob().
    */
   @VisibleForTesting
-  Future<List<Path>> safeGlobUnsorted(String pattern, boolean excludeDirs) throws BadGlobException {
+  Future<List<Path>> safeGlob(String pattern, boolean excludeDirs) throws BadGlobException {
     // Forbidden patterns:
     if (pattern.indexOf('?') != -1) {
       throw new BadGlobException("glob pattern '" + pattern + "' contains forbidden '?' wildcard");
@@ -213,28 +217,64 @@ public class GlobCache {
   }
 
   /**
-   * Helper for evaluating the build language expression "glob(includes, excludes)" in the
+   * 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
    * context of this package.
    *
    * <p>Called by PackageFactory via Package.
    */
-  public List<String> globUnsorted(
-      List<String> includes,
-      List<String> excludes,
-      boolean excludeDirs) throws IOException, BadGlobException, InterruptedException {
+  public List<String> glob(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)) {
-      getGlobUnsortedAsync(pattern, excludeDirs);
+      getGlobAsync(pattern, excludeDirs);
     }
 
-    HashSet<String> results = new HashSet<>();
+    LinkedHashSet<String> results = Sets.newLinkedHashSetWithExpectedSize(includes.size());
     for (String pattern : includes) {
-      results.addAll(getGlobUnsorted(pattern, excludeDirs));
+      results.addAll(getGlob(pattern, excludeDirs));
     }
     for (String pattern : excludes) {
-      for (String excludeMatch : getGlobUnsorted(pattern, excludeDirs)) {
+      for (String excludeMatch : getGlob(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 4b8db490f3..9c1a5c8a0c 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,7 +70,6 @@ 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;
@@ -286,11 +285,9 @@ 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;
 
-    private LegacyGlobber(GlobCache globCache, boolean sort) {
+    public LegacyGlobber(GlobCache globCache) {
       this.globCache = globCache;
-      this.sort = sort;
     }
 
     private static class Token extends Globber.Token {
@@ -309,25 +306,20 @@ 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.getGlobUnsortedAsync(pattern, excludeDirs);
+        globCache.getGlobAsync(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 {
-        result = globCache.globUnsorted(legacyToken.includes, legacyToken.excludes,
+        return globCache.glob(legacyToken.includes, legacyToken.excludes,
             legacyToken.excludeDirs);
       } catch (BadGlobException e) {
         throw new IllegalStateException(e);
       }
-      if (sort) {
-        Collections.sort(result);
-      }
-      return result;
     }
 
     @Override
@@ -1436,31 +1428,10 @@ public final class PackageFactory {
     }
   }
 
-  /** Returns a new {@link LegacyGlobber}. */
-  public LegacyGlobber createLegacyGlobber(
-      Path packageDirectory,
-      PackageIdentifier packageId,
-      CachingPackageLocator locator) {
-    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,
+  public LegacyGlobber createLegacyGlobber(Path packageDirectory, PackageIdentifier packageId,
       CachingPackageLocator locator) {
     return new LegacyGlobber(new GlobCache(packageDirectory, packageId, locator, syscalls,
-        threadPool), /*sort=*/ false);
+        threadPool));
   }
 
   @Nullable
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 733cf5abd3..54edcf52e0 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,7 +25,6 @@ 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;
@@ -37,7 +36,6 @@ 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;
@@ -71,7 +69,6 @@ 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;
@@ -154,10 +151,10 @@ public class PackageFunction implements SkyFunction {
     private final T value;
     private final Set<SkyKey> globDepKeys;
     @Nullable
-    private final LegacyGlobber legacyGlobber;
+    private final Globber legacyGlobber;
 
     private CacheEntryWithGlobDeps(T value, Set<SkyKey> globDepKeys,
-        @Nullable LegacyGlobber legacyGlobber) {
+        @Nullable Globber legacyGlobber) {
       this.value = value;
       this.globDepKeys = globDepKeys;
       this.legacyGlobber = legacyGlobber;
@@ -902,15 +899,15 @@ public class PackageFunction implements SkyFunction {
     private final PackageIdentifier packageId;
     private final Path packageRoot;
     private final Environment env;
-    private final LegacyGlobber legacyGlobber;
+    private final Globber delegate;
     private final Set<SkyKey> globDepsRequested = Sets.newConcurrentHashSet();
 
     private SkyframeHybridGlobber(PackageIdentifier packageId, Path packageRoot, Environment env,
-        LegacyGlobber legacyGlobber) {
+        Globber delegate) {
       this.packageId = packageId;
       this.packageRoot = packageRoot;
       this.env = env;
-      this.legacyGlobber = legacyGlobber;
+      this.delegate = delegate;
     }
 
     private Set<SkyKey> getGlobDepsRequested() {
@@ -975,15 +972,15 @@ public class PackageFunction implements SkyFunction {
           excludesKeys.remove(missingKey);
         }
       }
-      Token legacyIncludesToken =
-          legacyGlobber.runAsync(includesToDelegate, ImmutableList.<String>of(), excludeDirs);
+      Token delegateIncludesToken =
+          delegate.runAsync(includesToDelegate, ImmutableList.<String>of(), excludeDirs);
       // See the HybridToken class-comment for why we pass excludesToDelegate as the includes
       // parameter here.
-      Token legacyExcludesToken =
-          legacyGlobber.runAsync(excludesToDelegate, ImmutableList.<String>of(), excludeDirs);
+      Token delegateExcludesToken =
+          delegate.runAsync(excludesToDelegate, ImmutableList.<String>of(), excludeDirs);
 
       return new HybridToken(globValueMap, includesKeys, excludesKeys,
-          legacyIncludesToken, legacyExcludesToken);
+          delegateIncludesToken, delegateExcludesToken);
     }
 
     private Collection<SkyKey> getMissingKeys(Collection<SkyKey> globKeys,
@@ -1011,17 +1008,17 @@ public class PackageFunction implements SkyFunction {
     @Override
     public List<String> fetch(Token token) throws IOException, InterruptedException {
       HybridToken hybridToken = (HybridToken) token;
-      return hybridToken.resolve(legacyGlobber);
+      return hybridToken.resolve(delegate);
     }
 
     @Override
     public void onInterrupt() {
-      legacyGlobber.onInterrupt();
+      delegate.onInterrupt();
     }
 
     @Override
     public void onCompletion() {
-      legacyGlobber.onCompletion();
+      delegate.onCompletion();
     }
 
     /**
@@ -1065,9 +1062,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 legacyIncludesToken;
+      private final Token delegateIncludesToken;
       // A token for computing excludes_leg.
-      private final Token legacyExcludesToken;
+      private final Token delegateExcludesToken;
 
       private HybridToken(Map<SkyKey, ValueOrException4<IOException, BuildFileNotFoundException,
           FileSymlinkCycleException, InconsistentFilesystemException>> globValueMap,
@@ -1076,35 +1073,42 @@ public class PackageFunction implements SkyFunction {
         this.globValueMap = globValueMap;
         this.includesGlobKeys = includesGlobKeys;
         this.excludesGlobKeys = excludesGlobKeys;
-        this.legacyIncludesToken = delegateIncludesToken;
-        this.legacyExcludesToken = delegateExcludesToken;
+        this.delegateIncludesToken = delegateIncludesToken;
+        this.delegateExcludesToken = delegateExcludesToken;
       }
 
       private List<String> resolve(Globber delegate) throws IOException, InterruptedException {
-        HashSet<String> matches = new HashSet<>();
+        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(legacyIncludesToken));
+        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(legacyExcludesToken)) {
+        for (String delegateExcludeMatch : delegate.fetch(delegateExcludesToken)) {
           matches.remove(delegateExcludeMatch);
         }
         List<String> result = new ArrayList<>(matches);
-        // Skyframe glob results are unsorted. And we used a LegacyGlobber that doesn't sort.
-        // Therefore, we want to unconditionally sort here.
-        Collections.sort(result);
+        if (needsSorting) {
+          Collections.sort(result);
+        }
         return result;
       }
 
-      private static NestedSet<PathFragment> getGlobMatches(
+      private static Iterable<PathFragment> getGlobMatches(
           SkyKey globKey,
           Map<
                   SkyKey,
@@ -1118,6 +1122,7 @@ 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
@@ -1168,9 +1173,7 @@ public class PackageFunction implements SkyFunction {
           if (showLoadingProgress.get()) {
             env.getListener().handle(Event.progress("Loading package: " + packageId));
           }
-          // 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(
+          Globber legacyGlobber = packageFactory.createLegacyGlobber(
               buildFilePath.getParentDirectory(), packageId, packageLocator);
           SkyframeHybridGlobber skyframeGlobber = new SkyframeHybridGlobber(packageId, packageRoot,
               env, legacyGlobber);
@@ -1208,7 +1211,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();
-          LegacyGlobber legacyGlobberToStore = globDepsRequested.isEmpty() ? null : legacyGlobber;
+          Globber legacyGlobberToStore = globDepsRequested.isEmpty() ? null : legacyGlobber;
           astCacheEntry = new CacheEntryWithGlobDeps<>(
               new AstAfterPreprocessing(preprocessingResult, ast, astParsingEventHandler),
               globDepsRequested, legacyGlobberToStore);
@@ -1234,7 +1237,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.
-        LegacyGlobber legacyGlobber = astCacheEntry.legacyGlobber != null
+        Globber 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 1ea067d20f..6da3925e96 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,8 +55,6 @@ 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() {}
@@ -398,7 +396,7 @@ public final class UnixGlob {
     }
 
     /**
-     * Executes the glob and returns the result.
+     * Executes the glob.
      *
      * @throws InterruptedException if the thread is interrupted.
      */
@@ -501,10 +499,9 @@ public final class UnixGlob {
     }
 
     /**
-     * Performs wildcard globbing: returns the list of filenames that match any of
+     * Performs wildcard globbing: returns the sorted 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. The order
-     * of the returned list is unspecified.
+     * match {@code dirPred}. The predicate is also called for the root of the traversal.
      *
      * <p>Patterns may include "*" and "?", but not "[a-z]".
      *
@@ -533,10 +530,6 @@ 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) {
 
@@ -642,7 +635,7 @@ public final class UnixGlob {
         } else if (failure.get() != null) {
           result.setException(failure.get());
         } else {
-          result.set(ImmutableList.copyOf(results));
+          result.set(Ordering.<Path>natural().immutableSortedCopy(results));
         }
       }
     }