regcomp utf8 len cache panic

Compiling this regex:

    /\x{100}[xy]\x{100}{2}/

caused this:

    panic: sv_len_utf8 cache 1 real 2

This was due to the code in S_study_chunk() mixing up char and byte
lengths when updating the utf8 length cache on a utf8 string that
had been extended by repeatedly duplicating the last n chars.

(The second test is for an issue introduced during an initial attempt to
fix this).
re_intuit_start(): re-indent a block of code

(whitespace-only changes)

A block of code had a confusing mixture of 4- and 2-space indents.
Re-indent to be consistently 4 chars. Also, wrap some long lines
and add a few blank lines for clarity.
RT#120692 slow intuit with long utf8 strings

Some code in re_intuit_start() that tries to find the range of chars
to which the BM substr find can be applied, uses logic that is very
inefficient once utf8 was enabled. Basically the code tries to find
the maximum end-point where the substr could be found, by taking the
minimum of:

    * start + prog->check_offset_max + length(substr)
    * end   - prog->check_end_shift

Except that these values are in char lengths and need to be converted to
bytes before calling fbm_instr(). The code formerly involved scanning the
whole of the remaining string to determine how many chars it had.
By doing the calculation a different way, we can avoid this.

This makes the following two regexps each take milliseconds rather than
10s of seconds:

        my $s = 'ab' x 1_000_000;
        utf8::upgrade($s);
        1 while $s =~ m/\Ga+ba+b/g;
        $s=~ /^a{1,2}x/ for  1..10_000;
regexp.h: document the fields of reg_substr_datum

In particular, specify that the various offset fields are char rather
than byte counts.
re_intuit_start(): factor out some common code

3 assignments are done at the end of both branches of an if/else;
factor them out after the end.
re_intuit_start(): merge two similar code branches

When the check string is anchored at a fixed offset from the start
of the string (e.g. /^..abc/), there are two similar code branches
that do a quick memNE() reject - the difference being whether SvTAIL() is
true, i.e. whether the pattern ends with $ and may match a \n.

Merge the common bits of the two branches. Technically this makes the
non-SvTAIL() branch slightly less efficient, since it will always retrieve
SvCUR(check) even when its not needed, but in practice it will already be
in the cache since we have to access SvPVX(check), and the I-cache misses
will have been reduced by reducing the code size.

It also removes one label.
re_intuit_start(); eliminate max_shift var

I introduced this var a few commits ago, but after a bit of refactoring,
I can now eliminate it and just use its antecedents directly.
re_intuit_start(): rationalise ml_anch var

Make ml_anch bool rather than I32, since that's all its used for.
Also, unconditionally initialise it to zero then only set where needed.
This eliminates an else branch that just sets it to zero.
re_intuit_start(): refactor an if/else block

change

    if (X) { do nothing } else if (Y) { Z }

to
    if (!X && Y) { Z }
re_intuit_start(): add comments to a block of code

explain what it does!
eliminate RXf_ANCH_SINGLE

This macro defines two flag bits:

    #define PREGf_ANCH_SINGLE         (PREGf_ANCH_SBOL|PREGf_ANCH_GPOS)

but is only used twice in core (and not on CPAN),
don't really add any value, but increases cognitive complexity.
test for single-line ^ within /m

This combo doesn't appear to be tested anywhere; specifically, adding this
in re_intuit_start() didn't trigger the assertion when run against the
test suite:

    if (prog->extflags & RXf_ANCH_BOL)
        assert(!multiline);
re_intuit_start(): simplify ml_anch evaluation

rather than enumerating all the anchor flag combos where ml_anch *isn't*
true, enumerate the flags for which is *is* true. This is slighly simpler
logic, and involves once less negation, which makes it easier to
understand.
re_intuit_start(): add more debugging output

Add some debugging output to some parts of the code without them, so it's
easier to follow progress through intuit(); also add an initial "we're in
intuit" message.

