Expression régulière provoquant un débordement de stack

Suite à ma question précédente: ECMAScript Regex pour une chaîne multilignée , j’ai mis en œuvre la procédure de chargement suivante:

void Load( const std::ssortingng& 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(inFile)), (std::istreambuf_iterator()) ); inFile.close(); std::vector<std::future> 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::ssortingng szDataSsortingng ) { for( std::sregex_iterator itData( szDataSsortingng.cbegin(), szDataSsortingng.cend(), regexData ) { // Do Stuff } }, (*itObject)[2].str() ) ); } else if( (*itObject)[1] == "OBJECT2" ) { vecFutures.emplace_back( std::async( []( std::ssortingng szDataSsortingng ) { for( std::sregex_iterator itData( szDataSsortingng.cbegin(), szDataSsortingng.cend(), regexData ) { // Do Stuff } }, (*itObject)[2].str() ) ); } } for( auto& future : vecFutures ) { future.get(); } } 

Cependant, le charger avec ce fichier entraîne un débordement de stack (parameters: 0x00000001, 0x00332FE4):

 === OBJECT2 === :Test Manufacturer :Test Supplier 
:Test Multiline Contact Address :[email protected] :0123456789 === END OBJECT2 === === OBJECT1 === :1 :Test :Here : :12345 :54321 :Me :0.0.0.0 === END OBJECT1 ===

Je n’ai pas pu trouver la source du débordement de stack, mais il semble que la boucle externe std::sregex_iterator soit responsable.

Merci d’avance!

Voici une autre tentative:

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

Dans votre C ++, il serait évidemment écrit comme:

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

Il est fait pour un retour arrière minimal (du moins lors de la mise en correspondance), bien que je sois un peu M. Tired-Face en ce moment, alors j’ai probablement manqué plusieurs façons de l’améliorer.

Il fait deux hypothèses , qui sont utilisées pour éviter beaucoup de retours en arrière (ce qui peut éventuellement causer un débordement de stack, comme d’autres l’ont dit):

  1. Qu’il n’y a jamais de === au début d’une ligne, à l’exception des lignes de marqueur de début / fin.
  2. Ce C ++ prend en charge ces fonctionnalités regex – en particulier l’utilisation d’un lookahead négatif ( ?! ). Cela devrait, vu que c’est le dialecte ECMAScript.

A expliqué:

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

Faites correspondre et capturez le marqueur de début d’object. Le [^=] est un moyen d’éviter un nombre relativement faible de retours en arrière ici, tout comme le vôtre. Nous n’utilisons pas [^ ] , car je ne sais pas s’il peut y avoir des espaces dans l’identifiant OBJECT.

 ((?: 

Commencez à capturer le groupe pour les données. À l’intérieur, un groupe sans capture, car nous allons faire correspondre chaque ligne individuellement.

  (?!===) 

Lookahead négatif – nous ne voulons pas === au début de notre ligne capturée.

  [^\n]+\n 

Correspond à une ligne individuellement.

 )+) 

Faites correspondre au moins une ligne entre les marqueurs de début et de fin, puis capturez TOUTES les lignes d’un même groupe.

 === END \1 === 

Faites correspondre le marqueur de fin.

Comparaison (avec RegexBuddy):

Version originale:

  • Premier match: 1277 pas
  • Correspondance en échec: 1 étape (cela est dû au saut de ligne entre les objects)
  • Deuxième match: 396 marches

Chaque object ajouté entraînera une augmentation du nombre d’étapes pour les précédentes. Par exemple, l’ajout d’un object supplémentaire (copie de l’object 2, renommé en 3) donnera lieu à: 2203 étapes, 1322 étapes, 425 étapes.

Cette version:

  • Premier match: 67 pas
  • Correspondance en échec: 1 étape (encore une fois en raison du saut de ligne entre les objects)
  • Deuxième match: 72 marches
  • Match échoué: 1 étape
  • Troisième match: 67 marches

Sacré retour catastrophique. Le coupable est (?:.|\\n)* . Chaque fois que vous voyez une construction comme celle-ci, vous savez que vous posez des problèmes.

Pourquoi? Parce que vous indiquez au moteur de faire correspondre tout caractère (à l’exception de la nouvelle ligne) OU nouvelle ligne, autant de fois que possible ou aucun. Laisse-moi te guider.

Le moteur démarrera comme prévu et correspondra à la partie === OBJECT2 === sans aucun problème majeur, une nouvelle ligne sera consommée et l’enfer commencera ensuite. Le moteur consum TOUT, jusqu’à === END OBJECT1 === , et retourne de là à une correspondance appropriée. Faire un retour en arrière signifie essentiellement revenir en arrière et appliquer à nouveau l’expression régulière pour voir si cela fonctionne. Essentiellement, essayer toutes les permutations possibles avec votre chaîne. Dans votre cas, cela entraînera quelques centaines de milliers de tentatives. C’est probablement pourquoi certaines choses sont problématiques pour vous.

Je ne sais pas si votre code est meilleur ou s’il contient des erreurs, mais (?:.|\\n)* est identique à l’écriture .* Avec le modificateur de ligne ingle * s * (le point correspond aux nouvelles lignes ) ou [\S\s]* . Si vous remplacez cette construction par l’une des deux précédentes, nous vous recommandons de ne plus voir d’erreur de débordement de stack.

Edit: Découvrez les autres solutions aussi, je n’ai pas vraiment le temps d’approfondir et de fournir une solution solide à votre problème en plus d’expliquer pourquoi c’est si grave.

Vos expressions semblent causer beaucoup de retours en arrière. Je changerais vos expressions en:

D’abord: ^===\s+(.*?)\s+===[\r\n]+^(.*?)[\r\n]+^===\s+END\s+\1\s+===

Deuxième: ^<([^>]+)>:([^<]*)

Ces deux expressions fonctionnent avec les options: Multiline et DotMatchesAll. En incluant le début de l'ancre de ligne, il limite le retour en arrière à au plus une ligne ou un groupe.

Essayez plutôt avec ce motif:

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