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)”。

相关文章
|
2月前
|
Java
【Java报错】记录一次调用递归方法导致的 StackOverFlowError 及如何重构递归代码避免栈溢出
【Java报错】记录一次调用递归方法导致的 StackOverFlowError 及如何重构递归代码避免栈溢出
30 0
|
4月前
|
C++
[总结]c++ 内存泄露、内存溢出、内存越界和栈溢出
[总结]c++ 内存泄露、内存溢出、内存越界和栈溢出
|
算法
【基础篇】8 # 递归:如何避免出现堆栈溢出呢?
【基础篇】8 # 递归:如何避免出现堆栈溢出呢?
186 0
|
Java
编写一个程序,它能导致JVM抛出一个OutOfMemoryError,然后捕获和处理这个异常
编写一个程序,它能导致JVM抛出一个OutOfMemoryError,然后捕获和处理这个异常
168 0
记一次C栈溢出
今天与大家分享的一次堆栈溢出的调试过程,废话少说直接看代码。
|
Java 编译器
Java异常处理:如何写出“正确”但被编译器认为有语法错误的程序
Java异常处理:如何写出“正确”但被编译器认为有语法错误的程序
Java异常处理:如何写出“正确”但被编译器认为有语法错误的程序
|
Java
Java内存溢出OutOfMemoryError的产生与排查
在java的虚拟机异常中,有两个异常是大家比较关心的,一个是StackOverflowError,另一个是OutOfMemoryError。今天我们就来看看OutOfMemoryError是怎么产生的,以及如何去排查这个异常。
732 0
Java内存溢出OutOfMemoryError的产生与排查
|
Web App开发 JavaScript 前端开发