[3.10] gh-93671: Avoid exponential backtracking in deeply nested sequence patterns in match statements (GH-93680) (#93690)

Co-authored-by: Łukasz Langa <lukasz@langa.pl>.
(cherry picked from commit 53a8b17895e91d08f76a2fb59a555d012cd85ab4)

Co-authored-by: Pablo Galindo Salgado <Pablogsal@gmail.com>

1 files changed, 21 insertions, 0 deletions

diff --git a/Lib/test/test_patma.py b/Lib/test/test_patma.py
index aa18e29e22..b8444822c8 100644
--- a/Lib/test/test_patma.py
+++ b/Lib/test/test_patma.py
@@ -3138,6 +3138,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__":
     """