// Copyright 2015 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.collect.nestedset;

import static com.google.common.truth.Truth.assertThat;
import static org.junit.Assert.assertThrows;

import com.google.common.collect.ImmutableList;
import com.google.devtools.build.lib.collect.nestedset.Depset.ElementType;
import com.google.devtools.build.lib.syntax.Dict;
import com.google.devtools.build.lib.syntax.Sequence;
import com.google.devtools.build.lib.syntax.StarlarkCallable;
import com.google.devtools.build.lib.syntax.StarlarkIterable;
import com.google.devtools.build.lib.syntax.StarlarkList;
import com.google.devtools.build.lib.syntax.StarlarkValue;
import com.google.devtools.build.lib.syntax.Tuple;
import com.google.devtools.build.lib.syntax.util.EvaluationTestCase;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.JUnit4;

/** Tests for Depset. */
@RunWith(JUnit4.class)
public final class DepsetTest {

  private final EvaluationTestCase ev = new EvaluationTestCase();

  @Test
  public void testConstructor() throws Exception {
    ev.exec("s = depset(order='default')");
    assertThat(ev.lookup("s")).isInstanceOf(Depset.class);
  }

  private static final ElementType TUPLE = ElementType.of(Tuple.class);

  @Test
  public void testTuples() throws Exception {
    ev.exec(
        "s_one = depset([('1', '2'), ('3', '4')])",
        "s_two = depset(direct = [('1', '2'), ('3', '4'), ('5', '6')])",
        "s_three = depset(transitive = [s_one, s_two])",
        "s_four = depset(direct = [('1', '3')], transitive = [s_one, s_two])",
        "s_five = depset(direct = [('1', '3', '5')], transitive = [s_one, s_two])",
        "s_six = depset(transitive = [s_one, s_five])",
        "s_seven = depset(direct = [('1', '3')], transitive = [s_one, s_five])",
        "s_eight = depset(direct = [(1, 3)], transitive = [s_one, s_two])"); // note, tuple of int
    assertThat(get("s_one").getElementType()).isEqualTo(TUPLE);
    assertThat(get("s_two").getElementType()).isEqualTo(TUPLE);
    assertThat(get("s_three").getElementType()).isEqualTo(TUPLE);
    assertThat(get("s_eight").getElementType()).isEqualTo(TUPLE);

    assertThat(get("s_four").getSet(Tuple.class).toList())
        .containsExactly(
            Tuple.of("1", "3"), Tuple.of("1", "2"), Tuple.of("3", "4"), Tuple.of("5", "6"));
    assertThat(get("s_five").getSet(Tuple.class).toList())
        .containsExactly(
            Tuple.of("1", "3", "5"), Tuple.of("1", "2"), Tuple.of("3", "4"), Tuple.of("5", "6"));
    assertThat(get("s_eight").getSet(Tuple.class).toList())
        .containsExactly(
            Tuple.of(1, 3), Tuple.of("1", "2"), Tuple.of("3", "4"), Tuple.of("5", "6"));
  }

  @Test
  public void testGetSet() throws Exception {
    ev.exec("s = depset(['a', 'b'])");
    assertThat(get("s").getSet(String.class).toList()).containsExactly("a", "b").inOrder();
    assertThat(get("s").getSet(Object.class).toList()).containsExactly("a", "b").inOrder();
    assertThrows(Depset.TypeException.class, () -> get("s").getSet(Integer.class));

    // getSet argument must be a legal Starlark value class, or Object,
    // but not some superclass that doesn't implement StarlarkValue.
    Depset ints = Depset.legacyOf(Order.STABLE_ORDER, Tuple.of(1, 2, 3));
    assertThat(ints.getSet(Integer.class).toString()).isEqualTo("[1, 2, 3]");
    IllegalArgumentException ex =
        assertThrows(IllegalArgumentException.class, () -> ints.getSet(Number.class));
    assertThat(ex.getMessage()).contains("Number is not a subclass of StarlarkValue");
  }

