Why is indexingIterator.next() using dynamic dispatch?

struct SchoolIterator: IteratorProtocol { private var schoolList: School var idx = 0 init(_ school: School) { self.schoolList = school } mutating func next() -> String? { defer { idx += 1 } guard schoolList.count-1 >= idx else { return nil } return schoolList[idx] } } struct School: Sequence { fileprivate var list = Array(repeating: "school", count: 100000) var count: Int { return list.count } subscript(_ idx: Int ) -> String? { guard idx <= count-1 else { return nil } return list[idx] } func makeIterator() -> SchoolIterator { return SchoolIterator(self) } } var schools = School() for school in schools { print(school) }

Your for loop translates to:

var schools = School()
var iterator = schools.makeIterator()
while let school = iterator.next() {
    print(school)
}

Notice how nothing here is a protocol. schools is of type School, iterator is of type SchoolIterator, everything that next does (like accessing schoolList.count, or the subscript of schoolList) deals with structs too. The key point is that the compiler can figure out exactly which member you mean, because its (compile-time) type is a struct. There is no need to look up witness tables.

Compare that to, e.g.

func f<S: Sequence>(_ s: S) {
    for thing in s {
        ...
    }
/*
    var iterator: S.Iterator = s.makeIterator()
    while let thing = iterator.next() {
        ...
    }
*/
}

f(School())
f(1..<100)

How would the compiler dispatch the calls to iterator.next()? I've deliberately added the type annotation to make it clear what's happening - this time, the compiler doesn't know which next you mean. Is it IndexingIterator.next()? Or SchoolIterator.next()? Or SomeOtherIterator.next()? Keep in mind that I can call f with any kind of Sequence! That's why it needs to look up the witness table of the actual type of S.Iterator at runtime - it is impossible to figure out which next to call.

As for why for i in 0..<100 uses dynamic dispatch, well, on first sight, there seems to be all structs:

let range: Range<Int> = 0..<100
var iterator: IndexingIterator<Range<Int>> = range.makeIterator()
while let i = iterator.next() {
    ...
}

However, iterator.next actually does something like this:

public mutating func next() -> Elements.Element? { if _position == _elements.endIndex { return nil } let element = _elements[_position] _elements.formIndex(after: &_position) return element }

_elements is defined like this:

public struct IndexingIterator<Elements: Collection> {
  
  internal let _elements: Elements

_elements could be any kind of Collection, so again, we don't know which member _elements[_position] or _elements.formIndex refers to at compile time. Is it Array.formIndex? Or Set.formIndex? We only know at runtime, when we know what Elements is.

Recommended topics

Hot tags