|
Message-ID: <20130716165534.GR15323@port70.net> Date: Tue, 16 Jul 2013 18:55:35 +0200 From: Szabolcs Nagy <nsz@...t70.net> To: musl@...ts.openwall.com Subject: Re: regex libs (was Re: embedded newbies site.) * Justin Cormack <justin@...cialbusservice.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)
Powered by blists - more mailing lists
Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.