[GSoC][PATCH 0/6] t: port reftable/pq_test.c to the unit testing

[GSoC][PATCH 0/6] t: port reftable/pq_test.c to the unit testing

[Chandra Pratap]

In the recent codebase update (commit 8bf6fbd, 2023-12-09), a new unit
testing framework written entirely in C was introduced to the Git project
aimed at simplifying testing and reducing test run times.
Currently, tests for the reftable refs-backend are performed by a custom
testing framework defined by reftable/test_framework.{c, h}. Port
reftable/pq_test.c to the unit testing framework and improve upon
the ported test.

The first patch in the series is preparatory cleanup, the second patch
moves the test to the unit testing framework, and the rest of the patches
improve upon the ported test.

Mentored-by: Patrick Steinhardt <ps@pks.im>
Mentored-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>

CI/PR: https://github.com/gitgitgadget/git/pull/1745

Chandra Pratap (6):
reftable: clean up reftable/pq.c
t: move reftable/pq_test.c to the unit testing framework
t-reftable-pq: make merged_iter_pqueue_check() static
t-reftable-pq: make merged_iter_pqueue_check() callable
t-reftable-pq: add test for index based comparison
t-reftable-pq: add tests for merged_iter_pqueue_top()

[GSoC][PATCH 1/6] reftable: clean up reftable/pq.c

[Chandra Pratap]

According to Documentation/CodingGuidelines, control-flow statements
with a single line as their body must omit curly braces. Make
reftable/pq.c conform to this guideline. Besides that, remove
unnecessary newlines and variable assignment.

Mentored-by: Patrick Steinhardt <ps@pks.im>
Mentored-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
---
 reftable/pq.c | 18 ++++--------------
 1 file changed, 4 insertions(+), 14 deletions(-)

diff --git a/reftable/pq.c b/reftable/pq.c
index 7fb45d8c60..0401c47068 100644
--- a/reftable/pq.c
+++ b/reftable/pq.c
@@ -27,22 +27,16 @@ struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq)
 	pq->heap[0] = pq->heap[pq->len - 1];
 	pq->len--;
 
-	i = 0;
 	while (i < pq->len) {
 		int min = i;
 		int j = 2 * i + 1;
 		int k = 2 * i + 2;
-		if (j < pq->len && pq_less(&pq->heap[j], &pq->heap[i])) {
+		if (j < pq->len && pq_less(&pq->heap[j], &pq->heap[i]))
 			min = j;
-		}
-		if (k < pq->len && pq_less(&pq->heap[k], &pq->heap[min])) {
+		if (k < pq->len && pq_less(&pq->heap[k], &pq->heap[min]))
 			min = k;
-		}
-
-		if (min == i) {
+		if (min == i)
 			break;
-		}
-
 		SWAP(pq->heap[i], pq->heap[min]);
 		i = min;
 	}
@@ -53,19 +47,15 @@ struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq)
 void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry *e)
 {
 	int i = 0;
-
 	REFTABLE_ALLOC_GROW(pq->heap, pq->len + 1, pq->cap);
 	pq->heap[pq->len++] = *e;
 
 	i = pq->len - 1;
 	while (i > 0) {
 		int j = (i - 1) / 2;
-		if (pq_less(&pq->heap[j], &pq->heap[i])) {
+		if (pq_less(&pq->heap[j], &pq->heap[i]))
 			break;
-		}
-
 		SWAP(pq->heap[j], pq->heap[i]);
-
 		i = j;
 	}
 }
-- 
2.45.2.404.g9eaef5822c

Re: [GSoC][PATCH 1/6] reftable: clean up reftable/pq.c

[Christian Couder]

On Thu, Jun 6, 2024 at 9:57 AM Chandra Pratap
<chandrapratap3519@gmail.com> wrote:
>
> According to Documentation/CodingGuidelines, control-flow statements
> with a single line as their body must omit curly braces. Make
> reftable/pq.c conform to this guideline. Besides that, remove
> unnecessary newlines and variable assignment.

A commit subject like "reftable/pq: remove unnecessary curly braces"
might be a bit more specific.

Re: [GSoC][PATCH 1/6] reftable: clean up reftable/pq.c

[Chandra Pratap]

On Thu, 6 Jun 2024 at 14:21, Christian Couder
<christian.couder@gmail.com> wrote:
>
> On Thu, Jun 6, 2024 at 9:57 AM Chandra Pratap
> <chandrapratap3519@gmail.com> wrote:
> >
> > According to Documentation/CodingGuidelines, control-flow statements
> > with a single line as their body must omit curly braces. Make
> > reftable/pq.c conform to this guideline. Besides that, remove
> > unnecessary newlines and variable assignment.
>
> A commit subject like "reftable/pq: remove unnecessary curly braces"
> might be a bit more specific.

There are other forms of cleanup also being performed, like removing
unnecessary newlines and variable assignment. Would it still be okay
to sweep it all under 'removing unnecessary braces'?

Re: [GSoC][PATCH 1/6] reftable: clean up reftable/pq.c

[Christian Couder]

On Thu, Jun 6, 2024 at 12:07 PM Chandra Pratap
<chandrapratap3519@gmail.com> wrote:
>
> On Thu, 6 Jun 2024 at 14:21, Christian Couder
> <christian.couder@gmail.com> wrote:
> >
> > On Thu, Jun 6, 2024 at 9:57 AM Chandra Pratap
> > <chandrapratap3519@gmail.com> wrote:
> > >
> > > According to Documentation/CodingGuidelines, control-flow statements
> > > with a single line as their body must omit curly braces. Make
> > > reftable/pq.c conform to this guideline. Besides that, remove
> > > unnecessary newlines and variable assignment.
> >
> > A commit subject like "reftable/pq: remove unnecessary curly braces"
> > might be a bit more specific.
>
> There are other forms of cleanup also being performed, like removing
> unnecessary newlines and variable assignment. Would it still be okay
> to sweep it all under 'removing unnecessary braces'?

I think the removal of unnecessary braces is the main change and other
changes are made while at it, so I think it's Ok.

[GSoC][PATCH 2/6] t: move reftable/pq_test.c to the unit testing framework

[Chandra Pratap]

reftable/pq_test.c exercises a priority queue defined by
reftable/pq.{c, h}. Migrate reftable/pq_test.c to the unit
testing framework. Migration involves refactoring the tests
to use the unit testing framework instead of reftable's test
framework.

Mentored-by: Patrick Steinhardt <ps@pks.im>
Mentored-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
---
 Makefile                                      |  2 +-
 t/helper/test-reftable.c                      |  1 -
 .../pq_test.c => t/unit-tests/t-reftable-pq.c | 35 ++++++++-----------
 3 files changed, 15 insertions(+), 23 deletions(-)
 rename reftable/pq_test.c => t/unit-tests/t-reftable-pq.c (64%)

diff --git a/Makefile b/Makefile
index 59d98ba688..1cabe4cc69 100644
--- a/Makefile
+++ b/Makefile
@@ -1336,6 +1336,7 @@ THIRD_PARTY_SOURCES += sha1dc/%
 UNIT_TEST_PROGRAMS += t-ctype
 UNIT_TEST_PROGRAMS += t-mem-pool
 UNIT_TEST_PROGRAMS += t-prio-queue
+UNIT_TEST_PROGRAMS += t-reftable-pq
 UNIT_TEST_PROGRAMS += t-strbuf
 UNIT_TEST_PROGRAMS += t-strcmp-offset
 UNIT_TEST_PROGRAMS += t-trailer
@@ -2675,7 +2676,6 @@ REFTABLE_TEST_OBJS += reftable/basics_test.o
 REFTABLE_TEST_OBJS += reftable/block_test.o
 REFTABLE_TEST_OBJS += reftable/dump.o
 REFTABLE_TEST_OBJS += reftable/merged_test.o
-REFTABLE_TEST_OBJS += reftable/pq_test.o
 REFTABLE_TEST_OBJS += reftable/record_test.o
 REFTABLE_TEST_OBJS += reftable/readwrite_test.o
 REFTABLE_TEST_OBJS += reftable/stack_test.o
diff --git a/t/helper/test-reftable.c b/t/helper/test-reftable.c
index bae731669c..86a2b0f91a 100644
--- a/t/helper/test-reftable.c
+++ b/t/helper/test-reftable.c
@@ -9,7 +9,6 @@ int cmd__reftable(int argc, const char **argv)
 	record_test_main(argc, argv);
 	block_test_main(argc, argv);
 	tree_test_main(argc, argv);
-	pq_test_main(argc, argv);
 	readwrite_test_main(argc, argv);
 	merged_test_main(argc, argv);
 	stack_test_main(argc, argv);
diff --git a/reftable/pq_test.c b/t/unit-tests/t-reftable-pq.c
similarity index 64%
rename from reftable/pq_test.c
rename to t/unit-tests/t-reftable-pq.c
index b7d3c80cc7..dcde73de66 100644
--- a/reftable/pq_test.c
+++ b/t/unit-tests/t-reftable-pq.c
@@ -6,35 +6,28 @@ license that can be found in the LICENSE file or at
 https://developers.google.com/open-source/licenses/bsd
 */
 
-#include "system.h"
-
-#include "basics.h"
-#include "constants.h"
-#include "pq.h"
-#include "record.h"
-#include "reftable-tests.h"
-#include "test_framework.h"
+#include "test-lib.h"
+#include "reftable/constants.h"
+#include "reftable/pq.h"
 
 void merged_iter_pqueue_check(struct merged_iter_pqueue pq)
 {
-	int i;
-	for (i = 1; i < pq.len; i++) {
+	for (int i = 1; i < pq.len; i++) {
 		int parent = (i - 1) / 2;
-
-		EXPECT(pq_less(&pq.heap[parent], &pq.heap[i]));
+		check(pq_less(&pq.heap[parent], &pq.heap[i]));
 	}
 }
 
 static void test_pq(void)
 {
-	struct merged_iter_pqueue pq = { NULL };
+	struct merged_iter_pqueue pq = { 0 };
 	struct reftable_record recs[54];
-	int N = ARRAY_SIZE(recs) - 1, i;
+	size_t N = ARRAY_SIZE(recs) - 1, i;
 	char *last = NULL;
 
 	for (i = 0; i < N; i++) {
 		struct strbuf refname = STRBUF_INIT;
-		strbuf_addf(&refname, "%02d", i);
+		strbuf_addf(&refname, "%02ld", (long)i);
 
 		reftable_record_init(&recs[i], BLOCK_TYPE_REF);
 		recs[i].u.ref.refname = strbuf_detach(&refname, NULL);
@@ -48,7 +41,6 @@ static void test_pq(void)
 
 		merged_iter_pqueue_add(&pq, &e);
 		merged_iter_pqueue_check(pq);
-
 		i = (i * 7) % N;
 	} while (i != 1);
 
@@ -56,9 +48,9 @@ static void test_pq(void)
 		struct pq_entry e = merged_iter_pqueue_remove(&pq);
 		merged_iter_pqueue_check(pq);
 
-		EXPECT(reftable_record_type(e.rec) == BLOCK_TYPE_REF);
+		check(reftable_record_type(e.rec) == BLOCK_TYPE_REF);
 		if (last)
-			EXPECT(strcmp(last, e.rec->u.ref.refname) < 0);
+			check_int(strcmp(last, e.rec->u.ref.refname), <, 0);
 		last = e.rec->u.ref.refname;
 	}
 
@@ -67,8 +59,9 @@ static void test_pq(void)
 	merged_iter_pqueue_release(&pq);
 }
 
-int pq_test_main(int argc, const char *argv[])
+int cmd_main(int argc, const char *argv[])
 {
-	RUN_TEST(test_pq);
-	return 0;
+	TEST(test_pq(), "pq works");
+
+	return test_done();
 }
-- 
2.45.2.404.g9eaef5822c

Re: [GSoC][PATCH 2/6] t: move reftable/pq_test.c to the unit testing framework

[Patrick Steinhardt]

