5 * One Ring to rule them all, One Ring to find them
7 * [p.v of _The Lord of the Rings_, opening poem]
8 * [p.50 of _The Lord of the Rings_, I/iii: "The Shadow of the Past"]
9 * [p.254 of _The Lord of the Rings_, II/ii: "The Council of Elrond"]
12 /* This file contains functions for executing a regular expression. See
13 * also regcomp.c which funnily enough, contains functions for compiling
14 * a regular expression.
16 * This file is also copied at build time to ext/re/re_exec.c, where
17 * it's built with -DPERL_EXT_RE_BUILD -DPERL_EXT_RE_DEBUG -DPERL_EXT.
18 * This causes the main functions to be compiled under new names and with
19 * debugging support added, which makes "use re 'debug'" work.
22 /* NOTE: this is derived from Henry Spencer's regexp code, and should not
23 * confused with the original package (see point 3 below). Thanks, Henry!
26 /* Additional note: this code is very heavily munged from Henry's version
27 * in places. In some spots I've traded clarity for efficiency, so don't
28 * blame Henry for some of the lack of readability.
31 /* The names of the functions have been changed from regcomp and
32 * regexec to pregcomp and pregexec in order to avoid conflicts
33 * with the POSIX routines of the same names.
36 #ifdef PERL_EXT_RE_BUILD
40 /* At least one required character in the target string is expressible only in
42 static const char* const non_utf8_target_but_utf8_required
43 = "Can't match, because target string needs to be in UTF-8\n";
45 #define NON_UTF8_TARGET_BUT_UTF8_REQUIRED(target) STMT_START { \
46 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "%s", non_utf8_target_but_utf8_required));\
51 * pregcomp and pregexec -- regsub and regerror are not used in perl
53 * Copyright (c) 1986 by University of Toronto.
54 * Written by Henry Spencer. Not derived from licensed software.
56 * Permission is granted to anyone to use this software for any
57 * purpose on any computer system, and to redistribute it freely,
58 * subject to the following restrictions:
60 * 1. The author is not responsible for the consequences of use of
61 * this software, no matter how awful, even if they arise
64 * 2. The origin of this software must not be misrepresented, either
65 * by explicit claim or by omission.
67 * 3. Altered versions must be plainly marked as such, and must not
68 * be misrepresented as being the original software.
70 **** Alterations to Henry's code are...
72 **** Copyright (C) 1991, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999,
73 **** 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008
74 **** by Larry Wall and others
76 **** You may distribute under the terms of either the GNU General Public
77 **** License or the Artistic License, as specified in the README file.
79 * Beware that some of this code is subtly aware of the way operator
80 * precedence is structured in regular expressions. Serious changes in
81 * regular-expression syntax might require a total rethink.
84 #define PERL_IN_REGEXEC_C
87 #ifdef PERL_IN_XSUB_RE
93 #include "inline_invlist.c"
94 #include "unicode_constants.h"
96 #define RF_tainted 1 /* tainted information used? e.g. locale */
97 #define RF_warned 2 /* warned about big count? */
99 #define RF_utf8 8 /* Pattern contains multibyte chars? */
101 #define UTF_PATTERN ((PL_reg_flags & RF_utf8) != 0)
103 #define HAS_NONLATIN1_FOLD_CLOSURE(i) _HAS_NONLATIN1_FOLD_CLOSURE_ONLY_FOR_USE_BY_REGCOMP_DOT_C_AND_REGEXEC_DOT_C(i)
106 #define STATIC static
109 /* Valid for non-utf8 strings: avoids the reginclass
110 * call if there are no complications: i.e., if everything matchable is
111 * straight forward in the bitmap */
112 #define REGINCLASS(prog,p,c) (ANYOF_FLAGS(p) ? reginclass(prog,p,c,0) \
113 : ANYOF_BITMAP_TEST(p,*(c)))
119 #define CHR_SVLEN(sv) (utf8_target ? sv_len_utf8(sv) : SvCUR(sv))
120 #define CHR_DIST(a,b) (PL_reg_match_utf8 ? utf8_distance(a,b) : a - b)
122 #define HOPc(pos,off) \
123 (char *)(PL_reg_match_utf8 \
124 ? reghop3((U8*)pos, off, (U8*)(off >= 0 ? PL_regeol : PL_bostr)) \
126 #define HOPBACKc(pos, off) \
127 (char*)(PL_reg_match_utf8\
128 ? reghopmaybe3((U8*)pos, -off, (U8*)PL_bostr) \
129 : (pos - off >= PL_bostr) \
133 #define HOP3(pos,off,lim) (PL_reg_match_utf8 ? reghop3((U8*)(pos), off, (U8*)(lim)) : (U8*)(pos + off))
134 #define HOP3c(pos,off,lim) ((char*)HOP3(pos,off,lim))
137 #define NEXTCHR_EOS -10 /* nextchr has fallen off the end */
138 #define NEXTCHR_IS_EOS (nextchr < 0)
140 #define SET_nextchr \
141 nextchr = ((locinput < PL_regeol) ? UCHARAT(locinput) : NEXTCHR_EOS)
143 #define SET_locinput(p) \
148 #define LOAD_UTF8_CHARCLASS(swash_ptr, property_name) STMT_START { \
150 U8 flags = _CORE_SWASH_INIT_ACCEPT_INVLIST; \
151 ENTER; save_re_context(); \
152 swash_ptr = _core_swash_init("utf8", property_name, &PL_sv_undef, \
153 1, 0, NULL, &flags); \
158 /* If in debug mode, we test that a known character properly matches */
160 # define LOAD_UTF8_CHARCLASS_DEBUG_TEST(swash_ptr, \
162 utf8_char_in_property) \
163 LOAD_UTF8_CHARCLASS(swash_ptr, property_name); \
164 assert(swash_fetch(swash_ptr, (U8 *) utf8_char_in_property, TRUE));
166 # define LOAD_UTF8_CHARCLASS_DEBUG_TEST(swash_ptr, \
168 utf8_char_in_property) \
169 LOAD_UTF8_CHARCLASS(swash_ptr, property_name)
172 #define LOAD_UTF8_CHARCLASS_ALNUM() LOAD_UTF8_CHARCLASS_DEBUG_TEST( \
173 PL_utf8_swash_ptrs[_CC_WORDCHAR], \
174 swash_property_names[_CC_WORDCHAR], \
175 GREEK_SMALL_LETTER_IOTA_UTF8)
177 #define LOAD_UTF8_CHARCLASS_GCB() /* Grapheme cluster boundaries */ \
179 LOAD_UTF8_CHARCLASS_DEBUG_TEST(PL_utf8_X_regular_begin, \
180 "_X_regular_begin", \
181 GREEK_SMALL_LETTER_IOTA_UTF8); \
182 LOAD_UTF8_CHARCLASS_DEBUG_TEST(PL_utf8_X_extend, \
184 COMBINING_GRAVE_ACCENT_UTF8); \
187 #define PLACEHOLDER /* Something for the preprocessor to grab onto */
188 /* TODO: Combine JUMPABLE and HAS_TEXT to cache OP(rn) */
190 /* for use after a quantifier and before an EXACT-like node -- japhy */
191 /* it would be nice to rework regcomp.sym to generate this stuff. sigh
193 * NOTE that *nothing* that affects backtracking should be in here, specifically
194 * VERBS must NOT be included. JUMPABLE is used to determine if we can ignore a
195 * node that is in between two EXACT like nodes when ascertaining what the required
196 * "follow" character is. This should probably be moved to regex compile time
197 * although it may be done at run time beause of the REF possibility - more
198 * investigation required. -- demerphq
200 #define JUMPABLE(rn) ( \
202 (OP(rn) == CLOSE && (!cur_eval || cur_eval->u.eval.close_paren != ARG(rn))) || \
204 OP(rn) == SUSPEND || OP(rn) == IFMATCH || \
205 OP(rn) == PLUS || OP(rn) == MINMOD || \
207 (PL_regkind[OP(rn)] == CURLY && ARG1(rn) > 0) \
209 #define IS_EXACT(rn) (PL_regkind[OP(rn)] == EXACT)
211 #define HAS_TEXT(rn) ( IS_EXACT(rn) || PL_regkind[OP(rn)] == REF )
214 /* Currently these are only used when PL_regkind[OP(rn)] == EXACT so
215 we don't need this definition. */
216 #define IS_TEXT(rn) ( OP(rn)==EXACT || OP(rn)==REF || OP(rn)==NREF )
217 #define IS_TEXTF(rn) ( OP(rn)==EXACTFU || OP(rn)==EXACTFU_SS || OP(rn)==EXACTFU_TRICKYFOLD || OP(rn)==EXACTFA || OP(rn)==EXACTF || OP(rn)==REFF || OP(rn)==NREFF )
218 #define IS_TEXTFL(rn) ( OP(rn)==EXACTFL || OP(rn)==REFFL || OP(rn)==NREFFL )
221 /* ... so we use this as its faster. */
222 #define IS_TEXT(rn) ( OP(rn)==EXACT )
223 #define IS_TEXTFU(rn) ( OP(rn)==EXACTFU || OP(rn)==EXACTFU_SS || OP(rn)==EXACTFU_TRICKYFOLD || OP(rn) == EXACTFA)
224 #define IS_TEXTF(rn) ( OP(rn)==EXACTF )
225 #define IS_TEXTFL(rn) ( OP(rn)==EXACTFL )
230 Search for mandatory following text node; for lookahead, the text must
231 follow but for lookbehind (rn->flags != 0) we skip to the next step.
233 #define FIND_NEXT_IMPT(rn) STMT_START { \
234 while (JUMPABLE(rn)) { \
235 const OPCODE type = OP(rn); \
236 if (type == SUSPEND || PL_regkind[type] == CURLY) \
237 rn = NEXTOPER(NEXTOPER(rn)); \
238 else if (type == PLUS) \
240 else if (type == IFMATCH) \
241 rn = (rn->flags == 0) ? NEXTOPER(NEXTOPER(rn)) : rn + ARG(rn); \
242 else rn += NEXT_OFF(rn); \
246 /* These constants are for finding GCB=LV and GCB=LVT in the CLUMP regnode.
247 * These are for the pre-composed Hangul syllables, which are all in a
248 * contiguous block and arranged there in such a way so as to facilitate
249 * alorithmic determination of their characteristics. As such, they don't need
250 * a swash, but can be determined by simple arithmetic. Almost all are
251 * GCB=LVT, but every 28th one is a GCB=LV */
252 #define SBASE 0xAC00 /* Start of block */
253 #define SCount 11172 /* Length of block */
256 static void restore_pos(pTHX_ void *arg);
258 #define REGCP_PAREN_ELEMS 3
259 #define REGCP_OTHER_ELEMS 3
260 #define REGCP_FRAME_ELEMS 1
261 /* REGCP_FRAME_ELEMS are not part of the REGCP_OTHER_ELEMS and
262 * are needed for the regexp context stack bookkeeping. */
265 S_regcppush(pTHX_ const regexp *rex, I32 parenfloor, U32 maxopenparen)
268 const int retval = PL_savestack_ix;
269 const int paren_elems_to_push =
270 (maxopenparen - parenfloor) * REGCP_PAREN_ELEMS;
271 const UV total_elems = paren_elems_to_push + REGCP_OTHER_ELEMS;
272 const UV elems_shifted = total_elems << SAVE_TIGHT_SHIFT;
274 GET_RE_DEBUG_FLAGS_DECL;
276 PERL_ARGS_ASSERT_REGCPPUSH;
278 if (paren_elems_to_push < 0)
279 Perl_croak(aTHX_ "panic: paren_elems_to_push, %i < 0",
280 paren_elems_to_push);
282 if ((elems_shifted >> SAVE_TIGHT_SHIFT) != total_elems)
283 Perl_croak(aTHX_ "panic: paren_elems_to_push offset %"UVuf
284 " out of range (%lu-%ld)",
286 (unsigned long)maxopenparen,
289 SSGROW(total_elems + REGCP_FRAME_ELEMS);
292 if ((int)maxopenparen > (int)parenfloor)
293 PerlIO_printf(Perl_debug_log,
294 "rex=0x%"UVxf" offs=0x%"UVxf": saving capture indices:\n",
299 for (p = parenfloor+1; p <= (I32)maxopenparen; p++) {
300 /* REGCP_PARENS_ELEMS are pushed per pairs of parentheses. */
301 SSPUSHINT(rex->offs[p].end);
302 SSPUSHINT(rex->offs[p].start);
303 SSPUSHINT(rex->offs[p].start_tmp);
304 DEBUG_BUFFERS_r(PerlIO_printf(Perl_debug_log,
305 " \\%"UVuf": %"IVdf"(%"IVdf")..%"IVdf"\n",
307 (IV)rex->offs[p].start,
308 (IV)rex->offs[p].start_tmp,
312 /* REGCP_OTHER_ELEMS are pushed in any case, parentheses or no. */
313 SSPUSHINT(maxopenparen);
314 SSPUSHINT(rex->lastparen);
315 SSPUSHINT(rex->lastcloseparen);
316 SSPUSHUV(SAVEt_REGCONTEXT | elems_shifted); /* Magic cookie. */
321 /* These are needed since we do not localize EVAL nodes: */
322 #define REGCP_SET(cp) \
324 PerlIO_printf(Perl_debug_log, \
325 " Setting an EVAL scope, savestack=%"IVdf"\n", \
326 (IV)PL_savestack_ix)); \
329 #define REGCP_UNWIND(cp) \
331 if (cp != PL_savestack_ix) \
332 PerlIO_printf(Perl_debug_log, \
333 " Clearing an EVAL scope, savestack=%"IVdf"..%"IVdf"\n", \
334 (IV)(cp), (IV)PL_savestack_ix)); \
337 #define UNWIND_PAREN(lp, lcp) \
338 for (n = rex->lastparen; n > lp; n--) \
339 rex->offs[n].end = -1; \
340 rex->lastparen = n; \
341 rex->lastcloseparen = lcp;
345 S_regcppop(pTHX_ regexp *rex, U32 *maxopenparen_p)
350 GET_RE_DEBUG_FLAGS_DECL;
352 PERL_ARGS_ASSERT_REGCPPOP;
354 /* Pop REGCP_OTHER_ELEMS before the parentheses loop starts. */
356 assert((i & SAVE_MASK) == SAVEt_REGCONTEXT); /* Check that the magic cookie is there. */
357 i >>= SAVE_TIGHT_SHIFT; /* Parentheses elements to pop. */
358 rex->lastcloseparen = SSPOPINT;
359 rex->lastparen = SSPOPINT;
360 *maxopenparen_p = SSPOPINT;
362 i -= REGCP_OTHER_ELEMS;
363 /* Now restore the parentheses context. */
365 if (i || rex->lastparen + 1 <= rex->nparens)
366 PerlIO_printf(Perl_debug_log,
367 "rex=0x%"UVxf" offs=0x%"UVxf": restoring capture indices to:\n",
372 paren = *maxopenparen_p;
373 for ( ; i > 0; i -= REGCP_PAREN_ELEMS) {
375 rex->offs[paren].start_tmp = SSPOPINT;
376 rex->offs[paren].start = SSPOPINT;
378 if (paren <= rex->lastparen)
379 rex->offs[paren].end = tmps;
380 DEBUG_BUFFERS_r( PerlIO_printf(Perl_debug_log,
381 " \\%"UVuf": %"IVdf"(%"IVdf")..%"IVdf"%s\n",
383 (IV)rex->offs[paren].start,
384 (IV)rex->offs[paren].start_tmp,
385 (IV)rex->offs[paren].end,
386 (paren > rex->lastparen ? "(skipped)" : ""));
391 /* It would seem that the similar code in regtry()
392 * already takes care of this, and in fact it is in
393 * a better location to since this code can #if 0-ed out
394 * but the code in regtry() is needed or otherwise tests
395 * requiring null fields (pat.t#187 and split.t#{13,14}
396 * (as of patchlevel 7877) will fail. Then again,
397 * this code seems to be necessary or otherwise
398 * this erroneously leaves $1 defined: "1" =~ /^(?:(\d)x)?\d$/
399 * --jhi updated by dapm */
400 for (i = rex->lastparen + 1; i <= rex->nparens; i++) {
401 if (i > *maxopenparen_p)
402 rex->offs[i].start = -1;
403 rex->offs[i].end = -1;
404 DEBUG_BUFFERS_r( PerlIO_printf(Perl_debug_log,
405 " \\%"UVuf": %s ..-1 undeffing\n",
407 (i > *maxopenparen_p) ? "-1" : " "
413 /* restore the parens and associated vars at savestack position ix,
414 * but without popping the stack */
417 S_regcp_restore(pTHX_ regexp *rex, I32 ix, U32 *maxopenparen_p)
419 I32 tmpix = PL_savestack_ix;
420 PL_savestack_ix = ix;
421 regcppop(rex, maxopenparen_p);
422 PL_savestack_ix = tmpix;
425 #define regcpblow(cp) LEAVE_SCOPE(cp) /* Ignores regcppush()ed data. */
428 S_isFOO_lc(pTHX_ const U8 classnum, const U8 character)
430 /* Returns a boolean as to whether or not 'character' is a member of the
431 * Posix character class given by 'classnum' that should be equivalent to a
432 * value in the typedef '_char_class_number'.
434 * Ideally this could be replaced by a just an array of function pointers
435 * to the C library functions that implement the macros this calls.
436 * However, to compile, the precise function signatures are required, and
437 * these may vary from platform to to platform. To avoid having to figure
438 * out what those all are on each platform, I (khw) am using this method,
439 * which adds an extra layer of function call overhead (unless the C
440 * optimizer strips it away). But we don't particularly care about
441 * performance with locales anyway. */
443 switch ((_char_class_number) classnum) {
444 case _CC_ENUM_ALPHANUMERIC: return isALPHANUMERIC_LC(character);
445 case _CC_ENUM_ALPHA: return isALPHA_LC(character);
446 case _CC_ENUM_DIGIT: return isDIGIT_LC(character);
447 case _CC_ENUM_GRAPH: return isGRAPH_LC(character);
448 case _CC_ENUM_LOWER: return isLOWER_LC(character);
449 case _CC_ENUM_PRINT: return isPRINT_LC(character);
450 case _CC_ENUM_PUNCT: return isPUNCT_LC(character);
451 case _CC_ENUM_UPPER: return isUPPER_LC(character);
452 case _CC_ENUM_WORDCHAR: return isWORDCHAR_LC(character);
453 case _CC_ENUM_SPACE: return isSPACE_LC(character);
454 case _CC_ENUM_BLANK: return isBLANK_LC(character);
455 case _CC_ENUM_XDIGIT: return isXDIGIT_LC(character);
456 case _CC_ENUM_CNTRL: return isCNTRL_LC(character);
457 case _CC_ENUM_PSXSPC: return isPSXSPC_LC(character);
458 case _CC_ENUM_ASCII: return isASCII_LC(character);
459 default: /* VERTSPACE should never occur in locales */
460 Perl_croak(aTHX_ "panic: isFOO_lc() has an unexpected character class '%d'", classnum);
463 assert(0); /* NOTREACHED */
468 S_isFOO_utf8_lc(pTHX_ const U8 classnum, const U8* character)
470 /* Returns a boolean as to whether or not the (well-formed) UTF-8-encoded
471 * 'character' is a member of the Posix character class given by 'classnum'
472 * that should be equivalent to a value in the typedef
473 * '_char_class_number'.
475 * This just calls isFOO_lc on the code point for the character if it is in
476 * the range 0-255. Outside that range, all characters avoid Unicode
477 * rules, ignoring any locale. So use the Unicode function if this class
478 * requires a swash, and use the Unicode macro otherwise. */
480 PERL_ARGS_ASSERT_ISFOO_UTF8_LC;
482 if (UTF8_IS_INVARIANT(*character)) {
483 return isFOO_lc(classnum, *character);
485 else if (UTF8_IS_DOWNGRADEABLE_START(*character)) {
486 return isFOO_lc(classnum,
487 TWO_BYTE_UTF8_TO_UNI(*character, *(character + 1)));
490 if (classnum < _FIRST_NON_SWASH_CC) {
492 /* Initialize the swash unless done already */
493 if (! PL_utf8_swash_ptrs[classnum]) {
494 U8 flags = _CORE_SWASH_INIT_ACCEPT_INVLIST;
495 PL_utf8_swash_ptrs[classnum] = _core_swash_init("utf8",
496 swash_property_names[classnum], &PL_sv_undef, 1, 0, NULL, &flags);
499 return swash_fetch(PL_utf8_swash_ptrs[classnum], (U8 *) character, TRUE);
502 switch ((_char_class_number) classnum) {
504 case _CC_ENUM_PSXSPC: return is_XPERLSPACE_high(character);
506 case _CC_ENUM_BLANK: return is_HORIZWS_high(character);
507 case _CC_ENUM_XDIGIT: return is_XDIGIT_high(character);
508 case _CC_ENUM_VERTSPACE: return is_VERTWS_high(character);
509 default: return 0; /* Things like CNTRL are always
513 assert(0); /* NOTREACHED */
518 * pregexec and friends
521 #ifndef PERL_IN_XSUB_RE
523 - pregexec - match a regexp against a string
526 Perl_pregexec(pTHX_ REGEXP * const prog, char* stringarg, char *strend,
527 char *strbeg, I32 minend, SV *screamer, U32 nosave)
528 /* stringarg: the point in the string at which to begin matching */
529 /* strend: pointer to null at end of string */
530 /* strbeg: real beginning of string */
531 /* minend: end of match must be >= minend bytes after stringarg. */
532 /* screamer: SV being matched: only used for utf8 flag, pos() etc; string
533 * itself is accessed via the pointers above */
534 /* nosave: For optimizations. */
536 PERL_ARGS_ASSERT_PREGEXEC;
539 regexec_flags(prog, stringarg, strend, strbeg, minend, screamer, NULL,
540 nosave ? 0 : REXEC_COPY_STR);
545 * Need to implement the following flags for reg_anch:
547 * USE_INTUIT_NOML - Useful to call re_intuit_start() first
549 * INTUIT_AUTORITATIVE_NOML - Can trust a positive answer
550 * INTUIT_AUTORITATIVE_ML
551 * INTUIT_ONCE_NOML - Intuit can match in one location only.
554 * Another flag for this function: SECOND_TIME (so that float substrs
555 * with giant delta may be not rechecked).
558 /* Assumptions: if ANCH_GPOS, then strpos is anchored. XXXX Check GPOS logic */
560 /* If SCREAM, then SvPVX_const(sv) should be compatible with strpos and strend.
561 Otherwise, only SvCUR(sv) is used to get strbeg. */
563 /* XXXX We assume that strpos is strbeg unless sv. */
565 /* XXXX Some places assume that there is a fixed substring.
566 An update may be needed if optimizer marks as "INTUITable"
567 RExen without fixed substrings. Similarly, it is assumed that
568 lengths of all the strings are no more than minlen, thus they
569 cannot come from lookahead.
570 (Or minlen should take into account lookahead.)
571 NOTE: Some of this comment is not correct. minlen does now take account
572 of lookahead/behind. Further research is required. -- demerphq
576 /* A failure to find a constant substring means that there is no need to make
577 an expensive call to REx engine, thus we celebrate a failure. Similarly,
578 finding a substring too deep into the string means that less calls to
579 regtry() should be needed.
581 REx compiler's optimizer found 4 possible hints:
582 a) Anchored substring;
584 c) Whether we are anchored (beginning-of-line or \G);
585 d) First node (of those at offset 0) which may distinguish positions;
586 We use a)b)d) and multiline-part of c), and try to find a position in the
587 string which does not contradict any of them.
590 /* Most of decisions we do here should have been done at compile time.
591 The nodes of the REx which we used for the search should have been
592 deleted from the finite automaton. */
595 Perl_re_intuit_start(pTHX_ REGEXP * const rx, SV *sv, char *strpos,
596 char *strend, const U32 flags, re_scream_pos_data *data)
599 struct regexp *const prog = ReANY(rx);
601 /* Should be nonnegative! */
607 const bool utf8_target = (sv && SvUTF8(sv)) ? 1 : 0; /* if no sv we have to assume bytes */
609 char *other_last = NULL; /* other substr checked before this */
610 char *check_at = NULL; /* check substr found at this pos */
611 char *checked_upto = NULL; /* how far into the string we have already checked using find_byclass*/
612 const I32 multiline = prog->extflags & RXf_PMf_MULTILINE;
613 RXi_GET_DECL(prog,progi);
615 const char * const i_strpos = strpos;
617 GET_RE_DEBUG_FLAGS_DECL;
619 PERL_ARGS_ASSERT_RE_INTUIT_START;
620 PERL_UNUSED_ARG(flags);
621 PERL_UNUSED_ARG(data);
623 RX_MATCH_UTF8_set(rx,utf8_target);
626 PL_reg_flags |= RF_utf8;
629 debug_start_match(rx, utf8_target, strpos, strend,
630 sv ? "Guessing start of match in sv for"
631 : "Guessing start of match in string for");
634 /* CHR_DIST() would be more correct here but it makes things slow. */
635 if (prog->minlen > strend - strpos) {
636 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
637 "String too short... [re_intuit_start]\n"));
641 /* XXX we need to pass strbeg as a separate arg: the following is
642 * guesswork and can be wrong... */
643 if (sv && SvPOK(sv)) {
644 char * p = SvPVX(sv);
645 STRLEN cur = SvCUR(sv);
646 if (p <= strpos && strpos < p + cur) {
648 assert(p <= strend && strend <= p + cur);
651 strbeg = strend - cur;
658 if (!prog->check_utf8 && prog->check_substr)
659 to_utf8_substr(prog);
660 check = prog->check_utf8;
662 if (!prog->check_substr && prog->check_utf8) {
663 if (! to_byte_substr(prog)) {
664 NON_UTF8_TARGET_BUT_UTF8_REQUIRED(fail);
667 check = prog->check_substr;
669 if (prog->extflags & RXf_ANCH) { /* Match at beg-of-str or after \n */
670 ml_anch = !( (prog->extflags & RXf_ANCH_SINGLE)
671 || ( (prog->extflags & RXf_ANCH_BOL)
672 && !multiline ) ); /* Check after \n? */
675 if ( !(prog->extflags & RXf_ANCH_GPOS) /* Checked by the caller */
676 && !(prog->intflags & PREGf_IMPLICIT) /* not a real BOL */
677 /* SvCUR is not set on references: SvRV and SvPVX_const overlap */
679 && (strpos != strbeg)) {
680 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "Not at start...\n"));
683 if (prog->check_offset_min == prog->check_offset_max
684 && !(prog->extflags & RXf_CANY_SEEN)
685 && ! multiline) /* /m can cause \n's to match that aren't
686 accounted for in the string max length.
687 See [perl #115242] */
689 /* Substring at constant offset from beg-of-str... */
692 s = HOP3c(strpos, prog->check_offset_min, strend);
695 slen = SvCUR(check); /* >= 1 */
697 if ( strend - s > slen || strend - s < slen - 1
698 || (strend - s == slen && strend[-1] != '\n')) {
699 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "String too long...\n"));
702 /* Now should match s[0..slen-2] */
704 if (slen && (*SvPVX_const(check) != *s
706 && memNE(SvPVX_const(check), s, slen)))) {
708 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "String not equal...\n"));
712 else if (*SvPVX_const(check) != *s
713 || ((slen = SvCUR(check)) > 1
714 && memNE(SvPVX_const(check), s, slen)))
717 goto success_at_start;
720 /* Match is anchored, but substr is not anchored wrt beg-of-str. */
722 start_shift = prog->check_offset_min; /* okay to underestimate on CC */
723 end_shift = prog->check_end_shift;
726 const I32 end = prog->check_offset_max + CHR_SVLEN(check)
727 - (SvTAIL(check) != 0);
728 const I32 eshift = CHR_DIST((U8*)strend, (U8*)s) - end;
730 if (end_shift < eshift)
734 else { /* Can match at random position */
737 start_shift = prog->check_offset_min; /* okay to underestimate on CC */
738 end_shift = prog->check_end_shift;
740 /* end shift should be non negative here */
743 #ifdef QDEBUGGING /* 7/99: reports of failure (with the older version) */
745 Perl_croak(aTHX_ "panic: end_shift: %"IVdf" pattern:\n%s\n ",
746 (IV)end_shift, RX_PRECOMP(prog));
750 /* Find a possible match in the region s..strend by looking for
751 the "check" substring in the region corrected by start/end_shift. */
754 I32 srch_start_shift = start_shift;
755 I32 srch_end_shift = end_shift;
758 if (srch_start_shift < 0 && strbeg - s > srch_start_shift) {
759 srch_end_shift -= ((strbeg - s) - srch_start_shift);
760 srch_start_shift = strbeg - s;
762 DEBUG_OPTIMISE_MORE_r({
763 PerlIO_printf(Perl_debug_log, "Check offset min: %"IVdf" Start shift: %"IVdf" End shift %"IVdf" Real End Shift: %"IVdf"\n",
764 (IV)prog->check_offset_min,
765 (IV)srch_start_shift,
767 (IV)prog->check_end_shift);
770 if (prog->extflags & RXf_CANY_SEEN) {
771 start_point= (U8*)(s + srch_start_shift);
772 end_point= (U8*)(strend - srch_end_shift);
774 start_point= HOP3(s, srch_start_shift, srch_start_shift < 0 ? strbeg : strend);
775 end_point= HOP3(strend, -srch_end_shift, strbeg);
777 DEBUG_OPTIMISE_MORE_r({
778 PerlIO_printf(Perl_debug_log, "fbm_instr len=%d str=<%.*s>\n",
779 (int)(end_point - start_point),
780 (int)(end_point - start_point) > 20 ? 20 : (int)(end_point - start_point),
784 s = fbm_instr( start_point, end_point,
785 check, multiline ? FBMrf_MULTILINE : 0);
787 /* Update the count-of-usability, remove useless subpatterns,
791 RE_PV_QUOTED_DECL(quoted, utf8_target, PERL_DEBUG_PAD_ZERO(0),
792 SvPVX_const(check), RE_SV_DUMPLEN(check), 30);
793 PerlIO_printf(Perl_debug_log, "%s %s substr %s%s%s",
794 (s ? "Found" : "Did not find"),
795 (check == (utf8_target ? prog->anchored_utf8 : prog->anchored_substr)
796 ? "anchored" : "floating"),
799 (s ? " at offset " : "...\n") );
804 /* Finish the diagnostic message */
805 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "%ld...\n", (long)(s - i_strpos)) );
807 /* XXX dmq: first branch is for positive lookbehind...
808 Our check string is offset from the beginning of the pattern.
809 So we need to do any stclass tests offset forward from that
818 /* Got a candidate. Check MBOL anchoring, and the *other* substr.
819 Start with the other substr.
820 XXXX no SCREAM optimization yet - and a very coarse implementation
821 XXXX /ttx+/ results in anchored="ttx", floating="x". floating will
822 *always* match. Probably should be marked during compile...
823 Probably it is right to do no SCREAM here...
826 if (utf8_target ? (prog->float_utf8 && prog->anchored_utf8)
827 : (prog->float_substr && prog->anchored_substr))
829 /* Take into account the "other" substring. */
830 /* XXXX May be hopelessly wrong for UTF... */
833 if (check == (utf8_target ? prog->float_utf8 : prog->float_substr)) {
836 char * const last = HOP3c(s, -start_shift, strbeg);
838 char * const saved_s = s;
841 t = s - prog->check_offset_max;
842 if (s - strpos > prog->check_offset_max /* signed-corrected t > strpos */
844 || ((t = (char*)reghopmaybe3((U8*)s, -(prog->check_offset_max), (U8*)strpos))
849 t = HOP3c(t, prog->anchored_offset, strend);
850 if (t < other_last) /* These positions already checked */
852 last2 = last1 = HOP3c(strend, -prog->minlen, strbeg);
855 /* XXXX It is not documented what units *_offsets are in.
856 We assume bytes, but this is clearly wrong.
857 Meaning this code needs to be carefully reviewed for errors.
861 /* On end-of-str: see comment below. */
862 must = utf8_target ? prog->anchored_utf8 : prog->anchored_substr;
863 if (must == &PL_sv_undef) {
865 DEBUG_r(must = prog->anchored_utf8); /* for debug */
870 HOP3(HOP3(last1, prog->anchored_offset, strend)
871 + SvCUR(must), -(SvTAIL(must)!=0), strbeg),
873 multiline ? FBMrf_MULTILINE : 0
876 RE_PV_QUOTED_DECL(quoted, utf8_target, PERL_DEBUG_PAD_ZERO(0),
877 SvPVX_const(must), RE_SV_DUMPLEN(must), 30);
878 PerlIO_printf(Perl_debug_log, "%s anchored substr %s%s",
879 (s ? "Found" : "Contradicts"),
880 quoted, RE_SV_TAIL(must));
885 if (last1 >= last2) {
886 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
887 ", giving up...\n"));
890 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
891 ", trying floating at offset %ld...\n",
892 (long)(HOP3c(saved_s, 1, strend) - i_strpos)));
893 other_last = HOP3c(last1, prog->anchored_offset+1, strend);
894 s = HOP3c(last, 1, strend);
898 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, " at offset %ld...\n",
899 (long)(s - i_strpos)));
900 t = HOP3c(s, -prog->anchored_offset, strbeg);
901 other_last = HOP3c(s, 1, strend);
909 else { /* Take into account the floating substring. */
911 char * const saved_s = s;
914 t = HOP3c(s, -start_shift, strbeg);
916 HOP3c(strend, -prog->minlen + prog->float_min_offset, strbeg);
917 if (CHR_DIST((U8*)last, (U8*)t) > prog->float_max_offset)
918 last = HOP3c(t, prog->float_max_offset, strend);
919 s = HOP3c(t, prog->float_min_offset, strend);
922 /* XXXX It is not documented what units *_offsets are in. Assume bytes. */
923 must = utf8_target ? prog->float_utf8 : prog->float_substr;
924 /* fbm_instr() takes into account exact value of end-of-str
925 if the check is SvTAIL(ed). Since false positives are OK,
926 and end-of-str is not later than strend we are OK. */
927 if (must == &PL_sv_undef) {
929 DEBUG_r(must = prog->float_utf8); /* for debug message */
932 s = fbm_instr((unsigned char*)s,
933 (unsigned char*)last + SvCUR(must)
935 must, multiline ? FBMrf_MULTILINE : 0);
937 RE_PV_QUOTED_DECL(quoted, utf8_target, PERL_DEBUG_PAD_ZERO(0),
938 SvPVX_const(must), RE_SV_DUMPLEN(must), 30);
939 PerlIO_printf(Perl_debug_log, "%s floating substr %s%s",
940 (s ? "Found" : "Contradicts"),
941 quoted, RE_SV_TAIL(must));
945 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
946 ", giving up...\n"));
949 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
950 ", trying anchored starting at offset %ld...\n",
951 (long)(saved_s + 1 - i_strpos)));
953 s = HOP3c(t, 1, strend);
957 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, " at offset %ld...\n",
958 (long)(s - i_strpos)));
959 other_last = s; /* Fix this later. --Hugo */
969 t= (char*)HOP3( s, -prog->check_offset_max, (prog->check_offset_max<0) ? strend : strpos);
971 DEBUG_OPTIMISE_MORE_r(
972 PerlIO_printf(Perl_debug_log,
973 "Check offset min:%"IVdf" max:%"IVdf" S:%"IVdf" t:%"IVdf" D:%"IVdf" end:%"IVdf"\n",
974 (IV)prog->check_offset_min,
975 (IV)prog->check_offset_max,
983 if (s - strpos > prog->check_offset_max /* signed-corrected t > strpos */
985 || ((t = (char*)reghopmaybe3((U8*)s, -prog->check_offset_max, (U8*) ((prog->check_offset_max<0) ? strend : strpos)))
988 /* Fixed substring is found far enough so that the match
989 cannot start at strpos. */
991 if (ml_anch && t[-1] != '\n') {
992 /* Eventually fbm_*() should handle this, but often
993 anchored_offset is not 0, so this check will not be wasted. */
994 /* XXXX In the code below we prefer to look for "^" even in
995 presence of anchored substrings. And we search even
996 beyond the found float position. These pessimizations
997 are historical artefacts only. */
999 while (t < strend - prog->minlen) {
1001 if (t < check_at - prog->check_offset_min) {
1002 if (utf8_target ? prog->anchored_utf8 : prog->anchored_substr) {
1003 /* Since we moved from the found position,
1004 we definitely contradict the found anchored
1005 substr. Due to the above check we do not
1006 contradict "check" substr.
1007 Thus we can arrive here only if check substr
1008 is float. Redo checking for "other"=="fixed".
1011 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "Found /%s^%s/m at offset %ld, rescanning for anchored from offset %ld...\n",
1012 PL_colors[0], PL_colors[1], (long)(strpos - i_strpos), (long)(strpos - i_strpos + prog->anchored_offset)));
1013 goto do_other_anchored;
1015 /* We don't contradict the found floating substring. */
1016 /* XXXX Why not check for STCLASS? */
1018 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "Found /%s^%s/m at offset %ld...\n",
1019 PL_colors[0], PL_colors[1], (long)(s - i_strpos)));
1022 /* Position contradicts check-string */
1023 /* XXXX probably better to look for check-string
1024 than for "\n", so one should lower the limit for t? */
1025 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "Found /%s^%s/m, restarting lookup for check-string at offset %ld...\n",
1026 PL_colors[0], PL_colors[1], (long)(t + 1 - i_strpos)));
1027 other_last = strpos = s = t + 1;
1032 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "Did not find /%s^%s/m...\n",
1033 PL_colors[0], PL_colors[1]));
1037 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "Starting position does not contradict /%s^%s/m...\n",
1038 PL_colors[0], PL_colors[1]));
1042 ++BmUSEFUL(utf8_target ? prog->check_utf8 : prog->check_substr); /* hooray/5 */
1045 /* The found string does not prohibit matching at strpos,
1046 - no optimization of calling REx engine can be performed,
1047 unless it was an MBOL and we are not after MBOL,
1048 or a future STCLASS check will fail this. */
1050 /* Even in this situation we may use MBOL flag if strpos is offset
1051 wrt the start of the string. */
1052 if (ml_anch && sv && !SvROK(sv) /* See prev comment on SvROK */
1053 && (strpos != strbeg) && strpos[-1] != '\n'
1054 /* May be due to an implicit anchor of m{.*foo} */
1055 && !(prog->intflags & PREGf_IMPLICIT))
1060 DEBUG_EXECUTE_r( if (ml_anch)
1061 PerlIO_printf(Perl_debug_log, "Position at offset %ld does not contradict /%s^%s/m...\n",
1062 (long)(strpos - i_strpos), PL_colors[0], PL_colors[1]);
1065 if (!(prog->intflags & PREGf_NAUGHTY) /* XXXX If strpos moved? */
1067 prog->check_utf8 /* Could be deleted already */
1068 && --BmUSEFUL(prog->check_utf8) < 0
1069 && (prog->check_utf8 == prog->float_utf8)
1071 prog->check_substr /* Could be deleted already */
1072 && --BmUSEFUL(prog->check_substr) < 0
1073 && (prog->check_substr == prog->float_substr)
1076 /* If flags & SOMETHING - do not do it many times on the same match */
1077 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "... Disabling check substring...\n"));
1078 /* XXX Does the destruction order has to change with utf8_target? */
1079 SvREFCNT_dec(utf8_target ? prog->check_utf8 : prog->check_substr);
1080 SvREFCNT_dec(utf8_target ? prog->check_substr : prog->check_utf8);
1081 prog->check_substr = prog->check_utf8 = NULL; /* disable */
1082 prog->float_substr = prog->float_utf8 = NULL; /* clear */
1083 check = NULL; /* abort */
1085 /* XXXX If the check string was an implicit check MBOL, then we need to unset the relevant flag
1086 see http://bugs.activestate.com/show_bug.cgi?id=87173 */
1087 if (prog->intflags & PREGf_IMPLICIT)
1088 prog->extflags &= ~RXf_ANCH_MBOL;
1089 /* XXXX This is a remnant of the old implementation. It
1090 looks wasteful, since now INTUIT can use many
1091 other heuristics. */
1092 prog->extflags &= ~RXf_USE_INTUIT;
1093 /* XXXX What other flags might need to be cleared in this branch? */
1099 /* Last resort... */
1100 /* XXXX BmUSEFUL already changed, maybe multiple change is meaningful... */
1101 /* trie stclasses are too expensive to use here, we are better off to
1102 leave it to regmatch itself */
1103 if (progi->regstclass && PL_regkind[OP(progi->regstclass)]!=TRIE) {
1104 /* minlen == 0 is possible if regstclass is \b or \B,
1105 and the fixed substr is ''$.
1106 Since minlen is already taken into account, s+1 is before strend;
1107 accidentally, minlen >= 1 guaranties no false positives at s + 1
1108 even for \b or \B. But (minlen? 1 : 0) below assumes that
1109 regstclass does not come from lookahead... */
1110 /* If regstclass takes bytelength more than 1: If charlength==1, OK.
1111 This leaves EXACTF-ish only, which are dealt with in find_byclass(). */
1112 const U8* const str = (U8*)STRING(progi->regstclass);
1113 const int cl_l = (PL_regkind[OP(progi->regstclass)] == EXACT
1114 ? CHR_DIST(str+STR_LEN(progi->regstclass), str)
1117 if (prog->anchored_substr || prog->anchored_utf8 || ml_anch)
1118 endpos= HOP3c(s, (prog->minlen ? cl_l : 0), strend);
1119 else if (prog->float_substr || prog->float_utf8)
1120 endpos= HOP3c(HOP3c(check_at, -start_shift, strbeg), cl_l, strend);
1124 if (checked_upto < s)
1126 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "start_shift: %"IVdf" check_at: %"IVdf" s: %"IVdf" endpos: %"IVdf" checked_upto: %"IVdf"\n",
1127 (IV)start_shift, (IV)(check_at - strbeg), (IV)(s - strbeg), (IV)(endpos - strbeg), (IV)(checked_upto- strbeg)));
1130 s = find_byclass(prog, progi->regstclass, checked_upto, endpos, NULL);
1135 const char *what = NULL;
1137 if (endpos == strend) {
1138 DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log,
1139 "Could not match STCLASS...\n") );
1142 DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log,
1143 "This position contradicts STCLASS...\n") );
1144 if ((prog->extflags & RXf_ANCH) && !ml_anch)
1146 checked_upto = HOPBACKc(endpos, start_shift);
1147 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "start_shift: %"IVdf" check_at: %"IVdf" endpos: %"IVdf" checked_upto: %"IVdf"\n",
1148 (IV)start_shift, (IV)(check_at - strbeg), (IV)(endpos - strbeg), (IV)(checked_upto- strbeg)));
1149 /* Contradict one of substrings */
1150 if (prog->anchored_substr || prog->anchored_utf8) {
1151 if ((utf8_target ? prog->anchored_utf8 : prog->anchored_substr) == check) {
1152 DEBUG_EXECUTE_r( what = "anchored" );
1154 s = HOP3c(t, 1, strend);
1155 if (s + start_shift + end_shift > strend) {
1156 /* XXXX Should be taken into account earlier? */
1157 DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log,
1158 "Could not match STCLASS...\n") );
1163 DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log,
1164 "Looking for %s substr starting at offset %ld...\n",
1165 what, (long)(s + start_shift - i_strpos)) );
1168 /* Have both, check_string is floating */
1169 if (t + start_shift >= check_at) /* Contradicts floating=check */
1170 goto retry_floating_check;
1171 /* Recheck anchored substring, but not floating... */
1175 DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log,
1176 "Looking for anchored substr starting at offset %ld...\n",
1177 (long)(other_last - i_strpos)) );
1178 goto do_other_anchored;
1180 /* Another way we could have checked stclass at the
1181 current position only: */
1186 DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log,
1187 "Looking for /%s^%s/m starting at offset %ld...\n",
1188 PL_colors[0], PL_colors[1], (long)(t - i_strpos)) );
1191 if (!(utf8_target ? prog->float_utf8 : prog->float_substr)) /* Could have been deleted */
1193 /* Check is floating substring. */
1194 retry_floating_check:
1195 t = check_at - start_shift;
1196 DEBUG_EXECUTE_r( what = "floating" );
1197 goto hop_and_restart;
1200 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
1201 "By STCLASS: moving %ld --> %ld\n",
1202 (long)(t - i_strpos), (long)(s - i_strpos))
1206 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
1207 "Does not contradict STCLASS...\n");
1212 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "%s%s:%s match at offset %ld\n",
1213 PL_colors[4], (check ? "Guessed" : "Giving up"),
1214 PL_colors[5], (long)(s - i_strpos)) );
1217 fail_finish: /* Substring not found */
1218 if (prog->check_substr || prog->check_utf8) /* could be removed already */
1219 BmUSEFUL(utf8_target ? prog->check_utf8 : prog->check_substr) += 5; /* hooray */
1221 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "%sMatch rejected by optimizer%s\n",
1222 PL_colors[4], PL_colors[5]));
1226 #define DECL_TRIE_TYPE(scan) \
1227 const enum { trie_plain, trie_utf8, trie_utf8_fold, trie_latin_utf8_fold } \
1228 trie_type = ((scan->flags == EXACT) \
1229 ? (utf8_target ? trie_utf8 : trie_plain) \
1230 : (utf8_target ? trie_utf8_fold : trie_latin_utf8_fold))
1232 #define REXEC_TRIE_READ_CHAR(trie_type, trie, widecharmap, uc, uscan, len, \
1233 uvc, charid, foldlen, foldbuf, uniflags) STMT_START { \
1235 switch (trie_type) { \
1236 case trie_utf8_fold: \
1237 if ( foldlen>0 ) { \
1238 uvc = utf8n_to_uvuni( (const U8*) uscan, UTF8_MAXLEN, &len, uniflags ); \
1243 uvc = to_utf8_fold( (const U8*) uc, foldbuf, &foldlen ); \
1244 len = UTF8SKIP(uc); \
1245 skiplen = UNISKIP( uvc ); \
1246 foldlen -= skiplen; \
1247 uscan = foldbuf + skiplen; \
1250 case trie_latin_utf8_fold: \
1251 if ( foldlen>0 ) { \
1252 uvc = utf8n_to_uvuni( (const U8*) uscan, UTF8_MAXLEN, &len, uniflags ); \
1258 uvc = _to_fold_latin1( (U8) *uc, foldbuf, &foldlen, 1); \
1259 skiplen = UNISKIP( uvc ); \
1260 foldlen -= skiplen; \
1261 uscan = foldbuf + skiplen; \
1265 uvc = utf8n_to_uvuni( (const U8*) uc, UTF8_MAXLEN, &len, uniflags ); \
1272 charid = trie->charmap[ uvc ]; \
1276 if (widecharmap) { \
1277 SV** const svpp = hv_fetch(widecharmap, \
1278 (char*)&uvc, sizeof(UV), 0); \
1280 charid = (U16)SvIV(*svpp); \
1285 #define REXEC_FBC_EXACTISH_SCAN(CoNd) \
1289 && (ln == 1 || folder(s, pat_string, ln)) \
1290 && (!reginfo || regtry(reginfo, &s)) ) \
1296 #define REXEC_FBC_UTF8_SCAN(CoDe) \
1298 while (s < strend) { \
1304 #define REXEC_FBC_SCAN(CoDe) \
1306 while (s < strend) { \
1312 #define REXEC_FBC_UTF8_CLASS_SCAN(CoNd) \
1313 REXEC_FBC_UTF8_SCAN( \
1315 if (tmp && (!reginfo || regtry(reginfo, &s))) \
1324 #define REXEC_FBC_CLASS_SCAN(CoNd) \
1327 if (tmp && (!reginfo || regtry(reginfo, &s))) \
1336 #define REXEC_FBC_TRYIT \
1337 if ((!reginfo || regtry(reginfo, &s))) \
1340 #define REXEC_FBC_CSCAN(CoNdUtF8,CoNd) \
1341 if (utf8_target) { \
1342 REXEC_FBC_UTF8_CLASS_SCAN(CoNdUtF8); \
1345 REXEC_FBC_CLASS_SCAN(CoNd); \
1348 #define DUMP_EXEC_POS(li,s,doutf8) \
1349 dump_exec_pos(li,s,(PL_regeol),(PL_bostr),(PL_reg_starttry),doutf8)
1352 #define UTF8_NOLOAD(TEST_NON_UTF8, IF_SUCCESS, IF_FAIL) \
1353 tmp = (s != PL_bostr) ? UCHARAT(s - 1) : '\n'; \
1354 tmp = TEST_NON_UTF8(tmp); \
1355 REXEC_FBC_UTF8_SCAN( \
1356 if (tmp == ! TEST_NON_UTF8((U8) *s)) { \
1365 #define UTF8_LOAD(TeSt1_UtF8, TeSt2_UtF8, IF_SUCCESS, IF_FAIL) \
1366 if (s == PL_bostr) { \
1370 U8 * const r = reghop3((U8*)s, -1, (U8*)PL_bostr); \
1371 tmp = utf8n_to_uvchr(r, UTF8SKIP(r), 0, UTF8_ALLOW_DEFAULT); \
1374 LOAD_UTF8_CHARCLASS_ALNUM(); \
1375 REXEC_FBC_UTF8_SCAN( \
1376 if (tmp == ! (TeSt2_UtF8)) { \
1385 /* The only difference between the BOUND and NBOUND cases is that
1386 * REXEC_FBC_TRYIT is called when matched in BOUND, and when non-matched in
1387 * NBOUND. This is accomplished by passing it in either the if or else clause,
1388 * with the other one being empty */
1389 #define FBC_BOUND(TEST_NON_UTF8, TEST1_UTF8, TEST2_UTF8) \
1390 FBC_BOUND_COMMON(UTF8_LOAD(TEST1_UTF8, TEST2_UTF8, REXEC_FBC_TRYIT, PLACEHOLDER), TEST_NON_UTF8, REXEC_FBC_TRYIT, PLACEHOLDER)
1392 #define FBC_BOUND_NOLOAD(TEST_NON_UTF8, TEST1_UTF8, TEST2_UTF8) \
1393 FBC_BOUND_COMMON(UTF8_NOLOAD(TEST_NON_UTF8, REXEC_FBC_TRYIT, PLACEHOLDER), TEST_NON_UTF8, REXEC_FBC_TRYIT, PLACEHOLDER)
1395 #define FBC_NBOUND(TEST_NON_UTF8, TEST1_UTF8, TEST2_UTF8) \
1396 FBC_BOUND_COMMON(UTF8_LOAD(TEST1_UTF8, TEST2_UTF8, PLACEHOLDER, REXEC_FBC_TRYIT), TEST_NON_UTF8, PLACEHOLDER, REXEC_FBC_TRYIT)
1398 #define FBC_NBOUND_NOLOAD(TEST_NON_UTF8, TEST1_UTF8, TEST2_UTF8) \
1399 FBC_BOUND_COMMON(UTF8_NOLOAD(TEST_NON_UTF8, PLACEHOLDER, REXEC_FBC_TRYIT), TEST_NON_UTF8, PLACEHOLDER, REXEC_FBC_TRYIT)
1402 /* Common to the BOUND and NBOUND cases. Unfortunately the UTF8 tests need to
1403 * be passed in completely with the variable name being tested, which isn't
1404 * such a clean interface, but this is easier to read than it was before. We
1405 * are looking for the boundary (or non-boundary between a word and non-word
1406 * character. The utf8 and non-utf8 cases have the same logic, but the details
1407 * must be different. Find the "wordness" of the character just prior to this
1408 * one, and compare it with the wordness of this one. If they differ, we have
1409 * a boundary. At the beginning of the string, pretend that the previous
1410 * character was a new-line */
1411 #define FBC_BOUND_COMMON(UTF8_CODE, TEST_NON_UTF8, IF_SUCCESS, IF_FAIL) \
1412 if (utf8_target) { \
1415 else { /* Not utf8 */ \
1416 tmp = (s != PL_bostr) ? UCHARAT(s - 1) : '\n'; \
1417 tmp = TEST_NON_UTF8(tmp); \
1419 if (tmp == ! TEST_NON_UTF8((U8) *s)) { \
1428 if ((!prog->minlen && tmp) && (!reginfo || regtry(reginfo, &s))) \
1431 /* We know what class REx starts with. Try to find this position... */
1432 /* if reginfo is NULL, its a dryrun */
1433 /* annoyingly all the vars in this routine have different names from their counterparts
1434 in regmatch. /grrr */
1437 S_find_byclass(pTHX_ regexp * prog, const regnode *c, char *s,
1438 const char *strend, regmatch_info *reginfo)
1441 const I32 doevery = (prog->intflags & PREGf_SKIP) == 0;
1442 char *pat_string; /* The pattern's exactish string */
1443 char *pat_end; /* ptr to end char of pat_string */
1444 re_fold_t folder; /* Function for computing non-utf8 folds */
1445 const U8 *fold_array; /* array for folding ords < 256 */
1451 I32 tmp = 1; /* Scratch variable? */
1452 const bool utf8_target = PL_reg_match_utf8;
1453 UV utf8_fold_flags = 0;
1454 bool to_complement = FALSE; /* Invert the result? Taking the xor of this
1455 with a result inverts that result, as 0^1 =
1457 _char_class_number classnum;
1459 RXi_GET_DECL(prog,progi);
1461 PERL_ARGS_ASSERT_FIND_BYCLASS;
1463 /* We know what class it must start with. */
1467 REXEC_FBC_UTF8_CLASS_SCAN(
1468 reginclass(prog, c, (U8*)s, utf8_target));
1471 REXEC_FBC_CLASS_SCAN(REGINCLASS(prog, c, (U8*)s));
1476 if (tmp && (!reginfo || regtry(reginfo, &s)))
1484 if (UTF_PATTERN || utf8_target) {
1485 utf8_fold_flags = FOLDEQ_UTF8_NOMIX_ASCII;
1486 goto do_exactf_utf8;
1488 fold_array = PL_fold_latin1; /* Latin1 folds are not affected by */
1489 folder = foldEQ_latin1; /* /a, except the sharp s one which */
1490 goto do_exactf_non_utf8; /* isn't dealt with by these */
1495 /* regcomp.c already folded this if pattern is in UTF-8 */
1496 utf8_fold_flags = 0;
1497 goto do_exactf_utf8;
1499 fold_array = PL_fold;
1501 goto do_exactf_non_utf8;
1504 if (UTF_PATTERN || utf8_target) {
1505 utf8_fold_flags = FOLDEQ_UTF8_LOCALE;
1506 goto do_exactf_utf8;
1508 fold_array = PL_fold_locale;
1509 folder = foldEQ_locale;
1510 goto do_exactf_non_utf8;
1514 utf8_fold_flags = FOLDEQ_S2_ALREADY_FOLDED;
1516 goto do_exactf_utf8;
1518 case EXACTFU_TRICKYFOLD:
1520 if (UTF_PATTERN || utf8_target) {
1521 utf8_fold_flags = (UTF_PATTERN) ? FOLDEQ_S2_ALREADY_FOLDED : 0;
1522 goto do_exactf_utf8;
1525 /* Any 'ss' in the pattern should have been replaced by regcomp,
1526 * so we don't have to worry here about this single special case
1527 * in the Latin1 range */
1528 fold_array = PL_fold_latin1;
1529 folder = foldEQ_latin1;
1533 do_exactf_non_utf8: /* Neither pattern nor string are UTF8, and there
1534 are no glitches with fold-length differences
1535 between the target string and pattern */
1537 /* The idea in the non-utf8 EXACTF* cases is to first find the
1538 * first character of the EXACTF* node and then, if necessary,
1539 * case-insensitively compare the full text of the node. c1 is the
1540 * first character. c2 is its fold. This logic will not work for
1541 * Unicode semantics and the german sharp ss, which hence should
1542 * not be compiled into a node that gets here. */
1543 pat_string = STRING(c);
1544 ln = STR_LEN(c); /* length to match in octets/bytes */
1546 /* We know that we have to match at least 'ln' bytes (which is the
1547 * same as characters, since not utf8). If we have to match 3
1548 * characters, and there are only 2 availabe, we know without
1549 * trying that it will fail; so don't start a match past the
1550 * required minimum number from the far end */
1551 e = HOP3c(strend, -((I32)ln), s);
1553 if (!reginfo && e < s) {
1554 e = s; /* Due to minlen logic of intuit() */
1558 c2 = fold_array[c1];
1559 if (c1 == c2) { /* If char and fold are the same */
1560 REXEC_FBC_EXACTISH_SCAN(*(U8*)s == c1);
1563 REXEC_FBC_EXACTISH_SCAN(*(U8*)s == c1 || *(U8*)s == c2);
1571 /* If one of the operands is in utf8, we can't use the simpler folding
1572 * above, due to the fact that many different characters can have the
1573 * same fold, or portion of a fold, or different- length fold */
1574 pat_string = STRING(c);
1575 ln = STR_LEN(c); /* length to match in octets/bytes */
1576 pat_end = pat_string + ln;
1577 lnc = (UTF_PATTERN) /* length to match in characters */
1578 ? utf8_length((U8 *) pat_string, (U8 *) pat_end)
1581 /* We have 'lnc' characters to match in the pattern, but because of
1582 * multi-character folding, each character in the target can match
1583 * up to 3 characters (Unicode guarantees it will never exceed
1584 * this) if it is utf8-encoded; and up to 2 if not (based on the
1585 * fact that the Latin 1 folds are already determined, and the
1586 * only multi-char fold in that range is the sharp-s folding to
1587 * 'ss'. Thus, a pattern character can match as little as 1/3 of a
1588 * string character. Adjust lnc accordingly, rounding up, so that
1589 * if we need to match at least 4+1/3 chars, that really is 5. */
1590 expansion = (utf8_target) ? UTF8_MAX_FOLD_CHAR_EXPAND : 2;
1591 lnc = (lnc + expansion - 1) / expansion;
1593 /* As in the non-UTF8 case, if we have to match 3 characters, and
1594 * only 2 are left, it's guaranteed to fail, so don't start a
1595 * match that would require us to go beyond the end of the string
1597 e = HOP3c(strend, -((I32)lnc), s);
1599 if (!reginfo && e < s) {
1600 e = s; /* Due to minlen logic of intuit() */
1603 /* XXX Note that we could recalculate e to stop the loop earlier,
1604 * as the worst case expansion above will rarely be met, and as we
1605 * go along we would usually find that e moves further to the left.
1606 * This would happen only after we reached the point in the loop
1607 * where if there were no expansion we should fail. Unclear if
1608 * worth the expense */
1611 char *my_strend= (char *)strend;
1612 if (foldEQ_utf8_flags(s, &my_strend, 0, utf8_target,
1613 pat_string, NULL, ln, cBOOL(UTF_PATTERN), utf8_fold_flags)
1614 && (!reginfo || regtry(reginfo, &s)) )
1618 s += (utf8_target) ? UTF8SKIP(s) : 1;
1623 PL_reg_flags |= RF_tainted;
1624 FBC_BOUND(isALNUM_LC,
1625 isALNUM_LC_uvchr(UNI_TO_NATIVE(tmp)),
1626 isALNUM_LC_utf8((U8*)s));
1629 PL_reg_flags |= RF_tainted;
1630 FBC_NBOUND(isALNUM_LC,
1631 isALNUM_LC_uvchr(UNI_TO_NATIVE(tmp)),
1632 isALNUM_LC_utf8((U8*)s));
1635 FBC_BOUND(isWORDCHAR,
1637 cBOOL(swash_fetch(PL_utf8_swash_ptrs[_CC_WORDCHAR], (U8*)s, utf8_target)));
1640 FBC_BOUND_NOLOAD(isWORDCHAR_A,
1642 isWORDCHAR_A((U8*)s));
1645 FBC_NBOUND(isWORDCHAR,
1647 cBOOL(swash_fetch(PL_utf8_swash_ptrs[_CC_WORDCHAR], (U8*)s, utf8_target)));
1650 FBC_NBOUND_NOLOAD(isWORDCHAR_A,
1652 isWORDCHAR_A((U8*)s));
1655 FBC_BOUND(isWORDCHAR_L1,
1657 cBOOL(swash_fetch(PL_utf8_swash_ptrs[_CC_WORDCHAR], (U8*)s, utf8_target)));
1660 FBC_NBOUND(isWORDCHAR_L1,
1662 cBOOL(swash_fetch(PL_utf8_swash_ptrs[_CC_WORDCHAR], (U8*)s, utf8_target)));
1665 REXEC_FBC_CSCAN(is_LNBREAK_utf8_safe(s, strend),
1666 is_LNBREAK_latin1_safe(s, strend)
1670 /* The argument to all the POSIX node types is the class number to pass to
1671 * _generic_isCC() to build a mask for searching in PL_charclass[] */
1678 PL_reg_flags |= RF_tainted;
1679 REXEC_FBC_CSCAN(to_complement ^ cBOOL(isFOO_utf8_lc(FLAGS(c), (U8 *) s)),
1680 to_complement ^ cBOOL(isFOO_lc(FLAGS(c), *s)));
1695 /* The complement of something that matches only ASCII matches all
1696 * UTF-8 variant code points, plus everything in ASCII that isn't
1698 REXEC_FBC_UTF8_CLASS_SCAN(! UTF8_IS_INVARIANT(*s)
1699 || ! _generic_isCC_A(*s, FLAGS(c)));
1708 /* Don't need to worry about utf8, as it can match only a single
1709 * byte invariant character. */
1710 REXEC_FBC_CLASS_SCAN(
1711 to_complement ^ cBOOL(_generic_isCC_A(*s, FLAGS(c))));
1719 if (! utf8_target) {
1720 REXEC_FBC_CLASS_SCAN(to_complement ^ cBOOL(_generic_isCC(*s,
1726 classnum = (_char_class_number) FLAGS(c);
1727 if (classnum < _FIRST_NON_SWASH_CC) {
1728 while (s < strend) {
1730 /* We avoid loading in the swash as long as possible, but
1731 * should we have to, we jump to a separate loop. This
1732 * extra 'if' statement is what keeps this code from being
1733 * just a call to REXEC_FBC_UTF8_CLASS_SCAN() */
1734 if (UTF8_IS_ABOVE_LATIN1(*s)) {
1735 goto found_above_latin1;
1737 if ((UTF8_IS_INVARIANT(*s)
1738 && to_complement ^ cBOOL(_generic_isCC((U8) *s,
1740 || (UTF8_IS_DOWNGRADEABLE_START(*s)
1741 && to_complement ^ cBOOL(
1742 _generic_isCC(TWO_BYTE_UTF8_TO_UNI(*s, *(s + 1)),
1745 if (tmp && (!reginfo || regtry(reginfo, &s)))
1757 else switch (classnum) { /* These classes are implemented as
1759 case _CC_ENUM_SPACE: /* XXX would require separate code if we
1760 revert the change of \v matching this */
1763 case _CC_ENUM_PSXSPC:
1764 REXEC_FBC_UTF8_CLASS_SCAN(
1765 to_complement ^ cBOOL(isSPACE_utf8(s)));
1768 case _CC_ENUM_BLANK:
1769 REXEC_FBC_UTF8_CLASS_SCAN(
1770 to_complement ^ cBOOL(isBLANK_utf8(s)));
1773 case _CC_ENUM_XDIGIT:
1774 REXEC_FBC_UTF8_CLASS_SCAN(
1775 to_complement ^ cBOOL(isXDIGIT_utf8(s)));
1778 case _CC_ENUM_VERTSPACE:
1779 REXEC_FBC_UTF8_CLASS_SCAN(
1780 to_complement ^ cBOOL(isVERTWS_utf8(s)));
1783 case _CC_ENUM_CNTRL:
1784 REXEC_FBC_UTF8_CLASS_SCAN(
1785 to_complement ^ cBOOL(isCNTRL_utf8(s)));
1789 Perl_croak(aTHX_ "panic: find_byclass() node %d='%s' has an unexpected character class '%d'", OP(c), PL_reg_name[OP(c)], classnum);
1790 assert(0); /* NOTREACHED */
1795 found_above_latin1: /* Here we have to load a swash to get the result
1796 for the current code point */
1797 if (! PL_utf8_swash_ptrs[classnum]) {
1798 U8 flags = _CORE_SWASH_INIT_ACCEPT_INVLIST;
1799 PL_utf8_swash_ptrs[classnum] =
1800 _core_swash_init("utf8", swash_property_names[classnum],
1801 &PL_sv_undef, 1, 0, NULL, &flags);
1804 /* This is a copy of the loop above for swash classes, though using the
1805 * FBC macro instead of being expanded out. Since we've loaded the
1806 * swash, we don't have to check for that each time through the loop */
1807 REXEC_FBC_UTF8_CLASS_SCAN(
1808 to_complement ^ cBOOL(_generic_utf8(
1811 swash_fetch(PL_utf8_swash_ptrs[classnum],
1819 /* what trie are we using right now */
1820 reg_ac_data *aho = (reg_ac_data*)progi->data->data[ ARG( c ) ];
1821 reg_trie_data *trie = (reg_trie_data*)progi->data->data[ aho->trie ];
1822 HV *widecharmap = MUTABLE_HV(progi->data->data[ aho->trie + 1 ]);
1824 const char *last_start = strend - trie->minlen;
1826 const char *real_start = s;
1828 STRLEN maxlen = trie->maxlen;
1830 U8 **points; /* map of where we were in the input string
1831 when reading a given char. For ASCII this
1832 is unnecessary overhead as the relationship
1833 is always 1:1, but for Unicode, especially
1834 case folded Unicode this is not true. */
1835 U8 foldbuf[ UTF8_MAXBYTES_CASE + 1 ];
1839 GET_RE_DEBUG_FLAGS_DECL;
1841 /* We can't just allocate points here. We need to wrap it in
1842 * an SV so it gets freed properly if there is a croak while
1843 * running the match */
1846 sv_points=newSV(maxlen * sizeof(U8 *));
1847 SvCUR_set(sv_points,
1848 maxlen * sizeof(U8 *));
1849 SvPOK_on(sv_points);
1850 sv_2mortal(sv_points);
1851 points=(U8**)SvPV_nolen(sv_points );
1852 if ( trie_type != trie_utf8_fold
1853 && (trie->bitmap || OP(c)==AHOCORASICKC) )
1856 bitmap=(U8*)trie->bitmap;
1858 bitmap=(U8*)ANYOF_BITMAP(c);
1860 /* this is the Aho-Corasick algorithm modified a touch
1861 to include special handling for long "unknown char" sequences.
1862 The basic idea being that we use AC as long as we are dealing
1863 with a possible matching char, when we encounter an unknown char
1864 (and we have not encountered an accepting state) we scan forward
1865 until we find a legal starting char.
1866 AC matching is basically that of trie matching, except that when
1867 we encounter a failing transition, we fall back to the current
1868 states "fail state", and try the current char again, a process
1869 we repeat until we reach the root state, state 1, or a legal
1870 transition. If we fail on the root state then we can either
1871 terminate if we have reached an accepting state previously, or
1872 restart the entire process from the beginning if we have not.
1875 while (s <= last_start) {
1876 const U32 uniflags = UTF8_ALLOW_DEFAULT;
1884 U8 *uscan = (U8*)NULL;
1885 U8 *leftmost = NULL;
1887 U32 accepted_word= 0;
1891 while ( state && uc <= (U8*)strend ) {
1893 U32 word = aho->states[ state ].wordnum;
1897 DEBUG_TRIE_EXECUTE_r(
1898 if ( uc <= (U8*)last_start && !BITMAP_TEST(bitmap,*uc) ) {
1899 dump_exec_pos( (char *)uc, c, strend, real_start,
1900 (char *)uc, utf8_target );
1901 PerlIO_printf( Perl_debug_log,
1902 " Scanning for legal start char...\n");
1906 while ( uc <= (U8*)last_start && !BITMAP_TEST(bitmap,*uc) ) {
1910 while ( uc <= (U8*)last_start && !BITMAP_TEST(bitmap,*uc) ) {
1916 if (uc >(U8*)last_start) break;
1920 U8 *lpos= points[ (pointpos - trie->wordinfo[word].len) % maxlen ];
1921 if (!leftmost || lpos < leftmost) {
1922 DEBUG_r(accepted_word=word);
1928 points[pointpos++ % maxlen]= uc;
1929 if (foldlen || uc < (U8*)strend) {
1930 REXEC_TRIE_READ_CHAR(trie_type, trie,
1932 uscan, len, uvc, charid, foldlen,
1934 DEBUG_TRIE_EXECUTE_r({
1935 dump_exec_pos( (char *)uc, c, strend,
1936 real_start, s, utf8_target);
1937 PerlIO_printf(Perl_debug_log,
1938 " Charid:%3u CP:%4"UVxf" ",
1950 word = aho->states[ state ].wordnum;
1952 base = aho->states[ state ].trans.base;
1954 DEBUG_TRIE_EXECUTE_r({
1956 dump_exec_pos( (char *)uc, c, strend, real_start,
1958 PerlIO_printf( Perl_debug_log,
1959 "%sState: %4"UVxf", word=%"UVxf,
1960 failed ? " Fail transition to " : "",
1961 (UV)state, (UV)word);
1967 ( ((offset = base + charid
1968 - 1 - trie->uniquecharcount)) >= 0)
1969 && ((U32)offset < trie->lasttrans)
1970 && trie->trans[offset].check == state
1971 && (tmp=trie->trans[offset].next))
1973 DEBUG_TRIE_EXECUTE_r(
1974 PerlIO_printf( Perl_debug_log," - legal\n"));
1979 DEBUG_TRIE_EXECUTE_r(
1980 PerlIO_printf( Perl_debug_log," - fail\n"));
1982 state = aho->fail[state];
1986 /* we must be accepting here */
1987 DEBUG_TRIE_EXECUTE_r(
1988 PerlIO_printf( Perl_debug_log," - accepting\n"));
1997 if (!state) state = 1;
2000 if ( aho->states[ state ].wordnum ) {
2001 U8 *lpos = points[ (pointpos - trie->wordinfo[aho->states[ state ].wordnum].len) % maxlen ];
2002 if (!leftmost || lpos < leftmost) {
2003 DEBUG_r(accepted_word=aho->states[ state ].wordnum);
2008 s = (char*)leftmost;
2009 DEBUG_TRIE_EXECUTE_r({
2011 Perl_debug_log,"Matches word #%"UVxf" at position %"IVdf". Trying full pattern...\n",
2012 (UV)accepted_word, (IV)(s - real_start)
2015 if (!reginfo || regtry(reginfo, &s)) {
2021 DEBUG_TRIE_EXECUTE_r({
2022 PerlIO_printf( Perl_debug_log,"Pattern failed. Looking for new start point...\n");
2025 DEBUG_TRIE_EXECUTE_r(
2026 PerlIO_printf( Perl_debug_log,"No match.\n"));
2035 Perl_croak(aTHX_ "panic: unknown regstclass %d", (int)OP(c));
2045 - regexec_flags - match a regexp against a string
2048 Perl_regexec_flags(pTHX_ REGEXP * const rx, char *stringarg, char *strend,
2049 char *strbeg, I32 minend, SV *sv, void *data, U32 flags)
2050 /* stringarg: the point in the string at which to begin matching */
2051 /* strend: pointer to null at end of string */
2052 /* strbeg: real beginning of string */
2053 /* minend: end of match must be >= minend bytes after stringarg. */
2054 /* sv: SV being matched: only used for utf8 flag, pos() etc; string
2055 * itself is accessed via the pointers above */
2056 /* data: May be used for some additional optimizations.
2057 Currently its only used, with a U32 cast, for transmitting
2058 the ganch offset when doing a /g match. This will change */
2059 /* nosave: For optimizations. */
2063 struct regexp *const prog = ReANY(rx);
2066 char *startpos = stringarg;
2067 I32 minlen; /* must match at least this many chars */
2068 I32 dontbother = 0; /* how many characters not to try at end */
2069 I32 end_shift = 0; /* Same for the end. */ /* CC */
2070 I32 scream_pos = -1; /* Internal iterator of scream. */
2071 char *scream_olds = NULL;
2072 const bool utf8_target = cBOOL(DO_UTF8(sv));
2074 RXi_GET_DECL(prog,progi);
2075 regmatch_info reginfo; /* create some info to pass to regtry etc */
2076 regexp_paren_pair *swap = NULL;
2077 GET_RE_DEBUG_FLAGS_DECL;
2079 PERL_ARGS_ASSERT_REGEXEC_FLAGS;
2080 PERL_UNUSED_ARG(data);
2082 /* Be paranoid... */
2083 if (prog == NULL || startpos == NULL) {
2084 Perl_croak(aTHX_ "NULL regexp parameter");
2088 multiline = prog->extflags & RXf_PMf_MULTILINE;
2089 reginfo.prog = rx; /* Yes, sorry that this is confusing. */
2091 RX_MATCH_UTF8_set(rx, utf8_target);
2093 debug_start_match(rx, utf8_target, startpos, strend,
2097 minlen = prog->minlen;
2099 if (strend - startpos < (minlen+(prog->check_offset_min<0?prog->check_offset_min:0))) {
2100 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
2101 "String too short [regexec_flags]...\n"));
2106 /* Check validity of program. */
2107 if (UCHARAT(progi->program) != REG_MAGIC) {
2108 Perl_croak(aTHX_ "corrupted regexp program");
2112 PL_reg_state.re_state_eval_setup_done = FALSE;
2116 PL_reg_flags |= RF_utf8;
2118 /* Mark beginning of line for ^ and lookbehind. */
2119 reginfo.bol = startpos; /* XXX not used ??? */
2123 /* Mark end of line for $ (and such) */
2126 /* see how far we have to get to not match where we matched before */
2127 reginfo.till = startpos+minend;
2129 /* If there is a "must appear" string, look for it. */
2132 if (prog->extflags & RXf_GPOS_SEEN) { /* Need to set reginfo->ganch */
2134 if (flags & REXEC_IGNOREPOS){ /* Means: check only at start */
2135 reginfo.ganch = startpos + prog->gofs;
2136 DEBUG_GPOS_r(PerlIO_printf(Perl_debug_log,
2137 "GPOS IGNOREPOS: reginfo.ganch = startpos + %"UVxf"\n",(UV)prog->gofs));
2138 } else if (sv && SvTYPE(sv) >= SVt_PVMG
2140 && (mg = mg_find(sv, PERL_MAGIC_regex_global))
2141 && mg->mg_len >= 0) {
2142 reginfo.ganch = strbeg + mg->mg_len; /* Defined pos() */
2143 DEBUG_GPOS_r(PerlIO_printf(Perl_debug_log,
2144 "GPOS MAGIC: reginfo.ganch = strbeg + %"IVdf"\n",(IV)mg->mg_len));
2146 if (prog->extflags & RXf_ANCH_GPOS) {
2147 if (s > reginfo.ganch)
2149 s = reginfo.ganch - prog->gofs;
2150 DEBUG_GPOS_r(PerlIO_printf(Perl_debug_log,
2151 "GPOS ANCH_GPOS: s = ganch - %"UVxf"\n",(UV)prog->gofs));
2157 reginfo.ganch = strbeg + PTR2UV(data);
2158 DEBUG_GPOS_r(PerlIO_printf(Perl_debug_log,
2159 "GPOS DATA: reginfo.ganch= strbeg + %"UVxf"\n",PTR2UV(data)));
2161 } else { /* pos() not defined */
2162 reginfo.ganch = strbeg;
2163 DEBUG_GPOS_r(PerlIO_printf(Perl_debug_log,
2164 "GPOS: reginfo.ganch = strbeg\n"));
2167 if (PL_curpm && (PM_GETRE(PL_curpm) == rx)) {
2168 /* We have to be careful. If the previous successful match
2169 was from this regex we don't want a subsequent partially
2170 successful match to clobber the old results.
2171 So when we detect this possibility we add a swap buffer
2172 to the re, and switch the buffer each match. If we fail
2173 we switch it back, otherwise we leave it swapped.
2176 /* do we need a save destructor here for eval dies? */
2177 Newxz(prog->offs, (prog->nparens + 1), regexp_paren_pair);
2178 DEBUG_BUFFERS_r(PerlIO_printf(Perl_debug_log,
2179 "rex=0x%"UVxf" saving offs: orig=0x%"UVxf" new=0x%"UVxf"\n",
2185 if (!(flags & REXEC_CHECKED) && (prog->check_substr != NULL || prog->check_utf8 != NULL)) {
2186 re_scream_pos_data d;
2188 d.scream_olds = &scream_olds;
2189 d.scream_pos = &scream_pos;
2190 s = re_intuit_start(rx, sv, s, strend, flags, &d);
2192 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "Not present...\n"));
2193 goto phooey; /* not present */
2199 /* Simplest case: anchored match need be tried only once. */
2200 /* [unless only anchor is BOL and multiline is set] */
2201 if (prog->extflags & (RXf_ANCH & ~RXf_ANCH_GPOS)) {
2202 if (s == startpos && regtry(®info, &startpos))
2204 else if (multiline || (prog->intflags & PREGf_IMPLICIT)
2205 || (prog->extflags & RXf_ANCH_MBOL)) /* XXXX SBOL? */
2210 dontbother = minlen - 1;
2211 end = HOP3c(strend, -dontbother, strbeg) - 1;
2212 /* for multiline we only have to try after newlines */
2213 if (prog->check_substr || prog->check_utf8) {
2214 /* because of the goto we can not easily reuse the macros for bifurcating the
2215 unicode/non-unicode match modes here like we do elsewhere - demerphq */
2218 goto after_try_utf8;
2220 if (regtry(®info, &s)) {
2227 if (prog->extflags & RXf_USE_INTUIT) {
2228 s = re_intuit_start(rx, sv, s + UTF8SKIP(s), strend, flags, NULL);
2237 } /* end search for check string in unicode */
2239 if (s == startpos) {
2240 goto after_try_latin;
2243 if (regtry(®info, &s)) {
2250 if (prog->extflags & RXf_USE_INTUIT) {
2251 s = re_intuit_start(rx, sv, s + 1, strend, flags, NULL);
2260 } /* end search for check string in latin*/
2261 } /* end search for check string */
2262 else { /* search for newline */
2264 /*XXX: The s-- is almost definitely wrong here under unicode - demeprhq*/
2267 /* We can use a more efficient search as newlines are the same in unicode as they are in latin */
2268 while (s <= end) { /* note it could be possible to match at the end of the string */
2269 if (*s++ == '\n') { /* don't need PL_utf8skip here */
2270 if (regtry(®info, &s))
2274 } /* end search for newline */
2275 } /* end anchored/multiline check string search */
2277 } else if (RXf_GPOS_CHECK == (prog->extflags & RXf_GPOS_CHECK))
2279 /* the warning about reginfo.ganch being used without initialization
2280 is bogus -- we set it above, when prog->extflags & RXf_GPOS_SEEN
2281 and we only enter this block when the same bit is set. */
2282 char *tmp_s = reginfo.ganch - prog->gofs;
2284 if (tmp_s >= strbeg && regtry(®info, &tmp_s))
2289 /* Messy cases: unanchored match. */
2290 if ((prog->anchored_substr || prog->anchored_utf8) && prog->intflags & PREGf_SKIP) {
2291 /* we have /x+whatever/ */
2292 /* it must be a one character string (XXXX Except UTF_PATTERN?) */
2298 if (! prog->anchored_utf8) {
2299 to_utf8_substr(prog);
2301 ch = SvPVX_const(prog->anchored_utf8)[0];
2304 DEBUG_EXECUTE_r( did_match = 1 );
2305 if (regtry(®info, &s)) goto got_it;
2307 while (s < strend && *s == ch)
2314 if (! prog->anchored_substr) {
2315 if (! to_byte_substr(prog)) {
2316 NON_UTF8_TARGET_BUT_UTF8_REQUIRED(phooey);
2319 ch = SvPVX_const(prog->anchored_substr)[0];
2322 DEBUG_EXECUTE_r( did_match = 1 );
2323 if (regtry(®info, &s)) goto got_it;
2325 while (s < strend && *s == ch)
2330 DEBUG_EXECUTE_r(if (!did_match)
2331 PerlIO_printf(Perl_debug_log,
2332 "Did not find anchored character...\n")
2335 else if (prog->anchored_substr != NULL
2336 || prog->anchored_utf8 != NULL
2337 || ((prog->float_substr != NULL || prog->float_utf8 != NULL)
2338 && prog->float_max_offset < strend - s)) {
2343 char *last1; /* Last position checked before */
2347 if (prog->anchored_substr || prog->anchored_utf8) {
2349 if (! prog->anchored_utf8) {
2350 to_utf8_substr(prog);
2352 must = prog->anchored_utf8;
2355 if (! prog->anchored_substr) {
2356 if (! to_byte_substr(prog)) {
2357 NON_UTF8_TARGET_BUT_UTF8_REQUIRED(phooey);
2360 must = prog->anchored_substr;
2362 back_max = back_min = prog->anchored_offset;
2365 if (! prog->float_utf8) {
2366 to_utf8_substr(prog);
2368 must = prog->float_utf8;
2371 if (! prog->float_substr) {
2372 if (! to_byte_substr(prog)) {
2373 NON_UTF8_TARGET_BUT_UTF8_REQUIRED(phooey);
2376 must = prog->float_substr;
2378 back_max = prog->float_max_offset;
2379 back_min = prog->float_min_offset;
2385 last = HOP3c(strend, /* Cannot start after this */
2386 -(I32)(CHR_SVLEN(must)
2387 - (SvTAIL(must) != 0) + back_min), strbeg);
2390 last1 = HOPc(s, -1);
2392 last1 = s - 1; /* bogus */
2394 /* XXXX check_substr already used to find "s", can optimize if
2395 check_substr==must. */
2397 dontbother = end_shift;
2398 strend = HOPc(strend, -dontbother);
2399 while ( (s <= last) &&
2400 (s = fbm_instr((unsigned char*)HOP3(s, back_min, (back_min<0 ? strbeg : strend)),
2401 (unsigned char*)strend, must,
2402 multiline ? FBMrf_MULTILINE : 0)) ) {
2403 DEBUG_EXECUTE_r( did_match = 1 );
2404 if (HOPc(s, -back_max) > last1) {
2405 last1 = HOPc(s, -back_min);
2406 s = HOPc(s, -back_max);
2409 char * const t = (last1 >= PL_bostr) ? HOPc(last1, 1) : last1 + 1;
2411 last1 = HOPc(s, -back_min);
2415 while (s <= last1) {
2416 if (regtry(®info, &s))
2419 s++; /* to break out of outer loop */
2426 while (s <= last1) {
2427 if (regtry(®info, &s))
2433 DEBUG_EXECUTE_r(if (!did_match) {
2434 RE_PV_QUOTED_DECL(quoted, utf8_target, PERL_DEBUG_PAD_ZERO(0),
2435 SvPVX_const(must), RE_SV_DUMPLEN(must), 30);
2436 PerlIO_printf(Perl_debug_log, "Did not find %s substr %s%s...\n",
2437 ((must == prog->anchored_substr || must == prog->anchored_utf8)
2438 ? "anchored" : "floating"),
2439 quoted, RE_SV_TAIL(must));
2443 else if ( (c = progi->regstclass) ) {
2445 const OPCODE op = OP(progi->regstclass);
2446 /* don't bother with what can't match */
2447 if (PL_regkind[op] != EXACT && op != CANY && PL_regkind[op] != TRIE)
2448 strend = HOPc(strend, -(minlen - 1));
2451 SV * const prop = sv_newmortal();
2452 regprop(prog, prop, c);
2454 RE_PV_QUOTED_DECL(quoted,utf8_target,PERL_DEBUG_PAD_ZERO(1),
2456 PerlIO_printf(Perl_debug_log,
2457 "Matching stclass %.*s against %s (%d bytes)\n",
2458 (int)SvCUR(prop), SvPVX_const(prop),
2459 quoted, (int)(strend - s));
2462 if (find_byclass(prog, c, s, strend, ®info))
2464 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "Contradicts stclass... [regexec_flags]\n"));
2468 if (prog->float_substr != NULL || prog->float_utf8 != NULL) {
2476 if (! prog->float_utf8) {
2477 to_utf8_substr(prog);
2479 float_real = prog->float_utf8;
2482 if (! prog->float_substr) {
2483 if (! to_byte_substr(prog)) {
2484 NON_UTF8_TARGET_BUT_UTF8_REQUIRED(phooey);
2487 float_real = prog->float_substr;
2490 little = SvPV_const(float_real, len);
2491 if (SvTAIL(float_real)) {
2492 /* This means that float_real contains an artificial \n on
2493 * the end due to the presence of something like this:
2494 * /foo$/ where we can match both "foo" and "foo\n" at the
2495 * end of the string. So we have to compare the end of the
2496 * string first against the float_real without the \n and
2497 * then against the full float_real with the string. We
2498 * have to watch out for cases where the string might be
2499 * smaller than the float_real or the float_real without
2501 char *checkpos= strend - len;
2503 PerlIO_printf(Perl_debug_log,
2504 "%sChecking for float_real.%s\n",
2505 PL_colors[4], PL_colors[5]));
2506 if (checkpos + 1 < strbeg) {
2507 /* can't match, even if we remove the trailing \n
2508 * string is too short to match */
2510 PerlIO_printf(Perl_debug_log,
2511 "%sString shorter than required trailing substring, cannot match.%s\n",
2512 PL_colors[4], PL_colors[5]));
2514 } else if (memEQ(checkpos + 1, little, len - 1)) {
2515 /* can match, the end of the string matches without the
2517 last = checkpos + 1;
2518 } else if (checkpos < strbeg) {
2519 /* cant match, string is too short when the "\n" is
2522 PerlIO_printf(Perl_debug_log,
2523 "%sString does not contain required trailing substring, cannot match.%s\n",
2524 PL_colors[4], PL_colors[5]));
2526 } else if (!multiline) {
2527 /* non multiline match, so compare with the "\n" at the
2528 * end of the string */
2529 if (memEQ(checkpos, little, len)) {
2533 PerlIO_printf(Perl_debug_log,
2534 "%sString does not contain required trailing substring, cannot match.%s\n",
2535 PL_colors[4], PL_colors[5]));
2539 /* multiline match, so we have to search for a place
2540 * where the full string is located */
2546 last = rninstr(s, strend, little, little + len);
2548 last = strend; /* matching "$" */
2551 /* at one point this block contained a comment which was
2552 * probably incorrect, which said that this was a "should not
2553 * happen" case. Even if it was true when it was written I am
2554 * pretty sure it is not anymore, so I have removed the comment
2555 * and replaced it with this one. Yves */
2557 PerlIO_printf(Perl_debug_log,
2558 "String does not contain required substring, cannot match.\n"
2562 dontbother = strend - last + prog->float_min_offset;
2564 if (minlen && (dontbother < minlen))
2565 dontbother = minlen - 1;
2566 strend -= dontbother; /* this one's always in bytes! */
2567 /* We don't know much -- general case. */
2570 if (regtry(®info, &s))
2579 if (regtry(®info, &s))
2581 } while (s++ < strend);
2591 PerlIO_printf(Perl_debug_log,
2592 "rex=0x%"UVxf" freeing offs: 0x%"UVxf"\n",
2598 RX_MATCH_TAINTED_set(rx, PL_reg_flags & RF_tainted);
2600 if (PL_reg_state.re_state_eval_setup_done)
2601 restore_pos(aTHX_ prog);
2602 if (RXp_PAREN_NAMES(prog))
2603 (void)hv_iterinit(RXp_PAREN_NAMES(prog));
2605 /* make sure $`, $&, $', and $digit will work later */
2606 if ( !(flags & REXEC_NOT_FIRST) ) {
2607 if (flags & REXEC_COPY_STR) {
2611 PerlIO_printf(Perl_debug_log,
2612 "Copy on write: regexp capture, type %d\n",
2615 RX_MATCH_COPY_FREE(rx);
2616 prog->saved_copy = sv_setsv_cow(prog->saved_copy, sv);
2617 prog->subbeg = (char *)SvPVX_const(prog->saved_copy);
2618 assert (SvPOKp(prog->saved_copy));
2619 prog->sublen = PL_regeol - strbeg;
2620 prog->suboffset = 0;
2621 prog->subcoffset = 0;
2626 I32 max = PL_regeol - strbeg;
2629 if ( (flags & REXEC_COPY_SKIP_POST)
2630 && !(RX_EXTFLAGS(rx) & RXf_PMf_KEEPCOPY) /* //p */
2631 && !(PL_sawampersand & SAWAMPERSAND_RIGHT)
2632 ) { /* don't copy $' part of string */
2635 /* calculate the right-most part of the string covered
2636 * by a capture. Due to look-ahead, this may be to
2637 * the right of $&, so we have to scan all captures */
2638 while (n <= prog->lastparen) {
2639 if (prog->offs[n].end > max)
2640 max = prog->offs[n].end;
2644 max = (PL_sawampersand & SAWAMPERSAND_LEFT)
2645 ? prog->offs[0].start
2647 assert(max >= 0 && max <= PL_regeol - strbeg);
2650 if ( (flags & REXEC_COPY_SKIP_PRE)
2651 && !(RX_EXTFLAGS(rx) & RXf_PMf_KEEPCOPY) /* //p */
2652 && !(PL_sawampersand & SAWAMPERSAND_LEFT)
2653 ) { /* don't copy $` part of string */
2656 /* calculate the left-most part of the string covered
2657 * by a capture. Due to look-behind, this may be to
2658 * the left of $&, so we have to scan all captures */
2659 while (min && n <= prog->lastparen) {
2660 if ( prog->offs[n].start != -1
2661 && prog->offs[n].start < min)
2663 min = prog->offs[n].start;
2667 if ((PL_sawampersand & SAWAMPERSAND_RIGHT)
2668 && min > prog->offs[0].end
2670 min = prog->offs[0].end;
2674 assert(min >= 0 && min <= max && min <= PL_regeol - strbeg);
2677 if (RX_MATCH_COPIED(rx)) {
2678 if (sublen > prog->sublen)
2680 (char*)saferealloc(prog->subbeg, sublen+1);
2683 prog->subbeg = (char*)safemalloc(sublen+1);
2684 Copy(strbeg + min, prog->subbeg, sublen, char);
2685 prog->subbeg[sublen] = '\0';
2686 prog->suboffset = min;
2687 prog->sublen = sublen;
2688 RX_MATCH_COPIED_on(rx);
2690 prog->subcoffset = prog->suboffset;
2691 if (prog->suboffset && utf8_target) {
2692 /* Convert byte offset to chars.
2693 * XXX ideally should only compute this if @-/@+
2694 * has been seen, a la PL_sawampersand ??? */
2696 /* If there's a direct correspondence between the
2697 * string which we're matching and the original SV,
2698 * then we can use the utf8 len cache associated with
2699 * the SV. In particular, it means that under //g,
2700 * sv_pos_b2u() will use the previously cached
2701 * position to speed up working out the new length of
2702 * subcoffset, rather than counting from the start of
2703 * the string each time. This stops
2704 * $x = "\x{100}" x 1E6; 1 while $x =~ /(.)/g;
2705 * from going quadratic */
2706 if (SvPOKp(sv) && SvPVX(sv) == strbeg)
2707 sv_pos_b2u(sv, &(prog->subcoffset));
2709 prog->subcoffset = utf8_length((U8*)strbeg,
2710 (U8*)(strbeg+prog->suboffset));
2714 RX_MATCH_COPY_FREE(rx);
2715 prog->subbeg = strbeg;
2716 prog->suboffset = 0;
2717 prog->subcoffset = 0;
2718 prog->sublen = PL_regeol - strbeg; /* strend may have been modified */
2725 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "%sMatch failed%s\n",
2726 PL_colors[4], PL_colors[5]));
2727 if (PL_reg_state.re_state_eval_setup_done)
2728 restore_pos(aTHX_ prog);
2730 /* we failed :-( roll it back */
2731 DEBUG_BUFFERS_r(PerlIO_printf(Perl_debug_log,
2732 "rex=0x%"UVxf" rolling back offs: freeing=0x%"UVxf" restoring=0x%"UVxf"\n",
2737 Safefree(prog->offs);
2744 /* Set which rex is pointed to by PL_reg_state, handling ref counting.
2745 * Do inc before dec, in case old and new rex are the same */
2746 #define SET_reg_curpm(Re2) \
2747 if (PL_reg_state.re_state_eval_setup_done) { \
2748 (void)ReREFCNT_inc(Re2); \
2749 ReREFCNT_dec(PM_GETRE(PL_reg_curpm)); \
2750 PM_SETRE((PL_reg_curpm), (Re2)); \
2755 - regtry - try match at specific point
2757 STATIC I32 /* 0 failure, 1 success */
2758 S_regtry(pTHX_ regmatch_info *reginfo, char **startposp)
2762 REGEXP *const rx = reginfo->prog;
2763 regexp *const prog = ReANY(rx);
2765 RXi_GET_DECL(prog,progi);
2766 GET_RE_DEBUG_FLAGS_DECL;
2768 PERL_ARGS_ASSERT_REGTRY;
2770 reginfo->cutpoint=NULL;
2772 if ((prog->extflags & RXf_EVAL_SEEN)
2773 && !PL_reg_state.re_state_eval_setup_done)
2777 PL_reg_state.re_state_eval_setup_done = TRUE;
2779 /* Make $_ available to executed code. */
2780 if (reginfo->sv != DEFSV) {
2782 DEFSV_set(reginfo->sv);
2785 if (!(SvTYPE(reginfo->sv) >= SVt_PVMG && SvMAGIC(reginfo->sv)
2786 && (mg = mg_find(reginfo->sv, PERL_MAGIC_regex_global)))) {
2787 /* prepare for quick setting of pos */
2788 #ifdef PERL_OLD_COPY_ON_WRITE
2789 if (SvIsCOW(reginfo->sv))
2790 sv_force_normal_flags(reginfo->sv, 0);
2792 mg = sv_magicext(reginfo->sv, NULL, PERL_MAGIC_regex_global,
2793 &PL_vtbl_mglob, NULL, 0);
2797 PL_reg_oldpos = mg->mg_len;
2798 SAVEDESTRUCTOR_X(restore_pos, prog);
2800 if (!PL_reg_curpm) {
2801 Newxz(PL_reg_curpm, 1, PMOP);
2804 SV* const repointer = &PL_sv_undef;
2805 /* this regexp is also owned by the new PL_reg_curpm, which
2806 will try to free it. */
2807 av_push(PL_regex_padav, repointer);
2808 PL_reg_curpm->op_pmoffset = av_len(PL_regex_padav);
2809 PL_regex_pad = AvARRAY(PL_regex_padav);
2814 PL_reg_oldcurpm = PL_curpm;
2815 PL_curpm = PL_reg_curpm;
2816 if (RXp_MATCH_COPIED(prog)) {
2817 /* Here is a serious problem: we cannot rewrite subbeg,
2818 since it may be needed if this match fails. Thus
2819 $` inside (?{}) could fail... */
2820 PL_reg_oldsaved = prog->subbeg;
2821 PL_reg_oldsavedlen = prog->sublen;
2822 PL_reg_oldsavedoffset = prog->suboffset;
2823 PL_reg_oldsavedcoffset = prog->suboffset;
2825 PL_nrs = prog->saved_copy;
2827 RXp_MATCH_COPIED_off(prog);
2830 PL_reg_oldsaved = NULL;
2831 prog->subbeg = PL_bostr;
2832 prog->suboffset = 0;
2833 prog->subcoffset = 0;
2834 prog->sublen = PL_regeol - PL_bostr; /* strend may have been modified */
2837 PL_reg_starttry = *startposp;
2839 prog->offs[0].start = *startposp - PL_bostr;
2840 prog->lastparen = 0;
2841 prog->lastcloseparen = 0;
2843 /* XXXX What this code is doing here?!!! There should be no need
2844 to do this again and again, prog->lastparen should take care of
2847 /* Tests pat.t#187 and split.t#{13,14} seem to depend on this code.
2848 * Actually, the code in regcppop() (which Ilya may be meaning by
2849 * prog->lastparen), is not needed at all by the test suite
2850 * (op/regexp, op/pat, op/split), but that code is needed otherwise
2851 * this erroneously leaves $1 defined: "1" =~ /^(?:(\d)x)?\d$/
2852 * Meanwhile, this code *is* needed for the
2853 * above-mentioned test suite tests to succeed. The common theme
2854 * on those tests seems to be returning null fields from matches.
2855 * --jhi updated by dapm */
2857 if (prog->nparens) {
2858 regexp_paren_pair *pp = prog->offs;
2860 for (i = prog->nparens; i > (I32)prog->lastparen; i--) {
2868 result = regmatch(reginfo, *startposp, progi->program + 1);
2870 prog->offs[0].end = result;
2873 if (reginfo->cutpoint)
2874 *startposp= reginfo->cutpoint;
2875 REGCP_UNWIND(lastcp);
2880 #define sayYES goto yes
2881 #define sayNO goto no
2882 #define sayNO_SILENT goto no_silent
2884 /* we dont use STMT_START/END here because it leads to
2885 "unreachable code" warnings, which are bogus, but distracting. */
2886 #define CACHEsayNO \
2887 if (ST.cache_mask) \
2888 PL_reg_poscache[ST.cache_offset] |= ST.cache_mask; \
2891 /* this is used to determine how far from the left messages like
2892 'failed...' are printed. It should be set such that messages
2893 are inline with the regop output that created them.
2895 #define REPORT_CODE_OFF 32
2898 #define CHRTEST_UNINIT -1001 /* c1/c2 haven't been calculated yet */
2899 #define CHRTEST_VOID -1000 /* the c1/c2 "next char" test should be skipped */
2900 #define CHRTEST_NOT_A_CP_1 -999
2901 #define CHRTEST_NOT_A_CP_2 -998
2903 #define SLAB_FIRST(s) (&(s)->states[0])
2904 #define SLAB_LAST(s) (&(s)->states[PERL_REGMATCH_SLAB_SLOTS-1])
2906 /* grab a new slab and return the first slot in it */
2908 STATIC regmatch_state *
2911 #if PERL_VERSION < 9 && !defined(PERL_CORE)
2914 regmatch_slab *s = PL_regmatch_slab->next;
2916 Newx(s, 1, regmatch_slab);
2917 s->prev = PL_regmatch_slab;
2919 PL_regmatch_slab->next = s;
2921 PL_regmatch_slab = s;
2922 return SLAB_FIRST(s);
2926 /* push a new state then goto it */
2928 #define PUSH_STATE_GOTO(state, node, input) \
2929 pushinput = input; \
2931 st->resume_state = state; \
2934 /* push a new state with success backtracking, then goto it */
2936 #define PUSH_YES_STATE_GOTO(state, node, input) \
2937 pushinput = input; \
2939 st->resume_state = state; \
2940 goto push_yes_state;
2947 regmatch() - main matching routine
2949 This is basically one big switch statement in a loop. We execute an op,
2950 set 'next' to point the next op, and continue. If we come to a point which
2951 we may need to backtrack to on failure such as (A|B|C), we push a
2952 backtrack state onto the backtrack stack. On failure, we pop the top
2953 state, and re-enter the loop at the state indicated. If there are no more
2954 states to pop, we return failure.
2956 Sometimes we also need to backtrack on success; for example /A+/, where
2957 after successfully matching one A, we need to go back and try to
2958 match another one; similarly for lookahead assertions: if the assertion
2959 completes successfully, we backtrack to the state just before the assertion
2960 and then carry on. In these cases, the pushed state is marked as
2961 'backtrack on success too'. This marking is in fact done by a chain of
2962 pointers, each pointing to the previous 'yes' state. On success, we pop to
2963 the nearest yes state, discarding any intermediate failure-only states.
2964 Sometimes a yes state is pushed just to force some cleanup code to be
2965 called at the end of a successful match or submatch; e.g. (??{$re}) uses
2966 it to free the inner regex.
2968 Note that failure backtracking rewinds the cursor position, while
2969 success backtracking leaves it alone.
2971 A pattern is complete when the END op is executed, while a subpattern
2972 such as (?=foo) is complete when the SUCCESS op is executed. Both of these
2973 ops trigger the "pop to last yes state if any, otherwise return true"
2976 A common convention in this function is to use A and B to refer to the two
2977 subpatterns (or to the first nodes thereof) in patterns like /A*B/: so A is
2978 the subpattern to be matched possibly multiple times, while B is the entire
2979 rest of the pattern. Variable and state names reflect this convention.
2981 The states in the main switch are the union of ops and failure/success of
2982 substates associated with with that op. For example, IFMATCH is the op
2983 that does lookahead assertions /(?=A)B/ and so the IFMATCH state means
2984 'execute IFMATCH'; while IFMATCH_A is a state saying that we have just
2985 successfully matched A and IFMATCH_A_fail is a state saying that we have
2986 just failed to match A. Resume states always come in pairs. The backtrack
2987 state we push is marked as 'IFMATCH_A', but when that is popped, we resume
2988 at IFMATCH_A or IFMATCH_A_fail, depending on whether we are backtracking
2989 on success or failure.
2991 The struct that holds a backtracking state is actually a big union, with
2992 one variant for each major type of op. The variable st points to the
2993 top-most backtrack struct. To make the code clearer, within each
2994 block of code we #define ST to alias the relevant union.
2996 Here's a concrete example of a (vastly oversimplified) IFMATCH
3002 #define ST st->u.ifmatch
3004 case IFMATCH: // we are executing the IFMATCH op, (?=A)B
3005 ST.foo = ...; // some state we wish to save
3007 // push a yes backtrack state with a resume value of
3008 // IFMATCH_A/IFMATCH_A_fail, then continue execution at the
3010 PUSH_YES_STATE_GOTO(IFMATCH_A, A, newinput);
3013 case IFMATCH_A: // we have successfully executed A; now continue with B
3015 bar = ST.foo; // do something with the preserved value
3018 case IFMATCH_A_fail: // A failed, so the assertion failed
3019 ...; // do some housekeeping, then ...
3020 sayNO; // propagate the failure
3027 For any old-timers reading this who are familiar with the old recursive
3028 approach, the code above is equivalent to:
3030 case IFMATCH: // we are executing the IFMATCH op, (?=A)B
3039 ...; // do some housekeeping, then ...
3040 sayNO; // propagate the failure
3043 The topmost backtrack state, pointed to by st, is usually free. If you
3044 want to claim it, populate any ST.foo fields in it with values you wish to
3045 save, then do one of
3047 PUSH_STATE_GOTO(resume_state, node, newinput);
3048 PUSH_YES_STATE_GOTO(resume_state, node, newinput);
3050 which sets that backtrack state's resume value to 'resume_state', pushes a
3051 new free entry to the top of the backtrack stack, then goes to 'node'.
3052 On backtracking, the free slot is popped, and the saved state becomes the
3053 new free state. An ST.foo field in this new top state can be temporarily
3054 accessed to retrieve values, but once the main loop is re-entered, it
3055 becomes available for reuse.
3057 Note that the depth of the backtrack stack constantly increases during the
3058 left-to-right execution of the pattern, rather than going up and down with
3059 the pattern nesting. For example the stack is at its maximum at Z at the
3060 end of the pattern, rather than at X in the following:
3062 /(((X)+)+)+....(Y)+....Z/
3064 The only exceptions to this are lookahead/behind assertions and the cut,
3065 (?>A), which pop all the backtrack states associated with A before
3068 Backtrack state structs are allocated in slabs of about 4K in size.
3069 PL_regmatch_state and st always point to the currently active state,
3070 and PL_regmatch_slab points to the slab currently containing
3071 PL_regmatch_state. The first time regmatch() is called, the first slab is
3072 allocated, and is never freed until interpreter destruction. When the slab
3073 is full, a new one is allocated and chained to the end. At exit from
3074 regmatch(), slabs allocated since entry are freed.
3079 #define DEBUG_STATE_pp(pp) \
3081 DUMP_EXEC_POS(locinput, scan, utf8_target); \
3082 PerlIO_printf(Perl_debug_log, \
3083 " %*s"pp" %s%s%s%s%s\n", \
3085 PL_reg_name[st->resume_state], \
3086 ((st==yes_state||st==mark_state) ? "[" : ""), \
3087 ((st==yes_state) ? "Y" : ""), \
3088 ((st==mark_state) ? "M" : ""), \
3089 ((st==yes_state||st==mark_state) ? "]" : "") \
3094 #define REG_NODE_NUM(x) ((x) ? (int)((x)-prog) : -1)
3099 S_debug_start_match(pTHX_ const REGEXP *prog, const bool utf8_target,
3100 const char *start, const char *end, const char *blurb)
3102 const bool utf8_pat = RX_UTF8(prog) ? 1 : 0;
3104 PERL_ARGS_ASSERT_DEBUG_START_MATCH;
3109 RE_PV_QUOTED_DECL(s0, utf8_pat, PERL_DEBUG_PAD_ZERO(0),
3110 RX_PRECOMP_const(prog), RX_PRELEN(prog), 60);
3112 RE_PV_QUOTED_DECL(s1, utf8_target, PERL_DEBUG_PAD_ZERO(1),
3113 start, end - start, 60);
3115 PerlIO_printf(Perl_debug_log,
3116 "%s%s REx%s %s against %s\n",
3117 PL_colors[4], blurb, PL_colors[5], s0, s1);
3119 if (utf8_target||utf8_pat)
3120 PerlIO_printf(Perl_debug_log, "UTF-8 %s%s%s...\n",
3121 utf8_pat ? "pattern" : "",
3122 utf8_pat && utf8_target ? " and " : "",
3123 utf8_target ? "string" : ""
3129 S_dump_exec_pos(pTHX_ const char *locinput,
3130 const regnode *scan,
3131 const char *loc_regeol,
3132 const char *loc_bostr,
3133 const char *loc_reg_starttry,
3134 const bool utf8_target)
3136 const int docolor = *PL_colors[0] || *PL_colors[2] || *PL_colors[4];
3137 const int taill = (docolor ? 10 : 7); /* 3 chars for "> <" */
3138 int l = (loc_regeol - locinput) > taill ? taill : (loc_regeol - locinput);
3139 /* The part of the string before starttry has one color
3140 (pref0_len chars), between starttry and current
3141 position another one (pref_len - pref0_len chars),
3142 after the current position the third one.
3143 We assume that pref0_len <= pref_len, otherwise we
3144 decrease pref0_len. */
3145 int pref_len = (locinput - loc_bostr) > (5 + taill) - l
3146 ? (5 + taill) - l : locinput - loc_bostr;
3149 PERL_ARGS_ASSERT_DUMP_EXEC_POS;
3151 while (utf8_target && UTF8_IS_CONTINUATION(*(U8*)(locinput - pref_len)))
3153 pref0_len = pref_len - (locinput - loc_reg_starttry);
3154 if (l + pref_len < (5 + taill) && l < loc_regeol - locinput)
3155 l = ( loc_regeol - locinput > (5 + taill) - pref_len
3156 ? (5 + taill) - pref_len : loc_regeol - locinput);
3157 while (utf8_target && UTF8_IS_CONTINUATION(*(U8*)(locinput + l)))
3161 if (pref0_len > pref_len)
3162 pref0_len = pref_len;
3164 const int is_uni = (utf8_target && OP(scan) != CANY) ? 1 : 0;
3166 RE_PV_COLOR_DECL(s0,len0,is_uni,PERL_DEBUG_PAD(0),
3167 (locinput - pref_len),pref0_len, 60, 4, 5);
3169 RE_PV_COLOR_DECL(s1,len1,is_uni,PERL_DEBUG_PAD(1),
3170 (locinput - pref_len + pref0_len),
3171 pref_len - pref0_len, 60, 2, 3);
3173 RE_PV_COLOR_DECL(s2,len2,is_uni,PERL_DEBUG_PAD(2),
3174 locinput, loc_regeol - locinput, 10, 0, 1);
3176 const STRLEN tlen=len0+len1+len2;
3177 PerlIO_printf(Perl_debug_log,
3178 "%4"IVdf" <%.*s%.*s%s%.*s>%*s|",
3179 (IV)(locinput - loc_bostr),
3182 (docolor ? "" : "> <"),
3184 (int)(tlen > 19 ? 0 : 19 - tlen),
3191 /* reg_check_named_buff_matched()
3192 * Checks to see if a named buffer has matched. The data array of
3193 * buffer numbers corresponding to the buffer is expected to reside
3194 * in the regexp->data->data array in the slot stored in the ARG() of
3195 * node involved. Note that this routine doesn't actually care about the
3196 * name, that information is not preserved from compilation to execution.
3197 * Returns the index of the leftmost defined buffer with the given name
3198 * or 0 if non of the buffers matched.
3201 S_reg_check_named_buff_matched(pTHX_ const regexp *rex, const regnode *scan)
3204 RXi_GET_DECL(rex,rexi);
3205 SV *sv_dat= MUTABLE_SV(rexi->data->data[ ARG( scan ) ]);
3206 I32 *nums=(I32*)SvPVX(sv_dat);
3208 PERL_ARGS_ASSERT_REG_CHECK_NAMED_BUFF_MATCHED;
3210 for ( n=0; n<SvIVX(sv_dat); n++ ) {
3211 if ((I32)rex->lastparen >= nums[n] &&
3212 rex->offs[nums[n]].end != -1)
3221 /* free all slabs above current one - called during LEAVE_SCOPE */
3224 S_clear_backtrack_stack(pTHX_ void *p)
3226 regmatch_slab *s = PL_regmatch_slab->next;
3231 PL_regmatch_slab->next = NULL;
3233 regmatch_slab * const osl = s;
3239 S_setup_EXACTISH_ST_c1_c2(pTHX_ const regnode * const text_node, int *c1p, U8* c1_utf8, int *c2p, U8* c2_utf8)
3241 /* This function determines if there are one or two characters that match
3242 * the first character of the passed-in EXACTish node <text_node>, and if
3243 * so, returns them in the passed-in pointers.
3245 * If it determines that no possible character in the target string can
3246 * match, it returns FALSE; otherwise TRUE. (The FALSE situation occurs if
3247 * the first character in <text_node> requires UTF-8 to represent, and the
3248 * target string isn't in UTF-8.)
3250 * If there are more than two characters that could match the beginning of
3251 * <text_node>, or if more context is required to determine a match or not,
3252 * it sets both *<c1p> and *<c2p> to CHRTEST_VOID.
3254 * The motiviation behind this function is to allow the caller to set up
3255 * tight loops for matching. If <text_node> is of type EXACT, there is
3256 * only one possible character that can match its first character, and so
3257 * the situation is quite simple. But things get much more complicated if
3258 * folding is involved. It may be that the first character of an EXACTFish
3259 * node doesn't participate in any possible fold, e.g., punctuation, so it
3260 * can be matched only by itself. The vast majority of characters that are
3261 * in folds match just two things, their lower and upper-case equivalents.
3262 * But not all are like that; some have multiple possible matches, or match
3263 * sequences of more than one character. This function sorts all that out.
3265 * Consider the patterns A*B or A*?B where A and B are arbitrary. In a
3266 * loop of trying to match A*, we know we can't exit where the thing
3267 * following it isn't a B. And something can't be a B unless it is the
3268 * beginning of B. By putting a quick test for that beginning in a tight
3269 * loop, we can rule out things that can't possibly be B without having to
3270 * break out of the loop, thus avoiding work. Similarly, if A is a single
3271 * character, we can make a tight loop matching A*, using the outputs of
3274 * If the target string to match isn't in UTF-8, and there aren't
3275 * complications which require CHRTEST_VOID, *<c1p> and *<c2p> are set to
3276 * the one or two possible octets (which are characters in this situation)
3277 * that can match. In all cases, if there is only one character that can
3278 * match, *<c1p> and *<c2p> will be identical.
3280 * If the target string is in UTF-8, the buffers pointed to by <c1_utf8>
3281 * and <c2_utf8> will contain the one or two UTF-8 sequences of bytes that
3282 * can match the beginning of <text_node>. They should be declared with at
3283 * least length UTF8_MAXBYTES+1. (If the target string isn't in UTF-8, it is
3284 * undefined what these contain.) If one or both of the buffers are
3285 * invariant under UTF-8, *<c1p>, and *<c2p> will also be set to the
3286 * corresponding invariant. If variant, the corresponding *<c1p> and/or
3287 * *<c2p> will be set to a negative number(s) that shouldn't match any code
3288 * point (unless inappropriately coerced to unsigned). *<c1p> will equal
3289 * *<c2p> if and only if <c1_utf8> and <c2_utf8> are the same. */
3291 const bool utf8_target = PL_reg_match_utf8;
3293 UV c1 = CHRTEST_NOT_A_CP_1;
3294 UV c2 = CHRTEST_NOT_A_CP_2;
3295 bool use_chrtest_void = FALSE;
3297 /* Used when we have both utf8 input and utf8 output, to avoid converting
3298 * to/from code points */
3299 bool utf8_has_been_setup = FALSE;
3303 U8 *pat = (U8*)STRING(text_node);
3305 if (OP(text_node) == EXACT) {
3307 /* In an exact node, only one thing can be matched, that first
3308 * character. If both the pat and the target are UTF-8, we can just
3309 * copy the input to the output, avoiding finding the code point of
3311 if (! UTF_PATTERN) {
3314 else if (utf8_target) {
3315 Copy(pat, c1_utf8, UTF8SKIP(pat), U8);
3316 Copy(pat, c2_utf8, UTF8SKIP(pat), U8);
3317 utf8_has_been_setup = TRUE;
3320 c2 = c1 = valid_utf8_to_uvchr(pat, NULL);
3323 else /* an EXACTFish node */
3325 && is_MULTI_CHAR_FOLD_utf8_safe(pat,
3326 pat + STR_LEN(text_node)))
3328 && is_MULTI_CHAR_FOLD_latin1_safe(pat,
3329 pat + STR_LEN(text_node))))
3331 /* Multi-character folds require more context to sort out. Also
3332 * PL_utf8_foldclosures used below doesn't handle them, so have to be
3333 * handled outside this routine */
3334 use_chrtest_void = TRUE;
3336 else { /* an EXACTFish node which doesn't begin with a multi-char fold */
3337 c1 = (UTF_PATTERN) ? valid_utf8_to_uvchr(pat, NULL) : *pat;
3339 /* Load the folds hash, if not already done */
3341 if (! PL_utf8_foldclosures) {
3342 if (! PL_utf8_tofold) {
3343 U8 dummy[UTF8_MAXBYTES+1];
3345 /* Force loading this by folding an above-Latin1 char */
3346 to_utf8_fold((U8*) HYPHEN_UTF8, dummy, NULL);
3347 assert(PL_utf8_tofold); /* Verify that worked */
3349 PL_utf8_foldclosures = _swash_inversion_hash(PL_utf8_tofold);
3352 /* The fold closures data structure is a hash with the keys being
3353 * the UTF-8 of every character that is folded to, like 'k', and
3354 * the values each an array of all code points that fold to its
3355 * key. e.g. [ 'k', 'K', KELVIN_SIGN ]. Multi-character folds are
3357 if ((! (listp = hv_fetch(PL_utf8_foldclosures,
3362 /* Not found in the hash, therefore there are no folds
3363 * containing it, so there is only a single character that
3367 else { /* Does participate in folds */
3368 AV* list = (AV*) *listp;
3369 if (av_len(list) != 1) {
3371 /* If there aren't exactly two folds to this, it is outside
3372 * the scope of this function */
3373 use_chrtest_void = TRUE;
3375 else { /* There are two. Get them */
3376 SV** c_p = av_fetch(list, 0, FALSE);
3378 Perl_croak(aTHX_ "panic: invalid PL_utf8_foldclosures structure");
3382 c_p = av_fetch(list, 1, FALSE);
3384 Perl_croak(aTHX_ "panic: invalid PL_utf8_foldclosures structure");
3388 /* Folds that cross the 255/256 boundary are forbidden if
3389 * EXACTFL, or EXACTFA and one is ASCIII. Since the
3390 * pattern character is above 256, and its only other match
3391 * is below 256, the only legal match will be to itself.
3392 * We have thrown away the original, so have to compute
3393 * which is the one above 255 */
3394 if ((c1 < 256) != (c2 < 256)) {
3395 if (OP(text_node) == EXACTFL
3396 || (OP(text_node) == EXACTFA
3397 && (isASCII(c1) || isASCII(c2))))
3410 else /* Here, c1 is < 255 */
3412 && HAS_NONLATIN1_FOLD_CLOSURE(c1)
3413 && OP(text_node) != EXACTFL
3414 && (OP(text_node) != EXACTFA || ! isASCII(c1)))
3416 /* Here, there could be something above Latin1 in the target which
3417 * folds to this character in the pattern. All such cases except
3418 * LATIN SMALL LETTER Y WITH DIAERESIS have more than two characters
3419 * involved in their folds, so are outside the scope of this
3421 if (UNLIKELY(c1 == LATIN_SMALL_LETTER_Y_WITH_DIAERESIS)) {
3422 c2 = LATIN_CAPITAL_LETTER_Y_WITH_DIAERESIS;
3425 use_chrtest_void = TRUE;
3428 else { /* Here nothing above Latin1 can fold to the pattern character */
3429 switch (OP(text_node)) {
3431 case EXACTFL: /* /l rules */
3432 c2 = PL_fold_locale[c1];
3436 if (! utf8_target) { /* /d rules */
3441 /* /u rules for all these. This happens to work for
3442 * EXACTFA as nothing in Latin1 folds to ASCII */
3444 case EXACTFU_TRICKYFOLD:
3447 c2 = PL_fold_latin1[c1];
3451 Perl_croak(aTHX_ "panic: Unexpected op %u", OP(text_node));
3452 assert(0); /* NOTREACHED */
3457 /* Here have figured things out. Set up the returns */
3458 if (use_chrtest_void) {
3459 *c2p = *c1p = CHRTEST_VOID;
3461 else if (utf8_target) {
3462 if (! utf8_has_been_setup) { /* Don't have the utf8; must get it */
3463 uvchr_to_utf8(c1_utf8, c1);
3464 uvchr_to_utf8(c2_utf8, c2);
3467 /* Invariants are stored in both the utf8 and byte outputs; Use
3468 * negative numbers otherwise for the byte ones. Make sure that the
3469 * byte ones are the same iff the utf8 ones are the same */
3470 *c1p = (UTF8_IS_INVARIANT(*c1_utf8)) ? *c1_utf8 : CHRTEST_NOT_A_CP_1;
3471 *c2p = (UTF8_IS_INVARIANT(*c2_utf8))
3474 ? CHRTEST_NOT_A_CP_1
3475 : CHRTEST_NOT_A_CP_2;
3477 else if (c1 > 255) {
3478 if (c2 > 255) { /* both possibilities are above what a non-utf8 string
3483 *c1p = *c2p = c2; /* c2 is the only representable value */
3485 else { /* c1 is representable; see about c2 */
3487 *c2p = (c2 < 256) ? c2 : c1;
3493 /* returns -1 on failure, $+[0] on success */
3495 S_regmatch(pTHX_ regmatch_info *reginfo, char *startpos, regnode *prog)
3497 #if PERL_VERSION < 9 && !defined(PERL_CORE)
3501 const bool utf8_target = PL_reg_match_utf8;
3502 const U32 uniflags = UTF8_ALLOW_DEFAULT;
3503 REGEXP *rex_sv = reginfo->prog;
3504 regexp *rex = ReANY(rex_sv);
3505 RXi_GET_DECL(rex,rexi);
3507 /* the current state. This is a cached copy of PL_regmatch_state */
3509 /* cache heavy used fields of st in registers */
3512 U32 n = 0; /* general value; init to avoid compiler warning */
3513 I32 ln = 0; /* len or last; init to avoid compiler warning */
3514 char *locinput = startpos;
3515 char *pushinput; /* where to continue after a PUSH */
3516 I32 nextchr; /* is always set to UCHARAT(locinput) */
3518 bool result = 0; /* return value of S_regmatch */
3519 int depth = 0; /* depth of backtrack stack */
3520 U32 nochange_depth = 0; /* depth of GOSUB recursion with nochange */
3521 const U32 max_nochange_depth =
3522 (3 * rex->nparens > MAX_RECURSE_EVAL_NOCHANGE_DEPTH) ?
3523 3 * rex->nparens : MAX_RECURSE_EVAL_NOCHANGE_DEPTH;
3524 regmatch_state *yes_state = NULL; /* state to pop to on success of
3526 /* mark_state piggy backs on the yes_state logic so that when we unwind
3527 the stack on success we can update the mark_state as we go */
3528 regmatch_state *mark_state = NULL; /* last mark state we have seen */
3529 regmatch_state *cur_eval = NULL; /* most recent EVAL_AB state */
3530 struct regmatch_state *cur_curlyx = NULL; /* most recent curlyx */
3532 bool no_final = 0; /* prevent failure from backtracking? */
3533 bool do_cutgroup = 0; /* no_final only until next branch/trie entry */
3534 char *startpoint = locinput;
3535 SV *popmark = NULL; /* are we looking for a mark? */
3536 SV *sv_commit = NULL; /* last mark name seen in failure */
3537 SV *sv_yes_mark = NULL; /* last mark name we have seen
3538 during a successful match */
3539 U32 lastopen = 0; /* last open we saw */
3540 bool has_cutgroup = RX_HAS_CUTGROUP(rex) ? 1 : 0;
3541 SV* const oreplsv = GvSV(PL_replgv);
3542 /* these three flags are set by various ops to signal information to
3543 * the very next op. They have a useful lifetime of exactly one loop
3544 * iteration, and are not preserved or restored by state pushes/pops
3546 bool sw = 0; /* the condition value in (?(cond)a|b) */
3547 bool minmod = 0; /* the next "{n,m}" is a "{n,m}?" */
3548 int logical = 0; /* the following EVAL is:
3552 or the following IFMATCH/UNLESSM is:
3553 false: plain (?=foo)
3554 true: used as a condition: (?(?=foo))
3556 PAD* last_pad = NULL;
3558 I32 gimme = G_SCALAR;
3559 CV *caller_cv = NULL; /* who called us */
3560 CV *last_pushed_cv = NULL; /* most recently called (?{}) CV */
3561 CHECKPOINT runops_cp; /* savestack position before executing EVAL */
3562 U32 maxopenparen = 0; /* max '(' index seen so far */
3563 int to_complement; /* Invert the result? */
3564 _char_class_number classnum;
3567 GET_RE_DEBUG_FLAGS_DECL;
3570 /* shut up 'may be used uninitialized' compiler warnings for dMULTICALL */
3571 multicall_oldcatch = 0;
3572 multicall_cv = NULL;
3574 PERL_UNUSED_VAR(multicall_cop);
3575 PERL_UNUSED_VAR(newsp);
3578 PERL_ARGS_ASSERT_REGMATCH;
3580 DEBUG_OPTIMISE_r( DEBUG_EXECUTE_r({
3581 PerlIO_printf(Perl_debug_log,"regmatch start\n");
3583 /* on first ever call to regmatch, allocate first slab */
3584 if (!PL_regmatch_slab) {
3585 Newx(PL_regmatch_slab, 1, regmatch_slab);
3586 PL_regmatch_slab->prev = NULL;
3587 PL_regmatch_slab->next = NULL;
3588 PL_regmatch_state = SLAB_FIRST(PL_regmatch_slab);
3591 oldsave = PL_savestack_ix;
3592 SAVEDESTRUCTOR_X(S_clear_backtrack_stack, NULL);
3593 SAVEVPTR(PL_regmatch_slab);
3594 SAVEVPTR(PL_regmatch_state);
3596 /* grab next free state slot */
3597 st = ++PL_regmatch_state;
3598 if (st > SLAB_LAST(PL_regmatch_slab))
3599 st = PL_regmatch_state = S_push_slab(aTHX);
3601 /* Note that nextchr is a byte even in UTF */
3604 while (scan != NULL) {
3607 SV * const prop = sv_newmortal();
3608 regnode *rnext=regnext(scan);
3609 DUMP_EXEC_POS( locinput, scan, utf8_target );
3610 regprop(rex, prop, scan);
3612 PerlIO_printf(Perl_debug_log,
3613 "%3"IVdf":%*s%s(%"IVdf")\n",
3614 (IV)(scan - rexi->program), depth*2, "",
3616 (PL_regkind[OP(scan)] == END || !rnext) ?
3617 0 : (IV)(rnext - rexi->program));
3620 next = scan + NEXT_OFF(scan);
3623 state_num = OP(scan);
3629 assert(nextchr < 256 && (nextchr >= 0 || nextchr == NEXTCHR_EOS));
3631 switch (state_num) {
3632 case BOL: /* /^../ */
3633 if (locinput == PL_bostr)
3635 /* reginfo->till = reginfo->bol; */
3640 case MBOL: /* /^../m */
3641 if (locinput == PL_bostr ||
3642 (!NEXTCHR_IS_EOS && locinput[-1] == '\n'))
3648 case SBOL: /* /^../s */
3649 if (locinput == PL_bostr)
3654 if (locinput == reginfo->ganch)
3658 case KEEPS: /* \K */
3659 /* update the startpoint */
3660 st->u.keeper.val = rex->offs[0].start;
3661 rex->offs[0].start = locinput - PL_bostr;
3662 PUSH_STATE_GOTO(KEEPS_next, next, locinput);
3663 assert(0); /*NOTREACHED*/
3664 case KEEPS_next_fail:
3665 /* rollback the start point change */
3666 rex->offs[0].start = st->u.keeper.val;
3668 assert(0); /*NOTREACHED*/
3670 case EOL: /* /..$/ */
3673 case MEOL: /* /..$/m */
3674 if (!NEXTCHR_IS_EOS && nextchr != '\n')
3678 case SEOL: /* /..$/s */
3680 if (!NEXTCHR_IS_EOS && nextchr != '\n')
3682 if (PL_regeol - locinput > 1)
3687 if (!NEXTCHR_IS_EOS)
3691 case SANY: /* /./s */
3694 goto increment_locinput;
3702 case REG_ANY: /* /./ */
3703 if ((NEXTCHR_IS_EOS) || nextchr == '\n')
3705 goto increment_locinput;
3709 #define ST st->u.trie
3710 case TRIEC: /* (ab|cd) with known charclass */
3711 /* In this case the charclass data is available inline so
3712 we can fail fast without a lot of extra overhead.
3714 if(!NEXTCHR_IS_EOS && !ANYOF_BITMAP_TEST(scan, nextchr)) {
3716 PerlIO_printf(Perl_debug_log,
3717 "%*s %sfailed to match trie start class...%s\n",
3718 REPORT_CODE_OFF+depth*2, "", PL_colors[4], PL_colors[5])
3721 assert(0); /* NOTREACHED */
3724 case TRIE: /* (ab|cd) */
3725 /* the basic plan of execution of the trie is:
3726 * At the beginning, run though all the states, and
3727 * find the longest-matching word. Also remember the position
3728 * of the shortest matching word. For example, this pattern:
3731 * when matched against the string "abcde", will generate
3732 * accept states for all words except 3, with the longest
3733 * matching word being 4, and the shortest being 2 (with
3734 * the position being after char 1 of the string).
3736 * Then for each matching word, in word order (i.e. 1,2,4,5),
3737 * we run the remainder of the pattern; on each try setting
3738 * the current position to the character following the word,
3739 * returning to try the next word on failure.
3741 * We avoid having to build a list of words at runtime by
3742 * using a compile-time structure, wordinfo[].prev, which
3743 * gives, for each word, the previous accepting word (if any).
3744 * In the case above it would contain the mappings 1->2, 2->0,
3745 * 3->0, 4->5, 5->1. We can use this table to generate, from
3746 * the longest word (4 above), a list of all words, by
3747 * following the list of prev pointers; this gives us the
3748 * unordered list 4,5,1,2. Then given the current word we have
3749 * just tried, we can go through the list and find the
3750 * next-biggest word to try (so if we just failed on word 2,
3751 * the next in the list is 4).
3753 * Since at runtime we don't record the matching position in
3754 * the string for each word, we have to work that out for
3755 * each word we're about to process. The wordinfo table holds
3756 * the character length of each word; given that we recorded
3757 * at the start: the position of the shortest word and its
3758 * length in chars, we just need to move the pointer the
3759 * difference between the two char lengths. Depending on
3760 * Unicode status and folding, that's cheap or expensive.
3762 * This algorithm is optimised for the case where are only a
3763 * small number of accept states, i.e. 0,1, or maybe 2.
3764 * With lots of accepts states, and having to try all of them,
3765 * it becomes quadratic on number of accept states to find all
3770 /* what type of TRIE am I? (utf8 makes this contextual) */
3771 DECL_TRIE_TYPE(scan);
3773 /* what trie are we using right now */
3774 reg_trie_data * const trie
3775 = (reg_trie_data*)rexi->data->data[ ARG( scan ) ];
3776 HV * widecharmap = MUTABLE_HV(rexi->data->data[ ARG( scan ) + 1 ]);
3777 U32 state = trie->startstate;
3780 && (NEXTCHR_IS_EOS || !TRIE_BITMAP_TEST(trie, nextchr)))
3782 if (trie->states[ state ].wordnum) {
3784 PerlIO_printf(Perl_debug_log,
3785 "%*s %smatched empty string...%s\n",
3786 REPORT_CODE_OFF+depth*2, "", PL_colors[4], PL_colors[5])
3792 PerlIO_printf(Perl_debug_log,
3793 "%*s %sfailed to match trie start class...%s\n",
3794 REPORT_CODE_OFF+depth*2, "", PL_colors[4], PL_colors[5])
3801 U8 *uc = ( U8* )locinput;
3805 U8 *uscan = (U8*)NULL;
3806 U8 foldbuf[ UTF8_MAXBYTES_CASE + 1 ];
3807 U32 charcount = 0; /* how many input chars we have matched */
3808 U32 accepted = 0; /* have we seen any accepting states? */
3810 ST.jump = trie->jump;
3813 ST.longfold = FALSE; /* char longer if folded => it's harder */
3816 /* fully traverse the TRIE; note the position of the
3817 shortest accept state and the wordnum of the longest
3820 while ( state && uc <= (U8*)PL_regeol ) {
3821 U32 base = trie->states[ state ].trans.base;
3825 wordnum = trie->states[ state ].wordnum;
3827 if (wordnum) { /* it's an accept state */
3830 /* record first match position */
3832 ST.firstpos = (U8*)locinput;
3837 ST.firstchars = charcount;
3840 if (!ST.nextword || wordnum < ST.nextword)
3841 ST.nextword = wordnum;
3842 ST.topword = wordnum;
3845 DEBUG_TRIE_EXECUTE_r({
3846 DUMP_EXEC_POS( (char *)uc, scan, utf8_target );
3847 PerlIO_printf( Perl_debug_log,
3848 "%*s %sState: %4"UVxf" Accepted: %c ",
3849 2+depth * 2, "", PL_colors[4],
3850 (UV)state, (accepted ? 'Y' : 'N'));
3853 /* read a char and goto next state */
3854 if ( base && (foldlen || uc < (U8*)PL_regeol)) {
3856 REXEC_TRIE_READ_CHAR(trie_type, trie, widecharmap, uc,
3857 uscan, len, uvc, charid, foldlen,
3864 base + charid - 1 - trie->uniquecharcount)) >= 0)
3866 && ((U32)offset < trie->lasttrans)
3867 && trie->trans[offset].check == state)
3869 state = trie->trans[offset].next;
3880 DEBUG_TRIE_EXECUTE_r(
3881 PerlIO_printf( Perl_debug_log,
3882 "Charid:%3x CP:%4"UVxf" After State: %4"UVxf"%s\n",
3883 charid, uvc, (UV)state, PL_colors[5] );
3889 /* calculate total number of accept states */
3894 w = trie->wordinfo[w].prev;
3897 ST.accepted = accepted;
3901 PerlIO_printf( Perl_debug_log,
3902 "%*s %sgot %"IVdf" possible matches%s\n",
3903 REPORT_CODE_OFF + depth * 2, "",
3904 PL_colors[4], (IV)ST.accepted, PL_colors[5] );
3906 goto trie_first_try; /* jump into the fail handler */
3908 assert(0); /* NOTREACHED */
3910 case TRIE_next_fail: /* we failed - try next alternative */
3914 REGCP_UNWIND(ST.cp);
3915 UNWIND_PAREN(ST.lastparen, ST.lastcloseparen);
3917 if (!--ST.accepted) {
3919 PerlIO_printf( Perl_debug_log,
3920 "%*s %sTRIE failed...%s\n",
3921 REPORT_CODE_OFF+depth*2, "",
3928 /* Find next-highest word to process. Note that this code
3929 * is O(N^2) per trie run (O(N) per branch), so keep tight */
3932 U16 const nextword = ST.nextword;
3933 reg_trie_wordinfo * const wordinfo
3934 = ((reg_trie_data*)rexi->data->data[ARG(ST.me)])->wordinfo;
3935 for (word=ST.topword; word; word=wordinfo[word].prev) {
3936 if (word > nextword && (!min || word < min))
3949 ST.lastparen = rex->lastparen;
3950 ST.lastcloseparen = rex->lastcloseparen;
3954 /* find start char of end of current word */
3956 U32 chars; /* how many chars to skip */
3957 reg_trie_data * const trie
3958 = (reg_trie_data*)rexi->data->data[ARG(ST.me)];
3960 assert((trie->wordinfo[ST.nextword].len - trie->prefixlen)
3962 chars = (trie->wordinfo[ST.nextword].len - trie->prefixlen)
3967 /* the hard option - fold each char in turn and find
3968 * its folded length (which may be different */
3969 U8 foldbuf[UTF8_MAXBYTES_CASE + 1];
3977 uvc = utf8n_to_uvuni((U8*)uc, UTF8_MAXLEN, &len,
3985 uvc = to_uni_fold(uvc, foldbuf, &foldlen);
3990 uvc = utf8n_to_uvuni(uscan, UTF8_MAXLEN, &len,
4006 scan = ST.me + ((ST.jump && ST.jump[ST.nextword])
4007 ? ST.jump[ST.nextword]
4011 PerlIO_printf( Perl_debug_log,
4012 "%*s %sTRIE matched word #%d, continuing%s\n",
4013 REPORT_CODE_OFF+depth*2, "",
4020 if (ST.accepted > 1 || has_cutgroup) {
4021 PUSH_STATE_GOTO(TRIE_next, scan, (char*)uc);
4022 assert(0); /* NOTREACHED */
4024 /* only one choice left - just continue */
4026 AV *const trie_words
4027 = MUTABLE_AV(rexi->data->data[ARG(ST.me)+TRIE_WORDS_OFFSET]);
4028 SV ** const tmp = av_fetch( trie_words,
4030 SV *sv= tmp ? sv_newmortal() : NULL;
4032 PerlIO_printf( Perl_debug_log,
4033 "%*s %sonly one match left, short-circuiting: #%d <%s>%s\n",
4034 REPORT_CODE_OFF+depth*2, "", PL_colors[4],
4036 tmp ? pv_pretty(sv, SvPV_nolen_const(*tmp), SvCUR(*tmp), 0,
4037 PL_colors[0], PL_colors[1],
4038 (SvUTF8(*tmp) ? PERL_PV_ESCAPE_UNI : 0)|PERL_PV_ESCAPE_NONASCII
4040 : "not compiled under -Dr",
4044 locinput = (char*)uc;
4045 continue; /* execute rest of RE */
4046 assert(0); /* NOTREACHED */
4050 case EXACT: { /* /abc/ */
4051 char *s = STRING(scan);
4053 if (utf8_target != UTF_PATTERN) {
4054 /* The target and the pattern have differing utf8ness. */
4056 const char * const e = s + ln;
4059 /* The target is utf8, the pattern is not utf8.
4060 * Above-Latin1 code points can't match the pattern;
4061 * invariants match exactly, and the other Latin1 ones need
4062 * to be downgraded to a single byte in order to do the
4063 * comparison. (If we could be confident that the target
4064 * is not malformed, this could be refactored to have fewer
4065 * tests by just assuming that if the first bytes match, it
4066 * is an invariant, but there are tests in the test suite
4067 * dealing with (??{...}) which violate this) */
4071 if (UTF8_IS_ABOVE_LATIN1(* (U8*) l)) {
4074 if (UTF8_IS_INVARIANT(*(U8*)l)) {
4081 if (TWO_BYTE_UTF8_TO_UNI(*l, *(l+1)) != * (U8*) s) {
4090 /* The target is not utf8, the pattern is utf8. */
4092 if (l >= PL_regeol || UTF8_IS_ABOVE_LATIN1(* (U8*) s))
4096 if (UTF8_IS_INVARIANT(*(U8*)s)) {
4103 if (TWO_BYTE_UTF8_TO_UNI(*s, *(s+1)) != * (U8*) l) {
4114 /* The target and the pattern have the same utf8ness. */
4115 /* Inline the first character, for speed. */
4116 if (UCHARAT(s) != nextchr)
4118 if (PL_regeol - locinput < ln)
4120 if (ln > 1 && memNE(s, locinput, ln))
4126 case EXACTFL: { /* /abc/il */
4128 const U8 * fold_array;
4130 U32 fold_utf8_flags;
4132 PL_reg_flags |= RF_tainted;
4133 folder = foldEQ_locale;
4134 fold_array = PL_fold_locale;
4135 fold_utf8_flags = FOLDEQ_UTF8_LOCALE;
4138 case EXACTFU_SS: /* /\x{df}/iu */
4139 case EXACTFU_TRICKYFOLD: /* /\x{390}/iu */
4140 case EXACTFU: /* /abc/iu */
4141 folder = foldEQ_latin1;
4142 fold_array = PL_fold_latin1;
4143 fold_utf8_flags = (UTF_PATTERN) ? FOLDEQ_S1_ALREADY_FOLDED : 0;
4146 case EXACTFA: /* /abc/iaa */
4147 folder = foldEQ_latin1;
4148 fold_array = PL_fold_latin1;
4149 fold_utf8_flags = FOLDEQ_UTF8_NOMIX_ASCII;
4152 case EXACTF: /* /abc/i */
4154 fold_array = PL_fold;
4155 fold_utf8_flags = 0;
4161 if (utf8_target || UTF_PATTERN || state_num == EXACTFU_SS) {
4162 /* Either target or the pattern are utf8, or has the issue where
4163 * the fold lengths may differ. */
4164 const char * const l = locinput;
4165 char *e = PL_regeol;
4167 if (! foldEQ_utf8_flags(s, 0, ln, cBOOL(UTF_PATTERN),
4168 l, &e, 0, utf8_target, fold_utf8_flags))
4176 /* Neither the target nor the pattern are utf8 */
4177 if (UCHARAT(s) != nextchr
4179 && UCHARAT(s) != fold_array[nextchr])
4183 if (PL_regeol - locinput < ln)
4185 if (ln > 1 && ! folder(s, locinput, ln))
4191 /* XXX Could improve efficiency by separating these all out using a
4192 * macro or in-line function. At that point regcomp.c would no longer
4193 * have to set the FLAGS fields of these */
4194 case BOUNDL: /* /\b/l */
4195 case NBOUNDL: /* /\B/l */
4196 PL_reg_flags |= RF_tainted;
4198 case BOUND: /* /\b/ */
4199 case BOUNDU: /* /\b/u */
4200 case BOUNDA: /* /\b/a */
4201 case NBOUND: /* /\B/ */
4202 case NBOUNDU: /* /\B/u */
4203 case NBOUNDA: /* /\B/a */
4204 /* was last char in word? */
4206 && FLAGS(scan) != REGEX_ASCII_RESTRICTED_CHARSET
4207 && FLAGS(scan) != REGEX_ASCII_MORE_RESTRICTED_CHARSET)
4209 if (locinput == PL_bostr)
4212 const U8 * const r = reghop3((U8*)locinput, -1, (U8*)PL_bostr);
4214 ln = utf8n_to_uvchr(r, UTF8SKIP(r), 0, uniflags);
4216 if (FLAGS(scan) != REGEX_LOCALE_CHARSET) {
4217 ln = isALNUM_uni(ln);
4221 LOAD_UTF8_CHARCLASS_ALNUM();
4222 n = swash_fetch(PL_utf8_swash_ptrs[_CC_WORDCHAR], (U8*)locinput,
4227 ln = isALNUM_LC_uvchr(UNI_TO_NATIVE(ln));
4228 n = NEXTCHR_IS_EOS ? 0 : isALNUM_LC_utf8((U8*)locinput);
4233 /* Here the string isn't utf8, or is utf8 and only ascii
4234 * characters are to match \w. In the latter case looking at
4235 * the byte just prior to the current one may be just the final
4236 * byte of a multi-byte character. This is ok. There are two
4238 * 1) it is a single byte character, and then the test is doing
4239 * just what it's supposed to.
4240 * 2) it is a multi-byte character, in which case the final
4241 * byte is never mistakable for ASCII, and so the test
4242 * will say it is not a word character, which is the
4243 * correct answer. */
4244 ln = (locinput != PL_bostr) ?
4245 UCHARAT(locinput - 1) : '\n';
4246 switch (FLAGS(scan)) {
4247 case REGEX_UNICODE_CHARSET:
4248 ln = isWORDCHAR_L1(ln);
4249 n = NEXTCHR_IS_EOS ? 0 : isWORDCHAR_L1(nextchr);
4251 case REGEX_LOCALE_CHARSET:
4252 ln = isALNUM_LC(ln);
4253 n = NEXTCHR_IS_EOS ? 0 : isALNUM_LC(nextchr);
4255 case REGEX_DEPENDS_CHARSET:
4257 n = NEXTCHR_IS_EOS ? 0 : isALNUM(nextchr);
4259 case REGEX_ASCII_RESTRICTED_CHARSET:
4260 case REGEX_ASCII_MORE_RESTRICTED_CHARSET:
4261 ln = isWORDCHAR_A(ln);
4262 n = NEXTCHR_IS_EOS ? 0 : isWORDCHAR_A(nextchr);
4265 Perl_croak(aTHX_ "panic: Unexpected FLAGS %u in op %u", FLAGS(scan), OP(scan));
4269 /* Note requires that all BOUNDs be lower than all NBOUNDs in
4271 if (((!ln) == (!n)) == (OP(scan) < NBOUND))
4275 case ANYOF: /* /[abc]/ */
4279 if (!reginclass(rex, scan, (U8*)locinput, utf8_target))
4281 locinput += UTF8SKIP(locinput);
4284 if (!REGINCLASS(rex, scan, (U8*)locinput))
4290 /* The argument (FLAGS) to all the POSIX node types is the class number
4293 case NPOSIXL: /* \W or [:^punct:] etc. under /l */
4297 case POSIXL: /* \w or [:punct:] etc. under /l */
4301 /* The locale hasn't influenced the outcome before this, so defer
4302 * tainting until now */
4303 PL_reg_flags |= RF_tainted;
4305 /* Use isFOO_lc() for characters within Latin1. (Note that
4306 * UTF8_IS_INVARIANT works even on non-UTF-8 strings, or else
4307 * wouldn't be invariant) */
4308 if (UTF8_IS_INVARIANT(nextchr) || ! utf8_target) {
4309 if (! (to_complement ^ cBOOL(isFOO_lc(FLAGS(scan), nextchr)))) {
4313 else if (UTF8_IS_DOWNGRADEABLE_START(nextchr)) {
4314 if (! (to_complement ^ cBOOL(isFOO_lc(FLAGS(scan),
4315 TWO_BYTE_UTF8_TO_UNI(nextchr,
4316 *(locinput + 1))))))
4321 else { /* Here, must be an above Latin-1 code point */
4322 goto utf8_posix_not_eos;
4325 /* Here, must be utf8 */
4326 locinput += UTF8SKIP(locinput);
4329 case NPOSIXD: /* \W or [:^punct:] etc. under /d */
4333 case POSIXD: /* \w or [:punct:] etc. under /d */
4339 case NPOSIXA: /* \W or [:^punct:] etc. under /a */
4341 if (NEXTCHR_IS_EOS) {
4345 /* All UTF-8 variants match */
4346 if (! UTF8_IS_INVARIANT(nextchr)) {
4347 goto increment_locinput;
4353 case POSIXA: /* \w or [:punct:] etc. under /a */
4356 /* We get here through POSIXD, NPOSIXD, and NPOSIXA when not in
4357 * UTF-8, and also from NPOSIXA even in UTF-8 when the current
4358 * character is a single byte */
4361 || ! (to_complement ^ cBOOL(_generic_isCC_A(nextchr,
4367 /* Here we are either not in utf8, or we matched a utf8-invariant,
4368 * so the next char is the next byte */
4372 case NPOSIXU: /* \W or [:^punct:] etc. under /u */
4376 case POSIXU: /* \w or [:punct:] etc. under /u */
4378 if (NEXTCHR_IS_EOS) {
4383 /* Use _generic_isCC() for characters within Latin1. (Note that
4384 * UTF8_IS_INVARIANT works even on non-UTF-8 strings, or else
4385 * wouldn't be invariant) */
4386 if (UTF8_IS_INVARIANT(nextchr) || ! utf8_target) {
4387 if (! (to_complement ^ cBOOL(_generic_isCC(nextchr,
4394 else if (UTF8_IS_DOWNGRADEABLE_START(nextchr)) {
4395 if (! (to_complement
4396 ^ cBOOL(_generic_isCC(TWO_BYTE_UTF8_TO_UNI(nextchr,
4404 else { /* Handle above Latin-1 code points */
4405 classnum = (_char_class_number) FLAGS(scan);
4406 if (classnum < _FIRST_NON_SWASH_CC) {
4408 /* Here, uses a swash to find such code points. Load if if
4409 * not done already */
4410 if (! PL_utf8_swash_ptrs[classnum]) {
4411 U8 flags = _CORE_SWASH_INIT_ACCEPT_INVLIST;
4412 PL_utf8_swash_ptrs[classnum]
4413 = _core_swash_init("utf8",
4414 swash_property_names[classnum],
4415 &PL_sv_undef, 1, 0, NULL, &flags);
4417 if (! (to_complement
4418 ^ cBOOL(swash_fetch(PL_utf8_swash_ptrs[classnum],
4419 (U8 *) locinput, TRUE))))
4424 else { /* Here, uses macros to find above Latin-1 code points */
4426 case _CC_ENUM_SPACE: /* XXX would require separate
4427 code if we revert the change
4428 of \v matching this */
4429 case _CC_ENUM_PSXSPC:
4430 if (! (to_complement
4431 ^ cBOOL(is_XPERLSPACE_high(locinput))))
4436 case _CC_ENUM_BLANK:
4437 if (! (to_complement
4438 ^ cBOOL(is_HORIZWS_high(locinput))))
4443 case _CC_ENUM_XDIGIT:
4444 if (! (to_complement
4445 ^ cBOOL(is_XDIGIT_high(locinput))))
4450 case _CC_ENUM_VERTSPACE:
4451 if (! (to_complement
4452 ^ cBOOL(is_VERTWS_high(locinput))))
4457 default: /* The rest, e.g. [:cntrl:], can't match
4459 if (! to_complement) {
4465 locinput += UTF8SKIP(locinput);
4469 case CLUMP: /* Match \X: logical Unicode character. This is defined as
4470 a Unicode extended Grapheme Cluster */
4471 /* From http://www.unicode.org/reports/tr29 (5.2 version). An
4472 extended Grapheme Cluster is:
4475 | Prepend* Begin Extend*
4478 Begin is: ( Special_Begin | ! Control )
4479 Special_Begin is: ( Regional-Indicator+ | Hangul-syllable )
4480 Extend is: ( Grapheme_Extend | Spacing_Mark )
4481 Control is: [ GCB_Control | CR | LF ]
4482 Hangul-syllable is: ( T+ | ( L* ( L | ( LVT | ( V | LV ) V* ) T* ) ))
4484 If we create a 'Regular_Begin' = Begin - Special_Begin, then
4487 Begin is ( Regular_Begin + Special Begin )
4489 It turns out that 98.4% of all Unicode code points match
4490 Regular_Begin. Doing it this way eliminates a table match in
4491 the previous implementation for almost all Unicode code points.
4493 There is a subtlety with Prepend* which showed up in testing.
4494 Note that the Begin, and only the Begin is required in:
4495 | Prepend* Begin Extend*
4496 Also, Begin contains '! Control'. A Prepend must be a
4497 '! Control', which means it must also be a Begin. What it
4498 comes down to is that if we match Prepend* and then find no
4499 suitable Begin afterwards, that if we backtrack the last
4500 Prepend, that one will be a suitable Begin.
4505 if (! utf8_target) {
4507 /* Match either CR LF or '.', as all the other possibilities
4509 locinput++; /* Match the . or CR */
4510 if (nextchr == '\r' /* And if it was CR, and the next is LF,
4512 && locinput < PL_regeol
4513 && UCHARAT(locinput) == '\n')
4520 /* Utf8: See if is ( CR LF ); already know that locinput <
4521 * PL_regeol, so locinput+1 is in bounds */
4522 if ( nextchr == '\r' && locinput+1 < PL_regeol
4523 && UCHARAT(locinput + 1) == '\n')
4530 /* In case have to backtrack to beginning, then match '.' */
4531 char *starting = locinput;
4533 /* In case have to backtrack the last prepend */
4534 char *previous_prepend = NULL;
4536 LOAD_UTF8_CHARCLASS_GCB();
4538 /* Match (prepend)* */
4539 while (locinput < PL_regeol
4540 && (len = is_GCB_Prepend_utf8(locinput)))
4542 previous_prepend = locinput;
4546 /* As noted above, if we matched a prepend character, but
4547 * the next thing won't match, back off the last prepend we
4548 * matched, as it is guaranteed to match the begin */
4549 if (previous_prepend
4550 && (locinput >= PL_regeol
4551 || (! swash_fetch(PL_utf8_X_regular_begin,
4552 (U8*)locinput, utf8_target)
4553 && ! is_GCB_SPECIAL_BEGIN_START_utf8(locinput)))
4556 locinput = previous_prepend;
4559 /* Note that here we know PL_regeol > locinput, as we
4560 * tested that upon input to this switch case, and if we
4561 * moved locinput forward, we tested the result just above
4562 * and it either passed, or we backed off so that it will
4564 if (swash_fetch(PL_utf8_X_regular_begin,
4565 (U8*)locinput, utf8_target)) {
4566 locinput += UTF8SKIP(locinput);
4568 else if (! is_GCB_SPECIAL_BEGIN_START_utf8(locinput)) {
4570 /* Here did not match the required 'Begin' in the
4571 * second term. So just match the very first
4572 * character, the '.' of the final term of the regex */
4573 locinput = starting + UTF8SKIP(starting);
4577 /* Here is a special begin. It can be composed of
4578 * several individual characters. One possibility is
4580 if ((len = is_GCB_RI_utf8(locinput))) {
4582 while (locinput < PL_regeol
4583 && (len = is_GCB_RI_utf8(locinput)))
4587 } else if ((len = is_GCB_T_utf8(locinput))) {
4588 /* Another possibility is T+ */
4590 while (locinput < PL_regeol
4591 && (len = is_GCB_T_utf8(locinput)))
4597 /* Here, neither RI+ nor T+; must be some other
4598 * Hangul. That means it is one of the others: L,
4599 * LV, LVT or V, and matches:
4600 * L* (L | LVT T* | V * V* T* | LV V* T*) */
4603 while (locinput < PL_regeol
4604 && (len = is_GCB_L_utf8(locinput)))
4609 /* Here, have exhausted L*. If the next character
4610 * is not an LV, LVT nor V, it means we had to have
4611 * at least one L, so matches L+ in the original
4612 * equation, we have a complete hangul syllable.
4615 if (locinput < PL_regeol
4616 && is_GCB_LV_LVT_V_utf8(locinput))
4618 /* Otherwise keep going. Must be LV, LVT or V.
4619 * See if LVT, by first ruling out V, then LV */
4620 if (! is_GCB_V_utf8(locinput)
4621 /* All but every TCount one is LV */
4622 && (valid_utf8_to_uvchr((U8 *) locinput,
4627 locinput += UTF8SKIP(locinput);
4630 /* Must be V or LV. Take it, then match
4632 locinput += UTF8SKIP(locinput);
4633 while (locinput < PL_regeol
4634 && (len = is_GCB_V_utf8(locinput)))
4640 /* And any of LV, LVT, or V can be followed
4642 while (locinput < PL_regeol
4643 && (len = is_GCB_T_utf8(locinput)))
4651 /* Match any extender */
4652 while (locinput < PL_regeol
4653 && swash_fetch(PL_utf8_X_extend,
4654 (U8*)locinput, utf8_target))
4656 locinput += UTF8SKIP(locinput);
4660 if (locinput > PL_regeol) sayNO;
4664 case NREFFL: /* /\g{name}/il */
4665 { /* The capture buffer cases. The ones beginning with N for the
4666 named buffers just convert to the equivalent numbered and
4667 pretend they were called as the corresponding numbered buffer
4669 /* don't initialize these in the declaration, it makes C++
4674 const U8 *fold_array;
4677 PL_reg_flags |= RF_tainted;
4678 folder = foldEQ_locale;
4679 fold_array = PL_fold_locale;
4681 utf8_fold_flags = FOLDEQ_UTF8_LOCALE;
4684 case NREFFA: /* /\g{name}/iaa */
4685 folder = foldEQ_latin1;
4686 fold_array = PL_fold_latin1;
4688 utf8_fold_flags = FOLDEQ_UTF8_NOMIX_ASCII;
4691 case NREFFU: /* /\g{name}/iu */
4692 folder = foldEQ_latin1;
4693 fold_array = PL_fold_latin1;
4695 utf8_fold_flags = 0;
4698 case NREFF: /* /\g{name}/i */
4700 fold_array = PL_fold;
4702 utf8_fold_flags = 0;
4705 case NREF: /* /\g{name}/ */
4709 utf8_fold_flags = 0;
4712 /* For the named back references, find the corresponding buffer
4714 n = reg_check_named_buff_matched(rex,scan);
4719 goto do_nref_ref_common;
4721 case REFFL: /* /\1/il */
4722 PL_reg_flags |= RF_tainted;
4723 folder = foldEQ_locale;
4724 fold_array = PL_fold_locale;
4725 utf8_fold_flags = FOLDEQ_UTF8_LOCALE;
4728 case REFFA: /* /\1/iaa */
4729 folder = foldEQ_latin1;
4730 fold_array = PL_fold_latin1;
4731 utf8_fold_flags = FOLDEQ_UTF8_NOMIX_ASCII;
4734 case REFFU: /* /\1/iu */
4735 folder = foldEQ_latin1;
4736 fold_array = PL_fold_latin1;
4737 utf8_fold_flags = 0;
4740 case REFF: /* /\1/i */
4742 fold_array = PL_fold;
4743 utf8_fold_flags = 0;
4746 case REF: /* /\1/ */
4749 utf8_fold_flags = 0;
4753 n = ARG(scan); /* which paren pair */
4756 ln = rex->offs[n].start;
4757 PL_reg_leftiter = PL_reg_maxiter; /* Void cache */
4758 if (rex->lastparen < n || ln == -1)
4759 sayNO; /* Do not match unless seen CLOSEn. */
4760 if (ln == rex->offs[n].end)
4764 if (type != REF /* REF can do byte comparison */
4765 && (utf8_target || type == REFFU))
4766 { /* XXX handle REFFL better */
4767 char * limit = PL_regeol;
4769 /* This call case insensitively compares the entire buffer
4770 * at s, with the current input starting at locinput, but
4771 * not going off the end given by PL_regeol, and returns in
4772 * <limit> upon success, how much of the current input was
4774 if (! foldEQ_utf8_flags(s, NULL, rex->offs[n].end - ln, utf8_target,
4775 locinput, &limit, 0, utf8_target, utf8_fold_flags))
4783 /* Not utf8: Inline the first character, for speed. */
4784 if (!NEXTCHR_IS_EOS &&
4785 UCHARAT(s) != nextchr &&
4787 UCHARAT(s) != fold_array[nextchr]))
4789 ln = rex->offs[n].end - ln;
4790 if (locinput + ln > PL_regeol)
4792 if (ln > 1 && (type == REF
4793 ? memNE(s, locinput, ln)
4794 : ! folder(s, locinput, ln)))
4800 case NOTHING: /* null op; e.g. the 'nothing' following
4801 * the '*' in m{(a+|b)*}' */
4803 case TAIL: /* placeholder while compiling (A|B|C) */
4806 case BACK: /* ??? doesn't appear to be used ??? */
4810 #define ST st->u.eval
4815 regexp_internal *rei;
4816 regnode *startpoint;
4818 case GOSTART: /* (?R) */
4819 case GOSUB: /* /(...(?1))/ /(...(?&foo))/ */
4820 if (cur_eval && cur_eval->locinput==locinput) {
4821 if (cur_eval->u.eval.close_paren == (U32)ARG(scan))
4822 Perl_croak(aTHX_ "Infinite recursion in regex");
4823 if ( ++nochange_depth > max_nochange_depth )
4825 "Pattern subroutine nesting without pos change"
4826 " exceeded limit in regex");
4833 if (OP(scan)==GOSUB) {
4834 startpoint = scan + ARG2L(scan);
4835 ST.close_paren = ARG(scan);
4837 startpoint = rei->program+1;
4840 goto eval_recurse_doit;
4841 assert(0); /* NOTREACHED */
4843 case EVAL: /* /(?{A})B/ /(??{A})B/ and /(?(?{A})X|Y)B/ */
4844 if (cur_eval && cur_eval->locinput==locinput) {
4845 if ( ++nochange_depth > max_nochange_depth )
4846 Perl_croak(aTHX_ "EVAL without pos change exceeded limit in regex");
4851 /* execute the code in the {...} */
4855 OP * const oop = PL_op;
4856 COP * const ocurcop = PL_curcop;
4858 char *saved_regeol = PL_regeol;
4859 struct re_save_state saved_state;
4862 /* save *all* paren positions */
4863 regcppush(rex, 0, maxopenparen);
4864 REGCP_SET(runops_cp);
4866 /* To not corrupt the existing regex state while executing the
4867 * eval we would normally put it on the save stack, like with
4868 * save_re_context. However, re-evals have a weird scoping so we
4869 * can't just add ENTER/LEAVE here. With that, things like
4871 * (?{$a=2})(a(?{local$a=$a+1}))*aak*c(?{$b=$a})
4873 * would break, as they expect the localisation to be unwound
4874 * only when the re-engine backtracks through the bit that
4877 * What we do instead is just saving the state in a local c
4880 Copy(&PL_reg_state, &saved_state, 1, struct re_save_state);
4882 PL_reg_state.re_reparsing = FALSE;
4885 caller_cv = find_runcv(NULL);
4889 if (rexi->data->what[n] == 'r') { /* code from an external qr */
4891 (REGEXP*)(rexi->data->data[n])
4894 nop = (OP*)rexi->data->data[n+1];
4896 else if (rexi->data->what[n] == 'l') { /* literal code */
4898 nop = (OP*)rexi->data->data[n];
4899 assert(CvDEPTH(newcv));
4902 /* literal with own CV */
4903 assert(rexi->data->what[n] == 'L');
4904 newcv = rex->qr_anoncv;
4905 nop = (OP*)rexi->data->data[n];
4908 /* normally if we're about to execute code from the same
4909 * CV that we used previously, we just use the existing
4910 * CX stack entry. However, its possible that in the
4911 * meantime we may have backtracked, popped from the save
4912 * stack, and undone the SAVECOMPPAD(s) associated with
4913 * PUSH_MULTICALL; in which case PL_comppad no longer
4914 * points to newcv's pad. */
4915 if (newcv != last_pushed_cv || PL_comppad != last_pad)
4917 I32 depth = (newcv == caller_cv) ? 0 : 1;
4918 if (last_pushed_cv) {
4919 CHANGE_MULTICALL_WITHDEPTH(newcv, depth);
4922 PUSH_MULTICALL_WITHDEPTH(newcv, depth);
4924 last_pushed_cv = newcv;
4927 /* these assignments are just to silence compiler
4929 multicall_cop = NULL;
4932 last_pad = PL_comppad;
4934 /* the initial nextstate you would normally execute
4935 * at the start of an eval (which would cause error
4936 * messages to come from the eval), may be optimised
4937 * away from the execution path in the regex code blocks;
4938 * so manually set PL_curcop to it initially */
4940 OP *o = cUNOPx(nop)->op_first;
4941 assert(o->op_type == OP_NULL);
4942 if (o->op_targ == OP_SCOPE) {
4943 o = cUNOPo->op_first;
4946 assert(o->op_targ == OP_LEAVE);
4947 o = cUNOPo->op_first;
4948 assert(o->op_type == OP_ENTER);
4952 if (o->op_type != OP_STUB) {
4953 assert( o->op_type == OP_NEXTSTATE
4954 || o->op_type == OP_DBSTATE
4955 || (o->op_type == OP_NULL
4956 && ( o->op_targ == OP_NEXTSTATE
4957 || o->op_targ == OP_DBSTATE
4961 PL_curcop = (COP*)o;
4966 DEBUG_STATE_r( PerlIO_printf(Perl_debug_log,
4967 " re EVAL PL_op=0x%"UVxf"\n", PTR2UV(nop)) );
4969 rex->offs[0].end = PL_reg_magic->mg_len = locinput - PL_bostr;
4972 SV *sv_mrk = get_sv("REGMARK", 1);
4973 sv_setsv(sv_mrk, sv_yes_mark);
4976 /* we don't use MULTICALL here as we want to call the
4977 * first op of the block of interest, rather than the
4978 * first op of the sub */
4979 before = (IV)(SP-PL_stack_base);
4981 CALLRUNOPS(aTHX); /* Scalar context. */
4983 if ((IV)(SP-PL_stack_base) == before)
4984 ret = &PL_sv_undef; /* protect against empty (?{}) blocks. */
4990 /* before restoring everything, evaluate the returned
4991 * value, so that 'uninit' warnings don't use the wrong
4992 * PL_op or pad. Also need to process any magic vars
4993 * (e.g. $1) *before* parentheses are restored */
4998 if (logical == 0) /* (?{})/ */
4999 sv_setsv(save_scalar(PL_replgv), ret); /* $^R */
5000 else if (logical == 1) { /* /(?(?{...})X|Y)/ */
5001 sw = cBOOL(SvTRUE(ret));
5004 else { /* /(??{}) */
5005 /* if its overloaded, let the regex compiler handle
5006 * it; otherwise extract regex, or stringify */
5007 if (!SvAMAGIC(ret)) {
5011 if (SvTYPE(sv) == SVt_REGEXP)
5012 re_sv = (REGEXP*) sv;
5013 else if (SvSMAGICAL(sv)) {
5014 MAGIC *mg = mg_find(sv, PERL_MAGIC_qr);
5016 re_sv = (REGEXP *) mg->mg_obj;
5019 /* force any magic, undef warnings here */
5021 ret = sv_mortalcopy(ret);
5022 (void) SvPV_force_nolen(ret);
5028 Copy(&saved_state, &PL_reg_state, 1, struct re_save_state);
5030 /* *** Note that at this point we don't restore
5031 * PL_comppad, (or pop the CxSUB) on the assumption it may
5032 * be used again soon. This is safe as long as nothing
5033 * in the regexp code uses the pad ! */
5035 PL_curcop = ocurcop;
5036 PL_regeol = saved_regeol;
5037 S_regcp_restore(aTHX_ rex, runops_cp, &maxopenparen);
5043 /* only /(??{})/ from now on */
5046 /* extract RE object from returned value; compiling if
5050 re_sv = reg_temp_copy(NULL, re_sv);
5055 if (SvUTF8(ret) && IN_BYTES) {
5056 /* In use 'bytes': make a copy of the octet
5057 * sequence, but without the flag on */
5059 const char *const p = SvPV(ret, len);
5060 ret = newSVpvn_flags(p, len, SVs_TEMP);
5062 if (rex->intflags & PREGf_USE_RE_EVAL)
5063 pm_flags |= PMf_USE_RE_EVAL;
5065 /* if we got here, it should be an engine which
5066 * supports compiling code blocks and stuff */
5067 assert(rex->engine && rex->engine->op_comp);
5068 assert(!(scan->flags & ~RXf_PMf_COMPILETIME));
5069 re_sv = rex->engine->op_comp(aTHX_ &ret, 1, NULL,
5070 rex->engine, NULL, NULL,
5071 /* copy /msix etc to inner pattern */
5076 & (SVs_TEMP | SVs_PADTMP | SVf_READONLY
5078 /* This isn't a first class regexp. Instead, it's
5079 caching a regexp onto an existing, Perl visible
5081 sv_magic(ret, MUTABLE_SV(re_sv), PERL_MAGIC_qr, 0, 0);
5083 /* safe to do now that any $1 etc has been
5084 * interpolated into the new pattern string and
5086 S_regcp_restore(aTHX_ rex, runops_cp, &maxopenparen);
5091 RXp_MATCH_COPIED_off(re);
5092 re->subbeg = rex->subbeg;
5093 re->sublen = rex->sublen;
5094 re->suboffset = rex->suboffset;
5095 re->subcoffset = rex->subcoffset;
5098 debug_start_match(re_sv, utf8_target, locinput, PL_regeol,
5099 "Matching embedded");
5101 startpoint = rei->program + 1;
5102 ST.close_paren = 0; /* only used for GOSUB */
5104 eval_recurse_doit: /* Share code with GOSUB below this line */
5105 /* run the pattern returned from (??{...}) */
5107 /* Save *all* the positions. */
5108 ST.cp = regcppush(rex, 0, maxopenparen);
5109 REGCP_SET(ST.lastcp);
5112 re->lastcloseparen = 0;
5116 /* XXXX This is too dramatic a measure... */
5119 ST.toggle_reg_flags = PL_reg_flags;
5121 PL_reg_flags |= RF_utf8;
5123 PL_reg_flags &= ~RF_utf8;
5124 ST.toggle_reg_flags ^= PL_reg_flags; /* diff of old and new */
5126 ST.prev_rex = rex_sv;
5127 ST.prev_curlyx = cur_curlyx;
5129 SET_reg_curpm(rex_sv);
5134 ST.prev_eval = cur_eval;
5136 /* now continue from first node in postoned RE */
5137 PUSH_YES_STATE_GOTO(EVAL_AB, startpoint, locinput);
5138 assert(0); /* NOTREACHED */
5141 case EVAL_AB: /* cleanup after a successful (??{A})B */
5142 /* note: this is called twice; first after popping B, then A */
5143 PL_reg_flags ^= ST.toggle_reg_flags;
5144 rex_sv = ST.prev_rex;
5145 SET_reg_curpm(rex_sv);
5146 rex = ReANY(rex_sv);
5147 rexi = RXi_GET(rex);
5149 cur_eval = ST.prev_eval;
5150 cur_curlyx = ST.prev_curlyx;
5152 /* XXXX This is too dramatic a measure... */
5154 if ( nochange_depth )
5159 case EVAL_AB_fail: /* unsuccessfully ran A or B in (??{A})B */
5160 /* note: this is called twice; first after popping B, then A */
5161 PL_reg_flags ^= ST.toggle_reg_flags;
5162 rex_sv = ST.prev_rex;
5163 SET_reg_curpm(rex_sv);
5164 rex = ReANY(rex_sv);
5165 rexi = RXi_GET(rex);
5167 REGCP_UNWIND(ST.lastcp);
5168 regcppop(rex, &maxopenparen);
5169 cur_eval = ST.prev_eval;
5170 cur_curlyx = ST.prev_curlyx;
5171 /* XXXX This is too dramatic a measure... */
5173 if ( nochange_depth )
5179 n = ARG(scan); /* which paren pair */
5180 rex->offs[n].start_tmp = locinput - PL_bostr;
5181 if (n > maxopenparen)
5183 DEBUG_BUFFERS_r(PerlIO_printf(Perl_debug_log,
5184 "rex=0x%"UVxf" offs=0x%"UVxf": \\%"UVuf": set %"IVdf" tmp; maxopenparen=%"UVuf"\n",
5188 (IV)rex->offs[n].start_tmp,
5194 /* XXX really need to log other places start/end are set too */
5195 #define CLOSE_CAPTURE \
5196 rex->offs[n].start = rex->offs[n].start_tmp; \
5197 rex->offs[n].end = locinput - PL_bostr; \
5198 DEBUG_BUFFERS_r(PerlIO_printf(Perl_debug_log, \
5199 "rex=0x%"UVxf" offs=0x%"UVxf": \\%"UVuf": set %"IVdf"..%"IVdf"\n", \
5201 PTR2UV(rex->offs), \
5203 (IV)rex->offs[n].start, \
5204 (IV)rex->offs[n].end \
5208 n = ARG(scan); /* which paren pair */
5210 if (n > rex->lastparen)
5212 rex->lastcloseparen = n;
5213 if (cur_eval && cur_eval->u.eval.close_paren == n) {
5218 case ACCEPT: /* (*ACCEPT) */
5222 cursor && OP(cursor)!=END;
5223 cursor=regnext(cursor))
5225 if ( OP(cursor)==CLOSE ){
5227 if ( n <= lastopen ) {
5229 if (n > rex->lastparen)
5231 rex->lastcloseparen = n;
5232 if ( n == ARG(scan) || (cur_eval &&
5233 cur_eval->u.eval.close_paren == n))
5242 case GROUPP: /* (?(1)) */
5243 n = ARG(scan); /* which paren pair */
5244 sw = cBOOL(rex->lastparen >= n && rex->offs[n].end != -1);
5247 case NGROUPP: /* (?(<name>)) */
5248 /* reg_check_named_buff_matched returns 0 for no match */
5249 sw = cBOOL(0 < reg_check_named_buff_matched(rex,scan));
5252 case INSUBP: /* (?(R)) */
5254 sw = (cur_eval && (!n || cur_eval->u.eval.close_paren == n));
5257 case DEFINEP: /* (?(DEFINE)) */
5261 case IFTHEN: /* (?(cond)A|B) */
5262 PL_reg_leftiter = PL_reg_maxiter; /* Void cache */
5264 next = NEXTOPER(NEXTOPER(scan));
5266 next = scan + ARG(scan);
5267 if (OP(next) == IFTHEN) /* Fake one. */
5268 next = NEXTOPER(NEXTOPER(next));
5272 case LOGICAL: /* modifier for EVAL and IFMATCH */
5273 logical = scan->flags;
5276 /*******************************************************************
5278 The CURLYX/WHILEM pair of ops handle the most generic case of the /A*B/
5279 pattern, where A and B are subpatterns. (For simple A, CURLYM or
5280 STAR/PLUS/CURLY/CURLYN are used instead.)
5282 A*B is compiled as <CURLYX><A><WHILEM><B>
5284 On entry to the subpattern, CURLYX is called. This pushes a CURLYX
5285 state, which contains the current count, initialised to -1. It also sets
5286 cur_curlyx to point to this state, with any previous value saved in the
5289 CURLYX then jumps straight to the WHILEM op, rather than executing A,
5290 since the pattern may possibly match zero times (i.e. it's a while {} loop
5291 rather than a do {} while loop).
5293 Each entry to WHILEM represents a successful match of A. The count in the
5294 CURLYX block is incremented, another WHILEM state is pushed, and execution
5295 passes to A or B depending on greediness and the current count.
5297 For example, if matching against the string a1a2a3b (where the aN are
5298 substrings that match /A/), then the match progresses as follows: (the
5299 pushed states are interspersed with the bits of strings matched so far):
5302 <CURLYX cnt=0><WHILEM>
5303 <CURLYX cnt=1><WHILEM> a1 <WHILEM>
5304 <CURLYX cnt=2><WHILEM> a1 <WHILEM> a2 <WHILEM>
5305 <CURLYX cnt=3><WHILEM> a1 <WHILEM> a2 <WHILEM> a3 <WHILEM>
5306 <CURLYX cnt=3><WHILEM> a1 <WHILEM> a2 <WHILEM> a3 <WHILEM> b
5308 (Contrast this with something like CURLYM, which maintains only a single
5312 a1 <CURLYM cnt=1> a2
5313 a1 a2 <CURLYM cnt=2> a3
5314 a1 a2 a3 <CURLYM cnt=3> b
5317 Each WHILEM state block marks a point to backtrack to upon partial failure
5318 of A or B, and also contains some minor state data related to that
5319 iteration. The CURLYX block, pointed to by cur_curlyx, contains the
5320 overall state, such as the count, and pointers to the A and B ops.
5322 This is complicated slightly by nested CURLYX/WHILEM's. Since cur_curlyx
5323 must always point to the *current* CURLYX block, the rules are:
5325 When executing CURLYX, save the old cur_curlyx in the CURLYX state block,
5326 and set cur_curlyx to point the new block.
5328 When popping the CURLYX block after a successful or unsuccessful match,
5329 restore the previous cur_curlyx.
5331 When WHILEM is about to execute B, save the current cur_curlyx, and set it
5332 to the outer one saved in the CURLYX block.
5334 When popping the WHILEM block after a successful or unsuccessful B match,
5335 restore the previous cur_curlyx.
5337 Here's an example for the pattern (AI* BI)*BO
5338 I and O refer to inner and outer, C and W refer to CURLYX and WHILEM:
5341 curlyx backtrack stack
5342 ------ ---------------
5344 CO <CO prev=NULL> <WO>
5345 CI <CO prev=NULL> <WO> <CI prev=CO> <WI> ai
5346 CO <CO prev=NULL> <WO> <CI prev=CO> <WI> ai <WI prev=CI> bi
5347 NULL <CO prev=NULL> <WO> <CI prev=CO> <WI> ai <WI prev=CI> bi <WO prev=CO> bo
5349 At this point the pattern succeeds, and we work back down the stack to
5350 clean up, restoring as we go:
5352 CO <CO prev=NULL> <WO> <CI prev=CO> <WI> ai <WI prev=CI> bi
5353 CI <CO prev=NULL> <WO> <CI prev=CO> <WI> ai
5354 CO <CO prev=NULL> <WO>
5357 *******************************************************************/
5359 #define ST st->u.curlyx
5361 case CURLYX: /* start of /A*B/ (for complex A) */
5363 /* No need to save/restore up to this paren */
5364 I32 parenfloor = scan->flags;
5366 assert(next); /* keep Coverity happy */
5367 if (OP(PREVOPER(next)) == NOTHING) /* LONGJMP */
5370 /* XXXX Probably it is better to teach regpush to support
5371 parenfloor > maxopenparen ... */
5372 if (parenfloor > (I32)rex->lastparen)
5373 parenfloor = rex->lastparen; /* Pessimization... */
5375 ST.prev_curlyx= cur_curlyx;
5377 ST.cp = PL_savestack_ix;
5379 /* these fields contain the state of the current curly.
5380 * they are accessed by subsequent WHILEMs */
5381 ST.parenfloor = parenfloor;
5386 ST.count = -1; /* this will be updated by WHILEM */
5387 ST.lastloc = NULL; /* this will be updated by WHILEM */
5389 PUSH_YES_STATE_GOTO(CURLYX_end, PREVOPER(next), locinput);
5390 assert(0); /* NOTREACHED */
5393 case CURLYX_end: /* just finished matching all of A*B */
5394 cur_curlyx = ST.prev_curlyx;
5396 assert(0); /* NOTREACHED */
5398 case CURLYX_end_fail: /* just failed to match all of A*B */
5400 cur_curlyx = ST.prev_curlyx;
5402 assert(0); /* NOTREACHED */
5406 #define ST st->u.whilem
5408 case WHILEM: /* just matched an A in /A*B/ (for complex A) */
5410 /* see the discussion above about CURLYX/WHILEM */
5412 int min = ARG1(cur_curlyx->u.curlyx.me);
5413 int max = ARG2(cur_curlyx->u.curlyx.me);
5414 regnode *A = NEXTOPER(cur_curlyx->u.curlyx.me) + EXTRA_STEP_2ARGS;
5416 assert(cur_curlyx); /* keep Coverity happy */
5417 n = ++cur_curlyx->u.curlyx.count; /* how many A's matched */
5418 ST.save_lastloc = cur_curlyx->u.curlyx.lastloc;
5419 ST.cache_offset = 0;
5423 DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log,
5424 "%*s whilem: matched %ld out of %d..%d\n",
5425 REPORT_CODE_OFF+depth*2, "", (long)n, min, max)
5428 /* First just match a string of min A's. */
5431 ST.cp = regcppush(rex, cur_curlyx->u.curlyx.parenfloor,
5433 cur_curlyx->u.curlyx.lastloc = locinput;
5434 REGCP_SET(ST.lastcp);
5436 PUSH_STATE_GOTO(WHILEM_A_pre, A, locinput);
5437 assert(0); /* NOTREACHED */
5440 /* If degenerate A matches "", assume A done. */
5442 if (locinput == cur_curlyx->u.curlyx.lastloc) {
5443 DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log,
5444 "%*s whilem: empty match detected, trying continuation...\n",
5445 REPORT_CODE_OFF+depth*2, "")
5447 goto do_whilem_B_max;
5450 /* super-linear cache processing */
5454 if (!PL_reg_maxiter) {
5455 /* start the countdown: Postpone detection until we
5456 * know the match is not *that* much linear. */
5457 PL_reg_maxiter = (PL_regeol - PL_bostr + 1) * (scan->flags>>4);
5458 /* possible overflow for long strings and many CURLYX's */
5459 if (PL_reg_maxiter < 0)
5460 PL_reg_maxiter = I32_MAX;
5461 PL_reg_leftiter = PL_reg_maxiter;
5464 if (PL_reg_leftiter-- == 0) {
5465 /* initialise cache */
5466 const I32 size = (PL_reg_maxiter + 7)/8;
5467 if (PL_reg_poscache) {
5468 if ((I32)PL_reg_poscache_size < size) {
5469 Renew(PL_reg_poscache, size, char);
5470 PL_reg_poscache_size = size;
5472 Zero(PL_reg_poscache, size, char);
5475 PL_reg_poscache_size = size;
5476 Newxz(PL_reg_poscache, size, char);
5478 DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log,
5479 "%swhilem: Detected a super-linear match, switching on caching%s...\n",
5480 PL_colors[4], PL_colors[5])
5484 if (PL_reg_leftiter < 0) {
5485 /* have we already failed at this position? */
5487 offset = (scan->flags & 0xf) - 1
5488 + (locinput - PL_bostr) * (scan->flags>>4);
5489 mask = 1 << (offset % 8);
5491 if (PL_reg_poscache[offset] & mask) {
5492 DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log,
5493 "%*s whilem: (cache) already tried at this position...\n",
5494 REPORT_CODE_OFF+depth*2, "")
5496 sayNO; /* cache records failure */
5498 ST.cache_offset = offset;
5499 ST.cache_mask = mask;
5503 /* Prefer B over A for minimal matching. */
5505 if (cur_curlyx->u.curlyx.minmod) {
5506 ST.save_curlyx = cur_curlyx;
5507 cur_curlyx = cur_curlyx->u.curlyx.prev_curlyx;
5508 ST.cp = regcppush(rex, ST.save_curlyx->u.curlyx.parenfloor,
5510 REGCP_SET(ST.lastcp);
5511 PUSH_YES_STATE_GOTO(WHILEM_B_min, ST.save_curlyx->u.curlyx.B,
5513 assert(0); /* NOTREACHED */
5516 /* Prefer A over B for maximal matching. */
5518 if (n < max) { /* More greed allowed? */
5519 ST.cp = regcppush(rex, cur_curlyx->u.curlyx.parenfloor,
5521 cur_curlyx->u.curlyx.lastloc = locinput;
5522 REGCP_SET(ST.lastcp);
5523 PUSH_STATE_GOTO(WHILEM_A_max, A, locinput);
5524 assert(0); /* NOTREACHED */
5526 goto do_whilem_B_max;
5528 assert(0); /* NOTREACHED */
5530 case WHILEM_B_min: /* just matched B in a minimal match */
5531 case WHILEM_B_max: /* just matched B in a maximal match */
5532 cur_curlyx = ST.save_curlyx;
5534 assert(0); /* NOTREACHED */
5536 case WHILEM_B_max_fail: /* just failed to match B in a maximal match */
5537 cur_curlyx = ST.save_curlyx;
5538 cur_curlyx->u.curlyx.lastloc = ST.save_lastloc;
5539 cur_curlyx->u.curlyx.count--;
5541 assert(0); /* NOTREACHED */
5543 case WHILEM_A_min_fail: /* just failed to match A in a minimal match */
5545 case WHILEM_A_pre_fail: /* just failed to match even minimal A */
5546 REGCP_UNWIND(ST.lastcp);
5547 regcppop(rex, &maxopenparen);
5548 cur_curlyx->u.curlyx.lastloc = ST.save_lastloc;
5549 cur_curlyx->u.curlyx.count--;
5551 assert(0); /* NOTREACHED */
5553 case WHILEM_A_max_fail: /* just failed to match A in a maximal match */
5554 REGCP_UNWIND(ST.lastcp);
5555 regcppop(rex, &maxopenparen); /* Restore some previous $<digit>s? */
5556 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
5557 "%*s whilem: failed, trying continuation...\n",
5558 REPORT_CODE_OFF+depth*2, "")
5561 if (cur_curlyx->u.curlyx.count >= REG_INFTY
5562 && ckWARN(WARN_REGEXP)
5563 && !(PL_reg_flags & RF_warned))
5565 PL_reg_flags |= RF_warned;
5566 Perl_warner(aTHX_ packWARN(WARN_REGEXP),
5567 "Complex regular subexpression recursion limit (%d) "
5573 ST.save_curlyx = cur_curlyx;
5574 cur_curlyx = cur_curlyx->u.curlyx.prev_curlyx;
5575 PUSH_YES_STATE_GOTO(WHILEM_B_max, ST.save_curlyx->u.curlyx.B,
5577 assert(0); /* NOTREACHED */
5579 case WHILEM_B_min_fail: /* just failed to match B in a minimal match */
5580 cur_curlyx = ST.save_curlyx;
5581 REGCP_UNWIND(ST.lastcp);
5582 regcppop(rex, &maxopenparen);
5584 if (cur_curlyx->u.curlyx.count >= /*max*/ARG2(cur_curlyx->u.curlyx.me)) {
5585 /* Maximum greed exceeded */
5586 if (cur_curlyx->u.curlyx.count >= REG_INFTY
5587 && ckWARN(WARN_REGEXP)
5588 && !(PL_reg_flags & RF_warned))
5590 PL_reg_flags |= RF_warned;
5591 Perl_warner(aTHX_ packWARN(WARN_REGEXP),
5592 "Complex regular subexpression recursion "
5593 "limit (%d) exceeded",
5596 cur_curlyx->u.curlyx.count--;
5600 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
5601 "%*s trying longer...\n", REPORT_CODE_OFF+depth*2, "")
5603 /* Try grabbing another A and see if it helps. */
5604 cur_curlyx->u.curlyx.lastloc = locinput;
5605 ST.cp = regcppush(rex, cur_curlyx->u.curlyx.parenfloor,
5607 REGCP_SET(ST.lastcp);
5608 PUSH_STATE_GOTO(WHILEM_A_min,
5609 /*A*/ NEXTOPER(ST.save_curlyx->u.curlyx.me) + EXTRA_STEP_2ARGS,
5611 assert(0); /* NOTREACHED */
5614 #define ST st->u.branch
5616 case BRANCHJ: /* /(...|A|...)/ with long next pointer */
5617 next = scan + ARG(scan);
5620 scan = NEXTOPER(scan);
5623 case BRANCH: /* /(...|A|...)/ */
5624 scan = NEXTOPER(scan); /* scan now points to inner node */
5625 ST.lastparen = rex->lastparen;
5626 ST.lastcloseparen = rex->lastcloseparen;
5627 ST.next_branch = next;
5630 /* Now go into the branch */
5632 PUSH_YES_STATE_GOTO(BRANCH_next, scan, locinput);
5634 PUSH_STATE_GOTO(BRANCH_next, scan, locinput);
5636 assert(0); /* NOTREACHED */
5638 case CUTGROUP: /* /(*THEN)/ */
5639 sv_yes_mark = st->u.mark.mark_name = scan->flags ? NULL :
5640 MUTABLE_SV(rexi->data->data[ ARG( scan ) ]);
5641 PUSH_STATE_GOTO(CUTGROUP_next, next, locinput);
5642 assert(0); /* NOTREACHED */
5644 case CUTGROUP_next_fail:
5647 if (st->u.mark.mark_name)
5648 sv_commit = st->u.mark.mark_name;
5650 assert(0); /* NOTREACHED */
5654 assert(0); /* NOTREACHED */
5656 case BRANCH_next_fail: /* that branch failed; try the next, if any */
5661 REGCP_UNWIND(ST.cp);
5662 UNWIND_PAREN(ST.lastparen, ST.lastcloseparen);
5663 scan = ST.next_branch;
5664 /* no more branches? */
5665 if (!scan || (OP(scan) != BRANCH && OP(scan) != BRANCHJ)) {
5667 PerlIO_printf( Perl_debug_log,
5668 "%*s %sBRANCH failed...%s\n",
5669 REPORT_CODE_OFF+depth*2, "",
5675 continue; /* execute next BRANCH[J] op */
5676 assert(0); /* NOTREACHED */
5678 case MINMOD: /* next op will be non-greedy, e.g. A*? */
5683 #define ST st->u.curlym
5685 case CURLYM: /* /A{m,n}B/ where A is fixed-length */
5687 /* This is an optimisation of CURLYX that enables us to push
5688 * only a single backtracking state, no matter how many matches
5689 * there are in {m,n}. It relies on the pattern being constant
5690 * length, with no parens to influence future backrefs
5694 scan = NEXTOPER(scan) + NODE_STEP_REGNODE;
5696 ST.lastparen = rex->lastparen;
5697 ST.lastcloseparen = rex->lastcloseparen;
5699 /* if paren positive, emulate an OPEN/CLOSE around A */
5701 U32 paren = ST.me->flags;
5702 if (paren > maxopenparen)
5703 maxopenparen = paren;
5704 scan += NEXT_OFF(scan); /* Skip former OPEN. */
5712 ST.c1 = CHRTEST_UNINIT;
5715 if (!(ST.minmod ? ARG1(ST.me) : ARG2(ST.me))) /* min/max */
5718 curlym_do_A: /* execute the A in /A{m,n}B/ */
5719 PUSH_YES_STATE_GOTO(CURLYM_A, ST.A, locinput); /* match A */
5720 assert(0); /* NOTREACHED */
5722 case CURLYM_A: /* we've just matched an A */
5724 /* after first match, determine A's length: u.curlym.alen */
5725 if (ST.count == 1) {
5726 if (PL_reg_match_utf8) {
5727 char *s = st->locinput;
5728 while (s < locinput) {
5734 ST.alen = locinput - st->locinput;
5737 ST.count = ST.minmod ? ARG1(ST.me) : ARG2(ST.me);
5740 PerlIO_printf(Perl_debug_log,
5741 "%*s CURLYM now matched %"IVdf" times, len=%"IVdf"...\n",
5742 (int)(REPORT_CODE_OFF+(depth*2)), "",
5743 (IV) ST.count, (IV)ST.alen)
5746 if (cur_eval && cur_eval->u.eval.close_paren &&
5747 cur_eval->u.eval.close_paren == (U32)ST.me->flags)
5751 I32 max = (ST.minmod ? ARG1(ST.me) : ARG2(ST.me));
5752 if ( max == REG_INFTY || ST.count < max )
5753 goto curlym_do_A; /* try to match another A */
5755 goto curlym_do_B; /* try to match B */
5757 case CURLYM_A_fail: /* just failed to match an A */
5758 REGCP_UNWIND(ST.cp);
5760 if (ST.minmod || ST.count < ARG1(ST.me) /* min*/
5761 || (cur_eval && cur_eval->u.eval.close_paren &&
5762 cur_eval->u.eval.close_paren == (U32)ST.me->flags))
5765 curlym_do_B: /* execute the B in /A{m,n}B/ */
5766 if (ST.c1 == CHRTEST_UNINIT) {
5767 /* calculate c1 and c2 for possible match of 1st char
5768 * following curly */
5769 ST.c1 = ST.c2 = CHRTEST_VOID;
5770 if (HAS_TEXT(ST.B) || JUMPABLE(ST.B)) {
5771 regnode *text_node = ST.B;
5772 if (! HAS_TEXT(text_node))
5773 FIND_NEXT_IMPT(text_node);
5776 (HAS_TEXT(text_node) && PL_regkind[OP(text_node)] == EXACT)
5778 But the former is redundant in light of the latter.
5780 if this changes back then the macro for
5781 IS_TEXT and friends need to change.
5783 if (PL_regkind[OP(text_node)] == EXACT) {
5784 if (! S_setup_EXACTISH_ST_c1_c2(aTHX_
5785 text_node, &ST.c1, ST.c1_utf8, &ST.c2, ST.c2_utf8))
5794 PerlIO_printf(Perl_debug_log,
5795 "%*s CURLYM trying tail with matches=%"IVdf"...\n",
5796 (int)(REPORT_CODE_OFF+(depth*2)),
5799 if (! NEXTCHR_IS_EOS && ST.c1 != CHRTEST_VOID) {
5800 if (! UTF8_IS_INVARIANT(nextchr) && utf8_target) {
5801 if (memNE(locinput, ST.c1_utf8, UTF8SKIP(locinput))
5802 && memNE(locinput, ST.c2_utf8, UTF8SKIP(locinput)))
5804 /* simulate B failing */
5806 PerlIO_printf(Perl_debug_log,
5807 "%*s CURLYM Fast bail next target=U+%"UVXf" c1=U+%"UVXf" c2=U+%"UVXf"\n",
5808 (int)(REPORT_CODE_OFF+(depth*2)),"",
5809 valid_utf8_to_uvchr((U8 *) locinput, NULL),
5810 valid_utf8_to_uvchr(ST.c1_utf8, NULL),
5811 valid_utf8_to_uvchr(ST.c2_utf8, NULL))
5813 state_num = CURLYM_B_fail;
5814 goto reenter_switch;
5817 else if (nextchr != ST.c1 && nextchr != ST.c2) {
5818 /* simulate B failing */
5820 PerlIO_printf(Perl_debug_log,
5821 "%*s CURLYM Fast bail next target=U+%X c1=U+%X c2=U+%X\n",
5822 (int)(REPORT_CODE_OFF+(depth*2)),"",
5823 (int) nextchr, ST.c1, ST.c2)
5825 state_num = CURLYM_B_fail;
5826 goto reenter_switch;
5831 /* emulate CLOSE: mark current A as captured */
5832 I32 paren = ST.me->flags;
5834 rex->offs[paren].start
5835 = HOPc(locinput, -ST.alen) - PL_bostr;
5836 rex->offs[paren].end = locinput - PL_bostr;
5837 if ((U32)paren > rex->lastparen)
5838 rex->lastparen = paren;
5839 rex->lastcloseparen = paren;
5842 rex->offs[paren].end = -1;
5843 if (cur_eval && cur_eval->u.eval.close_paren &&
5844 cur_eval->u.eval.close_paren == (U32)ST.me->flags)
5853 PUSH_STATE_GOTO(CURLYM_B, ST.B, locinput); /* match B */
5854 assert(0); /* NOTREACHED */
5856 case CURLYM_B_fail: /* just failed to match a B */
5857 REGCP_UNWIND(ST.cp);
5858 UNWIND_PAREN(ST.lastparen, ST.lastcloseparen);
5860 I32 max = ARG2(ST.me);
5861 if (max != REG_INFTY && ST.count == max)
5863 goto curlym_do_A; /* try to match a further A */
5865 /* backtrack one A */
5866 if (ST.count == ARG1(ST.me) /* min */)
5869 SET_locinput(HOPc(locinput, -ST.alen));
5870 goto curlym_do_B; /* try to match B */
5873 #define ST st->u.curly
5875 #define CURLY_SETPAREN(paren, success) \
5878 rex->offs[paren].start = HOPc(locinput, -1) - PL_bostr; \
5879 rex->offs[paren].end = locinput - PL_bostr; \
5880 if (paren > rex->lastparen) \
5881 rex->lastparen = paren; \
5882 rex->lastcloseparen = paren; \
5885 rex->offs[paren].end = -1; \
5886 rex->lastparen = ST.lastparen; \
5887 rex->lastcloseparen = ST.lastcloseparen; \
5891 case STAR: /* /A*B/ where A is width 1 char */
5895 scan = NEXTOPER(scan);
5898 case PLUS: /* /A+B/ where A is width 1 char */
5902 scan = NEXTOPER(scan);
5905 case CURLYN: /* /(A){m,n}B/ where A is width 1 char */
5906 ST.paren = scan->flags; /* Which paren to set */
5907 ST.lastparen = rex->lastparen;
5908 ST.lastcloseparen = rex->lastcloseparen;
5909 if (ST.paren > maxopenparen)
5910 maxopenparen = ST.paren;
5911 ST.min = ARG1(scan); /* min to match */
5912 ST.max = ARG2(scan); /* max to match */
5913 if (cur_eval && cur_eval->u.eval.close_paren &&
5914 cur_eval->u.eval.close_paren == (U32)ST.paren) {
5918 scan = regnext(NEXTOPER(scan) + NODE_STEP_REGNODE);
5921 case CURLY: /* /A{m,n}B/ where A is width 1 char */
5923 ST.min = ARG1(scan); /* min to match */
5924 ST.max = ARG2(scan); /* max to match */
5925 scan = NEXTOPER(scan) + NODE_STEP_REGNODE;
5928 * Lookahead to avoid useless match attempts
5929 * when we know what character comes next.
5931 * Used to only do .*x and .*?x, but now it allows
5932 * for )'s, ('s and (?{ ... })'s to be in the way
5933 * of the quantifier and the EXACT-like node. -- japhy
5936 assert(ST.min <= ST.max);
5937 if (! HAS_TEXT(next) && ! JUMPABLE(next)) {
5938 ST.c1 = ST.c2 = CHRTEST_VOID;
5941 regnode *text_node = next;
5943 if (! HAS_TEXT(text_node))
5944 FIND_NEXT_IMPT(text_node);
5946 if (! HAS_TEXT(text_node))
5947 ST.c1 = ST.c2 = CHRTEST_VOID;
5949 if ( PL_regkind[OP(text_node)] != EXACT ) {
5950 ST.c1 = ST.c2 = CHRTEST_VOID;
5954 /* Currently we only get here when
5956 PL_rekind[OP(text_node)] == EXACT
5958 if this changes back then the macro for IS_TEXT and
5959 friends need to change. */
5960 if (! S_setup_EXACTISH_ST_c1_c2(aTHX_
5961 text_node, &ST.c1, ST.c1_utf8, &ST.c2, ST.c2_utf8))
5972 char *li = locinput;
5974 if (ST.min && regrepeat(rex, &li, ST.A, ST.min, depth) < ST.min)
5979 if (ST.c1 == CHRTEST_VOID)
5980 goto curly_try_B_min;
5982 ST.oldloc = locinput;
5984 /* set ST.maxpos to the furthest point along the
5985 * string that could possibly match */
5986 if (ST.max == REG_INFTY) {
5987 ST.maxpos = PL_regeol - 1;
5989 while (UTF8_IS_CONTINUATION(*(U8*)ST.maxpos))
5992 else if (utf8_target) {
5993 int m = ST.max - ST.min;
5994 for (ST.maxpos = locinput;
5995 m >0 && ST.maxpos < PL_regeol; m--)
5996 ST.maxpos += UTF8SKIP(ST.maxpos);
5999 ST.maxpos = locinput + ST.max - ST.min;
6000 if (ST.maxpos >= PL_regeol)
6001 ST.maxpos = PL_regeol - 1;
6003 goto curly_try_B_min_known;
6007 /* avoid taking address of locinput, so it can remain
6009 char *li = locinput;
6010 ST.count = regrepeat(rex, &li, ST.A, ST.max, depth);
6011 if (ST.count < ST.min)
6014 if ((ST.count > ST.min)
6015 && (PL_regkind[OP(ST.B)] == EOL) && (OP(ST.B) != MEOL))
6017 /* A{m,n} must come at the end of the string, there's
6018 * no point in backing off ... */
6020 /* ...except that $ and \Z can match before *and* after
6021 newline at the end. Consider "\n\n" =~ /\n+\Z\n/.
6022 We may back off by one in this case. */
6023 if (UCHARAT(locinput - 1) == '\n' && OP(ST.B) != EOS)
6027 goto curly_try_B_max;
6029 assert(0); /* NOTREACHED */
6032 case CURLY_B_min_known_fail:
6033 /* failed to find B in a non-greedy match where c1,c2 valid */
6035 REGCP_UNWIND(ST.cp);
6037 UNWIND_PAREN(ST.lastparen, ST.lastcloseparen);
6039 /* Couldn't or didn't -- move forward. */
6040 ST.oldloc = locinput;
6042 locinput += UTF8SKIP(locinput);
6046 curly_try_B_min_known:
6047 /* find the next place where 'B' could work, then call B */
6051 n = (ST.oldloc == locinput) ? 0 : 1;
6052 if (ST.c1 == ST.c2) {
6053 /* set n to utf8_distance(oldloc, locinput) */
6054 while (locinput <= ST.maxpos
6055 && memNE(locinput, ST.c1_utf8, UTF8SKIP(locinput)))
6057 locinput += UTF8SKIP(locinput);
6062 /* set n to utf8_distance(oldloc, locinput) */
6063 while (locinput <= ST.maxpos
6064 && memNE(locinput, ST.c1_utf8, UTF8SKIP(locinput))
6065 && memNE(locinput, ST.c2_utf8, UTF8SKIP(locinput)))
6067 locinput += UTF8SKIP(locinput);
6072 else { /* Not utf8_target */
6073 if (ST.c1 == ST.c2) {
6074 while (locinput <= ST.maxpos &&
6075 UCHARAT(locinput) != ST.c1)
6079 while (locinput <= ST.maxpos
6080 && UCHARAT(locinput) != ST.c1
6081 && UCHARAT(locinput) != ST.c2)
6084 n = locinput - ST.oldloc;
6086 if (locinput > ST.maxpos)
6089 /* In /a{m,n}b/, ST.oldloc is at "a" x m, locinput is
6090 * at b; check that everything between oldloc and
6091 * locinput matches */
6092 char *li = ST.oldloc;
6094 if (regrepeat(rex, &li, ST.A, n, depth) < n)
6096 assert(n == REG_INFTY || locinput == li);
6098 CURLY_SETPAREN(ST.paren, ST.count);
6099 if (cur_eval && cur_eval->u.eval.close_paren &&
6100 cur_eval->u.eval.close_paren == (U32)ST.paren) {
6103 PUSH_STATE_GOTO(CURLY_B_min_known, ST.B, locinput);
6105 assert(0); /* NOTREACHED */
6108 case CURLY_B_min_fail:
6109 /* failed to find B in a non-greedy match where c1,c2 invalid */
6111 REGCP_UNWIND(ST.cp);
6113 UNWIND_PAREN(ST.lastparen, ST.lastcloseparen);
6115 /* failed -- move forward one */
6117 char *li = locinput;
6118 if (!regrepeat(rex, &li, ST.A, 1, depth)) {
6125 if (ST.count <= ST.max || (ST.max == REG_INFTY &&
6126 ST.count > 0)) /* count overflow ? */
6129 CURLY_SETPAREN(ST.paren, ST.count);
6130 if (cur_eval && cur_eval->u.eval.close_paren &&
6131 cur_eval->u.eval.close_paren == (U32)ST.paren) {
6134 PUSH_STATE_GOTO(CURLY_B_min, ST.B, locinput);
6138 assert(0); /* NOTREACHED */
6142 /* a successful greedy match: now try to match B */
6143 if (cur_eval && cur_eval->u.eval.close_paren &&
6144 cur_eval->u.eval.close_paren == (U32)ST.paren) {
6148 bool could_match = locinput < PL_regeol;
6150 /* If it could work, try it. */
6151 if (ST.c1 != CHRTEST_VOID && could_match) {
6152 if (! UTF8_IS_INVARIANT(UCHARAT(locinput)) && utf8_target)
6154 could_match = memEQ(locinput,
6159 UTF8SKIP(locinput));
6162 could_match = UCHARAT(locinput) == ST.c1
6163 || UCHARAT(locinput) == ST.c2;
6166 if (ST.c1 == CHRTEST_VOID || could_match) {
6167 CURLY_SETPAREN(ST.paren, ST.count);
6168 PUSH_STATE_GOTO(CURLY_B_max, ST.B, locinput);
6169 assert(0); /* NOTREACHED */
6174 case CURLY_B_max_fail:
6175 /* failed to find B in a greedy match */
6177 REGCP_UNWIND(ST.cp);
6179 UNWIND_PAREN(ST.lastparen, ST.lastcloseparen);
6182 if (--ST.count < ST.min)
6184 locinput = HOPc(locinput, -1);
6185 goto curly_try_B_max;
6189 case END: /* last op of main pattern */
6192 /* we've just finished A in /(??{A})B/; now continue with B */
6193 st->u.eval.toggle_reg_flags
6194 = cur_eval->u.eval.toggle_reg_flags;
6195 PL_reg_flags ^= st->u.eval.toggle_reg_flags;
6197 st->u.eval.prev_rex = rex_sv; /* inner */
6199 /* Save *all* the positions. */
6200 st->u.eval.cp = regcppush(rex, 0, maxopenparen);
6201 rex_sv = cur_eval->u.eval.prev_rex;
6202 SET_reg_curpm(rex_sv);
6203 rex = ReANY(rex_sv);
6204 rexi = RXi_GET(rex);
6205 cur_curlyx = cur_eval->u.eval.prev_curlyx;
6207 REGCP_SET(st->u.eval.lastcp);
6209 /* Restore parens of the outer rex without popping the
6211 S_regcp_restore(aTHX_ rex, cur_eval->u.eval.lastcp,
6214 st->u.eval.prev_eval = cur_eval;
6215 cur_eval = cur_eval->u.eval.prev_eval;
6217 PerlIO_printf(Perl_debug_log, "%*s EVAL trying tail ... %"UVxf"\n",
6218 REPORT_CODE_OFF+depth*2, "",PTR2UV(cur_eval)););
6219 if ( nochange_depth )
6222 PUSH_YES_STATE_GOTO(EVAL_AB, st->u.eval.prev_eval->u.eval.B,
6223 locinput); /* match B */
6226 if (locinput < reginfo->till) {
6227 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
6228 "%sMatch possible, but length=%ld is smaller than requested=%ld, failing!%s\n",
6230 (long)(locinput - PL_reg_starttry),
6231 (long)(reginfo->till - PL_reg_starttry),
6234 sayNO_SILENT; /* Cannot match: too short. */
6236 sayYES; /* Success! */
6238 case SUCCEED: /* successful SUSPEND/UNLESSM/IFMATCH/CURLYM */
6240 PerlIO_printf(Perl_debug_log,
6241 "%*s %ssubpattern success...%s\n",
6242 REPORT_CODE_OFF+depth*2, "", PL_colors[4], PL_colors[5]));
6243 sayYES; /* Success! */
6246 #define ST st->u.ifmatch
6251 case SUSPEND: /* (?>A) */
6253 newstart = locinput;
6256 case UNLESSM: /* -ve lookaround: (?!A), or with flags, (?<!A) */
6258 goto ifmatch_trivial_fail_test;
6260 case IFMATCH: /* +ve lookaround: (?=A), or with flags, (?<=A) */
6262 ifmatch_trivial_fail_test:
6264 char * const s = HOPBACKc(locinput, scan->flags);
6269 sw = 1 - cBOOL(ST.wanted);
6273 next = scan + ARG(scan);
6281 newstart = locinput;
6285 ST.logical = logical;
6286 logical = 0; /* XXX: reset state of logical once it has been saved into ST */
6288 /* execute body of (?...A) */
6289 PUSH_YES_STATE_GOTO(IFMATCH_A, NEXTOPER(NEXTOPER(scan)), newstart);
6290 assert(0); /* NOTREACHED */
6293 case IFMATCH_A_fail: /* body of (?...A) failed */
6294 ST.wanted = !ST.wanted;
6297 case IFMATCH_A: /* body of (?...A) succeeded */
6299 sw = cBOOL(ST.wanted);
6301 else if (!ST.wanted)
6304 if (OP(ST.me) != SUSPEND) {
6305 /* restore old position except for (?>...) */
6306 locinput = st->locinput;
6308 scan = ST.me + ARG(ST.me);
6311 continue; /* execute B */
6315 case LONGJMP: /* alternative with many branches compiles to
6316 * (BRANCHJ; EXACT ...; LONGJMP ) x N */
6317 next = scan + ARG(scan);
6322 case COMMIT: /* (*COMMIT) */
6323 reginfo->cutpoint = PL_regeol;
6326 case PRUNE: /* (*PRUNE) */
6328 sv_yes_mark = sv_commit = MUTABLE_SV(rexi->data->data[ ARG( scan ) ]);
6329 PUSH_STATE_GOTO(COMMIT_next, next, locinput);
6330 assert(0); /* NOTREACHED */
6332 case COMMIT_next_fail:
6336 case OPFAIL: /* (*FAIL) */
6338 assert(0); /* NOTREACHED */
6340 #define ST st->u.mark
6341 case MARKPOINT: /* (*MARK:foo) */
6342 ST.prev_mark = mark_state;
6343 ST.mark_name = sv_commit = sv_yes_mark
6344 = MUTABLE_SV(rexi->data->data[ ARG( scan ) ]);
6346 ST.mark_loc = locinput;
6347 PUSH_YES_STATE_GOTO(MARKPOINT_next, next, locinput);
6348 assert(0); /* NOTREACHED */
6350 case MARKPOINT_next:
6351 mark_state = ST.prev_mark;
6353 assert(0); /* NOTREACHED */
6355 case MARKPOINT_next_fail:
6356 if (popmark && sv_eq(ST.mark_name,popmark))
6358 if (ST.mark_loc > startpoint)
6359 reginfo->cutpoint = HOPBACKc(ST.mark_loc, 1);
6360 popmark = NULL; /* we found our mark */
6361 sv_commit = ST.mark_name;
6364 PerlIO_printf(Perl_debug_log,
6365 "%*s %ssetting cutpoint to mark:%"SVf"...%s\n",
6366 REPORT_CODE_OFF+depth*2, "",
6367 PL_colors[4], SVfARG(sv_commit), PL_colors[5]);
6370 mark_state = ST.prev_mark;
6371 sv_yes_mark = mark_state ?
6372 mark_state->u.mark.mark_name : NULL;
6374 assert(0); /* NOTREACHED */
6376 case SKIP: /* (*SKIP) */
6378 /* (*SKIP) : if we fail we cut here*/
6379 ST.mark_name = NULL;
6380 ST.mark_loc = locinput;
6381 PUSH_STATE_GOTO(SKIP_next,next, locinput);
6383 /* (*SKIP:NAME) : if there is a (*MARK:NAME) fail where it was,
6384 otherwise do nothing. Meaning we need to scan
6386 regmatch_state *cur = mark_state;
6387 SV *find = MUTABLE_SV(rexi->data->data[ ARG( scan ) ]);
6390 if ( sv_eq( cur->u.mark.mark_name,
6393 ST.mark_name = find;
6394 PUSH_STATE_GOTO( SKIP_next, next, locinput);
6396 cur = cur->u.mark.prev_mark;
6399 /* Didn't find our (*MARK:NAME) so ignore this (*SKIP:NAME) */
6402 case SKIP_next_fail:
6404 /* (*CUT:NAME) - Set up to search for the name as we
6405 collapse the stack*/
6406 popmark = ST.mark_name;
6408 /* (*CUT) - No name, we cut here.*/
6409 if (ST.mark_loc > startpoint)
6410 reginfo->cutpoint = HOPBACKc(ST.mark_loc, 1);
6411 /* but we set sv_commit to latest mark_name if there
6412 is one so they can test to see how things lead to this
6415 sv_commit=mark_state->u.mark.mark_name;
6419 assert(0); /* NOTREACHED */
6422 case LNBREAK: /* \R */
6423 if ((n=is_LNBREAK_safe(locinput, PL_regeol, utf8_target))) {
6430 PerlIO_printf(Perl_error_log, "%"UVxf" %d\n",
6431 PTR2UV(scan), OP(scan));
6432 Perl_croak(aTHX_ "regexp memory corruption");
6434 /* this is a point to jump to in order to increment
6435 * locinput by one character */
6437 assert(!NEXTCHR_IS_EOS);
6439 locinput += PL_utf8skip[nextchr];
6440 /* locinput is allowed to go 1 char off the end, but not 2+ */
6441 if (locinput > PL_regeol)
6450 /* switch break jumps here */
6451 scan = next; /* prepare to execute the next op and ... */
6452 continue; /* ... jump back to the top, reusing st */
6453 assert(0); /* NOTREACHED */
6456 /* push a state that backtracks on success */
6457 st->u.yes.prev_yes_state = yes_state;
6461 /* push a new regex state, then continue at scan */
6463 regmatch_state *newst;
6466 regmatch_state *cur = st;
6467 regmatch_state *curyes = yes_state;
6469 regmatch_slab *slab = PL_regmatch_slab;
6470 for (;curd > -1;cur--,curd--) {
6471 if (cur < SLAB_FIRST(slab)) {
6473 cur = SLAB_LAST(slab);
6475 PerlIO_printf(Perl_error_log, "%*s#%-3d %-10s %s\n",
6476 REPORT_CODE_OFF + 2 + depth * 2,"",
6477 curd, PL_reg_name[cur->resume_state],
6478 (curyes == cur) ? "yes" : ""
6481 curyes = cur->u.yes.prev_yes_state;
6484 DEBUG_STATE_pp("push")
6487 st->locinput = locinput;
6489 if (newst > SLAB_LAST(PL_regmatch_slab))
6490 newst = S_push_slab(aTHX);
6491 PL_regmatch_state = newst;
6493 locinput = pushinput;
6496 assert(0); /* NOTREACHED */
6501 * We get here only if there's trouble -- normally "case END" is
6502 * the terminating point.
6504 Perl_croak(aTHX_ "corrupted regexp pointers");
6510 /* we have successfully completed a subexpression, but we must now
6511 * pop to the state marked by yes_state and continue from there */
6512 assert(st != yes_state);
6514 while (st != yes_state) {
6516 if (st < SLAB_FIRST(PL_regmatch_slab)) {
6517 PL_regmatch_slab = PL_regmatch_slab->prev;
6518 st = SLAB_LAST(PL_regmatch_slab);
6522 DEBUG_STATE_pp("pop (no final)");
6524 DEBUG_STATE_pp("pop (yes)");
6530 while (yes_state < SLAB_FIRST(PL_regmatch_slab)
6531 || yes_state > SLAB_LAST(PL_regmatch_slab))
6533 /* not in this slab, pop slab */
6534 depth -= (st - SLAB_FIRST(PL_regmatch_slab) + 1);
6535 PL_regmatch_slab = PL_regmatch_slab->prev;
6536 st = SLAB_LAST(PL_regmatch_slab);
6538 depth -= (st - yes_state);
6541 yes_state = st->u.yes.prev_yes_state;
6542 PL_regmatch_state = st;
6545 locinput= st->locinput;
6546 state_num = st->resume_state + no_final;
6547 goto reenter_switch;
6550 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "%sMatch successful!%s\n",
6551 PL_colors[4], PL_colors[5]));
6553 if (PL_reg_state.re_state_eval_setup_done) {
6554 /* each successfully executed (?{...}) block does the equivalent of
6555 * local $^R = do {...}
6556 * When popping the save stack, all these locals would be undone;
6557 * bypass this by setting the outermost saved $^R to the latest
6559 if (oreplsv != GvSV(PL_replgv))
6560 sv_setsv(oreplsv, GvSV(PL_replgv));
6567 PerlIO_printf(Perl_debug_log,
6568 "%*s %sfailed...%s\n",
6569 REPORT_CODE_OFF+depth*2, "",
6570 PL_colors[4], PL_colors[5])
6582 /* there's a previous state to backtrack to */
6584 if (st < SLAB_FIRST(PL_regmatch_slab)) {
6585 PL_regmatch_slab = PL_regmatch_slab->prev;
6586 st = SLAB_LAST(PL_regmatch_slab);
6588 PL_regmatch_state = st;
6589 locinput= st->locinput;
6591 DEBUG_STATE_pp("pop");
6593 if (yes_state == st)
6594 yes_state = st->u.yes.prev_yes_state;
6596 state_num = st->resume_state + 1; /* failure = success + 1 */
6597 goto reenter_switch;
6602 if (rex->intflags & PREGf_VERBARG_SEEN) {
6603 SV *sv_err = get_sv("REGERROR", 1);
6604 SV *sv_mrk = get_sv("REGMARK", 1);
6606 sv_commit = &PL_sv_no;
6608 sv_yes_mark = &PL_sv_yes;
6611 sv_commit = &PL_sv_yes;
6612 sv_yes_mark = &PL_sv_no;
6614 sv_setsv(sv_err, sv_commit);
6615 sv_setsv(sv_mrk, sv_yes_mark);
6619 if (last_pushed_cv) {
6622 PERL_UNUSED_VAR(SP);
6625 /* clean up; in particular, free all slabs above current one */
6626 LEAVE_SCOPE(oldsave);
6628 assert(!result || locinput - PL_bostr >= 0);
6629 return result ? locinput - PL_bostr : -1;
6633 - regrepeat - repeatedly match something simple, report how many
6635 * What 'simple' means is a node which can be the operand of a quantifier like
6638 * startposp - pointer a pointer to the start position. This is updated
6639 * to point to the byte following the highest successful
6641 * p - the regnode to be repeatedly matched against.
6642 * max - maximum number of things to match.
6643 * depth - (for debugging) backtracking depth.
6646 S_regrepeat(pTHX_ const regexp *prog, char **startposp, const regnode *p, I32 max, int depth)
6649 char *scan; /* Pointer to current position in target string */
6651 char *loceol = PL_regeol; /* local version */
6652 I32 hardcount = 0; /* How many matches so far */
6653 bool utf8_target = PL_reg_match_utf8;
6654 int to_complement = 0; /* Invert the result? */
6656 _char_class_number classnum;
6658 PERL_UNUSED_ARG(depth);
6661 PERL_ARGS_ASSERT_REGREPEAT;
6664 if (max == REG_INFTY)
6666 else if (! utf8_target && scan + max < loceol)
6667 loceol = scan + max;
6669 /* Here, for the case of a non-UTF-8 target we have adjusted <loceol> down
6670 * to the maximum of how far we should go in it (leaving it set to the real
6671 * end, if the maximum permissible would take us beyond that). This allows
6672 * us to make the loop exit condition that we haven't gone past <loceol> to
6673 * also mean that we haven't exceeded the max permissible count, saving a
6674 * test each time through the loop. But it assumes that the OP matches a
6675 * single byte, which is true for most of the OPs below when applied to a
6676 * non-UTF-8 target. Those relatively few OPs that don't have this
6677 * characteristic will have to compensate.
6679 * There is no adjustment for UTF-8 targets, as the number of bytes per
6680 * character varies. OPs will have to test both that the count is less
6681 * than the max permissible (using <hardcount> to keep track), and that we
6682 * are still within the bounds of the string (using <loceol>. A few OPs
6683 * match a single byte no matter what the encoding. They can omit the max
6684 * test if, for the UTF-8 case, they do the adjustment that was skipped
6687 * Thus, the code above sets things up for the common case; and exceptional
6688 * cases need extra work; the common case is to make sure <scan> doesn't
6689 * go past <loceol>, and for UTF-8 to also use <hardcount> to make sure the
6690 * count doesn't exceed the maximum permissible */
6695 while (scan < loceol && hardcount < max && *scan != '\n') {
6696 scan += UTF8SKIP(scan);
6700 while (scan < loceol && *scan != '\n')
6706 while (scan < loceol && hardcount < max) {
6707 scan += UTF8SKIP(scan);
6714 case CANY: /* Move <scan> forward <max> bytes, unless goes off end */
6715 if (utf8_target && scan + max < loceol) {
6717 /* <loceol> hadn't been adjusted in the UTF-8 case */
6725 assert(STR_LEN(p) == (UTF_PATTERN) ? UTF8SKIP(STRING(p)) : 1);
6729 /* Can use a simple loop if the pattern char to match on is invariant
6730 * under UTF-8, or both target and pattern aren't UTF-8. Note that we
6731 * can use UTF8_IS_INVARIANT() even if the pattern isn't UTF-8, as it's
6732 * true iff it doesn't matter if the argument is in UTF-8 or not */
6733 if (UTF8_IS_INVARIANT(c) || (! utf8_target && ! UTF_PATTERN)) {
6734 if (utf8_target && scan + max < loceol) {
6735 /* We didn't adjust <loceol> because is UTF-8, but ok to do so,
6736 * since here, to match at all, 1 char == 1 byte */
6737 loceol = scan + max;
6739 while (scan < loceol && UCHARAT(scan) == c) {
6743 else if (UTF_PATTERN) {
6745 STRLEN scan_char_len;
6747 /* When both target and pattern are UTF-8, we have to do
6749 while (hardcount < max
6751 && (scan_char_len = UTF8SKIP(scan)) <= STR_LEN(p)
6752 && memEQ(scan, STRING(p), scan_char_len))
6754 scan += scan_char_len;
6758 else if (! UTF8_IS_ABOVE_LATIN1(c)) {
6760 /* Target isn't utf8; convert the character in the UTF-8
6761 * pattern to non-UTF8, and do a simple loop */
6762 c = TWO_BYTE_UTF8_TO_UNI(c, *(STRING(p) + 1));
6763 while (scan < loceol && UCHARAT(scan) == c) {
6766 } /* else pattern char is above Latin1, can't possibly match the
6771 /* Here, the string must be utf8; pattern isn't, and <c> is
6772 * different in utf8 than not, so can't compare them directly.
6773 * Outside the loop, find the two utf8 bytes that represent c, and
6774 * then look for those in sequence in the utf8 string */
6775 U8 high = UTF8_TWO_BYTE_HI(c);
6776 U8 low = UTF8_TWO_BYTE_LO(c);
6778 while (hardcount < max
6779 && scan + 1 < loceol
6780 && UCHARAT(scan) == high
6781 && UCHARAT(scan + 1) == low)
6790 utf8_flags = FOLDEQ_UTF8_NOMIX_ASCII;
6794 PL_reg_flags |= RF_tainted;
6795 utf8_flags = FOLDEQ_UTF8_LOCALE;
6803 case EXACTFU_TRICKYFOLD:
6805 utf8_flags = (UTF_PATTERN) ? FOLDEQ_S2_ALREADY_FOLDED : 0;
6809 U8 c1_utf8[UTF8_MAXBYTES+1], c2_utf8[UTF8_MAXBYTES+1];
6811 assert(STR_LEN(p) == (UTF_PATTERN) ? UTF8SKIP(STRING(p)) : 1);
6813 if (S_setup_EXACTISH_ST_c1_c2(aTHX_ p, &c1, c1_utf8, &c2, c2_utf8)) {
6814 if (c1 == CHRTEST_VOID) {
6815 /* Use full Unicode fold matching */
6816 char *tmpeol = PL_regeol;
6817 STRLEN pat_len = (UTF_PATTERN) ? UTF8SKIP(STRING(p)) : 1;
6818 while (hardcount < max
6819 && foldEQ_utf8_flags(scan, &tmpeol, 0, utf8_target,
6820 STRING(p), NULL, pat_len,
6821 cBOOL(UTF_PATTERN), utf8_flags))
6828 else if (utf8_target) {
6830 while (scan < loceol
6832 && memEQ(scan, c1_utf8, UTF8SKIP(scan)))
6834 scan += UTF8SKIP(scan);
6839 while (scan < loceol
6841 && (memEQ(scan, c1_utf8, UTF8SKIP(scan))
6842 || memEQ(scan, c2_utf8, UTF8SKIP(scan))))
6844 scan += UTF8SKIP(scan);
6849 else if (c1 == c2) {
6850 while (scan < loceol && UCHARAT(scan) == c1) {
6855 while (scan < loceol &&
6856 (UCHARAT(scan) == c1 || UCHARAT(scan) == c2))
6866 while (hardcount < max
6868 && reginclass(prog, p, (U8*)scan, utf8_target))
6870 scan += UTF8SKIP(scan);
6874 while (scan < loceol && REGINCLASS(prog, p, (U8*)scan))
6879 /* The argument (FLAGS) to all the POSIX node types is the class number */
6886 PL_reg_flags |= RF_tainted;
6887 if (! utf8_target) {
6888 while (scan < loceol && to_complement ^ cBOOL(isFOO_lc(FLAGS(p),
6894 while (hardcount < max && scan < loceol
6895 && to_complement ^ cBOOL(isFOO_utf8_lc(FLAGS(p),
6898 scan += UTF8SKIP(scan);
6911 if (utf8_target && scan + max < loceol) {
6913 /* We didn't adjust <loceol> at the beginning of this routine
6914 * because is UTF-8, but it is actually ok to do so, since here, to
6915 * match, 1 char == 1 byte. */
6916 loceol = scan + max;
6918 while (scan < loceol && _generic_isCC_A((U8) *scan, FLAGS(p))) {
6931 if (! utf8_target) {
6932 while (scan < loceol && ! _generic_isCC_A((U8) *scan, FLAGS(p))) {
6938 /* The complement of something that matches only ASCII matches all
6939 * UTF-8 variant code points, plus everything in ASCII that isn't
6941 while (hardcount < max && scan < loceol
6942 && (! UTF8_IS_INVARIANT(*scan)
6943 || ! _generic_isCC_A((U8) *scan, FLAGS(p))))
6945 scan += UTF8SKIP(scan);
6956 if (! utf8_target) {
6957 while (scan < loceol && to_complement
6958 ^ cBOOL(_generic_isCC((U8) *scan, FLAGS(p))))
6965 classnum = (_char_class_number) FLAGS(p);
6966 if (classnum < _FIRST_NON_SWASH_CC) {
6968 /* Here, a swash is needed for above-Latin1 code points.
6969 * Process as many Latin1 code points using the built-in rules.
6970 * Go to another loop to finish processing upon encountering
6971 * the first Latin1 code point. We could do that in this loop
6972 * as well, but the other way saves having to test if the swash
6973 * has been loaded every time through the loop: extra space to
6975 while (hardcount < max && scan < loceol) {
6976 if (UTF8_IS_INVARIANT(*scan)) {
6977 if (! (to_complement ^ cBOOL(_generic_isCC((U8) *scan,
6984 else if (UTF8_IS_DOWNGRADEABLE_START(*scan)) {
6985 if (! (to_complement
6986 ^ cBOOL(_generic_isCC(TWO_BYTE_UTF8_TO_UNI(*scan,
6995 goto found_above_latin1;
7002 /* For these character classes, the knowledge of how to handle
7003 * every code point is compiled in to Perl via a macro. This
7004 * code is written for making the loops as tight as possible.
7005 * It could be refactored to save space instead */
7007 case _CC_ENUM_SPACE: /* XXX would require separate code
7008 if we revert the change of \v
7011 case _CC_ENUM_PSXSPC:
7012 while (hardcount < max
7014 && (to_complement ^ cBOOL(isSPACE_utf8(scan))))
7016 scan += UTF8SKIP(scan);
7020 case _CC_ENUM_BLANK:
7021 while (hardcount < max
7023 && (to_complement ^ cBOOL(isBLANK_utf8(scan))))
7025 scan += UTF8SKIP(scan);
7029 case _CC_ENUM_XDIGIT:
7030 while (hardcount < max
7032 && (to_complement ^ cBOOL(isXDIGIT_utf8(scan))))
7034 scan += UTF8SKIP(scan);
7038 case _CC_ENUM_VERTSPACE:
7039 while (hardcount < max
7041 && (to_complement ^ cBOOL(isVERTWS_utf8(scan))))
7043 scan += UTF8SKIP(scan);
7047 case _CC_ENUM_CNTRL:
7048 while (hardcount < max
7050 && (to_complement ^ cBOOL(isCNTRL_utf8(scan))))
7052 scan += UTF8SKIP(scan);
7057 Perl_croak(aTHX_ "panic: regrepeat() node %d='%s' has an unexpected character class '%d'", OP(p), PL_reg_name[OP(p)], classnum);
7063 found_above_latin1: /* Continuation of POSIXU and NPOSIXU */
7065 /* Load the swash if not already present */
7066 if (! PL_utf8_swash_ptrs[classnum]) {
7067 U8 flags = _CORE_SWASH_INIT_ACCEPT_INVLIST;
7068 PL_utf8_swash_ptrs[classnum] = _core_swash_init(
7069 "utf8", swash_property_names[classnum],
7070 &PL_sv_undef, 1, 0, NULL, &flags);
7073 while (hardcount < max && scan < loceol
7074 && to_complement ^ cBOOL(_generic_utf8(
7077 swash_fetch(PL_utf8_swash_ptrs[classnum],
7081 scan += UTF8SKIP(scan);
7088 while (hardcount < max && scan < loceol &&
7089 (c=is_LNBREAK_utf8_safe(scan, loceol))) {
7094 /* LNBREAK can match one or two latin chars, which is ok, but we
7095 * have to use hardcount in this situation, and throw away the
7096 * adjustment to <loceol> done before the switch statement */
7098 while (scan < loceol && (c=is_LNBREAK_latin1_safe(scan, loceol))) {
7119 /* These are all 0 width, so match right here or not at all. */
7123 Perl_croak(aTHX_ "panic: regrepeat() called with unrecognized node type %d='%s'", OP(p), PL_reg_name[OP(p)]);
7124 assert(0); /* NOTREACHED */
7131 c = scan - *startposp;
7135 GET_RE_DEBUG_FLAGS_DECL;
7137 SV * const prop = sv_newmortal();
7138 regprop(prog, prop, p);
7139 PerlIO_printf(Perl_debug_log,
7140 "%*s %s can match %"IVdf" times out of %"IVdf"...\n",
7141 REPORT_CODE_OFF + depth*2, "", SvPVX_const(prop),(IV)c,(IV)max);
7149 #if !defined(PERL_IN_XSUB_RE) || defined(PLUGGABLE_RE_EXTENSION)
7151 - regclass_swash - prepare the utf8 swash. Wraps the shared core version to
7152 create a copy so that changes the caller makes won't change the shared one.
7153 If <altsvp> is non-null, will return NULL in it, for back-compat.
7156 Perl_regclass_swash(pTHX_ const regexp *prog, const regnode* node, bool doinit, SV** listsvp, SV **altsvp)
7158 PERL_ARGS_ASSERT_REGCLASS_SWASH;
7164 return newSVsv(core_regclass_swash(prog, node, doinit, listsvp));
7169 S_core_regclass_swash(pTHX_ const regexp *prog, const regnode* node, bool doinit, SV** listsvp)
7171 /* Returns the swash for the input 'node' in the regex 'prog'.
7172 * If <doinit> is true, will attempt to create the swash if not already
7174 * If <listsvp> is non-null, will return the swash initialization string in
7176 * Tied intimately to how regcomp.c sets up the data structure */
7183 RXi_GET_DECL(prog,progi);
7184 const struct reg_data * const data = prog ? progi->data : NULL;
7186 PERL_ARGS_ASSERT_CORE_REGCLASS_SWASH;
7188 assert(ANYOF_NONBITMAP(node));
7190 if (data && data->count) {
7191 const U32 n = ARG(node);
7193 if (data->what[n] == 's') {
7194 SV * const rv = MUTABLE_SV(data->data[n]);
7195 AV * const av = MUTABLE_AV(SvRV(rv));
7196 SV **const ary = AvARRAY(av);
7197 U8 swash_init_flags = _CORE_SWASH_INIT_ACCEPT_INVLIST;
7199 si = *ary; /* ary[0] = the string to initialize the swash with */
7201 /* Elements 2 and 3 are either both present or both absent. [2] is
7202 * any inversion list generated at compile time; [3] indicates if
7203 * that inversion list has any user-defined properties in it. */
7204 if (av_len(av) >= 2) {
7207 swash_init_flags |= _CORE_SWASH_INIT_USER_DEFINED_PROPERTY;
7214 /* Element [1] is reserved for the set-up swash. If already there,
7215 * return it; if not, create it and store it there */
7216 if (SvROK(ary[1])) {
7219 else if (si && doinit) {
7221 sw = _core_swash_init("utf8", /* the utf8 package */
7225 0, /* not from tr/// */
7228 (void)av_store(av, 1, sw);
7234 SV* matches_string = newSVpvn("", 0);
7236 /* Use the swash, if any, which has to have incorporated into it all
7238 if ((! sw || (invlist = _get_swash_invlist(sw)) == NULL)
7239 && (si && si != &PL_sv_undef))
7242 /* If no swash, use the input initialization string, if available */
7243 sv_catsv(matches_string, si);
7246 /* Add the inversion list to whatever we have. This may have come from
7247 * the swash, or from an input parameter */
7249 sv_catsv(matches_string, _invlist_contents(invlist));
7251 *listsvp = matches_string;
7258 - reginclass - determine if a character falls into a character class
7260 n is the ANYOF regnode
7261 p is the target string
7262 utf8_target tells whether p is in UTF-8.
7264 Returns true if matched; false otherwise.
7266 Note that this can be a synthetic start class, a combination of various
7267 nodes, so things you think might be mutually exclusive, such as locale,
7268 aren't. It can match both locale and non-locale
7273 S_reginclass(pTHX_ const regexp * const prog, const regnode * const n, const U8* const p, const bool utf8_target)
7276 const char flags = ANYOF_FLAGS(n);
7280 PERL_ARGS_ASSERT_REGINCLASS;
7282 /* If c is not already the code point, get it. Note that
7283 * UTF8_IS_INVARIANT() works even if not in UTF-8 */
7284 if (! UTF8_IS_INVARIANT(c) && utf8_target) {
7286 c = utf8n_to_uvchr(p, UTF8_MAXBYTES, &c_len,
7287 (UTF8_ALLOW_DEFAULT & UTF8_ALLOW_ANYUV)
7288 | UTF8_ALLOW_FFFF | UTF8_CHECK_ONLY);
7289 /* see [perl #37836] for UTF8_ALLOW_ANYUV; [perl #38293] for
7290 * UTF8_ALLOW_FFFF */
7291 if (c_len == (STRLEN)-1)
7292 Perl_croak(aTHX_ "Malformed UTF-8 character (fatal)");
7295 /* If this character is potentially in the bitmap, check it */
7297 if (ANYOF_BITMAP_TEST(n, c))
7299 else if (flags & ANYOF_NON_UTF8_LATIN1_ALL
7305 else if (flags & ANYOF_LOCALE) {
7306 PL_reg_flags |= RF_tainted;
7308 if ((flags & ANYOF_LOC_FOLD)
7309 && ANYOF_BITMAP_TEST(n, PL_fold_locale[c]))
7313 else if (ANYOF_CLASS_TEST_ANY_SET(n)) {
7315 /* The data structure is arranged so bits 0, 2, 4, ... are set
7316 * if the class includes the Posix character class given by
7317 * bit/2; and 1, 3, 5, ... are set if the class includes the
7318 * complemented Posix class given by int(bit/2). So we loop
7319 * through the bits, each time changing whether we complement
7320 * the result or not. Suppose for the sake of illustration
7321 * that bits 0-3 mean respectively, \w, \W, \s, \S. If bit 0
7322 * is set, it means there is a match for this ANYOF node if the
7323 * character is in the class given by the expression (0 / 2 = 0
7324 * = \w). If it is in that class, isFOO_lc() will return 1,
7325 * and since 'to_complement' is 0, the result will stay TRUE,
7326 * and we exit the loop. Suppose instead that bit 0 is 0, but
7327 * bit 1 is 1. That means there is a match if the character
7328 * matches \W. We won't bother to call isFOO_lc() on bit 0,
7329 * but will on bit 1. On the second iteration 'to_complement'
7330 * will be 1, so the exclusive or will reverse things, so we
7331 * are testing for \W. On the third iteration, 'to_complement'
7332 * will be 0, and we would be testing for \s; the fourth
7333 * iteration would test for \S, etc. */
7336 int to_complement = 0;
7337 while (count < ANYOF_MAX) {
7338 if (ANYOF_CLASS_TEST(n, count)
7339 && to_complement ^ cBOOL(isFOO_lc(count/2, (U8) c)))
7351 /* If the bitmap didn't (or couldn't) match, and something outside the
7352 * bitmap could match, try that. Locale nodes specify completely the
7353 * behavior of code points in the bit map (otherwise, a utf8 target would
7354 * cause them to be treated as Unicode and not locale), except in
7355 * the very unlikely event when this node is a synthetic start class, which
7356 * could be a combination of locale and non-locale nodes. So allow locale
7357 * to match for the synthetic start class, which will give a false
7358 * positive that will be resolved when the match is done again as not part
7359 * of the synthetic start class */
7361 if (utf8_target && (flags & ANYOF_UNICODE_ALL) && c >= 256) {
7362 match = TRUE; /* Everything above 255 matches */
7364 else if (ANYOF_NONBITMAP(n)
7365 && ((flags & ANYOF_NONBITMAP_NON_UTF8)
7368 || (! (flags & ANYOF_LOCALE))
7369 || (flags & ANYOF_IS_SYNTHETIC)))))
7371 SV * const sw = core_regclass_swash(prog, n, TRUE, 0);
7376 } else { /* Convert to utf8 */
7378 utf8_p = bytes_to_utf8(p, &len);
7381 if (swash_fetch(sw, utf8_p, TRUE)) {
7385 /* If we allocated a string above, free it */
7386 if (! utf8_target) Safefree(utf8_p);
7390 if (UNICODE_IS_SUPER(c)
7391 && (flags & ANYOF_WARN_SUPER)
7392 && ckWARN_d(WARN_NON_UNICODE))
7394 Perl_warner(aTHX_ packWARN(WARN_NON_UNICODE),
7395 "Code point 0x%04"UVXf" is not Unicode, all \\p{} matches fail; all \\P{} matches succeed", c);
7399 /* The xor complements the return if to invert: 1^1 = 0, 1^0 = 1 */
7400 return cBOOL(flags & ANYOF_INVERT) ^ match;
7404 S_reghop3(U8 *s, I32 off, const U8* lim)
7406 /* return the position 'off' UTF-8 characters away from 's', forward if
7407 * 'off' >= 0, backwards if negative. But don't go outside of position
7408 * 'lim', which better be < s if off < 0 */
7412 PERL_ARGS_ASSERT_REGHOP3;
7415 while (off-- && s < lim) {
7416 /* XXX could check well-formedness here */
7421 while (off++ && s > lim) {
7423 if (UTF8_IS_CONTINUED(*s)) {
7424 while (s > lim && UTF8_IS_CONTINUATION(*s))
7427 /* XXX could check well-formedness here */
7434 /* there are a bunch of places where we use two reghop3's that should
7435 be replaced with this routine. but since thats not done yet
7436 we ifdef it out - dmq
7439 S_reghop4(U8 *s, I32 off, const U8* llim, const U8* rlim)
7443 PERL_ARGS_ASSERT_REGHOP4;
7446 while (off-- && s < rlim) {
7447 /* XXX could check well-formedness here */
7452 while (off++ && s > llim) {
7454 if (UTF8_IS_CONTINUED(*s)) {
7455 while (s > llim && UTF8_IS_CONTINUATION(*s))
7458 /* XXX could check well-formedness here */
7466 S_reghopmaybe3(U8* s, I32 off, const U8* lim)
7470 PERL_ARGS_ASSERT_REGHOPMAYBE3;
7473 while (off-- && s < lim) {
7474 /* XXX could check well-formedness here */
7481 while (off++ && s > lim) {
7483 if (UTF8_IS_CONTINUED(*s)) {
7484 while (s > lim && UTF8_IS_CONTINUATION(*s))
7487 /* XXX could check well-formedness here */
7496 restore_pos(pTHX_ void *arg)
7499 regexp * const rex = (regexp *)arg;
7500 if (PL_reg_state.re_state_eval_setup_done) {
7501 if (PL_reg_oldsaved) {
7502 rex->subbeg = PL_reg_oldsaved;
7503 rex->sublen = PL_reg_oldsavedlen;
7504 rex->suboffset = PL_reg_oldsavedoffset;
7505 rex->subcoffset = PL_reg_oldsavedcoffset;
7507 rex->saved_copy = PL_nrs;
7509 RXp_MATCH_COPIED_on(rex);
7511 PL_reg_magic->mg_len = PL_reg_oldpos;
7512 PL_reg_state.re_state_eval_setup_done = FALSE;
7513 PL_curpm = PL_reg_oldcurpm;
7518 S_to_utf8_substr(pTHX_ regexp *prog)
7520 /* Converts substr fields in prog from bytes to UTF-8, calling fbm_compile
7521 * on the converted value */
7525 PERL_ARGS_ASSERT_TO_UTF8_SUBSTR;
7528 if (prog->substrs->data[i].substr
7529 && !prog->substrs->data[i].utf8_substr) {
7530 SV* const sv = newSVsv(prog->substrs->data[i].substr);
7531 prog->substrs->data[i].utf8_substr = sv;
7532 sv_utf8_upgrade(sv);
7533 if (SvVALID(prog->substrs->data[i].substr)) {
7534 if (SvTAIL(prog->substrs->data[i].substr)) {
7535 /* Trim the trailing \n that fbm_compile added last
7537 SvCUR_set(sv, SvCUR(sv) - 1);
7538 /* Whilst this makes the SV technically "invalid" (as its
7539 buffer is no longer followed by "\0") when fbm_compile()
7540 adds the "\n" back, a "\0" is restored. */
7541 fbm_compile(sv, FBMcf_TAIL);
7545 if (prog->substrs->data[i].substr == prog->check_substr)
7546 prog->check_utf8 = sv;
7552 S_to_byte_substr(pTHX_ regexp *prog)
7554 /* Converts substr fields in prog from UTF-8 to bytes, calling fbm_compile
7555 * on the converted value; returns FALSE if can't be converted. */
7560 PERL_ARGS_ASSERT_TO_BYTE_SUBSTR;
7563 if (prog->substrs->data[i].utf8_substr
7564 && !prog->substrs->data[i].substr) {
7565 SV* sv = newSVsv(prog->substrs->data[i].utf8_substr);
7566 if (! sv_utf8_downgrade(sv, TRUE)) {
7569 if (SvVALID(prog->substrs->data[i].utf8_substr)) {
7570 if (SvTAIL(prog->substrs->data[i].utf8_substr)) {
7571 /* Trim the trailing \n that fbm_compile added last
7573 SvCUR_set(sv, SvCUR(sv) - 1);
7574 fbm_compile(sv, FBMcf_TAIL);
7578 prog->substrs->data[i].substr = sv;
7579 if (prog->substrs->data[i].utf8_substr == prog->check_utf8)
7580 prog->check_substr = sv;
7589 * c-indentation-style: bsd
7591 * indent-tabs-mode: nil
7594 * ex: set ts=8 sts=4 sw=4 et: