shortlog: use a stable sort
PATCH 1/1 shortlog: use a stable sort
From: Johannes Schindelin <[email protected]>
When sorting the output of git shortlog by count, a list of authors in alphabetical order is then sorted by contribution count. Obviously, the idea is to maintain the alphabetical order for items with identical contribution count.
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: items with identical contribution count could lose their alphabetical sub-order.
The qsort() in MS Visual C's runtime does _not_ implement a stable sort algorithm, and under certain circumstances this even causes a test failure in t4201.21 "shortlog can match multiple groups", where two authors both are listed with 2 contributions, and are listed in inverse alphabetical order.
Let's instead use the stable sort provided by git_stable_qsort() to avoid this inconsistency.
This is a companion to 2049b8dc65 (diffcore_rename(): use a stable sort, 2019-09-30).
---
shortlog: use a stable sort
This is another fall-out from validating Git for Windows v2.37.1 via the reinstated Azure Pipeline.
The most valid question a reviewer might have about this patch is: "But why does our current CI not fail in the vs-test job?". The answer is surprisingly trivial: Because our CMake-based definition universally defines INTERNAL_QSORT
[https://github.com/git/git/blob/v2.37.1/contrib/buildsystems/CMakeLists.txt#L227],
which should actually not even be necessary, while the Azure Pipeline I used still calls make vcxproj to generate the Visual Studio build definition and does not define that flag.
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1290%2Fdscho%2Fshortlog-requires-stable-sort-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1290/dscho/shortlog-requires-stable-sort-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/1290
builtin/shortlog.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
builtin/shortlog.c +1 -1
@@ -443,7 +443,7 @@ void shortlog_output(struct shortlog *log)struct strbuf sb =STRBUF_INIT ;if (log->sort_by_number) -QSORT (log->list.items, log->list.nr, +STABLE_QSORT (log->list.items, log->list.nr, log->summary ? compare_by_counter : compare_by_list);for (i =0 ; i < log->list.nr; i++) {const struct string_list_item *item = &log->list.items[i];
base-commit: bbea4dcf42b28eb7ce64a6306cdde875ae5d09ca
Signature · 1 line
gitgitgadget
"Johannes Schindelin via GitGitGadget" <[email protected]>
builtin/shortlog.c void shortlog_output(struct shortlog *log) · line 446
Quoted 8 lines · writes:
When sorting the output of
git shortlogby count, a list of authors in alphabetical order is then sorted by contribution count. Obviously, the idea is to maintain the alphabetical order for items with identical contribution count.
...builtin/shortlog.c +1
-1if (log->sort_by_number) - QSORT(log->list.items, log->list.nr, + STABLE_QSORT(log->list.items, log->list.nr,
Makes perfect sense. Will queue.
Thanks.
"Johannes Schindelin via GitGitGadget" <[email protected]>
Quoted 7 lines · writes:
why does our current CI not fail in the vs-test job?". The answer is surprisingly trivial: Because our CMake-based definition universally defines
INTERNAL_QSORT
[https://github.com/git/git/blob/v2.37.1/contrib/buildsystems/CMakeLists.txt#L227],
which should actually not even be necessary, while the Azure Pipeline I used still calls make vcxproj to generate the Visual Studio build definition and does not define that flag.
Diversity in test environments is very good.