[-- Attachment #1: Type: text/plain, Size: 4354 bytes --]

On Thu, Jun 06, 2024 at 01:10:46PM +0530, Chandra Pratap wrote:
> reftable/pq_test.c exercises a priority queue defined by
> reftable/pq.{c, h}. Migrate reftable/pq_test.c to the unit
> testing framework. Migration involves refactoring the tests
> to use the unit testing framework instead of reftable's test
> framework.
> 
> Mentored-by: Patrick Steinhardt <ps@pks.im>
> Mentored-by: Christian Couder <chriscool@tuxfamily.org>
> Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
> ---
>  Makefile                                      |  2 +-
>  t/helper/test-reftable.c                      |  1 -
>  .../pq_test.c => t/unit-tests/t-reftable-pq.c | 35 ++++++++-----------
>  3 files changed, 15 insertions(+), 23 deletions(-)
>  rename reftable/pq_test.c => t/unit-tests/t-reftable-pq.c (64%)
> 
> diff --git a/Makefile b/Makefile
> index 59d98ba688..1cabe4cc69 100644
> --- a/Makefile
> +++ b/Makefile
> @@ -1336,6 +1336,7 @@ THIRD_PARTY_SOURCES += sha1dc/%
>  UNIT_TEST_PROGRAMS += t-ctype
>  UNIT_TEST_PROGRAMS += t-mem-pool
>  UNIT_TEST_PROGRAMS += t-prio-queue
> +UNIT_TEST_PROGRAMS += t-reftable-pq
>  UNIT_TEST_PROGRAMS += t-strbuf
>  UNIT_TEST_PROGRAMS += t-strcmp-offset
>  UNIT_TEST_PROGRAMS += t-trailer
> @@ -2675,7 +2676,6 @@ REFTABLE_TEST_OBJS += reftable/basics_test.o
>  REFTABLE_TEST_OBJS += reftable/block_test.o
>  REFTABLE_TEST_OBJS += reftable/dump.o
>  REFTABLE_TEST_OBJS += reftable/merged_test.o
> -REFTABLE_TEST_OBJS += reftable/pq_test.o
>  REFTABLE_TEST_OBJS += reftable/record_test.o
>  REFTABLE_TEST_OBJS += reftable/readwrite_test.o
>  REFTABLE_TEST_OBJS += reftable/stack_test.o
> diff --git a/t/helper/test-reftable.c b/t/helper/test-reftable.c
> index bae731669c..86a2b0f91a 100644
> --- a/t/helper/test-reftable.c
> +++ b/t/helper/test-reftable.c
> @@ -9,7 +9,6 @@ int cmd__reftable(int argc, const char **argv)
>  	record_test_main(argc, argv);
>  	block_test_main(argc, argv);
>  	tree_test_main(argc, argv);
> -	pq_test_main(argc, argv);
>  	readwrite_test_main(argc, argv);
>  	merged_test_main(argc, argv);
>  	stack_test_main(argc, argv);
> diff --git a/reftable/pq_test.c b/t/unit-tests/t-reftable-pq.c
> similarity index 64%
> rename from reftable/pq_test.c
> rename to t/unit-tests/t-reftable-pq.c
> index b7d3c80cc7..dcde73de66 100644
> --- a/reftable/pq_test.c
> +++ b/t/unit-tests/t-reftable-pq.c
> @@ -6,35 +6,28 @@ license that can be found in the LICENSE file or at
>  https://developers.google.com/open-source/licenses/bsd
>  */
>  
> -#include "system.h"
> -
> -#include "basics.h"
> -#include "constants.h"
> -#include "pq.h"
> -#include "record.h"
> -#include "reftable-tests.h"
> -#include "test_framework.h"
> +#include "test-lib.h"
> +#include "reftable/constants.h"
> +#include "reftable/pq.h"
>  
>  void merged_iter_pqueue_check(struct merged_iter_pqueue pq)
>  {
> -	int i;
> -	for (i = 1; i < pq.len; i++) {
> +	for (int i = 1; i < pq.len; i++) {

If we're changing this already, then we can also convert it to `size_t
i` while at it to match the type of `pq.len`.

>  		int parent = (i - 1) / 2;
> -
> -		EXPECT(pq_less(&pq.heap[parent], &pq.heap[i]));
> +		check(pq_less(&pq.heap[parent], &pq.heap[i]));
>  	}
>  }
>  
>  static void test_pq(void)
>  {
> -	struct merged_iter_pqueue pq = { NULL };
> +	struct merged_iter_pqueue pq = { 0 };
>  	struct reftable_record recs[54];
> -	int N = ARRAY_SIZE(recs) - 1, i;
> +	size_t N = ARRAY_SIZE(recs) - 1, i;
>  	char *last = NULL;
>  
>  	for (i = 0; i < N; i++) {
>  		struct strbuf refname = STRBUF_INIT;
> -		strbuf_addf(&refname, "%02d", i);
> +		strbuf_addf(&refname, "%02ld", (long)i);

This should rather be:

    strubf_addf(&refname, "%02"PRIuMAX, (uintmax_t) i);

This is splitting hairs though as it does not matter in practice. But
I'd either drop this change to convert `N` and `i` to become a `size_t`,
or I'd do it correctly.

>  		reftable_record_init(&recs[i], BLOCK_TYPE_REF);
>  		recs[i].u.ref.refname = strbuf_detach(&refname, NULL);
> @@ -48,7 +41,6 @@ static void test_pq(void)
>  
>  		merged_iter_pqueue_add(&pq, &e);
>  		merged_iter_pqueue_check(pq);
> -
>  		i = (i * 7) % N;
>  	} while (i != 1);

This removed newline is of dubious value, but I guess that's
subjective.

Patrick

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

[GSoC][PATCH 3/6] t-reftable-pq: make merged_iter_pqueue_check() static

[Chandra Pratap]

merged_iter_pqueue_check() is a function previously defined in
reftable/pq_test.c (now t/unit-tests/t-reftable-pq.c) and used in
the testing of a priority queue as defined by reftable/pq.{c, h}.
As such, this function is only called by reftable/pq_test.c and it
makes little sense to expose it to non-testing code via reftable/pq.h.

Hence, make this function static and remove its prototype from
reftable/pq.h.

Mentored-by: Patrick Steinhardt <ps@pks.im>
Mentored-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
---
 reftable/pq.h                | 1 -
 t/unit-tests/t-reftable-pq.c | 2 +-
 2 files changed, 1 insertion(+), 2 deletions(-)

diff --git a/reftable/pq.h b/reftable/pq.h
index f796c23179..707bd26767 100644
--- a/reftable/pq.h
+++ b/reftable/pq.h
@@ -22,7 +22,6 @@ struct merged_iter_pqueue {
 	size_t cap;
 };
 
-void merged_iter_pqueue_check(struct merged_iter_pqueue pq);
 struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq);
 void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry *e);
 void merged_iter_pqueue_release(struct merged_iter_pqueue *pq);
diff --git a/t/unit-tests/t-reftable-pq.c b/t/unit-tests/t-reftable-pq.c
index dcde73de66..5c5a4ecdc5 100644
--- a/t/unit-tests/t-reftable-pq.c
+++ b/t/unit-tests/t-reftable-pq.c
@@ -10,7 +10,7 @@ license that can be found in the LICENSE file or at
 #include "reftable/constants.h"
 #include "reftable/pq.h"
 
-void merged_iter_pqueue_check(struct merged_iter_pqueue pq)
+static void merged_iter_pqueue_check(struct merged_iter_pqueue pq)
 {
 	for (int i = 1; i < pq.len; i++) {
 		int parent = (i - 1) / 2;
-- 
2.45.2.404.g9eaef5822c

[GSoC][PATCH 4/6] t-reftable-pq: make merged_iter_pqueue_check() callable by reference

[Chandra Pratap]

merged_iter_pqueue_check() checks the validity of a priority queue
represented by a merged_iter_pqueue struct by asserting the
parent-child relation in the struct's heap. Explicity passing a
struct to this function means a copy of the entire struct is created,
which is inefficient.

Make the function accept a pointer to the struct instead. This is
safe to do since the function doesn't modify the struct in any way.
Make the function parameter 'const' to assert immutability.

Mentored-by: Patrick Steinhardt <ps@pks.im>
Mentored-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
---
 t/unit-tests/t-reftable-pq.c | 10 +++++-----
 1 file changed, 5 insertions(+), 5 deletions(-)

diff --git a/t/unit-tests/t-reftable-pq.c b/t/unit-tests/t-reftable-pq.c
index 5c5a4ecdc5..30bf9cb492 100644
--- a/t/unit-tests/t-reftable-pq.c
+++ b/t/unit-tests/t-reftable-pq.c
@@ -10,11 +10,11 @@ license that can be found in the LICENSE file or at
 #include "reftable/constants.h"
 #include "reftable/pq.h"
 
-static void merged_iter_pqueue_check(struct merged_iter_pqueue pq)
+static void merged_iter_pqueue_check(const struct merged_iter_pqueue *pq)
 {
-	for (int i = 1; i < pq.len; i++) {
+	for (int i = 1; i < pq->len; i++) {
 		int parent = (i - 1) / 2;
-		check(pq_less(&pq.heap[parent], &pq.heap[i]));
+		check(pq_less(&pq->heap[parent], &pq->heap[i]));
 	}
 }
 
@@ -40,13 +40,13 @@ static void test_pq(void)
 		};
 
 		merged_iter_pqueue_add(&pq, &e);
-		merged_iter_pqueue_check(pq);
+		merged_iter_pqueue_check(&pq);
 		i = (i * 7) % N;
 	} while (i != 1);
 
 	while (!merged_iter_pqueue_is_empty(pq)) {
 		struct pq_entry e = merged_iter_pqueue_remove(&pq);
-		merged_iter_pqueue_check(pq);
+		merged_iter_pqueue_check(&pq);
 
 		check(reftable_record_type(e.rec) == BLOCK_TYPE_REF);
 		if (last)
-- 
2.45.2.404.g9eaef5822c

Re: [GSoC][PATCH 4/6] t-reftable-pq: make merged_iter_pqueue_check() callable by reference

[Patrick Steinhardt]

[-- Attachment #1: Type: text/plain, Size: 922 bytes --]

On Thu, Jun 06, 2024 at 01:10:48PM +0530, Chandra Pratap wrote:
> diff --git a/t/unit-tests/t-reftable-pq.c b/t/unit-tests/t-reftable-pq.c
> index 5c5a4ecdc5..30bf9cb492 100644
> --- a/t/unit-tests/t-reftable-pq.c
> +++ b/t/unit-tests/t-reftable-pq.c
> @@ -10,11 +10,11 @@ license that can be found in the LICENSE file or at
>  #include "reftable/constants.h"
>  #include "reftable/pq.h"
>  
> -static void merged_iter_pqueue_check(struct merged_iter_pqueue pq)
> +static void merged_iter_pqueue_check(const struct merged_iter_pqueue *pq)
>  {
> -	for (int i = 1; i < pq.len; i++) {
> +	for (int i = 1; i < pq->len; i++) {

Nit: we might also change this to `size_t i` while at it. I know that
these changes are not super popular, but I eventually want Git to
compile cleanly with `-Wsign-conversion`. So the more issues we fix
while at it, the smaller the patch series for this needs to be.

Patrick

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

[GSoC][PATCH 5/6] t-reftable-pq: add test for index based comparison

[Chandra Pratap]

When comparing two entries, the priority queue as defined by
reftable/pq.{c, h} first compares the entries on the basis of
their ref-record's keys. If the keys turn out to be equal, the
comparison is then made on the basis of their update indices
(which are never equal).

In the current testing setup, only the case for comparison on
the basis of ref-record's keys is exercised. Add a test for
index-based comparison as well. Rename the existing test to
reflect its nature of only testing record-based comparison.

Mentored-by: Patrick Steinhardt <ps@pks.im>
Mentored-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
---
 t/unit-tests/t-reftable-pq.c | 44 ++++++++++++++++++++++++++++++++++--
 1 file changed, 42 insertions(+), 2 deletions(-)

diff --git a/t/unit-tests/t-reftable-pq.c b/t/unit-tests/t-reftable-pq.c
index 30bf9cb492..6f6bf58307 100644
--- a/t/unit-tests/t-reftable-pq.c
+++ b/t/unit-tests/t-reftable-pq.c
@@ -18,7 +18,7 @@ static void merged_iter_pqueue_check(const struct merged_iter_pqueue *pq)
 	}
 }
 
-static void test_pq(void)
+static void test_pq_record(void)
 {
 	struct merged_iter_pqueue pq = { 0 };
 	struct reftable_record recs[54];
@@ -59,9 +59,49 @@ static void test_pq(void)
 	merged_iter_pqueue_release(&pq);
 }
 
+
+static void test_pq_index(void)
+{
+	struct merged_iter_pqueue pq = { 0 };
+	struct reftable_record recs[14];
+	char *last = NULL;
+	size_t N = ARRAY_SIZE(recs), i;
+
+	for (i = 0; i < N; i++) {
+		reftable_record_init(&recs[i], BLOCK_TYPE_REF);
+		recs[i].u.ref.refname = xstrdup("refs/heads/master");
+	}
+
+	for (i = 0; i < N; i++) {
+		struct pq_entry e = {
+			.rec = &recs[i],
+			.index = i,
+		};
+
+		merged_iter_pqueue_add(&pq, &e);
+		merged_iter_pqueue_check(&pq);
+	}
+
+	for (i = N - 1; !merged_iter_pqueue_is_empty(pq); i--) {
+		struct pq_entry e = merged_iter_pqueue_remove(&pq);
+		merged_iter_pqueue_check(&pq);
+
+		check(reftable_record_type(e.rec) == BLOCK_TYPE_REF);
+		check_int(e.index, ==, i);
+		if (last)
+			check_str(last, e.rec->u.ref.refname);
+		last = e.rec->u.ref.refname;
+	}
+
+	for (i = 0; i < N; i++)
+		reftable_record_release(&recs[i]);
+	merged_iter_pqueue_release(&pq);
+}
+
 int cmd_main(int argc, const char *argv[])
 {
-	TEST(test_pq(), "pq works");
+	TEST(test_pq_record(), "pq works with record-based comparison");
+	TEST(test_pq_index(), "pq works with index-based comparison");
 
 	return test_done();
 }
-- 
2.45.2.404.g9eaef5822c

Re: [GSoC][PATCH 5/6] t-reftable-pq: add test for index based comparison

[Patrick Steinhardt]

[-- Attachment #1: Type: text/plain, Size: 731 bytes --]

On Thu, Jun 06, 2024 at 01:10:49PM +0530, Chandra Pratap wrote:
> diff --git a/t/unit-tests/t-reftable-pq.c b/t/unit-tests/t-reftable-pq.c
> index 30bf9cb492..6f6bf58307 100644
> --- a/t/unit-tests/t-reftable-pq.c
> +++ b/t/unit-tests/t-reftable-pq.c
> @@ -18,7 +18,7 @@ static void merged_iter_pqueue_check(const struct merged_iter_pqueue *pq)
>  	}
>  }
>  
> -static void test_pq(void)
> +static void test_pq_record(void)
>  {
>  	struct merged_iter_pqueue pq = { 0 };
>  	struct reftable_record recs[54];
> @@ -59,9 +59,49 @@ static void test_pq(void)
>  	merged_iter_pqueue_release(&pq);
>  }
>  
> +

Nit: there's an extraneous empty line here.

Other than that this patch looks good to me.

Patrick

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

[GSoC][PATCH 6/6] t-reftable-pq: add tests for merged_iter_pqueue_top()

[Chandra Pratap]

merged_iter_pqueue_top() as defined by reftable/pq.{c, h} returns
the element at the top of a priority-queue's heap without removing
it. Since there are no tests for this function in the existing
setup, add tests for the same.

Mentored-by: Patrick Steinhardt <ps@pks.im>
Mentored-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
---
 t/unit-tests/t-reftable-pq.c | 49 +++++++++++++++++++++++++++++++++++-
 1 file changed, 48 insertions(+), 1 deletion(-)

diff --git a/t/unit-tests/t-reftable-pq.c b/t/unit-tests/t-reftable-pq.c
index 6f6bf58307..768337912f 100644
--- a/t/unit-tests/t-reftable-pq.c
+++ b/t/unit-tests/t-reftable-pq.c
@@ -18,6 +18,11 @@ static void merged_iter_pqueue_check(const struct merged_iter_pqueue *pq)
 	}
 }
 
+static int pq_entry_equal(struct pq_entry *a, struct pq_entry *b)
+{
+	return !reftable_record_cmp(a->rec, b->rec) && (a->index == b->index);
+}
+
 static void test_pq_record(void)
 {
 	struct merged_iter_pqueue pq = { 0 };
@@ -45,9 +50,11 @@ static void test_pq_record(void)
 	} while (i != 1);
 
 	while (!merged_iter_pqueue_is_empty(pq)) {
+		struct pq_entry top = merged_iter_pqueue_top(pq);
 		struct pq_entry e = merged_iter_pqueue_remove(&pq);
 		merged_iter_pqueue_check(&pq);
 
+		check(pq_entry_equal(&top, &e));
 		check(reftable_record_type(e.rec) == BLOCK_TYPE_REF);
 		if (last)
 			check_int(strcmp(last, e.rec->u.ref.refname), <, 0);
@@ -59,7 +66,6 @@ static void test_pq_record(void)
 	merged_iter_pqueue_release(&pq);
 }
 
-
 static void test_pq_index(void)
 {
 	struct merged_iter_pqueue pq = { 0 };
@@ -83,9 +89,11 @@ static void test_pq_index(void)
 	}
 
 	for (i = N - 1; !merged_iter_pqueue_is_empty(pq); i--) {
+		struct pq_entry top = merged_iter_pqueue_top(pq);
 		struct pq_entry e = merged_iter_pqueue_remove(&pq);
 		merged_iter_pqueue_check(&pq);
 
+		check(pq_entry_equal(&top, &e));
 		check(reftable_record_type(e.rec) == BLOCK_TYPE_REF);
 		check_int(e.index, ==, i);
 		if (last)
@@ -98,10 +106,49 @@ static void test_pq_index(void)
 	merged_iter_pqueue_release(&pq);
 }
 
+static void test_merged_iter_pqueue_top(void)
+{
+	struct merged_iter_pqueue pq = { 0 };
+	struct reftable_record recs[14];
+	size_t N = ARRAY_SIZE(recs), i;
+
+	for (i = 0; i < N; i++) {
+		reftable_record_init(&recs[i], BLOCK_TYPE_REF);
+		recs[i].u.ref.refname = xstrdup("refs/heads/master");
+	}
+
+	for (i = 0; i < N; i++) {
+		struct pq_entry e = {
+			.rec = &recs[i],
+			.index = i,
+		};
+
+		merged_iter_pqueue_add(&pq, &e);
+		merged_iter_pqueue_check(&pq);
+	}
+
+	while (!merged_iter_pqueue_is_empty(pq)) {
+		struct pq_entry top = merged_iter_pqueue_top(pq);
+		struct pq_entry e = merged_iter_pqueue_remove(&pq);
+
+		merged_iter_pqueue_check(&pq);
+		check(pq_entry_equal(&top, &e));
+		for (i = 0; i < pq.len; i++) {
+			check(pq_less(&top, &pq.heap[i]));
+			check_int(top.index, >, i);
+		}
+	}
+
+	for (i = 0; i < N; i++)
+		reftable_record_release(&recs[i]);
+	merged_iter_pqueue_release(&pq);
+}
+
 int cmd_main(int argc, const char *argv[])
 {
 	TEST(test_pq_record(), "pq works with record-based comparison");
 	TEST(test_pq_index(), "pq works with index-based comparison");
+	TEST(test_merged_iter_pqueue_top(), "merged_iter_pqueue_top works");
 
 	return test_done();
 }
-- 
2.45.2.404.g9eaef5822c

Re: [GSoC][PATCH 6/6] t-reftable-pq: add tests for merged_iter_pqueue_top()

[Patrick Steinhardt]

[-- Attachment #1: Type: text/plain, Size: 1330 bytes --]

On Thu, Jun 06, 2024 at 01:10:50PM +0530, Chandra Pratap wrote:
> @@ -59,7 +66,6 @@ static void test_pq_record(void)
>  	merged_iter_pqueue_release(&pq);
>  }
>  
> -
>  static void test_pq_index(void)
>  {
>  	struct merged_iter_pqueue pq = { 0 };

Ah, you drop the newline here. This should probably be part of the
preceding commit.

> @@ -98,10 +106,49 @@ static void test_pq_index(void)
>  	merged_iter_pqueue_release(&pq);
>  }
>  
> +static void test_merged_iter_pqueue_top(void)
> +{
> +	struct merged_iter_pqueue pq = { 0 };
> +	struct reftable_record recs[14];
> +	size_t N = ARRAY_SIZE(recs), i;
> +
> +	for (i = 0; i < N; i++) {
> +		reftable_record_init(&recs[i], BLOCK_TYPE_REF);
> +		recs[i].u.ref.refname = xstrdup("refs/heads/master");
> +	}
> +
> +	for (i = 0; i < N; i++) {
> +		struct pq_entry e = {
> +			.rec = &recs[i],
> +			.index = i,
> +		};
> +
> +		merged_iter_pqueue_add(&pq, &e);
> +		merged_iter_pqueue_check(&pq);
> +	}
> +
> +	while (!merged_iter_pqueue_is_empty(pq)) {
> +		struct pq_entry top = merged_iter_pqueue_top(pq);
> +		struct pq_entry e = merged_iter_pqueue_remove(&pq);
> +
> +		merged_iter_pqueue_check(&pq);
> +		check(pq_entry_equal(&top, &e));

Do we also want to check that `top` is equal to the expected entry in
`recs`?

Patrick

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

[GSoC][PATCH v2 0/6] t: port reftable/pq_test.c to the unit testing

[Chandra Pratap]

In the recent codebase update (commit 8bf6fbd, 2023-12-09), a new unit
testing framework written entirely in C was introduced to the Git project
aimed at simplifying testing and reducing test run times.
Currently, tests for the reftable refs-backend are performed by a custom
testing framework defined by reftable/test_framework.{c, h}. Port
reftable/pq_test.c to the unit testing framework and improve upon
the ported test.

The first patch in the series is preparatory cleanup, the second patch
moves the test to the unit testing framework, and the rest of the patches
improve upon the ported test.

Mentored-by: Patrick Steinhardt <ps@pks.im>
Mentored-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>

---
Changes in v2:
- Change data type of index variable 'i' to 'size_t' from 'int'
- Use correct format specifier for 'size_t' types
- Improve the test for merged_iter_pqueue_top() by asserting equality
  between 'top.rec' and the corresponding record in 'recs' array

CI/PR for v2: https://github.com/gitgitgadget/git/pull/1745

Chandra Pratap (6):
reftable: clean up reftable/pq.c
t: move reftable/pq_test.c to the unit testing framework
t-reftable-pq: make merged_iter_pqueue_check() static
t-reftable-pq: make merged_iter_pqueue_check() callable
t-reftable-pq: add test for index based comparison
t-reftable-pq: add tests for merged_iter_pqueue_top()

Makefile                     |   2 +-
reftable/pq.c                |  18 +++--------
reftable/pq.h                |   1 -
reftable/pq_test.c           |  74 ----------------------------
t/helper/test-reftable.c     |   1 -
t/unit-tests/t-reftable-pq.c | 155 +++++++++++++++++++++++++++++++++++++++++++++
6 files changed, 160 insertions(+), 91 deletions(-)


Range-diff against v1:
1:  f18b610f63 ! 1:  f24dc84877 t: move reftable/pq_test.c to the unit testing framework
    @@ t/unit-tests/t-reftable-pq.c: license that can be found in the LICENSE file or a
      {
     -	int i;
     -	for (i = 1; i < pq.len; i++) {
    -+	for (int i = 1; i < pq.len; i++) {
    - 		int parent = (i - 1) / 2;
    +-		int parent = (i - 1) / 2;
     -
     -		EXPECT(pq_less(&pq.heap[parent], &pq.heap[i]));
    ++	for (size_t i = 1; i < pq.len; i++) {
    ++		size_t parent = (i - 1) / 2;
     +		check(pq_less(&pq.heap[parent], &pq.heap[i]));
      	}
      }
    @@ t/unit-tests/t-reftable-pq.c: license that can be found in the LICENSE file or a
      	for (i = 0; i < N; i++) {
      		struct strbuf refname = STRBUF_INIT;
     -		strbuf_addf(&refname, "%02d", i);
    -+		strbuf_addf(&refname, "%02ld", (long)i);
    ++		strbuf_addf(&refname, "%02"PRIuMAX, (uintmax_t)i);

      		reftable_record_init(&recs[i], BLOCK_TYPE_REF);
      		recs[i].u.ref.refname = strbuf_detach(&refname, NULL);
2:  798e0adfeb ! 2:  ce42fd1288 t-reftable-pq: make merged_iter_pqueue_check() static
    @@ t/unit-tests/t-reftable-pq.c: license that can be found in the LICENSE file or a
     -void merged_iter_pqueue_check(struct merged_iter_pqueue pq)
     +static void merged_iter_pqueue_check(struct merged_iter_pqueue pq)
      {
    - 	for (int i = 1; i < pq.len; i++) {
    - 		int parent = (i - 1) / 2;
    + 	for (size_t i = 1; i < pq.len; i++) {
    + 		size_t parent = (i - 1) / 2;
3:  8412672105 ! 3:  226d72aa6a t-reftable-pq: make merged_iter_pqueue_check() callable by reference
    @@ t/unit-tests/t-reftable-pq.c: license that can be found in the LICENSE file or a
     -static void merged_iter_pqueue_check(struct merged_iter_pqueue pq)
     +static void merged_iter_pqueue_check(const struct merged_iter_pqueue *pq)
      {
    --	for (int i = 1; i < pq.len; i++) {
    -+	for (int i = 1; i < pq->len; i++) {
    - 		int parent = (i - 1) / 2;
    +-	for (size_t i = 1; i < pq.len; i++) {
    ++	for (size_t i = 1; i < pq->len; i++) {
    + 		size_t parent = (i - 1) / 2;
     -		check(pq_less(&pq.heap[parent], &pq.heap[i]));
     +		check(pq_less(&pq->heap[parent], &pq->heap[i]));
      	}
4:  2ef5b8b0b1 ! 4:  00cb440f11 t-reftable-pq: add test for index based comparison
    @@ t/unit-tests/t-reftable-pq.c: static void test_pq(void)
      	merged_iter_pqueue_release(&pq);
      }

    -+
     +static void test_pq_index(void)
     +{
     +	struct merged_iter_pqueue pq = { 0 };
5:  838e67d2a3 ! 5:  dd44486c28 t-reftable-pq: add tests for merged_iter_pqueue_top()
    @@ t/unit-tests/t-reftable-pq.c: static void test_pq_record(void)
      		check(reftable_record_type(e.rec) == BLOCK_TYPE_REF);
      		if (last)
      			check_int(strcmp(last, e.rec->u.ref.refname), <, 0);
    -@@ t/unit-tests/t-reftable-pq.c: static void test_pq_record(void)
    - 	merged_iter_pqueue_release(&pq);
    - }
    -
    --
    - static void test_pq_index(void)
    - {
    - 	struct merged_iter_pqueue pq = { 0 };
     @@ t/unit-tests/t-reftable-pq.c: static void test_pq_index(void)
      	}

    @@ t/unit-tests/t-reftable-pq.c: static void test_pq_index(void)
     +		merged_iter_pqueue_check(&pq);
     +	}
     +
    -+	while (!merged_iter_pqueue_is_empty(pq)) {
    ++	for (i = N - 1; !merged_iter_pqueue_is_empty(pq); i--) {
     +		struct pq_entry top = merged_iter_pqueue_top(pq);
     +		struct pq_entry e = merged_iter_pqueue_remove(&pq);
     +
     +		merged_iter_pqueue_check(&pq);
     +		check(pq_entry_equal(&top, &e));
    -+		for (i = 0; i < pq.len; i++) {
    -+			check(pq_less(&top, &pq.heap[i]));
    -+			check_int(top.index, >, i);
    ++		check(reftable_record_equal(top.rec, &recs[i], GIT_SHA1_RAWSZ));
    ++		for (size_t j = 0; i < pq.len; j++) {
    ++			check(pq_less(&top, &pq.heap[j]));
    ++			check_int(top.index, >, j);
     +		}
     +	}
     +

[GSoC][PATCH v2 1/6] reftable: clean up reftable/pq.c

[Chandra Pratap]

According to Documentation/CodingGuidelines, control-flow statements
with a single line as their body must omit curly braces. Make
reftable/pq.c conform to this guideline. Besides that, remove
unnecessary newlines and variable assignment.

Mentored-by: Patrick Steinhardt <ps@pks.im>
Mentored-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
---
 reftable/pq.c | 18 ++++--------------
 1 file changed, 4 insertions(+), 14 deletions(-)

diff --git a/reftable/pq.c b/reftable/pq.c
index 7fb45d8c60..0401c47068 100644
--- a/reftable/pq.c
+++ b/reftable/pq.c
@@ -27,22 +27,16 @@ struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq)
 	pq->heap[0] = pq->heap[pq->len - 1];
 	pq->len--;
 
-	i = 0;
 	while (i < pq->len) {
 		int min = i;
 		int j = 2 * i + 1;
 		int k = 2 * i + 2;
-		if (j < pq->len && pq_less(&pq->heap[j], &pq->heap[i])) {
+		if (j < pq->len && pq_less(&pq->heap[j], &pq->heap[i]))
 			min = j;
-		}
-		if (k < pq->len && pq_less(&pq->heap[k], &pq->heap[min])) {
+		if (k < pq->len && pq_less(&pq->heap[k], &pq->heap[min]))
 			min = k;
-		}
-
-		if (min == i) {
+		if (min == i)
 			break;
-		}
-
 		SWAP(pq->heap[i], pq->heap[min]);
 		i = min;
 	}
@@ -53,19 +47,15 @@ struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq)
 void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry *e)
 {
 	int i = 0;
-
 	REFTABLE_ALLOC_GROW(pq->heap, pq->len + 1, pq->cap);
 	pq->heap[pq->len++] = *e;
 
 	i = pq->len - 1;
 	while (i > 0) {
 		int j = (i - 1) / 2;
-		if (pq_less(&pq->heap[j], &pq->heap[i])) {
+		if (pq_less(&pq->heap[j], &pq->heap[i]))
 			break;
-		}
-
 		SWAP(pq->heap[j], pq->heap[i]);
-
 		i = j;
 	}
 }
-- 
2.45.2.404.g9eaef5822c

Re: [GSoC][PATCH v2 1/6] reftable: clean up reftable/pq.c

[Patrick Steinhardt]

[-- Attachment #1: Type: text/plain, Size: 2387 bytes --]

On Thu, Jun 06, 2024 at 08:53:37PM +0530, Chandra Pratap wrote:
> According to Documentation/CodingGuidelines, control-flow statements
> with a single line as their body must omit curly braces. Make
> reftable/pq.c conform to this guideline. Besides that, remove
> unnecessary newlines and variable assignment.
> 
> Mentored-by: Patrick Steinhardt <ps@pks.im>
> Mentored-by: Christian Couder <chriscool@tuxfamily.org>
> Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
> ---
>  reftable/pq.c | 18 ++++--------------
>  1 file changed, 4 insertions(+), 14 deletions(-)
> 
> diff --git a/reftable/pq.c b/reftable/pq.c
> index 7fb45d8c60..0401c47068 100644
> --- a/reftable/pq.c
> +++ b/reftable/pq.c
> @@ -27,22 +27,16 @@ struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq)
>  	pq->heap[0] = pq->heap[pq->len - 1];
>  	pq->len--;
>  
> -	i = 0;
>  	while (i < pq->len) {
>  		int min = i;
>  		int j = 2 * i + 1;
>  		int k = 2 * i + 2;
> -		if (j < pq->len && pq_less(&pq->heap[j], &pq->heap[i])) {
> +		if (j < pq->len && pq_less(&pq->heap[j], &pq->heap[i]))
>  			min = j;
> -		}
> -		if (k < pq->len && pq_less(&pq->heap[k], &pq->heap[min])) {
> +		if (k < pq->len && pq_less(&pq->heap[k], &pq->heap[min]))
>  			min = k;
> -		}
> -
> -		if (min == i) {
> +		if (min == i)
>  			break;
> -		}
> -
>  		SWAP(pq->heap[i], pq->heap[min]);
>  		i = min;
>  	}
> @@ -53,19 +47,15 @@ struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq)
>  void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry *e)
>  {
>  	int i = 0;
> -

Nit: I think this newline is helpful as it delimits the variable
declarations from the actual code.

I wonder whether we should also change the type of `i` to `size_t` while
at it, as `pq->len` is of type `size_t, as well (and further up in the
other test). It does mean that we have to add an explicit check whether
`pq->len == 0`, but that isn't all that bad.

In any case, if we want to do such a change, it should probably be in a
separate commit.

>  	REFTABLE_ALLOC_GROW(pq->heap, pq->len + 1, pq->cap);
>  	pq->heap[pq->len++] = *e;
>  
>  	i = pq->len - 1;
>  	while (i > 0) {
>  		int j = (i - 1) / 2;

The type of `j` is wrong, as well.

Other than that this patch series looks good to me, thanks.

Patrick

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

[GSoC][PATCH v2 2/6] t: move reftable/pq_test.c to the unit testing framework

[Chandra Pratap]

reftable/pq_test.c exercises a priority queue defined by
reftable/pq.{c, h}. Migrate reftable/pq_test.c to the unit
testing framework. Migration involves refactoring the tests
to use the unit testing framework instead of reftable's test
framework.

Mentored-by: Patrick Steinhardt <ps@pks.im>
Mentored-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
---
 Makefile                                      |  2 +-
 t/helper/test-reftable.c                      |  1 -
 .../pq_test.c => t/unit-tests/t-reftable-pq.c | 37 ++++++++-----------
 3 files changed, 16 insertions(+), 24 deletions(-)
 rename reftable/pq_test.c => t/unit-tests/t-reftable-pq.c (62%)

diff --git a/Makefile b/Makefile
index 59d98ba688..1cabe4cc69 100644
--- a/Makefile
+++ b/Makefile
@@ -1336,6 +1336,7 @@ THIRD_PARTY_SOURCES += sha1dc/%
 UNIT_TEST_PROGRAMS += t-ctype
 UNIT_TEST_PROGRAMS += t-mem-pool
 UNIT_TEST_PROGRAMS += t-prio-queue
+UNIT_TEST_PROGRAMS += t-reftable-pq
 UNIT_TEST_PROGRAMS += t-strbuf
 UNIT_TEST_PROGRAMS += t-strcmp-offset
 UNIT_TEST_PROGRAMS += t-trailer
@@ -2675,7 +2676,6 @@ REFTABLE_TEST_OBJS += reftable/basics_test.o
 REFTABLE_TEST_OBJS += reftable/block_test.o
 REFTABLE_TEST_OBJS += reftable/dump.o
 REFTABLE_TEST_OBJS += reftable/merged_test.o
-REFTABLE_TEST_OBJS += reftable/pq_test.o
 REFTABLE_TEST_OBJS += reftable/record_test.o
 REFTABLE_TEST_OBJS += reftable/readwrite_test.o
 REFTABLE_TEST_OBJS += reftable/stack_test.o
diff --git a/t/helper/test-reftable.c b/t/helper/test-reftable.c
index bae731669c..86a2b0f91a 100644
--- a/t/helper/test-reftable.c
+++ b/t/helper/test-reftable.c
@@ -9,7 +9,6 @@ int cmd__reftable(int argc, const char **argv)
 	record_test_main(argc, argv);
 	block_test_main(argc, argv);
 	tree_test_main(argc, argv);
-	pq_test_main(argc, argv);
 	readwrite_test_main(argc, argv);
 	merged_test_main(argc, argv);
 	stack_test_main(argc, argv);
diff --git a/reftable/pq_test.c b/t/unit-tests/t-reftable-pq.c
similarity index 62%
rename from reftable/pq_test.c
rename to t/unit-tests/t-reftable-pq.c
index b7d3c80cc7..a47a9473f3 100644
--- a/reftable/pq_test.c
+++ b/t/unit-tests/t-reftable-pq.c
@@ -6,35 +6,28 @@ license that can be found in the LICENSE file or at
 https://developers.google.com/open-source/licenses/bsd
 */
 
-#include "system.h"
-
-#include "basics.h"
-#include "constants.h"
-#include "pq.h"
-#include "record.h"
-#include "reftable-tests.h"
-#include "test_framework.h"
+#include "test-lib.h"
+#include "reftable/constants.h"
+#include "reftable/pq.h"
 
 void merged_iter_pqueue_check(struct merged_iter_pqueue pq)
 {
-	int i;
-	for (i = 1; i < pq.len; i++) {
-		int parent = (i - 1) / 2;
-
-		EXPECT(pq_less(&pq.heap[parent], &pq.heap[i]));
+	for (size_t i = 1; i < pq.len; i++) {
+		size_t parent = (i - 1) / 2;
+		check(pq_less(&pq.heap[parent], &pq.heap[i]));
 	}
 }
 
 static void test_pq(void)
 {
-	struct merged_iter_pqueue pq = { NULL };
+	struct merged_iter_pqueue pq = { 0 };
 	struct reftable_record recs[54];
-	int N = ARRAY_SIZE(recs) - 1, i;
+	size_t N = ARRAY_SIZE(recs) - 1, i;
 	char *last = NULL;
 
 	for (i = 0; i < N; i++) {
 		struct strbuf refname = STRBUF_INIT;
-		strbuf_addf(&refname, "%02d", i);
+		strbuf_addf(&refname, "%02"PRIuMAX, (uintmax_t)i);
 
 		reftable_record_init(&recs[i], BLOCK_TYPE_REF);
 		recs[i].u.ref.refname = strbuf_detach(&refname, NULL);
@@ -48,7 +41,6 @@ static void test_pq(void)
 
 		merged_iter_pqueue_add(&pq, &e);
 		merged_iter_pqueue_check(pq);
-
 		i = (i * 7) % N;
 	} while (i != 1);
 
@@ -56,9 +48,9 @@ static void test_pq(void)
 		struct pq_entry e = merged_iter_pqueue_remove(&pq);
 		merged_iter_pqueue_check(pq);
 
-		EXPECT(reftable_record_type(e.rec) == BLOCK_TYPE_REF);
+		check(reftable_record_type(e.rec) == BLOCK_TYPE_REF);
 		if (last)
-			EXPECT(strcmp(last, e.rec->u.ref.refname) < 0);
+			check_int(strcmp(last, e.rec->u.ref.refname), <, 0);
 		last = e.rec->u.ref.refname;
 	}
 
@@ -67,8 +59,9 @@ static void test_pq(void)
 	merged_iter_pqueue_release(&pq);
 }
 
-int pq_test_main(int argc, const char *argv[])
+int cmd_main(int argc, const char *argv[])
 {
-	RUN_TEST(test_pq);
-	return 0;
+	TEST(test_pq(), "pq works");
+
+	return test_done();
 }
-- 
2.45.2.404.g9eaef5822c

[GSoC][PATCH v2 3/6] t-reftable-pq: make merged_iter_pqueue_check() static

[Chandra Pratap]

merged_iter_pqueue_check() is a function previously defined in
reftable/pq_test.c (now t/unit-tests/t-reftable-pq.c) and used in
the testing of a priority queue as defined by reftable/pq.{c, h}.
As such, this function is only called by reftable/pq_test.c and it
makes little sense to expose it to non-testing code via reftable/pq.h.

Hence, make this function static and remove its prototype from
reftable/pq.h.

Mentored-by: Patrick Steinhardt <ps@pks.im>
Mentored-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
---
 reftable/pq.h                | 1 -
 t/unit-tests/t-reftable-pq.c | 2 +-
 2 files changed, 1 insertion(+), 2 deletions(-)

diff --git a/reftable/pq.h b/reftable/pq.h
index f796c23179..707bd26767 100644
--- a/reftable/pq.h
+++ b/reftable/pq.h
@@ -22,7 +22,6 @@ struct merged_iter_pqueue {
 	size_t cap;
 };
 
-void merged_iter_pqueue_check(struct merged_iter_pqueue pq);
 struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq);
 void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry *e);
 void merged_iter_pqueue_release(struct merged_iter_pqueue *pq);
diff --git a/t/unit-tests/t-reftable-pq.c b/t/unit-tests/t-reftable-pq.c
index a47a9473f3..7d151f8582 100644
--- a/t/unit-tests/t-reftable-pq.c
+++ b/t/unit-tests/t-reftable-pq.c
@@ -10,7 +10,7 @@ license that can be found in the LICENSE file or at
 #include "reftable/constants.h"
 #include "reftable/pq.h"
 
-void merged_iter_pqueue_check(struct merged_iter_pqueue pq)
+static void merged_iter_pqueue_check(struct merged_iter_pqueue pq)
 {
 	for (size_t i = 1; i < pq.len; i++) {
 		size_t parent = (i - 1) / 2;
-- 
2.45.2.404.g9eaef5822c

[GSoC][PATCH v2 4/6] t-reftable-pq: make merged_iter_pqueue_check() callable by reference

[Chandra Pratap]

merged_iter_pqueue_check() checks the validity of a priority queue
represented by a merged_iter_pqueue struct by asserting the
parent-child relation in the struct's heap. Explicity passing a
struct to this function means a copy of the entire struct is created,
which is inefficient.

Make the function accept a pointer to the struct instead. This is
safe to do since the function doesn't modify the struct in any way.
Make the function parameter 'const' to assert immutability.

Mentored-by: Patrick Steinhardt <ps@pks.im>
Mentored-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
---
 t/unit-tests/t-reftable-pq.c | 10 +++++-----
 1 file changed, 5 insertions(+), 5 deletions(-)

diff --git a/t/unit-tests/t-reftable-pq.c b/t/unit-tests/t-reftable-pq.c
index 7d151f8582..774c4194e5 100644
--- a/t/unit-tests/t-reftable-pq.c
+++ b/t/unit-tests/t-reftable-pq.c
@@ -10,11 +10,11 @@ license that can be found in the LICENSE file or at
 #include "reftable/constants.h"
 #include "reftable/pq.h"
 
-static void merged_iter_pqueue_check(struct merged_iter_pqueue pq)
+static void merged_iter_pqueue_check(const struct merged_iter_pqueue *pq)
 {
-	for (size_t i = 1; i < pq.len; i++) {
+	for (size_t i = 1; i < pq->len; i++) {
 		size_t parent = (i - 1) / 2;
-		check(pq_less(&pq.heap[parent], &pq.heap[i]));
+		check(pq_less(&pq->heap[parent], &pq->heap[i]));
 	}
 }
 
@@ -40,13 +40,13 @@ static void test_pq(void)
 		};
 
 		merged_iter_pqueue_add(&pq, &e);
-		merged_iter_pqueue_check(pq);
+		merged_iter_pqueue_check(&pq);
 		i = (i * 7) % N;
 	} while (i != 1);
 
 	while (!merged_iter_pqueue_is_empty(pq)) {
 		struct pq_entry e = merged_iter_pqueue_remove(&pq);
-		merged_iter_pqueue_check(pq);
+		merged_iter_pqueue_check(&pq);
 
 		check(reftable_record_type(e.rec) == BLOCK_TYPE_REF);
 		if (last)
-- 
2.45.2.404.g9eaef5822c

[GSoC][PATCH v2 5/6] t-reftable-pq: add test for index based comparison

[Chandra Pratap]

When comparing two entries, the priority queue as defined by
reftable/pq.{c, h} first compares the entries on the basis of
their ref-record's keys. If the keys turn out to be equal, the
comparison is then made on the basis of their update indices
(which are never equal).

In the current testing setup, only the case for comparison on
the basis of ref-record's keys is exercised. Add a test for
index-based comparison as well. Rename the existing test to
reflect its nature of only testing record-based comparison.

Mentored-by: Patrick Steinhardt <ps@pks.im>
Mentored-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
---
 t/unit-tests/t-reftable-pq.c | 43 ++++++++++++++++++++++++++++++++++--
 1 file changed, 41 insertions(+), 2 deletions(-)

diff --git a/t/unit-tests/t-reftable-pq.c b/t/unit-tests/t-reftable-pq.c
index 774c4194e5..e114a8cb0f 100644
--- a/t/unit-tests/t-reftable-pq.c
+++ b/t/unit-tests/t-reftable-pq.c
@@ -18,7 +18,7 @@ static void merged_iter_pqueue_check(const struct merged_iter_pqueue *pq)
 	}
 }
 
-static void test_pq(void)
+static void test_pq_record(void)
 {
 	struct merged_iter_pqueue pq = { 0 };
 	struct reftable_record recs[54];
@@ -59,9 +59,48 @@ static void test_pq(void)
 	merged_iter_pqueue_release(&pq);
 }
 
+static void test_pq_index(void)
+{
+	struct merged_iter_pqueue pq = { 0 };
+	struct reftable_record recs[14];
+	char *last = NULL;
+	size_t N = ARRAY_SIZE(recs), i;
+
+	for (i = 0; i < N; i++) {
+		reftable_record_init(&recs[i], BLOCK_TYPE_REF);
+		recs[i].u.ref.refname = xstrdup("refs/heads/master");
+	}
+
+	for (i = 0; i < N; i++) {
+		struct pq_entry e = {
+			.rec = &recs[i],
+			.index = i,
+		};
+
+		merged_iter_pqueue_add(&pq, &e);
+		merged_iter_pqueue_check(&pq);
+	}
+
+	for (i = N - 1; !merged_iter_pqueue_is_empty(pq); i--) {
+		struct pq_entry e = merged_iter_pqueue_remove(&pq);
+		merged_iter_pqueue_check(&pq);
+
+		check(reftable_record_type(e.rec) == BLOCK_TYPE_REF);
+		check_int(e.index, ==, i);
+		if (last)
+			check_str(last, e.rec->u.ref.refname);
+		last = e.rec->u.ref.refname;
+	}
+
+	for (i = 0; i < N; i++)
+		reftable_record_release(&recs[i]);
+	merged_iter_pqueue_release(&pq);
+}
+
 int cmd_main(int argc, const char *argv[])
 {
-	TEST(test_pq(), "pq works");
+	TEST(test_pq_record(), "pq works with record-based comparison");
+	TEST(test_pq_index(), "pq works with index-based comparison");
 
 	return test_done();
 }
-- 
2.45.2.404.g9eaef5822c

[GSoC][PATCH v2 6/6] t-reftable-pq: add tests for merged_iter_pqueue_top()

[Chandra Pratap]

merged_iter_pqueue_top() as defined by reftable/pq.{c, h} returns
the element at the top of a priority-queue's heap without removing
it. Since there are no tests for this function in the existing
setup, add tests for the same.

Mentored-by: Patrick Steinhardt <ps@pks.im>
Mentored-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
---
 t/unit-tests/t-reftable-pq.c | 49 ++++++++++++++++++++++++++++++++++++
 1 file changed, 49 insertions(+)

diff --git a/t/unit-tests/t-reftable-pq.c b/t/unit-tests/t-reftable-pq.c
index e114a8cb0f..0e93cc97b1 100644
--- a/t/unit-tests/t-reftable-pq.c
+++ b/t/unit-tests/t-reftable-pq.c
@@ -18,6 +18,11 @@ static void merged_iter_pqueue_check(const struct merged_iter_pqueue *pq)
 	}
 }
 
+static int pq_entry_equal(struct pq_entry *a, struct pq_entry *b)
+{
+	return !reftable_record_cmp(a->rec, b->rec) && (a->index == b->index);
+}
+
 static void test_pq_record(void)
 {
 	struct merged_iter_pqueue pq = { 0 };
@@ -45,9 +50,11 @@ static void test_pq_record(void)
 	} while (i != 1);
 
 	while (!merged_iter_pqueue_is_empty(pq)) {
+		struct pq_entry top = merged_iter_pqueue_top(pq);
 		struct pq_entry e = merged_iter_pqueue_remove(&pq);
 		merged_iter_pqueue_check(&pq);
 
+		check(pq_entry_equal(&top, &e));
 		check(reftable_record_type(e.rec) == BLOCK_TYPE_REF);
 		if (last)
 			check_int(strcmp(last, e.rec->u.ref.refname), <, 0);
@@ -82,9 +89,11 @@ static void test_pq_index(void)
 	}
 
 	for (i = N - 1; !merged_iter_pqueue_is_empty(pq); i--) {
+		struct pq_entry top = merged_iter_pqueue_top(pq);
 		struct pq_entry e = merged_iter_pqueue_remove(&pq);
 		merged_iter_pqueue_check(&pq);
 
+		check(pq_entry_equal(&top, &e));
 		check(reftable_record_type(e.rec) == BLOCK_TYPE_REF);
 		check_int(e.index, ==, i);
 		if (last)
@@ -97,10 +106,50 @@ static void test_pq_index(void)
 	merged_iter_pqueue_release(&pq);
 }
 
+static void test_merged_iter_pqueue_top(void)
+{
+	struct merged_iter_pqueue pq = { 0 };
+	struct reftable_record recs[14];
+	size_t N = ARRAY_SIZE(recs), i;
+
+	for (i = 0; i < N; i++) {
+		reftable_record_init(&recs[i], BLOCK_TYPE_REF);
+		recs[i].u.ref.refname = xstrdup("refs/heads/master");
+	}
+
+	for (i = 0; i < N; i++) {
+		struct pq_entry e = {
+			.rec = &recs[i],
+			.index = i,
+		};
+
+		merged_iter_pqueue_add(&pq, &e);
+		merged_iter_pqueue_check(&pq);
+	}
+
+	for (i = N - 1; !merged_iter_pqueue_is_empty(pq); i--) {
+		struct pq_entry top = merged_iter_pqueue_top(pq);
+		struct pq_entry e = merged_iter_pqueue_remove(&pq);
+
+		merged_iter_pqueue_check(&pq);
+		check(pq_entry_equal(&top, &e));
+		check(reftable_record_equal(top.rec, &recs[i], GIT_SHA1_RAWSZ));
+		for (size_t j = 0; i < pq.len; j++) {
+			check(pq_less(&top, &pq.heap[j]));
+			check_int(top.index, >, j);
+		}
+	}
+
+	for (i = 0; i < N; i++)
+		reftable_record_release(&recs[i]);
+	merged_iter_pqueue_release(&pq);
+}
+
 int cmd_main(int argc, const char *argv[])
 {
 	TEST(test_pq_record(), "pq works with record-based comparison");
 	TEST(test_pq_index(), "pq works with index-based comparison");
+	TEST(test_merged_iter_pqueue_top(), "merged_iter_pqueue_top works");
 
 	return test_done();
 }
-- 
2.45.2.404.g9eaef5822c

[GSoC][PATCH v3 0/7] t: port reftable/pq_test.c to the unit testing framework

[Chandra Pratap]

In the recent codebase update (commit 8bf6fbd, 2023-12-09), a new unit
testing framework written entirely in C was introduced to the Git project
aimed at simplifying testing and reducing test run times.
Currently, tests for the reftable refs-backend are performed by a custom
testing framework defined by reftable/test_framework.{c, h}. Port
reftable/pq_test.c to the unit testing framework and improve upon
the ported test.

The first two patches in the series are preparatory cleanup, the third patch
moves the test to the unit testing framework, and the rest of the patches
improve upon the ported test.

Mentored-by: Patrick Steinhardt <ps@pks.im>
Mentored-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>

---
Changes in v3:
- Add another cleanup patch for reftable/pq.c
- Change the commit title of the first patch
- Re-introduce a lost newline in the first patch

CI/PR for v3: https://github.com/gitgitgadget/git/pull/1745

Chandra Pratap(7):
reftable: remove unncessary curly braces in reftable/pq.c
reftable: change the type of array indices to 'size_t' in
t: move reftable/pq_test.c to the unit testing framework
t-reftable-pq: make merged_iter_pqueue_check() static
t-reftable-pq: make merged_iter_pqueue_check() callable
t-reftable-pq: add test for index based comparison
t-reftable-pq: add tests for merged_iter_pqueue_top()

Makefile                     |   2 +-
reftable/pq.c                |  29 +++--------
reftable/pq.h                |   1 -
reftable/pq_test.c           |  74 ----------------------------
t/helper/test-reftable.c     |   1 -
t/unit-tests/t-reftable-pq.c | 155 +++++++++++++++++++++++++++++++++++++++++++++
6 files changed, 166 insertions(+), 96 deletions(-)

Range-diff against v2:
1:  9ac1035c07 ! 1:  d3c5605ea2 reftable: clean up reftable/pq.c
    @@ Metadata
     Author: Chandra Pratap <chandrapratap3519@gmail.com>
     
      ## Commit message ##
    -    reftable: clean up reftable/pq.c
    +    reftable: remove unncessary curly braces in reftable/pq.c
     
         According to Documentation/CodingGuidelines, control-flow statements
         with a single line as their body must omit curly braces. Make
    @@ reftable/pq.c: struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pque
      		SWAP(pq->heap[i], pq->heap[min]);
      		i = min;
      	}
    -@@ reftable/pq.c: struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq)
    - void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry *e)
    - {
    - 	int i = 0;
    --
    - 	REFTABLE_ALLOC_GROW(pq->heap, pq->len + 1, pq->cap);
    - 	pq->heap[pq->len++] = *e;
    - 
    +@@ reftable/pq.c: void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry
      	i = pq->len - 1;
      	while (i > 0) {
      		int j = (i - 1) / 2;
-:  ---------- > 2:  1873fb02ce reftable: change the type of array indices to 'size_t' in reftable/pq.c
2:  f24dc84877 = 3:  3cccf8266a t: move reftable/pq_test.c to the unit testing framework
3:  ce42fd1288 = 4:  4b63849694 t-reftable-pq: make merged_iter_pqueue_check() static
4:  226d72aa6a = 5:  3698a7189f t-reftable-pq: make merged_iter_pqueue_check() callable by reference
5:  00cb440f11 = 6:  d58c8f709e t-reftable-pq: add test for index based comparison
6:  dd44486c28 = 7:  69521f0ff7 t-reftable-pq: add tests for merged_iter_pqueue_top()

[PATCH v3 1/7] reftable: remove unncessary curly braces in reftable/pq.c

[Chandra Pratap]

According to Documentation/CodingGuidelines, control-flow statements
with a single line as their body must omit curly braces. Make
reftable/pq.c conform to this guideline. Besides that, remove
unnecessary newlines and variable assignment.

Mentored-by: Patrick Steinhardt <ps@pks.im>
Mentored-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
---
 reftable/pq.c | 17 ++++-------------
 1 file changed, 4 insertions(+), 13 deletions(-)

diff --git a/reftable/pq.c b/reftable/pq.c
index 7fb45d8c60..1a180c5fa6 100644
--- a/reftable/pq.c
+++ b/reftable/pq.c
@@ -27,22 +27,16 @@ struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq)
 	pq->heap[0] = pq->heap[pq->len - 1];
 	pq->len--;
 
-	i = 0;
 	while (i < pq->len) {
 		int min = i;
 		int j = 2 * i + 1;
 		int k = 2 * i + 2;
-		if (j < pq->len && pq_less(&pq->heap[j], &pq->heap[i])) {
+		if (j < pq->len && pq_less(&pq->heap[j], &pq->heap[i]))
 			min = j;
-		}
-		if (k < pq->len && pq_less(&pq->heap[k], &pq->heap[min])) {
+		if (k < pq->len && pq_less(&pq->heap[k], &pq->heap[min]))
 			min = k;
-		}
-
-		if (min == i) {
+		if (min == i)
 			break;
-		}
-
 		SWAP(pq->heap[i], pq->heap[min]);
 		i = min;
 	}
@@ -60,12 +54,9 @@ void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry
 	i = pq->len - 1;
 	while (i > 0) {
 		int j = (i - 1) / 2;
-		if (pq_less(&pq->heap[j], &pq->heap[i])) {
+		if (pq_less(&pq->heap[j], &pq->heap[i]))
 			break;
-		}
-
 		SWAP(pq->heap[j], pq->heap[i]);
-
 		i = j;
 	}
 }
