[PATCH v2 0/3] ls-refs: traverse prefixes of disjoint "ref-prefix" sets

Here is a reroll of the series I sent yesterday to traverse the longest-common prefixes of disjoint sets containing the ref-prefix arguments to ls-refs.

Not much has changed last time, except some clarification about what 'for_each_fullref_in_prefixes()' can yield, and splitting out the last patch into one from Jacob and one from me. I've forged his sign-off since it contains his original code, but it includes a new patch description from me.

Jacob Vosmaer (1):
  ls-refs.c: initialize 'prefixes' before using it

Taylor Blau (2):
  refs: expose 'for_each_fullref_in_prefixes'
  ls-refs.c: traverse prefixes of disjoint "ref-prefix" sets

 ls-refs.c    |  6 +++-
 ref-filter.c | 74 ++------------------------------------------
 refs.c       | 87 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 refs.h       |  9 ++++++
 4 files changed, 103 insertions(+), 73 deletions(-)

Range-diff against v1:
1:  d4c8d059f6 ! 1:  bda314fe7a refs: expose 'for_each_fullref_in_prefixes'
    @@ Commit message
         common prefix of among a set of refspecs, and then to iterate all of the
         references that descend from that prefix.

    -    The subsequent patch will want to use that same code from ls-refs, so
    +    A future patch will want to use that same code from ls-refs.c, so
         prepare by exposing and moving it to refs.c. Since there is nothing
         specific to the ref-filter code here (other than that it was previously
         the only caller of this function), this really belongs in the more
         generic refs.h header.

    +    The code moved in this patch is identical before and after, with the one
    +    exception of renaming some arguments to be consistent with other
    +    functions exposed in refs.h.
    +
         Signed-off-by: Taylor Blau <me@ttaylorr.com>

      ## ref-filter.c ##
    @@ refs.h: int refs_for_each_fullref_in(struct ref_store *refs, const char *prefix,
      			unsigned int broken);

     +/**
    -+ * iterate all refs which are descendent from the longest common prefix among
    -+ * the list "patterns".
    ++ * iterate all refs in "patterns" by partitioning patterns into disjoint sets
    ++ * and iterating the longest-common prefix of each set.
    ++ *
    ++ * callers should be prepared to ignore references that they did not ask for.
     + */
     +int for_each_fullref_in_prefixes(const char *namespace, const char **patterns,
     +				 each_ref_fn fn, void *cb_data,
-:  ---------- > 2:  5fc081b2d5 ls-refs.c: initialize 'prefixes' before using it
2:  fb8681d128 ! 3:  b97dfb706f ls-refs.c: traverse longest common ref prefix
    @@ Metadata
     Author: Taylor Blau <me@ttaylorr.com>

      ## Commit message ##
    -    ls-refs.c: traverse longest common ref prefix
    +    ls-refs.c: traverse prefixes of disjoint "ref-prefix" sets

         ls-refs performs a single revision walk over the whole ref namespace,
         and sends ones that match with one of the given ref prefixes down to the
    @@ Commit message
         disjoint pattern prefixes, 2019-06-26) which does an analogous thing for
         multi-patterned 'git for-each-ref' invocations.

    -    The only difference here is that we are operating on ref prefixes, which
    -    do not necessarily point to a single reference. That is just fine, since
    -    all we care about is finding the longest common prefix among prefixes
    -    which can be thought of as refspecs for our purposes here.
    -
    -    Similarly, for_each_fullref_in_prefixes may return more results than the
    -    caller asked for (since the longest common prefix might match something
    -    that a longer prefix in the same set wouldn't match) but
    -    ls-refs.c:send_ref() discards such results.
    -
    -    The code introduced in b31e2680c4 is resilient to stop early (and
    -    return a shorter prefix) when it encounters a metacharacter (as
    -    mentioned in that patch, there is some opportunity to improve this, but
    -    nobody has done it).
    -
    -    There are two remaining small items in this patch:
    -
    -      - If no prefixes were provided, then implicitly add the empty string
    -        (which will match all references).
    -
    -      - Since we are manually munging the prefixes, make sure that we
    -        initialize it ourselves (previously this wasn't necessary since the
    -        first strvec_push would do so).
    +    The callback 'send_ref' is resilient to ignore extra patterns by
    +    discarding any arguments which do not begin with at least one of the
    +    specified prefixes.
    +
    +    Similarly, the code introduced in b31e2680c4 is resilient to stop early
    +    at metacharacters, but we only pass strict prefixes here. At worst we
    +    would return too many results, but the double checking done by send_ref
    +    will throw away anything that doesn't start with something in the prefix
    +    list.
    +
    +    Finally, if no prefixes were provided, then implicitly add the empty
    +    string (which will match all references) since this matches the existing
    +    behavior (see the "no restrictions" comment in "ls-refs.c:ref_match()").

         Original-patch-by: Jacob Vosmaer <jacob@gitlab.com>
         Signed-off-by: Taylor Blau <me@ttaylorr.com>

      ## ls-refs.c ##
    -@@ ls-refs.c: int ls_refs(struct repository *r, struct strvec *keys,
    - 	struct ls_refs_data data;
    -
    - 	memset(&data, 0, sizeof(data));
    -+	strvec_init(&data.prefixes);
    -
    - 	git_config(ls_refs_config, NULL);
    -
     @@ ls-refs.c: int ls_refs(struct repository *r, struct strvec *keys,
      		die(_("expected flush after ls-refs arguments"));

-- 2.30.0.138.g6d7191ea01