X-Git-Url: https://perl5.git.perl.org/perl5.git/blobdiff_plain/61a36c016d02518f6bc19ca7f7d1b5a51cc47d49..4b6dd97a16e9a5ba7782d6c0bdac29cff4a29dc4:/regcomp.c diff --git a/regcomp.c b/regcomp.c index bf1b42f..8c1abc5 100644 --- a/regcomp.c +++ b/regcomp.c @@ -5,6 +5,16 @@ * "A fair jaw-cracker dwarf-language must be." --Samwise Gamgee */ +/* This file contains functions for compiling a regular expression. See + * also regexec.c which funnily enough, contains functions for executing + * a regular expression. + * + * This file is also copied at build time to ext/re/re_comp.c, where + * it's built with -DPERL_EXT_RE_BUILD -DPERL_EXT_RE_DEBUG -DPERL_EXT. + * This causes the main functions to be compiled under new names and with + * debugging support added, which makes "use re 'debug'" work. + */ + /* NOTE: this is derived from Henry Spencer's regexp code, and should not * confused with the original package (see point 3 below). Thanks, Henry! */ @@ -69,7 +79,8 @@ * **** Alterations to Henry's code are... **** - **** Copyright (c) 1991-2001, Larry Wall + **** Copyright (C) 1991, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999, + **** 2000, 2001, 2002, 2003, 2004, 2005, by Larry Wall and others **** **** You may distribute under the terms of either the GNU General Public **** License or the Artistic License, as specified in the README file. @@ -95,12 +106,12 @@ #endif /* op */ #ifdef MSDOS -# if defined(BUGGY_MSC6) +# if defined(BUGGY_MSC6) /* MSC 6.00A breaks on op/regexp.t test 85 unless we turn this off */ - # pragma optimize("a",off) +# pragma optimize("a",off) /* But MSC 6.00A is happy with 'w', for aliases only across function calls*/ - # pragma optimize("w",on ) -# endif /* BUGGY_MSC6 */ +# pragma optimize("w",on ) +# endif /* BUGGY_MSC6 */ #endif /* MSDOS */ #ifndef STATIC @@ -108,7 +119,7 @@ #endif typedef struct RExC_state_t { - U16 flags16; /* are we folding, multilining? */ + U32 flags; /* are we folding, multilining? */ char *precomp; /* uncompiled string. */ regexp *rx; char *start; /* Start of input for compile */ @@ -132,7 +143,7 @@ typedef struct RExC_state_t { #endif } RExC_state_t; -#define RExC_flags16 (pRExC_state->flags16) +#define RExC_flags (pRExC_state->flags) #define RExC_precomp (pRExC_state->precomp) #define RExC_rx (pRExC_state->rx) #define RExC_start (pRExC_state->start) @@ -195,8 +206,8 @@ typedef struct scan_data_t { * Forward declarations for pregcomp()'s friends. */ -static scan_data_t zero_scan_data = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, - 0, 0, 0, 0, 0, 0}; +static const scan_data_t zero_scan_data = + { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; #define SF_BEFORE_EOL (SF_BEFORE_SEOL|SF_BEFORE_MEOL) #define SF_BEFORE_SEOL 0x1 @@ -227,9 +238,9 @@ static scan_data_t zero_scan_data = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, #define SCF_DO_STCLASS (SCF_DO_STCLASS_AND|SCF_DO_STCLASS_OR) #define SCF_WHILEM_VISITED_POS 0x2000 -#define UTF RExC_utf8 -#define LOC (RExC_flags16 & PMf_LOCALE) -#define FOLD (RExC_flags16 & PMf_FOLD) +#define UTF (RExC_utf8 != 0) +#define LOC ((RExC_flags & PMf_LOCALE) != 0) +#define FOLD ((RExC_flags & PMf_FOLD) != 0) #define OOB_UNICODE 12345678 #define OOB_NAMEDCLASS -1 @@ -256,184 +267,159 @@ static scan_data_t zero_scan_data = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, * arg. Show regex, up to a maximum length. If it's too long, chop and add * "...". */ -#define FAIL(msg) \ - STMT_START { \ - char *ellipses = ""; \ - IV len = RExC_end - RExC_precomp; \ - \ - if (!SIZE_ONLY) \ - SAVEDESTRUCTOR_X(clear_re,(void*)RExC_rx); \ - \ - if (len > RegexLengthToShowInErrorMessages) { \ - /* chop 10 shorter than the max, to ensure meaning of "..." */ \ - len = RegexLengthToShowInErrorMessages - 10; \ - ellipses = "..."; \ - } \ - Perl_croak(aTHX_ "%s in regex m/%.*s%s/", \ - msg, (int)len, RExC_precomp, ellipses); \ - } STMT_END +#define FAIL(msg) STMT_START { \ + const char *ellipses = ""; \ + IV len = RExC_end - RExC_precomp; \ + \ + if (!SIZE_ONLY) \ + SAVEDESTRUCTOR_X(clear_re,(void*)RExC_rx); \ + if (len > RegexLengthToShowInErrorMessages) { \ + /* chop 10 shorter than the max, to ensure meaning of "..." */ \ + len = RegexLengthToShowInErrorMessages - 10; \ + ellipses = "..."; \ + } \ + Perl_croak(aTHX_ "%s in regex m/%.*s%s/", \ + msg, (int)len, RExC_precomp, ellipses); \ +} STMT_END /* * Calls SAVEDESTRUCTOR_X if needed, then calls Perl_croak with the given * args. Show regex, up to a maximum length. If it's too long, chop and add * "...". */ -#define FAIL2(pat,msg) \ - STMT_START { \ - char *ellipses = ""; \ - IV len = RExC_end - RExC_precomp; \ - \ - if (!SIZE_ONLY) \ - SAVEDESTRUCTOR_X(clear_re,(void*)RExC_rx); \ - \ - if (len > RegexLengthToShowInErrorMessages) { \ - /* chop 10 shorter than the max, to ensure meaning of "..." */ \ - len = RegexLengthToShowInErrorMessages - 10; \ - ellipses = "..."; \ - } \ - S_re_croak2(aTHX_ pat, " in regex m/%.*s%s/", \ - msg, (int)len, RExC_precomp, ellipses); \ - } STMT_END +#define FAIL2(pat,msg) STMT_START { \ + const char *ellipses = ""; \ + IV len = RExC_end - RExC_precomp; \ + \ + if (!SIZE_ONLY) \ + SAVEDESTRUCTOR_X(clear_re,(void*)RExC_rx); \ + if (len > RegexLengthToShowInErrorMessages) { \ + /* chop 10 shorter than the max, to ensure meaning of "..." */ \ + len = RegexLengthToShowInErrorMessages - 10; \ + ellipses = "..."; \ + } \ + S_re_croak2(aTHX_ pat, " in regex m/%.*s%s/", \ + msg, (int)len, RExC_precomp, ellipses); \ +} STMT_END /* * Simple_vFAIL -- like FAIL, but marks the current location in the scan */ -#define Simple_vFAIL(m) \ - STMT_START { \ - IV offset = RExC_parse - RExC_precomp; \ - \ - Perl_croak(aTHX_ "%s" REPORT_LOCATION, \ - m, (int)offset, RExC_precomp, RExC_precomp + offset); \ - } STMT_END +#define Simple_vFAIL(m) STMT_START { \ + IV offset = RExC_parse - RExC_precomp; \ + Perl_croak(aTHX_ "%s" REPORT_LOCATION, \ + m, (int)offset, RExC_precomp, RExC_precomp + offset); \ +} STMT_END /* * Calls SAVEDESTRUCTOR_X if needed, then Simple_vFAIL() */ -#define vFAIL(m) \ - STMT_START { \ - if (!SIZE_ONLY) \ - SAVEDESTRUCTOR_X(clear_re,(void*)RExC_rx); \ - Simple_vFAIL(m); \ - } STMT_END +#define vFAIL(m) STMT_START { \ + if (!SIZE_ONLY) \ + SAVEDESTRUCTOR_X(clear_re,(void*)RExC_rx); \ + Simple_vFAIL(m); \ +} STMT_END /* * Like Simple_vFAIL(), but accepts two arguments. */ -#define Simple_vFAIL2(m,a1) \ - STMT_START { \ - IV offset = RExC_parse - RExC_precomp; \ - \ - S_re_croak2(aTHX_ m, REPORT_LOCATION, a1, \ - (int)offset, RExC_precomp, RExC_precomp + offset); \ - } STMT_END +#define Simple_vFAIL2(m,a1) STMT_START { \ + IV offset = RExC_parse - RExC_precomp; \ + S_re_croak2(aTHX_ m, REPORT_LOCATION, a1, \ + (int)offset, RExC_precomp, RExC_precomp + offset); \ +} STMT_END /* * Calls SAVEDESTRUCTOR_X if needed, then Simple_vFAIL2(). */ -#define vFAIL2(m,a1) \ - STMT_START { \ - if (!SIZE_ONLY) \ - SAVEDESTRUCTOR_X(clear_re,(void*)RExC_rx); \ - Simple_vFAIL2(m, a1); \ - } STMT_END +#define vFAIL2(m,a1) STMT_START { \ + if (!SIZE_ONLY) \ + SAVEDESTRUCTOR_X(clear_re,(void*)RExC_rx); \ + Simple_vFAIL2(m, a1); \ +} STMT_END /* * Like Simple_vFAIL(), but accepts three arguments. */ -#define Simple_vFAIL3(m, a1, a2) \ - STMT_START { \ - IV offset = RExC_parse - RExC_precomp; \ - \ - S_re_croak2(aTHX_ m, REPORT_LOCATION, a1, a2, \ - (int)offset, RExC_precomp, RExC_precomp + offset); \ - } STMT_END +#define Simple_vFAIL3(m, a1, a2) STMT_START { \ + IV offset = RExC_parse - RExC_precomp; \ + S_re_croak2(aTHX_ m, REPORT_LOCATION, a1, a2, \ + (int)offset, RExC_precomp, RExC_precomp + offset); \ +} STMT_END /* * Calls SAVEDESTRUCTOR_X if needed, then Simple_vFAIL3(). */ -#define vFAIL3(m,a1,a2) \ - STMT_START { \ - if (!SIZE_ONLY) \ - SAVEDESTRUCTOR_X(clear_re,(void*)RExC_rx); \ - Simple_vFAIL3(m, a1, a2); \ - } STMT_END +#define vFAIL3(m,a1,a2) STMT_START { \ + if (!SIZE_ONLY) \ + SAVEDESTRUCTOR_X(clear_re,(void*)RExC_rx); \ + Simple_vFAIL3(m, a1, a2); \ +} STMT_END /* * Like Simple_vFAIL(), but accepts four arguments. */ -#define Simple_vFAIL4(m, a1, a2, a3) \ - STMT_START { \ - IV offset = RExC_parse - RExC_precomp; \ - \ - S_re_croak2(aTHX_ m, REPORT_LOCATION, a1, a2, a3,\ - (int)offset, RExC_precomp, RExC_precomp + offset); \ - } STMT_END +#define Simple_vFAIL4(m, a1, a2, a3) STMT_START { \ + IV offset = RExC_parse - RExC_precomp; \ + S_re_croak2(aTHX_ m, REPORT_LOCATION, a1, a2, a3, \ + (int)offset, RExC_precomp, RExC_precomp + offset); \ +} STMT_END /* * Like Simple_vFAIL(), but accepts five arguments. */ -#define Simple_vFAIL5(m, a1, a2, a3, a4) \ - STMT_START { \ - IV offset = RExC_parse - RExC_precomp; \ - S_re_croak2(aTHX_ m, REPORT_LOCATION, a1, a2, a3, a4,\ - (int)offset, RExC_precomp, RExC_precomp + offset); \ - } STMT_END - - -#define vWARN(loc,m) \ - STMT_START { \ - IV offset = loc - RExC_precomp; \ - Perl_warner(aTHX_ WARN_REGEXP, "%s" REPORT_LOCATION,\ - m, (int)offset, RExC_precomp, RExC_precomp + offset); \ - } STMT_END \ - -#define vWARNdep(loc,m) \ - STMT_START { \ - IV offset = loc - RExC_precomp; \ - int warn_cat = ckWARN(WARN_REGEXP) ? WARN_REGEXP : WARN_DEPRECATED; \ - Perl_warner(aTHX_ warn_cat, "%s" REPORT_LOCATION,\ - m, (int)offset, RExC_precomp, RExC_precomp + offset); \ - } STMT_END \ - - -#define vWARN2(loc, m, a1) \ - STMT_START { \ - IV offset = loc - RExC_precomp; \ - Perl_warner(aTHX_ WARN_REGEXP, m REPORT_LOCATION,\ - a1, \ - (int)offset, RExC_precomp, RExC_precomp + offset); \ - } STMT_END - -#define vWARN3(loc, m, a1, a2) \ - STMT_START { \ - IV offset = loc - RExC_precomp; \ - Perl_warner(aTHX_ WARN_REGEXP, m REPORT_LOCATION, \ - a1, a2, \ - (int)offset, RExC_precomp, RExC_precomp + offset); \ - } STMT_END - -#define vWARN4(loc, m, a1, a2, a3) \ - STMT_START { \ - IV offset = loc - RExC_precomp; \ - Perl_warner(aTHX_ WARN_REGEXP, m REPORT_LOCATION,\ - a1, a2, a3, \ - (int)offset, RExC_precomp, RExC_precomp + offset); \ - } STMT_END - -/* used for the parse_flags section for (?c) -- japhy */ -#define vWARN5(loc, m, a1, a2, a3, a4) \ - STMT_START { \ - IV offset = loc - RExC_precomp; \ - Perl_warner(aTHX_ WARN_REGEXP, m REPORT_LOCATION, \ - a1, a2, a3, a4, \ - (int)offset, RExC_precomp, RExC_precomp + offset); \ - } STMT_END +#define Simple_vFAIL5(m, a1, a2, a3, a4) STMT_START { \ + IV offset = RExC_parse - RExC_precomp; \ + S_re_croak2(aTHX_ m, REPORT_LOCATION, a1, a2, a3, a4, \ + (int)offset, RExC_precomp, RExC_precomp + offset); \ +} STMT_END + + +#define vWARN(loc,m) STMT_START { \ + IV offset = loc - RExC_precomp; \ + Perl_warner(aTHX_ packWARN(WARN_REGEXP), "%s" REPORT_LOCATION, \ + m, (int)offset, RExC_precomp, RExC_precomp + offset); \ +} STMT_END + +#define vWARNdep(loc,m) STMT_START { \ + IV offset = loc - RExC_precomp; \ + Perl_warner(aTHX_ packWARN2(WARN_DEPRECATED, WARN_REGEXP), \ + "%s" REPORT_LOCATION, \ + m, (int)offset, RExC_precomp, RExC_precomp + offset); \ +} STMT_END + + +#define vWARN2(loc, m, a1) STMT_START { \ + IV offset = loc - RExC_precomp; \ + Perl_warner(aTHX_ packWARN(WARN_REGEXP), m REPORT_LOCATION, \ + a1, (int)offset, RExC_precomp, RExC_precomp + offset); \ +} STMT_END + +#define vWARN3(loc, m, a1, a2) STMT_START { \ + IV offset = loc - RExC_precomp; \ + Perl_warner(aTHX_ packWARN(WARN_REGEXP), m REPORT_LOCATION, \ + a1, a2, (int)offset, RExC_precomp, RExC_precomp + offset); \ +} STMT_END + +#define vWARN4(loc, m, a1, a2, a3) STMT_START { \ + IV offset = loc - RExC_precomp; \ + Perl_warner(aTHX_ packWARN(WARN_REGEXP), m REPORT_LOCATION, \ + a1, a2, a3, (int)offset, RExC_precomp, RExC_precomp + offset); \ +} STMT_END + +#define vWARN5(loc, m, a1, a2, a3, a4) STMT_START { \ + IV offset = loc - RExC_precomp; \ + Perl_warner(aTHX_ packWARN(WARN_REGEXP), m REPORT_LOCATION, \ + a1, a2, a3, a4, (int)offset, RExC_precomp, RExC_precomp + offset); \ +} STMT_END /* Allow for side effects in s */ -#define REGC(c,s) STMT_START { if (!SIZE_ONLY) *(s) = (c); else (void)(s);} STMT_END +#define REGC(c,s) STMT_START { \ + if (!SIZE_ONLY) *(s) = (c); else (void)(s); \ +} STMT_END /* Macros for recording node offsets. 20001227 mjd@plover.com * Nodes are numbered 1, 2, 3, 4. Node #n's position is recorded in @@ -442,38 +428,42 @@ static scan_data_t zero_scan_data = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, */ #define MJD_OFFSET_DEBUG(x) -/* #define MJD_OFFSET_DEBUG(x) fprintf x */ - - -# define Set_Node_Offset_To_R(node,byte) \ - STMT_START { \ - if (! SIZE_ONLY) { \ - if((node) < 0) { \ - Perl_croak(aTHX_ "value of node is %d in Offset macro", node); \ - } else { \ - RExC_offsets[2*(node)-1] = (byte); \ - } \ - } \ - } STMT_END - -# define Set_Node_Offset(node,byte) Set_Node_Offset_To_R((node)-RExC_emit_start, (byte)-RExC_start) -# define Set_Cur_Node_Offset Set_Node_Offset(RExC_emit, RExC_parse) - -# define Set_Node_Length_To_R(node,len) \ - STMT_START { \ - if (! SIZE_ONLY) { \ - MJD_OFFSET_DEBUG((stderr, "** (%d) size of node %d is %d.\n", __LINE__, (node), (len))); \ - if((node) < 0) { \ - Perl_croak(aTHX_ "value of node is %d in Length macro", node); \ - } else { \ - RExC_offsets[2*(node)] = (len); \ - } \ - } \ - } STMT_END - -# define Set_Node_Length(node,len) Set_Node_Length_To_R((node)-RExC_emit_start, len) -# define Set_Cur_Node_Length(len) Set_Node_Length(RExC_emit, len) -# define Set_Node_Cur_Length(node) Set_Node_Length(node, RExC_parse - parse_start) +/* #define MJD_OFFSET_DEBUG(x) DEBUG_r(Perl_warn_nocontext x) */ + + +#define Set_Node_Offset_To_R(node,byte) STMT_START { \ + if (! SIZE_ONLY) { \ + MJD_OFFSET_DEBUG(("** (%d) offset of node %d is %d.\n", \ + __LINE__, (node), (byte))); \ + if((node) < 0) { \ + Perl_croak(aTHX_ "value of node is %d in Offset macro", node); \ + } else { \ + RExC_offsets[2*(node)-1] = (byte); \ + } \ + } \ +} STMT_END + +#define Set_Node_Offset(node,byte) \ + Set_Node_Offset_To_R((node)-RExC_emit_start, (byte)-RExC_start) +#define Set_Cur_Node_Offset Set_Node_Offset(RExC_emit, RExC_parse) + +#define Set_Node_Length_To_R(node,len) STMT_START { \ + if (! SIZE_ONLY) { \ + MJD_OFFSET_DEBUG(("** (%d) size of node %d is %d.\n", \ + __LINE__, (node), (len))); \ + if((node) < 0) { \ + Perl_croak(aTHX_ "value of node is %d in Length macro", node); \ + } else { \ + RExC_offsets[2*(node)] = (len); \ + } \ + } \ +} STMT_END + +#define Set_Node_Length(node,len) \ + Set_Node_Length_To_R((node)-RExC_emit_start, len) +#define Set_Cur_Node_Length(len) Set_Node_Length(RExC_emit, len) +#define Set_Node_Cur_Length(node) \ + Set_Node_Length(node, RExC_parse - parse_start) /* Get offsets and lengths */ #define Node_Offset(n) (RExC_offsets[2*((n)-RExC_emit_start)-1]) @@ -488,11 +478,11 @@ static void clear_re(pTHX_ void *r); STATIC void S_scan_commit(pTHX_ RExC_state_t *pRExC_state, scan_data_t *data) { - STRLEN l = CHR_SVLEN(data->last_found); - STRLEN old_l = CHR_SVLEN(*data->longest); + const STRLEN l = CHR_SVLEN(data->last_found); + const STRLEN old_l = CHR_SVLEN(*data->longest); if ((l >= old_l) && ((l > old_l) || (data->flags & SF_BEFORE_EOL))) { - sv_setsv(*data->longest, data->last_found); + SvSetMagicSV(*data->longest, data->last_found); if (*data->longest == data->longest_fixed) { data->offset_fixed = l ? data->last_start_min : data->pos_min; if (data->flags & SF_BEFORE_EOL) @@ -506,6 +496,8 @@ S_scan_commit(pTHX_ RExC_state_t *pRExC_state, scan_data_t *data) data->offset_float_max = (l ? data->last_start_max : data->pos_min + data->pos_delta); + if ((U32)data->offset_float_max > (U32)I32_MAX) + data->offset_float_max = I32_MAX; if (data->flags & SF_BEFORE_EOL) data->flags |= ((data->flags & SF_BEFORE_EOL) << SF_FL_SHIFT_EOL); @@ -514,6 +506,13 @@ S_scan_commit(pTHX_ RExC_state_t *pRExC_state, scan_data_t *data) } } SvCUR_set(data->last_found, 0); + { + SV * sv = data->last_found; + MAGIC *mg = + SvUTF8(sv) && SvMAGICAL(sv) ? mg_find(sv, PERL_MAGIC_utf8) : NULL; + if (mg && mg->mg_len > 0) + mg->mg_len = 0; + } data->last_end = -1; data->flags &= ~SF_BEFORE_EOL; } @@ -587,14 +586,17 @@ S_cl_and(pTHX_ struct regnode_charclass_class *cl, if (!(and_with->flags & ANYOF_EOS)) cl->flags &= ~ANYOF_EOS; - if (cl->flags & ANYOF_UNICODE_ALL && and_with->flags & ANYOF_UNICODE) { + if (cl->flags & ANYOF_UNICODE_ALL && and_with->flags & ANYOF_UNICODE && + !(and_with->flags & ANYOF_INVERT)) { cl->flags &= ~ANYOF_UNICODE_ALL; cl->flags |= ANYOF_UNICODE; ARG_SET(cl, ARG(and_with)); } - if (!(and_with->flags & ANYOF_UNICODE_ALL)) + if (!(and_with->flags & ANYOF_UNICODE_ALL) && + !(and_with->flags & ANYOF_INVERT)) cl->flags &= ~ANYOF_UNICODE_ALL; - if (!(and_with->flags & (ANYOF_UNICODE|ANYOF_UNICODE_ALL))) + if (!(and_with->flags & (ANYOF_UNICODE|ANYOF_UNICODE_ALL)) && + !(and_with->flags & ANYOF_INVERT)) cl->flags &= ~ANYOF_UNICODE; } @@ -659,6 +661,882 @@ S_cl_or(pTHX_ RExC_state_t *pRExC_state, struct regnode_charclass_class *cl, str } /* + + make_trie(startbranch,first,last,tail,flags) + startbranch: the first branch in the whole branch sequence + first : start branch of sequence of branch-exact nodes. + May be the same as startbranch + last : Thing following the last branch. + May be the same as tail. + tail : item following the branch sequence + flags : currently the OP() type we will be building one of /EXACT(|F|Fl)/ + +Inplace optimizes a sequence of 2 or more Branch-Exact nodes into a TRIE node. + +A trie is an N'ary tree where the branches are determined by digital +decomposition of the key. IE, at the root node you look up the 1st character and +follow that branch repeat until you find the end of the branches. Nodes can be +marked as "accepting" meaning they represent a complete word. Eg: + + /he|she|his|hers/ + +would convert into the following structure. Numbers represent states, letters +following numbers represent valid transitions on the letter from that state, if +the number is in square brackets it represents an accepting state, otherwise it +will be in parenthesis. + + +-h->+-e->[3]-+-r->(8)-+-s->[9] + | | + | (2) + | | + (1) +-i->(6)-+-s->[7] + | + +-s->(3)-+-h->(4)-+-e->[5] + + Accept Word Mapping: 3=>1 (he),5=>2 (she), 7=>3 (his), 9=>4 (hers) + +This shows that when matching against the string 'hers' we will begin at state 1 +read 'h' and move to state 2, read 'e' and move to state 3 which is accepting, +then read 'r' and go to state 8 followed by 's' which takes us to state 9 which +is also accepting. Thus we know that we can match both 'he' and 'hers' with a +single traverse. We store a mapping from accepting to state to which word was +matched, and then when we have multiple possibilities we try to complete the +rest of the regex in the order in which they occured in the alternation. + +The only prior NFA like behaviour that would be changed by the TRIE support is +the silent ignoring of duplicate alternations which are of the form: + + / (DUPE|DUPE) X? (?{ ... }) Y /x + +Thus EVAL blocks follwing a trie may be called a different number of times with +and without the optimisation. With the optimisations dupes will be silently +ignored. This inconsistant behaviour of EVAL type nodes is well established as +the following demonstrates: + + 'words'=~/(word|word|word)(?{ print $1 })[xyz]/ + +which prints out 'word' three times, but + + 'words'=~/(word|word|word)(?{ print $1 })S/ + +which doesnt print it out at all. This is due to other optimisations kicking in. + +Example of what happens on a structural level: + +The regexp /(ac|ad|ab)+/ will produce the folowing debug output: + + 1: CURLYM[1] {1,32767}(18) + 5: BRANCH(8) + 6: EXACT (16) + 8: BRANCH(11) + 9: EXACT (16) + 11: BRANCH(14) + 12: EXACT (16) + 16: SUCCEED(0) + 17: NOTHING(18) + 18: END(0) + +This would be optimizable with startbranch=5, first=5, last=16, tail=16 +and should turn into: + + 1: CURLYM[1] {1,32767}(18) + 5: TRIE(16) + [Words:3 Chars Stored:6 Unique Chars:4 States:5 NCP:1] + + + + 16: SUCCEED(0) + 17: NOTHING(18) + 18: END(0) + +Cases where tail != last would be like /(?foo|bar)baz/: + + 1: BRANCH(4) + 2: EXACT (8) + 4: BRANCH(7) + 5: EXACT (8) + 7: TAIL(8) + 8: EXACT (10) + 10: END(0) + +which would be optimizable with startbranch=1, first=1, last=7, tail=8 +and would end up looking like: + + 1: TRIE(8) + [Words:2 Chars Stored:6 Unique Chars:5 States:7 NCP:1] + + + 7: TAIL(8) + 8: EXACT (10) + 10: END(0) + +*/ + +#define TRIE_DEBUG_CHAR \ + DEBUG_TRIE_COMPILE_r({ \ + SV *tmp; \ + if ( UTF ) { \ + tmp = newSVpv( "", 0 ); \ + pv_uni_display( tmp, uc, len, 60, UNI_DISPLAY_REGEX ); \ + } else { \ + tmp = Perl_newSVpvf_nocontext( "%c", (int)uvc ); \ + } \ + av_push( trie->revcharmap, tmp ); \ + }) + +#define TRIE_READ_CHAR STMT_START { \ + if ( UTF ) { \ + if ( folder ) { \ + if ( foldlen > 0 ) { \ + uvc = utf8n_to_uvuni( scan, UTF8_MAXLEN, &len, uniflags ); \ + foldlen -= len; \ + scan += len; \ + len = 0; \ + } else { \ + uvc = utf8n_to_uvuni( (const U8*)uc, UTF8_MAXLEN, &len, uniflags);\ + uvc = to_uni_fold( uvc, foldbuf, &foldlen ); \ + foldlen -= UNISKIP( uvc ); \ + scan = foldbuf + UNISKIP( uvc ); \ + } \ + } else { \ + uvc = utf8n_to_uvuni( (const U8*)uc, UTF8_MAXLEN, &len, uniflags);\ + } \ + } else { \ + uvc = (U32)*uc; \ + len = 1; \ + } \ +} STMT_END + + +#define TRIE_LIST_ITEM(state,idx) (trie->states[state].trans.list)[ idx ] +#define TRIE_LIST_CUR(state) ( TRIE_LIST_ITEM( state, 0 ).forid ) +#define TRIE_LIST_LEN(state) ( TRIE_LIST_ITEM( state, 0 ).newstate ) +#define TRIE_LIST_USED(idx) ( trie->states[state].trans.list ? (TRIE_LIST_CUR( idx ) - 1) : 0 ) + +#define TRIE_LIST_PUSH(state,fid,ns) STMT_START { \ + if ( TRIE_LIST_CUR( state ) >=TRIE_LIST_LEN( state ) ) { \ + TRIE_LIST_LEN( state ) *= 2; \ + Renew( trie->states[ state ].trans.list, \ + TRIE_LIST_LEN( state ), reg_trie_trans_le ); \ + } \ + TRIE_LIST_ITEM( state, TRIE_LIST_CUR( state ) ).forid = fid; \ + TRIE_LIST_ITEM( state, TRIE_LIST_CUR( state ) ).newstate = ns; \ + TRIE_LIST_CUR( state )++; \ +} STMT_END + +#define TRIE_LIST_NEW(state) STMT_START { \ + Newz( 1023, trie->states[ state ].trans.list, \ + 4, reg_trie_trans_le ); \ + TRIE_LIST_CUR( state ) = 1; \ + TRIE_LIST_LEN( state ) = 4; \ +} STMT_END + +STATIC I32 +S_make_trie(pTHX_ RExC_state_t *pRExC_state, regnode *startbranch, regnode *first, regnode *last, regnode *tail, U32 flags) +{ + dVAR; + /* first pass, loop through and scan words */ + reg_trie_data *trie; + regnode *cur; + const U32 uniflags = ckWARN(WARN_UTF8) ? 0 : UTF8_ALLOW_ANY; + STRLEN len = 0; + UV uvc = 0; + U16 curword = 0; + U32 next_alloc = 0; + /* we just use folder as a flag in utf8 */ + const U8 * const folder = ( flags == EXACTF + ? PL_fold + : ( flags == EXACTFL + ? PL_fold_locale + : NULL + ) + ); + + const U32 data_slot = add_data( pRExC_state, 1, "t" ); + SV *re_trie_maxbuff; + + GET_RE_DEBUG_FLAGS_DECL; + + Newz( 848200, trie, 1, reg_trie_data ); + trie->refcount = 1; + RExC_rx->data->data[ data_slot ] = (void*)trie; + Newz( 848201, trie->charmap, 256, U16 ); + DEBUG_r({ + trie->words = newAV(); + trie->revcharmap = newAV(); + }); + + + re_trie_maxbuff = get_sv(RE_TRIE_MAXBUF_NAME, 1); + if (!SvIOK(re_trie_maxbuff)) { + sv_setiv(re_trie_maxbuff, RE_TRIE_MAXBUF_INIT); + } + + /* -- First loop and Setup -- + + We first traverse the branches and scan each word to determine if it + contains widechars, and how many unique chars there are, this is + important as we have to build a table with at least as many columns as we + have unique chars. + + We use an array of integers to represent the character codes 0..255 + (trie->charmap) and we use a an HV* to store unicode characters. We use the + native representation of the character value as the key and IV's for the + coded index. + + *TODO* If we keep track of how many times each character is used we can + remap the columns so that the table compression later on is more + efficient in terms of memory by ensuring most common value is in the + middle and the least common are on the outside. IMO this would be better + than a most to least common mapping as theres a decent chance the most + common letter will share a node with the least common, meaning the node + will not be compressable. With a middle is most common approach the worst + case is when we have the least common nodes twice. + + */ + + + for ( cur = first ; cur < last ; cur = regnext( cur ) ) { + regnode *noper = NEXTOPER( cur ); + const U8 *uc = (U8*)STRING( noper ); + const U8 *e = uc + STR_LEN( noper ); + STRLEN foldlen = 0; + U8 foldbuf[ UTF8_MAXBYTES_CASE + 1 ]; + const U8 *scan = (U8*)NULL; + + for ( ; uc < e ; uc += len ) { + trie->charcount++; + TRIE_READ_CHAR; + if ( uvc < 256 ) { + if ( !trie->charmap[ uvc ] ) { + trie->charmap[ uvc ]=( ++trie->uniquecharcount ); + if ( folder ) + trie->charmap[ folder[ uvc ] ] = trie->charmap[ uvc ]; + TRIE_DEBUG_CHAR; + } + } else { + SV** svpp; + if ( !trie->widecharmap ) + trie->widecharmap = newHV(); + + svpp = hv_fetch( trie->widecharmap, (char*)&uvc, sizeof( UV ), 1 ); + + if ( !svpp ) + Perl_croak( aTHX_ "error creating/fetching widecharmap entry for 0x%"UVXf, uvc ); + + if ( !SvTRUE( *svpp ) ) { + sv_setiv( *svpp, ++trie->uniquecharcount ); + TRIE_DEBUG_CHAR; + } + } + } + trie->wordcount++; + } /* end first pass */ + DEBUG_TRIE_COMPILE_r( + PerlIO_printf( Perl_debug_log, "TRIE(%s): W:%d C:%d Uq:%d \n", + ( trie->widecharmap ? "UTF8" : "NATIVE" ), trie->wordcount, + (int)trie->charcount, trie->uniquecharcount ) + ); + + + /* + We now know what we are dealing with in terms of unique chars and + string sizes so we can calculate how much memory a naive + representation using a flat table will take. If it's over a reasonable + limit (as specified by ${^RE_TRIE_MAXBUF}) we use a more memory + conservative but potentially much slower representation using an array + of lists. + + At the end we convert both representations into the same compressed + form that will be used in regexec.c for matching with. The latter + is a form that cannot be used to construct with but has memory + properties similar to the list form and access properties similar + to the table form making it both suitable for fast searches and + small enough that its feasable to store for the duration of a program. + + See the comment in the code where the compressed table is produced + inplace from the flat tabe representation for an explanation of how + the compression works. + + */ + + + if ( (IV)( ( trie->charcount + 1 ) * trie->uniquecharcount + 1) > SvIV(re_trie_maxbuff) ) { + /* + Second Pass -- Array Of Lists Representation + + Each state will be represented by a list of charid:state records + (reg_trie_trans_le) the first such element holds the CUR and LEN + points of the allocated array. (See defines above). + + We build the initial structure using the lists, and then convert + it into the compressed table form which allows faster lookups + (but cant be modified once converted). + + + */ + + + STRLEN transcount = 1; + + Newz( 848204, trie->states, trie->charcount + 2, reg_trie_state ); + TRIE_LIST_NEW(1); + next_alloc = 2; + + for ( cur = first ; cur < last ; cur = regnext( cur ) ) { + + regnode *noper = NEXTOPER( cur ); + U8 *uc = (U8*)STRING( noper ); + U8 *e = uc + STR_LEN( noper ); + U32 state = 1; /* required init */ + U16 charid = 0; /* sanity init */ + U8 *scan = (U8*)NULL; /* sanity init */ + STRLEN foldlen = 0; /* required init */ + U8 foldbuf[ UTF8_MAXBYTES_CASE + 1 ]; + + + for ( ; uc < e ; uc += len ) { + + TRIE_READ_CHAR; + + if ( uvc < 256 ) { + charid = trie->charmap[ uvc ]; + } else { + SV** svpp=(SV**)NULL; + svpp = hv_fetch( trie->widecharmap, (char*)&uvc, sizeof( UV ), 0); + if ( !svpp ) { + charid = 0; + } else { + charid=(U16)SvIV( *svpp ); + } + } + if ( charid ) { + + U16 check; + U32 newstate = 0; + + charid--; + if ( !trie->states[ state ].trans.list ) { + TRIE_LIST_NEW( state ); + } + for ( check = 1; check <= TRIE_LIST_USED( state ); check++ ) { + if ( TRIE_LIST_ITEM( state, check ).forid == charid ) { + newstate = TRIE_LIST_ITEM( state, check ).newstate; + break; + } + } + if ( ! newstate ) { + newstate = next_alloc++; + TRIE_LIST_PUSH( state, charid, newstate ); + transcount++; + } + state = newstate; + + } else { + Perl_croak( aTHX_ "panic! In trie construction, no char mapping for %"IVdf, uvc ); + } + /* charid is now 0 if we dont know the char read, or nonzero if we do */ + } + + if ( !trie->states[ state ].wordnum ) { + /* we havent inserted this word into the structure yet. */ + trie->states[ state ].wordnum = ++curword; + + DEBUG_r({ + /* store the word for dumping */ + SV* tmp = newSVpvn( STRING( noper ), STR_LEN( noper ) ); + if ( UTF ) SvUTF8_on( tmp ); + av_push( trie->words, tmp ); + }); + + } else { + /* Its a dupe. So ignore it. */ + } + + } /* end second pass */ + + trie->laststate = next_alloc; + Renew( trie->states, next_alloc, reg_trie_state ); + + DEBUG_TRIE_COMPILE_MORE_r({ + U32 state; + U16 charid; + + /* + print out the table precompression. + */ + + PerlIO_printf( Perl_debug_log, "\nState :Word | Transition Data\n" ); + PerlIO_printf( Perl_debug_log, "------:-----+-----------------" ); + + for( state=1 ; state < next_alloc ; state ++ ) { + + PerlIO_printf( Perl_debug_log, "\n %04"UVXf" :", (UV)state ); + if ( ! trie->states[ state ].wordnum ) { + PerlIO_printf( Perl_debug_log, "%5s| ",""); + } else { + PerlIO_printf( Perl_debug_log, "W%04x| ", + trie->states[ state ].wordnum + ); + } + for( charid = 1 ; charid <= TRIE_LIST_USED( state ) ; charid++ ) { + SV **tmp = av_fetch( trie->revcharmap, TRIE_LIST_ITEM(state,charid).forid, 0); + PerlIO_printf( Perl_debug_log, "%s:%3X=%04"UVXf" | ", + SvPV_nolen( *tmp ), + TRIE_LIST_ITEM(state,charid).forid, + (UV)TRIE_LIST_ITEM(state,charid).newstate + ); + } + + } + PerlIO_printf( Perl_debug_log, "\n\n" ); + }); + + Newz( 848203, trie->trans, transcount ,reg_trie_trans ); + { + U32 state; + U16 idx; + U32 tp = 0; + U32 zp = 0; + + + for( state=1 ; state < next_alloc ; state ++ ) { + U32 base=0; + + /* + DEBUG_TRIE_COMPILE_MORE_r( + PerlIO_printf( Perl_debug_log, "tp: %d zp: %d ",tp,zp) + ); + */ + + if (trie->states[state].trans.list) { + U16 minid=TRIE_LIST_ITEM( state, 1).forid; + U16 maxid=minid; + + + for( idx = 2 ; idx <= TRIE_LIST_USED( state ) ; idx++ ) { + if ( TRIE_LIST_ITEM( state, idx).forid < minid ) { + minid=TRIE_LIST_ITEM( state, idx).forid; + } else if ( TRIE_LIST_ITEM( state, idx).forid > maxid ) { + maxid=TRIE_LIST_ITEM( state, idx).forid; + } + } + if ( transcount < tp + maxid - minid + 1) { + transcount *= 2; + Renew( trie->trans, transcount, reg_trie_trans ); + Zero( trie->trans + (transcount / 2), transcount / 2 , reg_trie_trans ); + } + base = trie->uniquecharcount + tp - minid; + if ( maxid == minid ) { + U32 set = 0; + for ( ; zp < tp ; zp++ ) { + if ( ! trie->trans[ zp ].next ) { + base = trie->uniquecharcount + zp - minid; + trie->trans[ zp ].next = TRIE_LIST_ITEM( state, 1).newstate; + trie->trans[ zp ].check = state; + set = 1; + break; + } + } + if ( !set ) { + trie->trans[ tp ].next = TRIE_LIST_ITEM( state, 1).newstate; + trie->trans[ tp ].check = state; + tp++; + zp = tp; + } + } else { + for ( idx=1; idx <= TRIE_LIST_USED( state ) ; idx++ ) { + U32 tid = base - trie->uniquecharcount + TRIE_LIST_ITEM( state, idx ).forid; + trie->trans[ tid ].next = TRIE_LIST_ITEM( state, idx ).newstate; + trie->trans[ tid ].check = state; + } + tp += ( maxid - minid + 1 ); + } + Safefree(trie->states[ state ].trans.list); + } + /* + DEBUG_TRIE_COMPILE_MORE_r( + PerlIO_printf( Perl_debug_log, " base: %d\n",base); + ); + */ + trie->states[ state ].trans.base=base; + } + trie->lasttrans = tp + 1; + } + } else { + /* + Second Pass -- Flat Table Representation. + + we dont use the 0 slot of either trans[] or states[] so we add 1 to each. + We know that we will need Charcount+1 trans at most to store the data + (one row per char at worst case) So we preallocate both structures + assuming worst case. + + We then construct the trie using only the .next slots of the entry + structs. + + We use the .check field of the first entry of the node temporarily to + make compression both faster and easier by keeping track of how many non + zero fields are in the node. + + Since trans are numbered from 1 any 0 pointer in the table is a FAIL + transition. + + There are two terms at use here: state as a TRIE_NODEIDX() which is a + number representing the first entry of the node, and state as a + TRIE_NODENUM() which is the trans number. state 1 is TRIE_NODEIDX(1) and + TRIE_NODENUM(1), state 2 is TRIE_NODEIDX(2) and TRIE_NODENUM(3) if there + are 2 entrys per node. eg: + + A B A B + 1. 2 4 1. 3 7 + 2. 0 3 3. 0 5 + 3. 0 0 5. 0 0 + 4. 0 0 7. 0 0 + + The table is internally in the right hand, idx form. However as we also + have to deal with the states array which is indexed by nodenum we have to + use TRIE_NODENUM() to convert. + + */ + + Newz( 848203, trie->trans, ( trie->charcount + 1 ) * trie->uniquecharcount + 1, + reg_trie_trans ); + Newz( 848204, trie->states, trie->charcount + 2, reg_trie_state ); + next_alloc = trie->uniquecharcount + 1; + + for ( cur = first ; cur < last ; cur = regnext( cur ) ) { + + regnode *noper = NEXTOPER( cur ); + U8 *uc = (U8*)STRING( noper ); + U8 *e = uc + STR_LEN( noper ); + + U32 state = 1; /* required init */ + + U16 charid = 0; /* sanity init */ + U32 accept_state = 0; /* sanity init */ + U8 *scan = (U8*)NULL; /* sanity init */ + + STRLEN foldlen = 0; /* required init */ + U8 foldbuf[ UTF8_MAXBYTES_CASE + 1 ]; + + + for ( ; uc < e ; uc += len ) { + + TRIE_READ_CHAR; + + if ( uvc < 256 ) { + charid = trie->charmap[ uvc ]; + } else { + SV** svpp=(SV**)NULL; + svpp = hv_fetch( trie->widecharmap, (char*)&uvc, sizeof( UV ), 0); + if ( !svpp ) { + charid = 0; + } else { + charid=(U16)SvIV( *svpp ); + } + } + if ( charid ) { + charid--; + if ( !trie->trans[ state + charid ].next ) { + trie->trans[ state + charid ].next = next_alloc; + trie->trans[ state ].check++; + next_alloc += trie->uniquecharcount; + } + state = trie->trans[ state + charid ].next; + } else { + Perl_croak( aTHX_ "panic! In trie construction, no char mapping for %"IVdf, uvc ); + } + /* charid is now 0 if we dont know the char read, or nonzero if we do */ + } + + accept_state = TRIE_NODENUM( state ); + if ( !trie->states[ accept_state ].wordnum ) { + /* we havent inserted this word into the structure yet. */ + trie->states[ accept_state ].wordnum = ++curword; + + DEBUG_r({ + /* store the word for dumping */ + SV* tmp = newSVpvn( STRING( noper ), STR_LEN( noper ) ); + if ( UTF ) SvUTF8_on( tmp ); + av_push( trie->words, tmp ); + }); + + } else { + /* Its a dupe. So ignore it. */ + } + + } /* end second pass */ + + DEBUG_TRIE_COMPILE_MORE_r({ + /* + print out the table precompression so that we can do a visual check + that they are identical. + */ + U32 state; + U16 charid; + PerlIO_printf( Perl_debug_log, "\nChar : " ); + + for( charid = 0 ; charid < trie->uniquecharcount ; charid++ ) { + SV **tmp = av_fetch( trie->revcharmap, charid, 0); + if ( tmp ) { + PerlIO_printf( Perl_debug_log, "%4.4s ", SvPV_nolen( *tmp ) ); + } + } + + PerlIO_printf( Perl_debug_log, "\nState+-" ); + + for( charid=0 ; charid < trie->uniquecharcount ; charid++ ) { + PerlIO_printf( Perl_debug_log, "%4s-", "----" ); + } + + PerlIO_printf( Perl_debug_log, "\n" ); + + for( state=1 ; state < next_alloc ; state += trie->uniquecharcount ) { + + PerlIO_printf( Perl_debug_log, "%04"UVXf" : ", (UV)TRIE_NODENUM( state ) ); + + for( charid = 0 ; charid < trie->uniquecharcount ; charid++ ) { + PerlIO_printf( Perl_debug_log, "%04"UVXf" ", + (UV)SAFE_TRIE_NODENUM( trie->trans[ state + charid ].next ) ); + } + if ( ! trie->states[ TRIE_NODENUM( state ) ].wordnum ) { + PerlIO_printf( Perl_debug_log, " (%04"UVXf")\n", (UV)trie->trans[ state ].check ); + } else { + PerlIO_printf( Perl_debug_log, " (%04"UVXf") W%04X\n", (UV)trie->trans[ state ].check, + trie->states[ TRIE_NODENUM( state ) ].wordnum ); + } + } + PerlIO_printf( Perl_debug_log, "\n\n" ); + }); + { + /* + * Inplace compress the table.* + + For sparse data sets the table constructed by the trie algorithm will + be mostly 0/FAIL transitions or to put it another way mostly empty. + (Note that leaf nodes will not contain any transitions.) + + This algorithm compresses the tables by eliminating most such + transitions, at the cost of a modest bit of extra work during lookup: + + - Each states[] entry contains a .base field which indicates the + index in the state[] array wheres its transition data is stored. + + - If .base is 0 there are no valid transitions from that node. + + - If .base is nonzero then charid is added to it to find an entry in + the trans array. + + -If trans[states[state].base+charid].check!=state then the + transition is taken to be a 0/Fail transition. Thus if there are fail + transitions at the front of the node then the .base offset will point + somewhere inside the previous nodes data (or maybe even into a node + even earlier), but the .check field determines if the transition is + valid. + + The following process inplace converts the table to the compressed + table: We first do not compress the root node 1,and mark its all its + .check pointers as 1 and set its .base pointer as 1 as well. This + allows to do a DFA construction from the compressed table later, and + ensures that any .base pointers we calculate later are greater than + 0. + + - We set 'pos' to indicate the first entry of the second node. + + - We then iterate over the columns of the node, finding the first and + last used entry at l and m. We then copy l..m into pos..(pos+m-l), + and set the .check pointers accordingly, and advance pos + appropriately and repreat for the next node. Note that when we copy + the next pointers we have to convert them from the original + NODEIDX form to NODENUM form as the former is not valid post + compression. + + - If a node has no transitions used we mark its base as 0 and do not + advance the pos pointer. + + - If a node only has one transition we use a second pointer into the + structure to fill in allocated fail transitions from other states. + This pointer is independent of the main pointer and scans forward + looking for null transitions that are allocated to a state. When it + finds one it writes the single transition into the "hole". If the + pointer doesnt find one the single transition is appeneded as normal. + + - Once compressed we can Renew/realloc the structures to release the + excess space. + + See "Table-Compression Methods" in sec 3.9 of the Red Dragon, + specifically Fig 3.47 and the associated pseudocode. + + demq + */ + const U32 laststate = TRIE_NODENUM( next_alloc ); + U32 used , state, charid; + U32 pos = 0, zp=0; + trie->laststate = laststate; + + for ( state = 1 ; state < laststate ; state++ ) { + U8 flag = 0; + U32 stateidx = TRIE_NODEIDX( state ); + U32 o_used=trie->trans[ stateidx ].check; + used = trie->trans[ stateidx ].check; + trie->trans[ stateidx ].check = 0; + + for ( charid = 0 ; used && charid < trie->uniquecharcount ; charid++ ) { + if ( flag || trie->trans[ stateidx + charid ].next ) { + if ( trie->trans[ stateidx + charid ].next ) { + if (o_used == 1) { + for ( ; zp < pos ; zp++ ) { + if ( ! trie->trans[ zp ].next ) { + break; + } + } + trie->states[ state ].trans.base = zp + trie->uniquecharcount - charid ; + trie->trans[ zp ].next = SAFE_TRIE_NODENUM( trie->trans[ stateidx + charid ].next ); + trie->trans[ zp ].check = state; + if ( ++zp > pos ) pos = zp; + break; + } + used--; + } + if ( !flag ) { + flag = 1; + trie->states[ state ].trans.base = pos + trie->uniquecharcount - charid ; + } + trie->trans[ pos ].next = SAFE_TRIE_NODENUM( trie->trans[ stateidx + charid ].next ); + trie->trans[ pos ].check = state; + pos++; + } + } + } + trie->lasttrans = pos + 1; + Renew( trie->states, laststate + 1, reg_trie_state); + DEBUG_TRIE_COMPILE_MORE_r( + PerlIO_printf( Perl_debug_log, + " Alloc: %d Orig: %"IVdf" elements, Final:%"IVdf". Savings of %%%5.2f\n", + (int)( ( trie->charcount + 1 ) * trie->uniquecharcount + 1 ), + (IV)next_alloc, + (IV)pos, + ( ( next_alloc - pos ) * 100 ) / (double)next_alloc ); + ); + + } /* end table compress */ + } + /* resize the trans array to remove unused space */ + Renew( trie->trans, trie->lasttrans, reg_trie_trans); + + DEBUG_TRIE_COMPILE_r({ + U32 state; + /* + Now we print it out again, in a slightly different form as there is additional + info we want to be able to see when its compressed. They are close enough for + visual comparison though. + */ + PerlIO_printf( Perl_debug_log, "\nChar : %-6s%-6s%-4s ","Match","Base","Ofs" ); + + for( state = 0 ; state < trie->uniquecharcount ; state++ ) { + SV **tmp = av_fetch( trie->revcharmap, state, 0); + if ( tmp ) { + PerlIO_printf( Perl_debug_log, "%4.4s ", SvPV_nolen( *tmp ) ); + } + } + PerlIO_printf( Perl_debug_log, "\n-----:-----------------------"); + + for( state = 0 ; state < trie->uniquecharcount ; state++ ) + PerlIO_printf( Perl_debug_log, "-----"); + PerlIO_printf( Perl_debug_log, "\n"); + + for( state = 1 ; state < trie->laststate ; state++ ) { + U32 base = trie->states[ state ].trans.base; + + PerlIO_printf( Perl_debug_log, "#%04"UVXf" ", (UV)state); + + if ( trie->states[ state ].wordnum ) { + PerlIO_printf( Perl_debug_log, " W%04X", trie->states[ state ].wordnum ); + } else { + PerlIO_printf( Perl_debug_log, "%6s", "" ); + } + + PerlIO_printf( Perl_debug_log, " @%04"UVXf" ", (UV)base ); + + if ( base ) { + U32 ofs = 0; + + while( ( base + ofs < trie->uniquecharcount ) || + ( base + ofs - trie->uniquecharcount < trie->lasttrans + && trie->trans[ base + ofs - trie->uniquecharcount ].check != state)) + ofs++; + + PerlIO_printf( Perl_debug_log, "+%02"UVXf"[ ", (UV)ofs); + + for ( ofs = 0 ; ofs < trie->uniquecharcount ; ofs++ ) { + if ( ( base + ofs >= trie->uniquecharcount ) && + ( base + ofs - trie->uniquecharcount < trie->lasttrans ) && + trie->trans[ base + ofs - trie->uniquecharcount ].check == state ) + { + PerlIO_printf( Perl_debug_log, "%04"UVXf" ", + (UV)trie->trans[ base + ofs - trie->uniquecharcount ].next ); + } else { + PerlIO_printf( Perl_debug_log, "%4s "," 0" ); + } + } + + PerlIO_printf( Perl_debug_log, "]"); + + } + PerlIO_printf( Perl_debug_log, "\n" ); + } + }); + + { + /* now finally we "stitch in" the new TRIE node + This means we convert either the first branch or the first Exact, + depending on whether the thing following (in 'last') is a branch + or not and whther first is the startbranch (ie is it a sub part of + the alternation or is it the whole thing.) + Assuming its a sub part we conver the EXACT otherwise we convert + the whole branch sequence, including the first. + */ + regnode *convert; + + + + + if ( first == startbranch && OP( last ) != BRANCH ) { + convert = first; + } else { + convert = NEXTOPER( first ); + NEXT_OFF( first ) = (U16)(last - first); + } + + OP( convert ) = TRIE + (U8)( flags - EXACT ); + NEXT_OFF( convert ) = (U16)(tail - convert); + ARG_SET( convert, data_slot ); + + /* tells us if we need to handle accept buffers specially */ + convert->flags = ( RExC_seen_evals ? 1 : 0 ); + + + /* needed for dumping*/ + DEBUG_r({ + regnode *optimize = convert + NODE_STEP_REGNODE + regarglen[ TRIE ]; + /* We now need to mark all of the space originally used by the + branches as optimized away. This keeps the dumpuntil from + throwing a wobbly as it doesnt use regnext() to traverse the + opcodes. + */ + while( optimize < last ) { + OP( optimize ) = OPTIMIZED; + optimize++; + } + }); + } /* end node insert */ + return 1; +} + + + +/* * There are strange code-generation bugs caused on sparc64 by gcc-2.95.2. * These need to be revisited when a newer toolchain becomes available. */ @@ -672,11 +1550,12 @@ S_cl_or(pTHX_ RExC_state_t *pRExC_state, struct regnode_charclass_class *cl, str /* REx optimizer. Converts nodes into quickier variants "in place". Finds fixed substrings. */ -/* Stops at toplevel WHILEM as well as at `last'. At end *scanp is set +/* Stops at toplevel WHILEM as well as at "last". At end *scanp is set to the position after last scanned or to NULL. */ + STATIC I32 -S_study_chunk(pTHX_ RExC_state_t *pRExC_state, regnode **scanp, I32 *deltap, regnode *last, scan_data_t *data, U32 flags) +S_study_chunk(pTHX_ RExC_state_t *pRExC_state, regnode **scanp, I32 *deltap, regnode *last, scan_data_t *data, U32 flags, U32 depth) /* scanp: Start here (read-write). */ /* deltap: Write maxlen-minlen here. */ /* last: Stop before this one. */ @@ -689,9 +1568,18 @@ S_study_chunk(pTHX_ RExC_state_t *pRExC_state, regnode **scanp, I32 *deltap, reg I32 is_par = OP(scan) == OPEN ? ARG(scan) : 0; scan_data_t data_fake; struct regnode_charclass_class and_with; /* Valid if flags & SCF_DO_STCLASS_OR */ + SV *re_trie_maxbuff = NULL; + + GET_RE_DEBUG_FLAGS_DECL; while (scan && OP(scan) != END && scan < last) { /* Peephole optimizer: */ + DEBUG_OPTIMISE_r({ + SV *mysv=sv_newmortal(); + regprop( mysv, scan); + PerlIO_printf(Perl_debug_log, "%*speep: %s (0x%08"UVXf")\n", + (int)depth*2, "", SvPV_nolen(mysv), PTR2UV(scan)); + }); if (PL_regkind[(U8)OP(scan)] == EXACT) { /* Merge several consecutive EXACTish nodes into one. */ @@ -720,7 +1608,7 @@ S_study_chunk(pTHX_ RExC_state_t *pRExC_state, regnode **scanp, I32 *deltap, reg n = regnext(n); } else if (stringok) { - int oldl = STR_LEN(scan); + const int oldl = STR_LEN(scan); regnode *nnext = regnext(n); if (oldl + STR_LEN(n) > U8_MAX) @@ -737,7 +1625,7 @@ S_study_chunk(pTHX_ RExC_state_t *pRExC_state, regnode **scanp, I32 *deltap, reg } } - if (UTF && OP(scan) == EXACTF) { + if (UTF && ( OP(scan) == EXACTF ) && ( STR_LEN(scan) >= 6 ) ) { /* Two problematic code points in Unicode casefolding of EXACT nodes: @@ -768,9 +1656,9 @@ S_study_chunk(pTHX_ RExC_state_t *pRExC_state, regnode **scanp, I32 *deltap, reg */ char *s0 = STRING(scan), *s, *t; char *s1 = s0 + STR_LEN(scan) - 1, *s2 = s1 - 4; - char *t0 = "\xcc\x88\xcc\x81"; - char *t1 = t0 + 3; - + const char *t0 = "\xcc\x88\xcc\x81"; + const char *t1 = t0 + 3; + for (s = s0 + 2; s < s2 && (t = ninstr(s, s1, t0, t1)); s = t + 4) { @@ -792,10 +1680,13 @@ S_study_chunk(pTHX_ RExC_state_t *pRExC_state, regnode **scanp, I32 *deltap, reg } #endif } + + + /* Follow the next-chain of the current node and optimize away all the NOTHINGs from it. */ if (OP(scan) != CURLYX) { - int max = (reg_off_by_arg[OP(scan)] + const int max = (reg_off_by_arg[OP(scan)] ? I32_MAX /* I32 may be smaller than U16 on CRAYs! */ : (I32_MAX < U16_MAX ? I32_MAX : U16_MAX)); @@ -814,21 +1705,25 @@ S_study_chunk(pTHX_ RExC_state_t *pRExC_state, regnode **scanp, I32 *deltap, reg else NEXT_OFF(scan) = off; } + /* The principal pseudo-switch. Cannot be a switch, since we look into several different things. */ if (OP(scan) == BRANCH || OP(scan) == BRANCHJ || OP(scan) == IFTHEN || OP(scan) == SUSPEND) { next = regnext(scan); code = OP(scan); + /* demq: the op(next)==code check is to see if we have "branch-branch" AFAICT */ if (OP(next) == code || code == IFTHEN || code == SUSPEND) { I32 max1 = 0, min1 = I32_MAX, num = 0; struct regnode_charclass_class accum; + regnode *startbranch=scan; if (flags & SCF_DO_SUBSTR) /* XXXX Add !SUSPEND? */ scan_commit(pRExC_state, data); /* Cannot merge strings after this. */ if (flags & SCF_DO_STCLASS) cl_init_zero(pRExC_state, &accum); + while (OP(scan) == code) { I32 deltanext, minnext, f = 0, fake; struct regnode_charclass_class this_class; @@ -852,9 +1747,10 @@ S_study_chunk(pTHX_ RExC_state_t *pRExC_state, regnode **scanp, I32 *deltap, reg } if (flags & SCF_WHILEM_VISITED_POS) f |= SCF_WHILEM_VISITED_POS; + /* we suppose the run is continuous, last=next...*/ minnext = study_chunk(pRExC_state, &scan, &deltanext, - next, &data_fake, f); + next, &data_fake, f,depth+1); if (min1 > minnext) min1 = minnext; if (max1 < minnext + deltanext) @@ -907,10 +1803,197 @@ S_study_chunk(pTHX_ RExC_state_t *pRExC_state, regnode **scanp, I32 *deltap, reg data->start_class->flags |= ANYOF_EOS; } } + + /* demq. + + Assuming this was/is a branch we are dealing with: 'scan' now + points at the item that follows the branch sequence, whatever + it is. We now start at the beginning of the sequence and look + for subsequences of + + BRANCH->EXACT=>X + BRANCH->EXACT=>X + + which would be constructed from a pattern like /A|LIST|OF|WORDS/ + + If we can find such a subseqence we need to turn the first + element into a trie and then add the subsequent branch exact + strings to the trie. + + We have two cases + + 1. patterns where the whole set of branch can be converted to a trie, + + 2. patterns where only a subset of the alternations can be + converted to a trie. + + In case 1 we can replace the whole set with a single regop + for the trie. In case 2 we need to keep the start and end + branchs so + + 'BRANCH EXACT; BRANCH EXACT; BRANCH X' + becomes BRANCH TRIE; BRANCH X; + + Hypthetically when we know the regex isnt anchored we can + turn a case 1 into a DFA and let it rip... Every time it finds a match + it would just call its tail, no WHILEM/CURLY needed. + + */ + if (DO_TRIE) { + if (!re_trie_maxbuff) { + re_trie_maxbuff = get_sv(RE_TRIE_MAXBUF_NAME, 1); + if (!SvIOK(re_trie_maxbuff)) + sv_setiv(re_trie_maxbuff, RE_TRIE_MAXBUF_INIT); + } + if ( SvIV(re_trie_maxbuff)>=0 && OP( startbranch )==BRANCH ) { + regnode *cur; + regnode *first = (regnode *)NULL; + regnode *last = (regnode *)NULL; + regnode *tail = scan; + U8 optype = 0; + U32 count=0; + +#ifdef DEBUGGING + SV *mysv = sv_newmortal(); /* for dumping */ +#endif + /* var tail is used because there may be a TAIL + regop in the way. Ie, the exacts will point to the + thing following the TAIL, but the last branch will + point at the TAIL. So we advance tail. If we + have nested (?:) we may have to move through several + tails. + */ + + while ( OP( tail ) == TAIL ) { + /* this is the TAIL generated by (?:) */ + tail = regnext( tail ); + } + + DEBUG_OPTIMISE_r({ + regprop( mysv, tail ); + PerlIO_printf( Perl_debug_log, "%*s%s%s%s\n", + (int)depth * 2 + 2, "", "Tail node is:", SvPV_nolen( mysv ), + (RExC_seen_evals) ? "[EVAL]" : "" + ); + }); + /* + + step through the branches, cur represents each + branch, noper is the first thing to be matched + as part of that branch and noper_next is the + regnext() of that node. if noper is an EXACT + and noper_next is the same as scan (our current + position in the regex) then the EXACT branch is + a possible optimization target. Once we have + two or more consequetive such branches we can + create a trie of the EXACT's contents and stich + it in place. If the sequence represents all of + the branches we eliminate the whole thing and + replace it with a single TRIE. If it is a + subsequence then we need to stitch it in. This + means the first branch has to remain, and needs + to be repointed at the item on the branch chain + following the last branch optimized. This could + be either a BRANCH, in which case the + subsequence is internal, or it could be the + item following the branch sequence in which + case the subsequence is at the end. + + */ + + /* dont use tail as the end marker for this traverse */ + for ( cur = startbranch ; cur != scan ; cur = regnext( cur ) ) { + regnode *noper = NEXTOPER( cur ); + regnode *noper_next = regnext( noper ); + + DEBUG_OPTIMISE_r({ + regprop( mysv, cur); + PerlIO_printf( Perl_debug_log, "%*s%s", + (int)depth * 2 + 2," ", SvPV_nolen( mysv ) ); + + regprop( mysv, noper); + PerlIO_printf( Perl_debug_log, " -> %s", + SvPV_nolen(mysv)); + + if ( noper_next ) { + regprop( mysv, noper_next ); + PerlIO_printf( Perl_debug_log,"\t=> %s\t", + SvPV_nolen(mysv)); + } + PerlIO_printf( Perl_debug_log, "0x%p,0x%p,0x%p)\n", + first, last, cur ); + }); + if ( ( first ? OP( noper ) == optype + : PL_regkind[ (U8)OP( noper ) ] == EXACT ) + && noper_next == tail && count %s\n", + SvPV_nolen( mysv ) ); + } + ); + last = cur; + DEBUG_OPTIMISE_r({ + regprop( mysv, cur); + PerlIO_printf( Perl_debug_log, "%*s%s", + (int)depth * 2 + 2, "N:", SvPV_nolen( mysv ) ); + regprop( mysv, noper ); + PerlIO_printf( Perl_debug_log, " -> %s\n", + SvPV_nolen( mysv ) ); + }); + } + } else { + if ( last ) { + DEBUG_OPTIMISE_r( + PerlIO_printf( Perl_debug_log, "%*s%s\n", + (int)depth * 2 + 2, "E:", "**END**" ); + ); + make_trie( pRExC_state, startbranch, first, cur, tail, optype ); + } + if ( PL_regkind[ (U8)OP( noper ) ] == EXACT + && noper_next == tail ) + { + count = 1; + first = cur; + optype = OP( noper ); + } else { + count = 0; + first = NULL; + optype = 0; + } + last = NULL; + } + } + DEBUG_OPTIMISE_r({ + regprop( mysv, cur); + PerlIO_printf( Perl_debug_log, + "%*s%s\t(0x%p,0x%p,0x%p)\n", (int)depth * 2 + 2, + " ", SvPV_nolen( mysv ), first, last, cur); + + }); + if ( last ) { + DEBUG_OPTIMISE_r( + PerlIO_printf( Perl_debug_log, "%*s%s\n", + (int)depth * 2 + 2, "E:", "==END==" ); + ); + make_trie( pRExC_state, startbranch, first, scan, tail, optype ); + } + } + } } - else if (code == BRANCHJ) /* single branch is optimized. */ + else if ( code == BRANCHJ ) { /* single branch is optimized. */ scan = NEXTOPER(NEXTOPER(scan)); - else /* single branch is optimized. */ + } else /* single branch is optimized. */ scan = NEXTOPER(scan); continue; } @@ -918,7 +2001,7 @@ S_study_chunk(pTHX_ RExC_state_t *pRExC_state, regnode **scanp, I32 *deltap, reg I32 l = STR_LEN(scan); UV uc = *((U8*)STRING(scan)); if (UTF) { - U8 *s = (U8*)STRING(scan); + const U8 * const s = (U8*)STRING(scan); l = utf8_length(s, s + l); uc = utf8_to_uvchr(s, NULL); } @@ -932,6 +2015,16 @@ S_study_chunk(pTHX_ RExC_state_t *pRExC_state, regnode **scanp, I32 *deltap, reg ? I32_MAX : data->pos_min + data->pos_delta; } sv_catpvn(data->last_found, STRING(scan), STR_LEN(scan)); + { + SV * sv = data->last_found; + MAGIC *mg = SvUTF8(sv) && SvMAGICAL(sv) ? + mg_find(sv, PERL_MAGIC_utf8) : NULL; + if (mg && mg->mg_len >= 0) + mg->mg_len += utf8_length((U8*)STRING(scan), + (U8*)STRING(scan)+STR_LEN(scan)); + } + if (UTF) + SvUTF8_on(data->last_found); data->last_end = data->pos_min + l; data->pos_min += l; /* As in the first entry. */ data->flags &= ~SF_BEFORE_EOL; @@ -1012,7 +2105,7 @@ S_study_chunk(pTHX_ RExC_state_t *pRExC_state, regnode **scanp, I32 *deltap, reg } flags &= ~SCF_DO_STCLASS; } - else if (strchr((char*)PL_varies,OP(scan))) { + else if (strchr((const char*)PL_varies,OP(scan))) { I32 mincount, maxcount, minnext, deltanext, fl = 0; I32 f = flags, pos_before = 0; regnode *oscan = scan; @@ -1060,8 +2153,7 @@ S_study_chunk(pTHX_ RExC_state_t *pRExC_state, regnode **scanp, I32 *deltap, reg next = regnext(scan); if (OP(scan) == CURLYX) { I32 lp = (data ? *(data->last_closep) : 0); - - scan->flags = ((lp <= U8_MAX) ? lp : U8_MAX); + scan->flags = ((lp <= U8_MAX) ? (U8)lp : U8_MAX); } scan = NEXTOPER(scan) + EXTRA_STEP_2ARGS; next_is_eval = (OP(scan) == EVAL); @@ -1094,8 +2186,8 @@ S_study_chunk(pTHX_ RExC_state_t *pRExC_state, regnode **scanp, I32 *deltap, reg /* This will finish on WHILEM, setting scan, or on NULL: */ minnext = study_chunk(pRExC_state, &scan, &deltanext, last, data, - mincount == 0 - ? (f & ~SCF_DO_SUBSTR) : f); + (mincount == 0 + ? (f & ~SCF_DO_SUBSTR) : f),depth+1); if (flags & SCF_DO_STCLASS) data->start_class = oclass; @@ -1157,7 +2249,7 @@ S_study_chunk(pTHX_ RExC_state_t *pRExC_state, regnode **scanp, I32 *deltap, reg /* Skip open. */ nxt = regnext(nxt); - if (!strchr((char*)PL_simple,OP(nxt)) + if (!strchr((const char*)PL_simple,OP(nxt)) && !(PL_regkind[(U8)OP(nxt)] == EXACT && STR_LEN(nxt) == 1)) goto nogo; @@ -1168,7 +2260,7 @@ S_study_chunk(pTHX_ RExC_state_t *pRExC_state, regnode **scanp, I32 *deltap, reg if (OP(nxt) != CLOSE) goto nogo; /* Now we know that nxt2 is the only contents: */ - oscan->flags = ARG(nxt); + oscan->flags = (U8)ARG(nxt); OP(oscan) = CURLYN; OP(nxt1) = NOTHING; /* was OPEN. */ #ifdef DEBUGGING @@ -1186,7 +2278,9 @@ S_study_chunk(pTHX_ RExC_state_t *pRExC_state, regnode **scanp, I32 *deltap, reg if ( OP(oscan) == CURLYX && data && !(data->flags & SF_HAS_PAR) && !(data->flags & SF_HAS_EVAL) - && !deltanext ) { + && !deltanext /* atom is fixed width */ + && minnext != 0 /* CURLYM can't handle zero width */ + ) { /* XXXX How to optimize if data == 0? */ /* Optimize to a simpler form. */ regnode *nxt = NEXTOPER(oscan) + EXTRA_STEP_2ARGS; /* OPEN */ @@ -1204,7 +2298,7 @@ S_study_chunk(pTHX_ RExC_state_t *pRExC_state, regnode **scanp, I32 *deltap, reg if (OP(nxt) != CLOSE) FAIL("Panic opt close"); - oscan->flags = ARG(nxt); + oscan->flags = (U8)ARG(nxt); OP(nxt1) = OPTIMIZED; /* was OPEN. */ OP(nxt) = OPTIMIZED; /* was CLOSE. */ #ifdef DEBUGGING @@ -1230,7 +2324,7 @@ S_study_chunk(pTHX_ RExC_state_t *pRExC_state, regnode **scanp, I32 *deltap, reg #endif /* Optimize again: */ study_chunk(pRExC_state, &nxt1, &deltanext, nxt, - NULL, 0); + NULL, 0,depth+1); } else oscan->flags = 0; @@ -1248,8 +2342,8 @@ S_study_chunk(pTHX_ RExC_state_t *pRExC_state, regnode **scanp, I32 *deltap, reg if (OP(PREVOPER(nxt)) == NOTHING) /* LONGJMP */ nxt += ARG(nxt); - PREVOPER(nxt)->flags = data->whilem_c - | (RExC_whilem_seen << 4); /* On WHILEM */ + PREVOPER(nxt)->flags = (U8)(data->whilem_c + | (RExC_whilem_seen << 4)); /* On WHILEM */ } if (data && fl & (SF_HAS_PAR|SF_IN_PAR)) pars++; @@ -1287,24 +2381,34 @@ S_study_chunk(pTHX_ RExC_state_t *pRExC_state, regnode **scanp, I32 *deltap, reg l -= old; /* Get the added string: */ last_str = newSVpvn(s + old, l); + if (UTF) + SvUTF8_on(last_str); if (deltanext == 0 && pos_before == b) { /* What was added is a constant string */ if (mincount > 1) { SvGROW(last_str, (mincount * l) + 1); repeatcpy(SvPVX(last_str) + l, SvPVX(last_str), l, mincount - 1); - SvCUR(last_str) *= mincount; + SvCUR_set(last_str, SvCUR(last_str) * mincount); /* Add additional parts. */ SvCUR_set(data->last_found, SvCUR(data->last_found) - l); sv_catsv(data->last_found, last_str); + { + SV * sv = data->last_found; + MAGIC *mg = + SvUTF8(sv) && SvMAGICAL(sv) ? + mg_find(sv, PERL_MAGIC_utf8) : NULL; + if (mg && mg->mg_len >= 0) + mg->mg_len += CHR_SVLEN(last_str); + } data->last_end += l * (mincount - 1); } } else { /* start offset must point into the last copy */ data->last_start_min += minnext * (mincount - 1); - data->last_start_max += is_inf ? 0 : (maxcount - 1) - * (minnext + data->pos_delta); + data->last_start_max += is_inf ? I32_MAX + : (maxcount - 1) * (minnext + data->pos_delta); } } /* It is counted once already... */ @@ -1350,7 +2454,7 @@ S_study_chunk(pTHX_ RExC_state_t *pRExC_state, regnode **scanp, I32 *deltap, reg break; } } - else if (strchr((char*)PL_simple,OP(scan))) { + else if (strchr((const char*)PL_simple,OP(scan))) { int value = 0; if (flags & SCF_DO_SUBSTR) { @@ -1582,7 +2686,7 @@ S_study_chunk(pTHX_ RExC_state_t *pRExC_state, regnode **scanp, I32 *deltap, reg f |= SCF_WHILEM_VISITED_POS; next = regnext(scan); nscan = NEXTOPER(NEXTOPER(scan)); - minnext = study_chunk(pRExC_state, &nscan, &deltanext, last, &data_fake, f); + minnext = study_chunk(pRExC_state, &nscan, &deltanext, last, &data_fake, f,depth+1); if (scan->flags) { if (deltanext) { vFAIL("Variable length lookbehind not implemented"); @@ -1590,7 +2694,7 @@ S_study_chunk(pTHX_ RExC_state_t *pRExC_state, regnode **scanp, I32 *deltap, reg else if (minnext > U8_MAX) { vFAIL2("Lookbehind longer than %"UVuf" not implemented", (UV)U8_MAX); } - scan->flags = minnext; + scan->flags = (U8)minnext; } if (data && data_fake.flags & (SF_HAS_PAR|SF_IN_PAR)) pars++; @@ -1610,7 +2714,7 @@ S_study_chunk(pTHX_ RExC_state_t *pRExC_state, regnode **scanp, I32 *deltap, reg pars++; } else if (OP(scan) == CLOSE) { - if (ARG(scan) == is_par) { + if ((I32)ARG(scan) == is_par) { next = regnext(scan); if ( next && (OP(next) != WHILEM) && next < last) @@ -1658,7 +2762,7 @@ S_study_chunk(pTHX_ RExC_state_t *pRExC_state, regnode **scanp, I32 *deltap, reg } STATIC I32 -S_add_data(pTHX_ RExC_state_t *pRExC_state, I32 n, char *s) +S_add_data(pTHX_ RExC_state_t *pRExC_state, I32 n, const char *s) { if (RExC_rx->data) { Renewc(RExC_rx->data, @@ -1680,23 +2784,24 @@ S_add_data(pTHX_ RExC_state_t *pRExC_state, I32 n, char *s) void Perl_reginitcolors(pTHX) { - int i = 0; - char *s = PerlEnv_getenv("PERL_RE_COLORS"); - + const char * const s = PerlEnv_getenv("PERL_RE_COLORS"); if (s) { - PL_colors[0] = s = savepv(s); + char *t = savepv(s); + int i = 0; + PL_colors[0] = t; while (++i < 6) { - s = strchr(s, '\t'); - if (s) { - *s = '\0'; - PL_colors[i] = ++s; + t = strchr(t, '\t'); + if (t) { + *t = '\0'; + PL_colors[i] = ++t; } else - PL_colors[i] = s = ""; + PL_colors[i] = t = (char *)""; } } else { + int i = 0; while (i < 6) - PL_colors[i++] = ""; + PL_colors[i++] = (char *)""; } PL_colorset = 1; } @@ -1731,19 +2836,21 @@ Perl_pregcomp(pTHX_ char *exp, char *xend, PMOP *pm) RExC_state_t RExC_state; RExC_state_t *pRExC_state = &RExC_state; + GET_RE_DEBUG_FLAGS_DECL; + if (exp == NULL) FAIL("NULL regexp argument"); RExC_utf8 = pm->op_pmdynflags & PMdf_CMP_UTF8; RExC_precomp = exp; - DEBUG_r({ - if (!PL_colorset) reginitcolors(); - PerlIO_printf(Perl_debug_log, "%sCompiling REx%s `%s%*s%s'\n", + DEBUG_r(if (!PL_colorset) reginitcolors()); + DEBUG_COMPILE_r({ + PerlIO_printf(Perl_debug_log, "%sCompiling REx%s \"%s%*s%s\"\n", PL_colors[4],PL_colors[5],PL_colors[0], (int)(xend - exp), RExC_precomp, PL_colors[1]); }); - RExC_flags16 = pm->op_pmflags; + RExC_flags = pm->op_pmflags; RExC_sawback = 0; RExC_seen = 0; @@ -1768,7 +2875,7 @@ Perl_pregcomp(pTHX_ char *exp, char *xend, PMOP *pm) RExC_precomp = Nullch; return(NULL); } - DEBUG_r(PerlIO_printf(Perl_debug_log, "size %"IVdf" ", (IV)RExC_size)); + DEBUG_COMPILE_r(PerlIO_printf(Perl_debug_log, "size %"IVdf" ", (IV)RExC_size)); /* Small enough for pointer-storage convention? If extralen==0, this means that we will not need long jumps. */ @@ -1793,6 +2900,9 @@ Perl_pregcomp(pTHX_ char *exp, char *xend, PMOP *pm) r->prelen = xend - exp; r->precomp = savepvn(RExC_precomp, r->prelen); r->subbeg = NULL; +#ifdef PERL_COPY_ON_WRITE + r->saved_copy = Nullsv; +#endif r->reganch = pm->op_pmflags & PMf_COMPILETIME; r->nparens = RExC_npar - 1; /* set early to validate backrefs */ @@ -1802,17 +2912,17 @@ Perl_pregcomp(pTHX_ char *exp, char *xend, PMOP *pm) Newz(1304, r->offsets, 2*RExC_size+1, U32); /* MJD 20001228 */ if (r->offsets) { - r->offsets[0] = RExC_size; + r->offsets[0] = RExC_size; } - DEBUG_r(PerlIO_printf(Perl_debug_log, - "%s %"UVuf" bytes for offset annotations.\n", - r->offsets ? "Got" : "Couldn't get", + DEBUG_OFFSETS_r(PerlIO_printf(Perl_debug_log, + "%s %"UVuf" bytes for offset annotations.\n", + r->offsets ? "Got" : "Couldn't get", (UV)((2*RExC_size+1) * sizeof(U32)))); RExC_rx = r; /* Second pass: emit code. */ - RExC_flags16 = pm->op_pmflags; /* don't let top level (?i) bleed */ + RExC_flags = pm->op_pmflags; /* don't let top level (?i) bleed */ RExC_parse = exp; RExC_end = xend; RExC_naughty = 0; @@ -1820,15 +2930,16 @@ Perl_pregcomp(pTHX_ char *exp, char *xend, PMOP *pm) RExC_emit_start = r->program; RExC_emit = r->program; /* Store the count of eval-groups for security checks: */ - RExC_emit->next_off = ((RExC_seen_evals > U16_MAX) ? U16_MAX : RExC_seen_evals); + RExC_emit->next_off = (U16)((RExC_seen_evals > U16_MAX) ? U16_MAX : RExC_seen_evals); REGC((U8)REG_MAGIC, (char*) RExC_emit++); r->data = 0; if (reg(pRExC_state, 0, &flags) == NULL) return(NULL); + /* Dig out information for optimizations. */ r->reganch = pm->op_pmflags & PMf_COMPILETIME; /* Again? */ - pm->op_pmflags = RExC_flags16; + pm->op_pmflags = RExC_flags; if (UTF) r->reganch |= ROPT_UTF8; /* Unicode in it? */ r->regstclass = NULL; @@ -1873,7 +2984,7 @@ Perl_pregcomp(pTHX_ char *exp, char *xend, PMOP *pm) else if ((OP(first) == EXACTF || OP(first) == EXACTFL)) r->regstclass = first; } - else if (strchr((char*)PL_simple,OP(first))) + else if (strchr((const char*)PL_simple,OP(first))) r->regstclass = first; else if (PL_regkind[(U8)OP(first)] == BOUND || PL_regkind[(U8)OP(first)] == NBOUND) @@ -1897,13 +3008,10 @@ Perl_pregcomp(pTHX_ char *exp, char *xend, PMOP *pm) !(r->reganch & ROPT_ANCH) ) { /* turn .* into ^.* with an implied $*=1 */ - int type = OP(NEXTOPER(first)); - - if (type == REG_ANY) - type = ROPT_ANCH_MBOL; - else - type = ROPT_ANCH_SBOL; - + const int type = + (OP(NEXTOPER(first)) == REG_ANY) + ? ROPT_ANCH_MBOL + : ROPT_ANCH_SBOL; r->reganch |= type | ROPT_IMPLICIT; first = NEXTOPER(first); goto again; @@ -1914,7 +3022,7 @@ Perl_pregcomp(pTHX_ char *exp, char *xend, PMOP *pm) r->reganch |= ROPT_SKIP; /* Scan is after the zeroth branch, first is atomic matcher. */ - DEBUG_r(PerlIO_printf(Perl_debug_log, "first at %"IVdf"\n", + DEBUG_COMPILE_r(PerlIO_printf(Perl_debug_log, "first at %"IVdf"\n", (IV)(first - scan + 1))); /* * If there's something expensive in the r.e., find the @@ -1943,7 +3051,7 @@ Perl_pregcomp(pTHX_ char *exp, char *xend, PMOP *pm) data.last_closep = &last_close; minlen = study_chunk(pRExC_state, &first, &fake, scan + RExC_size, /* Up to end */ - &data, SCF_DO_SUBSTR | SCF_WHILEM_VISITED_POS | stclass_flag); + &data, SCF_DO_SUBSTR | SCF_WHILEM_VISITED_POS | stclass_flag,0); if ( RExC_npar == 1 && data.longest == &(data.longest_fixed) && data.last_start_min == 0 && data.last_end > 0 && !RExC_seen_zerolen @@ -1956,7 +3064,7 @@ Perl_pregcomp(pTHX_ char *exp, char *xend, PMOP *pm) if (longest_float_length || (data.flags & SF_FL_BEFORE_EOL && (!(data.flags & SF_FL_BEFORE_MEOL) - || (RExC_flags16 & PMf_MULTILINE)))) { + || (RExC_flags & PMf_MULTILINE)))) { int t; if (SvCUR(data.longest_fixed) /* ok to leave SvCUR */ @@ -1964,17 +3072,23 @@ Perl_pregcomp(pTHX_ char *exp, char *xend, PMOP *pm) && SvCUR(data.longest_fixed) == SvCUR(data.longest_float)) goto remove_float; /* As in (a)+. */ - r->float_substr = data.longest_float; + if (SvUTF8(data.longest_float)) { + r->float_utf8 = data.longest_float; + r->float_substr = Nullsv; + } else { + r->float_substr = data.longest_float; + r->float_utf8 = Nullsv; + } r->float_min_offset = data.offset_float_min; r->float_max_offset = data.offset_float_max; t = (data.flags & SF_FL_BEFORE_EOL /* Can't have SEOL and MULTI */ && (!(data.flags & SF_FL_BEFORE_MEOL) - || (RExC_flags16 & PMf_MULTILINE))); - fbm_compile(r->float_substr, t ? FBMcf_TAIL : 0); + || (RExC_flags & PMf_MULTILINE))); + fbm_compile(data.longest_float, t ? FBMcf_TAIL : 0); } else { remove_float: - r->float_substr = Nullsv; + r->float_substr = r->float_utf8 = Nullsv; SvREFCNT_dec(data.longest_float); longest_float_length = 0; } @@ -1983,28 +3097,36 @@ Perl_pregcomp(pTHX_ char *exp, char *xend, PMOP *pm) if (longest_fixed_length || (data.flags & SF_FIX_BEFORE_EOL /* Cannot have SEOL and MULTI */ && (!(data.flags & SF_FIX_BEFORE_MEOL) - || (RExC_flags16 & PMf_MULTILINE)))) { + || (RExC_flags & PMf_MULTILINE)))) { int t; - r->anchored_substr = data.longest_fixed; + if (SvUTF8(data.longest_fixed)) { + r->anchored_utf8 = data.longest_fixed; + r->anchored_substr = Nullsv; + } else { + r->anchored_substr = data.longest_fixed; + r->anchored_utf8 = Nullsv; + } r->anchored_offset = data.offset_fixed; t = (data.flags & SF_FIX_BEFORE_EOL /* Can't have SEOL and MULTI */ && (!(data.flags & SF_FIX_BEFORE_MEOL) - || (RExC_flags16 & PMf_MULTILINE))); - fbm_compile(r->anchored_substr, t ? FBMcf_TAIL : 0); + || (RExC_flags & PMf_MULTILINE))); + fbm_compile(data.longest_fixed, t ? FBMcf_TAIL : 0); } else { - r->anchored_substr = Nullsv; + r->anchored_substr = r->anchored_utf8 = Nullsv; SvREFCNT_dec(data.longest_fixed); longest_fixed_length = 0; } if (r->regstclass && (OP(r->regstclass) == REG_ANY || OP(r->regstclass) == SANY)) r->regstclass = NULL; - if ((!r->anchored_substr || r->anchored_offset) && stclass_flag + if ((!(r->anchored_substr || r->anchored_utf8) || r->anchored_offset) + && stclass_flag && !(data.start_class->flags & ANYOF_EOS) - && !cl_is_anything(data.start_class)) { - I32 n = add_data(pRExC_state, 1, "f"); + && !cl_is_anything(data.start_class)) + { + const I32 n = add_data(pRExC_state, 1, "f"); New(1006, RExC_rx->data->data[n], 1, struct regnode_charclass_class); @@ -2014,30 +3136,32 @@ Perl_pregcomp(pTHX_ char *exp, char *xend, PMOP *pm) r->regstclass = (regnode*)RExC_rx->data->data[n]; r->reganch &= ~ROPT_SKIP; /* Used in find_byclass(). */ PL_regdata = r->data; /* for regprop() */ - DEBUG_r({ SV *sv = sv_newmortal(); + DEBUG_COMPILE_r({ SV *sv = sv_newmortal(); regprop(sv, (regnode*)data.start_class); PerlIO_printf(Perl_debug_log, - "synthetic stclass `%s'.\n", + "synthetic stclass \"%s\".\n", SvPVX(sv));}); } /* A temporary algorithm prefers floated substr to fixed one to dig more info. */ if (longest_fixed_length > longest_float_length) { r->check_substr = r->anchored_substr; + r->check_utf8 = r->anchored_utf8; r->check_offset_min = r->check_offset_max = r->anchored_offset; if (r->reganch & ROPT_ANCH_SINGLE) r->reganch |= ROPT_NOSCAN; } else { r->check_substr = r->float_substr; + r->check_utf8 = r->float_utf8; r->check_offset_min = data.offset_float_min; r->check_offset_max = data.offset_float_max; } /* XXXX Currently intuiting is not compatible with ANCH_GPOS. This should be changed ASAP! */ - if (r->check_substr && !(r->reganch & ROPT_ANCH_GPOS)) { + if ((r->check_substr || r->check_utf8) && !(r->reganch & ROPT_ANCH_GPOS)) { r->reganch |= RE_USE_INTUIT; - if (SvTAIL(r->check_substr)) + if (SvTAIL(r->check_substr ? r->check_substr : r->check_utf8)) r->reganch |= RE_INTUIT_TAIL; } } @@ -2047,16 +3171,18 @@ Perl_pregcomp(pTHX_ char *exp, char *xend, PMOP *pm) struct regnode_charclass_class ch_class; I32 last_close = 0; - DEBUG_r(PerlIO_printf(Perl_debug_log, "\n")); + DEBUG_COMPILE_r(PerlIO_printf(Perl_debug_log, "\n")); scan = r->program + 1; cl_init(pRExC_state, &ch_class); data.start_class = &ch_class; data.last_closep = &last_close; - minlen = study_chunk(pRExC_state, &scan, &fake, scan + RExC_size, &data, SCF_DO_STCLASS_AND|SCF_WHILEM_VISITED_POS); - r->check_substr = r->anchored_substr = r->float_substr = Nullsv; + minlen = study_chunk(pRExC_state, &scan, &fake, scan + RExC_size, &data, SCF_DO_STCLASS_AND|SCF_WHILEM_VISITED_POS,0); + r->check_substr = r->check_utf8 = r->anchored_substr = r->anchored_utf8 + = r->float_substr = r->float_utf8 = Nullsv; if (!(data.start_class->flags & ANYOF_EOS) - && !cl_is_anything(data.start_class)) { - I32 n = add_data(pRExC_state, 1, "f"); + && !cl_is_anything(data.start_class)) + { + const I32 n = add_data(pRExC_state, 1, "f"); New(1006, RExC_rx->data->data[n], 1, struct regnode_charclass_class); @@ -2065,10 +3191,10 @@ Perl_pregcomp(pTHX_ char *exp, char *xend, PMOP *pm) struct regnode_charclass_class); r->regstclass = (regnode*)RExC_rx->data->data[n]; r->reganch &= ~ROPT_SKIP; /* Used in find_byclass(). */ - DEBUG_r({ SV* sv = sv_newmortal(); + DEBUG_COMPILE_r({ SV* sv = sv_newmortal(); regprop(sv, (regnode*)data.start_class); PerlIO_printf(Perl_debug_log, - "synthetic stclass `%s'.\n", + "synthetic stclass \"%s\".\n", SvPVX(sv));}); } } @@ -2085,7 +3211,7 @@ Perl_pregcomp(pTHX_ char *exp, char *xend, PMOP *pm) Newz(1002, r->startp, RExC_npar, I32); Newz(1002, r->endp, RExC_npar, I32); PL_regdata = r->data; /* for regprop() */ - DEBUG_r(regdump(r)); + DEBUG_COMPILE_r(regdump(r)); return(r); } @@ -2102,12 +3228,13 @@ STATIC regnode * S_reg(pTHX_ RExC_state_t *pRExC_state, I32 paren, I32 *flagp) /* paren: Parenthesized? 0=top, 1=(, inside: changed to letter. */ { + dVAR; register regnode *ret; /* Will be the head of the group. */ register regnode *br; register regnode *lastbr; register regnode *ender = 0; register I32 parno = 0; - I32 flags, oregflags = RExC_flags16, have_branch = 0, open = 0; + I32 flags, oregflags = RExC_flags, have_branch = 0, open = 0; /* for (?g), (?gc), and (?o) warnings; warning about (?c) will warn about (?g) -- japhy */ @@ -2128,8 +3255,8 @@ S_reg(pTHX_ RExC_state_t *pRExC_state, I32 paren, I32 *flagp) /* Make an OPEN node, if parenthesized. */ if (paren) { if (*RExC_parse == '?') { /* (?...) */ - U16 posflags = 0, negflags = 0; - U16 *flagsp = &posflags; + U32 posflags = 0, negflags = 0; + U32 *flagsp = &posflags; int logical = 0; char *seqstart = RExC_parse; @@ -2168,6 +3295,8 @@ S_reg(pTHX_ RExC_state_t *pRExC_state, I32 paren, I32 *flagp) /* FALL THROUGH*/ case '?': /* (??...) */ logical = 1; + if (*RExC_parse != '{') + goto unknown; paren = *RExC_parse++; /* FALL THROUGH */ case '{': /* (?{...}) */ @@ -2195,7 +3324,7 @@ S_reg(pTHX_ RExC_state_t *pRExC_state, I32 paren, I32 *flagp) vFAIL("Sequence (?{...}) not terminated or not {}-balanced"); } if (!SIZE_ONLY) { - AV *av; + PAD *pad; if (RExC_parse - 1 - s) sv = newSVpvn(s, RExC_parse - 1 - s); @@ -2204,7 +3333,7 @@ S_reg(pTHX_ RExC_state_t *pRExC_state, I32 paren, I32 *flagp) ENTER; Perl_save_re_context(aTHX); - rop = sv_compile_2op(sv, &sop, "re", &av); + rop = sv_compile_2op(sv, &sop, "re", &pad); sop->op_private |= OPpREFCOUNTED; /* re_dup will OpREFCNT_inc */ OpREFCNT_set(sop, 1); @@ -2213,19 +3342,21 @@ S_reg(pTHX_ RExC_state_t *pRExC_state, I32 paren, I32 *flagp) n = add_data(pRExC_state, 3, "nop"); RExC_rx->data->data[n] = (void*)rop; RExC_rx->data->data[n+1] = (void*)sop; - RExC_rx->data->data[n+2] = (void*)av; + RExC_rx->data->data[n+2] = (void*)pad; SvREFCNT_dec(sv); } else { /* First pass */ if (PL_reginterp_cnt < ++RExC_seen_evals - && PL_curcop != &PL_compiling) + && IN_PERL_RUNTIME) /* No compiled RE interpolated, has runtime components ===> unsafe. */ FAIL("Eval-group not allowed at runtime, use re 'eval'"); if (PL_tainting && PL_tainted) FAIL("Eval-group in insecure regular expression"); + if (IN_PERL_COMPILETIME) + PL_cv_has_eval = 1; } - + nextchar(pRExC_state); if (logical) { ret = reg_node(pRExC_state, LOGICAL); @@ -2235,7 +3366,10 @@ S_reg(pTHX_ RExC_state_t *pRExC_state, I32 paren, I32 *flagp) /* deal with the length of this later - MJD */ return ret; } - return reganode(pRExC_state, EVAL, n); + ret = reganode(pRExC_state, EVAL, n); + Set_Node_Length(ret, RExC_parse - parse_start + 1); + Set_Node_Offset(ret, parse_start); + return ret; } case '(': /* (?(?{...})...) and (?(?=...)...) */ { @@ -2259,7 +3393,7 @@ S_reg(pTHX_ RExC_state_t *pRExC_state, I32 paren, I32 *flagp) while (isDIGIT(*RExC_parse)) RExC_parse++; ret = reganode(pRExC_state, GROUPP, parno); - + if ((c = *nextchar(pRExC_state)) != ')') vFAIL("Switch condition not recognized"); insert_if: @@ -2348,8 +3482,8 @@ S_reg(pTHX_ RExC_state_t *pRExC_state, I32 paren, I32 *flagp) ++RExC_parse; goto parse_flags; } - RExC_flags16 |= posflags; - RExC_flags16 &= ~negflags; + RExC_flags |= posflags; + RExC_flags &= ~negflags; if (*RExC_parse == ':') { RExC_parse++; paren = ':'; @@ -2381,7 +3515,7 @@ S_reg(pTHX_ RExC_state_t *pRExC_state, I32 paren, I32 *flagp) parse_start = RExC_parse; /* MJD */ br = regbranch(pRExC_state, &flags, 1); /* branch_len = (paren != 0); */ - + if (br == NULL) return(NULL); if (*RExC_parse == '|') { @@ -2416,7 +3550,7 @@ S_reg(pTHX_ RExC_state_t *pRExC_state, I32 paren, I32 *flagp) RExC_extralen += 2; /* Account for LONGJMP. */ nextchar(pRExC_state); br = regbranch(pRExC_state, &flags, 0); - + if (br == NULL) return(NULL); regtail(pRExC_state, lastbr, br); /* BRANCH -> BRANCH. */ @@ -2461,16 +3595,18 @@ S_reg(pTHX_ RExC_state_t *pRExC_state, I32 paren, I32 *flagp) } { - char *p; - static char parens[] = "=!<,>"; + const char *p; + static const char parens[] = "=!<,>"; if (paren && (p = strchr(parens, paren))) { - int node = ((p - parens) % 2) ? UNLESSM : IFMATCH; + U8 node = ((p - parens) % 2) ? UNLESSM : IFMATCH; int flag = (p - parens) > 1; if (paren == '>') node = SUSPEND, flag = 0; reginsert(pRExC_state, node,ret); + Set_Node_Cur_Length(ret); + Set_Node_Offset(ret, parse_start + 1); ret->flags = flag; regtail(pRExC_state, ret, reg_node(pRExC_state, TAIL)); } @@ -2478,7 +3614,7 @@ S_reg(pTHX_ RExC_state_t *pRExC_state, I32 paren, I32 *flagp) /* Check for proper termination. */ if (paren) { - RExC_flags16 = oregflags; + RExC_flags = oregflags; if (RExC_parse >= RExC_end || *nextchar(pRExC_state) != ')') { RExC_parse = oregcomp_parse; vFAIL("Unmatched ("); @@ -2576,7 +3712,7 @@ S_regpiece(pTHX_ RExC_state_t *pRExC_state, I32 *flagp) register char op; register char *next; I32 flags; - char *origparse = RExC_parse; + const char * const origparse = RExC_parse; char *maxpos; I32 min; I32 max = REG_INFTY; @@ -2641,9 +3777,9 @@ S_regpiece(pTHX_ RExC_state_t *pRExC_state, I32 *flagp) reginsert(pRExC_state, CURLYX,ret); /* MJD hk */ Set_Node_Offset(ret, parse_start+1); - Set_Node_Length(ret, + Set_Node_Length(ret, op == '{' ? (RExC_parse - parse_start) : 1); - + if (!SIZE_ONLY && RExC_extralen) NEXT_OFF(ret) = 3; /* Go over NOTHING to LONGJMP. */ regtail(pRExC_state, ret, reg_node(pRExC_state, NOTHING)); @@ -2660,8 +3796,8 @@ S_regpiece(pTHX_ RExC_state_t *pRExC_state, I32 *flagp) if (max && max < min) vFAIL("Can't do {n,m} with n > m"); if (!SIZE_ONLY) { - ARG1_SET(ret, min); - ARG2_SET(ret, max); + ARG1_SET(ret, (U16)min); + ARG2_SET(ret, (U16)max); } goto nest_check; @@ -2751,7 +3887,7 @@ S_regatom(pTHX_ RExC_state_t *pRExC_state, I32 *flagp) { register regnode *ret = 0; I32 flags; - char *parse_start = 0; + char *parse_start = RExC_parse; *flagp = WORST; /* Tentatively. */ @@ -2760,9 +3896,9 @@ tryagain: case '^': RExC_seen_zerolen++; nextchar(pRExC_state); - if (RExC_flags16 & PMf_MULTILINE) + if (RExC_flags & PMf_MULTILINE) ret = reg_node(pRExC_state, MBOL); - else if (RExC_flags16 & PMf_SINGLELINE) + else if (RExC_flags & PMf_SINGLELINE) ret = reg_node(pRExC_state, SBOL); else ret = reg_node(pRExC_state, BOL); @@ -2772,9 +3908,9 @@ tryagain: nextchar(pRExC_state); if (*RExC_parse) RExC_seen_zerolen++; - if (RExC_flags16 & PMf_MULTILINE) + if (RExC_flags & PMf_MULTILINE) ret = reg_node(pRExC_state, MEOL); - else if (RExC_flags16 & PMf_SINGLELINE) + else if (RExC_flags & PMf_SINGLELINE) ret = reg_node(pRExC_state, SEOL); else ret = reg_node(pRExC_state, EOL); @@ -2782,7 +3918,7 @@ tryagain: break; case '.': nextchar(pRExC_state); - if (RExC_flags16 & PMf_SINGLELINE) + if (RExC_flags & PMf_SINGLELINE) ret = reg_node(pRExC_state, SANY); else ret = reg_node(pRExC_state, REG_ANY); @@ -2883,13 +4019,13 @@ tryagain: Set_Node_Length(ret, 2); /* MJD */ break; case 'w': - ret = reg_node(pRExC_state, LOC ? ALNUML : ALNUM); + ret = reg_node(pRExC_state, (U8)(LOC ? ALNUML : ALNUM)); *flagp |= HASWIDTH|SIMPLE; nextchar(pRExC_state); Set_Node_Length(ret, 2); /* MJD */ break; case 'W': - ret = reg_node(pRExC_state, LOC ? NALNUML : NALNUM); + ret = reg_node(pRExC_state, (U8)(LOC ? NALNUML : NALNUM)); *flagp |= HASWIDTH|SIMPLE; nextchar(pRExC_state); Set_Node_Length(ret, 2); /* MJD */ @@ -2897,7 +4033,7 @@ tryagain: case 'b': RExC_seen_zerolen++; RExC_seen |= REG_SEEN_LOOKBEHIND; - ret = reg_node(pRExC_state, LOC ? BOUNDL : BOUND); + ret = reg_node(pRExC_state, (U8)(LOC ? BOUNDL : BOUND)); *flagp |= SIMPLE; nextchar(pRExC_state); Set_Node_Length(ret, 2); /* MJD */ @@ -2905,19 +4041,19 @@ tryagain: case 'B': RExC_seen_zerolen++; RExC_seen |= REG_SEEN_LOOKBEHIND; - ret = reg_node(pRExC_state, LOC ? NBOUNDL : NBOUND); + ret = reg_node(pRExC_state, (U8)(LOC ? NBOUNDL : NBOUND)); *flagp |= SIMPLE; nextchar(pRExC_state); Set_Node_Length(ret, 2); /* MJD */ break; case 's': - ret = reg_node(pRExC_state, LOC ? SPACEL : SPACE); + ret = reg_node(pRExC_state, (U8)(LOC ? SPACEL : SPACE)); *flagp |= HASWIDTH|SIMPLE; nextchar(pRExC_state); Set_Node_Length(ret, 2); /* MJD */ break; case 'S': - ret = reg_node(pRExC_state, LOC ? NSPACEL : NSPACE); + ret = reg_node(pRExC_state, (U8)(LOC ? NSPACEL : NSPACE)); *flagp |= HASWIDTH|SIMPLE; nextchar(pRExC_state); Set_Node_Length(ret, 2); /* MJD */ @@ -2938,7 +4074,7 @@ tryagain: case 'P': { char* oldregxend = RExC_end; - char* parse_start = RExC_parse; + char* parse_start = RExC_parse - 2; if (RExC_parse[1] == '{') { /* a lovely hack--pretend we saw [\pX] instead */ @@ -2951,15 +4087,20 @@ tryagain: } RExC_end++; } - else + else { RExC_end = RExC_parse + 2; + if (RExC_end > oldregxend) + RExC_end = oldregxend; + } RExC_parse--; ret = regclass(pRExC_state); RExC_end = oldregxend; RExC_parse--; - Set_Node_Cur_Length(ret); /* MJD */ + + Set_Node_Offset(ret, parse_start + 2); + Set_Node_Cur_Length(ret); nextchar(pRExC_state); *flagp |= HASWIDTH|SIMPLE; } @@ -2977,7 +4118,7 @@ tryagain: case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9': { - I32 num = atoi(RExC_parse); + const I32 num = atoi(RExC_parse); if (num > 9 && num >= RExC_npar) goto defchar; @@ -2986,16 +4127,16 @@ tryagain: while (isDIGIT(*RExC_parse)) RExC_parse++; - if (!SIZE_ONLY && num > RExC_rx->nparens) + if (!SIZE_ONLY && num > (I32)RExC_rx->nparens) vFAIL("Reference to nonexistent group"); RExC_sawback = 1; - ret = reganode(pRExC_state, FOLD - ? (LOC ? REFFL : REFF) - : REF, num); + ret = reganode(pRExC_state, + (U8)(FOLD ? (LOC ? REFFL : REFF) : REF), + num); *flagp |= HASWIDTH; - + /* override incorrect value set in reganode MJD */ - Set_Node_Offset(ret, parse_start+1); + Set_Node_Offset(ret, parse_start+1); Set_Node_Cur_Length(ret); /* MJD */ RExC_parse--; nextchar(pRExC_state); @@ -3007,14 +4148,15 @@ tryagain: FAIL("Trailing \\"); /* FALL THROUGH */ default: - /* Do not generate `unrecognized' warnings here, we fall + /* Do not generate "unrecognized" warnings here, we fall back into the quick-grab loop below */ + parse_start--; goto defchar; } break; case '#': - if (RExC_flags16 & PMf_EXTENDED) { + if (RExC_flags & PMf_EXTENDED) { while (RExC_parse < RExC_end && *RExC_parse != '\n') RExC_parse++; if (RExC_parse < RExC_end) goto tryagain; @@ -3026,18 +4168,17 @@ tryagain: register UV ender; register char *p; char *oldp, *s; - STRLEN numlen; STRLEN foldlen; - U8 tmpbuf[UTF8_MAXLEN_FOLD+1], *foldbuf; + U8 tmpbuf[UTF8_MAXBYTES_CASE+1], *foldbuf; parse_start = RExC_parse - 1; RExC_parse++; defchar: - ret = reg_node(pRExC_state, FOLD - ? (LOC ? EXACTFL : EXACTF) - : EXACT); + ender = 0; + ret = reg_node(pRExC_state, + (U8)(FOLD ? (LOC ? EXACTFL : EXACTF) : EXACT)); s = STRING(ret); for (len = 0, p = RExC_parse - 1; len < 127 && p < RExC_end; @@ -3045,7 +4186,7 @@ tryagain: { oldp = p; - if (RExC_flags16 & PMf_EXTENDED) + if (RExC_flags & PMf_EXTENDED) p = regwhite(p, RExC_end); switch (*p) { case '^': @@ -3102,7 +4243,7 @@ tryagain: break; case 'x': if (*++p == '{') { - char* e = strchr(p, '}'); + char* const e = strchr(p, '}'); if (!e) { RExC_parse = p + 1; @@ -3111,21 +4252,16 @@ tryagain: else { I32 flags = PERL_SCAN_ALLOW_UNDERSCORES | PERL_SCAN_DISALLOW_PREFIX; - numlen = e - p - 1; + STRLEN numlen = e - p - 1; ender = grok_hex(p + 1, &numlen, &flags, NULL); if (ender > 0xff) RExC_utf8 = 1; - /* numlen is generous */ - if (numlen + len >= 127) { - p--; - goto loopdone; - } p = e + 1; } } else { I32 flags = PERL_SCAN_DISALLOW_PREFIX; - numlen = 2; + STRLEN numlen = 2; ender = grok_hex(p, &numlen, &flags, NULL); p += numlen; } @@ -3140,7 +4276,7 @@ tryagain: if (*p == '0' || (isDIGIT(p[1]) && atoi(p) >= RExC_npar) ) { I32 flags = 0; - numlen = 3; + STRLEN numlen = 3; ender = grok_oct(p, &numlen, &flags, NULL); p += numlen; } @@ -3162,6 +4298,7 @@ tryagain: default: normal_default: if (UTF8_IS_START(*p) && UTF) { + STRLEN numlen; ender = utf8n_to_uvchr((U8*)p, RExC_end - p, &numlen, 0); p += numlen; @@ -3170,7 +4307,7 @@ tryagain: ender = *p++; break; } - if (RExC_flags16 & PMf_EXTENDED) + if (RExC_flags & PMf_EXTENDED) p = regwhite(p, RExC_end); if (UTF && FOLD) { /* Prime the casefolded buffer. */ @@ -3180,52 +4317,78 @@ tryagain: if (len) p = oldp; else if (UTF) { + STRLEN unilen; + if (FOLD) { /* Emit all the Unicode characters. */ + STRLEN numlen; for (foldbuf = tmpbuf; foldlen; foldlen -= numlen) { ender = utf8_to_uvchr(foldbuf, &numlen); - reguni(pRExC_state, ender, s, &numlen); - s += numlen; - len += numlen; - foldbuf += numlen; + if (numlen > 0) { + reguni(pRExC_state, ender, s, &unilen); + s += unilen; + len += unilen; + /* In EBCDIC the numlen + * and unilen can differ. */ + foldbuf += numlen; + if (numlen >= foldlen) + break; + } + else + break; /* "Can't happen." */ } } else { - reguni(pRExC_state, ender, s, &numlen); - s += numlen; - len += numlen; + reguni(pRExC_state, ender, s, &unilen); + if (unilen > 0) { + s += unilen; + len += unilen; + } } } else { len++; - REGC(ender, s++); + REGC((char)ender, s++); } break; } if (UTF) { + STRLEN unilen; + if (FOLD) { /* Emit all the Unicode characters. */ + STRLEN numlen; for (foldbuf = tmpbuf; foldlen; foldlen -= numlen) { ender = utf8_to_uvchr(foldbuf, &numlen); - reguni(pRExC_state, ender, s, &numlen); - s += numlen; - len += numlen; - foldbuf += numlen; + if (numlen > 0) { + reguni(pRExC_state, ender, s, &unilen); + len += unilen; + s += unilen; + /* In EBCDIC the numlen + * and unilen can differ. */ + foldbuf += numlen; + if (numlen >= foldlen) + break; + } + else + break; } } else { - reguni(pRExC_state, ender, s, &numlen); - s += numlen; - len += numlen; + reguni(pRExC_state, ender, s, &unilen); + if (unilen > 0) { + s += unilen; + len += unilen; + } } len--; } else - REGC(ender, s++); + REGC((char)ender, s++); } loopdone: RExC_parse = p - 1; @@ -3239,7 +4402,7 @@ tryagain: } if (len > 0) *flagp |= HASWIDTH; - if (len == 1) + if (len == 1 && UNI_IS_INVARIANT(ender)) *flagp |= SIMPLE; if (!SIZE_ONLY) STR_LEN(ret) = len; @@ -3254,32 +4417,35 @@ tryagain: /* If the encoding pragma is in effect recode the text of * any EXACT-kind nodes. */ if (PL_encoding && PL_regkind[(U8)OP(ret)] == EXACT) { - STRLEN oldlen = STR_LEN(ret); - SV *sv = sv_2mortal(newSVpvn(STRING(ret), oldlen)); - - if (RExC_utf8) - SvUTF8_on(sv); - if (sv_utf8_downgrade(sv, TRUE)) { - char *s = Perl_sv_recode_to_utf8(aTHX_ sv, PL_encoding); - STRLEN newlen = SvCUR(sv); - - if (!SIZE_ONLY) { - DEBUG_r(PerlIO_printf(Perl_debug_log, "recode %*s to %*s\n", - (int)oldlen, STRING(ret), - (int)newlen, s)); - Copy(s, STRING(ret), newlen, char); - STR_LEN(ret) += newlen - oldlen; - RExC_emit += STR_SZ(newlen) - STR_SZ(oldlen); - } else - RExC_size += STR_SZ(newlen) - STR_SZ(oldlen); - } + STRLEN oldlen = STR_LEN(ret); + SV *sv = sv_2mortal(newSVpvn(STRING(ret), oldlen)); + + if (RExC_utf8) + SvUTF8_on(sv); + if (sv_utf8_downgrade(sv, TRUE)) { + const char * const s = sv_recode_to_utf8(sv, PL_encoding); + const STRLEN newlen = SvCUR(sv); + + if (SvUTF8(sv)) + RExC_utf8 = 1; + if (!SIZE_ONLY) { + GET_RE_DEBUG_FLAGS_DECL; + DEBUG_COMPILE_r(PerlIO_printf(Perl_debug_log, "recode %*s to %*s\n", + (int)oldlen, STRING(ret), + (int)newlen, s)); + Copy(s, STRING(ret), newlen, char); + STR_LEN(ret) += newlen - oldlen; + RExC_emit += STR_SZ(newlen) - STR_SZ(oldlen); + } else + RExC_size += STR_SZ(newlen) - STR_SZ(oldlen); + } } return(ret); } STATIC char * -S_regwhite(pTHX_ char *p, char *e) +S_regwhite(pTHX_ char *p, const char *e) { while (p < e) { if (isSPACE(*p)) @@ -3314,7 +4480,7 @@ S_regpposixcc(pTHX_ RExC_state_t *pRExC_state, I32 value) if (value == '[' && RExC_parse + 1 < RExC_end && /* I smell either [: or [= or [. -- POSIX has been here, right? */ POSIXCC(UCHARAT(RExC_parse))) { - char c = UCHARAT(RExC_parse); + const char c = UCHARAT(RExC_parse); char* s = RExC_parse++; while (RExC_parse < RExC_end && UCHARAT(RExC_parse) != c) @@ -3323,92 +4489,127 @@ S_regpposixcc(pTHX_ RExC_state_t *pRExC_state, I32 value) /* Grandfather lone [:, [=, [. */ RExC_parse = s; else { - char* t = RExC_parse++; /* skip over the c */ + const char* t = RExC_parse++; /* skip over the c */ + + assert(*t == c); if (UCHARAT(RExC_parse) == ']') { RExC_parse++; /* skip over the ending ] */ posixcc = s + 1; if (*s == ':') { - I32 complement = *posixcc == '^' ? *posixcc++ : 0; - I32 skip = 5; /* the most common skip */ - - switch (*posixcc) { - case 'a': - if (strnEQ(posixcc, "alnum", 5)) - namedclass = - complement ? ANYOF_NALNUMC : ANYOF_ALNUMC; - else if (strnEQ(posixcc, "alpha", 5)) - namedclass = - complement ? ANYOF_NALPHA : ANYOF_ALPHA; - else if (strnEQ(posixcc, "ascii", 5)) - namedclass = - complement ? ANYOF_NASCII : ANYOF_ASCII; - break; - case 'b': - if (strnEQ(posixcc, "blank", 5)) - namedclass = - complement ? ANYOF_NBLANK : ANYOF_BLANK; - break; - case 'c': - if (strnEQ(posixcc, "cntrl", 5)) - namedclass = - complement ? ANYOF_NCNTRL : ANYOF_CNTRL; - break; - case 'd': - if (strnEQ(posixcc, "digit", 5)) - namedclass = - complement ? ANYOF_NDIGIT : ANYOF_DIGIT; - break; - case 'g': - if (strnEQ(posixcc, "graph", 5)) - namedclass = - complement ? ANYOF_NGRAPH : ANYOF_GRAPH; - break; - case 'l': - if (strnEQ(posixcc, "lower", 5)) - namedclass = - complement ? ANYOF_NLOWER : ANYOF_LOWER; - break; - case 'p': - if (strnEQ(posixcc, "print", 5)) - namedclass = - complement ? ANYOF_NPRINT : ANYOF_PRINT; - else if (strnEQ(posixcc, "punct", 5)) - namedclass = - complement ? ANYOF_NPUNCT : ANYOF_PUNCT; - break; - case 's': - if (strnEQ(posixcc, "space", 5)) - namedclass = - complement ? ANYOF_NPSXSPC : ANYOF_PSXSPC; + const I32 complement = *posixcc == '^' ? *posixcc++ : 0; + const I32 skip = t - posixcc; + + /* Initially switch on the length of the name. */ + switch (skip) { + case 4: + if (memEQ(posixcc, "word", 4)) { + /* this is not POSIX, this is the Perl \w */; + namedclass + = complement ? ANYOF_NALNUM : ANYOF_ALNUM; + } break; - case 'u': - if (strnEQ(posixcc, "upper", 5)) - namedclass = - complement ? ANYOF_NUPPER : ANYOF_UPPER; - break; - case 'w': /* this is not POSIX, this is the Perl \w */ - if (strnEQ(posixcc, "word", 4)) { - namedclass = - complement ? ANYOF_NALNUM : ANYOF_ALNUM; - skip = 4; + case 5: + /* Names all of length 5. */ + /* alnum alpha ascii blank cntrl digit graph lower + print punct space upper */ + /* Offset 4 gives the best switch position. */ + switch (posixcc[4]) { + case 'a': + if (memEQ(posixcc, "alph", 4)) { + /* a */ + namedclass + = complement ? ANYOF_NALPHA : ANYOF_ALPHA; + } + break; + case 'e': + if (memEQ(posixcc, "spac", 4)) { + /* e */ + namedclass + = complement ? ANYOF_NPSXSPC : ANYOF_PSXSPC; + } + break; + case 'h': + if (memEQ(posixcc, "grap", 4)) { + /* h */ + namedclass + = complement ? ANYOF_NGRAPH : ANYOF_GRAPH; + } + break; + case 'i': + if (memEQ(posixcc, "asci", 4)) { + /* i */ + namedclass + = complement ? ANYOF_NASCII : ANYOF_ASCII; + } + break; + case 'k': + if (memEQ(posixcc, "blan", 4)) { + /* k */ + namedclass + = complement ? ANYOF_NBLANK : ANYOF_BLANK; + } + break; + case 'l': + if (memEQ(posixcc, "cntr", 4)) { + /* l */ + namedclass + = complement ? ANYOF_NCNTRL : ANYOF_CNTRL; + } + break; + case 'm': + if (memEQ(posixcc, "alnu", 4)) { + /* m */ + namedclass + = complement ? ANYOF_NALNUMC : ANYOF_ALNUMC; + } + break; + case 'r': + if (memEQ(posixcc, "lowe", 4)) { + /* r */ + namedclass + = complement ? ANYOF_NLOWER : ANYOF_LOWER; + } + if (memEQ(posixcc, "uppe", 4)) { + /* r */ + namedclass + = complement ? ANYOF_NUPPER : ANYOF_UPPER; + } + break; + case 't': + if (memEQ(posixcc, "digi", 4)) { + /* t */ + namedclass + = complement ? ANYOF_NDIGIT : ANYOF_DIGIT; + } + if (memEQ(posixcc, "prin", 4)) { + /* t */ + namedclass + = complement ? ANYOF_NPRINT : ANYOF_PRINT; + } + if (memEQ(posixcc, "punc", 4)) { + /* t */ + namedclass + = complement ? ANYOF_NPUNCT : ANYOF_PUNCT; + } + break; } break; - case 'x': - if (strnEQ(posixcc, "xdigit", 6)) { - namedclass = - complement ? ANYOF_NXDIGIT : ANYOF_XDIGIT; - skip = 6; + case 6: + if (memEQ(posixcc, "xdigit", 6)) { + namedclass + = complement ? ANYOF_NXDIGIT : ANYOF_XDIGIT; } break; } - if (namedclass == OOB_NAMEDCLASS || - posixcc[skip] != ':' || - posixcc[skip+1] != ']') + + if (namedclass == OOB_NAMEDCLASS) { Simple_vFAIL3("POSIX class [:%.*s:] unknown", t - s - 1, s + 1); } + assert (posixcc[skip] == ':'); + assert (posixcc[skip+1] == ']'); } else if (!SIZE_ONLY) { /* [[=foo=]] and [[.foo.]] are still future. */ @@ -3432,15 +4633,17 @@ S_regpposixcc(pTHX_ RExC_state_t *pRExC_state, I32 value) STATIC void S_checkposixcc(pTHX_ RExC_state_t *pRExC_state) { - if (!SIZE_ONLY && ckWARN(WARN_REGEXP) && - POSIXCC(UCHARAT(RExC_parse))) { - char *s = RExC_parse; - char c = *s++; + if (!SIZE_ONLY && POSIXCC(UCHARAT(RExC_parse))) { + const char *s = RExC_parse; + const char c = *s++; while(*s && isALNUM(*s)) s++; if (*s && c == *s && s[1] == ']') { - vWARN3(s+2, "POSIX syntax [%c %c] belongs inside character classes", c, c); + if (ckWARN(WARN_REGEXP)) + vWARN3(s+2, + "POSIX syntax [%c %c] belongs inside character classes", + c, c); /* [[=foo=]] and [[.foo.]] are still future. */ if (POSIXCC_NOTYET(c)) { @@ -3471,6 +4674,9 @@ S_regclass(pTHX_ RExC_state_t *pRExC_state) UV n; bool optimize_invert = TRUE; AV* unicode_alternate = 0; +#ifdef EBCDIC + UV literal_endpoint = 0; +#endif ret = reganode(pRExC_state, ANYOF, 0); @@ -3498,7 +4704,7 @@ S_regclass(pTHX_ RExC_state_t *pRExC_state) nextvalue = RExC_parse < RExC_end ? UCHARAT(RExC_parse) : 0; - if (!SIZE_ONLY && ckWARN(WARN_REGEXP) && POSIXCC(nextvalue)) + if (!SIZE_ONLY && POSIXCC(nextvalue)) checkposixcc(pRExC_state); /* allow 1st char to be ] (allowing it to be - is dealt with later) */ @@ -3547,8 +4753,10 @@ S_regclass(pTHX_ RExC_state_t *pRExC_state) case 'D': namedclass = ANYOF_NDIGIT; break; case 'p': case 'P': + if (RExC_parse >= RExC_end) + vFAIL2("Empty \\%c{}", (U8)value); if (*RExC_parse == '{') { - U8 c = (U8)value; + const U8 c = (U8)value; e = strchr(RExC_parse++, '}'); if (!e) vFAIL2("Missing right brace on \\%c{}", c); @@ -3583,7 +4791,8 @@ S_regclass(pTHX_ RExC_state_t *pRExC_state) } RExC_parse = e + 1; ANYOF_FLAGS(ret) |= ANYOF_UNICODE; - continue; + namedclass = ANYOF_MAX; /* no official name, but it's named */ + break; case 'n': value = '\n'; break; case 'r': value = '\r'; break; case 't': value = '\t'; break; @@ -3631,6 +4840,10 @@ S_regclass(pTHX_ RExC_state_t *pRExC_state) break; } } /* end of \blah */ +#ifdef EBCDIC + else + literal_endpoint++; +#endif if (namedclass > OOB_NAMEDCLASS) { /* this is a named class \blah */ @@ -3663,6 +4876,9 @@ S_regclass(pTHX_ RExC_state_t *pRExC_state) } if (!SIZE_ONLY) { + const char *what = NULL; + char yesno = 0; + if (namedclass > OOB_NAMEDCLASS) optimize_invert = FALSE; /* Possible truncation here but in some 64-bit environments @@ -3678,7 +4894,8 @@ S_regclass(pTHX_ RExC_state_t *pRExC_state) if (isALNUM(value)) ANYOF_BITMAP_SET(ret, value); } - Perl_sv_catpvf(aTHX_ listsv, "+utf8::IsWord\n"); + yesno = '+'; + what = "Word"; break; case ANYOF_NALNUM: if (LOC) @@ -3688,7 +4905,8 @@ S_regclass(pTHX_ RExC_state_t *pRExC_state) if (!isALNUM(value)) ANYOF_BITMAP_SET(ret, value); } - Perl_sv_catpvf(aTHX_ listsv, "!utf8::IsWord\n"); + yesno = '!'; + what = "Word"; break; case ANYOF_ALNUMC: if (LOC) @@ -3698,7 +4916,8 @@ S_regclass(pTHX_ RExC_state_t *pRExC_state) if (isALNUMC(value)) ANYOF_BITMAP_SET(ret, value); } - Perl_sv_catpvf(aTHX_ listsv, "+utf8::IsAlnum\n"); + yesno = '+'; + what = "Alnum"; break; case ANYOF_NALNUMC: if (LOC) @@ -3708,7 +4927,8 @@ S_regclass(pTHX_ RExC_state_t *pRExC_state) if (!isALNUMC(value)) ANYOF_BITMAP_SET(ret, value); } - Perl_sv_catpvf(aTHX_ listsv, "!utf8::IsAlnum\n"); + yesno = '!'; + what = "Alnum"; break; case ANYOF_ALPHA: if (LOC) @@ -3718,7 +4938,8 @@ S_regclass(pTHX_ RExC_state_t *pRExC_state) if (isALPHA(value)) ANYOF_BITMAP_SET(ret, value); } - Perl_sv_catpvf(aTHX_ listsv, "+utf8::IsAlpha\n"); + yesno = '+'; + what = "Alpha"; break; case ANYOF_NALPHA: if (LOC) @@ -3728,7 +4949,8 @@ S_regclass(pTHX_ RExC_state_t *pRExC_state) if (!isALPHA(value)) ANYOF_BITMAP_SET(ret, value); } - Perl_sv_catpvf(aTHX_ listsv, "!utf8::IsAlpha\n"); + yesno = '!'; + what = "Alpha"; break; case ANYOF_ASCII: if (LOC) @@ -3744,7 +4966,8 @@ S_regclass(pTHX_ RExC_state_t *pRExC_state) } #endif /* EBCDIC */ } - Perl_sv_catpvf(aTHX_ listsv, "+utf8::IsASCII\n"); + yesno = '+'; + what = "ASCII"; break; case ANYOF_NASCII: if (LOC) @@ -3760,7 +4983,8 @@ S_regclass(pTHX_ RExC_state_t *pRExC_state) } #endif /* EBCDIC */ } - Perl_sv_catpvf(aTHX_ listsv, "!utf8::IsASCII\n"); + yesno = '!'; + what = "ASCII"; break; case ANYOF_BLANK: if (LOC) @@ -3770,7 +4994,8 @@ S_regclass(pTHX_ RExC_state_t *pRExC_state) if (isBLANK(value)) ANYOF_BITMAP_SET(ret, value); } - Perl_sv_catpvf(aTHX_ listsv, "+utf8::IsBlank\n"); + yesno = '+'; + what = "Blank"; break; case ANYOF_NBLANK: if (LOC) @@ -3780,7 +5005,8 @@ S_regclass(pTHX_ RExC_state_t *pRExC_state) if (!isBLANK(value)) ANYOF_BITMAP_SET(ret, value); } - Perl_sv_catpvf(aTHX_ listsv, "!utf8::IsBlank\n"); + yesno = '!'; + what = "Blank"; break; case ANYOF_CNTRL: if (LOC) @@ -3790,7 +5016,8 @@ S_regclass(pTHX_ RExC_state_t *pRExC_state) if (isCNTRL(value)) ANYOF_BITMAP_SET(ret, value); } - Perl_sv_catpvf(aTHX_ listsv, "+utf8::IsCntrl\n"); + yesno = '+'; + what = "Cntrl"; break; case ANYOF_NCNTRL: if (LOC) @@ -3800,7 +5027,8 @@ S_regclass(pTHX_ RExC_state_t *pRExC_state) if (!isCNTRL(value)) ANYOF_BITMAP_SET(ret, value); } - Perl_sv_catpvf(aTHX_ listsv, "!utf8::IsCntrl\n"); + yesno = '!'; + what = "Cntrl"; break; case ANYOF_DIGIT: if (LOC) @@ -3810,7 +5038,8 @@ S_regclass(pTHX_ RExC_state_t *pRExC_state) for (value = '0'; value <= '9'; value++) ANYOF_BITMAP_SET(ret, value); } - Perl_sv_catpvf(aTHX_ listsv, "+utf8::IsDigit\n"); + yesno = '+'; + what = "Digit"; break; case ANYOF_NDIGIT: if (LOC) @@ -3822,7 +5051,8 @@ S_regclass(pTHX_ RExC_state_t *pRExC_state) for (value = '9' + 1; value < 256; value++) ANYOF_BITMAP_SET(ret, value); } - Perl_sv_catpvf(aTHX_ listsv, "!utf8::IsDigit\n"); + yesno = '!'; + what = "Digit"; break; case ANYOF_GRAPH: if (LOC) @@ -3832,7 +5062,8 @@ S_regclass(pTHX_ RExC_state_t *pRExC_state) if (isGRAPH(value)) ANYOF_BITMAP_SET(ret, value); } - Perl_sv_catpvf(aTHX_ listsv, "+utf8::IsGraph\n"); + yesno = '+'; + what = "Graph"; break; case ANYOF_NGRAPH: if (LOC) @@ -3842,7 +5073,8 @@ S_regclass(pTHX_ RExC_state_t *pRExC_state) if (!isGRAPH(value)) ANYOF_BITMAP_SET(ret, value); } - Perl_sv_catpvf(aTHX_ listsv, "!utf8::IsGraph\n"); + yesno = '!'; + what = "Graph"; break; case ANYOF_LOWER: if (LOC) @@ -3852,7 +5084,8 @@ S_regclass(pTHX_ RExC_state_t *pRExC_state) if (isLOWER(value)) ANYOF_BITMAP_SET(ret, value); } - Perl_sv_catpvf(aTHX_ listsv, "+utf8::IsLower\n"); + yesno = '+'; + what = "Lower"; break; case ANYOF_NLOWER: if (LOC) @@ -3862,7 +5095,8 @@ S_regclass(pTHX_ RExC_state_t *pRExC_state) if (!isLOWER(value)) ANYOF_BITMAP_SET(ret, value); } - Perl_sv_catpvf(aTHX_ listsv, "!utf8::IsLower\n"); + yesno = '!'; + what = "Lower"; break; case ANYOF_PRINT: if (LOC) @@ -3872,7 +5106,8 @@ S_regclass(pTHX_ RExC_state_t *pRExC_state) if (isPRINT(value)) ANYOF_BITMAP_SET(ret, value); } - Perl_sv_catpvf(aTHX_ listsv, "+utf8::IsPrint\n"); + yesno = '+'; + what = "Print"; break; case ANYOF_NPRINT: if (LOC) @@ -3882,7 +5117,8 @@ S_regclass(pTHX_ RExC_state_t *pRExC_state) if (!isPRINT(value)) ANYOF_BITMAP_SET(ret, value); } - Perl_sv_catpvf(aTHX_ listsv, "!utf8::IsPrint\n"); + yesno = '!'; + what = "Print"; break; case ANYOF_PSXSPC: if (LOC) @@ -3892,7 +5128,8 @@ S_regclass(pTHX_ RExC_state_t *pRExC_state) if (isPSXSPC(value)) ANYOF_BITMAP_SET(ret, value); } - Perl_sv_catpvf(aTHX_ listsv, "+utf8::IsSpace\n"); + yesno = '+'; + what = "Space"; break; case ANYOF_NPSXSPC: if (LOC) @@ -3902,7 +5139,8 @@ S_regclass(pTHX_ RExC_state_t *pRExC_state) if (!isPSXSPC(value)) ANYOF_BITMAP_SET(ret, value); } - Perl_sv_catpvf(aTHX_ listsv, "!utf8::IsSpace\n"); + yesno = '!'; + what = "Space"; break; case ANYOF_PUNCT: if (LOC) @@ -3912,7 +5150,8 @@ S_regclass(pTHX_ RExC_state_t *pRExC_state) if (isPUNCT(value)) ANYOF_BITMAP_SET(ret, value); } - Perl_sv_catpvf(aTHX_ listsv, "+utf8::IsPunct\n"); + yesno = '+'; + what = "Punct"; break; case ANYOF_NPUNCT: if (LOC) @@ -3922,7 +5161,8 @@ S_regclass(pTHX_ RExC_state_t *pRExC_state) if (!isPUNCT(value)) ANYOF_BITMAP_SET(ret, value); } - Perl_sv_catpvf(aTHX_ listsv, "!utf8::IsPunct\n"); + yesno = '!'; + what = "Punct"; break; case ANYOF_SPACE: if (LOC) @@ -3932,7 +5172,8 @@ S_regclass(pTHX_ RExC_state_t *pRExC_state) if (isSPACE(value)) ANYOF_BITMAP_SET(ret, value); } - Perl_sv_catpvf(aTHX_ listsv, "+utf8::IsSpacePerl\n"); + yesno = '+'; + what = "SpacePerl"; break; case ANYOF_NSPACE: if (LOC) @@ -3942,7 +5183,8 @@ S_regclass(pTHX_ RExC_state_t *pRExC_state) if (!isSPACE(value)) ANYOF_BITMAP_SET(ret, value); } - Perl_sv_catpvf(aTHX_ listsv, "!utf8::IsSpacePerl\n"); + yesno = '!'; + what = "SpacePerl"; break; case ANYOF_UPPER: if (LOC) @@ -3952,7 +5194,8 @@ S_regclass(pTHX_ RExC_state_t *pRExC_state) if (isUPPER(value)) ANYOF_BITMAP_SET(ret, value); } - Perl_sv_catpvf(aTHX_ listsv, "+utf8::IsUpper\n"); + yesno = '+'; + what = "Upper"; break; case ANYOF_NUPPER: if (LOC) @@ -3962,7 +5205,8 @@ S_regclass(pTHX_ RExC_state_t *pRExC_state) if (!isUPPER(value)) ANYOF_BITMAP_SET(ret, value); } - Perl_sv_catpvf(aTHX_ listsv, "!utf8::IsUpper\n"); + yesno = '!'; + what = "Upper"; break; case ANYOF_XDIGIT: if (LOC) @@ -3972,7 +5216,8 @@ S_regclass(pTHX_ RExC_state_t *pRExC_state) if (isXDIGIT(value)) ANYOF_BITMAP_SET(ret, value); } - Perl_sv_catpvf(aTHX_ listsv, "+utf8::IsXDigit\n"); + yesno = '+'; + what = "XDigit"; break; case ANYOF_NXDIGIT: if (LOC) @@ -3982,12 +5227,20 @@ S_regclass(pTHX_ RExC_state_t *pRExC_state) if (!isXDIGIT(value)) ANYOF_BITMAP_SET(ret, value); } - Perl_sv_catpvf(aTHX_ listsv, "!utf8::IsXDigit\n"); + yesno = '!'; + what = "XDigit"; + break; + case ANYOF_MAX: + /* this is to handle \p and \P */ break; default: vFAIL("Invalid [::] class"); break; } + if (what) { + /* Strings such as "+utf8::isWord\n" */ + Perl_sv_catpvf(aTHX_ listsv, "%cutf8::Is%s\n", yesno, what); + } if (LOC) ANYOF_FLAGS(ret) |= ANYOF_CLASS; continue; @@ -3995,7 +5248,7 @@ S_regclass(pTHX_ RExC_state_t *pRExC_state) } /* end of namedclass \blah */ if (range) { - if (prevvalue > value) /* b-a */ { + if (prevvalue > (IV)value) /* b-a */ { Simple_vFAIL4("Invalid [] range \"%*.*s\"", RExC_parse - rangebegin, RExC_parse - rangebegin, @@ -4030,11 +5283,14 @@ S_regclass(pTHX_ RExC_state_t *pRExC_state) IV i; if (prevvalue < 256) { - IV ceilvalue = value < 256 ? value : 255; + const IV ceilvalue = value < 256 ? value : 255; #ifdef EBCDIC - if ((isLOWER(prevvalue) && isLOWER(ceilvalue)) || - (isUPPER(prevvalue) && isUPPER(ceilvalue))) + /* In EBCDIC [\x89-\x91] should include + * the \x8e but [i-j] should not. */ + if (literal_endpoint == 2 && + ((isLOWER(prevvalue) && isLOWER(ceilvalue)) || + (isUPPER(prevvalue) && isUPPER(ceilvalue)))) { if (isLOWER(prevvalue)) { for (i = prevvalue; i <= ceilvalue; i++) @@ -4052,28 +5308,26 @@ S_regclass(pTHX_ RExC_state_t *pRExC_state) ANYOF_BITMAP_SET(ret, i); } if (value > 255 || UTF) { + const UV prevnatvalue = NATIVE_TO_UNI(prevvalue); + const UV natvalue = NATIVE_TO_UNI(value); + ANYOF_FLAGS(ret) |= ANYOF_UNICODE; - if (prevvalue < value) + if (prevnatvalue < natvalue) { /* what about > ? */ Perl_sv_catpvf(aTHX_ listsv, "%04"UVxf"\t%04"UVxf"\n", - (UV)prevvalue, (UV)value); - else if (prevvalue == value) { - Perl_sv_catpvf(aTHX_ listsv, "%04"UVxf"\n", - (UV)value); + prevnatvalue, natvalue); + } + else if (prevnatvalue == natvalue) { + Perl_sv_catpvf(aTHX_ listsv, "%04"UVxf"\n", natvalue); if (FOLD) { - U8 tmpbuf [UTF8_MAXLEN+1]; - U8 foldbuf[UTF8_MAXLEN_FOLD+1]; + U8 foldbuf[UTF8_MAXBYTES_CASE+1]; STRLEN foldlen; - UV f; - - uvchr_to_utf8(tmpbuf, value); - to_utf8_fold(tmpbuf, foldbuf, &foldlen); - f = utf8_to_uvchr(foldbuf, 0); + const UV f = to_uni_fold(natvalue, foldbuf, &foldlen); /* If folding and foldable and a single * character, insert also the folded version * to the charclass. */ if (f != value) { - if (foldlen == UNISKIP(f)) + if (foldlen == (STRLEN)UNISKIP(f)) Perl_sv_catpvf(aTHX_ listsv, "%04"UVxf"\n", f); else { @@ -4116,6 +5370,9 @@ S_regclass(pTHX_ RExC_state_t *pRExC_state) } } } +#ifdef EBCDIC + literal_endpoint = 0; +#endif } range = 0; /* this range (if it was one) is done now */ @@ -4136,7 +5393,7 @@ S_regclass(pTHX_ RExC_state_t *pRExC_state) ) { for (value = 0; value < 256; ++value) { if (ANYOF_BITMAP_TEST(ret, value)) { - IV fold = PL_fold[value]; + UV fold = PL_fold[value]; if (fold != value) ANYOF_BITMAP_SET(ret, fold); @@ -4159,11 +5416,11 @@ S_regclass(pTHX_ RExC_state_t *pRExC_state) SV *rv; /* The 0th element stores the character class description - * in its textual form: used later (regexec.c:Perl_regclass_swatch()) + * in its textual form: used later (regexec.c:Perl_regclass_swash()) * to initialize the appropriate swash (which gets stored in * the 1st element), and also useful for dumping the regnode. * The 2nd element stores the multicharacter foldings, - * used later (regexec.c:s_reginclasslen()). */ + * used later (regexec.c:S_reginclass()). */ av_store(av, 0, listsv); av_store(av, 1, NULL); av_store(av, 2, (SV*)unicode_alternate); @@ -4184,20 +5441,22 @@ S_nextchar(pTHX_ RExC_state_t *pRExC_state) for (;;) { if (*RExC_parse == '(' && RExC_parse[1] == '?' && RExC_parse[2] == '#') { - while (*RExC_parse && *RExC_parse != ')') + while (*RExC_parse != ')') { + if (RExC_parse == RExC_end) + FAIL("Sequence (?#... not terminated"); RExC_parse++; + } RExC_parse++; continue; } - if (RExC_flags16 & PMf_EXTENDED) { + if (RExC_flags & PMf_EXTENDED) { if (isSPACE(*RExC_parse)) { RExC_parse++; continue; } else if (*RExC_parse == '#') { - while (*RExC_parse && *RExC_parse != '\n') - RExC_parse++; - RExC_parse++; + while (RExC_parse < RExC_end) + if (*RExC_parse++ == '\n') break; continue; } } @@ -4211,10 +5470,9 @@ S_nextchar(pTHX_ RExC_state_t *pRExC_state) STATIC regnode * /* Location. */ S_reg_node(pTHX_ RExC_state_t *pRExC_state, U8 op) { - register regnode *ret; register regnode *ptr; + regnode * const ret = RExC_emit; - ret = RExC_emit; if (SIZE_ONLY) { SIZE_ALIGN(RExC_size); RExC_size += 1; @@ -4225,7 +5483,7 @@ S_reg_node(pTHX_ RExC_state_t *pRExC_state, U8 op) ptr = ret; FILL_ADVANCE_NODE(ptr, op); if (RExC_offsets) { /* MJD */ - MJD_OFFSET_DEBUG((stderr, "%s:%u: (op %s) %s %u <- %u (len %u) (max %u).\n", + MJD_OFFSET_DEBUG(("%s:%u: (op %s) %s %u <- %u (len %u) (max %u).\n", "reg_node", __LINE__, reg_name[op], RExC_emit - RExC_emit_start > RExC_offsets[0] @@ -4233,7 +5491,7 @@ S_reg_node(pTHX_ RExC_state_t *pRExC_state, U8 op) RExC_emit - RExC_emit_start, RExC_parse - RExC_start, RExC_offsets[0])); - Set_Node_Offset(RExC_emit, RExC_parse + (op == END)); + Set_Node_Offset(RExC_emit, RExC_parse + (op == END)); } RExC_emit = ptr; @@ -4247,10 +5505,9 @@ S_reg_node(pTHX_ RExC_state_t *pRExC_state, U8 op) STATIC regnode * /* Location. */ S_reganode(pTHX_ RExC_state_t *pRExC_state, U8 op, U32 arg) { - register regnode *ret; register regnode *ptr; + regnode * const ret = RExC_emit; - ret = RExC_emit; if (SIZE_ONLY) { SIZE_ALIGN(RExC_size); RExC_size += 2; @@ -4261,14 +5518,16 @@ S_reganode(pTHX_ RExC_state_t *pRExC_state, U8 op, U32 arg) ptr = ret; FILL_ADVANCE_NODE_ARG(ptr, op, arg); if (RExC_offsets) { /* MJD */ - MJD_OFFSET_DEBUG((stderr, "%s: %s %u <- %u (max %u).\n", + MJD_OFFSET_DEBUG(("%s(%d): (op %s) %s %u <- %u (max %u).\n", "reganode", + __LINE__, + reg_name[op], RExC_emit - RExC_emit_start > RExC_offsets[0] ? "Overwriting end of array!\n" : "OK", RExC_emit - RExC_emit_start, RExC_parse - RExC_start, RExC_offsets[0])); - Set_Cur_Node_Offset; + Set_Cur_Node_Offset; } RExC_emit = ptr; @@ -4296,7 +5555,7 @@ S_reginsert(pTHX_ RExC_state_t *pRExC_state, U8 op, regnode *opnd) register regnode *src; register regnode *dst; register regnode *place; - register int offset = regarglen[(U8)op]; + const int offset = regarglen[(U8)op]; /* (PL_regkind[(U8)op] == CURLY ? EXTRA_STEP_2ARGS : 0); */ @@ -4311,29 +5570,34 @@ S_reginsert(pTHX_ RExC_state_t *pRExC_state, U8 op, regnode *opnd) while (src > opnd) { StructCopy(--src, --dst, regnode); if (RExC_offsets) { /* MJD 20010112 */ - MJD_OFFSET_DEBUG((stderr, "%s: %s copy %u -> %u (max %u).\n", + MJD_OFFSET_DEBUG(("%s(%d): (op %s) %s copy %u -> %u (max %u).\n", "reg_insert", + __LINE__, + reg_name[op], dst - RExC_emit_start > RExC_offsets[0] ? "Overwriting end of array!\n" : "OK", src - RExC_emit_start, dst - RExC_emit_start, RExC_offsets[0])); - Set_Node_Offset_To_R(dst-RExC_emit_start, Node_Offset(src)); - Set_Node_Length_To_R(dst-RExC_emit_start, Node_Length(src)); + Set_Node_Offset_To_R(dst-RExC_emit_start, Node_Offset(src)); + Set_Node_Length_To_R(dst-RExC_emit_start, Node_Length(src)); } } place = opnd; /* Op node, where operand used to be. */ if (RExC_offsets) { /* MJD */ - MJD_OFFSET_DEBUG((stderr, "%s: %s %u <- %u (max %u).\n", + MJD_OFFSET_DEBUG(("%s(%d): (op %s) %s %u <- %u (max %u).\n", "reginsert", + __LINE__, + reg_name[op], place - RExC_emit_start > RExC_offsets[0] ? "Overwriting end of array!\n" : "OK", place - RExC_emit_start, RExC_parse - RExC_start, RExC_offsets[0])); - Set_Node_Offset(place, RExC_parse); + Set_Node_Offset(place, RExC_parse); + Set_Node_Length(place, 1); } src = NEXTOPER(place); FILL_ADVANCE_NODE(place, op); @@ -4347,7 +5611,6 @@ STATIC void S_regtail(pTHX_ RExC_state_t *pRExC_state, regnode *p, regnode *val) { register regnode *scan; - register regnode *temp; if (SIZE_ONLY) return; @@ -4355,7 +5618,7 @@ S_regtail(pTHX_ RExC_state_t *pRExC_state, regnode *p, regnode *val) /* Find last node. */ scan = p; for (;;) { - temp = regnext(scan); + regnode * const temp = regnext(scan); if (temp == NULL) break; scan = temp; @@ -4392,7 +5655,7 @@ S_regoptail(pTHX_ RExC_state_t *pRExC_state, regnode *p, regnode *val) - regcurly - a little FSA that accepts {\d+,?\d*} */ STATIC I32 -S_regcurly(pTHX_ register char *s) +S_regcurly(pTHX_ register const char *s) { if (*s++ != '{') return FALSE; @@ -4449,7 +5712,45 @@ S_dumpuntil(pTHX_ regnode *start, regnode *node, regnode *last, SV* sv, I32 l) else if (PL_regkind[(U8)op] == BRANCH) { node = dumpuntil(start, NEXTOPER(node), next, sv, l + 1); } - else if ( op == CURLY) { /* `next' might be very big: optimizer */ + else if ( PL_regkind[(U8)op] == TRIE ) { + const I32 n = ARG(node); + const reg_trie_data *trie = (reg_trie_data*)PL_regdata->data[n]; + const I32 arry_len = av_len(trie->words)+1; + I32 word_idx; + PerlIO_printf(Perl_debug_log, + "%*s[Words:%d Chars Stored:%d Unique Chars:%d States:%"IVdf"%s]\n", + (int)(2*(l+3)), + "", + trie->wordcount, + (int)trie->charcount, + trie->uniquecharcount, + (IV)trie->laststate-1, + node->flags ? " EVAL mode" : ""); + + for (word_idx=0; word_idx < arry_len; word_idx++) { + SV **elem_ptr=av_fetch(trie->words,word_idx,0); + if (elem_ptr) { + PerlIO_printf(Perl_debug_log, "%*s<%s%s%s>\n", + (int)(2*(l+4)), "", + PL_colors[0], + SvPV_nolen(*elem_ptr), + PL_colors[1] + ); + /* + if (next == NULL) + PerlIO_printf(Perl_debug_log, "(0)\n"); + else + PerlIO_printf(Perl_debug_log, "(%"IVdf")\n", (IV)(next - start)); + */ + } + + } + + node = NEXTOPER(node); + node += regarglen[(U8)op]; + + } + else if ( op == CURLY) { /* "next" might be very big: optimizer */ node = dumpuntil(start, NEXTOPER(node) + EXTRA_STEP_2ARGS, NEXTOPER(node) + EXTRA_STEP_2ARGS + 1, sv, l + 1); } @@ -4499,36 +5800,55 @@ Perl_regdump(pTHX_ regexp *r) /* Header fields of interest. */ if (r->anchored_substr) PerlIO_printf(Perl_debug_log, - "anchored `%s%.*s%s'%s at %"IVdf" ", + "anchored \"%s%.*s%s\"%s at %"IVdf" ", PL_colors[0], (int)(SvCUR(r->anchored_substr) - (SvTAIL(r->anchored_substr)!=0)), SvPVX(r->anchored_substr), PL_colors[1], SvTAIL(r->anchored_substr) ? "$" : "", (IV)r->anchored_offset); + else if (r->anchored_utf8) + PerlIO_printf(Perl_debug_log, + "anchored utf8 \"%s%.*s%s\"%s at %"IVdf" ", + PL_colors[0], + (int)(SvCUR(r->anchored_utf8) - (SvTAIL(r->anchored_utf8)!=0)), + SvPVX(r->anchored_utf8), + PL_colors[1], + SvTAIL(r->anchored_utf8) ? "$" : "", + (IV)r->anchored_offset); if (r->float_substr) PerlIO_printf(Perl_debug_log, - "floating `%s%.*s%s'%s at %"IVdf"..%"UVuf" ", + "floating \"%s%.*s%s\"%s at %"IVdf"..%"UVuf" ", PL_colors[0], (int)(SvCUR(r->float_substr) - (SvTAIL(r->float_substr)!=0)), SvPVX(r->float_substr), PL_colors[1], SvTAIL(r->float_substr) ? "$" : "", (IV)r->float_min_offset, (UV)r->float_max_offset); - if (r->check_substr) + else if (r->float_utf8) + PerlIO_printf(Perl_debug_log, + "floating utf8 \"%s%.*s%s\"%s at %"IVdf"..%"UVuf" ", + PL_colors[0], + (int)(SvCUR(r->float_utf8) - (SvTAIL(r->float_utf8)!=0)), + SvPVX(r->float_utf8), + PL_colors[1], + SvTAIL(r->float_utf8) ? "$" : "", + (IV)r->float_min_offset, (UV)r->float_max_offset); + if (r->check_substr || r->check_utf8) PerlIO_printf(Perl_debug_log, r->check_substr == r->float_substr + && r->check_utf8 == r->float_utf8 ? "(checking floating" : "(checking anchored"); if (r->reganch & ROPT_NOSCAN) PerlIO_printf(Perl_debug_log, " noscan"); if (r->reganch & ROPT_CHECK_ALL) PerlIO_printf(Perl_debug_log, " isall"); - if (r->check_substr) + if (r->check_substr || r->check_utf8) PerlIO_printf(Perl_debug_log, ") "); if (r->regstclass) { regprop(sv, r->regstclass); - PerlIO_printf(Perl_debug_log, "stclass `%s' ", SvPVX(sv)); + PerlIO_printf(Perl_debug_log, "stclass \"%s\" ", SvPVX(sv)); } if (r->reganch & ROPT_ANCH) { PerlIO_printf(Perl_debug_log, "anchored"); @@ -4553,14 +5873,16 @@ Perl_regdump(pTHX_ regexp *r) PerlIO_printf(Perl_debug_log, "with eval "); PerlIO_printf(Perl_debug_log, "\n"); if (r->offsets) { - U32 i; - U32 len = r->offsets[0]; - PerlIO_printf(Perl_debug_log, "Offsets: [%"UVuf"]\n\t", (UV)r->offsets[0]); - for (i = 1; i <= len; i++) - PerlIO_printf(Perl_debug_log, "%"UVuf"[%"UVuf"] ", - (UV)r->offsets[i*2-1], - (UV)r->offsets[i*2]); - PerlIO_printf(Perl_debug_log, "\n"); + const U32 len = r->offsets[0]; + GET_RE_DEBUG_FLAGS_DECL; + DEBUG_OFFSETS_r({ + U32 i; + PerlIO_printf(Perl_debug_log, "Offsets: [%"UVuf"]\n\t", (UV)r->offsets[0]); + for (i = 1; i <= len; i++) + PerlIO_printf(Perl_debug_log, "%"UVuf"[%"UVuf"] ", + (UV)r->offsets[i*2-1], (UV)r->offsets[i*2]); + PerlIO_printf(Perl_debug_log, "\n"); + }); } #endif /* DEBUGGING */ } @@ -4580,11 +5902,12 @@ S_put_byte(pTHX_ SV *sv, int c) #endif /* DEBUGGING */ + /* - regprop - printable representation of opcode */ void -Perl_regprop(pTHX_ SV *sv, regnode *o) +Perl_regprop(pTHX_ SV *sv, const regnode *o) { #ifdef DEBUGGING register int k; @@ -4594,7 +5917,7 @@ Perl_regprop(pTHX_ SV *sv, regnode *o) /* It would be nice to FAIL() here, but this may be called from regexec.c, and it would be hard to supply pRExC_state. */ Perl_croak(aTHX_ "Corrupted regexp opcode"); - sv_catpv(sv, (char*)reg_name[OP(o)]); /* Take off const! */ + sv_catpv(sv, reg_name[OP(o)]); /* Take off const! */ k = PL_regkind[(U8)OP(o)]; @@ -4603,20 +5926,30 @@ Perl_regprop(pTHX_ SV *sv, regnode *o) /* Using is_utf8_string() is a crude hack but it may * be the best for now since we have no flag "this EXACTish * node was UTF-8" --jhi */ - bool do_utf8 = is_utf8_string((U8*)STRING(o), STR_LEN(o)); - char *s = do_utf8 ? + const bool do_utf8 = is_utf8_string((U8*)STRING(o), STR_LEN(o)); + const char *s = do_utf8 ? pv_uni_display(dsv, (U8*)STRING(o), STR_LEN(o), 60, UNI_DISPLAY_REGEX) : STRING(o); - int len = do_utf8 ? + const int len = do_utf8 ? strlen(s) : STR_LEN(o); Perl_sv_catpvf(aTHX_ sv, " <%s%.*s%s>", PL_colors[0], len, s, PL_colors[1]); - } - else if (k == CURLY) { + } else if (k == TRIE) {/* + this isn't always safe, as Pl_regdata may not be for this regex yet + (depending on where its called from) so its being moved to dumpuntil + I32 n = ARG(o); + reg_trie_data *trie=(reg_trie_data*)PL_regdata->data[n]; + Perl_sv_catpvf(aTHX_ sv, " (W:%d L:%d C:%d S:%d)", + trie->wordcount, + trie->charcount, + trie->uniquecharcount, + trie->laststate); + */ + } else if (k == CURLY) { if (OP(o) == CURLYM || OP(o) == CURLYN || OP(o) == CURLYX) Perl_sv_catpvf(aTHX_ sv, "[%d]", o->flags); /* Parenth number */ Perl_sv_catpvf(aTHX_ sv, " {%d,%d}", ARG1(o), ARG2(o)); @@ -4630,7 +5963,7 @@ Perl_regprop(pTHX_ SV *sv, regnode *o) else if (k == ANYOF) { int i, rangestart = -1; U8 flags = ANYOF_FLAGS(o); - const char * const anyofs[] = { /* Should be syncronized with + const char * const anyofs[] = { /* Should be synchronized with * ANYOF_ #xdefines in regcomp.h */ "\\w", "\\W", @@ -4704,11 +6037,10 @@ Perl_regprop(pTHX_ SV *sv, regnode *o) if (lv) { if (sw) { - UV i; - U8 s[UTF8_MAXLEN+1]; + U8 s[UTF8_MAXBYTES_CASE+1]; for (i = 0; i <= 256; i++) { /* just the first 256 */ - U8 *e = uvchr_to_utf8(s, i); + uvchr_to_utf8(s, i); if (i < 256 && swash_fetch(sw, s, TRUE)) { if (rangestart == -1) @@ -4718,15 +6050,17 @@ Perl_regprop(pTHX_ SV *sv, regnode *o) if (i <= rangestart + 3) for (; rangestart < i; rangestart++) { + U8 *e; for(e = uvchr_to_utf8(s, rangestart), p = s; p < e; p++) put_byte(sv, *p); } else { + U8 *e; for (e = uvchr_to_utf8(s, rangestart), p = s; p < e; p++) put_byte(sv, *p); sv_catpv(sv, "-"); - for (e = uvchr_to_utf8(s, i - 1), p = s; p < e; p++) - put_byte(sv, *p); + for (e = uvchr_to_utf8(s, i - 1), p = s; p < e; p++) + put_byte(sv, *p); } rangestart = -1; } @@ -4736,13 +6070,13 @@ Perl_regprop(pTHX_ SV *sv, regnode *o) } { - char *s = savepv(SvPVX(lv)); + char *s = savesvpv(lv); char *origs = s; while(*s && *s != '\n') s++; if (*s == '\n') { - char *t = ++s; + const char *t = ++s; while (*s) { if (*s == '\n') @@ -4770,39 +6104,47 @@ Perl_regprop(pTHX_ SV *sv, regnode *o) SV * Perl_re_intuit_string(pTHX_ regexp *prog) { /* Assume that RE_INTUIT is set */ - DEBUG_r( + GET_RE_DEBUG_FLAGS_DECL; + DEBUG_COMPILE_r( { STRLEN n_a; - char *s = SvPV(prog->check_substr,n_a); + const char *s = SvPV(prog->check_substr + ? prog->check_substr : prog->check_utf8, n_a); if (!PL_colorset) reginitcolors(); PerlIO_printf(Perl_debug_log, - "%sUsing REx substr:%s `%s%.60s%s%s'\n", - PL_colors[4],PL_colors[5],PL_colors[0], + "%sUsing REx %ssubstr:%s \"%s%.60s%s%s\"\n", + PL_colors[4], + prog->check_substr ? "" : "utf8 ", + PL_colors[5],PL_colors[0], s, PL_colors[1], (strlen(s) > 60 ? "..." : "")); } ); - return prog->check_substr; + return prog->check_substr ? prog->check_substr : prog->check_utf8; } void Perl_pregfree(pTHX_ struct regexp *r) { + dVAR; #ifdef DEBUGGING SV *dsv = PERL_DEBUG_PAD_ZERO(0); + SV *re_debug_flags=get_sv(RE_DEBUG_FLAGS,0); #endif + if (!r || (--r->refcnt > 0)) return; - DEBUG_r({ - char *s = pv_uni_display(dsv, (U8*)r->precomp, r->prelen, 60, - UNI_DISPLAY_REGEX); - int len = SvCUR(dsv); + DEBUG_r(if (re_debug_flags && (SvIV(re_debug_flags) & RE_DEBUG_COMPILE)) { + const char *s = (r->reganch & ROPT_UTF8) + ? pv_uni_display(dsv, (U8*)r->precomp, r->prelen, 60, UNI_DISPLAY_REGEX) + : pv_display(dsv, r->precomp, r->prelen, 0, 60); + const int len = SvCUR(dsv); if (!PL_colorset) reginitcolors(); PerlIO_printf(Perl_debug_log, - "%sFreeing REx:%s `%s%*.*s%s%s'\n", + "%sFreeing REx:%s %s%*.*s%s%s\n", PL_colors[4],PL_colors[5],PL_colors[0], len, len, s, PL_colors[1], @@ -4813,20 +6155,27 @@ Perl_pregfree(pTHX_ struct regexp *r) Safefree(r->precomp); if (r->offsets) /* 20010421 MJD */ Safefree(r->offsets); - if (RX_MATCH_COPIED(r)) - Safefree(r->subbeg); + RX_MATCH_COPY_FREE(r); +#ifdef PERL_COPY_ON_WRITE + if (r->saved_copy) + SvREFCNT_dec(r->saved_copy); +#endif if (r->substrs) { if (r->anchored_substr) SvREFCNT_dec(r->anchored_substr); + if (r->anchored_utf8) + SvREFCNT_dec(r->anchored_utf8); if (r->float_substr) SvREFCNT_dec(r->float_substr); + if (r->float_utf8) + SvREFCNT_dec(r->float_utf8); Safefree(r->substrs); } if (r->data) { int n = r->data->count; - AV* new_comppad = NULL; - AV* old_comppad; - SV** old_curpad; + PAD* new_comppad = NULL; + PAD* old_comppad; + PADOFFSET refcnt; while (--n >= 0) { /* If you add a ->what type here, update the comment in regcomp.h */ @@ -4843,27 +6192,49 @@ Perl_pregfree(pTHX_ struct regexp *r) case 'o': if (new_comppad == NULL) Perl_croak(aTHX_ "panic: pregfree comppad"); - old_comppad = PL_comppad; - old_curpad = PL_curpad; - /* Watch out for global destruction's random ordering. */ - if (SvTYPE(new_comppad) == SVt_PVAV) { - PL_comppad = new_comppad; - PL_curpad = AvARRAY(new_comppad); - } - else - PL_curpad = NULL; - - if (!OpREFCNT_dec((OP_4tree*)r->data->data[n])) { + PAD_SAVE_LOCAL(old_comppad, + /* Watch out for global destruction's random ordering. */ + (SvTYPE(new_comppad) == SVt_PVAV) ? + new_comppad : Null(PAD *) + ); + OP_REFCNT_LOCK; + refcnt = OpREFCNT_dec((OP_4tree*)r->data->data[n]); + OP_REFCNT_UNLOCK; + if (!refcnt) op_free((OP_4tree*)r->data->data[n]); - } - PL_comppad = old_comppad; - PL_curpad = old_curpad; + PAD_RESTORE_LOCAL(old_comppad); SvREFCNT_dec((SV*)new_comppad); new_comppad = NULL; break; case 'n': break; + case 't': + { + reg_trie_data *trie=(reg_trie_data*)r->data->data[n]; + U32 refcount; + OP_REFCNT_LOCK; + refcount = trie->refcount--; + OP_REFCNT_UNLOCK; + if ( !refcount ) { + if (trie->charmap) + Safefree(trie->charmap); + if (trie->widecharmap) + SvREFCNT_dec((SV*)trie->widecharmap); + if (trie->states) + Safefree(trie->states); + if (trie->trans) + Safefree(trie->trans); +#ifdef DEBUGGING + if (trie->words) + SvREFCNT_dec((SV*)trie->words); + if (trie->revcharmap) + SvREFCNT_dec((SV*)trie->revcharmap); +#endif + Safefree(r->data->data[n]); /* do this last!!!! */ + } + break; + } default: Perl_croak(aTHX_ "panic: regfree data code '%c'", r->data->what[n]); } @@ -4878,9 +6249,6 @@ Perl_pregfree(pTHX_ struct regexp *r) /* - regnext - dig the "next" pointer out of a node - * - * [Note, when REGALIGN is defined there are two places in regmatch() - * that bypass this code for speed.] */ regnode * Perl_regnext(pTHX_ register regnode *p) @@ -4905,7 +6273,7 @@ S_re_croak2(pTHX_ const char* pat1,const char* pat2,...) STRLEN l2 = strlen(pat2); char buf[512]; SV *msv; - char *message; + const char *message; if (l1 > 510) l1 = 510; @@ -4927,7 +6295,7 @@ S_re_croak2(pTHX_ const char* pat1,const char* pat2,...) if (l1 > 512) l1 = 512; Copy(message, buf, l1 , char); - buf[l1] = '\0'; /* Overwrite \n */ + buf[l1-1] = '\0'; /* Overwrite \n */ Perl_croak(aTHX_ "%s", buf); } @@ -4936,20 +6304,6 @@ S_re_croak2(pTHX_ const char* pat1,const char* pat2,...) void Perl_save_re_context(pTHX) { -#if 0 - SAVEPPTR(RExC_precomp); /* uncompiled string. */ - SAVEI32(RExC_npar); /* () count. */ - SAVEI32(RExC_size); /* Code size. */ - SAVEI16(RExC_flags16); /* are we folding, multilining? */ - SAVEVPTR(RExC_rx); /* from regcomp.c */ - SAVEI32(RExC_seen); /* from regcomp.c */ - SAVEI32(RExC_sawback); /* Did we see \1, ...? */ - SAVEI32(RExC_naughty); /* How bad is this pattern? */ - SAVEVPTR(RExC_emit); /* Code-emit pointer; ®dummy = don't */ - SAVEPPTR(RExC_end); /* End of input for compile */ - SAVEPPTR(RExC_parse); /* Input-scan pointer. */ -#endif - SAVEI32(PL_reg_flags); /* from regexec.c */ SAVEPPTR(PL_bostr); SAVEPPTR(PL_reginput); /* String-input pointer. */ @@ -4958,6 +6312,7 @@ Perl_save_re_context(pTHX) SAVEVPTR(PL_regstartp); /* Pointer to startp array. */ SAVEVPTR(PL_regendp); /* Ditto for endp. */ SAVEVPTR(PL_reglastparen); /* Similarly for lastparen. */ + SAVEVPTR(PL_reglastcloseparen); /* Similarly for lastcloseparen. */ SAVEPPTR(PL_regtill); /* How far we are required to go. */ SAVEGENERICPV(PL_reg_start_tmp); /* from regexec.c */ PL_reg_start_tmp = 0; @@ -4974,13 +6329,47 @@ Perl_save_re_context(pTHX) SAVEVPTR(PL_reg_re); /* from regexec.c */ SAVEPPTR(PL_reg_ganch); /* from regexec.c */ SAVESPTR(PL_reg_sv); /* from regexec.c */ - SAVEI8(PL_reg_match_utf8); /* from regexec.c */ + SAVEBOOL(PL_reg_match_utf8); /* from regexec.c */ SAVEVPTR(PL_reg_magic); /* from regexec.c */ SAVEI32(PL_reg_oldpos); /* from regexec.c */ SAVEVPTR(PL_reg_oldcurpm); /* from regexec.c */ SAVEVPTR(PL_reg_curpm); /* from regexec.c */ + SAVEPPTR(PL_reg_oldsaved); /* old saved substr during match */ + PL_reg_oldsaved = Nullch; + SAVEI32(PL_reg_oldsavedlen); /* old length of saved substr during match */ + PL_reg_oldsavedlen = 0; +#ifdef PERL_COPY_ON_WRITE + SAVESPTR(PL_nrs); + PL_nrs = Nullsv; +#endif + SAVEI32(PL_reg_maxiter); /* max wait until caching pos */ + PL_reg_maxiter = 0; + SAVEI32(PL_reg_leftiter); /* wait until caching pos */ + PL_reg_leftiter = 0; + SAVEGENERICPV(PL_reg_poscache); /* cache of pos of WHILEM */ + PL_reg_poscache = Nullch; + SAVEI32(PL_reg_poscache_size); /* size of pos cache of WHILEM */ + PL_reg_poscache_size = 0; + SAVEPPTR(PL_regprecomp); /* uncompiled string. */ SAVEI32(PL_regnpar); /* () count. */ SAVEI32(PL_regsize); /* from regexec.c */ + + { + /* Save $1..$n (#18107: UTF-8 s/(\w+)/uc($1)/e); AMS 20021106. */ + REGEXP *rx; + + if (PL_curpm && (rx = PM_GETRE(PL_curpm))) { + U32 i; + for (i = 1; i <= rx->nparens; i++) { + GV *mgv; + char digits[TYPE_CHARS(long)]; + sprintf(digits, "%lu", (long)i); + if ((mgv = gv_fetchpv(digits, FALSE, SVt_PV))) + save_scalar(mgv); + } + } + } + #ifdef DEBUGGING SAVEPPTR(PL_reg_starttry); /* from regexec.c */ #endif @@ -4992,3 +6381,12 @@ clear_re(pTHX_ void *r) ReREFCNT_dec((regexp *)r); } +/* + * Local variables: + * c-indentation-style: bsd + * c-basic-offset: 4 + * indent-tabs-mode: t + * End: + * + * ex: set ts=8 sts=4 sw=4 noet: + */