reference-crdts
xi-editor
reference-crdts | xi-editor | |
---|---|---|
5 | 42 | |
111 | 19,811 | |
- | 0.1% | |
6.6 | 2.6 | |
6 months ago | 2 months ago | |
TypeScript | Rust | |
- | Apache License 2.0 |
Stars - the number of stars that a project has on GitHub. Growth - month over month growth in stars.
Activity is a relative number indicating how actively a project is being developed. Recent commits have higher weight than older ones.
For example, an activity of 9.0 indicates that a project is amongst the top 10% of the most actively developed projects that we are tracking.
reference-crdts
-
CRDTs make multiplayer text editing part of Zed's DNA
> The goog version seems to work well but I have had nothing but frustration with ms word. Bad merges and weird states are typical, particularly from the fat client.
Argh not getting this stuff right is really frustrating. I've been working on collaborative editing for over a decade now, and I still can't implement any of these algorithms correctly without the help of a fuzz testing. But fuzz testing done right finds all of these problems! There's no excuse!
Fuzzers work so well here because all of these algorithms have a clear correctness criteria: After syncing, state should always converge to the same result. So its pretty easy to write code which does this in a loop:
1. Generates some random changes on some fake "peers"
2. Picks 2 peers at random and sync their changes, using your new fancy synchronization algorithm
3. Assert that the state has converged between the peers
I've been working on this stuff for over a decade. I've implemented dozens of these algorithms. And every single time I write a fuzzy boi to check my work I find convergence bugs. Playing whack-a-mole with a fuzzer is a rite of passage for implementing systems like this.
When your fuzzer runs all night, you should never have lingering convergence bugs like you're describing with Word.
As an example, here's a simple fuzzer for a reference list CRDT implementation: https://github.com/josephg/reference-crdts/blob/9f4f9c3a97b4...
The code is so small it almost fits on my laptop screen.
-
WebAssembly 2.0 Working Draft
> In this case, the bottleneck at 9 million LoC is not CPU cycles but memory usage. That's where I am considering pushing down into WebAssembly
How often does this come up in practice? I can't think of many files I've opened which were 9 million lines long. And you say "LoC" (lines of code). Are you doing syntax highlighting on 9 million lines of source code in javascript? Thats impressive!
> I guess my point is why do you need balanced trees? Is this a CRDT specific thing? Can you implement CRDT with just an array of lines / gap buffer?
Of course! Its just going to be slower. I made a simple reference implementation of Yjs, Automerge and Sync9's list types in javascript here[1]. This code is not optimized, and it takes 30 seconds to process an editing trace that diamond types (in native rust) takes 0.01 seconds to process. We could speed that up - yjs does the same thing in 1 second. But I don't think javascript will ever run as fast as optimized rust code.
The b-tree in diamond types is used for merging. If you're merging 2 branches, we need to map insert locations from the incoming branch into positions in the target (merged) branch. As items are inserted, the mapping changes dynamically. The benchmark I've been using for this is how long it takes to replay (and re-merge) all the changes in the most edited file in the nodejs git repository. That file has just shy of 1M single character insert / delete operations. If you're curious, the causal graph of changes looks like this[2].
Currently it takes 250ms to re-merge the entire causal graph. This is much slower than I'd like, but we can cache the merged positions in about 4kb on disk or something so we only need to do it once. I also want to replace the b-tree with a skip list. I think that'll make the code faster and smaller.
A gap buffer in javascript might work ok... if you're keen, I'd love to see that benchmark. The code to port is here: [3]
> Undo support -> In which case, you only have to stack / remember the set of commands and not have to store the state on every change. I'm not sure if this overlaps with the data structure choice, other than implementation details.
Yeah, I basically never store a snapshot of the state. Not on every change. Not really at all. Everything involves sending around patches. But you can't just roll back the changes when you undo.
Eg: I type "aaa" at position 0 (the start of the document). You type "bbb" at the start of the document. The document is now "bbbaaa". I hit undo. What should happen? Surely, we delete the "aaa" - now at position 3.
Translating from position 0 to position 3 is essentially the same algorithm we need to run in order to merge.
> I was just looking into TypedArrays.
I tried optimizing a physics library a few years ago by putting everything in typedarrays and it was weirdly slower than using raw javascript arrays. I have no idea why - but maybe thats fixed now.
TypedArrays are useful, but they're no panacea. You could probably write a custom b-tree on top of a typedarray in javascript if you really want to - assuming your data also fits into typedarrays. But at that point you may as well just use wasm. It'll be way faster and more ergonomic.
[1] https://github.com/josephg/reference-crdts
[2] https://home.seph.codes/public/node_graph.svg
[3] https://github.com/josephg/diamond-types/tree/master/src/lis...
xi-editor
-
Zed is now open source
Was confused until I realised I'd confused Zed, with Xi[1] which is also rust based, and which incidentally has a frontend called "Xim"..
Also there's a wiki-editor (like Tomboy[2]) called "Zim"[3].
[1] https://github.com/xi-editor/xi-editor
-
Text Editor: Data Structures
Project site linked from the GitHub[0] is https://xi-editor.io. Linked doc is a mirror of this[1], which was afaik originally written by Raph Linus.
[0]: https://github.com/xi-editor/xi-editor
[1]: https://xi-editor.io/docs/rope_science_01.html
-
The Absolute Minimum Every Software Developer Must Know About Unicode in 2023
> thing that gets deleted when you hit backspace
Is there a canonical source for this part, by the way? Xi copied the logic from Android[1] (as per the issue you linked downthread), and I vaguely remember that CLDR had something to say about this too, but I don’t know if there’s any sort of consensus here that’s actually written down anywhere.
[1] https://github.com/xi-editor/xi-editor/pull/837
- Google abandons work to move Assistant smart speakers to Fuchsia
-
What's is a rusty way to implement sharable trees?
This is pretty much how copy-on-write ropes work. Check out xi-rope, Ropey or crop, they're all built using B-trees and implement the behavior you described.
-
Helix (a Kakoune / Neovim inspired editor) 23.03
Helix is awesome, though once Lapce (spiritual successor to Xi editor) gets the Helix/Kakoune editing model, I may have to jump ship
-
Editors written in rust
Home (xi-editor.io)
-
How to share resources between instances of program?
Maybe take a look at the Xi editor (https://xi-editor.io/) (written in rust I think) that uses a client server architecture.
-
Suitable Rust GUI Library for Code Editor?
Have a look at what Lapce uses. The editor is coming along nicely, and iirc, they use the Xi editor as a plug-in.
-
CRDTs make multiplayer text editing part of Zed's DNA
Raph Levien posted a retrospective about using CRDT’s for collaborative editing in xi-editor here [1]. His conclusion is
“I come to the conclusion that the CRDT is not pulling its (considerable) weight. When I think about a future evolution of xi-editor, I see a much brighter future with a simpler, largely synchronous model, that still of course has enough revision tracking to get good results with asynchronous peers like the language server.”
[1]https://github.com/xi-editor/xi-editor/issues/1187#issuecomm...
What are some alternatives?
wai - A language binding generator for `wai` (a precursor to WebAssembly interface types)
helix - A post-modern modal text editor.
multi-memory - Multiple per-module memories for Wasm
alacritty - A cross-platform, OpenGL terminal emulator.
diamond-types - The world's fastest CRDT. WIP.
iota - A terminal-based text editor written in Rust
uwm-masters-thesis - My thesis for my Master's in Computer Science degree from the University of Wisconsin - Milwaukee.
lapce - Lightning-fast and Powerful Code Editor written in Rust
wit-bindgen - A language binding generator for WebAssembly interface types
Servo - Servo, the embeddable, independent, memory-safe, modular, parallel web rendering engine
yjs - Shared data types for building collaborative software
kakoune.el - A very simple simulation of the kakoune editor inside of emacs.