[CFP] Implement the _sre module in Rust

[coolreader18]

At the moment, _sre is a modified version of _sre.py from an old version of PyPy: https://github.com/nikhaldi/_sre.py.

This is s l o w. If you ctrl-C rustpython while it's running a decently complex script, there's a good chance that the traceback from the KeyboardInterrupt will have originated somewhere in _sre.py. While it's definitely possible to implement _sre in Rust -- I was able to modify the constant-generation script to output Rust instead of C code -- both the C and Python versions of _sre don't really lend well to simple/direct translation to Rust. The C version (_sre.c/sre_lib.h) uses lots of pointer arithmetic and a kind of "as long as we own an active reference to the str object, we can send pointers anywhere we want" approach that doesn't jive well with Rust's memory-safety rules. The Python version (Lib/_sre.py in the RustPython source tree) uses enough nested references (context.x_stack[n].context is context), generator functions, and dynamic typing that it's also tricky to translate to Rust.

If anyone wants to take a stab at this, I've left a scaffold of the implementation in the _sre-wip branch, that has the SRE constants available to Rust, and some of my sketches for how it might work, but no real functionality. Be warned, either route you go to emulate is tricky, so feel free to try whichever approach you think would be easier.

[darleybarreto]

pyre2 and Jython's _sre [1,2] might help on this.

[qingshi163]

Should we implement it by follow CPython that compile to bytecode? I did not look deep into the code yet, but can we do like compile to Vec? Anything that may tricky?

[darleybarreto]

I think that doing something like pyre2 would be better, but using regex in the backend instead of re2.

[coolreader18]

@darleybarreto Unfortunately, we can't use the regex crate, as it doesn't support lookbehinds and all the other fancy features that sre has.

@qingshi163, I'm not sure exactly what you're asking, but Python code in the sre_compile module compiles the regex to bytecode, the _sre module "just" has to interpret it. I think the scaffold already collects the bytecode into a Vec<u32>

[darleybarreto]

@darleybarreto Unfortunately, we can't use the regex crate, as it doesn't support lookbehinds and all the other fancy features that sre has.

Hmm, do you know all the fancy features that it has (and we can't use regex)? Depending on what those are, we could simply "avoid" them for as long as we can.

[darleybarreto]

Or perhaps fancy-regex.