Do playgrounds have limits on generating descriptions?

Continuing the discussion from [Draft] Adding Safe indexing to Array:

Isn’t Collection.Index: Comparable?

Huh, it is. I didn’t realize this, since it’s not that prominent in the documentation. This makes it a lot harder (if not impossible!) to write custom Swift Collections such as linked lists or search trees. If anyone has one that can satisfy Collection's guarantees, I’d love to see it!

Hmm,… for a linked list, each node (which would be a class) would have an Int (or similar) ID, and the main body of the list would have an internal [Int: Node] property to index all of its nodes. The list’s Index would be those key IDs. It’s up to the list to make sure all IDs are strictly increasing whenever a RangeReplaceableCollection or a custom equivalent event occurs, which may involve recalculating all indexes.

I tried out making a linked list that conforms to Collection:

/// A singly-linked list.
public class SinglyLinkedList<T>: RangeReplaceableCollection, MutableCollection {

    /// A node for a singly-linked list.
    class Node {
        /// The node's data.  May be absent (like for sentinel nodes).
        var value: T?
        /// The link to the next node, or `nil` when none.
        var next: Node?
        /// A link to the owning list.
        weak var list: SinglyLinkedList?

        /// Creates a disconnected node, possibly with data.
        init(possibleValue: T? = nil) {
            value = possibleValue
            next = nil
            list = nil
            print("Node created at:", UnsafeRawPointer(Unmanaged.passUnretained(self).toOpaque()))
        }
        /// Creates a disconnected node with the given data.
        convenience init(value: T) {
            self.init(possibleValue: value)
        }

        deinit {
            print("Bye!  From:", UnsafeRawPointer(Unmanaged.passUnretained(self).toOpaque()))
        }
    }

    /// The one-past-the-end node, and points to the first node when the list is not empty.
    var sentinel: Node
    /// The end node.  Points to `sentinel` when the list is empty.
    var tail: Node

    deinit {
        print("Running SinglyLinkedList.deinit")
        tail.next = nil

        var node = sentinel
        while let next = node.next {
            node.next = nil
            node = next
        }
    }

    // MARK: Sequence

    public var underestimatedCount: Int { return sentinel.next! === sentinel ? 0 : 1 }

    // MARK: (Mutable)Collection

    // The index type.  Hashable to be usable in Key-Paths (I think).
    public struct Index: Comparable, Hashable {
        public static func <(lhs: Index, rhs: Index) -> Bool {
            return lhs.id < rhs.id
        }

        public var hashValue: Int { return id.hashValue }

        public static func ==(lhs: Index, rhs: Index) -> Bool {
            return lhs.node === rhs.node
        }

        /// The targeted node.
        let node: Node
        /// A pusedo-ID.  Should be the offset from `startIndex`, except it's always `max` for `endIndex`.
        let id: UInt
    }

    public subscript(position: Index) -> T {
        get { return position.node.value! }
        set { position.node.value! = newValue }  // The "!" forces a NIL check before write.
    }

    public var endIndex: Index { return Index(node: sentinel, id: UInt.max) }

    public var startIndex: Index {
        guard let head = sentinel.next, head !== sentinel else { return endIndex }

        return Index(node: head, id: 0)
    }

    public func index(after i: Index) -> Index {
        let nextNode = i.node.next!
        guard nextNode !== sentinel else { return endIndex }

        return Index(node: nextNode, id: i.id + 1)
    }

    // MARK: RangeReplaceableCollection

    public required init() {
        print("Running SinglyLinkedList.init()")
        sentinel = Node()
        sentinel.next = sentinel
        tail = sentinel
        sentinel.list = self
    }

