Repository navigation
regex library to implement "re" module #13
Description
CPython uses (possibly patched) PCRE library http://www.pcre.org/ (BSD license). Nothing would preclude its usage in MicroPython, but:
- Worst-case performance is awful.
- Nobody would ever say PCRE is optimized for code size/memory usage.
So, PCRE would definitely fit "unix" port, to be completely compatible with CPython "re" module. But I'm not sure how usable it will be for MCU ports.
So, what I imagine is be able to support 2 (or more?) regex libraries - one PCRE for complete compatibility, another using other library(ies) for unbloatness, at the expense of reduced feature set. Note that "reduced" subset can live in a separate module (say, "remini").
This ticket would be a good place to discuss that and collect candidates for alternative re lib.
Activity
pfalcon commentedon Dec 30, 2013
See dpgeorge#9 (comment) for some previous discussion.
dpgeorge commentedon Dec 30, 2013
I like regex, and it's useful, so I think it's definitely worth trying to get it on the MCU. If we go for a cutdown version, then it should be a strict subset of Python's regex, not a variation.
hagenkaye commentedon Dec 31, 2013
as an FYI, the musl c library contains the tre regex code.
https://github.com/laurikari/tre
As well, it contains some bug fixes that were never fixed in the original code. (according to the wiki at musl)
Neon22 commentedon Dec 31, 2013
Note that tre does not appear to have the following (which Python re does):
Its not a terrible set of limitiations - providing the other aspects match the same of course.
chipaca commentedon Jan 2, 2014
Note Python does not use PCRE. The default "re" has not been PCRE-based since at least 2.2, and the PCRE implementation of "re" was only included for (AFAIK undocumented) backwards compatibility until 2.3.
pfalcon commentedon Apr 8, 2014
FYI, I started writing FFI bindings for libpcre in https://github.com/micropython/micropython-lib/tree/master/re-pcre , with the idea to have more or less complete re module implementation for unix port.
chipaca commentedon Apr 8, 2014
Not sure how useful it'll be, but you can look at
http://svn.python.org/projects/python/branches/release22-maint/Lib/pre.pyand
the pcre* files in
http://svn.python.org/projects/python/branches/release22-maint/Modules/ for
inspiration.
On Tue, Apr 8, 2014 at 11:20 PM, Paul Sokolovsky
[email protected]:
John Lenton ([email protected]) ::: http://chipaca.com
pfalcon commentedon Apr 12, 2014
re-pcre now has enough gear to run json module from CPy.
dpgeorge commentedon Apr 12, 2014
You mean, json module copied from CPy can run under uPy, by utilising re-pcre, right?
pfalcon commentedon Apr 12, 2014
Yep, the only change required was this: micropython/micropython-lib@a4833ed (CPy stdlib is full of such dirtiness). Ah, disclaimer: can run on trivial input ;-)
pfalcon commentedon Jun 24, 2014
Ok, I had another pass on this. Let's remind ourselves that regex matching can be implemented either as "recursive-descent" executor with backtracking (essentially, a Turing machine), or NFA/DFA (non-deterministic and deterministic finite automaton). The latter offers some performance guarantees, but harder to understand (and thus modify to add more features), and usually needs some bunch of memory to represent compiled regex, the former is easier to understand/modify and add non-regular features (with modern regex'es full of them).
Technically good contender for "backtracking" category: SLRE . Compiles to under 5K (x86, -Os). Problem spot: has "active" "license life" with several incarnations:
@dpgeorge, do you envision any probs adding MIT version to codebase? (This is certainly better than situation we had with "stm" port, which contained potentially proprietary code.)
pfalcon commentedon Jun 24, 2014
Example of FA-based contender: http://swtch.com/plan9port/unix/ . Messy code from outer space. Support captures, which was big progress for FA impl as http://swtch.com/~rsc/regexp/regexp1.html says. Doesn't support non-greedy quantifers. Compiles to ~7K.
There're bunch of hacks which seem to add non-greedy's and stay unbloated (unlike TLE):
pfalcon commentedon Jun 24, 2014
Generally, grepping for "regex" for github can lead to few interesting, if practical, finds, e.g. https://github.com/fy0/tinyre "A tiny python style regex engine implement.", with nice Chinese readme and comments.
dpgeorge commentedon Jul 4, 2014
No. There is no problem if it's MIT and we acknowledge the source of the code. Now with the extmod/ directory, we can land it there.
(Of course, I would love to write my own re engine, but that's not a good use of time :)
fy0/tinyre looks quite nice, and the license might even be MIT compatible.
pfalcon commentedon Jul 28, 2014
FYI, I kinda coded a module for slre, but then next step is refactoring slre to have sane interface (re-refactoring, because it's used to have it such, but latest explicitly MIT-licensed version has screwed it up), optimize memory usage (it just allocates big statically-sized buffer for compiled regexp), etc, etc.
All that seemed kinda boring, so I made another pass over solutions mentioned above. I looked at tinyre, and it actually compiles to small enough code too, but all the Chinese comments doesn't help, and I saw funny programming practices like infinite loop in case of error. So, previous assessment holds: nobody known what exactly is done there and why.
Then I took a more detailed look at https://code.google.com/p/re1/ (I almost skipped it last time). And that's true gem - first of all, it's truly minimal code (but implements all important features like greedy vs non-greedy quantifiers and submatch captures), and then, it separates regexp compiler from execution backends, and then provides few alternative backends (essentially, tiny VMs). Backends size from 400 bytes on. Frontend is implemented using yacc though, so is big, but I already reimplemented parser in adhoc way.
There's issue that backtracking (== requiring least explicit runtime state for execution, but potentially lot of stack space) backends don't have protection against known backtracking killers like
(a*)*. I even tried to implement that protection, until I checked how slre deals with it, and it infinite-loops too. So, I guess with our aims, it should be good enough to have just switchable backends to deal with it.3 remaining items
pfalcon commentedon Aug 16, 2014
Depending on what you mean. To start talking about "CPython compliance", would need to implement named groups. And full "CPython compliance" is not achievable for finite-automaton based implementation (and re1's feature is completely replaceable backends, so FA featureset is a common bound).
pfalcon commentedon Oct 19, 2014
Ok, "ure" module based on re1.5 as described above was merged (and actually went thru couple upgrade iterations adding more features).
dpgeorge commentedon Oct 19, 2014
Thanks @pfalcon, really great work!
Merge pull request micropython#13 from emfcamp/tear-pindef
Merge pull request micropython#13 from mithro/master
Merge pull request micropython#13 from pdp7/master
Merge pull request #13 from adafruit/main
Merge pull request micropython#13 from robert-hh1/w600_ftp
Merge pull request micropython#13 from kwagyeman/openmv
Merge pull request #13 from rk-exxec/tiva_from_stable
Fix 2 array bounds bugs in framebuffer polygon fill