// 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.collect.ImmutableList;
import com.google.devtools.build.lib.collect.nestedset.NestedSet;
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.events.Location;
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 com.google.devtools.build.lib.skylarkinterface.SkylarkValue;
import com.google.devtools.build.lib.syntax.SkylarkList.MutableList;
import com.google.devtools.build.lib.util.Preconditions;
import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
import javax.annotation.Nullable;
/**
* A generic, type-safe {@link NestedSet} wrapper for Skylark.
*
*
The content type of a {@code SkylarkNestedSet} is the intersection of the {@link SkylarkType}
* of each of its elements. It is an error if this intersection is {@link SkylarkType#BOTTOM}. An
* empty set has a content type of {@link SkylarkType#TOP}.
*
*
It is also an error if this type has a non-bottom intersection with {@link SkylarkType#DICT}
* or {@link SkylarkType#LIST}, unless the set is empty.
* TODO(bazel-team): Decide whether this restriction is still useful.
*/
@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 "
+ "tests, but on the contrary they support fast union. Depsets are designed to be used as "
+ "a collection of items (such as file names) generated by Bazel targets. "
+ "Depsets can be created using the depset function, "
+ "and they support the | operator to extend the depset with more elements or "
+ "to nest other depsets inside of it. Examples: "
+ "
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=\"postorder\")
"
+ "Note that in these examples {..} is not a valid literal to create depsets. "
+ "Depsets have a fixed generic type, so depset([1]) + [\"a\"] or "
+ "depset([1]) + depset([\"a\"]) results in an error. "
+ "Elements in a depset can neither be mutable nor be of type list, "
+ "struct or dict. "
+ "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. "
+ "Every depset has an order parameter which determines the iteration order. "
+ "There are four possible values:"
+ "
postorder (formerly compile): Defines a left-to-right "
+ "post-ordering where child elements come after those of nested depsets (parent-last). "
+ "For example, {1, 2, 3, {4, 5}} leads to 4 5 1 2 3. "
+ "Left-to-right order is preserved for both the child elements and the references to "
+ "nested depsets.
"
+ "
default (formerly stable): Same behavior as "
+ "postorder.
"
+ "
topological (formerly link): Defines a variation of "
+ "left-to-right pre-ordering, i.e. {1, 2, 3, {4, 5}} leads to "
+ "1 2 3 4 5. 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 (Example)."
+ "
"
+ "
preorder (formerly naive_link): Defines \"naive\" "
+ "left-to-right pre-ordering (parent-first), i.e. {1, 2, 3, {4, 5}} leads to "
+ "1 2 3 4 5. Unlike topological ordering, it will sacrifice the "
+ "parent-first property in order to uphold left-to-right order in cases where both "
+ "properties cannot be guaranteed (Example)."
+ "
"
+ "Except for default, the above values are incompatible with each other. "
+ "Consequently, two depsets can only be merged via the + operator or via "
+ "union() if either both depsets have the same order or one of "
+ "the depsets has stable order. In the latter case the iteration order will "
+ "be determined by the outer depset, thus ignoring the order parameter of "
+ "nested depsets."
)
@Immutable
public final class SkylarkNestedSet implements SkylarkValue, SkylarkQueryable {
private final SkylarkType contentType;
private final NestedSet> set;
@Nullable
private final List