diff options
Diffstat (limited to 'src/main/java/com/google')
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)); } } } |