[PATCH] test-mergesort: plug memory leaks in sort_stdin()

[PATCH] test-mergesort: plug memory leaks in sort_stdin()

[Muhammed Dilshad A]

The sort_stdin() helper allocates an input buffer and a memory pool for
the list of lines, but returns without releasing either. Discard the
pool and release the strbuf after printing the sorted lines.

Add a test for the sort subcommand to t0071. The existing test only
exercises the test subcommand, leaving these leaks undetected by the
regular leak-sanitized test suite.

Signed-off-by: Muhammed Dilshad A <dilsheddilu123@gmail.com>
---
 t/helper/test-mergesort.c | 2 ++
 t/t0071-sort.sh           | 7 +++++++
 2 files changed, 9 insertions(+)

diff --git a/t/helper/test-mergesort.c b/t/helper/test-mergesort.c
index 791e128793..3b8c428b14 100644
--- a/t/helper/test-mergesort.c
+++ b/t/helper/test-mergesort.c
@@ -61,6 +61,8 @@ static int sort_stdin(void)
 		puts(lines->text);
 		lines = lines->next;
 	}
+	mem_pool_discard(&lines_pool, 0);
+	strbuf_release(&sb);
 	return 0;
 }
 
diff --git a/t/t0071-sort.sh b/t/t0071-sort.sh
index 2236a7e956..97890da29f 100755
--- a/t/t0071-sort.sh
+++ b/t/t0071-sort.sh
@@ -8,4 +8,11 @@ test_expect_success 'DEFINE_LIST_SORT_DEBUG' '
 	test-tool mergesort test
 '
 
+test_expect_success 'sort stdin' '
+	printf "%s\n" c a b >input &&
+	printf "%s\n" a b c >expect &&
+	test-tool mergesort sort <input >actual &&
+	test_cmp expect actual
+'
+
 test_done
-- 
2.55.0

Re: [PATCH] test-mergesort: plug memory leaks in sort_stdin()

[Patrick Steinhardt]

On Wed, Oct 07, 2026 at 09:12:05AM +0530, Muhammed Dilshad A wrote:
> The sort_stdin() helper allocates an input buffer and a memory pool for
> the list of lines, but returns without releasing either. Discard the
> pool and release the strbuf after printing the sorted lines.

Makes sense.

> Add a test for the sort subcommand to t0071. The existing test only
> exercises the test subcommand, leaving these leaks undetected by the
> regular leak-sanitized test suite.

I was briefly wondering whether we could get rid of t0071 altogether in
favor of converting the tests into a unit test, and then drop the test
helper. And that's certainly doable, and I'd argue it would also be the
right thing to do. But unfortunately it wouldn't allow us to get rid of
the test helper completely as the "mergesort sort" subcommand is used as
part of our performance tests.

I would claim that the benchmark itself is of dubious value. It was nice
enough to have some numbers when we were working on the implementation
of the mergesort, but carrying it with us nowadays feels like a bit of a
waste as chances for regression are somewhat slim here. And if we ever
wanted to iterate further on the merge sort implementation we could
still introduce a new benchmark, that's easy enough to do.

But anyway, that's of course a much bigger scope, and I'm fine to just
fix the bugs for now.

> diff --git a/t/helper/test-mergesort.c b/t/helper/test-mergesort.c
> index 791e128793..3b8c428b14 100644
> --- a/t/helper/test-mergesort.c
> +++ b/t/helper/test-mergesort.c
> @@ -61,6 +61,8 @@ static int sort_stdin(void)
>  		puts(lines->text);
>  		lines = lines->next;
>  	}
> +	mem_pool_discard(&lines_pool, 0);
> +	strbuf_release(&sb);
>  	return 0;
>  }

The fix is obviously correct.

> diff --git a/t/t0071-sort.sh b/t/t0071-sort.sh
> index 2236a7e956..97890da29f 100755
> --- a/t/t0071-sort.sh
> +++ b/t/t0071-sort.sh
> @@ -8,4 +8,11 @@ test_expect_success 'DEFINE_LIST_SORT_DEBUG' '
>  	test-tool mergesort test
>  '
>  
> +test_expect_success 'sort stdin' '
> +	printf "%s\n" c a b >input &&
> +	printf "%s\n" a b c >expect &&
> +	test-tool mergesort sort <input >actual &&
> +	test_cmp expect actual
> +'

And having a test makes sense, I guess.

I noticed that there's another "generate" subcommand here that is
entirely unused. Do we maybe want to also remove it while at it? The
test suite passes with the below diff.

Thanks!

Patrick

diff --git a/t/helper/test-mergesort.c b/t/helper/test-mergesort.c
index 791e128793..9200c4bb4a 100644
--- a/t/helper/test-mergesort.c
+++ b/t/helper/test-mergesort.c
@@ -114,16 +114,6 @@ static struct dist {
 	DIST(shuffle),
 };
 
-static const struct dist *get_dist_by_name(const char *name)
-{
-	int i;
-	for (i = 0; i < ARRAY_SIZE(dist); i++) {
-	       if (!strcmp(dist[i].name, name))
-		       return &dist[i];
-	}
-	return NULL;
-}
-
 static void mode_copy(int *arr UNUSED, int n UNUSED)
 {
 	/* nothing */
@@ -237,41 +227,6 @@ static struct mode {
 	MODE(unriffle_skewed),
 };
 
-static const struct mode *get_mode_by_name(const char *name)
-{
-	int i;
-	for (i = 0; i < ARRAY_SIZE(mode); i++) {
-	       if (!strcmp(mode[i].name, name))
-		       return &mode[i];
-	}
-	return NULL;
-}
-
-static int generate(int argc, const char **argv)
-{
-	const struct dist *dist = NULL;
-	const struct mode *mode = NULL;
-	int i, n, m, *arr;
-
-	if (argc != 4)
-		return 1;
-
-	dist = get_dist_by_name(argv[0]);
-	mode = get_mode_by_name(argv[1]);
-	n = strtol(argv[2], NULL, 10);
-	m = strtol(argv[3], NULL, 10);
-	if (!dist || !mode)
-		return 1;
-
-	ALLOC_ARRAY(arr, n);
-	dist->fn(arr, n, m);
-	mode->fn(arr, n);
-	for (i = 0; i < n; i++)
-		printf("%08x\n", arr[i]);
-	free(arr);
-	return 0;
-}
-
 static struct stats {
 	int get_next, set_next, compare;
 } stats;
@@ -388,14 +343,11 @@ int cmd__mergesort(int argc, const char **argv)
 	int i;
 	const char *sep;
 
-	if (argc == 6 && !strcmp(argv[1], "generate"))
-		return generate(argc - 2, argv + 2);
 	if (argc == 2 && !strcmp(argv[1], "sort"))
 		return sort_stdin();
 	if (argc > 1 && !strcmp(argv[1], "test"))
 		return run_tests(argc - 2, argv + 2);
-	fprintf(stderr, "usage: test-tool mergesort generate <distribution> <mode> <n> <m>\n");
-	fprintf(stderr, "   or: test-tool mergesort sort\n");
+	fprintf(stderr, "usage: test-tool mergesort sort\n");
 	fprintf(stderr, "   or: test-tool mergesort test [<n>...]\n");
 	fprintf(stderr, "\n");
 	for (i = 0, sep = "distributions: "; i < ARRAY_SIZE(dist); i++, sep = ", ")

Re: [PATCH] test-mergesort: plug memory leaks in sort_stdin()

[Junio C Hamano]

Patrick Steinhardt <ps@pks.im> writes:

> I was briefly wondering whether we could get rid of t0071 altogether in
> favor of converting the tests into a unit test, and then drop the test
> helper. And that's certainly doable, and I'd argue it would also be the
> right thing to do.

Yup, unlike any "test-tool" feature that is specific to some Git
operation, things like mergesort does not need to be part of
end-to-end t[0-9]{4}-*.sh test suite.

> But anyway, that's of course a much bigger scope, and I'm fine to just
> fix the bugs for now.

;-).

> I noticed that there's another "generate" subcommand here that is
> entirely unused. Do we maybe want to also remove it while at it? The
> test suite passes with the below diff.

Great.

Thanks.

[PATCH v2 0/3] mergesort: move tests to Clar and retire the helper

[Muhammed Dilshad A]

Hi Patrick,

Thanks for the review. I followed up on the larger cleanup you mentioned.
The sorting tests now run in Clar, and I have removed the old benchmark
and its helper. This also removes the unused generate subcommand.

The new suite keeps all 1,680 cases from the old certification test and
adds checks for empty and small lists using both sort macros. It checks
sorting order, stability and list length. Cleanup frees the backing
arrays directly, so a failed assertion does not need to walk list links.

Changes since v1:

* Patch 1 is unchanged.
* Patch 2 moves the tests to Clar and removes the unused generate and
  test commands. The sort command remains available for the benchmark.
* Patch 3 removes p0071 and the remaining sort helper, along with their
  build and command registrations.

I kept the leak fix first so it can still be applied on its own if you
would prefer to keep the broader cleanup for a separate series.

The Make and Meson unit tests pass, and the mergesort unit suite also
passes with LeakSanitizer enabled. The production sorting implementation
is unchanged.

Muhammed Dilshad A (3):
  test-mergesort: plug memory leaks in sort_stdin()
  mergesort: move sorting tests to the unit-test framework
  t: retire the sorting benchmark and mergesort helper

 Makefile                   |   2 +-
 t/helper/meson.build       |   1 -
 t/helper/test-mergesort.c  | 408 -------------------------------------
 t/helper/test-tool.c       |   1 -
 t/helper/test-tool.h       |   1 -
 t/meson.build              |   3 +-
 t/perf/p0071-sort.sh       |  52 -----
 t/t0071-sort.sh            |  11 -
 t/unit-tests/u-mergesort.c | 369 +++++++++++++++++++++++++++++++++
 9 files changed, 371 insertions(+), 477 deletions(-)
 delete mode 100644 t/helper/test-mergesort.c
 delete mode 100755 t/perf/p0071-sort.sh
 delete mode 100755 t/t0071-sort.sh
 create mode 100644 t/unit-tests/u-mergesort.c


base-commit: 6de20f6092dcf9bdb1c8efe03db4b70c82b423dd
-- 
2.55.0

[PATCH v2 1/3] test-mergesort: plug memory leaks in sort_stdin()

[Muhammed Dilshad A]

The sort_stdin() helper allocates an input buffer and a memory pool for
the list of lines, but returns without releasing either. Discard the
pool and release the strbuf after printing the sorted lines.

Add a test for the sort subcommand to t0071. The existing test only
exercises the test subcommand, leaving these leaks undetected by the
regular leak-sanitized test suite.

Signed-off-by: Muhammed Dilshad A <dilsheddilu123@gmail.com>
---
 t/helper/test-mergesort.c | 2 ++
 t/t0071-sort.sh           | 7 +++++++
 2 files changed, 9 insertions(+)

diff --git a/t/helper/test-mergesort.c b/t/helper/test-mergesort.c
index 791e128793..3b8c428b14 100644
--- a/t/helper/test-mergesort.c
+++ b/t/helper/test-mergesort.c
@@ -61,6 +61,8 @@ static int sort_stdin(void)
 		puts(lines->text);
 		lines = lines->next;
 	}
+	mem_pool_discard(&lines_pool, 0);
+	strbuf_release(&sb);
 	return 0;
 }
 
diff --git a/t/t0071-sort.sh b/t/t0071-sort.sh
index 2236a7e956..97890da29f 100755
--- a/t/t0071-sort.sh
+++ b/t/t0071-sort.sh
@@ -8,4 +8,11 @@ test_expect_success 'DEFINE_LIST_SORT_DEBUG' '
 	test-tool mergesort test
 '
 
+test_expect_success 'sort stdin' '
+	printf "%s\n" c a b >input &&
+	printf "%s\n" a b c >expect &&
+	test-tool mergesort sort <input >actual &&
+	test_cmp expect actual
+'
+
 test_done
-- 
2.55.0

[PATCH v2 2/3] mergesort: move sorting tests to the unit-test framework

[Muhammed Dilshad A]

The mergesort certification checks exercise C code directly, so they do
not need a shell test and test-tool command. Move their distributions and
transformations to Clar, retaining the sorted-value, stability and list
length checks. Add small cases for both list sort macros and debug hooks.

