Files
Yuvraj TiwaryandClaude Fable 5.2 09d8daf0b5 [BitCollections] Don't trap in BitArray shifts when the amount is Int.min
`maskingShiftLeft(by:)`, `maskingShiftRight(by:)` and
`resizingShiftLeft(by:)` handle a negative amount by negating it and
shifting the other way, so `Int.min` trapped with an arithmetic
overflow. All three have a defined result for it: an amount of at least
`count` clears or removes every value, which is what `Int.min + 1`
already did.

Clamp the magnitude of a negative amount to `Int.max` in these three.
`resizingShiftRight(by:)` is left alone: a negative amount inserts
values there, and no array can hold as many as `Int.min` asks for.

The masking shifts had no tests. Add tests for both of them over
word-crossing counts and amounts on either side of `count`, for their
doc examples, and for the extreme amounts.

Co-Authored-By: Claude Fable 5.2 <noreply@anthropic.com>
2026-11-18 12:00:05 +05:30

182 lines
6.2 KiB
Swift

//===----------------------------------------------------------------------===//
//
// This source file is part of the Swift Collections open source project
//
// Copyright (c) 2022 - 2026 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
//
// SPDX-License-Identifier: Apache-2.0 WITH Swift-exception
//
//===----------------------------------------------------------------------===//
extension BitArray {
/// Returns the magnitude of a negative shift amount.
///
/// `Int.min` has no positive counterpart, so it is clamped to `Int.max`.
/// This only suits shifts that discard values: those treat every amount
/// that is at least `count` the same way.
@inline(__always)
internal static func _magnitude(ofNegativeShift amount: Int) -> Int {
assert(amount < 0)
return Int(clamping: amount.magnitude)
}
}
extension BitArray {
/// Shift the bits in this array by the specified number of places to the
/// left (towards the end of the array), by inserting `amount` false values
/// at the beginning.
///
/// If `amount` is negative, this is equivalent to shifting `-amount`
/// places to the right.
///
/// var bits: BitArray = "1110110"
/// bits.resizingShiftLeft(by: 2)
/// // bits is now 111011000
/// bits.resizingShiftLeft(by: -4)
/// // bits is now 11101
/// bits.resizingShiftLeft(by: 8)
/// // bits is now 1110100000000
public mutating func resizingShiftLeft(by amount: Int) {
guard amount != 0 else { return }
if amount > 0 {
_resizingShiftLeft(by: amount)
} else {
_resizingShiftRight(by: Self._magnitude(ofNegativeShift: amount))
}
}
/// Shift the bits in this array by the specified number of places to the
/// right (towards the start of the array), by removing `amount` existing
/// values from the front of the array.
///
/// If `amount` is negative, then this is equivalent to shifting `-amount`
/// places to the left. If amount is greater than or equal to `count`,
/// then the resulting bit array will be empty.
///
/// var bits: BitArray = "1110110"
/// bits.resizingShiftRight(by: 2)
/// // bits is now 11101
/// bits.resizingShiftRight(by: -4)
/// // bits is now 111010000
/// bits.resizingShiftRight(by: 10)
/// // bits is now empty
///
/// If `amount` is between 0 and `count`, then this has the same effect as
/// `removeFirst(amount)`.
public mutating func resizingShiftRight(by amount: Int) {
guard amount != 0 else { return }
if amount > 0 {
_resizingShiftRight(by: amount)
} else {
// This direction inserts values, so `Int.min` cannot be clamped: no
// array can hold as many values as it asks for, and the negation traps.
_resizingShiftLeft(by: -amount)
}
}
internal mutating func _resizingShiftLeft(by amount: Int) {
assert(amount > 0)
_extend(by: amount, with: false)
maskingShiftLeft(by: amount)
}
internal mutating func _resizingShiftRight(by amount: Int) {
assert(amount > 0)
guard amount < count else {
self = .init()
return
}
self._copy(from: unsafe Range(uncheckedBounds: (amount, count)), to: 0)
self._removeLast(amount)
}
}
extension BitArray {
// FIXME: Add maskingShiftRight(by:in:) and maskingShiftLeft(by:in:) for shifting slices.
/// Shift the bits in this array by the specified number of places to the
/// left (towards the end of the array), without changing
/// its count.
///
/// Values that are shifted off the array are discarded. Values that are
/// shifted in are all set to false.
///
/// If `amount` is negative, this is equivalent to shifting `-amount`
/// places to the right. If `amount` is greater than or equal to `count`,
/// then all values are set to false.
///
/// var bits: BitArray = "1110110"
/// bits.maskingShiftLeft(by: 2)
/// // bits is now 1011000
/// bits.maskingShiftLeft(by: -4)
/// // bits is now 0000101
/// bits.maskingShiftLeft(by: 8)
/// // bits is now 0000000
public mutating func maskingShiftLeft(by amount: Int) {
guard amount != 0 else { return }
unsafe _update {
if amount > 0 {
unsafe $0._maskingShiftLeft(by: amount)
} else {
unsafe $0._maskingShiftRight(
by: BitArray._magnitude(ofNegativeShift: amount))
}
}
}
/// Shift the bits in this array by the specified number of places to the
/// right (towards the beginning of the array), without changing
/// its count.
///
/// Values that are shifted off the array are discarded. Values that are
/// shifted in are all set to false.
///
/// If `amount` is negative, this is equivalent to shifting `-amount`
/// places to the left. If `amount` is greater than or equal to `count`,
/// then all values are set to false.
///
/// var bits: BitArray = "1110110"
/// bits.maskingShiftRight(by: 2)
/// // bits is now 0011101
/// bits.maskingShiftRight(by: -3)
/// // bits is now 1101000
/// bits.maskingShiftRight(by: 8)
/// // bits is now 0000000
public mutating func maskingShiftRight(by amount: Int) {
guard amount != 0 else { return }
unsafe _update {
if amount > 0 {
unsafe $0._maskingShiftRight(by: amount)
} else {
unsafe $0._maskingShiftLeft(
by: BitArray._magnitude(ofNegativeShift: amount))
}
}
}
}
extension BitArray._UnsafeHandle {
internal mutating func _maskingShiftLeft(by amount: Int) {
assert(amount > 0)
let d = Swift.min(amount, self.count)
if d == amount {
let range = unsafe Range(uncheckedBounds: (0, self.count &- d))
unsafe self.copy(from: range, to: d)
}
unsafe self.clear(in: Range(uncheckedBounds: (0, d)))
}
internal mutating func _maskingShiftRight(by amount: Int) {
assert(amount > 0)
let d = Swift.min(amount, self.count)
if d == amount {
let range = unsafe Range(uncheckedBounds: (d, self.count))
unsafe self.copy(from: range, to: 0)
}
unsafe self.clear(in: Range(uncheckedBounds: (self.count &- d, self.count)))
}
}