{"thread":{"id":"58900","subject":"[PATCH v2] line-range: Fix infinite loop bug with degenerate regex","startedAt":"2022-12-05T19:45:09Z","lastAt":"2022-12-20T01:08:07Z","messageCount":15,"participants":["Lars Kellogg-Stedman","Eric Sunshine","Ævar Arnfjörð Bjarmason","Junio C Hamano","SZEDER Gábor"],"isPatch":true,"patchVersion":2,"patchTotal":null},"messages":[{"id":"468543","messageId":"20221205193625.2424202-1-lars@oddbit.com","threadId":"58900","inReplyTo":null,"subject":"[PATCH v2] line-range: Fix infinite loop bug with degenerate regex","fromName":"Lars Kellogg-Stedman","fromEmail":"lars@oddbit.com","sentAt":"2022-12-05T19:36:25Z","receivedAt":"2022-12-05T19:45:09Z","isPatch":true,"sender":{"key":"lars@oddbit.com","avatar":"https://avatars.githubusercontent.com/u/82622?v=4"},"body":"When the -L argument to \"git log\" is passed the degenerate regular\nexpression \"$\" (as in \"-L :$:line-range.c\"), this results in an\ninfinite loop in find_funcname_matching_regexp() (the function\niterates through the file correctly, but when it reaches the end of\nthe file it matches $ against the empty string, \"\", and at that points\nloops forever).\n\nModify the loop condition from while (1) to while (*start) so that the\nloop exits when start is the empty string. In this case, \"git log\" exits\nwith the error:\n\n    fatal: -L parameter '$' starting at line 1: no match\n\nOriginally reported in <https://stackoverflow.com/q/74690545/147356>.\n\nSigned-off-by: Lars Kellogg-Stedman <lars@oddbit.com>\n---\n line-range.c | 4 +++-\n 1 file changed, 3 insertions(+), 1 deletion(-)\n\ndiff --git a/line-range.c b/line-range.c\nindex 955a8a9535..bdcb810485 100644\n--- a/line-range.c\n+++ b/line-range.c\n@@ -135,7 +135,7 @@ static const char *find_funcname_matching_regexp(xdemitconf_t *xecfg, const char\n {\n \tint reg_error;\n \tregmatch_t match[1];\n-\twhile (1) {\n+\twhile (*start) {\n \t\tconst char *bol, *eol;\n \t\treg_error = regexec(regexp, start, 1, match, 0);\n \t\tif (reg_error == REG_NOMATCH)\n@@ -161,6 +161,8 @@ static const char *find_funcname_matching_regexp(xdemitconf_t *xecfg, const char\n \t\t\treturn bol;\n \t\tstart = eol;\n \t}\n+\n+    return NULL;\n }\n \n static const char *parse_range_funcname(\n-- \n2.38.1\n\n"},{"id":"468683","messageId":"CAPig+cTypsXUrzkdO7S3cGFRWdO5CiaTKU_uM7av=M3nGHQ0+w@mail.gmail.com","threadId":"58900","inReplyTo":"20221205193625.2424202-1-lars@oddbit.com","subject":"Re: [PATCH v2] line-range: Fix infinite loop bug with degenerate regex","fromName":"Eric Sunshine","fromEmail":"sunshine@sunshineco.com","sentAt":"2022-12-07T04:33:23Z","receivedAt":"2022-12-07T04:33:40Z","isPatch":true,"sender":{"key":"sunshine@sunshineco.com","avatar":"https://avatars.githubusercontent.com/u/163641?v=4"},"body":"On Mon, Dec 5, 2022 at 2:45 PM Lars Kellogg-Stedman <lars@oddbit.com> wrote:\n> line-range: Fix infinite loop bug with degenerate regex\n\ns/Fix/fix/\n\n> When the -L argument to \"git log\" is passed the degenerate regular\n> expression \"$\" (as in \"-L :$:line-range.c\"), this results in an\n> infinite loop in find_funcname_matching_regexp() (the function\n> iterates through the file correctly, but when it reaches the end of\n> the file it matches $ against the empty string, \"\", and at that points\n> loops forever).\n\ns/points/point/\n\n> Modify the loop condition from while (1) to while (*start) so that the\n> loop exits when start is the empty string. In this case, \"git log\" exits\n> with the error:\n>\n>     fatal: -L parameter '$' starting at line 1: no match\n\nI've never really used `-L:funcname:`, so it took me by surprise that\nthis would be reported as a fatal error. However, now that I've read\nthrough the code and put a bit of thought into degenerate cases, I\ncan't come up with any better way to report it. Okay.\n\n> Originally reported in <https://stackoverflow.com/q/74690545/147356>.\n>\n> Signed-off-by: Lars Kellogg-Stedman <lars@oddbit.com>\n> ---\n> diff --git a/line-range.c b/line-range.c\n> @@ -135,7 +135,7 @@ static const char *find_funcname_matching_regexp(xdemitconf_t *xecfg, const char\n>  {\n>         int reg_error;\n>         regmatch_t match[1];\n> -       while (1) {\n> +       while (*start) {\n>                 const char *bol, *eol;\n>                 reg_error = regexec(regexp, start, 1, match, 0);\n>                 if (reg_error == REG_NOMATCH)\n> @@ -161,6 +161,8 @@ static const char *find_funcname_matching_regexp(xdemitconf_t *xecfg, const char\n>                         return bol;\n>                 start = eol;\n>         }\n> +\n> +    return NULL;\n>  }\n\nI'm not particularly familiar with this code (even though I touched it\nyears ago), so I can't say whether this is the best fix, but it seems\nreasonable now that I've studied the code and put some thought into\ndegenerate cases. I had wondered if it would be possible to catch\nthese degenerate cases in some general way, but whatever ideas I had\nseemed too special-purpose; your solution here is straightforward and\nprobably more robust than special-purpose code.\n\nStyle-wise, I'd probably drop the blank line before `return NULL`.\n\nPlease do re-roll once more with a test which verifies that this bug\nhas been fixed. Here's a test you can add to the bottom of\nt/t4211-line-log.sh for that purpose (be sure to re-indent it with\nTABs which Gmail mushes out):\n\n    test_expect_success 'degenerate -L:$: does not hang' '\n        >content-immaterial &&\n        git add content-immaterial &&\n        git commit -m immaterial &&\n        test_must_fail git log -L:$:content-immaterial\n    '\n\nAnd here's my sign-off which you can insert above your own sign-off if\nyou include the above test.\n\n    Signed-off-by: Eric Sunshine <sunshine@sunshineco.com>\n"},{"id":"468687","messageId":"221207.86tu27aju3.gmgdl@evledraar.gmail.com","threadId":"58900","inReplyTo":"20221205193625.2424202-1-lars@oddbit.com","subject":"Re: [PATCH v2] line-range: Fix infinite loop bug with degenerate regex","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2022-12-07T04:52:04Z","receivedAt":"2022-12-07T05:01:15Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Mon, Dec 05 2022, Lars Kellogg-Stedman wrote:\n\n> When the -L argument to \"git log\" is passed the degenerate regular\n> expression \"$\" (as in \"-L :$:line-range.c\"), this results in an\n> infinite loop in find_funcname_matching_regexp() (the function\n> iterates through the file correctly, but when it reaches the end of\n> the file it matches $ against the empty string, \"\", and at that points\n> loops forever).\n>\n> Modify the loop condition from while (1) to while (*start) so that the\n> loop exits when start is the empty string. In this case, \"git log\" exits\n> with the error:\n>\n>     fatal: -L parameter '$' starting at line 1: no match\n>\n> Originally reported in <https://stackoverflow.com/q/74690545/147356>.\n>\n> Signed-off-by: Lars Kellogg-Stedman <lars@oddbit.com>\n> ---\n>  line-range.c | 4 +++-\n>  1 file changed, 3 insertions(+), 1 deletion(-)\n>\n> diff --git a/line-range.c b/line-range.c\n> index 955a8a9535..bdcb810485 100644\n> --- a/line-range.c\n> +++ b/line-range.c\n> @@ -135,7 +135,7 @@ static const char *find_funcname_matching_regexp(xdemitconf_t *xecfg, const char\n>  {\n>  \tint reg_error;\n>  \tregmatch_t match[1];\n> -\twhile (1) {\n> +\twhile (*start) {\n>  \t\tconst char *bol, *eol;\n>  \t\treg_error = regexec(regexp, start, 1, match, 0);\n>  \t\tif (reg_error == REG_NOMATCH)\n> @@ -161,6 +161,8 @@ static const char *find_funcname_matching_regexp(xdemitconf_t *xecfg, const char\n>  \t\t\treturn bol;\n>  \t\tstart = eol;\n>  \t}\n> +\n> +    return NULL;\n>  }\n>  \n>  static const char *parse_range_funcname(\n\nWe really should fix this, but why not just count this as a match,\nrather than erroring out?\n\nThat we're mixing up whether '$' always matches here with our iteration\nloop is our own internal bug, we shouldn't error out on a '$'. It's just\na regex that happens to match everything.\n\nIt's perfectly OK to provide a zero-width regex in general, e.g. try:\n\n     git config --get-regexp '$'\n\nOr for a non-git tool:\n\n\tgrep '$' FILE\n\nI think the real bug here is that we are pointing our regexec() at the\nhaystack of multiple lines as an optimization.\n\nThen in \"determine extent of line matched\" and \"is it a funcname line\"\nassuming that a positive match must be non-zero-width. But that's just\nbecause the optimization is leaky.\n"},{"id":"468688","messageId":"xmqq359r7pdd.fsf@gitster.g","threadId":"58900","inReplyTo":"221207.86tu27aju3.gmgdl@evledraar.gmail.com","subject":"Re: [PATCH v2] line-range: Fix infinite loop bug with degenerate regex","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-12-07T05:29:50Z","receivedAt":"2022-12-07T05:29:58Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Ævar Arnfjörð Bjarmason <avarab@gmail.com> writes:\n\n> It's perfectly OK to provide a zero-width regex in general, e.g. try:\n> Or for a non-git tool:\n> ...\n\nThe same story goes for \"^\" or even \".*\", I suspect.\n\n> I think the real bug here is that we are pointing our regexec() at the\n> haystack of multiple lines as an optimization.\n>\n> Then in \"determine extent of line matched\" and \"is it a funcname line\"\n> assuming that a positive match must be non-zero-width. But that's just\n> because the optimization is leaky.\n\nGood thinking.\n\n"},{"id":"468735","messageId":"20221207203047.GA2996@szeder.dev","threadId":"58900","inReplyTo":"221207.86tu27aju3.gmgdl@evledraar.gmail.com","subject":"Re: [PATCH v2] line-range: Fix infinite loop bug with degenerate regex","fromName":"SZEDER Gábor","fromEmail":"szeder.dev@gmail.com","sentAt":"2022-12-07T20:30:47Z","receivedAt":"2022-12-07T20:30:54Z","isPatch":true,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"On Wed, Dec 07, 2022 at 05:52:04AM +0100, Ævar Arnfjörð Bjarmason wrote:\n> \n> On Mon, Dec 05 2022, Lars Kellogg-Stedman wrote:\n> \n> > When the -L argument to \"git log\" is passed the degenerate regular\n> > expression \"$\" (as in \"-L :$:line-range.c\"), this results in an\n> > infinite loop in find_funcname_matching_regexp() (the function\n> > iterates through the file correctly, but when it reaches the end of\n> > the file it matches $ against the empty string, \"\", and at that points\n> > loops forever).\n> >\n> > Modify the loop condition from while (1) to while (*start) so that the\n> > loop exits when start is the empty string. In this case, \"git log\" exits\n> > with the error:\n> >\n> >     fatal: -L parameter '$' starting at line 1: no match\n> >\n> > Originally reported in <https://stackoverflow.com/q/74690545/147356>.\n> >\n> > Signed-off-by: Lars Kellogg-Stedman <lars@oddbit.com>\n> > ---\n> >  line-range.c | 4 +++-\n> >  1 file changed, 3 insertions(+), 1 deletion(-)\n> >\n> > diff --git a/line-range.c b/line-range.c\n> > index 955a8a9535..bdcb810485 100644\n> > --- a/line-range.c\n> > +++ b/line-range.c\n> > @@ -135,7 +135,7 @@ static const char *find_funcname_matching_regexp(xdemitconf_t *xecfg, const char\n> >  {\n> >  \tint reg_error;\n> >  \tregmatch_t match[1];\n> > -\twhile (1) {\n> > +\twhile (*start) {\n> >  \t\tconst char *bol, *eol;\n> >  \t\treg_error = regexec(regexp, start, 1, match, 0);\n> >  \t\tif (reg_error == REG_NOMATCH)\n> > @@ -161,6 +161,8 @@ static const char *find_funcname_matching_regexp(xdemitconf_t *xecfg, const char\n> >  \t\t\treturn bol;\n> >  \t\tstart = eol;\n> >  \t}\n> > +\n> > +    return NULL;\n> >  }\n> >  \n> >  static const char *parse_range_funcname(\n> \n> We really should fix this, but why not just count this as a match,\n> rather than erroring out?\n> \n> That we're mixing up whether '$' always matches here with our iteration\n> loop is our own internal bug, we shouldn't error out on a '$'. It's just\n> a regex that happens to match everything.\n\nIndeed.  The description of '-L...' in the manpage of 'git log' (and\n'blame') states:\n\n    If :<funcname> is given in place of <start> and <end>, it is a\n    regular expression that denotes the range from the first funcname\n    line that matches <funcname>, up to the next funcname line.\n\nSo, if we use '-L' with a funcname regex that matches every line, be\nit '$', '^' or '.*', then this would mean that it should denote the\nrange from the first funcname line in that file to the second.\n\n"},{"id":"468836","messageId":"20221209191639.ixsvxgf5ef2zloik@oddbit.com","threadId":"58900","inReplyTo":"221207.86tu27aju3.gmgdl@evledraar.gmail.com","subject":"Re: [PATCH v2] line-range: Fix infinite loop bug with degenerate regex","fromName":"Lars Kellogg-Stedman","fromEmail":"lars@oddbit.com","sentAt":"2022-12-09T19:16:39Z","receivedAt":"2022-12-09T19:21:48Z","isPatch":true,"sender":{"key":"lars@oddbit.com","avatar":"https://avatars.githubusercontent.com/u/82622?v=4"},"body":"On Wed, Dec 07, 2022 at 05:52:04AM +0100, Ævar Arnfjörð Bjarmason wrote:\n> We really should fix this, but why not just count this as a match,\n> rather than erroring out?\n> \n> That we're mixing up whether '$' always matches here with our iteration\n> loop is our own internal bug, we shouldn't error out on a '$'. It's just\n> a regex that happens to match everything.\n\nThanks, that makes a lot of sense. I'll try to rework things this\nweekend.\n\nCheers,\n\n-- \nLars Kellogg-Stedman <lars@oddbit.com> | larsks @ {irc,twitter,github}\nhttp://blog.oddbit.com/                | N1LKS\n"},{"id":"468859","messageId":"20221211015340.2181837-1-lars@oddbit.com","threadId":"58900","inReplyTo":"20221205193625.2424202-1-lars@oddbit.com","subject":"[PATCH v3] line-range: Fix infinite loop bug with degenerate '$' regex","fromName":"Lars Kellogg-Stedman","fromEmail":"lars@oddbit.com","sentAt":"2022-12-11T01:53:40Z","receivedAt":"2022-12-11T01:53:56Z","isPatch":true,"sender":{"key":"lars@oddbit.com","avatar":"https://avatars.githubusercontent.com/u/82622?v=4"},"body":"When the -L argument to \"git log\" is passed the degenerate regular\nexpression \"$\" (as in \"-L :$:line-range.c\"), this results in an\ninfinite loop in find_funcname_matching_regexp().\n\nModify find_funcname_matching_regexp to correctly match the entire line\ninstead of the zero-width match at eol and update the loop condition to\nprevent an infinite loop in the event of other undiscovered corner cases.\n\nOriginally reported in <https://stackoverflow.com/q/74690545/147356>.\n\nSigned-off-by: Lars Kellogg-Stedman <lars@oddbit.com>\n---\nThis modifies my earlier patch so that instead of failing, the\nregular expression '$' correctly matches any function name (and so\nalways returns the first function in the named file). This makes '$'\nbehave the same as '.' and '^'.\n\nThe primary change is that we pre-decrement the beginning-of-line\nmarker ('bol') before comparing it to '\\n'. In the case of '$', where\nwe start with bol == eol, this ensures that bol will find the\nbeginning of the line on which the match occurred.\n\n line-range.c        |  6 +++---\n t/t4211-line-log.sh | 22 ++++++++++++++++++++++\n 2 files changed, 25 insertions(+), 3 deletions(-)\n\ndiff --git a/line-range.c b/line-range.c\nindex 955a8a9535..b0e26e7f9d 100644\n--- a/line-range.c\n+++ b/line-range.c\n@@ -135,7 +135,7 @@ static const char *find_funcname_matching_regexp(xdemitconf_t *xecfg, const char\n {\n \tint reg_error;\n \tregmatch_t match[1];\n-\twhile (1) {\n+\twhile (*start) {\n \t\tconst char *bol, *eol;\n \t\treg_error = regexec(regexp, start, 1, match, 0);\n \t\tif (reg_error == REG_NOMATCH)\n@@ -148,8 +148,7 @@ static const char *find_funcname_matching_regexp(xdemitconf_t *xecfg, const char\n \t\t/* determine extent of line matched */\n \t\tbol = start+match[0].rm_so;\n \t\teol = start+match[0].rm_eo;\n-\t\twhile (bol > start && *bol != '\\n')\n-\t\t\tbol--;\n+\t\twhile (bol > start && *--bol != '\\n');\n \t\tif (*bol == '\\n')\n \t\t\tbol++;\n \t\twhile (*eol && *eol != '\\n')\n@@ -161,6 +160,7 @@ static const char *find_funcname_matching_regexp(xdemitconf_t *xecfg, const char\n \t\t\treturn bol;\n \t\tstart = eol;\n \t}\n+\treturn NULL;\n }\n \n static const char *parse_range_funcname(\ndiff --git a/t/t4211-line-log.sh b/t/t4211-line-log.sh\nindex ac9e4d0928..19db07a8df 100755\n--- a/t/t4211-line-log.sh\n+++ b/t/t4211-line-log.sh\n@@ -315,4 +315,26 @@ test_expect_success 'line-log with --before' '\n \ttest_cmp expect actual\n '\n \n+test_expect_success 'setup tests for zero-width regular expressions' '\n+\tcat > expect <<-EOF\n+\tModify func1() in file.c\n+\tAdd func1() and func2() in file.c\n+\tEOF\n+'\n+\n+test_expect_success 'zero-width regex $ matches any function name' '\n+\tgit log --format=\"%s\" --no-patch \"-L:$:file.c\" >actual &&\n+\ttest_cmp expect actual\n+'\n+\n+test_expect_success 'zero-width regex ^ matches any function name' '\n+\tgit log --format=\"%s\" --no-patch \"-L:^:file.c\" >actual &&\n+\ttest_cmp expect actual\n+'\n+\n+test_expect_success 'zero-width regex . matches any function name' '\n+\tgit log --format=\"%s\" --no-patch \"-L:.:file.c\" >actual &&\n+\ttest_cmp expect actual\n+'\n+\n test_done\n-- \n2.38.1\n\n"},{"id":"468860","messageId":"xmqq5yeiwr6x.fsf@gitster.g","threadId":"58900","inReplyTo":"20221211015340.2181837-1-lars@oddbit.com","subject":"Re: [PATCH v3] line-range: Fix infinite loop bug with degenerate '$' regex","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-12-11T03:32:38Z","receivedAt":"2022-12-11T03:32:44Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Lars Kellogg-Stedman <lars@oddbit.com> writes:\n\n> When the -L argument to \"git log\" is passed the degenerate regular\n> expression \"$\" (as in \"-L :$:line-range.c\"), this results in an\n> infinite loop in find_funcname_matching_regexp().\n\nIs \"matching an empty line\" the only way a regular expression can be\na \"degenerate\" one?  If not, perhaps being a bit more explicit would\nhelp the readers, e.g.\n\n    ... a regular expression that matches any line, even an empty\n    one, such as \"-L :$:line-range.c\", this results in ...\n\n> The primary change is that we pre-decrement the beginning-of-line\n> marker ('bol') before comparing it to '\\n'. In the case of '$', where\n> we start with bol == eol, this ensures that bol will find the\n> beginning of the line on which the match occurred.\n\nThis clear explanation probably deserves to be in the commit log\nmessage proper.\n\n> @@ -148,8 +148,7 @@ static const char *find_funcname_matching_regexp(xdemitconf_t *xecfg, const char\n>  \t\t/* determine extent of line matched */\n>  \t\tbol = start+match[0].rm_so;\n>  \t\teol = start+match[0].rm_eo;\n> -\t\twhile (bol > start && *bol != '\\n')\n> -\t\t\tbol--;\n> +\t\twhile (bol > start && *--bol != '\\n');\n\nPlease write it on two lines, and highlight an empty body of the\nloop, like so\n\n\t\twhile (condition)\n\t\t\t; /* nothing */\n\nI think the intention of the above loop is to decrement bol\nsufficiently and make it point at the terminating LF at the end\nof the previous line, and then the next increment here\n\n>  \t\tif (*bol == '\\n')\n>  \t\t\tbol++;\n\ncompensates to bring bol back to point at the beginning of line.\n\nIn the iteration of the loop when bol == start + 1, we inspect\n*--bol (i.e.  *start).  If it is LF, we exit the loop, so bol ==\nstart and *bol == '\\n'.  If it is not LF, we iterate one more time,\nnotice bol == start and exit the loop, so bol == start and *bol !=\n'\\n'.  bol will never go below start, so dereference *bol to see it\nvalue where should be safe without OOB read.\n\n> @@ -161,6 +160,7 @@ static const char *find_funcname_matching_regexp(xdemitconf_t *xecfg, const char\n>  \t\t\treturn bol;\n>  \t\tstart = eol;\n>  \t}\n> +\treturn NULL;\n>  }\n\nWhat is this change about?  Isn't the above an endless loop without\nbreak, from which the only way for the control to leave it is by\nreturning?\n\n> diff --git a/t/t4211-line-log.sh b/t/t4211-line-log.sh\n> index ac9e4d0928..19db07a8df 100755\n> --- a/t/t4211-line-log.sh\n> +++ b/t/t4211-line-log.sh\n> @@ -315,4 +315,26 @@ test_expect_success 'line-log with --before' '\n>  \ttest_cmp expect actual\n>  '\n>  \n> +test_expect_success 'setup tests for zero-width regular expressions' '\n> +\tcat > expect <<-EOF\n\nStyle: lose the SP after \"cat >\".\n\n> +\tModify func1() in file.c\n> +\tAdd func1() and func2() in file.c\n> +\tEOF\n> +'\n> +\n> +test_expect_success 'zero-width regex $ matches any function name' '\n> +\tgit log --format=\"%s\" --no-patch \"-L:$:file.c\" >actual &&\n> +\ttest_cmp expect actual\n> +'\n> +\n> +test_expect_success 'zero-width regex ^ matches any function name' '\n> +\tgit log --format=\"%s\" --no-patch \"-L:^:file.c\" >actual &&\n> +\ttest_cmp expect actual\n> +'\n> +\n> +test_expect_success 'zero-width regex . matches any function name' '\n\n\".\" is one character wide, not zero-width.  Did you mean \".*\"?\n\n> +\tgit log --format=\"%s\" --no-patch \"-L:.:file.c\" >actual &&\n> +\ttest_cmp expect actual\n> +'\n> +\n>  test_done\n"},{"id":"468861","messageId":"xmqq1qp6wr46.fsf@gitster.g","threadId":"58900","inReplyTo":"xmqq5yeiwr6x.fsf@gitster.g","subject":"Re: [PATCH v3] line-range: Fix infinite loop bug with degenerate '$' regex","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-12-11T03:34:17Z","receivedAt":"2022-12-11T03:34:23Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> Lars Kellogg-Stedman <lars@oddbit.com> writes:\n>\n>> When the -L argument to \"git log\" is passed the degenerate regular\n>> expression \"$\" (as in \"-L :$:line-range.c\"), this results in an\n>> infinite loop in find_funcname_matching_regexp().\n>\n> Is \"matching an empty line\" the only way a regular expression can be\n> a \"degenerate\" one?  If not, perhaps being a bit more explicit would\n> help the readers, e.g.\n>\n>     ... a regular expression that matches any line, even an empty\n>     one, such as \"-L :$:line-range.c\", this results in ...\n\nI forgot to point out that the above comment on \"degenerate\" applies\nequally to the commit title (which matters more).  Also, please do\nnot upcase the first word after \"<area>:\" on the title line.\n\nThanks.\n"},{"id":"469014","messageId":"20221214145341.sonppjtshwqoxs6n@oddbit.com","threadId":"58900","inReplyTo":"xmqq5yeiwr6x.fsf@gitster.g","subject":"Re: [PATCH v3] line-range: Fix infinite loop bug with degenerate '$' regex","fromName":"Lars Kellogg-Stedman","fromEmail":"lars@oddbit.com","sentAt":"2022-12-14T14:53:41Z","receivedAt":"2022-12-14T14:53:46Z","isPatch":true,"sender":{"key":"lars@oddbit.com","avatar":"https://avatars.githubusercontent.com/u/82622?v=4"},"body":"On Sun, Dec 11, 2022 at 12:32:38PM +0900, Junio C Hamano wrote:\n> Lars Kellogg-Stedman <lars@oddbit.com> writes:\n> \n> > When the -L argument to \"git log\" is passed the degenerate regular\n> > expression \"$\" (as in \"-L :$:line-range.c\"), this results in an\n> > infinite loop in find_funcname_matching_regexp().\n> \n> Is \"matching an empty line\" the only way a regular expression can be\n> a \"degenerate\" one?  If not, perhaps being a bit more explicit would\n> help the readers, e.g.\n\n\"Matching an empty line\" isn't the issue (and if I implied that it\nwas, that's my bad). The issue only crops up when matching the\nzero-width regular expression at the *end* of a line.\n\nI'll update the subject and description to be more clear...\n\n> This clear explanation probably deserves to be in the commit log\n> message proper.\n\n...including adding the extended description to the commit message. Some projects\nobject if commit messages get too wordy.\n\n> Please write it on two lines, and highlight an empty body of the\n> loop, like so\n\nWill do.\n\n> > @@ -161,6 +160,7 @@ static const char *find_funcname_matching_regexp(xdemitconf_t *xecfg, const char\n> >  \t\t\treturn bol;\n> >  \t\tstart = eol;\n> >  \t}\n> > +\treturn NULL;\n> >  }\n> \n> What is this change about?  Isn't the above an endless loop without\n> break, from which the only way for the control to leave it is by\n> returning?\n\nIt's not an endless loop without break; this change modified the loop\ncondition:\n\n> -       while (1) {\n> +       while (*start) {\n\nThat would have prevented the infinite loop in the first place. I'm\nhappy to drop this change if you prefer, but if this condition had\nbeen in place originally we wouldn't have had the infinite loop bug\n(we would still have had incorrect behavior, but it would have been\nperhaps easier for an end user to diagnose).\n\n> Style: lose the SP after \"cat >\".\n\nWill do.\n\n-- \nLars Kellogg-Stedman <lars@oddbit.com> | larsks @ {irc,twitter,github}\nhttp://blog.oddbit.com/                | N1LKS\n"},{"id":"469237","messageId":"xmqqa63lzeb0.fsf@gitster.g","threadId":"58900","inReplyTo":"20221214145341.sonppjtshwqoxs6n@oddbit.com","subject":"Re: [PATCH v3] line-range: Fix infinite loop bug with degenerate '$' regex","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-12-18T01:33:07Z","receivedAt":"2022-12-18T01:36:54Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Lars Kellogg-Stedman <lars@oddbit.com> writes:\n\n>> > @@ -161,6 +160,7 @@ static const char *find_funcname_matching_regexp(xdemitconf_t *xecfg, const char\n>> >  \t\t\treturn bol;\n>> >  \t\tstart = eol;\n>> >  \t}\n>> > +\treturn NULL;\n>> >  }\n>> \n>> What is this change about?  Isn't the above an endless loop without\n>> break, from which the only way for the control to leave it is by\n>> returning?\n>\n> It's not an endless loop without break; this change modified the loop\n> condition:\n\nAh, thanks, that's clear, and sorry for the noise, and thanks.\n\n"},{"id":"469318","messageId":"20221219224850.2703967-1-lars@oddbit.com","threadId":"58900","inReplyTo":"20221205193625.2424202-1-lars@oddbit.com","subject":"[PATCH v4] line-range: fix infinite loop bug with '$' regex","fromName":"Lars Kellogg-Stedman","fromEmail":"lars@oddbit.com","sentAt":"2022-12-19T22:48:50Z","receivedAt":"2022-12-19T22:49:02Z","isPatch":true,"sender":{"key":"lars@oddbit.com","avatar":"https://avatars.githubusercontent.com/u/82622?v=4"},"body":"When the -L argument to \"git log\" is passed the zero-width regular\nexpression \"$\" (as in \"-L :$:line-range.c\"), this results in an\ninfinite loop in find_funcname_matching_regexp().\n\nModify find_funcname_matching_regexp to correctly match the entire line\ninstead of the zero-width match at eol and update the loop condition to\nprevent an infinite loop in the event of other undiscovered corner cases.\n\nThe primary change is that we pre-decrement the beginning-of-line marker\n('bol') before comparing it to '\\n'. In the case of '$', where we match the\n'\\n' at the end of the line and start the loop with bol == eol, this\nensures that bol will find the beginning of the line on which the match\noccurred.\n\nOriginally reported in <https://stackoverflow.com/q/74690545/147356>.\n\nSigned-off-by: Lars Kellogg-Stedman <lars@oddbit.com>\n---\n line-range.c        |  7 ++++---\n t/t4211-line-log.sh | 22 ++++++++++++++++++++++\n 2 files changed, 26 insertions(+), 3 deletions(-)\n\ndiff --git a/line-range.c b/line-range.c\nindex 955a8a9535..47bf0d6f1a 100644\n--- a/line-range.c\n+++ b/line-range.c\n@@ -135,7 +135,7 @@ static const char *find_funcname_matching_regexp(xdemitconf_t *xecfg, const char\n {\n \tint reg_error;\n \tregmatch_t match[1];\n-\twhile (1) {\n+\twhile (*start) {\n \t\tconst char *bol, *eol;\n \t\treg_error = regexec(regexp, start, 1, match, 0);\n \t\tif (reg_error == REG_NOMATCH)\n@@ -148,8 +148,8 @@ static const char *find_funcname_matching_regexp(xdemitconf_t *xecfg, const char\n \t\t/* determine extent of line matched */\n \t\tbol = start+match[0].rm_so;\n \t\teol = start+match[0].rm_eo;\n-\t\twhile (bol > start && *bol != '\\n')\n-\t\t\tbol--;\n+\t\twhile (bol > start && *--bol != '\\n')\n+\t\t\t; /* nothing */\n \t\tif (*bol == '\\n')\n \t\t\tbol++;\n \t\twhile (*eol && *eol != '\\n')\n@@ -161,6 +161,7 @@ static const char *find_funcname_matching_regexp(xdemitconf_t *xecfg, const char\n \t\t\treturn bol;\n \t\tstart = eol;\n \t}\n+\treturn NULL;\n }\n \n static const char *parse_range_funcname(\ndiff --git a/t/t4211-line-log.sh b/t/t4211-line-log.sh\nindex ac9e4d0928..c6540e822f 100755\n--- a/t/t4211-line-log.sh\n+++ b/t/t4211-line-log.sh\n@@ -315,4 +315,26 @@ test_expect_success 'line-log with --before' '\n \ttest_cmp expect actual\n '\n \n+test_expect_success 'setup tests for zero-width regular expressions' '\n+\tcat >expect <<-EOF\n+\tModify func1() in file.c\n+\tAdd func1() and func2() in file.c\n+\tEOF\n+'\n+\n+test_expect_success 'zero-width regex $ matches any function name' '\n+\tgit log --format=\"%s\" --no-patch \"-L:$:file.c\" >actual &&\n+\ttest_cmp expect actual\n+'\n+\n+test_expect_success 'zero-width regex ^ matches any function name' '\n+\tgit log --format=\"%s\" --no-patch \"-L:^:file.c\" >actual &&\n+\ttest_cmp expect actual\n+'\n+\n+test_expect_success 'zero-width regex .* matches any function name' '\n+\tgit log --format=\"%s\" --no-patch \"-L:.*:file.c\" >actual &&\n+\ttest_cmp expect actual\n+'\n+\n test_done\n-- \n2.38.1\n\n"},{"id":"469319","messageId":"221219.86edsvxank.gmgdl@evledraar.gmail.com","threadId":"58900","inReplyTo":"20221219224850.2703967-1-lars@oddbit.com","subject":"Re: [PATCH v4] line-range: fix infinite loop bug with '$' regex","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2022-12-19T22:55:41Z","receivedAt":"2022-12-19T22:59:40Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Mon, Dec 19 2022, Lars Kellogg-Stedman wrote:\n\n> When the -L argument to \"git log\" is passed the zero-width regular\n> expression \"$\" (as in \"-L :$:line-range.c\"), this results in an\n> infinite loop in find_funcname_matching_regexp().\n>\n> Modify find_funcname_matching_regexp to correctly match the entire line\n> instead of the zero-width match at eol and update the loop condition to\n> prevent an infinite loop in the event of other undiscovered corner cases.\n>\n> The primary change is that we pre-decrement the beginning-of-line marker\n> ('bol') before comparing it to '\\n'. In the case of '$', where we match the\n> '\\n' at the end of the line and start the loop with bol == eol, this\n> ensures that bol will find the beginning of the line on which the match\n> occurred.\n>\n> Originally reported in <https://stackoverflow.com/q/74690545/147356>.\n>\n> Signed-off-by: Lars Kellogg-Stedman <lars@oddbit.com>\n> ---\n>  line-range.c        |  7 ++++---\n>  t/t4211-line-log.sh | 22 ++++++++++++++++++++++\n>  2 files changed, 26 insertions(+), 3 deletions(-)\n>\n> diff --git a/line-range.c b/line-range.c\n> index 955a8a9535..47bf0d6f1a 100644\n> --- a/line-range.c\n> +++ b/line-range.c\n> @@ -135,7 +135,7 @@ static const char *find_funcname_matching_regexp(xdemitconf_t *xecfg, const char\n>  {\n>  \tint reg_error;\n>  \tregmatch_t match[1];\n> -\twhile (1) {\n> +\twhile (*start) {\n>  \t\tconst char *bol, *eol;\n>  \t\treg_error = regexec(regexp, start, 1, match, 0);\n>  \t\tif (reg_error == REG_NOMATCH)\n> @@ -148,8 +148,8 @@ static const char *find_funcname_matching_regexp(xdemitconf_t *xecfg, const char\n>  \t\t/* determine extent of line matched */\n>  \t\tbol = start+match[0].rm_so;\n>  \t\teol = start+match[0].rm_eo;\n> -\t\twhile (bol > start && *bol != '\\n')\n> -\t\t\tbol--;\n> +\t\twhile (bol > start && *--bol != '\\n')\n> +\t\t\t; /* nothing */\n>  \t\tif (*bol == '\\n')\n>  \t\t\tbol++;\n>  \t\twhile (*eol && *eol != '\\n')\n> @@ -161,6 +161,7 @@ static const char *find_funcname_matching_regexp(xdemitconf_t *xecfg, const char\n>  \t\t\treturn bol;\n>  \t\tstart = eol;\n>  \t}\n> +\treturn NULL;\n>  }\n>  \n>  static const char *parse_range_funcname(\n> diff --git a/t/t4211-line-log.sh b/t/t4211-line-log.sh\n> index ac9e4d0928..c6540e822f 100755\n> --- a/t/t4211-line-log.sh\n> +++ b/t/t4211-line-log.sh\n> @@ -315,4 +315,26 @@ test_expect_success 'line-log with --before' '\n>  \ttest_cmp expect actual\n>  '\n>  \n> +test_expect_success 'setup tests for zero-width regular expressions' '\n> +\tcat >expect <<-EOF\n> +\tModify func1() in file.c\n> +\tAdd func1() and func2() in file.c\n> +\tEOF\n> +'\n> +\n> +test_expect_success 'zero-width regex $ matches any function name' '\n> +\tgit log --format=\"%s\" --no-patch \"-L:$:file.c\" >actual &&\n> +\ttest_cmp expect actual\n> +'\n> +\n> +test_expect_success 'zero-width regex ^ matches any function name' '\n> +\tgit log --format=\"%s\" --no-patch \"-L:^:file.c\" >actual &&\n> +\ttest_cmp expect actual\n> +'\n> +\n> +test_expect_success 'zero-width regex .* matches any function name' '\n> +\tgit log --format=\"%s\" --no-patch \"-L:.*:file.c\" >actual &&\n> +\ttest_cmp expect actual\n> +'\n> +\n\nUntested, but as most of this is repeated & would fail if the \"setup\"\ntest is skipped, a one-off function would be better, e.g.:\n\t\n\ttest_zerowidth_regex () {\n\t\tlocal rx=\"$1\" &&\n\t\t\n\t\ttest_expect_success \"zero-width regex '$rx' matches any function name\" '\n\t\t\tcat >expect <<-\\EOF &&\n\t\t\tModify func1() in file.c\n\t\t\tAdd func1() and func2() in file.c\n\t\t\tEOF\n\t\t\tgit log --format=\"%s\" --no-patch -L:\"$rx\":file.c >actual &&\n\t\t\ttest_cmp expect actual\n\t\t'\n\t}\n\t\n\ttest_zerowidth_regex '$'\n\ttest_zerowidth_regex '^'\n\ttest_zerowidth_regex '.*'\n\nThe change of direction for the fix itself looks good to me (re my\nearlier feedback on a previous round), i.e. that we should fix our own\ncode, not forbid '$' in regexes.\n"},{"id":"469322","messageId":"CAPig+cSEtW3TpUkQhNVjM=7WBk-3ZYOCDohsu+AZSpEAPKwk2w@mail.gmail.com","threadId":"58900","inReplyTo":"221219.86edsvxank.gmgdl@evledraar.gmail.com","subject":"Re: [PATCH v4] line-range: fix infinite loop bug with '$' regex","fromName":"Eric Sunshine","fromEmail":"sunshine@sunshineco.com","sentAt":"2022-12-20T00:00:25Z","receivedAt":"2022-12-20T00:00:42Z","isPatch":true,"sender":{"key":"sunshine@sunshineco.com","avatar":"https://avatars.githubusercontent.com/u/163641?v=4"},"body":"On Mon, Dec 19, 2022 at 6:00 PM Ævar Arnfjörð Bjarmason\n<avarab@gmail.com> wrote:\n> On Mon, Dec 19 2022, Lars Kellogg-Stedman wrote:\n> > +test_expect_success 'setup tests for zero-width regular expressions' '\n> > +     cat >expect <<-EOF\n> > +     Modify func1() in file.c\n> > +     Add func1() and func2() in file.c\n> > +     EOF\n> > +'\n> > +\n> > +test_expect_success 'zero-width regex $ matches any function name' '\n> > +     git log --format=\"%s\" --no-patch \"-L:$:file.c\" >actual &&\n> > +     test_cmp expect actual\n> > +'\n>\n> Untested, but as most of this is repeated & would fail if the \"setup\"\n> test is skipped, a one-off function would be better, e.g.:\n>\n>         test_zerowidth_regex () {\n>                 local rx=\"$1\" &&\n>                 [...]\n>         }\n>         test_zerowidth_regex '$'\n>         test_zerowidth_regex '^'\n>         test_zerowidth_regex '.*'\n>\n> The change of direction for the fix itself looks good to me (re my\n> earlier feedback on a previous round), i.e. that we should fix our own\n> code, not forbid '$' in regexes.\n\nIt's subjective, of course, but the patch seems \"good enough\" as-is\nand the tests are easy to understand. Therefore, can you clarify for\nLars and other reviewers if you're merely presenting an alternative\napproach, or if you consider your suggestion \"blocking\" and expect a\nreroll.\n"},{"id":"469337","messageId":"xmqqo7ryzxu8.fsf@gitster.g","threadId":"58900","inReplyTo":"CAPig+cSEtW3TpUkQhNVjM=7WBk-3ZYOCDohsu+AZSpEAPKwk2w@mail.gmail.com","subject":"Re: [PATCH v4] line-range: fix infinite loop bug with '$' regex","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-12-20T01:07:59Z","receivedAt":"2022-12-20T01:08:07Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Eric Sunshine <sunshine@sunshineco.com> writes:\n\n>> The change of direction for the fix itself looks good to me (re my\n>> earlier feedback on a previous round), i.e. that we should fix our own\n>> code, not forbid '$' in regexes.\n>\n> It's subjective, of course, but the patch seems \"good enough\" as-is\n> and the tests are easy to understand. Therefore, can you clarify for\n> Lars and other reviewers if you're merely presenting an alternative\n> approach, or if you consider your suggestion \"blocking\" and expect a\n> reroll.\n\nThanks for saying this.\n\nI personally felt that the original was easier to follow---given\nthat these tests do not have too many moving parts that may need to\nbe changed (in which case abstracting common parts out would allow\nus to maintain only one copy which is a big win), being able to read\nfrom top to bottom without having to read a function and recall what\nthe parameter was etc.\n\n"}]}