Updates don't apply

[davidbrochart]

These updates are supposed to push "b" to the initial content "a" of a YText, but it doesn't work:

import y_py as Y

ydoc1 = Y.YDoc()
ysource1 = ydoc1.get_text("source")

with ydoc1.begin_transaction() as t:
    ysource1.push(t, "a")

updates = [
    [1, 2, 201, 210, 153, 56, 0, 40, 1, 5, 115, 116, 97, 116, 101, 5, 100, 105, 114, 116, 121, 1, 121, 40, 1, 7, 99, 111, 110, 116, 101, 120, 116, 4, 112, 97, 116, 104, 1, 119, 13, 117, 110, 116, 105, 116, 108, 101, 100, 52, 46, 116, 120, 116, 0],
    [1, 1, 201, 210, 153, 56, 2, 168, 201, 210, 153, 56, 0, 1, 120, 1, 201, 210, 153, 56, 1, 0, 1],
    [1, 1, 201, 210, 153, 56, 3, 40, 1, 7, 99, 111, 110, 116, 101, 120, 116, 13, 108, 97, 115, 116, 95, 109, 111, 100, 105, 102, 105, 101, 100, 1, 119, 27, 50, 48, 50, 50, 45, 48, 52, 45, 49, 54, 84, 49, 52, 58, 48, 51, 58, 53, 51, 46, 57, 51, 48, 52, 54, 56, 90, 0],
    [1, 1, 201, 210, 153, 56, 4, 168, 201, 210, 153, 56, 2, 1, 121, 1, 201, 210, 153, 56, 1, 2, 1],
    [1, 2, 201, 210, 153, 56, 5, 132, 228, 254, 237, 171, 7, 0, 1, 98, 168, 201, 210, 153, 56, 4, 1, 120, 0],
    [1, 1, 201, 210, 153, 56, 6, 168, 201, 210, 153, 56, 4, 1, 120, 1, 201, 210, 153, 56, 1, 4, 1],
]

for update in updates:
    Y.apply_update(ydoc1, update)

print(ysource1.to_json())

[Horusiath]

Initial investigation results: update at index 4 - the one that appends letter 'b' - refers to block with ID (client: 1971027812, clock: 0 as its origin, however none of the provided updates from an array had ever provided that block. In result update inserting 'b' stays in among the pending updates. So either:

1. Update having a block 1971027812#0 never arrived therefore we cannot show 'b'.
2. Client ID 1971027812 was parsed incorrectly, however this seem to be unlikely.
3. You wanted to create document with explicit ID 1971027812 first - Y.YDoc() creates client ID that's autogenerated by random number generator, therefore it may be different between runs.

[davidbrochart]

Thanks for the analysis, indeed I had to create a document with explicit ID 1971027812 (pt. 3), and everything works fine.
Now consider the following example, which starts as above, except that before applying the update at index 4 (the one that appends "b"), a new client ydoc2 syncs with the current state of ydoc1. Up to here, it works: ysource2 has "a".
But if we apply the update that appends "b" to ysource1, and a new client ydoc3 syncs with the current state of ydoc1, it doesn't work: ysource3 has "" instead of "ab".
Am I missing something?

import y_py as Y

ydoc1 = Y.YDoc(client_id=1971027812)
ysource1 = ydoc1.get_text("source")

with ydoc1.begin_transaction() as t:
    ysource1.push(t, "a")

updates = [
    [1, 2, 201, 210, 153, 56, 0, 40, 1, 5, 115, 116, 97, 116, 101, 5, 100, 105, 114, 116, 121, 1, 121, 40, 1, 7, 99, 111, 110, 116, 101, 120, 116, 4, 112, 97, 116, 104, 1, 119, 13, 117, 110, 116, 105, 116, 108, 101, 100, 52, 46, 116, 120, 116, 0],
    [1, 1, 201, 210, 153, 56, 2, 168, 201, 210, 153, 56, 0, 1, 120, 1, 201, 210, 153, 56, 1, 0, 1],
    [1, 1, 201, 210, 153, 56, 3, 40, 1, 7, 99, 111, 110, 116, 101, 120, 116, 13, 108, 97, 115, 116, 95, 109, 111, 100, 105, 102, 105, 101, 100, 1, 119, 27, 50, 48, 50, 50, 45, 48, 52, 45, 49, 54, 84, 49, 52, 58, 48, 51, 58, 53, 51, 46, 57, 51, 48, 52, 54, 56, 90, 0],
    [1, 1, 201, 210, 153, 56, 4, 168, 201, 210, 153, 56, 2, 1, 121, 1, 201, 210, 153, 56, 1, 2, 1],
]
for update in updates:
    Y.apply_update(ydoc1, update)

print(ysource1.to_json())
# prints "a"

ydoc2 = Y.YDoc()
ysource2 = ydoc2.get_text("source")
state2 = Y.encode_state_vector(ydoc2)
update = Y.encode_state_as_update(ydoc1, state2)
Y.apply_update(ydoc2, update)

print(ysource2.to_json())
# OK: prints "a"

update = [1, 2, 201, 210, 153, 56, 5, 132, 228, 254, 237, 171, 7, 0, 1, 98, 168, 201, 210, 153, 56, 4, 1, 120, 0]
Y.apply_update(ydoc1, update)

print(ysource1.to_json())
# prints "ab"

ydoc3 = Y.YDoc()
ysource3 = ydoc3.get_text("source")
state3 = Y.encode_state_vector(ydoc3)
update = Y.encode_state_as_update(ydoc1, state3)
Y.apply_update(ydoc3, update)

print(ysource3.to_json())
# KO: prints ""

[Horusiath]

It looks like the issue is in the `Update::integrate method: https://github.com/y-crdt/y-crdt/blob/44f9765d565a03af85824c11c72fd8947a69e97e/yrs/src/update.rs#L184-L186

It's a bug, since we should apply blocks by client IDs from highest client ID to the lowest one. However we're sorting them in order highest->lowest, and them pop them, taking the last one which is the lowest, first. One thing I don't fully understand is that this shouldn't produce bugs nonetheless. Maybe @dmonad can say more.

[dmonad]

You are right @Horusiath, this shouldn't produce any bugs.

The reason why we sort by clientId in descending order is that 1. the v2 encoder uses differential RLE encoders that encode the differences between clientids and 2. we can often avoid transformations when applying operations with a higher precedence first.

Using the sorting approach only avoids some transformations which is maybe the reason why the incorrectly sorted approach has a bug.

[davidbrochart]

If we could make a release with y-crdt/y-crdt#109 I can try it out.