// 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.base.Predicate;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.Iterables;
import com.google.common.collect.Sets;
import com.google.devtools.build.lib.pkgcache.PathPackageLocator;
import com.google.devtools.build.lib.util.Pair;
import com.google.devtools.build.lib.util.io.TimestampGranularityMonitor;
import com.google.devtools.build.lib.vfs.Path;
import com.google.devtools.build.lib.vfs.PathFragment;
import com.google.devtools.build.lib.vfs.RootedPath;
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.io.IOException;
import java.util.ArrayList;
import java.util.TreeSet;
import java.util.concurrent.atomic.AtomicReference;

import javax.annotation.Nullable;

/**
 * A {@link SkyFunction} for {@link FileValue}s.
 *
 * <p>Most of the complexity in the implementation is associated to handling symlinks. Namely,
 * this class makes sure that {@code FileValue}s corresponding to symlinks are correctly invalidated
 * if the destination of the symlink is invalidated. Directory symlinks are also covered.
 */
public class FileFunction implements SkyFunction {
  private final AtomicReference<PathPackageLocator> pkgLocator;
  private final TimestampGranularityMonitor tsgm;
  private final ExternalFilesHelper externalFilesHelper;

  public FileFunction(AtomicReference<PathPackageLocator> pkgLocator,
      TimestampGranularityMonitor tsgm,
      ExternalFilesHelper externalFilesHelper) {
    this.pkgLocator = pkgLocator;
    this.tsgm = tsgm;
    this.externalFilesHelper = externalFilesHelper;
  }

  @Override
  public SkyValue compute(SkyKey skyKey, Environment env) throws FileFunctionException {
    RootedPath rootedPath = (RootedPath) skyKey.argument();
    RootedPath realRootedPath = null;
    FileStateValue realFileStateValue = null;
    PathFragment relativePath = rootedPath.getRelativePath();

    // Resolve ancestor symlinks, but only if the current file is not the filesystem root (has no
    // parent) or a package path root (treated opaquely and handled by skyframe's DiffAwareness
    // interface). Note that this is the first thing we do - if an ancestor is part of a
    // symlink cycle, we want to detect that quickly as it gives a more informative error message
    // than we'd get doing bogus filesystem operations.
    if (!relativePath.equals(PathFragment.EMPTY_FRAGMENT)) {
      Pair<RootedPath, FileStateValue> resolvedState =
          resolveFromAncestors(rootedPath, env);
      if (resolvedState == null) {
        return null;
      }
      realRootedPath = resolvedState.getFirst();
      realFileStateValue = resolvedState.getSecond();
    }

    FileStateValue fileStateValue = (FileStateValue) env.getValue(FileStateValue.key(rootedPath));
    if (fileStateValue == null) {
      return null;
    }
    if (realFileStateValue == null) {
      realRootedPath = rootedPath;
      realFileStateValue = fileStateValue;
    } else if (rootedPath.equals(realRootedPath) && !fileStateValue.equals(realFileStateValue)) {
      String message = String.format(
          "Some filesystem operations implied %s was a %s but others made us think it was a %s",
          rootedPath.asPath().getPathString(),
          fileStateValue.prettyPrint(),
          realFileStateValue.prettyPrint());
      throw new FileFunctionException(new InconsistentFilesystemException(message),
          Transience.TRANSIENT);
    }

    ArrayList<RootedPath> symlinkChain = new ArrayList<>();
    TreeSet<Path> orderedSeenPaths = Sets.newTreeSet();
    while (realFileStateValue.getType().equals(FileStateValue.Type.SYMLINK)) {
      symlinkChain.add(realRootedPath);
      orderedSeenPaths.add(realRootedPath.asPath());
      if (externalFilesHelper.shouldAssumeImmutable(realRootedPath)) {
        // If the file is assumed to be immutable, we want to resolve the symlink chain without
        // adding dependencies since we don't care about incremental correctness.
        try {
          Path realPath = rootedPath.asPath().resolveSymbolicLinks();
          realRootedPath = RootedPath.toRootedPathMaybeUnderRoot(realPath,
              pkgLocator.get().getPathEntries());
          realFileStateValue = FileStateValue.create(realRootedPath, tsgm);
        } catch (IOException e) {
          RootedPath root = RootedPath.toRootedPath(
              rootedPath.asPath().getFileSystem().getRootDirectory(),
              rootedPath.asPath().getFileSystem().getRootDirectory());
          return FileValue.value(
              rootedPath, fileStateValue,
              root, FileStateValue.NONEXISTENT_FILE_STATE_NODE);
        } catch (InconsistentFilesystemException e) {
          throw new FileFunctionException(e, Transience.TRANSIENT);
        }
      } else {
        Pair<RootedPath, FileStateValue> resolvedState = getSymlinkTargetRootedPath(realRootedPath,
            realFileStateValue.getSymlinkTarget(), orderedSeenPaths, symlinkChain, env);
        if (resolvedState == null) {
          return null;
        }
        realRootedPath = resolvedState.getFirst();
        realFileStateValue = resolvedState.getSecond();
      }
    }
    return FileValue.value(rootedPath, fileStateValue, realRootedPath, realFileStateValue);
  }

