导致堆栈溢出

Question

而且我刚才的问题正则表达式：ECMAScript Regex for a multilined string，我已实现了以下装载过程：

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(); 
    } 
} 

然而，在一个堆栈溢出这个文件会导致加载它（参数：00000001，0x00332FE4） ：

=== OBJECT2 === 
<Name>:Test Manufacturer 
<Supplier>:Test Supplier 
<Address>:Test Multiline 
Contact 
Address 
<Email>:test@test.co.uk 
<Telephone Number>:
=== 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 === 

我一直无法找到堆栈溢出的来源，但它看起来像外std::sregex_iterator循环负责。

在此先感谢！

Answer 1

这里的另一种尝试：

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

在C++中，它显然会被写为：

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

它的最小回溯做（至少匹配时），虽然我有点Tired-Face先生，因此可能错过了改进它的几种方法。

它使两个假设，这是用来避免大量回溯（即可能导致堆栈溢出，正如其他人说的）：

1. 这从未有一个===在一开始行，除了开始/结束标记线。
2. C++支持这些正则表达式特性 - 特别是使用负向预测（?!）。它应该考虑到它是ECMAScript方言。

解释：

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

匹配和捕捉对象开始标记。 [^=]是避免相对少量回溯的一种方法，与您的相同 - 我们不使用[^ ]，因为我不知道OBJECT ID中是否有空格。

((?: 

开始捕获数据组。在它内部，一个非捕获组，因为我们要单独匹配每条线。

(?!===) 

负前瞻 - 我们不会在我们捕捉到的线路开始想===。

[^\n]+\n 

单独匹配一条线。

)+) 

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

=== END \1 === 

匹配结束标记。

比较（使用使用RegexBuddy）：

原始版本：

• 首先匹配：1277步骤
• 失败匹配：1个步骤（这是由于将行断物体）
• 第二次匹配：396步

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

此版本：

• 首先匹配：67个步骤
• 失败匹配：1个步骤（再次由于对象之间的换行）
• 第二匹配：72步骤
• 失败匹配：1步
• 第三次匹配：67步

Answer 2

尝试用这种模式来代替：

static const std::regex regexObject("=== (\\S+) ===\\n((?:[^\\n]+|\\n(?!=== END \\1 ===))*)\\n=== END \\1 ===", std::regex_constants::ECMAScript | std::regex_constants::optimize); 

Answer 3

你的表情似乎causeing很多回溯。我会改变你的表达式：

第一：^===\s+(.*?)\s+===[\r\n]+^(.*?)[\r\n]+^===\s+END\s+\1\s+===

• 活生生的例子：http://www.rubular.com/r/Iydp7AAxAz

二：^<([^>]+)>:([^<]*)

• 活生生的例子：http://www.rubular.com/r/mdeyMKIPcf

这两个表达式都与选项一起使用：Multiline和DotMatchesAll选项。通过包括起始行锚点^它将回溯限制为最多一行或一组。

Answer 4

神圣的灾难性的回溯。罪魁祸首是(?:.|\\n)*。每当你看到这样的结构时，你就会知道你在寻找麻烦。

为什么？因为你告诉引擎匹配任何字符（除了换行符）或换行符，尽可能多次，或者没有。让我带你通过它。

发动机将按预期启动，并匹配=== OBJECT2 ===-部分，没有任何重大问题，换行符将被消耗，地狱将开始。引擎消耗所有东西，一直到=== END OBJECT1 ===，并从那里回溯到合适的匹配。回溯基本意味着返回一步并再次应用正则表达式来查看它是否有效。基本上用你的字符串尝试所有可能的排列组合。在您的情况下，这将导致几次尝试。这可能是你为什么会遇到问题的原因。

我不知道如果你的代码是任何更好，如果它有任何错误，但(?:.|\\n)*相同与* 小号·英格尔行修改写入.*（点匹配换行符）或[\S\s]*。如果你用我推荐的两个之一替换了这个构造，你希望不会再看到堆栈溢出错误。

编辑： 查看其他解决方案，我没有真正有时间去深入并为您的问题提供一个可靠的解决方案，除了解释为什么它如此糟糕。