From bce6fc5b19bf3a907497b8756a4ccabcb48e0873 Mon Sep 17 00:00:00 2001 From: Janak Ramakrishnan Date: Thu, 18 Aug 2016 16:46:09 +0000 Subject: Refactor GlobFunction to avoid random-access lookup of the returned map of a SkyFunction.Environment#getValues call. In future, we may not want to pay the cost of constructing a true map in SkyFunction.Environment implementations. This is a preliminary refactor to allow that. -- MOS_MIGRATED_REVID=130649663 --- .../devtools/build/lib/skyframe/GlobFunction.java | 107 +++++++++++---------- 1 file changed, 56 insertions(+), 51 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 ec3f7138bf..4e15d86861 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,8 +15,8 @@ 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.common.collect.Sets; 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; @@ -143,10 +143,10 @@ public final class GlobFunction implements SkyFunction { // 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 symlinkFileMap = Maps.newHashMapWithExpectedSize(direntsSize); - Map firstPassSubdirMap = Maps.newHashMapWithExpectedSize(direntsSize); + Map symlinkFileMap = Maps.newHashMapWithExpectedSize(direntsSize); + Map subdirMap = Maps.newHashMapWithExpectedSize(direntsSize); Map sortedResultMap = Maps.newTreeMap(); - // First pass: do normal files and collect SkyKeys to request. + // First pass: do normal files and collect SkyKeys to request for subdirectories and symlinks. for (Dirent dirent : listingValue.getDirents()) { Type direntType = dirent.getType(); String fileName = dirent.getName(); @@ -160,77 +160,69 @@ public final class GlobFunction implements SkyFunction { // 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)))); + glob.getPackageRoot(), dirPathFragment.getRelative(fileName))), + dirent); continue; } if (direntType == Dirent.Type.DIRECTORY) { SkyKey keyToRequest = getSkyKeyForSubdir(fileName, glob, subdirPattern); if (keyToRequest != null) { - firstPassSubdirMap.put(dirent, keyToRequest); + subdirMap.put(keyToRequest, dirent); } } else if (globMatchesBareFile) { sortedResultMap.put(dirent, glob.getSubdir().getRelative(fileName)); } } - Map firstPassAndSymlinksResult = - env.getValues(Iterables.concat(firstPassSubdirMap.values(), symlinkFileMap.values())); + Map subdirAndSymlinksResult = + env.getValues(Sets.union(subdirMap.keySet(), symlinkFileMap.keySet())); if (env.valuesMissing()) { return null; } - // Second pass: do symlinks, and maybe collect further SkyKeys if targets are directories. - Map symlinkSubdirMap = Maps.newHashMapWithExpectedSize(symlinkFileMap.size()); - for (Map.Entry 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); + Map 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 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); } - } else if (globMatchesBareFile) { - sortedResultMap.put(dirent, glob.getSubdir().getRelative(fileName)); + if (!symlinkFileValue.exists()) { + continue; + } + 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) { + sortedResultMap.put(dirent, glob.getSubdir().getRelative(fileName)); + } + } else { + processSubdir(lookedUpKeyAndValue, subdirMap, glob, sortedResultMap); } } - Map secondResult = env.getValues(symlinkSubdirMap.values()); + Map symlinkSubdirResult = env.getValues(symlinkSubdirMap.keySet()); if (env.valuesMissing()) { return null; } - // Third pass: do needed subdirectories. - for (Map.Entry 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); - Object dirMatches = getSubdirMatchesFromSkyValue(fileName, glob, valueRequested); - if (dirMatches != null) { - sortedResultMap.put(dirent, dirMatches); - } + // Third pass: do needed subdirectories of symlinked directories discovered during the second + // pass. + for (Map.Entry lookedUpKeyAndValue : symlinkSubdirResult.entrySet()) { + processSubdir(lookedUpKeyAndValue, symlinkSubdirMap, glob, sortedResultMap); } for (Map.Entry fileMatches : sortedResultMap.entrySet()) { addToMatches(fileMatches.getValue(), matches); @@ -273,6 +265,19 @@ public final class GlobFunction implements SkyFunction { return new GlobValue(matchesBuilt); } + private static void processSubdir( + Map.Entry keyAndValue, + Map subdirMap, + GlobDescriptor glob, + Map 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("?"); -- cgit v1.2.3