Git's rename detection requires a stable sort
cover Git's rename detection requires a stable sort
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.
Johannes Schindelin (2):
Move git_sort(), a stable sort, into into libgit.a diffcore_rename(): use a stable sort
Makefile | 2 +- compat/mingw.c | 5 ----- diffcore-rename.c | 2 +- git-compat-util.h | 4 +++- compat/qsort.c => qsort.c | 2 +- 5 files changed, 6 insertions(+), 9 deletions(-) rename compat/qsort.c => qsort.c (97%)
base-commit: 4615a8cb5b3a8d4959c30338925b1fa3b948ae52
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-352%2Fdscho%2Frename-needs-stable-sort-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-352/dscho/rename-needs-stable-sort-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/352
Signature · 1 line
gitgitgadget
PATCH 2/2 diffcore_rename(): use a stable sort
From: Johannes Schindelin <[email protected]>
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_sort() to avoid this inconsistency.
--- diffcore-rename.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
diffcore-rename.c +1 -1
@@ -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); +QSORT_STABLE (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 )
Signature · 1 line
gitgitgadget
PATCH 1/2 Move git_sort(), a stable sort, into into libgit.a
In reply to Johannes Schindelin via GitGitGadgetFrom: Johannes Schindelin <[email protected]>
The qsort() function is not guaranteed to be stable, i.e. it does not promise to maintain the order of items it is told to consider equal. In contrast, the git_sort() function we carry in compat/qsort.c _is_ stable, by virtue of implementing a merge sort algorithm.
In preparation for using a stable sort in Git's rename detection, move the stable sort into libgit.a so that it is compiled in unconditionally.
Note: this also makes the hack obsolete that was introduced in fe21c6b285d (mingw: reencode environment variables on the fly (UTF-16 <-> UTF-8), 2018-10-30), where we included compat/qsort.c directly in compat/mingw.c to use the stable sort.
--- Makefile | 2 +- compat/mingw.c | 5 ----- git-compat-util.h | 4 +++- compat/qsort.c => qsort.c | 2 +- 4 files changed, 5 insertions(+), 8 deletions(-) rename compat/qsort.c => qsort.c (97%)
Makefile +1 -1
@@ -950,6 +950,7 @@ LIB_OBJS += prio-queue.o LIB_OBJS += progress.o LIB_OBJS += prompt.o LIB_OBJS += protocol.o +LIB_OBJS += qsort.o LIB_OBJS += quote.o LIB_OBJS += range-diff.o LIB_OBJS += reachable.o
@@ -1714,7 +1715,6 @@ ifdef NO_GETPAGESIZE endif ifdef INTERNAL_QSORT COMPAT_CFLAGS += -DINTERNAL_QSORT - COMPAT_OBJS += compat/qsort.o endif ifdef HAVE_ISO_QSORT_S COMPAT_CFLAGS += -DHAVE_ISO_QSORT_S
compat/mingw.c +0 -5
@@ -1229,11 +1229,6 @@ static int wenvcmp(const void *a, const void *b)return _wcsnicmp (p, q, p_len); } -/* We need a stable sort to convert the environment between UTF-16 <-> UTF-8 */ -#ifndef INTERNAL_QSORT -#include "qsort.c" -#endif -/* * Build an environment block combining the inherited environment * merged with the given list of settings.
git-compat-util.h +3 -1
@@ -1094,9 +1094,9 @@ static inline int strtol_i(char const *s, int base, int *result)return 0 ; } -#ifdef INTERNAL_QSORT void git_qsort (void *base,size_t nmemb,size_t size,int (*compar)(const void *,const void *)); +#ifdef INTERNAL_QSORT #define qsort git_qsort#endif
@@ -1108,6 +1108,8 @@ static inline void sane_qsort(void *base, size_t nmemb, size_t size,qsort (base, nmemb, size, compar); } +#define QSORT_STABLE (base, n, compar) git_qsort((base), (n), sizeof(*(base)), compar) +#ifndef HAVE_ISO_QSORT_S int git_qsort_s (void *base,size_t nmemb,size_t size,int (*compar)(const void *,const void *,void *),void *ctx);
qsort.c renamed from compat/qsort.c +1 -1
@@ -1,4 +1,4 @@ -#include "../git-compat-util.h" +#include "git-compat-util.h" /* * A merge sort implementation, simplified from the qsort implementation
Signature · 1 line
gitgitgadget
Re: [PATCH 1/2] Move git_sort(), a stable sort, into into libgit.a
"Johannes Schindelin via GitGitGadget" <[email protected]>
Quoted 7 lines · writes:
--- Makefile | 2 +- compat/mingw.c | 5 ----- git-compat-util.h | 4 +++- compat/qsort.c => qsort.c | 2 +- 4 files changed, 5 insertions(+), 8 deletions(-) rename compat/qsort.c => qsort.c (97%)
Quite pleasing.
compat/mingw.c static int wenvcmp(const void *a, const void *b) · line 1236
Quoted 13 lines
compat/mingw.c +0
-5@@ -1229,11 +1229,6 @@ static int wenvcmp(const void *a, const void *b)return _wcsnicmp (p, q, p_len); } -/* We need a stable sort to convert the environment between UTF-16 <-> UTF-8 */ -#ifndef INTERNAL_QSORT -#include "qsort.c" -#endif -
Especially these ;-)
qsort.c line 1
Quoted 10 lines
qsort.c renamed from compat/qsort.c +1
-1@@ -1,4 +1,4 @@ -#include "../git-compat-util.h" +#include "git-compat-util.h"
I however do not think this goes far enough. With a bit more effort would make the intention of the API more obvious.
What we are saying now is that
(1) some platforms do not even have qsort()
(2) some codepaths do care the stability of sorting
the former used to be the reason why we called our implementation git_qsort() and aliased qsort() to use git_qsort().
But now (2) is in the picture, we would probably want to make it more clear that our own implementation is not about having a sort function that behaves like qsort() and We want a lot more out of it (namely, stability). It probably is time to rename git_qsort() to git_stable_qsort() or something like that.
Macros QSORT() and QSORT_S() are about having a convenient and less error-prone thin wrapper that retains an interface similar to qsort(3) and qsort_s(3) that developers are familiar with, so they can and should stay the same name, and it is perfectly fine if the former called qsort() that in turn calls git_stable_qsort() on some platforms.
And that way, if/when the calling site of QSORT() (not the calling site of STABLE_QSORT()) needs a more performant but unstable sort implementation, we can safely give the most sensible name for it, which is git_qsort().
Other than that, the two patches look good to me. Thanks for working on this topic.
Re: [PATCH 1/2] Move git_sort(), a stable sort, into into libgit.a
Hi Junio,
Quoted 64 lines · Junio C Hamano
"Johannes Schindelin via GitGitGadget" <[email protected]>
Quoted 7 lines · writes:
--- Makefile | 2 +- compat/mingw.c | 5 ----- git-compat-util.h | 4 +++- compat/qsort.c => qsort.c | 2 +- 4 files changed, 5 insertions(+), 8 deletions(-) rename compat/qsort.c => qsort.c (97%)Quite pleasing.
compat/mingw.c static int wenvcmp(const void *a, const void *b) · line 1236
Quoted 13 lines
compat/mingw.c +0
-5@@ -1229,11 +1229,6 @@ static int wenvcmp(const void *a, const void *b)return _wcsnicmp (p, q, p_len); } -/* We need a stable sort to convert the environment between UTF-16 <-> UTF-8 */ -#ifndef INTERNAL_QSORT -#include "qsort.c" -#endif -Especially these ;-)
qsort.c line 1
Quoted 10 lines
qsort.c renamed from compat/qsort.c +1
-1@@ -1,4 +1,4 @@ -#include "../git-compat-util.h" +#include "git-compat-util.h" I however do not think this goes far enough. With a bit more effort would make the intention of the API more obvious.
What we are saying now is that
(1) some platforms do not even have
qsort()
(2) some codepaths do care the stability of sortingthe former used to be the reason why we called our implementation
git_qsort()and aliasedqsort()to usegit_qsort().But now (2) is in the picture, we would probably want to make it more clear that our own implementation is not about having a sort function that behaves like
qsort()and We want a lot more out of it (namely, stability). It probably is time to renamegit_qsort()togit_stable_qsort()or something like that.Macros
QSORT()andQSORT_S()are about having a convenient and less error-prone thin wrapper that retains an interface similar to qsort(3) andqsort_s(3)that developers are familiar with, so they can and should stay the same name, and it is perfectly fine if the former calledqsort()that in turn callsgit_stable_qsort()on some platforms.
Quoted 7 lines
And that way, if/when the calling site of
QSORT()(not the calling site ofSTABLE_QSORT()) needs a more performant but unstable sort implementation, we can safely give the most sensible name for it, which isgit_qsort().Other than that, the two patches look good to me. Thanks for working on this topic.
Okay, I will make that change.
Ciao,
Dscho
PATCH v2 1/2 Move git_sort(), a stable sort, into into libgit.a
In reply to Johannes Schindelin via GitGitGadgetFrom: Johannes Schindelin <[email protected]>
The qsort() function is not guaranteed to be stable, i.e. it does not promise to maintain the order of items it is told to consider equal. In contrast, the git_sort() function we carry in compat/qsort.c _is_ stable, by virtue of implementing a merge sort algorithm.
In preparation for using a stable sort in Git's rename detection, move the stable sort into libgit.a so that it is compiled in unconditionally, and rename it to git_stable_qsort().
Note: this also makes the hack obsolete that was introduced in fe21c6b285d (mingw: reencode environment variables on the fly (UTF-16 <-> UTF-8), 2018-10-30), where we included compat/qsort.c directly in compat/mingw.c to use the stable sort.
--- Makefile | 2 +- compat/mingw.c | 11 +++-------- git-compat-util.h | 9 ++++++--- compat/qsort.c => stable-qsort.c | 6 +++--- 4 files changed, 13 insertions(+), 15 deletions(-) rename compat/qsort.c => stable-qsort.c (89%)
Makefile +1 -1
@@ -983,6 +983,7 @@ LIB_OBJS += shallow.o LIB_OBJS += sideband.o LIB_OBJS += sigchain.o LIB_OBJS += split-index.o +LIB_OBJS += stable-qsort.o LIB_OBJS += strbuf.o LIB_OBJS += streaming.o LIB_OBJS += string-list.o
@@ -1714,7 +1715,6 @@ ifdef NO_GETPAGESIZE endif ifdef INTERNAL_QSORT COMPAT_CFLAGS += -DINTERNAL_QSORT - COMPAT_OBJS += compat/qsort.o endif ifdef HAVE_ISO_QSORT_S COMPAT_CFLAGS += -DHAVE_ISO_QSORT_S
compat/mingw.c +3 -8
@@ -1229,11 +1229,6 @@ static int wenvcmp(const void *a, const void *b)return _wcsnicmp (p, q, p_len); } -/* We need a stable sort to convert the environment between UTF-16 <-> UTF-8 */ -#ifndef INTERNAL_QSORT -#include "qsort.c" -#endif -/* * Build an environment block combining the inherited environment * merged with the given list of settings.
@@ -1272,8 +1267,8 @@ static wchar_t *make_environment_block(char **deltaenv)/* * If there is a deltaenv, let's accumulate all keys into `array`, -* sort them using the stable git_qsort() and then copy, skipping -* duplicate keys +* sort them using the stable git_stable_qsort() and then copy, +* skipping duplicate keys */ for (p = wenv; p && *p; ) {ALLOC_GROW (array, nr +1 , alloc);
@@ -1296,7 +1291,7 @@ static wchar_t *make_environment_block(char **deltaenv) p += wlen +1 ; } -git_qsort (array, nr,sizeof (*array), wenvcmp); +git_stable_qsort (array, nr,sizeof (*array), wenvcmp);ALLOC_ARRAY (result, size + delta_size);for (p = result, i =0 ; i < nr; i++) {
git-compat-util.h +6 -3
@@ -1094,10 +1094,10 @@ static inline int strtol_i(char const *s, int base, int *result)return 0 ; } +void git_stable_qsort (void *base,size_t nmemb,size_t size, +int (*compar)(const void *,const void *));#ifdef INTERNAL_QSORT -void git_qsort (void *base,size_t nmemb,size_t size, -int (*compar)(const void *,const void *)); -#define qsort git_qsort +#define qsort git_stable_qsort#endif #define QSORT (base, n, compar) sane_qsort((base), (n), sizeof(*(base)), compar)
@@ -1108,6 +1108,9 @@ static inline void sane_qsort(void *base, size_t nmemb, size_t size,qsort (base, nmemb, size, compar); } +#define STABLE_QSORT (base, n, compar) \ + git_stable_qsort((base), (n), sizeof(*(base)), compar) +#ifndef HAVE_ISO_QSORT_S int git_qsort_s (void *base,size_t nmemb,size_t size,int (*compar)(const void *,const void *,void *),void *ctx);
stable-qsort.c renamed from compat/qsort.c +3 -3
@@ -1,4 +1,4 @@ -#include "../git-compat-util.h" +#include "git-compat-util.h" /* * A merge sort implementation, simplified from the qsort implementation
@@ -44,8 +44,8 @@ static void msort_with_tmp(void *b, size_t n, size_t s,memcpy (b, t, (n - n2) * s); } -void git_qsort (void *b,size_t n,size_t s, -int (*cmp)(const void *,const void *)) +void git_stable_qsort (void *b,size_t n,size_t s, +int (*cmp)(const void *,const void *)) {const size_t size =st_mult (n, s);char buf[1024 ];
Signature · 1 line
gitgitgadget
v2 cover Git's rename detection requires a stable sort
In reply to Johannes Schindelin via GitGitGadgetWith 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 protected]>
@@ -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)Signature · 1 line
gitgitgadget
PATCH v2 2/2 diffcore_rename(): use a stable sort
From: Johannes Schindelin <[email protected]>
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.
--- diffcore-rename.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
diffcore-rename.c +1 -1
@@ -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 )
Signature · 1 line
gitgitgadget
"Johannes Schindelin via GitGitGadget" <[email protected]>
Quoted 18 lines · writes:
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):
Movegit_sort(), a stable sort, into into libgit.adiffcore_rename(): use a stable sort
Quoted 7 lines
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%)
Thanks. All looked sensible.
Quoted 3 lines
1: 1202809db7 < -: ---------- Move git_sort(), a stable sort, into into libgit.a -: ---------- > 1: 8a99008a64 Move git_sort(), a stable sort, into into libgit.a
This is where the current range-diff could be improved to shine more. If it were allowed to compute a pairwise diff with rename detection, readers would be able to see that qsort.c from version 1 is renamed to stable-qsort.c in version 2 with minimum adjustment of one function name.