Re: regex libs (was Re: [musl] embedded newbies site.)

[Szabolcs Nagy <nsz@port70.net>]

* Justin Cormack <justin@specialbusservice.com> [2013-07-16 16:41:44 +0100]:
> Lua includes a proper regex library. Lua is smaller than PCRE and you get a
> whole programming language thrown in which shows how complex PCRE is...

no, lua uses backtracking matching just like most of the
other listed regex matchers
(it also has weird syntax that is gratuitously different
from the posix one)

you can easily try it yourself with the (a?)^n a^n pattern:

s1 = ''
s2 = ''
for i = 1,24 do
        s1 = s1 .. 'a?'
        s2 = s2 .. 'a'
end
print(string.match(s2, '^'..s1..s2..'$'))

24 is not even a big number but since the matching
is O(2^n) it quickly becomes unresponsive..
(it takes 5s here)

(in the main lua implementation there is a recursion
limit of 200 which is more than enough to render a lua
interpreter completely unresponsive if the regex comes
from untrusted input)