Задержка в Regex без очевидной максимальной длины в Java - PullRequest
24 голосов
/ 08 октября 2009

Я всегда думал, что утверждение в Java regex-API (и многих других языках в этом отношении) должно иметь очевидную длину. Таким образом, квантификаторы STAR и PLUS не допускаются в предварительных запросах .

Отличный онлайн-ресурс регулярные-выражения.info , кажется, подтверждает (некоторые из) мои предположения:

"[...] Java делает шаг вперед, позволяя конечное повторение. Ты все еще не может использовать звезду или плюс, но вы можно использовать знак вопроса и фигурные скобки с параметром max указано. Ява признает факт это конечное повторение может быть переписан как чередование строк с разными, но фиксированными длинами. К сожалению, JDK 1.4 и 1.5 есть некоторые ошибки при использовании чередование взглядов назад. Эти были исправлены в JDK 1.6. [...] "

- http://www.regular -expressions.info / lookaround.html

Использование фигурных скобок работает до тех пор, пока общая длина диапазона символов в поле просмотра меньше или равна Integer.MAX_VALUE. Таким образом, эти регулярные выражения действительны:

"(?<=a{0,"   +(Integer.MAX_VALUE)   + "})B"
"(?<=Ca{0,"  +(Integer.MAX_VALUE-1) + "})B"
"(?<=CCa{0," +(Integer.MAX_VALUE-2) + "})B"

Но это не так:

"(?<=Ca{0,"  +(Integer.MAX_VALUE)   +"})B"
"(?<=CCa{0," +(Integer.MAX_VALUE-1) +"})B"

Однако я не понимаю следующее:

Когда я запускаю тест с использованием квантификатора * и + внутри фонаря *1029*, все идет хорошо (см. Вывод Тест 1 и Тест 2 ) .

Но, когда я добавляю один символ в начале просмотра из теста 1 и теста 2 , он прерывается (см. Вывод Тест 3 ).

Создание жадности * из Испытание 3 не дает эффекта, оно все еще ломается (см. Испытание 4 ).

Вот тестовый жгут:

public class Main {

    private static String testFind(String regex, String input) {
        try {
            boolean returned = java.util.regex.Pattern.compile(regex).matcher(input).find();
            return "testFind       : Valid   -> regex = "+regex+", input = "+input+", returned = "+returned;
        } catch(Exception e) {
            return "testFind       : Invalid -> "+regex+", "+e.getMessage();
        }
    }

    private static String testReplaceAll(String regex, String input) {
        try {
            String returned = input.replaceAll(regex, "FOO");
            return "testReplaceAll : Valid   -> regex = "+regex+", input = "+input+", returned = "+returned;
        } catch(Exception e) {
            return "testReplaceAll : Invalid -> "+regex+", "+e.getMessage();
        }
    }

    private static String testSplit(String regex, String input) {
        try {
            String[] returned = input.split(regex);
            return "testSplit      : Valid   -> regex = "+regex+", input = "+input+", returned = "+java.util.Arrays.toString(returned);
        } catch(Exception e) {
            return "testSplit      : Invalid -> "+regex+", "+e.getMessage();
        }
    }

    public static void main(String[] args) {
        String[] regexes = {"(?<=a*)B", "(?<=a+)B", "(?<=Ca*)B", "(?<=Ca*?)B"};
        String input = "CaaaaaaaaaaaaaaaBaaaa";
        int test = 0;
        for(String regex : regexes) {
            test++;
            System.out.println("********************** Test "+test+" **********************");
            System.out.println("    "+testFind(regex, input));
            System.out.println("    "+testReplaceAll(regex, input));
            System.out.println("    "+testSplit(regex, input));
            System.out.println();
        }
    }
}

Выход:

********************** Test 1 **********************
    testFind       : Valid   -> regex = (?<=a*)B, input = CaaaaaaaaaaaaaaaBaaaa, returned = true
    testReplaceAll : Valid   -> regex = (?<=a*)B, input = CaaaaaaaaaaaaaaaBaaaa, returned = CaaaaaaaaaaaaaaaFOOaaaa
    testSplit      : Valid   -> regex = (?<=a*)B, input = CaaaaaaaaaaaaaaaBaaaa, returned = [Caaaaaaaaaaaaaaa, aaaa]

********************** Test 2 **********************
    testFind       : Valid   -> regex = (?<=a+)B, input = CaaaaaaaaaaaaaaaBaaaa, returned = true
    testReplaceAll : Valid   -> regex = (?<=a+)B, input = CaaaaaaaaaaaaaaaBaaaa, returned = CaaaaaaaaaaaaaaaFOOaaaa
    testSplit      : Valid   -> regex = (?<=a+)B, input = CaaaaaaaaaaaaaaaBaaaa, returned = [Caaaaaaaaaaaaaaa, aaaa]

********************** Test 3 **********************
    testFind       : Invalid -> (?<=Ca*)B, Look-behind group does not have an obvious maximum length near index 6
(?<=Ca*)B
      ^
    testReplaceAll : Invalid -> (?<=Ca*)B, Look-behind group does not have an obvious maximum length near index 6
(?<=Ca*)B
      ^
    testSplit      : Invalid -> (?<=Ca*)B, Look-behind group does not have an obvious maximum length near index 6
(?<=Ca*)B
      ^

********************** Test 4 **********************
    testFind       : Invalid -> (?<=Ca*?)B, Look-behind group does not have an obvious maximum length near index 7
(?<=Ca*?)B
       ^
    testReplaceAll : Invalid -> (?<=Ca*?)B, Look-behind group does not have an obvious maximum length near index 7
(?<=Ca*?)B
       ^
    testSplit      : Invalid -> (?<=Ca*?)B, Look-behind group does not have an obvious maximum length near index 7
(?<=Ca*?)B
       ^

Мой вопрос может быть очевиден, но я все равно задам его: Может кто-нибудь объяснить мне, почему Тест 1 и 2 не пройден, и Тест 3 и 4 нет? Я бы ожидал, что все они выйдут из строя, не половина из них заработает, а половина из них выйдет из строя.

Спасибо.

PS. Я использую: Java версия 1.6.0_14

Ответы [ 2 ]

17 голосов
/ 08 октября 2009

Взглянув на исходный код для Pattern.java, вы обнаружите, что '*' и '+' реализованы как экземпляры Curly (это объект, созданный для операторов curly). Итак,

a*

реализовано как

a{0,0x7FFFFFFF}

и

a+

реализовано как

a{1,0x7FFFFFFF}

, поэтому вы видите точно такое же поведение для фигур и звезд.

13 голосов
/ 08 октября 2009

Это ошибка: http://bugs.sun.com/view_bug.do?bug_id=6695369

Pattern.compile() всегда должен выдавать исключение, если он не может определить максимально возможную длину совпадения просмотра за спиной.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...