Which function does Swift call? Part 2: Single Arguments

In the previous article, we saw how Swift allows overloading by just the return type. With these kind of overloads, explicitly stating the type tells Swift which function you want to call:

// r will be of type Range<Int>
let r = 1...5

// if you want a ClosedInterval<Int>, you
// have to be explicit:
let integer_interval: ClosedInterval = 1...5

But that still doesn’t explain why you get a Range back by default if you don’t specify what kind of return type you want. To answer that, we need to look at function arguments. We’ll start with just single-argument functions.

Unlike with return values, functions with the same name that take different types for their arguments don’t always need explicit disambiguation. Swift will try its best to pick one for you based on various best-match criteria.

As a rule of thumb, Swift likes to pick the most “specific” function possible based on the arguments passed. Swift’s fave thing, the thing that beats out all other single arguments, is a function that takes the exact type you’re passing.

If it can’t find a function that takes that exact type, the next preferred option is an inherited class or protocol. Child classes or protocols are preferred over parents.

To see this in action:

protocol P { }
protocol Q: P { }

struct S: Q { }

// this is the function that will be picked
// if called with type S
func f(s: S) { print("S") }

// if that weren't defined, this would be the next
// choice for a call passing in an S, since Q is
// more specialized than P:
func f(p: Q) { print("Q") }

// and then finally this
func f(p: P) { print("P") }

f(S())  // prints S

class C: P { }
class D: C { }
class E: D { }

// this is the function that will be picked
func f(d: D) { print("D") }

// if that weren't defined, this would be the next choice
func f(c: C) { print("C") }

// if neither were defined, the version above for the 
// protocol P would be called

f(E())  // prints D

This prioritized overloading allows you to write more specialized functions for specific types. For example, suppose you want an overloaded version of contains for ClosedInterval that used the fact that you can do the check in constant rather than linear time using comparators.

Well, that sounds like a familiar concept – it’s polymorphism. But don’t get too carried away. It’s important to understand that:

Overloaded functions are chosen at compile time

In all the cases above, which function is called is determined statically not dynamically, at compile-time not run-time. This means it’s determined by the type of the variable not what the variable points to:

class C { }
class D: C { }

// function that takes the base class
func f(c: C) { print("C") }
// function that takes the child class
func f(d: D) { print("D") }

// the object x references is of type D,
// but x is of type C
let x: C = D()

// which function to call is determined by the
// type of x, and not what it points to
f(x)    // Prints "C" _not_ "D"

// the same goes for protocols...
protocol P { }
struct S: P { }

func f(s: S) { print("S") }
func f(p: P) { print("P") }

let p: P = S()

// despite p pointing to an object of type S,
// the version that takes a P will be called:
f(p)    // Prints "P" _not_ "S"

If instead you need run-time polymorphism – that is, you want the function to be picked based on what a variable points to and not what the type of the variable is – you should be using methods not functions:

