diff options
3 files changed, 133 insertions, 174 deletions
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 fc78da5385..df936692aa 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,12 +24,9 @@ import com.google.devtools.build.lib.skylarkinterface.SkylarkModule; 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( @@ -85,47 +82,41 @@ public final class SkylarkNestedSet implements Iterable<Object>, SkylarkValue, S 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(order, SkylarkType.TOP, item, loc, null); + this(SkylarkType.TOP, item, loc, new NestedSetBuilder<Object>(order)); } public SkylarkNestedSet(SkylarkNestedSet left, Object right, Location loc) throws EvalException { - this(left.set.getOrder(), left.contentType, right, loc, left); + this( + left.contentType, + right, + loc, + new NestedSetBuilder<Object>(left.getOrder()).addTransitive(left.set)); } // This is safe because of the type checking @SuppressWarnings("unchecked") - 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); - } - } + private SkylarkNestedSet( + SkylarkType contentType, Object item, Location loc, NestedSetBuilder setBuilder) + throws EvalException { // Adding the item if (item instanceof SkylarkNestedSet) { SkylarkNestedSet nestedSet = (SkylarkNestedSet) item; if (!nestedSet.isEmpty()) { contentType = checkType(contentType, nestedSet.contentType, loc); - transitiveItems.add(nestedSet.set); + try { + setBuilder.addTransitive((NestedSet<Object>) nestedSet.set); + } catch (IllegalStateException e) { + // Order mismatch between item and setBuilder. + throw new EvalException(loc, e.getMessage()); + } } } 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); - items.add(object); + setBuilder.add(object); } } else { throw new EvalException( @@ -134,20 +125,7 @@ public final class SkylarkNestedSet implements Iterable<Object>, SkylarkValue, S "cannot add value of type '%s' to a depset", EvalUtils.getDataTypeName(item))); } this.contentType = Preconditions.checkNotNull(contentType, "type cannot be null"); - - // 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); + this.set = setBuilder.build(); } /** @@ -172,8 +150,6 @@ public final class SkylarkNestedSet implements Iterable<Object>, SkylarkValue, S // 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 92d962a9b7..913ae03e2d 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 @@ public class SkylarkEvaluationTest extends EvaluationTest { @Test public void testUnionSet() throws Exception { new SkylarkTest() - .testStatement("str(depset([1, 3]) | depset([1, 2]))", "set([1, 2, 3])") + .testStatement("str(depset([1, 3]) | depset([1, 2]))", "set([1, 3, 2])") .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 967940d470..3b155a744a 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,17 +14,12 @@ 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.Arrays; -import java.util.HashMap; -import java.util.List; -import java.util.Map; +import java.util.Collection; import org.junit.Test; import org.junit.runner.RunWith; import org.junit.runners.JUnit4; @@ -52,19 +47,25 @@ public class SkylarkNestedSetTest extends EvaluationTestCase { @Test public void testNsetOrder() throws Exception { eval("n = depset(['a', 'b'], order='compile')"); - assertEquals(Order.COMPILE_ORDER, get("n").getSet(String.class).getOrder()); + assertThat(get("n").getSet(String.class).getOrder()).isEqualTo(Order.COMPILE_ORDER); } @Test public void testEmptyNsetGenericType() throws Exception { eval("n = depset()"); - assertEquals(SkylarkType.TOP, get("n").getContentType()); + assertThat(get("n").getContentType()).isEqualTo(SkylarkType.TOP); } @Test public void testFunctionReturnsNset() throws Exception { - eval("def func():", " n = depset()", " n += ['a']", " return n", "s = func()"); - assertEquals(ImmutableList.of("a"), get("s").toCollection()); + eval( + "def func():", + " n = depset()", + " n += ['a']", + " return n", + "s = func()"); + assertThat(get("s")).isInstanceOf(SkylarkNestedSet.class); + assertThat(get("s").toCollection()).containsExactly("a"); } @Test @@ -77,21 +78,93 @@ public class SkylarkNestedSetTest extends EvaluationTestCase { " n2 += ['b']", " return n1", "n = func()"); - assertEquals(ImmutableList.of("a"), get("n").toCollection()); + assertThat(get("n").toCollection()).containsExactly("a"); } @Test - public void testNsetNestedItem() throws Exception { + public void testNsetUnionOrder() throws Exception { + // -----o----- [] + // / \ + // o ['a', 'b'] o ['b', 'c'] + // | | + // o [] o [] eval( "def func():", " n1 = depset()", " n2 = depset()", - " n1 += ['a']", - " n2 += ['b']", + " n1 += ['a', 'b']", + " n2 += ['b', 'c']", " n1 += n2", " return n1", "n = func()"); - assertEquals(ImmutableList.of("b", "a"), get("n").toCollection()); + // 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(); } @Test @@ -103,8 +176,13 @@ public class SkylarkNestedSetTest extends EvaluationTestCase { @Test public void testNsetItemList() throws Exception { - eval("def func():", " n = depset()", " n += ['a', 'b']", " return n", "n = func()"); - assertEquals(ImmutableList.of("a", "b"), get("n").toCollection()); + eval( + "def func():", + " n = depset()", + " n += ['a', 'b']", + " return n", + "n = func()"); + assertThat(get("n").toCollection()).containsExactly("a", "b").inOrder(); } @Test @@ -118,20 +196,7 @@ public class SkylarkNestedSetTest extends EvaluationTestCase { " func1(n)", " return n", "n = func2()"); - 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()); + assertThat(get("n").toCollection()).containsExactly("a"); } @Test @@ -145,7 +210,7 @@ public class SkylarkNestedSetTest extends EvaluationTestCase { " return na", "n = func()"); // The iterator lists the Transitive sets first - assertEquals(ImmutableList.of(4, 2, 3, 5), get("n").toCollection()); + assertThat(get("n").toCollection()).containsExactly(4, 2, 3, 5).inOrder(); } @Test @@ -160,14 +225,28 @@ public class SkylarkNestedSetTest extends EvaluationTestCase { @Test public void testNsetToString() throws Exception { - eval("s = depset() + [2, 4, 6] + [3, 4, 5]", "x = str(s)"); - assertEquals("set([2, 4, 6, 3, 5])", lookup("x")); + // 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])"); } @Test public void testNsetToStringWithOrder() throws Exception { - 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")); + // 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\")"); } @SuppressWarnings("unchecked") @@ -203,100 +282,4 @@ public class SkylarkNestedSetTest extends EvaluationTestCase { 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)}; - } } |