Generic constrained composite pattern

Using Swift
1

Let’s say I have some objects which satisfy a constrained composite pattern: There are leafs (possibly more than one kind) and composites, but each composite may only be composed of components of one kind. Let’s further assume these objects have been tag-length-value encoded and I was to write a custom decoder for them with an API similar to the decoders from the standard library. Here’s how I tried to do it (simplified; the actual decode implementations are more complex and perform e.g. bounds checking):

import Foundation

protocol Component {
    var tag: UInt8 { get }
    var length: Int { get }
}

struct Leaf: Component {
    var tag: UInt8
    var length: Int
    var value: [UInt8]
}

struct Composite<T>: Component where T: Component {
    var tag: UInt8
    var length: Int
    var components: [T]
}

protocol TLVDecodable {
    init(fromTLV decoder: TLVDecoder) throws
}

extension Leaf: TLVDecodable {
    init(fromTLV decoder: TLVDecoder) throws {
        self = try decoder.decode(Leaf.self)
    }
}

extension Composite: TLVDecodable {
    init(fromTLV decoder: TLVDecoder) throws {
        self = try decoder.decode(Composite.self)
    }
}

class TLVDecoder {
    fileprivate let buffer: [UInt8]
    fileprivate var cursor = 0
    
    public init(buffer: [UInt8]) {
        self.buffer = buffer
    }
}

extension TLVDecoder {
    func decode(_ type: UInt8.Type) throws -> UInt8 {
        let byte = buffer[cursor]
        cursor += 1
        return byte
    }
    
    func decode(_ type: Int.Type) throws -> Int {
        let bytes = buffer[cursor...cursor + 4]
        cursor += 4
        let length = bytes.reduce(0) { soFar, byte in
            return soFar << 8 | Int(byte)
        }
        return length
    }

    func decode(_ type: Leaf.Type) throws -> Leaf {
        let tag = try decode(UInt8.self)
        let length = try decode(Int.self)
        let value = buffer[cursor...cursor + length]
        return Leaf(tag: tag, length: length, value: [UInt8](value))
    }

    func decode<T: Component>(_ type: Composite<T>.Type) throws -> Composite<T> {
        let tag = try decode(UInt8.self)
        let length = try decode(Int.self)
        var components = [T]()
        while cursor < buffer.count {
            let t = try decode(T.self) // FIXME: No exact matches in call to instance method 'decode'
            components.append(t)
        }
        return Composite(tag: tag, length: length, components: components)
    }
}

However, I’m stuck on the // FIXME: - why can’t the compiler infer which decode method to call here?

2

T is not constrained to be decodable.
Either Component must me decodable :

protocol Component: Decodable

or constrain your decode method to work on decodables types :

func decode<T: Component & Decodable>(_:)

edit: swap Decodable with TLVDecoble

3

Thanks and you're right, but unfortunately the compiler is not so easily convinced.

4

Parametric polymporphism doesn't work with generics. The compiler needs to know the exact type of the argument in order to select the appropriate decode(:) method. T is a placeholder type, not an actual type;

Assuming your example would work and it correctly figures out to dispatch to decode(_ : Leaf.Type), would happen if I then add another type in the code like
struct LeafV2: Component { ... } but not implement a decode(_ : LeafV2.Type) method for it? After all there's no obligation/constraint in the TLVDecoder class to implement it anyway. How should the compiler react when it sees it has to make a call to something which doesn't exist?

5

Well, I guess you're right, but that's too bad. Anyway thank you for giving me something to read up on.

6

I appreciate this is not what you might be looking for, but consider this alternative type structure:

struct TaggedComponent {
    let tag: UInt8
    let length: Int
    let component: Component
}

enum Component {
    case leaf(value: [UInt8])
    case composite(components: [TaggedComponent])
}

I used a similar approach together with Codable, Message Pack and custom coder (in my case I didn't have explicit Tagged structure, but hardcoded tag into the relevant coder/decoders, and length was derived automatically (e.g. no need to have a separate length for Int, as its length is already known from the tag).

7

Thanks, I will look into it!