Hi Jacob,
On Thu, Jun 27, 2019 at 04:21:57PM -0700, Jacob Keller wrote:
> On Wed, Jun 26, 2019 at 3:44 PM Taylor Blau <me@xxxxxxxxxxxx> wrote:
> >
>
> Ok, now I've got some time to look at the code itself.
>
> > ref-filter.c | 89 +++++++++++++++++++++++++++++------------
> > t/t6300-for-each-ref.sh | 26 ++++++++++++
> > 2 files changed, 89 insertions(+), 26 deletions(-)
> >
> > diff --git a/ref-filter.c b/ref-filter.c
> > index 8500671bc6..3e10fd647b 100644
> > --- a/ref-filter.c
> > +++ b/ref-filter.c
> > @@ -20,6 +20,7 @@
> > #include "commit-slab.h"
> > #include "commit-graph.h"
> > #include "commit-reach.h"
> > +#include "argv-array.h"
> >
> > static struct ref_msg {
> > const char *gone;
> > @@ -1790,21 +1791,62 @@ static int filter_pattern_match(struct ref_filter *filter, const char *refname)
> > return match_pattern(filter, refname);
> > }
> >
> > -/*
> > - * Find the longest prefix of pattern we can pass to
> > - * `for_each_fullref_in()`, namely the part of pattern preceding the
> > - * first glob character. (Note that `for_each_fullref_in()` is
> > - * perfectly happy working with a prefix that doesn't end at a
> > - * pathname component boundary.)
> > - */
> > -static void find_longest_prefix(struct strbuf *out, const char *pattern)
> > +static int qsort_strcmp(const void *va, const void *vb)
> > {
> > - const char *p;
> > + const char *a = *(const char **)va;
> > + const char *b = *(const char **)vb;
> >
> > - for (p = pattern; *p && !is_glob_special(*p); p++)
> > - ;
> > + return strcmp(a, b);
> > +}
> >
> > - strbuf_add(out, pattern, p - pattern);
> > +static void find_longest_prefixes_1(struct string_list *out,
> > + struct strbuf *prefix,
> > + const char **patterns, size_t nr)
> > +{
> > + size_t i;
> > +
> > + for (i = 0; i < nr; i++) {
> > + char c = patterns[i][prefix->len];
> > + if (!c || is_glob_special(c)) {
> > + string_list_append(out, prefix->buf);
> > + return;
> > + }
> > + }
>
> Ok, so we loop over the patterns, find the last character up to our
> current prefix length, and check if it's either the end of the string,
> or a special glob character. I assume that the patterns are sorted so
> that prefix->len never goes past the array?
That's right. The idea here is that if we compare two patterns character
by character, we can detect where the references "split", and thus
constitute membership of unique disjoint sets.
Consider the following example:
refs/heads/a
refs/heads/b
^
Here, we were given, say 'git for-each-ref refs/heads/a refs/heads/b',
and appropriate queries are:
- '*'
- 'refs/*'
- 'refs/heads/*'
- 'refs/heads/a' with 'refs/heads/b'
When we have advanced our cursor up until the position where the
patterns read 'a', and 'b', respectively, we have built up so far as our
pattern: 'refs/heads/'. We would like to realize that those two can
create two queries, so when we discover that 'a' != 'b', we "split" the
strbuf into two patterns in the next level of recursion.
One alternative view is that we are trying to construct the shortest
paths from the root of the tree to the leaf 'NUL' nodes as below:
a --- NUL
/
refs --- heads
\
b --- NUL
> If we find one, we just add this to the list and return, since we
> found an unambigous one.
>
> Otherwise, we keep searching recursively.
>
> So, prefix is a strbuf, and its length will initially be zero. So, we
> check all patterns, up to the prefix length and check the character
> just past the end of our prefix. If it matches a NUL or glob
> character, then we have found an exact match up to a glob, so this
> gets returned.
Right: two additional wrinkles here.
One is that we don't have very careful handling of wildcard characters,
i.e., between 'a*c' and '*bc' we give up and split those at 'a*', and
'*b' (an equally good query would be '**c'), so treat the presence of a
wildcard character the same way we would a disagreement in character as
above.
The second wrinkle is that we originally wrote this patch looking for
disagreements in _ref component_, i.e., that given 'refs/heads/a' with
'refs/tags/a', we would split because 'heads != tags', not 'h != t'. The
references backend (to my surprise) does per-character matching, so
that's why we do it, too.
> Here, we're going to loop from beginning to end of all of the strings.
>
> > + /*
> > + * Set "end" to the index of the element _after_ the last one
> > + * in our group.
> > + */
> > + for (end = i + 1; end < nr; end++) {
> > + if (patterns[i][prefix->len] != patterns[end][prefix->len])
> > + break;
> > + }
> > +
>
> We break on the first string which doesn't have the same length as our
> current prefix, but start with the ones after the current loop
> iteration.
>
> > + strbuf_addch(prefix, patterns[i][prefix->len]);
> > + find_longest_prefixes_1(out, prefix, patterns + i, end - i);
> > + strbuf_setlen(prefix, prefix->len - 1);
> > +
Right, we have a potentially long list of patterns underneath that we
have just covered, so we can skip those.
> We'll add the next character to the prefix, and then find longest
> prefixes again.
>
> This basically has us recurse and keep adding additional characters,
> essentially splitting the strings apart by their disjoint sets.
>
> I think this works, but it's definitely not clear from reading exactly
> what is going on. I think this algorithm would benefit from a comment,
> since it doesn't quite seem to match your description in the commit
> message.
> > + find_longest_prefixes_1(out, &prefix, sorted.argv, sorted.argc);
> > +
> > + argv_array_clear(&sorted);
> > + strbuf_release(&prefix);
Fair enough, I'm happy to add a comment if others like, too.
Thanks,
Taylor
