byexamples / byexamples/byexample
Use a Thompson NFA instead of the Python default re (regex) engine if it is possible
- Dominant language
- Python
- Stars
- 67
- Forks
- 9
- PR merge metrics
- No merged PRs in 30d
Description
As most of the languages, interpreters, libs, and most of anything out there, Python uses a classical engine that can have an **exponential** performance in the worst case (known as 'pathological cases').
A non-deterministic finite automata (NFA) can be used to represent any regular expression (without backrefereces). The use of this to implement a regular expression engine is known as the Thompson NFA algorithm.
It is used in the well known grep and awk implementations and it has a **linear** performance.
The idea is to replace the implementation of `re.compile` and the subsequent calls to the `re` module and objects by a NFA implementation.
However, as said before, the NFA will be possible only if the regex has no backreferences.
Byexample uses the backreferences when a given captured tag with label foo appears twice or more times in the expected string.
In those cases the byexample must fall back to the `re` module.
The Thompson NFA must not introduce any new mandatory dependency but it can require an optional one.
Contributor guide
Assessment
This issue has not been assessed yet.