1

I'm trying out a UInt4 type. It crashes during conversion from another integer. (Direct initialization from an integer literal now works just fine.) The crash is from an assert I wrote in - triggering because the Standard Library code is trying "0 - 15".

Assuming I wrote FixedWidthInteger.subtractingReportingOverflow(_:) correctly, what are each of these supposed to do on overflow?:

  • unsafeSubtracting
  • "-" (Without the quotes, the forum's MarkDown formatting is triggered.)
  • &-

And do the answers differ whether checks are turned on or not?

My take: I figure "&-" is supposed to let the wrapped-answer through on overflow. That's the very point of the method. The docs for unsafeSubtracting say it's supposed to be fast, but it triggered a precondition-failure when I ran it. I guess it does the same as "&-" on release builds but asserts otherwise. I thought that regular "-" is supposed to assert too, but then the fact that some internal routine of the integer system calls "0 - 15" causally means that I was supposed to do something else. But I don't know what. (Or there's a big bug.)

2

Are you trying to convert from a negative integer? If so, the documented behavior is that an unsigned integer type causes a runtime error.

3

No, I’m testing “UInt4(6)”, so it calls the standard library code to convert an integer. If the standard “-“ is supposed to assert on the base subtraction method flagging overflow (which I thought it is), then there may be a bug.

4

UInt4(6) is a call to init<T>(_ source: T) where T : BinaryInteger, which does not have a default implementation. That is, it’s calling your own code, not standard library code, unless I’m mistaken.

5

There is a default implementation for this initializer in UnsignedInteger when it's also a FixedWidthInteger, which UInt4 is. AIUI, the only protocol initializers you have to provide are the secret truncating-bits one and the one for integer literals.

The error is present in both Xcode 9.2 and 9.3beta. When I'm using the playground version in Xcode 9.3beta, UInt4.bitWidth is called a bunch of times before execution quits at the "print(UInt4(6))" line with "error: Execution was interrupted, reason: EXC_BAD_ACCESS (code=2, address=0x7ffeeef9c818)."

I was also going to add the initializer for non-exact floating-point as mandatory, but I just commented it out for the playground under Xcode 9.3beta and everything compiled. The regular project on Xcode 9.2 still insisted that I keep it. Was the corresponding initializer default implementation added for Swift 4.1?

6

I'd need to see more of your code to figure out what's going on. Any default implementation, as I mentioned, would be building on non-defaulted protocol requirements that you have to implement. If the default implementation relies on very carefully documented semantics that your implementation doesn't fulfill, then you're going to get errors.

As far as I can tell, the default implementation is deliberately trying to create a negative value (that is the only circumstance in which we use 0 - x). It would not do this unless it's in a branch that unsigned integer types should never reach.

The link you're showing is to my implementation of conversion from floating-point values to integer values, which is indeed new for Swift 4.1. (Before then, concrete types in the standard library "implemented" the requirement by calling fatalError.)

7

When I saw the subtraction method being called with 0 and 15, I was wondering if the stdLib code somehow thought Self was a signed type.

I copied this out of the playground:

struct UInt4: FixedWidthInteger, UnsignedInteger {
    init(integerLiteral value: UInt8) {
        self.init(_truncatingBits: numericCast(value))
    }

    static func * (lhs: UInt4, rhs: UInt4) -> UInt4 {
        let result = lhs.multipliedReportingOverflow(by: rhs)
        precondition(!result.overflow)
        return result.partialValue
    }
    static func *= (lhs: inout UInt4, rhs: UInt4) { lhs = lhs * rhs }
    static func + (lhs: UInt4, rhs: UInt4) -> UInt4 {
        let result = lhs.addingReportingOverflow(rhs)
        precondition(!result.overflow)
        return result.partialValue
    }
    static func += (lhs: inout UInt4, rhs: UInt4) { lhs = lhs + rhs }
    static func - (lhs: UInt4, rhs: UInt4) -> UInt4 {
        let result = lhs.subtractingReportingOverflow(rhs)
        precondition(!result.overflow)
        return result.partialValue
    }
    static func -= (lhs: inout UInt4, rhs: UInt4) { lhs = lhs - rhs }

