TPerlRegEx - stack overflow

[liftoff]

Hallo zusammen.:)

Da dies mein erstes Posting hier ist, zunächst mal eine ganz kurze Vorstellung.

Ich bin 44 Jahre alt, männlich und Programmierknecht.

Zur Zeit stelle ich eine über Jahre gewachsene Klassenbibliothek zur Verarbeitung von Swiftnachrichten von Delphi 2007 nach XE um.
Hier hatte ich einige erhellenden Momente im Zusammenhang mit Unicode, welche ich aber soweit in den Griff bekommen habe. :wink:
Nur die TPerlRegEx-Klasse macht mir da im Moment noch Probleme. Zuvor habe ich den selben pcre-Unterbau von pcre.org mit einem anderen Wrapper verwendet. Also:

Folgender String
{4:
:16R:XYZ
:20C:ABC
usw. mit insgesamt 482 Zeilen. Am Ende dann:
-}

Matchen soll sich das mit

({4:\r\n(?:[^\r\n]*\r\n)*-})

Der Teil-Ausdruck (?:[^\r\n]*\r\n)* führt zu einem stack overflow. Finde ich bei lümmeligen 482 Zeile etwas merkwürdig.
Mit PCRE 5.x hat das auch jahrelang wunderbar geklappt.

Jemand dazu eine Idee? Vielleicht auch, wie man die Stacksize erhöhen könnte?

Vielen Dank und viele Grüße

[Namenloser]

Willkommen in der DP :dp:

Ich kenne mich mit dem Wrapper und PCRE-Interna nicht aus, aber könnte es daran liegen, dass Unicode-Strings doppelt so viele Bytes pro Zeichen haben wie Ansi-Strings und daher doppelt so viel Platz auf dem Stack benötigt wird?

Die Größe des Stack kann man bei Delphi in den Projekt-Optionen unter Linker einstellen (jedenfalls bei Delphi 2006, bei XE ist der Build-Prozess ja etwas anders).

Oder könnte es sein, dass der neue Wrapper standardmäßig non-greedy statt greedy (oder umgekert?) matcht? Ich sehe zwar auf den ersten Blick nicht, wo das bei diesem Ausdruck einen Unterschied machen sollte, aber wie gesagt kenne ich mich mit den PCRE-Interna nicht aus. Vielleicht einfach mal ausprobieren...

[himitsu]

PCRE gibt es nur für ANSI. (Unicode wird als UTF-8 behandelt).

Es wird hier das originale PCRE von Philip Hazel als *.obj ins Delphi gelinkt. (unter Mac über eine DLL)
Also genau das Selbe, was man in C#, PHP und Co. finden kann.

In Delphi wird daher das Unicode in UTF-8 umgewandelt, also nix mit 2 Byte pro Char,
aber ansonsten ist da nix Besonderes dran. Nur Unicode-UTF8-Konvertierungen und alles in eine Klasse verpackt, aber am Ende nur der originale C++-Code.


Welche Delphi-Edition nutzt du denn genau?
Falls nicht grade die "Starter", dann aktiviere in den Prokjektoptionen mal die DebugDCUs.

Wie sieht der Stacktrace aus?
Und knallt es genau?

Ein Testprojekt hast du nicht zufällig für uns?

[liftoff]

Bin gerade nicht im Büro :wink:. Auf jeden Fall ist es keine Starter Edition.

Ich habe mir einen Wrapper für den Wrapper geschrieben, damit ich die Orginalsourcen meiner Bibliothek (etwa 15000 Codezeilen) nicht anfassen muss. Diese arbeitet weiterhin mit string, der ja UTF16-codiert ist. Problem war nur die Umwandlung der Matchpositionen von UTF8 nach UTF16. Ein €-Zeichen hat beispielsweise 3 Byte in UTF8 und ein Char (2Byte) in UTF16. Das läuft auch alles prima, solange die zu matchenden Nachrichten nicht zu lang werden.

Mein Problem kann man auch ganz einfach mit der originalen TPerlRegEx nachstellen, also losgelöst von meinem Code.
Es knallt dann direkt beim Aufruf von pcre_exec in TPerlRegEx.Match.
Geliefert wird ein EStackOverflow.

({4:\r\n(?:[^\r\n]*\r\n)*-})

Der Teilausdruck in der Mitte muss ja von pcre_exec intern immer wieder pro Zeile durchgeackert werden. Und irgendwo bei 300 Zeilen (genaue Zahl habe ich jetzt nicht da) ist dann einfach Schluss und die Exception wird ausgeworfen. In meinem Delphi-2007-Wrapper um pcre.obj ist das nicht der Fall.

Entweder ich muss den Ausdruck anfassen, was dann bedeutet, dass ich unter Umständen eine Menge solcher Gefahrenstellen in der Bibliothek habe.
Oder es gelingt irgendwie, die Stackgröße zu erhöhen. Auf pcre.org wird das Thema zwar durchgekaut, allerdings gelingt es mir bisher nicht, dass mit Delphi zu verheiraten.

Wie soll so ein Beispielprojekt aussehen? Könnte ich dann morgen sicherlich noch liefern.

[Uwe Raabe]

Ich kann mich erinnern, daß wir vor Jahren mal ein ähnliches Problem mit TPerlRegEx hatten, das mangels Pascal-Sourcen weder zu debuggen, noch zu beheben war. Die (zumindest damalige) Implementation der RegEx-Enhine war stark rekursiv und brachte bei bestimmten Eingabedateien einen StackOverflow.

Die damalige Lösung bestand darin, auf TPerlRegEx zu verzichten und einen nicht-rekursiven, handgeschriebenen Parser zu verwenden. War auch um Klassen performanter und ließ sich wesentlich besser debuggen.

[liftoff]

Vielen Dank für die bisherigen Anworten.

Einen eigenen Parser zu schreiben, wäre hier viel zu aufwändig. Das Ganze ist ja bereits ein Parser für Swiftnachrichten auf der Basis von regulären Ausdrücken. In der Tat ist TPerlRegEx ungefähr halb so schnell, wie mein alter Wrapper. Insgesamt ist die Performance aber zufriedenstellend. :)

Hier dann mal ein Beispielcode:

Code:

var re : TPerlRegEx;
    teststr : UTF8String;
    l1 : integer;
begin
  try
    re := TPerlRegEx.create;
    re.Options := [precaseless];
    re.State := [];

    re.RegEx := '({4:\r\n(?:[^\r\n]*\r\n)*-})';
    re.Compile;

    //    Nun Beispielstring mit Inhalt
    //    {4:
    //    :00X:ABCDEFB0123456789
    //    :00X:ABCDEFB0123456789
    //    :00X:ABCDEFB0123456789
    //    :00X:ABCDEFB0123456789
    //    ...
    //    -}
    //    zusammenbauen

    TestStr := '{4:'+chr(13)+chr(10);

    for l1 := 1 to 500 do
        TestStr := TestStr + ':00X:ABCDEFB0123456789' +chr(13)+chr(10);

    TestStr := TestStr + '-}';


    re.Subject := TestStr;

    re.Match;

    { TODO -oUser -cConsole Main : Code hier einfügen }
  except
    on E: Exception do
      Writeln(E.ClassName, ': ', E.Message);
  end;

  ReadLn;
end.

Es knallt bei re.match.

Angehängt ist auch ein Beipielprojekt. Ist hoffentlich so korrekt. Delphi XE ist übrigens die Enterprise-Edition.

Anhang 37052

[ele]

Huch, bin etwas überrascht hier noch einen Delphi Programmierer anzutreffen der sich mit SWIFT-Messages herumschlagen muss. Wilkommen im Club :-D

Folgende RegEx funktioniert:

Code:

({4:\r\n(?:[^\r\n]*\r\n)*?-})

P.S: Falls du jemals mit deinem Job unzufrieden wirst. Unsere Firma sucht immer wieder mal Delphi-Programmiere mit SWIFT-Erfahrung. Melde dich einfach per PM bei mir falls du interessiert bist.

[WladiD]

Zitat:

Zitat von ele (Beitrag 1170618)

