Uploaded image for project: 'JDK'
  1. JDK
  2. JDK-6693451

RegEx matcher goes into infinite delay

    Details

    • Type: Bug
    • Status: Resolved
    • Priority: P4
    • Resolution: Fixed
    • Affects Version/s: 6
    • Fix Version/s: 9
    • Component/s: core-libs
    • Labels:
    • Subcomponent:
    • Resolved In Build:
      b119
    • CPU:
      x86
    • OS:
      windows_xp

      Description

      FULL PRODUCT VERSION :
      java version "1.6.0"
      Java(TM) SE Runtime Environment (build 1.6.0-b105)
      Java HotSpot(TM) Client VM (build 1.6.0-b105, mixed mode)

      ADDITIONAL OS VERSION INFORMATION :
      Microsoft Windows XP [Version 5.1.2600]

      A DESCRIPTION OF THE PROBLEM :
      Following the general discussion on http://perlmonks.org/index.pl?node_id=502408 regarding java / perl regex handling (this link is a good reading for a deep understanding of the problem) the following regular expression

      ^(\s*foo\s*)*$

      was tested using the input string

      foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo fo

      (note the ending is "fo" and not "foo")

      which results in a program execution of the Matcher.find() method that will take hundreds of years to finish (exponential duration) rendering this method useless in cases of the same nature like the simplified sample above.



      STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
      Execute the source code provided as a test case

      EXPECTED VERSUS ACTUAL BEHAVIOR :
      EXPECTED -
      Method executing within a few milliseconds
      ACTUAL -
      Method has an exponential execution time (de-facto infinite execution time)

      REPRODUCIBILITY :
      This bug can be reproduced always.

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

          public class JavaBugRegEx {
              public static final void main(String[] args) {
                  System.out.println("Start");
                  final Pattern pattern = Pattern.compile("^(\\s*foo\\s*)*$");
                  System.out.println("Compiled pattern");
                  final Matcher matcher = pattern.matcher("foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo foo fo");
                  System.out.println("Created matcher");
                  final boolean found = matcher.find();
                  System.out.println("Finished (found="+found+")");
              }
          }
      ---------- END SOURCE ----------

        Attachments

          Activity

            People

            • Assignee:
              sherman Xueming Shen
              Reporter:
              ndcosta Nelson Dcosta
            • Votes:
              0 Vote for this issue
              Watchers:
              1 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved:
                Imported:
                Indexed: