从一个正则表达式造成的StackOverflowError说起
? ? ?现有一系统上有个这样的功能：对一个HTML文件中的所有链接地址后面添加一个特定的参数，如abc=123。已有的实现方法为通过正则表达式"(<a)(\\S|\\s)*?(</a>)"匹配到该文件中的所有链接地址，然后逐个对匹配到的链接地址进行处理，包含解析出href属性值，再添加指定的参数等，故事也就从"(<a)(\\S|\\s)*?(</a>)"这个表达式开始了。
? ? ?测试的时候文件中有个链接带了很多参数，导致这个链接地址比较长，执行正则匹配的时候就抛出了StackOverflowError错误。通过错误日志，可以很快定位到是这个正则表达式匹配造成的该问题，但这行正则表达式为什么会导致栈溢出呢？从错误现象分析，这个线程执行的时候使用的规模空间超出了jvm启动时设置的XSS大小，所以治标的办法就是把XSS调大点，比如设置为512K或者1Ｍ，甚至更大。当然这个要结合系统实际情况的，因为调大该参数就意味着启动每个线程分配的内存变大了，会直接导致可创建的线程后变少，甚至系统启动不了。???????造成该栈溢出更本质的原因是什么呢？现象中可以判断出来是正则匹配的时候造成，所以也就自然从正则匹配这过程开始说起。? ? ??正则表达式引擎分成两类，一类称为DFA（确定性有穷自动机），另一类称为NFA（非确定性有穷自动机）。两类引擎要顺利工作，都必须有一个正则式（即上文的"(<a)(\\S|\\s)*?(</a>)"）和一个文本串（即上文中待处理的HTML文件内容）。DFA捏着文本串去比较正则式，看到一个子正则式，就把可能的匹配串全标注出来，然后再看正则式的下一个部分，根据新的匹配结果更新标注。而NFA是捏着正则式去比文本，吃掉一个字符，就把它跟正则式比较，匹配就记下来，然后接着往下干。一旦不匹配，就把刚吃的这个字符吐出来，一个个的吐，直到回到上一次匹配的地方。??????DFA与NFA机制上的不同带来5个影响：??????1. DFA 对于文本串里的每一个字符只需扫描一次，比较快，但特性较少；NFA要翻来覆去吃字符、吐字符，速度慢，但是特性丰富，所以反而应用广泛，当今主要的正则表达式引擎，如Perl、Ruby、Python的re模块、Java和.NET的regex库，都是NFA的。??????2. 只有NFA才支持lazy和backreference等特性；??????3. NFA急于邀功请赏，所以最左子正则式优先匹配成功，因此偶尔会错过最佳匹配结果；DFA则是“最长的左子正则式优先匹配成功”。??????4. NFA缺省采用greedy量词；??????5. NFA可能会陷入递归调用的陷阱而表现得性能极差。??? ? ?java.util.regex包使用NFA作为模式匹配引擎，本质上使用回缩。通常情况下，并非只有一种方式在给定的字符串上使用正则表达式，因此模式匹配引擎会尝试所有情况，直到它宣布失败。?????由于日常遇到的正则表达式引擎全都是NFA，所以缺省都采用greedy量词。Greedy量词的意思不难理解，就是对于/.*/、/w+/这样的“重复n”次的模式，以贪婪方式进行，尽可能匹配更多字符，直到不得以罢手为止。? ? ?举一个例子，以 /<.*>/ 模式匹配'<book> <title> Perl Hacks </title> </book>'文本，匹配结果不是'<book>'，而是'<book> <title> Perl Hacks </title> </book>'。原因就在于NFA引擎以贪婪方式执行“重复n次”的命令。?????NFA的模型是以正则式为导向，拿着正则式吃文本。在上面的例子里，当它拿着/.*/这个正则式去吃文本的时候，缺省情况下它就这么一路吃下去，即使碰到'>'字符也不罢手——既然 /./ 是匹配任意字符，'>'当然也可以匹配！所以就尽管吃下去，直到吃完遇到结尾（包括t字符）也不觉得有什么不对。这个时候它突然发现，在正则表达式最后还有一个'>'，于是慌了神，知道吃多了，于是就开始一个字符一个字符的往回吐，直到吐出倒数第二个字符'>'，完成了与正则式的匹配，才长舒一口气，向上汇报，匹配字符串从第一个字符'<'开始，到倒数第二个字符'>'结束，即'<book> <title> Perl Hacks </title> </book>'。??????Greedy量词的行为有时确实是用户所需要的，有时则不是。比如在这个例子里，用户可能实际上想得到的是'book'串。怎么办呢？这时候lazy量词就派上用场了。把模式改为/<.*?>/就可以得到'book'。这个加在'*'号后面的'?'把greedy量词行为变成lazy量词行为，从而由尽量多吃变为尽量少吃，只要吃到一个'>'立刻停止。?问号在正则表达式里用途最广泛，这里是很重要的一个用途。??? ? ?基于上面的例子理解下回缩（backtracking?），当NFA发现自己吃多了，一个一个往回吐，边吐边找匹配，这个过程叫做backtracking。由于存在这个过程，在NFA匹配过程中，特别是在编写不合理的正则式匹配过程中，文本被反复扫描，效率损失是不小的。明白这个道理，对于写出高效的正则表达式很有帮助。? ? ?对于回缩，可以考虑下面这个例子：? ? ?正则表达式是“sc(ored|ared|oring)x”，输入字符串是“scared”。?????首先引擎会寻找“sc”，由于在输入字符串的起始两个字符，因此会立即找到。然后，它会从输入字符串的第三个字符开始尝试匹配“ored”。没有匹配项，它就回到第三个字符，尝试“ared”。找到匹配，于是它继续向前，尝试匹配“x”。不能找到匹配，它将返回第三个字符，寻找“oring”。仍然没有匹配，于是它就返回到输入字符串的第二个字符，开始寻找另外一个“sc”。一直到达输入字符串的结束，它将宣布失败。? ? ?通过上面的例子，可以看到NFA如何使用回缩进行模式匹配的，同时也会发现回缩存在的一个问题。甚至在上面十分简单的例子中，引擎为了将输入字符串匹配到正则表达式不得不回退数次。不难想象，如果回缩使失去控制，将会对应用程序的性能发生什么样的影响。优化正则表达式的一个重要部分就是最小化回缩的数量。? ? ?由于回缩，在现实场景中正则表达式有时候会遇到花费数小时完成匹配的情况。更惨的是，引擎会花费比匹配成功更长的时间声明正则表达式不匹配输入字符串。牢记这个重要的事实。当你想要测试正则表达式的速度时，使用其不能匹配的字符串进行测试。其中，特别是使用几乎匹配的字符串，因为它们会消耗最长的时间。??????下面是一些优化正则表达式的简单方法：?????1.如果在程序中多次使用同一个正则表达式，一定要用Pattern.compile()编译，代替直接使用Pattern.matches()。如果一次次对同一个正则表达式使用Pattern.matches()，例如在循环中，没有编译的正则表达式消耗比较大。因为matches()方法每次都会预编译使用的表达式。另外，记住你可以通过调用reset()方法对不同的输入字符串重复使用Matcher对象。? ? ?2.留意选择（Beware of alternation）。类似“(X|Y|Z)”的正则表达式有降低速度的坏名声，所以要多留心。首先，考虑选择的顺序，那么要将比较常用的选择项放在前面，因此它们可以较快被匹配。另外，尝试提取共用模式。例如将“(abcd|abef)”替换为“ab(cd|ef)“，后者匹配速度较快，因为NFA会尝试匹配ab，如果没有找到就不再尝试任何选择项（在当前情况下，只有两个选择项。如果有很多选择项，速度将会有显著的提升），选择的确会降低程序的速度。? ? ?3.获取每次使用引起小损失的分组。如果你实际并不需要获取一个分组内的文本，那么就使用非捕获分组。例如使用“(?:X)”代替“(X)”。?? ? ?另外，有时java库regex包中的Pattern类会抛出StackOverflowError。这是JDK已知bug #5050507的表现，它自从Java 1.4就存在于java.util.regex包中。这个bug仍然存在，因为它是“won't fix”的状态。这个错误的出现是因为Pattern类把一个正则表达式编译为一个用来寻找匹配的小程序。这个程序被递归调用，有时太多的递归就会导致该错误的出现，更多细节请参考bug描述。?? ? ?归纳起来，对于正则匹配时出现StackOverflowError的情况，如果对正则表达式不熟悉，最简单易行的做法莫过于将JVM的XSS参数适当调大。但这样并不能根本上解决问题，只能适当缓解，同时因为每个线程分配的内存增大，对系统很可能有影响，要慎重。根本的办法还是对正则表达式做好优化，但这趟混水有多深就只有试过才知道了，始终是不大好测试，难怪会有这么句老话“您有一个问题，用正则表达式解决。那您就有两个问题了。”?参考资料：优化Java中的正则表达式：http://blog.csdn.net/mydeman/article/details/1800636Java正则与栈溢出：http://daimojingdeyu.iteye.com/blog/385304? ? ?