Folgende RegEx funktioniert:

Code:

({4:\r\n(?:[^\r\n]*\r\n)*?-})

Ich habe keine Ahnung von SWIFT (zumindest nicht im Detail), aber der reguläre Ausdruck ist definitv nicht richtig.

- Geschweifte Klammern haben in pcre eine spezielle Bedeutung (Quantifizierung) und müssen daher escaped werden, wenn man sie matchen möchte
- Das Fragezeichen vor der Klammer ist auch fragwürdig, denn es ist ein Quantifizierer also ein Kürzel für {0,1} und ein vorhergehendes Char, Set oder Gruppe fehlt demnach

Dieser Ausdruck würde die vorliegenden Daten richtig matchen:

Code:

(\{4:\r\n(:\w{3}:.*\r\n)*-\})

PS: Reguläre Ausdrücke sind (richtig angewendet) in 99% aller Fälle schneller (weil sie direkt in Maschinencode übersetzt werden) als ein selbstgeschriebener Parser, eine bestimmte Komplexität an den zu matchenden Daten vorausgesetzt.

[liftoff]

Der reguläre Ausdruck hat schon viele fehlerfreie Jahre auf dem Buckel. :P
Macht halt eben Mucken nach der Portierung von 2007 nach XE.

Also mit geschweiften Klammern hatte ich in pcre noch nie Probleme. Nur wenn daraus tatsächlich eine Quantifizierung entsteht. Dann ist ein \ angesagt. Werde den Einwand aber auf jeden Fall mal im Hinterkopf behalten.

Noch ein Frage zu dem *? (was wirklich prima funktioniert. Danke !)

Bedeutet dies, dass pcre bei nongreedy quantifiers immer nur einen Match auf den Stack legt?
Derart ins Eingemachte bin ich da nie gegangen.

[Namenloser]

@WladiD:
Ein auf eine geöffnete Klammer folgendes Fragezeichen markiert den Beginn eines Subpatterns und ist gültige PCRE-Syntax. Die geschweiften Klammern sollte man allerdings besser escapen.

Abgesehen davon sollte ein selbstgeschriebener Parser eigentlich immer schneller sein als Regex, zumindest in einer kompilierenden Sprache wie Delphi.

@liftoff:
Hatte ich mit Greedy/Non-Greedy wohl doch den richtigen Riecher ;)

Geht der String denn nach dem

Delphi-Quellcode:

-}

noch weiter? Denn die Sub-Expression

Delphi-Quellcode:

[^\r\n]*\r\n

matcht ja auch auf Anfang und Ende eines solchen Konstrukts, d.h. die Engine geht immer erst mal bis zum Ende des Strings, weil ja immer noch ein

Delphi-Quellcode:

-}

folgen könnte; erst am Ende merkt sie dann, dass dort keines ist, und geht schrittweise zurück. Das könnte also, gerade in Kombination mit Sub-Patterns, die vielleicht rekursiv implementiert sind, die Ursache für den Überlauf sein.

[liftoff]

Ja, gutes Näschen. :wink:

Es folgt am Anfang der letzten Zeile immer ein '-}'

Eine Swiftnachricht besteht aus mehreren Blöcken.

Code:

{1:...}{2:...}{3:...}{4:
Nachrichteinhalt
-}{5:}

Der Block 4 (Textblock) muss immer mit '{4:'+Zeilenumbruch anfangen und mit Zeilenumbruch+'-}' enden.

Blöcke 1+2 enthalten Adressinformationen (Absender+Empfänger), 3 Userinfos und 5 Checksummen und son Zeuchs. 1+3+5 sind optional.

Ich habe eben auch noch einen anderen funktionierenden Konstrukt gebastelt

Code:

{4:\R(?:[[:ascii:]]+\R)+-}

[liftoff]

So. Nach einigen Tests habe ich mich für die non-greedy Variante entschieden.
Performance liegt bei etwa 22000 Nachrichten/h, also parsen, zerlegen und strukturiert in der DB ablegen.
Auf den produktiven Systeme geht das noch ne ganze Ecke flotter.
Ist zwar langsamer als vorher, jedoch vollkommen zufriedenstellend. :-D
Nun lass ich die Bibliothek auf die anderen Prozesse los.

