Closed mweidner037 closed 1 year ago
[ ] Ensure CPositionSource doesn’t have any mutable state besides the abstract tree structure that might confuse sharers. E.g., the current delete counts would break CValueList merging if a separate list modified them.
My current plan for this:
CPositionSource
only remembers it for locally created waypoints. (Necessary to avoid creating the same Position twice. The local info is not saved - only relevant to the current replicaID.)CPositionSource.createPosition
take two arguments, a prevPos and the nextPos. The created position is allowed to be anywhere between, even if it's not directly after prevPos
counting tombstones. In particular, it is okay if we skip over some positions with the same waypoint as prevPos
, so long as those are also < nextPos. This allowance is necessary b/c we don't track whether those posistions exist or not.
prevPos = (my waypoint, n)
and (my waypoint, n + 1) ... (my waypoint, n + m)
already exist but are prior to nextPos, then we are allowed to create (my waypoint, n + m + 1)
instead of a left child of (my waypoint, n + 1)
.CValueList
internally keeps a map from each waypoint to the max valueIndex seen for that waypoint considering only the list's own ops. This is needed to merge deletions.
I'm skipping CPositionSource.compare
for now because it was more complicated than I expected and had a performance cost (from storing depth
). There is an untested draft here: https://github.com/composablesys/collabs/blob/9b20307e05d32f69049e62cb60319c83174e80e6/crdts/src/list/c_position_source.ts#L532
[ ] Individual list CRDTs allow specifying a
CPositionSource
I'm omitting this for now because I can't think of a good use case, and we can add it backwards-compatibly later.
E.g. for suggestions on a doc, storing the actual text and suggestions in separate CValueLists does not allow proper "accepting": you want to transfer (position, value) pairs from the suggestion to the actual text, but CValueList doesn't let you set a position directly. Instead, you should:
Even without this feature, the CPositionSource refactoring still makes (2) more reasonable. It might also enable using CPositionSource in a centralized app, to manage a CRDT total order whose actual position-value maps are handled by a server.
Allow multiple list CRDTs to share a
CPositionSource
, possibly across linked documents (https://github.com/composablesys/collabs/issues/262).E.g.:
CPositionSource
in a 3rd document, but not the original text CRDT's document.(Can we make this work for multiple CRichTexts as well, including formatting spans?)
LocalList
gets partway there but not all the way.Some specific changes needed:
CPositionSource
, and also expose theirs.newLocalList()
methods? (If fully redundant)CValueList
.CValueList
merging if a separate list modified them.CPositionSource.compare
function, in case you want to opt out of whatever the list CRDTs are doing.This feature is not critical, but it would be nice to implement it sooner because it will break backwards compatibility for saved states.