  /**
   * Returns the path and file state of {@code rootedPath}, accounting for ancestor symlinks, or
   * {@code null} if there was a missing dep.
   */
  @Nullable
  private Pair<RootedPath, FileStateValue> resolveFromAncestors(RootedPath rootedPath,
      Environment env) throws FileFunctionException {
    PathFragment relativePath = rootedPath.getRelativePath();
    RootedPath realRootedPath = rootedPath;
    FileValue parentFileValue = null;
    // We only resolve ancestors if the file is not assumed to be immutable (handling ancestors
    // would be too aggressive).
    if (!externalFilesHelper.shouldAssumeImmutable(rootedPath)
        && !relativePath.equals(PathFragment.EMPTY_FRAGMENT)) {
      RootedPath parentRootedPath = RootedPath.toRootedPath(rootedPath.getRoot(),
          relativePath.getParentDirectory());
      parentFileValue = (FileValue) env.getValue(FileValue.key(parentRootedPath));
      if (parentFileValue == null) {
        return null;
      }
      PathFragment baseName = new PathFragment(relativePath.getBaseName());
      RootedPath parentRealRootedPath = parentFileValue.realRootedPath();
      realRootedPath = RootedPath.toRootedPath(parentRealRootedPath.getRoot(),
          parentRealRootedPath.getRelativePath().getRelative(baseName));
      if (!parentFileValue.exists()) {
        return Pair.<RootedPath, FileStateValue>of(
            realRootedPath, FileStateValue.NONEXISTENT_FILE_STATE_NODE);
      }
    }
    FileStateValue realFileStateValue =
        (FileStateValue) env.getValue(FileStateValue.key(realRootedPath));
    if (realFileStateValue == null) {
      return null;
    }
    if (realFileStateValue.getType() != FileStateValue.Type.NONEXISTENT
        && parentFileValue != null && !parentFileValue.isDirectory()) {
      String type = realFileStateValue.getType().toString().toLowerCase();
      String message = type + " " + rootedPath.asPath() + " exists but its parent "
          + "path " + parentFileValue.realRootedPath().asPath() + " isn't an existing directory.";
      throw new FileFunctionException(new InconsistentFilesystemException(message),
          Transience.TRANSIENT);
    }
    return Pair.of(realRootedPath, realFileStateValue);
  }

