blob: 0de6a6647644cb91945a7775be5ae999fd09daf8 [file] [log] [blame]
// Copyright 2014 The Bazel Authors. 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.skyframe;
import com.google.common.base.Preconditions;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.Maps;
import com.google.common.collect.Sets;
import com.google.devtools.build.lib.actions.FileValue;
import com.google.devtools.build.lib.cmdline.PackageIdentifier;
import com.google.devtools.build.lib.cmdline.RepositoryName;
import com.google.devtools.build.lib.collect.nestedset.NestedSet;
import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
import com.google.devtools.build.lib.io.FileSymlinkInfiniteExpansionException;
import com.google.devtools.build.lib.io.FileSymlinkInfiniteExpansionUniquenessFunction;
import com.google.devtools.build.lib.io.InconsistentFilesystemException;
import com.google.devtools.build.lib.packages.Globber;
import com.google.devtools.build.lib.vfs.Dirent;
import com.google.devtools.build.lib.vfs.PathFragment;
import com.google.devtools.build.lib.vfs.RootedPath;
import com.google.devtools.build.lib.vfs.UnixGlob;
import com.google.devtools.build.skyframe.SkyFunction;
import com.google.devtools.build.skyframe.SkyFunctionException;
import com.google.devtools.build.skyframe.SkyFunctionException.Transience;
import com.google.devtools.build.skyframe.SkyKey;
import com.google.devtools.build.skyframe.SkyValue;
import com.google.devtools.build.skyframe.SkyframeLookupResult;
import java.util.Map;
import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;
import java.util.regex.Pattern;
import javax.annotation.Nullable;
/**
* A {@link SkyFunction} for {@link GlobValue}s.
*
* <p>This code drives the glob matching process.
*/
public final class GlobFunction implements SkyFunction {
private ConcurrentHashMap<String, Pattern> regexPatternCache = new ConcurrentHashMap<>();
private final boolean alwaysUseDirListing;
public GlobFunction(boolean alwaysUseDirListing) {
this.alwaysUseDirListing = alwaysUseDirListing;
}
void complete() {
this.regexPatternCache = new ConcurrentHashMap<>();
}
@Nullable
@Override
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);
SkyframeLookupResult listingAndRecursiveGlobResult =
env.getValuesAndExceptions(
ImmutableList.of(keyForRecursiveGlobInCurrentDirectory, directoryListingKey));
if (env.valuesMissing()) {
return null;
}
GlobValue globValue =
(GlobValue) listingAndRecursiveGlobResult.get(keyForRecursiveGlobInCurrentDirectory);
if (globValue == null) {
// has exception, will be handled later.
return null;
}
matches.addTransitive(globValue.getMatches());
listingValue =
(DirectoryListingValue) listingAndRecursiveGlobResult.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));
}
}
Set<SkyKey> subdirAndSymlinksKeys = Sets.union(subdirMap.keySet(), symlinkFileMap.keySet());
SkyframeLookupResult subdirAndSymlinksResult =
env.getValuesAndExceptions(subdirAndSymlinksKeys);
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 (SkyKey subdirAndSymlinksKey : subdirAndSymlinksKeys) {
if (symlinkFileMap.containsKey(subdirAndSymlinksKey)) {
FileValue symlinkFileValue =
(FileValue) subdirAndSymlinksResult.get(subdirAndSymlinksKey);
if (symlinkFileValue == null) {
return null;
}
if (!symlinkFileValue.isSymlink()) {
throw new GlobFunctionException(
new InconsistentFilesystemException(
"readdir and stat disagree about whether "
+ ((RootedPath) subdirAndSymlinksKey.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(subdirAndSymlinksKey);
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 {
SkyValue value = subdirAndSymlinksResult.get(subdirAndSymlinksKey);
if (value == null) {
return null;
}
processSubdir(Map.entry(subdirAndSymlinksKey, value), subdirMap, glob, sortedResultMap);
}
}
Set<SkyKey> symlinkSubdirKeys = symlinkSubdirMap.keySet();
SkyframeLookupResult symlinkSubdirResult = env.getValuesAndExceptions(symlinkSubdirKeys);
if (env.valuesMissing()) {
return null;
}
// Third pass: do needed subdirectories of symlinked directories discovered during the second
// pass.
for (SkyKey symlinkSubdirKey : symlinkSubdirKeys) {
SkyValue symlinkSubdirValue = symlinkSubdirResult.get(symlinkSubdirKey);
if (symlinkSubdirValue == null) {
return null;
}
processSubdir(
Map.entry(symlinkSubdirKey, symlinkSubdirValue),
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);
}
private static void processSubdir(
Map.Entry<SkyKey, SkyValue> keyAndValue,
Map<SkyKey, Dirent> subdirMap,
GlobDescriptor glob,
Map<Dirent, Object> sortedResultMap) {
Dirent dirent = Preconditions.checkNotNull(subdirMap.get(keyAndValue.getKey()), keyAndValue);
String fileName = dirent.getName();
Object dirMatches = getSubdirMatchesFromSkyValue(fileName, glob, keyAndValue.getValue());
if (dirMatches != null) {
sortedResultMap.put(dirent, dirMatches);
}
}
/** Returns true if the given pattern contains globs. */
private static boolean containsGlobs(String pattern) {
return pattern.contains("*") || pattern.contains("?");
}
@SuppressWarnings("unchecked") // cast to NestedSet<PathFragment>
private static void addToMatches(Object toAdd, NestedSetBuilder<PathFragment> matches) {
if (toAdd instanceof PathFragment) {
matches.add((PathFragment) toAdd);
} else if (toAdd instanceof NestedSet) {
matches.addTransitive((NestedSet<PathFragment>) toAdd);
}
// else Not actually a valid type and ignore.
}
/**
* Includes the given file/directory in the glob.
*
* <p>{@code fileName} must exist.
*
* <p>{@code isDirectory} must be true iff the file is a directory.
*
* <p>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 #getSubdirMatchesFromSkyValue}.
*/
@Nullable
private static SkyKey getSkyKeyForSubdir(
String fileName, GlobDescriptor glob, String subdirPattern) {
if (subdirPattern == null) {
if (glob.globberOperation() == Globber.Operation.FILES) {
return null;
}
// For FILES_AND_DIRS and SUBPACKAGES we want to maybe inspect a
// PackageLookupValue for it.
return PackageLookupValue.key(
PackageIdentifier.create(
glob.getPackageId().getRepository(),
glob.getPackageId()
.getPackageFragment()
.getRelative(glob.getSubdir())
.getRelative(fileName)));
} 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.globberOperation());
}
}
/**
* Returns an Object indicating a match was found for the given fileName in the given
* valueRequested. The Object will be one of:
*
* <ul>
* <li>{@code null} if no matches for the given parameters exists
* <li>{@code NestedSet<PathFragment>} if a match exists, either because we are looking for
* files/directories or the SkyValue is a package and we're globbing for {@link
* Globber.Operation#SUBPACKAGES}
* </ul>
*
* <p>{@code valueRequested} must be the SkyValue whose key was returned by {@link
* #getSkyKeyForSubdir} for these parameters.
*/
@Nullable
private static Object getSubdirMatchesFromSkyValue(
String fileName, GlobDescriptor glob, SkyValue valueRequested) {
if (valueRequested instanceof GlobValue) {
return ((GlobValue) valueRequested).getMatches();
}
Preconditions.checkState(
valueRequested instanceof PackageLookupValue,
"%s is not a GlobValue or PackageLookupValue (%s %s)",
valueRequested,
fileName,
glob);
PackageLookupValue packageLookupValue = (PackageLookupValue) valueRequested;
if (packageLookupValue
instanceof PackageLookupValue.IncorrectRepositoryReferencePackageLookupValue) {
// This is a separate repository, so ignore it.
return null;
}
boolean isSubpackagesOp = glob.globberOperation() == Globber.Operation.SUBPACKAGES;
boolean pkgExists = packageLookupValue.packageExists();
if (!isSubpackagesOp && pkgExists) {
// We're in our repo and fileName is a package. Since we're not doing SUBPACKAGES listing, we
// do not want to add it to the results.
return null;
} else if (isSubpackagesOp && !pkgExists) {
// We're in our repo and the package exists. Since we're doing SUBPACKAGES listing, we do
// want to add fileName to the results.
return null;
}
// The fileName should be added to the results of the glob.
return glob.getSubdir().getRelative(fileName);
}
/**
* Used to declare all the exception types that can be wrapped in the exception thrown by
* {@link GlobFunction#compute}.
*/
private static final class GlobFunctionException extends SkyFunctionException {
GlobFunctionException(InconsistentFilesystemException e, Transience transience) {
super(e, transience);
}
GlobFunctionException(FileSymlinkInfiniteExpansionException e, Transience transience) {
super(e, transience);
}
}
}