tests: move t0009-prio-queue.sh to the new unit testing framework

PATCH Superseded Chandra Pratap via GitGitGadget 6 participants 15 messages Jan 14, 2024 – Jan 25, 2024 Kbuild

lore

Share & tools

lore

Chandra Pratap via GitGitGadget

author

2024-01-14 08:10 UTC #0 lore raw

PATCH 1/1 tests: move t0009-prio-queue.sh to the new unit testing framework

From: Chandra Pratap <[email protected]>

t/t0009-prio-queue.sh along with t/helper/test-prio-queue.c unit tests Git's implementation of a priority queue. Migrate the test over to the new unit testing framework to simplify debugging and reduce test run-time. Refactor the required logic and add a new test case in addition to porting over the original ones in shell.

Signed-off-by Chandra Pratap <[email protected]>

---
tests: move t0009-prio-queue.sh to the new unit testing framework

Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1642%2FChand-ra%2Fprio-queue-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1642/Chand-ra/prio-queue-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/1642

 Makefile                    |  2 +-
 t/helper/test-prio-queue.c  | 51 -------------------
 t/helper/test-tool.c        |  1 -
 t/helper/test-tool.h        |  1 -
 t/t0009-prio-queue.sh       | 66 -------------------------
 t/unit-tests/t-prio-queue.c | 99 +++++++++++++++++++++++++++++++++++++
 6 files changed, 100 insertions(+), 120 deletions(-)
 delete mode 100644 t/helper/test-prio-queue.c
 delete mode 100755 t/t0009-prio-queue.sh
 create mode 100644 t/unit-tests/t-prio-queue.c

Makefile +1 -1

index 312d95084c1..d5e48e656b3 100644
@@ -828,7 +828,6 @@ TEST_BUILTINS_OBJS += test-partial-clone.o
 TEST_BUILTINS_OBJS += test-path-utils.o
 TEST_BUILTINS_OBJS += test-pcre2-config.o
 TEST_BUILTINS_OBJS += test-pkt-line.o
-TEST_BUILTINS_OBJS += test-prio-queue.o
 TEST_BUILTINS_OBJS += test-proc-receive.o
 TEST_BUILTINS_OBJS += test-progress.o
 TEST_BUILTINS_OBJS += test-reach.o

@@ -1340,6 +1339,7 @@ THIRD_PARTY_SOURCES += sha1dc/%
 
 UNIT_TEST_PROGRAMS += t-basic
 UNIT_TEST_PROGRAMS += t-strbuf
+UNIT_TEST_PROGRAMS += t-prio-queue
 UNIT_TEST_PROGS = $(patsubst %,$(UNIT_TEST_BIN)/%$X,$(UNIT_TEST_PROGRAMS))
 UNIT_TEST_OBJS = $(patsubst %,$(UNIT_TEST_DIR)/%.o,$(UNIT_TEST_PROGRAMS))
 UNIT_TEST_OBJS += $(UNIT_TEST_DIR)/test-lib.o

t/helper/test-prio-queue.c deleted +0 ~~-51~~

51 lines not on this page · raw message

t/helper/test-tool.c +0 -1

