// Copyright 2018 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 static java.nio.charset.StandardCharsets.US_ASCII;

import com.google.common.base.Preconditions;
import com.google.common.collect.ImmutableMap;
import com.google.common.collect.Streams;
import com.google.common.io.BaseEncoding;
import com.google.devtools.build.lib.actions.ActionInput;
import com.google.devtools.build.lib.actions.ActionInputFileCache;
import com.google.devtools.build.lib.actions.Artifact;
import com.google.devtools.build.lib.actions.FileStateType;
import com.google.devtools.build.lib.profiler.Profiler;
import com.google.devtools.build.lib.profiler.ProfilerTask;
import com.google.devtools.build.lib.vfs.AbstractFileSystem;
import com.google.devtools.build.lib.vfs.Path;
import com.google.devtools.build.lib.vfs.PathFragment;
import com.google.devtools.build.skyframe.SkyFunction;
import com.google.protobuf.ByteString;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.InterruptedIOException;
import java.io.OutputStream;
import java.util.Collection;
import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
import java.util.function.Function;
import java.util.function.Supplier;
import java.util.logging.Logger;
import javax.annotation.Nullable;

/**
 * File system for actions.
 *
 * <p>This class is thread-safe except that
 *
 * <ul>
 *   <li>{@link updateContext} and {@link updateInputData} must be called exclusively of any other
 *       methods.
 *   <li>This class relies on synchronized access to {@link env}. If there are other threads, that
 *       access {@link env}, they must also used synchronized access.
 * </ul>
 */
final class ActionFileSystem extends AbstractFileSystem implements ActionInputFileCache {
  private static final Logger LOGGER = Logger.getLogger(ActionFileSystem.class.getName());

  /**
   * Exec root and source roots.
   *
   * <p>First entry is exec root. Used to convert paths into exec paths.
   */
  private final LinkedHashSet<PathFragment> roots = new LinkedHashSet<>();

  /** exec path → artifact and metadata */
  private final Map<PathFragment, ArtifactAndMetadata> inputs;

  /** exec path → artifact and metadata */
  private final ImmutableMap<PathFragment, ArtifactAndMutableMetadata> outputs;

  /** digest → artifacts in {@link inputs} */
  private final ConcurrentHashMap<ByteString, Artifact> reverseMap;

  /** Used to lookup metadata for optional inputs. */
  private SkyFunction.Environment env = null;

  /**
   * Called whenever there is new metadata for an output.
   *
   * <p>This is backed by injection into an {@link ActionMetadataHandler} instance so should only be
   * called once per artifact.
   */
  private MetadataConsumer metadataConsumer = null;

  ActionFileSystem(
      Map<Artifact, FileArtifactValue> inputData,
      Iterable<Artifact> allowedInputs,
      Iterable<Artifact> outputArtifacts) {
    try {
      Profiler.instance().startTask(ProfilerTask.ACTION_FS_STAGING, "staging");
      roots.add(computeExecRoot(outputArtifacts));

      // TODO(shahan): Underestimates because this doesn't account for discovered inputs. Improve
      // this estimate using data.
      this.reverseMap = new ConcurrentHashMap<>(inputData.size());

      HashMap<PathFragment, ArtifactAndMetadata> inputs = new HashMap<>();
      for (Map.Entry<Artifact, FileArtifactValue> entry : inputData.entrySet()) {
        Artifact input = entry.getKey();
        updateRootsIfSource(input);
        inputs.put(input.getExecPath(), new SimpleArtifactAndMetadata(input, entry.getValue()));
        updateReverseMapIfDigestExists(entry.getValue(), entry.getKey());
      }
      for (Artifact input : allowedInputs) {
        PathFragment execPath = input.getExecPath();
        inputs.computeIfAbsent(execPath, unused -> new OptionalInputArtifactAndMetadata(input));
        updateRootsIfSource(input);
      }
      this.inputs = inputs;

      validateRoots();

      this.outputs =
          Streams.stream(outputArtifacts)
              .collect(
                  ImmutableMap.toImmutableMap(
                      a -> a.getExecPath(), a -> new ArtifactAndMutableMetadata(a)));
    } finally {
      Profiler.instance().completeTask(ProfilerTask.ACTION_FS_STAGING);
    }
  }