    var hashValue: Int { return value.hashValue }

    var words: UInt8.Words { return value.words }
    var trailingZeroBitCount: Int { return Swift.max(value.trailingZeroBitCount, bitWidth) }
    func quotientAndRemainder(dividingBy rhs: UInt4) -> (quotient: UInt4, remainder: UInt4) {
        return rhs.dividingFullWidth((high: 0, low: self))
    }
    func signum() -> UInt4 { return UInt4(truncatingIfNeeded: value.signum()) }
    static func &= (lhs: inout UInt4, rhs: UInt4) { lhs.value &= rhs.value }
    static func / (lhs: UInt4, rhs: UInt4) -> UInt4 {
        let result = lhs.dividedReportingOverflow(by: rhs)
        precondition(!result.overflow)
        return result.partialValue
    }
    static func /= (lhs: inout UInt4, rhs: UInt4) { lhs = lhs / rhs }
    static func % (lhs: UInt4, rhs: UInt4) -> UInt4 {
        let result = lhs.remainderReportingOverflow(dividingBy: rhs)
        precondition(!result.overflow)
        return result.partialValue
    }
    static func %= (lhs: inout UInt4, rhs: UInt4) { lhs = lhs % rhs }
    static func ^= (lhs: inout UInt4, rhs: UInt4) { lhs.value ^= rhs.value }
    static func |= (lhs: inout UInt4, rhs: UInt4) { lhs.value |= rhs.value }

    init(_truncatingBits value: UInt) {
        self.value = UInt8(truncatingIfNeeded: value) & 0x0F
    }
    var nonzeroBitCount: Int { return value.nonzeroBitCount }
    var leadingZeroBitCount: Int { return value.leadingZeroBitCount - bitWidth }
    var byteSwapped: UInt4 { return self }
    func addingReportingOverflow(_ rhs: UInt4) -> (partialValue: UInt4, overflow: Bool) {
        let result = value.addingReportingOverflow(rhs.value)
        assert(!result.overflow)
        return (UInt4(truncatingIfNeeded: result.partialValue), result.partialValue >> bitWidth != 0)
    }
    func subtractingReportingOverflow(_ rhs: UInt4) -> (partialValue: UInt4, overflow: Bool) {
        let result = value.subtractingReportingOverflow(rhs.value)
        return (UInt4(truncatingIfNeeded: result.partialValue), result.overflow)
    }
    func multipliedReportingOverflow(by rhs: UInt4) -> (partialValue: UInt4, overflow: Bool) {
        let result = value.multipliedReportingOverflow(by: rhs.value)
        assert(!result.overflow)
        return (UInt4(truncatingIfNeeded: result.partialValue), result.partialValue >> bitWidth != 0)
    }
    func dividedReportingOverflow(by rhs: UInt4) -> (partialValue: UInt4, overflow: Bool) {
        let result = value.dividedReportingOverflow(by: rhs.value)
        return (UInt4(truncatingIfNeeded: result.partialValue), result.overflow)
    }
    func remainderReportingOverflow(dividingBy rhs: UInt4) -> (partialValue: UInt4, overflow: Bool) {
        let result = value.remainderReportingOverflow(dividingBy: rhs.value)
        return (UInt4(truncatingIfNeeded: result.partialValue), result.overflow)
    }
    func multipliedFullWidth(by other: UInt4) -> (high: UInt4, low: UInt4) {
        let result = value.multipliedFullWidth(by: other.value)
        assert(result.high == 0)
        return (UInt4(truncatingIfNeeded: result.low >> bitWidth), UInt4(truncatingIfNeeded: result.low))
    }
    func dividingFullWidth(_ dividend: (high: UInt4, low: UInt4)) -> (quotient: UInt4, remainder: UInt4) {
        let result = value.dividingFullWidth((high: 0, low: dividend.high.value << bitWidth | dividend.low.value))
        precondition(result.quotient >> bitWidth == 0)
        return (UInt4(truncatingIfNeeded: result.quotient), UInt4(truncatingIfNeeded: result.remainder))
    }
    static let bitWidth: Int = 4
    static func &<<= (lhs: inout UInt4, rhs: UInt4) { lhs.value << (rhs.value & 0x03) ; lhs.value &= 0x0F }
    static func &>>= (lhs: inout UInt4, rhs: UInt4) { lhs.value >> (rhs.value & 0x03) }

