// Copyright 2020 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.buildtool;

import static com.google.common.truth.Truth.assertThat;
import static com.google.devtools.build.lib.testutil.MoreAsserts.assertContainsEvent;
import static org.junit.Assert.assertThrows;

import com.google.common.collect.ImmutableList;
import com.google.common.collect.Iterables;
import com.google.devtools.build.lib.actions.Artifact;
import com.google.devtools.build.lib.actions.BuildFailedException;
import com.google.devtools.build.lib.analysis.ViewCreationFailedException;
import com.google.devtools.build.lib.buildtool.util.BuildIntegrationTestCase;
import com.google.devtools.build.lib.skyframe.TransitiveTargetKey;
import com.google.testing.junit.testparameterinjector.TestParameter;
import com.google.testing.junit.testparameterinjector.TestParameterInjector;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.regex.Pattern;
import org.junit.Test;
import org.junit.runner.RunWith;

/** Integration tests for the 'genquery' rule. */
@RunWith(TestParameterInjector.class)
public class GenQueryIntegrationTest extends BuildIntegrationTestCase {

  @TestParameter private boolean ttvFree;
  @TestParameter private boolean keepGoing;

  @Override
  protected void setupOptions() throws Exception {
    super.setupOptions();
    runtimeWrapper.addOptions(
        ttvFree
            ? "--experimental_skip_ttvs_for_genquery"
            : "--noexperimental_skip_ttvs_for_genquery");
    runtimeWrapper.addOptions(keepGoing ? "--keep_going" : "--nokeep_going");
  }

  @Test
  public void testDoesNotFailHorribly() throws Exception {
    write(
        "fruits/BUILD",
        "sh_library(name='melon', deps=[':papaya'])",
        "sh_library(name='papaya')",
        "genquery(name='q',",
        "         scope=[':melon'],",
        "         expression='deps(//fruits:melon)')");
    assertQueryResult("//fruits:q", "//fruits:melon", "//fruits:papaya");
  }

  private void deterministicTestHelper(boolean graphless) throws Exception {
    write(
        "fruits/BUILD",
        "sh_library(name='melon', deps=[':papaya', ':apple'])",
        "sh_library(name='papaya', deps=[':banana'])",
        "sh_library(name='banana', deps=[':apple'])",
        "sh_library(name='apple', deps=[':cherry'])",
        "sh_library(name='cherry')",
        "genquery(name='q',",
        "         scope=[':melon'],",
        "         expression='deps(//fruits:melon)')");
    String firstResult = getQueryResult("//fruits:q");
    for (int i = 0; i < 10; i++) {
      createFilesAndMocks(); // Do a clean.
      if (graphless) {
        runtimeWrapper.addOptions("--experimental_genquery_use_graphless_query");
      }
      assertThat(getQueryResult("//fruits:q")).isEqualTo(firstResult);
    }
  }

  @Test
  public void testDeterministic() throws Exception {
    deterministicTestHelper(/* graphless= */ false);
  }

  @Test
  public void testDeterministicGraphless() throws Exception {
    runtimeWrapper.addOptions("--experimental_genquery_use_graphless_query");
    deterministicTestHelper(/* graphless= */ true);
  }

  @Test
  public void testDuplicateName() throws Exception {
    write("one/BUILD", "sh_library(name='foo')");
    write("two/BUILD", "sh_library(name='foo')");
    write(
        "query/BUILD",
        "sh_library(name='common', deps=['//one:foo', '//two:foo'])",
        "genquery(name='q',",
        "         scope=['//query:common'],",
        "         expression='deps(//query:common)')");
    runtimeWrapper.addOptions("--experimental_genquery_use_graphless_query");
    assertThat(getQueryResult("//query:q").split("\n")).hasLength(3);
  }

