RustPython · youknowone · Mar 22, 2024 · Oct 1, 2020 · Dec 1, 2020 · Dec 23, 2020
diff --git a/Cargo.lock b/Cargo.lock
diff --git a/Cargo.toml b/Cargo.toml
@@ -13,7 +13,7 @@ include = ["LICENSE", "Cargo.toml", "src/**/*.rs"]
 resolver = "2"
 members = [
     "compiler", "compiler/core", "compiler/codegen",
-    ".", "common", "derive", "jit", "vm", "pylib", "stdlib", "wasm/lib", "derive-impl",
+    ".", "common", "derive", "jit", "vm", "vm/sre_engine", "pylib", "stdlib", "wasm/lib", "derive-impl",
 ]
 
 [workspace.dependencies]
@@ -27,6 +27,7 @@ rustpython-jit = { path = "jit", version = "0.3.0" }
 rustpython-vm = { path = "vm", default-features = false, version = "0.3.0" }
 rustpython-pylib = { path = "pylib", version = "0.3.0" }
 rustpython-stdlib = { path = "stdlib", default-features = false, version = "0.3.0" }
+rustpython-sre_engine = { path = "vm/sre_engine", version = "0.6.0" }
 rustpython-doc = { git = "https://github.com/RustPython/__doc__", tag = "0.3.0", version = "0.3.0" }
 
 rustpython-literal = { git = "https://github.com/RustPython/Parser.git", rev = "29c4728dbedc7e69cc2560b9b34058bbba9b1303" }
@@ -64,7 +65,7 @@ malachite-base = "0.4.4"
 num-complex = "0.4.0"
 num-integer = "0.1.44"
 num-traits = "0.2"
-num_enum = "0.5.7"
+num_enum = "0.7"
 once_cell = "1.18"
 parking_lot = "0.12.1"
 paste = "1.0.7"

diff --git a/vm/sre_engine/.gitignore b/vm/sre_engine/.gitignore
@@ -0,0 +1,2 @@
+/target
+Cargo.lock
diff --git a/vm/sre_engine/.vscode/launch.json b/vm/sre_engine/.vscode/launch.json
@@ -0,0 +1,21 @@
+{
+    "version": "0.2.0",
+    "configurations": [
+        {
+            "type": "lldb",
+            "request": "launch",
+            "name": "Debug Unit Test",
+            "cargo": {
+                "args": [
+                    "test",
+                    "--no-run"
+                ],
+                "filter": {
+                    "kind": "test"
+                }
+            },
+            "args": [],
+            "cwd": "${workspaceFolder}"
+        }
+    ]
+}
diff --git a/vm/sre_engine/Cargo.toml b/vm/sre_engine/Cargo.toml
@@ -0,0 +1,15 @@
+[package]
+name = "rustpython-sre_engine"
+version = "0.6.0"
+authors = ["Kangzhi Shi <shikangzhi@gmail.com>", "RustPython Team"]
+description = "A low-level implementation of Python's SRE regex engine"
+repository = "https://github.com/RustPython/RustPython"
+license = "MIT"
+edition = "2021"
+keywords = ["regex"]
+include = ["LICENSE", "src/**/*.rs"]
+
+[dependencies]
+num_enum = { workspace = true }
+bitflags = { workspace = true }
+optional = "0.5"
diff --git a/vm/sre_engine/LICENSE b/vm/sre_engine/LICENSE
@@ -0,0 +1,21 @@
+MIT License
+
+Copyright (c) 2020 RustPython Team
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in all
+copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+SOFTWARE.
diff --git a/vm/sre_engine/benches/benches.rs b/vm/sre_engine/benches/benches.rs
@@ -0,0 +1,111 @@
+#![feature(test)]
+
+extern crate test;
+use test::Bencher;
+
+use sre_engine::{Request, State, StrDrive};
+
+struct Pattern {
+    code: &'static [u32],
+}
+
+impl Pattern {
+    fn state<'a, S: StrDrive>(&self, string: S) -> (Request<'a, S>, State) {
+        self.state_range(string, 0..usize::MAX)
+    }
+
+    fn state_range<'a, S: StrDrive>(
+        &self,
+        string: S,
+        range: std::ops::Range<usize>,
+    ) -> (Request<'a, S>, State) {
+        let req = Request::new(string, range.start, range.end, self.code, false);
+        let state = State::default();
+        (req, state)
+    }
+}
+
+#[bench]
+fn benchmarks(b: &mut Bencher) {
+    // # test common prefix
+    // pattern p1 = re.compile('Python|Perl') # , 'Perl'),    # Alternation
+    // START GENERATED by generate_tests.py
+    #[rustfmt::skip] let p1 = Pattern { code: &[14, 8, 1, 4, 6, 1, 1, 80, 0, 16, 80, 7, 13, 16, 121, 16, 116, 16, 104, 16, 111, 16, 110, 15, 11, 9, 16, 101, 16, 114, 16, 108, 15, 2, 0, 1] };
+    // END GENERATED
+    // pattern p2 = re.compile('(Python|Perl)') #, 'Perl'),  # Grouped alternation
+    // START GENERATED by generate_tests.py
+    #[rustfmt::skip] let p2 = Pattern { code: &[14, 8, 1, 4, 6, 1, 0, 80, 0, 17, 0, 16, 80, 7, 13, 16, 121, 16, 116, 16, 104, 16, 111, 16, 110, 15, 11, 9, 16, 101, 16, 114, 16, 108, 15, 2, 0, 17, 1, 1] };
+    // END GENERATED
+    // pattern p3 = re.compile('Python|Perl|Tcl') #, 'Perl'),        # Alternation
+    // START GENERATED by generate_tests.py
+    #[rustfmt::skip] let p3 = Pattern { code: &[14, 9, 4, 3, 6, 16, 80, 16, 84, 0, 7, 15, 16, 80, 16, 121, 16, 116, 16, 104, 16, 111, 16, 110, 15, 22, 11, 16, 80, 16, 101, 16, 114, 16, 108, 15, 11, 9, 16, 84, 16, 99, 16, 108, 15, 2, 0, 1] };
+    // END GENERATED
+    // pattern p4 = re.compile('(Python|Perl|Tcl)') #, 'Perl'),      # Grouped alternation
+    // START GENERATED by generate_tests.py
+    #[rustfmt::skip] let p4 = Pattern { code: &[14, 9, 4, 3, 6, 16, 80, 16, 84, 0, 17, 0, 7, 15, 16, 80, 16, 121, 16, 116, 16, 104, 16, 111, 16, 110, 15, 22, 11, 16, 80, 16, 101, 16, 114, 16, 108, 15, 11, 9, 16, 84, 16, 99, 16, 108, 15, 2, 0, 17, 1, 1] };
+    // END GENERATED
+    // pattern p5 = re.compile('(Python)\\1') #, 'PythonPython'),    # Backreference
+    // START GENERATED by generate_tests.py
+    #[rustfmt::skip] let p5 = Pattern { code: &[14, 18, 1, 12, 12, 6, 0, 80, 121, 116, 104, 111, 110, 0, 0, 0, 0, 0, 0, 17, 0, 16, 80, 16, 121, 16, 116, 16, 104, 16, 111, 16, 110, 17, 1, 11, 0, 1] };
+    // END GENERATED
+    // pattern p6 = re.compile('([0a-z][a-z0-9]*,)+') #, 'a5,b7,c9,'), # Disable the fastmap optimization
+    // START GENERATED by generate_tests.py
+    #[rustfmt::skip] let p6 = Pattern { code: &[14, 4, 0, 2, 4294967295, 23, 31, 1, 4294967295, 17, 0, 13, 7, 16, 48, 22, 97, 122, 0, 24, 13, 0, 4294967295, 13, 8, 22, 97, 122, 22, 48, 57, 0, 1, 16, 44, 17, 1, 18, 1] };
+    // END GENERATED
+    // pattern p7 = re.compile('([a-z][a-z0-9]*,)+') #, 'a5,b7,c9,'), # A few sets
+    // START GENERATED by generate_tests.py
+    #[rustfmt::skip] let p7 = Pattern { code: &[14, 4, 0, 2, 4294967295, 23, 29, 1, 4294967295, 17, 0, 13, 5, 22, 97, 122, 0, 24, 13, 0, 4294967295, 13, 8, 22, 97, 122, 22, 48, 57, 0, 1, 16, 44, 17, 1, 18, 1] };
+    // END GENERATED
+    // pattern p8 = re.compile('Python') #, 'Python'),               # Simple text literal
+    // START GENERATED by generate_tests.py
+    #[rustfmt::skip] let p8 = Pattern { code: &[14, 18, 3, 6, 6, 6, 6, 80, 121, 116, 104, 111, 110, 0, 0, 0, 0, 0, 0, 16, 80, 16, 121, 16, 116, 16, 104, 16, 111, 16, 110, 1] };
+    // END GENERATED
+    // pattern p9 = re.compile('.*Python') #, 'Python'),             # Bad text literal
+    // START GENERATED by generate_tests.py
+    #[rustfmt::skip] let p9 = Pattern { code: &[14, 4, 0, 6, 4294967295, 24, 5, 0, 4294967295, 2, 1, 16, 80, 16, 121, 16, 116, 16, 104, 16, 111, 16, 110, 1] };
+    // END GENERATED
+    // pattern p10 = re.compile('.*Python.*') #, 'Python'),           # Worse text literal
+    // START GENERATED by generate_tests.py
+    #[rustfmt::skip] let p10 = Pattern { code: &[14, 4, 0, 6, 4294967295, 24, 5, 0, 4294967295, 2, 1, 16, 80, 16, 121, 16, 116, 16, 104, 16, 111, 16, 110, 24, 5, 0, 4294967295, 2, 1, 1] };
+    // END GENERATED
+    // pattern p11 = re.compile('.*(Python)') #, 'Python'),           # Bad text literal with grouping
+    // START GENERATED by generate_tests.py
+    #[rustfmt::skip] let p11 = Pattern { code: &[14, 4, 0, 6, 4294967295, 24, 5, 0, 4294967295, 2, 1, 17, 0, 16, 80, 16, 121, 16, 116, 16, 104, 16, 111, 16, 110, 17, 1, 1] };
+    // END GENERATED
+
+    let tests = [
+        (p1, "Perl"),
+        (p2, "Perl"),
+        (p3, "Perl"),
+        (p4, "Perl"),
+        (p5, "PythonPython"),
+        (p6, "a5,b7,c9,"),
+        (p7, "a5,b7,c9,"),
+        (p8, "Python"),
+        (p9, "Python"),
+        (p10, "Python"),
+        (p11, "Python"),
+    ];
+
+    b.iter(move || {
+        for (p, s) in &tests {
+            let (req, mut state) = p.state(s.clone());
+            assert!(state.search(req));
+            let (req, mut state) = p.state(s.clone());
+            assert!(state.pymatch(&req));
+            let (mut req, mut state) = p.state(s.clone());
+            req.match_all = true;
+            assert!(state.pymatch(&req));
+            let s2 = format!("{}{}{}", " ".repeat(10000), s, " ".repeat(10000));
+            let (req, mut state) = p.state_range(s2.as_str(), 0..usize::MAX);
+            assert!(state.search(req));
+            let (req, mut state) = p.state_range(s2.as_str(), 10000..usize::MAX);
+            assert!(state.pymatch(&req));
+            let (req, mut state) = p.state_range(s2.as_str(), 10000..10000 + s.len());
+            assert!(state.pymatch(&req));
+            let (mut req, mut state) = p.state_range(s2.as_str(), 10000..10000 + s.len());
+            req.match_all = true;
+            assert!(state.pymatch(&req));
+        }
+    })
+}
diff --git a/vm/sre_engine/generate_tests.py b/vm/sre_engine/generate_tests.py
@@ -0,0 +1,47 @@
+import os
+from pathlib import Path
+import re
+import sre_constants
+import sre_compile
+import sre_parse
+import json
+from itertools import chain
+
+m = re.search(r"const SRE_MAGIC: usize = (\d+);", open("src/constants.rs").read())
+sre_engine_magic = int(m.group(1))
+del m
+
+assert sre_constants.MAGIC == sre_engine_magic
+
+class CompiledPattern:
+    @classmethod
+    def compile(cls, pattern, flags=0):
+        p = sre_parse.parse(pattern)
+        code = sre_compile._code(p, flags)
+        self = cls()
+        self.pattern = pattern
+        self.code = code
+        self.flags = re.RegexFlag(flags | p.state.flags)
+        return self
+
+for k, v in re.RegexFlag.__members__.items():
+    setattr(CompiledPattern, k, v)
+
+
+# matches `// pattern {varname} = re.compile(...)`
+pattern_pattern = re.compile(r"^((\s*)\/\/\s*pattern\s+(\w+)\s+=\s+(.+?))$(?:.+?END GENERATED)?", re.M | re.S)
+def replace_compiled(m):
+    line, indent, varname, pattern = m.groups()
+    pattern = eval(pattern, {"re": CompiledPattern})
+    pattern = f"Pattern {{ code: &{json.dumps(pattern.code)} }}"
+    return f'''{line}
+{indent}// START GENERATED by generate_tests.py
+{indent}#[rustfmt::skip] let {varname} = {pattern};
+{indent}// END GENERATED'''
+
+with os.scandir("tests") as t, os.scandir("benches") as b:
+    for f in chain(t, b):
+        path = Path(f.path)
+        if path.suffix == ".rs":
+            replaced = pattern_pattern.sub(replace_compiled, path.read_text())
+            path.write_text(replaced)