Update from Google.
--
MOE_MIGRATED_REVID=85702957
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
new file mode 100644
index 0000000..a1fdcb2
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/GlobFunction.java
@@ -0,0 +1,251 @@
+// 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.skyframe;
+
+import com.google.common.base.Preconditions;
+import com.google.common.cache.Cache;
+import com.google.common.cache.CacheBuilder;
+import com.google.devtools.build.lib.collect.nestedset.NestedSet;
+import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder;
+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;
+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 java.util.regex.Pattern;
+
+import javax.annotation.Nullable;
+
+/**
+ * A {@link SkyFunction} for {@link GlobValue}s.
+ *
+ * <p>This code drives the glob matching process.
+ */
+final class GlobFunction implements SkyFunction {
+
+ private final Cache<String, Pattern> regexPatternCache =
+ CacheBuilder.newBuilder().concurrencyLevel(4).build();
+
+ @Override
+ public SkyValue compute(SkyKey skyKey, Environment env) throws GlobFunctionException {
+ GlobDescriptor glob = (GlobDescriptor) skyKey.argument();
+
+ PackageLookupValue globPkgLookupValue = (PackageLookupValue)
+ env.getValue(PackageLookupValue.key(glob.getPackageId()));
+ if (globPkgLookupValue == null) {
+ return null;
+ }
+ Preconditions.checkState(globPkgLookupValue.packageExists(), "%s isn't an existing package",
+ glob.getPackageId());
+ // Note that this implies that the package's BUILD file 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(glob.getPackageId().getPackageFragment()
+ .getRelative(globSubdir)));
+ 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.
+ 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();
+
+ // "**" also matches an empty segment, so try the case where it is not present.
+ if ("**".equals(patternHead)) {
+ if (patternTail == null) {
+ if (!glob.excludeDirs()) {
+ matches.add(globSubdir);
+ }
+ } else {
+ SkyKey globKey = GlobValue.internalKey(
+ glob.getPackageId(), globSubdir, patternTail, glob.excludeDirs());
+ GlobValue globValue = (GlobValue) env.getValue(globKey);
+ if (globValue == null) {
+ return null;
+ }
+ matches.addTransitive(globValue.getMatches());
+ }
+ }
+
+ PathFragment dirPathFragment = glob.getPackageId().getPackageFragment().getRelative(globSubdir);
+ RootedPath dirRootedPath = RootedPath.toRootedPath(globPkgLookupValue.getRoot(),
+ dirPathFragment);
+ if (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.
+ DirectoryListingValue listingValue = (DirectoryListingValue)
+ env.getValue(DirectoryListingValue.key(dirRootedPath));
+ if (listingValue == null) {
+ return null;
+ }
+
+ 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;
+ }
+
+ 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.
+ RootedPath symlinkRootedPath = RootedPath.toRootedPath(globPkgLookupValue.getRoot(),
+ dirPathFragment.getRelative(fileName));
+ FileValue symlinkFileValue = (FileValue) env.getValue(FileValue.key(symlinkRootedPath));
+ if (symlinkFileValue == null) {
+ continue;
+ }
+ if (!symlinkFileValue.isSymlink()) {
+ throw new GlobFunctionException(new InconsistentFilesystemException(
+ "readdir and stat disagree about whether " + symlinkRootedPath.asPath()
+ + " is a symlink."), Transience.TRANSIENT);
+ }
+ isDirectory = symlinkFileValue.isDirectory();
+ }
+
+ 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(globPkgLookupValue.getRoot(),
+ dirPathFragment.getRelative(fileName));
+ FileValue fileValue = (FileValue) env.getValue(FileValue.key(fileRootedPath));
+ if (fileValue == null) {
+ return null;
+ }
+ if (fileValue.exists()) {
+ addFile(fileName, glob, patternTail, patternTail == null,
+ fileValue.isDirectory(), matches, env);
+ }
+ }
+
+ if (env.valuesMissing()) {
+ return null;
+ }
+
+ 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);
+ }
+
+ /**
+ * Returns true if the given pattern contains globs.
+ */
+ private boolean containsGlobs(String pattern) {
+ return pattern.contains("*") || pattern.contains("?");
+ }
+
+ /**
+ * 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>{@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 void addFile(String fileName, GlobDescriptor glob, String subdirPattern,
+ boolean directResult, boolean isDirectory, NestedSetBuilder<PathFragment> 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.getSubdir().getRelative(fileName), subdirPattern, glob.excludeDirs());
+ GlobValue subdirGlob = (GlobValue) env.getValue(subdirGlobKey);
+ if (subdirGlob == null) {
+ return;
+ }
+ matches.addTransitive(subdirGlob.getMatches());
+ }
+
+ 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(directory));
+ if (pkgLookupValue == null) {
+ return;
+ }
+ if (pkgLookupValue.packageExists()) {
+ // The file is a directory and contains another package.
+ return;
+ }
+ }
+ matches.add(glob.getSubdir().getRelative(fileName));
+ }
+ }
+
+ @Nullable
+ @Override
+ public String extractTag(SkyKey skyKey) {
+ return null;
+ }
+
+ /**
+ * 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 {
+ public GlobFunctionException(InconsistentFilesystemException e, Transience transience) {
+ super(e, transience);
+ }
+ }
+}