  @Test
  public void testFailsIfGoesOutOfScope() throws Exception {
    write(
        "vegetables/BUILD",
        "sh_library(name='tomato', deps=[':cabbage'])",
        "sh_library(name='cabbage')",
        "genquery(name='q',",
        "         scope=[':cabbage'],",
        "         expression='deps(//vegetables:tomato)')");

    assertThrows(expectedExceptionClass(), () -> buildTarget("//vegetables:q"));

    assertContainsEvent(events.collector(), "is not within the scope of the query");
  }

  // Regression test for http://b/29964062.
  @Test
  public void testFailsIfGoesOutOfScopeViaSelect() throws Exception {
    write(
        "q/BUILD",
        "genquery(name='q', expression='deps(//q:f)', scope=['f'])",
        "config_setting(name='cs', values={'define':'D=1'})",
        "filegroup(name='f', srcs=select({'cs':[], '//conditions:default':['//dne']}))");

    addOptions("--define=D=1");
    assertThrows(expectedExceptionClass(), () -> buildTarget("//q"));

    events.assertContainsError(
        "in genquery rule //q:q: errors were encountered while computing transitive closure of the"
            + " scope");
    events.assertContainsError(
        Pattern.compile(
            "no such package 'dne': BUILD file not found in any of the following directories. Add a"
                + " BUILD file to a directory to mark it as a package.\n"
                + " - .*/dne"));
  }

  // Regression test for http://b/34132681
  @Test
  public void testFailsIfBrokenDependencyViaSelect() throws Exception {
    write(
        "q/BUILD",
        "genquery(name='q', expression='deps(//q:f)', scope=['f'])",
        "config_setting(name='cs', values={'define':'D=1'})",
        "filegroup(name='f', srcs=select({'cs':[], '//conditions:default':['//d:d']}))");
    // d exists but is missing "srcs"
    write("d/BUILD", "sh_binary(name = 'd')");

    addOptions("--define=D=1");
    assertThrows(expectedExceptionClass(), () -> buildTarget("//q"));

    events.assertContainsError(
        "in genquery rule //q:q: errors were encountered while computing transitive closure of the"
            + " scope");
    events.assertContainsError("Target '//d:d' contains an error and its package is in error");
  }

  @Test
  public void testResultsAlphabetized() throws Exception {
    write(
        "fruits/BUILD",
        "sh_library(name='melon', deps=[':a', ':z', ':c', ':1', '//z:a', '//a:z', '//c:c'])",
        "sh_library(name='a')",
        "sh_library(name='z')",
        "sh_library(name='1')",
        "sh_library(name='c')",
        "genquery(name='q',",
        "         scope=[':melon'],",
        "         expression='deps(//fruits:melon)')");
    write("z/BUILD", "sh_library(name = 'a')");
    write("a/BUILD", "sh_library(name = 'z')");
    write("c/BUILD", "sh_library(name = 'c', deps = ['//z:a'])");
    assertQueryResult(
        "//fruits:q",
        // Results are ordered in lexicographical order (uses graphless genquery by default).
        "//a:z",
        "//c:c",
        "//fruits:1",
        "//fruits:a",
        "//fruits:c",
        "//fruits:melon",
        "//fruits:z",
        "//z:a");
  }

  @Test
  public void testQueryReexecutedIfDepsChange() throws Exception {
    write(
        "food/BUILD",
        "sh_library(name='fruit_salad', deps=['//fruits:tropical'])",
        "genquery(name='q',",
        "         scope=[':fruit_salad'],",
        "         expression='deps(//food:fruit_salad)')");

    write(
        "fruits/BUILD",
        "sh_library(name='tropical', deps=[':papaya'])",
        "sh_library(name='papaya')");

    assertQueryResult("//food:q", "//food:fruit_salad", "//fruits:papaya", "//fruits:tropical");

    write(
        "fruits/BUILD",
        "sh_library(name='tropical', deps=[':papaya', ':coconut'])",
        "sh_library(name='papaya')",
        "sh_library(name='coconut')");

    assertQueryResult(
        "//food:q",
        "//food:fruit_salad",
        "//fruits:coconut",
        "//fruits:papaya",
        "//fruits:tropical");
  }

