CODEWITHSUNDEEP
javascriptregexcrash
NoBrainer
NoBrainer

Reputation: 5940

Why does this Javascript match() function Crash My Browser?

WHAT I DO:

WHAT I NOTICE:

EXAMPLE STRING THAT CRASHES FIREFOX

// Note that this is not wrapped in parentheses,
// since it is two separate sets of nested parentheses
var test = "(the OR (and) OR (and) OR (and)) AND ((to) OR (to) OR (to))";

BACKGROUND

CODE

isWrappedInParens = function(str){
    if(_.isNull(str)) {
        return false;
    }
    str = str.trim();

    var pattern = /^[(](([(][^()]+[)]|[^()]+)|[(]([(][^()]+[)]|[^()]+)+[)])+[)]$/;

    var matchesPattern;
    try{
        matchesPattern = str.match(pattern) || null; //CRASH POINT!!!!!!!!!!!
    }catch(err){
        return false; //Note that no error is ever caught from freezing
    }

    var isWrapped = !_.isUndefined(matchesPattern) && !_.isNull(matchesPattern);
    return isWrapped;
}

WHERE THE REGEX CAME FROM:

// Atoms, building blocks for the expressions
var parenAtom = "[(][^()]+[)]";
var nonParenAtom = "[^()]+";

// Expressions, building blocks for the final regular expression
var baseCase = "(" + parenAtom + "|" + nonParenAtom + ")";
var nestedCase = "[(]_base_[)]"
    .replace("_base_", baseCase);

// Regular Expression
var wholeCase = "^[(](_base_|_nested_)+[)]$"
    .replace("_base_", baseCase)
    .replace("_nested_", nestedCase);
var pattern = new RegExp(wholeCase, "");

Upvotes: 1

Views: 933

Answers (1)

Pointy
Pointy

Reputation: 413747

From my comment:

Looking through the Firefox bug database, there have been many regular expression bugs found and categorized loosely as "exponential behavior" bugs. Most of them have been fixed in the newer versions of the browser.

In this bug there are a couple of comments from Brendan Eich about the issue, and he lists several other bugs (some pretty old). Another comment there alludes to an "overhaul in regular expression" in Firefox 4, suggesting that many changes occurred as far back as that.

Upvotes: 1

Related Questions