Dank Euch bis hierhin für die Hilfe. :thumb:

@ele
Bin sehr zufrieden mit meinem Arbeitgeber. Aber vielleicht kann man sich ja auf fachlicher Ebene ein wenig austauschen.
Bei mir steht beispielweise demnächst die Erweiterung auf ISO20022 (XML) an.

[MaBuSE]

Zitat:

Zitat von liftoff (Beitrag 1170612)

Code:

...
    re.RegEx := '({4:\r\n(?:[^\r\n]*\r\n)*-})';

Hallo,
ich habe mit meinen RegEx Experten gesprochen. 8-)

Er sagt, Deine RegEx sieht so aus, als hättest Du den Unterschied zwischen greedy und non-greedy nicht richtig verstanden, als Du diese Expression erstellt hast. Es sieht so aus, als wolltest Du das non-greedy manuell erzwingen. Das macht die RegEx nur unnötig kompliziert.

Folgende Expression würde alles zwischen dem '{4:' und '-}' auswählen. Mit der non-greedy Option '?' die nach dem Wildcard '*' steht, wird das Ergebnis möglichst kurz gehalten.

Code:

...
    re.RegEx := '(\{4\:.*?-\})';
...

'{4: bla bla bla bla -}{4: bla bla -}'

-> '{4: bla bla bla bla -}' wird ausgewählt

Code:

...
    re.RegEx := '(\{4\:.*-\})'; // ohne ? -> greedy
...

ohne ? -> greedy wird folgendes ausgewählt:

'{4: bla bla bla bla -}{4: bla bla -}'

Durch die Vereinfachung der RegEx ist es nicht nur einfacher zu lesen sondern es werden auch weniger rekursive Aufrufe nötig, also auch der Stack weniger beansprucht ;-)
Ich hoffe das hilft Dir weiter.

cu
MaBuSE

[edit]
Obiges Beispiel funktioniert natürlich nur wenn die SingleLine Option aktiv ist. Nur dann steht der '.' auch für ein '/n'.

Delphi-Quellcode:

...
//    re.Options := [preCaseLess, preSingleLine];
//    re.RegEx := '(\{4\:.*?-\})';

    // alternativ kann man die Optionen auch in die RegEx schreiben: 
    // '?' -> jetzt kommen Optionen -> 's' = SingleLine ; 'i' = CaseLess -> ':' = Optionen Ende
    re.Options := [];
    re.RegEx := '(?si:\{4\:.*?-\})';
...

Habe ich ausprobiert funktioniert. :stupid:
[/edit]

[edit] Beispiel:

Delphi-Quellcode:

unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls;

type
  TForm1 = class(TForm)
    Button1: TButton;
    Memo1: TMemo;
    procedure Button1Click(Sender: TObject);
  private
    { Private-Deklarationen }
  public
    { Public-Deklarationen }
  end;

var
  Form1: TForm1;

implementation

uses
  RegularExpressionsCore;

{$R *.dfm}

procedure TForm1.Button1Click(Sender: TObject);
var re : TPerlRegEx;
    teststr : UTF8String;
    l1 : integer;
begin
  try
    re := TPerlRegEx.create;
    re.State := [];
    re.Options := [];
    re.RegEx := '(?si:\{4\:.*?-\})';
    re.Compile;

    //    Nun Beispielstring mit Inhalt
    //    {4:
    //    :00X:ABCDEFB0123456789
    //    :00X:ABCDEFB0123456789
    //    -}
    //    ...
    //    {4:
    //    :00X:ABCDEFB0123456789
    //    :00X:ABCDEFB0123456789
    //    -}
    //    zusammenbauen

    TestStr := '{4:'+chr(13)+chr(10);
    for l1 := 1 to 2 do
    begin
      TestStr := TestStr + ':00X:ABCDEFB0123456789' +chr(13)+chr(10);
    end;
    TestStr := TestStr + '-}';
    TestStr := TestStr + TestStr + TestStr + TestStr;

    re.Subject := TestStr;

    if re.Match then
    begin
      Memo1.Lines.Add(re.MatchedText);
      Memo1.Lines.Add('-------------------');

      while re.MatchAgain do
      begin
        Memo1.Lines.Add(re.MatchedText);
        Memo1.Lines.Add('-------------------');
      end;
    end
    else
    begin
      Memo1.Lines.Add('Kein Treffer')
    end;

  except
    on E: Exception do
      Memo1.Lines.Add(E.ClassName+ ': '+ E.Message);
  end;
