GitoxideLabs/gitoxide gix-imara-diff-v0.3.2

gix-imara-diff v0.3.2

on GitHub

Bug Fixes

• compact removals before additions

  Text merges of short inputs with repeated lines can choose a different
  alignment from git merge-file: issue #3076 case 1 falsely conflicts, and
  case 5 silently drops a repeated line. Cases 2, 3, and 4 already agree
  with Git after the recent Myers improvements.

  Run the removal-side post-processing pass before the addition-side pass.
  Each pass aligns its movable groups with the other side's current groups,
  so the order affects which equally valid diff alignment survives. Fix this
  in the shared post-processor for merge, diff, blame, and word-diff callers.

  Add all five exact minimized inputs to the existing gix-merge baseline,
  including their missing final newlines. Compare both merge directions
  against Git's output and conflict status.

  Git reference: git merge-file -p ours base theirs with Git 2.54.0
  (Apple Git-157). The reference checkout's xdiff/xmerge.c and
  xdiff/xdiffi.c call xdl_change_compact() on xdf1 before xdf2.
  The reference checkout reports 2.55.0.782.g1630431f32.dirty.

• number the edit cost of a Myers split like xdl_split()
  When the middle snake of a split is expensive to find, Git's xdl_split() first tries a
  heuristic that accepts a good enough snake once the edit cost exceeds heur_min, and gives
  up with the furthest reaching path once the cost reaches mxcost. It counts that cost from
  1, in for (ec = 1;; ec++), and checks the limit at the end of each round.

  gix-imara-diff counted from 0 and checked the limit before each round, so it searched one
  round longer than Git, applied the heuristic one round later, and scaled its threshold
  (XDL_K_HEUR * ec) with a cost that was one too small. Large diffs could then split
  differently and come out with other line counts than git diff.

  The cost is now counted the way Git counts it. Unlike Git, MyersMinimal remains bounded by
  the same limit, so adversarial inputs still can't make the search quadratic.

  Together with the previous commit, the line counts of every file compared with
  git diff-tree --numstat over the last 4,000 non-merge commits of git.git and the last 1,500
  of gitoxide now agree, as do those of 300 multi-commit git diff ranges across both. Of 216
  pseudo-random file pairs of 30 to 5,000 lines, the released version disagreed with
  git diff --no-index --numstat on 37, and this one on none.

• count lines across the whole input like xdl_cleanup_records()
  Before running Myers, Git prunes lines that can't be matched, and frequent lines that sit
  inside runs of such lines. It judges every line by how often it occurs in the whole other
  file, and derives its frequency limit from the whole file's line count:
  xdl_classify_record() counts every line of both files while preparing them, and only then
  does xdl_trim_ends() strip the common prefix and postfix before xdl_cleanup_records()
  classifies the lines in between.

  gix-imara-diff stripped the common prefix and postfix first and took both the occurrence
  counts and the limits from what remained. Frequent lines like blank lines or braces mostly
  live in the unchanged parts of a file, so they were rarely considered frequent, and lines
  Git prunes were kept and matched instead. Each one made the diff differ from git diff by
  one removal and one insertion. The existing parity tests sidestepped this by making the
  first and last lines differ so nothing could be stripped.

  Now myers::diff() counts the tokens of its whole input and trims the common ends itself.
  That also makes the histogram fallback match xdl_fall_back_diff(), which prepares the
  subrange it is given anew.

  MyersMinimal applied the frequency limit as well, while Git's XDF_NEED_MINIMAL sets it
  to infinity so no line is ever pruned for being frequent.

  Comparing the line counts of every non-merge commit with git diff-tree --numstat over the
  last 4,000 commits of git.git and the last 1,500 of gitoxide, the number of files whose
  counts differed went from 75 to 26 and from 29 to 2 respectively.

Performance

• skip occurrence counting for trivial Myers diffs
  After trimming common prefixes and suffixes, an empty side means the
  remaining region contains only insertions or deletions, or both inputs
  are identical.

  Return early in these cases, avoiding occurrence counting,
  preprocessing, and Myers search. Nontrivial comparisons still use
  occurrence counts and frequency limits from the complete inputs.

Commit Statistics

• 11 commits contributed to the release over the course of 14 calendar days.
• 14 days passed between releases.
• 4 commits were understood as conventional.
• 1 unique issue was worked on: #3076

Commit Details