Ошибка в двойном отрицании классов символов регулярных выражений?

TL; DR (до исправления):
Почему [^\\D2], [^[^0-9]2], [^2[^0-9]] получают разные результаты в Java?

Код, используемый для тестов. Вы можете пропустить это сейчас.

Допустим, мне нужно регулярное выражение, которое будет принимать символы, которые

Таким образом, такое регулярное выражение должно представлять каждый символ, кроме 0, 1, 3, 4 ,..., 9. Я могу написать это по крайней мере двумя способами, которые будут суммой всего, что не является цифрой с 2:

Оба эти регулярных выражения работают как ожидалось

Теперь допустим, что я хочу изменить принятые символы. (поэтому я хочу принять все цифры, кроме 2) Я мог бы создать регулярное выражение, которое явно содержит все принятые символы, такие как

или попытайтесь опровергнуть два ранее описанных регулярных выражения, обернув их в другой [^...]

но к моему удивлению только первые две версии работают как положено

Поэтому мой вопрос: почему [^[^0-9]2] или [^2[^0-9]] не ведут себя как [^\D2]? Могу ли я как-то исправить эти регулярные выражения, чтобы иметь возможность использовать [^0-9] внутри них?

Ответы

Ответ 1

В коде анализа символов класса Oracle класса Pattern есть некоторый странный voodoo, который поставляется с вашим JRE/JDK, если вы загрузили его с веб-сайта Oracle или если вы используете OpenJDK. Я не проверял, как другие JVM (особенно GNU Classpath) реализуют синтаксический анализ регулярного выражения в вопросе.

С этой точки зрения любая ссылка на класс Pattern и его внутренняя работа строго ограничена реализацией Oracle (эталонная реализация).

Потребовалось некоторое время, чтобы прочитать и понять, как класс Pattern анализирует вложенное отрицание, как показано в вопросе. Тем не менее, я написал программу ¹ чтобы извлечь информацию из объекта Pattern (API отражения), чтобы посмотреть на результат компиляции, Ниже приведен вывод о запуске моей программы на Java HotSpot Client VM версии 1.7.0_51.

^{1: В настоящее время программа является неловким беспорядком. Я обновлю это сообщение ссылкой, когда я его закончу и реорганизую.}

[^0-9]
Start. Start unanchored match (minLength=1)
CharProperty.complement (character class negation). Match any character NOT matched by the following character class:
  Pattern.rangeFor (character range). Match any character within the range from code point U+0030 to code point U+0039 (both ends inclusive)
LastNode
Node. Accept match

Ничего удивительного здесь.

[^[^0-9]]
Start. Start unanchored match (minLength=1)
CharProperty.complement (character class negation). Match any character NOT matched by the following character class:
  Pattern.rangeFor (character range). Match any character within the range from code point U+0030 to code point U+0039 (both ends inclusive)
LastNode
Node. Accept match

[^[^[^0-9]]]
Start. Start unanchored match (minLength=1)
CharProperty.complement (character class negation). Match any character NOT matched by the following character class:
  Pattern.rangeFor (character range). Match any character within the range from code point U+0030 to code point U+0039 (both ends inclusive)
LastNode
Node. Accept match

Следующие два случая, приведенные выше, скомпилированы в ту же программу, что и [^0-9], которая контринтуитивно понятна.

[[^0-9]2]
Start. Start unanchored match (minLength=1)
Pattern.union (character class union). Match any character matched by either character classes below:
  CharProperty.complement (character class negation). Match any character NOT matched by the following character class:
    Pattern.rangeFor (character range). Match any character within the range from code point U+0030 to code point U+0039 (both ends inclusive)
  BitClass. Optimized character class with boolean[] to match characters in Latin-1 (code point <= 255). Match the following 1 character(s):
    [U+0032]
    2
LastNode
Node. Accept match

[\D2]
Start. Start unanchored match (minLength=1)
Pattern.union (character class union). Match any character matched by either character classes below:
  CharProperty.complement (character class negation). Match any character NOT matched by the following character class:
    Ctype. Match POSIX character class DIGIT (US-ASCII)
  BitClass. Optimized character class with boolean[] to match characters in Latin-1 (code point <= 255). Match the following 1 character(s):
    [U+0032]
    2
LastNode
Node. Accept match

Ничего странного в 2 случаях выше, как указано в вопросе.

[013-9]
Start. Start unanchored match (minLength=1)
Pattern.union (character class union). Match any character matched by either character classes below:
  BitClass. Optimized character class with boolean[] to match characters in Latin-1 (code point <= 255). Match the following 2 character(s):
    [U+0030][U+0031]
    01
  Pattern.rangeFor (character range). Match any character within the range from code point U+0033 to code point U+0039 (both ends inclusive)
LastNode
Node. Accept match

[^\D2]
Start. Start unanchored match (minLength=1)
Pattern.setDifference (character class subtraction). Match any character matched by the 1st character class, but NOT the 2nd character class:
  CharProperty.complement (character class negation). Match any character NOT matched by the following character class:
    CharProperty.complement (character class negation). Match any character NOT matched by the following character class:
      Ctype. Match POSIX character class DIGIT (US-ASCII)
  BitClass. Optimized character class with boolean[] to match characters in Latin-1 (code point <= 255). Match the following 1 character(s):
    [U+0032]
    2
