src/main/java/com/google/devtools/build/lib/skyframe/GlobFunction.java

// 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 java.util.Map;
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 final ConcurrentHashMap<String, Pattern> regexPatternCache = new ConcurrentHashMap<>();

  private final boolean alwaysUseDirListing;

  public GlobFunction(boolean alwaysUseDirListing) {
    this.alwaysUseDirListing = alwaysUseDirListing;
  }

  @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);
          Map<SkyKey, SkyValue> listingAndRecursiveGlobMap =
              env.getValues(
                  ImmutableList.of(keyForRecursiveGlobInCurrentDirectory, directoryListingKey));
          if (env.valuesMissing()) {
            return null;
          }
          GlobValue globValue =
              (GlobValue) listingAndRecursiveGlobMap.get(keyForRecursiveGlobInCurrentDirectory);
          matches.addTransitive(globValue.getMatches());
          listingValue =
              (DirectoryListingValue) listingAndRecursiveGlobMap.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));
        }
      }

      Map<SkyKey, SkyValue> subdirAndSymlinksResult =
          env.getValues(Sets.union(subdirMap.keySet(), symlinkFileMap.keySet()));
      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 (Map.Entry<SkyKey, SkyValue> 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);
          }
          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(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 && globberOperation != Globber.Operation.SUBPACKAGES) {
            sortedResultMap.put(dirent, glob.getSubdir().getRelative(fileName));
          }
        } else {
          processSubdir(lookedUpKeyAndValue, subdirMap, glob, sortedResultMap);
        }
      }

      Map<SkyKey, SkyValue> symlinkSubdirResult = env.getValues(symlinkSubdirMap.keySet());
      if (env.valuesMissing()) {
        return null;
      }
      // Third pass: do needed subdirectories of symlinked directories discovered during the second
      // pass.
      for (Map.Entry<SkyKey, SkyValue> lookedUpKeyAndValue : symlinkSubdirResult.entrySet()) {
        processSubdir(lookedUpKeyAndValue, 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}.
   */
  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);
  }

  @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);
    }

    public GlobFunctionException(FileSymlinkInfiniteExpansionException e, Transience transience) {
      super(e, transience);
    }
  }
}