Merge View: diff algorithm marks line as deleted & re-inserted when new line is inserted above + behaves weird

[VasylMarchuk]

Describe the issue

When a new line is inserted into the document, the diff algorithm marks the line it was inserted before as deleted & re-inserted later.

Example

If I have a document:

An example plain-text document 7
An example plain-text document 8
An example plain-text document 9

and then I insert a new line:

An example plain-text document 7
An example plain-text document NEW LINE
An example plain-text document 8
An example plain-text document 9

... it will mark An example plain-text document 8 as deleted & re-inserted later:

Details

What's more interesting, it treats the lines that don't start similarly correctly, such as line 11 NEW LINE:

What is even more interesting, this also strangely depends on what's LATER in the diff... but not always... the topmost "glitch" remains even after no more changes below, this video demonstrates it perfectly:

https://github.com/user-attachments/assets/084a8ade-7cf3-4a0e-950d-80754b2b32a4

Summary

So, to summarize what happens in the video above:

• Inserting An example plain-text document NEW LINE between An example plain-text document 7 and An example plain-text document 8 results in An example plain-text document 8 treated as removed, re-inserted
• Inserting NEW LINE between 9 & 10 doesn't do that
• Inserting An example plain-text document NEW LINE between 21 & 22 does that again
• BUT ONLY if there are changes later in the diff
• Discarding or accepting later changes fixes 21 & 22
• Discarding all changes below 7 & 8 doesn't fix it
• Bonus: a weird minus is shown in the gutter after line 11 NEW LINE is ACCEPTED

Document used in the video, to reproduce:

{
  document:
      'An example plain-text document 1\nAn example plain-text document 2\nAn example plain-text document 3\nAn example plain-text document 4\nAn example plain-text document 5\nAn example plain-text document 6\nAn example plain-text document 7\nAn example plain-text document NEW LINE\nAn example plain-text document 8\nAn example plain-text document 9\nNEW LINE\nAn example plain-text document 10\nAn example plain-text document 11\nAn example plain-text document 12\nAn example plain-text document 13\nAn example plain-text document 14\nAn example plain-text document 15\nAn example plain-text document 16\nAn example plain-text document 17\nAn example plain-text document 18\nAn example plain-text document 19\nAn example plain-text document 20\nAn example plain-text document 21\nAn example plain-text document NEW LINE\nAn example plain-text document 22\nAn example plain-text document 23\nAn example plain-text document 24\nAn example plain-text MODIFIED document 25\nAn example plain-text document 26\nAn example plain-text document 27\nAn example plain-text document 28\nAn example plain-text document 29\nAn example plain-text document 30\nAn example plain-text document 31\nAn example plain-text document 32\nAn example plain-text document 33\nAn example plain-text document 34\nAn example plain-text document 35',
  originalDocument:
      'An example plain-text document 1\nAn example plain-text document 2\nAn example plain-text document 3\nAn example plain-text document 4\nAn example plain-text document 5\nAn example plain-text document 6\nAn example plain-text document 7\nAn example plain-text document 8\nAn example plain-text document 9\nAn example plain-text document 10\nAn example plain-text document 11\nAn example plain-text document 12\nAn example plain-text document 13\nAn example plain-text document 14\nAn example plain-text document 15\nAn example plain-text document 16\nAn example plain-text document 17\nAn example plain-text document 18\nAn example plain-text document 19\nAn example plain-text document 20\nAn example plain-text document 21\nAn example plain-text document 22\nAn example plain-text document 23\nAn example plain-text document 24\nAn example plain-text document 25\nAn example plain-text document 26\nAn example plain-text document 27\nAn example plain-text document 28\nAn example plain-text document 29\nAn example plain-text document 30\nAn example plain-text document 31\nAn example plain-text document 32\nAn example plain-text document 33\nAn example plain-text document 34\nAn example plain-text document 35',
  filename: 'test.txt',
  language: 'text',
}

Reproduction link

We have a complete functioning demo of CodeMirror, wrapped into an Ember.js component over at https://app.codecrafters.io/demo/code-mirror, configurable with most of the standard extensions & their options in realtime, please feel free to test over there. It's ok if people discover the link here on GitHub, but please don't link to it, yet :)

All of the documents used as examples in the Demo's document drop-down can be found here. The Ember.js component itself, which wraps CodeMirror, passes it all enabled extensions, and handles updates is here, just in case.

Our current CodeMirror & Merge versions

npm ls --depth=0 | grep codemirror
├── @codemirror/language-data@6.5.1
├── @codemirror/merge@6.7.2
├── @uiw/codemirror-theme-github@4.23.6
├── codemirror@6.0.1

[marijnh]

There are often multiple valid diffs for a given pair of documents, and the one the library found here is definitely also valid. That being said, it does try to align changes to line boundaries, and attached patch fixes the issue that made it fail to do so here.

[VasylMarchuk]

Thank you @marijnh, I can conform that updating @codemirror/merge from 6.7.2 to 6.7.4 does fix the most obvious mis-behaviours of the diff algorithm for us, so that commit did help, big thanks again, our diffs look much cleaner now!

Before:

After:

[VasylMarchuk]

PS: it also appears that the accept/reject buttons of the mergeControls option are now missing for line insertions, but luckily we aren't using those yet.