Rollback of commit 0d1dc5537903a8c2ad56e66cee129b8f4d4e2592.
--
PiperOrigin-RevId: 144194956
MOS_MIGRATED_REVID=144194956
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 df93669..fc78da5 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
@@ -24,9 +24,12 @@
import com.google.devtools.build.lib.skylarkinterface.SkylarkModuleCategory;
import com.google.devtools.build.lib.skylarkinterface.SkylarkValue;
import com.google.devtools.build.lib.util.Preconditions;
+import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
+import java.util.List;
import java.util.Set;
+import javax.annotation.Nullable;
/** A generic type safe NestedSet wrapper for Skylark. */
@SkylarkModule(
@@ -82,41 +85,47 @@
private final SkylarkType contentType;
private final NestedSet<?> set;
+ @Nullable
+ private final List<Object> items;
+ @Nullable
+ private final List<NestedSet> transitiveItems;
public SkylarkNestedSet(Order order, Object item, Location loc) throws EvalException {
- this(SkylarkType.TOP, item, loc, new NestedSetBuilder<Object>(order));
+ this(order, SkylarkType.TOP, item, loc, null);
}
public SkylarkNestedSet(SkylarkNestedSet left, Object right, Location loc) throws EvalException {
- this(
- left.contentType,
- right,
- loc,
- new NestedSetBuilder<Object>(left.getOrder()).addTransitive(left.set));
+ this(left.set.getOrder(), left.contentType, right, loc, left);
}
// This is safe because of the type checking
@SuppressWarnings("unchecked")
- private SkylarkNestedSet(
- SkylarkType contentType, Object item, Location loc, NestedSetBuilder setBuilder)
- throws EvalException {
+ private SkylarkNestedSet(Order order, SkylarkType contentType, Object item, Location loc,
+ @Nullable SkylarkNestedSet left) throws EvalException {
+
+ ArrayList<Object> items = new ArrayList<>();
+ ArrayList<NestedSet> transitiveItems = new ArrayList<>();
+ if (left != null) {
+ if (left.items == null) { // SkylarkSet created from native NestedSet
+ transitiveItems.add(left.set);
+ } else { // Preserving the left-to-right addition order.
+ items.addAll(left.items);
+ transitiveItems.addAll(left.transitiveItems);
+ }
+ }
// Adding the item
if (item instanceof SkylarkNestedSet) {
SkylarkNestedSet nestedSet = (SkylarkNestedSet) item;
if (!nestedSet.isEmpty()) {
contentType = checkType(contentType, nestedSet.contentType, loc);
- try {
- setBuilder.addTransitive((NestedSet<Object>) nestedSet.set);
- } catch (IllegalStateException e) {
- // Order mismatch between item and setBuilder.
- throw new EvalException(loc, e.getMessage());
- }
+ transitiveItems.add(nestedSet.set);
}
} else if (item instanceof SkylarkList) {
+ // TODO(bazel-team): we should check ImmutableList here but it screws up genrule at line 43
for (Object object : (SkylarkList) item) {
contentType = checkType(contentType, SkylarkType.of(object.getClass()), loc);
checkImmutable(object, loc);
- setBuilder.add(object);
+ items.add(object);
}
} else {
throw new EvalException(
@@ -125,7 +134,20 @@
"cannot add value of type '%s' to a depset", EvalUtils.getDataTypeName(item)));
}
this.contentType = Preconditions.checkNotNull(contentType, "type cannot be null");
- this.set = setBuilder.build();
+
+ // Initializing the real nested set
+ NestedSetBuilder<Object> builder = new NestedSetBuilder<>(order);
+ builder.addAll(items);
+ try {
+ for (NestedSet<?> nestedSet : transitiveItems) {
+ builder.addTransitive(nestedSet);
+ }
+ } catch (IllegalStateException e) {
+ throw new EvalException(loc, e.getMessage());
+ }
+ this.set = builder.build();
+ this.items = ImmutableList.copyOf(items);
+ this.transitiveItems = ImmutableList.copyOf(transitiveItems);
}
/**
@@ -150,6 +172,8 @@
// This is here for the sake of FuncallExpression.
this.contentType = Preconditions.checkNotNull(contentType, "type cannot be null");
this.set = Preconditions.checkNotNull(set, "set cannot be null");
+ this.items = null;
+ this.transitiveItems = null;
}
/**
diff --git a/src/test/java/com/google/devtools/build/lib/syntax/SkylarkEvaluationTest.java b/src/test/java/com/google/devtools/build/lib/syntax/SkylarkEvaluationTest.java
index 913ae03..92d962a 100644
--- a/src/test/java/com/google/devtools/build/lib/syntax/SkylarkEvaluationTest.java
+++ b/src/test/java/com/google/devtools/build/lib/syntax/SkylarkEvaluationTest.java
@@ -871,7 +871,7 @@
@Test
public void testUnionSet() throws Exception {
new SkylarkTest()
- .testStatement("str(depset([1, 3]) | depset([1, 2]))", "set([1, 3, 2])")
+ .testStatement("str(depset([1, 3]) | depset([1, 2]))", "set([1, 2, 3])")
.testStatement("str(depset([1, 2]) | [1, 3])", "set([1, 2, 3])")
.testIfExactError("unsupported operand type(s) for |: 'int' and 'int'", "2 | 4");
}
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 3b155a7..967940d 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,12 +14,17 @@
package com.google.devtools.build.lib.syntax;
import static com.google.common.truth.Truth.assertThat;
+import static org.junit.Assert.assertEquals;
+import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableSet;
import com.google.devtools.build.lib.collect.nestedset.Order;
import com.google.devtools.build.lib.syntax.SkylarkList.Tuple;
import com.google.devtools.build.lib.syntax.util.EvaluationTestCase;
-import java.util.Collection;
+import java.util.Arrays;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.JUnit4;
@@ -47,25 +52,19 @@
@Test
public void testNsetOrder() throws Exception {
eval("n = depset(['a', 'b'], order='compile')");
- assertThat(get("n").getSet(String.class).getOrder()).isEqualTo(Order.COMPILE_ORDER);
+ assertEquals(Order.COMPILE_ORDER, get("n").getSet(String.class).getOrder());
}
@Test
public void testEmptyNsetGenericType() throws Exception {
eval("n = depset()");
- assertThat(get("n").getContentType()).isEqualTo(SkylarkType.TOP);
+ assertEquals(SkylarkType.TOP, get("n").getContentType());
}
@Test
public void testFunctionReturnsNset() throws Exception {
- eval(
- "def func():",
- " n = depset()",
- " n += ['a']",
- " return n",
- "s = func()");
- assertThat(get("s")).isInstanceOf(SkylarkNestedSet.class);
- assertThat(get("s").toCollection()).containsExactly("a");
+ eval("def func():", " n = depset()", " n += ['a']", " return n", "s = func()");
+ assertEquals(ImmutableList.of("a"), get("s").toCollection());
}
@Test
@@ -78,93 +77,21 @@
" n2 += ['b']",
" return n1",
"n = func()");
- assertThat(get("n").toCollection()).containsExactly("a");
+ assertEquals(ImmutableList.of("a"), get("n").toCollection());
}
@Test
- public void testNsetUnionOrder() throws Exception {
- // -----o----- []
- // / \
- // o ['a', 'b'] o ['b', 'c']
- // | |
- // o [] o []
+ public void testNsetNestedItem() throws Exception {
eval(
"def func():",
" n1 = depset()",
" n2 = depset()",
- " n1 += ['a', 'b']",
- " n2 += ['b', 'c']",
+ " n1 += ['a']",
+ " n2 += ['b']",
" n1 += n2",
" return n1",
"n = func()");
- // Under old behavior, the left operand was made a parent of the right operand. If that had
- // happened, then the post-order traversal would yield [b, c, a] rather than [a, b, c].
- assertThat(get("n").toCollection()).containsExactly("a", "b", "c").inOrder();
- }
-
- @Test
- public void testNsetMultiUnionOrder() throws Exception {
- // --------o-------- []
- // / \
- // ---o--- [] ---o--- []
- // / \ / \
- // o ['a'] o ['b'] o ['c'] o ['d']
- eval(
- "def func():",
- " na = depset(['a'], order='compile')",
- " nb = depset(['b'], order='compile')",
- " nc = depset(['c'], order='compile')",
- " nd = depset(['d'], order='compile')",
- " return na + nb + (nc + nd)",
- "n = func()");
- // Under old behavior, in a chain of three or more unions s1 + s2 + ... + sn (left-
- // associative), the post-order traversal yielded in order the elements of s2, s3, ..., sn, s1.
- // Now it should just be s1, ..., sn.
- assertThat(get("n").toCollection()).containsExactly("a", "b", "c", "d").inOrder();
- }
-
- @Test
- public void testNsetTransitiveOrder() throws Exception {
- // ---o--- []
- // / \
- // o ['a'] o ['b']
- // |
- // o ['c']
- eval(
- "def func():",
- " na = depset(['a'])",
- " nc = depset(['c'])",
- " nb = nc + ['b']",
- " return na + nb",
- "n = func()");
- assertThat(get("n").toCollection()).containsExactly("a", "c", "b").inOrder();
- }
-
- private Collection<Object> getDiamondTraversal(String order) throws Exception {
- // o ['a']
- // |
- // --o--
- // / \
- // o ['b'] o ['c']
- // \ /
- // --o-- ['d']
- initialize();
- eval(
- "def func():",
- " nd = depset(['d'], order='" + order + "')",
- " nb = nd + ['b']",
- " nc = nd + ['c']",
- " na = nb + nc + ['a']",
- " return na",
- "n = func()");
- return get("n").toCollection();
- }
-
- @Test
- public void testNsetDiamond() throws Exception {
- assertThat(getDiamondTraversal("compile")).containsExactly("d", "b", "c", "a").inOrder();
- assertThat(getDiamondTraversal("naive_link")).containsExactly("a", "b", "d", "c").inOrder();
- assertThat(getDiamondTraversal("link")).containsExactly("a", "b", "c", "d").inOrder();
+ assertEquals(ImmutableList.of("b", "a"), get("n").toCollection());
}
@Test
@@ -176,13 +103,8 @@
@Test
public void testNsetItemList() throws Exception {
- eval(
- "def func():",
- " n = depset()",
- " n += ['a', 'b']",
- " return n",
- "n = func()");
- assertThat(get("n").toCollection()).containsExactly("a", "b").inOrder();
+ eval("def func():", " n = depset()", " n += ['a', 'b']", " return n", "n = func()");
+ assertEquals(ImmutableList.of("a", "b"), get("n").toCollection());
}
@Test
@@ -196,7 +118,20 @@
" func1(n)",
" return n",
"n = func2()");
- assertThat(get("n").toCollection()).containsExactly("a");
+ assertEquals(ImmutableList.of("a"), get("n").toCollection());
+ }
+
+ @Test
+ public void testNsetTransitiveOrdering() throws Exception {
+ eval(
+ "def func():",
+ " na = depset(['a'], order='compile')",
+ " nb = depset(['b'], order='compile')",
+ " nc = depset(['c'], order='compile') + na",
+ " return depset() + nb + nc",
+ "n = func()");
+ // The iterator lists the Transitive sets first
+ assertEquals(ImmutableList.of("b", "a", "c"), get("n").toCollection());
}
@Test
@@ -210,7 +145,7 @@
" return na",
"n = func()");
// The iterator lists the Transitive sets first
- assertThat(get("n").toCollection()).containsExactly(4, 2, 3, 5).inOrder();
+ assertEquals(ImmutableList.of(4, 2, 3, 5), get("n").toCollection());
}
@Test
@@ -225,28 +160,14 @@
@Test
public void testNsetToString() throws Exception {
- // o [3, 4, 5]
- // |
- // o [2, 4, 6]
- // |
- // o []
- eval(
- "s = depset() + [2, 4, 6] + [3, 4, 5]",
- "x = str(s)");
- assertThat(lookup("x")).isEqualTo("set([2, 4, 6, 3, 5])");
+ eval("s = depset() + [2, 4, 6] + [3, 4, 5]", "x = str(s)");
+ assertEquals("set([2, 4, 6, 3, 5])", lookup("x"));
}
@Test
public void testNsetToStringWithOrder() throws Exception {
- // o [3, 4, 5]
- // |
- // o [2, 4, 6]
- // |
- // o []
- eval(
- "s = depset(order = 'link') + [2, 4, 6] + [3, 4, 5]",
- "x = str(s)");
- assertThat(lookup("x")).isEqualTo("set([3, 5, 2, 4, 6], order = \"link\")");
+ eval("s = depset(order = 'link') + [2, 4, 6] + [3, 4, 5]", "x = str(s)");
+ assertEquals("set([2, 4, 6, 3, 5], order = \"link\")", lookup("x"));
}
@SuppressWarnings("unchecked")
@@ -282,4 +203,100 @@
private boolean areOrdersCompatible(Order first, Order second) {
return first == Order.STABLE_ORDER || second == Order.STABLE_ORDER || first == second;
}
+
+ @Test
+ public void testSetOrderComplexUnion() throws Exception {
+ // {1, 11, {2, 22}, {3, 33}, {4, 44}}
+ List<String> preOrder = Arrays.asList("1", "11", "2", "22", "3", "33", "4", "44");
+ List<String> postOrder = Arrays.asList("2", "22", "3", "33", "4", "44", "1", "11");
+
+ MergeStrategy strategy = new MergeStrategy() {
+ @Override
+ public SkylarkNestedSet merge(SkylarkNestedSet[] sets) throws Exception {
+ SkylarkNestedSet union = new SkylarkNestedSet(sets[0], sets[1], null);
+ union = new SkylarkNestedSet(union, sets[2], null);
+ union = new SkylarkNestedSet(union, sets[3], null);
+
+ return union;
+ }
+ };
+
+ runComplexOrderTest(strategy, preOrder, postOrder);
+ }
+
+ @Test
+ public void testSetOrderBalancedTree() throws Exception {
+ // {{1, 11, {2, 22}}, {3, 33, {4, 44}}}
+ List<String> preOrder = Arrays.asList("1", "11", "2", "22", "3", "33", "4", "44");
+ List<String> postOrder = Arrays.asList("2", "22", "4", "44", "3", "33", "1", "11");
+
+ MergeStrategy strategy = new MergeStrategy() {
+ @Override
+ public SkylarkNestedSet merge(SkylarkNestedSet[] sets) throws Exception {
+ SkylarkNestedSet leftUnion = new SkylarkNestedSet(sets[0], sets[1], null);
+ SkylarkNestedSet rightUnion = new SkylarkNestedSet(sets[2], sets[3], null);
+ SkylarkNestedSet union = new SkylarkNestedSet(leftUnion, rightUnion, null);
+
+ return union;
+ }
+ };
+
+ runComplexOrderTest(strategy, preOrder, postOrder);
+ }
+
+ @Test
+ public void testSetOrderManyLevelsOfNesting() throws Exception {
+ // {1, 11, {2, 22, {3, 33, {4, 44}}}}
+ List<String> preOrder = Arrays.asList("1", "11", "2", "22", "3", "33", "4", "44");
+ List<String> postOrder = Arrays.asList("4", "44", "3", "33", "2", "22", "1", "11");
+
+ MergeStrategy strategy = new MergeStrategy() {
+ @Override
+ public SkylarkNestedSet merge(SkylarkNestedSet[] sets) throws Exception {
+ SkylarkNestedSet union = new SkylarkNestedSet(sets[2], sets[3], null);
+ union = new SkylarkNestedSet(sets[1], union, null);
+ union = new SkylarkNestedSet(sets[0], union, null);
+
+ return union;
+ }
+ };
+
+ runComplexOrderTest(strategy, preOrder, postOrder);
+ }
+
+ private interface MergeStrategy {
+ SkylarkNestedSet merge(SkylarkNestedSet[] sets) throws Exception;
+ }
+
+ private void runComplexOrderTest(
+ MergeStrategy strategy, List<String> preOrder, List<String> postOrder) throws Exception {
+ Map<Order, List<String>> expected = createExpectedMap(preOrder, postOrder);
+ for (Order order : Order.values()) {
+ SkylarkNestedSet union = strategy.merge(makeFourSets(order));
+ assertThat(union.toCollection()).containsExactlyElementsIn(expected.get(order)).inOrder();
+ }
+ }
+
+ private Map<Order, List<String>> createExpectedMap(
+ List<String> preOrder, List<String> postOrder) {
+ Map<Order, List<String>> expected = new HashMap<>();
+
+ for (Order order : Order.values()) {
+ expected.put(order, isPostOrder(order) ? postOrder : preOrder);
+ }
+
+ return expected;
+ }
+
+ private boolean isPostOrder(Order order) {
+ return order == Order.STABLE_ORDER || order == Order.COMPILE_ORDER;
+ }
+
+ private SkylarkNestedSet[] makeFourSets(Order order) throws Exception {
+ return new SkylarkNestedSet[] {
+ new SkylarkNestedSet(order, Tuple.of("1", "11"), null),
+ new SkylarkNestedSet(order, Tuple.of("2", "22"), null),
+ new SkylarkNestedSet(order, Tuple.of("3", "33"), null),
+ new SkylarkNestedSet(order, Tuple.of("4", "44"), null)};
+ }
}