  @Test
  public void testGetSetDirect() throws Exception {
    ev.exec("s = depset(direct = ['a', 'b'])");
    assertThat(get("s").getSet(String.class).toList()).containsExactly("a", "b").inOrder();
    assertThat(get("s").getSet(Object.class).toList()).containsExactly("a", "b").inOrder();
    assertThrows(Depset.TypeException.class, () -> get("s").getSet(Integer.class));
  }

  @Test
  public void testGetSetItems() throws Exception {
    ev.exec("s = depset(items = ['a', 'b'])");
    assertThat(get("s").getSet(String.class).toList()).containsExactly("a", "b").inOrder();
    assertThat(get("s").getSet(Object.class).toList()).containsExactly("a", "b").inOrder();
    assertThrows(Depset.TypeException.class, () -> get("s").getSet(Integer.class));
  }

  @Test
  public void testToList() throws Exception {
    ev.exec("s = depset(['a', 'b'])");
    assertThat(get("s").toList(String.class)).containsExactly("a", "b").inOrder();
    assertThat(get("s").toList(Object.class)).containsExactly("a", "b").inOrder();
    assertThat(get("s").toList()).containsExactly("a", "b").inOrder();
    assertThrows(Depset.TypeException.class, () -> get("s").toList(Integer.class));
  }

  @Test
  public void testToListDirect() throws Exception {
    ev.exec("s = depset(direct = ['a', 'b'])");
    assertThat(get("s").toList(String.class)).containsExactly("a", "b").inOrder();
    assertThat(get("s").toList(Object.class)).containsExactly("a", "b").inOrder();
    assertThat(get("s").toList()).containsExactly("a", "b").inOrder();
    assertThrows(Depset.TypeException.class, () -> get("s").toList(Integer.class));
  }

  @Test
  public void testToListItems() throws Exception {
    ev.exec("s = depset(items = ['a', 'b'])");
    assertThat(get("s").toList(String.class)).containsExactly("a", "b").inOrder();
    assertThat(get("s").toList(Object.class)).containsExactly("a", "b").inOrder();
    assertThat(get("s").toList()).containsExactly("a", "b").inOrder();
    assertThrows(Depset.TypeException.class, () -> get("s").toList(Integer.class));
  }

  @Test
  public void testOrder() throws Exception {
    ev.exec("s = depset(['a', 'b'], order='postorder')");
    assertThat(get("s").getSet(String.class).getOrder()).isEqualTo(Order.COMPILE_ORDER);
  }

  @Test
  public void testOrderDirect() throws Exception {
    ev.exec("s = depset(direct = ['a', 'b'], order='postorder')");
    assertThat(get("s").getSet(String.class).getOrder()).isEqualTo(Order.COMPILE_ORDER);
  }

  @Test
  public void testOrderItems() throws Exception {
    ev.exec("s = depset(items = ['a', 'b'], order='postorder')");
    assertThat(get("s").getSet(String.class).getOrder()).isEqualTo(Order.COMPILE_ORDER);
  }

  @Test
  public void testBadOrder() throws Exception {
    ev.new Scenario()
        .testIfExactError("Invalid order: non_existing", "depset(['a'], order='non_existing')");
  }

  @Test
  public void testBadOrderDirect() throws Exception {
    ev.new Scenario()
        .testIfExactError(
            "Invalid order: non_existing", "depset(direct = ['a'], order='non_existing')");
  }

  @Test
  public void testBadOrderItems() throws Exception {
    ev.new Scenario()
        .testIfExactError(
            "Invalid order: non_existing", "depset(items = ['a'], order='non_existing')");
  }

  @Test
  public void testEmptyGenericType() throws Exception {
    ev.exec("s = depset()");
    assertThat(get("s").getElementType()).isEqualTo(ElementType.EMPTY);
  }

