導致堆棧溢出

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]*。如果你用我推薦的兩個之一替換了這個構造，你希望不會再看到堆棧溢出錯誤。

編輯： 查看其他解決方案，我沒有真正有時間去深入併爲您的問題提供一個可靠的解決方案，除了解釋爲什麼它如此糟糕。