Регулярное выражение вызывает переполнения стека

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

Однако, загрузив ее с этим файлом приводит к переполнению стека (параметры: 0x00000001, 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 === 

Это сделано для минимального отката (по крайней мере, при сопоставлении), хотя я немного Г-н Усталый-Лицо в данный момент, поэтому, вероятно, пропустил немало способов улучшить его.

Это делает два предположения, которые используются, чтобы избежать большого количества возвратов (что, возможно, вызывает переполнение стека, как уже говорили другие):

1. То есть никогда нет === в начале линии, за исключением линий начала и конца маркера.
2. Этот C++ поддерживает эти функции регулярного выражения - в частности, использование отрицательного вида (?!). Это необходимо, учитывая, что это диалект ECMAScript.

Разъяснение:

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

Match и захватить начальный объект маркер. [^=] - один из способов избежать относительно небольшого количества обратного отслеживания здесь, как и у вас - мы не используем [^ ], потому что я не знаю, могут ли быть пробелы в OBJECT id.

((?: 

Начать сбор данных для данных. Внутри это не захватывающая группа, потому что мы будем соответствовать каждой строке индивидуально.

(?!===) 

Отрицательное опережение - мы не хотим === в начале нашей захваченной линии.

[^\n]+\n 

Соответствует одной строке в отдельности.

)+) 

Соедините хотя бы одну строку между маркерами начала и конца, а затем захватите ВСЕ строки в одной группе.

=== END \1 === 

Соответствующий маркер конца.

Сравнение (с использованием RegexBuddy):

Оригинальная версия:

• Первый матч: 1277 шаги
• Failed матч: 1 этап (это из-за разрыва линии между объектов)
• Второй матч: 396 этапов

Каждый добавленный объект приведет к увеличению количества шагов для предыдущих. Например., добавление еще одного объекта (копия объекта 2, переименованного в 3) приведет к: 2203 шагам, 1322 шагам, 425 шагам.

Эта версия:

• Первый матч: 67 шагов
• Failed матч: 1 этап (в очередной раз из-за разрыва линии между объектами)
• Второй матч: 72 шагает
• Неверное совпадение: 1 шаг
• Третий матч: 67 шагов

Answer 2

Try с этим рисунком вместо:

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

Священный катастрофический backtracking. Претендент (?:.|\\n)*. Всякий раз, когда вы видите такую ​​конструкцию, вы знаете, что вы просите о неприятностях.

Почему? Потому что вы говорите движку, чтобы он соответствовал любому символу (кроме новой строки) или новой строке, как можно чаще, или никому. Позвольте мне провести вас через это.

Двигатель будет работать как можно раньше и будет соответствовать === OBJECT2 === -part без каких-либо серьезных проблем, будет использована новая линия, и тогда начнется ад. Двигатель потребляет ВСЕ, вплоть до === END OBJECT1 ===, и отходит оттуда к подходящему совпадению. Backtracking в основном означает возврат на один шаг и повторное применение регулярного выражения, чтобы увидеть, работает ли оно. В основном, все возможные перестановки с вашей строкой. Это, в вашем случае, приведет к нескольким попыткам: сто тысяч. Вероятно, поэтому для вас проблематично.

Я не знаю, если ваш код лучше, или если у него есть какая-либо ошибка в нем, но (?:.|\\n)* таком же, как написание .* с * сек * модификатором Ingle линии (точка соответствует новой строке) или [\S\s]*. Если вы замените эту конструкцию на одну из двух, я рекомендую вам, надеюсь, больше не увидеть ошибку переполнения стека.

Редактировать: Проверьте другие решения тоже, я действительно не успел углубиться и обеспечить надежное решение вашей проблемы, кроме объяснения, почему это так плохо.