c++ - Why did boost regex run out of stack space? -

#include <boost/regex.hpp> #include <string> #include <iostream>  using namespace boost; static const regex regexp(         "std::vector<"             "(std::map<"                    "(std::pair<((\\w+)(::)?)+, (\\w+)>,?)+"              ">,?)+"         ">");  std::string errormsg = "std::vector<"         "std::map<"                 "std::pair<test::test, int>,"                 "std::pair<test::test, int>,"                 "std::pair<test::test, int>"         ">,"         "std::map<"                 "std::pair<test::test, int>,"                 "std::pair<test::test, int>,"                 "std::pair<test::test, int>"         ">" ">"; int main() {     smatch result;     if(regex_match(errormsg, result, regexp))     {           (unsigned = 0; < result.size(); ++i)         {               std::cout << result[i] << std::endl;         }     }  //    std::cout << errormsg << std::endl;      return 0; } 

this produces:

terminate called after throwing instance of 'boost::exception_detail::clone_impl<boost::exception_detail::error_info_injector<std::runtime_error> >'   what():  ran out of stack space trying match regular expression. 

compiled with

g++ regex.cc -lboost_regex 

edit

my platform:

g++ (ubuntu/linaro 4.4.4-14ubuntu5) 4.4.5 libboost-regex1.42 intel(r) core(tm)2 quad cpu q9400 @ 2.66ghz latest ubuntu 64 bit 

((\\w+)(::)?)+ 1 of called "pathological" regular expressions -- it's going take exponential time, because have 2 expressions dependent upon each other 1 right after other. is, fails due catastrophic backtracking.

consider if follow example of link, , reduce "something more complicated" "x". let's \\w:

• ((x+)(::)?)+

let's assume our input never going have ::. having makes regex more complex, if throw out complexity should making things simpler if nothing else:

• (x+)+

now you've got textbook nested quantifier problem detailed in link above.

there few ways fix simplest way disallow backtracking on inner match using atomic group modifier "(?>":

• ((?>\\w+)(::)?)+