  @Test
  public void testHomogeneousGenericType() throws Exception {
    ev.exec("s = depset(['a', 'b', 'c'])");
    assertThat(get("s").getElementType()).isEqualTo(ElementType.STRING);
  }

  @Test
  public void testHomogeneousGenericTypeDirect() throws Exception {
    ev.exec("s = depset(['a', 'b', 'c'], transitive = [])");
    assertThat(get("s").getElementType()).isEqualTo(ElementType.STRING);
  }

  @Test
  public void testHomogeneousGenericTypeItems() throws Exception {
    ev.exec("s = depset(items = ['a', 'b', 'c'], transitive = [])");
    assertThat(get("s").getElementType()).isEqualTo(ElementType.STRING);
  }

  @Test
  public void testHomogeneousGenericTypeTransitive() throws Exception {
    ev.exec("s = depset(['a', 'b', 'c'], transitive = [depset(['x'])])");
    assertThat(get("s").getElementType()).isEqualTo(ElementType.STRING);
  }

  @Test
  public void testTransitiveIncompatibleOrder() throws Exception {
    ev.checkEvalError(
        "Order 'postorder' is incompatible with order 'topological'",
        "depset(['a', 'b'], order='postorder',",
        "       transitive = [depset(['c', 'd'], order='topological')])");
  }

  @Test
  public void testBadGenericType() throws Exception {
    ev.new Scenario()
        .testIfExactError(
            "cannot add an item of type 'int' to a depset of 'string'", "depset(['a', 5])");
  }

  @Test
  public void testBadGenericTypeDirect() throws Exception {
    ev.new Scenario()
        .testIfExactError(
            "cannot add an item of type 'int' to a depset of 'string'",
            "depset(direct = ['a', 5])");
  }

  @Test
  public void testBadGenericTypeItems() throws Exception {
    ev.new Scenario()
        .testIfExactError(
            "cannot add an item of type 'int' to a depset of 'string'", "depset(items = ['a', 5])");
  }

  @Test
  public void testBadGenericTypeTransitive() throws Exception {
    ev.new Scenario()
        .testIfExactError(
            "cannot add an item of type 'int' to a depset of 'string'",
            "depset(['a', 'b'], transitive=[depset([1])])");
  }

  @Test
  public void testLegacyAndNewApi() throws Exception {
    ev.new Scenario()
        .testIfExactError(
            "Do not pass both 'direct' and 'items' argument to depset constructor.",
            "depset(['a', 'b'], direct = ['c', 'd'])");
  }

  @Test
  public void testItemsAndTransitive() throws Exception {
    ev.new Scenario()
        .testIfExactError(
            "for items, got depset, want sequence",
            "depset(items = depset(), transitive = [depset()])");
  }

  @Test
  public void testTooManyPositionals() throws Exception {
    ev.new Scenario()
        .testIfErrorContains(
            "depset() accepts no more than 2 positional arguments but got 3",
            "depset([], 'default', [])");
  }


  @Test
  public void testTransitiveOrder() throws Exception {
    assertContainsInOrder("depset([], transitive=[depset(['a', 'b', 'c'])])", "a", "b", "c");
    assertContainsInOrder("depset(['a'], transitive = [depset(['b', 'c'])])", "b", "c", "a");
    assertContainsInOrder("depset(['a', 'b'], transitive = [depset(['c'])])", "c", "a", "b");
    assertContainsInOrder("depset(['a', 'b', 'c'], transitive = [depset([])])", "a", "b", "c");
  }

  @Test
  public void testTransitiveOrderItems() throws Exception {
    assertContainsInOrder("depset(items=[], transitive=[depset(['a', 'b', 'c'])])", "a", "b", "c");
    assertContainsInOrder("depset(items=['a'], transitive = [depset(['b', 'c'])])", "b", "c", "a");
    assertContainsInOrder("depset(items=['a', 'b'], transitive = [depset(['c'])])", "c", "a", "b");
    assertContainsInOrder("depset(items=['a', 'b', 'c'], transitive = [depset([])])",
        "a", "b", "c");
  }

