// Copyright 2019 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.remote.merkletree;

import static com.google.common.truth.Truth.assertThat;

import com.google.devtools.build.lib.actions.ActionInput;
import com.google.devtools.build.lib.actions.ActionInputHelper;
import com.google.devtools.build.lib.actions.Artifact;
import com.google.devtools.build.lib.actions.ArtifactRoot;
import com.google.devtools.build.lib.actions.FileArtifactValue;
import com.google.devtools.build.lib.actions.cache.VirtualActionInput;
import com.google.devtools.build.lib.actions.util.ActionsTestUtil;
import com.google.devtools.build.lib.clock.JavaClock;
import com.google.devtools.build.lib.remote.merkletree.DirectoryTree.DirectoryNode;
import com.google.devtools.build.lib.remote.merkletree.DirectoryTree.FileNode;
import com.google.devtools.build.lib.remote.merkletree.DirectoryTree.Node;
import com.google.devtools.build.lib.remote.util.DigestUtil;
import com.google.devtools.build.lib.remote.util.StaticMetadataProvider;
import com.google.devtools.build.lib.remote.util.StringActionInput;
import com.google.devtools.build.lib.vfs.DigestHashFunction;
import com.google.devtools.build.lib.vfs.FileSystem;
import com.google.devtools.build.lib.vfs.FileSystemUtils;
import com.google.devtools.build.lib.vfs.Path;
import com.google.devtools.build.lib.vfs.PathFragment;
import com.google.devtools.build.lib.vfs.inmemoryfs.InMemoryFileSystem;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.SortedMap;
import java.util.TreeMap;
import java.util.stream.Collectors;
import org.junit.Before;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.JUnit4;

/** Unit tests for {@link DirectoryTree}. */
@RunWith(JUnit4.class)
public class DirectoryTreeTest {

  private Path execRoot;
  private ArtifactRoot artifactRoot;
  private DigestUtil digestUtil;

  @Before
  public void setup() {
    FileSystem fs = new InMemoryFileSystem(new JavaClock(), DigestHashFunction.SHA256);
    execRoot = fs.getPath("/exec");
    artifactRoot = ArtifactRoot.asDerivedRoot(execRoot, execRoot.getRelative("srcs"));
    digestUtil = new DigestUtil(fs.getDigestFunction());
  }

  @Test
  public void emptyTreeShouldWork() throws Exception {
    DirectoryTree tree =
        DirectoryTreeBuilder.fromActionInputs(
            new TreeMap<>(),
            new StaticMetadataProvider(Collections.emptyMap()),
            execRoot,
            digestUtil);
    assertThat(directoryNodesAtDepth(tree, 0)).isEmpty();
    assertThat(fileNodesAtDepth(tree, 0)).isEmpty();
  }

  @Test
  public void buildingATreeOfFilesShouldWork() throws Exception {
    SortedMap<PathFragment, ActionInput> sortedInputs = new TreeMap<>();
    Map<ActionInput, FileArtifactValue> metadata = new HashMap<>();

    Artifact foo = addFile("srcs/foo.cc", "foo", sortedInputs, metadata);
    Artifact bar = addFile("srcs/bar.cc", "bar", sortedInputs, metadata);
    Artifact buzz = addFile("srcs/fizz/buzz.cc", "buzz", sortedInputs, metadata);

    DirectoryTree tree =
        DirectoryTreeBuilder.fromActionInputs(
            sortedInputs, new StaticMetadataProvider(metadata), execRoot, digestUtil);
    assertLexicographicalOrder(tree);

    assertThat(directoriesAtDepth(0, tree)).containsExactly("srcs");
    assertThat(directoriesAtDepth(1, tree)).containsExactly("fizz");
    assertThat(directoriesAtDepth(2, tree)).isEmpty();

    FileNode expectedFooNode =
        new FileNode("foo.cc", foo.getPath(), digestUtil.computeAsUtf8("foo"));
    FileNode expectedBarNode =
        new FileNode("bar.cc", bar.getPath(), digestUtil.computeAsUtf8("bar"));
    FileNode expectedBuzzNode =
        new FileNode("buzz.cc", buzz.getPath(), digestUtil.computeAsUtf8("buzz"));
    assertThat(fileNodesAtDepth(tree, 0)).isEmpty();
    assertThat(fileNodesAtDepth(tree, 1)).containsExactly(expectedFooNode, expectedBarNode);
    assertThat(fileNodesAtDepth(tree, 2)).containsExactly(expectedBuzzNode);
  }

