From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/3659 Path: news.gmane.org!not-for-mail From: Szabolcs Nagy Newsgroups: gmane.linux.lib.musl.general Subject: Re: regex libs (was Re: [musl] embedded newbies site.) Date: Tue, 16 Jul 2013 18:55:35 +0200 Message-ID: <20130716165534.GR15323@port70.net> References: Reply-To: musl@lists.openwall.com NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: ger.gmane.org 1373993746 31620 80.91.229.3 (16 Jul 2013 16:55:46 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Tue, 16 Jul 2013 16:55:46 +0000 (UTC) To: musl@lists.openwall.com Original-X-From: musl-return-3663-gllmg-musl=m.gmane.org@lists.openwall.com Tue Jul 16 18:55:48 2013 Return-path: Envelope-to: gllmg-musl@plane.gmane.org Original-Received: from mother.openwall.net ([195.42.179.200]) by plane.gmane.org with smtp (Exim 4.69) (envelope-from ) id 1Uz8XT-0006kB-8Z for gllmg-musl@plane.gmane.org; Tue, 16 Jul 2013 18:55:47 +0200 Original-Received: (qmail 10194 invoked by uid 550); 16 Jul 2013 16:55:46 -0000 Mailing-List: contact musl-help@lists.openwall.com; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: Original-Received: (qmail 10185 invoked from network); 16 Jul 2013 16:55:46 -0000 Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.21 (2010-09-15) Xref: news.gmane.org gmane.linux.lib.musl.general:3659 Archived-At: * Justin Cormack [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)