  @Test
  public void testTransitiveOrderDirect() throws Exception {
    assertContainsInOrder("depset(direct=[], transitive=[depset(['a', 'b', 'c'])])", "a", "b", "c");
    assertContainsInOrder("depset(direct=['a'], transitive = [depset(['b', 'c'])])", "b", "c", "a");
    assertContainsInOrder("depset(direct=['a', 'b'], transitive = [depset(['c'])])", "c", "a", "b");
    assertContainsInOrder("depset(direct=['a', 'b', 'c'], transitive = [depset([])])",
        "a", "b", "c");
  }

  @Test
  public void testIncompatibleUnion() throws Exception {
    ev.new Scenario()
        .testIfErrorContains("unsupported binary operation: depset + list", "depset([]) + ['a']");

    ev.new Scenario()
        .testIfErrorContains("unsupported binary operation: depset | list", "depset([]) | ['a']");
  }

  private void assertContainsInOrder(String statement, Object... expectedElements)
      throws Exception {
    assertThat(((Depset) ev.eval(statement)).toList()).containsExactly(expectedElements).inOrder();
  }

  @Test
  public void testToString() throws Exception {
    ev.exec("s = depset([3, 4, 5], transitive = [depset([2, 4, 6])])", "x = str(s)");
    assertThat(ev.lookup("x")).isEqualTo("depset([2, 4, 6, 3, 5])");
  }

  @Test
  public void testToStringWithOrder() throws Exception {
    ev.exec(
        "s = depset([3, 4, 5], transitive = [depset([2, 4, 6])], ",
        "           order = 'topological')",
        "x = str(s)");
    assertThat(ev.lookup("x")).isEqualTo("depset([3, 5, 6, 4, 2], order = \"topological\")");
  }

  private Depset get(String varname) throws Exception {
    return (Depset) ev.lookup(varname);
  }

  @Test
  public void testToListForStarlark() throws Exception {
    ev.exec("s = depset([3, 4, 5], transitive = [depset([2, 4, 6])])", "x = s.to_list()");
    Object value = ev.lookup("x");
    assertThat(value).isInstanceOf(StarlarkList.class);
    assertThat((Iterable<?>) value).containsExactly(2, 4, 6, 3, 5).inOrder();
  }

  @Test
  public void testOrderCompatibility() throws Exception {
    // Two sets are compatible if
    //  (a) both have the same order or
    //  (b) at least one order is "default"

    for (Order first : Order.values()) {
      Depset s1 = Depset.legacyOf(first, Tuple.of("1", "11"));

      for (Order second : Order.values()) {
        Depset s2 = Depset.legacyOf(second, Tuple.of("2", "22"));

        boolean compatible = true;

        try {
          // merge
          Depset.fromDirectAndTransitive(
              first,
              /*direct=*/ ImmutableList.of(),
              /*transitive=*/ ImmutableList.of(s1, s2),
              /*strict=*/ true);
        } catch (Exception ex) {
          compatible = false;
        }

        assertThat(compatible).isEqualTo(areOrdersCompatible(first, second));
      }
    }
  }

  private static boolean areOrdersCompatible(Order first, Order second) {
    return first == Order.STABLE_ORDER || second == Order.STABLE_ORDER || first == second;
  }

