Bug 14850

Summary: Search gets frozen for a pattern
Product: ORO Reporter: Andras Soltesz <soltesz_andras>
Component: MainAssignee: Jakarta Notifications Mailing List <notifications>
Status: CLOSED INVALID    
Severity: blocker    
Priority: P3    
Version: 2.0.6   
Target Milestone: ---   
Hardware: PC   
OS: Windows XP   

Description Andras Soltesz 2002-11-26 13:29:29 UTC 
I'm searching in program code (ORACLE PL/SQL, package specification) for a package definition 
(package header). 
The search expression I use "package( +)((\w+|\W+)+)( +)is( +|\n)"

I 
have a test search at which ORO gets frozen.
----------------------------------
package "dlfk"."isam" is
 isa varchar2(10);
 
procedure isa_as;
end;
----------------------------------

I tested it with the demonstration applet of the ORO 
documentation as well and it produced the same result (getting frozen).
Comment 1 Daniel F. Savarese 2002-11-26 14:24:12 UTC 
Although the behavior is not desirable, it is not quite a bug.  Both Perl
5.003_07 and Perl-5.005.03 behave the same way.  For example:

perl5.003_07/perl -e  '@foo=<STDIN>; $bar=join("", @foo); print "$bar"; if (
$bar =~ /package( +)((\w+|\W+)+)( +)is( +|\n)/) { print "MATCH!\n"; }' < foo.txt

and

perl-5.005.03/perl -e  '@foo=<STDIN>; $bar=join("", @foo); print "$bar"; if (
$bar =~ /package( +)((\w+|\W+)+)( +)is( +|\n)/) { print "MATCH!\n"; }' < foo.txt

where foo.txt contains:

----------------------------------
package "dlfk"."isam" is
 isa varchar2(10);
 
procedure isa_as;
end;
----------------------------------

This will be fixed as we move to Perl 5.6 compatibility, but right now, we
do the same as Perl 5.00x.

It is important to remember that regular expressions are state machines and
are not guaranteed to terminate.  You have to craft reasonable expressions
that do not result in excessive or even infinite backtracking and recursion.
The problem is easily solved by simplifying the regular expression to the
more accurate:
  package( +)((\w|\W)+)( +)is( +|\n)
Notice how (\w+|\W+)+ is equivalent to (\w|\W)+ in what it matches.  The
expression can be further simplified because "\w|\W" is equivalent to "."

We would rather you ask for help on oro-dev before using the bug reporting
system.
Comment 2 Daniel F. Savarese 2004-11-07 16:00:23 UTC 
This issues been resolved for a long while.  Therefore I'm closing it.