New depset() API

`depset` constructor has new arguments, `direct` and `transitive`.
`items` argument is deprecated and after its removal `direct` will
become a sole positional argument.
If `transitive` and `items` are specified, `items` must be a list of
direct elements.
In the absence of `transitive` the value of `items` can also be a
depset, but that behavior is deprecated.

RELNOTES: New depset API
PiperOrigin-RevId: 170346194

3 files changed, 352 insertions, 44 deletions

diff --git a/src/main/java/com/google/devtools/build/lib/syntax/BazelLibrary.java b/src/main/java/com/google/devtools/build/lib/syntax/BazelLibrary.java
index 8c392c9389..5c493ffde6 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/BazelLibrary.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/BazelLibrary.java
@@ -57,23 +57,34 @@ public class BazelLibrary {
     name = "depset",
     returnType = SkylarkNestedSet.class,
     doc =
-        "Creates a <a href=\"depset.html\">depset</a>. In the case that <code>items</code> is an "
-            + "iterable, its contents become the direct elements of the depset, with their left-to-"
-            + "right order preserved, and the depset has no transitive elements. In the case that "
-            + "<code>items</code> is a depset, it is made the sole transitive element of the new "
-            + "depset, and no direct elements are added. In the second case the given depset's "
-            + "order must match the <code>order</code> param or else one of the two must be <code>"
-            + "\"default\"</code>. See the <a href=\"../depsets.md\">Depsets overview</a> for more "
-            + "information.",
+        "Creates a <a href=\"depset.html\">depset</a>. The <code>direct</code> parameter is a list "
+            + "of direct elements of the depset, and <code>transitive</code> parameter is "
+            + "a list of depsets whose elements become indirect elements of the created depset. "
+            + "The order in which elements are returned when the depset is converted to a list "
+            + "is specified by the <code>order</code> parameter. "
+            + "See the <a href=\"../depsets.md\">Depsets overview</a> for more information. "
+            + "<p> All elements (direct and indirect) of a depset must be of the same type. "
+            + "<p> The order of the created depset should be <i>compatible</i> with the order of "
+            + "its <code>transitive</code> depsets. <code>\"default\"</code> order is compatible "
+            + "with any other order, all other orders are only compatible with themselves."
+            + "<p> Note on backward/forward compatibility. This function currently accepts a "
+            + "positional <code>items</code> parameter. It is deprecated and will be removed "
+            + "in the future, and after its removal <code>direct</code> will become a sole "
+            + "positional parameter of the <code>depset</code> function. Thus, both of the "
+            + "following calls are equivalent and future-proof:<br>"
+            + "<pre class=language-python>"
+            + "depset(['a', 'b'], transitive = [...])\n"
+            + "depset(direct = ['a', 'b'], transitive = [...])\n"
+            + "</pre>",
     parameters = {
       @Param(
         name = "items",
         type = Object.class,
         defaultValue = "[]",
-        doc =
-            "An iterable whose items become the direct elements of the new depset, in left-to-"
-                + "right order; or alternatively, a depset that becomes the transitive element of "
-                + "the new depset."
+        doc = "Deprecated: Either an iterable whose items become the direct elements of "
+            + "the new depset, in left-to-right order, or else a depset that becomes "
+            + "a transitive element of the new depset. In the latter case, <code>transitive</code> "
+            + "cannot be specified."
       ),
       @Param(
         name = "order",
@@ -82,25 +93,89 @@ public class BazelLibrary {
         doc =
             "The traversal strategy for the new depset. See <a href=\"depset.html\">here</a> for "
                 + "the possible values."
+      ),
+      @Param(
+          name = "direct",
+          type = SkylarkList.class,
+          defaultValue = "None",
+          positional = false,
+          named = true,
+          noneable = true,
+          doc =  "A list of <i>direct</i> elements of a depset."
+      ),
+      @Param(
+        name = "transitive",
+        named = true,
+        positional = false,
+        type = SkylarkList.class,
+        generic1 = SkylarkNestedSet.class,
+        noneable = true,
+        doc = "A list of depsets whose elements will become indirect elements of the depset.",
+        defaultValue = "None"
       )
     },
-      useLocation = true,
-      useEnvironment = true
+    useLocation = true,
+    useEnvironment = true
   )
   private static final BuiltinFunction depset =
       new BuiltinFunction("depset") {
-        public SkylarkNestedSet invoke(Object items, String order, Location loc, Environment env)
+        public SkylarkNestedSet invoke(
+            Object items,
+            String orderString,
+            Object direct,
+            Object transitive,
+            Location loc,
+            Environment env)
             throws EvalException {
+          Order order;
           try {
-            return new SkylarkNestedSet(
-                Order.parse(order, env.getSemantics().incompatibleDisallowSetConstructor),
-                items, loc);
+            order = Order.parse(orderString, env.getSemantics().incompatibleDisallowSetConstructor);
           } catch (IllegalArgumentException ex) {
             throw new EvalException(loc, ex);
           }
+
+          if (transitive == Runtime.NONE && direct == Runtime.NONE) {
+            // Legacy behavior.
+            return new SkylarkNestedSet(order, items, loc);
+          }
+
+          if (direct != Runtime.NONE && !isEmptySkylarkList(items)) {
+            throw new EvalException(
+                loc, "Do not pass both 'direct' and 'items' argument to depset constructor.");
+          }
+
+          // Non-legacy behavior: either 'transitive' or 'direct' were specified.
+          Iterable<Object> directElements;
+          if (direct != Runtime.NONE) {
+            directElements = ((SkylarkList<?>) direct).getContents(Object.class, "direct");
+          } else {
+            SkylarkType.checkType(items, SkylarkList.class, "items");
+            directElements = ((SkylarkList<?>) items).getContents(Object.class, "items");
+          }
+
+          Iterable<SkylarkNestedSet> transitiveList;
+          if (transitive != Runtime.NONE) {
+            SkylarkType.checkType(transitive, SkylarkList.class, "transitive");
+            transitiveList = ((SkylarkList<?>) transitive).getContents(
+                SkylarkNestedSet.class, "transitive");
+          } else {
+            transitiveList = ImmutableList.of();
+          }
+          SkylarkNestedSet.Builder builder = SkylarkNestedSet.builder(order, loc);
+          for (Object directElement : directElements) {
+            builder.addDirect(directElement);
+          }
+          for (SkylarkNestedSet transitiveSet : transitiveList) {
+            builder.addTransitive(transitiveSet);
+          }
+          return builder.build();
         }
       };
 
+  private static boolean isEmptySkylarkList(Object o) {
+    return o instanceof SkylarkList && ((SkylarkList) o).isEmpty();
+  }
+
   @SkylarkSignature(
     name = "set",
     returnType = SkylarkNestedSet.class,
diff --git a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkNestedSet.java b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkNestedSet.java
index 2fe608824b..2915a8db83 100644
--- a/src/main/java/com/google/devtools/build/lib/syntax/SkylarkNestedSet.java
+++ b/src/main/java/com/google/devtools/build/lib/syntax/SkylarkNestedSet.java
@@ -336,4 +336,67 @@ public final class SkylarkNestedSet implements SkylarkValue, SkylarkQueryable {
   public final boolean containsKey(Object key, Location loc) throws EvalException {
     return (set.toList().contains(key));
   }
+
+  /**
+   * Create a {@link Builder} with specified order.
+   *
+   * <p>The {@code Builder} will use {@code location} to report errors.
+   */
+  public static Builder builder(Order order, Location location) {
+    return new Builder(order, location);
+  }
+
+  /**
+   * Builder for {@link SkylarkNestedSet}.
+   *
+   * <p>Use this to construct typesafe Skylark nested sets (depsets).
+   * Encapsulates content type checking logic.
+   */
+  public static final class Builder {
+
+    private final Order order;
+    private final NestedSetBuilder<Object> builder;
+    /** Location for error messages */
+    private final Location location;
+    private SkylarkType contentType = SkylarkType.TOP;
+
+    private Builder(Order order, Location location) {
+      this.order = order;
+      this.location = location;
+      this.builder = new NestedSetBuilder<>(order);
+    }
+
+    /**
+     * Add a direct element, checking its type to be compatible to already added
+     * elements and transitive sets.
+     */
+    public Builder addDirect(Object direct) throws EvalException {
+      contentType = getTypeAfterInsert(contentType, SkylarkType.of(direct.getClass()), location);
+      builder.add(direct);
+      return this;
+    }
+
+    /**
+     * Add a transitive set, checking its content type to be compatible to already added
+     * elements and transitive sets.
+     */
+    public Builder addTransitive(SkylarkNestedSet transitive) throws EvalException {
+      if (transitive.isEmpty()) {
+        return this;
+      }
+
+      contentType = getTypeAfterInsert(contentType, transitive.getContentType(), this.location);
+      if (!order.isCompatible(transitive.getOrder())) {
+        throw new EvalException(location,
+            String.format("Order '%s' is incompatible with order '%s'",
+                          order.getSkylarkName(), transitive.getOrder().getSkylarkName()));
+      }
+      builder.addTransitive(transitive.getSet(Object.class));
+      return this;
+    }
+
+    public SkylarkNestedSet build() {
+      return new SkylarkNestedSet(contentType, builder.build());
+    }
+  }
 }
diff --git a/src/test/java/com/google/devtools/build/lib/syntax/SkylarkNestedSetTest.java b/src/test/java/com/google/devtools/build/lib/syntax/SkylarkNestedSetTest.java
index 5047051df6..d61cb8ab16 100644
--- a/src/test/java/com/google/devtools/build/lib/syntax/SkylarkNestedSetTest.java
+++ b/src/test/java/com/google/devtools/build/lib/syntax/SkylarkNestedSetTest.java
@@ -14,7 +14,8 @@
 package com.google.devtools.build.lib.syntax;
 
 import static com.google.common.truth.Truth.assertThat;
-import static org.junit.Assert.fail;
+import static com.google.devtools.build.lib.testutil.MoreAsserts.assertThrows;
+import static com.google.devtools.build.lib.testutil.MoreAsserts.expectThrows;
 
 import com.google.common.collect.ImmutableList;
 import com.google.devtools.build.lib.collect.nestedset.Order;
@@ -47,12 +48,11 @@ public class SkylarkNestedSetTest extends EvaluationTestCase {
   @Test
   public void testLegacyConstructorDeprecation() throws Exception {
     env = newEnvironmentWithSkylarkOptions("--incompatible_disallow_set_constructor=true");
-    try {
-      eval("s = set([1, 2, 3], order='postorder')");
-      fail("`set` should have failed");
-    } catch (EvalException e) {
-      assertThat(e).hasMessageThat().contains("The `set` constructor for depsets is deprecated");
-    }
+    EvalException e = expectThrows(
+        EvalException.class,
+        () -> eval("s = set([1, 2, 3], order='postorder')")
+    );
+    assertThat(e).hasMessageThat().contains("The `set` constructor for depsets is deprecated");
   }
 
   @Test
@@ -66,24 +66,69 @@ public class SkylarkNestedSetTest extends EvaluationTestCase {
     eval("s = depset(['a', 'b'])");
     assertThat(get("s").getSet(String.class)).containsExactly("a", "b").inOrder();
     assertThat(get("s").getSet(Object.class)).containsExactly("a", "b").inOrder();
-    try {
-      get("s").getSet(Integer.class);
-      fail("getSet() with wrong type should have raised IllegalArgumentException");
-    } catch (IllegalArgumentException expected) {
-    }
+    assertThrows(
+        IllegalArgumentException.class,
+        () -> get("s").getSet(Integer.class)
+    );
+  }
+
+  @Test
+  public void testGetSetDirect() throws Exception {
+    eval("s = depset(direct = ['a', 'b'])");
+    assertThat(get("s").getSet(String.class)).containsExactly("a", "b").inOrder();
+    assertThat(get("s").getSet(Object.class)).containsExactly("a", "b").inOrder();
+    assertThrows(
+        IllegalArgumentException.class,
+        () -> get("s").getSet(Integer.class)
+    );
   }
 
   @Test
+  public void testGetSetItems() throws Exception {
+    eval("s = depset(items = ['a', 'b'])");
+    assertThat(get("s").getSet(String.class)).containsExactly("a", "b").inOrder();
+    assertThat(get("s").getSet(Object.class)).containsExactly("a", "b").inOrder();
+    assertThrows(
+        IllegalArgumentException.class,
+        () -> get("s").getSet(Integer.class)
+    );
+  }
+
+
+  @Test
   public void testToCollection() throws Exception {
     eval("s = depset(['a', 'b'])");
     assertThat(get("s").toCollection(String.class)).containsExactly("a", "b").inOrder();
     assertThat(get("s").toCollection(Object.class)).containsExactly("a", "b").inOrder();
     assertThat(get("s").toCollection()).containsExactly("a", "b").inOrder();
-    try {
-      get("s").toCollection(Integer.class);
-      fail("toCollection() with wrong type should have raised IllegalArgumentException");
-    } catch (IllegalArgumentException expected) {
-    }
+    assertThrows(
+        IllegalArgumentException.class,
+        () -> get("s").toCollection(Integer.class)
+    );
+  }
+
+  @Test
+  public void testToCollectionDirect() throws Exception {
+    eval("s = depset(direct = ['a', 'b'])");
+    assertThat(get("s").toCollection(String.class)).containsExactly("a", "b").inOrder();
+    assertThat(get("s").toCollection(Object.class)).containsExactly("a", "b").inOrder();
+    assertThat(get("s").toCollection()).containsExactly("a", "b").inOrder();
+    assertThrows(
+        IllegalArgumentException.class,
+        () -> get("s").toCollection(Integer.class)
+    );
+  }
+
+  @Test
+  public void testToCollectionItems() throws Exception {
+    eval("s = depset(items = ['a', 'b'])");
+    assertThat(get("s").toCollection(String.class)).containsExactly("a", "b").inOrder();
+    assertThat(get("s").toCollection(Object.class)).containsExactly("a", "b").inOrder();
+    assertThat(get("s").toCollection()).containsExactly("a", "b").inOrder();
+    assertThrows(
+        IllegalArgumentException.class,
+        () -> get("s").toCollection(Integer.class)
+    );
   }
 
   @Test
@@ -93,19 +138,30 @@ public class SkylarkNestedSetTest extends EvaluationTestCase {
   }
 
   @Test
+  public void testOrderDirect() throws Exception {
+    eval("s = depset(direct = ['a', 'b'], order='postorder')");
+    assertThat(get("s").getSet(String.class).getOrder()).isEqualTo(Order.COMPILE_ORDER);
+  }
+
+  @Test
+  public void testOrderItems() throws Exception {
+    eval("s = depset(items = ['a', 'b'], order='postorder')");
+    assertThat(get("s").getSet(String.class).getOrder()).isEqualTo(Order.COMPILE_ORDER);
+  }
+
+  @Test
   public void testDeprecatedOrder() throws Exception {
     env = newEnvironmentWithSkylarkOptions("--incompatible_disallow_set_constructor=false");
     eval("s = depset(['a', 'b'], order='compile')");
     assertThat(get("s").getSet(String.class).getOrder()).isEqualTo(Order.COMPILE_ORDER);
 
     env = newEnvironmentWithSkylarkOptions("--incompatible_disallow_set_constructor=true");
-    try {
-      eval("s = depset(['a', 'b'], order='compile')");
-      fail("Should have not accepted a deprecated order name");
-    } catch (Exception e) {
-      assertThat(e).hasMessageThat().contains(
+    Exception e = expectThrows(
+        Exception.class,
+        () -> eval("s = depset(['a', 'b'], order='compile')")
+    );
+    assertThat(e).hasMessageThat().contains(
           "Order name 'compile' is deprecated, use 'postorder' instead");
-    }
   }
 
   @Test
@@ -116,6 +172,20 @@ public class SkylarkNestedSetTest extends EvaluationTestCase {
   }
 
   @Test
+  public void testBadOrderDirect() throws Exception {
+    new BothModesTest().testIfExactError(
+        "Invalid order: non_existing",
+        "depset(direct = ['a'], order='non_existing')");
+  }
+
+  @Test
+  public void testBadOrderItems() throws Exception {
+    new BothModesTest().testIfExactError(
+        "Invalid order: non_existing",
+        "depset(items = ['a'], order='non_existing')");
+  }
+
+  @Test
   public void testEmptyGenericType() throws Exception {
     eval("s = depset()");
     assertThat(get("s").getContentType()).isEqualTo(SkylarkType.TOP);
@@ -128,6 +198,32 @@ public class SkylarkNestedSetTest extends EvaluationTestCase {
   }
 
   @Test
+  public void testHomogeneousGenericTypeDirect() throws Exception {
+    eval("s = depset(['a', 'b', 'c'], transitive = [])");
+    assertThat(get("s").getContentType()).isEqualTo(SkylarkType.of(String.class));
+  }
+
+  @Test
+  public void testHomogeneousGenericTypeItems() throws Exception {
+    eval("s = depset(items = ['a', 'b', 'c'], transitive = [])");
+    assertThat(get("s").getContentType()).isEqualTo(SkylarkType.of(String.class));
+  }
+
+  @Test
+  public void testHomogeneousGenericTypeTransitive() throws Exception {
+    eval("s = depset(['a', 'b', 'c'], transitive = [depset(['x'])])");
+    assertThat(get("s").getContentType()).isEqualTo(SkylarkType.of(String.class));
+  }
+
+  @Test
+  public void testTransitiveIncompatibleOrder() throws Exception {
+    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 {
     new BothModesTest().testIfExactError(
         "cannot add an item of type 'int' to a depset of 'string'",
@@ -135,6 +231,78 @@ public class SkylarkNestedSetTest extends EvaluationTestCase {
   }
 
   @Test
+  public void testBadGenericTypeDirect() throws Exception {
+    new BothModesTest().testIfExactError(
+        "cannot add an item of type 'int' to a depset of 'string'",
+        "depset(direct = ['a', 5])");
+  }
+
+  @Test
+  public void testBadGenericTypeItems() throws Exception {
+    new BothModesTest().testIfExactError(
+        "cannot add an item of type 'int' to a depset of 'string'",
+        "depset(items = ['a', 5])");
+  }
+
+  @Test
+  public void testBadGenericTypeTransitive() throws Exception {
+    new BothModesTest().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 {
+    new BothModesTest().testIfExactError(
+        "Do not pass both 'direct' and 'items' argument to depset constructor.",
+        "depset(['a', 'b'], direct = ['c', 'd'])");
+  }
+
+  @Test
+  public void testItemsAndTransitive() throws Exception {
+    new BothModesTest().testIfExactError(
+        "expected type 'sequence' for items but got type 'depset' instead",
+        "depset(items = depset(), transitive = [depset()])");
+  }
+
+  @Test
+  public void testTooManyPositionals() throws Exception {
+    new BothModesTest().testIfExactError(
+        "too many (3) positional arguments in call to "
+            + "depset(items = [], order: string = \"default\", *, "
+            + "direct: sequence or NoneType = None, "
+            + "transitive: sequence of depsets or NoneType = None)",
+        "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 testUnionWithList() throws Exception {
     assertContainsInOrder("depset([]).union(['a', 'b', 'c'])", "a", "b", "c");
     assertContainsInOrder("depset(['a']).union(['b', 'c'])", "a", "b", "c");
@@ -145,8 +313,8 @@ public class SkylarkNestedSetTest extends EvaluationTestCase {
   @Test
   public void testUnionWithDepset() throws Exception {
     assertContainsInOrder("depset([]).union(depset(['a', 'b', 'c']))", "a", "b", "c");
-    assertContainsInOrder("depset(['a']).union(depset(['b', 'c']))", "a", "b", "c");
-    assertContainsInOrder("depset(['a', 'b']).union(depset(['c']))", "a", "b", "c");
+    assertContainsInOrder("depset(['a']).union(depset(['b', 'c']))", "b", "c", "a");
+    assertContainsInOrder("depset(['a', 'b']).union(depset(['c']))", "c", "a", "b");
     assertContainsInOrder("depset(['a', 'b', 'c']).union(depset([]))", "a", "b", "c");
   }
 
@@ -159,10 +327,12 @@ public class SkylarkNestedSetTest extends EvaluationTestCase {
     assertContainsInOrder("depset(['a', 'a', 'a']).union(depset(['a', 'a']))", "a");
   }
 
+
   private void assertContainsInOrder(String statement, Object... expectedElements)
       throws Exception {
     assertThat(((SkylarkNestedSet) eval(statement)).toCollection())
-        .containsExactly(expectedElements);
+        .containsExactly(expectedElements)
+        .inOrder();
   }
 
   @Test