cfcs/ocaml-xi-rope

xi-editor data structures in OCaml

ocaml-xi-rope

The aim of this library is to implement a (immutable) "rope" data structure based on the one used in xi-editor (authored by Raph Levien).

Xi's rope type is a CRDT (based on WOOT) permitting decentralized collaborative editing without vector clocks.

The ropes are currently implemented and exposed using Daniel Bünzli's pvec library.

My hope is to provide a set of libraries on top of this data structure supporting n-way merges of application configuration state for MirageOS unikernels, and a collaborative text editor widget usable with notty and mirage-framebuffer.

Please report any issues or requests for additional features on the issue tracker.

Limitations

This repository is currently available mainly as a proof of concept, and to enable me to receive feedback on the implementation. As such, this is not production-ready:

• While the data structures are immutable, it is still quite possible to supply invalid data (cyclic graphs, colliding unique IDs, ..)

• instead of using result types to signal invalid operations, the implementation throws exceptions left and right.

• While the construction, merging and snapshotting are implemented, my underlying implementation is pretty inefficient and some work on that will be needed to support large operations with reasonable performance.

• insertion is supported, but my algorithms, and the API, to handle insertions are fairly limited and cumbersome to work with.

• The test suite is missing.

  • The test suite is missing QuickCheck shrinkers

• Nice things like Levien's line-wrapping and paging algorithms are not implemented.

Installing the dependencies

Library:

opam pin add -ny pvec https://github.com/dbuenzli/pvec.git
opam install alcotest fmt logs pvec qcheck rresult uchar

Test / demo utils:

opam install notty
dune build
./_build/default/demo/notty_demo.exe
# this will launch a server on 127.0.0.1:7777
# start the program again in another window to have it connect to
# the server. you can now enjoy collaborative editing with
# horribly broken linewrapping where edits from anyone but the server
# gets propagated to the server exclusively. PRs welcome! :-)

Further reading

Below is a list of resources I found helpful and interesting:

• Levien on OT, TP2, CRDTs
• overview of Xi's CRDT
  • more details
  • Xi documentation
• YouTube presentation on Xi (36min)
• YouTube presentation on WOOT (25min)
• Nathan Sobo's description of the merge operations