为什么此代码会导致Chrome窒息？ [英] Why does this code cause Chrome to choke?

问题描述

我试图在我的应用程序中调试一个问题，我已经缩小到涉及导致Chrome呛的正则表达式的特定情况！在Firefox中尝试相同的代码工作正常。另外，如果我减少我的样本文本运行正则表达式也可以。

那么给出了什么？

以下是jsfiddle： http://jsfiddle.net/XWKRb/1/
（根本不能初始化，因为如果您获得与我相同的结果，Chrome会窒息）

我在jsfiddle中放入的代码是：

  var rgx = / ^（\ d +（[，|;]？\d *））* $ /; 
 var sample ='40162690,40162755,40162691,40168355,40168357,40162726,40162752,40162729,40428707,40162740,40162546'; 
 alert（Test is+ rgx.test（sample））; 
  

也许有更好的方法来写我的正则表达式来避免这个问题？目标是正则表达式应该捕获一串由逗号或分号分隔的数字。 你有一个灾难性的回溯的经典案例：

  ^（\d +（[，|;]？\ d *））* $ 
 ^ ^ ^ ^ 
 | | | ----零次或多次重复组
 | | -------零个或多个数字
 | ----------零或一个逗号，管道或分号
 -----------------一个或多个数字
  

包含一个重复组，其中包含可选元素，其中一个重复其自身。现在忽略分隔符，你基本上是正则表达式

  ^（\ d + \d *）* $ 
  

这会导致您的正则表达式在最坏的情况下需要检查的指数数量的排列。

一旦在字符串中找到了除允许的字符之外的另一个字符（例如您的示例中的空格），则正则表达式必须失败 - 但需要使用引擎的年龄来计算出结果。一些浏览器检测到这种失控的正则表达式匹配，但Chrome似乎想要这样做。

为了说明这一点，在 RegexBuddy 显示以下内容：

 输入确定不匹配
 1,1X 23 
 12,21X 119 
 123,321X 723 
 1234,4321X 4,743 
 12345,54321X 31,991 
 123456,654321X 217,995 
 1234567,7654321X尝试在1,000,000步后中止
  

I am trying to debug a problem in my app which I have narrowed down to a particular situation involving a regular expression which causes Chrome to choke! Trying the same code in Firefox works fine. Also if I reduce my 'sample' text to run the regex on it works too.

So what gives?

Here is the jsfiddle: http://jsfiddle.net/XWKRb/1/ (Which will fail to initialize at all because Chrome would choke if you are getting the same result as I am)

The code I have put in the jsfiddle is:

var rgx = /^(\d+([,|;]?\d*))*$/;
var sample = '40162690,40162755,40162691,40168355,40168357,40162726,40162752,40162729,40428707 ,40162740,40162546';
alert("Test is "+rgx.test(sample));

Maybe there is a better way to write my regular expression to avoid the issue? The goal is the regular expression should catch a string of numbers which are separated by comma or semi-colon.

解决方案

You have a classic case of catastrophic backtracking:

^(\d+([,|;]?\d*))*$
    ^      ^  ^  ^
    |      |  |  ---- zero or more repetitions of the group 
    |      |  ------- zero or more digits
    |      ---------- zero or one comma, pipe or semicolon
    ----------------- one or more digits

contains a repeated group which contains optional elements, one of which is repeated itself. Ignoring the separators for now, you have essentially the regex

^(\d+\d*)*$

That leads to an exponential number of permutations your regex has to check in the worst case.

As soon as another character besides the allowed characters is found in your string (like a space in your example), the regex must fail - but it takes the engine ages to figure this out. Some browsers detect such runaway regex matches, but Chrome appears to want to ride this out.

To illustrate this, testing your regex in RegexBuddy shows the following:

Input             Steps to determine a non-match
1,1X                   23
12,21X                119
123,321X              723
1234,4321X          4,743
12345,54321X       31,991
123456,654321X    217,995
1234567,7654321X  attempt aborted after 1,000,000 steps

这篇关于为什么此代码会导致Chrome窒息？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！