Documented the iteration order of SkylarkNestedSets.

Also added additional tests that check for the correct behavior regarding order.

--
MOS_MIGRATED_REVID=99370126

1 files changed, 162 insertions, 0 deletions

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 08123ac41c..64804d5155 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
@@ -23,6 +23,11 @@ import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.junit.runners.JUnit4;
 
+import java.util.Arrays;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+
 /**
  * Tests for SkylarkNestedSet.
  */
@@ -169,4 +174,161 @@ public class SkylarkNestedSetTest extends EvaluationTestCase {
   private SkylarkNestedSet get(String varname) throws Exception {
     return (SkylarkNestedSet) lookup(varname);
   }
+  
+  @Test
+  public void testSetOuterOrderWins() throws Exception {
+    // The order of the outer set should define the final iteration order,
+    // no matter what the order of nested sets is
+    /*
+     * Set:     {4, 44, {1, 11, {2, 22}}}
+     * PRE:     4, 44, 1, 11, 2, 22     (Link)
+     * POST:    2, 22, 1, 11, 4, 44     (Stable)
+     *
+     */
+    Order[] orders = {Order.STABLE_ORDER, Order.LINK_ORDER};
+    String[] expected = {
+        "set([\"2\", \"22\", \"1\", \"11\", \"4\", \"44\"])",
+        "set([\"4\", \"44\", \"1\", \"11\", \"2\", \"22\"], order = \"link\")"};
+
+    for (int i = 0; i < 2; ++i) {
+      Order outerOrder = orders[i];
+      Order innerOrder = orders[1 - i];
+
+      SkylarkNestedSet inner1 =
+          new SkylarkNestedSet(innerOrder, SkylarkList.tuple("1", "11"), null);
+      SkylarkNestedSet inner2 =
+          new SkylarkNestedSet(innerOrder, SkylarkList.tuple("2", "22"), null);
+      SkylarkNestedSet innerUnion = new SkylarkNestedSet(inner1, inner2, null);
+      SkylarkNestedSet result =
+          new SkylarkNestedSet(outerOrder, SkylarkList.tuple("4", "44"), null);
+      result = new SkylarkNestedSet(result, innerUnion, null);
+
+      assertThat(result.toString()).isEqualTo(expected[i]);
+    }
+  }
+
+  @Test
+  public void testSetOrderCompatibility() throws Exception {
+    // Two sets are compatible if
+    //  (a) both have the same order or
+    //  (b) at least one order is "stable"
+
+    for (Order first : Order.values()) {
+      SkylarkNestedSet s1 = new SkylarkNestedSet(first, SkylarkList.tuple("1", "11"), null);
+
+      for (Order second : Order.values()) {
+        SkylarkNestedSet s2 = new SkylarkNestedSet(second, SkylarkList.tuple("2", "22"), null);
+
+        boolean compatible = true;
+
+        try {
+          new SkylarkNestedSet(s1, s2, null);
+        } catch (Exception ex) {
+          compatible = false;
+        }
+
+        assertThat(compatible).isEqualTo(areOrdersCompatible(first, second));
+      }
+    }
+  }
+
+  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, SkylarkList.tuple("1", "11"), null),
+        new SkylarkNestedSet(order, SkylarkList.tuple("2", "22"), null),
+        new SkylarkNestedSet(order, SkylarkList.tuple("3", "33"), null),
+        new SkylarkNestedSet(order, SkylarkList.tuple("4", "44"), null)};
+  }
 }