// 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.query2.engine;

import com.google.common.annotations.VisibleForTesting;
import com.google.common.collect.ImmutableList;
import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
import com.google.devtools.build.lib.query2.engine.QueryEnvironment.Argument;
import com.google.devtools.build.lib.query2.engine.QueryEnvironment.ArgumentType;
import com.google.devtools.build.lib.query2.engine.QueryEnvironment.MutableMap;
import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryFunction;
import com.google.devtools.build.lib.query2.engine.QueryEnvironment.QueryTaskFuture;
import com.google.devtools.build.lib.query2.engine.QueryEnvironment.Setting;
import com.google.devtools.build.lib.query2.engine.QueryEnvironment.ThreadSafeMutableSet;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;

/**
 * A tests(x) filter expression, which returns all the tests in set x, expanding test_suite rules
 * into their constituents.
 *
 * <p>Unfortunately this class reproduces a substantial amount of logic from {@code
 * TestSuiteConfiguredTarget}, albeit in a somewhat simplified form. This is basically inevitable
 * since the expansion of test_suites cannot be done during the loading phase, because it involves
 * inter-package references. We make no attempt to validate the input, or report errors or warnings
 * other than missing target.
 *
 * <pre>expr ::= TESTS '(' expr ')'</pre>
 */
public class TestsFunction implements QueryFunction {
  @VisibleForTesting
  public TestsFunction() {}

  @Override
  public String getName() {
    return "tests";
  }

  @Override
  public int getMandatoryArguments() {
    return 1;
  }

  @Override
  public List<ArgumentType> getArgumentTypes() {
    return ImmutableList.of(ArgumentType.EXPRESSION);
  }

  @Override
  public <T> QueryTaskFuture<Void> eval(
      final QueryEnvironment<T> env,
      QueryExpressionContext<T> context,
      QueryExpression expression,
      List<Argument> args,
      final Callback<T> callback) {
    final Closure<T> closure = new Closure<>(expression, env);
    final Uniquifier<T> uniquifier = env.createUniquifier();

    return env.eval(
        args.get(0).getExpression(),
        context,
        new Callback<T>() {
          @Override
          public void process(Iterable<T> partialResult)
              throws QueryException, InterruptedException {
            for (T target : partialResult) {
              if (env.getAccessor().isTestRule(target)) {
                if (uniquifier.unique(target)) {
                  callback.process(ImmutableList.of(target));
                }
              } else if (env.getAccessor().isTestSuite(target)) {
                for (T test : closure.getTestsInSuite(target)) {
                  T testTarget = env.getOrCreate(test);
                  if (uniquifier.unique(testTarget)) {
                    callback.process(ImmutableList.of(testTarget));
                  }
                }
              }
            }
          }
        });
  }

  // TODO(ulfjack): This must match the code in TestTargetUtils. However, we don't currently want
  // to depend on the packages library. Extract to a neutral place?
  /**
   * Decides whether to include a test in a test_suite or not.
   * @param testTags Collection of all tags exhibited by a given test.
   * @param positiveTags Tags declared by the suite. A test must match ALL of these.
   * @param negativeTags Tags declared by the suite. A test must match NONE of these.
   * @return false is the test is to be removed.
   */
  private static boolean includeTest(Collection<String> testTags,
      Collection<String> positiveTags, Collection<String> negativeTags) {
    // Add this test if it matches ALL of the positive tags and NONE of the
    // negative tags in the tags attribute.
    for (String tag : negativeTags) {
      if (testTags.contains(tag)) {
        return false;
      }
    }
    for (String tag : positiveTags) {
      if (!testTags.contains(tag)) {
        return false;
      }
    }
    return true;
  }

  /**
   * Separates a list of text "tags" into a Pair of Collections, where
   * the first element are the required or positive tags and the second element
   * are the excluded or negative tags.
   * This should work on tag list provided from the command line
   * --test_tags_filters flag or on tag filters explicitly declared in the
   * suite.
   *
   * Keep this function in sync with the version in
   *  java.com.google.devtools.build.lib.view.packages.TestTargetUtils.sortTagsBySense
   *
   * @param tagList A collection of text tags to separate.
   */
  private static void sortTagsBySense(
      Collection<String> tagList, Set<String> requiredTags, Set<String> excludedTags) {
    for (String tag : tagList) {
      if (tag.startsWith("-")) {
        excludedTags.add(tag.substring(1));
      } else if (tag.startsWith("+")) {
        requiredTags.add(tag.substring(1));
      } else if (tag.equals("manual")) {
        // Ignore manual attribute because it is an exception: it is not a filter
        // but a property of test_suite
        continue;
      } else {
        requiredTags.add(tag);
      }
    }
  }

  /** A closure over the temporary state needed to compute the expression. */
  @ThreadSafe
  private static final class Closure<T> {
    private final QueryExpression expression;
    /** A dynamically-populated mapping from test_suite rules to their tests. */
    private final MutableMap<T, ThreadSafeMutableSet<T>> testsInSuite;

