Delphi DLL Requires Chilkat v11.1.0+

Regular Expression Catastrophic Backtrack

See more Regular Expressions Examples

This example demonstrates how adding a processing time limit prevents a catastrophic backtrack.

Catastrophic backtracking in regular expressions occurs when a poorly constructed pattern causes the regex engine to try an exponential number of possibilities, especially on non-matching input. This leads to extremely slow performance or even a program hang.

Example:

(a+)+$

Applied to:

aaaaaaaaaaaaaaaaaaaaaab

The regex engine tries many combinations of grouping a+ inside another +, looking for a way to match the whole string, but it never matches due to the final b. The nested quantifiers (+ inside +) are what trigger the backtracking explosion.

How to prevent it:

• Avoid nested quantifiers like (a+)+
• Use atomic groups or possessive quantifiers if available
• Consider more efficient regex design or a parser

Catastrophic backtracking is especially dangerous when regex patterns are applied to user-controlled input.

Delphi DLL

var
sbSubject: HCkStringBuilder;
i: Integer;
pattern: PWideChar;
json: HCkJsonObject;
numMatches: Integer;

begin
sbSubject := CkStringBuilder_Create();

//  Create data that would cause a catastrophic backtrack with the regular expression "((a+)+$)"
i := 0;
while i < 500 do
  begin
    CkStringBuilder_Append(sbSubject,'aaaaaaaaaaaaaaaaaaaa');
    i := i + 1;
  end;

CkStringBuilder_Append(sbSubject,'X');

pattern := '((a+)+$)';

json := CkJsonObject_Create();
CkJsonObject_putEmitCompact(json,False);

//  Set a time limit to prevent a catastrophic backtrack..
//  (Approx) 1 second time limit.
//  This should fail:
numMatches := CkStringBuilder_RegexMatch(sbSubject,pattern,json,1000);
if (numMatches < 1) then
  begin
    Memo1.Lines.Add(CkStringBuilder__lastErrorText(sbSubject));

    //  	We should get an error such as the following:

    //  	ChilkatLog:
    //  	  RegexMatch:
    //  	    ChilkatVersion: 11.1.0
    //  	    regex_match:
    //  	      timeoutMs: 1000
    //  	      Exceeded regular expression match limit.
    //  	      elapsedMs: Elapsed time: 797 millisec
    //  	      num_matches: -1
    //  	    --regex_match
    //  	  --RegexMatch
    //  	--ChilkatLog

    Exit;
  end;

//  We shouldn't get here.
//  The above data and regular expression should've caused a catastrophic backtrack.
Memo1.Lines.Add('numMatches: ' + IntToStr(numMatches));
Memo1.Lines.Add(CkJsonObject__emit(json));

CkStringBuilder_Dispose(sbSubject);
CkJsonObject_Dispose(json);