re_intuit_start(): simplify other=anchored block
authorDavid Mitchell <davem@iabyn.com>
Fri, 31 Jan 2014 23:58:14 +0000 (23:58 +0000)
committerDavid Mitchell <davem@iabyn.com>
Sat, 8 Feb 2014 12:59:51 +0000 (12:59 +0000)
commite176ee937f117fc2c220e253b4134cf677626b67
treec9b909c4e460314438fd6449614ae44d55f5e2cf
parent88a35045d18338c34e942de2492f5f04dc941db9
re_intuit_start(): simplify other=anchored block

This block of code calculates 2 limits: last, last2; plus a third,
last1 = min(last, last2)

It turns out that (as explained below), last is always <= last2, which
allows us to simplify the code. In particular, this means that last always
equals last1, so eliminate last1 and always use last instead.
At the same time, rename last2 to last1, so the vars have the same names /
meanings as in the other=float branch.

Here's the math (ignoring char/byte differences for simplicity's sake):

    last  = s (== start of just matched float substr)
                    - float_min_offset
                    +  anchored_offset
    last2 = strend - minlen + anchored_offset

Let

    delta = last2 - last

          =   (strend - minlen + anchored_offset)
            - (s - float_min_offset + anchored_offset)

          =  (strend  - s) - (minlen - float_min_offset) [1]

Now, we've just matched a floating substring at s. But this previous
match was constrained to *end* no later than end_shift chars before
strend,  so it was constrained to *start* no later than
end_shift + length(float) chars before strend; i.e.

    strend - s >= end_shift + length(float) [2].

Also, more or less by definition,

    minlen = float_min_offset + length(float) + end_shift
or
    end_shift = minlen - float_min_offset - length(float) [2]

So, combining [2] and [3] gives

    strend - s >= (minlen - float_min_offset - length(float)) + length(float)
    strend - s >= minlen - float_min_offset

Therefore, from [1],

    delta >= 0
regexec.c