On Tue, Aug 20, 2019 at 8:12 AM Derrick Stolee via GitGitGadget
<gitgitgadget@xxxxxxxxx> wrote:
>
> From: Derrick Stolee <dstolee@xxxxxxxxxxxxx>
>
> The parent and recursive patterns allowed by the "cone mode"
> option in sparse-checkout are restrictive enough that we
> can avoid using the regex parsing. Everything is based on
> prefix matches, so we can use hashsets to store the prefixes
> from the sparse-checkout file. When checking a path, we can
> strip path entries from the path and check the hashset for
> an exact match.
>
> As a test, I created a cone-mode sparse-checkout file for the
> Linux repository that actually includes every file. This was
> constructed by taking every folder in the Linux repo and creating
> the pattern pairs here:
>
> /$folder/*
> !/$folder/*/*
>
> This resulted in a sparse-checkout file sith 8,296 patterns.
> Running 'git read-tree -mu HEAD' on this file had the following
> performance:
>
> core.sparseCheckout=false: 0.21 s (0.00 s)
> core.sparseCheckout=true: 3.75 s (3.50 s)
> core.sparseCheckout=cone: 0.23 s (0.01 s)
Nice!
> The times in parentheses above correspond to the time spent
> in the first clear_ce_flags() call, according to the trace2
> performance traces.
>
> While this example is contrived, it demonstrates how these
> patterns can slow the sparse-checkout feature.
>
> Signed-off-by: Derrick Stolee <dstolee@xxxxxxxxxxxxx>
> ---
> Documentation/git-sparse-checkout.txt | 1 -
> dir.c | 154 +++++++++++++++++++++++++-
> dir.h | 27 +++++
> t/t1091-sparse-checkout-builtin.sh | 8 ++
> 4 files changed, 183 insertions(+), 7 deletions(-)
>
> diff --git a/Documentation/git-sparse-checkout.txt b/Documentation/git-sparse-checkout.txt
> index 463319055b..7ade827370 100644
> --- a/Documentation/git-sparse-checkout.txt
> +++ b/Documentation/git-sparse-checkout.txt
> @@ -85,7 +85,6 @@ negate patterns. For example, to remove the file `unwanted`:
> !unwanted
> ----------------
>
> -
> ## CONE PATTERN SET
>
> The full pattern set allows for arbitrary pattern matches and complicated
> diff --git a/dir.c b/dir.c
> index d021c908e5..2c5ff89a72 100644
> --- a/dir.c
> +++ b/dir.c
> @@ -599,6 +599,99 @@ void parse_exclude_pattern(const char **pattern,
> *patternlen = len;
> }
>
> +static int el_hashmap_cmp(const void *unused_cmp_data,
> + const void *a, const void *b, const void *key)
> +{
> + const struct exclude_entry *ee1 = a;
> + const struct exclude_entry *ee2 = b;
> +
> + return strncmp(ee1->pattern, ee2->pattern, ee1->patternlen);
> +}
> +
> +static void add_exclude_to_hashsets(struct exclude_list *el, struct exclude *x)
Is this for something that is logically an "include" or an "exclude"?
The earlier use of "exclude" for "include"s now how me totally confused
and makes me know I'll have to read the code really carefully and may
still get messed up.
I don't know if there's a better way, but re-using .gitignore internals
for sparse-checkout stuff leads to this inverted switcheroo and makes
things hard to follow. Is it too late or too hard to easily rename the
"exclude" stuff used by gitignore to something else more neutral?
Sigh...
> +{
> + struct exclude_entry *e;
> + char *truncated;
> + char *data = NULL;
> +
> + if (!el->use_cone_patterns)
> + return;
> +
> + if (x->patternlen >= 4 &&
> + !strcmp(x->pattern + x->patternlen - 4, "/*/*")) {
> + if (!(x->flags & EXC_FLAG_NEGATIVE)) {
> + /* Not a cone pattern. */
> + el->use_cone_patterns = 0;
> + warning(_("unrecognized pattern: '%s'"), x->pattern);
> + goto clear_hashmaps;
> + }
> +
> + truncated = xstrdup(x->pattern);
> + truncated[x->patternlen - 4] = 0;
> +
> + e = xmalloc(sizeof(struct exclude_entry));
> + e->pattern = truncated;
> + e->patternlen = x->patternlen - 4;
> + hashmap_entry_init(e, memhash(e->pattern, e->patternlen));
> +
> + if (!hashmap_get(&el->recursive_hashmap, e, NULL)) {
> + /* We did not see the "parent" included */
> + warning(_("unrecognized negative pattern: '%s'"), x->pattern);
> + free(truncated);
> + goto clear_hashmaps;
> + }
> +
> + hashmap_add(&el->parent_hashmap, e);
> + hashmap_remove(&el->recursive_hashmap, e, &data);
> + free(data);
> + return;
> + }
> +
> + if (x->patternlen >= 2 &&
> + !strcmp(x->pattern + x->patternlen - 2, "/*")) {
> + if (x->flags & EXC_FLAG_NEGATIVE) {
> + warning(_("unrecognized negative pattern: '%s'"), x->pattern);
> + goto clear_hashmaps;
> + }
> +
> + e = xmalloc(sizeof(struct exclude_entry));
> +
> + truncated = xstrdup(x->pattern);
> + truncated[x->patternlen - 2] = 0;
> + e->pattern = truncated;
> + e->patternlen = x->patternlen - 2;
> + hashmap_entry_init(e, memhash(e->pattern, e->patternlen));
> +
> + hashmap_add(&el->recursive_hashmap, e);
> +
> + if (hashmap_get(&el->parent_hashmap, e, NULL)) {
> + /* we already included this at the parent level */
> + warning(_("your sparse-checkout file may have issues: pattern '%s' is repeated"),
> + x->pattern);
> + hashmap_remove(&el->parent_hashmap, e, &data);
> + free(data);
> + }
> + return;
> + }
> +
> +clear_hashmaps:
> + hashmap_free(&el->parent_hashmap, 1);
> + hashmap_free(&el->recursive_hashmap, 1);
> + el->use_cone_patterns = 0;
> +}
> +
> +static int hashmap_contains_path(struct hashmap *map,
> + struct strbuf *pattern)
> +{
> + struct exclude_entry e;
> +
> + /* Check straight mapping */
> + e.pattern = pattern->buf;
> + e.patternlen = pattern->len;
> + hashmap_entry_init(&e, memhash(e.pattern, e.patternlen));
> + return !!hashmap_get(map, &e, NULL);
> +}
> +
> void add_exclude(const char *string, const char *base,
> int baselen, struct exclude_list *el, int srcpos)
> {
> @@ -623,6 +716,8 @@ void add_exclude(const char *string, const char *base,
> ALLOC_GROW(el->excludes, el->nr + 1, el->alloc);
> el->excludes[el->nr++] = x;
> x->el = el;
> +
> + add_exclude_to_hashsets(el, x);
> }
>
> static int read_skip_worktree_file_from_index(const struct index_state *istate,
> @@ -848,6 +943,10 @@ static int add_excludes_from_buffer(char *buf, size_t size,
> int i, lineno = 1;
> char *entry;
>
> + el->use_cone_patterns = core_sparse_checkout == SPARSE_CHECKOUT_CONE ? 1 : 0;
> + hashmap_init(&el->recursive_hashmap, el_hashmap_cmp, NULL, 0);
> + hashmap_init(&el->parent_hashmap, el_hashmap_cmp, NULL, 0);
> +
> el->filebuf = buf;
>
> if (skip_utf8_bom(&buf, size))
> @@ -1070,18 +1169,61 @@ static struct exclude *last_exclude_matching_from_list(const char *pathname,
>
> /*
> * Scan the list and let the last match determine the fate.
> - * Return 1 for exclude, 0 for include and -1 for undecided.
> + * Return 0 for exclude, 1 for include and -1 for undecided.
Um...this doesn't make me feel any better about whether we're going to
run into bugs about "include" vs. "exclude".
> */
> int is_excluded_from_list(const char *pathname,
> int pathlen, const char *basename, int *dtype,
> struct exclude_list *el, struct index_state *istate)
> {
> struct exclude *exclude;
> - exclude = last_exclude_matching_from_list(pathname, pathlen, basename,
> - dtype, el, istate);
> - if (exclude)
> - return exclude->flags & EXC_FLAG_NEGATIVE ? 0 : 1;
> - return -1; /* undecided */
> + struct strbuf parent_pathname = STRBUF_INIT;
> + int result = 0;
> + const char *slash_pos;
> +
> + if (!el->use_cone_patterns) {
> + exclude = last_exclude_matching_from_list(pathname, pathlen, basename,
> + dtype, el, istate);
> +
> + if (exclude)
> + return exclude->flags & EXC_FLAG_NEGATIVE ? 0 : 1;
> +
> + return -1; /* undecided */
> + }
> +
> + strbuf_addch(&parent_pathname, '/');
> + strbuf_add(&parent_pathname, pathname, pathlen);
> + slash_pos = strrchr(parent_pathname.buf, '/');
> +
> + if (slash_pos == parent_pathname.buf) {
> + /* include every file in root */
> + result = 1;
> + goto done;
> + }
> +
> + strbuf_setlen(&parent_pathname, slash_pos - parent_pathname.buf);
> +
> + if (hashmap_contains_path(&el->parent_hashmap, &parent_pathname)) {
> + result = 1;
> + goto done;
> + }
> +
> + while (parent_pathname.len) {
> + if (hashmap_contains_path(&el->recursive_hashmap,
> + &parent_pathname)) {
> + result = -1;
> + goto done;
> + }
> +
> + slash_pos = strrchr(parent_pathname.buf, '/');
> + if (slash_pos == parent_pathname.buf)
> + break;
> +
> + strbuf_setlen(&parent_pathname, slash_pos - parent_pathname.buf);
> + }
> +
> +done:
> + strbuf_release(&parent_pathname);
> + return result;
> }
>
> static struct exclude *last_exclude_matching_from_lists(struct dir_struct *dir,
> diff --git a/dir.h b/dir.h
> index 680079bbe3..2d3356d1c0 100644
> --- a/dir.h
> +++ b/dir.h
> @@ -4,6 +4,7 @@
> /* See Documentation/technical/api-directory-listing.txt */
>
> #include "cache.h"
> +#include "hashmap.h"
> #include "strbuf.h"
>
> struct dir_entry {
> @@ -37,6 +38,13 @@ struct exclude {
> int srcpos;
> };
>
> +/* used for hashmaps for cone patterns */
> +struct exclude_entry {
> + struct hashmap_entry ent;
> + char *pattern;
> + size_t patternlen;
> +};
> +
> /*
> * Each excludes file will be parsed into a fresh exclude_list which
> * is appended to the relevant exclude_list_group (either EXC_DIRS or
> @@ -55,6 +63,25 @@ struct exclude_list {
> const char *src;
>
> struct exclude **excludes;
> +
> + /*
> + * While scanning the excludes, we attempt to match the patterns
> + * with a more restricted set that allows us to use hashsets for
> + * matching logic, which is faster than the linear lookup in the
> + * excludes array above. If non-zero, that check succeeded.
> + */
> + unsigned use_cone_patterns;
> +
> + /*
> + * Stores paths where everything starting with those paths
> + * is included.
> + */
> + struct hashmap recursive_hashmap;
> +
> + /*
> + * Used to check single-level parents of blobs.
> + */
> + struct hashmap parent_hashmap;
> };
>
> /*
> diff --git a/t/t1091-sparse-checkout-builtin.sh b/t/t1091-sparse-checkout-builtin.sh
> index 8cc377b839..60f10864a1 100755
> --- a/t/t1091-sparse-checkout-builtin.sh
> +++ b/t/t1091-sparse-checkout-builtin.sh
> @@ -134,6 +134,14 @@ test_expect_success 'cone mode: match patterns' '
> test_cmp expect dir
> '
>
> +test_expect_success 'cone mode: warn on bad pattern' '
> + test_when_finished mv sparse-checkout repo/.git/info &&
> + cp repo/.git/info/sparse-checkout . &&
> + echo "!/deep/deeper/*" >>repo/.git/info/sparse-checkout &&
> + git -C repo read-tree -mu HEAD 2>err &&
> + test_i18ngrep "unrecognized negative pattern" err
> +'
> +
> test_expect_success 'sparse-checkout disable' '
> git -C repo sparse-checkout disable &&
> test_path_is_missing repo/.git/info/sparse-checkout &&
> --
> gitgitgadget
So, uh, I saw the exclude vs. include thing, started scanning to see
if it was going to get better, saw the next include/exclude thing that
triggered a bell, and I more or less just scrolled quickly to the
bottom checking if anything might catch my eye. So I didn't look at
this patch very closely at all. I decided to just start playing with
the series instead...and as far as that goes, this patch is probably
fine because my testing seemed to work.
