#22023 [Com]: Non-termination problems with certain patterns.

ID: 22023 Comment by: cryo@tiscali.dk Reported By: cryo@tiscali.dk Status: Bogus Bug Type: PCRE related Operating System: Mandrake 9.0 Linux PHP Version: 4.3.1-dev, 5.0.0-dev New Comment: Alright, after more careful study I reached the same conclusion. Also, it's hardly even a bug as such in PCRE but more a consequence of the NFA approach to regular expression matching that the library takes, allowing for a extremely high number of potential matches in patterns like the one I posted. Previous Comments: ------------------------------------------------------------------------ [2003-02-03 15:31:58] iliaa@php.net Sorry, but your problem does not imply a bug in PHP itself. For a list of more appropriate places to ask for help using PHP, please visit http://www.php.net/support.php as this bug system is not the appropriate forum for asking support questions. Thank you for your interest in PHP. This is indeed a bug, however it is not a PHP bug, but rather a bug in the PCRE library, which is not particular to the bundled PCRE library. If you use the PCRE's pcretest command to execute the regular expression shown by sniper@php.net you'll notice that the utility will also 'hang' indefinately consuming all avaliable CPU (unterminated loop?). ------------------------------------------------------------------------ [2003-02-03 03:34:25] sniper@php.net <?php $foo = "test AAthis is a test of some text inside end."; var_dump(preg_match("/AA(([^A]*A?[^A]+)+)AA/", $foo)); ?> This just hangs. ------------------------------------------------------------------------ [2003-02-02 17:38:56] cryo@tiscali.dk This is most likely a bug in the PCRE library. It happens with certain patterns in a no-match situation. Consider the following pattern: /AA(([^A]*A?[^A]+)+)AA/ The letter A doesn't matter. This allows the matching of 'AA' delimited strings, while still allowing single A's inside such strings. Note that /AA(.*)AA/ will not work, since it will just match the outermost enclosing of such a string. Now when matching for instance: test AAthis is a test of some text insideAA end. This works fine, and returns right away with preg_match or preg_replace alike. Also with ereg it works fine (without the / pattern delimiters of course). Now consider the similar string: test AAthis is a test of some text inside end. The delimiter at the end was removed. Now both preg_match and preg_replace time out after the maximum execution time of 30 seconds. ereg still works fine. The longer the text after the opening AA, the longer time it takes. This is long enough to never finish (within the allotted time), while shorter texts will make it finish after e.g. 20 seconds or so. ------------------------------------------------------------------------ -- Edit this bug report at http://bugs.php.net/?id=22023&edit=1