Menu
TL;DR (before fix):
Why [^\\D2], [^[^0-9]2], [^2[^0-9]] get different results in Java?
Code used for tests. You can skip it for now.
String[] regexes = { "[[^0-9]2]", "[\\D2]", "[013-9]", "[^\\D2]", "[^[^0-9]2]", "[^2[^0-9]]" }; String[] tests = { "x", "1", "2", "3", "^", "[", "]" }; System.out.printf("match | %9s , %6s | %6s , %6s , %6s , %10s%n", (Object[]) regexes); System.out.println("-----------------------------------------------------------------------"); for (String test : tests) System.out.printf("%5s | %9b , %6b | %7b , %6b , %10b , %10b %n", test, test.matches(regexes[0]), test.matches(regexes[1]), test.matches(regexes[2]), test.matches(regexes[3]), test.matches(regexes[4]), test.matches(regexes[5])); Lets say I need regex which will accept characters that are
2.So such regex should represent every character except 0, 1, 3,4, ... , 9. I can write it at least in two ways which will be sum of everything which is not digit with 2:
[[^0-9]2][\\D2]Both of these regexes works as expected
match , [[^0-9]2] , [\D2] -------------------------- x , true , true 1 , false , false 2 , true , true 3 , false , false ^ , true , true [ , true , true ] , true , true Now lets say I want to reverse accepted characters. (so I want to accept all digits except 2) I could create regex which explicitly contains all accepted characters like
[013-9]or try to negate two previously described regexes by wrapping it in another [^...] like
[^\\D2][^[^0-9]2][^2[^0-9]]but to my surprise only first two versions work as expected
match | [[^0-9]2] , [\D2] | [013-9] , [^\D2] , [^[^0-9]2] , [^2[^0-9]] ------+--------------------+------------------------------------------- x | true , true | false , false , true , true 1 | false , false | true , true , false , true 2 | true , true | false , false , false , false 3 | false , false | true , true , false , true ^ | true , true | false , false , true , true [ | true , true | false , false , true , true ] | true , true | false , false , true , true So my question is why [^[^0-9]2] or [^2[^0-9]] doesn't behave as [^\D2]? Can I somehow correct these regexes so I would be able to use [^0-9] inside them?
697
Similarly, the negation variant of the character class is defined as "[^ ]" (with ^ within the square braces), it matches a single character which is not in the specified or set of possible characters. For example the regular expression [^abc] matches a single character except a or, b or, c.
$ means "Match the end of the string" (the position after the last character in the string). Both are called anchors and ensure that the entire string is matched instead of just a substring.
In the context of regular expressions, a character class is a set of characters enclosed within square brackets. It specifies the characters that will successfully match a single character from a given input string.
A regex consists of a sequence of characters, metacharacters (such as . , \d , \D , \ s, \S , \w , \W ) and operators (such as + , * , ? , | , ^ ). They are constructed by combining many smaller sub-expressions.
There are some strange voodoo going on in the character class parsing code of Oracle's implementation of Pattern class, which comes with your JRE/JDK if you downloaded it from Oracle's website or if you are using OpenJDK. I have not checked how other JVM (notably GNU Classpath) implementations parse the regex in the question.
From this point, any reference to Pattern class and its internal working is strictly restricted to Oracle's implementation (the reference implementation).
It would take some time to read and understand how Pattern class parses the nested negation as shown in the question. However, I have written a program1 to extract information from a Pattern object (with Reflection API) to look at the result of compilation. The output below is from running my program on Java HotSpot Client VM version 1.7.0_51.
1: Currently, the program is an embarrassing mess. I will update this post with a link when I finished it and refactored it.
[^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 Nothing surprising here.
[^[^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 The next 2 cases above are compiled to the same program as [^0-9], which is counter-intuitive.
[[^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 Nothing strange in the 2 cases above, as stated in the 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 These 2 cases work as expected, as stated in the question. However, take note of how the engine takes complement of the first character class (\D) and apply set difference to the character class consisting of the leftover.
[^[^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 As confirmed via testing by Keppil in the comment, the output above shows that all 3 regex above are compiled to the same program!
[^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 Instead of NOT(UNION(2, NOT(0-9)), which is 0-13-9, we get UNION(NOT(2), NOT(0-9)), which is equivalent to 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 The regex [^2[^[^0-9]]] compiles to the same program as [^2[^0-9]] due to the same bug.
There is an unresolved bug that seems to be of the same nature: JDK-6609854.
Below are implementation details of Pattern class that one should know before reading further:
Pattern class compiles a String into a chain of nodes, each node is in charge of a small and well-defined responsibility, and delegates the work to the next node in the chain. Node class is the base class of all the nodes.CharProperty class is the base class of all character-class related Nodes.BitClass class is a subclass of CharProperty class that uses a boolean[] array to speed up matching for Latin-1 characters (code point <= 255). It has an add method, which allows characters to be added during compilation.CharProperty.complement, Pattern.union, Pattern.intersection are methods corresponding to set operations. What they do is self-explanatory.Pattern.setDifference is asymmetric set difference.Before looking at the full code of CharProperty clazz(boolean consume) method, which is the method responsible for parsing a character class, let us look at an extremely simplified version of the code to understand the flow of the 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(); } } The code basically reads the input (the input String converted to null-terminated int[] of code points) until it hits ] or the end of the String (unclosed character class).
The code is a bit confusing with continue and break mixing together inside the switch block. However, as long as you realize that continue belongs to the outer for loop and break belongs to the switch block, the code is easy to understand:
continue will never execute the code after the switch statement.break may execute the code after the switch statement (if it doesn't return already).With the observation above, we can see that whenever a character is found to be non-special and should be included in the character class, we will execute the code after the switch statement, in which node = range(bits); is the first statement.
If you check the source code, the method CharProperty range(BitClass bits) parses "a single character or a character range in a character class". The method either returns the same BitClass object passed in (with new character added) or return a new instance of CharProperty class.
Next, let us look at the full version of the code (with the part parsing character class intersection && omitted):
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(); } } Looking at the code in case '[': of the switch statement and the code after the switch statement:
node variable stores the result of parsing a unit (a standalone character, a character range, a shorthand character class, a POSIX/Unicode character class or a nested character class)prev variable stores the compilation result so far, and is always updated right after we compiles a unit in node.Since the local variable boolean include, which records whether the character class is negated, is never passed to any method call, it can only be acted upon in this method alone. And the only place include is read and processed is after the switch statement.
184
According to the JavaDoc page nesting classes produces the union of the two classes, which makes it impossible to create an intersection using that notation:
To create a union, simply nest one class inside the other, such as [0-4[6-8]]. This particular union creates a single character class that matches the numbers 0, 1, 2, 3, 4, 6, 7, and 8.
To create an intersection you will have to use &&:
To create a single character class matching only the characters common to all of its nested classes, use &&, as in [0-9&&[345]]. This particular intersection creates a single character class matching only the numbers common to both character classes: 3, 4, and 5.
The last part of your problem is still a mystery to me too. The union of [^2] and [^0-9] should indeed be [^2], so [^2[^0-9]] behaves as expected. [^[^0-9]2] behaving like [^0-9] is indeed strange though.
29
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
