// 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.github.benmanes.caffeine.cache.Caffeine;
import com.github.benmanes.caffeine.cache.CaffeineSpec;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Lists;
import com.google.common.util.concurrent.Striped;
import com.google.devtools.build.lib.actions.Artifact;
import com.google.devtools.build.lib.actions.ArtifactPathResolver;
import com.google.devtools.build.lib.vfs.FileStatus;
import com.google.devtools.build.lib.vfs.Path;
import com.google.devtools.build.lib.vfs.PathFragment;
import com.google.devtools.build.lib.vfs.Symlinks;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.concurrent.locks.Lock;

/**
 * Helper class to create directories for {@linkplain com.google.devtools.build.lib.actions.Action
 * action} outputs.
 */
public final class ActionOutputDirectoryHelper {

  // Used to prevent check-then-act races in #createOutputDirectories. See the comment there for
  // more detail.
  private static final Striped<Lock> outputDirectoryDeletionLock = Striped.lock(64);

  // Directories which are known to be created as regular directories within this invocation. This
  // implies parent directories are also regular directories.
  private final Map<PathFragment, DirectoryState> knownDirectories;

  private enum DirectoryState {
    FOUND,
    CREATED
  }

  ActionOutputDirectoryHelper(CaffeineSpec cacheBuilderSpec) {
    knownDirectories =
        Caffeine.from(cacheBuilderSpec)
            .initialCapacity(Runtime.getRuntime().availableProcessors())
            .<PathFragment, DirectoryState>build()
            .asMap();
  }

  /**
   * Creates output directories for an in-memory action file system ({@link
   * com.google.devtools.build.lib.vfs.OutputService.ActionFileSystemType#inMemoryFileSystem}).
   */
  void createActionFsOutputDirectories(
      ImmutableSet<Artifact> actionOutputs, ArtifactPathResolver artifactPathResolver)
      throws CreateOutputDirectoryException {
    Set<Path> done = new HashSet<>(); // avoid redundant calls for the same directory.
    for (Artifact outputFile : actionOutputs) {
      Path outputDir;
      if (outputFile.isTreeArtifact()) {
        outputDir = artifactPathResolver.toPath(outputFile);
      } else {
        outputDir = artifactPathResolver.toPath(outputFile).getParentDirectory();
      }

      if (done.add(outputDir)) {
        try {
          outputDir.createDirectoryAndParents();
          continue;
        } catch (IOException e) {
          /* Fall through to plan B. */
        }

        Path rootPath = artifactPathResolver.convertPath(outputFile.getRoot().getRoot().asPath());
        forceCreateDirectoryAndParents(outputDir, rootPath);
      }
    }
  }

  /**
   * Called to invalidate the cached creation of tree artifact directories when an action is going
   * to be rewound.
   *
   * <p>We use {@link #knownDirectories} to only create an output directory once per build. With
   * rewinding, actions that output tree artifacts need to recreate the directories because they are
   * deleted as part of the {@link com.google.devtools.build.lib.actions.Action#prepare} step.
   *
   * <p>Note that this does not need to be called if using an in-memory action file system ({@link
   * com.google.devtools.build.lib.vfs.OutputService.ActionFileSystemType#inMemoryFileSystem}).
   */
  void invalidateTreeArtifactDirectoryCreation(ImmutableSet<Artifact> actionOutputs) {
    for (Artifact output : actionOutputs) {
      if (output.isTreeArtifact()) {
        knownDirectories.remove(output.getPath().asFragment());
      }
    }
  }

  /**
   * Creates output directories, with ancestors, for all action outputs.
   *
   * <p>For regular file outputs, creates the parent directories, for tree outputs creates the tree
   * directory (with ancestors in both cases).
   *
   * <p>It is only valid to use this method when not using an action file system, in which case
   * please use {@link #createActionFsOutputDirectories} instead. In particular, {@linkplain
   * #knownDirectories the cache of directories}, shared across actions will cause common
   * directories to be created in action file system for only one of the actions as opposed to all
   * of them.
   */
  void createOutputDirectories(ImmutableSet<Artifact> actionOutputs)
      throws CreateOutputDirectoryException {
    Set<Path> done = new HashSet<>(); // avoid redundant calls for the same directory.
    for (Artifact outputFile : actionOutputs) {
      Path outputDir;
      // Given we know that we are not using action file system, we can get safely get paths
      // directly from the artifacts.
      if (outputFile.isTreeArtifact()) {
        outputDir = outputFile.getPath();
      } else {
        outputDir = outputFile.getPath().getParentDirectory();
      }

      if (done.add(outputDir)) {
        Path rootPath = outputFile.getRoot().getRoot().asPath();
        try {
          createAndCheckForSymlinks(outputDir, rootPath);
          continue;
        } catch (IOException e) {
          /* Fall through to plan B. */
        }

        forceCreateDirectoryAndParents(outputDir, rootPath);
      }
    }
  }

