Re: [PATCH 1/1] ls-refs.c: minimize number of refs visited
From: Jacob Vosmaer <hidden>
Date: 2021-01-19 18:42:57
Hi Taylor, Thanks for your reply. That sounds like a great idea! On Tue, Jan 19, 2021 at 5:12 PM Taylor Blau [off-list ref] wrote:
But, I think that we could get pretty far by treating the prefixes as refs so that we can call ref-filter.c:find_longest_prefixes(). For its purposes, it doesn't really care about whether or not the arguments actually are references. It simply returns the longest common prefix among all of its arguments (delimited by '/' characters).
What does "delimited by /" mean? Without really understanding the longest common prefix code in ref-filter.c, my intuitive concern is that the specifics of glob matching and special treatment of '/' may bite us. I suppose we'll be fine because ls-refs has its own matching logic. So long as for_each_fullref_in_prefixes yield enough prefixes, the end result would remain the same. The question is then, does for_each_fullref_in_prefixes yield everything we need? I think my approach would be to expose the new for_each_fullref_in_prefixes iterator you propose through test-tool, and unit test it so we can be sure it handles both contexts (for-each-refs with globs and special '/', and ls-refs without any special character behavior) correctly. I may be overly cautious here, take this with a grain of salt because I am not an experienced Git contributor. On that topic, apologies if I'm botching my inline replies in this email. Regarding your patch: it works correctly and as fast as expected for my development "many refs" test case. Yay! It also segfaults and fails some tests but see my comments below. All in all: thanks, great idea, yes we should reuse, I only lack confidence on correctness because I don't fully grasp your longest-common-prefix algorithm yet. Cheers, Jacob
quoted hunk ↗ jump to hunk
--- >8 ---Subject: [PATCH] ls-refs: iterate longest common refs prefix Signed-off-by: Taylor Blau <redacted> --- ls-refs.c | 4 +++- ref-filter.c | 46 ++++++++++++++++++++++++++++++++-------------- ref-filter.h | 10 ++++++++++ 3 files changed, 45 insertions(+), 15 deletions(-)diff --git a/ls-refs.c b/ls-refs.c index a1e0b473e4..6a3e11d45c 100644 --- a/ls-refs.c +++ b/ls-refs.c@@ -6,6 +6,7 @@ #include "ls-refs.h" #include "pkt-line.h" #include "config.h" +#include "ref-filter.h" /* * Check if one of the prefixes is a prefix of the ref.@@ -109,7 +110,8 @@ int ls_refs(struct repository *r, struct strvec *keys, die(_("expected flush after ls-refs arguments")); head_ref_namespaced(send_ref, &data); - for_each_namespaced_ref(send_ref, &data); + for_each_fullref_in_prefixes(get_git_namespace(), data.prefixes.v, + send_ref, &data, 0);
Remember to add that strvec_init(&data.prefixes) I talked about in my commit message, or you get a segfault. You also need: if (!data.prefixes.nr) strvec_push(&data.prefixes, "refs/"); Without it, the "ls-refs without ref-prefix" scenario fails.
quoted hunk ↗ jump to hunk
packet_flush(1); strvec_clear(&data.prefixes); return 0;diff --git a/ref-filter.c b/ref-filter.c index aa260bfd09..c34bf34d06 100644 --- a/ref-filter.c +++ b/ref-filter.c@@ -1987,6 +1987,36 @@ static void find_longest_prefixes(struct string_list *out, strbuf_release(&prefix); } +int for_each_fullref_in_prefixes(const char *namespace, + const char **patterns, + each_ref_fn cb, + void *cb_data, + int broken) +{ + struct string_list prefixes = STRING_LIST_INIT_DUP; + struct string_list_item *prefix; + struct strbuf buf = STRBUF_INIT; + int ret = 0, namespace_len; + + find_longest_prefixes(&prefixes, patterns); + + if (namespace) + strbuf_addstr(&buf, namespace); + namespace_len = buf.len; + + for_each_string_list_item(prefix, &prefixes) { + strbuf_addf(&buf, prefix->string);
Missing format string "%s".
quoted hunk ↗ jump to hunk
+ ret = for_each_fullref_in(buf.buf, cb, cb_data, broken); + if (ret) + break; + strbuf_setlen(&buf, namespace_len); + } + + string_list_clear(&prefixes, 0); + strbuf_release(&buf); + return ret; +} + /* * This is the same as for_each_fullref_in(), but it tries to iterate * only over the patterns we'll care about. Note that it _doesn't_ do a full@@ -1997,10 +2027,6 @@ static int for_each_fullref_in_pattern(struct ref_filter *filter, void *cb_data, int broken) { - struct string_list prefixes = STRING_LIST_INIT_DUP; - struct string_list_item *prefix; - int ret; - if (!filter->match_as_path) { /* * in this case, the patterns are applied after@@ -2024,16 +2050,8 @@ static int for_each_fullref_in_pattern(struct ref_filter *filter, return for_each_fullref_in("", cb, cb_data, broken); } - find_longest_prefixes(&prefixes, filter->name_patterns); - - for_each_string_list_item(prefix, &prefixes) { - ret = for_each_fullref_in(prefix->string, cb, cb_data, broken); - if (ret) - break; - } - - string_list_clear(&prefixes, 0); - return ret; + return for_each_fullref_in_prefixes(NULL, filter->name_patterns, + cb, cb_data, broken); } /*diff --git a/ref-filter.h b/ref-filter.h index feaef4a8fd..f666a0fb49 100644 --- a/ref-filter.h +++ b/ref-filter.h@@ -146,4 +146,14 @@ struct ref_array_item *ref_array_push(struct ref_array *array, const char *refname, const struct object_id *oid); +/** + * iterate all refs which descend from the longest common prefix among + * "patterns". + */ +int for_each_fullref_in_prefixes(const char *namespace, + const char **patterns, + each_ref_fn cb, + void *cb_data, + int broken); + #endif /* REF_FILTER_H */ --2.30.0.138.g6d7191ea01