  @Test
  public void testGenQueryEncountersAnotherGenQuery() throws Exception {
    write(
        "spices/BUILD",
        "sh_library(name='cinnamon', deps=[':nutmeg'])",
        "sh_library(name='nutmeg')",
        "genquery(name='q',",
        "         scope=[':cinnamon'],",
        "         expression='deps(//spices:cinnamon)')");

    write(
        "fruits/BUILD",
        "sh_library(name='pear', deps=[':plum'])",
        "sh_library(name='plum')",
        "genquery(name='q',",
        "         scope=[':pear', '//spices:q'],",
        "         expression='deps(//fruits:pear) + deps(//spices:q)')");

    assertQueryResult(
        "//fruits:q",
        "//fruits:pear",
        "//fruits:plum",
        "//spices:cinnamon",
        "//spices:nutmeg",
        "//spices:q");
  }

  /**
   * Regression test for b/14227750: genquery referring to non-existent target crashes on skyframe.
   */
  @Test
  public void testHandlesMissingTargetGracefully() throws Exception {
    write(
        "a/BUILD",
        "genquery(name='query', scope=['//b:target'], expression='deps(//b:nosuchtarget)')");
    write("b/BUILD", "sh_library(name = 'target')");
    assertThrows(expectedExceptionClass(), () -> buildTarget("//a:query"));
    events.assertContainsError(
        "in genquery rule //a:query: query failed: no such target '//b:nosuchtarget'");
  }

  @Test
  public void testReportsMissingScopeTarget() throws Exception {
    write("a/BUILD", "genquery(name='query', scope=['//b:target'], expression='set()')");
    write("b/BUILD");
    assertThrows(expectedExceptionClass(), () -> buildTarget("//a:query"));
    events.assertContainsError(
        "in genquery rule //a:query: errors were encountered while computing transitive closure of"
            + " the scope");
    events.assertContainsError(
        Pattern.compile(
            "no such target '//b:target': target 'target' not declared in package 'b' defined by"
                + " .*/b/BUILD"));
  }

  @Test
  public void testReportsMissingTransitiveScopeTarget() throws Exception {
    write(
        "a/BUILD",
        "genquery(name='query', scope=[':missingdep'], expression='set()')",
        "sh_library(name='missingdep', deps=['//b:target'])");
    write("b/BUILD");
    assertThrows(expectedExceptionClass(), () -> buildTarget("//a:query"));
    events.assertContainsError(
        "in genquery rule //a:query: errors were encountered while computing transitive closure of"
            + " the scope");
    events.assertContainsError(
        Pattern.compile(
            "no such target '//b:target': target 'target' not declared in package 'b' defined by"
                + " .*/b/BUILD"));
  }

  @Test
  public void testReportsMissingScopePackage() throws Exception {
    write("a/BUILD", "genquery(name='query', scope=['//b:target'], expression='set()')");
    assertThrows(expectedExceptionClass(), () -> buildTarget("//a:query"));
    events.assertContainsError(
        "in genquery rule //a:query: errors were encountered while computing transitive closure of"
            + " the scope");
    events.assertContainsError(
        Pattern.compile(
            "no such package 'b': BUILD file not found in any of the following directories. Add a"
                + " BUILD file to a directory to mark it as a package.\n"
                + " - .*/b"));
  }

  @Test
  public void testReportsMissingTransitiveScopePackage() throws Exception {
    write(
        "a/BUILD",
        "genquery(name='query', scope=[':missingdep'], expression='set()')",
        "sh_library(name='missingdep', deps=['//b:target'])");
    assertThrows(expectedExceptionClass(), () -> buildTarget("//a:query"));
    events.assertContainsError(
        "in genquery rule //a:query: errors were encountered while computing transitive closure"
            + " of the scope");
    events.assertContainsError(
        Pattern.compile(
            "no such package 'b': BUILD file not found in any of the following"
                + " directories. Add a BUILD file to a directory to mark it as a package.\n"
                + " - .*/b"));
  }

