How to improve (eliminate too many tokens?) slow regexp in JavaScript?

Question

I have function to bold part of line before colon.

//Fast regex (time: 0) var colonRegex = /^[^*:\n]+:/gm;

and

//Slow regex (time: 139) Limit by 10 words //var colonRegex = /^([^*:\n ]+ ?){1,10}:/gm; // I have issue with it when I want to apply replace to tens of divs (it freezes chrome) var bolded = str.replace(colonRegex, function(match) { return "<b>"+match+"</b>"; });

you can test it on jsfiddle: http://jsfiddle.net/damg7zuk/4/

Where I do a mistake? I can make word limitation inside the callback. Can it be done better in regex itself? Thank you for your trick.

Why are you using a callback? Can't you use .replace(colonRegex,"<b>$1</b>");? (If you add some parentheses to the regex: /^([^*:\n]+:)/gm.) If I add the slow regex to your fiddle it runs in "Time: 34" and doesn't freeze Chrome. — nnnnnn
– nnnnnn, Commented Dec 5, 2014 at 12:57
The problem is that you get a catastrofic backtracking. When you have a line with more than ten words before the colon the pattern will first match the ten words. Then it finds that the colon at the end doesn't match, so it starts backtracking one character at a time and reevaluating the pattern over an over until it gets it down to a single word where it can determine that the pattern doesn't match at all on that line. — Guffa
– Guffa, Commented Dec 5, 2014 at 13:12

Bergi · Accepted Answer · 2014-12-05 15:21:36Z

Your /^([^*:\n ]+ ?){1,10}:/gm regex exhibits catastrophic backtracking: You're nesting the + and the {1,10} repetition with (possibly) nothing in between. Fix this by making the blank that separates the groups compulsory to match:

/^([^*:\n ]+ ){0,9}[^*:\n ]+:/gm # ^

or

/^[^*:\n ]+( [^*:\n ]+){0,9}:/gm

websky · Accepted Answer · 2014-12-05 15:02:25Z

js level can be so:

var bolded = str.replace(colonRegex, function(match) { if (match.indexOf(".") > 0){ match1 = match.slice(0,(match.indexOf(".")+1)); match2 = match.slice(match.indexOf(".")+1); match = match1+"<b>"+match2+"</b>"; return match; } return "<b>"+match+"</b>"; });

vks · Accepted Answer · 2014-12-05 13:35:36Z

0

^(?:(?=([^*:\n ]+[ ]?))\1){0,10}:

Try this.See demo.

https://regex101.com/r/kX9kT1/1

answered Dec 5, 2014 at 13:35

vks

68.1k11 gold badges96 silver badges132 bronze badges

Collectives™ on Stack Overflow

How to improve (eliminate too many tokens?) slow regexp in JavaScript?

3 Answers 3

Comments

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Related