  /**
   * Must be called prior to access and updated as needed.
   *
   * <p>These cannot be passed into the constructor because while {@link ActionFileSystem} is
   * action-scoped, the environment and metadata consumer change multiple times, at well defined
   * points, during the lifetime of an action.
   */
  public void updateContext(SkyFunction.Environment env, MetadataConsumer metadataConsumer) {
    this.env = env;
    this.metadataConsumer = metadataConsumer;
  }

  /** Input discovery changes the values of the input data map so it must be updated accordingly. */
  public void updateInputData(Map<Artifact, FileArtifactValue> inputData) {
    try {
      Profiler.instance().startTask(ProfilerTask.ACTION_FS_UPDATE, "update");
      boolean foundNewRoots = false;
      for (Map.Entry<Artifact, FileArtifactValue> entry : inputData.entrySet()) {
        ArtifactAndMetadata current = inputs.get(entry.getKey().getExecPath());
        if (current == null || isUnsetOptional(current)) {
          Artifact input = entry.getKey();
          inputs.put(input.getExecPath(), new SimpleArtifactAndMetadata(input, entry.getValue()));
          foundNewRoots = updateRootsIfSource(entry.getKey()) || foundNewRoots;
          updateReverseMapIfDigestExists(entry.getValue(), entry.getKey());
        }
      }
      if (foundNewRoots) {
        validateRoots();
      }
    } finally {
      Profiler.instance().completeTask(ProfilerTask.ACTION_FS_UPDATE);
    }
  }

  // -------------------- ActionInputFileCache implementation --------------------

  @Override
  @Nullable
  public FileArtifactValue getMetadata(ActionInput actionInput) {
    return apply(
        actionInput.getExecPath(),
        input -> {
          try {
            return input.getMetadata();
          } catch (IOException e) {
            // TODO(shahan): improve the handling of this error by propagating it correctly
            // through MetadataHandler.getMetadata().
            throw new IllegalStateException(e);
          }
        },
        output -> output.getMetadata(),
        () -> null);
  }

  @Override
  public boolean contentsAvailableLocally(ByteString digest) {
    // TODO(shahan): we assume this is never true, though the digests might be present. Should
    // this be relaxed for locally available source files?
    return false;
  }

  @Override
  @Nullable
  public Artifact getInputFromDigest(ByteString digest) {
    return reverseMap.get(digest);
  }

  @Override
  public Path getInputPath(ActionInput actionInput) {
    ArtifactAndMetadata input = inputs.get(actionInput.getExecPath());
    if (input != null) {
      return getPath(input.getArtifact().getPath().getPathString());
    }
    ArtifactAndMutableMetadata output = outputs.get(actionInput.getExecPath());
    if (output != null) {
      return getPath(output.getArtifact().getPath().getPathString());
    }
    // TODO(shahan): this might need to be relaxed
    throw new IllegalStateException(actionInput + " not found");
  }

  // -------------------- FileSystem implementation --------------------

  @Override
  public boolean supportsModifications(Path path) {
    return isOutput(path);
  }

  @Override
  public boolean supportsSymbolicLinksNatively(Path path) {
    return isOutput(path);
  }

  @Override
  protected boolean supportsHardLinksNatively(Path path) {
    return isOutput(path);
  }

  @Override
  public boolean isFilePathCaseSensitive() {
    return true;
  }

  /** ActionFileSystem currently doesn't track directories. */
  @Override
  public boolean createDirectory(Path path) throws IOException {
    return true;
  }

  @Override
  public void createDirectoryAndParents(Path path) throws IOException {}

  @Override
  protected long getFileSize(Path path, boolean followSymlinks) throws IOException {
    Preconditions.checkArgument(
        followSymlinks, "ActionFileSystem doesn't support no-follow: %s", path);
    return getMetadataOrThrowFileNotFound(path).getSize();
  }

  @Override
  public boolean delete(Path path) throws IOException {
    throw new UnsupportedOperationException(path.getPathString());
  }

  @Override
  protected long getLastModifiedTime(Path path, boolean followSymlinks) throws IOException {
    Preconditions.checkArgument(
        followSymlinks, "ActionFileSystem doesn't support no-follow: %s", path);
    return getMetadataOrThrowFileNotFound(path).getModifiedTime();
  }

  @Override
  public void setLastModifiedTime(Path path, long newTime) throws IOException {
    throw new UnsupportedOperationException(path.getPathString());
  }

