Bug in pathspec handling (in conjunction with submodules)
Hi Duy & Brandon,
in 74ed43711fd (grep: enable recurse-submodules to work on <tree> objects, 2016-12-16), the do_match() function in tree-walk.c was changed so that it can recurse across submodule boundaries.
However, there is a bug, and I *think* there may be two bugs actually. Or even three.
First of all, here is an MCVE that I distilled from
https://github.com/git-for-windows/git/issues/1371:
git init repo
cd repo
git init submodule
git -C submodule commit -m initial --allow-empty
touch "[bracket]"
git add "[bracket]"
git commit -m bracket
git add submodule
git commit -m submodule
git rev-list HEAD -- "[bracket]"
Nothing fancy, just adding a file with brackets in the name, then a submodule, then showing the commit history filtered by the funny file name.
However, the log prints *both* commits. Clearly the submodule commit should *not* be shown.
Now, how does this all happen?
Since the pathspec contains brackets, parse_pathspec() marks it as containing wildcards and sets nowildcard_len to 0.
Now, note that [bracket] *is* a wildcard expression: it should only match a single character that is one of a, b, c, e, k, r or t.
I think this is the first bug: git rev-list should not even match the commit that adds the file [bracket] because its file name does not match that expression. From where I sit, it would appear that f1a2ddbbc2d (tree_entry_interesting(): optimize wildcard matching when base is matched, 2010-12-15) simply added the fnmatch() code without disabling the literal match_entry() code when the pathspec contains a pattern.
But it does not stop there: there is *another* bug which causes the pattern to somehow match the submodule. I *guess* the idea of
https://github.com/git/git/commit/74ed43711#diff-7a08243175f2cae66aedf53f7dce3bdfR1015
was to allow a pattern like *.c to match files in a submodule, but the pattern [bracket] should not match any file in submodule/. I think that that code needs to be a little bit more careful to try to match the submodule's name against the pattern (it seems to interpret nowildcard_len == 0 to mean that the wildcard is *).
However, the commit introducing that code wanted to teach *grep* (not *rev-list*) a new trick, and it relies on the recursive flag of the pathspec to be set.
And now it gets really interesting. Or confusing, depending on your mental condition. This recursive flag of the pathspec is set in ll_diff_tree_paths() (yep, changing the flag in the passed-in opt structure... which I found a bit... unexpected, given the function name, I would have been less surprised if that function only diff'ed the trees and used the options without changing the options). That flag-change was introduced in
https://github.com/git/git/commit/bc96cc87dbb2#diff-15203e8cd8ee9191113894de9d97a8a6R149
which is another patch that changed the tree diff machinery to accommodate git grep (but maybe not really paying a lot of attention to the fact that the same machinery is called repeatedly by the revision machinery, too).
I am really confused by this code mainly due to the fact that the term "recursive" is pretty ambiguous in that context: does it refer to directories/tree objects, or to submodules? I guess it is used for both when there should be two flags so that rev-list can recurse over tree objects but not submodules (unless told to do so).
The problem, of course, is that git rev-list HEAD -- '[bracket]' never recurses into the submodule. And therefore, the promised "more accurate matching [...] in the submodule" is never performed. And the commit adding the submodule is never pruned.
Since I am not really familiar with all that tree diff code (and as a general rule to protect my mental health, I try my best to stay away from submodules, too), but you two are, may I ask you gentle people to have a closer look to fix those bugs?
Thanks,
Dscho
Quoted 41 lines · Johannes Schindelin
Hi Duy & Brandon,
in
74ed43711fd(grep: enable recurse-submodules to work on <tree> objects, 2016-12-16), thedo_match()function intree-walk.cwas changed so that it can recurse across submodule boundaries.However, there is a bug, and I *think* there may be two bugs actually. Or even three.
First of all, here is an MCVE that I distilled from
https://github.com/git-for-windows/git/issues/1371:git init repo
cd repogit init submodule
git -C submodule commit -m initial --allow-emptytouch "[bracket]"
git add "[bracket]"
git commit -m bracket
git add submodule
git commit -m submodulegit rev-list HEAD -- "[bracket]"
Nothing fancy, just adding a file with brackets in the name, then a submodule, then showing the commit history filtered by the funny file name.
However, the log prints *both* commits. Clearly the submodule commit should *not* be shown.
Now, how does this all happen?
Since the pathspec contains brackets,
parse_pathspec()marks it as containing wildcards and setsnowildcard_lento 0.Now, note that [bracket] *is* a wildcard expression: it should only match a single character that is one of a, b, c, e, k, r or t.
Quoted 6 lines
I think this is the first bug:
git rev-listshould not even match the commit that adds the file [bracket] because its file name does not match that expression. From where I sit, it would appear thatf1a2ddbbc2d(tree_entry_interesting(): optimize wildcard matching when base is matched, 2010-12-15) simply added thefnmatch()code without disabling the literalmatch_entry()code when the pathspec contains a pattern.
I can see both sides to this, wanting to try matching literally first and then trying the wildcards, so I don't really have an opinion on how/if we should fix that.
Quoted 9 lines
But it does not stop there: there is *another* bug which causes the pattern to somehow match the submodule. I *guess* the idea of
https://github.com/git/git/commit/74ed43711#diff-7a08243175f2cae66aedf53f7dce3bdfR1015
was to allow a pattern like *.c to match files in a submodule, but the pattern [bracket] should not match any file in submodule/. I think that that code needs to be a little bit more careful to try to match the submodule's name against the pattern (it seems to interpretnowildcard_len== 0 to mean that the wildcard is*).
This is a much bigger issue and I'm surprised it took this long to find this bug. And of course its due to one of my earlier contributions to the project :)
Quoted 4 lines
However, the commit introducing that code wanted to teach *grep* (not *rev-list*) a new trick, and it relies on the
recursiveflag of the pathspec to be set.
This is the root cause of the bug. The added code to match against submodules was intended to allow for matching past submodule boundaries for those commands (like grep) which are recursing submodules. So really there should be an additional flag which is passed in to trigger this logic instead of relying on the recursive flag of the pathspec. Or we can add a recurse_submodules flag to the pathspec struct and respect that flag instead of the 'recursive' flag.
I have a quick patch to do just that which I'll send shortly.
Quoted 32 lines
And now it gets really interesting. Or confusing, depending on your mental condition. This recursive flag of the pathspec is set in
ll_diff_tree_paths()(yep, changing the flag in the passed-in opt structure... which I found a bit... unexpected, given the function name, I would have been less surprised if that function only diff'ed the trees and used the options without changing the options). That flag-change was introduced in
https://github.com/git/git/commit/bc96cc87dbb2#diff-15203e8cd8ee9191113894de9d97a8a6R149
which is another patch that changed the tree diff machinery to accommodategit grep(but maybe not really paying a lot of attention to the fact that the same machinery is called repeatedly by the revision machinery, too).I am really confused by this code mainly due to the fact that the term "recursive" is pretty ambiguous in that context: does it refer to directories/tree objects, or to submodules? I guess it is used for both when there should be two flags so that rev-list can recurse over tree objects but not submodules (unless told to do so).
The problem, of course, is that
git rev-list HEAD -- '[bracket]'never recurses into the submodule. And therefore, the promised "more accurate matching [...] in the submodule" is never performed. And the commit adding the submodule is never pruned.Since I am not really familiar with all that tree diff code (and as a general rule to protect my mental health, I try my best to stay away from submodules, too), but you two are, may I ask you gentle people to have a closer look to fix those bugs?
Thanks,
Dscho
Signature · 1 line
Brandon Williams
PATCH 1/1 pathspec: only match across submodule boundaries when requested
In reply to Johannes SchindelinCommit 74ed43711fd (grep: enable recurse-submodules to work on <tree> objects, 2016-12-16) taught 'tree_entry_interesting()' to be able to match across submodule boundaries in the presence of wildcards. This is done by performing literal matching up to the first wildcard and then punting to the submodule itself to perform more accurate pattern matching. Instead of introducing a new flag to request this behavior, commit 74ed43711fd overloaded the already existing 'recursive' flag in 'struct pathspec' to request this behavior.
This leads to a bug where whenever any other caller has the 'recursive' flag set as well as a pathspec with wildcards that all submodules will be indicated as matches. One simple example of this is:
git init repo
cd repo
git init submodule
git -C submodule commit -m initial --allow-empty
touch "[bracket]"
git add "[bracket]"
git commit -m bracket
git add submodule
git commit -m submodule
git rev-list HEAD -- "[bracket]"
Fix this by introducing the new flag 'recurse_submodules' in 'struct pathspec' and using this flag to determine if matches should be allowed to cross submodule boundaries.
--- builtin/grep.c | 1 + pathspec.h | 1 + t/t4208-log-magic-pathspec.sh | 17 +++++++++++++++++ tree-walk.c | 5 +++-- 4 files changed, 22 insertions(+), 2 deletions(-)
builtin/grep.c +1 -0
@@ -1015,6 +1015,7 @@ int cmd_grep(int argc, const char **argv, const char *prefix) prefix, argv + i); pathspec.max_depth = opt.max_depth; pathspec.recursive =1 ; + pathspec.recurse_submodules = !!recurse_submodules;#ifndef NO_PTHREADS if (list.nr || cached || show_in_pager)
pathspec.h +1 -0
@@ -24,6 +24,7 @@ struct pathspec {int nr; unsigned int has_wildcard:1; unsigned int recursive:1; + unsigned int recurse_submodules:1;unsigned magic;int max_depth;struct pathspec_item {
t/t4208-log-magic-pathspec.sh +17 -0
@@ -93,4 +93,21 @@ test_expect_success 'command line pathspec parsing for "git log"' ' git log --merge -- a ' +test_expect_success 'tree_entry_interesting does not match past submodule boundaries' ' + test_when_finished "rm -rf repo submodule" && + git init submodule && + test_commit -C submodule initial && + git init repo && + >"repo/[bracket]" && + git -C repo add "[bracket]" && + git -C repo commit -m bracket && + git -C repo rev-list HEAD -- "[bracket]" >expect && + + git -C repo submodule add ../submodule && + git -C repo commit -m submodule && + + git -C repo rev-list HEAD -- "[bracket]" >actual && + test_cmp expect actual +' + test_done
tree-walk.c +3 -2
@@ -1011,7 +1011,8 @@ static enum interesting do_match(const struct name_entry *entry,* character. More accurate matching can then * be performed in the submodule itself. */ -if (ps->recursive &&S_ISGITLINK (entry->mode) && +if (ps->recurse_submodules && +S_ISGITLINK (entry->mode) && !ps_strncmp (item, match + baselen, entry->path, item->nowildcard_len - baselen))
@@ -1060,7 +1061,7 @@ static enum interesting do_match(const struct name_entry *entry,* character. More accurate matching can then * be performed in the submodule itself. */ -if (ps->recursive &&S_ISGITLINK (entry->mode) && +if (ps->recurse_submodules &&S_ISGITLINK (entry->mode) && !ps_strncmp (item, match, base->buf + base_offset, item->nowildcard_len)) {strbuf_setlen (base, base_offset + baselen);
Signature · 1 line
2.15.0.531.g2ccb3012c9-goog
Re: [PATCH] pathspec: only match across submodule boundaries when requested
Hi Brandon,
Quoted 25 lines · Brandon Williams
Commit
74ed43711fd(grep: enable recurse-submodules to work on <tree> objects, 2016-12-16) taught 'tree_entry_interesting()' to be able to match across submodule boundaries in the presence of wildcards. This is done by performing literal matching up to the first wildcard and then punting to the submodule itself to perform more accurate pattern matching. Instead of introducing a new flag to request this behavior, commit74ed43711fdoverloaded the already existing 'recursive' flag in 'struct pathspec' to request this behavior.This leads to a bug where whenever any other caller has the 'recursive' flag set as well as a pathspec with wildcards that all submodules will be indicated as matches. One simple example of this is:
git init repo
cd repogit init submodule
git -C submodule commit -m initial --allow-emptytouch "[bracket]"
git add "[bracket]"
git commit -m bracket
git add submodule
git commit -m submodule
Quoted 7 lines
git rev-list HEAD -- "[bracket]"
Fix this by introducing the new flag '
recurse_submodules' in 'struct pathspec' and using this flag to determine if matches should be allowed to cross submodule boundaries.Signed-off-by Brandon Williams <[email protected]>
Could you also add something like
This fixes https://github.com/git-for-windows/git/issues/1371
at the end of the commit message, to keep a reference to the original bug report?
Quoted 1 line
4 files changed, 22 insertions(+), 2 deletions(-)
Phew. That was much smaller than I expected.
Quoted 6 lines
t/t4208-log-magic-pathspec.sh +6
-0+test_expect_success 'tree_entry_interesting does not match past submodule boundaries' ' + test_when_finished "rm -rf repo submodule" && + git init submodule && + test_commit -C submodule initial && + git init repo && + >"repo/[bracket]" &&
t/t4208-log-magic-pathspec.sh test_expect_success 'command line pathspec parsing for "git log"' ' · line 111
Quoted 10 lines
t/t4208-log-magic-pathspec.sh +10
-0+ git -C repo add "[bracket]" && + git -C repo commit -m bracket && + git -C repo rev-list HEAD -- "[bracket]" >expect && + + git -C repo submodule add ../submodule && + git -C repo commit -m submodule && + + git -C repo rev-list HEAD -- "[bracket]" >actual && + test_cmp expect actual +'
Nicely prepared for a new hash function, too (no explicit SHA-1).
I wonder, however, why we can't git checkout -b bracket and test_when_finished "git checkout master" and void those many -C repo options. But then, it is actually one of the shorter test cases, and pretty easy to understand.
However, I would still like to see test_ticks before those git commit calls, to make the commit names reproducible.
Thanks,
Dscho
Re: [PATCH] pathspec: only match across submodule boundaries when requested
Quoted 35 lines · Johannes Schindelin
Hi Brandon,
Quoted 31 lines · Brandon Williams
Commit
74ed43711fd(grep: enable recurse-submodules to work on <tree> objects, 2016-12-16) taught 'tree_entry_interesting()' to be able to match across submodule boundaries in the presence of wildcards. This is done by performing literal matching up to the first wildcard and then punting to the submodule itself to perform more accurate pattern matching. Instead of introducing a new flag to request this behavior, commit74ed43711fdoverloaded the already existing 'recursive' flag in 'struct pathspec' to request this behavior.This leads to a bug where whenever any other caller has the 'recursive' flag set as well as a pathspec with wildcards that all submodules will be indicated as matches. One simple example of this is:
git init repo
cd repogit init submodule
git -C submodule commit -m initial --allow-emptytouch "[bracket]"
git add "[bracket]"
git commit -m bracket
git add submodule
git commit -m submodulegit rev-list HEAD -- "[bracket]"
Fix this by introducing the new flag '
recurse_submodules' in 'struct pathspec' and using this flag to determine if matches should be allowed to cross submodule boundaries.
Quoted 8 lines
Quoted 1 line
Signed-off-by Brandon Williams <[email protected]>Could you also add something like
This fixes https://github.com/git-for-windows/git/issues/1371
at the end of the commit message, to keep a reference to the original bug report?
Yep! I can do that.
Quoted 24 lines
Quoted 2 lines
4 files changed, 22 insertions(+), 2 deletions(-)Phew. That was much smaller than I expected.
Quoted 6 lines
t/t4208-log-magic-pathspec.sh +6
-0+test_expect_success 'tree_entry_interesting does not match past submodule boundaries' ' + test_when_finished "rm -rf repo submodule" && + git init submodule && + test_commit -C submodule initial && + git init repo && + >"repo/[bracket]" &&t/t4208-log-magic-pathspec.sh test_expect_success 'command line pathspec parsing for "git log"' ' · line 111
Quoted 10 lines
t/t4208-log-magic-pathspec.sh +10
-0+ git -C repo add "[bracket]" && + git -C repo commit -m bracket && + git -C repo rev-list HEAD -- "[bracket]" >expect && + + git -C repo submodule add ../submodule && + git -C repo commit -m submodule && + + git -C repo rev-list HEAD -- "[bracket]" >actual && + test_cmp expect actual +'Nicely prepared for a new hash function, too (no explicit SHA-1).
Quoted 7 lines
I wonder, however, why we can't
git checkout -b bracketandtest_when_finished "git checkout master"and void those many-C repooptions. But then, it is actually one of the shorter test cases, and pretty easy to understand.However, I would still like to see
test_ticks before thosegit commitcalls, to make the commit names reproducible.
In v2 I added the calls to test_tick. I've never used the function myself so hopefully I used it correctly! :)
Quoted 3 lines
Thanks,
Dscho
Signature · 1 line
Brandon Williams
PATCH v2 1/1 pathspec: only match across submodule boundaries when requested
In reply to Brandon WilliamsCommit 74ed43711fd (grep: enable recurse-submodules to work on <tree> objects, 2016-12-16) taught 'tree_entry_interesting()' to be able to match across submodule boundaries in the presence of wildcards. This is done by performing literal matching up to the first wildcard and then punting to the submodule itself to perform more accurate pattern matching. Instead of introducing a new flag to request this behavior, commit 74ed43711fd overloaded the already existing 'recursive' flag in 'struct pathspec' to request this behavior.
This leads to a bug where whenever any other caller has the 'recursive' flag set as well as a pathspec with wildcards that all submodules will be indicated as matches. One simple example of this is:
git init repo
cd repo
git init submodule
git -C submodule commit -m initial --allow-empty
touch "[bracket]"
git add "[bracket]"
git commit -m bracket
git add submodule
git commit -m submodule
git rev-list HEAD -- "[bracket]"
Fix this by introducing the new flag 'recurse_submodules' in 'struct pathspec' and using this flag to determine if matches should be allowed to cross submodule boundaries.
This fixes https://github.com/git-for-windows/git/issues/1371.
--- builtin/grep.c | 1 + pathspec.h | 1 + t/t4208-log-magic-pathspec.sh | 19 +++++++++++++++++++ tree-walk.c | 5 +++-- 4 files changed, 24 insertions(+), 2 deletions(-)
builtin/grep.c +1 -0
@@ -1015,6 +1015,7 @@ int cmd_grep(int argc, const char **argv, const char *prefix) prefix, argv + i); pathspec.max_depth = opt.max_depth; pathspec.recursive =1 ; + pathspec.recurse_submodules = !!recurse_submodules;#ifndef NO_PTHREADS if (list.nr || cached || show_in_pager)
pathspec.h +1 -0
@@ -24,6 +24,7 @@ struct pathspec {int nr; unsigned int has_wildcard:1; unsigned int recursive:1; + unsigned int recurse_submodules:1;unsigned magic;int max_depth;struct pathspec_item {
t/t4208-log-magic-pathspec.sh +19 -0
@@ -93,4 +93,23 @@ test_expect_success 'command line pathspec parsing for "git log"' ' git log --merge -- a ' +test_expect_success 'tree_entry_interesting does not match past submodule boundaries' ' + test_when_finished "rm -rf repo submodule" && + git init submodule && + test_commit -C submodule initial && + git init repo && + >"repo/[bracket]" && + git -C repo add "[bracket]" && + test_tick && + git -C repo commit -m bracket && + git -C repo rev-list HEAD -- "[bracket]" >expect && + + git -C repo submodule add ../submodule && + test_tick && + git -C repo commit -m submodule && + + git -C repo rev-list HEAD -- "[bracket]" >actual && + test_cmp expect actual +' + test_done
tree-walk.c +3 -2
@@ -1011,7 +1011,8 @@ static enum interesting do_match(const struct name_entry *entry,* character. More accurate matching can then * be performed in the submodule itself. */ -if (ps->recursive &&S_ISGITLINK (entry->mode) && +if (ps->recurse_submodules && +S_ISGITLINK (entry->mode) && !ps_strncmp (item, match + baselen, entry->path, item->nowildcard_len - baselen))
@@ -1060,7 +1061,7 @@ static enum interesting do_match(const struct name_entry *entry,* character. More accurate matching can then * be performed in the submodule itself. */ -if (ps->recursive &&S_ISGITLINK (entry->mode) && +if (ps->recurse_submodules &&S_ISGITLINK (entry->mode) && !ps_strncmp (item, match, base->buf + base_offset, item->nowildcard_len)) {strbuf_setlen (base, base_offset + baselen);
Signature · 1 line
2.15.1.424.g9478a66081-goog
Re: [PATCH v2] pathspec: only match across submodule boundaries when requested
Quoted 25 lines · Brandon Williams
Commit
74ed43711fd(grep: enable recurse-submodules to work on <tree> objects, 2016-12-16) taught 'tree_entry_interesting()' to be able to match across submodule boundaries in the presence of wildcards. This is done by performing literal matching up to the first wildcard and then punting to the submodule itself to perform more accurate pattern matching. Instead of introducing a new flag to request this behavior, commit74ed43711fdoverloaded the already existing 'recursive' flag in 'struct pathspec' to request this behavior.This leads to a bug where whenever any other caller has the 'recursive' flag set as well as a pathspec with wildcards that all submodules will be indicated as matches. One simple example of this is:
git init repo
cd repogit init submodule
git -C submodule commit -m initial --allow-emptytouch "[bracket]"
git add "[bracket]"
git commit -m bracket
git add submodule
git commit -m submodule
Quoted 5 lines
git rev-list HEAD -- "[bracket]"
Fix this by introducing the new flag '
recurse_submodules' in 'struct pathspec' and using this flag to determine if matches should be allowed to cross submodule boundaries.
Makes sense.
I initially misread the title
"pathspec: only match across submodule boundaries when requested"
to be saying that the match happens only at the boundary, but that "only" is not about where the match happens.
"pathspec: match across submodule boundaries only when requested"
would have avoided such a confusion.
builtin/grep.c int cmd_grep(int argc, const char **argv, const char *prefix) · line 1018
Quoted 9 lines
builtin/grep.c +1
-0@@ -1015,6 +1015,7 @@ int cmd_grep(int argc, const char **argv, const char *prefix) prefix, argv + i); pathspec.max_depth = opt.max_depth; pathspec.recursive =1 ; + pathspec.recurse_submodules = !!recurse_submodules;
With the current code, recurse_submodules can only be 0 or 1 (the only assignment is from the return value of git_config_bool()), so the force-boolean !! is not strictly needed, but it may be a good future-proofing measure.
Will queue; thanks.
Re: [PATCH v2] pathspec: only match across submodule boundaries when requested
In reply to Brandon WilliamsHi Brandon,
Quoted 25 lines · Brandon Williams
Commit
74ed43711fd(grep: enable recurse-submodules to work on <tree> objects, 2016-12-16) taught 'tree_entry_interesting()' to be able to match across submodule boundaries in the presence of wildcards. This is done by performing literal matching up to the first wildcard and then punting to the submodule itself to perform more accurate pattern matching. Instead of introducing a new flag to request this behavior, commit74ed43711fdoverloaded the already existing 'recursive' flag in 'struct pathspec' to request this behavior.This leads to a bug where whenever any other caller has the 'recursive' flag set as well as a pathspec with wildcards that all submodules will be indicated as matches. One simple example of this is:
git init repo
cd repogit init submodule
git -C submodule commit -m initial --allow-emptytouch "[bracket]"
git add "[bracket]"
git commit -m bracket
git add submodule
git commit -m submodule
Quoted 7 lines
git rev-list HEAD -- "[bracket]"
Fix this by introducing the new flag '
recurse_submodules' in 'struct pathspec' and using this flag to determine if matches should be allowed to cross submodule boundaries.This fixes https://github.com/git-for-windows/git/issues/1371.
Thanks,
Dscho