Where is the code for bit-twiddling operations defined?

Looking at the Standard Library’s integer code. Noting that my custom UInt72 type had to manually define the arithmetic operators, but none of the bit-twiddling ones. In the file, I see code to forward & / | / ^ to &= / |= / ^=, but I don’t see where the latter are defined for generic code. I see their definitions for the default integer types (UInt8, Int64, etc.), though.

I’m curious, and I may want to apply some optimization. But I want to see the default code first.

In that file, look for the binaryBitwise collection—whenever you see that, the GYB is generating something related to those operators. The operators are declared as requirements on BinaryInteger, with implementations on each stdlib integer type here:

Yes I saw that. But what about for custom types? My UInt72 type had to define + - * / %, but not & | ^. That means that &= |= ^= have generic implementations somewhere, otherwise the compiler would have flagged an error and insist I provide the code. I can’t find those implementations.

You didn’t have to define either the &= or & static methods? Do they crash when you try to use them?

Oh, I see—you’re talking about your UInt72 type from another thread. Yes, the compiler should definitely flag the assignment versions as missing required symbols. Would you mind filing a bug?

There are default implementations for non-mutating versions of operators, dispatched through the mutating ones here: https://github.com/apple/swift/blob/master/stdlib/public/core/Integers.swift.gyb#L3673-L3679

But they are on concrete types, not protocols. so they are not generic.

So I got rid of the old UInt72 code and added a stump version in the test file, like @xnw suggested.

    struct UInt72: CustomDebugStringConvertible, FixedWidthInteger, UnsignedInteger {
    // Implementation properties
    var high: UInt8
    var low: UInt64

    // Main initializer
    init(highOrderBits hi: UInt8, lowOrderBits lo: UInt64) { (high, low) = (hi, lo) }

    // CustomDebugStringConvertible interface
    var debugDescription: String { return "UInt72(\(high.fullHexadecimalString),\(low.fullHexadecimalString))" }

    // FixedWidthInteger secret initializer
    init(_truncatingBits bits: UInt) { self.init(highOrderBits: 0, lowOrderBits: UInt64(bits)) }

    // FixedWidthInteger properties
    var byteSwapped: UInt72 {
        return UInt72(highOrderBits: UInt8(truncatingIfNeeded: low), lowOrderBits: (low.byteSwapped << 8) | UInt64(high))
    }
    var leadingZeroBitCount: Int { return high != 0 ? high.leadingZeroBitCount : 8 + low.leadingZeroBitCount }
    var nonzeroBitCount: Int { return high.nonzeroBitCount + low.nonzeroBitCount }

    static var bitWidth: Int { return 72 }

    // BinaryInteger properties
    var trailingZeroBitCount: Int { return low != 0 ? low.trailingZeroBitCount : high.trailingZeroBitCount + 64 }
    var words: [UInt] { return Array(low.words) + high.words }

    // ExpressibleByIntegerLiteral and Hashable support
    init(integerLiteral value: UInt) { self.init(_truncatingBits: value) }

    var hashValue: Int { return debugDescription.hashValue }

    // BinaryInteger floating-point initializer
    init<T>(_ source: T) where T : BinaryFloatingPoint {
        //fatalError("\(#function) not implemented")
        switch source.floatingPointClass {
        case .negativeNormal where source > -1.0:
            fallthrough
        case .negativeSubnormal, .negativeZero, .positiveZero, .positiveSubnormal:
            self.init(_truncatingBits: 0)
        case .positiveNormal:
            precondition(T.significandBitCount < 72)

            var copy: UInt72 = 1
            copy <<= T.significandBitCount  // inlining 'transparent' functions forms circular loop
            copy |= UInt72(exactly: source.significandBitPattern)!
            copy >>= T.significandBitCount - (source.significandWidth + 1)
            self.init(highOrderBits: copy.high, lowOrderBits: copy.low)
        default:
            preconditionFailure("Out-of-range value")
        }
    }

    // FixedWidthInteger core math
    func addingReportingOverflow(_ rhs: UInt72) -> (partialValue: UInt72, overflow: Bool) {
        fatalError("\(#function) not implemented")
    }
    func dividedReportingOverflow(by rhs: UInt72) -> (partialValue: UInt72, overflow: Bool) {
        fatalError("\(#function) not implemented")
    }
    func dividingFullWidth(_ dividend: (high: UInt72, low: UInt72)) -> (quotient: UInt72, remainder: UInt72) {
        fatalError("\(#function) not implemented")
    }
    func multipliedReportingOverflow(by rhs: UInt72) -> (partialValue: UInt72, overflow: Bool) {
        fatalError("\(#function) not implemented")
    }
    func multipliedFullWidth(by other: UInt72) -> (high: UInt72, low: UInt72) {
        fatalError("\(#function) not implemented")
    }
    func remainderReportingOverflow(dividingBy rhs: UInt72) -> (partialValue: UInt72, overflow: Bool) {
        fatalError("\(#function) not implemented")
    }
    func subtractingReportingOverflow(_ rhs: UInt72) -> (partialValue: UInt72, overflow: Bool) {
        fatalError("\(#function) not implemented")
    }

    // BinaryInteger operators
    static func %(lhs: UInt72, rhs: UInt72) -> UInt72 {
        let results = lhs.remainderReportingOverflow(dividingBy: rhs)
        assert(!results.overflow)
        return results.partialValue
    }
    static func *(lhs: UInt72, rhs: UInt72) -> UInt72 {
        let results = lhs.multipliedReportingOverflow(by: rhs)
        assert(!results.overflow)
        return results.partialValue
    }
    static func +(lhs: UInt72, rhs: UInt72) -> UInt72 {
        let results = lhs.addingReportingOverflow(rhs)
        assert(!results.overflow)
        return results.partialValue
    }
    static func -(lhs: UInt72, rhs: UInt72) -> UInt72 {
        let results = lhs.subtractingReportingOverflow(rhs)
        assert(!results.overflow)
        return results.partialValue
    }
    static func /(lhs: UInt72, rhs: UInt72) -> UInt72 {
        let results = lhs.dividedReportingOverflow(by: rhs)
        assert(!results.overflow)
        return results.partialValue
    }

    static func %=(lhs: inout UInt72, rhs: UInt72) { lhs = lhs % rhs }
    static func *=(lhs: inout UInt72, rhs: UInt72) { lhs = lhs * rhs }
    static func +=(lhs: inout UInt72, rhs: UInt72) { lhs = lhs + rhs }
    static func -=(lhs: inout UInt72, rhs: UInt72) { lhs = lhs - rhs }
    static func /=(lhs: inout UInt72, rhs: UInt72) { lhs = lhs / rhs }
}

