objc.io

00:06 Today we'll reimplement SwiftUI's attribute graph — well, perhaps it'll take a few episodes. We can't know how the attribute graph is actually implemented, but rumor has it that it's based on an old C++ paper called A System for Efficient and Flexible One-Way Constraint Evaluation in C++.

00:38 The article is all about constraints, and this does fit SwiftUI. Although, we usually talk about dependencies rather than constraints — e.g. if a view depends on some state property or an observed object and the state changes, we want the view's body to be reevaluated, which constitutes a dependency between the view's body and the state.

01:11 In our workshops, we use a more simplified mental model to explain these dependencies: the view tree. Working with SwiftUI, we create a value-based view tree, which serves as the blueprint for the actual views onscreen, i.e. the persistent objects that make up the render tree. But under the hood, there's no such thing as a render tree; there's only the attribute graph.

01:46 The difference between a tree and a graph is that a graph's dependencies can flow in any direction. Say we have an HStack with two subviews. The layout of the subviews depends on the configuration of the HStack, but also on the configuration of those subviews. The graph describing this view has an HStack node and nodes for the two subviews, and the HStack node depends on the other two nodes for its contents. But the position of each subview also depends on the HStack node. That suggests we're dealing with a graph, and not a tree.

02:37 We want to explore the basic idea of an attribute graph, as the paper lays it out, and see how updating the graph works by marking nodes as dirty. In a previous series of episodes, we worked on an incremental programming library, which has similar goals as the attribute graph — i.e. to provide ways to define inputs and rules that transform those inputs into the desired outputs. The incremental programming library, as we implemented it, responds to an input change by recomputing everything that depends on that input. The attribute graph, on the other hand, is more "pull-based" — when an input changes, it marks its dependents as potentially dirty, but nothing else happens. Then, when the system wants to use a new value, it starts reevaluating everything that's marked dirty.

A Graph of Nodes and Rules

03:53 Let's get started by writing a small test. We want to create an AttributeGraph with nodes and rules. We create two nodes — a and b — from integer values, along with another node, c, that adds up the values of a and b:

@Test func example() async throws {
    let graph = AttributeGraph()
    let a = graph.input(10)
    let b = graph.input(20)
    let c = graph.rule { a.wrappedValue + b.wrappedValue }
    #expect(c.wrappedValue == 30)
}

04:41 Later on, we also want to assign a new value to a and test that c's value automatically updates, because c is dependent on a:

@Test func example() async throws {
    let graph = AttributeGraph()
    let a = graph.input(10)
    let b = graph.input(20)
    let c = graph.rule { a.wrappedValue + b.wrappedValue }
    #expect(c.wrappedValue == 30)

    // a.wrappedValue = 40
    // c == 60
    //
    // a -> c
    // b -> c
}

05:13 To make this test compile, we need to write data structures that match the API used in it: the AttributeGraph, but also Node to represent each node, and Edge to define connections between nodes.

05:40 We'll define these as classes, because we need reference semantics to store two-way connections between nodes without making copies of the nodes. The AttributeGraph class stores an array of Nodes:

final class AttributeGraph {
    var nodes: [Node] = []
}

06:44 Node stores a wrappedValue, and it's generic over the value's type:

final class Node<A> {
    var wrappedValue: A

}

07:03 This already creates a problem, because the generic type parameter prevents us from storing an array of Node in the attribute graph. So, we need a type-erased wrapper, an AnyNode. We write a protocol for this, we conform Node to it, and we update AttributeGraph to store an array of AnyNode:

final class AttributeGraph {
    var nodes: [AnyNode] = []
}

protocol AnyNode: AnyObject {
}

final class Node<A>: AnyNode {
    var wrappedValue: A

}

08:05 If we want to use Node both for inputs and for rules, it needs one initializer to create an input, and one to create a rule. The rule initializer takes an escaping closure that returns an A value:

final class Node<A>: AnyNode {
    var wrappedValue: A
    var rule: (() -> A)?

    init(wrappedValue: A) {
        self.wrappedValue = wrappedValue
    }

    init(rule: @escaping () -> A) {
        self.rule = rule
    }
}

09:14 We probably want to access wrappedValue from the outside, but internally, it makes sense to store a cached value, which we can update by evaluating the rule. So, we create a private stored property _cachedValue, and we turn wrappedValue into a computed property. In the setter of this property, we make sure we're not in a rule-based node, because it would be an error to write to this node directly:

final class Node<A>: AnyNode {
    var rule: (() -> A)?

    private var _cachedValue: A?

    var wrappedValue: A {
        get {

        }
        set {
            assert(rule == nil)
            _cachedValue = newValue
        }
    }

    // ...
}

10:35 In the getter, we check if there's a cached value, and we execute the rule if there isn't one. After that, we know _cachedValue isn't nil, so we force-unwrap it:

final class Node<A>: AnyNode {
    var name: String
    var rule: (() -> A)?

    private var _cachedValue: A?

    var wrappedValue: A {
        get {
            if _cachedValue == nil, let rule {
                _cachedValue = rule()
            }
            return _cachedValue!
        }
        set {
            assert(rule == nil)
            _cachedValue = newValue
        }
    }

