Commitf9d0240

and

authored

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 commit53a8b17)Co-authored-by: Pablo Galindo Salgado <Pablogsal@gmail.com>

1 parent98558a8 commitf9d0240Copy full SHA for f9d0240

File tree

+36

-3

lines changed

+36

-3

lines changed

Lines changed: 3 additions & 3 deletions

Original file line number	Diff line number	Diff line change
`@@ -471,7 +471,7 @@ or_pattern[pattern_ty]:`
`471`	`471`	`\| patterns[asdl_pattern_seq*]='\|'.closed_pattern+ {`
`472`	`472`	`asdl_seq_LEN(patterns) == 1 ? asdl_seq_GET(patterns, 0) : _PyAST_MatchOr(patterns, EXTRA) }`
`473`	`473`
`474`		`-closed_pattern[pattern_ty]:`
	`474`	`+closed_pattern[pattern_ty] (memo):`
`475`	`475`	`\| literal_pattern`
`476`	`476`	`\| capture_pattern`
`477`	`477`	`\| wildcard_pattern`
`@@ -558,7 +558,7 @@ maybe_star_pattern[pattern_ty]:`
`558`	`558`	`\| star_pattern`
`559`	`559`	`\| pattern`
`560`	`560`
`561`		`-star_pattern[pattern_ty]:`
	`561`	`+star_pattern[pattern_ty] (memo):`
`562`	`562`	`\| '*' target=pattern_capture_target {`
`563`	`563`	`_PyAST_MatchStar(target->v.Name.id, EXTRA) }`
`564`	`564`	`\| '*' wildcard_pattern {`
`@@ -1312,4 +1312,4 @@ invalid_kvpair:`
`1312`	`1312`	`\| a=expression !(':') {`
`1313`	`1313`	`RAISE_ERROR_KNOWN_LOCATION(p, PyExc_SyntaxError, a->lineno, a->end_col_offset - 1, a->end_lineno, -1, "':' expected after dictionary key") }`
`1314`	`1314`	`\| expression ':' a='*' bitwise_or { RAISE_SYNTAX_ERROR_STARTING_FROM(a, "cannot use a starred expression in a dictionary value") }`
`1315`		`- \| expression a=':' {RAISE_SYNTAX_ERROR_KNOWN_LOCATION(a, "expression expected after dictionary key and ':'") }`
	`1315`	`+ \| expression a=':' {RAISE_SYNTAX_ERROR_KNOWN_LOCATION(a, "expression expected after dictionary key and ':'") }`

Lines changed: 21 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -3151,6 +3151,27 @@ def f(command): # 0`
`3151`	`3151`	`self.assertListEqual(self._trace(f,"go x"), [1,2,3])`
`3152`	`3152`	`self.assertListEqual(self._trace(f,"spam"), [1,2,3])`
`3153`	`3153`
	`3154`	`+deftest_parser_deeply_nested_patterns(self):`
	`3155`	`+# Deeply nested patterns can cause exponential backtracking when parsing.`
	`3156`	`+# See gh-93671 for more information.`
	`3157`	`+`
	`3158`	`+levels=100`
	`3159`	`+`
	`3160`	`+patterns= [`
	`3161`	`+"A"+"("levels+")"levels,`
	`3162`	`+"{1:"levels+"1"+"}"levels,`
	`3163`	`+"["levels+"1"+"]"levels,`
	`3164`	`+ ]`
	`3165`	`+`
	`3166`	`+forpatterninpatterns:`
	`3167`	`+withself.subTest(pattern):`
	`3168`	`+code=inspect.cleandoc("""`
	`3169`	`+ match None:`
	`3170`	`+ case {}:`
	`3171`	`+ pass`
	`3172`	`+ """.format(pattern))`
	`3173`	`+compile(code,"<string>","exec")`
	`3174`	`+`
`3154`	`3175`
`3155`	`3176`	`if__name__=="__main__":`
`3156`	`3177`	`"""`

Lines changed: 2 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,2 @@`
	`1`	`+Fix some exponential backtrace case happening with deeply nested sequence`
	`2`	`+patterns in match statements. Patch by Pablo Galindo`

Lines changed: 10 additions & 0 deletions

Some generated files are not rendered by default. Learn more aboutcustomizing how changed files appear on GitHub.

Comments

(0)