# CRDT-Richtext

Based on the algorithms of Peritext and Fugue, we made `crdt-richtext`, a lib written in Rust that provides a wasm interface. Itâs available on [crates.io](http://crates.io) and npm now.

## Example

```tsx
import { RichText } from "crdt-richtext-wasm";

const text = new RichText(BigInt(1));
text.insert(0, "ä½ å¥½ï¼ä¸çï¼");
text.insert(2, "å");
expect(text.toString()).toBe("ä½ å¥½åï¼ä¸çï¼");
text.annotate(0, 3, "bold", AnnotateType.BoldLike);
const spans = text.getAnnSpans();
expect(spans.length).toBe(2);
expect(spans[0].text).toBe("ä½ å¥½å");
expect(spans[0].annotations.size).toBe(1);
expect(spans[0].annotations.has("bold")).toBeTruthy();
expect(spans[1].text.length).toBe(4);

const b = new RichText(BigInt(2));
b.import(text.export(new Uint8Array()));
expect(b.toString()).toBe("ä½ å¥½åï¼ä¸çï¼");
```

## Data structure

We heavily use B-Trees to optimize our algorithm. We made a library called [generic-btree](https://github.com/loro-dev/generic-btree), which is written in safe Rust code, which provides a flexible foundation for our optimization efforts.

[https://github.com/loro-dev/generic-btree](https://github.com/loro-dev/generic-btree)

![The cached content inside B-Tree](./images/richtext3.png)

The cached content inside B-Tree

There are several common tasks we need to address in Text CRDT, including:

- Finding, inserting, or deleting content at a given index:
  - We use a BTree to look up and update the content
  - The time complexity is O(logN), where N is the length of the content
- Finding content with a given op ID:
  - We use a combination of HashMap and BTree
  - The time complexity if O(logN), where N is the number of operations
- Compressing content in memory:
  - To reduce the amount of memory used by storing every operation in raw format, we compress the content using the RLE tricks from Yjs and DiamondTypes.
    - The insight behind this compression is that neighboring inserts and deletions tend to be continuous, so we can merge them and store less metadata.
  - Commonly, every leaf node in the diagram contains a dozen of characters
- Converting index between UTF-16 and UTF-8:
  - In JS, the default encoding of a string is utf16, but in Rust, the default one is utf8. Although the WASM interface can help us convert the encoding of the string, we still need to convert the _index_ of the operation.
  - To solve this, `crdt-richtext` also store the UTF-16 length of the content in B-Tree. So we can query the B-Tree with either the utf8 index or the utf16 index.
- Storing the boundary of style/format/comments:
  - We use the same B-Tree to store the boundary, with each subtree corresponding to a span of text or tombstones. For each node in the tree, we store which annotations start before it, start after it, end before it, or end after it.
    ```rust
    #[derive(Debug, PartialEq, Eq, Default, Clone)]
    pub struct ElemAnchorSet {
        start_before: FxHashSet<AnnIdx>,
        end_before: FxHashSet<AnnIdx>,
        start_after: FxHashSet<AnnIdx>,
        end_after: FxHashSet<AnnIdx>,
    }
    ```
  - This is basically the same optimization as Peritext, except we do it on the tree.

## Encoding

We use columnar encoding, which was first adopted to CRDTs by Martin Kelppmann [in automerge](https://github.com/automerge/automerge-classic/pull/253). To make it easier in Rust, we created the lib [Serde Columnar: Ergonomic columnar storage encoding crate](https://www.notion.so/Serde-Columnar-Ergonomic-columnar-storage-encoding-crate-7b0c86d6f8d24e4da45a1e2ebd86741c?pvs=21).

## Heavily tested by libFuzzer

Test-Driven Development (TDD) provides an amazing development experience. If possible, I always write unit tests for a standalone module before moving forward. However, for algorithms like CRDTs, it is infeasible to list all possible cases manually but is easy to generate test cases automatically. This is where fuzzing tests come into play.

Some fuzzers can track coverage information and generate mutations on the input data to maximize code coverage. LibFuzzer can also identify memory leaks and UAF problems.

`[cargo-fuzz`](https://www.notion.so/crdt-richtext-Rust-implementation-of-Peritext-and-Fugue-c49ef2a411c0404196170ac8daf066c0?pvs=21) provides a user-friendly API for writing fuzzing tests, and it supports two fuzzers: libFuzzer and AFL. It makes the unstructured libFuzzer feel structured. So weâre able to write fuzzing tests in this way

```rust
use arbitrary::Arbitrary;

#[derive(Arbitrary, Clone, Debug, Copy)]
pub enum Action {
    Insert {
        actor: u8,
        pos: u8,
        content: u16,
    },
    Delete {
        actor: u8,
        pos: u8,
        len: u8,
    },
    Annotate {
        actor: u8,
        pos: u8,
        len: u8,
        annotation: AnnotationType,
    },
    Sync(u8, u8),
}

pub fn fuzzing(actions: Vec<Action>) {
	// run tests based on actions
	...
}

#![no_main]
use libfuzzer_sys::fuzz_target;

fuzz_target!(|actions: [Action; 100]| { fuzzing(actions.to_vec()) });
```

![We will run millions of Fuzzing Tests after making big changes. The fuzzer can help us extract the most useful thousands of tests to be included into the corpus. The minor changes can be verified by running the corpus.](./images/richtext4.png)

We will run millions of Fuzzing Tests after making big changes. The fuzzer can help us extract the most useful thousands of tests to be included into the corpus. The minor changes can be verified by running the corpus.

We use fuzzing tests in Loro's CRDTs too. This test suite is like our safety net when we're making big tweaks to the code. It's great at spotting all our little slip-ups.