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;
+ }
+}