正则表达式导致堆栈溢出

Question

继上一个问题:ECMAScript Regex的多行字符串,我实现了以下加载过程:

void Load( const std::string& szFileName )
{
     static const std::regex regexObject( "=== ([^=]+) ===\\n((?:.|\\n)*)\\n=== END \\1 ===", std::regex_constants::ECMAScript | std::regex_constants::optimize );
     static const std::regex regexData( "<([^>]+)>:([^<]*)\\n", std::regex_constants::ECMAScript | std::regex_constants::optimize );

     std::ifstream inFile( szFileName );
     inFile.exceptions( std::ifstream::badbit );

     std::string szFileData( (std::istreambuf_iterator<char>(inFile)), (std::istreambuf_iterator<char>()) );

     inFile.close();

     std::vector<std::future<void>> vecFutures;

     for( std::sregex_iterator itObject( szFileData.cbegin(), szFileData.cend(), regexObject ), end; itObject != end; ++itObject )
     {
          if( (*itObject)[1] == "OBJECT1" )
          {
               vecFutures.emplace_back( std::async( []( std::string szDataString ) {
                    for( std::sregex_iterator itData( szDataString.cbegin(), szDataString.cend(), regexData ) { // Do Stuff }
               }, (*itObject)[2].str() ) );
          }
          else if( (*itObject)[1] == "OBJECT2" )
          {
               vecFutures.emplace_back( std::async( []( std::string szDataString ) {
                    for( std::sregex_iterator itData( szDataString.cbegin(), szDataString.cend(), regexData ) { // Do Stuff }
               }, (*itObject)[2].str() ) );
          }
     }

     for( auto& future : vecFutures )
     {
          future.get();
     }
}

但是,使用此文件加载会导致堆栈溢出(参数:0x00000001,0x00332FE4):

=== OBJECT2 ===
<Name>:Test Manufacturer
<Supplier>:Test Supplier
<Address>:Test Multiline
Contact
Address
<Email>:test@test.co.uk
<Telephone Number>:0123456789
=== END OBJECT2 ===
=== OBJECT1 ===
<Number>:1
<Name>:Test
<Location>:Here
<Manufacturer>:
<Model Number>:12345
<Serial Number>:54321
<Owner>:Me
<IP Address>:0.0.0.0
=== END OBJECT1 ===

我一直无法找到Stack Overflow的源代码,但看起来外std::sregex_iterator循环是负责任的.

提前致谢!

Answer 1

这是另一个尝试：

=== ([^=]+) ===\n((?:(?!===)[^\n]+\n)+)=== END \1 ===

在你的 C++ 中，它显然会写成：

=== ([^=]+) ===\\n((?:(?!===)[^\\n]+\\n)+)=== END \\1 ===

它是为了最小化回溯（至少在匹配时）而设计的，尽管我现在有点疲惫不堪，所以可能错过了很多改进它的方法。

它做出两个假设，用于避免大量回溯（这可能导致堆栈溢出，正如其他人所说）：

1. ===除了开始/结束标记线之外，一行的开头永远不会有 a 。
2. C++ 支持这些正则表达式功能 - 特别是使用负前瞻 ( ?!)。考虑到它是 ECMAScript 方言，它应该如此。

解释：

=== ([^=]+) ===\n

匹配并捕获对象开始标记。这[^=]是避免此处相对少量回溯的一种方法，与您的相同 - 我们没有使用[^ ]，因为我不知道 OBJECT id 中是否可能有空格。

((?:

开始捕获数据组。在其中，是一个非捕获组，因为我们将单独匹配每一行。

   (?!===)

负向前瞻 - 我们不希望===在捕获行的开头。

   [^\n]+\n

单独匹配一行。

)+)

匹配开始标记和结束标记之间的至少一行，然后捕获单个组中的所有行。

=== END \1 ===

匹配结束标记。

比较（使用RegexBuddy）：

原始版本：

• 第一场比赛：1277步
• 匹配失败：第 1 步（这是由于对象之间的换行符造成的）
• 第二场比赛：396步

每个添加的对象都会导致先前对象的步数增加。例如，再添加一个对象（对象 2 的副本，重命名为 3）将导致：2203 步、1322 步、425 步。

这个版本：

• 第一场比赛：67步
• 匹配失败：1 步（再次由于对象之间的换行符）
• 第二场比赛：72步
• 失败匹配：1步
• 第三场比赛：67步