    init(wrappedValue: A) {
        self._cachedValue = wrappedValue
    }

    init(rule: @escaping () -> A) {
        self.rule = rule
    }
}

Graph Methods

11:28 We now have an attribute graph and nodes, but the connections between nodes are still missing, as are the methods on AttributeGraph that add nodes to the graph. Let's write the input method that takes a value, wraps it in a node, adds the node to the graph, and also returns the node:

final class AttributeGraph {
    var nodes: [AnyNode] = []

    func input<A>(_ value: A) -> Node<A> {
        let n = Node(wrappedValue: value)
        nodes.append(n)
        return n
    }
}

12:40 Then we write the rule method, which does the same, but with a rule closure instead of an input value:

final class AttributeGraph {
    // ...

    func rule<A>(_ rule: @escaping () -> A) -> Node<A> {
        let n = Node(rule: rule)
        nodes.append(n)
        return n
    }
}

12:56 Our test now passes. Later, we want the graph to recompute its nodes when an input changes, so let's think about capturing the dependencies between nodes.

Edges

13:26 If we were to render the graph using Graphviz — a helpful tool that can render a graph from an ASCII syntax — we'd expect to output a digraph with the nodes A, B, and C, and edges from A to C and from B to C:

@Test func example() async throws {
    let graph = AttributeGraph()
    let a = graph.input(10)
    let b = graph.input(20)
    let c = graph.rule { a.wrappedValue + b.wrappedValue }
    #expect(c.wrappedValue == 30)

    let str = """
    digraph {
    A
    B
    C
    A -> C
    B -> C
    }
    """
    #expect(str == graph.graphViz())

    // a.wrappedValue = 40
    // c == 60
    //
    // a -> c
    // b -> c
}

14:17 In AttributeGraph, we write a graphViz method that returns something like the string above by inserting the nodes' names, and for now, an empty string for the edges:

final class AttributeGraph {
    var nodes: [AnyNode] = []

    // ...

    func graphViz() -> String {
        let nodes = nodes.map(\.name).joined(separator: "\n")
        let edges = ""
        return """
        digraph {
        \(nodes)
        \(edges)
        }
        """
    }
}

15:06 For this, we need to add a name property to the AnyNode protocol and to Node:

protocol AnyNode: AnyObject {
    var name: String { get }
}

final class Node<A>: AnyNode {
    var name: String
    var rule: (() -> A)?

    private var _cachedValue: A?

    var wrappedValue: A {
        // ...
    }

    init(name: String, wrappedValue: A) {
        self.name = name
        self._cachedValue = wrappedValue
    }

    init(name: String, rule: @escaping () -> A) {
        self.name = name
        self.rule = rule
    }
}

15:56 We update our test by adding names to our nodes:

@Test func example() async throws {
    let graph = AttributeGraph()
    let a = graph.input(name: "A", 10)
    let b = graph.input(name: "B", 20)
    let c = graph.rule(name: "C") { a.wrappedValue + b.wrappedValue }
    #expect(c.wrappedValue == 30)

    let str = """
    digraph {
    A
    B
    C
    A -> C
    B -> C
    }
    """
    #expect(str == graph.graphViz())

    // a.wrappedValue = 40
    // c == 60
    //
    // a -> c
    // b -> c
}

16:08 The test obviously fails, because we aren't inserting any edges into the graph string.

16:39 The next question is, how do we capture the dependencies of the nodes? In our test, we just create the three nodes without specifying any edges. And that's how we want it to work: rather than explicitly adding the edges to the graph, we want the graph to infer the dependencies on node A and B from what happens in the rule of node C.

17:24 This is also how SwiftUI works; accessing a state property from a view's body creates a dependency between the two, and if we don't access the state property, there's no dependency.

17:48 In Node, we need to store the incoming edges and the outgoing edges, so we need an Edge class that stores a from node and a to node:

final class Edge {
    var from: AnyNode
    var to: AnyNode

    init(from: AnyNode, to: AnyNode) {
        self.from = from
        self.to = to
    }
}

18:55 Since we'll store edges in our nodes, we have to mark the node properties of Edge as unowned so that we don't create a reference cycle. The nodes are all stored in the AttributeGraph, so nothing else needs to create a strong reference to a node to keep it around:

final class Edge {
    unowned var from: AnyNode
    unowned var to: AnyNode

    init(from: AnyNode, to: AnyNode) {
        self.from = from
        self.to = to
    }
}

19:27 In Node, we keep an array of incoming edges and an array of outgoing edges. The incoming edges are the dependencies of the node, and the outgoing edges are the connections with other nodes that depend on this one:

final class Node<A>: AnyNode {
    var name: String
    var rule: (() -> A)?
    var incomingEdges: [Edge] = []
    var outgoingEdges: [Edge] = []

}

20:00 That's the basic structure of our attribute graph. Next, we have to register accesses of other nodes when we execute a node's rule closure and store edges with those nodes in them. That's going to be a little bit tricky, so let's start it with a fresh mind next week.