  @Override
  protected byte[] getFastDigest(Path path, HashFunction hash) throws IOException {
    if (hash != HashFunction.MD5) {
      return null;
    }
    return getMetadataOrThrowFileNotFound(path).getDigest();
  }

  @Override
  protected boolean isSymbolicLink(Path path) {
    throw new UnsupportedOperationException(path.getPathString());
  }

  @Override
  protected boolean isDirectory(Path path, boolean followSymlinks) {
    Preconditions.checkArgument(
        followSymlinks, "ActionFileSystem doesn't support no-follow: %s", path);
    FileArtifactValue metadata = getMetadataUnchecked(path);
    return metadata == null ? false : metadata.getType() == FileStateType.DIRECTORY;
  }

  @Override
  protected boolean isFile(Path path, boolean followSymlinks) {
    Preconditions.checkArgument(
        followSymlinks, "ActionFileSystem doesn't support no-follow: %s", path);
    FileArtifactValue metadata = getMetadataUnchecked(path);
    return metadata == null ? false : metadata.getType() == FileStateType.REGULAR_FILE;
  }

  @Override
  protected boolean isSpecialFile(Path path, boolean followSymlinks) {
    Preconditions.checkArgument(
        followSymlinks, "ActionFileSystem doesn't support no-follow: %s", path);
    FileArtifactValue metadata = getMetadataUnchecked(path);
    return metadata == null ? false : metadata.getType() == FileStateType.SPECIAL_FILE;
  }

  private static String createSymbolicLinkErrorMessage(
      Path linkPath, PathFragment targetFragment, String message) {
    return "createSymbolicLink(" + linkPath + ", " + targetFragment + "): " + message;
  }

  @Override
  protected void createSymbolicLink(Path linkPath, PathFragment targetFragment) throws IOException {
    ArtifactAndMetadata input = inputs.get(asExecPath(targetFragment));
    if (input == null) {
      throw new FileNotFoundException(
          createSymbolicLinkErrorMessage(
              linkPath, targetFragment, targetFragment + " is not an input."));
    }
    ArtifactAndMutableMetadata output = outputs.get(asExecPath(linkPath));
    if (output == null) {
      throw new FileNotFoundException(
          createSymbolicLinkErrorMessage(
              linkPath, targetFragment, linkPath + " is not an output."));
    }
    output.setMetadata(input.getMetadata());
  }

  @Override
  protected PathFragment readSymbolicLink(Path path) throws IOException {
    throw new UnsupportedOperationException(path.getPathString());
  }

  @Override
  protected boolean exists(Path path, boolean followSymlinks) {
    Preconditions.checkArgument(
        followSymlinks, "ActionFileSystem doesn't support no-follow: %s", path);
    return apply(path, input -> true, output -> output.getMetadata() != null, () -> false);
  }

  @Override
  protected Collection<String> getDirectoryEntries(Path path) throws IOException {
    throw new UnsupportedOperationException(path.getPathString());
  }

  @Override
  protected boolean isReadable(Path path) throws IOException {
    return exists(path, true);
  }

  @Override
  protected void setReadable(Path path, boolean readable) throws IOException {}

  @Override
  protected boolean isWritable(Path path) throws IOException {
    return isOutput(path);
  }

  @Override
  public void setWritable(Path path, boolean writable) throws IOException {}

  @Override
  protected boolean isExecutable(Path path) throws IOException {
    return true;
  }

  @Override
  protected void setExecutable(Path path, boolean executable) throws IOException {}

  @Override
  protected InputStream getInputStream(Path path) throws IOException {
    // TODO(shahan): cleanup callers of this method and disable or maybe figure out a reasonable
    // implementation.
    LOGGER.severe("Raw read of path: " + path);
    return super.getInputStream(path);
  }

  @Override
  protected OutputStream getOutputStream(Path path, boolean append) throws IOException {
    // TODO(shahan): cleanup callers of this method and disable or maybe figure out a reasonable
    // implementation.
    LOGGER.severe("Raw write of path: " + path);
    return super.getOutputStream(path, append);
  }

  @Override
  public void renameTo(Path sourcePath, Path targetPath) throws IOException {
    throw new UnsupportedOperationException("renameTo(" + sourcePath + ", " + targetPath + ")");
  }

