What?

Brings Delta/diff library updates to trunk. See original PR for wpvip/rtc-plugin in #72604.

This PR:

• Adds a fork of quill-delta to the sync package.
• Replaces the fast-diff library used in quill-delta, which is incompatible with GPLv2 due to the Apache 2 license. Instead we use diff, which has a compatible license.
• Adds a post-processing function on top of fast-diff called diffWithCursor() that attempts to match insert/deletion location with user cursor position. More information on this below.

Why?

For multi-user editing within a single rich text area, we want to send incremental updates instead of entirely new strings in Yjs. This makes update operations more efficient and allows us to support relative positioning. Y.Text natively supports applying changes as Deltas along with quill-delta, but we're unable to directly use the quill-delta library due to license constraints.

What does the new diffWithCursor() function do? The per-character function provided by diff is diffChars(), which takes two strings as input but does not accept a cursor position. This can cause ambiguous changes when there are repeated characters or substrings.

For example, a user enters an a in the middle of a run of the same character:

diffChars( 'aaa', 'aaaa' ) gives this result:

[
    { count:3, value:"aaa" },
    { count:1, value:"a", added:true }
]

This indicates adding an a to the end of the string. Because diffChars() only accepts two strings and has no cursor awareness, it can only guess where the a was added, and always selects the last position. This results in cursors "moving backwards" when another user types:

The "Chrome" user's cursor should move forward when my user is typing, but it doesn't because the a is being appended to the end of the string and the relative positioning of cursor fails to match user expectations.

The new diffWithCursor() function wraps the initial diff result and attempts to move deletions or insertions to the user's cursor position. Here's what the processed result of diffChars() looks like:

[
    { value:"a",  count:1, added:false, removed:false },
    { value:"a",  count:1, added:true,  removed:false },
    { value:"aa", count:2, added:false, removed:false }
]

This matches the actual user's experience and where the character is added. The result, with the character in the right position, is relative postioning working as expected:

How?

Here's a runthrough of the diffWithCursor() function. I'm not sure it handles every case, but it handles a lot of cases better than diff alone.

1. First, we convert incoming Delta operations to strings we can use with diffChars().

   For example, if we have the string jajaja and a user has pasted ja at cursor position 2, (ja|jaja -> jaja|jaja where | is the cursor), this.ops will be { insert: "jajaja" } and other.ops will be { insert: "jajajaja" }.

   deltasToStrings() will process these operations into two strings, "jajaja" and "jajajaja".

2. Next, diffChars() is run against those two strings which is provided by the diff package. It gives this result:

   [
       { value:"jajaja", count:6 },
       { value:"ja", count:2, added:true }
   ]

   The ja addition has incorrectly been placed at the end of the diff.
   ​

3. Next, we post-process this diff to see if we can move the changes to the position of the cursor. Each diff object is iterated with these rules:

   1. Path 1: If the current segment is unchanged, but we see the cursor ended in this segment, we try to see if we can move the insertion from the next segment.

      For the example above, we encounter this path on the first diff segment. cursorAfterChange is 4, indicating the cursor ended in the middle of the first jajaja segment, but there is no insertion there. There is also an insertion directly after this segment, so we call tryMoveInsertionToCursor() which will check if the insertion after this segment ({count:2, added:true, value:"ja"}) can be moved to match the cursor location. If it can, then it'll:

      • Split the current segment: {count:2, value:"ja"}
      • Insert the next insertion segment: {count:2, added:true, value:"ja"}
      • Then put the rest of the current segment afterward: {count:2, value:"jaja"} with this result:

      [
          { value:"ja",   count:2, added:false, removed:false },
          { value:"ja",   count:2, added:true,  removed:false },
          { value:"jaja", count:4, added:false, removed:false }
      ]

      This segment and the next is then consumed.

   2. Path 2: Works similarly to part 1, but checking for deletions. Here's an example for the text aaaa where an a is deleted in the second position (aa|aa -> a|aa):

      We process the original diff of:

      [
          { count":3, "value":"aaa" },
          { count":1," removed":true, "value":"a" }
      ]

      On processing the second segment, we see a deletion where the cursor was in the previous segment. Calling into tryMoveDeletionToCursor() will test if the deletion string can be moved to the prior segment. If this is possible, we split the prior segment and add the deletion with this result:

      [
          { value:"a", count:1, added:false, removed:false },
          { value:"a", count:1, added:false, removed:true },
          { value:"a", count:1, added:false, removed:false }
      ]

   3. If the segment doesn't match either case above, add it as-is to the processed segments.

4. Lastly we convert the result of the processed diffs to Delta format with convertChangesToDelta(). For example:

   Before processing:

   [
       { value:"ja",   count:2, added:false, removed:false },
       { value:"ja",   count:2, added:true,  removed:false },
       { value:"jaja", count:4, added:false, removed:false }
   ]

   After processing as a Delta:

   {"ops":[
       { "retain":2 },
       { "insert":"ja" }
   ]}

   This indicates that the original text stays the same for the first two characters, and adds ja, matching our original user behavior.

Testing Instructions

1. Recreate the UI examples above by adding two users to a collaborative post, and put one user's cursor near the end.
2. Type with the first user and ensure that the second user's cursor in awareness moves with local changes. Note that the other user's actual editing position in the editor won't move, but this PR will create the basis to make that possible
3. Try repeating strings like aaaaa or jajajaja and insert multiple characters with pastes and ensure the second user's cursor in awareness moves as expected.
4. Try the same with deletions and ensure cursor position changes are in the correct location.

The 34 new diffWithCursor() tests can be run via:

 npm run test:unit -- --testPathPattern=Delta.ts