Call `observeReads()` one or more times, passing i...

# compose

[min]

> Call observeReads() one or more times, passing it a function to observe reads from as well as a callback to execute when any of the read values is changed. Every time the callback is invoked, the set of states being observed is cleared and observeReads() must be called again in order to continue tracking changes.
(Emphasis mine) This explanation doesn’t match what I’m seeing in my experiment

val state = mutableIntStateOf(0)
    val observer = SnapshotStateObserver { f -> f() }
    observer.start()

    val observed = mutableListOf<Int>()
    observer.observeReads(
        scope = Unit,
        block = { kotlin.test.assertEquals(0, state.intValue) },
        onValueChangedForScope = { observed.add(state.intValue) },
    )

    val applications = mutableListOf<Int>()
    repeat(3) {
        applications.add(Snapshot.withMutableSnapshot {
            state.intValue += 1
            state.intValue += 1
            state.intValue
        })
    }
    observer.stop()
    kotlin.test.assertEquals(applications, observed)

This test passes even though I didn’t call observeReads after each run of the onValueChangedForScope lambda. Is the explanation wrong, or have I got something wrong?

[min]

Pardon the ping, @Zach Klippenstein (he/him) [MOD] but I think this is your article, so I’d appreciate it if you could check out the question when you have time. I’m immensely confused because…

val name = mutableStateOf("")
val observer = SnapshotStateObserver { f -> f() }
observer.start()

val observed = mutableListOf<Pair<Int, String>>()
fun onChanged(scope: Int) {
    observed.add(Pair(scope, name.value))
    observer.observeReads(
        scope = scope + 1,
        onValueChangedForScope = ::onChanged,
        block = { name.value },
    )
}
observer.observeReads(
    scope = 0,
    onValueChangedForScope = ::onChanged,
    block = { name.value },
)
Snapshot.withMutableSnapshot {
    name.value = "Fido"
}
Snapshot.withMutableSnapshot {
    name.value = "Fluffy"
}

observer.stop()
Snapshot.withMutableSnapshot {
    name.value = "Fluffy"
}
kotlin.test.assertEquals(observed, listOf(
    Pair(0, "Fido"),
    Pair(1, "Fluffy")
))

…this test fails with the following error.

Expected <[(0, Fido), (0, Fluffy), (1, Fluffy)]>, actual <[(0, Fido), (1, Fluffy)]>.

Doesn’t that suggest it’s unnecessary to call onChanged again and again to keep observing changes?

[min]

@Zach Klippenstein (he/him) [MOD] I have concluded your article is incorrect. The expected outcome you presented in the article is as follows.

// Output:
performing initial read pass
dog name: Spot
starting observation
initial state change
something was changed from pass 0
performing next read pass
dog name: Fido
second state change
something was changed from pass 1
performing next read pass
dog name: Fluffy
stopping
third state change

However I’ve just run your code in my IDE as-is without replacing the println statements with assertions or otherwise making any changes. The actual outcome is as follows.

performing initial read pass
dog name: Spot
starting observation
initial state change
something was changed from pass 0
performing next read pass
dog name: Fido
second state change
something was changed from pass 0
performing next read pass
dog name: Fluffy
something was changed from pass 1
performing next read pass
dog name: Fluffy
stopping
third state change

You can see that the scope 0 observer is also notified of the name change to "Fluffy". I thought I had got something wrong and spent a full day investigating and trying to understand, but perhaps there simply have been some breaking changes to the Snapshot system that now make it behave differently than how it’s explained to in your article, although I don’t know for sure.

[shikasd]

Correct, the states are not cleared after invalidation, it only reset on rerun or when SnapshotStateObserver#clear is called.

[min]

I’m correct that the set of observed states isn’t cleared after each run of the onValueChangedForScope argument, right?

only reset on rerun

Could you show me a short example of this (being cleared on rerun) please? I’m afraid I don’t know what you’re referring to when you say ‘rerun’

[min]

Is the author no longer active in this workspace? His talk also seems to contain an error (as far as I can tell) that has tripped me up. His slide says that applying a snapshot advances the ID of the parent,

Snapshot.global {
    val initId = currentId()
    Snapshot.withMutableSnapshot {
        kotlin.test.assertEquals(initId + 1, currentId())
        Snapshot.global {
            kotlin.test.assertEquals(initId + 2, currentId())
        }

        val nested = Snapshot.takeMutableSnapshot()
        kotlin.test.assertEquals(initId + 4, currentId())
        nested.enter {
            kotlin.test.assertEquals(initId + 3, currentId())
            Snapshot.global {
                kotlin.test.assertEquals(initId + 2, currentId())
            }
        }
        kotlin.test.assertEquals(initId + 4, currentId())
        nested.apply()
        kotlin.test.assertEquals(initId + 4, currentId())
        kotlin.test.assertNotEquals(initId + 5, currentId())
    }
}

…but the last two assertions show that that’s not the case. Unless I’ve misunderstood something (very possible), it seems that an application only advances the parent, if the parent is the root snapshot? I’d appreciate it if anybody more familiar with snapshot could confirm this or tell me how I’m wrong.

[shikasd]

Zach is not the author, this was mostly thought out and implemented by Chuck Jazdzewski

[Zach Klippenstein (he/him) [MOD]]

Good catch, i'll work on fixing it

[min]

@Test fun snapshotIdDemo() {
    fun currentId(): SnapshotId { return Snapshot.current.snapshotId }
    fun globalId(): SnapshotId { return Snapshot.global(::currentId) }
    Snapshot.global {
        val initId = currentId()
        val depth0 = Snapshot.takeMutableSnapshot()
        depth0.enter {
            kotlin.test.assertEquals(initId + 2, globalId())
            kotlin.test.assertEquals(initId + 1, currentId())

            val depth1 = Snapshot.takeMutableSnapshot()
            kotlin.test.assertEquals(initId + 2, globalId())
            kotlin.test.assertEquals(initId + 4, currentId())
            val depth2 = depth1.enter {
                kotlin.test.assertEquals(initId + 3, currentId())
                Snapshot.takeMutableSnapshot()
            }

            kotlin.test.assertEquals(initId + 2, globalId())
            kotlin.test.assertEquals(initId + 4, currentId())
            depth1.enter {
                kotlin.test.assertEquals(initId + 6, currentId())
                depth2.enter { kotlin.test.assertEquals(initId + 5, currentId()) }
                depth2.apply()
                kotlin.test.assertEquals(initId + 6, currentId())
            }

            kotlin.test.assertEquals(initId + 2, globalId())
            kotlin.test.assertEquals(initId + 4, currentId())
            depth1.apply()
            kotlin.test.assertEquals(initId + 7, currentId())
        }

        kotlin.test.assertEquals(initId + 2, currentId())
        depth0.apply()
        kotlin.test.assertEquals(initId + 8, currentId())
        Snapshot.withMutableSnapshot {
            kotlin.test.assertEquals(initId + 10, globalId())
            kotlin.test.assertEquals(initId + 9, currentId())
        }
        kotlin.test.assertEquals(initId + 11, currentId())
    }
}