    /** The environment in which this query is being evaluated. */
    private final QueryEnvironment<T> env;

    private final boolean strict;

    private Closure(QueryExpression expression, QueryEnvironment<T> env) {
      this.expression = expression;
      this.env = env;
      this.strict = env.isSettingEnabled(Setting.TESTS_EXPRESSION_STRICT);
      this.testsInSuite = env.createMutableMap();
    }

    /**
     * Computes and returns the set of test rules in a particular suite. Uses dynamic
     * programming---a memoized version of {@link #computeTestsInSuite}.
     *
     * @precondition env.getAccessor().isTestSuite(testSuite)
     */
    private synchronized ThreadSafeMutableSet<T> getTestsInSuite(T testSuite)
        throws QueryException, InterruptedException {
      ThreadSafeMutableSet<T> tests = testsInSuite.get(testSuite);
      if (tests == null) {
        tests = env.createThreadSafeMutableSet();
        testsInSuite.put(testSuite, tests); // break cycles by inserting empty set early.
        computeTestsInSuite(testSuite, tests);
      }
      return tests;
    }

    /**
     * Populates 'result' with all the tests associated with the specified 'testSuite'. Throws an
     * exception if any target is missing.
     *
     * <p>CAUTION! Keep this logic consistent with {@code TestsSuiteConfiguredTarget}!
     *
     * @precondition env.getAccessor().isTestSuite(testSuite)
     */
    private void computeTestsInSuite(T testSuite, ThreadSafeMutableSet<T> result)
        throws QueryException, InterruptedException {
      List<T> testsAndSuites = new ArrayList<>();
      // Note that testsAndSuites can contain input file targets; the test_suite rule does not
      // restrict the set of targets that can appear in tests or suites.
      testsAndSuites.addAll(getPrerequisites(testSuite, "tests"));

      // 1. Add all tests
      for (T test : testsAndSuites) {
        if (env.getAccessor().isTestRule(test)) {
          result.add(test);
        } else if (strict && !env.getAccessor().isTestSuite(test)) {
          // If strict mode is enabled, then give an error for any non-test, non-test-suite targets.
          env.reportBuildFileError(expression, "The label '"
              + env.getAccessor().getLabel(test) + "' in the test_suite '"
              + env.getAccessor().getLabel(testSuite) + "' does not refer to a test or test_suite "
              + "rule!");
        }
      }

      // 2. Add implicit dependencies on tests in same package, if any.
      for (T target : getPrerequisites(testSuite, "$implicit_tests")) {
        // The Package construction of $implicit_tests ensures that this check never fails, but we
        // add it here anyway for compatibility with future code.
        if (env.getAccessor().isTestRule(target)) {
          result.add(target);
        }
      }

      // 3. Filter based on tags, size, env.
      filterTests(testSuite, result);

      // 4. Expand all suites recursively.
      for (T suite : testsAndSuites) {
        if (env.getAccessor().isTestSuite(suite)) {
          result.addAll(getTestsInSuite(suite));
        }
      }
    }

    /**
     * Returns the set of rules named by the attribute 'attrName' of test_suite rule 'testSuite'.
     * The attribute must be a list of labels. If a target cannot be resolved, then an error is
     * reported to the environment (which may throw an exception if {@code keep_going} is disabled).
     *
     * @precondition env.getAccessor().isTestSuite(testSuite)
     */
    private List<T> getPrerequisites(T testSuite, String attrName)
        throws QueryException, InterruptedException {
      return env.getAccessor().getLabelListAttr(expression, testSuite, attrName,
          "couldn't expand '" + attrName
          + "' attribute of test_suite " + env.getAccessor().getLabel(testSuite) + ": ");
    }

    /**
     * Filters 'tests' (by mutation) according to the 'tags' attribute, specifically those that
     * match ALL of the tags in tagsAttribute.
     *
     * @precondition {@code env.getAccessor().isTestSuite(testSuite)}
     * @precondition {@code env.getAccessor().isTestRule(test)} for all test in tests
     */
    private void filterTests(T testSuite, ThreadSafeMutableSet<T> tests) {
      List<String> tagsAttribute = env.getAccessor().getStringListAttr(testSuite, "tags");
      // Split the tags list into positive and negative tags
      Set<String> requiredTags = new HashSet<>();
      Set<String> excludedTags = new HashSet<>();
      sortTagsBySense(tagsAttribute, requiredTags, excludedTags);

      Iterator<T> it = tests.iterator();
      while (it.hasNext()) {
        T test = it.next();
        // TODO(ulfjack): This does not match the code used for TestSuite.
        List<String> testTags = new ArrayList<>(env.getAccessor().getStringListAttr(test, "tags"));
        testTags.add(env.getAccessor().getStringAttr(test, "size"));
        if (!includeTest(testTags, requiredTags, excludedTags)) {
          it.remove();
        }
      }
    }
  }
}