  @Test
  public void virtualActionInputShouldWork() throws Exception {
    SortedMap<PathFragment, ActionInput> sortedInputs = new TreeMap<>();
    Map<ActionInput, FileArtifactValue> metadata = new HashMap<>();

    Artifact foo = addFile("srcs/foo.cc", "foo", sortedInputs, metadata);
    VirtualActionInput bar = addVirtualFile("srcs/bar.cc", "bar", sortedInputs);

    DirectoryTree tree =
        DirectoryTreeBuilder.fromActionInputs(
            sortedInputs, new StaticMetadataProvider(metadata), execRoot, digestUtil);
    assertLexicographicalOrder(tree);

    assertThat(directoriesAtDepth(0, tree)).containsExactly("srcs");
    assertThat(directoriesAtDepth(1, tree)).isEmpty();

    FileNode expectedFooNode =
        new FileNode("foo.cc", foo.getPath(), digestUtil.computeAsUtf8("foo"));
    FileNode expectedBarNode =
        new FileNode("bar.cc", bar.getBytes(), digestUtil.computeAsUtf8("bar"));
    assertThat(fileNodesAtDepth(tree, 0)).isEmpty();
    assertThat(fileNodesAtDepth(tree, 1)).containsExactly(expectedFooNode, expectedBarNode);
  }

  @Test
  public void directoryInputShouldBeExpanded() throws Exception {
    // Test that directory inputs are fully expanded and added to the input tree.
    // Note that this test is not about tree artifacts, but normal artifacts that point to
    // a directory on disk.

    SortedMap<PathFragment, ActionInput> sortedInputs = new TreeMap<>();
    Map<ActionInput, FileArtifactValue> metadata = new HashMap<>();

    Artifact foo = addFile("srcs/foo.cc", "foo", sortedInputs, metadata);

    Path dirPath = execRoot.getRelative("srcs/dir");
    dirPath.createDirectoryAndParents();

    Path barPath = dirPath.getRelative("bar.cc");
    FileSystemUtils.writeContentAsLatin1(barPath, "bar");
    ActionInput bar = ActionInputHelper.fromPath(barPath.relativeTo(execRoot));
    metadata.put(bar, FileArtifactValue.createForTesting(barPath));

    dirPath.getRelative("fizz").createDirectoryAndParents();
    Path buzzPath = dirPath.getRelative("fizz/buzz.cc");
    FileSystemUtils.writeContentAsLatin1(dirPath.getRelative("fizz/buzz.cc"), "buzz");
    ActionInput buzz = ActionInputHelper.fromPath(buzzPath.relativeTo(execRoot));
    metadata.put(buzz, FileArtifactValue.createForTesting(buzzPath));

    Artifact dir = ActionsTestUtil.createArtifact(artifactRoot, dirPath);
    sortedInputs.put(dirPath.relativeTo(execRoot), dir);
    metadata.put(dir, FileArtifactValue.createForTesting(dirPath));

    DirectoryTree tree =
        DirectoryTreeBuilder.fromActionInputs(
            sortedInputs, new StaticMetadataProvider(metadata), execRoot, digestUtil);
    assertLexicographicalOrder(tree);

    assertThat(directoriesAtDepth(0, tree)).containsExactly("srcs");
    assertThat(directoriesAtDepth(1, tree)).containsExactly("dir");
    assertThat(directoriesAtDepth(2, tree)).containsExactly("fizz");
    assertThat(directoriesAtDepth(3, tree)).isEmpty();

    FileNode expectedFooNode =
        new FileNode("foo.cc", foo.getPath(), digestUtil.computeAsUtf8("foo"));
    FileNode expectedBarNode =
        new FileNode(
            "bar.cc", execRoot.getRelative(bar.getExecPath()), digestUtil.computeAsUtf8("bar"));
    FileNode expectedBuzzNode =
        new FileNode(
            "buzz.cc", execRoot.getRelative(buzz.getExecPath()), digestUtil.computeAsUtf8("buzz"));
    assertThat(fileNodesAtDepth(tree, 0)).isEmpty();
    assertThat(fileNodesAtDepth(tree, 1)).containsExactly(expectedFooNode);
    assertThat(fileNodesAtDepth(tree, 2)).containsExactly(expectedBarNode);
    assertThat(fileNodesAtDepth(tree, 3)).containsExactly(expectedBuzzNode);
  }

