Improve performance and semantics of union of Skylark sets

== Before this change ==

Previously, if a and b are sets, then a + b created a new set c whose direct and transitive elements were all those of a, and with b appended as an additional transitive element. If on the other hand b is a list instead of a set, then its contents were appended as additional direct elements of c. In both cases, you can think of c as a copy of a that also knows about b.

This copying of a's elements into c can lead to accumulation when you do it repeatedly, e.g. x += y in a loop. Each union can take O(n) time so you get O(n^2) time overall. Nested set union is supposed to be O(1) time per operation and O(n) time overall.

It also leads to surprising iteration orders. If you do a + b + c + d (left-associative), where each one is a set, then when you do a post-order traversal you get the elements of b, c, d, and a, in that order. This is because b, c, and d each get appended as transitive children of the copies of a.

== After this change ==

If a and b are sets, then a + b returns a new set c with a and b as its two transitive children. If b is a list, then c has a as its only transitive child and b's elements as its only direct elements. This is straightforward, O(1), and avoids the problem with the confusing order.

It is implemented by removing the items/transitiveItems fields and just relying on NestedSetBuilder.

RELNOTES[INC]: (Skylark) Set union is now O(1). As a side-effect, the iteration order of sets produced by union has changed. "print(set([1]) + set([2]) + set([3]))" will now give back the order 1, 2, 3 instead of 2, 3, 1.

--
PiperOrigin-RevId: 143972165
MOS_MIGRATED_REVID=143972165

2 files changed, 116 insertions, 133 deletions

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)};
-  }
 }