  @Override
  protected void createFSDependentHardLink(Path linkPath, Path originalPath) throws IOException {
    throw new UnsupportedOperationException(
        "createFSDependendHardLink(" + linkPath + ", " + originalPath + ")");
  }

  // -------------------- Implementation Helpers --------------------

  private PathFragment asExecPath(Path path) {
    return asExecPath(path.asFragment());
  }

  private PathFragment asExecPath(PathFragment fragment) {
    for (PathFragment root : roots) {
      if (fragment.startsWith(root)) {
        return fragment.relativeTo(root);
      }
    }
    throw new IllegalArgumentException(fragment + " was not found under any known root: " + roots);
  }

  private boolean isOutput(Path path) {
    return outputs.containsKey(asExecPath(path));
  }

  /**
   * Lambda-based case implementation.
   *
   * <p>One of {@code inputOp} or {@code outputOp} will be called depending on whether {@code path}
   * is an input or output.
   */
  private <T> T apply(Path path, InputFileOperator<T> inputOp, OutputFileOperator<T> outputOp)
      throws IOException {
    PathFragment execPath = asExecPath(path);
    ArtifactAndMetadata input = inputs.get(execPath);
    if (input != null) {
      return inputOp.apply(input);
    }
    ArtifactAndMutableMetadata output = outputs.get(execPath);
    if (output != null) {
      return outputOp.apply(output);
    }
    throw new FileNotFoundException(path.getPathString());
  }

  /**
   * Apply variant that doesn't throw exceptions.
   *
   * <p>Useful for implementing existence-type methods.
   */
  private <T> T apply(
      Path path,
      Function<ArtifactAndMetadata, T> inputOp,
      Function<ArtifactAndMutableMetadata, T> outputOp,
      Supplier<T> notFoundOp) {
    return apply(asExecPath(path), inputOp, outputOp, notFoundOp);
  }

  private <T> T apply(
      PathFragment execPath,
      Function<ArtifactAndMetadata, T> inputOp,
      Function<ArtifactAndMutableMetadata, T> outputOp,
      Supplier<T> notFoundOp) {
    ArtifactAndMetadata input = inputs.get(execPath);
    if (input != null) {
      return inputOp.apply(input);
    }
    ArtifactAndMutableMetadata output = outputs.get(execPath);
    if (output != null) {
      return outputOp.apply(output);
    }
    return notFoundOp.get();
  }

  private boolean updateRootsIfSource(Artifact input) {
    if (input.isSourceArtifact()) {
      return roots.add(input.getRoot().getRoot().asPath().asFragment());
    }
    return false;
  }

  /**
   * The execution root is globally unique for a build so can be derived from any output.
   *
   * <p>Outputs must be nonempty.
   */
  private static PathFragment computeExecRoot(Iterable<Artifact> outputs) {
    Artifact derived = outputs.iterator().next();
    Preconditions.checkArgument(!derived.isSourceArtifact(), derived);
    PathFragment rootFragment = derived.getRoot().getRoot().asPath().asFragment();
    int rootSegments = rootFragment.segmentCount();
    int execSegments = derived.getRoot().getExecPath().segmentCount();
    return rootFragment.subFragment(0, rootSegments - execSegments);
  }

  /**
   * Verifies that no root is the prefix of any other root.
   *
   * <p>TODO(shahan): if this is insufficiently general, we can topologically order on the prefix
   * relation between roots.
   */
  private void validateRoots() {
    for (PathFragment root1 : roots) {
      for (PathFragment root2 : roots) {
        if (root1 == root2) {
          continue;
        }
        Preconditions.checkState(!root1.startsWith(root2), "%s starts with %s", root1, root2);
      }
    }
  }

  private static ByteString toByteString(byte[] digest) {
    return ByteString.copyFrom(BaseEncoding.base16().lowerCase().encode(digest).getBytes(US_ASCII));
  }

  private static boolean isUnsetOptional(ArtifactAndMetadata input) {
    if (input instanceof OptionalInputArtifactAndMetadata) {
      OptionalInputArtifactAndMetadata optional = (OptionalInputArtifactAndMetadata) input;
      return !optional.hasMetadata();
    }
    return false;
  }

  private void updateReverseMapIfDigestExists(FileArtifactValue metadata, Artifact artifact) {
    if (metadata.getDigest() != null) {
      reverseMap.put(toByteString(metadata.getDigest()), artifact);
    }
  }

