https://github.com/loro-dev/crdt-richtext
Presenting a new Rust crate that combines Peritext and Fugue's power with impressive performance, tailored specifically for rich text. This crate's functionality is set to be incorporated into Loro, a general-purpose CRDT library currently under development.
Peritext: A CRDT for Rich-Text Collaboration
Peritext is a novel rich-text CRDT (Conflict-free Replicated Data Type) algorithm. It is capable of merging concurrent edits in rich text format while preserving users' intent as much as possible. Its primary focus is on merging the formats and annotations of rich text content, such as bold, italic, and comments.
<aside> 💡 The specific definition of user intent in the context of concurrent rich text editing can't be clearly explained in a few words. it's best understood through specific examples.
</aside>
Peritext is designed to solve a couple of significant challenges:
Firstly, it addresses the anticipated problems arising from conflicting style edits. For instance, consider a text example, "The quick fox jumped." If User A highlights "The quick" in bold and User B highlights "quick fox jumped," the ideal merge should result in the entire sentence, "The quick fox jumped," being bold. However, existing algorithms might not meet this expectation, resulting in either "The quick fox" or "The" and "jumped" being bold instead.
| Original Text | The quick fox jumped |
|---|---|
| Concurrent Edit from A | The quick fox jumped |
| Concurrent Edit from B | The quick fox jumped |
| Expected Merged Result | The quick fox jumped |
| Bad case from merging | |
| Markdown text directly | The quick fox jumped |
| Bad case from Yjs | The quick fox jumped |
Additionally, Peritext manages conflicts between style and text edits. In the same example, if User A highlights "The quick" in bold, but User B changes the text to "The fast fox jumped," the ideal merge should result in "The fast" being bold.
| Original Text | The quick fox jumped |
|---|---|
| Concurrent Edit from A | The quick fox jumped |
| Concurrent Edit from B | The fast fox jumped |
| Expected Merged Result | The fast fox jumped |
What’s more, Peritext takes into account different expectations for expanding styles. For example, if you type after a bold text, you would typically want the new text to continue being bold. However, if you're typing after a hyperlink or a comment, you likely wouldn't want the new input to become part of the hyperlink or comment.
Fugue is a new CRDT text algorithm, presented in The Art of the Fugue: Minimizing Interleaving in Collaborative Text Editing by Matthew Weidner et al., nicely solves the interleaving problem.
The interleaving problem was proposed in the paper Interleaving anomalies in collaborative text editors by Martin Kleppmann et al.
An example of interleaving: