Skip to content
Commit f3dc1890 authored by David Mitchell's avatar David Mitchell Committed by Niko Tyni
Browse files

simpify and speed up /.*.../ handling

See RT ##123743.

A pattern that starts /.*/ has a fake MBOL or SBOL flag added, along
with PREGf_IMPLICIT.

The idea is that, with /.*.../s, if the NFA don't match when started at
pos 0, then it's not going to match if started at any other position
either; while /.*.../ won't match at any other start position up until
the next \n.

However, the branch in regexec() that implemented this was a bit a mess
(like much in the perl core, it had gradually accreted), and caused
intuit-enabled /.*.../ and /.*...patterns to go quadratic.

The branch looked roughly like:

    if (anchored) {
        if (regtry(s)) goto success;
        if (can_intuit) {
            while (s < end) {
                s = intuit(s+1);
                if (!s) goto fail;
                if (regtry(s)) goto success;
            }
        }
        else {
            while (s < end) {
                s = skip_to_next_newline(s);
                if (regtry(s)) goto success;
            }
        }
    }

The problem is that in the presence of a .* at the start of the pattern,
intuit() will always return either NULL on failure, or the start position,
rather than any later position. So the can_intuit branch above calls
regtry() on every character position.

This commit fixes this by changing the structure of the code to be like
this, where it only tries things on newline boundaries:

    if (anchored) {
        if (regtry(s)) goto success;
        while (1) {
            s = skip_to_next_newline(s);
            if (can_intuit) {
                s = intuit(s+1);
                if (!s) goto fail;
            }
            if (regtry(s)) goto success;
        }
    }

This makes the code a lot simpler, and mostly avoids quadratic behaviour
(you can still get it with a string consisting mainly of newlines).

(backported for 5.20.1 by Niko Tyni <ntyni@debian.org>)

Bug: https://rt.perl.org/Public/Bug/Display.html?id=123743
Bug-Debian: https://bugs.debian.org/777556
Origin: http://perl5.git.perl.org/perl.git/commitdiff/0fa70a06a98fc8fa9840d4dbaa31fc2d3b28b99b
Patch-Name: fixes/regexp-performance.diff
parent ce572cc9
0% or .
You are about to add 0 people to the discussion. Proceed with caution.
Finish editing this message first!
Please register or to comment