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?

Joel Spolsky wrote a good article back in 2001 about knowing when the function you’re calling has linear complexity,¹ and not accidentally putting a loop in your loop,² 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.³ 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 {
                collection.removeAtIndex(idx)
            }
            else {
                ++idx
            }
        }
}

The documentation for removeAtIndex says: ⁴

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,
                 MutableCollectionType>,
     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]
                    ++rear
                }
                ++advance
            }
            col.removeRange(rear..<col.endIndex)
        }
}

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. ⁵

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.⁶ 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.⁷ 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.

Congratulations to the Swift team on releasing a 1.0 GM! Unsurprisingly, there were no changes that I could spot¹ 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.1² 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.

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?

I managed to catch a copy of beta 6 before it was pulled. Though not a copy of the release notes, so apologies if I duplicate some items (and hopefully don’t misspeak about stuff better explained in them!). On the assumption the binaries will be the same except re-signed, here’s a rundown of the changes to the standard library. (edit: they were)

Feels like Swift might be approaching the 1.0 home-stretch, with the focus moving to stability and Objective-C API interfacing. Nevertheless, plenty of changes to the Swift standard library in beta 6.

By far the largest swathe of changes are additional comments on existing types and functions, which are definitely worth a read and clarify several things. For example, a comment above Comparable makes it clear you only need to define < to be comparable, despite Comparable defining the comparators that aren't <.

Some small bits and pieces:

• The ?? operator has been updated to include a version to explicitly handle both the LHS and RHS being of the same optional type. I've updated my post with a comment, but it's still worth reading as a case study if you're writing a similar function.
• Array now has an init that takes a _CocoaArrayType, as well as a noCopy flag, only to be set if the source array cannot be further mutated.
• AutoreleasingUnsafeMutablePointer is no longer a BooleanType, so no longer has a boolValue property
• Bit.Zero and Bit.One are now capitalized (don't say we don't pay attention to detail here!)
• The Bool constructor, which previously took a parameter of BooleanType (which worked because BooleanType has no associated type requirements unlike, say, IntegerType), now takes a generic parameter T that must be of BooleanType. Interesting question to ponder is how this changes the function.
• COpaquePointer has new constructors from raw memory addresses (these are described as “fundamentally unsafe”, you have been warned)
• Character is now Comparable
• The value properties of Float, Float80 and Double (which were of Builtin.FPIEEExx) are gone.
• The FloatingPointType protocol now includes constructors from all the built-in integer types.
• ImplicitlyUnwrappedOptional no longer conforms to BooleanType, though it still has its boolValue property (I should avoid using that if I were you).
• Optional no longer has a hasValue property. You should just use != nil
• RawOptionSetType no longer implements BooleanType and Equatable but instead implements BitwiseOperationsType
• The FIXMEs about how StrideThrough and StrideTo should be collections not sequences are gone. They're still sequences.
• UnicodeScalarView is now reflectable.
• String has a new extend method that takes another string. This is in addition to the existing extend that takes a sequence of characters.
• It also has an append function that takes a UnicodeScalar.
• String is also now Comparable.
• Strings unicodeScalars property is now writeable.
• UnicodeScalar now has an init for UInt16 and UInt8 in addition to UInt32
• UnsafeMutableBufferPointer has several changes. First, it is heavily commented. It's now a RandomAccessIndexType (so you can calculate distances between them, and advance them). And its constructors have been changed to be consistent with COpaquePointer.
• _ExtensibleCollectionType has added an append function that appends a single element (all the implementors already support this)
• _RawOptionSetType (and thus RawOptionSetType) is now Equatable.
• contains now has a version that takes an equatable element rather than a predicate.
• sorted now takes any sequence, which is way less restrictive as before it required a mutable random-access collection.
• startsWith now has a version that takes a comparison predicate (but like equal requires both sequences to contain the same type, even if the predicate could handle two different types).

transcode, which I think officially has the longest function signature in the whole Swift library, got a teeny bit shorter as it now returns a (still a bit odd-looking) 1-tuple containing a Bool, rather than a 1-tuple containing a Bool labelled hadError. Oh, by the way, you're not allowed to return 1-tuples with labels as of beta 6.

There is a new AssertString type, which has a lower precedence for overloading purposes than StaticString. How this is achieved is interesting, and a demonstration of how there are still inheritance hierarchies with structs: AssertString implements a new AssertStringType protocol. StaticString also now implements a new protocol, StaticStringType. StaticStringType inherits from AssertStringType. This means StaticString is more specific than AssertString and will therefore “win” in choices for which overload to pick (in the same way a function taking a CollectionType wins over SequenceType if an object supports it, or RandomAccessIndexType wins over ForwardIndexType). The protocols StaticString previously implemented have moved to AssertStringType

There is a family of a new kind of assertion function, precondition. The signatures are very similar to that of assert. The comments suggest precondition is a little stronger – they will still stop program execution even if assertions are turned off. Only with -Ounchecked will they not check the condition. There's also a @noreturn preconditionFailure function that doesn't check anything, just stops execution immediately.

Various new comments in the Swift library suggest use of these new preconditions. For example, a comment above GeneratorType.next suggests calling preconditionFailure if called a second time after nil has already been returned.

There's a new protocol, RangeReplaceableCollectionType, that defines several new operations on collections such as removing or replacing ranges, as well as insert (insert an element into the middle of a collection), and splice (insert a collection into the middle of the collection).

String implements this new protocol. Interestingly, Array (alongside ContiguousArray and Slice) does not appear to, though it does support all the methods (including new splice and removeRange functions) and if you write a generic function that takes a RangeReplaceableCollectionType, you can pass an Array into it. Declared somewhere more private I guess? Unless I'm missing a bit of indirection somewhere. If you spot it, let me know on twitter.

Following a familiar pattern, several of these new functions, such as slice and the remove operations, are also availabe as non-member functions as well.

Finally, _BridgedToObjectiveCType and _ConditionallyBridgedToObjectiveCType appear to have coalesced into _ObjectiveCBridgeable, but as ever I'll steer clear of discussing bridging topics.