-- 
2.45.2.404.g9eaef5822c

[PATCH v3 2/7] reftable: change the type of array indices to 'size_t' in reftable/pq.c

[Chandra Pratap]

Mentored-by: Patrick Steinhardt <ps@pks.im>
Mentored-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
---
 reftable/pq.c | 12 ++++++------
 1 file changed, 6 insertions(+), 6 deletions(-)

diff --git a/reftable/pq.c b/reftable/pq.c
index 1a180c5fa6..2b5b7d1c0e 100644
--- a/reftable/pq.c
+++ b/reftable/pq.c
@@ -22,15 +22,15 @@ int pq_less(struct pq_entry *a, struct pq_entry *b)
 
 struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq)
 {
-	int i = 0;
+	size_t i = 0;
 	struct pq_entry e = pq->heap[0];
 	pq->heap[0] = pq->heap[pq->len - 1];
 	pq->len--;
 
 	while (i < pq->len) {
-		int min = i;
-		int j = 2 * i + 1;
-		int k = 2 * i + 2;
+		size_t min = i;
+		size_t j = 2 * i + 1;
+		size_t k = 2 * i + 2;
 		if (j < pq->len && pq_less(&pq->heap[j], &pq->heap[i]))
 			min = j;
 		if (k < pq->len && pq_less(&pq->heap[k], &pq->heap[min]))
@@ -46,14 +46,14 @@ struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq)
 
 void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry *e)
 {
-	int i = 0;
+	size_t i = 0;
 
 	REFTABLE_ALLOC_GROW(pq->heap, pq->len + 1, pq->cap);
 	pq->heap[pq->len++] = *e;
 
 	i = pq->len - 1;
 	while (i > 0) {
-		int j = (i - 1) / 2;
+		size_t j = (i - 1) / 2;
 		if (pq_less(&pq->heap[j], &pq->heap[i]))
 			break;
 		SWAP(pq->heap[j], pq->heap[i]);
-- 
2.45.2.404.g9eaef5822c

Re: [PATCH v3 2/7] reftable: change the type of array indices to 'size_t' in reftable/pq.c

[Patrick Steinhardt]

[-- Attachment #1: Type: text/plain, Size: 1937 bytes --]

On Tue, Jun 11, 2024 at 01:49:19PM +0530, Chandra Pratap wrote:

This commit is missing a commit message. The important information that
the reader needs to understand this change is that `pq->len` is of type
`size_t`, as well. So that information should probably go in here.

Other than that this patch series looks good to me, thanks!

Patrick

> Mentored-by: Patrick Steinhardt <ps@pks.im>
> Mentored-by: Christian Couder <chriscool@tuxfamily.org>
> Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
> ---
>  reftable/pq.c | 12 ++++++------
>  1 file changed, 6 insertions(+), 6 deletions(-)
> 
> diff --git a/reftable/pq.c b/reftable/pq.c
> index 1a180c5fa6..2b5b7d1c0e 100644
> --- a/reftable/pq.c
> +++ b/reftable/pq.c
> @@ -22,15 +22,15 @@ int pq_less(struct pq_entry *a, struct pq_entry *b)
>  
>  struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq)
>  {
> -	int i = 0;
> +	size_t i = 0;
>  	struct pq_entry e = pq->heap[0];
>  	pq->heap[0] = pq->heap[pq->len - 1];
>  	pq->len--;
>  
>  	while (i < pq->len) {
> -		int min = i;
> -		int j = 2 * i + 1;
> -		int k = 2 * i + 2;
> +		size_t min = i;
> +		size_t j = 2 * i + 1;
> +		size_t k = 2 * i + 2;
>  		if (j < pq->len && pq_less(&pq->heap[j], &pq->heap[i]))
>  			min = j;
>  		if (k < pq->len && pq_less(&pq->heap[k], &pq->heap[min]))
> @@ -46,14 +46,14 @@ struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq)
>  
>  void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry *e)
>  {
> -	int i = 0;
> +	size_t i = 0;
>  
>  	REFTABLE_ALLOC_GROW(pq->heap, pq->len + 1, pq->cap);
>  	pq->heap[pq->len++] = *e;
>  
>  	i = pq->len - 1;
>  	while (i > 0) {
> -		int j = (i - 1) / 2;
> +		size_t j = (i - 1) / 2;
>  		if (pq_less(&pq->heap[j], &pq->heap[i]))
>  			break;
>  		SWAP(pq->heap[j], pq->heap[i]);
> -- 
> 2.45.2.404.g9eaef5822c
> 

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

[PATCH v3 3/7] t: move reftable/pq_test.c to the unit testing framework

[Chandra Pratap]

reftable/pq_test.c exercises a priority queue defined by
reftable/pq.{c, h}. Migrate reftable/pq_test.c to the unit
testing framework. Migration involves refactoring the tests
to use the unit testing framework instead of reftable's test
framework.

Mentored-by: Patrick Steinhardt <ps@pks.im>
Mentored-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
---
 Makefile                                      |  2 +-
 t/helper/test-reftable.c                      |  1 -
 .../pq_test.c => t/unit-tests/t-reftable-pq.c | 37 ++++++++-----------
 3 files changed, 16 insertions(+), 24 deletions(-)
 rename reftable/pq_test.c => t/unit-tests/t-reftable-pq.c (62%)

diff --git a/Makefile b/Makefile
index 59d98ba688..1cabe4cc69 100644
--- a/Makefile
+++ b/Makefile
@@ -1336,6 +1336,7 @@ THIRD_PARTY_SOURCES += sha1dc/%
 UNIT_TEST_PROGRAMS += t-ctype
 UNIT_TEST_PROGRAMS += t-mem-pool
 UNIT_TEST_PROGRAMS += t-prio-queue
+UNIT_TEST_PROGRAMS += t-reftable-pq
 UNIT_TEST_PROGRAMS += t-strbuf
 UNIT_TEST_PROGRAMS += t-strcmp-offset
 UNIT_TEST_PROGRAMS += t-trailer
@@ -2675,7 +2676,6 @@ REFTABLE_TEST_OBJS += reftable/basics_test.o
 REFTABLE_TEST_OBJS += reftable/block_test.o
 REFTABLE_TEST_OBJS += reftable/dump.o
 REFTABLE_TEST_OBJS += reftable/merged_test.o
-REFTABLE_TEST_OBJS += reftable/pq_test.o
 REFTABLE_TEST_OBJS += reftable/record_test.o
 REFTABLE_TEST_OBJS += reftable/readwrite_test.o
 REFTABLE_TEST_OBJS += reftable/stack_test.o
diff --git a/t/helper/test-reftable.c b/t/helper/test-reftable.c
index bae731669c..86a2b0f91a 100644
--- a/t/helper/test-reftable.c
+++ b/t/helper/test-reftable.c
@@ -9,7 +9,6 @@ int cmd__reftable(int argc, const char **argv)
 	record_test_main(argc, argv);
 	block_test_main(argc, argv);
 	tree_test_main(argc, argv);
-	pq_test_main(argc, argv);
 	readwrite_test_main(argc, argv);
 	merged_test_main(argc, argv);
 	stack_test_main(argc, argv);
diff --git a/reftable/pq_test.c b/t/unit-tests/t-reftable-pq.c
similarity index 62%
rename from reftable/pq_test.c
rename to t/unit-tests/t-reftable-pq.c
index b7d3c80cc7..a47a9473f3 100644
--- a/reftable/pq_test.c
+++ b/t/unit-tests/t-reftable-pq.c
@@ -6,35 +6,28 @@ license that can be found in the LICENSE file or at
 https://developers.google.com/open-source/licenses/bsd
 */
 
-#include "system.h"
-
-#include "basics.h"
-#include "constants.h"
-#include "pq.h"
-#include "record.h"
-#include "reftable-tests.h"
-#include "test_framework.h"
+#include "test-lib.h"
+#include "reftable/constants.h"
+#include "reftable/pq.h"
 
 void merged_iter_pqueue_check(struct merged_iter_pqueue pq)
 {
-	int i;
-	for (i = 1; i < pq.len; i++) {
-		int parent = (i - 1) / 2;
-
-		EXPECT(pq_less(&pq.heap[parent], &pq.heap[i]));
+	for (size_t i = 1; i < pq.len; i++) {
+		size_t parent = (i - 1) / 2;
+		check(pq_less(&pq.heap[parent], &pq.heap[i]));
 	}
 }
 
 static void test_pq(void)
 {
-	struct merged_iter_pqueue pq = { NULL };
+	struct merged_iter_pqueue pq = { 0 };
 	struct reftable_record recs[54];
-	int N = ARRAY_SIZE(recs) - 1, i;
+	size_t N = ARRAY_SIZE(recs) - 1, i;
 	char *last = NULL;
 
 	for (i = 0; i < N; i++) {
 		struct strbuf refname = STRBUF_INIT;
-		strbuf_addf(&refname, "%02d", i);
+		strbuf_addf(&refname, "%02"PRIuMAX, (uintmax_t)i);
 
 		reftable_record_init(&recs[i], BLOCK_TYPE_REF);
 		recs[i].u.ref.refname = strbuf_detach(&refname, NULL);
@@ -48,7 +41,6 @@ static void test_pq(void)
 
 		merged_iter_pqueue_add(&pq, &e);
 		merged_iter_pqueue_check(pq);
-
 		i = (i * 7) % N;
 	} while (i != 1);
 
@@ -56,9 +48,9 @@ static void test_pq(void)
 		struct pq_entry e = merged_iter_pqueue_remove(&pq);
 		merged_iter_pqueue_check(pq);
 
-		EXPECT(reftable_record_type(e.rec) == BLOCK_TYPE_REF);
+		check(reftable_record_type(e.rec) == BLOCK_TYPE_REF);
 		if (last)
-			EXPECT(strcmp(last, e.rec->u.ref.refname) < 0);
+			check_int(strcmp(last, e.rec->u.ref.refname), <, 0);
 		last = e.rec->u.ref.refname;
 	}
 
@@ -67,8 +59,9 @@ static void test_pq(void)
 	merged_iter_pqueue_release(&pq);
 }
 
-int pq_test_main(int argc, const char *argv[])
+int cmd_main(int argc, const char *argv[])
 {
-	RUN_TEST(test_pq);
-	return 0;
+	TEST(test_pq(), "pq works");
+
+	return test_done();
 }
-- 
2.45.2.404.g9eaef5822c

[PATCH v3 4/7] t-reftable-pq: make merged_iter_pqueue_check() static

[Chandra Pratap]

merged_iter_pqueue_check() is a function previously defined in
reftable/pq_test.c (now t/unit-tests/t-reftable-pq.c) and used in
the testing of a priority queue as defined by reftable/pq.{c, h}.
As such, this function is only called by reftable/pq_test.c and it
makes little sense to expose it to non-testing code via reftable/pq.h.

Hence, make this function static and remove its prototype from
reftable/pq.h.

Mentored-by: Patrick Steinhardt <ps@pks.im>
Mentored-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
---
 reftable/pq.h                | 1 -
 t/unit-tests/t-reftable-pq.c | 2 +-
 2 files changed, 1 insertion(+), 2 deletions(-)

diff --git a/reftable/pq.h b/reftable/pq.h
index f796c23179..707bd26767 100644
--- a/reftable/pq.h
+++ b/reftable/pq.h
@@ -22,7 +22,6 @@ struct merged_iter_pqueue {
 	size_t cap;
 };
 
-void merged_iter_pqueue_check(struct merged_iter_pqueue pq);
 struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq);
 void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry *e);
 void merged_iter_pqueue_release(struct merged_iter_pqueue *pq);
diff --git a/t/unit-tests/t-reftable-pq.c b/t/unit-tests/t-reftable-pq.c
index a47a9473f3..7d151f8582 100644
--- a/t/unit-tests/t-reftable-pq.c
+++ b/t/unit-tests/t-reftable-pq.c
@@ -10,7 +10,7 @@ license that can be found in the LICENSE file or at
 #include "reftable/constants.h"
 #include "reftable/pq.h"
 
-void merged_iter_pqueue_check(struct merged_iter_pqueue pq)
+static void merged_iter_pqueue_check(struct merged_iter_pqueue pq)
 {
 	for (size_t i = 1; i < pq.len; i++) {
 		size_t parent = (i - 1) / 2;
-- 
2.45.2.404.g9eaef5822c

[PATCH v3 5/7] t-reftable-pq: make merged_iter_pqueue_check() callable by reference

[Chandra Pratap]

merged_iter_pqueue_check() checks the validity of a priority queue
represented by a merged_iter_pqueue struct by asserting the
parent-child relation in the struct's heap. Explicity passing a
struct to this function means a copy of the entire struct is created,
which is inefficient.

Make the function accept a pointer to the struct instead. This is
safe to do since the function doesn't modify the struct in any way.
Make the function parameter 'const' to assert immutability.

Mentored-by: Patrick Steinhardt <ps@pks.im>
Mentored-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
---
 t/unit-tests/t-reftable-pq.c | 10 +++++-----
 1 file changed, 5 insertions(+), 5 deletions(-)

diff --git a/t/unit-tests/t-reftable-pq.c b/t/unit-tests/t-reftable-pq.c
index 7d151f8582..774c4194e5 100644
--- a/t/unit-tests/t-reftable-pq.c
+++ b/t/unit-tests/t-reftable-pq.c
@@ -10,11 +10,11 @@ license that can be found in the LICENSE file or at
 #include "reftable/constants.h"
 #include "reftable/pq.h"
 
-static void merged_iter_pqueue_check(struct merged_iter_pqueue pq)
+static void merged_iter_pqueue_check(const struct merged_iter_pqueue *pq)
 {
-	for (size_t i = 1; i < pq.len; i++) {
+	for (size_t i = 1; i < pq->len; i++) {
 		size_t parent = (i - 1) / 2;
-		check(pq_less(&pq.heap[parent], &pq.heap[i]));
+		check(pq_less(&pq->heap[parent], &pq->heap[i]));
 	}
 }
 
@@ -40,13 +40,13 @@ static void test_pq(void)
 		};
 
 		merged_iter_pqueue_add(&pq, &e);
-		merged_iter_pqueue_check(pq);
+		merged_iter_pqueue_check(&pq);
 		i = (i * 7) % N;
 	} while (i != 1);
 
 	while (!merged_iter_pqueue_is_empty(pq)) {
 		struct pq_entry e = merged_iter_pqueue_remove(&pq);
-		merged_iter_pqueue_check(pq);
+		merged_iter_pqueue_check(&pq);
 
 		check(reftable_record_type(e.rec) == BLOCK_TYPE_REF);
 		if (last)
-- 
2.45.2.404.g9eaef5822c

[PATCH v3 6/7] t-reftable-pq: add test for index based comparison

[Chandra Pratap]

When comparing two entries, the priority queue as defined by
reftable/pq.{c, h} first compares the entries on the basis of
their ref-record's keys. If the keys turn out to be equal, the
comparison is then made on the basis of their update indices
(which are never equal).

In the current testing setup, only the case for comparison on
the basis of ref-record's keys is exercised. Add a test for
index-based comparison as well. Rename the existing test to
reflect its nature of only testing record-based comparison.

Mentored-by: Patrick Steinhardt <ps@pks.im>
Mentored-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
---
 t/unit-tests/t-reftable-pq.c | 43 ++++++++++++++++++++++++++++++++++--
 1 file changed, 41 insertions(+), 2 deletions(-)

diff --git a/t/unit-tests/t-reftable-pq.c b/t/unit-tests/t-reftable-pq.c
index 774c4194e5..e114a8cb0f 100644
--- a/t/unit-tests/t-reftable-pq.c
+++ b/t/unit-tests/t-reftable-pq.c
@@ -18,7 +18,7 @@ static void merged_iter_pqueue_check(const struct merged_iter_pqueue *pq)
 	}
 }
 
-static void test_pq(void)
+static void test_pq_record(void)
 {
 	struct merged_iter_pqueue pq = { 0 };
 	struct reftable_record recs[54];
@@ -59,9 +59,48 @@ static void test_pq(void)
 	merged_iter_pqueue_release(&pq);
 }
 
+static void test_pq_index(void)
+{
+	struct merged_iter_pqueue pq = { 0 };
+	struct reftable_record recs[14];
+	char *last = NULL;
+	size_t N = ARRAY_SIZE(recs), i;
+
+	for (i = 0; i < N; i++) {
+		reftable_record_init(&recs[i], BLOCK_TYPE_REF);
+		recs[i].u.ref.refname = xstrdup("refs/heads/master");
+	}
+
+	for (i = 0; i < N; i++) {
+		struct pq_entry e = {
+			.rec = &recs[i],
+			.index = i,
+		};
+
+		merged_iter_pqueue_add(&pq, &e);
+		merged_iter_pqueue_check(&pq);
+	}
+
+	for (i = N - 1; !merged_iter_pqueue_is_empty(pq); i--) {
+		struct pq_entry e = merged_iter_pqueue_remove(&pq);
+		merged_iter_pqueue_check(&pq);
+
+		check(reftable_record_type(e.rec) == BLOCK_TYPE_REF);
+		check_int(e.index, ==, i);
+		if (last)
+			check_str(last, e.rec->u.ref.refname);
+		last = e.rec->u.ref.refname;
+	}
+
+	for (i = 0; i < N; i++)
+		reftable_record_release(&recs[i]);
+	merged_iter_pqueue_release(&pq);
+}
+
 int cmd_main(int argc, const char *argv[])
 {
-	TEST(test_pq(), "pq works");
+	TEST(test_pq_record(), "pq works with record-based comparison");
+	TEST(test_pq_index(), "pq works with index-based comparison");
 
 	return test_done();
 }
-- 
2.45.2.404.g9eaef5822c

[PATCH v3 7/7] t-reftable-pq: add tests for merged_iter_pqueue_top()

[Chandra Pratap]

merged_iter_pqueue_top() as defined by reftable/pq.{c, h} returns
the element at the top of a priority-queue's heap without removing
it. Since there are no tests for this function in the existing
setup, add tests for the same.

Mentored-by: Patrick Steinhardt <ps@pks.im>
Mentored-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
---
 t/unit-tests/t-reftable-pq.c | 49 ++++++++++++++++++++++++++++++++++++
 1 file changed, 49 insertions(+)

diff --git a/t/unit-tests/t-reftable-pq.c b/t/unit-tests/t-reftable-pq.c
index e114a8cb0f..0e93cc97b1 100644
--- a/t/unit-tests/t-reftable-pq.c
+++ b/t/unit-tests/t-reftable-pq.c
@@ -18,6 +18,11 @@ static void merged_iter_pqueue_check(const struct merged_iter_pqueue *pq)
 	}
 }
 
+static int pq_entry_equal(struct pq_entry *a, struct pq_entry *b)
+{
+	return !reftable_record_cmp(a->rec, b->rec) && (a->index == b->index);
+}
+
 static void test_pq_record(void)
 {
 	struct merged_iter_pqueue pq = { 0 };
@@ -45,9 +50,11 @@ static void test_pq_record(void)
 	} while (i != 1);
 
 	while (!merged_iter_pqueue_is_empty(pq)) {
+		struct pq_entry top = merged_iter_pqueue_top(pq);
 		struct pq_entry e = merged_iter_pqueue_remove(&pq);
 		merged_iter_pqueue_check(&pq);
 
+		check(pq_entry_equal(&top, &e));
 		check(reftable_record_type(e.rec) == BLOCK_TYPE_REF);
 		if (last)
 			check_int(strcmp(last, e.rec->u.ref.refname), <, 0);
@@ -82,9 +89,11 @@ static void test_pq_index(void)
 	}
 
 	for (i = N - 1; !merged_iter_pqueue_is_empty(pq); i--) {
+		struct pq_entry top = merged_iter_pqueue_top(pq);
 		struct pq_entry e = merged_iter_pqueue_remove(&pq);
 		merged_iter_pqueue_check(&pq);
 
+		check(pq_entry_equal(&top, &e));
 		check(reftable_record_type(e.rec) == BLOCK_TYPE_REF);
 		check_int(e.index, ==, i);
 		if (last)
@@ -97,10 +106,50 @@ static void test_pq_index(void)
 	merged_iter_pqueue_release(&pq);
 }
 
+static void test_merged_iter_pqueue_top(void)
+{
+	struct merged_iter_pqueue pq = { 0 };
+	struct reftable_record recs[14];
+	size_t N = ARRAY_SIZE(recs), i;
+
+	for (i = 0; i < N; i++) {
+		reftable_record_init(&recs[i], BLOCK_TYPE_REF);
+		recs[i].u.ref.refname = xstrdup("refs/heads/master");
+	}
+
+	for (i = 0; i < N; i++) {
+		struct pq_entry e = {
+			.rec = &recs[i],
+			.index = i,
+		};
+
+		merged_iter_pqueue_add(&pq, &e);
+		merged_iter_pqueue_check(&pq);
+	}
+
+	for (i = N - 1; !merged_iter_pqueue_is_empty(pq); i--) {
+		struct pq_entry top = merged_iter_pqueue_top(pq);
+		struct pq_entry e = merged_iter_pqueue_remove(&pq);
+
+		merged_iter_pqueue_check(&pq);
+		check(pq_entry_equal(&top, &e));
+		check(reftable_record_equal(top.rec, &recs[i], GIT_SHA1_RAWSZ));
+		for (size_t j = 0; i < pq.len; j++) {
+			check(pq_less(&top, &pq.heap[j]));
+			check_int(top.index, >, j);
+		}
+	}
+
+	for (i = 0; i < N; i++)
+		reftable_record_release(&recs[i]);
+	merged_iter_pqueue_release(&pq);
+}
+
 int cmd_main(int argc, const char *argv[])
 {
 	TEST(test_pq_record(), "pq works with record-based comparison");
 	TEST(test_pq_index(), "pq works with index-based comparison");
+	TEST(test_merged_iter_pqueue_top(), "merged_iter_pqueue_top works");
 
 	return test_done();
 }
-- 
2.45.2.404.g9eaef5822c

[GSoC][PATCH v4 0/7] t: port reftable/pq_test.c to the unit testing framework

[Chandra Pratap]

In the recent codebase update (commit 8bf6fbd, 2023-12-09), a new unit
testing framework written entirely in C was introduced to the Git project
aimed at simplifying testing and reducing test run times.
Currently, tests for the reftable refs-backend are performed by a custom
testing framework defined by reftable/test_framework.{c, h}. Port
reftable/pq_test.c to the unit testing framework and improve upon
the ported test.

The first two patches in the series are preparatory cleanup, the third patch
moves the test to the unit testing framework, and the rest of the patches
improve upon the ported test.

Mentored-by: Patrick Steinhardt <ps@pks.im>
Mentored-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>

---
Changes in v4:
- Add a commit message for the second patch

CI/PR for v4: https://github.com/gitgitgadget/git/pull/1745

Chandra Pratap(7):
reftable: remove unncessary curly braces in reftable/pq.c
reftable: change the type of array indices to 'size_t' in
t: move reftable/pq_test.c to the unit testing framework
t-reftable-pq: make merged_iter_pqueue_check() static
t-reftable-pq: make merged_iter_pqueue_check() callable
t-reftable-pq: add test for index based comparison
t-reftable-pq: add tests for merged_iter_pqueue_top()

Makefile                     |   2 +-
reftable/pq.c                |  29 +++--------
reftable/pq.h                |   1 -
reftable/pq_test.c           |  74 ----------------------------
t/helper/test-reftable.c     |   1 -
t/unit-tests/t-reftable-pq.c | 155 +++++++++++++++++++++++++++++++++++++++++++++
6 files changed, 166 insertions(+), 96 deletions(-)

