"Observing" changes to arbitrary key paths on move-only structs

jeremyabannister · April 16, 2023, 8:39pm

I've been following the discussions around SE-0395: Observability as well as the counter-points raised by @gwendal.roue here, and some new ideas related to the topic formed in my mind that I want to share and hear feedback on.

Based on Gwendal's post I believe that my experience grappling with the implementation of "Observation" patterns is more limited than his. The ideas I propose here are not meant to address the full problem space, rather to attempt to describe a possible design for a specific subsection of it.

As far as my experience with the topic, I did recently implement (somewhat hastily hack together) this Swift package which provides MainActorValueSource<Value>, a main-actor-isolated generic single value holder that can be composed with other (compositions of) sources and then observed. It uses a SwiftUI-like approach for dependency tracking so as to provide what I believe is what Gwendal describes as "Value Observation":

To be clear, the implementation in that package is not directly related to what I describe below.

The Vision In My Mind

I'm going to try to lay out my ideas clearly and concisely. I don't know if the things I'm thinking of actually fit together as a coherently implementable approach - it's more of a brainstorm:

I imagine defining a huge, deeply nested struct. When I say "huge struct" I don't mean that the top level has a lot of properties. I'm imagining the struct encoded as a JSON object, which can still be huge even if the top level has only one key.
I imagine using the new move-only features to create exactly one instance of this huge struct. That instance "has an identity" by virtue of being move-only (a concept which I started a thread about here).
I imagine that access to that huge struct instance could be restricted to a specific concurrency context. (e.g., one's ViewModel would be restricted to the MainActor).
If this huge struct is indeed a view model, then I imagine having a beautifully direct method (probably using key paths) of connecting one of its far-away leaves to a small sub-component of my UI, and have that UI component observe changes to that specific part of the huge ViewModel struct and update itself accordingly.
More generally, I imagine being able to conveniently observe any key path on this giant struct. (I realize that the definition of "conveniently observe" is hotly debated - I don't think that's what I'm addressing here, in that whatever the resolution is there would presumably be compatible with what I'm describing here).
To summarize so far, I think the core of what I'm proposing is the ability to observe arbitrary key paths on move-only structs, using whatever observation API we deem best in general (although maybe the results of those debates are fundamentally incompatible with this design for whatever reason - the whole thing is too abstract for me to feel very certain about it).
If I've correctly understood the discussions surrounding invariants and the problems wanting to be addressed, I think that this approach may offer an elegant solution, which is that you statically enforce your invariants using structs and then you just have to widen the scope of your observed key path enough to encompass the enforcement. For example:

// Use:
observe(\.hallOfFameTab.hallOfFame)

// Instead of:
observe(\.hallOfFameTab.hallOfFame.totalNumberOfPlayers)
observe(\.hallOfFameTab.hallOfFame.topPlayers)

I'm not 100% sure that my point about invariants is an appropriate or relevant addition to the discussions I saw going on in Gwendal's thread, but I think that what I'm getting at is at least somewhat clear.

Lastly, I'll give a shout-out to BSON, the existence of which some of @taylorswift's posts only recently brought to my attention, because I'm imagining observing a change in a distant leaf of my huge move-only struct and then leveraging BSON's architecture (if I've understood it correctly) to efficiently persist that change to the BSON file that contains the whole encoded struct without needing to encode and persist the entire struct on every change.

Would love to hear your thoughts (and corrections - I am sure that many of the things I said are correctable).

tera · April 16, 2023, 9:39pm

Why move only structs necessarily, btw? Note, you'd need a copy in some shape and form, e.g. when you are animating a change from value1 to value2 you need to have both values to extrapolate between them over time.

In my experience working with Swift UI the beauty of its ObservableObject / Published mechanism is that you don't have to call "observe" (and "unobserve") explicitly:

class Model: ObservableObject {
    struct ModelState {
        struct HallOfFameTab {
            struct HallOfFame {
                var totalNumberOfPlayers: Int = 0
                var topPlayers: [Player] = []
            }
            var hallOfFame = HallOfFame()
        }
        var hallOfFameTab = HallOfFameTab()
    }
    @Published var state = ModelState()
}

struct HallOfFameView: View {
    @StateObject var model = Model()
    var body: some View {
        Text("\(model.state.hallOfFameTab.hallOfFame.totalNumberOfPlayers)")
    }
}

Note that I didn't have to use keypaths explicitly, which IMHO is a very good thing.

There are these issues though we found problematic with SwiftUI observation (not in the order of importance):

I can forget putting StateObject, ObservedObject. In this case the relevant piece of UI won't update. Worse - it could still update because of the change in another view, and when I change something in the app the bug surfaces.
that the changes are triggered not on didSet but on on willSet when the state is not yet "new" caught us by surprise a few times. The typical workaround is to use an extra DispatchQueue.main.async which we found not ideal. We noticed this issue is somehow interconnects with animations (it depends upon whether we are changing model values in the "withAnimation" block or not).
we haven't found an ideal place yet for withAnimation call. It belongs to the view, but do we call it always or in some cases only? If that's always why doesn't SwiftUI do this for us under the hood. Sometimes we end up having withAnimation in the model code, which is a strange place I'd say, but often times it's hard to do it otherwise (e.g. if model code is changing the model state asynchronously).
For a big data structure and complex UI body calculations / diffing are quite expensive, often to the extent that UI is too slow to be usable. The latter caused us to use ViewModel classes (typically one per view) to minimise the amount of changes SwiftUI diffing machinery has to deal with.
But now that we have multiple ViewModels (and split the state into small pieces) we no longer have a nice semi-automated machinery of ObservableObject / Published – we have to use some other mechanism to micromanage and propagate state changes from one model to another, Combine or otherwise. We found this propagation too manual, somewhat error prone, and quite cumbersome. Note that if we did't have issue (4) we'd not have to deal with issue (5).

The BSON angle is quite interesting and there are indeed similarities in writing a minimal amount of data to the file and redrawing a minimal amount of pixels on the screen when changes happen somewhere within a big data structure tree.

taylorswift · April 16, 2023, 10:08pm

i haven’t gotten a chance to go over the observability stuff in detail, so i don’t have much to add there, but i will say since BSON is suddenly getting a lot of attention that BSON is not a good serialization format. it has a lot of encoding overhead when naiively porting over strongly-typed swift structures, and i only use it currently because:

it is the native storage format of MongoDB,
it can handle fixed-point and decimals, and
despite its many shortcomings, it is still vastly more efficient than JSON, particularly in memory usage, since JSON needs an entire AST to be persisted in memory, whereas BSON is traversible.

in a perfect world, i would be using a binary serialization format like ion, which has many of the same advantages as BSON, but can encode data with a somewhat smaller size footprint than BSON can.

Ion has implementations for pretty much every major programming language ( C – C# – Go – Java – JavaScript – Python – Rust, D – PHP – Ion Object Mapper for .NET) except for swift, which is quite unfortunate. @Joannis_Orlandos and i have in the past discussed development of a swift ion library, but sadly we concluded it was economically impractical, so for now we are stuck with BSON, protobuf, etc.

this is one of those situations where i feel that Apple “talks the talk” when it comes to cultivating a rich library ecosystem, but fails to “walk the walk”.

jeremyabannister · April 16, 2023, 10:28pm

To be clear, the struct does not define itself as non-copyable, rather it is a normal struct, a single instance of which we protect and give an identity to (the identity being key for observability) by leveraging the move-only tools we've recently created, which I think @Joe_Groff affirmed is part of the design. The move-only instance is the source of truth, and of course copies of it or copies of sub-portions of it can and will be created, often. Those copies will be manipulated and transformed and eventually some new data will make its way back into the move-only struct instance (the source of truth).

tera · April 21, 2023, 5:16pm

In one of my projects where I had a similar setup – a giant tree like "master" state data structure, with individual views representing small portions of the tree. I ended up having views backed by individual view models, each view model with its own tiny state contained only bits and pieces relevant to the view in question. Between views and corresponding view modes normal swiftUI Observable / published machinery was used, so that's not particularly interesting.

Interesting was a manual replicating system that synchronised changes between master state and individual view models' states. Naturally on its initialisation the view model subscribed to observe master model changes to keep synchronised. I did my best to keep that synchronisation off the main thread and spread it across multiple threads to fully utilise multiple CPU cores – data extraction master state -> individual view state was done on the serial background queue of the individual view model and less frequent data updating back from individual view state -> master state was done on the master model background serial queue. Part of data extraction process was comparing the new view state to the old view state to see if view model state actually changed and the view actually needs to be updated - that comparison was also done off the main thread.

I had a specific challenge to solve: during view model creation (done as part of SwiftUI view creation on the main thread) you either leave the current view state "empty" / "loading" (to have the equivalent of "loading data" UI) - bad because of view flickering, or you synchronously obtain the data from the master state – the latter is bad for two reason: it is relatively slow (main queue -> other queue(s) -> back) and it is complicated to implement as there were two background queues involved. I didn't like either outcome, instead decided to use the third approach: have a "fresh enough" copy of the master state readily available for the main queue callers. On the upside - this makes individual view models creation instant. On the down side - it's an extra copy to store in memory and an extra CPU load to keep that copy up to date.

Alternative to having two copies would be to use a single copy protected by a lock - need to play with this idea more to see if this'll fly well.

malhal · April 25, 2023, 11:40am

If you use the View struct hierarchy to divide up your view data as it is designed to be used, instead of a large struct in a custom view model object, then you will benefit from (secret) SwiftUI features like efficient tree invalidation and dependency tracking.

Just query and transform bits of the JSON tree into a new View struct tree and SwiftUI will efficiently keep the UIViews it generates up to date. If you pass transformed data into child Views as lets then SwiftUI will fly.

jeremyabannister · April 25, 2023, 12:58pm

I think I'm suggesting a way to still have things like efficient tree invalidation while at the same time getting to enjoy the advantages of being able to represent your whole state as a single struct (one concrete advantage being one-step persistence).

I have been using SwiftUI since basically day 1, so on the one hand I'm quite familiar with the technology, but I don't claim to have advanced knowledge of its implementation, and therefore maybe you're overall point is correct, that what I'm proposing is fundamentally incompatible with many of the design points of SwiftUI (like "efficient tree invalidation"). However, simply reading your post doesn't convince me that what I'm proposing is incompatible with SwiftUI.

tera · April 26, 2023, 1:58am

Jeremy, I share your vision.

Do we currently have means to somehow collect data accesses, e.g. in the form of key paths?

struct Foo {
    struct Bar {
        struct Baz {
            var qux: Int = 0
            var quux: Int = 0
        }
        var baz: [Baz] = []
    }
    var bar: [String: Bar] = [:]
}

var foo = Foo()

// view body calculation:
startRecordingAccesses()
let x = foo.bar["hello"]!.baz[2].qux
print(x) // use x somehow
let accesses = stopRecordingAccesses()
print(accesses)
// list (or Set) of accesses to foo:
//    read of \Foo.bar["hello"]!.baz[2].qux

// model modification (via view action or external)
startRecordingAccesses()
foo.bar["world"]!.baz[1].quux = 42
let accesses = stopRecordingAccesses()
print(accesses)
// list (or Set) of accesses to foo:
//     write of \Foo.bar["world"]!.baz[1].quux

Once we have this mechanism we could use it to recalculate (and redraw) the views whose data accesses intersect with model data modification accesses.

Edit: I guess I could have my keyPath subscripts on Foo and use those explicitly:

let x = foo[myRecordingSubscript: \Foo.bar["hello"]!.baz[0].qux]
foo[myRecordingSubscript: \Foo.bar["hello"]!.baz[0].qux] = 42

Is there any way my subscripts are getting called when I write simply this?

let x = foo.bar["hello"]!.baz[0].qux
foo.bar["hello"]!.baz[0].qux = 42

Edit 2: checking read / write access intersection when using explicit custom keypath subscripts.

var readAccesses: Set<AnyKeyPath> = []
var writeAccesses: Set<AnyKeyPath> = []

extension Foo {
    subscript<T>(keyPath: KeyPath<Foo, T>) -> T {
        readAccesses.insert(keyPath)
        return self[keyPath: keyPath]
    }
    subscript<T>(keyPath: WritableKeyPath<Foo, T>) -> T {
        get {
            readAccesses.insert(keyPath)
            return self[keyPath: keyPath]
        }
        set {
            writeAccesses.insert(keyPath)
            self[keyPath: keyPath] = newValue
        }
    }
}

var foo = Foo()
let x = foo[\Foo.bar["hello"]!.baz[0].qux]
foo[\Foo.bar["hello"]!.baz[0].qux] = 42
let intersects = !readAccesses.isDisjoint(with: writeAccesses)
print(intersects) // true

tera · April 26, 2023, 3:12am

I found the missing link here.

With the following "access tracking" holder type:

@dynamicMemberLookup
struct AccessTracker<Value> {
    private var value: Value

    init(_ value: Value) {
        self.value = value
    }
    subscript<T>(dynamicMember keyPath: KeyPath<Value, T>) -> T {
        AccessTracker<Never>.readAccesses?.insert(keyPath)
        return value[keyPath: keyPath]
    }
    subscript<T>(dynamicMember keyPath: WritableKeyPath<Value, T>) -> T {
        get {
            AccessTracker<Never>.readAccesses?.insert(keyPath)
            return value[keyPath: keyPath]
        }
        set {
            AccessTracker<Never>.writeAccesses?.insert(keyPath)
            value[keyPath: keyPath] = newValue
        }
    }
}

The following static storage mechanism to track changes:

extension AccessTracker where Value == Never {
    static var readAccesses: Set<AnyKeyPath>?
    static var writeAccesses: Set<AnyKeyPath>?
    
    static func startReadAccessTracking() {
        readAccesses = []
    }
    static func stopReadAccessTracking() -> Set<AnyKeyPath> {
        guard let accesses = readAccesses else {
            fatalError("read access tracking has not been started")
        }
        readAccesses = nil
        return accesses
    }
    static func startWriteAccessTracking() {
        writeAccesses = []
    }
    static func stopWriteAccessTracking() -> Set<AnyKeyPath> {
        guard let accesses = writeAccesses else {
            fatalError("write access tracking has not been started")
        }
        writeAccesses = nil
        return accesses
    }
}

For the following example data structure:

struct Foo {
    struct Bar {
        struct Baz {
            var qux: Int = 0
            var quux: Int = 0
        }
        var baz: [Baz] = [Baz(), Baz()]
    }
    var bar: [String: Bar] = ["hello" : Bar()]
}

I can now write the following code using normal looking read / write accesses without using keypaths explicitly:

var foo = AccessTracker(Foo())
AccessTracker.startReadAccessTracking()
let x = foo.bar["hello"]!.baz[0].qux
let readAccesses = AccessTracker.stopReadAccessTracking()

AccessTracker.startWriteAccessTracking()
foo.bar["hello"]!.baz[0].qux = 42
let writeAccesses = AccessTracker.stopWriteAccessTracking()

and know if write access has changed something that read access was depending upon:

let intersects = !readAccesses.isDisjoint(with: writeAccesses)
print(intersects) // true

Hurray

Edit:

Note that only a single data structure is supported in this code: only key paths are getting recorded, so if you read from "foo1" but write to "foo2" this code would be confused.

Also found a bug in AccessTracker:

do {
    var foo = AccessTracker(Foo())
    
    AccessTracker.startReadAccessTracking()
    let x = foo.bar["hello"]!.baz[0].qux
    let readAccesses = AccessTracker.stopReadAccessTracking()
    
    AccessTracker.startWriteAccessTracking()
    foo.bar["hello"]!.baz[1].qux = 42  // different key path
    let writeAccesses = AccessTracker.stopWriteAccessTracking()
    print(writeAccesses) // [Swift.WritableKeyPath<App.Foo, Swift.Dictionary<Swift.String, App.Foo.Bar>>]
    
    let intersects = !readAccesses.isDisjoint(with: writeAccesses)
    print(intersects) // true
}

Interestingly the code that doesn't use AccessTracker doesn't have this bug:

do {
    var foo = Foo()
    
    AccessTracker.startReadAccessTracking()
    let x = foo.bar["hello"]!.baz[0].qux
    AccessTracker.readAccesses!.insert(\Foo.bar["hello"]!.baz[0].qux)
    let readAccesses = AccessTracker.stopReadAccessTracking()
    
    AccessTracker.startWriteAccessTracking()
    foo.bar["hello"]!.baz[1].qux = 42  // different key path
    AccessTracker.writeAccesses!.insert(\Foo.bar["hello"]!.baz[1].qux)
    let writeAccesses = AccessTracker.stopWriteAccessTracking()
    print(writeAccesses) // [Swift.WritableKeyPath<App.Foo, Swift.Int>]

    let intersects = !readAccesses.isDisjoint(with: writeAccesses)
    print(intersects) // false
}

Notably, keyPaths look different in these two cases, which explains why the bug occurs, but I don't see yet how to fix it.

jeremyabannister · April 26, 2023, 1:12pm

@tera This is awesome - I'm looking forward to having the bandwidth to absorb and consider within a few days

tera · April 26, 2023, 11:14pm

I don't see how to fix AccessTracker, for now will be using the next best thing - explicit keypath usage. Full example that simulates simple model, "view" and "rendering loop" inside OS:

AccessTracker, partly commented out as it doesn't work properly

// @dynamicMemberLookup
struct AccessTracker<Value> {
    // doesn't work 🤔
    /*
    private var value: Value

    init(_ value: Value) {
        self.value = value
    }
    subscript<T>(dynamicMember keyPath: KeyPath<Value, T>) -> T {
        print(keyPath)
        return value[keyPath: keyPath]
    }
    subscript<T>(dynamicMember keyPath: WritableKeyPath<Value, T>) -> T {
        get {
            print(keyPath)
            return value[keyPath: keyPath]
        }
        set {
            print(keyPath)
            value[keyPath: keyPath] = newValue
        }
    }
    */
}

extension AccessTracker where Value == Never {
    static var readAccesses: Set<AnyKeyPath>?
    static var writeAccesses: Set<AnyKeyPath>?
    
    static func startReadAccessTracking() {
        readAccesses = []
    }
    static func stopReadAccessTracking() -> Set<AnyKeyPath> {
        guard let accesses = readAccesses else {
            fatalError("read access tracking has not been started")
        }
        readAccesses = nil
        return accesses
    }
    static func startWriteAccessTracking() {
        writeAccesses = []
    }
    static func stopWriteAccessTracking() -> Set<AnyKeyPath> {
        guard let accesses = writeAccesses else {
            fatalError("write access tracking has not been started")
        }
        writeAccesses = nil
        return accesses
    }
}

AccessTrackable helper protocol for manual key path access tracking

protocol AccessTrackable {}

extension AccessTrackable {
    subscript<T>(keyPath: KeyPath<Self, T>) -> T {
        AccessTracker.readAccesses!.insert(keyPath)
        return self[keyPath: keyPath]
    }
    subscript<T: Equatable>(keyPath: WritableKeyPath<Self, T>) -> T {
        get {
            AccessTracker.readAccesses!.insert(keyPath)
            return self[keyPath: keyPath]
        }
        set {
            // #1 - always record write access:
            AccessTracker.writeAccesses!.insert(keyPath)
            self[keyPath: keyPath] = newValue
            
            // #2 - only record write access on change:
            // (T needs to be Equatable for this to work)
            let oldValue = self[keyPath: keyPath]
            if oldValue != newValue {
                AccessTracker.writeAccesses!.insert(keyPath)
                self[keyPath: keyPath] = newValue
            }
        }
    }
}

Example user model struct conforming to AccessTrackable

struct Foo {
    struct Bar {
        struct Baz {
            var qux = 1
            var quux = 2
        }
        var baz: [Baz] = [Baz(), Baz()]
    }
    var bar: [String: Bar] = ["hello" : Bar()]
}

extension Foo: AccessTrackable {}

View simulation

struct MyView {
    //var foo = AccessTracker(Foo())
    var foo = Foo()

    var body: String {
        let x = foo[\.bar["hello"]!.baz[0].qux]
        return "\(x)"
    }
    mutating func action() {
        let index = Int.random(in: 0 ... 1)
        let value = Int.random(in: 0 ... 1000)
        if Bool.random() {
            print("changing index: \(index) qux to \(value)")
            foo[\.bar["hello"]!.baz[index].qux] = value
        } else {
            print("changing index: \(index) quux to \(value)")
            foo[\.bar["hello"]!.baz[index].quux] = value
        }
    }
}

Render loop simulation

func renderLoop() {
    
    struct ViewRecord {
        var view: MyView
        var content: String = ""
        var readAccesses: Set<AnyKeyPath> = []
        var dirty = true
    }
    
    var views = [ViewRecord(view: MyView())]

    while true {
        for i in 0 ..< views.count {
            if views[i].dirty {
                views[i].dirty = false
                AccessTracker.startReadAccessTracking()
                views[i].content = views[i].view.body
                print("🟢 rendered view: \(views[i].content)")
                views[i].readAccesses = AccessTracker.stopReadAccessTracking()
            }
        }
        
        var hasDirtyViews = false
        for i in 0 ..< views.count {
            // simulating a button press
            if Int.random(in: 0 ... 2) == 0 {
                AccessTracker.startWriteAccessTracking()
                views[i].view.action()
                let writeAccesses = AccessTracker.stopWriteAccessTracking()
                views[i].dirty = !views[i].readAccesses.isDisjoint(with: writeAccesses)
                print(views[i].dirty ? "🟠 will rerender" : "unrelated change - won't rerender")
                hasDirtyViews = hasDirtyViews || views[i].dirty
            } else {
                print("won't call action")
            }
        }
        
        if !hasDirtyViews {
            sleep(1)
        }
    }
}

renderLoop()

If anyone can see a way how to fix AccessTracker or otherwise go from:

foo[\.bar["hello"]!.baz[0].qux] = 42

to

foo.bar["hello"]!.baz[0].qux = 42

please shout. The amount of boilerplate here is not massive (3 extra characters) but it's still unfortunate and having it will be quite error prone in practice as it would be very easy forgetting using keypath form and access tracking won't work.

If this is impossible to do with the currently available language constructs perhaps we could consider introducing a pinpoint language support for this feature.

How does this method answer the questions raised in the other thread:

"would the body be recalculated on state.unrelated changes" - No. Only relevant changes would cause body recalculation, even if they happen deep inside the data structure. †
"if I set state.related variable to the same value, would it cause body recalculation" - could be Yes (with #1 above) or No (with #2 above).

† - the change to the "parent" ketpath e.g. [\.bar["hello"]!.baz[0] or [\.bar["hello"] should be considered changing "child" keypaths like [\.bar["hello"]!.baz[0].qux. We'd probably need to expose some new methods on keypaths to allow this.

tera · April 27, 2023, 3:54pm

How do I check that the two key paths are related?

let a = \Foo.bar["hello"]!.baz[0].qux
let b = \Foo.bar["hello"]!.baz[0]

Changing a value through keypath a will result in a changed data obtained through keypath b and vice versa.

tera · July 17, 2023, 3:46pm

Is there no public way currently?

@Philippe_Hausler did you have to solve this puzzle in the new Observable implementation?

Joe_Groff · July 17, 2023, 3:49pm

In general, you have to be pessimistic and assume they might be related. For struct stored properties, you can check whether the referenced fields overlap by using the MemoryLayout.offset of the key path and MemoryLayout.size of the property type. You might also be able to do dynamic type checks for common cases like Array to see if referenced indexes overlap or something like that.

Philippe_Hausler · July 17, 2023, 3:49pm

There are no public solutions for that; however I have been working on a version that avoids the need for explicit declarations of dependencies to form AsyncSequences of values. But it is worth noting: that is not ready yet and only has a draft implementation. The solution that I have been using for that is to use the access tracking to determine composition.

But that approach only applies to immediate keypath members and not potential overlaps or child key paths.