    var value: UInt8
}
8

This code isn't running into problems with what you think it is. When you write let x = UInt4(6), it's calling words 10 times before failing with EXC_BAD_ACCESS, which is not what happens with integer overflow.

The entirety of the default implementation for that initializer is:

  public init<T : BinaryInteger>(_ source: T) {
    if T.isSigned {
      _precondition(source >= (0 as T), "Negative value is not representable")
    }
    if source.bitWidth >= Self.bitWidth {
      _precondition(source <= Self.max, "Not enough bits to represent a signed value")
    }
    self.init(truncatingIfNeeded: source)
  }

You can try to input each expression by hand into your playground to see what stops working. It's not self.init(truncatingIfNeeded: source), which works just fine. Instead, you get the same runtime error when you write:

6 <= UInt4.max

So as you'll see, the problem is that you never implemented conformance to Comparable. This is essentially the same issue we discussed in the other thread.

The compiler has trouble with compile-time errors when a more general method (in this case, heterogeneous comparison) is implemented in terms of a more specific requirement (in this case, homogeneous comparison) that the user hasn't implemented. There are diagnostics improvements to be made on that front (as I discussed earlier in that thread). However, I've also mentioned a few times how this is avoidable on your part:

Fundamentally, you mustn't attempt implementation of a complex protocol hierarchy in one go, as you've done here. Conform your type in separate extensions to each protocol, one at at time, starting from the top of the hierarchy (Equatable). Make sure that each conformance stands on its own without using default implementations from more refined protocols. Had you done so, the compiler would have warned you about missing Comparable methods before you attempted to conform to BinaryInteger. It would also have spared you from several other issues; I'll touch on a few below.

Because there's no separation of protocol conformances and pervasive use of more refined protocol implementations to implement less refined protocol requirements, you've got a web of redundant calls. Let's take the first implementation:

    init(integerLiteral value: UInt8) {
        self.init(_truncatingBits: numericCast(value))
    }

This method takes a value of type UInt8, then calls numericCast(_:) to convert to type UInt. Then, it calls UInt4.init(_truncatingBits), which you wrote as follows:

    init(_truncatingBits value: UInt) {
        self.value = UInt8(truncatingIfNeeded: value) & 0x0F
    }

So, the method actually calls UInt8.init(truncatingIfNeeded:) to convert that value of type UInt back to a value of type UInt8. UInt8.init(truncatingIfNeeded:) is a standard library implementation that in turn calls UInt8.init(_truncatingBits:). This is all to convert a value of type UInt8 to UInt and back to UInt8!

Let's look at the next member:

    static func * (lhs: UInt4, rhs: UInt4) -> UInt4 {
        let result = lhs.multipliedReportingOverflow(by: rhs)
        precondition(!result.overflow)
        return result.partialValue
    }

You're implementing a requirement of Numeric (*) by calling an implementation that's a requirement of the more refined protocol FixedWidthInteger (multipliedReportingOverflow). This is not advisable; you do happen to control both implementations, but even in that scenario, if you happen to call a default implementation in multipliedReportingOverflow without realizing it, you're liable to cause infinite recursion. By contrast, if you call a requirement of Numeric from a requirement of FixedWidthInteger, you can be assured that there won't be infinite recursion if you built up Numeric conformance first.

Let's look at another:

    func signum() -> UInt4 { return UInt4(truncatingIfNeeded: value.signum()) }

