How can I call the specialized version of a generic function?

I want to specialize the unbox__ function for when the input type conforms to Collection. Currently, my specialized unbox__ function is never called in the example below during the init method. Any ideas?

struct Aa: Codable {
    let c: [Float]
    enum Keys: CodingKey {
        case c
    }
    init(from decoder: Decoder) throws {
        let container = try decoder.container(keyedBy: Keys.self)
        self.c = try container.decode([Float].self, forKey: .c)
    }
}

try! ZippyJSONDecoder().decode(Aa.self, from: #"{"c": [2, 3]}"#.data(using: .utf8)!)

// In ZippyJSONDecoder's Decoder...
    func unbox__<T: Decodable>() throws -> T where T: Collection {
        // This function isn't called
        return try decoder.unbox(value, as: T.self)
    }
    
    func unbox__<T: Decodable>() throws -> T {
        return try decoder.unbox(value, as: T.self)
    }

    fileprivate func decode<T : Decodable>(_ type: T.Type, forKey key: K) throws -> T {
        let subValue: Value = key.stringValue.withCString(fetchValue)
        return try unbox__()
    }

You’ll also need to add Collection version of decode, or perform the check dynamically.

The compiler choose the version of unbox__ before the specialization (that is, the substitution of T) occurs.

I've tried adding fileprivate func decode<T : Decodable>(_ type: T.Type, forKey key: K) throws -> T where T: Collection { abort() }, but it never gets called. I tried performing the check dynamically, but it's too slow for my purposes.

I wonder if that function doesn't get called because it's not a part of the Decoder protocol, it's just a function of my concrete implementation of Decoder, __JSONDecoder.

Oh, if you use them as a protocol conformance, that's about the granularity you'll get (at least, I'm pretty sure of that).

Since there's no Collection version specifically in KeyedDecodingContainer, you'll need to make do with dynamic checking.

Fair enough. Since dynamic checking was so slow, I was able to make it work as such:

    var nonArrayTypes = Set<ObjectIdentifier>()
    var typeMap: [ObjectIdentifier: AnyArray] = [:]
    fileprivate func decode<T : Decodable>(_ type: T.Type, forKey key: K) throws -> T {
        let subValue: Value = key.stringValue.withCString(fetchValue)
        let id = ObjectIdentifier(type)
        if nonArrayTypes.contains(id) {
            return try decoder.unbox(subValue, as: T.self)
        }
        if let dummyInstance = typeMap[id] {
            return try dummyInstance.create(value: value, decoder: decoder) as! T
        }
        if let arrayType = type as? AnyArray.Type {
            let dummy = arrayType.dummy()
            typeMap[id] = dummy
            return try dummy.create(value: value, decoder: decoder) as! T
        } else {
            nonArrayTypes.insert(id)
            return try decoder.unbox(subValue, as: T.self)
        }
    }
fileprivate protocol AnyArray: Decodable {
    static func dummy() -> Self
    func create(value: Value, decoder: __JSONDecoder) throws -> Self
}

extension Array: AnyArray where Element: Decodable {
    fileprivate static func dummy() -> Self {
        return []
    }

    fileprivate func create(value: Value, decoder: __JSONDecoder) throws -> Self {
        // return array from decoder
    }
}

I wasn't able to figure out how to use unsafeBitCast here, or if it's ever possible, but what I have is good enough.

Is there some constraint not to use Array's own Decodable implementation, which is to get UnkeyedDecodingContainer, then keeps decoding element one-by-one?

I'm not sure what you're aiming for here. I don't see where it'd fit either. :thinking:

That implementation is substantially slower (doesn't preallocate the perfect size, creates an UnkeyedDecodingContainer which IIRC involves heap allocations, appends elements one at a time, etc.). My version speeds up my JSON decoder by ~20% for typical JSON payloads. Code:

    fileprivate func create(value: Value, decoder: __JSONDecoder) throws -> Self {
        guard var currentValue = JNTDocumentEnterStructureAndReturnCopy(value) else {
            return []
        }
        decoder.containers.push(container: currentValue)
        defer { decoder.containers.popContainer() }
        var isAtEnd = false
        let count = JNTDocumentGetArrayCount(currentValue)
        let array: [Element] = try Array(unsafeUninitializedCapacity: count) { (buffer, countToAssign) in
            let rawPointer = UnsafeMutableRawPointer(mutating: UnsafeRawPointer(buffer.baseAddress))
            // Zero it out to be safe
            memset(rawPointer, 0, MemoryLayout<Element>.stride * count)
            for i in 0..<count {
                buffer[i] = try Element(from: decoder)
                JNTDocumentNextArrayElement(currentValue, &isAtEnd)
            }
            countToAssign = count
        }
        return array
    }

The one unsafe thing that I see in my code is that there's a try in the array initialization block, and the documentation states, "The memory in the range buffer[0..<initializedCount] must be initialized at the end of the closure’s execution, and the memory in the range buffer[initializedCount...] must be uninitialized. This postcondition must hold even if the initializer closure throws an error." It seems impossible to completely avoid that. But, perhaps it is not terrible since I zero'd the memory first?

That's very reasonable. On that topic, it's odd that Array doesn't take advantage of UnkeyedDecodingContainer.count whenever possible. Maybe one can file an improvement request at some point (or just straight to pull request).

As a general note, you don't need to zero-out the data, esp. since you'll be writing over it anyway (which is kind of the point of this initialiser). Just need make sure that countToAssign reflects the actual number at the end.

You could do

for i in 0..<count {
  do {
    buffer[i] = try Element(from: decoder)
  } catch {
    countToAssign = i
    throw error
  }
  JNTDocumentNextArrayElement(currentValue, &isAtEnd)
}

or even

for i in 0..<count {
  buffer[i] = try Element(from: decoder)
  countToAssign += 1
  JNTDocumentNextArrayElement(currentValue, &isAtEnd)
}

Though I don't know how cheap do-catch block is (you probably know better at this point).

IMO it's more dangerous to say that zero'd memory is initialised memory, especially around undecided Element type.

Nice catch, thank you. Although you know what's weird is that it turns out, unless I do the memset call, I get an EXC_BAD_ACCESS as soon as I try to access buffer. You can see that in any of my code, e.g. what I currently have after your suggestions:

    fileprivate func create(value: Value, decoder: __JSONDecoder) throws -> Self {
        guard var currentValue = JNTDocumentEnterStructureAndReturnCopy(value) else {
            return []
        }
        decoder.containers.push(container: currentValue)
        defer { decoder.containers.popContainer() }
        var isAtEnd = false
        let count = JNTDocumentGetArrayCount(currentValue)
        let array: [Element] = try Array(unsafeUninitializedCapacity: count) { (buffer, countToAssign) in
            let rawPointer = UnsafeMutableRawPointer(mutating: UnsafeRawPointer(buffer.baseAddress))
            // Zero it out to be safe
            // memset(rawPointer, 0, MemoryLayout<Element>.stride * count)
            countToAssign = 0
            for _ in 0..<count {
                buffer[countToAssign] = try Element(from: decoder)
                JNTDocumentNextArrayElement(currentValue, &isAtEnd)
                countToAssign += 1
            }
        }
        return array
    }
}

Oh that's right, there's this warning in UnsafeMutablePointer.subscript(_:)

Do not assign an instance of a nontrivial type through the subscript to uninitialized memory. Instead, use an initializing method, such as initialize(to:count:).

Which doesn't appear in UnsafeMutableBufferPointer version. Either Buffer version has better handling or the it missed the warning. I'm gonna assume the latter, but maybe someone more knowledgeable can chime in.

This may be related, so you may want to instead use UnsafeMutablePointer.initialized(to:).

let array: [Element] = try Array(unsafeUninitializedCapacity: count) { (buffer, countToAssign) in
    var address = buffer.baseAddress!

    defer {
        countToAssign = address - buffer.baseAddress!
    }

    for _ in 0..<count {
        try addess.initialize(to: Element(from: decoder))
        address = address.successor()
        JNTDocumentNextArrayElement(currentValue, &isAtEnd)
    }
}

Good to know! Fortunately, initializing the memory with a Sequence is actually as fast/slightly faster:

extension Array: AnyArray where Element: Decodable {
    fileprivate static func dummy() -> Self {
        return []
    }
    
    struct Seq: Sequence, IteratorProtocol {
        private let decoder: __JSONDecoder
        private let count: Int
        private let value: Value
        var i = 0
        private var b = false
        var error: Error? = nil
        
        fileprivate init(decoder: __JSONDecoder, count: Int, value: Value) {
            self.decoder = decoder
            self.count = count
            self.value = value
        }
        
        mutating func next() -> Element? {
            if i >= count {
                return nil
            }
            do {
                let element = try Element(from: decoder)
                i += 1
                JNTDocumentNextArrayElement(value, &b)
                return element
            } catch {
                self.error = error
            }
            return nil
        }
    }

    fileprivate func create(value: Value, decoder: __JSONDecoder) throws -> Self {
        guard var currentValue = JNTDocumentEnterStructureAndReturnCopy(value) else {
            return []
        }
        decoder.containers.push(container: currentValue)
        defer { decoder.containers.popContainer() }
        let count = JNTDocumentGetArrayCount(currentValue)
        let sequence = Seq(decoder: decoder, count: count, value: value)
        let array: [Element] = try Array(unsafeUninitializedCapacity: count) { (buffer, countToAssign) in
            // We can't use subscript mutation with buffer because Swift requires buffer to be initialized anywhere we mutate it
            // Instead, use a lightweight sequence
            let _ = buffer.initialize(from: sequence)
            countToAssign = sequence.i
            if let error = sequence.error {
                throw error
            }
        }
        return array
    }
}
1 Like

@Lantua similar question as the original one... why does only ElementSequence's next function get called in the example below, and not ArraySequence's next function?

fileprivate protocol AnyArray: Decodable {
    func create() throws -> Self
}

private func getSequence<T: Decodable>() -> SequenceParent<T> {
    return ElementSequence<T>()
}

private func getSequence<T: Decodable>() -> SequenceParent<T> where T: AnyArray {
    return ArraySequence<T>()
}


private class SequenceParent<T: Decodable>: Sequence, IteratorProtocol {
    func next() -> T? { fatalError() }
}

private final class ArraySequence<T: Decodable & AnyArray>: SequenceParent<T> {
    override func next() -> T? { fatalError() } // This one should be called, but isn't
}

private final class ElementSequence<T: Decodable>: SequenceParent<T> {
    override func next() -> T? { fatalError() }
}

extension Array: AnyArray where Element: Decodable {
    fileprivate func create() throws -> Self {
        let sequence: SequenceParent<Element> = getSequence()
        for _ in sequence { print("") }
        fatalError()
    }
}


try [[Int]]().create()

It is similar to the post here–Resolving the correct function by conditional conformance.

It’s still the same story, that getSequence is inferred only from within create context, which knows only that Element: Codable from extension declaration. Even if at the use site it’s already known to be Element: AnyArray, the function is resolved before that.

You can look up static dispatch vs dynamic dispatch (in this forum too).

I think there's a fundamental misconception here which needs to be cleared up.

If you override an open member of a class, or if you implement a protocol requirement in a conforming type, then that acts as a "specialized" version of the overridden member or default implementation (respectively). In the general case, the choice of implementation used is determined at run time based on the dynamic type of the instance on which the method is invoked. There is a performance and memory cost to dynamic dispatch. If the compiler can work out for sure which implementation will be called, then as an optimization, the choice can be baked in at compile time.

It so happens that the specialized implementation must use the same name as the overridden/default implementation. There is no reason that this must be the case forever in Swift, and in the case of protocols, there's in fact the not-yet-official @_implements that allows one not to use the same name.

Which brings us to the central point I think needs to be cleared up here: There is nothing magical about naming two functions identically with different generic constraints; no table exists at run time to choose between them. All you have are two functions with the same name, thus potentially requiring the use of complicated overload resolution rules to determine at compile time which one the user intended to invoke. One function is a "specialized" version of the other only in the sense that when a user types the same name, at compile time there are these overload resolution rules to decide which one the user means based on context such as type annotations.

In this case, you have two free functions named getSequence. Fortunately, when you invoke getSequence(), it's unambiguous which one you mean. It's unambiguous because you can only choose a method inside create that can return any SequenceParent<T> where T is of the caller's choosing.

To clarify what the compiler is doing, it would be simpler to name the first getSequence instead as getSequenceA and the second one as getSequenceB. (Again, there is no magic you unlock by using the same name for these two functions.) Then, you will easily see that inside create() you invoke getSequenceA. Therefore, when you iterate over the returned value of type ElementSequence<[Int]>, which next() is called becomes obvious.

3 Likes

Is there some way to dynamically dispatch, without too much dynamic casting, to a different function based on whether an Array's members are of type of Array themselves? Or better yet, to somehow dynamically dispatch to a different init(from: Decoder) implementation. Or will I have to use more maps with ObjectIdentifiers?

On top of my head, these are already dynamically dispatched:

  • methods for protocol conformance (if used in protocol context)
  • non-final class method

but then they’re dynamic on the class’s instance, not argument. As @xwu said, functions with different constraints also count as different functions regardless. So do be careful with that.

I’m pretty sure there’s some more from @objc but I’m not too well versed in that area.