Pascal (Lazarus/Delphi)

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.

Pascal (Lazarus/Delphi)

program ChilkatDemo;

// Demonstrates using the Chilkat Pascal wrapper via the C bridge DLL.
// Builds as a console application under Lazarus (FPC) or Delphi.

{$IFDEF FPC}
  {$MODE DELPHI}
{$ENDIF}
{$APPTYPE CONSOLE}

uses
  {$IFDEF UNIX}
  cthreads,
  {$ENDIF}
  SysUtils,
  CkDllLoader,
  Chilkat.JsonObject,
  Chilkat.StringBuilder;

// ---------------------------------------------------------------------------

procedure RunDemo;
var
  sbSubject: TStringBuilder;
  i: Integer;
  pattern: string;
  json: TJsonObject;
  numMatches: Integer;

begin
  sbSubject := TStringBuilder.Create;

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

  sbSubject.Append('X');

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

  json := TJsonObject.Create;
  json.EmitCompact := False;

  //  Set a time limit to prevent a catastrophic backtrack..
  //  (Approx) 1 second time limit.
  //  This should fail:
  numMatches := sbSubject.RegexMatch(pattern,json,1000);
  if (numMatches < 1) then
    begin
      WriteLn(sbSubject.LastErrorText);

      //  	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.
  WriteLn('numMatches: ' + numMatches);
  WriteLn(json.Emit());


  sbSubject.Free;
  json.Free;

end;

// ---------------------------------------------------------------------------

begin

  try
    RunDemo;
  except
    on E: Exception do
      WriteLn('Unhandled exception: ', E.ClassName, ': ', E.Message);
  end;

  WriteLn;
  {$IFDEF MSWINDOWS}
  WriteLn('Press Enter to exit...');
  ReadLn;
  {$ENDIF}
end.