[regex] Fix BZ429

[Paolo Bonzini]

To fix BZ429, it is enough to do some kind of caching and cut the number 
of invocations of calc_dst_limits_pos.  Its current implementation is 
naive: Complexity is exponential in N because every epsilon closure 
visits N backreferences: this without any hope of succeeding, because no 
OP_{OPEN,CLOSE}_SUBEXP node is reachable from the OP_BACK_REF nodes.

The tests in bug-regex11.c now complete in a sane amount of time (11 
seconds each on a G4 PowerMac), but still not exactly small so I've not 
enabled them.  Unluckily this does not speed up other testcases, but the 
profiles for these pathologic regexes look more similar to the common 
one (sift_states_bkref is at the top).

Paolo
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: 06-fix-bz429.patch
URL: <http://sourceware.org/pipermail/libc-alpha/attachments/20041110/609618b7/attachment.ksh>