regex: Use ANYOFV
authorKarl Williamson <public@khwilliamson.com>
Fri, 14 Jan 2011 05:36:36 +0000 (22:36 -0700)
committerKarl Williamson <public@khwilliamson.com>
Fri, 14 Jan 2011 05:55:54 +0000 (22:55 -0700)
This patch restructures the regex ANYOF code to generate ANYOFV nodes instead
when there is a possibility that it could match more than one character.   Note
that this doesn't affect the optimizer, as it essentially ignores things that
fit into this category.  (But it means that the optimizer will no longer reject
these when it shouldn't have.)

The handling of the LATIN SHARP s is modified to correspond with this new node
type.

The initial handling of ANYOFV is placed in regexec.c.  More analysis will come
on that.  But there was significant change to the part that handles matching
multi-char strings.  This has long been buggy, with it previously comparing a
folded-version on one side with a non-folded version on the other.

This patch fixes about 60% of the problems that my undelivered test suite gives
for multi-char folds.  But there are still 17K test failures left, so I'm still
not delivering that.  The TODOs that this fixes will be cleaned up in a later commit

regcomp.c
regexec.c

index 0d91c50..b39cf5c 100644 (file)
--- a/regcomp.c
+++ b/regcomp.c
@@ -3533,7 +3533,7 @@ S_study_chunk(pTHX_ RExC_state_t *pRExC_state, regnode **scanp,
                        NEXT_OFF(oscan) += NEXT_OFF(next);
                }
                continue;
-           default:                    /* REF and CLUMP only? */
+           default:                    /* REF, ANYOFV, and CLUMP only? */
                if (flags & SCF_DO_SUBSTR) {
                    SCAN_COMMIT(pRExC_state,data,minlenp);      /* Cannot expect anything... */
                    data->longest = &(data->longest_float);
@@ -8276,17 +8276,10 @@ S_set_regclass_bit_fold(pTHX_ RExC_state_t *pRExC_state, regnode* node, const U8
         ANYOF_BITMAP_SET(node, fold);
         stored++;
     }
-
-    /* The fold of the German sharp s is two ASCII characters, so isn't in the
-     * bitmap and doesn't have to be in utf8, but we only process it if unicode
-     * semantics are called for */
-    if (UNI_SEMANTICS && value == LATIN_SMALL_LETTER_SHARP_S) {
-       ANYOF_FLAGS(node) |= ANYOF_NONBITMAP_NON_UTF8;
-    }
-    else if (_HAS_NONLATIN1_FOLD_CLOSURE_ONLY_FOR_USE_BY_REGCOMP_DOT_C_AND_REGEXEC_DOT_C(value)
-            || (! UNI_SEMANTICS
-                 && ! isASCII(value)
-                 && PL_fold_latin1[value] != value))
+    if (_HAS_NONLATIN1_FOLD_CLOSURE_ONLY_FOR_USE_BY_REGCOMP_DOT_C_AND_REGEXEC_DOT_C(value)
+       || (! UNI_SEMANTICS
+           && ! isASCII(value)
+           && PL_fold_latin1[value] != value))
     {   /* A character that has a fold outside of Latin1 matches outside the
            bitmap, but only when the target string is utf8.  Similarly when we
            don't have unicode semantics for the above ASCII Latin-1 characters,
@@ -8506,6 +8499,9 @@ parseit:
                /* The \p could match something in the Latin1 range, hence
                 * something that isn't utf8 */
                ANYOF_FLAGS(ret) |= ANYOF_NONBITMAP;
+               if (FOLD) { /* And one of these could have a multi-char fold */
+                   OP(ret) = ANYOFV;
+               }
                namedclass = ANYOF_MAX;  /* no official name, but it's named */
                }
                break;
@@ -8827,6 +8823,13 @@ parseit:
                    /* The \t sets the whole range */
                    Perl_sv_catpvf(aTHX_ listsv, "%04"UVxf"\t%04"UVxf"\n",
                                   prevnatvalue, natvalue);
+
+                   /* Currently, we don't look at every value in the range.
+                    * Therefore we have to assume the worst case: that if
+                    * folding, it will match more than one character */
+                   if (FOLD) {
+                     OP(ret) = ANYOFV;
+                   }
                }
                else if (prevnatvalue == natvalue) {
                    Perl_sv_catpvf(aTHX_ listsv, "%04"UVxf"\n", natvalue);
@@ -8875,6 +8878,7 @@ parseit:
                                  sv = newSVpvn_utf8((char*)foldbuf, foldlen,
                                                     TRUE);
                                  av_push(unicode_alternate, sv);
+                                 OP(ret) = ANYOFV;
                              }
                         }
 
