Support nested CRDT structures

[heckj]

Somewhere down the road, we'll want to support nested CRDT data structures. For example, allowing and supporting a YArray of YText, where the order within the array is managed by the CRDTs, and updates within each text inside the array is also managed by the CRDT. This is supported today in Yjs, and Bartosz built the same support for the WASM language bindings.

Taking a snapshot of the details he shared within Discord of how he tackled this scenario:

the general idea in the WebAssembly example:

1. Have an inner enum that's representing an either prelim or integrated state of the y-type.
2. y-type wrapping structure that's works like struct YText(RefCell<MyEnum<String, yrs::TextRef>>) - ref cell is useful here because it has replace method.
3. implement Prelim trait for that structure - the integrate method is executed after the block has been created, and it can be used to append prelim content values and finally to swap the prelim implementation with the integrated one.

The WASM code has these examples:

The "insert" logic, stashing a preliminary type marker within an embedded enum:

• https://github.com/y-crdt/y-crdt/blob/31b309868006d14c47c5deac6875979245de6409/ywasm/src/lib.rs#L1866

The replacement logic, converting preliminary types to final types:

• https://github.com/y-crdt/y-crdt/blob/31b309868006d14c47c5deac6875979245de6409/ywasm/src/lib.rs#L3638

[nugmanoff]

Let me add links to what @Waidhoferj has done as part of his work on ypy:

Have an inner enum that's representing an either prelim or integrated state of the y-type.

Here is essentially the same thing in ypy:

• https://github.com/y-crdt/ypy/blob/main/src/shared_types.rs

The rest of the logic (basically just the other methods like insert, move_to & etc) can be found in YArray implementation:

• https://github.com/y-crdt/ypy/blob/main/src/y_array.rs

[fivestones]

Do you think this will ever have progress here or is there some other way to do this in swift today?

[heckj]

hey @fivestones - it's definitely possible, but we haven't (as you can likely see) made any coding progress on this project in a few months. It's doable, but we're light on development time on the Rust side to make this happen. I can't make any promises of when it will be completed currently, as there's no active movement on the Rust side of this.

[nugmanoff]

@fivestones thanks for reaching out! seconding @heckj here, it definitely is possible to do it in this library, you would need to do some amount of Rust though. Reference links that I've attached above still apply. Unfortunately personally I have been quite tight on time lately, so I can't give any hard estimates, but plan is there.

Let me know if you want to try do it – I will do my best to assist you.

[fivestones]

Thanks both of you for responding. I'd love to see this more fleshed out but I can also see you guys have been busy. I also see you @heckj have been making a lot of progress with automerge in swift. I've been looking into seeing how I might make use of that. I would dive in here maybe except that I'd have to learn some rust first 😄 (which I guess isn't out of the question but then I'm in the same state as you guys--busy).
Thanks for all you've already done!

[nugmanoff]

I didn't know Rust at all (nor do I know it enough now) when I decided to take a stab at implementing POC for this whole thing. It is not that much Rust really, just a simple wrapping code here and there. Mostly it is about wrapping your head around all of the moving parts (yrs itself, UniFFI bindgen, Rust wrapping code, safely interfacing with generated bindings from Swift & etc).

[ghost]

@fivestones one potential workaround is to set up a YArray<String> of IDs, and then separately maintain root-level YTexts (or other shared types) named with those IDs.

I'm not sure if there are any significant downsides that I'm missing, but it seems to be working for a prototype I'm building at the moment.