Xiaodi Wu
June 17, 2017
The design, re-design, and implementation of SE-0104, a proposal to revise integer protocols in Swift, is now largely complete in shipping previews of Swift 4.0. As an exercise, I have used the new APIs to develop a set of additional numeric facilities. Here are some insights gained from that experience and suggestions for improvement based on that experience.
- Performing heterogeneous comparison with integer literals
- Conforming to
_ExpressibleByBuiltinIntegerLiteral - Overriding heterogeneous comparison and bit shift operators
- Masking shifts and arbitrary-width integers
- Using
ArithmeticOverflow - Initializing from a floating-point source
SE-0104 added heterogeneous comparison and bit shift operators to the language to improve the user experience (for example, you can now check if an Int value is equal to a UInt value).1
These operators behave as intended with concrete types, but comparisons in generic algorithms behave differently. This was encountered during review of the standard library's implementation of DoubleWidth, which in fact had a bug as a consequence of the following behavior:
func f() -> Bool {
return UInt.max == ~0
}
func g() -> Bool {
return UInt.max == .max
}
func h<T : FixedWidthInteger>(_: T.Type) -> Bool {
return T.max == ~0
}
func i<T : FixedWidthInteger>(_: T.Type) -> Bool {
return T.max == .max
}
f() // Returns `true`.
g() // Returns `true`.
h(UInt.self) // Returns `false`.
i(UInt.self) // Returns `true`.The reason that h(_:) gives a surprising result is explained as follows:
-
Each concrete integer type implements its own overload of the homogeneous comparison operator, whereas protocol extension methods implement heterogeneous comparison operators. When an integer literal is used on the right-hand side of the comparison, the compiler looks first to the concrete type for an suitable implementation of the operator and finds the homogeneous overload. Therefore, it does not traverse the protocol hierarchy and instead infers the literal to be of the same type as the left-hand side.
-
In generic code, even if the most refined protocol implements its own overload of the homogeneous comparison operator, the compiler will look for all overloads of the operator by traversing the entire protocol hierarchy. Since heterogeneous comparison operators are defined somewhere along the hierarchy, the will always find an overload that accepts the "preferred" integer literal type (
Swift.IntegerLiteralType, akaInt) and infers the literal to be of typeInt.
Therefore, in the invocation h(UInt.self), we are actually comparing UInt.max to ~(0 as Int). This is a surprising result, as evidenced by the fact that a bug nearly slipped into the standard library itself.
> 1 Similar enhancements for operations such as addition are not yet possible because a design is lacking for how to express the idea of _promotion_. If and when Swift allows integer constants as generic parameters (e.g. `typealias Int64 = _Int<64>`), this may become a more realistic prospect as bit widths could then be expressed in generic constraints (e.g. `func + (lhs: T, rhs: U) -> U where T : FixedWidthInteger, U : FixedWidthInteger, T.BitWidth < U.BitWidth`). This is meant to be an aside and is certainly outside the scope of correctly or incrementally improving upon SE-0104. [↩](#a1)
@xwu what are the “various reasons” you think arbitrary precision integers are best represented as sign-magnitude? As far as I can tell, two's complement has only advantages and no drawbacks in this application.