[PATCH v2 2/2] diffcore_rename(): use a stable sort
- From
Johannes Schindelin via GitGitGadget <gitgitgadget@gmail.com>
- Date
- Sep 30, 2019, 17:21 UTC
- Message-ID
- <442140438aa0363c53cbfe1fe07219730f042e48.1569864113.git.gitgitgadget@gmail.com>
- In-Reply-To
- <pull.352.v2.git.gitgitgadget@gmail.com>
From: Johannes Schindelin <johannes.schindelin@gmx.de>
During Git's rename detection, the file names are sorted. At the moment, this job is performed by `qsort()`. As that function is not guaranteed to implement a stable sort algorithm, this can lead to inconsistent and/or surprising behavior: a rename might be detected differently depending on the platform where Git was run.
The `qsort()` in MS Visual C's runtime does _not_ implement a stable sort algorithm, and it even leads to an inconsistency leading to a test failure in t3030.35 "merge-recursive remembers the names of all base trees": a different code path than on Linux is taken in the rename detection of an ambiguous rename between either `e` to `a` or `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_stable_qsort()` to avoid this inconsistency.
Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de> --- diffcore-rename.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/diffcore-rename.c b/diffcore-rename.c index 9624864858..9042936aba 100644 --- a/diffcore-rename.c +++ b/diffcore-rename.c @@ -585,7 +585,7 @@ void diffcore_rename(struct diff_options *options) stop_progress(&progress); /* cost matrix sorted by most to least similar pair */ - QSORT(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