Branch: refs/heads/smoke-me/khw-pr3
Home: https://github.com/Perl/perl5
Commit: 1daf05f4cfa0e4c9806b2017cee45083b443d391
https://github.com/Perl/perl5/commit/1daf05f4cfa0e4c9806b2017cee45083b443d391
Author: Karl Williamson <[email protected]>
Date: 2020-11-18 (Wed, 18 Nov 2020)
Changed paths:
M regcharclass.h
M regen/regcharclass.pl
Log Message:
-----------
regen/regcharclass.pl: Rmv special case
This avoided checking for optimizations. Whatever its original use, it
doesn't do any good, and the optimizations are actually useful.
Commit: 1886b90bbe67d3eff88af56b4cd893bd685a29d7
https://github.com/Perl/perl5/commit/1886b90bbe67d3eff88af56b4cd893bd685a29d7
Author: Karl Williamson <[email protected]>
Date: 2020-11-18 (Wed, 18 Nov 2020)
Changed paths:
M regcharclass.h
M regen/regcharclass.pl
M regen/regcharclass_multi_char_folds.pl
Log Message:
-----------
regcharclass.pl: Get code point folding to a seq
Previously regcharclass.pl could tell if an input string was a
multi-character fold of some Unicode code point. This commit adds the
ability to return what that code point is. This capability will be used
in a later commit.
Commit: df78f5b2fc208a887facaf86549f3377982bf53c
https://github.com/Perl/perl5/commit/df78f5b2fc208a887facaf86549f3377982bf53c
Author: Karl Williamson <[email protected]>
Date: 2020-11-18 (Wed, 18 Nov 2020)
Changed paths:
M regexec.c
Log Message:
-----------
regexec.c: Trim trailing blanks
Commit: e89da447d4e079b8774f0da402bd352f3b640405
https://github.com/Perl/perl5/commit/e89da447d4e079b8774f0da402bd352f3b640405
Author: Karl Williamson <[email protected]>
Date: 2020-11-18 (Wed, 18 Nov 2020)
Changed paths:
M regexec.c
Log Message:
-----------
regexec.c: Change name of static function
The new name reflects its new generality coming in future commits
Commit: 384527f452b2a0fac1256404601af35fabfff4ae
https://github.com/Perl/perl5/commit/384527f452b2a0fac1256404601af35fabfff4ae
Author: Karl Williamson <[email protected]>
Date: 2020-11-18 (Wed, 18 Nov 2020)
Changed paths:
M regexec.c
M regexp.h
Log Message:
-----------
regexec.c: Revamp looping end conditions
Consider the pattern /A*B/ where A and B are arbitrary. The pattern
matching code tries to make a tight loop to match the span of A's. The
logic of this was not really updated when UTF-8 was added. A function
was called that essentially punted when UTF-8 was involved. I did
revamp the function some releases ago to fix some bugs and to consider
UTF-8 to a limited extent.
This commit revamps the whole mechanism so that now UTF-8 is a first
class citizen, and improves the loop exit criteria for non-UTF-8 as
well.
The old code returned FALSE if there was no possiblility of
anything matching (such as the match requiring UTF-8 to represent and
the target isn't UTF-8 encoded). If there was a match possibility it
returned TRUE and 1 or 2 code points that could be the first things
in B if A is something like '.*'. Or in the case of A being a single
repeating character, those 1 or 2 code points could be what 'A' matched
under /i, the thing(s) being spanned. For other situations it gave up
and returned 0 code points. In this case, the caller had to check for
every eventuality, and in the case of /i had to re-fold each backtrack.
Like the old one, the new function introduced here returns FALSE if
there is no possibility of a match succeeding, but unlike the old one it
never gives up. If the return is TRUE, It also always returns:
1) A string and a mask to quickly rule out non-matches
2) A count of initial bytes that are exact matches, and a count of
initial definitive matches
3) The first character of all possible matches
The caller does a bitwise 'and' of the target string with the returned
mask. If that doesn't match the returned string, then the caller can
immediately rule out this match. If the mask is all one bits, then
there are no false positives. This will always be the case if the
function is called on an exact match, one without /i.
ikewise, if just a single 0 bit is in the mask, there are just two
possible matches, both returned by this function, and the match is
definitive for these, with no false positives. The more 0 bits in the
mask, the more false positives there are, but it still quickly rules out
the remaining ones. This is graceful degradation, unlike the mechanism
it replaces.
When the counts of initial exact and definitive match bytes are non-zero
(a likely scenario), the caller can use this to cut down the number of
brute force tests it must do.
Finally, having the exact strings of what can possibly match means no
need to refold when backtracking.
Here are some examples.
In an EXACT node, the mask returned will be all one bits, and the
returned string will be the first character of the node. The caller
will AND the mask with the target string and see if it matches the
returned string. This is not very different from before, except that
the caller doesn't have to check each time if 0, 1, or 2 characters were
returned from the function, and then behave accordingly. Only if the
match succeeds, does it need to check if this was a definitive match or
not.
More complex is
qr/.*\N{U+100}/i
Only U+100 and U+101 match. The old way knew this and returned those
code points and the two UTF-8 strings that represent them: \xC4\x80 and
\xC4\x81. There were a bunch of conditionals in the old way to
determine to use the UTF-8 strings, and to compare each one separately.
The mask and string returned in the new way uses a single compare and
mask, dispensing with the code point returns completely.
The old way was optimized for ASCII characters, and the new way doesn't
improve that for the ones whose only matches are their upper and lowercase
versions. But for those with matches outside of ASCII, the old one gave
up and the caller had to resort to brute force matching each time,
whereas the new one always returns something that can quickly rule out
many possibilities. An example is
qr/.*\N{LATIN SMALL LETTER K}/i
'K', 'k', and the KELVIN SIGN all match. Here is a detailed analysis of
this case to show the complexities involved.
This pattern is too complicated for the code prior to this commit to
deal with; brute force needed to be used to check for matches. The new
code returns the mask 0x56, and a string 0x42. There are 4 zero bits in
this mask. That means that the code can immediately reject all but 16
of the possible bytes that could follow it. The ones it accepts are:
0x82 83 8A 8B
A2 A3 AA AB
C2 C3 CA CB
E2 E3 EA EB
If the target string isn't UTF-8 encoded, this excludes 240 of 256
bytes, all 16 that are accepted are non-ASCII and 4 of them are
extremely rare control characters. If you're dealing with just ASCII
inputs, it's a 0% false positive rate; otherwise the false positive rate
of 3% or 6%, depending on if you count those controls.
If the target string is UTF-8 encoded, the first 8 bytes in the list
above are illegal start bytes. The 4 Cx bytes are the beginning of
2-byte representations, each of which has 64 possible continuation
bytes, so any of 256 characters could match, out of the possible 1792
legal 2-UTF-8-byte characters, a 14% false positive rate
The 4 Ex bytes are the beginning of 3-byte representations, each of
which has 64-squared possible continuation bytes, so any of 16384
characters could match, out the possible 63488 legal 3-UTF-8-byte
characters, a 26% false positive rate.
All 4-byte, 5-byte, etc., representations are excluded, so the total
false positive rate approaches 0% if we include all possible UTF-8
sequences. If we confine the input domain to just the million legal
Unicode code points, the false positive rate is 1%, but, except for
emoji, most characters in any sort of common use are represented by 3 or
fewer bytes, and the false positive rate is about 25%, but only the
characters common to multiple scripts or Latin ones in that domain
are likely to occur in text with 'k' and 'K'. There are 4758 of these
in the current version of the Unicode standard, of which this could
potentially match 3500, or 76%, if all were equally likely to occur
immediately after one of these 'K'-characters. One could do further
restrictions, such as using only modern, non-technical characters to get
wildly differing false positive rates.
But whatever the false positive rate, it is better than the brute force
method required prior to this commit.
Finally, perhaps the worst case fold in Unicode is that of
\N{GREEK SMALL LETTER IOTA WITH DIALYTIKA AND OXIA}. There are 6
characters that match this under /i. As a result, the mask and returned
string have lots of false positives. But they still immediately rule
out all characters that aren't represented by 2 or 3 bytes, and any 2
byte characters that begin with D0-DF.
Compare: https://github.com/Perl/perl5/compare/1daf05f4cfa0%5E...384527f452b2
