struct Set { var first { get } }

Welcome to Swift: Shuffle All.

While some of us may have fond memories of these friendly words greeting users in iOS 7’s Music app, these days we must turn elsewhere to appreciate a random ordering of collections.

Swift: Shuffle All is intended as one option to satisfy this need by bringing together Nate Cook’s SwiftDoc.org and a source of random indexes (RandomAccessIndexType anyone?) as a means to explore Swift’s standard library and built-ins in a more serendipitous fashion.

Rather than hoping for a conference talk to mention that API you always wanted to know about:

I learned so much at @dotSwift. Can't believe I've overlooked CAReplicatorLayer all these years. Made new friends. If you have a chance, go!

— Rob Napier (@cocoaphony) January 30, 2016

entropy may well do a better job of surfacing it before you need it.

While so far no well-defined method exists for choosing subject matter from SwiftDoc.org, Chris kindly provided inspiration for this initial exploration:

It's kind of weird that Swift's Set has "no defined ordering" but implements first et al by virtue of adhering to CollectionType.

— Chris (@cdntr) February 2, 2016

Investigating the protocol hierarchy for Set, or rather: Set<Element : Hashable> is revealing. Conforming to CollectionType places several requirements on Set, in particular providing a Generator for interation and Index for representing collection indices.

CollectionType thus also requires that a Set provides an instance variable defined as:

So far, so good. However this doesn’t tell us how first element is determined when iterating.

On the other hand, we now have a place to go and find these details: the Swift source at https://github.com/apple/swift An initial search for struct Set doesn’t yield any results in Swift source files, however a HashedCollections.swift.gyb file looks promising.

Further investigation reveals these are parsed by a tool included in the repository dubbed Generate Your Boilerplate. Clearly some tooling work has been done to ease Swift development.

Back to HashedCollections.swift.gyb. Running this through

utils/gyb stdlib/public/core/HashedCollections.swift.gyb > HashedCollections.swift

inflates a somewhat larger Swift source file.

This seems to contain two rather similar clusters of types, one for Dictionaries and another for Sets. In fact, much of this was investigated in Ankit Aggarwal’s Exploring Swift Dictionary Implementation(Although they don’t seem to have shown their hand about where this information was gleaned from.)

Both Dictionary and Set share their HashedContainerStorageHeader while a Set consists only of keys as opposed to a Dictionary which must store keys and values.

Since buckets for keys are looked up by their hashValue, this suggests a Set’s first object will depend on its hashValue. Well, almost. As the hashValue is squeezed to fit the header bitmap which is sized based on the Set’s capacity, a sufficiently large capacity for the range of hashValues must be choosen to allow this sorting to take place.

Have a look at this Playground page to experiment with this behaviour. Simply drag the page into an existing playground to get started.