end;

end.

[/edit]

[liftoff]

Wow. Danke fur die ausführliche Untersuchung.:)
Ich möchte, dass sich das nur matcht, wenn die unter #11 beschriebenen Kriterien zutreffen.
Also nach {4: ein Umbruch, danach Zeilen mit Egal plus Umbruch und danach eine letzte Zeile mit einem -} am Anfang.

So ganz habe ich aber in der Tat den Zusammenhang mit dem Stack noch nicht ergründen können.

[MaBuSE]

Zitat:

Zitat von liftoff (Beitrag 1170712)

Wow. Danke fur die ausführliche Untersuchung.:)

Gern geschehen. Übrigens willkommen in der DP :dp:

Zitat:

Zitat von liftoff (Beitrag 1170712)

Ich möchte, dass sich das nur matcht, wenn die unter #11 beschriebenen Kriterien zutreffen.
Also nach {4: ein Umbruch, danach Zeilen mit Egal plus Umbruch und danach eine letzte Zeile mit einem -} am Anfang.

Dann solltest Du noch zusätzlich je einen Zeilenumbruch einfügen '/n'.

Delphi-Quellcode:

re.RegEx := '(\{4\:/n.*?/n-\})';

Zitat:

Zitat von liftoff (Beitrag 1170712)

So ganz habe ich aber in der Tat den Zusammenhang mit dem Stack noch nicht ergründen können.

Im Wesentlichen wird zwischen HEAP und STACK unterschieden. Auf Daten die auf den Stack gelegt werden kann man relativ schnell zugreifen, dafür ist die Stackgröße beschränkt. Auf Daten im Heap kann langsamer zugegriffen werden, dafür ist im Heap viel mehr Platz.

Parameter von Prozeduren und Funktionen werden auf dem Stack gespeichertund nach dem Ende der Funktion wieder freigegeben.
Bei einer Rekursion ruft sich eine Funktion selbst auf. Wenn eine Funktion sich z.B. 100 mal aufruft, dann wird auch 100 mal Stack für Parameter benötigt.

Ich hoffe das hilft Dir weiter.

[liftoff]

Nene. Stack und Heap, hab ich lieb. Damit kenne ich mich schon aus. 8-)

Nur den Zusammenhang zwischen greedy und lazy im Zusammenhang mit dem PCRE-Stack hab ich nicht verstanden.

Hier ein glaube ich altes Beispiel.

banane

b(an)+ liefert 'banan'

b(an)+? liefert der Faulheit wegen nur noch 'ban'

Hänge ich dem Ausdruck ein e an

b(an)+?e

liefert das 'banane'. Er ackert also den Match mit (an)+? zwei Mal durch.

Genauso verhält es sich mit meinem Ausdruck ganz oben. Nur statt 'an' eben einzelne Zeilen mit einem Umbruch am Ende.

Wieso liefert greedy einen stack overflow und lazy keinen. Die X Zeilen muss er in beiden Fällen durchlaufen.

Meinste statt /n vielleicht nicht eher \n ? :)
Statt \n nehme ich \r\n, also einen Windows-Umbruch #13#10.

[MaBuSE]

Zitat:

Zitat von liftoff (Beitrag 1170817)

Wieso liefert greedy einen stack overflow und lazy keinen. Die X Zeilen muss er in beiden Fällen durchlaufen.

Sorry, hab dich falsch verstanden.
In Deiner XE Ent. Version sind ja alle Quelltexte enthalten.
IN Projektoptionen Debug-DCUs anschalten und einfach mal in die Match Methode reindebuggen ;-)

Zitat:

