diff options
| -rw-r--r-- | Grammar/python.gram | 6 | ||||
| -rw-r--r-- | Lib/test/test_patma.py | 21 | ||||
| -rw-r--r-- | Misc/NEWS.d/next/Core and Builtins/2022-06-10-12-03-17.gh-issue-93671.idkQqG.rst | 2 | ||||
| -rw-r--r-- | Parser/parser.c | 10 |
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 31ad9a0..50fd03c 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; } |