  void forceCreateDirectoryAndParents(Path outputDir, Path rootPath)
      throws CreateOutputDirectoryException {
    // Possibly some direct ancestors are not directories.  In that case, we traverse the
    // ancestors downward, deleting any non-directories. This handles the case where a file
    // becomes a directory. The traversal is done downward because otherwise we may delete
    // files through a symlink in a parent directory. Since Blaze never creates such
    // directories within a build, we have no idea where on disk we're actually deleting.
    //
    // Symlinks should not be followed so in order to clean up symlinks pointing to Fileset
    // outputs from previous builds. See bug [incremental build of Fileset fails if
    // Fileset.out was changed to be a subdirectory of the old value].
    try {
      Path p = rootPath;
      for (String segment : outputDir.relativeTo(p).segments()) {
        p = p.getRelative(segment);

        // This lock ensures that the only thread that observes a filesystem transition in
        // which the path p first exists and then does not is the thread that calls
        // p.delete() and causes the transition.
        //
        // If it were otherwise, then some thread A could test p.exists(), see that it does,
        // then test p.isDirectory(), see that p isn't a directory (because, say, thread
        // B deleted it), and then call p.delete(). That could result in two different kinds
        // of failures:
        //
        // 1) In the time between when thread A sees that p is not a directory and when thread
        // A calls p.delete(), thread B may reach the call to createDirectoryAndParents
        // and create a directory at p, which thread A then deletes. Thread B would then try
        // adding outputs to the directory it thought was there, and fail.
        //
        // 2) In the time between when thread A sees that p is not a directory and when thread
        // A calls p.delete(), thread B may create a directory at p, and then either create a
        // subdirectory beneath it or add outputs to it. Then when thread A tries to delete p,
        // it would fail.
        Lock lock = outputDirectoryDeletionLock.get(p);
        lock.lock();
        try {
          FileStatus stat = p.statIfFound(Symlinks.NOFOLLOW);
          if (stat == null) {
            // Missing entry: Break out and create expected directories.
            break;
          }
          if (stat.isDirectory()) {
            // If this directory used to be a tree artifact it won't be writable.
            p.setWritable(true);
            knownDirectories.put(p.asFragment(), DirectoryState.FOUND);
          } else {
            // p may be a file or symlink (possibly from a Fileset in a previous build).
            p.delete(); // throws IOException
            break;
          }
        } finally {
          lock.unlock();
        }
      }
      outputDir.createDirectoryAndParents();
    } catch (IOException e) {
      throw new CreateOutputDirectoryException(outputDir.asFragment(), e);
    }
  }

  /**
   * Create an output directory and ensure that no symlinks exists between the output root and the
   * output file. These are all expected to be regular directories. Violations of this expectations
   * can only come from state left behind by previous invocations or external filesystem mutation.
   */
  private void createAndCheckForSymlinks(Path dir, Path rootPath) throws IOException {
    PathFragment root = rootPath.asFragment();

    // If the output root has not been created yet, do so now.
    if (!knownDirectories.containsKey(root)) {
      FileStatus stat = rootPath.statNullable(Symlinks.NOFOLLOW);
      if (stat == null) {
        rootPath.createDirectoryAndParents();
        knownDirectories.put(root, DirectoryState.CREATED);
      } else {
        knownDirectories.put(root, DirectoryState.FOUND);
      }
    }

    // Walk up until the first known directory is found (must be root or below).
    List<Path> checkDirs = new ArrayList<>();
    while (!dir.equals(rootPath) && !knownDirectories.containsKey(dir.asFragment())) {
      checkDirs.add(dir);
      dir = dir.getParentDirectory();
    }

    // Check in reverse order (parent directory first):
    // - If symlink -> Exception.
    // - If non-existent -> Create directory and all children.
    boolean parentCreated = knownDirectories.get(dir.asFragment()) == DirectoryState.CREATED;
    for (Path path : Lists.reverse(checkDirs)) {
      if (parentCreated) {
        // If we have created this directory's parent, we know that it doesn't exist or else we
        // would know about it already. Even if a parallel thread has created it in the meantime,
        // createDirectory() will return normally and we can assume that a regular directory exists
        // afterwards.
        path.createDirectory();
        knownDirectories.put(path.asFragment(), DirectoryState.CREATED);
        continue;
      }
      boolean createdNew = path.createWritableDirectory();
      knownDirectories.put(
          path.asFragment(), createdNew ? DirectoryState.CREATED : DirectoryState.FOUND);
    }
  }

  static final class CreateOutputDirectoryException extends IOException {
    final PathFragment directoryPath;

    private CreateOutputDirectoryException(PathFragment directoryPath, IOException cause) {
      super(cause.getMessage(), cause);
      this.directoryPath = directoryPath;
    }
  }
}