Variadic type-safe eager cartesian product in Swift 6

cartesian.swift

func liftOptional<each Ts>(_ values: repeat (each Ts)?) -> (repeat each Ts)? {
    for value in repeat each values {
        if value == nil { return nil }
    }
    return (repeat (each values)!)
}

struct PartialResult<each Element> {
    var contents: (repeat (each Element)?)

    init(_ contents: repeat (each Element)?) {
        self.contents = (repeat each contents)
    }

    init() {
        func chooseNil<T, U>(_: U) -> T? {
            return nil
        }

        self.contents = (repeat chooseNil((each Element).self))
    }

    func tryPack() -> (repeat each Element)? {
        return liftOptional(repeat each contents)
    }

    var count: Int {
        var count = 0
        for case _? in repeat each contents {
            count += 1
        }
        return count
    }

    func combined(with partialTuple: repeat (each Element)?) -> Self {

        func doCombine<T>(_ contents: T?, _ partialTuple: T?) -> T? {
            switch (contents, partialTuple) {
            case (_?, _?):
                preconditionFailure("Cannot combine two non-nil values")
            case let (contents?, nil):
                return contents
            case let (nil, partialTuple?):
                return partialTuple
            case (nil, nil):
                return nil
            }
        }

        return .init(repeat doCombine(each contents, each partialTuple))
    }
}

typealias IterSeqPair<each Seq: Sequence> = (
    repeat (sequence: (each Seq), iterator: (each Seq).Iterator?)
)

// This is the entrypoint
func carteseanProduct<each T: Sequence>(_ sequence: repeat each T) -> [(repeat (each T).Element)] {
    var result: [(repeat (each T).Element)] = []

    _ = reccursionStep(
        partialResult: .init(),
        out: &result,
        iterSeqPair: (repeat ((each sequence), (each sequence).makeIterator()))
    )
    return result
}

func reccursionStep<each Seq: Sequence>(
    partialResult: PartialResult<repeat (each Seq).Element>,
    out: inout [(repeat (each Seq).Element)],
    iterSeqPair: IterSeqPair<repeat each Seq>
) -> IterSeqPair<repeat each Seq> {
    if let completeEntry = partialResult.tryPack() {
        out.append(completeEntry)
        return iterSeqPair
    }

    var iterSeqPair = iterSeqPair
    while true {
        let (partialAdvance, nextIterSeqPair) = advanceParticularIter(
            (repeat each iterSeqPair), at: partialResult.count)
        guard hasElement(repeat each partialAdvance) else { return nextIterSeqPair }
        iterSeqPair = reccursionStep(
            partialResult: partialResult.combined(with: repeat each partialAdvance),
            out: &out,
            iterSeqPair: (repeat each nextIterSeqPair)
        )
    }
}

func hasElement<each T>(_ value: repeat (each T)?) -> Bool {
    for case _? in repeat each value {
        return true
    }
    return false
}

func advanceParticularIter<each Seqs: Sequence>(
    _ iterSeqPair: IterSeqPair<repeat each Seqs>,
    at targetIdx: Int
) -> (partialAdvance: (repeat (each Seqs).Element?), nextIterSeqPair: IterSeqPair<repeat each Seqs>)
{
    var idx = 0

    func doAdvance<Seq: Sequence>(
        _ iterSeqPair: (sequence: Seq, iterator: Seq.Iterator?)
    ) -> (value: Seq.Element?, nextIterSeqPair: (sequence: Seq, iterator: Seq.Iterator?)) {
        let isTarget = idx == targetIdx
        idx += 1
        guard isTarget else { return (value: nil, nextIterSeqPair: iterSeqPair) }

        var iter = iterSeqPair.iterator ?? iterSeqPair.sequence.makeIterator()
        guard let element = iter.next() else {
            return (value: nil, nextIterSeqPair: (sequence: iterSeqPair.sequence, iterator: nil))
        }

        return (value: element, nextIterSeqPair: (sequence: iterSeqPair.sequence, iterator: iter))
    }

    let res = (repeat doAdvance(each iterSeqPair))
    return (
        partialAdvance: (repeat (each res).value),
        nextIterSeqPair: (repeat (each res).nextIterSeqPair)
    )
}

let res = carteseanProduct([1, 2], ["foo", "bar", "baz"], [true, false], [1.0, 2.0, 3.0, 4.5])
print(type(of: res))
print(res.count)
for tuple in res {
    print(tuple)
}

Removed the use of Any and dynamically sized arrays of [Any] in favour of fixed-sized tuples of typed optionals. Algo still allocates for every element, since Array.subscript.read allocates coroutines. Big sadge. swiftlang/swift#53663