Bug 8

Summary: Quadratic behavior on regex with * at the beginning
Product: glibc Reporter: Paolo Bonzini <bonzini>
Component: regexAssignee: Paolo Bonzini <bonzini>
Status: RESOLVED FIXED    
Severity: normal CC: fweimer
Priority: P2 Flags: fweimer: security+
Version: unspecified   
Target Milestone: ---   
Host: Target:
Build: Last reconfirmed:
Attachments: Proposed patch

Description Paolo Bonzini 2004-02-02 14:59:59 UTC
perl -e 'print ("a" x 10000) . "b\n"' | (time sed -n 's/a*b//') 
real    0m1.986s 
user    0m1.900s 
sys     0m0.010s 
 
perl -e 'print ("a" x 20000) . "b\n"' | (time sed -n 's/a*b//') 
real    0m7.977s 
user    0m7.720s 
sys     0m0.030s 
 
When searching forward, the fastmap should be complemented by some heuristic 
to skip optional parts of the regex, like the "a"s in the above testcase.
Comment 1 Paolo Bonzini 2004-02-02 15:00:48 UTC
Created attachment 2 [details]
Proposed patch


2004-02-02  Paolo Bonzini  <bonzini@gnu.org>

	* posix/regexec.c (check_matching): Add P_MATCH_FIRST
	parameter.
	(re_search_internal): Pass new parameter to check_matching.
	(check_matching): Unless a parenthesized group is found at the
	beginning of the regexp, advance P_MATCH_FIRST until we entered
	a state different from the initial state.
Comment 2 Paolo Bonzini 2004-02-03 09:02:13 UTC
Attached patch applied by Ulrich.