Type-Erased Wrappers in Swift

by Realm
on Aug 6 2015

There are situations where we’d like to treat associated types on protocols as generics, but the compiler refuses. Using type-erasure, there is a way to perform this transformation. In this post, Samuel E. Giddins walks us through the process of – and the reasoning behind – turning associated types into generic constraints in Swift.

Protocol-Oriented Programming is the way to go in Swift, right? I mean, it even got a WWDC session for crying out loud! Protocols are awesome. They let you define interfaces, and allow you to ignore how those interfaces are actually implemented (and what is actually implementing them).

Take the SequenceType protocol from the Swift standard library. It defines what it means for a type to be enumerable, so every type that conforms to SequenceType can be used in a for-in statement. With Swift 2.0, we enter a whole new level of usefulness thanks to default protocol implementations – every type conforming to SequenceType also gets a map method, for example.

This lets you write a function that just takes a SequenceType parameter, and be agnostic to the actual class or struct or enum that’s passed in.

func printAll<S: SequenceType where S.Generator.Element: Printable>(printables: S) {
  for printable in printables {
    print(printable)
  }
}

// printAll(Set(["a", "b", "c"]))
// printAll(["d", "e", "f"])
// printAll("ghi".characters)

Our printAll function doesn’t need to care about how the printables get enumerated over, only that they can be. This lets us write abstractions, where we can easily swap out different implementations of things that behave similarly.

So, this all works great when you’re writing functions and methods, but what about when you’re writing a class or struct, and want to be able to swap out different collections to power your table view?

struct TableViewController {
  var items: CollectionType<T>
  // error: cannot specialize non-generic type 'CollectionType'
  // error: protocol 'CollectionType' can only be used as a generic constraint because it has Self or associated type requirements
}

Oops. As the error messages say, protocols that have Self or associated type requirements are special. They can’t be used as properties, only as generic constraints, either on a type or function. But we want the sort of functionality this code would intuitively give us – letting us treat associated types on protocols as generics.

It turns out there’s a fancy term for doing just this – turning associated types into generic constraints – and it’s called type erasure. The Swift standard library already has a few type-erased wrappers, such as AnySequence and AnyGenerator.

If we take a look at the documentation for AnySequence, we’ll probably be left wanting some more information, particularly if we’re interested in implementing type-erased wrappers for our own protocols.

struct AnySequence { ... }

A type-erased sequence.

Forwards operations to an arbitrary underlying sequence having the same Element type, hiding the specifics of the underlying SequenceType.

See Also: AnyGenerator.

That’s exactly what we want! It even has an initializer, defined as init<S : SequenceType where S.Generator.Element == Element>(_ base: S) to turn our SequenceType of T into an AnySequence of T. But how?

It took me a few hours of struggling, and some key insights from a colleague, but eventually the elegance of the implementation shone through. Before we dive into that, though, let’s walk through some of the building blocks we’ll need to employ:

  • fatalError(): used to plug any hole in type signatures
  • Swift classes are polymorphic
  • You can assign an instance of a subclass to a property declared to hold the superclass

We want to end up with the following interface:

final class AnySequence<Element>: SequenceType {
    func generate() -> AnyGenerator<Element>
    func underestimateCount() -> Int
    init<S: SequenceType where S.Generator.Element == Element>(_ base: S)
}

This is a class that can be initialized with any SequenceType, it conforms to the SequenceType protocol itself, and its Generator.Element is the same as base’s. (There’s a reason we’ve written it as a class, which I’ll explain later. The other two methods from SequenceType, map and filter, have been left out for the sake of brevity.)

To start out, we’re going to write a small class that also conforms to SequenceType and is also generic over the Element we want:

class _AnySequenceBoxBase<Element>: SequenceType {
  func generate() -> AnyGenerator<Element> {
    fatalError()
  }
  func underestimateCount() -> Int {
    fatalError()
  }
}

“But wait!” you probably want to say, “that doesn’t really conform to SequenceType!” It does. This is using the same fatalError trick I mentioned earlier, to gloss over the holes in the SequenceType type signatures we can’t possibly know how to fill.

Returning to our AnySequence, we’ll probably want to add a property declaration to hold an instance of this BoxBase, private let box: _AnySequenceBoxBase<Element>. So far, so good – no complaints from the compiler.

Next, we subclass _AnySequenceBoxBase (this is probably pretty predictable, since its name includes Base). Let’s name this subclass _AnySequenceBox:

class _AnySequenceBox<Sequence: SequenceType>: _AnySequenceBoxBase<Sequence.Generator.Element> {}

What? That looks crazy! We’re subclassing that base class that just fatalErrors everywhere, and we’re introducing a new generic and not using the existing one… Let’s try and break this down.

The most important thing to notice about this class declaration is that _AnySequenceBox is generic over a particular SequenceType implementation. In fact, it’s generic over the very type that our AnySequence wrapper is erasing. It’s also a subclass of _AnySequenceBoxBase, with the base’s generic element being that of the erased type’s Generator.Element. This is the point of translation from our associated type protocol into the world of generics. The rest of the implementation for AnySequence is basically just boilerplate (albeit a vast quantity thereof).

But first, let’s finish up _AnySequenceBox:

let base: Sequence
init(_ base: Sequence) {
  self.base = base
}
override func generate() -> AnyGenerator<Element> {
  return base.generate()
}
override func underestimateCount() -> Int {
  return base.underestimateCount()
}

The only interesting bit to note here is that generate returns AnyGenerator instead of Sequence.Generator, and this is because we need to override the method from the base class, and the base class obviously has no knowledge of the concrete generators our contained sequences will be using. This demonstrates that type erasure has a cascading effect – every method that returns a type that depends on Self will have to return the type-erased wrapper for that protocol.

Finally, we can fill in the implementation for AnySequence itself:

final class AnySequence<Element>: SequenceType {
  typealias Element = Sequence.Generator.Element
  private let box: _AnySequenceBoxBase<Element>
    func generate() -> AnyGenerator<Element> {
      return anyGenerator(box.generate())
    }
    func underestimateCount() -> Int {
      return box.underestimateCount()
    }
    init<S: SequenceType where S.Generator.Element == Element>(_ base: S) {
      self.box = _AnySequenceBox(base)
    }
}

Yes, we’ve implemented the methods of SequenceType three times. And you’d need to do this again for every protocol you wish to provide a type-erased wrapper for. It’s rather a lot of code to write, but doing this work will make your protocols feel more like first class citizens. I wish the Swift compiler would do this work for us automatically when we write the naïve code (let property: Protocol<Element>), but in the meantime, we can resort to manually writing these wrappers.

Now, you may be wondering why AnySequence itself is a final class rather than a struct, and I have some rather bad news on this front: we can’t write our type-erased wrappers to have value semantics at the moment. ( can’t either, don’t worry; Swift.AnySequence is also a reference type). This is because we’d need the very type information we’ve erased in order to copy-on-write the box (we’d need to create a new _AnySequenceBox, which is generic on the concrete sequence type, which is precisely what we’re type-erasing).

Type erasure is pretty cool, and I hope you’ve enjoyed this little exposition into how to implement it in Swift. If you want a peek at how this works for a much larger protocol, you can see how we’ve been implementing this for our RealmCollectionType in a work-in-progress pull request. You can also download this implementation of AnySequence as a playground that you can play around with, and the standard library’s (internal) interface is available by exploring via :type lookup AnySequence in the Swift REPL.



Featured News

See more news