Here, you're implementing signum, a requirement of BinaryInteger, by calling init(truncatingIfNeeded:) a default implementation of another requirement of BinaryInteger. Again, you're liable to cause an infinite recursion, because that default implementation rightly assumes that it can call signum at will. Even if this implementation works today, it's not guaranteed to work tomorrow. Do not do this unless you're also providing an implementation of init(truncatingIfNeeded:) that you control.

I hope I've illustrated how you can safely go about implementing a type with conformance to a complex hierarchy of protocols. This will spare you the repeated troubles that you're running into.

6 Likes
9

No, it's not quite the same problem. The generic == and < are not being used to satisfy the required homogenous versions; they already have default implementations in Strideable! Those implementations call distance(to:). BinaryInteger has default implementations for its Strideable members, and the one for distance(to:) calls < (twice in the signed branch) and > (once in the unsigned branch). That's where the infinite recursion comes from.

I patched it in my code for now by adding my own < for UInt4. (I had one for == too, but I commented it out to narrow down the problem.) The official fix probably needs to be new default implementations of < (and ==) in BinaryInteger that don't reference distance(to:). (They could use lexicographic compare on signed-extended reversed words.)

Bug SR-7117

Fundamentally, you mustn't attempt implementation of a complex protocol hierarchy in one go, as you've done here. Conform your type in separate extensions to each protocol, one at at time, starting from the top of the hierarchy (Equatable). Make sure that each conformance stands on its own without using default implementations from more refined protocols. Had you done so, the compiler would have warned you about missing Comparable methods before you attempted to conform to BinaryInteger. It would also have spared you from several other issues; I'll touch on a few below.

Doing that completely defeats the purpose of having default implementations (of required members), because this technique by definition forfeits using those implementations. These library bugs would have been left as time bombs for other users to find. Doing the way I have has found holes due to under-documentation on top of straight-up bugs.

Because there's no separation of protocol conformances and pervasive use of more refined protocol implementations to implement less refined protocol requirements, you've got a web of redundant calls. Let's take the first implementation:

    init(integerLiteral value: UInt8) {
        self.init(_truncatingBits: numericCast(value))
    }

This method takes a value of type UInt8, then calls numericCast(_:) to convert to type UInt. Then, it calls UInt4.init(_truncatingBits), which you wrote as follows:

    init(_truncatingBits value: UInt) {
        self.value = UInt8(truncatingIfNeeded: value) & 0x0F
    }

So, the method actually calls UInt8.init(truncatingIfNeeded:) to convert that value of type UInt back to a value of type UInt8. UInt8.init(truncatingIfNeeded:) is a standard library implementation that in turn calls UInt8.init(_truncatingBits:). This is all to convert a value of type UInt8 to UInt and back to UInt8!

That was an intentional choice. My other choice was making the integer-literal initializer use Uint as the parameter type. I found out that defining the initializer to use an unsigned type meant the compiler automatically filtered out attempts to give a negative number. Using the smallest built-in unsigned integer meant I filtered out most too-large values. Of course, 16...255 are still read and need to be rejected at run-time, meaning that using Uint instead wouldn't really extra painful over UInt8. But I'm taking a third option and have both call a new common initializer:

var value: UInt8
private init(direct value: UInt8) { self.value = value & UInt4.valueMask }
private static let valueMask: UInt8 = 0x0F
private static let shiftMask = UInt8(bitWidth - 1)  // Depends on `bitWidth.nonZeroBitCount == 1`.
//...
init(_truncatingBits value: UInt) { self.init(direct: UInt8(truncatingIfNeeded: value)) }
init(integerLiteral value: UInt8) {
    self.init(direct: value)
    precondition(self.value == value)
}

Let's look at the next member:

    static func * (lhs: UInt4, rhs: UInt4) -> UInt4 {
        let result = lhs.multipliedReportingOverflow(by: rhs)
        precondition(!result.overflow)
        return result.partialValue
    }