  @Test
  public void testMutableDepsetElementsLegacyBehavior() throws Exception {
    // See b/144992997 and github.com/bazelbuild/bazel/issues/10313.
    ev.setSemantics("--incompatible_always_check_depset_elements=false");

    // Test legacy depset(...) and new depset(direct=...) constructors.

    // mutable list should be an error
    ev.checkEvalError("depset elements must not be mutable values", "depset([[1,2,3]])");
    ev.checkEvalError("depsets cannot contain items of type 'list'", "depset(direct=[[1,2,3]])");

    // struct containing mutable list should be an error
    ev.checkEvalError("depset elements must not be mutable values", "depset([struct(a=[])])");
    ev.eval("depset(direct=[struct(a=[])])"); // no error (!)

    // tuple of frozen list currently gives no error (this may change)
    ev.update("x", StarlarkList.empty());
    ev.eval("depset([(x,)])");
    ev.eval("depset(direct=[(x,)])");

    // any list (even frozen) is an error, even with legacy constructor
    ev.checkEvalError("depsets cannot contain items of type 'list'", "depset([x])");
    ev.checkEvalError("depsets cannot contain items of type 'list'", "depset(direct=[x])");

    // toplevel dict is an error, even with legacy constructor
    ev.checkEvalError("depset elements must not be mutable values", "depset([{}])");
    ev.checkEvalError("depsets cannot contain items of type 'dict'", "depset(direct=[{}])");

    // struct containing dict should be an error
    ev.checkEvalError("depset elements must not be mutable values", "depset([struct(a={})])");
    ev.eval("depset(direct=[struct(a={})])"); // no error (!)
  }

  @Test
  public void testMutableDepsetElementsDesiredBehavior() throws Exception {
    // See b/144992997 and github.com/bazelbuild/bazel/issues/10313.
    ev.setSemantics("--incompatible_always_check_depset_elements=true");

    // Test legacy depset(...) and new depset(direct=...) constructors.

    // mutable list should be an error
    ev.checkEvalError("depset elements must not be mutable values", "depset([[1,2,3]])");
    ev.checkEvalError("depset elements must not be mutable values", "depset(direct=[[1,2,3]])");

    // struct containing mutable list should be an error
    ev.checkEvalError("depset elements must not be mutable values", "depset([struct(a=[])])");
    ev.checkEvalError(
        "depset elements must not be mutable values", "depset(direct=[struct(a=[])])");

    // tuple of frozen list currently gives no error (this may change)
    ev.update("x", StarlarkList.empty());
    ev.eval("depset([(x,)])");
    ev.eval("depset(direct=[(x,)])");

    // any list (even frozen) is an error, even with legacy constructor
    ev.checkEvalError("depsets cannot contain items of type 'list'", "depset([x,])");
    ev.checkEvalError("depsets cannot contain items of type 'list'", "depset(direct=[x,])");

    // toplevel dict is an error, even with legacy constructor
    ev.checkEvalError("depset elements must not be mutable values", "depset([{}])");
    ev.checkEvalError("depset elements must not be mutable values", "depset(direct=[{}])");

    // struct containing dict should be an error
    ev.checkEvalError("depset elements must not be mutable values", "depset([struct(a={})])");
    ev.checkEvalError(
        "depset elements must not be mutable values", "depset(direct=[struct(a={})])");
  }

  @Test
  public void testDepthExceedsLimitDuringIteration() throws Exception {
    NestedSet.setApplicationDepthLimit(2000);
    ev.new Scenario()
        .setUp(
            "def create_depset(depth):",
            "  x = depset([0])",
            "  for i in range(1, depth):",
            "    x = depset([i], transitive = [x])",
            "  for element in x.to_list():",
            "    str(x)",
            "  return None")
        .testEval("create_depset(1000)", "None")
        .testIfErrorContains("depset exceeded maximum depth", "create_depset(3000)");
  }

