Re: bug?: git grep HEAD with exclude in pathspec not taken into account

Re: bug?: git grep HEAD with exclude in pathspec not taken into account

[Christophe Bliard]

Hi,

I observed an unexpected behavior while using git grep with both git
2.19.1 and 2.14.3. Here is how to reproduce it:

> git init
Initialized empty Git repository in /private/tmp/hello/.git/
> echo foo > fileA
> echo 'foo is false+' > fileB
> git add fileA
> git commit -m fileA
[master (root-commit) f2c83e7] fileA
 1 file changed, 1 insertion(+)
 create mode 100644 fileA
> git add fileB
> git commit -m fileB
[master e35df26] fileB
 1 file changed, 1 insertion(+)
 create mode 100644 fileB
> git --no-pager grep foo HEAD -- ':!fileA'
HEAD:fileB:foo is false+
> git --no-pager grep foo HEAD -- ':!fileB'
HEAD:fileA:foo
HEAD:fileB:foo is false+

In the last command, fileB appears in grep results but it should have
been excluded.

If the HEAD parameter is removed, it works as expected:

> git --no-pager grep foo -- ':!fileB'
fileA:foo

If giving the revision, it does not work either

> git --no-pager grep foo e35df26 -- ':!fileB'
e35df26:fileA:foo
e35df26:fileB:foo is false+

The same behavior can be seen with git archive:

> git archive --verbose master ':(top)'
fileA
fileB
pax_global_header00006660000000000000000000000064133641017230014512gustar00rootroot0000000000000052
comment=e35df26c65f3c0b303e78743496598b8b6a566e9
fileA000066400000000000000000000000041336410172300120130ustar00rootroot00000000000000foo
fileB000066400000000000000000000000161336410172300120170ustar00rootroot00000000000000foo
is false+
> /usr/local/bin/git archive --verbose master ':(top)' ':(exclude)fileA'
fileB
pax_global_header00006660000000000000000000000064133641017230014512gustar00rootroot0000000000000052
comment=e35df26c65f3c0b303e78743496598b8b6a566e9
fileB000066400000000000000000000000161336410172300120170ustar00rootroot00000000000000foo
is false+
> /usr/local/bin/git archive --verbose master ':(top)' ':(exclude)fileB'
fileA
fileB
pax_global_header00006660000000000000000000000064133641017230014512gustar00rootroot0000000000000052
comment=e35df26c65f3c0b303e78743496598b8b6a566e9
fileA000066400000000000000000000000041336410172300120130ustar00rootroot00000000000000foo
fileB000066400000000000000000000000161336410172300120170ustar00rootroot00000000000000foo
is false+

fileA can be excluded, but not fileB.

Is it a bug?

Thanks

--
Christophe Bliard

Re: bug?: git grep HEAD with exclude in pathspec not taken into account

[Duy Nguyen]

On Wed, Oct 24, 2018 at 4:55 PM Christophe Bliard
<christophe.bliard@trux.info> wrote:
>
> Hi,
>
> I observed an unexpected behavior while using git grep with both git
> 2.19.1 and 2.14.3. Here is how to reproduce it:
>
> > git init
> Initialized empty Git repository in /private/tmp/hello/.git/
> > echo foo > fileA
> > echo 'foo is false+' > fileB
> > git add fileA
> > git commit -m fileA
> [master (root-commit) f2c83e7] fileA
>  1 file changed, 1 insertion(+)
>  create mode 100644 fileA
> > git add fileB
> > git commit -m fileB
> [master e35df26] fileB
>  1 file changed, 1 insertion(+)
>  create mode 100644 fileB
> > git --no-pager grep foo HEAD -- ':!fileA'
> HEAD:fileB:foo is false+
> > git --no-pager grep foo HEAD -- ':!fileB'
> HEAD:fileA:foo
> HEAD:fileB:foo is false+
>
> In the last command, fileB appears in grep results but it should have
> been excluded.
>
> If the HEAD parameter is removed, it works as expected:

It's probably a bug. We have different code paths for matching things
with or without HEAD, roughly speaking. I'll look into to this more on
the weekend, unless somebody (is welcome to) beats me first.

