Re: [Boost-bugs] [Boost C++ Libraries] #8392: Too complex regex for boost::regex (perl, extended) isn't so complex

Subject: Re: [Boost-bugs] [Boost C++ Libraries] #8392: Too complex regex for boost::regex (perl, extended) isn't so complex
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2013-04-21 11:00:25

#8392: Too complex regex for boost::regex (perl, extended) isn't so complex
-------------------------------+--------------------------------------------
  Reporter:  bkalinczuk@…      |       Owner:  johnmaddock
      Type:  Bugs              |      Status:  closed     
 Milestone:  To Be Determined  |   Component:  regex      
   Version:  Boost 1.52.0      |    Severity:  Problem    
Resolution:  wontfix           |    Keywords:             
-------------------------------+--------------------------------------------

Comment (by anonymous):

 >I checked your example with grep and it had no problem with matching the
 largest matching substring. (There wasn't even any delay).

 Grep is a completely different beast: it's a DFA meaning the complexity of
 matching is O(N).  Perl compatible engines are NFA's, and in the worst
 case the complexity of obtaining a match is NP-complete, so something like
 O(N!) for an N-character string.

 >I understand, that for the purpose of limiting the time taken for regex
 matching/searching a developer can set a BOOST_REGEX_MAX_STATE_COUNT as he
 wishes. I would expect though, that regex matching will take
 O(BOOST_REGEX_MAX_STATE_COUNT * exp(size_of_regex) ) (128n in the
 example), which is not the case.

 No it's much worst than that as mentioned above.  NP-complete in the worst
 case (which strangely this nearly is).

 >I believe there is a bug with counting number of states in this example
 and the behaviour is not as it is described.

 It's not states in the machine that matter - it's how many are ''visited''
 while trying to find the match.  The maximum is set to the lowest of:

 * BOOST_REGEX_MAX_STATE_COUNT
 * N^2^ for an N character string.
 * A lower limit k, which is hard coded to 100000.

 You can change this behavour by editing {{{estimate_max_state_count}}} in
 perl_matcher_common.hpp.

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