Range-diff against v3:
1:  3c333e7770 ! 1:  1873fb02ce reftable: change the type of array indices to 'size_t' in reftable/pq.c
    @@ Metadata
      ## Commit message ##
         reftable: change the type of array indices to 'size_t' in reftable/pq.c
     
    +    The variables 'i', 'j', 'k' and 'min' are used as indices for
    +    'pq->heap', which is an array. Additionally, 'pq->len' is of
    +    type 'size_t' and is often used to assign values to these
    +    variables. Hence, change the type of these variables from 'int'
    +    to 'size_t'.
    +
         Mentored-by: Patrick Steinhardt <ps@pks.im>
         Mentored-by: Christian Couder <chriscool@tuxfamily.org>
         Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
2:  bf547f705a = 2:  3cccf8266a t: move reftable/pq_test.c to the unit testing framework
3:  7dd3a2b27f = 3:  4b63849694 t-reftable-pq: make merged_iter_pqueue_check() static
4:  c803e7adfc = 4:  3698a7189f t-reftable-pq: make merged_iter_pqueue_check() callable by reference
5:  0b03f3567d = 5:  d58c8f709e t-reftable-pq: add test for index based comparison
6:  0cdfa6221e = 6:  69521f0ff7 t-reftable-pq: add tests for merged_iter_pqueue_top()

[PATCH v4 1/7] reftable: remove unncessary curly braces in reftable/pq.c

[Chandra Pratap]

According to Documentation/CodingGuidelines, control-flow statements
with a single line as their body must omit curly braces. Make
reftable/pq.c conform to this guideline. Besides that, remove
unnecessary newlines and variable assignment.

Mentored-by: Patrick Steinhardt <ps@pks.im>
Mentored-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
---
 reftable/pq.c | 17 ++++-------------
 1 file changed, 4 insertions(+), 13 deletions(-)

diff --git a/reftable/pq.c b/reftable/pq.c
index 7fb45d8c60..1a180c5fa6 100644
--- a/reftable/pq.c
+++ b/reftable/pq.c
@@ -27,22 +27,16 @@ struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq)
 	pq->heap[0] = pq->heap[pq->len - 1];
 	pq->len--;
 
-	i = 0;
 	while (i < pq->len) {
 		int min = i;
 		int j = 2 * i + 1;
 		int k = 2 * i + 2;
-		if (j < pq->len && pq_less(&pq->heap[j], &pq->heap[i])) {
+		if (j < pq->len && pq_less(&pq->heap[j], &pq->heap[i]))
 			min = j;
-		}
-		if (k < pq->len && pq_less(&pq->heap[k], &pq->heap[min])) {
+		if (k < pq->len && pq_less(&pq->heap[k], &pq->heap[min]))
 			min = k;
-		}
-
-		if (min == i) {
+		if (min == i)
 			break;
-		}
-
 		SWAP(pq->heap[i], pq->heap[min]);
 		i = min;
 	}
@@ -60,12 +54,9 @@ void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry
 	i = pq->len - 1;
 	while (i > 0) {
 		int j = (i - 1) / 2;
-		if (pq_less(&pq->heap[j], &pq->heap[i])) {
+		if (pq_less(&pq->heap[j], &pq->heap[i]))
 			break;
-		}
-
 		SWAP(pq->heap[j], pq->heap[i]);
-
 		i = j;
 	}
 }
-- 
2.45.2.404.g9eaef5822c

[PATCH v4 2/7] reftable: change the type of array indices to 'size_t' in reftable/pq.c

[Chandra Pratap]

The variables 'i', 'j', 'k' and 'min' are used as indices for
'pq->heap', which is an array. Additionally, 'pq->len' is of
type 'size_t' and is often used to assign values to these
variables. Hence, change the type of these variables from 'int'
to 'size_t'.

Mentored-by: Patrick Steinhardt <ps@pks.im>
Mentored-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
---
 reftable/pq.c | 12 ++++++------
 1 file changed, 6 insertions(+), 6 deletions(-)

diff --git a/reftable/pq.c b/reftable/pq.c
index 1a180c5fa6..2b5b7d1c0e 100644
--- a/reftable/pq.c
+++ b/reftable/pq.c
@@ -22,15 +22,15 @@ int pq_less(struct pq_entry *a, struct pq_entry *b)
 
 struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq)
 {
-	int i = 0;
+	size_t i = 0;
 	struct pq_entry e = pq->heap[0];
 	pq->heap[0] = pq->heap[pq->len - 1];
 	pq->len--;
 
 	while (i < pq->len) {
-		int min = i;
-		int j = 2 * i + 1;
-		int k = 2 * i + 2;
+		size_t min = i;
+		size_t j = 2 * i + 1;
+		size_t k = 2 * i + 2;
 		if (j < pq->len && pq_less(&pq->heap[j], &pq->heap[i]))
 			min = j;
 		if (k < pq->len && pq_less(&pq->heap[k], &pq->heap[min]))
@@ -46,14 +46,14 @@ struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq)
 
 void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry *e)
 {
-	int i = 0;
+	size_t i = 0;
 
 	REFTABLE_ALLOC_GROW(pq->heap, pq->len + 1, pq->cap);
 	pq->heap[pq->len++] = *e;
 
 	i = pq->len - 1;
 	while (i > 0) {
-		int j = (i - 1) / 2;
+		size_t j = (i - 1) / 2;
 		if (pq_less(&pq->heap[j], &pq->heap[i]))
 			break;
 		SWAP(pq->heap[j], pq->heap[i]);
-- 
2.45.2.404.g9eaef5822c

[PATCH v4 3/7] t: move reftable/pq_test.c to the unit testing framework

[Chandra Pratap]

reftable/pq_test.c exercises a priority queue defined by
reftable/pq.{c, h}. Migrate reftable/pq_test.c to the unit
testing framework. Migration involves refactoring the tests
to use the unit testing framework instead of reftable's test
framework.

Mentored-by: Patrick Steinhardt <ps@pks.im>
Mentored-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
---
 Makefile                                      |  2 +-
 t/helper/test-reftable.c                      |  1 -
 .../pq_test.c => t/unit-tests/t-reftable-pq.c | 37 ++++++++-----------
 3 files changed, 16 insertions(+), 24 deletions(-)
 rename reftable/pq_test.c => t/unit-tests/t-reftable-pq.c (62%)

diff --git a/Makefile b/Makefile
index 59d98ba688..1cabe4cc69 100644
--- a/Makefile
+++ b/Makefile
@@ -1336,6 +1336,7 @@ THIRD_PARTY_SOURCES += sha1dc/%
 UNIT_TEST_PROGRAMS += t-ctype
 UNIT_TEST_PROGRAMS += t-mem-pool
 UNIT_TEST_PROGRAMS += t-prio-queue
+UNIT_TEST_PROGRAMS += t-reftable-pq
 UNIT_TEST_PROGRAMS += t-strbuf
 UNIT_TEST_PROGRAMS += t-strcmp-offset
 UNIT_TEST_PROGRAMS += t-trailer
@@ -2675,7 +2676,6 @@ REFTABLE_TEST_OBJS += reftable/basics_test.o
 REFTABLE_TEST_OBJS += reftable/block_test.o
 REFTABLE_TEST_OBJS += reftable/dump.o
 REFTABLE_TEST_OBJS += reftable/merged_test.o
-REFTABLE_TEST_OBJS += reftable/pq_test.o
 REFTABLE_TEST_OBJS += reftable/record_test.o
 REFTABLE_TEST_OBJS += reftable/readwrite_test.o
 REFTABLE_TEST_OBJS += reftable/stack_test.o
diff --git a/t/helper/test-reftable.c b/t/helper/test-reftable.c
index bae731669c..86a2b0f91a 100644
--- a/t/helper/test-reftable.c
+++ b/t/helper/test-reftable.c
@@ -9,7 +9,6 @@ int cmd__reftable(int argc, const char **argv)
 	record_test_main(argc, argv);
 	block_test_main(argc, argv);
 	tree_test_main(argc, argv);
-	pq_test_main(argc, argv);
 	readwrite_test_main(argc, argv);
 	merged_test_main(argc, argv);
 	stack_test_main(argc, argv);
diff --git a/reftable/pq_test.c b/t/unit-tests/t-reftable-pq.c
similarity index 62%
rename from reftable/pq_test.c
rename to t/unit-tests/t-reftable-pq.c
index b7d3c80cc7..a47a9473f3 100644
--- a/reftable/pq_test.c
+++ b/t/unit-tests/t-reftable-pq.c
@@ -6,35 +6,28 @@ license that can be found in the LICENSE file or at
 https://developers.google.com/open-source/licenses/bsd
 */
 
-#include "system.h"
-
-#include "basics.h"
-#include "constants.h"
-#include "pq.h"
-#include "record.h"
-#include "reftable-tests.h"
-#include "test_framework.h"
+#include "test-lib.h"
+#include "reftable/constants.h"
+#include "reftable/pq.h"
 
 void merged_iter_pqueue_check(struct merged_iter_pqueue pq)
 {
-	int i;
-	for (i = 1; i < pq.len; i++) {
-		int parent = (i - 1) / 2;
-
-		EXPECT(pq_less(&pq.heap[parent], &pq.heap[i]));
+	for (size_t i = 1; i < pq.len; i++) {
+		size_t parent = (i - 1) / 2;
+		check(pq_less(&pq.heap[parent], &pq.heap[i]));
 	}
 }
 
 static void test_pq(void)
 {
-	struct merged_iter_pqueue pq = { NULL };
+	struct merged_iter_pqueue pq = { 0 };
 	struct reftable_record recs[54];
-	int N = ARRAY_SIZE(recs) - 1, i;
+	size_t N = ARRAY_SIZE(recs) - 1, i;
 	char *last = NULL;
 
 	for (i = 0; i < N; i++) {
 		struct strbuf refname = STRBUF_INIT;
-		strbuf_addf(&refname, "%02d", i);
+		strbuf_addf(&refname, "%02"PRIuMAX, (uintmax_t)i);
 
 		reftable_record_init(&recs[i], BLOCK_TYPE_REF);
 		recs[i].u.ref.refname = strbuf_detach(&refname, NULL);
@@ -48,7 +41,6 @@ static void test_pq(void)
 
 		merged_iter_pqueue_add(&pq, &e);
 		merged_iter_pqueue_check(pq);
-
 		i = (i * 7) % N;
 	} while (i != 1);
 
@@ -56,9 +48,9 @@ static void test_pq(void)
 		struct pq_entry e = merged_iter_pqueue_remove(&pq);
 		merged_iter_pqueue_check(pq);
 
-		EXPECT(reftable_record_type(e.rec) == BLOCK_TYPE_REF);
+		check(reftable_record_type(e.rec) == BLOCK_TYPE_REF);
 		if (last)
-			EXPECT(strcmp(last, e.rec->u.ref.refname) < 0);
+			check_int(strcmp(last, e.rec->u.ref.refname), <, 0);
 		last = e.rec->u.ref.refname;
 	}
 
@@ -67,8 +59,9 @@ static void test_pq(void)
 	merged_iter_pqueue_release(&pq);
 }
 
-int pq_test_main(int argc, const char *argv[])
+int cmd_main(int argc, const char *argv[])
 {
-	RUN_TEST(test_pq);
-	return 0;
+	TEST(test_pq(), "pq works");
+
+	return test_done();
 }
-- 
2.45.2.404.g9eaef5822c

[PATCH v4 4/7] t-reftable-pq: make merged_iter_pqueue_check() static

[Chandra Pratap]

merged_iter_pqueue_check() is a function previously defined in
reftable/pq_test.c (now t/unit-tests/t-reftable-pq.c) and used in
the testing of a priority queue as defined by reftable/pq.{c, h}.
As such, this function is only called by reftable/pq_test.c and it
makes little sense to expose it to non-testing code via reftable/pq.h.

Hence, make this function static and remove its prototype from
reftable/pq.h.

Mentored-by: Patrick Steinhardt <ps@pks.im>
Mentored-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
---
 reftable/pq.h                | 1 -
 t/unit-tests/t-reftable-pq.c | 2 +-
 2 files changed, 1 insertion(+), 2 deletions(-)

diff --git a/reftable/pq.h b/reftable/pq.h
index f796c23179..707bd26767 100644
--- a/reftable/pq.h
+++ b/reftable/pq.h
@@ -22,7 +22,6 @@ struct merged_iter_pqueue {
 	size_t cap;
 };
 
-void merged_iter_pqueue_check(struct merged_iter_pqueue pq);
 struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq);
 void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry *e);
 void merged_iter_pqueue_release(struct merged_iter_pqueue *pq);
diff --git a/t/unit-tests/t-reftable-pq.c b/t/unit-tests/t-reftable-pq.c
index a47a9473f3..7d151f8582 100644
--- a/t/unit-tests/t-reftable-pq.c
+++ b/t/unit-tests/t-reftable-pq.c
@@ -10,7 +10,7 @@ license that can be found in the LICENSE file or at
 #include "reftable/constants.h"
 #include "reftable/pq.h"
 
-void merged_iter_pqueue_check(struct merged_iter_pqueue pq)
+static void merged_iter_pqueue_check(struct merged_iter_pqueue pq)
 {
 	for (size_t i = 1; i < pq.len; i++) {
 		size_t parent = (i - 1) / 2;
-- 
2.45.2.404.g9eaef5822c

[PATCH v4 5/7] t-reftable-pq: make merged_iter_pqueue_check() callable by reference

[Chandra Pratap]

merged_iter_pqueue_check() checks the validity of a priority queue
represented by a merged_iter_pqueue struct by asserting the
parent-child relation in the struct's heap. Explicity passing a
struct to this function means a copy of the entire struct is created,
which is inefficient.

Make the function accept a pointer to the struct instead. This is
safe to do since the function doesn't modify the struct in any way.
Make the function parameter 'const' to assert immutability.

Mentored-by: Patrick Steinhardt <ps@pks.im>
Mentored-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
---
 t/unit-tests/t-reftable-pq.c | 10 +++++-----
 1 file changed, 5 insertions(+), 5 deletions(-)

diff --git a/t/unit-tests/t-reftable-pq.c b/t/unit-tests/t-reftable-pq.c
index 7d151f8582..774c4194e5 100644
--- a/t/unit-tests/t-reftable-pq.c
+++ b/t/unit-tests/t-reftable-pq.c
@@ -10,11 +10,11 @@ license that can be found in the LICENSE file or at
 #include "reftable/constants.h"
 #include "reftable/pq.h"
 
-static void merged_iter_pqueue_check(struct merged_iter_pqueue pq)
+static void merged_iter_pqueue_check(const struct merged_iter_pqueue *pq)
 {
-	for (size_t i = 1; i < pq.len; i++) {
+	for (size_t i = 1; i < pq->len; i++) {
 		size_t parent = (i - 1) / 2;
-		check(pq_less(&pq.heap[parent], &pq.heap[i]));
+		check(pq_less(&pq->heap[parent], &pq->heap[i]));
 	}
 }
 
@@ -40,13 +40,13 @@ static void test_pq(void)
 		};
 
 		merged_iter_pqueue_add(&pq, &e);
-		merged_iter_pqueue_check(pq);
+		merged_iter_pqueue_check(&pq);
 		i = (i * 7) % N;
 	} while (i != 1);
 
 	while (!merged_iter_pqueue_is_empty(pq)) {
 		struct pq_entry e = merged_iter_pqueue_remove(&pq);
-		merged_iter_pqueue_check(pq);
+		merged_iter_pqueue_check(&pq);
 
 		check(reftable_record_type(e.rec) == BLOCK_TYPE_REF);
 		if (last)
-- 
2.45.2.404.g9eaef5822c

[PATCH v4 6/7] t-reftable-pq: add test for index based comparison

[Chandra Pratap]

When comparing two entries, the priority queue as defined by
reftable/pq.{c, h} first compares the entries on the basis of
their ref-record's keys. If the keys turn out to be equal, the
comparison is then made on the basis of their update indices
(which are never equal).

In the current testing setup, only the case for comparison on
the basis of ref-record's keys is exercised. Add a test for
index-based comparison as well. Rename the existing test to
reflect its nature of only testing record-based comparison.

Mentored-by: Patrick Steinhardt <ps@pks.im>
Mentored-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
---
 t/unit-tests/t-reftable-pq.c | 43 ++++++++++++++++++++++++++++++++++--
 1 file changed, 41 insertions(+), 2 deletions(-)

diff --git a/t/unit-tests/t-reftable-pq.c b/t/unit-tests/t-reftable-pq.c
index 774c4194e5..e114a8cb0f 100644
--- a/t/unit-tests/t-reftable-pq.c
+++ b/t/unit-tests/t-reftable-pq.c
@@ -18,7 +18,7 @@ static void merged_iter_pqueue_check(const struct merged_iter_pqueue *pq)
 	}
 }
 
-static void test_pq(void)
+static void test_pq_record(void)
 {
 	struct merged_iter_pqueue pq = { 0 };
 	struct reftable_record recs[54];
@@ -59,9 +59,48 @@ static void test_pq(void)
 	merged_iter_pqueue_release(&pq);
 }
 
+static void test_pq_index(void)
+{
+	struct merged_iter_pqueue pq = { 0 };
+	struct reftable_record recs[14];
+	char *last = NULL;
+	size_t N = ARRAY_SIZE(recs), i;
+
+	for (i = 0; i < N; i++) {
+		reftable_record_init(&recs[i], BLOCK_TYPE_REF);
+		recs[i].u.ref.refname = xstrdup("refs/heads/master");
+	}
+
+	for (i = 0; i < N; i++) {
+		struct pq_entry e = {
+			.rec = &recs[i],
+			.index = i,
+		};
+
+		merged_iter_pqueue_add(&pq, &e);
+		merged_iter_pqueue_check(&pq);
+	}
+
+	for (i = N - 1; !merged_iter_pqueue_is_empty(pq); i--) {
+		struct pq_entry e = merged_iter_pqueue_remove(&pq);
+		merged_iter_pqueue_check(&pq);
+
+		check(reftable_record_type(e.rec) == BLOCK_TYPE_REF);
+		check_int(e.index, ==, i);
+		if (last)
+			check_str(last, e.rec->u.ref.refname);
+		last = e.rec->u.ref.refname;
+	}
+
+	for (i = 0; i < N; i++)
+		reftable_record_release(&recs[i]);
+	merged_iter_pqueue_release(&pq);
+}
+
 int cmd_main(int argc, const char *argv[])
 {
-	TEST(test_pq(), "pq works");
+	TEST(test_pq_record(), "pq works with record-based comparison");
+	TEST(test_pq_index(), "pq works with index-based comparison");
 
 	return test_done();
 }
-- 
2.45.2.404.g9eaef5822c

[PATCH v4 7/7] t-reftable-pq: add tests for merged_iter_pqueue_top()

[Chandra Pratap]

merged_iter_pqueue_top() as defined by reftable/pq.{c, h} returns
the element at the top of a priority-queue's heap without removing
it. Since there are no tests for this function in the existing
setup, add tests for the same.

Mentored-by: Patrick Steinhardt <ps@pks.im>
Mentored-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
---
 t/unit-tests/t-reftable-pq.c | 49 ++++++++++++++++++++++++++++++++++++
 1 file changed, 49 insertions(+)

diff --git a/t/unit-tests/t-reftable-pq.c b/t/unit-tests/t-reftable-pq.c
index e114a8cb0f..0e93cc97b1 100644
--- a/t/unit-tests/t-reftable-pq.c
+++ b/t/unit-tests/t-reftable-pq.c
@@ -18,6 +18,11 @@ static void merged_iter_pqueue_check(const struct merged_iter_pqueue *pq)
 	}
 }
 
+static int pq_entry_equal(struct pq_entry *a, struct pq_entry *b)
+{
+	return !reftable_record_cmp(a->rec, b->rec) && (a->index == b->index);
+}
+
 static void test_pq_record(void)
 {
 	struct merged_iter_pqueue pq = { 0 };
@@ -45,9 +50,11 @@ static void test_pq_record(void)
 	} while (i != 1);
 
 	while (!merged_iter_pqueue_is_empty(pq)) {
+		struct pq_entry top = merged_iter_pqueue_top(pq);
 		struct pq_entry e = merged_iter_pqueue_remove(&pq);
 		merged_iter_pqueue_check(&pq);
 
+		check(pq_entry_equal(&top, &e));
 		check(reftable_record_type(e.rec) == BLOCK_TYPE_REF);
 		if (last)
 			check_int(strcmp(last, e.rec->u.ref.refname), <, 0);
@@ -82,9 +89,11 @@ static void test_pq_index(void)
 	}
 
 	for (i = N - 1; !merged_iter_pqueue_is_empty(pq); i--) {
+		struct pq_entry top = merged_iter_pqueue_top(pq);
 		struct pq_entry e = merged_iter_pqueue_remove(&pq);
 		merged_iter_pqueue_check(&pq);
 
+		check(pq_entry_equal(&top, &e));
 		check(reftable_record_type(e.rec) == BLOCK_TYPE_REF);
 		check_int(e.index, ==, i);
 		if (last)
@@ -97,10 +106,50 @@ static void test_pq_index(void)
 	merged_iter_pqueue_release(&pq);
 }
 
+static void test_merged_iter_pqueue_top(void)
+{
+	struct merged_iter_pqueue pq = { 0 };
+	struct reftable_record recs[14];
+	size_t N = ARRAY_SIZE(recs), i;
+
+	for (i = 0; i < N; i++) {
+		reftable_record_init(&recs[i], BLOCK_TYPE_REF);
+		recs[i].u.ref.refname = xstrdup("refs/heads/master");
+	}
+
+	for (i = 0; i < N; i++) {
+		struct pq_entry e = {
+			.rec = &recs[i],
+			.index = i,
+		};
+
+		merged_iter_pqueue_add(&pq, &e);
+		merged_iter_pqueue_check(&pq);
+	}
+
+	for (i = N - 1; !merged_iter_pqueue_is_empty(pq); i--) {
+		struct pq_entry top = merged_iter_pqueue_top(pq);
+		struct pq_entry e = merged_iter_pqueue_remove(&pq);
+
+		merged_iter_pqueue_check(&pq);
+		check(pq_entry_equal(&top, &e));
+		check(reftable_record_equal(top.rec, &recs[i], GIT_SHA1_RAWSZ));
+		for (size_t j = 0; i < pq.len; j++) {
+			check(pq_less(&top, &pq.heap[j]));
+			check_int(top.index, >, j);
+		}
+	}
+
+	for (i = 0; i < N; i++)
+		reftable_record_release(&recs[i]);
+	merged_iter_pqueue_release(&pq);
+}
+
 int cmd_main(int argc, const char *argv[])
 {
 	TEST(test_pq_record(), "pq works with record-based comparison");
 	TEST(test_pq_index(), "pq works with index-based comparison");
+	TEST(test_merged_iter_pqueue_top(), "merged_iter_pqueue_top works");
 
 	return test_done();
 }
-- 
2.45.2.404.g9eaef5822c

Re: [GSoC][PATCH v4 0/7] t: port reftable/pq_test.c to the unit testing framework

[Junio C Hamano]

Chandra Pratap <chandrapratap3519@gmail.com> writes:

> In the recent codebase update (commit 8bf6fbd, 2023-12-09), a new unit
> testing framework written entirely in C was introduced to the Git project
> aimed at simplifying testing and reducing test run times.
> Currently, tests for the reftable refs-backend are performed by a custom
> testing framework defined by reftable/test_framework.{c, h}. Port
> reftable/pq_test.c to the unit testing framework and improve upon
> the ported test.
>
> The first two patches in the series are preparatory cleanup, the third patch
> moves the test to the unit testing framework, and the rest of the patches
> improve upon the ported test.
>
> Mentored-by: Patrick Steinhardt <ps@pks.im>
> Mentored-by: Christian Couder <chriscool@tuxfamily.org>
> Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
>
> ---
> Changes in v4:
> - Add a commit message for the second patch
>
> CI/PR for v4: https://github.com/gitgitgadget/git/pull/1745

Hmph.

A larger question is how pristine we want to keep the "imported
source" that is reftable/* stuff.

Obviously we are getting rid of some parts of it (like pq_test.c
here) so our "fork" will no longer be usable, without pulling some
of the stuff our project offers from outside that directory, by
outside people.  This concern is shared with other topics we saw
recently to move the unit tests bundled with the reftable library to
t/unit-tests/.

But this series brings in another twist that makes it a larger
question.  If we are willing to butcher our copy of reftable library
to a shape that cannot be reused by outside folks, do we still want
to use reftable/pq.c instead of getting rid of it and use the other
prio queue implementation we use elsewhere in our system?  If that
will be the longer term direction we want to go, then porting the
unit tests for reftable/pq.c may end up being a wasted effort.

So, I dunno.

> Chandra Pratap(7):
> reftable: remove unncessary curly braces in reftable/pq.c
> reftable: change the type of array indices to 'size_t' in
> t: move reftable/pq_test.c to the unit testing framework
> t-reftable-pq: make merged_iter_pqueue_check() static
> t-reftable-pq: make merged_iter_pqueue_check() callable
> t-reftable-pq: add test for index based comparison
> t-reftable-pq: add tests for merged_iter_pqueue_top()
>
> Makefile                     |   2 +-
> reftable/pq.c                |  29 +++--------
> reftable/pq.h                |   1 -
> reftable/pq_test.c           |  74 ----------------------------
> t/helper/test-reftable.c     |   1 -
> t/unit-tests/t-reftable-pq.c | 155 +++++++++++++++++++++++++++++++++++++++++++++
> 6 files changed, 166 insertions(+), 96 deletions(-)
>
> Range-diff against v3:
> 1:  3c333e7770 ! 1:  1873fb02ce reftable: change the type of array indices to 'size_t' in reftable/pq.c
>     @@ Metadata
>       ## Commit message ##
>          reftable: change the type of array indices to 'size_t' in reftable/pq.c
>      
>     +    The variables 'i', 'j', 'k' and 'min' are used as indices for
>     +    'pq->heap', which is an array. Additionally, 'pq->len' is of
>     +    type 'size_t' and is often used to assign values to these
>     +    variables. Hence, change the type of these variables from 'int'
>     +    to 'size_t'.
>     +
>          Mentored-by: Patrick Steinhardt <ps@pks.im>
>          Mentored-by: Christian Couder <chriscool@tuxfamily.org>
>          Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
> 2:  bf547f705a = 2:  3cccf8266a t: move reftable/pq_test.c to the unit testing framework
> 3:  7dd3a2b27f = 3:  4b63849694 t-reftable-pq: make merged_iter_pqueue_check() static
> 4:  c803e7adfc = 4:  3698a7189f t-reftable-pq: make merged_iter_pqueue_check() callable by reference
> 5:  0b03f3567d = 5:  d58c8f709e t-reftable-pq: add test for index based comparison
> 6:  0cdfa6221e = 6:  69521f0ff7 t-reftable-pq: add tests for merged_iter_pqueue_top()

[GSoC][PATCH v5 0/7] t: port reftable/pq_test.c to the unit testing framework

[Chandra Pratap]

The reftable library comes with self tests, which are exercised
as part of the usual end-to-end tests and are designed to
observe the end-user visible effects of Git commands. What it
exercises, however, is a better match for the unit-testing
framework, merged at 8bf6fbd0 (Merge branch 'js/doc-unit-tests',
2023-12-09), which is designed to observe how low level
implementation details, at the level of sequences of individual
function calls, behave.

Hence, port reftable/pq_test.c to the unit testing framework and
improve upon the ported test. The first two patches in the series
are preparatory cleanup, the third patch moves the test to the unit
testing framework, and the rest of the patches improve upon the
ported test.

Mentored-by: Patrick Steinhardt <ps@pks.im>
Mentored-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>

---
Changes in v5:
- Rebase the branch on top of the  latest master branch
- Rename tests according to unit-tests' conventions
- remove 'pq_test_main()' from reftable/reftable-test.h

CI/PR for v5: https://github.com/gitgitgadget/git/pull/1745

Chandra Pratap(7):
reftable: remove unncessary curly braces in reftable/pq.c
reftable: change the type of array indices to 'size_t' in reftable/pq.c
t: move reftable/pq_test.c to the unit testing framework
t-reftable-pq: make merged_iter_pqueue_check() static
t-reftable-pq: make merged_iter_pqueue_check() callable by reference
t-reftable-pq: add test for index based comparison
t-reftable-pq: add tests for merged_iter_pqueue_top()

Makefile                     |   2 +-
reftable/pq.c                |  29 +++-----
reftable/pq.h                |   1 -
reftable/pq_test.c           |  74 ---------------------
reftable/reftable-tests.h    |   1 -
t/helper/test-reftable.c     |   1 -
t/unit-tests/t-reftable-pq.c | 155 +++++++++++++++++++++++++++++++++++++++++++
7 files changed, 166 insertions(+), 97 deletions(-)