  @Test
  public void testMultiplePatternsInQuery() throws Exception {
    String buildFile = "";
    String genQuery =
        "genquery(name = 'q', scope = [':top'], expression = 'deps(//spices:top) ' + \n";
    String topTarget = "sh_library(name = 'top', deps = [\n";
    for (int i = 0; i < 20; i++) {
      String targetName = (i % 2 == 0 ? "in" : "out") + i;
      buildFile += "sh_library(name = '" + targetName + "')\n";
      if (i % 2 != 0) {
        genQuery += "' - //spices:" + targetName + " ' + \n";
      }
      topTarget += "    ':" + targetName + "',\n";
    }
    topTarget += "]\n)\n";
    genQuery += "'')";
    write("spices/BUILD", buildFile, topTarget, genQuery);
    List<String> expected = new ArrayList<>(11);
    for (int i = 0; i < 20; i += 2) {
      expected.add(i / 2, "//spices:in" + i);
    }
    expected.add(0, "//spices:top");
    Collections.sort(expected);
    assertQueryResult("//spices:q", expected.toArray(new String[0]));
  }

  @Test
  public void testGraphOutput_factored() throws Exception {
    write(
        "fruits/BUILD",
        "sh_library(name='melon', deps=[':papaya', ':coconut', ':mango'])",
        "sh_library(name='papaya')",
        "sh_library(name = 'mango')",
        "sh_library(name = 'coconut')",
        "genquery(name='q',",
        "         scope=[':melon'],",
        "         opts = ['--output=graph'],",
        "         expression='deps(//fruits:melon)')");
    assertPartialQueryResult(
        "//fruits:q",
        "  \"//fruits:melon\"",
        "  \"//fruits:melon\" -> \"//fruits:coconut\\n//fruits:mango\\n//fruits:papaya\"",
        "  \"//fruits:coconut\\n//fruits:mango\\n//fruits:papaya\"");
  }

  @Test
  public void testGraphOutput_unfactored() throws Exception {
    write(
        "fruits/BUILD",
        "sh_library(name='melon', deps=[':papaya', ':coconut', ':mango'])",
        "sh_library(name='papaya')",
        "sh_library(name = 'mango')",
        "sh_library(name = 'coconut')",
        "genquery(name='q',",
        "         scope=[':melon'],",
        "         opts = ['--output=graph', '--nograph:factored'],",
        "         expression='deps(//fruits:melon)')");
    assertPartialQueryResult(
        "//fruits:q",
        "  \"//fruits:melon\"",
        "  \"//fruits:melon\" -> \"//fruits:coconut\"",
        "  \"//fruits:melon\" -> \"//fruits:mango\"",
        "  \"//fruits:melon\" -> \"//fruits:papaya\"",
        "  \"//fruits:papaya\"",
        "  \"//fruits:mango\"",
        "  \"//fruits:coconut\"");
  }

  @Test
  public void testDoesntAllowLocationOutputWithLoadfiles() throws Exception {
    write("foo/bzl.bzl", "x = 2");
    write(
        "foo/BUILD",
        "load('//foo:bzl.bzl', 'x')",
        "sh_library(name='foo')",
        "genquery(",
        "  name = 'gen-loadfiles',",
        "  expression = 'loadfiles(//foo:foo)',",
        "  scope = ['//foo:foo'],",
        ")",
        "genquery(",
        "  name = 'gen-loadfiles-location',",
        "  expression = 'loadfiles(//foo:foo)',",
        "  opts = ['--output=location'],",
        "  scope = ['//foo:foo'],",
        ")");
    assertQueryResult("//foo:gen-loadfiles", "//foo:bzl.bzl");
    assertThrows(expectedExceptionClass(), () -> buildTarget("//foo:gen-loadfiles-location"));
    events.assertContainsError(
        "in genquery rule //foo:gen-loadfiles-location: query failed: Query expressions "
            + "involving 'buildfiles' or 'loadfiles' cannot be used with --output=location");
  }

