Name: gm110360 Date: 03/16/2004


FULL PRODUCT VERSION :
java version "1.4.2_03"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.4.2_03-b02)
Java HotSpot(TM) Client VM (build 1.4.2_03-b02, mixed mode)

ADDITIONAL OS VERSION INFORMATION :
Linux pavel-z 2.4.20-4GB #1 Mon Dec 15 09:41:14 EET 2003 i686 unknown unknown GNU/Linux

A DESCRIPTION OF THE PROBLEM :
When matching comparetively big strings with comparetively big regular expressions Matcher Engine hangs taking 100% CPU Usage.
I think it's a bug because it happens with the BAD_PATTERN and doesn't happen with the GOOD_PATTERN (see source code below). The only difference between them is the slash sign in the begining of the last row which should simply make the BAD_PATTERN not match the given string. It should not make Matcher Engine hang.

STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
compile the source code given below and run it.

EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
Does Good Pattern match? true
Does Bad Pattern match? false
ACTUAL -
Does Good Pattern match? true
<<<<hang>>>

ERROR MESSAGES/STACK TRACES THAT OCCUR :
Does Good Pattern match? true
Full thread dump Java HotSpot(TM) Client VM (1.4.2_03-b02 mixed mode):

"Signal Dispatcher" daemon prio=1 tid=0x0808e1e8 nid=0xcd0 waiting on condition [0..0]

"Finalizer" daemon prio=1 tid=0x0808a5c0 nid=0xcce in Object.wait() [bf3ff000..bf3ff8d8]
        at java.lang.Object.wait(Native Method)
        - waiting on <0x44760490> (a java.lang.ref.ReferenceQueue$Lock)
        at java.lang.ref.ReferenceQueue.remove(ReferenceQueue.java:111)
        - locked <0x44760490> (a java.lang.ref.ReferenceQueue$Lock)
        at java.lang.ref.ReferenceQueue.remove(ReferenceQueue.java:127)
        at java.lang.ref.Finalizer$FinalizerThread.run(Finalizer.java:159)

"Reference Handler" daemon prio=1 tid=0x08089a00 nid=0xccd in Object.wait() [bf5ff000..bf5ff8d8]
        at java.lang.Object.wait(Native Method)
        - waiting on <0x44760380> (a java.lang.ref.Reference$Lock)
        at java.lang.Object.wait(Object.java:429)
        at java.lang.ref.Reference$ReferenceHandler.run(Reference.java:115)
        - locked <0x44760380> (a java.lang.ref.Reference$Lock)