Another thing that might also be a problem is, negative patterns are
supposed to exclude stuff from "something" but you don't specify that
"something" (i.e. positive patterns) in your grep commands above. If
"grep foo HEAD -- :/ ':!fileB'" works, then you probably just run into
some undefined corner case.
-- 
Duy

Re: bug?: git grep HEAD with exclude in pathspec not taken into account

[Christophe Bliard]

In fact, per https://github.com/git/git/commit/859b7f1d0e742493d2a9396794cd9040213ad846,
having only a negative pattern is like having a catch-all positive
pattern and the negative pattern (since git 2.13.0).

Thus, adding the positive pattern yields the same results:

> git --no-pager grep foo HEAD -- ':!fileA' .
HEAD:fileB:foo is false+
> git --no-pager grep foo HEAD -- ':!fileB' .
HEAD:fileA:foo
HEAD:fileB:foo is false+

Le mer. 24 oct. 2018 à 17:14, Duy Nguyen <pclouds@gmail.com> a écrit :
>
> On Wed, Oct 24, 2018 at 4:55 PM Christophe Bliard
> <christophe.bliard@trux.info> wrote:
> >
> > Hi,
> >
> > I observed an unexpected behavior while using git grep with both git
> > 2.19.1 and 2.14.3. Here is how to reproduce it:
> >
> > > git init
> > Initialized empty Git repository in /private/tmp/hello/.git/
> > > echo foo > fileA
> > > echo 'foo is false+' > fileB
> > > git add fileA
> > > git commit -m fileA
> > [master (root-commit) f2c83e7] fileA
> >  1 file changed, 1 insertion(+)
> >  create mode 100644 fileA
> > > git add fileB
> > > git commit -m fileB
> > [master e35df26] fileB
> >  1 file changed, 1 insertion(+)
> >  create mode 100644 fileB
> > > git --no-pager grep foo HEAD -- ':!fileA'
> > HEAD:fileB:foo is false+
> > > git --no-pager grep foo HEAD -- ':!fileB'
> > HEAD:fileA:foo
> > HEAD:fileB:foo is false+
> >
> > In the last command, fileB appears in grep results but it should have
> > been excluded.
> >
> > If the HEAD parameter is removed, it works as expected:
>
> It's probably a bug. We have different code paths for matching things
> with or without HEAD, roughly speaking. I'll look into to this more on
> the weekend, unless somebody (is welcome to) beats me first.
>
> Another thing that might also be a problem is, negative patterns are
> supposed to exclude stuff from "something" but you don't specify that
> "something" (i.e. positive patterns) in your grep commands above. If
> "grep foo HEAD -- :/ ':!fileB'" works, then you probably just run into
> some undefined corner case.
> --
> Duy

Re: bug?: git grep HEAD with exclude in pathspec not taken into account

[Duy Nguyen]

On Wed, Oct 24, 2018 at 4:55 PM Christophe Bliard
<christophe.bliard@trux.info> wrote:
>
> Hi,
>
> I observed an unexpected behavior while using git grep with both git
> 2.19.1 and 2.14.3.

Quick note. I confirm this is a bug in tree_entry_interesting()
perhaps being over-optimistic. It'll take me more time to familiarize
myself with this negative matching in the function before I come up
with a fix for it. Thanks for reporting.
-- 
Duy

[PATCH] tree-walk.c: fix overoptimistic inclusion in :(exclude) matching

[Nguyễn Thái Ngọc Duy]

tree_entry_interesting() is used for matching pathspec on a tree. The
interesting thing about this function is that, because the tree
entries are known to be sorted, this function can return more than
just "yes, matched" and "no, not matched". It can also say "yes, this
entry is matched and so is the remaining entries in the tree".

This is where I made a mistake when matching exclude pathspec. For
exclude pathspec, we do matching twice, one with positive patterns and
one with negative ones, then a rule table is applied to determine the
final "include or exclude" result. Note that "matched" does not
necessarily mean include. For negative patterns, "matched" means
exclude.

This particular rule is too eager to include everything. Rule 8 says
that "if all entries are positively matched" and the current entry is
not negatively matched (i.e. not excluded), then all entries are
positively matched and therefore included. But this is not true. If
the _current_ entry is not negatively matched, it does not mean the
next one will not be and we cannot conclude right away that all
remaining entries are positively matched and can be included.

