--

MOS_MIGRATED_REVID=116363666

1 files 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<PathFragment> 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<Dirent, SkyKey> symlinkFileMap = Maps.newHashMapWithExpectedSize(direntsSize);
-      Map<Dirent, SkyKey> 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<SkyKey, SkyValue> 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<Dirent, SkyKey> symlinkSubdirMap = Maps.newHashMapWithExpectedSize(symlinkFileMap.size());
-      for (Map.Entry<Dirent, SkyKey> 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<SkyKey, SkyValue> secondResult = env.getValues(symlinkSubdirMap.values());
-      if (env.valuesMissing()) {
-        return null;
-      }
-      // Third pass: do needed subdirectories.
-      for (Map.Entry<Dirent, SkyKey> 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<PathFragment> 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 {
    *
    * <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 #addSubdirMatchesFromSkyValue}.
+   * <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 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<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.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.
-   *
-   * <p>{@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<PathFragment> 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));
     }
   }