apple / swift-collections

Commonly used data structures for Swift
Apache License 2.0
3.55k stars 270 forks source link

BitArray's bitwise operations should allow operating on slices #350

Open lorentey opened 4 months ago

lorentey commented 4 months ago

BitArray currently provides custom operators for the customary bitwise operations:

extension BitArray {
  static func &=(left: inout Self, right: Self)
  static func |=(left: inout Self, right: Self)
  static func ^=(left: inout Self, right: Self)

  static func &(left: Self, right: Self) -> Self
  static func |(left: Self, right: Self) -> Self
  static func ^(left: Self, right: Self) -> Self

  static prefix func ~(value: Self) -> Self

  mutating func toggleAll(in range: some RangeExpression<Int>)
}

These require their inputs to have the same count, and they do not support operating on arbitrary slices of bit arrays. Requiring operands to have the same size does make sense, but disallowing slices seems overly restrictive.

Additionally, using operator syntax for these is rubbing me the wrong way -- I think I'd prefer to keep these as regular named methods for now, deferring the question of introducing operators pending future discussion. (I especially do not like the idea of adding more overloads for the slice-taking variants.)

Bitwise operations over arbitrary slices of bit arrays is very tricky to implement efficiently, so it seems preferably for the library to provide these out of the box.

In an ideal world, we could allow this with the following pleasant slicing syntax:

let a: BitArray, b: BitArray
a[2 ..< 10] |= b[5 ..< 13]

Unfortunately, we do not live in an ideal world -- we have not figured out how to allow in-place slice-mutations like that without incurring unnecessary copy-on-write copies. But we can at least implement named top-level bit array mutations that take index ranges:

a.formBitwiseOr(in: 2 ..< 10, with: b[5 ..< 13])

This isn't nearly as pleasant as the slicing syntax would be, but it's still quite readable, and it at least allows clients to use these operations.

extension BitArray {
  mutating func formBitwiseOr(with other: BitArray)
  mutating func formBitwiseOr(with other: Slice<BitArray>)
  mutating func formBitwiseOr(in range: some RangeExpression<Int>, with other: BitArray)
  mutating func formBitwiseOr(in range: some RangeExpression<Int>, with other: Slice<BitArray>)

  mutating func formBitwiseAnd(with other: BitArray)
  mutating func formBitwiseAnd(with other: Slice<BitArray>)
  mutating func formBitwiseAnd(in range: some RangeExpression<Int>, with other: BitArray)
  mutating func formBitwiseAnd(in range: some RangeExpression<Int>, with other: Slice<BitArray>)

  mutating func formBitwiseXor(with other: BitArray)
  mutating func formBitwiseXor(with other: Slice<BitArray>)
  mutating func formBitwiseXor(in range: some RangeExpression<Int>, with other: BitArray)
  mutating func formBitwiseXor(in range: some RangeExpression<Int>, with other: Slice<BitArray>)

  mutating func toggleAll()
  mutating func toggleAll(in range: some RangeExpression<Int>)
}

Replace the current list of operators with the above list of methods.

lorentey commented 4 months ago

I think we wouldn't want to ship 1.1 with the current operators, so I'm provisionally scheduling this for 1.1.

We may end up deferring adding the slicing variants to a future update though. (Just like we don't currently provide a way to do masking shifts/rotations on a slice of a bit array.)

lorentey commented 3 months ago

Rescheduling to 1.2, to unblock the 1.1 release.

I'm disabling these operators on release/1.1 for now, in https://github.com/apple/swift-collections/pull/353.