Bit fields, like in C

[CTMacUser (Daryle Walker)]

@CTMacUser

/// Note that a tuple type automatically conforms to `BitFieldRepresentable` if
/// all of its members do, and a grid array type conforms if its element type
/// does.

I realized, and should have mentioned, that automatic synthesis requires the tuple or grid array to not be a loosely-sized type, since CompactValue specifies a compile-time sized array.

@CTMacUser

protocol BitFieldRepresentable {
    associatedtype CompactValue: [_! ; Bool]
    init?(compactValue: CompactValue)
    var compactValue: CompactValue { get }
}

Since we're turning something whose bits go from taking one bit of space to either one byte or word of space (depending on how Bool is stored), the transport type definitely isn't compact! We should use "BooleanExpansion" and "booleanExpansion" for names instead.

@CTMacUser

The big problem is making small integers. C can make its multi-bit bit fields act as integer types because all its integer types are built-ins, and so the C runtime can do the translations between calculations. Swift deliberately puts the default integer types into the standard library instead of being built-ins.

Maybe we can use a new conversion initializer:

public protocol BinaryInteger : /*...*/ {
    //...

    /// Creates a new instance from a bit pattern copied from the given Boolean
    /// grid array, sign-extending or truncating as needed to fit.
    ///
    /// When the bit width of `T` (the type of `source`) is equal to or greater
    /// than this type's bit width, the result is the truncated lowest-valued
    /// indices of `source`. For example, when converting a pack of 16 Boolean
    /// values to an 8-bit type, only the lower 8 elements of `source` are used.
    ///
    ///     let p: Int16 = -500
    ///     let pa = p.booleanExpansion
    ///     // 'p' has a binary representation of 0b11111110_00001100, so the
    ///     // expansion of 'pa' is [false, false, true, true, false, false,
    ///     // false, false, false, true, true, true, true, true, true, true].
    ///     let q = Int8(transliterating: pa)
    ///     // q == 12
    ///     // 'q' has a binary representation of 00001100
    ///     // 'q.booleanExpansion' is [false, false, true, true, false, false,
    ///     // false, false]
    ///
    /// When the length of `T` is less than this type's bit width, the result is
    /// *sign-extended* to fill the remaining bits. That is, most-significant
    /// bits of the result are filled with 0 or 1 depending on whether
    /// `source.last` is `false` or `true`. (If `source` is empty, the result is
    /// set to zero.)
    ///
    ///     let u: Int8 = 21
    ///     // 'u' has a binary representation of 00010101
    ///     // Its Boolean expansion is [true, false, true, false, true, false,
    ///     // false, false].
    ///     let v = Int16(transliterating: u.booleanExpansion)
    ///     // v == 21
    ///     // 'v' has a binary representation of 00000000_00010101
    ///
    ///     let w: Int8 = -21
    ///     // 'w' has a binary representation of 11101011
    ///     // Its Boolean expansion is [true, true, false, true, false, true,
    ///     // true, true].
    ///     let x = Int16(transliterating: w.booleanExpansion)
    ///     // x == -21
    ///     // 'x' has a binary representation of 11111111_11101011
    ///     let y = UInt16(transliterating: w.booleanExpansion)
    ///     // y == 65515
    ///     // 'y' has a binary representation of 11111111_11101011
    ///
    /// - Parameter source: An integer to convert to this type.
    init<T: [_? ; Bool]>(transliterating source: T)

    //...
}

@John_McCall

That said, the compiler can't automatically compress to less than the formally-expressible range of a type. We can bit-pack Bool and frozen enums, but we'd still need some ability to just put a range constraint on an integer.

That may have to wait until we get value-based generic parameters, since the bounds can't be encoded per-instance, but per type instantiation. Then we need to determine the span of values and how many bits are required, all in @constexpr time, so the results can be used within a BitFieldRepresentable.

@John_McCall

personally don't see eliminating C headers as an interesting goal in and of itself. If you already have an existing C header that perfectly describes the interface you want to work with, you should just use that header instead of trying to duplicate it perfectly in Swift as an exercise.

I would want to punt C; it's a failure every time we have to punt to C. What if we want bit-fields for a Swift-original type, not something ported over?

@scanon

OptionSet is good at what it does, but it's only a piece of what is meant by "bitfields" in C or C++ (and it has some of the same difficulty as C bitfields around endianness and layout, which I would expect a complete "bitfield" proposal to solve).

So, something in the direction of using property wrappers to potentially compact a Bool array to a bit-packed one?

Running with that idea, when we have variadic generics, we could use another property wrapper to create the bit-field effect. This property wrapper would replace the "@compact" built-in.

@dynamicMemberLookup
@propertyWrapper
public struct BitFielded<Storage: FixedWidthInteger, variadic Value: BitFieldRepresentable> {
    @constexpr private static bitCounts = toArray(Value.#map(\.BooleanExpression.count))
    @constexpr private static bitOffsets = scan(bitCounts)
    @constexpr private static totalBitCount = bitCounts.reduce(0, +)
    @constexpr private static let wholeWordCount = totalBitCount / Storage.bitWidth
    @constexpr private static let partialWordCount = totalBitCount % Storage.bitWidth == 0 ? 0 : 1
    @constexpr private static let wordCount = wholeWordCount + partialWordCount

    private typealias Words = [wordCount ; Storage]
    private storage: Words

    public var wrappedValue: (#explode(Value)) {
        get {
            // Can't think of anything right now.
        }
        set {
            self = Self(wrappedValue: newValue, into: Storage.self)
        }
    }
    @inlinable public var projectedValue: Self { return self }

    public init(wrappedValue: (#explode(Value)), into type: Storage.Type) {
        storage = fill(a: Words.self, with: 0)
        // The rest of this is too complicated for me to figure out right now.
    }

    subscript<T>(dynamicMember member: KeyPath<#explode(Value), T>) -> T {
        get {
            // 1. Peel off the head key path component.
            // 2. Get its offset from the value-tuple's start.
            // 3. Get its bit-length within the entire bit-field span.
            // 4. Extract that span of bits.
            // 5. Convert it to the component's full type.
            // 6. Follow the rest of the key path off that component.
        }
        set { /* Do something similar to the "get," but write back too. */ }
    }
}

// I don't know if this would be legal for defaulting the storage type.
extension BitFielded where Storage == UInt {
    @inlinable public init(wrappedValue: #explode(Value)) {
        self.init(wrappedValue: wrappedValue, into: Storage.self)
    }
}

Future idea after the code above: make placeholder empty types that push the next member to a new Storage word.