Improve performance and semantics of union of Skylark sets

== Before this change ==

Previously, if a and b are sets, then a + b created a new set c whose direct and transitive elements were all those of a, and with b appended as an additional transitive element. If on the other hand b is a list instead of a set, then its contents were appended as additional direct elements of c. In both cases, you can think of c as a copy of a that also knows about b.

This copying of a's elements into c can lead to accumulation when you do it repeatedly, e.g. x += y in a loop. Each union can take O(n) time so you get O(n^2) time overall. Nested set union is supposed to be O(1) time per operation and O(n) time overall.

It also leads to surprising iteration orders. If you do a + b + c + d (left-associative), where each one is a set, then when you do a post-order traversal you get the elements of b, c, d, and a, in that order. This is because b, c, and d each get appended as transitive children of the copies of a.

== After this change ==

If a and b are sets, then a + b returns a new set c with a and b as its two transitive children. If b is a list, then c has a as its only transitive child and b's elements as its only direct elements. This is straightforward, O(1), and avoids the problem with the confusing order.

It is implemented by removing the items/transitiveItems fields and just relying on NestedSetBuilder.

RELNOTES[INC]: (Skylark) Set union is now O(1). As a side-effect, the iteration order of sets produced by union has changed. "print(set([1]) + set([2]) + set([3]))" will now give back the order 1, 2, 3 instead of 2, 3, 1.

--
PiperOrigin-RevId: 143972165
MOS_MIGRATED_REVID=143972165

0 files changed, 0 insertions, 0 deletions