Rules 8 and 18 are now updated to be less eager. We conclude that the
current entry is positively matched and included. But we say nothing
about remaining entries. tree_entry_interesting() will be called again
for those entries where we will determine entries individually.

Reported-by: Christophe Bliard <christophe.bliard@trux.info>
Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 t/t6132-pathspec-exclude.sh | 17 +++++++++++++++++
 tree-walk.c                 | 11 ++++++++---
 2 files changed, 25 insertions(+), 3 deletions(-)

diff --git a/t/t6132-pathspec-exclude.sh b/t/t6132-pathspec-exclude.sh
index eb829fce97..393b29f205 100755
--- a/t/t6132-pathspec-exclude.sh
+++ b/t/t6132-pathspec-exclude.sh
@@ -194,4 +194,21 @@ test_expect_success 'multiple exclusions' '
 	test_cmp expect actual
 '
 
+test_expect_success 't_e_i() exclude case #8' '
+	git init case8 &&
+	(
+		cd case8 &&
+		echo file >file1 &&
+		echo file >file2 &&
+		git add . &&
+		git commit -m twofiles &&
+		git grep -l file HEAD :^file2 >actual &&
+		echo HEAD:file1 >expected &&
+		test_cmp expected actual &&
+		git grep -l file HEAD :^file1 >actual &&
+		echo HEAD:file2 >expected &&
+		test_cmp expected actual
+	)
+'
+
 test_done
