From 9d46bc791b77e059deb740fde3439a0417a91b5e Mon Sep 17 00:00:00 2001 From: Derrick Stolee Date: Fri, 20 Dec 2024 16:21:09 +0000 Subject: path-walk: introduce an object walk by path In anticipation of a few planned applications, introduce the most basic form of a path-walk API. It currently assumes that there are no UNINTERESTING objects, and does not include any complicated filters. It calls a function pointer on groups of tree and blob objects as grouped by path. This only includes objects the first time they are discovered, so an object that appears at multiple paths will not be included in two batches. These batches are collected in 'struct type_and_oid_list' objects, which store an object type and an oid_array of objects. The data structures are documented in 'struct path_walk_context', but in summary the most important are: * 'paths_to_lists' is a strmap that connects a path to a type_and_oid_list for that path. To avoid conflicts in path names, we make sure that tree paths end in "/" (except the root path with is an empty string) and blob paths do not end in "/". * 'path_stack' is a string list that is added to in an append-only way. This stores the stack of our depth-first search on the heap instead of using recursion. * 'path_stack_pushed' is a strmap that stores path names that were already added to 'path_stack', to avoid repeating paths in the stack. Mostly, this saves us from quadratic lookups from doing unsorted checks into the string_list. The coupling of 'path_stack' and 'path_stack_pushed' is protected by the push_to_stack() method. Call this instead of inserting into these structures directly. The walk_objects_by_path() method initializes these structures and starts walking commits from the given rev_info struct. The commits are used to find the list of root trees which populate the start of our depth-first search. The core of our depth-first search is in a while loop that continues while we have not indicated an early exit and our 'path_stack' still has entries in it. The loop body pops a path off of the stack and "visits" the path via the walk_path() method. The walk_path() method gets the list of OIDs from the 'path_to_lists' strmap and executes the callback method on that list with the given path and type. If the OIDs correspond to tree objects, then iterate over all trees in the list and run add_children() to add the child objects to their own lists, adding new entries to the stack if necessary. In testing, this depth-first search approach was the one that used the least memory while iterating over the object lists. There is still a chance that repositories with too-wide path patterns could cause memory pressure issues. Limiting the stack size could be done in the future by limiting how many objects are being considered in-progress, or by visiting blob paths earlier than trees. There are many future adaptations that could be made, but they are left for future updates when consumers are ready to take advantage of those features. Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano --- Makefile | 1 + 1 file changed, 1 insertion(+) (limited to 'Makefile') diff --git a/Makefile b/Makefile index 8d8cc6ab90..1b2abad3b4 100644 --- a/Makefile +++ b/Makefile @@ -1098,6 +1098,7 @@ LIB_OBJS += parse-options.o LIB_OBJS += patch-delta.o LIB_OBJS += patch-ids.o LIB_OBJS += path.o +LIB_OBJS += path-walk.o LIB_OBJS += pathspec.o LIB_OBJS += pkt-line.o LIB_OBJS += preload-index.o -- cgit v1.3 From d190124f277952bd828f932d87e76deabedf0c83 Mon Sep 17 00:00:00 2001 From: Derrick Stolee Date: Fri, 20 Dec 2024 16:21:11 +0000 Subject: t6601: add helper for testing path-walk API Add some tests based on the current behavior, doing interesting checks for different sets of branches, ranges, and the --boundary option. This sets a baseline for the behavior and we can extend it as new options are introduced. Store and output a 'batch_nr' value so we can demonstrate that the paths are grouped together in a batch and not following some other ordering. This allows us to test the depth-first behavior of the path-walk API. However, we purposefully do not test the order of the objects in the batch, so the output is compared to the expected output through a sort. It is important to mention that the behavior of the API will change soon as we start to handle UNINTERESTING objects differently, but these tests will demonstrate the change in behavior. Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano --- Documentation/technical/api-path-walk.txt | 3 +- Makefile | 1 + t/helper/test-path-walk.c | 84 +++++++++++++++++++++ t/helper/test-tool.c | 1 + t/helper/test-tool.h | 1 + t/t6601-path-walk.sh | 120 ++++++++++++++++++++++++++++++ 6 files changed, 209 insertions(+), 1 deletion(-) create mode 100644 t/helper/test-path-walk.c create mode 100755 t/t6601-path-walk.sh (limited to 'Makefile') diff --git a/Documentation/technical/api-path-walk.txt b/Documentation/technical/api-path-walk.txt index c550c77ca3..662162ec70 100644 --- a/Documentation/technical/api-path-walk.txt +++ b/Documentation/technical/api-path-walk.txt @@ -42,4 +42,5 @@ commits. Examples -------- -See example usages in future changes. +See example usages in: + `t/helper/test-path-walk.c` diff --git a/Makefile b/Makefile index 1b2abad3b4..e0b9e14a68 100644 --- a/Makefile +++ b/Makefile @@ -822,6 +822,7 @@ TEST_BUILTINS_OBJS += test-parse-options.o TEST_BUILTINS_OBJS += test-parse-pathspec-file.o TEST_BUILTINS_OBJS += test-partial-clone.o TEST_BUILTINS_OBJS += test-path-utils.o +TEST_BUILTINS_OBJS += test-path-walk.o TEST_BUILTINS_OBJS += test-pcre2-config.o TEST_BUILTINS_OBJS += test-pkt-line.o TEST_BUILTINS_OBJS += test-proc-receive.o diff --git a/t/helper/test-path-walk.c b/t/helper/test-path-walk.c new file mode 100644 index 0000000000..def7c81ac4 --- /dev/null +++ b/t/helper/test-path-walk.c @@ -0,0 +1,84 @@ +#define USE_THE_REPOSITORY_VARIABLE + +#include "test-tool.h" +#include "environment.h" +#include "hex.h" +#include "object-name.h" +#include "object.h" +#include "pretty.h" +#include "revision.h" +#include "setup.h" +#include "parse-options.h" +#include "path-walk.h" +#include "oid-array.h" + +static const char * const path_walk_usage[] = { + N_("test-tool path-walk -- "), + NULL +}; + +struct path_walk_test_data { + uintmax_t batch_nr; + uintmax_t tree_nr; + uintmax_t blob_nr; +}; + +static int emit_block(const char *path, struct oid_array *oids, + enum object_type type, void *data) +{ + struct path_walk_test_data *tdata = data; + const char *typestr; + + if (type == OBJ_TREE) + tdata->tree_nr += oids->nr; + else if (type == OBJ_BLOB) + tdata->blob_nr += oids->nr; + else + BUG("we do not understand this type"); + + typestr = type_name(type); + + for (size_t i = 0; i < oids->nr; i++) + printf("%"PRIuMAX":%s:%s:%s\n", + tdata->batch_nr, typestr, path, + oid_to_hex(&oids->oid[i])); + + tdata->batch_nr++; + return 0; +} + +int cmd__path_walk(int argc, const char **argv) +{ + int res; + struct rev_info revs = REV_INFO_INIT; + struct path_walk_info info = PATH_WALK_INFO_INIT; + struct path_walk_test_data data = { 0 }; + struct option options[] = { + OPT_END(), + }; + + setup_git_directory(); + revs.repo = the_repository; + + argc = parse_options(argc, argv, NULL, + options, path_walk_usage, + PARSE_OPT_KEEP_UNKNOWN_OPT | PARSE_OPT_KEEP_ARGV0); + + if (argc > 1) + setup_revisions(argc, argv, &revs, NULL); + else + usage(path_walk_usage[0]); + + info.revs = &revs; + info.path_fn = emit_block; + info.path_fn_data = &data; + + res = walk_objects_by_path(&info); + + printf("trees:%" PRIuMAX "\n" + "blobs:%" PRIuMAX "\n", + data.tree_nr, data.blob_nr); + + release_revisions(&revs); + return res; +} diff --git a/t/helper/test-tool.c b/t/helper/test-tool.c index 1ebb69a5dc..43676e7b93 100644 --- a/t/helper/test-tool.c +++ b/t/helper/test-tool.c @@ -52,6 +52,7 @@ static struct test_cmd cmds[] = { { "parse-subcommand", cmd__parse_subcommand }, { "partial-clone", cmd__partial_clone }, { "path-utils", cmd__path_utils }, + { "path-walk", cmd__path_walk }, { "pcre2-config", cmd__pcre2_config }, { "pkt-line", cmd__pkt_line }, { "proc-receive", cmd__proc_receive }, diff --git a/t/helper/test-tool.h b/t/helper/test-tool.h index 21802ac27d..9cfc5da6e5 100644 --- a/t/helper/test-tool.h +++ b/t/helper/test-tool.h @@ -45,6 +45,7 @@ int cmd__parse_pathspec_file(int argc, const char** argv); int cmd__parse_subcommand(int argc, const char **argv); int cmd__partial_clone(int argc, const char **argv); int cmd__path_utils(int argc, const char **argv); +int cmd__path_walk(int argc, const char **argv); int cmd__pcre2_config(int argc, const char **argv); int cmd__pkt_line(int argc, const char **argv); int cmd__proc_receive(int argc, const char **argv); diff --git a/t/t6601-path-walk.sh b/t/t6601-path-walk.sh new file mode 100755 index 0000000000..4e052c0930 --- /dev/null +++ b/t/t6601-path-walk.sh @@ -0,0 +1,120 @@ +#!/bin/sh + +TEST_PASSES_SANITIZE_LEAK=true + +test_description='direct path-walk API tests' + +. ./test-lib.sh + +test_expect_success 'setup test repository' ' + git checkout -b base && + + mkdir left && + mkdir right && + echo a >a && + echo b >left/b && + echo c >right/c && + git add . && + git commit -m "first" && + + echo d >right/d && + git add right && + git commit -m "second" && + + echo bb >left/b && + git commit -a -m "third" && + + git checkout -b topic HEAD~1 && + echo cc >right/c && + git commit -a -m "topic" +' + +test_expect_success 'all' ' + test-tool path-walk -- --all >out && + + cat >expect <<-EOF && + 0:tree::$(git rev-parse topic^{tree}) + 0:tree::$(git rev-parse base^{tree}) + 0:tree::$(git rev-parse base~1^{tree}) + 0:tree::$(git rev-parse base~2^{tree}) + 1:tree:right/:$(git rev-parse topic:right) + 1:tree:right/:$(git rev-parse base~1:right) + 1:tree:right/:$(git rev-parse base~2:right) + 2:blob:right/d:$(git rev-parse base~1:right/d) + 3:blob:right/c:$(git rev-parse base~2:right/c) + 3:blob:right/c:$(git rev-parse topic:right/c) + 4:tree:left/:$(git rev-parse base:left) + 4:tree:left/:$(git rev-parse base~2:left) + 5:blob:left/b:$(git rev-parse base~2:left/b) + 5:blob:left/b:$(git rev-parse base:left/b) + 6:blob:a:$(git rev-parse base~2:a) + blobs:6 + trees:9 + EOF + + test_cmp_sorted expect out +' + +test_expect_success 'topic only' ' + test-tool path-walk -- topic >out && + + cat >expect <<-EOF && + 0:tree::$(git rev-parse topic^{tree}) + 0:tree::$(git rev-parse base~1^{tree}) + 0:tree::$(git rev-parse base~2^{tree}) + 1:tree:right/:$(git rev-parse topic:right) + 1:tree:right/:$(git rev-parse base~1:right) + 1:tree:right/:$(git rev-parse base~2:right) + 2:blob:right/d:$(git rev-parse base~1:right/d) + 3:blob:right/c:$(git rev-parse base~2:right/c) + 3:blob:right/c:$(git rev-parse topic:right/c) + 4:tree:left/:$(git rev-parse base~2:left) + 5:blob:left/b:$(git rev-parse base~2:left/b) + 6:blob:a:$(git rev-parse base~2:a) + blobs:5 + trees:7 + EOF + + test_cmp_sorted expect out +' + +test_expect_success 'topic, not base' ' + test-tool path-walk -- topic --not base >out && + + cat >expect <<-EOF && + 0:tree::$(git rev-parse topic^{tree}) + 1:tree:right/:$(git rev-parse topic:right) + 2:blob:right/d:$(git rev-parse topic:right/d) + 3:blob:right/c:$(git rev-parse topic:right/c) + 4:tree:left/:$(git rev-parse topic:left) + 5:blob:left/b:$(git rev-parse topic:left/b) + 6:blob:a:$(git rev-parse topic:a) + blobs:4 + trees:3 + EOF + + test_cmp_sorted expect out +' + +test_expect_success 'topic, not base, boundary' ' + test-tool path-walk -- --boundary topic --not base >out && + + cat >expect <<-EOF && + 0:tree::$(git rev-parse topic^{tree}) + 0:tree::$(git rev-parse base~1^{tree}) + 1:tree:right/:$(git rev-parse topic:right) + 1:tree:right/:$(git rev-parse base~1:right) + 2:blob:right/d:$(git rev-parse base~1:right/d) + 3:blob:right/c:$(git rev-parse base~1:right/c) + 3:blob:right/c:$(git rev-parse topic:right/c) + 4:tree:left/:$(git rev-parse base~1:left) + 5:blob:left/b:$(git rev-parse base~1:left/b) + 6:blob:a:$(git rev-parse base~1:a) + blobs:5 + trees:5 + EOF + + test_cmp_sorted expect out +' + +test_done -- cgit v1.3