  @Test
  public void testLexicographicalOrder() throws Exception {
    // Regression test for https://github.com/bazelbuild/bazel/pull/8008
    //
    // The issue was that before #8008 we wrongly assumed that a sorted full list of inputs would
    // also lead to sorted tree nodes. Thereby not taking into account that the path separator '/'
    // influences the sorting of the full list but not that of the tree nodes as its stripped there.
    // For example, the below full list is lexicographically sorted
    //  srcs/system-root/bar.txt
    //  srcs/system/foo.txt
    //
    // However, the tree node [system-root, system] is not (note the missing / suffix).

    SortedMap<PathFragment, ActionInput> sortedInputs = new TreeMap<>();
    Map<ActionInput, FileArtifactValue> metadata = new HashMap<>();

    addFile("srcs/system/foo.txt", "foo", sortedInputs, metadata);
    addFile("srcs/system-root/bar.txt", "bar", sortedInputs, metadata);

    DirectoryTree tree =
        DirectoryTreeBuilder.fromActionInputs(
            sortedInputs, new StaticMetadataProvider(metadata), execRoot, digestUtil);
    assertLexicographicalOrder(tree);
  }

  private Artifact addFile(
      String path,
      String content,
      SortedMap<PathFragment, ActionInput> sortedInputs,
      Map<ActionInput, FileArtifactValue> metadata)
      throws IOException {
    Path p = execRoot.getRelative(path);
    p.getParentDirectory().createDirectoryAndParents();
    FileSystemUtils.writeContentAsLatin1(p, content);
    Artifact a = ActionsTestUtil.createArtifact(artifactRoot, p);

    sortedInputs.put(PathFragment.create(path), a);
    metadata.put(a, FileArtifactValue.createForTesting(a));
    return a;
  }

  private VirtualActionInput addVirtualFile(
      String path, String content, SortedMap<PathFragment, ActionInput> sortedInputs) {
    VirtualActionInput input = new StringActionInput(content, PathFragment.create(path));
    sortedInputs.put(PathFragment.create(path), input);
    return input;
  }

  private static void assertLexicographicalOrder(DirectoryTree tree) {
    // Assert the lexicographical order as defined by the remote execution protocol
    tree.visit(
        (PathFragment dirname, List<FileNode> files, List<DirectoryNode> dirs) -> {
          assertThat(files).isStrictlyOrdered();
          assertThat(dirs).isStrictlyOrdered();
        });
  }

  private static List<String> directoriesAtDepth(int depth, DirectoryTree tree) {
    return asPathSegments(directoryNodesAtDepth(tree, depth));
  }

  private static List<String> asPathSegments(List<? extends Node> nodes) {
    return nodes.stream().map(Node::getPathSegment).collect(Collectors.toList());
  }

  private static List<DirectoryNode> directoryNodesAtDepth(DirectoryTree tree, int depth) {
    List<DirectoryNode> directoryNodes = new ArrayList<>();
    tree.visit(
        (PathFragment dirname, List<FileNode> files, List<DirectoryNode> dirs) -> {
          int currDepth = dirname.segmentCount();
          if (currDepth == depth) {
            directoryNodes.addAll(dirs);
          }
        });
    return directoryNodes;
  }

  private static List<FileNode> fileNodesAtDepth(DirectoryTree tree, int depth) {
    List<FileNode> fileNodes = new ArrayList<>();
    tree.visit(
        (PathFragment dirname, List<FileNode> files, List<DirectoryNode> dirs) -> {
          int currDepth = dirname.segmentCount();
          if (currDepth == depth) {
            fileNodes.addAll(files);
          }
        });
    return fileNodes;
  }
}