[PATCH v2 0/2] dir: fix pathspec prefixes with exclusions

Pathspec prefix optimization must account for exclude items separately. The prefix is derived from non-exclude items, so applying it while matching an exclude item can compare the wrong portions of the paths. Conversely, an exclude item at the start of the pathspec currently prevents finding a common prefix among the remaining items.

The first patch matches exclude items against the full pathname. The second patch finds the common prefix starting with the first non-exclude item and returns both the prefix length and the string from which it was derived.

Changes since v1:

* Send the changes as a two-patch series in dependency order.
* Return the matched prefix through an output parameter instead of returning
  a structure by value.
* Use "non-exclude pathspec item" terminology and consistent variable names.

Yannik Tausch (2):
  dir: do not apply prefix to negative pathspecs
  dir: find common prefix among non-exclude pathspec items

 dir.c                       | 39 +++++++++++++++++++++----------------
 t/t6132-pathspec-exclude.sh |  9 +++++++++
 t/unit-tests/u-dir.c        | 28 ++++++++++++++++++++++++++
 3 files changed, 59 insertions(+), 17 deletions(-)

Range-diff against v1:
1:  c8a2f1e22e = 1:  c8a2f1e22e dir: do not apply prefix to negative pathspecs
2:  5a179872c1 ! 2:  d0e08fdb96 dir: find common prefix among positive pathspecs
    @@ Metadata
     Author: Yannik Tausch <dev@ytausch.de>
     
      ## Commit message ##
    -    dir: find common prefix among positive pathspecs
    +    dir: find common prefix among non-exclude pathspec items
     
         common_prefix_len() skips exclude pathspec items, but uses n == 0 to
         identify the initial item and items[0] as the comparison source. When
         an exclude item comes first, the function returns zero even when all
    -    positive pathspecs share a directory.
    +    remaining items share a directory.
     
    -    Track the first positive item explicitly. Return its match and the
    -    common prefix length together so that common_prefix() and
    -    fill_directory() use the correct string. Add a unit test with an
    -    unrelated exclude before two positive pathspecs that share a directory.
    +    Track the first non-exclude item explicitly. Return its match through
    +    an output parameter so that common_prefix() and fill_directory() use
    +    the correct string. Add a unit test with an unrelated exclude item
    +    before two non-exclude items that share a directory.
     
         Signed-off-by: Yannik Tausch <dev@ytausch.de>
     
    @@ dir.c: static int fnmatch_icase_mem(const char *pattern, int patternlen,
      }
      
     -static size_t common_prefix_len(const struct pathspec *pathspec)
    -+struct pathspec_prefix {
    -+	const char *match;
    -+	size_t len;
    -+};
    -+
    -+/*
    -+ * Find the common prefix of positive pathspec items. The returned match
    -+ * points into the first positive item and is not NUL-terminated at len.
    -+ */
    -+static struct pathspec_prefix find_common_prefix(const struct pathspec *pathspec)
    ++static size_t common_prefix_len(const struct pathspec *pathspec,
    ++				const char **matched_prefix)
      {
     -	int n;
    -+	struct pathspec_prefix prefix = { 0 };
     +	int n, first = -1;
      	size_t max = 0;
      
    @@ dir.c: static size_t common_prefix_len(const struct pathspec *pathspec)
      				break;
      		}
      	}
    --	return max;
    -+	prefix.match = first < 0 ? NULL : pathspec->items[first].match;
    -+	prefix.len = max;
    -+	return prefix;
    ++	*matched_prefix = first < 0 ? NULL : pathspec->items[first].match;
    + 	return max;
      }
      
      /*
     - * Returns a copy of the longest leading path common among all
    -+ * Returns a copy of the longest leading path common among all positive
    -  * pathspecs.
    +- * pathspecs.
    ++ * Returns a copy of the longest leading path common among all pathspec
    ++ * items that are not excluded.
       */
      char *common_prefix(const struct pathspec *pathspec)
      {
     -	unsigned long len = common_prefix_len(pathspec);
    -+	struct pathspec_prefix prefix = find_common_prefix(pathspec);
    ++	const char *matched_prefix;
    ++	size_t len = common_prefix_len(pathspec, &matched_prefix);
      
     -	return len ? xmemdupz(pathspec->items[0].match, len) : NULL;
    -+	return prefix.len ? xmemdupz(prefix.match, prefix.len) : NULL;
    ++	return len ? xmemdupz(matched_prefix, len) : NULL;
      }
      
      int fill_directory(struct dir_struct *dir,
    @@ dir.c: static size_t common_prefix_len(const struct pathspec *pathspec)
      		   const struct pathspec *pathspec)
      {
     -	const char *prefix;
    --	size_t prefix_len;
    -+	struct pathspec_prefix prefix;
    ++	const char *matched_prefix;
    + 	size_t prefix_len;
      
      	unsigned exclusive_flags = DIR_SHOW_IGNORED | DIR_SHOW_IGNORED_TOO;
    - 	if ((dir->flags & exclusive_flags) == exclusive_flags)
     @@ dir.c: int fill_directory(struct dir_struct *dir,
      	 * Calculate common prefix for the pathspec, and
      	 * use that to optimize the directory walk
      	 */
     -	prefix_len = common_prefix_len(pathspec);
     -	prefix = prefix_len ? pathspec->items[0].match : "";
    -+	prefix = find_common_prefix(pathspec);
    ++	prefix_len = common_prefix_len(pathspec, &matched_prefix);
      
      	/* Read the directory and prune it */
     -	read_directory(dir, istate, prefix, prefix_len, pathspec);
    -+	read_directory(dir, istate, prefix.len ? prefix.match : "",
    -+		       prefix.len, pathspec);
    ++	read_directory(dir, istate, prefix_len ? matched_prefix : "",
    ++		       prefix_len, pathspec);
      
    --	return prefix_len;
    -+	return prefix.len;
    + 	return prefix_len;
      }
    - 
    - int within_depth(const char *name, int namelen,
     @@ dir.c: static int match_pathspec_item(struct index_state *istate,
      
      	/*
      	 * The normal call pattern is:
     -	 * 1. prefix = common_prefix_len(ps);
    -+	 * 1. prefix = find_common_prefix(ps).len;
    ++	 * 1. prefix = common_prefix_len(ps, &matched_prefix);
      	 * 2. prune something, or fill_directory
      	 * 3. match_pathspec()
      	 *
     @@ dir.c: static int match_pathspec_item(struct index_state *istate,
    - 	 * prefix part when :(icase) is involved. We do exact
    - 	 * comparison ourselves.
    - 	 *
    --	 * Normally the caller (common_prefix_len() in fact) does
    -+	 * Normally the caller (find_common_prefix() in fact) does
    + 	 * Normally the caller (common_prefix_len() in fact) does
      	 * _exact_ matching on name[-prefix+1..-1] and we do not need
      	 * to check that part. Be defensive and check it anyway, in
     -	 * case common_prefix_len is changed, or a new caller is
     -	 * introduced that does not use common_prefix_len.
    -+	 * case find_common_prefix() is changed, or a new caller is
    -+	 * introduced that does not use find_common_prefix().
    ++	 * case common_prefix_len() is changed, or a new caller is
    ++	 * introduced that does not use common_prefix_len().
      	 *
      	 * If the penalty turns out too high when prefix is really
      	 * long, maybe change it to
    @@ t/unit-tests/u-dir.c: void test_dir__within_depth(void)
      
      }
     +
    -+void test_dir__common_prefix_skips_excluded_pathspecs(void)
    ++void test_dir__common_prefix_skips_excluded_pathspec_items(void)
     +{
     +	struct pathspec_item items[] = {
     +		{