  @Test
  public void testElementTypeOf() {
    // legal values
    assertThat(ElementType.of(String.class).toString()).isEqualTo("string");
    assertThat(ElementType.of(Integer.class).toString()).isEqualTo("int");
    assertThat(ElementType.of(Boolean.class).toString()).isEqualTo("bool");

    // concrete non-values
    assertThrows(IllegalArgumentException.class, () -> ElementType.of(Float.class));

    // concrete classes that implement StarlarkValue
    assertThat(ElementType.of(StarlarkList.class).toString()).isEqualTo("list");
    assertThat(ElementType.of(Tuple.class).toString()).isEqualTo("tuple");
    assertThat(ElementType.of(Dict.class).toString()).isEqualTo("dict");
    class V implements StarlarkValue {} // no StarlarkModule annotation
    assertThat(ElementType.of(V.class).toString()).isEqualTo("V");

    // abstract classes that implement StarlarkValue
    assertThat(ElementType.of(Sequence.class).toString()).isEqualTo("sequence");
    assertThat(ElementType.of(StarlarkCallable.class).toString()).isEqualTo("function");
    assertThat(ElementType.of(StarlarkIterable.class).toString()).isEqualTo("StarlarkIterable");

    // superclasses of legal values that aren't values themselves
    assertThrows(IllegalArgumentException.class, () -> ElementType.of(Number.class));
    assertThrows(IllegalArgumentException.class, () -> ElementType.of(CharSequence.class));
    assertThrows(IllegalArgumentException.class, () -> ElementType.of(Object.class));
  }

  @Test
  public void testSetComparison() throws Exception {
    ev.new Scenario()
        .testIfExactError("Cannot compare depset with depset", "depset([1, 2]) < depset([3, 4])");
  }

  @Test
  public void testDepsetItemsKeywordAndPositional() throws Exception {
    ev.new Scenario("--incompatible_disable_depset_items=false")
        .testIfErrorContains(
            "parameter 'items' cannot be specified both positionally and by keyword",
            "depset([0, 1], 'default', items=[0,1])");
  }

  @Test
  public void testDepsetDirectInvalidType() throws Exception {
    ev.new Scenario()
        .testIfErrorContains("for direct, got string, want sequence", "depset(direct='hello')");
  }

  @Test
  public void testDisableDepsetItems() throws Exception {
    ev.new Scenario("--incompatible_disable_depset_items")
        .setUp("x = depset([0])", "y = depset(direct = [1])")
        .testEval("depset([2, 3], transitive = [x, y]).to_list()", "[0, 1, 2, 3]")
        .testIfErrorContains(
            "parameter 'direct' cannot be specified both positionally and by keyword",
            "depset([0, 1], 'default', direct=[0,1])")
        .testIfErrorContains(
            "in call to depset(), parameter 'items' is deprecated and will be removed soon. "
                + "It may be temporarily re-enabled by setting "
                + "--incompatible_disable_depset_inputs=false",
            "depset(items=[0,1])");
  }

  @Test
  public void testDepsetDepthLimit() throws Exception {
    NestedSet.setApplicationDepthLimit(2000);
    ev.new Scenario()
        .setUp(
            "def create_depset(depth):",
            "  x = depset([0])",
            "  for i in range(1, depth):",
            "    x = depset([i], transitive = [x])",
            "  return x",
            "too_deep_depset = create_depset(3000)",
            "fine_depset = create_depset(900)")
        .testEval("fine_depset.to_list()[0]", "0")
        .testEval("str(fine_depset)[0:6]", "'depset'")
        .testIfErrorContains("depset exceeded maximum depth", "print(too_deep_depset)")
        .testIfErrorContains("depset exceeded maximum depth", "str(too_deep_depset)")
        .testIfErrorContains("depset exceeded maximum depth", "too_deep_depset.to_list()");
  }

  @Test
  public void testDepsetDebugDepth() throws Exception {
    NestedSet.setApplicationDepthLimit(2000);
    ev.new Scenario("--debug_depset_depth=true")
        .setUp(
            "def create_depset(depth):",
            "  x = depset([0])",
            "  for i in range(1, depth):",
            "    x = depset([i], transitive = [x])",
            "  return x")
        .testEval("str(create_depset(900))[0:6]", "'depset'")
        .testIfErrorContains("depset exceeded maximum depth", "create_depset(3000)");
  }
}