Zig 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.

Zig

const std = @import("std");
const chilkat = @import("chilkat");

pub fn main(init: std.process.Init) !void {
    const alloc = init.arena.allocator();

    const sb_subject = try chilkat.StringBuilder.init();
    defer sb_subject.deinit();

    // Create data that would cause a catastrophic backtrack with the regular expression "((a+)+$)"
    var i: i32 = 0;
    while (i < 500) {
        sb_subject.append("aaaaaaaaaaaaaaaaaaaa") catch {};
        i = i + 1;
    }

    sb_subject.append("X") catch {};

    const pattern = "((a+)+$)";

    const json = try chilkat.JsonObject.init();
    defer json.deinit();
    json.setEmitCompact(false);

    // Set a time limit to prevent a catastrophic backtrack..
    // (Approx) 1 second time limit.
    // This should fail:
    const num_matches = sb_subject.regexMatch(pattern, json, 1000);
    if (num_matches < 1) {
        std.debug.print("{s}\n", .{try sb_subject.getLastErrorText(alloc)});

        //     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

        return;
    }

    // We shouldn't get here.
    // The above data and regular expression should've caused a catastrophic backtrack.
    std.debug.print("numMatches: {d}\n", .{num_matches});
    std.debug.print("{s}\n", .{try json.emit(alloc)});
}