diff --git a/tree-walk.c b/tree-walk.c
index 77b37f36fa..79bafbd1a2 100644
--- a/tree-walk.c
+++ b/tree-walk.c
@@ -1107,7 +1107,7 @@ enum interesting tree_entry_interesting(const struct name_entry *entry,
 	 *   5  |  file |    1     |    1     |   0
 	 *   6  |  file |    1     |    2     |   0
 	 *   7  |  file |    2     |   -1     |   2
-	 *   8  |  file |    2     |    0     |   2
+	 *   8  |  file |    2     |    0     |   1
 	 *   9  |  file |    2     |    1     |   0
 	 *  10  |  file |    2     |    2     |  -1
 	 * -----+-------+----------+----------+-------
@@ -1118,7 +1118,7 @@ enum interesting tree_entry_interesting(const struct name_entry *entry,
 	 *  15  |  dir  |    1     |    1     |   1 (*)
 	 *  16  |  dir  |    1     |    2     |   0
 	 *  17  |  dir  |    2     |   -1     |   2
-	 *  18  |  dir  |    2     |    0     |   2
+	 *  18  |  dir  |    2     |    0     |   1
 	 *  19  |  dir  |    2     |    1     |   1 (*)
 	 *  20  |  dir  |    2     |    2     |  -1
 	 *
@@ -1134,7 +1134,12 @@ enum interesting tree_entry_interesting(const struct name_entry *entry,
 
 	negative = do_match(entry, base, base_offset, ps, 1);
 
-	/* #3, #4, #7, #8, #13, #14, #17, #18 */
+	/* #8, #18 */
+	if (positive == all_entries_interesting &&
+	    negative == entry_not_interesting)
+		return entry_interesting;
+
+	/* #3, #4, #7, #13, #14, #17 */
 	if (negative <= entry_not_interesting)
 		return positive;
 
-- 
2.19.1.1005.gac84295441

Re: [PATCH] tree-walk.c: fix overoptimistic inclusion in :(exclude) matching

[Eric Sunshine]

On Sat, Nov 3, 2018 at 11:31 AM Nguyễn Thái Ngọc Duy <pclouds@gmail.com> wrote:
> Rules 8 and 18 are now updated to be less eager. We conclude that the
> current entry is positively matched and included. But we say nothing
> about remaining entries. tree_entry_interesting() will be called again
> for those entries where we will determine entries individually.
>
> Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
> ---
> diff --git a/t/t6132-pathspec-exclude.sh b/t/t6132-pathspec-exclude.sh
> @@ -194,4 +194,21 @@ test_expect_success 'multiple exclusions' '
> +test_expect_success 't_e_i() exclude case #8' '
> +       git init case8 &&
> +       (
> +               cd case8 &&
> +               echo file >file1 &&
> +               echo file >file2 &&
> +               git add . &&

Won't this loose git-add invocation end up adding all the junk files
from earlier tests? One might have expected to see the more restricted
invocation:

    git add file1 file2 &&

to make it easier to reason about the test and not worry about someone
later inserting tests above this one which might interfere with it.

> +               git commit -m twofiles &&
> +               git grep -l file HEAD :^file2 >actual &&
> +               echo HEAD:file1 >expected &&
> +               test_cmp expected actual &&
> +               git grep -l file HEAD :^file1 >actual &&
> +               echo HEAD:file2 >expected &&
> +               test_cmp expected actual
> +       )
> +'

[PATCH v2] tree-walk.c: fix overoptimistic inclusion in :(exclude) matching

[Nguyễn Thái Ngọc Duy]

tree_entry_interesting() is used for matching pathspec on a tree. The
interesting thing about this function is that, because the tree
entries are known to be sorted, this function can return more than
just "yes, matched" and "no, not matched". It can also say "yes, this
entry is matched and so is the remaining entries in the tree".

This is where I made a mistake when matching exclude pathspec. For
exclude pathspec, we do matching twice, one with positive patterns and
one with negative ones, then a rule table is applied to determine the
final "include or exclude" result. Note that "matched" does not
necessarily mean include. For negative patterns, "matched" means
exclude.

This particular rule is too eager to include everything. Rule 8 says
that "if all entries are positively matched" and the current entry is
not negatively matched (i.e. not excluded), then all entries are
positively matched and therefore included. But this is not true. If
the _current_ entry is not negatively matched, it does not mean the
next one will not be and we cannot conclude right away that all
remaining entries are positively matched and can be included.

Rules 8 and 18 are now updated to be less eager. We conclude that the
current entry is positively matched and included. But we say nothing
about remaining entries. tree_entry_interesting() will be called again
for those entries where we will determine entries individually.

Reported-by: Christophe Bliard <christophe.bliard@trux.info>
Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 v2 fixes the too broad "git add ." in the test

 t/t6132-pathspec-exclude.sh | 17 +++++++++++++++++
 tree-walk.c                 | 11 ++++++++---
 2 files changed, 25 insertions(+), 3 deletions(-)

diff --git a/t/t6132-pathspec-exclude.sh b/t/t6132-pathspec-exclude.sh
index eb829fce97..2462b19ddd 100755
--- a/t/t6132-pathspec-exclude.sh
+++ b/t/t6132-pathspec-exclude.sh
@@ -194,4 +194,21 @@ test_expect_success 'multiple exclusions' '
 	test_cmp expect actual
 '
 
+test_expect_success 't_e_i() exclude case #8' '
+	git init case8 &&
+	(
+		cd case8 &&
+		echo file >file1 &&
+		echo file >file2 &&
+		git add file1 file2 &&
+		git commit -m twofiles &&
+		git grep -l file HEAD :^file2 >actual &&
+		echo HEAD:file1 >expected &&
+		test_cmp expected actual &&
+		git grep -l file HEAD :^file1 >actual &&
+		echo HEAD:file2 >expected &&
+		test_cmp expected actual
+	)
+'
+
 test_done
diff --git a/tree-walk.c b/tree-walk.c
index 77b37f36fa..79bafbd1a2 100644
--- a/tree-walk.c
+++ b/tree-walk.c
@@ -1107,7 +1107,7 @@ enum interesting tree_entry_interesting(const struct name_entry *entry,
 	 *   5  |  file |    1     |    1     |   0
 	 *   6  |  file |    1     |    2     |   0
 	 *   7  |  file |    2     |   -1     |   2
-	 *   8  |  file |    2     |    0     |   2
+	 *   8  |  file |    2     |    0     |   1
 	 *   9  |  file |    2     |    1     |   0
 	 *  10  |  file |    2     |    2     |  -1
 	 * -----+-------+----------+----------+-------
@@ -1118,7 +1118,7 @@ enum interesting tree_entry_interesting(const struct name_entry *entry,
 	 *  15  |  dir  |    1     |    1     |   1 (*)
 	 *  16  |  dir  |    1     |    2     |   0
 	 *  17  |  dir  |    2     |   -1     |   2
-	 *  18  |  dir  |    2     |    0     |   2
+	 *  18  |  dir  |    2     |    0     |   1
 	 *  19  |  dir  |    2     |    1     |   1 (*)
 	 *  20  |  dir  |    2     |    2     |  -1
 	 *
@@ -1134,7 +1134,12 @@ enum interesting tree_entry_interesting(const struct name_entry *entry,
 
 	negative = do_match(entry, base, base_offset, ps, 1);
 
-	/* #3, #4, #7, #8, #13, #14, #17, #18 */
+	/* #8, #18 */
+	if (positive == all_entries_interesting &&
+	    negative == entry_not_interesting)
+		return entry_interesting;
+
+	/* #3, #4, #7, #13, #14, #17 */
 	if (negative <= entry_not_interesting)
 		return positive;
 
-- 
2.19.1.1005.gac84295441

Re: [PATCH] tree-walk.c: fix overoptimistic inclusion in :(exclude) matching

[Eric Sunshine]

On Sat, Nov 3, 2018 at 8:25 PM Eric Sunshine <sunshine@sunshineco.com> wrote:
> On Sat, Nov 3, 2018 at 11:31 AM Nguyễn Thái Ngọc Duy <pclouds@gmail.com> wrote:
> > +test_expect_success 't_e_i() exclude case #8' '
> > +       git init case8 &&
> > +       (
> > +               cd case8 &&
> > +               echo file >file1 &&
> > +               echo file >file2 &&
> > +               git add . &&
>
> Won't this loose git-add invocation end up adding all the junk files
> from earlier tests? One might have expected to see the more restricted
> invocation:
>     git add file1 file2 &&
> to make it easier to reason about the test and not worry about someone
> later inserting tests above this one which might interfere with it.

Upon reflection, there shouldn't be any junk files since this test is
creating a new repository and "file1" and "file2" are the only files
present. Apparently, I wasn't paying close enough attention when I
made the earlier observation.

Anyhow, the more restricted git-add invocation you used in the re-roll
is still preferable since it makes the intention obvious. Thanks.

Re: [PATCH] tree-walk.c: fix overoptimistic inclusion in :(exclude) matching

[Duy Nguyen]

On Sun, Nov 4, 2018 at 7:27 AM Eric Sunshine <sunshine@sunshineco.com> wrote:
>
> On Sat, Nov 3, 2018 at 8:25 PM Eric Sunshine <sunshine@sunshineco.com> wrote:
> > On Sat, Nov 3, 2018 at 11:31 AM Nguyễn Thái Ngọc Duy <pclouds@gmail.com> wrote:
> > > +test_expect_success 't_e_i() exclude case #8' '
> > > +       git init case8 &&
> > > +       (
> > > +               cd case8 &&
> > > +               echo file >file1 &&
> > > +               echo file >file2 &&
> > > +               git add . &&
> >
> > Won't this loose git-add invocation end up adding all the junk files
> > from earlier tests? One might have expected to see the more restricted
> > invocation:
> >     git add file1 file2 &&
> > to make it easier to reason about the test and not worry about someone
> > later inserting tests above this one which might interfere with it.
>
> Upon reflection, there shouldn't be any junk files since this test is
> creating a new repository and "file1" and "file2" are the only files
> present. Apparently, I wasn't paying close enough attention when I
> made the earlier observation.

Yup.

> Anyhow, the more restricted git-add invocation you used in the re-roll
> is still preferable since it makes the intention obvious. Thanks.

Which is why I did it anyway :)
-- 
Duy

Re: [PATCH v2] tree-walk.c: fix overoptimistic inclusion in :(exclude) matching

[Junio C Hamano]

Nguyễn Thái Ngọc Duy  <pclouds@gmail.com> writes:

> tree_entry_interesting() is used for matching pathspec on a tree. The
> interesting thing about this function is that, because the tree
> entries are known to be sorted, this function can return more than
> just "yes, matched" and "no, not matched". It can also say "yes, this
> entry is matched and so is the remaining entries in the tree".
>
> This is where I made a mistake when matching exclude pathspec. For
> exclude pathspec, we do matching twice, one with positive patterns and
> one with negative ones, then a rule table is applied to determine the
> final "include or exclude" result. Note that "matched" does not
> necessarily mean include. For negative patterns, "matched" means
> exclude.
>
> This particular rule is too eager to include everything. Rule 8 says
> that "if all entries are positively matched" and the current entry is
> not negatively matched (i.e. not excluded), then all entries are
> positively matched and therefore included. But this is not true. If
> the _current_ entry is not negatively matched, it does not mean the
> next one will not be and we cannot conclude right away that all
> remaining entries are positively matched and can be included.
>
> Rules 8 and 18 are now updated to be less eager. We conclude that the
> current entry is positively matched and included. But we say nothing
> about remaining entries. tree_entry_interesting() will be called again
> for those entries where we will determine entries individually.

Thanks.  Will queue.

> Reported-by: Christophe Bliard <christophe.bliard@trux.info>
> Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
> ---
>  v2 fixes the too broad "git add ." in the test
>
>  t/t6132-pathspec-exclude.sh | 17 +++++++++++++++++
>  tree-walk.c                 | 11 ++++++++---
>  2 files changed, 25 insertions(+), 3 deletions(-)
>
> diff --git a/t/t6132-pathspec-exclude.sh b/t/t6132-pathspec-exclude.sh
> index eb829fce97..2462b19ddd 100755
> --- a/t/t6132-pathspec-exclude.sh
> +++ b/t/t6132-pathspec-exclude.sh
> @@ -194,4 +194,21 @@ test_expect_success 'multiple exclusions' '
>  	test_cmp expect actual
>  '
>  
> +test_expect_success 't_e_i() exclude case #8' '
> +	git init case8 &&
> +	(
> +		cd case8 &&
> +		echo file >file1 &&
> +		echo file >file2 &&
> +		git add file1 file2 &&
> +		git commit -m twofiles &&
> +		git grep -l file HEAD :^file2 >actual &&
> +		echo HEAD:file1 >expected &&
> +		test_cmp expected actual &&
> +		git grep -l file HEAD :^file1 >actual &&
> +		echo HEAD:file2 >expected &&
> +		test_cmp expected actual
> +	)
> +'
> +
>  test_done
> diff --git a/tree-walk.c b/tree-walk.c
> index 77b37f36fa..79bafbd1a2 100644
> --- a/tree-walk.c
> +++ b/tree-walk.c
> @@ -1107,7 +1107,7 @@ enum interesting tree_entry_interesting(const struct name_entry *entry,
>  	 *   5  |  file |    1     |    1     |   0
>  	 *   6  |  file |    1     |    2     |   0
>  	 *   7  |  file |    2     |   -1     |   2
> -	 *   8  |  file |    2     |    0     |   2
> +	 *   8  |  file |    2     |    0     |   1
>  	 *   9  |  file |    2     |    1     |   0
>  	 *  10  |  file |    2     |    2     |  -1
>  	 * -----+-------+----------+----------+-------
> @@ -1118,7 +1118,7 @@ enum interesting tree_entry_interesting(const struct name_entry *entry,
>  	 *  15  |  dir  |    1     |    1     |   1 (*)
>  	 *  16  |  dir  |    1     |    2     |   0
>  	 *  17  |  dir  |    2     |   -1     |   2
> -	 *  18  |  dir  |    2     |    0     |   2
> +	 *  18  |  dir  |    2     |    0     |   1
>  	 *  19  |  dir  |    2     |    1     |   1 (*)
>  	 *  20  |  dir  |    2     |    2     |  -1
>  	 *
> @@ -1134,7 +1134,12 @@ enum interesting tree_entry_interesting(const struct name_entry *entry,
>  
>  	negative = do_match(entry, base, base_offset, ps, 1);
>  
> -	/* #3, #4, #7, #8, #13, #14, #17, #18 */
> +	/* #8, #18 */
> +	if (positive == all_entries_interesting &&
> +	    negative == entry_not_interesting)
> +		return entry_interesting;
> +
> +	/* #3, #4, #7, #13, #14, #17 */
>  	if (negative <= entry_not_interesting)
>  		return positive;