From: Jacob Vosmaer <jacob@gitlab.com>
To: Taylor Blau <me@ttaylorr.com>
Cc: Git Mailing List <git@vger.kernel.org>
Subject: Re: [PATCH 1/1] ls-refs.c: minimize number of refs visited
Date: Tue, 19 Jan 2021 18:42:56 +0100 [thread overview]
Message-ID: <CADMWQoPREhirr+RJPkJJV2U+8VG=DFotvTBCDSXFhn-3pn2X-A@mail.gmail.com> (raw)
In-Reply-To: <YAcE/dTuOB9PbGQU@nand.local>
Hi Taylor,
Thanks for your reply. That sounds like a great idea!
On Tue, Jan 19, 2021 at 5:12 PM Taylor Blau <me@ttaylorr.com> 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
> --- >8 ---
>
> Subject: [PATCH] ls-refs: iterate longest common refs prefix
>
> Signed-off-by: Taylor Blau <me@ttaylorr.com>
> ---
> 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.
> 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".
> + 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
>
next prev parent reply other threads:[~2021-01-19 18:48 UTC|newest]
Thread overview: 35+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-01-19 14:42 [PATCH 0/1] ls-refs.c: minimize number of refs visited Jacob Vosmaer
2021-01-19 14:42 ` [PATCH 1/1] " Jacob Vosmaer
2021-01-19 16:12 ` Taylor Blau
2021-01-19 17:42 ` Jacob Vosmaer [this message]
2021-01-19 18:19 ` [PATCH 0/2] ls-refs: only traverse through longest common ref prefix Taylor Blau
2021-01-19 18:19 ` [PATCH 1/2] refs: expose 'for_each_fullref_in_prefixes' Taylor Blau
2021-01-19 18:19 ` [PATCH 2/2] ls-refs.c: traverse longest common ref prefix Taylor Blau
2021-01-19 23:09 ` Jeff King
2021-01-19 23:52 ` Taylor Blau
2021-01-20 0:08 ` Jeff King
2021-01-20 11:00 ` Jacob Vosmaer
2021-01-20 16:04 ` [PATCH v2 0/3] ls-refs: traverse prefixes of disjoint "ref-prefix" sets Taylor Blau
2021-01-20 16:04 ` [PATCH v2 1/3] refs: expose 'for_each_fullref_in_prefixes' Taylor Blau
2021-01-20 19:56 ` Jeff King
2021-01-20 20:12 ` Taylor Blau
2021-01-23 2:59 ` Junio C Hamano
2021-01-25 1:35 ` Taylor Blau
2021-01-20 16:04 ` [PATCH v2 2/3] ls-refs.c: initialize 'prefixes' before using it Taylor Blau
2021-01-20 19:58 ` Jeff King
2021-01-20 20:13 ` Taylor Blau
2021-01-20 21:50 ` Jacob Vosmaer
2021-01-20 16:04 ` [PATCH v2 3/3] ls-refs.c: traverse prefixes of disjoint "ref-prefix" sets Taylor Blau
2021-01-23 17:55 ` [PATCH v2 0/3] ls-refs: " Junio C Hamano
2021-01-19 19:09 ` [PATCH 1/1] ls-refs.c: minimize number of refs visited Taylor Blau
2021-01-19 21:59 ` Jeff King
2021-01-19 22:15 ` Jeff King
2021-01-19 22:23 ` Taylor Blau
2021-01-19 22:52 ` Jeff King
2021-01-19 22:59 ` Jeff King
2021-01-19 23:02 ` Taylor Blau
2021-01-19 22:53 ` Jeff King
2021-01-19 23:00 ` Taylor Blau
2021-01-19 23:11 ` Jeff King
2021-01-20 10:40 ` Jacob Vosmaer
2021-01-20 10:44 ` Jacob Vosmaer
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: http://vger.kernel.org/majordomo-info.html
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='CADMWQoPREhirr+RJPkJJV2U+8VG=DFotvTBCDSXFhn-3pn2X-A@mail.gmail.com' \
--to=jacob@gitlab.com \
--cc=git@vger.kernel.org \
--cc=me@ttaylorr.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://80x24.org/mirrors/git.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).