proposal: add a set data type

[dieortin]

A set data structure, similar to the one in Python, would be a useful addition. For example, it is sometimes required to ensure no duplicate values exist in a list, and a set is the most ergonomic solution.

names = ["Thomas", "David", "Michelle", "David"] # contains duplicate names
unique_names = set(names) # building a set from the list removes duplicates

Other common use cases are:

• Efficiently checking for membership
• Filtering
• Performing mathematical operations (difference, intersection, symmetric difference, union...) among sets

Thoughts? Should I make an attempt at writing a proposal?

Use case example

As an example, I have run into this need while adding automatic dependency exploration in my fork of kklochkov/rules_qt, a ruleset for building Qt applications with Bazel. When generating a rule instantiation, the deps attribute cannot contain duplicate values. Because my feature analyzes Qt shared libraries in the system, and they can be duplicated with different names (for example, libQt6Quick.so and libQt6Quick.so.6.4.3) This introduces the need to enforce each dependency is only added once. Of course, there are ways to work around this problem, but it would be easily solved with a set.

[ndmitchell]

The standard recommendation thus far has been to use a dict with None as the values. I've used that in practice and while it's not quite as nice, it's perfectly workable.

[suganoi]

@dieortin @ndmitchell It's already half-done in Go: google/starlark-go#492

[dieortin]

@suganoi that's nice! I have also just seen #20, but it doesn't seem to include the existence of set.

IMO the set API selected for the Go version makes sense and should be added to the general spec. @laurentlb what do you think?

[laurentlb]

For the record, the example above can be written:

names = ["Thomas", "David", "Michelle", "David"] # contains duplicate names
unique_names = {n: None for n in names}.keys()

In many cases, people want sets just to remove duplicates; this workaround may be sufficient for that use-case.

In Bazel BUILD files, there's a tradition of using lists in most places. For example, deps and srcs are lists, even when the order is not relevant and duplicates are forbidden. In Bazel rules, sets should usually be avoided, and depsets should be used most of the time. So there were concerns that adding a native type set could cause more problems to Bazel. When a set is really needed in Bazel, a set implementation is provided in skylib (https://github.com/bazelbuild/bazel-skylib/blob/main/lib/new_sets.bzl).

As mentioned previously, Starlark-Go has a implementation for sets (https://github.com/google/starlark-go/blob/master/doc/spec.md#set - https://github.com/google/starlark-go/blob/90ade8b19d09805d1b91a9687198869add6dfaa1/starlark/library.go#L990). It can be used using a flag.

[tetromino]

I'm not opposed to a set data type, although if we do add it, I think we ought to also support the literal {foo, bar, ...} syntax. I regularly field questions from new macro and rule authors asking for where is Starlark's set data type :) In Bazel, it would entail a bit of work to chase down the native methods that currently require a starlark list as argument but which could also take a set as argument where it makes sense. And of course we'd need clear documentation for when to use sets vs. depsets.

[stepancheg]

I think we ought to also support the literal {foo, bar, ...} syntax

This is not as easy decision: people constantly make mistakes by writing {} assuming it is an empty set (and in many cases it behaves like empty set, e.g. in in operator or iterator, making it harder to debug). And writing set([foo, bar, ...]) is OK-ish, and has no perf difference if optimized properly.

I suggest to have separate discussions/decisions for set() builtin, and {...} syntax for sets.

[tomaspipes]

Given the discussions ... is there any status on the set data type feature?

[tetromino]

@tomaspipes - given the positive reaction from the community here and elsewhere, I want to take a few days this summer to add a set data type to the Java implementation, and have it enabled in Bazel 8. The Go implementation already has set behind a flag, we may want to flip the flag to enabled.

[tetromino]

Didn't have time to look at this in summer - but I finally wrote an experimental implementation for Java / Bazel: https://bazel.googlesource.com/bazel/+/0651a84f3b1a8d8ad06eb30d96ed298e14dde74f

In light of this, let's hammer out a language spec. Current feature matrix:

• set literals, set comprehensions
  • Supported: python3
  • Not supported: starlark-go, starlark-rust, bazel
• comparison operators implement a partial order via subset relation
  • Supported: python3, starlark-go
  • Not supported: starlark-rust
  • Undecided: bazel
• update() method
  • Supported: python3, starlark-rust, bazel
  • Not supported: starlark-go
• isdisjoint(),intersection_update(), difference_update(), symmetric_difference_update()
  • Supported: python3, bazel
  • Not supported: starlark-go, starlark-rust
• Multiple-argument form of union(), intersection(), difference() (and corresponding _update methods, if implemented):
  • Supported: python3, bazel
  • Not supported: starlark-go, starlark-rust

For the spec, I propose the following:

• Do not support set literals and set comprehensions, per @stepancheg
• Do not support comparison operators - their behavior is surprising/confusing
• Support isdisjoint(), update(), intersection_update(), difference_update(), symmetric_difference_update() - since these are generally useful, easy to implement, and help memory efficiency
• Not sure about multiple-argument form of union(), intersection(), difference() etc. - these are generally useful, but while they are completely trivial to implement in java, it seems that it would be rather awkward to add them starlark-go (due to how starlark-go does its argument parsing for builtins), so perhaps we can live without them. (Did not look at starlark-rust.)

[tetromino]

Proposed spec (with multiple-argument form of union() etc.): #290