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

Message ID 20181104052851.12584-1-pclouds@gmail.com
State New
Headers show
Series
  • [v2] tree-walk.c: fix overoptimistic inclusion in :(exclude) matching
Related show

Commit Message

Duy Nguyen Nov. 4, 2018, 5:28 a.m. UTC
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(-)

Comments

Junio C Hamano Nov. 5, 2018, 1:50 a.m. UTC | #1
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;

Patch
diff mbox series

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;