Upon further investigation, I’ve found that applying a snapshot advances the parent
• IF the parent is the global snapshot (eg 10 -> 11),
• OR the parent has a lower ID than the child (eg 4 -> 7).
In other words, if the parent neither is the global snapshot nor has a lower ID, it’s not advanced (eg 6 -> 6)

[min]

Okay, I’m 90% certain that’s the exact rule thanks to this new piece of evidence

[min]

@Chuck Jazdzewski [G] Pardon the ping, but I’ve been told that you’re the person who designed and implemented the snapshot system. I’m trying to understand its behaviour better, and have tried to read the source code, but I find it deeply complicated and would like to ask you a couple questions.
1. My understanding is that creating a snapshot advances the parent, but I see no code that implements such behaviour in Snapshot.takeMutableSnapshot() for example. I’ve given up following the call graph would appreciate some pointers.

// ...
return creatingSnapshot(this, readObserver, writeObserver, readonly = false) {
    actualReadObserver,
    actualWriteObserver ->
    advance {
        sync {
            val newId = nextSnapshotId
            nextSnapshotId += 1
            openSnapshots = openSnapshots.set(newId)
            val currentInvalid = invalid
            this.invalid = currentInvalid.set(newId)
            NestedMutableSnapshot(
                newId, // I understand this gives the child the next highest ID.
                       // But who then gives the next highest ID to the parent?
                currentInvalid.addRange(snapshotId + 1, newId),
                mergedReadObserver(actualReadObserver, this.readObserver),
                mergedWriteObserver(actualWriteObserver, this.writeObserver),
                this,
            )
        }
    }
}

2. My understanding is that applying a snapshot advances the parent IF the parent is the global snapshot OR the parent has a lower ID than the child. I have identified (I think) the code that implements the OR case behaviour in the apply method of MutableNestedSnapshot, but I cannot locate code that implements the IF case behaviour. I’d appreciate any insights

override fun apply(): SnapshotApplyResult {
    // ...
    sync {
        // ...

        // Ensure the parent is newer than the current snapshot
        if (parent.snapshotId < id) {
            parent.advance()
        }

        // ...
    }

    applied = true
    deactivate()
    dispatchObserverOnApplied(this, modified)
    return SnapshotApplyResult.Success
}

3. The apply method above includes a call to innerApplyLocked. That method includes the following let call, and I don’t understand why we’re advancing the current snapshot here.

mergedRecords?.let {
    // Ensure we have a new snapshot id
    advance()

    // Update all the merged records to have the new id.
    it.fastForEach { merged ->
        val (state, stateRecord) = merged
        stateRecord.snapshotId = nextId
        sync {
            stateRecord.next = state.firstStateRecord
            state.prependStateRecord(stateRecord)
        }
    }
}

I have been unable to find any comprehensive docs that explain the behaviour the system in plain English, so I’ve had to dive into the codebase, but its behaviour is split up and spread out between a lot of small things that are tightly coupled, so I’m struggling to make sense of it.

[Chuck Jazdzewski [G]]

I am confused by (1) and (2) as you ask for where to find this code that does what you ask but the code you quote is exactly the code you are looking for. I am uncertain what you were expecting to find, maybe you could explain what you thought would be there that you didn't find.