Compiling to test on this file flagged an error on the floating-point initializer. There’s a comment about transparency and recursive calls. So I added that fatalError call and commented out the rest of the initializer.

…Now to add a test case that would need to call UInt72's bit-twiddling code…

…Oh, I don’t call anything besides the words property, and I handle the resulting [UInt] myself. It seems I’ll have to go out of my way to test what happens.

OK, I’ll add

XCTAssertEqual(String(reflecting: longword), "UInt72(AA,EEEEEEEEEEEEEEEE)")

at the end of my test case. Now I’ll shift up by 1:

XCTAssertEqual(String(reflecting: longword << 1), "UInt72(55,DDDDDDDDDDDDDDDC)")

and it builds just fine! When I run it as a test-suite, I get a compiler error: inlining 'transparent' functions forms circular loop while pointing at the “l” of longword << 1. So I still don’t know whether there’s an implementation somewhere that the compiler’s choking on, or if it’s the flagging the assignment versions as missing, because the compiler doesn’t get that far.

I just tried:

XCTAssertEqual(String(reflecting: longword & longword), "UInt72(AA,EEEEEEEEEEEEEEEE)")

and got a “Thread 1: EXC_BAD_ACCESS (code=2, address=0x7ffeef3ffff8)” during the test run. That means it still built and initially ran.

Created a bug SR- 7019: “Not all required, yet missing, methods for a protocol are noticed.”

I posted the results of a quick investigation in the JIRA. It seems generally useful so I’ll quote it here:

This is an amazing discovery! Prior to Swift 4 and the new integers, there was a protocol called BitwiseOperations. It was deemed not needed with the introduction of the integer protocols. But, for backward compatibility, it was left in the standard library as _BitwiseOperations with a conditionally available typealias BitwiseOperations. That protocol declares only the “non-muating” operators, the mutating ones (i.e. |= and friends) are defined as free functions here: https://github.com/apple/swift/blob/0b62b0608d50115d5fd3e5714d6d798716ed443a/stdlib/public/core/Policy.swift#L477-L510
As you can see, they are implemented in terms of _BitwiseOperations protocol requirements, which is reasonable.

Now the interesting part. In the new integer protocols we established a convention to provide default implementations for non-mutating functions in terms of mutating ones (exactly the opposite of a much earlier decision made for BitwiseOperations). So now, when you define a type that conforms to the FixedWidthInteger, even though both mutating and non-mutating bitwise operations are required, the default implementation of | comes from extension FixedWidthInteger, and the default implementation of |= comes from the _BitwiseOperations free functions. And they are mutually recursive. Hence the crash.
Unfortunately this is not a unique case where a protocol requirement can be accidentally fulfilled unexpectedly and self-recursively. But in this case, it should be very much possible to mark the default implementations coming from the _BitwiseOperations as obsolete from Swift 4 onward.

Transparent and infinite inlining might have similar causes, but is a separate issue from this.

3 Likes

@Nicole_Jacque And likewise about moving this thread to the standard library category.

Do you think this might have anything to do with this issue:
https://bugs.swift.org/browse/SR-7150

It is possible to work around or reproduce the issue using certain (but seemingly random) combinations of &<< and <<, working differently for different (recent) versions of the compiler.