Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Open
lorentey opened this issue Jan 9, 2024 · 2 comments
Open

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

lorentey opened this issue Jan 9, 2024 · 2 comments
Labels
BitCollections enhancement New feature or request
Milestone

Comments

@lorentey
Copy link
Member

lorentey commented Jan 9, 2024

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 lorentey added bug Something isn't working BitCollections enhancement New feature or request and removed bug Something isn't working labels Jan 9, 2024
@lorentey lorentey modified the milestones: 1.2.0, 1.1.0 Jan 9, 2024
@lorentey
Copy link
Member Author

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 lorentey modified the milestones: 1.1.0, 1.2.0 Jan 30, 2024
@lorentey
Copy link
Member Author

Rescheduling to 1.2, to unblock the 1.1 release.

I'm disabling these operators on release/1.1 for now, in #353.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
BitCollections enhancement New feature or request
Projects
None yet
Development

No branches or pull requests

1 participant