From c0f870649f3f98dd26ef550c7c7776dabb90d86e Mon Sep 17 00:00:00 2001 From: Janak Ramakrishnan Date: Fri, 4 Mar 2016 16:22:23 +0000 Subject: -- MOS_MIGRATED_REVID=116363666 --- .../devtools/build/lib/skyframe/GlobFunction.java | 233 ++++++--------------- 1 file changed, 68 insertions(+), 165 deletions(-) diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/GlobFunction.java b/src/main/java/com/google/devtools/build/lib/skyframe/GlobFunction.java index 2044a902e0..e233cdfdd5 100644 --- a/src/main/java/com/google/devtools/build/lib/skyframe/GlobFunction.java +++ b/src/main/java/com/google/devtools/build/lib/skyframe/GlobFunction.java @@ -15,12 +15,9 @@ package com.google.devtools.build.lib.skyframe; import com.google.common.cache.Cache; import com.google.common.cache.CacheBuilder; -import com.google.common.collect.Iterables; -import com.google.common.collect.Maps; import com.google.devtools.build.lib.cmdline.PackageIdentifier; import com.google.devtools.build.lib.collect.nestedset.NestedSet; import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder; -import com.google.devtools.build.lib.util.Preconditions; import com.google.devtools.build.lib.vfs.Dirent; import com.google.devtools.build.lib.vfs.Dirent.Type; import com.google.devtools.build.lib.vfs.PathFragment; @@ -32,7 +29,6 @@ import com.google.devtools.build.skyframe.SkyFunctionException.Transience; import com.google.devtools.build.skyframe.SkyKey; import com.google.devtools.build.skyframe.SkyValue; -import java.util.Map; import java.util.regex.Pattern; import javax.annotation.Nullable; @@ -61,13 +57,10 @@ public final class GlobFunction implements SkyFunction { // exists which implies that the package's directory exists. PathFragment globSubdir = glob.getSubdir(); if (!globSubdir.equals(PathFragment.EMPTY_FRAGMENT)) { - PackageLookupValue globSubdirPkgLookupValue = - (PackageLookupValue) - env.getValue( - PackageLookupValue.key( - PackageIdentifier.create( - glob.getPackageId().getRepository(), - glob.getPackageId().getPackageFragment().getRelative(globSubdir)))); + PackageLookupValue globSubdirPkgLookupValue = (PackageLookupValue) env.getValue( + PackageLookupValue.key(PackageIdentifier.create( + glob.getPackageId().getRepository(), + glob.getPackageId().getPackageFragment().getRelative(globSubdir)))); if (globSubdirPkgLookupValue == null) { return null; } @@ -94,23 +87,16 @@ public final class GlobFunction implements SkyFunction { NestedSetBuilder matches = NestedSetBuilder.stableOrder(); - boolean globMatchesBareFile = patternTail == null; - // "**" also matches an empty segment, so try the case where it is not present. if ("**".equals(patternHead)) { - if (globMatchesBareFile) { + if (patternTail == null) { // Recursive globs aren't supposed to match the package's directory. if (!glob.excludeDirs() && !globSubdir.equals(PathFragment.EMPTY_FRAGMENT)) { matches.add(globSubdir); } } else { - SkyKey globKey = - GlobValue.internalKey( - glob.getPackageId(), - glob.getPackageRoot(), - globSubdir, - patternTail, - glob.excludeDirs()); + SkyKey globKey = GlobValue.internalKey(glob.getPackageId(), glob.getPackageRoot(), + globSubdir, patternTail, glob.excludeDirs()); GlobValue globValue = (GlobValue) env.getValue(globKey); if (globValue == null) { return null; @@ -122,7 +108,6 @@ public final class GlobFunction implements SkyFunction { PathFragment dirPathFragment = glob.getPackageId().getPackageFragment().getRelative(globSubdir); RootedPath dirRootedPath = RootedPath.toRootedPath(glob.getPackageRoot(), dirPathFragment); if (alwaysUseDirListing || containsGlobs(patternHead)) { - String subdirPattern = "**".equals(patternHead) ? glob.getPattern() : patternTail; // Pattern contains globs, so a directory listing is required. // // Note that we have good reason to believe the directory exists: if this is the @@ -136,20 +121,12 @@ public final class GlobFunction implements SkyFunction { return null; } - // In order to batch Skyframe requests, we do three passes over the directory: - // (1) Process every dirent, keeping track of values we need to request if the dirent cannot - // be processed with current information (symlink targets and subdirectory globs/package - // lookups for some subdirectories). - // (2) Get those values and process the symlinks, keeping track of subdirectory globs/package - // lookups we may need to request in case the symlink's target is a directory. - // (3) Process the necessary subdirectories. - int direntsSize = listingValue.getDirents().size(); - Map symlinkFileMap = Maps.newHashMapWithExpectedSize(direntsSize); - Map firstPassSubdirMap = Maps.newHashMapWithExpectedSize(direntsSize); - // First pass: do normal files and collect SkyKeys to request. for (Dirent dirent : listingValue.getDirents()) { Type direntType = dirent.getType(); String fileName = dirent.getName(); + + boolean isDirectory = (direntType == Dirent.Type.DIRECTORY); + if (!UnixGlob.matches(patternHead, fileName, regexPatternCache)) { continue; } @@ -158,103 +135,46 @@ public final class GlobFunction implements SkyFunction { // TODO(bazel-team): Consider extracting the symlink resolution logic. // For symlinks, look up the corresponding FileValue. This ensures that if the symlink // changes and "switches types" (say, from a file to a directory), this value will be - // invalidated. We also need the target's type to properly process the symlink. - symlinkFileMap.put( - dirent, - FileValue.key( - RootedPath.toRootedPath( - glob.getPackageRoot(), dirPathFragment.getRelative(fileName)))); - continue; - } - - if (direntType == Dirent.Type.DIRECTORY) { - SkyKey keyToRequest = getSkyKeyForSubdir(fileName, glob, subdirPattern); - if (keyToRequest != null) { - firstPassSubdirMap.put(dirent, keyToRequest); + // invalidated. + RootedPath symlinkRootedPath = RootedPath.toRootedPath(glob.getPackageRoot(), + dirPathFragment.getRelative(fileName)); + FileValue symlinkFileValue = (FileValue) env.getValue(FileValue.key(symlinkRootedPath)); + if (symlinkFileValue == null) { + continue; } - } else if (globMatchesBareFile) { - matches.add(glob.getSubdir().getRelative(fileName)); - } - } - - Map firstPassAndSymlinksResult = - env.getValues(Iterables.concat(firstPassSubdirMap.values(), symlinkFileMap.values())); - if (env.valuesMissing()) { - return null; - } - // Second pass: do symlinks, and maybe collect further SkyKeys if targets are directories. - Map symlinkSubdirMap = Maps.newHashMapWithExpectedSize(symlinkFileMap.size()); - for (Map.Entry direntAndKey : symlinkFileMap.entrySet()) { - Dirent dirent = direntAndKey.getKey(); - String fileName = dirent.getName(); - Preconditions.checkState(dirent.getType() == Dirent.Type.SYMLINK, direntAndKey); - FileValue symlinkFileValue = - Preconditions.checkNotNull( - (FileValue) firstPassAndSymlinksResult.get(direntAndKey.getValue()), direntAndKey); - if (!symlinkFileValue.isSymlink()) { - throw new GlobFunctionException( - new InconsistentFilesystemException( - "readdir and stat disagree about whether " - + ((RootedPath) direntAndKey.getValue().argument()).asPath() - + " is a symlink."), - Transience.TRANSIENT); - } - if (!symlinkFileValue.exists()) { - continue; - } - if (symlinkFileValue.isDirectory()) { - SkyKey keyToRequest = getSkyKeyForSubdir(fileName, glob, subdirPattern); - if (keyToRequest != null) { - symlinkSubdirMap.put(dirent, keyToRequest); + if (!symlinkFileValue.isSymlink()) { + throw new GlobFunctionException(new InconsistentFilesystemException( + "readdir and stat disagree about whether " + symlinkRootedPath.asPath() + + " is a symlink."), Transience.TRANSIENT); + } + if (!symlinkFileValue.exists()) { + continue; } - } else if (globMatchesBareFile) { - matches.add(glob.getSubdir().getRelative(fileName)); + isDirectory = symlinkFileValue.isDirectory(); } - } - Map secondResult = env.getValues(symlinkSubdirMap.values()); - if (env.valuesMissing()) { - return null; - } - // Third pass: do needed subdirectories. - for (Map.Entry direntAndKey : - Iterables.concat(firstPassSubdirMap.entrySet(), symlinkSubdirMap.entrySet())) { - Dirent dirent = direntAndKey.getKey(); - String fileName = dirent.getName(); - SkyKey key = direntAndKey.getValue(); - SkyValue valueRequested = - symlinkSubdirMap.containsKey(dirent) - ? secondResult.get(key) - : firstPassAndSymlinksResult.get(key); - Preconditions.checkNotNull(valueRequested, direntAndKey); - addSubdirMatchesFromSkyValue(fileName, glob, matches, valueRequested); + String subdirPattern = "**".equals(patternHead) ? glob.getPattern() : patternTail; + addFile(fileName, glob, subdirPattern, patternTail == null, isDirectory, + matches, env); } } else { // Pattern does not contain globs, so a direct stat is enough. String fileName = patternHead; - RootedPath fileRootedPath = - RootedPath.toRootedPath(glob.getPackageRoot(), dirPathFragment.getRelative(fileName)); + RootedPath fileRootedPath = RootedPath.toRootedPath(glob.getPackageRoot(), + dirPathFragment.getRelative(fileName)); FileValue fileValue = (FileValue) env.getValue(FileValue.key(fileRootedPath)); if (fileValue == null) { return null; } if (fileValue.exists()) { - if (fileValue.isDirectory()) { - SkyKey keyToRequest = getSkyKeyForSubdir(fileName, glob, patternTail); - if (keyToRequest != null) { - SkyValue valueRequested = env.getValue(keyToRequest); - if (env.valuesMissing()) { - return null; - } - addSubdirMatchesFromSkyValue(fileName, glob, matches, valueRequested); - } - } else if (globMatchesBareFile) { - matches.add(glob.getSubdir().getRelative(fileName)); - } + addFile(fileName, glob, patternTail, patternTail == null, + fileValue.isDirectory(), matches, env); } } - Preconditions.checkState(!env.valuesMissing(), skyKey); + if (env.valuesMissing()) { + return null; + } NestedSet matchesBuilt = matches.build(); // Use the same value to represent that we did not match anything. @@ -264,8 +184,10 @@ public final class GlobFunction implements SkyFunction { return new GlobValue(matchesBuilt); } - /** Returns true if the given pattern contains globs. */ - private static boolean containsGlobs(String pattern) { + /** + * Returns true if the given pattern contains globs. + */ + private boolean containsGlobs(String pattern) { return pattern.contains("*") || pattern.contains("?"); } @@ -276,60 +198,41 @@ public final class GlobFunction implements SkyFunction { * *

{@code isDirectory} must be true iff the file is a directory. * - *

Returns a {@link SkyKey} for a value that is needed to compute the files that will be added - * to {@code matches}, or {@code null} if no additional value is needed. The returned value should - * be opaquely passed to {@link #addSubdirMatchesFromSkyValue}. + *

{@code directResult} must be set if the file should be included in the result set + * directly rather than recursed into if it is a directory. */ - private static SkyKey getSkyKeyForSubdir( - String fileName, GlobDescriptor glob, String subdirPattern) { - if (subdirPattern == null) { - if (glob.excludeDirs()) { - return null; - } else { - return PackageLookupValue.key( - PackageIdentifier.create( - glob.getPackageId().getRepository(), - glob.getPackageId() - .getPackageFragment() - .getRelative(glob.getSubdir()) - .getRelative(fileName))); + private void addFile(String fileName, GlobDescriptor glob, String subdirPattern, + boolean directResult, boolean isDirectory, NestedSetBuilder matches, + Environment env) { + if (isDirectory && subdirPattern != null) { + // This is a directory, and the pattern covers files under that directory. + SkyKey subdirGlobKey = GlobValue.internalKey(glob.getPackageId(), glob.getPackageRoot(), + glob.getSubdir().getRelative(fileName), subdirPattern, glob.excludeDirs()); + GlobValue subdirGlob = (GlobValue) env.getValue(subdirGlobKey); + if (subdirGlob == null) { + return; } - } else { - // There is some more pattern to match. Get the glob for the subdirectory. Note that this - // directory may also match directly in the case of a pattern that starts with "**", but that - // match will be found in the subdirectory glob. - return GlobValue.internalKey( - glob.getPackageId(), - glob.getPackageRoot(), - glob.getSubdir().getRelative(fileName), - subdirPattern, - glob.excludeDirs()); + matches.addTransitive(subdirGlob.getMatches()); } - } - /** - * Add matches to {@code matches} coming from the directory {@code fileName} if appropriate. - * - *

{@code valueRequested} must be the SkyValue whose key was returned by - * {@link #getSkyKeyForSubdir} for these parameters. - */ - private static void addSubdirMatchesFromSkyValue( - String fileName, - GlobDescriptor glob, - NestedSetBuilder matches, - SkyValue valueRequested) { - if (valueRequested instanceof GlobValue) { - matches.addTransitive(((GlobValue) valueRequested).getMatches()); - } else { - Preconditions.checkState( - valueRequested instanceof PackageLookupValue, - "%s is not a GlobValue or PackageLookupValue (%s %s)", - valueRequested, - fileName, - glob); - if (!((PackageLookupValue) valueRequested).packageExists()) { - matches.add(glob.getSubdir().getRelative(fileName)); + if (directResult && !(isDirectory && glob.excludeDirs())) { + if (isDirectory) { + // TODO(bazel-team): Refactor. This is basically inlined code from the next recursion level. + // Ensure that subdirectories that contain other packages are not picked up. + PathFragment directory = glob.getPackageId().getPackageFragment() + .getRelative(glob.getSubdir()).getRelative(fileName); + PackageLookupValue pkgLookupValue = (PackageLookupValue) + env.getValue(PackageLookupValue.key(PackageIdentifier.create( + glob.getPackageId().getRepository(), directory))); + if (pkgLookupValue == null) { + return; + } + if (pkgLookupValue.packageExists()) { + // The file is a directory and contains another package. + return; + } } + matches.add(glob.getSubdir().getRelative(fileName)); } } -- cgit v1.2.3