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);
4285 if (!REGINCLASS(rex, scan, (U8*)locinput))
4292 /* The argument (FLAGS) to all the POSIX node types is the class number
4295 case NPOSIXL: /* \W or [:^punct:] etc. under /l */
4299 case POSIXL: /* \w or [:punct:] etc. under /l */
4303 /* The locale hasn't influenced the outcome before this, so defer
4304 * tainting until now */
4305 PL_reg_flags |= RF_tainted;
4307 /* Use isFOO_lc() for characters within Latin1. (Note that
4308 * UTF8_IS_INVARIANT works even on non-UTF-8 strings, or else
4309 * wouldn't be invariant) */
4310 if (UTF8_IS_INVARIANT(nextchr) || ! utf8_target) {
4311 if (! (to_complement ^ cBOOL(isFOO_lc(FLAGS(scan), nextchr)))) {
4315 else if (UTF8_IS_DOWNGRADEABLE_START(nextchr)) {
4316 if (! (to_complement ^ cBOOL(isFOO_lc(FLAGS(scan),
4317 TWO_BYTE_UTF8_TO_UNI(nextchr,
4318 *(locinput + 1))))))
4323 else { /* Here, must be an above Latin-1 code point */
4324 goto utf8_posix_not_eos;
4327 /* Here, must be utf8 */
4328 locinput += UTF8SKIP(locinput);
4331 case NPOSIXD: /* \W or [:^punct:] etc. under /d */
4335 case POSIXD: /* \w or [:punct:] etc. under /d */
4341 case NPOSIXA: /* \W or [:^punct:] etc. under /a */
4343 if (NEXTCHR_IS_EOS) {
4347 /* All UTF-8 variants match */
4348 if (! UTF8_IS_INVARIANT(nextchr)) {
4349 goto increment_locinput;
4355 case POSIXA: /* \w or [:punct:] etc. under /a */
4358 /* We get here through POSIXD, NPOSIXD, and NPOSIXA when not in
4359 * UTF-8, and also from NPOSIXA even in UTF-8 when the current
4360 * character is a single byte */
4363 || ! (to_complement ^ cBOOL(_generic_isCC_A(nextchr,
4369 /* Here we are either not in utf8, or we matched a utf8-invariant,
4370 * so the next char is the next byte */
4374 case NPOSIXU: /* \W or [:^punct:] etc. under /u */
4378 case POSIXU: /* \w or [:punct:] etc. under /u */
4380 if (NEXTCHR_IS_EOS) {
4385 /* Use _generic_isCC() for characters within Latin1. (Note that
4386 * UTF8_IS_INVARIANT works even on non-UTF-8 strings, or else
4387 * wouldn't be invariant) */
4388 if (UTF8_IS_INVARIANT(nextchr) || ! utf8_target) {
4389 if (! (to_complement ^ cBOOL(_generic_isCC(nextchr,
4396 else if (UTF8_IS_DOWNGRADEABLE_START(nextchr)) {
4397 if (! (to_complement
4398 ^ cBOOL(_generic_isCC(TWO_BYTE_UTF8_TO_UNI(nextchr,
4406 else { /* Handle above Latin-1 code points */
4407 classnum = (_char_class_number) FLAGS(scan);
4408 if (classnum < _FIRST_NON_SWASH_CC) {
4410 /* Here, uses a swash to find such code points. Load if if
4411 * not done already */
4412 if (! PL_utf8_swash_ptrs[classnum]) {
4413 U8 flags = _CORE_SWASH_INIT_ACCEPT_INVLIST;
4414 PL_utf8_swash_ptrs[classnum]
4415 = _core_swash_init("utf8",
4416 swash_property_names[classnum],
4417 &PL_sv_undef, 1, 0, NULL, &flags);
4419 if (! (to_complement
4420 ^ cBOOL(swash_fetch(PL_utf8_swash_ptrs[classnum],
4421 (U8 *) locinput, TRUE))))
4426 else { /* Here, uses macros to find above Latin-1 code points */
4428 case _CC_ENUM_SPACE: /* XXX would require separate
4429 code if we revert the change
4430 of \v matching this */
4431 case _CC_ENUM_PSXSPC:
4432 if (! (to_complement
4433 ^ cBOOL(is_XPERLSPACE_high(locinput))))
4438 case _CC_ENUM_BLANK:
4439 if (! (to_complement
4440 ^ cBOOL(is_HORIZWS_high(locinput))))
4445 case _CC_ENUM_XDIGIT:
4446 if (! (to_complement
4447 ^ cBOOL(is_XDIGIT_high(locinput))))
4452 case _CC_ENUM_VERTSPACE:
4453 if (! (to_complement
4454 ^ cBOOL(is_VERTWS_high(locinput))))
4459 default: /* The rest, e.g. [:cntrl:], can't match
4461 if (! to_complement) {
4467 locinput += UTF8SKIP(locinput);
4471 case CLUMP: /* Match \X: logical Unicode character. This is defined as
4472 a Unicode extended Grapheme Cluster */
4473 /* From http://www.unicode.org/reports/tr29 (5.2 version). An
4474 extended Grapheme Cluster is:
4477 | Prepend* Begin Extend*
4480 Begin is: ( Special_Begin | ! Control )
4481 Special_Begin is: ( Regional-Indicator+ | Hangul-syllable )
4482 Extend is: ( Grapheme_Extend | Spacing_Mark )
4483 Control is: [ GCB_Control | CR | LF ]
4484 Hangul-syllable is: ( T+ | ( L* ( L | ( LVT | ( V | LV ) V* ) T* ) ))
4486 If we create a 'Regular_Begin' = Begin - Special_Begin, then
4489 Begin is ( Regular_Begin + Special Begin )
4491 It turns out that 98.4% of all Unicode code points match
4492 Regular_Begin. Doing it this way eliminates a table match in
4493 the previous implementation for almost all Unicode code points.
4495 There is a subtlety with Prepend* which showed up in testing.
4496 Note that the Begin, and only the Begin is required in:
4497 | Prepend* Begin Extend*
4498 Also, Begin contains '! Control'. A Prepend must be a
4499 '! Control', which means it must also be a Begin. What it
4500 comes down to is that if we match Prepend* and then find no
4501 suitable Begin afterwards, that if we backtrack the last
4502 Prepend, that one will be a suitable Begin.
4507 if (! utf8_target) {
4509 /* Match either CR LF or '.', as all the other possibilities
4511 locinput++; /* Match the . or CR */
4512 if (nextchr == '\r' /* And if it was CR, and the next is LF,
4514 && locinput < PL_regeol
4515 && UCHARAT(locinput) == '\n')
4522 /* Utf8: See if is ( CR LF ); already know that locinput <
4523 * PL_regeol, so locinput+1 is in bounds */
4524 if ( nextchr == '\r' && locinput+1 < PL_regeol
4525 && UCHARAT(locinput + 1) == '\n')
4532 /* In case have to backtrack to beginning, then match '.' */
4533 char *starting = locinput;
4535 /* In case have to backtrack the last prepend */
4536 char *previous_prepend = NULL;
4538 LOAD_UTF8_CHARCLASS_GCB();
4540 /* Match (prepend)* */
4541 while (locinput < PL_regeol
4542 && (len = is_GCB_Prepend_utf8(locinput)))
4544 previous_prepend = locinput;
4548 /* As noted above, if we matched a prepend character, but
4549 * the next thing won't match, back off the last prepend we
4550 * matched, as it is guaranteed to match the begin */
4551 if (previous_prepend
4552 && (locinput >= PL_regeol
4553 || (! swash_fetch(PL_utf8_X_regular_begin,
4554 (U8*)locinput, utf8_target)
4555 && ! is_GCB_SPECIAL_BEGIN_START_utf8(locinput)))
4558 locinput = previous_prepend;
4561 /* Note that here we know PL_regeol > locinput, as we
4562 * tested that upon input to this switch case, and if we
4563 * moved locinput forward, we tested the result just above
4564 * and it either passed, or we backed off so that it will
4566 if (swash_fetch(PL_utf8_X_regular_begin,
4567 (U8*)locinput, utf8_target)) {
4568 locinput += UTF8SKIP(locinput);
4570 else if (! is_GCB_SPECIAL_BEGIN_START_utf8(locinput)) {
4572 /* Here did not match the required 'Begin' in the
4573 * second term. So just match the very first
4574 * character, the '.' of the final term of the regex */
4575 locinput = starting + UTF8SKIP(starting);
4579 /* Here is a special begin. It can be composed of
4580 * several individual characters. One possibility is
4582 if ((len = is_GCB_RI_utf8(locinput))) {
4584 while (locinput < PL_regeol
4585 && (len = is_GCB_RI_utf8(locinput)))
4589 } else if ((len = is_GCB_T_utf8(locinput))) {
4590 /* Another possibility is T+ */
4592 while (locinput < PL_regeol
4593 && (len = is_GCB_T_utf8(locinput)))
4599 /* Here, neither RI+ nor T+; must be some other
4600 * Hangul. That means it is one of the others: L,
4601 * LV, LVT or V, and matches:
4602 * L* (L | LVT T* | V * V* T* | LV V* T*) */
4605 while (locinput < PL_regeol
4606 && (len = is_GCB_L_utf8(locinput)))
4611 /* Here, have exhausted L*. If the next character
4612 * is not an LV, LVT nor V, it means we had to have
4613 * at least one L, so matches L+ in the original
4614 * equation, we have a complete hangul syllable.
4617 if (locinput < PL_regeol
4618 && is_GCB_LV_LVT_V_utf8(locinput))
4620 /* Otherwise keep going. Must be LV, LVT or V.
4621 * See if LVT, by first ruling out V, then LV */
4622 if (! is_GCB_V_utf8(locinput)
4623 /* All but every TCount one is LV */
4624 && (valid_utf8_to_uvchr((U8 *) locinput,
4629 locinput += UTF8SKIP(locinput);
4632 /* Must be V or LV. Take it, then match
4634 locinput += UTF8SKIP(locinput);
4635 while (locinput < PL_regeol
4636 && (len = is_GCB_V_utf8(locinput)))
4642 /* And any of LV, LVT, or V can be followed
4644 while (locinput < PL_regeol
4645 && (len = is_GCB_T_utf8(locinput)))
4653 /* Match any extender */
4654 while (locinput < PL_regeol
4655 && swash_fetch(PL_utf8_X_extend,
4656 (U8*)locinput, utf8_target))
4658 locinput += UTF8SKIP(locinput);
4662 if (locinput > PL_regeol) sayNO;
4666 case NREFFL: /* /\g{name}/il */
4667 { /* The capture buffer cases. The ones beginning with N for the
4668 named buffers just convert to the equivalent numbered and
4669 pretend they were called as the corresponding numbered buffer
4671 /* don't initialize these in the declaration, it makes C++
4676 const U8 *fold_array;
4679 PL_reg_flags |= RF_tainted;
4680 folder = foldEQ_locale;
4681 fold_array = PL_fold_locale;
4683 utf8_fold_flags = FOLDEQ_UTF8_LOCALE;
4686 case NREFFA: /* /\g{name}/iaa */
4687 folder = foldEQ_latin1;
4688 fold_array = PL_fold_latin1;
4690 utf8_fold_flags = FOLDEQ_UTF8_NOMIX_ASCII;
4693 case NREFFU: /* /\g{name}/iu */
4694 folder = foldEQ_latin1;
4695 fold_array = PL_fold_latin1;
4697 utf8_fold_flags = 0;
4700 case NREFF: /* /\g{name}/i */
4702 fold_array = PL_fold;
4704 utf8_fold_flags = 0;
4707 case NREF: /* /\g{name}/ */
4711 utf8_fold_flags = 0;
4714 /* For the named back references, find the corresponding buffer
4716 n = reg_check_named_buff_matched(rex,scan);
4721 goto do_nref_ref_common;
4723 case REFFL: /* /\1/il */
4724 PL_reg_flags |= RF_tainted;
4725 folder = foldEQ_locale;
4726 fold_array = PL_fold_locale;
4727 utf8_fold_flags = FOLDEQ_UTF8_LOCALE;
4730 case REFFA: /* /\1/iaa */
4731 folder = foldEQ_latin1;
4732 fold_array = PL_fold_latin1;
4733 utf8_fold_flags = FOLDEQ_UTF8_NOMIX_ASCII;
4736 case REFFU: /* /\1/iu */
4737 folder = foldEQ_latin1;
4738 fold_array = PL_fold_latin1;
4739 utf8_fold_flags = 0;
4742 case REFF: /* /\1/i */
4744 fold_array = PL_fold;
4745 utf8_fold_flags = 0;
4748 case REF: /* /\1/ */
4751 utf8_fold_flags = 0;
4755 n = ARG(scan); /* which paren pair */
4758 ln = rex->offs[n].start;
4759 PL_reg_leftiter = PL_reg_maxiter; /* Void cache */
4760 if (rex->lastparen < n || ln == -1)
4761 sayNO; /* Do not match unless seen CLOSEn. */
4762 if (ln == rex->offs[n].end)
4766 if (type != REF /* REF can do byte comparison */
4767 && (utf8_target || type == REFFU))
4768 { /* XXX handle REFFL better */
4769 char * limit = PL_regeol;
4771 /* This call case insensitively compares the entire buffer
4772 * at s, with the current input starting at locinput, but
4773 * not going off the end given by PL_regeol, and returns in
4774 * <limit> upon success, how much of the current input was
4776 if (! foldEQ_utf8_flags(s, NULL, rex->offs[n].end - ln, utf8_target,
4777 locinput, &limit, 0, utf8_target, utf8_fold_flags))
4785 /* Not utf8: Inline the first character, for speed. */
4786 if (!NEXTCHR_IS_EOS &&
4787 UCHARAT(s) != nextchr &&
4789 UCHARAT(s) != fold_array[nextchr]))
4791 ln = rex->offs[n].end - ln;
4792 if (locinput + ln > PL_regeol)
4794 if (ln > 1 && (type == REF
4795 ? memNE(s, locinput, ln)
4796 : ! folder(s, locinput, ln)))
4802 case NOTHING: /* null op; e.g. the 'nothing' following
4803 * the '*' in m{(a+|b)*}' */
4805 case TAIL: /* placeholder while compiling (A|B|C) */
4808 case BACK: /* ??? doesn't appear to be used ??? */
4812 #define ST st->u.eval
4817 regexp_internal *rei;
4818 regnode *startpoint;
4820 case GOSTART: /* (?R) */
4821 case GOSUB: /* /(...(?1))/ /(...(?&foo))/ */
4822 if (cur_eval && cur_eval->locinput==locinput) {
4823 if (cur_eval->u.eval.close_paren == (U32)ARG(scan))
4824 Perl_croak(aTHX_ "Infinite recursion in regex");
4825 if ( ++nochange_depth > max_nochange_depth )
4827 "Pattern subroutine nesting without pos change"
4828 " exceeded limit in regex");
4835 if (OP(scan)==GOSUB) {
4836 startpoint = scan + ARG2L(scan);
4837 ST.close_paren = ARG(scan);
4839 startpoint = rei->program+1;
4842 goto eval_recurse_doit;
4843 assert(0); /* NOTREACHED */
4845 case EVAL: /* /(?{A})B/ /(??{A})B/ and /(?(?{A})X|Y)B/ */
4846 if (cur_eval && cur_eval->locinput==locinput) {
4847 if ( ++nochange_depth > max_nochange_depth )
4848 Perl_croak(aTHX_ "EVAL without pos change exceeded limit in regex");
4853 /* execute the code in the {...} */
4857 OP * const oop = PL_op;
4858 COP * const ocurcop = PL_curcop;
4860 char *saved_regeol = PL_regeol;
4861 struct re_save_state saved_state;
4864 /* save *all* paren positions */
4865 regcppush(rex, 0, maxopenparen);
4866 REGCP_SET(runops_cp);
4868 /* To not corrupt the existing regex state while executing the
4869 * eval we would normally put it on the save stack, like with
4870 * save_re_context. However, re-evals have a weird scoping so we
4871 * can't just add ENTER/LEAVE here. With that, things like
4873 * (?{$a=2})(a(?{local$a=$a+1}))*aak*c(?{$b=$a})
4875 * would break, as they expect the localisation to be unwound
4876 * only when the re-engine backtracks through the bit that
4879 * What we do instead is just saving the state in a local c
4882 Copy(&PL_reg_state, &saved_state, 1, struct re_save_state);
4884 PL_reg_state.re_reparsing = FALSE;
4887 caller_cv = find_runcv(NULL);
4891 if (rexi->data->what[n] == 'r') { /* code from an external qr */
4893 (REGEXP*)(rexi->data->data[n])
4896 nop = (OP*)rexi->data->data[n+1];
4898 else if (rexi->data->what[n] == 'l') { /* literal code */
4900 nop = (OP*)rexi->data->data[n];
4901 assert(CvDEPTH(newcv));
4904 /* literal with own CV */
4905 assert(rexi->data->what[n] == 'L');
4906 newcv = rex->qr_anoncv;
4907 nop = (OP*)rexi->data->data[n];
4910 /* normally if we're about to execute code from the same
4911 * CV that we used previously, we just use the existing
4912 * CX stack entry. However, its possible that in the
4913 * meantime we may have backtracked, popped from the save
4914 * stack, and undone the SAVECOMPPAD(s) associated with
4915 * PUSH_MULTICALL; in which case PL_comppad no longer
4916 * points to newcv's pad. */
4917 if (newcv != last_pushed_cv || PL_comppad != last_pad)
4919 I32 depth = (newcv == caller_cv) ? 0 : 1;
4920 if (last_pushed_cv) {
4921 CHANGE_MULTICALL_WITHDEPTH(newcv, depth);
4924 PUSH_MULTICALL_WITHDEPTH(newcv, depth);
4926 last_pushed_cv = newcv;
4929 /* these assignments are just to silence compiler
4931 multicall_cop = NULL;
4934 last_pad = PL_comppad;
4936 /* the initial nextstate you would normally execute
4937 * at the start of an eval (which would cause error
4938 * messages to come from the eval), may be optimised
4939 * away from the execution path in the regex code blocks;
4940 * so manually set PL_curcop to it initially */
4942 OP *o = cUNOPx(nop)->op_first;
4943 assert(o->op_type == OP_NULL);
4944 if (o->op_targ == OP_SCOPE) {
4945 o = cUNOPo->op_first;
4948 assert(o->op_targ == OP_LEAVE);
4949 o = cUNOPo->op_first;
4950 assert(o->op_type == OP_ENTER);
4954 if (o->op_type != OP_STUB) {
4955 assert( o->op_type == OP_NEXTSTATE
4956 || o->op_type == OP_DBSTATE
4957 || (o->op_type == OP_NULL
4958 && ( o->op_targ == OP_NEXTSTATE
4959 || o->op_targ == OP_DBSTATE
4963 PL_curcop = (COP*)o;
4968 DEBUG_STATE_r( PerlIO_printf(Perl_debug_log,
4969 " re EVAL PL_op=0x%"UVxf"\n", PTR2UV(nop)) );
4971 rex->offs[0].end = PL_reg_magic->mg_len = locinput - PL_bostr;
4974 SV *sv_mrk = get_sv("REGMARK", 1);
4975 sv_setsv(sv_mrk, sv_yes_mark);
4978 /* we don't use MULTICALL here as we want to call the
4979 * first op of the block of interest, rather than the
4980 * first op of the sub */
4981 before = (IV)(SP-PL_stack_base);
4983 CALLRUNOPS(aTHX); /* Scalar context. */
4985 if ((IV)(SP-PL_stack_base) == before)
4986 ret = &PL_sv_undef; /* protect against empty (?{}) blocks. */
4992 /* before restoring everything, evaluate the returned
4993 * value, so that 'uninit' warnings don't use the wrong
4994 * PL_op or pad. Also need to process any magic vars
4995 * (e.g. $1) *before* parentheses are restored */
5000 if (logical == 0) /* (?{})/ */
5001 sv_setsv(save_scalar(PL_replgv), ret); /* $^R */
5002 else if (logical == 1) { /* /(?(?{...})X|Y)/ */
5003 sw = cBOOL(SvTRUE(ret));
5006 else { /* /(??{}) */
5007 /* if its overloaded, let the regex compiler handle
5008 * it; otherwise extract regex, or stringify */
5009 if (!SvAMAGIC(ret)) {
5013 if (SvTYPE(sv) == SVt_REGEXP)
5014 re_sv = (REGEXP*) sv;
5015 else if (SvSMAGICAL(sv)) {
5016 MAGIC *mg = mg_find(sv, PERL_MAGIC_qr);
5018 re_sv = (REGEXP *) mg->mg_obj;
5021 /* force any magic, undef warnings here */
5023 ret = sv_mortalcopy(ret);
5024 (void) SvPV_force_nolen(ret);
5030 Copy(&saved_state, &PL_reg_state, 1, struct re_save_state);
5032 /* *** Note that at this point we don't restore
5033 * PL_comppad, (or pop the CxSUB) on the assumption it may
5034 * be used again soon. This is safe as long as nothing
5035 * in the regexp code uses the pad ! */
5037 PL_curcop = ocurcop;
5038 PL_regeol = saved_regeol;
5039 S_regcp_restore(aTHX_ rex, runops_cp, &maxopenparen);
5045 /* only /(??{})/ from now on */
5048 /* extract RE object from returned value; compiling if
5052 re_sv = reg_temp_copy(NULL, re_sv);
5057 if (SvUTF8(ret) && IN_BYTES) {
5058 /* In use 'bytes': make a copy of the octet
5059 * sequence, but without the flag on */
5061 const char *const p = SvPV(ret, len);
5062 ret = newSVpvn_flags(p, len, SVs_TEMP);
5064 if (rex->intflags & PREGf_USE_RE_EVAL)
5065 pm_flags |= PMf_USE_RE_EVAL;
5067 /* if we got here, it should be an engine which
5068 * supports compiling code blocks and stuff */
5069 assert(rex->engine && rex->engine->op_comp);
5070 assert(!(scan->flags & ~RXf_PMf_COMPILETIME));
5071 re_sv = rex->engine->op_comp(aTHX_ &ret, 1, NULL,
5072 rex->engine, NULL, NULL,
5073 /* copy /msix etc to inner pattern */
5078 & (SVs_TEMP | SVs_PADTMP | SVf_READONLY
5080 /* This isn't a first class regexp. Instead, it's
5081 caching a regexp onto an existing, Perl visible
5083 sv_magic(ret, MUTABLE_SV(re_sv), PERL_MAGIC_qr, 0, 0);
5085 /* safe to do now that any $1 etc has been
5086 * interpolated into the new pattern string and
5088 S_regcp_restore(aTHX_ rex, runops_cp, &maxopenparen);
5093 RXp_MATCH_COPIED_off(re);
5094 re->subbeg = rex->subbeg;
5095 re->sublen = rex->sublen;
5096 re->suboffset = rex->suboffset;
5097 re->subcoffset = rex->subcoffset;
5100 debug_start_match(re_sv, utf8_target, locinput, PL_regeol,
5101 "Matching embedded");
5103 startpoint = rei->program + 1;
5104 ST.close_paren = 0; /* only used for GOSUB */
5106 eval_recurse_doit: /* Share code with GOSUB below this line */
5107 /* run the pattern returned from (??{...}) */
5109 /* Save *all* the positions. */
5110 ST.cp = regcppush(rex, 0, maxopenparen);
5111 REGCP_SET(ST.lastcp);
5114 re->lastcloseparen = 0;
5118 /* XXXX This is too dramatic a measure... */
5121 ST.toggle_reg_flags = PL_reg_flags;
5123 PL_reg_flags |= RF_utf8;
5125 PL_reg_flags &= ~RF_utf8;
5126 ST.toggle_reg_flags ^= PL_reg_flags; /* diff of old and new */
5128 ST.prev_rex = rex_sv;
5129 ST.prev_curlyx = cur_curlyx;
5131 SET_reg_curpm(rex_sv);
5136 ST.prev_eval = cur_eval;
5138 /* now continue from first node in postoned RE */
5139 PUSH_YES_STATE_GOTO(EVAL_AB, startpoint, locinput);
5140 assert(0); /* NOTREACHED */
5143 case EVAL_AB: /* cleanup after a successful (??{A})B */
5144 /* note: this is called twice; first after popping B, then A */
5145 PL_reg_flags ^= ST.toggle_reg_flags;
5146 rex_sv = ST.prev_rex;
5147 SET_reg_curpm(rex_sv);
5148 rex = ReANY(rex_sv);
5149 rexi = RXi_GET(rex);
5151 cur_eval = ST.prev_eval;
5152 cur_curlyx = ST.prev_curlyx;
5154 /* XXXX This is too dramatic a measure... */
5156 if ( nochange_depth )
5161 case EVAL_AB_fail: /* unsuccessfully ran A or B in (??{A})B */
5162 /* note: this is called twice; first after popping B, then A */
5163 PL_reg_flags ^= ST.toggle_reg_flags;
5164 rex_sv = ST.prev_rex;
5165 SET_reg_curpm(rex_sv);
5166 rex = ReANY(rex_sv);
5167 rexi = RXi_GET(rex);
5169 REGCP_UNWIND(ST.lastcp);
5170 regcppop(rex, &maxopenparen);
5171 cur_eval = ST.prev_eval;
5172 cur_curlyx = ST.prev_curlyx;
5173 /* XXXX This is too dramatic a measure... */
5175 if ( nochange_depth )
5181 n = ARG(scan); /* which paren pair */
5182 rex->offs[n].start_tmp = locinput - PL_bostr;
5183 if (n > maxopenparen)
5185 DEBUG_BUFFERS_r(PerlIO_printf(Perl_debug_log,
5186 "rex=0x%"UVxf" offs=0x%"UVxf": \\%"UVuf": set %"IVdf" tmp; maxopenparen=%"UVuf"\n",
5190 (IV)rex->offs[n].start_tmp,
5196 /* XXX really need to log other places start/end are set too */
5197 #define CLOSE_CAPTURE \
5198 rex->offs[n].start = rex->offs[n].start_tmp; \
5199 rex->offs[n].end = locinput - PL_bostr; \
5200 DEBUG_BUFFERS_r(PerlIO_printf(Perl_debug_log, \
5201 "rex=0x%"UVxf" offs=0x%"UVxf": \\%"UVuf": set %"IVdf"..%"IVdf"\n", \
5203 PTR2UV(rex->offs), \
5205 (IV)rex->offs[n].start, \
5206 (IV)rex->offs[n].end \
5210 n = ARG(scan); /* which paren pair */
5212 if (n > rex->lastparen)
5214 rex->lastcloseparen = n;
5215 if (cur_eval && cur_eval->u.eval.close_paren == n) {
5220 case ACCEPT: /* (*ACCEPT) */
5224 cursor && OP(cursor)!=END;
5225 cursor=regnext(cursor))
5227 if ( OP(cursor)==CLOSE ){
5229 if ( n <= lastopen ) {
5231 if (n > rex->lastparen)
5233 rex->lastcloseparen = n;
5234 if ( n == ARG(scan) || (cur_eval &&
5235 cur_eval->u.eval.close_paren == n))
5244 case GROUPP: /* (?(1)) */
5245 n = ARG(scan); /* which paren pair */
5246 sw = cBOOL(rex->lastparen >= n && rex->offs[n].end != -1);
5249 case NGROUPP: /* (?(<name>)) */
5250 /* reg_check_named_buff_matched returns 0 for no match */
5251 sw = cBOOL(0 < reg_check_named_buff_matched(rex,scan));
5254 case INSUBP: /* (?(R)) */
5256 sw = (cur_eval && (!n || cur_eval->u.eval.close_paren == n));
5259 case DEFINEP: /* (?(DEFINE)) */
5263 case IFTHEN: /* (?(cond)A|B) */
5264 PL_reg_leftiter = PL_reg_maxiter; /* Void cache */
5266 next = NEXTOPER(NEXTOPER(scan));
5268 next = scan + ARG(scan);
5269 if (OP(next) == IFTHEN) /* Fake one. */
5270 next = NEXTOPER(NEXTOPER(next));
5274 case LOGICAL: /* modifier for EVAL and IFMATCH */
5275 logical = scan->flags;
5278 /*******************************************************************
5280 The CURLYX/WHILEM pair of ops handle the most generic case of the /A*B/
5281 pattern, where A and B are subpatterns. (For simple A, CURLYM or
5282 STAR/PLUS/CURLY/CURLYN are used instead.)
5284 A*B is compiled as <CURLYX><A><WHILEM><B>
5286 On entry to the subpattern, CURLYX is called. This pushes a CURLYX
5287 state, which contains the current count, initialised to -1. It also sets
5288 cur_curlyx to point to this state, with any previous value saved in the
5291 CURLYX then jumps straight to the WHILEM op, rather than executing A,
5292 since the pattern may possibly match zero times (i.e. it's a while {} loop
5293 rather than a do {} while loop).
5295 Each entry to WHILEM represents a successful match of A. The count in the
5296 CURLYX block is incremented, another WHILEM state is pushed, and execution
5297 passes to A or B depending on greediness and the current count.
5299 For example, if matching against the string a1a2a3b (where the aN are
5300 substrings that match /A/), then the match progresses as follows: (the
5301 pushed states are interspersed with the bits of strings matched so far):
5304 <CURLYX cnt=0><WHILEM>
5305 <CURLYX cnt=1><WHILEM> a1 <WHILEM>
5306 <CURLYX cnt=2><WHILEM> a1 <WHILEM> a2 <WHILEM>
5307 <CURLYX cnt=3><WHILEM> a1 <WHILEM> a2 <WHILEM> a3 <WHILEM>
5308 <CURLYX cnt=3><WHILEM> a1 <WHILEM> a2 <WHILEM> a3 <WHILEM> b
5310 (Contrast this with something like CURLYM, which maintains only a single
5314 a1 <CURLYM cnt=1> a2
5315 a1 a2 <CURLYM cnt=2> a3
5316 a1 a2 a3 <CURLYM cnt=3> b
5319 Each WHILEM state block marks a point to backtrack to upon partial failure
5320 of A or B, and also contains some minor state data related to that
5321 iteration. The CURLYX block, pointed to by cur_curlyx, contains the
5322 overall state, such as the count, and pointers to the A and B ops.
5324 This is complicated slightly by nested CURLYX/WHILEM's. Since cur_curlyx
5325 must always point to the *current* CURLYX block, the rules are:
5327 When executing CURLYX, save the old cur_curlyx in the CURLYX state block,
5328 and set cur_curlyx to point the new block.
5330 When popping the CURLYX block after a successful or unsuccessful match,
5331 restore the previous cur_curlyx.
5333 When WHILEM is about to execute B, save the current cur_curlyx, and set it
5334 to the outer one saved in the CURLYX block.
5336 When popping the WHILEM block after a successful or unsuccessful B match,
5337 restore the previous cur_curlyx.
5339 Here's an example for the pattern (AI* BI)*BO
5340 I and O refer to inner and outer, C and W refer to CURLYX and WHILEM:
5343 curlyx backtrack stack
5344 ------ ---------------
5346 CO <CO prev=NULL> <WO>
5347 CI <CO prev=NULL> <WO> <CI prev=CO> <WI> ai
5348 CO <CO prev=NULL> <WO> <CI prev=CO> <WI> ai <WI prev=CI> bi
5349 NULL <CO prev=NULL> <WO> <CI prev=CO> <WI> ai <WI prev=CI> bi <WO prev=CO> bo
5351 At this point the pattern succeeds, and we work back down the stack to
5352 clean up, restoring as we go:
5354 CO <CO prev=NULL> <WO> <CI prev=CO> <WI> ai <WI prev=CI> bi
5355 CI <CO prev=NULL> <WO> <CI prev=CO> <WI> ai
5356 CO <CO prev=NULL> <WO>
5359 *******************************************************************/
5361 #define ST st->u.curlyx
5363 case CURLYX: /* start of /A*B/ (for complex A) */
5365 /* No need to save/restore up to this paren */
5366 I32 parenfloor = scan->flags;
5368 assert(next); /* keep Coverity happy */
5369 if (OP(PREVOPER(next)) == NOTHING) /* LONGJMP */
5372 /* XXXX Probably it is better to teach regpush to support
5373 parenfloor > maxopenparen ... */
5374 if (parenfloor > (I32)rex->lastparen)
5375 parenfloor = rex->lastparen; /* Pessimization... */
5377 ST.prev_curlyx= cur_curlyx;
5379 ST.cp = PL_savestack_ix;
5381 /* these fields contain the state of the current curly.
5382 * they are accessed by subsequent WHILEMs */
5383 ST.parenfloor = parenfloor;
5388 ST.count = -1; /* this will be updated by WHILEM */
5389 ST.lastloc = NULL; /* this will be updated by WHILEM */
5391 PUSH_YES_STATE_GOTO(CURLYX_end, PREVOPER(next), locinput);
5392 assert(0); /* NOTREACHED */
5395 case CURLYX_end: /* just finished matching all of A*B */
5396 cur_curlyx = ST.prev_curlyx;
5398 assert(0); /* NOTREACHED */
5400 case CURLYX_end_fail: /* just failed to match all of A*B */
5402 cur_curlyx = ST.prev_curlyx;
5404 assert(0); /* NOTREACHED */
5408 #define ST st->u.whilem
5410 case WHILEM: /* just matched an A in /A*B/ (for complex A) */
5412 /* see the discussion above about CURLYX/WHILEM */
5414 int min = ARG1(cur_curlyx->u.curlyx.me);
5415 int max = ARG2(cur_curlyx->u.curlyx.me);
5416 regnode *A = NEXTOPER(cur_curlyx->u.curlyx.me) + EXTRA_STEP_2ARGS;
5418 assert(cur_curlyx); /* keep Coverity happy */
5419 n = ++cur_curlyx->u.curlyx.count; /* how many A's matched */
5420 ST.save_lastloc = cur_curlyx->u.curlyx.lastloc;
5421 ST.cache_offset = 0;
5425 DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log,
5426 "%*s whilem: matched %ld out of %d..%d\n",
5427 REPORT_CODE_OFF+depth*2, "", (long)n, min, max)
5430 /* First just match a string of min A's. */
5433 ST.cp = regcppush(rex, cur_curlyx->u.curlyx.parenfloor,
5435 cur_curlyx->u.curlyx.lastloc = locinput;
5436 REGCP_SET(ST.lastcp);
5438 PUSH_STATE_GOTO(WHILEM_A_pre, A, locinput);
5439 assert(0); /* NOTREACHED */
5442 /* If degenerate A matches "", assume A done. */
5444 if (locinput == cur_curlyx->u.curlyx.lastloc) {
5445 DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log,
5446 "%*s whilem: empty match detected, trying continuation...\n",
5447 REPORT_CODE_OFF+depth*2, "")
5449 goto do_whilem_B_max;
5452 /* super-linear cache processing */
5456 if (!PL_reg_maxiter) {
5457 /* start the countdown: Postpone detection until we
5458 * know the match is not *that* much linear. */
5459 PL_reg_maxiter = (PL_regeol - PL_bostr + 1) * (scan->flags>>4);
5460 /* possible overflow for long strings and many CURLYX's */
5461 if (PL_reg_maxiter < 0)
5462 PL_reg_maxiter = I32_MAX;
5463 PL_reg_leftiter = PL_reg_maxiter;
5466 if (PL_reg_leftiter-- == 0) {
5467 /* initialise cache */
5468 const I32 size = (PL_reg_maxiter + 7)/8;
5469 if (PL_reg_poscache) {
5470 if ((I32)PL_reg_poscache_size < size) {
5471 Renew(PL_reg_poscache, size, char);
5472 PL_reg_poscache_size = size;
5474 Zero(PL_reg_poscache, size, char);
5477 PL_reg_poscache_size = size;
5478 Newxz(PL_reg_poscache, size, char);
5480 DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log,
5481 "%swhilem: Detected a super-linear match, switching on caching%s...\n",
5482 PL_colors[4], PL_colors[5])
5486 if (PL_reg_leftiter < 0) {
5487 /* have we already failed at this position? */
5489 offset = (scan->flags & 0xf) - 1
5490 + (locinput - PL_bostr) * (scan->flags>>4);
5491 mask = 1 << (offset % 8);
5493 if (PL_reg_poscache[offset] & mask) {
5494 DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log,
5495 "%*s whilem: (cache) already tried at this position...\n",
5496 REPORT_CODE_OFF+depth*2, "")
5498 sayNO; /* cache records failure */
5500 ST.cache_offset = offset;
5501 ST.cache_mask = mask;
5505 /* Prefer B over A for minimal matching. */
5507 if (cur_curlyx->u.curlyx.minmod) {
5508 ST.save_curlyx = cur_curlyx;
5509 cur_curlyx = cur_curlyx->u.curlyx.prev_curlyx;
5510 ST.cp = regcppush(rex, ST.save_curlyx->u.curlyx.parenfloor,
5512 REGCP_SET(ST.lastcp);
5513 PUSH_YES_STATE_GOTO(WHILEM_B_min, ST.save_curlyx->u.curlyx.B,
5515 assert(0); /* NOTREACHED */
5518 /* Prefer A over B for maximal matching. */
5520 if (n < max) { /* More greed allowed? */
5521 ST.cp = regcppush(rex, cur_curlyx->u.curlyx.parenfloor,
5523 cur_curlyx->u.curlyx.lastloc = locinput;
5524 REGCP_SET(ST.lastcp);
5525 PUSH_STATE_GOTO(WHILEM_A_max, A, locinput);
5526 assert(0); /* NOTREACHED */
5528 goto do_whilem_B_max;
5530 assert(0); /* NOTREACHED */
5532 case WHILEM_B_min: /* just matched B in a minimal match */
5533 case WHILEM_B_max: /* just matched B in a maximal match */
5534 cur_curlyx = ST.save_curlyx;
5536 assert(0); /* NOTREACHED */
5538 case WHILEM_B_max_fail: /* just failed to match B in a maximal match */
5539 cur_curlyx = ST.save_curlyx;
5540 cur_curlyx->u.curlyx.lastloc = ST.save_lastloc;
5541 cur_curlyx->u.curlyx.count--;
5543 assert(0); /* NOTREACHED */
5545 case WHILEM_A_min_fail: /* just failed to match A in a minimal match */
5547 case WHILEM_A_pre_fail: /* just failed to match even minimal A */
5548 REGCP_UNWIND(ST.lastcp);
5549 regcppop(rex, &maxopenparen);
5550 cur_curlyx->u.curlyx.lastloc = ST.save_lastloc;
5551 cur_curlyx->u.curlyx.count--;
5553 assert(0); /* NOTREACHED */
5555 case WHILEM_A_max_fail: /* just failed to match A in a maximal match */
5556 REGCP_UNWIND(ST.lastcp);
5557 regcppop(rex, &maxopenparen); /* Restore some previous $<digit>s? */
5558 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
5559 "%*s whilem: failed, trying continuation...\n",
5560 REPORT_CODE_OFF+depth*2, "")
5563 if (cur_curlyx->u.curlyx.count >= REG_INFTY
5564 && ckWARN(WARN_REGEXP)
5565 && !(PL_reg_flags & RF_warned))
5567 PL_reg_flags |= RF_warned;
5568 Perl_warner(aTHX_ packWARN(WARN_REGEXP),
5569 "Complex regular subexpression recursion limit (%d) "
5575 ST.save_curlyx = cur_curlyx;
5576 cur_curlyx = cur_curlyx->u.curlyx.prev_curlyx;
5577 PUSH_YES_STATE_GOTO(WHILEM_B_max, ST.save_curlyx->u.curlyx.B,
5579 assert(0); /* NOTREACHED */
5581 case WHILEM_B_min_fail: /* just failed to match B in a minimal match */
5582 cur_curlyx = ST.save_curlyx;
5583 REGCP_UNWIND(ST.lastcp);
5584 regcppop(rex, &maxopenparen);
5586 if (cur_curlyx->u.curlyx.count >= /*max*/ARG2(cur_curlyx->u.curlyx.me)) {
5587 /* Maximum greed exceeded */
5588 if (cur_curlyx->u.curlyx.count >= REG_INFTY
5589 && ckWARN(WARN_REGEXP)
5590 && !(PL_reg_flags & RF_warned))
5592 PL_reg_flags |= RF_warned;
5593 Perl_warner(aTHX_ packWARN(WARN_REGEXP),
5594 "Complex regular subexpression recursion "
5595 "limit (%d) exceeded",
5598 cur_curlyx->u.curlyx.count--;
5602 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
5603 "%*s trying longer...\n", REPORT_CODE_OFF+depth*2, "")
5605 /* Try grabbing another A and see if it helps. */
5606 cur_curlyx->u.curlyx.lastloc = locinput;
5607 ST.cp = regcppush(rex, cur_curlyx->u.curlyx.parenfloor,
5609 REGCP_SET(ST.lastcp);
5610 PUSH_STATE_GOTO(WHILEM_A_min,
5611 /*A*/ NEXTOPER(ST.save_curlyx->u.curlyx.me) + EXTRA_STEP_2ARGS,
5613 assert(0); /* NOTREACHED */
5616 #define ST st->u.branch
5618 case BRANCHJ: /* /(...|A|...)/ with long next pointer */
5619 next = scan + ARG(scan);
5622 scan = NEXTOPER(scan);
5625 case BRANCH: /* /(...|A|...)/ */
5626 scan = NEXTOPER(scan); /* scan now points to inner node */
5627 ST.lastparen = rex->lastparen;
5628 ST.lastcloseparen = rex->lastcloseparen;
5629 ST.next_branch = next;
5632 /* Now go into the branch */
5634 PUSH_YES_STATE_GOTO(BRANCH_next, scan, locinput);
5636 PUSH_STATE_GOTO(BRANCH_next, scan, locinput);
5638 assert(0); /* NOTREACHED */
5640 case CUTGROUP: /* /(*THEN)/ */
5641 sv_yes_mark = st->u.mark.mark_name = scan->flags ? NULL :
5642 MUTABLE_SV(rexi->data->data[ ARG( scan ) ]);
5643 PUSH_STATE_GOTO(CUTGROUP_next, next, locinput);
5644 assert(0); /* NOTREACHED */
5646 case CUTGROUP_next_fail:
5649 if (st->u.mark.mark_name)
5650 sv_commit = st->u.mark.mark_name;
5652 assert(0); /* NOTREACHED */
5656 assert(0); /* NOTREACHED */
5658 case BRANCH_next_fail: /* that branch failed; try the next, if any */
5663 REGCP_UNWIND(ST.cp);
5664 UNWIND_PAREN(ST.lastparen, ST.lastcloseparen);
5665 scan = ST.next_branch;
5666 /* no more branches? */
5667 if (!scan || (OP(scan) != BRANCH && OP(scan) != BRANCHJ)) {
5669 PerlIO_printf( Perl_debug_log,
5670 "%*s %sBRANCH failed...%s\n",
5671 REPORT_CODE_OFF+depth*2, "",
5677 continue; /* execute next BRANCH[J] op */
5678 assert(0); /* NOTREACHED */
5680 case MINMOD: /* next op will be non-greedy, e.g. A*? */
5685 #define ST st->u.curlym
5687 case CURLYM: /* /A{m,n}B/ where A is fixed-length */
5689 /* This is an optimisation of CURLYX that enables us to push
5690 * only a single backtracking state, no matter how many matches
5691 * there are in {m,n}. It relies on the pattern being constant
5692 * length, with no parens to influence future backrefs
5696 scan = NEXTOPER(scan) + NODE_STEP_REGNODE;
5698 ST.lastparen = rex->lastparen;
5699 ST.lastcloseparen = rex->lastcloseparen;
5701 /* if paren positive, emulate an OPEN/CLOSE around A */
5703 U32 paren = ST.me->flags;
5704 if (paren > maxopenparen)
5705 maxopenparen = paren;
5706 scan += NEXT_OFF(scan); /* Skip former OPEN. */
5714 ST.c1 = CHRTEST_UNINIT;
5717 if (!(ST.minmod ? ARG1(ST.me) : ARG2(ST.me))) /* min/max */
5720 curlym_do_A: /* execute the A in /A{m,n}B/ */
5721 PUSH_YES_STATE_GOTO(CURLYM_A, ST.A, locinput); /* match A */
5722 assert(0); /* NOTREACHED */
5724 case CURLYM_A: /* we've just matched an A */
5726 /* after first match, determine A's length: u.curlym.alen */
5727 if (ST.count == 1) {
5728 if (PL_reg_match_utf8) {
5729 char *s = st->locinput;
5730 while (s < locinput) {
5736 ST.alen = locinput - st->locinput;
5739 ST.count = ST.minmod ? ARG1(ST.me) : ARG2(ST.me);
5742 PerlIO_printf(Perl_debug_log,
5743 "%*s CURLYM now matched %"IVdf" times, len=%"IVdf"...\n",
5744 (int)(REPORT_CODE_OFF+(depth*2)), "",
5745 (IV) ST.count, (IV)ST.alen)
5748 if (cur_eval && cur_eval->u.eval.close_paren &&
5749 cur_eval->u.eval.close_paren == (U32)ST.me->flags)
5753 I32 max = (ST.minmod ? ARG1(ST.me) : ARG2(ST.me));
5754 if ( max == REG_INFTY || ST.count < max )
5755 goto curlym_do_A; /* try to match another A */
5757 goto curlym_do_B; /* try to match B */
5759 case CURLYM_A_fail: /* just failed to match an A */
5760 REGCP_UNWIND(ST.cp);
5762 if (ST.minmod || ST.count < ARG1(ST.me) /* min*/
5763 || (cur_eval && cur_eval->u.eval.close_paren &&
5764 cur_eval->u.eval.close_paren == (U32)ST.me->flags))
5767 curlym_do_B: /* execute the B in /A{m,n}B/ */
5768 if (ST.c1 == CHRTEST_UNINIT) {
5769 /* calculate c1 and c2 for possible match of 1st char
5770 * following curly */
5771 ST.c1 = ST.c2 = CHRTEST_VOID;
5772 if (HAS_TEXT(ST.B) || JUMPABLE(ST.B)) {
5773 regnode *text_node = ST.B;
5774 if (! HAS_TEXT(text_node))
5775 FIND_NEXT_IMPT(text_node);
5778 (HAS_TEXT(text_node) && PL_regkind[OP(text_node)] == EXACT)
5780 But the former is redundant in light of the latter.
5782 if this changes back then the macro for
5783 IS_TEXT and friends need to change.
5785 if (PL_regkind[OP(text_node)] == EXACT) {
5786 if (! S_setup_EXACTISH_ST_c1_c2(aTHX_
5787 text_node, &ST.c1, ST.c1_utf8, &ST.c2, ST.c2_utf8))
5796 PerlIO_printf(Perl_debug_log,
5797 "%*s CURLYM trying tail with matches=%"IVdf"...\n",
5798 (int)(REPORT_CODE_OFF+(depth*2)),
5801 if (! NEXTCHR_IS_EOS && ST.c1 != CHRTEST_VOID) {
5802 if (! UTF8_IS_INVARIANT(nextchr) && utf8_target) {
5803 if (memNE(locinput, ST.c1_utf8, UTF8SKIP(locinput))
5804 && memNE(locinput, ST.c2_utf8, UTF8SKIP(locinput)))
5806 /* simulate B failing */
5808 PerlIO_printf(Perl_debug_log,
5809 "%*s CURLYM Fast bail next target=U+%"UVXf" c1=U+%"UVXf" c2=U+%"UVXf"\n",
5810 (int)(REPORT_CODE_OFF+(depth*2)),"",
5811 valid_utf8_to_uvchr((U8 *) locinput, NULL),
5812 valid_utf8_to_uvchr(ST.c1_utf8, NULL),
5813 valid_utf8_to_uvchr(ST.c2_utf8, NULL))
5815 state_num = CURLYM_B_fail;
5816 goto reenter_switch;
5819 else if (nextchr != ST.c1 && nextchr != ST.c2) {
5820 /* simulate B failing */
5822 PerlIO_printf(Perl_debug_log,
5823 "%*s CURLYM Fast bail next target=U+%X c1=U+%X c2=U+%X\n",
5824 (int)(REPORT_CODE_OFF+(depth*2)),"",
5825 (int) nextchr, ST.c1, ST.c2)
5827 state_num = CURLYM_B_fail;
5828 goto reenter_switch;
5833 /* emulate CLOSE: mark current A as captured */
5834 I32 paren = ST.me->flags;
5836 rex->offs[paren].start
5837 = HOPc(locinput, -ST.alen) - PL_bostr;
5838 rex->offs[paren].end = locinput - PL_bostr;
5839 if ((U32)paren > rex->lastparen)
5840 rex->lastparen = paren;
5841 rex->lastcloseparen = paren;
5844 rex->offs[paren].end = -1;
5845 if (cur_eval && cur_eval->u.eval.close_paren &&
5846 cur_eval->u.eval.close_paren == (U32)ST.me->flags)
5855 PUSH_STATE_GOTO(CURLYM_B, ST.B, locinput); /* match B */
5856 assert(0); /* NOTREACHED */
5858 case CURLYM_B_fail: /* just failed to match a B */
5859 REGCP_UNWIND(ST.cp);
5860 UNWIND_PAREN(ST.lastparen, ST.lastcloseparen);
5862 I32 max = ARG2(ST.me);
5863 if (max != REG_INFTY && ST.count == max)
5865 goto curlym_do_A; /* try to match a further A */
5867 /* backtrack one A */
5868 if (ST.count == ARG1(ST.me) /* min */)
5871 SET_locinput(HOPc(locinput, -ST.alen));
5872 goto curlym_do_B; /* try to match B */
5875 #define ST st->u.curly
5877 #define CURLY_SETPAREN(paren, success) \
5880 rex->offs[paren].start = HOPc(locinput, -1) - PL_bostr; \
5881 rex->offs[paren].end = locinput - PL_bostr; \
5882 if (paren > rex->lastparen) \
5883 rex->lastparen = paren; \
5884 rex->lastcloseparen = paren; \
5887 rex->offs[paren].end = -1; \
5888 rex->lastparen = ST.lastparen; \
5889 rex->lastcloseparen = ST.lastcloseparen; \
5893 case STAR: /* /A*B/ where A is width 1 char */
5897 scan = NEXTOPER(scan);
5900 case PLUS: /* /A+B/ where A is width 1 char */
5904 scan = NEXTOPER(scan);
5907 case CURLYN: /* /(A){m,n}B/ where A is width 1 char */
5908 ST.paren = scan->flags; /* Which paren to set */
5909 ST.lastparen = rex->lastparen;
5910 ST.lastcloseparen = rex->lastcloseparen;
5911 if (ST.paren > maxopenparen)
5912 maxopenparen = ST.paren;
5913 ST.min = ARG1(scan); /* min to match */
5914 ST.max = ARG2(scan); /* max to match */
5915 if (cur_eval && cur_eval->u.eval.close_paren &&
5916 cur_eval->u.eval.close_paren == (U32)ST.paren) {
5920 scan = regnext(NEXTOPER(scan) + NODE_STEP_REGNODE);
5923 case CURLY: /* /A{m,n}B/ where A is width 1 char */
5925 ST.min = ARG1(scan); /* min to match */
5926 ST.max = ARG2(scan); /* max to match */
5927 scan = NEXTOPER(scan) + NODE_STEP_REGNODE;
5930 * Lookahead to avoid useless match attempts
5931 * when we know what character comes next.
5933 * Used to only do .*x and .*?x, but now it allows
5934 * for )'s, ('s and (?{ ... })'s to be in the way
5935 * of the quantifier and the EXACT-like node. -- japhy
5938 assert(ST.min <= ST.max);
5939 if (! HAS_TEXT(next) && ! JUMPABLE(next)) {
5940 ST.c1 = ST.c2 = CHRTEST_VOID;
5943 regnode *text_node = next;
5945 if (! HAS_TEXT(text_node))
5946 FIND_NEXT_IMPT(text_node);
5948 if (! HAS_TEXT(text_node))
5949 ST.c1 = ST.c2 = CHRTEST_VOID;
5951 if ( PL_regkind[OP(text_node)] != EXACT ) {
5952 ST.c1 = ST.c2 = CHRTEST_VOID;
5956 /* Currently we only get here when
5958 PL_rekind[OP(text_node)] == EXACT
5960 if this changes back then the macro for IS_TEXT and
5961 friends need to change. */
5962 if (! S_setup_EXACTISH_ST_c1_c2(aTHX_
5963 text_node, &ST.c1, ST.c1_utf8, &ST.c2, ST.c2_utf8))
5974 char *li = locinput;
5976 if (ST.min && regrepeat(rex, &li, ST.A, ST.min, depth) < ST.min)
5981 if (ST.c1 == CHRTEST_VOID)
5982 goto curly_try_B_min;
5984 ST.oldloc = locinput;
5986 /* set ST.maxpos to the furthest point along the
5987 * string that could possibly match */
5988 if (ST.max == REG_INFTY) {
5989 ST.maxpos = PL_regeol - 1;
5991 while (UTF8_IS_CONTINUATION(*(U8*)ST.maxpos))
5994 else if (utf8_target) {
5995 int m = ST.max - ST.min;
5996 for (ST.maxpos = locinput;
5997 m >0 && ST.maxpos < PL_regeol; m--)
5998 ST.maxpos += UTF8SKIP(ST.maxpos);
6001 ST.maxpos = locinput + ST.max - ST.min;
6002 if (ST.maxpos >= PL_regeol)
6003 ST.maxpos = PL_regeol - 1;
6005 goto curly_try_B_min_known;
6009 /* avoid taking address of locinput, so it can remain
6011 char *li = locinput;
6012 ST.count = regrepeat(rex, &li, ST.A, ST.max, depth);
6013 if (ST.count < ST.min)
6016 if ((ST.count > ST.min)
6017 && (PL_regkind[OP(ST.B)] == EOL) && (OP(ST.B) != MEOL))
6019 /* A{m,n} must come at the end of the string, there's
6020 * no point in backing off ... */
6022 /* ...except that $ and \Z can match before *and* after
6023 newline at the end. Consider "\n\n" =~ /\n+\Z\n/.
6024 We may back off by one in this case. */
6025 if (UCHARAT(locinput - 1) == '\n' && OP(ST.B) != EOS)
6029 goto curly_try_B_max;
6031 assert(0); /* NOTREACHED */
6034 case CURLY_B_min_known_fail:
6035 /* failed to find B in a non-greedy match where c1,c2 valid */
6037 REGCP_UNWIND(ST.cp);
6039 UNWIND_PAREN(ST.lastparen, ST.lastcloseparen);
6041 /* Couldn't or didn't -- move forward. */
6042 ST.oldloc = locinput;
6044 locinput += UTF8SKIP(locinput);
6048 curly_try_B_min_known:
6049 /* find the next place where 'B' could work, then call B */
6053 n = (ST.oldloc == locinput) ? 0 : 1;
6054 if (ST.c1 == ST.c2) {
6055 /* set n to utf8_distance(oldloc, locinput) */
6056 while (locinput <= ST.maxpos
6057 && memNE(locinput, ST.c1_utf8, UTF8SKIP(locinput)))
6059 locinput += UTF8SKIP(locinput);
6064 /* set n to utf8_distance(oldloc, locinput) */
6065 while (locinput <= ST.maxpos
6066 && memNE(locinput, ST.c1_utf8, UTF8SKIP(locinput))
6067 && memNE(locinput, ST.c2_utf8, UTF8SKIP(locinput)))
6069 locinput += UTF8SKIP(locinput);
6074 else { /* Not utf8_target */
6075 if (ST.c1 == ST.c2) {
6076 while (locinput <= ST.maxpos &&
6077 UCHARAT(locinput) != ST.c1)
6081 while (locinput <= ST.maxpos
6082 && UCHARAT(locinput) != ST.c1
6083 && UCHARAT(locinput) != ST.c2)
6086 n = locinput - ST.oldloc;
6088 if (locinput > ST.maxpos)
6091 /* In /a{m,n}b/, ST.oldloc is at "a" x m, locinput is
6092 * at b; check that everything between oldloc and
6093 * locinput matches */
6094 char *li = ST.oldloc;
6096 if (regrepeat(rex, &li, ST.A, n, depth) < n)
6098 assert(n == REG_INFTY || locinput == li);
6100 CURLY_SETPAREN(ST.paren, ST.count);
6101 if (cur_eval && cur_eval->u.eval.close_paren &&
6102 cur_eval->u.eval.close_paren == (U32)ST.paren) {
6105 PUSH_STATE_GOTO(CURLY_B_min_known, ST.B, locinput);
6107 assert(0); /* NOTREACHED */
6110 case CURLY_B_min_fail:
6111 /* failed to find B in a non-greedy match where c1,c2 invalid */
6113 REGCP_UNWIND(ST.cp);
6115 UNWIND_PAREN(ST.lastparen, ST.lastcloseparen);
6117 /* failed -- move forward one */
6119 char *li = locinput;
6120 if (!regrepeat(rex, &li, ST.A, 1, depth)) {
6127 if (ST.count <= ST.max || (ST.max == REG_INFTY &&
6128 ST.count > 0)) /* count overflow ? */
6131 CURLY_SETPAREN(ST.paren, ST.count);
6132 if (cur_eval && cur_eval->u.eval.close_paren &&
6133 cur_eval->u.eval.close_paren == (U32)ST.paren) {
6136 PUSH_STATE_GOTO(CURLY_B_min, ST.B, locinput);
6140 assert(0); /* NOTREACHED */
6144 /* a successful greedy match: now try to match B */
6145 if (cur_eval && cur_eval->u.eval.close_paren &&
6146 cur_eval->u.eval.close_paren == (U32)ST.paren) {
6150 bool could_match = locinput < PL_regeol;
6152 /* If it could work, try it. */
6153 if (ST.c1 != CHRTEST_VOID && could_match) {
6154 if (! UTF8_IS_INVARIANT(UCHARAT(locinput)) && utf8_target)
6156 could_match = memEQ(locinput,
6161 UTF8SKIP(locinput));
6164 could_match = UCHARAT(locinput) == ST.c1
6165 || UCHARAT(locinput) == ST.c2;
6168 if (ST.c1 == CHRTEST_VOID || could_match) {
6169 CURLY_SETPAREN(ST.paren, ST.count);
6170 PUSH_STATE_GOTO(CURLY_B_max, ST.B, locinput);
6171 assert(0); /* NOTREACHED */
6176 case CURLY_B_max_fail:
6177 /* failed to find B in a greedy match */
6179 REGCP_UNWIND(ST.cp);
6181 UNWIND_PAREN(ST.lastparen, ST.lastcloseparen);
6184 if (--ST.count < ST.min)
6186 locinput = HOPc(locinput, -1);
6187 goto curly_try_B_max;
6191 case END: /* last op of main pattern */
6194 /* we've just finished A in /(??{A})B/; now continue with B */
6195 st->u.eval.toggle_reg_flags
6196 = cur_eval->u.eval.toggle_reg_flags;
6197 PL_reg_flags ^= st->u.eval.toggle_reg_flags;
6199 st->u.eval.prev_rex = rex_sv; /* inner */
6201 /* Save *all* the positions. */
6202 st->u.eval.cp = regcppush(rex, 0, maxopenparen);
6203 rex_sv = cur_eval->u.eval.prev_rex;
6204 SET_reg_curpm(rex_sv);
6205 rex = ReANY(rex_sv);
6206 rexi = RXi_GET(rex);
6207 cur_curlyx = cur_eval->u.eval.prev_curlyx;
6209 REGCP_SET(st->u.eval.lastcp);
6211 /* Restore parens of the outer rex without popping the
6213 S_regcp_restore(aTHX_ rex, cur_eval->u.eval.lastcp,
6216 st->u.eval.prev_eval = cur_eval;
6217 cur_eval = cur_eval->u.eval.prev_eval;
6219 PerlIO_printf(Perl_debug_log, "%*s EVAL trying tail ... %"UVxf"\n",
6220 REPORT_CODE_OFF+depth*2, "",PTR2UV(cur_eval)););
6221 if ( nochange_depth )
6224 PUSH_YES_STATE_GOTO(EVAL_AB, st->u.eval.prev_eval->u.eval.B,
6225 locinput); /* match B */
6228 if (locinput < reginfo->till) {
6229 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
6230 "%sMatch possible, but length=%ld is smaller than requested=%ld, failing!%s\n",
6232 (long)(locinput - PL_reg_starttry),
6233 (long)(reginfo->till - PL_reg_starttry),
6236 sayNO_SILENT; /* Cannot match: too short. */
6238 sayYES; /* Success! */
6240 case SUCCEED: /* successful SUSPEND/UNLESSM/IFMATCH/CURLYM */
6242 PerlIO_printf(Perl_debug_log,
6243 "%*s %ssubpattern success...%s\n",
6244 REPORT_CODE_OFF+depth*2, "", PL_colors[4], PL_colors[5]));
6245 sayYES; /* Success! */
6248 #define ST st->u.ifmatch
6253 case SUSPEND: /* (?>A) */
6255 newstart = locinput;
6258 case UNLESSM: /* -ve lookaround: (?!A), or with flags, (?<!A) */
6260 goto ifmatch_trivial_fail_test;
6262 case IFMATCH: /* +ve lookaround: (?=A), or with flags, (?<=A) */
6264 ifmatch_trivial_fail_test:
6266 char * const s = HOPBACKc(locinput, scan->flags);
6271 sw = 1 - cBOOL(ST.wanted);
6275 next = scan + ARG(scan);
6283 newstart = locinput;
6287 ST.logical = logical;
6288 logical = 0; /* XXX: reset state of logical once it has been saved into ST */
6290 /* execute body of (?...A) */
6291 PUSH_YES_STATE_GOTO(IFMATCH_A, NEXTOPER(NEXTOPER(scan)), newstart);
6292 assert(0); /* NOTREACHED */
6295 case IFMATCH_A_fail: /* body of (?...A) failed */
6296 ST.wanted = !ST.wanted;
6299 case IFMATCH_A: /* body of (?...A) succeeded */
6301 sw = cBOOL(ST.wanted);
6303 else if (!ST.wanted)
6306 if (OP(ST.me) != SUSPEND) {
6307 /* restore old position except for (?>...) */
6308 locinput = st->locinput;
6310 scan = ST.me + ARG(ST.me);
6313 continue; /* execute B */
6317 case LONGJMP: /* alternative with many branches compiles to
6318 * (BRANCHJ; EXACT ...; LONGJMP ) x N */
6319 next = scan + ARG(scan);
6324 case COMMIT: /* (*COMMIT) */
6325 reginfo->cutpoint = PL_regeol;
6328 case PRUNE: /* (*PRUNE) */
6330 sv_yes_mark = sv_commit = MUTABLE_SV(rexi->data->data[ ARG( scan ) ]);
6331 PUSH_STATE_GOTO(COMMIT_next, next, locinput);
6332 assert(0); /* NOTREACHED */
6334 case COMMIT_next_fail:
6338 case OPFAIL: /* (*FAIL) */
6340 assert(0); /* NOTREACHED */
6342 #define ST st->u.mark
6343 case MARKPOINT: /* (*MARK:foo) */
6344 ST.prev_mark = mark_state;
6345 ST.mark_name = sv_commit = sv_yes_mark
6346 = MUTABLE_SV(rexi->data->data[ ARG( scan ) ]);
6348 ST.mark_loc = locinput;
6349 PUSH_YES_STATE_GOTO(MARKPOINT_next, next, locinput);
6350 assert(0); /* NOTREACHED */
6352 case MARKPOINT_next:
6353 mark_state = ST.prev_mark;
6355 assert(0); /* NOTREACHED */
6357 case MARKPOINT_next_fail:
6358 if (popmark && sv_eq(ST.mark_name,popmark))
6360 if (ST.mark_loc > startpoint)
6361 reginfo->cutpoint = HOPBACKc(ST.mark_loc, 1);
6362 popmark = NULL; /* we found our mark */
6363 sv_commit = ST.mark_name;
6366 PerlIO_printf(Perl_debug_log,
6367 "%*s %ssetting cutpoint to mark:%"SVf"...%s\n",
6368 REPORT_CODE_OFF+depth*2, "",
6369 PL_colors[4], SVfARG(sv_commit), PL_colors[5]);
6372 mark_state = ST.prev_mark;
6373 sv_yes_mark = mark_state ?
6374 mark_state->u.mark.mark_name : NULL;
6376 assert(0); /* NOTREACHED */
6378 case SKIP: /* (*SKIP) */
6380 /* (*SKIP) : if we fail we cut here*/
6381 ST.mark_name = NULL;
6382 ST.mark_loc = locinput;
6383 PUSH_STATE_GOTO(SKIP_next,next, locinput);
6385 /* (*SKIP:NAME) : if there is a (*MARK:NAME) fail where it was,
6386 otherwise do nothing. Meaning we need to scan
6388 regmatch_state *cur = mark_state;
6389 SV *find = MUTABLE_SV(rexi->data->data[ ARG( scan ) ]);
6392 if ( sv_eq( cur->u.mark.mark_name,
6395 ST.mark_name = find;
6396 PUSH_STATE_GOTO( SKIP_next, next, locinput);
6398 cur = cur->u.mark.prev_mark;
6401 /* Didn't find our (*MARK:NAME) so ignore this (*SKIP:NAME) */
6404 case SKIP_next_fail:
6406 /* (*CUT:NAME) - Set up to search for the name as we
6407 collapse the stack*/
6408 popmark = ST.mark_name;
6410 /* (*CUT) - No name, we cut here.*/
6411 if (ST.mark_loc > startpoint)
6412 reginfo->cutpoint = HOPBACKc(ST.mark_loc, 1);
6413 /* but we set sv_commit to latest mark_name if there
6414 is one so they can test to see how things lead to this
6417 sv_commit=mark_state->u.mark.mark_name;
6421 assert(0); /* NOTREACHED */
6424 case LNBREAK: /* \R */
6425 if ((n=is_LNBREAK_safe(locinput, PL_regeol, utf8_target))) {
6432 PerlIO_printf(Perl_error_log, "%"UVxf" %d\n",
6433 PTR2UV(scan), OP(scan));
6434 Perl_croak(aTHX_ "regexp memory corruption");
6436 /* this is a point to jump to in order to increment
6437 * locinput by one character */
6439 assert(!NEXTCHR_IS_EOS);
6441 locinput += PL_utf8skip[nextchr];
6442 /* locinput is allowed to go 1 char off the end, but not 2+ */
6443 if (locinput > PL_regeol)
6452 /* switch break jumps here */
6453 scan = next; /* prepare to execute the next op and ... */
6454 continue; /* ... jump back to the top, reusing st */
6455 assert(0); /* NOTREACHED */
6458 /* push a state that backtracks on success */
6459 st->u.yes.prev_yes_state = yes_state;
6463 /* push a new regex state, then continue at scan */
6465 regmatch_state *newst;
6468 regmatch_state *cur = st;
6469 regmatch_state *curyes = yes_state;
6471 regmatch_slab *slab = PL_regmatch_slab;
6472 for (;curd > -1;cur--,curd--) {
6473 if (cur < SLAB_FIRST(slab)) {
6475 cur = SLAB_LAST(slab);
6477 PerlIO_printf(Perl_error_log, "%*s#%-3d %-10s %s\n",
6478 REPORT_CODE_OFF + 2 + depth * 2,"",
6479 curd, PL_reg_name[cur->resume_state],
6480 (curyes == cur) ? "yes" : ""
6483 curyes = cur->u.yes.prev_yes_state;
6486 DEBUG_STATE_pp("push")
6489 st->locinput = locinput;
6491 if (newst > SLAB_LAST(PL_regmatch_slab))
6492 newst = S_push_slab(aTHX);
6493 PL_regmatch_state = newst;
6495 locinput = pushinput;
6498 assert(0); /* NOTREACHED */
6503 * We get here only if there's trouble -- normally "case END" is
6504 * the terminating point.
6506 Perl_croak(aTHX_ "corrupted regexp pointers");
6512 /* we have successfully completed a subexpression, but we must now
6513 * pop to the state marked by yes_state and continue from there */
6514 assert(st != yes_state);
6516 while (st != yes_state) {
6518 if (st < SLAB_FIRST(PL_regmatch_slab)) {
6519 PL_regmatch_slab = PL_regmatch_slab->prev;
6520 st = SLAB_LAST(PL_regmatch_slab);
6524 DEBUG_STATE_pp("pop (no final)");
6526 DEBUG_STATE_pp("pop (yes)");
6532 while (yes_state < SLAB_FIRST(PL_regmatch_slab)
6533 || yes_state > SLAB_LAST(PL_regmatch_slab))
6535 /* not in this slab, pop slab */
6536 depth -= (st - SLAB_FIRST(PL_regmatch_slab) + 1);
6537 PL_regmatch_slab = PL_regmatch_slab->prev;
6538 st = SLAB_LAST(PL_regmatch_slab);
6540 depth -= (st - yes_state);
6543 yes_state = st->u.yes.prev_yes_state;
6544 PL_regmatch_state = st;
6547 locinput= st->locinput;
6548 state_num = st->resume_state + no_final;
6549 goto reenter_switch;
6552 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "%sMatch successful!%s\n",
6553 PL_colors[4], PL_colors[5]));
6555 if (PL_reg_state.re_state_eval_setup_done) {
6556 /* each successfully executed (?{...}) block does the equivalent of
6557 * local $^R = do {...}
6558 * When popping the save stack, all these locals would be undone;
6559 * bypass this by setting the outermost saved $^R to the latest
6561 if (oreplsv != GvSV(PL_replgv))
6562 sv_setsv(oreplsv, GvSV(PL_replgv));
6569 PerlIO_printf(Perl_debug_log,
6570 "%*s %sfailed...%s\n",
6571 REPORT_CODE_OFF+depth*2, "",
6572 PL_colors[4], PL_colors[5])
6584 /* there's a previous state to backtrack to */
6586 if (st < SLAB_FIRST(PL_regmatch_slab)) {
6587 PL_regmatch_slab = PL_regmatch_slab->prev;
6588 st = SLAB_LAST(PL_regmatch_slab);
6590 PL_regmatch_state = st;
6591 locinput= st->locinput;
6593 DEBUG_STATE_pp("pop");
6595 if (yes_state == st)
6596 yes_state = st->u.yes.prev_yes_state;
6598 state_num = st->resume_state + 1; /* failure = success + 1 */
6599 goto reenter_switch;
6604 if (rex->intflags & PREGf_VERBARG_SEEN) {
6605 SV *sv_err = get_sv("REGERROR", 1);
6606 SV *sv_mrk = get_sv("REGMARK", 1);
6608 sv_commit = &PL_sv_no;
6610 sv_yes_mark = &PL_sv_yes;
6613 sv_commit = &PL_sv_yes;
6614 sv_yes_mark = &PL_sv_no;
6616 sv_setsv(sv_err, sv_commit);
6617 sv_setsv(sv_mrk, sv_yes_mark);
6621 if (last_pushed_cv) {
6624 PERL_UNUSED_VAR(SP);
6627 /* clean up; in particular, free all slabs above current one */
6628 LEAVE_SCOPE(oldsave);
6630 assert(!result || locinput - PL_bostr >= 0);
6631 return result ? locinput - PL_bostr : -1;
6635 - regrepeat - repeatedly match something simple, report how many
6637 * What 'simple' means is a node which can be the operand of a quantifier like
6640 * startposp - pointer a pointer to the start position. This is updated
6641 * to point to the byte following the highest successful
6643 * p - the regnode to be repeatedly matched against.
6644 * max - maximum number of things to match.
6645 * depth - (for debugging) backtracking depth.
6648 S_regrepeat(pTHX_ const regexp *prog, char **startposp, const regnode *p, I32 max, int depth)
6651 char *scan; /* Pointer to current position in target string */
6653 char *loceol = PL_regeol; /* local version */
6654 I32 hardcount = 0; /* How many matches so far */
6655 bool utf8_target = PL_reg_match_utf8;
6656 int to_complement = 0; /* Invert the result? */
6658 _char_class_number classnum;
6660 PERL_UNUSED_ARG(depth);
6663 PERL_ARGS_ASSERT_REGREPEAT;
6666 if (max == REG_INFTY)
6668 else if (! utf8_target && scan + max < loceol)
6669 loceol = scan + max;
6671 /* Here, for the case of a non-UTF-8 target we have adjusted <loceol> down
6672 * to the maximum of how far we should go in it (leaving it set to the real
6673 * end, if the maximum permissible would take us beyond that). This allows
6674 * us to make the loop exit condition that we haven't gone past <loceol> to
6675 * also mean that we haven't exceeded the max permissible count, saving a
6676 * test each time through the loop. But it assumes that the OP matches a
6677 * single byte, which is true for most of the OPs below when applied to a
6678 * non-UTF-8 target. Those relatively few OPs that don't have this
6679 * characteristic will have to compensate.
6681 * There is no adjustment for UTF-8 targets, as the number of bytes per
6682 * character varies. OPs will have to test both that the count is less
6683 * than the max permissible (using <hardcount> to keep track), and that we
6684 * are still within the bounds of the string (using <loceol>. A few OPs
6685 * match a single byte no matter what the encoding. They can omit the max
6686 * test if, for the UTF-8 case, they do the adjustment that was skipped
6689 * Thus, the code above sets things up for the common case; and exceptional
6690 * cases need extra work; the common case is to make sure <scan> doesn't
6691 * go past <loceol>, and for UTF-8 to also use <hardcount> to make sure the
6692 * count doesn't exceed the maximum permissible */
6697 while (scan < loceol && hardcount < max && *scan != '\n') {
6698 scan += UTF8SKIP(scan);
6702 while (scan < loceol && *scan != '\n')
6708 while (scan < loceol && hardcount < max) {
6709 scan += UTF8SKIP(scan);
6716 case CANY: /* Move <scan> forward <max> bytes, unless goes off end */
6717 if (utf8_target && scan + max < loceol) {
6719 /* <loceol> hadn't been adjusted in the UTF-8 case */
6727 assert(STR_LEN(p) == (UTF_PATTERN) ? UTF8SKIP(STRING(p)) : 1);
6731 /* Can use a simple loop if the pattern char to match on is invariant
6732 * under UTF-8, or both target and pattern aren't UTF-8. Note that we
6733 * can use UTF8_IS_INVARIANT() even if the pattern isn't UTF-8, as it's
6734 * true iff it doesn't matter if the argument is in UTF-8 or not */
6735 if (UTF8_IS_INVARIANT(c) || (! utf8_target && ! UTF_PATTERN)) {
6736 if (utf8_target && scan + max < loceol) {
6737 /* We didn't adjust <loceol> because is UTF-8, but ok to do so,
6738 * since here, to match at all, 1 char == 1 byte */
6739 loceol = scan + max;
6741 while (scan < loceol && UCHARAT(scan) == c) {
6745 else if (UTF_PATTERN) {
6747 STRLEN scan_char_len;
6749 /* When both target and pattern are UTF-8, we have to do
6751 while (hardcount < max
6753 && (scan_char_len = UTF8SKIP(scan)) <= STR_LEN(p)
6754 && memEQ(scan, STRING(p), scan_char_len))
6756 scan += scan_char_len;
6760 else if (! UTF8_IS_ABOVE_LATIN1(c)) {
6762 /* Target isn't utf8; convert the character in the UTF-8
6763 * pattern to non-UTF8, and do a simple loop */
6764 c = TWO_BYTE_UTF8_TO_UNI(c, *(STRING(p) + 1));
6765 while (scan < loceol && UCHARAT(scan) == c) {
6768 } /* else pattern char is above Latin1, can't possibly match the
6773 /* Here, the string must be utf8; pattern isn't, and <c> is
6774 * different in utf8 than not, so can't compare them directly.
6775 * Outside the loop, find the two utf8 bytes that represent c, and
6776 * then look for those in sequence in the utf8 string */
6777 U8 high = UTF8_TWO_BYTE_HI(c);
6778 U8 low = UTF8_TWO_BYTE_LO(c);
6780 while (hardcount < max
6781 && scan + 1 < loceol
6782 && UCHARAT(scan) == high
6783 && UCHARAT(scan + 1) == low)
6792 utf8_flags = FOLDEQ_UTF8_NOMIX_ASCII;
6796 PL_reg_flags |= RF_tainted;
6797 utf8_flags = FOLDEQ_UTF8_LOCALE;
6805 case EXACTFU_TRICKYFOLD:
6807 utf8_flags = (UTF_PATTERN) ? FOLDEQ_S2_ALREADY_FOLDED : 0;
6811 U8 c1_utf8[UTF8_MAXBYTES+1], c2_utf8[UTF8_MAXBYTES+1];
6813 assert(STR_LEN(p) == (UTF_PATTERN) ? UTF8SKIP(STRING(p)) : 1);
6815 if (S_setup_EXACTISH_ST_c1_c2(aTHX_ p, &c1, c1_utf8, &c2, c2_utf8)) {
6816 if (c1 == CHRTEST_VOID) {
6817 /* Use full Unicode fold matching */
6818 char *tmpeol = PL_regeol;
6819 STRLEN pat_len = (UTF_PATTERN) ? UTF8SKIP(STRING(p)) : 1;
6820 while (hardcount < max
6821 && foldEQ_utf8_flags(scan, &tmpeol, 0, utf8_target,
6822 STRING(p), NULL, pat_len,
6823 cBOOL(UTF_PATTERN), utf8_flags))
6830 else if (utf8_target) {
6832 while (scan < loceol
6834 && memEQ(scan, c1_utf8, UTF8SKIP(scan)))
6836 scan += UTF8SKIP(scan);
6841 while (scan < loceol
6843 && (memEQ(scan, c1_utf8, UTF8SKIP(scan))
6844 || memEQ(scan, c2_utf8, UTF8SKIP(scan))))
6846 scan += UTF8SKIP(scan);
6851 else if (c1 == c2) {
6852 while (scan < loceol && UCHARAT(scan) == c1) {
6857 while (scan < loceol &&
6858 (UCHARAT(scan) == c1 || UCHARAT(scan) == c2))
6868 while (hardcount < max
6870 && reginclass(prog, p, (U8*)scan, utf8_target))
6872 scan += UTF8SKIP(scan);
6876 while (scan < loceol && REGINCLASS(prog, p, (U8*)scan))
6881 /* The argument (FLAGS) to all the POSIX node types is the class number */
6888 PL_reg_flags |= RF_tainted;
6889 if (! utf8_target) {
6890 while (scan < loceol && to_complement ^ cBOOL(isFOO_lc(FLAGS(p),
6896 while (hardcount < max && scan < loceol
6897 && to_complement ^ cBOOL(isFOO_utf8_lc(FLAGS(p),
6900 scan += UTF8SKIP(scan);
6913 if (utf8_target && scan + max < loceol) {
6915 /* We didn't adjust <loceol> at the beginning of this routine
6916 * because is UTF-8, but it is actually ok to do so, since here, to
6917 * match, 1 char == 1 byte. */
6918 loceol = scan + max;
6920 while (scan < loceol && _generic_isCC_A((U8) *scan, FLAGS(p))) {
6933 if (! utf8_target) {
6934 while (scan < loceol && ! _generic_isCC_A((U8) *scan, FLAGS(p))) {
6940 /* The complement of something that matches only ASCII matches all
6941 * UTF-8 variant code points, plus everything in ASCII that isn't
6943 while (hardcount < max && scan < loceol
6944 && (! UTF8_IS_INVARIANT(*scan)
6945 || ! _generic_isCC_A((U8) *scan, FLAGS(p))))
6947 scan += UTF8SKIP(scan);
6958 if (! utf8_target) {
6959 while (scan < loceol && to_complement
6960 ^ cBOOL(_generic_isCC((U8) *scan, FLAGS(p))))
6967 classnum = (_char_class_number) FLAGS(p);
6968 if (classnum < _FIRST_NON_SWASH_CC) {
6970 /* Here, a swash is needed for above-Latin1 code points.
6971 * Process as many Latin1 code points using the built-in rules.
6972 * Go to another loop to finish processing upon encountering
6973 * the first Latin1 code point. We could do that in this loop
6974 * as well, but the other way saves having to test if the swash
6975 * has been loaded every time through the loop: extra space to
6977 while (hardcount < max && scan < loceol) {
6978 if (UTF8_IS_INVARIANT(*scan)) {
6979 if (! (to_complement ^ cBOOL(_generic_isCC((U8) *scan,
6986 else if (UTF8_IS_DOWNGRADEABLE_START(*scan)) {
6987 if (! (to_complement
6988 ^ cBOOL(_generic_isCC(TWO_BYTE_UTF8_TO_UNI(*scan,
6997 goto found_above_latin1;
7004 /* For these character classes, the knowledge of how to handle
7005 * every code point is compiled in to Perl via a macro. This
7006 * code is written for making the loops as tight as possible.
7007 * It could be refactored to save space instead */
7009 case _CC_ENUM_SPACE: /* XXX would require separate code
7010 if we revert the change of \v
7013 case _CC_ENUM_PSXSPC:
7014 while (hardcount < max
7016 && (to_complement ^ cBOOL(isSPACE_utf8(scan))))
7018 scan += UTF8SKIP(scan);
7022 case _CC_ENUM_BLANK:
7023 while (hardcount < max
7025 && (to_complement ^ cBOOL(isBLANK_utf8(scan))))
7027 scan += UTF8SKIP(scan);
7031 case _CC_ENUM_XDIGIT:
7032 while (hardcount < max
7034 && (to_complement ^ cBOOL(isXDIGIT_utf8(scan))))
7036 scan += UTF8SKIP(scan);
7040 case _CC_ENUM_VERTSPACE:
7041 while (hardcount < max
7043 && (to_complement ^ cBOOL(isVERTWS_utf8(scan))))
7045 scan += UTF8SKIP(scan);
7049 case _CC_ENUM_CNTRL:
7050 while (hardcount < max
7052 && (to_complement ^ cBOOL(isCNTRL_utf8(scan))))
7054 scan += UTF8SKIP(scan);
7059 Perl_croak(aTHX_ "panic: regrepeat() node %d='%s' has an unexpected character class '%d'", OP(p), PL_reg_name[OP(p)], classnum);
7065 found_above_latin1: /* Continuation of POSIXU and NPOSIXU */
7067 /* Load the swash if not already present */
7068 if (! PL_utf8_swash_ptrs[classnum]) {
7069 U8 flags = _CORE_SWASH_INIT_ACCEPT_INVLIST;
7070 PL_utf8_swash_ptrs[classnum] = _core_swash_init(
7071 "utf8", swash_property_names[classnum],
7072 &PL_sv_undef, 1, 0, NULL, &flags);
7075 while (hardcount < max && scan < loceol
7076 && to_complement ^ cBOOL(_generic_utf8(
7079 swash_fetch(PL_utf8_swash_ptrs[classnum],
7083 scan += UTF8SKIP(scan);
7090 while (hardcount < max && scan < loceol &&
7091 (c=is_LNBREAK_utf8_safe(scan, loceol))) {
7096 /* LNBREAK can match one or two latin chars, which is ok, but we
7097 * have to use hardcount in this situation, and throw away the
7098 * adjustment to <loceol> done before the switch statement */
7100 while (scan < loceol && (c=is_LNBREAK_latin1_safe(scan, loceol))) {
7121 /* These are all 0 width, so match right here or not at all. */
7125 Perl_croak(aTHX_ "panic: regrepeat() called with unrecognized node type %d='%s'", OP(p), PL_reg_name[OP(p)]);
7126 assert(0); /* NOTREACHED */
7133 c = scan - *startposp;
7137 GET_RE_DEBUG_FLAGS_DECL;
7139 SV * const prop = sv_newmortal();
7140 regprop(prog, prop, p);
7141 PerlIO_printf(Perl_debug_log,
7142 "%*s %s can match %"IVdf" times out of %"IVdf"...\n",
7143 REPORT_CODE_OFF + depth*2, "", SvPVX_const(prop),(IV)c,(IV)max);
7151 #if !defined(PERL_IN_XSUB_RE) || defined(PLUGGABLE_RE_EXTENSION)
7153 - regclass_swash - prepare the utf8 swash. Wraps the shared core version to
7154 create a copy so that changes the caller makes won't change the shared one.
7155 If <altsvp> is non-null, will return NULL in it, for back-compat.
7158 Perl_regclass_swash(pTHX_ const regexp *prog, const regnode* node, bool doinit, SV** listsvp, SV **altsvp)
7160 PERL_ARGS_ASSERT_REGCLASS_SWASH;
7166 return newSVsv(core_regclass_swash(prog, node, doinit, listsvp));
7171 S_core_regclass_swash(pTHX_ const regexp *prog, const regnode* node, bool doinit, SV** listsvp)
7173 /* Returns the swash for the input 'node' in the regex 'prog'.
7174 * If <doinit> is true, will attempt to create the swash if not already
7176 * If <listsvp> is non-null, will return the swash initialization string in
7178 * Tied intimately to how regcomp.c sets up the data structure */
7185 RXi_GET_DECL(prog,progi);
7186 const struct reg_data * const data = prog ? progi->data : NULL;
7188 PERL_ARGS_ASSERT_CORE_REGCLASS_SWASH;
7190 assert(ANYOF_NONBITMAP(node));
7192 if (data && data->count) {
7193 const U32 n = ARG(node);
7195 if (data->what[n] == 's') {
7196 SV * const rv = MUTABLE_SV(data->data[n]);
7197 AV * const av = MUTABLE_AV(SvRV(rv));
7198 SV **const ary = AvARRAY(av);
7199 U8 swash_init_flags = _CORE_SWASH_INIT_ACCEPT_INVLIST;
7201 si = *ary; /* ary[0] = the string to initialize the swash with */
7203 /* Elements 2 and 3 are either both present or both absent. [2] is
7204 * any inversion list generated at compile time; [3] indicates if
7205 * that inversion list has any user-defined properties in it. */
7206 if (av_len(av) >= 2) {
7209 swash_init_flags |= _CORE_SWASH_INIT_USER_DEFINED_PROPERTY;
7216 /* Element [1] is reserved for the set-up swash. If already there,
7217 * return it; if not, create it and store it there */
7218 if (SvROK(ary[1])) {
7221 else if (si && doinit) {
7223 sw = _core_swash_init("utf8", /* the utf8 package */
7227 0, /* not from tr/// */
7230 (void)av_store(av, 1, sw);
7236 SV* matches_string = newSVpvn("", 0);
7238 /* Use the swash, if any, which has to have incorporated into it all
7240 if ((! sw || (invlist = _get_swash_invlist(sw)) == NULL)
7241 && (si && si != &PL_sv_undef))
7244 /* If no swash, use the input initialization string, if available */
7245 sv_catsv(matches_string, si);
7248 /* Add the inversion list to whatever we have. This may have come from
7249 * the swash, or from an input parameter */
7251 sv_catsv(matches_string, _invlist_contents(invlist));
7253 *listsvp = matches_string;
7260 - reginclass - determine if a character falls into a character class
7262 n is the ANYOF regnode
7263 p is the target string
7264 utf8_target tells whether p is in UTF-8.
7266 Returns true if matched; false otherwise.
7268 Note that this can be a synthetic start class, a combination of various
7269 nodes, so things you think might be mutually exclusive, such as locale,
7270 aren't. It can match both locale and non-locale
7275 S_reginclass(pTHX_ const regexp * const prog, const regnode * const n, const U8* const p, const bool utf8_target)
7278 const char flags = ANYOF_FLAGS(n);
7282 PERL_ARGS_ASSERT_REGINCLASS;
7284 /* If c is not already the code point, get it. Note that
7285 * UTF8_IS_INVARIANT() works even if not in UTF-8 */
7286 if (! UTF8_IS_INVARIANT(c) && utf8_target) {
7288 c = utf8n_to_uvchr(p, UTF8_MAXBYTES, &c_len,
7289 (UTF8_ALLOW_DEFAULT & UTF8_ALLOW_ANYUV)
7290 | UTF8_ALLOW_FFFF | UTF8_CHECK_ONLY);
7291 /* see [perl #37836] for UTF8_ALLOW_ANYUV; [perl #38293] for
7292 * UTF8_ALLOW_FFFF */
7293 if (c_len == (STRLEN)-1)
7294 Perl_croak(aTHX_ "Malformed UTF-8 character (fatal)");
7297 /* If this character is potentially in the bitmap, check it */
7299 if (ANYOF_BITMAP_TEST(n, c))
7301 else if (flags & ANYOF_NON_UTF8_LATIN1_ALL
7307 else if (flags & ANYOF_LOCALE) {
7308 PL_reg_flags |= RF_tainted;
7310 if ((flags & ANYOF_LOC_FOLD)
7311 && ANYOF_BITMAP_TEST(n, PL_fold_locale[c]))
7315 else if (ANYOF_CLASS_TEST_ANY_SET(n)) {
7317 /* The data structure is arranged so bits 0, 2, 4, ... are set
7318 * if the class includes the Posix character class given by
7319 * bit/2; and 1, 3, 5, ... are set if the class includes the
7320 * complemented Posix class given by int(bit/2). So we loop
7321 * through the bits, each time changing whether we complement
7322 * the result or not. Suppose for the sake of illustration
7323 * that bits 0-3 mean respectively, \w, \W, \s, \S. If bit 0
7324 * is set, it means there is a match for this ANYOF node if the
7325 * character is in the class given by the expression (0 / 2 = 0
7326 * = \w). If it is in that class, isFOO_lc() will return 1,
7327 * and since 'to_complement' is 0, the result will stay TRUE,
7328 * and we exit the loop. Suppose instead that bit 0 is 0, but
7329 * bit 1 is 1. That means there is a match if the character
7330 * matches \W. We won't bother to call isFOO_lc() on bit 0,
7331 * but will on bit 1. On the second iteration 'to_complement'
7332 * will be 1, so the exclusive or will reverse things, so we
7333 * are testing for \W. On the third iteration, 'to_complement'
7334 * will be 0, and we would be testing for \s; the fourth
7335 * iteration would test for \S, etc. */
7338 int to_complement = 0;
7339 while (count < ANYOF_MAX) {
7340 if (ANYOF_CLASS_TEST(n, count)
7341 && to_complement ^ cBOOL(isFOO_lc(count/2, (U8) c)))
7353 /* If the bitmap didn't (or couldn't) match, and something outside the
7354 * bitmap could match, try that. Locale nodes specify completely the
7355 * behavior of code points in the bit map (otherwise, a utf8 target would
7356 * cause them to be treated as Unicode and not locale), except in
7357 * the very unlikely event when this node is a synthetic start class, which
7358 * could be a combination of locale and non-locale nodes. So allow locale
7359 * to match for the synthetic start class, which will give a false
7360 * positive that will be resolved when the match is done again as not part
7361 * of the synthetic start class */
7363 if (utf8_target && (flags & ANYOF_UNICODE_ALL) && c >= 256) {
7364 match = TRUE; /* Everything above 255 matches */
7366 else if (ANYOF_NONBITMAP(n)
7367 && ((flags & ANYOF_NONBITMAP_NON_UTF8)
7370 || (! (flags & ANYOF_LOCALE))
7371 || (flags & ANYOF_IS_SYNTHETIC)))))
7373 SV * const sw = core_regclass_swash(prog, n, TRUE, 0);
7378 } else { /* Convert to utf8 */
7380 utf8_p = bytes_to_utf8(p, &len);
7383 if (swash_fetch(sw, utf8_p, TRUE)) {
7387 /* If we allocated a string above, free it */
7388 if (! utf8_target) Safefree(utf8_p);
7392 if (UNICODE_IS_SUPER(c)
7393 && (flags & ANYOF_WARN_SUPER)
7394 && ckWARN_d(WARN_NON_UNICODE))
7396 Perl_warner(aTHX_ packWARN(WARN_NON_UNICODE),
7397 "Code point 0x%04"UVXf" is not Unicode, all \\p{} matches fail; all \\P{} matches succeed", c);
7401 /* The xor complements the return if to invert: 1^1 = 0, 1^0 = 1 */
7402 return cBOOL(flags & ANYOF_INVERT) ^ match;
7406 S_reghop3(U8 *s, I32 off, const U8* lim)
7408 /* return the position 'off' UTF-8 characters away from 's', forward if
7409 * 'off' >= 0, backwards if negative. But don't go outside of position
7410 * 'lim', which better be < s if off < 0 */
7414 PERL_ARGS_ASSERT_REGHOP3;
7417 while (off-- && s < lim) {
7418 /* XXX could check well-formedness here */
7423 while (off++ && s > lim) {
7425 if (UTF8_IS_CONTINUED(*s)) {
7426 while (s > lim && UTF8_IS_CONTINUATION(*s))
7429 /* XXX could check well-formedness here */
7436 /* there are a bunch of places where we use two reghop3's that should
7437 be replaced with this routine. but since thats not done yet
7438 we ifdef it out - dmq
7441 S_reghop4(U8 *s, I32 off, const U8* llim, const U8* rlim)
7445 PERL_ARGS_ASSERT_REGHOP4;
7448 while (off-- && s < rlim) {
7449 /* XXX could check well-formedness here */
7454 while (off++ && s > llim) {
7456 if (UTF8_IS_CONTINUED(*s)) {
7457 while (s > llim && UTF8_IS_CONTINUATION(*s))
7460 /* XXX could check well-formedness here */
7468 S_reghopmaybe3(U8* s, I32 off, const U8* lim)
7472 PERL_ARGS_ASSERT_REGHOPMAYBE3;
7475 while (off-- && s < lim) {
7476 /* XXX could check well-formedness here */
7483 while (off++ && s > lim) {
7485 if (UTF8_IS_CONTINUED(*s)) {
7486 while (s > lim && UTF8_IS_CONTINUATION(*s))
7489 /* XXX could check well-formedness here */
7498 restore_pos(pTHX_ void *arg)
7501 regexp * const rex = (regexp *)arg;
7502 if (PL_reg_state.re_state_eval_setup_done) {
7503 if (PL_reg_oldsaved) {
7504 rex->subbeg = PL_reg_oldsaved;
7505 rex->sublen = PL_reg_oldsavedlen;
7506 rex->suboffset = PL_reg_oldsavedoffset;
7507 rex->subcoffset = PL_reg_oldsavedcoffset;
7509 rex->saved_copy = PL_nrs;
7511 RXp_MATCH_COPIED_on(rex);
7513 PL_reg_magic->mg_len = PL_reg_oldpos;
7514 PL_reg_state.re_state_eval_setup_done = FALSE;
7515 PL_curpm = PL_reg_oldcurpm;
7520 S_to_utf8_substr(pTHX_ regexp *prog)
7522 /* Converts substr fields in prog from bytes to UTF-8, calling fbm_compile
7523 * on the converted value */
7527 PERL_ARGS_ASSERT_TO_UTF8_SUBSTR;
7530 if (prog->substrs->data[i].substr
7531 && !prog->substrs->data[i].utf8_substr) {
7532 SV* const sv = newSVsv(prog->substrs->data[i].substr);
7533 prog->substrs->data[i].utf8_substr = sv;
7534 sv_utf8_upgrade(sv);
7535 if (SvVALID(prog->substrs->data[i].substr)) {
7536 if (SvTAIL(prog->substrs->data[i].substr)) {
7537 /* Trim the trailing \n that fbm_compile added last
7539 SvCUR_set(sv, SvCUR(sv) - 1);
7540 /* Whilst this makes the SV technically "invalid" (as its
7541 buffer is no longer followed by "\0") when fbm_compile()
7542 adds the "\n" back, a "\0" is restored. */
7543 fbm_compile(sv, FBMcf_TAIL);
7547 if (prog->substrs->data[i].substr == prog->check_substr)
7548 prog->check_utf8 = sv;
7554 S_to_byte_substr(pTHX_ regexp *prog)
7556 /* Converts substr fields in prog from UTF-8 to bytes, calling fbm_compile
7557 * on the converted value; returns FALSE if can't be converted. */
7562 PERL_ARGS_ASSERT_TO_BYTE_SUBSTR;
7565 if (prog->substrs->data[i].utf8_substr
7566 && !prog->substrs->data[i].substr) {
7567 SV* sv = newSVsv(prog->substrs->data[i].utf8_substr);
7568 if (! sv_utf8_downgrade(sv, TRUE)) {
7571 if (SvVALID(prog->substrs->data[i].utf8_substr)) {
7572 if (SvTAIL(prog->substrs->data[i].utf8_substr)) {
7573 /* Trim the trailing \n that fbm_compile added last
7575 SvCUR_set(sv, SvCUR(sv) - 1);
7576 fbm_compile(sv, FBMcf_TAIL);
7580 prog->substrs->data[i].substr = sv;
7581 if (prog->substrs->data[i].utf8_substr == prog->check_utf8)
7582 prog->check_substr = sv;
7591 * c-indentation-style: bsd
7593 * indent-tabs-mode: nil
7596 * ex: set ts=8 sts=4 sw=4 et: