summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorMiss Islington (bot) <31488909+miss-islington@users.noreply.github.com>2022-06-10 16:21:04 (GMT)
committerGitHub <noreply@github.com>2022-06-10 16:21:04 (GMT)
commitf9d0240db809fbb4443dc8f96a18e4c49af3fb7f (patch)
treed9f7ebf49a52c76e9e5796d470b51a2dede73244
parent98558a83976b0279b1404fcb67bc72e7fcf3fe8a (diff)
downloadcpython-f9d0240db809fbb4443dc8f96a18e4c49af3fb7f.zip
cpython-f9d0240db809fbb4443dc8f96a18e4c49af3fb7f.tar.gz
cpython-f9d0240db809fbb4443dc8f96a18e4c49af3fb7f.tar.bz2
gh-93671: Avoid exponential backtracking in deeply nested sequence patterns in match statements (GH-93680)
Co-authored-by: Ɓukasz Langa <lukasz@langa.pl> (cherry picked from commit 53a8b17895e91d08f76a2fb59a555d012cd85ab4) Co-authored-by: Pablo Galindo Salgado <Pablogsal@gmail.com>
-rw-r--r--Grammar/python.gram6
-rw-r--r--Lib/test/test_patma.py21
-rw-r--r--Misc/NEWS.d/next/Core and Builtins/2022-06-10-12-03-17.gh-issue-93671.idkQqG.rst2
-rw-r--r--Parser/parser.c10
4 files changed, 36 insertions, 3 deletions
diff --git a/Grammar/python.gram b/Grammar/python.gram
index 15c40b6..67b7a55 100644
--- a/Grammar/python.gram
+++ b/Grammar/python.gram
@@ -471,7 +471,7 @@ or_pattern[pattern_ty]:
| patterns[asdl_pattern_seq*]='|'.closed_pattern+ {
asdl_seq_LEN(patterns) == 1 ? asdl_seq_GET(patterns, 0) : _PyAST_MatchOr(patterns, EXTRA) }
-closed_pattern[pattern_ty]:
+closed_pattern[pattern_ty] (memo):
| literal_pattern
| capture_pattern
| wildcard_pattern
@@ -558,7 +558,7 @@ maybe_star_pattern[pattern_ty]:
| star_pattern
| pattern
-star_pattern[pattern_ty]:
+star_pattern[pattern_ty] (memo):
| '*' target=pattern_capture_target {
_PyAST_MatchStar(target->v.Name.id, EXTRA) }
| '*' wildcard_pattern {
@@ -1312,4 +1312,4 @@ invalid_kvpair:
| a=expression !(':') {
RAISE_ERROR_KNOWN_LOCATION(p, PyExc_SyntaxError, a->lineno, a->end_col_offset - 1, a->end_lineno, -1, "':' expected after dictionary key") }
| expression ':' a='*' bitwise_or { RAISE_SYNTAX_ERROR_STARTING_FROM(a, "cannot use a starred expression in a dictionary value") }
- | expression a=':' {RAISE_SYNTAX_ERROR_KNOWN_LOCATION(a, "expression expected after dictionary key and ':'") } \ No newline at end of file
+ | expression a=':' {RAISE_SYNTAX_ERROR_KNOWN_LOCATION(a, "expression expected after dictionary key and ':'") }
diff --git a/Lib/test/test_patma.py b/Lib/test/test_patma.py
index 57d3b1e..db198f7 100644
--- a/Lib/test/test_patma.py
+++ b/Lib/test/test_patma.py
@@ -3151,6 +3151,27 @@ class TestTracing(unittest.TestCase):
self.assertListEqual(self._trace(f, "go x"), [1, 2, 3])
self.assertListEqual(self._trace(f, "spam"), [1, 2, 3])
+ def test_parser_deeply_nested_patterns(self):
+ # Deeply nested patterns can cause exponential backtracking when parsing.
+ # See gh-93671 for more information.
+
+ levels = 100
+
+ patterns = [
+ "A" + "(" * levels + ")" * levels,
+ "{1:" * levels + "1" + "}" * levels,
+ "[" * levels + "1" + "]" * levels,
+ ]
+
+ for pattern in patterns:
+ with self.subTest(pattern):
+ code = inspect.cleandoc("""
+ match None:
+ case {}:
+ pass
+ """.format(pattern))
+ compile(code, "<string>", "exec")
+
if __name__ == "__main__":
"""
diff --git a/Misc/NEWS.d/next/Core and Builtins/2022-06-10-12-03-17.gh-issue-93671.idkQqG.rst b/Misc/NEWS.d/next/Core and Builtins/2022-06-10-12-03-17.gh-issue-93671.idkQqG.rst
new file mode 100644
index 0000000..a775715
--- /dev/null
+++ b/Misc/NEWS.d/next/Core and Builtins/2022-06-10-12-03-17.gh-issue-93671.idkQqG.rst
@@ -0,0 +1,2 @@
+Fix some exponential backtrace case happening with deeply nested sequence
+patterns in match statements. Patch by Pablo Galindo
diff --git a/Parser/parser.c b/Parser/parser.c
index 08bf6d2..8758e9c 100644
--- a/Parser/parser.c
+++ b/Parser/parser.c
@@ -7945,6 +7945,10 @@ closed_pattern_rule(Parser *p)
return NULL;
}
pattern_ty _res = NULL;
+ if (_PyPegen_is_memoized(p, closed_pattern_type, &_res)) {
+ p->level--;
+ return _res;
+ }
int _mark = p->mark;
{ // literal_pattern
if (p->error_indicator) {
@@ -8100,6 +8104,7 @@ closed_pattern_rule(Parser *p)
}
_res = NULL;
done:
+ _PyPegen_insert_memo(p, _mark, closed_pattern_type, _res);
p->level--;
return _res;
}
@@ -9623,6 +9628,10 @@ star_pattern_rule(Parser *p)
return NULL;
}
pattern_ty _res = NULL;
+ if (_PyPegen_is_memoized(p, star_pattern_type, &_res)) {
+ p->level--;
+ return _res;
+ }
int _mark = p->mark;
if (p->mark == p->fill && _PyPegen_fill_token(p) < 0) {
p->error_indicator = 1;
@@ -9707,6 +9716,7 @@ star_pattern_rule(Parser *p)
}
_res = NULL;
done:
+ _PyPegen_insert_memo(p, _mark, star_pattern_type, _res);
p->level--;
return _res;
}