(Visual FoxPro) 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.

Note: This example requires Chilkat v11.1.0 or greater.

Chilkat ActiveX Downloads

ActiveX for 32-bit and 64-bit Windows

LOCAL loSbSubject
LOCAL i
LOCAL lcPattern
LOCAL loJson
LOCAL lnNumMatches

loSbSubject = CreateObject('Chilkat.StringBuilder')

* Create data that would cause a catastrophic backtrack with the regular expression "((a+)+$)"
i = 0
DO WHILE i < 500
    loSbSubject.Append("aaaaaaaaaaaaaaaaaaaa")
    i = i + 1
ENDDO
loSbSubject.Append("X")

lcPattern = "((a+)+$)"

loJson = CreateObject('Chilkat.JsonObject')
loJson.EmitCompact = 0

* Set a time limit to prevent a catastrophic backtrack..
* (Approx) 1 second time limit.
* This should fail:
lnNumMatches = loSbSubject.RegexMatch(lcPattern,loJson,1000)
IF (lnNumMatches < 1) THEN
    ? loSbSubject.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

    RELEASE loSbSubject
    RELEASE loJson
    CANCEL
ENDIF

* We shouldn't get here.
* The above data and regular expression should've caused a catastrophic backtrack.
? "numMatches: " + STR(lnNumMatches)
? loJson.Emit()

RELEASE loSbSubject
RELEASE loJson