| Message ID | pull.1642.v3.git.1705502304219.gitgitgadget@gmail.com (mailing list archive) |
|---|---|
| State | Superseded |
| Headers | show |
| Series | [v3] tests: move t0009-prio-queue.sh to the new unit testing framework | expand |
"Chandra Pratap via GitGitGadget" <gitgitgadget@gmail.com> writes: > +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; } } > +... > + default: > + prio_queue_put(&pq, val); > + break; > + } > + } > + 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. > + int expected[] = {EXPECTED}; \ > + int result[ARRAY_SIZE(expected)]; \ These arrays are correct. > + test_prio_queue(input, result); \ > + check(!memcmp(expected, result, sizeof(expected))); \ So is this check. > +} > + > +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(); > +} Other than that, looking good. Thanks.
I forgot to examine the contents of the tests themselves. > -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 > -' 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. > -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. > -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. > -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 <gitster@pobox.com> writes: > 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(-) diff --git a/t/unit-tests/t-prio-queue.c b/t/unit-tests/t-prio-queue.c index 0b826b463e..3014a67ac2 100644 --- a/t/unit-tests/t-prio-queue.c +++ b/t/unit-tests/t-prio-queue.c @@ -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); \
On Wed, Jan 17, 2024 at 02:38:23PM +0000, Chandra Pratap via GitGitGadget wrote: > +#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
On 17/01/2024 14:38, Chandra Pratap via GitGitGadget wrote: > From: Chandra Pratap <chandrapratap3519@gmail.com> > > 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. > [...] > +static int test_prio_queue(int *input, int *result) This function does not need to return a value. > +{ > + 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. > + 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; > + 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
diff --git a/Makefile b/Makefile index 312d95084c1..d5e48e656b3 100644 --- a/Makefile +++ b/Makefile @@ -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 diff --git a/t/helper/test-prio-queue.c b/t/helper/test-prio-queue.c deleted file mode 100644 index f0bf255f5f0..00000000000 --- a/t/helper/test-prio-queue.c +++ /dev/null @@ -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; -} diff --git a/t/helper/test-tool.c b/t/helper/test-tool.c index 876cd2dc313..5f591b9718f 100644 --- a/t/helper/test-tool.c +++ b/t/helper/test-tool.c @@ -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 }, diff --git a/t/helper/test-tool.h b/t/helper/test-tool.h index 70dd4eba119..b921138d8ec 100644 --- a/t/helper/test-tool.h +++ b/t/helper/test-tool.h @@ -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); diff --git a/t/t0009-prio-queue.sh b/t/t0009-prio-queue.sh deleted file mode 100755 index eea99107a48..00000000000 --- a/t/t0009-prio-queue.sh +++ /dev/null @@ -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 diff --git a/t/unit-tests/t-prio-queue.c b/t/unit-tests/t-prio-queue.c new file mode 100644 index 00000000000..0b826b463e9 --- /dev/null +++ b/t/unit-tests/t-prio-queue.c @@ -0,0 +1,101 @@ +#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) +{ + return v ? *v : MISSING; +} + +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) { + 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 STACK: + pq.compare = NULL; + break; + case REVERSE: + prio_queue_reverse(&pq); + break; + default: + prio_queue_put(&pq, val); + 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 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, 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 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) \ +{ \ + int input[] = {INPUT}; \ + int expected[] = {EXPECTED}; \ + int result[ARRAY_SIZE(expected)]; \ + 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(); +}