Rollback of commit bb5d5efb4b50710241b5b374eb67084f4bf08278.

--
MOS_MIGRATED_REVID=130941264

11 files changed, 217 insertions, 154 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));
         }
       }
     }
diff --git a/src/test/java/com/google/devtools/build/lib/packages/GlobCacheTest.java b/src/test/java/com/google/devtools/build/lib/packages/GlobCacheTest.java
index 7285edea34..11d301f4f8 100644
--- a/src/test/java/com/google/devtools/build/lib/packages/GlobCacheTest.java
+++ b/src/test/java/com/google/devtools/build/lib/packages/GlobCacheTest.java
@@ -14,9 +14,12 @@
 package com.google.devtools.build.lib.packages;
 
 import static com.google.common.truth.Truth.assertThat;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
 import static org.junit.Assert.fail;
 
 import com.google.common.collect.Lists;
+import com.google.common.util.concurrent.Futures;
 import com.google.devtools.build.lib.cmdline.PackageIdentifier;
 import com.google.devtools.build.lib.packages.Globber.BadGlobException;
 import com.google.devtools.build.lib.testutil.Scratch;
@@ -112,7 +115,7 @@ public class GlobCacheTest {
 
   @Test
   public void testSafeGlob() throws Exception {
-    List<Path> paths = cache.safeGlobUnsorted("*.js", false).get();
+    List<Path> paths = cache.safeGlob("*.js", false).get();
     assertPathsAre(paths,
         "/workspace/isolated/first.js", "/workspace/isolated/second.js");
   }
@@ -122,7 +125,7 @@ public class GlobCacheTest {
     for (String pattern : new String[] {
         "Foo?.txt", "List{Test}.py", "List(Test).py" }) {
       try {
-        cache.safeGlobUnsorted(pattern, false);
+        cache.safeGlob(pattern, false);
         fail("Expected pattern " + pattern + " to fail");
       } catch (BadGlobException expected) {
       }
@@ -131,13 +134,13 @@ public class GlobCacheTest {
 
   @Test
   public void testGetGlob() throws Exception {
-    List<String> glob = cache.getGlobUnsorted("*.js");
+    List<String> glob = cache.getGlob("*.js");
     assertThat(glob).containsExactly("first.js", "second.js");
   }
 
   @Test
   public void testGetGlob_subdirectory() throws Exception {
-    List<String> glob = cache.getGlobUnsorted("foo/*.js");
+    List<String> glob = cache.getGlob("foo/*.js");
     assertThat(glob).containsExactly("foo/first.js", "foo/second.js");
   }
 
@@ -145,108 +148,148 @@ public class GlobCacheTest {
   public void testGetKeySet() throws Exception {
     assertThat(cache.getKeySet()).isEmpty();
 
-    cache.getGlobUnsorted("*.java");
+    cache.getGlob("*.java");
     assertThat(cache.getKeySet()).containsExactly(Pair.of("*.java", false));
 
-    cache.getGlobUnsorted("*.java");
+    cache.getGlob("*.java");
     assertThat(cache.getKeySet()).containsExactly(Pair.of("*.java", false));
 
-    cache.getGlobUnsorted("*.js");
+    cache.getGlob("*.js");
     assertThat(cache.getKeySet()).containsExactly(Pair.of("*.java", false), Pair.of("*.js", false));
 
-    cache.getGlobUnsorted("*.java", true);
+    cache.getGlob("*.java", true);
     assertThat(cache.getKeySet()).containsExactly(Pair.of("*.java", false), Pair.of("*.js", false),
         Pair.of("*.java", true));
 
     try {
-      cache.getGlobUnsorted("invalid?");
+      cache.getGlob("invalid?");
       fail("Expected an invalid regex exception");
     } catch (BadGlobException expected) {
     }
     assertThat(cache.getKeySet()).containsExactly(Pair.of("*.java", false), Pair.of("*.js", false),
         Pair.of("*.java", true));
 
-    cache.getGlobUnsorted("foo/first.*");
+    cache.getGlob("foo/first.*");
     assertThat(cache.getKeySet()).containsExactly(Pair.of("*.java", false), Pair.of("*.java", true),
         Pair.of("*.js", false), Pair.of("foo/first.*", false));
   }
 
   @Test
   public void testGlob() throws Exception {
-    assertEmpty(cache.globUnsorted(list("*.java"), NONE, false));
+    assertEmpty(cache.glob(list("*.java"), NONE, false));
 
-    assertThat(cache.globUnsorted(list("*.*"), NONE, false)).containsExactly(
-        "first.js", "first.txt", "second.js", "second.txt");
+    assertThat(cache.glob(list("*.*"), NONE, false)).containsExactly("first.js", "first.txt",
+        "second.js", "second.txt").inOrder();
 
-    assertThat(cache.globUnsorted(list("*.*"), list("first.js"), false)).containsExactly(
-        "first.txt", "second.js", "second.txt");
+    assertThat(cache.glob(list("*.*"), list("first.js"), false)).containsExactly("first.txt",
+        "second.js", "second.txt").inOrder();
 
-    assertThat(cache.globUnsorted(list("*.txt", "first.*"), NONE, false)).containsExactly(
-        "first.txt", "second.txt", "first.js");
+    assertThat(cache.glob(list("*.txt", "first.*"), NONE, false)).containsExactly("first.txt",
+        "second.txt", "first.js").inOrder();
+  }
+
+  @Test
+  public void testSetGlobPaths() throws Exception {
+    // This pattern matches no files.
+    String pattern = "fake*.java";
+    assertThat(cache.getKeySet()).doesNotContain(pattern);
+
+    List<String> results = cache.getGlob(pattern, false);
+
+    assertThat(cache.getKeySet()).contains(Pair.of(pattern, false));
+    assertThat(results).isEmpty();
+
+    cache.setGlobPaths(pattern, false, Futures.<List<Path>>immediateFuture(Lists.newArrayList(
+        scratch.resolve("isolated/fake.txt"),
+        scratch.resolve("isolated/fake.py"))));
+
+    assertThat(cache.getGlob(pattern, false)).containsExactly("fake.py", "fake.txt");
+  }
+
+  @Test
+  public void testGlobsUpToDate() throws Exception {
+    assertTrue(cache.globsUpToDate());
+
+    // Initialize the cache
+    cache.getGlob("*.txt");
+    assertTrue(cache.globsUpToDate());
+
+    cache.getGlob("*.js");
+    assertTrue(cache.globsUpToDate());
+
+    // Change the filesystem
+    scratch.file("isolated/third.txt",
+        "# this is third.txt");
+    assertFalse(cache.globsUpToDate());
+
+    // Fool the cache to observe the method's behavior.
+    cache.setGlobPaths("*.txt", false, Futures.<List<Path>>immediateFuture(Lists.newArrayList(
+        scratch.resolve("isolated/first.txt"),
+        scratch.resolve("isolated/second.txt"),
+        scratch.resolve("isolated/third.txt"))));
+    assertTrue(cache.globsUpToDate());
   }
 
   @Test
   public void testRecursiveGlobDoesNotMatchSubpackage() throws Exception {
-    List<String> glob = cache.getGlobUnsorted("**/*.js");
+    List<String> glob = cache.getGlob("**/*.js");
     assertThat(glob).containsExactly("first.js", "second.js", "foo/first.js", "bar/first.js",
         "foo/second.js", "bar/second.js");
   }
 
   @Test
   public void testSingleFileExclude_Star() throws Exception {
-    assertThat(cache.globUnsorted(list("*"), list("first.txt"), false)).containsExactly(
-        "BUILD", "bar", "first.js", "foo", "second.js", "second.txt");
+    assertThat(cache.glob(list("*"), list("first.txt"), false)).containsExactly(
+        "BUILD", "bar", "first.js", "foo", "second.js", "second.txt").inOrder();
   }
 
   @Test
   public void testSingleFileExclude_StarStar() throws Exception {
-    assertThat(cache.globUnsorted(list("**"), list("first.txt"), false)).containsExactly(
+    assertThat(cache.glob(list("**"), list("first.txt"), false)).containsExactly(
         "BUILD", "bar", "bar/first.js", "bar/second.js", "first.js", "foo", "foo/first.js",
-        "foo/second.js", "second.js", "second.txt");
+        "foo/second.js", "second.js", "second.txt").inOrder();
   }
 
   @Test
   public void testExcludeAll_Star() throws Exception {
-    assertThat(cache.globUnsorted(list("*"), list("*"), false)).isEmpty();
+    assertThat(cache.glob(list("*"), list("*"), false)).isEmpty();
   }
 
   @Test
   public void testExcludeAll_Star_NoMatchesAnyway() throws Exception {
-    assertThat(cache.globUnsorted(list("nope"), list("*"), false)).isEmpty();
+    assertThat(cache.glob(list("nope"), list("*"), false)).isEmpty();
   }
 
   @Test
   public void testExcludeAll_StarStar() throws Exception {
-    assertThat(cache.globUnsorted(list("**"), list("**"), false)).isEmpty();
+    assertThat(cache.glob(list("**"), list("**"), false)).isEmpty();
   }
 
   @Test
   public void testExcludeAll_Manual() throws Exception {
-    assertThat(cache.globUnsorted(list("**"), list("*", "*/*", "*/*/*"), false)).isEmpty();
+    assertThat(cache.glob(list("**"), list("*", "*/*", "*/*/*"), false)).isEmpty();
   }
 
   @Test
   public void testSingleFileExcludeDoesntMatch() throws Exception {
-    assertThat(cache.globUnsorted(list("first.txt"), list("nope.txt"), false)).containsExactly(
-        "first.txt");
+    assertThat(cache.glob(list("first.txt"), list("nope.txt"), false)).containsExactly("first.txt");
   }
 
   @Test
   public void testExcludeDirectory() throws Exception {
-    assertThat(cache.globUnsorted(list("foo/*"), NONE, true)).containsExactly(
+    assertThat(cache.glob(list("foo/*"), NONE, true)).containsExactly(
         "foo/first.js", "foo/second.js");
-    assertThat(cache.globUnsorted(list("foo/*"), list("foo"), false)).containsExactly(
+    assertThat(cache.glob(list("foo/*"), list("foo"), false)).containsExactly(
         "foo/first.js", "foo/second.js");
   }
 
   @Test
   public void testChildGlobWithChildExclude() throws Exception {
-    assertThat(cache.globUnsorted(list("foo/*"), list("foo/*"), false)).isEmpty();
-    assertThat(
-        cache.globUnsorted(list("foo/first.js", "foo/second.js"), list("foo/*"), false)).isEmpty();
-    assertThat(cache.globUnsorted(list("foo/first.js"), list("foo/first.js"), false)).isEmpty();
-    assertThat(cache.globUnsorted(list("foo/first.js"), list("*/first.js"), false)).isEmpty();
-    assertThat(cache.globUnsorted(list("foo/first.js"), list("*/*"), false)).isEmpty();
+    assertThat(cache.glob(list("foo/*"), list("foo/*"), false)).isEmpty();
+    assertThat(cache.glob(list("foo/first.js", "foo/second.js"), list("foo/*"), false)).isEmpty();
+    assertThat(cache.glob(list("foo/first.js"), list("foo/first.js"), false)).isEmpty();
+    assertThat(cache.glob(list("foo/first.js"), list("*/first.js"), false)).isEmpty();
+    assertThat(cache.glob(list("foo/first.js"), list("*/*"), false)).isEmpty();
   }
 
   private void assertEmpty(Collection<?> glob) {
diff --git a/src/test/java/com/google/devtools/build/lib/packages/util/PackageFactoryApparatus.java b/src/test/java/com/google/devtools/build/lib/packages/util/PackageFactoryApparatus.java
index e53690e20c..b3740c8f8c 100644
--- a/src/test/java/com/google/devtools/build/lib/packages/util/PackageFactoryApparatus.java
+++ b/src/test/java/com/google/devtools/build/lib/packages/util/PackageFactoryApparatus.java
@@ -121,7 +121,7 @@ public class PackageFactoryApparatus {
             getPackageLocator(),
             null,
             TestUtils.getPool());
-    LegacyGlobber globber = PackageFactory.createLegacyGlobber(globCache);
+    LegacyGlobber globber = new LegacyGlobber(globCache);
     Package externalPkg =
         factory.newExternalPackageBuilder(
                 buildFile.getParentDirectory().getRelative("WORKSPACE"), "TESTING")
diff --git a/src/test/java/com/google/devtools/build/lib/packages/util/PackageFactoryTestBase.java b/src/test/java/com/google/devtools/build/lib/packages/util/PackageFactoryTestBase.java
index 5d8c1dac17..872c4e2bfb 100644
--- a/src/test/java/com/google/devtools/build/lib/packages/util/PackageFactoryTestBase.java
+++ b/src/test/java/com/google/devtools/build/lib/packages/util/PackageFactoryTestBase.java
@@ -114,7 +114,7 @@ public abstract class PackageFactoryTestBase {
             PackageFactoryApparatus.createEmptyLocator(),
             null,
             TestUtils.getPool());
-    assertThat(globCache.globUnsorted(include, exclude, false)).containsExactlyElementsIn(expected);
+    assertThat(globCache.glob(include, exclude, false)).containsExactlyElementsIn(expected);
   }
 
   @Before
diff --git a/src/test/java/com/google/devtools/build/lib/skyframe/PackageFunctionTest.java b/src/test/java/com/google/devtools/build/lib/skyframe/PackageFunctionTest.java
index 2aec5947e9..e243a82e45 100644
--- a/src/test/java/com/google/devtools/build/lib/skyframe/PackageFunctionTest.java
+++ b/src/test/java/com/google/devtools/build/lib/skyframe/PackageFunctionTest.java
@@ -434,24 +434,6 @@ public class PackageFunctionTest extends BuildViewTestCase {
             Label.parseAbsoluteUnchecked("//foo:a.config"),
             Label.parseAbsoluteUnchecked("//foo:b.txt"))
         .inOrder();
-    getSkyframeExecutor().resetEvaluator();
-    getSkyframeExecutor().preparePackageLoading(
-        new PathPackageLocator(outputBase, ImmutableList.of(rootDirectory)),
-        ConstantRuleVisibility.PUBLIC, true, 7, "",
-        UUID.randomUUID(), tsgm);
-    value = validPackage(skyKey);
-    assertThat(
-            (Iterable<Label>)
-                value
-                    .getPackage()
-                    .getTarget("foo")
-                    .getAssociatedRule()
-                    .getAttributeContainer()
-                    .getAttr("srcs"))
-        .containsExactly(
-            Label.parseAbsoluteUnchecked("//foo:a.config"),
-            Label.parseAbsoluteUnchecked("//foo:b.txt"))
-        .inOrder();
   }
 
   @Test
diff --git a/src/test/java/com/google/devtools/build/lib/vfs/GlobTest.java b/src/test/java/com/google/devtools/build/lib/vfs/GlobTest.java
index 34cfcc2db2..e8c08f00d5 100644
--- a/src/test/java/com/google/devtools/build/lib/vfs/GlobTest.java
+++ b/src/test/java/com/google/devtools/build/lib/vfs/GlobTest.java
@@ -21,6 +21,7 @@ import static org.junit.Assert.fail;
 import com.google.common.base.Predicate;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.Lists;
+import com.google.common.collect.Ordering;
 import com.google.common.util.concurrent.Uninterruptibles;
 import com.google.devtools.build.lib.testutil.TestUtils;
 import com.google.devtools.build.lib.vfs.inmemoryfs.InMemoryFileSystem;
@@ -276,6 +277,20 @@ public class GlobTest {
         new UnixGlob.Builder(tmpPath).addPatterns(patterns).globInterruptible());
   }
 
+  /**
+   * Tests that a glob returns files in sorted order.
+   */
+  @Test
+  public void testGlobEntriesAreSorted() throws Exception {
+    Collection<Path> directoryEntries = tmpPath.getDirectoryEntries();
+    List<Path> globResult = new UnixGlob.Builder(tmpPath)
+        .addPattern("*")
+        .setExcludeDirectories(false)
+        .globInterruptible();
+    assertThat(Ordering.natural().sortedCopy(directoryEntries)).containsExactlyElementsIn(
+        globResult).inOrder();
+  }
+
   private void assertIllegalPattern(String pattern) throws Exception {
     try {
       new UnixGlob.Builder(tmpPath)
diff --git a/src/test/java/com/google/devtools/build/lib/vfs/RecursiveGlobTest.java b/src/test/java/com/google/devtools/build/lib/vfs/RecursiveGlobTest.java
index 4b3b697150..5e0f7875fe 100644
--- a/src/test/java/com/google/devtools/build/lib/vfs/RecursiveGlobTest.java
+++ b/src/test/java/com/google/devtools/build/lib/vfs/RecursiveGlobTest.java
@@ -18,6 +18,7 @@ import static org.junit.Assert.fail;
 
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.Lists;
+import com.google.common.collect.Ordering;
 import com.google.devtools.build.lib.util.BlazeClock;
 import com.google.devtools.build.lib.vfs.inmemoryfs.InMemoryFileSystem;
 
@@ -28,6 +29,7 @@ import org.junit.runners.JUnit4;
 
 import java.util.Collection;
 import java.util.HashSet;
+import java.util.List;
 import java.util.Set;
 
 /**
@@ -138,6 +140,20 @@ public class RecursiveGlobTest {
     return expectedFiles;
   }
 
+  /**
+   * Tests that a recursive glob returns files in sorted order.
+   */
+  @Test
+  public void testGlobEntriesAreSorted() throws Exception {
+    List<Path> globResult = new UnixGlob.Builder(tmpPath)
+        .addPattern("**")
+        .setExcludeDirectories(false)
+        .globInterruptible();
+
+    assertThat(Ordering.natural().sortedCopy(globResult)).containsExactlyElementsIn(globResult)
+        .inOrder();
+  }
+
   @Test
   public void testRecursiveGlobsAreOptimized() throws Exception {
     long numGlobTasks = new UnixGlob.Builder(tmpPath)