Регулярное выражение для многострочных строковых литералов создает `StackOverflowError` - PullRequest
Новая
       6

Регулярное выражение для многострочных строковых литералов создает `StackOverflowError`

0 голосов
/ 06 июня 2018

Я хочу сопоставить строки, заключенные в тройные " -цитаты, которые могут содержать разрывы строк и не содержат """ -подстрок, кроме как в самом начале и в самом конце.

Допустимый пример: 

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

Неверный пример: 

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

Я попытался использовать следующее регулярное выражение (как Java String литерал): 

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

икажется, работает на коротких примерах.Однако в более длинных примерах, например, в строке, состоящей из тысячи строк с hello world, он дает мне StackOverflowError.

фрагмент Scala для воспроизведения ошибки 

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

val text = "\"" * 3 + "hello world \n" * 1000 + "\"" * 3
val p = Pattern.compile("(?m)\"\"\"(?:[^\"]|(?:\"[^\"])|(?:\"\"[^\"]))*\"\"\"")
println(p.matcher("\"\"\" foo bar baz \n 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 \n");
    }
    bldr.append("\"\"\"");
    String text = bldr.toString();
    Pattern p = Pattern.compile("(?m)\"\"\"(?:[^\"]|(?:\"[^\"])|(?:\"\"[^\"]))*\"\"\"");
    System.out.println(p.matcher("\"\"\" foo bar baz \n baz bar foo \"\"\"").lookingAt());
    System.out.println(p.matcher(text).lookingAt());
  }
}

Вопрос

Любая идея, как сделать этот "стек безопасным", т.е. может ли кто-нибудь найти регулярное выражение, принимающее тот же язык, но не выдающее StackOverflowError при подаче наJava regex API?

Мне все равно, будет ли решение в Scala или Java (или где-либо еще), если используется одна и та же базовая библиотека Java regex.

Ответы [ 2 ]

0 голосов
/ 06 июня 2018

Полный ответ ниже оптимизирует производительность регулярных выражений, но для предотвращения переполнения стека, в качестве простого решения, просто сделайте повторяющуюся группу притяжательным .

Не притяжательные повторяющиеся группы с необходимостью выборарекурсивные вызовы, чтобы разрешить возврат.Устранение этой проблемы решает проблему, поэтому просто добавьте + после *:

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

Также обратите внимание, что если вы хотите сопоставить весь ввод, вынужно позвонить matches(), а не lookingAt().

Повышение производительности

Примечание: быстрый тест производительности показал, что это будет более чем в 6 раз быстрее , чем регулярное выражение в ответе по x4rf41 .

Вместо совпадения с одним из

  • Не цитата: [^\"]
  • Ровно одна цитата: (?:\"[^\"])
  • Ровно две цитаты: (?:\"\"[^\"])

inцикл, сначала сопоставьте все до цитаты.Если это одинарная или двойная кавычка, но не тройная, сопоставьте 1-2 кавычки, затем все до следующей кавычки, при необходимости повторите.Наконец, сопоставьте окончательную тройную кавычку.

Это сопоставление является окончательным, поэтому сделайте повторы притяжательными.Это также предотвращает переполнение стека в случае, если на входе есть много встроенных кавычек. 

"{3}          match 3 leading quotes
[^"]*+        match as many non-quotes as possible (if any) {possesive}
(?:           start optional repeating group
   "{1,2}       match 1-2 quotes
   [^"]++       match one or more non-quotes (at least one) {possesive}
)*+           end optional repeating group                  {possesive}
"{3}          match 3 trailing quotes

Поскольку вы не используете ^ или $, нет необходимости в (?m) ( MULTILINE )

в виде строки Java:

"\"{3}[^\"]*+(?:\"{1,2}[^\"]++)*+\"{3}"

0 голосов
/ 06 июня 2018

Решение, использующее отрицательный прогноз, чтобы найти строку, начинающуюся с """ и заканчивающуюся """ и содержащую содержимое, которое не включает """

в качестве простого регулярного выражения: ^"""((?!""")[\s\S])*"""$

Поскольку Java избежало регулярного выражения: "^\"\"\"((?!\"\"\")[\\s\\S])*\"\"\"$ "

\s\S включает разрыв строки (в основном это . + перевод строки или . с однострочным флагом)

Это следует использовать без многострочного флага, чтобы ^ и $ соответствовали началу и концу строки, а не началу и концу строки

, иначе это:

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

будет соответствовать

Также я использовал это как ссылку для того, как исключить регулярное выражение """: , чтобы соответствовать строке, которая не содержит слова

...