  /**
   * Returns the symlink target and file state of {@code rootedPath}'s symlink to
   * {@code symlinkTarget}, accounting for ancestor symlinks, or {@code null} if there was a
   * missing dep.
   */
  @Nullable
  private Pair<RootedPath, FileStateValue> getSymlinkTargetRootedPath(RootedPath rootedPath,
      PathFragment symlinkTarget, TreeSet<Path> orderedSeenPaths,
      Iterable<RootedPath> symlinkChain, Environment env) throws FileFunctionException {
    RootedPath symlinkTargetRootedPath;
    if (symlinkTarget.isAbsolute()) {
      Path path = rootedPath.asPath().getFileSystem().getRootDirectory().getRelative(
          symlinkTarget);
      symlinkTargetRootedPath =
          RootedPath.toRootedPathMaybeUnderRoot(path, pkgLocator.get().getPathEntries());
    } else {
      Path path = rootedPath.asPath();
      Path symlinkTargetPath;
      if (path.getParentDirectory() != null) {
        RootedPath parentRootedPath = RootedPath.toRootedPathMaybeUnderRoot(
            path.getParentDirectory(), pkgLocator.get().getPathEntries());
        FileValue parentFileValue = (FileValue) env.getValue(FileValue.key(parentRootedPath));
        if (parentFileValue == null) {
          return null;
        }
        symlinkTargetPath = parentFileValue.realRootedPath().asPath().getRelative(symlinkTarget);
      } else {
        // This means '/' is a symlink to 'symlinkTarget'.
        symlinkTargetPath = path.getRelative(symlinkTarget);
      }
      symlinkTargetRootedPath = RootedPath.toRootedPathMaybeUnderRoot(symlinkTargetPath,
          pkgLocator.get().getPathEntries());
    }
    // Suppose we have a symlink chain p -> p1 -> p2 -> ... pK. We want to determine the fully
    // resolved path, if any, of p. This entails following the chain and noticing if there's a
    // symlink issue. There three sorts of issues:
    // (i) Symlink cycle:
    //   p -> p1 -> p2 -> p1
    // (ii) Unbounded expansion caused by a symlink to a descendant of a member of the chain:
    //   p -> a/b -> c/d -> a/b/e
    // (iii) Unbounded expansion caused by a symlink to an ancestor of a member of the chain:
    //   p -> a/b -> c/d -> a
    //
    // We can detect all three of these symlink issues by following the chain and deciding if each
    // new element is problematic. Here is our incremental algorithm:
    //
    // Suppose we encounter the symlink target p and we have already encountered all the paths in P:
    //   If p is in P then we have a found a cycle (i).
    //   If p is a descendant of any path p' in P then we have unbounded expansion (ii).
    //   If p is an ancestor of any path p' in P then we have unbounded expansion (iii).
    // We can check for these cases efficiently (read: sublinear time) by finding the extremal
    // candidate p' for (ii) and (iii).
    Path symlinkTargetPath = symlinkTargetRootedPath.asPath();
    SkyKey uniquenessKey = null;
    FileSymlinkException fse = null;
    Path seenFloorPath = orderedSeenPaths.floor(symlinkTargetPath);
    Path seenCeilingPath = orderedSeenPaths.ceiling(symlinkTargetPath);
    if (orderedSeenPaths.contains(symlinkTargetPath)) {
      // 'rootedPath' is a symlink to a previous element in the symlink chain (i).
      Pair<ImmutableList<RootedPath>, ImmutableList<RootedPath>> pathAndChain =
          CycleUtils.splitIntoPathAndChain(
              isPathPredicate(symlinkTargetRootedPath.asPath()), symlinkChain);
      FileSymlinkCycleException fsce =
          new FileSymlinkCycleException(pathAndChain.getFirst(), pathAndChain.getSecond());
      uniquenessKey = FileSymlinkCycleUniquenessFunction.key(fsce.getCycle());
      fse = fsce;
    } else if (seenFloorPath != null && symlinkTargetPath.startsWith(seenFloorPath)) {
      // 'rootedPath' is a symlink to a descendant of a previous element in the symlink chain (ii).
      Pair<ImmutableList<RootedPath>, ImmutableList<RootedPath>> pathAndChain =
          CycleUtils.splitIntoPathAndChain(
              isPathPredicate(seenFloorPath),
              ImmutableList.copyOf(
                  Iterables.concat(symlinkChain, ImmutableList.of(symlinkTargetRootedPath))));
      uniquenessKey = FileSymlinkInfiniteExpansionUniquenessFunction.key(pathAndChain.getSecond());
      fse = new FileSymlinkInfiniteExpansionException(
          pathAndChain.getFirst(), pathAndChain.getSecond());
    } else if (seenCeilingPath != null && seenCeilingPath.startsWith(symlinkTargetPath)) {
      // 'rootedPath' is a symlink to an ancestor of a previous element in the symlink chain (iii).
      Pair<ImmutableList<RootedPath>, ImmutableList<RootedPath>> pathAndChain =
          CycleUtils.splitIntoPathAndChain(
              isPathPredicate(seenCeilingPath),
              ImmutableList.copyOf(
                  Iterables.concat(symlinkChain, ImmutableList.of(symlinkTargetRootedPath))));
      uniquenessKey = FileSymlinkInfiniteExpansionUniquenessFunction.key(pathAndChain.getSecond());
      fse = new FileSymlinkInfiniteExpansionException(
          pathAndChain.getFirst(), pathAndChain.getSecond());
    }
    if (uniquenessKey != null) {
      if (env.getValue(uniquenessKey) == null) {
        // Note that this dependency is merely to ensure that each unique symlink error gets
        // reported exactly once.
        return null;
      }
      throw new FileFunctionException(Preconditions.checkNotNull(fse, rootedPath));
    }
    return resolveFromAncestors(symlinkTargetRootedPath, env);
  }

  private static final Predicate<RootedPath> isPathPredicate(final Path path) {
    return new Predicate<RootedPath>() {
      @Override
      public boolean apply(RootedPath rootedPath) {
        return rootedPath.asPath().equals(path);
      }
    };
  }

  @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 FileFunction#compute}.
   */
  private static final class FileFunctionException extends SkyFunctionException {

    public FileFunctionException(InconsistentFilesystemException e, Transience transience) {
      super(e, transience);
    }

    public FileFunctionException(FileSymlinkException e) {
      super(e, Transience.PERSISTENT);
    }
  }
}