Reference. Peritext: A CRDT for Collaborative Rich Text Editing

Conflict-Free Replicated Data Types (CRDTs) support decentralized collaborative editing of shared data, enabling peer-to-peer sharing and flexible branching and merging workflows. While there is extensive work on CRDTs for plain text, much less is known about CRDTs for rich text with formatting. No algorithms have been published, and existing open-source implementations do not always preserve user intent. In this paper, we describe a model of intent preservation in rich text editing, developed through a series of concurrent editing scenarios. We then describe Peritext, a CRDT algorithm for rich text that satisfies the criteria of our model. The key idea is to store formatting spans alongside the plaintext character sequence, linked to a stable identifier for the first and last character of each span, and then to derive the final formatted text from these spans in a deterministic way that ensures concurrent operations commute. We have prototyped our algorithm in TypeScript, validated it using randomized property-based testing, and integrated it with an editor UI. We also prove that our algorithm ensures convergence, and demonstrate its causality preservation and intention preservation properties.

Cite

Cite as @litt-2022-peritext (helia, typst) · \cite{litt-2022-peritext} (LaTeX)
BibTeX
bibtex · 1 line
@article{litt-2022-peritext, title={Peritext: A CRDT for Collaborative Rich Text Editing}, volume={6}, ISSN={2573-0142}, url={http://dx.doi.org/10.1145/3555644}, DOI={10.1145/3555644}, number={CSCW2}, journal={Proceedings of the ACM on Human-Computer Interaction}, publisher={Association for Computing Machinery (ACM)}, author={Litt, Geoffrey and Lim, Sarah and Kleppmann, Martin and van Hardenberg, Peter}, year={2022}, month=Nov, pages={1–36} }
hayagriva YAML (typst)
yaml · 22 lines
litt-2022-peritext:
  type: article
  title: 'Peritext: A CRDT for Collaborative Rich Text Editing'
  author:
  - Litt, Geoffrey
  - Lim, Sarah
  - Kleppmann, Martin
  - name: Hardenberg
    given-name: Peter
    prefix: van
  date: 2022-11
  page-range: 1-36
  url: http://dx.doi.org/10.1145/3555644
  serial-number:
    doi: 10.1145/3555644
    issn: 2573-0142
  parent:
    type: periodical
    title: Proceedings of the ACM on Human-Computer Interaction
    publisher: Association for Computing Machinery (ACM)
    issue: CSCW2
    volume: 6
Cited by (1)

Grove: A Bidirectionally Typed Collaborative Structure Editor Calculus adams-2025-grove

Version control systems typically rely on a patch language , heuristic patch synthesis algorithms like diff , and three-way merge algorithms . Standard patch languages and merge algorithms often fail to identify conflicts correctly when there are multiple edits to one line of code or code is relocated. This paper introduces Grove, a collaborative structure editor calculus that eliminates patch synthesis and three-way merge algorithms entirely. Instead, patches are derived directly from the log of the developer’s edit actions and all edits commute, i.e. the repository state forms a commutative replicated data type (CmRDT). To handle conflicts that can arise due to code relocation, the core datatype in Grove is a labeled directed multi-graph with uniquely identified vertices and edges. All edits amount to edge insertion and deletion, with deletion being permanent. To support tree-based editing, we define a decomposition from graphs into groves , which are a set of syntax trees with conflicts–including local, relocation, and unicyclic relocation conflicts–represented explicitly using holes and references between trees. Finally, we define a type error localization system for groves that enjoys a totality property, i.e. all editor states in Grove are statically meaningful, so developers can use standard editor services while working to resolve these explicitly represented conflicts. The static semantics is defined as a bidirectional marking system in line with recent work, with gradual typing employed to handle situations where errors and conflicts prevent type determination. We then layer on a unification-based type inference system to opportunistically fill type holes and fail gracefully when no solution exists. We mechanize the metatheory of Grove using the Agda theorem prover. We implement these ideas as the Grove Workbench , which generates the necessary data structures and algorithms in OCaml given a syntax tree specification.
DOI · pldb
Cites 48 works (0 here)
External (48)
litt-2022-peritext reference entries/refs/litt-2022-peritext/litt-2022-peritext.hel