| // Copyright 2014 The Bazel Authors. All rights reserved. |
| // |
| // Licensed under the Apache License, Version 2.0 (the "License"); |
| // you may not use this file except in compliance with the License. |
| // You may obtain a copy of the License at |
| // |
| // http://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, software |
| // distributed under the License is distributed on an "AS IS" BASIS, |
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| // See the License for the specific language governing permissions and |
| // limitations under the License. |
| package com.google.devtools.build.lib.syntax; |
| |
| import com.google.common.base.Preconditions; |
| import com.google.common.collect.ImmutableList; |
| import com.google.devtools.build.lib.collect.nestedset.NestedSet; |
| import com.google.devtools.build.lib.collect.nestedset.NestedSet.NestedSetDepthException; |
| import com.google.devtools.build.lib.collect.nestedset.NestedSetBuilder; |
| import com.google.devtools.build.lib.collect.nestedset.Order; |
| import com.google.devtools.build.lib.concurrent.ThreadSafety.Immutable; |
| import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec; |
| import com.google.devtools.build.lib.skylarkinterface.SkylarkCallable; |
| import com.google.devtools.build.lib.skylarkinterface.SkylarkModule; |
| import com.google.devtools.build.lib.skylarkinterface.SkylarkModuleCategory; |
| import java.util.Collection; |
| import java.util.List; |
| import javax.annotation.Nullable; |
| |
| /** |
| * A Depset is a Starlark value that wraps a {@link NestedSet}. |
| * |
| * <p>A NestedSet has a type parameter that describes, at compile time, the elements of the set. By |
| * contrast, a Depset has a value, {@link #getContentType}, that describes the elements during |
| * execution. This type symbol permits the element type of a Depset value to be queried, after the |
| * type parameter has been erased, without visiting each element of the often-vast data structure. |
| * |
| * <p>The content type of a non-empty {@code Depset} is determined by its first element. All |
| * elements must have the same type. An empty depset has type {@code SkylarkType.TOP}, and may be |
| * combined with any other depset. |
| */ |
| // TODO(adonovan): move to lib.packages, as this is a Bazelism. Requires: |
| // - moving the function to StarlarkLibrary.COMMON. |
| // - making SkylarkType.getGenericArgType extensible somehow |
| // - relaxing StarlarkThread.checkStateEquals (or defining Depset.equals) |
| @SkylarkModule( |
| name = "depset", |
| category = SkylarkModuleCategory.BUILTIN, |
| doc = |
| "<p>A specialized data structure that supports efficient merge operations and has a" |
| + " defined traversal order. Commonly used for accumulating data from transitive" |
| + " dependencies in rules and aspects. For more information see <a" |
| + " href=\"../depsets.md\">here</a>." |
| + " <p>The elements of a depset must be hashable and all of the same type (as" |
| + " defined by the built-in type(x) function), but depsets are not simply" |
| + " hash sets and do not support fast membership tests." |
| + " If you need a general set datatype, you can" |
| + " simulate one using a dictionary where all keys map to <code>True</code>." |
| + "<p>Depsets are immutable. They should be created using their <a" |
| + " href=\"globals.html#depset\">constructor function</a> and merged or augmented with" |
| + " other depsets via the <code>transitive</code> argument. There are other deprecated" |
| + " methods (<code>|</code> and <code>+</code> operators)" |
| + " that will eventually go away." |
| + "<p>The <code>order</code> parameter determines the" |
| + " kind of traversal that is done to convert the depset to an iterable. There are" |
| + " four possible values:" |
| + "<ul><li><code>\"default\"</code> (formerly" |
| + " <code>\"stable\"</code>): Order is unspecified (but" |
| + " deterministic).</li>" |
| + "<li><code>\"postorder\"</code> (formerly" |
| + " <code>\"compile\"</code>): A left-to-right post-ordering. Precisely, this" |
| + " recursively traverses all children leftmost-first, then the direct elements" |
| + " leftmost-first.</li>" |
| + "<li><code>\"preorder\"</code> (formerly" |
| + " <code>\"naive_link\"</code>): A left-to-right pre-ordering. Precisely, this" |
| + " traverses the direct elements leftmost-first, then recursively traverses the" |
| + " children leftmost-first.</li>" |
| + "<li><code>\"topological\"</code> (formerly" |
| + " <code>\"link\"</code>): A topological ordering from the root down to the leaves." |
| + " There is no left-to-right guarantee.</li>" |
| + "</ul>" |
| + "<p>Two depsets may only be merged if" |
| + " either both depsets have the same order, or one of them has" |
| + " <code>\"default\"</code> order. In the latter case the resulting depset's order" |
| + " will be the same as the other's order." |
| + "<p>Depsets may contain duplicate values but" |
| + " these will be suppressed when iterating (using <code>to_list()</code>). Duplicates" |
| + " may interfere with the ordering semantics.") |
| @Immutable |
| @AutoCodec |
| public final class Depset implements StarlarkValue { |
| private final SkylarkType contentType; |
| private final NestedSet<?> set; |
| @Nullable private final ImmutableList<Object> items; |
| @Nullable private final ImmutableList<NestedSet<?>> transitiveItems; |
| |
| @AutoCodec.VisibleForSerialization |
| Depset( |
| SkylarkType contentType, |
| NestedSet<?> set, |
| ImmutableList<Object> items, |
| ImmutableList<NestedSet<?>> transitiveItems) { |
| this.contentType = Preconditions.checkNotNull(contentType, "type cannot be null"); |
| this.set = set; |
| this.items = items; |
| this.transitiveItems = transitiveItems; |
| } |
| |
| private static Depset create( |
| Order order, SkylarkType contentType, Object item, @Nullable Depset left) |
| throws EvalException { |
| ImmutableList.Builder<Object> itemsBuilder = ImmutableList.builder(); |
| ImmutableList.Builder<NestedSet<?>> transitiveItemsBuilder = ImmutableList.builder(); |
| if (left != null) { |
| if (left.items == null) { // SkylarkSet created from native NestedSet |
| transitiveItemsBuilder.add(left.set); |
| } else { // Preserving the left-to-right addition order. |
| itemsBuilder.addAll(left.items); |
| transitiveItemsBuilder.addAll(left.transitiveItems); |
| } |
| } |
| // Adding the item |
| if (item instanceof Depset) { |
| Depset nestedSet = (Depset) item; |
| if (!nestedSet.isEmpty()) { |
| contentType = checkType(contentType, nestedSet.contentType); |
| transitiveItemsBuilder.add(nestedSet.set); |
| } |
| } else if (item instanceof Sequence) { |
| for (Object x : (Sequence) item) { |
| checkElement(x, /*strict=*/ true); |
| SkylarkType xt = SkylarkType.of(x); |
| contentType = checkType(contentType, xt); |
| itemsBuilder.add(x); |
| } |
| } else { |
| throw Starlark.errorf( |
| "cannot union value of type '%s' to a depset", EvalUtils.getDataTypeName(item)); |
| } |
| ImmutableList<Object> items = itemsBuilder.build(); |
| ImmutableList<NestedSet<?>> transitiveItems = transitiveItemsBuilder.build(); |
| // Initializing the real nested set |
| NestedSetBuilder<Object> builder = new NestedSetBuilder<>(order); |
| builder.addAll(items); |
| try { |
| for (NestedSet<?> nestedSet : transitiveItems) { |
| builder.addTransitive(nestedSet); |
| } |
| } catch (IllegalArgumentException e) { |
| // Order mismatch between item and builder. |
| throw Starlark.errorf("%s", e.getMessage()); |
| } |
| return new Depset(contentType, builder.build(), items, transitiveItems); |
| } |
| |
| private static void checkElement(Object x, boolean strict) throws EvalException { |
| // Historically the requirement for a depset element was isImmutable(x). |
| // However, this check is neither necessary not sufficient. |
| // It is unnecessary because elements need only be hashable, |
| // as with dicts, whose keys may be mutable so long as mutations |
| // don't affect the hash code. (Elements of a NestedSet must be |
| // hashable because a hash-based set is used to de-duplicate |
| // elements during iteration.) |
| // And it is insufficient because some values are immutable |
| // but not Starlark-hashable, such as frozen lists. |
| // NestedSet calls its hashCode method regardless. |
| // |
| // TODO(adonovan): use this check instead: |
| // EvalUtils.checkHashable(x); |
| // and delete the StarlarkValue.isImmutable and EvalUtils.isImmutable. |
| // Unfortunately this is a breaking change because some users |
| // construct depsets whose elements contain lists of strings, |
| // which are Starlark-unhashable even if frozen. |
| // TODO(adonovan): also remove StarlarkList.hashCode. |
| if (strict && !EvalUtils.isImmutable(x)) { |
| throw Starlark.errorf("depset elements must not be mutable values"); |
| } |
| |
| // Even the looser regime forbids the toplevel constructor to be list or dict. |
| if (x instanceof StarlarkList || x instanceof Dict) { |
| throw Starlark.errorf( |
| "depsets cannot contain items of type '%s'", EvalUtils.getDataTypeName(x)); |
| } |
| } |
| |
| // implementation of deprecated depset(x) constructor |
| static Depset legacyOf(Order order, Object items) throws EvalException { |
| // TODO(adonovan): rethink this API. TOP is a pessimistic type for item, and it's wrong |
| // (should be BOTTOM) if items is an empty Depset or Sequence. |
| return create(order, SkylarkType.TOP, items, null); |
| } |
| |
| // implementation of deprecated depset+x, depset|x |
| static Depset unionOf(Depset left, Object right) throws EvalException { |
| return create(left.set.getOrder(), left.contentType, right, left); |
| } |
| |
| /** |
| * Returns a Depset that wraps the specified NestedSet. |
| * |
| * <p>This operation is type-safe only if the specified element type is appropriate for every |
| * element of the set. |
| */ |
| // TODO(adonovan): enforce that we never construct a Depset with a StarlarkType |
| // that represents a non-Skylark type (e.g. NestedSet<PathFragment>). |
| // One way to do that is to disallow constructing StarlarkTypes for classes |
| // that would fail Starlark.valid; however remains the problem that |
| // Object.class means "any Starlark value" but in fact allows any Java value. |
| public static <T> Depset of(SkylarkType contentType, NestedSet<T> set) { |
| return new Depset(contentType, set, null, null); |
| } |
| |
| /** |
| * Checks that an item type is allowed in a given set type, and returns the type of a new depset |
| * with that item inserted. |
| */ |
| private static SkylarkType checkType(SkylarkType depsetType, SkylarkType itemType) |
| throws EvalException { |
| // An initially empty depset takes its type from the first element added. |
| // Otherwise, the types of the item and depset must match exactly. |
| // |
| // TODO(adonovan): why is the empty depset TOP, not BOTTOM? |
| // T ^ TOP == TOP, whereas T ^ BOTTOM == T. |
| // This can't be changed without breaking callers of getContentType who |
| // expect to see TOP. Maybe this is minor, but it at least would require |
| // changes to EvalUtils#getDataTypeName so that it |
| // can continue to print "depset of Objects" instead of "depset of EmptyTypes". |
| // Better yet, break the behavior and change it to "empty depset". |
| if (depsetType == SkylarkType.TOP || depsetType.equals(itemType)) { |
| return itemType; |
| } |
| throw Starlark.errorf( |
| "cannot add an item of type '%s' to a depset of '%s'", itemType, depsetType); |
| } |
| |
| /** |
| * Throws an {@link TypeException} if this nested set does not have elements of the given type. |
| */ |
| private void checkHasContentType(Class<?> type) throws TypeException { |
| // Empty sets should be SkylarkType.TOP anyway. |
| if (!set.isEmpty() && !contentType.canBeCastTo(type)) { |
| throw new TypeException(); |
| } |
| } |
| |
| /** |
| * Returns the embedded {@link NestedSet}, while asserting that its elements all have the given |
| * type. Note that the type itself cannot be a parameterized type, as the type check is shallow. |
| * |
| * <p>If you do not specifically need the {@code NestedSet} and you are going to flatten it |
| * anyway, prefer {@link #toCollection} to make your intent clear. |
| * |
| * @param type a {@link Class} representing the expected type of the contents |
| * @return the {@code NestedSet}, with the appropriate generic type |
| * @throws TypeException if the type does not accurately describe all elements |
| */ |
| // The precondition ensures generic type safety, and sets are immutable. |
| @SuppressWarnings("unchecked") |
| public <T> NestedSet<T> getSet(Class<T> type) throws TypeException { |
| // TODO(adonovan): eliminate this function and toCollection in favor of ones |
| // that accept a SkylarkType augmented with a type parameter so that it acts |
| // like a "reified generic": whereas a Class symbol can express only the |
| // top-level value tag, a SkylarkType could express an entire type such as |
| // Set<List<String+Integer>>, and act as a "witness" or existential type to |
| // unlock the untyped nested set. For example: |
| // |
| // public <T> NestedSet<T> getSet(SkylarkType<NestedSet<T>> witness) throws TypeException { |
| // if (this.type.matches(witness)) { |
| // return witness.convert(this); |
| // } |
| // throw TypeException; |
| // } |
| |
| checkHasContentType(type); |
| return (NestedSet<T>) set; |
| } |
| |
| /** |
| * Returns the embedded {@link NestedSet} without asserting the type of its elements. To validate |
| * the type of elements in the set, call {@link #getSet(Class)} instead. |
| */ |
| public NestedSet<?> getSet() { |
| return set; |
| } |
| |
| /** |
| * Returns the contents of the set as a {@link Collection}, asserting that the set type is |
| * compatible with {@code T}. |
| * |
| * @param type a {@link Class} representing the expected type of the contents |
| * @throws TypeException if the type does not accurately describe all elements |
| */ |
| // The precondition ensures generic type safety. |
| @SuppressWarnings("unchecked") |
| public <T> Collection<T> toCollection(Class<T> type) throws TypeException { |
| checkHasContentType(type); |
| return (Collection<T>) toCollection(); |
| } |
| |
| /** Returns the contents of the set as a {@link Collection}. */ |
| public Collection<?> toCollection() { |
| return set.toList(); |
| } |
| |
| /** |
| * Returns the embedded {@link NestedSet} of this object while asserting that its elements have |
| * the given type. |
| * |
| * <p>This convenience method should be invoked only by methods which are called from Starlark to |
| * validate the parameters of the method, as the exception thrown is specific to param validation. |
| * |
| * @param expectedType a class representing the expected type of the contents |
| * @param fieldName the name of the field being validated, used to construct a descriptive error |
| * message if validation fails |
| * @return the {@code NestedSet}, with the appropriate generic type |
| * @throws EvalException if the type does not accurately describe the elements of the set |
| */ |
| public <T> NestedSet<T> getSetFromParam(Class<T> expectedType, String fieldName) |
| throws EvalException { |
| try { |
| return getSet(expectedType); |
| } catch (TypeException exception) { |
| throw new EvalException( |
| null, |
| String.format( |
| "for parameter '%s', got a depset of '%s', expected a depset of '%s'", |
| fieldName, getContentType(), EvalUtils.getDataTypeNameFromClass(expectedType)), |
| exception); |
| } |
| } |
| |
| /** |
| * Identical to {@link #getSetFromParam(Class, String)}, except that it handles a <b>noneable</b> |
| * depset parameter. |
| * |
| * <p>If the parameter's value is None, returns an empty nested set. |
| * |
| * @throws EvalException if the parameter is neither None nor a Depset, or if it is a Depset of an |
| * unexpected type |
| */ |
| // TODO(b/140932420): Better noneable handling should prevent instanceof checking. |
| public static <T> NestedSet<T> getSetFromNoneableParam( |
| Object depsetOrNone, Class<T> expectedType, String fieldName) throws EvalException { |
| if (depsetOrNone == Starlark.NONE) { |
| return NestedSetBuilder.<T>emptySet(Order.STABLE_ORDER); |
| } |
| if (depsetOrNone instanceof Depset) { |
| Depset depset = (Depset) depsetOrNone; |
| return depset.getSetFromParam(expectedType, fieldName); |
| } else { |
| throw Starlark.errorf( |
| "expected a depset of '%s' but got '%s' for parameter '%s'", |
| EvalUtils.getDataTypeNameFromClass(expectedType), depsetOrNone, fieldName); |
| } |
| } |
| |
| public boolean isEmpty() { |
| return set.isEmpty(); |
| } |
| |
| @Override |
| public boolean truth() { |
| return !set.isEmpty(); |
| } |
| |
| public SkylarkType getContentType() { |
| return contentType; |
| } |
| |
| @Override |
| public String toString() { |
| return Starlark.repr(this); |
| } |
| |
| public Order getOrder() { |
| return set.getOrder(); |
| } |
| |
| @Override |
| public boolean isImmutable() { |
| return true; |
| } |
| |
| @Override |
| public void repr(Printer printer) { |
| printer.append("depset("); |
| printer.printList(set.toList(), "[", ", ", "]", null); |
| Order order = getOrder(); |
| if (order != Order.STABLE_ORDER) { |
| printer.append(", order = "); |
| printer.repr(order.getSkylarkName()); |
| } |
| printer.append(")"); |
| } |
| |
| @SkylarkCallable( |
| name = "to_list", |
| doc = |
| "Returns a list of the elements, without duplicates, in the depset's traversal order. " |
| + "Note that order is unspecified (but deterministic) for elements that were added " |
| + "more than once to the depset. Order is also unspecified for <code>\"default\"" |
| + "</code>-ordered depsets, and for elements of child depsets whose order differs " |
| + "from that of the parent depset. The list is a copy; modifying it has no effect " |
| + "on the depset and vice versa.", |
| useStarlarkThread = true) |
| public StarlarkList<Object> toList(StarlarkThread thread) throws EvalException { |
| try { |
| return StarlarkList.copyOf(thread.mutability(), this.toCollection()); |
| } catch (NestedSetDepthException exception) { |
| throw new EvalException( |
| null, |
| "depset exceeded maximum depth " |
| + exception.getDepthLimit() |
| + ". This was only discovered when attempting to flatten the depset for to_list(), " |
| + "as the size of depsets is unknown until flattening. " |
| + "See https://github.com/bazelbuild/bazel/issues/9180 for details and possible " |
| + "solutions."); |
| } |
| } |
| |
| /** Create a Depset from the given direct and transitive components. */ |
| static Depset fromDirectAndTransitive( |
| Order order, List<Object> direct, List<Depset> transitive, boolean strict) |
| throws EvalException { |
| NestedSetBuilder<Object> builder = new NestedSetBuilder<>(order); |
| SkylarkType type = SkylarkType.TOP; |
| |
| // Check direct elements' type is equal to elements already added. |
| for (Object x : direct) { |
| // Historically, checkElement was called only by some depset constructors, |
| // but not this one, depset(direct=[x]). |
| // This was a regrettable oversight that allowed users to put mutable values |
| // such as lists into depsets, doubly so because we have just forced our |
| // users to migrate away from the legacy constructor which applied the check. |
| // |
| // We are currently discovering and fixing existing violations, for example |
| // marking the relevant Starlark types as immutable where appropriate |
| // (e.g. ConfiguredTarget), but violations are numerous so we must |
| // suppress the checkElement call below and reintroduce it as a breaking change. |
| // See b/144992997 or github.com/bazelbuild/bazel/issues/10289. |
| checkElement(x, /*strict=*/ strict); |
| |
| SkylarkType xt = SkylarkType.of(x); |
| type = checkType(type, xt); |
| } |
| builder.addAll(direct); |
| |
| // Add transitive sets, checking that type is equal to elements already added. |
| for (Depset x : transitive) { |
| if (!x.isEmpty()) { |
| type = checkType(type, x.getContentType()); |
| if (!order.isCompatible(x.getOrder())) { |
| throw Starlark.errorf( |
| "Order '%s' is incompatible with order '%s'", |
| order.getSkylarkName(), x.getOrder().getSkylarkName()); |
| } |
| builder.addTransitive(x.getSet()); |
| } |
| } |
| |
| return new Depset(type, builder.build(), null, null); |
| } |
| |
| /** An exception thrown when validation fails on the type of elements of a nested set. */ |
| public static class TypeException extends Exception {} |
| } |