index 876cd2dc313..5f591b9718f 100644
@@ -57,7 +57,6 @@ static struct test_cmd cmds[] = {
 	{ "path-utils", cmd__path_utils },
 	{ "pcre2-config", cmd__pcre2_config },
 	{ "pkt-line", cmd__pkt_line },
-	{ "prio-queue", cmd__prio_queue },
 	{ "proc-receive", cmd__proc_receive },
 	{ "progress", cmd__progress },
 	{ "reach", cmd__reach },

t/helper/test-tool.h +0 -1

index 70dd4eba119..b921138d8ec 100644
@@ -50,7 +50,6 @@ int cmd__partial_clone(int argc, const char **argv);
 int cmd__path_utils(int argc, const char **argv);
 int cmd__pcre2_config(int argc, const char **argv);
 int cmd__pkt_line(int argc, const char **argv);
-int cmd__prio_queue(int argc, const char **argv);
 int cmd__proc_receive(int argc, const char **argv);
 int cmd__progress(int argc, const char **argv);
 int cmd__reach(int argc, const char **argv);

t/t0009-prio-queue.sh deleted +0 ~~-66~~

66 lines not on this page · raw message

t/unit-tests/t-prio-queue.c new file +99 -0

99 lines not on this page · raw message

base-commit: 1a87c842ece327d03d08096395969aca5e0a6996

Signature · 1 line

gitgitgadget

Chandra Pratap

2024-01-14 08:16 UTC #1 lore raw

Please ignore the patch above, my e-mail client seems to have messed up the backslash indentation. I will follow up with the corrected patch shortly.

Quoted 311 lines · Chandra Pratap via GitGitGadget

From: Chandra Pratap <[email protected]>

Signed-off-by Chandra Pratap <[email protected]>

---
tests: move t0009-prio-queue.sh to the new unit testing framework

 Makefile                    |  2 +-
 t/helper/test-prio-queue.c  | 51 -------------------
 t/helper/test-tool.c        |  1 -
 t/helper/test-tool.h        |  1 -
 t/t0009-prio-queue.sh       | 66 -------------------------
 t/unit-tests/t-prio-queue.c | 99 +++++++++++++++++++++++++++++++++++++
 6 files changed, 100 insertions(+), 120 deletions(-)
 delete mode 100644 t/helper/test-prio-queue.c
 delete mode 100755 t/t0009-prio-queue.sh
 create mode 100644 t/unit-tests/t-prio-queue.c

Makefile +1 -1

index 312d95084c1..d5e48e656b3 100644
@@ -828,7 +828,6 @@ TEST_BUILTINS_OBJS += test-partial-clone.o
 TEST_BUILTINS_OBJS += test-path-utils.o
 TEST_BUILTINS_OBJS += test-pcre2-config.o
 TEST_BUILTINS_OBJS += test-pkt-line.o
-TEST_BUILTINS_OBJS += test-prio-queue.o
 TEST_BUILTINS_OBJS += test-proc-receive.o
 TEST_BUILTINS_OBJS += test-progress.o
 TEST_BUILTINS_OBJS += test-reach.o

@@ -1340,6 +1339,7 @@ THIRD_PARTY_SOURCES += sha1dc/%
 
 UNIT_TEST_PROGRAMS += t-basic
 UNIT_TEST_PROGRAMS += t-strbuf
+UNIT_TEST_PROGRAMS += t-prio-queue
 UNIT_TEST_PROGS = $(patsubst %,$(UNIT_TEST_BIN)/%$X,$(UNIT_TEST_PROGRAMS))
 UNIT_TEST_OBJS = $(patsubst %,$(UNIT_TEST_DIR)/%.o,$(UNIT_TEST_PROGRAMS))
 UNIT_TEST_OBJS += $(UNIT_TEST_DIR)/test-lib.o

t/helper/test-prio-queue.c deleted +0 ~~-51~~

deleted file mode 100644
index f0bf255f5f0..00000000000
@@ -1,51 +0,0 @@
-#include "test-tool.h"
-#include "prio-queue.h"
-
-static int intcmp(const void *va, const void *vb, void *data UNUSED)
-{
-       const int *a = va, *b = vb;
-       return *a - *b;
-}
-
-static void show(int *v)
-{
-       if (!v)
-               printf("NULL\n");
-       else
-               printf("%d\n", *v);
-       free(v);
-}
-
-int cmd__prio_queue(int argc UNUSED, const char **argv)
-{
-       struct prio_queue pq = { intcmp };
-
-       while (*++argv) {
-               if (!strcmp(*argv, "get")) {
-                       void *peek = prio_queue_peek(&pq);
-                       void *get = prio_queue_get(&pq);
-                       if (peek != get)
-                               BUG("peek and get results do not match");
-                       show(get);
-               } else if (!strcmp(*argv, "dump")) {
-                       void *peek;
-                       void *get;
-                       while ((peek = prio_queue_peek(&pq))) {
-                               get = prio_queue_get(&pq);
-                               if (peek != get)
-                                       BUG("peek and get results do not match");
-                               show(get);
-                       }
-               } else if (!strcmp(*argv, "stack")) {
-                       pq.compare = NULL;
-               } else {
-                       int *v = xmalloc(sizeof(*v));
-                       *v = atoi(*argv);
-                       prio_queue_put(&pq, v);
-               }
-       }
-
-       clear_prio_queue(&pq);
-
-       return 0;
-}

t/helper/test-tool.c +0 -1

index 876cd2dc313..5f591b9718f 100644
@@ -57,7 +57,6 @@ static struct test_cmd cmds[] = {
        { "path-utils", cmd__path_utils },
        { "pcre2-config", cmd__pcre2_config },
        { "pkt-line", cmd__pkt_line },
-       { "prio-queue", cmd__prio_queue },
        { "proc-receive", cmd__proc_receive },
        { "progress", cmd__progress },
        { "reach", cmd__reach },

t/helper/test-tool.h +0 -1

index 70dd4eba119..b921138d8ec 100644
@@ -50,7 +50,6 @@ int cmd__partial_clone(int argc, const char **argv);
 int cmd__path_utils(int argc, const char **argv);
 int cmd__pcre2_config(int argc, const char **argv);
 int cmd__pkt_line(int argc, const char **argv);
-int cmd__prio_queue(int argc, const char **argv);
 int cmd__proc_receive(int argc, const char **argv);
 int cmd__progress(int argc, const char **argv);
 int cmd__reach(int argc, const char **argv);

t/t0009-prio-queue.sh deleted +0 ~~-66~~

deleted file mode 100755
index eea99107a48..00000000000
@@ -1,66 +0,0 @@
-#!/bin/sh
-
-test_description='basic tests for priority queue implementation'
-
-TEST_PASSES_SANITIZE_LEAK=true
-. ./test-lib.sh
-
-cat >expect <<'EOF'
-1
-2
-3
-4
-5
-5
-6
-7
-8
-9
-10
-EOF
-test_expect_success 'basic ordering' '
-       test-tool prio-queue 2 6 3 10 9 5 7 4 5 8 1 dump >actual &&
-       test_cmp expect actual
-'
-
-cat >expect <<'EOF'
-2
-3
-4
-1
-5
-6
-EOF
-test_expect_success 'mixed put and get' '
-       test-tool prio-queue 6 2 4 get 5 3 get get 1 dump >actual &&
-       test_cmp expect actual
-'
-
-cat >expect <<'EOF'
-1
-2
-NULL
-1
-2
-NULL
-EOF
-test_expect_success 'notice empty queue' '
-       test-tool prio-queue 1 2 get get get 1 2 get get get >actual &&
-       test_cmp expect actual
-'
-
-cat >expect <<'EOF'
-3
-2
-6
-4
-5
-1
-8
-EOF
-test_expect_success 'stack order' '
-       test-tool prio-queue stack 8 1 5 4 6 2 3 dump >actual &&
-       test_cmp expect actual
-'
-
-test_done

t/unit-tests/t-prio-queue.c new file +99 -0

new file mode 100644
index 00000000000..98a69790f7e
@@ -0,0 +1,99 @@
+#include "test-lib.h"
+#include "prio-queue.h"
+
+static int intcmp(const void *va, const void *vb, void *data UNUSED)
+{
+       const int *a = va, *b = vb;
+       return *a - *b;
+}
+
+static int show(int *v)
+{
+       int ret = -1;
+       if (v)
+               ret = *v;
+       free(v);
+       return ret;
+}
+
+static int test_prio_queue(const char **input, int *result)
+{
+       struct prio_queue pq = { intcmp };
+       int i = 0;
+
+       while (*input) {
+               if (!strcmp(*input, "get")) {
+                       void *peek = prio_queue_peek(&pq);
+                       void *get = prio_queue_get(&pq);
+                       if (peek != get)
+                               BUG("peek and get results do not match");
+                       result[i++] = show(get);
+               } else if (!strcmp(*input, "dump")) {
+                       void *peek;
+                       void *get;
+                       while ((peek = prio_queue_peek(&pq))) {
+                               get = prio_queue_get(&pq);
+                               if (peek != get)
+                                       BUG("peek and get results do not match");
+                               result[i++] = show(get);
+                       }
+               } else if (!strcmp(*input, "stack")) {
+                       pq.compare = NULL;
+               } else if (!strcmp(*input, "reverse")) {
+                       prio_queue_reverse(&pq);
+               } else {
+                       int *v = xmalloc(sizeof(*v));
+                       *v = atoi(*input);
+                       prio_queue_put(&pq, v);
+               }
+               input++;
+       }
+
+       clear_prio_queue(&pq);
+
+       return 0;
+}
+
+#define INPUT_SIZE 6
+
+#define BASIC_INPUT "1", "2", "3", "4", "5", "5", "dump"
+#define BASIC_EXPECTED 1, 2, 3, 4, 5, 5
+
+#define MIXED_PUT_GET_INPUT "6", "2", "4", "get", "5", "3", "get", "get", "1", "dump"
+#define MIXED_PUT_GET_EXPECTED 2, 3, 4, 1, 5, 6
+
+#define EMPTY_QUEUE_INPUT "1", "2", "get", "get", "get", "1", "2", "get", "get", "get"
+#define EMPTY_QUEUE_EXPECTED 1, 2, -1, 1, 2, -1
+
+#define STACK_INPUT "stack", "1", "5", "4", "6", "2", "3", "dump"
+#define STACK_EXPECTED 3, 2, 6, 4, 5, 1
+
+#define REVERSE_STACK_INPUT "stack", "1", "2", "3", "4", "5", "6", "reverse", "dump"
+#define REVERSE_STACK_EXPECTED 1, 2, 3, 4, 5, 6
+
+#define TEST_INPUT(INPUT, EXPECTED, name)              \
+  static void test_##name(void)                                        \
+{                                                                                      \
+       const char *input[] = {INPUT};                                          \
+       int expected[] = {EXPECTED};                                    \
+       int result[INPUT_SIZE];                                                         \
+       test_prio_queue(input, result);                                         \
+       check(!memcmp(expected, result, sizeof(expected)));     \
+}
+
+TEST_INPUT(BASIC_INPUT, BASIC_EXPECTED, basic)
+TEST_INPUT(MIXED_PUT_GET_INPUT, MIXED_PUT_GET_EXPECTED, mixed)
+TEST_INPUT(EMPTY_QUEUE_INPUT, EMPTY_QUEUE_EXPECTED, empty)
+TEST_INPUT(STACK_INPUT, STACK_EXPECTED, stack)
+TEST_INPUT(REVERSE_STACK_INPUT, REVERSE_STACK_EXPECTED, reverse)
+
+int cmd_main(int argc, const char **argv)
+{
+       TEST(test_basic(), "prio-queue works for basic input");
+       TEST(test_mixed(), "prio-queue works for mixed put & get commands");
+       TEST(test_empty(), "prio-queue works when queue is empty");
+       TEST(test_stack(), "prio-queue works when used as a LIFO stack");
+       TEST(test_reverse(), "prio-queue works when LIFO stack is reversed");
+
+       return test_done();
+}

base-commit: 1a87c842ece327d03d08096395969aca5e0a6996 --
gitgitgadget

Chandra Pratap via GitGitGadget

author

2024-01-14 08:18 UTC #2 lore raw

PATCH v2 1/1 tests: move t0009-prio-queue.sh to the new unit testing framework

In reply to Chandra Pratap via GitGitGadget

From: Chandra Pratap <[email protected]>

Signed-off-by Chandra Pratap <[email protected]>

---
tests: move t0009-prio-queue.sh to the new unit testing framework

Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1642%2FChand-ra%2Fprio-queue-v2
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1642/Chand-ra/prio-queue-v2
Pull-Request: https://github.com/gitgitgadget/git/pull/1642

Range-diff vs v1:

1: ca20abe95ea ! 1: 60ac9b3c259 tests: move t0009-prio-queue.sh to the new unit testing framework

     @@ t/unit-tests/t-prio-queue.c (new)
      +#define REVERSE_STACK_INPUT "stack", "1", "2", "3", "4", "5", "6", "reverse", "dump"
      +#define REVERSE_STACK_EXPECTED 1, 2, 3, 4, 5, 6
      +
     -+#define TEST_INPUT(INPUT, EXPECTED, name)		\
     ++#define TEST_INPUT(INPUT, EXPECTED, name)			\
      +  static void test_##name(void)					\
     -+{											\
     -+	const char *input[] = {INPUT};						\
     -+	int expected[] = {EXPECTED};					\
     -+	int result[INPUT_SIZE];								\
     -+	test_prio_queue(input, result);						\
     ++{								\
     ++	const char *input[] = {INPUT};				\
     ++	int expected[] = {EXPECTED};				\
     ++	int result[INPUT_SIZE];					\
     ++	test_prio_queue(input, result);				\
      +	check(!memcmp(expected, result, sizeof(expected)));	\
      +}
      +

 Makefile                    |  2 +-
 t/helper/test-prio-queue.c  | 51 -------------------
 t/helper/test-tool.c        |  1 -
 t/helper/test-tool.h        |  1 -
 t/t0009-prio-queue.sh       | 66 -------------------------
 t/unit-tests/t-prio-queue.c | 99 +++++++++++++++++++++++++++++++++++++
 6 files changed, 100 insertions(+), 120 deletions(-)
 delete mode 100644 t/helper/test-prio-queue.c
 delete mode 100755 t/t0009-prio-queue.sh
 create mode 100644 t/unit-tests/t-prio-queue.c

Makefile +1 -1

index 312d95084c1..d5e48e656b3 100644
@@ -828,7 +828,6 @@ TEST_BUILTINS_OBJS += test-partial-clone.o
 TEST_BUILTINS_OBJS += test-path-utils.o
 TEST_BUILTINS_OBJS += test-pcre2-config.o
 TEST_BUILTINS_OBJS += test-pkt-line.o
-TEST_BUILTINS_OBJS += test-prio-queue.o
 TEST_BUILTINS_OBJS += test-proc-receive.o
 TEST_BUILTINS_OBJS += test-progress.o
 TEST_BUILTINS_OBJS += test-reach.o

@@ -1340,6 +1339,7 @@ THIRD_PARTY_SOURCES += sha1dc/%
 
 UNIT_TEST_PROGRAMS += t-basic
 UNIT_TEST_PROGRAMS += t-strbuf
+UNIT_TEST_PROGRAMS += t-prio-queue
 UNIT_TEST_PROGS = $(patsubst %,$(UNIT_TEST_BIN)/%$X,$(UNIT_TEST_PROGRAMS))
 UNIT_TEST_OBJS = $(patsubst %,$(UNIT_TEST_DIR)/%.o,$(UNIT_TEST_PROGRAMS))
 UNIT_TEST_OBJS += $(UNIT_TEST_DIR)/test-lib.o

t/helper/test-prio-queue.c deleted +0 ~~-51~~

51 lines not on this page · raw message

t/helper/test-tool.c +0 -1

index 876cd2dc313..5f591b9718f 100644
@@ -57,7 +57,6 @@ static struct test_cmd cmds[] = {
 	{ "path-utils", cmd__path_utils },
 	{ "pcre2-config", cmd__pcre2_config },
 	{ "pkt-line", cmd__pkt_line },
-	{ "prio-queue", cmd__prio_queue },
 	{ "proc-receive", cmd__proc_receive },
 	{ "progress", cmd__progress },
 	{ "reach", cmd__reach },

t/helper/test-tool.h +0 -1

index 70dd4eba119..b921138d8ec 100644
@@ -50,7 +50,6 @@ int cmd__partial_clone(int argc, const char **argv);
 int cmd__path_utils(int argc, const char **argv);
 int cmd__pcre2_config(int argc, const char **argv);
 int cmd__pkt_line(int argc, const char **argv);
-int cmd__prio_queue(int argc, const char **argv);
 int cmd__proc_receive(int argc, const char **argv);
 int cmd__progress(int argc, const char **argv);
 int cmd__reach(int argc, const char **argv);

t/t0009-prio-queue.sh deleted +0 ~~-66~~

66 lines not on this page · raw message

t/unit-tests/t-prio-queue.c new file +99 -0

99 lines not on this page · raw message

base-commit: 1a87c842ece327d03d08096395969aca5e0a6996

Signature · 1 line

gitgitgadget

Junio C Hamano

2024-01-16 16:36 UTC #3 lore raw

Quoted 6 lines · Chandra Pratap via GitGitGadget

t/unit-tests/t-prio-queue.c new file +0 -0
new file mode 100644
index 00000000000..07b112f5894

t/unit-tests/t-prio-queue.c line 8

Quoted 8 lines

t/unit-tests/t-prio-queue.c new file +8 -0

@@ -0,0 +1,99 @@
+#include "test-lib.h"
+#include "prio-queue.h"
+
+static int intcmp(const void *va, const void *vb, void *data UNUSED)
+{
+	const int *a = va, *b = vb;
+	return *a - *b;
+}

This came from the original and looks obviously OK.

t/unit-tests/t-prio-queue.c line 17

Quoted 8 lines

t/unit-tests/t-prio-queue.c new file +8 -0

+static int show(int *v)
+{
+	int ret = -1;
+	if (v)
+		ret = *v;
+	free(v);
+	return ret;
+}

The original allowed us to differentiate "prio queue did not yield anything" case and "the integer obtained from the queue happened to be negative" cases, but with this, -1 is taken.

It is not a huge loss, as the tests can limit themselves to a subset of "int" (say, positive integers only). But this realization can lead to further simplfication.

t/unit-tests/t-prio-queue.c line 19

Quoted 1 line

t/unit-tests/t-prio-queue.c new file +1 -0
+static int test_prio_queue(const char **input, int *result)

This takes an array of strings, but it does not have to. Make it take an array of "int" and then with something like

	#define MISSING	-1
        #define GET	-2
        #define DUMP	-3
	#define STACK	-4

you can get rid of strcmp(), atoi(), and xmalloc(), like so:

	while (*input) {
		int val = *input++;

		switch (val) {
		case GET:
			void *peek = prio_queue_peek(&pq);
			...
			result[i++] = peek ? (*(int*)peek) : MISSING;
			break;
		... other "commands" here ...
		default:
			prio_queue_put(&pq, val);
			break;			
		}
	}

I inlined the show() in the above illustration, but you can keep it as a separate small helper function. The point is that it makes it far easier to follow by using the MISSING symbolic constant either way.

Quoted 28 lines

t/unit-tests/t-prio-queue.c new file +28 -0

+{
+	struct prio_queue pq = { intcmp };
+	int i = 0;
+
+	while (*input) {
+		if (!strcmp(*input, "get")) {
+			void *peek = prio_queue_peek(&pq);
+			void *get = prio_queue_get(&pq);
+			if (peek != get)
+				BUG("peek and get results do not match");
+			result[i++] = show(get);
+		} else if (!strcmp(*input, "dump")) {
+			void *peek;
+			void *get;
+			while ((peek = prio_queue_peek(&pq))) {
+				get = prio_queue_get(&pq);
+				if (peek != get)
+					BUG("peek and get results do not match");
+				result[i++] = show(get);
+			}
+		} else if (!strcmp(*input, "stack")) {
+			pq.compare = NULL;
+		} else if (!strcmp(*input, "reverse")) {
+			prio_queue_reverse(&pq);
+		} else {
+			int *v = xmalloc(sizeof(*v));
+			*v = atoi(*input);
+			prio_queue_put(&pq, v);

t/unit-tests/t-prio-queue.c line 57

Quoted 10 lines

t/unit-tests/t-prio-queue.c new file +10 -0

+		}
+		input++;
+	}
+
+	clear_prio_queue(&pq);
+
+	return 0;
+}
+
+#define INPUT_SIZE 6

You do not need this (see below)

t/unit-tests/t-prio-queue.c line 66

Quoted 8 lines

t/unit-tests/t-prio-queue.c new file +8 -0

+#define BASIC_INPUT "1", "2", "3", "4", "5", "5", "dump"
+#define BASIC_EXPECTED 1, 2, 3, 4, 5, 5
+
+#define MIXED_PUT_GET_INPUT "6", "2", "4", "get", "5", "3", "get", "get", "1", "dump"
+#define MIXED_PUT_GET_EXPECTED 2, 3, 4, 1, 5, 6
+
+#define EMPTY_QUEUE_INPUT "1", "2", "get", "get", "get", "1", "2", "get", "get", "get"
+#define EMPTY_QUEUE_EXPECTED 1, 2, -1, 1, 2, -1

And these input and expectation can become all integers, i.e.

	#define EMPTY_QUEUE_INPUT 1, 2, GET, GET, GET, 1, 2, GET, GET, GET
	#define EMPTY_QUEUE_EXPECTED 1, 2, MISSING, 1, 2, MISSING

t/unit-tests/t-prio-queue.c line 79

Quoted 13 lines

t/unit-tests/t-prio-queue.c new file +13 -0

+
+#define STACK_INPUT "stack", "1", "5", "4", "6", "2", "3", "dump"
+#define STACK_EXPECTED 3, 2, 6, 4, 5, 1
+
+#define REVERSE_STACK_INPUT "stack", "1", "2", "3", "4", "5", "6", "reverse", "dump"
+#define REVERSE_STACK_EXPECTED 1, 2, 3, 4, 5, 6
+
+#define TEST_INPUT(INPUT, EXPECTED, name)			\
+  static void test_##name(void)					\
+{								\
+	const char *input[] = {INPUT};				\
+	int expected[] = {EXPECTED};				\
+	int result[INPUT_SIZE];					\

This can be written more like

int result[ARRAY_SIZE(expected)]

so that you can freely extend each test without having to worry about increasing the hardcoded limit.

Quoted 22 lines

t/unit-tests/t-prio-queue.c new file +20 -0

+	test_prio_queue(input, result);				\
+	check(!memcmp(expected, result, sizeof(expected)));	\
+}
+
+TEST_INPUT(BASIC_INPUT, BASIC_EXPECTED, basic)
+TEST_INPUT(MIXED_PUT_GET_INPUT, MIXED_PUT_GET_EXPECTED, mixed)
+TEST_INPUT(EMPTY_QUEUE_INPUT, EMPTY_QUEUE_EXPECTED, empty)
+TEST_INPUT(STACK_INPUT, STACK_EXPECTED, stack)
+TEST_INPUT(REVERSE_STACK_INPUT, REVERSE_STACK_EXPECTED, reverse)
+
+int cmd_main(int argc, const char **argv)
+{
+	TEST(test_basic(), "prio-queue works for basic input");
+	TEST(test_mixed(), "prio-queue works for mixed put & get commands");
+	TEST(test_empty(), "prio-queue works when queue is empty");
+	TEST(test_stack(), "prio-queue works when used as a LIFO stack");
+	TEST(test_reverse(), "prio-queue works when LIFO stack is reversed");
+
+	return test_done();
+}

base-commit: 1a87c842ece327d03d08096395969aca5e0a6996

Josh Steadmon

2024-01-17 06:01 UTC #4 lore raw

In reply to Chandra Pratap via GitGitGadget

Quoted 247 lines · Chandra Pratap via GitGitGadget

From: Chandra Pratap <[email protected]>

Signed-off-by Chandra Pratap <[email protected]>

---
tests: move t0009-prio-queue.sh to the new unit testing framework

Range-diff vs v1:

1: ca20abe95ea ! 1: 60ac9b3c259 tests: move t0009-prio-queue.sh to the new unit testing framework

     @@ t/unit-tests/t-prio-queue.c (new)
      +#define REVERSE_STACK_INPUT "stack", "1", "2", "3", "4", "5", "6", "reverse", "dump"
      +#define REVERSE_STACK_EXPECTED 1, 2, 3, 4, 5, 6
      +
     -+#define TEST_INPUT(INPUT, EXPECTED, name)		\
     ++#define TEST_INPUT(INPUT, EXPECTED, name)			\
      +  static void test_##name(void)					\
     -+{											\
     -+	const char *input[] = {INPUT};						\
     -+	int expected[] = {EXPECTED};					\
     -+	int result[INPUT_SIZE];								\
     -+	test_prio_queue(input, result);						\
     ++{								\
     ++	const char *input[] = {INPUT};				\
     ++	int expected[] = {EXPECTED};				\
     ++	int result[INPUT_SIZE];					\
     ++	test_prio_queue(input, result);				\
      +	check(!memcmp(expected, result, sizeof(expected)));	\
      +}
      +

 Makefile                    |  2 +-
 t/helper/test-prio-queue.c  | 51 -------------------
 t/helper/test-tool.c        |  1 -
 t/helper/test-tool.h        |  1 -
 t/t0009-prio-queue.sh       | 66 -------------------------
 t/unit-tests/t-prio-queue.c | 99 +++++++++++++++++++++++++++++++++++++
 6 files changed, 100 insertions(+), 120 deletions(-)
 delete mode 100644 t/helper/test-prio-queue.c
 delete mode 100755 t/t0009-prio-queue.sh
 create mode 100644 t/unit-tests/t-prio-queue.c

Makefile +1 -1

index 312d95084c1..d5e48e656b3 100644
@@ -828,7 +828,6 @@ TEST_BUILTINS_OBJS += test-partial-clone.o
 TEST_BUILTINS_OBJS += test-path-utils.o
 TEST_BUILTINS_OBJS += test-pcre2-config.o
 TEST_BUILTINS_OBJS += test-pkt-line.o
-TEST_BUILTINS_OBJS += test-prio-queue.o
 TEST_BUILTINS_OBJS += test-proc-receive.o
 TEST_BUILTINS_OBJS += test-progress.o
 TEST_BUILTINS_OBJS += test-reach.o

@@ -1340,6 +1339,7 @@ THIRD_PARTY_SOURCES += sha1dc/%
 
 UNIT_TEST_PROGRAMS += t-basic
 UNIT_TEST_PROGRAMS += t-strbuf
+UNIT_TEST_PROGRAMS += t-prio-queue
 UNIT_TEST_PROGS = $(patsubst %,$(UNIT_TEST_BIN)/%$X,$(UNIT_TEST_PROGRAMS))
 UNIT_TEST_OBJS = $(patsubst %,$(UNIT_TEST_DIR)/%.o,$(UNIT_TEST_PROGRAMS))
 UNIT_TEST_OBJS += $(UNIT_TEST_DIR)/test-lib.o

t/helper/test-prio-queue.c deleted +0 ~~-51~~

deleted file mode 100644
index f0bf255f5f0..00000000000
@@ -1,51 +0,0 @@
-#include "test-tool.h"
-#include "prio-queue.h"
-
-static int intcmp(const void *va, const void *vb, void *data UNUSED)
-{
-	const int *a = va, *b = vb;
-	return *a - *b;
-}
-
-static void show(int *v)
-{
-	if (!v)
-		printf("NULL\n");
-	else
-		printf("%d\n", *v);
-	free(v);
-}
-
-int cmd__prio_queue(int argc UNUSED, const char **argv)
-{
-	struct prio_queue pq = { intcmp };
-
-	while (*++argv) {
-		if (!strcmp(*argv, "get")) {
-			void *peek = prio_queue_peek(&pq);
-			void *get = prio_queue_get(&pq);
-			if (peek != get)
-				BUG("peek and get results do not match");
-			show(get);
-		} else if (!strcmp(*argv, "dump")) {
-			void *peek;
-			void *get;
-			while ((peek = prio_queue_peek(&pq))) {
-				get = prio_queue_get(&pq);
-				if (peek != get)
-					BUG("peek and get results do not match");
-				show(get);
-			}
-		} else if (!strcmp(*argv, "stack")) {
-			pq.compare = NULL;
-		} else {
-			int *v = xmalloc(sizeof(*v));
-			*v = atoi(*argv);
-			prio_queue_put(&pq, v);
-		}
-	}
-
-	clear_prio_queue(&pq);
-
-	return 0;
-}

t/helper/test-tool.c +0 -1

index 876cd2dc313..5f591b9718f 100644
@@ -57,7 +57,6 @@ static struct test_cmd cmds[] = {
 	{ "path-utils", cmd__path_utils },
 	{ "pcre2-config", cmd__pcre2_config },
 	{ "pkt-line", cmd__pkt_line },
-	{ "prio-queue", cmd__prio_queue },
 	{ "proc-receive", cmd__proc_receive },
 	{ "progress", cmd__progress },
 	{ "reach", cmd__reach },

t/helper/test-tool.h +0 -1

index 70dd4eba119..b921138d8ec 100644
@@ -50,7 +50,6 @@ int cmd__partial_clone(int argc, const char **argv);
 int cmd__path_utils(int argc, const char **argv);
 int cmd__pcre2_config(int argc, const char **argv);
 int cmd__pkt_line(int argc, const char **argv);
-int cmd__prio_queue(int argc, const char **argv);
 int cmd__proc_receive(int argc, const char **argv);
 int cmd__progress(int argc, const char **argv);
 int cmd__reach(int argc, const char **argv);

t/t0009-prio-queue.sh deleted +0 ~~-66~~

deleted file mode 100755
index eea99107a48..00000000000
@@ -1,66 +0,0 @@
-#!/bin/sh
-
-test_description='basic tests for priority queue implementation'
-
-TEST_PASSES_SANITIZE_LEAK=true
-. ./test-lib.sh
-
-cat >expect <<'EOF'
-1
-2
-3
-4
-5
-5
-6
-7
-8
-9
-10
-EOF
-test_expect_success 'basic ordering' '
-	test-tool prio-queue 2 6 3 10 9 5 7 4 5 8 1 dump >actual &&
-	test_cmp expect actual
-'
-
-cat >expect <<'EOF'
-2
-3
-4
-1
-5
-6
-EOF
-test_expect_success 'mixed put and get' '
-	test-tool prio-queue 6 2 4 get 5 3 get get 1 dump >actual &&
-	test_cmp expect actual
-'
-
-cat >expect <<'EOF'
-1
-2
-NULL
-1
-2
-NULL
-EOF
-test_expect_success 'notice empty queue' '
-	test-tool prio-queue 1 2 get get get 1 2 get get get >actual &&
-	test_cmp expect actual
-'
-
-cat >expect <<'EOF'
-3
-2
-6
-4
-5
-1
-8
-EOF
-test_expect_success 'stack order' '
-	test-tool prio-queue stack 8 1 5 4 6 2 3 dump >actual &&
-	test_cmp expect actual
-'
-
-test_done

t/unit-tests/t-prio-queue.c new file +15 -0

new file mode 100644
index 00000000000..07b112f5894
@@ -0,0 +1,99 @@
+#include "test-lib.h"
+#include "prio-queue.h"
+
+static int intcmp(const void *va, const void *vb, void *data UNUSED)
+{
+	const int *a = va, *b = vb;
+	return *a - *b;
+}
+
+static int show(int *v)
+{
+	int ret = -1;
+	if (v)
+		ret = *v;
+	free(v);

t/unit-tests/t-prio-queue.c line 25

Quoted 10 lines

t/unit-tests/t-prio-queue.c new file +10 -0

+	return ret;
+}
+
+static int test_prio_queue(const char **input, int *result)
+{
+	struct prio_queue pq = { intcmp };
+	int i = 0;
+
+	while (*input) {
+		if (!strcmp(*input, "get")) {

Running the test segfaults at the above strcmp() for me, from the very first test_basic test case. I'm not sure why, there's not an obvious problem that I can see. Does it run properly for you?

Quoted 78 lines

t/unit-tests/t-prio-queue.c new file +74 -0

+			void *peek = prio_queue_peek(&pq);
+			void *get = prio_queue_get(&pq);
+			if (peek != get)
+				BUG("peek and get results do not match");
+			result[i++] = show(get);
+		} else if (!strcmp(*input, "dump")) {
+			void *peek;
+			void *get;
+			while ((peek = prio_queue_peek(&pq))) {
+				get = prio_queue_get(&pq);
+				if (peek != get)
+					BUG("peek and get results do not match");
+				result[i++] = show(get);
+			}
+		} else if (!strcmp(*input, "stack")) {
+			pq.compare = NULL;
+		} else if (!strcmp(*input, "reverse")) {
+			prio_queue_reverse(&pq);
+		} else {
+			int *v = xmalloc(sizeof(*v));
+			*v = atoi(*input);
+			prio_queue_put(&pq, v);
+		}
+		input++;
+	}
+
+	clear_prio_queue(&pq);
+
+	return 0;
+}
+
+#define INPUT_SIZE 6
+
+#define BASIC_INPUT "1", "2", "3", "4", "5", "5", "dump"
+#define BASIC_EXPECTED 1, 2, 3, 4, 5, 5
+
+#define MIXED_PUT_GET_INPUT "6", "2", "4", "get", "5", "3", "get", "get", "1", "dump"
+#define MIXED_PUT_GET_EXPECTED 2, 3, 4, 1, 5, 6
+
+#define EMPTY_QUEUE_INPUT "1", "2", "get", "get", "get", "1", "2", "get", "get", "get"
+#define EMPTY_QUEUE_EXPECTED 1, 2, -1, 1, 2, -1
+
+#define STACK_INPUT "stack", "1", "5", "4", "6", "2", "3", "dump"
+#define STACK_EXPECTED 3, 2, 6, 4, 5, 1
+
+#define REVERSE_STACK_INPUT "stack", "1", "2", "3", "4", "5", "6", "reverse", "dump"
+#define REVERSE_STACK_EXPECTED 1, 2, 3, 4, 5, 6
+
+#define TEST_INPUT(INPUT, EXPECTED, name)			\
+  static void test_##name(void)					\
+{								\
+	const char *input[] = {INPUT};				\
+	int expected[] = {EXPECTED};				\
+	int result[INPUT_SIZE];					\
+	test_prio_queue(input, result);				\
+	check(!memcmp(expected, result, sizeof(expected)));	\
+}
+
+TEST_INPUT(BASIC_INPUT, BASIC_EXPECTED, basic)
+TEST_INPUT(MIXED_PUT_GET_INPUT, MIXED_PUT_GET_EXPECTED, mixed)
+TEST_INPUT(EMPTY_QUEUE_INPUT, EMPTY_QUEUE_EXPECTED, empty)
+TEST_INPUT(STACK_INPUT, STACK_EXPECTED, stack)
+TEST_INPUT(REVERSE_STACK_INPUT, REVERSE_STACK_EXPECTED, reverse)
+
+int cmd_main(int argc, const char **argv)
+{
+	TEST(test_basic(), "prio-queue works for basic input");
+	TEST(test_mixed(), "prio-queue works for mixed put & get commands");
+	TEST(test_empty(), "prio-queue works when queue is empty");
+	TEST(test_stack(), "prio-queue works when used as a LIFO stack");
+	TEST(test_reverse(), "prio-queue works when LIFO stack is reversed");
+
+	return test_done();
+}

base-commit: 1a87c842ece327d03d08096395969aca5e0a6996

Signature · 1 line

gitgitgadget

Chandra Pratap via GitGitGadget

author

2024-01-17 14:38 UTC #5 lore raw

PATCH v3 1/1 tests: move t0009-prio-queue.sh to the new unit testing framework

In reply to Chandra Pratap via GitGitGadget

From: Chandra Pratap <[email protected]>

Signed-off-by Chandra Pratap <[email protected]>

---
tests: move t0009-prio-queue.sh to the new unit testing framework

Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1642%2FChand-ra%2Fprio-queue-v3
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1642/Chand-ra/prio-queue-v3
Pull-Request: https://github.com/gitgitgadget/git/pull/1642

Range-diff vs v2:

1: 60ac9b3c259 ! 1: 6b10028177a tests: move t0009-prio-queue.sh to the new unit testing framework

     @@ t/unit-tests/t-prio-queue.c (new)
      +	return *a - *b;
      +}
      +
     ++
     ++#define MISSING  -1
     ++#define DUMP	 -2
     ++#define STACK	 -3
     ++#define GET	 -4
     ++#define REVERSE  -5
     ++
      +static int show(int *v)
      +{
     -+	int ret = -1;
     -+	if (v)
     -+		ret = *v;
     -+	free(v);
     -+	return ret;
     ++	return v ? *v : MISSING;
      +}
      +
     -+static int test_prio_queue(const char **input, int *result)
     ++static int test_prio_queue(int *input, int *result)
      +{
      +	struct prio_queue pq = { intcmp };
      +	int i = 0;
      +
      +	while (*input) {
     -+		if (!strcmp(*input, "get")) {
     -+			void *peek = prio_queue_peek(&pq);
     -+			void *get = prio_queue_get(&pq);
     -+			if (peek != get)
     -+				BUG("peek and get results do not match");
     -+			result[i++] = show(get);
     -+		} else if (!strcmp(*input, "dump")) {
     -+			void *peek;
     -+			void *get;
     -+			while ((peek = prio_queue_peek(&pq))) {
     ++		int *val = input++;
     ++		void *peek, *get;
     ++		switch(*val) {
     ++			case GET:
     ++				peek = prio_queue_peek(&pq);
      +				get = prio_queue_get(&pq);
      +				if (peek != get)
     -+					BUG("peek and get results do not match");
     ++					BUG("peek and get results don't match");
      +				result[i++] = show(get);
     -+			}
     -+		} else if (!strcmp(*input, "stack")) {
     -+			pq.compare = NULL;
     -+		} else if (!strcmp(*input, "reverse")) {
     -+			prio_queue_reverse(&pq);
     -+		} else {
     -+			int *v = xmalloc(sizeof(*v));
     -+			*v = atoi(*input);
     -+			prio_queue_put(&pq, v);
     ++				break;
     ++			case DUMP:
     ++				while ((peek = prio_queue_peek(&pq))) {
     ++					get = prio_queue_get(&pq);
     ++					if (peek != get)
     ++						BUG("peek and get results don't match");
     ++					result[i++] = show(get);
     ++				}
     ++				break;
     ++			case STACK:
     ++				pq.compare = NULL;
     ++				break;
     ++			case REVERSE:
     ++				prio_queue_reverse(&pq);
     ++				break;
     ++			default:
     ++				prio_queue_put(&pq, val);
     ++				break;
      +		}
     -+		input++;
      +	}
     -+
      +	clear_prio_queue(&pq);
     -+
      +	return 0;
      +}
      +
     -+#define INPUT_SIZE 6
     -+
     -+#define BASIC_INPUT "1", "2", "3", "4", "5", "5", "dump"
     ++#define BASIC_INPUT 1, 2, 3, 4, 5, 5, DUMP
      +#define BASIC_EXPECTED 1, 2, 3, 4, 5, 5
      +
     -+#define MIXED_PUT_GET_INPUT "6", "2", "4", "get", "5", "3", "get", "get", "1", "dump"
     ++#define MIXED_PUT_GET_INPUT 6, 2, 4, GET, 5, 3, GET, GET, 1, DUMP
      +#define MIXED_PUT_GET_EXPECTED 2, 3, 4, 1, 5, 6
      +
     -+#define EMPTY_QUEUE_INPUT "1", "2", "get", "get", "get", "1", "2", "get", "get", "get"
     -+#define EMPTY_QUEUE_EXPECTED 1, 2, -1, 1, 2, -1
     ++#define EMPTY_QUEUE_INPUT 1, 2, GET, GET, GET, 1, 2, GET, GET, GET
     ++#define EMPTY_QUEUE_EXPECTED 1, 2, MISSING, 1, 2, MISSING
      +
     -+#define STACK_INPUT "stack", "1", "5", "4", "6", "2", "3", "dump"
     ++#define STACK_INPUT STACK, 1, 5, 4, 6, 2, 3, DUMP
      +#define STACK_EXPECTED 3, 2, 6, 4, 5, 1
      +
     -+#define REVERSE_STACK_INPUT "stack", "1", "2", "3", "4", "5", "6", "reverse", "dump"
     ++#define REVERSE_STACK_INPUT STACK, 1, 2, 3, 4, 5, 6, REVERSE, DUMP
      +#define REVERSE_STACK_EXPECTED 1, 2, 3, 4, 5, 6
      +
      +#define TEST_INPUT(INPUT, EXPECTED, name)			\
     -+  static void test_##name(void)					\
     ++  static void test_##name(void)				\
      +{								\
     -+	const char *input[] = {INPUT};				\
     ++	int input[] = {INPUT};					\
      +	int expected[] = {EXPECTED};				\
     -+	int result[INPUT_SIZE];					\
     ++	int result[ARRAY_SIZE(expected)];			\
      +	test_prio_queue(input, result);				\
      +	check(!memcmp(expected, result, sizeof(expected)));	\
      +}

 Makefile                    |   2 +-
 t/helper/test-prio-queue.c  |  51 ------------------
 t/helper/test-tool.c        |   1 -
 t/helper/test-tool.h        |   1 -
 t/t0009-prio-queue.sh       |  66 -----------------------
 t/unit-tests/t-prio-queue.c | 101 ++++++++++++++++++++++++++++++++++++
 6 files changed, 102 insertions(+), 120 deletions(-)
 delete mode 100644 t/helper/test-prio-queue.c
 delete mode 100755 t/t0009-prio-queue.sh
 create mode 100644 t/unit-tests/t-prio-queue.c

Makefile +1 -1

index 312d95084c1..d5e48e656b3 100644
@@ -828,7 +828,6 @@ TEST_BUILTINS_OBJS += test-partial-clone.o
 TEST_BUILTINS_OBJS += test-path-utils.o
 TEST_BUILTINS_OBJS += test-pcre2-config.o
 TEST_BUILTINS_OBJS += test-pkt-line.o
-TEST_BUILTINS_OBJS += test-prio-queue.o
 TEST_BUILTINS_OBJS += test-proc-receive.o
 TEST_BUILTINS_OBJS += test-progress.o
 TEST_BUILTINS_OBJS += test-reach.o

@@ -1340,6 +1339,7 @@ THIRD_PARTY_SOURCES += sha1dc/%
 
 UNIT_TEST_PROGRAMS += t-basic
 UNIT_TEST_PROGRAMS += t-strbuf
+UNIT_TEST_PROGRAMS += t-prio-queue
 UNIT_TEST_PROGS = $(patsubst %,$(UNIT_TEST_BIN)/%$X,$(UNIT_TEST_PROGRAMS))
 UNIT_TEST_OBJS = $(patsubst %,$(UNIT_TEST_DIR)/%.o,$(UNIT_TEST_PROGRAMS))
 UNIT_TEST_OBJS += $(UNIT_TEST_DIR)/test-lib.o

t/helper/test-prio-queue.c deleted +0 ~~-51~~

51 lines not on this page · raw message

t/helper/test-tool.c +0 -1

index 876cd2dc313..5f591b9718f 100644
@@ -57,7 +57,6 @@ static struct test_cmd cmds[] = {
 	{ "path-utils", cmd__path_utils },
 	{ "pcre2-config", cmd__pcre2_config },
 	{ "pkt-line", cmd__pkt_line },
-	{ "prio-queue", cmd__prio_queue },
 	{ "proc-receive", cmd__proc_receive },
 	{ "progress", cmd__progress },
 	{ "reach", cmd__reach },

t/helper/test-tool.h +0 -1

index 70dd4eba119..b921138d8ec 100644
@@ -50,7 +50,6 @@ int cmd__partial_clone(int argc, const char **argv);
 int cmd__path_utils(int argc, const char **argv);
 int cmd__pcre2_config(int argc, const char **argv);
 int cmd__pkt_line(int argc, const char **argv);
-int cmd__prio_queue(int argc, const char **argv);
 int cmd__proc_receive(int argc, const char **argv);
 int cmd__progress(int argc, const char **argv);
 int cmd__reach(int argc, const char **argv);

t/t0009-prio-queue.sh deleted +0 ~~-66~~

66 lines not on this page · raw message

t/unit-tests/t-prio-queue.c new file +101 -0

101 lines not on this page · raw message

base-commit: 1a87c842ece327d03d08096395969aca5e0a6996

Signature · 1 line

gitgitgadget

Junio C Hamano

2024-01-17 21:52 UTC #6 lore raw

t/unit-tests/t-prio-queue.c line 30

Quoted 9 lines · Chandra Pratap via GitGitGadget

t/unit-tests/t-prio-queue.c new file +9 -0

+static int test_prio_queue(int *input, int *result)
+{
+	struct prio_queue pq = { intcmp };
+	int i = 0;
+
+	while (*input) {
+		int *val = input++;
+		void *peek, *get;
+		switch(*val) {

Ah, this one is a bit tricky. I would have expected that we can make val a pure integer, but because we need to give the address of the element to be placed in the queue, not the value to be placed as an element in the queue, to prio_queue_put(), we would need the pointer.

I wonder if writing this as a more conventional for(;;) loop would make it easier to handle, i.e.

	int val, i;

	for (i = 0; (val = *input); input++) {
		switch (val) {
		case ...:
		...
		default:
			prio_queue_put(&pq, input);
			break;
		}
	}

Quoted 4 lines

+...
t/unit-tests/t-prio-queue.c new file +3 -0
+			default:
+				prio_queue_put(&pq, val);
+				break;

t/unit-tests/t-prio-queue.c line 79

Quoted 10 lines

t/unit-tests/t-prio-queue.c new file +9 -0

+		}
+	}
+	clear_prio_queue(&pq);
+	return 0;
+}
 
+#define TEST_INPUT(INPUT, EXPECTED, name)			\
+  static void test_##name(void)				\
+{								\
+	int input[] = {INPUT};					\

I think I missed this myself in my review the last round, but we need the sentinel value 0 at the end, i.e.,

	int input[] = {INPUT, 0};

because the test_prio_queue() loops "while (*input)". Otherwise the loop would not terminate.

t/unit-tests/t-prio-queue.c line 81

Quoted 2 lines

t/unit-tests/t-prio-queue.c new file +2 -0
+	int expected[] = {EXPECTED};				\
+	int result[ARRAY_SIZE(expected)];			\

These arrays are correct.

t/unit-tests/t-prio-queue.c line 83

Quoted 2 lines

t/unit-tests/t-prio-queue.c new file +2 -0

+	test_prio_queue(input, result);				\
+	check(!memcmp(expected, result, sizeof(expected)));	\

So is this check.

Quoted 8 lines

t/unit-tests/t-prio-queue.c new file +8 -0

+}
+
+TEST_INPUT(BASIC_INPUT, BASIC_EXPECTED, basic)
+TEST_INPUT(MIXED_PUT_GET_INPUT, MIXED_PUT_GET_EXPECTED, mixed)
+TEST_INPUT(EMPTY_QUEUE_INPUT, EMPTY_QUEUE_EXPECTED, empty)
+TEST_INPUT(STACK_INPUT, STACK_EXPECTED, stack)
+TEST_INPUT(REVERSE_STACK_INPUT, REVERSE_STACK_EXPECTED, reverse)
+

t/unit-tests/t-prio-queue.c line 101

Quoted 10 lines

t/unit-tests/t-prio-queue.c new file +10 -0

+int cmd_main(int argc, const char **argv)
+{
+	TEST(test_basic(), "prio-queue works for basic input");
+	TEST(test_mixed(), "prio-queue works for mixed put & get commands");
+	TEST(test_empty(), "prio-queue works when queue is empty");
+	TEST(test_stack(), "prio-queue works when used as a LIFO stack");
+	TEST(test_reverse(), "prio-queue works when LIFO stack is reversed");
+
+	return test_done();
+}

Other than that, looking good. Thanks.

Junio C Hamano

2024-01-17 21:58 UTC #7 lore raw

In reply to Chandra Pratap via GitGitGadget

I forgot to examine the contents of the tests themselves.

Quoted 7 lines

t/t0009-prio-queue.sh deleted +0 -7
-cat >expect <<'EOF'
-1
-2
-3
-4
-5
-5

t/t0009-prio-queue.sh line 24

Quoted 10 lines

t/t0009-prio-queue.sh deleted +0 ~~-10~~

-6
-7
-8
-9
-10
-EOF
-test_expect_success 'basic ordering' '
-	test-tool prio-queue 2 6 3 10 9 5 7 4 5 8 1 dump >actual &&
-	test_cmp expect actual
-'

This seems to have been lost from the converted test. Your basic input test feeds an already sorted array of 6 items and dump to see they are the same already sorted array, which is a lot less interesting than the above.

t/t0009-prio-queue.sh line 37

Quoted 12 lines

t/t0009-prio-queue.sh deleted +0 ~~-12~~

-cat >expect <<'EOF'
-2
-3
-4
-1
-5
-6
-EOF
-test_expect_success 'mixed put and get' '
-	test-tool prio-queue 6 2 4 get 5 3 get get 1 dump >actual &&
-	test_cmp expect actual
-'

This is a faithful conversion.

t/t0009-prio-queue.sh line 50

Quoted 12 lines

t/t0009-prio-queue.sh deleted +0 ~~-12~~

-cat >expect <<'EOF'
-1
-2
-NULL
-1
-2
-NULL
-EOF
-test_expect_success 'notice empty queue' '
-	test-tool prio-queue 1 2 get get get 1 2 get get get >actual &&
-	test_cmp expect actual
-'

This too.

t/t0009-prio-queue.sh line 64

Quoted 13 lines

t/t0009-prio-queue.sh deleted +0 ~~-13~~

-cat >expect <<'EOF'
-3
-2
-6
-4
-5
-1
-8
-EOF
-test_expect_success 'stack order' '
-	test-tool prio-queue stack 8 1 5 4 6 2 3 dump >actual &&
-	test_cmp expect actual
-'

This test got truncated in your version, which is not horribly wrong, but if we claim "move t0009 to unit testing", people would expect to see a conversion faithful to the original. And with the use of result[ARRAY_SIZE(expected)], there is no reason to truncate the original test with this version, no?

Thanks.

Junio C Hamano

2024-01-17 22:16 UTC #8 lore raw

Quoted 2 lines · Junio C Hamano

I forgot to examine the contents of the tests themselves.
...

FYI: taking them all together, here is what I tentatively queued on top of what was posted as v3 before I start doing today's integration cycle.

Thanks.

----- >8 -----
Subject: [PATCH] SQUASH???

---
 t/unit-tests/t-prio-queue.c | 57 ++++++++++++++++++-------------------
 1 file changed, 28 insertions(+), 29 deletions(-)

t/unit-tests/t-prio-queue.c +28 ~~-29~~

index 0b826b463e..3014a67ac2 100644
@@ -22,44 +22,43 @@ static int show(int *v)
 static int test_prio_queue(int *input, int *result)
 {
 	struct prio_queue pq = { intcmp };
-	int i = 0;
+	int i, val;
 
-	while (*input) {
-		int *val = input++;
+	for (i = 0; (val = *input); input++) {
 		void *peek, *get;
-		switch(*val) {
-			case GET:
-				peek = prio_queue_peek(&pq);
+		switch (val) {
+		case GET:
+			peek = prio_queue_peek(&pq);
+			get = prio_queue_get(&pq);
+			if (peek != get)
+				BUG("peek and get results don't match");
+			result[i++] = show(get);
+			break;
+		case DUMP:
+			while ((peek = prio_queue_peek(&pq))) {
 				get = prio_queue_get(&pq);
 				if (peek != get)
 					BUG("peek and get results don't match");
 				result[i++] = show(get);
-				break;
-			case DUMP:
-				while ((peek = prio_queue_peek(&pq))) {
-					get = prio_queue_get(&pq);
-					if (peek != get)
-						BUG("peek and get results don't match");
-					result[i++] = show(get);
-				}
-				break;
-			case STACK:
-				pq.compare = NULL;
-				break;
-			case REVERSE:
-				prio_queue_reverse(&pq);
-				break;
-			default:
-				prio_queue_put(&pq, val);
-				break;
+			}
+			break;
+		case STACK:
+			pq.compare = NULL;
+			break;
+		case REVERSE:
+			prio_queue_reverse(&pq);
+			break;
+		default:
+			prio_queue_put(&pq, input);
+			break;
 		}
 	}
 	clear_prio_queue(&pq);
 	return 0;
 }
 
-#define BASIC_INPUT 1, 2, 3, 4, 5, 5, DUMP
-#define BASIC_EXPECTED 1, 2, 3, 4, 5, 5
+#define BASIC_INPUT 2, 6, 3, 10, 9, 5, 7, 4, 5, 8, 1, DUMP
+#define BASIC_EXPECTED 1, 2, 3, 4, 5, 5, 6, 7, 8, 9, 10
 
 #define MIXED_PUT_GET_INPUT 6, 2, 4, GET, 5, 3, GET, GET, 1, DUMP
 #define MIXED_PUT_GET_EXPECTED 2, 3, 4, 1, 5, 6

@@ -67,8 +66,8 @@ static int test_prio_queue(int *input, int *result)
 #define EMPTY_QUEUE_INPUT 1, 2, GET, GET, GET, 1, 2, GET, GET, GET
 #define EMPTY_QUEUE_EXPECTED 1, 2, MISSING, 1, 2, MISSING
 
-#define STACK_INPUT STACK, 1, 5, 4, 6, 2, 3, DUMP
-#define STACK_EXPECTED 3, 2, 6, 4, 5, 1
+#define STACK_INPUT STACK, 8, 1, 5, 4, 6, 2, 3, DUMP
+#define STACK_EXPECTED 3, 2, 6, 4, 5, 1, 8
 
 #define REVERSE_STACK_INPUT STACK, 1, 2, 3, 4, 5, 6, REVERSE, DUMP
 #define REVERSE_STACK_EXPECTED 1, 2, 3, 4, 5, 6

@@ -76,7 +75,7 @@ static int test_prio_queue(int *input, int *result)
 #define TEST_INPUT(INPUT, EXPECTED, name)			\
   static void test_##name(void)				\
 {								\
-	int input[] = {INPUT};					\
+	int input[] = {INPUT, 0};				\
 	int expected[] = {EXPECTED};				\
 	int result[ARRAY_SIZE(expected)];			\
 	test_prio_queue(input, result);				\

Signature · 1 line

2.43.0-367-g186b115d30

Jeff King

2024-01-20 02:31 UTC #9 lore raw

In reply to Chandra Pratap via GitGitGadget

t/unit-tests/t-prio-queue.c line 84

Quoted 9 lines · Chandra Pratap via GitGitGadget

t/unit-tests/t-prio-queue.c new file +9 -0

+#define TEST_INPUT(INPUT, EXPECTED, name)			\
+  static void test_##name(void)				\
+{								\
+	int input[] = {INPUT};					\
+	int expected[] = {EXPECTED};				\
+	int result[ARRAY_SIZE(expected)];			\
+	test_prio_queue(input, result);				\
+	check(!memcmp(expected, result, sizeof(expected)));	\
+}

It is somewhat unfortunate that a failing test here gives a fairly uninformative message like:

  # check "!memcmp(expected, result, sizeof(expected))" failed at t/unit-tests/t-prio-queue.c:89
  not ok 5 - prio-queue works when LIFO stack is reversed

whereas the original t0009 you get a nice diff between expected and actual output. I guess this is a place where the test framework could help us more with a specialized check_memequal() or something that showed the differing bytes on failure (of course being C, it has no type info so it wouldn't even know these are ints!).

Another solution would be to have the test function check the result as it is computed rather than storing it in an array. That would also solve another potential problem: undefined behavior if the result is not the expected size. If there is a bug that causes too much output we'd overflow our buffer. If too few, we'll end up comparing uninitialized memory (which could even accidentally have the correct values, especially if it's recycled from a previous test!). Neither of those should happen in practice, but then the whole point of this exercise is to test the code.

I admit I find myself a little skeptical in general of this whole "let's do tests in C" framework.

-Peff

Phillip Wood

2024-01-20 14:23 UTC #10 lore raw

In reply to Chandra Pratap via GitGitGadget

Quoted 8 lines · Chandra Pratap via GitGitGadget

From: Chandra Pratap <[email protected]>
t/t0009-prio-queue.sh along with t/helper/test-prio-queue.c unit tests Git's implementation of a priority queue. Migrate the test over to the new unit testing framework to simplify debugging and reduce test run-time. Refactor the required logic and add a new test case in addition to porting over the original ones in shell.

Thanks for working on this, it is good to see people exploring the unit test framework. I agree with the points that Junio and Peff have already made, I've got a couple of additional comments below.

Quoted 2 lines

[...]
+static int test_prio_queue(int *input, int *result)

This function does not need to return a value.

t/unit-tests/t-prio-queue.c line 27

Quoted 5 lines

t/unit-tests/t-prio-queue.c new file +5 -0

+{
+	struct prio_queue pq = { intcmp };
+	int i = 0;
+
+	while (*input) {

I agree with Junio that a for() loop would be better here, but I think that rather than testing for '0' we should just pass the length of the input array to this function.

t/unit-tests/t-prio-queue.c line 35

Quoted 8 lines

t/unit-tests/t-prio-queue.c new file +8 -0

+		int *val = input++;
+		void *peek, *get;
+		switch(*val) {
+			case GET:
+				peek = prio_queue_peek(&pq);
+				get = prio_queue_get(&pq);
+				if (peek != get)
+					BUG("peek and get results don't match");

If possible avoid calling BUG() in unit test code as it aborts the whole test program, not just the current test. You can use check() and return early instead

	if (!check(peek, !=, get))
		return;

Review

Quoted 1 line

(quoted diff) +1 -0
+				result[i++] = show(get);

I agree with Peff that it would be safer just to use check_int() here. If you switch to a for loop with an index you can also print the current index with

	test_msg("index %d", i);

Which will help diagnose which item in the queue is failing.

Alternatively we could grow result dynamically using ALLOC_GROW() and add a function to compare two arrays of integers. Such a function should take the two lengths, one for each array.

Best Wishes

Phillip

Chandra Pratap via GitGitGadget

author

2024-01-21 19:28 UTC #11 lore raw

PATCH v4 1/1 tests: move t0009-prio-queue.sh to the new unit testing framework

In reply to Chandra Pratap via GitGitGadget

From: Chandra Pratap <[email protected]>

Signed-off-by Chandra Pratap <[email protected]>

---
tests: move t0009-prio-queue.sh to the new unit testing framework

Thanks to Jeff, Philip and Junio for your valuable feedbacks! I have updated the patch so that the resulting tests are more verbose when they fail and lesser prone to memory related errors.

Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1642%2FChand-ra%2Fprio-queue-v4
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1642/Chand-ra/prio-queue-v4
Pull-Request: https://github.com/gitgitgadget/git/pull/1642

Range-diff vs v3:

1: 6b10028177a ! 1: e9a0dba6f47 tests: move t0009-prio-queue.sh to the new unit testing framework

     @@ t/unit-tests/t-prio-queue.c (new)
      +	return v ? *v : MISSING;
      +}
      +
     -+static int test_prio_queue(int *input, int *result)
     ++static void test_prio_queue(int *input, int *result, size_t input_size)
      +{
      +	struct prio_queue pq = { intcmp };
     -+	int i = 0;
      +
     -+	while (*input) {
     -+		int *val = input++;
     ++	for (int i = 0, j = 0; i < input_size; i++) {
      +		void *peek, *get;
     -+		switch(*val) {
     -+			case GET:
     -+				peek = prio_queue_peek(&pq);
     ++		switch(input[i]) {
     ++		case GET:
     ++			peek = prio_queue_peek(&pq);
     ++			get = prio_queue_get(&pq);
     ++			if (!check(peek == get))
     ++				return;
     ++			if(!check_int(result[j++], ==, show(get)))
     ++				test_msg("failed at result[] index %d", j-1);
     ++			break;
     ++		case DUMP:
     ++			while ((peek = prio_queue_peek(&pq))) {
      +				get = prio_queue_get(&pq);
     -+				if (peek != get)
     -+					BUG("peek and get results don't match");
     -+				result[i++] = show(get);
     -+				break;
     -+			case DUMP:
     -+				while ((peek = prio_queue_peek(&pq))) {
     -+					get = prio_queue_get(&pq);
     -+					if (peek != get)
     -+						BUG("peek and get results don't match");
     -+					result[i++] = show(get);
     -+				}
     -+				break;
     -+			case STACK:
     -+				pq.compare = NULL;
     -+				break;
     -+			case REVERSE:
     -+				prio_queue_reverse(&pq);
     -+				break;
     -+			default:
     -+				prio_queue_put(&pq, val);
     -+				break;
     ++				if (!check(peek == get))
     ++					return;
     ++				if(!check_int(result[j++], ==, show(get)))
     ++					test_msg("failed at result[] index %d", j-1);
     ++			}
     ++			break;
     ++		case STACK:
     ++			pq.compare = NULL;
     ++			break;
     ++		case REVERSE:
     ++			prio_queue_reverse(&pq);
     ++			break;
     ++		default:
     ++			prio_queue_put(&pq, &input[i]);
     ++			break;
      +		}
      +	}
      +	clear_prio_queue(&pq);
     -+	return 0;
      +}
      +
     -+#define BASIC_INPUT 1, 2, 3, 4, 5, 5, DUMP
     -+#define BASIC_EXPECTED 1, 2, 3, 4, 5, 5
     ++#define BASIC_INPUT 2, 6, 3, 10, 9, 5, 7, 4, 5, 8, 1, DUMP
     ++#define BASIC_RESULT 1, 2, 3, 4, 5, 5, 6, 7, 8, 9, 10
      +
      +#define MIXED_PUT_GET_INPUT 6, 2, 4, GET, 5, 3, GET, GET, 1, DUMP
     -+#define MIXED_PUT_GET_EXPECTED 2, 3, 4, 1, 5, 6
     ++#define MIXED_PUT_GET_RESULT 2, 3, 4, 1, 5, 6
      +
      +#define EMPTY_QUEUE_INPUT 1, 2, GET, GET, GET, 1, 2, GET, GET, GET
     -+#define EMPTY_QUEUE_EXPECTED 1, 2, MISSING, 1, 2, MISSING
     ++#define EMPTY_QUEUE_RESULT 1, 2, MISSING, 1, 2, MISSING
      +
     -+#define STACK_INPUT STACK, 1, 5, 4, 6, 2, 3, DUMP
     -+#define STACK_EXPECTED 3, 2, 6, 4, 5, 1
     ++#define STACK_INPUT STACK, 8, 1, 5, 4, 6, 2, 3, DUMP
     ++#define STACK_RESULT 3, 2, 6, 4, 5, 1, 8
      +
      +#define REVERSE_STACK_INPUT STACK, 1, 2, 3, 4, 5, 6, REVERSE, DUMP
     -+#define REVERSE_STACK_EXPECTED 1, 2, 3, 4, 5, 6
     ++#define REVERSE_STACK_RESULT 1, 2, 3, 4, 5, 6
      +
     -+#define TEST_INPUT(INPUT, EXPECTED, name)			\
     ++#define TEST_INPUT(INPUT, RESULT, name)			\
      +  static void test_##name(void)				\
      +{								\
      +	int input[] = {INPUT};					\
     -+	int expected[] = {EXPECTED};				\
     -+	int result[ARRAY_SIZE(expected)];			\
     -+	test_prio_queue(input, result);				\
     -+	check(!memcmp(expected, result, sizeof(expected)));	\
     ++	int result[] = {RESULT};				\
     ++	test_prio_queue(input, result, ARRAY_SIZE(input));	\
      +}
      +
     -+TEST_INPUT(BASIC_INPUT, BASIC_EXPECTED, basic)
     -+TEST_INPUT(MIXED_PUT_GET_INPUT, MIXED_PUT_GET_EXPECTED, mixed)
     -+TEST_INPUT(EMPTY_QUEUE_INPUT, EMPTY_QUEUE_EXPECTED, empty)
     -+TEST_INPUT(STACK_INPUT, STACK_EXPECTED, stack)
     -+TEST_INPUT(REVERSE_STACK_INPUT, REVERSE_STACK_EXPECTED, reverse)
     ++TEST_INPUT(BASIC_INPUT, BASIC_RESULT, basic)
     ++TEST_INPUT(MIXED_PUT_GET_INPUT, MIXED_PUT_GET_RESULT, mixed)
     ++TEST_INPUT(EMPTY_QUEUE_INPUT, EMPTY_QUEUE_RESULT, empty)
     ++TEST_INPUT(STACK_INPUT, STACK_RESULT, stack)
     ++TEST_INPUT(REVERSE_STACK_INPUT, REVERSE_STACK_RESULT, reverse)
      +
      +int cmd_main(int argc, const char **argv)
      +{

 Makefile                    |  2 +-
 t/helper/test-prio-queue.c  | 51 -------------------
 t/helper/test-tool.c        |  1 -
 t/helper/test-tool.h        |  1 -
 t/t0009-prio-queue.sh       | 66 -------------------------
 t/unit-tests/t-prio-queue.c | 98 +++++++++++++++++++++++++++++++++++++
 6 files changed, 99 insertions(+), 120 deletions(-)
 delete mode 100644 t/helper/test-prio-queue.c
 delete mode 100755 t/t0009-prio-queue.sh
 create mode 100644 t/unit-tests/t-prio-queue.c

Makefile +1 -1

index 312d95084c1..d5e48e656b3 100644
@@ -828,7 +828,6 @@ TEST_BUILTINS_OBJS += test-partial-clone.o
 TEST_BUILTINS_OBJS += test-path-utils.o
 TEST_BUILTINS_OBJS += test-pcre2-config.o
 TEST_BUILTINS_OBJS += test-pkt-line.o
-TEST_BUILTINS_OBJS += test-prio-queue.o
 TEST_BUILTINS_OBJS += test-proc-receive.o
 TEST_BUILTINS_OBJS += test-progress.o
 TEST_BUILTINS_OBJS += test-reach.o

@@ -1340,6 +1339,7 @@ THIRD_PARTY_SOURCES += sha1dc/%
 
 UNIT_TEST_PROGRAMS += t-basic
 UNIT_TEST_PROGRAMS += t-strbuf
+UNIT_TEST_PROGRAMS += t-prio-queue
 UNIT_TEST_PROGS = $(patsubst %,$(UNIT_TEST_BIN)/%$X,$(UNIT_TEST_PROGRAMS))
 UNIT_TEST_OBJS = $(patsubst %,$(UNIT_TEST_DIR)/%.o,$(UNIT_TEST_PROGRAMS))
 UNIT_TEST_OBJS += $(UNIT_TEST_DIR)/test-lib.o

t/helper/test-prio-queue.c deleted +0 ~~-51~~

51 lines not on this page · raw message

t/helper/test-tool.c +0 -1

index 876cd2dc313..5f591b9718f 100644
@@ -57,7 +57,6 @@ static struct test_cmd cmds[] = {
 	{ "path-utils", cmd__path_utils },
 	{ "pcre2-config", cmd__pcre2_config },
 	{ "pkt-line", cmd__pkt_line },
-	{ "prio-queue", cmd__prio_queue },
 	{ "proc-receive", cmd__proc_receive },
 	{ "progress", cmd__progress },
 	{ "reach", cmd__reach },

t/helper/test-tool.h +0 -1

index 70dd4eba119..b921138d8ec 100644
@@ -50,7 +50,6 @@ int cmd__partial_clone(int argc, const char **argv);
 int cmd__path_utils(int argc, const char **argv);
 int cmd__pcre2_config(int argc, const char **argv);
 int cmd__pkt_line(int argc, const char **argv);
-int cmd__prio_queue(int argc, const char **argv);
 int cmd__proc_receive(int argc, const char **argv);
 int cmd__progress(int argc, const char **argv);
 int cmd__reach(int argc, const char **argv);

t/t0009-prio-queue.sh deleted +0 ~~-66~~

66 lines not on this page · raw message

t/unit-tests/t-prio-queue.c new file +98 -0

98 lines not on this page · raw message

base-commit: 1a87c842ece327d03d08096395969aca5e0a6996

Signature · 1 line

gitgitgadget

Junio C Hamano

2024-01-22 19:09 UTC #12 lore raw

Quoted 24 lines

t/unit-tests/t-prio-queue.c new file +18 -0

new file mode 100644
index 00000000000..d78b002f9ea
@@ -0,0 +1,98 @@
+#include "test-lib.h"
+#include "prio-queue.h"
+
+static int intcmp(const void *va, const void *vb, void *data UNUSED)
+{
+	const int *a = va, *b = vb;
+	return *a - *b;
+}
+
+
+#define MISSING  -1
+#define DUMP	 -2
+#define STACK	 -3
+#define GET	 -4
+#define REVERSE  -5
+
+static int show(int *v)
+{

t/unit-tests/t-prio-queue.c line 28

Quoted 10 lines

t/unit-tests/t-prio-queue.c new file +10 -0

+	return v ? *v : MISSING;
+}
+
+static void test_prio_queue(int *input, int *result, size_t input_size)
+{
+	struct prio_queue pq = { intcmp };
+
+	for (int i = 0, j = 0; i < input_size; i++) {
+		void *peek, *get;
+		switch(input[i]) {

Style: in this codebase, a flow control keyword followed by a parenthesized stuff always get a single SP before the parenthesis.

		switch (input[i]) {

There are similar style violations in this patch with if().

Quoted 7 lines

t/unit-tests/t-prio-queue.c new file +7 -0

+		case GET:
+			peek = prio_queue_peek(&pq);
+			get = prio_queue_get(&pq);
+			if (!check(peek == get))
+				return;
+			if(!check_int(result[j++], ==, show(get)))
+				test_msg("failed at result[] index %d", j-1);

t/unit-tests/t-prio-queue.c line 45

Quoted 10 lines

t/unit-tests/t-prio-queue.c new file +10 -0

+			break;
+		case DUMP:
+			while ((peek = prio_queue_peek(&pq))) {
+				get = prio_queue_get(&pq);
+				if (!check(peek == get))
+					return;
+				if(!check_int(result[j++], ==, show(get)))
+					test_msg("failed at result[] index %d", j-1);
+			}
+			break;

OK. So this one checks as we go. I am not sure how easy to grok a breakage diagnosis with these giving the same message, without giving any context of the failure (e.g. when we are fed

	INPUT  = 6 2 4 GET 5 3 GET GET 1 DUMP
	EXPECT = 2 3 4 1 5 6

and for some reason if the first GET did not yield expected 2 but gave us, say, 6, we only see "left: 2, right: 6" followed by "failed at result[] index 0", and nothing else.

If it said something like "We pushed 6, 2, 4 and then did GET" to give the reader a bit more context, it would make it easier to see why we were complaining, i.e. expecting to see 2, instead getting 6. But perhaps that is too much to ask to this code?

I dunno. Those who wanted to see an easier-to-diagnose output may have better ideas.

Thanks.

Quoted 55 lines

t/unit-tests/t-prio-queue.c new file +53 -0

+		case STACK:
+			pq.compare = NULL;
+			break;
+		case REVERSE:
+			prio_queue_reverse(&pq);
+			break;
+		default:
+			prio_queue_put(&pq, &input[i]);
+			break;
+		}
+	}
+	clear_prio_queue(&pq);
+}
+
+#define BASIC_INPUT 2, 6, 3, 10, 9, 5, 7, 4, 5, 8, 1, DUMP
+#define BASIC_RESULT 1, 2, 3, 4, 5, 5, 6, 7, 8, 9, 10
+
+#define MIXED_PUT_GET_INPUT 6, 2, 4, GET, 5, 3, GET, GET, 1, DUMP
+#define MIXED_PUT_GET_RESULT 2, 3, 4, 1, 5, 6
+
+#define EMPTY_QUEUE_INPUT 1, 2, GET, GET, GET, 1, 2, GET, GET, GET
+#define EMPTY_QUEUE_RESULT 1, 2, MISSING, 1, 2, MISSING
+
+#define STACK_INPUT STACK, 8, 1, 5, 4, 6, 2, 3, DUMP
+#define STACK_RESULT 3, 2, 6, 4, 5, 1, 8
+
+#define REVERSE_STACK_INPUT STACK, 1, 2, 3, 4, 5, 6, REVERSE, DUMP
+#define REVERSE_STACK_RESULT 1, 2, 3, 4, 5, 6
+
+#define TEST_INPUT(INPUT, RESULT, name)			\
+  static void test_##name(void)				\
+{								\
+	int input[] = {INPUT};					\
+	int result[] = {RESULT};				\
+	test_prio_queue(input, result, ARRAY_SIZE(input));	\
+}
+
+TEST_INPUT(BASIC_INPUT, BASIC_RESULT, basic)
+TEST_INPUT(MIXED_PUT_GET_INPUT, MIXED_PUT_GET_RESULT, mixed)
+TEST_INPUT(EMPTY_QUEUE_INPUT, EMPTY_QUEUE_RESULT, empty)
+TEST_INPUT(STACK_INPUT, STACK_RESULT, stack)
+TEST_INPUT(REVERSE_STACK_INPUT, REVERSE_STACK_RESULT, reverse)
+
+int cmd_main(int argc, const char **argv)
+{
+	TEST(test_basic(), "prio-queue works for basic input");
+	TEST(test_mixed(), "prio-queue works for mixed put & get commands");
+	TEST(test_empty(), "prio-queue works when queue is empty");
+	TEST(test_stack(), "prio-queue works when used as a LIFO stack");
+	TEST(test_reverse(), "prio-queue works when LIFO stack is reversed");
+
+	return test_done();
+}

base-commit: 1a87c842ece327d03d08096395969aca5e0a6996

Jeff King

2024-01-22 22:42 UTC #13 lore raw

Quoted 21 lines · Junio C Hamano

t/unit-tests/t-prio-queue.c line 45
Quoted 9 lines
t/unit-tests/t-prio-queue.c new file +9 -0
+		case DUMP:
+			while ((peek = prio_queue_peek(&pq))) {
+				get = prio_queue_get(&pq);
+				if (!check(peek == get))
+					return;
+				if(!check_int(result[j++], ==, show(get)))
+					test_msg("failed at result[] index %d", j-1);
+			}
+			break;
OK. So this one checks as we go. I am not sure how easy to grok a breakage diagnosis with these giving the same message, without giving any context of the failure (e.g. when we are fed
	INPUT  = 6 2 4 GET 5 3 GET GET 1 DUMP
	EXPECT = 2 3 4 1 5 6
and for some reason if the first GET did not yield expected 2 but gave us, say, 6, we only see "left: 2, right: 6" followed by "failed at result[] index 0", and nothing else.

Quoted 7 lines

If it said something like "We pushed 6, 2, 4 and then did GET" to give the reader a bit more context, it would make it easier to see why we were complaining, i.e. expecting to see 2, instead getting 6. But perhaps that is too much to ask to this code?
I dunno. Those who wanted to see an easier-to-diagnose output may have better ideas.

I don't have any bright ideas, but here are some dumb ones.

The big issue is that storing and manipulating data in C is tricky and requires code to do correctly. And the whole idea of these tests is to avoid having a ton of special code. That's why I actually think that the existing strategy used in t0009 and elsewhere is pretty good. It pawns off output handling and such to existing programs.

But if we really want to keep it all in C, some options are:

1. We could log what is happening verbosely to stderr (or maybe stdout with a TAP "#" prefix?). That lets it go nowhere most of the time, but you can see it if you are investigating a failure (like the way our current "-v" works).

Obviously by that same argument you can fire up a debugger to look at the problem more closely when you have a failure. But failures aren't always easy to reproduce. Sometimes they're racy, sometimes CI fails but local runs don't (I've found CI's use of "-v -x" especially helpful there), etc.

2. We can rely on a dynamic-growth array of ints to store the result, and then a check_int_array() to compare/output them. That's custom code for the test harness, but in theory it's reusable across many tests.

3. In the same direction, we could simply output to a strbuf or similar, and then compare the strbufs. We could even show a diff when they are not the same. ;) That is reimplementing what scripts like t0009 are doing already, but maybe people think there is other value in shoving it all into a single C program (as I've said, I remain a bit skeptical).

-Peff

Chandra Pratap via GitGitGadget

author

2024-01-25 20:02 UTC #14 lore raw

PATCH v5 1/1 tests: move t0009-prio-queue.sh to the new unit testing framework

In reply to Chandra Pratap via GitGitGadget

From: Chandra Pratap <[email protected]>

Signed-off-by Chandra Pratap <[email protected]>

---
tests: move t0009-prio-queue.sh to the new unit testing framework

Thanks for the feedbacks! I have updated the patch so that the resulting tests show something like:

> check "result[j++] == show(get)" failed at
> unit-tests/t-prio-queue.c:60

> left: 20 right: 2

> input: push 1, push 2, get, get, get, push 1, push 2, get, get, get,

> failed at input index 8

in the case of a failing test.

Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1642%2FChand-ra%2Fprio-queue-v5
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1642/Chand-ra/prio-queue-v5
Pull-Request: https://github.com/gitgitgadget/git/pull/1642

Range-diff vs v4:

1: e9a0dba6f47 ! 1: 88e70127ad3 tests: move t0009-prio-queue.sh to the new unit testing framework

     @@ t/unit-tests/t-prio-queue.c (new)
      +	return v ? *v : MISSING;
      +}
      +
     ++static void print_input(int *input, size_t input_size)
     ++{
     ++	char buf[128];
     ++	int len = 0;
     ++	for(size_t i = 0; i < input_size; i++) {
     ++		switch (input[i]) {
     ++		case GET:
     ++			len += xsnprintf(buf+len, sizeof(buf), "get, ");
     ++			break;
     ++		case DUMP:
     ++			len += xsnprintf(buf+len, sizeof(buf), "dump");
     ++			break;
     ++		case STACK:
     ++			len += xsnprintf(buf+len, sizeof(buf), "stack, ");
     ++			break;
     ++		case REVERSE:
     ++			len += xsnprintf(buf+len, sizeof(buf), "reverse, ");
     ++			break;
     ++		default:
     ++			len += xsnprintf(buf+len, sizeof(buf), "push %d, ", input[i]);
     ++			break;
     ++		}
     ++	}
     ++	test_msg("input: %s", buf);
     ++}
     ++
      +static void test_prio_queue(int *input, int *result, size_t input_size)
      +{
      +	struct prio_queue pq = { intcmp };
      +
      +	for (int i = 0, j = 0; i < input_size; i++) {
      +		void *peek, *get;
     -+		switch(input[i]) {
     ++		switch (input[i]) {
      +		case GET:
      +			peek = prio_queue_peek(&pq);
      +			get = prio_queue_get(&pq);
      +			if (!check(peek == get))
      +				return;
     -+			if(!check_int(result[j++], ==, show(get)))
     -+				test_msg("failed at result[] index %d", j-1);
     ++			if (!check_int(result[j++], ==, show(get))) {
     ++				print_input(input, input_size);
     ++				test_msg("failed at input index %d", i);
     ++			}
      +			break;
      +		case DUMP:
      +			while ((peek = prio_queue_peek(&pq))) {
      +				get = prio_queue_get(&pq);
      +				if (!check(peek == get))
      +					return;
     -+				if(!check_int(result[j++], ==, show(get)))
     -+					test_msg("failed at result[] index %d", j-1);
     ++				if (!check_int(result[j++], ==, show(get))) {
     ++					print_input(input, input_size);
     ++					test_msg("failed at input index %d", i);
     ++				}
      +			}
      +			break;
      +		case STACK:
     @@ t/unit-tests/t-prio-queue.c (new)
      +	clear_prio_queue(&pq);
      +}
      +
     ++
      +#define BASIC_INPUT 2, 6, 3, 10, 9, 5, 7, 4, 5, 8, 1, DUMP
      +#define BASIC_RESULT 1, 2, 3, 4, 5, 5, 6, 7, 8, 9, 10
      +

 Makefile                    |   2 +-
 t/helper/test-prio-queue.c  |  51 --------------
 t/helper/test-tool.c        |   1 -
 t/helper/test-tool.h        |   1 -
 t/t0009-prio-queue.sh       |  66 ------------------
 t/unit-tests/t-prio-queue.c | 129 ++++++++++++++++++++++++++++++++++++
 6 files changed, 130 insertions(+), 120 deletions(-)
 delete mode 100644 t/helper/test-prio-queue.c
 delete mode 100755 t/t0009-prio-queue.sh
 create mode 100644 t/unit-tests/t-prio-queue.c

Makefile +1 -1

index 312d95084c1..d5e48e656b3 100644
@@ -828,7 +828,6 @@ TEST_BUILTINS_OBJS += test-partial-clone.o
 TEST_BUILTINS_OBJS += test-path-utils.o
 TEST_BUILTINS_OBJS += test-pcre2-config.o
 TEST_BUILTINS_OBJS += test-pkt-line.o
-TEST_BUILTINS_OBJS += test-prio-queue.o
 TEST_BUILTINS_OBJS += test-proc-receive.o
 TEST_BUILTINS_OBJS += test-progress.o
 TEST_BUILTINS_OBJS += test-reach.o

@@ -1340,6 +1339,7 @@ THIRD_PARTY_SOURCES += sha1dc/%
 
 UNIT_TEST_PROGRAMS += t-basic
 UNIT_TEST_PROGRAMS += t-strbuf
+UNIT_TEST_PROGRAMS += t-prio-queue
 UNIT_TEST_PROGS = $(patsubst %,$(UNIT_TEST_BIN)/%$X,$(UNIT_TEST_PROGRAMS))
 UNIT_TEST_OBJS = $(patsubst %,$(UNIT_TEST_DIR)/%.o,$(UNIT_TEST_PROGRAMS))
 UNIT_TEST_OBJS += $(UNIT_TEST_DIR)/test-lib.o

t/helper/test-prio-queue.c deleted +0 ~~-51~~

51 lines not on this page · raw message

t/helper/test-tool.c +0 -1

index 876cd2dc313..5f591b9718f 100644
@@ -57,7 +57,6 @@ static struct test_cmd cmds[] = {
 	{ "path-utils", cmd__path_utils },
 	{ "pcre2-config", cmd__pcre2_config },
 	{ "pkt-line", cmd__pkt_line },
-	{ "prio-queue", cmd__prio_queue },
 	{ "proc-receive", cmd__proc_receive },
 	{ "progress", cmd__progress },
 	{ "reach", cmd__reach },

t/helper/test-tool.h +0 -1

index 70dd4eba119..b921138d8ec 100644
@@ -50,7 +50,6 @@ int cmd__partial_clone(int argc, const char **argv);
 int cmd__path_utils(int argc, const char **argv);
 int cmd__pcre2_config(int argc, const char **argv);
 int cmd__pkt_line(int argc, const char **argv);
-int cmd__prio_queue(int argc, const char **argv);
 int cmd__proc_receive(int argc, const char **argv);
 int cmd__progress(int argc, const char **argv);
 int cmd__reach(int argc, const char **argv);

t/t0009-prio-queue.sh deleted +0 ~~-66~~

66 lines not on this page · raw message

t/unit-tests/t-prio-queue.c new file +129 -0

129 lines not on this page · raw message

base-commit: 1a87c842ece327d03d08096395969aca5e0a6996

Signature · 1 line

gitgitgadget