[GSoC][PATCH] t/: migrate helper/test-oidtree.c to unit-tests/t-oidtree.c

[GSoC][PATCH] t/: migrate helper/test-oidtree.c to unit-tests/t-oidtree.c

[Ghanshyam Thakkar]

helper/test-oidtree.c along with t0069-oidtree.sh test the oidtree.h
library, which is a wrapper around crit-bit tree. Migrate them to
the unit testing framework for better debugging and runtime
performance.

To achieve this, introduce a new library called 'lib-oid.h'
exclusively for the unit tests to use. It currently mainly includes
utility to generate object_id from an arbitrary hex string
(i.e. '12a' -> '12a0000000000000000000000000000000000000').
This will also be helpful when we port other unit tests such
as oid-array, oidset etc.

Mentored-by: Christian Couder <chriscool@tuxfamily.org>
Mentored-by: Kaartic Sivaraam <kaartic.sivaraam@gmail.com>
Signed-off-by: Ghanshyam Thakkar <shyamthakkar001@gmail.com>
---
 Makefile                 |  8 +++-
 t/helper/test-oidtree.c  | 54 ------------------------
 t/helper/test-tool.c     |  1 -
 t/helper/test-tool.h     |  1 -
 t/t0069-oidtree.sh       | 50 ----------------------
 t/unit-tests/lib-oid.c   | 52 +++++++++++++++++++++++
 t/unit-tests/lib-oid.h   | 17 ++++++++
 t/unit-tests/t-oidtree.c | 91 ++++++++++++++++++++++++++++++++++++++++
 8 files changed, 166 insertions(+), 108 deletions(-)
 delete mode 100644 t/helper/test-oidtree.c
 delete mode 100755 t/t0069-oidtree.sh
 create mode 100644 t/unit-tests/lib-oid.c
 create mode 100644 t/unit-tests/lib-oid.h
 create mode 100644 t/unit-tests/t-oidtree.c

diff --git a/Makefile b/Makefile
index 59d98ba688..6c9927afae 100644
--- a/Makefile
+++ b/Makefile
@@ -811,7 +811,6 @@ TEST_BUILTINS_OBJS += test-mergesort.o
 TEST_BUILTINS_OBJS += test-mktemp.o
 TEST_BUILTINS_OBJS += test-oid-array.o
 TEST_BUILTINS_OBJS += test-oidmap.o
-TEST_BUILTINS_OBJS += test-oidtree.o
 TEST_BUILTINS_OBJS += test-online-cpus.o
 TEST_BUILTINS_OBJS += test-pack-mtimes.o
 TEST_BUILTINS_OBJS += test-parse-options.o
@@ -1335,6 +1334,7 @@ THIRD_PARTY_SOURCES += sha1dc/%
 
 UNIT_TEST_PROGRAMS += t-ctype
 UNIT_TEST_PROGRAMS += t-mem-pool
+UNIT_TEST_PROGRAMS += t-oidtree
 UNIT_TEST_PROGRAMS += t-prio-queue
 UNIT_TEST_PROGRAMS += t-strbuf
 UNIT_TEST_PROGRAMS += t-strcmp-offset
@@ -1342,6 +1342,7 @@ UNIT_TEST_PROGRAMS += t-trailer
 UNIT_TEST_PROGS = $(patsubst %,$(UNIT_TEST_BIN)/%$X,$(UNIT_TEST_PROGRAMS))
 UNIT_TEST_OBJS = $(patsubst %,$(UNIT_TEST_DIR)/%.o,$(UNIT_TEST_PROGRAMS))
 UNIT_TEST_OBJS += $(UNIT_TEST_DIR)/test-lib.o
+UNIT_TEST_OBJS += $(UNIT_TEST_DIR)/lib-oid.o
 
 # xdiff and reftable libs may in turn depend on what is in libgit.a
 GITLIBS = common-main.o $(LIB_FILE) $(XDIFF_LIB) $(REFTABLE_LIB) $(LIB_FILE)
@@ -3882,7 +3883,10 @@ $(FUZZ_PROGRAMS): %: %.o oss-fuzz/dummy-cmd-main.o $(GITLIBS) GIT-LDFLAGS
 		-Wl,--allow-multiple-definition \
 		$(filter %.o,$^) $(filter %.a,$^) $(LIBS) $(LIB_FUZZING_ENGINE)
 
-$(UNIT_TEST_PROGS): $(UNIT_TEST_BIN)/%$X: $(UNIT_TEST_DIR)/%.o $(UNIT_TEST_DIR)/test-lib.o $(GITLIBS) GIT-LDFLAGS
+$(UNIT_TEST_PROGS): $(UNIT_TEST_BIN)/%$X: $(UNIT_TEST_DIR)/%.o \
+	$(UNIT_TEST_DIR)/test-lib.o \
+	$(UNIT_TEST_DIR)/lib-oid.o \
+	$(GITLIBS) GIT-LDFLAGS
 	$(call mkdir_p_parent_template)
 	$(QUIET_LINK)$(CC) $(ALL_CFLAGS) -o $@ $(ALL_LDFLAGS) \
 		$(filter %.o,$^) $(filter %.a,$^) $(LIBS)
