多行字符串文字的正则表达式生成`StackOverflow Error`

2022-04-12 00:00:00 regex stack-overflow scala java

我希望匹配用三个"引号括起来的字符串,这些字符串可能包含换行符,并且除开头和结尾外不包含任何"""子字符串。

有效示例:

"""foo
bar "baz" blah"""

无效示例:

"""foo bar """ baz"""

我尝试使用以下正则表达式(作为JavaString文本):

"(?m)"""(?:[^"]|(?:"[^"])|(?:""[^"]))*""""

而且它似乎在简短的例子中起作用。但是,在较长的示例中,比如包含1000行hello world的字符串,它会给我一个StackOverflowError

复制错误的Scala代码段

import java.util.regex.{Pattern, Matcher}

val text = """ * 3 + "hello world 
" * 1000 + """ * 3
val p = Pattern.compile("(?m)"""(?:[^"]|(?:"[^"])|(?:""[^"]))*"""")
println(p.matcher("""" foo bar baz 
 baz bar foo """").lookingAt())
println(p.matcher(text).lookingAt())

(注意:本地测试,SCastie超时;或者可能将1000减少到更小的数字?)。

产生相同错误的Java代码段

import java.util.regex.Pattern;
import java.util.regex.Matcher;

class RegexOverflowMain {
  public static void main(String[] args) {
    StringBuilder bldr = new StringBuilder();
    bldr.append(""""");
    for (int i = 0; i < 1000; i++) {
      bldr.append("hello world 
");
    }
    bldr.append(""""");
    String text = bldr.toString();
    Pattern p = Pattern.compile("(?m)"""(?:[^"]|(?:"[^"])|(?:""[^"]))*"""");
    System.out.println(p.matcher("""" foo bar baz 
 baz bar foo """").lookingAt());
    System.out.println(p.matcher(text).lookingAt());
  }
}

问题

您知道如何使此"堆栈安全"吗?即,是否有人可以找到接受相同语言,但在提供给Java regex API时不会生成StackOverflowError的正则表达式?

我不在乎解决方案是使用Scala还是Java(或其他任何语言),只要使用相同的底层Java regex库即可。


解决方案

解决方案使用负向前瞻基本上查找以"""开头、"""结尾且不包含"""

内容的字符串

作为普通正则表达式:^"""((?!""")[sS])*"""$

AS Java转义正则表达式:"^"""((?!""")[\s\S])*"""$"

sS包括换行符(基本为.+换行符或.带单行标志)

使用时不应使用MULTLINE标志,以便^$匹配字符串的开始和结束,而不是行的开始和结束

否则:

""" ab """abc""" abc """

将匹配

我还将此作为如何排除""":Regular expression to match a line that doesn't contain a word?

的参考

相关文章