diff options
6 files changed, 116 insertions, 82 deletions
diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetBuilder.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetBuilder.java index be932dd549..c3da6679bf 100644 --- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetBuilder.java +++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/NestedSetBuilder.java @@ -121,7 +121,7 @@ public final class NestedSetBuilder<E> { Preconditions.checkNotNull(subset); Preconditions.checkArgument( order.isCompatible(subset.getOrder()), - "Order mismatch: %s != %s", subset.getOrder(), order); + "Order mismatch: %s != %s", subset.getOrder().getSkylarkName(), order.getSkylarkName()); if (!subset.isEmpty()) { transitiveSets.add(subset); } diff --git a/src/main/java/com/google/devtools/build/lib/collect/nestedset/Order.java b/src/main/java/com/google/devtools/build/lib/collect/nestedset/Order.java index c40546e9a3..d2f2d515f9 100644 --- a/src/main/java/com/google/devtools/build/lib/collect/nestedset/Order.java +++ b/src/main/java/com/google/devtools/build/lib/collect/nestedset/Order.java @@ -22,10 +22,12 @@ import java.util.HashMap; * Type of a nested set (defines order). * * - * <p>STABLE_ORDER: an unspecified traversal order. Use when the order of elements does not matter. + * <p>STABLE_ORDER: an unspecified traversal order. Use when the order of elements does not matter. + * Called "default" or "stable" (deprecated) in Skylark. * * - * <p>COMPILE_ORDER: left-to-right postorder. + * <p>COMPILE_ORDER: left-to-right postorder. Called "postorder" or "compile" (deprecated) in + * Skylark. * * <p>For example, for the nested set {B, D, {A, C}}, the iteration order is "A C B D" * (child-first). @@ -34,25 +36,24 @@ import java.util.HashMap; * the direct members of a set, for example in the case of Javascript dependencies. * * - * <p>LINK_ORDER: a variation of left-to-right preorder. + * <p>LINK_ORDER: a variation of left-to-right preorder that enforces topological sorting. Called + * "topological" or "link" (deprecated) in Skylark. * * <p>For example, for the nested set {A, C, {B, D}}, the iteration order is "A C B D" * (parent-first). * - * <p>This type of set would typically be used for artifacts where elements of - * nested sets go after the direct members of a set, for example when providing - * a list of libraries to the C++ compiler. + * <p>This type of set would typically be used for artifacts where elements of nested sets go after + * the direct members of a set, for example when providing a list of libraries to the C++ compiler. * - * <p>The custom ordering has the property that elements of nested sets always come - * before elements of descendant nested sets. Left-to-right order is preserved if - * possible, both for items and for references to nested sets. + * <p>The custom ordering has the property that elements of nested sets always come before elements + * of descendant nested sets. Left-to-right order is preserved if possible, both for items and for + * references to nested sets. * - * <p>The left-to-right pre-order-like ordering is implemented by running a - * right-to-left postorder traversal and then reversing the result. + * <p>The left-to-right pre-order-like ordering is implemented by running a right-to-left postorder + * traversal and then reversing the result. * - * <p>The reason naive left-to left-to-right preordering is not used here is that - * it does not handle diamond-like structures properly. For example, take the - * following structure (nesting downwards): + * <p>The reason naive left-to left-to-right preordering is not used here is that it does not handle + * diamond-like structures properly. For example, take the following structure (nesting downwards): * * <pre> * A @@ -62,13 +63,13 @@ import java.util.HashMap; * D * </pre> * - * <p>Naive preordering would produce "A B D C", which does not preserve the - * "parent before child" property: C is a parent of D, so C should come before - * D. Either "A B C D" or "A C B D" would be acceptable. This implementation - * returns the first option of the two so that left-to-right order is preserved. + * <p>Naive preordering would produce "A B D C", which does not preserve the "parent before child" + * property: C is a parent of D, so C should come before D. Either "A B C D" or "A C B D" would be + * acceptable. This implementation returns the first option of the two so that left-to-right order + * is preserved. * - * <p>In case the nested sets form a tree, the ordering algorithm is equivalent to - * standard left-to-right preorder. + * <p>In case the nested sets form a tree, the ordering algorithm is equivalent to standard + * left-to-right preorder. * * <p>Sometimes it may not be possible to preserve left-to-right order: * @@ -83,38 +84,42 @@ import java.util.HashMap; * D * </pre> * - * <p>The left branch (B) would indicate "D E" ordering and the right branch (C) - * dictates "E D". In such cases ordering is decided by the rightmost branch - * because of the list reversing behind the scenes, so the ordering in the final - * enumeration will be "E D". + * <p>The left branch (B) would indicate "D E" ordering and the right branch (C) dictates "E D". In + * such cases ordering is decided by the rightmost branch because of the list reversing behind the + * scenes, so the ordering in the final enumeration will be "E D". * * - * <p>NAIVE_LINK_ORDER: a left-to-right preordering. + * <p>NAIVE_LINK_ORDER: a left-to-right preordering. Called "preorder" or "naive_link" (deprecated) + * in Skylark. * * <p>For example, for the nested set {B, D, {A, C}}, the iteration order is "B D A C". * - * <p>The order is called naive because it does no special treatment of dependency graphs - * that are not trees. For such graphs the property of parent-before-dependencies in the iteration - * order will not be upheld. For example, the diamond-shape graph A->{B, C}, B->{D}, C->{D} will be - * enumerated as "A B D C" rather than "A B C D" or "A C B D". + * <p>The order is called naive because it does no special treatment of dependency graphs that are + * not trees. For such graphs the property of parent-before-dependencies in the iteration order will + * not be upheld. For example, the diamond-shape graph A->{B, C}, B->{D}, C->{D} will be enumerated + * as "A B D C" rather than "A B C D" or "A C B D". * - * <p>The difference from LINK_ORDER is that this order gives priority to - * left-to-right order over dependencies-after-parent ordering. Note that the latter is usually more - * important, so please use LINK_ORDER whenever possible. + * <p>The difference from LINK_ORDER is that this order gives priority to left-to-right order over + * dependencies-after-parent ordering. Note that the latter is usually more important, so please use + * LINK_ORDER whenever possible. */ +// TODO(bazel-team): Remove deprecatedSkylarkName and it's associated helpers before Bazel 1.0. public enum Order { - STABLE_ORDER("stable"), - COMPILE_ORDER("compile"), - LINK_ORDER("link"), - NAIVE_LINK_ORDER("naive_link"); + STABLE_ORDER("default", "stable"), + COMPILE_ORDER("postorder", "compile"), + LINK_ORDER("topological", "link"), + NAIVE_LINK_ORDER("preorder", "naive_link"); private static final ImmutableMap<String, Order> VALUES; + private static final ImmutableMap<String, Order> DEPRECATED_VALUES; - private final String name; + private final String skylarkName; + private final String deprecatedSkylarkName; private final NestedSet<?> emptySet; - private Order(String name) { - this.name = name; + private Order(String skylarkName, String deprecatedSkylarkName) { + this.skylarkName = skylarkName; + this.deprecatedSkylarkName = deprecatedSkylarkName; this.emptySet = new NestedSet<>(this); } @@ -126,8 +131,12 @@ public enum Order { return (NestedSet<E>) emptySet; } - public String getName() { - return name; + public String getSkylarkName() { + return skylarkName; + } + + public String getDeprecatedSkylarkName() { + return deprecatedSkylarkName; } /** @@ -138,11 +147,14 @@ public enum Order { * @throws IllegalArgumentException If the name is not valid */ public static Order parse(String name) { - if (!VALUES.containsKey(name)) { + if (VALUES.containsKey(name)) { + return VALUES.get(name); + } else if (DEPRECATED_VALUES.containsKey(name)) { + // TODO(bazel-team): Give a deprecation warning or error. + return DEPRECATED_VALUES.get(name); + } else { throw new IllegalArgumentException("Invalid order: " + name); } - - return VALUES.get(name); } /** @@ -162,11 +174,14 @@ public enum Order { Order[] tmpValues = Order.values(); HashMap<String, Order> entries = Maps.newHashMapWithExpectedSize(tmpValues.length); + HashMap<String, Order> deprecatedEntries = Maps.newHashMapWithExpectedSize(tmpValues.length); for (Order current : tmpValues) { - entries.put(current.getName(), current); + entries.put(current.getSkylarkName(), current); + deprecatedEntries.put(current.getDeprecatedSkylarkName(), current); } VALUES = ImmutableMap.copyOf(entries); + DEPRECATED_VALUES = ImmutableMap.copyOf(deprecatedEntries); } } 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 cfee7b117d..799f850c8a 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 @@ -65,7 +65,7 @@ public class BazelLibrary { + "The depset supports nesting other depsets of the same element type in it. " + "A desired <a href=\"depset.html\">iteration order</a> can also be specified.<br>" + "Examples:<br><pre class=\"language-python\">depset([\"a\", \"b\"])\n" - + "depset([1, 2, 3], order=\"compile\")</pre>", + + "depset([1, 2, 3], order=\"postorder\")</pre>", parameters = { @Param( name = "items", @@ -78,12 +78,14 @@ public class BazelLibrary { @Param( name = "order", type = String.class, - defaultValue = "\"stable\"", + defaultValue = "\"default\"", doc = - "The ordering strategy for the depset if it's nested, " - + "possible values are: <code>stable</code> (default), <code>compile</code>, " - + "<code>link</code> or <code>naive_link</code>. An explanation of the " - + "values can be found <a href=\"depset.html\">here</a>." + "The ordering strategy for the depset. Possible values are: <code>default</code> " + + "(default), <code>postorder</code>, <code>topological</code>, and " + + "<code>preorder</code>. These are also known by the deprecated names " + + "<code>stable</code>, <code>compile</code>, <code>link</code> and " + + "<code>naive_link</code> respectively. An explanation of the values can be found " + + "<a href=\"depset.html\">here</a>." ) }, useLocation = true @@ -116,7 +118,7 @@ public class BazelLibrary { @Param( name = "order", type = String.class, - defaultValue = "\"stable\"", + defaultValue = "\"default\"", doc = "Same as for <a href=\"#depset\">depset</a>." ) }, 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 23535f6fc3..530efc0994 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 @@ -45,6 +45,7 @@ import javax.annotation.Nullable; @SkylarkModule( name = "depset", category = SkylarkModuleCategory.BUILTIN, + // TODO(bazel-team): Move this documentation to a dedicated page and link to it from here. doc = "A language built-in type that supports efficiently accumulating data from transitive " + "dependencies. Note that depsets are not hash sets: they don't support fast membership " @@ -53,38 +54,47 @@ import javax.annotation.Nullable; + "Depsets can be created using the <a href=\"globals.html#depset\">depset</a> function, " + "and they support the <code>|</code> operator to extend the depset with more elements or " + "to nest other depsets inside of it. Examples:<br>" + + "<pre class=language-python>s = depset([1, 2])\n" + "s = s | [3] # s == {1, 2, 3}\n" + "s = s | depset([4, 5]) # s == {1, 2, 3, {4, 5}}\n" - + "other = depset([\"a\", \"b\", \"c\"], order=\"compile\")</pre>" + + "other = depset([\"a\", \"b\", \"c\"], order=\"postorder\")</pre>" + + "Note that in these examples <code>{..}</code> is not a valid literal to create depsets. " + "Depsets have a fixed generic type, so <code>depset([1]) + [\"a\"]</code> or " + "<code>depset([1]) + depset([\"a\"])</code> results in an error.<br>" - + "Elements in a depset can neither be mutable or be of type <code>list</code>, " + + "Elements in a depset can neither be mutable nor be of type <code>list</code>, " + "<code>struct</code> or <code>dict</code>.<br>" + "When aggregating data from providers, depsets can take significantly less memory than " + "other types as they support nesting, that is, their subsets are shared in memory.<br>" + "Every depset has an <code>order</code> parameter which determines the iteration order. " + "There are four possible values:" - + "<ul><li><code>compile</code>: Defines a left-to-right post-ordering where child " - + "elements come after those of nested depsets (parent-last). For example, " - + "<code>{1, 2, 3, {4, 5}}</code> leads to <code>4 5 1 2 3</code>. Left-to-right order " - + "is preserved for both the child elements and the references to nested depsets.</li>" - + "<li><code>stable</code>: Same behavior as <code>compile</code>.</li>" - + "<li><code>link</code>: Defines a variation of left-to-right pre-ordering, i.e. " - + "<code>{1, 2, 3, {4, 5}}</code> leads to <code>1 2 3 4 5</code>. " - + "This ordering enforces that elements of the depset always come before elements of " - + "nested depsets (parent-first), which may lead to situations where left-to-right " - + "order cannot be preserved (<a href=\"https://github.com/bazelbuild/bazel/blob/master/src/main/java/com/google/devtools/build/lib/collect/nestedset/LinkOrderExpander.java#L56\">Example</a>)." + + + "<ul><li><code>postorder</code> (formerly <code>compile</code>): Defines a left-to-right " + + "post-ordering where child elements come after those of nested depsets (parent-last). " + + "For example, <code>{1, 2, 3, {4, 5}}</code> leads to <code>4 5 1 2 3</code>. " + + "Left-to-right order is preserved for both the child elements and the references to " + + "nested depsets.</li>" + + + "<li><code>default</code> (formerly <code>stable</code>): Same behavior as " + + "<code>postorder</code>.</li>" + + + "<li><code>topological</code> (formerly <code>link</code>): Defines a variation of " + + "left-to-right pre-ordering, i.e. <code>{1, 2, 3, {4, 5}}</code> leads to " + + "<code>1 2 3 4 5</code>. This ordering enforces that elements of the depset always come " + + "before elements of nested depsets (parent-first), which may lead to situations where " + + "left-to-right order cannot be preserved (<a href=\"https://github.com/bazelbuild/bazel/blob/master/src/main/java/com/google/devtools/build/lib/collect/nestedset/LinkOrderExpander.java#L56\">Example</a>)." + "</li>" - + "<li><code>naive_link</code>: Defines \"naive\" left-to-right pre-ordering " - + "(parent-first), i.e. <code>{1, 2, 3, {4, 5}}</code> leads to <code>1 2 3 4 5</code>. " - + "Unlike <code>link</code> ordering, it will sacrifice the parent-first property in " - + "order to uphold left-to-right order in cases where both properties cannot be " - + "guaranteed (<a href=\"https://github.com/bazelbuild/bazel/blob/master/src/main/java/com/google/devtools/build/lib/collect/nestedset/NaiveLinkOrderExpander.java#L26\">Example</a>)." + + + "<li><code>preorder</code> (formerly <code>naive_link</code>): Defines \"naive\" " + + "left-to-right pre-ordering (parent-first), i.e. <code>{1, 2, 3, {4, 5}}</code> leads to " + + "<code>1 2 3 4 5</code>. Unlike <code>topological</code> ordering, it will sacrifice the " + + "parent-first property in order to uphold left-to-right order in cases where both " + + "properties cannot be guaranteed (<a href=\"https://github.com/bazelbuild/bazel/blob/master/src/main/java/com/google/devtools/build/lib/collect/nestedset/NaiveLinkOrderExpander.java#L26\">Example</a>)." + "</li></ul>" - + "Except for <code>stable</code>, the above values are incompatible with each other. " - + "Consequently, two depsets can only be merged via the <code>|</code> operator or via " + + + "Except for <code>default</code>, the above values are incompatible with each other. " + + "Consequently, two depsets can only be merged via the <code>+</code> operator or via " + "<code>union()</code> if either both depsets have the same <code>order</code> or one of " + "the depsets has <code>stable</code> order. In the latter case the iteration order will " + "be determined by the outer depset, thus ignoring the <code>order</code> parameter of " @@ -312,7 +322,7 @@ public final class SkylarkNestedSet implements Iterable<Object>, SkylarkValue, S Printer.printList(buffer, this, "[", ", ", "]", null, quotationMark); Order order = getOrder(); if (order != Order.STABLE_ORDER) { - Printer.append(buffer, ", order = \"" + order.getName() + "\""); + Printer.append(buffer, ", order = \"" + order.getSkylarkName() + "\""); } Printer.append(buffer, ")"); } diff --git a/src/test/java/com/google/devtools/build/lib/collect/nestedset/OrderTest.java b/src/test/java/com/google/devtools/build/lib/collect/nestedset/OrderTest.java index e714980558..7f6308dc48 100644 --- a/src/test/java/com/google/devtools/build/lib/collect/nestedset/OrderTest.java +++ b/src/test/java/com/google/devtools/build/lib/collect/nestedset/OrderTest.java @@ -29,7 +29,8 @@ public class OrderTest { @Test public void testParsing() throws Exception { for (Order current : Order.values()) { - assertThat(Order.parse(current.getName())).isEqualTo(current); + assertThat(Order.parse(current.getSkylarkName())).isEqualTo(current); + assertThat(Order.parse(current.getDeprecatedSkylarkName())).isEqualTo(current); } } 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 31a6d495a0..6471192af5 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 @@ -37,15 +37,15 @@ public class SkylarkNestedSetTest extends EvaluationTestCase { @Test public void testLegacyConstructor() throws Exception { - eval("s = set([1, 2, 3], order='compile')"); + eval("s = set([1, 2, 3], order='postorder')"); SkylarkNestedSet s = get("s"); - assertThat(s.getOrder().getName()).isEqualTo("compile"); + assertThat(s.getOrder().getSkylarkName()).isEqualTo("postorder"); assertThat(s.getSet(Object.class)).containsExactly(1, 2, 3); } @Test public void testConstructor() throws Exception { - eval("s = depset(order='stable')"); + eval("s = depset(order='default')"); assertThat(lookup("s")).isInstanceOf(SkylarkNestedSet.class); } @@ -63,6 +63,12 @@ public class SkylarkNestedSetTest extends EvaluationTestCase { @Test public void testOrder() throws Exception { + eval("s = depset(['a', 'b'], order='postorder')"); + assertThat(get("s").getSet(String.class).getOrder()).isEqualTo(Order.COMPILE_ORDER); + } + + @Test + public void testDeprecatedOrder() throws Exception { eval("s = depset(['a', 'b'], order='compile')"); assertThat(get("s").getSet(String.class).getOrder()).isEqualTo(Order.COMPILE_ORDER); } @@ -144,8 +150,8 @@ public class SkylarkNestedSetTest extends EvaluationTestCase { @Test public void testUnionIncompatibleOrder() throws Exception { checkEvalError( - "Order mismatch: LINK_ORDER != COMPILE_ORDER", - "depset(['a', 'b'], order='compile') + depset(['c', 'd'], order='link')"); + "Order mismatch: topological != postorder", + "depset(['a', 'b'], order='postorder') + depset(['c', 'd'], order='topological')"); } @Test @@ -266,9 +272,9 @@ public class SkylarkNestedSetTest extends EvaluationTestCase { @Test public void testToStringWithOrder() throws Exception { eval( - "s = depset(order = 'link') + [2, 4, 6] + [3, 4, 5]", + "s = depset(order = 'topological') + [2, 4, 6] + [3, 4, 5]", "x = str(s)"); - assertThat(lookup("x")).isEqualTo("set([2, 4, 6, 3, 5], order = \"link\")"); + assertThat(lookup("x")).isEqualTo("set([2, 4, 6, 3, 5], order = \"topological\")"); } @SuppressWarnings("unchecked") @@ -290,7 +296,7 @@ public class SkylarkNestedSetTest extends EvaluationTestCase { public void testOrderCompatibility() throws Exception { // Two sets are compatible if // (a) both have the same order or - // (b) at least one order is "stable" + // (b) at least one order is "default" for (Order first : Order.values()) { SkylarkNestedSet s1 = new SkylarkNestedSet(first, Tuple.of("1", "11"), null); |