"main" prio=1 tid=0x08052250 nid=0xcca runnable [bfffc000..bfffd16c]
        at java.util.regex.Pattern$Dot.match(Pattern.java:3529)
        at java.util.regex.Pattern$Curly.match0(Pattern.java:3657)
        at java.util.regex.Pattern$Curly.match(Pattern.java:3631)
        at java.util.regex.Pattern$GroupTail.match(Pattern.java:4032)
        at java.util.regex.Pattern$Curly.match0(Pattern.java:3669)
        at java.util.regex.Pattern$Curly.match(Pattern.java:3631)
        at java.util.regex.Pattern$GroupHead.match(Pattern.java:3973)
        at java.util.regex.Pattern$Curly.match0(Pattern.java:3669)
        at java.util.regex.Pattern$Curly.match(Pattern.java:3631)
        at java.util.regex.Pattern$Slice.match(Pattern.java:3297)
        at java.util.regex.Pattern$Curly.match0(Pattern.java:3669)
        at java.util.regex.Pattern$Curly.match(Pattern.java:3631)
        at java.util.regex.Pattern$Curly.match0(Pattern.java:3669)
        at java.util.regex.Pattern$Curly.match(Pattern.java:3631)
        at java.util.regex.Pattern$GroupTail.match(Pattern.java:4032)
        at java.util.regex.Pattern$Curly.match0(Pattern.java:3669)
        at java.util.regex.Pattern$Curly.match(Pattern.java:3631)
        at java.util.regex.Pattern$GroupHead.match(Pattern.java:3973)
        at java.util.regex.Pattern$Curly.match0(Pattern.java:3669)
        at java.util.regex.Pattern$Curly.match(Pattern.java:3631)
        at java.util.regex.Pattern$Slice.match(Pattern.java:3297)
        at java.util.regex.Pattern$Curly.match0(Pattern.java:3669)
        at java.util.regex.Pattern$Curly.match(Pattern.java:3631)
        at java.util.regex.Pattern$Curly.match0(Pattern.java:3669)
        at java.util.regex.Pattern$Curly.match(Pattern.java:3631)
        at java.util.regex.Pattern$GroupTail.match(Pattern.java:4032)
        at java.util.regex.Pattern$Curly.match0(Pattern.java:3669)
        at java.util.regex.Pattern$Curly.match(Pattern.java:3631)
        at java.util.regex.Pattern$GroupHead.match(Pattern.java:3973)
        at java.util.regex.Pattern$Curly.match0(Pattern.java:3669)
        at java.util.regex.Pattern$Curly.match(Pattern.java:3631)
        at java.util.regex.Pattern$Slice.match(Pattern.java:3297)
        at java.util.regex.Pattern$Curly.match0(Pattern.java:3669)
        at java.util.regex.Pattern$Curly.match(Pattern.java:3631)
        at java.util.regex.Pattern$Curly.match0(Pattern.java:3669)
        at java.util.regex.Pattern$Curly.match(Pattern.java:3631)
        at java.util.regex.Pattern$GroupTail.match(Pattern.java:4032)
        at java.util.regex.Pattern$Curly.match0(Pattern.java:3669)
        at java.util.regex.Pattern$Curly.match(Pattern.java:3631)
        at java.util.regex.Pattern$GroupHead.match(Pattern.java:3973)
        at java.util.regex.Pattern$Curly.match0(Pattern.java:3669)
        at java.util.regex.Pattern$Curly.match(Pattern.java:3631)
        at java.util.regex.Pattern$Slice.match(Pattern.java:3297)
        at java.util.regex.Pattern$Curly.match0(Pattern.java:3669)
        at java.util.regex.Pattern$Curly.match(Pattern.java:3631)
        at java.util.regex.Pattern$Curly.match0(Pattern.java:3676)
        at java.util.regex.Pattern$Curly.match(Pattern.java:3631)
        at java.util.regex.Pattern$Slice.match(Pattern.java:3297)
        at java.util.regex.Pattern$Curly.match0(Pattern.java:3676)
        at java.util.regex.Pattern$Curly.match(Pattern.java:3631)
        at java.util.regex.Pattern$Slice.match(Pattern.java:3297)
        at java.util.regex.Pattern$Curly.match0(Pattern.java:3669)
        at java.util.regex.Pattern$Curly.match(Pattern.java:3631)
        at java.util.regex.Pattern$Single.match(Pattern.java:3004)
        at java.util.regex.Pattern$Curly.match0(Pattern.java:3669)
        at java.util.regex.Pattern$Curly.match(Pattern.java:3631)
        at java.util.regex.Pattern$Slice.match(Pattern.java:3297)
        at java.util.regex.Pattern$Curly.match0(Pattern.java:3669)
        at java.util.regex.Pattern$Curly.match(Pattern.java:3631)
        at java.util.regex.Pattern$Begin.match(Pattern.java:2831)
        at java.util.regex.Matcher.match(Matcher.java:745)
        at java.util.regex.Matcher.matches(Matcher.java:388)
        at PatternProblem.main(PatternProblem.java:27)

"VM Thread" prio=1 tid=0x08086798 nid=0xccc runnable

"VM Periodic Task Thread" prio=1 tid=0x080917d0 nid=0xcd2 waiting on condition
"Suspend Checker Thread" prio=1 tid=0x0808d860 nid=0xccf runnable
Full thread dump Java HotSpot(TM) Client VM (1.4.2_03-b02 mixed mode):

"Signal Dispatcher" daemon prio=1 tid=0x0808e1e8 nid=0xcd0 waiting on condition [0..0]

