[PATCH v4 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 v3, which was withdrawn in favor of v2:

* Return to a two-patch series based on d66ac2af30, leaving Junio's
  preparatory const-correctness patch on its separately queued topic.
* Add the deterministic regression test suggested by Elijah, while
  retaining the shorter-pattern test for the out-of-bounds access.
* Explain the observable incorrect match in patch 1 and use consistent
  non-exclude/exclude terminology.
* Reword patch 2 to describe the directory-walk optimization it restores.

Yannik Tausch (2):
  dir: do not apply prefix to negative pathspecs
  dir: preserve pathspec prefix optimization with leading excludes

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

Range-diff against v2:
1:  c8a2f1e22e ! 1:  adeb7f2fb6 dir: do not apply prefix to negative pathspecs
    @@ Metadata
      ## Commit message ##
         dir: do not apply prefix to negative pathspecs
     
    -    common_prefix_len() derives the common prefix solely from positive
    -    pathspecs, skipping those marked with PATHSPEC_EXCLUDE. However,
    -    match_pathspec_with_flags() also passes that prefix when matching the
    -    negative pathspecs.
    +    common_prefix_len() derives the common prefix solely from non-exclude
    +    pathspec items. However, match_pathspec_with_flags() also passes that
    +    prefix when matching exclude items.
     
    -    A negative pathspec may be shorter than the prefix. In that case,
    -    match_pathspec_item() advances item->match beyond its allocation and
    -    subtracts the prefix from item->len, producing a negative matchlen. It
    -    then dereferences the out-of-bounds pointer. If the resulting byte is
    -    not NUL, matchlen is converted to size_t when passed to ps_strncmp(),
    -    which may cause a much larger out-of-bounds read.
    +    This can produce incorrect results because that prefix does not
    +    necessarily match an exclude item. For example, given non-exclude items
    +    "a/b" and "a/c" and an exclude item "x/b", stripping the two-byte
    +    prefix from both the pathname "a/b/m" and pattern "x/b" makes the
    +    remaining strings match and incorrectly excludes the pathname.
     
    -    The problem can be reproduced with AddressSanitizer:
    +    If an exclude item is shorter than the prefix, match_pathspec_item()
    +    instead advances item->match beyond its allocation and subtracts the
    +    prefix from item->len, producing a negative matchlen. It then
    +    dereferences the out-of-bounds pointer. If the resulting byte is not
    +    NUL, matchlen is converted to size_t when passed to ps_strncmp(), which
    +    may cause a much larger out-of-bounds read.
    +
    +    The out-of-bounds access can be reproduced with AddressSanitizer:
     
             make SANITIZE=address CFLAGS="-g -O0" git
             git init test &&
    @@ Commit message
             git commit -m test &&
             ../git ls-files -- "$DIR/" ":(exclude)xy"
     
    -    This reports a heap-buffer-overflow. Without AddressSanitizer, the
    -    output may depend on the contents of memory following the negative
    -    pathspec.
    -
    -    Fix the bug by using a zero prefix when matching negative pathspecs.
    -    Add a regression test that combines a positive pathspec with a longer
    -    common prefix and a shorter, unrelated negative pathspec.
    +    Fix the bug by using a zero prefix when matching exclude items. Add
    +    regression tests for both the deterministic incorrect match and the
    +    shorter exclude item that causes the out-of-bounds access.
     
         Signed-off-by: Yannik Tausch <dev@ytausch.de>
     
    @@ t/t6132-pathspec-exclude.sh: EOF
     +	EOF
     +	test_cmp expect actual
     +'
    ++
    ++test_expect_success 'exclude is matched against the full path' '
    ++	git ls-files -- sub/sub/ ":(exclude)zzzzzzz" >actual &&
    ++	cat <<-\EOF >expect &&
    ++	sub/sub/file
    ++	sub/sub/sub/file
    ++	EOF
    ++	test_cmp expect actual
    ++'
     +
      test_expect_success 'multiple exclusions' '
      	git ls-files -- ":^*/file2" ":^sub2" >actual &&
2:  d0e08fdb96 ! 2:  e8f72cab9c dir: find common prefix among non-exclude pathspec items
    @@ Metadata
     Author: Yannik Tausch <dev@ytausch.de>
     
      ## Commit message ##
    -    dir: find common prefix among non-exclude pathspec items
    +    dir: preserve pathspec prefix optimization with leading excludes
     
    -    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
    -    remaining items share a directory.
    +    Directory walks use the common directory prefix of non-exclude
    +    pathspec items to avoid scanning unrelated portions of the working
    +    tree or index. Exclude items only remove paths from that candidate
    +    set, so they do not need to widen the traversal.
     
    -    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.
    +    When an exclude item is the first pathspec item, common_prefix_len()
    +    fails to establish a comparison base and returns a zero-length prefix.
    +    The result is correct, but Git unnecessarily traverses from a broader
    +    starting point even when all non-exclude items share a directory.
    +
    +    Use the first non-exclude item as the comparison base and return its
    +    string together with the prefix length, allowing callers to start from
    +    the recovered directory prefix. Exclude matching continues to use full
    +    paths, so this restores the optimization without changing which paths
    +    are selected. Add a unit test covering an exclude item before two
    +    non-exclude items with a common directory.
     
         Signed-off-by: Yannik Tausch <dev@ytausch.de>
     

base-commit: d66ac2af300f33bd9e8558c5645f2a808cc01f89