LastNode
Node. Accept match

Эти 2 дела работают, как ожидалось, как указано в вопросе. Однако обратите внимание на то, как двигатель дополняет первый класс символов (\D) и применяет разницу заданий к классу символов, состоящему из оставшегося.

[^[^0-9]2]
Start. Start unanchored match (minLength=1)
Pattern.setDifference (character class subtraction). Match any character matched by the 1st character class, but NOT the 2nd character class:
  CharProperty.complement (character class negation). Match any character NOT matched by the following character class:
    Pattern.rangeFor (character range). Match any character within the range from code point U+0030 to code point U+0039 (both ends inclusive)
  BitClass. Optimized character class with boolean[] to match characters in Latin-1 (code point <= 255). Match the following 1 character(s):
    [U+0032]
    2
LastNode
Node. Accept match

[^[^[^0-9]]2]
Start. Start unanchored match (minLength=1)
Pattern.setDifference (character class subtraction). Match any character matched by the 1st character class, but NOT the 2nd character class:
  CharProperty.complement (character class negation). Match any character NOT matched by the following character class:
    Pattern.rangeFor (character range). Match any character within the range from code point U+0030 to code point U+0039 (both ends inclusive)
  BitClass. Optimized character class with boolean[] to match characters in Latin-1 (code point <= 255). Match the following 1 character(s):
    [U+0032]
    2
LastNode
Node. Accept match

[^[^[^[^0-9]]]2]
Start. Start unanchored match (minLength=1)
Pattern.setDifference (character class subtraction). Match any character matched by the 1st character class, but NOT the 2nd character class:
  CharProperty.complement (character class negation). Match any character NOT matched by the following character class:
    Pattern.rangeFor (character range). Match any character within the range from code point U+0030 to code point U+0039 (both ends inclusive)
  BitClass. Optimized character class with boolean[] to match characters in Latin-1 (code point <= 255). Match the following 1 character(s):
    [U+0032]
    2
LastNode
Node. Accept match

Как было подтверждено в тесте Keppil в комментарии, вышеприведенный вывод показывает, что все 3 регулярных выражения скомпилированы в одну и ту же программу!

[^2[^0-9]]
Start. Start unanchored match (minLength=1)
Pattern.union (character class union). Match any character matched by either character classes below:
  CharProperty.complement (character class negation). Match any character NOT matched by the following character class:
    BitClass. Optimized character class with boolean[] to match characters in Latin-1 (code point <= 255). Match the following 1 character(s):
      [U+0032]
      2
  CharProperty.complement (character class negation). Match any character NOT matched by the following character class:
    Pattern.rangeFor (character range). Match any character within the range from code point U+0030 to code point U+0039 (both ends inclusive)
LastNode
Node. Accept match

Вместо NOT(UNION(2, NOT(0-9)), который равен 0-13-9, получаем UNION(NOT(2), NOT(0-9)), что эквивалентно NOT(2).

[^2[^[^0-9]]]
Start. Start unanchored match (minLength=1)
Pattern.union (character class union). Match any character matched by either character classes below:
  CharProperty.complement (character class negation). Match any character NOT matched by the following character class:
    BitClass. Optimized character class with boolean[] to match characters in Latin-1 (code point <= 255). Match the following 1 character(s):
      [U+0032]
      2
  CharProperty.complement (character class negation). Match any character NOT matched by the following character class:
    Pattern.rangeFor (character range). Match any character within the range from code point U+0030 to code point U+0039 (both ends inclusive)
LastNode
Node. Accept match

Регулярное выражение [^2[^[^0-9]]] компилируется в ту же программу, что и [^2[^0-9]] из-за той же ошибки.

Существует нерешенная ошибка, которая, по-видимому, имеет один и тот же характер: JDK-6609854.

Описание

Предварительный

Ниже представлены сведения о реализации класса Pattern, которые следует знать, прежде чем читать дальше:

Pattern класс компилирует a String в цепочку узлов, каждый node отвечает за небольшую и четко определенную ответственность и делегирует работу следующему node в цепочке. Node class - это базовый класс всех узлов.
CharProperty class - это базовый класс всех связанных с символьным классом Node s.
BitClass class - это подкласс класса CharProperty, который использует массив boolean[] для ускорения сопоставления символов Latin-1 (кодовая точка <= 255). Он имеет метод add, который позволяет добавлять символы во время компиляции.
CharProperty.complement, Pattern.union, Pattern.intersection - это методы, соответствующие заданным операциям. То, что они делают, самоочевидно.
Pattern.setDifference - асимметричная разность заданий.

Анализ класса символов с первого взгляда

Перед рассмотрением полного кода метода CharProperty clazz(boolean consume), который является методом, ответственным за разбор символьного класса, рассмотрим чрезвычайно упрощенную версию кода, чтобы понять поток кода:

private CharProperty clazz(boolean consume) {
    // [Declaration and initialization of local variables - OMITTED]
    BitClass bits = new BitClass();
    int ch = next();
    for (;;) {
        switch (ch) {
            case '^':
                // Negates if first char in a class, otherwise literal
                if (firstInClass) {
                    // [CODE OMITTED]
                    ch = next();
                    continue;
                } else {
                    // ^ not first in class, treat as literal
                    break;
                }
            case '[':
                // [CODE OMITTED]
                ch = peek();
                continue;
            case '&':
                // [CODE OMITTED]
                continue;
            case 0:
                // [CODE OMITTED]
                // Unclosed character class is checked here
                break;
            case ']':
                // [CODE OMITTED]
                // The only return statement in this method
                // is in this case
                break;
            default:
                // [CODE OMITTED]
                break;
        }
        node = range(bits);

        // [CODE OMITTED]
        ch = peek();
    }
}

В основном код считывает ввод (вход String преобразуется в оканчивающиеся на нуль int[] кодовые точки) до тех пор, пока он не достигнет ] или конца строки (незакрытый класс символов).