"Finalizer" daemon prio=1 tid=0x0808a5c0 nid=0xcce in Object.wait() [bf3ff000..bf3ff8d8]
        at java.lang.Object.wait(Native Method)
        - waiting on <0x44760490> (a java.lang.ref.ReferenceQueue$Lock)
        at java.lang.ref.ReferenceQueue.remove(ReferenceQueue.java:111)
        - locked <0x44760490> (a java.lang.ref.ReferenceQueue$Lock)
        at java.lang.ref.ReferenceQueue.remove(ReferenceQueue.java:127)
        at java.lang.ref.Finalizer$FinalizerThread.run(Finalizer.java:159)

"Reference Handler" daemon prio=1 tid=0x08089a00 nid=0xccd in Object.wait() [bf5ff000..bf5ff8d8]
        at java.lang.Object.wait(Native Method)
        - waiting on <0x44760380> (a java.lang.ref.Reference$Lock)
        at java.lang.Object.wait(Object.java:429)
        at java.lang.ref.Reference$ReferenceHandler.run(Reference.java:115)
        - locked <0x44760380> (a java.lang.ref.Reference$Lock)

"main" prio=1 tid=0x08052250 nid=0xcca runnable [bfffc000..bfffd16c]
        at java.util.regex.Pattern$Single.match(Pattern.java:3004)
        at java.util.regex.Pattern$Curly.match0(Pattern.java:3669)
        at java.util.regex.Pattern$Curly.match(Pattern.java:3631)
        at java.util.regex.Pattern$GroupTail.match(Pattern.java:4032)
        at java.util.regex.Pattern$Curly.match0(Pattern.java:3669)
        at java.util.regex.Pattern$Curly.match(Pattern.java:3631)
        at java.util.regex.Pattern$GroupHead.match(Pattern.java:3973)
        at java.util.regex.Pattern$Curly.match0(Pattern.java:3669)
        at java.util.regex.Pattern$Curly.match(Pattern.java:3631)
        at java.util.regex.Pattern$Slice.match(Pattern.java:3297)
        at java.util.regex.Pattern$Curly.match0(Pattern.java:3669)
        at java.util.regex.Pattern$Curly.match(Pattern.java:3631)
        at java.util.regex.Pattern$Curly.match0(Pattern.java:3669)
        at java.util.regex.Pattern$Curly.match(Pattern.java:3631)
        at java.util.regex.Pattern$GroupTail.match(Pattern.java:4032)
        at java.util.regex.Pattern$Curly.match0(Pattern.java:3669)
        at java.util.regex.Pattern$Curly.match(Pattern.java:3631)
        at java.util.regex.Pattern$GroupHead.match(Pattern.java:3973)
        at java.util.regex.Pattern$Curly.match0(Pattern.java:3669)
        at java.util.regex.Pattern$Curly.match(Pattern.java:3631)
        at java.util.regex.Pattern$Slice.match(Pattern.java:3297)
        at java.util.regex.Pattern$Curly.match0(Pattern.java:3669)
        at java.util.regex.Pattern$Curly.match(Pattern.java:3631)
        at java.util.regex.Pattern$Curly.match0(Pattern.java:3669)
        at java.util.regex.Pattern$Curly.match(Pattern.java:3631)
        at java.util.regex.Pattern$GroupTail.match(Pattern.java:4032)
        at java.util.regex.Pattern$Curly.match0(Pattern.java:3669)
        at java.util.regex.Pattern$Curly.match(Pattern.java:3631)
        at java.util.regex.Pattern$GroupHead.match(Pattern.java:3973)
        at java.util.regex.Pattern$Curly.match0(Pattern.java:3669)
        at java.util.regex.Pattern$Curly.match(Pattern.java:3631)
        at java.util.regex.Pattern$Slice.match(Pattern.java:3297)
        at java.util.regex.Pattern$Curly.match0(Pattern.java:3669)
        at java.util.regex.Pattern$Curly.match(Pattern.java:3631)
        at java.util.regex.Pattern$Curly.match0(Pattern.java:3669)
        at java.util.regex.Pattern$Curly.match(Pattern.java:3631)
        at java.util.regex.Pattern$GroupTail.match(Pattern.java:4032)
        at java.util.regex.Pattern$Curly.match0(Pattern.java:3669)
        at java.util.regex.Pattern$Curly.match(Pattern.java:3631)
        at java.util.regex.Pattern$GroupHead.match(Pattern.java:3973)
        at java.util.regex.Pattern$Curly.match0(Pattern.java:3669)
        at java.util.regex.Pattern$Curly.match(Pattern.java:3631)
        at java.util.regex.Pattern$Slice.match(Pattern.java:3297)
        at java.util.regex.Pattern$Curly.match0(Pattern.java:3669)
        at java.util.regex.Pattern$Curly.match(Pattern.java:3631)
        at java.util.regex.Pattern$Curly.match0(Pattern.java:3676)
        at java.util.regex.Pattern$Curly.match(Pattern.java:3631)
        at java.util.regex.Pattern$Slice.match(Pattern.java:3297)
        at java.util.regex.Pattern$Curly.match0(Pattern.java:3676)
        at java.util.regex.Pattern$Curly.match(Pattern.java:3631)
        at java.util.regex.Pattern$Slice.match(Pattern.java:3297)
        at java.util.regex.Pattern$Curly.match0(Pattern.java:3669)
        at java.util.regex.Pattern$Curly.match(Pattern.java:3631)
        at java.util.regex.Pattern$Single.match(Pattern.java:3004)
        at java.util.regex.Pattern$Curly.match0(Pattern.java:3669)
        at java.util.regex.Pattern$Curly.match(Pattern.java:3631)
        at java.util.regex.Pattern$Slice.match(Pattern.java:3297)
        at java.util.regex.Pattern$Curly.match0(Pattern.java:3669)
        at java.util.regex.Pattern$Curly.match(Pattern.java:3631)
        at java.util.regex.Pattern$Begin.match(Pattern.java:2831)
        at java.util.regex.Matcher.match(Matcher.java:745)
        at java.util.regex.Matcher.matches(Matcher.java:388)
        at PatternProblem.main(PatternProblem.java:27)

