Tracking: match `git diff` slider algorithm more closely in `gix-diff`

[cruessler]

This is a tracking issue related to what’s known as the “diff slider problem”. When calculating the diff between two versions of a file, a hunk can be ambiguous with respect to where it starts and ends. Consider the following example:

 fn test_a_different_thing() {
 }
 
+#[test]
+fn test_something() {
+}
+
 #[test]
 fn test_something_else() {
 } 

The following diff is, technically speaking, equally valid, even though human readers most likely would prefer the above diff.

 fn test_a_different_thing() {
 }
 
 #[test]
+fn test_something() {
+}
+
+#[test]
 fn test_something_else() {
 } 

gix-diff relies on imara-diff 0.1 under the hood for it’s diffing algorithm. There’s a significant number of cases, though, where imara-diff 0.1 and git diff yield different results as they employ different heuristics with respect to moving ambiguous diff hunks up or down.

There is an experimental feature flag in gix-diff (blob-experimental) that uses imara-diff 0.2. imara-diff 0.2 comes closer to what git diff returns, though it still doesn’t match its output in all cases.

We assume that most people would expect gix-diff to yield the same results as git diff. Based on this assumption, we want to track progress towards closing the gap between gix-diff and git diff with respect to slider placement.

Tasks

• Extract a set of baseline tests for use in gix-diff/tests
• Document how closely imara-diff matches git diff
• Port git diff postprocessing heuristic for use with imara-diff 0.2

Sources

https://github.com/mhagger/diff-slider-tools

Related

• Add feature flag blame-experimental to gix #2307
• Update to imara-diff 0.2 in diff slider test #2288
• Update gix-blame to imara-diff 0.2 #2287
• Add imara-diff v0.2 with slider heuristics support #2286
• Account for "\ No newline at end of file" in baseline diff parser #2285
• Report number of non-matching diffs in slider test #2276
• Exclude expectrl and imara-diff from grouped version updates #2269
• Add script to generate tests cases for gix-diff #2197

• Merged, but later reverted: Add Sink that implements git's diffing improvement heuristics #2011

[Byron]

Thanks for getting this started!

Could we have a task-list/checkbox list in the issue description to show what's there and what's still planned to do? This is more of a tool for both of us to align, and I would then add what I think to your initial take on it.

Thanks again!

[cruessler]

I’ve updated the issue, adding the PRs that are related to imara-diff 0.2. Feel free to make further changes if something’s missing or not accurate!

[Byron]

Thanks, and sorry for the ambiguity. What I meant is to have a task list to indicate where we are and what's planned.
I thought it's best if you start it so I don't influence you with what I'd come up with, as a tool for alignment :).

[cruessler]

I see. 😂 I’ve added 3 items to the “Related” section.

[Byron]

Getting there :). I have turned these into tasks, and thought it would also be good to have ticked boxes for what's already been done, on a high level.
But even as is it's good to offer perspective.