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) (reginfo->is_utf8_target ? utf8_distance(a,b) : a - b)
115 #define HOPc(pos,off) \
116 (char *)(reginfo->is_utf8_target \
117 ? reghop3((U8*)pos, off, \
118 (U8*)(off >= 0 ? reginfo->strend : reginfo->strbeg)) \
120 #define HOPBACKc(pos, off) \
121 (char*)(reginfo->is_utf8_target \
122 ? reghopmaybe3((U8*)pos, -off, (U8*)(reginfo->strbeg)) \
123 : (pos - off >= reginfo->strbeg) \
127 #define HOP3(pos,off,lim) (reginfo->is_utf8_target ? reghop3((U8*)(pos), off, (U8*)(lim)) : (U8*)(pos + off))
128 #define HOP3c(pos,off,lim) ((char*)HOP3(pos,off,lim))
131 #define NEXTCHR_EOS -10 /* nextchr has fallen off the end */
132 #define NEXTCHR_IS_EOS (nextchr < 0)
134 #define SET_nextchr \
135 nextchr = ((locinput < reginfo->strend) ? UCHARAT(locinput) : NEXTCHR_EOS)
137 #define SET_locinput(p) \
142 #define LOAD_UTF8_CHARCLASS(swash_ptr, property_name) STMT_START { \
144 U8 flags = _CORE_SWASH_INIT_ACCEPT_INVLIST; \
145 swash_ptr = _core_swash_init("utf8", property_name, &PL_sv_undef, \
146 1, 0, NULL, &flags); \
151 /* If in debug mode, we test that a known character properly matches */
153 # define LOAD_UTF8_CHARCLASS_DEBUG_TEST(swash_ptr, \
155 utf8_char_in_property) \
156 LOAD_UTF8_CHARCLASS(swash_ptr, property_name); \
157 assert(swash_fetch(swash_ptr, (U8 *) utf8_char_in_property, TRUE));
159 # define LOAD_UTF8_CHARCLASS_DEBUG_TEST(swash_ptr, \
161 utf8_char_in_property) \
162 LOAD_UTF8_CHARCLASS(swash_ptr, property_name)
165 #define LOAD_UTF8_CHARCLASS_ALNUM() LOAD_UTF8_CHARCLASS_DEBUG_TEST( \
166 PL_utf8_swash_ptrs[_CC_WORDCHAR], \
167 swash_property_names[_CC_WORDCHAR], \
168 GREEK_SMALL_LETTER_IOTA_UTF8)
170 #define LOAD_UTF8_CHARCLASS_GCB() /* Grapheme cluster boundaries */ \
172 LOAD_UTF8_CHARCLASS_DEBUG_TEST(PL_utf8_X_regular_begin, \
173 "_X_regular_begin", \
174 GREEK_SMALL_LETTER_IOTA_UTF8); \
175 LOAD_UTF8_CHARCLASS_DEBUG_TEST(PL_utf8_X_extend, \
177 COMBINING_GRAVE_ACCENT_UTF8); \
180 #define PLACEHOLDER /* Something for the preprocessor to grab onto */
181 /* TODO: Combine JUMPABLE and HAS_TEXT to cache OP(rn) */
183 /* for use after a quantifier and before an EXACT-like node -- japhy */
184 /* it would be nice to rework regcomp.sym to generate this stuff. sigh
186 * NOTE that *nothing* that affects backtracking should be in here, specifically
187 * VERBS must NOT be included. JUMPABLE is used to determine if we can ignore a
188 * node that is in between two EXACT like nodes when ascertaining what the required
189 * "follow" character is. This should probably be moved to regex compile time
190 * although it may be done at run time beause of the REF possibility - more
191 * investigation required. -- demerphq
193 #define JUMPABLE(rn) ( \
195 (OP(rn) == CLOSE && (!cur_eval || cur_eval->u.eval.close_paren != ARG(rn))) || \
197 OP(rn) == SUSPEND || OP(rn) == IFMATCH || \
198 OP(rn) == PLUS || OP(rn) == MINMOD || \
200 (PL_regkind[OP(rn)] == CURLY && ARG1(rn) > 0) \
202 #define IS_EXACT(rn) (PL_regkind[OP(rn)] == EXACT)
204 #define HAS_TEXT(rn) ( IS_EXACT(rn) || PL_regkind[OP(rn)] == REF )
207 /* Currently these are only used when PL_regkind[OP(rn)] == EXACT so
208 we don't need this definition. */
209 #define IS_TEXT(rn) ( OP(rn)==EXACT || OP(rn)==REF || OP(rn)==NREF )
210 #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 )
211 #define IS_TEXTFL(rn) ( OP(rn)==EXACTFL || OP(rn)==REFFL || OP(rn)==NREFFL )
214 /* ... so we use this as its faster. */
215 #define IS_TEXT(rn) ( OP(rn)==EXACT )
216 #define IS_TEXTFU(rn) ( OP(rn)==EXACTFU || OP(rn)==EXACTFU_SS || OP(rn)==EXACTFU_TRICKYFOLD || OP(rn) == EXACTFA)
217 #define IS_TEXTF(rn) ( OP(rn)==EXACTF )
218 #define IS_TEXTFL(rn) ( OP(rn)==EXACTFL )
223 Search for mandatory following text node; for lookahead, the text must
224 follow but for lookbehind (rn->flags != 0) we skip to the next step.
226 #define FIND_NEXT_IMPT(rn) STMT_START { \
227 while (JUMPABLE(rn)) { \
228 const OPCODE type = OP(rn); \
229 if (type == SUSPEND || PL_regkind[type] == CURLY) \
230 rn = NEXTOPER(NEXTOPER(rn)); \
231 else if (type == PLUS) \
233 else if (type == IFMATCH) \
234 rn = (rn->flags == 0) ? NEXTOPER(NEXTOPER(rn)) : rn + ARG(rn); \
235 else rn += NEXT_OFF(rn); \
239 /* These constants are for finding GCB=LV and GCB=LVT in the CLUMP regnode.
240 * These are for the pre-composed Hangul syllables, which are all in a
241 * contiguous block and arranged there in such a way so as to facilitate
242 * alorithmic determination of their characteristics. As such, they don't need
243 * a swash, but can be determined by simple arithmetic. Almost all are
244 * GCB=LVT, but every 28th one is a GCB=LV */
245 #define SBASE 0xAC00 /* Start of block */
246 #define SCount 11172 /* Length of block */
249 #define SLAB_FIRST(s) (&(s)->states[0])
250 #define SLAB_LAST(s) (&(s)->states[PERL_REGMATCH_SLAB_SLOTS-1])
252 static void S_setup_eval_state(pTHX_ regmatch_info *const reginfo);
253 static void S_cleanup_regmatch_info_aux(pTHX_ void *arg);
254 static regmatch_state * S_push_slab(pTHX);
256 #define REGCP_PAREN_ELEMS 3
257 #define REGCP_OTHER_ELEMS 3
258 #define REGCP_FRAME_ELEMS 1
259 /* REGCP_FRAME_ELEMS are not part of the REGCP_OTHER_ELEMS and
260 * are needed for the regexp context stack bookkeeping. */
263 S_regcppush(pTHX_ const regexp *rex, I32 parenfloor, U32 maxopenparen)
266 const int retval = PL_savestack_ix;
267 const int paren_elems_to_push =
268 (maxopenparen - parenfloor) * REGCP_PAREN_ELEMS;
269 const UV total_elems = paren_elems_to_push + REGCP_OTHER_ELEMS;
270 const UV elems_shifted = total_elems << SAVE_TIGHT_SHIFT;
272 GET_RE_DEBUG_FLAGS_DECL;
274 PERL_ARGS_ASSERT_REGCPPUSH;
276 if (paren_elems_to_push < 0)
277 Perl_croak(aTHX_ "panic: paren_elems_to_push, %i < 0",
278 paren_elems_to_push);
280 if ((elems_shifted >> SAVE_TIGHT_SHIFT) != total_elems)
281 Perl_croak(aTHX_ "panic: paren_elems_to_push offset %"UVuf
282 " out of range (%lu-%ld)",
284 (unsigned long)maxopenparen,
287 SSGROW(total_elems + REGCP_FRAME_ELEMS);
290 if ((int)maxopenparen > (int)parenfloor)
291 PerlIO_printf(Perl_debug_log,
292 "rex=0x%"UVxf" offs=0x%"UVxf": saving capture indices:\n",
297 for (p = parenfloor+1; p <= (I32)maxopenparen; p++) {
298 /* REGCP_PARENS_ELEMS are pushed per pairs of parentheses. */
299 SSPUSHINT(rex->offs[p].end);
300 SSPUSHINT(rex->offs[p].start);
301 SSPUSHINT(rex->offs[p].start_tmp);
302 DEBUG_BUFFERS_r(PerlIO_printf(Perl_debug_log,
303 " \\%"UVuf": %"IVdf"(%"IVdf")..%"IVdf"\n",
305 (IV)rex->offs[p].start,
306 (IV)rex->offs[p].start_tmp,
310 /* REGCP_OTHER_ELEMS are pushed in any case, parentheses or no. */
311 SSPUSHINT(maxopenparen);
312 SSPUSHINT(rex->lastparen);
313 SSPUSHINT(rex->lastcloseparen);
314 SSPUSHUV(SAVEt_REGCONTEXT | elems_shifted); /* Magic cookie. */
319 /* These are needed since we do not localize EVAL nodes: */
320 #define REGCP_SET(cp) \
322 PerlIO_printf(Perl_debug_log, \
323 " Setting an EVAL scope, savestack=%"IVdf"\n", \
324 (IV)PL_savestack_ix)); \
327 #define REGCP_UNWIND(cp) \
329 if (cp != PL_savestack_ix) \
330 PerlIO_printf(Perl_debug_log, \
331 " Clearing an EVAL scope, savestack=%"IVdf"..%"IVdf"\n", \
332 (IV)(cp), (IV)PL_savestack_ix)); \
335 #define UNWIND_PAREN(lp, lcp) \
336 for (n = rex->lastparen; n > lp; n--) \
337 rex->offs[n].end = -1; \
338 rex->lastparen = n; \
339 rex->lastcloseparen = lcp;
343 S_regcppop(pTHX_ regexp *rex, U32 *maxopenparen_p)
348 GET_RE_DEBUG_FLAGS_DECL;
350 PERL_ARGS_ASSERT_REGCPPOP;
352 /* Pop REGCP_OTHER_ELEMS before the parentheses loop starts. */
354 assert((i & SAVE_MASK) == SAVEt_REGCONTEXT); /* Check that the magic cookie is there. */
355 i >>= SAVE_TIGHT_SHIFT; /* Parentheses elements to pop. */
356 rex->lastcloseparen = SSPOPINT;
357 rex->lastparen = SSPOPINT;
358 *maxopenparen_p = SSPOPINT;
360 i -= REGCP_OTHER_ELEMS;
361 /* Now restore the parentheses context. */
363 if (i || rex->lastparen + 1 <= rex->nparens)
364 PerlIO_printf(Perl_debug_log,
365 "rex=0x%"UVxf" offs=0x%"UVxf": restoring capture indices to:\n",
370 paren = *maxopenparen_p;
371 for ( ; i > 0; i -= REGCP_PAREN_ELEMS) {
373 rex->offs[paren].start_tmp = SSPOPINT;
374 rex->offs[paren].start = SSPOPINT;
376 if (paren <= rex->lastparen)
377 rex->offs[paren].end = tmps;
378 DEBUG_BUFFERS_r( PerlIO_printf(Perl_debug_log,
379 " \\%"UVuf": %"IVdf"(%"IVdf")..%"IVdf"%s\n",
381 (IV)rex->offs[paren].start,
382 (IV)rex->offs[paren].start_tmp,
383 (IV)rex->offs[paren].end,
384 (paren > rex->lastparen ? "(skipped)" : ""));
389 /* It would seem that the similar code in regtry()
390 * already takes care of this, and in fact it is in
391 * a better location to since this code can #if 0-ed out
392 * but the code in regtry() is needed or otherwise tests
393 * requiring null fields (pat.t#187 and split.t#{13,14}
394 * (as of patchlevel 7877) will fail. Then again,
395 * this code seems to be necessary or otherwise
396 * this erroneously leaves $1 defined: "1" =~ /^(?:(\d)x)?\d$/
397 * --jhi updated by dapm */
398 for (i = rex->lastparen + 1; i <= rex->nparens; i++) {
399 if (i > *maxopenparen_p)
400 rex->offs[i].start = -1;
401 rex->offs[i].end = -1;
402 DEBUG_BUFFERS_r( PerlIO_printf(Perl_debug_log,
403 " \\%"UVuf": %s ..-1 undeffing\n",
405 (i > *maxopenparen_p) ? "-1" : " "
411 /* restore the parens and associated vars at savestack position ix,
412 * but without popping the stack */
415 S_regcp_restore(pTHX_ regexp *rex, I32 ix, U32 *maxopenparen_p)
417 I32 tmpix = PL_savestack_ix;
418 PL_savestack_ix = ix;
419 regcppop(rex, maxopenparen_p);
420 PL_savestack_ix = tmpix;
423 #define regcpblow(cp) LEAVE_SCOPE(cp) /* Ignores regcppush()ed data. */
426 S_isFOO_lc(pTHX_ const U8 classnum, const U8 character)
428 /* Returns a boolean as to whether or not 'character' is a member of the
429 * Posix character class given by 'classnum' that should be equivalent to a
430 * value in the typedef '_char_class_number'.
432 * Ideally this could be replaced by a just an array of function pointers
433 * to the C library functions that implement the macros this calls.
434 * However, to compile, the precise function signatures are required, and
435 * these may vary from platform to to platform. To avoid having to figure
436 * out what those all are on each platform, I (khw) am using this method,
437 * which adds an extra layer of function call overhead (unless the C
438 * optimizer strips it away). But we don't particularly care about
439 * performance with locales anyway. */
441 switch ((_char_class_number) classnum) {
442 case _CC_ENUM_ALPHANUMERIC: return isALPHANUMERIC_LC(character);
443 case _CC_ENUM_ALPHA: return isALPHA_LC(character);
444 case _CC_ENUM_ASCII: return isASCII_LC(character);
445 case _CC_ENUM_BLANK: return isBLANK_LC(character);
446 case _CC_ENUM_CASED: return isLOWER_LC(character)
447 || isUPPER_LC(character);
448 case _CC_ENUM_CNTRL: return isCNTRL_LC(character);
449 case _CC_ENUM_DIGIT: return isDIGIT_LC(character);
450 case _CC_ENUM_GRAPH: return isGRAPH_LC(character);
451 case _CC_ENUM_LOWER: return isLOWER_LC(character);
452 case _CC_ENUM_PRINT: return isPRINT_LC(character);
453 case _CC_ENUM_PSXSPC: return isPSXSPC_LC(character);
454 case _CC_ENUM_PUNCT: return isPUNCT_LC(character);
455 case _CC_ENUM_SPACE: return isSPACE_LC(character);
456 case _CC_ENUM_UPPER: return isUPPER_LC(character);
457 case _CC_ENUM_WORDCHAR: return isWORDCHAR_LC(character);
458 case _CC_ENUM_XDIGIT: return isXDIGIT_LC(character);
459 default: /* VERTSPACE should never occur in locales */
460 Perl_croak(aTHX_ "panic: isFOO_lc() has an unexpected character class '%d'", classnum);
463 assert(0); /* NOTREACHED */
468 S_isFOO_utf8_lc(pTHX_ const U8 classnum, const U8* character)
470 /* Returns a boolean as to whether or not the (well-formed) UTF-8-encoded
471 * 'character' is a member of the Posix character class given by 'classnum'
472 * that should be equivalent to a value in the typedef
473 * '_char_class_number'.
475 * This just calls isFOO_lc on the code point for the character if it is in
476 * the range 0-255. Outside that range, all characters avoid Unicode
477 * rules, ignoring any locale. So use the Unicode function if this class
478 * requires a swash, and use the Unicode macro otherwise. */
480 PERL_ARGS_ASSERT_ISFOO_UTF8_LC;
482 if (UTF8_IS_INVARIANT(*character)) {
483 return isFOO_lc(classnum, *character);
485 else if (UTF8_IS_DOWNGRADEABLE_START(*character)) {
486 return isFOO_lc(classnum,
487 TWO_BYTE_UTF8_TO_UNI(*character, *(character + 1)));
490 if (classnum < _FIRST_NON_SWASH_CC) {
492 /* Initialize the swash unless done already */
493 if (! PL_utf8_swash_ptrs[classnum]) {
494 U8 flags = _CORE_SWASH_INIT_ACCEPT_INVLIST;
495 PL_utf8_swash_ptrs[classnum] = _core_swash_init("utf8",
496 swash_property_names[classnum], &PL_sv_undef, 1, 0, NULL, &flags);
499 return cBOOL(swash_fetch(PL_utf8_swash_ptrs[classnum], (U8 *)
501 TRUE /* is UTF */ ));
504 switch ((_char_class_number) classnum) {
506 case _CC_ENUM_PSXSPC: return is_XPERLSPACE_high(character);
508 case _CC_ENUM_BLANK: return is_HORIZWS_high(character);
509 case _CC_ENUM_XDIGIT: return is_XDIGIT_high(character);
510 case _CC_ENUM_VERTSPACE: return is_VERTWS_high(character);
511 default: return 0; /* Things like CNTRL are always
515 assert(0); /* NOTREACHED */
520 * pregexec and friends
523 #ifndef PERL_IN_XSUB_RE
525 - pregexec - match a regexp against a string
528 Perl_pregexec(pTHX_ REGEXP * const prog, char* stringarg, char *strend,
529 char *strbeg, I32 minend, SV *screamer, U32 nosave)
530 /* stringarg: the point in the string at which to begin matching */
531 /* strend: pointer to null at end of string */
532 /* strbeg: real beginning of string */
533 /* minend: end of match must be >= minend bytes after stringarg. */
534 /* screamer: SV being matched: only used for utf8 flag, pos() etc; string
535 * itself is accessed via the pointers above */
536 /* nosave: For optimizations. */
538 PERL_ARGS_ASSERT_PREGEXEC;
541 regexec_flags(prog, stringarg, strend, strbeg, minend, screamer, NULL,
542 nosave ? 0 : REXEC_COPY_STR);
547 * Need to implement the following flags for reg_anch:
549 * USE_INTUIT_NOML - Useful to call re_intuit_start() first
551 * INTUIT_AUTORITATIVE_NOML - Can trust a positive answer
552 * INTUIT_AUTORITATIVE_ML
553 * INTUIT_ONCE_NOML - Intuit can match in one location only.
556 * Another flag for this function: SECOND_TIME (so that float substrs
557 * with giant delta may be not rechecked).
560 /* Assumptions: if ANCH_GPOS, then strpos is anchored. XXXX Check GPOS logic */
562 /* If SCREAM, then SvPVX_const(sv) should be compatible with strpos and strend.
563 Otherwise, only SvCUR(sv) is used to get strbeg. */
565 /* XXXX We assume that strpos is strbeg unless sv. */
567 /* XXXX Some places assume that there is a fixed substring.
568 An update may be needed if optimizer marks as "INTUITable"
569 RExen without fixed substrings. Similarly, it is assumed that
570 lengths of all the strings are no more than minlen, thus they
571 cannot come from lookahead.
572 (Or minlen should take into account lookahead.)
573 NOTE: Some of this comment is not correct. minlen does now take account
574 of lookahead/behind. Further research is required. -- demerphq
578 /* A failure to find a constant substring means that there is no need to make
579 an expensive call to REx engine, thus we celebrate a failure. Similarly,
580 finding a substring too deep into the string means that fewer calls to
581 regtry() should be needed.
583 REx compiler's optimizer found 4 possible hints:
584 a) Anchored substring;
586 c) Whether we are anchored (beginning-of-line or \G);
587 d) First node (of those at offset 0) which may distinguish positions;
588 We use a)b)d) and multiline-part of c), and try to find a position in the
589 string which does not contradict any of them.
592 /* Most of decisions we do here should have been done at compile time.
593 The nodes of the REx which we used for the search should have been
594 deleted from the finite automaton. */
597 * rx: the regex to match against
598 * sv: the SV being matched: only used for utf8 flag; the string
599 * itself is accessed via the pointers below. Note that on
600 * something like an overloaded SV, SvPOK(sv) may be false
601 * and the string pointers may point to something unrelated to
603 * strbeg: real beginning of string
604 * strpos: the point in the string at which to begin matching
605 * strend: pointer to the byte following the last char of the string
606 * flags currently unused; set to 0
607 * data: currently unused; set to NULL
611 Perl_re_intuit_start(pTHX_
614 const char * const strbeg,
618 re_scream_pos_data *data)
621 struct regexp *const prog = ReANY(rx);
623 /* Should be nonnegative! */
628 const bool utf8_target = (sv && SvUTF8(sv)) ? 1 : 0; /* if no sv we have to assume bytes */
630 char *other_last = NULL; /* other substr checked before this */
631 char *check_at = NULL; /* check substr found at this pos */
632 char *checked_upto = NULL; /* how far into the string we have already checked using find_byclass*/
633 const I32 multiline = prog->extflags & RXf_PMf_MULTILINE;
634 RXi_GET_DECL(prog,progi);
635 regmatch_info reginfo_buf; /* create some info to pass to find_byclass */
636 regmatch_info *const reginfo = ®info_buf;
638 const char * const i_strpos = strpos;
640 GET_RE_DEBUG_FLAGS_DECL;
642 PERL_ARGS_ASSERT_RE_INTUIT_START;
643 PERL_UNUSED_ARG(flags);
644 PERL_UNUSED_ARG(data);
646 /* CHR_DIST() would be more correct here but it makes things slow. */
647 if (prog->minlen > strend - strpos) {
648 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
649 "String too short... [re_intuit_start]\n"));
653 reginfo->is_utf8_target = cBOOL(utf8_target);
654 reginfo->info_aux = NULL;
655 reginfo->strbeg = strbeg;
656 reginfo->strend = strend;
657 reginfo->is_utf8_pat = cBOOL(RX_UTF8(rx));
659 /* not actually used within intuit, but zero for safety anyway */
660 reginfo->poscache_maxiter = 0;
663 if (!prog->check_utf8 && prog->check_substr)
664 to_utf8_substr(prog);
665 check = prog->check_utf8;
667 if (!prog->check_substr && prog->check_utf8) {
668 if (! to_byte_substr(prog)) {
669 NON_UTF8_TARGET_BUT_UTF8_REQUIRED(fail);
672 check = prog->check_substr;
674 if (prog->extflags & RXf_ANCH) { /* Match at beg-of-str or after \n */
675 ml_anch = !( (prog->extflags & RXf_ANCH_SINGLE)
676 || ( (prog->extflags & RXf_ANCH_BOL)
677 && !multiline ) ); /* Check after \n? */
680 if ( !(prog->extflags & RXf_ANCH_GPOS) /* Checked by the caller */
681 && !(prog->intflags & PREGf_IMPLICIT) /* not a real BOL */
682 && (strpos != strbeg)) {
683 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "Not at start...\n"));
686 if (prog->check_offset_min == prog->check_offset_max
687 && !(prog->extflags & RXf_CANY_SEEN)
688 && ! multiline) /* /m can cause \n's to match that aren't
689 accounted for in the string max length.
690 See [perl #115242] */
692 /* Substring at constant offset from beg-of-str... */
695 s = HOP3c(strpos, prog->check_offset_min, strend);
698 slen = SvCUR(check); /* >= 1 */
700 if ( strend - s > slen || strend - s < slen - 1
701 || (strend - s == slen && strend[-1] != '\n')) {
702 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "String too long...\n"));
705 /* Now should match s[0..slen-2] */
707 if (slen && (*SvPVX_const(check) != *s
709 && memNE(SvPVX_const(check), s, slen)))) {
711 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "String not equal...\n"));
715 else if (*SvPVX_const(check) != *s
716 || ((slen = SvCUR(check)) > 1
717 && memNE(SvPVX_const(check), s, slen)))
720 goto success_at_start;
723 /* Match is anchored, but substr is not anchored wrt beg-of-str. */
725 start_shift = prog->check_offset_min; /* okay to underestimate on CC */
726 end_shift = prog->check_end_shift;
729 const I32 end = prog->check_offset_max + CHR_SVLEN(check)
730 - (SvTAIL(check) != 0);
731 const I32 eshift = CHR_DIST((U8*)strend, (U8*)s) - end;
733 if (end_shift < eshift)
737 else { /* Can match at random position */
740 start_shift = prog->check_offset_min; /* okay to underestimate on CC */
741 end_shift = prog->check_end_shift;
743 /* end shift should be non negative here */
746 #ifdef QDEBUGGING /* 7/99: reports of failure (with the older version) */
748 Perl_croak(aTHX_ "panic: end_shift: %"IVdf" pattern:\n%s\n ",
749 (IV)end_shift, RX_PRECOMP(prog));
753 /* Find a possible match in the region s..strend by looking for
754 the "check" substring in the region corrected by start/end_shift. */
757 I32 srch_start_shift = start_shift;
758 I32 srch_end_shift = end_shift;
761 if (srch_start_shift < 0 && strbeg - s > srch_start_shift) {
762 srch_end_shift -= ((strbeg - s) - srch_start_shift);
763 srch_start_shift = strbeg - s;
765 DEBUG_OPTIMISE_MORE_r({
766 PerlIO_printf(Perl_debug_log, "Check offset min: %"IVdf" Start shift: %"IVdf" End shift %"IVdf" Real End Shift: %"IVdf"\n",
767 (IV)prog->check_offset_min,
768 (IV)srch_start_shift,
770 (IV)prog->check_end_shift);
773 if (prog->extflags & RXf_CANY_SEEN) {
774 start_point= (U8*)(s + srch_start_shift);
775 end_point= (U8*)(strend - srch_end_shift);
777 start_point= HOP3(s, srch_start_shift, srch_start_shift < 0 ? strbeg : strend);
778 end_point= HOP3(strend, -srch_end_shift, strbeg);
780 DEBUG_OPTIMISE_MORE_r({
781 PerlIO_printf(Perl_debug_log, "fbm_instr len=%d str=<%.*s>\n",
782 (int)(end_point - start_point),
783 (int)(end_point - start_point) > 20 ? 20 : (int)(end_point - start_point),
787 s = fbm_instr( start_point, end_point,
788 check, multiline ? FBMrf_MULTILINE : 0);
790 /* Update the count-of-usability, remove useless subpatterns,
794 RE_PV_QUOTED_DECL(quoted, utf8_target, PERL_DEBUG_PAD_ZERO(0),
795 SvPVX_const(check), RE_SV_DUMPLEN(check), 30);
796 PerlIO_printf(Perl_debug_log, "%s %s substr %s%s%s",
797 (s ? "Found" : "Did not find"),
798 (check == (utf8_target ? prog->anchored_utf8 : prog->anchored_substr)
799 ? "anchored" : "floating"),
802 (s ? " at offset " : "...\n") );
807 /* Finish the diagnostic message */
808 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "%ld...\n", (long)(s - i_strpos)) );
810 /* XXX dmq: first branch is for positive lookbehind...
811 Our check string is offset from the beginning of the pattern.
812 So we need to do any stclass tests offset forward from that
821 /* Got a candidate. Check MBOL anchoring, and the *other* substr.
822 Start with the other substr.
823 XXXX no SCREAM optimization yet - and a very coarse implementation
824 XXXX /ttx+/ results in anchored="ttx", floating="x". floating will
825 *always* match. Probably should be marked during compile...
826 Probably it is right to do no SCREAM here...
829 if (utf8_target ? (prog->float_utf8 && prog->anchored_utf8)
830 : (prog->float_substr && prog->anchored_substr))
832 /* Take into account the "other" substring. */
833 /* XXXX May be hopelessly wrong for UTF... */
836 if (check == (utf8_target ? prog->float_utf8 : prog->float_substr)) {
839 char * const last = HOP3c(s, -start_shift, strbeg);
841 char * const saved_s = s;
844 t = s - prog->check_offset_max;
845 if (s - strpos > prog->check_offset_max /* signed-corrected t > strpos */
847 || ((t = (char*)reghopmaybe3((U8*)s, -(prog->check_offset_max), (U8*)strpos))
852 t = HOP3c(t, prog->anchored_offset, strend);
853 if (t < other_last) /* These positions already checked */
855 last2 = last1 = HOP3c(strend, -prog->minlen, strbeg);
858 /* XXXX It is not documented what units *_offsets are in.
859 We assume bytes, but this is clearly wrong.
860 Meaning this code needs to be carefully reviewed for errors.
864 /* On end-of-str: see comment below. */
865 must = utf8_target ? prog->anchored_utf8 : prog->anchored_substr;
866 if (must == &PL_sv_undef) {
868 DEBUG_r(must = prog->anchored_utf8); /* for debug */
873 HOP3(HOP3(last1, prog->anchored_offset, strend)
874 + SvCUR(must), -(SvTAIL(must)!=0), strbeg),
876 multiline ? FBMrf_MULTILINE : 0
879 RE_PV_QUOTED_DECL(quoted, utf8_target, PERL_DEBUG_PAD_ZERO(0),
880 SvPVX_const(must), RE_SV_DUMPLEN(must), 30);
881 PerlIO_printf(Perl_debug_log, "%s anchored substr %s%s",
882 (s ? "Found" : "Contradicts"),
883 quoted, RE_SV_TAIL(must));
888 if (last1 >= last2) {
889 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
890 ", giving up...\n"));
893 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
894 ", trying floating at offset %ld...\n",
895 (long)(HOP3c(saved_s, 1, strend) - i_strpos)));
896 other_last = HOP3c(last1, prog->anchored_offset+1, strend);
897 s = HOP3c(last, 1, strend);
901 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, " at offset %ld...\n",
902 (long)(s - i_strpos)));
903 t = HOP3c(s, -prog->anchored_offset, strbeg);
904 other_last = HOP3c(s, 1, strend);
912 else { /* Take into account the floating substring. */
914 char * const saved_s = s;
917 t = HOP3c(s, -start_shift, strbeg);
919 HOP3c(strend, -prog->minlen + prog->float_min_offset, strbeg);
920 if (CHR_DIST((U8*)last, (U8*)t) > prog->float_max_offset)
921 last = HOP3c(t, prog->float_max_offset, strend);
922 s = HOP3c(t, prog->float_min_offset, strend);
925 /* XXXX It is not documented what units *_offsets are in. Assume bytes. */
926 must = utf8_target ? prog->float_utf8 : prog->float_substr;
927 /* fbm_instr() takes into account exact value of end-of-str
928 if the check is SvTAIL(ed). Since false positives are OK,
929 and end-of-str is not later than strend we are OK. */
930 if (must == &PL_sv_undef) {
932 DEBUG_r(must = prog->float_utf8); /* for debug message */
935 s = fbm_instr((unsigned char*)s,
936 (unsigned char*)last + SvCUR(must)
938 must, multiline ? FBMrf_MULTILINE : 0);
940 RE_PV_QUOTED_DECL(quoted, utf8_target, PERL_DEBUG_PAD_ZERO(0),
941 SvPVX_const(must), RE_SV_DUMPLEN(must), 30);
942 PerlIO_printf(Perl_debug_log, "%s floating substr %s%s",
943 (s ? "Found" : "Contradicts"),
944 quoted, RE_SV_TAIL(must));
948 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
949 ", giving up...\n"));
952 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
953 ", trying anchored starting at offset %ld...\n",
954 (long)(saved_s + 1 - i_strpos)));
956 s = HOP3c(t, 1, strend);
960 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, " at offset %ld...\n",
961 (long)(s - i_strpos)));
962 other_last = s; /* Fix this later. --Hugo */
972 t= (char*)HOP3( s, -prog->check_offset_max, (prog->check_offset_max<0) ? strend : strpos);
974 DEBUG_OPTIMISE_MORE_r(
975 PerlIO_printf(Perl_debug_log,
976 "Check offset min:%"IVdf" max:%"IVdf" S:%"IVdf" t:%"IVdf" D:%"IVdf" end:%"IVdf"\n",
977 (IV)prog->check_offset_min,
978 (IV)prog->check_offset_max,
986 if (s - strpos > prog->check_offset_max /* signed-corrected t > strpos */
988 || ((t = (char*)reghopmaybe3((U8*)s, -prog->check_offset_max, (U8*) ((prog->check_offset_max<0) ? strend : strpos)))
991 /* Fixed substring is found far enough so that the match
992 cannot start at strpos. */
994 if (ml_anch && t[-1] != '\n') {
995 /* Eventually fbm_*() should handle this, but often
996 anchored_offset is not 0, so this check will not be wasted. */
997 /* XXXX In the code below we prefer to look for "^" even in
998 presence of anchored substrings. And we search even
999 beyond the found float position. These pessimizations
1000 are historical artefacts only. */
1002 while (t < strend - prog->minlen) {
1004 if (t < check_at - prog->check_offset_min) {
1005 if (utf8_target ? prog->anchored_utf8 : prog->anchored_substr) {
1006 /* Since we moved from the found position,
1007 we definitely contradict the found anchored
1008 substr. Due to the above check we do not
1009 contradict "check" substr.
1010 Thus we can arrive here only if check substr
1011 is float. Redo checking for "other"=="fixed".
1014 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "Found /%s^%s/m at offset %ld, rescanning for anchored from offset %ld...\n",
1015 PL_colors[0], PL_colors[1], (long)(strpos - i_strpos), (long)(strpos - i_strpos + prog->anchored_offset)));
1016 goto do_other_anchored;
1018 /* We don't contradict the found floating substring. */
1019 /* XXXX Why not check for STCLASS? */
1021 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "Found /%s^%s/m at offset %ld...\n",
1022 PL_colors[0], PL_colors[1], (long)(s - i_strpos)));
1025 /* Position contradicts check-string */
1026 /* XXXX probably better to look for check-string
1027 than for "\n", so one should lower the limit for t? */
1028 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "Found /%s^%s/m, restarting lookup for check-string at offset %ld...\n",
1029 PL_colors[0], PL_colors[1], (long)(t + 1 - i_strpos)));
1030 other_last = strpos = s = t + 1;
1035 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "Did not find /%s^%s/m...\n",
1036 PL_colors[0], PL_colors[1]));
1040 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "Starting position does not contradict /%s^%s/m...\n",
1041 PL_colors[0], PL_colors[1]));
1045 ++BmUSEFUL(utf8_target ? prog->check_utf8 : prog->check_substr); /* hooray/5 */
1048 /* The found string does not prohibit matching at strpos,
1049 - no optimization of calling REx engine can be performed,
1050 unless it was an MBOL and we are not after MBOL,
1051 or a future STCLASS check will fail this. */
1053 /* Even in this situation we may use MBOL flag if strpos is offset
1054 wrt the start of the string. */
1055 if (ml_anch && (strpos != strbeg) && strpos[-1] != '\n'
1056 /* May be due to an implicit anchor of m{.*foo} */
1057 && !(prog->intflags & PREGf_IMPLICIT))
1062 DEBUG_EXECUTE_r( if (ml_anch)
1063 PerlIO_printf(Perl_debug_log, "Position at offset %ld does not contradict /%s^%s/m...\n",
1064 (long)(strpos - i_strpos), PL_colors[0], PL_colors[1]);
1067 if (!(prog->intflags & PREGf_NAUGHTY) /* XXXX If strpos moved? */
1069 prog->check_utf8 /* Could be deleted already */
1070 && --BmUSEFUL(prog->check_utf8) < 0
1071 && (prog->check_utf8 == prog->float_utf8)
1073 prog->check_substr /* Could be deleted already */
1074 && --BmUSEFUL(prog->check_substr) < 0
1075 && (prog->check_substr == prog->float_substr)
1078 /* If flags & SOMETHING - do not do it many times on the same match */
1079 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "... Disabling check substring...\n"));
1080 /* XXX Does the destruction order has to change with utf8_target? */
1081 SvREFCNT_dec(utf8_target ? prog->check_utf8 : prog->check_substr);
1082 SvREFCNT_dec(utf8_target ? prog->check_substr : prog->check_utf8);
1083 prog->check_substr = prog->check_utf8 = NULL; /* disable */
1084 prog->float_substr = prog->float_utf8 = NULL; /* clear */
1085 check = NULL; /* abort */
1087 /* XXXX If the check string was an implicit check MBOL, then we need to unset the relevant flag
1088 see http://bugs.activestate.com/show_bug.cgi?id=87173 */
1089 if (prog->intflags & PREGf_IMPLICIT)
1090 prog->extflags &= ~RXf_ANCH_MBOL;
1091 /* XXXX This is a remnant of the old implementation. It
1092 looks wasteful, since now INTUIT can use many
1093 other heuristics. */
1094 prog->extflags &= ~RXf_USE_INTUIT;
1095 /* XXXX What other flags might need to be cleared in this branch? */
1101 /* Last resort... */
1102 /* XXXX BmUSEFUL already changed, maybe multiple change is meaningful... */
1103 /* trie stclasses are too expensive to use here, we are better off to
1104 leave it to regmatch itself */
1105 if (progi->regstclass && PL_regkind[OP(progi->regstclass)]!=TRIE) {
1106 /* minlen == 0 is possible if regstclass is \b or \B,
1107 and the fixed substr is ''$.
1108 Since minlen is already taken into account, s+1 is before strend;
1109 accidentally, minlen >= 1 guaranties no false positives at s + 1
1110 even for \b or \B. But (minlen? 1 : 0) below assumes that
1111 regstclass does not come from lookahead... */
1112 /* If regstclass takes bytelength more than 1: If charlength==1, OK.
1113 This leaves EXACTF-ish only, which are dealt with in find_byclass(). */
1114 const U8* const str = (U8*)STRING(progi->regstclass);
1115 const int cl_l = (PL_regkind[OP(progi->regstclass)] == EXACT
1116 ? CHR_DIST(str+STR_LEN(progi->regstclass), str)
1119 if (prog->anchored_substr || prog->anchored_utf8 || ml_anch)
1120 endpos= HOP3c(s, (prog->minlen ? cl_l : 0), strend);
1121 else if (prog->float_substr || prog->float_utf8)
1122 endpos= HOP3c(HOP3c(check_at, -start_shift, strbeg), cl_l, strend);
1126 if (checked_upto < s)
1128 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "start_shift: %"IVdf" check_at: %"IVdf" s: %"IVdf" endpos: %"IVdf" checked_upto: %"IVdf"\n",
1129 (IV)start_shift, (IV)(check_at - strbeg), (IV)(s - strbeg), (IV)(endpos - strbeg), (IV)(checked_upto- strbeg)));
1132 s = find_byclass(prog, progi->regstclass, checked_upto, endpos,
1138 const char *what = NULL;
1140 if (endpos == strend) {
1141 DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log,
1142 "Could not match STCLASS...\n") );
1145 DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log,
1146 "This position contradicts STCLASS...\n") );
1147 if ((prog->extflags & RXf_ANCH) && !ml_anch)
1149 checked_upto = HOPBACKc(endpos, start_shift);
1150 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "start_shift: %"IVdf" check_at: %"IVdf" endpos: %"IVdf" checked_upto: %"IVdf"\n",
1151 (IV)start_shift, (IV)(check_at - strbeg), (IV)(endpos - strbeg), (IV)(checked_upto- strbeg)));
1152 /* Contradict one of substrings */
1153 if (prog->anchored_substr || prog->anchored_utf8) {
1154 if ((utf8_target ? prog->anchored_utf8 : prog->anchored_substr) == check) {
1155 DEBUG_EXECUTE_r( what = "anchored" );
1157 s = HOP3c(t, 1, strend);
1158 if (s + start_shift + end_shift > strend) {
1159 /* XXXX Should be taken into account earlier? */
1160 DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log,
1161 "Could not match STCLASS...\n") );
1166 DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log,
1167 "Looking for %s substr starting at offset %ld...\n",
1168 what, (long)(s + start_shift - i_strpos)) );
1171 /* Have both, check_string is floating */
1172 if (t + start_shift >= check_at) /* Contradicts floating=check */
1173 goto retry_floating_check;
1174 /* Recheck anchored substring, but not floating... */
1178 DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log,
1179 "Looking for anchored substr starting at offset %ld...\n",
1180 (long)(other_last - i_strpos)) );
1181 goto do_other_anchored;
1183 /* Another way we could have checked stclass at the
1184 current position only: */
1189 DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log,
1190 "Looking for /%s^%s/m starting at offset %ld...\n",
1191 PL_colors[0], PL_colors[1], (long)(t - i_strpos)) );
1194 if (!(utf8_target ? prog->float_utf8 : prog->float_substr)) /* Could have been deleted */
1196 /* Check is floating substring. */
1197 retry_floating_check:
1198 t = check_at - start_shift;
1199 DEBUG_EXECUTE_r( what = "floating" );
1200 goto hop_and_restart;
1203 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
1204 "By STCLASS: moving %ld --> %ld\n",
1205 (long)(t - i_strpos), (long)(s - i_strpos))
1209 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
1210 "Does not contradict STCLASS...\n");
1215 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "%s%s:%s match at offset %ld\n",
1216 PL_colors[4], (check ? "Guessed" : "Giving up"),
1217 PL_colors[5], (long)(s - i_strpos)) );
1220 fail_finish: /* Substring not found */
1221 if (prog->check_substr || prog->check_utf8) /* could be removed already */
1222 BmUSEFUL(utf8_target ? prog->check_utf8 : prog->check_substr) += 5; /* hooray */
1224 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "%sMatch rejected by optimizer%s\n",
1225 PL_colors[4], PL_colors[5]));
1229 #define DECL_TRIE_TYPE(scan) \
1230 const enum { trie_plain, trie_utf8, trie_utf8_fold, trie_latin_utf8_fold } \
1231 trie_type = ((scan->flags == EXACT) \
1232 ? (utf8_target ? trie_utf8 : trie_plain) \
1233 : (utf8_target ? trie_utf8_fold : trie_latin_utf8_fold))
1235 #define REXEC_TRIE_READ_CHAR(trie_type, trie, widecharmap, uc, uscan, len, uvc, charid, foldlen, foldbuf, uniflags) \
1238 switch (trie_type) { \
1239 case trie_utf8_fold: \
1240 if ( foldlen>0 ) { \
1241 uvc = utf8n_to_uvuni( (const U8*) uscan, UTF8_MAXLEN, &len, uniflags ); \
1246 uvc = to_utf8_fold( (const U8*) uc, foldbuf, &foldlen ); \
1247 len = UTF8SKIP(uc); \
1248 skiplen = UNISKIP( uvc ); \
1249 foldlen -= skiplen; \
1250 uscan = foldbuf + skiplen; \
1253 case trie_latin_utf8_fold: \
1254 if ( foldlen>0 ) { \
1255 uvc = utf8n_to_uvuni( (const U8*) uscan, UTF8_MAXLEN, &len, uniflags ); \
1261 uvc = _to_fold_latin1( (U8) *uc, foldbuf, &foldlen, FOLD_FLAGS_FULL); \
1262 skiplen = UNISKIP( uvc ); \
1263 foldlen -= skiplen; \
1264 uscan = foldbuf + skiplen; \
1268 uvc = utf8n_to_uvuni( (const U8*) uc, UTF8_MAXLEN, &len, uniflags ); \
1275 charid = trie->charmap[ uvc ]; \
1279 if (widecharmap) { \
1280 SV** const svpp = hv_fetch(widecharmap, \
1281 (char*)&uvc, sizeof(UV), 0); \
1283 charid = (U16)SvIV(*svpp); \
1288 #define REXEC_FBC_EXACTISH_SCAN(CoNd) \
1292 && (ln == 1 || folder(s, pat_string, ln)) \
1293 && (reginfo->intuit || regtry(reginfo, &s)) )\
1299 #define REXEC_FBC_UTF8_SCAN(CoDe) \
1301 while (s < strend) { \
1307 #define REXEC_FBC_SCAN(CoDe) \
1309 while (s < strend) { \
1315 #define REXEC_FBC_UTF8_CLASS_SCAN(CoNd) \
1316 REXEC_FBC_UTF8_SCAN( \
1318 if (tmp && (reginfo->intuit || regtry(reginfo, &s))) \
1327 #define REXEC_FBC_CLASS_SCAN(CoNd) \
1330 if (tmp && (reginfo->intuit || regtry(reginfo, &s))) \
1339 #define REXEC_FBC_TRYIT \
1340 if ((reginfo->intuit || regtry(reginfo, &s))) \
1343 #define REXEC_FBC_CSCAN(CoNdUtF8,CoNd) \
1344 if (utf8_target) { \
1345 REXEC_FBC_UTF8_CLASS_SCAN(CoNdUtF8); \
1348 REXEC_FBC_CLASS_SCAN(CoNd); \
1351 #define DUMP_EXEC_POS(li,s,doutf8) \
1352 dump_exec_pos(li,s,(reginfo->strend),(reginfo->strbeg), \
1356 #define UTF8_NOLOAD(TEST_NON_UTF8, IF_SUCCESS, IF_FAIL) \
1357 tmp = (s != reginfo->strbeg) ? UCHARAT(s - 1) : '\n'; \
1358 tmp = TEST_NON_UTF8(tmp); \
1359 REXEC_FBC_UTF8_SCAN( \
1360 if (tmp == ! TEST_NON_UTF8((U8) *s)) { \
1369 #define UTF8_LOAD(TeSt1_UtF8, TeSt2_UtF8, IF_SUCCESS, IF_FAIL) \
1370 if (s == reginfo->strbeg) { \
1374 U8 * const r = reghop3((U8*)s, -1, (U8*)reginfo->strbeg); \
1375 tmp = utf8n_to_uvchr(r, UTF8SKIP(r), 0, UTF8_ALLOW_DEFAULT); \
1378 LOAD_UTF8_CHARCLASS_ALNUM(); \
1379 REXEC_FBC_UTF8_SCAN( \
1380 if (tmp == ! (TeSt2_UtF8)) { \
1389 /* The only difference between the BOUND and NBOUND cases is that
1390 * REXEC_FBC_TRYIT is called when matched in BOUND, and when non-matched in
1391 * NBOUND. This is accomplished by passing it in either the if or else clause,
1392 * with the other one being empty */
1393 #define FBC_BOUND(TEST_NON_UTF8, TEST1_UTF8, TEST2_UTF8) \
1394 FBC_BOUND_COMMON(UTF8_LOAD(TEST1_UTF8, TEST2_UTF8, REXEC_FBC_TRYIT, PLACEHOLDER), TEST_NON_UTF8, REXEC_FBC_TRYIT, PLACEHOLDER)
1396 #define FBC_BOUND_NOLOAD(TEST_NON_UTF8, TEST1_UTF8, TEST2_UTF8) \
1397 FBC_BOUND_COMMON(UTF8_NOLOAD(TEST_NON_UTF8, REXEC_FBC_TRYIT, PLACEHOLDER), TEST_NON_UTF8, REXEC_FBC_TRYIT, PLACEHOLDER)
1399 #define FBC_NBOUND(TEST_NON_UTF8, TEST1_UTF8, TEST2_UTF8) \
1400 FBC_BOUND_COMMON(UTF8_LOAD(TEST1_UTF8, TEST2_UTF8, PLACEHOLDER, REXEC_FBC_TRYIT), TEST_NON_UTF8, PLACEHOLDER, REXEC_FBC_TRYIT)
1402 #define FBC_NBOUND_NOLOAD(TEST_NON_UTF8, TEST1_UTF8, TEST2_UTF8) \
1403 FBC_BOUND_COMMON(UTF8_NOLOAD(TEST_NON_UTF8, PLACEHOLDER, REXEC_FBC_TRYIT), TEST_NON_UTF8, PLACEHOLDER, REXEC_FBC_TRYIT)
1406 /* Common to the BOUND and NBOUND cases. Unfortunately the UTF8 tests need to
1407 * be passed in completely with the variable name being tested, which isn't
1408 * such a clean interface, but this is easier to read than it was before. We
1409 * are looking for the boundary (or non-boundary between a word and non-word
1410 * character. The utf8 and non-utf8 cases have the same logic, but the details
1411 * must be different. Find the "wordness" of the character just prior to this
1412 * one, and compare it with the wordness of this one. If they differ, we have
1413 * a boundary. At the beginning of the string, pretend that the previous
1414 * character was a new-line */
1415 #define FBC_BOUND_COMMON(UTF8_CODE, TEST_NON_UTF8, IF_SUCCESS, IF_FAIL) \
1416 if (utf8_target) { \
1419 else { /* Not utf8 */ \
1420 tmp = (s != reginfo->strbeg) ? UCHARAT(s - 1) : '\n'; \
1421 tmp = TEST_NON_UTF8(tmp); \
1423 if (tmp == ! TEST_NON_UTF8((U8) *s)) { \
1432 if ((!prog->minlen && tmp) && (reginfo->intuit || regtry(reginfo, &s))) \
1435 /* We know what class REx starts with. Try to find this position... */
1436 /* if reginfo->intuit, its a dryrun */
1437 /* annoyingly all the vars in this routine have different names from their counterparts
1438 in regmatch. /grrr */
1441 S_find_byclass(pTHX_ regexp * prog, const regnode *c, char *s,
1442 const char *strend, regmatch_info *reginfo)
1445 const I32 doevery = (prog->intflags & PREGf_SKIP) == 0;
1446 char *pat_string; /* The pattern's exactish string */
1447 char *pat_end; /* ptr to end char of pat_string */
1448 re_fold_t folder; /* Function for computing non-utf8 folds */
1449 const U8 *fold_array; /* array for folding ords < 256 */
1455 I32 tmp = 1; /* Scratch variable? */
1456 const bool utf8_target = reginfo->is_utf8_target;
1457 UV utf8_fold_flags = 0;
1458 const bool is_utf8_pat = reginfo->is_utf8_pat;
1459 bool to_complement = FALSE; /* Invert the result? Taking the xor of this
1460 with a result inverts that result, as 0^1 =
1462 _char_class_number classnum;
1464 RXi_GET_DECL(prog,progi);
1466 PERL_ARGS_ASSERT_FIND_BYCLASS;
1468 /* We know what class it must start with. */
1471 case ANYOF_SYNTHETIC:
1472 case ANYOF_WARN_SUPER:
1474 REXEC_FBC_UTF8_CLASS_SCAN(
1475 reginclass(prog, c, (U8*)s, utf8_target));
1478 REXEC_FBC_CLASS_SCAN(REGINCLASS(prog, c, (U8*)s));
1483 if (tmp && (reginfo->intuit || regtry(reginfo, &s)))
1491 if (is_utf8_pat || utf8_target) {
1492 utf8_fold_flags = FOLDEQ_UTF8_NOMIX_ASCII;
1493 goto do_exactf_utf8;
1495 fold_array = PL_fold_latin1; /* Latin1 folds are not affected by */
1496 folder = foldEQ_latin1; /* /a, except the sharp s one which */
1497 goto do_exactf_non_utf8; /* isn't dealt with by these */
1502 /* regcomp.c already folded this if pattern is in UTF-8 */
1503 utf8_fold_flags = 0;
1504 goto do_exactf_utf8;
1506 fold_array = PL_fold;
1508 goto do_exactf_non_utf8;
1511 if (is_utf8_pat || utf8_target) {
1512 utf8_fold_flags = FOLDEQ_UTF8_LOCALE;
1513 goto do_exactf_utf8;
1515 fold_array = PL_fold_locale;
1516 folder = foldEQ_locale;
1517 goto do_exactf_non_utf8;
1521 utf8_fold_flags = FOLDEQ_S2_ALREADY_FOLDED;
1523 goto do_exactf_utf8;
1525 case EXACTFU_TRICKYFOLD:
1527 if (is_utf8_pat || utf8_target) {
1528 utf8_fold_flags = is_utf8_pat ? FOLDEQ_S2_ALREADY_FOLDED : 0;
1529 goto do_exactf_utf8;
1532 /* Any 'ss' in the pattern should have been replaced by regcomp,
1533 * so we don't have to worry here about this single special case
1534 * in the Latin1 range */
1535 fold_array = PL_fold_latin1;
1536 folder = foldEQ_latin1;
1540 do_exactf_non_utf8: /* Neither pattern nor string are UTF8, and there
1541 are no glitches with fold-length differences
1542 between the target string and pattern */
1544 /* The idea in the non-utf8 EXACTF* cases is to first find the
1545 * first character of the EXACTF* node and then, if necessary,
1546 * case-insensitively compare the full text of the node. c1 is the
1547 * first character. c2 is its fold. This logic will not work for
1548 * Unicode semantics and the german sharp ss, which hence should
1549 * not be compiled into a node that gets here. */
1550 pat_string = STRING(c);
1551 ln = STR_LEN(c); /* length to match in octets/bytes */
1553 /* We know that we have to match at least 'ln' bytes (which is the
1554 * same as characters, since not utf8). If we have to match 3
1555 * characters, and there are only 2 availabe, we know without
1556 * trying that it will fail; so don't start a match past the
1557 * required minimum number from the far end */
1558 e = HOP3c(strend, -((I32)ln), s);
1560 if (reginfo->intuit && e < s) {
1561 e = s; /* Due to minlen logic of intuit() */
1565 c2 = fold_array[c1];
1566 if (c1 == c2) { /* If char and fold are the same */
1567 REXEC_FBC_EXACTISH_SCAN(*(U8*)s == c1);
1570 REXEC_FBC_EXACTISH_SCAN(*(U8*)s == c1 || *(U8*)s == c2);
1578 /* If one of the operands is in utf8, we can't use the simpler folding
1579 * above, due to the fact that many different characters can have the
1580 * same fold, or portion of a fold, or different- length fold */
1581 pat_string = STRING(c);
1582 ln = STR_LEN(c); /* length to match in octets/bytes */
1583 pat_end = pat_string + ln;
1584 lnc = is_utf8_pat /* length to match in characters */
1585 ? utf8_length((U8 *) pat_string, (U8 *) pat_end)
1588 /* We have 'lnc' characters to match in the pattern, but because of
1589 * multi-character folding, each character in the target can match
1590 * up to 3 characters (Unicode guarantees it will never exceed
1591 * this) if it is utf8-encoded; and up to 2 if not (based on the
1592 * fact that the Latin 1 folds are already determined, and the
1593 * only multi-char fold in that range is the sharp-s folding to
1594 * 'ss'. Thus, a pattern character can match as little as 1/3 of a
1595 * string character. Adjust lnc accordingly, rounding up, so that
1596 * if we need to match at least 4+1/3 chars, that really is 5. */
1597 expansion = (utf8_target) ? UTF8_MAX_FOLD_CHAR_EXPAND : 2;
1598 lnc = (lnc + expansion - 1) / expansion;
1600 /* As in the non-UTF8 case, if we have to match 3 characters, and
1601 * only 2 are left, it's guaranteed to fail, so don't start a
1602 * match that would require us to go beyond the end of the string
1604 e = HOP3c(strend, -((I32)lnc), s);
1606 if (reginfo->intuit && e < s) {
1607 e = s; /* Due to minlen logic of intuit() */
1610 /* XXX Note that we could recalculate e to stop the loop earlier,
1611 * as the worst case expansion above will rarely be met, and as we
1612 * go along we would usually find that e moves further to the left.
1613 * This would happen only after we reached the point in the loop
1614 * where if there were no expansion we should fail. Unclear if
1615 * worth the expense */
1618 char *my_strend= (char *)strend;
1619 if (foldEQ_utf8_flags(s, &my_strend, 0, utf8_target,
1620 pat_string, NULL, ln, is_utf8_pat, utf8_fold_flags)
1621 && (reginfo->intuit || regtry(reginfo, &s)) )
1625 s += (utf8_target) ? UTF8SKIP(s) : 1;
1630 RXp_MATCH_TAINTED_on(prog);
1631 FBC_BOUND(isWORDCHAR_LC,
1632 isWORDCHAR_LC_uvchr(UNI_TO_NATIVE(tmp)),
1633 isWORDCHAR_LC_utf8((U8*)s));
1636 RXp_MATCH_TAINTED_on(prog);
1637 FBC_NBOUND(isWORDCHAR_LC,
1638 isWORDCHAR_LC_uvchr(UNI_TO_NATIVE(tmp)),
1639 isWORDCHAR_LC_utf8((U8*)s));
1642 FBC_BOUND(isWORDCHAR,
1643 isWORDCHAR_uni(tmp),
1644 cBOOL(swash_fetch(PL_utf8_swash_ptrs[_CC_WORDCHAR], (U8*)s, utf8_target)));
1647 FBC_BOUND_NOLOAD(isWORDCHAR_A,
1649 isWORDCHAR_A((U8*)s));
1652 FBC_NBOUND(isWORDCHAR,
1653 isWORDCHAR_uni(tmp),
1654 cBOOL(swash_fetch(PL_utf8_swash_ptrs[_CC_WORDCHAR], (U8*)s, utf8_target)));
1657 FBC_NBOUND_NOLOAD(isWORDCHAR_A,
1659 isWORDCHAR_A((U8*)s));
1662 FBC_BOUND(isWORDCHAR_L1,
1663 isWORDCHAR_uni(tmp),
1664 cBOOL(swash_fetch(PL_utf8_swash_ptrs[_CC_WORDCHAR], (U8*)s, utf8_target)));
1667 FBC_NBOUND(isWORDCHAR_L1,
1668 isWORDCHAR_uni(tmp),
1669 cBOOL(swash_fetch(PL_utf8_swash_ptrs[_CC_WORDCHAR], (U8*)s, utf8_target)));
1672 REXEC_FBC_CSCAN(is_LNBREAK_utf8_safe(s, strend),
1673 is_LNBREAK_latin1_safe(s, strend)
1677 /* The argument to all the POSIX node types is the class number to pass to
1678 * _generic_isCC() to build a mask for searching in PL_charclass[] */
1685 RXp_MATCH_TAINTED_on(prog);
1686 REXEC_FBC_CSCAN(to_complement ^ cBOOL(isFOO_utf8_lc(FLAGS(c), (U8 *) s)),
1687 to_complement ^ cBOOL(isFOO_lc(FLAGS(c), *s)));
1702 /* The complement of something that matches only ASCII matches all
1703 * UTF-8 variant code points, plus everything in ASCII that isn't
1705 REXEC_FBC_UTF8_CLASS_SCAN(! UTF8_IS_INVARIANT(*s)
1706 || ! _generic_isCC_A(*s, FLAGS(c)));
1715 /* Don't need to worry about utf8, as it can match only a single
1716 * byte invariant character. */
1717 REXEC_FBC_CLASS_SCAN(
1718 to_complement ^ cBOOL(_generic_isCC_A(*s, FLAGS(c))));
1726 if (! utf8_target) {
1727 REXEC_FBC_CLASS_SCAN(to_complement ^ cBOOL(_generic_isCC(*s,
1733 classnum = (_char_class_number) FLAGS(c);
1734 if (classnum < _FIRST_NON_SWASH_CC) {
1735 while (s < strend) {
1737 /* We avoid loading in the swash as long as possible, but
1738 * should we have to, we jump to a separate loop. This
1739 * extra 'if' statement is what keeps this code from being
1740 * just a call to REXEC_FBC_UTF8_CLASS_SCAN() */
1741 if (UTF8_IS_ABOVE_LATIN1(*s)) {
1742 goto found_above_latin1;
1744 if ((UTF8_IS_INVARIANT(*s)
1745 && to_complement ^ cBOOL(_generic_isCC((U8) *s,
1747 || (UTF8_IS_DOWNGRADEABLE_START(*s)
1748 && to_complement ^ cBOOL(
1749 _generic_isCC(TWO_BYTE_UTF8_TO_UNI(*s, *(s + 1)),
1752 if (tmp && (reginfo->intuit || regtry(reginfo, &s)))
1764 else switch (classnum) { /* These classes are implemented as
1766 case _CC_ENUM_SPACE: /* XXX would require separate code if we
1767 revert the change of \v matching this */
1770 case _CC_ENUM_PSXSPC:
1771 REXEC_FBC_UTF8_CLASS_SCAN(
1772 to_complement ^ cBOOL(isSPACE_utf8(s)));
1775 case _CC_ENUM_BLANK:
1776 REXEC_FBC_UTF8_CLASS_SCAN(
1777 to_complement ^ cBOOL(isBLANK_utf8(s)));
1780 case _CC_ENUM_XDIGIT:
1781 REXEC_FBC_UTF8_CLASS_SCAN(
1782 to_complement ^ cBOOL(isXDIGIT_utf8(s)));
1785 case _CC_ENUM_VERTSPACE:
1786 REXEC_FBC_UTF8_CLASS_SCAN(
1787 to_complement ^ cBOOL(isVERTWS_utf8(s)));
1790 case _CC_ENUM_CNTRL:
1791 REXEC_FBC_UTF8_CLASS_SCAN(
1792 to_complement ^ cBOOL(isCNTRL_utf8(s)));
1796 Perl_croak(aTHX_ "panic: find_byclass() node %d='%s' has an unexpected character class '%d'", OP(c), PL_reg_name[OP(c)], classnum);
1797 assert(0); /* NOTREACHED */
1802 found_above_latin1: /* Here we have to load a swash to get the result
1803 for the current code point */
1804 if (! PL_utf8_swash_ptrs[classnum]) {
1805 U8 flags = _CORE_SWASH_INIT_ACCEPT_INVLIST;
1806 PL_utf8_swash_ptrs[classnum] =
1807 _core_swash_init("utf8", swash_property_names[classnum],
1808 &PL_sv_undef, 1, 0, NULL, &flags);
1811 /* This is a copy of the loop above for swash classes, though using the
1812 * FBC macro instead of being expanded out. Since we've loaded the
1813 * swash, we don't have to check for that each time through the loop */
1814 REXEC_FBC_UTF8_CLASS_SCAN(
1815 to_complement ^ cBOOL(_generic_utf8(
1818 swash_fetch(PL_utf8_swash_ptrs[classnum],
1826 /* what trie are we using right now */
1827 reg_ac_data *aho = (reg_ac_data*)progi->data->data[ ARG( c ) ];
1828 reg_trie_data *trie = (reg_trie_data*)progi->data->data[ aho->trie ];
1829 HV *widecharmap = MUTABLE_HV(progi->data->data[ aho->trie + 1 ]);
1831 const char *last_start = strend - trie->minlen;
1833 const char *real_start = s;
1835 STRLEN maxlen = trie->maxlen;
1837 U8 **points; /* map of where we were in the input string
1838 when reading a given char. For ASCII this
1839 is unnecessary overhead as the relationship
1840 is always 1:1, but for Unicode, especially
1841 case folded Unicode this is not true. */
1842 U8 foldbuf[ UTF8_MAXBYTES_CASE + 1 ];
1846 GET_RE_DEBUG_FLAGS_DECL;
1848 /* We can't just allocate points here. We need to wrap it in
1849 * an SV so it gets freed properly if there is a croak while
1850 * running the match */
1853 sv_points=newSV(maxlen * sizeof(U8 *));
1854 SvCUR_set(sv_points,
1855 maxlen * sizeof(U8 *));
1856 SvPOK_on(sv_points);
1857 sv_2mortal(sv_points);
1858 points=(U8**)SvPV_nolen(sv_points );
1859 if ( trie_type != trie_utf8_fold
1860 && (trie->bitmap || OP(c)==AHOCORASICKC) )
1863 bitmap=(U8*)trie->bitmap;
1865 bitmap=(U8*)ANYOF_BITMAP(c);
1867 /* this is the Aho-Corasick algorithm modified a touch
1868 to include special handling for long "unknown char" sequences.
1869 The basic idea being that we use AC as long as we are dealing
1870 with a possible matching char, when we encounter an unknown char
1871 (and we have not encountered an accepting state) we scan forward
1872 until we find a legal starting char.
1873 AC matching is basically that of trie matching, except that when
1874 we encounter a failing transition, we fall back to the current
1875 states "fail state", and try the current char again, a process
1876 we repeat until we reach the root state, state 1, or a legal
1877 transition. If we fail on the root state then we can either
1878 terminate if we have reached an accepting state previously, or
1879 restart the entire process from the beginning if we have not.
1882 while (s <= last_start) {
1883 const U32 uniflags = UTF8_ALLOW_DEFAULT;
1891 U8 *uscan = (U8*)NULL;
1892 U8 *leftmost = NULL;
1894 U32 accepted_word= 0;
1898 while ( state && uc <= (U8*)strend ) {
1900 U32 word = aho->states[ state ].wordnum;
1904 DEBUG_TRIE_EXECUTE_r(
1905 if ( uc <= (U8*)last_start && !BITMAP_TEST(bitmap,*uc) ) {
1906 dump_exec_pos( (char *)uc, c, strend, real_start,
1907 (char *)uc, utf8_target );
1908 PerlIO_printf( Perl_debug_log,
1909 " Scanning for legal start char...\n");
1913 while ( uc <= (U8*)last_start && !BITMAP_TEST(bitmap,*uc) ) {
1917 while ( uc <= (U8*)last_start && !BITMAP_TEST(bitmap,*uc) ) {
1923 if (uc >(U8*)last_start) break;
1927 U8 *lpos= points[ (pointpos - trie->wordinfo[word].len) % maxlen ];
1928 if (!leftmost || lpos < leftmost) {
1929 DEBUG_r(accepted_word=word);
1935 points[pointpos++ % maxlen]= uc;
1936 if (foldlen || uc < (U8*)strend) {
1937 REXEC_TRIE_READ_CHAR(trie_type, trie,
1939 uscan, len, uvc, charid, foldlen,
1941 DEBUG_TRIE_EXECUTE_r({
1942 dump_exec_pos( (char *)uc, c, strend,
1943 real_start, s, utf8_target);
1944 PerlIO_printf(Perl_debug_log,
1945 " Charid:%3u CP:%4"UVxf" ",
1957 word = aho->states[ state ].wordnum;
1959 base = aho->states[ state ].trans.base;
1961 DEBUG_TRIE_EXECUTE_r({
1963 dump_exec_pos( (char *)uc, c, strend, real_start,
1965 PerlIO_printf( Perl_debug_log,
1966 "%sState: %4"UVxf", word=%"UVxf,
1967 failed ? " Fail transition to " : "",
1968 (UV)state, (UV)word);
1974 ( ((offset = base + charid
1975 - 1 - trie->uniquecharcount)) >= 0)
1976 && ((U32)offset < trie->lasttrans)
1977 && trie->trans[offset].check == state
1978 && (tmp=trie->trans[offset].next))
1980 DEBUG_TRIE_EXECUTE_r(
1981 PerlIO_printf( Perl_debug_log," - legal\n"));
1986 DEBUG_TRIE_EXECUTE_r(
1987 PerlIO_printf( Perl_debug_log," - fail\n"));
1989 state = aho->fail[state];
1993 /* we must be accepting here */
1994 DEBUG_TRIE_EXECUTE_r(
1995 PerlIO_printf( Perl_debug_log," - accepting\n"));
2004 if (!state) state = 1;
2007 if ( aho->states[ state ].wordnum ) {
2008 U8 *lpos = points[ (pointpos - trie->wordinfo[aho->states[ state ].wordnum].len) % maxlen ];
2009 if (!leftmost || lpos < leftmost) {
2010 DEBUG_r(accepted_word=aho->states[ state ].wordnum);
2015 s = (char*)leftmost;
2016 DEBUG_TRIE_EXECUTE_r({
2018 Perl_debug_log,"Matches word #%"UVxf" at position %"IVdf". Trying full pattern...\n",
2019 (UV)accepted_word, (IV)(s - real_start)
2022 if (reginfo->intuit || regtry(reginfo, &s)) {
2028 DEBUG_TRIE_EXECUTE_r({
2029 PerlIO_printf( Perl_debug_log,"Pattern failed. Looking for new start point...\n");
2032 DEBUG_TRIE_EXECUTE_r(
2033 PerlIO_printf( Perl_debug_log,"No match.\n"));
2042 Perl_croak(aTHX_ "panic: unknown regstclass %d", (int)OP(c));
2052 - regexec_flags - match a regexp against a string
2055 Perl_regexec_flags(pTHX_ REGEXP * const rx, char *stringarg, char *strend,
2056 char *strbeg, I32 minend, SV *sv, void *data, U32 flags)
2057 /* stringarg: the point in the string at which to begin matching */
2058 /* strend: pointer to null at end of string */
2059 /* strbeg: real beginning of string */
2060 /* minend: end of match must be >= minend bytes after stringarg. */
2061 /* sv: SV being matched: only used for utf8 flag, pos() etc; string
2062 * itself is accessed via the pointers above */
2063 /* data: May be used for some additional optimizations.
2064 Currently its only used, with a U32 cast, for transmitting
2065 the ganch offset when doing a /g match. This will change */
2066 /* nosave: For optimizations. */
2070 struct regexp *const prog = ReANY(rx);
2073 char *startpos = stringarg;
2074 I32 minlen; /* must match at least this many chars */
2075 I32 dontbother = 0; /* how many characters not to try at end */
2076 I32 end_shift = 0; /* Same for the end. */ /* CC */
2077 I32 scream_pos = -1; /* Internal iterator of scream. */
2078 char *scream_olds = NULL;
2079 const bool utf8_target = cBOOL(DO_UTF8(sv));
2081 RXi_GET_DECL(prog,progi);
2082 regmatch_info reginfo_buf; /* create some info to pass to regtry etc */
2083 regmatch_info *const reginfo = ®info_buf;
2084 regexp_paren_pair *swap = NULL;
2086 GET_RE_DEBUG_FLAGS_DECL;
2088 PERL_ARGS_ASSERT_REGEXEC_FLAGS;
2089 PERL_UNUSED_ARG(data);
2091 /* Be paranoid... */
2092 if (prog == NULL || startpos == NULL) {
2093 Perl_croak(aTHX_ "NULL regexp parameter");
2098 debug_start_match(rx, utf8_target, startpos, strend,
2103 /* at the end of this function, we'll do a LEAVE_SCOPE(oldsave),
2104 * which will call destuctors to reset PL_regmatch_state, free higher
2105 * PL_regmatch_slabs, and clean up regmatch_info_aux and
2106 * regmatch_info_aux_eval */
2108 oldsave = PL_savestack_ix;
2110 multiline = prog->extflags & RXf_PMf_MULTILINE;
2111 minlen = prog->minlen;
2113 if (strend - startpos < (minlen+(prog->check_offset_min<0?prog->check_offset_min:0))) {
2114 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
2115 "String too short [regexec_flags]...\n"));
2119 /* Check validity of program. */
2120 if (UCHARAT(progi->program) != REG_MAGIC) {
2121 Perl_croak(aTHX_ "corrupted regexp program");
2124 RX_MATCH_TAINTED_off(rx);
2126 reginfo->prog = rx; /* Yes, sorry that this is confusing. */
2127 reginfo->intuit = 0;
2128 reginfo->is_utf8_target = cBOOL(utf8_target);
2129 reginfo->is_utf8_pat = cBOOL(RX_UTF8(rx));
2130 reginfo->warned = FALSE;
2131 reginfo->strbeg = strbeg;
2133 reginfo->poscache_maxiter = 0; /* not yet started a countdown */
2134 reginfo->strend = strend;
2135 /* see how far we have to get to not match where we matched before */
2136 reginfo->till = startpos+minend;
2138 /* reserve next 2 or 3 slots in PL_regmatch_state:
2139 * slot N+0: may currently be in use: skip it
2140 * slot N+1: use for regmatch_info_aux struct
2141 * slot N+2: use for regmatch_info_aux_eval struct if we have (?{})'s
2142 * slot N+3: ready for use by regmatch()
2146 regmatch_state *old_regmatch_state;
2147 regmatch_slab *old_regmatch_slab;
2148 int i, max = (prog->extflags & RXf_EVAL_SEEN) ? 2 : 1;
2150 /* on first ever match, allocate first slab */
2151 if (!PL_regmatch_slab) {
2152 Newx(PL_regmatch_slab, 1, regmatch_slab);
2153 PL_regmatch_slab->prev = NULL;
2154 PL_regmatch_slab->next = NULL;
2155 PL_regmatch_state = SLAB_FIRST(PL_regmatch_slab);
2158 old_regmatch_state = PL_regmatch_state;
2159 old_regmatch_slab = PL_regmatch_slab;
2161 for (i=0; i <= max; i++) {
2163 reginfo->info_aux = &(PL_regmatch_state->u.info_aux);
2165 reginfo->info_aux_eval =
2166 reginfo->info_aux->info_aux_eval =
2167 &(PL_regmatch_state->u.info_aux_eval);
2169 if (++PL_regmatch_state > SLAB_LAST(PL_regmatch_slab))
2170 PL_regmatch_state = S_push_slab(aTHX);
2173 /* note initial PL_regmatch_state position; at end of match we'll
2174 * pop back to there and free any higher slabs */
2176 reginfo->info_aux->old_regmatch_state = old_regmatch_state;
2177 reginfo->info_aux->old_regmatch_slab = old_regmatch_slab;
2178 reginfo->info_aux->poscache = NULL;
2180 SAVEDESTRUCTOR_X(S_cleanup_regmatch_info_aux, reginfo->info_aux);
2182 if ((prog->extflags & RXf_EVAL_SEEN))
2183 S_setup_eval_state(aTHX_ reginfo);
2185 reginfo->info_aux_eval = reginfo->info_aux->info_aux_eval = NULL;
2188 /* If there is a "must appear" string, look for it. */
2191 if (prog->extflags & RXf_GPOS_SEEN) { /* Need to set reginfo->ganch */
2193 if (flags & REXEC_IGNOREPOS){ /* Means: check only at start */
2194 reginfo->ganch = startpos + prog->gofs;
2195 DEBUG_GPOS_r(PerlIO_printf(Perl_debug_log,
2196 "GPOS IGNOREPOS: reginfo->ganch = startpos + %"UVxf"\n",(UV)prog->gofs));
2197 } else if (sv && SvTYPE(sv) >= SVt_PVMG
2199 && (mg = mg_find(sv, PERL_MAGIC_regex_global))
2200 && mg->mg_len >= 0) {
2201 reginfo->ganch = strbeg + mg->mg_len; /* Defined pos() */
2202 DEBUG_GPOS_r(PerlIO_printf(Perl_debug_log,
2203 "GPOS MAGIC: reginfo->ganch = strbeg + %"IVdf"\n",(IV)mg->mg_len));
2205 if (prog->extflags & RXf_ANCH_GPOS) {
2206 if (s > reginfo->ganch)
2208 s = reginfo->ganch - prog->gofs;
2209 DEBUG_GPOS_r(PerlIO_printf(Perl_debug_log,
2210 "GPOS ANCH_GPOS: s = ganch - %"UVxf"\n",(UV)prog->gofs));
2216 reginfo->ganch = strbeg + PTR2UV(data);
2217 DEBUG_GPOS_r(PerlIO_printf(Perl_debug_log,
2218 "GPOS DATA: reginfo->ganch= strbeg + %"UVxf"\n",PTR2UV(data)));
2220 } else { /* pos() not defined */
2221 reginfo->ganch = strbeg;
2222 DEBUG_GPOS_r(PerlIO_printf(Perl_debug_log,
2223 "GPOS: reginfo->ganch = strbeg\n"));
2226 if (PL_curpm && (PM_GETRE(PL_curpm) == rx)) {
2227 /* We have to be careful. If the previous successful match
2228 was from this regex we don't want a subsequent partially
2229 successful match to clobber the old results.
2230 So when we detect this possibility we add a swap buffer
2231 to the re, and switch the buffer each match. If we fail,
2232 we switch it back; otherwise we leave it swapped.
2235 /* do we need a save destructor here for eval dies? */
2236 Newxz(prog->offs, (prog->nparens + 1), regexp_paren_pair);
2237 DEBUG_BUFFERS_r(PerlIO_printf(Perl_debug_log,
2238 "rex=0x%"UVxf" saving offs: orig=0x%"UVxf" new=0x%"UVxf"\n",
2244 if (!(flags & REXEC_CHECKED) && (prog->check_substr != NULL || prog->check_utf8 != NULL)) {
2245 re_scream_pos_data d;
2247 d.scream_olds = &scream_olds;
2248 d.scream_pos = &scream_pos;
2249 s = re_intuit_start(rx, sv, strbeg, s, strend, flags, &d);
2251 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "Not present...\n"));
2252 goto phooey; /* not present */
2258 /* Simplest case: anchored match need be tried only once. */
2259 /* [unless only anchor is BOL and multiline is set] */
2260 if (prog->extflags & (RXf_ANCH & ~RXf_ANCH_GPOS)) {
2261 if (s == startpos && regtry(reginfo, &startpos))
2263 else if (multiline || (prog->intflags & PREGf_IMPLICIT)
2264 || (prog->extflags & RXf_ANCH_MBOL)) /* XXXX SBOL? */
2269 dontbother = minlen - 1;
2270 end = HOP3c(strend, -dontbother, strbeg) - 1;
2271 /* for multiline we only have to try after newlines */
2272 if (prog->check_substr || prog->check_utf8) {
2273 /* because of the goto we can not easily reuse the macros for bifurcating the
2274 unicode/non-unicode match modes here like we do elsewhere - demerphq */
2277 goto after_try_utf8;
2279 if (regtry(reginfo, &s)) {
2286 if (prog->extflags & RXf_USE_INTUIT) {
2287 s = re_intuit_start(rx, sv, strbeg,
2288 s + UTF8SKIP(s), strend, flags, NULL);
2297 } /* end search for check string in unicode */
2299 if (s == startpos) {
2300 goto after_try_latin;
2303 if (regtry(reginfo, &s)) {
2310 if (prog->extflags & RXf_USE_INTUIT) {
2311 s = re_intuit_start(rx, sv, strbeg,
2312 s + 1, strend, flags, NULL);
2321 } /* end search for check string in latin*/
2322 } /* end search for check string */
2323 else { /* search for newline */
2325 /*XXX: The s-- is almost definitely wrong here under unicode - demeprhq*/
2328 /* We can use a more efficient search as newlines are the same in unicode as they are in latin */
2329 while (s <= end) { /* note it could be possible to match at the end of the string */
2330 if (*s++ == '\n') { /* don't need PL_utf8skip here */
2331 if (regtry(reginfo, &s))
2335 } /* end search for newline */
2336 } /* end anchored/multiline check string search */
2338 } else if (RXf_GPOS_CHECK == (prog->extflags & RXf_GPOS_CHECK))
2340 /* the warning about reginfo->ganch being used without initialization
2341 is bogus -- we set it above, when prog->extflags & RXf_GPOS_SEEN
2342 and we only enter this block when the same bit is set. */
2343 char *tmp_s = reginfo->ganch - prog->gofs;
2345 if (tmp_s >= strbeg && regtry(reginfo, &tmp_s))
2350 /* Messy cases: unanchored match. */
2351 if ((prog->anchored_substr || prog->anchored_utf8) && prog->intflags & PREGf_SKIP) {
2352 /* we have /x+whatever/ */
2353 /* it must be a one character string (XXXX Except is_utf8_pat?) */
2359 if (! prog->anchored_utf8) {
2360 to_utf8_substr(prog);
2362 ch = SvPVX_const(prog->anchored_utf8)[0];
2365 DEBUG_EXECUTE_r( did_match = 1 );
2366 if (regtry(reginfo, &s)) goto got_it;
2368 while (s < strend && *s == ch)
2375 if (! prog->anchored_substr) {
2376 if (! to_byte_substr(prog)) {
2377 NON_UTF8_TARGET_BUT_UTF8_REQUIRED(phooey);
2380 ch = SvPVX_const(prog->anchored_substr)[0];
2383 DEBUG_EXECUTE_r( did_match = 1 );
2384 if (regtry(reginfo, &s)) goto got_it;
2386 while (s < strend && *s == ch)
2391 DEBUG_EXECUTE_r(if (!did_match)
2392 PerlIO_printf(Perl_debug_log,
2393 "Did not find anchored character...\n")
2396 else if (prog->anchored_substr != NULL
2397 || prog->anchored_utf8 != NULL
2398 || ((prog->float_substr != NULL || prog->float_utf8 != NULL)
2399 && prog->float_max_offset < strend - s)) {
2404 char *last1; /* Last position checked before */
2408 if (prog->anchored_substr || prog->anchored_utf8) {
2410 if (! prog->anchored_utf8) {
2411 to_utf8_substr(prog);
2413 must = prog->anchored_utf8;
2416 if (! prog->anchored_substr) {
2417 if (! to_byte_substr(prog)) {
2418 NON_UTF8_TARGET_BUT_UTF8_REQUIRED(phooey);
2421 must = prog->anchored_substr;
2423 back_max = back_min = prog->anchored_offset;
2426 if (! prog->float_utf8) {
2427 to_utf8_substr(prog);
2429 must = prog->float_utf8;
2432 if (! prog->float_substr) {
2433 if (! to_byte_substr(prog)) {
2434 NON_UTF8_TARGET_BUT_UTF8_REQUIRED(phooey);
2437 must = prog->float_substr;
2439 back_max = prog->float_max_offset;
2440 back_min = prog->float_min_offset;
2446 last = HOP3c(strend, /* Cannot start after this */
2447 -(I32)(CHR_SVLEN(must)
2448 - (SvTAIL(must) != 0) + back_min), strbeg);
2450 if (s > reginfo->strbeg)
2451 last1 = HOPc(s, -1);
2453 last1 = s - 1; /* bogus */
2455 /* XXXX check_substr already used to find "s", can optimize if
2456 check_substr==must. */
2458 dontbother = end_shift;
2459 strend = HOPc(strend, -dontbother);
2460 while ( (s <= last) &&
2461 (s = fbm_instr((unsigned char*)HOP3(s, back_min, (back_min<0 ? strbeg : strend)),
2462 (unsigned char*)strend, must,
2463 multiline ? FBMrf_MULTILINE : 0)) ) {
2464 DEBUG_EXECUTE_r( did_match = 1 );
2465 if (HOPc(s, -back_max) > last1) {
2466 last1 = HOPc(s, -back_min);
2467 s = HOPc(s, -back_max);
2470 char * const t = (last1 >= reginfo->strbeg)
2471 ? HOPc(last1, 1) : last1 + 1;
2473 last1 = HOPc(s, -back_min);
2477 while (s <= last1) {
2478 if (regtry(reginfo, &s))
2481 s++; /* to break out of outer loop */
2488 while (s <= last1) {
2489 if (regtry(reginfo, &s))
2495 DEBUG_EXECUTE_r(if (!did_match) {
2496 RE_PV_QUOTED_DECL(quoted, utf8_target, PERL_DEBUG_PAD_ZERO(0),
2497 SvPVX_const(must), RE_SV_DUMPLEN(must), 30);
2498 PerlIO_printf(Perl_debug_log, "Did not find %s substr %s%s...\n",
2499 ((must == prog->anchored_substr || must == prog->anchored_utf8)
2500 ? "anchored" : "floating"),
2501 quoted, RE_SV_TAIL(must));
2505 else if ( (c = progi->regstclass) ) {
2507 const OPCODE op = OP(progi->regstclass);
2508 /* don't bother with what can't match */
2509 if (PL_regkind[op] != EXACT && op != CANY && PL_regkind[op] != TRIE)
2510 strend = HOPc(strend, -(minlen - 1));
2513 SV * const prop = sv_newmortal();
2514 regprop(prog, prop, c);
2516 RE_PV_QUOTED_DECL(quoted,utf8_target,PERL_DEBUG_PAD_ZERO(1),
2518 PerlIO_printf(Perl_debug_log,
2519 "Matching stclass %.*s against %s (%d bytes)\n",
2520 (int)SvCUR(prop), SvPVX_const(prop),
2521 quoted, (int)(strend - s));
2524 if (find_byclass(prog, c, s, strend, reginfo))
2526 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "Contradicts stclass... [regexec_flags]\n"));
2530 if (prog->float_substr != NULL || prog->float_utf8 != NULL) {
2538 if (! prog->float_utf8) {
2539 to_utf8_substr(prog);
2541 float_real = prog->float_utf8;
2544 if (! prog->float_substr) {
2545 if (! to_byte_substr(prog)) {
2546 NON_UTF8_TARGET_BUT_UTF8_REQUIRED(phooey);
2549 float_real = prog->float_substr;
2552 little = SvPV_const(float_real, len);
2553 if (SvTAIL(float_real)) {
2554 /* This means that float_real contains an artificial \n on
2555 * the end due to the presence of something like this:
2556 * /foo$/ where we can match both "foo" and "foo\n" at the
2557 * end of the string. So we have to compare the end of the
2558 * string first against the float_real without the \n and
2559 * then against the full float_real with the string. We
2560 * have to watch out for cases where the string might be
2561 * smaller than the float_real or the float_real without
2563 char *checkpos= strend - len;
2565 PerlIO_printf(Perl_debug_log,
2566 "%sChecking for float_real.%s\n",
2567 PL_colors[4], PL_colors[5]));
2568 if (checkpos + 1 < strbeg) {
2569 /* can't match, even if we remove the trailing \n
2570 * string is too short to match */
2572 PerlIO_printf(Perl_debug_log,
2573 "%sString shorter than required trailing substring, cannot match.%s\n",
2574 PL_colors[4], PL_colors[5]));
2576 } else if (memEQ(checkpos + 1, little, len - 1)) {
2577 /* can match, the end of the string matches without the
2579 last = checkpos + 1;
2580 } else if (checkpos < strbeg) {
2581 /* cant match, string is too short when the "\n" is
2584 PerlIO_printf(Perl_debug_log,
2585 "%sString does not contain required trailing substring, cannot match.%s\n",
2586 PL_colors[4], PL_colors[5]));
2588 } else if (!multiline) {
2589 /* non multiline match, so compare with the "\n" at the
2590 * end of the string */
2591 if (memEQ(checkpos, little, len)) {
2595 PerlIO_printf(Perl_debug_log,
2596 "%sString does not contain required trailing substring, cannot match.%s\n",
2597 PL_colors[4], PL_colors[5]));
2601 /* multiline match, so we have to search for a place
2602 * where the full string is located */
2608 last = rninstr(s, strend, little, little + len);
2610 last = strend; /* matching "$" */
2613 /* at one point this block contained a comment which was
2614 * probably incorrect, which said that this was a "should not
2615 * happen" case. Even if it was true when it was written I am
2616 * pretty sure it is not anymore, so I have removed the comment
2617 * and replaced it with this one. Yves */
2619 PerlIO_printf(Perl_debug_log,
2620 "String does not contain required substring, cannot match.\n"
2624 dontbother = strend - last + prog->float_min_offset;
2626 if (minlen && (dontbother < minlen))
2627 dontbother = minlen - 1;
2628 strend -= dontbother; /* this one's always in bytes! */
2629 /* We don't know much -- general case. */
2632 if (regtry(reginfo, &s))
2641 if (regtry(reginfo, &s))
2643 } while (s++ < strend);
2653 PerlIO_printf(Perl_debug_log,
2654 "rex=0x%"UVxf" freeing offs: 0x%"UVxf"\n",
2661 /* clean up; this will trigger destructors that will free all slabs
2662 * above the current one, and cleanup the regmatch_info_aux
2663 * and regmatch_info_aux_eval sructs */
2665 LEAVE_SCOPE(oldsave);
2667 if (RXp_PAREN_NAMES(prog))
2668 (void)hv_iterinit(RXp_PAREN_NAMES(prog));
2670 RX_MATCH_UTF8_set(rx, utf8_target);
2672 /* make sure $`, $&, $', and $digit will work later */
2673 if ( !(flags & REXEC_NOT_FIRST) ) {
2674 if (flags & REXEC_COPY_STR) {
2678 PerlIO_printf(Perl_debug_log,
2679 "Copy on write: regexp capture, type %d\n",
2682 RX_MATCH_COPY_FREE(rx);
2683 prog->saved_copy = sv_setsv_cow(prog->saved_copy, sv);
2684 prog->subbeg = (char *)SvPVX_const(prog->saved_copy);
2685 assert (SvPOKp(prog->saved_copy));
2686 prog->sublen = reginfo->strend - strbeg;
2687 prog->suboffset = 0;
2688 prog->subcoffset = 0;
2693 I32 max = reginfo->strend - strbeg;
2696 if ( (flags & REXEC_COPY_SKIP_POST)
2697 && !(RX_EXTFLAGS(rx) & RXf_PMf_KEEPCOPY) /* //p */
2698 && !(PL_sawampersand & SAWAMPERSAND_RIGHT)
2699 ) { /* don't copy $' part of string */
2702 /* calculate the right-most part of the string covered
2703 * by a capture. Due to look-ahead, this may be to
2704 * the right of $&, so we have to scan all captures */
2705 while (n <= prog->lastparen) {
2706 if (prog->offs[n].end > max)
2707 max = prog->offs[n].end;
2711 max = (PL_sawampersand & SAWAMPERSAND_LEFT)
2712 ? prog->offs[0].start
2714 assert(max >= 0 && max <= reginfo->strend - strbeg);
2717 if ( (flags & REXEC_COPY_SKIP_PRE)
2718 && !(RX_EXTFLAGS(rx) & RXf_PMf_KEEPCOPY) /* //p */
2719 && !(PL_sawampersand & SAWAMPERSAND_LEFT)
2720 ) { /* don't copy $` part of string */
2723 /* calculate the left-most part of the string covered
2724 * by a capture. Due to look-behind, this may be to
2725 * the left of $&, so we have to scan all captures */
2726 while (min && n <= prog->lastparen) {
2727 if ( prog->offs[n].start != -1
2728 && prog->offs[n].start < min)
2730 min = prog->offs[n].start;
2734 if ((PL_sawampersand & SAWAMPERSAND_RIGHT)
2735 && min > prog->offs[0].end
2737 min = prog->offs[0].end;
2741 assert(min >= 0 && min <= max
2742 && min <= reginfo->strend - strbeg);
2745 if (RX_MATCH_COPIED(rx)) {
2746 if (sublen > prog->sublen)
2748 (char*)saferealloc(prog->subbeg, sublen+1);
2751 prog->subbeg = (char*)safemalloc(sublen+1);
2752 Copy(strbeg + min, prog->subbeg, sublen, char);
2753 prog->subbeg[sublen] = '\0';
2754 prog->suboffset = min;
2755 prog->sublen = sublen;
2756 RX_MATCH_COPIED_on(rx);
2758 prog->subcoffset = prog->suboffset;
2759 if (prog->suboffset && utf8_target) {
2760 /* Convert byte offset to chars.
2761 * XXX ideally should only compute this if @-/@+
2762 * has been seen, a la PL_sawampersand ??? */
2764 /* If there's a direct correspondence between the
2765 * string which we're matching and the original SV,
2766 * then we can use the utf8 len cache associated with
2767 * the SV. In particular, it means that under //g,
2768 * sv_pos_b2u() will use the previously cached
2769 * position to speed up working out the new length of
2770 * subcoffset, rather than counting from the start of
2771 * the string each time. This stops
2772 * $x = "\x{100}" x 1E6; 1 while $x =~ /(.)/g;
2773 * from going quadratic */
2774 if (SvPOKp(sv) && SvPVX(sv) == strbeg)
2775 sv_pos_b2u(sv, &(prog->subcoffset));
2777 prog->subcoffset = utf8_length((U8*)strbeg,
2778 (U8*)(strbeg+prog->suboffset));
2782 RX_MATCH_COPY_FREE(rx);
2783 prog->subbeg = strbeg;
2784 prog->suboffset = 0;
2785 prog->subcoffset = 0;
2786 /* use reginfo->strend, as strend may have been modified */
2787 prog->sublen = reginfo->strend - strbeg;
2794 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "%sMatch failed%s\n",
2795 PL_colors[4], PL_colors[5]));
2797 /* clean up; this will trigger destructors that will free all slabs
2798 * above the current one, and cleanup the regmatch_info_aux
2799 * and regmatch_info_aux_eval sructs */
2801 LEAVE_SCOPE(oldsave);
2804 /* we failed :-( roll it back */
2805 DEBUG_BUFFERS_r(PerlIO_printf(Perl_debug_log,
2806 "rex=0x%"UVxf" rolling back offs: freeing=0x%"UVxf" restoring=0x%"UVxf"\n",
2811 Safefree(prog->offs);
2818 /* Set which rex is pointed to by PL_reg_curpm, handling ref counting.
2819 * Do inc before dec, in case old and new rex are the same */
2820 #define SET_reg_curpm(Re2) \
2821 if (reginfo->info_aux_eval) { \
2822 (void)ReREFCNT_inc(Re2); \
2823 ReREFCNT_dec(PM_GETRE(PL_reg_curpm)); \
2824 PM_SETRE((PL_reg_curpm), (Re2)); \
2829 - regtry - try match at specific point
2831 STATIC I32 /* 0 failure, 1 success */
2832 S_regtry(pTHX_ regmatch_info *reginfo, char **startposp)
2836 REGEXP *const rx = reginfo->prog;
2837 regexp *const prog = ReANY(rx);
2839 RXi_GET_DECL(prog,progi);
2840 GET_RE_DEBUG_FLAGS_DECL;
2842 PERL_ARGS_ASSERT_REGTRY;
2844 reginfo->cutpoint=NULL;
2846 prog->offs[0].start = *startposp - reginfo->strbeg;
2847 prog->lastparen = 0;
2848 prog->lastcloseparen = 0;
2850 /* XXXX What this code is doing here?!!! There should be no need
2851 to do this again and again, prog->lastparen should take care of
2854 /* Tests pat.t#187 and split.t#{13,14} seem to depend on this code.
2855 * Actually, the code in regcppop() (which Ilya may be meaning by
2856 * prog->lastparen), is not needed at all by the test suite
2857 * (op/regexp, op/pat, op/split), but that code is needed otherwise
2858 * this erroneously leaves $1 defined: "1" =~ /^(?:(\d)x)?\d$/
2859 * Meanwhile, this code *is* needed for the
2860 * above-mentioned test suite tests to succeed. The common theme
2861 * on those tests seems to be returning null fields from matches.
2862 * --jhi updated by dapm */
2864 if (prog->nparens) {
2865 regexp_paren_pair *pp = prog->offs;
2867 for (i = prog->nparens; i > (I32)prog->lastparen; i--) {
2875 result = regmatch(reginfo, *startposp, progi->program + 1);
2877 prog->offs[0].end = result;
2880 if (reginfo->cutpoint)
2881 *startposp= reginfo->cutpoint;
2882 REGCP_UNWIND(lastcp);
2887 #define sayYES goto yes
2888 #define sayNO goto no
2889 #define sayNO_SILENT goto no_silent
2891 /* we dont use STMT_START/END here because it leads to
2892 "unreachable code" warnings, which are bogus, but distracting. */
2893 #define CACHEsayNO \
2894 if (ST.cache_mask) \
2895 reginfo->info_aux->poscache[ST.cache_offset] |= ST.cache_mask; \
2898 /* this is used to determine how far from the left messages like
2899 'failed...' are printed. It should be set such that messages
2900 are inline with the regop output that created them.
2902 #define REPORT_CODE_OFF 32
2905 #define CHRTEST_UNINIT -1001 /* c1/c2 haven't been calculated yet */
2906 #define CHRTEST_VOID -1000 /* the c1/c2 "next char" test should be skipped */
2907 #define CHRTEST_NOT_A_CP_1 -999
2908 #define CHRTEST_NOT_A_CP_2 -998
2910 /* grab a new slab and return the first slot in it */
2912 STATIC regmatch_state *
2915 #if PERL_VERSION < 9 && !defined(PERL_CORE)
2918 regmatch_slab *s = PL_regmatch_slab->next;
2920 Newx(s, 1, regmatch_slab);
2921 s->prev = PL_regmatch_slab;
2923 PL_regmatch_slab->next = s;
2925 PL_regmatch_slab = s;
2926 return SLAB_FIRST(s);
2930 /* push a new state then goto it */
2932 #define PUSH_STATE_GOTO(state, node, input) \
2933 pushinput = input; \
2935 st->resume_state = state; \
2938 /* push a new state with success backtracking, then goto it */
2940 #define PUSH_YES_STATE_GOTO(state, node, input) \
2941 pushinput = input; \
2943 st->resume_state = state; \
2944 goto push_yes_state;
2951 regmatch() - main matching routine
2953 This is basically one big switch statement in a loop. We execute an op,
2954 set 'next' to point the next op, and continue. If we come to a point which
2955 we may need to backtrack to on failure such as (A|B|C), we push a
2956 backtrack state onto the backtrack stack. On failure, we pop the top
2957 state, and re-enter the loop at the state indicated. If there are no more
2958 states to pop, we return failure.
2960 Sometimes we also need to backtrack on success; for example /A+/, where
2961 after successfully matching one A, we need to go back and try to
2962 match another one; similarly for lookahead assertions: if the assertion
2963 completes successfully, we backtrack to the state just before the assertion
2964 and then carry on. In these cases, the pushed state is marked as
2965 'backtrack on success too'. This marking is in fact done by a chain of
2966 pointers, each pointing to the previous 'yes' state. On success, we pop to
2967 the nearest yes state, discarding any intermediate failure-only states.
2968 Sometimes a yes state is pushed just to force some cleanup code to be
2969 called at the end of a successful match or submatch; e.g. (??{$re}) uses
2970 it to free the inner regex.
2972 Note that failure backtracking rewinds the cursor position, while
2973 success backtracking leaves it alone.
2975 A pattern is complete when the END op is executed, while a subpattern
2976 such as (?=foo) is complete when the SUCCESS op is executed. Both of these
2977 ops trigger the "pop to last yes state if any, otherwise return true"
2980 A common convention in this function is to use A and B to refer to the two
2981 subpatterns (or to the first nodes thereof) in patterns like /A*B/: so A is
2982 the subpattern to be matched possibly multiple times, while B is the entire
2983 rest of the pattern. Variable and state names reflect this convention.
2985 The states in the main switch are the union of ops and failure/success of
2986 substates associated with with that op. For example, IFMATCH is the op
2987 that does lookahead assertions /(?=A)B/ and so the IFMATCH state means
2988 'execute IFMATCH'; while IFMATCH_A is a state saying that we have just
2989 successfully matched A and IFMATCH_A_fail is a state saying that we have
2990 just failed to match A. Resume states always come in pairs. The backtrack
2991 state we push is marked as 'IFMATCH_A', but when that is popped, we resume
2992 at IFMATCH_A or IFMATCH_A_fail, depending on whether we are backtracking
2993 on success or failure.
2995 The struct that holds a backtracking state is actually a big union, with
2996 one variant for each major type of op. The variable st points to the
2997 top-most backtrack struct. To make the code clearer, within each
2998 block of code we #define ST to alias the relevant union.
3000 Here's a concrete example of a (vastly oversimplified) IFMATCH
3006 #define ST st->u.ifmatch
3008 case IFMATCH: // we are executing the IFMATCH op, (?=A)B
3009 ST.foo = ...; // some state we wish to save
3011 // push a yes backtrack state with a resume value of
3012 // IFMATCH_A/IFMATCH_A_fail, then continue execution at the
3014 PUSH_YES_STATE_GOTO(IFMATCH_A, A, newinput);
3017 case IFMATCH_A: // we have successfully executed A; now continue with B
3019 bar = ST.foo; // do something with the preserved value
3022 case IFMATCH_A_fail: // A failed, so the assertion failed
3023 ...; // do some housekeeping, then ...
3024 sayNO; // propagate the failure
3031 For any old-timers reading this who are familiar with the old recursive
3032 approach, the code above is equivalent to:
3034 case IFMATCH: // we are executing the IFMATCH op, (?=A)B
3043 ...; // do some housekeeping, then ...
3044 sayNO; // propagate the failure
3047 The topmost backtrack state, pointed to by st, is usually free. If you
3048 want to claim it, populate any ST.foo fields in it with values you wish to
3049 save, then do one of
3051 PUSH_STATE_GOTO(resume_state, node, newinput);
3052 PUSH_YES_STATE_GOTO(resume_state, node, newinput);
3054 which sets that backtrack state's resume value to 'resume_state', pushes a
3055 new free entry to the top of the backtrack stack, then goes to 'node'.
3056 On backtracking, the free slot is popped, and the saved state becomes the
3057 new free state. An ST.foo field in this new top state can be temporarily
3058 accessed to retrieve values, but once the main loop is re-entered, it
3059 becomes available for reuse.
3061 Note that the depth of the backtrack stack constantly increases during the
3062 left-to-right execution of the pattern, rather than going up and down with
3063 the pattern nesting. For example the stack is at its maximum at Z at the
3064 end of the pattern, rather than at X in the following:
3066 /(((X)+)+)+....(Y)+....Z/
3068 The only exceptions to this are lookahead/behind assertions and the cut,
3069 (?>A), which pop all the backtrack states associated with A before
3072 Backtrack state structs are allocated in slabs of about 4K in size.
3073 PL_regmatch_state and st always point to the currently active state,
3074 and PL_regmatch_slab points to the slab currently containing
3075 PL_regmatch_state. The first time regmatch() is called, the first slab is
3076 allocated, and is never freed until interpreter destruction. When the slab
3077 is full, a new one is allocated and chained to the end. At exit from
3078 regmatch(), slabs allocated since entry are freed.
3083 #define DEBUG_STATE_pp(pp) \
3085 DUMP_EXEC_POS(locinput, scan, utf8_target); \
3086 PerlIO_printf(Perl_debug_log, \
3087 " %*s"pp" %s%s%s%s%s\n", \
3089 PL_reg_name[st->resume_state], \
3090 ((st==yes_state||st==mark_state) ? "[" : ""), \
3091 ((st==yes_state) ? "Y" : ""), \
3092 ((st==mark_state) ? "M" : ""), \
3093 ((st==yes_state||st==mark_state) ? "]" : "") \
3098 #define REG_NODE_NUM(x) ((x) ? (int)((x)-prog) : -1)
3103 S_debug_start_match(pTHX_ const REGEXP *prog, const bool utf8_target,
3104 const char *start, const char *end, const char *blurb)
3106 const bool utf8_pat = RX_UTF8(prog) ? 1 : 0;
3108 PERL_ARGS_ASSERT_DEBUG_START_MATCH;
3113 RE_PV_QUOTED_DECL(s0, utf8_pat, PERL_DEBUG_PAD_ZERO(0),
3114 RX_PRECOMP_const(prog), RX_PRELEN(prog), 60);
3116 RE_PV_QUOTED_DECL(s1, utf8_target, PERL_DEBUG_PAD_ZERO(1),
3117 start, end - start, 60);
3119 PerlIO_printf(Perl_debug_log,
3120 "%s%s REx%s %s against %s\n",
3121 PL_colors[4], blurb, PL_colors[5], s0, s1);
3123 if (utf8_target||utf8_pat)
3124 PerlIO_printf(Perl_debug_log, "UTF-8 %s%s%s...\n",
3125 utf8_pat ? "pattern" : "",
3126 utf8_pat && utf8_target ? " and " : "",
3127 utf8_target ? "string" : ""
3133 S_dump_exec_pos(pTHX_ const char *locinput,
3134 const regnode *scan,
3135 const char *loc_regeol,
3136 const char *loc_bostr,
3137 const char *loc_reg_starttry,
3138 const bool utf8_target)
3140 const int docolor = *PL_colors[0] || *PL_colors[2] || *PL_colors[4];
3141 const int taill = (docolor ? 10 : 7); /* 3 chars for "> <" */
3142 int l = (loc_regeol - locinput) > taill ? taill : (loc_regeol - locinput);
3143 /* The part of the string before starttry has one color
3144 (pref0_len chars), between starttry and current
3145 position another one (pref_len - pref0_len chars),
3146 after the current position the third one.
3147 We assume that pref0_len <= pref_len, otherwise we
3148 decrease pref0_len. */
3149 int pref_len = (locinput - loc_bostr) > (5 + taill) - l
3150 ? (5 + taill) - l : locinput - loc_bostr;
3153 PERL_ARGS_ASSERT_DUMP_EXEC_POS;
3155 while (utf8_target && UTF8_IS_CONTINUATION(*(U8*)(locinput - pref_len)))
3157 pref0_len = pref_len - (locinput - loc_reg_starttry);
3158 if (l + pref_len < (5 + taill) && l < loc_regeol - locinput)
3159 l = ( loc_regeol - locinput > (5 + taill) - pref_len
3160 ? (5 + taill) - pref_len : loc_regeol - locinput);
3161 while (utf8_target && UTF8_IS_CONTINUATION(*(U8*)(locinput + l)))
3165 if (pref0_len > pref_len)
3166 pref0_len = pref_len;
3168 const int is_uni = (utf8_target && OP(scan) != CANY) ? 1 : 0;
3170 RE_PV_COLOR_DECL(s0,len0,is_uni,PERL_DEBUG_PAD(0),
3171 (locinput - pref_len),pref0_len, 60, 4, 5);
3173 RE_PV_COLOR_DECL(s1,len1,is_uni,PERL_DEBUG_PAD(1),
3174 (locinput - pref_len + pref0_len),
3175 pref_len - pref0_len, 60, 2, 3);
3177 RE_PV_COLOR_DECL(s2,len2,is_uni,PERL_DEBUG_PAD(2),
3178 locinput, loc_regeol - locinput, 10, 0, 1);
3180 const STRLEN tlen=len0+len1+len2;
3181 PerlIO_printf(Perl_debug_log,
3182 "%4"IVdf" <%.*s%.*s%s%.*s>%*s|",
3183 (IV)(locinput - loc_bostr),
3186 (docolor ? "" : "> <"),
3188 (int)(tlen > 19 ? 0 : 19 - tlen),
3195 /* reg_check_named_buff_matched()
3196 * Checks to see if a named buffer has matched. The data array of
3197 * buffer numbers corresponding to the buffer is expected to reside
3198 * in the regexp->data->data array in the slot stored in the ARG() of
3199 * node involved. Note that this routine doesn't actually care about the
3200 * name, that information is not preserved from compilation to execution.
3201 * Returns the index of the leftmost defined buffer with the given name
3202 * or 0 if non of the buffers matched.
3205 S_reg_check_named_buff_matched(pTHX_ const regexp *rex, const regnode *scan)
3208 RXi_GET_DECL(rex,rexi);
3209 SV *sv_dat= MUTABLE_SV(rexi->data->data[ ARG( scan ) ]);
3210 I32 *nums=(I32*)SvPVX(sv_dat);
3212 PERL_ARGS_ASSERT_REG_CHECK_NAMED_BUFF_MATCHED;
3214 for ( n=0; n<SvIVX(sv_dat); n++ ) {
3215 if ((I32)rex->lastparen >= nums[n] &&
3216 rex->offs[nums[n]].end != -1)
3226 S_setup_EXACTISH_ST_c1_c2(pTHX_ const regnode * const text_node, int *c1p,
3227 U8* c1_utf8, int *c2p, U8* c2_utf8, regmatch_info *reginfo)
3229 /* This function determines if there are one or two characters that match
3230 * the first character of the passed-in EXACTish node <text_node>, and if
3231 * so, returns them in the passed-in pointers.
3233 * If it determines that no possible character in the target string can
3234 * match, it returns FALSE; otherwise TRUE. (The FALSE situation occurs if
3235 * the first character in <text_node> requires UTF-8 to represent, and the
3236 * target string isn't in UTF-8.)
3238 * If there are more than two characters that could match the beginning of
3239 * <text_node>, or if more context is required to determine a match or not,
3240 * it sets both *<c1p> and *<c2p> to CHRTEST_VOID.
3242 * The motiviation behind this function is to allow the caller to set up
3243 * tight loops for matching. If <text_node> is of type EXACT, there is
3244 * only one possible character that can match its first character, and so
3245 * the situation is quite simple. But things get much more complicated if
3246 * folding is involved. It may be that the first character of an EXACTFish
3247 * node doesn't participate in any possible fold, e.g., punctuation, so it
3248 * can be matched only by itself. The vast majority of characters that are
3249 * in folds match just two things, their lower and upper-case equivalents.
3250 * But not all are like that; some have multiple possible matches, or match
3251 * sequences of more than one character. This function sorts all that out.
3253 * Consider the patterns A*B or A*?B where A and B are arbitrary. In a
3254 * loop of trying to match A*, we know we can't exit where the thing
3255 * following it isn't a B. And something can't be a B unless it is the
3256 * beginning of B. By putting a quick test for that beginning in a tight
3257 * loop, we can rule out things that can't possibly be B without having to
3258 * break out of the loop, thus avoiding work. Similarly, if A is a single
3259 * character, we can make a tight loop matching A*, using the outputs of
3262 * If the target string to match isn't in UTF-8, and there aren't
3263 * complications which require CHRTEST_VOID, *<c1p> and *<c2p> are set to
3264 * the one or two possible octets (which are characters in this situation)
3265 * that can match. In all cases, if there is only one character that can
3266 * match, *<c1p> and *<c2p> will be identical.
3268 * If the target string is in UTF-8, the buffers pointed to by <c1_utf8>
3269 * and <c2_utf8> will contain the one or two UTF-8 sequences of bytes that
3270 * can match the beginning of <text_node>. They should be declared with at
3271 * least length UTF8_MAXBYTES+1. (If the target string isn't in UTF-8, it is
3272 * undefined what these contain.) If one or both of the buffers are
3273 * invariant under UTF-8, *<c1p>, and *<c2p> will also be set to the
3274 * corresponding invariant. If variant, the corresponding *<c1p> and/or
3275 * *<c2p> will be set to a negative number(s) that shouldn't match any code
3276 * point (unless inappropriately coerced to unsigned). *<c1p> will equal
3277 * *<c2p> if and only if <c1_utf8> and <c2_utf8> are the same. */
3279 const bool utf8_target = reginfo->is_utf8_target;
3281 UV c1 = CHRTEST_NOT_A_CP_1;
3282 UV c2 = CHRTEST_NOT_A_CP_2;
3283 bool use_chrtest_void = FALSE;
3284 const bool is_utf8_pat = reginfo->is_utf8_pat;
3286 /* Used when we have both utf8 input and utf8 output, to avoid converting
3287 * to/from code points */
3288 bool utf8_has_been_setup = FALSE;
3292 U8 *pat = (U8*)STRING(text_node);
3294 if (OP(text_node) == EXACT) {
3296 /* In an exact node, only one thing can be matched, that first
3297 * character. If both the pat and the target are UTF-8, we can just
3298 * copy the input to the output, avoiding finding the code point of
3303 else if (utf8_target) {
3304 Copy(pat, c1_utf8, UTF8SKIP(pat), U8);
3305 Copy(pat, c2_utf8, UTF8SKIP(pat), U8);
3306 utf8_has_been_setup = TRUE;
3309 c2 = c1 = valid_utf8_to_uvchr(pat, NULL);
3312 else /* an EXACTFish node */
3314 && is_MULTI_CHAR_FOLD_utf8_safe(pat,
3315 pat + STR_LEN(text_node)))
3317 && is_MULTI_CHAR_FOLD_latin1_safe(pat,
3318 pat + STR_LEN(text_node))))
3320 /* Multi-character folds require more context to sort out. Also
3321 * PL_utf8_foldclosures used below doesn't handle them, so have to be
3322 * handled outside this routine */
3323 use_chrtest_void = TRUE;
3325 else { /* an EXACTFish node which doesn't begin with a multi-char fold */
3326 c1 = is_utf8_pat ? valid_utf8_to_uvchr(pat, NULL) : *pat;
3328 /* Load the folds hash, if not already done */
3330 if (! PL_utf8_foldclosures) {
3331 if (! PL_utf8_tofold) {
3332 U8 dummy[UTF8_MAXBYTES+1];
3334 /* Force loading this by folding an above-Latin1 char */
3335 to_utf8_fold((U8*) HYPHEN_UTF8, dummy, NULL);
3336 assert(PL_utf8_tofold); /* Verify that worked */
3338 PL_utf8_foldclosures = _swash_inversion_hash(PL_utf8_tofold);
3341 /* The fold closures data structure is a hash with the keys being
3342 * the UTF-8 of every character that is folded to, like 'k', and
3343 * the values each an array of all code points that fold to its
3344 * key. e.g. [ 'k', 'K', KELVIN_SIGN ]. Multi-character folds are
3346 if ((! (listp = hv_fetch(PL_utf8_foldclosures,
3351 /* Not found in the hash, therefore there are no folds
3352 * containing it, so there is only a single character that
3356 else { /* Does participate in folds */
3357 AV* list = (AV*) *listp;
3358 if (av_len(list) != 1) {
3360 /* If there aren't exactly two folds to this, it is outside
3361 * the scope of this function */
3362 use_chrtest_void = TRUE;
3364 else { /* There are two. Get them */
3365 SV** c_p = av_fetch(list, 0, FALSE);
3367 Perl_croak(aTHX_ "panic: invalid PL_utf8_foldclosures structure");
3371 c_p = av_fetch(list, 1, FALSE);
3373 Perl_croak(aTHX_ "panic: invalid PL_utf8_foldclosures structure");
3377 /* Folds that cross the 255/256 boundary are forbidden if
3378 * EXACTFL, or EXACTFA and one is ASCIII. Since the
3379 * pattern character is above 256, and its only other match
3380 * is below 256, the only legal match will be to itself.
3381 * We have thrown away the original, so have to compute
3382 * which is the one above 255 */
3383 if ((c1 < 256) != (c2 < 256)) {
3384 if (OP(text_node) == EXACTFL
3385 || (OP(text_node) == EXACTFA
3386 && (isASCII(c1) || isASCII(c2))))
3399 else /* Here, c1 is < 255 */
3401 && HAS_NONLATIN1_FOLD_CLOSURE(c1)
3402 && OP(text_node) != EXACTFL
3403 && (OP(text_node) != EXACTFA || ! isASCII(c1)))
3405 /* Here, there could be something above Latin1 in the target which
3406 * folds to this character in the pattern. All such cases except
3407 * LATIN SMALL LETTER Y WITH DIAERESIS have more than two characters
3408 * involved in their folds, so are outside the scope of this
3410 if (UNLIKELY(c1 == LATIN_SMALL_LETTER_Y_WITH_DIAERESIS)) {
3411 c2 = LATIN_CAPITAL_LETTER_Y_WITH_DIAERESIS;
3414 use_chrtest_void = TRUE;
3417 else { /* Here nothing above Latin1 can fold to the pattern character */
3418 switch (OP(text_node)) {
3420 case EXACTFL: /* /l rules */
3421 c2 = PL_fold_locale[c1];
3425 if (! utf8_target) { /* /d rules */
3430 /* /u rules for all these. This happens to work for
3431 * EXACTFA as nothing in Latin1 folds to ASCII */
3433 case EXACTFU_TRICKYFOLD:
3436 c2 = PL_fold_latin1[c1];
3440 Perl_croak(aTHX_ "panic: Unexpected op %u", OP(text_node));
3441 assert(0); /* NOTREACHED */
3446 /* Here have figured things out. Set up the returns */
3447 if (use_chrtest_void) {
3448 *c2p = *c1p = CHRTEST_VOID;
3450 else if (utf8_target) {
3451 if (! utf8_has_been_setup) { /* Don't have the utf8; must get it */
3452 uvchr_to_utf8(c1_utf8, c1);
3453 uvchr_to_utf8(c2_utf8, c2);
3456 /* Invariants are stored in both the utf8 and byte outputs; Use
3457 * negative numbers otherwise for the byte ones. Make sure that the
3458 * byte ones are the same iff the utf8 ones are the same */
3459 *c1p = (UTF8_IS_INVARIANT(*c1_utf8)) ? *c1_utf8 : CHRTEST_NOT_A_CP_1;
3460 *c2p = (UTF8_IS_INVARIANT(*c2_utf8))
3463 ? CHRTEST_NOT_A_CP_1
3464 : CHRTEST_NOT_A_CP_2;
3466 else if (c1 > 255) {
3467 if (c2 > 255) { /* both possibilities are above what a non-utf8 string
3472 *c1p = *c2p = c2; /* c2 is the only representable value */
3474 else { /* c1 is representable; see about c2 */
3476 *c2p = (c2 < 256) ? c2 : c1;
3482 /* returns -1 on failure, $+[0] on success */
3484 S_regmatch(pTHX_ regmatch_info *reginfo, char *startpos, regnode *prog)
3486 #if PERL_VERSION < 9 && !defined(PERL_CORE)
3490 const bool utf8_target = reginfo->is_utf8_target;
3491 const U32 uniflags = UTF8_ALLOW_DEFAULT;
3492 REGEXP *rex_sv = reginfo->prog;
3493 regexp *rex = ReANY(rex_sv);
3494 RXi_GET_DECL(rex,rexi);
3495 /* the current state. This is a cached copy of PL_regmatch_state */
3497 /* cache heavy used fields of st in registers */
3500 U32 n = 0; /* general value; init to avoid compiler warning */
3501 I32 ln = 0; /* len or last; init to avoid compiler warning */
3502 char *locinput = startpos;
3503 char *pushinput; /* where to continue after a PUSH */
3504 I32 nextchr; /* is always set to UCHARAT(locinput) */
3506 bool result = 0; /* return value of S_regmatch */
3507 int depth = 0; /* depth of backtrack stack */
3508 U32 nochange_depth = 0; /* depth of GOSUB recursion with nochange */
3509 const U32 max_nochange_depth =
3510 (3 * rex->nparens > MAX_RECURSE_EVAL_NOCHANGE_DEPTH) ?
3511 3 * rex->nparens : MAX_RECURSE_EVAL_NOCHANGE_DEPTH;
3512 regmatch_state *yes_state = NULL; /* state to pop to on success of
3514 /* mark_state piggy backs on the yes_state logic so that when we unwind
3515 the stack on success we can update the mark_state as we go */
3516 regmatch_state *mark_state = NULL; /* last mark state we have seen */
3517 regmatch_state *cur_eval = NULL; /* most recent EVAL_AB state */
3518 struct regmatch_state *cur_curlyx = NULL; /* most recent curlyx */
3520 bool no_final = 0; /* prevent failure from backtracking? */
3521 bool do_cutgroup = 0; /* no_final only until next branch/trie entry */
3522 char *startpoint = locinput;
3523 SV *popmark = NULL; /* are we looking for a mark? */
3524 SV *sv_commit = NULL; /* last mark name seen in failure */
3525 SV *sv_yes_mark = NULL; /* last mark name we have seen
3526 during a successful match */
3527 U32 lastopen = 0; /* last open we saw */
3528 bool has_cutgroup = RX_HAS_CUTGROUP(rex) ? 1 : 0;
3529 SV* const oreplsv = GvSV(PL_replgv);
3530 /* these three flags are set by various ops to signal information to
3531 * the very next op. They have a useful lifetime of exactly one loop
3532 * iteration, and are not preserved or restored by state pushes/pops
3534 bool sw = 0; /* the condition value in (?(cond)a|b) */
3535 bool minmod = 0; /* the next "{n,m}" is a "{n,m}?" */
3536 int logical = 0; /* the following EVAL is:
3540 or the following IFMATCH/UNLESSM is:
3541 false: plain (?=foo)
3542 true: used as a condition: (?(?=foo))
3544 PAD* last_pad = NULL;
3546 I32 gimme = G_SCALAR;
3547 CV *caller_cv = NULL; /* who called us */
3548 CV *last_pushed_cv = NULL; /* most recently called (?{}) CV */
3549 CHECKPOINT runops_cp; /* savestack position before executing EVAL */
3550 U32 maxopenparen = 0; /* max '(' index seen so far */
3551 int to_complement; /* Invert the result? */
3552 _char_class_number classnum;
3553 bool is_utf8_pat = reginfo->is_utf8_pat;
3556 GET_RE_DEBUG_FLAGS_DECL;
3559 /* shut up 'may be used uninitialized' compiler warnings for dMULTICALL */
3560 multicall_oldcatch = 0;
3561 multicall_cv = NULL;
3563 PERL_UNUSED_VAR(multicall_cop);
3564 PERL_UNUSED_VAR(newsp);
3567 PERL_ARGS_ASSERT_REGMATCH;
3569 DEBUG_OPTIMISE_r( DEBUG_EXECUTE_r({
3570 PerlIO_printf(Perl_debug_log,"regmatch start\n");
3573 st = PL_regmatch_state;
3575 /* Note that nextchr is a byte even in UTF */
3578 while (scan != NULL) {
3581 SV * const prop = sv_newmortal();
3582 regnode *rnext=regnext(scan);
3583 DUMP_EXEC_POS( locinput, scan, utf8_target );
3584 regprop(rex, prop, scan);
3586 PerlIO_printf(Perl_debug_log,
3587 "%3"IVdf":%*s%s(%"IVdf")\n",
3588 (IV)(scan - rexi->program), depth*2, "",
3590 (PL_regkind[OP(scan)] == END || !rnext) ?
3591 0 : (IV)(rnext - rexi->program));
3594 next = scan + NEXT_OFF(scan);
3597 state_num = OP(scan);
3603 assert(nextchr < 256 && (nextchr >= 0 || nextchr == NEXTCHR_EOS));
3605 switch (state_num) {
3606 case BOL: /* /^../ */
3607 if (locinput == reginfo->strbeg)
3611 case MBOL: /* /^../m */
3612 if (locinput == reginfo->strbeg ||
3613 (!NEXTCHR_IS_EOS && locinput[-1] == '\n'))
3619 case SBOL: /* /^../s */
3620 if (locinput == reginfo->strbeg)
3625 if (locinput == reginfo->ganch)
3629 case KEEPS: /* \K */
3630 /* update the startpoint */
3631 st->u.keeper.val = rex->offs[0].start;
3632 rex->offs[0].start = locinput - reginfo->strbeg;
3633 PUSH_STATE_GOTO(KEEPS_next, next, locinput);
3634 assert(0); /*NOTREACHED*/
3635 case KEEPS_next_fail:
3636 /* rollback the start point change */
3637 rex->offs[0].start = st->u.keeper.val;
3639 assert(0); /*NOTREACHED*/
3641 case EOL: /* /..$/ */
3644 case MEOL: /* /..$/m */
3645 if (!NEXTCHR_IS_EOS && nextchr != '\n')
3649 case SEOL: /* /..$/s */
3651 if (!NEXTCHR_IS_EOS && nextchr != '\n')
3653 if (reginfo->strend - locinput > 1)
3658 if (!NEXTCHR_IS_EOS)
3662 case SANY: /* /./s */
3665 goto increment_locinput;
3673 case REG_ANY: /* /./ */
3674 if ((NEXTCHR_IS_EOS) || nextchr == '\n')
3676 goto increment_locinput;
3680 #define ST st->u.trie
3681 case TRIEC: /* (ab|cd) with known charclass */
3682 /* In this case the charclass data is available inline so
3683 we can fail fast without a lot of extra overhead.
3685 if(!NEXTCHR_IS_EOS && !ANYOF_BITMAP_TEST(scan, nextchr)) {
3687 PerlIO_printf(Perl_debug_log,
3688 "%*s %sfailed to match trie start class...%s\n",
3689 REPORT_CODE_OFF+depth*2, "", PL_colors[4], PL_colors[5])
3692 assert(0); /* NOTREACHED */
3695 case TRIE: /* (ab|cd) */
3696 /* the basic plan of execution of the trie is:
3697 * At the beginning, run though all the states, and
3698 * find the longest-matching word. Also remember the position
3699 * of the shortest matching word. For example, this pattern:
3702 * when matched against the string "abcde", will generate
3703 * accept states for all words except 3, with the longest
3704 * matching word being 4, and the shortest being 2 (with
3705 * the position being after char 1 of the string).
3707 * Then for each matching word, in word order (i.e. 1,2,4,5),
3708 * we run the remainder of the pattern; on each try setting
3709 * the current position to the character following the word,
3710 * returning to try the next word on failure.
3712 * We avoid having to build a list of words at runtime by
3713 * using a compile-time structure, wordinfo[].prev, which
3714 * gives, for each word, the previous accepting word (if any).
3715 * In the case above it would contain the mappings 1->2, 2->0,
3716 * 3->0, 4->5, 5->1. We can use this table to generate, from
3717 * the longest word (4 above), a list of all words, by
3718 * following the list of prev pointers; this gives us the
3719 * unordered list 4,5,1,2. Then given the current word we have
3720 * just tried, we can go through the list and find the
3721 * next-biggest word to try (so if we just failed on word 2,
3722 * the next in the list is 4).
3724 * Since at runtime we don't record the matching position in
3725 * the string for each word, we have to work that out for
3726 * each word we're about to process. The wordinfo table holds
3727 * the character length of each word; given that we recorded
3728 * at the start: the position of the shortest word and its
3729 * length in chars, we just need to move the pointer the
3730 * difference between the two char lengths. Depending on
3731 * Unicode status and folding, that's cheap or expensive.
3733 * This algorithm is optimised for the case where are only a
3734 * small number of accept states, i.e. 0,1, or maybe 2.
3735 * With lots of accepts states, and having to try all of them,
3736 * it becomes quadratic on number of accept states to find all
3741 /* what type of TRIE am I? (utf8 makes this contextual) */
3742 DECL_TRIE_TYPE(scan);
3744 /* what trie are we using right now */
3745 reg_trie_data * const trie
3746 = (reg_trie_data*)rexi->data->data[ ARG( scan ) ];
3747 HV * widecharmap = MUTABLE_HV(rexi->data->data[ ARG( scan ) + 1 ]);
3748 U32 state = trie->startstate;
3751 && (NEXTCHR_IS_EOS || !TRIE_BITMAP_TEST(trie, nextchr)))
3753 if (trie->states[ state ].wordnum) {
3755 PerlIO_printf(Perl_debug_log,
3756 "%*s %smatched empty string...%s\n",
3757 REPORT_CODE_OFF+depth*2, "", PL_colors[4], PL_colors[5])
3763 PerlIO_printf(Perl_debug_log,
3764 "%*s %sfailed to match trie start class...%s\n",
3765 REPORT_CODE_OFF+depth*2, "", PL_colors[4], PL_colors[5])
3772 U8 *uc = ( U8* )locinput;
3776 U8 *uscan = (U8*)NULL;
3777 U8 foldbuf[ UTF8_MAXBYTES_CASE + 1 ];
3778 U32 charcount = 0; /* how many input chars we have matched */
3779 U32 accepted = 0; /* have we seen any accepting states? */
3781 ST.jump = trie->jump;
3784 ST.longfold = FALSE; /* char longer if folded => it's harder */
3787 /* fully traverse the TRIE; note the position of the
3788 shortest accept state and the wordnum of the longest
3791 while ( state && uc <= (U8*)(reginfo->strend) ) {
3792 U32 base = trie->states[ state ].trans.base;
3796 wordnum = trie->states[ state ].wordnum;
3798 if (wordnum) { /* it's an accept state */
3801 /* record first match position */
3803 ST.firstpos = (U8*)locinput;
3808 ST.firstchars = charcount;
3811 if (!ST.nextword || wordnum < ST.nextword)
3812 ST.nextword = wordnum;
3813 ST.topword = wordnum;
3816 DEBUG_TRIE_EXECUTE_r({
3817 DUMP_EXEC_POS( (char *)uc, scan, utf8_target );
3818 PerlIO_printf( Perl_debug_log,
3819 "%*s %sState: %4"UVxf" Accepted: %c ",
3820 2+depth * 2, "", PL_colors[4],
3821 (UV)state, (accepted ? 'Y' : 'N'));
3824 /* read a char and goto next state */
3825 if ( base && (foldlen || uc < (U8*)(reginfo->strend))) {
3827 REXEC_TRIE_READ_CHAR(trie_type, trie, widecharmap, uc,
3828 uscan, len, uvc, charid, foldlen,
3835 base + charid - 1 - trie->uniquecharcount)) >= 0)
3837 && ((U32)offset < trie->lasttrans)
3838 && trie->trans[offset].check == state)
3840 state = trie->trans[offset].next;
3851 DEBUG_TRIE_EXECUTE_r(
3852 PerlIO_printf( Perl_debug_log,
3853 "Charid:%3x CP:%4"UVxf" After State: %4"UVxf"%s\n",
3854 charid, uvc, (UV)state, PL_colors[5] );
3860 /* calculate total number of accept states */
3865 w = trie->wordinfo[w].prev;
3868 ST.accepted = accepted;
3872 PerlIO_printf( Perl_debug_log,
3873 "%*s %sgot %"IVdf" possible matches%s\n",
3874 REPORT_CODE_OFF + depth * 2, "",
3875 PL_colors[4], (IV)ST.accepted, PL_colors[5] );
3877 goto trie_first_try; /* jump into the fail handler */
3879 assert(0); /* NOTREACHED */
3881 case TRIE_next_fail: /* we failed - try next alternative */
3885 REGCP_UNWIND(ST.cp);
3886 UNWIND_PAREN(ST.lastparen, ST.lastcloseparen);
3888 if (!--ST.accepted) {
3890 PerlIO_printf( Perl_debug_log,
3891 "%*s %sTRIE failed...%s\n",
3892 REPORT_CODE_OFF+depth*2, "",
3899 /* Find next-highest word to process. Note that this code
3900 * is O(N^2) per trie run (O(N) per branch), so keep tight */
3903 U16 const nextword = ST.nextword;
3904 reg_trie_wordinfo * const wordinfo
3905 = ((reg_trie_data*)rexi->data->data[ARG(ST.me)])->wordinfo;
3906 for (word=ST.topword; word; word=wordinfo[word].prev) {
3907 if (word > nextword && (!min || word < min))
3920 ST.lastparen = rex->lastparen;
3921 ST.lastcloseparen = rex->lastcloseparen;
3925 /* find start char of end of current word */
3927 U32 chars; /* how many chars to skip */
3928 reg_trie_data * const trie
3929 = (reg_trie_data*)rexi->data->data[ARG(ST.me)];
3931 assert((trie->wordinfo[ST.nextword].len - trie->prefixlen)
3933 chars = (trie->wordinfo[ST.nextword].len - trie->prefixlen)
3938 /* the hard option - fold each char in turn and find
3939 * its folded length (which may be different */
3940 U8 foldbuf[UTF8_MAXBYTES_CASE + 1];
3948 uvc = utf8n_to_uvuni((U8*)uc, UTF8_MAXLEN, &len,
3956 uvc = to_uni_fold(uvc, foldbuf, &foldlen);
3961 uvc = utf8n_to_uvuni(uscan, UTF8_MAXLEN, &len,
3977 scan = ST.me + ((ST.jump && ST.jump[ST.nextword])
3978 ? ST.jump[ST.nextword]
3982 PerlIO_printf( Perl_debug_log,
3983 "%*s %sTRIE matched word #%d, continuing%s\n",
3984 REPORT_CODE_OFF+depth*2, "",
3991 if (ST.accepted > 1 || has_cutgroup) {
3992 PUSH_STATE_GOTO(TRIE_next, scan, (char*)uc);
3993 assert(0); /* NOTREACHED */
3995 /* only one choice left - just continue */
3997 AV *const trie_words
3998 = MUTABLE_AV(rexi->data->data[ARG(ST.me)+TRIE_WORDS_OFFSET]);
3999 SV ** const tmp = av_fetch( trie_words,
4001 SV *sv= tmp ? sv_newmortal() : NULL;
4003 PerlIO_printf( Perl_debug_log,
4004 "%*s %sonly one match left, short-circuiting: #%d <%s>%s\n",
4005 REPORT_CODE_OFF+depth*2, "", PL_colors[4],
4007 tmp ? pv_pretty(sv, SvPV_nolen_const(*tmp), SvCUR(*tmp), 0,
4008 PL_colors[0], PL_colors[1],
4009 (SvUTF8(*tmp) ? PERL_PV_ESCAPE_UNI : 0)|PERL_PV_ESCAPE_NONASCII
4011 : "not compiled under -Dr",
4015 locinput = (char*)uc;
4016 continue; /* execute rest of RE */
4017 assert(0); /* NOTREACHED */
4021 case EXACT: { /* /abc/ */
4022 char *s = STRING(scan);
4024 if (utf8_target != is_utf8_pat) {
4025 /* The target and the pattern have differing utf8ness. */
4027 const char * const e = s + ln;
4030 /* The target is utf8, the pattern is not utf8.
4031 * Above-Latin1 code points can't match the pattern;
4032 * invariants match exactly, and the other Latin1 ones need
4033 * to be downgraded to a single byte in order to do the
4034 * comparison. (If we could be confident that the target
4035 * is not malformed, this could be refactored to have fewer
4036 * tests by just assuming that if the first bytes match, it
4037 * is an invariant, but there are tests in the test suite
4038 * dealing with (??{...}) which violate this) */
4040 if (l >= reginfo->strend
4041 || UTF8_IS_ABOVE_LATIN1(* (U8*) l))
4045 if (UTF8_IS_INVARIANT(*(U8*)l)) {
4052 if (TWO_BYTE_UTF8_TO_UNI(*l, *(l+1)) != * (U8*) s) {
4061 /* The target is not utf8, the pattern is utf8. */
4063 if (l >= reginfo->strend
4064 || UTF8_IS_ABOVE_LATIN1(* (U8*) s))
4068 if (UTF8_IS_INVARIANT(*(U8*)s)) {
4075 if (TWO_BYTE_UTF8_TO_UNI(*s, *(s+1)) != * (U8*) l) {
4086 /* The target and the pattern have the same utf8ness. */
4087 /* Inline the first character, for speed. */
4088 if (reginfo->strend - locinput < ln
4089 || UCHARAT(s) != nextchr
4090 || (ln > 1 && memNE(s, locinput, ln)))
4099 case EXACTFL: { /* /abc/il */
4101 const U8 * fold_array;
4103 U32 fold_utf8_flags;
4105 RX_MATCH_TAINTED_on(reginfo->prog);
4106 folder = foldEQ_locale;
4107 fold_array = PL_fold_locale;
4108 fold_utf8_flags = FOLDEQ_UTF8_LOCALE;
4111 case EXACTFU_SS: /* /\x{df}/iu */
4112 case EXACTFU_TRICKYFOLD: /* /\x{390}/iu */
4113 case EXACTFU: /* /abc/iu */
4114 folder = foldEQ_latin1;
4115 fold_array = PL_fold_latin1;
4116 fold_utf8_flags = is_utf8_pat ? FOLDEQ_S1_ALREADY_FOLDED : 0;
4119 case EXACTFA: /* /abc/iaa */
4120 folder = foldEQ_latin1;
4121 fold_array = PL_fold_latin1;
4122 fold_utf8_flags = FOLDEQ_UTF8_NOMIX_ASCII;
4125 case EXACTF: /* /abc/i */
4127 fold_array = PL_fold;
4128 fold_utf8_flags = 0;
4134 if (utf8_target || is_utf8_pat || state_num == EXACTFU_SS) {
4135 /* Either target or the pattern are utf8, or has the issue where
4136 * the fold lengths may differ. */
4137 const char * const l = locinput;
4138 char *e = reginfo->strend;
4140 if (! foldEQ_utf8_flags(s, 0, ln, is_utf8_pat,
4141 l, &e, 0, utf8_target, fold_utf8_flags))
4149 /* Neither the target nor the pattern are utf8 */
4150 if (UCHARAT(s) != nextchr
4152 && UCHARAT(s) != fold_array[nextchr])
4156 if (reginfo->strend - locinput < ln)
4158 if (ln > 1 && ! folder(s, locinput, ln))
4164 /* XXX Could improve efficiency by separating these all out using a
4165 * macro or in-line function. At that point regcomp.c would no longer
4166 * have to set the FLAGS fields of these */
4167 case BOUNDL: /* /\b/l */
4168 case NBOUNDL: /* /\B/l */
4169 RX_MATCH_TAINTED_on(reginfo->prog);
4171 case BOUND: /* /\b/ */
4172 case BOUNDU: /* /\b/u */
4173 case BOUNDA: /* /\b/a */
4174 case NBOUND: /* /\B/ */
4175 case NBOUNDU: /* /\B/u */
4176 case NBOUNDA: /* /\B/a */
4177 /* was last char in word? */
4179 && FLAGS(scan) != REGEX_ASCII_RESTRICTED_CHARSET
4180 && FLAGS(scan) != REGEX_ASCII_MORE_RESTRICTED_CHARSET)
4182 if (locinput == reginfo->strbeg)
4185 const U8 * const r =
4186 reghop3((U8*)locinput, -1, (U8*)(reginfo->strbeg));
4188 ln = utf8n_to_uvchr(r, UTF8SKIP(r), 0, uniflags);
4190 if (FLAGS(scan) != REGEX_LOCALE_CHARSET) {
4191 ln = isWORDCHAR_uni(ln);
4195 LOAD_UTF8_CHARCLASS_ALNUM();
4196 n = swash_fetch(PL_utf8_swash_ptrs[_CC_WORDCHAR], (U8*)locinput,
4201 ln = isWORDCHAR_LC_uvchr(UNI_TO_NATIVE(ln));
4202 n = NEXTCHR_IS_EOS ? 0 : isWORDCHAR_LC_utf8((U8*)locinput);
4207 /* Here the string isn't utf8, or is utf8 and only ascii
4208 * characters are to match \w. In the latter case looking at
4209 * the byte just prior to the current one may be just the final
4210 * byte of a multi-byte character. This is ok. There are two
4212 * 1) it is a single byte character, and then the test is doing
4213 * just what it's supposed to.
4214 * 2) it is a multi-byte character, in which case the final
4215 * byte is never mistakable for ASCII, and so the test
4216 * will say it is not a word character, which is the
4217 * correct answer. */
4218 ln = (locinput != reginfo->strbeg) ?
4219 UCHARAT(locinput - 1) : '\n';
4220 switch (FLAGS(scan)) {
4221 case REGEX_UNICODE_CHARSET:
4222 ln = isWORDCHAR_L1(ln);
4223 n = NEXTCHR_IS_EOS ? 0 : isWORDCHAR_L1(nextchr);
4225 case REGEX_LOCALE_CHARSET:
4226 ln = isWORDCHAR_LC(ln);
4227 n = NEXTCHR_IS_EOS ? 0 : isWORDCHAR_LC(nextchr);
4229 case REGEX_DEPENDS_CHARSET:
4230 ln = isWORDCHAR(ln);
4231 n = NEXTCHR_IS_EOS ? 0 : isWORDCHAR(nextchr);
4233 case REGEX_ASCII_RESTRICTED_CHARSET:
4234 case REGEX_ASCII_MORE_RESTRICTED_CHARSET:
4235 ln = isWORDCHAR_A(ln);
4236 n = NEXTCHR_IS_EOS ? 0 : isWORDCHAR_A(nextchr);
4239 Perl_croak(aTHX_ "panic: Unexpected FLAGS %u in op %u", FLAGS(scan), OP(scan));
4243 /* Note requires that all BOUNDs be lower than all NBOUNDs in
4245 if (((!ln) == (!n)) == (OP(scan) < NBOUND))
4249 case ANYOF: /* /[abc]/ */
4250 case ANYOF_WARN_SUPER:
4254 if (!reginclass(rex, scan, (U8*)locinput, utf8_target))
4256 locinput += UTF8SKIP(locinput);
4259 if (!REGINCLASS(rex, scan, (U8*)locinput))
4265 /* The argument (FLAGS) to all the POSIX node types is the class number
4268 case NPOSIXL: /* \W or [:^punct:] etc. under /l */
4272 case POSIXL: /* \w or [:punct:] etc. under /l */
4276 /* The locale hasn't influenced the outcome before this, so defer
4277 * tainting until now */
4278 RX_MATCH_TAINTED_on(reginfo->prog);
4280 /* Use isFOO_lc() for characters within Latin1. (Note that
4281 * UTF8_IS_INVARIANT works even on non-UTF-8 strings, or else
4282 * wouldn't be invariant) */
4283 if (UTF8_IS_INVARIANT(nextchr) || ! utf8_target) {
4284 if (! (to_complement ^ cBOOL(isFOO_lc(FLAGS(scan), (U8) nextchr)))) {
4288 else if (UTF8_IS_DOWNGRADEABLE_START(nextchr)) {
4289 if (! (to_complement ^ cBOOL(isFOO_lc(FLAGS(scan),
4290 (U8) TWO_BYTE_UTF8_TO_UNI(nextchr,
4291 *(locinput + 1))))))
4296 else { /* Here, must be an above Latin-1 code point */
4297 goto utf8_posix_not_eos;
4300 /* Here, must be utf8 */
4301 locinput += UTF8SKIP(locinput);
4304 case NPOSIXD: /* \W or [:^punct:] etc. under /d */
4308 case POSIXD: /* \w or [:punct:] etc. under /d */
4314 case NPOSIXA: /* \W or [:^punct:] etc. under /a */
4316 if (NEXTCHR_IS_EOS) {
4320 /* All UTF-8 variants match */
4321 if (! UTF8_IS_INVARIANT(nextchr)) {
4322 goto increment_locinput;
4328 case POSIXA: /* \w or [:punct:] etc. under /a */
4331 /* We get here through POSIXD, NPOSIXD, and NPOSIXA when not in
4332 * UTF-8, and also from NPOSIXA even in UTF-8 when the current
4333 * character is a single byte */
4336 || ! (to_complement ^ cBOOL(_generic_isCC_A(nextchr,
4342 /* Here we are either not in utf8, or we matched a utf8-invariant,
4343 * so the next char is the next byte */
4347 case NPOSIXU: /* \W or [:^punct:] etc. under /u */
4351 case POSIXU: /* \w or [:punct:] etc. under /u */
4353 if (NEXTCHR_IS_EOS) {
4358 /* Use _generic_isCC() for characters within Latin1. (Note that
4359 * UTF8_IS_INVARIANT works even on non-UTF-8 strings, or else
4360 * wouldn't be invariant) */
4361 if (UTF8_IS_INVARIANT(nextchr) || ! utf8_target) {
4362 if (! (to_complement ^ cBOOL(_generic_isCC(nextchr,
4369 else if (UTF8_IS_DOWNGRADEABLE_START(nextchr)) {
4370 if (! (to_complement
4371 ^ cBOOL(_generic_isCC(TWO_BYTE_UTF8_TO_UNI(nextchr,
4379 else { /* Handle above Latin-1 code points */
4380 classnum = (_char_class_number) FLAGS(scan);
4381 if (classnum < _FIRST_NON_SWASH_CC) {
4383 /* Here, uses a swash to find such code points. Load if if
4384 * not done already */
4385 if (! PL_utf8_swash_ptrs[classnum]) {
4386 U8 flags = _CORE_SWASH_INIT_ACCEPT_INVLIST;
4387 PL_utf8_swash_ptrs[classnum]
4388 = _core_swash_init("utf8",
4389 swash_property_names[classnum],
4390 &PL_sv_undef, 1, 0, NULL, &flags);
4392 if (! (to_complement
4393 ^ cBOOL(swash_fetch(PL_utf8_swash_ptrs[classnum],
4394 (U8 *) locinput, TRUE))))
4399 else { /* Here, uses macros to find above Latin-1 code points */
4401 case _CC_ENUM_SPACE: /* XXX would require separate
4402 code if we revert the change
4403 of \v matching this */
4404 case _CC_ENUM_PSXSPC:
4405 if (! (to_complement
4406 ^ cBOOL(is_XPERLSPACE_high(locinput))))
4411 case _CC_ENUM_BLANK:
4412 if (! (to_complement
4413 ^ cBOOL(is_HORIZWS_high(locinput))))
4418 case _CC_ENUM_XDIGIT:
4419 if (! (to_complement
4420 ^ cBOOL(is_XDIGIT_high(locinput))))
4425 case _CC_ENUM_VERTSPACE:
4426 if (! (to_complement
4427 ^ cBOOL(is_VERTWS_high(locinput))))
4432 default: /* The rest, e.g. [:cntrl:], can't match
4434 if (! to_complement) {
4440 locinput += UTF8SKIP(locinput);
4444 case CLUMP: /* Match \X: logical Unicode character. This is defined as
4445 a Unicode extended Grapheme Cluster */
4446 /* From http://www.unicode.org/reports/tr29 (5.2 version). An
4447 extended Grapheme Cluster is:
4450 | Prepend* Begin Extend*
4453 Begin is: ( Special_Begin | ! Control )
4454 Special_Begin is: ( Regional-Indicator+ | Hangul-syllable )
4455 Extend is: ( Grapheme_Extend | Spacing_Mark )
4456 Control is: [ GCB_Control | CR | LF ]
4457 Hangul-syllable is: ( T+ | ( L* ( L | ( LVT | ( V | LV ) V* ) T* ) ))
4459 If we create a 'Regular_Begin' = Begin - Special_Begin, then
4462 Begin is ( Regular_Begin + Special Begin )
4464 It turns out that 98.4% of all Unicode code points match
4465 Regular_Begin. Doing it this way eliminates a table match in
4466 the previous implementation for almost all Unicode code points.
4468 There is a subtlety with Prepend* which showed up in testing.
4469 Note that the Begin, and only the Begin is required in:
4470 | Prepend* Begin Extend*
4471 Also, Begin contains '! Control'. A Prepend must be a
4472 '! Control', which means it must also be a Begin. What it
4473 comes down to is that if we match Prepend* and then find no
4474 suitable Begin afterwards, that if we backtrack the last
4475 Prepend, that one will be a suitable Begin.
4480 if (! utf8_target) {
4482 /* Match either CR LF or '.', as all the other possibilities
4484 locinput++; /* Match the . or CR */
4485 if (nextchr == '\r' /* And if it was CR, and the next is LF,
4487 && locinput < reginfo->strend
4488 && UCHARAT(locinput) == '\n')
4495 /* Utf8: See if is ( CR LF ); already know that locinput <
4496 * reginfo->strend, so locinput+1 is in bounds */
4497 if ( nextchr == '\r' && locinput+1 < reginfo->strend
4498 && UCHARAT(locinput + 1) == '\n')
4505 /* In case have to backtrack to beginning, then match '.' */
4506 char *starting = locinput;
4508 /* In case have to backtrack the last prepend */
4509 char *previous_prepend = NULL;
4511 LOAD_UTF8_CHARCLASS_GCB();
4513 /* Match (prepend)* */
4514 while (locinput < reginfo->strend
4515 && (len = is_GCB_Prepend_utf8(locinput)))
4517 previous_prepend = locinput;
4521 /* As noted above, if we matched a prepend character, but
4522 * the next thing won't match, back off the last prepend we
4523 * matched, as it is guaranteed to match the begin */
4524 if (previous_prepend
4525 && (locinput >= reginfo->strend
4526 || (! swash_fetch(PL_utf8_X_regular_begin,
4527 (U8*)locinput, utf8_target)
4528 && ! is_GCB_SPECIAL_BEGIN_START_utf8(locinput)))
4531 locinput = previous_prepend;
4534 /* Note that here we know reginfo->strend > locinput, as we
4535 * tested that upon input to this switch case, and if we
4536 * moved locinput forward, we tested the result just above
4537 * and it either passed, or we backed off so that it will
4539 if (swash_fetch(PL_utf8_X_regular_begin,
4540 (U8*)locinput, utf8_target)) {
4541 locinput += UTF8SKIP(locinput);
4543 else if (! is_GCB_SPECIAL_BEGIN_START_utf8(locinput)) {
4545 /* Here did not match the required 'Begin' in the
4546 * second term. So just match the very first
4547 * character, the '.' of the final term of the regex */
4548 locinput = starting + UTF8SKIP(starting);
4552 /* Here is a special begin. It can be composed of
4553 * several individual characters. One possibility is
4555 if ((len = is_GCB_RI_utf8(locinput))) {
4557 while (locinput < reginfo->strend
4558 && (len = is_GCB_RI_utf8(locinput)))
4562 } else if ((len = is_GCB_T_utf8(locinput))) {
4563 /* Another possibility is T+ */
4565 while (locinput < reginfo->strend
4566 && (len = is_GCB_T_utf8(locinput)))
4572 /* Here, neither RI+ nor T+; must be some other
4573 * Hangul. That means it is one of the others: L,
4574 * LV, LVT or V, and matches:
4575 * L* (L | LVT T* | V * V* T* | LV V* T*) */
4578 while (locinput < reginfo->strend
4579 && (len = is_GCB_L_utf8(locinput)))
4584 /* Here, have exhausted L*. If the next character
4585 * is not an LV, LVT nor V, it means we had to have
4586 * at least one L, so matches L+ in the original
4587 * equation, we have a complete hangul syllable.
4590 if (locinput < reginfo->strend
4591 && is_GCB_LV_LVT_V_utf8(locinput))
4593 /* Otherwise keep going. Must be LV, LVT or V.
4594 * See if LVT, by first ruling out V, then LV */
4595 if (! is_GCB_V_utf8(locinput)
4596 /* All but every TCount one is LV */
4597 && (valid_utf8_to_uvchr((U8 *) locinput,
4602 locinput += UTF8SKIP(locinput);
4605 /* Must be V or LV. Take it, then match
4607 locinput += UTF8SKIP(locinput);
4608 while (locinput < reginfo->strend
4609 && (len = is_GCB_V_utf8(locinput)))
4615 /* And any of LV, LVT, or V can be followed
4617 while (locinput < reginfo->strend
4618 && (len = is_GCB_T_utf8(locinput)))
4626 /* Match any extender */
4627 while (locinput < reginfo->strend
4628 && swash_fetch(PL_utf8_X_extend,
4629 (U8*)locinput, utf8_target))
4631 locinput += UTF8SKIP(locinput);
4635 if (locinput > reginfo->strend) sayNO;
4639 case NREFFL: /* /\g{name}/il */
4640 { /* The capture buffer cases. The ones beginning with N for the
4641 named buffers just convert to the equivalent numbered and
4642 pretend they were called as the corresponding numbered buffer
4644 /* don't initialize these in the declaration, it makes C++
4649 const U8 *fold_array;
4652 RX_MATCH_TAINTED_on(reginfo->prog);
4653 folder = foldEQ_locale;
4654 fold_array = PL_fold_locale;
4656 utf8_fold_flags = FOLDEQ_UTF8_LOCALE;
4659 case NREFFA: /* /\g{name}/iaa */
4660 folder = foldEQ_latin1;
4661 fold_array = PL_fold_latin1;
4663 utf8_fold_flags = FOLDEQ_UTF8_NOMIX_ASCII;
4666 case NREFFU: /* /\g{name}/iu */
4667 folder = foldEQ_latin1;
4668 fold_array = PL_fold_latin1;
4670 utf8_fold_flags = 0;
4673 case NREFF: /* /\g{name}/i */
4675 fold_array = PL_fold;
4677 utf8_fold_flags = 0;
4680 case NREF: /* /\g{name}/ */
4684 utf8_fold_flags = 0;
4687 /* For the named back references, find the corresponding buffer
4689 n = reg_check_named_buff_matched(rex,scan);
4694 goto do_nref_ref_common;
4696 case REFFL: /* /\1/il */
4697 RX_MATCH_TAINTED_on(reginfo->prog);
4698 folder = foldEQ_locale;
4699 fold_array = PL_fold_locale;
4700 utf8_fold_flags = FOLDEQ_UTF8_LOCALE;
4703 case REFFA: /* /\1/iaa */
4704 folder = foldEQ_latin1;
4705 fold_array = PL_fold_latin1;
4706 utf8_fold_flags = FOLDEQ_UTF8_NOMIX_ASCII;
4709 case REFFU: /* /\1/iu */
4710 folder = foldEQ_latin1;
4711 fold_array = PL_fold_latin1;
4712 utf8_fold_flags = 0;
4715 case REFF: /* /\1/i */
4717 fold_array = PL_fold;
4718 utf8_fold_flags = 0;
4721 case REF: /* /\1/ */
4724 utf8_fold_flags = 0;
4728 n = ARG(scan); /* which paren pair */
4731 ln = rex->offs[n].start;
4732 reginfo->poscache_iter = reginfo->poscache_maxiter; /* Void cache */
4733 if (rex->lastparen < n || ln == -1)
4734 sayNO; /* Do not match unless seen CLOSEn. */
4735 if (ln == rex->offs[n].end)
4738 s = reginfo->strbeg + ln;
4739 if (type != REF /* REF can do byte comparison */
4740 && (utf8_target || type == REFFU))
4741 { /* XXX handle REFFL better */
4742 char * limit = reginfo->strend;
4744 /* This call case insensitively compares the entire buffer
4745 * at s, with the current input starting at locinput, but
4746 * not going off the end given by reginfo->strend, and
4747 * returns in <limit> upon success, how much of the
4748 * current input was matched */
4749 if (! foldEQ_utf8_flags(s, NULL, rex->offs[n].end - ln, utf8_target,
4750 locinput, &limit, 0, utf8_target, utf8_fold_flags))
4758 /* Not utf8: Inline the first character, for speed. */
4759 if (!NEXTCHR_IS_EOS &&
4760 UCHARAT(s) != nextchr &&
4762 UCHARAT(s) != fold_array[nextchr]))
4764 ln = rex->offs[n].end - ln;
4765 if (locinput + ln > reginfo->strend)
4767 if (ln > 1 && (type == REF
4768 ? memNE(s, locinput, ln)
4769 : ! folder(s, locinput, ln)))
4775 case NOTHING: /* null op; e.g. the 'nothing' following
4776 * the '*' in m{(a+|b)*}' */
4778 case TAIL: /* placeholder while compiling (A|B|C) */
4781 case BACK: /* ??? doesn't appear to be used ??? */
4785 #define ST st->u.eval
4790 regexp_internal *rei;
4791 regnode *startpoint;
4793 case GOSTART: /* (?R) */
4794 case GOSUB: /* /(...(?1))/ /(...(?&foo))/ */
4795 if (cur_eval && cur_eval->locinput==locinput) {
4796 if (cur_eval->u.eval.close_paren == (U32)ARG(scan))
4797 Perl_croak(aTHX_ "Infinite recursion in regex");
4798 if ( ++nochange_depth > max_nochange_depth )
4800 "Pattern subroutine nesting without pos change"
4801 " exceeded limit in regex");
4808 if (OP(scan)==GOSUB) {
4809 startpoint = scan + ARG2L(scan);
4810 ST.close_paren = ARG(scan);
4812 startpoint = rei->program+1;
4815 goto eval_recurse_doit;
4816 assert(0); /* NOTREACHED */
4818 case EVAL: /* /(?{A})B/ /(??{A})B/ and /(?(?{A})X|Y)B/ */
4819 if (cur_eval && cur_eval->locinput==locinput) {
4820 if ( ++nochange_depth > max_nochange_depth )
4821 Perl_croak(aTHX_ "EVAL without pos change exceeded limit in regex");
4826 /* execute the code in the {...} */
4830 OP * const oop = PL_op;
4831 COP * const ocurcop = PL_curcop;
4835 /* save *all* paren positions */
4836 regcppush(rex, 0, maxopenparen);
4837 REGCP_SET(runops_cp);
4840 caller_cv = find_runcv(NULL);
4844 if (rexi->data->what[n] == 'r') { /* code from an external qr */
4846 (REGEXP*)(rexi->data->data[n])
4849 nop = (OP*)rexi->data->data[n+1];
4851 else if (rexi->data->what[n] == 'l') { /* literal code */
4853 nop = (OP*)rexi->data->data[n];
4854 assert(CvDEPTH(newcv));
4857 /* literal with own CV */
4858 assert(rexi->data->what[n] == 'L');
4859 newcv = rex->qr_anoncv;
4860 nop = (OP*)rexi->data->data[n];
4863 /* normally if we're about to execute code from the same
4864 * CV that we used previously, we just use the existing
4865 * CX stack entry. However, its possible that in the
4866 * meantime we may have backtracked, popped from the save
4867 * stack, and undone the SAVECOMPPAD(s) associated with
4868 * PUSH_MULTICALL; in which case PL_comppad no longer
4869 * points to newcv's pad. */
4870 if (newcv != last_pushed_cv || PL_comppad != last_pad)
4872 U8 flags = (CXp_SUB_RE |
4873 ((newcv == caller_cv) ? CXp_SUB_RE_FAKE : 0));
4874 if (last_pushed_cv) {
4875 CHANGE_MULTICALL_FLAGS(newcv, flags);
4878 PUSH_MULTICALL_FLAGS(newcv, flags);
4880 last_pushed_cv = newcv;
4883 /* these assignments are just to silence compiler
4885 multicall_cop = NULL;
4888 last_pad = PL_comppad;
4890 /* the initial nextstate you would normally execute
4891 * at the start of an eval (which would cause error
4892 * messages to come from the eval), may be optimised
4893 * away from the execution path in the regex code blocks;
4894 * so manually set PL_curcop to it initially */
4896 OP *o = cUNOPx(nop)->op_first;
4897 assert(o->op_type == OP_NULL);
4898 if (o->op_targ == OP_SCOPE) {
4899 o = cUNOPo->op_first;
4902 assert(o->op_targ == OP_LEAVE);
4903 o = cUNOPo->op_first;
4904 assert(o->op_type == OP_ENTER);
4908 if (o->op_type != OP_STUB) {
4909 assert( o->op_type == OP_NEXTSTATE
4910 || o->op_type == OP_DBSTATE
4911 || (o->op_type == OP_NULL
4912 && ( o->op_targ == OP_NEXTSTATE
4913 || o->op_targ == OP_DBSTATE
4917 PL_curcop = (COP*)o;
4922 DEBUG_STATE_r( PerlIO_printf(Perl_debug_log,
4923 " re EVAL PL_op=0x%"UVxf"\n", PTR2UV(nop)) );
4925 rex->offs[0].end = locinput - reginfo->strbeg;
4926 if (reginfo->info_aux_eval->pos_magic)
4927 reginfo->info_aux_eval->pos_magic->mg_len
4928 = locinput - reginfo->strbeg;
4931 SV *sv_mrk = get_sv("REGMARK", 1);
4932 sv_setsv(sv_mrk, sv_yes_mark);
4935 /* we don't use MULTICALL here as we want to call the
4936 * first op of the block of interest, rather than the
4937 * first op of the sub */
4938 before = (IV)(SP-PL_stack_base);
4940 CALLRUNOPS(aTHX); /* Scalar context. */
4942 if ((IV)(SP-PL_stack_base) == before)
4943 ret = &PL_sv_undef; /* protect against empty (?{}) blocks. */
4949 /* before restoring everything, evaluate the returned
4950 * value, so that 'uninit' warnings don't use the wrong
4951 * PL_op or pad. Also need to process any magic vars
4952 * (e.g. $1) *before* parentheses are restored */
4957 if (logical == 0) /* (?{})/ */
4958 sv_setsv(save_scalar(PL_replgv), ret); /* $^R */
4959 else if (logical == 1) { /* /(?(?{...})X|Y)/ */
4960 sw = cBOOL(SvTRUE(ret));
4963 else { /* /(??{}) */
4964 /* if its overloaded, let the regex compiler handle
4965 * it; otherwise extract regex, or stringify */
4966 if (!SvAMAGIC(ret)) {
4970 if (SvTYPE(sv) == SVt_REGEXP)
4971 re_sv = (REGEXP*) sv;
4972 else if (SvSMAGICAL(sv)) {
4973 MAGIC *mg = mg_find(sv, PERL_MAGIC_qr);
4975 re_sv = (REGEXP *) mg->mg_obj;
4978 /* force any magic, undef warnings here */
4980 ret = sv_mortalcopy(ret);
4981 (void) SvPV_force_nolen(ret);
4987 /* *** Note that at this point we don't restore
4988 * PL_comppad, (or pop the CxSUB) on the assumption it may
4989 * be used again soon. This is safe as long as nothing
4990 * in the regexp code uses the pad ! */
4992 PL_curcop = ocurcop;
4993 S_regcp_restore(aTHX_ rex, runops_cp, &maxopenparen);
4999 /* only /(??{})/ from now on */
5002 /* extract RE object from returned value; compiling if
5006 re_sv = reg_temp_copy(NULL, re_sv);
5011 if (SvUTF8(ret) && IN_BYTES) {
5012 /* In use 'bytes': make a copy of the octet
5013 * sequence, but without the flag on */
5015 const char *const p = SvPV(ret, len);
5016 ret = newSVpvn_flags(p, len, SVs_TEMP);
5018 if (rex->intflags & PREGf_USE_RE_EVAL)
5019 pm_flags |= PMf_USE_RE_EVAL;
5021 /* if we got here, it should be an engine which
5022 * supports compiling code blocks and stuff */
5023 assert(rex->engine && rex->engine->op_comp);
5024 assert(!(scan->flags & ~RXf_PMf_COMPILETIME));
5025 re_sv = rex->engine->op_comp(aTHX_ &ret, 1, NULL,
5026 rex->engine, NULL, NULL,
5027 /* copy /msix etc to inner pattern */
5032 & (SVs_TEMP | SVs_PADTMP | SVf_READONLY
5034 /* This isn't a first class regexp. Instead, it's
5035 caching a regexp onto an existing, Perl visible
5037 sv_magic(ret, MUTABLE_SV(re_sv), PERL_MAGIC_qr, 0, 0);
5039 /* safe to do now that any $1 etc has been
5040 * interpolated into the new pattern string and
5042 S_regcp_restore(aTHX_ rex, runops_cp, &maxopenparen);
5047 RXp_MATCH_COPIED_off(re);
5048 re->subbeg = rex->subbeg;
5049 re->sublen = rex->sublen;
5050 re->suboffset = rex->suboffset;
5051 re->subcoffset = rex->subcoffset;
5054 debug_start_match(re_sv, utf8_target, locinput,
5055 reginfo->strend, "Matching embedded");
5057 startpoint = rei->program + 1;
5058 ST.close_paren = 0; /* only used for GOSUB */
5060 eval_recurse_doit: /* Share code with GOSUB below this line */
5061 /* run the pattern returned from (??{...}) */
5063 /* Save *all* the positions. */
5064 ST.cp = regcppush(rex, 0, maxopenparen);
5065 REGCP_SET(ST.lastcp);
5068 re->lastcloseparen = 0;
5072 /* invalidate the S-L poscache. We're now executing a
5073 * different set of WHILEM ops (and their associated
5074 * indexes) against the same string, so the bits in the
5075 * cache are meaningless. Setting maxiter to zero forces
5076 * the cache to be invalidated and zeroed before reuse.
5077 * XXX This is too dramatic a measure. Ideally we should
5078 * save the old cache and restore when running the outer
5080 reginfo->poscache_maxiter = 0;
5082 is_utf8_pat = reginfo->is_utf8_pat = cBOOL(RX_UTF8(re_sv));
5084 ST.prev_rex = rex_sv;
5085 ST.prev_curlyx = cur_curlyx;
5087 SET_reg_curpm(rex_sv);
5092 ST.prev_eval = cur_eval;
5094 /* now continue from first node in postoned RE */
5095 PUSH_YES_STATE_GOTO(EVAL_AB, startpoint, locinput);
5096 assert(0); /* NOTREACHED */
5099 case EVAL_AB: /* cleanup after a successful (??{A})B */
5100 /* note: this is called twice; first after popping B, then A */
5101 rex_sv = ST.prev_rex;
5102 is_utf8_pat = reginfo->is_utf8_pat = cBOOL(RX_UTF8(rex_sv));
5103 SET_reg_curpm(rex_sv);
5104 rex = ReANY(rex_sv);
5105 rexi = RXi_GET(rex);
5107 cur_eval = ST.prev_eval;
5108 cur_curlyx = ST.prev_curlyx;
5110 /* Invalidate cache. See "invalidate" comment above. */
5111 reginfo->poscache_maxiter = 0;
5112 if ( nochange_depth )
5117 case EVAL_AB_fail: /* unsuccessfully ran A or B in (??{A})B */
5118 /* note: this is called twice; first after popping B, then A */
5119 rex_sv = ST.prev_rex;
5120 is_utf8_pat = reginfo->is_utf8_pat = cBOOL(RX_UTF8(rex_sv));
5121 SET_reg_curpm(rex_sv);
5122 rex = ReANY(rex_sv);
5123 rexi = RXi_GET(rex);
5125 REGCP_UNWIND(ST.lastcp);
5126 regcppop(rex, &maxopenparen);
5127 cur_eval = ST.prev_eval;
5128 cur_curlyx = ST.prev_curlyx;
5129 /* Invalidate cache. See "invalidate" comment above. */
5130 reginfo->poscache_maxiter = 0;
5131 if ( nochange_depth )
5137 n = ARG(scan); /* which paren pair */
5138 rex->offs[n].start_tmp = locinput - reginfo->strbeg;
5139 if (n > maxopenparen)
5141 DEBUG_BUFFERS_r(PerlIO_printf(Perl_debug_log,
5142 "rex=0x%"UVxf" offs=0x%"UVxf": \\%"UVuf": set %"IVdf" tmp; maxopenparen=%"UVuf"\n",
5146 (IV)rex->offs[n].start_tmp,
5152 /* XXX really need to log other places start/end are set too */
5153 #define CLOSE_CAPTURE \
5154 rex->offs[n].start = rex->offs[n].start_tmp; \
5155 rex->offs[n].end = locinput - reginfo->strbeg; \
5156 DEBUG_BUFFERS_r(PerlIO_printf(Perl_debug_log, \
5157 "rex=0x%"UVxf" offs=0x%"UVxf": \\%"UVuf": set %"IVdf"..%"IVdf"\n", \
5159 PTR2UV(rex->offs), \
5161 (IV)rex->offs[n].start, \
5162 (IV)rex->offs[n].end \
5166 n = ARG(scan); /* which paren pair */
5168 if (n > rex->lastparen)
5170 rex->lastcloseparen = n;
5171 if (cur_eval && cur_eval->u.eval.close_paren == n) {
5176 case ACCEPT: /* (*ACCEPT) */
5180 cursor && OP(cursor)!=END;
5181 cursor=regnext(cursor))
5183 if ( OP(cursor)==CLOSE ){
5185 if ( n <= lastopen ) {
5187 if (n > rex->lastparen)
5189 rex->lastcloseparen = n;
5190 if ( n == ARG(scan) || (cur_eval &&
5191 cur_eval->u.eval.close_paren == n))
5200 case GROUPP: /* (?(1)) */
5201 n = ARG(scan); /* which paren pair */
5202 sw = cBOOL(rex->lastparen >= n && rex->offs[n].end != -1);
5205 case NGROUPP: /* (?(<name>)) */
5206 /* reg_check_named_buff_matched returns 0 for no match */
5207 sw = cBOOL(0 < reg_check_named_buff_matched(rex,scan));
5210 case INSUBP: /* (?(R)) */
5212 sw = (cur_eval && (!n || cur_eval->u.eval.close_paren == n));
5215 case DEFINEP: /* (?(DEFINE)) */
5219 case IFTHEN: /* (?(cond)A|B) */
5220 reginfo->poscache_iter = reginfo->poscache_maxiter; /* Void cache */
5222 next = NEXTOPER(NEXTOPER(scan));
5224 next = scan + ARG(scan);
5225 if (OP(next) == IFTHEN) /* Fake one. */
5226 next = NEXTOPER(NEXTOPER(next));
5230 case LOGICAL: /* modifier for EVAL and IFMATCH */
5231 logical = scan->flags;
5234 /*******************************************************************
5236 The CURLYX/WHILEM pair of ops handle the most generic case of the /A*B/
5237 pattern, where A and B are subpatterns. (For simple A, CURLYM or
5238 STAR/PLUS/CURLY/CURLYN are used instead.)
5240 A*B is compiled as <CURLYX><A><WHILEM><B>
5242 On entry to the subpattern, CURLYX is called. This pushes a CURLYX
5243 state, which contains the current count, initialised to -1. It also sets
5244 cur_curlyx to point to this state, with any previous value saved in the
5247 CURLYX then jumps straight to the WHILEM op, rather than executing A,
5248 since the pattern may possibly match zero times (i.e. it's a while {} loop
5249 rather than a do {} while loop).
5251 Each entry to WHILEM represents a successful match of A. The count in the
5252 CURLYX block is incremented, another WHILEM state is pushed, and execution
5253 passes to A or B depending on greediness and the current count.
5255 For example, if matching against the string a1a2a3b (where the aN are
5256 substrings that match /A/), then the match progresses as follows: (the
5257 pushed states are interspersed with the bits of strings matched so far):
5260 <CURLYX cnt=0><WHILEM>
5261 <CURLYX cnt=1><WHILEM> a1 <WHILEM>
5262 <CURLYX cnt=2><WHILEM> a1 <WHILEM> a2 <WHILEM>
5263 <CURLYX cnt=3><WHILEM> a1 <WHILEM> a2 <WHILEM> a3 <WHILEM>
5264 <CURLYX cnt=3><WHILEM> a1 <WHILEM> a2 <WHILEM> a3 <WHILEM> b
5266 (Contrast this with something like CURLYM, which maintains only a single
5270 a1 <CURLYM cnt=1> a2
5271 a1 a2 <CURLYM cnt=2> a3
5272 a1 a2 a3 <CURLYM cnt=3> b
5275 Each WHILEM state block marks a point to backtrack to upon partial failure
5276 of A or B, and also contains some minor state data related to that
5277 iteration. The CURLYX block, pointed to by cur_curlyx, contains the
5278 overall state, such as the count, and pointers to the A and B ops.
5280 This is complicated slightly by nested CURLYX/WHILEM's. Since cur_curlyx
5281 must always point to the *current* CURLYX block, the rules are:
5283 When executing CURLYX, save the old cur_curlyx in the CURLYX state block,
5284 and set cur_curlyx to point the new block.
5286 When popping the CURLYX block after a successful or unsuccessful match,
5287 restore the previous cur_curlyx.
5289 When WHILEM is about to execute B, save the current cur_curlyx, and set it
5290 to the outer one saved in the CURLYX block.
5292 When popping the WHILEM block after a successful or unsuccessful B match,
5293 restore the previous cur_curlyx.
5295 Here's an example for the pattern (AI* BI)*BO
5296 I and O refer to inner and outer, C and W refer to CURLYX and WHILEM:
5299 curlyx backtrack stack
5300 ------ ---------------
5302 CO <CO prev=NULL> <WO>
5303 CI <CO prev=NULL> <WO> <CI prev=CO> <WI> ai
5304 CO <CO prev=NULL> <WO> <CI prev=CO> <WI> ai <WI prev=CI> bi
5305 NULL <CO prev=NULL> <WO> <CI prev=CO> <WI> ai <WI prev=CI> bi <WO prev=CO> bo
5307 At this point the pattern succeeds, and we work back down the stack to
5308 clean up, restoring as we go:
5310 CO <CO prev=NULL> <WO> <CI prev=CO> <WI> ai <WI prev=CI> bi
5311 CI <CO prev=NULL> <WO> <CI prev=CO> <WI> ai
5312 CO <CO prev=NULL> <WO>
5315 *******************************************************************/
5317 #define ST st->u.curlyx
5319 case CURLYX: /* start of /A*B/ (for complex A) */
5321 /* No need to save/restore up to this paren */
5322 I32 parenfloor = scan->flags;
5324 assert(next); /* keep Coverity happy */
5325 if (OP(PREVOPER(next)) == NOTHING) /* LONGJMP */
5328 /* XXXX Probably it is better to teach regpush to support
5329 parenfloor > maxopenparen ... */
5330 if (parenfloor > (I32)rex->lastparen)
5331 parenfloor = rex->lastparen; /* Pessimization... */
5333 ST.prev_curlyx= cur_curlyx;
5335 ST.cp = PL_savestack_ix;
5337 /* these fields contain the state of the current curly.
5338 * they are accessed by subsequent WHILEMs */
5339 ST.parenfloor = parenfloor;
5344 ST.count = -1; /* this will be updated by WHILEM */
5345 ST.lastloc = NULL; /* this will be updated by WHILEM */
5347 PUSH_YES_STATE_GOTO(CURLYX_end, PREVOPER(next), locinput);
5348 assert(0); /* NOTREACHED */
5351 case CURLYX_end: /* just finished matching all of A*B */
5352 cur_curlyx = ST.prev_curlyx;
5354 assert(0); /* NOTREACHED */
5356 case CURLYX_end_fail: /* just failed to match all of A*B */
5358 cur_curlyx = ST.prev_curlyx;
5360 assert(0); /* NOTREACHED */
5364 #define ST st->u.whilem
5366 case WHILEM: /* just matched an A in /A*B/ (for complex A) */
5368 /* see the discussion above about CURLYX/WHILEM */
5370 int min = ARG1(cur_curlyx->u.curlyx.me);
5371 int max = ARG2(cur_curlyx->u.curlyx.me);
5372 regnode *A = NEXTOPER(cur_curlyx->u.curlyx.me) + EXTRA_STEP_2ARGS;
5374 assert(cur_curlyx); /* keep Coverity happy */
5375 n = ++cur_curlyx->u.curlyx.count; /* how many A's matched */
5376 ST.save_lastloc = cur_curlyx->u.curlyx.lastloc;
5377 ST.cache_offset = 0;
5381 DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log,
5382 "%*s whilem: matched %ld out of %d..%d\n",
5383 REPORT_CODE_OFF+depth*2, "", (long)n, min, max)
5386 /* First just match a string of min A's. */
5389 ST.cp = regcppush(rex, cur_curlyx->u.curlyx.parenfloor,
5391 cur_curlyx->u.curlyx.lastloc = locinput;
5392 REGCP_SET(ST.lastcp);
5394 PUSH_STATE_GOTO(WHILEM_A_pre, A, locinput);
5395 assert(0); /* NOTREACHED */
5398 /* If degenerate A matches "", assume A done. */
5400 if (locinput == cur_curlyx->u.curlyx.lastloc) {
5401 DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log,
5402 "%*s whilem: empty match detected, trying continuation...\n",
5403 REPORT_CODE_OFF+depth*2, "")
5405 goto do_whilem_B_max;
5408 /* super-linear cache processing.
5410 * The idea here is that for certain types of CURLYX/WHILEM -
5411 * principally those whose upper bound is infinity (and
5412 * excluding regexes that have things like \1 and other very
5413 * non-regular expresssiony things), then if a pattern like
5414 * /....A*.../ fails and we backtrack to the WHILEM, then we
5415 * make a note that this particular WHILEM op was at string
5416 * position 47 (say) when the rest of pattern failed. Then, if
5417 * we ever find ourselves back at that WHILEM, and at string
5418 * position 47 again, we can just fail immediately rather than
5419 * running the rest of the pattern again.
5421 * This is very handy when patterns start to go
5422 * 'super-linear', like in (a+)*(a+)*(a+)*, where you end up
5423 * with a combinatorial explosion of backtracking.
5425 * The cache is implemented as a bit array, with one bit per
5426 * string byte position per WHILEM op (up to 16) - so its
5427 * between 0.25 and 2x the string size.
5429 * To avoid allocating a poscache buffer every time, we do an
5430 * initially countdown; only after we have executed a WHILEM
5431 * op (string-length x #WHILEMs) times do we allocate the
5434 * The top 4 bits of scan->flags byte say how many different
5435 * relevant CURLLYX/WHILEM op pairs there are, while the
5436 * bottom 4-bits is the identifying index number of this
5442 if (!reginfo->poscache_maxiter) {
5443 /* start the countdown: Postpone detection until we
5444 * know the match is not *that* much linear. */
5445 reginfo->poscache_maxiter
5446 = (reginfo->strend - reginfo->strbeg + 1)
5448 /* possible overflow for long strings and many CURLYX's */
5449 if (reginfo->poscache_maxiter < 0)
5450 reginfo->poscache_maxiter = I32_MAX;
5451 reginfo->poscache_iter = reginfo->poscache_maxiter;
5454 if (reginfo->poscache_iter-- == 0) {
5455 /* initialise cache */
5456 const I32 size = (reginfo->poscache_maxiter + 7)/8;
5457 regmatch_info_aux *const aux = reginfo->info_aux;
5458 if (aux->poscache) {
5459 if ((I32)reginfo->poscache_size < size) {
5460 Renew(aux->poscache, size, char);
5461 reginfo->poscache_size = size;
5463 Zero(aux->poscache, size, char);
5466 reginfo->poscache_size = size;
5467 Newxz(aux->poscache, size, char);
5469 DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log,
5470 "%swhilem: Detected a super-linear match, switching on caching%s...\n",
5471 PL_colors[4], PL_colors[5])
5475 if (reginfo->poscache_iter < 0) {
5476 /* have we already failed at this position? */
5479 reginfo->poscache_iter = -1; /* stop eventual underflow */
5480 offset = (scan->flags & 0xf) - 1
5481 + (locinput - reginfo->strbeg)
5483 mask = 1 << (offset % 8);
5485 if (reginfo->info_aux->poscache[offset] & mask) {
5486 DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log,
5487 "%*s whilem: (cache) already tried at this position...\n",
5488 REPORT_CODE_OFF+depth*2, "")
5490 sayNO; /* cache records failure */
5492 ST.cache_offset = offset;
5493 ST.cache_mask = mask;
5497 /* Prefer B over A for minimal matching. */
5499 if (cur_curlyx->u.curlyx.minmod) {
5500 ST.save_curlyx = cur_curlyx;
5501 cur_curlyx = cur_curlyx->u.curlyx.prev_curlyx;
5502 ST.cp = regcppush(rex, ST.save_curlyx->u.curlyx.parenfloor,
5504 REGCP_SET(ST.lastcp);
5505 PUSH_YES_STATE_GOTO(WHILEM_B_min, ST.save_curlyx->u.curlyx.B,
5507 assert(0); /* NOTREACHED */
5510 /* Prefer A over B for maximal matching. */
5512 if (n < max) { /* More greed allowed? */
5513 ST.cp = regcppush(rex, cur_curlyx->u.curlyx.parenfloor,
5515 cur_curlyx->u.curlyx.lastloc = locinput;
5516 REGCP_SET(ST.lastcp);
5517 PUSH_STATE_GOTO(WHILEM_A_max, A, locinput);
5518 assert(0); /* NOTREACHED */
5520 goto do_whilem_B_max;
5522 assert(0); /* NOTREACHED */
5524 case WHILEM_B_min: /* just matched B in a minimal match */
5525 case WHILEM_B_max: /* just matched B in a maximal match */
5526 cur_curlyx = ST.save_curlyx;
5528 assert(0); /* NOTREACHED */
5530 case WHILEM_B_max_fail: /* just failed to match B in a maximal match */
5531 cur_curlyx = ST.save_curlyx;
5532 cur_curlyx->u.curlyx.lastloc = ST.save_lastloc;
5533 cur_curlyx->u.curlyx.count--;
5535 assert(0); /* NOTREACHED */
5537 case WHILEM_A_min_fail: /* just failed to match A in a minimal match */
5539 case WHILEM_A_pre_fail: /* just failed to match even minimal A */
5540 REGCP_UNWIND(ST.lastcp);
5541 regcppop(rex, &maxopenparen);
5542 cur_curlyx->u.curlyx.lastloc = ST.save_lastloc;
5543 cur_curlyx->u.curlyx.count--;
5545 assert(0); /* NOTREACHED */
5547 case WHILEM_A_max_fail: /* just failed to match A in a maximal match */
5548 REGCP_UNWIND(ST.lastcp);
5549 regcppop(rex, &maxopenparen); /* Restore some previous $<digit>s? */
5550 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
5551 "%*s whilem: failed, trying continuation...\n",
5552 REPORT_CODE_OFF+depth*2, "")
5555 if (cur_curlyx->u.curlyx.count >= REG_INFTY
5556 && ckWARN(WARN_REGEXP)
5557 && !reginfo->warned)
5559 reginfo->warned = TRUE;
5560 Perl_warner(aTHX_ packWARN(WARN_REGEXP),
5561 "Complex regular subexpression recursion limit (%d) "
5567 ST.save_curlyx = cur_curlyx;
5568 cur_curlyx = cur_curlyx->u.curlyx.prev_curlyx;
5569 PUSH_YES_STATE_GOTO(WHILEM_B_max, ST.save_curlyx->u.curlyx.B,
5571 assert(0); /* NOTREACHED */
5573 case WHILEM_B_min_fail: /* just failed to match B in a minimal match */
5574 cur_curlyx = ST.save_curlyx;
5575 REGCP_UNWIND(ST.lastcp);
5576 regcppop(rex, &maxopenparen);
5578 if (cur_curlyx->u.curlyx.count >= /*max*/ARG2(cur_curlyx->u.curlyx.me)) {
5579 /* Maximum greed exceeded */
5580 if (cur_curlyx->u.curlyx.count >= REG_INFTY
5581 && ckWARN(WARN_REGEXP)
5582 && !reginfo->warned)
5584 reginfo->warned = TRUE;
5585 Perl_warner(aTHX_ packWARN(WARN_REGEXP),
5586 "Complex regular subexpression recursion "
5587 "limit (%d) exceeded",
5590 cur_curlyx->u.curlyx.count--;
5594 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
5595 "%*s trying longer...\n", REPORT_CODE_OFF+depth*2, "")
5597 /* Try grabbing another A and see if it helps. */
5598 cur_curlyx->u.curlyx.lastloc = locinput;
5599 ST.cp = regcppush(rex, cur_curlyx->u.curlyx.parenfloor,
5601 REGCP_SET(ST.lastcp);
5602 PUSH_STATE_GOTO(WHILEM_A_min,
5603 /*A*/ NEXTOPER(ST.save_curlyx->u.curlyx.me) + EXTRA_STEP_2ARGS,
5605 assert(0); /* NOTREACHED */
5608 #define ST st->u.branch
5610 case BRANCHJ: /* /(...|A|...)/ with long next pointer */
5611 next = scan + ARG(scan);
5614 scan = NEXTOPER(scan);
5617 case BRANCH: /* /(...|A|...)/ */
5618 scan = NEXTOPER(scan); /* scan now points to inner node */
5619 ST.lastparen = rex->lastparen;
5620 ST.lastcloseparen = rex->lastcloseparen;
5621 ST.next_branch = next;
5624 /* Now go into the branch */
5626 PUSH_YES_STATE_GOTO(BRANCH_next, scan, locinput);
5628 PUSH_STATE_GOTO(BRANCH_next, scan, locinput);
5630 assert(0); /* NOTREACHED */
5632 case CUTGROUP: /* /(*THEN)/ */
5633 sv_yes_mark = st->u.mark.mark_name = scan->flags ? NULL :
5634 MUTABLE_SV(rexi->data->data[ ARG( scan ) ]);
5635 PUSH_STATE_GOTO(CUTGROUP_next, next, locinput);
5636 assert(0); /* NOTREACHED */
5638 case CUTGROUP_next_fail:
5641 if (st->u.mark.mark_name)
5642 sv_commit = st->u.mark.mark_name;
5644 assert(0); /* NOTREACHED */
5648 assert(0); /* NOTREACHED */
5650 case BRANCH_next_fail: /* that branch failed; try the next, if any */
5655 REGCP_UNWIND(ST.cp);
5656 UNWIND_PAREN(ST.lastparen, ST.lastcloseparen);
5657 scan = ST.next_branch;
5658 /* no more branches? */
5659 if (!scan || (OP(scan) != BRANCH && OP(scan) != BRANCHJ)) {
5661 PerlIO_printf( Perl_debug_log,
5662 "%*s %sBRANCH failed...%s\n",
5663 REPORT_CODE_OFF+depth*2, "",
5669 continue; /* execute next BRANCH[J] op */
5670 assert(0); /* NOTREACHED */
5672 case MINMOD: /* next op will be non-greedy, e.g. A*? */
5677 #define ST st->u.curlym
5679 case CURLYM: /* /A{m,n}B/ where A is fixed-length */
5681 /* This is an optimisation of CURLYX that enables us to push
5682 * only a single backtracking state, no matter how many matches
5683 * there are in {m,n}. It relies on the pattern being constant
5684 * length, with no parens to influence future backrefs
5688 scan = NEXTOPER(scan) + NODE_STEP_REGNODE;
5690 ST.lastparen = rex->lastparen;
5691 ST.lastcloseparen = rex->lastcloseparen;
5693 /* if paren positive, emulate an OPEN/CLOSE around A */
5695 U32 paren = ST.me->flags;
5696 if (paren > maxopenparen)
5697 maxopenparen = paren;
5698 scan += NEXT_OFF(scan); /* Skip former OPEN. */
5706 ST.c1 = CHRTEST_UNINIT;
5709 if (!(ST.minmod ? ARG1(ST.me) : ARG2(ST.me))) /* min/max */
5712 curlym_do_A: /* execute the A in /A{m,n}B/ */
5713 PUSH_YES_STATE_GOTO(CURLYM_A, ST.A, locinput); /* match A */
5714 assert(0); /* NOTREACHED */
5716 case CURLYM_A: /* we've just matched an A */
5718 /* after first match, determine A's length: u.curlym.alen */
5719 if (ST.count == 1) {
5720 if (reginfo->is_utf8_target) {
5721 char *s = st->locinput;
5722 while (s < locinput) {
5728 ST.alen = locinput - st->locinput;
5731 ST.count = ST.minmod ? ARG1(ST.me) : ARG2(ST.me);
5734 PerlIO_printf(Perl_debug_log,
5735 "%*s CURLYM now matched %"IVdf" times, len=%"IVdf"...\n",
5736 (int)(REPORT_CODE_OFF+(depth*2)), "",
5737 (IV) ST.count, (IV)ST.alen)
5740 if (cur_eval && cur_eval->u.eval.close_paren &&
5741 cur_eval->u.eval.close_paren == (U32)ST.me->flags)
5745 I32 max = (ST.minmod ? ARG1(ST.me) : ARG2(ST.me));
5746 if ( max == REG_INFTY || ST.count < max )
5747 goto curlym_do_A; /* try to match another A */
5749 goto curlym_do_B; /* try to match B */
5751 case CURLYM_A_fail: /* just failed to match an A */
5752 REGCP_UNWIND(ST.cp);
5754 if (ST.minmod || ST.count < ARG1(ST.me) /* min*/
5755 || (cur_eval && cur_eval->u.eval.close_paren &&
5756 cur_eval->u.eval.close_paren == (U32)ST.me->flags))
5759 curlym_do_B: /* execute the B in /A{m,n}B/ */
5760 if (ST.c1 == CHRTEST_UNINIT) {
5761 /* calculate c1 and c2 for possible match of 1st char
5762 * following curly */
5763 ST.c1 = ST.c2 = CHRTEST_VOID;
5764 if (HAS_TEXT(ST.B) || JUMPABLE(ST.B)) {
5765 regnode *text_node = ST.B;
5766 if (! HAS_TEXT(text_node))
5767 FIND_NEXT_IMPT(text_node);
5770 (HAS_TEXT(text_node) && PL_regkind[OP(text_node)] == EXACT)
5772 But the former is redundant in light of the latter.
5774 if this changes back then the macro for
5775 IS_TEXT and friends need to change.
5777 if (PL_regkind[OP(text_node)] == EXACT) {
5778 if (! S_setup_EXACTISH_ST_c1_c2(aTHX_
5779 text_node, &ST.c1, ST.c1_utf8, &ST.c2, ST.c2_utf8,
5789 PerlIO_printf(Perl_debug_log,
5790 "%*s CURLYM trying tail with matches=%"IVdf"...\n",
5791 (int)(REPORT_CODE_OFF+(depth*2)),
5794 if (! NEXTCHR_IS_EOS && ST.c1 != CHRTEST_VOID) {
5795 if (! UTF8_IS_INVARIANT(nextchr) && utf8_target) {
5796 if (memNE(locinput, ST.c1_utf8, UTF8SKIP(locinput))
5797 && memNE(locinput, ST.c2_utf8, UTF8SKIP(locinput)))
5799 /* simulate B failing */
5801 PerlIO_printf(Perl_debug_log,
5802 "%*s CURLYM Fast bail next target=U+%"UVXf" c1=U+%"UVXf" c2=U+%"UVXf"\n",
5803 (int)(REPORT_CODE_OFF+(depth*2)),"",
5804 valid_utf8_to_uvchr((U8 *) locinput, NULL),
5805 valid_utf8_to_uvchr(ST.c1_utf8, NULL),
5806 valid_utf8_to_uvchr(ST.c2_utf8, NULL))
5808 state_num = CURLYM_B_fail;
5809 goto reenter_switch;
5812 else if (nextchr != ST.c1 && nextchr != ST.c2) {
5813 /* simulate B failing */
5815 PerlIO_printf(Perl_debug_log,
5816 "%*s CURLYM Fast bail next target=U+%X c1=U+%X c2=U+%X\n",
5817 (int)(REPORT_CODE_OFF+(depth*2)),"",
5818 (int) nextchr, ST.c1, ST.c2)
5820 state_num = CURLYM_B_fail;
5821 goto reenter_switch;
5826 /* emulate CLOSE: mark current A as captured */
5827 I32 paren = ST.me->flags;
5829 rex->offs[paren].start
5830 = HOPc(locinput, -ST.alen) - reginfo->strbeg;
5831 rex->offs[paren].end = locinput - reginfo->strbeg;
5832 if ((U32)paren > rex->lastparen)
5833 rex->lastparen = paren;
5834 rex->lastcloseparen = paren;
5837 rex->offs[paren].end = -1;
5838 if (cur_eval && cur_eval->u.eval.close_paren &&
5839 cur_eval->u.eval.close_paren == (U32)ST.me->flags)
5848 PUSH_STATE_GOTO(CURLYM_B, ST.B, locinput); /* match B */
5849 assert(0); /* NOTREACHED */
5851 case CURLYM_B_fail: /* just failed to match a B */
5852 REGCP_UNWIND(ST.cp);
5853 UNWIND_PAREN(ST.lastparen, ST.lastcloseparen);
5855 I32 max = ARG2(ST.me);
5856 if (max != REG_INFTY && ST.count == max)
5858 goto curlym_do_A; /* try to match a further A */
5860 /* backtrack one A */
5861 if (ST.count == ARG1(ST.me) /* min */)
5864 SET_locinput(HOPc(locinput, -ST.alen));
5865 goto curlym_do_B; /* try to match B */
5868 #define ST st->u.curly
5870 #define CURLY_SETPAREN(paren, success) \
5873 rex->offs[paren].start = HOPc(locinput, -1) - reginfo->strbeg; \
5874 rex->offs[paren].end = locinput - reginfo->strbeg; \
5875 if (paren > rex->lastparen) \
5876 rex->lastparen = paren; \
5877 rex->lastcloseparen = paren; \
5880 rex->offs[paren].end = -1; \
5881 rex->lastparen = ST.lastparen; \
5882 rex->lastcloseparen = ST.lastcloseparen; \
5886 case STAR: /* /A*B/ where A is width 1 char */
5890 scan = NEXTOPER(scan);
5893 case PLUS: /* /A+B/ where A is width 1 char */
5897 scan = NEXTOPER(scan);
5900 case CURLYN: /* /(A){m,n}B/ where A is width 1 char */
5901 ST.paren = scan->flags; /* Which paren to set */
5902 ST.lastparen = rex->lastparen;
5903 ST.lastcloseparen = rex->lastcloseparen;
5904 if (ST.paren > maxopenparen)
5905 maxopenparen = ST.paren;
5906 ST.min = ARG1(scan); /* min to match */
5907 ST.max = ARG2(scan); /* max to match */
5908 if (cur_eval && cur_eval->u.eval.close_paren &&
5909 cur_eval->u.eval.close_paren == (U32)ST.paren) {
5913 scan = regnext(NEXTOPER(scan) + NODE_STEP_REGNODE);
5916 case CURLY: /* /A{m,n}B/ where A is width 1 char */
5918 ST.min = ARG1(scan); /* min to match */
5919 ST.max = ARG2(scan); /* max to match */
5920 scan = NEXTOPER(scan) + NODE_STEP_REGNODE;
5923 * Lookahead to avoid useless match attempts
5924 * when we know what character comes next.
5926 * Used to only do .*x and .*?x, but now it allows
5927 * for )'s, ('s and (?{ ... })'s to be in the way
5928 * of the quantifier and the EXACT-like node. -- japhy
5931 assert(ST.min <= ST.max);
5932 if (! HAS_TEXT(next) && ! JUMPABLE(next)) {
5933 ST.c1 = ST.c2 = CHRTEST_VOID;
5936 regnode *text_node = next;
5938 if (! HAS_TEXT(text_node))
5939 FIND_NEXT_IMPT(text_node);
5941 if (! HAS_TEXT(text_node))
5942 ST.c1 = ST.c2 = CHRTEST_VOID;
5944 if ( PL_regkind[OP(text_node)] != EXACT ) {
5945 ST.c1 = ST.c2 = CHRTEST_VOID;
5949 /* Currently we only get here when
5951 PL_rekind[OP(text_node)] == EXACT
5953 if this changes back then the macro for IS_TEXT and
5954 friends need to change. */
5955 if (! S_setup_EXACTISH_ST_c1_c2(aTHX_
5956 text_node, &ST.c1, ST.c1_utf8, &ST.c2, ST.c2_utf8,
5968 char *li = locinput;
5971 regrepeat(rex, &li, ST.A, reginfo, ST.min, depth)
5977 if (ST.c1 == CHRTEST_VOID)
5978 goto curly_try_B_min;
5980 ST.oldloc = locinput;
5982 /* set ST.maxpos to the furthest point along the
5983 * string that could possibly match */
5984 if (ST.max == REG_INFTY) {
5985 ST.maxpos = reginfo->strend - 1;
5987 while (UTF8_IS_CONTINUATION(*(U8*)ST.maxpos))
5990 else if (utf8_target) {
5991 int m = ST.max - ST.min;
5992 for (ST.maxpos = locinput;
5993 m >0 && ST.maxpos < reginfo->strend; m--)
5994 ST.maxpos += UTF8SKIP(ST.maxpos);
5997 ST.maxpos = locinput + ST.max - ST.min;
5998 if (ST.maxpos >= reginfo->strend)
5999 ST.maxpos = reginfo->strend - 1;
6001 goto curly_try_B_min_known;
6005 /* avoid taking address of locinput, so it can remain
6007 char *li = locinput;
6008 ST.count = regrepeat(rex, &li, ST.A, reginfo, ST.max, depth);
6009 if (ST.count < ST.min)
6012 if ((ST.count > ST.min)
6013 && (PL_regkind[OP(ST.B)] == EOL) && (OP(ST.B) != MEOL))
6015 /* A{m,n} must come at the end of the string, there's
6016 * no point in backing off ... */
6018 /* ...except that $ and \Z can match before *and* after
6019 newline at the end. Consider "\n\n" =~ /\n+\Z\n/.
6020 We may back off by one in this case. */
6021 if (UCHARAT(locinput - 1) == '\n' && OP(ST.B) != EOS)
6025 goto curly_try_B_max;
6027 assert(0); /* NOTREACHED */
6030 case CURLY_B_min_known_fail:
6031 /* failed to find B in a non-greedy match where c1,c2 valid */
6033 REGCP_UNWIND(ST.cp);
6035 UNWIND_PAREN(ST.lastparen, ST.lastcloseparen);
6037 /* Couldn't or didn't -- move forward. */
6038 ST.oldloc = locinput;
6040 locinput += UTF8SKIP(locinput);
6044 curly_try_B_min_known:
6045 /* find the next place where 'B' could work, then call B */
6049 n = (ST.oldloc == locinput) ? 0 : 1;
6050 if (ST.c1 == ST.c2) {
6051 /* set n to utf8_distance(oldloc, locinput) */
6052 while (locinput <= ST.maxpos
6053 && memNE(locinput, ST.c1_utf8, UTF8SKIP(locinput)))
6055 locinput += UTF8SKIP(locinput);
6060 /* set n to utf8_distance(oldloc, locinput) */
6061 while (locinput <= ST.maxpos
6062 && memNE(locinput, ST.c1_utf8, UTF8SKIP(locinput))
6063 && memNE(locinput, ST.c2_utf8, UTF8SKIP(locinput)))
6065 locinput += UTF8SKIP(locinput);
6070 else { /* Not utf8_target */
6071 if (ST.c1 == ST.c2) {
6072 while (locinput <= ST.maxpos &&
6073 UCHARAT(locinput) != ST.c1)
6077 while (locinput <= ST.maxpos
6078 && UCHARAT(locinput) != ST.c1
6079 && UCHARAT(locinput) != ST.c2)
6082 n = locinput - ST.oldloc;
6084 if (locinput > ST.maxpos)
6087 /* In /a{m,n}b/, ST.oldloc is at "a" x m, locinput is
6088 * at b; check that everything between oldloc and
6089 * locinput matches */
6090 char *li = ST.oldloc;
6092 if (regrepeat(rex, &li, ST.A, reginfo, n, depth) < n)
6094 assert(n == REG_INFTY || locinput == li);
6096 CURLY_SETPAREN(ST.paren, ST.count);
6097 if (cur_eval && cur_eval->u.eval.close_paren &&
6098 cur_eval->u.eval.close_paren == (U32)ST.paren) {
6101 PUSH_STATE_GOTO(CURLY_B_min_known, ST.B, locinput);
6103 assert(0); /* NOTREACHED */
6106 case CURLY_B_min_fail:
6107 /* failed to find B in a non-greedy match where c1,c2 invalid */
6109 REGCP_UNWIND(ST.cp);
6111 UNWIND_PAREN(ST.lastparen, ST.lastcloseparen);
6113 /* failed -- move forward one */
6115 char *li = locinput;
6116 if (!regrepeat(rex, &li, ST.A, reginfo, 1, depth)) {
6123 if (ST.count <= ST.max || (ST.max == REG_INFTY &&
6124 ST.count > 0)) /* count overflow ? */
6127 CURLY_SETPAREN(ST.paren, ST.count);
6128 if (cur_eval && cur_eval->u.eval.close_paren &&
6129 cur_eval->u.eval.close_paren == (U32)ST.paren) {
6132 PUSH_STATE_GOTO(CURLY_B_min, ST.B, locinput);
6136 assert(0); /* NOTREACHED */
6140 /* a successful greedy match: now try to match B */
6141 if (cur_eval && cur_eval->u.eval.close_paren &&
6142 cur_eval->u.eval.close_paren == (U32)ST.paren) {
6146 bool could_match = locinput < reginfo->strend;
6148 /* If it could work, try it. */
6149 if (ST.c1 != CHRTEST_VOID && could_match) {
6150 if (! UTF8_IS_INVARIANT(UCHARAT(locinput)) && utf8_target)
6152 could_match = memEQ(locinput,
6157 UTF8SKIP(locinput));
6160 could_match = UCHARAT(locinput) == ST.c1
6161 || UCHARAT(locinput) == ST.c2;
6164 if (ST.c1 == CHRTEST_VOID || could_match) {
6165 CURLY_SETPAREN(ST.paren, ST.count);
6166 PUSH_STATE_GOTO(CURLY_B_max, ST.B, locinput);
6167 assert(0); /* NOTREACHED */
6172 case CURLY_B_max_fail:
6173 /* failed to find B in a greedy match */
6175 REGCP_UNWIND(ST.cp);
6177 UNWIND_PAREN(ST.lastparen, ST.lastcloseparen);
6180 if (--ST.count < ST.min)
6182 locinput = HOPc(locinput, -1);
6183 goto curly_try_B_max;
6187 case END: /* last op of main pattern */
6190 /* we've just finished A in /(??{A})B/; now continue with B */
6192 st->u.eval.prev_rex = rex_sv; /* inner */
6194 /* Save *all* the positions. */
6195 st->u.eval.cp = regcppush(rex, 0, maxopenparen);
6196 rex_sv = cur_eval->u.eval.prev_rex;
6197 is_utf8_pat = reginfo->is_utf8_pat = cBOOL(RX_UTF8(rex_sv));
6198 SET_reg_curpm(rex_sv);
6199 rex = ReANY(rex_sv);
6200 rexi = RXi_GET(rex);
6201 cur_curlyx = cur_eval->u.eval.prev_curlyx;
6203 REGCP_SET(st->u.eval.lastcp);
6205 /* Restore parens of the outer rex without popping the
6207 S_regcp_restore(aTHX_ rex, cur_eval->u.eval.lastcp,
6210 st->u.eval.prev_eval = cur_eval;
6211 cur_eval = cur_eval->u.eval.prev_eval;
6213 PerlIO_printf(Perl_debug_log, "%*s EVAL trying tail ... %"UVxf"\n",
6214 REPORT_CODE_OFF+depth*2, "",PTR2UV(cur_eval)););
6215 if ( nochange_depth )
6218 PUSH_YES_STATE_GOTO(EVAL_AB, st->u.eval.prev_eval->u.eval.B,
6219 locinput); /* match B */
6222 if (locinput < reginfo->till) {
6223 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
6224 "%sMatch possible, but length=%ld is smaller than requested=%ld, failing!%s\n",
6226 (long)(locinput - startpos),
6227 (long)(reginfo->till - startpos),
6230 sayNO_SILENT; /* Cannot match: too short. */
6232 sayYES; /* Success! */
6234 case SUCCEED: /* successful SUSPEND/UNLESSM/IFMATCH/CURLYM */
6236 PerlIO_printf(Perl_debug_log,
6237 "%*s %ssubpattern success...%s\n",
6238 REPORT_CODE_OFF+depth*2, "", PL_colors[4], PL_colors[5]));
6239 sayYES; /* Success! */
6242 #define ST st->u.ifmatch
6247 case SUSPEND: /* (?>A) */
6249 newstart = locinput;
6252 case UNLESSM: /* -ve lookaround: (?!A), or with flags, (?<!A) */
6254 goto ifmatch_trivial_fail_test;
6256 case IFMATCH: /* +ve lookaround: (?=A), or with flags, (?<=A) */
6258 ifmatch_trivial_fail_test:
6260 char * const s = HOPBACKc(locinput, scan->flags);
6265 sw = 1 - cBOOL(ST.wanted);
6269 next = scan + ARG(scan);
6277 newstart = locinput;
6281 ST.logical = logical;
6282 logical = 0; /* XXX: reset state of logical once it has been saved into ST */
6284 /* execute body of (?...A) */
6285 PUSH_YES_STATE_GOTO(IFMATCH_A, NEXTOPER(NEXTOPER(scan)), newstart);
6286 assert(0); /* NOTREACHED */
6289 case IFMATCH_A_fail: /* body of (?...A) failed */
6290 ST.wanted = !ST.wanted;
6293 case IFMATCH_A: /* body of (?...A) succeeded */
6295 sw = cBOOL(ST.wanted);
6297 else if (!ST.wanted)
6300 if (OP(ST.me) != SUSPEND) {
6301 /* restore old position except for (?>...) */
6302 locinput = st->locinput;
6304 scan = ST.me + ARG(ST.me);
6307 continue; /* execute B */
6311 case LONGJMP: /* alternative with many branches compiles to
6312 * (BRANCHJ; EXACT ...; LONGJMP ) x N */
6313 next = scan + ARG(scan);
6318 case COMMIT: /* (*COMMIT) */
6319 reginfo->cutpoint = reginfo->strend;
6322 case PRUNE: /* (*PRUNE) */
6324 sv_yes_mark = sv_commit = MUTABLE_SV(rexi->data->data[ ARG( scan ) ]);
6325 PUSH_STATE_GOTO(COMMIT_next, next, locinput);
6326 assert(0); /* NOTREACHED */
6328 case COMMIT_next_fail:
6332 case OPFAIL: /* (*FAIL) */
6334 assert(0); /* NOTREACHED */
6336 #define ST st->u.mark
6337 case MARKPOINT: /* (*MARK:foo) */
6338 ST.prev_mark = mark_state;
6339 ST.mark_name = sv_commit = sv_yes_mark
6340 = MUTABLE_SV(rexi->data->data[ ARG( scan ) ]);
6342 ST.mark_loc = locinput;
6343 PUSH_YES_STATE_GOTO(MARKPOINT_next, next, locinput);
6344 assert(0); /* NOTREACHED */
6346 case MARKPOINT_next:
6347 mark_state = ST.prev_mark;
6349 assert(0); /* NOTREACHED */
6351 case MARKPOINT_next_fail:
6352 if (popmark && sv_eq(ST.mark_name,popmark))
6354 if (ST.mark_loc > startpoint)
6355 reginfo->cutpoint = HOPBACKc(ST.mark_loc, 1);
6356 popmark = NULL; /* we found our mark */
6357 sv_commit = ST.mark_name;
6360 PerlIO_printf(Perl_debug_log,
6361 "%*s %ssetting cutpoint to mark:%"SVf"...%s\n",
6362 REPORT_CODE_OFF+depth*2, "",
6363 PL_colors[4], SVfARG(sv_commit), PL_colors[5]);
6366 mark_state = ST.prev_mark;
6367 sv_yes_mark = mark_state ?
6368 mark_state->u.mark.mark_name : NULL;
6370 assert(0); /* NOTREACHED */
6372 case SKIP: /* (*SKIP) */
6374 /* (*SKIP) : if we fail we cut here*/
6375 ST.mark_name = NULL;
6376 ST.mark_loc = locinput;
6377 PUSH_STATE_GOTO(SKIP_next,next, locinput);
6379 /* (*SKIP:NAME) : if there is a (*MARK:NAME) fail where it was,
6380 otherwise do nothing. Meaning we need to scan
6382 regmatch_state *cur = mark_state;
6383 SV *find = MUTABLE_SV(rexi->data->data[ ARG( scan ) ]);
6386 if ( sv_eq( cur->u.mark.mark_name,
6389 ST.mark_name = find;
6390 PUSH_STATE_GOTO( SKIP_next, next, locinput);
6392 cur = cur->u.mark.prev_mark;
6395 /* Didn't find our (*MARK:NAME) so ignore this (*SKIP:NAME) */
6398 case SKIP_next_fail:
6400 /* (*CUT:NAME) - Set up to search for the name as we
6401 collapse the stack*/
6402 popmark = ST.mark_name;
6404 /* (*CUT) - No name, we cut here.*/
6405 if (ST.mark_loc > startpoint)
6406 reginfo->cutpoint = HOPBACKc(ST.mark_loc, 1);
6407 /* but we set sv_commit to latest mark_name if there
6408 is one so they can test to see how things lead to this
6411 sv_commit=mark_state->u.mark.mark_name;
6415 assert(0); /* NOTREACHED */
6418 case LNBREAK: /* \R */
6419 if ((n=is_LNBREAK_safe(locinput, reginfo->strend, utf8_target))) {
6426 PerlIO_printf(Perl_error_log, "%"UVxf" %d\n",
6427 PTR2UV(scan), OP(scan));
6428 Perl_croak(aTHX_ "regexp memory corruption");
6430 /* this is a point to jump to in order to increment
6431 * locinput by one character */
6433 assert(!NEXTCHR_IS_EOS);
6435 locinput += PL_utf8skip[nextchr];
6436 /* locinput is allowed to go 1 char off the end, but not 2+ */
6437 if (locinput > reginfo->strend)
6446 /* switch break jumps here */
6447 scan = next; /* prepare to execute the next op and ... */
6448 continue; /* ... jump back to the top, reusing st */
6449 assert(0); /* NOTREACHED */
6452 /* push a state that backtracks on success */
6453 st->u.yes.prev_yes_state = yes_state;
6457 /* push a new regex state, then continue at scan */
6459 regmatch_state *newst;
6462 regmatch_state *cur = st;
6463 regmatch_state *curyes = yes_state;
6465 regmatch_slab *slab = PL_regmatch_slab;
6466 for (;curd > -1;cur--,curd--) {
6467 if (cur < SLAB_FIRST(slab)) {
6469 cur = SLAB_LAST(slab);
6471 PerlIO_printf(Perl_error_log, "%*s#%-3d %-10s %s\n",
6472 REPORT_CODE_OFF + 2 + depth * 2,"",
6473 curd, PL_reg_name[cur->resume_state],
6474 (curyes == cur) ? "yes" : ""
6477 curyes = cur->u.yes.prev_yes_state;
6480 DEBUG_STATE_pp("push")
6483 st->locinput = locinput;
6485 if (newst > SLAB_LAST(PL_regmatch_slab))
6486 newst = S_push_slab(aTHX);
6487 PL_regmatch_state = newst;
6489 locinput = pushinput;
6492 assert(0); /* NOTREACHED */
6497 * We get here only if there's trouble -- normally "case END" is
6498 * the terminating point.
6500 Perl_croak(aTHX_ "corrupted regexp pointers");
6506 /* we have successfully completed a subexpression, but we must now
6507 * pop to the state marked by yes_state and continue from there */
6508 assert(st != yes_state);
6510 while (st != yes_state) {
6512 if (st < SLAB_FIRST(PL_regmatch_slab)) {
6513 PL_regmatch_slab = PL_regmatch_slab->prev;
6514 st = SLAB_LAST(PL_regmatch_slab);
6518 DEBUG_STATE_pp("pop (no final)");
6520 DEBUG_STATE_pp("pop (yes)");
6526 while (yes_state < SLAB_FIRST(PL_regmatch_slab)
6527 || yes_state > SLAB_LAST(PL_regmatch_slab))
6529 /* not in this slab, pop slab */
6530 depth -= (st - SLAB_FIRST(PL_regmatch_slab) + 1);
6531 PL_regmatch_slab = PL_regmatch_slab->prev;
6532 st = SLAB_LAST(PL_regmatch_slab);
6534 depth -= (st - yes_state);
6537 yes_state = st->u.yes.prev_yes_state;
6538 PL_regmatch_state = st;
6541 locinput= st->locinput;
6542 state_num = st->resume_state + no_final;
6543 goto reenter_switch;
6546 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "%sMatch successful!%s\n",
6547 PL_colors[4], PL_colors[5]));
6549 if (reginfo->info_aux_eval) {
6550 /* each successfully executed (?{...}) block does the equivalent of
6551 * local $^R = do {...}
6552 * When popping the save stack, all these locals would be undone;
6553 * bypass this by setting the outermost saved $^R to the latest
6555 if (oreplsv != GvSV(PL_replgv))
6556 sv_setsv(oreplsv, GvSV(PL_replgv));
6563 PerlIO_printf(Perl_debug_log,
6564 "%*s %sfailed...%s\n",
6565 REPORT_CODE_OFF+depth*2, "",
6566 PL_colors[4], PL_colors[5])
6578 /* there's a previous state to backtrack to */
6580 if (st < SLAB_FIRST(PL_regmatch_slab)) {
6581 PL_regmatch_slab = PL_regmatch_slab->prev;
6582 st = SLAB_LAST(PL_regmatch_slab);
6584 PL_regmatch_state = st;
6585 locinput= st->locinput;
6587 DEBUG_STATE_pp("pop");
6589 if (yes_state == st)
6590 yes_state = st->u.yes.prev_yes_state;
6592 state_num = st->resume_state + 1; /* failure = success + 1 */
6593 goto reenter_switch;
6598 if (rex->intflags & PREGf_VERBARG_SEEN) {
6599 SV *sv_err = get_sv("REGERROR", 1);
6600 SV *sv_mrk = get_sv("REGMARK", 1);
6602 sv_commit = &PL_sv_no;
6604 sv_yes_mark = &PL_sv_yes;
6607 sv_commit = &PL_sv_yes;
6608 sv_yes_mark = &PL_sv_no;
6610 sv_setsv(sv_err, sv_commit);
6611 sv_setsv(sv_mrk, sv_yes_mark);
6615 if (last_pushed_cv) {
6618 PERL_UNUSED_VAR(SP);
6621 assert(!result || locinput - reginfo->strbeg >= 0);
6622 return result ? locinput - reginfo->strbeg : -1;
6626 - regrepeat - repeatedly match something simple, report how many
6628 * What 'simple' means is a node which can be the operand of a quantifier like
6631 * startposp - pointer a pointer to the start position. This is updated
6632 * to point to the byte following the highest successful
6634 * p - the regnode to be repeatedly matched against.
6635 * reginfo - struct holding match state, such as strend
6636 * max - maximum number of things to match.
6637 * depth - (for debugging) backtracking depth.
6640 S_regrepeat(pTHX_ regexp *prog, char **startposp, const regnode *p,
6641 regmatch_info *const reginfo, I32 max, int depth)
6644 char *scan; /* Pointer to current position in target string */
6646 char *loceol = reginfo->strend; /* local version */
6647 I32 hardcount = 0; /* How many matches so far */
6648 bool utf8_target = reginfo->is_utf8_target;
6649 int to_complement = 0; /* Invert the result? */
6651 _char_class_number classnum;
6653 PERL_UNUSED_ARG(depth);
6656 PERL_ARGS_ASSERT_REGREPEAT;
6659 if (max == REG_INFTY)
6661 else if (! utf8_target && loceol - scan > max)
6662 loceol = scan + max;
6664 /* Here, for the case of a non-UTF-8 target we have adjusted <loceol> down
6665 * to the maximum of how far we should go in it (leaving it set to the real
6666 * end, if the maximum permissible would take us beyond that). This allows
6667 * us to make the loop exit condition that we haven't gone past <loceol> to
6668 * also mean that we haven't exceeded the max permissible count, saving a
6669 * test each time through the loop. But it assumes that the OP matches a
6670 * single byte, which is true for most of the OPs below when applied to a
6671 * non-UTF-8 target. Those relatively few OPs that don't have this
6672 * characteristic will have to compensate.
6674 * There is no adjustment for UTF-8 targets, as the number of bytes per
6675 * character varies. OPs will have to test both that the count is less
6676 * than the max permissible (using <hardcount> to keep track), and that we
6677 * are still within the bounds of the string (using <loceol>. A few OPs
6678 * match a single byte no matter what the encoding. They can omit the max
6679 * test if, for the UTF-8 case, they do the adjustment that was skipped
6682 * Thus, the code above sets things up for the common case; and exceptional
6683 * cases need extra work; the common case is to make sure <scan> doesn't
6684 * go past <loceol>, and for UTF-8 to also use <hardcount> to make sure the
6685 * count doesn't exceed the maximum permissible */
6690 while (scan < loceol && hardcount < max && *scan != '\n') {
6691 scan += UTF8SKIP(scan);
6695 while (scan < loceol && *scan != '\n')
6701 while (scan < loceol && hardcount < max) {
6702 scan += UTF8SKIP(scan);
6709 case CANY: /* Move <scan> forward <max> bytes, unless goes off end */
6710 if (utf8_target && loceol - scan > max) {
6712 /* <loceol> hadn't been adjusted in the UTF-8 case */
6720 assert(STR_LEN(p) == reginfo->is_utf8_pat ? UTF8SKIP(STRING(p)) : 1);
6724 /* Can use a simple loop if the pattern char to match on is invariant
6725 * under UTF-8, or both target and pattern aren't UTF-8. Note that we
6726 * can use UTF8_IS_INVARIANT() even if the pattern isn't UTF-8, as it's
6727 * true iff it doesn't matter if the argument is in UTF-8 or not */
6728 if (UTF8_IS_INVARIANT(c) || (! utf8_target && ! reginfo->is_utf8_pat)) {
6729 if (utf8_target && loceol - scan > max) {
6730 /* We didn't adjust <loceol> because is UTF-8, but ok to do so,
6731 * since here, to match at all, 1 char == 1 byte */
6732 loceol = scan + max;
6734 while (scan < loceol && UCHARAT(scan) == c) {
6738 else if (reginfo->is_utf8_pat) {
6740 STRLEN scan_char_len;
6742 /* When both target and pattern are UTF-8, we have to do
6744 while (hardcount < max
6746 && (scan_char_len = UTF8SKIP(scan)) <= STR_LEN(p)
6747 && memEQ(scan, STRING(p), scan_char_len))
6749 scan += scan_char_len;
6753 else if (! UTF8_IS_ABOVE_LATIN1(c)) {
6755 /* Target isn't utf8; convert the character in the UTF-8
6756 * pattern to non-UTF8, and do a simple loop */
6757 c = TWO_BYTE_UTF8_TO_UNI(c, *(STRING(p) + 1));
6758 while (scan < loceol && UCHARAT(scan) == c) {
6761 } /* else pattern char is above Latin1, can't possibly match the
6766 /* Here, the string must be utf8; pattern isn't, and <c> is
6767 * different in utf8 than not, so can't compare them directly.
6768 * Outside the loop, find the two utf8 bytes that represent c, and
6769 * then look for those in sequence in the utf8 string */
6770 U8 high = UTF8_TWO_BYTE_HI(c);
6771 U8 low = UTF8_TWO_BYTE_LO(c);
6773 while (hardcount < max
6774 && scan + 1 < loceol
6775 && UCHARAT(scan) == high
6776 && UCHARAT(scan + 1) == low)
6785 utf8_flags = FOLDEQ_UTF8_NOMIX_ASCII;
6789 RXp_MATCH_TAINTED_on(prog);
6790 utf8_flags = FOLDEQ_UTF8_LOCALE;
6798 case EXACTFU_TRICKYFOLD:
6800 utf8_flags = reginfo->is_utf8_pat ? FOLDEQ_S2_ALREADY_FOLDED : 0;
6804 U8 c1_utf8[UTF8_MAXBYTES+1], c2_utf8[UTF8_MAXBYTES+1];
6806 assert(STR_LEN(p) == reginfo->is_utf8_pat ? UTF8SKIP(STRING(p)) : 1);
6808 if (S_setup_EXACTISH_ST_c1_c2(aTHX_ p, &c1, c1_utf8, &c2, c2_utf8,
6811 if (c1 == CHRTEST_VOID) {
6812 /* Use full Unicode fold matching */
6813 char *tmpeol = reginfo->strend;
6814 STRLEN pat_len = reginfo->is_utf8_pat ? UTF8SKIP(STRING(p)) : 1;
6815 while (hardcount < max
6816 && foldEQ_utf8_flags(scan, &tmpeol, 0, utf8_target,
6817 STRING(p), NULL, pat_len,
6818 reginfo->is_utf8_pat, utf8_flags))
6821 tmpeol = reginfo->strend;
6825 else if (utf8_target) {
6827 while (scan < loceol
6829 && memEQ(scan, c1_utf8, UTF8SKIP(scan)))
6831 scan += UTF8SKIP(scan);
6836 while (scan < loceol
6838 && (memEQ(scan, c1_utf8, UTF8SKIP(scan))
6839 || memEQ(scan, c2_utf8, UTF8SKIP(scan))))
6841 scan += UTF8SKIP(scan);
6846 else if (c1 == c2) {
6847 while (scan < loceol && UCHARAT(scan) == c1) {
6852 while (scan < loceol &&
6853 (UCHARAT(scan) == c1 || UCHARAT(scan) == c2))
6862 case ANYOF_WARN_SUPER:
6864 while (hardcount < max
6866 && reginclass(prog, p, (U8*)scan, utf8_target))
6868 scan += UTF8SKIP(scan);
6872 while (scan < loceol && REGINCLASS(prog, p, (U8*)scan))
6877 /* The argument (FLAGS) to all the POSIX node types is the class number */
6884 RXp_MATCH_TAINTED_on(prog);
6885 if (! utf8_target) {
6886 while (scan < loceol && to_complement ^ cBOOL(isFOO_lc(FLAGS(p),
6892 while (hardcount < max && scan < loceol
6893 && to_complement ^ cBOOL(isFOO_utf8_lc(FLAGS(p),
6896 scan += UTF8SKIP(scan);
6909 if (utf8_target && loceol - scan > max) {
6911 /* We didn't adjust <loceol> at the beginning of this routine
6912 * because is UTF-8, but it is actually ok to do so, since here, to
6913 * match, 1 char == 1 byte. */
6914 loceol = scan + max;
6916 while (scan < loceol && _generic_isCC_A((U8) *scan, FLAGS(p))) {
6929 if (! utf8_target) {
6930 while (scan < loceol && ! _generic_isCC_A((U8) *scan, FLAGS(p))) {
6936 /* The complement of something that matches only ASCII matches all
6937 * UTF-8 variant code points, plus everything in ASCII that isn't
6939 while (hardcount < max && scan < loceol
6940 && (! UTF8_IS_INVARIANT(*scan)
6941 || ! _generic_isCC_A((U8) *scan, FLAGS(p))))
6943 scan += UTF8SKIP(scan);
6954 if (! utf8_target) {
6955 while (scan < loceol && to_complement
6956 ^ cBOOL(_generic_isCC((U8) *scan, FLAGS(p))))
6963 classnum = (_char_class_number) FLAGS(p);
6964 if (classnum < _FIRST_NON_SWASH_CC) {
6966 /* Here, a swash is needed for above-Latin1 code points.
6967 * Process as many Latin1 code points using the built-in rules.
6968 * Go to another loop to finish processing upon encountering
6969 * the first Latin1 code point. We could do that in this loop
6970 * as well, but the other way saves having to test if the swash
6971 * has been loaded every time through the loop: extra space to
6973 while (hardcount < max && scan < loceol) {
6974 if (UTF8_IS_INVARIANT(*scan)) {
6975 if (! (to_complement ^ cBOOL(_generic_isCC((U8) *scan,
6982 else if (UTF8_IS_DOWNGRADEABLE_START(*scan)) {
6983 if (! (to_complement
6984 ^ cBOOL(_generic_isCC(TWO_BYTE_UTF8_TO_UNI(*scan,
6993 goto found_above_latin1;
7000 /* For these character classes, the knowledge of how to handle
7001 * every code point is compiled in to Perl via a macro. This
7002 * code is written for making the loops as tight as possible.
7003 * It could be refactored to save space instead */
7005 case _CC_ENUM_SPACE: /* XXX would require separate code
7006 if we revert the change of \v
7009 case _CC_ENUM_PSXSPC:
7010 while (hardcount < max
7012 && (to_complement ^ cBOOL(isSPACE_utf8(scan))))
7014 scan += UTF8SKIP(scan);
7018 case _CC_ENUM_BLANK:
7019 while (hardcount < max
7021 && (to_complement ^ cBOOL(isBLANK_utf8(scan))))
7023 scan += UTF8SKIP(scan);
7027 case _CC_ENUM_XDIGIT:
7028 while (hardcount < max
7030 && (to_complement ^ cBOOL(isXDIGIT_utf8(scan))))
7032 scan += UTF8SKIP(scan);
7036 case _CC_ENUM_VERTSPACE:
7037 while (hardcount < max
7039 && (to_complement ^ cBOOL(isVERTWS_utf8(scan))))
7041 scan += UTF8SKIP(scan);
7045 case _CC_ENUM_CNTRL:
7046 while (hardcount < max
7048 && (to_complement ^ cBOOL(isCNTRL_utf8(scan))))
7050 scan += UTF8SKIP(scan);
7055 Perl_croak(aTHX_ "panic: regrepeat() node %d='%s' has an unexpected character class '%d'", OP(p), PL_reg_name[OP(p)], classnum);
7061 found_above_latin1: /* Continuation of POSIXU and NPOSIXU */
7063 /* Load the swash if not already present */
7064 if (! PL_utf8_swash_ptrs[classnum]) {
7065 U8 flags = _CORE_SWASH_INIT_ACCEPT_INVLIST;
7066 PL_utf8_swash_ptrs[classnum] = _core_swash_init(
7067 "utf8", swash_property_names[classnum],
7068 &PL_sv_undef, 1, 0, NULL, &flags);
7071 while (hardcount < max && scan < loceol
7072 && to_complement ^ cBOOL(_generic_utf8(
7075 swash_fetch(PL_utf8_swash_ptrs[classnum],
7079 scan += UTF8SKIP(scan);
7086 while (hardcount < max && scan < loceol &&
7087 (c=is_LNBREAK_utf8_safe(scan, loceol))) {
7092 /* LNBREAK can match one or two latin chars, which is ok, but we
7093 * have to use hardcount in this situation, and throw away the
7094 * adjustment to <loceol> done before the switch statement */
7095 loceol = reginfo->strend;
7096 while (scan < loceol && (c=is_LNBREAK_latin1_safe(scan, loceol))) {
7117 /* These are all 0 width, so match right here or not at all. */
7121 Perl_croak(aTHX_ "panic: regrepeat() called with unrecognized node type %d='%s'", OP(p), PL_reg_name[OP(p)]);
7122 assert(0); /* NOTREACHED */
7129 c = scan - *startposp;
7133 GET_RE_DEBUG_FLAGS_DECL;
7135 SV * const prop = sv_newmortal();
7136 regprop(prog, prop, p);
7137 PerlIO_printf(Perl_debug_log,
7138 "%*s %s can match %"IVdf" times out of %"IVdf"...\n",
7139 REPORT_CODE_OFF + depth*2, "", SvPVX_const(prop),(IV)c,(IV)max);
7147 #if !defined(PERL_IN_XSUB_RE) || defined(PLUGGABLE_RE_EXTENSION)
7149 - regclass_swash - prepare the utf8 swash. Wraps the shared core version to
7150 create a copy so that changes the caller makes won't change the shared one.
7151 If <altsvp> is non-null, will return NULL in it, for back-compat.
7154 Perl_regclass_swash(pTHX_ const regexp *prog, const regnode* node, bool doinit, SV** listsvp, SV **altsvp)
7156 PERL_ARGS_ASSERT_REGCLASS_SWASH;
7162 return newSVsv(core_regclass_swash(prog, node, doinit, listsvp));
7167 S_core_regclass_swash(pTHX_ const regexp *prog, const regnode* node, bool doinit, SV** listsvp)
7169 /* Returns the swash for the input 'node' in the regex 'prog'.
7170 * If <doinit> is true, will attempt to create the swash if not already
7172 * If <listsvp> is non-null, will return the swash initialization string in
7174 * Tied intimately to how regcomp.c sets up the data structure */
7181 RXi_GET_DECL(prog,progi);
7182 const struct reg_data * const data = prog ? progi->data : NULL;
7184 PERL_ARGS_ASSERT_CORE_REGCLASS_SWASH;
7186 assert(ANYOF_NONBITMAP(node));
7188 if (data && data->count) {
7189 const U32 n = ARG(node);
7191 if (data->what[n] == 's') {
7192 SV * const rv = MUTABLE_SV(data->data[n]);
7193 AV * const av = MUTABLE_AV(SvRV(rv));
7194 SV **const ary = AvARRAY(av);
7195 U8 swash_init_flags = _CORE_SWASH_INIT_ACCEPT_INVLIST;
7197 si = *ary; /* ary[0] = the string to initialize the swash with */
7199 /* Elements 2 and 3 are either both present or both absent. [2] is
7200 * any inversion list generated at compile time; [3] indicates if
7201 * that inversion list has any user-defined properties in it. */
7202 if (av_len(av) >= 2) {
7205 swash_init_flags |= _CORE_SWASH_INIT_USER_DEFINED_PROPERTY;
7212 /* Element [1] is reserved for the set-up swash. If already there,
7213 * return it; if not, create it and store it there */
7214 if (SvROK(ary[1])) {
7217 else if (si && doinit) {
7219 sw = _core_swash_init("utf8", /* the utf8 package */
7223 0, /* not from tr/// */
7226 (void)av_store(av, 1, sw);
7232 SV* matches_string = newSVpvn("", 0);
7234 /* Use the swash, if any, which has to have incorporated into it all
7236 if ((! sw || (invlist = _get_swash_invlist(sw)) == NULL)
7237 && (si && si != &PL_sv_undef))
7240 /* If no swash, use the input initialization string, if available */
7241 sv_catsv(matches_string, si);
7244 /* Add the inversion list to whatever we have. This may have come from
7245 * the swash, or from an input parameter */
7247 sv_catsv(matches_string, _invlist_contents(invlist));
7249 *listsvp = matches_string;
7256 - reginclass - determine if a character falls into a character class
7258 n is the ANYOF regnode
7259 p is the target string
7260 utf8_target tells whether p is in UTF-8.
7262 Returns true if matched; false otherwise.
7264 Note that this can be a synthetic start class, a combination of various
7265 nodes, so things you think might be mutually exclusive, such as locale,
7266 aren't. It can match both locale and non-locale
7271 S_reginclass(pTHX_ regexp * const prog, const regnode * const n, const U8* const p, const bool utf8_target)
7274 const char flags = ANYOF_FLAGS(n);
7278 PERL_ARGS_ASSERT_REGINCLASS;
7280 /* If c is not already the code point, get it. Note that
7281 * UTF8_IS_INVARIANT() works even if not in UTF-8 */
7282 if (! UTF8_IS_INVARIANT(c) && utf8_target) {
7284 c = utf8n_to_uvchr(p, UTF8_MAXBYTES, &c_len,
7285 (UTF8_ALLOW_DEFAULT & UTF8_ALLOW_ANYUV)
7286 | UTF8_ALLOW_FFFF | UTF8_CHECK_ONLY);
7287 /* see [perl #37836] for UTF8_ALLOW_ANYUV; [perl #38293] for
7288 * UTF8_ALLOW_FFFF */
7289 if (c_len == (STRLEN)-1)
7290 Perl_croak(aTHX_ "Malformed UTF-8 character (fatal)");
7293 /* If this character is potentially in the bitmap, check it */
7295 if (ANYOF_BITMAP_TEST(n, c))
7297 else if (flags & ANYOF_NON_UTF8_LATIN1_ALL
7303 else if (flags & ANYOF_LOCALE) {
7304 RXp_MATCH_TAINTED_on(prog);
7306 if ((flags & ANYOF_LOC_FOLD)
7307 && ANYOF_BITMAP_TEST(n, PL_fold_locale[c]))
7311 else if (ANYOF_CLASS_TEST_ANY_SET(n)) {
7313 /* The data structure is arranged so bits 0, 2, 4, ... are set
7314 * if the class includes the Posix character class given by
7315 * bit/2; and 1, 3, 5, ... are set if the class includes the
7316 * complemented Posix class given by int(bit/2). So we loop
7317 * through the bits, each time changing whether we complement
7318 * the result or not. Suppose for the sake of illustration
7319 * that bits 0-3 mean respectively, \w, \W, \s, \S. If bit 0
7320 * is set, it means there is a match for this ANYOF node if the
7321 * character is in the class given by the expression (0 / 2 = 0
7322 * = \w). If it is in that class, isFOO_lc() will return 1,
7323 * and since 'to_complement' is 0, the result will stay TRUE,
7324 * and we exit the loop. Suppose instead that bit 0 is 0, but
7325 * bit 1 is 1. That means there is a match if the character
7326 * matches \W. We won't bother to call isFOO_lc() on bit 0,
7327 * but will on bit 1. On the second iteration 'to_complement'
7328 * will be 1, so the exclusive or will reverse things, so we
7329 * are testing for \W. On the third iteration, 'to_complement'
7330 * will be 0, and we would be testing for \s; the fourth
7331 * iteration would test for \S, etc.
7333 * Note that this code assumes that all the classes are closed
7334 * under folding. For example, if a character matches \w, then
7335 * its fold does too; and vice versa. This should be true for
7336 * any well-behaved locale for all the currently defined Posix
7337 * classes, except for :lower: and :upper:, which are handled
7338 * by the pseudo-class :cased: which matches if either of the
7339 * other two does. To get rid of this assumption, an outer
7340 * loop could be used below to iterate over both the source
7341 * character, and its fold (if different) */
7344 int to_complement = 0;
7345 while (count < ANYOF_MAX) {
7346 if (ANYOF_CLASS_TEST(n, count)
7347 && to_complement ^ cBOOL(isFOO_lc(count/2, (U8) c)))
7359 /* If the bitmap didn't (or couldn't) match, and something outside the
7360 * bitmap could match, try that. Locale nodes specify completely the
7361 * behavior of code points in the bit map (otherwise, a utf8 target would
7362 * cause them to be treated as Unicode and not locale), except in
7363 * the very unlikely event when this node is a synthetic start class, which
7364 * could be a combination of locale and non-locale nodes. So allow locale
7365 * to match for the synthetic start class, which will give a false
7366 * positive that will be resolved when the match is done again as not part
7367 * of the synthetic start class */
7369 if (utf8_target && (flags & ANYOF_UNICODE_ALL) && c >= 256) {
7370 match = TRUE; /* Everything above 255 matches */
7372 else if (ANYOF_NONBITMAP(n)
7373 && ((flags & ANYOF_NONBITMAP_NON_UTF8)
7376 || (! (flags & ANYOF_LOCALE))
7377 || OP(n) == ANYOF_SYNTHETIC))))
7379 SV * const sw = core_regclass_swash(prog, n, TRUE, 0);
7384 } else { /* Convert to utf8 */
7386 utf8_p = bytes_to_utf8(p, &len);
7389 if (swash_fetch(sw, utf8_p, TRUE)) {
7393 /* If we allocated a string above, free it */
7394 if (! utf8_target) Safefree(utf8_p);
7398 if (UNICODE_IS_SUPER(c)
7399 && OP(n) == ANYOF_WARN_SUPER
7400 && ckWARN_d(WARN_NON_UNICODE))
7402 Perl_warner(aTHX_ packWARN(WARN_NON_UNICODE),
7403 "Code point 0x%04"UVXf" is not Unicode, all \\p{} matches fail; all \\P{} matches succeed", c);
7407 /* The xor complements the return if to invert: 1^1 = 0, 1^0 = 1 */
7408 return cBOOL(flags & ANYOF_INVERT) ^ match;
7412 S_reghop3(U8 *s, I32 off, const U8* lim)
7414 /* return the position 'off' UTF-8 characters away from 's', forward if
7415 * 'off' >= 0, backwards if negative. But don't go outside of position
7416 * 'lim', which better be < s if off < 0 */
7420 PERL_ARGS_ASSERT_REGHOP3;
7423 while (off-- && s < lim) {
7424 /* XXX could check well-formedness here */
7429 while (off++ && s > lim) {
7431 if (UTF8_IS_CONTINUED(*s)) {
7432 while (s > lim && UTF8_IS_CONTINUATION(*s))
7435 /* XXX could check well-formedness here */
7442 /* there are a bunch of places where we use two reghop3's that should
7443 be replaced with this routine. but since thats not done yet
7444 we ifdef it out - dmq
7447 S_reghop4(U8 *s, I32 off, const U8* llim, const U8* rlim)
7451 PERL_ARGS_ASSERT_REGHOP4;
7454 while (off-- && s < rlim) {
7455 /* XXX could check well-formedness here */
7460 while (off++ && s > llim) {
7462 if (UTF8_IS_CONTINUED(*s)) {
7463 while (s > llim && UTF8_IS_CONTINUATION(*s))
7466 /* XXX could check well-formedness here */
7474 S_reghopmaybe3(U8* s, I32 off, const U8* lim)
7478 PERL_ARGS_ASSERT_REGHOPMAYBE3;
7481 while (off-- && s < lim) {
7482 /* XXX could check well-formedness here */
7489 while (off++ && s > lim) {
7491 if (UTF8_IS_CONTINUED(*s)) {
7492 while (s > lim && UTF8_IS_CONTINUATION(*s))
7495 /* XXX could check well-formedness here */
7504 /* when executing a regex that may have (?{}), extra stuff needs setting
7505 up that will be visible to the called code, even before the current
7506 match has finished. In particular:
7508 * $_ is localised to the SV currently being matched;
7509 * pos($_) is created if necessary, ready to be updated on each call-out
7511 * a fake PMOP is created that can be set to PL_curpm (normally PL_curpm
7512 isn't set until the current pattern is successfully finished), so that
7513 $1 etc of the match-so-far can be seen;
7514 * save the old values of subbeg etc of the current regex, and set then
7515 to the current string (again, this is normally only done at the end
7520 S_setup_eval_state(pTHX_ regmatch_info *const reginfo)
7523 regexp *const rex = ReANY(reginfo->prog);
7524 regmatch_info_aux_eval *eval_state = reginfo->info_aux_eval;
7526 eval_state->rex = rex;
7529 /* Make $_ available to executed code. */
7530 if (reginfo->sv != DEFSV) {
7532 DEFSV_set(reginfo->sv);
7535 if (!(SvTYPE(reginfo->sv) >= SVt_PVMG && SvMAGIC(reginfo->sv)
7536 && (mg = mg_find(reginfo->sv, PERL_MAGIC_regex_global)))) {
7537 /* prepare for quick setting of pos */
7538 #ifdef PERL_OLD_COPY_ON_WRITE
7539 if (SvIsCOW(reginfo->sv))
7540 sv_force_normal_flags(reginfo->sv, 0);
7542 mg = sv_magicext(reginfo->sv, NULL, PERL_MAGIC_regex_global,
7543 &PL_vtbl_mglob, NULL, 0);
7546 eval_state->pos_magic = mg;
7547 eval_state->pos = mg->mg_len;
7550 eval_state->pos_magic = NULL;
7552 if (!PL_reg_curpm) {
7553 /* PL_reg_curpm is a fake PMOP that we can attach the current
7554 * regex to and point PL_curpm at, so that $1 et al are visible
7555 * within a /(?{})/. It's just allocated once per interpreter the
7556 * first time its needed */
7557 Newxz(PL_reg_curpm, 1, PMOP);
7560 SV* const repointer = &PL_sv_undef;
7561 /* this regexp is also owned by the new PL_reg_curpm, which
7562 will try to free it. */
7563 av_push(PL_regex_padav, repointer);
7564 PL_reg_curpm->op_pmoffset = av_len(PL_regex_padav);
7565 PL_regex_pad = AvARRAY(PL_regex_padav);
7569 SET_reg_curpm(reginfo->prog);
7570 eval_state->curpm = PL_curpm;
7571 PL_curpm = PL_reg_curpm;
7572 if (RXp_MATCH_COPIED(rex)) {
7573 /* Here is a serious problem: we cannot rewrite subbeg,
7574 since it may be needed if this match fails. Thus
7575 $` inside (?{}) could fail... */
7576 eval_state->subbeg = rex->subbeg;
7577 eval_state->sublen = rex->sublen;
7578 eval_state->suboffset = rex->suboffset;
7579 eval_state->subcoffset = rex->subcoffset;
7581 eval_state->saved_copy = rex->saved_copy;
7583 RXp_MATCH_COPIED_off(rex);
7586 eval_state->subbeg = NULL;
7587 rex->subbeg = (char *)reginfo->strbeg;
7589 rex->subcoffset = 0;
7590 rex->sublen = reginfo->strend - reginfo->strbeg;
7594 /* destructor to clear up regmatch_info_aux and regmatch_info_aux_eval */
7597 S_cleanup_regmatch_info_aux(pTHX_ void *arg)
7600 regmatch_info_aux *aux = (regmatch_info_aux *) arg;
7601 regmatch_info_aux_eval *eval_state = aux->info_aux_eval;
7604 Safefree(aux->poscache);
7608 /* undo the effects of S_setup_eval_state() */
7610 if (eval_state->subbeg) {
7611 regexp * const rex = eval_state->rex;
7612 rex->subbeg = eval_state->subbeg;
7613 rex->sublen = eval_state->sublen;
7614 rex->suboffset = eval_state->suboffset;
7615 rex->subcoffset = eval_state->subcoffset;
7617 rex->saved_copy = eval_state->saved_copy;
7619 RXp_MATCH_COPIED_on(rex);
7621 if (eval_state->pos_magic)
7622 eval_state->pos_magic->mg_len = eval_state->pos;
7624 PL_curpm = eval_state->curpm;
7627 PL_regmatch_state = aux->old_regmatch_state;
7628 PL_regmatch_slab = aux->old_regmatch_slab;
7630 /* free all slabs above current one - this must be the last action
7631 * of this function, as aux and eval_state are allocated within
7632 * slabs and may be freed here */
7634 s = PL_regmatch_slab->next;
7636 PL_regmatch_slab->next = NULL;
7638 regmatch_slab * const osl = s;
7647 S_to_utf8_substr(pTHX_ regexp *prog)
7649 /* Converts substr fields in prog from bytes to UTF-8, calling fbm_compile
7650 * on the converted value */
7654 PERL_ARGS_ASSERT_TO_UTF8_SUBSTR;
7657 if (prog->substrs->data[i].substr
7658 && !prog->substrs->data[i].utf8_substr) {
7659 SV* const sv = newSVsv(prog->substrs->data[i].substr);
7660 prog->substrs->data[i].utf8_substr = sv;
7661 sv_utf8_upgrade(sv);
7662 if (SvVALID(prog->substrs->data[i].substr)) {
7663 if (SvTAIL(prog->substrs->data[i].substr)) {
7664 /* Trim the trailing \n that fbm_compile added last
7666 SvCUR_set(sv, SvCUR(sv) - 1);
7667 /* Whilst this makes the SV technically "invalid" (as its
7668 buffer is no longer followed by "\0") when fbm_compile()
7669 adds the "\n" back, a "\0" is restored. */
7670 fbm_compile(sv, FBMcf_TAIL);
7674 if (prog->substrs->data[i].substr == prog->check_substr)
7675 prog->check_utf8 = sv;
7681 S_to_byte_substr(pTHX_ regexp *prog)
7683 /* Converts substr fields in prog from UTF-8 to bytes, calling fbm_compile
7684 * on the converted value; returns FALSE if can't be converted. */
7689 PERL_ARGS_ASSERT_TO_BYTE_SUBSTR;
7692 if (prog->substrs->data[i].utf8_substr
7693 && !prog->substrs->data[i].substr) {
7694 SV* sv = newSVsv(prog->substrs->data[i].utf8_substr);
7695 if (! sv_utf8_downgrade(sv, TRUE)) {
7698 if (SvVALID(prog->substrs->data[i].utf8_substr)) {
7699 if (SvTAIL(prog->substrs->data[i].utf8_substr)) {
7700 /* Trim the trailing \n that fbm_compile added last
7702 SvCUR_set(sv, SvCUR(sv) - 1);
7703 fbm_compile(sv, FBMcf_TAIL);
7707 prog->substrs->data[i].substr = sv;
7708 if (prog->substrs->data[i].utf8_substr == prog->check_utf8)
7709 prog->check_substr = sv;
7718 * c-indentation-style: bsd
7720 * indent-tabs-mode: nil
7723 * ex: set ts=8 sts=4 sw=4 et: