// 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.annotations.VisibleForTesting;
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.SkylarkModule;
import com.google.devtools.build.lib.skylarkinterface.SkylarkModuleCategory;
import com.google.devtools.build.lib.skylarkinterface.SkylarkValue;
import com.google.devtools.build.lib.util.Preconditions;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
import javax.annotation.Nullable;
/** A generic type safe NestedSet wrapper for Skylark. */
@SkylarkModule(
name = "set",
category = SkylarkModuleCategory.BUILTIN,
doc =
"A language built-in type that supports sets. "
+ "Sets can be created using the set function, and "
+ "they support the | operator to extend the set with more elements or "
+ "to nest other sets inside of it. Examples: "
+ "
s = set([1, 2])\n"
+ "s = s | [3] # s == {1, 2, 3}\n"
+ "s = s | set([4, 5]) # s == {1, 2, 3, {4, 5}}\n"
+ "other = set([\"a\", \"b\", \"c\"], order=\"compile\")
"
+ "Note that in these examples {..} is not a valid literal to create sets. "
+ "Sets have a fixed generic type, so set([1]) + [\"a\"] or "
+ "set([1]) + set([\"a\"]) results in an error. "
+ "Elements in a set can neither be mutable or be of type list, "
+ "struct or dict. "
+ "When aggregating data from providers, sets can take significantly less memory than "
+ "other types as they support nesting, that is, their subsets are shared in memory. "
+ "Every set has an order parameter which determines the iteration order. "
+ "There are four possible values:"
+ "
compile: Defines a left-to-right post-ordering where child "
+ "elements come after those of nested sets (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 sets.
"
+ "
stable: Same behavior as compile.
"
+ "
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 set always come before elements of "
+ "nested sets (parent-first), which may lead to situations where left-to-right "
+ "order cannot be preserved (Example)."
+ "
"
+ "
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 link 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 stable, the above values are incompatible with each other. "
+ "Consequently, two sets can only be merged via the | operator or via "
+ "union() if either both sets have the same order or one of "
+ "the sets has stable order. In the latter case the iteration order will be "
+ "determined by the outer set, thus ignoring the order parameter of "
+ "nested sets."
)
@Immutable
public final class SkylarkNestedSet implements Iterable