BRRE - BeRo Regex Engine

Benchmark source data from http://lh3lh3.users.sourceforge.net/reb.shtml

BRRE (BeRo Regex Engine):

                                                /installation/ :      47 ms
                  /([a-zA-Z][a-zA-Z0-9]*)://([^ /]+)(/[^ ]*)?/ :     374 ms
                                           /([^ @]+)@([^ @]+)/ :     343 ms
       /([0-9][0-9]?)/([0-9][0-9]?)/([0-9][0-9]([0-9][0-9])?)/ :     265 ms
/([a-zA-Z][a-zA-Z0-9]*)://([^ /]+)(/[^ ]*)?|([^ @]+)@([^ @]+)/ :     375 ms

regex.pp:
                                                /installation/ :      78 ms
                  /([a-zA-Z][a-zA-Z0-9]*)://([^ /]+)(/[^ ]*)?/ :    6333 ms
                                           /([^ @]+)@([^ @]+)/ :   11357 ms
       /([0-9][0-9]?)/([0-9][0-9]?)/([0-9][0-9]([0-9][0-9])?)/ :    1591 ms
/([a-zA-Z][a-zA-Z0-9]*)://([^ /]+)(/[^ ]*)?|([^ @]+)@([^ @]+)/ :   17706 ms

BRRE is in 5 of 5 cases faster than the naive NFA regex implementation from the FPC SVN trunk.

The secret of BRRE speed is that BRRE uses multiple subengines with automatic selection at the regex-compiling-process:

1. UTF8-and-Latin1/Bytewise-capable fixed string search for pure static literal string regexs, shift-or for short strings shorter than 32 chars, and boyer-moore for strings longer than or equal 32 chars.

2. UTF8-and-Latin1/Bytewise-capable damn ultra fast DFA as "full match boundary prefilter" for the followed NFA subengines, so that the NFA subengine must capture only the sub matches, except for the backtracking NFA, because the backtracking NFA must run always fully for itself because of the contra performance points of the backtracking features as back references and so on.

3. UTF8-and-Latin1/Bytewise-capable onepass NFA (aka simpifed DFA with NFA submatch capture feature). This subengine is quite damn super fast! But it can process simple regexs only, where it's always immediately obvious when a repetition ends. For example x(y|z) is onepass, (xy)|(xz) not, but the regex abstract syntax tree optimizer optimizes this anyway out (at least in the most cases), before the bytecode and the OnePassNFA/DFA state map will generated. The base idea is from the re2 regex engine from Google.

4. UTF8-and-Latin1/Bytewise-capable bitparallel backtracking NFA. This subengine is a backtracking NFA combined a already-visited-flag-bitmap.

5. UTF8-and-Latin1/Bytewise-capable parallel threaded non-backtracking NFA (aka Thompson NFA). This subengine supports the most 08/15 regular expression syntax features "except" backtracking-stuff and so on. And this subengine is also very fast, but not so damn super fast like the onepass NFA subengine.

6. UTF8-and-Latin1/Bytewise-capable backtracking NFA. This subengine is for all cases, for whose the other subengines can't handle these, for example regexs with backreferences stuff and so on.

And as a addon, BRRE features prefix presearching with shift-or for short strings shorter than 32 chars, and boyer-moore (or naive bruteforce if UTF8) for strings longer than or equal 32 chars. So for example the prefix for regex /Hello [A-Za-z]+/ is "Hello "

And BRRE has Unicode 6.0 support at the UTF8 work mode. It's with double matchcapturing-bookkeeping, it captures "always" the codeunitoffsets and codepointoffsets at the same time, to save costly UTF8CodePoint<->ByteCodeUnit reindexing time, for example at the backtracking features.