StackOverflowError:正则表达式栈溢出错误-阿里云开发者社区

开发者社区> 开发与运维> 正文

StackOverflowError:正则表达式栈溢出错误

简介: Some people, when confronted with a problem, think "I know, I'll use regular expressions." Now they have two problems. “ 如果你有一个问题,用正则表达式解决,那么你现在就有两个问题了。

Some people, when confronted with a problem, think "I know, I'll use regular expressions." Now they have two problems.
“ 如果你有一个问题,用正则表达式解决,那么你现在就有两个问题了。”

问题

最近碰巧遇到了一个使用正则表达式错误!!

我们系统是基于Java语言开发的,其中使用的是JDK8自带的java.util.regex.Pattern类实现正则表达式匹配的。

系统中有一个正则表达式如下。

\{(.|\n)*?\}

其目的是用来区分Json风格字符串与其它字符串的。

但在实际使用中,当传入一个较长的Json字符串时,却发生了如下的错误。

Exception in thread "main" java.lang.StackOverflowError
    at java.util.regex.Pattern$LazyLoop.match(Pattern.java:4845)
    at java.util.regex.Pattern$GroupTail.match(Pattern.java:4719)
    at java.util.regex.Pattern$BranchConn.match(Pattern.java:4570)
    at java.util.regex.Pattern$CharProperty.match(Pattern.java:3779)
    at java.util.regex.Pattern$Branch.match(Pattern.java:4606)
    at java.util.regex.Pattern$GroupHead.match(Pattern.java:4660)
    at java.util.regex.Pattern$LazyLoop.match(Pattern.java:4849)
    at java.util.regex.Pattern$GroupTail.match(Pattern.java:4719)
    at java.util.regex.Pattern$BranchConn.match(Pattern.java:4570)
    at java.util.regex.Pattern$CharProperty.match(Pattern.java:3779)
    at java.util.regex.Pattern$Branch.match(Pattern.java:4606)
    at java.util.regex.Pattern$GroupHead.match(Pattern.java:4660)
    at java.util.regex.Pattern$LazyLoop.match(Pattern.java:4849)
    at java.util.regex.Pattern$GroupTail.match(Pattern.java:4719)
    at java.util.regex.Pattern$BranchConn.match(Pattern.java:4570)
    at java.util.regex.Pattern$CharProperty.match(Pattern.java:3779)
    at java.util.regex.Pattern$Branch.match(Pattern.java:4606)
    at java.util.regex.Pattern$GroupHead.match(Pattern.java:4660)
    ...
    ...(非常多行)

分析

通过观察,我们知道这是一个虚拟机 栈溢出 错误。

Java语言中每个线程(Thread)的栈大小是有限制的,每一次函数调用都会生成一个栈帧(Frame),占用一定的栈空间,当栈空间被消耗完虚拟机就会报出StackOverflowError。

再仔细地观察,发现栈信息中显示调用层次非常多,而且类名与代码行重复出现,这意味着栈帧是由递归调用产生的。

到这里,问题发生的原因己经基本可以确定了。

在Java中正则表达式的产生了递归调用,而传入的长Json字符串导致函数调用层次太多,超过虚拟机预设的栈空间,因此,出现了StackOverflowError。

追根溯源

然而,以上的解释纯粹是现象+经验的推断,显然不能满足我的好奇心。

所以,我略略又研究了一下Java正则表达式部分功能的实现。

Java语言在做正则表达式匹配时,首先要进行编译。

使用java.util.regex.Pattern类的compile方法,编译的过程相当于把正则表达式

\{(.|\n)*?\}

转换类似下图的数据结构。


img_817ac5f6a55f47ef1a721f42eb392e93.png

实际编译后的对象结构更复杂些,如下图。


img_3e873d4d3da1b8e59ee7ba18734c83b6.png

上图每个节点的类型都继承自Pattern$Node类,实现了match方法(即使没有重写方法,也有默认实现)。

当进行字付串匹配时,java.util.regex.Matcher的matches方法会调用第一个节点的match方法,继而形成递归调用链。

正如上面编译后的表达式,有一个以LazyLoop为启始的循环引用,当字符串的每个字符进行匹配时,都产生如下的栈结构。

    at java.util.regex.Pattern$GroupTail.match(Pattern.java:4719)
    at java.util.regex.Pattern$BranchConn.match(Pattern.java:4570)
    at java.util.regex.Pattern$CharProperty.match(Pattern.java:3779)
    at java.util.regex.Pattern$Branch.match(Pattern.java:4606)
    at java.util.regex.Pattern$GroupHead.match(Pattern.java:4660)
    at java.util.regex.Pattern$LazyLoop.match(Pattern.java:4849)

由于传入的字符串很长,因此递归调用的层次太多,很快便耗尽线程的栈空间(可以用-Xss配置),接着虚拟机就报出了StackOverflowError错误。

改进

知道了问题,我们着手进行改进。

修改正则表达式如下。

\{[\w\W]*\}

这样,编译后的表达式结构变成为。


img_659ae5f167ba85756822fb1a34d7ee49.png

而在Pattern$Curly中的match方法使用的是while循环查找而非递归,因此,不会造成栈溢出。

总结

关于正则表达式及其优化,讲解的比较好的链接如下,这里不再赘述。

Java 正则表达式 StackOverflowError 问题及其优化

其中有一点与我这个场景是有关系的。

留意选择(Beware of alternation)
类似“(X|Y|Z)”的正则表达式有降低速度的坏名声,所以要多留心。首先,考虑选择的顺序,那么要将比较常用的选择项放在前面,因此它们可以较快被匹配。另外,尝试提取共用模式;例如将“(abcd|abef)”替换为“ab(cd|ef)”。后者匹配速度较快,因为NFA会尝试匹配ab,如果没有找到就不再尝试任何选择项。……

这一点其实不难理解,表达式编译后 (X|Y|Z) 其实是一个数组,从前到后依次进行匹配。

因此,在Java中写正则表达式最重要的还是:

减少分组与嵌套
如果你实际并不需要获取一个分组内的文本,那么就使用非捕获分组。例如使用“(?:X)”代替“(X)”。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
开发与运维
使用钉钉扫一扫加入圈子
+ 订阅

集结各类场景实战经验,助你开发运维畅行无忧

其他文章