Peritext algorithm may attach deleted mark to new inserted text

[zxch3n]

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.

Steps to reproduce the issue in this repo

This can be replicated by adding this micromerge test

    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. 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, 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.

[ept]

Hi @zxch3n, well spotted, and thank you for reporting this issue. Your proposed fix seems reasonable.