  private FileArtifactValue getMetadataOrThrowFileNotFound(Path path) throws IOException {
    return apply(
        path,
        input -> input.getMetadata(),
        output -> {
          if (output.getMetadata() == null) {
            throw new FileNotFoundException(path.getPathString());
          }
          return output.getMetadata();
        });
  }

  @Nullable
  private FileArtifactValue getMetadataUnchecked(Path path) {
    return apply(
        path,
        input -> {
          try {
            return input.getMetadata();
          } catch (IOException e) {
            // TODO(shahan): propagate this error correctly through higher level APIs.
            throw new IllegalStateException(e);
          }
        },
        output -> output.getMetadata(),
        () -> null);
  }

  @FunctionalInterface
  private static interface InputFileOperator<T> {
    T apply(ArtifactAndMetadata entry) throws IOException;
  }

  @FunctionalInterface
  private static interface OutputFileOperator<T> {
    T apply(ArtifactAndMutableMetadata entry) throws IOException;
  }

  @FunctionalInterface
  public static interface MetadataConsumer {
    void accept(Artifact artifact, FileArtifactValue value) throws IOException;
  }

  private abstract static class ArtifactAndMetadata {
    public abstract Artifact getArtifact();

    public abstract FileArtifactValue getMetadata() throws IOException;

    @Override
    public String toString() {
      String metadataText = null;
      try {
        metadataText = "" + getMetadata();
      } catch (IOException e) {
        metadataText = "Error getting metadata(" + e.getMessage() + ")";
      }
      return getArtifact() + ": " + metadataText;
    }
  }

  private static class SimpleArtifactAndMetadata extends ArtifactAndMetadata {
    private final Artifact artifact;
    private final FileArtifactValue metadata;

    private SimpleArtifactAndMetadata(Artifact artifact, FileArtifactValue metadata) {
      this.artifact = artifact;
      this.metadata = metadata;
    }

    @Override
    public Artifact getArtifact() {
      return artifact;
    }

    @Override
    public FileArtifactValue getMetadata() {
      return metadata;
    }
  }

  private class OptionalInputArtifactAndMetadata extends ArtifactAndMetadata {
    private final Artifact artifact;
    private volatile FileArtifactValue metadata = null;

    private OptionalInputArtifactAndMetadata(Artifact artifact) {
      this.artifact = artifact;
    }

    @Override
    public Artifact getArtifact() {
      return artifact;
    }

    @Override
    public FileArtifactValue getMetadata() throws IOException {
      if (metadata == null) {
        synchronized (this) {
          if (metadata == null) {
            try {
              // TODO(shahan): {@link SkyFunction.Environment} requires single-threaded access so
              // we enforce that here by making these (multithreaded) calls synchronized. It might
              // be better to make the underlying methods synchronized to avoid having another
              // caller unintentionally calling into the environment without locking.
              //
              // This is currently known to be reached from the distributor during remote include
              // scanning. It might make sense to instead of bubbling this error out all the way
              // from within the distributor, to ensure that this metadata value exists when
              // creating the spawn from the include parser, which will require slightly fewer
              // layers of error propagation and there is some batching opportunity (across the
              // parallel expansion of the include scanner).
              synchronized (env) {
                metadata = (FileArtifactValue) env.getValue(ArtifactSkyKey.key(artifact, false));
              }
            } catch (InterruptedException e) {
              throw new InterruptedIOException(e.getMessage());
            }
            if (metadata == null) {
              throw new ActionExecutionFunction.MissingDepException();
            }
            updateReverseMapIfDigestExists(metadata, artifact);
          }
        }
      }
      return metadata;
    }

    public boolean hasMetadata() {
      return metadata != null;
    }
  }

  private class ArtifactAndMutableMetadata extends ArtifactAndMetadata {
    private final Artifact artifact;
    @Nullable private volatile FileArtifactValue metadata = null;

    @Override
    public Artifact getArtifact() {
      return artifact;
    }

    @Override
    @Nullable
    public FileArtifactValue getMetadata() {
      return metadata;
    }

    public void setMetadata(FileArtifactValue metadata) throws IOException {
      metadataConsumer.accept(artifact, metadata);
      this.metadata = metadata;
    }

    private ArtifactAndMutableMetadata(Artifact artifact) {
      this.artifact = artifact;
    }
  }
}