Make all the debugging output, apart from the initial and final intuit
messages, indented by 2 chars so that they are seen to be things happening
within intuit.

Dump the susbtrs data array.

Fix up a few of the existing outputs to be more informative.
re_intuit_start(): document floating code better

Add some comments to the float-finding code that explains what the t, last
and last1 vars are, and how they're calculated.

Also make the calculation of last separate from last1;
it should logically be the same, but clearer. i.e. change

    last = last1 = ...;
    if (cond)
        last = ....;

to

    last1 = ...;
    last = cond ? .... : last1;
re_intuit_start(): fix another utf8 slowdown

The code that looks for a floating substr after a fixed substr has
already been found, was very slow on long utf8 strings. For example
this used to take an hour or more, and now takes millisecs:

    $s = "ab" x 1_000_000;
    utf8::upgrade($s);
    $s =~ /ab.{1,2}x/;

When calculating the maximum position at which the floating substr could
start, there are two possible upper limits.

First, the absolute max position, ignoring the results of the previous
fixed substr match - this is the end-of-string less a bit (last1);

Second, float_max_offset on from the current origin of the regex (this
is dependent on where the fixed substr previously matched).

To decide which of these two values to use (the smaller), it used to
calculate the distance in chars from the regex origin to last1, and if
this was greater than float_max_offset, it used origin + float_max_offset
(in chars) instead.

This distance calculation involved doing a utf8 length calculation on the
majority of the string, which for long strings was a big slowdown.

Fix this by instead always using HOP3(origin + float_max_offset), but
using last1 as the upper HOP limit rather than strend, so it's always
limited to <= last1.

If L is number of chars that had to be hopped over for the distance
calculation (which could be most of the string), and if M is the
chars hopped for origin +  float_max_offset (typically either small or
infinite), then we:

    previously hopped: (M>=L ? L : L+M) chars
    now hop:           min(L,M) chars; or if M is infinite, hop 0 chars

Which is always less than or equal to the amount of work done previously,
and is a very big win for long strings with smallish maximum float
offsets.
re_intuit_start(): assert substr offsets are >= 0.

Some parts of this function handle the negative offset case, while other
parts don't. Also, nothing in the test suite generates negative offsets.

So for now, assert that all offsets are positive, and strip out any
code that handles negative offsets. This will make my current activity
in fixing and refactoring this function easier. If at some future point
someone wants to add support for negative offsets (e.g. with look-behind)
then they'll have to add support fully to re_intuit_start() from scratch.
re_intuit_start(): delete srch_(start|end)_shift

remove these two vars; these are now just unmodified copies of
start_shift, end_shift; so just use those two vars directly.
re_intuit_start(): add some more code comments
re_intuit_start(): bias last* vars; revive reghop4

In the "just matched float substr, now match fixed substr" branch,
initially add an extra prog->anchored_offset to the last and last2 vars;
since a lot of the later calculations involve adding anchored_offset,
doing this early to the last* vars means less work in some cases. In
particular, last is calculated from s by a single

    HOP4(s, prog->anchored_offset-start_shift,...)

rather than two separate

    HOP3(s,   -start_shift,...);
    HOP3(..., prog->anchored_offset,...);

which may mostly cancel each other out.

Similarly with last2. Later, we can skip adding prog->anchored_offset to
last1, since its antecedents already have the bias added.

In the case of failure, calculating a new start position involves an extra
HOP to s, but removes a HOP from other_last, so the two cancel out.

To make this work, I revived the reghop4() function which had been
commented out, and added a HOP4c() wrapper macro. This is like HOP3c(),
but allows you to specify both lower and upper limits. Useful when you
don't know the sign of the offset in advance.

(Yves had earlier added this function, but had commented it out until such
time as it was actually used.)

I also added some extra comments to this block and removed the comment
about it being maybe broken under utf8, since I'm auditing the code for
utf8-safeness.