Thread Leerzeichen-Regex lässt StackExchange ausfallen? (27 answers)
Opened by GwenDragon at 2016-07-21 13:24

clms
 2016-07-25 12:30
#185133 #185133
User since
2010-08-29
373 Artikel
BenutzerIn
[default_avatar]
Auch wenn ich den eigentlichen Grund für den Serverausfall im Aufbau/Flow des CMS und nicht im Backtracking der Regex sehe, bleibt die Frage, ob das mit Perl auch passieren kann. Oder ist die Regex-Engine bei Perl schlauer und optimiert in diesem Fall die Suche auf O(N) statt O(N^2)?

Zur Erinnerung - die Regex ist \s+$.
Wenn jetzt ein String eine lange Reihe von N Leerzeichen hat, muss die Regex beim erste Leerzeichen anfangen zu suchen, ob ein Match vorliegt. Sie überprüft dann die N Leerzeichen und stellt fest, dass hinter den Leerzeichen ein anderes Zeichen kommt, also kein Match vorliegt. Das hat die Komplexität O(N).

Laut StackExchange probiert die Regex es beim nächsten Leerzeichen erneut - und wieder wird die lange Reihe von Leerzeichen nicht von einem Zeilenende sondern einem anderen Zeichen abgeschlossen. Also Backtracking - und das Ganze mit dem dritten Leerzeichen als Start versuchen. So kommt man dann auf O(N*N).

Nun ist aber klar, dass wenn die Regex nicht schon beim ersten Leerzeichen als Start matched, sie auch bei allen anderen Leerzeichen der Reihe nicht matchen kann. Entsprechend kann man die Suche auf O(N) optimieren.

View full thread Leerzeichen-Regex lässt StackExchange ausfallen?