postgres.git / summary / log / commit / refs
commit d4a63f829702cf28adb5db7e2ed44d2d9d893451
Author: Andrew Gierth <rhodiumtoad@postgresql.org>
Date: Thu Aug 23 15:35:33 2018 +0000
First released in: 12.0, 9.3.25, 9.4.20, 9.5.15, 9.6.11, 10.6, 11.0
Reduce an unnecessary O(N^3) loop in lexer.
The lexer's handling of operators contained an O(N^3) hazard when
dealing with long strings of + or - characters; it seems hard to
prevent this case from being O(N^2), but the additional N multiplier
was not needed.
Backpatch all the way since this has been there since 7.x, and it
presents at least a mild hazard in that trying to do Bind, PREPARE or
EXPLAIN on a hostile query could take excessive time (without
honouring cancels or timeouts) even if the query was never executed.
src/backend/parser/scan.l | 27 ++++++++++++++++++++-------
src/fe_utils/psqlscan.l | 27 ++++++++++++++++++++-------
src/interfaces/ecpg/preproc/pgc.l | 29 +++++++++++++++++++++--------
3 files changed, 61 insertions(+), 22 deletions(-)
diff --git a/src/backend/parser/scan.l b/src/backend/parser/scan.l
index 0cd782827ac..96f51bfd596 100644
--- a/src/backend/parser/scan.l
+++ b/src/backend/parser/scan.l
@@ -885,20 +885,33 @@ other .
* to forbid operator names like '?-' that could not be
* sequences of SQL operators.
*/
- while (nchars > 1 &&
- (yytext[nchars - 1] == '+' ||
- yytext[nchars - 1] == '-'))
+ if (nchars > 1 &&
+ (yytext[nchars - 1] == '+' ||
+ yytext[nchars - 1] == '-'))
{
int ic;
for (ic = nchars - 2; ic >= 0; ic--)
{
- if (strchr("~!@#^&|`?%", yytext[ic]))
+ char c = yytext[ic];
+ if (c == '~' || c == '!' || c == '@' ||
+ c == '#' || c == '^' || c == '&' ||
+ c == '|' || c == '`' || c == '?' ||
+ c == '%')
break;
}
- if (ic >= 0)
- break; /* found a char that makes it OK */
- nchars--; /* else remove the +/-, and check again */
+ if (ic < 0)
+ {
+ /*
+ * didn't find a qualifying character, so remove
+ * all trailing [+-]
+ */
+ do {
+ nchars--;
+ } while (nchars > 1 &&
+ (yytext[nchars - 1] == '+' ||
+ yytext[nchars - 1] == '-'));
+ }
}
SET_YYLLOC();
diff --git a/src/fe_utils/psqlscan.l b/src/fe_utils/psqlscan.l
index 1cc587be34c..989284dc6fe 100644
--- a/src/fe_utils/psqlscan.l
+++ b/src/fe_utils/psqlscan.l
@@ -817,20 +817,33 @@ other .
* to forbid operator names like '?-' that could not be
* sequences of SQL operators.
*/
- while (nchars > 1 &&
- (yytext[nchars - 1] == '+' ||
- yytext[nchars - 1] == '-'))
+ if (nchars > 1 &&
+ (yytext[nchars - 1] == '+' ||
+ yytext[nchars - 1] == '-'))
{
int ic;
for (ic = nchars - 2; ic >= 0; ic--)
{
- if (strchr("~!@#^&|`?%", yytext[ic]))
+ char c = yytext[ic];
+ if (c == '~' || c == '!' || c == '@' ||
+ c == '#' || c == '^' || c == '&' ||
+ c == '|' || c == '`' || c == '?' ||
+ c == '%')
break;
}
- if (ic >= 0)
- break; /* found a char that makes it OK */
- nchars--; /* else remove the +/-, and check again */
+ if (ic < 0)
+ {
+ /*
+ * didn't find a qualifying character, so remove
+ * all trailing [+-]
+ */
+ do {
+ nchars--;
+ } while (nchars > 1 &&
+ (yytext[nchars - 1] == '+' ||
+ yytext[nchars - 1] == '-'));
+ }
}
if (nchars < yyleng)
diff --git a/src/interfaces/ecpg/preproc/pgc.l b/src/interfaces/ecpg/preproc/pgc.l
index 405dee73b03..9ad50b99119 100644
--- a/src/interfaces/ecpg/preproc/pgc.l
+++ b/src/interfaces/ecpg/preproc/pgc.l
@@ -690,20 +690,33 @@ cppline {space}*#([^i][A-Za-z]*|{if}|{ifdef}|{ifndef}|{import})((\/\*[^*/]*\*+
* to forbid operator names like '?-' that could not be
* sequences of SQL operators.
*/
- while (nchars > 1 &&
- (yytext[nchars-1] == '+' ||
- yytext[nchars-1] == '-'))
+ if (nchars > 1 &&
+ (yytext[nchars - 1] == '+' ||
+ yytext[nchars - 1] == '-'))
{
int ic;
- for (ic = nchars-2; ic >= 0; ic--)
+ for (ic = nchars - 2; ic >= 0; ic--)
{
- if (strchr("~!@#^&|`?%", yytext[ic]))
+ char c = yytext[ic];
+ if (c == '~' || c == '!' || c == '@' ||
+ c == '#' || c == '^' || c == '&' ||
+ c == '|' || c == '`' || c == '?' ||
+ c == '%')
break;
}
- if (ic >= 0)
- break; /* found a char that makes it OK */
- nchars--; /* else remove the +/-, and check again */
+ if (ic < 0)
+ {
+ /*
+ * didn't find a qualifying character, so remove
+ * all trailing [+-]
+ */
+ do {
+ nchars--;
+ } while (nchars > 1 &&
+ (yytext[nchars - 1] == '+' ||
+ yytext[nchars - 1] == '-'));
+ }
}
if (nchars < yyleng)
[parent: 5ca00774194d]