in src/main/java/com/google/devtools/build/lib/skyframe/GlobFunction.java [63:344]
public SkyValue compute(SkyKey skyKey, Environment env)
throws GlobFunctionException, InterruptedException {
GlobDescriptor glob = (GlobDescriptor) skyKey.argument();
Globber.Operation globberOperation = glob.globberOperation();
RepositoryName repositoryName = glob.getPackageId().getRepository();
IgnoredPackagePrefixesValue ignoredPackagePrefixes =
(IgnoredPackagePrefixesValue) env.getValue(IgnoredPackagePrefixesValue.key(repositoryName));
if (env.valuesMissing()) {
return null;
}
PathFragment globSubdir = glob.getSubdir();
PathFragment dirPathFragment = glob.getPackageId().getPackageFragment().getRelative(globSubdir);
for (PathFragment ignoredPrefix : ignoredPackagePrefixes.getPatterns()) {
if (dirPathFragment.startsWith(ignoredPrefix)) {
return GlobValue.EMPTY;
}
}
// Note that the glob's package is assumed to exist which implies that the package's BUILD file
// exists which implies that the package's directory exists.
if (!globSubdir.equals(PathFragment.EMPTY_FRAGMENT)) {
PathFragment subDirFragment =
glob.getPackageId().getPackageFragment().getRelative(globSubdir);
PackageLookupValue globSubdirPkgLookupValue =
(PackageLookupValue)
env.getValue(
PackageLookupValue.key(PackageIdentifier.create(repositoryName, subDirFragment)));
if (globSubdirPkgLookupValue == null) {
return null;
}
if (globSubdirPkgLookupValue.packageExists()) {
// We crossed the package boundary, that is, pkg/subdir contains a BUILD file and thus
// defines another package, so glob expansion should not descend into
// that subdir.
//
// For SUBPACKAGES, we encounter this when the pattern is a recursive ** and we are a
// terminal package for that pattern. In that case we should include the subDirFragment
// PathFragment (relative to the glob's package) in the GlobValue.getMatches,
// otherwise for file/dir matching return EMPTY;
if (globberOperation == Globber.Operation.SUBPACKAGES) {
return new GlobValue(
NestedSetBuilder.<PathFragment>stableOrder()
.add(subDirFragment.relativeTo(glob.getPackageId().getPackageFragment()))
.build());
}
return GlobValue.EMPTY;
} else if (globSubdirPkgLookupValue
instanceof PackageLookupValue.IncorrectRepositoryReferencePackageLookupValue) {
// We crossed a repository boundary, so glob expansion should not descend into that subdir.
return GlobValue.EMPTY;
}
}
String pattern = glob.getPattern();
// Split off the first path component of the pattern.
int slashPos = pattern.indexOf('/');
String patternHead;
String patternTail;
if (slashPos == -1) {
patternHead = pattern;
patternTail = null;
} else {
// Substrings will share the backing array of the original glob string. That should be fine.
patternHead = pattern.substring(0, slashPos);
patternTail = pattern.substring(slashPos + 1);
}
NestedSetBuilder<PathFragment> matches = NestedSetBuilder.stableOrder();
boolean globMatchesBareFile = patternTail == null;
RootedPath dirRootedPath = RootedPath.toRootedPath(glob.getPackageRoot(), dirPathFragment);
if (alwaysUseDirListing || containsGlobs(patternHead)) {
// Pattern contains globs, so a directory listing is required.
//
// Note that we have good reason to believe the directory exists: if this is the
// top-level directory of the package, the package's existence implies the directory's
// existence; if this is a lower-level directory in the package, then we got here from
// previous directory listings. Filesystem operations concurrent with build could mean the
// directory no longer exists, but DirectoryListingFunction handles that gracefully.
SkyKey directoryListingKey = DirectoryListingValue.key(dirRootedPath);
DirectoryListingValue listingValue = null;
boolean patternHeadIsStarStar = "**".equals(patternHead);
if (patternHeadIsStarStar) {
// "**" also matches an empty segment, so try the case where it is not present.
if (globMatchesBareFile) {
// Recursive globs aren't supposed to match the package's directory.
if (globberOperation == Globber.Operation.FILES_AND_DIRS
&& !globSubdir.equals(PathFragment.EMPTY_FRAGMENT)) {
matches.add(globSubdir);
}
} else {
// Optimize away a Skyframe restart by requesting the DirectoryListingValue dep and
// recursive GlobValue dep in a single batch.
SkyKey keyForRecursiveGlobInCurrentDirectory =
GlobValue.internalKey(
glob.getPackageId(),
glob.getPackageRoot(),
globSubdir,
patternTail,
globberOperation);
Map<SkyKey, SkyValue> listingAndRecursiveGlobMap =
env.getValues(
ImmutableList.of(keyForRecursiveGlobInCurrentDirectory, directoryListingKey));
if (env.valuesMissing()) {
return null;
}
GlobValue globValue =
(GlobValue) listingAndRecursiveGlobMap.get(keyForRecursiveGlobInCurrentDirectory);
matches.addTransitive(globValue.getMatches());
listingValue =
(DirectoryListingValue) listingAndRecursiveGlobMap.get(directoryListingKey);
}
}
if (listingValue == null) {
listingValue = (DirectoryListingValue) env.getValue(directoryListingKey);
if (listingValue == null) {
return null;
}
}
// Now that we have the directory listing, we do three passes over it so as to maximize
// skyframe batching:
// (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<SkyKey, Dirent> symlinkFileMap = Maps.newHashMapWithExpectedSize(direntsSize);
Map<SkyKey, Dirent> subdirMap = Maps.newHashMapWithExpectedSize(direntsSize);
Map<Dirent, Object> sortedResultMap = Maps.newTreeMap();
String subdirPattern = patternHeadIsStarStar ? glob.getPattern() : patternTail;
// First pass: do normal files and collect SkyKeys to request for subdirectories and symlinks.
for (Dirent dirent : listingValue.getDirents()) {
Dirent.Type direntType = dirent.getType();
String fileName = dirent.getName();
if (!UnixGlob.matches(patternHead, fileName, regexPatternCache)) {
continue;
}
if (direntType == Dirent.Type.SYMLINK) {
// 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(
FileValue.key(
RootedPath.toRootedPath(
glob.getPackageRoot(), dirPathFragment.getRelative(fileName))),
dirent);
continue;
}
if (direntType == Dirent.Type.DIRECTORY) {
SkyKey keyToRequest = getSkyKeyForSubdir(fileName, glob, subdirPattern);
if (keyToRequest != null) {
subdirMap.put(keyToRequest, dirent);
}
} else if (globMatchesBareFile && globberOperation != Globber.Operation.SUBPACKAGES) {
sortedResultMap.put(dirent, glob.getSubdir().getRelative(fileName));
}
}
Map<SkyKey, SkyValue> subdirAndSymlinksResult =
env.getValues(Sets.union(subdirMap.keySet(), symlinkFileMap.keySet()));
if (env.valuesMissing()) {
return null;
}
Map<SkyKey, Dirent> symlinkSubdirMap = Maps.newHashMapWithExpectedSize(symlinkFileMap.size());
// Second pass: process the symlinks and subdirectories from the first pass, and maybe
// collect further SkyKeys if fully resolved symlink targets are themselves directories.
// Also process any known directories.
for (Map.Entry<SkyKey, SkyValue> lookedUpKeyAndValue : subdirAndSymlinksResult.entrySet()) {
if (symlinkFileMap.containsKey(lookedUpKeyAndValue.getKey())) {
FileValue symlinkFileValue = (FileValue) lookedUpKeyAndValue.getValue();
if (!symlinkFileValue.isSymlink()) {
throw new GlobFunctionException(
new InconsistentFilesystemException(
"readdir and stat disagree about whether "
+ ((RootedPath) lookedUpKeyAndValue.getKey().argument()).asPath()
+ " is a symlink."),
Transience.TRANSIENT);
}
if (!symlinkFileValue.exists()) {
continue;
}
// This check is more strict than necessary: we raise an error if globbing traverses into
// a directory for any reason, even though it's only necessary if that reason was the
// resolution of a recursive glob ("**"). Fixing this would require plumbing the ancestor
// symlink information through DirectoryListingValue.
if (symlinkFileValue.isDirectory()
&& symlinkFileValue.unboundedAncestorSymlinkExpansionChain() != null) {
SkyKey uniquenessKey =
FileSymlinkInfiniteExpansionUniquenessFunction.key(
symlinkFileValue.unboundedAncestorSymlinkExpansionChain());
env.getValue(uniquenessKey);
if (env.valuesMissing()) {
return null;
}
FileSymlinkInfiniteExpansionException symlinkException =
new FileSymlinkInfiniteExpansionException(
symlinkFileValue.pathToUnboundedAncestorSymlinkExpansionChain(),
symlinkFileValue.unboundedAncestorSymlinkExpansionChain());
throw new GlobFunctionException(symlinkException, Transience.PERSISTENT);
}
Dirent dirent = symlinkFileMap.get(lookedUpKeyAndValue.getKey());
String fileName = dirent.getName();
if (symlinkFileValue.isDirectory()) {
SkyKey keyToRequest = getSkyKeyForSubdir(fileName, glob, subdirPattern);
if (keyToRequest != null) {
symlinkSubdirMap.put(keyToRequest, dirent);
}
} else if (globMatchesBareFile && globberOperation != Globber.Operation.SUBPACKAGES) {
sortedResultMap.put(dirent, glob.getSubdir().getRelative(fileName));
}
} else {
processSubdir(lookedUpKeyAndValue, subdirMap, glob, sortedResultMap);
}
}
Map<SkyKey, SkyValue> symlinkSubdirResult = env.getValues(symlinkSubdirMap.keySet());
if (env.valuesMissing()) {
return null;
}
// Third pass: do needed subdirectories of symlinked directories discovered during the second
// pass.
for (Map.Entry<SkyKey, SkyValue> lookedUpKeyAndValue : symlinkSubdirResult.entrySet()) {
processSubdir(lookedUpKeyAndValue, symlinkSubdirMap, glob, sortedResultMap);
}
for (Map.Entry<Dirent, Object> fileMatches : sortedResultMap.entrySet()) {
addToMatches(fileMatches.getValue(), matches);
}
} else {
// Pattern does not contain globs, so a direct stat is enough.
String fileName = patternHead;
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;
}
Object fileMatches = getSubdirMatchesFromSkyValue(fileName, glob, valueRequested);
if (fileMatches != null) {
addToMatches(fileMatches, matches);
}
}
} else if (globMatchesBareFile && globberOperation != Globber.Operation.SUBPACKAGES) {
matches.add(glob.getSubdir().getRelative(fileName));
}
}
}
Preconditions.checkState(!env.valuesMissing(), skyKey);
NestedSet<PathFragment> matchesBuilt = matches.build();
// Use the same value to represent that we did not match anything.
if (matchesBuilt.isEmpty()) {
return GlobValue.EMPTY;
}
return new GlobValue(matchesBuilt);
}