"VM Thread" prio=1 tid=0x08086798 nid=0xccc runnable

"VM Periodic Task Thread" prio=1 tid=0x080917d0 nid=0xcd2 waiting on condition
"Suspend Checker Thread" prio=1 tid=0x0808d860 nid=0xccf runnable

REPRODUCIBILITY :
This bug can be reproduced always.

---------- BEGIN SOURCE ----------
import java.util.regex.*;

public class PatternProblem {
static final Pattern GOOD_PATTERN = Pattern.compile("^\\s*sites\\[sites\\.length\\+\\+\\]\\s*=\\s*new\\s+Array\\(.*" +
"\\s*//\\s*(\\d+).*" +
"\\s*//\\s*([^-]+).*" +
"\\s*//\\s*([^-]+).*" +
"\\s*//\\s*([^-]+).*" +
"(?sui).*$");
static final Pattern BAD_PATTERN = Pattern.compile("^\\s*sites\\[sites\\.length\\+\\+\\]\\s*=\\s*new\\s+Array\\(.*" +
"\\s*//\\s*(\\d+).*" +
"\\s*//\\s*([^-]+).*" +
"\\s*//\\s*([^-]+).*" +
"\\s*//\\s*([^-]+).*" +
"/(?sui).*$");
static final String testString = "\tsites[sites.length++] = new Array(\n" +
                                   "// 1079193366647 - creation time\n" +
"// 1078902678663 1078852539723 1078753482632 0 0 0 0 0 0 0 0 0 0 0 - creation time last 14 days\n" +
"// 0 1 0 0 0 0 0 0 0 0 0 0 0 0 - bad\n" +
"// 0.0030 0.0080 0.01 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 -\n\n";

public static final void main(final String[] a) throws Exception {
Matcher m = GOOD_PATTERN.matcher(testString);
System.out.println("Does Good Pattern match? " + m.matches());
m = BAD_PATTERN.matcher(testString);
System.out.println("Does Bad Pattern match? " + m.matches());
}
}
---------- END SOURCE ----------
(Incident Review ID: 243729)
======================================================================