You're implementing a requirement of Numeric (*) by calling an implementation that's a requirement of the more refined protocol FixedWidthInteger (multipliedReportingOverflow). This is not advisable; you do happen to control both implementations, but even in that scenario, if you happen to call a default implementation in multipliedReportingOverflow without realizing it, you're liable to cause infinite recursion. By contrast, if you call a requirement of Numeric from a requirement of FixedWidthInteger, you can be assured that there won't be infinite recursion if you built up Numeric conformance first.

There's little point to having multipliedReportingOverflow if I can't have it secretly be the implementation of *. I want to keep the "one truth" of each operation to one method, and have all other related methods call that one. (For multiplication, it's actually multipliedFullWidth(by:).) Remember, for the type that conforms to multiple protocols, directly and/or indirectly, there is no hierarchy(ies). All the members of the protocols are flat from the type's perspective (modulo class types that get a conformance solely through an ancestor class). I can make multiple method implementations as incestuous as I want, in any direction. Even if the witness tables or whatever Swift does behind the scenes treat the implemented protocol methods hierarchically, the members still have to be flat externally. (I would consider it a bug otherwise.)

The alternative from your suggestion would be to write a custom method that effectively duplicates multipliedFullWidth(by:) that the standard methods call.

Let's look at another:

    func signum() -> UInt4 { return UInt4(truncatingIfNeeded: value.signum()) }

Here, you're implementing signum, a requirement of BinaryInteger, by calling init(truncatingIfNeeded:) a default implementation of another requirement of BinaryInteger. Again, you're liable to cause an infinite recursion, because that default implementation rightly assumes that it can call signum at will. Even if this implementation works today, it's not guaranteed to work tomorrow. Do not do this unless you're also providing an implementation of init(truncatingIfNeeded:) that you control.

Well, now I can use that new initializer in these places.

I hope I've illustrated how you can safely go about implementing a type with conformance to a complex hierarchy of protocols. This will spare you the repeated troubles that you're running into.

The actual problems were bugs in the Standard Library. Both in not documenting what isn't covered by default implementations and actually needs to be implemented, and direct bugs in said default implementations.

Most of the currently uncovered arithmetic operations in FixedWidthInteger should have default implementations that use: addingReportingOverflow, subtractingReportingOverflow, multipliedFullWidth and dividingFullWidth.

1 Like
10

It does boil down to the same problem, or at least a very similar one. BinaryInteger refines both Strideable and Comparable and tries to provide default implementations so that you don't have to write too much boilerplate, but you do have to implement either < or distance(to:) and the diagnostics can't tell you that--yet.

If you'd conformed to Comparable before attempting to conform to Strideable, this oversight would have been avoidable.

Given two protocols, P and R : P, this technique does mean that you'll forgo using default implementations in R of protocol requirements in P, at least initially. Afterwards, if you find that your implementations in P never call a certain requirement of P, you can then safely delete your own implementation of that requirement in favor of R's default.

You don't have to use this technique, but my point is that it's an effective way to ensure a very important thing that the compiler doesn't help you with: your implementations of P's requirements should never call R's default implementations of P's requirements (or P's own default implementations, but this technique doesn't help you with that).

Well, your other choice is writing:

    init(integerLiteral value: UInt8) {
        self.value = value & 0xf
    }

I'm not sure why you reason that the alternative is to use UInt as the parameter type rather than to manually remove the multiple layers of redundant integer conversions.

Sure, you can do that, but if you're not extremely careful, you're risking unintentional infinite recursion. The integer protocols compose with each other in very deliberate ways; keeping those relationships clear in your mind and in your code is what helps you avoid these problems.

It also helps your reader (i.e., me) to reason about your code.

There's lots of work to be done in improving how the compiler can help you implement complex protocol requirements correctly, and the documentation does sometime lag behind the introduction of new default implementations. What I'm showing you, however, are ways to make your own code robust independent of changes in the standard library.

There are a bunch of default implementations commented out because they explode compilation time. In the future, these will gradually become possible to put in place. For now, boilerplate.