Swift: Can't use nested/chained generic type constraints (Policy pattern)

I'm implementing a randomized tree data structure in Swift. To constrain tree's width and depth, I have decided to use the Policy (Strategy) pattern.

My policy looks like this:

protocol BaseTreeNodePolicy {
    static var maximumDepth: Int { get }
    static var maximumWidth: Int { get }
}

and I have a base class which looks like this:

class BaseTreeNode<PolicyType: BaseTreeNodePolicy> { /* ... */ }

some subclasses of it:

class ValueNode<ValueType, PolicyType: BaseTreeNodePolicy>: BaseTreeNode<PolicyType> { /* ... */ }
class ActionNode<PolicyType: BaseTreeNodePolicy>: BaseTreeNode<PolicyType> { /* ... */ }

Everything has worked well until I added this class:

final class SequenceNode<ChildType: ActionNode<PolicyType>, PolicyType: BaseTreeNodePolicy>: ActionNode<PolicyType> {
    public var sequence: [ChildType] = []
    // ...
    public override func addRandomDescendants(generator: EntropyGenerator, maxDepth: Int) {
        // ...
        sequence.reserveCapacity(42)
        // ...
        let descendant = ChildType(generator: generator, maxDepth: maxDepth - 1)
        // ...
    }
}

When compiling SequenceNode, I get compiler errors on this row:

// 'ChildType' is not a subtype of 'ActionNode<PolicyType>'
sequence.reserveCapacity(42)

and this row:

// Type 'PolicyType' does not conform to protocol 'BaseTreeNodePolicy'
let descendant = ChildType(generator: generator, maxDepth: maxDepth - 1)

I have no idea what's wrong as I clearly state the type requirements saying that ChildType: ActionNode<PolicyType> and PolicyType: BaseTreeNodePolicy right in the header part of the declaration.

What could be wrong?

Thanks in advance! Petr.

Solution

EDIT: Re-do to get to your intent:

ActionNode<PolicyType> doesn't belong in the parameter list. You're only parameterizing on PolicyType:

final class SequenceNode<PolicyType: BaseTreeNodePolicy> {
    typealias ChildType = ActionNode<PolicyType>
    var sequence = [ChildType]()
    func addRandomDescendants(generator: EntropyGenerator, maxDepth: Int) {
        sequence.reserveCapacity(42)
    }
}

EDIT 2: Now you want to be more generic. OK, but you don't get to chain type dependencies WITHIN a generic type constraint list. The type constraints must be resolvable directly. This should make the error clear:

class _ERROR_SequenceNode<PolicyType, ChildType where PolicyType: BaseTreeNodePolicy, ChildType: ActionNode<PolicyType>> { }

Superclass constraint 'ActionNode' cannot depend on a type parameter

However, you ALSO cannot use BaseTreeNodePolicy in place of PolicyType because it's not concrete:

Using 'BaseTreeNodePolicy' as a concrete type conforming to protocol 'BaseTreeNodePolicy' is not supported

So, since ChildType is already constrained already by a generic type, that generic type must be instantiable directly, hence it can only be itself constrained by a known, outside, concrete implementation of BaseTreeNodePolicy.

BIG PICTURE

However, I think you're getting tangled in generics while missing the idea of just getting the job done simply. There is no value in parameterizing through generics when you have full control of that branch of the type system, and *you don't need to return the ACTUAL genericized type from a function*.

In other words, I must build a hash table generically parameterized on FooKeyType where FooKeyType: Hashable because users of my class rightfully expect the return value from a getKey() function to be the actual type in their code, not of type Hashable. Here, you don't ever return the policy object, or even if you did, you shouldn't care that its return type is fixed at BaseTreeNodePolicy rather than some specific, concrete policy type.

You can constrain simply by abstractly type-constraining the stored property as the requisite protocol.

Consider:

protocol BaseTreeNodePolicy {
    var maximumDepth: Int { get }
    var maximumWidth: Int { get }
}

class BaseTreeNode {
    var policy: BaseTreeNodePolicy

    required init(policy: BaseTreeNodePolicy) {
        self.policy = policy
    }

    // Use 'policy' anywhere now. You've defined a protocol, don't generically parameterize
}

class ValueNode: BaseTreeNode {
    required init(policy: BaseTreeNodePolicy) {
        super.init(policy: policy)
    }
}

class ActionNode: BaseTreeNode {
    required init(policy: BaseTreeNodePolicy) {
        super.init(policy: policy)
    }
}

class SequenceNode<ChildType: ActionNode>: BaseTreeNode {
    var sequence: [ChildType] = []

    required init(policy: BaseTreeNodePolicy) {
        super.init(policy: policy)
    }

    func addRandomDescendants() {
        let c = ChildType(policy: policy)
        sequence.reserveCapacity(42)
    }
}

class FooNode: ActionNode {}

class MyPolicy: BaseTreeNodePolicy {
    var maximumDepth = 3
    var maximumWidth = 5
}

let s = SequenceNode<FooNode>(policy: MyPolicy())