Parallelize fetches of symlink file values, subdirectory globs, and subdirectory package lookup values. This should improve change pruning speed when we have to check a glob. It also keeps GlobFunction closer to the contract of Skyframe, because in order to avoid quadratic restarts, it wasn't checking for missing deps between getValue calls.

--
MOS_MIGRATED_REVID=115882309

1 files changed, 165 insertions, 68 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 e233cdfdd5..2044a902e0 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,9 +15,12 @@ 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;
@@ -29,6 +32,7 @@ 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;
@@ -57,10 +61,13 @@ 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;
       }
@@ -87,16 +94,23 @@ 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 (patternTail == null) {
+      if (globMatchesBareFile) {
         // 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;
@@ -108,6 +122,7 @@ 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
@@ -121,12 +136,20 @@ 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;
         }
@@ -135,46 +158,103 @@ 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.
-          RootedPath symlinkRootedPath = RootedPath.toRootedPath(glob.getPackageRoot(),
-              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);
+          // 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);
           }
-          if (!symlinkFileValue.exists()) {
-            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);
           }
-          isDirectory = symlinkFileValue.isDirectory();
+        } else if (globMatchesBareFile) {
+          matches.add(glob.getSubdir().getRelative(fileName));
         }
+      }
 
-        String subdirPattern = "**".equals(patternHead) ? glob.getPattern() : patternTail;
-        addFile(fileName, glob, subdirPattern, patternTail == null, isDirectory,
-            matches, env);
+      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);
       }
     } 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()) {
-        addFile(fileName, glob, patternTail, patternTail == null,
-            fileValue.isDirectory(), matches, env);
+        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));
+        }
       }
     }
 
-    if (env.valuesMissing()) {
-      return null;
-    }
+    Preconditions.checkState(!env.valuesMissing(), skyKey);
 
     NestedSet<PathFragment> matchesBuilt = matches.build();
     // Use the same value to represent that we did not match anything.
@@ -184,10 +264,8 @@ public final class GlobFunction implements SkyFunction {
     return new GlobValue(matchesBuilt);
   }
 
-  /**
-   * Returns true if the given pattern contains globs.
-   */
-  private boolean containsGlobs(String pattern) {
+  /** Returns true if the given pattern contains globs. */
+  private static boolean containsGlobs(String pattern) {
     return pattern.contains("*") || pattern.contains("?");
   }
 
@@ -198,41 +276,60 @@ public final class GlobFunction implements SkyFunction {
    *
    * <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.
+   * <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}.
    */
-  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;
+  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)));
       }
-      matches.addTransitive(subdirGlob.getMatches());
+    } 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());
     }
+  }
 
-    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;
-        }
+  /**
+   * 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));
       }
-      matches.add(glob.getSubdir().getRelative(fileName));
     }
   }