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 HAS_NONLATIN1_FOLD_CLOSURE(i) _HAS_NONLATIN1_FOLD_CLOSURE_ONLY_FOR_USE_BY_REGCOMP_DOT_C_AND_REGEXEC_DOT_C(i)
102 /* Valid for non-utf8 strings: avoids the reginclass
103 * call if there are no complications: i.e., if everything matchable is
104 * straight forward in the bitmap */
105 #define REGINCLASS(prog,p,c) (ANYOF_FLAGS(p) ? reginclass(prog,p,c,0) \
106 : ANYOF_BITMAP_TEST(p,*(c)))
112 #define CHR_SVLEN(sv) (utf8_target ? sv_len_utf8(sv) : SvCUR(sv))
113 #define CHR_DIST(a,b) (PL_reg_match_utf8 ? utf8_distance(a,b) : a - b)
115 #define HOPc(pos,off) \
116 (char *)(PL_reg_match_utf8 \
117 ? reghop3((U8*)pos, off, (U8*)(off >= 0 ? PL_regeol : PL_bostr)) \
119 #define HOPBACKc(pos, off) \
120 (char*)(PL_reg_match_utf8\
121 ? reghopmaybe3((U8*)pos, -off, (U8*)PL_bostr) \
122 : (pos - off >= PL_bostr) \
126 #define HOP3(pos,off,lim) (PL_reg_match_utf8 ? reghop3((U8*)(pos), off, (U8*)(lim)) : (U8*)(pos + off))
127 #define HOP3c(pos,off,lim) ((char*)HOP3(pos,off,lim))
130 #define NEXTCHR_EOS -10 /* nextchr has fallen off the end */
131 #define NEXTCHR_IS_EOS (nextchr < 0)
133 #define SET_nextchr \
134 nextchr = ((locinput < PL_regeol) ? UCHARAT(locinput) : NEXTCHR_EOS)
136 #define SET_locinput(p) \
141 #define LOAD_UTF8_CHARCLASS(swash_ptr, property_name) STMT_START { \
143 U8 flags = _CORE_SWASH_INIT_ACCEPT_INVLIST; \
144 ENTER; save_re_context(); \
145 swash_ptr = _core_swash_init("utf8", property_name, &PL_sv_undef, \
146 1, 0, NULL, &flags); \
152 /* If in debug mode, we test that a known character properly matches */
154 # define LOAD_UTF8_CHARCLASS_DEBUG_TEST(swash_ptr, \
156 utf8_char_in_property) \
157 LOAD_UTF8_CHARCLASS(swash_ptr, property_name); \
158 assert(swash_fetch(swash_ptr, (U8 *) utf8_char_in_property, TRUE));
160 # define LOAD_UTF8_CHARCLASS_DEBUG_TEST(swash_ptr, \
162 utf8_char_in_property) \
163 LOAD_UTF8_CHARCLASS(swash_ptr, property_name)
166 #define LOAD_UTF8_CHARCLASS_ALNUM() LOAD_UTF8_CHARCLASS_DEBUG_TEST( \
167 PL_utf8_swash_ptrs[_CC_WORDCHAR], \
168 swash_property_names[_CC_WORDCHAR], \
169 GREEK_SMALL_LETTER_IOTA_UTF8)
171 #define LOAD_UTF8_CHARCLASS_GCB() /* Grapheme cluster boundaries */ \
173 LOAD_UTF8_CHARCLASS_DEBUG_TEST(PL_utf8_X_regular_begin, \
174 "_X_regular_begin", \
175 GREEK_SMALL_LETTER_IOTA_UTF8); \
176 LOAD_UTF8_CHARCLASS_DEBUG_TEST(PL_utf8_X_extend, \
178 COMBINING_GRAVE_ACCENT_UTF8); \
181 #define PLACEHOLDER /* Something for the preprocessor to grab onto */
182 /* TODO: Combine JUMPABLE and HAS_TEXT to cache OP(rn) */
184 /* for use after a quantifier and before an EXACT-like node -- japhy */
185 /* it would be nice to rework regcomp.sym to generate this stuff. sigh
187 * NOTE that *nothing* that affects backtracking should be in here, specifically
188 * VERBS must NOT be included. JUMPABLE is used to determine if we can ignore a
189 * node that is in between two EXACT like nodes when ascertaining what the required
190 * "follow" character is. This should probably be moved to regex compile time
191 * although it may be done at run time beause of the REF possibility - more
192 * investigation required. -- demerphq
194 #define JUMPABLE(rn) ( \
196 (OP(rn) == CLOSE && (!cur_eval || cur_eval->u.eval.close_paren != ARG(rn))) || \
198 OP(rn) == SUSPEND || OP(rn) == IFMATCH || \
199 OP(rn) == PLUS || OP(rn) == MINMOD || \
201 (PL_regkind[OP(rn)] == CURLY && ARG1(rn) > 0) \
203 #define IS_EXACT(rn) (PL_regkind[OP(rn)] == EXACT)
205 #define HAS_TEXT(rn) ( IS_EXACT(rn) || PL_regkind[OP(rn)] == REF )
208 /* Currently these are only used when PL_regkind[OP(rn)] == EXACT so
209 we don't need this definition. */
210 #define IS_TEXT(rn) ( OP(rn)==EXACT || OP(rn)==REF || OP(rn)==NREF )
211 #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 )
212 #define IS_TEXTFL(rn) ( OP(rn)==EXACTFL || OP(rn)==REFFL || OP(rn)==NREFFL )
215 /* ... so we use this as its faster. */
216 #define IS_TEXT(rn) ( OP(rn)==EXACT )
217 #define IS_TEXTFU(rn) ( OP(rn)==EXACTFU || OP(rn)==EXACTFU_SS || OP(rn)==EXACTFU_TRICKYFOLD || OP(rn) == EXACTFA)
218 #define IS_TEXTF(rn) ( OP(rn)==EXACTF )
219 #define IS_TEXTFL(rn) ( OP(rn)==EXACTFL )
224 Search for mandatory following text node; for lookahead, the text must
225 follow but for lookbehind (rn->flags != 0) we skip to the next step.
227 #define FIND_NEXT_IMPT(rn) STMT_START { \
228 while (JUMPABLE(rn)) { \
229 const OPCODE type = OP(rn); \
230 if (type == SUSPEND || PL_regkind[type] == CURLY) \
231 rn = NEXTOPER(NEXTOPER(rn)); \
232 else if (type == PLUS) \
234 else if (type == IFMATCH) \
235 rn = (rn->flags == 0) ? NEXTOPER(NEXTOPER(rn)) : rn + ARG(rn); \
236 else rn += NEXT_OFF(rn); \
240 /* These constants are for finding GCB=LV and GCB=LVT in the CLUMP regnode.
241 * These are for the pre-composed Hangul syllables, which are all in a
242 * contiguous block and arranged there in such a way so as to facilitate
243 * alorithmic determination of their characteristics. As such, they don't need
244 * a swash, but can be determined by simple arithmetic. Almost all are
245 * GCB=LVT, but every 28th one is a GCB=LV */
246 #define SBASE 0xAC00 /* Start of block */
247 #define SCount 11172 /* Length of block */
250 static void restore_pos(pTHX_ void *arg);
252 #define REGCP_PAREN_ELEMS 3
253 #define REGCP_OTHER_ELEMS 3
254 #define REGCP_FRAME_ELEMS 1
255 /* REGCP_FRAME_ELEMS are not part of the REGCP_OTHER_ELEMS and
256 * are needed for the regexp context stack bookkeeping. */
259 S_regcppush(pTHX_ const regexp *rex, I32 parenfloor, U32 maxopenparen)
262 const int retval = PL_savestack_ix;
263 const int paren_elems_to_push =
264 (maxopenparen - parenfloor) * REGCP_PAREN_ELEMS;
265 const UV total_elems = paren_elems_to_push + REGCP_OTHER_ELEMS;
266 const UV elems_shifted = total_elems << SAVE_TIGHT_SHIFT;
268 GET_RE_DEBUG_FLAGS_DECL;
270 PERL_ARGS_ASSERT_REGCPPUSH;
272 if (paren_elems_to_push < 0)
273 Perl_croak(aTHX_ "panic: paren_elems_to_push, %i < 0",
274 paren_elems_to_push);
276 if ((elems_shifted >> SAVE_TIGHT_SHIFT) != total_elems)
277 Perl_croak(aTHX_ "panic: paren_elems_to_push offset %"UVuf
278 " out of range (%lu-%ld)",
280 (unsigned long)maxopenparen,
283 SSGROW(total_elems + REGCP_FRAME_ELEMS);
286 if ((int)maxopenparen > (int)parenfloor)
287 PerlIO_printf(Perl_debug_log,
288 "rex=0x%"UVxf" offs=0x%"UVxf": saving capture indices:\n",
293 for (p = parenfloor+1; p <= (I32)maxopenparen; p++) {
294 /* REGCP_PARENS_ELEMS are pushed per pairs of parentheses. */
295 SSPUSHINT(rex->offs[p].end);
296 SSPUSHINT(rex->offs[p].start);
297 SSPUSHINT(rex->offs[p].start_tmp);
298 DEBUG_BUFFERS_r(PerlIO_printf(Perl_debug_log,
299 " \\%"UVuf": %"IVdf"(%"IVdf")..%"IVdf"\n",
301 (IV)rex->offs[p].start,
302 (IV)rex->offs[p].start_tmp,
306 /* REGCP_OTHER_ELEMS are pushed in any case, parentheses or no. */
307 SSPUSHINT(maxopenparen);
308 SSPUSHINT(rex->lastparen);
309 SSPUSHINT(rex->lastcloseparen);
310 SSPUSHUV(SAVEt_REGCONTEXT | elems_shifted); /* Magic cookie. */
315 /* These are needed since we do not localize EVAL nodes: */
316 #define REGCP_SET(cp) \
318 PerlIO_printf(Perl_debug_log, \
319 " Setting an EVAL scope, savestack=%"IVdf"\n", \
320 (IV)PL_savestack_ix)); \
323 #define REGCP_UNWIND(cp) \
325 if (cp != PL_savestack_ix) \
326 PerlIO_printf(Perl_debug_log, \
327 " Clearing an EVAL scope, savestack=%"IVdf"..%"IVdf"\n", \
328 (IV)(cp), (IV)PL_savestack_ix)); \
331 #define UNWIND_PAREN(lp, lcp) \
332 for (n = rex->lastparen; n > lp; n--) \
333 rex->offs[n].end = -1; \
334 rex->lastparen = n; \
335 rex->lastcloseparen = lcp;
339 S_regcppop(pTHX_ regexp *rex, U32 *maxopenparen_p)
344 GET_RE_DEBUG_FLAGS_DECL;
346 PERL_ARGS_ASSERT_REGCPPOP;
348 /* Pop REGCP_OTHER_ELEMS before the parentheses loop starts. */
350 assert((i & SAVE_MASK) == SAVEt_REGCONTEXT); /* Check that the magic cookie is there. */
351 i >>= SAVE_TIGHT_SHIFT; /* Parentheses elements to pop. */
352 rex->lastcloseparen = SSPOPINT;
353 rex->lastparen = SSPOPINT;
354 *maxopenparen_p = SSPOPINT;
356 i -= REGCP_OTHER_ELEMS;
357 /* Now restore the parentheses context. */
359 if (i || rex->lastparen + 1 <= rex->nparens)
360 PerlIO_printf(Perl_debug_log,
361 "rex=0x%"UVxf" offs=0x%"UVxf": restoring capture indices to:\n",
366 paren = *maxopenparen_p;
367 for ( ; i > 0; i -= REGCP_PAREN_ELEMS) {
369 rex->offs[paren].start_tmp = SSPOPINT;
370 rex->offs[paren].start = SSPOPINT;
372 if (paren <= rex->lastparen)
373 rex->offs[paren].end = tmps;
374 DEBUG_BUFFERS_r( PerlIO_printf(Perl_debug_log,
375 " \\%"UVuf": %"IVdf"(%"IVdf")..%"IVdf"%s\n",
377 (IV)rex->offs[paren].start,
378 (IV)rex->offs[paren].start_tmp,
379 (IV)rex->offs[paren].end,
380 (paren > rex->lastparen ? "(skipped)" : ""));
385 /* It would seem that the similar code in regtry()
386 * already takes care of this, and in fact it is in
387 * a better location to since this code can #if 0-ed out
388 * but the code in regtry() is needed or otherwise tests
389 * requiring null fields (pat.t#187 and split.t#{13,14}
390 * (as of patchlevel 7877) will fail. Then again,
391 * this code seems to be necessary or otherwise
392 * this erroneously leaves $1 defined: "1" =~ /^(?:(\d)x)?\d$/
393 * --jhi updated by dapm */
394 for (i = rex->lastparen + 1; i <= rex->nparens; i++) {
395 if (i > *maxopenparen_p)
396 rex->offs[i].start = -1;
397 rex->offs[i].end = -1;
398 DEBUG_BUFFERS_r( PerlIO_printf(Perl_debug_log,
399 " \\%"UVuf": %s ..-1 undeffing\n",
401 (i > *maxopenparen_p) ? "-1" : " "
407 /* restore the parens and associated vars at savestack position ix,
408 * but without popping the stack */
411 S_regcp_restore(pTHX_ regexp *rex, I32 ix, U32 *maxopenparen_p)
413 I32 tmpix = PL_savestack_ix;
414 PL_savestack_ix = ix;
415 regcppop(rex, maxopenparen_p);
416 PL_savestack_ix = tmpix;
419 #define regcpblow(cp) LEAVE_SCOPE(cp) /* Ignores regcppush()ed data. */
422 S_isFOO_lc(pTHX_ const U8 classnum, const U8 character)
424 /* Returns a boolean as to whether or not 'character' is a member of the
425 * Posix character class given by 'classnum' that should be equivalent to a
426 * value in the typedef '_char_class_number'.
428 * Ideally this could be replaced by a just an array of function pointers
429 * to the C library functions that implement the macros this calls.
430 * However, to compile, the precise function signatures are required, and
431 * these may vary from platform to to platform. To avoid having to figure
432 * out what those all are on each platform, I (khw) am using this method,
433 * which adds an extra layer of function call overhead (unless the C
434 * optimizer strips it away). But we don't particularly care about
435 * performance with locales anyway. */
437 switch ((_char_class_number) classnum) {
438 case _CC_ENUM_ALPHANUMERIC: return isALPHANUMERIC_LC(character);
439 case _CC_ENUM_ALPHA: return isALPHA_LC(character);
440 case _CC_ENUM_ASCII: return isASCII_LC(character);
441 case _CC_ENUM_BLANK: return isBLANK_LC(character);
442 case _CC_ENUM_CASED: return isLOWER_LC(character)
443 || isUPPER_LC(character);
444 case _CC_ENUM_CNTRL: return isCNTRL_LC(character);
445 case _CC_ENUM_DIGIT: return isDIGIT_LC(character);
446 case _CC_ENUM_GRAPH: return isGRAPH_LC(character);
447 case _CC_ENUM_LOWER: return isLOWER_LC(character);
448 case _CC_ENUM_PRINT: return isPRINT_LC(character);
449 case _CC_ENUM_PSXSPC: return isPSXSPC_LC(character);
450 case _CC_ENUM_PUNCT: return isPUNCT_LC(character);
451 case _CC_ENUM_SPACE: return isSPACE_LC(character);
452 case _CC_ENUM_UPPER: return isUPPER_LC(character);
453 case _CC_ENUM_WORDCHAR: return isWORDCHAR_LC(character);
454 case _CC_ENUM_XDIGIT: return isXDIGIT_LC(character);
455 default: /* VERTSPACE should never occur in locales */
456 Perl_croak(aTHX_ "panic: isFOO_lc() has an unexpected character class '%d'", classnum);
459 assert(0); /* NOTREACHED */
464 S_isFOO_utf8_lc(pTHX_ const U8 classnum, const U8* character)
466 /* Returns a boolean as to whether or not the (well-formed) UTF-8-encoded
467 * 'character' is a member of the Posix character class given by 'classnum'
468 * that should be equivalent to a value in the typedef
469 * '_char_class_number'.
471 * This just calls isFOO_lc on the code point for the character if it is in
472 * the range 0-255. Outside that range, all characters avoid Unicode
473 * rules, ignoring any locale. So use the Unicode function if this class
474 * requires a swash, and use the Unicode macro otherwise. */
476 PERL_ARGS_ASSERT_ISFOO_UTF8_LC;
478 if (UTF8_IS_INVARIANT(*character)) {
479 return isFOO_lc(classnum, *character);
481 else if (UTF8_IS_DOWNGRADEABLE_START(*character)) {
482 return isFOO_lc(classnum,
483 TWO_BYTE_UTF8_TO_UNI(*character, *(character + 1)));
486 if (classnum < _FIRST_NON_SWASH_CC) {
488 /* Initialize the swash unless done already */
489 if (! PL_utf8_swash_ptrs[classnum]) {
490 U8 flags = _CORE_SWASH_INIT_ACCEPT_INVLIST;
491 PL_utf8_swash_ptrs[classnum] = _core_swash_init("utf8",
492 swash_property_names[classnum], &PL_sv_undef, 1, 0, NULL, &flags);
495 return cBOOL(swash_fetch(PL_utf8_swash_ptrs[classnum], (U8 *)
497 TRUE /* is UTF */ ));
500 switch ((_char_class_number) classnum) {
502 case _CC_ENUM_PSXSPC: return is_XPERLSPACE_high(character);
504 case _CC_ENUM_BLANK: return is_HORIZWS_high(character);
505 case _CC_ENUM_XDIGIT: return is_XDIGIT_high(character);
506 case _CC_ENUM_VERTSPACE: return is_VERTWS_high(character);
507 default: return 0; /* Things like CNTRL are always
511 assert(0); /* NOTREACHED */
516 * pregexec and friends
519 #ifndef PERL_IN_XSUB_RE
521 - pregexec - match a regexp against a string
524 Perl_pregexec(pTHX_ REGEXP * const prog, char* stringarg, char *strend,
525 char *strbeg, I32 minend, SV *screamer, U32 nosave)
526 /* stringarg: the point in the string at which to begin matching */
527 /* strend: pointer to null at end of string */
528 /* strbeg: real beginning of string */
529 /* minend: end of match must be >= minend bytes after stringarg. */
530 /* screamer: SV being matched: only used for utf8 flag, pos() etc; string
531 * itself is accessed via the pointers above */
532 /* nosave: For optimizations. */
534 PERL_ARGS_ASSERT_PREGEXEC;
537 regexec_flags(prog, stringarg, strend, strbeg, minend, screamer, NULL,
538 nosave ? 0 : REXEC_COPY_STR);
543 * Need to implement the following flags for reg_anch:
545 * USE_INTUIT_NOML - Useful to call re_intuit_start() first
547 * INTUIT_AUTORITATIVE_NOML - Can trust a positive answer
548 * INTUIT_AUTORITATIVE_ML
549 * INTUIT_ONCE_NOML - Intuit can match in one location only.
552 * Another flag for this function: SECOND_TIME (so that float substrs
553 * with giant delta may be not rechecked).
556 /* Assumptions: if ANCH_GPOS, then strpos is anchored. XXXX Check GPOS logic */
558 /* If SCREAM, then SvPVX_const(sv) should be compatible with strpos and strend.
559 Otherwise, only SvCUR(sv) is used to get strbeg. */
561 /* XXXX We assume that strpos is strbeg unless sv. */
563 /* XXXX Some places assume that there is a fixed substring.
564 An update may be needed if optimizer marks as "INTUITable"
565 RExen without fixed substrings. Similarly, it is assumed that
566 lengths of all the strings are no more than minlen, thus they
567 cannot come from lookahead.
568 (Or minlen should take into account lookahead.)
569 NOTE: Some of this comment is not correct. minlen does now take account
570 of lookahead/behind. Further research is required. -- demerphq
574 /* A failure to find a constant substring means that there is no need to make
575 an expensive call to REx engine, thus we celebrate a failure. Similarly,
576 finding a substring too deep into the string means that fewer calls to
577 regtry() should be needed.
579 REx compiler's optimizer found 4 possible hints:
580 a) Anchored substring;
582 c) Whether we are anchored (beginning-of-line or \G);
583 d) First node (of those at offset 0) which may distinguish positions;
584 We use a)b)d) and multiline-part of c), and try to find a position in the
585 string which does not contradict any of them.
588 /* Most of decisions we do here should have been done at compile time.
589 The nodes of the REx which we used for the search should have been
590 deleted from the finite automaton. */
593 Perl_re_intuit_start(pTHX_ REGEXP * const rx, SV *sv, char *strpos,
594 char *strend, const U32 flags, re_scream_pos_data *data)
597 struct regexp *const prog = ReANY(rx);
599 /* Should be nonnegative! */
605 const bool utf8_target = (sv && SvUTF8(sv)) ? 1 : 0; /* if no sv we have to assume bytes */
607 char *other_last = NULL; /* other substr checked before this */
608 char *check_at = NULL; /* check substr found at this pos */
609 char *checked_upto = NULL; /* how far into the string we have already checked using find_byclass*/
610 const I32 multiline = prog->extflags & RXf_PMf_MULTILINE;
611 RXi_GET_DECL(prog,progi);
614 const char * const i_strpos = strpos;
616 GET_RE_DEBUG_FLAGS_DECL;
618 PERL_ARGS_ASSERT_RE_INTUIT_START;
619 PERL_UNUSED_ARG(flags);
620 PERL_UNUSED_ARG(data);
622 RX_MATCH_UTF8_set(rx,utf8_target);
624 is_utf8_pat = cBOOL(RX_UTF8(rx));
627 debug_start_match(rx, utf8_target, strpos, strend,
628 sv ? "Guessing start of match in sv for"
629 : "Guessing start of match in string for");
632 /* CHR_DIST() would be more correct here but it makes things slow. */
633 if (prog->minlen > strend - strpos) {
634 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
635 "String too short... [re_intuit_start]\n"));
639 /* XXX we need to pass strbeg as a separate arg: the following is
640 * guesswork and can be wrong... */
641 if (sv && SvPOK(sv)) {
642 char * p = SvPVX(sv);
643 STRLEN cur = SvCUR(sv);
644 if (p <= strpos && strpos < p + cur) {
646 assert(p <= strend && strend <= p + cur);
649 strbeg = strend - cur;
656 if (!prog->check_utf8 && prog->check_substr)
657 to_utf8_substr(prog);
658 check = prog->check_utf8;
660 if (!prog->check_substr && prog->check_utf8) {
661 if (! to_byte_substr(prog)) {
662 NON_UTF8_TARGET_BUT_UTF8_REQUIRED(fail);
665 check = prog->check_substr;
667 if (prog->extflags & RXf_ANCH) { /* Match at beg-of-str or after \n */
668 ml_anch = !( (prog->extflags & RXf_ANCH_SINGLE)
669 || ( (prog->extflags & RXf_ANCH_BOL)
670 && !multiline ) ); /* Check after \n? */
673 if ( !(prog->extflags & RXf_ANCH_GPOS) /* Checked by the caller */
674 && !(prog->intflags & PREGf_IMPLICIT) /* not a real BOL */
675 /* SvCUR is not set on references: SvRV and SvPVX_const overlap */
677 && (strpos != strbeg)) {
678 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "Not at start...\n"));
681 if (prog->check_offset_min == prog->check_offset_max
682 && !(prog->extflags & RXf_CANY_SEEN)
683 && ! multiline) /* /m can cause \n's to match that aren't
684 accounted for in the string max length.
685 See [perl #115242] */
687 /* Substring at constant offset from beg-of-str... */
690 s = HOP3c(strpos, prog->check_offset_min, strend);
693 slen = SvCUR(check); /* >= 1 */
695 if ( strend - s > slen || strend - s < slen - 1
696 || (strend - s == slen && strend[-1] != '\n')) {
697 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "String too long...\n"));
700 /* Now should match s[0..slen-2] */
702 if (slen && (*SvPVX_const(check) != *s
704 && memNE(SvPVX_const(check), s, slen)))) {
706 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "String not equal...\n"));
710 else if (*SvPVX_const(check) != *s
711 || ((slen = SvCUR(check)) > 1
712 && memNE(SvPVX_const(check), s, slen)))
715 goto success_at_start;
718 /* Match is anchored, but substr is not anchored wrt beg-of-str. */
720 start_shift = prog->check_offset_min; /* okay to underestimate on CC */
721 end_shift = prog->check_end_shift;
724 const I32 end = prog->check_offset_max + CHR_SVLEN(check)
725 - (SvTAIL(check) != 0);
726 const I32 eshift = CHR_DIST((U8*)strend, (U8*)s) - end;
728 if (end_shift < eshift)
732 else { /* Can match at random position */
735 start_shift = prog->check_offset_min; /* okay to underestimate on CC */
736 end_shift = prog->check_end_shift;
738 /* end shift should be non negative here */
741 #ifdef QDEBUGGING /* 7/99: reports of failure (with the older version) */
743 Perl_croak(aTHX_ "panic: end_shift: %"IVdf" pattern:\n%s\n ",
744 (IV)end_shift, RX_PRECOMP(prog));
748 /* Find a possible match in the region s..strend by looking for
749 the "check" substring in the region corrected by start/end_shift. */
752 I32 srch_start_shift = start_shift;
753 I32 srch_end_shift = end_shift;
756 if (srch_start_shift < 0 && strbeg - s > srch_start_shift) {
757 srch_end_shift -= ((strbeg - s) - srch_start_shift);
758 srch_start_shift = strbeg - s;
760 DEBUG_OPTIMISE_MORE_r({
761 PerlIO_printf(Perl_debug_log, "Check offset min: %"IVdf" Start shift: %"IVdf" End shift %"IVdf" Real End Shift: %"IVdf"\n",
762 (IV)prog->check_offset_min,
763 (IV)srch_start_shift,
765 (IV)prog->check_end_shift);
768 if (prog->extflags & RXf_CANY_SEEN) {
769 start_point= (U8*)(s + srch_start_shift);
770 end_point= (U8*)(strend - srch_end_shift);
772 start_point= HOP3(s, srch_start_shift, srch_start_shift < 0 ? strbeg : strend);
773 end_point= HOP3(strend, -srch_end_shift, strbeg);
775 DEBUG_OPTIMISE_MORE_r({
776 PerlIO_printf(Perl_debug_log, "fbm_instr len=%d str=<%.*s>\n",
777 (int)(end_point - start_point),
778 (int)(end_point - start_point) > 20 ? 20 : (int)(end_point - start_point),
782 s = fbm_instr( start_point, end_point,
783 check, multiline ? FBMrf_MULTILINE : 0);
785 /* Update the count-of-usability, remove useless subpatterns,
789 RE_PV_QUOTED_DECL(quoted, utf8_target, PERL_DEBUG_PAD_ZERO(0),
790 SvPVX_const(check), RE_SV_DUMPLEN(check), 30);
791 PerlIO_printf(Perl_debug_log, "%s %s substr %s%s%s",
792 (s ? "Found" : "Did not find"),
793 (check == (utf8_target ? prog->anchored_utf8 : prog->anchored_substr)
794 ? "anchored" : "floating"),
797 (s ? " at offset " : "...\n") );
802 /* Finish the diagnostic message */
803 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "%ld...\n", (long)(s - i_strpos)) );
805 /* XXX dmq: first branch is for positive lookbehind...
806 Our check string is offset from the beginning of the pattern.
807 So we need to do any stclass tests offset forward from that
816 /* Got a candidate. Check MBOL anchoring, and the *other* substr.
817 Start with the other substr.
818 XXXX no SCREAM optimization yet - and a very coarse implementation
819 XXXX /ttx+/ results in anchored="ttx", floating="x". floating will
820 *always* match. Probably should be marked during compile...
821 Probably it is right to do no SCREAM here...
824 if (utf8_target ? (prog->float_utf8 && prog->anchored_utf8)
825 : (prog->float_substr && prog->anchored_substr))
827 /* Take into account the "other" substring. */
828 /* XXXX May be hopelessly wrong for UTF... */
831 if (check == (utf8_target ? prog->float_utf8 : prog->float_substr)) {
834 char * const last = HOP3c(s, -start_shift, strbeg);
836 char * const saved_s = s;
839 t = s - prog->check_offset_max;
840 if (s - strpos > prog->check_offset_max /* signed-corrected t > strpos */
842 || ((t = (char*)reghopmaybe3((U8*)s, -(prog->check_offset_max), (U8*)strpos))
847 t = HOP3c(t, prog->anchored_offset, strend);
848 if (t < other_last) /* These positions already checked */
850 last2 = last1 = HOP3c(strend, -prog->minlen, strbeg);
853 /* XXXX It is not documented what units *_offsets are in.
854 We assume bytes, but this is clearly wrong.
855 Meaning this code needs to be carefully reviewed for errors.
859 /* On end-of-str: see comment below. */
860 must = utf8_target ? prog->anchored_utf8 : prog->anchored_substr;
861 if (must == &PL_sv_undef) {
863 DEBUG_r(must = prog->anchored_utf8); /* for debug */
868 HOP3(HOP3(last1, prog->anchored_offset, strend)
869 + SvCUR(must), -(SvTAIL(must)!=0), strbeg),
871 multiline ? FBMrf_MULTILINE : 0
874 RE_PV_QUOTED_DECL(quoted, utf8_target, PERL_DEBUG_PAD_ZERO(0),
875 SvPVX_const(must), RE_SV_DUMPLEN(must), 30);
876 PerlIO_printf(Perl_debug_log, "%s anchored substr %s%s",
877 (s ? "Found" : "Contradicts"),
878 quoted, RE_SV_TAIL(must));
883 if (last1 >= last2) {
884 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
885 ", giving up...\n"));
888 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
889 ", trying floating at offset %ld...\n",
890 (long)(HOP3c(saved_s, 1, strend) - i_strpos)));
891 other_last = HOP3c(last1, prog->anchored_offset+1, strend);
892 s = HOP3c(last, 1, strend);
896 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, " at offset %ld...\n",
897 (long)(s - i_strpos)));
898 t = HOP3c(s, -prog->anchored_offset, strbeg);
899 other_last = HOP3c(s, 1, strend);
907 else { /* Take into account the floating substring. */
909 char * const saved_s = s;
912 t = HOP3c(s, -start_shift, strbeg);
914 HOP3c(strend, -prog->minlen + prog->float_min_offset, strbeg);
915 if (CHR_DIST((U8*)last, (U8*)t) > prog->float_max_offset)
916 last = HOP3c(t, prog->float_max_offset, strend);
917 s = HOP3c(t, prog->float_min_offset, strend);
920 /* XXXX It is not documented what units *_offsets are in. Assume bytes. */
921 must = utf8_target ? prog->float_utf8 : prog->float_substr;
922 /* fbm_instr() takes into account exact value of end-of-str
923 if the check is SvTAIL(ed). Since false positives are OK,
924 and end-of-str is not later than strend we are OK. */
925 if (must == &PL_sv_undef) {
927 DEBUG_r(must = prog->float_utf8); /* for debug message */
930 s = fbm_instr((unsigned char*)s,
931 (unsigned char*)last + SvCUR(must)
933 must, multiline ? FBMrf_MULTILINE : 0);
935 RE_PV_QUOTED_DECL(quoted, utf8_target, PERL_DEBUG_PAD_ZERO(0),
936 SvPVX_const(must), RE_SV_DUMPLEN(must), 30);
937 PerlIO_printf(Perl_debug_log, "%s floating substr %s%s",
938 (s ? "Found" : "Contradicts"),
939 quoted, RE_SV_TAIL(must));
943 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
944 ", giving up...\n"));
947 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
948 ", trying anchored starting at offset %ld...\n",
949 (long)(saved_s + 1 - i_strpos)));
951 s = HOP3c(t, 1, strend);
955 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, " at offset %ld...\n",
956 (long)(s - i_strpos)));
957 other_last = s; /* Fix this later. --Hugo */
967 t= (char*)HOP3( s, -prog->check_offset_max, (prog->check_offset_max<0) ? strend : strpos);
969 DEBUG_OPTIMISE_MORE_r(
970 PerlIO_printf(Perl_debug_log,
971 "Check offset min:%"IVdf" max:%"IVdf" S:%"IVdf" t:%"IVdf" D:%"IVdf" end:%"IVdf"\n",
972 (IV)prog->check_offset_min,
973 (IV)prog->check_offset_max,
981 if (s - strpos > prog->check_offset_max /* signed-corrected t > strpos */
983 || ((t = (char*)reghopmaybe3((U8*)s, -prog->check_offset_max, (U8*) ((prog->check_offset_max<0) ? strend : strpos)))
986 /* Fixed substring is found far enough so that the match
987 cannot start at strpos. */
989 if (ml_anch && t[-1] != '\n') {
990 /* Eventually fbm_*() should handle this, but often
991 anchored_offset is not 0, so this check will not be wasted. */
992 /* XXXX In the code below we prefer to look for "^" even in
993 presence of anchored substrings. And we search even
994 beyond the found float position. These pessimizations
995 are historical artefacts only. */
997 while (t < strend - prog->minlen) {
999 if (t < check_at - prog->check_offset_min) {
1000 if (utf8_target ? prog->anchored_utf8 : prog->anchored_substr) {
1001 /* Since we moved from the found position,
1002 we definitely contradict the found anchored
1003 substr. Due to the above check we do not
1004 contradict "check" substr.
1005 Thus we can arrive here only if check substr
1006 is float. Redo checking for "other"=="fixed".
1009 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "Found /%s^%s/m at offset %ld, rescanning for anchored from offset %ld...\n",
1010 PL_colors[0], PL_colors[1], (long)(strpos - i_strpos), (long)(strpos - i_strpos + prog->anchored_offset)));
1011 goto do_other_anchored;
1013 /* We don't contradict the found floating substring. */
1014 /* XXXX Why not check for STCLASS? */
1016 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "Found /%s^%s/m at offset %ld...\n",
1017 PL_colors[0], PL_colors[1], (long)(s - i_strpos)));
1020 /* Position contradicts check-string */
1021 /* XXXX probably better to look for check-string
1022 than for "\n", so one should lower the limit for t? */
1023 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "Found /%s^%s/m, restarting lookup for check-string at offset %ld...\n",
1024 PL_colors[0], PL_colors[1], (long)(t + 1 - i_strpos)));
1025 other_last = strpos = s = t + 1;
1030 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "Did not find /%s^%s/m...\n",
1031 PL_colors[0], PL_colors[1]));
1035 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "Starting position does not contradict /%s^%s/m...\n",
1036 PL_colors[0], PL_colors[1]));
1040 ++BmUSEFUL(utf8_target ? prog->check_utf8 : prog->check_substr); /* hooray/5 */
1043 /* The found string does not prohibit matching at strpos,
1044 - no optimization of calling REx engine can be performed,
1045 unless it was an MBOL and we are not after MBOL,
1046 or a future STCLASS check will fail this. */
1048 /* Even in this situation we may use MBOL flag if strpos is offset
1049 wrt the start of the string. */
1050 if (ml_anch && sv && !SvROK(sv) /* See prev comment on SvROK */
1051 && (strpos != strbeg) && strpos[-1] != '\n'
1052 /* May be due to an implicit anchor of m{.*foo} */
1053 && !(prog->intflags & PREGf_IMPLICIT))
1058 DEBUG_EXECUTE_r( if (ml_anch)
1059 PerlIO_printf(Perl_debug_log, "Position at offset %ld does not contradict /%s^%s/m...\n",
1060 (long)(strpos - i_strpos), PL_colors[0], PL_colors[1]);
1063 if (!(prog->intflags & PREGf_NAUGHTY) /* XXXX If strpos moved? */
1065 prog->check_utf8 /* Could be deleted already */
1066 && --BmUSEFUL(prog->check_utf8) < 0
1067 && (prog->check_utf8 == prog->float_utf8)
1069 prog->check_substr /* Could be deleted already */
1070 && --BmUSEFUL(prog->check_substr) < 0
1071 && (prog->check_substr == prog->float_substr)
1074 /* If flags & SOMETHING - do not do it many times on the same match */
1075 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "... Disabling check substring...\n"));
1076 /* XXX Does the destruction order has to change with utf8_target? */
1077 SvREFCNT_dec(utf8_target ? prog->check_utf8 : prog->check_substr);
1078 SvREFCNT_dec(utf8_target ? prog->check_substr : prog->check_utf8);
1079 prog->check_substr = prog->check_utf8 = NULL; /* disable */
1080 prog->float_substr = prog->float_utf8 = NULL; /* clear */
1081 check = NULL; /* abort */
1083 /* XXXX If the check string was an implicit check MBOL, then we need to unset the relevant flag
1084 see http://bugs.activestate.com/show_bug.cgi?id=87173 */
1085 if (prog->intflags & PREGf_IMPLICIT)
1086 prog->extflags &= ~RXf_ANCH_MBOL;
1087 /* XXXX This is a remnant of the old implementation. It
1088 looks wasteful, since now INTUIT can use many
1089 other heuristics. */
1090 prog->extflags &= ~RXf_USE_INTUIT;
1091 /* XXXX What other flags might need to be cleared in this branch? */
1097 /* Last resort... */
1098 /* XXXX BmUSEFUL already changed, maybe multiple change is meaningful... */
1099 /* trie stclasses are too expensive to use here, we are better off to
1100 leave it to regmatch itself */
1101 if (progi->regstclass && PL_regkind[OP(progi->regstclass)]!=TRIE) {
1102 /* minlen == 0 is possible if regstclass is \b or \B,
1103 and the fixed substr is ''$.
1104 Since minlen is already taken into account, s+1 is before strend;
1105 accidentally, minlen >= 1 guaranties no false positives at s + 1
1106 even for \b or \B. But (minlen? 1 : 0) below assumes that
1107 regstclass does not come from lookahead... */
1108 /* If regstclass takes bytelength more than 1: If charlength==1, OK.
1109 This leaves EXACTF-ish only, which are dealt with in find_byclass(). */
1110 const U8* const str = (U8*)STRING(progi->regstclass);
1111 const int cl_l = (PL_regkind[OP(progi->regstclass)] == EXACT
1112 ? CHR_DIST(str+STR_LEN(progi->regstclass), str)
1115 if (prog->anchored_substr || prog->anchored_utf8 || ml_anch)
1116 endpos= HOP3c(s, (prog->minlen ? cl_l : 0), strend);
1117 else if (prog->float_substr || prog->float_utf8)
1118 endpos= HOP3c(HOP3c(check_at, -start_shift, strbeg), cl_l, strend);
1122 if (checked_upto < s)
1124 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "start_shift: %"IVdf" check_at: %"IVdf" s: %"IVdf" endpos: %"IVdf" checked_upto: %"IVdf"\n",
1125 (IV)start_shift, (IV)(check_at - strbeg), (IV)(s - strbeg), (IV)(endpos - strbeg), (IV)(checked_upto- strbeg)));
1128 s = find_byclass(prog, progi->regstclass, checked_upto, endpos,
1134 const char *what = NULL;
1136 if (endpos == strend) {
1137 DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log,
1138 "Could not match STCLASS...\n") );
1141 DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log,
1142 "This position contradicts STCLASS...\n") );
1143 if ((prog->extflags & RXf_ANCH) && !ml_anch)
1145 checked_upto = HOPBACKc(endpos, start_shift);
1146 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "start_shift: %"IVdf" check_at: %"IVdf" endpos: %"IVdf" checked_upto: %"IVdf"\n",
1147 (IV)start_shift, (IV)(check_at - strbeg), (IV)(endpos - strbeg), (IV)(checked_upto- strbeg)));
1148 /* Contradict one of substrings */
1149 if (prog->anchored_substr || prog->anchored_utf8) {
1150 if ((utf8_target ? prog->anchored_utf8 : prog->anchored_substr) == check) {
1151 DEBUG_EXECUTE_r( what = "anchored" );
1153 s = HOP3c(t, 1, strend);
1154 if (s + start_shift + end_shift > strend) {
1155 /* XXXX Should be taken into account earlier? */
1156 DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log,
1157 "Could not match STCLASS...\n") );
1162 DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log,
1163 "Looking for %s substr starting at offset %ld...\n",
1164 what, (long)(s + start_shift - i_strpos)) );
1167 /* Have both, check_string is floating */
1168 if (t + start_shift >= check_at) /* Contradicts floating=check */
1169 goto retry_floating_check;
1170 /* Recheck anchored substring, but not floating... */
1174 DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log,
1175 "Looking for anchored substr starting at offset %ld...\n",
1176 (long)(other_last - i_strpos)) );
1177 goto do_other_anchored;
1179 /* Another way we could have checked stclass at the
1180 current position only: */
1185 DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log,
1186 "Looking for /%s^%s/m starting at offset %ld...\n",
1187 PL_colors[0], PL_colors[1], (long)(t - i_strpos)) );
1190 if (!(utf8_target ? prog->float_utf8 : prog->float_substr)) /* Could have been deleted */
1192 /* Check is floating substring. */
1193 retry_floating_check:
1194 t = check_at - start_shift;
1195 DEBUG_EXECUTE_r( what = "floating" );
1196 goto hop_and_restart;
1199 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
1200 "By STCLASS: moving %ld --> %ld\n",
1201 (long)(t - i_strpos), (long)(s - i_strpos))
1205 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
1206 "Does not contradict STCLASS...\n");
1211 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "%s%s:%s match at offset %ld\n",
1212 PL_colors[4], (check ? "Guessed" : "Giving up"),
1213 PL_colors[5], (long)(s - i_strpos)) );
1216 fail_finish: /* Substring not found */
1217 if (prog->check_substr || prog->check_utf8) /* could be removed already */
1218 BmUSEFUL(utf8_target ? prog->check_utf8 : prog->check_substr) += 5; /* hooray */
1220 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "%sMatch rejected by optimizer%s\n",
1221 PL_colors[4], PL_colors[5]));
1225 #define DECL_TRIE_TYPE(scan) \
1226 const enum { trie_plain, trie_utf8, trie_utf8_fold, trie_latin_utf8_fold } \
1227 trie_type = ((scan->flags == EXACT) \
1228 ? (utf8_target ? trie_utf8 : trie_plain) \
1229 : (utf8_target ? trie_utf8_fold : trie_latin_utf8_fold))
1231 #define REXEC_TRIE_READ_CHAR(trie_type, trie, widecharmap, uc, uscan, len, \
1232 uvc, charid, foldlen, foldbuf, uniflags) STMT_START { \
1234 switch (trie_type) { \
1235 case trie_utf8_fold: \
1236 if ( foldlen>0 ) { \
1237 uvc = utf8n_to_uvuni( (const U8*) uscan, UTF8_MAXLEN, &len, uniflags ); \
1242 uvc = to_utf8_fold( (const U8*) uc, foldbuf, &foldlen ); \
1243 len = UTF8SKIP(uc); \
1244 skiplen = UNISKIP( uvc ); \
1245 foldlen -= skiplen; \
1246 uscan = foldbuf + skiplen; \
1249 case trie_latin_utf8_fold: \
1250 if ( foldlen>0 ) { \
1251 uvc = utf8n_to_uvuni( (const U8*) uscan, UTF8_MAXLEN, &len, uniflags ); \
1257 uvc = _to_fold_latin1( (U8) *uc, foldbuf, &foldlen, 1); \
1258 skiplen = UNISKIP( uvc ); \
1259 foldlen -= skiplen; \
1260 uscan = foldbuf + skiplen; \
1264 uvc = utf8n_to_uvuni( (const U8*) uc, UTF8_MAXLEN, &len, uniflags ); \
1271 charid = trie->charmap[ uvc ]; \
1275 if (widecharmap) { \
1276 SV** const svpp = hv_fetch(widecharmap, \
1277 (char*)&uvc, sizeof(UV), 0); \
1279 charid = (U16)SvIV(*svpp); \
1284 #define REXEC_FBC_EXACTISH_SCAN(CoNd) \
1288 && (ln == 1 || folder(s, pat_string, ln)) \
1289 && (!reginfo || regtry(reginfo, &s)) ) \
1295 #define REXEC_FBC_UTF8_SCAN(CoDe) \
1297 while (s < strend) { \
1303 #define REXEC_FBC_SCAN(CoDe) \
1305 while (s < strend) { \
1311 #define REXEC_FBC_UTF8_CLASS_SCAN(CoNd) \
1312 REXEC_FBC_UTF8_SCAN( \
1314 if (tmp && (!reginfo || regtry(reginfo, &s))) \
1323 #define REXEC_FBC_CLASS_SCAN(CoNd) \
1326 if (tmp && (!reginfo || regtry(reginfo, &s))) \
1335 #define REXEC_FBC_TRYIT \
1336 if ((!reginfo || regtry(reginfo, &s))) \
1339 #define REXEC_FBC_CSCAN(CoNdUtF8,CoNd) \
1340 if (utf8_target) { \
1341 REXEC_FBC_UTF8_CLASS_SCAN(CoNdUtF8); \
1344 REXEC_FBC_CLASS_SCAN(CoNd); \
1347 #define DUMP_EXEC_POS(li,s,doutf8) \
1348 dump_exec_pos(li,s,(PL_regeol),(PL_bostr),(PL_reg_starttry),doutf8)
1351 #define UTF8_NOLOAD(TEST_NON_UTF8, IF_SUCCESS, IF_FAIL) \
1352 tmp = (s != PL_bostr) ? UCHARAT(s - 1) : '\n'; \
1353 tmp = TEST_NON_UTF8(tmp); \
1354 REXEC_FBC_UTF8_SCAN( \
1355 if (tmp == ! TEST_NON_UTF8((U8) *s)) { \
1364 #define UTF8_LOAD(TeSt1_UtF8, TeSt2_UtF8, IF_SUCCESS, IF_FAIL) \
1365 if (s == PL_bostr) { \
1369 U8 * const r = reghop3((U8*)s, -1, (U8*)PL_bostr); \
1370 tmp = utf8n_to_uvchr(r, UTF8SKIP(r), 0, UTF8_ALLOW_DEFAULT); \
1373 LOAD_UTF8_CHARCLASS_ALNUM(); \
1374 REXEC_FBC_UTF8_SCAN( \
1375 if (tmp == ! (TeSt2_UtF8)) { \
1384 /* The only difference between the BOUND and NBOUND cases is that
1385 * REXEC_FBC_TRYIT is called when matched in BOUND, and when non-matched in
1386 * NBOUND. This is accomplished by passing it in either the if or else clause,
1387 * with the other one being empty */
1388 #define FBC_BOUND(TEST_NON_UTF8, TEST1_UTF8, TEST2_UTF8) \
1389 FBC_BOUND_COMMON(UTF8_LOAD(TEST1_UTF8, TEST2_UTF8, REXEC_FBC_TRYIT, PLACEHOLDER), TEST_NON_UTF8, REXEC_FBC_TRYIT, PLACEHOLDER)
1391 #define FBC_BOUND_NOLOAD(TEST_NON_UTF8, TEST1_UTF8, TEST2_UTF8) \
1392 FBC_BOUND_COMMON(UTF8_NOLOAD(TEST_NON_UTF8, REXEC_FBC_TRYIT, PLACEHOLDER), TEST_NON_UTF8, REXEC_FBC_TRYIT, PLACEHOLDER)
1394 #define FBC_NBOUND(TEST_NON_UTF8, TEST1_UTF8, TEST2_UTF8) \
1395 FBC_BOUND_COMMON(UTF8_LOAD(TEST1_UTF8, TEST2_UTF8, PLACEHOLDER, REXEC_FBC_TRYIT), TEST_NON_UTF8, PLACEHOLDER, REXEC_FBC_TRYIT)
1397 #define FBC_NBOUND_NOLOAD(TEST_NON_UTF8, TEST1_UTF8, TEST2_UTF8) \
1398 FBC_BOUND_COMMON(UTF8_NOLOAD(TEST_NON_UTF8, PLACEHOLDER, REXEC_FBC_TRYIT), TEST_NON_UTF8, PLACEHOLDER, REXEC_FBC_TRYIT)
1401 /* Common to the BOUND and NBOUND cases. Unfortunately the UTF8 tests need to
1402 * be passed in completely with the variable name being tested, which isn't
1403 * such a clean interface, but this is easier to read than it was before. We
1404 * are looking for the boundary (or non-boundary between a word and non-word
1405 * character. The utf8 and non-utf8 cases have the same logic, but the details
1406 * must be different. Find the "wordness" of the character just prior to this
1407 * one, and compare it with the wordness of this one. If they differ, we have
1408 * a boundary. At the beginning of the string, pretend that the previous
1409 * character was a new-line */
1410 #define FBC_BOUND_COMMON(UTF8_CODE, TEST_NON_UTF8, IF_SUCCESS, IF_FAIL) \
1411 if (utf8_target) { \
1414 else { /* Not utf8 */ \
1415 tmp = (s != PL_bostr) ? UCHARAT(s - 1) : '\n'; \
1416 tmp = TEST_NON_UTF8(tmp); \
1418 if (tmp == ! TEST_NON_UTF8((U8) *s)) { \
1427 if ((!prog->minlen && tmp) && (!reginfo || regtry(reginfo, &s))) \
1430 /* We know what class REx starts with. Try to find this position... */
1431 /* if reginfo is NULL, its a dryrun */
1432 /* annoyingly all the vars in this routine have different names from their counterparts
1433 in regmatch. /grrr */
1436 S_find_byclass(pTHX_ regexp * prog, const regnode *c, char *s,
1437 const char *strend, regmatch_info *reginfo, bool is_utf8_pat)
1440 const I32 doevery = (prog->intflags & PREGf_SKIP) == 0;
1441 char *pat_string; /* The pattern's exactish string */
1442 char *pat_end; /* ptr to end char of pat_string */
1443 re_fold_t folder; /* Function for computing non-utf8 folds */
1444 const U8 *fold_array; /* array for folding ords < 256 */
1450 I32 tmp = 1; /* Scratch variable? */
1451 const bool utf8_target = PL_reg_match_utf8;
1452 UV utf8_fold_flags = 0;
1453 bool to_complement = FALSE; /* Invert the result? Taking the xor of this
1454 with a result inverts that result, as 0^1 =
1456 _char_class_number classnum;
1458 RXi_GET_DECL(prog,progi);
1460 PERL_ARGS_ASSERT_FIND_BYCLASS;
1462 /* We know what class it must start with. */
1465 case ANYOF_SYNTHETIC:
1466 case ANYOF_WARN_SUPER:
1468 REXEC_FBC_UTF8_CLASS_SCAN(
1469 reginclass(prog, c, (U8*)s, utf8_target));
1472 REXEC_FBC_CLASS_SCAN(REGINCLASS(prog, c, (U8*)s));
1477 if (tmp && (!reginfo || regtry(reginfo, &s)))
1485 if (is_utf8_pat || utf8_target) {
1486 utf8_fold_flags = FOLDEQ_UTF8_NOMIX_ASCII;
1487 goto do_exactf_utf8;
1489 fold_array = PL_fold_latin1; /* Latin1 folds are not affected by */
1490 folder = foldEQ_latin1; /* /a, except the sharp s one which */
1491 goto do_exactf_non_utf8; /* isn't dealt with by these */
1496 /* regcomp.c already folded this if pattern is in UTF-8 */
1497 utf8_fold_flags = 0;
1498 goto do_exactf_utf8;
1500 fold_array = PL_fold;
1502 goto do_exactf_non_utf8;
1505 if (is_utf8_pat || utf8_target) {
1506 utf8_fold_flags = FOLDEQ_UTF8_LOCALE;
1507 goto do_exactf_utf8;
1509 fold_array = PL_fold_locale;
1510 folder = foldEQ_locale;
1511 goto do_exactf_non_utf8;
1515 utf8_fold_flags = FOLDEQ_S2_ALREADY_FOLDED;
1517 goto do_exactf_utf8;
1519 case EXACTFU_TRICKYFOLD:
1521 if (is_utf8_pat || utf8_target) {
1522 utf8_fold_flags = is_utf8_pat ? FOLDEQ_S2_ALREADY_FOLDED : 0;
1523 goto do_exactf_utf8;
1526 /* Any 'ss' in the pattern should have been replaced by regcomp,
1527 * so we don't have to worry here about this single special case
1528 * in the Latin1 range */
1529 fold_array = PL_fold_latin1;
1530 folder = foldEQ_latin1;
1534 do_exactf_non_utf8: /* Neither pattern nor string are UTF8, and there
1535 are no glitches with fold-length differences
1536 between the target string and pattern */
1538 /* The idea in the non-utf8 EXACTF* cases is to first find the
1539 * first character of the EXACTF* node and then, if necessary,
1540 * case-insensitively compare the full text of the node. c1 is the
1541 * first character. c2 is its fold. This logic will not work for
1542 * Unicode semantics and the german sharp ss, which hence should
1543 * not be compiled into a node that gets here. */
1544 pat_string = STRING(c);
1545 ln = STR_LEN(c); /* length to match in octets/bytes */
1547 /* We know that we have to match at least 'ln' bytes (which is the
1548 * same as characters, since not utf8). If we have to match 3
1549 * characters, and there are only 2 availabe, we know without
1550 * trying that it will fail; so don't start a match past the
1551 * required minimum number from the far end */
1552 e = HOP3c(strend, -((I32)ln), s);
1554 if (!reginfo && e < s) {
1555 e = s; /* Due to minlen logic of intuit() */
1559 c2 = fold_array[c1];
1560 if (c1 == c2) { /* If char and fold are the same */
1561 REXEC_FBC_EXACTISH_SCAN(*(U8*)s == c1);
1564 REXEC_FBC_EXACTISH_SCAN(*(U8*)s == c1 || *(U8*)s == c2);
1572 /* If one of the operands is in utf8, we can't use the simpler folding
1573 * above, due to the fact that many different characters can have the
1574 * same fold, or portion of a fold, or different- length fold */
1575 pat_string = STRING(c);
1576 ln = STR_LEN(c); /* length to match in octets/bytes */
1577 pat_end = pat_string + ln;
1578 lnc = is_utf8_pat /* length to match in characters */
1579 ? utf8_length((U8 *) pat_string, (U8 *) pat_end)
1582 /* We have 'lnc' characters to match in the pattern, but because of
1583 * multi-character folding, each character in the target can match
1584 * up to 3 characters (Unicode guarantees it will never exceed
1585 * this) if it is utf8-encoded; and up to 2 if not (based on the
1586 * fact that the Latin 1 folds are already determined, and the
1587 * only multi-char fold in that range is the sharp-s folding to
1588 * 'ss'. Thus, a pattern character can match as little as 1/3 of a
1589 * string character. Adjust lnc accordingly, rounding up, so that
1590 * if we need to match at least 4+1/3 chars, that really is 5. */
1591 expansion = (utf8_target) ? UTF8_MAX_FOLD_CHAR_EXPAND : 2;
1592 lnc = (lnc + expansion - 1) / expansion;
1594 /* As in the non-UTF8 case, if we have to match 3 characters, and
1595 * only 2 are left, it's guaranteed to fail, so don't start a
1596 * match that would require us to go beyond the end of the string
1598 e = HOP3c(strend, -((I32)lnc), s);
1600 if (!reginfo && e < s) {
1601 e = s; /* Due to minlen logic of intuit() */
1604 /* XXX Note that we could recalculate e to stop the loop earlier,
1605 * as the worst case expansion above will rarely be met, and as we
1606 * go along we would usually find that e moves further to the left.
1607 * This would happen only after we reached the point in the loop
1608 * where if there were no expansion we should fail. Unclear if
1609 * worth the expense */
1612 char *my_strend= (char *)strend;
1613 if (foldEQ_utf8_flags(s, &my_strend, 0, utf8_target,
1614 pat_string, NULL, ln, is_utf8_pat, utf8_fold_flags)
1615 && (!reginfo || regtry(reginfo, &s)) )
1619 s += (utf8_target) ? UTF8SKIP(s) : 1;
1624 RXp_MATCH_TAINTED_on(prog);
1625 FBC_BOUND(isWORDCHAR_LC,
1626 isWORDCHAR_LC_uvchr(UNI_TO_NATIVE(tmp)),
1627 isWORDCHAR_LC_utf8((U8*)s));
1630 RXp_MATCH_TAINTED_on(prog);
1631 FBC_NBOUND(isWORDCHAR_LC,
1632 isWORDCHAR_LC_uvchr(UNI_TO_NATIVE(tmp)),
1633 isWORDCHAR_LC_utf8((U8*)s));
1636 FBC_BOUND(isWORDCHAR,
1637 isWORDCHAR_uni(tmp),
1638 cBOOL(swash_fetch(PL_utf8_swash_ptrs[_CC_WORDCHAR], (U8*)s, utf8_target)));
1641 FBC_BOUND_NOLOAD(isWORDCHAR_A,
1643 isWORDCHAR_A((U8*)s));
1646 FBC_NBOUND(isWORDCHAR,
1647 isWORDCHAR_uni(tmp),
1648 cBOOL(swash_fetch(PL_utf8_swash_ptrs[_CC_WORDCHAR], (U8*)s, utf8_target)));
1651 FBC_NBOUND_NOLOAD(isWORDCHAR_A,
1653 isWORDCHAR_A((U8*)s));
1656 FBC_BOUND(isWORDCHAR_L1,
1657 isWORDCHAR_uni(tmp),
1658 cBOOL(swash_fetch(PL_utf8_swash_ptrs[_CC_WORDCHAR], (U8*)s, utf8_target)));
1661 FBC_NBOUND(isWORDCHAR_L1,
1662 isWORDCHAR_uni(tmp),
1663 cBOOL(swash_fetch(PL_utf8_swash_ptrs[_CC_WORDCHAR], (U8*)s, utf8_target)));
1666 REXEC_FBC_CSCAN(is_LNBREAK_utf8_safe(s, strend),
1667 is_LNBREAK_latin1_safe(s, strend)
1671 /* The argument to all the POSIX node types is the class number to pass to
1672 * _generic_isCC() to build a mask for searching in PL_charclass[] */
1679 RXp_MATCH_TAINTED_on(prog);
1680 REXEC_FBC_CSCAN(to_complement ^ cBOOL(isFOO_utf8_lc(FLAGS(c), (U8 *) s)),
1681 to_complement ^ cBOOL(isFOO_lc(FLAGS(c), *s)));
1696 /* The complement of something that matches only ASCII matches all
1697 * UTF-8 variant code points, plus everything in ASCII that isn't
1699 REXEC_FBC_UTF8_CLASS_SCAN(! UTF8_IS_INVARIANT(*s)
1700 || ! _generic_isCC_A(*s, FLAGS(c)));
1709 /* Don't need to worry about utf8, as it can match only a single
1710 * byte invariant character. */
1711 REXEC_FBC_CLASS_SCAN(
1712 to_complement ^ cBOOL(_generic_isCC_A(*s, FLAGS(c))));
1720 if (! utf8_target) {
1721 REXEC_FBC_CLASS_SCAN(to_complement ^ cBOOL(_generic_isCC(*s,
1727 classnum = (_char_class_number) FLAGS(c);
1728 if (classnum < _FIRST_NON_SWASH_CC) {
1729 while (s < strend) {
1731 /* We avoid loading in the swash as long as possible, but
1732 * should we have to, we jump to a separate loop. This
1733 * extra 'if' statement is what keeps this code from being
1734 * just a call to REXEC_FBC_UTF8_CLASS_SCAN() */
1735 if (UTF8_IS_ABOVE_LATIN1(*s)) {
1736 goto found_above_latin1;
1738 if ((UTF8_IS_INVARIANT(*s)
1739 && to_complement ^ cBOOL(_generic_isCC((U8) *s,
1741 || (UTF8_IS_DOWNGRADEABLE_START(*s)
1742 && to_complement ^ cBOOL(
1743 _generic_isCC(TWO_BYTE_UTF8_TO_UNI(*s, *(s + 1)),
1746 if (tmp && (!reginfo || regtry(reginfo, &s)))
1758 else switch (classnum) { /* These classes are implemented as
1760 case _CC_ENUM_SPACE: /* XXX would require separate code if we
1761 revert the change of \v matching this */
1764 case _CC_ENUM_PSXSPC:
1765 REXEC_FBC_UTF8_CLASS_SCAN(
1766 to_complement ^ cBOOL(isSPACE_utf8(s)));
1769 case _CC_ENUM_BLANK:
1770 REXEC_FBC_UTF8_CLASS_SCAN(
1771 to_complement ^ cBOOL(isBLANK_utf8(s)));
1774 case _CC_ENUM_XDIGIT:
1775 REXEC_FBC_UTF8_CLASS_SCAN(
1776 to_complement ^ cBOOL(isXDIGIT_utf8(s)));
1779 case _CC_ENUM_VERTSPACE:
1780 REXEC_FBC_UTF8_CLASS_SCAN(
1781 to_complement ^ cBOOL(isVERTWS_utf8(s)));
1784 case _CC_ENUM_CNTRL:
1785 REXEC_FBC_UTF8_CLASS_SCAN(
1786 to_complement ^ cBOOL(isCNTRL_utf8(s)));
1790 Perl_croak(aTHX_ "panic: find_byclass() node %d='%s' has an unexpected character class '%d'", OP(c), PL_reg_name[OP(c)], classnum);
1791 assert(0); /* NOTREACHED */
1796 found_above_latin1: /* Here we have to load a swash to get the result
1797 for the current code point */
1798 if (! PL_utf8_swash_ptrs[classnum]) {
1799 U8 flags = _CORE_SWASH_INIT_ACCEPT_INVLIST;
1800 PL_utf8_swash_ptrs[classnum] =
1801 _core_swash_init("utf8", swash_property_names[classnum],
1802 &PL_sv_undef, 1, 0, NULL, &flags);
1805 /* This is a copy of the loop above for swash classes, though using the
1806 * FBC macro instead of being expanded out. Since we've loaded the
1807 * swash, we don't have to check for that each time through the loop */
1808 REXEC_FBC_UTF8_CLASS_SCAN(
1809 to_complement ^ cBOOL(_generic_utf8(
1812 swash_fetch(PL_utf8_swash_ptrs[classnum],
1820 /* what trie are we using right now */
1821 reg_ac_data *aho = (reg_ac_data*)progi->data->data[ ARG( c ) ];
1822 reg_trie_data *trie = (reg_trie_data*)progi->data->data[ aho->trie ];
1823 HV *widecharmap = MUTABLE_HV(progi->data->data[ aho->trie + 1 ]);
1825 const char *last_start = strend - trie->minlen;
1827 const char *real_start = s;
1829 STRLEN maxlen = trie->maxlen;
1831 U8 **points; /* map of where we were in the input string
1832 when reading a given char. For ASCII this
1833 is unnecessary overhead as the relationship
1834 is always 1:1, but for Unicode, especially
1835 case folded Unicode this is not true. */
1836 U8 foldbuf[ UTF8_MAXBYTES_CASE + 1 ];
1840 GET_RE_DEBUG_FLAGS_DECL;
1842 /* We can't just allocate points here. We need to wrap it in
1843 * an SV so it gets freed properly if there is a croak while
1844 * running the match */
1847 sv_points=newSV(maxlen * sizeof(U8 *));
1848 SvCUR_set(sv_points,
1849 maxlen * sizeof(U8 *));
1850 SvPOK_on(sv_points);
1851 sv_2mortal(sv_points);
1852 points=(U8**)SvPV_nolen(sv_points );
1853 if ( trie_type != trie_utf8_fold
1854 && (trie->bitmap || OP(c)==AHOCORASICKC) )
1857 bitmap=(U8*)trie->bitmap;
1859 bitmap=(U8*)ANYOF_BITMAP(c);
1861 /* this is the Aho-Corasick algorithm modified a touch
1862 to include special handling for long "unknown char" sequences.
1863 The basic idea being that we use AC as long as we are dealing
1864 with a possible matching char, when we encounter an unknown char
1865 (and we have not encountered an accepting state) we scan forward
1866 until we find a legal starting char.
1867 AC matching is basically that of trie matching, except that when
1868 we encounter a failing transition, we fall back to the current
1869 states "fail state", and try the current char again, a process
1870 we repeat until we reach the root state, state 1, or a legal
1871 transition. If we fail on the root state then we can either
1872 terminate if we have reached an accepting state previously, or
1873 restart the entire process from the beginning if we have not.
1876 while (s <= last_start) {
1877 const U32 uniflags = UTF8_ALLOW_DEFAULT;
1885 U8 *uscan = (U8*)NULL;
1886 U8 *leftmost = NULL;
1888 U32 accepted_word= 0;
1892 while ( state && uc <= (U8*)strend ) {
1894 U32 word = aho->states[ state ].wordnum;
1898 DEBUG_TRIE_EXECUTE_r(
1899 if ( uc <= (U8*)last_start && !BITMAP_TEST(bitmap,*uc) ) {
1900 dump_exec_pos( (char *)uc, c, strend, real_start,
1901 (char *)uc, utf8_target );
1902 PerlIO_printf( Perl_debug_log,
1903 " Scanning for legal start char...\n");
1907 while ( uc <= (U8*)last_start && !BITMAP_TEST(bitmap,*uc) ) {
1911 while ( uc <= (U8*)last_start && !BITMAP_TEST(bitmap,*uc) ) {
1917 if (uc >(U8*)last_start) break;
1921 U8 *lpos= points[ (pointpos - trie->wordinfo[word].len) % maxlen ];
1922 if (!leftmost || lpos < leftmost) {
1923 DEBUG_r(accepted_word=word);
1929 points[pointpos++ % maxlen]= uc;
1930 if (foldlen || uc < (U8*)strend) {
1931 REXEC_TRIE_READ_CHAR(trie_type, trie,
1933 uscan, len, uvc, charid, foldlen,
1935 DEBUG_TRIE_EXECUTE_r({
1936 dump_exec_pos( (char *)uc, c, strend,
1937 real_start, s, utf8_target);
1938 PerlIO_printf(Perl_debug_log,
1939 " Charid:%3u CP:%4"UVxf" ",
1951 word = aho->states[ state ].wordnum;
1953 base = aho->states[ state ].trans.base;
1955 DEBUG_TRIE_EXECUTE_r({
1957 dump_exec_pos( (char *)uc, c, strend, real_start,
1959 PerlIO_printf( Perl_debug_log,
1960 "%sState: %4"UVxf", word=%"UVxf,
1961 failed ? " Fail transition to " : "",
1962 (UV)state, (UV)word);
1968 ( ((offset = base + charid
1969 - 1 - trie->uniquecharcount)) >= 0)
1970 && ((U32)offset < trie->lasttrans)
1971 && trie->trans[offset].check == state
1972 && (tmp=trie->trans[offset].next))
1974 DEBUG_TRIE_EXECUTE_r(
1975 PerlIO_printf( Perl_debug_log," - legal\n"));
1980 DEBUG_TRIE_EXECUTE_r(
1981 PerlIO_printf( Perl_debug_log," - fail\n"));
1983 state = aho->fail[state];
1987 /* we must be accepting here */
1988 DEBUG_TRIE_EXECUTE_r(
1989 PerlIO_printf( Perl_debug_log," - accepting\n"));
1998 if (!state) state = 1;
2001 if ( aho->states[ state ].wordnum ) {
2002 U8 *lpos = points[ (pointpos - trie->wordinfo[aho->states[ state ].wordnum].len) % maxlen ];
2003 if (!leftmost || lpos < leftmost) {
2004 DEBUG_r(accepted_word=aho->states[ state ].wordnum);
2009 s = (char*)leftmost;
2010 DEBUG_TRIE_EXECUTE_r({
2012 Perl_debug_log,"Matches word #%"UVxf" at position %"IVdf". Trying full pattern...\n",
2013 (UV)accepted_word, (IV)(s - real_start)
2016 if (!reginfo || regtry(reginfo, &s)) {
2022 DEBUG_TRIE_EXECUTE_r({
2023 PerlIO_printf( Perl_debug_log,"Pattern failed. Looking for new start point...\n");
2026 DEBUG_TRIE_EXECUTE_r(
2027 PerlIO_printf( Perl_debug_log,"No match.\n"));
2036 Perl_croak(aTHX_ "panic: unknown regstclass %d", (int)OP(c));
2046 - regexec_flags - match a regexp against a string
2049 Perl_regexec_flags(pTHX_ REGEXP * const rx, char *stringarg, char *strend,
2050 char *strbeg, I32 minend, SV *sv, void *data, U32 flags)
2051 /* stringarg: the point in the string at which to begin matching */
2052 /* strend: pointer to null at end of string */
2053 /* strbeg: real beginning of string */
2054 /* minend: end of match must be >= minend bytes after stringarg. */
2055 /* sv: SV being matched: only used for utf8 flag, pos() etc; string
2056 * itself is accessed via the pointers above */
2057 /* data: May be used for some additional optimizations.
2058 Currently its only used, with a U32 cast, for transmitting
2059 the ganch offset when doing a /g match. This will change */
2060 /* nosave: For optimizations. */
2064 struct regexp *const prog = ReANY(rx);
2067 char *startpos = stringarg;
2068 I32 minlen; /* must match at least this many chars */
2069 I32 dontbother = 0; /* how many characters not to try at end */
2070 I32 end_shift = 0; /* Same for the end. */ /* CC */
2071 I32 scream_pos = -1; /* Internal iterator of scream. */
2072 char *scream_olds = NULL;
2073 const bool utf8_target = cBOOL(DO_UTF8(sv));
2075 RXi_GET_DECL(prog,progi);
2076 regmatch_info reginfo; /* create some info to pass to regtry etc */
2077 regexp_paren_pair *swap = NULL;
2078 GET_RE_DEBUG_FLAGS_DECL;
2080 PERL_ARGS_ASSERT_REGEXEC_FLAGS;
2081 PERL_UNUSED_ARG(data);
2083 /* Be paranoid... */
2084 if (prog == NULL || startpos == NULL) {
2085 Perl_croak(aTHX_ "NULL regexp parameter");
2089 multiline = prog->extflags & RXf_PMf_MULTILINE;
2090 reginfo.prog = rx; /* Yes, sorry that this is confusing. */
2092 RX_MATCH_UTF8_set(rx, utf8_target);
2094 debug_start_match(rx, utf8_target, startpos, strend,
2098 minlen = prog->minlen;
2100 if (strend - startpos < (minlen+(prog->check_offset_min<0?prog->check_offset_min:0))) {
2101 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
2102 "String too short [regexec_flags]...\n"));
2107 /* Check validity of program. */
2108 if (UCHARAT(progi->program) != REG_MAGIC) {
2109 Perl_croak(aTHX_ "corrupted regexp program");
2112 RX_MATCH_TAINTED_off(rx);
2113 PL_reg_state.re_state_eval_setup_done = FALSE;
2116 reginfo.is_utf8_pat = cBOOL(RX_UTF8(rx));
2117 reginfo.warned = FALSE;
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 is_utf8_pat?) */
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, reginfo.is_utf8_pat))
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",
2599 if (PL_reg_state.re_state_eval_setup_done)
2600 restore_pos(aTHX_ prog);
2601 if (RXp_PAREN_NAMES(prog))
2602 (void)hv_iterinit(RXp_PAREN_NAMES(prog));
2604 /* make sure $`, $&, $', and $digit will work later */
2605 if ( !(flags & REXEC_NOT_FIRST) ) {
2606 if (flags & REXEC_COPY_STR) {
2610 PerlIO_printf(Perl_debug_log,
2611 "Copy on write: regexp capture, type %d\n",
2614 RX_MATCH_COPY_FREE(rx);
2615 prog->saved_copy = sv_setsv_cow(prog->saved_copy, sv);
2616 prog->subbeg = (char *)SvPVX_const(prog->saved_copy);
2617 assert (SvPOKp(prog->saved_copy));
2618 prog->sublen = PL_regeol - strbeg;
2619 prog->suboffset = 0;
2620 prog->subcoffset = 0;
2625 I32 max = PL_regeol - strbeg;
2628 if ( (flags & REXEC_COPY_SKIP_POST)
2629 && !(RX_EXTFLAGS(rx) & RXf_PMf_KEEPCOPY) /* //p */
2630 && !(PL_sawampersand & SAWAMPERSAND_RIGHT)
2631 ) { /* don't copy $' part of string */
2634 /* calculate the right-most part of the string covered
2635 * by a capture. Due to look-ahead, this may be to
2636 * the right of $&, so we have to scan all captures */
2637 while (n <= prog->lastparen) {
2638 if (prog->offs[n].end > max)
2639 max = prog->offs[n].end;
2643 max = (PL_sawampersand & SAWAMPERSAND_LEFT)
2644 ? prog->offs[0].start
2646 assert(max >= 0 && max <= PL_regeol - strbeg);
2649 if ( (flags & REXEC_COPY_SKIP_PRE)
2650 && !(RX_EXTFLAGS(rx) & RXf_PMf_KEEPCOPY) /* //p */
2651 && !(PL_sawampersand & SAWAMPERSAND_LEFT)
2652 ) { /* don't copy $` part of string */
2655 /* calculate the left-most part of the string covered
2656 * by a capture. Due to look-behind, this may be to
2657 * the left of $&, so we have to scan all captures */
2658 while (min && n <= prog->lastparen) {
2659 if ( prog->offs[n].start != -1
2660 && prog->offs[n].start < min)
2662 min = prog->offs[n].start;
2666 if ((PL_sawampersand & SAWAMPERSAND_RIGHT)
2667 && min > prog->offs[0].end
2669 min = prog->offs[0].end;
2673 assert(min >= 0 && min <= max && min <= PL_regeol - strbeg);
2676 if (RX_MATCH_COPIED(rx)) {
2677 if (sublen > prog->sublen)
2679 (char*)saferealloc(prog->subbeg, sublen+1);
2682 prog->subbeg = (char*)safemalloc(sublen+1);
2683 Copy(strbeg + min, prog->subbeg, sublen, char);
2684 prog->subbeg[sublen] = '\0';
2685 prog->suboffset = min;
2686 prog->sublen = sublen;
2687 RX_MATCH_COPIED_on(rx);
2689 prog->subcoffset = prog->suboffset;
2690 if (prog->suboffset && utf8_target) {
2691 /* Convert byte offset to chars.
2692 * XXX ideally should only compute this if @-/@+
2693 * has been seen, a la PL_sawampersand ??? */
2695 /* If there's a direct correspondence between the
2696 * string which we're matching and the original SV,
2697 * then we can use the utf8 len cache associated with
2698 * the SV. In particular, it means that under //g,
2699 * sv_pos_b2u() will use the previously cached
2700 * position to speed up working out the new length of
2701 * subcoffset, rather than counting from the start of
2702 * the string each time. This stops
2703 * $x = "\x{100}" x 1E6; 1 while $x =~ /(.)/g;
2704 * from going quadratic */
2705 if (SvPOKp(sv) && SvPVX(sv) == strbeg)
2706 sv_pos_b2u(sv, &(prog->subcoffset));
2708 prog->subcoffset = utf8_length((U8*)strbeg,
2709 (U8*)(strbeg+prog->suboffset));
2713 RX_MATCH_COPY_FREE(rx);
2714 prog->subbeg = strbeg;
2715 prog->suboffset = 0;
2716 prog->subcoffset = 0;
2717 prog->sublen = PL_regeol - strbeg; /* strend may have been modified */
2724 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "%sMatch failed%s\n",
2725 PL_colors[4], PL_colors[5]));
2726 if (PL_reg_state.re_state_eval_setup_done)
2727 restore_pos(aTHX_ prog);
2729 /* we failed :-( roll it back */
2730 DEBUG_BUFFERS_r(PerlIO_printf(Perl_debug_log,
2731 "rex=0x%"UVxf" rolling back offs: freeing=0x%"UVxf" restoring=0x%"UVxf"\n",
2736 Safefree(prog->offs);
2743 /* Set which rex is pointed to by PL_reg_state, handling ref counting.
2744 * Do inc before dec, in case old and new rex are the same */
2745 #define SET_reg_curpm(Re2) \
2746 if (PL_reg_state.re_state_eval_setup_done) { \
2747 (void)ReREFCNT_inc(Re2); \
2748 ReREFCNT_dec(PM_GETRE(PL_reg_curpm)); \
2749 PM_SETRE((PL_reg_curpm), (Re2)); \
2754 - regtry - try match at specific point
2756 STATIC I32 /* 0 failure, 1 success */
2757 S_regtry(pTHX_ regmatch_info *reginfo, char **startposp)
2761 REGEXP *const rx = reginfo->prog;
2762 regexp *const prog = ReANY(rx);
2764 RXi_GET_DECL(prog,progi);
2765 GET_RE_DEBUG_FLAGS_DECL;
2767 PERL_ARGS_ASSERT_REGTRY;
2769 reginfo->cutpoint=NULL;
2771 if ((prog->extflags & RXf_EVAL_SEEN)
2772 && !PL_reg_state.re_state_eval_setup_done)
2776 PL_reg_state.re_state_eval_setup_done = TRUE;
2778 /* Make $_ available to executed code. */
2779 if (reginfo->sv != DEFSV) {
2781 DEFSV_set(reginfo->sv);
2784 if (!(SvTYPE(reginfo->sv) >= SVt_PVMG && SvMAGIC(reginfo->sv)
2785 && (mg = mg_find(reginfo->sv, PERL_MAGIC_regex_global)))) {
2786 /* prepare for quick setting of pos */
2787 #ifdef PERL_OLD_COPY_ON_WRITE
2788 if (SvIsCOW(reginfo->sv))
2789 sv_force_normal_flags(reginfo->sv, 0);
2791 mg = sv_magicext(reginfo->sv, NULL, PERL_MAGIC_regex_global,
2792 &PL_vtbl_mglob, NULL, 0);
2796 PL_reg_oldpos = mg->mg_len;
2797 SAVEDESTRUCTOR_X(restore_pos, prog);
2799 if (!PL_reg_curpm) {
2800 Newxz(PL_reg_curpm, 1, PMOP);
2803 SV* const repointer = &PL_sv_undef;
2804 /* this regexp is also owned by the new PL_reg_curpm, which
2805 will try to free it. */
2806 av_push(PL_regex_padav, repointer);
2807 PL_reg_curpm->op_pmoffset = av_len(PL_regex_padav);
2808 PL_regex_pad = AvARRAY(PL_regex_padav);
2813 PL_reg_oldcurpm = PL_curpm;
2814 PL_curpm = PL_reg_curpm;
2815 if (RXp_MATCH_COPIED(prog)) {
2816 /* Here is a serious problem: we cannot rewrite subbeg,
2817 since it may be needed if this match fails. Thus
2818 $` inside (?{}) could fail... */
2819 PL_reg_oldsaved = prog->subbeg;
2820 PL_reg_oldsavedlen = prog->sublen;
2821 PL_reg_oldsavedoffset = prog->suboffset;
2822 PL_reg_oldsavedcoffset = prog->suboffset;
2824 PL_nrs = prog->saved_copy;
2826 RXp_MATCH_COPIED_off(prog);
2829 PL_reg_oldsaved = NULL;
2830 prog->subbeg = PL_bostr;
2831 prog->suboffset = 0;
2832 prog->subcoffset = 0;
2833 prog->sublen = PL_regeol - PL_bostr; /* strend may have been modified */
2836 PL_reg_starttry = *startposp;
2838 prog->offs[0].start = *startposp - PL_bostr;
2839 prog->lastparen = 0;
2840 prog->lastcloseparen = 0;
2842 /* XXXX What this code is doing here?!!! There should be no need
2843 to do this again and again, prog->lastparen should take care of
2846 /* Tests pat.t#187 and split.t#{13,14} seem to depend on this code.
2847 * Actually, the code in regcppop() (which Ilya may be meaning by
2848 * prog->lastparen), is not needed at all by the test suite
2849 * (op/regexp, op/pat, op/split), but that code is needed otherwise
2850 * this erroneously leaves $1 defined: "1" =~ /^(?:(\d)x)?\d$/
2851 * Meanwhile, this code *is* needed for the
2852 * above-mentioned test suite tests to succeed. The common theme
2853 * on those tests seems to be returning null fields from matches.
2854 * --jhi updated by dapm */
2856 if (prog->nparens) {
2857 regexp_paren_pair *pp = prog->offs;
2859 for (i = prog->nparens; i > (I32)prog->lastparen; i--) {
2867 result = regmatch(reginfo, *startposp, progi->program + 1);
2869 prog->offs[0].end = result;
2872 if (reginfo->cutpoint)
2873 *startposp= reginfo->cutpoint;
2874 REGCP_UNWIND(lastcp);
2879 #define sayYES goto yes
2880 #define sayNO goto no
2881 #define sayNO_SILENT goto no_silent
2883 /* we dont use STMT_START/END here because it leads to
2884 "unreachable code" warnings, which are bogus, but distracting. */
2885 #define CACHEsayNO \
2886 if (ST.cache_mask) \
2887 PL_reg_poscache[ST.cache_offset] |= ST.cache_mask; \
2890 /* this is used to determine how far from the left messages like
2891 'failed...' are printed. It should be set such that messages
2892 are inline with the regop output that created them.
2894 #define REPORT_CODE_OFF 32
2897 #define CHRTEST_UNINIT -1001 /* c1/c2 haven't been calculated yet */
2898 #define CHRTEST_VOID -1000 /* the c1/c2 "next char" test should be skipped */
2899 #define CHRTEST_NOT_A_CP_1 -999
2900 #define CHRTEST_NOT_A_CP_2 -998
2902 #define SLAB_FIRST(s) (&(s)->states[0])
2903 #define SLAB_LAST(s) (&(s)->states[PERL_REGMATCH_SLAB_SLOTS-1])
2905 /* grab a new slab and return the first slot in it */
2907 STATIC regmatch_state *
2910 #if PERL_VERSION < 9 && !defined(PERL_CORE)
2913 regmatch_slab *s = PL_regmatch_slab->next;
2915 Newx(s, 1, regmatch_slab);
2916 s->prev = PL_regmatch_slab;
2918 PL_regmatch_slab->next = s;
2920 PL_regmatch_slab = s;
2921 return SLAB_FIRST(s);
2925 /* push a new state then goto it */
2927 #define PUSH_STATE_GOTO(state, node, input) \
2928 pushinput = input; \
2930 st->resume_state = state; \
2933 /* push a new state with success backtracking, then goto it */
2935 #define PUSH_YES_STATE_GOTO(state, node, input) \
2936 pushinput = input; \
2938 st->resume_state = state; \
2939 goto push_yes_state;
2946 regmatch() - main matching routine
2948 This is basically one big switch statement in a loop. We execute an op,
2949 set 'next' to point the next op, and continue. If we come to a point which
2950 we may need to backtrack to on failure such as (A|B|C), we push a
2951 backtrack state onto the backtrack stack. On failure, we pop the top
2952 state, and re-enter the loop at the state indicated. If there are no more
2953 states to pop, we return failure.
2955 Sometimes we also need to backtrack on success; for example /A+/, where
2956 after successfully matching one A, we need to go back and try to
2957 match another one; similarly for lookahead assertions: if the assertion
2958 completes successfully, we backtrack to the state just before the assertion
2959 and then carry on. In these cases, the pushed state is marked as
2960 'backtrack on success too'. This marking is in fact done by a chain of
2961 pointers, each pointing to the previous 'yes' state. On success, we pop to
2962 the nearest yes state, discarding any intermediate failure-only states.
2963 Sometimes a yes state is pushed just to force some cleanup code to be
2964 called at the end of a successful match or submatch; e.g. (??{$re}) uses
2965 it to free the inner regex.
2967 Note that failure backtracking rewinds the cursor position, while
2968 success backtracking leaves it alone.
2970 A pattern is complete when the END op is executed, while a subpattern
2971 such as (?=foo) is complete when the SUCCESS op is executed. Both of these
2972 ops trigger the "pop to last yes state if any, otherwise return true"
2975 A common convention in this function is to use A and B to refer to the two
2976 subpatterns (or to the first nodes thereof) in patterns like /A*B/: so A is
2977 the subpattern to be matched possibly multiple times, while B is the entire
2978 rest of the pattern. Variable and state names reflect this convention.
2980 The states in the main switch are the union of ops and failure/success of
2981 substates associated with with that op. For example, IFMATCH is the op
2982 that does lookahead assertions /(?=A)B/ and so the IFMATCH state means
2983 'execute IFMATCH'; while IFMATCH_A is a state saying that we have just
2984 successfully matched A and IFMATCH_A_fail is a state saying that we have
2985 just failed to match A. Resume states always come in pairs. The backtrack
2986 state we push is marked as 'IFMATCH_A', but when that is popped, we resume
2987 at IFMATCH_A or IFMATCH_A_fail, depending on whether we are backtracking
2988 on success or failure.
2990 The struct that holds a backtracking state is actually a big union, with
2991 one variant for each major type of op. The variable st points to the
2992 top-most backtrack struct. To make the code clearer, within each
2993 block of code we #define ST to alias the relevant union.
2995 Here's a concrete example of a (vastly oversimplified) IFMATCH
3001 #define ST st->u.ifmatch
3003 case IFMATCH: // we are executing the IFMATCH op, (?=A)B
3004 ST.foo = ...; // some state we wish to save
3006 // push a yes backtrack state with a resume value of
3007 // IFMATCH_A/IFMATCH_A_fail, then continue execution at the
3009 PUSH_YES_STATE_GOTO(IFMATCH_A, A, newinput);
3012 case IFMATCH_A: // we have successfully executed A; now continue with B
3014 bar = ST.foo; // do something with the preserved value
3017 case IFMATCH_A_fail: // A failed, so the assertion failed
3018 ...; // do some housekeeping, then ...
3019 sayNO; // propagate the failure
3026 For any old-timers reading this who are familiar with the old recursive
3027 approach, the code above is equivalent to:
3029 case IFMATCH: // we are executing the IFMATCH op, (?=A)B
3038 ...; // do some housekeeping, then ...
3039 sayNO; // propagate the failure
3042 The topmost backtrack state, pointed to by st, is usually free. If you
3043 want to claim it, populate any ST.foo fields in it with values you wish to
3044 save, then do one of
3046 PUSH_STATE_GOTO(resume_state, node, newinput);
3047 PUSH_YES_STATE_GOTO(resume_state, node, newinput);
3049 which sets that backtrack state's resume value to 'resume_state', pushes a
3050 new free entry to the top of the backtrack stack, then goes to 'node'.
3051 On backtracking, the free slot is popped, and the saved state becomes the
3052 new free state. An ST.foo field in this new top state can be temporarily
3053 accessed to retrieve values, but once the main loop is re-entered, it
3054 becomes available for reuse.
3056 Note that the depth of the backtrack stack constantly increases during the
3057 left-to-right execution of the pattern, rather than going up and down with
3058 the pattern nesting. For example the stack is at its maximum at Z at the
3059 end of the pattern, rather than at X in the following:
3061 /(((X)+)+)+....(Y)+....Z/
3063 The only exceptions to this are lookahead/behind assertions and the cut,
3064 (?>A), which pop all the backtrack states associated with A before
3067 Backtrack state structs are allocated in slabs of about 4K in size.
3068 PL_regmatch_state and st always point to the currently active state,
3069 and PL_regmatch_slab points to the slab currently containing
3070 PL_regmatch_state. The first time regmatch() is called, the first slab is
3071 allocated, and is never freed until interpreter destruction. When the slab
3072 is full, a new one is allocated and chained to the end. At exit from
3073 regmatch(), slabs allocated since entry are freed.
3078 #define DEBUG_STATE_pp(pp) \
3080 DUMP_EXEC_POS(locinput, scan, utf8_target); \
3081 PerlIO_printf(Perl_debug_log, \
3082 " %*s"pp" %s%s%s%s%s\n", \
3084 PL_reg_name[st->resume_state], \
3085 ((st==yes_state||st==mark_state) ? "[" : ""), \
3086 ((st==yes_state) ? "Y" : ""), \
3087 ((st==mark_state) ? "M" : ""), \
3088 ((st==yes_state||st==mark_state) ? "]" : "") \
3093 #define REG_NODE_NUM(x) ((x) ? (int)((x)-prog) : -1)
3098 S_debug_start_match(pTHX_ const REGEXP *prog, const bool utf8_target,
3099 const char *start, const char *end, const char *blurb)
3101 const bool utf8_pat = RX_UTF8(prog) ? 1 : 0;
3103 PERL_ARGS_ASSERT_DEBUG_START_MATCH;
3108 RE_PV_QUOTED_DECL(s0, utf8_pat, PERL_DEBUG_PAD_ZERO(0),
3109 RX_PRECOMP_const(prog), RX_PRELEN(prog), 60);
3111 RE_PV_QUOTED_DECL(s1, utf8_target, PERL_DEBUG_PAD_ZERO(1),
3112 start, end - start, 60);
3114 PerlIO_printf(Perl_debug_log,
3115 "%s%s REx%s %s against %s\n",
3116 PL_colors[4], blurb, PL_colors[5], s0, s1);
3118 if (utf8_target||utf8_pat)
3119 PerlIO_printf(Perl_debug_log, "UTF-8 %s%s%s...\n",
3120 utf8_pat ? "pattern" : "",
3121 utf8_pat && utf8_target ? " and " : "",
3122 utf8_target ? "string" : ""
3128 S_dump_exec_pos(pTHX_ const char *locinput,
3129 const regnode *scan,
3130 const char *loc_regeol,
3131 const char *loc_bostr,
3132 const char *loc_reg_starttry,
3133 const bool utf8_target)
3135 const int docolor = *PL_colors[0] || *PL_colors[2] || *PL_colors[4];
3136 const int taill = (docolor ? 10 : 7); /* 3 chars for "> <" */
3137 int l = (loc_regeol - locinput) > taill ? taill : (loc_regeol - locinput);
3138 /* The part of the string before starttry has one color
3139 (pref0_len chars), between starttry and current
3140 position another one (pref_len - pref0_len chars),
3141 after the current position the third one.
3142 We assume that pref0_len <= pref_len, otherwise we
3143 decrease pref0_len. */
3144 int pref_len = (locinput - loc_bostr) > (5 + taill) - l
3145 ? (5 + taill) - l : locinput - loc_bostr;
3148 PERL_ARGS_ASSERT_DUMP_EXEC_POS;
3150 while (utf8_target && UTF8_IS_CONTINUATION(*(U8*)(locinput - pref_len)))
3152 pref0_len = pref_len - (locinput - loc_reg_starttry);
3153 if (l + pref_len < (5 + taill) && l < loc_regeol - locinput)
3154 l = ( loc_regeol - locinput > (5 + taill) - pref_len
3155 ? (5 + taill) - pref_len : loc_regeol - locinput);
3156 while (utf8_target && UTF8_IS_CONTINUATION(*(U8*)(locinput + l)))
3160 if (pref0_len > pref_len)
3161 pref0_len = pref_len;
3163 const int is_uni = (utf8_target && OP(scan) != CANY) ? 1 : 0;
3165 RE_PV_COLOR_DECL(s0,len0,is_uni,PERL_DEBUG_PAD(0),
3166 (locinput - pref_len),pref0_len, 60, 4, 5);
3168 RE_PV_COLOR_DECL(s1,len1,is_uni,PERL_DEBUG_PAD(1),
3169 (locinput - pref_len + pref0_len),
3170 pref_len - pref0_len, 60, 2, 3);
3172 RE_PV_COLOR_DECL(s2,len2,is_uni,PERL_DEBUG_PAD(2),
3173 locinput, loc_regeol - locinput, 10, 0, 1);
3175 const STRLEN tlen=len0+len1+len2;
3176 PerlIO_printf(Perl_debug_log,
3177 "%4"IVdf" <%.*s%.*s%s%.*s>%*s|",
3178 (IV)(locinput - loc_bostr),
3181 (docolor ? "" : "> <"),
3183 (int)(tlen > 19 ? 0 : 19 - tlen),
3190 /* reg_check_named_buff_matched()
3191 * Checks to see if a named buffer has matched. The data array of
3192 * buffer numbers corresponding to the buffer is expected to reside
3193 * in the regexp->data->data array in the slot stored in the ARG() of
3194 * node involved. Note that this routine doesn't actually care about the
3195 * name, that information is not preserved from compilation to execution.
3196 * Returns the index of the leftmost defined buffer with the given name
3197 * or 0 if non of the buffers matched.
3200 S_reg_check_named_buff_matched(pTHX_ const regexp *rex, const regnode *scan)
3203 RXi_GET_DECL(rex,rexi);
3204 SV *sv_dat= MUTABLE_SV(rexi->data->data[ ARG( scan ) ]);
3205 I32 *nums=(I32*)SvPVX(sv_dat);
3207 PERL_ARGS_ASSERT_REG_CHECK_NAMED_BUFF_MATCHED;
3209 for ( n=0; n<SvIVX(sv_dat); n++ ) {
3210 if ((I32)rex->lastparen >= nums[n] &&
3211 rex->offs[nums[n]].end != -1)
3220 /* free all slabs above current one - called during LEAVE_SCOPE */
3223 S_clear_backtrack_stack(pTHX_ void *p)
3225 regmatch_slab *s = PL_regmatch_slab->next;
3230 PL_regmatch_slab->next = NULL;
3232 regmatch_slab * const osl = s;
3238 S_setup_EXACTISH_ST_c1_c2(pTHX_ const regnode * const text_node, int *c1p,
3239 U8* c1_utf8, int *c2p, U8* c2_utf8, bool is_utf8_pat)
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
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 = is_utf8_pat ? 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;
3565 bool is_utf8_pat = reginfo->is_utf8_pat;
3568 GET_RE_DEBUG_FLAGS_DECL;
3571 /* shut up 'may be used uninitialized' compiler warnings for dMULTICALL */
3572 multicall_oldcatch = 0;
3573 multicall_cv = NULL;
3575 PERL_UNUSED_VAR(multicall_cop);
3576 PERL_UNUSED_VAR(newsp);
3579 PERL_ARGS_ASSERT_REGMATCH;
3581 DEBUG_OPTIMISE_r( DEBUG_EXECUTE_r({
3582 PerlIO_printf(Perl_debug_log,"regmatch start\n");
3584 /* on first ever call to regmatch, allocate first slab */
3585 if (!PL_regmatch_slab) {
3586 Newx(PL_regmatch_slab, 1, regmatch_slab);
3587 PL_regmatch_slab->prev = NULL;
3588 PL_regmatch_slab->next = NULL;
3589 PL_regmatch_state = SLAB_FIRST(PL_regmatch_slab);
3592 oldsave = PL_savestack_ix;
3593 SAVEDESTRUCTOR_X(S_clear_backtrack_stack, NULL);
3594 SAVEVPTR(PL_regmatch_slab);
3595 SAVEVPTR(PL_regmatch_state);
3597 /* grab next free state slot */
3598 st = ++PL_regmatch_state;
3599 if (st > SLAB_LAST(PL_regmatch_slab))
3600 st = PL_regmatch_state = S_push_slab(aTHX);
3602 /* Note that nextchr is a byte even in UTF */
3605 while (scan != NULL) {
3608 SV * const prop = sv_newmortal();
3609 regnode *rnext=regnext(scan);
3610 DUMP_EXEC_POS( locinput, scan, utf8_target );
3611 regprop(rex, prop, scan);
3613 PerlIO_printf(Perl_debug_log,
3614 "%3"IVdf":%*s%s(%"IVdf")\n",
3615 (IV)(scan - rexi->program), depth*2, "",
3617 (PL_regkind[OP(scan)] == END || !rnext) ?
3618 0 : (IV)(rnext - rexi->program));
3621 next = scan + NEXT_OFF(scan);
3624 state_num = OP(scan);
3630 assert(nextchr < 256 && (nextchr >= 0 || nextchr == NEXTCHR_EOS));
3632 switch (state_num) {
3633 case BOL: /* /^../ */
3634 if (locinput == PL_bostr)
3636 /* reginfo->till = reginfo->bol; */
3641 case MBOL: /* /^../m */
3642 if (locinput == PL_bostr ||
3643 (!NEXTCHR_IS_EOS && locinput[-1] == '\n'))
3649 case SBOL: /* /^../s */
3650 if (locinput == PL_bostr)
3655 if (locinput == reginfo->ganch)
3659 case KEEPS: /* \K */
3660 /* update the startpoint */
3661 st->u.keeper.val = rex->offs[0].start;
3662 rex->offs[0].start = locinput - PL_bostr;
3663 PUSH_STATE_GOTO(KEEPS_next, next, locinput);
3664 assert(0); /*NOTREACHED*/
3665 case KEEPS_next_fail:
3666 /* rollback the start point change */
3667 rex->offs[0].start = st->u.keeper.val;
3669 assert(0); /*NOTREACHED*/
3671 case EOL: /* /..$/ */
3674 case MEOL: /* /..$/m */
3675 if (!NEXTCHR_IS_EOS && nextchr != '\n')
3679 case SEOL: /* /..$/s */
3681 if (!NEXTCHR_IS_EOS && nextchr != '\n')
3683 if (PL_regeol - locinput > 1)
3688 if (!NEXTCHR_IS_EOS)
3692 case SANY: /* /./s */
3695 goto increment_locinput;
3703 case REG_ANY: /* /./ */
3704 if ((NEXTCHR_IS_EOS) || nextchr == '\n')
3706 goto increment_locinput;
3710 #define ST st->u.trie
3711 case TRIEC: /* (ab|cd) with known charclass */
3712 /* In this case the charclass data is available inline so
3713 we can fail fast without a lot of extra overhead.
3715 if(!NEXTCHR_IS_EOS && !ANYOF_BITMAP_TEST(scan, nextchr)) {
3717 PerlIO_printf(Perl_debug_log,
3718 "%*s %sfailed to match trie start class...%s\n",
3719 REPORT_CODE_OFF+depth*2, "", PL_colors[4], PL_colors[5])
3722 assert(0); /* NOTREACHED */
3725 case TRIE: /* (ab|cd) */
3726 /* the basic plan of execution of the trie is:
3727 * At the beginning, run though all the states, and
3728 * find the longest-matching word. Also remember the position
3729 * of the shortest matching word. For example, this pattern:
3732 * when matched against the string "abcde", will generate
3733 * accept states for all words except 3, with the longest
3734 * matching word being 4, and the shortest being 2 (with
3735 * the position being after char 1 of the string).
3737 * Then for each matching word, in word order (i.e. 1,2,4,5),
3738 * we run the remainder of the pattern; on each try setting
3739 * the current position to the character following the word,
3740 * returning to try the next word on failure.
3742 * We avoid having to build a list of words at runtime by
3743 * using a compile-time structure, wordinfo[].prev, which
3744 * gives, for each word, the previous accepting word (if any).
3745 * In the case above it would contain the mappings 1->2, 2->0,
3746 * 3->0, 4->5, 5->1. We can use this table to generate, from
3747 * the longest word (4 above), a list of all words, by
3748 * following the list of prev pointers; this gives us the
3749 * unordered list 4,5,1,2. Then given the current word we have
3750 * just tried, we can go through the list and find the
3751 * next-biggest word to try (so if we just failed on word 2,
3752 * the next in the list is 4).
3754 * Since at runtime we don't record the matching position in
3755 * the string for each word, we have to work that out for
3756 * each word we're about to process. The wordinfo table holds
3757 * the character length of each word; given that we recorded
3758 * at the start: the position of the shortest word and its
3759 * length in chars, we just need to move the pointer the
3760 * difference between the two char lengths. Depending on
3761 * Unicode status and folding, that's cheap or expensive.
3763 * This algorithm is optimised for the case where are only a
3764 * small number of accept states, i.e. 0,1, or maybe 2.
3765 * With lots of accepts states, and having to try all of them,
3766 * it becomes quadratic on number of accept states to find all
3771 /* what type of TRIE am I? (utf8 makes this contextual) */
3772 DECL_TRIE_TYPE(scan);
3774 /* what trie are we using right now */
3775 reg_trie_data * const trie
3776 = (reg_trie_data*)rexi->data->data[ ARG( scan ) ];
3777 HV * widecharmap = MUTABLE_HV(rexi->data->data[ ARG( scan ) + 1 ]);
3778 U32 state = trie->startstate;
3781 && (NEXTCHR_IS_EOS || !TRIE_BITMAP_TEST(trie, nextchr)))
3783 if (trie->states[ state ].wordnum) {
3785 PerlIO_printf(Perl_debug_log,
3786 "%*s %smatched empty string...%s\n",
3787 REPORT_CODE_OFF+depth*2, "", PL_colors[4], PL_colors[5])
3793 PerlIO_printf(Perl_debug_log,
3794 "%*s %sfailed to match trie start class...%s\n",
3795 REPORT_CODE_OFF+depth*2, "", PL_colors[4], PL_colors[5])
3802 U8 *uc = ( U8* )locinput;
3806 U8 *uscan = (U8*)NULL;
3807 U8 foldbuf[ UTF8_MAXBYTES_CASE + 1 ];
3808 U32 charcount = 0; /* how many input chars we have matched */
3809 U32 accepted = 0; /* have we seen any accepting states? */
3811 ST.jump = trie->jump;
3814 ST.longfold = FALSE; /* char longer if folded => it's harder */
3817 /* fully traverse the TRIE; note the position of the
3818 shortest accept state and the wordnum of the longest
3821 while ( state && uc <= (U8*)PL_regeol ) {
3822 U32 base = trie->states[ state ].trans.base;
3826 wordnum = trie->states[ state ].wordnum;
3828 if (wordnum) { /* it's an accept state */
3831 /* record first match position */
3833 ST.firstpos = (U8*)locinput;
3838 ST.firstchars = charcount;
3841 if (!ST.nextword || wordnum < ST.nextword)
3842 ST.nextword = wordnum;
3843 ST.topword = wordnum;
3846 DEBUG_TRIE_EXECUTE_r({
3847 DUMP_EXEC_POS( (char *)uc, scan, utf8_target );
3848 PerlIO_printf( Perl_debug_log,
3849 "%*s %sState: %4"UVxf" Accepted: %c ",
3850 2+depth * 2, "", PL_colors[4],
3851 (UV)state, (accepted ? 'Y' : 'N'));
3854 /* read a char and goto next state */
3855 if ( base && (foldlen || uc < (U8*)PL_regeol)) {
3857 REXEC_TRIE_READ_CHAR(trie_type, trie, widecharmap, uc,
3858 uscan, len, uvc, charid, foldlen,
3865 base + charid - 1 - trie->uniquecharcount)) >= 0)
3867 && ((U32)offset < trie->lasttrans)
3868 && trie->trans[offset].check == state)
3870 state = trie->trans[offset].next;
3881 DEBUG_TRIE_EXECUTE_r(
3882 PerlIO_printf( Perl_debug_log,
3883 "Charid:%3x CP:%4"UVxf" After State: %4"UVxf"%s\n",
3884 charid, uvc, (UV)state, PL_colors[5] );
3890 /* calculate total number of accept states */
3895 w = trie->wordinfo[w].prev;
3898 ST.accepted = accepted;
3902 PerlIO_printf( Perl_debug_log,
3903 "%*s %sgot %"IVdf" possible matches%s\n",
3904 REPORT_CODE_OFF + depth * 2, "",
3905 PL_colors[4], (IV)ST.accepted, PL_colors[5] );
3907 goto trie_first_try; /* jump into the fail handler */
3909 assert(0); /* NOTREACHED */
3911 case TRIE_next_fail: /* we failed - try next alternative */
3915 REGCP_UNWIND(ST.cp);
3916 UNWIND_PAREN(ST.lastparen, ST.lastcloseparen);
3918 if (!--ST.accepted) {
3920 PerlIO_printf( Perl_debug_log,
3921 "%*s %sTRIE failed...%s\n",
3922 REPORT_CODE_OFF+depth*2, "",
3929 /* Find next-highest word to process. Note that this code
3930 * is O(N^2) per trie run (O(N) per branch), so keep tight */
3933 U16 const nextword = ST.nextword;
3934 reg_trie_wordinfo * const wordinfo
3935 = ((reg_trie_data*)rexi->data->data[ARG(ST.me)])->wordinfo;
3936 for (word=ST.topword; word; word=wordinfo[word].prev) {
3937 if (word > nextword && (!min || word < min))
3950 ST.lastparen = rex->lastparen;
3951 ST.lastcloseparen = rex->lastcloseparen;
3955 /* find start char of end of current word */
3957 U32 chars; /* how many chars to skip */
3958 reg_trie_data * const trie
3959 = (reg_trie_data*)rexi->data->data[ARG(ST.me)];
3961 assert((trie->wordinfo[ST.nextword].len - trie->prefixlen)
3963 chars = (trie->wordinfo[ST.nextword].len - trie->prefixlen)
3968 /* the hard option - fold each char in turn and find
3969 * its folded length (which may be different */
3970 U8 foldbuf[UTF8_MAXBYTES_CASE + 1];
3978 uvc = utf8n_to_uvuni((U8*)uc, UTF8_MAXLEN, &len,
3986 uvc = to_uni_fold(uvc, foldbuf, &foldlen);
3991 uvc = utf8n_to_uvuni(uscan, UTF8_MAXLEN, &len,
4007 scan = ST.me + ((ST.jump && ST.jump[ST.nextword])
4008 ? ST.jump[ST.nextword]
4012 PerlIO_printf( Perl_debug_log,
4013 "%*s %sTRIE matched word #%d, continuing%s\n",
4014 REPORT_CODE_OFF+depth*2, "",
4021 if (ST.accepted > 1 || has_cutgroup) {
4022 PUSH_STATE_GOTO(TRIE_next, scan, (char*)uc);
4023 assert(0); /* NOTREACHED */
4025 /* only one choice left - just continue */
4027 AV *const trie_words
4028 = MUTABLE_AV(rexi->data->data[ARG(ST.me)+TRIE_WORDS_OFFSET]);
4029 SV ** const tmp = av_fetch( trie_words,
4031 SV *sv= tmp ? sv_newmortal() : NULL;
4033 PerlIO_printf( Perl_debug_log,
4034 "%*s %sonly one match left, short-circuiting: #%d <%s>%s\n",
4035 REPORT_CODE_OFF+depth*2, "", PL_colors[4],
4037 tmp ? pv_pretty(sv, SvPV_nolen_const(*tmp), SvCUR(*tmp), 0,
4038 PL_colors[0], PL_colors[1],
4039 (SvUTF8(*tmp) ? PERL_PV_ESCAPE_UNI : 0)|PERL_PV_ESCAPE_NONASCII
4041 : "not compiled under -Dr",
4045 locinput = (char*)uc;
4046 continue; /* execute rest of RE */
4047 assert(0); /* NOTREACHED */
4051 case EXACT: { /* /abc/ */
4052 char *s = STRING(scan);
4054 if (utf8_target != is_utf8_pat) {
4055 /* The target and the pattern have differing utf8ness. */
4057 const char * const e = s + ln;
4060 /* The target is utf8, the pattern is not utf8.
4061 * Above-Latin1 code points can't match the pattern;
4062 * invariants match exactly, and the other Latin1 ones need
4063 * to be downgraded to a single byte in order to do the
4064 * comparison. (If we could be confident that the target
4065 * is not malformed, this could be refactored to have fewer
4066 * tests by just assuming that if the first bytes match, it
4067 * is an invariant, but there are tests in the test suite
4068 * dealing with (??{...}) which violate this) */
4070 if (l >= PL_regeol || UTF8_IS_ABOVE_LATIN1(* (U8*) l)) {
4073 if (UTF8_IS_INVARIANT(*(U8*)l)) {
4080 if (TWO_BYTE_UTF8_TO_UNI(*l, *(l+1)) != * (U8*) s) {
4089 /* The target is not utf8, the pattern is utf8. */
4091 if (l >= PL_regeol || UTF8_IS_ABOVE_LATIN1(* (U8*) s))
4095 if (UTF8_IS_INVARIANT(*(U8*)s)) {
4102 if (TWO_BYTE_UTF8_TO_UNI(*s, *(s+1)) != * (U8*) l) {
4113 /* The target and the pattern have the same utf8ness. */
4114 /* Inline the first character, for speed. */
4115 if (PL_regeol - locinput < ln
4116 || UCHARAT(s) != nextchr
4117 || (ln > 1 && memNE(s, locinput, ln)))
4126 case EXACTFL: { /* /abc/il */
4128 const U8 * fold_array;
4130 U32 fold_utf8_flags;
4132 RX_MATCH_TAINTED_on(reginfo->prog);
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 = is_utf8_pat ? 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 || is_utf8_pat || 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, is_utf8_pat,
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 RX_MATCH_TAINTED_on(reginfo->prog);
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 = isWORDCHAR_uni(ln);
4221 LOAD_UTF8_CHARCLASS_ALNUM();
4222 n = swash_fetch(PL_utf8_swash_ptrs[_CC_WORDCHAR], (U8*)locinput,
4227 ln = isWORDCHAR_LC_uvchr(UNI_TO_NATIVE(ln));
4228 n = NEXTCHR_IS_EOS ? 0 : isWORDCHAR_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 = isWORDCHAR_LC(ln);
4253 n = NEXTCHR_IS_EOS ? 0 : isWORDCHAR_LC(nextchr);
4255 case REGEX_DEPENDS_CHARSET:
4256 ln = isWORDCHAR(ln);
4257 n = NEXTCHR_IS_EOS ? 0 : isWORDCHAR(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]/ */
4276 case ANYOF_WARN_SUPER:
4280 if (!reginclass(rex, scan, (U8*)locinput, utf8_target))
4282 locinput += UTF8SKIP(locinput);
4285 if (!REGINCLASS(rex, scan, (U8*)locinput))
4291 /* The argument (FLAGS) to all the POSIX node types is the class number
4294 case NPOSIXL: /* \W or [:^punct:] etc. under /l */
4298 case POSIXL: /* \w or [:punct:] etc. under /l */
4302 /* The locale hasn't influenced the outcome before this, so defer
4303 * tainting until now */
4304 RX_MATCH_TAINTED_on(reginfo->prog);
4306 /* Use isFOO_lc() for characters within Latin1. (Note that
4307 * UTF8_IS_INVARIANT works even on non-UTF-8 strings, or else
4308 * wouldn't be invariant) */
4309 if (UTF8_IS_INVARIANT(nextchr) || ! utf8_target) {
4310 if (! (to_complement ^ cBOOL(isFOO_lc(FLAGS(scan), (U8) nextchr)))) {
4314 else if (UTF8_IS_DOWNGRADEABLE_START(nextchr)) {
4315 if (! (to_complement ^ cBOOL(isFOO_lc(FLAGS(scan),
4316 (U8) TWO_BYTE_UTF8_TO_UNI(nextchr,
4317 *(locinput + 1))))))
4322 else { /* Here, must be an above Latin-1 code point */
4323 goto utf8_posix_not_eos;
4326 /* Here, must be utf8 */
4327 locinput += UTF8SKIP(locinput);
4330 case NPOSIXD: /* \W or [:^punct:] etc. under /d */
4334 case POSIXD: /* \w or [:punct:] etc. under /d */
4340 case NPOSIXA: /* \W or [:^punct:] etc. under /a */
4342 if (NEXTCHR_IS_EOS) {
4346 /* All UTF-8 variants match */
4347 if (! UTF8_IS_INVARIANT(nextchr)) {
4348 goto increment_locinput;
4354 case POSIXA: /* \w or [:punct:] etc. under /a */
4357 /* We get here through POSIXD, NPOSIXD, and NPOSIXA when not in
4358 * UTF-8, and also from NPOSIXA even in UTF-8 when the current
4359 * character is a single byte */
4362 || ! (to_complement ^ cBOOL(_generic_isCC_A(nextchr,
4368 /* Here we are either not in utf8, or we matched a utf8-invariant,
4369 * so the next char is the next byte */
4373 case NPOSIXU: /* \W or [:^punct:] etc. under /u */
4377 case POSIXU: /* \w or [:punct:] etc. under /u */
4379 if (NEXTCHR_IS_EOS) {
4384 /* Use _generic_isCC() for characters within Latin1. (Note that
4385 * UTF8_IS_INVARIANT works even on non-UTF-8 strings, or else
4386 * wouldn't be invariant) */
4387 if (UTF8_IS_INVARIANT(nextchr) || ! utf8_target) {
4388 if (! (to_complement ^ cBOOL(_generic_isCC(nextchr,
4395 else if (UTF8_IS_DOWNGRADEABLE_START(nextchr)) {
4396 if (! (to_complement
4397 ^ cBOOL(_generic_isCC(TWO_BYTE_UTF8_TO_UNI(nextchr,
4405 else { /* Handle above Latin-1 code points */
4406 classnum = (_char_class_number) FLAGS(scan);
4407 if (classnum < _FIRST_NON_SWASH_CC) {
4409 /* Here, uses a swash to find such code points. Load if if
4410 * not done already */
4411 if (! PL_utf8_swash_ptrs[classnum]) {
4412 U8 flags = _CORE_SWASH_INIT_ACCEPT_INVLIST;
4413 PL_utf8_swash_ptrs[classnum]
4414 = _core_swash_init("utf8",
4415 swash_property_names[classnum],
4416 &PL_sv_undef, 1, 0, NULL, &flags);
4418 if (! (to_complement
4419 ^ cBOOL(swash_fetch(PL_utf8_swash_ptrs[classnum],
4420 (U8 *) locinput, TRUE))))
4425 else { /* Here, uses macros to find above Latin-1 code points */
4427 case _CC_ENUM_SPACE: /* XXX would require separate
4428 code if we revert the change
4429 of \v matching this */
4430 case _CC_ENUM_PSXSPC:
4431 if (! (to_complement
4432 ^ cBOOL(is_XPERLSPACE_high(locinput))))
4437 case _CC_ENUM_BLANK:
4438 if (! (to_complement
4439 ^ cBOOL(is_HORIZWS_high(locinput))))
4444 case _CC_ENUM_XDIGIT:
4445 if (! (to_complement
4446 ^ cBOOL(is_XDIGIT_high(locinput))))
4451 case _CC_ENUM_VERTSPACE:
4452 if (! (to_complement
4453 ^ cBOOL(is_VERTWS_high(locinput))))
4458 default: /* The rest, e.g. [:cntrl:], can't match
4460 if (! to_complement) {
4466 locinput += UTF8SKIP(locinput);
4470 case CLUMP: /* Match \X: logical Unicode character. This is defined as
4471 a Unicode extended Grapheme Cluster */
4472 /* From http://www.unicode.org/reports/tr29 (5.2 version). An
4473 extended Grapheme Cluster is:
4476 | Prepend* Begin Extend*
4479 Begin is: ( Special_Begin | ! Control )
4480 Special_Begin is: ( Regional-Indicator+ | Hangul-syllable )
4481 Extend is: ( Grapheme_Extend | Spacing_Mark )
4482 Control is: [ GCB_Control | CR | LF ]
4483 Hangul-syllable is: ( T+ | ( L* ( L | ( LVT | ( V | LV ) V* ) T* ) ))
4485 If we create a 'Regular_Begin' = Begin - Special_Begin, then
4488 Begin is ( Regular_Begin + Special Begin )
4490 It turns out that 98.4% of all Unicode code points match
4491 Regular_Begin. Doing it this way eliminates a table match in
4492 the previous implementation for almost all Unicode code points.
4494 There is a subtlety with Prepend* which showed up in testing.
4495 Note that the Begin, and only the Begin is required in:
4496 | Prepend* Begin Extend*
4497 Also, Begin contains '! Control'. A Prepend must be a
4498 '! Control', which means it must also be a Begin. What it
4499 comes down to is that if we match Prepend* and then find no
4500 suitable Begin afterwards, that if we backtrack the last
4501 Prepend, that one will be a suitable Begin.
4506 if (! utf8_target) {
4508 /* Match either CR LF or '.', as all the other possibilities
4510 locinput++; /* Match the . or CR */
4511 if (nextchr == '\r' /* And if it was CR, and the next is LF,
4513 && locinput < PL_regeol
4514 && UCHARAT(locinput) == '\n')
4521 /* Utf8: See if is ( CR LF ); already know that locinput <
4522 * PL_regeol, so locinput+1 is in bounds */
4523 if ( nextchr == '\r' && locinput+1 < PL_regeol
4524 && UCHARAT(locinput + 1) == '\n')
4531 /* In case have to backtrack to beginning, then match '.' */
4532 char *starting = locinput;
4534 /* In case have to backtrack the last prepend */
4535 char *previous_prepend = NULL;
4537 LOAD_UTF8_CHARCLASS_GCB();
4539 /* Match (prepend)* */
4540 while (locinput < PL_regeol
4541 && (len = is_GCB_Prepend_utf8(locinput)))
4543 previous_prepend = locinput;
4547 /* As noted above, if we matched a prepend character, but
4548 * the next thing won't match, back off the last prepend we
4549 * matched, as it is guaranteed to match the begin */
4550 if (previous_prepend
4551 && (locinput >= PL_regeol
4552 || (! swash_fetch(PL_utf8_X_regular_begin,
4553 (U8*)locinput, utf8_target)
4554 && ! is_GCB_SPECIAL_BEGIN_START_utf8(locinput)))
4557 locinput = previous_prepend;
4560 /* Note that here we know PL_regeol > locinput, as we
4561 * tested that upon input to this switch case, and if we
4562 * moved locinput forward, we tested the result just above
4563 * and it either passed, or we backed off so that it will
4565 if (swash_fetch(PL_utf8_X_regular_begin,
4566 (U8*)locinput, utf8_target)) {
4567 locinput += UTF8SKIP(locinput);
4569 else if (! is_GCB_SPECIAL_BEGIN_START_utf8(locinput)) {
4571 /* Here did not match the required 'Begin' in the
4572 * second term. So just match the very first
4573 * character, the '.' of the final term of the regex */
4574 locinput = starting + UTF8SKIP(starting);
4578 /* Here is a special begin. It can be composed of
4579 * several individual characters. One possibility is
4581 if ((len = is_GCB_RI_utf8(locinput))) {
4583 while (locinput < PL_regeol
4584 && (len = is_GCB_RI_utf8(locinput)))
4588 } else if ((len = is_GCB_T_utf8(locinput))) {
4589 /* Another possibility is T+ */
4591 while (locinput < PL_regeol
4592 && (len = is_GCB_T_utf8(locinput)))
4598 /* Here, neither RI+ nor T+; must be some other
4599 * Hangul. That means it is one of the others: L,
4600 * LV, LVT or V, and matches:
4601 * L* (L | LVT T* | V * V* T* | LV V* T*) */
4604 while (locinput < PL_regeol
4605 && (len = is_GCB_L_utf8(locinput)))
4610 /* Here, have exhausted L*. If the next character
4611 * is not an LV, LVT nor V, it means we had to have
4612 * at least one L, so matches L+ in the original
4613 * equation, we have a complete hangul syllable.
4616 if (locinput < PL_regeol
4617 && is_GCB_LV_LVT_V_utf8(locinput))
4619 /* Otherwise keep going. Must be LV, LVT or V.
4620 * See if LVT, by first ruling out V, then LV */
4621 if (! is_GCB_V_utf8(locinput)
4622 /* All but every TCount one is LV */
4623 && (valid_utf8_to_uvchr((U8 *) locinput,
4628 locinput += UTF8SKIP(locinput);
4631 /* Must be V or LV. Take it, then match
4633 locinput += UTF8SKIP(locinput);
4634 while (locinput < PL_regeol
4635 && (len = is_GCB_V_utf8(locinput)))
4641 /* And any of LV, LVT, or V can be followed
4643 while (locinput < PL_regeol
4644 && (len = is_GCB_T_utf8(locinput)))
4652 /* Match any extender */
4653 while (locinput < PL_regeol
4654 && swash_fetch(PL_utf8_X_extend,
4655 (U8*)locinput, utf8_target))
4657 locinput += UTF8SKIP(locinput);
4661 if (locinput > PL_regeol) sayNO;
4665 case NREFFL: /* /\g{name}/il */
4666 { /* The capture buffer cases. The ones beginning with N for the
4667 named buffers just convert to the equivalent numbered and
4668 pretend they were called as the corresponding numbered buffer
4670 /* don't initialize these in the declaration, it makes C++
4675 const U8 *fold_array;
4678 RX_MATCH_TAINTED_on(reginfo->prog);
4679 folder = foldEQ_locale;
4680 fold_array = PL_fold_locale;
4682 utf8_fold_flags = FOLDEQ_UTF8_LOCALE;
4685 case NREFFA: /* /\g{name}/iaa */
4686 folder = foldEQ_latin1;
4687 fold_array = PL_fold_latin1;
4689 utf8_fold_flags = FOLDEQ_UTF8_NOMIX_ASCII;
4692 case NREFFU: /* /\g{name}/iu */
4693 folder = foldEQ_latin1;
4694 fold_array = PL_fold_latin1;
4696 utf8_fold_flags = 0;
4699 case NREFF: /* /\g{name}/i */
4701 fold_array = PL_fold;
4703 utf8_fold_flags = 0;
4706 case NREF: /* /\g{name}/ */
4710 utf8_fold_flags = 0;
4713 /* For the named back references, find the corresponding buffer
4715 n = reg_check_named_buff_matched(rex,scan);
4720 goto do_nref_ref_common;
4722 case REFFL: /* /\1/il */
4723 RX_MATCH_TAINTED_on(reginfo->prog);
4724 folder = foldEQ_locale;
4725 fold_array = PL_fold_locale;
4726 utf8_fold_flags = FOLDEQ_UTF8_LOCALE;
4729 case REFFA: /* /\1/iaa */
4730 folder = foldEQ_latin1;
4731 fold_array = PL_fold_latin1;
4732 utf8_fold_flags = FOLDEQ_UTF8_NOMIX_ASCII;
4735 case REFFU: /* /\1/iu */
4736 folder = foldEQ_latin1;
4737 fold_array = PL_fold_latin1;
4738 utf8_fold_flags = 0;
4741 case REFF: /* /\1/i */
4743 fold_array = PL_fold;
4744 utf8_fold_flags = 0;
4747 case REF: /* /\1/ */
4750 utf8_fold_flags = 0;
4754 n = ARG(scan); /* which paren pair */
4757 ln = rex->offs[n].start;
4758 PL_reg_leftiter = PL_reg_maxiter; /* Void cache */
4759 if (rex->lastparen < n || ln == -1)
4760 sayNO; /* Do not match unless seen CLOSEn. */
4761 if (ln == rex->offs[n].end)
4765 if (type != REF /* REF can do byte comparison */
4766 && (utf8_target || type == REFFU))
4767 { /* XXX handle REFFL better */
4768 char * limit = PL_regeol;
4770 /* This call case insensitively compares the entire buffer
4771 * at s, with the current input starting at locinput, but
4772 * not going off the end given by PL_regeol, and returns in
4773 * <limit> upon success, how much of the current input was
4775 if (! foldEQ_utf8_flags(s, NULL, rex->offs[n].end - ln, utf8_target,
4776 locinput, &limit, 0, utf8_target, utf8_fold_flags))
4784 /* Not utf8: Inline the first character, for speed. */
4785 if (!NEXTCHR_IS_EOS &&
4786 UCHARAT(s) != nextchr &&
4788 UCHARAT(s) != fold_array[nextchr]))
4790 ln = rex->offs[n].end - ln;
4791 if (locinput + ln > PL_regeol)
4793 if (ln > 1 && (type == REF
4794 ? memNE(s, locinput, ln)
4795 : ! folder(s, locinput, ln)))
4801 case NOTHING: /* null op; e.g. the 'nothing' following
4802 * the '*' in m{(a+|b)*}' */
4804 case TAIL: /* placeholder while compiling (A|B|C) */
4807 case BACK: /* ??? doesn't appear to be used ??? */
4811 #define ST st->u.eval
4816 regexp_internal *rei;
4817 regnode *startpoint;
4819 case GOSTART: /* (?R) */
4820 case GOSUB: /* /(...(?1))/ /(...(?&foo))/ */
4821 if (cur_eval && cur_eval->locinput==locinput) {
4822 if (cur_eval->u.eval.close_paren == (U32)ARG(scan))
4823 Perl_croak(aTHX_ "Infinite recursion in regex");
4824 if ( ++nochange_depth > max_nochange_depth )
4826 "Pattern subroutine nesting without pos change"
4827 " exceeded limit in regex");
4834 if (OP(scan)==GOSUB) {
4835 startpoint = scan + ARG2L(scan);
4836 ST.close_paren = ARG(scan);
4838 startpoint = rei->program+1;
4841 goto eval_recurse_doit;
4842 assert(0); /* NOTREACHED */
4844 case EVAL: /* /(?{A})B/ /(??{A})B/ and /(?(?{A})X|Y)B/ */
4845 if (cur_eval && cur_eval->locinput==locinput) {
4846 if ( ++nochange_depth > max_nochange_depth )
4847 Perl_croak(aTHX_ "EVAL without pos change exceeded limit in regex");
4852 /* execute the code in the {...} */
4856 OP * const oop = PL_op;
4857 COP * const ocurcop = PL_curcop;
4859 char *saved_regeol = PL_regeol;
4860 struct re_save_state saved_state;
4863 /* save *all* paren positions */
4864 regcppush(rex, 0, maxopenparen);
4865 REGCP_SET(runops_cp);
4867 /* To not corrupt the existing regex state while executing the
4868 * eval we would normally put it on the save stack, like with
4869 * save_re_context. However, re-evals have a weird scoping so we
4870 * can't just add ENTER/LEAVE here. With that, things like
4872 * (?{$a=2})(a(?{local$a=$a+1}))*aak*c(?{$b=$a})
4874 * would break, as they expect the localisation to be unwound
4875 * only when the re-engine backtracks through the bit that
4878 * What we do instead is just saving the state in a local c
4881 Copy(&PL_reg_state, &saved_state, 1, struct re_save_state);
4883 PL_reg_state.re_reparsing = FALSE;
4886 caller_cv = find_runcv(NULL);
4890 if (rexi->data->what[n] == 'r') { /* code from an external qr */
4892 (REGEXP*)(rexi->data->data[n])
4895 nop = (OP*)rexi->data->data[n+1];
4897 else if (rexi->data->what[n] == 'l') { /* literal code */
4899 nop = (OP*)rexi->data->data[n];
4900 assert(CvDEPTH(newcv));
4903 /* literal with own CV */
4904 assert(rexi->data->what[n] == 'L');
4905 newcv = rex->qr_anoncv;
4906 nop = (OP*)rexi->data->data[n];
4909 /* normally if we're about to execute code from the same
4910 * CV that we used previously, we just use the existing
4911 * CX stack entry. However, its possible that in the
4912 * meantime we may have backtracked, popped from the save
4913 * stack, and undone the SAVECOMPPAD(s) associated with
4914 * PUSH_MULTICALL; in which case PL_comppad no longer
4915 * points to newcv's pad. */
4916 if (newcv != last_pushed_cv || PL_comppad != last_pad)
4918 I32 depth = (newcv == caller_cv) ? 0 : 1;
4919 if (last_pushed_cv) {
4920 CHANGE_MULTICALL_WITHDEPTH(newcv, depth);
4923 PUSH_MULTICALL_WITHDEPTH(newcv, depth);
4925 last_pushed_cv = newcv;
4928 /* these assignments are just to silence compiler
4930 multicall_cop = NULL;
4933 last_pad = PL_comppad;
4935 /* the initial nextstate you would normally execute
4936 * at the start of an eval (which would cause error
4937 * messages to come from the eval), may be optimised
4938 * away from the execution path in the regex code blocks;
4939 * so manually set PL_curcop to it initially */
4941 OP *o = cUNOPx(nop)->op_first;
4942 assert(o->op_type == OP_NULL);
4943 if (o->op_targ == OP_SCOPE) {
4944 o = cUNOPo->op_first;
4947 assert(o->op_targ == OP_LEAVE);
4948 o = cUNOPo->op_first;
4949 assert(o->op_type == OP_ENTER);
4953 if (o->op_type != OP_STUB) {
4954 assert( o->op_type == OP_NEXTSTATE
4955 || o->op_type == OP_DBSTATE
4956 || (o->op_type == OP_NULL
4957 && ( o->op_targ == OP_NEXTSTATE
4958 || o->op_targ == OP_DBSTATE
4962 PL_curcop = (COP*)o;
4967 DEBUG_STATE_r( PerlIO_printf(Perl_debug_log,
4968 " re EVAL PL_op=0x%"UVxf"\n", PTR2UV(nop)) );
4970 rex->offs[0].end = PL_reg_magic->mg_len = locinput - PL_bostr;
4973 SV *sv_mrk = get_sv("REGMARK", 1);
4974 sv_setsv(sv_mrk, sv_yes_mark);
4977 /* we don't use MULTICALL here as we want to call the
4978 * first op of the block of interest, rather than the
4979 * first op of the sub */
4980 before = (IV)(SP-PL_stack_base);
4982 CALLRUNOPS(aTHX); /* Scalar context. */
4984 if ((IV)(SP-PL_stack_base) == before)
4985 ret = &PL_sv_undef; /* protect against empty (?{}) blocks. */
4991 /* before restoring everything, evaluate the returned
4992 * value, so that 'uninit' warnings don't use the wrong
4993 * PL_op or pad. Also need to process any magic vars
4994 * (e.g. $1) *before* parentheses are restored */
4999 if (logical == 0) /* (?{})/ */
5000 sv_setsv(save_scalar(PL_replgv), ret); /* $^R */
5001 else if (logical == 1) { /* /(?(?{...})X|Y)/ */
5002 sw = cBOOL(SvTRUE(ret));
5005 else { /* /(??{}) */
5006 /* if its overloaded, let the regex compiler handle
5007 * it; otherwise extract regex, or stringify */
5008 if (!SvAMAGIC(ret)) {
5012 if (SvTYPE(sv) == SVt_REGEXP)
5013 re_sv = (REGEXP*) sv;
5014 else if (SvSMAGICAL(sv)) {
5015 MAGIC *mg = mg_find(sv, PERL_MAGIC_qr);
5017 re_sv = (REGEXP *) mg->mg_obj;
5020 /* force any magic, undef warnings here */
5022 ret = sv_mortalcopy(ret);
5023 (void) SvPV_force_nolen(ret);
5029 Copy(&saved_state, &PL_reg_state, 1, struct re_save_state);
5031 /* *** Note that at this point we don't restore
5032 * PL_comppad, (or pop the CxSUB) on the assumption it may
5033 * be used again soon. This is safe as long as nothing
5034 * in the regexp code uses the pad ! */
5036 PL_curcop = ocurcop;
5037 PL_regeol = saved_regeol;
5038 S_regcp_restore(aTHX_ rex, runops_cp, &maxopenparen);
5044 /* only /(??{})/ from now on */
5047 /* extract RE object from returned value; compiling if
5051 re_sv = reg_temp_copy(NULL, re_sv);
5056 if (SvUTF8(ret) && IN_BYTES) {
5057 /* In use 'bytes': make a copy of the octet
5058 * sequence, but without the flag on */
5060 const char *const p = SvPV(ret, len);
5061 ret = newSVpvn_flags(p, len, SVs_TEMP);
5063 if (rex->intflags & PREGf_USE_RE_EVAL)
5064 pm_flags |= PMf_USE_RE_EVAL;
5066 /* if we got here, it should be an engine which
5067 * supports compiling code blocks and stuff */
5068 assert(rex->engine && rex->engine->op_comp);
5069 assert(!(scan->flags & ~RXf_PMf_COMPILETIME));
5070 re_sv = rex->engine->op_comp(aTHX_ &ret, 1, NULL,
5071 rex->engine, NULL, NULL,
5072 /* copy /msix etc to inner pattern */
5077 & (SVs_TEMP | SVs_PADTMP | SVf_READONLY
5079 /* This isn't a first class regexp. Instead, it's
5080 caching a regexp onto an existing, Perl visible
5082 sv_magic(ret, MUTABLE_SV(re_sv), PERL_MAGIC_qr, 0, 0);
5084 /* safe to do now that any $1 etc has been
5085 * interpolated into the new pattern string and
5087 S_regcp_restore(aTHX_ rex, runops_cp, &maxopenparen);
5092 RXp_MATCH_COPIED_off(re);
5093 re->subbeg = rex->subbeg;
5094 re->sublen = rex->sublen;
5095 re->suboffset = rex->suboffset;
5096 re->subcoffset = rex->subcoffset;
5099 debug_start_match(re_sv, utf8_target, locinput, PL_regeol,
5100 "Matching embedded");
5102 startpoint = rei->program + 1;
5103 ST.close_paren = 0; /* only used for GOSUB */
5105 eval_recurse_doit: /* Share code with GOSUB below this line */
5106 /* run the pattern returned from (??{...}) */
5108 /* Save *all* the positions. */
5109 ST.cp = regcppush(rex, 0, maxopenparen);
5110 REGCP_SET(ST.lastcp);
5113 re->lastcloseparen = 0;
5117 /* XXXX This is too dramatic a measure... */
5120 ST.saved_utf8_pat = is_utf8_pat;
5121 is_utf8_pat = cBOOL(RX_UTF8(re_sv));
5123 ST.prev_rex = rex_sv;
5124 ST.prev_curlyx = cur_curlyx;
5126 SET_reg_curpm(rex_sv);
5131 ST.prev_eval = cur_eval;
5133 /* now continue from first node in postoned RE */
5134 PUSH_YES_STATE_GOTO(EVAL_AB, startpoint, locinput);
5135 assert(0); /* NOTREACHED */
5138 case EVAL_AB: /* cleanup after a successful (??{A})B */
5139 /* note: this is called twice; first after popping B, then A */
5140 is_utf8_pat = ST.saved_utf8_pat;
5141 rex_sv = ST.prev_rex;
5142 SET_reg_curpm(rex_sv);
5143 rex = ReANY(rex_sv);
5144 rexi = RXi_GET(rex);
5146 cur_eval = ST.prev_eval;
5147 cur_curlyx = ST.prev_curlyx;
5149 /* XXXX This is too dramatic a measure... */
5151 if ( nochange_depth )
5156 case EVAL_AB_fail: /* unsuccessfully ran A or B in (??{A})B */
5157 /* note: this is called twice; first after popping B, then A */
5158 is_utf8_pat = ST.saved_utf8_pat;
5159 rex_sv = ST.prev_rex;
5160 SET_reg_curpm(rex_sv);
5161 rex = ReANY(rex_sv);
5162 rexi = RXi_GET(rex);
5164 REGCP_UNWIND(ST.lastcp);
5165 regcppop(rex, &maxopenparen);
5166 cur_eval = ST.prev_eval;
5167 cur_curlyx = ST.prev_curlyx;
5168 /* XXXX This is too dramatic a measure... */
5170 if ( nochange_depth )
5176 n = ARG(scan); /* which paren pair */
5177 rex->offs[n].start_tmp = locinput - PL_bostr;
5178 if (n > maxopenparen)
5180 DEBUG_BUFFERS_r(PerlIO_printf(Perl_debug_log,
5181 "rex=0x%"UVxf" offs=0x%"UVxf": \\%"UVuf": set %"IVdf" tmp; maxopenparen=%"UVuf"\n",
5185 (IV)rex->offs[n].start_tmp,
5191 /* XXX really need to log other places start/end are set too */
5192 #define CLOSE_CAPTURE \
5193 rex->offs[n].start = rex->offs[n].start_tmp; \
5194 rex->offs[n].end = locinput - PL_bostr; \
5195 DEBUG_BUFFERS_r(PerlIO_printf(Perl_debug_log, \
5196 "rex=0x%"UVxf" offs=0x%"UVxf": \\%"UVuf": set %"IVdf"..%"IVdf"\n", \
5198 PTR2UV(rex->offs), \
5200 (IV)rex->offs[n].start, \
5201 (IV)rex->offs[n].end \
5205 n = ARG(scan); /* which paren pair */
5207 if (n > rex->lastparen)
5209 rex->lastcloseparen = n;
5210 if (cur_eval && cur_eval->u.eval.close_paren == n) {
5215 case ACCEPT: /* (*ACCEPT) */
5219 cursor && OP(cursor)!=END;
5220 cursor=regnext(cursor))
5222 if ( OP(cursor)==CLOSE ){
5224 if ( n <= lastopen ) {
5226 if (n > rex->lastparen)
5228 rex->lastcloseparen = n;
5229 if ( n == ARG(scan) || (cur_eval &&
5230 cur_eval->u.eval.close_paren == n))
5239 case GROUPP: /* (?(1)) */
5240 n = ARG(scan); /* which paren pair */
5241 sw = cBOOL(rex->lastparen >= n && rex->offs[n].end != -1);
5244 case NGROUPP: /* (?(<name>)) */
5245 /* reg_check_named_buff_matched returns 0 for no match */
5246 sw = cBOOL(0 < reg_check_named_buff_matched(rex,scan));
5249 case INSUBP: /* (?(R)) */
5251 sw = (cur_eval && (!n || cur_eval->u.eval.close_paren == n));
5254 case DEFINEP: /* (?(DEFINE)) */
5258 case IFTHEN: /* (?(cond)A|B) */
5259 PL_reg_leftiter = PL_reg_maxiter; /* Void cache */
5261 next = NEXTOPER(NEXTOPER(scan));
5263 next = scan + ARG(scan);
5264 if (OP(next) == IFTHEN) /* Fake one. */
5265 next = NEXTOPER(NEXTOPER(next));
5269 case LOGICAL: /* modifier for EVAL and IFMATCH */
5270 logical = scan->flags;
5273 /*******************************************************************
5275 The CURLYX/WHILEM pair of ops handle the most generic case of the /A*B/
5276 pattern, where A and B are subpatterns. (For simple A, CURLYM or
5277 STAR/PLUS/CURLY/CURLYN are used instead.)
5279 A*B is compiled as <CURLYX><A><WHILEM><B>
5281 On entry to the subpattern, CURLYX is called. This pushes a CURLYX
5282 state, which contains the current count, initialised to -1. It also sets
5283 cur_curlyx to point to this state, with any previous value saved in the
5286 CURLYX then jumps straight to the WHILEM op, rather than executing A,
5287 since the pattern may possibly match zero times (i.e. it's a while {} loop
5288 rather than a do {} while loop).
5290 Each entry to WHILEM represents a successful match of A. The count in the
5291 CURLYX block is incremented, another WHILEM state is pushed, and execution
5292 passes to A or B depending on greediness and the current count.
5294 For example, if matching against the string a1a2a3b (where the aN are
5295 substrings that match /A/), then the match progresses as follows: (the
5296 pushed states are interspersed with the bits of strings matched so far):
5299 <CURLYX cnt=0><WHILEM>
5300 <CURLYX cnt=1><WHILEM> a1 <WHILEM>
5301 <CURLYX cnt=2><WHILEM> a1 <WHILEM> a2 <WHILEM>
5302 <CURLYX cnt=3><WHILEM> a1 <WHILEM> a2 <WHILEM> a3 <WHILEM>
5303 <CURLYX cnt=3><WHILEM> a1 <WHILEM> a2 <WHILEM> a3 <WHILEM> b
5305 (Contrast this with something like CURLYM, which maintains only a single
5309 a1 <CURLYM cnt=1> a2
5310 a1 a2 <CURLYM cnt=2> a3
5311 a1 a2 a3 <CURLYM cnt=3> b
5314 Each WHILEM state block marks a point to backtrack to upon partial failure
5315 of A or B, and also contains some minor state data related to that
5316 iteration. The CURLYX block, pointed to by cur_curlyx, contains the
5317 overall state, such as the count, and pointers to the A and B ops.
5319 This is complicated slightly by nested CURLYX/WHILEM's. Since cur_curlyx
5320 must always point to the *current* CURLYX block, the rules are:
5322 When executing CURLYX, save the old cur_curlyx in the CURLYX state block,
5323 and set cur_curlyx to point the new block.
5325 When popping the CURLYX block after a successful or unsuccessful match,
5326 restore the previous cur_curlyx.
5328 When WHILEM is about to execute B, save the current cur_curlyx, and set it
5329 to the outer one saved in the CURLYX block.
5331 When popping the WHILEM block after a successful or unsuccessful B match,
5332 restore the previous cur_curlyx.
5334 Here's an example for the pattern (AI* BI)*BO
5335 I and O refer to inner and outer, C and W refer to CURLYX and WHILEM:
5338 curlyx backtrack stack
5339 ------ ---------------
5341 CO <CO prev=NULL> <WO>
5342 CI <CO prev=NULL> <WO> <CI prev=CO> <WI> ai
5343 CO <CO prev=NULL> <WO> <CI prev=CO> <WI> ai <WI prev=CI> bi
5344 NULL <CO prev=NULL> <WO> <CI prev=CO> <WI> ai <WI prev=CI> bi <WO prev=CO> bo
5346 At this point the pattern succeeds, and we work back down the stack to
5347 clean up, restoring as we go:
5349 CO <CO prev=NULL> <WO> <CI prev=CO> <WI> ai <WI prev=CI> bi
5350 CI <CO prev=NULL> <WO> <CI prev=CO> <WI> ai
5351 CO <CO prev=NULL> <WO>
5354 *******************************************************************/
5356 #define ST st->u.curlyx
5358 case CURLYX: /* start of /A*B/ (for complex A) */
5360 /* No need to save/restore up to this paren */
5361 I32 parenfloor = scan->flags;
5363 assert(next); /* keep Coverity happy */
5364 if (OP(PREVOPER(next)) == NOTHING) /* LONGJMP */
5367 /* XXXX Probably it is better to teach regpush to support
5368 parenfloor > maxopenparen ... */
5369 if (parenfloor > (I32)rex->lastparen)
5370 parenfloor = rex->lastparen; /* Pessimization... */
5372 ST.prev_curlyx= cur_curlyx;
5374 ST.cp = PL_savestack_ix;
5376 /* these fields contain the state of the current curly.
5377 * they are accessed by subsequent WHILEMs */
5378 ST.parenfloor = parenfloor;
5383 ST.count = -1; /* this will be updated by WHILEM */
5384 ST.lastloc = NULL; /* this will be updated by WHILEM */
5386 PUSH_YES_STATE_GOTO(CURLYX_end, PREVOPER(next), locinput);
5387 assert(0); /* NOTREACHED */
5390 case CURLYX_end: /* just finished matching all of A*B */
5391 cur_curlyx = ST.prev_curlyx;
5393 assert(0); /* NOTREACHED */
5395 case CURLYX_end_fail: /* just failed to match all of A*B */
5397 cur_curlyx = ST.prev_curlyx;
5399 assert(0); /* NOTREACHED */
5403 #define ST st->u.whilem
5405 case WHILEM: /* just matched an A in /A*B/ (for complex A) */
5407 /* see the discussion above about CURLYX/WHILEM */
5409 int min = ARG1(cur_curlyx->u.curlyx.me);
5410 int max = ARG2(cur_curlyx->u.curlyx.me);
5411 regnode *A = NEXTOPER(cur_curlyx->u.curlyx.me) + EXTRA_STEP_2ARGS;
5413 assert(cur_curlyx); /* keep Coverity happy */
5414 n = ++cur_curlyx->u.curlyx.count; /* how many A's matched */
5415 ST.save_lastloc = cur_curlyx->u.curlyx.lastloc;
5416 ST.cache_offset = 0;
5420 DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log,
5421 "%*s whilem: matched %ld out of %d..%d\n",
5422 REPORT_CODE_OFF+depth*2, "", (long)n, min, max)
5425 /* First just match a string of min A's. */
5428 ST.cp = regcppush(rex, cur_curlyx->u.curlyx.parenfloor,
5430 cur_curlyx->u.curlyx.lastloc = locinput;
5431 REGCP_SET(ST.lastcp);
5433 PUSH_STATE_GOTO(WHILEM_A_pre, A, locinput);
5434 assert(0); /* NOTREACHED */
5437 /* If degenerate A matches "", assume A done. */
5439 if (locinput == cur_curlyx->u.curlyx.lastloc) {
5440 DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log,
5441 "%*s whilem: empty match detected, trying continuation...\n",
5442 REPORT_CODE_OFF+depth*2, "")
5444 goto do_whilem_B_max;
5447 /* super-linear cache processing */
5451 if (!PL_reg_maxiter) {
5452 /* start the countdown: Postpone detection until we
5453 * know the match is not *that* much linear. */
5454 PL_reg_maxiter = (PL_regeol - PL_bostr + 1) * (scan->flags>>4);
5455 /* possible overflow for long strings and many CURLYX's */
5456 if (PL_reg_maxiter < 0)
5457 PL_reg_maxiter = I32_MAX;
5458 PL_reg_leftiter = PL_reg_maxiter;
5461 if (PL_reg_leftiter-- == 0) {
5462 /* initialise cache */
5463 const I32 size = (PL_reg_maxiter + 7)/8;
5464 if (PL_reg_poscache) {
5465 if ((I32)PL_reg_poscache_size < size) {
5466 Renew(PL_reg_poscache, size, char);
5467 PL_reg_poscache_size = size;
5469 Zero(PL_reg_poscache, size, char);
5472 PL_reg_poscache_size = size;
5473 Newxz(PL_reg_poscache, size, char);
5475 DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log,
5476 "%swhilem: Detected a super-linear match, switching on caching%s...\n",
5477 PL_colors[4], PL_colors[5])
5481 if (PL_reg_leftiter < 0) {
5482 /* have we already failed at this position? */
5484 offset = (scan->flags & 0xf) - 1
5485 + (locinput - PL_bostr) * (scan->flags>>4);
5486 mask = 1 << (offset % 8);
5488 if (PL_reg_poscache[offset] & mask) {
5489 DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log,
5490 "%*s whilem: (cache) already tried at this position...\n",
5491 REPORT_CODE_OFF+depth*2, "")
5493 sayNO; /* cache records failure */
5495 ST.cache_offset = offset;
5496 ST.cache_mask = mask;
5500 /* Prefer B over A for minimal matching. */
5502 if (cur_curlyx->u.curlyx.minmod) {
5503 ST.save_curlyx = cur_curlyx;
5504 cur_curlyx = cur_curlyx->u.curlyx.prev_curlyx;
5505 ST.cp = regcppush(rex, ST.save_curlyx->u.curlyx.parenfloor,
5507 REGCP_SET(ST.lastcp);
5508 PUSH_YES_STATE_GOTO(WHILEM_B_min, ST.save_curlyx->u.curlyx.B,
5510 assert(0); /* NOTREACHED */
5513 /* Prefer A over B for maximal matching. */
5515 if (n < max) { /* More greed allowed? */
5516 ST.cp = regcppush(rex, cur_curlyx->u.curlyx.parenfloor,
5518 cur_curlyx->u.curlyx.lastloc = locinput;
5519 REGCP_SET(ST.lastcp);
5520 PUSH_STATE_GOTO(WHILEM_A_max, A, locinput);
5521 assert(0); /* NOTREACHED */
5523 goto do_whilem_B_max;
5525 assert(0); /* NOTREACHED */
5527 case WHILEM_B_min: /* just matched B in a minimal match */
5528 case WHILEM_B_max: /* just matched B in a maximal match */
5529 cur_curlyx = ST.save_curlyx;
5531 assert(0); /* NOTREACHED */
5533 case WHILEM_B_max_fail: /* just failed to match B in a maximal match */
5534 cur_curlyx = ST.save_curlyx;
5535 cur_curlyx->u.curlyx.lastloc = ST.save_lastloc;
5536 cur_curlyx->u.curlyx.count--;
5538 assert(0); /* NOTREACHED */
5540 case WHILEM_A_min_fail: /* just failed to match A in a minimal match */
5542 case WHILEM_A_pre_fail: /* just failed to match even minimal A */
5543 REGCP_UNWIND(ST.lastcp);
5544 regcppop(rex, &maxopenparen);
5545 cur_curlyx->u.curlyx.lastloc = ST.save_lastloc;
5546 cur_curlyx->u.curlyx.count--;
5548 assert(0); /* NOTREACHED */
5550 case WHILEM_A_max_fail: /* just failed to match A in a maximal match */
5551 REGCP_UNWIND(ST.lastcp);
5552 regcppop(rex, &maxopenparen); /* Restore some previous $<digit>s? */
5553 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
5554 "%*s whilem: failed, trying continuation...\n",
5555 REPORT_CODE_OFF+depth*2, "")
5558 if (cur_curlyx->u.curlyx.count >= REG_INFTY
5559 && ckWARN(WARN_REGEXP)
5560 && !reginfo->warned)
5562 reginfo->warned = TRUE;
5563 Perl_warner(aTHX_ packWARN(WARN_REGEXP),
5564 "Complex regular subexpression recursion limit (%d) "
5570 ST.save_curlyx = cur_curlyx;
5571 cur_curlyx = cur_curlyx->u.curlyx.prev_curlyx;
5572 PUSH_YES_STATE_GOTO(WHILEM_B_max, ST.save_curlyx->u.curlyx.B,
5574 assert(0); /* NOTREACHED */
5576 case WHILEM_B_min_fail: /* just failed to match B in a minimal match */
5577 cur_curlyx = ST.save_curlyx;
5578 REGCP_UNWIND(ST.lastcp);
5579 regcppop(rex, &maxopenparen);
5581 if (cur_curlyx->u.curlyx.count >= /*max*/ARG2(cur_curlyx->u.curlyx.me)) {
5582 /* Maximum greed exceeded */
5583 if (cur_curlyx->u.curlyx.count >= REG_INFTY
5584 && ckWARN(WARN_REGEXP)
5585 && !reginfo->warned)
5587 reginfo->warned = TRUE;
5588 Perl_warner(aTHX_ packWARN(WARN_REGEXP),
5589 "Complex regular subexpression recursion "
5590 "limit (%d) exceeded",
5593 cur_curlyx->u.curlyx.count--;
5597 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
5598 "%*s trying longer...\n", REPORT_CODE_OFF+depth*2, "")
5600 /* Try grabbing another A and see if it helps. */
5601 cur_curlyx->u.curlyx.lastloc = locinput;
5602 ST.cp = regcppush(rex, cur_curlyx->u.curlyx.parenfloor,
5604 REGCP_SET(ST.lastcp);
5605 PUSH_STATE_GOTO(WHILEM_A_min,
5606 /*A*/ NEXTOPER(ST.save_curlyx->u.curlyx.me) + EXTRA_STEP_2ARGS,
5608 assert(0); /* NOTREACHED */
5611 #define ST st->u.branch
5613 case BRANCHJ: /* /(...|A|...)/ with long next pointer */
5614 next = scan + ARG(scan);
5617 scan = NEXTOPER(scan);
5620 case BRANCH: /* /(...|A|...)/ */
5621 scan = NEXTOPER(scan); /* scan now points to inner node */
5622 ST.lastparen = rex->lastparen;
5623 ST.lastcloseparen = rex->lastcloseparen;
5624 ST.next_branch = next;
5627 /* Now go into the branch */
5629 PUSH_YES_STATE_GOTO(BRANCH_next, scan, locinput);
5631 PUSH_STATE_GOTO(BRANCH_next, scan, locinput);
5633 assert(0); /* NOTREACHED */
5635 case CUTGROUP: /* /(*THEN)/ */
5636 sv_yes_mark = st->u.mark.mark_name = scan->flags ? NULL :
5637 MUTABLE_SV(rexi->data->data[ ARG( scan ) ]);
5638 PUSH_STATE_GOTO(CUTGROUP_next, next, locinput);
5639 assert(0); /* NOTREACHED */
5641 case CUTGROUP_next_fail:
5644 if (st->u.mark.mark_name)
5645 sv_commit = st->u.mark.mark_name;
5647 assert(0); /* NOTREACHED */
5651 assert(0); /* NOTREACHED */
5653 case BRANCH_next_fail: /* that branch failed; try the next, if any */
5658 REGCP_UNWIND(ST.cp);
5659 UNWIND_PAREN(ST.lastparen, ST.lastcloseparen);
5660 scan = ST.next_branch;
5661 /* no more branches? */
5662 if (!scan || (OP(scan) != BRANCH && OP(scan) != BRANCHJ)) {
5664 PerlIO_printf( Perl_debug_log,
5665 "%*s %sBRANCH failed...%s\n",
5666 REPORT_CODE_OFF+depth*2, "",
5672 continue; /* execute next BRANCH[J] op */
5673 assert(0); /* NOTREACHED */
5675 case MINMOD: /* next op will be non-greedy, e.g. A*? */
5680 #define ST st->u.curlym
5682 case CURLYM: /* /A{m,n}B/ where A is fixed-length */
5684 /* This is an optimisation of CURLYX that enables us to push
5685 * only a single backtracking state, no matter how many matches
5686 * there are in {m,n}. It relies on the pattern being constant
5687 * length, with no parens to influence future backrefs
5691 scan = NEXTOPER(scan) + NODE_STEP_REGNODE;
5693 ST.lastparen = rex->lastparen;
5694 ST.lastcloseparen = rex->lastcloseparen;
5696 /* if paren positive, emulate an OPEN/CLOSE around A */
5698 U32 paren = ST.me->flags;
5699 if (paren > maxopenparen)
5700 maxopenparen = paren;
5701 scan += NEXT_OFF(scan); /* Skip former OPEN. */
5709 ST.c1 = CHRTEST_UNINIT;
5712 if (!(ST.minmod ? ARG1(ST.me) : ARG2(ST.me))) /* min/max */
5715 curlym_do_A: /* execute the A in /A{m,n}B/ */
5716 PUSH_YES_STATE_GOTO(CURLYM_A, ST.A, locinput); /* match A */
5717 assert(0); /* NOTREACHED */
5719 case CURLYM_A: /* we've just matched an A */
5721 /* after first match, determine A's length: u.curlym.alen */
5722 if (ST.count == 1) {
5723 if (PL_reg_match_utf8) {
5724 char *s = st->locinput;
5725 while (s < locinput) {
5731 ST.alen = locinput - st->locinput;
5734 ST.count = ST.minmod ? ARG1(ST.me) : ARG2(ST.me);
5737 PerlIO_printf(Perl_debug_log,
5738 "%*s CURLYM now matched %"IVdf" times, len=%"IVdf"...\n",
5739 (int)(REPORT_CODE_OFF+(depth*2)), "",
5740 (IV) ST.count, (IV)ST.alen)
5743 if (cur_eval && cur_eval->u.eval.close_paren &&
5744 cur_eval->u.eval.close_paren == (U32)ST.me->flags)
5748 I32 max = (ST.minmod ? ARG1(ST.me) : ARG2(ST.me));
5749 if ( max == REG_INFTY || ST.count < max )
5750 goto curlym_do_A; /* try to match another A */
5752 goto curlym_do_B; /* try to match B */
5754 case CURLYM_A_fail: /* just failed to match an A */
5755 REGCP_UNWIND(ST.cp);
5757 if (ST.minmod || ST.count < ARG1(ST.me) /* min*/
5758 || (cur_eval && cur_eval->u.eval.close_paren &&
5759 cur_eval->u.eval.close_paren == (U32)ST.me->flags))
5762 curlym_do_B: /* execute the B in /A{m,n}B/ */
5763 if (ST.c1 == CHRTEST_UNINIT) {
5764 /* calculate c1 and c2 for possible match of 1st char
5765 * following curly */
5766 ST.c1 = ST.c2 = CHRTEST_VOID;
5767 if (HAS_TEXT(ST.B) || JUMPABLE(ST.B)) {
5768 regnode *text_node = ST.B;
5769 if (! HAS_TEXT(text_node))
5770 FIND_NEXT_IMPT(text_node);
5773 (HAS_TEXT(text_node) && PL_regkind[OP(text_node)] == EXACT)
5775 But the former is redundant in light of the latter.
5777 if this changes back then the macro for
5778 IS_TEXT and friends need to change.
5780 if (PL_regkind[OP(text_node)] == EXACT) {
5781 if (! S_setup_EXACTISH_ST_c1_c2(aTHX_
5782 text_node, &ST.c1, ST.c1_utf8, &ST.c2, ST.c2_utf8,
5792 PerlIO_printf(Perl_debug_log,
5793 "%*s CURLYM trying tail with matches=%"IVdf"...\n",
5794 (int)(REPORT_CODE_OFF+(depth*2)),
5797 if (! NEXTCHR_IS_EOS && ST.c1 != CHRTEST_VOID) {
5798 if (! UTF8_IS_INVARIANT(nextchr) && utf8_target) {
5799 if (memNE(locinput, ST.c1_utf8, UTF8SKIP(locinput))
5800 && memNE(locinput, ST.c2_utf8, UTF8SKIP(locinput)))
5802 /* simulate B failing */
5804 PerlIO_printf(Perl_debug_log,
5805 "%*s CURLYM Fast bail next target=U+%"UVXf" c1=U+%"UVXf" c2=U+%"UVXf"\n",
5806 (int)(REPORT_CODE_OFF+(depth*2)),"",
5807 valid_utf8_to_uvchr((U8 *) locinput, NULL),
5808 valid_utf8_to_uvchr(ST.c1_utf8, NULL),
5809 valid_utf8_to_uvchr(ST.c2_utf8, NULL))
5811 state_num = CURLYM_B_fail;
5812 goto reenter_switch;
5815 else if (nextchr != ST.c1 && nextchr != ST.c2) {
5816 /* simulate B failing */
5818 PerlIO_printf(Perl_debug_log,
5819 "%*s CURLYM Fast bail next target=U+%X c1=U+%X c2=U+%X\n",
5820 (int)(REPORT_CODE_OFF+(depth*2)),"",
5821 (int) nextchr, ST.c1, ST.c2)
5823 state_num = CURLYM_B_fail;
5824 goto reenter_switch;
5829 /* emulate CLOSE: mark current A as captured */
5830 I32 paren = ST.me->flags;
5832 rex->offs[paren].start
5833 = HOPc(locinput, -ST.alen) - PL_bostr;
5834 rex->offs[paren].end = locinput - PL_bostr;
5835 if ((U32)paren > rex->lastparen)
5836 rex->lastparen = paren;
5837 rex->lastcloseparen = paren;
5840 rex->offs[paren].end = -1;
5841 if (cur_eval && cur_eval->u.eval.close_paren &&
5842 cur_eval->u.eval.close_paren == (U32)ST.me->flags)
5851 PUSH_STATE_GOTO(CURLYM_B, ST.B, locinput); /* match B */
5852 assert(0); /* NOTREACHED */
5854 case CURLYM_B_fail: /* just failed to match a B */
5855 REGCP_UNWIND(ST.cp);
5856 UNWIND_PAREN(ST.lastparen, ST.lastcloseparen);
5858 I32 max = ARG2(ST.me);
5859 if (max != REG_INFTY && ST.count == max)
5861 goto curlym_do_A; /* try to match a further A */
5863 /* backtrack one A */
5864 if (ST.count == ARG1(ST.me) /* min */)
5867 SET_locinput(HOPc(locinput, -ST.alen));
5868 goto curlym_do_B; /* try to match B */
5871 #define ST st->u.curly
5873 #define CURLY_SETPAREN(paren, success) \
5876 rex->offs[paren].start = HOPc(locinput, -1) - PL_bostr; \
5877 rex->offs[paren].end = locinput - PL_bostr; \
5878 if (paren > rex->lastparen) \
5879 rex->lastparen = paren; \
5880 rex->lastcloseparen = paren; \
5883 rex->offs[paren].end = -1; \
5884 rex->lastparen = ST.lastparen; \
5885 rex->lastcloseparen = ST.lastcloseparen; \
5889 case STAR: /* /A*B/ where A is width 1 char */
5893 scan = NEXTOPER(scan);
5896 case PLUS: /* /A+B/ where A is width 1 char */
5900 scan = NEXTOPER(scan);
5903 case CURLYN: /* /(A){m,n}B/ where A is width 1 char */
5904 ST.paren = scan->flags; /* Which paren to set */
5905 ST.lastparen = rex->lastparen;
5906 ST.lastcloseparen = rex->lastcloseparen;
5907 if (ST.paren > maxopenparen)
5908 maxopenparen = ST.paren;
5909 ST.min = ARG1(scan); /* min to match */
5910 ST.max = ARG2(scan); /* max to match */
5911 if (cur_eval && cur_eval->u.eval.close_paren &&
5912 cur_eval->u.eval.close_paren == (U32)ST.paren) {
5916 scan = regnext(NEXTOPER(scan) + NODE_STEP_REGNODE);
5919 case CURLY: /* /A{m,n}B/ where A is width 1 char */
5921 ST.min = ARG1(scan); /* min to match */
5922 ST.max = ARG2(scan); /* max to match */
5923 scan = NEXTOPER(scan) + NODE_STEP_REGNODE;
5926 * Lookahead to avoid useless match attempts
5927 * when we know what character comes next.
5929 * Used to only do .*x and .*?x, but now it allows
5930 * for )'s, ('s and (?{ ... })'s to be in the way
5931 * of the quantifier and the EXACT-like node. -- japhy
5934 assert(ST.min <= ST.max);
5935 if (! HAS_TEXT(next) && ! JUMPABLE(next)) {
5936 ST.c1 = ST.c2 = CHRTEST_VOID;
5939 regnode *text_node = next;
5941 if (! HAS_TEXT(text_node))
5942 FIND_NEXT_IMPT(text_node);
5944 if (! HAS_TEXT(text_node))
5945 ST.c1 = ST.c2 = CHRTEST_VOID;
5947 if ( PL_regkind[OP(text_node)] != EXACT ) {
5948 ST.c1 = ST.c2 = CHRTEST_VOID;
5952 /* Currently we only get here when
5954 PL_rekind[OP(text_node)] == EXACT
5956 if this changes back then the macro for IS_TEXT and
5957 friends need to change. */
5958 if (! S_setup_EXACTISH_ST_c1_c2(aTHX_
5959 text_node, &ST.c1, ST.c1_utf8, &ST.c2, ST.c2_utf8,
5971 char *li = locinput;
5974 regrepeat(rex, &li, ST.A, ST.min, depth, is_utf8_pat)
5980 if (ST.c1 == CHRTEST_VOID)
5981 goto curly_try_B_min;
5983 ST.oldloc = locinput;
5985 /* set ST.maxpos to the furthest point along the
5986 * string that could possibly match */
5987 if (ST.max == REG_INFTY) {
5988 ST.maxpos = PL_regeol - 1;
5990 while (UTF8_IS_CONTINUATION(*(U8*)ST.maxpos))
5993 else if (utf8_target) {
5994 int m = ST.max - ST.min;
5995 for (ST.maxpos = locinput;
5996 m >0 && ST.maxpos < PL_regeol; m--)
5997 ST.maxpos += UTF8SKIP(ST.maxpos);
6000 ST.maxpos = locinput + ST.max - ST.min;
6001 if (ST.maxpos >= PL_regeol)
6002 ST.maxpos = PL_regeol - 1;
6004 goto curly_try_B_min_known;
6008 /* avoid taking address of locinput, so it can remain
6010 char *li = locinput;
6011 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, is_utf8_pat) < 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, is_utf8_pat)) {
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.saved_utf8_pat = is_utf8_pat;
6196 is_utf8_pat = cur_eval->u.eval.saved_utf8_pat;
6198 st->u.eval.prev_rex = rex_sv; /* inner */
6200 /* Save *all* the positions. */
6201 st->u.eval.cp = regcppush(rex, 0, maxopenparen);
6202 rex_sv = cur_eval->u.eval.prev_rex;
6203 SET_reg_curpm(rex_sv);
6204 rex = ReANY(rex_sv);
6205 rexi = RXi_GET(rex);
6206 cur_curlyx = cur_eval->u.eval.prev_curlyx;
6208 REGCP_SET(st->u.eval.lastcp);
6210 /* Restore parens of the outer rex without popping the
6212 S_regcp_restore(aTHX_ rex, cur_eval->u.eval.lastcp,
6215 st->u.eval.prev_eval = cur_eval;
6216 cur_eval = cur_eval->u.eval.prev_eval;
6218 PerlIO_printf(Perl_debug_log, "%*s EVAL trying tail ... %"UVxf"\n",
6219 REPORT_CODE_OFF+depth*2, "",PTR2UV(cur_eval)););
6220 if ( nochange_depth )
6223 PUSH_YES_STATE_GOTO(EVAL_AB, st->u.eval.prev_eval->u.eval.B,
6224 locinput); /* match B */
6227 if (locinput < reginfo->till) {
6228 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
6229 "%sMatch possible, but length=%ld is smaller than requested=%ld, failing!%s\n",
6231 (long)(locinput - PL_reg_starttry),
6232 (long)(reginfo->till - PL_reg_starttry),
6235 sayNO_SILENT; /* Cannot match: too short. */
6237 sayYES; /* Success! */
6239 case SUCCEED: /* successful SUSPEND/UNLESSM/IFMATCH/CURLYM */
6241 PerlIO_printf(Perl_debug_log,
6242 "%*s %ssubpattern success...%s\n",
6243 REPORT_CODE_OFF+depth*2, "", PL_colors[4], PL_colors[5]));
6244 sayYES; /* Success! */
6247 #define ST st->u.ifmatch
6252 case SUSPEND: /* (?>A) */
6254 newstart = locinput;
6257 case UNLESSM: /* -ve lookaround: (?!A), or with flags, (?<!A) */
6259 goto ifmatch_trivial_fail_test;
6261 case IFMATCH: /* +ve lookaround: (?=A), or with flags, (?<=A) */
6263 ifmatch_trivial_fail_test:
6265 char * const s = HOPBACKc(locinput, scan->flags);
6270 sw = 1 - cBOOL(ST.wanted);
6274 next = scan + ARG(scan);
6282 newstart = locinput;
6286 ST.logical = logical;
6287 logical = 0; /* XXX: reset state of logical once it has been saved into ST */
6289 /* execute body of (?...A) */
6290 PUSH_YES_STATE_GOTO(IFMATCH_A, NEXTOPER(NEXTOPER(scan)), newstart);
6291 assert(0); /* NOTREACHED */
6294 case IFMATCH_A_fail: /* body of (?...A) failed */
6295 ST.wanted = !ST.wanted;
6298 case IFMATCH_A: /* body of (?...A) succeeded */
6300 sw = cBOOL(ST.wanted);
6302 else if (!ST.wanted)
6305 if (OP(ST.me) != SUSPEND) {
6306 /* restore old position except for (?>...) */
6307 locinput = st->locinput;
6309 scan = ST.me + ARG(ST.me);
6312 continue; /* execute B */
6316 case LONGJMP: /* alternative with many branches compiles to
6317 * (BRANCHJ; EXACT ...; LONGJMP ) x N */
6318 next = scan + ARG(scan);
6323 case COMMIT: /* (*COMMIT) */
6324 reginfo->cutpoint = PL_regeol;
6327 case PRUNE: /* (*PRUNE) */
6329 sv_yes_mark = sv_commit = MUTABLE_SV(rexi->data->data[ ARG( scan ) ]);
6330 PUSH_STATE_GOTO(COMMIT_next, next, locinput);
6331 assert(0); /* NOTREACHED */
6333 case COMMIT_next_fail:
6337 case OPFAIL: /* (*FAIL) */
6339 assert(0); /* NOTREACHED */
6341 #define ST st->u.mark
6342 case MARKPOINT: /* (*MARK:foo) */
6343 ST.prev_mark = mark_state;
6344 ST.mark_name = sv_commit = sv_yes_mark
6345 = MUTABLE_SV(rexi->data->data[ ARG( scan ) ]);
6347 ST.mark_loc = locinput;
6348 PUSH_YES_STATE_GOTO(MARKPOINT_next, next, locinput);
6349 assert(0); /* NOTREACHED */
6351 case MARKPOINT_next:
6352 mark_state = ST.prev_mark;
6354 assert(0); /* NOTREACHED */
6356 case MARKPOINT_next_fail:
6357 if (popmark && sv_eq(ST.mark_name,popmark))
6359 if (ST.mark_loc > startpoint)
6360 reginfo->cutpoint = HOPBACKc(ST.mark_loc, 1);
6361 popmark = NULL; /* we found our mark */
6362 sv_commit = ST.mark_name;
6365 PerlIO_printf(Perl_debug_log,
6366 "%*s %ssetting cutpoint to mark:%"SVf"...%s\n",
6367 REPORT_CODE_OFF+depth*2, "",
6368 PL_colors[4], SVfARG(sv_commit), PL_colors[5]);
6371 mark_state = ST.prev_mark;
6372 sv_yes_mark = mark_state ?
6373 mark_state->u.mark.mark_name : NULL;
6375 assert(0); /* NOTREACHED */
6377 case SKIP: /* (*SKIP) */
6379 /* (*SKIP) : if we fail we cut here*/
6380 ST.mark_name = NULL;
6381 ST.mark_loc = locinput;
6382 PUSH_STATE_GOTO(SKIP_next,next, locinput);
6384 /* (*SKIP:NAME) : if there is a (*MARK:NAME) fail where it was,
6385 otherwise do nothing. Meaning we need to scan
6387 regmatch_state *cur = mark_state;
6388 SV *find = MUTABLE_SV(rexi->data->data[ ARG( scan ) ]);
6391 if ( sv_eq( cur->u.mark.mark_name,
6394 ST.mark_name = find;
6395 PUSH_STATE_GOTO( SKIP_next, next, locinput);
6397 cur = cur->u.mark.prev_mark;
6400 /* Didn't find our (*MARK:NAME) so ignore this (*SKIP:NAME) */
6403 case SKIP_next_fail:
6405 /* (*CUT:NAME) - Set up to search for the name as we
6406 collapse the stack*/
6407 popmark = ST.mark_name;
6409 /* (*CUT) - No name, we cut here.*/
6410 if (ST.mark_loc > startpoint)
6411 reginfo->cutpoint = HOPBACKc(ST.mark_loc, 1);
6412 /* but we set sv_commit to latest mark_name if there
6413 is one so they can test to see how things lead to this
6416 sv_commit=mark_state->u.mark.mark_name;
6420 assert(0); /* NOTREACHED */
6423 case LNBREAK: /* \R */
6424 if ((n=is_LNBREAK_safe(locinput, PL_regeol, utf8_target))) {
6431 PerlIO_printf(Perl_error_log, "%"UVxf" %d\n",
6432 PTR2UV(scan), OP(scan));
6433 Perl_croak(aTHX_ "regexp memory corruption");
6435 /* this is a point to jump to in order to increment
6436 * locinput by one character */
6438 assert(!NEXTCHR_IS_EOS);
6440 locinput += PL_utf8skip[nextchr];
6441 /* locinput is allowed to go 1 char off the end, but not 2+ */
6442 if (locinput > PL_regeol)
6451 /* switch break jumps here */
6452 scan = next; /* prepare to execute the next op and ... */
6453 continue; /* ... jump back to the top, reusing st */
6454 assert(0); /* NOTREACHED */
6457 /* push a state that backtracks on success */
6458 st->u.yes.prev_yes_state = yes_state;
6462 /* push a new regex state, then continue at scan */
6464 regmatch_state *newst;
6467 regmatch_state *cur = st;
6468 regmatch_state *curyes = yes_state;
6470 regmatch_slab *slab = PL_regmatch_slab;
6471 for (;curd > -1;cur--,curd--) {
6472 if (cur < SLAB_FIRST(slab)) {
6474 cur = SLAB_LAST(slab);
6476 PerlIO_printf(Perl_error_log, "%*s#%-3d %-10s %s\n",
6477 REPORT_CODE_OFF + 2 + depth * 2,"",
6478 curd, PL_reg_name[cur->resume_state],
6479 (curyes == cur) ? "yes" : ""
6482 curyes = cur->u.yes.prev_yes_state;
6485 DEBUG_STATE_pp("push")
6488 st->locinput = locinput;
6490 if (newst > SLAB_LAST(PL_regmatch_slab))
6491 newst = S_push_slab(aTHX);
6492 PL_regmatch_state = newst;
6494 locinput = pushinput;
6497 assert(0); /* NOTREACHED */
6502 * We get here only if there's trouble -- normally "case END" is
6503 * the terminating point.
6505 Perl_croak(aTHX_ "corrupted regexp pointers");
6511 /* we have successfully completed a subexpression, but we must now
6512 * pop to the state marked by yes_state and continue from there */
6513 assert(st != yes_state);
6515 while (st != yes_state) {
6517 if (st < SLAB_FIRST(PL_regmatch_slab)) {
6518 PL_regmatch_slab = PL_regmatch_slab->prev;
6519 st = SLAB_LAST(PL_regmatch_slab);
6523 DEBUG_STATE_pp("pop (no final)");
6525 DEBUG_STATE_pp("pop (yes)");
6531 while (yes_state < SLAB_FIRST(PL_regmatch_slab)
6532 || yes_state > SLAB_LAST(PL_regmatch_slab))
6534 /* not in this slab, pop slab */
6535 depth -= (st - SLAB_FIRST(PL_regmatch_slab) + 1);
6536 PL_regmatch_slab = PL_regmatch_slab->prev;
6537 st = SLAB_LAST(PL_regmatch_slab);
6539 depth -= (st - yes_state);
6542 yes_state = st->u.yes.prev_yes_state;
6543 PL_regmatch_state = st;
6546 locinput= st->locinput;
6547 state_num = st->resume_state + no_final;
6548 goto reenter_switch;
6551 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "%sMatch successful!%s\n",
6552 PL_colors[4], PL_colors[5]));
6554 if (PL_reg_state.re_state_eval_setup_done) {
6555 /* each successfully executed (?{...}) block does the equivalent of
6556 * local $^R = do {...}
6557 * When popping the save stack, all these locals would be undone;
6558 * bypass this by setting the outermost saved $^R to the latest
6560 if (oreplsv != GvSV(PL_replgv))
6561 sv_setsv(oreplsv, GvSV(PL_replgv));
6568 PerlIO_printf(Perl_debug_log,
6569 "%*s %sfailed...%s\n",
6570 REPORT_CODE_OFF+depth*2, "",
6571 PL_colors[4], PL_colors[5])
6583 /* there's a previous state to backtrack to */
6585 if (st < SLAB_FIRST(PL_regmatch_slab)) {
6586 PL_regmatch_slab = PL_regmatch_slab->prev;
6587 st = SLAB_LAST(PL_regmatch_slab);
6589 PL_regmatch_state = st;
6590 locinput= st->locinput;
6592 DEBUG_STATE_pp("pop");
6594 if (yes_state == st)
6595 yes_state = st->u.yes.prev_yes_state;
6597 state_num = st->resume_state + 1; /* failure = success + 1 */
6598 goto reenter_switch;
6603 if (rex->intflags & PREGf_VERBARG_SEEN) {
6604 SV *sv_err = get_sv("REGERROR", 1);
6605 SV *sv_mrk = get_sv("REGMARK", 1);
6607 sv_commit = &PL_sv_no;
6609 sv_yes_mark = &PL_sv_yes;
6612 sv_commit = &PL_sv_yes;
6613 sv_yes_mark = &PL_sv_no;
6615 sv_setsv(sv_err, sv_commit);
6616 sv_setsv(sv_mrk, sv_yes_mark);
6620 if (last_pushed_cv) {
6623 PERL_UNUSED_VAR(SP);
6626 /* clean up; in particular, free all slabs above current one */
6627 LEAVE_SCOPE(oldsave);
6629 assert(!result || locinput - PL_bostr >= 0);
6630 return result ? locinput - PL_bostr : -1;
6634 - regrepeat - repeatedly match something simple, report how many
6636 * What 'simple' means is a node which can be the operand of a quantifier like
6639 * startposp - pointer a pointer to the start position. This is updated
6640 * to point to the byte following the highest successful
6642 * p - the regnode to be repeatedly matched against.
6643 * max - maximum number of things to match.
6644 * depth - (for debugging) backtracking depth.
6647 S_regrepeat(pTHX_ regexp *prog, char **startposp, const regnode *p,
6648 I32 max, int depth, bool is_utf8_pat)
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) == is_utf8_pat ? 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 && ! is_utf8_pat)) {
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 (is_utf8_pat) {
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 RXp_MATCH_TAINTED_on(prog);
6797 utf8_flags = FOLDEQ_UTF8_LOCALE;
6805 case EXACTFU_TRICKYFOLD:
6807 utf8_flags = is_utf8_pat ? FOLDEQ_S2_ALREADY_FOLDED : 0;
6811 U8 c1_utf8[UTF8_MAXBYTES+1], c2_utf8[UTF8_MAXBYTES+1];
6813 assert(STR_LEN(p) == is_utf8_pat ? UTF8SKIP(STRING(p)) : 1);
6815 if (S_setup_EXACTISH_ST_c1_c2(aTHX_ p, &c1, c1_utf8, &c2, c2_utf8,
6818 if (c1 == CHRTEST_VOID) {
6819 /* Use full Unicode fold matching */
6820 char *tmpeol = PL_regeol;
6821 STRLEN pat_len = is_utf8_pat ? UTF8SKIP(STRING(p)) : 1;
6822 while (hardcount < max
6823 && foldEQ_utf8_flags(scan, &tmpeol, 0, utf8_target,
6824 STRING(p), NULL, pat_len,
6825 is_utf8_pat, utf8_flags))
6832 else if (utf8_target) {
6834 while (scan < loceol
6836 && memEQ(scan, c1_utf8, UTF8SKIP(scan)))
6838 scan += UTF8SKIP(scan);
6843 while (scan < loceol
6845 && (memEQ(scan, c1_utf8, UTF8SKIP(scan))
6846 || memEQ(scan, c2_utf8, UTF8SKIP(scan))))
6848 scan += UTF8SKIP(scan);
6853 else if (c1 == c2) {
6854 while (scan < loceol && UCHARAT(scan) == c1) {
6859 while (scan < loceol &&
6860 (UCHARAT(scan) == c1 || UCHARAT(scan) == c2))
6869 case ANYOF_WARN_SUPER:
6871 while (hardcount < max
6873 && reginclass(prog, p, (U8*)scan, utf8_target))
6875 scan += UTF8SKIP(scan);
6879 while (scan < loceol && REGINCLASS(prog, p, (U8*)scan))
6884 /* The argument (FLAGS) to all the POSIX node types is the class number */
6891 RXp_MATCH_TAINTED_on(prog);
6892 if (! utf8_target) {
6893 while (scan < loceol && to_complement ^ cBOOL(isFOO_lc(FLAGS(p),
6899 while (hardcount < max && scan < loceol
6900 && to_complement ^ cBOOL(isFOO_utf8_lc(FLAGS(p),
6903 scan += UTF8SKIP(scan);
6916 if (utf8_target && scan + max < loceol) {
6918 /* We didn't adjust <loceol> at the beginning of this routine
6919 * because is UTF-8, but it is actually ok to do so, since here, to
6920 * match, 1 char == 1 byte. */
6921 loceol = scan + max;
6923 while (scan < loceol && _generic_isCC_A((U8) *scan, FLAGS(p))) {
6936 if (! utf8_target) {
6937 while (scan < loceol && ! _generic_isCC_A((U8) *scan, FLAGS(p))) {
6943 /* The complement of something that matches only ASCII matches all
6944 * UTF-8 variant code points, plus everything in ASCII that isn't
6946 while (hardcount < max && scan < loceol
6947 && (! UTF8_IS_INVARIANT(*scan)
6948 || ! _generic_isCC_A((U8) *scan, FLAGS(p))))
6950 scan += UTF8SKIP(scan);
6961 if (! utf8_target) {
6962 while (scan < loceol && to_complement
6963 ^ cBOOL(_generic_isCC((U8) *scan, FLAGS(p))))
6970 classnum = (_char_class_number) FLAGS(p);
6971 if (classnum < _FIRST_NON_SWASH_CC) {
6973 /* Here, a swash is needed for above-Latin1 code points.
6974 * Process as many Latin1 code points using the built-in rules.
6975 * Go to another loop to finish processing upon encountering
6976 * the first Latin1 code point. We could do that in this loop
6977 * as well, but the other way saves having to test if the swash
6978 * has been loaded every time through the loop: extra space to
6980 while (hardcount < max && scan < loceol) {
6981 if (UTF8_IS_INVARIANT(*scan)) {
6982 if (! (to_complement ^ cBOOL(_generic_isCC((U8) *scan,
6989 else if (UTF8_IS_DOWNGRADEABLE_START(*scan)) {
6990 if (! (to_complement
6991 ^ cBOOL(_generic_isCC(TWO_BYTE_UTF8_TO_UNI(*scan,
7000 goto found_above_latin1;
7007 /* For these character classes, the knowledge of how to handle
7008 * every code point is compiled in to Perl via a macro. This
7009 * code is written for making the loops as tight as possible.
7010 * It could be refactored to save space instead */
7012 case _CC_ENUM_SPACE: /* XXX would require separate code
7013 if we revert the change of \v
7016 case _CC_ENUM_PSXSPC:
7017 while (hardcount < max
7019 && (to_complement ^ cBOOL(isSPACE_utf8(scan))))
7021 scan += UTF8SKIP(scan);
7025 case _CC_ENUM_BLANK:
7026 while (hardcount < max
7028 && (to_complement ^ cBOOL(isBLANK_utf8(scan))))
7030 scan += UTF8SKIP(scan);
7034 case _CC_ENUM_XDIGIT:
7035 while (hardcount < max
7037 && (to_complement ^ cBOOL(isXDIGIT_utf8(scan))))
7039 scan += UTF8SKIP(scan);
7043 case _CC_ENUM_VERTSPACE:
7044 while (hardcount < max
7046 && (to_complement ^ cBOOL(isVERTWS_utf8(scan))))
7048 scan += UTF8SKIP(scan);
7052 case _CC_ENUM_CNTRL:
7053 while (hardcount < max
7055 && (to_complement ^ cBOOL(isCNTRL_utf8(scan))))
7057 scan += UTF8SKIP(scan);
7062 Perl_croak(aTHX_ "panic: regrepeat() node %d='%s' has an unexpected character class '%d'", OP(p), PL_reg_name[OP(p)], classnum);
7068 found_above_latin1: /* Continuation of POSIXU and NPOSIXU */
7070 /* Load the swash if not already present */
7071 if (! PL_utf8_swash_ptrs[classnum]) {
7072 U8 flags = _CORE_SWASH_INIT_ACCEPT_INVLIST;
7073 PL_utf8_swash_ptrs[classnum] = _core_swash_init(
7074 "utf8", swash_property_names[classnum],
7075 &PL_sv_undef, 1, 0, NULL, &flags);
7078 while (hardcount < max && scan < loceol
7079 && to_complement ^ cBOOL(_generic_utf8(
7082 swash_fetch(PL_utf8_swash_ptrs[classnum],
7086 scan += UTF8SKIP(scan);
7093 while (hardcount < max && scan < loceol &&
7094 (c=is_LNBREAK_utf8_safe(scan, loceol))) {
7099 /* LNBREAK can match one or two latin chars, which is ok, but we
7100 * have to use hardcount in this situation, and throw away the
7101 * adjustment to <loceol> done before the switch statement */
7103 while (scan < loceol && (c=is_LNBREAK_latin1_safe(scan, loceol))) {
7124 /* These are all 0 width, so match right here or not at all. */
7128 Perl_croak(aTHX_ "panic: regrepeat() called with unrecognized node type %d='%s'", OP(p), PL_reg_name[OP(p)]);
7129 assert(0); /* NOTREACHED */
7136 c = scan - *startposp;
7140 GET_RE_DEBUG_FLAGS_DECL;
7142 SV * const prop = sv_newmortal();
7143 regprop(prog, prop, p);
7144 PerlIO_printf(Perl_debug_log,
7145 "%*s %s can match %"IVdf" times out of %"IVdf"...\n",
7146 REPORT_CODE_OFF + depth*2, "", SvPVX_const(prop),(IV)c,(IV)max);
7154 #if !defined(PERL_IN_XSUB_RE) || defined(PLUGGABLE_RE_EXTENSION)
7156 - regclass_swash - prepare the utf8 swash. Wraps the shared core version to
7157 create a copy so that changes the caller makes won't change the shared one.
7158 If <altsvp> is non-null, will return NULL in it, for back-compat.
7161 Perl_regclass_swash(pTHX_ const regexp *prog, const regnode* node, bool doinit, SV** listsvp, SV **altsvp)
7163 PERL_ARGS_ASSERT_REGCLASS_SWASH;
7169 return newSVsv(core_regclass_swash(prog, node, doinit, listsvp));
7174 S_core_regclass_swash(pTHX_ const regexp *prog, const regnode* node, bool doinit, SV** listsvp)
7176 /* Returns the swash for the input 'node' in the regex 'prog'.
7177 * If <doinit> is true, will attempt to create the swash if not already
7179 * If <listsvp> is non-null, will return the swash initialization string in
7181 * Tied intimately to how regcomp.c sets up the data structure */
7188 RXi_GET_DECL(prog,progi);
7189 const struct reg_data * const data = prog ? progi->data : NULL;
7191 PERL_ARGS_ASSERT_CORE_REGCLASS_SWASH;
7193 assert(ANYOF_NONBITMAP(node));
7195 if (data && data->count) {
7196 const U32 n = ARG(node);
7198 if (data->what[n] == 's') {
7199 SV * const rv = MUTABLE_SV(data->data[n]);
7200 AV * const av = MUTABLE_AV(SvRV(rv));
7201 SV **const ary = AvARRAY(av);
7202 U8 swash_init_flags = _CORE_SWASH_INIT_ACCEPT_INVLIST;
7204 si = *ary; /* ary[0] = the string to initialize the swash with */
7206 /* Elements 2 and 3 are either both present or both absent. [2] is
7207 * any inversion list generated at compile time; [3] indicates if
7208 * that inversion list has any user-defined properties in it. */
7209 if (av_len(av) >= 2) {
7212 swash_init_flags |= _CORE_SWASH_INIT_USER_DEFINED_PROPERTY;
7219 /* Element [1] is reserved for the set-up swash. If already there,
7220 * return it; if not, create it and store it there */
7221 if (SvROK(ary[1])) {
7224 else if (si && doinit) {
7226 sw = _core_swash_init("utf8", /* the utf8 package */
7230 0, /* not from tr/// */
7233 (void)av_store(av, 1, sw);
7239 SV* matches_string = newSVpvn("", 0);
7241 /* Use the swash, if any, which has to have incorporated into it all
7243 if ((! sw || (invlist = _get_swash_invlist(sw)) == NULL)
7244 && (si && si != &PL_sv_undef))
7247 /* If no swash, use the input initialization string, if available */
7248 sv_catsv(matches_string, si);
7251 /* Add the inversion list to whatever we have. This may have come from
7252 * the swash, or from an input parameter */
7254 sv_catsv(matches_string, _invlist_contents(invlist));
7256 *listsvp = matches_string;
7263 - reginclass - determine if a character falls into a character class
7265 n is the ANYOF regnode
7266 p is the target string
7267 utf8_target tells whether p is in UTF-8.
7269 Returns true if matched; false otherwise.
7271 Note that this can be a synthetic start class, a combination of various
7272 nodes, so things you think might be mutually exclusive, such as locale,
7273 aren't. It can match both locale and non-locale
7278 S_reginclass(pTHX_ regexp * const prog, const regnode * const n, const U8* const p, const bool utf8_target)
7281 const char flags = ANYOF_FLAGS(n);
7285 PERL_ARGS_ASSERT_REGINCLASS;
7287 /* If c is not already the code point, get it. Note that
7288 * UTF8_IS_INVARIANT() works even if not in UTF-8 */
7289 if (! UTF8_IS_INVARIANT(c) && utf8_target) {
7291 c = utf8n_to_uvchr(p, UTF8_MAXBYTES, &c_len,
7292 (UTF8_ALLOW_DEFAULT & UTF8_ALLOW_ANYUV)
7293 | UTF8_ALLOW_FFFF | UTF8_CHECK_ONLY);
7294 /* see [perl #37836] for UTF8_ALLOW_ANYUV; [perl #38293] for
7295 * UTF8_ALLOW_FFFF */
7296 if (c_len == (STRLEN)-1)
7297 Perl_croak(aTHX_ "Malformed UTF-8 character (fatal)");
7300 /* If this character is potentially in the bitmap, check it */
7302 if (ANYOF_BITMAP_TEST(n, c))
7304 else if (flags & ANYOF_NON_UTF8_LATIN1_ALL
7310 else if (flags & ANYOF_LOCALE) {
7311 RXp_MATCH_TAINTED_on(prog);
7313 if ((flags & ANYOF_LOC_FOLD)
7314 && ANYOF_BITMAP_TEST(n, PL_fold_locale[c]))
7318 else if (ANYOF_CLASS_TEST_ANY_SET(n)) {
7320 /* The data structure is arranged so bits 0, 2, 4, ... are set
7321 * if the class includes the Posix character class given by
7322 * bit/2; and 1, 3, 5, ... are set if the class includes the
7323 * complemented Posix class given by int(bit/2). So we loop
7324 * through the bits, each time changing whether we complement
7325 * the result or not. Suppose for the sake of illustration
7326 * that bits 0-3 mean respectively, \w, \W, \s, \S. If bit 0
7327 * is set, it means there is a match for this ANYOF node if the
7328 * character is in the class given by the expression (0 / 2 = 0
7329 * = \w). If it is in that class, isFOO_lc() will return 1,
7330 * and since 'to_complement' is 0, the result will stay TRUE,
7331 * and we exit the loop. Suppose instead that bit 0 is 0, but
7332 * bit 1 is 1. That means there is a match if the character
7333 * matches \W. We won't bother to call isFOO_lc() on bit 0,
7334 * but will on bit 1. On the second iteration 'to_complement'
7335 * will be 1, so the exclusive or will reverse things, so we
7336 * are testing for \W. On the third iteration, 'to_complement'
7337 * will be 0, and we would be testing for \s; the fourth
7338 * iteration would test for \S, etc.
7340 * Note that this code assumes that all the classes are closed
7341 * under folding. For example, if a character matches \w, then
7342 * its fold does too; and vice versa. This should be true for
7343 * any well-behaved locale for all the currently defined Posix
7344 * classes, except for :lower: and :upper:, which are handled
7345 * by the pseudo-class :cased: which matches if either of the
7346 * other two does. To get rid of this assumption, an outer
7347 * loop could be used below to iterate over both the source
7348 * character, and its fold (if different) */
7351 int to_complement = 0;
7352 while (count < ANYOF_MAX) {
7353 if (ANYOF_CLASS_TEST(n, count)
7354 && to_complement ^ cBOOL(isFOO_lc(count/2, (U8) c)))
7366 /* If the bitmap didn't (or couldn't) match, and something outside the
7367 * bitmap could match, try that. Locale nodes specify completely the
7368 * behavior of code points in the bit map (otherwise, a utf8 target would
7369 * cause them to be treated as Unicode and not locale), except in
7370 * the very unlikely event when this node is a synthetic start class, which
7371 * could be a combination of locale and non-locale nodes. So allow locale
7372 * to match for the synthetic start class, which will give a false
7373 * positive that will be resolved when the match is done again as not part
7374 * of the synthetic start class */
7376 if (utf8_target && (flags & ANYOF_UNICODE_ALL) && c >= 256) {
7377 match = TRUE; /* Everything above 255 matches */
7379 else if (ANYOF_NONBITMAP(n)
7380 && ((flags & ANYOF_NONBITMAP_NON_UTF8)
7383 || (! (flags & ANYOF_LOCALE))
7384 || OP(n) == ANYOF_SYNTHETIC))))
7386 SV * const sw = core_regclass_swash(prog, n, TRUE, 0);
7391 } else { /* Convert to utf8 */
7393 utf8_p = bytes_to_utf8(p, &len);
7396 if (swash_fetch(sw, utf8_p, TRUE)) {
7400 /* If we allocated a string above, free it */
7401 if (! utf8_target) Safefree(utf8_p);
7405 if (UNICODE_IS_SUPER(c)
7406 && OP(n) == ANYOF_WARN_SUPER
7407 && ckWARN_d(WARN_NON_UNICODE))
7409 Perl_warner(aTHX_ packWARN(WARN_NON_UNICODE),
7410 "Code point 0x%04"UVXf" is not Unicode, all \\p{} matches fail; all \\P{} matches succeed", c);
7414 /* The xor complements the return if to invert: 1^1 = 0, 1^0 = 1 */
7415 return cBOOL(flags & ANYOF_INVERT) ^ match;
7419 S_reghop3(U8 *s, I32 off, const U8* lim)
7421 /* return the position 'off' UTF-8 characters away from 's', forward if
7422 * 'off' >= 0, backwards if negative. But don't go outside of position
7423 * 'lim', which better be < s if off < 0 */
7427 PERL_ARGS_ASSERT_REGHOP3;
7430 while (off-- && s < lim) {
7431 /* XXX could check well-formedness here */
7436 while (off++ && s > lim) {
7438 if (UTF8_IS_CONTINUED(*s)) {
7439 while (s > lim && UTF8_IS_CONTINUATION(*s))
7442 /* XXX could check well-formedness here */
7449 /* there are a bunch of places where we use two reghop3's that should
7450 be replaced with this routine. but since thats not done yet
7451 we ifdef it out - dmq
7454 S_reghop4(U8 *s, I32 off, const U8* llim, const U8* rlim)
7458 PERL_ARGS_ASSERT_REGHOP4;
7461 while (off-- && s < rlim) {
7462 /* XXX could check well-formedness here */
7467 while (off++ && s > llim) {
7469 if (UTF8_IS_CONTINUED(*s)) {
7470 while (s > llim && UTF8_IS_CONTINUATION(*s))
7473 /* XXX could check well-formedness here */
7481 S_reghopmaybe3(U8* s, I32 off, const U8* lim)
7485 PERL_ARGS_ASSERT_REGHOPMAYBE3;
7488 while (off-- && s < lim) {
7489 /* XXX could check well-formedness here */
7496 while (off++ && s > lim) {
7498 if (UTF8_IS_CONTINUED(*s)) {
7499 while (s > lim && UTF8_IS_CONTINUATION(*s))
7502 /* XXX could check well-formedness here */
7511 restore_pos(pTHX_ void *arg)
7514 regexp * const rex = (regexp *)arg;
7515 if (PL_reg_state.re_state_eval_setup_done) {
7516 if (PL_reg_oldsaved) {
7517 rex->subbeg = PL_reg_oldsaved;
7518 rex->sublen = PL_reg_oldsavedlen;
7519 rex->suboffset = PL_reg_oldsavedoffset;
7520 rex->subcoffset = PL_reg_oldsavedcoffset;
7522 rex->saved_copy = PL_nrs;
7524 RXp_MATCH_COPIED_on(rex);
7526 PL_reg_magic->mg_len = PL_reg_oldpos;
7527 PL_reg_state.re_state_eval_setup_done = FALSE;
7528 PL_curpm = PL_reg_oldcurpm;
7533 S_to_utf8_substr(pTHX_ regexp *prog)
7535 /* Converts substr fields in prog from bytes to UTF-8, calling fbm_compile
7536 * on the converted value */
7540 PERL_ARGS_ASSERT_TO_UTF8_SUBSTR;
7543 if (prog->substrs->data[i].substr
7544 && !prog->substrs->data[i].utf8_substr) {
7545 SV* const sv = newSVsv(prog->substrs->data[i].substr);
7546 prog->substrs->data[i].utf8_substr = sv;
7547 sv_utf8_upgrade(sv);
7548 if (SvVALID(prog->substrs->data[i].substr)) {
7549 if (SvTAIL(prog->substrs->data[i].substr)) {
7550 /* Trim the trailing \n that fbm_compile added last
7552 SvCUR_set(sv, SvCUR(sv) - 1);
7553 /* Whilst this makes the SV technically "invalid" (as its
7554 buffer is no longer followed by "\0") when fbm_compile()
7555 adds the "\n" back, a "\0" is restored. */
7556 fbm_compile(sv, FBMcf_TAIL);
7560 if (prog->substrs->data[i].substr == prog->check_substr)
7561 prog->check_utf8 = sv;
7567 S_to_byte_substr(pTHX_ regexp *prog)
7569 /* Converts substr fields in prog from UTF-8 to bytes, calling fbm_compile
7570 * on the converted value; returns FALSE if can't be converted. */
7575 PERL_ARGS_ASSERT_TO_BYTE_SUBSTR;
7578 if (prog->substrs->data[i].utf8_substr
7579 && !prog->substrs->data[i].substr) {
7580 SV* sv = newSVsv(prog->substrs->data[i].utf8_substr);
7581 if (! sv_utf8_downgrade(sv, TRUE)) {
7584 if (SvVALID(prog->substrs->data[i].utf8_substr)) {
7585 if (SvTAIL(prog->substrs->data[i].utf8_substr)) {
7586 /* Trim the trailing \n that fbm_compile added last
7588 SvCUR_set(sv, SvCUR(sv) - 1);
7589 fbm_compile(sv, FBMcf_TAIL);
7593 prog->substrs->data[i].substr = sv;
7594 if (prog->substrs->data[i].utf8_substr == prog->check_utf8)
7595 prog->check_substr = sv;
7604 * c-indentation-style: bsd
7606 * indent-tabs-mode: nil
7609 * ex: set ts=8 sts=4 sw=4 et: