bpo-42885: Optimize search for regular expressions starting with "\A" or "^"

serhiy-storchaka · serhiy-storchaka · commit 5f66afe8717b · 2022-03-21T08:44:23.000+02:00
Affected functions are re.search(), re.split(), re.findall(), re.finditer()
and re.sub().
diff --git a/Lib/test/test_re.py b/Lib/test/test_re.py
@@ -2072,6 +2072,15 @@ def test_bug_40736(self):
         with self.assertRaisesRegex(TypeError, "got 'type'"):
             re.search("x*", type)
 
+    def test_search_anchor_at_beginning(self):
+        s = 'x'*10**7
+        for p in r'\Ax*y', r'^x*y':
+            self.assertIsNone(re.search(p, s))
+            self.assertEqual(re.split(p, s), [s])
+            self.assertEqual(re.findall(p, s), [])
+            self.assertEqual(list(re.finditer(p, s)), [])
+            self.assertEqual(re.sub(p, '', s), s)
+
 
 class PatternReprTests(unittest.TestCase):
     def check(self, pattern, expected):
diff --git a/Misc/NEWS.d/next/Library/2022-03-21-08-32-19.bpo-42885.LCnTTp.rst b/Misc/NEWS.d/next/Library/2022-03-21-08-32-19.bpo-42885.LCnTTp.rst
@@ -0,0 +1,3 @@
+Optimize :func:`re.search`, :func:`re.split`, :func:`re.findall`,
+:func:`re.finditer` and :func:`re.sub` for regular expressions starting with
+``\A`` or ``^``.
diff --git a/Modules/sre_lib.h b/Modules/sre_lib.h
@@ -1495,6 +1495,13 @@ SRE(search)(SRE_STATE* state, SRE_CODE* pattern)
         state->start = state->ptr = ptr;
         status = SRE(match)(state, pattern, 1);
         state->must_advance = 0;
+        if (status == 0 && pattern[0] == SRE_OP_AT &&
+            (pattern[1] == SRE_AT_BEGINNING ||
+             pattern[1] == SRE_AT_BEGINNING_STRING))
+        {
+            state->start = state->ptr = ptr = end;
+            return 0;
+        }
         while (status == 0 && ptr < end) {
             ptr++;
             RESET_CAPTURE_GROUP();

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,3 @@`
	`1`	+Optimize :func:`re.search`, :func:`re.split`, :func:`re.findall`,
	`2`	+:func:`re.finditer` and :func:`re.sub` for regular expressions starting with
	`3`	+``\A`` or ``^``.