8000 CPositionSource sharing · Issue #264 · composablesys/collabs · GitHub
[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to content

CPositionSource sharing #264

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Closed
3 of 5 tasks
mweidner037 opened this issue Jul 16, 2023 · 3 comments · Fixed by #265
Closed
3 of 5 tasks

CPositionSource sharing #264

mweidner037 opened this issue Jul 16, 2023 · 3 comments · Fixed by #265
Assignees
@mweidner037
Labels
feature package:crdts crdts package

Comments

@mweidner037
Copy link
Collaborator
mweidner037 commented Jul 16, 2023 •
edited
Loading

Allow multiple list CRDTs to share a CPositionSource, possibly across linked documents (#262).

E.g.:

  • When a text CRDT grows beyond a certain point, it is retired (becomes delete-only) and new text CRDTs are defined on top of fractions of the document. New insertions go in those fractional documents; a user only needs to load the original document and the fraction they are currently using.
  • Suggestions on a text document go in a separate document with its own text CRDT for new text. Users with suggestion-only access get edit access to the latter document and a base 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:

  • Individual list CRDTs allow specifying a CPositionSource, and also expose theirs.
  • Delete newLocalList() methods? (If fully redundant)
  • Get rid of Create-as-insert opt in CValueList.
  • 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.
  • 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.
@mweidner037
Copy link
Collaborator Author

[ ] 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:

  • Instead of remembering the max-created valueIndex of every waypoint, 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.
    • While we're allowing this, we can also add the opt: if 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.
    • For merging deletions to work, we need to make sure that waypoints are specific to both a replicaID and a CValueList: only the CValueList is allowed to extend its own waypoints, not some other list.

@mweidner037 mweidner037 self-assigned this Jul 31, 2023
@mweidner037
Copy link
Collaborator Author

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:

collabs/crdts/src/list/c_position_source.ts

Line 532 in 9b20307

compare(a: Position, b: Position): number {

@mweidner037
Copy link
Collaborator Author

[ ] 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:

  1. Store suggestions in a "forked" doc that you merge to accept.
  2. Or, manually manage a CPositionSource plus 2 LocalLists. (We can make this easier to moving CValueList's merge logic to a static LocalList function.)

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.

This was referenced Jul 31, 2023
Open
Merged
@mweidner037 mweidner037 linked a pull request Jul 31, 2023 that will close this issue
List refactor (CTotalOrder) #265
Merged
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@mweidner037 mweidner037

Labels
feature package:crdts crdts package
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

List refactor (CTotalOrder) composablesys/collabs
1 participant
@mweidner037
0