t: port reftable/tree_test.c to the unit testing framework
cover t: port reftable/tree_test.c to the unit testing framework
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/tree_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.
---
CI/PR: https://github.com/gitgitgadget/git/pull/1740
Chandra Pratap (4):
reftable: remove unnecessary curly braces in
t: move reftable/tree_test.c to the unit testing
t-reftable-tree: split test_tree() into two sub-test
t-reftable-tree: add test for non-existent key
Makefile | 2 +- reftable/tree.c | 15 +++-------- reftable/tree_test.c | 60 ----------------------------------- t/helper/test-reftable.c | 1 - t/unit-tests/t-reftable-tree.c | 73 ++++++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 79 insertions(+), 72 deletions(-)
PATCH 1/4 reftable: remove unnecessary curly braces in reftable/tree.c
According to Documentation/CodingGuidelines, single-line control-flow statements must omit curly braces (except for some special cases). Make reftable/tree.c adhere to this guideline.
--- reftable/tree.c | 15 +++++---------- 1 file changed, 5 insertions(+), 10 deletions(-)
reftable/tree.c +5 -10
@@ -39,25 +39,20 @@ struct tree_node *tree_search(void *key, struct tree_node **rootp,void infix_walk (struct tree_node *t,void (*action)(void *arg,void *key),void *arg) { -if (t->left) { +if (t->left)infix_walk (t->left, action, arg); - }action (arg, t->key); -if (t->right) { +if (t->right)infix_walk (t->right, action, arg); - } }void tree_free (struct tree_node *t) { -if (!t) { +if (!t)return ; - } -if (t->left) { +if (t->left)tree_free (t->left); - } -if (t->right) { +if (t->right)tree_free (t->right); - }reftable_free (t); }
Signature · 1 line
2.45.2.404.g9eaef5822c
PATCH 2/4 t: move reftable/tree_test.c to the unit testing framework
In reply to Chandra Pratapreftable/tree_test.c exercises the functions defined in reftable/tree.{c, h}. Migrate reftable/tree_test.c to the unit testing framework. Migration involves refactoring the tests to use the unit testing framework instead of reftable's test framework.
--- Makefile | 2 +- t/helper/test-reftable.c | 1 - .../unit-tests/t-reftable-tree.c | 32 ++++++++----------- 3 files changed, 15 insertions(+), 20 deletions(-) rename reftable/tree_test.c => t/unit-tests/t-reftable-tree.c (59%)
Makefile +1 -1
@@ -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-tree UNIT_TEST_PROGRAMS += t-strbuf UNIT_TEST_PROGRAMS += t-strcmp-offset UNIT_TEST_PROGRAMS += t-strvec
@@ -2681,7 +2682,6 @@ 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_TEST_OBJS += reftable/tree_test.o TEST_OBJS := $(patsubst %$X,%.o,$(TEST_PROGRAMS)) $(patsubst %,t/helper/%,$(TEST_BUILTINS_OBJS))
t/helper/test-reftable.c +0 -1
@@ -8,7 +8,6 @@ int cmd__reftable(int argc, const char **argv)basics_test_main (argc, 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);
t/unit-tests/t-reftable-tree.c renamed from reftable/tree_test.c +14 -18
@@ -6,11 +6,8 @@ license that can be found in the LICENSE file or athttps://developers.google.com/open-source/licenses/bsd */ -#include "system.h" -#include "tree.h" - -#include "test_framework.h" -#include "reftable-tests.h" +#include "test-lib.h" +#include "reftable/tree.h" static int test_compare (const void *a,const void *b) {
@@ -24,37 +21,36 @@ struct curry {static void check_increasing (void *arg,void *key) {struct curry *c = arg; -if (c->last) { -EXPECT (test_compare (c->last, key) <0 ); - } +if (c->last) + check_int(test_compare(c->last, key), <, 0); c->last = key; }static void test_tree (void ) {struct tree_node *root =NULL ; +void *values[11 ] = {0 }; +struct tree_node *nodes[11 ] = {0 }; +size_t i =1 ; +struct curry c = {0 }; -void *values[11 ] = {NULL }; -struct tree_node *nodes[11 ] = {NULL }; -int i =1 ; -struct curry c = {NULL };do { nodes[i] =tree_search (values + i, &root, &test_compare,1 ); i = (i *7 ) %11 ; }while (i !=1 );for (i =1 ; i <ARRAY_SIZE (nodes); i++) { -EXPECT (values + i == nodes[i]->key); -EXPECT (nodes[i] == -tree_search (values + i, &root, &test_compare,0 )); +check_pointer_eq (values + i, nodes[i]->key); +check_pointer_eq (nodes[i],tree_search (values + i, &root, &test_compare,0 )); }infix_walk (root, check_increasing, &c);tree_free (root); } -int tree_test_main (int argc,const char *argv[]) +int cmd_main (int argc,const char *argv[]) { -RUN_TEST (test_tree); -return 0 ; +TEST (test_tree (),"tree_search and infix_walk work" ); + +return test_done (); }
Signature · 1 line
2.45.2.404.g9eaef5822c
PATCH 3/4 t-reftable-tree: split test_tree() into two sub-test functions
In reply to Chandra PratapIn the current testing setup, tests for both tree_search() and infix_walk() defined by reftable/tree.{c, h} are performed by a single test function, test_tree(). Split tree_test() into test_tree_search() and test_infix_walk() responsible for independently testing tree_search() and infix_walk() respectively. This improves the overall readability of the test file as well as simplifies debugging.
--- t/unit-tests/t-reftable-tree.c | 22 +++++++++++++++++++--- 1 file changed, 19 insertions(+), 3 deletions(-)
t/unit-tests/t-reftable-tree.c +19 -3
@@ -26,7 +26,7 @@ static void check_increasing(void *arg, void *key) c->last = key; } -static void test_tree (void ) +static void test_tree_search (void ) {struct tree_node *root =NULL ;void *values[11 ] = {0 };
@@ -44,13 +44,29 @@ static void test_tree(void)check_pointer_eq (nodes[i],tree_search (values + i, &root, &test_compare,0 )); } -infix_walk (root, check_increasing, &c); +tree_free (root); +} + +static void test_infix_walk (void ) +{ +struct tree_node *root =NULL ; +void *values[13 ] = {0 }; +struct curry c = {0 }; +size_t i =1 ; + +do { +tree_search (values + i, &root, &test_compare,1 ); + i = (i *5 ) %13 ; + }while (i !=1 ); + +infix_walk (root, &check_increasing, &c);tree_free (root); }int cmd_main (int argc,const char *argv[]) { -TEST (test_tree (),"tree_search and infix_walk work" ); +TEST (test_tree_search (),"tree_search works" ); +TEST (test_infix_walk (),"infix_walk works" );return test_done (); }
Signature · 1 line
2.45.2.404.g9eaef5822c
Re: [PATCH 3/4] t-reftable-tree: split test_tree() into two sub-test functions
t/unit-tests/t-reftable-tree.c static void test_tree(void) · line 53
Quoted 12 lines · Chandra Pratap
t/unit-tests/t-reftable-tree.c +7
-1@@ -44,13 +44,29 @@ static void test_tree(void)check_pointer_eq (nodes[i],tree_search (values + i, &root, &test_compare,0 )); } -infix_walk (root, check_increasing, &c); +tree_free (root); +} + +static void test_infix_walk (void ) +{ +struct tree_node *root =NULL ; +void *values[13 ] = {0 };
Is there a reason why we have 13 values here while we had 11 values in the test this was split out from?
t/unit-tests/t-reftable-tree.c static void test_tree(void) · line 60
Quoted 7 lines
t/unit-tests/t-reftable-tree.c +7
-0+struct curry c = {0 }; +size_t i =1 ; + +do { +tree_search (values + i, &root, &test_compare,1 ); + i = (i *5 ) %13 ; + }while (i !=1 );
It's completely non-obvious that tree_search() ends up _inserting_ nodes into the tree when the entry we're searching for wasn't found (and if the last parameter is 1. I feel like this interface could really use a complete makeover and split up its concerns. In any case, that does not need to happen as part of this patch seriesr
What I think would help though is if the commit message itself mentioned this unorthodox way of inserting values into the tree.
t/unit-tests/t-reftable-tree.c static void test_tree(void) · line 62
Quoted 1 line
t/unit-tests/t-reftable-tree.c +1
-0+infix_walk (root, &check_increasing, &c);
Not a fault of this commit, but this test certainly isn't great. It would succeed even if infix_walk() didn't do anything as we do not verify at all whether all nodes have been traversed (and traversed once, exactly).
Patrick
Re: [PATCH 3/4] t-reftable-tree: split test_tree() into two sub-test functions
Quoted 6 lines · Patrick Steinhardt
Quoted 4 lines · Chandra Pratap
t/unit-tests/t-reftable-tree.c +0
-0@@ -44,13 +44,29 @@ static void test_tree(void)check_pointer_eq (nodes[i],tree_search (values + i, &root, &test_compare,0 )); }
Quoted 11 lines
t/unit-tests/t-reftable-tree.c static void test_tree(void) · line 53
Quoted 8 lines
t/unit-tests/t-reftable-tree.c +7
-1-infix_walk (root, check_increasing, &c); +tree_free (root); +} + +static void test_infix_walk (void ) +{ +struct tree_node *root =NULL ; +void *values[13 ] = {0 };Is there a reason why we have 13 values here while we had 11 values in the test this was split out from?
I did that to introduce some variety between the test cases, but now that you mention it, this change doesn't go well with the objective of this patch.
Quoted 8 lines
t/unit-tests/t-reftable-tree.c static void test_tree(void) · line 60
Quoted 7 lines
t/unit-tests/t-reftable-tree.c +7
-0+struct curry c = {0 }; +size_t i =1 ; + +do { +tree_search (values + i, &root, &test_compare,1 ); + i = (i *5 ) %13 ; + }while (i !=1 );
Quoted 5 lines
It's completely non-obvious that
tree_search()ends up _inserting_ nodes into the tree when the entry we're searching for wasn't found (and if the last parameter is1. I feel like this interface could really use a complete makeover and split up its concerns. In any case, that does not need to happen as part of this patch seriesr
I don't really mind it because all tree operations are only used in reftable/writer.c and only in a couple of places, so it would make sense for the original authors to focus their efforts on other parts of the codebase. Still, I do agree that the readability takes a hit 'cause of that.
Quoted 2 lines
What I think would help though is if the commit message itself mentioned this unorthodox way of inserting values into the tree.
Sure thing.
Quoted 6 lines
t/unit-tests/t-reftable-tree.c static void test_tree(void) · line 62
Quoted 1 line
t/unit-tests/t-reftable-tree.c +1
-0+infix_walk (root, &check_increasing, &c);Not a fault of this commit, but this test certainly isn't great. It would succeed even if
infix_walk()didn't do anything as we do not verify at all whether all nodes have been traversed (and traversed once, exactly).
I'll try to modify the test to check for these properties of an infix walk as well.
PATCH 4/4 t-reftable-tree: add test for non-existent key
In reply to Chandra PratapIn the current testing setup for tree_search(), the case for non-existent key is not exercised. Improve this by adding a test-case for the same.
--- t/unit-tests/t-reftable-tree.c | 1 + 1 file changed, 1 insertion(+)
t/unit-tests/t-reftable-tree.c +1 -0
@@ -44,6 +44,7 @@ static void test_tree_search(void)check_pointer_eq (nodes[i],tree_search (values + i, &root, &test_compare,0 )); } +check (!tree_search (values, &root, &test_compare,0 ));tree_free (root); }
Signature · 1 line
2.45.2.404.g9eaef5822c
v2 cover t: port reftable/tree_test.c to the unit testing framework
In reply to Chandra PratapIn 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/tree_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.
---
Changes in v2:
- Add more context in the commit message of the third patch
- Add an improvement patch for test_infix_walk()
- Small refactor changes
CI/PR: https://github.com/gitgitgadget/git/pull/1740
Chandra Pratap(5):
reftable: remove unnecessary curly braces in
t: move reftable/tree_test.c to the unit testing
t-reftable-tree: split test_tree() into two sub-test
t-reftable-tree: add test for non-existent key
t-reftable-tree: improve the test for infix_walk()
Makefile | 2 +- reftable/tree.c | 15 +++-------- reftable/tree_test.c | 60 ------------------------------- t/helper/test-reftable.c | 1 - t/unit-tests/t-reftable-tree.c | 76 ++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 82 insertions(+), 72 deletions(-)
Range-diff against v1:
1: 161d8892d6 ! 1: 542e497334 t-reftable-tree: split test_tree() into two sub-test functions
@@ Commit message
This improves the overall readability of the test file as well as
simplifies debugging.
+ Note that the last parameter in the tree_search() functiom is
+ 'int insert' which when set, inserts the key if it is not found
+ in the tree. Otherwise, the function returns NULL for such cases.
+
Mentored-by: Patrick Steinhardt <[email protected]>
Mentored-by: Christian Couder <[email protected]>
Signed-off-by: Chandra Pratap <[email protected]>
@@ t/unit-tests/t-reftable-tree.c: static void check_increasing(void *arg, void *ke
{
struct tree_node *root = NULL;
void *values[11] = { 0 };
+ struct tree_node *nodes[11] = { 0 };
+ size_t i = 1;
+- struct curry c = { 0 };
+
+ do {
+ nodes[i] = tree_search(values + i, &root, &test_compare, 1);
@@ t/unit-tests/t-reftable-tree.c: static void test_tree(void)
check_pointer_eq(nodes[i], tree_search(values + i, &root, &test_compare, 0));
}
@@ t/unit-tests/t-reftable-tree.c: static void test_tree(void)
+static void test_infix_walk(void)
+{
+ struct tree_node *root = NULL;
-+ void *values[13] = { 0 };
++ void *values[11] = { 0 };
+ struct curry c = { 0 };
+ size_t i = 1;
+
+ do {
+ tree_search(values + i, &root, &test_compare, 1);
-+ i = (i * 5) % 13;
++ i = (i * 7) % 11;
+ } while (i != 1);
+
+ infix_walk(root, &check_increasing, &c);
2: d649c4a193 = 2: c976a37cbc t-reftable-tree: add test for non-existent key
-: ---------- > 3: 3010c8f01a t-reftable-tree: improve the test for infix_walk()PATCH v2 1/5 reftable: remove unnecessary curly braces in reftable/tree.c
According to Documentation/CodingGuidelines, single-line control-flow statements must omit curly braces (except for some special cases). Make reftable/tree.c adhere to this guideline.
--- reftable/tree.c | 15 +++++---------- 1 file changed, 5 insertions(+), 10 deletions(-)
reftable/tree.c +5 -10
@@ -39,25 +39,20 @@ struct tree_node *tree_search(void *key, struct tree_node **rootp,void infix_walk (struct tree_node *t,void (*action)(void *arg,void *key),void *arg) { -if (t->left) { +if (t->left)infix_walk (t->left, action, arg); - }action (arg, t->key); -if (t->right) { +if (t->right)infix_walk (t->right, action, arg); - } }void tree_free (struct tree_node *t) { -if (!t) { +if (!t)return ; - } -if (t->left) { +if (t->left)tree_free (t->left); - } -if (t->right) { +if (t->right)tree_free (t->right); - }reftable_free (t); }
Signature · 1 line
2.45.2.404.g9eaef5822c
PATCH v2 2/5 t: move reftable/tree_test.c to the unit testing framework
In reply to Chandra Pratapreftable/tree_test.c exercises the functions defined in reftable/tree.{c, h}. Migrate reftable/tree_test.c to the unit testing framework. Migration involves refactoring the tests to use the unit testing framework instead of reftable's test framework.
--- Makefile | 2 +- t/helper/test-reftable.c | 1 - .../unit-tests/t-reftable-tree.c | 32 ++++++++----------- 3 files changed, 15 insertions(+), 20 deletions(-) rename reftable/tree_test.c => t/unit-tests/t-reftable-tree.c (59%)
Makefile +1 -1
@@ -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-tree UNIT_TEST_PROGRAMS += t-strbuf UNIT_TEST_PROGRAMS += t-strcmp-offset UNIT_TEST_PROGRAMS += t-strvec
@@ -2681,7 +2682,6 @@ 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_TEST_OBJS += reftable/tree_test.o TEST_OBJS := $(patsubst %$X,%.o,$(TEST_PROGRAMS)) $(patsubst %,t/helper/%,$(TEST_BUILTINS_OBJS))
t/helper/test-reftable.c +0 -1
@@ -8,7 +8,6 @@ int cmd__reftable(int argc, const char **argv)basics_test_main (argc, 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);
t/unit-tests/t-reftable-tree.c renamed from reftable/tree_test.c +14 -18
@@ -6,11 +6,8 @@ license that can be found in the LICENSE file or athttps://developers.google.com/open-source/licenses/bsd */ -#include "system.h" -#include "tree.h" - -#include "test_framework.h" -#include "reftable-tests.h" +#include "test-lib.h" +#include "reftable/tree.h" static int test_compare (const void *a,const void *b) {
@@ -24,37 +21,36 @@ struct curry {static void check_increasing (void *arg,void *key) {struct curry *c = arg; -if (c->last) { -EXPECT (test_compare (c->last, key) <0 ); - } +if (c->last) + check_int(test_compare(c->last, key), <, 0); c->last = key; }static void test_tree (void ) {struct tree_node *root =NULL ; +void *values[11 ] = {0 }; +struct tree_node *nodes[11 ] = {0 }; +size_t i =1 ; +struct curry c = {0 }; -void *values[11 ] = {NULL }; -struct tree_node *nodes[11 ] = {NULL }; -int i =1 ; -struct curry c = {NULL };do { nodes[i] =tree_search (values + i, &root, &test_compare,1 ); i = (i *7 ) %11 ; }while (i !=1 );for (i =1 ; i <ARRAY_SIZE (nodes); i++) { -EXPECT (values + i == nodes[i]->key); -EXPECT (nodes[i] == -tree_search (values + i, &root, &test_compare,0 )); +check_pointer_eq (values + i, nodes[i]->key); +check_pointer_eq (nodes[i],tree_search (values + i, &root, &test_compare,0 )); }infix_walk (root, check_increasing, &c);tree_free (root); } -int tree_test_main (int argc,const char *argv[]) +int cmd_main (int argc,const char *argv[]) { -RUN_TEST (test_tree); -return 0 ; +TEST (test_tree (),"tree_search and infix_walk work" ); + +return test_done (); }
Signature · 1 line
2.45.2.404.g9eaef5822c
PATCH v2 3/5 t-reftable-tree: split test_tree() into two sub-test functions
In reply to Chandra PratapIn the current testing setup, tests for both tree_search() and infix_walk() defined by reftable/tree.{c, h} are performed by a single test function, test_tree(). Split tree_test() into test_tree_search() and test_infix_walk() responsible for independently testing tree_search() and infix_walk() respectively. This improves the overall readability of the test file as well as simplifies debugging.
Note that the last parameter in the tree_search() functiom is 'int insert' which when set, inserts the key if it is not found in the tree. Otherwise, the function returns NULL for such cases.
--- t/unit-tests/t-reftable-tree.c | 23 +++++++++++++++++++---- 1 file changed, 19 insertions(+), 4 deletions(-)
t/unit-tests/t-reftable-tree.c +19 -4
@@ -26,13 +26,12 @@ static void check_increasing(void *arg, void *key) c->last = key; } -static void test_tree (void ) +static void test_tree_search (void ) {struct tree_node *root =NULL ;void *values[11 ] = {0 };struct tree_node *nodes[11 ] = {0 };size_t i =1 ; -struct curry c = {0 }; do { nodes[i] = tree_search(values + i, &root, &test_compare, 1);
@@ -44,13 +43,29 @@ static void test_tree(void)check_pointer_eq (nodes[i],tree_search (values + i, &root, &test_compare,0 )); } -infix_walk (root, check_increasing, &c); +tree_free (root); +} + +static void test_infix_walk (void ) +{ +struct tree_node *root =NULL ; +void *values[11 ] = {0 }; +struct curry c = {0 }; +size_t i =1 ; + +do { +tree_search (values + i, &root, &test_compare,1 ); + i = (i *7 ) %11 ; + }while (i !=1 ); + +infix_walk (root, &check_increasing, &c);tree_free (root); }int cmd_main (int argc,const char *argv[]) { -TEST (test_tree (),"tree_search and infix_walk work" ); +TEST (test_tree_search (),"tree_search works" ); +TEST (test_infix_walk (),"infix_walk works" );return test_done (); }
Signature · 1 line
2.45.2.404.g9eaef5822c
PATCH v2 4/5 t-reftable-tree: add test for non-existent key
In reply to Chandra PratapIn the current testing setup for tree_search(), the case for non-existent key is not exercised. Improve this by adding a test-case for the same.
--- t/unit-tests/t-reftable-tree.c | 1 + 1 file changed, 1 insertion(+)
t/unit-tests/t-reftable-tree.c +1 -0
@@ -43,6 +43,7 @@ static void test_tree_search(void)check_pointer_eq (nodes[i],tree_search (values + i, &root, &test_compare,0 )); } +check (!tree_search (values, &root, &test_compare,0 ));tree_free (root); }
Signature · 1 line
2.45.2.404.g9eaef5822c
PATCH v2 5/5 t-reftable-tree: improve the test for infix_walk()
In reply to Chandra PratapIn the current testing setup for infix_walk(), the following properties of an infix traversal of a tree remain untested:
- every node of the tree must be visited
- every node must be visited exactly only
and only the property 'traversal in increasing order' is tested. Modify test_infix_walk() to check for all the properties above.
This can be achieved by storing the nodes' keys linearly, in a nullified buffer, as we visit them and then checking the input keys against this buffer in increasing order. By checking that the element just after the last input key is 'NULL' in the output buffer, we ensure that every node is traversed exactly once.
--- t/unit-tests/t-reftable-tree.c | 16 ++++++++++------ 1 file changed, 10 insertions(+), 6 deletions(-)
t/unit-tests/t-reftable-tree.c +10 -6
@@ -15,15 +15,14 @@ static int test_compare(const void *a, const void *b) }struct curry { -void *last; +void **arr; +size_t i; }; -static void check_increasing (void *arg,void *key) +static void store (void *arg,void *key) {struct curry *c = arg; -if (c->last) - check_int(test_compare(c->last, key), <, 0); - c->last = key; + c->arr[c->i++] = key; }static void test_tree_search (void )
@@ -51,6 +50,7 @@ static void test_infix_walk(void) {struct tree_node *root =NULL ;void *values[11 ] = {0 }; +void *out[20 ] = {0 };struct curry c = {0 };size_t i =1 ;
@@ -59,7 +59,11 @@ static void test_infix_walk(void) i = (i *7 ) %11 ; }while (i !=1 ); -infix_walk (root, &check_increasing, &c); + c.arr = (void **) &out; +infix_walk (root, &store, &c); +for (i =1 ; i <ARRAY_SIZE (values); i++) +check_pointer_eq (values + i, out[i -1 ]); +check (!out[i]);tree_free (root); }
Signature · 1 line
2.45.2.404.g9eaef5822c
Re: [PATCH v2 5/5] t-reftable-tree: improve the test for infix_walk()
Quoted 4 lines · Chandra Pratap
In the current testing setup for
infix_walk(), the following properties of an infix traversal of a tree remain untested:
- every node of the tree must be visited
- every node must be visited exactly only
s/only/once
Quoted 1 line
and only the property 'traversal in increasing order' is tested.
Nit: this reads a bit awkward. How about "In fact, we only verify that the traversal happens in increasing order."
t/unit-tests/t-reftable-tree.c static void test_infix_walk(void) · line 53
Quoted 5 lines
t/unit-tests/t-reftable-tree.c +1
-0@@ -51,6 +50,7 @@ static void test_infix_walk(void) {struct tree_node *root =NULL ;void *values[11 ] = {0 }; +void *out[20 ] = {0 };
From the test below it looks like we only expect 11 values to be added to out. Why does this array have length 20?
We could of course also use something like ALLOC_GROW() to grow the array dynamically. But that'd likely be overkill.
t/unit-tests/t-reftable-tree.c static void test_infix_walk(void) · line 62
Quoted 9 lines
t/unit-tests/t-reftable-tree.c +1
-1struct curry c = {0 };size_t i =1 ;@@ -59,7 +59,11 @@ static void test_infix_walk(void) i = (i *7 ) %11 ; }while (i !=1 ); -infix_walk (root, &check_increasing, &c); + c.arr = (void **) &out;
We can initialize this variable directly when declaring c:
struct curry c = {
.arr = &out;
};Also, is the cast necessary? This is the only site where we use struct curry if I'm not mistaken, so I'd expect that the type of arr should match our expectations.
t/unit-tests/t-reftable-tree.c static void test_infix_walk(void) · line 65
Quoted 3 lines
t/unit-tests/t-reftable-tree.c +3
-0+infix_walk (root, &store, &c); +for (i =1 ; i <ARRAY_SIZE (values); i++) +check_pointer_eq (values + i, out[i -1 ]);
Let's also verify that c.len matches the expected number of nodes visited.
Patrick
Quoted 3 lines
t/unit-tests/t-reftable-tree.c +1
-0+check (!out[i]);tree_free (root); }
Re: [PATCH v2 5/5] t-reftable-tree: improve the test for infix_walk()
Quoted 14 lines · Patrick Steinhardt
Quoted 4 lines · Chandra Pratap
In the current testing setup for
infix_walk(), the following properties of an infix traversal of a tree remain untested:
- every node of the tree must be visited
- every node must be visited exactly onlys/only/once
Quoted 1 line
and only the property 'traversal in increasing order' is tested.
Nit: this reads a bit awkward. How about "In fact, we only verify that the traversal happens in increasing order."
Quoted 8 lines
t/unit-tests/t-reftable-tree.c static void test_infix_walk(void) · line 53
Quoted 5 lines
t/unit-tests/t-reftable-tree.c +1
-0@@ -51,6 +50,7 @@ static void test_infix_walk(void) {struct tree_node *root =NULL ;void *values[11 ] = {0 }; +void *out[20 ] = {0 };From the test below it looks like we only expect 11 values to be added to
out. Why does this array have length 20?
That's an error. I'll correct it in the next iteration.
Quoted 10 lines
We could of course also use something like
ALLOC_GROW()to grow the array dynamically. But that'd likely be overkill.Quoted 7 lines
t/unit-tests/t-reftable-tree.c +0
-0struct curry c = {0 };size_t i =1 ;@@ -59,7 +59,11 @@ static void test_infix_walk(void) i = (i *7 ) %11 ; }while (i !=1 );
Quoted 8 lines
t/unit-tests/t-reftable-tree.c static void test_infix_walk(void) · line 62
Quoted 2 lines
t/unit-tests/t-reftable-tree.c +1
-1-infix_walk (root, &check_increasing, &c); + c.arr = (void **) &out;We can initialize this variable directly when declaring
c:struct curry c = { .arr = &out; };
Right, this seems more concise.
Quoted 3 lines
Also, is the cast necessary? This is the only site where we use
struct curryif I'm not mistaken, so I'd expect that the type ofarrshould match our expectations.
Trying to do this without a cast produces the following compilation error for me:
initialization of ‘void **’ from incompatible pointer type ‘void * (*)[11]’
Quoted 6 lines
t/unit-tests/t-reftable-tree.c static void test_infix_walk(void) · line 65
Quoted 3 lines
t/unit-tests/t-reftable-tree.c +3
-0+infix_walk (root, &store, &c); +for (i =1 ; i <ARRAY_SIZE (values); i++) +check_pointer_eq (values + i, out[i -1 ]);Let's also verify that
c.lenmatches the expected number of nodes visited.
Sure.
v3 cover t: port reftable/tree_test.c to the unit testing framework
In reply to Chandra PratapIn 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/tree_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.
---
Changes in v3:
- Fix a typo in the commit message of the fifth patch
- Add a check for number of input & output elements in the fifth patch
- Small refactor changes
CI/PR: https://github.com/gitgitgadget/git/pull/1740
Chandra Pratap(5):
reftable: remove unnecessary curly braces in
t: move reftable/tree_test.c to the unit testing
t-reftable-tree: split test_tree() into two sub-test
t-reftable-tree: add test for non-existent key
t-reftable-tree: improve the test for infix_walk()
Makefile | 2 +- reftable/tree.c | 15 +++-------- reftable/tree_test.c | 60 ------------------------------- t/helper/test-reftable.c | 1 - t/unit-tests/t-reftable-tree.c | 76 ++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 86 insertions(+), 72 deletions(-)
Range-diff against v2:
1: 3010c8f01a ! 1: 44800ad205 t-reftable-tree: improve the test for infix_walk()
@@ Commit message
In the current testing setup for infix_walk(), the following
properties of an infix traversal of a tree remain untested:
- every node of the tree must be visited
- - every node must be visited exactly only
- and only the property 'traversal in increasing order' is tested.
+ - every node must be visited exactly once
+ In fact, only the property 'traversal in increasing order' is tested.
Modify test_infix_walk() to check for all the properties above.
This can be achieved by storing the nodes' keys linearly, in a nullified
@@ t/unit-tests/t-reftable-tree.c: static int test_compare(const void *a, const voi
struct curry {
- void *last;
+ void **arr;
-+ size_t i;
++ size_t len;
};
-static void check_increasing(void *arg, void *key)
@@ t/unit-tests/t-reftable-tree.c: static int test_compare(const void *a, const voi
- if (c->last)
- check_int(test_compare(c->last, key), <, 0);
- c->last = key;
-+ c->arr[c->i++] = key;
++ c->arr[c->len++] = key;
}
static void test_tree_search(void)
@@ t/unit-tests/t-reftable-tree.c: static void test_infix_walk(void)
{
struct tree_node *root = NULL;
void *values[11] = { 0 };
-+ void *out[20] = { 0 };
- struct curry c = { 0 };
+- struct curry c = { 0 };
++ void *out[11] = { 0 };
++ struct curry c = {
++ .arr = (void **) &out,
++ };
size_t i = 1;
++ size_t count = 0;
-@@ t/unit-tests/t-reftable-tree.c: static void test_infix_walk(void)
+ do {
+ tree_search(values + i, &root, &test_compare, 1);
i = (i * 7) % 11;
++ count++;
} while (i != 1);
- infix_walk(root, &check_increasing, &c);
-+ c.arr = (void **) &out;
+ infix_walk(root, &store, &c);
+ for (i = 1; i < ARRAY_SIZE(values); i++)
+ check_pointer_eq(values + i, out[i - 1]);
-+ check(!out[i]);
++ check(!out[i - 1]);
++ check_int(c.len, ==, count);
tree_free(root);
}PATCH v3 1/5 reftable: remove unnecessary curly braces in reftable/tree.c
According to Documentation/CodingGuidelines, single-line control-flow statements must omit curly braces (except for some special cases). Make reftable/tree.c adhere to this guideline.
--- reftable/tree.c | 15 +++++---------- 1 file changed, 5 insertions(+), 10 deletions(-)
reftable/tree.c +5 -10
@@ -39,25 +39,20 @@ struct tree_node *tree_search(void *key, struct tree_node **rootp,void infix_walk (struct tree_node *t,void (*action)(void *arg,void *key),void *arg) { -if (t->left) { +if (t->left)infix_walk (t->left, action, arg); - }action (arg, t->key); -if (t->right) { +if (t->right)infix_walk (t->right, action, arg); - } }void tree_free (struct tree_node *t) { -if (!t) { +if (!t)return ; - } -if (t->left) { +if (t->left)tree_free (t->left); - } -if (t->right) { +if (t->right)tree_free (t->right); - }reftable_free (t); }
Signature · 1 line
2.45.2.404.g9eaef5822c
PATCH v3 2/5 t: move reftable/tree_test.c to the unit testing framework
In reply to Chandra Pratapreftable/tree_test.c exercises the functions defined in reftable/tree.{c, h}. Migrate reftable/tree_test.c to the unit testing framework. Migration involves refactoring the tests to use the unit testing framework instead of reftable's test framework.
--- Makefile | 2 +- t/helper/test-reftable.c | 1 - .../unit-tests/t-reftable-tree.c | 32 ++++++++----------- 3 files changed, 15 insertions(+), 20 deletions(-) rename reftable/tree_test.c => t/unit-tests/t-reftable-tree.c (59%)
Makefile +1 -1
@@ -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-tree UNIT_TEST_PROGRAMS += t-strbuf UNIT_TEST_PROGRAMS += t-strcmp-offset UNIT_TEST_PROGRAMS += t-strvec
@@ -2681,7 +2682,6 @@ 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_TEST_OBJS += reftable/tree_test.o TEST_OBJS := $(patsubst %$X,%.o,$(TEST_PROGRAMS)) $(patsubst %,t/helper/%,$(TEST_BUILTINS_OBJS))
t/helper/test-reftable.c +0 -1
@@ -8,7 +8,6 @@ int cmd__reftable(int argc, const char **argv)basics_test_main (argc, 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);
t/unit-tests/t-reftable-tree.c renamed from reftable/tree_test.c +14 -18
@@ -6,11 +6,8 @@ license that can be found in the LICENSE file or athttps://developers.google.com/open-source/licenses/bsd */ -#include "system.h" -#include "tree.h" - -#include "test_framework.h" -#include "reftable-tests.h" +#include "test-lib.h" +#include "reftable/tree.h" static int test_compare (const void *a,const void *b) {
@@ -24,37 +21,36 @@ struct curry {static void check_increasing (void *arg,void *key) {struct curry *c = arg; -if (c->last) { -EXPECT (test_compare (c->last, key) <0 ); - } +if (c->last) + check_int(test_compare(c->last, key), <, 0); c->last = key; }static void test_tree (void ) {struct tree_node *root =NULL ; +void *values[11 ] = {0 }; +struct tree_node *nodes[11 ] = {0 }; +size_t i =1 ; +struct curry c = {0 }; -void *values[11 ] = {NULL }; -struct tree_node *nodes[11 ] = {NULL }; -int i =1 ; -struct curry c = {NULL };do { nodes[i] =tree_search (values + i, &root, &test_compare,1 ); i = (i *7 ) %11 ; }while (i !=1 );for (i =1 ; i <ARRAY_SIZE (nodes); i++) { -EXPECT (values + i == nodes[i]->key); -EXPECT (nodes[i] == -tree_search (values + i, &root, &test_compare,0 )); +check_pointer_eq (values + i, nodes[i]->key); +check_pointer_eq (nodes[i],tree_search (values + i, &root, &test_compare,0 )); }infix_walk (root, check_increasing, &c);tree_free (root); } -int tree_test_main (int argc,const char *argv[]) +int cmd_main (int argc,const char *argv[]) { -RUN_TEST (test_tree); -return 0 ; +TEST (test_tree (),"tree_search and infix_walk work" ); + +return test_done (); }
Signature · 1 line
2.45.2.404.g9eaef5822c
PATCH v3 3/5 t-reftable-tree: split test_tree() into two sub-test functions
In reply to Chandra PratapIn the current testing setup, tests for both tree_search() and infix_walk() defined by reftable/tree.{c, h} are performed by a single test function, test_tree(). Split tree_test() into test_tree_search() and test_infix_walk() responsible for independently testing tree_search() and infix_walk() respectively. This improves the overall readability of the test file as well as simplifies debugging.
Note that the last parameter in the tree_search() functiom is 'int insert' which when set, inserts the key if it is not found in the tree. Otherwise, the function returns NULL for such cases.
--- t/unit-tests/t-reftable-tree.c | 23 +++++++++++++++++++---- 1 file changed, 19 insertions(+), 4 deletions(-)
t/unit-tests/t-reftable-tree.c +19 -4
@@ -26,13 +26,12 @@ static void check_increasing(void *arg, void *key) c->last = key; } -static void test_tree (void ) +static void test_tree_search (void ) {struct tree_node *root =NULL ;void *values[11 ] = {0 };struct tree_node *nodes[11 ] = {0 };size_t i =1 ; -struct curry c = {0 }; do { nodes[i] = tree_search(values + i, &root, &test_compare, 1);
@@ -44,13 +43,29 @@ static void test_tree(void)check_pointer_eq (nodes[i],tree_search (values + i, &root, &test_compare,0 )); } -infix_walk (root, check_increasing, &c); +tree_free (root); +} + +static void test_infix_walk (void ) +{ +struct tree_node *root =NULL ; +void *values[11 ] = {0 }; +struct curry c = {0 }; +size_t i =1 ; + +do { +tree_search (values + i, &root, &test_compare,1 ); + i = (i *7 ) %11 ; + }while (i !=1 ); + +infix_walk (root, &check_increasing, &c);tree_free (root); }int cmd_main (int argc,const char *argv[]) { -TEST (test_tree (),"tree_search and infix_walk work" ); +TEST (test_tree_search (),"tree_search works" ); +TEST (test_infix_walk (),"infix_walk works" );return test_done (); }
Signature · 1 line
2.45.2.404.g9eaef5822c
PATCH v3 4/5 t-reftable-tree: add test for non-existent key
In reply to Chandra PratapIn the current testing setup for tree_search(), the case for non-existent key is not exercised. Improve this by adding a test-case for the same.
--- t/unit-tests/t-reftable-tree.c | 1 + 1 file changed, 1 insertion(+)
t/unit-tests/t-reftable-tree.c +1 -0
@@ -43,6 +43,7 @@ static void test_tree_search(void)check_pointer_eq (nodes[i],tree_search (values + i, &root, &test_compare,0 )); } +check (!tree_search (values, &root, &test_compare,0 ));tree_free (root); }
Signature · 1 line
2.45.2.404.g9eaef5822c
PATCH v3 5/5 t-reftable-tree: improve the test for infix_walk()
In reply to Chandra PratapIn the current testing setup for infix_walk(), the following properties of an infix traversal of a tree remain untested:
- every node of the tree must be visited
- every node must be visited exactly once
In fact, only the property 'traversal in increasing order' is tested. Modify test_infix_walk() to check for all the properties above.
This can be achieved by storing the nodes' keys linearly, in a nullified buffer, as we visit them and then checking the input keys against this buffer in increasing order. By checking that the element just after the last input key is 'NULL' in the output buffer, we ensure that every node is traversed exactly once.
--- t/unit-tests/t-reftable-tree.c | 22 +++++++++++++++------- 1 file changed, 15 insertions(+), 7 deletions(-)
t/unit-tests/t-reftable-tree.c +15 -7
@@ -15,15 +15,14 @@ static int test_compare(const void *a, const void *b) }struct curry { -void *last; +void **arr; +size_t len; }; -static void check_increasing (void *arg,void *key) +static void store (void *arg,void *key) {struct curry *c = arg; -if (c->last) - check_int(test_compare(c->last, key), <, 0); - c->last = key; + c->arr[c->len++] = key; }static void test_tree_search (void )
@@ -51,15 +50,24 @@ static void test_infix_walk(void) {struct tree_node *root =NULL ;void *values[11 ] = {0 }; -struct curry c = {0 }; +void *out[11 ] = {0 }; +struct curry c = { + .arr = (void **) &out, + };size_t i =1 ; +size_t count =0 ;do {tree_search (values + i, &root, &test_compare,1 ); i = (i *7 ) %11 ; + count++; }while (i !=1 ); -infix_walk (root, &check_increasing, &c); +infix_walk (root, &store, &c); +for (i =1 ; i <ARRAY_SIZE (values); i++) +check_pointer_eq (values + i, out[i -1 ]); +check (!out[i -1 ]); + check_int(c.len, ==, count);tree_free (root); }
Signature · 1 line
2.45.2.404.g9eaef5822c
v4 cover t: port reftable/tree_test.c to the unit testing framework
In reply to Chandra PratapIn 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/tree_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.
---
Changes in v4:
- Rename the tests to be in-line with unit-tests' standards
CI/PR: https://github.com/gitgitgadget/git/pull/1740
Chandra Pratap(5):
reftable: remove unnecessary curly braces in reftable/tree.c
t: move reftable/tree_test.c to the unit testing framework
t-reftable-tree: split test_tree() into two sub-test
t-reftable-tree: add test for non-existent key
t-reftable-tree: improve the test for infix_walk()
Makefile | 2 +- reftable/reftable-tests.h | 1 - reftable/tree.c | 15 +++------- reftable/tree_test.c | 60 ---------------------- t/helper/test-reftable.c | 1 - t/unit-tests/t-reftable-tree.c | 80 +++++++++++++++++++++++++++++++++++++ 6 files changed, 86 insertions(+), 73 deletions(-)
Range-diff against v3:
1: ffabd3e411 = 1: 2be2a35b7f reftable: remove unnecessary curly braces in reftable/tree.c
2: 17937233fb < -: ---------- t: move reftable/tree_test.c to the unit testing framework
-: ---------- > 2: de49698ea7 t: move reftable/tree_test.c to the unit testing framework
3: c3992091db ! 3: c733776054 t-reftable-tree: split test_tree() into two sub-test functions
@@ t/unit-tests/t-reftable-tree.c: static void check_increasing(void *arg, void *ke
c->last = key;
}
--static void test_tree(void)
-+static void test_tree_search(void)
+-static void t_tree(void)
++static void t_tree_search(void)
{
struct tree_node *root = NULL;
void *values[11] = { 0 };
@@ t/unit-tests/t-reftable-tree.c: static void check_increasing(void *arg, void *ke
- struct curry c = { 0 };
do {
- nodes[i] = tree_search(values + i, &root, &test_compare, 1);
-@@ t/unit-tests/t-reftable-tree.c: static void test_tree(void)
- check_pointer_eq(nodes[i], tree_search(values + i, &root, &test_compare, 0));
+ nodes[i] = tree_search(values + i, &root, &t_compare, 1);
+@@ t/unit-tests/t-reftable-tree.c: static void t_tree(void)
+ check_pointer_eq(nodes[i], tree_search(values + i, &root, &t_compare, 0));
}
- infix_walk(root, check_increasing, &c);
+ tree_free(root);
+}
+
-+static void test_infix_walk(void)
++static void t_infix_walk(void)
+{
+ struct tree_node *root = NULL;
+ void *values[11] = { 0 };
@@ t/unit-tests/t-reftable-tree.c: static void test_tree(void)
+ size_t i = 1;
+
+ do {
-+ tree_search(values + i, &root, &test_compare, 1);
++ tree_search(values + i, &root, &t_compare, 1);
+ i = (i * 7) % 11;
+ } while (i != 1);
+
@@ t/unit-tests/t-reftable-tree.c: static void test_tree(void)
int cmd_main(int argc, const char *argv[])
{
-- TEST(test_tree(), "tree_search and infix_walk work");
-+ TEST(test_tree_search(), "tree_search works");
-+ TEST(test_infix_walk(), "infix_walk works");
+- TEST(t_tree(), "tree_search and infix_walk work");
++ TEST(t_tree_search(), "tree_search works");
++ TEST(t_infix_walk(), "infix_walk works");
return test_done();
}4: 99a0ed484e ! 4: f1a9325bb3 t-reftable-tree: add test for non-existent key
@@ Commit message
## t/unit-tests/t-reftable-tree.c ##
-@@ t/unit-tests/t-reftable-tree.c: static void test_tree_search(void)
- check_pointer_eq(nodes[i], tree_search(values + i, &root, &test_compare, 0));
+@@ t/unit-tests/t-reftable-tree.c: static void t_tree_search(void)
+ check_pointer_eq(nodes[i], tree_search(values + i, &root, &t_compare, 0));
}
+ check(!tree_search(values, &root, &test_compare, 0));
5: 4fce9a8bd8 ! 5: c6b7a3d646 t-reftable-tree: improve the test for infix_walk()
@@ Commit message
Signed-off-by: Chandra Pratap <[email protected]>
## t/unit-tests/t-reftable-tree.c ##
-@@ t/unit-tests/t-reftable-tree.c: static int test_compare(const void *a, const void *b)
+@@ t/unit-tests/t-reftable-tree.c: static int t_compare(const void *a, const void *b)
}
struct curry {
@@ t/unit-tests/t-reftable-tree.c: static int test_compare(const void *a, const voi
{
struct curry *c = arg;
- if (c->last)
-- check_int(test_compare(c->last, key), <, 0);
+- check_int(t_compare(c->last, key), <, 0);
- c->last = key;
+ c->arr[c->len++] = key;
}
- static void test_tree_search(void)
-@@ t/unit-tests/t-reftable-tree.c: static void test_infix_walk(void)
+ static void t_tree_search(void)
+@@ t/unit-tests/t-reftable-tree.c: static void t_infix_walk(void)
{
struct tree_node *root = NULL;
void *values[11] = { 0 };
@@ t/unit-tests/t-reftable-tree.c: static void test_infix_walk(void)
+ size_t count = 0;
do {
- tree_search(values + i, &root, &test_compare, 1);
+ tree_search(values + i, &root, &t_compare, 1);
i = (i * 7) % 11;
+ count++;
} while (i != 1);PATCH v4 1/5 reftable: remove unnecessary curly braces in reftable/tree.c
According to Documentation/CodingGuidelines, single-line control-flow statements must omit curly braces (except for some special cases). Make reftable/tree.c adhere to this guideline.
--- reftable/tree.c | 15 +++++---------- 1 file changed, 5 insertions(+), 10 deletions(-)
reftable/tree.c +5 -10
@@ -39,25 +39,20 @@ struct tree_node *tree_search(void *key, struct tree_node **rootp,void infix_walk (struct tree_node *t,void (*action)(void *arg,void *key),void *arg) { -if (t->left) { +if (t->left)infix_walk (t->left, action, arg); - }action (arg, t->key); -if (t->right) { +if (t->right)infix_walk (t->right, action, arg); - } }void tree_free (struct tree_node *t) { -if (!t) { +if (!t)return ; - } -if (t->left) { +if (t->left)tree_free (t->left); - } -if (t->right) { +if (t->right)tree_free (t->right); - }reftable_free (t); }
Signature · 1 line
2.45.GIT
PATCH v4 2/5 t: move reftable/tree_test.c to the unit testing framework
In reply to Chandra Pratapreftable/tree_test.c exercises the functions defined in reftable/tree.{c, h}. Migrate reftable/tree_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.
--- Makefile | 2 +- reftable/reftable-tests.h | 1 - reftable/tree_test.c | 60 ---------------------------------- t/helper/test-reftable.c | 1 - t/unit-tests/t-reftable-tree.c | 56 +++++++++++++++++++++++++++++++ 5 files changed, 57 insertions(+), 63 deletions(-) delete mode 100644 reftable/tree_test.c create mode 100644 t/unit-tests/t-reftable-tree.c
Makefile +1 -1
@@ -1340,6 +1340,7 @@ UNIT_TEST_PROGRAMS += t-mem-pool UNIT_TEST_PROGRAMS += t-oidtree UNIT_TEST_PROGRAMS += t-prio-queue UNIT_TEST_PROGRAMS += t-reftable-basics +UNIT_TEST_PROGRAMS += t-reftable-tree UNIT_TEST_PROGRAMS += t-strbuf UNIT_TEST_PROGRAMS += t-strcmp-offset UNIT_TEST_PROGRAMS += t-strvec
@@ -2685,7 +2686,6 @@ 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_TEST_OBJS += reftable/tree_test.o TEST_OBJS := $(patsubst %$X,%.o,$(TEST_PROGRAMS)) $(patsubst %,t/helper/%,$(TEST_BUILTINS_OBJS))
reftable/reftable-tests.h +0 -1
@@ -16,7 +16,6 @@ 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); -int tree_test_main (int argc,const char **argv);int reftable_dump_main (int argc,char *const *argv);#endif
reftable/tree_test.c deleted +0 -60
60 lines not on this page · raw message
t/helper/test-reftable.c +0 -1
@@ -7,7 +7,6 @@ int cmd__reftable(int argc, const char **argv)/* test from simple to complex. */ 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);
t/unit-tests/t-reftable-tree.c new file +56 -0
56 lines not on this page · raw message
Signature · 1 line
2.45.GIT
Re: [PATCH v4 2/5] t: move reftable/tree_test.c to the unit testing framework
Quoted 6 lines · Chandra Pratap
reftable/tree_test.cexercises the functions defined in reftable/tree.{c, h}. Migratereftable/tree_test.cto 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.
Nit: it would be nice to mention that this commit copies it over as-is (mostly) and the upcoming commits do refactoring. This would really help reviewers.
Quoted 187 lines
Mentored-by Patrick Steinhardt <[email protected]>Mentored-by Christian Couder <[email protected]>Signed-off-by Chandra Pratap <[email protected]>--- Makefile | 2 +- reftable/reftable-tests.h | 1 - reftable/tree_test.c | 60 ---------------------------------- t/helper/test-reftable.c | 1 - t/unit-tests/t-reftable-tree.c | 56 +++++++++++++++++++++++++++++++ 5 files changed, 57 insertions(+), 63 deletions(-) delete mode 100644 reftable/tree_test.c create mode 100644 t/unit-tests/t-reftable-tree.cMakefile +1
-1@@ -1340,6 +1340,7 @@ UNIT_TEST_PROGRAMS += t-mem-pool UNIT_TEST_PROGRAMS += t-oidtree UNIT_TEST_PROGRAMS += t-prio-queue UNIT_TEST_PROGRAMS += t-reftable-basics +UNIT_TEST_PROGRAMS += t-reftable-tree UNIT_TEST_PROGRAMS += t-strbuf UNIT_TEST_PROGRAMS += t-strcmp-offset UNIT_TEST_PROGRAMS += t-strvec@@ -2685,7 +2686,6 @@ 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_TEST_OBJS += reftable/tree_test.o TEST_OBJS := $(patsubst %$X,%.o,$(TEST_PROGRAMS)) $(patsubst %,t/helper/%,$(TEST_BUILTINS_OBJS))reftable/reftable-tests.h +0
-1@@ -16,7 +16,6 @@ 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); -int tree_test_main (int argc,const char **argv);int reftable_dump_main (int argc,char *const *argv);#endif reftable/tree_test.c deleted +0
-60@@ -1,60 +0,0 @@ -/* -Copyright 2020 Google LLC - -Use of this source code is governed by a BSD-style -license that can be found in the LICENSE file or at -https://developers.google.com/open-source/licenses/bsd -*/ - -#include "system.h" -#include "tree.h" - -#include "test_framework.h" -#include "reftable-tests.h" - -static int test_compare (const void *a,const void *b) -{ -return (char *)a - (char *)b; -} - -struct curry { -void *last; -}; - -static void check_increasing (void *arg,void *key) -{ -struct curry *c = arg; -if (c->last) { -EXPECT (test_compare (c->last, key) <0 ); - } - c->last = key; -} - -static void test_tree (void ) -{ -struct tree_node *root =NULL ; - -void *values[11 ] = {NULL }; -struct tree_node *nodes[11 ] = {NULL }; -int i =1 ; -struct curry c = {NULL }; -do { - nodes[i] =tree_search (values + i, &root, &test_compare,1 ); - i = (i *7 ) %11 ; - }while (i !=1 ); - -for (i =1 ; i <ARRAY_SIZE (nodes); i++) { -EXPECT (values + i == nodes[i]->key); -EXPECT (nodes[i] == -tree_search (values + i, &root, &test_compare,0 )); - } - -infix_walk (root, check_increasing, &c); -tree_free (root); -} - -int tree_test_main (int argc,const char *argv[]) -{ -RUN_TEST (test_tree); -return 0 ; -}t/helper/test-reftable.c +0
-1@@ -7,7 +7,6 @@ int cmd__reftable(int argc, const char **argv)/* test from simple to complex. */ 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);t/unit-tests/t-reftable-tree.c new file +56
-1@@ -0,0 +1,56 @@ +/* +Copyright 2020 Google LLC + +Use of this source code is governed by a BSD-style +license that can be found in the LICENSE file or at +https://developers.google.com/open-source/licenses/bsd +*/ + +#include "test-lib.h" +#include "reftable/tree.h" + +static int t_compare (const void *a,const void *b) +{ +return (char *)a - (char *)b; +} + +struct curry { +void *last; +}; + +static void check_increasing (void *arg,void *key) +{ +struct curry *c = arg; +if (c->last) + check_int(t_compare(c->last, key), <, 0); + c->last = key; +} + +static void t_tree (void ) +{ +struct tree_node *root =NULL ; +void *values[11 ] = {0 }; +struct tree_node *nodes[11 ] = {0 }; +size_t i =1 ; +struct curry c = {0 }; + +do { + nodes[i] =tree_search (values + i, &root, &t_compare,1 ); + i = (i *7 ) %11 ; + }while (i !=1 ); + +for (i =1 ; i <ARRAY_SIZE (nodes); i++) { +check_pointer_eq (values + i, nodes[i]->key); +check_pointer_eq (nodes[i],tree_search (values + i, &root, &t_compare,0 )); + } + +infix_walk (root, check_increasing, &c); +tree_free (root); +} + +int cmd_main (int argc,const char *argv[]) +{ +TEST (t_tree (),"tree_search and infix_walk work" ); + +return test_done (); +} --2.45.GIT
Re: [PATCH v4 2/5] t: move reftable/tree_test.c to the unit testing framework
Quoted 10 lines · Karthik Nayak
Quoted 6 lines · Chandra Pratap
reftable/tree_test.cexercises the functions defined in reftable/tree.{c, h}. Migratereftable/tree_test.cto 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.
Quoted 3 lines
Nit: it would be nice to mention that this commit copies it over as-is (mostly) and the upcoming commits do refactoring. This would really help reviewers.
I do mention that in the patch cover letter, specifically this paragraph:
Quoted 3 lines
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.
Would it be better if I transport that here?
----[snip]----
Re: [PATCH v4 2/5] t: move reftable/tree_test.c to the unit testing framework
Quoted 17 lines · Chandra Pratap
Quoted 10 lines · Karthik Nayak
Quoted 6 lines · Chandra Pratap
reftable/tree_test.cexercises the functions defined in reftable/tree.{c, h}. Migratereftable/tree_test.cto 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.Quoted 3 lines
Nit: it would be nice to mention that this commit copies it over as-is (mostly) and the upcoming commits do refactoring. This would really help reviewers.
I do mention that in the patch cover letter, specifically this paragraph:
Quoted 7 lines
Quoted 3 lines
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.
Would it be better if I transport that here?
----[snip]----
I think that would be nice!
Re: [PATCH v4 2/5] t: move reftable/tree_test.c to the unit testing framework
In reply to Chandra PratapQuoted 6 lines · Chandra Pratap
reftable/tree_test.cexercises the functions defined in reftable/tree.{c, h}. Migratereftable/tree_test.cto 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.
On second thought, it's easier for me to review here for the existing state of the code. So let me do that..
[snip]
Quoted 12 lines
t/unit-tests/t-reftable-tree.c new file +6
-0@@ -0,0 +1,56 @@ +/* +Copyright 2020 Google LLC + +Use of this source code is governed by a BSD-style +license that can be found in the LICENSE file or at +https://developers.google.com/open-source/licenses/bsd
t/unit-tests/t-reftable-tree.c line 16
Quoted 10 lines
t/unit-tests/t-reftable-tree.c new file +10
-0+*/ + +#include "test-lib.h" +#include "reftable/tree.h" + +static int t_compare (const void *a,const void *b) +{ +return (char *)a - (char *)b; +} +
So this is the comparison code, and we're expecting the values to be a character. Okay.
Quoted 6 lines
t/unit-tests/t-reftable-tree.c new file +6
-0+struct curry { +void *last; +}; + +static void check_increasing (void *arg,void *key) +{
t/unit-tests/t-reftable-tree.c line 32
Quoted 10 lines
t/unit-tests/t-reftable-tree.c new file +10
-0+struct curry *c = arg; +if (c->last) + check_int(t_compare(c->last, key), <, 0); + c->last = key; +} + +static void t_tree (void ) +{ +struct tree_node *root =NULL ; +void *values[11 ] = {0 };
Although we were comparing 'char' above, here we have a 'void *' array. Why?
t/unit-tests/t-reftable-tree.c line 39
Quoted 7 lines
t/unit-tests/t-reftable-tree.c new file +7
-0+struct tree_node *nodes[11 ] = {0 }; +size_t i =1 ; +struct curry c = {0 }; + + do { + nodes[i] = tree_search(values + i, &root, &t_compare, 1); + i = (i * 7) % 11;
It gets weirder, we calculate 'i' as {7, 5, 2, 3, 10, 4, 6, 9, 8, 1}. We use that to index 'values', but values is '0' initialized, so we always send '0' to tree_search? Doesn't that make this whole thing a moot? Or did I miss something?
Quoted 19 lines
t/unit-tests/t-reftable-tree.c new file +17
-1+ }while (i !=1 ); + +for (i =1 ; i <ARRAY_SIZE (nodes); i++) { +check_pointer_eq (values + i, nodes[i]->key); +check_pointer_eq (nodes[i],tree_search (values + i, &root, &t_compare,0 )); + } + +infix_walk (root, check_increasing, &c); +tree_free (root); +} + +int cmd_main (int argc,const char *argv[]) +{ +TEST (t_tree (),"tree_search and infix_walk work" ); + +return test_done (); +} --2.45.GIT
Re: [PATCH v4 2/5] t: move reftable/tree_test.c to the unit testing framework
Quoted 32 lines · Karthik Nayak
Quoted 6 lines · Chandra Pratap
reftable/tree_test.cexercises the functions defined in reftable/tree.{c, h}. Migratereftable/tree_test.cto 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.On second thought, it's easier for me to review here for the existing state of the code. So let me do that..
[snip]
Quoted 17 lines
t/unit-tests/t-reftable-tree.c new file +11
-0@@ -0,0 +1,56 @@ +/* +Copyright 2020 Google LLC + +Use of this source code is governed by a BSD-style +license that can be found in the LICENSE file or at +https://developers.google.com/open-source/licenses/bsd +*/ + +#include "test-lib.h" +#include "reftable/tree.h" +
Quoted 8 lines
t/unit-tests/t-reftable-tree.c line 16
Quoted 5 lines
t/unit-tests/t-reftable-tree.c new file +5
-0+static int t_compare (const void *a,const void *b) +{ +return (char *)a - (char *)b; +} +So this is the comparison code, and we're expecting the values to be a character. Okay.
We're actually expecting the values 'a' and 'b' to be of the type (char *), which is a pointer to a character, and thus we perform the comparison on the basis of pointer arithmetic.
Quoted 11 lines
Quoted 11 lines
t/unit-tests/t-reftable-tree.c new file +11
-0+struct curry { +void *last; +}; + +static void check_increasing (void *arg,void *key) +{ +struct curry *c = arg; +if (c->last) + check_int(t_compare(c->last, key), <, 0); + c->last = key; +}
Quoted 8 lines
t/unit-tests/t-reftable-tree.c line 32
Quoted 5 lines
t/unit-tests/t-reftable-tree.c new file +5
-0+ +static void t_tree (void ) +{ +struct tree_node *root =NULL ; +void *values[11 ] = {0 };Although we were comparing 'char' above, here we have a 'void *' array. Why?
The array is passed as a parameter to the 'tree_search()' function which requires a void * parameter (i.e. a generic pointer). In the comparison function (also passed as a parameter), we cast it to our expected type (a character pointer) and then perform the required comparison.
Quoted 8 lines
t/unit-tests/t-reftable-tree.c line 39
Quoted 7 lines
t/unit-tests/t-reftable-tree.c new file +7
-0+struct tree_node *nodes[11 ] = {0 }; +size_t i =1 ; +struct curry c = {0 }; + + do { + nodes[i] = tree_search(values + i, &root, &t_compare, 1); + i = (i * 7) % 11;
Quoted 4 lines
It gets weirder, we calculate 'i' as {7, 5, 2, 3, 10, 4, 6, 9, 8, 1}. We use that to index 'values', but values is '0' initialized, so we always send '0' to
tree_search? Doesn't that make this whole thing a moot? Or did I miss something?
We don't use 'i' to index 'values[]', we use it to calculate the next pointer address to be passed to the 'tree_search()' function (the pointer that is 'i' ahead of the pointer 'values'), which isn't 0.
Quoted 19 lines
Quoted 19 lines
t/unit-tests/t-reftable-tree.c new file +17
-1+ }while (i !=1 ); + +for (i =1 ; i <ARRAY_SIZE (nodes); i++) { +check_pointer_eq (values + i, nodes[i]->key); +check_pointer_eq (nodes[i],tree_search (values + i, &root, &t_compare,0 )); + } + +infix_walk (root, check_increasing, &c); +tree_free (root); +} + +int cmd_main (int argc,const char *argv[]) +{ +TEST (t_tree (),"tree_search and infix_walk work" ); + +return test_done (); +} --2.45.GIT
Re: [PATCH v4 2/5] t: move reftable/tree_test.c to the unit testing framework
Quoted 24 lines · Chandra Pratap
Quoted 14 lines · Karthik Nayak
Quoted 11 lines · Chandra Pratap
t/unit-tests/t-reftable-tree.c new file +11
-0+struct curry { +void *last; +}; + +static void check_increasing (void *arg,void *key) +{ +struct curry *c = arg; +if (c->last) + check_int(t_compare(c->last, key), <, 0); + c->last = key; +}Quoted 8 lines
t/unit-tests/t-reftable-tree.c line 32
Quoted 5 lines
t/unit-tests/t-reftable-tree.c new file +5
-0+ +static void t_tree (void ) +{ +struct tree_node *root =NULL ; +void *values[11 ] = {0 };Although we were comparing 'char' above, here we have a 'void *' array. Why?
Quoted 4 lines
The array is passed as a parameter to the '
tree_search()' function which requires a void * parameter (i.e. a generic pointer). In the comparison function (also passed as a parameter), we cast it to our expected type (a character pointer) and then perform the required comparison.
The point of values is to provide a set of values of type void ** to be inserted in the tree. As far as I can tell, there is no reason for values to be initialized to begin with and is a bit misleading. Might be reasonable to remove its initialization here.
Quoted 8 lines
Quoted 8 lines
Quoted 7 lines
t/unit-tests/t-reftable-tree.c new file +7
-0+struct tree_node *nodes[11 ] = {0 }; +size_t i =1 ; +struct curry c = {0 }; + + do { + nodes[i] = tree_search(values + i, &root, &t_compare, 1); + i = (i * 7) % 11;
Quoted 8 lines
Quoted 4 lines
It gets weirder, we calculate 'i' as {7, 5, 2, 3, 10, 4, 6, 9, 8, 1}. We use that to index 'values', but values is '0' initialized, so we always send '0' to
tree_search? Doesn't that make this whole thing a moot? Or did I miss something?We don't use 'i' to index 'values[]', we use it to calculate the next pointer address to be passed to the '
tree_search()' function (the pointer that is 'i' ahead of the pointer 'values'), which isn't 0.
The i = (i * 7) % 11; is used to deterministically generate numbers 1-10 in a psuedo-random fashion. These numbers are used as memory offsets to be inserted into the tree. I suspect the psuedo-randomness is useful keys should be ordered when inserted into the tree and that is later validated as part of the in-order traversal that is performed.
While rather compact, I find the test setup here to rather difficult to parse. It might be a good idea to either provide comments explaining this test setup or consider refactoring it. Honestly, I'd personally perfer the tree setup be done more explicitly as I think it would make understanding the test much easier.
-Justin
Re: [PATCH v4 2/5] t: move reftable/tree_test.c to the unit testing framework
Quoted 31 lines · Justin Tobler
Quoted 24 lines · Chandra Pratap
Quoted 14 lines · Karthik Nayak
Quoted 11 lines · Chandra Pratap
t/unit-tests/t-reftable-tree.c new file +11
-0+struct curry { +void *last; +}; + +static void check_increasing (void *arg,void *key) +{ +struct curry *c = arg; +if (c->last) + check_int(t_compare(c->last, key), <, 0); + c->last = key; +}Quoted 8 lines
t/unit-tests/t-reftable-tree.c line 32
Quoted 5 lines
t/unit-tests/t-reftable-tree.c new file +5
-0+ +static void t_tree (void ) +{ +struct tree_node *root =NULL ; +void *values[11 ] = {0 };Although we were comparing 'char' above, here we have a 'void *' array. Why?
Quoted 4 lines
The array is passed as a parameter to the '
tree_search()' function which requires a void * parameter (i.e. a generic pointer). In the comparison function (also passed as a parameter), we cast it to our expected type (a character pointer) and then perform the required comparison.
Quoted 4 lines
The point of
valuesis to provide a set of values of typevoid **to be inserted in the tree. As far as I can tell, there is no reason forvaluesto be initialized to begin with and is a bit misleading. Might be reasonable to remove its initialization here.
The thing is, the values[] array being 0-initialized makes debugging a lot easier in the case of a test failure, so I'm not very sure about getting rid of the initialization here.
Quoted 17 lines
Quoted 8 lines
Quoted 8 lines
Quoted 7 lines
t/unit-tests/t-reftable-tree.c new file +7
-0+struct tree_node *nodes[11 ] = {0 }; +size_t i =1 ; +struct curry c = {0 }; + + do { + nodes[i] = tree_search(values + i, &root, &t_compare, 1); + i = (i * 7) % 11;Quoted 8 lines
Quoted 4 lines
It gets weirder, we calculate 'i' as {7, 5, 2, 3, 10, 4, 6, 9, 8, 1}. We use that to index 'values', but values is '0' initialized, so we always send '0' to
tree_search? Doesn't that make this whole thing a moot? Or did I miss something?We don't use 'i' to index 'values[]', we use it to calculate the next pointer address to be passed to the '
tree_search()' function (the pointer that is 'i' ahead of the pointer 'values'), which isn't 0.
Quoted 5 lines
The
i = (i * 7) % 11;is used to deterministically generate numbers 1-10 in a psuedo-random fashion. These numbers are used as memory offsets to be inserted into the tree. I suspect the psuedo-randomness is useful keys should be ordered when inserted into the tree and that is later validated as part of the in-order traversal that is performed.
That's right, the randomness of the insertion order is helpful in validating that the tree-functions 'tree_search()' and 'infix_walk()' work according to their defined behaviour.
Quoted 5 lines
While rather compact, I find the test setup here to rather difficult to parse. It might be a good idea to either provide comments explaining this test setup or consider refactoring it. Honestly, I'd personally perfer the tree setup be done more explicitly as I think it would make understanding the test much easier.
This probably ties in with the comments by Patrick on the previous iteration of this patch, that using 'tree_search()' to insert tree nodes leads to confusion. Solving that would require efforts outside the scope of this patch series though, so I'm more inclined towards providing comments and other ways of simplifying this subroutine.
Re: [PATCH v4 2/5] t: move reftable/tree_test.c to the unit testing framework
Quoted 74 lines · Chandra Pratap
Quoted 31 lines · Justin Tobler
Quoted 24 lines · Chandra Pratap
Quoted 14 lines · Karthik Nayak
Quoted 11 lines · Chandra Pratap
t/unit-tests/t-reftable-tree.c new file +11
-0+struct curry { +void *last; +}; + +static void check_increasing (void *arg,void *key) +{ +struct curry *c = arg; +if (c->last) + check_int(t_compare(c->last, key), <, 0); + c->last = key; +}Quoted 8 lines
t/unit-tests/t-reftable-tree.c line 32
Quoted 5 lines
t/unit-tests/t-reftable-tree.c new file +5
-0+ +static void t_tree (void ) +{ +struct tree_node *root =NULL ; +void *values[11 ] = {0 };Although we were comparing 'char' above, here we have a 'void *' array. Why?
Quoted 4 lines
The array is passed as a parameter to the '
tree_search()' function which requires a void * parameter (i.e. a generic pointer). In the comparison function (also passed as a parameter), we cast it to our expected type (a character pointer) and then perform the required comparison.Quoted 4 lines
The point of
valuesis to provide a set of values of typevoid **to be inserted in the tree. As far as I can tell, there is no reason forvaluesto be initialized to begin with and is a bit misleading. Might be reasonable to remove its initialization here.The thing is, the values[] array being 0-initialized makes debugging a lot easier in the case of a test failure, so I'm not very sure about getting rid of the initialization here.
Quoted 17 lines
Quoted 8 lines
Quoted 8 lines
Quoted 7 lines
t/unit-tests/t-reftable-tree.c new file +7
-0+struct tree_node *nodes[11 ] = {0 }; +size_t i =1 ; +struct curry c = {0 }; + + do { + nodes[i] = tree_search(values + i, &root, &t_compare, 1); + i = (i * 7) % 11;Quoted 8 lines
Quoted 4 lines
It gets weirder, we calculate 'i' as {7, 5, 2, 3, 10, 4, 6, 9, 8, 1}. We use that to index 'values', but values is '0' initialized, so we always send '0' to
tree_search? Doesn't that make this whole thing a moot? Or did I miss something?We don't use 'i' to index 'values[]', we use it to calculate the next pointer address to be passed to the '
tree_search()' function (the pointer that is 'i' ahead of the pointer 'values'), which isn't 0.Quoted 5 lines
The
i = (i * 7) % 11;is used to deterministically generate numbers 1-10 in a psuedo-random fashion. These numbers are used as memory offsets to be inserted into the tree. I suspect the psuedo-randomness is useful keys should be ordered when inserted into the tree and that is later validated as part of the in-order traversal that is performed.That's right, the randomness of the insertion order is helpful in validating that the tree-functions '
tree_search()' and 'infix_walk()' work according to their defined behaviour.Quoted 5 lines
While rather compact, I find the test setup here to rather difficult to parse. It might be a good idea to either provide comments explaining this test setup or consider refactoring it. Honestly, I'd personally perfer the tree setup be done more explicitly as I think it would make understanding the test much easier.
Quoted 5 lines
This probably ties in with the comments by Patrick on the previous iteration of this patch, that using '
tree_search()' to insert tree nodes leads to confusion. Solving that would require efforts outside the scope of this patch series though, so I'm more inclined towards providing comments and other ways of simplifying this subroutine.
Agreed that refactoring tree_search() probably is out of scope here. But rewriting the test is definitely something we can do.
Perhaps:
static void t_tree(void)
{
struct tree_node *root = NULL;
int values[11] = {7, 5, 2, 3, 10, 4, 6, 9, 8, 1};
struct tree_node *nodes[11] = { 0 };
size_t i = 1;
struct curry c = { 0 };
// Insert values to the tree by passing '1' as the last argument.
for (i = 1; i < ARRAY_SIZE(values); i++) {
nodes[i] = tree_search(&values[i], &root, &t_compare, 1);
}
for (i = 1; i < ARRAY_SIZE(nodes); i++) {
check_pointer_eq(values[i], nodes[i]->key);
check_pointer_eq(nodes[i], tree_search(values + i, &root, &t_compare, 0));
}
infix_walk(root, check_increasing, &c);
tree_free(root);
}Wouldn't this have the same effect while making it much easier to read?
Re: [PATCH v4 2/5] t: move reftable/tree_test.c to the unit testing framework
Quoted 110 lines · Karthik Nayak
Quoted 74 lines · Chandra Pratap
Quoted 31 lines · Justin Tobler
Quoted 24 lines · Chandra Pratap
Quoted 14 lines · Karthik Nayak
Quoted 11 lines · Chandra Pratap
t/unit-tests/t-reftable-tree.c new file +11
-0+struct curry { +void *last; +}; + +static void check_increasing (void *arg,void *key) +{ +struct curry *c = arg; +if (c->last) + check_int(t_compare(c->last, key), <, 0); + c->last = key; +}Quoted 8 lines
t/unit-tests/t-reftable-tree.c line 32
Quoted 5 lines
t/unit-tests/t-reftable-tree.c new file +5
-0+ +static void t_tree (void ) +{ +struct tree_node *root =NULL ; +void *values[11 ] = {0 };Although we were comparing 'char' above, here we have a 'void *' array. Why?
Quoted 4 lines
The array is passed as a parameter to the '
tree_search()' function which requires a void * parameter (i.e. a generic pointer). In the comparison function (also passed as a parameter), we cast it to our expected type (a character pointer) and then perform the required comparison.Quoted 4 lines
The point of
valuesis to provide a set of values of typevoid **to be inserted in the tree. As far as I can tell, there is no reason forvaluesto be initialized to begin with and is a bit misleading. Might be reasonable to remove its initialization here.The thing is, the values[] array being 0-initialized makes debugging a lot easier in the case of a test failure, so I'm not very sure about getting rid of the initialization here.
Quoted 17 lines
Quoted 8 lines
Quoted 8 lines
Quoted 7 lines
t/unit-tests/t-reftable-tree.c new file +7
-0+struct tree_node *nodes[11 ] = {0 }; +size_t i =1 ; +struct curry c = {0 }; + + do { + nodes[i] = tree_search(values + i, &root, &t_compare, 1); + i = (i * 7) % 11;Quoted 8 lines
Quoted 4 lines
It gets weirder, we calculate 'i' as {7, 5, 2, 3, 10, 4, 6, 9, 8, 1}. We use that to index 'values', but values is '0' initialized, so we always send '0' to
tree_search? Doesn't that make this whole thing a moot? Or did I miss something?We don't use 'i' to index 'values[]', we use it to calculate the next pointer address to be passed to the '
tree_search()' function (the pointer that is 'i' ahead of the pointer 'values'), which isn't 0.Quoted 5 lines
The
i = (i * 7) % 11;is used to deterministically generate numbers 1-10 in a psuedo-random fashion. These numbers are used as memory offsets to be inserted into the tree. I suspect the psuedo-randomness is useful keys should be ordered when inserted into the tree and that is later validated as part of the in-order traversal that is performed.That's right, the randomness of the insertion order is helpful in validating that the tree-functions '
tree_search()' and 'infix_walk()' work according to their defined behaviour.Quoted 5 lines
While rather compact, I find the test setup here to rather difficult to parse. It might be a good idea to either provide comments explaining this test setup or consider refactoring it. Honestly, I'd personally perfer the tree setup be done more explicitly as I think it would make understanding the test much easier.
Quoted 5 lines
This probably ties in with the comments by Patrick on the previous iteration of this patch, that using '
tree_search()' to insert tree nodes leads to confusion. Solving that would require efforts outside the scope of this patch series though, so I'm more inclined towards providing comments and other ways of simplifying this subroutine.Agreed that refactoring
tree_search()probably is out of scope here. But rewriting the test is definitely something we can do.Perhaps:
static void
t_tree(void){ struct tree_node *root = NULL; int values[11] = {7, 5, 2, 3, 10, 4, 6, 9, 8, 1}; struct tree_node *nodes[11] = { 0 }; size_t i = 1; struct curry c = { 0 }; // Insert values to the tree by passing '1' as the last argument. for (i = 1; i < ARRAY_SIZE(values); i++) { nodes[i] = tree_search(&values[i], &root, &t_compare, 1); } for (i = 1; i < ARRAY_SIZE(nodes); i++) { check_pointer_eq(values[i], nodes[i]->key); check_pointer_eq(nodes[i], tree_search(values + i, &root, &t_compare, 0)); } infix_walk(root, check_increasing, &c); tree_free(root); }
Quoted 1 line
Wouldn't this have the same effect while making it much easier to read?
I agree that the change 'values + i -> &values[i]' is a net positive, I had this change in mind as well. This comment on the other hand,
Quoted 1 line
// Insert values to the tree by passing '1' as the last argument.
has already been stated in the commit message of the 3rd patch as was suggested by Patrick earlier:
'Note that the last parameter in the tree_search() function is 'int insert' which when set, inserts the key if it is not found in the tree. Otherwise, the function returns NULL for such cases.'
So I was thinking of adding something along the lines of:
'// pseudo-randomly insert pointers to elements between values[1] and values[10] in the tree'
Re: [PATCH v4 2/5] t: move reftable/tree_test.c to the unit testing framework
In reply to Karthik NayakQuoted 55 lines · Karthik Nayak
Quoted 20 lines · Chandra Pratap
Quoted 8 lines · Justin Tobler
On 24/07/17 08:00PM, Chandra Pratap wrote:
The
i = (i * 7) % 11;is used to deterministically generate numbers 1-10 in a psuedo-random fashion. These numbers are used as memory offsets to be inserted into the tree. I suspect the psuedo-randomness is useful keys should be ordered when inserted into the tree and that is later validated as part of the in-order traversal that is performed.That's right, the randomness of the insertion order is helpful in validating that the tree-functions '
tree_search()' and 'infix_walk()' work according to their defined behaviour.Quoted 5 lines
While rather compact, I find the test setup here to rather difficult to parse. It might be a good idea to either provide comments explaining this test setup or consider refactoring it. Honestly, I'd personally perfer the tree setup be done more explicitly as I think it would make understanding the test much easier.
Quoted 5 lines
This probably ties in with the comments by Patrick on the previous iteration of this patch, that using '
tree_search()' to insert tree nodes leads to confusion. Solving that would require efforts outside the scope of this patch series though, so I'm more inclined towards providing comments and other ways of simplifying this subroutine.Agreed that refactoring
tree_search()probably is out of scope here. But rewriting the test is definitely something we can do.Perhaps:
static void
t_tree(void){ struct tree_node *root = NULL; int values[11] = {7, 5, 2, 3, 10, 4, 6, 9, 8, 1}; struct tree_node *nodes[11] = { 0 }; size_t i = 1; struct curry c = { 0 }; // Insert values to the tree by passing '1' as the last argument. for (i = 1; i < ARRAY_SIZE(values); i++) { nodes[i] = tree_search(&values[i], &root, &t_compare, 1); } for (i = 1; i < ARRAY_SIZE(nodes); i++) { check_pointer_eq(values[i], nodes[i]->key); check_pointer_eq(nodes[i], tree_search(values + i, &root, &t_compare, 0)); } infix_walk(root, check_increasing, &c); tree_free(root); }
Quoted 1 line
Wouldn't this have the same effect while making it much easier to read?
Personally, I quite like this approach. It's more up front with what its doing and ultimately accoplishes the same thing.
PATCH v4 3/5 t-reftable-tree: split test_tree() into two sub-test functions
In reply to Chandra PratapIn the current testing setup, tests for both tree_search() and infix_walk() defined by reftable/tree.{c, h} are performed by a single test function, test_tree(). Split tree_test() into test_tree_search() and test_infix_walk() responsible for independently testing tree_search() and infix_walk() respectively. This improves the overall readability of the test file as well as simplifies debugging.
Note that the last parameter in the tree_search() functiom is 'int insert' which when set, inserts the key if it is not found in the tree. Otherwise, the function returns NULL for such cases.
--- t/unit-tests/t-reftable-tree.c | 23 +++++++++++++++++++---- 1 file changed, 19 insertions(+), 4 deletions(-)
t/unit-tests/t-reftable-tree.c +19 -4
@@ -26,13 +26,12 @@ static void check_increasing(void *arg, void *key) c->last = key; } -static void t_tree (void ) +static void t_tree_search (void ) {struct tree_node *root =NULL ;void *values[11 ] = {0 };struct tree_node *nodes[11 ] = {0 };size_t i =1 ; -struct curry c = {0 }; do { nodes[i] = tree_search(values + i, &root, &t_compare, 1);
@@ -44,13 +43,29 @@ static void t_tree(void)check_pointer_eq (nodes[i],tree_search (values + i, &root, &t_compare,0 )); } -infix_walk (root, check_increasing, &c); +tree_free (root); +} + +static void t_infix_walk (void ) +{ +struct tree_node *root =NULL ; +void *values[11 ] = {0 }; +struct curry c = {0 }; +size_t i =1 ; + +do { +tree_search (values + i, &root, &t_compare,1 ); + i = (i *7 ) %11 ; + }while (i !=1 ); + +infix_walk (root, &check_increasing, &c);tree_free (root); }int cmd_main (int argc,const char *argv[]) { -TEST (t_tree (),"tree_search and infix_walk work" ); +TEST (t_tree_search (),"tree_search works" ); +TEST (t_infix_walk (),"infix_walk works" );return test_done (); }
Signature · 1 line
2.45.GIT
PATCH v4 4/5 t-reftable-tree: add test for non-existent key
In reply to Chandra PratapIn the current testing setup for tree_search(), the case for non-existent key is not exercised. Improve this by adding a test-case for the same.
--- t/unit-tests/t-reftable-tree.c | 1 + 1 file changed, 1 insertion(+)
t/unit-tests/t-reftable-tree.c +1 -0
@@ -43,6 +43,7 @@ static void t_tree_search(void)check_pointer_eq (nodes[i],tree_search (values + i, &root, &t_compare,0 )); } +check (!tree_search (values, &root, &test_compare,0 ));tree_free (root); }
Signature · 1 line
2.45.GIT
PATCH v4 5/5 t-reftable-tree: improve the test for infix_walk()
In reply to Chandra PratapIn the current testing setup for infix_walk(), the following properties of an infix traversal of a tree remain untested:
- every node of the tree must be visited
- every node must be visited exactly once
In fact, only the property 'traversal in increasing order' is tested. Modify test_infix_walk() to check for all the properties above.
This can be achieved by storing the nodes' keys linearly, in a nullified buffer, as we visit them and then checking the input keys against this buffer in increasing order. By checking that the element just after the last input key is 'NULL' in the output buffer, we ensure that every node is traversed exactly once.
--- t/unit-tests/t-reftable-tree.c | 22 +++++++++++++++------- 1 file changed, 15 insertions(+), 7 deletions(-)
t/unit-tests/t-reftable-tree.c +15 -7
@@ -15,15 +15,14 @@ static int t_compare(const void *a, const void *b) }struct curry { -void *last; +void **arr; +size_t len; }; -static void check_increasing (void *arg,void *key) +static void store (void *arg,void *key) {struct curry *c = arg; -if (c->last) - check_int(t_compare(c->last, key), <, 0); - c->last = key; + c->arr[c->len++] = key; }static void t_tree_search (void )
@@ -51,15 +50,24 @@ static void t_infix_walk(void) {struct tree_node *root =NULL ;void *values[11 ] = {0 }; -struct curry c = {0 }; +void *out[11 ] = {0 }; +struct curry c = { + .arr = (void **) &out, + };size_t i =1 ; +size_t count =0 ;do {tree_search (values + i, &root, &t_compare,1 ); i = (i *7 ) %11 ; + count++; }while (i !=1 ); -infix_walk (root, &check_increasing, &c); +infix_walk (root, &store, &c); +for (i =1 ; i <ARRAY_SIZE (values); i++) +check_pointer_eq (values + i, out[i -1 ]); +check (!out[i -1 ]); + check_int(c.len, ==, count);tree_free (root); }
Signature · 1 line
2.45.GIT
Quoted 1 line · Chandra Pratap
In the recent codebase update (commit 8bf6fbd, 2023-12-09), a new unit
Consistently refer to an existing commit with --format=reference.
$ git show -s --format=reference 8bf6fbd 8bf6fbd00d (Merge branch 'js/doc-unit-tests', 2023-12-09)
Quoted 2 lines
testing framework written entirely in C was introduced to the Git project aimed at simplifying testing and reducing test run times.
I doubt that the reason why "unit-tests" written entirely in C was introduced is because we wanted to simplify testing and to reduce test run times to begin with. The traditional tests to observe the effect visible to end-users by actually running commands that would be run by end-users and unit tests serve two separate purposes. The latter does not "simplify", or "reduce time"---you cannot write a test "entirely in C" to make sure, say, that "git push --force" allows a non-fast-forward update to happen using unit-test framework. The unit-tests cannot replace end-to-end tests. They are complementary.
The statement may need to be rethought.
Or just stop at saying something like
The reftable library comes with self tests, which are exercised as part of the usual end-to-end tests that are designed to observe the end-user visible effects of Git commands. What it exercises, however, is a better match to the unit-testing framework, merged at 8bf6fbd0 (Merge branch 'js/doc-unit-tests', 2023-12-09), that are designed to observe how low level implementation details, at the level of sequences of individual function calls, behave.
which already covers the next paragraph while at it.
Quoted 13 lines
Currently, tests for the reftable refs-backend are performed by a custom testing framework defined by reftable/test_framework.{c, h}. Port
reftable/tree_test.cto 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 <[email protected]>Mentored-by Christian Couder <[email protected]>Signed-off-by Chandra Pratap <[email protected]>
Quoted 5 lines
---
Changes in v4:
- Rename the tests to be in-line with unit-tests' standards
By the way, did you rebase the patches? On which commit is this iteration based? Judging from the second patch, it seems to assume that Makefile does not yet have t-reftable-record in it, and it applies cleanly to 'master' before 9118e46e (Merge branch 'cp/unit-test-reftable-record', 2024-07-15). Newer 'master' has textual conflicts (nothing that I cannot resolve, but it shows that apparently that anything newer than 9118e46e are not commits that you developed this series on).
Has this series even been compile-tested? I do not think that even the unit test added by this series has been run (or compiled).
$ make -j32 t/unit-tests/t-reftable-tree.o
GIT_VERSION = 2.46.0.rc0.27.g0c2075a7c5
* new build flags
CC t/unit-tests/t-reftable-tree.o
In file included from t/unit-tests/t-reftable-tree.c:9:
t/unit-tests/t-reftable-tree.c: In function ‘t_tree_search’:
t/unit-tests/t-reftable-tree.c:45:44: error: ‘test_compare’ undeclared (first use in this function); did you mean ‘t_compare’?
45 | check(!tree_search(values, &root, &test_compare, 0));
| ^~~~~~~~~~~~
t/unit-tests/test-lib.h:75:45: note: in definition of macro ‘check’
75 | check_bool_loc(TEST_LOCATION(), #x, x)
| ^
t/unit-tests/t-reftable-tree.c:45:44: note: each undeclared identifier is reported only once for each function it appears in
45 | check(!tree_search(values, &root, &test_compare, 0));
| ^~~~~~~~~~~~
t/unit-tests/test-lib.h:75:45: note: in definition of macro ‘check’
75 | check_bool_loc(TEST_LOCATION(), #x, x)
| ^
make: *** [Makefile:2754: t/unit-tests/t-reftable-tree.o] Error 1Let's concentrate on quality, not quantity; too many topics with the same prefix cp/unit-test* seem to be left unreviewed on the list.
In the meantime, I'll queue the following fix-up on top. In this codebase, it is preferred to write a pointer to a function whose name is "func" as just "func", not "&func".
t/unit-tests/t-reftable-tree.c | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-)
t/unit-tests/t-reftable-tree.c +4 -4
@@ -33,16 +33,16 @@ static void t_tree_search(void)size_t i =1 ;do { - nodes[i] =tree_search (values + i, &root, &t_compare,1 ); + nodes[i] =tree_search (values + i, &root, t_compare,1 ); i = (i *7 ) %11 ; }while (i !=1 );for (i =1 ; i <ARRAY_SIZE (nodes); i++) {check_pointer_eq (values + i, nodes[i]->key); -check_pointer_eq (nodes[i],tree_search (values + i, &root, &t_compare,0 )); +check_pointer_eq (nodes[i],tree_search (values + i, &root, t_compare,0 )); } -check (!tree_search (values, &root, &test_compare,0 )); +check (!tree_search (values, &root, t_compare,0 ));tree_free (root); }
@@ -58,7 +58,7 @@ static void t_infix_walk(void)size_t count =0 ;do { -tree_search (values + i, &root, &t_compare,1 ); +tree_search (values + i, &root, t_compare,1 ); i = (i *7 ) %11 ; count++; }while (i !=1 );
Signature · 1 line
2.46.0-rc0-137-g851401d64b
v5 cover t: port reftable/tree_test.c to the unit testing framework
In reply to Chandra PratapThe 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/tree_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.
---
Changes in v5:
- Rebase the branch on top of the latest master
- Add more explanation in the commit message of patch 2
- Refer to function pointers as 'func' and not '&func'
- Add comments and refactor the test in patch 2 for easier comprehension
CI/PR: https://github.com/gitgitgadget/git/pull/1740
Chandra Pratap(5):
reftable: remove unnecessary curly braces in reftable/tree.c
t: move reftable/tree_test.c to the unit testing framework
t-reftable-tree: split test_tree() into two sub-test
t-reftable-tree: add test for non-existent key
t-reftable-tree: improve the test for infix_walk()
Makefile | 2 +- reftable/reftable-tests.h | 1 - reftable/tree.c | 15 +++------- reftable/tree_test.c | 60 ---------------------- t/helper/test-reftable.c | 1 - t/unit-tests/t-reftable-tree.c | 83 +++++++++++++++++++++++++++++++++++++ 6 files changed, 89 insertions(+), 73 deletions(-)
Range-diff against v4:
<rebase commits>
1: 2be2a35b7f = 45: 1d637f7686 reftable: remove unnecessary curly braces in reftable/tree.c 2: de49698ea7 ! 46: 7401e2409f t: move reftable/tree_test.c to the unit testing framework
@@ Commit message
the unit testing framework instead of reftable's test framework and renaming the tests to align with unit-tests' standards.
+ Also add a comment to help understand the test routine.
+
+ Note that this commit mostly moves the test from reftable/ to + t/unit-tests/ and most of the refactoring is performed by the + trailing commits.
+
## Makefile ##
-@@ Makefile: UNIT_TEST_PROGRAMS += t-mem-pool
- UNIT_TEST_PROGRAMS += t-oidtree
+@@ Makefile: UNIT_TEST_PROGRAMS += t-oidtree
UNIT_TEST_PROGRAMS += t-prio-queue
UNIT_TEST_PROGRAMS += t-reftable-basics
+ UNIT_TEST_PROGRAMS += t-reftable-record
+UNIT_TEST_PROGRAMS += t-reftable-tree
UNIT_TEST_PROGRAMS += t-strbuf
UNIT_TEST_PROGRAMS += t-strcmp-offset
UNIT_TEST_PROGRAMS += t-strvec
-@@ Makefile: REFTABLE_TEST_OBJS += reftable/record_test.o
+@@ Makefile: 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
@@ reftable/tree_test.c (deleted)
## t/helper/test-reftable.c ##
@@ t/helper/test-reftable.c: int cmd__reftable(int argc, const char **argv)
+ {
/* test from simple to complex. */
- record_test_main(argc, argv);
block_test_main(argc, argv);
- tree_test_main(argc, argv);
pq_test_main(argc, argv);
@@ t/unit-tests/t-reftable-tree.c (new)
+ size_t i = 1;
+ struct curry c = { 0 };
+
++ /* pseudo-randomly insert the pointers for elements between
++ * values[1] and values[10] (included) in the tree.
++ */
+ do {
-+ nodes[i] = tree_search(values + i, &root, &t_compare, 1);
++ nodes[i] = tree_search(&values[i], &root, &t_compare, 1);
+ i = (i * 7) % 11;
+ } while (i != 1);
+
+ for (i = 1; i < ARRAY_SIZE(nodes); i++) {
-+ check_pointer_eq(values + i, nodes[i]->key);
-+ check_pointer_eq(nodes[i], tree_search(values + i, &root, &t_compare, 0));
++ check_pointer_eq(&values[i], nodes[i]->key);
++ check_pointer_eq(nodes[i], tree_search(&values[i], &root, &t_compare, 0));
+ }
+
+ infix_walk(root, check_increasing, &c); 3: c733776054 ! 47: 59d5c17d5e t-reftable-tree: split test_tree() into two sub-test functions
@@ Commit message
'int insert' which when set, inserts the key if it is not found
in the tree. Otherwise, the function returns NULL for such cases.
+ While at it, use 'func' to pass function pointers and not '&func'.
+
@@ t/unit-tests/t-reftable-tree.c: static void check_increasing(void *arg, void *ke
size_t i = 1;
- struct curry c = { 0 };
- do {
- nodes[i] = tree_search(values + i, &root, &t_compare, 1);
+ /* pseudo-randomly insert the pointers for elements between
+ * values[1] and values[10] (included) in the tree.
@@ t/unit-tests/t-reftable-tree.c: static void t_tree(void)
- check_pointer_eq(nodes[i], tree_search(values + i, &root, &t_compare, 0));
+ check_pointer_eq(nodes[i], tree_search(&values[i], &root, &t_compare, 0));
}
- infix_walk(root, check_increasing, &c);
@@ t/unit-tests/t-reftable-tree.c: static void t_tree(void)
+ size_t i = 1;
+
+ do {
-+ tree_search(values + i, &root, &t_compare, 1);
++ tree_search(&values[i], &root, t_compare, 1);
+ i = (i * 7) % 11;
+ } while (i != 1);
+
4: f1a9325bb3 < -: ---------- t-reftable-tree: add test for non-existent key
-: ---------- > 48: c1ce79916b t-reftable-tree: add test for non-existent key
5: c6b7a3d646 ! 49: d1a5ced526 t-reftable-tree: improve the test for infix_walk()
@@ t/unit-tests/t-reftable-tree.c: static void t_infix_walk(void)
+ size_t count = 0;
do {
- tree_search(values + i, &root, &t_compare, 1);
+ tree_search(&values[i], &root, t_compare, 1);
i = (i * 7) % 11;
+ count++;
} while (i != 1);
@@ t/unit-tests/t-reftable-tree.c: static void t_infix_walk(void)
- infix_walk(root, &check_increasing, &c);
+ infix_walk(root, &store, &c);
+ for (i = 1; i < ARRAY_SIZE(values); i++)
-+ check_pointer_eq(values + i, out[i - 1]);
++ check_pointer_eq(&values[i], out[i - 1]);
+ check(!out[i - 1]);
+ check_int(c.len, ==, count);
tree_free(root);PATCH v5 1/5 reftable: remove unnecessary curly braces in reftable/tree.c
According to Documentation/CodingGuidelines, single-line control-flow statements must omit curly braces (except for some special cases). Make reftable/tree.c adhere to this guideline.
--- reftable/tree.c | 15 +++++---------- 1 file changed, 5 insertions(+), 10 deletions(-)
reftable/tree.c +5 -10
@@ -39,25 +39,20 @@ struct tree_node *tree_search(void *key, struct tree_node **rootp,void infix_walk (struct tree_node *t,void (*action)(void *arg,void *key),void *arg) { -if (t->left) { +if (t->left)infix_walk (t->left, action, arg); - }action (arg, t->key); -if (t->right) { +if (t->right)infix_walk (t->right, action, arg); - } }void tree_free (struct tree_node *t) { -if (!t) { +if (!t)return ; - } -if (t->left) { +if (t->left)tree_free (t->left); - } -if (t->right) { +if (t->right)tree_free (t->right); - }reftable_free (t); }
Signature · 1 line
2.45.GIT
PATCH v5 2/5 t: move reftable/tree_test.c to the unit testing framework
In reply to Chandra Pratapreftable/tree_test.c exercises the functions defined in reftable/tree.{c, h}. Migrate reftable/tree_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.
Also add a comment to help understand the test routine.
Note that this commit mostly moves the test from reftable/ to t/unit-tests/ and most of the refactoring is performed by the trailing commits.
--- Makefile | 2 +- reftable/reftable-tests.h | 1 - reftable/tree_test.c | 60 ---------------------------------- t/helper/test-reftable.c | 1 - t/unit-tests/t-reftable-tree.c | 59 +++++++++++++++++++++++++++++++++ 5 files changed, 60 insertions(+), 63 deletions(-) delete mode 100644 reftable/tree_test.c create mode 100644 t/unit-tests/t-reftable-tree.c
Makefile +1 -1
@@ -1341,6 +1341,7 @@ UNIT_TEST_PROGRAMS += t-oidtree UNIT_TEST_PROGRAMS += t-prio-queue UNIT_TEST_PROGRAMS += t-reftable-basics UNIT_TEST_PROGRAMS += t-reftable-record +UNIT_TEST_PROGRAMS += t-reftable-tree UNIT_TEST_PROGRAMS += t-strbuf UNIT_TEST_PROGRAMS += t-strcmp-offset UNIT_TEST_PROGRAMS += t-strvec
@@ -2685,7 +2686,6 @@ 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 -REFTABLE_TEST_OBJS += reftable/tree_test.o TEST_OBJS := $(patsubst %$X,%.o,$(TEST_PROGRAMS)) $(patsubst %,t/helper/%,$(TEST_BUILTINS_OBJS))
reftable/reftable-tests.h +0 -1
@@ -16,7 +16,6 @@ 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); -int tree_test_main (int argc,const char **argv);int reftable_dump_main (int argc,char *const *argv);#endif
reftable/tree_test.c deleted +0 -60
60 lines not on this page · raw message
t/helper/test-reftable.c +0 -1
@@ -6,7 +6,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);
t/unit-tests/t-reftable-tree.c new file +59 -0
59 lines not on this page · raw message
Signature · 1 line
2.45.GIT
Re: [PATCH v5 2/5] t: move reftable/tree_test.c to the unit testing framework
Quoted 8 lines · Chandra Pratap
reftable/tree_test.cexercises the functions defined in reftable/tree.{c, h}. Migratereftable/tree_test.cto 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.Also add a comment to help understand the test routine.
Quoted 8 lines
Note that this commit mostly moves the test from reftable/ to t/unit-tests/ and most of the refactoring is performed by the trailing commits.
Mentored-by Patrick Steinhardt <[email protected]>Mentored-by Christian Couder <[email protected]>Signed-off-by Chandra Pratap <[email protected]>---
Looking good.
"git show -M30" matches the moved file up correctly and makes it easy to see that there is no serious changes snuck in (please do not take this as a suggestion to run format-patch with -M30---I am just saying that it was a good way to give an extra validation).
Thanks.
Re: [PATCH v5 2/5] t: move reftable/tree_test.c to the unit testing framework
In reply to Chandra Pratapt/unit-tests/t-reftable-tree.c line 39
Quoted 3 lines · Chandra Pratap
t/unit-tests/t-reftable-tree.c new file +3
-0+/* pseudo-randomly insert the pointers for elements between +* values[1] and values[10] (included) in the tree. +*/
Style?
Re: [PATCH v5 2/5] t: move reftable/tree_test.c to the unit testing framework
Quoted 7 lines · Junio C Hamano
Review
Quoted 3 lines · Chandra Pratap
(quoted diff) +3
-0+ /* pseudo-randomly insert the pointers for elements between + * values[1] and values[10] (included) in the tree. + */Style?
t/unit-tests/t-reftable-tree.c +3 -2
@@ -32,8 +32,9 @@ static void t_tree_search(void)struct tree_node *nodes[11 ] = {0 };size_t i =1 ; -/* pseudo-randomly insert the pointers for elements between -* values[1] and values[10] (included) in the tree. +/* +* Pseudo-randomly insert the pointers for elements between +* values[1] and values[10] (inclusive) in the tree. */ do { nodes[i] = tree_search(&values[i], &root, &t_compare, 1);
Signature · 1 line
2.46.0-rc1-48-g0900f1888e
PATCH v5 3/5 t-reftable-tree: split test_tree() into two sub-test functions
In reply to Chandra PratapIn the current testing setup, tests for both tree_search() and infix_walk() defined by reftable/tree.{c, h} are performed by a single test function, test_tree(). Split tree_test() into test_tree_search() and test_infix_walk() responsible for independently testing tree_search() and infix_walk() respectively. This improves the overall readability of the test file as well as simplifies debugging.
Note that the last parameter in the tree_search() functiom is 'int insert' which when set, inserts the key if it is not found in the tree. Otherwise, the function returns NULL for such cases.
While at it, use 'func' to pass function pointers and not '&func'.
--- t/unit-tests/t-reftable-tree.c | 23 +++++++++++++++++++---- 1 file changed, 19 insertions(+), 4 deletions(-)
t/unit-tests/t-reftable-tree.c +19 -4
@@ -26,13 +26,12 @@ static void check_increasing(void *arg, void *key) c->last = key; } -static void t_tree (void ) +static void t_tree_search (void ) {struct tree_node *root =NULL ;void *values[11 ] = {0 };struct tree_node *nodes[11 ] = {0 };size_t i =1 ; -struct curry c = {0 };/* pseudo-randomly insert the pointers for elements between * values[1] and values[10] (included) in the tree.
@@ -47,13 +46,29 @@ static void t_tree(void)check_pointer_eq (nodes[i],tree_search (&values[i], &root, &t_compare,0 )); } -infix_walk (root, check_increasing, &c); +tree_free (root); +} + +static void t_infix_walk (void ) +{ +struct tree_node *root =NULL ; +void *values[11 ] = {0 }; +struct curry c = {0 }; +size_t i =1 ; + +do { +tree_search (&values[i], &root, t_compare,1 ); + i = (i *7 ) %11 ; + }while (i !=1 ); + +infix_walk (root, &check_increasing, &c);tree_free (root); }int cmd_main (int argc,const char *argv[]) { -TEST (t_tree (),"tree_search and infix_walk work" ); +TEST (t_tree_search (),"tree_search works" ); +TEST (t_infix_walk (),"infix_walk works" );return test_done (); }
Signature · 1 line
2.45.GIT
PATCH v5 4/5 t-reftable-tree: add test for non-existent key
In reply to Chandra PratapIn the current testing setup for tree_search(), the case for non-existent key is not exercised. Improve this by adding a test-case for the same.
--- t/unit-tests/t-reftable-tree.c | 1 + 1 file changed, 1 insertion(+)
t/unit-tests/t-reftable-tree.c +1 -0
@@ -46,6 +46,7 @@ static void t_tree_search(void)check_pointer_eq (nodes[i],tree_search (&values[i], &root, &t_compare,0 )); } +check (!tree_search (values, &root, t_compare,0 ));tree_free (root); }
Signature · 1 line
2.45.GIT
PATCH v5 5/5 t-reftable-tree: improve the test for infix_walk()
In reply to Chandra PratapIn the current testing setup for infix_walk(), the following properties of an infix traversal of a tree remain untested:
- every node of the tree must be visited
- every node must be visited exactly once
In fact, only the property 'traversal in increasing order' is tested. Modify test_infix_walk() to check for all the properties above.
This can be achieved by storing the nodes' keys linearly, in a nullified buffer, as we visit them and then checking the input keys against this buffer in increasing order. By checking that the element just after the last input key is 'NULL' in the output buffer, we ensure that every node is traversed exactly once.
--- t/unit-tests/t-reftable-tree.c | 22 +++++++++++++++------- 1 file changed, 15 insertions(+), 7 deletions(-)
t/unit-tests/t-reftable-tree.c +15 -7
@@ -15,15 +15,14 @@ static int t_compare(const void *a, const void *b) }struct curry { -void *last; +void **arr; +size_t len; }; -static void check_increasing (void *arg,void *key) +static void store (void *arg,void *key) {struct curry *c = arg; -if (c->last) - check_int(t_compare(c->last, key), <, 0); - c->last = key; + c->arr[c->len++] = key; }static void t_tree_search (void )
@@ -54,15 +53,24 @@ static void t_infix_walk(void) {struct tree_node *root =NULL ;void *values[11 ] = {0 }; -struct curry c = {0 }; +void *out[11 ] = {0 }; +struct curry c = { + .arr = (void **) &out, + };size_t i =1 ; +size_t count =0 ;do {tree_search (&values[i], &root, t_compare,1 ); i = (i *7 ) %11 ; + count++; }while (i !=1 ); -infix_walk (root, &check_increasing, &c); +infix_walk (root, &store, &c); +for (i =1 ; i <ARRAY_SIZE (values); i++) +check_pointer_eq (&values[i], out[i -1 ]); +check (!out[i -1 ]); + check_int(c.len, ==, count);tree_free (root); }
Signature · 1 line
2.45.GIT
A reminder for reviews/acks.
Quoted 1 line · Chandra Pratap
A reminder for reviews/acks.
There was one style nit from Junio already that you should probably address. Other than that I didn't really have anything else to add to this series.
Patrick
v6 cover t: port reftable/tree_test.c to the unit testing framework
In reply to Chandra PratapThe 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/tree_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.
---
Changes in v6:
- Fix a style issue in a comment introduced in patch 3
CI/PR: https://github.com/gitgitgadget/git/pull/1740
Chandra Pratap(5):
reftable: remove unnecessary curly braces in reftable/tree.c
t: move reftable/tree_test.c to the unit testing framework
t-reftable-tree: split test_tree() into two sub-test
t-reftable-tree: add test for non-existent key
t-reftable-tree: improve the test for infix_walk()
Makefile | 2 +- reftable/reftable-tests.h | 1 - reftable/tree.c | 15 +++------- reftable/tree_test.c | 60 ---------------------- t/helper/test-reftable.c | 1 - t/unit-tests/t-reftable-tree.c | 83 +++++++++++++++++++++++++++++++++++++ 6 files changed, 89 insertions(+), 73 deletions(-)
Range-diff against v5:
1: 59d5c17d5e ! 1: 501ea6c05d t-reftable-tree: split test_tree() into two sub-test functions
@@ t/unit-tests/t-reftable-tree.c: static void check_increasing(void *arg, void *ke
size_t i = 1;
- struct curry c = { 0 };
- /* pseudo-randomly insert the pointers for elements between
- * values[1] and values[10] (included) in the tree.
+- /* pseudo-randomly insert the pointers for elements between
+- * values[1] and values[10] (included) in the tree.
++ /* Pseudo-randomly insert the pointers for elements between
++ * values[1] and values[10] (inclusive) in the tree.
+ */
+ do {
+ nodes[i] = tree_search(&values[i], &root, &t_compare, 1);
@@ t/unit-tests/t-reftable-tree.c: static void t_tree(void)
check_pointer_eq(nodes[i], tree_search(&values[i], &root, &t_compare, 0));
}
2: c1ce79916b = 2: ecadc1833e t-reftable-tree: add test for non-existent key 3: d1a5ced526 = 3: cda7509281 t-reftable-tree: improve the test for infix_walk()
PATCH v6 1/5 reftable: remove unnecessary curly braces in reftable/tree.c
According to Documentation/CodingGuidelines, single-line control-flow statements must omit curly braces (except for some special cases). Make reftable/tree.c adhere to this guideline.
--- reftable/tree.c | 15 +++++---------- 1 file changed, 5 insertions(+), 10 deletions(-)
reftable/tree.c +5 -10
@@ -39,25 +39,20 @@ struct tree_node *tree_search(void *key, struct tree_node **rootp,void infix_walk (struct tree_node *t,void (*action)(void *arg,void *key),void *arg) { -if (t->left) { +if (t->left)infix_walk (t->left, action, arg); - }action (arg, t->key); -if (t->right) { +if (t->right)infix_walk (t->right, action, arg); - } }void tree_free (struct tree_node *t) { -if (!t) { +if (!t)return ; - } -if (t->left) { +if (t->left)tree_free (t->left); - } -if (t->right) { +if (t->right)tree_free (t->right); - }reftable_free (t); }
Signature · 1 line
2.45.GIT
PATCH v6 2/5 t: move reftable/tree_test.c to the unit testing framework
In reply to Chandra Pratapreftable/tree_test.c exercises the functions defined in reftable/tree.{c, h}. Migrate reftable/tree_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.
Also add a comment to help understand the test routine.
Note that this commit mostly moves the test from reftable/ to t/unit-tests/ and most of the refactoring is performed by the trailing commits.
--- Makefile | 2 +- reftable/reftable-tests.h | 1 - reftable/tree_test.c | 60 ---------------------------------- t/helper/test-reftable.c | 1 - t/unit-tests/t-reftable-tree.c | 59 +++++++++++++++++++++++++++++++++ 5 files changed, 60 insertions(+), 63 deletions(-) delete mode 100644 reftable/tree_test.c create mode 100644 t/unit-tests/t-reftable-tree.c
Makefile +1 -1
@@ -1342,6 +1342,7 @@ UNIT_TEST_PROGRAMS += t-prio-queue UNIT_TEST_PROGRAMS += t-reftable-basics UNIT_TEST_PROGRAMS += t-reftable-merged UNIT_TEST_PROGRAMS += t-reftable-record +UNIT_TEST_PROGRAMS += t-reftable-tree UNIT_TEST_PROGRAMS += t-strbuf UNIT_TEST_PROGRAMS += t-strcmp-offset UNIT_TEST_PROGRAMS += t-strvec
@@ -2685,7 +2686,6 @@ 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 -REFTABLE_TEST_OBJS += reftable/tree_test.o TEST_OBJS := $(patsubst %$X,%.o,$(TEST_PROGRAMS)) $(patsubst %,t/helper/%,$(TEST_BUILTINS_OBJS))
reftable/reftable-tests.h +0 -1
@@ -15,7 +15,6 @@ 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); -int tree_test_main (int argc,const char **argv);int reftable_dump_main (int argc,char *const *argv);#endif
reftable/tree_test.c deleted +0 -60
60 lines not on this page · raw message
t/helper/test-reftable.c +0 -1
@@ -6,7 +6,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);stack_test_main (argc, argv);
t/unit-tests/t-reftable-tree.c new file +59 -0
59 lines not on this page · raw message
Signature · 1 line
2.45.GIT
PATCH v6 3/5 t-reftable-tree: split test_tree() into two sub-test functions
In reply to Chandra PratapIn the current testing setup, tests for both tree_search() and infix_walk() defined by reftable/tree.{c, h} are performed by a single test function, test_tree(). Split tree_test() into test_tree_search() and test_infix_walk() responsible for independently testing tree_search() and infix_walk() respectively. This improves the overall readability of the test file as well as simplifies debugging.
Note that the last parameter in the tree_search() functiom is 'int insert' which when set, inserts the key if it is not found in the tree. Otherwise, the function returns NULL for such cases.
While at it, use 'func' to pass function pointers and not '&func'.
--- t/unit-tests/t-reftable-tree.c | 27 +++++++++++++++++++++------ 1 file changed, 21 insertions(+), 6 deletions(-)
t/unit-tests/t-reftable-tree.c +21 -6
@@ -26,16 +26,15 @@ static void check_increasing(void *arg, void *key) c->last = key; } -static void t_tree (void ) +static void t_tree_search (void ) {struct tree_node *root =NULL ;void *values[11 ] = {0 };struct tree_node *nodes[11 ] = {0 };size_t i =1 ; -struct curry c = {0 }; -/* pseudo-randomly insert the pointers for elements between -* values[1] and values[10] (included) in the tree. +/* Pseudo-randomly insert the pointers for elements between +* values[1] and values[10] (inclusive) in the tree. */ do { nodes[i] = tree_search(&values[i], &root, &t_compare, 1);
@@ -47,13 +46,29 @@ static void t_tree(void)check_pointer_eq (nodes[i],tree_search (&values[i], &root, &t_compare,0 )); } -infix_walk (root, check_increasing, &c); +tree_free (root); +} + +static void t_infix_walk (void ) +{ +struct tree_node *root =NULL ; +void *values[11 ] = {0 }; +struct curry c = {0 }; +size_t i =1 ; + +do { +tree_search (&values[i], &root, t_compare,1 ); + i = (i *7 ) %11 ; + }while (i !=1 ); + +infix_walk (root, &check_increasing, &c);tree_free (root); }int cmd_main (int argc,const char *argv[]) { -TEST (t_tree (),"tree_search and infix_walk work" ); +TEST (t_tree_search (),"tree_search works" ); +TEST (t_infix_walk (),"infix_walk works" );return test_done (); }
Signature · 1 line
2.45.GIT
Re: [PATCH v6 3/5] t-reftable-tree: split test_tree() into two sub-test functions
t/unit-tests/t-reftable-tree.c static void check_increasing(void *arg, void *key) · line 38
Quoted 5 lines · Chandra Pratap
t/unit-tests/t-reftable-tree.c +2
-2-/* pseudo-randomly insert the pointers for elements between -* values[1] and values[10] (included) in the tree. +/* Pseudo-randomly insert the pointers for elements between +* values[1] and values[10] (inclusive) in the tree. */
If you are "fixing" the comment, let's fix its style as well.
/*
* Our multi-line comments begin with slash-asterisk, and
* end with asterisk-slash, on their own line.
*/PATCH v6 4/5 t-reftable-tree: add test for non-existent key
In reply to Chandra PratapIn the current testing setup for tree_search(), the case for non-existent key is not exercised. Improve this by adding a test-case for the same.
--- t/unit-tests/t-reftable-tree.c | 1 + 1 file changed, 1 insertion(+)
t/unit-tests/t-reftable-tree.c +1 -0
@@ -46,6 +46,7 @@ static void t_tree_search(void)check_pointer_eq (nodes[i],tree_search (&values[i], &root, &t_compare,0 )); } +check (!tree_search (values, &root, t_compare,0 ));tree_free (root); }
Signature · 1 line
2.45.GIT
PATCH v6 5/5 t-reftable-tree: improve the test for infix_walk()
In reply to Chandra PratapIn the current testing setup for infix_walk(), the following properties of an infix traversal of a tree remain untested:
- every node of the tree must be visited
- every node must be visited exactly once
In fact, only the property 'traversal in increasing order' is tested. Modify test_infix_walk() to check for all the properties above.
This can be achieved by storing the nodes' keys linearly, in a nullified buffer, as we visit them and then checking the input keys against this buffer in increasing order. By checking that the element just after the last input key is 'NULL' in the output buffer, we ensure that every node is traversed exactly once.
--- t/unit-tests/t-reftable-tree.c | 22 +++++++++++++++------- 1 file changed, 15 insertions(+), 7 deletions(-)
t/unit-tests/t-reftable-tree.c +15 -7
@@ -15,15 +15,14 @@ static int t_compare(const void *a, const void *b) }struct curry { -void *last; +void **arr; +size_t len; }; -static void check_increasing (void *arg,void *key) +static void store (void *arg,void *key) {struct curry *c = arg; -if (c->last) - check_int(t_compare(c->last, key), <, 0); - c->last = key; + c->arr[c->len++] = key; }static void t_tree_search (void )
@@ -54,15 +53,24 @@ static void t_infix_walk(void) {struct tree_node *root =NULL ;void *values[11 ] = {0 }; -struct curry c = {0 }; +void *out[11 ] = {0 }; +struct curry c = { + .arr = (void **) &out, + };size_t i =1 ; +size_t count =0 ;do {tree_search (&values[i], &root, t_compare,1 ); i = (i *7 ) %11 ; + count++; }while (i !=1 ); -infix_walk (root, &check_increasing, &c); +infix_walk (root, &store, &c); +for (i =1 ; i <ARRAY_SIZE (values); i++) +check_pointer_eq (&values[i], out[i -1 ]); +check (!out[i -1 ]); + check_int(c.len, ==, count);tree_free (root); }
Signature · 1 line
2.45.GIT
v7 cover t: port reftable/tree_test.c to the unit testing framework
In reply to Chandra PratapThe 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/tree_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.
---
Changes in v7:
- Fix style issues in a comment introduced in patch 3 of the previous series
CI/PR: https://github.com/gitgitgadget/git/pull/1740
Chandra Pratap(5):
reftable: remove unnecessary curly braces in reftable/tree.c
t: move reftable/tree_test.c to the unit testing framework
t-reftable-tree: split test_tree() into two sub-test
t-reftable-tree: add test for non-existent key
t-reftable-tree: improve the test for infix_walk()
Makefile | 2 +- reftable/reftable-tests.h | 1 - reftable/tree.c | 15 +++------- reftable/tree_test.c | 60 ---------------------- t/helper/test-reftable.c | 1 - t/unit-tests/t-reftable-tree.c | 83 +++++++++++++++++++++++++++++++++++++ 6 files changed, 89 insertions(+), 73 deletions(-)
Range-diff against v6:
1: d4a45e602c = 1: d738bf57e2 reftable: remove unnecessary curly braces in reftable/tree.c
2: 9148e740e8 ! 2: f090ace685 t: move reftable/tree_test.c to the unit testing framework
@@ t/unit-tests/t-reftable-tree.c (new)
+ size_t i = 1;
+ struct curry c = { 0 };
+
-+ /* pseudo-randomly insert the pointers for elements between
-+ * values[1] and values[10] (included) in the tree.
++ /*
++ * Pseudo-randomly insert the pointers for elements between
++ * values[1] and values[10] (inclusive) in the tree.
+ */
+ do {
+ nodes[i] = tree_search(&values[i], &root, &t_compare, 1);3: f73ad11238 ! 3: 22256e77b3 t-reftable-tree: split test_tree() into two sub-test functions
@@ t/unit-tests/t-reftable-tree.c: static void check_increasing(void *arg, void *ke
size_t i = 1;
- struct curry c = { 0 };
-- /* pseudo-randomly insert the pointers for elements between
-- * values[1] and values[10] (included) in the tree.
-+ /* Pseudo-randomly insert the pointers for elements between
-+ * values[1] and values[10] (inclusive) in the tree.
- */
- do {
- nodes[i] = tree_search(&values[i], &root, &t_compare, 1);
+ /*
+ * Pseudo-randomly insert the pointers for elements between
@@ t/unit-tests/t-reftable-tree.c: static void t_tree(void)
check_pointer_eq(nodes[i], tree_search(&values[i], &root, &t_compare, 0));
}
4: edb02d2e84 = 4: 0d04daad28 t-reftable-tree: add test for non-existent key 5: 6aecd4e374 = 5: 80d4aa2a66 t-reftable-tree: improve the test for infix_walk()
PATCH v7 1/5 reftable: remove unnecessary curly braces in reftable/tree.c
According to Documentation/CodingGuidelines, single-line control-flow statements must omit curly braces (except for some special cases). Make reftable/tree.c adhere to this guideline.
--- reftable/tree.c | 15 +++++---------- 1 file changed, 5 insertions(+), 10 deletions(-)
reftable/tree.c +5 -10
@@ -39,25 +39,20 @@ struct tree_node *tree_search(void *key, struct tree_node **rootp,void infix_walk (struct tree_node *t,void (*action)(void *arg,void *key),void *arg) { -if (t->left) { +if (t->left)infix_walk (t->left, action, arg); - }action (arg, t->key); -if (t->right) { +if (t->right)infix_walk (t->right, action, arg); - } }void tree_free (struct tree_node *t) { -if (!t) { +if (!t)return ; - } -if (t->left) { +if (t->left)tree_free (t->left); - } -if (t->right) { +if (t->right)tree_free (t->right); - }reftable_free (t); }
Signature · 1 line
2.45.GIT
PATCH v7 2/5 t: move reftable/tree_test.c to the unit testing framework
In reply to Chandra Pratapreftable/tree_test.c exercises the functions defined in reftable/tree.{c, h}. Migrate reftable/tree_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.
Also add a comment to help understand the test routine.
Note that this commit mostly moves the test from reftable/ to t/unit-tests/ and most of the refactoring is performed by the trailing commits.
--- Makefile | 2 +- reftable/reftable-tests.h | 1 - reftable/tree_test.c | 60 ---------------------------------- t/helper/test-reftable.c | 1 - t/unit-tests/t-reftable-tree.c | 60 ++++++++++++++++++++++++++++++++++ 5 files changed, 61 insertions(+), 63 deletions(-) delete mode 100644 reftable/tree_test.c create mode 100644 t/unit-tests/t-reftable-tree.c
Makefile +1 -1
@@ -1342,6 +1342,7 @@ UNIT_TEST_PROGRAMS += t-prio-queue UNIT_TEST_PROGRAMS += t-reftable-basics UNIT_TEST_PROGRAMS += t-reftable-merged UNIT_TEST_PROGRAMS += t-reftable-record +UNIT_TEST_PROGRAMS += t-reftable-tree UNIT_TEST_PROGRAMS += t-strbuf UNIT_TEST_PROGRAMS += t-strcmp-offset UNIT_TEST_PROGRAMS += t-strvec
@@ -2685,7 +2686,6 @@ 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 -REFTABLE_TEST_OBJS += reftable/tree_test.o TEST_OBJS := $(patsubst %$X,%.o,$(TEST_PROGRAMS)) $(patsubst %,t/helper/%,$(TEST_BUILTINS_OBJS))
reftable/reftable-tests.h +0 -1
@@ -15,7 +15,6 @@ 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); -int tree_test_main (int argc,const char **argv);int reftable_dump_main (int argc,char *const *argv);#endif
reftable/tree_test.c deleted +0 -60
60 lines not on this page · raw message
t/helper/test-reftable.c +0 -1
@@ -6,7 +6,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);stack_test_main (argc, argv);
t/unit-tests/t-reftable-tree.c new file +60 -0
60 lines not on this page · raw message
Signature · 1 line
2.45.GIT
PATCH v7 3/5 t-reftable-tree: split test_tree() into two sub-test functions
In reply to Chandra PratapIn the current testing setup, tests for both tree_search() and infix_walk() defined by reftable/tree.{c, h} are performed by a single test function, test_tree(). Split tree_test() into test_tree_search() and test_infix_walk() responsible for independently testing tree_search() and infix_walk() respectively. This improves the overall readability of the test file as well as simplifies debugging.
Note that the last parameter in the tree_search() functiom is 'int insert' which when set, inserts the key if it is not found in the tree. Otherwise, the function returns NULL for such cases.
While at it, use 'func' to pass function pointers and not '&func'.
--- t/unit-tests/t-reftable-tree.c | 23 +++++++++++++++++++---- 1 file changed, 19 insertions(+), 4 deletions(-)
t/unit-tests/t-reftable-tree.c +19 -4
@@ -26,13 +26,12 @@ static void check_increasing(void *arg, void *key) c->last = key; } -static void t_tree (void ) +static void t_tree_search (void ) {struct tree_node *root =NULL ;void *values[11 ] = {0 };struct tree_node *nodes[11 ] = {0 };size_t i =1 ; -struct curry c = {0 };/* * Pseudo-randomly insert the pointers for elements between
@@ -48,13 +47,29 @@ static void t_tree(void)check_pointer_eq (nodes[i],tree_search (&values[i], &root, &t_compare,0 )); } -infix_walk (root, check_increasing, &c); +tree_free (root); +} + +static void t_infix_walk (void ) +{ +struct tree_node *root =NULL ; +void *values[11 ] = {0 }; +struct curry c = {0 }; +size_t i =1 ; + +do { +tree_search (&values[i], &root, t_compare,1 ); + i = (i *7 ) %11 ; + }while (i !=1 ); + +infix_walk (root, &check_increasing, &c);tree_free (root); }int cmd_main (int argc,const char *argv[]) { -TEST (t_tree (),"tree_search and infix_walk work" ); +TEST (t_tree_search (),"tree_search works" ); +TEST (t_infix_walk (),"infix_walk works" );return test_done (); }
Signature · 1 line
2.45.GIT
PATCH v7 4/5 t-reftable-tree: add test for non-existent key
In reply to Chandra PratapIn the current testing setup for tree_search(), the case for non-existent key is not exercised. Improve this by adding a test-case for the same.
--- t/unit-tests/t-reftable-tree.c | 1 + 1 file changed, 1 insertion(+)
t/unit-tests/t-reftable-tree.c +1 -0
@@ -47,6 +47,7 @@ static void t_tree_search(void)check_pointer_eq (nodes[i],tree_search (&values[i], &root, &t_compare,0 )); } +check (!tree_search (values, &root, t_compare,0 ));tree_free (root); }
Signature · 1 line
2.45.GIT
PATCH v7 5/5 t-reftable-tree: improve the test for infix_walk()
In reply to Chandra PratapIn the current testing setup for infix_walk(), the following properties of an infix traversal of a tree remain untested:
- every node of the tree must be visited
- every node must be visited exactly once
In fact, only the property 'traversal in increasing order' is tested. Modify test_infix_walk() to check for all the properties above.
This can be achieved by storing the nodes' keys linearly, in a nullified buffer, as we visit them and then checking the input keys against this buffer in increasing order. By checking that the element just after the last input key is 'NULL' in the output buffer, we ensure that every node is traversed exactly once.
--- t/unit-tests/t-reftable-tree.c | 22 +++++++++++++++------- 1 file changed, 15 insertions(+), 7 deletions(-)
t/unit-tests/t-reftable-tree.c +15 -7
@@ -15,15 +15,14 @@ static int t_compare(const void *a, const void *b) }struct curry { -void *last; +void **arr; +size_t len; }; -static void check_increasing (void *arg,void *key) +static void store (void *arg,void *key) {struct curry *c = arg; -if (c->last) - check_int(t_compare(c->last, key), <, 0); - c->last = key; + c->arr[c->len++] = key; }static void t_tree_search (void )
@@ -55,15 +54,24 @@ static void t_infix_walk(void) {struct tree_node *root =NULL ;void *values[11 ] = {0 }; -struct curry c = {0 }; +void *out[11 ] = {0 }; +struct curry c = { + .arr = (void **) &out, + };size_t i =1 ; +size_t count =0 ;do {tree_search (&values[i], &root, t_compare,1 ); i = (i *7 ) %11 ; + count++; }while (i !=1 ); -infix_walk (root, &check_increasing, &c); +infix_walk (root, &store, &c); +for (i =1 ; i <ARRAY_SIZE (values); i++) +check_pointer_eq (&values[i], out[i -1 ]); +check (!out[i -1 ]); + check_int(c.len, ==, count);tree_free (root); }
Signature · 1 line
2.45.GIT
Quoted 15 lines · 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/tree_test.cto 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.
Quoted 3 lines
Mentored-by Patrick Steinhardt <[email protected]>Mentored-by Christian Couder <[email protected]>Signed-off-by Chandra Pratap <[email protected]>
Only a single change compared to v6, addressing the only feedback on that version. So this looks good to me, thanks!
Patrick
Quoted 16 lines · Patrick Steinhardt
Quoted 15 lines · 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/tree_test.cto 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.
Quoted 6 lines
Quoted 3 lines
Mentored-by Patrick Steinhardt <[email protected]>Mentored-by Christian Couder <[email protected]>Signed-off-by Chandra Pratap <[email protected]>Only a single change compared to v6, addressing the only feedback on that version. So this looks good to me, thanks!
FWIW, I didn't have other feedback not because I found the rest perfect, but because I didn't read the series myself carefully, hoping others are sharing the burden.
Thanks.
Quoted 22 lines · Junio C Hamano
Quoted 20 lines · Patrick Steinhardt
Quoted 18 lines · 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/tree_test.cto 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 <[email protected]>Mentored-by Christian Couder <[email protected]>Signed-off-by Chandra Pratap <[email protected]>
Quoted 6 lines
Quoted 2 lines
Only a single change compared to v6, addressing the only feedback on that version. So this looks good to me, thanks!
FWIW, I didn't have other feedback not because I found the rest perfect, but because I didn't read the series myself carefully, hoping others are sharing the burden.
Oh, yes. I didn't mean to say that I relied on your feedback being addressed exclusively. I already reviewed v5/v6 of this patch series and found it to be good, and given that there was only a single change proposed by you that I'm happy with it translates into me being in favor of v7, as well.
Patrick
Quoted 5 lines · Patrick Steinhardt
Oh, yes. I didn't mean to say that I relied on your feedback being addressed exclusively. I already reviewed v5/v6 of this patch series and found it to be good, and given that there was only a single change proposed by you that I'm happy with it translates into me being in favor of v7, as well.
Yes, after sending the message you are responding to, I went back to the original thread and figured that much---the topic is marked for 'next'.
Thanks for your help.