Keep node storage available to the cleanup fixture and bound validation
so a failed assertion can release it without walking a broken list.
Remove the unused generate command along with the old test command,
leaving sort available for the sorting benchmark.

Suggested-by: Patrick Steinhardt <ps@pks.im>
Signed-off-by: Muhammed Dilshad A <dilsheddilu123@gmail.com>
---
 Makefile                   |   1 +
 t/helper/test-mergesort.c  | 345 +---------------------------------
 t/meson.build              |   2 +-
 t/t0071-sort.sh            |  18 --
 t/unit-tests/u-mergesort.c | 369 +++++++++++++++++++++++++++++++++++++
 5 files changed, 372 insertions(+), 363 deletions(-)
 delete mode 100755 t/t0071-sort.sh
 create mode 100644 t/unit-tests/u-mergesort.c

diff --git a/Makefile b/Makefile
index a96be506b5..cac535ba19 100644
--- a/Makefile
+++ b/Makefile
@@ -1541,6 +1541,7 @@ CLAR_TEST_SUITES += u-hash
 CLAR_TEST_SUITES += u-hashmap
 CLAR_TEST_SUITES += u-list-objects-filter-options
 CLAR_TEST_SUITES += u-mem-pool
+CLAR_TEST_SUITES += u-mergesort
 CLAR_TEST_SUITES += u-odb-inmemory
 CLAR_TEST_SUITES += u-oid-array
 CLAR_TEST_SUITES += u-oidmap
diff --git a/t/helper/test-mergesort.c b/t/helper/test-mergesort.c
index 3b8c428b14..e8b8de239b 100644
--- a/t/helper/test-mergesort.c
+++ b/t/helper/test-mergesort.c
@@ -1,16 +1,8 @@
-#define DISABLE_SIGN_COMPARE_WARNINGS
-
 #include "test-tool.h"
 #include "mem-pool.h"
 #include "mergesort.h"
 #include "strbuf.h"
 
-static uint32_t minstd_rand(uint32_t *state)
-{
-	*state = (uint64_t)*state * 48271 % 2147483647;
-	return *state;
-}
-
 struct line {
 	char *text;
 	struct line *next;
@@ -66,345 +58,10 @@ static int sort_stdin(void)
 	return 0;
 }
 
-static void dist_sawtooth(int *arr, int n, int m)
-{
-	int i;
-	for (i = 0; i < n; i++)
-		arr[i] = i % m;
-}
-
-static void dist_rand(int *arr, int n, int m)
-{
-	int i;
-	uint32_t seed = 1;
-	for (i = 0; i < n; i++)
-		arr[i] = minstd_rand(&seed) % m;
-}
-
-static void dist_stagger(int *arr, int n, int m)
-{
-	int i;
-	for (i = 0; i < n; i++)
-		arr[i] = (i * m + i) % n;
-}
-
-static void dist_plateau(int *arr, int n, int m)
-{
-	int i;
-	for (i = 0; i < n; i++)
-		arr[i] = (i < m) ? i : m;
-}
-
-static void dist_shuffle(int *arr, int n, int m)
-{
-	int i, j, k;
-	uint32_t seed = 1;
-	for (i = j = 0, k = 1; i < n; i++)
-		arr[i] = minstd_rand(&seed) % m ? (j += 2) : (k += 2);
-}
-
-#define DIST(name) { #name, dist_##name }
-
-static struct dist {
-	const char *name;
-	void (*fn)(int *arr, int n, int m);
-} dist[] = {
-	DIST(sawtooth),
-	DIST(rand),
-	DIST(stagger),
-	DIST(plateau),
-	DIST(shuffle),
-};
-
-static const struct dist *get_dist_by_name(const char *name)
-{
-	int i;
-	for (i = 0; i < ARRAY_SIZE(dist); i++) {
-	       if (!strcmp(dist[i].name, name))
-		       return &dist[i];
-	}
-	return NULL;
-}
-
-static void mode_copy(int *arr UNUSED, int n UNUSED)
-{
-	/* nothing */
-}
-
-static void mode_reverse(int *arr, int n)
-{
-	int i, j;
-	for (i = 0, j = n - 1; i < j; i++, j--)
-		SWAP(arr[i], arr[j]);
-}
-
-static void mode_reverse_1st_half(int *arr, int n)
-{
-	mode_reverse(arr, n / 2);
-}
-
-static void mode_reverse_2nd_half(int *arr, int n)
-{
-	int half = n / 2;
-	mode_reverse(arr + half, n - half);
-}
-
-static int compare_ints(const void *av, const void *bv)
-{
-	const int *ap = av, *bp = bv;
-	int a = *ap, b = *bp;
-	return (a > b) - (a < b);
-}
-
-static void mode_sort(int *arr, int n)
-{
-	QSORT(arr, n, compare_ints);
-}
-
-static void mode_dither(int *arr, int n)
-{
-	int i;
-	for (i = 0; i < n; i++)
-		arr[i] += i % 5;
-}
-
-static void unriffle(int *arr, int n, int *tmp)
-{
-	int i, j;
-	COPY_ARRAY(tmp, arr, n);
-	for (i = j = 0; i < n; i += 2)
-		arr[j++] = tmp[i];
-	for (i = 1; i < n; i += 2)
-		arr[j++] = tmp[i];
-}
-
-static void unriffle_recursively(int *arr, int n, int *tmp)
-{
-	if (n > 1) {
-		int half = n / 2;
-		unriffle(arr, n, tmp);
-		unriffle_recursively(arr, half, tmp);
-		unriffle_recursively(arr + half, n - half, tmp);
-	}
-}
-
-static void mode_unriffle(int *arr, int n)
-{
-	int *tmp;
-	ALLOC_ARRAY(tmp, n);
-	unriffle_recursively(arr, n, tmp);
-	free(tmp);
-}
-
-static unsigned int prev_pow2(unsigned int n)
-{
-	unsigned int pow2 = 1;
-	while (pow2 * 2 < n)
-		pow2 *= 2;
-	return pow2;
-}
-
-static void unriffle_recursively_skewed(int *arr, int n, int *tmp)
-{
-	if (n > 1) {
-		int pow2 = prev_pow2(n);
-		int rest = n - pow2;
-		unriffle(arr + pow2 - rest, rest * 2, tmp);
-		unriffle_recursively_skewed(arr, pow2, tmp);
-		unriffle_recursively_skewed(arr + pow2, rest, tmp);
-	}
-}
-
-static void mode_unriffle_skewed(int *arr, int n)
-{
-	int *tmp;
-	ALLOC_ARRAY(tmp, n);
-	unriffle_recursively_skewed(arr, n, tmp);
-	free(tmp);
-}
-
-#define MODE(name) { #name, mode_##name }
-
-static struct mode {
-	const char *name;
-	void (*fn)(int *arr, int n);
-} mode[] = {
-	MODE(copy),
-	MODE(reverse),
-	MODE(reverse_1st_half),
-	MODE(reverse_2nd_half),
-	MODE(sort),
-	MODE(dither),
-	MODE(unriffle),
-	MODE(unriffle_skewed),
-};
-
-static const struct mode *get_mode_by_name(const char *name)
-{
-	int i;
-	for (i = 0; i < ARRAY_SIZE(mode); i++) {
-	       if (!strcmp(mode[i].name, name))
-		       return &mode[i];
-	}
-	return NULL;
-}
-
-static int generate(int argc, const char **argv)
-{
-	const struct dist *dist = NULL;
-	const struct mode *mode = NULL;
-	int i, n, m, *arr;
-
-	if (argc != 4)
-		return 1;
-
-	dist = get_dist_by_name(argv[0]);
-	mode = get_mode_by_name(argv[1]);
-	n = strtol(argv[2], NULL, 10);
-	m = strtol(argv[3], NULL, 10);
-	if (!dist || !mode)
-		return 1;
-
-	ALLOC_ARRAY(arr, n);
-	dist->fn(arr, n, m);
-	mode->fn(arr, n);
-	for (i = 0; i < n; i++)
-		printf("%08x\n", arr[i]);
-	free(arr);
-	return 0;
-}
-
-static struct stats {
-	int get_next, set_next, compare;
-} stats;
-
-struct number {
-	int value, rank;
-	struct number *next;
-};
-
-DEFINE_LIST_SORT_DEBUG(static, sort_numbers, struct number, next,
-		       stats.get_next++, stats.set_next++);
-
-static int compare_numbers(const struct number *an, const struct number *bn)
-{
-	int a = an->value, b = bn->value;
-	stats.compare++;
-	return (a > b) - (a < b);
-}
-
-static void clear_numbers(struct number *list)
-{
-	while (list) {
-		struct number *next = list->next;
-		free(list);
-		list = next;
-	}
-}
-
-static int test(const struct dist *dist, const struct mode *mode, int n, int m)
-{
-	int *arr;
-	size_t i;
-	struct number *curr, *list, **tail;
-	int is_sorted = 1;
-	int is_stable = 1;
-	const char *verdict;
-	int result = -1;
-
-	ALLOC_ARRAY(arr, n);
-	dist->fn(arr, n, m);
-	mode->fn(arr, n);
-	for (i = 0, tail = &list; i < n; i++) {
-		curr = xmalloc(sizeof(*curr));
-		curr->value = arr[i];
-		curr->rank = i;
-		*tail = curr;
-		tail = &curr->next;
-	}
-	*tail = NULL;
-
-	stats.get_next = stats.set_next = stats.compare = 0;
-	sort_numbers(&list, compare_numbers);
-
-	QSORT(arr, n, compare_ints);
-	for (i = 0, curr = list; i < n && curr; i++, curr = curr->next) {
-		if (arr[i] != curr->value)
-			is_sorted = 0;
-		if (curr->next && curr->value == curr->next->value &&
-		    curr->rank >= curr->next->rank)
-			is_stable = 0;
-	}
-	if (i < n) {
-		verdict = "too short";
-	} else if (curr) {
-		verdict = "too long";
-	} else if (!is_sorted) {
-		verdict = "not sorted";
-	} else if (!is_stable) {
-		verdict = "unstable";
-	} else {
-		verdict = "OK";
-		result = 0;
-	}
-
-	printf("%-9s %-16s %8d %8d %8d %8d %8d %s\n",
-	       dist->name, mode->name, n, m, stats.get_next, stats.set_next,
-	       stats.compare, verdict);
-
-	clear_numbers(list);
-	free(arr);
-
-	return result;
-}
-
-/*
- * A version of the qsort certification program from "Engineering a Sort
- * Function" by Bentley and McIlroy, Software—Practice and Experience,
- * Volume 23, Issue 11, 1249–1265 (November 1993).
- */
-static int run_tests(int argc, const char **argv)
-{
-	const char *argv_default[] = { "100", "1023", "1024", "1025" };
-	if (!argc)
-		return run_tests(ARRAY_SIZE(argv_default), argv_default);
-	printf("%-9s %-16s %8s %8s %8s %8s %8s %s\n",
-	       "distribut", "mode", "n", "m", "get_next", "set_next",
-	       "compare", "verdict");
-	while (argc--) {
-		int i, j, m, n = strtol(*argv++, NULL, 10);
-		for (i = 0; i < ARRAY_SIZE(dist); i++) {
-			for (j = 0; j < ARRAY_SIZE(mode); j++) {
-				for (m = 1; m < 2 * n; m *= 2) {
-					if (test(&dist[i], &mode[j], n, m))
-						return 1;
-				}
-			}
-		}
-	}
-	return 0;
-}
-
 int cmd__mergesort(int argc, const char **argv)
 {
-	int i;
-	const char *sep;
-
-	if (argc == 6 && !strcmp(argv[1], "generate"))
-		return generate(argc - 2, argv + 2);
 	if (argc == 2 && !strcmp(argv[1], "sort"))
 		return sort_stdin();
-	if (argc > 1 && !strcmp(argv[1], "test"))
-		return run_tests(argc - 2, argv + 2);
-	fprintf(stderr, "usage: test-tool mergesort generate <distribution> <mode> <n> <m>\n");
-	fprintf(stderr, "   or: test-tool mergesort sort\n");
-	fprintf(stderr, "   or: test-tool mergesort test [<n>...]\n");
-	fprintf(stderr, "\n");
-	for (i = 0, sep = "distributions: "; i < ARRAY_SIZE(dist); i++, sep = ", ")
-		fprintf(stderr, "%s%s", sep, dist[i].name);
-	fprintf(stderr, "\n");
-	for (i = 0, sep = "modes: "; i < ARRAY_SIZE(mode); i++, sep = ", ")
-		fprintf(stderr, "%s%s", sep, mode[i].name);
-	fprintf(stderr, "\n");
+	fprintf(stderr, "usage: test-tool mergesort sort\n");
 	return 129;
 }
