Re: [PATCH v4 2/5] t: move reftable/tree_test.c to the unit testing framework

From: Karthik Nayak <karthik.188@gmail.com>
Date: Jul 18, 2024, 08:10 UTC
Message-ID: <CAOLa=ZRGV1-3cDxgJd9zENTCEPqz04AFwWmkQnYwj5Cbg=EmfA@mail.gmail.com>
In-Reply-To: <CA+J6zkRWzq_XNf-E7Nx4_D7rOOjN4Bwi4g3zgzV6YCiVoCe8rA@mail.gmail.com>

Chandra Pratap <chandrapratap3519@gmail.com> writes:

Show 79 quoted lines

> On Thu, 18 Jul 2024 at 03:45, Justin Tobler <jltobler@gmail.com> wrote:
>>
>> On 24/07/17 08:00PM, Chandra Pratap wrote:
>> > On Wed, 17 Jul 2024 at 18:09, Karthik Nayak <karthik.188@gmail.com> wrote:
>> > >
>> > > Chandra Pratap <chandrapratap3519@gmail.com> writes:
>> > >
>> > > > +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 };
>> > >
>> > > 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.
>>
>> 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.
>
> 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.
>
>> > > > +     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?
>> >
>> > 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.
>
> 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.
>
>> 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.

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?