    public func replaceSubrange<C: Collection>(_ subrange: Range<Index>, with newElements: C) where C.Element == Element {
        // Sanity checks.
        precondition(subrange.lowerBound.node.list! === self)
        precondition(subrange.upperBound.node.list! === self)
        precondition(subrange.lowerBound.id <= subrange.upperBound.id)

        // Create nodes for the new elements.
        let newNodes = newElements.map { Node(value: $0) }
        zip(newNodes.dropLast(), newNodes.dropFirst()).forEach { arg in arg.0.next = arg.1 }
        newNodes.forEach { $0.list = self }

        // Point to the parts of the current list that are staying.
        var lastPrefixNode = sentinel
        if subrange.lowerBound < endIndex {
            for _ in 0..<subrange.lowerBound.id {
                lastPrefixNode = lastPrefixNode.next!
            }
        } else {
            lastPrefixNode = tail
        }
        var firstNodeToKill = lastPrefixNode.next!
        let firstSuffixNode = subrange.upperBound.node
        assert(firstNodeToKill === subrange.lowerBound.node)

        // Connect the nodes
        switch (newNodes.isEmpty, subrange.lowerBound == endIndex, subrange.upperBound == endIndex) {
        case (true, true, _):
            // No change.
            break
        case (true, false, true):
            // Truncation.
            lastPrefixNode.next = sentinel
            tail = lastPrefixNode
        case (true, false, false):
            // Interior removal.
            lastPrefixNode.next = firstSuffixNode
        case (false, true, _):
            // Appending.
            newNodes.last!.next = sentinel
            tail.next = newNodes.first!
            tail = newNodes.last!
        case (false, false, true):
            // Tail-end replacement.
            newNodes.last!.next = sentinel
            lastPrefixNode.next = newNodes.first!
            tail = newNodes.last!
        case (false, false, false):
            // Interior replacement or insertion.
            newNodes.last!.next = firstSuffixNode
            lastPrefixNode.next = newNodes.first!
        }

        // Purge any removed nodes.
        while firstNodeToKill !== firstSuffixNode {
            let next = firstNodeToKill.next!
            firstNodeToKill.next = nil
            firstNodeToKill = next
        }
    }

    // MARK: Custom Linked-List Stuff

    var aDescription: String {
        return String(describing: Array(self))
    }

}

I did use custom numbers for indexes, but not in the same way as my original guess.

It seems to be working so far. I originally had a description property for printing. But it hung the playground. You can see that I added a custom property; and sure enough, it works. Then I realized that official descriptions are what are called on the right sidebar for object states. Is there some sort of computation limit a type can have for description before locking up the playground? I’ve been using Xcode 9.2 (with Swift 4.0) here.

Unrelated to your question, but how are you maintaining these?

  • endIndex is (sentinel, Uint.max), where sentinel is the linked list's anchor node. It has no value stored. The node stores a T? and I use ! for both get and set during subscript.
  • startIndex, when there's at least one element, is (firstNode, 0).
  • Since index instance creation is regulated only through the methods of Collection, other valid values come from index(after:), where I return (i.node.next, i.id + 1).

The node objects don't store an ID, only Index instances do. In my latest code, index instances have a weak reference to the list, so replaceRange(_: with:) can confirm the index refers to the same list. (I first had the weak list reference in the node, then I moved it to the indexes because they're just as transitory as IDs; I only need back-references during replaceRange(_: with:) because confirming a node is actually part of a given list is O(n) otherwise.)

Have you considered upgrading this into a doubly-linked list? I’m guessing you’re holding off on it because endIndex.id == .max, this would make index(before:) difficult to implement? If this is the case, here’s a suggestion: try keeping track of your count at all times (updating it in replaceSubrange(_:with:)) so that endIndex.id == count.

Singly- vs. doubly-linked lists are more different trade-offs instead of an upgrade. I just uploaded a Gist of this single-link version. I might take a breather before the double-link version.

The single version uses a circular list with a sentinel node. I’m thinking of just head and tail pointers in non-circular non-sentinel format for the double version, so I could use it as its own sub-sequence. I already figured out I need to track the count to because Uint.max can’t work as the endIndex for a BidirectionalCollection version.