gh-93671: Avoid exponential backtracking in deeply nested sequence patterns in match statements (GH-93680)

Co-authored-by: Łukasz Langa <lukasz@langa.pl>

1 files changed, 10 insertions, 0 deletions

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;
 }