Regular Expression verursacht Stapelüberlauf

Question

Weitere meiner vorherigen Frage:

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

Es ist jedoch mit dieser Datei Ergebnisse in einem Stapelüberlauf Laden: ECMAScript Regex for a multilined string, habe ich die folgenden Ladevorgang implementiert (Parameter: 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 === 

ich war nicht in der Lage, die Quelle des Stack-Überlauf zu finden, aber es sieht aus wie die äußere std::sregex_iterator Schleife verantwortlich ist.

Vielen Dank im Voraus!

Answer 1

Hier ist ein weiterer Versuch:

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

In Ihrem C++ es offensichtlich geschrieben werden würde:

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

Es ist gemacht für minimal Rückzieher (zumindest, wenn passend), obwohl ich ein bisschen bin Mr. Tired-Face im Moment, hat also wahrscheinlich einige Wege verpasst, um es zu verbessern.

Es macht zwei Annahmen, die verwendet werden, eine Menge Backtracking zu vermeiden (das möglicherweise den Stapelüberlauf verursacht, wie andere gesagt haben):

1. Dass es nie ein === zu Beginn eines Linie, mit Ausnahme der Anfangs-/Endmarkierungslinien.
2. Das C++ unterstützt diese Regex-Funktionen - insbesondere die Verwendung eines negativen Lookahead (?!). Es sollte, in Anbetracht seines ECMAScript-Dialekts.

Erklärt:

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

Spiel und erfassen das Objekt Startmarkierung. Die [^=] ist eine Möglichkeit, um eine relativ kleine Menge von Backtracking hier zu vermeiden, genau wie Ihre - wir verwenden nicht [^ ], weil ich nicht weiß, ob es Leerzeichen in der OBJECT-ID geben kann.

((?: 

Starten Sie die Erfassungsgruppe für Daten. Darin befindet sich eine nicht einfangende Gruppe, da wir jede Zeile einzeln abgleichen.

(?!===) 

Negative Look-Ahead - wir wollen nicht === zu Beginn unserer erfassten Linie.

[^\n]+\n 

Entspricht einer Zeile einzeln.

Passen Sie mindestens eine Zeile zwischen Anfangs- und Endmarkierungen an, und erfassen Sie dann ALLE Zeilen in einer einzelnen Gruppe.

=== END \1 === 

Passen Sie die Endmarkierung an.

Vergleich (mit RegexBuddy):

Originalversion:

• Erstes Spiel: 1277 Schritte
• fehlgeschlagen match: 1 Schritt (dies ist aufgrund des Zeilenumbruchs zwischen dem Objekte)
• Zweites Spiel: 396 Schritte

Jedes hinzugefügte Objekt erhöht die Anzahl der Schritte für die vorherigen. Z.B.Das Hinzufügen eines weiteren Objekts (Kopie von Objekt 2, umbenannt in 3) ergibt: 2203 Schritte, 1322 Schritte, 425 Schritte.

Diese Version:

• Erstes Spiel: 67 Schritte
• fehlgeschlagen match: 1 Schritt (wieder einmal aufgrund des Zeilenumbruchs zwischen den Objekten)
• zweite Partie: 72 Schritte
• Fehlgeschlagene Übereinstimmung: 1 Schritt
• Dritte Übereinstimmung: 67 Schritte

Answer 2

Versuchen mit diesem Muster statt:

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

Answer 3

erscheinen Ihre Ausdrücke causeing viel Rückzieher werden.

Erstens: Ich würde Ihre Ausdrücke ändern ^===\s+(.*?)\s+===[\r\n]+^(.*?)[\r\n]+^===\s+END\s+\1\s+===

• anschauliches Beispiel: http://www.rubular.com/r/Iydp7AAxAz

Zweitens: ^<([^>]+)>:([^<]*)

• anschauliches Beispiel: http://www.rubular.com/r/mdeyMKIPcf

Beide Ausdrücke funktionieren mit den Optionen Multiline und DotMatchesAll. Durch die Einbeziehung des Anfangs des Linienankers ^ wird die Rückverfolgung auf höchstens eine Linie oder eine Gruppe begrenzt.

Answer 4

Heiliges katastrophales Backtracking. Der Schuldige ist (?:.|\\n)*. Wann immer du ein Konstrukt wie dieses siehst, weißt du, dass du nach Ärger fragst.

Warum? Weil Sie der Engine sagen, dass sie so oft wie möglich oder gar keinem anderen Zeichen (außer Newline) oder Newline entsprechen soll. Lass mich dich durchgehen.

Der Motor startet wie erwartet und entspricht dem === OBJECT2 ===-Teil ohne größere Probleme, ein Newline wird verbraucht, und die Hölle wird dann beginnen. Die Engine verbraucht ALLES bis hinunter auf === END OBJECT1 === und rückt ihren Weg von dort zu einem passenden Match zurück. Backtracking bedeutet grundsätzlich, einen Schritt zurückzugehen und die Regex erneut anzuwenden, um zu sehen, ob es funktioniert. Grundsätzlich versuchen Sie alle möglichen Permutationen mit Ihrer Zeichenfolge. Dies wird in Ihrem Fall zu ein paar hunderttausend Versuchen führen. Das ist wahrscheinlich der Grund, warum Sachen für dich problematisch sind.

Ich weiß nicht, ob Ihr Code besser ist oder wenn es irgendwelche Fehler in ihm, aber (?:.|\\n)* ist das gleiche wie das Schreiben .* mit der * s * ingle Linie Modifikator (Punkt paßt Zeilenumbrüche) oder [\S\s]*. Wenn Sie dieses Konstrukt durch eines der beiden ersetzen, die ich empfohlen habe, werden Sie hoffentlich keinen Stapelüberlauffehler mehr sehen.

Edit: Schauen Sie sich auch die anderen Lösungen an, ich hatte nicht wirklich Zeit, in die Tiefe zu gehen und bieten eine solide Lösung yo Ihr Problem neben der Erklärung, warum es so schlecht ist.