Zitat von liftoff (Beitrag 1170817)

Meinste statt /n vielleicht nicht eher \n ? :)
Statt \n nehme ich \r\n, also einen Windows-Umbruch #13#10.

Stimmt :roll:

[Uwe Raabe]

Zitat:

Zitat von MaBuSE (Beitrag 1170822)

In Deiner XE Ent. Version sind ja alle Quelltexte enthalten.
IN Projektoptionen Debug-DCUs anschalten und einfach mal in die Match Methode reindebuggen ;-)

Die PCRE-Implementation liegt zwar als C-Source vor, wird aber von Delphi als vorcompilierte OBJ-Dateien (ohne Debug-Info) eingelinkt. Leider gestaltet sich das Debuggen so etwas schwieriger als gewohnt.

[ele]

Zitat:

Zitat von WladiD (Beitrag 1170636)

Zitat:

Zitat von ele (Beitrag 1170618)

Folgende RegEx funktioniert:

Code:

({4:\r\n(?:[^\r\n]*\r\n)*?-})

Ich habe keine Ahnung von SWIFT (zumindest nicht im Detail), aber der reguläre Ausdruck ist definitv nicht richtig.

- Geschweifte Klammern haben in pcre eine spezielle Bedeutung (Quantifizierung) und müssen daher escaped werden, wenn man sie matchen möchte
- Das Fragezeichen vor der Klammer ist auch fragwürdig, denn es ist ein Quantifizierer also ein Kürzel für {0,1} und ein vorhergehendes Char, Set oder Gruppe fehlt demnach

Du hast recht, es ist besser die geschweiften Klammern zu escapen. Trotzdem ist es eine absolut gültige RegEx:

Zitat:

Zitat von http://perldoc.perl.org/perlre.html

If a curly bracket occurs in any other context and does not form part of a backslashed sequence like \x{...} , it is treated as a regular character.

Zur aktuellen Diskussion:
Das debuggen von PCRE willst du dir nicht antun - selbst wenn der code in Delphi geschreiben wäre. Regular Expression Engines sind ein ziemlich komplizierte Dinger und die PCRE ist ein Monster. Da schreibst du lieber deinen eigenen Parser - das benötigt weniger Zeit.

[WladiD]

Zitat:

Zitat von ele (Beitrag 1170859)

Du hast recht, es ist besser die geschweiften Klammern zu escapen. Trotzdem ist es eine absolut gültige RegEx:

Zitat:

Zitat von http://perldoc.perl.org/perlre.html

If a curly bracket occurs in any other context and does not form part of a backslashed sequence like \x{...} , it is treated as a regular character.

Ja, du hast Recht, das habe ich im Nachhinein auch erfahren. Ich persönlich escape generell alle Zeichen, die irgendeine anderweitige Bedeutung im Ausdruck haben, so ist man auf der sicheren Seite. Vor allem wenn man den Punkt an sich matchen möchte, sollte man ihn tunlichst nicht vergessen zu escapen :lol:

Zitat:

Zitat von ele (Beitrag 1170859)

Zur aktuellen Diskussion:
Das debuggen von PCRE willst du dir nicht antun - selbst wenn der code in Delphi geschreiben wäre. Regular Expression Engines sind ein ziemlich komplizierte Dinger und die PCRE ist ein Monster. Da schreibst du lieber deinen eigenen Parser - das benötigt weniger Zeit.

Keine Software ist perfekt, aber die PCRE halte ich für eines der solidesten Projekte, die die IT-Branche zu bieten hat. Sodass man zuerst an der eigenen Expression zweifeln sollte, bevor man einen Bug in der PCRE vermutet.

[liftoff]

Also einen Bug habe ich auch nie vermutet.:wink:

Eingangs wollte ich nur die Stackbehandlung in pcre allgemein und an diesem Punkt jetzt die unterschiedliche Stackbehandlung von greedy- und nongreedy Ausdrücken ein wenig besser verstehen. Wenn nongreedy sich bei gleichem Matchergebnis ressourcenschonender verhält, wäre das ja auch mal eine wichtige Erkenntnis. :)