Bogue dans la double négation des classes de caractères regex?

Il y a un vaudou étrange qui se passe dans le code d'analyse de classe de caractères de l'implémentation d'Oracle de la classe Pattern, qui vient avec votre JRE/JDK si vous l'avez téléchargé depuis le site Web d'Oracle ou si vous utilisez OpenJDK. Je n'ai pas vérifié comment d'autres implémentations JVM (notamment GNU Classpath) analysent l'expression régulière dans la question.

À partir de ce point, toute référence à la classe Pattern et à son fonctionnement interne est strictement limitée à l'implémentation d'Oracle (la référence application).

Il faudrait un certain temps pour lire et comprendre comment la classe Pattern analyse la négation imbriquée comme indiqué dans la question. Cependant, j'ai écrit un programme¹ extraire des informations d'un objet Pattern (avec Reflection API) pour regarder le résultat de la compilation. La sortie ci-dessous provient de l'exécution de mon programme sur Java HotSpot Client VM version 1.7.0_51.

^{1: Actuellement, le programme est un gâchis embarrassant. Je vais mettre à jour ce post avec un lien quand je l'ai terminé et refactorisé.}

[^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

Rien de surprenant ici.

[^[^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

Les 2 cas ci-dessus sont compilés dans le même programme que [^0-9], qui est contre-intuitif.

[[^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

Rien d'étrange dans les 2 cas ci-dessus, comme indiqué dans la question.

[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

Ces 2 cas fonctionnent comme prévu, comme indiqué dans la question. Toutefois, prenez note de la façon dont le moteur prend complément de la première classe de caractères (\D) et appliquer une différence à la classe de caractères composée des restes.

[^[^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

Comme confirmé par les tests de Keppil dans le commentaire, la sortie ci-dessus montre que les 3 expressions régulières ci-dessus sont compilées dans le même programme!

[^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

Au Lieu de NOT(UNION(2, NOT(0-9)), qui est 0-13-9, nous obtenons UNION(NOT(2), NOT(0-9)), ce qui est équivalent à 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

L'expression régulière [^2[^[^0-9]]] compile dans le même programme que [^2[^0-9]] en raison du même bogue.

Il y a un bug non résolu cela semble être de même nature: JDK-6609854 .

Explication

Préliminaire

Voici les détails d'implémentation de la classe Pattern que l'on devrait connaître avant de lire plus loin:

• La classe Pattern compile un String dans une chaîne de nœuds, chaque nœud est responsable d'une petite responsabilité bien définie et délègue le travail au nœud suivant de la chaîne. Node classe est la classe de base de tous les nœud.
• CharProperty class est la classe de base de tous les Nodes liés à la classe de caractères.
• La classe BitClass est une sous-classe de la classe CharProperty qui utilise un tableau boolean[] pour accélérer la correspondance des caractères latin-1 (point de code add, qui permet d'ajouter des caractères lors de la compilation.
• CharProperty.complement, Pattern.union, Pattern.intersection sont des méthodes correspondant aux opérations sur les ensembles. Ce qu'ils font est auto-explicatif.
• Pattern.setDifference est asymétrique ensemble différence.

Analyser la classe de caractères à première vue

Avant de regarder le code complet de la méthode CharProperty clazz(boolean consume), qui est la méthode responsable de l'analyse d'une classe de caractères, examinons une version extrêmement simplifiée du code pour comprendre le flux du code:

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();
    }
}

Le code lit essentiellement l'entrée (l'entrée String convertie en terminée par un caractère nul int[] de points de code) jusqu'à ce qu'il atteigne ] ou la fin de la chaîne (non fermée classe de caractères).

Le code est un peu déroutant avec continue et break se mélangeant à l'intérieur du bloc switch. Cependant, tant que vous réalisez que continue appartient à la boucle externe for et que break appartient au bloc switch, le code est facile à comprendre:

• Les cas se terminant par continue n'exécuteront jamais le code après l'instruction switch.
• Les cas se terminant par break peuvent exécuter le code après l'instruction switch (si ce n'est pas le cas return déjà).

, Avec l'observation ci-dessus, nous pouvons voir qu'à chaque fois , un caractère est jugé non spécial et doit être inclus dans la classe de caractères, nous allons exécuter le code après le switch déclaration, dans laquelle node = range(bits); est la première instruction.

Si vous vérifiez le code source, la méthode CharProperty range(BitClass bits) analyse "un seul caractère ou une plage de caractères dans une classe de caractères". La méthode renvoie soit le même BitClass objet passé (avec un nouveau caractère ajouté) ou renvoie une nouvelle instance de la classe CharProperty.

Les détails sanglants

Ensuite, regardons la version complète du code (avec la partie analysant l'intersection de la classe de caractères && omise):

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();
    }
}

Regardant le code de case '[': de la switch déclaration et le code après le switch instruction:

• La variable node stocke le résultat de l'analyse d'une unité (un caractère autonome, une plage de caractères, une classe de caractères Classe de caractères POSIX/Unicode ou une classe de caractères imbriqués)
• La variable prevstocke le résultat de la compilation jusqu'à présent, et est toujours mise à jour juste après la compilation d'une unité dans node.

Étant donné que la variable locale boolean include, qui enregistre si la classe de caractères est annulée, n'est jamais passée à un appel de méthode, elle ne peut être utilisée que dans cette méthode seule. Et le seul endroit où include est lu et traité est après l'instruction switch.

Poste en cours de construction