class C {
    func f() { print("C") }

class D: C {
    override func f() { print("D") }

// function that takes the child class

// the object x references is of type D,
// but x is of type C:
let x: C = D()

// which method to call is determined by 
// what x points to, and not what type it is
x.f()    // Prints "D" _not_ "C"

The two approaches aren’t mutually exclusive, mind you. You could for example overload a function to take a particular protocol, checking for protocol conformance statically, but then invoke a method on that protocol to get dynamic behaviour.

The downside to that approach is that:

Functions that take Protocols can be ambiguous

With protocols, it’s possible to use multiple inheritance to generate ambiguous situations.

protocol P { }
protocol Q { }

struct S: P, Q { }
let s = S()

func f(p: P) { print("P") }
func f(p: Q) { print("Q") }

// error: argument could be either a P or a Q

// so you need to disambiguate, either:
f(s as P)  // prints P

// or:
let q: Q = S()
f(q)       // prints Q

// the same happens with classes vs protocols:
class C  { }
class D: C, P { }

func f(c: C) { print("C") }

// error: argument could be either a C or a P
// you must specify, either:
f(D() as P)
// or:
f(D() as C)

Defaulting to ClosedInterval for Integers

So, knowing now that a function that takes a struct will be chosen ahead of a function that takes a protocol, we should be able to write a version of the ... operator that takes a struct (Int), that will beat the current versions that take protocols (Comparable to create a ClosedInterval, and ForwardIndex to create a Range):

func ...(start: Int, end: Int) -> ClosedInterval<Int> {
    return ClosedInterval(start, end)

// x is now of type ClosedInterval
let x = 1...5

This is not very appealing though. If you pass in other integer types, you still get a Range:

let i: Int32 = 1, j: Int32 = 5

// r will be of type Range still:
let r = i...j

It would be much better to write a generic version that took an IntegerType.

And it still doesn’t explain why ranges are preferred to closed intervals. Comparable and ForwardIndex don’t inherit from each other. Why isn’t it ambiguous, as in our protocol multiple inheritance example above?

Well, because I was lying when I said the current implementations of ... took a protocol. They actually take generic arguments constrained by protocols. The next article will look at how generic versions of functions fit into the matching criteria.

Which function does Swift call? Part 1: Return Values

ClosedInterval is shy. You have to coax it out from behind its friend, Range.

// r will be of type Range<Int>
let r = 1...5

// if you want a ClosedInterval<Int>, you
// have to be explicit:
let integer_interval: ClosedInterval = 1...5

// if you use doubles though, you don’t need
// to declare the type explicitly.
// floatingpoint_interval is a ClosedInterval<Double>
let floatingpoint_interval = 1.0...5.0

Ever since Swift 1.0 beta 5, Range has supposed to be only for representing collection index ranges. If you’re not operating on indices, ClosedInterval is probably what you want. It has methods like contains, which determines in constant time if an interval contains a value. Range can only use the non-member contains algorithm, which will turn your range into a sequence and iterate over it – don’t accidentally put a loop in your loop!

But Range is not going quietly. If you use the ... operator with an integer, it elbows ClosedRange out the way and dashes onto the stage. Why? Because integers are forward indexes (as used by Array), and the Swift ... operator has 3 declarations:

func ...<T : Comparable>(start: T, end: T) -> ClosedInterval<T>

func ...<Pos : ForwardIndexType>(minimum: Pos, maximum: Pos) -> Range<Pos>

func ...<Pos : ForwardIndexType where Pos : Comparable>(start: Pos, end: Pos) -> Range<Pos>

When you write let r = 1...5, Swift calls the last one of these, and you get back a Range. To understand why, we need to run through the different ways Swift decides which overloaded function to call. There are a lot of them.

Let’s start with:

Differing Return Values

In Swift, you can’t declare the exact same function twice:

func f() {  }

// error: Invalid redeclaration of f()
func f() {  }

What you can do in Swift, unlike in some other languages, is define two versions of a function that differ only by their return type:

struct A { }
struct B { }

func f() -> A { return A() }

// this second f is fine, even though it only differs
// by what it returns:
func f() -> B { return B() } 

// note, typealiases are just aliases not different types,
// so you can't do this:
typealias L = A
// error: Invalid redeclaration of 'f()'
func f() -> L { return A() }

When calling these only-differing-by-return-value functions, you need to give Swift enough information at the call site for it to unambiguously determine which one to call:

// error: Ambiguous use of 'f'
let x = f()

// instead you must specify which return value you want:
let x: A = f()    // calls the A-returning version
                  // x is of type A

// or if you prefer this syntax:
let y = f() as B  // calls the B-returning version
                  // y is of type B

// or, maybe you're passing it in as the argument to a function:
func takesA(a: A) { }

// the A-returning version of f will be called

Finally, if you want declare a reference to a function f, you need to specify the full type of the function. Note, once you have assigned it, the reference is to a specific function. It doesn’t need further disambiguation:

// g will be a reference to the A-returning version
let g: ()->A = f

// h will be a reference to the B-returning version
let h = f as ()->B

// calling g doesn't need further info, it references 
// a specific f, and z will be of type A:
let z = g()

OK, so ... is a function that differs by return type – it returns either a ClosedInterval or a Range. By explicitly specifying the result needs to be a ClosedInterval, we can force Swift to call the function that returns one.

But if we don’t specify which ... explicitly, we don’t get an error about ambiguity as seen above. Instead, Swift picks the Range version by default. How come?

Because the different versions of ... also differ by the arguments they can take. In the next article, we’ll take a look at how that works.

Changes to the Swift Standard Library in 1.1 beta 2

Less than a week after the last beta was released, Swift 1.1 beta 2 is up. And yes, it’s officially Swift 1.1, as displayed by running swift -v from the command line.

Presumably we’re gearing up for a new GM alongside Yosemite, as there are almost no changes to the standard library in this release, much like when the GM was almost upon us for 6.0. Not surprising, since the Swift team had already confirmed on the dev forums that 6.1 was going to be a fairly small release.

The only material change are to the RawRepresentable protocol, and the _RawOptionSetType which inherits from it:

  • RawRepresentable’s Raw typealias is now RawValue.
  • Instead of a toRaw function, it now has a read-only rawValue property.
  • Instead of a fromRaw class function, it now defines an init? that takes a raw value.
  • _RawOptionSetType also now defines an init that takes a raw value, rather than a class function fromMask.

This matches the release notes, which state that enums construction from raw values have been changed to take advantage of the new failable initializers introduced in the last beta.

Interesting thing to note: while RawRepresentable has an init?(rawValue: RawValue) method, _RawOptionSetType has an init(rawValue: RawValue) method. This might seem odd at first – _RawOptionSetType inherits from RawRepresentable, shouldn’t they have the same kind of init? But since init is more restrictive than init?, it works, as an optional type can always be substituted with its non-optional equivalent. _RawOptionSetType is essentially restating RawRepresentable’s raw initializer as non-optional after all.

Here’s looking forward to a Swift 1.1 GM, and maybe after that on to 1.2?

Accidentally putting a loop in your loop

Joel Spolsky wrote a good article back in 2001 about knowing when the function you’re calling has linear complexity,1 and not accidentally putting a loop in your loop,2 getting quadratic complexity without realizing it. He was talking about C string algorithms like strlen and strcat, but it applies just as much to several Swift standard library functions.

When a function only has versions that take a sequence, like the seductively-useful contains, equal, min– and maxElement, it’s linear.3 Some depend on their input: countElements can be done in constant time if you give it a collection with a random-access index, but linear if not. Same with distance and advance index operations, which is why extending String to support random-access indexing using them is probably a bad idea. Be careful, not everything that could be optimized may have been. For example, ClosedInterval.contains is presumably O(1) but there doesn’t appear to be an optimized overload for the non-member contains, which only has versions that take a sequence.

The Swift team have helpfully put the complexity of certain functions in the documentation. Array’s reserveCapacity, insert, and replaceRange are O(N).

And so is… removeAtIndex. In a previous article, I mentioned the following code to remove all occurrences of a given value from an array has an efficiency problem:

func remove
    <C: RangeReplaceableCollectionType,
     E: Equatable
     where C.Generator.Element == E>
    (inout collection: C, value: E) {
        var idx = collection.startIndex
        while idx != collection.endIndex {
            if collection[idx] == value {
            else {

The documentation for removeAtIndex says: 4

Remove and return the element at the given index. Worst case complexity:
O(N). Requires: index < count

That is, the worst-case time it takes to remove an element increases in linear proportion to the length of the collection. That's not surprising – if you remove an element of an array, you have to shuffle each element after it down one. The larger the collection the more things to shuffle. Maybe your element is near the end, maybe your collection is a linked list that can remove elements in O(1), maybe it’s magic and has all sorts of cool optimizations – hence O(N) is the worst case. But still, it’s probably not best to call it within another loop.

Here, it shouldn't be necessary. We're already iterating over the collection, so ought to be able to combine the deletion and shuffling down together as one operation. Here's a new version of remove that does this, modelled on the C++ STL equivalent:

(incidentally, it also removes the need for questionable assumptions about how indexes behave when you remove elements, the subject of the previous article)

func remove
    <C: protocol<RangeReplaceableCollectionType,
     E: Equatable
     where C.Generator.Element == E>
    (inout col: C, value: E) {
        // find the first entry to remove
        if var advance = find(col, value) {
            // advance points to next element to test,
            // rear points to where to copy it to
            // if it's a keeper
            var rear = advance++
            while advance != col.endIndex {
                if col[advance] != value {
                    col[rear] = col[advance]

This version breaks the removal into multiple steps. First, it uses find to locate the first entry to remove (and if it doesn’t find one, does nothing more). Next, one by one it moves the subsequent elements down on top of that entry. When it encounters more entries to remove, it skips over them (i.e. it increments advance, the index of entries to examine and maybe copy, but not rear, the index of where to copy to, and they aren’t copied).

Finally, when all this is done, the collection should have all the non-removed entries at the front, and some meaningless garbage at the end. This end section is the length of the number of removed entries (though it doesn‘t contain the removed entries – entries were copied, not swapped). This is trimmed off by a call to removeRange, which is also O(N). But that’s fine – two O(N) algorithms in series is still O(N).

By the way, in this last step it differs from the C++ STL version which, in a quality bit of user-unfriendliness, requires the caller to do the final remove step, instead leaving the collection with the garbage still at the end. There‘s good reasons for this (because iterators), but it’s a nasty gotcha for newbies. I’d chalk this one up as a win for Swift’s approach to generic collection algorithms. 5

Note that for this to work, the collection also needs to support the MutableCollectionType protocol, because that’s where the assignable version of subscript lives for some reason.6 In fact, that’s all MutableCollectionType adds. By the way, this whole optimization is based on the assumption that the assignment version of subscript runs in constant time. It should do, right? Copying a value into a position in an array shouldn’t affect the rest of the array, so it shouldn’t matter how long it is.

A quick test with a reasonably large array shows that this new version of remove does indeed run quicker (and more consistently) than our first version. Yay.

Then you try and use it on a string, and your celebration is short lived. String doesn’t implement MutableCollectionType. Huh, what’s that about?

What this doesn‘t mean is that String is immutable. It’s totally mutable. Mutating is what RangeReplaceableCollectionType is all about. This is a chance to make an important if maybe obvious point: just because your function takes an object via a protocol that doesn’t allow mutation doesn‘t mean that object is immutable. It just means you can‘t mutate it in your function.

My guess for why strings don‘t support MutableCollectionType? Because that assumption above, about subscript assignment being O(1), doesn’t hold. Remember, individual elements of Swift strings are of variable length. What if you replaced a longer character with a shorter one? We’d be back to square one, having to shovel all the subsequent characters down to fill in the gap. Worse, what if you replaced a shorter entry with a longer one? The string would get bigger, maybe even need relocating to a newly allocated chunk of memory.

This would be another example of signalling more from protocols than just what functions are supported. They can tell you about fundamental properties of the object. Perhaps MutableCollectionType is like MutableInConstantTimeCollectionType. Course, on the other hand, I could be reading waaay too much into String not implementing it. It could just be an oversight – only time (or one of the Swift devs) will tell.

String does support replaceRange as an alternative to subscript assign. But its complexity is, you guessed it, O(N). And after crowbarring it into the second algorithm above, tests suggest it’s no faster than the removeAtIndex version.7 So if you really have a burning desire to remove some characters from a huge string, maybe find another way. Perhaps you can trade some space for that time.

  1. That wikipedia entry on complexity, like so many wikipedia entries on mathematical topics, is pretty beginner-unfriendly. If anyone has a good beginner’s guide link I could replace it with, let me know. An (admittedly cursory) google search doesn’t turn much up. 
  2. I’d have called this post “Yo, dawg” but then I’ve already done that once. 
  3. Unless it does something like return the first element in the sequence, obvs. Hmmm, maybe I should be less paranoid about people finding errors in my posts. 
  4. Actually it doesn’t, not on the protocol version anyway. The stand-alone function version (that takes that same protocol) does though, so I’m taking the liberty of giving that instead. 
  5. It‘s not all wins, mind. The STL’s iterator-based functions are much easier to use with subranges of collections. Don‘t get me started on slices… 
  6. Wait for it… 
  7. though this is possibly due to my lack of deftness with a crowbar. 

Changes to the Swift Standard Library in Xcode 6.1

Congratulations to the Swift team on releasing a 1.0 GM! Unsurprisingly, there were no changes that I could spot1 between beta 7 and the GM standard libraries.

But as they said in their blog post, “Swift will continue to advance with new features, improved performance, and refined syntax. In fact, you can expect a few improvements to come in Xcode 6.1 in time for the Yosemite launch.” As such, the first beta of Xcode 6.12 saw more changes to the standard library than we saw in the pre-1.0 beta, and here they are:

  • As flagged in the release notes, all the integer types have acquired truncatingBitPattern initializers for each of their larger counterparts.
  • The functions join, reduce, sort and sorted have acquired descriptions in the various places they’re implemented.
  • AssertString and StaticString are now Printable and DebugPrintable
  • HeapBufferStorage no longer inherits from HeapBufferStorageBase, which is gone.
  • The Process instance is now declared with let rather than var
  • StrideThrough or StrideTo are now Reflectable
  • StaticString now has a utf8Start instead of start (which still returns an UnsafePointer). It also has a withUTF8Buffer method for using the underlying raw buffer, a unicodeScalar get property.
  • String has lost its compare(other: String.UnicodeScalarView) method.
  • String also now implements several methods extending StringInterpolationConvertible – for a variety of different built-in types.
  • Second versions of assertionFailure and fatalError now take a generic AssertStringType instead of StaticString.
  • equal and startsWith‘s predicate functions have been renamed isEquivalent.
  • maxElement and minElement‘s input parameter has been renamed elements.
  • The toString function now says it returns the result of printing, not debugPrinting, an object.

There’s a new unsafeAddressOf function that takes an AnyObject. Apparently there’s “not much you can do with this other than use it to identify the object”.

There is a new protocol, UnicodeScalarLiteralConvertible, that follows the now-familiar literal converter pattern: a ThingType typealias, a convertFromThing class function, and a library-level typealias for ThingType for the standard type for these literals to convert into, in this case a String.

The ExtendedGraphemeClusterLiteralConvertible protocol now inherits this protocol, so the objects that implement it (Character, String, AssertString and StaticString) also now implement convertFromUnicodeScalarLiteral. And the UnicodeScalar struct now implements UnicodeScalarLiteralConvertible instead of ExtendedGraphemeClusterLiteralConvertible.

Here’s looking forward to more enhancements as Swift continues to develop.

  1. Unless there’s one hiding in those pesky re-ordered operator overloads… 
  2. Does this mean this is Swift 1.1? 

Changes in the Swift Standard Library in Beta 7

There aren’t any.

Well, actually there’s one:

  • The ImplicitlyUnwrappedOptional type, which ceased to be of BooleanType in beta 6, no longer has the associated vestigial boolValue property.

Ok, Ok there are a couple more:

  • The comparison function taken by non-member sort, sorted and partition is now labelled isOrderedBefore (matching the member versions). Not that it’s an external parameter, so no code change needed.
  • Further enhancements to some function documentation comments (for example min() now has a description).

I think… that’s it. I have to admit, I don’t diff all the operators each time, as they seem to constantly reorder with each beta. That’s how I missed that, between beta 3 and beta 4, you stopped being able to use === to determine if two arrays referenced the same underlying storage. Shame on me!

There’s one operator that hasn’t changed. Despite what the release notes say, you still seem to be able to use + to concatenate Characters:

let c1: Character = "a"
let c2: Character = "b"
let s = c1 + c2
// s is now the String "ab"

…but presumably it’s not long for this world. This is in keeping with the trend of having + only work between two collection types, not between collection types and their contained types.

I guess this stabilization of the Swift library is in readyness for the Swift 1.0 release, which is pretty great news. The interesting question is, how will the library keep evolving post-1.0?