byexamples / byexamples/byexample

Use a Thompson NFA instead of the Python default re (regex) engine if it is possible

Open
#16 4 comments 2 reactions 0 assignees View on GitHub
enhancement far in the future help wanted
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.