Код немного путается с continue и break, смешающимися внутри блока switch. Однако, если вы понимаете, что continue принадлежит внешнему циклу for, а break принадлежит блоку switch, код легко понять:

Случаи, заканчивающиеся на continue, никогда не будут выполнять код после инструкции switch.
Дела, заканчивающиеся на break, могут выполнять код после оператора switch (если он уже не return).

С учетом вышеизложенного мы видим, что всякий раз, когда признается неспецифический символ и должен быть включен в класс символов, мы будем выполнять код после инструкции switch в котором node = range(bits); является первым утверждением.

Если вы проверяете исходный код , метод CharProperty range(BitClass bits) анализирует "один символ или диапазон символов в классе символов". Метод возвращает тот же объект BitClass, который был передан (с добавлением нового символа), или возвращает новый экземпляр класса CharProperty.

Детали gory

Далее, давайте посмотрим на полную версию кода (с пересечением класса символа парсера &&):

private CharProperty clazz(boolean consume) {
    CharProperty prev = null;
    CharProperty node = null;
    BitClass bits = new BitClass();
    boolean include = true;
    boolean firstInClass = true;
    int ch = next();
    for (;;) {
        switch (ch) {
            case '^':
                // Negates if first char in a class, otherwise literal
                if (firstInClass) {
                    if (temp[cursor-1] != '[')
                        break;
                    ch = next();
                    include = !include;
                    continue;
                } else {
                    // ^ not first in class, treat as literal
                    break;
                }
            case '[':
                firstInClass = false;
                node = clazz(true);
                if (prev == null)
                    prev = node;
                else
                    prev = union(prev, node);
                ch = peek();
                continue;
            case '&':
                // [CODE OMITTED]
                // There are interesting things (bugs) here,
                // but it is not relevant to the discussion.
                continue;
            case 0:
                firstInClass = false;
                if (cursor >= patternLength)
                    throw error("Unclosed character class");
                break;
            case ']':
                firstInClass = false;

                if (prev != null) {
                    if (consume)
                        next();

                    return prev;
                }
                break;
            default:
                firstInClass = false;
                break;
        }
        node = range(bits);

        if (include) {
            if (prev == null) {
                prev = node;
            } else {
                if (prev != node)
                    prev = union(prev, node);
            }
        } else {
            if (prev == null) {
                prev = node.complement();
            } else {
                if (prev != node)
                    prev = setDifference(prev, node);
            }
        }
        ch = peek();
    }
}

Посмотрите на код в case '[': оператора switch и код после инструкции switch:

В переменной Node хранится результат разбора единицы (автономный символ, диапазон символов, сокращенный класс символов, класс символов POSIX/Unicode или вложенный класс символов).
Переменная prev сохраняет результат компиляции до сих пор и всегда обновляется сразу после компиляции единицы в Node.

Так как локальная переменная boolean include, которая записывает, является ли класс символа отрицательным, никогда не передается ни одному вызову метода, его действие может действовать только в этом методе. И единственное место include читается и обрабатывается после инструкции switch.

Опубликовать в процессе строительства

Ответ 2

В соответствии со страницей JavaDoc классы вложенности создают объединение двух классов, что делает невозможным создание пересечения с использованием этой нотации:

Чтобы создать объединение, просто вставьте один класс внутри другого, например [0-4 [6-8]]. Этот конкретный союз создает один класс символов, который соответствует номерам 0, 1, 2, 3, 4, 6, 7 и 8.

Чтобы создать пересечение, вам нужно будет использовать &&:

Чтобы создать один класс символов, соответствующий только символам, общим для всех его вложенных классов, используйте & &, как в [0-9 & [345]]. Это конкретное пересечение создает один класс символов, соответствующий только числам, общим для обоих классов символов: 3, 4 и 5.

Последняя часть вашей проблемы по-прежнему остается загадкой для меня. Объединение [^2] и [^0-9] должно действительно быть [^2], поэтому [^2[^0-9]] ведет себя так, как ожидалось. [^[^0-9]2] поведение, подобное [^0-9], действительно странно.