inkandswitch / inkandswitch/peritext

Peritext algorithm may attach deleted mark to new inserted text

Open
#32 1 comment 1 reaction 0 assignees View on GitHub
Dominant language
TypeScript
Stars
791
Forks
30
PR merge metrics
No merged PRs in 30d

Description

The Peritext algorithm may attach a non-exist ghost mark to a newly inserted string. It is also reproducible in Automerge's implementation. But it can be fixed without affecting the validity of the historical data.

CleanShot 2023-05-18 at 00 54 25@2x

Steps to reproduce the issue in this repo

This can be replicated by adding this micromerge test

```ts

it("doesn't create ghost style", () => {
testConcurrentWrites({
inputOps1: [],
inputOps2: [
{
action: "addMark",
startIndex: 4,
endIndex: 12,
markType: "link",
attrs: {
url: "inkandswitch.com",
},
},
{
action: "addMark",
startIndex: 8,
endIndex: 12,
markType: "strong",
},
{
action: "delete",
index: 3,
count: 8,
},
{
action: "insert",
index: 3,
values: ["!"],
},
],
//
expectedResult: [
{ marks: {}, text: "The!editor" },
],
});
});

```

## Why

The problem is caused by [this fix in the paper](https://www.inkandswitch.com/peritext/#:~:text=To%20fix%20this,of%20the%20link.). In this example, when Peritext inserts the new char '!', it prefers the positions after the tombstone with the end of the link. And the tombstone is after the beginning of the bold mark. So '!' turns out to be bold.

In [my implementation](https://github.com/loro-dev/crdt-richtext), I've fixed this by adding a new rule for choosing the insertion position among tombstones:

1. Insertions occur before tombstones that contain the beginning of new marks. (new)
2. Insertions occur before tombstones that contain the end of bold-like marks
3. Insertions occur after tombstones that contain the end of link-like marks

Rule 1 should be satisfied before rules 2 and 3 to avoid this problem.

This solution can clearly fix the example given above and make it satisfy all of the rules. The only downside is it might make a "link-like mark" grow forward unexpectedly a bit more often. But it seems to be more tolerable.

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.