For example, (1) includes a call to advance { which is the call that advances the snapshot. Advancing the snapshot is a rather trivial operation that changes ID to the highest snapshot number and ensures that all open snapshots prior to it are explicitly excluded. It does this when a new snapshot is taken to ensure that the child snapshot will see all changes made to the parent at up to the point of the snapshot but not after.

For (2), the code you are looking for is the if statement you quote. The parent doesn't need to advance if changes in the parent are already not visible to the child.

Snapshots is an implement of the MVCC algorithm. An explanation of the underlying principle behind the snapshot system can be found here https://en.wikipedia.org/wiki/Multiversion_concurrency_control. The comments do not explain this algorithm as it is fairly well-known and external sources explain it better than I could. This doesn't cover some of the details around nested transactions (which I call snapshots as snapshots are not durable) but @Zach Klippenstein (he/him) [MOD] explains this better than I could in his talks and blog posts.

For (3), this is to implement `SnapshotMutationPolicy`'s merge method which can be used to implement conflict free data types. By default, any modification to a value is considered conflicting with the same value modified in another snapshot. Through a mutation policy you can define that two snapshot that change the value can be merged. This can result in a third value that includes the changes made by both snapshots. I give an example for this in the documentation regarding the count of a set of physical items where snapshot A and snapshot B can both consume or produce a physical items without conflict. You can learn more about this here (https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type). Any CFRD an be implemented by this mechanism as well as non-replicating conflict free values such a count of resources.

For why (3) needs to advance the snapshot here is because, taking a count as an example, if you decrement the count in both A and B, merging them means adjusting the value by the sum of the differences (e.g. if foo is a mergable count then foo = foo - 2 in A and foo = foo - 3 in B would merge to produce foo = foo - 5. If foo starts at 10 then A sees `8`and B sees 7 but the merged value is 5.) Since neither A or B has seen the new value (5 in the example), a new snapshot ID is required to contain the merged value. Advancing the snapshot allocates this new snapshot.

[min]

Massive thanks for the detailed response, @Chuck Jazdzewski [G]!
1. I was several days into the investigation and must have been tunnel visioning. I see now that the call to advance is what advances the parent snapshot on snapshot creation. Thanks for pointing me to it!
2. I’m not sure how the quoted if statement handles all cases.

fun currentId(): SnapshotId { return Snapshot.current.snapshotId }
fun globalId(): SnapshotId { return Snapshot.global(::currentId) }
Snapshot.global {
    val initId = globalId()
    Snapshot.withMutableSnapshot {
        kotlin.test.assertEquals(initId + 2, globalId())
        kotlin.test.assertEquals(initId + 1, currentId())
    }
    kotlin.test.assertEquals(initId + 3, globalId())
}

This shows that the parent is advanced even if parent.snapshotId < id is false and the parent.advance() call is thus skipped. Am I even correct in understanding that the rule is that the parent is advanced IF it is the global snapshot, OR it has a lower ID than the child? If so, where is the part before the OR implemented?
3. Sorry, I still don’t understand.

fun currentId(): SnapshotId { return Snapshot.current.snapshotId }
fun globalId(): SnapshotId { return Snapshot.global(::currentId) }
Snapshot.global {
    val initId = globalId()
    val state = MyIntState.new(0) { prev, curr, next ->
        val currDiff = curr - prev
        val nextDiff = next - prev
        prev + currDiff + nextDiff
    }
    val snap0 = Snapshot.takeMutableSnapshot()
    snap0.enter {
        kotlin.test.assertEquals(initId + 2, globalId())
        kotlin.test.assertEquals(initId + 1, currentId())
    }
    val snap1 = Snapshot.takeMutableSnapshot()
    snap1.enter {
        kotlin.test.assertEquals(initId + 4, globalId())
        kotlin.test.assertEquals(initId + 3, currentId())
    }

    kotlin.test.assertEquals(0, state.read())
    kotlin.test.assertEquals(initId + 4, globalId())
    snap0.enter { state.write(3) }; snap0.apply()
    kotlin.test.assertEquals(3, state.read())
    kotlin.test.assertEquals(initId + 5, globalId())
    snap1.enter { state.write(5) }; snap1.apply()
    kotlin.test.assertEquals(8, state.read())
    kotlin.test.assertEquals(initId + 7, globalId())
}

Why couldn't the globalId() have returned initId + 6 in the last assertion? It seems we’re advancing snap1 from initId + 3 to initId + 6, and applying it to the global snapshot which is then advanced to initId + 7. Am I correct, and if so, why?

[min]

fun currentId(): SnapshotId { return Snapshot.current.snapshotId }
fun globalId(): SnapshotId { return Snapshot.global(::currentId) }
fun myIntStateOf(arg: Int): MyIntState {
    return MyIntState.new(arg) { prev, curr, next ->
        val currDiff = curr - prev
        val nextDiff = next - prev
        prev + currDiff + nextDiff
    }
}
Snapshot.global {
    val initId = globalId()
    val state = myIntStateOf(0)
    val snap0 = Snapshot.takeMutableSnapshot()
    snap0.enter {
        kotlin.test.assertEquals(initId + 2, globalId())
        kotlin.test.assertEquals(initId + 1, currentId())
    }
    val snap1 = Snapshot.takeMutableSnapshot()
    snap1.enter {
        kotlin.test.assertEquals(initId + 4, globalId())
        kotlin.test.assertEquals(initId + 3, currentId())
    }

    kotlin.test.assertEquals(0, state.read())
    kotlin.test.assertEquals(initId + 4, globalId())
    kotlin.test.assertEquals(actual = state.inspect(), expected = mapOf(
        Pair(initId, 0),
    ))
    snap0.enter { state.write(10) }; snap0.apply()
    kotlin.test.assertEquals(10, state.read())
    kotlin.test.assertEquals(initId + 5, globalId())
    kotlin.test.assertEquals(actual = state.inspect(), expected = mapOf(
        Pair(initId, 0),
        Pair(initId + 1, 10),
    ))
    snap1.enter { state.write(20) }; snap1.apply()
    kotlin.test.assertEquals(30, state.read())
    kotlin.test.assertEquals(initId + 7, globalId())
    kotlin.test.assertEquals(actual = state.inspect(), expected = mapOf(
        Pair(initId, 30),
        Pair(initId + 1, 30),
        Pair(initId + 3, 30),
        Pair(initId + 5, 30),
    ))
}
Snapshot.global {
    val initId = globalId()
    val state = myIntStateOf(0)
    Snapshot.withMutableSnapshot {
        kotlin.test.assertEquals(initId + 2, globalId())
        kotlin.test.assertEquals(initId + 1, currentId())
        val nested0 = Snapshot.takeMutableSnapshot()
        kotlin.test.assertEquals(initId + 2, globalId())
        kotlin.test.assertEquals(initId + 4, currentId())
        nested0.enter { kotlin.test.assertEquals(initId + 3, currentId()) }
        val nested1 = Snapshot.takeMutableSnapshot()
        kotlin.test.assertEquals(initId + 2, globalId())
        kotlin.test.assertEquals(initId + 6, currentId())
        nested1.enter { kotlin.test.assertEquals(initId + 5, currentId()) }

        kotlin.test.assertEquals(0, state.read())
        kotlin.test.assertEquals(initId + 6, currentId())
        kotlin.test.assertEquals(actual = state.inspect(), expected = mapOf(
            Pair(initId, 0),
        ))
        nested0.enter { state.write(10) }; nested0.apply()
        kotlin.test.assertEquals(10, state.read())
        kotlin.test.assertEquals(initId + 6, currentId())
        kotlin.test.assertEquals(actual = state.inspect(), expected = mapOf(
            Pair(initId, 0),
            Pair(initId + 3, 10),
        ))
        nested1.enter { state.write(20) }; nested1.apply()
        kotlin.test.assertEquals(30, state.read())
        kotlin.test.assertEquals(initId + 6, currentId())
        kotlin.test.assertEquals(actual = state.inspect(), expected = mapOf(
            Pair(initId, 0),
            Pair(initId + 3, 10),
            Pair(initId + 5, 20),
            Pair(initId + 6, 30),
        ))
    }
}

Profoundly confused by the behaviour I’m observing here. What on earth could possibly be happening?
• Applying to the global snapshot unconditionally advances it (already behaviour that I’ve observed but yet to be able to substantiate with code evidence), two IDs if merged records are present?
• Applying to the global snapshot when there are merged records corrupts all existing records? See the assertion where every value is 30. Also the IDs in the map make no sense either.
• Applying to a nested snapshot only advances it if the parent has a lower ID than the child, even if there are merged records?

[min]

How exactly do IDs behave? Every experiment absolutely shatters the expectations suggested by the one before, and I’ve been unable to find any documentation that spells it out in prose.

[min]

typealias FnMergeInts = (Int, Int, Int) -> Int?
class MyIntState private constructor(
    private var head: MyIntRecord,
    private val mergeInts: FnMergeInts?,
    private val map: MutableMap<SnapshotId, WeakReference<MyIntRecord>>,
): StateObject {
    companion object {
        fun new(arg: Int, mergeInts: FnMergeInts? = null): MyIntState {
            val map = mutableMapOf<SnapshotId, WeakReference<MyIntRecord>>()
            return MyIntState(
                head = MyIntRecord.new(arg, map),
                mergeInts = mergeInts,
                map = map,
            )
        }
    }
    override val firstStateRecord: StateRecord get () { return this.head }
    override fun prependStateRecord(value: StateRecord) {
        this.head = value as MyIntRecord
    }
    override fun mergeRecords(
        previous: StateRecord,
        current: StateRecord,
        applied: StateRecord,
    ): StateRecord? {
        return this.mergeInts?.invoke(
            (previous as MyIntRecord).prop,
            (current as MyIntRecord).prop,
            (applied as MyIntRecord).prop,
        )
            ?.let { prop ->
                MyIntRecord.new(prop = prop, map = this.map)
            }
    }

    fun read(): Int { return this.head.readable(this).prop }
    fun write(arg: Int) {
        fun update(record: MyIntRecord) { record.prop = arg }
        this.head.writable(this, ::update)
    }
    fun inspect(): Map<SnapshotId, Int> {
        return this.map
            .mapNotNull { (id, maybeRecord) ->
                maybeRecord.get()?.let { record -> Pair(id, record.prop) }
            }
            .toMap()
    }

    private class MyIntRecord private constructor(
        var prop: Int,
        val map: MutableMap<SnapshotId, WeakReference<MyIntRecord>>,
    ): StateRecord() {
        companion object {
            fun new(prop: Int, map: MutableMap<SnapshotId, WeakReference<MyIntRecord>>): MyIntRecord {
                val self = MyIntRecord(prop = prop, map = map)
                map[Snapshot.current.snapshotId] = WeakReference(self)
                return self
            }
        }

        override fun assign(value: StateRecord) {
            this.prop = (value as MyIntRecord).prop
        }
        override fun create(): StateRecord {
            return MyIntRecord.new(this.prop, this.map)
        }
    }
}

Here’s MyIntState for reference in case it’s my implementation that’s messing something up.

[min]

Instead of the following,

kotlin.test.assertEquals(actual = state.inspect(), expected = mapOf(
        Pair(initId, 30),
        Pair(initId + 1, 30),
        Pair(initId + 3, 30),
        Pair(initId + 5, 30),
    ))

I was expecting to see the following

kotlin.test.assertEquals(actual = state.inspect(), expected = mapOf(
        Pair(initId, 0),
        Pair(initId + 1, 10),
        Pair(initId + 3, 20),
        Pair(initId + 6, 30),
    ))

Because everything else I’ve seen has led me to suspect that applying a snapshot advances the parent
• IF the parent is the global snapshot (2 IDs at that if merges are present)
• OR the parent has a lower ID than the child
Although I can still only substantiate the OR part of this claim with evidence (no docs, can’t find code)

[Chuck Jazdzewski [G]]

The assertions you are making about the snapshot ID are not valid for a number of reasons. The only constraint on the ID of a snapshot is that new snapshots have a greater ID than previous snapshots. The ID of a snapshot may change overtime but what is important as the effect on the which record is considered valid. This is a combination of the ID and the invalid ID sets. The ID is an arbitrary point in time where record with an ID greater than the snapshot ID are invalid. An ID less than the snapshot is valid if it is not explicitly invalid. The ID is effectively the timestamp of when the snapshot was taken. Any assertions over how fast or slow this number changes are invalid as long as the constraint that it is monotonically increasing is preserved. When a snapshot advances or the implications to the global snapshot's ID are should be viewed as implementation details that may change in the future.

As for stating the IDs are corrupted. They are not. It is critical that the snapshots provide the MVCC model, perform well, and use as little memory as practicable. To do this, the implementation is rather intricate in places. For example, the fact that the ID of a record changes is not "corruption" but record reuse. When the snapshot system determines that a snapshot ID has been retired (it has been applied or abandoned) the records that are only visible to it are eligible to be reused. This is a case where the records are no longer visible and were cleared by copying the current record to all of the now record for reuse. It is important we do this to avoid holding on to reference passed the point when they are needed.

[min]

@Chuck Jazdzewski [G] Thanks for the reply again. I hate to be persistent, but I must ask, because while the exact IDs might be an implementation detail, which is fine, applying a snapshot is a public API operation, as is observing reads and writes. Currently, when merges are present:
• Applying to the global snapshot observes the merged value
• Applying to an intermediate snapshot observes the child value.
I find this behaviour inconsistent to the point where it’s unclear whether it’s intended or a bug. The following code demonstrates the first bullet point:

fun currentId(): SnapshotId { return Snapshot.current.snapshotId }
fun globalId(): SnapshotId { return Snapshot.global(::currentId) }
fun myIntStateOf(arg: Int): MyIntState {
    return MyIntState.new(arg) { prev, curr, next ->
        val currDiff = curr - prev
        val nextDiff = next - prev
        prev + currDiff + nextDiff
    }
}
Snapshot.global {
    val state = myIntStateOf(0)
    val applications = mutableListOf<Pair<SnapshotId, Int>>()
    Snapshot.registerApplyObserver { set, snapshot ->
        if (!set.contains(state)) { return@registerApplyObserver }
        applications.add(snapshot.enter { Pair(currentId(), state.read()) })
    }

    val initId = globalId()
    val writes0 = mutableListOf<Pair<SnapshotId, Int>>()
    val snap0 = /* id = initId + 1 */ Snapshot.takeMutableSnapshot(writeObserver = { target ->
        if (target != state) { return@takeMutableSnapshot }
        writes0.add(Pair(currentId(), state.read()))
    })
    val writes1 = mutableListOf<Pair<SnapshotId, Int>>()
    val snap1 = /* id = initId + 3 */ Snapshot.takeMutableSnapshot(writeObserver = { target ->
        if (target != state) { return@takeMutableSnapshot }
        writes1.add(Pair(currentId(), state.read()))
    })

    kotlin.test.assertEquals(initId + 4, globalId())
    snap0.enter { state.write(10) }; snap0.apply()
    kotlin.test.assertEquals(initId + 5, globalId())
    kotlin.test.assertEquals(10, state.read())
    kotlin.test.assertEquals(actual = applications, expected = listOf(
        Pair(initId + 1, 10)
    ))
    kotlin.test.assertEquals(actual = writes0, expected = listOf(
        Pair(initId + 1, 10)
    ))
    kotlin.test.assertEquals(actual = writes1, expected = listOf())

    snap1.enter { state.write(20) }; snap1.apply()
    kotlin.test.assertEquals(initId + 7, globalId())
    kotlin.test.assertEquals(30, state.read())
    kotlin.test.assertEquals(actual = applications, expected = listOf(
        Pair(initId + 1, 10),
        Pair(initId + 6, 30),
    ))
    kotlin.test.assertEquals(actual = writes0, expected = listOf(
        Pair(initId + 1, 10)
    ))
    kotlin.test.assertEquals(actual = writes1, expected = listOf(
        Pair(initId + 3, 20),
    ))

The assertions after snap1.apply() show that
• snap1 wrote, when initId + 3 was its ID, 20 to the state
• An initId + 6 snapshot had written 30 to the state and was applied to the global snapshot.
The following code demonstrates the second bullet point:

state.write(0)
    val writes2 = mutableListOf<Pair<SnapshotId, Int>>()
    val snap2 = /* id = initId + 8 */ Snapshot.takeMutableSnapshot(writeObserver = { target ->
        if (target != state) { return@takeMutableSnapshot }
        writes2.add(Pair(currentId(), state.read()))
    })
    snap2.enter {
        val nestedWrites0 = mutableListOf<Pair<SnapshotId, Int>>()
        val nested0 = /* id = initId + 10 */ Snapshot.takeMutableSnapshot(writeObserver = { target ->
            if (target != state) { return@takeMutableSnapshot }
            nestedWrites0.add(Pair(currentId(), state.read()))
        })
        val nestedWrites1 = mutableListOf<Pair<SnapshotId, Int>>()
        val nested1 = /* id = initId + 12 */ Snapshot.takeMutableSnapshot(writeObserver = { target ->
            if (target != state) { return@takeMutableSnapshot }
            nestedWrites1.add(Pair(currentId(), state.read()))
        })

        nested0.enter { state.write(100) }; nested0.apply()
        kotlin.test.assertEquals(100, state.read())
        kotlin.test.assertEquals(actual = writes2, expected = listOf(
            Pair(initId + 10, 100)
        ))
        kotlin.test.assertEquals(actual = nestedWrites0, expected = listOf(
            Pair(initId + 10, 100)
        ))
        kotlin.test.assertEquals(actual = nestedWrites1, expected = listOf())

        nested1.enter { state.write(200) }; nested1.apply()
        kotlin.test.assertEquals(300, state.read())
        kotlin.test.assertEquals(actual = writes2, expected = listOf(
            Pair(initId + 10, 100),
            Pair(initId + 12, 200),
        ))
        kotlin.test.assertEquals(actual = nestedWrites0, expected = listOf(
            Pair(initId + 10, 100),
        ))
        kotlin.test.assertEquals(actual = nestedWrites1, expected = listOf(
            Pair(initId + 12, 200),
        ))
    }
    snap2.apply()
}

The assertions after nested1.apply() show that
• nested1 wrote, when initId + 12 was its ID, 200 to the state
• The initId + 12 snapshot, having written 200 to the state, was applied to the intermediate snapshot.
See the inconsistency?
• An initId + 6 snapshot had written 30 to the state and was applied to the global snapshot.
• The initId + 12 snapshot, having written 200 to the state, was applied to the intermediate snapshot.
On application, the global snapshot observes the merged value (30), and the intermediate snapshot observes the child value (200). In the latter case, the write of 300 to the state went unobserved. I find this behaviour extremely confusing and am uncertain this isn’t a bug, because everything _this-is-an-implementation-detail_s its way out of establishing a coherent mental model of the system that could have at least explained the underlying rules that lead to this behaviour if it is indeed intended. I am deeply frustrated because after days of research and running experiments, I still have no idea who I can expect to observe what when, even if I accept that the exact IDs are an implementation detail and can be any values the system sees fit for as long as applying a snapshot guarantees the parent has a larger ID. What are the rules?

[Chuck Jazdzewski [G]]

I am unclear what you mean by "the write of`300`to the state when unobserved". By whom? If you mean the apply observer then that is by design as the apply observer only observes changes to the global snapshot. As the change occurs in a nested snapshot, it is not visible to the global snapshot yet. The apply observers are only notified when an apply occurs on the global snapshot. The intent is to observe changes to global state, not nested snapshot state.

"...even if I accept that the exact IDs are an implementation detail and can be any values the system sees fit for as long as applying a snapshot guarantees the parent has a larger ID. What are the rules?

The rules is as I stated them above. The only thing that maters is what the `valid`function returns. valid is true when a record is potentially visible to the snapshot. This is currently when the record id (the snapshot a record was created in) is less than or equal to its own snapshot and not explicitly made invalid by being in the `invalid`set. readable returns the newest valid record (i.e. with the highest id) .

Snapshots could be implemented by each snapshot having just an `invalid`set and, as new snapshots are added, they are added to every snapshot's invalid set. Using the snapshot id relative value is effectively the same thing. As new snapshots always have ids greater than previous snapshots new snapshots are effectively added to the set of invalid snapshots of older snapshots. The manipulation of these number is just a trick to avoid having to maintain a list of snapshots and updating them whenever a new one is created. What is important is which record is valid and which is not. How this is determined is not visible through public API.

With this in mind, you must ignore the snapshotId. It is an implementation detail that may be useful when debugging but should never be used in a way that changes the behavior of the application as you don't have enough public information to reason about it. The values returned by a state object is the only contract (e.g. what is returned by readable and writable). What the snapshotId is an at any time is an implementation detail.

The general rule for snapshots are that snapshots see only the values the parent snapshot had at the point the snapshot was taken, all changes that have been explicitly made to them, and all changes from nested snapshots applied into them. They are isolated from all other changes. When a changes is applied to a snapshot, all the changes applied are seen as one atomic change. In other words, snapshots are atomic, consistent and isolated. The guarantees are to the snapshot instances, not to what id they may have at any moment.

[min]

@Chuck Jazdzewski [G], Thank you for your patience. I understand that snapshot IDs are an implementation detail, and my followup wasn't about them. My message was rather lengthy, so I think you might have got lost while skimming. In the demo for the first bullet point, the global snapshot parented snap0 and snap1. All writes to state in the global snapshot, snap0, and snap1 were recorded in applications, writes0, and writes1 respectively. Under this setup, the following writes were observed and recorded:
1. snap0.enter { state.write(10) } in `writes0`; 10 was recorded.
2. snap0.apply() in `applications`; 10 was recorded.
3. snap1.enter { state.write(20) } in `writes1`; 20 was recorded.
4. snap1.apply() in `applications`; 30 (merged) was recorded.
For the second bullet point, the global snapshot parented snap2, which in turn parented nested0 and nested1. All writes to state were recorded in writes2, nestedWrites0, and nestedWrites1 respectively. The following writes were then observed and recorded:
1. nested0.enter { state.write(100) } in `nestedWrites0`; 100 was recorded.
2. nested0.apply() in `writes2`; 100 was recorded.
3. nested1.enter { state.write(200) } in `nestedWrites1`; 200 was recorded.
4. nested1.apply() in `writes2`; 200 (not merged) was recorded.
As you can see,
• The first demo observed both written values (10 in writes0, and 20 in writes1) and the merged value (30 in applications)
• But the second only observed the written values (100 in nestedWrites0, and 200 in nestedWrites1) and the merged value (300) went unobserved by both nestedWrites1 and writes2.
> By whom? If you mean the apply observer then that is by design…
You can see no part of the demo attempted to record the write of 300 in applications on nested1.apply().

nested1.enter { state.write(200) }; nested1.apply()
        kotlin.test.assertEquals(300, state.read())
        kotlin.test.assertEquals(actual = writes2, expected = listOf(
            Pair(initId + 10, 100),
            Pair(initId + 12, 200),
        ))
        kotlin.test.assertEquals(actual = nestedWrites0, expected = listOf(
            Pair(initId + 10, 100),
        ))
        kotlin.test.assertEquals(actual = nestedWrites1, expected = listOf(
            Pair(initId + 12, 200),
        ))

So 300 was read from the state after nested1.apply(), even though no write of 300 to state had been recorded.

[Chuck Jazdzewski [G]]

There was no write of 300 (or 30). It's a value that was produced by the merge lambda given to MyIntState. This reflects the merge policy of the type which interprets changes to the value as a delta, not the literal values. In this case writing 200 means increase MyIntState by 200 and a write of 100 means increase it by 100. Therefore a merge of these two requests is an increase of the MyIntState instance to 300 (i.e. 100 + 200). If you remove the merge policy you will get a merge conflict as one snapshot writes 100 and the other writes 200. Only one can succeed. A merge policy allows snapshots that would otherwise collide to produce a merged value instead of failing. This merging happens when the snapshot is applied. Also the statement (4) above about `nested1.apply()`in `write2`is misleading, at least from what I can tell. The value of state is 300 after the `nested1.apply()`which is asserted by `kotlin.test.assertEquals(300, state.read())`above. This means it is consistent the 10, 20 case above it.

[min]

In the case of applying snap0 and snap1 to the global snapshot with a conflict, all of 10, 20, and 30 were observed by their observers. In the case of applying nested0 and nested1 to snap2 however, only 100 and 200 were observed by their observers, and 300 went unobserved. I’m struggling to understand what part of this isn’t inconsistent, or which observer you think observed the 300.

[Chuck Jazdzewski [G]]

That is because you registered an apply observer for the global which sees all changes and write observers in the nested snapshots which observe writes to in the snapshot. These are not the same thing and have different behavior as you point out. Merges are not writes, as I discussed above, but they are changes. Snapshots do not have apply observers (which would see these changes), only the global snapshot does,

Read observers observe calls to readable and write observers observes calls to writable. The apply observer observes calls to apply of the global snapshot. The changes show up in a apply observer because it was applied to the global snapshot. They do not show up to a write observer as they were not written to by the snapshot that had the write observer. The merged values were "written" in a synthetic snapshot implied by the merge.

[min]

That almost makes sense, but the inconsistency persists even when I use Snapshot.registerGlobalWriteObserver, not Snapshot.registerApplyObserver.

@Test fun myIntStateTest() {
    val state = MyIntState.accumulate(0) // Each write increments
    val snap0 = Snapshot.takeMutableSnapshot()
    val snap1 = Snapshot.takeMutableSnapshot()

    snap0.enter { state.write(10) }; snap0.apply()
    snap1.enter { state.write(20) }; snap1.apply()
    kotlin.test.assertEquals(30, state.read())
}

@Test fun globalObserverTest() {
    val state = MyIntState.accumulate(0)
    val writes = mutableListOf<Int>()
    Snapshot.registerGlobalWriteObserver { target ->
        if (target != state) {return@registerGlobalWriteObserver }
        writes.add((target as MyIntState).read())
    }

    val snap0 = Snapshot.takeMutableSnapshot()
    val snap1 = Snapshot.takeMutableSnapshot()
    snap0.enter { state.write(10) }; snap0.apply()
    snap1.enter { state.write(20) }; snap1.apply()
    kotlin.test.assertEquals(30, state.read())
    kotlin.test.assertEquals(listOf(), writes)
}

@Test fun localObserverTest() {
    val state = MyIntState.accumulate(0)
    val writes = mutableListOf<Int>()
    val pivot = Snapshot.takeMutableSnapshot(writeObserver = { target ->
        if (target != state) { return@takeMutableSnapshot }
        writes.add((target as MyIntState).read())
    })

    pivot.enter {
        val snap0 = Snapshot.takeMutableSnapshot()
        val snap1 = Snapshot.takeMutableSnapshot()
        snap0.enter { state.write(100) }; snap0.apply()
        snap1.enter { state.write(200) }; snap1.apply()
        kotlin.test.assertEquals(300, state.read())
        kotlin.test.assertEquals(listOf(100, 200), writes)
    }
}

Now both the global snapshot and pivot have a write observer. Still,
• In globalObserverTest, writes does not record snap0.apply() and snap1.apply().
• In localObserverTest, writes does record snap0.apply() and snap1.apply().

[Chuck Jazdzewski [G]]

This is inconsistent but intentionally so. Nested snapshot read and write observers will call the parent snapshot read and write observers. This should be optional behavior since, as you point out, it is inconsistent with the global snapshot. I will create a feature request to make this behavior optional.

[Chuck Jazdzewski [G]]

b/492143967

[min]

I just wanted to understand the system and wasn’t trying to request any specific features, but thanks for having such a close look and taking the feedback into account nevertheless. I guess what happens on apply is:
• Advances the parent once.
◦ Unconditionally if the parent is the global snapshot.
◦ Otherwise if necessary for the parent to be greater than the child.
• Resolves merges in an implied intermediate snapshot.
• If the parent is a nested snapshot, notifies* its write observer of its values before they’re merged.
• If the parent is the global snapshot, notifies its apply observer of merged values.
*Will be optional once b/492143967 is accepted.

[Chuck Jazdzewski [G]]

Not exactly. The write observers are notified synchronously in the call to writable. For example, someIntState.value = 10 will call the write observer immediately. Same with read observers, they are called immediately during readable. Read and write observers are ignored during apply.

Like I said above, write observers and apply observers are two entirely different things. They are inconsistent because they are different. You should only use apply observers when observing for changes. Write observers should be almost never be used. For example, they are needed for the global snapshot manager (to know when to schedule an advance of the global snapshot) but are not used for anything else in Compose.

The pattern is to use a read observer to detect which objects an expression reads and an apply observer to detect when the state objects the expression read change. The write observer should not be used for observation. As you point out, write observers are incomplete for this as they only are notified when a write occurs; not when the object changes. Also they will be notified of write even if the write eventually is abandoned and they are called redundantly (multiple time, once for each write). Write observers are both called to little and to much. Apply observers, on the other hand, will see every object that has changed and only the objects that have changed (e.g. not snapshot that are abandoned) and are called once per non-nested snapshot apply (or global advance).

The snapshot id is only relevant to understand how the snapshot system delivers on the promise of consistent, atomic, and isolated changes. It otherwise should be ignored.

[min]

I’m not sure what you’re saying I’ve got wrong.

val policy = object: SnapshotMutationPolicy<Int> {
    override fun equivalent(a: Int, b: Int): Boolean {
        return a == b
    }
    override fun merge(previous: Int, current: Int, applied: Int): Int {
        val currDiff = current - previous
        val nextDiff = applied - previous
        return previous + currDiff + nextDiff
    }
}

My understanding of apply is that, if the parent is the global snapshot, it notifies the ⓐ apply observers ⓑ after merging, as evidenced by the following empirical observation.

Snapshot.global {
    val state = mutableStateOf(0, policy = policy)
    val applications = mutableListOf<Int>()
    Snapshot.registerApplyObserver { targets, snapshot ->
        if (targets.contains(state)) { applications.add(snapshot.enter { state.value }) }
    }
    val writes = mutableListOf<Int>()
    Snapshot.registerGlobalWriteObserver { target ->
        if (target == state) { writes.add(state.value) }
    }

    val snap0 = Snapshot.takeMutableSnapshot()
    val snap1 = Snapshot.takeMutableSnapshot()
    snap0.enter { state.value = 10 }; snap0.apply()
    snap1.enter { state.value = 20 }; snap1.apply()
    kotlin.test.assertEquals(30, state.value)
    kotlin.test.assertEquals(actual = /* ⓐ */ applications, expected = listOf(10, /* ⓑ */ 30))
    kotlin.test.assertEquals(actual = writes, expected = listOf())
}

And if the parent is a nested snapshot, it notifies the ⓒ write observer ⓓ before merging, as evidenced by the following empirical observation.

val state = mutableStateOf(0, policy = policy)
val writes = mutableListOf<Int>()
val parent = Snapshot.takeMutableSnapshot(writeObserver = { target ->
    if (target == state) { writes.add(state.value) }
})
parent.enter {
    val snap0 = Snapshot.takeMutableSnapshot()
    val snap1 = Snapshot.takeMutableSnapshot()
    snap0.enter { state.value = 10 }; snap0.apply()
    snap1.enter { state.value = 20 }; snap1.apply()
    kotlin.test.assertEquals(30, state.value)
    kotlin.test.assertEquals(actual = /* ⓒ */ writes, expected = listOf(10, /* ⓓ */ 20))
}

These explain the last two points in my list in the previous message:

• If the parent is a nested snapshot, notifies* its write observer of its values before they’re merged.

• If the parent is the global snapshot, notifies its apply observer of merged values.

*Will be optional once b/492143967 is accepted.

In conclusion, the behaviour of apply is such that different things (ⓐ & ⓒ) are notified at different points in time (ⓑ & ⓓ), depending on the parent snapshot.

Read and write observers are ignored during apply.

But this seems to be in direct contradiction, namely of ⓒ and ⓓ, which confuses me.

The write observers are notified synchronously in the call to writable

Are you just trying to say that applying to a nested snapshot is equivalent to writing (ⓒ) all diffs to it before merging (ⓓ)?

Write observers should be almost never be used. For example, they are needed for the global snapshot manager (to know when to schedule an advance of the global snapshot) but are not used for anything else in Compose.

Are you referring to this in GlobalSnapshotManager.ensureStarted?

val channel = Channel<Unit>(1)
CoroutineScope(AndroidUiDispatcher.Main).launch {
    channel.consumeEach {
        sent.set(false)
        Snapshot.sendApplyNotifications()
    }
}
Snapshot.registerGlobalWriteObserver {
    if (sent.compareAndSet(false, true)) {
        channel.trySend(Unit)
    }
}

Or this in Recomposer.composing?

val snapshot =
    Snapshot.takeMutableSnapshot(
        readObserverOf(composition),
        writeObserverOf(composition, modifiedValues),
    )
try {
    return snapshot.enter(block)
} finally {
    applyAndCheck(snapshot)
}

Either way, there’s more than one write observer in Compose that I know of, so I’m not sure what you meant in your explanation. I’ve only been told that you’re the primary architect of the snapshot system, so I don’t know how involved you are in the rest of Compose, but if you happen to be familiar with the use of snapshots in it, I’d appreciate it if you could also have a look at this.

[Chuck Jazdzewski [G]]

> But this seems to be in direct contradiction, namely of ⓒ and ⓓ, which confuses me.
The test is incomplete. The write observer is called earlier than the call to apply. The test just test if it occurred at all, not when. Your test seems to conflate write and apply observers. As I said, they are different and they are called at completely different times. Write is called while in the snapshot (e.g. in enter()). Apply observers are called after the snapshot applies.

> Are you just trying to say that applying to a nested snapshot is equivalent to writing (ⓒ) all diffs to it before merging (ⓓ)?
No. I write observers are not called during apply at all. Nested snapshot do not call any observers when they are applied.

> Or this in Recomposer.composing?
I missed that one! Sorry about that. That is used to detect writes during composition that may invalidate other parts of composition. I am not sure how I missed that... Write observer allow the snapshot to observe itself which is compose does. Composition uses the write observer observers itself (e.g. changes made during composition). The apply observer observe changes outside composition.

[min]

val state = mutableStateOf(0, policy = policy)
val writes = mutableListOf<Int>()
val parent = Snapshot.takeMutableSnapshot(writeObserver = { target ->
    if (target == state) { writes.add(state.value) }
})
parent.enter {
    val snap0 = Snapshot.takeMutableSnapshot()
    val snap1 = Snapshot.takeMutableSnapshot()
    snap0.enter { state.value = 10 }
    kotlin.test.assertEquals(0, state.value)
    kotlin.test.assertEquals(actual = writes, expected = listOf(10))
    snap0.apply()
    kotlin.test.assertEquals(10, state.value)
    kotlin.test.assertEquals(actual = writes, expected = listOf(10))
    snap1.enter { state.value = 20 }
    kotlin.test.assertEquals(10, state.value)
    kotlin.test.assertEquals(actual = writes, expected = listOf(10, 20))
    snap1.apply()
    kotlin.test.assertEquals(30, state.value)
    kotlin.test.assertEquals(actual = writes, expected = listOf(10, 20))
}

Writes inside snap0 and snap1 are also observed by the write observer of parent? Even though those writes are invisible to the parent? So notifications are propagated up the snapshot hierarchy? It seems that global write observer aren’t notified though? So notifications are propagated up the hierarchy until they’re observed?

parent.enter {
    val nestedWrites = mutableListOf<Int>()
    val snap0 = Snapshot.takeMutableSnapshot()
    val snap1 = Snapshot.takeMutableSnapshot(writeObserver = { target ->
        if (target == state) { nestedWrites.add(state.value) }
    })
    snap0.enter { state.value = 10 }
    kotlin.test.assertEquals(0, state.value)
    kotlin.test.assertEquals(listOf(10), parentWrites)
    kotlin.test.assertEquals(listOf(), nestedWrites)
    snap0.apply()
    kotlin.test.assertEquals(10, state.value)
    kotlin.test.assertEquals(listOf(10), parentWrites)
    kotlin.test.assertEquals(listOf(), nestedWrites)
    snap1.enter { state.value = 20 }
    kotlin.test.assertEquals(10, state.value)
    kotlin.test.assertEquals(listOf(10, 20), parentWrites)
    kotlin.test.assertEquals(listOf(20), nestedWrites)
    snap1.apply()
    kotlin.test.assertEquals(30, state.value)
    kotlin.test.assertEquals(listOf(10, 20), parentWrites)
    kotlin.test.assertEquals(listOf(20), nestedWrites)
}

But the write in snap1 of 20 notified both the parent write observer and the snap1 write observer? So notifications are propagated up the tree, notifying all observers on the way, up to and excluding the global snapshot write observers? Also I’m wondering if you’ve seen the HTML notes attached to the message I linked to in my previous reply. I understand the call chain from ComposeView.setContent called in ComponentActivity.setContent during the initial activity creation to WrappedComposition.setContent. I know that it calls CompositionImpl.setContent which calls Recomposer.composeInitial. I don’t understand the lambda passed to CompositionImpl.setContent, how Recomposer goes on to set up everything needed for the first composition, and how it’s composed.

[Chuck Jazdzewski [G]]

I answer the question about how nested snapshot call their parent snapshots above. I also submitted a feature request to allow this to be more consistent with the global snapshot.

As for how composition works, I am willing to answer specific questions but a general question like this is more than I can answer in a chat window. There are blog posts and videos that describe this and at least one book. I recommend you start there.

[min]

So what happens on write is:
• In a nested snapshot, the write observers of the snapshot and recursively all its ancestors excluding the global snapshot are notified.
• In the global snapshot, the global snapshot write observers are notified.

Snapshot.global {
    val state = mutableStateOf(0, policy = policy)
    val observer = { history: MutableList<Int> ->
        { target: Any -> history.takeIf { target == state }?.add(state.value); Unit }
    }

    val writesGlobal = mutableListOf<Int>()
    Snapshot.registerGlobalWriteObserver(observer(writesGlobal))
    val writesPivot = mutableListOf<Int>()
    val pivot = Snapshot.takeMutableSnapshot(writeObserver = observer(writesPivot))
    pivot.enter {
        val writesNested0 = mutableListOf<Int>()
        val writesNested1 = mutableListOf<Int>()
        val nested0 = Snapshot
            .takeMutableSnapshot(writeObserver = observer(writesNested0))
        val nested1 = Snapshot
            .takeMutableSnapshot(writeObserver = observer(writesNested1))

        nested0.enter { state.value += 1 }
        nested1.enter { state.value += 2 }
        kotlin.test.assertEquals(0, state.value)
        kotlin.test.assertEquals(listOf(), writesGlobal)
        kotlin.test.assertEquals(listOf(1, 2), writesPivot)
        kotlin.test.assertEquals(listOf(1), writesNested0)
        kotlin.test.assertEquals(listOf(2), writesNested1)

        nested0.apply(); nested1.apply()
        kotlin.test.assertEquals(3, state.value)
        kotlin.test.assertEquals(listOf(), writesGlobal)
        kotlin.test.assertEquals(listOf(1, 2), writesPivot)
        kotlin.test.assertEquals(listOf(1), writesNested0)
        kotlin.test.assertEquals(listOf(2), writesNested1)
    }
    pivot.apply()
}

[Chuck Jazdzewski [G]]

Yes.