Marcin Krzyżanowski had a great post a few days ago about the challenges of working with integers in Swift, Madness of Generic Integer. The gist of the post is that since Swift’s disparate integer types don’t have a single common protocol in their hierarchy that encapsulates all their functionality, you need to jump too many hurdles to write generic functions that can apply to all the available integer types, from Int8 up to UInt64.

I’d like to explain here how I would go about solving this particular problem, and in the process hopefully make Swift generic functions a bit easier to understand and implement. Some of the frustration I’ve seen in the responses to Marcin’s post seem to stem from trying to look at Swift’s protocol system through Objective-C-tinged lenses.

While Swift and Objective-C both use protocols extensively, protocols in Swift are constructed and put to use in an entirely different way. In Objective-C, protocols are mostly used to loosely couple objects—for example, a UITableView doesn’t need to know the precise type of its data source, just that it conforms to UITableViewDataSource. In Swift, however, protocols hierarchically build functionality by adding capabilities to types bit by bit. The sprawling protocol hierarchy of Int isn’t a sign of addled language designers run amok, but of a deep and powerful type system.

I’d like to suggest a workflow for creating generic functions, whether for integer types, collection types, or anything else:

  1. Create a type-specific version of your function. Get it working and simplify as much as you can.

  2. Look at your function implementation and determine what functions and operations you’ll need. Are you simply adding two numbers? Are you using the length of an array or map, reduce, and filter?

  3. Enumerate the types that you want to use with a generic version of your function and look for their common protocol ancestors. For example, at what point do the protocol hierarchy graphs for Array and Dictionary merge?

  4. Find the lowest-level protocol that provides your needed functionality. Keep in mind that you use generic constraints to require that the type for your generic function conforms to multiple protocols.

  5. If you can’t find one or more protocols that provide all the functionality you need (as Marcin found), you may need to write your own, and extend your targeted types to conform to your new protocol. (Depending on what you’re doing in your function, this may require adding a new top-level function or two.)

  6. Genericize! You’re now ready to convert your type-specific function to a generic one and test it.

I’ll walk through each of these steps with the problem from Marcin’s post: converting an array of bytes (UInt8) to any particular integer type.

1. A type-specific function

Before trying to write a generic function that handles this, I’ll write a type specific one so I know what I’m working with, and try to reduce it to its simplest form. Particularly when using collections, favor top-level functions over instance methods: map(array) { ... } instead of array.map { ... }:

func integerWithBytes(bytes: [UInt8]) -> UInt32? {
    // check the size of the bytes array
    if bytes.count != sizeof(UInt32) {
        return nil
    }
    
    var result: UInt32 = 0
    for byte in bytes.reverse() {
        result = result << 8 | UInt32(byte)
    }
    return result
}

We’re going to step through the bytes array in reverse, shifting result upward by one byte-length at each step and using a bitwise or (|) to add each byte. Testing this out, we can see that it works properly:

let shouldBeNil = integerWithBytes([0])                         // nil
let shouldBeOne = integerWithBytes([0x01, 0x00, 0x00, 0x00])    // 1
let shouldBeMax = integerWithBytes([0xFF, 0xFF, 0xFF, 0xFF])    // 4294967295

2. Finding operations

Looking at my function, I can see that I’m doing four things with UInt32:

  1. var result: UInt32 = 0 is initializing a variable from an integer literal,
  2. result << 8 uses the << left bitshift operator,
  3. UInt32(byte) initializes a new UInt32 from an UInt8, and
  4. the bitwise or operator | merges those last two expressions.

3. Enumerate types

As said above, I’d like this to work with any signed or unsigned integer type. Let’s take a look at the Int and UInt8 protocol graphs, as examples of the types I want to use.

4. Find common protocol ancestors

It looks like IntegerType is probably the best match for what I need. It inherits from IntegerLiteralConvertible, solving #1 above, and from BitwiseOperationsType, solving #4. Unfortunately, I can’t find a protocol that satisfies #2 and #3—there’s no BitshiftOperationsType (although there should be), and no common protocol that provides a UInt8 intitializer.

5. Adding to the protocol hierarchy

To solve these missing items, we can think either big or small. Thinking big means we would implement the protocols that were left out of Swift’s standard library—in this case, BitshiftOperationsType and, perhaps, ByteConvertible.

protocol BitshiftOperationsType {
    func <<(lhs: Self, rhs: Self) -> Self
    func >>(lhs: Self, rhs: Self) -> Self
    func <<=(inout lhs: Self, rhs: Self)
    func >>=(inout lhs: Self, rhs: Self)
}