  @Test
  public void testDoesntAllowLocationOutputWithBuildfiles() throws Exception {
    write("foo/bzl.bzl", "x = 2");
    write(
        "foo/BUILD",
        "load('//foo:bzl.bzl', 'x')",
        "sh_library(name='foo')",
        "genquery(",
        "  name = 'gen-buildfiles',",
        "  expression = 'buildfiles(//foo:foo)',",
        "  scope = ['//foo:foo'],",
        ")",
        "genquery(",
        "  name = 'gen-buildfiles-location',",
        "  expression = 'buildfiles(//foo:foo)',",
        "  opts = ['--output=location'],",
        "  scope = ['//foo:foo'],",
        ")");
    assertQueryResult("//foo:gen-buildfiles", "//foo:BUILD", "//foo:bzl.bzl");
    assertThrows(expectedExceptionClass(), () -> buildTarget("//foo:gen-buildfiles-location"));
    events.assertContainsError(
        "in genquery rule //foo:gen-buildfiles-location: query failed: Query expressions "
            + "involving 'buildfiles' or 'loadfiles' cannot be used with --output=location");
  }

  /** Regression test for b/127644784. */
  @Test
  public void somepathOutputDeterministic() throws Exception {
    /*
     * This graph structure routinely reproduces the bug within 10 iterations:
     *
     *   ----------top------------
     *   |       |       |       |
     *  mid1    mid2    mid3    mid4
     *   |       |       |       |
     *   --lower--       |       |
     *       |           |       |
     *       -----bottom----------
     */
    write(
        "query/BUILD",
        "genquery(",
        "  name = 'query',",
        "  expression = 'somepath(//top, //bottom)',",
        "  scope = ['//top', '//bottom'],",
        ")");
    write("top/BUILD", "sh_library(name = 'top', deps = ['//mid1', '//mid2', '//mid3', '//mid4'])");
    write("mid1/BUILD", "sh_library(name = 'mid1', deps = ['//lower'])");
    write("mid2/BUILD", "sh_library(name = 'mid2', deps = ['//lower'])");
    write("mid3/BUILD", "sh_library(name = 'mid3', deps = ['//bottom'])");
    write("mid4/BUILD", "sh_library(name = 'mid4', deps = ['//bottom'])");
    write("lower/BUILD", "sh_library(name = 'lower', deps = ['//bottom'])");
    write("bottom/BUILD", "sh_library(name = 'bottom')");

    String firstResult = getQueryResult("//query");
    for (int i = 0; i < 10; i++) {
      createFilesAndMocks(); // Do a clean.
      assertThat(getQueryResult("//query")).isEqualTo(firstResult);
    }
  }

  private void runNodepDepsTest(String optsStringValue, boolean expectVisibilityDep)
      throws Exception {
    write(
        "foo/BUILD",
        "sh_library(name = 't1', deps = [':t2'], visibility = [':pg', '//query:__pkg__'])",
        "sh_library(name = 't2')",
        "package_group(name = 'pg')");
    write(
        "query/BUILD",
        "genquery(",
        "  name = 'gen',",
        "  expression = 'deps(//foo:t1)',",
        "  scope = ['//foo:t1'],",
        "  opts = " + optsStringValue,
        ")");

    List<String> queryResultStrings =
        ImmutableList.copyOf(getQueryResult("//query:gen").split("\n"));
    if (expectVisibilityDep) {
      assertThat(queryResultStrings).contains("//foo:pg");
    } else {
      assertThat(queryResultStrings).doesNotContain("//foo:pg");
    }
  }

  @Test
  public void testNodepDeps_defaultIsFalse() throws Exception {
    runNodepDepsTest(/* optsStringValue= */ "[]", /* expectVisibilityDep= */ false);
  }

  @Test
  public void testNodepDeps_false() throws Exception {
    runNodepDepsTest(
        /* optsStringValue= */ "['--nodep_deps=false']", /* expectVisibilityDep= */ false);
  }

