Page MenuHomePhabricator

Enhance line matching in diffs
Open, MediumPublic

Assigned To
Authored By
Mar 21 2008, 3:08 AM
Referenced Files
F22440168: 2018-06-21_Translate diff.png
Jun 21 2018, 7:36 AM
F22440200: 2018-06-23_fibres diff.png
Jun 21 2018, 7:36 AM
F22440177: 2018-06-22_Lawrence diff.png
Jun 21 2018, 7:36 AM
F3822550: Screen Shot 2016-04-03 at 4.14.53 PM.png
Apr 3 2016, 1:14 PM
F4793: dwdiff.png
Nov 21 2014, 10:08 PM
"Doubloon" token, awarded by Ciencia_Al_Poder."Like" token, awarded by Ricordisamoa."Love" token, awarded by He7d3r.


Author: random832

In the example URL, the lines beginning "Sed elit" on each side differ by only one character. These should be considered the "equivalent lines" to each other and show up in the same row of the table and get word-by-word hilighting. This is a general feature request for more intelligence in deciding what lines are "equivalent".

Version: unspecified
Severity: normal

Event Timeline

bzimport raised the priority of this task from to Medium.Nov 21 2014, 10:07 PM
bzimport set Reference to bz13462.
bzimport added a subscriber: Unknown Object (MLST).

The solution might affect bug 13466 somehow.

  • Bug 24618 has been marked as a duplicate of this bug. ***

sumanah wrote:

'This is a general feature request for more intelligence in deciding what lines are "equivalent".' I agree with Random832.

An acquaintance of mine gives this example:

The diff:

This person teaches English composition. He uses MediaWiki to do it. His students type their essays into MediaWiki, he improves them via an edit, and then they look at the diff together to understand what he changed and why. He finds that the diff calculation in MediaWiki is not robust enough and fails to sensibly show linebreak changes in some instances, and that this makes it much harder to use the diffs as a teaching tool.

"There were very minimal changes made to the article between the first and second revisions; however, I did add a number of paragraph breaks, and coalesced a couple of paragraphs.

"You can see that the paragraph breaks caused the diff "discernment function" to identify whole paragraphs as changes, when in fact all that happened with the addition of a simple line break."

Adding the "design" keyword to ping a designer to consider what we should really be doing regarding various diff generation and diff-viewing edge cases. wrote:

Agree, visiting here to report a similar request with this example:

Examples of issues that should have been noticed by the diff engine/formatter:

  • Line starting "{{cquote|It is surprising" -- same or virtually same line appears left and right, diff engine fails to match them with no obvious reason why that should be. So they appear as a deletion + insertion, rather than shown adjacent. Common problem.
  • Same occurs lower down with line starting ":* Fibres from"
  • Under heading "=== Subsequent events ===" -- a paragraph has been added starting "An inquest into..." Surrounding text is unchanged. Instead of recognizing this as a simple one-paragraph addition, it's treating it as a removal of one paragraph and change to all text in all following paragraphs (ie believes each para has changed when they have merely moved down one para simultaneously due to the insertion). The last 2 paras in the section are then treated as new insertions which they aren't.
  • Line starting ": "I don't" edited to add a {{cquote| template. Instead of recognizing the few extra characters diff treated it as a completely substituted new paragraph.
  • Bug 349 has been marked as a duplicate of this bug. ***

Created attachment 9885

Histories are full of completely useless diffs like this (just a random example, things can get much worse).

Word-level diff gives better results in such cases, see screenshot of a simple dwdiff -c (1.9; I see there are further improvements in later releases).


dwdiff.png (768×1 px, 205 KB)

(In reply to comment #6)

Word-level diff gives better results in such cases, see screenshot of a simple
dwdiff -c (1.9; I see there are further improvements in later releases).

According to docs (which are outdated) wikidiff2 «performs word-level (space-delimited) diffs» (now they're [always?] character-level), so it probably should be able to handle whitespace in a more sensible way, but I don't know how the different features can be merged/balanced. Moving under wikidiff2 anyway.

The bad matching of paragraphs is definitely harming my productivity. Raising to a bug to give it credit it should have.

  • Bug 23704 has been marked as a duplicate of this bug. ***

sumanah wrote:

(In reply to comment #10)

Here is a fresh example where the diff algorithm fails:

That example is still kind of annoying, yeah.

mr.heat wrote:

(In reply to comment #11)

(In reply to comment #10)

That example is still kind of annoying, yeah.

As announced in bug #33331 I improved my user script a lot in the past months.

Besides other features (it shrinks the word-level highlighting to character-level and improves the highlighting for single characters) it also fixes bad line matching like in the example above.

On of the reasons for bad line matching are spaces in otherwise empty lines. If a space is added to or removed from an empty line the diff algorithm gets confused. It tries to find an other empty line with the same amount of spaces. It will find one. But in almost all cases these empty lines don't belong together.

My proposed fix is to simply ignore all trailing whitespace when matching lines. Trailing whitespace never have a meaning in the wiki syntax. It's good to highlight it in the diff. But it should be ignored in the first step when the algorithm tries to match lines.

sumanah wrote:

I'm removing myself from cc as I prepare to leave Wikimedia Foundation, but I will leave my 2 cents here: improving the line matching in diffs seems, to me, a cool project that could go in .

(In reply to Nemo from comment #15)

Cc bawolff due to

It should be noted that displaying diffs and doing edit merges/edit conflicts use two different code paths, probably with different algorithms. Better line matching would be nice in both cases.

Change 281285 had a related patch set uploaded (by Jdlrobson):
Show moved lines in diff view using JavaScript/CSS

You can move stuff -

Screen Shot 2016-04-03 at 4.14.53 PM.png (542×1 px, 215 KB)
- yay. Crude design but hopefully gives idea.

Change 281285 abandoned by Jdlrobson:
Show moved lines in diff view using JavaScript/CSS

Preserved forever in

With the resolution of T195375, the example diff is rather ... different than it was before, showing the paragraph having been moved to a point before the lines deleted in the same diff. I don't know whether to consider that an improvement on that diff, but it might make solving this task somewhat easier.

Indeed. In fact I had expected that development to fix most diffs here, but I see that's not the case: most of the examples above are still valid. I'm adding a couple screenshots for reference because it's very hard to reconstruct how diffs looked in the past:

2018-06-21_Translate diff.png (856×1 px, 115 KB)

2018-06-22_Lawrence diff.png (790×1 px, 134 KB)

2018-06-23_fibres diff.png (785×1 px, 114 KB)

FT2's example is still very relevant, although the paragraphs which superficially looked identical actually do have some minor difference in the middle, in addition to some markup change of a character or two at the beginning.