diff --git a/t/helper/test-oidtree.c b/t/helper/test-oidtree.c
deleted file mode 100644
index c7a1d4c642..0000000000
--- a/t/helper/test-oidtree.c
+++ /dev/null
@@ -1,54 +0,0 @@
-#include "test-tool.h"
-#include "hex.h"
-#include "oidtree.h"
-#include "setup.h"
-#include "strbuf.h"
-
-static enum cb_next print_oid(const struct object_id *oid, void *data UNUSED)
-{
-	puts(oid_to_hex(oid));
-	return CB_CONTINUE;
-}
-
-int cmd__oidtree(int argc UNUSED, const char **argv UNUSED)
-{
-	struct oidtree ot;
-	struct strbuf line = STRBUF_INIT;
-	int nongit_ok;
-	int algo = GIT_HASH_UNKNOWN;
-
-	oidtree_init(&ot);
-	setup_git_directory_gently(&nongit_ok);
-
-	while (strbuf_getline(&line, stdin) != EOF) {
-		const char *arg;
-		struct object_id oid;
-
-		if (skip_prefix(line.buf, "insert ", &arg)) {
-			if (get_oid_hex_any(arg, &oid) == GIT_HASH_UNKNOWN)
-				die("insert not a hexadecimal oid: %s", arg);
-			algo = oid.algo;
-			oidtree_insert(&ot, &oid);
-		} else if (skip_prefix(line.buf, "contains ", &arg)) {
-			if (get_oid_hex(arg, &oid))
-				die("contains not a hexadecimal oid: %s", arg);
-			printf("%d\n", oidtree_contains(&ot, &oid));
-		} else if (skip_prefix(line.buf, "each ", &arg)) {
-			char buf[GIT_MAX_HEXSZ + 1] = { '0' };
-			memset(&oid, 0, sizeof(oid));
-			memcpy(buf, arg, strlen(arg));
-			buf[hash_algos[algo].hexsz] = '\0';
-			get_oid_hex_any(buf, &oid);
-			oid.algo = algo;
-			oidtree_each(&ot, &oid, strlen(arg), print_oid, NULL);
-		} else if (!strcmp(line.buf, "clear")) {
-			oidtree_clear(&ot);
-		} else {
-			die("unknown command: %s", line.buf);
-		}
-	}
-
-	strbuf_release(&line);
-
-	return 0;
-}
diff --git a/t/helper/test-tool.c b/t/helper/test-tool.c
index 7ad7d07018..253324a06b 100644
--- a/t/helper/test-tool.c
+++ b/t/helper/test-tool.c
@@ -46,7 +46,6 @@ static struct test_cmd cmds[] = {
 	{ "mktemp", cmd__mktemp },
 	{ "oid-array", cmd__oid_array },
 	{ "oidmap", cmd__oidmap },
-	{ "oidtree", cmd__oidtree },
 	{ "online-cpus", cmd__online_cpus },
 	{ "pack-mtimes", cmd__pack_mtimes },
 	{ "parse-options", cmd__parse_options },
diff --git a/t/helper/test-tool.h b/t/helper/test-tool.h
index d14b3072bd..460dd7d260 100644
--- a/t/helper/test-tool.h
+++ b/t/helper/test-tool.h
@@ -39,7 +39,6 @@ int cmd__match_trees(int argc, const char **argv);
 int cmd__mergesort(int argc, const char **argv);
 int cmd__mktemp(int argc, const char **argv);
 int cmd__oidmap(int argc, const char **argv);
-int cmd__oidtree(int argc, const char **argv);
 int cmd__online_cpus(int argc, const char **argv);
 int cmd__pack_mtimes(int argc, const char **argv);
 int cmd__parse_options(int argc, const char **argv);
diff --git a/t/t0069-oidtree.sh b/t/t0069-oidtree.sh
deleted file mode 100755
index 889db50818..0000000000
--- a/t/t0069-oidtree.sh
+++ /dev/null
@@ -1,50 +0,0 @@
-#!/bin/sh
-
-test_description='basic tests for the oidtree implementation'
-TEST_PASSES_SANITIZE_LEAK=true
-. ./test-lib.sh
-
-maxhexsz=$(test_oid hexsz)
-echoid () {
-	prefix="${1:+$1 }"
-	shift
-	while test $# -gt 0
-	do
-		shortoid="$1"
-		shift
-		difference=$(($maxhexsz - ${#shortoid}))
-		printf "%s%s%0${difference}d\\n" "$prefix" "$shortoid" "0"
-	done
-}
-
-test_expect_success 'oidtree insert and contains' '
-	cat >expect <<-\EOF &&
-		0
-		0
-		0
-		1
-		1
-		0
-	EOF
-	{
-		echoid insert 444 1 2 3 4 5 a b c d e &&
-		echoid contains 44 441 440 444 4440 4444 &&
-		echo clear
-	} | test-tool oidtree >actual &&
-	test_cmp expect actual
-'
-
-test_expect_success 'oidtree each' '
-	echoid "" 123 321 321 >expect &&
-	{
-		echoid insert f 9 8 123 321 a b c d e &&
-		echo each 12300 &&
-		echo each 3211 &&
-		echo each 3210 &&
-		echo each 32100 &&
-		echo clear
-	} | test-tool oidtree >actual &&
-	test_cmp expect actual
-'
-
-test_done
diff --git a/t/unit-tests/lib-oid.c b/t/unit-tests/lib-oid.c
new file mode 100644
index 0000000000..37105f0a8f
--- /dev/null
+++ b/t/unit-tests/lib-oid.c
@@ -0,0 +1,52 @@
+#include "test-lib.h"
+#include "lib-oid.h"
+#include "strbuf.h"
+#include "hex.h"
+
+static int init_hash_algo(void)
+{
+	static int algo = -1;
+
+	if (algo < 0) {
+		const char *algo_name = getenv("GIT_TEST_DEFAULT_HASH");
+		algo = algo_name ? hash_algo_by_name(algo_name) : GIT_HASH_SHA1;
+
+		if (!check(algo != GIT_HASH_UNKNOWN))
+			test_msg("BUG: invalid GIT_TEST_DEFAULT_HASH value ('%s')",
+				 algo_name);
+	}
+	return algo;
+}
+
+static int get_oid_arbitrary_hex_algop(const char *hex, struct object_id *oid,
+				       const struct git_hash_algo *algop)
+{
+	int ret;
+	size_t sz = strlen(hex);
+	struct strbuf buf = STRBUF_INIT;
+
+	if (!check(sz <= algop->hexsz)) {
+		test_msg("BUG: hex string (%s) bigger than maximum allowed (%lu)",
+			 hex, (unsigned long)algop->hexsz);
+		return -1;
+	}
+
+	strbuf_add(&buf, hex, sz);
+	strbuf_addchars(&buf, '0', algop->hexsz - sz);
+
+	ret = get_oid_hex_algop(buf.buf, oid, algop);
+	if (!check_int(ret, ==, 0))
+		test_msg("BUG: invalid hex input (%s) provided", hex);
+
+	strbuf_release(&buf);
+	return ret;
+}
+
+int get_oid_arbitrary_hex(const char *hex, struct object_id *oid)
+{
+	int hash_algo = init_hash_algo();
+
+	if (!check_int(hash_algo, !=, GIT_HASH_UNKNOWN))
+		return -1;
+	return get_oid_arbitrary_hex_algop(hex, oid, &hash_algos[hash_algo]);
+}
diff --git a/t/unit-tests/lib-oid.h b/t/unit-tests/lib-oid.h
new file mode 100644
index 0000000000..bfde639190
--- /dev/null
+++ b/t/unit-tests/lib-oid.h
@@ -0,0 +1,17 @@
+#ifndef LIB_OID_H
+#define LIB_OID_H
+
+#include "hash-ll.h"
+
+/*
+ * Convert arbitrary hex string to object_id.
+ * For example, passing "abc12" will generate
+ * "abc1200000000000000000000000000000000000" hex of length 40 for SHA-1 and
+ * create object_id with that.
+ * WARNING: passing a string of length more than the hexsz of respective hash
+ * algo is not allowed. The hash algo is decided based on GIT_TEST_DEFAULT_HASH
+ * environment variable.
+ */
+int get_oid_arbitrary_hex(const char *s, struct object_id *oid);
+
+#endif /* LIB_OID_H */
diff --git a/t/unit-tests/t-oidtree.c b/t/unit-tests/t-oidtree.c
new file mode 100644
index 0000000000..0ebe17d2b9
--- /dev/null
+++ b/t/unit-tests/t-oidtree.c
@@ -0,0 +1,91 @@
+#include "test-lib.h"
+#include "lib-oid.h"
+#include "oidtree.h"
+#include "hash.h"
+#include "hex.h"
+
+#define FILL_TREE(tree, ...)                                       \
+	do {                                                       \
+		const char *hexes[] = { __VA_ARGS__ };             \
+		if (fill_tree_loc(tree, hexes, ARRAY_SIZE(hexes))) \
+			return;                                    \
+	} while (0)
+
+static int fill_tree_loc(struct oidtree *ot, const char *hexes[], int n)
+{
+	for (size_t i = 0; i < n; i++) {
+		struct object_id oid;
+		if (!check_int(get_oid_arbitrary_hex(hexes[i], &oid), ==, 0))
+			return -1;
+		oidtree_insert(ot, &oid);
+	}
+	return 0;
+}
+
+static void check_contains(struct oidtree *ot, const char *hex, int expected)
+{
+	struct object_id oid;
+
+	if (!check_int(get_oid_arbitrary_hex(hex, &oid), ==, 0))
+		return;
+	if (!check_int(oidtree_contains(ot, &oid), ==, expected))
+		test_msg("oid: %s", oid_to_hex(&oid));
+}
+
+static enum cb_next check_each_cb(const struct object_id *oid, void *data)
+{
+	const char *hex = data;
+	struct object_id expected;
+
+	if (!check_int(get_oid_arbitrary_hex(hex, &expected), ==, 0))
+		return CB_CONTINUE;
+	if (!check(oideq(oid, &expected)))
+		test_msg("expected: %s\n       got: %s",
+			 hash_to_hex(expected.hash), hash_to_hex(oid->hash));
+	return CB_CONTINUE;
+}
+
+static void check_each(struct oidtree *ot, char *hex, char *expected)
+{
+	struct object_id oid;
+
+	if (!check_int(get_oid_arbitrary_hex(hex, &oid), ==, 0))
+		return;
+	oidtree_each(ot, &oid, 40, check_each_cb, expected);
+}
+
+static void setup(void (*f)(struct oidtree *ot))
+{
+	struct oidtree ot;
+
+	oidtree_init(&ot);
+	f(&ot);
+	oidtree_clear(&ot);
+}
+
+static void t_contains(struct oidtree *ot)
+{
+	FILL_TREE(ot, "444", "1", "2", "3", "4", "5", "a", "b", "c", "d", "e");
+	check_contains(ot, "44", 0);
+	check_contains(ot, "441", 0);
+	check_contains(ot, "440", 0);
+	check_contains(ot, "444", 1);
+	check_contains(ot, "4440", 1);
+	check_contains(ot, "4444", 0);
+}
+
+static void t_each(struct oidtree *ot)
+{
+	FILL_TREE(ot, "f", "9", "8", "123", "321", "a", "b", "c", "d", "e");
+	check_each(ot, "12300", "123");
+	check_each(ot, "3211", ""); /* should not reach callback */
+	check_each(ot, "3210", "321");
+	check_each(ot, "32100", "321");
+}
+
+int cmd_main(int argc UNUSED, const char **argv UNUSED)
+{
+	TEST(setup(t_contains), "oidtree insert and contains works");
+	TEST(setup(t_each), "oidtree each works");
+	return test_done();
+}
-- 
2.45.2

Re: [GSoC][PATCH] t/: migrate helper/test-oidtree.c to unit-tests/t-oidtree.c

[Junio C Hamano]

Ghanshyam Thakkar <shyamthakkar001@gmail.com> writes:

> helper/test-oidtree.c along with t0069-oidtree.sh test the oidtree.h
> library, which is a wrapper around crit-bit tree. Migrate them to
> the unit testing framework for better debugging and runtime
> performance.
>
> To achieve this, introduce a new library called 'lib-oid.h'
> exclusively for the unit tests to use. It currently mainly includes
> utility to generate object_id from an arbitrary hex string
> (i.e. '12a' -> '12a0000000000000000000000000000000000000').
> This will also be helpful when we port other unit tests such
> as oid-array, oidset etc.

Perhaps.  With only a single user it is hard to judge if it is worth
doing, but once the code is written, it is not worth a code churn to
merge it into t-oidtree.c.

> +#define FILL_TREE(tree, ...)                                       \
> +	do {                                                       \
> +		const char *hexes[] = { __VA_ARGS__ };             \
> +		if (fill_tree_loc(tree, hexes, ARRAY_SIZE(hexes))) \
> +			return;                                    \
> +	} while (0)

Nice.

> +static enum cb_next check_each_cb(const struct object_id *oid, void *data)
> +{
> +	const char *hex = data;
> +	struct object_id expected;
> +
> +	if (!check_int(get_oid_arbitrary_hex(hex, &expected), ==, 0))
> +		return CB_CONTINUE;
> +	if (!check(oideq(oid, &expected)))
> +		test_msg("expected: %s\n       got: %s",
> +			 hash_to_hex(expected.hash), hash_to_hex(oid->hash));
> +	return CB_CONTINUE;
> +}

The control flow looks somewhat strange here.  I would have written:

	if (!check_int(..., ==, 0))
		; /* the data is bogus and cannot be used */
	else if (!check(oideq(...))
		test_msg(... expected and got differ ...);
	return CB_CONTINUE;

but OK.

> +static void check_each(struct oidtree *ot, char *hex, char *expected)
> +{
> +	struct object_id oid;
> +
> +	if (!check_int(get_oid_arbitrary_hex(hex, &oid), ==, 0))
> +		return;
> +	oidtree_each(ot, &oid, 40, check_each_cb, expected);
> +}
> +
> +static void setup(void (*f)(struct oidtree *ot))
> +{
> +	struct oidtree ot;
> +
> +	oidtree_init(&ot);
> +	f(&ot);
> +	oidtree_clear(&ot);
> +}
> +
> +static void t_contains(struct oidtree *ot)
> +{
> +	FILL_TREE(ot, "444", "1", "2", "3", "4", "5", "a", "b", "c", "d", "e");
> +	check_contains(ot, "44", 0);
> +	check_contains(ot, "441", 0);
> +	check_contains(ot, "440", 0);
> +	check_contains(ot, "444", 1);
> +	check_contains(ot, "4440", 1);
> +	check_contains(ot, "4444", 0);
> +}

OK.

Compared to the original, this makes the correspondence between the
input and the expected result slightly easier to see, which is good.

> +static void t_each(struct oidtree *ot)
> +{
> +	FILL_TREE(ot, "f", "9", "8", "123", "321", "a", "b", "c", "d", "e");
> +	check_each(ot, "12300", "123");
> +	check_each(ot, "3211", ""); /* should not reach callback */
> +	check_each(ot, "3210", "321");
> +	check_each(ot, "32100", "321");
> +}

Testing "each" with test data that yields only at most one response
smells iffy.  It is a problem in the original test, and not a
problem with the conversion, ...

BUT

... in the original, it is easy to do something like the attached to
demonstrate that "each" can yield all oid that the shares the query
prefix.  But the rewritten unit test bakes the assumption that we
will only try a query that yields at most one response into the test
helper functions.  Shouldn't we do a bit better, perhaps allowing the
check_each() helper to take variable number of parameters, e.g.

	check_each(ot, "12300", "123", NULL);
	check_each(ot, "32", "320", "321", NULL);

so the latter invocation asks "ot" trie "I have prefix 32, please
call me back with each element you have that match", and makes sure
that we get called back with "320" and then "321" and never after.

Come to think of it, how is your check_each_cb() ensuring that it is
only called once with "123" when queried with "12300"?  If the
callback is made with "123" 100 times with the single query with
"12300", would it even notice?  I would imagine that the original
would (simply because it dumps each and every callback to a file to
be compared with the golden copy).

 t/t0069-oidtree.sh | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)

diff --git c/t/t0069-oidtree.sh w/t/t0069-oidtree.sh
index 889db50818..40b836aff5 100755
--- c/t/t0069-oidtree.sh
+++ w/t/t0069-oidtree.sh
@@ -35,13 +35,14 @@ test_expect_success 'oidtree insert and contains' '
 '
 
 test_expect_success 'oidtree each' '
-	echoid "" 123 321 321 >expect &&
+	echoid "" 123 321 321 320 321 >expect &&
 	{
-		echoid insert f 9 8 123 321 a b c d e &&
+		echoid insert f 9 8 123 321 320 a b c d e &&
 		echo each 12300 &&
 		echo each 3211 &&
 		echo each 3210 &&
 		echo each 32100 &&
+		echo each 32 &&
 		echo clear
 	} | test-tool oidtree >actual &&
 	test_cmp expect actual

Re: [GSoC][PATCH] t/: migrate helper/test-oidtree.c to unit-tests/t-oidtree.c

[Ghanshyam Thakkar]

On Thu, 06 Jun 2024, Junio C Hamano <gitster@pobox.com> wrote:
> Ghanshyam Thakkar <shyamthakkar001@gmail.com> writes:
> > +static void check_each(struct oidtree *ot, char *hex, char *expected)
> > +{
> > +	struct object_id oid;
> > +
> > +	if (!check_int(get_oid_arbitrary_hex(hex, &oid), ==, 0))
> > +		return;
> > +	oidtree_each(ot, &oid, 40, check_each_cb, expected);

I think I mistakenly kept '40' from when I was testing, but it should
be strlen(hex). Will correct.

> > +static void t_each(struct oidtree *ot)
> > +{
> > +	FILL_TREE(ot, "f", "9", "8", "123", "321", "a", "b", "c", "d", "e");
> > +	check_each(ot, "12300", "123");
> > +	check_each(ot, "3211", ""); /* should not reach callback */
> > +	check_each(ot, "3210", "321");
> > +	check_each(ot, "32100", "321");
> > +}
> 
> Testing "each" with test data that yields only at most one response
> smells iffy.  It is a problem in the original test, and not a
> problem with the conversion, ...
> 
> BUT
> 
> ... in the original, it is easy to do something like the attached to
> demonstrate that "each" can yield all oid that the shares the query
> prefix.  But the rewritten unit test bakes the assumption that we
> will only try a query that yields at most one response into the test
> helper functions.  Shouldn't we do a bit better, perhaps allowing the
> check_each() helper to take variable number of parameters, e.g.
> 
> 	check_each(ot, "12300", "123", NULL);
> 	check_each(ot, "32", "320", "321", NULL);
> 
> so the latter invocation asks "ot" trie "I have prefix 32, please
> call me back with each element you have that match", and makes sure
> that we get called back with "320" and then "321" and never after.
> 
> Come to think of it, how is your check_each_cb() ensuring that it is
> only called once with "123" when queried with "12300"?  If the
> callback is made with "123" 100 times with the single query with
> "12300", would it even notice?  I would imagine that the original
> would (simply because it dumps each and every callback to a file to
> be compared with the golden copy).

That's true! I did not think of that. What do you think about something
like this then? I will clean it up to send in v2.

---

struct cb_data {
	int *i;
	struct strvec *expected_hexes;
};

static enum cb_next check_each_cb(const struct object_id *oid, void *data)
{
	struct cb_data *cb_data = data;
	struct object_id expected;

	if(!check_int(*cb_data->i, <, cb_data->hexes->nr)) {
		test_msg("error: extraneous callback. found oid: %s", oid_to_hex(oid));
		return CB_BREAK;
	}

	if (!check_int(get_oid_arbitrary_hex(cb_data->expected_hexes->v[*cb_data->i], &expected), ==, 0))
		return CB_BREAK;
	if (!check(oideq(oid, &expected)))
		test_msg("expected: %s\n       got: %s",
			 hash_to_hex(expected.hash), hash_to_hex(oid->hash));

	*cb_data->i += 1;
	return CB_CONTINUE;
}

static void check_each(struct oidtree *ot, char *query, ...)
{
	struct object_id oid;
	struct strvec hexes = STRVEC_INIT;
	struct cb_data cb_data;
	const char *arg;
	int i = 0;

	va_list expected;
	va_start(expected, query);

	while ((arg = va_arg(expected, const char *)))
		strvec_push(&hexes, arg);

	cb_data.i = &i;
	cb_data.expected_hexes = &hexes;

	if (!check_int(get_oid_arbitrary_hex(query, &oid), ==, 0))
		return;
	oidtree_each(ot, &oid, strlen(query), check_each_cb, &cb_data);

	if (!check_int(*cb_data.i, ==, cb_data.expected_hexes->nr))
		test_msg("error: could not find some oids");
}
---

Thanks for the review.

Re: [GSoC][PATCH] t/: migrate helper/test-oidtree.c to unit-tests/t-oidtree.c

[Christian Couder]

On Fri, Jun 7, 2024 at 1:35 AM Ghanshyam Thakkar
<shyamthakkar001@gmail.com> wrote:

> > Come to think of it, how is your check_each_cb() ensuring that it is
> > only called once with "123" when queried with "12300"?  If the
> > callback is made with "123" 100 times with the single query with
> > "12300", would it even notice?  I would imagine that the original
> > would (simply because it dumps each and every callback to a file to
> > be compared with the golden copy).
>
> That's true! I did not think of that. What do you think about something
> like this then? I will clean it up to send in v2.
>
> ---
>
> struct cb_data {
>         int *i;
>         struct strvec *expected_hexes;
> };

It might be better to use a more meaningful name for the struct, like
perhaps 'expected_hex_iter'. Also I think 'i' could be just 'size_t i'
instead of 'int *i', and 'expected_hexes' could be just 'hexes'.

> static enum cb_next check_each_cb(const struct object_id *oid, void *data)
> {
>         struct cb_data *cb_data = data;

Maybe: `struct expected_hex_iter *hex_iter = data;`

>         struct object_id expected;
>
>         if(!check_int(*cb_data->i, <, cb_data->hexes->nr)) {

A space character is missing between 'if' and '('. And by the way you
use 'hexes' instead of 'expected_hexes' here.

>                 test_msg("error: extraneous callback. found oid: %s", oid_to_hex(oid));
>                 return CB_BREAK;
>         }
>
>         if (!check_int(get_oid_arbitrary_hex(cb_data->expected_hexes->v[*cb_data->i], &expected), ==, 0))
>                 return CB_BREAK;
>         if (!check(oideq(oid, &expected)))
>                 test_msg("expected: %s\n       got: %s",
>                          hash_to_hex(expected.hash), hash_to_hex(oid->hash));
>
>         *cb_data->i += 1;
>         return CB_CONTINUE;
> }
>
> static void check_each(struct oidtree *ot, char *query, ...)
> {
>         struct object_id oid;
>         struct strvec hexes = STRVEC_INIT;
>         struct cb_data cb_data;
>         const char *arg;
>         int i = 0;
>
>         va_list expected;
>         va_start(expected, query);
>
>         while ((arg = va_arg(expected, const char *)))
>                 strvec_push(&hexes, arg);
>
>         cb_data.i = &i;
>         cb_data.expected_hexes = &hexes;

Can't we just have something like:

        struct expected_hex_iter hex_iter = { .i = 0, .hexes = &hexes };

above when 'hex_iter' is declared?

>         if (!check_int(get_oid_arbitrary_hex(query, &oid), ==, 0))
>                 return;
>         oidtree_each(ot, &oid, strlen(query), check_each_cb, &cb_data);
>
>         if (!check_int(*cb_data.i, ==, cb_data.expected_hexes->nr))
>                 test_msg("error: could not find some oids");
> }

Thanks.

Re: [GSoC][PATCH] t/: migrate helper/test-oidtree.c to unit-tests/t-oidtree.c

[Christian Couder]

On Fri, Jun 7, 2024 at 10:31 AM Christian Couder
<christian.couder@gmail.com> wrote:
>
> On Fri, Jun 7, 2024 at 1:35 AM Ghanshyam Thakkar
> <shyamthakkar001@gmail.com> wrote:
>
> > > Come to think of it, how is your check_each_cb() ensuring that it is
> > > only called once with "123" when queried with "12300"?  If the
> > > callback is made with "123" 100 times with the single query with
> > > "12300", would it even notice?  I would imagine that the original
> > > would (simply because it dumps each and every callback to a file to
> > > be compared with the golden copy).
> >
> > That's true! I did not think of that. What do you think about something
> > like this then? I will clean it up to send in v2.
> >
> > ---
> >
> > struct cb_data {
> >         int *i;
> >         struct strvec *expected_hexes;
> > };
>
> It might be better to use a more meaningful name for the struct, like
> perhaps 'expected_hex_iter'. Also I think 'i' could be just 'size_t i'
> instead of 'int *i', and 'expected_hexes' could be just 'hexes'.

Maybe even:

struct expected_hex_iter {
       size_t i;
       struct strvec hexes;
};

(so without any pointer)

...

> > static enum cb_next check_each_cb(const struct object_id *oid, void *data)
> > {
> >         struct cb_data *cb_data = data;
>
> Maybe: `struct expected_hex_iter *hex_iter = data;`
>
> >         struct object_id expected;
> >
> >         if(!check_int(*cb_data->i, <, cb_data->hexes->nr)) {
>
> A space character is missing between 'if' and '('. And by the way you
> use 'hexes' instead of 'expected_hexes' here.
>
> >                 test_msg("error: extraneous callback. found oid: %s", oid_to_hex(oid));
> >                 return CB_BREAK;
> >         }
> >
> >         if (!check_int(get_oid_arbitrary_hex(cb_data->expected_hexes->v[*cb_data->i], &expected), ==, 0))
> >                 return CB_BREAK;
> >         if (!check(oideq(oid, &expected)))
> >                 test_msg("expected: %s\n       got: %s",
> >                          hash_to_hex(expected.hash), hash_to_hex(oid->hash));
> >
> >         *cb_data->i += 1;
> >         return CB_CONTINUE;
> > }
> >
> > static void check_each(struct oidtree *ot, char *query, ...)
> > {
> >         struct object_id oid;
> >         struct strvec hexes = STRVEC_INIT;
> >         struct cb_data cb_data;
> >         const char *arg;
> >         int i = 0;

... and above only:

        struct object_id oid;
        const char *arg;
        struct expected_hex_iter hex_iter = { 0 };

Re: [GSoC][PATCH] t/: migrate helper/test-oidtree.c to unit-tests/t-oidtree.c

[Christian Couder]

On Fri, Jun 7, 2024 at 10:36 AM Christian Couder
<christian.couder@gmail.com> wrote:
>
> On Fri, Jun 7, 2024 at 10:31 AM Christian Couder
> <christian.couder@gmail.com> wrote:
> >
> > On Fri, Jun 7, 2024 at 1:35 AM Ghanshyam Thakkar
> > <shyamthakkar001@gmail.com> wrote:


> > > static void check_each(struct oidtree *ot, char *query, ...)
> > > {
> > >         struct object_id oid;
> > >         struct strvec hexes = STRVEC_INIT;
> > >         struct cb_data cb_data;
> > >         const char *arg;
> > >         int i = 0;
>
> ... and above only:
>
>         struct object_id oid;
>         const char *arg;
>         struct expected_hex_iter hex_iter = { 0 };

Actually I think it should be:

        struct expected_hex_iter hex_iter = { .hexes = STRVEC_INIT };

Re: [GSoC][PATCH] t/: migrate helper/test-oidtree.c to unit-tests/t-oidtree.c

[Junio C Hamano]

Ghanshyam Thakkar <shyamthakkar001@gmail.com> writes:

>> Come to think of it, how is your check_each_cb() ensuring that it is
>> only called once with "123" when queried with "12300"?  If the
>> callback is made with "123" 100 times with the single query with
>> "12300", would it even notice?  I would imagine that the original
>> would (simply because it dumps each and every callback to a file to
>> be compared with the golden copy).
>
> That's true! I did not think of that. What do you think about something
> like this then? I will clean it up to send in v2.

I do not see a strong reason to have a pointer to int in cb_data, as
the caller has access to cb_data after the callback finishes using
it so check_each() can check cb_data.i instead of *cb_data.i (or i)
at the end.

But other than that, yes, it is the direction you would want to go,
I would think.

>
> ---
>
> struct cb_data {
> 	int *i;
> 	struct strvec *expected_hexes;
> };
>
> static enum cb_next check_each_cb(const struct object_id *oid, void *data)
> {
> 	struct cb_data *cb_data = data;
> 	struct object_id expected;
>
> 	if(!check_int(*cb_data->i, <, cb_data->hexes->nr)) {
> 		test_msg("error: extraneous callback. found oid: %s", oid_to_hex(oid));
> 		return CB_BREAK;
> 	}
>
> 	if (!check_int(get_oid_arbitrary_hex(cb_data->expected_hexes->v[*cb_data->i], &expected), ==, 0))
> 		return CB_BREAK;
> 	if (!check(oideq(oid, &expected)))
> 		test_msg("expected: %s\n       got: %s",
> 			 hash_to_hex(expected.hash), hash_to_hex(oid->hash));
>
> 	*cb_data->i += 1;
> 	return CB_CONTINUE;
> }
>
> static void check_each(struct oidtree *ot, char *query, ...)
> {
> 	struct object_id oid;
> 	struct strvec hexes = STRVEC_INIT;
> 	struct cb_data cb_data;
> 	const char *arg;
> 	int i = 0;
>
> 	va_list expected;
> 	va_start(expected, query);
>
> 	while ((arg = va_arg(expected, const char *)))
> 		strvec_push(&hexes, arg);
>
> 	cb_data.i = &i;
> 	cb_data.expected_hexes = &hexes;
>
> 	if (!check_int(get_oid_arbitrary_hex(query, &oid), ==, 0))
> 		return;
> 	oidtree_each(ot, &oid, strlen(query), check_each_cb, &cb_data);
>
> 	if (!check_int(*cb_data.i, ==, cb_data.expected_hexes->nr))
> 		test_msg("error: could not find some oids");
> }
> ---
>
> Thanks for the review.

[GSoC][PATCH v2] t/: migrate helper/test-oidtree.c to unit-tests/t-oidtree.c

[Ghanshyam Thakkar]

helper/test-oidtree.c along with t0069-oidtree.sh test the oidtree.h
library, which is a wrapper around crit-bit tree. Migrate them to
the unit testing framework for better debugging and runtime
performance. Along with the migration, add an extra check for
oidtree_each() test, which showcases how multiple expected matches can
be given to check_each() helper.

To achieve this, introduce a new library called 'lib-oid.h'
exclusively for the unit tests to use. It currently mainly includes
utility to generate object_id from an arbitrary hex string
(i.e. '12a' -> '12a0000000000000000000000000000000000000'). This also
handles the hash algo selection based on GIT_TEST_DEFAULT_HASH.
This library will also be helpful when we port other unit tests such
as oid-array, oidset etc.

Helped-by: Junio C Hamano <gitster@pobox.com>
Mentored-by: Christian Couder <chriscool@tuxfamily.org>
Mentored-by: Kaartic Sivaraam <kaartic.sivaraam@gmail.com>
Signed-off-by: Ghanshyam Thakkar <shyamthakkar001@gmail.com>
---
Range-diff against v1:
1:  ee3df5db33 ! 1:  6d94be745a t/: migrate helper/test-oidtree.c to unit-tests/t-oidtree.c
    @@ Commit message
         helper/test-oidtree.c along with t0069-oidtree.sh test the oidtree.h
         library, which is a wrapper around crit-bit tree. Migrate them to
         the unit testing framework for better debugging and runtime
    -    performance.
    +    performance. Along with the migration, add an extra check for
    +    oidtree_each() test, which showcases how multiple expected matches can
    +    be given to check_each() helper.
     
         To achieve this, introduce a new library called 'lib-oid.h'
         exclusively for the unit tests to use. It currently mainly includes
         utility to generate object_id from an arbitrary hex string
    -    (i.e. '12a' -> '12a0000000000000000000000000000000000000').
    -    This will also be helpful when we port other unit tests such
    +    (i.e. '12a' -> '12a0000000000000000000000000000000000000'). This also
    +    handles the hash algo selection based on GIT_TEST_DEFAULT_HASH.
    +    This library will also be helpful when we port other unit tests such
         as oid-array, oidset etc.
     
         Mentored-by: Christian Couder <chriscool@tuxfamily.org>
    @@ t/unit-tests/t-oidtree.c (new)
     +#include "oidtree.h"
     +#include "hash.h"
     +#include "hex.h"
    ++#include "strvec.h"
     +
     +#define FILL_TREE(tree, ...)                                       \
     +	do {                                                       \
    @@ t/unit-tests/t-oidtree.c (new)
     +			return;                                    \
     +	} while (0)
     +
    -+static int fill_tree_loc(struct oidtree *ot, const char *hexes[], int n)
    ++static int fill_tree_loc(struct oidtree *ot, const char *hexes[], size_t n)
     +{
     +	for (size_t i = 0; i < n; i++) {
     +		struct object_id oid;
    @@ t/unit-tests/t-oidtree.c (new)
     +		test_msg("oid: %s", oid_to_hex(&oid));
     +}
     +
    ++struct expected_hex_iter {
    ++	size_t i;
    ++	struct strvec expected_hexes;
    ++	const char *query;
    ++};
    ++
     +static enum cb_next check_each_cb(const struct object_id *oid, void *data)
     +{
    -+	const char *hex = data;
    ++	struct expected_hex_iter *hex_iter = data;
     +	struct object_id expected;
     +
    -+	if (!check_int(get_oid_arbitrary_hex(hex, &expected), ==, 0))
    -+		return CB_CONTINUE;
    -+	if (!check(oideq(oid, &expected)))
    -+		test_msg("expected: %s\n       got: %s",
    -+			 hash_to_hex(expected.hash), hash_to_hex(oid->hash));
    ++	if (!check_int(hex_iter->i, <, hex_iter->expected_hexes.nr)) {
    ++		test_msg("error: extraneous callback for query: ('%s'), object_id: ('%s')",
    ++			 hex_iter->query, oid_to_hex(oid));
    ++		return CB_BREAK;
    ++	}
    ++
    ++	if (!check_int(get_oid_arbitrary_hex(hex_iter->expected_hexes.v[hex_iter->i],
    ++					     &expected), ==, 0))
    ++		; /* the data is bogus and cannot be used */
    ++	else if (!check(oideq(oid, &expected)))
    ++		test_msg("expected: %s\n       got: %s\n     query: %s",
    ++			 oid_to_hex(&expected), oid_to_hex(oid), hex_iter->query);
    ++
    ++	hex_iter->i += 1;
     +	return CB_CONTINUE;
     +}
     +
    -+static void check_each(struct oidtree *ot, char *hex, char *expected)
    ++static void check_each(struct oidtree *ot, char *query, ...)
     +{
     +	struct object_id oid;
    ++	struct expected_hex_iter hex_iter = { .expected_hexes = STRVEC_INIT,
    ++					      .query = query };
    ++	const char *arg;
    ++	va_list hex_args;
     +
    -+	if (!check_int(get_oid_arbitrary_hex(hex, &oid), ==, 0))
    ++	va_start(hex_args, query);
    ++	while ((arg = va_arg(hex_args, const char *)))
    ++		strvec_push(&hex_iter.expected_hexes, arg);
    ++	va_end(hex_args);
    ++
    ++	if (!check_int(get_oid_arbitrary_hex(query, &oid), ==, 0))
     +		return;
    -+	oidtree_each(ot, &oid, 40, check_each_cb, expected);
    ++	oidtree_each(ot, &oid, strlen(query), check_each_cb, &hex_iter);
    ++
    ++	if (!check_int(hex_iter.i, ==, hex_iter.expected_hexes.nr))
    ++		test_msg("error: could not find some 'object_id's for query ('%s')", query);
    ++	strvec_clear(&hex_iter.expected_hexes);
     +}
     +
     +static void setup(void (*f)(struct oidtree *ot))
    @@ t/unit-tests/t-oidtree.c (new)
     +
     +static void t_each(struct oidtree *ot)
     +{
    -+	FILL_TREE(ot, "f", "9", "8", "123", "321", "a", "b", "c", "d", "e");
    -+	check_each(ot, "12300", "123");
    -+	check_each(ot, "3211", ""); /* should not reach callback */
    -+	check_each(ot, "3210", "321");
    -+	check_each(ot, "32100", "321");
    ++	FILL_TREE(ot, "f", "9", "8", "123", "321", "320", "a", "b", "c", "d", "e");
    ++	check_each(ot, "12300", "123", NULL);
    ++	check_each(ot, "3211", NULL); /* should not reach callback */
    ++	check_each(ot, "3210", "321", NULL);
    ++	check_each(ot, "32100", "321", NULL);
    ++	check_each(ot, "32", "320", "321", NULL);
     +}
     +
     +int cmd_main(int argc UNUSED, const char **argv UNUSED)

 Makefile                 |   8 ++-
 t/helper/test-oidtree.c  |  54 -----------------
 t/helper/test-tool.c     |   1 -
 t/helper/test-tool.h     |   1 -
 t/t0069-oidtree.sh       |  50 ----------------
 t/unit-tests/lib-oid.c   |  52 +++++++++++++++++
 t/unit-tests/lib-oid.h   |  17 ++++++
 t/unit-tests/t-oidtree.c | 121 +++++++++++++++++++++++++++++++++++++++
 8 files changed, 196 insertions(+), 108 deletions(-)
 delete mode 100644 t/helper/test-oidtree.c
 delete mode 100755 t/t0069-oidtree.sh
 create mode 100644 t/unit-tests/lib-oid.c
 create mode 100644 t/unit-tests/lib-oid.h
 create mode 100644 t/unit-tests/t-oidtree.c

diff --git a/Makefile b/Makefile
index 2f5f16847a..03751e0fc0 100644
--- a/Makefile
+++ b/Makefile
@@ -811,7 +811,6 @@ TEST_BUILTINS_OBJS += test-mergesort.o
 TEST_BUILTINS_OBJS += test-mktemp.o
 TEST_BUILTINS_OBJS += test-oid-array.o
 TEST_BUILTINS_OBJS += test-oidmap.o
-TEST_BUILTINS_OBJS += test-oidtree.o
 TEST_BUILTINS_OBJS += test-online-cpus.o
 TEST_BUILTINS_OBJS += test-pack-mtimes.o
 TEST_BUILTINS_OBJS += test-parse-options.o
@@ -1335,6 +1334,7 @@ THIRD_PARTY_SOURCES += sha1dc/%
 
 UNIT_TEST_PROGRAMS += t-ctype
 UNIT_TEST_PROGRAMS += t-mem-pool
+UNIT_TEST_PROGRAMS += t-oidtree
 UNIT_TEST_PROGRAMS += t-prio-queue
 UNIT_TEST_PROGRAMS += t-strbuf
 UNIT_TEST_PROGRAMS += t-strcmp-offset
@@ -1343,6 +1343,7 @@ UNIT_TEST_PROGRAMS += t-trailer
 UNIT_TEST_PROGS = $(patsubst %,$(UNIT_TEST_BIN)/%$X,$(UNIT_TEST_PROGRAMS))
 UNIT_TEST_OBJS = $(patsubst %,$(UNIT_TEST_DIR)/%.o,$(UNIT_TEST_PROGRAMS))
 UNIT_TEST_OBJS += $(UNIT_TEST_DIR)/test-lib.o
+UNIT_TEST_OBJS += $(UNIT_TEST_DIR)/lib-oid.o
 
 # xdiff and reftable libs may in turn depend on what is in libgit.a
 GITLIBS = common-main.o $(LIB_FILE) $(XDIFF_LIB) $(REFTABLE_LIB) $(LIB_FILE)
@@ -3883,7 +3884,10 @@ $(FUZZ_PROGRAMS): %: %.o oss-fuzz/dummy-cmd-main.o $(GITLIBS) GIT-LDFLAGS
 		-Wl,--allow-multiple-definition \
 		$(filter %.o,$^) $(filter %.a,$^) $(LIBS) $(LIB_FUZZING_ENGINE)
 
-$(UNIT_TEST_PROGS): $(UNIT_TEST_BIN)/%$X: $(UNIT_TEST_DIR)/%.o $(UNIT_TEST_DIR)/test-lib.o $(GITLIBS) GIT-LDFLAGS
+$(UNIT_TEST_PROGS): $(UNIT_TEST_BIN)/%$X: $(UNIT_TEST_DIR)/%.o \
+	$(UNIT_TEST_DIR)/test-lib.o \
+	$(UNIT_TEST_DIR)/lib-oid.o \
+	$(GITLIBS) GIT-LDFLAGS
 	$(call mkdir_p_parent_template)
 	$(QUIET_LINK)$(CC) $(ALL_CFLAGS) -o $@ $(ALL_LDFLAGS) \
 		$(filter %.o,$^) $(filter %.a,$^) $(LIBS)
diff --git a/t/helper/test-oidtree.c b/t/helper/test-oidtree.c
deleted file mode 100644
index c7a1d4c642..0000000000
--- a/t/helper/test-oidtree.c
+++ /dev/null
@@ -1,54 +0,0 @@
-#include "test-tool.h"
-#include "hex.h"
-#include "oidtree.h"
-#include "setup.h"
-#include "strbuf.h"
-
-static enum cb_next print_oid(const struct object_id *oid, void *data UNUSED)
-{
-	puts(oid_to_hex(oid));
-	return CB_CONTINUE;
-}
-
-int cmd__oidtree(int argc UNUSED, const char **argv UNUSED)
-{
-	struct oidtree ot;
-	struct strbuf line = STRBUF_INIT;
-	int nongit_ok;
-	int algo = GIT_HASH_UNKNOWN;
-
-	oidtree_init(&ot);
-	setup_git_directory_gently(&nongit_ok);
-
-	while (strbuf_getline(&line, stdin) != EOF) {
-		const char *arg;
-		struct object_id oid;
-
-		if (skip_prefix(line.buf, "insert ", &arg)) {
-			if (get_oid_hex_any(arg, &oid) == GIT_HASH_UNKNOWN)
-				die("insert not a hexadecimal oid: %s", arg);
-			algo = oid.algo;
-			oidtree_insert(&ot, &oid);
-		} else if (skip_prefix(line.buf, "contains ", &arg)) {
-			if (get_oid_hex(arg, &oid))
-				die("contains not a hexadecimal oid: %s", arg);
-			printf("%d\n", oidtree_contains(&ot, &oid));
-		} else if (skip_prefix(line.buf, "each ", &arg)) {
-			char buf[GIT_MAX_HEXSZ + 1] = { '0' };
-			memset(&oid, 0, sizeof(oid));
-			memcpy(buf, arg, strlen(arg));
-			buf[hash_algos[algo].hexsz] = '\0';
-			get_oid_hex_any(buf, &oid);
-			oid.algo = algo;
-			oidtree_each(&ot, &oid, strlen(arg), print_oid, NULL);
-		} else if (!strcmp(line.buf, "clear")) {
-			oidtree_clear(&ot);
-		} else {
-			die("unknown command: %s", line.buf);
-		}
-	}
-
-	strbuf_release(&line);
-
-	return 0;
-}
diff --git a/t/helper/test-tool.c b/t/helper/test-tool.c
index 7ad7d07018..253324a06b 100644
--- a/t/helper/test-tool.c
+++ b/t/helper/test-tool.c
@@ -46,7 +46,6 @@ static struct test_cmd cmds[] = {
 	{ "mktemp", cmd__mktemp },
 	{ "oid-array", cmd__oid_array },
 	{ "oidmap", cmd__oidmap },
-	{ "oidtree", cmd__oidtree },
 	{ "online-cpus", cmd__online_cpus },
 	{ "pack-mtimes", cmd__pack_mtimes },
 	{ "parse-options", cmd__parse_options },
diff --git a/t/helper/test-tool.h b/t/helper/test-tool.h
index d14b3072bd..460dd7d260 100644
--- a/t/helper/test-tool.h
+++ b/t/helper/test-tool.h
@@ -39,7 +39,6 @@ int cmd__match_trees(int argc, const char **argv);
 int cmd__mergesort(int argc, const char **argv);
 int cmd__mktemp(int argc, const char **argv);
 int cmd__oidmap(int argc, const char **argv);
-int cmd__oidtree(int argc, const char **argv);
 int cmd__online_cpus(int argc, const char **argv);
 int cmd__pack_mtimes(int argc, const char **argv);
 int cmd__parse_options(int argc, const char **argv);
diff --git a/t/t0069-oidtree.sh b/t/t0069-oidtree.sh
deleted file mode 100755
index 889db50818..0000000000
--- a/t/t0069-oidtree.sh
+++ /dev/null
@@ -1,50 +0,0 @@
-#!/bin/sh
-
-test_description='basic tests for the oidtree implementation'
-TEST_PASSES_SANITIZE_LEAK=true
-. ./test-lib.sh
-
-maxhexsz=$(test_oid hexsz)
-echoid () {
-	prefix="${1:+$1 }"
-	shift
-	while test $# -gt 0
-	do
-		shortoid="$1"
-		shift
-		difference=$(($maxhexsz - ${#shortoid}))
-		printf "%s%s%0${difference}d\\n" "$prefix" "$shortoid" "0"
-	done
-}
-
-test_expect_success 'oidtree insert and contains' '
-	cat >expect <<-\EOF &&
-		0
-		0
-		0
-		1
-		1
-		0
-	EOF
-	{
-		echoid insert 444 1 2 3 4 5 a b c d e &&
-		echoid contains 44 441 440 444 4440 4444 &&
-		echo clear
-	} | test-tool oidtree >actual &&
-	test_cmp expect actual
-'
-
-test_expect_success 'oidtree each' '
-	echoid "" 123 321 321 >expect &&
-	{
-		echoid insert f 9 8 123 321 a b c d e &&
-		echo each 12300 &&
-		echo each 3211 &&
-		echo each 3210 &&
-		echo each 32100 &&
-		echo clear
-	} | test-tool oidtree >actual &&
-	test_cmp expect actual
-'
-
-test_done
diff --git a/t/unit-tests/lib-oid.c b/t/unit-tests/lib-oid.c
new file mode 100644
index 0000000000..37105f0a8f
--- /dev/null
+++ b/t/unit-tests/lib-oid.c
@@ -0,0 +1,52 @@
+#include "test-lib.h"
+#include "lib-oid.h"
+#include "strbuf.h"
+#include "hex.h"
+
+static int init_hash_algo(void)
+{
+	static int algo = -1;
+
+	if (algo < 0) {
+		const char *algo_name = getenv("GIT_TEST_DEFAULT_HASH");
+		algo = algo_name ? hash_algo_by_name(algo_name) : GIT_HASH_SHA1;
+
+		if (!check(algo != GIT_HASH_UNKNOWN))
+			test_msg("BUG: invalid GIT_TEST_DEFAULT_HASH value ('%s')",
+				 algo_name);
+	}
+	return algo;
+}
+
+static int get_oid_arbitrary_hex_algop(const char *hex, struct object_id *oid,
+				       const struct git_hash_algo *algop)
+{
+	int ret;
+	size_t sz = strlen(hex);
+	struct strbuf buf = STRBUF_INIT;
+
+	if (!check(sz <= algop->hexsz)) {
+		test_msg("BUG: hex string (%s) bigger than maximum allowed (%lu)",
+			 hex, (unsigned long)algop->hexsz);
+		return -1;
+	}
+
+	strbuf_add(&buf, hex, sz);
+	strbuf_addchars(&buf, '0', algop->hexsz - sz);
+
+	ret = get_oid_hex_algop(buf.buf, oid, algop);
+	if (!check_int(ret, ==, 0))
+		test_msg("BUG: invalid hex input (%s) provided", hex);
+
+	strbuf_release(&buf);
+	return ret;
+}
+
+int get_oid_arbitrary_hex(const char *hex, struct object_id *oid)
+{
+	int hash_algo = init_hash_algo();
+
+	if (!check_int(hash_algo, !=, GIT_HASH_UNKNOWN))
+		return -1;
+	return get_oid_arbitrary_hex_algop(hex, oid, &hash_algos[hash_algo]);
+}
diff --git a/t/unit-tests/lib-oid.h b/t/unit-tests/lib-oid.h
new file mode 100644
index 0000000000..bfde639190
--- /dev/null
+++ b/t/unit-tests/lib-oid.h
@@ -0,0 +1,17 @@
+#ifndef LIB_OID_H
+#define LIB_OID_H
+
+#include "hash-ll.h"
+
+/*
+ * Convert arbitrary hex string to object_id.
+ * For example, passing "abc12" will generate
+ * "abc1200000000000000000000000000000000000" hex of length 40 for SHA-1 and
+ * create object_id with that.
+ * WARNING: passing a string of length more than the hexsz of respective hash
+ * algo is not allowed. The hash algo is decided based on GIT_TEST_DEFAULT_HASH
+ * environment variable.
+ */
+int get_oid_arbitrary_hex(const char *s, struct object_id *oid);
+
+#endif /* LIB_OID_H */
diff --git a/t/unit-tests/t-oidtree.c b/t/unit-tests/t-oidtree.c
new file mode 100644
index 0000000000..80cbab0394
--- /dev/null
+++ b/t/unit-tests/t-oidtree.c
@@ -0,0 +1,121 @@
+#include "test-lib.h"
+#include "lib-oid.h"
+#include "oidtree.h"
+#include "hash.h"
+#include "hex.h"
+#include "strvec.h"
+
+#define FILL_TREE(tree, ...)                                       \
+	do {                                                       \
+		const char *hexes[] = { __VA_ARGS__ };             \
+		if (fill_tree_loc(tree, hexes, ARRAY_SIZE(hexes))) \
+			return;                                    \
+	} while (0)
+
+static int fill_tree_loc(struct oidtree *ot, const char *hexes[], size_t n)
+{
+	for (size_t i = 0; i < n; i++) {
+		struct object_id oid;
+		if (!check_int(get_oid_arbitrary_hex(hexes[i], &oid), ==, 0))
+			return -1;
+		oidtree_insert(ot, &oid);
+	}
+	return 0;
+}
+
+static void check_contains(struct oidtree *ot, const char *hex, int expected)
+{
+	struct object_id oid;
+
+	if (!check_int(get_oid_arbitrary_hex(hex, &oid), ==, 0))
+		return;
+	if (!check_int(oidtree_contains(ot, &oid), ==, expected))
+		test_msg("oid: %s", oid_to_hex(&oid));
+}
+
+struct expected_hex_iter {
+	size_t i;
+	struct strvec expected_hexes;
+	const char *query;
+};
+
+static enum cb_next check_each_cb(const struct object_id *oid, void *data)
+{
+	struct expected_hex_iter *hex_iter = data;
+	struct object_id expected;
+
+	if (!check_int(hex_iter->i, <, hex_iter->expected_hexes.nr)) {
+		test_msg("error: extraneous callback for query: ('%s'), object_id: ('%s')",
+			 hex_iter->query, oid_to_hex(oid));
+		return CB_BREAK;
+	}
+
+	if (!check_int(get_oid_arbitrary_hex(hex_iter->expected_hexes.v[hex_iter->i],
+					     &expected), ==, 0))
+		; /* the data is bogus and cannot be used */
+	else if (!check(oideq(oid, &expected)))
+		test_msg("expected: %s\n       got: %s\n     query: %s",
+			 oid_to_hex(&expected), oid_to_hex(oid), hex_iter->query);
+
+	hex_iter->i += 1;
+	return CB_CONTINUE;
+}
+
+static void check_each(struct oidtree *ot, char *query, ...)
+{
+	struct object_id oid;
+	struct expected_hex_iter hex_iter = { .expected_hexes = STRVEC_INIT,
+					      .query = query };
+	const char *arg;
+	va_list hex_args;
+
+	va_start(hex_args, query);
+	while ((arg = va_arg(hex_args, const char *)))
+		strvec_push(&hex_iter.expected_hexes, arg);
+	va_end(hex_args);
+
+	if (!check_int(get_oid_arbitrary_hex(query, &oid), ==, 0))
+		return;
+	oidtree_each(ot, &oid, strlen(query), check_each_cb, &hex_iter);
+
+	if (!check_int(hex_iter.i, ==, hex_iter.expected_hexes.nr))
+		test_msg("error: could not find some 'object_id's for query ('%s')", query);
+	strvec_clear(&hex_iter.expected_hexes);
+}
+
+static void setup(void (*f)(struct oidtree *ot))
+{
+	struct oidtree ot;
+
+	oidtree_init(&ot);
+	f(&ot);
+	oidtree_clear(&ot);
+}
+
+static void t_contains(struct oidtree *ot)
+{
+	FILL_TREE(ot, "444", "1", "2", "3", "4", "5", "a", "b", "c", "d", "e");
+	check_contains(ot, "44", 0);
+	check_contains(ot, "441", 0);
+	check_contains(ot, "440", 0);
+	check_contains(ot, "444", 1);
+	check_contains(ot, "4440", 1);
+	check_contains(ot, "4444", 0);
+}
+
+static void t_each(struct oidtree *ot)
+{
+	FILL_TREE(ot, "f", "9", "8", "123", "321", "320", "a", "b", "c", "d", "e");
+	check_each(ot, "12300", "123", NULL);
+	check_each(ot, "3211", NULL); /* should not reach callback */
+	check_each(ot, "3210", "321", NULL);
+	check_each(ot, "32100", "321", NULL);
+	check_each(ot, "32", "320", "321", NULL);
+}
+
+int cmd_main(int argc UNUSED, const char **argv UNUSED)
+{
+	TEST(setup(t_contains), "oidtree insert and contains works");
+	TEST(setup(t_each), "oidtree each works");
+	return test_done();
+}
-- 
2.45.2

Re: [GSoC][PATCH v2] t/: migrate helper/test-oidtree.c to unit-tests/t-oidtree.c

[Junio C Hamano]

Ghanshyam Thakkar <shyamthakkar001@gmail.com> writes:

> helper/test-oidtree.c along with t0069-oidtree.sh test the oidtree.h
> library, which is a wrapper around crit-bit tree. Migrate them to
> the unit testing framework for better debugging and runtime
> performance. Along with the migration, add an extra check for
> oidtree_each() test, which showcases how multiple expected matches can
> be given to check_each() helper.
> ...

Use "LAST_ARG_MUST_BE_NULL" here, probably.
> +static void check_each(struct oidtree *ot, char *query, ...)
> +{
> +	struct object_id oid;
> +	struct expected_hex_iter hex_iter = { .expected_hexes = STRVEC_INIT,
> ...
> +static void t_each(struct oidtree *ot)
> +{
> +	FILL_TREE(ot, "f", "9", "8", "123", "321", "320", "a", "b", "c", "d", "e");
> +	check_each(ot, "12300", "123", NULL);
> +	check_each(ot, "3211", NULL); /* should not reach callback */

This one truly checks that the callback is never called with this
version, which is way better than the previous one (or the
original).

> +	check_each(ot, "3210", "321", NULL);
> +	check_each(ot, "32100", "321", NULL);
> +	check_each(ot, "32", "320", "321", NULL);
> +}
> +
> +int cmd_main(int argc UNUSED, const char **argv UNUSED)
> +{
> +	TEST(setup(t_contains), "oidtree insert and contains works");
> +	TEST(setup(t_each), "oidtree each works");
> +	return test_done();
> +}

Re: [GSoC][PATCH v2] t/: migrate helper/test-oidtree.c to unit-tests/t-oidtree.c

[Ghanshyam Thakkar]

On Mon, 10 Jun 2024, Junio C Hamano <gitster@pobox.com> wrote:
> Ghanshyam Thakkar <shyamthakkar001@gmail.com> writes:
> 
> > helper/test-oidtree.c along with t0069-oidtree.sh test the oidtree.h
> > library, which is a wrapper around crit-bit tree. Migrate them to
> > the unit testing framework for better debugging and runtime
> > performance. Along with the migration, add an extra check for
> > oidtree_each() test, which showcases how multiple expected matches can
> > be given to check_each() helper.
> > ...
> 
> Use "LAST_ARG_MUST_BE_NULL" here, probably.
> > +static void check_each(struct oidtree *ot, char *query, ...)

I see that you already made this change in merge-fix/gt/unit-test-oidtree.
Thanks for that.

Re: [GSoC][PATCH v2] t/: migrate helper/test-oidtree.c to unit-tests/t-oidtree.c

[Junio C Hamano]

Ghanshyam Thakkar <shyamthakkar001@gmail.com> writes:

> On Mon, 10 Jun 2024, Junio C Hamano <gitster@pobox.com> wrote:
>> Ghanshyam Thakkar <shyamthakkar001@gmail.com> writes:
>> 
>> > helper/test-oidtree.c along with t0069-oidtree.sh test the oidtree.h
>> > library, which is a wrapper around crit-bit tree. Migrate them to
>> > the unit testing framework for better debugging and runtime
>> > performance. Along with the migration, add an extra check for
>> > oidtree_each() test, which showcases how multiple expected matches can
>> > be given to check_each() helper.
>> > ...
>> 
>> Use "LAST_ARG_MUST_BE_NULL" here, probably.
>> > +static void check_each(struct oidtree *ot, char *query, ...)
>
> I see that you already made this change in merge-fix/gt/unit-test-oidtree.
> Thanks for that.

That is merely tentative.  LAST_ARG_MUST_BE_NULL must be on the base
topic, as it is not something that suddenly becomes required after
getting merged to the integration branch (unlike other changes in
the merge-fix which became necessary in the world order after Patrick's
const string fixes are merged).

I do not know what other fixes are needed, and if there is nothing
else that needs to be done in gt/unit-test-oidtree topic, I can do
"git commit --amend" before merging it to 'next' (unless I forget,
that is ;-)), but if you are rerolling, please do not forget to add
that (you do not need to do the constness changes, which will require
you to rebase on top of whatever contains Patrick's work).

Thanks.

Re: [GSoC][PATCH v2] t/: migrate helper/test-oidtree.c to unit-tests/t-oidtree.c

[Ghanshyam Thakkar]

On Mon, 10 Jun 2024, Junio C Hamano <gitster@pobox.com> wrote:
> Ghanshyam Thakkar <shyamthakkar001@gmail.com> writes:
> 
> > On Mon, 10 Jun 2024, Junio C Hamano <gitster@pobox.com> wrote:
> >> Ghanshyam Thakkar <shyamthakkar001@gmail.com> writes:
> >> 
> >> > helper/test-oidtree.c along with t0069-oidtree.sh test the oidtree.h
> >> > library, which is a wrapper around crit-bit tree. Migrate them to
> >> > the unit testing framework for better debugging and runtime
> >> > performance. Along with the migration, add an extra check for
> >> > oidtree_each() test, which showcases how multiple expected matches can
> >> > be given to check_each() helper.
> >> > ...
> >> 
> >> Use "LAST_ARG_MUST_BE_NULL" here, probably.
> >> > +static void check_each(struct oidtree *ot, char *query, ...)
> >
> > I see that you already made this change in merge-fix/gt/unit-test-oidtree.
> > Thanks for that.
> 
> That is merely tentative.  LAST_ARG_MUST_BE_NULL must be on the base
> topic, as it is not something that suddenly becomes required after
> getting merged to the integration branch (unlike other changes in
> the merge-fix which became necessary in the world order after Patrick's
> const string fixes are merged).
> 
> I do not know what other fixes are needed, and if there is nothing
> else that needs to be done in gt/unit-test-oidtree topic, I can do
> "git commit --amend" before merging it to 'next' (unless I forget,
> that is ;-)), but if you are rerolling, please do not forget to add
> that (you do not need to do the constness changes, which will require
> you to rebase on top of whatever contains Patrick's work).

Yeah, I'll reroll as rebasing on 'ps/no-writable-strings' did produce some
errors but the change required was minimal, so I'll include it anyway:

diff --git a/t/unit-tests/t-oidtree.c b/t/unit-tests/t-oidtree.c
index cecefde899..a38754b066 100644
--- a/t/unit-tests/t-oidtree.c
+++ b/t/unit-tests/t-oidtree.c
@@ -62,7 +62,7 @@ static enum cb_next check_each_cb(const struct object_id *oid, void *data)
 }

 LAST_ARG_MUST_BE_NULL
-static void check_each(struct oidtree *ot, char *query, ...)
+static void check_each(struct oidtree *ot, const char *query, ...)
 {
        struct object_id oid;
        struct expected_hex_iter hex_iter = { .expected_hexes = STRVEC_INIT,

Thanks.

Re: [GSoC][PATCH v2] t/: migrate helper/test-oidtree.c to unit-tests/t-oidtree.c

[Junio C Hamano]

Ghanshyam Thakkar <shyamthakkar001@gmail.com> writes:

> Yeah, I'll reroll as rebasing on 'ps/no-writable-strings' did produce some
> errors but the change required was minimal, so I'll include it anyway:
>
> diff --git a/t/unit-tests/t-oidtree.c b/t/unit-tests/t-oidtree.c
> index cecefde899..a38754b066 100644
> --- a/t/unit-tests/t-oidtree.c
> +++ b/t/unit-tests/t-oidtree.c
> @@ -62,7 +62,7 @@ static enum cb_next check_each_cb(const struct object_id *oid, void *data)
>  }
>
>  LAST_ARG_MUST_BE_NULL
> -static void check_each(struct oidtree *ot, char *query, ...)
> +static void check_each(struct oidtree *ot, const char *query, ...)
>  {
>         struct object_id oid;
>         struct expected_hex_iter hex_iter = { .expected_hexes = STRVEC_INIT,

I somehow suspect that you do not even need to depend on the
Patrick's series---tightening the constness in the function
signature by itself is a good thing as you are not writing into
"query" anyway, even without his topic.

Thanks.

Re: [GSoC][PATCH v2] t/: migrate helper/test-oidtree.c to unit-tests/t-oidtree.c

[Ghanshyam Thakkar]

On Mon, 10 Jun 2024, Junio C Hamano <gitster@pobox.com> wrote:
> Ghanshyam Thakkar <shyamthakkar001@gmail.com> writes:
> 
> > Yeah, I'll reroll as rebasing on 'ps/no-writable-strings' did produce some
> > errors but the change required was minimal, so I'll include it anyway:
> >
> > diff --git a/t/unit-tests/t-oidtree.c b/t/unit-tests/t-oidtree.c
> > index cecefde899..a38754b066 100644
> > --- a/t/unit-tests/t-oidtree.c
> > +++ b/t/unit-tests/t-oidtree.c
> > @@ -62,7 +62,7 @@ static enum cb_next check_each_cb(const struct object_id *oid, void *data)
> >  }
> >
> >  LAST_ARG_MUST_BE_NULL
> > -static void check_each(struct oidtree *ot, char *query, ...)
> > +static void check_each(struct oidtree *ot, const char *query, ...)
> >  {
> >         struct object_id oid;
> >         struct expected_hex_iter hex_iter = { .expected_hexes = STRVEC_INIT,
> 
> I somehow suspect that you do not even need to depend on the
> Patrick's series---tightening the constness in the function
> signature by itself is a good thing as you are not writing into
> "query" anyway, even without his topic.

I'll clarify "I'll reroll as rebasing..." -> "I'll reroll, as rebasing..." 

Yeah, I meant as not depending on 'ps/no-writable-strings' but only
including the diff above. But since you already did that, I'll refrain from
sending another version unless some other changes are required. :)

Thanks.