  @Test
  public void testNodepDeps_true() throws Exception {
    runNodepDepsTest(
        /* optsStringValue= */ "['--nodep_deps=true']", /* expectVisibilityDep= */ true);
  }

  @Test
  public void testLoadingPhaseCycle() throws Exception {
    // This test uses a target in a self-cycle to demonstrate that a genquery rule having a cycle in
    // its scope causes it to fail, unless --experimental_skip_ttvs_for_genquery is used.
    write(
        "cycle/BUILD",
        "genquery(",
        "  name = 'gen',",
        "  expression = '//cycle',",
        "  scope = [':cycle'],",
        ")",
        "sh_library(name = 'cycle', deps = [':cycle'])");
    if (ttvFree) {
      assertQueryResult("//cycle:gen", "//cycle:cycle");
    } else {
      assertThrows(expectedExceptionClass(), () -> buildTarget("//cycle:gen"));
      assertContainsEvent(
          events.collector(), "in sh_library rule //cycle:cycle: cycle in dependency graph");
    }
  }

  protected void writeAspectDefinition(String aspectPackage, String extraDep) throws Exception {
    write(aspectPackage + "/BUILD");
    write(
        aspectPackage + "/aspect.bzl",
        "def _aspect_impl(target, ctx):",
        "   return struct()",
        "def _rule_impl(ctx):",
        "   return struct()",
        "MyAspect = aspect(",
        "   implementation=_aspect_impl,",
        "   attr_aspects=['deps'],",
        "   attrs = {'_extra_deps': attr.label(default = Label('" + extraDep + "'))})",
        "aspect_rule = rule(",
        "   implementation=_rule_impl,",
        "   attrs = { 'attr' : ",
        "             attr.label_list(mandatory=True, allow_files=True, aspects = [MyAspect]),",
        "             'param' : attr.string(),",
        "           },",
        ")");
  }

  @Test
  public void testAspectDepChain() throws Exception {
    writeAspectDefinition("aspect1", "//middle");
    writeAspectDefinition("aspect2", "//end");
    write(
        "start/BUILD",
        "load('//aspect1:aspect.bzl', 'aspect_rule')",
        "genquery(",
        "  name = 'gen',",
        "  expression = 'deps(//start)',",
        "  scope = [':start'],",
        ")",
        "aspect_rule(name = 'start', attr = [':startdep'])",
        "sh_library(name = 'startdep')");
    write(
        "middle/BUILD",
        "load('//aspect2:aspect.bzl', 'aspect_rule')",
        "aspect_rule(name = 'middle', attr = [':middledep'])",
        "sh_library(name = 'middledep')");
    write(
        "end/BUILD", "sh_library(name = 'end', deps = [':enddep'])", "sh_library(name = 'enddep')");
    assertQueryResult(
        "//start:gen",
        "//end:end",
        "//end:enddep",
        "//middle:middle",
        "//middle:middledep",
        "//start:start",
        "//start:startdep");
  }

  private void assertQueryResult(String queryTarget, String... expected) throws Exception {
    assertThat(getQueryResult(queryTarget).split("\n"))
        .asList()
        .containsExactlyElementsIn(ImmutableList.copyOf(expected))
        .inOrder();
  }

  private void assertPartialQueryResult(String queryTarget, String... expected) throws Exception {
    assertThat(getQueryResult(queryTarget).split("\n"))
        .asList()
        .containsAtLeastElementsIn(ImmutableList.copyOf(expected))
        .inOrder();
  }

  private String getQueryResult(String queryTarget) throws Exception {
    var unused = buildTarget(queryTarget);
    Artifact output = Iterables.getOnlyElement(getArtifacts(queryTarget));
    assertThat(
            getSkyframeExecutor().getEvaluator().getValues().keySet().stream()
                .anyMatch(key -> key instanceof TransitiveTargetKey))
        .isEqualTo(!ttvFree);
    return readContentAsLatin1String(output);
  }

  private Class<? extends Throwable> expectedExceptionClass() {
    return keepGoing ? BuildFailedException.class : ViewCreationFailedException.class;
  }
}