protocol ByteConvertible {
    init(_ value: UInt8)
}

Thinking small in this case would be adding a protocol that does exactly what our function needs and nothing more: a ByteArrayConvertibleType protocol with only the four operations listed in step 2:

// inheriting from IntegerType gets us bitwise operations and literal convertible
protocol ByteArrayConvertibleType : IntegerType {
    init(_ value: UInt8)
    func <<(lhs: Self, rhs: Self) -> Self
}

In either case, we need to add our new protocol(s) to all the integer types. It’s easy to do this, since they already implement the required initializer and operator functions—Apple calls this declaring protocol adoption. I’ll use the “thinking big” version here:

extension Int : BitshiftOperationsType, ByteConvertible {}
extension Int8 : BitshiftOperationsType, ByteConvertible {}
extension Int16 : BitshiftOperationsType, ByteConvertible {}
// yada yada yada...

6. Type-specific to generic

Now we’re ready for the generic implementation of our integerWithBytes function. Add the generic constraints to the earlier function and convert the specific type UInt32 to the generic T:

func integerWithBytes<T: IntegerType where T: ByteConvertible, T: BitshiftOperationsType>
    (bytes: [UInt8]) -> T?
{
    if bytes.count != sizeof(T) {
        return nil
    }
    
    var result: T = 0
    for byte in bytes.reverse() {
        result = result << 8 | T(byte)
    }
    return result
}

Now, before anyone gets angle-bracket-T blindness, here’s what that bracketed code is saying:

  • <T: IntegerType—you can call this function with any type that conforms to IntegerType
  • where T: ByteConvertible—and conforms to ByteConvertible
  • , T: BitshiftOperationsType>—and conforms to BitshiftOperationsType

Testing out our newly generic function, we can check for any runtime issues:

// original examples:
let shouldBeNil: UInt32? = integerWithBytes([0])
let shouldBeOne: UInt32? = integerWithBytes([0x01, 0x00, 0x00, 0x00])
let shouldBeMax: UInt32? = integerWithBytes([0xFF, 0xFF, 0xFF, 0xFF])
// all still correct

// new types:
let uhOh: UInt8? = integerWithBytes([1])
> EXC_BAD_INSTRUCTION
let alsoBad: Int8? = integerWithBytes([0xFF])
> EXC_BAD_INSTRUCTION

So, what happened there? Shifting by eight bits is fine for UInt32, but with an eight-bit type it’s a runtime exception. Moreover, even trying to initialize a signed Int8 with a higher-range UInt8 will result in an overflow. These are a couple of the errors, like out-of-bounds exceptions, that Swift’s type-checking unfortunately can’t protect us from. To fix the problem, we’ll need to add a bit pattern-based initializer to our ByteConvertible protocol—init(truncatingBitPattern:) already exists for most integer types, with this description:

Construct a [specific integer type] having the same bitwise representation as the least significant bits of the provided bit pattern. No range or overflow checking occurs.

Sounds like what we need! Here’s the new declaration of ByteConvertible, and an implementation of the init for the two integer types without it:

protocol ByteConvertible {
    init(_ value: UInt8)
    init(truncatingBitPattern: UInt64)
}

extension Int64  : BitshiftOperationsType, ByteConvertible {
    init(truncatingBitPattern value: UInt64) {
        self = Int64(bitPattern: value)
    }
}
extension UInt64 : BitshiftOperationsType, ByteConvertible {
    init(truncatingBitPattern value: UInt64) {
        self = value
    }
}

Now we can use that initializer to return early if T is a single-byte type:

func integerWithBytes<T: IntegerType where T: ByteConvertible, T: BitshiftOperationsType>
    (bytes: [UInt8]) -> T?
{
    if bytes.count != sizeof(T) {
        return nil
    }
    
    if sizeof(T) == 1 {
        return T(truncatingBitPattern: UInt64(bytes[0]))
    }
    
    var result: T = 0
    for byte in bytes.reverse() {
        result = result << 8 | T(byte)
    }
    return result
}

// new types:
let noProblem: UInt8? = integerWithBytes([1])
// 1
let allGood: Int8? = integerWithBytes([0xFF])
// -1

All set! You can get the final code as a gist.

I hope this post has provided some clarity into how generic functions can be constructed. Generics aren’t always intuitive or easy at first, particularly for those coming from an Objective-C background. However, they are a powerful feature in a strongly-typed language such as Swift and one that can’t be ignored.