diff --git a/t/meson.build b/t/meson.build
index f65eb04684..2752321e0d 100644
--- a/t/meson.build
+++ b/t/meson.build
@@ -6,6 +6,7 @@ clar_test_suites = [
   'unit-tests/u-hashmap.c',
   'unit-tests/u-list-objects-filter-options.c',
   'unit-tests/u-mem-pool.c',
+  'unit-tests/u-mergesort.c',
   'unit-tests/u-odb-inmemory.c',
   'unit-tests/u-oid-array.c',
   'unit-tests/u-oidmap.c',
@@ -119,7 +120,6 @@ integration_tests = [
   't0067-parse_pathspec_file.sh',
   't0068-for-each-repo.sh',
   't0070-fundamental.sh',
-  't0071-sort.sh',
   't0080-unit-test-output.sh',
   't0081-find-pack.sh',
   't0090-cache-tree.sh',
diff --git a/t/t0071-sort.sh b/t/t0071-sort.sh
deleted file mode 100755
index 97890da29f..0000000000
--- a/t/t0071-sort.sh
+++ /dev/null
@@ -1,18 +0,0 @@
-#!/bin/sh
-
-test_description='verify sort functions'
-
-. ./test-lib.sh
-
-test_expect_success 'DEFINE_LIST_SORT_DEBUG' '
-	test-tool mergesort test
-'
-
-test_expect_success 'sort stdin' '
-	printf "%s\n" c a b >input &&
-	printf "%s\n" a b c >expect &&
-	test-tool mergesort sort <input >actual &&
-	test_cmp expect actual
-'
-
-test_done
diff --git a/t/unit-tests/u-mergesort.c b/t/unit-tests/u-mergesort.c
new file mode 100644
index 0000000000..e621c9ec21
--- /dev/null
+++ b/t/unit-tests/u-mergesort.c
@@ -0,0 +1,369 @@
+#include "unit-test.h"
+#include "mergesort.h"
+
+static uint32_t minstd_rand(uint32_t *state)
+{
+	*state = (uint64_t)*state * 48271 % 2147483647;
+	return *state;
+}
+
+static void dist_sawtooth(int *arr, int n, int m)
+{
+	int i;
+	for (i = 0; i < n; i++)
+		arr[i] = i % m;
+}
+
+static void dist_rand(int *arr, int n, int m)
+{
+	int i;
+	uint32_t seed = 1;
+	for (i = 0; i < n; i++)
+		arr[i] = minstd_rand(&seed) % m;
+}
+
+static void dist_stagger(int *arr, int n, int m)
+{
+	int i;
+	for (i = 0; i < n; i++)
+		arr[i] = (i * m + i) % n;
+}
+
+static void dist_plateau(int *arr, int n, int m)
+{
+	int i;
+	for (i = 0; i < n; i++)
+		arr[i] = (i < m) ? i : m;
+}
+
+static void dist_shuffle(int *arr, int n, int m)
+{
+	int i, j, k;
+	uint32_t seed = 1;
+	for (i = j = 0, k = 1; i < n; i++)
+		arr[i] = minstd_rand(&seed) % m ? (j += 2) : (k += 2);
+}
+
+#define DIST(name) { #name, dist_##name }
+
+static struct dist {
+	const char *name;
+	void (*fn)(int *arr, int n, int m);
+} dist[] = {
+	DIST(sawtooth),
+	DIST(rand),
+	DIST(stagger),
+	DIST(plateau),
+	DIST(shuffle),
+};
+
+static void mode_copy(int *arr UNUSED, int n UNUSED)
+{
+	/* nothing */
+}
+
+static void mode_reverse(int *arr, int n)
+{
+	int i, j;
+	for (i = 0, j = n - 1; i < j; i++, j--)
+		SWAP(arr[i], arr[j]);
+}
+
+static void mode_reverse_1st_half(int *arr, int n)
+{
+	mode_reverse(arr, n / 2);
+}
+
+static void mode_reverse_2nd_half(int *arr, int n)
+{
+	int half = n / 2;
+	mode_reverse(arr + half, n - half);
+}
+
+static int compare_ints(const void *av, const void *bv)
+{
+	const int *ap = av, *bp = bv;
+	int a = *ap, b = *bp;
+	return (a > b) - (a < b);
+}
+
+static void mode_sort(int *arr, int n)
+{
+	QSORT(arr, n, compare_ints);
+}
+
+static void mode_dither(int *arr, int n)
+{
+	int i;
+	for (i = 0; i < n; i++)
+		arr[i] += i % 5;
+}
+
+static void unriffle(int *arr, int n, int *tmp)
+{
+	int i, j;
+	COPY_ARRAY(tmp, arr, n);
+	for (i = j = 0; i < n; i += 2)
+		arr[j++] = tmp[i];
+	for (i = 1; i < n; i += 2)
+		arr[j++] = tmp[i];
+}
+
+static void unriffle_recursively(int *arr, int n, int *tmp)
+{
+	if (n > 1) {
+		int half = n / 2;
+		unriffle(arr, n, tmp);
+		unriffle_recursively(arr, half, tmp);
+		unriffle_recursively(arr + half, n - half, tmp);
+	}
+}
+
+static void mode_unriffle(int *arr, int n)
+{
+	int *tmp;
+	ALLOC_ARRAY(tmp, n);
+	unriffle_recursively(arr, n, tmp);
+	free(tmp);
+}
+
+static unsigned int prev_pow2(unsigned int n)
+{
+	unsigned int pow2 = 1;
+	while (pow2 * 2 < n)
+		pow2 *= 2;
+	return pow2;
+}
+
+static void unriffle_recursively_skewed(int *arr, int n, int *tmp)
+{
+	if (n > 1) {
+		int pow2 = prev_pow2(n);
+		int rest = n - pow2;
+		unriffle(arr + pow2 - rest, rest * 2, tmp);
+		unriffle_recursively_skewed(arr, pow2, tmp);
+		unriffle_recursively_skewed(arr + pow2, rest, tmp);
+	}
+}
+
+static void mode_unriffle_skewed(int *arr, int n)
+{
+	int *tmp;
+	ALLOC_ARRAY(tmp, n);
+	unriffle_recursively_skewed(arr, n, tmp);
+	free(tmp);
+}
+
+#define MODE(name) { #name, mode_##name }
+
+static struct mode {
+	const char *name;
+	void (*fn)(int *arr, int n);
+} mode[] = {
+	MODE(copy),
+	MODE(reverse),
+	MODE(reverse_1st_half),
+	MODE(reverse_2nd_half),
+	MODE(sort),
+	MODE(dither),
+	MODE(unriffle),
+	MODE(unriffle_skewed),
+};
+
+static struct stats {
+	int get_next, set_next;
+} stats;
+
+struct number {
+	int value, rank;
+	struct number *next;
+};
+
+DEFINE_LIST_SORT_DEBUG(static, sort_numbers_debug, struct number, next,
+		       stats.get_next++, stats.set_next++);
+DEFINE_LIST_SORT(static, sort_numbers, struct number, next);
+
+static int compare_numbers(const struct number *an, const struct number *bn)
+{
+	int a = an->value, b = bn->value;
+	return (a > b) - (a < b);
+}
+
+/* Free the storage directly, even if an assertion fails on a broken list. */
+static int *values;
+static struct number *numbers;
+
+void test_mergesort__cleanup(void)
+{
+	FREE_AND_NULL(values);
+	FREE_AND_NULL(numbers);
+}
+
+static struct number *prepare_list(const int *arr, int n)
+{
+	int i;
+
+	ALLOC_ARRAY(numbers, n);
+	for (i = 0; i < n; i++) {
+		numbers[i].value = arr[i];
+		numbers[i].rank = i;
+		numbers[i].next = i + 1 < n ? &numbers[i + 1] : NULL;
+	}
+	stats.get_next = stats.set_next = 0;
+	return n ? numbers : NULL;
+}
+
+static void check_list(struct number *list, const int *expected,
+		       const int *ranks, int n, const char *context)
+{
+	struct number *previous = NULL;
+	int i;
+
+	/* Bound traversal so a cycle is reported as an overlong list. */
+	for (i = 0; i < n; i++) {
+		cl_assert_(list, context);
+		cl_assert_equal_i_(list->value, expected[i], "%s: index %d",
+				   context, i);
+		if (previous && previous->value == list->value)
+			cl_assert_lt_i_(previous->rank, list->rank,
+					"%s: stability at index %d", context, i);
+		if (ranks)
+			cl_assert_equal_i_(list->rank, ranks[i],
+					   "%s: rank at index %d", context, i);
+		previous = list;
+		list = list->next;
+	}
+	cl_assert_(list == NULL, context);
+}
+
+/*
+ * A version of the qsort certification program from "Engineering a Sort
+ * Function" by Bentley and McIlroy, Software—Practice and Experience,
+ * Volume 23, Issue 11, 1249–1265 (November 1993).
+ */
+static void certify(const struct dist *distribution)
+{
+	static const int sizes[] = { 100, 1023, 1024, 1025 };
+	size_t i, j;
+	int m;
+
+	for (i = 0; i < ARRAY_SIZE(sizes); i++) {
+		int n = sizes[i];
+
+		for (j = 0; j < ARRAY_SIZE(mode); j++) {
+			for (m = 1; m < 2 * n; m *= 2) {
+				struct number *list;
+				char context[128];
+
+				xsnprintf(context, sizeof(context),
+					  "%s %s n=%d m=%d",
+					  distribution->name, mode[j].name, n, m);
+				ALLOC_ARRAY(values, n);
+				distribution->fn(values, n, m);
+				mode[j].fn(values, n);
+				list = prepare_list(values, n);
+				sort_numbers_debug(&list, compare_numbers);
+				QSORT(values, n, compare_ints);
+				check_list(list, values, NULL, n, context);
+				test_mergesort__cleanup();
+			}
+		}
+	}
+}
+
+void test_mergesort__sawtooth(void)
+{
+	certify(&dist[0]);
+}
+
+void test_mergesort__rand(void)
+{
+	certify(&dist[1]);
+}
+
+void test_mergesort__stagger(void)
+{
+	certify(&dist[2]);
+}
+
+void test_mergesort__plateau(void)
+{
+	certify(&dist[3]);
+}
+
+void test_mergesort__shuffle(void)
+{
+	certify(&dist[4]);
+}
+
+static void check_small(const int *input, const int *expected,
+			const int *ranks, int n, const char *name)
+{
+	int debug;
+
+	for (debug = 0; debug < 2; debug++) {
+		struct number *list = prepare_list(input, n);
+		char context[128];
+
+		xsnprintf(context, sizeof(context), "%s %s n=%d",
+			  debug ? "debug" : "normal", name, n);
+		if (debug)
+			sort_numbers_debug(&list, compare_numbers);
+		else
+			sort_numbers(&list, compare_numbers);
+		check_list(list, expected, ranks, n, context);
+		test_mergesort__cleanup();
+	}
+}
+
+void test_mergesort__empty(void)
+{
+	check_small(NULL, NULL, NULL, 0, "empty");
+}
+
+void test_mergesort__singleton(void)
+{
+	const int input[] = { 42 };
+	const int ranks[] = { 0 };
+
+	check_small(input, input, ranks, ARRAY_SIZE(input), "singleton");
+}
+
+void test_mergesort__reversed_pair(void)
+{
+	const int input[] = { 2, 1 };
+	const int expected[] = { 1, 2 };
+	const int ranks[] = { 1, 0 };
+
+	check_small(input, expected, ranks, ARRAY_SIZE(input), "reversed pair");
+}
+
+void test_mergesort__equal_pair(void)
+{
+	const int input[] = { 1, 1 };
+	const int ranks[] = { 0, 1 };
+
+	check_small(input, input, ranks, ARRAY_SIZE(input), "equal pair");
+}
+
+void test_mergesort__mixed_values(void)
+{
+	const int input[] = { INT_MAX, -1, 0, INT_MIN, -1, INT_MAX, 0 };
+	const int expected[] = { INT_MIN, -1, -1, 0, 0, INT_MAX, INT_MAX };
+	const int ranks[] = { 3, 1, 4, 2, 6, 0, 5 };
+
+	check_small(input, expected, ranks, ARRAY_SIZE(input), "mixed values");
+}
+
+void test_mergesort__debug_hooks(void)
+{
+	const int input[] = { 2, 1 };
+	const int expected[] = { 1, 2 };
+	const int ranks[] = { 1, 0 };
+	struct number *list = prepare_list(input, ARRAY_SIZE(input));
+
+	sort_numbers_debug(&list, compare_numbers);
+	check_list(list, expected, ranks, ARRAY_SIZE(input), "debug hooks");
+	cl_assert_gt_i(stats.get_next, 0);
+	cl_assert_gt_i(stats.set_next, 0);
+}
-- 
2.55.0

Re: [PATCH v2 2/3] mergesort: move sorting tests to the unit-test framework

[Patrick Steinhardt]

On Wed, Oct 07, 2026 at 07:20:24PM +0530, Muhammed Dilshad A wrote:
> The mergesort certification checks exercise C code directly, so they do
> not need a shell test and test-tool command. Move their distributions and
> transformations to Clar, retaining the sorted-value, stability and list
> length checks. Add small cases for both list sort macros and debug hooks.
> 
> Keep node storage available to the cleanup fixture and bound validation
> so a failed assertion can release it without walking a broken list.

Wat...? I have no idea what this means.

I would appreciate it if you would read through the AI generated
messages and ask yourself whether a normal human being would understand
what was being generated. In general, we ask you to fully vet all of the
stuff that is being generated, understand it and convert it into a form
that normal human beings understand.

A commit message is _your_ chance to demonstrate that you understand
what you're contributing. If it's this obviously AI generated it raises
a huge red flag as I will immediately assume that you haven't read any
of the code it wrote.

> diff --git a/t/unit-tests/u-mergesort.c b/t/unit-tests/u-mergesort.c
> new file mode 100644
> index 0000000000..e621c9ec21
> --- /dev/null
> +++ b/t/unit-tests/u-mergesort.c
> @@ -0,0 +1,369 @@
> +#include "unit-test.h"
> +#include "mergesort.h"
> +
> +static uint32_t minstd_rand(uint32_t *state)

All of these distributions are kinda cute. But is it really required to
test the merge sort with half a dozen different distributions? I dunno,
color me sceptical.

That being said, you just retain the old status quo, so okay.

[snip]
> +#define DIST(name) { #name, dist_##name }
> +
> +static struct dist {
> +	const char *name;
> +	void (*fn)(int *arr, int n, int m);
> +} dist[] = {
> +	DIST(sawtooth),
> +	DIST(rand),
> +	DIST(stagger),
> +	DIST(plateau),
> +	DIST(shuffle),
> +};

This also feels quite overengineered now for the unit test infra.

[snip]
> +#define MODE(name) { #name, mode_##name }
> +
> +static struct mode {
> +	const char *name;
> +	void (*fn)(int *arr, int n);
> +} mode[] = {
> +	MODE(copy),
> +	MODE(reverse),
> +	MODE(reverse_1st_half),
> +	MODE(reverse_2nd_half),
> +	MODE(sort),
> +	MODE(dither),
> +	MODE(unriffle),
> +	MODE(unriffle_skewed),
> +};

Same. All of this is way too overengineered. It probably was useful at
one point in time to show performance with these different modes and
distributions. But even with the performance test we don't use those at
all anymore, so it just feels needlessly complex by now.

Patrick

Re: [PATCH v2 2/3] mergesort: move sorting tests to the unit-test framework

[Muhammed Dilshad A]

Hi Patrick,

Sorry, I didn't explain that clearly. The list items are stored in one
allocated array. Cleanup frees that array directly, so it does not have
to follow possibly broken list links.

I'll go through the code and simplify the test setup before sending
another version. I'll also rewrite the commit message to explain the
changes clearly.

Regards,
Dilshad

[PATCH v2 3/3] t: retire the sorting benchmark and mergesort helper

[Muhammed Dilshad A]

p0071 compared sorting implementations during mergesort development.
Retire it as suggested during the unit-test conversion. A new benchmark
can be added if later optimization work needs performance measurements.

The benchmark was the last caller of the sort-only mergesort helper.
Removing it allows us to delete the helper and its build and command
registrations as well.

Suggested-by: Patrick Steinhardt <ps@pks.im>
Signed-off-by: Muhammed Dilshad A <dilsheddilu123@gmail.com>
---
 Makefile                  |  1 -
 t/helper/meson.build      |  1 -
 t/helper/test-mergesort.c | 67 ---------------------------------------
 t/helper/test-tool.c      |  1 -
 t/helper/test-tool.h      |  1 -
 t/meson.build             |  1 -
 t/perf/p0071-sort.sh      | 52 ------------------------------
 7 files changed, 124 deletions(-)
 delete mode 100644 t/helper/test-mergesort.c
 delete mode 100755 t/perf/p0071-sort.sh

diff --git a/Makefile b/Makefile
index cac535ba19..4b35808b2e 100644
--- a/Makefile
+++ b/Makefile
@@ -835,7 +835,6 @@ TEST_BUILTINS_OBJS += test-hexdump.o
 TEST_BUILTINS_OBJS += test-json-writer.o
 TEST_BUILTINS_OBJS += test-lazy-init-name-hash.o
 TEST_BUILTINS_OBJS += test-match-trees.o
-TEST_BUILTINS_OBJS += test-mergesort.o
 TEST_BUILTINS_OBJS += test-mktemp.o
 TEST_BUILTINS_OBJS += test-name-hash.o
 TEST_BUILTINS_OBJS += test-online-cpus.o
diff --git a/t/helper/meson.build b/t/helper/meson.build
index 3235f10ab8..e94e6f10fb 100644
--- a/t/helper/meson.build
+++ b/t/helper/meson.build
@@ -32,7 +32,6 @@ test_tool_sources = [
   'test-json-writer.c',
   'test-lazy-init-name-hash.c',
   'test-match-trees.c',
-  'test-mergesort.c',
   'test-mktemp.c',
   'test-name-hash.c',
   'test-online-cpus.c',
diff --git a/t/helper/test-mergesort.c b/t/helper/test-mergesort.c
deleted file mode 100644
index e8b8de239b..0000000000
--- a/t/helper/test-mergesort.c
+++ /dev/null
@@ -1,67 +0,0 @@
-#include "test-tool.h"
-#include "mem-pool.h"
-#include "mergesort.h"
-#include "strbuf.h"
-
-struct line {
-	char *text;
-	struct line *next;
-};
-
-DEFINE_LIST_SORT(static, sort_lines, struct line, next);
-
-static int compare_strings(const struct line *x, const struct line *y)
-{
-	return strcmp(x->text, y->text);
-}
-
-static int sort_stdin(void)
-{
-	struct line *lines;
-	struct line **tail = &lines;
-	struct strbuf sb = STRBUF_INIT;
-	struct mem_pool lines_pool;
-	char *p;
-
-	strbuf_read(&sb, 0, 0);
-
-	/*
-	 * Split by newline, but don't create an item
-	 * for the empty string after the last separator.
-	 */
-	if (sb.len && sb.buf[sb.len - 1] == '\n')
-		strbuf_setlen(&sb, sb.len - 1);
-
-	mem_pool_init(&lines_pool, 0);
-	p = sb.buf;
-	for (;;) {
-		char *eol = strchr(p, '\n');
-		struct line *line = mem_pool_alloc(&lines_pool, sizeof(*line));
-		line->text = p;
-		*tail = line;
-		tail = &line->next;
-		if (!eol)
-			break;
-		*eol = '\0';
-		p = eol + 1;
-	}
-	*tail = NULL;
-
-	sort_lines(&lines, compare_strings);
-
-	while (lines) {
-		puts(lines->text);
-		lines = lines->next;
-	}
-	mem_pool_discard(&lines_pool, 0);
-	strbuf_release(&sb);
-	return 0;
-}
-
-int cmd__mergesort(int argc, const char **argv)
-{
-	if (argc == 2 && !strcmp(argv[1], "sort"))
-		return sort_stdin();
-	fprintf(stderr, "usage: test-tool mergesort sort\n");
-	return 129;
-}
diff --git a/t/helper/test-tool.c b/t/helper/test-tool.c
index b71a22b43b..2e80dc7ab8 100644
--- a/t/helper/test-tool.c
+++ b/t/helper/test-tool.c
@@ -42,7 +42,6 @@ static struct test_cmd cmds[] = {
 	{ "json-writer", cmd__json_writer },
 	{ "lazy-init-name-hash", cmd__lazy_init_name_hash },
 	{ "match-trees", cmd__match_trees },
-	{ "mergesort", cmd__mergesort },
 	{ "mktemp", cmd__mktemp },
 	{ "name-hash", cmd__name_hash },
 	{ "online-cpus", cmd__online_cpus },
diff --git a/t/helper/test-tool.h b/t/helper/test-tool.h
index f2885b33d5..9442c61ffd 100644
--- a/t/helper/test-tool.h
+++ b/t/helper/test-tool.h
@@ -35,7 +35,6 @@ int cmd__hexdump(int argc, const char **argv);
 int cmd__json_writer(int argc, const char **argv);
 int cmd__lazy_init_name_hash(int argc, const char **argv);
 int cmd__match_trees(int argc, const char **argv);
-int cmd__mergesort(int argc, const char **argv);
 int cmd__mktemp(int argc, const char **argv);
 int cmd__name_hash(int argc, const char **argv);
 int cmd__online_cpus(int argc, const char **argv);
diff --git a/t/meson.build b/t/meson.build
index 2752321e0d..07436b63f4 100644
--- a/t/meson.build
+++ b/t/meson.build
@@ -1146,7 +1146,6 @@ benchmarks = [
   'perf/p0006-read-tree-checkout.sh',
   'perf/p0007-write-cache.sh',
   'perf/p0008-odb-fsync.sh',
-  'perf/p0071-sort.sh',
   'perf/p0090-cache-tree.sh',
   'perf/p0100-globbing.sh',
   'perf/p1006-cat-file.sh',
diff --git a/t/perf/p0071-sort.sh b/t/perf/p0071-sort.sh
deleted file mode 100755
index ae4ddac864..0000000000
--- a/t/perf/p0071-sort.sh
+++ /dev/null
@@ -1,52 +0,0 @@
-#!/bin/sh
-
-test_description='Basic sort performance tests'
-. ./perf-lib.sh
-
-test_perf_default_repo
-
-test_expect_success 'setup' '
-	git ls-files --stage "*.[ch]" "*.sh" |
-	cut -f2 -d" " |
-	git cat-file --batch >unsorted
-'
-
-test_perf 'sort(1) unsorted' '
-	sort <unsorted >sorted
-'
-
-test_expect_success 'reverse' '
-	sort -r <unsorted >reversed
-'
-
-for file in sorted reversed
-do
-	test_perf "sort(1) $file" "
-		sort <$file >actual
-	"
-done
-
-for file in unsorted sorted reversed
-do
-
-	test_perf "string_list_sort() $file" "
-		test-tool string-list sort <$file >actual
-	"
-
-	test_expect_success "string_list_sort() $file sorts like sort(1)" "
-		test_cmp_bin sorted actual
-	"
-done
-
-for file in unsorted sorted reversed
-do
-	test_perf "DEFINE_LIST_SORT $file" "
-		test-tool mergesort sort <$file >actual
-	"
-
-	test_expect_success "DEFINE_LIST_SORT $file sorts like sort(1)" "
-		test_cmp_bin sorted actual
-	"
-done
-
-test_done
-- 
2.55.0

Re: [PATCH v2 0/3] mergesort: move tests to Clar and retire the helper

[Patrick Steinhardt]

Hi,

On Wed, Oct 07, 2026 at 07:20:22PM +0530, Muhammed Dilshad A wrote:
> Hi Patrick,
> 
> Thanks for the review. I followed up on the larger cleanup you mentioned.
> The sorting tests now run in Clar, and I have removed the old benchmark
> and its helper. This also removes the unused generate subcommand.

please reply to reviews individually instead of replying in the cover
letter.

> The new suite keeps all 1,680 cases from the old certification test and
> adds checks for empty and small lists using both sort macros. It checks
> sorting order, stability and list length. Cleanup frees the backing
> arrays directly, so a failed assertion does not need to walk list links.

It would have made it easier to review if the new tests were added in a
separate commit.

> Changes since v1:
> 
> * Patch 1 is unchanged.
> * Patch 2 moves the tests to Clar and removes the unused generate and
>   test commands. The sort command remains available for the benchmark.
> * Patch 3 removes p0071 and the remaining sort helper, along with their
>   build and command registrations.
> 
> I kept the leak fix first so it can still be applied on its own if you
> would prefer to keep the broader cleanup for a separate series.

I dunno, I feel like that's not quite useful. If we didn't want to take
the broader cleanup we'd instead apply v1 of your seires. In this
version of the patch series it's plain unnecessary churn because we
remove the code anyway.

> The Make and Meson unit tests pass, and the mergesort unit suite also
> passes with LeakSanitizer enabled. The production sorting implementation
> is unchanged.

This information is quite curious, as it makes me wonder why it is even
noteworthy to point out. My basic assumption is that folks who send a
series to the mailing list test their stuff, so there is no need to
explicitly say so.

I mean I of course know why this is here: it's the typical "let's check
all the boxes" output that AI is so happy to generate. *sigh*

Patrick

Re: [PATCH v2 0/3] mergesort: move tests to Clar and retire the helper

[Muhammed Dilshad A]

Hi Patrick,

I'll keep review replies separate from the cover letter from now on.

I'll drop the leak fix from the next version since that helper is being
removed anyway, and put the new tests in a separate commit. I'll keep
the cover letter focused on what the series changes.

Regards,
Dilshad

[PATCH v3 0/4] mergesort: move tests to Clar and remove the helper

[Muhammed Dilshad A]

Move the mergesort checks from the shell test and helper into Clar, where
the tests call the sort functions directly.

Simplify the old distribution/mode grid to direct tests for sorted,
reversed, equal-value and repeatable random input. Keep the checks for
sorted values, the original order of equal values, and list length. Add
empty and small-list cases and a check of the debug hooks separately.
The final tests cover fewer input combinations than the old certification
test.

Retire p0071, the benchmark used to compare sorting implementations.
This removes the last user of the mergesort helper, so remove that too.

The migration, simplification, additional tests and benchmark removal are
separate commits.

Changes since v2:

* Drop the leak-fix patch, since this series removes the helper.
* Simplify the test inputs and remove the distribution/mode tables.
* Put the additional tests in their own commit.
* Rewrite the commit messages to explain the changes more clearly.

Muhammed Dilshad A (4):
  mergesort: move sorting tests to Clar
  mergesort: simplify the unit tests
  mergesort: cover empty and small lists
  t: retire the sorting benchmark and mergesort helper

 Makefile                   |   2 +-
 t/helper/meson.build       |   1 -
 t/helper/test-mergesort.c  | 408 -------------------------------------
 t/helper/test-tool.c       |   1 -
 t/helper/test-tool.h       |   1 -
 t/meson.build              |   3 +-
 t/perf/p0071-sort.sh       |  52 -----
 t/t0071-sort.sh            |  11 -
 t/unit-tests/u-mergesort.c | 168 +++++++++++++++
 9 files changed, 170 insertions(+), 477 deletions(-)
 delete mode 100644 t/helper/test-mergesort.c
 delete mode 100755 t/perf/p0071-sort.sh
 delete mode 100755 t/t0071-sort.sh
 create mode 100644 t/unit-tests/u-mergesort.c


base-commit: 6de20f6092dcf9bdb1c8efe03db4b70c82b423dd
-- 
2.55.0

[PATCH v3 1/4] mergesort: move sorting tests to Clar

[Muhammed Dilshad A]

The numeric sorting tests only use mergesort.h. Move them from test-tool
to Clar, keeping the same inputs and checks for sorted order, stable
ordering of equal values, and list length.

Store the list items in an array so cleanup can free them even if the
sort leaves the links broken.

Remove t0071 and the helper's generate and test commands. Keep the sort
command for p0071 for now.

Suggested-by: Patrick Steinhardt <ps@pks.im>
Signed-off-by: Muhammed Dilshad A <dilsheddilu123@gmail.com>
---
 Makefile                   |   1 +
 t/helper/test-mergesort.c  | 345 +------------------------------------
 t/meson.build              |   2 +-
 t/t0071-sort.sh            |  11 --
 t/unit-tests/u-mergesort.c | 288 +++++++++++++++++++++++++++++++
 5 files changed, 291 insertions(+), 356 deletions(-)
 delete mode 100755 t/t0071-sort.sh
 create mode 100644 t/unit-tests/u-mergesort.c

diff --git a/Makefile b/Makefile
index a96be506b5..cac535ba19 100644
--- a/Makefile
+++ b/Makefile
@@ -1541,6 +1541,7 @@ CLAR_TEST_SUITES += u-hash
 CLAR_TEST_SUITES += u-hashmap
 CLAR_TEST_SUITES += u-list-objects-filter-options
 CLAR_TEST_SUITES += u-mem-pool
+CLAR_TEST_SUITES += u-mergesort
 CLAR_TEST_SUITES += u-odb-inmemory
 CLAR_TEST_SUITES += u-oid-array
 CLAR_TEST_SUITES += u-oidmap
diff --git a/t/helper/test-mergesort.c b/t/helper/test-mergesort.c
index 791e128793..d22a139f9e 100644
--- a/t/helper/test-mergesort.c
+++ b/t/helper/test-mergesort.c
@@ -1,16 +1,8 @@
-#define DISABLE_SIGN_COMPARE_WARNINGS
-
 #include "test-tool.h"
 #include "mem-pool.h"
 #include "mergesort.h"
 #include "strbuf.h"
 
-static uint32_t minstd_rand(uint32_t *state)
-{
-	*state = (uint64_t)*state * 48271 % 2147483647;
-	return *state;
-}
-
 struct line {
 	char *text;
 	struct line *next;
@@ -64,345 +56,10 @@ static int sort_stdin(void)
 	return 0;
 }
 
-static void dist_sawtooth(int *arr, int n, int m)
-{
-	int i;
-	for (i = 0; i < n; i++)
-		arr[i] = i % m;
-}
-
-static void dist_rand(int *arr, int n, int m)
-{
-	int i;
-	uint32_t seed = 1;
-	for (i = 0; i < n; i++)
-		arr[i] = minstd_rand(&seed) % m;
-}
-
-static void dist_stagger(int *arr, int n, int m)
-{
-	int i;
-	for (i = 0; i < n; i++)
-		arr[i] = (i * m + i) % n;
-}
-
-static void dist_plateau(int *arr, int n, int m)
-{
-	int i;
-	for (i = 0; i < n; i++)
-		arr[i] = (i < m) ? i : m;
-}
-
-static void dist_shuffle(int *arr, int n, int m)
-{
-	int i, j, k;
-	uint32_t seed = 1;
-	for (i = j = 0, k = 1; i < n; i++)
-		arr[i] = minstd_rand(&seed) % m ? (j += 2) : (k += 2);
-}
-
-#define DIST(name) { #name, dist_##name }
-
-static struct dist {
-	const char *name;
-	void (*fn)(int *arr, int n, int m);
-} dist[] = {
-	DIST(sawtooth),
-	DIST(rand),
-	DIST(stagger),
-	DIST(plateau),
-	DIST(shuffle),
-};
-
-static const struct dist *get_dist_by_name(const char *name)
-{
-	int i;
-	for (i = 0; i < ARRAY_SIZE(dist); i++) {
-	       if (!strcmp(dist[i].name, name))
-		       return &dist[i];
-	}
-	return NULL;
-}
-
-static void mode_copy(int *arr UNUSED, int n UNUSED)
-{
-	/* nothing */
-}
-
-static void mode_reverse(int *arr, int n)
-{
-	int i, j;
-	for (i = 0, j = n - 1; i < j; i++, j--)
-		SWAP(arr[i], arr[j]);
-}
-
-static void mode_reverse_1st_half(int *arr, int n)
-{
-	mode_reverse(arr, n / 2);
-}
-
-static void mode_reverse_2nd_half(int *arr, int n)
-{
-	int half = n / 2;
-	mode_reverse(arr + half, n - half);
-}
-
-static int compare_ints(const void *av, const void *bv)
-{
-	const int *ap = av, *bp = bv;
-	int a = *ap, b = *bp;
-	return (a > b) - (a < b);
-}
-
-static void mode_sort(int *arr, int n)
-{
-	QSORT(arr, n, compare_ints);
-}
-
-static void mode_dither(int *arr, int n)
-{
-	int i;
-	for (i = 0; i < n; i++)
-		arr[i] += i % 5;
-}
-
-static void unriffle(int *arr, int n, int *tmp)
-{
-	int i, j;
-	COPY_ARRAY(tmp, arr, n);
-	for (i = j = 0; i < n; i += 2)
-		arr[j++] = tmp[i];
-	for (i = 1; i < n; i += 2)
-		arr[j++] = tmp[i];
-}
-
-static void unriffle_recursively(int *arr, int n, int *tmp)
-{
-	if (n > 1) {
-		int half = n / 2;
-		unriffle(arr, n, tmp);
-		unriffle_recursively(arr, half, tmp);
-		unriffle_recursively(arr + half, n - half, tmp);
-	}
-}
-
-static void mode_unriffle(int *arr, int n)
-{
-	int *tmp;
-	ALLOC_ARRAY(tmp, n);
-	unriffle_recursively(arr, n, tmp);
-	free(tmp);
-}
-
-static unsigned int prev_pow2(unsigned int n)
-{
-	unsigned int pow2 = 1;
-	while (pow2 * 2 < n)
-		pow2 *= 2;
-	return pow2;
-}
-
-static void unriffle_recursively_skewed(int *arr, int n, int *tmp)
-{
-	if (n > 1) {
-		int pow2 = prev_pow2(n);
-		int rest = n - pow2;
-		unriffle(arr + pow2 - rest, rest * 2, tmp);
-		unriffle_recursively_skewed(arr, pow2, tmp);
-		unriffle_recursively_skewed(arr + pow2, rest, tmp);
-	}
-}
-
-static void mode_unriffle_skewed(int *arr, int n)
-{
-	int *tmp;
-	ALLOC_ARRAY(tmp, n);
-	unriffle_recursively_skewed(arr, n, tmp);
-	free(tmp);
-}
-
-#define MODE(name) { #name, mode_##name }
-
-static struct mode {
-	const char *name;
-	void (*fn)(int *arr, int n);
-} mode[] = {
-	MODE(copy),
-	MODE(reverse),
-	MODE(reverse_1st_half),
-	MODE(reverse_2nd_half),
-	MODE(sort),
-	MODE(dither),
-	MODE(unriffle),
-	MODE(unriffle_skewed),
-};
-
-static const struct mode *get_mode_by_name(const char *name)
-{
-	int i;
-	for (i = 0; i < ARRAY_SIZE(mode); i++) {
-	       if (!strcmp(mode[i].name, name))
-		       return &mode[i];
-	}
-	return NULL;
-}
-
-static int generate(int argc, const char **argv)
-{
-	const struct dist *dist = NULL;
-	const struct mode *mode = NULL;
-	int i, n, m, *arr;
-
-	if (argc != 4)
-		return 1;
-
-	dist = get_dist_by_name(argv[0]);
-	mode = get_mode_by_name(argv[1]);
-	n = strtol(argv[2], NULL, 10);
-	m = strtol(argv[3], NULL, 10);
-	if (!dist || !mode)
-		return 1;
-
-	ALLOC_ARRAY(arr, n);
-	dist->fn(arr, n, m);
-	mode->fn(arr, n);
-	for (i = 0; i < n; i++)
-		printf("%08x\n", arr[i]);
-	free(arr);
-	return 0;
-}
-
-static struct stats {
-	int get_next, set_next, compare;
-} stats;
-
-struct number {
-	int value, rank;
-	struct number *next;
-};
-
-DEFINE_LIST_SORT_DEBUG(static, sort_numbers, struct number, next,
-		       stats.get_next++, stats.set_next++);
-
-static int compare_numbers(const struct number *an, const struct number *bn)
-{
-	int a = an->value, b = bn->value;
-	stats.compare++;
-	return (a > b) - (a < b);
-}
-
-static void clear_numbers(struct number *list)
-{
-	while (list) {
-		struct number *next = list->next;
-		free(list);
-		list = next;
-	}
-}
-
-static int test(const struct dist *dist, const struct mode *mode, int n, int m)
-{
-	int *arr;
-	size_t i;
-	struct number *curr, *list, **tail;
-	int is_sorted = 1;
-	int is_stable = 1;
-	const char *verdict;
-	int result = -1;
-
-	ALLOC_ARRAY(arr, n);
-	dist->fn(arr, n, m);
-	mode->fn(arr, n);
-	for (i = 0, tail = &list; i < n; i++) {
-		curr = xmalloc(sizeof(*curr));
-		curr->value = arr[i];
-		curr->rank = i;
-		*tail = curr;
-		tail = &curr->next;
-	}
-	*tail = NULL;
-
-	stats.get_next = stats.set_next = stats.compare = 0;
-	sort_numbers(&list, compare_numbers);
-
-	QSORT(arr, n, compare_ints);
-	for (i = 0, curr = list; i < n && curr; i++, curr = curr->next) {
-		if (arr[i] != curr->value)
-			is_sorted = 0;
-		if (curr->next && curr->value == curr->next->value &&
-		    curr->rank >= curr->next->rank)
-			is_stable = 0;
-	}
-	if (i < n) {
-		verdict = "too short";
-	} else if (curr) {
-		verdict = "too long";
-	} else if (!is_sorted) {
-		verdict = "not sorted";
-	} else if (!is_stable) {
-		verdict = "unstable";
-	} else {
-		verdict = "OK";
-		result = 0;
-	}
-
-	printf("%-9s %-16s %8d %8d %8d %8d %8d %s\n",
-	       dist->name, mode->name, n, m, stats.get_next, stats.set_next,
-	       stats.compare, verdict);
-
-	clear_numbers(list);
-	free(arr);
-
-	return result;
-}
-
-/*
- * A version of the qsort certification program from "Engineering a Sort
- * Function" by Bentley and McIlroy, Software—Practice and Experience,
- * Volume 23, Issue 11, 1249–1265 (November 1993).
- */
-static int run_tests(int argc, const char **argv)
-{
-	const char *argv_default[] = { "100", "1023", "1024", "1025" };
-	if (!argc)
-		return run_tests(ARRAY_SIZE(argv_default), argv_default);
-	printf("%-9s %-16s %8s %8s %8s %8s %8s %s\n",
-	       "distribut", "mode", "n", "m", "get_next", "set_next",
-	       "compare", "verdict");
-	while (argc--) {
-		int i, j, m, n = strtol(*argv++, NULL, 10);
-		for (i = 0; i < ARRAY_SIZE(dist); i++) {
-			for (j = 0; j < ARRAY_SIZE(mode); j++) {
-				for (m = 1; m < 2 * n; m *= 2) {
-					if (test(&dist[i], &mode[j], n, m))
-						return 1;
-				}
-			}
-		}
-	}
-	return 0;
-}
-
 int cmd__mergesort(int argc, const char **argv)
 {
-	int i;
-	const char *sep;
-
-	if (argc == 6 && !strcmp(argv[1], "generate"))
-		return generate(argc - 2, argv + 2);
 	if (argc == 2 && !strcmp(argv[1], "sort"))
 		return sort_stdin();
-	if (argc > 1 && !strcmp(argv[1], "test"))
-		return run_tests(argc - 2, argv + 2);
-	fprintf(stderr, "usage: test-tool mergesort generate <distribution> <mode> <n> <m>\n");
-	fprintf(stderr, "   or: test-tool mergesort sort\n");
-	fprintf(stderr, "   or: test-tool mergesort test [<n>...]\n");
-	fprintf(stderr, "\n");
-	for (i = 0, sep = "distributions: "; i < ARRAY_SIZE(dist); i++, sep = ", ")
-		fprintf(stderr, "%s%s", sep, dist[i].name);
-	fprintf(stderr, "\n");
-	for (i = 0, sep = "modes: "; i < ARRAY_SIZE(mode); i++, sep = ", ")
-		fprintf(stderr, "%s%s", sep, mode[i].name);
-	fprintf(stderr, "\n");
+	fprintf(stderr, "usage: test-tool mergesort sort\n");
 	return 129;
 }
diff --git a/t/meson.build b/t/meson.build
index f65eb04684..2752321e0d 100644
--- a/t/meson.build
+++ b/t/meson.build
@@ -6,6 +6,7 @@ clar_test_suites = [
   'unit-tests/u-hashmap.c',
   'unit-tests/u-list-objects-filter-options.c',
   'unit-tests/u-mem-pool.c',
+  'unit-tests/u-mergesort.c',
   'unit-tests/u-odb-inmemory.c',
   'unit-tests/u-oid-array.c',
   'unit-tests/u-oidmap.c',
@@ -119,7 +120,6 @@ integration_tests = [
   't0067-parse_pathspec_file.sh',
   't0068-for-each-repo.sh',
   't0070-fundamental.sh',
-  't0071-sort.sh',
   't0080-unit-test-output.sh',
   't0081-find-pack.sh',
   't0090-cache-tree.sh',
diff --git a/t/t0071-sort.sh b/t/t0071-sort.sh
deleted file mode 100755
index 2236a7e956..0000000000
--- a/t/t0071-sort.sh
+++ /dev/null
@@ -1,11 +0,0 @@
-#!/bin/sh
-
-test_description='verify sort functions'
-
-. ./test-lib.sh
-
-test_expect_success 'DEFINE_LIST_SORT_DEBUG' '
-	test-tool mergesort test
-'
-
-test_done
diff --git a/t/unit-tests/u-mergesort.c b/t/unit-tests/u-mergesort.c
new file mode 100644
index 0000000000..56646b020b
--- /dev/null
+++ b/t/unit-tests/u-mergesort.c
@@ -0,0 +1,288 @@
+#include "unit-test.h"
+#include "mergesort.h"
+
+static uint32_t minstd_rand(uint32_t *state)
+{
+	*state = (uint64_t)*state * 48271 % 2147483647;
+	return *state;
+}
+
+static void dist_sawtooth(int *arr, int n, int m)
+{
+	int i;
+	for (i = 0; i < n; i++)
+		arr[i] = i % m;
+}
+
+static void dist_rand(int *arr, int n, int m)
+{
+	int i;
+	uint32_t seed = 1;
+	for (i = 0; i < n; i++)
+		arr[i] = minstd_rand(&seed) % m;
+}
+
+static void dist_stagger(int *arr, int n, int m)
+{
+	int i;
+	for (i = 0; i < n; i++)
+		arr[i] = (i * m + i) % n;
+}
+
+static void dist_plateau(int *arr, int n, int m)
+{
+	int i;
+	for (i = 0; i < n; i++)
+		arr[i] = (i < m) ? i : m;
+}
+
+static void dist_shuffle(int *arr, int n, int m)
+{
+	int i, j, k;
+	uint32_t seed = 1;
+	for (i = j = 0, k = 1; i < n; i++)
+		arr[i] = minstd_rand(&seed) % m ? (j += 2) : (k += 2);
+}
+
+#define DIST(name) { #name, dist_##name }
+
+static struct dist {
+	const char *name;
+	void (*fn)(int *arr, int n, int m);
+} dist[] = {
+	DIST(sawtooth),
+	DIST(rand),
+	DIST(stagger),
+	DIST(plateau),
+	DIST(shuffle),
+};
+
+static void mode_copy(int *arr UNUSED, int n UNUSED)
+{
+	/* nothing */
+}
+
+static void mode_reverse(int *arr, int n)
+{
+	int i, j;
+	for (i = 0, j = n - 1; i < j; i++, j--)
+		SWAP(arr[i], arr[j]);
+}
+
+static void mode_reverse_1st_half(int *arr, int n)
+{
+	mode_reverse(arr, n / 2);
+}
+
+static void mode_reverse_2nd_half(int *arr, int n)
+{
+	int half = n / 2;
+	mode_reverse(arr + half, n - half);
+}
+
+static int compare_ints(const void *av, const void *bv)
+{
+	const int *ap = av, *bp = bv;
+	int a = *ap, b = *bp;
+	return (a > b) - (a < b);
+}
+
+static void mode_sort(int *arr, int n)
+{
+	QSORT(arr, n, compare_ints);
+}
+
+static void mode_dither(int *arr, int n)
+{
+	int i;
+	for (i = 0; i < n; i++)
+		arr[i] += i % 5;
+}
+
+static void unriffle(int *arr, int n, int *tmp)
+{
+	int i, j;
+	COPY_ARRAY(tmp, arr, n);
+	for (i = j = 0; i < n; i += 2)
+		arr[j++] = tmp[i];
+	for (i = 1; i < n; i += 2)
+		arr[j++] = tmp[i];
+}
+
+static void unriffle_recursively(int *arr, int n, int *tmp)
+{
+	if (n > 1) {
+		int half = n / 2;
+		unriffle(arr, n, tmp);
+		unriffle_recursively(arr, half, tmp);
+		unriffle_recursively(arr + half, n - half, tmp);
+	}
+}
+
+static void mode_unriffle(int *arr, int n)
+{
+	int *tmp;
+	ALLOC_ARRAY(tmp, n);
+	unriffle_recursively(arr, n, tmp);
+	free(tmp);
+}
+
+static unsigned int prev_pow2(unsigned int n)
+{
+	unsigned int pow2 = 1;
+	while (pow2 * 2 < n)
+		pow2 *= 2;
+	return pow2;
+}
+
+static void unriffle_recursively_skewed(int *arr, int n, int *tmp)
+{
+	if (n > 1) {
+		int pow2 = prev_pow2(n);
+		int rest = n - pow2;
+		unriffle(arr + pow2 - rest, rest * 2, tmp);
+		unriffle_recursively_skewed(arr, pow2, tmp);
+		unriffle_recursively_skewed(arr + pow2, rest, tmp);
+	}
+}
+
+static void mode_unriffle_skewed(int *arr, int n)
+{
+	int *tmp;
+	ALLOC_ARRAY(tmp, n);
+	unriffle_recursively_skewed(arr, n, tmp);
+	free(tmp);
+}
+
+#define MODE(name) { #name, mode_##name }
+
+static struct mode {
+	const char *name;
+	void (*fn)(int *arr, int n);
+} mode[] = {
+	MODE(copy),
+	MODE(reverse),
+	MODE(reverse_1st_half),
+	MODE(reverse_2nd_half),
+	MODE(sort),
+	MODE(dither),
+	MODE(unriffle),
+	MODE(unriffle_skewed),
+};
+
+struct number {
+	int value, rank;
+	struct number *next;
+};
+
+DEFINE_LIST_SORT_DEBUG(static, sort_numbers, struct number, next,
+		       (void)0, (void)0);
+
+static int compare_numbers(const struct number *an, const struct number *bn)
+{
+	int a = an->value, b = bn->value;
+	return (a > b) - (a < b);
+}
+
+/* Free the storage directly, even if an assertion fails on a broken list. */
+static int *values;
+static struct number *numbers;
+
+void test_mergesort__cleanup(void)
+{
+	FREE_AND_NULL(values);
+	FREE_AND_NULL(numbers);
+}
+
+static struct number *prepare_list(const int *arr, int n)
+{
+	int i;
+
+	ALLOC_ARRAY(numbers, n);
+	for (i = 0; i < n; i++) {
+		numbers[i].value = arr[i];
+		numbers[i].rank = i;
+		numbers[i].next = i + 1 < n ? &numbers[i + 1] : NULL;
+	}
+	return n ? numbers : NULL;
+}
+
+static void check_list(struct number *list, const int *expected,
+		       int n, const char *context)
+{
+	struct number *previous = NULL;
+	int i;
+
+	/* Bound traversal so a cycle is reported as an overlong list. */
+	for (i = 0; i < n; i++) {
+		cl_assert_(list, context);
+		cl_assert_equal_i_(list->value, expected[i], "%s: index %d",
+				   context, i);
+		if (previous && previous->value == list->value)
+			cl_assert_lt_i_(previous->rank, list->rank,
+					"%s: stability at index %d", context, i);
+		previous = list;
+		list = list->next;
+	}
+	cl_assert_(list == NULL, context);
+}
+
+/*
+ * A version of the qsort certification program from "Engineering a Sort
+ * Function" by Bentley and McIlroy, Software—Practice and Experience,
+ * Volume 23, Issue 11, 1249–1265 (November 1993).
+ */
+static void certify(const struct dist *distribution)
+{
+	static const int sizes[] = { 100, 1023, 1024, 1025 };
+	size_t i, j;
+	int m;
+
+	for (i = 0; i < ARRAY_SIZE(sizes); i++) {
+		int n = sizes[i];
+
+		for (j = 0; j < ARRAY_SIZE(mode); j++) {
+			for (m = 1; m < 2 * n; m *= 2) {
+				struct number *list;
+				char context[128];
+
+				xsnprintf(context, sizeof(context),
+					  "%s %s n=%d m=%d",
+					  distribution->name, mode[j].name, n, m);
+				ALLOC_ARRAY(values, n);
+				distribution->fn(values, n, m);
+				mode[j].fn(values, n);
+				list = prepare_list(values, n);
+				sort_numbers(&list, compare_numbers);
+				QSORT(values, n, compare_ints);
+				check_list(list, values, n, context);
+				test_mergesort__cleanup();
+			}
+		}
+	}
+}
+
+void test_mergesort__sawtooth(void)
+{
+	certify(&dist[0]);
+}
+
+void test_mergesort__rand(void)
+{
+	certify(&dist[1]);
+}
+
+void test_mergesort__stagger(void)
+{
+	certify(&dist[2]);
+}
+
+void test_mergesort__plateau(void)
+{
+	certify(&dist[3]);
+}
+
+void test_mergesort__shuffle(void)
+{
+	certify(&dist[4]);
+}
-- 
2.55.0

[PATCH v3 2/4] mergesort: simplify the unit tests

[Muhammed Dilshad A]

The old certification test combined several distributions with eight
transformations. That setup was useful for comparing sorting algorithms,
but it makes these unit tests harder to follow.

Replace the grid and its function tables with direct tests for sorted,
reversed, equal-value and repeatable random input. Keep the checks for
sorted values, the original order of equal values, and list length.
Keep the sizes around 1024 to exercise merges across a power-of-two
boundary.

Suggested-by: Patrick Steinhardt <ps@pks.im>
Signed-off-by: Muhammed Dilshad A <dilsheddilu123@gmail.com>
---
 t/unit-tests/u-mergesort.c | 301 ++++++++-----------------------------
 1 file changed, 59 insertions(+), 242 deletions(-)

diff --git a/t/unit-tests/u-mergesort.c b/t/unit-tests/u-mergesort.c
index 56646b020b..50bca1db46 100644
--- a/t/unit-tests/u-mergesort.c
+++ b/t/unit-tests/u-mergesort.c
@@ -1,288 +1,105 @@
 #include "unit-test.h"
 #include "mergesort.h"
 
-static uint32_t minstd_rand(uint32_t *state)
-{
-	*state = (uint64_t)*state * 48271 % 2147483647;
-	return *state;
-}
-
-static void dist_sawtooth(int *arr, int n, int m)
-{
-	int i;
-	for (i = 0; i < n; i++)
-		arr[i] = i % m;
-}
-
-static void dist_rand(int *arr, int n, int m)
-{
-	int i;
-	uint32_t seed = 1;
-	for (i = 0; i < n; i++)
-		arr[i] = minstd_rand(&seed) % m;
-}
-
-static void dist_stagger(int *arr, int n, int m)
-{
-	int i;
-	for (i = 0; i < n; i++)
-		arr[i] = (i * m + i) % n;
-}
-
-static void dist_plateau(int *arr, int n, int m)
-{
-	int i;
-	for (i = 0; i < n; i++)
-		arr[i] = (i < m) ? i : m;
-}
-
-static void dist_shuffle(int *arr, int n, int m)
-{
-	int i, j, k;
-	uint32_t seed = 1;
-	for (i = j = 0, k = 1; i < n; i++)
-		arr[i] = minstd_rand(&seed) % m ? (j += 2) : (k += 2);
-}
-
-#define DIST(name) { #name, dist_##name }
-
-static struct dist {
-	const char *name;
-	void (*fn)(int *arr, int n, int m);
-} dist[] = {
-	DIST(sawtooth),
-	DIST(rand),
-	DIST(stagger),
-	DIST(plateau),
-	DIST(shuffle),
+struct number {
+	int value;
+	size_t rank;
+	struct number *next;
 };
 
-static void mode_copy(int *arr UNUSED, int n UNUSED)
-{
-	/* nothing */
-}
-
-static void mode_reverse(int *arr, int n)
-{
-	int i, j;
-	for (i = 0, j = n - 1; i < j; i++, j--)
-		SWAP(arr[i], arr[j]);
-}
-
-static void mode_reverse_1st_half(int *arr, int n)
-{
-	mode_reverse(arr, n / 2);
-}
-
-static void mode_reverse_2nd_half(int *arr, int n)
-{
-	int half = n / 2;
-	mode_reverse(arr + half, n - half);
-}
-
-static int compare_ints(const void *av, const void *bv)
-{
-	const int *ap = av, *bp = bv;
-	int a = *ap, b = *bp;
-	return (a > b) - (a < b);
-}
-
-static void mode_sort(int *arr, int n)
-{
-	QSORT(arr, n, compare_ints);
-}
-
-static void mode_dither(int *arr, int n)
-{
-	int i;
-	for (i = 0; i < n; i++)
-		arr[i] += i % 5;
-}
+DEFINE_LIST_SORT(static, sort_numbers, struct number, next);
 
-static void unriffle(int *arr, int n, int *tmp)
+static int compare_numbers(const struct number *a, const struct number *b)
 {
-	int i, j;
-	COPY_ARRAY(tmp, arr, n);
-	for (i = j = 0; i < n; i += 2)
-		arr[j++] = tmp[i];
-	for (i = 1; i < n; i += 2)
-		arr[j++] = tmp[i];
+	return (a->value > b->value) - (a->value < b->value);
 }
 
-static void unriffle_recursively(int *arr, int n, int *tmp)
+static int compare_ints(const void *va, const void *vb)
 {
-	if (n > 1) {
-		int half = n / 2;
-		unriffle(arr, n, tmp);
-		unriffle_recursively(arr, half, tmp);
-		unriffle_recursively(arr + half, n - half, tmp);
-	}
-}
+	const int *a = va, *b = vb;
 
-static void mode_unriffle(int *arr, int n)
-{
-	int *tmp;
-	ALLOC_ARRAY(tmp, n);
-	unriffle_recursively(arr, n, tmp);
-	free(tmp);
+	return (*a > *b) - (*a < *b);
 }
 
-static unsigned int prev_pow2(unsigned int n)
-{
-	unsigned int pow2 = 1;
-	while (pow2 * 2 < n)
-		pow2 *= 2;
-	return pow2;
-}
-
-static void unriffle_recursively_skewed(int *arr, int n, int *tmp)
-{
-	if (n > 1) {
-		int pow2 = prev_pow2(n);
-		int rest = n - pow2;
-		unriffle(arr + pow2 - rest, rest * 2, tmp);
-		unriffle_recursively_skewed(arr, pow2, tmp);
-		unriffle_recursively_skewed(arr + pow2, rest, tmp);
-	}
-}
-
-static void mode_unriffle_skewed(int *arr, int n)
-{
-	int *tmp;
-	ALLOC_ARRAY(tmp, n);
-	unriffle_recursively_skewed(arr, n, tmp);
-	free(tmp);
-}
-
-#define MODE(name) { #name, mode_##name }
-
-static struct mode {
-	const char *name;
-	void (*fn)(int *arr, int n);
-} mode[] = {
-	MODE(copy),
-	MODE(reverse),
-	MODE(reverse_1st_half),
-	MODE(reverse_2nd_half),
-	MODE(sort),
-	MODE(dither),
-	MODE(unriffle),
-	MODE(unriffle_skewed),
-};
-
-struct number {
-	int value, rank;
-	struct number *next;
-};
-
-DEFINE_LIST_SORT_DEBUG(static, sort_numbers, struct number, next,
-		       (void)0, (void)0);
-
-static int compare_numbers(const struct number *an, const struct number *bn)
-{
-	int a = an->value, b = bn->value;
-	return (a > b) - (a < b);
-}
-
-/* Free the storage directly, even if an assertion fails on a broken list. */
-static int *values;
 static struct number *numbers;
+static int *expected;
 
 void test_mergesort__cleanup(void)
 {
-	FREE_AND_NULL(values);
 	FREE_AND_NULL(numbers);
+	FREE_AND_NULL(expected);
 }
 
-static struct number *prepare_list(const int *arr, int n)
+static void check_sort(const int *input, size_t nr)
 {
-	int i;
+	struct number *list, *previous = NULL;
 
-	ALLOC_ARRAY(numbers, n);
-	for (i = 0; i < n; i++) {
-		numbers[i].value = arr[i];
+	ALLOC_ARRAY(numbers, nr);
+	ALLOC_ARRAY(expected, nr);
+	COPY_ARRAY(expected, input, nr);
+	QSORT(expected, nr, compare_ints);
+	for (size_t i = 0; i < nr; i++) {
+		numbers[i].value = input[i];
 		numbers[i].rank = i;
-		numbers[i].next = i + 1 < n ? &numbers[i + 1] : NULL;
+		numbers[i].next = i + 1 < nr ? &numbers[i + 1] : NULL;
 	}
-	return n ? numbers : NULL;
-}
-
-static void check_list(struct number *list, const int *expected,
-		       int n, const char *context)
-{
-	struct number *previous = NULL;
-	int i;
 
-	/* Bound traversal so a cycle is reported as an overlong list. */
-	for (i = 0; i < n; i++) {
-		cl_assert_(list, context);
-		cl_assert_equal_i_(list->value, expected[i], "%s: index %d",
-				   context, i);
+	list = nr ? numbers : NULL;
+	sort_numbers(&list, compare_numbers);
+	for (size_t i = 0; i < nr; i++) {
+		cl_assert_(list, "list is too short");
+		cl_assert_equal_i_(list->value, expected[i],
+				   "size %zu, item %zu", nr, i);
 		if (previous && previous->value == list->value)
 			cl_assert_lt_i_(previous->rank, list->rank,
-					"%s: stability at index %d", context, i);
+					"stability: size %zu, item %zu", nr, i);
 		previous = list;
 		list = list->next;
 	}
-	cl_assert_(list == NULL, context);
+	cl_assert_(list == NULL, "list is too long");
+	test_mergesort__cleanup();
 }
 
-/*
- * A version of the qsort certification program from "Engineering a Sort
- * Function" by Bentley and McIlroy, Software—Practice and Experience,
- * Volume 23, Issue 11, 1249–1265 (November 1993).
- */
-static void certify(const struct dist *distribution)
-{
-	static const int sizes[] = { 100, 1023, 1024, 1025 };
-	size_t i, j;
-	int m;
-
-	for (i = 0; i < ARRAY_SIZE(sizes); i++) {
-		int n = sizes[i];
+static const size_t sizes[] = { 100, 1023, 1024, 1025 };
 
-		for (j = 0; j < ARRAY_SIZE(mode); j++) {
-			for (m = 1; m < 2 * n; m *= 2) {
-				struct number *list;
-				char context[128];
+void test_mergesort__sorted(void)
+{
+	int input[1025];
 
-				xsnprintf(context, sizeof(context),
-					  "%s %s n=%d m=%d",
-					  distribution->name, mode[j].name, n, m);
-				ALLOC_ARRAY(values, n);
-				distribution->fn(values, n, m);
-				mode[j].fn(values, n);
-				list = prepare_list(values, n);
-				sort_numbers(&list, compare_numbers);
-				QSORT(values, n, compare_ints);
-				check_list(list, values, n, context);
-				test_mergesort__cleanup();
-			}
-		}
-	}
+	for (size_t i = 0; i < ARRAY_SIZE(input); i++)
+		input[i] = i;
+	for (size_t i = 0; i < ARRAY_SIZE(sizes); i++)
+		check_sort(input, sizes[i]);
 }
 
-void test_mergesort__sawtooth(void)
+void test_mergesort__reversed(void)
 {
-	certify(&dist[0]);
-}
+	int input[1025];
 
-void test_mergesort__rand(void)
-{
-	certify(&dist[1]);
+	for (size_t i = 0; i < ARRAY_SIZE(sizes); i++) {
+		for (size_t j = 0; j < sizes[i]; j++)
+			input[j] = sizes[i] - j;
+		check_sort(input, sizes[i]);
+	}
 }
 
-void test_mergesort__stagger(void)
+void test_mergesort__equal_values(void)
 {
-	certify(&dist[2]);
-}
+	int input[1025] = { 0 };
 
-void test_mergesort__plateau(void)
-{
-	certify(&dist[3]);
+	for (size_t i = 0; i < ARRAY_SIZE(sizes); i++)
+		check_sort(input, sizes[i]);
 }
 
-void test_mergesort__shuffle(void)
+void test_mergesort__random(void)
 {
-	certify(&dist[4]);
+	int input[1025];
+	uint32_t seed = 1;
+
+	for (size_t i = 0; i < ARRAY_SIZE(input); i++) {
+		seed = (uint64_t)seed * 48271 % 2147483647;
+		input[i] = seed % 32;
+	}
+	for (size_t i = 0; i < ARRAY_SIZE(sizes); i++)
+		check_sort(input, sizes[i]);
 }
-- 
2.55.0

[PATCH v3 3/4] mergesort: cover empty and small lists

[Muhammed Dilshad A]

The existing tests use at least 100 items. Add empty and single-item
lists, reversed and equal pairs, and a small list with duplicate values
and integer limits. Add two sorted runs whose values need to interleave
during the merge.

Also check that the debug version sorts a two-item list and calls both
the get-next and set-next hooks.

Signed-off-by: Muhammed Dilshad A <dilsheddilu123@gmail.com>
---
 t/unit-tests/u-mergesort.c | 63 ++++++++++++++++++++++++++++++++++++++
 1 file changed, 63 insertions(+)

diff --git a/t/unit-tests/u-mergesort.c b/t/unit-tests/u-mergesort.c
index 50bca1db46..1a5c0a60a8 100644
--- a/t/unit-tests/u-mergesort.c
+++ b/t/unit-tests/u-mergesort.c
@@ -9,6 +9,11 @@ struct number {
 
 DEFINE_LIST_SORT(static, sort_numbers, struct number, next);
 
+static int get_next_count, set_next_count;
+
+DEFINE_LIST_SORT_DEBUG(static, sort_numbers_debug, struct number, next,
+		       get_next_count++, set_next_count++);
+
 static int compare_numbers(const struct number *a, const struct number *b)
 {
 	return (a->value > b->value) - (a->value < b->value);
@@ -103,3 +108,61 @@ void test_mergesort__random(void)
 	for (size_t i = 0; i < ARRAY_SIZE(sizes); i++)
 		check_sort(input, sizes[i]);
 }
+
+void test_mergesort__empty(void)
+{
+	check_sort(NULL, 0);
+}
+
+void test_mergesort__singleton(void)
+{
+	const int input[] = { 42 };
+
+	check_sort(input, ARRAY_SIZE(input));
+}
+
+void test_mergesort__reversed_pair(void)
+{
+	const int input[] = { 2, 1 };
+
+	check_sort(input, ARRAY_SIZE(input));
+}
+
+void test_mergesort__equal_pair(void)
+{
+	const int input[] = { 1, 1 };
+
+	check_sort(input, ARRAY_SIZE(input));
+}
+
+void test_mergesort__interleaved_runs(void)
+{
+	const int input[] = { 0, 2, 4, 6, 1, 3, 5, 7 };
+
+	check_sort(input, ARRAY_SIZE(input));
+}
+
+void test_mergesort__mixed_values(void)
+{
+	const int input[] = { INT_MAX, -1, 0, INT_MIN, -1, INT_MAX, 0 };
+
+	check_sort(input, ARRAY_SIZE(input));
+}
+
+void test_mergesort__debug_hooks(void)
+{
+	struct number nodes[] = {
+		{ .value = 2 },
+		{ .value = 1 },
+	};
+	struct number *list = &nodes[0];
+
+	nodes[0].next = &nodes[1];
+	get_next_count = set_next_count = 0;
+	sort_numbers_debug(&list, compare_numbers);
+	cl_assert_equal_p(list, &nodes[1]);
+	cl_assert_equal_p(list->next, &nodes[0]);
+	cl_assert_equal_p(list->next->next, NULL);
+	cl_assert_gt_i(get_next_count, 0);
+	cl_assert_gt_i(set_next_count, 0);
+}
-- 
2.55.0

[PATCH v3 4/4] t: retire the sorting benchmark and mergesort helper

[Muhammed Dilshad A]

p0071 was added to compare sorting implementations during mergesort
development. Retire that benchmark. A benchmark can be added again if
future sorting changes need measurements.

With the numeric tests now in Clar, p0071 is the last user of test-tool
mergesort. Remove the helper and its command and build registrations.

Suggested-by: Patrick Steinhardt <ps@pks.im>
Signed-off-by: Muhammed Dilshad A <dilsheddilu123@gmail.com>
---
 Makefile                  |  1 -
 t/helper/meson.build      |  1 -
 t/helper/test-mergesort.c | 65 ---------------------------------------
 t/helper/test-tool.c      |  1 -
 t/helper/test-tool.h      |  1 -
 t/meson.build             |  1 -
 t/perf/p0071-sort.sh      | 52 -------------------------------
 7 files changed, 122 deletions(-)
 delete mode 100644 t/helper/test-mergesort.c
 delete mode 100755 t/perf/p0071-sort.sh

diff --git a/Makefile b/Makefile
index cac535ba19..4b35808b2e 100644
--- a/Makefile
+++ b/Makefile
@@ -835,7 +835,6 @@ TEST_BUILTINS_OBJS += test-hexdump.o
 TEST_BUILTINS_OBJS += test-json-writer.o
 TEST_BUILTINS_OBJS += test-lazy-init-name-hash.o
 TEST_BUILTINS_OBJS += test-match-trees.o
-TEST_BUILTINS_OBJS += test-mergesort.o
 TEST_BUILTINS_OBJS += test-mktemp.o
 TEST_BUILTINS_OBJS += test-name-hash.o
 TEST_BUILTINS_OBJS += test-online-cpus.o
diff --git a/t/helper/meson.build b/t/helper/meson.build
index 3235f10ab8..e94e6f10fb 100644
--- a/t/helper/meson.build
+++ b/t/helper/meson.build
@@ -32,7 +32,6 @@ test_tool_sources = [
   'test-json-writer.c',
   'test-lazy-init-name-hash.c',
   'test-match-trees.c',
-  'test-mergesort.c',
   'test-mktemp.c',
   'test-name-hash.c',
   'test-online-cpus.c',
diff --git a/t/helper/test-mergesort.c b/t/helper/test-mergesort.c
deleted file mode 100644
index d22a139f9e..0000000000
--- a/t/helper/test-mergesort.c
+++ /dev/null
@@ -1,65 +0,0 @@
-#include "test-tool.h"
-#include "mem-pool.h"
-#include "mergesort.h"
-#include "strbuf.h"
-
-struct line {
-	char *text;
-	struct line *next;
-};
-
-DEFINE_LIST_SORT(static, sort_lines, struct line, next);
-
-static int compare_strings(const struct line *x, const struct line *y)
-{
-	return strcmp(x->text, y->text);
-}
-
-static int sort_stdin(void)
-{
-	struct line *lines;
-	struct line **tail = &lines;
-	struct strbuf sb = STRBUF_INIT;
-	struct mem_pool lines_pool;
-	char *p;
-
-	strbuf_read(&sb, 0, 0);
-
-	/*
-	 * Split by newline, but don't create an item
-	 * for the empty string after the last separator.
-	 */
-	if (sb.len && sb.buf[sb.len - 1] == '\n')
-		strbuf_setlen(&sb, sb.len - 1);
-
-	mem_pool_init(&lines_pool, 0);
-	p = sb.buf;
-	for (;;) {
-		char *eol = strchr(p, '\n');
-		struct line *line = mem_pool_alloc(&lines_pool, sizeof(*line));
-		line->text = p;
-		*tail = line;
-		tail = &line->next;
-		if (!eol)
-			break;
-		*eol = '\0';
-		p = eol + 1;
-	}
-	*tail = NULL;
-
-	sort_lines(&lines, compare_strings);
-
-	while (lines) {
-		puts(lines->text);
-		lines = lines->next;
-	}
-	return 0;
-}
-
-int cmd__mergesort(int argc, const char **argv)
-{
-	if (argc == 2 && !strcmp(argv[1], "sort"))
-		return sort_stdin();
-	fprintf(stderr, "usage: test-tool mergesort sort\n");
-	return 129;
-}
diff --git a/t/helper/test-tool.c b/t/helper/test-tool.c
index b71a22b43b..2e80dc7ab8 100644
--- a/t/helper/test-tool.c
+++ b/t/helper/test-tool.c
@@ -42,7 +42,6 @@ static struct test_cmd cmds[] = {
 	{ "json-writer", cmd__json_writer },
 	{ "lazy-init-name-hash", cmd__lazy_init_name_hash },
 	{ "match-trees", cmd__match_trees },
-	{ "mergesort", cmd__mergesort },
 	{ "mktemp", cmd__mktemp },
 	{ "name-hash", cmd__name_hash },
 	{ "online-cpus", cmd__online_cpus },
diff --git a/t/helper/test-tool.h b/t/helper/test-tool.h
index f2885b33d5..9442c61ffd 100644
--- a/t/helper/test-tool.h
+++ b/t/helper/test-tool.h
@@ -35,7 +35,6 @@ int cmd__hexdump(int argc, const char **argv);
 int cmd__json_writer(int argc, const char **argv);
 int cmd__lazy_init_name_hash(int argc, const char **argv);
 int cmd__match_trees(int argc, const char **argv);
-int cmd__mergesort(int argc, const char **argv);
 int cmd__mktemp(int argc, const char **argv);
 int cmd__name_hash(int argc, const char **argv);
 int cmd__online_cpus(int argc, const char **argv);
diff --git a/t/meson.build b/t/meson.build
index 2752321e0d..07436b63f4 100644
--- a/t/meson.build
+++ b/t/meson.build
@@ -1146,7 +1146,6 @@ benchmarks = [
   'perf/p0006-read-tree-checkout.sh',
   'perf/p0007-write-cache.sh',
   'perf/p0008-odb-fsync.sh',
-  'perf/p0071-sort.sh',
   'perf/p0090-cache-tree.sh',
   'perf/p0100-globbing.sh',
   'perf/p1006-cat-file.sh',
diff --git a/t/perf/p0071-sort.sh b/t/perf/p0071-sort.sh
deleted file mode 100755
index ae4ddac864..0000000000
--- a/t/perf/p0071-sort.sh
+++ /dev/null
@@ -1,52 +0,0 @@
-#!/bin/sh
-
-test_description='Basic sort performance tests'
-. ./perf-lib.sh
-
-test_perf_default_repo
-
-test_expect_success 'setup' '
-	git ls-files --stage "*.[ch]" "*.sh" |
-	cut -f2 -d" " |
-	git cat-file --batch >unsorted
-'
-
-test_perf 'sort(1) unsorted' '
-	sort <unsorted >sorted
-'
-
-test_expect_success 'reverse' '
-	sort -r <unsorted >reversed
-'
-
-for file in sorted reversed
-do
-	test_perf "sort(1) $file" "
-		sort <$file >actual
-	"
-done
-
-for file in unsorted sorted reversed
-do
-
-	test_perf "string_list_sort() $file" "
-		test-tool string-list sort <$file >actual
-	"
-
-	test_expect_success "string_list_sort() $file sorts like sort(1)" "
-		test_cmp_bin sorted actual
-	"
-done
-
-for file in unsorted sorted reversed
-do
-	test_perf "DEFINE_LIST_SORT $file" "
-		test-tool mergesort sort <$file >actual
-	"
-
-	test_expect_success "DEFINE_LIST_SORT $file sorts like sort(1)" "
-		test_cmp_bin sorted actual
-	"
-done
-
-test_done
-- 
2.55.0