src/main/java/com/google/devtools/build/lib/packages/GlobCache.java - bazel - Git at Google

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