A non-backtracking NFA/DFA-based Perl-compatible regex engine matching on large data streams
A non-backtracking NFA/DFA-based Perl-compatible regex engine matching on large data streams
libsregex - A non-backtracking NFA/DFA-based Perl-compatible regex engine library for matching on large data streams
This library is already quite usable and some people are already using it in production.
Nevertheless this library is still under heavy development. The API is still in flux and may be changed quickly without notice.
This is a pure C library that is designed to have zero dependencies.
No pathological regexes exist for this regex engine because it does not use a backtracking algorithm at all.
Already rewrote the code base of Russ Cox's re1 library using the nginx coding style (yes, I love it!), also incorporated a clone of the nginx memory pool into it for memory management.
Already ported the Thompson and Pike VM backends to sregex. The former is just for yes-or-no matching, and the latter also supports sub-match capturing.
Implemented the case-insensitive matching mode via the SRE_REGEX_CASELESS flag.
The full streaming matching API for the sregex engine has already been implemented,
for both the Pike and Thompson regex VMs. The sub-match capturing also supports streaming processing.
When the state machine is yielded (that is, returning SRE_AGAIN on the current input data chunk),
sregex will always output the current value range for the $& sub-match capture in the user-supplied
ovector array.
Almost all the relevant test cases for PCRE 8.32 and Perl 5.16.2 have been imported into sregex's test suite and all tests are passing right now.
Already implemented an API for assembling multiple user regexes and returning an ID indicating exactly which regex is matched (first), as well as the corresponding sub-match captures.
There is also a Just-in-Time (JIT) compiler targeting x86_64 for the Thompson VM.
The following Perl 5 regex syntax features have already been implemented.
^ match the beginning of lines
$ match the end of lines
\A match only at beginning of stream
\z match only at end of stream
\b match a word boundary
\B match except at a word boundary
. match any char
[ab0-9] character classes (positive)
[^ab0-9] character classes (negative)
\d match a digit character ([0-9])
\D match a non-digit character ([^0-9])
\s match a whitespace character ([ \f\n\r\t])
\S match a non-whitespace character ([^ \f\n\r\t])
\h match a horizontal whitespace character
\H match a character that isn't horizontal whitespace
\v match a vertical whitespace character
\V match a character that isn't vertical whitespace
\w match a "word" character ([A-Za-z0-9_])
\W match a non-"word" character ([^A-Za-z0-9_])
\cK control char (example: VT)
\N match a character that isn't a newline
ab concatenation; first match a, and then b
a|b alternation; match a or b
(a) capturing parentheses
(?:a) non-capturing parantheses
a? match 1 or 0 times, greedily
a* match 0 or more times, greedily
a+ match 1 or more times, greedily
a?? match 1 or 0 times, not greedily
a*? match 0 or more times, not greedily
a+? match 1 or more times, not greedily
a{n} match exactly n times
a{n,m} match at least n but not more than m times, greedily
a{n,} match at least n times, greedily
a{n}? match exactly n times, not greedily (redundant)
a{n,m}? match at least n but not more than m times, not greedily
a{n,}? match at least n times, not greedilyThe following escaping sequences are supported:
\t tab
\n newline
\r return
\f form feed
\a alarm
\e escape
\b backspace (in character class only)
\\x{}, \x00 character whose ordinal is the given hexadecimal number
\o{}, \000 character whose ordinal is the given octal numberEscaping a regex meta character yields the literal character itself, like \{ and \..
Only the octet mode is supported; no multi-byte character encoding love (yet).
This library provides a pure C API. This API is still in flux and may change in the near future without notice.
This library provides the following public constants for use in the various API functions.
SRE_OKSRE_DECLINEDSRE_AGAINSRE_ERRORThe actual meanings of these constants depend on the concrete API functions using them.
This library utilizes a memory pool to simplify memory management. Most of the low-level API functions provided by this library does accept a memory pool pointer as an argument.
The operations on the memory pool on the user side are limited to
sre_pool_t *sre_create_pool(size_t size);Creates a memory pool with a page size of size. Returns the pool as an opaque pointer type sre_pool_t.
Usually the page size you specify should not be too large. Usually 1KB or 4KB should be sufficient. Optimal values depend on your actual regexes and input data pattern involved and should be tuned empirically.
The returned memory pool pointer is usually fed into other API functions provided by this library as an argument.
It is your responsibility to destroy the pool when you no longer need it via the sre_destroy_pool function. Failing to destroy the pool will result in memory leaks.
void sre_destroy_pool(sre_pool_t *pool);Destroys the memory pool created by the sre_create_pool function.
void sre_reset_pool(sre_pool_t *pool);Before running a regex (or set of multiple regexes), you need to parse and compile them first, such that you can run the compiled form of the regex(es) over and over again at maximum speed.
typedef uint8_t sre_char;
typedef uintptr_t sre_uint_t;
typedef intptr_t sre_int_t;
sre_regex_t *sre_regex_parse(sre_pool_t *pool, sre_char *regex,
sre_uint_t *ncaps, int flags, sre_int_t *err_offset);Parses the string representation of the user regex specified by the regex parameter (as a null-terminated string).
Returns a parsed regex object of the opaque pointer type sre_regex_t if no error happens. Otherwise returns a NULL pointer and set the offset in the regex string where the parse failure happens.
The parsed regex object pointer is an Abstract-Syntax-Tree (AST) representation of the string regex. It can later be fed into API function calls like sre_regex_compile as an argument.
The first parameter, pool, is a memory pool created by the sre_create_pool API function.
The ncaps parameter is used to output the number of sub-match captures found in the regex. This integer can later be used to extract sub-match captures.
The flags parameter specifies additional regex compiling flags like below:
SRE_REGEX_CASELESS
case-insensitive matching mode.typedef uint8_t sre_char;
typedef uintptr_t sre_uint_t;
typedef intptr_t sre_int_t;
sre_regex_t *sre_regex_parse_multi(sre_pool_t *pool, sre_char **regexes,
sre_int_t nregexes, sre_uint_t *max_ncaps, int *multi_flags,
sre_int_t *err_offset, sre_int_t *err_regex_id);Similar to the sre_regex_parse API function but works on multiple regexes at once.
These regexes are specified by the C string array regexes, whose size is determined by the nregexes parameter.
All these input regexes are combined into a single parsed regex object, returned as the opaque
pointer of the type sre_regex_t, just like sre_regex_parse. These regexes are
logically connected via the alternative regex operator (|), so the order of these regexes determine
their relative precedence in a tie. Despite of being connected by | logically, the
regex execution API can still signify which of these regexes is matched
by returning the regex ID which is the offset of the regex in the regexes input array.
Upon failures, returns the NULL pointer and sets
err_regex_id for the number of regex having syntax errors
(i.e., the 0-based offset of the regex in the regexes input parameter array), anderr_offset for the string offset in the guilty regex where the failure happens.The output parameter max_ncaps returns the maximum number of sub-match captures in all these regexes.
Note that, this is is the maximum instead of the sum.
The multi_flags is an input array consisting of the regex flags for every regex specified in the regexes array.
The size of this array must be no shorter than the size specified by nregexes. For what
regex flags you can use, just check out the documentation for the sre_regex_parse API function.
sre_program_t *sre_regex_compile(sre_pool_t *pool, sre_regex_t *re);Compiles the parsed regex object (returned by sre_regex_parse) into a bytecode
representation of the regex, of the opaque pointer type sre_program_t.
Returns the NULL pointer in case of failures.
The memory pool specified by the pool parameter does not have to be the same as the one used
by the earlier sre_regex_parse call. But you could use the same memory pool if you want.
The compiled regex form (or bytecode form) returned can be fed into one of the regex backend VMs provided by this library for execution. See regex execution API for more details.
No open issues yet, or sync has not completed.