Update from Google.

--
MOE_MIGRATED_REVID=85702957
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
new file mode 100644
index 0000000..3e150b4
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/packages/GlobCache.java
@@ -0,0 +1,347 @@
+// Copyright 2014 Google Inc. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//    http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+package com.google.devtools.build.lib.packages;
+
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.base.Preconditions;
+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.util.concurrent.SettableFuture;
+import com.google.devtools.build.lib.concurrent.ThreadSafety;
+import com.google.devtools.build.lib.util.Pair;
+import com.google.devtools.build.lib.vfs.Path;
+import com.google.devtools.build.lib.vfs.PathFragment;
+import com.google.devtools.build.lib.vfs.Symlinks;
+import com.google.devtools.build.lib.vfs.UnixGlob;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.HashMap;
+import java.util.LinkedHashSet;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import java.util.concurrent.ExecutionException;
+import java.util.concurrent.Future;
+import java.util.concurrent.ThreadPoolExecutor;
+import java.util.concurrent.atomic.AtomicReference;
+
+/**
+ * Caches the results of glob expansion for a package.
+ */
+@ThreadSafety.ThreadCompatible
+public class GlobCache {
+  public static class BadGlobException extends Exception {
+    BadGlobException(String message) {
+      super(message);
+    }
+  }
+
+  /**
+   * A mapping from glob expressions (e.g. "*.java") to the list of files it
+   * matched (in the order returned by VFS) at the time the package was
+   * constructed.  Required for sound dependency analysis.
+   *
+   * We don't use a Multimap because it provides no way to distinguish "key not
+   * present" from (key -> {}).
+   */
+  private final Map<Pair<String, Boolean>, Future<List<Path>>> globCache = new HashMap<>();
+
+  /**
+   * The directory in which our package's BUILD file resides.
+   */
+  private final Path packageDirectory;
+
+  /**
+   * The name of the package we belong to.
+   */
+  private final PackageIdentifier packageId;
+
+  /**
+   * The package locator-based directory traversal predicate.
+   */
+  private final Predicate<Path> childDirectoryPredicate;
+
+  /**
+   * System call caching layer.
+   */
+  private AtomicReference<? extends UnixGlob.FilesystemCalls> syscalls;
+
+  /**
+   * The thread pool for glob evaluation.
+   */
+  private final ThreadPoolExecutor globExecutor;
+
+  /**
+   * Create a glob expansion cache.
+   * @param packageDirectory globs will be expanded relatively to this
+   *                         directory.
+   * @param packageId the name of the package this cache belongs to.
+   * @param locator the package locator.
+   * @param globExecutor thread pool for glob evaluation.
+   */
+  public GlobCache(final Path packageDirectory,
+                   final PackageIdentifier packageId,
+                   final CachingPackageLocator locator,
+                   AtomicReference<? extends UnixGlob.FilesystemCalls> syscalls,
+                   ThreadPoolExecutor globExecutor) {
+    this.packageDirectory = Preconditions.checkNotNull(packageDirectory);
+    this.packageId = Preconditions.checkNotNull(packageId);
+    this.globExecutor = Preconditions.checkNotNull(globExecutor);
+    this.syscalls = syscalls == null ? new AtomicReference<>(UnixGlob.DEFAULT_SYSCALLS) : syscalls;
+
+    Preconditions.checkNotNull(locator);
+    final PathFragment pkgNameFrag = packageId.getPackageFragment();
+    childDirectoryPredicate = new Predicate<Path>() {
+      @Override
+      public boolean apply(Path directory) {
+        if (directory.equals(packageDirectory)) {
+          return true;
+        }
+
+        PathFragment pkgName = pkgNameFrag.getRelative(directory.relativeTo(packageDirectory));
+        UnixGlob.FilesystemCalls syscalls = GlobCache.this.syscalls.get();
+        if (syscalls != UnixGlob.DEFAULT_SYSCALLS) {
+          // This is needed because in case the BUILD file exists, we do not call readdir() on its
+          // directory. However, the package needs to be re-evaluated if the BUILD file is removed.
+          // Therefore, we add this BUILD file to our dependencies by statting it through the
+          // recording syscall object so that the BUILD file itself is added to the dependencies of
+          // this package.
+          //
+          // The stat() call issued by locator.getBuildFileForPackage() does not quite cut it
+          // because 1. it is cached so there may not be a stat() call at all and 2. even if there
+          // is, it does not go through the proxy in GlobCache.this.syscalls.
+          //
+          // Note that this does not cause any significant slowdown; the BUILD file cache will have
+          // already evaluated the very same stat, so we don't pay any I/O cost, only a cache
+          // lookup.
+          syscalls.statNullable(directory.getChild("BUILD"), Symlinks.FOLLOW);
+        }
+
+        return locator.getBuildFileForPackage(pkgName.getPathString()) == null;
+      }
+    };
+  }
+
+  /**
+   * Returns the future result of evaluating glob "pattern" against this
+   * package's directory, using the package's cache of previously-started
+   * globs if possible.
+   *
+   * @return the list of paths matching the pattern, relative to the package's
+   *   directory.
+   * @throws BadGlobException if the glob was syntactically invalid, or
+   *  contained uplevel references.
+   */
+  Future<List<Path>> getGlobAsync(String pattern, boolean excludeDirs)
+      throws BadGlobException {
+    Future<List<Path>> cached = globCache.get(Pair.of(pattern, excludeDirs));
+    if (cached == null) {
+      cached = safeGlob(pattern, excludeDirs);
+      setGlobPaths(pattern, excludeDirs, cached);
+    }
+    return cached;
+  }
+
+  @VisibleForTesting
+  List<String> getGlob(String pattern)
+      throws IOException, BadGlobException, InterruptedException {
+    return getGlob(pattern, false);
+  }
+
+  @VisibleForTesting
+  protected List<String> getGlob(String pattern, boolean excludeDirs)
+      throws IOException, BadGlobException, InterruptedException {
+    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.
+    if (!(futureResult instanceof SettableFuture<?>)) {
+      SettableFuture<List<Path>> completedFuture = SettableFuture.create();
+      completedFuture.set(globPaths);
+      globCache.put(Pair.of(pattern, excludeDirs), completedFuture);
+    }
+
+    List<String> result = Lists.newArrayListWithCapacity(globPaths.size());
+    for (Path path : globPaths) {
+      String relative = path.relativeTo(packageDirectory).getPathString();
+      // Don't permit "" (meaning ".") in the glob expansion, since it's
+      // invalid as a label, plus users should say explicitly if they
+      // really want to name the package directory.
+      if (!relative.isEmpty()) {
+        result.add(relative);
+      }
+    }
+    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) {
+    globCache.put(Pair.of(pattern, excludeDirectories), result);
+  }
+
+  /**
+   * Actually execute a glob against the filesystem.  Otherwise similar to
+   * getGlob().
+   */
+  @VisibleForTesting
+  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");
+    }
+    // Patterns forbidden by UnixGlob library:
+    String error = UnixGlob.checkPatternForError(pattern);
+    if (error != null) {
+      throw new BadGlobException(error + " (in glob pattern '" + pattern + "')");
+    }
+    return UnixGlob.forPath(packageDirectory)
+        .addPattern(pattern)
+        .setExcludeDirectories(excludeDirs)
+        .setDirectoryFilter(childDirectoryPredicate)
+        .setThreadPool(globExecutor)
+        .setFilesystemCalls(syscalls)
+        .globAsync(true);
+  }
+
+  /**
+   * Sanitize the future exceptions - the only expected checked exception
+   * is IOException.
+   */
+  private static List<Path> fromFuture(Future<List<Path>> future)
+      throws IOException, InterruptedException {
+    try {
+      return future.get();
+    } catch (ExecutionException e) {
+      Throwable cause = e.getCause();
+      Throwables.propagateIfPossible(cause,
+          IOException.class, InterruptedException.class);
+      throw new RuntimeException(e);
+    }
+  }
+
+  /**
+   * 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> 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)) {
+      getGlobAsync(pattern, excludeDirs);
+    }
+
+    Set<String> results = new LinkedHashSet<>();
+    for (String pattern : includes) {
+      results.addAll(getGlob(pattern, excludeDirs));
+    }
+    for (String pattern : excludes) {
+      results.removeAll(getGlob(pattern, excludeDirs));
+    }
+
+    Preconditions.checkState(!results.contains(null), "glob returned null");
+    return new ArrayList<>(results);
+  }
+
+  public Set<Pair<String, Boolean>> getKeySet() {
+    return globCache.keySet();
+  }
+
+  /**
+   * Block on the completion of all potentially-abandoned background tasks.
+   */
+  public void finishBackgroundTasks() {
+    finishBackgroundTasks(globCache.values());
+  }
+
+  public void cancelBackgroundTasks() {
+    cancelBackgroundTasks(globCache.values());
+  }
+
+  private static void finishBackgroundTasks(Collection<Future<List<Path>>> tasks) {
+    for (Future<List<Path>> task : tasks) {
+      try {
+        fromFuture(task);
+      } catch (IOException | InterruptedException e) {
+        // Ignore: If this was still going on in the background, some other
+        // failure already occurred.
+      }
+    }
+  }
+
+  private static void cancelBackgroundTasks(Collection<Future<List<Path>>> tasks) {
+    for (Future<List<Path>> task : tasks) {
+      task.cancel(true);
+
+      try {
+        task.get();
+      } catch (ExecutionException | InterruptedException e) {
+        // We don't care. Point is, the task does not bother us anymore.
+      }
+    }
+  }
+
+  @Override
+  public String toString() {
+    return "GlobCache for " + packageId + " in " + packageDirectory;
+  }
+}