@@ -8912,18 +8916,12 @@ parseit:
         return ret;
     /****** !SIZE_ONLY AFTER HERE *********/
 
-    /* Folding in the bitmap is taken care of above, but not for locale, for
-     * which we have to wait to see what folding is in effect at runtime, and
-     * for things not in the bitmap */
-    if (FOLD && (LOC || ANYOF_FLAGS(ret) & ANYOF_NONBITMAP)) {
-        ANYOF_FLAGS(ret) |= ANYOF_LOC_NONBITMAP_FOLD;
-    }
-
-    /* Optimize inverted simple patterns (e.g. [^a-z]).  Note that this doesn't
+    /* Optimize inverted simple patterns (e.g. [^a-z]).  Note that we haven't
+     * set the FOLD flag yet, so this this does optimize those.  It doesn't
      * optimize locale.  Doing so perhaps could be done as long as there is
      * nothing like \w in it; some thought also would have to be given to the
      * interaction with above 0x100 chars */
-    if ((ANYOF_FLAGS(ret) & ANYOF_FLAGS_ALL) == ANYOF_INVERT) {
+    if (! LOC && (ANYOF_FLAGS(ret) & ANYOF_FLAGS_ALL) == ANYOF_INVERT) {
        for (value = 0; value < ANYOF_BITMAP_SIZE; ++value)
            ANYOF_BITMAP(ret)[value] ^= 0xFF;
        stored = 256 - stored;
@@ -8933,6 +8931,41 @@ parseit:
        ANYOF_FLAGS(ret) = ANYOF_UTF8|ANYOF_UNICODE_ALL;
     }
 
+    if (FOLD) {
+       SV *sv;
+
+       /* This is the one character in the bitmap that needs special handling
+        * under non-locale folding, as it folds to two characters 'ss'.  This
+        * happens if it is set and not inverting, or isn't set and are
+        * inverting */
+       if (! LOC
+           && (cBOOL(ANYOF_BITMAP_TEST(ret, LATIN_SMALL_LETTER_SHARP_S))
+               ^ cBOOL(ANYOF_FLAGS(ret) & ANYOF_INVERT)))
+       {
+           OP(ret) = ANYOFV;   /* Can match more than a single char */
+
+           /* Under Unicode semantics), it can do this when the target string
+            * isn't in utf8 */
+           if (UNI_SEMANTICS) {
+               ANYOF_FLAGS(ret) |= ANYOF_NONBITMAP_NON_UTF8;
+           }
+
+           if (!unicode_alternate) {
+               unicode_alternate = newAV();
+           }
+           sv = newSVpvn_utf8("ss", 2, TRUE);
+           av_push(unicode_alternate, sv);
+       }
+
+       /* Folding in the bitmap is taken care of above, but not for locale
+        * (for which we have to wait to see what folding is in effect at
+        * runtime), and for things not in the bitmap.  Set run-time fold flag
+        * for these */
+       if ((LOC || (ANYOF_FLAGS(ret) & ANYOF_NONBITMAP))) {
+           ANYOF_FLAGS(ret) |= ANYOF_LOC_NONBITMAP_FOLD;
+       }
+    }
+
     /* A single character class can be "optimized" into an EXACTish node.
      * Note that since we don't currently count how many characters there are
      * outside the bitmap, we are XXX missing optimization possibilities for
@@ -10650,7 +10683,7 @@ S_dumpuntil(pTHX_ const regexp *r, const regnode *start, const regnode *node,
        else if ( op == PLUS || op == STAR) {
            DUMPUNTIL(NEXTOPER(node), NEXTOPER(node) + 1);
        }
-       else if (op == ANYOF) {
+       else if (PL_regkind[(U8)op] == ANYOF) {
            /* arglen 1 + class block */
            node += 1 + ((ANYOF_FLAGS(node) & ANYOF_CLASS)
                    ? ANYOF_CLASS_SKIP : ANYOF_SKIP);
index 7b69bbc..6e144fe 100644 (file)
--- a/regexec.c
+++ b/regexec.c
@@ -1364,8 +1364,9 @@ S_find_byclass(pTHX_ regexp * prog, const regnode *c, char *s,
         
        /* We know what class it must start with. */
        switch (OP(c)) {
+       case ANYOFV:
        case ANYOF:
-           if (utf8_target) {
+           if (utf8_target || OP(c) == ANYOFV) {
                 REXEC_FBC_UTF8_CLASS_SCAN((ANYOF_FLAGS(c) & ANYOF_NONBITMAP) ||
                          !UTF8_IS_INVARIANT((U8)s[0]) ?
                          reginclass(prog, c, (U8*)s, 0, utf8_target) :
@@ -3670,8 +3671,9 @@ S_regmatch(pTHX_ regmatch_info *reginfo, regnode *prog)
                                    OP(scan) == BOUNDL))
                    sayNO;
            break;
+       case ANYOFV:
        case ANYOF:
-           if (utf8_target) {
+           if (utf8_target || state_num == ANYOFV) {
                STRLEN inclasslen = PL_regeol - locinput;
                if (locinput >= PL_regeol)
                    sayNO;
@@ -3693,15 +3695,7 @@ S_regmatch(pTHX_ regmatch_info *reginfo, regnode *prog)
                break;
            }
        anyof_fail:
-           /* If we might have the case of the German sharp s
-            * in a casefolding Unicode character class. */
-
-           if (ANYOF_FOLD_SHARP_S(scan, locinput, PL_regeol)) {
-                locinput += SHARP_S_SKIP;
-                nextchr = UCHARAT(locinput);
-           }
-           else
-                sayNO;
+           sayNO;
            break;
        /* Special char classes - The defines start on line 129 or so */
         CCC_TRY_AFF_U( ALNUM,  ALNUML, perl_word,   "a", isALNUM_LC_utf8, isWORDCHAR_L1, isALNUM_LC);
@@ -5926,6 +5920,7 @@ S_regrepeat(pTHX_ const regexp *prog, const regnode *p, I32 max, int depth)
            }
        }
        break;
+    case ANYOFV:
     case ANYOF:
        if (utf8_target) {
            loceol = PL_regeol;
@@ -6414,31 +6409,158 @@ S_reginclass(pTHX_ const regexp * const prog, register const regnode * const n,
                if (utf8_target) {
                    utf8_p = (U8 *) p;
                } else {
-                   STRLEN len = 1;
+
+                   /* Not utf8.  Convert as much of the string as available up
+                    * to the limit of how far the (single) character in the
+                    * pattern can possibly match (no need to go further).  If
+                    * the node is a straight ANYOF or not folding, it can't
+                    * match more than one.  Otherwise, It can match up to how
+                    * far a single char can fold to.  Since not utf8, each
+                    * character is a single byte, so the max it can be in
+                    * bytes is the same as the max it can be in characters */
+                   STRLEN len = (OP(n) == ANYOF
+                                 || ! (flags & ANYOF_LOC_NONBITMAP_FOLD))
+                                 ? 1
+                                 : (maxlen < UTF8_MAX_FOLD_CHAR_EXPAND)
+                                   ? maxlen
+                                   : UTF8_MAX_FOLD_CHAR_EXPAND;
                    utf8_p = bytes_to_utf8(p, &len);
                }
-               if (swash_fetch(sw, utf8_p, 1))
+
+               if (swash_fetch(sw, utf8_p, 1)) /* See if in the swash */
                    match = TRUE;
                else if (flags & ANYOF_LOC_NONBITMAP_FOLD) {
-                   if (!match && lenp && av) {
+
+                   /* Here, we need to test if the fold of the target string
+                    * matches.  In the case of a multi-char fold that is
+                    * caught by regcomp.c, it has stored all such folds into
+                    * 'av'; we linearly check to see if any match the target
+                    * string (folded).   We know that the originals were each
+                    * one character, but we don't currently know how many
+                    * characters/bytes each folded to, except we do know that
+                    * there are small limits imposed by Unicode.  XXX A
+                    * performance enhancement would be to have regcomp.c store
+                    * the max number of chars/bytes that are in an av entry,
+                    * as, say the 0th element.  Further down, if there isn't a
+                    * match in the av, we will check if there is another
+                    * fold-type match.  For that, we also need the fold, but
+                    * only the first character.  No sense in folding it twice,
+                    * so we do it here, even if there isn't any multi-char
+                    * fold, so we always fold at least the first character.
+                    * If the node is a straight ANYOF node, or there is only
+                    * one character available in the string, or if there isn't
+                    * any av, that's all we have to fold.  In the case of a
+                    * multi-char fold, we do have guarantees in Unicode that
+                    * it can only expand up to so many characters and so many
+                    * bytes.  We keep track so don't exceed either.
+                    *
+                    * If there is a match, we will need to advance (if lenp is
+                    * specified) the match pointer in the target string.  But
+                    * what we are comparing here isn't that string directly,
+                    * but its fold, whose length may differ from the original.
+                    * As we go along in constructing the fold, therefore, we
+                    * create a map so that we know how many bytes in the
+                    * source to advance given that we have matched a certain
+                    * number of bytes in the fold.  This map is stored in
+                    * 'map_fold_len_back'.  The first character in the fold
+                    * has array element 1 contain the number of bytes in the
+                    * source that folded to it; the 2nd is the cumulative
+                    * number to match it; ... */
+                   U8 map_fold_len_back[UTF8_MAX_FOLD_CHAR_EXPAND] = { 0 };
+                   U8 folded[UTF8_MAXBYTES_CASE+1];
+                   STRLEN foldlen = 0; /* num bytes in fold of 1st char */
+                   STRLEN foldlen_for_av; /* num bytes in fold of all chars */
+
+                   if (OP(n) == ANYOF || maxlen == 1 || ! lenp || ! av) {
+
+                       /* Here, only need to fold the first char of the target
+                        * string */
+                       to_utf8_fold(utf8_p, folded, &foldlen);
+                       foldlen_for_av = foldlen;
+                       map_fold_len_back[1] = UTF8SKIP(utf8_p);
+                   }
+                   else {
+
+                       /* Here, need to fold more than the first char.  Do so
+                        * up to the limits */
+                       UV which_char = 0;
+                       U8* source_ptr = utf8_p;    /* The source for the fold
+                                                      is the regex target
+                                                      string */
+                       U8* folded_ptr = folded;
+                       U8* e = utf8_p + maxlen;    /* Can't go beyond last
+                                                      available byte in the
+                                                      target string */
+                       while (which_char < UTF8_MAX_FOLD_CHAR_EXPAND
+                              && source_ptr < e)
+                       {
+
+                           /* Fold the next character */
+                           U8 this_char_folded[UTF8_MAXBYTES_CASE+1];
+                           STRLEN this_char_foldlen;
+                           to_utf8_fold(source_ptr,
+                                        this_char_folded,
+                                        &this_char_foldlen);
+
+                           /* Bail if it would exceed the byte limit for
+                            * folding a single char. */
+                           if (this_char_foldlen + folded_ptr - folded >
+                                                           UTF8_MAXBYTES_CASE)
+                           {
+                               break;
+                           }
+
+                           /* Save the first character's folded length, in
+                            * case we have to use it later */
+                           if (! foldlen) {
+                               foldlen = this_char_foldlen;
+                           }
+
+                           /* Here, add the fold of this character */
+                           Copy(this_char_folded,
+                                folded_ptr,
+                                this_char_foldlen,
+                                U8);
+                           which_char++;
+                           map_fold_len_back[which_char] =
+                               map_fold_len_back[which_char - 1]
+                               + UTF8SKIP(source_ptr);
+                           folded_ptr += this_char_foldlen;
+                           source_ptr += UTF8SKIP(source_ptr);
+                       }
+                       *folded_ptr = '\0';
+                       foldlen_for_av = folded_ptr - folded;
+                   }
+
+
+                   /* Do the linear search to see if the fold is in the list
+                    * of multi-char folds.  (Useless to look if won't be able
+                    * to store that it is a multi-char fold in *lenp) */
+                   if (lenp && av) {
                        I32 i;
                        for (i = 0; i <= av_len(av); i++) {
                            SV* const sv = *av_fetch(av, i, FALSE);
                            STRLEN len;
                            const char * const s = SvPV_const(sv, len);
-                           if (len <= maxlen && memEQ(s, (char*)utf8_p, len)) {
-                               *lenp = len;
+                           if (len <= foldlen_for_av && memEQ(s,
+                                                              (char*)folded,
+                                                              len))
+                           {
+
+                               /* Advance the target string ptr to account for
+                                * this fold, but have to translate from the
+                                * folded length to the corresponding source
+                                * length.  The array is indexed by how many
+                                * characters in the match */
+                               *lenp = map_fold_len_back[
+                                       utf8_length(folded, folded + len)];
                                match = TRUE;
                                break;
                            }
                        }
                    }
                    if (!match) { /* See if the folded version matches */
-                       U8 folded[UTF8_MAXBYTES_CASE+1];
                        SV** listp;
-                       STRLEN foldlen;
-
-                       to_utf8_fold(utf8_p, folded, &foldlen);
 
                        /* Consider "k" =~ /[K]/i.  The line above would have
                         * just folded the 'k' to itself, and that isn't going