re_intuit_start(): use better limit on anch float
authorDavid Mitchell <davem@iabyn.com>
Tue, 18 Mar 2014 23:36:20 +0000 (23:36 +0000)
committerDavid Mitchell <davem@iabyn.com>
Wed, 19 Mar 2014 18:25:55 +0000 (18:25 +0000)
commite0362b861b7abfc19b44160e65c0d94b98ae924b
tree900ce4ad0762bed72a8b8ac8bfff19d434f429ab
parent7bb3b9eb56c4b9374abfae3780eeb77c607bb1a5
re_intuit_start(): use better limit on anch float

The 'check' block of code has special handling for if the pattern is
anchored; in this case, it allows us to set an upper bound on where a
floating substring might match; e.g. in

    /^..\d?abc/

the floating string can't be more than 3 chars from the absolute beginning
of the string. Similarly with /..\G\d?abc/, it can't be more than 3 chars
from the start position (assuming that position been calculated correctly
by the caller).

However, the current code used rx_origin as the base for the offset
calculation, rather than strbeg/strpos as appropriate. This meant that

a) the first time round the loop, if strpos > strbeg, then the upper bound
would be set higher than needed;
b) if we ever go back to restart: with an incremented rx_origin, then the
upper limit is recalculated with more wasted slack at the latter end.

This commit changes the limit calculation, which reduces the following
from second to milliseconds:

    $s = "abcdefg" x 1_000_000;
    $s =~ /^XX\d{1,10}cde/ for 1..100;

It also adds a quick test to skip hopping when the result is likely to
leave end_point unchanged, and adds an explicit test for !PREGf_IMPLICIT.
This latter test isn't strictly necessary, as if PREGf_IMPLICIT were set,
it implies that the pattern starts with '.*', which implies that
prog->check_offset_max == SSize_t_MAX, which is already tested for.
However, it makes the overall condition more comprehensible, and makes it
more robust in the face of future changes.
regexec.c
t/re/pat.t