Range-diff against v4:
<rebase commits>
  1:  d3c5605ea2 = 382:  acd9d26aaf reftable: remove unncessary curly braces in reftable/pq.c
  2:  3c333e7770 = 383:  2e0986207b reftable: change the type of array indices to 'size_t' in reftable/pq.c
  3:  bf547f705a ! 384:  df06b6d604 t: move reftable/pq_test.c to the unit testing framework
    @@ Commit message
         t: move reftable/pq_test.c to the unit testing framework

         reftable/pq_test.c exercises a priority queue defined by
    -    reftable/pq.{c, h}. Migrate reftable/pq_test.c to the unit
    -    testing framework. Migration involves refactoring the tests
    -    to use the unit testing framework instead of reftable's test
    -    framework.
    +    reftable/pq.{c, h}. Migrate reftable/pq_test.c to the unit testing
    +    framework. Migration involves refactoring the tests to use the unit
    +    testing framework instead of reftable's test framework, and
    +    renaming the tests to align with unit-tests' standards.

         Mentored-by: Patrick Steinhardt <ps@pks.im>
         Mentored-by: Christian Couder <chriscool@tuxfamily.org>
         Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>

      ## Makefile ##
    -@@ Makefile: THIRD_PARTY_SOURCES += sha1dc/%
    - UNIT_TEST_PROGRAMS += t-ctype
    - UNIT_TEST_PROGRAMS += t-mem-pool
    +@@ Makefile: UNIT_TEST_PROGRAMS += t-oidmap
    + UNIT_TEST_PROGRAMS += t-oidtree
      UNIT_TEST_PROGRAMS += t-prio-queue
    + UNIT_TEST_PROGRAMS += t-reftable-basics
     +UNIT_TEST_PROGRAMS += t-reftable-pq
    + UNIT_TEST_PROGRAMS += t-reftable-record
      UNIT_TEST_PROGRAMS += t-strbuf
      UNIT_TEST_PROGRAMS += t-strcmp-offset
    - UNIT_TEST_PROGRAMS += t-trailer
    -@@ Makefile: REFTABLE_TEST_OBJS += reftable/basics_test.o
    +@@ Makefile: REFTABLE_OBJS += reftable/writer.o
      REFTABLE_TEST_OBJS += reftable/block_test.o
      REFTABLE_TEST_OBJS += reftable/dump.o
      REFTABLE_TEST_OBJS += reftable/merged_test.o
     -REFTABLE_TEST_OBJS += reftable/pq_test.o
    - REFTABLE_TEST_OBJS += reftable/record_test.o
      REFTABLE_TEST_OBJS += reftable/readwrite_test.o
      REFTABLE_TEST_OBJS += reftable/stack_test.o
    + REFTABLE_TEST_OBJS += reftable/test_framework.o
    +
    + ## reftable/reftable-tests.h ##
    +@@ reftable/reftable-tests.h: license that can be found in the LICENSE file or at
    + int basics_test_main(int argc, const char **argv);
    + int block_test_main(int argc, const char **argv);
    + int merged_test_main(int argc, const char **argv);
    +-int pq_test_main(int argc, const char **argv);
    + int record_test_main(int argc, const char **argv);
    + int readwrite_test_main(int argc, const char **argv);
    + int stack_test_main(int argc, const char **argv);

      ## t/helper/test-reftable.c ##
     @@ t/helper/test-reftable.c: int cmd__reftable(int argc, const char **argv)
    - 	record_test_main(argc, argv);
    + 	/* test from simple to complex. */
      	block_test_main(argc, argv);
      	tree_test_main(argc, argv);
     -	pq_test_main(argc, argv);
    @@ t/unit-tests/t-reftable-pq.c: license that can be found in the LICENSE file or a
      	}
      }

    - static void test_pq(void)
    +-static void test_pq(void)
    ++static void t_pq(void)
      {
     -	struct merged_iter_pqueue pq = { NULL };
     +	struct merged_iter_pqueue pq = { 0 };
    @@ t/unit-tests/t-reftable-pq.c: static void test_pq(void)
      {
     -	RUN_TEST(test_pq);
     -	return 0;
    -+	TEST(test_pq(), "pq works");
    ++	TEST(t_pq(), "pq works");
     +
     +	return test_done();
      }
  4:  7dd3a2b27f = 385:  40745ab18e t-reftable-pq: make merged_iter_pqueue_check() static
  5:  c803e7adfc ! 386:  ee8432ac4a t-reftable-pq: make merged_iter_pqueue_check() callable by reference
    @@ t/unit-tests/t-reftable-pq.c: license that can be found in the LICENSE file or a
      	}
      }

    -@@ t/unit-tests/t-reftable-pq.c: static void test_pq(void)
    +@@ t/unit-tests/t-reftable-pq.c: static void t_pq(void)
      		};

      		merged_iter_pqueue_add(&pq, &e);
  6:  0b03f3567d ! 387:  94a77f5a60 t-reftable-pq: add test for index based comparison
    @@ t/unit-tests/t-reftable-pq.c: static void merged_iter_pqueue_check(const struct
      	}
      }

    --static void test_pq(void)
    -+static void test_pq_record(void)
    +-static void t_pq(void)
    ++static void t_pq_record(void)
      {
      	struct merged_iter_pqueue pq = { 0 };
      	struct reftable_record recs[54];
    -@@ t/unit-tests/t-reftable-pq.c: static void test_pq(void)
    +@@ t/unit-tests/t-reftable-pq.c: static void t_pq(void)
      	merged_iter_pqueue_release(&pq);
      }

    -+static void test_pq_index(void)
    ++static void t_pq_index(void)
     +{
     +	struct merged_iter_pqueue pq = { 0 };
     +	struct reftable_record recs[14];
    @@ t/unit-tests/t-reftable-pq.c: static void test_pq(void)
     +
      int cmd_main(int argc, const char *argv[])
      {
    --	TEST(test_pq(), "pq works");
    -+	TEST(test_pq_record(), "pq works with record-based comparison");
    -+	TEST(test_pq_index(), "pq works with index-based comparison");
    +-	TEST(t_pq(), "pq works");
    ++	TEST(t_pq_record(), "pq works with record-based comparison");
    ++	TEST(t_pq_index(), "pq works with index-based comparison");

      	return test_done();
      }
  7:  0cdfa6221e ! 388:  9a76f87bd1 t-reftable-pq: add tests for merged_iter_pqueue_top()
    @@ t/unit-tests/t-reftable-pq.c: static void merged_iter_pqueue_check(const struct
     +	return !reftable_record_cmp(a->rec, b->rec) && (a->index == b->index);
     +}
     +
    - static void test_pq_record(void)
    + static void t_pq_record(void)
      {
      	struct merged_iter_pqueue pq = { 0 };
    -@@ t/unit-tests/t-reftable-pq.c: static void test_pq_record(void)
    +@@ t/unit-tests/t-reftable-pq.c: static void t_pq_record(void)
      	} while (i != 1);

      	while (!merged_iter_pqueue_is_empty(pq)) {
    @@ t/unit-tests/t-reftable-pq.c: static void test_pq_record(void)
      		check(reftable_record_type(e.rec) == BLOCK_TYPE_REF);
      		if (last)
      			check_int(strcmp(last, e.rec->u.ref.refname), <, 0);
    -@@ t/unit-tests/t-reftable-pq.c: static void test_pq_index(void)
    +@@ t/unit-tests/t-reftable-pq.c: static void t_pq_index(void)
      	}

      	for (i = N - 1; !merged_iter_pqueue_is_empty(pq); i--) {
    @@ t/unit-tests/t-reftable-pq.c: static void test_pq_index(void)
      		check(reftable_record_type(e.rec) == BLOCK_TYPE_REF);
      		check_int(e.index, ==, i);
      		if (last)
    -@@ t/unit-tests/t-reftable-pq.c: static void test_pq_index(void)
    +@@ t/unit-tests/t-reftable-pq.c: static void t_pq_index(void)
      	merged_iter_pqueue_release(&pq);
      }

    -+static void test_merged_iter_pqueue_top(void)
    ++static void t_merged_iter_pqueue_top(void)
     +{
     +	struct merged_iter_pqueue pq = { 0 };
     +	struct reftable_record recs[14];
    @@ t/unit-tests/t-reftable-pq.c: static void test_pq_index(void)
     +
      int cmd_main(int argc, const char *argv[])
      {
    - 	TEST(test_pq_record(), "pq works with record-based comparison");
    - 	TEST(test_pq_index(), "pq works with index-based comparison");
    -+	TEST(test_merged_iter_pqueue_top(), "merged_iter_pqueue_top works");
    + 	TEST(t_pq_record(), "pq works with record-based comparison");
    + 	TEST(t_pq_index(), "pq works with index-based comparison");
    ++	TEST(t_merged_iter_pqueue_top(), "merged_iter_pqueue_top works");

      	return test_done();
      }

[PATCH v5 1/7] reftable: remove unncessary curly braces in reftable/pq.c

[Chandra Pratap]

According to Documentation/CodingGuidelines, control-flow statements
with a single line as their body must omit curly braces. Make
reftable/pq.c conform to this guideline. Besides that, remove
unnecessary newlines and variable assignment.

Mentored-by: Patrick Steinhardt <ps@pks.im>
Mentored-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
---
 reftable/pq.c | 17 ++++-------------
 1 file changed, 4 insertions(+), 13 deletions(-)

diff --git a/reftable/pq.c b/reftable/pq.c
index 7fb45d8c60..1a180c5fa6 100644
--- a/reftable/pq.c
+++ b/reftable/pq.c
@@ -27,22 +27,16 @@ struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq)
 	pq->heap[0] = pq->heap[pq->len - 1];
 	pq->len--;
 
-	i = 0;
 	while (i < pq->len) {
 		int min = i;
 		int j = 2 * i + 1;
 		int k = 2 * i + 2;
-		if (j < pq->len && pq_less(&pq->heap[j], &pq->heap[i])) {
+		if (j < pq->len && pq_less(&pq->heap[j], &pq->heap[i]))
 			min = j;
-		}
-		if (k < pq->len && pq_less(&pq->heap[k], &pq->heap[min])) {
+		if (k < pq->len && pq_less(&pq->heap[k], &pq->heap[min]))
 			min = k;
-		}
-
-		if (min == i) {
+		if (min == i)
 			break;
-		}
-
 		SWAP(pq->heap[i], pq->heap[min]);
 		i = min;
 	}
@@ -60,12 +54,9 @@ void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry
 	i = pq->len - 1;
 	while (i > 0) {
 		int j = (i - 1) / 2;
-		if (pq_less(&pq->heap[j], &pq->heap[i])) {
+		if (pq_less(&pq->heap[j], &pq->heap[i]))
 			break;
-		}
-
 		SWAP(pq->heap[j], pq->heap[i]);
-
 		i = j;
 	}
 }
-- 
2.45.GIT

[PATCH v5 2/7] reftable: change the type of array indices to 'size_t' in reftable/pq.c

[Chandra Pratap]

The variables 'i', 'j', 'k' and 'min' are used as indices for
'pq->heap', which is an array. Additionally, 'pq->len' is of
type 'size_t' and is often used to assign values to these
variables. Hence, change the type of these variables from 'int'
to 'size_t'.

Mentored-by: Patrick Steinhardt <ps@pks.im>
Mentored-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
---
 reftable/pq.c | 12 ++++++------
 1 file changed, 6 insertions(+), 6 deletions(-)

diff --git a/reftable/pq.c b/reftable/pq.c
index 1a180c5fa6..2b5b7d1c0e 100644
--- a/reftable/pq.c
+++ b/reftable/pq.c
@@ -22,15 +22,15 @@ int pq_less(struct pq_entry *a, struct pq_entry *b)
 
 struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq)
 {
-	int i = 0;
+	size_t i = 0;
 	struct pq_entry e = pq->heap[0];
 	pq->heap[0] = pq->heap[pq->len - 1];
 	pq->len--;
 
 	while (i < pq->len) {
-		int min = i;
-		int j = 2 * i + 1;
-		int k = 2 * i + 2;
+		size_t min = i;
+		size_t j = 2 * i + 1;
+		size_t k = 2 * i + 2;
 		if (j < pq->len && pq_less(&pq->heap[j], &pq->heap[i]))
 			min = j;
 		if (k < pq->len && pq_less(&pq->heap[k], &pq->heap[min]))
@@ -46,14 +46,14 @@ struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq)
 
 void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry *e)
 {
-	int i = 0;
+	size_t i = 0;
 
 	REFTABLE_ALLOC_GROW(pq->heap, pq->len + 1, pq->cap);
 	pq->heap[pq->len++] = *e;
 
 	i = pq->len - 1;
 	while (i > 0) {
-		int j = (i - 1) / 2;
+		size_t j = (i - 1) / 2;
 		if (pq_less(&pq->heap[j], &pq->heap[i]))
 			break;
 		SWAP(pq->heap[j], pq->heap[i]);
-- 
2.45.GIT

[PATCH v5 3/7] t: move reftable/pq_test.c to the unit testing framework

[Chandra Pratap]

reftable/pq_test.c exercises a priority queue defined by
reftable/pq.{c, h}. Migrate reftable/pq_test.c to the unit testing
framework. Migration involves refactoring the tests to use the unit
testing framework instead of reftable's test framework, and
renaming the tests to align with unit-tests' standards.

Mentored-by: Patrick Steinhardt <ps@pks.im>
Mentored-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
---
 Makefile                                      |  2 +-
 reftable/reftable-tests.h                     |  1 -
 t/helper/test-reftable.c                      |  1 -
 .../pq_test.c => t/unit-tests/t-reftable-pq.c | 39 ++++++++-----------
 4 files changed, 17 insertions(+), 26 deletions(-)
 rename reftable/pq_test.c => t/unit-tests/t-reftable-pq.c (61%)

diff --git a/Makefile b/Makefile
index d6479092a0..1ee83e98dc 100644
--- a/Makefile
+++ b/Makefile
@@ -1340,6 +1340,7 @@ UNIT_TEST_PROGRAMS += t-oidmap
 UNIT_TEST_PROGRAMS += t-oidtree
 UNIT_TEST_PROGRAMS += t-prio-queue
 UNIT_TEST_PROGRAMS += t-reftable-basics
+UNIT_TEST_PROGRAMS += t-reftable-pq
 UNIT_TEST_PROGRAMS += t-reftable-record
 UNIT_TEST_PROGRAMS += t-strbuf
 UNIT_TEST_PROGRAMS += t-strcmp-offset
@@ -2681,7 +2682,6 @@ REFTABLE_OBJS += reftable/writer.o
 REFTABLE_TEST_OBJS += reftable/block_test.o
 REFTABLE_TEST_OBJS += reftable/dump.o
 REFTABLE_TEST_OBJS += reftable/merged_test.o
-REFTABLE_TEST_OBJS += reftable/pq_test.o
 REFTABLE_TEST_OBJS += reftable/readwrite_test.o
 REFTABLE_TEST_OBJS += reftable/stack_test.o
 REFTABLE_TEST_OBJS += reftable/test_framework.o
diff --git a/reftable/reftable-tests.h b/reftable/reftable-tests.h
index 114cc3d053..67283faf06 100644
--- a/reftable/reftable-tests.h
+++ b/reftable/reftable-tests.h
@@ -12,7 +12,6 @@ license that can be found in the LICENSE file or at
 int basics_test_main(int argc, const char **argv);
 int block_test_main(int argc, const char **argv);
 int merged_test_main(int argc, const char **argv);
-int pq_test_main(int argc, const char **argv);
 int record_test_main(int argc, const char **argv);
 int readwrite_test_main(int argc, const char **argv);
 int stack_test_main(int argc, const char **argv);
diff --git a/t/helper/test-reftable.c b/t/helper/test-reftable.c
index aa6538a8da..b808ad3e12 100644
--- a/t/helper/test-reftable.c
+++ b/t/helper/test-reftable.c
@@ -7,7 +7,6 @@ int cmd__reftable(int argc, const char **argv)
 	/* test from simple to complex. */
 	block_test_main(argc, argv);
 	tree_test_main(argc, argv);
-	pq_test_main(argc, argv);
 	readwrite_test_main(argc, argv);
 	merged_test_main(argc, argv);
 	stack_test_main(argc, argv);
diff --git a/reftable/pq_test.c b/t/unit-tests/t-reftable-pq.c
similarity index 61%
rename from reftable/pq_test.c
rename to t/unit-tests/t-reftable-pq.c
index b7d3c80cc7..a78aba9e71 100644
--- a/reftable/pq_test.c
+++ b/t/unit-tests/t-reftable-pq.c
@@ -6,35 +6,28 @@ license that can be found in the LICENSE file or at
 https://developers.google.com/open-source/licenses/bsd
 */
 
-#include "system.h"
-
-#include "basics.h"
-#include "constants.h"
-#include "pq.h"
-#include "record.h"
-#include "reftable-tests.h"
-#include "test_framework.h"
+#include "test-lib.h"
+#include "reftable/constants.h"
+#include "reftable/pq.h"
 
 void merged_iter_pqueue_check(struct merged_iter_pqueue pq)
 {
-	int i;
-	for (i = 1; i < pq.len; i++) {
-		int parent = (i - 1) / 2;
-
-		EXPECT(pq_less(&pq.heap[parent], &pq.heap[i]));
+	for (size_t i = 1; i < pq.len; i++) {
+		size_t parent = (i - 1) / 2;
+		check(pq_less(&pq.heap[parent], &pq.heap[i]));
 	}
 }
 
-static void test_pq(void)
+static void t_pq(void)
 {
-	struct merged_iter_pqueue pq = { NULL };
+	struct merged_iter_pqueue pq = { 0 };
 	struct reftable_record recs[54];
-	int N = ARRAY_SIZE(recs) - 1, i;
+	size_t N = ARRAY_SIZE(recs) - 1, i;
 	char *last = NULL;
 
 	for (i = 0; i < N; i++) {
 		struct strbuf refname = STRBUF_INIT;
-		strbuf_addf(&refname, "%02d", i);
+		strbuf_addf(&refname, "%02"PRIuMAX, (uintmax_t)i);
 
 		reftable_record_init(&recs[i], BLOCK_TYPE_REF);
 		recs[i].u.ref.refname = strbuf_detach(&refname, NULL);
@@ -48,7 +41,6 @@ static void test_pq(void)
 
 		merged_iter_pqueue_add(&pq, &e);
 		merged_iter_pqueue_check(pq);
-
 		i = (i * 7) % N;
 	} while (i != 1);
 
@@ -56,9 +48,9 @@ static void test_pq(void)
 		struct pq_entry e = merged_iter_pqueue_remove(&pq);
 		merged_iter_pqueue_check(pq);
 
-		EXPECT(reftable_record_type(e.rec) == BLOCK_TYPE_REF);
+		check(reftable_record_type(e.rec) == BLOCK_TYPE_REF);
 		if (last)
-			EXPECT(strcmp(last, e.rec->u.ref.refname) < 0);
+			check_int(strcmp(last, e.rec->u.ref.refname), <, 0);
 		last = e.rec->u.ref.refname;
 	}
 
@@ -67,8 +59,9 @@ static void test_pq(void)
 	merged_iter_pqueue_release(&pq);
 }
 
-int pq_test_main(int argc, const char *argv[])
+int cmd_main(int argc, const char *argv[])
 {
-	RUN_TEST(test_pq);
-	return 0;
+	TEST(t_pq(), "pq works");
+
+	return test_done();
 }
-- 
2.45.GIT

[PATCH v5 4/7] t-reftable-pq: make merged_iter_pqueue_check() static

[Chandra Pratap]

merged_iter_pqueue_check() is a function previously defined in
reftable/pq_test.c (now t/unit-tests/t-reftable-pq.c) and used in
the testing of a priority queue as defined by reftable/pq.{c, h}.
As such, this function is only called by reftable/pq_test.c and it
makes little sense to expose it to non-testing code via reftable/pq.h.

Hence, make this function static and remove its prototype from
reftable/pq.h.

Mentored-by: Patrick Steinhardt <ps@pks.im>
Mentored-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
---
 reftable/pq.h                | 1 -
 t/unit-tests/t-reftable-pq.c | 2 +-
 2 files changed, 1 insertion(+), 2 deletions(-)

diff --git a/reftable/pq.h b/reftable/pq.h
index f796c23179..707bd26767 100644
--- a/reftable/pq.h
+++ b/reftable/pq.h
@@ -22,7 +22,6 @@ struct merged_iter_pqueue {
 	size_t cap;
 };
 
-void merged_iter_pqueue_check(struct merged_iter_pqueue pq);
 struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq);
 void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry *e);
 void merged_iter_pqueue_release(struct merged_iter_pqueue *pq);
diff --git a/t/unit-tests/t-reftable-pq.c b/t/unit-tests/t-reftable-pq.c
index a78aba9e71..220e82be19 100644
--- a/t/unit-tests/t-reftable-pq.c
+++ b/t/unit-tests/t-reftable-pq.c
@@ -10,7 +10,7 @@ license that can be found in the LICENSE file or at
 #include "reftable/constants.h"
 #include "reftable/pq.h"
 
-void merged_iter_pqueue_check(struct merged_iter_pqueue pq)
+static void merged_iter_pqueue_check(struct merged_iter_pqueue pq)
 {
 	for (size_t i = 1; i < pq.len; i++) {
 		size_t parent = (i - 1) / 2;
-- 
2.45.GIT

[PATCH v5 5/7] t-reftable-pq: make merged_iter_pqueue_check() callable by reference

[Chandra Pratap]

merged_iter_pqueue_check() checks the validity of a priority queue
represented by a merged_iter_pqueue struct by asserting the
parent-child relation in the struct's heap. Explicity passing a
struct to this function means a copy of the entire struct is created,
which is inefficient.

Make the function accept a pointer to the struct instead. This is
safe to do since the function doesn't modify the struct in any way.
Make the function parameter 'const' to assert immutability.

Mentored-by: Patrick Steinhardt <ps@pks.im>
Mentored-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
---
 t/unit-tests/t-reftable-pq.c | 10 +++++-----
 1 file changed, 5 insertions(+), 5 deletions(-)

diff --git a/t/unit-tests/t-reftable-pq.c b/t/unit-tests/t-reftable-pq.c
index 220e82be19..9230dd9b9e 100644
--- a/t/unit-tests/t-reftable-pq.c
+++ b/t/unit-tests/t-reftable-pq.c
@@ -10,11 +10,11 @@ license that can be found in the LICENSE file or at
 #include "reftable/constants.h"
 #include "reftable/pq.h"
 
-static void merged_iter_pqueue_check(struct merged_iter_pqueue pq)
+static void merged_iter_pqueue_check(const struct merged_iter_pqueue *pq)
 {
-	for (size_t i = 1; i < pq.len; i++) {
+	for (size_t i = 1; i < pq->len; i++) {
 		size_t parent = (i - 1) / 2;
-		check(pq_less(&pq.heap[parent], &pq.heap[i]));
+		check(pq_less(&pq->heap[parent], &pq->heap[i]));
 	}
 }
 
@@ -40,13 +40,13 @@ static void t_pq(void)
 		};
 
 		merged_iter_pqueue_add(&pq, &e);
-		merged_iter_pqueue_check(pq);
+		merged_iter_pqueue_check(&pq);
 		i = (i * 7) % N;
 	} while (i != 1);
 
 	while (!merged_iter_pqueue_is_empty(pq)) {
 		struct pq_entry e = merged_iter_pqueue_remove(&pq);
-		merged_iter_pqueue_check(pq);
+		merged_iter_pqueue_check(&pq);
 
 		check(reftable_record_type(e.rec) == BLOCK_TYPE_REF);
 		if (last)
-- 
2.45.GIT

[PATCH v5 6/7] t-reftable-pq: add test for index based comparison

[Chandra Pratap]

When comparing two entries, the priority queue as defined by
reftable/pq.{c, h} first compares the entries on the basis of
their ref-record's keys. If the keys turn out to be equal, the
comparison is then made on the basis of their update indices
(which are never equal).

In the current testing setup, only the case for comparison on
the basis of ref-record's keys is exercised. Add a test for
index-based comparison as well. Rename the existing test to
reflect its nature of only testing record-based comparison.

Mentored-by: Patrick Steinhardt <ps@pks.im>
Mentored-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
---
 t/unit-tests/t-reftable-pq.c | 43 ++++++++++++++++++++++++++++++++++--
 1 file changed, 41 insertions(+), 2 deletions(-)

diff --git a/t/unit-tests/t-reftable-pq.c b/t/unit-tests/t-reftable-pq.c
index 9230dd9b9e..23c3f6888b 100644
--- a/t/unit-tests/t-reftable-pq.c
+++ b/t/unit-tests/t-reftable-pq.c
@@ -18,7 +18,7 @@ static void merged_iter_pqueue_check(const struct merged_iter_pqueue *pq)
 	}
 }
 
-static void t_pq(void)
+static void t_pq_record(void)
 {
 	struct merged_iter_pqueue pq = { 0 };
 	struct reftable_record recs[54];
@@ -59,9 +59,48 @@ static void t_pq(void)
 	merged_iter_pqueue_release(&pq);
 }
 
+static void t_pq_index(void)
+{
+	struct merged_iter_pqueue pq = { 0 };
+	struct reftable_record recs[14];
+	char *last = NULL;
+	size_t N = ARRAY_SIZE(recs), i;
+
+	for (i = 0; i < N; i++) {
+		reftable_record_init(&recs[i], BLOCK_TYPE_REF);
+		recs[i].u.ref.refname = xstrdup("refs/heads/master");
+	}
+
+	for (i = 0; i < N; i++) {
+		struct pq_entry e = {
+			.rec = &recs[i],
+			.index = i,
+		};
+
+		merged_iter_pqueue_add(&pq, &e);
+		merged_iter_pqueue_check(&pq);
+	}
+
+	for (i = N - 1; !merged_iter_pqueue_is_empty(pq); i--) {
+		struct pq_entry e = merged_iter_pqueue_remove(&pq);
+		merged_iter_pqueue_check(&pq);
+
+		check(reftable_record_type(e.rec) == BLOCK_TYPE_REF);
+		check_int(e.index, ==, i);
+		if (last)
+			check_str(last, e.rec->u.ref.refname);
+		last = e.rec->u.ref.refname;
+	}
+
+	for (i = 0; i < N; i++)
+		reftable_record_release(&recs[i]);
+	merged_iter_pqueue_release(&pq);
+}
+
 int cmd_main(int argc, const char *argv[])
 {
-	TEST(t_pq(), "pq works");
+	TEST(t_pq_record(), "pq works with record-based comparison");
+	TEST(t_pq_index(), "pq works with index-based comparison");
 
 	return test_done();
 }
-- 
2.45.GIT

Re: [PATCH v5 6/7] t-reftable-pq: add test for index based comparison

[Patrick Steinhardt]

[-- Attachment #1: Type: text/plain, Size: 1451 bytes --]

On Tue, Jul 23, 2024 at 07:47:16PM +0530, Chandra Pratap wrote:
> diff --git a/t/unit-tests/t-reftable-pq.c b/t/unit-tests/t-reftable-pq.c
> index 9230dd9b9e..23c3f6888b 100644
> --- a/t/unit-tests/t-reftable-pq.c
> +++ b/t/unit-tests/t-reftable-pq.c
> @@ -18,7 +18,7 @@ static void merged_iter_pqueue_check(const struct merged_iter_pqueue *pq)
>  	}
>  }
>  
> -static void t_pq(void)
> +static void t_pq_record(void)
>  {
>  	struct merged_iter_pqueue pq = { 0 };
>  	struct reftable_record recs[54];
> @@ -59,9 +59,48 @@ static void t_pq(void)
>  	merged_iter_pqueue_release(&pq);
>  }
>  
> +static void t_pq_index(void)
> +{
> +	struct merged_iter_pqueue pq = { 0 };
> +	struct reftable_record recs[14];
> +	char *last = NULL;
> +	size_t N = ARRAY_SIZE(recs), i;
> +
> +	for (i = 0; i < N; i++) {
> +		reftable_record_init(&recs[i], BLOCK_TYPE_REF);
> +		recs[i].u.ref.refname = xstrdup("refs/heads/master");
> +	}
> +
> +	for (i = 0; i < N; i++) {
> +		struct pq_entry e = {
> +			.rec = &recs[i],
> +			.index = i,
> +		};
> +
> +		merged_iter_pqueue_add(&pq, &e);
> +		merged_iter_pqueue_check(&pq);
> +	}

One of those reasons that we use the modulo-loops in the other tests is
so that the order in which entries are added is mixed. Here we add them
in priority order already, so that makes the test less interesting. We
might thus want to do the same here and scramble the order a bit.

Patrick

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [PATCH v5 6/7] t-reftable-pq: add test for index based comparison

[Junio C Hamano]

Patrick Steinhardt <ps@pks.im> writes:

> One of those reasons that we use the modulo-loops in the other tests is
> so that the order in which entries are added is mixed. Here we add them
> in priority order already, so that makes the test less interesting. We
> might thus want to do the same here and scramble the order a bit.

Wouldn't modulo-loops mean the total number of elements must be
prime with the skip count, or something, which in turn means that it
is harder to test certain corner cases of the underlying data
structure (e.g. "what if the length is exactly a power of two?  A
power of two plus one?  A power of two minus one?"  etc.)

It certainly is much better than just inserting in the priority
order (or in the reverse priority order).

Thanks.

Re: [PATCH v5 6/7] t-reftable-pq: add test for index based comparison

[Patrick Steinhardt]

[-- Attachment #1: Type: text/plain, Size: 1224 bytes --]

On Wed, Jul 24, 2024 at 09:15:31AM -0700, Junio C Hamano wrote:
> Patrick Steinhardt <ps@pks.im> writes:
> 
> > One of those reasons that we use the modulo-loops in the other tests is
> > so that the order in which entries are added is mixed. Here we add them
> > in priority order already, so that makes the test less interesting. We
> > might thus want to do the same here and scramble the order a bit.
> 
> Wouldn't modulo-loops mean the total number of elements must be
> prime with the skip count, or something, which in turn means that it
> is harder to test certain corner cases of the underlying data
> structure (e.g. "what if the length is exactly a power of two?  A
> power of two plus one?  A power of two minus one?"  etc.)
> 
> It certainly is much better than just inserting in the priority
> order (or in the reverse priority order).

Yeah. I am not a huge fan of those modulo-loop as they hide what the
actual test data is myself, but they are already being used in those
tests anyway, and that's why I proposed them. The better option, in my
opinion, is to just make the test data explicit by for example looping
through an array of input data and inserting it one by one.

Patrick

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

[PATCH v5 7/7] t-reftable-pq: add tests for merged_iter_pqueue_top()

[Chandra Pratap]

merged_iter_pqueue_top() as defined by reftable/pq.{c, h} returns
the element at the top of a priority-queue's heap without removing
it. Since there are no tests for this function in the existing
setup, add tests for the same.

Mentored-by: Patrick Steinhardt <ps@pks.im>
Mentored-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
---
 t/unit-tests/t-reftable-pq.c | 49 ++++++++++++++++++++++++++++++++++++
 1 file changed, 49 insertions(+)

diff --git a/t/unit-tests/t-reftable-pq.c b/t/unit-tests/t-reftable-pq.c
index 23c3f6888b..84b0a3b708 100644
--- a/t/unit-tests/t-reftable-pq.c
+++ b/t/unit-tests/t-reftable-pq.c
@@ -18,6 +18,11 @@ static void merged_iter_pqueue_check(const struct merged_iter_pqueue *pq)
 	}
 }
 
+static int pq_entry_equal(struct pq_entry *a, struct pq_entry *b)
+{
+	return !reftable_record_cmp(a->rec, b->rec) && (a->index == b->index);
+}
+
 static void t_pq_record(void)
 {
 	struct merged_iter_pqueue pq = { 0 };
@@ -45,9 +50,11 @@ static void t_pq_record(void)
 	} while (i != 1);
 
 	while (!merged_iter_pqueue_is_empty(pq)) {
+		struct pq_entry top = merged_iter_pqueue_top(pq);
 		struct pq_entry e = merged_iter_pqueue_remove(&pq);
 		merged_iter_pqueue_check(&pq);
 
+		check(pq_entry_equal(&top, &e));
 		check(reftable_record_type(e.rec) == BLOCK_TYPE_REF);
 		if (last)
 			check_int(strcmp(last, e.rec->u.ref.refname), <, 0);
@@ -82,9 +89,11 @@ static void t_pq_index(void)
 	}
 
 	for (i = N - 1; !merged_iter_pqueue_is_empty(pq); i--) {
+		struct pq_entry top = merged_iter_pqueue_top(pq);
 		struct pq_entry e = merged_iter_pqueue_remove(&pq);
 		merged_iter_pqueue_check(&pq);
 
+		check(pq_entry_equal(&top, &e));
 		check(reftable_record_type(e.rec) == BLOCK_TYPE_REF);
 		check_int(e.index, ==, i);
 		if (last)
@@ -97,10 +106,50 @@ static void t_pq_index(void)
 	merged_iter_pqueue_release(&pq);
 }
 
+static void t_merged_iter_pqueue_top(void)
+{
+	struct merged_iter_pqueue pq = { 0 };
+	struct reftable_record recs[14];
+	size_t N = ARRAY_SIZE(recs), i;
+
+	for (i = 0; i < N; i++) {
+		reftable_record_init(&recs[i], BLOCK_TYPE_REF);
+		recs[i].u.ref.refname = xstrdup("refs/heads/master");
+	}
+
+	for (i = 0; i < N; i++) {
+		struct pq_entry e = {
+			.rec = &recs[i],
+			.index = i,
+		};
+
+		merged_iter_pqueue_add(&pq, &e);
+		merged_iter_pqueue_check(&pq);
+	}
+
+	for (i = N - 1; !merged_iter_pqueue_is_empty(pq); i--) {
+		struct pq_entry top = merged_iter_pqueue_top(pq);
+		struct pq_entry e = merged_iter_pqueue_remove(&pq);
+
+		merged_iter_pqueue_check(&pq);
+		check(pq_entry_equal(&top, &e));
+		check(reftable_record_equal(top.rec, &recs[i], GIT_SHA1_RAWSZ));
+		for (size_t j = 0; i < pq.len; j++) {
+			check(pq_less(&top, &pq.heap[j]));
+			check_int(top.index, >, j);
+		}
+	}
+
+	for (i = 0; i < N; i++)
+		reftable_record_release(&recs[i]);
+	merged_iter_pqueue_release(&pq);
+}
+
 int cmd_main(int argc, const char *argv[])
 {
 	TEST(t_pq_record(), "pq works with record-based comparison");
 	TEST(t_pq_index(), "pq works with index-based comparison");
+	TEST(t_merged_iter_pqueue_top(), "merged_iter_pqueue_top works");
 
 	return test_done();
 }
-- 
2.45.GIT

Re: [GSoC][PATCH v5 0/7] t: port reftable/pq_test.c to the unit testing framework

[Junio C Hamano]

Chandra Pratap <chandrapratap3519@gmail.com> writes:

> The reftable library comes with self tests, which are exercised
> as part of the usual end-to-end tests and are designed to
> observe the end-user visible effects of Git commands. What it
> exercises, however, is a better match for the unit-testing
> framework, merged at 8bf6fbd0 (Merge branch 'js/doc-unit-tests',
> 2023-12-09), which is designed to observe how low level
> implementation details, at the level of sequences of individual
> function calls, behave.
>
> Hence, port reftable/pq_test.c to the unit testing framework and
> improve upon the ported test. The first two patches in the series
> are preparatory cleanup, the third patch moves the test to the unit
> testing framework, and the rest of the patches improve upon the
> ported test.
>
> Mentored-by: Patrick Steinhardt <ps@pks.im>
> Mentored-by: Christian Couder <chriscool@tuxfamily.org>
> Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
>
> ---
> Changes in v5:
> - Rebase the branch on top of the  latest master branch

If you need to perform this rebase, please say _why_ you are
rebasing.

"A new rc was tagged so I rebased" is *not* a good reason.

"I wanted to use that new feature that was merged to 'master'
recently, which was not available when I wrote the previous
iteration of this series, hence I rebased" is a very good reason.

"Since I wrote the previous iteration, other unit test topics have
graduated, so there are trivial conflicts in Makefile when merging
this topic" is usually not a good reason, especially when the same
conflicts with these other unit test topics are already resolved
when your previous iteration is merged to 'seen'.

If there isn't a reason worth mentioning why you are rebasing, then
please do not rebase.  It is distracting.

> - Rename tests according to unit-tests' conventions
> - remove 'pq_test_main()' from reftable/reftable-test.h
>
> CI/PR for v5: https://github.com/gitgitgadget/git/pull/1745

By the way, I still haven't got any answer to a question I asked
long ago on this series, wrt possibly unifying this pq and another
pq we already use elsewhere in our codebase.  If we are butchering
what we borrowed from elsewhere and store in reftable/. directory
and taking responsibility of maintaining it ourselves, we probably
should consider larger refactoring and cleaning up, and part of it
we may end up discarding this pq implementation, making the unit
testing on it a wasted effort.

Thanks.

> Chandra Pratap(7):
> reftable: remove unncessary curly braces in reftable/pq.c
> reftable: change the type of array indices to 'size_t' in reftable/pq.c
> t: move reftable/pq_test.c to the unit testing framework
> t-reftable-pq: make merged_iter_pqueue_check() static
> t-reftable-pq: make merged_iter_pqueue_check() callable by reference
> t-reftable-pq: add test for index based comparison
> t-reftable-pq: add tests for merged_iter_pqueue_top()
>
> Makefile                     |   2 +-
> reftable/pq.c                |  29 +++-----
> reftable/pq.h                |   1 -
> reftable/pq_test.c           |  74 ---------------------
> reftable/reftable-tests.h    |   1 -
> t/helper/test-reftable.c     |   1 -
> t/unit-tests/t-reftable-pq.c | 155 +++++++++++++++++++++++++++++++++++++++++++
> 7 files changed, 166 insertions(+), 97 deletions(-)
>
> Range-diff against v4:
> <rebase commits>
>   1:  d3c5605ea2 = 382:  acd9d26aaf reftable: remove unncessary curly braces in reftable/pq.c
>   2:  3c333e7770 = 383:  2e0986207b reftable: change the type of array indices to 'size_t' in reftable/pq.c
>   3:  bf547f705a ! 384:  df06b6d604 t: move reftable/pq_test.c to the unit testing framework
>     @@ Commit message
>          t: move reftable/pq_test.c to the unit testing framework
>
>          reftable/pq_test.c exercises a priority queue defined by
>     -    reftable/pq.{c, h}. Migrate reftable/pq_test.c to the unit
>     -    testing framework. Migration involves refactoring the tests
>     -    to use the unit testing framework instead of reftable's test
>     -    framework.
>     +    reftable/pq.{c, h}. Migrate reftable/pq_test.c to the unit testing
>     +    framework. Migration involves refactoring the tests to use the unit
>     +    testing framework instead of reftable's test framework, and
>     +    renaming the tests to align with unit-tests' standards.
>
>          Mentored-by: Patrick Steinhardt <ps@pks.im>
>          Mentored-by: Christian Couder <chriscool@tuxfamily.org>
>          Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
>
>       ## Makefile ##
>     -@@ Makefile: THIRD_PARTY_SOURCES += sha1dc/%
>     - UNIT_TEST_PROGRAMS += t-ctype
>     - UNIT_TEST_PROGRAMS += t-mem-pool
>     +@@ Makefile: UNIT_TEST_PROGRAMS += t-oidmap
>     + UNIT_TEST_PROGRAMS += t-oidtree
>       UNIT_TEST_PROGRAMS += t-prio-queue
>     + UNIT_TEST_PROGRAMS += t-reftable-basics
>      +UNIT_TEST_PROGRAMS += t-reftable-pq
>     + UNIT_TEST_PROGRAMS += t-reftable-record
>       UNIT_TEST_PROGRAMS += t-strbuf
>       UNIT_TEST_PROGRAMS += t-strcmp-offset
>     - UNIT_TEST_PROGRAMS += t-trailer
>     -@@ Makefile: REFTABLE_TEST_OBJS += reftable/basics_test.o
>     +@@ Makefile: REFTABLE_OBJS += reftable/writer.o
>       REFTABLE_TEST_OBJS += reftable/block_test.o
>       REFTABLE_TEST_OBJS += reftable/dump.o
>       REFTABLE_TEST_OBJS += reftable/merged_test.o
>      -REFTABLE_TEST_OBJS += reftable/pq_test.o
>     - REFTABLE_TEST_OBJS += reftable/record_test.o
>       REFTABLE_TEST_OBJS += reftable/readwrite_test.o
>       REFTABLE_TEST_OBJS += reftable/stack_test.o
>     + REFTABLE_TEST_OBJS += reftable/test_framework.o
>     +
>     + ## reftable/reftable-tests.h ##
>     +@@ reftable/reftable-tests.h: license that can be found in the LICENSE file or at
>     + int basics_test_main(int argc, const char **argv);
>     + int block_test_main(int argc, const char **argv);
>     + int merged_test_main(int argc, const char **argv);
>     +-int pq_test_main(int argc, const char **argv);
>     + int record_test_main(int argc, const char **argv);
>     + int readwrite_test_main(int argc, const char **argv);
>     + int stack_test_main(int argc, const char **argv);
>
>       ## t/helper/test-reftable.c ##
>      @@ t/helper/test-reftable.c: int cmd__reftable(int argc, const char **argv)
>     - 	record_test_main(argc, argv);
>     + 	/* test from simple to complex. */
>       	block_test_main(argc, argv);
>       	tree_test_main(argc, argv);
>      -	pq_test_main(argc, argv);
>     @@ t/unit-tests/t-reftable-pq.c: license that can be found in the LICENSE file or a
>       	}
>       }
>
>     - static void test_pq(void)
>     +-static void test_pq(void)
>     ++static void t_pq(void)
>       {
>      -	struct merged_iter_pqueue pq = { NULL };
>      +	struct merged_iter_pqueue pq = { 0 };
>     @@ t/unit-tests/t-reftable-pq.c: static void test_pq(void)
>       {
>      -	RUN_TEST(test_pq);
>      -	return 0;
>     -+	TEST(test_pq(), "pq works");
>     ++	TEST(t_pq(), "pq works");
>      +
>      +	return test_done();
>       }
>   4:  7dd3a2b27f = 385:  40745ab18e t-reftable-pq: make merged_iter_pqueue_check() static
>   5:  c803e7adfc ! 386:  ee8432ac4a t-reftable-pq: make merged_iter_pqueue_check() callable by reference
>     @@ t/unit-tests/t-reftable-pq.c: license that can be found in the LICENSE file or a
>       	}
>       }
>
>     -@@ t/unit-tests/t-reftable-pq.c: static void test_pq(void)
>     +@@ t/unit-tests/t-reftable-pq.c: static void t_pq(void)
>       		};
>
>       		merged_iter_pqueue_add(&pq, &e);
>   6:  0b03f3567d ! 387:  94a77f5a60 t-reftable-pq: add test for index based comparison
>     @@ t/unit-tests/t-reftable-pq.c: static void merged_iter_pqueue_check(const struct
>       	}
>       }
>
>     --static void test_pq(void)
>     -+static void test_pq_record(void)
>     +-static void t_pq(void)
>     ++static void t_pq_record(void)
>       {
>       	struct merged_iter_pqueue pq = { 0 };
>       	struct reftable_record recs[54];
>     -@@ t/unit-tests/t-reftable-pq.c: static void test_pq(void)
>     +@@ t/unit-tests/t-reftable-pq.c: static void t_pq(void)
>       	merged_iter_pqueue_release(&pq);
>       }
>
>     -+static void test_pq_index(void)
>     ++static void t_pq_index(void)
>      +{
>      +	struct merged_iter_pqueue pq = { 0 };
>      +	struct reftable_record recs[14];
>     @@ t/unit-tests/t-reftable-pq.c: static void test_pq(void)
>      +
>       int cmd_main(int argc, const char *argv[])
>       {
>     --	TEST(test_pq(), "pq works");
>     -+	TEST(test_pq_record(), "pq works with record-based comparison");
>     -+	TEST(test_pq_index(), "pq works with index-based comparison");
>     +-	TEST(t_pq(), "pq works");
>     ++	TEST(t_pq_record(), "pq works with record-based comparison");
>     ++	TEST(t_pq_index(), "pq works with index-based comparison");
>
>       	return test_done();
>       }
>   7:  0cdfa6221e ! 388:  9a76f87bd1 t-reftable-pq: add tests for merged_iter_pqueue_top()
>     @@ t/unit-tests/t-reftable-pq.c: static void merged_iter_pqueue_check(const struct
>      +	return !reftable_record_cmp(a->rec, b->rec) && (a->index == b->index);
>      +}
>      +
>     - static void test_pq_record(void)
>     + static void t_pq_record(void)
>       {
>       	struct merged_iter_pqueue pq = { 0 };
>     -@@ t/unit-tests/t-reftable-pq.c: static void test_pq_record(void)
>     +@@ t/unit-tests/t-reftable-pq.c: static void t_pq_record(void)
>       	} while (i != 1);
>
>       	while (!merged_iter_pqueue_is_empty(pq)) {
>     @@ t/unit-tests/t-reftable-pq.c: static void test_pq_record(void)
>       		check(reftable_record_type(e.rec) == BLOCK_TYPE_REF);
>       		if (last)
>       			check_int(strcmp(last, e.rec->u.ref.refname), <, 0);
>     -@@ t/unit-tests/t-reftable-pq.c: static void test_pq_index(void)
>     +@@ t/unit-tests/t-reftable-pq.c: static void t_pq_index(void)
>       	}
>
>       	for (i = N - 1; !merged_iter_pqueue_is_empty(pq); i--) {
>     @@ t/unit-tests/t-reftable-pq.c: static void test_pq_index(void)
>       		check(reftable_record_type(e.rec) == BLOCK_TYPE_REF);
>       		check_int(e.index, ==, i);
>       		if (last)
>     -@@ t/unit-tests/t-reftable-pq.c: static void test_pq_index(void)
>     +@@ t/unit-tests/t-reftable-pq.c: static void t_pq_index(void)
>       	merged_iter_pqueue_release(&pq);
>       }
>
>     -+static void test_merged_iter_pqueue_top(void)
>     ++static void t_merged_iter_pqueue_top(void)
>      +{
>      +	struct merged_iter_pqueue pq = { 0 };
>      +	struct reftable_record recs[14];
>     @@ t/unit-tests/t-reftable-pq.c: static void test_pq_index(void)
>      +
>       int cmd_main(int argc, const char *argv[])
>       {
>     - 	TEST(test_pq_record(), "pq works with record-based comparison");
>     - 	TEST(test_pq_index(), "pq works with index-based comparison");
>     -+	TEST(test_merged_iter_pqueue_top(), "merged_iter_pqueue_top works");
>     + 	TEST(t_pq_record(), "pq works with record-based comparison");
>     + 	TEST(t_pq_index(), "pq works with index-based comparison");
>     ++	TEST(t_merged_iter_pqueue_top(), "merged_iter_pqueue_top works");
>
>       	return test_done();
>       }

Re: [GSoC][PATCH v5 0/7] t: port reftable/pq_test.c to the unit testing framework

[Chandra Pratap]

On Tue, 23 Jul 2024 at 22:39, Junio C Hamano <gitster@pobox.com> wrote:
>
> Chandra Pratap <chandrapratap3519@gmail.com> writes:
>
> > The reftable library comes with self tests, which are exercised
> > as part of the usual end-to-end tests and are designed to
> > observe the end-user visible effects of Git commands. What it
> > exercises, however, is a better match for the unit-testing
> > framework, merged at 8bf6fbd0 (Merge branch 'js/doc-unit-tests',
> > 2023-12-09), which is designed to observe how low level
> > implementation details, at the level of sequences of individual
> > function calls, behave.
> >
> > Hence, port reftable/pq_test.c to the unit testing framework and
> > improve upon the ported test. The first two patches in the series
> > are preparatory cleanup, the third patch moves the test to the unit
> > testing framework, and the rest of the patches improve upon the
> > ported test.
> >
> > Mentored-by: Patrick Steinhardt <ps@pks.im>
> > Mentored-by: Christian Couder <chriscool@tuxfamily.org>
> > Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
> >
> > ---
> > Changes in v5:
> > - Rebase the branch on top of the  latest master branch
>
> If you need to perform this rebase, please say _why_ you are
> rebasing.
>
> "A new rc was tagged so I rebased" is *not* a good reason.
>
> "I wanted to use that new feature that was merged to 'master'
> recently, which was not available when I wrote the previous
> iteration of this series, hence I rebased" is a very good reason.
>
> "Since I wrote the previous iteration, other unit test topics have
> graduated, so there are trivial conflicts in Makefile when merging
> this topic" is usually not a good reason, especially when the same
> conflicts with these other unit test topics are already resolved
> when your previous iteration is merged to 'seen'.
>
> If there isn't a reason worth mentioning why you are rebasing, then
> please do not rebase.  It is distracting.

Oh, okay.

> > - Rename tests according to unit-tests' conventions
> > - remove 'pq_test_main()' from reftable/reftable-test.h
> >
> > CI/PR for v5: https://github.com/gitgitgadget/git/pull/1745
>
> By the way, I still haven't got any answer to a question I asked
> long ago on this series, wrt possibly unifying this pq and another
> pq we already use elsewhere in our codebase.  If we are butchering
> what we borrowed from elsewhere and store in reftable/. directory
> and taking responsibility of maintaining it ourselves, we probably
> should consider larger refactoring and cleaning up, and part of it
> we may end up discarding this pq implementation, making the unit
> testing on it a wasted effort.
>
> Thanks.
>

I did talk about this with Patrick and Christian on a private slack channel
a few weeks ago and here is how that conversation went:

Me: Hey, I wanted to talk about the message from Junio the other day.
It is true that through this project, we are modifying the reftable directory
to a point that it is no longer easily usable by someone from outside. If
that is the direction we want to take, wouldn't it make more sense to get
rid of reftable/pq.{c, h} altogether and use Git's prio-queue instead?

Christian: Yeah, I think the direction the Git project wants to take is to
integrate the reftable code more and more with the Git code. On the other
hand, there are libification projects which are trying to split parts of the
Git code into libraries usable by other projects. But I don't think each of
these libraries should have their own test framework, their own prio-queue
implementation, their own string implementation, etc. So, even if I am not
sure about the end result, I think it would be ok to modify the reftable code
so that it uses the Git's prio queue and maybe other Git data structures.
But I'd like Patrick to confirm, and the list to agree to this. So I'd
rather wait
until Patrick is back from his vacation before doing things like replacing
reftable/pq.{c, h} with Git's prio-queue.

Patrick: Just chiming in real quick: while the reftable library is
currently in a
position where it cannot be used standalone by other projects, I'd very much
like to move into the direction of making it completely standalone again so
that we can adapt e.g. libgit2 to use it. So I rather want to move the other
direction over time and re-establish a proper boundary between reftable
library and the remainder of Git. I don't really think that this needs to impact
the reftable tests though. Git is the upstream of the reftable
library, and I don't
see much of a point why every other project should carry the same tests, too.

---snip---

Re: [GSoC][PATCH v5 0/7] t: port reftable/pq_test.c to the unit testing framework

[Christian Couder]

On Wed, Jul 24, 2024 at 7:12 AM Chandra Pratap
<chandrapratap3519@gmail.com> wrote:
>
> On Tue, 23 Jul 2024 at 22:39, Junio C Hamano <gitster@pobox.com> wrote:

> > > - Rename tests according to unit-tests' conventions
> > > - remove 'pq_test_main()' from reftable/reftable-test.h
> > >
> > > CI/PR for v5: https://github.com/gitgitgadget/git/pull/1745
> >
> > By the way, I still haven't got any answer to a question I asked
> > long ago on this series, wrt possibly unifying this pq and another
> > pq we already use elsewhere in our codebase.  If we are butchering
> > what we borrowed from elsewhere and store in reftable/. directory
> > and taking responsibility of maintaining it ourselves, we probably
> > should consider larger refactoring and cleaning up, and part of it
> > we may end up discarding this pq implementation, making the unit
> > testing on it a wasted effort.

I agree it might have been better to start by replacing the pq
implementation in reftable/ with our own first, as there would be no
need for this patch series, but Chandra's GSoC is about replacing the
unit test framework in reftable/ with our own which is still valuable.
And I think that at this point it is just simpler to not get
distracted by replacing the pq implementation now. It's also not like
changing the unit test framework would make replacing the pq
implementation harder.

> I did talk about this with Patrick and Christian on a private slack channel
> a few weeks ago and here is how that conversation went:
>
> Me: Hey, I wanted to talk about the message from Junio the other day.
> It is true that through this project, we are modifying the reftable directory
> to a point that it is no longer easily usable by someone from outside. If
> that is the direction we want to take, wouldn't it make more sense to get
> rid of reftable/pq.{c, h} altogether and use Git's prio-queue instead?
>
> Christian: Yeah, I think the direction the Git project wants to take is to
> integrate the reftable code more and more with the Git code. On the other
> hand, there are libification projects which are trying to split parts of the
> Git code into libraries usable by other projects. But I don't think each of
> these libraries should have their own test framework, their own prio-queue
> implementation, their own string implementation, etc. So, even if I am not
> sure about the end result, I think it would be ok to modify the reftable code
> so that it uses the Git's prio queue and maybe other Git data structures.
> But I'd like Patrick to confirm, and the list to agree to this. So I'd
> rather wait
> until Patrick is back from his vacation before doing things like replacing
> reftable/pq.{c, h} with Git's prio-queue.

Yeah, if it had been discussed and agreed on earlier, I think
replacing the pq implementation would have made sense. Now I think
it's a bit late at this stage in Chandra's GSoC to go in this
direction though. I think it's better if he can focus on finishing to
replace the unit test framework.

Re: [GSoC][PATCH v5 0/7] t: port reftable/pq_test.c to the unit testing framework

[Chandra Pratap]

On Wed, 24 Jul 2024 at 12:48, Christian Couder
<christian.couder@gmail.com> wrote:
>
> On Wed, Jul 24, 2024 at 7:12 AM Chandra Pratap
> <chandrapratap3519@gmail.com> wrote:
> >
> > On Tue, 23 Jul 2024 at 22:39, Junio C Hamano <gitster@pobox.com> wrote:
>
> > > > - Rename tests according to unit-tests' conventions
> > > > - remove 'pq_test_main()' from reftable/reftable-test.h
> > > >
> > > > CI/PR for v5: https://github.com/gitgitgadget/git/pull/1745
> > >
> > > By the way, I still haven't got any answer to a question I asked
> > > long ago on this series, wrt possibly unifying this pq and another
> > > pq we already use elsewhere in our codebase.  If we are butchering
> > > what we borrowed from elsewhere and store in reftable/. directory
> > > and taking responsibility of maintaining it ourselves, we probably
> > > should consider larger refactoring and cleaning up, and part of it
> > > we may end up discarding this pq implementation, making the unit
> > > testing on it a wasted effort.
>
> I agree it might have been better to start by replacing the pq
> implementation in reftable/ with our own first, as there would be no
> need for this patch series, but Chandra's GSoC is about replacing the
> unit test framework in reftable/ with our own which is still valuable.
> And I think that at this point it is just simpler to not get
> distracted by replacing the pq implementation now. It's also not like
> changing the unit test framework would make replacing the pq
> implementation harder.
>
> > I did talk about this with Patrick and Christian on a private slack channel
> > a few weeks ago and here is how that conversation went:
> >
> > Me: Hey, I wanted to talk about the message from Junio the other day.
> > It is true that through this project, we are modifying the reftable directory
> > to a point that it is no longer easily usable by someone from outside. If
> > that is the direction we want to take, wouldn't it make more sense to get
> > rid of reftable/pq.{c, h} altogether and use Git's prio-queue instead?
> >
> > Christian: Yeah, I think the direction the Git project wants to take is to
> > integrate the reftable code more and more with the Git code. On the other
> > hand, there are libification projects which are trying to split parts of the
> > Git code into libraries usable by other projects. But I don't think each of
> > these libraries should have their own test framework, their own prio-queue
> > implementation, their own string implementation, etc. So, even if I am not
> > sure about the end result, I think it would be ok to modify the reftable code
> > so that it uses the Git's prio queue and maybe other Git data structures.
> > But I'd like Patrick to confirm, and the list to agree to this. So I'd
> > rather wait
> > until Patrick is back from his vacation before doing things like replacing
> > reftable/pq.{c, h} with Git's prio-queue.
>
> Yeah, if it had been discussed and agreed on earlier, I think
> replacing the pq implementation would have made sense. Now I think
> it's a bit late at this stage in Chandra's GSoC to go in this
> direction though. I think it's better if he can focus on finishing to
> replace the unit test framework.

I'm actually more or less done with porting most of the reftable
tests to the unit test framework and it shouldn't be long before
patches for rest of the tests see the mailing list, so I can definitely
make time for other endeavors like these.

The only thing that I think is holding us back from making a change
like what Junio suggests is 'how far are we willing to butcher our copy
of reftable/?' From what Patrick said earlier, I think the answer to that is
'it is fine to modify reftable/ tests because they don't need to be uniform
across all implementations of reftable, but modifying other parts to be
more dependent on Git's internals is a no-go.'

Re: [GSoC][PATCH v5 0/7] t: port reftable/pq_test.c to the unit testing framework

[Patrick Steinhardt]

[-- Attachment #1: Type: text/plain, Size: 3511 bytes --]

On Wed, Jul 24, 2024 at 09:17:55AM +0200, Christian Couder wrote:
> On Wed, Jul 24, 2024 at 7:12 AM Chandra Pratap
> <chandrapratap3519@gmail.com> wrote:
> > On Tue, 23 Jul 2024 at 22:39, Junio C Hamano <gitster@pobox.com> wrote:
> > I did talk about this with Patrick and Christian on a private slack channel
> > a few weeks ago and here is how that conversation went:
> >
> > Me: Hey, I wanted to talk about the message from Junio the other day.
> > It is true that through this project, we are modifying the reftable directory
> > to a point that it is no longer easily usable by someone from outside. If
> > that is the direction we want to take, wouldn't it make more sense to get
> > rid of reftable/pq.{c, h} altogether and use Git's prio-queue instead?
> >
> > Christian: Yeah, I think the direction the Git project wants to take is to
> > integrate the reftable code more and more with the Git code. On the other
> > hand, there are libification projects which are trying to split parts of the
> > Git code into libraries usable by other projects. But I don't think each of
> > these libraries should have their own test framework, their own prio-queue
> > implementation, their own string implementation, etc. So, even if I am not
> > sure about the end result, I think it would be ok to modify the reftable code
> > so that it uses the Git's prio queue and maybe other Git data structures.
> > But I'd like Patrick to confirm, and the list to agree to this. So I'd
> > rather wait
> > until Patrick is back from his vacation before doing things like replacing
> > reftable/pq.{c, h} with Git's prio-queue.
> 
> Yeah, if it had been discussed and agreed on earlier, I think
> replacing the pq implementation would have made sense. Now I think
> it's a bit late at this stage in Chandra's GSoC to go in this
> direction though. I think it's better if he can focus on finishing to
> replace the unit test framework.

Replacing the priority queue with the one we already have will create
additional work in the future when we want to get the reftable library
back into a state where it can be used as a standalone library again. I
know that it's currently a mess anyway, but I've heard from multiple
folks already who are interested in using the reftable library in their
own C projects (most importantly libgit2).

If we want Git to be the reftable upstream for such projects, then we
should play nice and not make their lifes harder. I plan to work on
portability work as soon as somebody properly commits to integrating
reftables into their project. This will probably come in the form of:

  - Removing all Git-specific includes in the "reftable/" directory.

  - Declaring a list of "shim" functions and types that users of the
    reftable library need to use.

  - Implementing those shim functions for Git.

Of course, those shims will closely follow the interfaces that we have
in Git. E.g. there will shims for "strbuf", the tempfile interface, and
everything else that we currently use in the reftable library. So
ultimately, I expect that the shim implementations will simply look like
the following:

```
typedef struct strbuf reftable_buf;

static inline void reftable_buf_add(struct strbuf reftable_buf *buf,
                                    const void *data, size_t len)
{
    strbuf_add(buf, data, len);
}
```

While we could also shim out the priority queue, I don't really think
that it is worth it.

Patrick

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [GSoC][PATCH v5 0/7] t: port reftable/pq_test.c to the unit testing framework

[Junio C Hamano]

Patrick Steinhardt <ps@pks.im> writes:

> Of course, those shims will closely follow the interfaces that we have
> in Git. E.g. there will shims for "strbuf", the tempfile interface, and
> everything else that we currently use in the reftable library. So
> ultimately, I expect that the shim implementations will simply look like
> the following:
>
> ```
> typedef struct strbuf reftable_buf;
>
> static inline void reftable_buf_add(struct strbuf reftable_buf *buf,
>                                     const void *data, size_t len)
> {
>     strbuf_add(buf, data, len);
> }
> ```
>
> While we could also shim out the priority queue, I don't really think
> that it is worth it.

OK, I am fine if somebody wants to spend cycles to move the
reftable_pq tests to the unit-test framework.  I just wasn't sure
what the future plans were, and one obvious direction to replace
reftable_pq would invalidate such work, and I wanted to make sure
everybody involved in this effort is aware of that.

Thanks.

[GSoC][PATCH v6 0/7] t: port reftable/pq_test.c to the unit testing framework

[Chandra Pratap]

The reftable library comes with self tests, which are exercised
as part of the usual end-to-end tests and are designed to
observe the end-user visible effects of Git commands. What it
exercises, however, is a better match for the unit-testing
framework, merged at 8bf6fbd0 (Merge branch 'js/doc-unit-tests',
2023-12-09), which is designed to observe how low level
implementation details, at the level of sequences of individual
function calls, behave.

Hence, port reftable/pq_test.c to the unit testing framework and
improve upon the ported test. The first two patches in the series
are preparatory cleanup, the third patch moves the test to the unit
testing framework, and the rest of the patches improve upon the
ported test.

Mentored-by: Patrick Steinhardt <ps@pks.im>
Mentored-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>

---
Changes in v6:
- Use modulo loop to pseudo-randomly insert elements in
  t_pq_index() in patch 6.
- Use 'xstrfmt' for refnames instead of using a 'strbuf'
  in t_pq_record() in patch 6.
- Use string literals instead of 'xstrdup' for refnames in
  t_pq_index() and t_merged_iter_pqueue_top() in patch 6 & 7.
- Use modulo loop to pseudo-randomly insert elements in
  t_merged_iter_pqueue_top() in patch 7

CI/PR for v6: https://github.com/gitgitgadget/git/pull/1745

Chandra Pratap(7):
reftable: remove unncessary curly braces in reftable/pq.c
reftable: change the type of array indices to 'size_t' in reftable/pq.c
t: move reftable/pq_test.c to the unit testing framework
t-reftable-pq: make merged_iter_pqueue_check() static
t-reftable-pq: make merged_iter_pqueue_check() callable by reference
t-reftable-pq: add test for index based comparison
t-reftable-pq: add tests for merged_iter_pqueue_top()

Makefile                     |   2 +-
reftable/pq.c                |  29 +++-----
reftable/pq.h                |   1 -
reftable/pq_test.c           |  74 ---------------------
reftable/reftable-tests.h    |   1 -
t/helper/test-reftable.c     |   1 -
t/unit-tests/t-reftable-pq.c | 154 +++++++++++++++++++++++++++++++++++++++++++
7 files changed, 165 insertions(+), 97 deletions(-)

Range-diff against v5:
1:  94a77f5a60 ! 1:  f5c30187e1 t-reftable-pq: add test for index based comparison
    @@ Commit message
         index-based comparison as well. Rename the existing test to
         reflect its nature of only testing record-based comparison.

    +    While at it, replace 'strbuf_detach' with 'xstrfmt' to assign
    +    refnames in the existing test. This makes the test conciser.
    +
         Mentored-by: Patrick Steinhardt <ps@pks.im>
         Mentored-by: Christian Couder <chriscool@tuxfamily.org>
         Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
    @@ t/unit-tests/t-reftable-pq.c: static void merged_iter_pqueue_check(const struct
      {
      	struct merged_iter_pqueue pq = { 0 };
      	struct reftable_record recs[54];
    +@@ t/unit-tests/t-reftable-pq.c: static void t_pq(void)
    + 	char *last = NULL;
    +
    + 	for (i = 0; i < N; i++) {
    +-		struct strbuf refname = STRBUF_INIT;
    +-		strbuf_addf(&refname, "%02"PRIuMAX, (uintmax_t)i);
    +-
    + 		reftable_record_init(&recs[i], BLOCK_TYPE_REF);
    +-		recs[i].u.ref.refname = strbuf_detach(&refname, NULL);
    ++		recs[i].u.ref.refname = xstrfmt("%02"PRIuMAX, (uintmax_t)i);
    + 	}
    +
    + 	i = 1;
     @@ t/unit-tests/t-reftable-pq.c: static void t_pq(void)
      	merged_iter_pqueue_release(&pq);
      }
    @@ t/unit-tests/t-reftable-pq.c: static void t_pq(void)
     +static void t_pq_index(void)
     +{
     +	struct merged_iter_pqueue pq = { 0 };
    -+	struct reftable_record recs[14];
    ++	struct reftable_record recs[13];
     +	char *last = NULL;
     +	size_t N = ARRAY_SIZE(recs), i;
     +
     +	for (i = 0; i < N; i++) {
     +		reftable_record_init(&recs[i], BLOCK_TYPE_REF);
    -+		recs[i].u.ref.refname = xstrdup("refs/heads/master");
    ++		recs[i].u.ref.refname = (char *) "refs/heads/master";
     +	}
     +
    -+	for (i = 0; i < N; i++) {
    ++	i = 1;
    ++	do {
     +		struct pq_entry e = {
     +			.rec = &recs[i],
     +			.index = i,
    @@ t/unit-tests/t-reftable-pq.c: static void t_pq(void)
     +
     +		merged_iter_pqueue_add(&pq, &e);
     +		merged_iter_pqueue_check(&pq);
    ++		i = (i * 7) % N;
     +	}
    ++	while (i != 1);
     +
    -+	for (i = N - 1; !merged_iter_pqueue_is_empty(pq); i--) {
    ++	for (i = N - 1; i > 0; i--) {
     +		struct pq_entry e = merged_iter_pqueue_remove(&pq);
     +		merged_iter_pqueue_check(&pq);
     +
    @@ t/unit-tests/t-reftable-pq.c: static void t_pq(void)
     +		last = e.rec->u.ref.refname;
     +	}
     +
    -+	for (i = 0; i < N; i++)
    -+		reftable_record_release(&recs[i]);
     +	merged_iter_pqueue_release(&pq);
     +}
     +
2:  9a76f87bd1 ! 2:  394540a789 t-reftable-pq: add tests for merged_iter_pqueue_top()
    @@ t/unit-tests/t-reftable-pq.c: static void t_pq_record(void)
      		if (last)
      			check_int(strcmp(last, e.rec->u.ref.refname), <, 0);
     @@ t/unit-tests/t-reftable-pq.c: static void t_pq_index(void)
    - 	}
    + 	while (i != 1);

    - 	for (i = N - 1; !merged_iter_pqueue_is_empty(pq); i--) {
    + 	for (i = N - 1; i > 0; i--) {
     +		struct pq_entry top = merged_iter_pqueue_top(pq);
      		struct pq_entry e = merged_iter_pqueue_remove(&pq);
      		merged_iter_pqueue_check(&pq);
    @@ t/unit-tests/t-reftable-pq.c: static void t_pq_index(void)
     +static void t_merged_iter_pqueue_top(void)
     +{
     +	struct merged_iter_pqueue pq = { 0 };
    -+	struct reftable_record recs[14];
    ++	struct reftable_record recs[13];
     +	size_t N = ARRAY_SIZE(recs), i;
     +
     +	for (i = 0; i < N; i++) {
     +		reftable_record_init(&recs[i], BLOCK_TYPE_REF);
    -+		recs[i].u.ref.refname = xstrdup("refs/heads/master");
    ++		recs[i].u.ref.refname = (char *) "refs/heads/master";
     +	}
     +
    -+	for (i = 0; i < N; i++) {
    ++	i = 1;
    ++	do {
     +		struct pq_entry e = {
     +			.rec = &recs[i],
     +			.index = i,
    @@ t/unit-tests/t-reftable-pq.c: static void t_pq_index(void)
     +
     +		merged_iter_pqueue_add(&pq, &e);
     +		merged_iter_pqueue_check(&pq);
    ++		i = (i * 7) % N;
     +	}
    ++	while (i != 1);
     +
    -+	for (i = N - 1; !merged_iter_pqueue_is_empty(pq); i--) {
    ++	for (i = N - 1; i > 0; i--) {
     +		struct pq_entry top = merged_iter_pqueue_top(pq);
     +		struct pq_entry e = merged_iter_pqueue_remove(&pq);
     +
    @@ t/unit-tests/t-reftable-pq.c: static void t_pq_index(void)
     +		}
     +	}
     +
    -+	for (i = 0; i < N; i++)
    -+		reftable_record_release(&recs[i]);
     +	merged_iter_pqueue_release(&pq);
     +}
     +

[PATCH v6 1/7] reftable: remove unncessary curly braces in reftable/pq.c

[Chandra Pratap]

According to Documentation/CodingGuidelines, control-flow statements
with a single line as their body must omit curly braces. Make
reftable/pq.c conform to this guideline. Besides that, remove
unnecessary newlines and variable assignment.

Mentored-by: Patrick Steinhardt <ps@pks.im>
Mentored-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
---
 reftable/pq.c | 17 ++++-------------
 1 file changed, 4 insertions(+), 13 deletions(-)

diff --git a/reftable/pq.c b/reftable/pq.c
index 7fb45d8c60..1a180c5fa6 100644
--- a/reftable/pq.c
+++ b/reftable/pq.c
@@ -27,22 +27,16 @@ struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq)
 	pq->heap[0] = pq->heap[pq->len - 1];
 	pq->len--;
 
-	i = 0;
 	while (i < pq->len) {
 		int min = i;
 		int j = 2 * i + 1;
 		int k = 2 * i + 2;
-		if (j < pq->len && pq_less(&pq->heap[j], &pq->heap[i])) {
+		if (j < pq->len && pq_less(&pq->heap[j], &pq->heap[i]))
 			min = j;
-		}
-		if (k < pq->len && pq_less(&pq->heap[k], &pq->heap[min])) {
+		if (k < pq->len && pq_less(&pq->heap[k], &pq->heap[min]))
 			min = k;
-		}
-
-		if (min == i) {
+		if (min == i)
 			break;
-		}
-
 		SWAP(pq->heap[i], pq->heap[min]);
 		i = min;
 	}
@@ -60,12 +54,9 @@ void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry
 	i = pq->len - 1;
 	while (i > 0) {
 		int j = (i - 1) / 2;
-		if (pq_less(&pq->heap[j], &pq->heap[i])) {
+		if (pq_less(&pq->heap[j], &pq->heap[i]))
 			break;
-		}
-
 		SWAP(pq->heap[j], pq->heap[i]);
-
 		i = j;
 	}
 }
-- 
2.45.GIT

Re: [PATCH v6 1/7] reftable: remove unncessary curly braces in reftable/pq.c

[Kristoffer Haugsbakk]

On Thu, Jul 25, 2024, at 11:25, Chandra Pratap wrote:
> […]

s/unncessary/unnecessary/

(the subject line)

-- 
Kristoffer Haugsbakk

[PATCH v6 2/7] reftable: change the type of array indices to 'size_t' in reftable/pq.c

[Chandra Pratap]

The variables 'i', 'j', 'k' and 'min' are used as indices for
'pq->heap', which is an array. Additionally, 'pq->len' is of
type 'size_t' and is often used to assign values to these
variables. Hence, change the type of these variables from 'int'
to 'size_t'.

Mentored-by: Patrick Steinhardt <ps@pks.im>
Mentored-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
---
 reftable/pq.c | 12 ++++++------
 1 file changed, 6 insertions(+), 6 deletions(-)

diff --git a/reftable/pq.c b/reftable/pq.c
index 1a180c5fa6..2b5b7d1c0e 100644
--- a/reftable/pq.c
+++ b/reftable/pq.c
@@ -22,15 +22,15 @@ int pq_less(struct pq_entry *a, struct pq_entry *b)
 
 struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq)
 {
-	int i = 0;
+	size_t i = 0;
 	struct pq_entry e = pq->heap[0];
 	pq->heap[0] = pq->heap[pq->len - 1];
 	pq->len--;
 
 	while (i < pq->len) {
-		int min = i;
-		int j = 2 * i + 1;
-		int k = 2 * i + 2;
+		size_t min = i;
+		size_t j = 2 * i + 1;
+		size_t k = 2 * i + 2;
 		if (j < pq->len && pq_less(&pq->heap[j], &pq->heap[i]))
 			min = j;
 		if (k < pq->len && pq_less(&pq->heap[k], &pq->heap[min]))
@@ -46,14 +46,14 @@ struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq)
 
 void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry *e)
 {
-	int i = 0;
+	size_t i = 0;
 
 	REFTABLE_ALLOC_GROW(pq->heap, pq->len + 1, pq->cap);
 	pq->heap[pq->len++] = *e;
 
 	i = pq->len - 1;
 	while (i > 0) {
-		int j = (i - 1) / 2;
+		size_t j = (i - 1) / 2;
 		if (pq_less(&pq->heap[j], &pq->heap[i]))
 			break;
 		SWAP(pq->heap[j], pq->heap[i]);
-- 
2.45.GIT

[PATCH v6 3/7] t: move reftable/pq_test.c to the unit testing framework

[Chandra Pratap]

reftable/pq_test.c exercises a priority queue defined by
reftable/pq.{c, h}. Migrate reftable/pq_test.c to the unit testing
framework. Migration involves refactoring the tests to use the unit
testing framework instead of reftable's test framework, and
renaming the tests to align with unit-tests' standards.

Mentored-by: Patrick Steinhardt <ps@pks.im>
Mentored-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
---
 Makefile                                      |  2 +-
 reftable/reftable-tests.h                     |  1 -
 t/helper/test-reftable.c                      |  1 -
 .../pq_test.c => t/unit-tests/t-reftable-pq.c | 39 ++++++++-----------
 4 files changed, 17 insertions(+), 26 deletions(-)
 rename reftable/pq_test.c => t/unit-tests/t-reftable-pq.c (61%)

diff --git a/Makefile b/Makefile
index d6479092a0..1ee83e98dc 100644
--- a/Makefile
+++ b/Makefile
@@ -1340,6 +1340,7 @@ UNIT_TEST_PROGRAMS += t-oidmap
 UNIT_TEST_PROGRAMS += t-oidtree
 UNIT_TEST_PROGRAMS += t-prio-queue
 UNIT_TEST_PROGRAMS += t-reftable-basics
+UNIT_TEST_PROGRAMS += t-reftable-pq
 UNIT_TEST_PROGRAMS += t-reftable-record
 UNIT_TEST_PROGRAMS += t-strbuf
 UNIT_TEST_PROGRAMS += t-strcmp-offset
@@ -2681,7 +2682,6 @@ REFTABLE_OBJS += reftable/writer.o
 REFTABLE_TEST_OBJS += reftable/block_test.o
 REFTABLE_TEST_OBJS += reftable/dump.o
 REFTABLE_TEST_OBJS += reftable/merged_test.o
-REFTABLE_TEST_OBJS += reftable/pq_test.o
 REFTABLE_TEST_OBJS += reftable/readwrite_test.o
 REFTABLE_TEST_OBJS += reftable/stack_test.o
 REFTABLE_TEST_OBJS += reftable/test_framework.o
diff --git a/reftable/reftable-tests.h b/reftable/reftable-tests.h
index 114cc3d053..67283faf06 100644
--- a/reftable/reftable-tests.h
+++ b/reftable/reftable-tests.h
@@ -12,7 +12,6 @@ license that can be found in the LICENSE file or at
 int basics_test_main(int argc, const char **argv);
 int block_test_main(int argc, const char **argv);
 int merged_test_main(int argc, const char **argv);
-int pq_test_main(int argc, const char **argv);
 int record_test_main(int argc, const char **argv);
 int readwrite_test_main(int argc, const char **argv);
 int stack_test_main(int argc, const char **argv);
diff --git a/t/helper/test-reftable.c b/t/helper/test-reftable.c
index aa6538a8da..b808ad3e12 100644
--- a/t/helper/test-reftable.c
+++ b/t/helper/test-reftable.c
@@ -7,7 +7,6 @@ int cmd__reftable(int argc, const char **argv)
 	/* test from simple to complex. */
 	block_test_main(argc, argv);
 	tree_test_main(argc, argv);
-	pq_test_main(argc, argv);
 	readwrite_test_main(argc, argv);
 	merged_test_main(argc, argv);
 	stack_test_main(argc, argv);
diff --git a/reftable/pq_test.c b/t/unit-tests/t-reftable-pq.c
similarity index 61%
rename from reftable/pq_test.c
rename to t/unit-tests/t-reftable-pq.c
index b7d3c80cc7..a78aba9e71 100644
--- a/reftable/pq_test.c
+++ b/t/unit-tests/t-reftable-pq.c
@@ -6,35 +6,28 @@ license that can be found in the LICENSE file or at
 https://developers.google.com/open-source/licenses/bsd
 */
 
-#include "system.h"
-
-#include "basics.h"
-#include "constants.h"
-#include "pq.h"
-#include "record.h"
-#include "reftable-tests.h"
-#include "test_framework.h"
+#include "test-lib.h"
+#include "reftable/constants.h"
+#include "reftable/pq.h"
 
 void merged_iter_pqueue_check(struct merged_iter_pqueue pq)
 {
-	int i;
-	for (i = 1; i < pq.len; i++) {
-		int parent = (i - 1) / 2;
-
-		EXPECT(pq_less(&pq.heap[parent], &pq.heap[i]));
+	for (size_t i = 1; i < pq.len; i++) {
+		size_t parent = (i - 1) / 2;
+		check(pq_less(&pq.heap[parent], &pq.heap[i]));
 	}
 }
 
-static void test_pq(void)
+static void t_pq(void)
 {
-	struct merged_iter_pqueue pq = { NULL };
+	struct merged_iter_pqueue pq = { 0 };
 	struct reftable_record recs[54];
-	int N = ARRAY_SIZE(recs) - 1, i;
+	size_t N = ARRAY_SIZE(recs) - 1, i;
 	char *last = NULL;
 
 	for (i = 0; i < N; i++) {
 		struct strbuf refname = STRBUF_INIT;
-		strbuf_addf(&refname, "%02d", i);
+		strbuf_addf(&refname, "%02"PRIuMAX, (uintmax_t)i);
 
 		reftable_record_init(&recs[i], BLOCK_TYPE_REF);
 		recs[i].u.ref.refname = strbuf_detach(&refname, NULL);
@@ -48,7 +41,6 @@ static void test_pq(void)
 
 		merged_iter_pqueue_add(&pq, &e);
 		merged_iter_pqueue_check(pq);
-
 		i = (i * 7) % N;
 	} while (i != 1);
 
@@ -56,9 +48,9 @@ static void test_pq(void)
 		struct pq_entry e = merged_iter_pqueue_remove(&pq);
 		merged_iter_pqueue_check(pq);
 
-		EXPECT(reftable_record_type(e.rec) == BLOCK_TYPE_REF);
+		check(reftable_record_type(e.rec) == BLOCK_TYPE_REF);
 		if (last)
-			EXPECT(strcmp(last, e.rec->u.ref.refname) < 0);
+			check_int(strcmp(last, e.rec->u.ref.refname), <, 0);
 		last = e.rec->u.ref.refname;
 	}
 
@@ -67,8 +59,9 @@ static void test_pq(void)
 	merged_iter_pqueue_release(&pq);
 }
 
-int pq_test_main(int argc, const char *argv[])
+int cmd_main(int argc, const char *argv[])
 {
-	RUN_TEST(test_pq);
-	return 0;
+	TEST(t_pq(), "pq works");
+
+	return test_done();
 }
-- 
2.45.GIT

[PATCH v6 4/7] t-reftable-pq: make merged_iter_pqueue_check() static

[Chandra Pratap]

merged_iter_pqueue_check() is a function previously defined in
reftable/pq_test.c (now t/unit-tests/t-reftable-pq.c) and used in
the testing of a priority queue as defined by reftable/pq.{c, h}.
As such, this function is only called by reftable/pq_test.c and it
makes little sense to expose it to non-testing code via reftable/pq.h.

Hence, make this function static and remove its prototype from
reftable/pq.h.

Mentored-by: Patrick Steinhardt <ps@pks.im>
Mentored-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
---
 reftable/pq.h                | 1 -
 t/unit-tests/t-reftable-pq.c | 2 +-
 2 files changed, 1 insertion(+), 2 deletions(-)

diff --git a/reftable/pq.h b/reftable/pq.h
index f796c23179..707bd26767 100644
--- a/reftable/pq.h
+++ b/reftable/pq.h
@@ -22,7 +22,6 @@ struct merged_iter_pqueue {
 	size_t cap;
 };
 
-void merged_iter_pqueue_check(struct merged_iter_pqueue pq);
 struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq);
 void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry *e);
 void merged_iter_pqueue_release(struct merged_iter_pqueue *pq);
diff --git a/t/unit-tests/t-reftable-pq.c b/t/unit-tests/t-reftable-pq.c
index a78aba9e71..220e82be19 100644
--- a/t/unit-tests/t-reftable-pq.c
+++ b/t/unit-tests/t-reftable-pq.c
@@ -10,7 +10,7 @@ license that can be found in the LICENSE file or at
 #include "reftable/constants.h"
 #include "reftable/pq.h"
 
-void merged_iter_pqueue_check(struct merged_iter_pqueue pq)
+static void merged_iter_pqueue_check(struct merged_iter_pqueue pq)
 {
 	for (size_t i = 1; i < pq.len; i++) {
 		size_t parent = (i - 1) / 2;
-- 
2.45.GIT

[PATCH v6 5/7] t-reftable-pq: make merged_iter_pqueue_check() callable by reference

[Chandra Pratap]

merged_iter_pqueue_check() checks the validity of a priority queue
represented by a merged_iter_pqueue struct by asserting the
parent-child relation in the struct's heap. Explicity passing a
struct to this function means a copy of the entire struct is created,
which is inefficient.

Make the function accept a pointer to the struct instead. This is
safe to do since the function doesn't modify the struct in any way.
Make the function parameter 'const' to assert immutability.

Mentored-by: Patrick Steinhardt <ps@pks.im>
Mentored-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
---
 t/unit-tests/t-reftable-pq.c | 10 +++++-----
 1 file changed, 5 insertions(+), 5 deletions(-)

diff --git a/t/unit-tests/t-reftable-pq.c b/t/unit-tests/t-reftable-pq.c
index 220e82be19..9230dd9b9e 100644
--- a/t/unit-tests/t-reftable-pq.c
+++ b/t/unit-tests/t-reftable-pq.c
@@ -10,11 +10,11 @@ license that can be found in the LICENSE file or at
 #include "reftable/constants.h"
 #include "reftable/pq.h"
 
-static void merged_iter_pqueue_check(struct merged_iter_pqueue pq)
+static void merged_iter_pqueue_check(const struct merged_iter_pqueue *pq)
 {
-	for (size_t i = 1; i < pq.len; i++) {
+	for (size_t i = 1; i < pq->len; i++) {
 		size_t parent = (i - 1) / 2;
-		check(pq_less(&pq.heap[parent], &pq.heap[i]));
+		check(pq_less(&pq->heap[parent], &pq->heap[i]));
 	}
 }
 
@@ -40,13 +40,13 @@ static void t_pq(void)
 		};
 
 		merged_iter_pqueue_add(&pq, &e);
-		merged_iter_pqueue_check(pq);
+		merged_iter_pqueue_check(&pq);
 		i = (i * 7) % N;
 	} while (i != 1);
 
 	while (!merged_iter_pqueue_is_empty(pq)) {
 		struct pq_entry e = merged_iter_pqueue_remove(&pq);
-		merged_iter_pqueue_check(pq);
+		merged_iter_pqueue_check(&pq);
 
 		check(reftable_record_type(e.rec) == BLOCK_TYPE_REF);
 		if (last)
-- 
2.45.GIT

[PATCH v6 6/7] t-reftable-pq: add test for index based comparison

[Chandra Pratap]

When comparing two entries, the priority queue as defined by
reftable/pq.{c, h} first compares the entries on the basis of
their ref-record's keys. If the keys turn out to be equal, the
comparison is then made on the basis of their update indices
(which are never equal).

In the current testing setup, only the case for comparison on
the basis of ref-record's keys is exercised. Add a test for
index-based comparison as well. Rename the existing test to
reflect its nature of only testing record-based comparison.

While at it, replace 'strbuf_detach' with 'xstrfmt' to assign
refnames in the existing test. This makes the test conciser.

Mentored-by: Patrick Steinhardt <ps@pks.im>
Mentored-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
---
 t/unit-tests/t-reftable-pq.c | 49 +++++++++++++++++++++++++++++++-----
 1 file changed, 43 insertions(+), 6 deletions(-)

diff --git a/t/unit-tests/t-reftable-pq.c b/t/unit-tests/t-reftable-pq.c
index 9230dd9b9e..67f3e4546c 100644
--- a/t/unit-tests/t-reftable-pq.c
+++ b/t/unit-tests/t-reftable-pq.c
@@ -18,7 +18,7 @@ static void merged_iter_pqueue_check(const struct merged_iter_pqueue *pq)
 	}
 }
 
-static void t_pq(void)
+static void t_pq_record(void)
 {
 	struct merged_iter_pqueue pq = { 0 };
 	struct reftable_record recs[54];
@@ -26,11 +26,8 @@ static void t_pq(void)
 	char *last = NULL;
 
 	for (i = 0; i < N; i++) {
-		struct strbuf refname = STRBUF_INIT;
-		strbuf_addf(&refname, "%02"PRIuMAX, (uintmax_t)i);
-
 		reftable_record_init(&recs[i], BLOCK_TYPE_REF);
-		recs[i].u.ref.refname = strbuf_detach(&refname, NULL);
+		recs[i].u.ref.refname = xstrfmt("%02"PRIuMAX, (uintmax_t)i);
 	}
 
 	i = 1;
@@ -59,9 +56,49 @@ static void t_pq(void)
 	merged_iter_pqueue_release(&pq);
 }
 
+static void t_pq_index(void)
+{
+	struct merged_iter_pqueue pq = { 0 };
+	struct reftable_record recs[13];
+	char *last = NULL;
+	size_t N = ARRAY_SIZE(recs), i;
+
+	for (i = 0; i < N; i++) {
+		reftable_record_init(&recs[i], BLOCK_TYPE_REF);
+		recs[i].u.ref.refname = (char *) "refs/heads/master";
+	}
+
+	i = 1;
+	do {
+		struct pq_entry e = {
+			.rec = &recs[i],
+			.index = i,
+		};
+
+		merged_iter_pqueue_add(&pq, &e);
+		merged_iter_pqueue_check(&pq);
+		i = (i * 7) % N;
+	}
+	while (i != 1);
+
+	for (i = N - 1; i > 0; i--) {
+		struct pq_entry e = merged_iter_pqueue_remove(&pq);
+		merged_iter_pqueue_check(&pq);
+
+		check(reftable_record_type(e.rec) == BLOCK_TYPE_REF);
+		check_int(e.index, ==, i);
+		if (last)
+			check_str(last, e.rec->u.ref.refname);
+		last = e.rec->u.ref.refname;
+	}
+
+	merged_iter_pqueue_release(&pq);
+}
+
 int cmd_main(int argc, const char *argv[])
 {
-	TEST(t_pq(), "pq works");
+	TEST(t_pq_record(), "pq works with record-based comparison");
+	TEST(t_pq_index(), "pq works with index-based comparison");
 
 	return test_done();
 }
-- 
2.45.GIT

Re: [PATCH v6 6/7] t-reftable-pq: add test for index based comparison

[Patrick Steinhardt]

[-- Attachment #1: Type: text/plain, Size: 832 bytes --]

On Thu, Jul 25, 2024 at 02:55:58PM +0530, Chandra Pratap wrote:
> @@ -59,9 +56,49 @@ static void t_pq(void)
>  	merged_iter_pqueue_release(&pq);
>  }
>  
> +static void t_pq_index(void)
> +{
> +	struct merged_iter_pqueue pq = { 0 };
> +	struct reftable_record recs[13];
> +	char *last = NULL;
> +	size_t N = ARRAY_SIZE(recs), i;
> +
> +	for (i = 0; i < N; i++) {
> +		reftable_record_init(&recs[i], BLOCK_TYPE_REF);
> +		recs[i].u.ref.refname = (char *) "refs/heads/master";
> +	}
> +
> +	i = 1;
> +	do {
> +		struct pq_entry e = {
> +			.rec = &recs[i],
> +			.index = i,
> +		};
> +
> +		merged_iter_pqueue_add(&pq, &e);
> +		merged_iter_pqueue_check(&pq);
> +		i = (i * 7) % N;
> +	}
> +	while (i != 1);

Nit: the `while (i != 1)` should go on the same line as the closing
curly brace.

Patrick

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

[PATCH v6 7/7] t-reftable-pq: add tests for merged_iter_pqueue_top()

[Chandra Pratap]

merged_iter_pqueue_top() as defined by reftable/pq.{c, h} returns
the element at the top of a priority-queue's heap without removing
it. Since there are no tests for this function in the existing
setup, add tests for the same.

Mentored-by: Patrick Steinhardt <ps@pks.im>
Mentored-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
---
 t/unit-tests/t-reftable-pq.c | 50 ++++++++++++++++++++++++++++++++++++
 1 file changed, 50 insertions(+)

diff --git a/t/unit-tests/t-reftable-pq.c b/t/unit-tests/t-reftable-pq.c
index 67f3e4546c..ce322d7255 100644
--- a/t/unit-tests/t-reftable-pq.c
+++ b/t/unit-tests/t-reftable-pq.c
@@ -18,6 +18,11 @@ static void merged_iter_pqueue_check(const struct merged_iter_pqueue *pq)
 	}
 }
 
+static int pq_entry_equal(struct pq_entry *a, struct pq_entry *b)
+{
+	return !reftable_record_cmp(a->rec, b->rec) && (a->index == b->index);
+}
+
 static void t_pq_record(void)
 {
 	struct merged_iter_pqueue pq = { 0 };
@@ -42,9 +47,11 @@ static void t_pq_record(void)
 	} while (i != 1);
 
 	while (!merged_iter_pqueue_is_empty(pq)) {
+		struct pq_entry top = merged_iter_pqueue_top(pq);
 		struct pq_entry e = merged_iter_pqueue_remove(&pq);
 		merged_iter_pqueue_check(&pq);
 
+		check(pq_entry_equal(&top, &e));
 		check(reftable_record_type(e.rec) == BLOCK_TYPE_REF);
 		if (last)
 			check_int(strcmp(last, e.rec->u.ref.refname), <, 0);
@@ -82,9 +89,11 @@ static void t_pq_index(void)
 	while (i != 1);
 
 	for (i = N - 1; i > 0; i--) {
+		struct pq_entry top = merged_iter_pqueue_top(pq);
 		struct pq_entry e = merged_iter_pqueue_remove(&pq);
 		merged_iter_pqueue_check(&pq);
 
+		check(pq_entry_equal(&top, &e));
 		check(reftable_record_type(e.rec) == BLOCK_TYPE_REF);
 		check_int(e.index, ==, i);
 		if (last)
@@ -95,10 +104,51 @@ static void t_pq_index(void)
 	merged_iter_pqueue_release(&pq);
 }
 
+static void t_merged_iter_pqueue_top(void)
+{
+	struct merged_iter_pqueue pq = { 0 };
+	struct reftable_record recs[13];
+	size_t N = ARRAY_SIZE(recs), i;
+
+	for (i = 0; i < N; i++) {
+		reftable_record_init(&recs[i], BLOCK_TYPE_REF);
+		recs[i].u.ref.refname = (char *) "refs/heads/master";
+	}
+
+	i = 1;
+	do {
+		struct pq_entry e = {
+			.rec = &recs[i],
+			.index = i,
+		};
+
+		merged_iter_pqueue_add(&pq, &e);
+		merged_iter_pqueue_check(&pq);
+		i = (i * 7) % N;
+	}
+	while (i != 1);
+
+	for (i = N - 1; i > 0; i--) {
+		struct pq_entry top = merged_iter_pqueue_top(pq);
+		struct pq_entry e = merged_iter_pqueue_remove(&pq);
+
+		merged_iter_pqueue_check(&pq);
+		check(pq_entry_equal(&top, &e));
+		check(reftable_record_equal(top.rec, &recs[i], GIT_SHA1_RAWSZ));
+		for (size_t j = 0; i < pq.len; j++) {
+			check(pq_less(&top, &pq.heap[j]));
+			check_int(top.index, >, j);
+		}
+	}
+
+	merged_iter_pqueue_release(&pq);
+}
+
 int cmd_main(int argc, const char *argv[])
 {
 	TEST(t_pq_record(), "pq works with record-based comparison");
 	TEST(t_pq_index(), "pq works with index-based comparison");
+	TEST(t_merged_iter_pqueue_top(), "merged_iter_pqueue_top works");
 
 	return test_done();
 }
-- 
2.45.GIT

Re: [PATCH v6 7/7] t-reftable-pq: add tests for merged_iter_pqueue_top()

[Patrick Steinhardt]

[-- Attachment #1: Type: text/plain, Size: 824 bytes --]

On Thu, Jul 25, 2024 at 02:55:59PM +0530, Chandra Pratap wrote:
> @@ -95,10 +104,51 @@ static void t_pq_index(void)
>  	merged_iter_pqueue_release(&pq);
>  }
>  
> +static void t_merged_iter_pqueue_top(void)
> +{
> +	struct merged_iter_pqueue pq = { 0 };
> +	struct reftable_record recs[13];
> +	size_t N = ARRAY_SIZE(recs), i;
> +
> +	for (i = 0; i < N; i++) {
> +		reftable_record_init(&recs[i], BLOCK_TYPE_REF);
> +		recs[i].u.ref.refname = (char *) "refs/heads/master";
> +	}
> +
> +	i = 1;
> +	do {
> +		struct pq_entry e = {
> +			.rec = &recs[i],
> +			.index = i,
> +		};
> +
> +		merged_iter_pqueue_add(&pq, &e);
> +		merged_iter_pqueue_check(&pq);
> +		i = (i * 7) % N;
> +	}
> +	while (i != 1);

Same nit here. Other than that this patch series looks good to me,
thanks!

Patrick

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

[GSoC][PATCH v7 0/7] t: port reftable/pq_test.c to the unit testing framework

[Chandra Pratap]

The reftable library comes with self tests, which are exercised
as part of the usual end-to-end tests and are designed to
observe the end-user visible effects of Git commands. What it
exercises, however, is a better match for the unit-testing
framework, merged at 8bf6fbd0 (Merge branch 'js/doc-unit-tests',
2023-12-09), which is designed to observe how low level
implementation details, at the level of sequences of individual
function calls, behave.

Hence, port reftable/pq_test.c to the unit testing framework and
improve upon the ported test. The first two patches in the series
are preparatory cleanup, the third patch moves the test to the unit
testing framework, and the rest of the patches improve upon the
ported test.

Mentored-by: Patrick Steinhardt <ps@pks.im>
Mentored-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>

---
Changes in v7:
- Fix a typo in patch 1
- Fix do-while style error in patch 6 and 7

CI/PR for v7: https://github.com/gitgitgadget/git/pull/1745

Chandra Pratap(7):
reftable: remove unncessary curly braces in reftable/pq.c
reftable: change the type of array indices to 'size_t' in reftable/pq.c
t: move reftable/pq_test.c to the unit testing framework
t-reftable-pq: make merged_iter_pqueue_check() static
t-reftable-pq: make merged_iter_pqueue_check() callable by reference
t-reftable-pq: add test for index based comparison
t-reftable-pq: add tests for merged_iter_pqueue_top()

Makefile                     |   2 +-
reftable/pq.c                |  29 +++-----
reftable/pq.h                |   1 -
reftable/pq_test.c           |  74 ---------------------
reftable/reftable-tests.h    |   1 -
t/helper/test-reftable.c     |   1 -
t/unit-tests/t-reftable-pq.c | 152 +++++++++++++++++++++++++++++++++++++++++++
7 files changed, 163 insertions(+), 97 deletions(-)

Range-diff against v6:

1:  acd9d26aaf ! 1:  91719cc47f reftable: remove unncessary curly braces in reftable/pq.c
    @@ Metadata
     Author: Chandra Pratap <chandrapratap3519@gmail.com>

      ## Commit message ##
    -    reftable: remove unncessary curly braces in reftable/pq.c
    +    reftable: remove unnecessary curly braces in reftable/pq.c

         According to Documentation/CodingGuidelines, control-flow statements
         with a single line as their body must omit curly braces. Make
2:  2e0986207b = 2:  2e5e72d5c5 reftable: change the type of array indices to 'size_t' in reftable/pq.c
3:  df06b6d604 = 3:  5db9e92f20 t: move reftable/pq_test.c to the unit testing framework
4:  40745ab18e = 4:  9334b1fe9e t-reftable-pq: make merged_iter_pqueue_check() static
5:  ee8432ac4a = 5:  9d8c33d1fc t-reftable-pq: make merged_iter_pqueue_check() callable by reference
6:  f5c30187e1 ! 6:  7a67861652 t-reftable-pq: add test for index based comparison
    @@ t/unit-tests/t-reftable-pq.c: static void t_pq(void)
     +		merged_iter_pqueue_add(&pq, &e);
     +		merged_iter_pqueue_check(&pq);
     +		i = (i * 7) % N;
    -+	}
    -+	while (i != 1);
    ++	} while (i != 1);
     +
     +	for (i = N - 1; i > 0; i--) {
     +		struct pq_entry e = merged_iter_pqueue_remove(&pq);
7:  394540a789 ! 7:  5ac60563e4 t-reftable-pq: add tests for merged_iter_pqueue_top()
    @@ t/unit-tests/t-reftable-pq.c: static void t_pq_record(void)
      		if (last)
      			check_int(strcmp(last, e.rec->u.ref.refname), <, 0);
     @@ t/unit-tests/t-reftable-pq.c: static void t_pq_index(void)
    - 	while (i != 1);
    + 	} while (i != 1);

      	for (i = N - 1; i > 0; i--) {
     +		struct pq_entry top = merged_iter_pqueue_top(pq);
    @@ t/unit-tests/t-reftable-pq.c: static void t_pq_index(void)
     +		merged_iter_pqueue_add(&pq, &e);
     +		merged_iter_pqueue_check(&pq);
     +		i = (i * 7) % N;
    -+	}
    -+	while (i != 1);
    ++	} while (i != 1);
     +
     +	for (i = N - 1; i > 0; i--) {
     +		struct pq_entry top = merged_iter_pqueue_top(pq);

[PATCH v7 1/7] reftable: remove unnecessary curly braces in reftable/pq.c

[Chandra Pratap]

According to Documentation/CodingGuidelines, control-flow statements
with a single line as their body must omit curly braces. Make
reftable/pq.c conform to this guideline. Besides that, remove
unnecessary newlines and variable assignment.

Mentored-by: Patrick Steinhardt <ps@pks.im>
Mentored-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
---
 reftable/pq.c | 17 ++++-------------
 1 file changed, 4 insertions(+), 13 deletions(-)

diff --git a/reftable/pq.c b/reftable/pq.c
index 7fb45d8c60..1a180c5fa6 100644
--- a/reftable/pq.c
+++ b/reftable/pq.c
@@ -27,22 +27,16 @@ struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq)
 	pq->heap[0] = pq->heap[pq->len - 1];
 	pq->len--;
 
-	i = 0;
 	while (i < pq->len) {
 		int min = i;
 		int j = 2 * i + 1;
 		int k = 2 * i + 2;
-		if (j < pq->len && pq_less(&pq->heap[j], &pq->heap[i])) {
+		if (j < pq->len && pq_less(&pq->heap[j], &pq->heap[i]))
 			min = j;
-		}
-		if (k < pq->len && pq_less(&pq->heap[k], &pq->heap[min])) {
+		if (k < pq->len && pq_less(&pq->heap[k], &pq->heap[min]))
 			min = k;
-		}
-
-		if (min == i) {
+		if (min == i)
 			break;
-		}
-
 		SWAP(pq->heap[i], pq->heap[min]);
 		i = min;
 	}
@@ -60,12 +54,9 @@ void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry
 	i = pq->len - 1;
 	while (i > 0) {
 		int j = (i - 1) / 2;
-		if (pq_less(&pq->heap[j], &pq->heap[i])) {
+		if (pq_less(&pq->heap[j], &pq->heap[i]))
 			break;
-		}
-
 		SWAP(pq->heap[j], pq->heap[i]);
-
 		i = j;
 	}
 }
-- 
2.45.GIT

[PATCH v7 2/7] reftable: change the type of array indices to 'size_t' in reftable/pq.c

[Chandra Pratap]

The variables 'i', 'j', 'k' and 'min' are used as indices for
'pq->heap', which is an array. Additionally, 'pq->len' is of
type 'size_t' and is often used to assign values to these
variables. Hence, change the type of these variables from 'int'
to 'size_t'.

Mentored-by: Patrick Steinhardt <ps@pks.im>
Mentored-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
---
 reftable/pq.c | 12 ++++++------
 1 file changed, 6 insertions(+), 6 deletions(-)

diff --git a/reftable/pq.c b/reftable/pq.c
index 1a180c5fa6..2b5b7d1c0e 100644
--- a/reftable/pq.c
+++ b/reftable/pq.c
@@ -22,15 +22,15 @@ int pq_less(struct pq_entry *a, struct pq_entry *b)
 
 struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq)
 {
-	int i = 0;
+	size_t i = 0;
 	struct pq_entry e = pq->heap[0];
 	pq->heap[0] = pq->heap[pq->len - 1];
 	pq->len--;
 
 	while (i < pq->len) {
-		int min = i;
-		int j = 2 * i + 1;
-		int k = 2 * i + 2;
+		size_t min = i;
+		size_t j = 2 * i + 1;
+		size_t k = 2 * i + 2;
 		if (j < pq->len && pq_less(&pq->heap[j], &pq->heap[i]))
 			min = j;
 		if (k < pq->len && pq_less(&pq->heap[k], &pq->heap[min]))
@@ -46,14 +46,14 @@ struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq)
 
 void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry *e)
 {
-	int i = 0;
+	size_t i = 0;
 
 	REFTABLE_ALLOC_GROW(pq->heap, pq->len + 1, pq->cap);
 	pq->heap[pq->len++] = *e;
 
 	i = pq->len - 1;
 	while (i > 0) {
-		int j = (i - 1) / 2;
+		size_t j = (i - 1) / 2;
 		if (pq_less(&pq->heap[j], &pq->heap[i]))
 			break;
 		SWAP(pq->heap[j], pq->heap[i]);
-- 
2.45.GIT

[PATCH v7 3/7] t: move reftable/pq_test.c to the unit testing framework

[Chandra Pratap]

reftable/pq_test.c exercises a priority queue defined by
reftable/pq.{c, h}. Migrate reftable/pq_test.c to the unit testing
framework. Migration involves refactoring the tests to use the unit
testing framework instead of reftable's test framework, and
renaming the tests to align with unit-tests' standards.

Mentored-by: Patrick Steinhardt <ps@pks.im>
Mentored-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
---
 Makefile                                      |  2 +-
 reftable/reftable-tests.h                     |  1 -
 t/helper/test-reftable.c                      |  1 -
 .../pq_test.c => t/unit-tests/t-reftable-pq.c | 39 ++++++++-----------
 4 files changed, 17 insertions(+), 26 deletions(-)
 rename reftable/pq_test.c => t/unit-tests/t-reftable-pq.c (61%)

diff --git a/Makefile b/Makefile
index d6479092a0..1ee83e98dc 100644
--- a/Makefile
+++ b/Makefile
@@ -1340,6 +1340,7 @@ UNIT_TEST_PROGRAMS += t-oidmap
 UNIT_TEST_PROGRAMS += t-oidtree
 UNIT_TEST_PROGRAMS += t-prio-queue
 UNIT_TEST_PROGRAMS += t-reftable-basics
+UNIT_TEST_PROGRAMS += t-reftable-pq
 UNIT_TEST_PROGRAMS += t-reftable-record
 UNIT_TEST_PROGRAMS += t-strbuf
 UNIT_TEST_PROGRAMS += t-strcmp-offset
@@ -2681,7 +2682,6 @@ REFTABLE_OBJS += reftable/writer.o
 REFTABLE_TEST_OBJS += reftable/block_test.o
 REFTABLE_TEST_OBJS += reftable/dump.o
 REFTABLE_TEST_OBJS += reftable/merged_test.o
-REFTABLE_TEST_OBJS += reftable/pq_test.o
 REFTABLE_TEST_OBJS += reftable/readwrite_test.o
 REFTABLE_TEST_OBJS += reftable/stack_test.o
 REFTABLE_TEST_OBJS += reftable/test_framework.o
diff --git a/reftable/reftable-tests.h b/reftable/reftable-tests.h
index 114cc3d053..67283faf06 100644
--- a/reftable/reftable-tests.h
+++ b/reftable/reftable-tests.h
@@ -12,7 +12,6 @@ license that can be found in the LICENSE file or at
 int basics_test_main(int argc, const char **argv);
 int block_test_main(int argc, const char **argv);
 int merged_test_main(int argc, const char **argv);
-int pq_test_main(int argc, const char **argv);
 int record_test_main(int argc, const char **argv);
 int readwrite_test_main(int argc, const char **argv);
 int stack_test_main(int argc, const char **argv);
diff --git a/t/helper/test-reftable.c b/t/helper/test-reftable.c
index aa6538a8da..b808ad3e12 100644
--- a/t/helper/test-reftable.c
+++ b/t/helper/test-reftable.c
@@ -7,7 +7,6 @@ int cmd__reftable(int argc, const char **argv)
 	/* test from simple to complex. */
 	block_test_main(argc, argv);
 	tree_test_main(argc, argv);
-	pq_test_main(argc, argv);
 	readwrite_test_main(argc, argv);
 	merged_test_main(argc, argv);
 	stack_test_main(argc, argv);
diff --git a/reftable/pq_test.c b/t/unit-tests/t-reftable-pq.c
similarity index 61%
rename from reftable/pq_test.c
rename to t/unit-tests/t-reftable-pq.c
index b7d3c80cc7..a78aba9e71 100644
--- a/reftable/pq_test.c
+++ b/t/unit-tests/t-reftable-pq.c
@@ -6,35 +6,28 @@ license that can be found in the LICENSE file or at
 https://developers.google.com/open-source/licenses/bsd
 */
 
-#include "system.h"
-
-#include "basics.h"
-#include "constants.h"
-#include "pq.h"
-#include "record.h"
-#include "reftable-tests.h"
-#include "test_framework.h"
+#include "test-lib.h"
+#include "reftable/constants.h"
+#include "reftable/pq.h"
 
 void merged_iter_pqueue_check(struct merged_iter_pqueue pq)
 {
-	int i;
-	for (i = 1; i < pq.len; i++) {
-		int parent = (i - 1) / 2;
-
-		EXPECT(pq_less(&pq.heap[parent], &pq.heap[i]));
+	for (size_t i = 1; i < pq.len; i++) {
+		size_t parent = (i - 1) / 2;
+		check(pq_less(&pq.heap[parent], &pq.heap[i]));
 	}
 }
 
-static void test_pq(void)
+static void t_pq(void)
 {
-	struct merged_iter_pqueue pq = { NULL };
+	struct merged_iter_pqueue pq = { 0 };
 	struct reftable_record recs[54];
-	int N = ARRAY_SIZE(recs) - 1, i;
+	size_t N = ARRAY_SIZE(recs) - 1, i;
 	char *last = NULL;
 
 	for (i = 0; i < N; i++) {
 		struct strbuf refname = STRBUF_INIT;
-		strbuf_addf(&refname, "%02d", i);
+		strbuf_addf(&refname, "%02"PRIuMAX, (uintmax_t)i);
 
 		reftable_record_init(&recs[i], BLOCK_TYPE_REF);
 		recs[i].u.ref.refname = strbuf_detach(&refname, NULL);
@@ -48,7 +41,6 @@ static void test_pq(void)
 
 		merged_iter_pqueue_add(&pq, &e);
 		merged_iter_pqueue_check(pq);
-
 		i = (i * 7) % N;
 	} while (i != 1);
 
@@ -56,9 +48,9 @@ static void test_pq(void)
 		struct pq_entry e = merged_iter_pqueue_remove(&pq);
 		merged_iter_pqueue_check(pq);
 
-		EXPECT(reftable_record_type(e.rec) == BLOCK_TYPE_REF);
+		check(reftable_record_type(e.rec) == BLOCK_TYPE_REF);
 		if (last)
-			EXPECT(strcmp(last, e.rec->u.ref.refname) < 0);
+			check_int(strcmp(last, e.rec->u.ref.refname), <, 0);
 		last = e.rec->u.ref.refname;
 	}
 
@@ -67,8 +59,9 @@ static void test_pq(void)
 	merged_iter_pqueue_release(&pq);
 }
 
-int pq_test_main(int argc, const char *argv[])
+int cmd_main(int argc, const char *argv[])
 {
-	RUN_TEST(test_pq);
-	return 0;
+	TEST(t_pq(), "pq works");
+
+	return test_done();
 }
-- 
2.45.GIT

[PATCH v7 4/7] t-reftable-pq: make merged_iter_pqueue_check() static

[Chandra Pratap]

merged_iter_pqueue_check() is a function previously defined in
reftable/pq_test.c (now t/unit-tests/t-reftable-pq.c) and used in
the testing of a priority queue as defined by reftable/pq.{c, h}.
As such, this function is only called by reftable/pq_test.c and it
makes little sense to expose it to non-testing code via reftable/pq.h.

Hence, make this function static and remove its prototype from
reftable/pq.h.

Mentored-by: Patrick Steinhardt <ps@pks.im>
Mentored-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
---
 reftable/pq.h                | 1 -
 t/unit-tests/t-reftable-pq.c | 2 +-
 2 files changed, 1 insertion(+), 2 deletions(-)

diff --git a/reftable/pq.h b/reftable/pq.h
index f796c23179..707bd26767 100644
--- a/reftable/pq.h
+++ b/reftable/pq.h
@@ -22,7 +22,6 @@ struct merged_iter_pqueue {
 	size_t cap;
 };
 
-void merged_iter_pqueue_check(struct merged_iter_pqueue pq);
 struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq);
 void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, const struct pq_entry *e);
 void merged_iter_pqueue_release(struct merged_iter_pqueue *pq);
diff --git a/t/unit-tests/t-reftable-pq.c b/t/unit-tests/t-reftable-pq.c
index a78aba9e71..220e82be19 100644
--- a/t/unit-tests/t-reftable-pq.c
+++ b/t/unit-tests/t-reftable-pq.c
@@ -10,7 +10,7 @@ license that can be found in the LICENSE file or at
 #include "reftable/constants.h"
 #include "reftable/pq.h"
 
-void merged_iter_pqueue_check(struct merged_iter_pqueue pq)
+static void merged_iter_pqueue_check(struct merged_iter_pqueue pq)
 {
 	for (size_t i = 1; i < pq.len; i++) {
 		size_t parent = (i - 1) / 2;
-- 
2.45.GIT

[PATCH v7 5/7] t-reftable-pq: make merged_iter_pqueue_check() callable by reference

[Chandra Pratap]

merged_iter_pqueue_check() checks the validity of a priority queue
represented by a merged_iter_pqueue struct by asserting the
parent-child relation in the struct's heap. Explicity passing a
struct to this function means a copy of the entire struct is created,
which is inefficient.

Make the function accept a pointer to the struct instead. This is
safe to do since the function doesn't modify the struct in any way.
Make the function parameter 'const' to assert immutability.

Mentored-by: Patrick Steinhardt <ps@pks.im>
Mentored-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
---
 t/unit-tests/t-reftable-pq.c | 10 +++++-----
 1 file changed, 5 insertions(+), 5 deletions(-)

diff --git a/t/unit-tests/t-reftable-pq.c b/t/unit-tests/t-reftable-pq.c
index 220e82be19..9230dd9b9e 100644
--- a/t/unit-tests/t-reftable-pq.c
+++ b/t/unit-tests/t-reftable-pq.c
@@ -10,11 +10,11 @@ license that can be found in the LICENSE file or at
 #include "reftable/constants.h"
 #include "reftable/pq.h"
 
-static void merged_iter_pqueue_check(struct merged_iter_pqueue pq)
+static void merged_iter_pqueue_check(const struct merged_iter_pqueue *pq)
 {
-	for (size_t i = 1; i < pq.len; i++) {
+	for (size_t i = 1; i < pq->len; i++) {
 		size_t parent = (i - 1) / 2;
-		check(pq_less(&pq.heap[parent], &pq.heap[i]));
+		check(pq_less(&pq->heap[parent], &pq->heap[i]));
 	}
 }
 
@@ -40,13 +40,13 @@ static void t_pq(void)
 		};
 
 		merged_iter_pqueue_add(&pq, &e);
-		merged_iter_pqueue_check(pq);
+		merged_iter_pqueue_check(&pq);
 		i = (i * 7) % N;
 	} while (i != 1);
 
 	while (!merged_iter_pqueue_is_empty(pq)) {
 		struct pq_entry e = merged_iter_pqueue_remove(&pq);
-		merged_iter_pqueue_check(pq);
+		merged_iter_pqueue_check(&pq);
 
 		check(reftable_record_type(e.rec) == BLOCK_TYPE_REF);
 		if (last)
-- 
2.45.GIT

[PATCH v7 6/7] t-reftable-pq: add test for index based comparison

[Chandra Pratap]

When comparing two entries, the priority queue as defined by
reftable/pq.{c, h} first compares the entries on the basis of
their ref-record's keys. If the keys turn out to be equal, the
comparison is then made on the basis of their update indices
(which are never equal).

In the current testing setup, only the case for comparison on
the basis of ref-record's keys is exercised. Add a test for
index-based comparison as well. Rename the existing test to
reflect its nature of only testing record-based comparison.

While at it, replace 'strbuf_detach' with 'xstrfmt' to assign
refnames in the existing test. This makes the test conciser.

Mentored-by: Patrick Steinhardt <ps@pks.im>
Mentored-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
---
 t/unit-tests/t-reftable-pq.c | 48 +++++++++++++++++++++++++++++++-----
 1 file changed, 42 insertions(+), 6 deletions(-)

diff --git a/t/unit-tests/t-reftable-pq.c b/t/unit-tests/t-reftable-pq.c
index 9230dd9b9e..70ff89507d 100644
--- a/t/unit-tests/t-reftable-pq.c
+++ b/t/unit-tests/t-reftable-pq.c
@@ -18,7 +18,7 @@ static void merged_iter_pqueue_check(const struct merged_iter_pqueue *pq)
 	}
 }
 
-static void t_pq(void)
+static void t_pq_record(void)
 {
 	struct merged_iter_pqueue pq = { 0 };
 	struct reftable_record recs[54];
@@ -26,11 +26,8 @@ static void t_pq(void)
 	char *last = NULL;
 
 	for (i = 0; i < N; i++) {
-		struct strbuf refname = STRBUF_INIT;
-		strbuf_addf(&refname, "%02"PRIuMAX, (uintmax_t)i);
-
 		reftable_record_init(&recs[i], BLOCK_TYPE_REF);
-		recs[i].u.ref.refname = strbuf_detach(&refname, NULL);
+		recs[i].u.ref.refname = xstrfmt("%02"PRIuMAX, (uintmax_t)i);
 	}
 
 	i = 1;
@@ -59,9 +56,48 @@ static void t_pq(void)
 	merged_iter_pqueue_release(&pq);
 }
 
+static void t_pq_index(void)
+{
+	struct merged_iter_pqueue pq = { 0 };
+	struct reftable_record recs[13];
+	char *last = NULL;
+	size_t N = ARRAY_SIZE(recs), i;
+
+	for (i = 0; i < N; i++) {
+		reftable_record_init(&recs[i], BLOCK_TYPE_REF);
+		recs[i].u.ref.refname = (char *) "refs/heads/master";
+	}
+
+	i = 1;
+	do {
+		struct pq_entry e = {
+			.rec = &recs[i],
+			.index = i,
+		};
+
+		merged_iter_pqueue_add(&pq, &e);
+		merged_iter_pqueue_check(&pq);
+		i = (i * 7) % N;
+	} while (i != 1);
+
+	for (i = N - 1; i > 0; i--) {
+		struct pq_entry e = merged_iter_pqueue_remove(&pq);
+		merged_iter_pqueue_check(&pq);
+
+		check(reftable_record_type(e.rec) == BLOCK_TYPE_REF);
+		check_int(e.index, ==, i);
+		if (last)
+			check_str(last, e.rec->u.ref.refname);
+		last = e.rec->u.ref.refname;
+	}
+
+	merged_iter_pqueue_release(&pq);
+}
+
 int cmd_main(int argc, const char *argv[])
 {
-	TEST(t_pq(), "pq works");
+	TEST(t_pq_record(), "pq works with record-based comparison");
+	TEST(t_pq_index(), "pq works with index-based comparison");
 
 	return test_done();
 }
-- 
2.45.GIT

[PATCH v7 7/7] t-reftable-pq: add tests for merged_iter_pqueue_top()

[Chandra Pratap]

merged_iter_pqueue_top() as defined by reftable/pq.{c, h} returns
the element at the top of a priority-queue's heap without removing
it. Since there are no tests for this function in the existing
setup, add tests for the same.

Mentored-by: Patrick Steinhardt <ps@pks.im>
Mentored-by: Christian Couder <chriscool@tuxfamily.org>
Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
---
 t/unit-tests/t-reftable-pq.c | 49 ++++++++++++++++++++++++++++++++++++
 1 file changed, 49 insertions(+)

diff --git a/t/unit-tests/t-reftable-pq.c b/t/unit-tests/t-reftable-pq.c
index 70ff89507d..039bd0f1f9 100644
--- a/t/unit-tests/t-reftable-pq.c
+++ b/t/unit-tests/t-reftable-pq.c
@@ -18,6 +18,11 @@ static void merged_iter_pqueue_check(const struct merged_iter_pqueue *pq)
 	}
 }
 
+static int pq_entry_equal(struct pq_entry *a, struct pq_entry *b)
+{
+	return !reftable_record_cmp(a->rec, b->rec) && (a->index == b->index);
+}
+
 static void t_pq_record(void)
 {
 	struct merged_iter_pqueue pq = { 0 };
@@ -42,9 +47,11 @@ static void t_pq_record(void)
 	} while (i != 1);
 
 	while (!merged_iter_pqueue_is_empty(pq)) {
+		struct pq_entry top = merged_iter_pqueue_top(pq);
 		struct pq_entry e = merged_iter_pqueue_remove(&pq);
 		merged_iter_pqueue_check(&pq);
 
+		check(pq_entry_equal(&top, &e));
 		check(reftable_record_type(e.rec) == BLOCK_TYPE_REF);
 		if (last)
 			check_int(strcmp(last, e.rec->u.ref.refname), <, 0);
@@ -81,9 +88,11 @@ static void t_pq_index(void)
 	} while (i != 1);
 
 	for (i = N - 1; i > 0; i--) {
+		struct pq_entry top = merged_iter_pqueue_top(pq);
 		struct pq_entry e = merged_iter_pqueue_remove(&pq);
 		merged_iter_pqueue_check(&pq);
 
+		check(pq_entry_equal(&top, &e));
 		check(reftable_record_type(e.rec) == BLOCK_TYPE_REF);
 		check_int(e.index, ==, i);
 		if (last)
@@ -94,10 +103,50 @@ static void t_pq_index(void)
 	merged_iter_pqueue_release(&pq);
 }
 
+static void t_merged_iter_pqueue_top(void)
+{
+	struct merged_iter_pqueue pq = { 0 };
+	struct reftable_record recs[13];
+	size_t N = ARRAY_SIZE(recs), i;
+
+	for (i = 0; i < N; i++) {
+		reftable_record_init(&recs[i], BLOCK_TYPE_REF);
+		recs[i].u.ref.refname = (char *) "refs/heads/master";
+	}
+
+	i = 1;
+	do {
+		struct pq_entry e = {
+			.rec = &recs[i],
+			.index = i,
+		};
+
+		merged_iter_pqueue_add(&pq, &e);
+		merged_iter_pqueue_check(&pq);
+		i = (i * 7) % N;
+	} while (i != 1);
+
+	for (i = N - 1; i > 0; i--) {
+		struct pq_entry top = merged_iter_pqueue_top(pq);
+		struct pq_entry e = merged_iter_pqueue_remove(&pq);
+
+		merged_iter_pqueue_check(&pq);
+		check(pq_entry_equal(&top, &e));
+		check(reftable_record_equal(top.rec, &recs[i], GIT_SHA1_RAWSZ));
+		for (size_t j = 0; i < pq.len; j++) {
+			check(pq_less(&top, &pq.heap[j]));
+			check_int(top.index, >, j);
+		}
+	}
+
+	merged_iter_pqueue_release(&pq);
+}
+
 int cmd_main(int argc, const char *argv[])
 {
 	TEST(t_pq_record(), "pq works with record-based comparison");
 	TEST(t_pq_index(), "pq works with index-based comparison");
+	TEST(t_merged_iter_pqueue_top(), "merged_iter_pqueue_top works");
 
 	return test_done();
 }
-- 
2.45.GIT

Re: [GSoC][PATCH v7 0/7] t: port reftable/pq_test.c to the unit testing framework

[Patrick Steinhardt]

[-- Attachment #1: Type: text/plain, Size: 1205 bytes --]

On Thu, Aug 01, 2024 at 04:29:41PM +0530, Chandra Pratap wrote:
> The reftable library comes with self tests, which are exercised
> as part of the usual end-to-end tests and are designed to
> observe the end-user visible effects of Git commands. What it
> exercises, however, is a better match for the unit-testing
> framework, merged at 8bf6fbd0 (Merge branch 'js/doc-unit-tests',
> 2023-12-09), which is designed to observe how low level
> implementation details, at the level of sequences of individual
> function calls, behave.
> 
> Hence, port reftable/pq_test.c to the unit testing framework and
> improve upon the ported test. The first two patches in the series
> are preparatory cleanup, the third patch moves the test to the unit
> testing framework, and the rest of the patches improve upon the
> ported test.
> 
> Mentored-by: Patrick Steinhardt <ps@pks.im>
> Mentored-by: Christian Couder <chriscool@tuxfamily.org>
> Signed-off-by: Chandra Pratap <chandrapratap3519@gmail.com>
> 
> ---
> Changes in v7:
> - Fix a typo in patch 1
> - Fix do-while style error in patch 6 and 7

The range-diff looks as expected to me, so the whole series LGTM now.
Thanks!

Patrick

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [GSoC][PATCH v7 0/7] t: port reftable/pq_test.c to the unit testing framework

[Junio C Hamano]

Patrick Steinhardt <ps@pks.im> writes:

> ... the whole series LGTM now.
> Thanks!

Thanks, both.