泛型类型之间的循环依赖（CollectionType 及其 Index/Generator，例如）

Question

给定一个基于 struct 的泛型 CollectionType …

struct MyCollection<Element>: CollectionType, MyProtocol {
    typealias Index = MyIndex<MyCollection>

    subscript(i: Index) -> Element { … }

    func generate() -> IndexingGenerator<MyCollection> {
        return IndexingGenerator(self)
    }
}

…如何为它定义一个Index…

struct MyIndex<Collection: MyProtocol>: BidirectionalIndexType {

    func predecessor() -> MyIndex { … }
    func successor() -> MyIndex { … }
}

…没有引入死亡依赖循环？

MyIndex 的通用性质是必要的，因为：

它应该适用于任何类型的 MyProtocol。
MyProtocol 引用 Self 因此只能用作类型约束。

如果有前向声明（à la Objective-C）我会只是^{[原文如此！]}为[添加一个=22=] 到我的 MyCollection<…>。唉，没有这回事。

一个可能的具体用例是二叉树，例如：

indirect enum BinaryTree<Element>: CollectionType, BinaryTreeType {
    typealias Index = BinaryTreeIndex<BinaryTree>

    case Nil
    case Node(BinaryTree, Element, BinaryTree)

    subscript(i: Index) -> Element { … }
}

这需要基于堆栈的 Index:

struct BinaryTreeIndex<BinaryTree: BinaryTreeType>: BidirectionalIndexType {
    let stack: [BinaryTree]

    func predecessor() -> BinaryTreeIndex { … }
    func successor() -> BinaryTreeIndex { … }
}

不能（还？）在 Swift.
中的通用 struct 中嵌套 struct 否则我会把 BinaryTreeIndex<…> 移到 BinaryTree<…>.

里面

此外，我更希望有一个通用的 BinaryTreeIndex，
然后可以与任何类型的 BinaryTreeType.

一起使用

Answer 1

您不能在结构中嵌套结构，因为它们是值类型。它们不是指向对象的指针，而是将它们的属性保存在变量中。想想如果一个结构包含自己，它的内存布局会是什么样子？

前向声明在 Objective-C 中起作用，因为它们随后被用作指针。这就是 indirect 关键字被添加到枚举的原因——它告诉编译器通过指针添加一个间接级别。

理论上可以将相同的关键字添加到结构中，但这没有多大意义。不过，您可以使用 class 框来代替 indirect 手动执行的操作：

// turns any type T into a reference type
final class Box<T> {
    let unbox: T
    init(_ x: T) { unbox = x }
}

您可以使用它来打包一个结构来创建，例如，一个链表：

struct ListNode<T> {
    var box: Box<(element: T, next: ListNode<T>)>?

    func cons(x: T) -> ListNode<T> {
        return ListNode(node: Box(element: x, next: self))
    }

    init() { box = nil }
    init(node: Box<(element: T, next: ListNode<T>)>?)
    { box = node }
}

let nodes = ListNode().cons(1).cons(2).cons(3)
nodes.box?.unbox.element // first element
nodes.box?.unbox.next.box?.unbox.element // second element

您可以将此节点直接变成一个集合，方法是使其同时符合 ForwardIndexType 和 CollectionType，但这不是一个好主意.

例如，他们需要非常不同的 == 实现：

索引需要知道同一列表中的两个索引是否在同一位置。它不需要元素符合Equatable。

集合需要比较两个不同的集合，看它们是否持有相同的元素。它确实需要元素符合Equatable即：

func == <T where T: Equatable>(lhs: List<T>, rhs: List<T>) -> Bool {
    // once the List conforms to at least SequenceType:
    return lhs.elementsEqual(rhs)
}

最好用两种特定类型包装它。这是“免费的”——包装器没有开销，只是帮助您更轻松地构建正确的行为：

struct ListIndex<T>: ForwardIndexType {
    let node: ListNode<T>

    func successor() -> ListIndex<T> {
        guard let next = node.box?.unbox.next
            else { fatalError("attempt to advance past end") }
        return ListIndex(node: next)
    }
}

func == <T>(lhs: ListIndex<T>, rhs: ListIndex<T>) -> Bool {
    switch (lhs.node.box, rhs.node.box) {
    case (nil,nil): return true
    case (_?,nil),(nil,_?): return false
    case let (x,y): return x === y
    }
}

struct List<T>: CollectionType {
    typealias Index = ListIndex<T>
    var startIndex: Index
    var endIndex: Index { return ListIndex(node: ListNode()) }
    subscript(idx: Index) -> T {
        guard let element = idx.node.box?.unbox.element
            else { fatalError("index out of bounds") }
        return element
    }
}

（无需实施 generate() – 您通过实施 CollectionType 在 2.0 中“免费”获得索引生成器）

您现在拥有一个功能齐全的集合：

// in practice you would add methods to List such as
// conforming to ArrayLiteralConvertible or init from 
// another sequence
let list = List(startIndex: ListIndex(node: nodes))

list.first  // 3
for x in list { print(x) }  // prints 3 2 1

现在所有这些代码看起来都很恶心，原因有二。

一个是因为盒子挡道，indirect 更好，因为编译器会在后台为您整理好所有内容。但它正在做类似的事情。

另一个是结构不是解决这个问题的好方法。枚举要好得多。事实上，代码是 really 使用枚举——这就是 Optional 的含义。只不过不是nil（即Optional.None），链表的末尾有一个End的情况会更好。这就是我们使用它的目的。

如需了解更多此类内容，您可以查看 these posts。

Answer 2

虽然 Airspeed Velocity 的答案适用于最常见的情况，但我的问题是专门询问一般化 CollectionType 索引的特殊情况，以便能够为所有可想到的二叉树共享一个 Index 实现（其递归性质使得有必要使用堆栈进行基于索引的遍历（至少对于没有父指针的树）），这需要Index 专门针对实际的 BinaryTree，而不是 Element。

我解决这个问题的方法是将 MyCollection 重命名为 MyCollectionStorage，撤销它的 CollectionType 一致性，并用一个现在取代它的结构 MyCollection 并处理符合 CollectionType.

为了让事情更精彩一些"real"我会参考：

MyCollection<E> 作为 SortedSet<E>
MyCollectionStorage<E> 作为 BinaryTree<E>
MyIndex<T> 作为 BinaryTreeIndex<T>

废话少说：

struct SortedSet<Element>: CollectionType {
    typealias Tree = BinaryTree<Element>
    typealias Index = BinaryTreeIndex<Tree>

    subscript(i: Index) -> Element { … }

    func generate() -> IndexingGenerator<SortedSet> {
        return IndexingGenerator(self)
    }
}

struct BinaryTree<Element>: BinaryTreeType {

}

struct BinaryTreeIndex<BinaryTree: BinaryTreeType>: BidirectionalIndexType {
    func predecessor() -> BinaryTreeIndex { … }
    func successor() -> BinaryTreeIndex { … }
}

这样依赖图就从有向循环图变成了有向无环图.

泛型类型之间的循环依赖（CollectionType 及其 Index/Generator，例如）

Circular dependencies between generic types (CollectionType and its Index/Generator, e.g.)

generics

protocols

persistent-storage

swift