Re: [Boost-bugs] [Boost C++ Libraries] #1636: Bug in regex?

Subject: Re: [Boost-bugs] [Boost C++ Libraries] #1636: Bug in regex?
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2008-03-30 16:01:04

#1636: Bug in regex?
--------------------------------+-------------------------------------------
  Reporter:  freewave_at_[hidden]  |       Owner:  johnmaddock
      Type:  Support Requests   |      Status:  closed     
 Milestone:  Boost 1.36.0       |   Component:  regex      
   Version:  Boost 1.34.1       |    Severity:  Problem    
Resolution:  wontfix            |    Keywords:             
--------------------------------+-------------------------------------------
Changes (by johnmaddock):

  * status:  new => closed
  * resolution:  => wontfix

Comment:

 This is expected behaviour: Perl-style regular expression matching is an
 NP-complete problem in general, and any expression that looks like:
 (something*)* may experience these issues eventually.  Boost.Regex tries
 to prevent "runaway" expressions by throwing an exception if the
 complexity of the match looks like it's going to exceed a certain maximum
 - and this is what's happening here.

 Using a more precise expression would fix this - for example

 "([^,]*?,){11}P"

 or

 "(?>.*?,){11}P"

 would fix this - and improve performance a lot into the bargain.

 HTH, John Maddock.

-- 
Ticket URL: <http://svn.boost.org/trac/boost/ticket/1636#comment:1>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.