/* whether trie related optimizations are enabled */
#if PERL_ENABLE_EXTENDED_TRIE_OPTIMISATION
#define TRIE_STUDY_OPT
+#define FULL_TRIE_STUDY
#define TRIE_STCLASS
#endif
-/* Length of a variant. */
+
+
+/* About scan_data_t.
+
+ During optimisation we recurse through the regexp program performing
+ various inplace (keyhole style) optimisations. In addition study_chunk
+ and scan_commit populate this data structure with information about
+ what strings MUST appear in the pattern. We look for the longest
+ string that must appear for at a fixed location, and we look for the
+ longest string that may appear at a floating location. So for instance
+ in the pattern:
+
+ /FOO[xX]A.*B[xX]BAR/
+
+ Both 'FOO' and 'A' are fixed strings. Both 'B' and 'BAR' are floating
+ strings (because they follow a .* construct). study_chunk will identify
+ both FOO and BAR as being the longest fixed and floating strings respectively.
+
+ The strings can be composites, for instance
+
+ /(f)(o)(o)/
+
+ will result in a composite fixed substring 'foo'.
+
+ For each string some basic information is maintained:
+
+ - offset or min_offset
+ This is the position the string must appear at, or not before.
+ It also implicitly (when combined with minlenp) tells us how many
+ character must match before the string we are searching.
+ Likewise when combined with minlenp and the length of the string
+ tells us how many characters must appear after the string we have
+ found.
+
+ - max_offset
+ Only used for floating strings. This is the rightmost point that
+ the string can appear at. Ifset to I32 max it indicates that the
+ string can occur infinitely far to the right.
+
+ - minlenp
+ A pointer to the minimum length of the pattern that the string
+ was found inside. This is important as in the case of positive
+ lookahead or positive lookbehind we can have multiple patterns
+ involved. Consider
+
+ /(?=FOO).*F/
+
+ The minimum length of the pattern overall is 3, the minimum length
+ of the lookahead part is 3, but the minimum length of the part that
+ will actually match is 1. So 'FOO's minimum length is 3, but the
+ minimum length for the F is 1. This is important as the minimum length
+ is used to determine offsets in front of and behind the string being
+ looked for. Since strings can be composites this is the length of the
+ pattern at the time it was commited with a scan_commit. Note that
+ the length is calculated by study_chunk, so that the minimum lengths
+ are not known until the full pattern has been compiled, thus the
+ pointer to the value.
+
+ - lookbehind
+
+ In the case of lookbehind the string being searched for can be
+ offset past the start point of the final matching string.
+ If this value was just blithely removed from the min_offset it would
+ invalidate some of the calculations for how many chars must match
+ before or after (as they are derived from min_offset and minlen and
+ the length of the string being searched for).
+ When the final pattern is compiled and the data is moved from the
+ scan_data_t structure into the regexp structure the information
+ about lookbehind is factored in, with the information that would
+ have been lost precalculated in the end_shift field for the
+ associated string.
+
+ The fields pos_min and pos_delta are used to store the minimum offset
+ and the delta to the maximum offset at the current point in the pattern.
+
+*/
typedef struct scan_data_t {
- I32 len_min;
- I32 len_delta;
+ /*I32 len_min; unused */
+ /*I32 len_delta; unused */
I32 pos_min;
I32 pos_delta;
SV *last_found;
- I32 last_end; /* min value, <0 unless valid. */
+ I32 last_end; /* min value, <0 unless valid. */
I32 last_start_min;
I32 last_start_max;
- SV **longest; /* Either &l_fixed, or &l_float. */
- SV *longest_fixed;
- I32 offset_fixed;
- SV *longest_float;
- I32 offset_float_min;
- I32 offset_float_max;
+ SV **longest; /* Either &l_fixed, or &l_float. */
+ SV *longest_fixed; /* longest fixed string found in pattern */
+ I32 offset_fixed; /* offset where it starts */
+ I32 *minlen_fixed; /* pointer to the minlen relevent to the string */
+ I32 lookbehind_fixed; /* is the position of the string modfied by LB */
+ SV *longest_float; /* longest floating string found in pattern */
+ I32 offset_float_min; /* earliest point in string it can appear */
+ I32 offset_float_max; /* latest point in string it can appear */
+ I32 *minlen_float; /* pointer to the minlen relevent to the string */
+ I32 lookbehind_float; /* is the position of the string modified by LB */
I32 flags;
I32 whilem_c;
I32 *last_closep;
*/
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};
+ { 0, 0, 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 0x0001
#define SCF_DO_STCLASS (SCF_DO_STCLASS_AND|SCF_DO_STCLASS_OR)
#define SCF_WHILEM_VISITED_POS 0x2000
-#define SCF_EXACT_TRIE 0x4000 /* should re study once we are done? */
+#define SCF_TRIE_RESTUDY 0x4000 /* Do restudy? */
+
#define UTF (RExC_utf8 != 0)
#define LOC ((RExC_flags & PMf_LOCALE) != 0)
#define EXPERIMENTAL_INPLACESCAN
#endif
+#define DEBUG_STUDYDATA(data,depth) \
+DEBUG_OPTIMISE_r(if(data){ \
+ PerlIO_printf(Perl_debug_log, \
+ "%*s"/* Len:%"IVdf"/%"IVdf" */" Pos:%"IVdf"/%"IVdf \
+ " Flags: %"IVdf" Whilem_c: %"IVdf" Lcp: %"IVdf" ", \
+ (int)(depth)*2, "", \
+ (IV)((data)->pos_min), \
+ (IV)((data)->pos_delta), \
+ (IV)((data)->flags), \
+ (IV)((data)->whilem_c), \
+ (IV)((data)->last_closep ? *((data)->last_closep) : -1) \
+ ); \
+ if ((data)->last_found) \
+ PerlIO_printf(Perl_debug_log, \
+ "Last:'%s' %"IVdf":%"IVdf"/%"IVdf" %sFixed:'%s' @ %"IVdf \
+ " %sFloat: '%s' @ %"IVdf"/%"IVdf"", \
+ SvPVX_const((data)->last_found), \
+ (IV)((data)->last_end), \
+ (IV)((data)->last_start_min), \
+ (IV)((data)->last_start_max), \
+ ((data)->longest && \
+ (data)->longest==&((data)->longest_fixed)) ? "*" : "", \
+ SvPVX_const((data)->longest_fixed), \
+ (IV)((data)->offset_fixed), \
+ ((data)->longest && \
+ (data)->longest==&((data)->longest_float)) ? "*" : "", \
+ SvPVX_const((data)->longest_float), \
+ (IV)((data)->offset_float_min), \
+ (IV)((data)->offset_float_max) \
+ ); \
+ PerlIO_printf(Perl_debug_log,"\n"); \
+});
+
static void clear_re(pTHX_ void *r);
/* Mark that we cannot extend a found fixed substring at this point.
- Updata the longest found anchored substring and the longest found
+ Update the longest found anchored substring and the longest found
floating substrings if needed. */
STATIC void
-S_scan_commit(pTHX_ const RExC_state_t *pRExC_state, scan_data_t *data)
+S_scan_commit(pTHX_ const RExC_state_t *pRExC_state, scan_data_t *data, I32 *minlenp)
{
const STRLEN l = CHR_SVLEN(data->last_found);
const STRLEN old_l = CHR_SVLEN(*data->longest);
+ GET_RE_DEBUG_FLAGS_DECL;
if ((l >= old_l) && ((l > old_l) || (data->flags & SF_BEFORE_EOL))) {
SvSetMagicSV(*data->longest, data->last_found);
|= ((data->flags & SF_BEFORE_EOL) << SF_FIX_SHIFT_EOL);
else
data->flags &= ~SF_FIX_BEFORE_EOL;
+ data->minlen_fixed=minlenp;
+ data->lookbehind_fixed=0;
}
else {
data->offset_float_min = l ? data->last_start_min : data->pos_min;
|= ((data->flags & SF_BEFORE_EOL) << SF_FL_SHIFT_EOL);
else
data->flags &= ~SF_FL_BEFORE_EOL;
+ data->minlen_float=minlenp;
+ data->lookbehind_float=0;
}
}
SvCUR_set(data->last_found, 0);
}
data->last_end = -1;
data->flags &= ~SF_BEFORE_EOL;
+ DEBUG_STUDYDATA(data,0);
}
/* Can match anything (initialization) */
return 1;
if (!(cl->flags & ANYOF_UNICODE_ALL))
return 0;
- if (!ANYOF_BITMAP_TESTALLSET(cl))
+ if (!ANYOF_BITMAP_TESTALLSET((const void*)cl))
return 0;
return 1;
}
}
}
-/*
-
- make_trie(startbranch,first,last,tail,flags,depth)
- 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)/
- depth : indent depth
-
-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 <ac>(16)
- 8: BRANCH(11)
- 9: EXACT <ad>(16)
- 11: BRANCH(14)
- 12: EXACT <ab>(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]
- <ac>
- <ad>
- <ab>
- 16: SUCCEED(0)
- 17: NOTHING(18)
- 18: END(0)
-
-Cases where tail != last would be like /(?foo|bar)baz/:
-
- 1: BRANCH(4)
- 2: EXACT <foo>(8)
- 4: BRANCH(7)
- 5: EXACT <bar>(8)
- 7: TAIL(8)
- 8: EXACT <baz>(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]
- <foo>
- <bar>
- 7: TAIL(8)
- 8: EXACT <baz>(10)
- 10: END(0)
-
- d = uvuni_to_utf8_flags(d, uv, 0);
-
-is the recommended Unicode-aware way of saying
-
- *(d++) = uv;
-*/
-
-#define TRIE_STORE_REVCHAR \
- STMT_START { \
- SV *tmp = Perl_newSVpvf_nocontext( "%c", (int)uvc ); \
- av_push( TRIE_REVCHARMAP(trie), tmp ); \
- } STMT_END
-
-#define TRIE_READ_CHAR STMT_START { \
- wordlen++; \
- 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 { \
- Newxz( trie->states[ state ].trans.list, \
- 4, reg_trie_trans_le ); \
- TRIE_LIST_CUR( state ) = 1; \
- TRIE_LIST_LEN( state ) = 4; \
-} STMT_END
-
-#define TRIE_HANDLE_WORD(state) STMT_START { \
- if ( !trie->states[ state ].wordnum ) { \
- /* we haven't inserted this word into the structure yet. */ \
- if (trie->wordlen) \
- trie->wordlen[ curword ] = wordlen; \
- trie->states[ state ].wordnum = ++curword; \
- DEBUG_r({ \
- /* store the word for dumping */ \
- SV* tmp; \
- if (OP(noper) != NOTHING) \
- tmp = newSVpvn(STRING(noper), STR_LEN(noper)); \
- else \
- tmp = newSVpvn( "", 0 ); \
- if ( UTF ) SvUTF8_on( tmp ); \
- av_push( trie->words, tmp ); \
- }); \
- } else { \
- NOOP; /* It's a dupe. So ignore it. */ \
- } \
-} STMT_END
#ifdef DEBUGGING
/*
S_dump_trie(pTHX_ const struct _reg_trie_data *trie,U32 depth)
{
U32 state;
+ SV *sv=sv_newmortal();
+ int colwidth= trie->widecharmap ? 6 : 4;
GET_RE_DEBUG_FLAGS_DECL;
+
PerlIO_printf( Perl_debug_log, "%*sChar : %-6s%-6s%-4s ",
(int)depth * 2 + 2,"",
"Match","Base","Ofs" );
for( state = 0 ; state < trie->uniquecharcount ; state++ ) {
SV ** const tmp = av_fetch( trie->revcharmap, state, 0);
if ( tmp ) {
- PerlIO_printf( Perl_debug_log, "%4.4s ", SvPV_nolen_const( *tmp ) );
+ PerlIO_printf( Perl_debug_log, "%*s",
+ colwidth,
+ pv_pretty(sv, SvPV_nolen_const(*tmp), SvCUR(*tmp), colwidth,
+ PL_colors[0], PL_colors[1],
+ (SvUTF8(*tmp) ? PERL_PV_ESCAPE_UNI : 0) |
+ PERL_PV_ESCAPE_FIRSTCHAR
+ )
+ );
}
}
PerlIO_printf( Perl_debug_log, "\n%*sState|-----------------------",
(int)depth * 2 + 2,"");
for( state = 0 ; state < trie->uniquecharcount ; state++ )
- PerlIO_printf( Perl_debug_log, "-----");
+ PerlIO_printf( Perl_debug_log, "%.*s", colwidth, "--------");
PerlIO_printf( Perl_debug_log, "\n");
- for( state = 1 ; state < TRIE_LASTSTATE(trie) ; state++ ) {
+ for( state = 1 ; state < trie->laststate ; state++ ) {
const U32 base = trie->states[ state ].trans.base;
PerlIO_printf( Perl_debug_log, "%*s#%4"UVXf"|", (int)depth * 2 + 2,"", (UV)state);
( base + ofs - trie->uniquecharcount < trie->lasttrans ) &&
trie->trans[ base + ofs - trie->uniquecharcount ].check == state )
{
- PerlIO_printf( Perl_debug_log, "%4"UVXf" ",
+ PerlIO_printf( Perl_debug_log, "%*"UVXf,
+ colwidth,
(UV)trie->trans[ base + ofs - trie->uniquecharcount ].next );
} else {
- PerlIO_printf( Perl_debug_log, "%4s "," ." );
+ PerlIO_printf( Perl_debug_log, "%*s",colwidth," ." );
}
}
S_dump_trie_interim_list(pTHX_ const struct _reg_trie_data *trie, U32 next_alloc,U32 depth)
{
U32 state;
+ SV *sv=sv_newmortal();
+ int colwidth= trie->widecharmap ? 6 : 4;
GET_RE_DEBUG_FLAGS_DECL;
/* print out the table precompression. */
- PerlIO_printf( Perl_debug_log, "%*sState :Word | Transition Data\n%*s",
- (int)depth * 2 + 2,"", (int)depth * 2 + 2,"");
- PerlIO_printf( Perl_debug_log, "------:-----+-----------------" );
+ PerlIO_printf( Perl_debug_log, "%*sState :Word | Transition Data\n%*s%s",
+ (int)depth * 2 + 2,"", (int)depth * 2 + 2,"",
+ "------:-----+-----------------\n" );
for( state=1 ; state < next_alloc ; state ++ ) {
U16 charid;
- PerlIO_printf( Perl_debug_log, "\n%*s %4"UVXf" :",
+ PerlIO_printf( Perl_debug_log, "%*s %4"UVXf" :",
(int)depth * 2 + 2,"", (UV)state );
if ( ! trie->states[ state ].wordnum ) {
PerlIO_printf( Perl_debug_log, "%5s| ","");
}
for( charid = 1 ; charid <= TRIE_LIST_USED( state ) ; charid++ ) {
SV ** const tmp = av_fetch( trie->revcharmap, TRIE_LIST_ITEM(state,charid).forid, 0);
- PerlIO_printf( Perl_debug_log, "%s:%3X=%4"UVXf" | ",
- SvPV_nolen_const( *tmp ),
+ if ( tmp ) {
+ PerlIO_printf( Perl_debug_log, "%*s:%3X=%4"UVXf" | ",
+ colwidth,
+ pv_pretty(sv, SvPV_nolen_const(*tmp), SvCUR(*tmp), colwidth,
+ PL_colors[0], PL_colors[1],
+ (SvUTF8(*tmp) ? PERL_PV_ESCAPE_UNI : 0) |
+ PERL_PV_ESCAPE_FIRSTCHAR
+ ) ,
TRIE_LIST_ITEM(state,charid).forid,
(UV)TRIE_LIST_ITEM(state,charid).newstate
);
}
-
+ }
+ PerlIO_printf( Perl_debug_log, "\n");
}
}
{
U32 state;
U16 charid;
+ SV *sv=sv_newmortal();
+ int colwidth= trie->widecharmap ? 6 : 4;
GET_RE_DEBUG_FLAGS_DECL;
/*
for( charid = 0 ; charid < trie->uniquecharcount ; charid++ ) {
SV ** const tmp = av_fetch( trie->revcharmap, charid, 0);
if ( tmp ) {
- PerlIO_printf( Perl_debug_log, "%4.4s ", SvPV_nolen_const( *tmp ) );
+ PerlIO_printf( Perl_debug_log, "%*s",
+ colwidth,
+ pv_pretty(sv, SvPV_nolen_const(*tmp), SvCUR(*tmp), colwidth,
+ PL_colors[0], PL_colors[1],
+ (SvUTF8(*tmp) ? PERL_PV_ESCAPE_UNI : 0) |
+ PERL_PV_ESCAPE_FIRSTCHAR
+ )
+ );
}
}
PerlIO_printf( Perl_debug_log, "\n%*sState+-",(int)depth * 2 + 2,"" );
for( charid=0 ; charid < trie->uniquecharcount ; charid++ ) {
- PerlIO_printf( Perl_debug_log, "%4s-", "----" );
+ PerlIO_printf( Perl_debug_log, "%.*s", colwidth,"--------");
}
PerlIO_printf( Perl_debug_log, "\n" );
(UV)TRIE_NODENUM( state ) );
for( charid = 0 ; charid < trie->uniquecharcount ; charid++ ) {
- PerlIO_printf( Perl_debug_log, "%4"UVXf" ",
- (UV)SAFE_TRIE_NODENUM( trie->trans[ state + charid ].next ) );
+ UV v=(UV)SAFE_TRIE_NODENUM( trie->trans[ state + charid ].next );
+ if (v)
+ PerlIO_printf( Perl_debug_log, "%*"UVXf, colwidth, v );
+ else
+ PerlIO_printf( Perl_debug_log, "%*s", colwidth, "." );
}
if ( ! trie->states[ TRIE_NODENUM( state ) ].wordnum ) {
PerlIO_printf( Perl_debug_log, " (%4"UVXf")\n", (UV)trie->trans[ state ].check );
#endif
-#define TRIE_TRANS_STATE(state,base,ucharcount,charid,special) \
- ( ( base + charid >= ucharcount \
- && base + charid < ubound \
- && state == trie->trans[ base - ucharcount + charid ].check \
- && trie->trans[ base - ucharcount + charid ].next ) \
- ? trie->trans[ base - ucharcount + charid ].next \
- : ( state==1 ? special : 0 ) \
- )
-
-STATIC void
-S_make_trie_failtable(pTHX_ RExC_state_t *pRExC_state, regnode *source, regnode *stclass, U32 depth)
-{
-/* The Trie is constructed and compressed now so we can build a fail array now if its needed
+/* make_trie(startbranch,first,last,tail,word_count,flags,depth)
+ 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
+ count : words in the sequence
+ flags : currently the OP() type we will be building one of /EXACT(|F|Fl)/
+ depth : indent depth
- This is apparently the Aho-Corasick algorithm. Its from exercise 3.31 and 3.32 in the
- "Red Dragon" -- Compilers, principles, techniques, and tools. Aho, Sethi, Ullman 1985/88
- ISBN 0-201-10088-6
+Inplace optimizes a sequence of 2 or more Branch-Exact nodes into a TRIE node.
- We find the fail state for each state in the trie, this state is the longest proper
- suffix of the current states 'word' that is also a proper prefix of another word in our
- trie. State 1 represents the word '' and is the thus the default fail state. This allows
- the DFA not to have to restart after its tried and failed a word at a given point, it
- simply continues as though it had been matching the other word in the first place.
- Consider
- 'abcdgu'=~/abcdefg|cdgu/
- When we get to 'd' we are still matching the first word, we would encounter 'g' which would
- fail, which would bring use to the state representing 'd' in the second word where we would
- try 'g' and succeed, prodceding to match 'cdgu'.
- */
- /* add a fail transition */
- reg_trie_data *trie=(reg_trie_data *)RExC_rx->data->data[ARG(source)];
- U32 *q;
- const U32 ucharcount = trie->uniquecharcount;
- const U32 numstates = trie->laststate;
- const U32 ubound = trie->lasttrans + ucharcount;
- U32 q_read = 0;
- U32 q_write = 0;
- U32 charid;
- U32 base = trie->states[ 1 ].trans.base;
- U32 *fail;
- reg_ac_data *aho;
- const U32 data_slot = add_data( pRExC_state, 1, "T" );
- GET_RE_DEBUG_FLAGS_DECL;
-#ifndef DEBUGGING
- PERL_UNUSED_ARG(depth);
-#endif
+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/
- ARG_SET( stclass, data_slot );
- Newxz( aho, 1, reg_ac_data );
- RExC_rx->data->data[ data_slot ] = (void*)aho;
- aho->trie=trie;
- aho->states=(reg_trie_state *)savepvn((const char*)trie->states,
- (trie->laststate+1)*sizeof(reg_trie_state));
- Newxz( q, numstates, U32);
- Newxz( aho->fail, numstates, U32 );
- aho->refcount = 1;
- fail = aho->fail;
- fail[ 0 ] = fail[ 1 ] = 1;
+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.
- for ( charid = 0; charid < ucharcount ; charid++ ) {
- const U32 newstate = TRIE_TRANS_STATE( 1, base, ucharcount, charid, 0 );
- if ( newstate ) {
- q[ q_write ] = newstate;
- /* set to point at the root */
- fail[ q[ q_write++ ] ]=1;
- }
- }
- while ( q_read < q_write) {
- const U32 cur = q[ q_read++ % numstates ];
- base = trie->states[ cur ].trans.base;
+ +-h->+-e->[3]-+-r->(8)-+-s->[9]
+ | |
+ | (2)
+ | |
+ (1) +-i->(6)-+-s->[7]
+ |
+ +-s->(3)-+-h->(4)-+-e->[5]
- for ( charid = 0 ; charid < ucharcount ; charid++ ) {
- const U32 ch_state = TRIE_TRANS_STATE( cur, base, ucharcount, charid, 1 );
- if (ch_state) {
- U32 fail_state = cur;
- U32 fail_base;
- do {
- fail_state = fail[ fail_state ];
- fail_base = aho->states[ fail_state ].trans.base;
- } while ( !TRIE_TRANS_STATE( fail_state, fail_base, ucharcount, charid, 1 ) );
+ Accept Word Mapping: 3=>1 (he),5=>2 (she), 7=>3 (his), 9=>4 (hers)
- fail_state = TRIE_TRANS_STATE( fail_state, fail_base, ucharcount, charid, 1 );
- fail[ ch_state ] = fail_state;
- if ( !aho->states[ ch_state ].wordnum && aho->states[ fail_state ].wordnum )
- {
- aho->states[ ch_state ].wordnum = aho->states[ fail_state ].wordnum;
- }
- q[ q_write++ % numstates] = ch_state;
- }
- }
- }
+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.
- DEBUG_TRIE_COMPILE_MORE_r({
- PerlIO_printf(Perl_debug_log, "%*sFail: 1", (int)(depth * 2), "");
- for( q_read=2; q_read<numstates; q_read++ ) {
- PerlIO_printf(Perl_debug_log, ", %"UVuf, fail[q_read]);
- }
- PerlIO_printf(Perl_debug_log, "\n");
- });
- Safefree(q);
- /*RExC_seen |= REG_SEEN_TRIEDFA;*/
-}
+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 <ac>(16)
+ 8: BRANCH(11)
+ 9: EXACT <ad>(16)
+ 11: BRANCH(14)
+ 12: EXACT <ab>(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]
+ <ac>
+ <ad>
+ <ab>
+ 16: SUCCEED(0)
+ 17: NOTHING(18)
+ 18: END(0)
+
+Cases where tail != last would be like /(?foo|bar)baz/:
+
+ 1: BRANCH(4)
+ 2: EXACT <foo>(8)
+ 4: BRANCH(7)
+ 5: EXACT <bar>(8)
+ 7: TAIL(8)
+ 8: EXACT <baz>(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]
+ <foo>
+ <bar>
+ 7: TAIL(8)
+ 8: EXACT <baz>(10)
+ 10: END(0)
+
+ d = uvuni_to_utf8_flags(d, uv, 0);
+
+is the recommended Unicode-aware way of saying
+
+ *(d++) = uv;
+*/
+
+#define TRIE_STORE_REVCHAR \
+ STMT_START { \
+ SV *tmp = Perl_newSVpvf_nocontext( "%c", (int)uvc ); \
+ if (UTF) SvUTF8_on(tmp); \
+ av_push( TRIE_REVCHARMAP(trie), tmp ); \
+ } STMT_END
+
+#define TRIE_READ_CHAR STMT_START { \
+ wordlen++; \
+ 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_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 { \
+ Newxz( trie->states[ state ].trans.list, \
+ 4, reg_trie_trans_le ); \
+ TRIE_LIST_CUR( state ) = 1; \
+ TRIE_LIST_LEN( state ) = 4; \
+} STMT_END
+
+#define TRIE_HANDLE_WORD(state) STMT_START { \
+ U16 dupe= trie->states[ state ].wordnum; \
+ regnode * const noper_next = regnext( noper ); \
+ \
+ if (trie->wordlen) \
+ trie->wordlen[ curword ] = wordlen; \
+ DEBUG_r({ \
+ /* store the word for dumping */ \
+ SV* tmp; \
+ if (OP(noper) != NOTHING) \
+ tmp = newSVpvn(STRING(noper), STR_LEN(noper)); \
+ else \
+ tmp = newSVpvn( "", 0 ); \
+ if ( UTF ) SvUTF8_on( tmp ); \
+ av_push( trie->words, tmp ); \
+ }); \
+ \
+ curword++; \
+ \
+ if ( noper_next < tail ) { \
+ if (!trie->jump) \
+ Newxz( trie->jump, word_count + 1, U16); \
+ trie->jump[curword] = (U16)(tail - noper_next); \
+ if (!jumper) \
+ jumper = noper_next; \
+ if (!nextbranch) \
+ nextbranch= regnext(cur); \
+ } \
+ \
+ if ( dupe ) { \
+ /* So it's a dupe. This means we need to maintain a */\
+ /* linked-list from the first to the next. */\
+ /* we only allocate the nextword buffer when there */\
+ /* a dupe, so first time we have to do the allocation */\
+ if (!trie->nextword) \
+ Newxz( trie->nextword, word_count + 1, U16); \
+ while ( trie->nextword[dupe] ) \
+ dupe= trie->nextword[dupe]; \
+ trie->nextword[dupe]= curword; \
+ } else { \
+ /* we haven't inserted this word yet. */ \
+ trie->states[ state ].wordnum = curword; \
+ } \
+} STMT_END
+#define TRIE_TRANS_STATE(state,base,ucharcount,charid,special) \
+ ( ( base + charid >= ucharcount \
+ && base + charid < ubound \
+ && state == trie->trans[ base - ucharcount + charid ].check \
+ && trie->trans[ base - ucharcount + charid ].next ) \
+ ? trie->trans[ base - ucharcount + charid ].next \
+ : ( state==1 ? special : 0 ) \
+ )
+
+#define MADE_TRIE 1
+#define MADE_JUMP_TRIE 2
+#define MADE_EXACT_TRIE 4
+
STATIC I32
-S_make_trie(pTHX_ RExC_state_t *pRExC_state, regnode *startbranch, regnode *first, regnode *last, regnode *tail, U32 flags, U32 depth)
+S_make_trie(pTHX_ RExC_state_t *pRExC_state, regnode *startbranch, regnode *first, regnode *last, regnode *tail, U32 word_count, U32 flags, U32 depth)
{
dVAR;
/* first pass, loop through and scan words */
UV uvc = 0;
U16 curword = 0;
U32 next_alloc = 0;
+ regnode *jumper = NULL;
+ regnode *nextbranch = NULL;
/* we just use folder as a flag in utf8 */
const U8 * const folder = ( flags == EXACTF
? PL_fold
#ifndef DEBUGGING
/* these are only used during construction but are useful during
* debugging so we store them in the struct when debugging.
- * Wordcount is actually superfluous in debugging as we have
- * (AV*)trie->words to use for it, but that's not available when
- * not debugging... We could make the macro use the AV during
- * debugging though...
*/
- U16 trie_wordcount=0;
STRLEN trie_charcount=0;
- /*U32 trie_laststate=0;*/
AV *trie_revcharmap;
#endif
GET_RE_DEBUG_FLAGS_DECL;
Newxz( trie, 1, reg_trie_data );
trie->refcount = 1;
trie->startstate = 1;
+ trie->wordcount = word_count;
RExC_rx->data->data[ data_slot ] = (void*)trie;
Newxz( trie->charmap, 256, U16 );
if (!(UTF && folder))
}
DEBUG_OPTIMISE_r({
PerlIO_printf( Perl_debug_log,
- "%*smake_trie start==%d, first==%d, last==%d, tail==%d\n",
+ "%*smake_trie start==%d, first==%d, last==%d, tail==%d depth=%d\n",
(int)depth * 2 + 2, "",
REG_NODE_NUM(startbranch),REG_NODE_NUM(first),
- REG_NODE_NUM(last), REG_NODE_NUM(tail));
+ REG_NODE_NUM(last), REG_NODE_NUM(tail),
+ (int)depth);
});
/* -- First loop and Setup --
U32 wordlen = 0; /* required init */
STRLEN chars=0;
- TRIE_WORDCOUNT(trie)++;
if (OP(noper) == NOTHING) {
trie->minlen= 0;
continue;
DEBUG_TRIE_COMPILE_r(
PerlIO_printf( Perl_debug_log, "%*sTRIE(%s): W:%d C:%d Uq:%d Min:%d Max:%d\n",
(int)depth * 2 + 2,"",
- ( trie->widecharmap ? "UTF8" : "NATIVE" ), TRIE_WORDCOUNT(trie),
+ ( trie->widecharmap ? "UTF8" : "NATIVE" ), (int)word_count,
(int)TRIE_CHARCOUNT(trie), trie->uniquecharcount,
(int)trie->minlen, (int)trie->maxlen )
);
- Newxz( trie->wordlen, TRIE_WORDCOUNT(trie), U32 );
+ Newxz( trie->wordlen, word_count, U32 );
/*
We now know what we are dealing with in terms of unique chars and
U8 foldbuf[ UTF8_MAXBYTES_CASE + 1 ];
if (OP(noper) != NOTHING) {
- for ( ; uc < e ; uc += len ) {
+ for ( ; uc < e ; uc += len ) {
- TRIE_READ_CHAR;
+ TRIE_READ_CHAR;
- if ( uvc < 256 ) {
- charid = trie->charmap[ uvc ];
- } else {
- SV** const svpp = hv_fetch( trie->widecharmap, (char*)&uvc, sizeof( UV ), 0);
- if ( !svpp ) {
- charid = 0;
+ if ( uvc < 256 ) {
+ charid = trie->charmap[ uvc ];
} else {
- charid=(U16)SvIV( *svpp );
+ SV** const svpp = hv_fetch( trie->widecharmap, (char*)&uvc, sizeof( UV ), 0);
+ if ( !svpp ) {
+ charid = 0;
+ } else {
+ charid=(U16)SvIV( *svpp );
+ }
}
- }
- if ( charid ) {
+ /* charid is now 0 if we dont know the char read, or nonzero if we do */
+ if ( charid ) {
- U16 check;
- U32 newstate = 0;
+ 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;
+ 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 );
}
- 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 */
- }
}
TRIE_HANDLE_WORD(state);
} /* end second pass */
- TRIE_LASTSTATE(trie) = next_alloc;
+ trie->laststate = next_alloc;
Renew( trie->states, next_alloc, reg_trie_state );
/* and now dump it out before we compress it */
U8 foldbuf[ UTF8_MAXBYTES_CASE + 1 ];
if ( OP(noper) != NOTHING ) {
- for ( ; uc < e ; uc += len ) {
+ for ( ; uc < e ; uc += len ) {
- TRIE_READ_CHAR;
+ TRIE_READ_CHAR;
- if ( uvc < 256 ) {
- charid = trie->charmap[ uvc ];
- } else {
- SV* const * const svpp = hv_fetch( trie->widecharmap, (char*)&uvc, sizeof( UV ), 0);
- charid = svpp ? (U16)SvIV(*svpp) : 0;
- }
- if ( charid ) {
- charid--;
- if ( !trie->trans[ state + charid ].next ) {
- trie->trans[ state + charid ].next = next_alloc;
- trie->trans[ state ].check++;
- next_alloc += trie->uniquecharcount;
+ if ( uvc < 256 ) {
+ charid = trie->charmap[ uvc ];
+ } else {
+ SV* const * const svpp = hv_fetch( trie->widecharmap, (char*)&uvc, sizeof( UV ), 0);
+ charid = svpp ? (U16)SvIV(*svpp) : 0;
}
- state = trie->trans[ state + charid ].next;
- } else {
- Perl_croak( aTHX_ "panic! In trie construction, no char mapping for %"IVdf, uvc );
+ 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 */
}
- /* charid is now 0 if we dont know the char read, or nonzero if we do */
- }
}
accept_state = TRIE_NODENUM( state );
TRIE_HANDLE_WORD(accept_state);
even earlier), but the .check field determines if the transition is
valid.
+ XXX - wrong maybe?
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
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.
+ pointer doesnt find one the single transition is appended as normal.
- Once compressed we can Renew/realloc the structures to release the
excess space.
const U32 laststate = TRIE_NODENUM( next_alloc );
U32 state, charid;
U32 pos = 0, zp=0;
- TRIE_LASTSTATE(trie) = laststate;
+ trie->laststate = laststate;
for ( state = 1 ; state < laststate ; state++ ) {
U8 flag = 0;
regnode *convert;
U8 nodetype =(U8)(flags & 0xFF);
char *str=NULL;
+
#ifdef DEBUGGING
+
U32 mjd_offset;
U32 mjd_nodelen;
#endif
DEBUG_OPTIMISE_r(
PerlIO_printf(Perl_debug_log, "%*sMJD offset:%"UVuf" MJD length:%"UVuf"\n",
(int)depth * 2 + 2, "",
- mjd_offset,mjd_nodelen)
+ (UV)mjd_offset, (UV)mjd_nodelen)
);
/* But first we check to see if there is a common prefix we can
split out as an EXACT and put in front of the TRIE node. */
trie->startstate= 1;
- if ( trie->bitmap && !trie->widecharmap ) {
+ if ( trie->bitmap && !trie->widecharmap && !trie->jump ) {
U32 state;
DEBUG_OPTIMISE_r(
PerlIO_printf(Perl_debug_log, "%*sLaststate:%"UVuf"\n",
(int)depth * 2 + 2, "",
- TRIE_LASTSTATE(trie))
+ (UV)trie->laststate)
);
- for ( state = 1 ; state < TRIE_LASTSTATE(trie)-1 ; state++ ) {
+ for ( state = 1 ; state < trie->laststate-1 ; state++ ) {
U32 ofs = 0;
I32 idx = -1;
U32 count = 0;
PerlIO_printf(Perl_debug_log,
"%*sNew Start State=%"UVuf" Class: [",
(int)depth * 2 + 2, "",
- state));
+ (UV)state));
if (idx >= 0) {
SV ** const tmp = av_fetch( TRIE_REVCHARMAP(trie), idx, 0);
const U8 * const ch = (U8*)SvPV_nolen_const( *tmp );
PerlIO_printf( Perl_debug_log,
"%*sPrefix State: %"UVuf" Idx:%"UVuf" Char='%s'\n",
(int)depth * 2 + 2, "",
- state, idx, ch)
+ (UV)state, (UV)idx, ch)
);
if ( state==1 ) {
OP( convert ) = nodetype;
*str++=*ch;
STR_LEN(convert)++;
- } else {
-#ifdef DEBUGGING
- if (state>1)
- DEBUG_OPTIMISE_r(PerlIO_printf( Perl_debug_log,"]\n"));
-#endif
- break;
- }
- }
- if (str) {
- regnode *n = convert+NODE_SZ_STR(convert);
- NEXT_OFF(convert) = NODE_SZ_STR(convert);
- trie->startstate = state;
- trie->minlen -= (state - 1);
- trie->maxlen -= (state - 1);
- DEBUG_r({
- regnode *fix = convert;
- mjd_nodelen++;
- Set_Node_Offset_Length(convert, mjd_offset, state - 1);
- while( ++fix < n ) {
- Set_Node_Offset_Length(fix, 0, 0);
- }
- });
- if (trie->maxlen) {
- convert = n;
- } else {
- NEXT_OFF(convert) = (U16)(tail - convert);
+ } else {
+#ifdef DEBUGGING
+ if (state>1)
+ DEBUG_OPTIMISE_r(PerlIO_printf( Perl_debug_log,"]\n"));
+#endif
+ break;
+ }
+ }
+ if (str) {
+ regnode *n = convert+NODE_SZ_STR(convert);
+ NEXT_OFF(convert) = NODE_SZ_STR(convert);
+ trie->startstate = state;
+ trie->minlen -= (state - 1);
+ trie->maxlen -= (state - 1);
+ DEBUG_r({
+ regnode *fix = convert;
+ mjd_nodelen++;
+ Set_Node_Offset_Length(convert, mjd_offset, state - 1);
+ while( ++fix < n ) {
+ Set_Node_Offset_Length(fix, 0, 0);
+ }
+ });
+ if (trie->maxlen) {
+ convert = n;
+ } else {
+ NEXT_OFF(convert) = (U16)(tail - convert);
+ }
+ }
+ }
+ if ( trie->maxlen ) {
+ NEXT_OFF( convert ) = (U16)(tail - convert);
+ ARG_SET( convert, data_slot );
+ /* Store the offset to the first unabsorbed branch in
+ jump[0], which is otherwise unused by the jump logic.
+ We use this when dumping a trie and during optimisation. */
+ if (trie->jump)
+ trie->jump[0] = (U16)(tail - nextbranch);
+ if (!jumper)
+ jumper = last;
+ /* XXXX */
+ if ( !trie->states[trie->startstate].wordnum && trie->bitmap &&
+ ( (char *)jumper - (char *)convert) >= (int)sizeof(struct regnode_charclass) )
+ {
+ OP( convert ) = TRIEC;
+ Copy(trie->bitmap, ((struct regnode_charclass *)convert)->bitmap, ANYOF_BITMAP_SIZE, char);
+ Safefree(trie->bitmap);
+ trie->bitmap= NULL;
+ } else
+ OP( convert ) = TRIE;
+
+ /* store the type in the flags */
+ convert->flags = nodetype;
+ /* XXX We really should free up the resource in trie now, as we wont use them */
+ }
+ /* needed for dumping*/
+ DEBUG_r({
+ regnode *optimize = convert
+ + NODE_STEP_REGNODE
+ + regarglen[ OP( convert ) ];
+ regnode *opt = convert;
+ while (++opt<optimize) {
+ Set_Node_Offset_Length(opt,0,0);
+ }
+ /*
+ Try to clean up some of the debris left after the
+ optimisation.
+ */
+ while( optimize < jumper ) {
+ mjd_nodelen += Node_Length((optimize));
+ OP( optimize ) = OPTIMIZED;
+ Set_Node_Offset_Length(optimize,0,0);
+ optimize++;
+ }
+ Set_Node_Offset_Length(convert,mjd_offset,mjd_nodelen);
+ });
+ } /* end node insert */
+#ifndef DEBUGGING
+ SvREFCNT_dec(TRIE_REVCHARMAP(trie));
+#endif
+ return trie->jump
+ ? MADE_JUMP_TRIE
+ : trie->startstate>1
+ ? MADE_EXACT_TRIE
+ : MADE_TRIE;
+}
+
+STATIC void
+S_make_trie_failtable(pTHX_ RExC_state_t *pRExC_state, regnode *source, regnode *stclass, U32 depth)
+{
+/* The Trie is constructed and compressed now so we can build a fail array now if its needed
+
+ This is basically the Aho-Corasick algorithm. Its from exercise 3.31 and 3.32 in the
+ "Red Dragon" -- Compilers, principles, techniques, and tools. Aho, Sethi, Ullman 1985/88
+ ISBN 0-201-10088-6
+
+ We find the fail state for each state in the trie, this state is the longest proper
+ suffix of the current states 'word' that is also a proper prefix of another word in our
+ trie. State 1 represents the word '' and is the thus the default fail state. This allows
+ the DFA not to have to restart after its tried and failed a word at a given point, it
+ simply continues as though it had been matching the other word in the first place.
+ Consider
+ 'abcdgu'=~/abcdefg|cdgu/
+ When we get to 'd' we are still matching the first word, we would encounter 'g' which would
+ fail, which would bring use to the state representing 'd' in the second word where we would
+ try 'g' and succeed, prodceding to match 'cdgu'.
+ */
+ /* add a fail transition */
+ reg_trie_data *trie=(reg_trie_data *)RExC_rx->data->data[ARG(source)];
+ U32 *q;
+ const U32 ucharcount = trie->uniquecharcount;
+ const U32 numstates = trie->laststate;
+ const U32 ubound = trie->lasttrans + ucharcount;
+ U32 q_read = 0;
+ U32 q_write = 0;
+ U32 charid;
+ U32 base = trie->states[ 1 ].trans.base;
+ U32 *fail;
+ reg_ac_data *aho;
+ const U32 data_slot = add_data( pRExC_state, 1, "T" );
+ GET_RE_DEBUG_FLAGS_DECL;
+#ifndef DEBUGGING
+ PERL_UNUSED_ARG(depth);
+#endif
+
+
+ ARG_SET( stclass, data_slot );
+ Newxz( aho, 1, reg_ac_data );
+ RExC_rx->data->data[ data_slot ] = (void*)aho;
+ aho->trie=trie;
+ aho->states=(reg_trie_state *)savepvn((const char*)trie->states,
+ (trie->laststate+1)*sizeof(reg_trie_state));
+ Newxz( q, numstates, U32);
+ Newxz( aho->fail, numstates, U32 );
+ aho->refcount = 1;
+ fail = aho->fail;
+ /* initialize fail[0..1] to be 1 so that we always have
+ a valid final fail state */
+ fail[ 0 ] = fail[ 1 ] = 1;
+
+ for ( charid = 0; charid < ucharcount ; charid++ ) {
+ const U32 newstate = TRIE_TRANS_STATE( 1, base, ucharcount, charid, 0 );
+ if ( newstate ) {
+ q[ q_write ] = newstate;
+ /* set to point at the root */
+ fail[ q[ q_write++ ] ]=1;
+ }
+ }
+ while ( q_read < q_write) {
+ const U32 cur = q[ q_read++ % numstates ];
+ base = trie->states[ cur ].trans.base;
+
+ for ( charid = 0 ; charid < ucharcount ; charid++ ) {
+ const U32 ch_state = TRIE_TRANS_STATE( cur, base, ucharcount, charid, 1 );
+ if (ch_state) {
+ U32 fail_state = cur;
+ U32 fail_base;
+ do {
+ fail_state = fail[ fail_state ];
+ fail_base = aho->states[ fail_state ].trans.base;
+ } while ( !TRIE_TRANS_STATE( fail_state, fail_base, ucharcount, charid, 1 ) );
+
+ fail_state = TRIE_TRANS_STATE( fail_state, fail_base, ucharcount, charid, 1 );
+ fail[ ch_state ] = fail_state;
+ if ( !aho->states[ ch_state ].wordnum && aho->states[ fail_state ].wordnum )
+ {
+ aho->states[ ch_state ].wordnum = aho->states[ fail_state ].wordnum;
}
+ q[ q_write++ % numstates] = ch_state;
}
}
- if ( trie->maxlen ) {
- OP( convert ) = TRIE;
- NEXT_OFF( convert ) = (U16)(tail - convert);
- ARG_SET( convert, data_slot );
-
- /* store the type in the flags */
- convert->flags = nodetype;
- /* XXX We really should free up the resource in trie now, as we wont use them */
+ }
+ /* restore fail[0..1] to 0 so that we "fall out" of the AC loop
+ when we fail in state 1, this allows us to use the
+ charclass scan to find a valid start char. This is based on the principle
+ that theres a good chance the string being searched contains lots of stuff
+ that cant be a start char.
+ */
+ fail[ 0 ] = fail[ 1 ] = 0;
+ DEBUG_TRIE_COMPILE_r({
+ PerlIO_printf(Perl_debug_log, "%*sStclass Failtable: 0", (int)(depth * 2), "");
+ for( q_read=1; q_read<numstates; q_read++ ) {
+ PerlIO_printf(Perl_debug_log, ", %"UVuf, (UV)fail[q_read]);
}
- /* needed for dumping*/
- DEBUG_r({
- regnode *optimize = convert + NODE_STEP_REGNODE + regarglen[ TRIE ];
- regnode *opt = convert;
- while (++opt<optimize) {
- Set_Node_Offset_Length(opt,0,0);
- }
- /* 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.
- We also "fix" the offsets
- */
- while( optimize < last ) {
- mjd_nodelen += Node_Length((optimize));
- OP( optimize ) = OPTIMIZED;
- Set_Node_Offset_Length(optimize,0,0);
- optimize++;
- }
- Set_Node_Offset_Length(convert,mjd_offset,mjd_nodelen);
- });
- } /* end node insert */
-#ifndef DEBUGGING
- SvREFCNT_dec(TRIE_REVCHARMAP(trie));
-#endif
- return 1;
+ PerlIO_printf(Perl_debug_log, "\n");
+ });
+ Safefree(q);
+ /*RExC_seen |= REG_SEEN_TRIEDFA;*/
}
+
/*
* 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.
Next ? (REG_NODE_NUM(Next)) : 0 ); \
});
+
+
+
+
#define JOIN_EXACT(scan,min,flags) \
if (PL_regkind[OP(scan)] == EXACT) \
join_exact(pRExC_state,(scan),(min),(flags),NULL,depth+1)
regnode *stop = scan;
GET_RE_DEBUG_FLAGS_DECL;
#else
+ PERL_UNUSED_ARG(depth);
+#endif
+#ifndef EXPERIMENTAL_INPLACESCAN
PERL_UNUSED_ARG(flags);
PERL_UNUSED_ARG(val);
- PERL_UNUSED_ARG(depth);
#endif
DEBUG_PEEP("join",scan,depth);
if (OP(n) == TAIL || n > next)
stringok = 0;
if (PL_regkind[OP(n)] == NOTHING) {
-
DEBUG_PEEP("skip:",n,depth);
NEXT_OFF(scan) += NEXT_OFF(n);
next = n + NODE_STEP_REGNODE;
n = regnext(n);
}
else if (stringok) {
- const int oldl = STR_LEN(scan);
+ const unsigned int oldl = STR_LEN(scan);
regnode * const nnext = regnext(n);
DEBUG_PEEP("merg",n,depth);
if (stopnow) break;
}
-#ifdef EXPERIMENTAL_INPLACESCAN
- if (flags && !NEXT_OFF(n)) {
- DEBUG_PEEP("atch",val,depth);
- if (reg_off_by_arg[OP(n)]) {
- ARG_SET(n, val - n);
- }
- else {
- NEXT_OFF(n) = val - n;
- }
- stopnow=1;
- }
+#ifdef EXPERIMENTAL_INPLACESCAN
+ if (flags && !NEXT_OFF(n)) {
+ DEBUG_PEEP("atch", val, depth);
+ if (reg_off_by_arg[OP(n)]) {
+ ARG_SET(n, val - n);
+ }
+ else {
+ NEXT_OFF(n) = val - n;
+ }
+ stopnow = 1;
+ }
#endif
}
char * const s0 = STRING(scan), *s, *t;
char * const s1 = s0 + STR_LEN(scan) - 1;
char * const s2 = s1 - 4;
+#ifdef EBCDIC /* RD tunifold greek 0390 and 03B0 */
+ const char t0[] = "\xaf\x49\xaf\x42";
+#else
const char t0[] = "\xcc\x88\xcc\x81";
+#endif
const char * const t1 = t0 + 3;
for (s = s0 + 2;
s < s2 && (t = ninstr(s, s1, t0, t1));
s = t + 4) {
+#ifdef EBCDIC
+ if (((U8)t[-1] == 0x68 && (U8)t[-2] == 0xB4) ||
+ ((U8)t[-1] == 0x46 && (U8)t[-2] == 0xB5))
+#else
if (((U8)t[-1] == 0xB9 && (U8)t[-2] == 0xCE) ||
((U8)t[-1] == 0x85 && (U8)t[-2] == 0xCF))
+#endif
*min -= 4;
}
}
STATIC I32
-S_study_chunk(pTHX_ RExC_state_t *pRExC_state, regnode **scanp, I32 *deltap,
+S_study_chunk(pTHX_ RExC_state_t *pRExC_state, regnode **scanp,
+ I32 *minlenp, I32 *deltap,
regnode *last, scan_data_t *data, U32 flags, U32 depth)
/* scanp: Start here (read-write). */
/* deltap: Write maxlen-minlen here. */
scan_data_t data_fake;
struct regnode_charclass_class and_with; /* Valid if flags & SCF_DO_STCLASS_OR */
SV *re_trie_maxbuff = NULL;
+ regnode *first_non_open = scan;
+
GET_RE_DEBUG_FLAGS_DECL;
#ifdef DEBUGGING
StructCopy(&zero_scan_data, &data_fake, scan_data_t);
#endif
+ if ( depth == 0 ) {
+ while (first_non_open && OP(first_non_open) == OPEN)
+ first_non_open=regnext(first_non_open);
+ }
+
while (scan && OP(scan) != END && scan < last) {
/* Peephole optimizer: */
+ DEBUG_STUDYDATA(data,depth);
DEBUG_PEEP("Peep",scan,depth);
-
JOIN_EXACT(scan,&min,0);
/* Follow the next-chain of the current node and optimize
/* demq: the op(next)==code check is to see if we have "branch-branch" AFAICT */
if (OP(next) == code || code == IFTHEN || code == SUSPEND) {
+ /* NOTE - There is similar code to this block below for handling
+ TRIE nodes on a re-study. If you change stuff here check there
+ too. */
I32 max1 = 0, min1 = I32_MAX, num = 0;
struct regnode_charclass_class accum;
regnode * const startbranch=scan;
if (flags & SCF_DO_SUBSTR) /* XXXX Add !SUSPEND? */
- scan_commit(pRExC_state, data); /* Cannot merge strings after this. */
+ scan_commit(pRExC_state, data, minlenp); /* Cannot merge strings after this. */
if (flags & SCF_DO_STCLASS)
cl_init_zero(pRExC_state, &accum);
f |= SCF_WHILEM_VISITED_POS;
/* we suppose the run is continuous, last=next...*/
- minnext = study_chunk(pRExC_state, &scan, &deltanext,
+ minnext = study_chunk(pRExC_state, &scan, minlenp, &deltanext,
next, &data_fake, f,depth+1);
if (min1 > minnext)
min1 = minnext;
}
}
+ if (PERL_ENABLE_TRIE_OPTIMISATION && OP( startbranch ) == BRANCH ) {
/* demq.
Assuming this was/is a branch we are dealing with: 'scan' now
it is. We now start at the beginning of the sequence and look
for subsequences of
- BRANCH->EXACT=>X
- BRANCH->EXACT=>X
+ BRANCH->EXACT=>x1
+ BRANCH->EXACT=>x2
+ tail
which would be constructed from a pattern like /A|LIST|OF|WORDS/
We have two cases
- 1. patterns where the whole set of branch can be converted to a trie,
+ 1. patterns where the whole set of branch can be converted.
- 2. patterns where only a subset of the alternations can be
- converted to a trie.
+ 2. patterns where only a subset can be converted.
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
'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.
+ There is an additional case, that being where there is a
+ common prefix, which gets split out into an EXACT like node
+ preceding the TRIE node.
+
+ If x(1..n)==tail then we can do a simple trie, if not we make
+ a "jump" trie, such that when we match the appropriate word
+ we "jump" to the appopriate tail node. Essentailly we turn
+ a nested if into a case structure of sorts.
*/
- if (PERL_ENABLE_TRIE_OPTIMISATION) {
+
int made=0;
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 ) {
+ if ( SvIV(re_trie_maxbuff)>=0 ) {
regnode *cur;
regnode *first = (regnode *)NULL;
regnode *last = (regnode *)NULL;
if ( (((first && optype!=NOTHING) ? OP( noper ) == optype
: PL_regkind[ OP( noper ) ] == EXACT )
|| OP(noper) == NOTHING )
- && noper_next == tail && count<U16_MAX)
+#ifdef NOJUMPTRIE
+ && noper_next == tail
+#endif
+ && count < U16_MAX)
{
count++;
if ( !first || optype == NOTHING ) {
}
} else {
if ( last ) {
- made+=make_trie( pRExC_state, startbranch, first, cur, tail, optype, depth+1 );
+ make_trie( pRExC_state,
+ startbranch, first, cur, tail, count,
+ optype, depth+1 );
}
if ( PL_regkind[ OP( noper ) ] == EXACT
- && noper_next == tail )
- {
+#ifdef NOJUMPTRIE
+ && noper_next == tail
+#endif
+ ){
count = 1;
first = cur;
optype = OP( noper );
});
if ( last ) {
- made+= make_trie( pRExC_state, startbranch, first, scan, tail, optype, depth+1 );
+ made= make_trie( pRExC_state, startbranch, first, scan, tail, count, optype, depth+1 );
#ifdef TRIE_STUDY_OPT
- if ( made && startbranch == first ) {
- if ( OP(first)!=TRIE )
- flags |= SCF_EXACT_TRIE;
- else {
- regnode *chk=*scanp;
- while ( OP( chk ) == OPEN )
- chk = regnext( chk );
- if (chk==first)
- flags |= SCF_EXACT_TRIE;
- }
- }
+ if ( ((made == MADE_EXACT_TRIE &&
+ startbranch == first)
+ || ( first_non_open == first )) &&
+ depth==0 )
+ flags |= SCF_TRIE_RESTUDY;
#endif
}
}
} /* do trie */
+
}
else if ( code == BRANCHJ ) { /* single branch is optimized. */
scan = NEXTOPER(NEXTOPER(scan));
/* Search for fixed substrings supports EXACT only. */
if (flags & SCF_DO_SUBSTR) {
assert(data);
- scan_commit(pRExC_state, data);
+ scan_commit(pRExC_state, data, minlenp);
}
if (UTF) {
const U8 * const s = (U8 *)STRING(scan);
}
flags &= ~SCF_DO_STCLASS;
}
-#ifdef TRIE_STUDY_OPT
- else if (OP(scan) == TRIE) {
- reg_trie_data *trie=RExC_rx->data->data[ ARG(scan) ];
- min += trie->minlen;
- delta += (trie->maxlen - trie->minlen);
- flags &= ~SCF_DO_STCLASS; /* xxx */
- if (flags & SCF_DO_SUBSTR) {
- scan_commit(pRExC_state,data); /* Cannot expect anything... */
- data->pos_min += trie->minlen;
- data->pos_delta += (trie->maxlen - trie->minlen);
- if (trie->maxlen != trie->minlen)
- data->longest = &(data->longest_float);
- }
- }
-#endif
else if (strchr((const char*)PL_varies,OP(scan))) {
I32 mincount, maxcount, minnext, deltanext, fl = 0;
I32 f = flags, pos_before = 0;
is_inf = is_inf_internal = 1;
scan = regnext(scan);
if (flags & SCF_DO_SUBSTR) {
- scan_commit(pRExC_state, data); /* Cannot extend fixed substrings */
+ scan_commit(pRExC_state, data, minlenp); /* Cannot extend fixed substrings */
data->longest = &(data->longest_float);
}
goto optimize_curly_tail;
next = regnext(scan);
if (OP(scan) == CURLYX) {
I32 lp = (data ? *(data->last_closep) : 0);
- scan->flags = ((lp <= U8_MAX) ? (U8)lp : U8_MAX);
+ scan->flags = ((lp <= (I32)U8_MAX) ? (U8)lp : U8_MAX);
}
scan = NEXTOPER(scan) + EXTRA_STEP_2ARGS;
next_is_eval = (OP(scan) == EVAL);
do_curly:
if (flags & SCF_DO_SUBSTR) {
- if (mincount == 0) scan_commit(pRExC_state,data); /* Cannot extend fixed substrings */
+ if (mincount == 0) scan_commit(pRExC_state,data,minlenp); /* Cannot extend fixed substrings */
pos_before = data->pos_min;
}
if (data) {
f &= ~SCF_WHILEM_VISITED_POS;
/* This will finish on WHILEM, setting scan, or on NULL: */
- minnext = study_chunk(pRExC_state, &scan, &deltanext, last, data,
+ minnext = study_chunk(pRExC_state, &scan, minlenp, &deltanext, last, data,
(mincount == 0
? (f & ~SCF_DO_SUBSTR) : f),depth+1);
}
#endif
/* Optimize again: */
- study_chunk(pRExC_state, &nxt1, &deltanext, nxt,
+ study_chunk(pRExC_state, &nxt1, minlenp, &deltanext, nxt,
NULL, 0,depth+1);
}
else
if (mincount != maxcount) {
/* Cannot extend fixed substrings found inside
the group. */
- scan_commit(pRExC_state,data);
+ scan_commit(pRExC_state,data,minlenp);
if (mincount && last_str) {
SV * const sv = data->last_found;
MAGIC * const mg = SvUTF8(sv) && SvMAGICAL(sv) ?
continue;
default: /* REF and CLUMP only? */
if (flags & SCF_DO_SUBSTR) {
- scan_commit(pRExC_state,data); /* Cannot expect anything... */
+ scan_commit(pRExC_state,data,minlenp); /* Cannot expect anything... */
data->longest = &(data->longest_float);
}
is_inf = is_inf_internal = 1;
int value = 0;
if (flags & SCF_DO_SUBSTR) {
- scan_commit(pRExC_state,data);
+ scan_commit(pRExC_state,data,minlenp);
data->pos_min++;
}
min++;
/* Lookbehind, or need to calculate parens/evals/stclass: */
&& (scan->flags || data || (flags & SCF_DO_STCLASS))
&& (OP(scan) == IFMATCH || OP(scan) == UNLESSM)) {
- /* Lookahead/lookbehind */
- I32 deltanext, minnext, fake = 0;
- regnode *nscan;
- struct regnode_charclass_class intrnl;
- int f = 0;
-
- data_fake.flags = 0;
- if (data) {
- data_fake.whilem_c = data->whilem_c;
- data_fake.last_closep = data->last_closep;
- }
- else
- data_fake.last_closep = &fake;
- if ( flags & SCF_DO_STCLASS && !scan->flags
- && OP(scan) == IFMATCH ) { /* Lookahead */
- cl_init(pRExC_state, &intrnl);
- data_fake.start_class = &intrnl;
- f |= SCF_DO_STCLASS_AND;
- }
- if (flags & SCF_WHILEM_VISITED_POS)
- f |= SCF_WHILEM_VISITED_POS;
- next = regnext(scan);
- nscan = NEXTOPER(NEXTOPER(scan));
- minnext = study_chunk(pRExC_state, &nscan, &deltanext, last, &data_fake, f,depth+1);
- if (scan->flags) {
- if (deltanext) {
- vFAIL("Variable length lookbehind not implemented");
+ if ( !PERL_ENABLE_POSITIVE_ASSERTION_STUDY
+ || OP(scan) == UNLESSM )
+ {
+ /* Negative Lookahead/lookbehind
+ In this case we can't do fixed string optimisation.
+ */
+
+ I32 deltanext, minnext, fake = 0;
+ regnode *nscan;
+ struct regnode_charclass_class intrnl;
+ int f = 0;
+
+ data_fake.flags = 0;
+ if (data) {
+ data_fake.whilem_c = data->whilem_c;
+ data_fake.last_closep = data->last_closep;
}
- else if (minnext > U8_MAX) {
- vFAIL2("Lookbehind longer than %"UVuf" not implemented", (UV)U8_MAX);
+ else
+ data_fake.last_closep = &fake;
+ if ( flags & SCF_DO_STCLASS && !scan->flags
+ && OP(scan) == IFMATCH ) { /* Lookahead */
+ cl_init(pRExC_state, &intrnl);
+ data_fake.start_class = &intrnl;
+ f |= SCF_DO_STCLASS_AND;
}
- scan->flags = (U8)minnext;
- }
- if (data) {
- if (data_fake.flags & (SF_HAS_PAR|SF_IN_PAR))
- pars++;
- if (data_fake.flags & SF_HAS_EVAL)
- data->flags |= SF_HAS_EVAL;
- data->whilem_c = data_fake.whilem_c;
+ if (flags & SCF_WHILEM_VISITED_POS)
+ f |= SCF_WHILEM_VISITED_POS;
+ next = regnext(scan);
+ nscan = NEXTOPER(NEXTOPER(scan));
+ minnext = study_chunk(pRExC_state, &nscan, minlenp, &deltanext, last, &data_fake, f,depth+1);
+ if (scan->flags) {
+ if (deltanext) {
+ vFAIL("Variable length lookbehind not implemented");
+ }
+ else if (minnext > (I32)U8_MAX) {
+ vFAIL2("Lookbehind longer than %"UVuf" not implemented", (UV)U8_MAX);
+ }
+ scan->flags = (U8)minnext;
+ }
+ if (data) {
+ if (data_fake.flags & (SF_HAS_PAR|SF_IN_PAR))
+ pars++;
+ if (data_fake.flags & SF_HAS_EVAL)
+ data->flags |= SF_HAS_EVAL;
+ data->whilem_c = data_fake.whilem_c;
+ }
+ if (f & SCF_DO_STCLASS_AND) {
+ const int was = (data->start_class->flags & ANYOF_EOS);
+
+ cl_and(data->start_class, &intrnl);
+ if (was)
+ data->start_class->flags |= ANYOF_EOS;
+ }
}
- if (f & SCF_DO_STCLASS_AND) {
- const int was = (data->start_class->flags & ANYOF_EOS);
+#if PERL_ENABLE_POSITIVE_ASSERTION_STUDY
+ else {
+ /* Positive Lookahead/lookbehind
+ In this case we can do fixed string optimisation,
+ but we must be careful about it. Note in the case of
+ lookbehind the positions will be offset by the minimum
+ length of the pattern, something we won't know about
+ until after the recurse.
+ */
+ I32 deltanext, fake = 0;
+ regnode *nscan;
+ struct regnode_charclass_class intrnl;
+ int f = 0;
+ /* We use SAVEFREEPV so that when the full compile
+ is finished perl will clean up the allocated
+ minlens when its all done. This was we don't
+ have to worry about freeing them when we know
+ they wont be used, which would be a pain.
+ */
+ I32 *minnextp;
+ Newx( minnextp, 1, I32 );
+ SAVEFREEPV(minnextp);
+
+ if (data) {
+ StructCopy(data, &data_fake, scan_data_t);
+ if ((flags & SCF_DO_SUBSTR) && data->last_found) {
+ f |= SCF_DO_SUBSTR;
+ if (scan->flags)
+ scan_commit(pRExC_state, &data_fake,minlenp);
+ data_fake.last_found=newSVsv(data->last_found);
+ }
+ }
+ else
+ data_fake.last_closep = &fake;
+ data_fake.flags = 0;
+ if (is_inf)
+ data_fake.flags |= SF_IS_INF;
+ if ( flags & SCF_DO_STCLASS && !scan->flags
+ && OP(scan) == IFMATCH ) { /* Lookahead */
+ cl_init(pRExC_state, &intrnl);
+ data_fake.start_class = &intrnl;
+ f |= SCF_DO_STCLASS_AND;
+ }
+ if (flags & SCF_WHILEM_VISITED_POS)
+ f |= SCF_WHILEM_VISITED_POS;
+ next = regnext(scan);
+ nscan = NEXTOPER(NEXTOPER(scan));
+
+ *minnextp = study_chunk(pRExC_state, &nscan, minnextp, &deltanext, last, &data_fake, f,depth+1);
+ if (scan->flags) {
+ if (deltanext) {
+ vFAIL("Variable length lookbehind not implemented");
+ }
+ else if (*minnextp > (I32)U8_MAX) {
+ vFAIL2("Lookbehind longer than %"UVuf" not implemented", (UV)U8_MAX);
+ }
+ scan->flags = (U8)*minnextp;
+ }
+
+ *minnextp += min;
+
+
+ if (f & SCF_DO_STCLASS_AND) {
+ const int was = (data->start_class->flags & ANYOF_EOS);
+
+ cl_and(data->start_class, &intrnl);
+ if (was)
+ data->start_class->flags |= ANYOF_EOS;
+ }
+ if (data) {
+ if (data_fake.flags & (SF_HAS_PAR|SF_IN_PAR))
+ pars++;
+ if (data_fake.flags & SF_HAS_EVAL)
+ data->flags |= SF_HAS_EVAL;
+ data->whilem_c = data_fake.whilem_c;
+ if ((flags & SCF_DO_SUBSTR) && data_fake.last_found) {
+ if (RExC_rx->minlen<*minnextp)
+ RExC_rx->minlen=*minnextp;
+ scan_commit(pRExC_state, &data_fake, minnextp);
+ SvREFCNT_dec(data_fake.last_found);
+
+ if ( data_fake.minlen_fixed != minlenp )
+ {
+ data->offset_fixed= data_fake.offset_fixed;
+ data->minlen_fixed= data_fake.minlen_fixed;
+ data->lookbehind_fixed+= scan->flags;
+ }
+ if ( data_fake.minlen_float != minlenp )
+ {
+ data->minlen_float= data_fake.minlen_float;
+ data->offset_float_min=data_fake.offset_float_min;
+ data->offset_float_max=data_fake.offset_float_max;
+ data->lookbehind_float+= scan->flags;
+ }
+ }
+ }
+
- cl_and(data->start_class, &intrnl);
- if (was)
- data->start_class->flags |= ANYOF_EOS;
}
+#endif
}
else if (OP(scan) == OPEN) {
pars++;
}
else if (OP(scan) == LOGICAL && scan->flags == 2) { /* Embedded follows */
if (flags & SCF_DO_SUBSTR) {
- scan_commit(pRExC_state,data);
+ scan_commit(pRExC_state,data,minlenp);
data->longest = &(data->longest_float);
}
is_inf = is_inf_internal = 1;
cl_anything(pRExC_state, data->start_class);
flags &= ~SCF_DO_STCLASS;
}
+#ifdef TRIE_STUDY_OPT
+#ifdef FULL_TRIE_STUDY
+ else if (PL_regkind[OP(scan)] == TRIE) {
+ /* NOTE - There is similar code to this block above for handling
+ BRANCH nodes on the initial study. If you change stuff here
+ check there too. */
+ regnode *tail= regnext(scan);
+ reg_trie_data *trie = (reg_trie_data*)RExC_rx->data->data[ ARG(scan) ];
+ I32 max1 = 0, min1 = I32_MAX;
+ struct regnode_charclass_class accum;
+
+ if (flags & SCF_DO_SUBSTR) /* XXXX Add !SUSPEND? */
+ scan_commit(pRExC_state, data,minlenp); /* Cannot merge strings after this. */
+ if (flags & SCF_DO_STCLASS)
+ cl_init_zero(pRExC_state, &accum);
+
+ if (!trie->jump) {
+ min1= trie->minlen;
+ max1= trie->maxlen;
+ } else {
+ const regnode *nextbranch= NULL;
+ U32 word;
+
+ for ( word=1 ; word <= trie->wordcount ; word++)
+ {
+ I32 deltanext=0, minnext=0, f = 0, fake;
+ struct regnode_charclass_class this_class;
+
+ data_fake.flags = 0;
+ if (data) {
+ data_fake.whilem_c = data->whilem_c;
+ data_fake.last_closep = data->last_closep;
+ }
+ else
+ data_fake.last_closep = &fake;
+
+ if (flags & SCF_DO_STCLASS) {
+ cl_init(pRExC_state, &this_class);
+ data_fake.start_class = &this_class;
+ f = SCF_DO_STCLASS_AND;
+ }
+ if (flags & SCF_WHILEM_VISITED_POS)
+ f |= SCF_WHILEM_VISITED_POS;
+
+ if (trie->jump[word]) {
+ if (!nextbranch)
+ nextbranch = tail - trie->jump[0];
+ scan= tail - trie->jump[word];
+ /* We go from the jump point to the branch that follows
+ it. Note this means we need the vestigal unused branches
+ even though they arent otherwise used.
+ */
+ minnext = study_chunk(pRExC_state, &scan, minlenp, &deltanext,
+ (regnode *)nextbranch, &data_fake, f,depth+1);
+ }
+ if (nextbranch && PL_regkind[OP(nextbranch)]==BRANCH)
+ nextbranch= regnext((regnode*)nextbranch);
+
+ if (min1 > (I32)(minnext + trie->minlen))
+ min1 = minnext + trie->minlen;
+ if (max1 < (I32)(minnext + deltanext + trie->maxlen))
+ max1 = minnext + deltanext + trie->maxlen;
+ if (deltanext == I32_MAX)
+ is_inf = is_inf_internal = 1;
+
+ if (data_fake.flags & (SF_HAS_PAR|SF_IN_PAR))
+ pars++;
+
+ if (data) {
+ if (data_fake.flags & SF_HAS_EVAL)
+ data->flags |= SF_HAS_EVAL;
+ data->whilem_c = data_fake.whilem_c;
+ }
+ if (flags & SCF_DO_STCLASS)
+ cl_or(pRExC_state, &accum, &this_class);
+ }
+ }
+ if (flags & SCF_DO_SUBSTR) {
+ data->pos_min += min1;
+ data->pos_delta += max1 - min1;
+ if (max1 != min1 || is_inf)
+ data->longest = &(data->longest_float);
+ }
+ min += min1;
+ delta += max1 - min1;
+ if (flags & SCF_DO_STCLASS_OR) {
+ cl_or(pRExC_state, data->start_class, &accum);
+ if (min1) {
+ cl_and(data->start_class, &and_with);
+ flags &= ~SCF_DO_STCLASS;
+ }
+ }
+ else if (flags & SCF_DO_STCLASS_AND) {
+ if (min1) {
+ cl_and(data->start_class, &accum);
+ flags &= ~SCF_DO_STCLASS;
+ }
+ else {
+ /* Switch to OR mode: cache the old value of
+ * data->start_class */
+ StructCopy(data->start_class, &and_with,
+ struct regnode_charclass_class);
+ flags &= ~SCF_DO_STCLASS_AND;
+ StructCopy(&accum, data->start_class,
+ struct regnode_charclass_class);
+ flags |= SCF_DO_STCLASS_OR;
+ data->start_class->flags |= ANYOF_EOS;
+ }
+ }
+ scan= tail;
+ continue;
+ }
+#else
+ else if (PL_regkind[OP(scan)] == TRIE) {
+ reg_trie_data *trie = (reg_trie_data*)RExC_rx->data->data[ ARG(scan) ];
+ U8*bang=NULL;
+
+ min += trie->minlen;
+ delta += (trie->maxlen - trie->minlen);
+ flags &= ~SCF_DO_STCLASS; /* xxx */
+ if (flags & SCF_DO_SUBSTR) {
+ scan_commit(pRExC_state,data,minlenp); /* Cannot expect anything... */
+ data->pos_min += trie->minlen;
+ data->pos_delta += (trie->maxlen - trie->minlen);
+ if (trie->maxlen != trie->minlen)
+ data->longest = &(data->longest_float);
+ }
+ if (trie->jump) /* no more substrings -- for now /grr*/
+ flags &= ~SCF_DO_SUBSTR;
+ }
+#endif /* old or new */
+#endif /* TRIE_STUDY_OPT */
/* Else: zero-length, ignore. */
scan = regnext(scan);
}
*deltap = is_inf_internal ? I32_MAX : delta;
if (flags & SCF_DO_SUBSTR && is_inf)
data->pos_delta = I32_MAX - data->pos_min;
- if (is_par > U8_MAX)
+ if (is_par > (I32)U8_MAX)
is_par = 0;
if (is_par && pars==1 && data) {
data->flags |= SF_IN_PAR;
}
if (flags & SCF_DO_STCLASS_OR)
cl_and(data->start_class, &and_with);
- if (flags & SCF_EXACT_TRIE)
- data->flags |= SCF_EXACT_TRIE;
+ if (flags & SCF_TRIE_RESTUDY)
+ data->flags |= SCF_TRIE_RESTUDY;
+
+ DEBUG_STUDYDATA(data,depth);
+
return min;
}
#endif
+#ifdef TRIE_STUDY_OPT
+#define CHECK_RESTUDY_GOTO \
+ if ( \
+ (data.flags & SCF_TRIE_RESTUDY) \
+ && ! restudied++ \
+ ) goto reStudy
+#else
+#define CHECK_RESTUDY_GOTO
+#endif
/*
- pregcomp - compile a regular expression into internal code
*
RExC_precomp = exp;
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]);
+ SV *dsv= sv_newmortal();
+ RE_PV_QUOTED_DECL(s, RExC_utf8,
+ dsv, RExC_precomp, (xend - exp), 60);
+ PerlIO_printf(Perl_debug_log, "%sCompiling REx%s %s\n",
+ PL_colors[4],PL_colors[5],s);
});
RExC_flags = pm->op_pmflags;
RExC_sawback = 0;
RExC_emit_start = r->program;
RExC_emit = r->program;
/* Store the count of eval-groups for security checks: */
- RExC_emit->next_off = (U16)((RExC_seen_evals > U16_MAX) ? U16_MAX : RExC_seen_evals);
+ RExC_emit->next_off = (RExC_seen_evals > (I32)U16_MAX) ? U16_MAX : (U16)RExC_seen_evals;
REGC((U8)REG_MAGIC, (char*) RExC_emit++);
r->data = 0;
if (reg(pRExC_state, 0, &flags,1) == NULL)
Newx(r->substrs, 1, struct reg_substr_data);
reStudy:
+ r->minlen = minlen = sawplus = sawopen = 0;
Zero(r->substrs, 1, struct reg_substr_data);
StructCopy(&zero_scan_data, &data, scan_data_t);
if ( restudied ) {
DEBUG_OPTIMISE_r(PerlIO_printf(Perl_debug_log,"Restudying\n"));
RExC_state=copyRExC_state;
- if (data.longest_fixed)
+ if (data.last_found) {
SvREFCNT_dec(data.longest_fixed);
- if (data.longest_float)
SvREFCNT_dec(data.longest_float);
- if (data.last_found)
SvREFCNT_dec(data.last_found);
+ }
} else {
copyRExC_state=RExC_state;
}
r->reganch |= ROPT_NAUGHTY;
scan = r->program + 1; /* First BRANCH. */
- /* XXXX Should not we check for something else? Usually it is OPEN1... */
+ /* testing for BRANCH here tells us whether there is "must appear"
+ data in the pattern. If there is then we can use it for optimisations */
if (OP(scan) != BRANCH) { /* Only one top-level choice. */
I32 fake;
STRLEN longest_float_length, longest_fixed_length;
/* An {n,m} with n>0 */
(PL_regkind[OP(first)] == CURLY && ARG1(first) > 0) )
{
- DEBUG_PEEP("first:",first,0);
+
if (OP(first) == PLUS)
sawplus = 1;
else
/* Starting-point info. */
again:
+ DEBUG_PEEP("first:",first,0);
/* Ignore EXACT as we deal with it later. */
if (PL_regkind[OP(first)] == EXACT) {
if (OP(first) == EXACT)
r->regstclass = first;
}
#ifdef TRIE_STCLASS
- else if (OP(first) == TRIE &&
+ else if (PL_regkind[OP(first)] == TRIE &&
((reg_trie_data *)r->data->data[ ARG(first) ])->minlen>0)
{
+ regnode *trie_op;
/* this can happen only on restudy */
- struct regnode_1 *trie_op;
- Newxz(trie_op,1,struct regnode_1);
- StructCopy(first,trie_op,struct regnode_1);
- make_trie_failtable(pRExC_state, (regnode *)first, (regnode *)trie_op, 0);
- r->regstclass = (regnode *)trie_op;
+ if ( OP(first) == TRIE ) {
+ struct regnode_1 *trieop;
+ Newxz(trieop,1,struct regnode_1);
+ StructCopy(first,trieop,struct regnode_1);
+ trie_op=(regnode *)trieop;
+ } else {
+ struct regnode_charclass *trieop;
+ Newxz(trieop,1,struct regnode_charclass);
+ StructCopy(first,trieop,struct regnode_charclass);
+ trie_op=(regnode *)trieop;
+ }
+ OP(trie_op)+=2;
+ make_trie_failtable(pRExC_state, (regnode *)first, trie_op, 0);
+ r->regstclass = trie_op;
}
#endif
else if (strchr((const char*)PL_simple,OP(first)))
stclass_flag = 0;
data.last_closep = &last_close;
- minlen = study_chunk(pRExC_state, &first, &fake, scan + RExC_size, /* Up to end */
+ minlen = study_chunk(pRExC_state, &first, &minlen, &fake, scan + RExC_size, /* Up to end */
&data, SCF_DO_SUBSTR | SCF_WHILEM_VISITED_POS | stclass_flag,0);
-#ifdef TRIE_STUDY_OPT
- if ( (data.flags & SCF_EXACT_TRIE) && ! restudied++ ) {
- goto reStudy;
- }
-#endif
+ CHECK_RESTUDY_GOTO;
+
+
if ( RExC_npar == 1 && data.longest == &(data.longest_fixed)
&& data.last_start_min == 0 && data.last_end > 0
&& !RExC_seen_zerolen
&& (!(RExC_seen & REG_SEEN_GPOS) || (r->reganch & ROPT_ANCH_GPOS)))
r->reganch |= ROPT_CHECK_ALL;
- scan_commit(pRExC_state, &data);
+ scan_commit(pRExC_state, &data,&minlen);
SvREFCNT_dec(data.last_found);
+ /* Note that code very similar to this but for anchored string
+ follows immediately below, changes may need to be made to both.
+ Be careful.
+ */
longest_float_length = CHR_SVLEN(data.longest_float);
if (longest_float_length
|| (data.flags & SF_FL_BEFORE_EOL
&& (!(data.flags & SF_FL_BEFORE_MEOL)
- || (RExC_flags & PMf_MULTILINE)))) {
- int t;
+ || (RExC_flags & PMf_MULTILINE))))
+ {
+ I32 t,ml;
- if (SvCUR(data.longest_fixed) /* ok to leave SvCUR */
+ if (SvCUR(data.longest_fixed) /* ok to leave SvCUR */
&& data.offset_fixed == data.offset_float_min
&& SvCUR(data.longest_fixed) == SvCUR(data.longest_float))
goto remove_float; /* As in (a)+. */
+ /* copy the information about the longest float from the reg_scan_data
+ over to the program. */
if (SvUTF8(data.longest_float)) {
r->float_utf8 = data.longest_float;
r->float_substr = NULL;
r->float_substr = data.longest_float;
r->float_utf8 = NULL;
}
- r->float_min_offset = data.offset_float_min;
+ /* float_end_shift is how many chars that must be matched that
+ follow this item. We calculate it ahead of time as once the
+ lookbehind offset is added in we lose the ability to correctly
+ calculate it.*/
+ ml = data.minlen_float ? *(data.minlen_float)
+ : (I32)longest_float_length;
+ r->float_end_shift = ml - data.offset_float_min
+ - longest_float_length + (SvTAIL(data.longest_float) != 0)
+ + data.lookbehind_float;
+ r->float_min_offset = data.offset_float_min - data.lookbehind_float;
r->float_max_offset = data.offset_float_max;
+ if (data.offset_float_max < I32_MAX) /* Don't offset infinity */
+ r->float_max_offset -= data.lookbehind_float;
+
t = (data.flags & SF_FL_BEFORE_EOL /* Can't have SEOL and MULTI */
&& (!(data.flags & SF_FL_BEFORE_MEOL)
|| (RExC_flags & PMf_MULTILINE)));
longest_float_length = 0;
}
+ /* Note that code very similar to this but for floating string
+ is immediately above, changes may need to be made to both.
+ Be careful.
+ */
longest_fixed_length = CHR_SVLEN(data.longest_fixed);
if (longest_fixed_length
|| (data.flags & SF_FIX_BEFORE_EOL /* Cannot have SEOL and MULTI */
&& (!(data.flags & SF_FIX_BEFORE_MEOL)
- || (RExC_flags & PMf_MULTILINE)))) {
- int t;
+ || (RExC_flags & PMf_MULTILINE))))
+ {
+ I32 t,ml;
+ /* copy the information about the longest fixed
+ from the reg_scan_data over to the program. */
if (SvUTF8(data.longest_fixed)) {
r->anchored_utf8 = data.longest_fixed;
r->anchored_substr = NULL;
r->anchored_substr = data.longest_fixed;
r->anchored_utf8 = NULL;
}
- r->anchored_offset = data.offset_fixed;
+ /* fixed_end_shift is how many chars that must be matched that
+ follow this item. We calculate it ahead of time as once the
+ lookbehind offset is added in we lose the ability to correctly
+ calculate it.*/
+ ml = data.minlen_fixed ? *(data.minlen_fixed)
+ : (I32)longest_fixed_length;
+ r->anchored_end_shift = ml - data.offset_fixed
+ - longest_fixed_length + (SvTAIL(data.longest_fixed) != 0)
+ + data.lookbehind_fixed;
+ r->anchored_offset = data.offset_fixed - data.lookbehind_fixed;
+
t = (data.flags & SF_FIX_BEFORE_EOL /* Can't have SEOL and MULTI */
&& (!(data.flags & SF_FIX_BEFORE_MEOL)
|| (RExC_flags & PMf_MULTILINE)));
/* A temporary algorithm prefers floated substr to fixed one to dig more info. */
if (longest_fixed_length > longest_float_length) {
+ r->check_end_shift = r->anchored_end_shift;
r->check_substr = r->anchored_substr;
r->check_utf8 = r->anchored_utf8;
r->check_offset_min = r->check_offset_max = r->anchored_offset;
r->reganch |= ROPT_NOSCAN;
}
else {
+ r->check_end_shift = r->float_end_shift;
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;
+ r->check_offset_min = r->float_min_offset;
+ r->check_offset_max = r->float_max_offset;
}
/* XXXX Currently intuiting is not compatible with ANCH_GPOS.
This should be changed ASAP! */
if (SvTAIL(r->check_substr ? r->check_substr : r->check_utf8))
r->reganch |= RE_INTUIT_TAIL;
}
+ /* XXX Unneeded? dmq (shouldn't as this is handled elsewhere)
+ if ( (STRLEN)minlen < longest_float_length )
+ minlen= longest_float_length;
+ if ( (STRLEN)minlen < longest_fixed_length )
+ minlen= longest_fixed_length;
+ */
}
else {
/* Several toplevels. Best we can is to set minlen. */
data.start_class = &ch_class;
data.last_closep = &last_close;
- minlen = study_chunk(pRExC_state, &scan, &fake, scan + RExC_size,
+ minlen = study_chunk(pRExC_state, &scan, &minlen, &fake, scan + RExC_size,
&data, SCF_DO_STCLASS_AND|SCF_WHILEM_VISITED_POS,0);
-#ifdef TRIE_STUDY_OPT
- if ( (data.flags & SCF_EXACT_TRIE) && ! restudied++ ) {
- goto reStudy;
- }
-#endif
+ CHECK_RESTUDY_GOTO;
r->check_substr = r->check_utf8 = r->anchored_substr = r->anchored_utf8
= r->float_substr = r->float_utf8 = NULL;
}
}
- r->minlen = minlen;
+ /* Guard against an embedded (?=) or (?<=) with a longer minlen than
+ the "real" pattern. */
+ if (r->minlen < minlen)
+ r->minlen = minlen;
+
if (RExC_seen & REG_SEEN_GPOS)
r->reganch |= ROPT_GPOS_SEEN;
if (RExC_seen & REG_SEEN_LOOKBEHIND)
for (i = 1; i <= len; i++) {
if (r->offsets[i*2-1] || r->offsets[i*2])
PerlIO_printf(Perl_debug_log, "%"UVuf":%"UVuf"[%"UVuf"] ",
- i, (UV)r->offsets[i*2-1], (UV)r->offsets[i*2]);
+ (UV)i, (UV)r->offsets[i*2-1], (UV)r->offsets[i*2]);
}
PerlIO_printf(Perl_debug_log, "\n");
});
I32 min;
I32 max = REG_INFTY;
char *parse_start;
+ const char *maxpos = NULL;
GET_RE_DEBUG_FLAGS_DECL;
DEBUG_PARSE("piec");
op = *RExC_parse;
if (op == '{' && regcurly(RExC_parse)) {
- const char *maxpos = NULL;
+ maxpos = NULL;
parse_start = RExC_parse; /* MJD */
next = RExC_parse + 1;
while (isDIGIT(*next) || *next == ',') {
S_regclass(pTHX_ RExC_state_t *pRExC_state, U32 depth)
{
dVAR;
- register UV value;
+ register UV value = 0;
register UV nextvalue;
register IV prevvalue = OOB_UNICODE;
register IV range = 0;
STRLEN foldlen;
const UV f = to_uni_fold(natvalue, foldbuf, &foldlen);
+#ifdef EBCDIC /* RD t/uni/fold ff and 6b */
+ if (RExC_precomp[0] == ':' &&
+ RExC_precomp[1] == '[' &&
+ (f == 0xDF || f == 0x92)) {
+ f = NATIVE_TO_UNI(f);
+ }
+#endif
/* If folding and foldable and a single
* character, insert also the folded version
* to the charclass. */
if (f != value) {
+#ifdef EBCDIC /* RD tunifold ligatures s,t fb05, fb06 */
+ if ((RExC_precomp[0] == ':' &&
+ RExC_precomp[1] == '[' &&
+ (f == 0xA2 &&
+ (value == 0xFB05 || value == 0xFB06))) ?
+ foldlen == ((STRLEN)UNISKIP(f) - 1) :
+ foldlen == (STRLEN)UNISKIP(f) )
+#else
if (foldlen == (STRLEN)UNISKIP(f))
+#endif
Perl_sv_catpvf(aTHX_ listsv,
"%04"UVxf"\n", f);
else {
? "Overwriting end of array!\n" : "OK",
(UV)(place - RExC_emit_start),
(UV)(RExC_parse - RExC_start),
- RExC_offsets[0]));
+ (UV)RExC_offsets[0]));
Set_Node_Offset(place, RExC_parse);
Set_Node_Length(place, 1);
}
#ifdef DEBUGGING
dVAR;
SV * const sv = sv_newmortal();
+ SV *dsv= sv_newmortal();
- (void)dumpuntil(r, r->program, r->program + 1, NULL, sv, 0);
+ (void)dumpuntil(r, r->program, r->program + 1, NULL, NULL, sv, 0, 0);
/* Header fields of interest. */
- if (r->anchored_substr)
+ if (r->anchored_substr) {
+ RE_PV_QUOTED_DECL(s, 0, dsv, SvPVX_const(r->anchored_substr),
+ RE_SV_DUMPLEN(r->anchored_substr), 30);
PerlIO_printf(Perl_debug_log,
- "anchored \"%s%.*s%s\"%s at %"IVdf" ",
- PL_colors[0],
- (int)(SvCUR(r->anchored_substr) - (SvTAIL(r->anchored_substr)!=0)),
- SvPVX_const(r->anchored_substr),
- PL_colors[1],
- SvTAIL(r->anchored_substr) ? "$" : "",
+ "anchored %s%s at %"IVdf" ",
+ s, RE_SV_TAIL(r->anchored_substr),
(IV)r->anchored_offset);
- else if (r->anchored_utf8)
+ } else if (r->anchored_utf8) {
+ RE_PV_QUOTED_DECL(s, 1, dsv, SvPVX_const(r->anchored_utf8),
+ RE_SV_DUMPLEN(r->anchored_utf8), 30);
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_const(r->anchored_utf8),
- PL_colors[1],
- SvTAIL(r->anchored_utf8) ? "$" : "",
+ "anchored utf8 %s%s at %"IVdf" ",
+ s, RE_SV_TAIL(r->anchored_utf8),
(IV)r->anchored_offset);
- if (r->float_substr)
+ }
+ if (r->float_substr) {
+ RE_PV_QUOTED_DECL(s, 0, dsv, SvPVX_const(r->float_substr),
+ RE_SV_DUMPLEN(r->float_substr), 30);
PerlIO_printf(Perl_debug_log,
- "floating \"%s%.*s%s\"%s at %"IVdf"..%"UVuf" ",
- PL_colors[0],
- (int)(SvCUR(r->float_substr) - (SvTAIL(r->float_substr)!=0)),
- SvPVX_const(r->float_substr),
- PL_colors[1],
- SvTAIL(r->float_substr) ? "$" : "",
+ "floating %s%s at %"IVdf"..%"UVuf" ",
+ s, RE_SV_TAIL(r->float_substr),
(IV)r->float_min_offset, (UV)r->float_max_offset);
- else if (r->float_utf8)
+ } else if (r->float_utf8) {
+ RE_PV_QUOTED_DECL(s, 1, dsv, SvPVX_const(r->float_utf8),
+ RE_SV_DUMPLEN(r->float_utf8), 30);
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_const(r->float_utf8),
- PL_colors[1],
- SvTAIL(r->float_utf8) ? "$" : "",
+ "floating utf8 %s%s at %"IVdf"..%"UVuf" ",
+ s, RE_SV_TAIL(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");
+ (const char *)
+ (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)
if (r->regstclass) {
regprop(r, sv, r->regstclass);
- PerlIO_printf(Perl_debug_log, "stclass \"%s\" ", SvPVX_const(sv));
+ PerlIO_printf(Perl_debug_log, "stclass %s ", SvPVX_const(sv));
}
if (r->reganch & ROPT_ANCH) {
PerlIO_printf(Perl_debug_log, "anchored");
#ifdef DEBUGGING
dVAR;
register int k;
+ GET_RE_DEBUG_FLAGS_DECL;
sv_setpvn(sv, "", 0);
if (OP(o) >= reg_num) /* regnode.type is unsigned */
if (k == EXACT) {
SV * const dsv = sv_2mortal(newSVpvs(""));
- /* 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 */
- const bool do_utf8 = is_utf8_string((U8*)STRING(o), STR_LEN(o));
- const char * const s = do_utf8 ?
- pv_uni_display(dsv, (U8*)STRING(o), STR_LEN(o), 60,
- UNI_DISPLAY_REGEX) :
- STRING(o);
- 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]);
+ /* Using is_utf8_string() (via PERL_PV_UNI_DETECT)
+ * is a crude hack but it may be the best for now since
+ * we have no flag "this EXACTish node was UTF-8"
+ * --jhi */
+ const char * const s =
+ pv_pretty(dsv, STRING(o), STR_LEN(o), 60,
+ PL_colors[0], PL_colors[1],
+ PERL_PV_ESCAPE_UNI_DETECT |
+ PERL_PV_PRETTY_ELIPSES |
+ PERL_PV_PRETTY_LTGT
+ );
+ Perl_sv_catpvf(aTHX_ sv, " %s", s );
} else if (k == TRIE) {
- Perl_sv_catpvf(aTHX_ sv, "-%s",reg_name[o->flags]);
/* print the details of the trie in dumpuntil instead, as
* prog->data isn't available here */
+ const char op = OP(o);
+ const I32 n = ARG(o);
+ const reg_ac_data * const ac = IS_TRIE_AC(op) ?
+ (reg_ac_data *)prog->data->data[n] :
+ NULL;
+ const reg_trie_data * const trie = !IS_TRIE_AC(op) ?
+ (reg_trie_data*)prog->data->data[n] :
+ ac->trie;
+
+ Perl_sv_catpvf(aTHX_ sv, "-%s",reg_name[o->flags]);
+ DEBUG_TRIE_COMPILE_r(
+ Perl_sv_catpvf(aTHX_ sv,
+ "<S:%"UVuf"/%"IVdf" W:%"UVuf" L:%"UVuf"/%"UVuf" C:%"UVuf"/%"UVuf">",
+ (UV)trie->startstate,
+ (IV)trie->laststate-1,
+ (UV)trie->wordcount,
+ (UV)trie->minlen,
+ (UV)trie->maxlen,
+ (UV)TRIE_CHARCOUNT(trie),
+ (UV)trie->uniquecharcount
+ )
+ );
+ if ( IS_ANYOF_TRIE(op) || trie->bitmap ) {
+ int i;
+ int rangestart = -1;
+ U8* bitmap = IS_ANYOF_TRIE(op) ? (U8*)ANYOF_BITMAP(o) : (U8*)TRIE_BITMAP(trie);
+ Perl_sv_catpvf(aTHX_ sv, "[");
+ for (i = 0; i <= 256; i++) {
+ if (i < 256 && BITMAP_TEST(bitmap,i)) {
+ if (rangestart == -1)
+ rangestart = i;
+ } else if (rangestart != -1) {
+ if (i <= rangestart + 3)
+ for (; rangestart < i; rangestart++)
+ put_byte(sv, rangestart);
+ else {
+ put_byte(sv, rangestart);
+ sv_catpvs(sv, "-");
+ put_byte(sv, i - 1);
+ }
+ rangestart = -1;
+ }
+ }
+ Perl_sv_catpvf(aTHX_ sv, "]");
+ }
+
} 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_pregfree(pTHX_ struct regexp *r)
{
dVAR;
-#ifdef DEBUGGING
- SV * const dsv = PERL_DEBUG_PAD_ZERO(0);
-#endif
+
GET_RE_DEBUG_FLAGS_DECL;
if (!r || (--r->refcnt > 0))
return;
- DEBUG_COMPILE_r(if (RX_DEBUG(r)){
- const char * const 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",
- PL_colors[4],PL_colors[5],PL_colors[0],
- len, len, s,
- PL_colors[1],
- len > 60 ? "..." : "");
+ DEBUG_COMPILE_r({
+ if (!PL_colorset)
+ reginitcolors();
+ if (RX_DEBUG(r)){
+ SV *dsv= sv_newmortal();
+ RE_PV_QUOTED_DECL(s, (r->reganch & ROPT_UTF8),
+ dsv, r->precomp, r->prelen, 60);
+ PerlIO_printf(Perl_debug_log,"%sFreeing REx:%s %s\n",
+ PL_colors[4],PL_colors[5],s);
+ }
});
/* gcov results gave these as non-null 100% of the time, so there's no
Safefree(trie->bitmap);
if (trie->wordlen)
Safefree(trie->wordlen);
+ if (trie->jump)
+ Safefree(trie->jump);
+ if (trie->nextword)
+ Safefree(trie->nextword);
#ifdef DEBUGGING
if (RX_DEBUG(r)) {
if (trie->words)
Perl_sv_catpvf(aTHX_ sv, "%c", c);
}
+
#define CLEAR_OPTSTART \
if (optstart) STMT_START { \
DEBUG_OPTIMISE_r(PerlIO_printf(Perl_debug_log, " (%d nodes)\n", node - optstart)); \
optstart=NULL; \
} STMT_END
-#define DUMPUNTIL(a,b,c,d,e,f) CLEAR_OPTSTART; node=dumpuntil(a,b,c,d,e,f);
+#define DUMPUNTIL(b,e) CLEAR_OPTSTART; node=dumpuntil(r,start,(b),(e),last,sv,indent+1,depth+1);
STATIC const regnode *
S_dumpuntil(pTHX_ const regexp *r, const regnode *start, const regnode *node,
- const regnode *last, SV* sv, I32 l)
+ const regnode *last, const regnode *plast,
+ SV* sv, I32 indent, U32 depth)
{
dVAR;
- register U8 op = EXACT; /* Arbitrary non-END op. */
+ register U8 op = PSEUDO; /* Arbitrary non-END op. */
register const regnode *next;
const regnode *optstart= NULL;
GET_RE_DEBUG_FLAGS_DECL;
- while (op != END && (!last || node < last)) {
+#ifdef DEBUG_DUMPUNTIL
+ PerlIO_printf(Perl_debug_log, "--- %d : %d - %d - %d\n",indent,node-start,
+ last ? last-start : 0,plast ? plast-start : 0);
+#endif
+
+ if (plast && plast < last)
+ last= plast;
+
+ while (PL_regkind[op] != END && (!last || node < last)) {
/* While that wasn't END last time... */
NODE_ALIGN(node);
op = OP(node);
if (op == CLOSE)
- l--;
+ indent--;
next = regnext((regnode *)node);
/* Where, what. */
regprop(r, sv, node);
PerlIO_printf(Perl_debug_log, "%4"IVdf":%*s%s", (IV)(node - start),
- (int)(2*l + 1), "", SvPVX_const(sv));
+ (int)(2*indent + 1), "", SvPVX_const(sv));
if (OP(node) != OPTIMIZED) {
if (next == NULL) /* Next ptr. */
PerlIO_printf(Perl_debug_log, "(0)");
+ else if (PL_regkind[(U8)op] == BRANCH && PL_regkind[OP(next)] != BRANCH )
+ PerlIO_printf(Perl_debug_log, "(FAIL)");
else
PerlIO_printf(Perl_debug_log, "(%"IVdf")", (IV)(next - start));
- (void)PerlIO_putc(Perl_debug_log, '\n');
+
+ /*if (PL_regkind[(U8)op] != TRIE)*/
+ (void)PerlIO_putc(Perl_debug_log, '\n');
}
after_print:
: next);
if (last && nnode > last)
nnode = last;
- DUMPUNTIL(r, start, NEXTOPER(NEXTOPER(node)), nnode, sv, l + 1);
+ DUMPUNTIL(NEXTOPER(NEXTOPER(node)), nnode);
}
}
else if (PL_regkind[(U8)op] == BRANCH) {
assert(next);
- DUMPUNTIL(r, start, NEXTOPER(node), next, sv, l + 1);
+ DUMPUNTIL(NEXTOPER(node), next);
}
else if ( PL_regkind[(U8)op] == TRIE ) {
+ const char op = OP(node);
const I32 n = ARG(node);
- const reg_trie_data * const trie = (reg_trie_data*)r->data->data[n];
- const I32 arry_len = av_len(trie->words)+1;
+ const reg_ac_data * const ac = op>=AHOCORASICK ?
+ (reg_ac_data *)r->data->data[n] :
+ NULL;
+ const reg_trie_data * const trie = op<AHOCORASICK ?
+ (reg_trie_data*)r->data->data[n] :
+ ac->trie;
+ const regnode *nextbranch= NULL;
I32 word_idx;
- PerlIO_printf(Perl_debug_log,
- "%*s[StS:%"UVuf" Wds:%d Cs:%d Uq:%d #Sts:%"IVdf" Mn:%d Mx:%d",
- (int)(2*(l+3)),
- "",
- trie->startstate,
- TRIE_WORDCOUNT(trie),
- (int)TRIE_CHARCOUNT(trie),
- trie->uniquecharcount,
- (IV)TRIE_LASTSTATE(trie)-1,
- (int)trie->minlen,
- (int)trie->maxlen
- );
- if (trie->bitmap) {
- int i;
- int rangestart= -1;
- sv_setpvn(sv, "", 0);
- for (i = 0; i <= 256; i++) {
- if (i < 256 && TRIE_BITMAP_TEST(trie,i)) {
- if (rangestart == -1)
- rangestart = i;
- } else if (rangestart != -1) {
- if (i <= rangestart + 3)
- for (; rangestart < i; rangestart++)
- put_byte(sv, rangestart);
- else {
- put_byte(sv, rangestart);
- sv_catpvs(sv, "-");
- put_byte(sv, i - 1);
- }
- rangestart = -1;
- }
- }
- PerlIO_printf(Perl_debug_log, " Stcls:%s]\n", SvPVX_const(sv));
- } else
- PerlIO_printf(Perl_debug_log, " No-Stcls]\n");
-
- for (word_idx=0; word_idx < arry_len; word_idx++) {
+ sv_setpvn(sv, "", 0);
+ for (word_idx= 0; word_idx < (I32)trie->wordcount; word_idx++) {
SV ** const 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_const(*elem_ptr),
- PL_colors[1]
- );
+
+ PerlIO_printf(Perl_debug_log, "%*s%s ",
+ (int)(2*(indent+3)), "",
+ elem_ptr ? pv_pretty(sv, SvPV_nolen_const(*elem_ptr), SvCUR(*elem_ptr), 60,
+ PL_colors[0], PL_colors[1],
+ (SvUTF8(*elem_ptr) ? PERL_PV_ESCAPE_UNI : 0) |
+ PERL_PV_PRETTY_ELIPSES |
+ PERL_PV_PRETTY_LTGT
+ )
+ : "???"
+ );
+ if (trie->jump) {
+ U16 dist= trie->jump[word_idx+1];
+ PerlIO_printf(Perl_debug_log, "(%u)\n",(next - dist) - start);
+ if (dist) {
+ if (!nextbranch)
+ nextbranch= next - trie->jump[0];
+ DUMPUNTIL(next - dist, nextbranch);
+ }
+ if (nextbranch && PL_regkind[OP(nextbranch)]==BRANCH)
+ nextbranch= regnext((regnode *)nextbranch);
+ } else {
+ PerlIO_printf(Perl_debug_log, "\n");
}
}
-
- node = NEXTOPER(node);
- node += regarglen[(U8)op];
-
+ if (last && next > last)
+ node= last;
+ else
+ node= next;
}
- else if ( op == CURLY) { /* "next" might be very big: optimizer */
- DUMPUNTIL(r, start, NEXTOPER(node) + EXTRA_STEP_2ARGS,
- NEXTOPER(node) + EXTRA_STEP_2ARGS + 1, sv, l + 1);
+ else if ( op == CURLY ) { /* "next" might be very big: optimizer */
+ DUMPUNTIL(NEXTOPER(node) + EXTRA_STEP_2ARGS,
+ NEXTOPER(node) + EXTRA_STEP_2ARGS + 1);
}
else if (PL_regkind[(U8)op] == CURLY && op != CURLYX) {
assert(next);
- DUMPUNTIL(r, start, NEXTOPER(node) + EXTRA_STEP_2ARGS,
- next, sv, l + 1);
+ DUMPUNTIL(NEXTOPER(node) + EXTRA_STEP_2ARGS, next);
}
else if ( op == PLUS || op == STAR) {
- DUMPUNTIL(r, start, NEXTOPER(node), NEXTOPER(node) + 1, sv, l + 1);
+ DUMPUNTIL(NEXTOPER(node), NEXTOPER(node) + 1);
}
else if (op == ANYOF) {
/* arglen 1 + class block */
node += regarglen[(U8)op];
}
if (op == CURLYX || op == OPEN)
- l++;
+ indent++;
else if (op == WHILEM)
- l--;
+ indent--;
}
CLEAR_OPTSTART;
+#ifdef DEBUG_DUMPUNTIL
+ PerlIO_printf(Perl_debug_log, "--- %d\n",indent);
+#endif
return node;
}
projects / p5sagit/p5-mst-13.2.git / blobdiff