How do I actually use Iterable?

I found plenty of articles explaining its design, but no actual end-to-end code. I've tried:

struct MyBorrowingIterator: BorrowingIteratorProtocol {
  @_lifetime(&self)  // '@_lifetime' attribute is only valid when experimental feature Lifetimes is enabled
  mutating func nextSpan(maxCount: Int) throws(Never) -> Span<UInt8> {  // A mutating method cannot return a ~Escapable result
    return .init()
  }
}

Is there a full guide to creating a type? What do I need in the "Package.swift" file? It has "ApproachableConcurrency" and "Lifetimes".

It took me two full days to successfully wrap my head, and the code, around how to actually use Iterable. You only really need to use it if you work with noncopyable types and noncopyable array storage, and sometimes you can even get away without enabling the experimental Lifetimes feature (but you most likely will need to eventually; its only mentioned once in the proposal). ApproachableConcurrency is something different and isn't related to iterable (and idk what the feature actually does).

Moreover, I successfully adopted Iterable in my league scheduling engine a month ago which gave it a huge performance improvement over using a regular Array and ContiguousArray. Here is that real-world usage (but stripped down version) of it being adopted in my BitSetHeap implementation (feel free to steal it :grinning_face_with_smiling_eyes:):

/// A rigid (doesn't grow), heap-backed, noncopyable regular bit set container.
/// - NOTE: keep in mind every bucket contains only up-to 64 unique elements (each bit represents 1 unique element).
struct BitSetHeap: Sendable, Iterable, ~Copyable {
    typealias Element = UInt32
    typealias Failure = Never
    typealias Storage = UniqueArray<UInt64>

    var storage:Storage

    init(minimumCapacity: Int) {
        assert(minimumCapacity >= 0)
        let buckets = ((minimumCapacity-1) / 64) + 1
        storage = .Swift::init(repeating: 0, count: buckets)
    }
}

// MARK: iterator
extension BitSetHeap {
    func makeBorrowingIterator() -> BorrowingIterator {
        .init(ref: Ref(storage))
    }

    struct BorrowingIterator: BorrowingIteratorProtocol, ~Copyable, ~Escapable {

        private var ref:Ref<Storage>
        private var converter:BitSetHeapConversion
        private var bucket:Int

        @_lifetime(copy ref)
        init(
            ref: Ref<Storage>
        ) {
            self.ref = ref
            converter = .init(defaultValue: 0)
            bucket = 0
        }

        @_lifetime(&self)
        mutating func nextSpan(maxCount: Int) -> Span<Element> {
            guard bucket < ref.value.count else { return .init() }
            converter.update(offset: Element(bucket) * 64, newValue: ref.value[bucket])
            bucket += 1
            guard converter.count > 0 else { return nextSpan(maxCount: maxCount) }
            return converter.span
        }
    }
}
BitSetHeapConversion
/// Helper that converts a `UInt64`'s populated bit indexes into a span of `Element`.
struct BitSetHeapConversion: Sendable, ~Copyable {
    typealias Element = UInt32
    private var array:[64 of Element]
    private(set) var count:Int

    init(
        defaultValue: Element
    ) {
        array = .init(repeating: defaultValue)
        count = 0
    }

    /// - Complexity: O(1).
    var span: Span<Element> {
        array.span.extracting(first: count)
    }

    mutating func update(offset: Element, newValue: UInt64) {
        count = 0
        var temp:UInt64 = newValue
        while temp != 0 {
            let index = UInt8(truncatingIfNeeded: temp.trailingZeroBitCount)
            array[count] = offset + Element(index)
            count &+= 1
            temp &= (temp &- 1)
        }
    }
}

Sidenote: I haven't read any articles or watched any videos regarding adopting Iterable or BorrowingIteratorProtocol and I started out using BorrowingIteratorAdapter before getting it to actually work. I got the code working by basically brute-forcing different combinations of syntax (I remember that ~Escapable was a bit tricky to fit properly). Even then I don't really think my usage of the lifetime annotations to be that correct or optimal (lets be real here for a second: we are using an underscored annotation afterall) and even had to use Ref to glue it all together.

4 Likes

Here's a full example:

struct HexOutputOctetSerializer<Base: RandomAccessCollection<UInt8>> {
  let direction: Direction
  let isFirstSegment: Bool
  var elements: Base.SubSequence.Iterator
  let suffix: HexOutputOctetSuffix
  var stage: HexOutputOctetStages

  var oneByte = InlineArray<1, UInt8>(repeating: 0)
  var twoBytes = InlineArray<2, UInt8>(repeating: 0)
  var threeBytes = InlineArray<3, UInt8>(repeating: 0)

  init(direction: Direction, isFirstSegment: Bool, source: Base, sourceEndIndex: Base.Index, isLastSegment: Bool) {
    self.direction = direction
    self.isFirstSegment = isFirstSegment
    if sourceEndIndex < source.endIndex {
      self.suffix = .continuing
    } else if isLastSegment {
      self.suffix = .completeFinish
    } else {
      self.suffix = .nonFinalFinish
    }
    self.elements = source[..<sourceEndIndex].makeIterator()
    self.stage = .prefixArrow
  }
}

extension HexOutputOctetSerializer: BorrowingIteratorProtocol {
  mutating func nextSpan(maxCount: Int) throws(Never) -> Span<UInt8> { // A mutating method cannot return a ~Escapable result
    switch self.stage {
      case .prefixArrow:
        self.threeBytes = self.direction.utf8
        self.stage = .prefixSpace
        return self.threeBytes.span
      case .prefixSpace:
        self.oneByte = [0x20]
        self.stage = .prefixOpener
        return self.oneByte.span
      case .prefixOpener:
        defer { self.stage = .firstElement }
        if isFirstSegment {
          self.oneByte = leftBracket
          return self.oneByte.span
        } else {
          self.threeBytes = midlineEllipsis
          return self.threeBytes.span
        }
      case .firstElement:
        guard let firstValue = self.elements.next() else {
          self.stage = .suffixCloser
          return self.nextSpan(maxCount: maxCount)
        }

        self.twoBytes = firstValue.asciiValueOctetString
        self.stage = .subsequentElement
        return self.twoBytes.span
      case .subsequentElement:
        guard let latestValue = self.elements.next() else {
          self.stage = .suffixCloser
          fallthrough
        }

        let digitHexOutput = latestValue.asciiValueOctetString
        self.threeBytes[0] = 0x20
        self.threeBytes[1] = digitHexOutput[0]
        self.threeBytes[2] = digitHexOutput[1]
        return self.threeBytes.span
      case .suffixCloser:
        defer { self.stage = .done }
        switch self.suffix {
          case .continuing:
            self.threeBytes = midlineEllipsis
            return self.threeBytes.span
          case .nonFinalFinish:
            self.oneByte = rightBracket
            return self.oneByte.span
          case .completeFinish:
            self.threeBytes = rightMathWhiteBracket
            return self.threeBytes.span
        }
      case .done:
        return .init()
    }
  }
}

Most of the unknown types are enum types. The unknown variables are InlineArray objects. The compiler currently doesn't accept type-static objects for spanning, just actual globals.

I'm still getting the same error. Adding ~Escapable to the borrowing-iterator just adds the same error message to the initializer.

Try adding the @_lifetime(&self) annotation to your nextSpan(maxCount:) (and you will need to enable the Lifetimes feature in your target).