Subject: [PATCH v2 0/2] Git's rename detection requires a stable sort

From: "Johannes Schindelin via GitGitGadget" <[email-masked]>
Date: Mon, 30 Sep 2019 10:21:53 -0700 (PDT)

With the en/merge-recursive-cleanup patches already having advanced to next,
the problem I discovered when rebasing Git for Windows' branch thicket
becomes quite relevant now: t3030.35 fails consistently in the MSVC build &
test (this part of the Azure Pipeline will be upstreamed later).

The solution: use a stable sort.

Note: this patch series is based on top of en/merge-recursive-cleanup.

Changes since v1:

 * The function was renamed to git_stable_qsort(), as per Junio's
   suggestion.

Johannes Schindelin (2):
  Move git_sort(), a stable sort, into into libgit.a
  diffcore_rename(): use a stable sort

 Makefile                         |  2 +-
 compat/mingw.c                   | 11 +++--------
 diffcore-rename.c                |  2 +-
 git-compat-util.h                |  9 ++++++---
 compat/qsort.c => stable-qsort.c |  6 +++---
 5 files changed, 14 insertions(+), 16 deletions(-)
 rename compat/qsort.c => stable-qsort.c (89%)

base-commit: 4615a8cb5b3a8d4959c30338925b1fa3b948ae52
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-352%2Fdscho%2Frename-needs-stable-sort-v2
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-352/dscho/rename-needs-stable-sort-v2
Pull-Request: https://github.com/gitgitgadget/git/pull/352

Range-diff vs v1:

 1:  1202809db7 < -:  ---------- Move git_sort(), a stable sort, into into libgit.a
 -:  ---------- > 1:  8a99008a64 Move git_sort(), a stable sort, into into libgit.a
 2:  a95cdf1e94 ! 2:  442140438a diffcore_rename(): use a stable sort
     @@ -16,7 +16,7 @@
          `a~Temporary merge branch 2_0` to `a` during a recursive merge,
          unexpectedly resulting in a clean merge.
      
     -    Let's use the stable sort provided by `git_sort()` to avoid this
     +    Let's use the stable sort provided by `git_stable_qsort()` to avoid this
          inconsistency.
      
          Signed-off-by: Johannes Schindelin <[email-masked]>
     @@ -29,7 +29,7 @@
       
       	/* cost matrix sorted by most to least similar pair */
      -	QSORT(mx, dst_cnt * NUM_CANDIDATE_PER_DST, score_compare);
     -+	QSORT_STABLE(mx, dst_cnt * NUM_CANDIDATE_PER_DST, score_compare);
     ++	STABLE_QSORT(mx, dst_cnt * NUM_CANDIDATE_PER_DST, score_compare);
       
       	rename_count += find_renames(mx, dst_cnt, minimum_score, 0);
       	if (detect_rename == DIFF_DETECT_COPY)

-- 
gitgitgadget