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
41 * pregcomp and pregexec -- regsub and regerror are not used in perl
43 * Copyright (c) 1986 by University of Toronto.
44 * Written by Henry Spencer. Not derived from licensed software.
46 * Permission is granted to anyone to use this software for any
47 * purpose on any computer system, and to redistribute it freely,
48 * subject to the following restrictions:
50 * 1. The author is not responsible for the consequences of use of
51 * this software, no matter how awful, even if they arise
54 * 2. The origin of this software must not be misrepresented, either
55 * by explicit claim or by omission.
57 * 3. Altered versions must be plainly marked as such, and must not
58 * be misrepresented as being the original software.
60 **** Alterations to Henry's code are...
62 **** Copyright (C) 1991, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999,
63 **** 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008
64 **** by Larry Wall and others
66 **** You may distribute under the terms of either the GNU General Public
67 **** License or the Artistic License, as specified in the README file.
69 * Beware that some of this code is subtly aware of the way operator
70 * precedence is structured in regular expressions. Serious changes in
71 * regular-expression syntax might require a total rethink.
74 #define PERL_IN_REGEXEC_C
77 #ifdef PERL_IN_XSUB_RE
83 #include "inline_invlist.c"
84 #include "unicode_constants.h"
87 /* At least one required character in the target string is expressible only in
89 static const char* const non_utf8_target_but_utf8_required
90 = "Can't match, because target string needs to be in UTF-8\n";
93 #define NON_UTF8_TARGET_BUT_UTF8_REQUIRED(target) STMT_START { \
94 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "%s", non_utf8_target_but_utf8_required));\
98 #define HAS_NONLATIN1_FOLD_CLOSURE(i) _HAS_NONLATIN1_FOLD_CLOSURE_ONLY_FOR_USE_BY_REGCOMP_DOT_C_AND_REGEXEC_DOT_C(i)
101 #define STATIC static
104 /* Valid only for non-utf8 strings: avoids the reginclass
105 * call if there are no complications: i.e., if everything matchable is
106 * straight forward in the bitmap */
107 #define REGINCLASS(prog,p,c) (ANYOF_FLAGS(p) ? reginclass(prog,p,c,c+1,0) \
108 : ANYOF_BITMAP_TEST(p,*(c)))
114 #define CHR_SVLEN(sv) (utf8_target ? sv_len_utf8(sv) : SvCUR(sv))
115 #define CHR_DIST(a,b) (reginfo->is_utf8_target ? utf8_distance(a,b) : a - b)
117 #define HOPc(pos,off) \
118 (char *)(reginfo->is_utf8_target \
119 ? reghop3((U8*)pos, off, \
120 (U8*)(off >= 0 ? reginfo->strend : reginfo->strbeg)) \
122 #define HOPBACKc(pos, off) \
123 (char*)(reginfo->is_utf8_target \
124 ? reghopmaybe3((U8*)pos, -off, (U8*)(reginfo->strbeg)) \
125 : (pos - off >= reginfo->strbeg) \
129 #define HOP3(pos,off,lim) (reginfo->is_utf8_target ? reghop3((U8*)(pos), off, (U8*)(lim)) : (U8*)(pos + off))
130 #define HOP3c(pos,off,lim) ((char*)HOP3(pos,off,lim))
132 /* like HOP3, but limits the result to <= lim even for the non-utf8 case.
133 * off must be >=0; args should be vars rather than expressions */
134 #define HOP3lim(pos,off,lim) (reginfo->is_utf8_target \
135 ? reghop3((U8*)(pos), off, (U8*)(lim)) \
136 : (U8*)((pos + off) > lim ? lim : (pos + off)))
138 #define HOP4(pos,off,llim, rlim) (reginfo->is_utf8_target \
139 ? reghop4((U8*)(pos), off, (U8*)(llim), (U8*)(rlim)) \
141 #define HOP4c(pos,off,llim, rlim) ((char*)HOP4(pos,off,llim, rlim))
143 #define NEXTCHR_EOS -10 /* nextchr has fallen off the end */
144 #define NEXTCHR_IS_EOS (nextchr < 0)
146 #define SET_nextchr \
147 nextchr = ((locinput < reginfo->strend) ? UCHARAT(locinput) : NEXTCHR_EOS)
149 #define SET_locinput(p) \
154 #define LOAD_UTF8_CHARCLASS(swash_ptr, property_name, invlist) STMT_START { \
156 U8 flags = _CORE_SWASH_INIT_ACCEPT_INVLIST; \
157 swash_ptr = _core_swash_init("utf8", property_name, &PL_sv_undef, \
158 1, 0, invlist, &flags); \
163 /* If in debug mode, we test that a known character properly matches */
165 # define LOAD_UTF8_CHARCLASS_DEBUG_TEST(swash_ptr, \
168 utf8_char_in_property) \
169 LOAD_UTF8_CHARCLASS(swash_ptr, property_name, invlist); \
170 assert(swash_fetch(swash_ptr, (U8 *) utf8_char_in_property, TRUE));
172 # define LOAD_UTF8_CHARCLASS_DEBUG_TEST(swash_ptr, \
175 utf8_char_in_property) \
176 LOAD_UTF8_CHARCLASS(swash_ptr, property_name, invlist)
179 #define LOAD_UTF8_CHARCLASS_ALNUM() LOAD_UTF8_CHARCLASS_DEBUG_TEST( \
180 PL_utf8_swash_ptrs[_CC_WORDCHAR], \
182 PL_XPosix_ptrs[_CC_WORDCHAR], \
183 LATIN_CAPITAL_LETTER_SHARP_S_UTF8);
185 #define LOAD_UTF8_CHARCLASS_GCB() /* Grapheme cluster boundaries */ \
187 LOAD_UTF8_CHARCLASS_DEBUG_TEST(PL_utf8_X_regular_begin, \
188 "_X_regular_begin", \
190 LATIN_CAPITAL_LETTER_SHARP_S_UTF8); \
191 LOAD_UTF8_CHARCLASS_DEBUG_TEST(PL_utf8_X_extend, \
194 COMBINING_GRAVE_ACCENT_UTF8); \
197 #define PLACEHOLDER /* Something for the preprocessor to grab onto */
198 /* TODO: Combine JUMPABLE and HAS_TEXT to cache OP(rn) */
200 /* for use after a quantifier and before an EXACT-like node -- japhy */
201 /* it would be nice to rework regcomp.sym to generate this stuff. sigh
203 * NOTE that *nothing* that affects backtracking should be in here, specifically
204 * VERBS must NOT be included. JUMPABLE is used to determine if we can ignore a
205 * node that is in between two EXACT like nodes when ascertaining what the required
206 * "follow" character is. This should probably be moved to regex compile time
207 * although it may be done at run time beause of the REF possibility - more
208 * investigation required. -- demerphq
210 #define JUMPABLE(rn) ( \
212 (OP(rn) == CLOSE && (!cur_eval || cur_eval->u.eval.close_paren != ARG(rn))) || \
214 OP(rn) == SUSPEND || OP(rn) == IFMATCH || \
215 OP(rn) == PLUS || OP(rn) == MINMOD || \
217 (PL_regkind[OP(rn)] == CURLY && ARG1(rn) > 0) \
219 #define IS_EXACT(rn) (PL_regkind[OP(rn)] == EXACT)
221 #define HAS_TEXT(rn) ( IS_EXACT(rn) || PL_regkind[OP(rn)] == REF )
224 /* Currently these are only used when PL_regkind[OP(rn)] == EXACT so
225 we don't need this definition. */
226 #define IS_TEXT(rn) ( OP(rn)==EXACT || OP(rn)==REF || OP(rn)==NREF )
227 #define IS_TEXTF(rn) ( OP(rn)==EXACTFU || OP(rn)==EXACTFU_SS || OP(rn)==EXACTFA || OP(rn)==EXACTFA_NO_TRIE || OP(rn)==EXACTF || OP(rn)==REFF || OP(rn)==NREFF )
228 #define IS_TEXTFL(rn) ( OP(rn)==EXACTFL || OP(rn)==REFFL || OP(rn)==NREFFL )
231 /* ... so we use this as its faster. */
232 #define IS_TEXT(rn) ( OP(rn)==EXACT )
233 #define IS_TEXTFU(rn) ( OP(rn)==EXACTFU || OP(rn)==EXACTFU_SS || OP(rn) == EXACTFA || OP(rn) == EXACTFA_NO_TRIE)
234 #define IS_TEXTF(rn) ( OP(rn)==EXACTF )
235 #define IS_TEXTFL(rn) ( OP(rn)==EXACTFL )
240 Search for mandatory following text node; for lookahead, the text must
241 follow but for lookbehind (rn->flags != 0) we skip to the next step.
243 #define FIND_NEXT_IMPT(rn) STMT_START { \
244 while (JUMPABLE(rn)) { \
245 const OPCODE type = OP(rn); \
246 if (type == SUSPEND || PL_regkind[type] == CURLY) \
247 rn = NEXTOPER(NEXTOPER(rn)); \
248 else if (type == PLUS) \
250 else if (type == IFMATCH) \
251 rn = (rn->flags == 0) ? NEXTOPER(NEXTOPER(rn)) : rn + ARG(rn); \
252 else rn += NEXT_OFF(rn); \
256 /* These constants are for finding GCB=LV and GCB=LVT in the CLUMP regnode.
257 * These are for the pre-composed Hangul syllables, which are all in a
258 * contiguous block and arranged there in such a way so as to facilitate
259 * alorithmic determination of their characteristics. As such, they don't need
260 * a swash, but can be determined by simple arithmetic. Almost all are
261 * GCB=LVT, but every 28th one is a GCB=LV */
262 #define SBASE 0xAC00 /* Start of block */
263 #define SCount 11172 /* Length of block */
266 #define SLAB_FIRST(s) (&(s)->states[0])
267 #define SLAB_LAST(s) (&(s)->states[PERL_REGMATCH_SLAB_SLOTS-1])
269 static void S_setup_eval_state(pTHX_ regmatch_info *const reginfo);
270 static void S_cleanup_regmatch_info_aux(pTHX_ void *arg);
271 static regmatch_state * S_push_slab(pTHX);
273 #define REGCP_PAREN_ELEMS 3
274 #define REGCP_OTHER_ELEMS 3
275 #define REGCP_FRAME_ELEMS 1
276 /* REGCP_FRAME_ELEMS are not part of the REGCP_OTHER_ELEMS and
277 * are needed for the regexp context stack bookkeeping. */
280 S_regcppush(pTHX_ const regexp *rex, I32 parenfloor, U32 maxopenparen)
283 const int retval = PL_savestack_ix;
284 const int paren_elems_to_push =
285 (maxopenparen - parenfloor) * REGCP_PAREN_ELEMS;
286 const UV total_elems = paren_elems_to_push + REGCP_OTHER_ELEMS;
287 const UV elems_shifted = total_elems << SAVE_TIGHT_SHIFT;
289 GET_RE_DEBUG_FLAGS_DECL;
291 PERL_ARGS_ASSERT_REGCPPUSH;
293 if (paren_elems_to_push < 0)
294 Perl_croak(aTHX_ "panic: paren_elems_to_push, %i < 0",
295 paren_elems_to_push);
297 if ((elems_shifted >> SAVE_TIGHT_SHIFT) != total_elems)
298 Perl_croak(aTHX_ "panic: paren_elems_to_push offset %"UVuf
299 " out of range (%lu-%ld)",
301 (unsigned long)maxopenparen,
304 SSGROW(total_elems + REGCP_FRAME_ELEMS);
307 if ((int)maxopenparen > (int)parenfloor)
308 PerlIO_printf(Perl_debug_log,
309 "rex=0x%"UVxf" offs=0x%"UVxf": saving capture indices:\n",
314 for (p = parenfloor+1; p <= (I32)maxopenparen; p++) {
315 /* REGCP_PARENS_ELEMS are pushed per pairs of parentheses. */
316 SSPUSHIV(rex->offs[p].end);
317 SSPUSHIV(rex->offs[p].start);
318 SSPUSHINT(rex->offs[p].start_tmp);
319 DEBUG_BUFFERS_r(PerlIO_printf(Perl_debug_log,
320 " \\%"UVuf": %"IVdf"(%"IVdf")..%"IVdf"\n",
322 (IV)rex->offs[p].start,
323 (IV)rex->offs[p].start_tmp,
327 /* REGCP_OTHER_ELEMS are pushed in any case, parentheses or no. */
328 SSPUSHINT(maxopenparen);
329 SSPUSHINT(rex->lastparen);
330 SSPUSHINT(rex->lastcloseparen);
331 SSPUSHUV(SAVEt_REGCONTEXT | elems_shifted); /* Magic cookie. */
336 /* These are needed since we do not localize EVAL nodes: */
337 #define REGCP_SET(cp) \
339 PerlIO_printf(Perl_debug_log, \
340 " Setting an EVAL scope, savestack=%"IVdf"\n", \
341 (IV)PL_savestack_ix)); \
344 #define REGCP_UNWIND(cp) \
346 if (cp != PL_savestack_ix) \
347 PerlIO_printf(Perl_debug_log, \
348 " Clearing an EVAL scope, savestack=%"IVdf"..%"IVdf"\n", \
349 (IV)(cp), (IV)PL_savestack_ix)); \
352 #define UNWIND_PAREN(lp, lcp) \
353 for (n = rex->lastparen; n > lp; n--) \
354 rex->offs[n].end = -1; \
355 rex->lastparen = n; \
356 rex->lastcloseparen = lcp;
360 S_regcppop(pTHX_ regexp *rex, U32 *maxopenparen_p)
365 GET_RE_DEBUG_FLAGS_DECL;
367 PERL_ARGS_ASSERT_REGCPPOP;
369 /* Pop REGCP_OTHER_ELEMS before the parentheses loop starts. */
371 assert((i & SAVE_MASK) == SAVEt_REGCONTEXT); /* Check that the magic cookie is there. */
372 i >>= SAVE_TIGHT_SHIFT; /* Parentheses elements to pop. */
373 rex->lastcloseparen = SSPOPINT;
374 rex->lastparen = SSPOPINT;
375 *maxopenparen_p = SSPOPINT;
377 i -= REGCP_OTHER_ELEMS;
378 /* Now restore the parentheses context. */
380 if (i || rex->lastparen + 1 <= rex->nparens)
381 PerlIO_printf(Perl_debug_log,
382 "rex=0x%"UVxf" offs=0x%"UVxf": restoring capture indices to:\n",
387 paren = *maxopenparen_p;
388 for ( ; i > 0; i -= REGCP_PAREN_ELEMS) {
390 rex->offs[paren].start_tmp = SSPOPINT;
391 rex->offs[paren].start = SSPOPIV;
393 if (paren <= rex->lastparen)
394 rex->offs[paren].end = tmps;
395 DEBUG_BUFFERS_r( PerlIO_printf(Perl_debug_log,
396 " \\%"UVuf": %"IVdf"(%"IVdf")..%"IVdf"%s\n",
398 (IV)rex->offs[paren].start,
399 (IV)rex->offs[paren].start_tmp,
400 (IV)rex->offs[paren].end,
401 (paren > rex->lastparen ? "(skipped)" : ""));
406 /* It would seem that the similar code in regtry()
407 * already takes care of this, and in fact it is in
408 * a better location to since this code can #if 0-ed out
409 * but the code in regtry() is needed or otherwise tests
410 * requiring null fields (pat.t#187 and split.t#{13,14}
411 * (as of patchlevel 7877) will fail. Then again,
412 * this code seems to be necessary or otherwise
413 * this erroneously leaves $1 defined: "1" =~ /^(?:(\d)x)?\d$/
414 * --jhi updated by dapm */
415 for (i = rex->lastparen + 1; i <= rex->nparens; i++) {
416 if (i > *maxopenparen_p)
417 rex->offs[i].start = -1;
418 rex->offs[i].end = -1;
419 DEBUG_BUFFERS_r( PerlIO_printf(Perl_debug_log,
420 " \\%"UVuf": %s ..-1 undeffing\n",
422 (i > *maxopenparen_p) ? "-1" : " "
428 /* restore the parens and associated vars at savestack position ix,
429 * but without popping the stack */
432 S_regcp_restore(pTHX_ regexp *rex, I32 ix, U32 *maxopenparen_p)
434 I32 tmpix = PL_savestack_ix;
435 PL_savestack_ix = ix;
436 regcppop(rex, maxopenparen_p);
437 PL_savestack_ix = tmpix;
440 #define regcpblow(cp) LEAVE_SCOPE(cp) /* Ignores regcppush()ed data. */
443 S_isFOO_lc(pTHX_ const U8 classnum, const U8 character)
445 /* Returns a boolean as to whether or not 'character' is a member of the
446 * Posix character class given by 'classnum' that should be equivalent to a
447 * value in the typedef '_char_class_number'.
449 * Ideally this could be replaced by a just an array of function pointers
450 * to the C library functions that implement the macros this calls.
451 * However, to compile, the precise function signatures are required, and
452 * these may vary from platform to to platform. To avoid having to figure
453 * out what those all are on each platform, I (khw) am using this method,
454 * which adds an extra layer of function call overhead (unless the C
455 * optimizer strips it away). But we don't particularly care about
456 * performance with locales anyway. */
458 switch ((_char_class_number) classnum) {
459 case _CC_ENUM_ALPHANUMERIC: return isALPHANUMERIC_LC(character);
460 case _CC_ENUM_ALPHA: return isALPHA_LC(character);
461 case _CC_ENUM_ASCII: return isASCII_LC(character);
462 case _CC_ENUM_BLANK: return isBLANK_LC(character);
463 case _CC_ENUM_CASED: return isLOWER_LC(character)
464 || isUPPER_LC(character);
465 case _CC_ENUM_CNTRL: return isCNTRL_LC(character);
466 case _CC_ENUM_DIGIT: return isDIGIT_LC(character);
467 case _CC_ENUM_GRAPH: return isGRAPH_LC(character);
468 case _CC_ENUM_LOWER: return isLOWER_LC(character);
469 case _CC_ENUM_PRINT: return isPRINT_LC(character);
470 case _CC_ENUM_PSXSPC: return isPSXSPC_LC(character);
471 case _CC_ENUM_PUNCT: return isPUNCT_LC(character);
472 case _CC_ENUM_SPACE: return isSPACE_LC(character);
473 case _CC_ENUM_UPPER: return isUPPER_LC(character);
474 case _CC_ENUM_WORDCHAR: return isWORDCHAR_LC(character);
475 case _CC_ENUM_XDIGIT: return isXDIGIT_LC(character);
476 default: /* VERTSPACE should never occur in locales */
477 Perl_croak(aTHX_ "panic: isFOO_lc() has an unexpected character class '%d'", classnum);
480 assert(0); /* NOTREACHED */
485 S_isFOO_utf8_lc(pTHX_ const U8 classnum, const U8* character)
487 /* Returns a boolean as to whether or not the (well-formed) UTF-8-encoded
488 * 'character' is a member of the Posix character class given by 'classnum'
489 * that should be equivalent to a value in the typedef
490 * '_char_class_number'.
492 * This just calls isFOO_lc on the code point for the character if it is in
493 * the range 0-255. Outside that range, all characters avoid Unicode
494 * rules, ignoring any locale. So use the Unicode function if this class
495 * requires a swash, and use the Unicode macro otherwise. */
497 PERL_ARGS_ASSERT_ISFOO_UTF8_LC;
499 if (UTF8_IS_INVARIANT(*character)) {
500 return isFOO_lc(classnum, *character);
502 else if (UTF8_IS_DOWNGRADEABLE_START(*character)) {
503 return isFOO_lc(classnum,
504 TWO_BYTE_UTF8_TO_NATIVE(*character, *(character + 1)));
507 if (classnum < _FIRST_NON_SWASH_CC) {
509 /* Initialize the swash unless done already */
510 if (! PL_utf8_swash_ptrs[classnum]) {
511 U8 flags = _CORE_SWASH_INIT_ACCEPT_INVLIST;
512 PL_utf8_swash_ptrs[classnum] =
513 _core_swash_init("utf8",
516 PL_XPosix_ptrs[classnum], &flags);
519 return cBOOL(swash_fetch(PL_utf8_swash_ptrs[classnum], (U8 *)
521 TRUE /* is UTF */ ));
524 switch ((_char_class_number) classnum) {
526 case _CC_ENUM_PSXSPC: return is_XPERLSPACE_high(character);
528 case _CC_ENUM_BLANK: return is_HORIZWS_high(character);
529 case _CC_ENUM_XDIGIT: return is_XDIGIT_high(character);
530 case _CC_ENUM_VERTSPACE: return is_VERTWS_high(character);
531 default: return 0; /* Things like CNTRL are always
535 assert(0); /* NOTREACHED */
540 * pregexec and friends
543 #ifndef PERL_IN_XSUB_RE
545 - pregexec - match a regexp against a string
548 Perl_pregexec(pTHX_ REGEXP * const prog, char* stringarg, char *strend,
549 char *strbeg, SSize_t minend, SV *screamer, U32 nosave)
550 /* stringarg: the point in the string at which to begin matching */
551 /* strend: pointer to null at end of string */
552 /* strbeg: real beginning of string */
553 /* minend: end of match must be >= minend bytes after stringarg. */
554 /* screamer: SV being matched: only used for utf8 flag, pos() etc; string
555 * itself is accessed via the pointers above */
556 /* nosave: For optimizations. */
558 PERL_ARGS_ASSERT_PREGEXEC;
561 regexec_flags(prog, stringarg, strend, strbeg, minend, screamer, NULL,
562 nosave ? 0 : REXEC_COPY_STR);
567 * Need to implement the following flags for reg_anch:
569 * USE_INTUIT_NOML - Useful to call re_intuit_start() first
571 * INTUIT_AUTORITATIVE_NOML - Can trust a positive answer
572 * INTUIT_AUTORITATIVE_ML
573 * INTUIT_ONCE_NOML - Intuit can match in one location only.
576 * Another flag for this function: SECOND_TIME (so that float substrs
577 * with giant delta may be not rechecked).
580 /* If SCREAM, then SvPVX_const(sv) should be compatible with strpos and strend.
581 Otherwise, only SvCUR(sv) is used to get strbeg. */
583 /* XXXX Some places assume that there is a fixed substring.
584 An update may be needed if optimizer marks as "INTUITable"
585 RExen without fixed substrings. Similarly, it is assumed that
586 lengths of all the strings are no more than minlen, thus they
587 cannot come from lookahead.
588 (Or minlen should take into account lookahead.)
589 NOTE: Some of this comment is not correct. minlen does now take account
590 of lookahead/behind. Further research is required. -- demerphq
594 /* A failure to find a constant substring means that there is no need to make
595 an expensive call to REx engine, thus we celebrate a failure. Similarly,
596 finding a substring too deep into the string means that fewer calls to
597 regtry() should be needed.
599 REx compiler's optimizer found 4 possible hints:
600 a) Anchored substring;
602 c) Whether we are anchored (beginning-of-line or \G);
603 d) First node (of those at offset 0) which may distinguish positions;
604 We use a)b)d) and multiline-part of c), and try to find a position in the
605 string which does not contradict any of them.
608 /* Most of decisions we do here should have been done at compile time.
609 The nodes of the REx which we used for the search should have been
610 deleted from the finite automaton. */
613 * rx: the regex to match against
614 * sv: the SV being matched: only used for utf8 flag; the string
615 * itself is accessed via the pointers below. Note that on
616 * something like an overloaded SV, SvPOK(sv) may be false
617 * and the string pointers may point to something unrelated to
619 * strbeg: real beginning of string
620 * strpos: the point in the string at which to begin matching
621 * strend: pointer to the byte following the last char of the string
622 * flags currently unused; set to 0
623 * data: currently unused; set to NULL
627 Perl_re_intuit_start(pTHX_
630 const char * const strbeg,
634 re_scream_pos_data *data)
637 struct regexp *const prog = ReANY(rx);
638 SSize_t start_shift = 0;
639 /* Should be nonnegative! */
640 SSize_t end_shift = 0;
642 /* current lowest pos in string where the regex can start matching */
643 char *rx_origin = strpos;
646 const bool utf8_target = (sv && SvUTF8(sv)) ? 1 : 0; /* if no sv we have to assume bytes */
647 U8 other_ix = 1 - prog->substrs->check_ix;
649 char *other_last = NULL; /* latest pos 'other' substr already checked to */
650 char *check_at = NULL; /* check substr found at this pos */
651 char *checked_upto = NULL; /* how far into the string we have already checked using find_byclass*/
652 const I32 multiline = prog->extflags & RXf_PMf_MULTILINE;
653 RXi_GET_DECL(prog,progi);
654 regmatch_info reginfo_buf; /* create some info to pass to find_byclass */
655 regmatch_info *const reginfo = ®info_buf;
657 const char * const i_strpos = strpos;
659 GET_RE_DEBUG_FLAGS_DECL;
661 PERL_ARGS_ASSERT_RE_INTUIT_START;
662 PERL_UNUSED_ARG(flags);
663 PERL_UNUSED_ARG(data);
665 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
666 "Intuit: trying to determine minimum start position...\n"));
668 /* for now, assume that all substr offsets are positive. If at some point
669 * in the future someone wants to do clever things with look-behind and
670 * -ve offsets, they'll need to fix up any code in this function
671 * which uses these offsets. See the thread beginning
672 * <20140113145929.GF27210@iabyn.com>
674 assert(prog->substrs->data[0].min_offset >= 0);
675 assert(prog->substrs->data[0].max_offset >= 0);
676 assert(prog->substrs->data[1].min_offset >= 0);
677 assert(prog->substrs->data[1].max_offset >= 0);
678 assert(prog->substrs->data[2].min_offset >= 0);
679 assert(prog->substrs->data[2].max_offset >= 0);
681 /* CHR_DIST() would be more correct here but it makes things slow. */
682 if (prog->minlen > strend - strpos) {
683 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
684 " String too short...\n"));
688 reginfo->is_utf8_target = cBOOL(utf8_target);
689 reginfo->info_aux = NULL;
690 reginfo->strbeg = strbeg;
691 reginfo->strend = strend;
692 reginfo->is_utf8_pat = cBOOL(RX_UTF8(rx));
694 /* not actually used within intuit, but zero for safety anyway */
695 reginfo->poscache_maxiter = 0;
698 if (!prog->check_utf8 && prog->check_substr)
699 to_utf8_substr(prog);
700 check = prog->check_utf8;
702 if (!prog->check_substr && prog->check_utf8) {
703 if (! to_byte_substr(prog)) {
704 NON_UTF8_TARGET_BUT_UTF8_REQUIRED(fail);
707 check = prog->check_substr;
710 /* dump the various substring data */
711 DEBUG_OPTIMISE_MORE_r({
713 for (i=0; i<=2; i++) {
714 SV *sv = (utf8_target ? prog->substrs->data[i].utf8_substr
715 : prog->substrs->data[i].substr);
719 PerlIO_printf(Perl_debug_log,
720 " substrs[%d]: min=%"IVdf" max=%"IVdf" end shift=%"IVdf
721 " useful=%"IVdf" utf8=%d [%s]\n",
723 (IV)prog->substrs->data[i].min_offset,
724 (IV)prog->substrs->data[i].max_offset,
725 (IV)prog->substrs->data[i].end_shift,
732 if (prog->intflags & PREGf_ANCH) { /* Match at \G, beg-of-str or after \n */
733 /* Check after \n? */
734 ml_anch = ( (prog->intflags & PREGf_ANCH_MBOL)
735 || ((prog->intflags & PREGf_ANCH_BOL) && multiline));
738 /* we are only allowed to match at BOS or \G */
740 /* trivially reject if there's a BOS anchor and we're not at BOS.
741 * In the case of \G, we hope(!) that the caller has already
742 * set strpos to pos()-gofs, and will already have checked
743 * that this anchor position is legal. So we can skip it here.
745 if ( !(prog->intflags & PREGf_ANCH_GPOS)
746 && !(prog->intflags & PREGf_IMPLICIT) /* not a real BOL */
747 && (strpos != strbeg))
749 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
750 " Not at start...\n"));
754 /* in the presence of an anchor, the anchored (relative to the
755 * start of the regex) substr must also be anchored relative
756 * to strpos. So quickly reject if substr isn't found there */
758 if (prog->check_offset_min == prog->check_offset_max
759 && !(prog->intflags & PREGf_CANY_SEEN)
760 && ! multiline) /* /m can cause \n's to match that aren't
761 accounted for in the string max length.
762 See [perl #115242] */
764 /* Substring at constant offset from beg-of-str... */
765 SSize_t slen = SvCUR(check);
767 s = HOP3c(strpos, prog->check_offset_min, strend);
769 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
770 " Looking for check substr at fixed offset %"IVdf"...\n",
771 (IV)prog->check_offset_min));
774 /* In this case, the regex is anchored at the end too,
775 * so the lengths must match exactly, give or take a \n.
776 * NB: slen >= 1 since the last char of check is \n */
777 if ( strend - s > slen || strend - s < slen - 1
778 || (strend - s == slen && strend[-1] != '\n'))
780 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
781 " String too long...\n"));
784 /* Now should match s[0..slen-2] */
787 if (slen && (*SvPVX_const(check) != *s
788 || (slen > 1 && memNE(SvPVX_const(check), s, slen))))
790 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
791 " String not equal...\n"));
796 goto success_at_start;
801 start_shift = prog->check_offset_min; /* okay to underestimate on CC */
802 end_shift = prog->check_end_shift;
804 #ifdef DEBUGGING /* 7/99: reports of failure (with the older version) */
806 Perl_croak(aTHX_ "panic: end_shift: %"IVdf" pattern:\n%s\n ",
807 (IV)end_shift, RX_PRECOMP(prog));
811 /* Find a candidate regex origin in the region rx_origin..strend
812 * by looking for the "check" substring in that region, corrected by
820 DEBUG_OPTIMISE_MORE_r({
821 PerlIO_printf(Perl_debug_log,
822 " At restart: s=%"IVdf" Check offset min: %"IVdf
823 " Start shift: %"IVdf" End shift %"IVdf
824 " Real end Shift: %"IVdf"\n",
825 (IV)(rx_origin - i_strpos),
826 (IV)prog->check_offset_min,
829 (IV)prog->check_end_shift);
832 if (prog->intflags & PREGf_CANY_SEEN) {
833 start_point= (U8*)(rx_origin + start_shift);
834 end_point= (U8*)(strend - end_shift);
836 start_point= HOP3(rx_origin, start_shift, strend);
837 end_point= HOP3(strend, -end_shift, strbeg);
840 /* if the regex is absolutely anchored to the start of the string,
841 * then check_offset_max represents an upper bound on the string
842 * where the substr could start */
844 && prog->intflags & PREGf_ANCH
845 && prog->check_offset_max != SSize_t_MAX
846 && start_shift < prog->check_offset_max)
848 SSize_t off = prog->check_offset_max - start_shift
849 + CHR_SVLEN(check) - !!SvTAIL(check);
850 end_point = HOP3lim(start_point, off, end_point);
853 DEBUG_OPTIMISE_MORE_r({
854 PerlIO_printf(Perl_debug_log, " fbm_instr len=%d str=<%.*s>\n",
855 (int)(end_point - start_point),
856 (int)(end_point - start_point) > 20 ? 20 : (int)(end_point - start_point),
860 s = fbm_instr( start_point, end_point,
861 check, multiline ? FBMrf_MULTILINE : 0);
864 /* Update the count-of-usability, remove useless subpatterns,
868 RE_PV_QUOTED_DECL(quoted, utf8_target, PERL_DEBUG_PAD_ZERO(0),
869 SvPVX_const(check), RE_SV_DUMPLEN(check), 30);
870 PerlIO_printf(Perl_debug_log, " %s %s substr %s%s%s",
871 (s ? "Found" : "Did not find"),
872 (check == (utf8_target ? prog->anchored_utf8 : prog->anchored_substr)
873 ? "anchored" : "floating"),
876 (s ? " at offset " : "...\n") );
881 /* Finish the diagnostic message */
882 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "%ld...\n", (long)(s - i_strpos)) );
884 /* set rx_origin to the minimum position where the regex could start
885 * matching, given the constraint of the just-matched check substring
888 rx_origin = (s - strpos <= prog->check_offset_max)
890 : HOP3c(s, -prog->check_offset_max, strpos);
893 /* XXX dmq: first branch is for positive lookbehind...
894 Our check string is offset from the beginning of the pattern.
895 So we need to do any stclass tests offset forward from that
901 /* Got a candidate. Check MBOL anchoring, and the *other* substr.
902 Start with the other substr.
903 XXXX no SCREAM optimization yet - and a very coarse implementation
904 XXXX /ttx+/ results in anchored="ttx", floating="x". floating will
905 *always* match. Probably should be marked during compile...
906 Probably it is right to do no SCREAM here...
909 if (utf8_target ? prog->substrs->data[other_ix].utf8_substr
910 : prog->substrs->data[other_ix].substr)
912 /* Take into account the "other" substring. */
913 /* XXXX May be hopelessly wrong for UTF... */
918 if (prog->substrs->check_ix) {
920 char * const saved_s = s;
922 struct reg_substr_datum *other = &prog->substrs->data[other_ix];
924 /* we've previously found a floating substr starting at s.
925 * This means that the regex origin must lie somewhere
926 * between min (rx_origin): HOP3(s, -check_offset_max)
927 * and max: HOP3(s, -check_offset_min)
928 * (except that min will be >= strpos)
929 * So the fixed substr must lie somewhere between
930 * HOP3(min, anchored_offset)
931 * HOP3(max, anchored_offset) + SvCUR(substr)
933 assert(strpos + start_shift <= s);
934 last = HOP4c(s, other->min_offset - start_shift,
937 s = HOP3c(rx_origin, other->min_offset, strend);
938 if (s < other_last) /* These positions already checked */
941 assert(prog->minlen > other->min_offset);
942 last1 = HOP3c(strend,
943 other->min_offset - prog->minlen, strbeg);
945 /* On end-of-str: see comment below. */
946 must = utf8_target ? other->utf8_substr : other->substr;
950 HOP3(last + SvCUR(must), -(SvTAIL(must)!=0), strbeg),
952 multiline ? FBMrf_MULTILINE : 0
955 RE_PV_QUOTED_DECL(quoted, utf8_target, PERL_DEBUG_PAD_ZERO(0),
956 SvPVX_const(must), RE_SV_DUMPLEN(must), 30);
957 PerlIO_printf(Perl_debug_log, " %s anchored substr %s%s",
958 (s ? "Found" : "Contradicts"),
959 quoted, RE_SV_TAIL(must));
965 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
966 ", giving up...\n"));
969 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
970 ", trying floating at offset %ld...\n",
971 (long)(HOP3c(saved_s, 1, strend) - i_strpos)));
972 other_last = HOP3c(last, 1, strend);
973 rx_origin = HOP4c(last, 1 - other->min_offset, strbeg, strend);
977 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, " at offset %ld...\n",
978 (long)(s - i_strpos)));
979 rx_origin = HOP3c(s, -other->min_offset, strbeg);
980 other_last = HOP3c(s, 1, strend);
982 if (rx_origin == strpos)
987 else { /* Take into account the floating substring. */
989 char * const saved_s = s;
991 struct reg_substr_datum *other = &prog->substrs->data[other_ix];
993 /* Calculate last1, the absolute latest point where the
994 * floating substr could start in the string, ignoring any
995 * constraints from the earlier fixed match. It is calculated
998 * strend - prog->minlen (in chars) is the absolute latest
999 * position within the string where the origin of the regex
1000 * could appear. The latest start point for the floating
1001 * substr is float_min_offset(*) on from the start of the
1002 * regex. last1 simply combines thee two offsets.
1004 * (*) You might think the latest start point should be
1005 * float_max_offset from the regex origin, and technically
1006 * you'd be correct. However, consider
1008 * Here, float min, max are 3,5 and minlen is 7.
1009 * This can match either
1013 * In the first case, the regex matches minlen chars; in the
1014 * second, minlen+1, in the third, minlen+2.
1015 * In the first case, the floating offset is 3 (which equals
1016 * float_min), in the second, 4, and in the third, 5 (which
1017 * equals float_max). In all cases, the floating string bcd
1018 * can never start more than 4 chars from the end of the
1019 * string, which equals minlen - float_min. As the substring
1020 * starts to match more than float_min from the start of the
1021 * regex, it makes the regex match more than minlen chars,
1022 * and the two cancel each other out. So we can always use
1023 * float_min - minlen, rather than float_max - minlen for the
1024 * latest position in the string.
1026 * Note that -minlen + float_min_offset is equivalent (AFAIKT)
1027 * to CHR_SVLEN(must) - !!SvTAIL(must) + prog->float_end_shift
1030 HOP3c(strend, other->min_offset - prog->minlen, strbeg);
1032 /* last is the latest point where the floating substr could
1033 * start, *given* any constraints from the earlier fixed
1034 * match. This constraint is that the floating string starts
1035 * <= float_max_offset chars from the regex origin (rx_origin).
1036 * If this value is less than last1, use it instead.
1038 assert(rx_origin <= last1);
1040 /* this condition handles the offset==infinity case, and
1041 * is a short-cut otherwise. Although it's comparing a
1042 * byte offset to a char length, it does so in a safe way,
1043 * since 1 char always occupies 1 or more bytes,
1044 * so if a string range is (last1 - rx_origin) bytes,
1045 * it will be less than or equal to (last1 - rx_origin)
1046 * chars; meaning it errs towards doing the accurate HOP3
1047 * rather than just using last1 as a short-cut */
1048 (last1 - rx_origin) < other->max_offset
1050 : (char*)HOP3lim(rx_origin, other->max_offset, last1);
1052 /* set s to the earliest position the float string can start */
1053 s = HOP3c(rx_origin, other->min_offset, strend);
1054 if (s < other_last) /* skip previous failures */
1057 must = utf8_target ? other->utf8_substr : other->substr;
1058 assert(SvPOK(must));
1059 /* fbm_instr() takes into account exact value of end-of-str
1060 if the check is SvTAIL(ed). Since false positives are OK,
1061 and end-of-str is not later than strend we are OK. */
1062 s = fbm_instr((unsigned char*)s,
1063 (unsigned char*)last + SvCUR(must)
1064 - (SvTAIL(must)!=0),
1065 must, multiline ? FBMrf_MULTILINE : 0);
1067 RE_PV_QUOTED_DECL(quoted, utf8_target, PERL_DEBUG_PAD_ZERO(0),
1068 SvPVX_const(must), RE_SV_DUMPLEN(must), 30);
1069 PerlIO_printf(Perl_debug_log, " %s floating substr %s%s",
1070 (s ? "Found" : "Contradicts"),
1071 quoted, RE_SV_TAIL(must));
1075 /* last1 is latest possible float location. If we didn't
1076 * find it before there, we never will */
1077 if (last == last1) {
1078 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
1079 ", giving up...\n"));
1083 /* try to find the anchored substr again at a later
1084 * position. Maybe next time we'll find a float in range
1086 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
1087 ", trying anchored starting at offset %ld...\n",
1088 (long)(saved_s + 1 - i_strpos)));
1089 other_last = HOP3c(last, 1, strend); /* highest failure */
1090 rx_origin = HOP3c(rx_origin, 1, strend);
1094 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, " at offset %ld...\n",
1095 (long)(s - i_strpos)));
1097 /* other_last is set to s, not s+1, since its possible for
1098 * a floating substr to fail first time, then succeed
1099 * second time at the same floating position; e.g.:
1100 * "-AB--AABZ" =~ /\wAB\d*Z/
1101 * The first time round, anchored and float match at
1102 * "-(AB)--AAB(Z)" then fail on the initial \w character
1103 * class. Second time round, they match at "-AB--A(AB)(Z)".
1107 if (rx_origin == strpos)
1115 DEBUG_OPTIMISE_MORE_r(
1116 PerlIO_printf(Perl_debug_log,
1117 " Check-only match: offset min:%"IVdf" max:%"IVdf
1118 " s:%"IVdf" rx_origin:%"IVdf" rx_origin-s:%"IVdf
1119 " strend-strpos:%"IVdf"\n",
1120 (IV)prog->check_offset_min,
1121 (IV)prog->check_offset_max,
1123 (IV)(rx_origin-strpos),
1129 /* signed-corrected rx_origin > strpos */
1130 if (s - strpos > prog->check_offset_max
1132 || ((rx_origin = (char*)reghopmaybe3((U8*)s,
1133 -prog->check_offset_max, (U8*) strpos))
1134 && rx_origin > strpos)))
1136 /* Fixed substring is found far enough so that the match
1137 cannot start at strpos. */
1139 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, " try at offset...\n"));
1140 if (ml_anch && rx_origin[-1] != '\n') {
1141 /* Eventually fbm_*() should handle this, but often
1142 anchored_offset is not 0, so this check will not be wasted. */
1143 /* XXXX In the code below we prefer to look for "^" even in
1144 presence of anchored substrings. And we search even
1145 beyond the found float position. These pessimizations
1146 are historical artefacts only. */
1149 while (t < strend - prog->minlen) {
1151 if (t < check_at - prog->check_offset_min) {
1152 if (utf8_target ? prog->anchored_utf8 : prog->anchored_substr) {
1153 /* Since we moved from the found position,
1154 we definitely contradict the found anchored
1155 substr. Due to the above check we do not
1156 contradict "check" substr.
1157 Thus we can arrive here only if check substr
1158 is float. Redo checking for "other"=="fixed".
1160 rx_origin = strpos = t + 1;
1161 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, " Found /%s^%s/m at offset %ld, rescanning for anchored from offset %ld...\n",
1162 PL_colors[0], PL_colors[1], (long)(strpos - i_strpos), (long)(strpos - i_strpos + prog->anchored_offset)));
1163 assert(prog->substrs->check_ix); /* other is float */
1164 goto do_other_substr;
1166 /* We don't contradict the found floating substring. */
1167 /* XXXX Why not check for STCLASS? */
1169 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, " Found /%s^%s/m at offset %ld...\n",
1170 PL_colors[0], PL_colors[1], (long)(s - i_strpos)));
1173 /* Position contradicts check-string */
1174 /* XXXX probably better to look for check-string
1175 than for "\n", so one should lower the limit for t? */
1176 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, " Found /%s^%s/m, restarting lookup for check-string at offset %ld...\n",
1177 PL_colors[0], PL_colors[1], (long)(t + 1 - i_strpos)));
1178 other_last = strpos = rx_origin = t + 1;
1183 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, " Did not find /%s^%s/m...\n",
1184 PL_colors[0], PL_colors[1]));
1188 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, " Starting position does not contradict /%s^%s/m...\n",
1189 PL_colors[0], PL_colors[1]));
1193 ++BmUSEFUL(utf8_target ? prog->check_utf8 : prog->check_substr); /* hooray/5 */
1196 /* The found string does not prohibit matching at strpos,
1197 - no optimization of calling REx engine can be performed,
1198 unless it was an MBOL and we are not after MBOL,
1199 or a future STCLASS check will fail this. */
1201 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, " try at start...\n"));
1202 /* Even in this situation we may use MBOL flag if strpos is offset
1203 wrt the start of the string. */
1204 if (ml_anch && (strpos != strbeg) && strpos[-1] != '\n'
1205 /* May be due to an implicit anchor of m{.*foo} */
1206 && !(prog->intflags & PREGf_IMPLICIT))
1211 DEBUG_EXECUTE_r( if (ml_anch)
1212 PerlIO_printf(Perl_debug_log, " Position at offset %ld does not contradict /%s^%s/m...\n",
1213 (long)(strpos - i_strpos), PL_colors[0], PL_colors[1]);
1216 if (!(prog->intflags & PREGf_NAUGHTY) /* XXXX If strpos moved? */
1218 prog->check_utf8 /* Could be deleted already */
1219 && --BmUSEFUL(prog->check_utf8) < 0
1220 && (prog->check_utf8 == prog->float_utf8)
1222 prog->check_substr /* Could be deleted already */
1223 && --BmUSEFUL(prog->check_substr) < 0
1224 && (prog->check_substr == prog->float_substr)
1227 /* If flags & SOMETHING - do not do it many times on the same match */
1228 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, " ... Disabling check substring...\n"));
1229 /* XXX Does the destruction order has to change with utf8_target? */
1230 SvREFCNT_dec(utf8_target ? prog->check_utf8 : prog->check_substr);
1231 SvREFCNT_dec(utf8_target ? prog->check_substr : prog->check_utf8);
1232 prog->check_substr = prog->check_utf8 = NULL; /* disable */
1233 prog->float_substr = prog->float_utf8 = NULL; /* clear */
1234 check = NULL; /* abort */
1236 /* XXXX If the check string was an implicit check MBOL, then we need to unset the relevant flag
1237 see http://bugs.activestate.com/show_bug.cgi?id=87173 */
1238 if (prog->intflags & PREGf_IMPLICIT) {
1239 prog->intflags &= ~PREGf_ANCH_MBOL;
1240 /* maybe we have no anchors left after this... */
1241 if (!(prog->intflags & PREGf_ANCH))
1242 prog->extflags &= ~RXf_IS_ANCHORED;
1244 /* XXXX This is a remnant of the old implementation. It
1245 looks wasteful, since now INTUIT can use many
1246 other heuristics. */
1247 prog->extflags &= ~RXf_USE_INTUIT;
1248 /* XXXX What other flags might need to be cleared in this branch? */
1254 /* Last resort... */
1255 /* XXXX BmUSEFUL already changed, maybe multiple change is meaningful... */
1256 /* trie stclasses are too expensive to use here, we are better off to
1257 leave it to regmatch itself */
1258 if (progi->regstclass && PL_regkind[OP(progi->regstclass)]!=TRIE) {
1259 /* minlen == 0 is possible if regstclass is \b or \B,
1260 and the fixed substr is ''$.
1261 Since minlen is already taken into account, s+1 is before strend;
1262 accidentally, minlen >= 1 guaranties no false positives at s + 1
1263 even for \b or \B. But (minlen? 1 : 0) below assumes that
1264 regstclass does not come from lookahead... */
1265 /* If regstclass takes bytelength more than 1: If charlength==1, OK.
1266 This leaves EXACTF-ish only, which are dealt with in find_byclass(). */
1267 const U8* const str = (U8*)STRING(progi->regstclass);
1268 /* XXX this value could be pre-computed */
1269 const int cl_l = (PL_regkind[OP(progi->regstclass)] == EXACT
1270 ? (reginfo->is_utf8_pat
1271 ? utf8_distance(str + STR_LEN(progi->regstclass), str)
1272 : STR_LEN(progi->regstclass))
1275 if (prog->anchored_substr || prog->anchored_utf8 || ml_anch)
1276 endpos= HOP3c(s, (prog->minlen ? cl_l : 0), strend);
1277 else if (prog->float_substr || prog->float_utf8)
1278 endpos= HOP3c(HOP3c(check_at, -start_shift, strbeg), cl_l, strend);
1282 if (checked_upto < s)
1284 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
1285 " looking for class: start_shift: %"IVdf" check_at: %"IVdf
1286 " s: %"IVdf" endpos: %"IVdf" checked_upto: %"IVdf"\n",
1287 (IV)start_shift, (IV)(check_at - strbeg),
1288 (IV)(s - strbeg), (IV)(endpos - strbeg),
1289 (IV)(checked_upto- strbeg)));
1292 s = find_byclass(prog, progi->regstclass, checked_upto, endpos,
1298 const char *what = NULL;
1300 if (endpos == strend) {
1301 DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log,
1302 " Could not match STCLASS...\n") );
1305 DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log,
1306 " This position contradicts STCLASS...\n") );
1307 if ((prog->intflags & PREGf_ANCH) && !ml_anch)
1309 checked_upto = HOPBACKc(endpos, start_shift);
1310 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, " start_shift: %"IVdf" check_at: %"IVdf" endpos: %"IVdf" checked_upto: %"IVdf"\n",
1311 (IV)start_shift, (IV)(check_at - strbeg), (IV)(endpos - strbeg), (IV)(checked_upto- strbeg)));
1312 /* Contradict one of substrings */
1313 if (prog->anchored_substr || prog->anchored_utf8) {
1314 if ((utf8_target ? prog->anchored_utf8 : prog->anchored_substr) == check) {
1315 DEBUG_EXECUTE_r( what = "anchored" );
1317 s = HOP3c(t, 1, strend);
1318 if (s + start_shift + end_shift > strend) {
1319 /* XXXX Should be taken into account earlier? */
1320 DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log,
1321 " Could not match STCLASS...\n") );
1327 DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log,
1328 " Looking for %s substr starting at offset %ld...\n",
1329 what, (long)(rx_origin + start_shift - i_strpos)) );
1332 /* Have both, check_string is floating */
1333 if (t + start_shift >= check_at) /* Contradicts floating=check */
1334 goto retry_floating_check;
1335 /* Recheck anchored substring, but not floating... */
1339 DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log,
1340 " Looking for anchored substr starting at offset %ld...\n",
1341 (long)(other_last - i_strpos)) );
1342 assert(prog->substrs->check_ix); /* other is float */
1343 goto do_other_substr;
1345 /* Another way we could have checked stclass at the
1346 current position only: */
1348 s = rx_origin = t + 1;
1351 DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log,
1352 " Looking for /%s^%s/m starting at offset %ld...\n",
1353 PL_colors[0], PL_colors[1],
1354 (long)(rx_origin - i_strpos)) );
1357 if (!(utf8_target ? prog->float_utf8 : prog->float_substr)) /* Could have been deleted */
1359 /* Check is floating substring. */
1360 retry_floating_check:
1361 t = check_at - start_shift;
1362 DEBUG_EXECUTE_r( what = "floating" );
1363 goto hop_and_restart;
1366 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
1367 " By STCLASS: moving %ld --> %ld\n",
1368 (long)(t - i_strpos), (long)(s - i_strpos))
1372 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
1373 " Does not contradict STCLASS...\n");
1378 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "Intuit: %s%s:%s match at offset %ld\n",
1379 PL_colors[4], (check ? "Successfully guessed" : "Giving up"),
1380 PL_colors[5], (long)(s - i_strpos)) );
1383 fail_finish: /* Substring not found */
1384 if (prog->check_substr || prog->check_utf8) /* could be removed already */
1385 BmUSEFUL(utf8_target ? prog->check_utf8 : prog->check_substr) += 5; /* hooray */
1387 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "%sMatch rejected by optimizer%s\n",
1388 PL_colors[4], PL_colors[5]));
1392 #define DECL_TRIE_TYPE(scan) \
1393 const enum { trie_plain, trie_utf8, trie_utf8_fold, trie_latin_utf8_fold, \
1394 trie_utf8_exactfa_fold, trie_latin_utf8_exactfa_fold } \
1395 trie_type = ((scan->flags == EXACT) \
1396 ? (utf8_target ? trie_utf8 : trie_plain) \
1397 : (scan->flags == EXACTFA) \
1398 ? (utf8_target ? trie_utf8_exactfa_fold : trie_latin_utf8_exactfa_fold) \
1399 : (utf8_target ? trie_utf8_fold : trie_latin_utf8_fold))
1401 #define REXEC_TRIE_READ_CHAR(trie_type, trie, widecharmap, uc, uscan, len, uvc, charid, foldlen, foldbuf, uniflags) \
1404 U8 flags = FOLD_FLAGS_FULL; \
1405 switch (trie_type) { \
1406 case trie_utf8_exactfa_fold: \
1407 flags |= FOLD_FLAGS_NOMIX_ASCII; \
1408 /* FALL THROUGH */ \
1409 case trie_utf8_fold: \
1410 if ( foldlen>0 ) { \
1411 uvc = utf8n_to_uvchr( (const U8*) uscan, UTF8_MAXLEN, &len, uniflags ); \
1416 uvc = _to_utf8_fold_flags( (const U8*) uc, foldbuf, &foldlen, flags); \
1417 len = UTF8SKIP(uc); \
1418 skiplen = UNISKIP( uvc ); \
1419 foldlen -= skiplen; \
1420 uscan = foldbuf + skiplen; \
1423 case trie_latin_utf8_exactfa_fold: \
1424 flags |= FOLD_FLAGS_NOMIX_ASCII; \
1425 /* FALL THROUGH */ \
1426 case trie_latin_utf8_fold: \
1427 if ( foldlen>0 ) { \
1428 uvc = utf8n_to_uvchr( (const U8*) uscan, UTF8_MAXLEN, &len, uniflags ); \
1434 uvc = _to_fold_latin1( (U8) *uc, foldbuf, &foldlen, flags); \
1435 skiplen = UNISKIP( uvc ); \
1436 foldlen -= skiplen; \
1437 uscan = foldbuf + skiplen; \
1441 uvc = utf8n_to_uvchr( (const U8*) uc, UTF8_MAXLEN, &len, uniflags ); \
1448 charid = trie->charmap[ uvc ]; \
1452 if (widecharmap) { \
1453 SV** const svpp = hv_fetch(widecharmap, \
1454 (char*)&uvc, sizeof(UV), 0); \
1456 charid = (U16)SvIV(*svpp); \
1461 #define REXEC_FBC_EXACTISH_SCAN(CoNd) \
1465 && (ln == 1 || folder(s, pat_string, ln)) \
1466 && (reginfo->intuit || regtry(reginfo, &s)) )\
1472 #define REXEC_FBC_UTF8_SCAN(CoDe) \
1474 while (s < strend) { \
1480 #define REXEC_FBC_SCAN(CoDe) \
1482 while (s < strend) { \
1488 #define REXEC_FBC_UTF8_CLASS_SCAN(CoNd) \
1489 REXEC_FBC_UTF8_SCAN( \
1491 if (tmp && (reginfo->intuit || regtry(reginfo, &s))) \
1500 #define REXEC_FBC_CLASS_SCAN(CoNd) \
1503 if (tmp && (reginfo->intuit || regtry(reginfo, &s))) \
1512 #define REXEC_FBC_TRYIT \
1513 if ((reginfo->intuit || regtry(reginfo, &s))) \
1516 #define REXEC_FBC_CSCAN(CoNdUtF8,CoNd) \
1517 if (utf8_target) { \
1518 REXEC_FBC_UTF8_CLASS_SCAN(CoNdUtF8); \
1521 REXEC_FBC_CLASS_SCAN(CoNd); \
1524 #define DUMP_EXEC_POS(li,s,doutf8) \
1525 dump_exec_pos(li,s,(reginfo->strend),(reginfo->strbeg), \
1529 #define UTF8_NOLOAD(TEST_NON_UTF8, IF_SUCCESS, IF_FAIL) \
1530 tmp = (s != reginfo->strbeg) ? UCHARAT(s - 1) : '\n'; \
1531 tmp = TEST_NON_UTF8(tmp); \
1532 REXEC_FBC_UTF8_SCAN( \
1533 if (tmp == ! TEST_NON_UTF8((U8) *s)) { \
1542 #define UTF8_LOAD(TeSt1_UtF8, TeSt2_UtF8, IF_SUCCESS, IF_FAIL) \
1543 if (s == reginfo->strbeg) { \
1547 U8 * const r = reghop3((U8*)s, -1, (U8*)reginfo->strbeg); \
1548 tmp = utf8n_to_uvchr(r, (U8*) reginfo->strend - r, \
1549 0, UTF8_ALLOW_DEFAULT); \
1552 LOAD_UTF8_CHARCLASS_ALNUM(); \
1553 REXEC_FBC_UTF8_SCAN( \
1554 if (tmp == ! (TeSt2_UtF8)) { \
1563 /* The only difference between the BOUND and NBOUND cases is that
1564 * REXEC_FBC_TRYIT is called when matched in BOUND, and when non-matched in
1565 * NBOUND. This is accomplished by passing it in either the if or else clause,
1566 * with the other one being empty */
1567 #define FBC_BOUND(TEST_NON_UTF8, TEST1_UTF8, TEST2_UTF8) \
1568 FBC_BOUND_COMMON(UTF8_LOAD(TEST1_UTF8, TEST2_UTF8, REXEC_FBC_TRYIT, PLACEHOLDER), TEST_NON_UTF8, REXEC_FBC_TRYIT, PLACEHOLDER)
1570 #define FBC_BOUND_NOLOAD(TEST_NON_UTF8, TEST1_UTF8, TEST2_UTF8) \
1571 FBC_BOUND_COMMON(UTF8_NOLOAD(TEST_NON_UTF8, REXEC_FBC_TRYIT, PLACEHOLDER), TEST_NON_UTF8, REXEC_FBC_TRYIT, PLACEHOLDER)
1573 #define FBC_NBOUND(TEST_NON_UTF8, TEST1_UTF8, TEST2_UTF8) \
1574 FBC_BOUND_COMMON(UTF8_LOAD(TEST1_UTF8, TEST2_UTF8, PLACEHOLDER, REXEC_FBC_TRYIT), TEST_NON_UTF8, PLACEHOLDER, REXEC_FBC_TRYIT)
1576 #define FBC_NBOUND_NOLOAD(TEST_NON_UTF8, TEST1_UTF8, TEST2_UTF8) \
1577 FBC_BOUND_COMMON(UTF8_NOLOAD(TEST_NON_UTF8, PLACEHOLDER, REXEC_FBC_TRYIT), TEST_NON_UTF8, PLACEHOLDER, REXEC_FBC_TRYIT)
1580 /* Common to the BOUND and NBOUND cases. Unfortunately the UTF8 tests need to
1581 * be passed in completely with the variable name being tested, which isn't
1582 * such a clean interface, but this is easier to read than it was before. We
1583 * are looking for the boundary (or non-boundary between a word and non-word
1584 * character. The utf8 and non-utf8 cases have the same logic, but the details
1585 * must be different. Find the "wordness" of the character just prior to this
1586 * one, and compare it with the wordness of this one. If they differ, we have
1587 * a boundary. At the beginning of the string, pretend that the previous
1588 * character was a new-line */
1589 #define FBC_BOUND_COMMON(UTF8_CODE, TEST_NON_UTF8, IF_SUCCESS, IF_FAIL) \
1590 if (utf8_target) { \
1593 else { /* Not utf8 */ \
1594 tmp = (s != reginfo->strbeg) ? UCHARAT(s - 1) : '\n'; \
1595 tmp = TEST_NON_UTF8(tmp); \
1597 if (tmp == ! TEST_NON_UTF8((U8) *s)) { \
1606 if ((!prog->minlen && tmp) && (reginfo->intuit || regtry(reginfo, &s))) \
1609 /* We know what class REx starts with. Try to find this position... */
1610 /* if reginfo->intuit, its a dryrun */
1611 /* annoyingly all the vars in this routine have different names from their counterparts
1612 in regmatch. /grrr */
1615 S_find_byclass(pTHX_ regexp * prog, const regnode *c, char *s,
1616 const char *strend, regmatch_info *reginfo)
1619 const I32 doevery = (prog->intflags & PREGf_SKIP) == 0;
1620 char *pat_string; /* The pattern's exactish string */
1621 char *pat_end; /* ptr to end char of pat_string */
1622 re_fold_t folder; /* Function for computing non-utf8 folds */
1623 const U8 *fold_array; /* array for folding ords < 256 */
1629 I32 tmp = 1; /* Scratch variable? */
1630 const bool utf8_target = reginfo->is_utf8_target;
1631 UV utf8_fold_flags = 0;
1632 const bool is_utf8_pat = reginfo->is_utf8_pat;
1633 bool to_complement = FALSE; /* Invert the result? Taking the xor of this
1634 with a result inverts that result, as 0^1 =
1636 _char_class_number classnum;
1638 RXi_GET_DECL(prog,progi);
1640 PERL_ARGS_ASSERT_FIND_BYCLASS;
1642 /* We know what class it must start with. */
1646 REXEC_FBC_UTF8_CLASS_SCAN(
1647 reginclass(prog, c, (U8*)s, (U8*) strend, utf8_target));
1650 REXEC_FBC_CLASS_SCAN(REGINCLASS(prog, c, (U8*)s));
1655 if (tmp && (reginfo->intuit || regtry(reginfo, &s)))
1662 case EXACTFA_NO_TRIE: /* This node only generated for non-utf8 patterns */
1663 assert(! is_utf8_pat);
1666 if (is_utf8_pat || utf8_target) {
1667 utf8_fold_flags = FOLDEQ_UTF8_NOMIX_ASCII;
1668 goto do_exactf_utf8;
1670 fold_array = PL_fold_latin1; /* Latin1 folds are not affected by */
1671 folder = foldEQ_latin1; /* /a, except the sharp s one which */
1672 goto do_exactf_non_utf8; /* isn't dealt with by these */
1674 case EXACTF: /* This node only generated for non-utf8 patterns */
1675 assert(! is_utf8_pat);
1677 utf8_fold_flags = 0;
1678 goto do_exactf_utf8;
1680 fold_array = PL_fold;
1682 goto do_exactf_non_utf8;
1685 if (is_utf8_pat || utf8_target || IN_UTF8_CTYPE_LOCALE) {
1686 utf8_fold_flags = FOLDEQ_LOCALE;
1687 goto do_exactf_utf8;
1689 fold_array = PL_fold_locale;
1690 folder = foldEQ_locale;
1691 goto do_exactf_non_utf8;
1695 utf8_fold_flags = FOLDEQ_S2_ALREADY_FOLDED;
1697 goto do_exactf_utf8;
1700 if (is_utf8_pat || utf8_target) {
1701 utf8_fold_flags = is_utf8_pat ? FOLDEQ_S2_ALREADY_FOLDED : 0;
1702 goto do_exactf_utf8;
1705 /* Any 'ss' in the pattern should have been replaced by regcomp,
1706 * so we don't have to worry here about this single special case
1707 * in the Latin1 range */
1708 fold_array = PL_fold_latin1;
1709 folder = foldEQ_latin1;
1713 do_exactf_non_utf8: /* Neither pattern nor string are UTF8, and there
1714 are no glitches with fold-length differences
1715 between the target string and pattern */
1717 /* The idea in the non-utf8 EXACTF* cases is to first find the
1718 * first character of the EXACTF* node and then, if necessary,
1719 * case-insensitively compare the full text of the node. c1 is the
1720 * first character. c2 is its fold. This logic will not work for
1721 * Unicode semantics and the german sharp ss, which hence should
1722 * not be compiled into a node that gets here. */
1723 pat_string = STRING(c);
1724 ln = STR_LEN(c); /* length to match in octets/bytes */
1726 /* We know that we have to match at least 'ln' bytes (which is the
1727 * same as characters, since not utf8). If we have to match 3
1728 * characters, and there are only 2 availabe, we know without
1729 * trying that it will fail; so don't start a match past the
1730 * required minimum number from the far end */
1731 e = HOP3c(strend, -((SSize_t)ln), s);
1733 if (reginfo->intuit && e < s) {
1734 e = s; /* Due to minlen logic of intuit() */
1738 c2 = fold_array[c1];
1739 if (c1 == c2) { /* If char and fold are the same */
1740 REXEC_FBC_EXACTISH_SCAN(*(U8*)s == c1);
1743 REXEC_FBC_EXACTISH_SCAN(*(U8*)s == c1 || *(U8*)s == c2);
1751 /* If one of the operands is in utf8, we can't use the simpler folding
1752 * above, due to the fact that many different characters can have the
1753 * same fold, or portion of a fold, or different- length fold */
1754 pat_string = STRING(c);
1755 ln = STR_LEN(c); /* length to match in octets/bytes */
1756 pat_end = pat_string + ln;
1757 lnc = is_utf8_pat /* length to match in characters */
1758 ? utf8_length((U8 *) pat_string, (U8 *) pat_end)
1761 /* We have 'lnc' characters to match in the pattern, but because of
1762 * multi-character folding, each character in the target can match
1763 * up to 3 characters (Unicode guarantees it will never exceed
1764 * this) if it is utf8-encoded; and up to 2 if not (based on the
1765 * fact that the Latin 1 folds are already determined, and the
1766 * only multi-char fold in that range is the sharp-s folding to
1767 * 'ss'. Thus, a pattern character can match as little as 1/3 of a
1768 * string character. Adjust lnc accordingly, rounding up, so that
1769 * if we need to match at least 4+1/3 chars, that really is 5. */
1770 expansion = (utf8_target) ? UTF8_MAX_FOLD_CHAR_EXPAND : 2;
1771 lnc = (lnc + expansion - 1) / expansion;
1773 /* As in the non-UTF8 case, if we have to match 3 characters, and
1774 * only 2 are left, it's guaranteed to fail, so don't start a
1775 * match that would require us to go beyond the end of the string
1777 e = HOP3c(strend, -((SSize_t)lnc), s);
1779 if (reginfo->intuit && e < s) {
1780 e = s; /* Due to minlen logic of intuit() */
1783 /* XXX Note that we could recalculate e to stop the loop earlier,
1784 * as the worst case expansion above will rarely be met, and as we
1785 * go along we would usually find that e moves further to the left.
1786 * This would happen only after we reached the point in the loop
1787 * where if there were no expansion we should fail. Unclear if
1788 * worth the expense */
1791 char *my_strend= (char *)strend;
1792 if (foldEQ_utf8_flags(s, &my_strend, 0, utf8_target,
1793 pat_string, NULL, ln, is_utf8_pat, utf8_fold_flags)
1794 && (reginfo->intuit || regtry(reginfo, &s)) )
1798 s += (utf8_target) ? UTF8SKIP(s) : 1;
1803 RXp_MATCH_TAINTED_on(prog);
1804 FBC_BOUND(isWORDCHAR_LC,
1805 isWORDCHAR_LC_uvchr(tmp),
1806 isWORDCHAR_LC_utf8((U8*)s));
1809 RXp_MATCH_TAINTED_on(prog);
1810 FBC_NBOUND(isWORDCHAR_LC,
1811 isWORDCHAR_LC_uvchr(tmp),
1812 isWORDCHAR_LC_utf8((U8*)s));
1815 FBC_BOUND(isWORDCHAR,
1816 isWORDCHAR_uni(tmp),
1817 cBOOL(swash_fetch(PL_utf8_swash_ptrs[_CC_WORDCHAR], (U8*)s, utf8_target)));
1820 FBC_BOUND_NOLOAD(isWORDCHAR_A,
1822 isWORDCHAR_A((U8*)s));
1825 FBC_NBOUND(isWORDCHAR,
1826 isWORDCHAR_uni(tmp),
1827 cBOOL(swash_fetch(PL_utf8_swash_ptrs[_CC_WORDCHAR], (U8*)s, utf8_target)));
1830 FBC_NBOUND_NOLOAD(isWORDCHAR_A,
1832 isWORDCHAR_A((U8*)s));
1835 FBC_BOUND(isWORDCHAR_L1,
1836 isWORDCHAR_uni(tmp),
1837 cBOOL(swash_fetch(PL_utf8_swash_ptrs[_CC_WORDCHAR], (U8*)s, utf8_target)));
1840 FBC_NBOUND(isWORDCHAR_L1,
1841 isWORDCHAR_uni(tmp),
1842 cBOOL(swash_fetch(PL_utf8_swash_ptrs[_CC_WORDCHAR], (U8*)s, utf8_target)));
1845 REXEC_FBC_CSCAN(is_LNBREAK_utf8_safe(s, strend),
1846 is_LNBREAK_latin1_safe(s, strend)
1850 /* The argument to all the POSIX node types is the class number to pass to
1851 * _generic_isCC() to build a mask for searching in PL_charclass[] */
1858 RXp_MATCH_TAINTED_on(prog);
1859 REXEC_FBC_CSCAN(to_complement ^ cBOOL(isFOO_utf8_lc(FLAGS(c), (U8 *) s)),
1860 to_complement ^ cBOOL(isFOO_lc(FLAGS(c), *s)));
1875 /* The complement of something that matches only ASCII matches all
1876 * UTF-8 variant code points, plus everything in ASCII that isn't
1878 REXEC_FBC_UTF8_CLASS_SCAN(! UTF8_IS_INVARIANT(*s)
1879 || ! _generic_isCC_A(*s, FLAGS(c)));
1888 /* Don't need to worry about utf8, as it can match only a single
1889 * byte invariant character. */
1890 REXEC_FBC_CLASS_SCAN(
1891 to_complement ^ cBOOL(_generic_isCC_A(*s, FLAGS(c))));
1899 if (! utf8_target) {
1900 REXEC_FBC_CLASS_SCAN(to_complement ^ cBOOL(_generic_isCC(*s,
1906 classnum = (_char_class_number) FLAGS(c);
1907 if (classnum < _FIRST_NON_SWASH_CC) {
1908 while (s < strend) {
1910 /* We avoid loading in the swash as long as possible, but
1911 * should we have to, we jump to a separate loop. This
1912 * extra 'if' statement is what keeps this code from being
1913 * just a call to REXEC_FBC_UTF8_CLASS_SCAN() */
1914 if (UTF8_IS_ABOVE_LATIN1(*s)) {
1915 goto found_above_latin1;
1917 if ((UTF8_IS_INVARIANT(*s)
1918 && to_complement ^ cBOOL(_generic_isCC((U8) *s,
1920 || (UTF8_IS_DOWNGRADEABLE_START(*s)
1921 && to_complement ^ cBOOL(
1922 _generic_isCC(TWO_BYTE_UTF8_TO_NATIVE(*s,
1926 if (tmp && (reginfo->intuit || regtry(reginfo, &s)))
1938 else switch (classnum) { /* These classes are implemented as
1940 case _CC_ENUM_SPACE: /* XXX would require separate code if we
1941 revert the change of \v matching this */
1944 case _CC_ENUM_PSXSPC:
1945 REXEC_FBC_UTF8_CLASS_SCAN(
1946 to_complement ^ cBOOL(isSPACE_utf8(s)));
1949 case _CC_ENUM_BLANK:
1950 REXEC_FBC_UTF8_CLASS_SCAN(
1951 to_complement ^ cBOOL(isBLANK_utf8(s)));
1954 case _CC_ENUM_XDIGIT:
1955 REXEC_FBC_UTF8_CLASS_SCAN(
1956 to_complement ^ cBOOL(isXDIGIT_utf8(s)));
1959 case _CC_ENUM_VERTSPACE:
1960 REXEC_FBC_UTF8_CLASS_SCAN(
1961 to_complement ^ cBOOL(isVERTWS_utf8(s)));
1964 case _CC_ENUM_CNTRL:
1965 REXEC_FBC_UTF8_CLASS_SCAN(
1966 to_complement ^ cBOOL(isCNTRL_utf8(s)));
1970 Perl_croak(aTHX_ "panic: find_byclass() node %d='%s' has an unexpected character class '%d'", OP(c), PL_reg_name[OP(c)], classnum);
1971 assert(0); /* NOTREACHED */
1976 found_above_latin1: /* Here we have to load a swash to get the result
1977 for the current code point */
1978 if (! PL_utf8_swash_ptrs[classnum]) {
1979 U8 flags = _CORE_SWASH_INIT_ACCEPT_INVLIST;
1980 PL_utf8_swash_ptrs[classnum] =
1981 _core_swash_init("utf8",
1984 PL_XPosix_ptrs[classnum], &flags);
1987 /* This is a copy of the loop above for swash classes, though using the
1988 * FBC macro instead of being expanded out. Since we've loaded the
1989 * swash, we don't have to check for that each time through the loop */
1990 REXEC_FBC_UTF8_CLASS_SCAN(
1991 to_complement ^ cBOOL(_generic_utf8(
1994 swash_fetch(PL_utf8_swash_ptrs[classnum],
2002 /* what trie are we using right now */
2003 reg_ac_data *aho = (reg_ac_data*)progi->data->data[ ARG( c ) ];
2004 reg_trie_data *trie = (reg_trie_data*)progi->data->data[ aho->trie ];
2005 HV *widecharmap = MUTABLE_HV(progi->data->data[ aho->trie + 1 ]);
2007 const char *last_start = strend - trie->minlen;
2009 const char *real_start = s;
2011 STRLEN maxlen = trie->maxlen;
2013 U8 **points; /* map of where we were in the input string
2014 when reading a given char. For ASCII this
2015 is unnecessary overhead as the relationship
2016 is always 1:1, but for Unicode, especially
2017 case folded Unicode this is not true. */
2018 U8 foldbuf[ UTF8_MAXBYTES_CASE + 1 ];
2022 GET_RE_DEBUG_FLAGS_DECL;
2024 /* We can't just allocate points here. We need to wrap it in
2025 * an SV so it gets freed properly if there is a croak while
2026 * running the match */
2029 sv_points=newSV(maxlen * sizeof(U8 *));
2030 SvCUR_set(sv_points,
2031 maxlen * sizeof(U8 *));
2032 SvPOK_on(sv_points);
2033 sv_2mortal(sv_points);
2034 points=(U8**)SvPV_nolen(sv_points );
2035 if ( trie_type != trie_utf8_fold
2036 && (trie->bitmap || OP(c)==AHOCORASICKC) )
2039 bitmap=(U8*)trie->bitmap;
2041 bitmap=(U8*)ANYOF_BITMAP(c);
2043 /* this is the Aho-Corasick algorithm modified a touch
2044 to include special handling for long "unknown char" sequences.
2045 The basic idea being that we use AC as long as we are dealing
2046 with a possible matching char, when we encounter an unknown char
2047 (and we have not encountered an accepting state) we scan forward
2048 until we find a legal starting char.
2049 AC matching is basically that of trie matching, except that when
2050 we encounter a failing transition, we fall back to the current
2051 states "fail state", and try the current char again, a process
2052 we repeat until we reach the root state, state 1, or a legal
2053 transition. If we fail on the root state then we can either
2054 terminate if we have reached an accepting state previously, or
2055 restart the entire process from the beginning if we have not.
2058 while (s <= last_start) {
2059 const U32 uniflags = UTF8_ALLOW_DEFAULT;
2067 U8 *uscan = (U8*)NULL;
2068 U8 *leftmost = NULL;
2070 U32 accepted_word= 0;
2074 while ( state && uc <= (U8*)strend ) {
2076 U32 word = aho->states[ state ].wordnum;
2080 DEBUG_TRIE_EXECUTE_r(
2081 if ( uc <= (U8*)last_start && !BITMAP_TEST(bitmap,*uc) ) {
2082 dump_exec_pos( (char *)uc, c, strend, real_start,
2083 (char *)uc, utf8_target );
2084 PerlIO_printf( Perl_debug_log,
2085 " Scanning for legal start char...\n");
2089 while ( uc <= (U8*)last_start && !BITMAP_TEST(bitmap,*uc) ) {
2093 while ( uc <= (U8*)last_start && !BITMAP_TEST(bitmap,*uc) ) {
2099 if (uc >(U8*)last_start) break;
2103 U8 *lpos= points[ (pointpos - trie->wordinfo[word].len) % maxlen ];
2104 if (!leftmost || lpos < leftmost) {
2105 DEBUG_r(accepted_word=word);
2111 points[pointpos++ % maxlen]= uc;
2112 if (foldlen || uc < (U8*)strend) {
2113 REXEC_TRIE_READ_CHAR(trie_type, trie,
2115 uscan, len, uvc, charid, foldlen,
2117 DEBUG_TRIE_EXECUTE_r({
2118 dump_exec_pos( (char *)uc, c, strend,
2119 real_start, s, utf8_target);
2120 PerlIO_printf(Perl_debug_log,
2121 " Charid:%3u CP:%4"UVxf" ",
2133 word = aho->states[ state ].wordnum;
2135 base = aho->states[ state ].trans.base;
2137 DEBUG_TRIE_EXECUTE_r({
2139 dump_exec_pos( (char *)uc, c, strend, real_start,
2141 PerlIO_printf( Perl_debug_log,
2142 "%sState: %4"UVxf", word=%"UVxf,
2143 failed ? " Fail transition to " : "",
2144 (UV)state, (UV)word);
2150 ( ((offset = base + charid
2151 - 1 - trie->uniquecharcount)) >= 0)
2152 && ((U32)offset < trie->lasttrans)
2153 && trie->trans[offset].check == state
2154 && (tmp=trie->trans[offset].next))
2156 DEBUG_TRIE_EXECUTE_r(
2157 PerlIO_printf( Perl_debug_log," - legal\n"));
2162 DEBUG_TRIE_EXECUTE_r(
2163 PerlIO_printf( Perl_debug_log," - fail\n"));
2165 state = aho->fail[state];
2169 /* we must be accepting here */
2170 DEBUG_TRIE_EXECUTE_r(
2171 PerlIO_printf( Perl_debug_log," - accepting\n"));
2180 if (!state) state = 1;
2183 if ( aho->states[ state ].wordnum ) {
2184 U8 *lpos = points[ (pointpos - trie->wordinfo[aho->states[ state ].wordnum].len) % maxlen ];
2185 if (!leftmost || lpos < leftmost) {
2186 DEBUG_r(accepted_word=aho->states[ state ].wordnum);
2191 s = (char*)leftmost;
2192 DEBUG_TRIE_EXECUTE_r({
2194 Perl_debug_log,"Matches word #%"UVxf" at position %"IVdf". Trying full pattern...\n",
2195 (UV)accepted_word, (IV)(s - real_start)
2198 if (reginfo->intuit || regtry(reginfo, &s)) {
2204 DEBUG_TRIE_EXECUTE_r({
2205 PerlIO_printf( Perl_debug_log,"Pattern failed. Looking for new start point...\n");
2208 DEBUG_TRIE_EXECUTE_r(
2209 PerlIO_printf( Perl_debug_log,"No match.\n"));
2218 Perl_croak(aTHX_ "panic: unknown regstclass %d", (int)OP(c));
2226 /* set RX_SAVED_COPY, RX_SUBBEG etc.
2227 * flags have same meanings as with regexec_flags() */
2230 S_reg_set_capture_string(pTHX_ REGEXP * const rx,
2237 struct regexp *const prog = ReANY(rx);
2239 if (flags & REXEC_COPY_STR) {
2243 PerlIO_printf(Perl_debug_log,
2244 "Copy on write: regexp capture, type %d\n",
2247 /* Create a new COW SV to share the match string and store
2248 * in saved_copy, unless the current COW SV in saved_copy
2249 * is valid and suitable for our purpose */
2250 if (( prog->saved_copy
2251 && SvIsCOW(prog->saved_copy)
2252 && SvPOKp(prog->saved_copy)
2255 && SvPVX(sv) == SvPVX(prog->saved_copy)))
2257 /* just reuse saved_copy SV */
2258 if (RXp_MATCH_COPIED(prog)) {
2259 Safefree(prog->subbeg);
2260 RXp_MATCH_COPIED_off(prog);
2264 /* create new COW SV to share string */
2265 RX_MATCH_COPY_FREE(rx);
2266 prog->saved_copy = sv_setsv_cow(prog->saved_copy, sv);
2268 prog->subbeg = (char *)SvPVX_const(prog->saved_copy);
2269 assert (SvPOKp(prog->saved_copy));
2270 prog->sublen = strend - strbeg;
2271 prog->suboffset = 0;
2272 prog->subcoffset = 0;
2277 SSize_t max = strend - strbeg;
2280 if ( (flags & REXEC_COPY_SKIP_POST)
2281 && !(prog->extflags & RXf_PMf_KEEPCOPY) /* //p */
2282 && !(PL_sawampersand & SAWAMPERSAND_RIGHT)
2283 ) { /* don't copy $' part of string */
2286 /* calculate the right-most part of the string covered
2287 * by a capture. Due to look-ahead, this may be to
2288 * the right of $&, so we have to scan all captures */
2289 while (n <= prog->lastparen) {
2290 if (prog->offs[n].end > max)
2291 max = prog->offs[n].end;
2295 max = (PL_sawampersand & SAWAMPERSAND_LEFT)
2296 ? prog->offs[0].start
2298 assert(max >= 0 && max <= strend - strbeg);
2301 if ( (flags & REXEC_COPY_SKIP_PRE)
2302 && !(prog->extflags & RXf_PMf_KEEPCOPY) /* //p */
2303 && !(PL_sawampersand & SAWAMPERSAND_LEFT)
2304 ) { /* don't copy $` part of string */
2307 /* calculate the left-most part of the string covered
2308 * by a capture. Due to look-behind, this may be to
2309 * the left of $&, so we have to scan all captures */
2310 while (min && n <= prog->lastparen) {
2311 if ( prog->offs[n].start != -1
2312 && prog->offs[n].start < min)
2314 min = prog->offs[n].start;
2318 if ((PL_sawampersand & SAWAMPERSAND_RIGHT)
2319 && min > prog->offs[0].end
2321 min = prog->offs[0].end;
2325 assert(min >= 0 && min <= max && min <= strend - strbeg);
2328 if (RX_MATCH_COPIED(rx)) {
2329 if (sublen > prog->sublen)
2331 (char*)saferealloc(prog->subbeg, sublen+1);
2334 prog->subbeg = (char*)safemalloc(sublen+1);
2335 Copy(strbeg + min, prog->subbeg, sublen, char);
2336 prog->subbeg[sublen] = '\0';
2337 prog->suboffset = min;
2338 prog->sublen = sublen;
2339 RX_MATCH_COPIED_on(rx);
2341 prog->subcoffset = prog->suboffset;
2342 if (prog->suboffset && utf8_target) {
2343 /* Convert byte offset to chars.
2344 * XXX ideally should only compute this if @-/@+
2345 * has been seen, a la PL_sawampersand ??? */
2347 /* If there's a direct correspondence between the
2348 * string which we're matching and the original SV,
2349 * then we can use the utf8 len cache associated with
2350 * the SV. In particular, it means that under //g,
2351 * sv_pos_b2u() will use the previously cached
2352 * position to speed up working out the new length of
2353 * subcoffset, rather than counting from the start of
2354 * the string each time. This stops
2355 * $x = "\x{100}" x 1E6; 1 while $x =~ /(.)/g;
2356 * from going quadratic */
2357 if (SvPOKp(sv) && SvPVX(sv) == strbeg)
2358 prog->subcoffset = sv_pos_b2u_flags(sv, prog->subcoffset,
2359 SV_GMAGIC|SV_CONST_RETURN);
2361 prog->subcoffset = utf8_length((U8*)strbeg,
2362 (U8*)(strbeg+prog->suboffset));
2366 RX_MATCH_COPY_FREE(rx);
2367 prog->subbeg = strbeg;
2368 prog->suboffset = 0;
2369 prog->subcoffset = 0;
2370 prog->sublen = strend - strbeg;
2378 - regexec_flags - match a regexp against a string
2381 Perl_regexec_flags(pTHX_ REGEXP * const rx, char *stringarg, char *strend,
2382 char *strbeg, SSize_t minend, SV *sv, void *data, U32 flags)
2383 /* stringarg: the point in the string at which to begin matching */
2384 /* strend: pointer to null at end of string */
2385 /* strbeg: real beginning of string */
2386 /* minend: end of match must be >= minend bytes after stringarg. */
2387 /* sv: SV being matched: only used for utf8 flag, pos() etc; string
2388 * itself is accessed via the pointers above */
2389 /* data: May be used for some additional optimizations.
2390 Currently unused. */
2391 /* flags: For optimizations. See REXEC_* in regexp.h */
2395 struct regexp *const prog = ReANY(rx);
2399 SSize_t minlen; /* must match at least this many chars */
2400 SSize_t dontbother = 0; /* how many characters not to try at end */
2401 const bool utf8_target = cBOOL(DO_UTF8(sv));
2403 RXi_GET_DECL(prog,progi);
2404 regmatch_info reginfo_buf; /* create some info to pass to regtry etc */
2405 regmatch_info *const reginfo = ®info_buf;
2406 regexp_paren_pair *swap = NULL;
2408 GET_RE_DEBUG_FLAGS_DECL;
2410 PERL_ARGS_ASSERT_REGEXEC_FLAGS;
2411 PERL_UNUSED_ARG(data);
2413 /* Be paranoid... */
2414 if (prog == NULL || stringarg == NULL) {
2415 Perl_croak(aTHX_ "NULL regexp parameter");
2420 debug_start_match(rx, utf8_target, stringarg, strend,
2424 startpos = stringarg;
2426 if (prog->intflags & PREGf_GPOS_SEEN) {
2429 /* set reginfo->ganch, the position where \G can match */
2432 (flags & REXEC_IGNOREPOS)
2433 ? stringarg /* use start pos rather than pos() */
2434 : (sv && (mg = mg_find_mglob(sv)) && mg->mg_len >= 0)
2435 /* Defined pos(): */
2436 ? strbeg + MgBYTEPOS(mg, sv, strbeg, strend-strbeg)
2437 : strbeg; /* pos() not defined; use start of string */
2439 DEBUG_GPOS_r(PerlIO_printf(Perl_debug_log,
2440 "GPOS ganch set to strbeg[%"IVdf"]\n", (IV)(reginfo->ganch - strbeg)));
2442 /* in the presence of \G, we may need to start looking earlier in
2443 * the string than the suggested start point of stringarg:
2444 * if prog->gofs is set, then that's a known, fixed minimum
2447 * /ab|c\G/: gofs = 1
2448 * or if the minimum offset isn't known, then we have to go back
2449 * to the start of the string, e.g. /w+\G/
2452 if (prog->intflags & PREGf_ANCH_GPOS) {
2453 startpos = reginfo->ganch - prog->gofs;
2455 ((flags & REXEC_FAIL_ON_UNDERFLOW) ? stringarg : strbeg))
2457 DEBUG_r(PerlIO_printf(Perl_debug_log,
2458 "fail: ganch-gofs before earliest possible start\n"));
2462 else if (prog->gofs) {
2463 if (startpos - prog->gofs < strbeg)
2466 startpos -= prog->gofs;
2468 else if (prog->intflags & PREGf_GPOS_FLOAT)
2472 minlen = prog->minlen;
2473 if ((startpos + minlen) > strend || startpos < strbeg) {
2474 DEBUG_r(PerlIO_printf(Perl_debug_log,
2475 "Regex match can't succeed, so not even tried\n"));
2479 /* at the end of this function, we'll do a LEAVE_SCOPE(oldsave),
2480 * which will call destuctors to reset PL_regmatch_state, free higher
2481 * PL_regmatch_slabs, and clean up regmatch_info_aux and
2482 * regmatch_info_aux_eval */
2484 oldsave = PL_savestack_ix;
2488 if ((prog->extflags & RXf_USE_INTUIT)
2489 && !(flags & REXEC_CHECKED))
2491 s = re_intuit_start(rx, sv, strbeg, startpos, strend,
2496 if (prog->extflags & RXf_CHECK_ALL) {
2497 /* we can match based purely on the result of INTUIT.
2498 * Set up captures etc just for $& and $-[0]
2499 * (an intuit-only match wont have $1,$2,..) */
2500 assert(!prog->nparens);
2502 /* s/// doesn't like it if $& is earlier than where we asked it to
2503 * start searching (which can happen on something like /.\G/) */
2504 if ( (flags & REXEC_FAIL_ON_UNDERFLOW)
2507 /* this should only be possible under \G */
2508 assert(prog->intflags & PREGf_GPOS_SEEN);
2509 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
2510 "matched, but failing for REXEC_FAIL_ON_UNDERFLOW\n"));
2514 /* match via INTUIT shouldn't have any captures.
2515 * Let @-, @+, $^N know */
2516 prog->lastparen = prog->lastcloseparen = 0;
2517 RX_MATCH_UTF8_set(rx, utf8_target);
2518 prog->offs[0].start = s - strbeg;
2519 prog->offs[0].end = utf8_target
2520 ? (char*)utf8_hop((U8*)s, prog->minlenret) - strbeg
2521 : s - strbeg + prog->minlenret;
2522 if ( !(flags & REXEC_NOT_FIRST) )
2523 S_reg_set_capture_string(aTHX_ rx,
2525 sv, flags, utf8_target);
2531 multiline = prog->extflags & RXf_PMf_MULTILINE;
2533 if (strend - s < (minlen+(prog->check_offset_min<0?prog->check_offset_min:0))) {
2534 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
2535 "String too short [regexec_flags]...\n"));
2539 /* Check validity of program. */
2540 if (UCHARAT(progi->program) != REG_MAGIC) {
2541 Perl_croak(aTHX_ "corrupted regexp program");
2544 RX_MATCH_TAINTED_off(rx);
2546 reginfo->prog = rx; /* Yes, sorry that this is confusing. */
2547 reginfo->intuit = 0;
2548 reginfo->is_utf8_target = cBOOL(utf8_target);
2549 reginfo->is_utf8_pat = cBOOL(RX_UTF8(rx));
2550 reginfo->warned = FALSE;
2551 reginfo->strbeg = strbeg;
2553 reginfo->poscache_maxiter = 0; /* not yet started a countdown */
2554 reginfo->strend = strend;
2555 /* see how far we have to get to not match where we matched before */
2556 reginfo->till = stringarg + minend;
2558 if (prog->extflags & RXf_EVAL_SEEN && SvPADTMP(sv) && !IS_PADGV(sv)) {
2559 /* SAVEFREESV, not sv_mortalcopy, as this SV must last until after
2560 S_cleanup_regmatch_info_aux has executed (registered by
2561 SAVEDESTRUCTOR_X below). S_cleanup_regmatch_info_aux modifies
2562 magic belonging to this SV.
2563 Not newSVsv, either, as it does not COW.
2565 reginfo->sv = newSV(0);
2566 SvSetSV_nosteal(reginfo->sv, sv);
2567 SAVEFREESV(reginfo->sv);
2570 /* reserve next 2 or 3 slots in PL_regmatch_state:
2571 * slot N+0: may currently be in use: skip it
2572 * slot N+1: use for regmatch_info_aux struct
2573 * slot N+2: use for regmatch_info_aux_eval struct if we have (?{})'s
2574 * slot N+3: ready for use by regmatch()
2578 regmatch_state *old_regmatch_state;
2579 regmatch_slab *old_regmatch_slab;
2580 int i, max = (prog->extflags & RXf_EVAL_SEEN) ? 2 : 1;
2582 /* on first ever match, allocate first slab */
2583 if (!PL_regmatch_slab) {
2584 Newx(PL_regmatch_slab, 1, regmatch_slab);
2585 PL_regmatch_slab->prev = NULL;
2586 PL_regmatch_slab->next = NULL;
2587 PL_regmatch_state = SLAB_FIRST(PL_regmatch_slab);
2590 old_regmatch_state = PL_regmatch_state;
2591 old_regmatch_slab = PL_regmatch_slab;
2593 for (i=0; i <= max; i++) {
2595 reginfo->info_aux = &(PL_regmatch_state->u.info_aux);
2597 reginfo->info_aux_eval =
2598 reginfo->info_aux->info_aux_eval =
2599 &(PL_regmatch_state->u.info_aux_eval);
2601 if (++PL_regmatch_state > SLAB_LAST(PL_regmatch_slab))
2602 PL_regmatch_state = S_push_slab(aTHX);
2605 /* note initial PL_regmatch_state position; at end of match we'll
2606 * pop back to there and free any higher slabs */
2608 reginfo->info_aux->old_regmatch_state = old_regmatch_state;
2609 reginfo->info_aux->old_regmatch_slab = old_regmatch_slab;
2610 reginfo->info_aux->poscache = NULL;
2612 SAVEDESTRUCTOR_X(S_cleanup_regmatch_info_aux, reginfo->info_aux);
2614 if ((prog->extflags & RXf_EVAL_SEEN))
2615 S_setup_eval_state(aTHX_ reginfo);
2617 reginfo->info_aux_eval = reginfo->info_aux->info_aux_eval = NULL;
2620 /* If there is a "must appear" string, look for it. */
2622 if (PL_curpm && (PM_GETRE(PL_curpm) == rx)) {
2623 /* We have to be careful. If the previous successful match
2624 was from this regex we don't want a subsequent partially
2625 successful match to clobber the old results.
2626 So when we detect this possibility we add a swap buffer
2627 to the re, and switch the buffer each match. If we fail,
2628 we switch it back; otherwise we leave it swapped.
2631 /* do we need a save destructor here for eval dies? */
2632 Newxz(prog->offs, (prog->nparens + 1), regexp_paren_pair);
2633 DEBUG_BUFFERS_r(PerlIO_printf(Perl_debug_log,
2634 "rex=0x%"UVxf" saving offs: orig=0x%"UVxf" new=0x%"UVxf"\n",
2641 /* Simplest case: anchored match need be tried only once. */
2642 /* [unless only anchor is BOL and multiline is set] */
2643 if (prog->intflags & (PREGf_ANCH & ~PREGf_ANCH_GPOS)) {
2644 if (s == startpos && regtry(reginfo, &s))
2646 else if (multiline || (prog->intflags & (PREGf_IMPLICIT | PREGf_ANCH_MBOL))) /* XXXX SBOL? */
2651 dontbother = minlen - 1;
2652 end = HOP3c(strend, -dontbother, strbeg) - 1;
2653 /* for multiline we only have to try after newlines */
2654 if (prog->check_substr || prog->check_utf8) {
2655 /* because of the goto we can not easily reuse the macros for bifurcating the
2656 unicode/non-unicode match modes here like we do elsewhere - demerphq */
2659 goto after_try_utf8;
2661 if (regtry(reginfo, &s)) {
2668 if (prog->extflags & RXf_USE_INTUIT) {
2669 s = re_intuit_start(rx, sv, strbeg,
2670 s + UTF8SKIP(s), strend, flags, NULL);
2679 } /* end search for check string in unicode */
2681 if (s == startpos) {
2682 goto after_try_latin;
2685 if (regtry(reginfo, &s)) {
2692 if (prog->extflags & RXf_USE_INTUIT) {
2693 s = re_intuit_start(rx, sv, strbeg,
2694 s + 1, strend, flags, NULL);
2703 } /* end search for check string in latin*/
2704 } /* end search for check string */
2705 else { /* search for newline */
2707 /*XXX: The s-- is almost definitely wrong here under unicode - demeprhq*/
2710 /* We can use a more efficient search as newlines are the same in unicode as they are in latin */
2711 while (s <= end) { /* note it could be possible to match at the end of the string */
2712 if (*s++ == '\n') { /* don't need PL_utf8skip here */
2713 if (regtry(reginfo, &s))
2717 } /* end search for newline */
2718 } /* end anchored/multiline check string search */
2720 } else if (prog->intflags & PREGf_ANCH_GPOS)
2722 /* PREGf_ANCH_GPOS should never be true if PREGf_GPOS_SEEN is not true */
2723 assert(prog->intflags & PREGf_GPOS_SEEN);
2724 /* For anchored \G, the only position it can match from is
2725 * (ganch-gofs); we already set startpos to this above; if intuit
2726 * moved us on from there, we can't possibly succeed */
2727 assert(startpos == reginfo->ganch - prog->gofs);
2728 if (s == startpos && regtry(reginfo, &s))
2733 /* Messy cases: unanchored match. */
2734 if ((prog->anchored_substr || prog->anchored_utf8) && prog->intflags & PREGf_SKIP) {
2735 /* we have /x+whatever/ */
2736 /* it must be a one character string (XXXX Except is_utf8_pat?) */
2742 if (! prog->anchored_utf8) {
2743 to_utf8_substr(prog);
2745 ch = SvPVX_const(prog->anchored_utf8)[0];
2748 DEBUG_EXECUTE_r( did_match = 1 );
2749 if (regtry(reginfo, &s)) goto got_it;
2751 while (s < strend && *s == ch)
2758 if (! prog->anchored_substr) {
2759 if (! to_byte_substr(prog)) {
2760 NON_UTF8_TARGET_BUT_UTF8_REQUIRED(phooey);
2763 ch = SvPVX_const(prog->anchored_substr)[0];
2766 DEBUG_EXECUTE_r( did_match = 1 );
2767 if (regtry(reginfo, &s)) goto got_it;
2769 while (s < strend && *s == ch)
2774 DEBUG_EXECUTE_r(if (!did_match)
2775 PerlIO_printf(Perl_debug_log,
2776 "Did not find anchored character...\n")
2779 else if (prog->anchored_substr != NULL
2780 || prog->anchored_utf8 != NULL
2781 || ((prog->float_substr != NULL || prog->float_utf8 != NULL)
2782 && prog->float_max_offset < strend - s)) {
2787 char *last1; /* Last position checked before */
2791 if (prog->anchored_substr || prog->anchored_utf8) {
2793 if (! prog->anchored_utf8) {
2794 to_utf8_substr(prog);
2796 must = prog->anchored_utf8;
2799 if (! prog->anchored_substr) {
2800 if (! to_byte_substr(prog)) {
2801 NON_UTF8_TARGET_BUT_UTF8_REQUIRED(phooey);
2804 must = prog->anchored_substr;
2806 back_max = back_min = prog->anchored_offset;
2809 if (! prog->float_utf8) {
2810 to_utf8_substr(prog);
2812 must = prog->float_utf8;
2815 if (! prog->float_substr) {
2816 if (! to_byte_substr(prog)) {
2817 NON_UTF8_TARGET_BUT_UTF8_REQUIRED(phooey);
2820 must = prog->float_substr;
2822 back_max = prog->float_max_offset;
2823 back_min = prog->float_min_offset;
2829 last = HOP3c(strend, /* Cannot start after this */
2830 -(SSize_t)(CHR_SVLEN(must)
2831 - (SvTAIL(must) != 0) + back_min), strbeg);
2833 if (s > reginfo->strbeg)
2834 last1 = HOPc(s, -1);
2836 last1 = s - 1; /* bogus */
2838 /* XXXX check_substr already used to find "s", can optimize if
2839 check_substr==must. */
2841 strend = HOPc(strend, -dontbother);
2842 while ( (s <= last) &&
2843 (s = fbm_instr((unsigned char*)HOP4c(s, back_min, strbeg, strend),
2844 (unsigned char*)strend, must,
2845 multiline ? FBMrf_MULTILINE : 0)) ) {
2846 DEBUG_EXECUTE_r( did_match = 1 );
2847 if (HOPc(s, -back_max) > last1) {
2848 last1 = HOPc(s, -back_min);
2849 s = HOPc(s, -back_max);
2852 char * const t = (last1 >= reginfo->strbeg)
2853 ? HOPc(last1, 1) : last1 + 1;
2855 last1 = HOPc(s, -back_min);
2859 while (s <= last1) {
2860 if (regtry(reginfo, &s))
2863 s++; /* to break out of outer loop */
2870 while (s <= last1) {
2871 if (regtry(reginfo, &s))
2877 DEBUG_EXECUTE_r(if (!did_match) {
2878 RE_PV_QUOTED_DECL(quoted, utf8_target, PERL_DEBUG_PAD_ZERO(0),
2879 SvPVX_const(must), RE_SV_DUMPLEN(must), 30);
2880 PerlIO_printf(Perl_debug_log, "Did not find %s substr %s%s...\n",
2881 ((must == prog->anchored_substr || must == prog->anchored_utf8)
2882 ? "anchored" : "floating"),
2883 quoted, RE_SV_TAIL(must));
2887 else if ( (c = progi->regstclass) ) {
2889 const OPCODE op = OP(progi->regstclass);
2890 /* don't bother with what can't match */
2891 if (PL_regkind[op] != EXACT && op != CANY && PL_regkind[op] != TRIE)
2892 strend = HOPc(strend, -(minlen - 1));
2895 SV * const prop = sv_newmortal();
2896 regprop(prog, prop, c);
2898 RE_PV_QUOTED_DECL(quoted,utf8_target,PERL_DEBUG_PAD_ZERO(1),
2900 PerlIO_printf(Perl_debug_log,
2901 "Matching stclass %.*s against %s (%d bytes)\n",
2902 (int)SvCUR(prop), SvPVX_const(prop),
2903 quoted, (int)(strend - s));
2906 if (find_byclass(prog, c, s, strend, reginfo))
2908 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "Contradicts stclass... [regexec_flags]\n"));
2912 if (prog->float_substr != NULL || prog->float_utf8 != NULL) {
2920 if (! prog->float_utf8) {
2921 to_utf8_substr(prog);
2923 float_real = prog->float_utf8;
2926 if (! prog->float_substr) {
2927 if (! to_byte_substr(prog)) {
2928 NON_UTF8_TARGET_BUT_UTF8_REQUIRED(phooey);
2931 float_real = prog->float_substr;
2934 little = SvPV_const(float_real, len);
2935 if (SvTAIL(float_real)) {
2936 /* This means that float_real contains an artificial \n on
2937 * the end due to the presence of something like this:
2938 * /foo$/ where we can match both "foo" and "foo\n" at the
2939 * end of the string. So we have to compare the end of the
2940 * string first against the float_real without the \n and
2941 * then against the full float_real with the string. We
2942 * have to watch out for cases where the string might be
2943 * smaller than the float_real or the float_real without
2945 char *checkpos= strend - len;
2947 PerlIO_printf(Perl_debug_log,
2948 "%sChecking for float_real.%s\n",
2949 PL_colors[4], PL_colors[5]));
2950 if (checkpos + 1 < strbeg) {
2951 /* can't match, even if we remove the trailing \n
2952 * string is too short to match */
2954 PerlIO_printf(Perl_debug_log,
2955 "%sString shorter than required trailing substring, cannot match.%s\n",
2956 PL_colors[4], PL_colors[5]));
2958 } else if (memEQ(checkpos + 1, little, len - 1)) {
2959 /* can match, the end of the string matches without the
2961 last = checkpos + 1;
2962 } else if (checkpos < strbeg) {
2963 /* cant match, string is too short when the "\n" is
2966 PerlIO_printf(Perl_debug_log,
2967 "%sString does not contain required trailing substring, cannot match.%s\n",
2968 PL_colors[4], PL_colors[5]));
2970 } else if (!multiline) {
2971 /* non multiline match, so compare with the "\n" at the
2972 * end of the string */
2973 if (memEQ(checkpos, little, len)) {
2977 PerlIO_printf(Perl_debug_log,
2978 "%sString does not contain required trailing substring, cannot match.%s\n",
2979 PL_colors[4], PL_colors[5]));
2983 /* multiline match, so we have to search for a place
2984 * where the full string is located */
2990 last = rninstr(s, strend, little, little + len);
2992 last = strend; /* matching "$" */
2995 /* at one point this block contained a comment which was
2996 * probably incorrect, which said that this was a "should not
2997 * happen" case. Even if it was true when it was written I am
2998 * pretty sure it is not anymore, so I have removed the comment
2999 * and replaced it with this one. Yves */
3001 PerlIO_printf(Perl_debug_log,
3002 "String does not contain required substring, cannot match.\n"
3006 dontbother = strend - last + prog->float_min_offset;
3008 if (minlen && (dontbother < minlen))
3009 dontbother = minlen - 1;
3010 strend -= dontbother; /* this one's always in bytes! */
3011 /* We don't know much -- general case. */
3014 if (regtry(reginfo, &s))
3023 if (regtry(reginfo, &s))
3025 } while (s++ < strend);
3033 /* s/// doesn't like it if $& is earlier than where we asked it to
3034 * start searching (which can happen on something like /.\G/) */
3035 if ( (flags & REXEC_FAIL_ON_UNDERFLOW)
3036 && (prog->offs[0].start < stringarg - strbeg))
3038 /* this should only be possible under \G */
3039 assert(prog->intflags & PREGf_GPOS_SEEN);
3040 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
3041 "matched, but failing for REXEC_FAIL_ON_UNDERFLOW\n"));
3047 PerlIO_printf(Perl_debug_log,
3048 "rex=0x%"UVxf" freeing offs: 0x%"UVxf"\n",
3055 /* clean up; this will trigger destructors that will free all slabs
3056 * above the current one, and cleanup the regmatch_info_aux
3057 * and regmatch_info_aux_eval sructs */
3059 LEAVE_SCOPE(oldsave);
3061 if (RXp_PAREN_NAMES(prog))
3062 (void)hv_iterinit(RXp_PAREN_NAMES(prog));
3064 RX_MATCH_UTF8_set(rx, utf8_target);
3066 /* make sure $`, $&, $', and $digit will work later */
3067 if ( !(flags & REXEC_NOT_FIRST) )
3068 S_reg_set_capture_string(aTHX_ rx,
3069 strbeg, reginfo->strend,
3070 sv, flags, utf8_target);
3075 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "%sMatch failed%s\n",
3076 PL_colors[4], PL_colors[5]));
3078 /* clean up; this will trigger destructors that will free all slabs
3079 * above the current one, and cleanup the regmatch_info_aux
3080 * and regmatch_info_aux_eval sructs */
3082 LEAVE_SCOPE(oldsave);
3085 /* we failed :-( roll it back */
3086 DEBUG_BUFFERS_r(PerlIO_printf(Perl_debug_log,
3087 "rex=0x%"UVxf" rolling back offs: freeing=0x%"UVxf" restoring=0x%"UVxf"\n",
3092 Safefree(prog->offs);
3099 /* Set which rex is pointed to by PL_reg_curpm, handling ref counting.
3100 * Do inc before dec, in case old and new rex are the same */
3101 #define SET_reg_curpm(Re2) \
3102 if (reginfo->info_aux_eval) { \
3103 (void)ReREFCNT_inc(Re2); \
3104 ReREFCNT_dec(PM_GETRE(PL_reg_curpm)); \
3105 PM_SETRE((PL_reg_curpm), (Re2)); \
3110 - regtry - try match at specific point
3112 STATIC I32 /* 0 failure, 1 success */
3113 S_regtry(pTHX_ regmatch_info *reginfo, char **startposp)
3117 REGEXP *const rx = reginfo->prog;
3118 regexp *const prog = ReANY(rx);
3120 RXi_GET_DECL(prog,progi);
3121 GET_RE_DEBUG_FLAGS_DECL;
3123 PERL_ARGS_ASSERT_REGTRY;
3125 reginfo->cutpoint=NULL;
3127 prog->offs[0].start = *startposp - reginfo->strbeg;
3128 prog->lastparen = 0;
3129 prog->lastcloseparen = 0;
3131 /* XXXX What this code is doing here?!!! There should be no need
3132 to do this again and again, prog->lastparen should take care of
3135 /* Tests pat.t#187 and split.t#{13,14} seem to depend on this code.
3136 * Actually, the code in regcppop() (which Ilya may be meaning by
3137 * prog->lastparen), is not needed at all by the test suite
3138 * (op/regexp, op/pat, op/split), but that code is needed otherwise
3139 * this erroneously leaves $1 defined: "1" =~ /^(?:(\d)x)?\d$/
3140 * Meanwhile, this code *is* needed for the
3141 * above-mentioned test suite tests to succeed. The common theme
3142 * on those tests seems to be returning null fields from matches.
3143 * --jhi updated by dapm */
3145 if (prog->nparens) {
3146 regexp_paren_pair *pp = prog->offs;
3148 for (i = prog->nparens; i > (I32)prog->lastparen; i--) {
3156 result = regmatch(reginfo, *startposp, progi->program + 1);
3158 prog->offs[0].end = result;
3161 if (reginfo->cutpoint)
3162 *startposp= reginfo->cutpoint;
3163 REGCP_UNWIND(lastcp);
3168 #define sayYES goto yes
3169 #define sayNO goto no
3170 #define sayNO_SILENT goto no_silent
3172 /* we dont use STMT_START/END here because it leads to
3173 "unreachable code" warnings, which are bogus, but distracting. */
3174 #define CACHEsayNO \
3175 if (ST.cache_mask) \
3176 reginfo->info_aux->poscache[ST.cache_offset] |= ST.cache_mask; \
3179 /* this is used to determine how far from the left messages like
3180 'failed...' are printed. It should be set such that messages
3181 are inline with the regop output that created them.
3183 #define REPORT_CODE_OFF 32
3186 #define CHRTEST_UNINIT -1001 /* c1/c2 haven't been calculated yet */
3187 #define CHRTEST_VOID -1000 /* the c1/c2 "next char" test should be skipped */
3188 #define CHRTEST_NOT_A_CP_1 -999
3189 #define CHRTEST_NOT_A_CP_2 -998
3191 /* grab a new slab and return the first slot in it */
3193 STATIC regmatch_state *
3196 #if PERL_VERSION < 9 && !defined(PERL_CORE)
3199 regmatch_slab *s = PL_regmatch_slab->next;
3201 Newx(s, 1, regmatch_slab);
3202 s->prev = PL_regmatch_slab;
3204 PL_regmatch_slab->next = s;
3206 PL_regmatch_slab = s;
3207 return SLAB_FIRST(s);
3211 /* push a new state then goto it */
3213 #define PUSH_STATE_GOTO(state, node, input) \
3214 pushinput = input; \
3216 st->resume_state = state; \
3219 /* push a new state with success backtracking, then goto it */
3221 #define PUSH_YES_STATE_GOTO(state, node, input) \
3222 pushinput = input; \
3224 st->resume_state = state; \
3225 goto push_yes_state;
3232 regmatch() - main matching routine
3234 This is basically one big switch statement in a loop. We execute an op,
3235 set 'next' to point the next op, and continue. If we come to a point which
3236 we may need to backtrack to on failure such as (A|B|C), we push a
3237 backtrack state onto the backtrack stack. On failure, we pop the top
3238 state, and re-enter the loop at the state indicated. If there are no more
3239 states to pop, we return failure.
3241 Sometimes we also need to backtrack on success; for example /A+/, where
3242 after successfully matching one A, we need to go back and try to
3243 match another one; similarly for lookahead assertions: if the assertion
3244 completes successfully, we backtrack to the state just before the assertion
3245 and then carry on. In these cases, the pushed state is marked as
3246 'backtrack on success too'. This marking is in fact done by a chain of
3247 pointers, each pointing to the previous 'yes' state. On success, we pop to
3248 the nearest yes state, discarding any intermediate failure-only states.
3249 Sometimes a yes state is pushed just to force some cleanup code to be
3250 called at the end of a successful match or submatch; e.g. (??{$re}) uses
3251 it to free the inner regex.
3253 Note that failure backtracking rewinds the cursor position, while
3254 success backtracking leaves it alone.
3256 A pattern is complete when the END op is executed, while a subpattern
3257 such as (?=foo) is complete when the SUCCESS op is executed. Both of these
3258 ops trigger the "pop to last yes state if any, otherwise return true"
3261 A common convention in this function is to use A and B to refer to the two
3262 subpatterns (or to the first nodes thereof) in patterns like /A*B/: so A is
3263 the subpattern to be matched possibly multiple times, while B is the entire
3264 rest of the pattern. Variable and state names reflect this convention.
3266 The states in the main switch are the union of ops and failure/success of
3267 substates associated with with that op. For example, IFMATCH is the op
3268 that does lookahead assertions /(?=A)B/ and so the IFMATCH state means
3269 'execute IFMATCH'; while IFMATCH_A is a state saying that we have just
3270 successfully matched A and IFMATCH_A_fail is a state saying that we have
3271 just failed to match A. Resume states always come in pairs. The backtrack
3272 state we push is marked as 'IFMATCH_A', but when that is popped, we resume
3273 at IFMATCH_A or IFMATCH_A_fail, depending on whether we are backtracking
3274 on success or failure.
3276 The struct that holds a backtracking state is actually a big union, with
3277 one variant for each major type of op. The variable st points to the
3278 top-most backtrack struct. To make the code clearer, within each
3279 block of code we #define ST to alias the relevant union.
3281 Here's a concrete example of a (vastly oversimplified) IFMATCH
3287 #define ST st->u.ifmatch
3289 case IFMATCH: // we are executing the IFMATCH op, (?=A)B
3290 ST.foo = ...; // some state we wish to save
3292 // push a yes backtrack state with a resume value of
3293 // IFMATCH_A/IFMATCH_A_fail, then continue execution at the
3295 PUSH_YES_STATE_GOTO(IFMATCH_A, A, newinput);
3298 case IFMATCH_A: // we have successfully executed A; now continue with B
3300 bar = ST.foo; // do something with the preserved value
3303 case IFMATCH_A_fail: // A failed, so the assertion failed
3304 ...; // do some housekeeping, then ...
3305 sayNO; // propagate the failure
3312 For any old-timers reading this who are familiar with the old recursive
3313 approach, the code above is equivalent to:
3315 case IFMATCH: // we are executing the IFMATCH op, (?=A)B
3324 ...; // do some housekeeping, then ...
3325 sayNO; // propagate the failure
3328 The topmost backtrack state, pointed to by st, is usually free. If you
3329 want to claim it, populate any ST.foo fields in it with values you wish to
3330 save, then do one of
3332 PUSH_STATE_GOTO(resume_state, node, newinput);
3333 PUSH_YES_STATE_GOTO(resume_state, node, newinput);
3335 which sets that backtrack state's resume value to 'resume_state', pushes a
3336 new free entry to the top of the backtrack stack, then goes to 'node'.
3337 On backtracking, the free slot is popped, and the saved state becomes the
3338 new free state. An ST.foo field in this new top state can be temporarily
3339 accessed to retrieve values, but once the main loop is re-entered, it
3340 becomes available for reuse.
3342 Note that the depth of the backtrack stack constantly increases during the
3343 left-to-right execution of the pattern, rather than going up and down with
3344 the pattern nesting. For example the stack is at its maximum at Z at the
3345 end of the pattern, rather than at X in the following:
3347 /(((X)+)+)+....(Y)+....Z/
3349 The only exceptions to this are lookahead/behind assertions and the cut,
3350 (?>A), which pop all the backtrack states associated with A before
3353 Backtrack state structs are allocated in slabs of about 4K in size.
3354 PL_regmatch_state and st always point to the currently active state,
3355 and PL_regmatch_slab points to the slab currently containing
3356 PL_regmatch_state. The first time regmatch() is called, the first slab is
3357 allocated, and is never freed until interpreter destruction. When the slab
3358 is full, a new one is allocated and chained to the end. At exit from
3359 regmatch(), slabs allocated since entry are freed.
3364 #define DEBUG_STATE_pp(pp) \
3366 DUMP_EXEC_POS(locinput, scan, utf8_target); \
3367 PerlIO_printf(Perl_debug_log, \
3368 " %*s"pp" %s%s%s%s%s\n", \
3370 PL_reg_name[st->resume_state], \
3371 ((st==yes_state||st==mark_state) ? "[" : ""), \
3372 ((st==yes_state) ? "Y" : ""), \
3373 ((st==mark_state) ? "M" : ""), \
3374 ((st==yes_state||st==mark_state) ? "]" : "") \
3379 #define REG_NODE_NUM(x) ((x) ? (int)((x)-prog) : -1)
3384 S_debug_start_match(pTHX_ const REGEXP *prog, const bool utf8_target,
3385 const char *start, const char *end, const char *blurb)
3387 const bool utf8_pat = RX_UTF8(prog) ? 1 : 0;
3389 PERL_ARGS_ASSERT_DEBUG_START_MATCH;
3394 RE_PV_QUOTED_DECL(s0, utf8_pat, PERL_DEBUG_PAD_ZERO(0),
3395 RX_PRECOMP_const(prog), RX_PRELEN(prog), 60);
3397 RE_PV_QUOTED_DECL(s1, utf8_target, PERL_DEBUG_PAD_ZERO(1),
3398 start, end - start, 60);
3400 PerlIO_printf(Perl_debug_log,
3401 "%s%s REx%s %s against %s\n",
3402 PL_colors[4], blurb, PL_colors[5], s0, s1);
3404 if (utf8_target||utf8_pat)
3405 PerlIO_printf(Perl_debug_log, "UTF-8 %s%s%s...\n",
3406 utf8_pat ? "pattern" : "",
3407 utf8_pat && utf8_target ? " and " : "",
3408 utf8_target ? "string" : ""
3414 S_dump_exec_pos(pTHX_ const char *locinput,
3415 const regnode *scan,
3416 const char *loc_regeol,
3417 const char *loc_bostr,
3418 const char *loc_reg_starttry,
3419 const bool utf8_target)
3421 const int docolor = *PL_colors[0] || *PL_colors[2] || *PL_colors[4];
3422 const int taill = (docolor ? 10 : 7); /* 3 chars for "> <" */
3423 int l = (loc_regeol - locinput) > taill ? taill : (loc_regeol - locinput);
3424 /* The part of the string before starttry has one color
3425 (pref0_len chars), between starttry and current
3426 position another one (pref_len - pref0_len chars),
3427 after the current position the third one.
3428 We assume that pref0_len <= pref_len, otherwise we
3429 decrease pref0_len. */
3430 int pref_len = (locinput - loc_bostr) > (5 + taill) - l
3431 ? (5 + taill) - l : locinput - loc_bostr;
3434 PERL_ARGS_ASSERT_DUMP_EXEC_POS;
3436 while (utf8_target && UTF8_IS_CONTINUATION(*(U8*)(locinput - pref_len)))
3438 pref0_len = pref_len - (locinput - loc_reg_starttry);
3439 if (l + pref_len < (5 + taill) && l < loc_regeol - locinput)
3440 l = ( loc_regeol - locinput > (5 + taill) - pref_len
3441 ? (5 + taill) - pref_len : loc_regeol - locinput);
3442 while (utf8_target && UTF8_IS_CONTINUATION(*(U8*)(locinput + l)))
3446 if (pref0_len > pref_len)
3447 pref0_len = pref_len;
3449 const int is_uni = (utf8_target && OP(scan) != CANY) ? 1 : 0;
3451 RE_PV_COLOR_DECL(s0,len0,is_uni,PERL_DEBUG_PAD(0),
3452 (locinput - pref_len),pref0_len, 60, 4, 5);
3454 RE_PV_COLOR_DECL(s1,len1,is_uni,PERL_DEBUG_PAD(1),
3455 (locinput - pref_len + pref0_len),
3456 pref_len - pref0_len, 60, 2, 3);
3458 RE_PV_COLOR_DECL(s2,len2,is_uni,PERL_DEBUG_PAD(2),
3459 locinput, loc_regeol - locinput, 10, 0, 1);
3461 const STRLEN tlen=len0+len1+len2;
3462 PerlIO_printf(Perl_debug_log,
3463 "%4"IVdf" <%.*s%.*s%s%.*s>%*s|",
3464 (IV)(locinput - loc_bostr),
3467 (docolor ? "" : "> <"),
3469 (int)(tlen > 19 ? 0 : 19 - tlen),
3476 /* reg_check_named_buff_matched()
3477 * Checks to see if a named buffer has matched. The data array of
3478 * buffer numbers corresponding to the buffer is expected to reside
3479 * in the regexp->data->data array in the slot stored in the ARG() of
3480 * node involved. Note that this routine doesn't actually care about the
3481 * name, that information is not preserved from compilation to execution.
3482 * Returns the index of the leftmost defined buffer with the given name
3483 * or 0 if non of the buffers matched.
3486 S_reg_check_named_buff_matched(pTHX_ const regexp *rex, const regnode *scan)
3489 RXi_GET_DECL(rex,rexi);
3490 SV *sv_dat= MUTABLE_SV(rexi->data->data[ ARG( scan ) ]);
3491 I32 *nums=(I32*)SvPVX(sv_dat);
3493 PERL_ARGS_ASSERT_REG_CHECK_NAMED_BUFF_MATCHED;
3495 for ( n=0; n<SvIVX(sv_dat); n++ ) {
3496 if ((I32)rex->lastparen >= nums[n] &&
3497 rex->offs[nums[n]].end != -1)
3507 S_setup_EXACTISH_ST_c1_c2(pTHX_ const regnode * const text_node, int *c1p,
3508 U8* c1_utf8, int *c2p, U8* c2_utf8, regmatch_info *reginfo)
3510 /* This function determines if there are one or two characters that match
3511 * the first character of the passed-in EXACTish node <text_node>, and if
3512 * so, returns them in the passed-in pointers.
3514 * If it determines that no possible character in the target string can
3515 * match, it returns FALSE; otherwise TRUE. (The FALSE situation occurs if
3516 * the first character in <text_node> requires UTF-8 to represent, and the
3517 * target string isn't in UTF-8.)
3519 * If there are more than two characters that could match the beginning of
3520 * <text_node>, or if more context is required to determine a match or not,
3521 * it sets both *<c1p> and *<c2p> to CHRTEST_VOID.
3523 * The motiviation behind this function is to allow the caller to set up
3524 * tight loops for matching. If <text_node> is of type EXACT, there is
3525 * only one possible character that can match its first character, and so
3526 * the situation is quite simple. But things get much more complicated if
3527 * folding is involved. It may be that the first character of an EXACTFish
3528 * node doesn't participate in any possible fold, e.g., punctuation, so it
3529 * can be matched only by itself. The vast majority of characters that are
3530 * in folds match just two things, their lower and upper-case equivalents.
3531 * But not all are like that; some have multiple possible matches, or match
3532 * sequences of more than one character. This function sorts all that out.
3534 * Consider the patterns A*B or A*?B where A and B are arbitrary. In a
3535 * loop of trying to match A*, we know we can't exit where the thing
3536 * following it isn't a B. And something can't be a B unless it is the
3537 * beginning of B. By putting a quick test for that beginning in a tight
3538 * loop, we can rule out things that can't possibly be B without having to
3539 * break out of the loop, thus avoiding work. Similarly, if A is a single
3540 * character, we can make a tight loop matching A*, using the outputs of
3543 * If the target string to match isn't in UTF-8, and there aren't
3544 * complications which require CHRTEST_VOID, *<c1p> and *<c2p> are set to
3545 * the one or two possible octets (which are characters in this situation)
3546 * that can match. In all cases, if there is only one character that can
3547 * match, *<c1p> and *<c2p> will be identical.
3549 * If the target string is in UTF-8, the buffers pointed to by <c1_utf8>
3550 * and <c2_utf8> will contain the one or two UTF-8 sequences of bytes that
3551 * can match the beginning of <text_node>. They should be declared with at
3552 * least length UTF8_MAXBYTES+1. (If the target string isn't in UTF-8, it is
3553 * undefined what these contain.) If one or both of the buffers are
3554 * invariant under UTF-8, *<c1p>, and *<c2p> will also be set to the
3555 * corresponding invariant. If variant, the corresponding *<c1p> and/or
3556 * *<c2p> will be set to a negative number(s) that shouldn't match any code
3557 * point (unless inappropriately coerced to unsigned). *<c1p> will equal
3558 * *<c2p> if and only if <c1_utf8> and <c2_utf8> are the same. */
3560 const bool utf8_target = reginfo->is_utf8_target;
3562 UV c1 = CHRTEST_NOT_A_CP_1;
3563 UV c2 = CHRTEST_NOT_A_CP_2;
3564 bool use_chrtest_void = FALSE;
3565 const bool is_utf8_pat = reginfo->is_utf8_pat;
3567 /* Used when we have both utf8 input and utf8 output, to avoid converting
3568 * to/from code points */
3569 bool utf8_has_been_setup = FALSE;
3573 U8 *pat = (U8*)STRING(text_node);
3574 U8 folded[UTF8_MAX_FOLD_CHAR_EXPAND * UTF8_MAXBYTES_CASE + 1];
3576 if (OP(text_node) == EXACT) {
3578 /* In an exact node, only one thing can be matched, that first
3579 * character. If both the pat and the target are UTF-8, we can just
3580 * copy the input to the output, avoiding finding the code point of
3585 else if (utf8_target) {
3586 Copy(pat, c1_utf8, UTF8SKIP(pat), U8);
3587 Copy(pat, c2_utf8, UTF8SKIP(pat), U8);
3588 utf8_has_been_setup = TRUE;
3591 c2 = c1 = valid_utf8_to_uvchr(pat, NULL);
3594 else { /* an EXACTFish node */
3595 U8 *pat_end = pat + STR_LEN(text_node);
3597 /* An EXACTFL node has at least some characters unfolded, because what
3598 * they match is not known until now. So, now is the time to fold
3599 * the first few of them, as many as are needed to determine 'c1' and
3600 * 'c2' later in the routine. If the pattern isn't UTF-8, we only need
3601 * to fold if in a UTF-8 locale, and then only the Sharp S; everything
3602 * else is 1-1 and isn't assumed to be folded. In a UTF-8 pattern, we
3603 * need to fold as many characters as a single character can fold to,
3604 * so that later we can check if the first ones are such a multi-char
3605 * fold. But, in such a pattern only locale-problematic characters
3606 * aren't folded, so we can skip this completely if the first character
3607 * in the node isn't one of the tricky ones */
3608 if (OP(text_node) == EXACTFL) {
3610 if (! is_utf8_pat) {
3611 if (IN_UTF8_CTYPE_LOCALE && *pat == LATIN_SMALL_LETTER_SHARP_S)
3613 folded[0] = folded[1] = 's';
3615 pat_end = folded + 2;
3618 else if (is_PROBLEMATIC_LOCALE_FOLDEDS_START_utf8(pat)) {
3623 for (i = 0; i < UTF8_MAX_FOLD_CHAR_EXPAND && s < pat_end; i++) {
3625 *(d++) = (U8) toFOLD_LC(*s);
3630 _to_utf8_fold_flags(s,
3633 FOLD_FLAGS_FULL | FOLD_FLAGS_LOCALE);
3644 if ((is_utf8_pat && is_MULTI_CHAR_FOLD_utf8(pat))
3645 || (!is_utf8_pat && is_MULTI_CHAR_FOLD_latin1(pat)))
3647 /* Multi-character folds require more context to sort out. Also
3648 * PL_utf8_foldclosures used below doesn't handle them, so have to
3649 * be handled outside this routine */
3650 use_chrtest_void = TRUE;
3652 else { /* an EXACTFish node which doesn't begin with a multi-char fold */
3653 c1 = is_utf8_pat ? valid_utf8_to_uvchr(pat, NULL) : *pat;
3655 /* Load the folds hash, if not already done */
3657 if (! PL_utf8_foldclosures) {
3658 if (! PL_utf8_tofold) {
3659 U8 dummy[UTF8_MAXBYTES_CASE+1];
3661 /* Force loading this by folding an above-Latin1 char */
3662 to_utf8_fold((U8*) HYPHEN_UTF8, dummy, NULL);
3663 assert(PL_utf8_tofold); /* Verify that worked */
3665 PL_utf8_foldclosures = _swash_inversion_hash(PL_utf8_tofold);
3668 /* The fold closures data structure is a hash with the keys
3669 * being the UTF-8 of every character that is folded to, like
3670 * 'k', and the values each an array of all code points that
3671 * fold to its key. e.g. [ 'k', 'K', KELVIN_SIGN ].
3672 * Multi-character folds are not included */
3673 if ((! (listp = hv_fetch(PL_utf8_foldclosures,
3678 /* Not found in the hash, therefore there are no folds
3679 * containing it, so there is only a single character that
3683 else { /* Does participate in folds */
3684 AV* list = (AV*) *listp;
3685 if (av_len(list) != 1) {
3687 /* If there aren't exactly two folds to this, it is
3688 * outside the scope of this function */
3689 use_chrtest_void = TRUE;
3691 else { /* There are two. Get them */
3692 SV** c_p = av_fetch(list, 0, FALSE);
3694 Perl_croak(aTHX_ "panic: invalid PL_utf8_foldclosures structure");
3698 c_p = av_fetch(list, 1, FALSE);
3700 Perl_croak(aTHX_ "panic: invalid PL_utf8_foldclosures structure");
3704 /* Folds that cross the 255/256 boundary are forbidden
3705 * if EXACTFL (and isnt a UTF8 locale), or EXACTFA and
3706 * one is ASCIII. Since the pattern character is above
3707 * 256, and its only other match is below 256, the only
3708 * legal match will be to itself. We have thrown away
3709 * the original, so have to compute which is the one
3711 if ((c1 < 256) != (c2 < 256)) {
3712 if ((OP(text_node) == EXACTFL
3713 && ! IN_UTF8_CTYPE_LOCALE)
3714 || ((OP(text_node) == EXACTFA
3715 || OP(text_node) == EXACTFA_NO_TRIE)
3716 && (isASCII(c1) || isASCII(c2))))
3729 else /* Here, c1 is < 255 */
3731 && HAS_NONLATIN1_FOLD_CLOSURE(c1)
3732 && ( ! (OP(text_node) == EXACTFL && ! IN_UTF8_CTYPE_LOCALE))
3733 && ((OP(text_node) != EXACTFA
3734 && OP(text_node) != EXACTFA_NO_TRIE)
3737 /* Here, there could be something above Latin1 in the target
3738 * which folds to this character in the pattern. All such
3739 * cases except LATIN SMALL LETTER Y WITH DIAERESIS have more
3740 * than two characters involved in their folds, so are outside
3741 * the scope of this function */
3742 if (UNLIKELY(c1 == LATIN_SMALL_LETTER_Y_WITH_DIAERESIS)) {
3743 c2 = LATIN_CAPITAL_LETTER_Y_WITH_DIAERESIS;
3746 use_chrtest_void = TRUE;
3749 else { /* Here nothing above Latin1 can fold to the pattern
3751 switch (OP(text_node)) {
3753 case EXACTFL: /* /l rules */
3754 c2 = PL_fold_locale[c1];
3757 case EXACTF: /* This node only generated for non-utf8
3759 assert(! is_utf8_pat);
3760 if (! utf8_target) { /* /d rules */
3765 /* /u rules for all these. This happens to work for
3766 * EXACTFA as nothing in Latin1 folds to ASCII */
3767 case EXACTFA_NO_TRIE: /* This node only generated for
3768 non-utf8 patterns */
3769 assert(! is_utf8_pat);
3774 c2 = PL_fold_latin1[c1];
3778 Perl_croak(aTHX_ "panic: Unexpected op %u", OP(text_node));
3779 assert(0); /* NOTREACHED */
3785 /* Here have figured things out. Set up the returns */
3786 if (use_chrtest_void) {
3787 *c2p = *c1p = CHRTEST_VOID;
3789 else if (utf8_target) {
3790 if (! utf8_has_been_setup) { /* Don't have the utf8; must get it */
3791 uvchr_to_utf8(c1_utf8, c1);
3792 uvchr_to_utf8(c2_utf8, c2);
3795 /* Invariants are stored in both the utf8 and byte outputs; Use
3796 * negative numbers otherwise for the byte ones. Make sure that the
3797 * byte ones are the same iff the utf8 ones are the same */
3798 *c1p = (UTF8_IS_INVARIANT(*c1_utf8)) ? *c1_utf8 : CHRTEST_NOT_A_CP_1;
3799 *c2p = (UTF8_IS_INVARIANT(*c2_utf8))
3802 ? CHRTEST_NOT_A_CP_1
3803 : CHRTEST_NOT_A_CP_2;
3805 else if (c1 > 255) {
3806 if (c2 > 255) { /* both possibilities are above what a non-utf8 string
3811 *c1p = *c2p = c2; /* c2 is the only representable value */
3813 else { /* c1 is representable; see about c2 */
3815 *c2p = (c2 < 256) ? c2 : c1;
3821 /* returns -1 on failure, $+[0] on success */
3823 S_regmatch(pTHX_ regmatch_info *reginfo, char *startpos, regnode *prog)
3825 #if PERL_VERSION < 9 && !defined(PERL_CORE)
3829 const bool utf8_target = reginfo->is_utf8_target;
3830 const U32 uniflags = UTF8_ALLOW_DEFAULT;
3831 REGEXP *rex_sv = reginfo->prog;
3832 regexp *rex = ReANY(rex_sv);
3833 RXi_GET_DECL(rex,rexi);
3834 /* the current state. This is a cached copy of PL_regmatch_state */
3836 /* cache heavy used fields of st in registers */
3839 U32 n = 0; /* general value; init to avoid compiler warning */
3840 SSize_t ln = 0; /* len or last; init to avoid compiler warning */
3841 char *locinput = startpos;
3842 char *pushinput; /* where to continue after a PUSH */
3843 I32 nextchr; /* is always set to UCHARAT(locinput) */
3845 bool result = 0; /* return value of S_regmatch */
3846 int depth = 0; /* depth of backtrack stack */
3847 U32 nochange_depth = 0; /* depth of GOSUB recursion with nochange */
3848 const U32 max_nochange_depth =
3849 (3 * rex->nparens > MAX_RECURSE_EVAL_NOCHANGE_DEPTH) ?
3850 3 * rex->nparens : MAX_RECURSE_EVAL_NOCHANGE_DEPTH;
3851 regmatch_state *yes_state = NULL; /* state to pop to on success of
3853 /* mark_state piggy backs on the yes_state logic so that when we unwind
3854 the stack on success we can update the mark_state as we go */
3855 regmatch_state *mark_state = NULL; /* last mark state we have seen */
3856 regmatch_state *cur_eval = NULL; /* most recent EVAL_AB state */
3857 struct regmatch_state *cur_curlyx = NULL; /* most recent curlyx */
3859 bool no_final = 0; /* prevent failure from backtracking? */
3860 bool do_cutgroup = 0; /* no_final only until next branch/trie entry */
3861 char *startpoint = locinput;
3862 SV *popmark = NULL; /* are we looking for a mark? */
3863 SV *sv_commit = NULL; /* last mark name seen in failure */
3864 SV *sv_yes_mark = NULL; /* last mark name we have seen
3865 during a successful match */
3866 U32 lastopen = 0; /* last open we saw */
3867 bool has_cutgroup = RX_HAS_CUTGROUP(rex) ? 1 : 0;
3868 SV* const oreplsv = GvSVn(PL_replgv);
3869 /* these three flags are set by various ops to signal information to
3870 * the very next op. They have a useful lifetime of exactly one loop
3871 * iteration, and are not preserved or restored by state pushes/pops
3873 bool sw = 0; /* the condition value in (?(cond)a|b) */
3874 bool minmod = 0; /* the next "{n,m}" is a "{n,m}?" */
3875 int logical = 0; /* the following EVAL is:
3879 or the following IFMATCH/UNLESSM is:
3880 false: plain (?=foo)
3881 true: used as a condition: (?(?=foo))
3883 PAD* last_pad = NULL;
3885 I32 gimme = G_SCALAR;
3886 CV *caller_cv = NULL; /* who called us */
3887 CV *last_pushed_cv = NULL; /* most recently called (?{}) CV */
3888 CHECKPOINT runops_cp; /* savestack position before executing EVAL */
3889 U32 maxopenparen = 0; /* max '(' index seen so far */
3890 int to_complement; /* Invert the result? */
3891 _char_class_number classnum;
3892 bool is_utf8_pat = reginfo->is_utf8_pat;
3895 GET_RE_DEBUG_FLAGS_DECL;
3898 /* protect against undef(*^R) */
3899 SAVEFREESV(SvREFCNT_inc_simple_NN(oreplsv));
3901 /* shut up 'may be used uninitialized' compiler warnings for dMULTICALL */
3902 multicall_oldcatch = 0;
3903 multicall_cv = NULL;
3905 PERL_UNUSED_VAR(multicall_cop);
3906 PERL_UNUSED_VAR(newsp);
3909 PERL_ARGS_ASSERT_REGMATCH;
3911 DEBUG_OPTIMISE_r( DEBUG_EXECUTE_r({
3912 PerlIO_printf(Perl_debug_log,"regmatch start\n");
3915 st = PL_regmatch_state;
3917 /* Note that nextchr is a byte even in UTF */
3920 while (scan != NULL) {
3923 SV * const prop = sv_newmortal();
3924 regnode *rnext=regnext(scan);
3925 DUMP_EXEC_POS( locinput, scan, utf8_target );
3926 regprop(rex, prop, scan);
3928 PerlIO_printf(Perl_debug_log,
3929 "%3"IVdf":%*s%s(%"IVdf")\n",
3930 (IV)(scan - rexi->program), depth*2, "",
3932 (PL_regkind[OP(scan)] == END || !rnext) ?
3933 0 : (IV)(rnext - rexi->program));
3936 next = scan + NEXT_OFF(scan);
3939 state_num = OP(scan);
3945 assert(nextchr < 256 && (nextchr >= 0 || nextchr == NEXTCHR_EOS));
3947 switch (state_num) {
3948 case BOL: /* /^../ */
3949 if (locinput == reginfo->strbeg)
3953 case MBOL: /* /^../m */
3954 if (locinput == reginfo->strbeg ||
3955 (!NEXTCHR_IS_EOS && locinput[-1] == '\n'))
3961 case SBOL: /* /^../s */
3962 if (locinput == reginfo->strbeg)
3967 if (locinput == reginfo->ganch)
3971 case KEEPS: /* \K */
3972 /* update the startpoint */
3973 st->u.keeper.val = rex->offs[0].start;
3974 rex->offs[0].start = locinput - reginfo->strbeg;
3975 PUSH_STATE_GOTO(KEEPS_next, next, locinput);
3976 assert(0); /*NOTREACHED*/
3977 case KEEPS_next_fail:
3978 /* rollback the start point change */
3979 rex->offs[0].start = st->u.keeper.val;
3981 assert(0); /*NOTREACHED*/
3983 case MEOL: /* /..$/m */
3984 if (!NEXTCHR_IS_EOS && nextchr != '\n')
3988 case EOL: /* /..$/ */
3990 case SEOL: /* /..$/s */
3991 if (!NEXTCHR_IS_EOS && nextchr != '\n')
3993 if (reginfo->strend - locinput > 1)
3998 if (!NEXTCHR_IS_EOS)
4002 case SANY: /* /./s */
4005 goto increment_locinput;
4013 case REG_ANY: /* /./ */
4014 if ((NEXTCHR_IS_EOS) || nextchr == '\n')
4016 goto increment_locinput;
4020 #define ST st->u.trie
4021 case TRIEC: /* (ab|cd) with known charclass */
4022 /* In this case the charclass data is available inline so
4023 we can fail fast without a lot of extra overhead.
4025 if(!NEXTCHR_IS_EOS && !ANYOF_BITMAP_TEST(scan, nextchr)) {
4027 PerlIO_printf(Perl_debug_log,
4028 "%*s %sfailed to match trie start class...%s\n",
4029 REPORT_CODE_OFF+depth*2, "", PL_colors[4], PL_colors[5])
4032 assert(0); /* NOTREACHED */
4035 case TRIE: /* (ab|cd) */
4036 /* the basic plan of execution of the trie is:
4037 * At the beginning, run though all the states, and
4038 * find the longest-matching word. Also remember the position
4039 * of the shortest matching word. For example, this pattern:
4042 * when matched against the string "abcde", will generate
4043 * accept states for all words except 3, with the longest
4044 * matching word being 4, and the shortest being 2 (with
4045 * the position being after char 1 of the string).
4047 * Then for each matching word, in word order (i.e. 1,2,4,5),
4048 * we run the remainder of the pattern; on each try setting
4049 * the current position to the character following the word,
4050 * returning to try the next word on failure.
4052 * We avoid having to build a list of words at runtime by
4053 * using a compile-time structure, wordinfo[].prev, which
4054 * gives, for each word, the previous accepting word (if any).
4055 * In the case above it would contain the mappings 1->2, 2->0,
4056 * 3->0, 4->5, 5->1. We can use this table to generate, from
4057 * the longest word (4 above), a list of all words, by
4058 * following the list of prev pointers; this gives us the
4059 * unordered list 4,5,1,2. Then given the current word we have
4060 * just tried, we can go through the list and find the
4061 * next-biggest word to try (so if we just failed on word 2,
4062 * the next in the list is 4).
4064 * Since at runtime we don't record the matching position in
4065 * the string for each word, we have to work that out for
4066 * each word we're about to process. The wordinfo table holds
4067 * the character length of each word; given that we recorded
4068 * at the start: the position of the shortest word and its
4069 * length in chars, we just need to move the pointer the
4070 * difference between the two char lengths. Depending on
4071 * Unicode status and folding, that's cheap or expensive.
4073 * This algorithm is optimised for the case where are only a
4074 * small number of accept states, i.e. 0,1, or maybe 2.
4075 * With lots of accepts states, and having to try all of them,
4076 * it becomes quadratic on number of accept states to find all
4081 /* what type of TRIE am I? (utf8 makes this contextual) */
4082 DECL_TRIE_TYPE(scan);
4084 /* what trie are we using right now */
4085 reg_trie_data * const trie
4086 = (reg_trie_data*)rexi->data->data[ ARG( scan ) ];
4087 HV * widecharmap = MUTABLE_HV(rexi->data->data[ ARG( scan ) + 1 ]);
4088 U32 state = trie->startstate;
4091 && (NEXTCHR_IS_EOS || !TRIE_BITMAP_TEST(trie, nextchr)))
4093 if (trie->states[ state ].wordnum) {
4095 PerlIO_printf(Perl_debug_log,
4096 "%*s %smatched empty string...%s\n",
4097 REPORT_CODE_OFF+depth*2, "", PL_colors[4], PL_colors[5])
4103 PerlIO_printf(Perl_debug_log,
4104 "%*s %sfailed to match trie start class...%s\n",
4105 REPORT_CODE_OFF+depth*2, "", PL_colors[4], PL_colors[5])
4112 U8 *uc = ( U8* )locinput;
4116 U8 *uscan = (U8*)NULL;
4117 U8 foldbuf[ UTF8_MAXBYTES_CASE + 1 ];
4118 U32 charcount = 0; /* how many input chars we have matched */
4119 U32 accepted = 0; /* have we seen any accepting states? */
4121 ST.jump = trie->jump;
4124 ST.longfold = FALSE; /* char longer if folded => it's harder */
4127 /* fully traverse the TRIE; note the position of the
4128 shortest accept state and the wordnum of the longest
4131 while ( state && uc <= (U8*)(reginfo->strend) ) {
4132 U32 base = trie->states[ state ].trans.base;
4136 wordnum = trie->states[ state ].wordnum;
4138 if (wordnum) { /* it's an accept state */
4141 /* record first match position */
4143 ST.firstpos = (U8*)locinput;
4148 ST.firstchars = charcount;
4151 if (!ST.nextword || wordnum < ST.nextword)
4152 ST.nextword = wordnum;
4153 ST.topword = wordnum;
4156 DEBUG_TRIE_EXECUTE_r({
4157 DUMP_EXEC_POS( (char *)uc, scan, utf8_target );
4158 PerlIO_printf( Perl_debug_log,
4159 "%*s %sState: %4"UVxf" Accepted: %c ",
4160 2+depth * 2, "", PL_colors[4],
4161 (UV)state, (accepted ? 'Y' : 'N'));
4164 /* read a char and goto next state */
4165 if ( base && (foldlen || uc < (U8*)(reginfo->strend))) {
4167 REXEC_TRIE_READ_CHAR(trie_type, trie, widecharmap, uc,
4168 uscan, len, uvc, charid, foldlen,
4175 base + charid - 1 - trie->uniquecharcount)) >= 0)
4177 && ((U32)offset < trie->lasttrans)
4178 && trie->trans[offset].check == state)
4180 state = trie->trans[offset].next;
4191 DEBUG_TRIE_EXECUTE_r(
4192 PerlIO_printf( Perl_debug_log,
4193 "Charid:%3x CP:%4"UVxf" After State: %4"UVxf"%s\n",
4194 charid, uvc, (UV)state, PL_colors[5] );
4200 /* calculate total number of accept states */
4205 w = trie->wordinfo[w].prev;
4208 ST.accepted = accepted;
4212 PerlIO_printf( Perl_debug_log,
4213 "%*s %sgot %"IVdf" possible matches%s\n",
4214 REPORT_CODE_OFF + depth * 2, "",
4215 PL_colors[4], (IV)ST.accepted, PL_colors[5] );
4217 goto trie_first_try; /* jump into the fail handler */
4219 assert(0); /* NOTREACHED */
4221 case TRIE_next_fail: /* we failed - try next alternative */
4225 REGCP_UNWIND(ST.cp);
4226 UNWIND_PAREN(ST.lastparen, ST.lastcloseparen);
4228 if (!--ST.accepted) {
4230 PerlIO_printf( Perl_debug_log,
4231 "%*s %sTRIE failed...%s\n",
4232 REPORT_CODE_OFF+depth*2, "",
4239 /* Find next-highest word to process. Note that this code
4240 * is O(N^2) per trie run (O(N) per branch), so keep tight */
4243 U16 const nextword = ST.nextword;
4244 reg_trie_wordinfo * const wordinfo
4245 = ((reg_trie_data*)rexi->data->data[ARG(ST.me)])->wordinfo;
4246 for (word=ST.topword; word; word=wordinfo[word].prev) {
4247 if (word > nextword && (!min || word < min))
4260 ST.lastparen = rex->lastparen;
4261 ST.lastcloseparen = rex->lastcloseparen;
4265 /* find start char of end of current word */
4267 U32 chars; /* how many chars to skip */
4268 reg_trie_data * const trie
4269 = (reg_trie_data*)rexi->data->data[ARG(ST.me)];
4271 assert((trie->wordinfo[ST.nextword].len - trie->prefixlen)
4273 chars = (trie->wordinfo[ST.nextword].len - trie->prefixlen)
4278 /* the hard option - fold each char in turn and find
4279 * its folded length (which may be different */
4280 U8 foldbuf[UTF8_MAXBYTES_CASE + 1];
4288 uvc = utf8n_to_uvchr((U8*)uc, UTF8_MAXLEN, &len,
4296 uvc = to_uni_fold(uvc, foldbuf, &foldlen);
4301 uvc = utf8n_to_uvchr(uscan, UTF8_MAXLEN, &len,
4317 scan = ST.me + ((ST.jump && ST.jump[ST.nextword])
4318 ? ST.jump[ST.nextword]
4322 PerlIO_printf( Perl_debug_log,
4323 "%*s %sTRIE matched word #%d, continuing%s\n",
4324 REPORT_CODE_OFF+depth*2, "",
4331 if (ST.accepted > 1 || has_cutgroup) {
4332 PUSH_STATE_GOTO(TRIE_next, scan, (char*)uc);
4333 assert(0); /* NOTREACHED */
4335 /* only one choice left - just continue */
4337 AV *const trie_words
4338 = MUTABLE_AV(rexi->data->data[ARG(ST.me)+TRIE_WORDS_OFFSET]);
4339 SV ** const tmp = av_fetch( trie_words,
4341 SV *sv= tmp ? sv_newmortal() : NULL;
4343 PerlIO_printf( Perl_debug_log,
4344 "%*s %sonly one match left, short-circuiting: #%d <%s>%s\n",
4345 REPORT_CODE_OFF+depth*2, "", PL_colors[4],
4347 tmp ? pv_pretty(sv, SvPV_nolen_const(*tmp), SvCUR(*tmp), 0,
4348 PL_colors[0], PL_colors[1],
4349 (SvUTF8(*tmp) ? PERL_PV_ESCAPE_UNI : 0)|PERL_PV_ESCAPE_NONASCII
4351 : "not compiled under -Dr",
4355 locinput = (char*)uc;
4356 continue; /* execute rest of RE */
4357 assert(0); /* NOTREACHED */
4361 case EXACT: { /* /abc/ */
4362 char *s = STRING(scan);
4364 if (utf8_target != is_utf8_pat) {
4365 /* The target and the pattern have differing utf8ness. */
4367 const char * const e = s + ln;
4370 /* The target is utf8, the pattern is not utf8.
4371 * Above-Latin1 code points can't match the pattern;
4372 * invariants match exactly, and the other Latin1 ones need
4373 * to be downgraded to a single byte in order to do the
4374 * comparison. (If we could be confident that the target
4375 * is not malformed, this could be refactored to have fewer
4376 * tests by just assuming that if the first bytes match, it
4377 * is an invariant, but there are tests in the test suite
4378 * dealing with (??{...}) which violate this) */
4380 if (l >= reginfo->strend
4381 || UTF8_IS_ABOVE_LATIN1(* (U8*) l))
4385 if (UTF8_IS_INVARIANT(*(U8*)l)) {
4392 if (TWO_BYTE_UTF8_TO_NATIVE(*l, *(l+1)) != * (U8*) s)
4402 /* The target is not utf8, the pattern is utf8. */
4404 if (l >= reginfo->strend
4405 || UTF8_IS_ABOVE_LATIN1(* (U8*) s))
4409 if (UTF8_IS_INVARIANT(*(U8*)s)) {
4416 if (TWO_BYTE_UTF8_TO_NATIVE(*s, *(s+1)) != * (U8*) l)
4428 /* The target and the pattern have the same utf8ness. */
4429 /* Inline the first character, for speed. */
4430 if (reginfo->strend - locinput < ln
4431 || UCHARAT(s) != nextchr
4432 || (ln > 1 && memNE(s, locinput, ln)))
4441 case EXACTFL: { /* /abc/il */
4443 const U8 * fold_array;
4445 U32 fold_utf8_flags;
4447 RX_MATCH_TAINTED_on(reginfo->prog);
4448 folder = foldEQ_locale;
4449 fold_array = PL_fold_locale;
4450 fold_utf8_flags = FOLDEQ_LOCALE;
4453 case EXACTFU_SS: /* /\x{df}/iu */
4454 case EXACTFU: /* /abc/iu */
4455 folder = foldEQ_latin1;
4456 fold_array = PL_fold_latin1;
4457 fold_utf8_flags = is_utf8_pat ? FOLDEQ_S1_ALREADY_FOLDED : 0;
4460 case EXACTFA_NO_TRIE: /* This node only generated for non-utf8
4462 assert(! is_utf8_pat);
4464 case EXACTFA: /* /abc/iaa */
4465 folder = foldEQ_latin1;
4466 fold_array = PL_fold_latin1;
4467 fold_utf8_flags = FOLDEQ_UTF8_NOMIX_ASCII;
4470 case EXACTF: /* /abc/i This node only generated for
4471 non-utf8 patterns */
4472 assert(! is_utf8_pat);
4474 fold_array = PL_fold;
4475 fold_utf8_flags = 0;
4483 || state_num == EXACTFU_SS
4484 || (state_num == EXACTFL && IN_UTF8_CTYPE_LOCALE))
4486 /* Either target or the pattern are utf8, or has the issue where
4487 * the fold lengths may differ. */
4488 const char * const l = locinput;
4489 char *e = reginfo->strend;
4491 if (! foldEQ_utf8_flags(s, 0, ln, is_utf8_pat,
4492 l, &e, 0, utf8_target, fold_utf8_flags))
4500 /* Neither the target nor the pattern are utf8 */
4501 if (UCHARAT(s) != nextchr
4503 && UCHARAT(s) != fold_array[nextchr])
4507 if (reginfo->strend - locinput < ln)
4509 if (ln > 1 && ! folder(s, locinput, ln))
4515 /* XXX Could improve efficiency by separating these all out using a
4516 * macro or in-line function. At that point regcomp.c would no longer
4517 * have to set the FLAGS fields of these */
4518 case BOUNDL: /* /\b/l */
4519 case NBOUNDL: /* /\B/l */
4520 RX_MATCH_TAINTED_on(reginfo->prog);
4522 case BOUND: /* /\b/ */
4523 case BOUNDU: /* /\b/u */
4524 case BOUNDA: /* /\b/a */
4525 case NBOUND: /* /\B/ */
4526 case NBOUNDU: /* /\B/u */
4527 case NBOUNDA: /* /\B/a */
4528 /* was last char in word? */
4530 && FLAGS(scan) != REGEX_ASCII_RESTRICTED_CHARSET
4531 && FLAGS(scan) != REGEX_ASCII_MORE_RESTRICTED_CHARSET)
4533 if (locinput == reginfo->strbeg)
4536 const U8 * const r =
4537 reghop3((U8*)locinput, -1, (U8*)(reginfo->strbeg));
4539 ln = utf8n_to_uvchr(r, (U8*) reginfo->strend - r,
4542 if (FLAGS(scan) != REGEX_LOCALE_CHARSET) {
4543 ln = isWORDCHAR_uni(ln);
4547 LOAD_UTF8_CHARCLASS_ALNUM();
4548 n = swash_fetch(PL_utf8_swash_ptrs[_CC_WORDCHAR], (U8*)locinput,
4553 ln = isWORDCHAR_LC_uvchr(ln);
4554 n = NEXTCHR_IS_EOS ? 0 : isWORDCHAR_LC_utf8((U8*)locinput);
4559 /* Here the string isn't utf8, or is utf8 and only ascii
4560 * characters are to match \w. In the latter case looking at
4561 * the byte just prior to the current one may be just the final
4562 * byte of a multi-byte character. This is ok. There are two
4564 * 1) it is a single byte character, and then the test is doing
4565 * just what it's supposed to.
4566 * 2) it is a multi-byte character, in which case the final
4567 * byte is never mistakable for ASCII, and so the test
4568 * will say it is not a word character, which is the
4569 * correct answer. */
4570 ln = (locinput != reginfo->strbeg) ?
4571 UCHARAT(locinput - 1) : '\n';
4572 switch (FLAGS(scan)) {
4573 case REGEX_UNICODE_CHARSET:
4574 ln = isWORDCHAR_L1(ln);
4575 n = NEXTCHR_IS_EOS ? 0 : isWORDCHAR_L1(nextchr);
4577 case REGEX_LOCALE_CHARSET:
4578 ln = isWORDCHAR_LC(ln);
4579 n = NEXTCHR_IS_EOS ? 0 : isWORDCHAR_LC(nextchr);
4581 case REGEX_DEPENDS_CHARSET:
4582 ln = isWORDCHAR(ln);
4583 n = NEXTCHR_IS_EOS ? 0 : isWORDCHAR(nextchr);
4585 case REGEX_ASCII_RESTRICTED_CHARSET:
4586 case REGEX_ASCII_MORE_RESTRICTED_CHARSET:
4587 ln = isWORDCHAR_A(ln);
4588 n = NEXTCHR_IS_EOS ? 0 : isWORDCHAR_A(nextchr);
4591 Perl_croak(aTHX_ "panic: Unexpected FLAGS %u in op %u", FLAGS(scan), OP(scan));
4595 /* Note requires that all BOUNDs be lower than all NBOUNDs in
4597 if (((!ln) == (!n)) == (OP(scan) < NBOUND))
4601 case ANYOF: /* /[abc]/ */
4605 if (!reginclass(rex, scan, (U8*)locinput, (U8*)reginfo->strend,
4608 locinput += UTF8SKIP(locinput);
4611 if (!REGINCLASS(rex, scan, (U8*)locinput))
4617 /* The argument (FLAGS) to all the POSIX node types is the class number
4620 case NPOSIXL: /* \W or [:^punct:] etc. under /l */
4624 case POSIXL: /* \w or [:punct:] etc. under /l */
4628 /* The locale hasn't influenced the outcome before this, so defer
4629 * tainting until now */
4630 RX_MATCH_TAINTED_on(reginfo->prog);
4632 /* Use isFOO_lc() for characters within Latin1. (Note that
4633 * UTF8_IS_INVARIANT works even on non-UTF-8 strings, or else
4634 * wouldn't be invariant) */
4635 if (UTF8_IS_INVARIANT(nextchr) || ! utf8_target) {
4636 if (! (to_complement ^ cBOOL(isFOO_lc(FLAGS(scan), (U8) nextchr)))) {
4640 else if (UTF8_IS_DOWNGRADEABLE_START(nextchr)) {
4641 if (! (to_complement ^ cBOOL(isFOO_lc(FLAGS(scan),
4642 (U8) TWO_BYTE_UTF8_TO_NATIVE(nextchr,
4643 *(locinput + 1))))))
4648 else { /* Here, must be an above Latin-1 code point */
4649 goto utf8_posix_not_eos;
4652 /* Here, must be utf8 */
4653 locinput += UTF8SKIP(locinput);
4656 case NPOSIXD: /* \W or [:^punct:] etc. under /d */
4660 case POSIXD: /* \w or [:punct:] etc. under /d */
4666 case NPOSIXA: /* \W or [:^punct:] etc. under /a */
4668 if (NEXTCHR_IS_EOS) {
4672 /* All UTF-8 variants match */
4673 if (! UTF8_IS_INVARIANT(nextchr)) {
4674 goto increment_locinput;
4680 case POSIXA: /* \w or [:punct:] etc. under /a */
4683 /* We get here through POSIXD, NPOSIXD, and NPOSIXA when not in
4684 * UTF-8, and also from NPOSIXA even in UTF-8 when the current
4685 * character is a single byte */
4688 || ! (to_complement ^ cBOOL(_generic_isCC_A(nextchr,
4694 /* Here we are either not in utf8, or we matched a utf8-invariant,
4695 * so the next char is the next byte */
4699 case NPOSIXU: /* \W or [:^punct:] etc. under /u */
4703 case POSIXU: /* \w or [:punct:] etc. under /u */
4705 if (NEXTCHR_IS_EOS) {
4710 /* Use _generic_isCC() for characters within Latin1. (Note that
4711 * UTF8_IS_INVARIANT works even on non-UTF-8 strings, or else
4712 * wouldn't be invariant) */
4713 if (UTF8_IS_INVARIANT(nextchr) || ! utf8_target) {
4714 if (! (to_complement ^ cBOOL(_generic_isCC(nextchr,
4721 else if (UTF8_IS_DOWNGRADEABLE_START(nextchr)) {
4722 if (! (to_complement
4723 ^ cBOOL(_generic_isCC(TWO_BYTE_UTF8_TO_NATIVE(nextchr,
4731 else { /* Handle above Latin-1 code points */
4732 classnum = (_char_class_number) FLAGS(scan);
4733 if (classnum < _FIRST_NON_SWASH_CC) {
4735 /* Here, uses a swash to find such code points. Load if if
4736 * not done already */
4737 if (! PL_utf8_swash_ptrs[classnum]) {
4738 U8 flags = _CORE_SWASH_INIT_ACCEPT_INVLIST;
4739 PL_utf8_swash_ptrs[classnum]
4740 = _core_swash_init("utf8",
4743 PL_XPosix_ptrs[classnum], &flags);
4745 if (! (to_complement
4746 ^ cBOOL(swash_fetch(PL_utf8_swash_ptrs[classnum],
4747 (U8 *) locinput, TRUE))))
4752 else { /* Here, uses macros to find above Latin-1 code points */
4754 case _CC_ENUM_SPACE: /* XXX would require separate
4755 code if we revert the change
4756 of \v matching this */
4757 case _CC_ENUM_PSXSPC:
4758 if (! (to_complement
4759 ^ cBOOL(is_XPERLSPACE_high(locinput))))
4764 case _CC_ENUM_BLANK:
4765 if (! (to_complement
4766 ^ cBOOL(is_HORIZWS_high(locinput))))
4771 case _CC_ENUM_XDIGIT:
4772 if (! (to_complement
4773 ^ cBOOL(is_XDIGIT_high(locinput))))
4778 case _CC_ENUM_VERTSPACE:
4779 if (! (to_complement
4780 ^ cBOOL(is_VERTWS_high(locinput))))
4785 default: /* The rest, e.g. [:cntrl:], can't match
4787 if (! to_complement) {
4793 locinput += UTF8SKIP(locinput);
4797 case CLUMP: /* Match \X: logical Unicode character. This is defined as
4798 a Unicode extended Grapheme Cluster */
4799 /* From http://www.unicode.org/reports/tr29 (5.2 version). An
4800 extended Grapheme Cluster is:
4803 | Prepend* Begin Extend*
4806 Begin is: ( Special_Begin | ! Control )
4807 Special_Begin is: ( Regional-Indicator+ | Hangul-syllable )
4808 Extend is: ( Grapheme_Extend | Spacing_Mark )
4809 Control is: [ GCB_Control | CR | LF ]
4810 Hangul-syllable is: ( T+ | ( L* ( L | ( LVT | ( V | LV ) V* ) T* ) ))
4812 If we create a 'Regular_Begin' = Begin - Special_Begin, then
4815 Begin is ( Regular_Begin + Special Begin )
4817 It turns out that 98.4% of all Unicode code points match
4818 Regular_Begin. Doing it this way eliminates a table match in
4819 the previous implementation for almost all Unicode code points.
4821 There is a subtlety with Prepend* which showed up in testing.
4822 Note that the Begin, and only the Begin is required in:
4823 | Prepend* Begin Extend*
4824 Also, Begin contains '! Control'. A Prepend must be a
4825 '! Control', which means it must also be a Begin. What it
4826 comes down to is that if we match Prepend* and then find no
4827 suitable Begin afterwards, that if we backtrack the last
4828 Prepend, that one will be a suitable Begin.
4833 if (! utf8_target) {
4835 /* Match either CR LF or '.', as all the other possibilities
4837 locinput++; /* Match the . or CR */
4838 if (nextchr == '\r' /* And if it was CR, and the next is LF,
4840 && locinput < reginfo->strend
4841 && UCHARAT(locinput) == '\n')
4848 /* Utf8: See if is ( CR LF ); already know that locinput <
4849 * reginfo->strend, so locinput+1 is in bounds */
4850 if ( nextchr == '\r' && locinput+1 < reginfo->strend
4851 && UCHARAT(locinput + 1) == '\n')
4858 /* In case have to backtrack to beginning, then match '.' */
4859 char *starting = locinput;
4861 /* In case have to backtrack the last prepend */
4862 char *previous_prepend = NULL;
4864 LOAD_UTF8_CHARCLASS_GCB();
4866 /* Match (prepend)* */
4867 while (locinput < reginfo->strend
4868 && (len = is_GCB_Prepend_utf8(locinput)))
4870 previous_prepend = locinput;
4874 /* As noted above, if we matched a prepend character, but
4875 * the next thing won't match, back off the last prepend we
4876 * matched, as it is guaranteed to match the begin */
4877 if (previous_prepend
4878 && (locinput >= reginfo->strend
4879 || (! swash_fetch(PL_utf8_X_regular_begin,
4880 (U8*)locinput, utf8_target)
4881 && ! is_GCB_SPECIAL_BEGIN_START_utf8(locinput)))
4884 locinput = previous_prepend;
4887 /* Note that here we know reginfo->strend > locinput, as we
4888 * tested that upon input to this switch case, and if we
4889 * moved locinput forward, we tested the result just above
4890 * and it either passed, or we backed off so that it will
4892 if (swash_fetch(PL_utf8_X_regular_begin,
4893 (U8*)locinput, utf8_target)) {
4894 locinput += UTF8SKIP(locinput);
4896 else if (! is_GCB_SPECIAL_BEGIN_START_utf8(locinput)) {
4898 /* Here did not match the required 'Begin' in the
4899 * second term. So just match the very first
4900 * character, the '.' of the final term of the regex */
4901 locinput = starting + UTF8SKIP(starting);
4905 /* Here is a special begin. It can be composed of
4906 * several individual characters. One possibility is
4908 if ((len = is_GCB_RI_utf8(locinput))) {
4910 while (locinput < reginfo->strend
4911 && (len = is_GCB_RI_utf8(locinput)))
4915 } else if ((len = is_GCB_T_utf8(locinput))) {
4916 /* Another possibility is T+ */
4918 while (locinput < reginfo->strend
4919 && (len = is_GCB_T_utf8(locinput)))
4925 /* Here, neither RI+ nor T+; must be some other
4926 * Hangul. That means it is one of the others: L,
4927 * LV, LVT or V, and matches:
4928 * L* (L | LVT T* | V * V* T* | LV V* T*) */
4931 while (locinput < reginfo->strend
4932 && (len = is_GCB_L_utf8(locinput)))
4937 /* Here, have exhausted L*. If the next character
4938 * is not an LV, LVT nor V, it means we had to have
4939 * at least one L, so matches L+ in the original
4940 * equation, we have a complete hangul syllable.
4943 if (locinput < reginfo->strend
4944 && is_GCB_LV_LVT_V_utf8(locinput))
4946 /* Otherwise keep going. Must be LV, LVT or V.
4947 * See if LVT, by first ruling out V, then LV */
4948 if (! is_GCB_V_utf8(locinput)
4949 /* All but every TCount one is LV */
4950 && (valid_utf8_to_uvchr((U8 *) locinput,
4955 locinput += UTF8SKIP(locinput);
4958 /* Must be V or LV. Take it, then match
4960 locinput += UTF8SKIP(locinput);
4961 while (locinput < reginfo->strend
4962 && (len = is_GCB_V_utf8(locinput)))
4968 /* And any of LV, LVT, or V can be followed
4970 while (locinput < reginfo->strend
4971 && (len = is_GCB_T_utf8(locinput)))
4979 /* Match any extender */
4980 while (locinput < reginfo->strend
4981 && swash_fetch(PL_utf8_X_extend,
4982 (U8*)locinput, utf8_target))
4984 locinput += UTF8SKIP(locinput);
4988 if (locinput > reginfo->strend) sayNO;
4992 case NREFFL: /* /\g{name}/il */
4993 { /* The capture buffer cases. The ones beginning with N for the
4994 named buffers just convert to the equivalent numbered and
4995 pretend they were called as the corresponding numbered buffer
4997 /* don't initialize these in the declaration, it makes C++
5002 const U8 *fold_array;
5005 RX_MATCH_TAINTED_on(reginfo->prog);
5006 folder = foldEQ_locale;
5007 fold_array = PL_fold_locale;
5009 utf8_fold_flags = FOLDEQ_LOCALE;
5012 case NREFFA: /* /\g{name}/iaa */
5013 folder = foldEQ_latin1;
5014 fold_array = PL_fold_latin1;
5016 utf8_fold_flags = FOLDEQ_UTF8_NOMIX_ASCII;
5019 case NREFFU: /* /\g{name}/iu */
5020 folder = foldEQ_latin1;
5021 fold_array = PL_fold_latin1;
5023 utf8_fold_flags = 0;
5026 case NREFF: /* /\g{name}/i */
5028 fold_array = PL_fold;
5030 utf8_fold_flags = 0;
5033 case NREF: /* /\g{name}/ */
5037 utf8_fold_flags = 0;
5040 /* For the named back references, find the corresponding buffer
5042 n = reg_check_named_buff_matched(rex,scan);
5047 goto do_nref_ref_common;
5049 case REFFL: /* /\1/il */
5050 RX_MATCH_TAINTED_on(reginfo->prog);
5051 folder = foldEQ_locale;
5052 fold_array = PL_fold_locale;
5053 utf8_fold_flags = FOLDEQ_LOCALE;
5056 case REFFA: /* /\1/iaa */
5057 folder = foldEQ_latin1;
5058 fold_array = PL_fold_latin1;
5059 utf8_fold_flags = FOLDEQ_UTF8_NOMIX_ASCII;
5062 case REFFU: /* /\1/iu */
5063 folder = foldEQ_latin1;
5064 fold_array = PL_fold_latin1;
5065 utf8_fold_flags = 0;
5068 case REFF: /* /\1/i */
5070 fold_array = PL_fold;
5071 utf8_fold_flags = 0;
5074 case REF: /* /\1/ */
5077 utf8_fold_flags = 0;
5081 n = ARG(scan); /* which paren pair */
5084 ln = rex->offs[n].start;
5085 reginfo->poscache_iter = reginfo->poscache_maxiter; /* Void cache */
5086 if (rex->lastparen < n || ln == -1)
5087 sayNO; /* Do not match unless seen CLOSEn. */
5088 if (ln == rex->offs[n].end)
5091 s = reginfo->strbeg + ln;
5092 if (type != REF /* REF can do byte comparison */
5093 && (utf8_target || type == REFFU || type == REFFL))
5095 char * limit = reginfo->strend;
5097 /* This call case insensitively compares the entire buffer
5098 * at s, with the current input starting at locinput, but
5099 * not going off the end given by reginfo->strend, and
5100 * returns in <limit> upon success, how much of the
5101 * current input was matched */
5102 if (! foldEQ_utf8_flags(s, NULL, rex->offs[n].end - ln, utf8_target,
5103 locinput, &limit, 0, utf8_target, utf8_fold_flags))
5111 /* Not utf8: Inline the first character, for speed. */
5112 if (!NEXTCHR_IS_EOS &&
5113 UCHARAT(s) != nextchr &&
5115 UCHARAT(s) != fold_array[nextchr]))
5117 ln = rex->offs[n].end - ln;
5118 if (locinput + ln > reginfo->strend)
5120 if (ln > 1 && (type == REF
5121 ? memNE(s, locinput, ln)
5122 : ! folder(s, locinput, ln)))
5128 case NOTHING: /* null op; e.g. the 'nothing' following
5129 * the '*' in m{(a+|b)*}' */
5131 case TAIL: /* placeholder while compiling (A|B|C) */
5134 case BACK: /* ??? doesn't appear to be used ??? */
5138 #define ST st->u.eval
5143 regexp_internal *rei;
5144 regnode *startpoint;
5146 case GOSTART: /* (?R) */
5147 case GOSUB: /* /(...(?1))/ /(...(?&foo))/ */
5148 if (cur_eval && cur_eval->locinput==locinput) {
5149 if (cur_eval->u.eval.close_paren == (U32)ARG(scan))
5150 Perl_croak(aTHX_ "Infinite recursion in regex");
5151 if ( ++nochange_depth > max_nochange_depth )
5153 "Pattern subroutine nesting without pos change"
5154 " exceeded limit in regex");
5161 if (OP(scan)==GOSUB) {
5162 startpoint = scan + ARG2L(scan);
5163 ST.close_paren = ARG(scan);
5165 startpoint = rei->program+1;
5168 goto eval_recurse_doit;
5169 assert(0); /* NOTREACHED */
5171 case EVAL: /* /(?{A})B/ /(??{A})B/ and /(?(?{A})X|Y)B/ */
5172 if (cur_eval && cur_eval->locinput==locinput) {
5173 if ( ++nochange_depth > max_nochange_depth )
5174 Perl_croak(aTHX_ "EVAL without pos change exceeded limit in regex");
5179 /* execute the code in the {...} */
5183 OP * const oop = PL_op;
5184 COP * const ocurcop = PL_curcop;
5188 /* save *all* paren positions */
5189 regcppush(rex, 0, maxopenparen);
5190 REGCP_SET(runops_cp);
5193 caller_cv = find_runcv(NULL);
5197 if (rexi->data->what[n] == 'r') { /* code from an external qr */
5199 (REGEXP*)(rexi->data->data[n])
5202 nop = (OP*)rexi->data->data[n+1];
5204 else if (rexi->data->what[n] == 'l') { /* literal code */
5206 nop = (OP*)rexi->data->data[n];
5207 assert(CvDEPTH(newcv));
5210 /* literal with own CV */
5211 assert(rexi->data->what[n] == 'L');
5212 newcv = rex->qr_anoncv;
5213 nop = (OP*)rexi->data->data[n];
5216 /* normally if we're about to execute code from the same
5217 * CV that we used previously, we just use the existing
5218 * CX stack entry. However, its possible that in the
5219 * meantime we may have backtracked, popped from the save
5220 * stack, and undone the SAVECOMPPAD(s) associated with
5221 * PUSH_MULTICALL; in which case PL_comppad no longer
5222 * points to newcv's pad. */
5223 if (newcv != last_pushed_cv || PL_comppad != last_pad)
5225 U8 flags = (CXp_SUB_RE |
5226 ((newcv == caller_cv) ? CXp_SUB_RE_FAKE : 0));
5227 if (last_pushed_cv) {
5228 CHANGE_MULTICALL_FLAGS(newcv, flags);
5231 PUSH_MULTICALL_FLAGS(newcv, flags);
5233 last_pushed_cv = newcv;
5236 /* these assignments are just to silence compiler
5238 multicall_cop = NULL;
5241 last_pad = PL_comppad;
5243 /* the initial nextstate you would normally execute
5244 * at the start of an eval (which would cause error
5245 * messages to come from the eval), may be optimised
5246 * away from the execution path in the regex code blocks;
5247 * so manually set PL_curcop to it initially */
5249 OP *o = cUNOPx(nop)->op_first;
5250 assert(o->op_type == OP_NULL);
5251 if (o->op_targ == OP_SCOPE) {
5252 o = cUNOPo->op_first;
5255 assert(o->op_targ == OP_LEAVE);
5256 o = cUNOPo->op_first;
5257 assert(o->op_type == OP_ENTER);
5261 if (o->op_type != OP_STUB) {
5262 assert( o->op_type == OP_NEXTSTATE
5263 || o->op_type == OP_DBSTATE
5264 || (o->op_type == OP_NULL
5265 && ( o->op_targ == OP_NEXTSTATE
5266 || o->op_targ == OP_DBSTATE
5270 PL_curcop = (COP*)o;
5275 DEBUG_STATE_r( PerlIO_printf(Perl_debug_log,
5276 " re EVAL PL_op=0x%"UVxf"\n", PTR2UV(nop)) );
5278 rex->offs[0].end = locinput - reginfo->strbeg;
5279 if (reginfo->info_aux_eval->pos_magic)
5280 MgBYTEPOS_set(reginfo->info_aux_eval->pos_magic,
5281 reginfo->sv, reginfo->strbeg,
5282 locinput - reginfo->strbeg);
5285 SV *sv_mrk = get_sv("REGMARK", 1);
5286 sv_setsv(sv_mrk, sv_yes_mark);
5289 /* we don't use MULTICALL here as we want to call the
5290 * first op of the block of interest, rather than the
5291 * first op of the sub */
5292 before = (IV)(SP-PL_stack_base);
5294 CALLRUNOPS(aTHX); /* Scalar context. */
5296 if ((IV)(SP-PL_stack_base) == before)
5297 ret = &PL_sv_undef; /* protect against empty (?{}) blocks. */
5303 /* before restoring everything, evaluate the returned
5304 * value, so that 'uninit' warnings don't use the wrong
5305 * PL_op or pad. Also need to process any magic vars
5306 * (e.g. $1) *before* parentheses are restored */
5311 if (logical == 0) /* (?{})/ */
5312 sv_setsv(save_scalar(PL_replgv), ret); /* $^R */
5313 else if (logical == 1) { /* /(?(?{...})X|Y)/ */
5314 sw = cBOOL(SvTRUE(ret));
5317 else { /* /(??{}) */
5318 /* if its overloaded, let the regex compiler handle
5319 * it; otherwise extract regex, or stringify */
5320 if (SvGMAGICAL(ret))
5321 ret = sv_mortalcopy(ret);
5322 if (!SvAMAGIC(ret)) {
5326 if (SvTYPE(sv) == SVt_REGEXP)
5327 re_sv = (REGEXP*) sv;
5328 else if (SvSMAGICAL(ret)) {
5329 MAGIC *mg = mg_find(ret, PERL_MAGIC_qr);
5331 re_sv = (REGEXP *) mg->mg_obj;
5334 /* force any undef warnings here */
5335 if (!re_sv && !SvPOK(ret) && !SvNIOK(ret)) {
5336 ret = sv_mortalcopy(ret);
5337 (void) SvPV_force_nolen(ret);
5343 /* *** Note that at this point we don't restore
5344 * PL_comppad, (or pop the CxSUB) on the assumption it may
5345 * be used again soon. This is safe as long as nothing
5346 * in the regexp code uses the pad ! */
5348 PL_curcop = ocurcop;
5349 S_regcp_restore(aTHX_ rex, runops_cp, &maxopenparen);
5350 PL_curpm = PL_reg_curpm;
5356 /* only /(??{})/ from now on */
5359 /* extract RE object from returned value; compiling if
5363 re_sv = reg_temp_copy(NULL, re_sv);
5368 if (SvUTF8(ret) && IN_BYTES) {
5369 /* In use 'bytes': make a copy of the octet
5370 * sequence, but without the flag on */
5372 const char *const p = SvPV(ret, len);
5373 ret = newSVpvn_flags(p, len, SVs_TEMP);
5375 if (rex->intflags & PREGf_USE_RE_EVAL)
5376 pm_flags |= PMf_USE_RE_EVAL;
5378 /* if we got here, it should be an engine which
5379 * supports compiling code blocks and stuff */
5380 assert(rex->engine && rex->engine->op_comp);
5381 assert(!(scan->flags & ~RXf_PMf_COMPILETIME));
5382 re_sv = rex->engine->op_comp(aTHX_ &ret, 1, NULL,
5383 rex->engine, NULL, NULL,
5384 /* copy /msix etc to inner pattern */
5389 & (SVs_TEMP | SVs_GMG | SVf_ROK))
5390 && (!SvPADTMP(ret) || SvREADONLY(ret))) {
5391 /* This isn't a first class regexp. Instead, it's
5392 caching a regexp onto an existing, Perl visible
5394 sv_magic(ret, MUTABLE_SV(re_sv), PERL_MAGIC_qr, 0, 0);
5400 RXp_MATCH_COPIED_off(re);
5401 re->subbeg = rex->subbeg;
5402 re->sublen = rex->sublen;
5403 re->suboffset = rex->suboffset;
5404 re->subcoffset = rex->subcoffset;
5407 debug_start_match(re_sv, utf8_target, locinput,
5408 reginfo->strend, "Matching embedded");
5410 startpoint = rei->program + 1;
5411 ST.close_paren = 0; /* only used for GOSUB */
5413 eval_recurse_doit: /* Share code with GOSUB below this line */
5414 /* run the pattern returned from (??{...}) */
5416 /* Save *all* the positions. */
5417 ST.cp = regcppush(rex, 0, maxopenparen);
5418 REGCP_SET(ST.lastcp);
5421 re->lastcloseparen = 0;
5425 /* invalidate the S-L poscache. We're now executing a
5426 * different set of WHILEM ops (and their associated
5427 * indexes) against the same string, so the bits in the
5428 * cache are meaningless. Setting maxiter to zero forces
5429 * the cache to be invalidated and zeroed before reuse.
5430 * XXX This is too dramatic a measure. Ideally we should
5431 * save the old cache and restore when running the outer
5433 reginfo->poscache_maxiter = 0;
5435 is_utf8_pat = reginfo->is_utf8_pat = cBOOL(RX_UTF8(re_sv));
5437 ST.prev_rex = rex_sv;
5438 ST.prev_curlyx = cur_curlyx;
5440 SET_reg_curpm(rex_sv);
5445 ST.prev_eval = cur_eval;
5447 /* now continue from first node in postoned RE */
5448 PUSH_YES_STATE_GOTO(EVAL_AB, startpoint, locinput);
5449 assert(0); /* NOTREACHED */
5452 case EVAL_AB: /* cleanup after a successful (??{A})B */
5453 /* note: this is called twice; first after popping B, then A */
5454 rex_sv = ST.prev_rex;
5455 is_utf8_pat = reginfo->is_utf8_pat = cBOOL(RX_UTF8(rex_sv));
5456 SET_reg_curpm(rex_sv);
5457 rex = ReANY(rex_sv);
5458 rexi = RXi_GET(rex);
5460 /* preserve $^R across LEAVE's. See Bug 121070. */
5461 SV *save_sv= GvSV(PL_replgv);
5462 SvREFCNT_inc(save_sv);
5463 regcpblow(ST.cp); /* LEAVE in disguise */
5464 sv_setsv(GvSV(PL_replgv), save_sv);
5465 SvREFCNT_dec(save_sv);
5467 cur_eval = ST.prev_eval;
5468 cur_curlyx = ST.prev_curlyx;
5470 /* Invalidate cache. See "invalidate" comment above. */
5471 reginfo->poscache_maxiter = 0;
5472 if ( nochange_depth )
5477 case EVAL_AB_fail: /* unsuccessfully ran A or B in (??{A})B */
5478 /* note: this is called twice; first after popping B, then A */
5479 rex_sv = ST.prev_rex;
5480 is_utf8_pat = reginfo->is_utf8_pat = cBOOL(RX_UTF8(rex_sv));
5481 SET_reg_curpm(rex_sv);
5482 rex = ReANY(rex_sv);
5483 rexi = RXi_GET(rex);
5485 REGCP_UNWIND(ST.lastcp);
5486 regcppop(rex, &maxopenparen);
5487 cur_eval = ST.prev_eval;
5488 cur_curlyx = ST.prev_curlyx;
5489 /* Invalidate cache. See "invalidate" comment above. */
5490 reginfo->poscache_maxiter = 0;
5491 if ( nochange_depth )
5497 n = ARG(scan); /* which paren pair */
5498 rex->offs[n].start_tmp = locinput - reginfo->strbeg;
5499 if (n > maxopenparen)
5501 DEBUG_BUFFERS_r(PerlIO_printf(Perl_debug_log,
5502 "rex=0x%"UVxf" offs=0x%"UVxf": \\%"UVuf": set %"IVdf" tmp; maxopenparen=%"UVuf"\n",
5506 (IV)rex->offs[n].start_tmp,
5512 /* XXX really need to log other places start/end are set too */
5513 #define CLOSE_CAPTURE \
5514 rex->offs[n].start = rex->offs[n].start_tmp; \
5515 rex->offs[n].end = locinput - reginfo->strbeg; \
5516 DEBUG_BUFFERS_r(PerlIO_printf(Perl_debug_log, \
5517 "rex=0x%"UVxf" offs=0x%"UVxf": \\%"UVuf": set %"IVdf"..%"IVdf"\n", \
5519 PTR2UV(rex->offs), \
5521 (IV)rex->offs[n].start, \
5522 (IV)rex->offs[n].end \
5526 n = ARG(scan); /* which paren pair */
5528 if (n > rex->lastparen)
5530 rex->lastcloseparen = n;
5531 if (cur_eval && cur_eval->u.eval.close_paren == n) {
5536 case ACCEPT: /* (*ACCEPT) */
5540 cursor && OP(cursor)!=END;
5541 cursor=regnext(cursor))
5543 if ( OP(cursor)==CLOSE ){
5545 if ( n <= lastopen ) {
5547 if (n > rex->lastparen)
5549 rex->lastcloseparen = n;
5550 if ( n == ARG(scan) || (cur_eval &&
5551 cur_eval->u.eval.close_paren == n))
5560 case GROUPP: /* (?(1)) */
5561 n = ARG(scan); /* which paren pair */
5562 sw = cBOOL(rex->lastparen >= n && rex->offs[n].end != -1);
5565 case NGROUPP: /* (?(<name>)) */
5566 /* reg_check_named_buff_matched returns 0 for no match */
5567 sw = cBOOL(0 < reg_check_named_buff_matched(rex,scan));
5570 case INSUBP: /* (?(R)) */
5572 sw = (cur_eval && (!n || cur_eval->u.eval.close_paren == n));
5575 case DEFINEP: /* (?(DEFINE)) */
5579 case IFTHEN: /* (?(cond)A|B) */
5580 reginfo->poscache_iter = reginfo->poscache_maxiter; /* Void cache */
5582 next = NEXTOPER(NEXTOPER(scan));
5584 next = scan + ARG(scan);
5585 if (OP(next) == IFTHEN) /* Fake one. */
5586 next = NEXTOPER(NEXTOPER(next));
5590 case LOGICAL: /* modifier for EVAL and IFMATCH */
5591 logical = scan->flags;
5594 /*******************************************************************
5596 The CURLYX/WHILEM pair of ops handle the most generic case of the /A*B/
5597 pattern, where A and B are subpatterns. (For simple A, CURLYM or
5598 STAR/PLUS/CURLY/CURLYN are used instead.)
5600 A*B is compiled as <CURLYX><A><WHILEM><B>
5602 On entry to the subpattern, CURLYX is called. This pushes a CURLYX
5603 state, which contains the current count, initialised to -1. It also sets
5604 cur_curlyx to point to this state, with any previous value saved in the
5607 CURLYX then jumps straight to the WHILEM op, rather than executing A,
5608 since the pattern may possibly match zero times (i.e. it's a while {} loop
5609 rather than a do {} while loop).
5611 Each entry to WHILEM represents a successful match of A. The count in the
5612 CURLYX block is incremented, another WHILEM state is pushed, and execution
5613 passes to A or B depending on greediness and the current count.
5615 For example, if matching against the string a1a2a3b (where the aN are
5616 substrings that match /A/), then the match progresses as follows: (the
5617 pushed states are interspersed with the bits of strings matched so far):
5620 <CURLYX cnt=0><WHILEM>
5621 <CURLYX cnt=1><WHILEM> a1 <WHILEM>
5622 <CURLYX cnt=2><WHILEM> a1 <WHILEM> a2 <WHILEM>
5623 <CURLYX cnt=3><WHILEM> a1 <WHILEM> a2 <WHILEM> a3 <WHILEM>
5624 <CURLYX cnt=3><WHILEM> a1 <WHILEM> a2 <WHILEM> a3 <WHILEM> b
5626 (Contrast this with something like CURLYM, which maintains only a single
5630 a1 <CURLYM cnt=1> a2
5631 a1 a2 <CURLYM cnt=2> a3
5632 a1 a2 a3 <CURLYM cnt=3> b
5635 Each WHILEM state block marks a point to backtrack to upon partial failure
5636 of A or B, and also contains some minor state data related to that
5637 iteration. The CURLYX block, pointed to by cur_curlyx, contains the
5638 overall state, such as the count, and pointers to the A and B ops.
5640 This is complicated slightly by nested CURLYX/WHILEM's. Since cur_curlyx
5641 must always point to the *current* CURLYX block, the rules are:
5643 When executing CURLYX, save the old cur_curlyx in the CURLYX state block,
5644 and set cur_curlyx to point the new block.
5646 When popping the CURLYX block after a successful or unsuccessful match,
5647 restore the previous cur_curlyx.
5649 When WHILEM is about to execute B, save the current cur_curlyx, and set it
5650 to the outer one saved in the CURLYX block.
5652 When popping the WHILEM block after a successful or unsuccessful B match,
5653 restore the previous cur_curlyx.
5655 Here's an example for the pattern (AI* BI)*BO
5656 I and O refer to inner and outer, C and W refer to CURLYX and WHILEM:
5659 curlyx backtrack stack
5660 ------ ---------------
5662 CO <CO prev=NULL> <WO>
5663 CI <CO prev=NULL> <WO> <CI prev=CO> <WI> ai
5664 CO <CO prev=NULL> <WO> <CI prev=CO> <WI> ai <WI prev=CI> bi
5665 NULL <CO prev=NULL> <WO> <CI prev=CO> <WI> ai <WI prev=CI> bi <WO prev=CO> bo
5667 At this point the pattern succeeds, and we work back down the stack to
5668 clean up, restoring as we go:
5670 CO <CO prev=NULL> <WO> <CI prev=CO> <WI> ai <WI prev=CI> bi
5671 CI <CO prev=NULL> <WO> <CI prev=CO> <WI> ai
5672 CO <CO prev=NULL> <WO>
5675 *******************************************************************/
5677 #define ST st->u.curlyx
5679 case CURLYX: /* start of /A*B/ (for complex A) */
5681 /* No need to save/restore up to this paren */
5682 I32 parenfloor = scan->flags;
5684 assert(next); /* keep Coverity happy */
5685 if (OP(PREVOPER(next)) == NOTHING) /* LONGJMP */
5688 /* XXXX Probably it is better to teach regpush to support
5689 parenfloor > maxopenparen ... */
5690 if (parenfloor > (I32)rex->lastparen)
5691 parenfloor = rex->lastparen; /* Pessimization... */
5693 ST.prev_curlyx= cur_curlyx;
5695 ST.cp = PL_savestack_ix;
5697 /* these fields contain the state of the current curly.
5698 * they are accessed by subsequent WHILEMs */
5699 ST.parenfloor = parenfloor;
5704 ST.count = -1; /* this will be updated by WHILEM */
5705 ST.lastloc = NULL; /* this will be updated by WHILEM */
5707 PUSH_YES_STATE_GOTO(CURLYX_end, PREVOPER(next), locinput);
5708 assert(0); /* NOTREACHED */
5711 case CURLYX_end: /* just finished matching all of A*B */
5712 cur_curlyx = ST.prev_curlyx;
5714 assert(0); /* NOTREACHED */
5716 case CURLYX_end_fail: /* just failed to match all of A*B */
5718 cur_curlyx = ST.prev_curlyx;
5720 assert(0); /* NOTREACHED */
5724 #define ST st->u.whilem
5726 case WHILEM: /* just matched an A in /A*B/ (for complex A) */
5728 /* see the discussion above about CURLYX/WHILEM */
5730 int min = ARG1(cur_curlyx->u.curlyx.me);
5731 int max = ARG2(cur_curlyx->u.curlyx.me);
5732 regnode *A = NEXTOPER(cur_curlyx->u.curlyx.me) + EXTRA_STEP_2ARGS;
5734 assert(cur_curlyx); /* keep Coverity happy */
5735 n = ++cur_curlyx->u.curlyx.count; /* how many A's matched */
5736 ST.save_lastloc = cur_curlyx->u.curlyx.lastloc;
5737 ST.cache_offset = 0;
5741 DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log,
5742 "%*s whilem: matched %ld out of %d..%d\n",
5743 REPORT_CODE_OFF+depth*2, "", (long)n, min, max)
5746 /* First just match a string of min A's. */
5749 ST.cp = regcppush(rex, cur_curlyx->u.curlyx.parenfloor,
5751 cur_curlyx->u.curlyx.lastloc = locinput;
5752 REGCP_SET(ST.lastcp);
5754 PUSH_STATE_GOTO(WHILEM_A_pre, A, locinput);
5755 assert(0); /* NOTREACHED */
5758 /* If degenerate A matches "", assume A done. */
5760 if (locinput == cur_curlyx->u.curlyx.lastloc) {
5761 DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log,
5762 "%*s whilem: empty match detected, trying continuation...\n",
5763 REPORT_CODE_OFF+depth*2, "")
5765 goto do_whilem_B_max;
5768 /* super-linear cache processing.
5770 * The idea here is that for certain types of CURLYX/WHILEM -
5771 * principally those whose upper bound is infinity (and
5772 * excluding regexes that have things like \1 and other very
5773 * non-regular expresssiony things), then if a pattern like
5774 * /....A*.../ fails and we backtrack to the WHILEM, then we
5775 * make a note that this particular WHILEM op was at string
5776 * position 47 (say) when the rest of pattern failed. Then, if
5777 * we ever find ourselves back at that WHILEM, and at string
5778 * position 47 again, we can just fail immediately rather than
5779 * running the rest of the pattern again.
5781 * This is very handy when patterns start to go
5782 * 'super-linear', like in (a+)*(a+)*(a+)*, where you end up
5783 * with a combinatorial explosion of backtracking.
5785 * The cache is implemented as a bit array, with one bit per
5786 * string byte position per WHILEM op (up to 16) - so its
5787 * between 0.25 and 2x the string size.
5789 * To avoid allocating a poscache buffer every time, we do an
5790 * initially countdown; only after we have executed a WHILEM
5791 * op (string-length x #WHILEMs) times do we allocate the
5794 * The top 4 bits of scan->flags byte say how many different
5795 * relevant CURLLYX/WHILEM op pairs there are, while the
5796 * bottom 4-bits is the identifying index number of this
5802 if (!reginfo->poscache_maxiter) {
5803 /* start the countdown: Postpone detection until we
5804 * know the match is not *that* much linear. */
5805 reginfo->poscache_maxiter
5806 = (reginfo->strend - reginfo->strbeg + 1)
5808 /* possible overflow for long strings and many CURLYX's */
5809 if (reginfo->poscache_maxiter < 0)
5810 reginfo->poscache_maxiter = I32_MAX;
5811 reginfo->poscache_iter = reginfo->poscache_maxiter;
5814 if (reginfo->poscache_iter-- == 0) {
5815 /* initialise cache */
5816 const SSize_t size = (reginfo->poscache_maxiter + 7)/8;
5817 regmatch_info_aux *const aux = reginfo->info_aux;
5818 if (aux->poscache) {
5819 if ((SSize_t)reginfo->poscache_size < size) {
5820 Renew(aux->poscache, size, char);
5821 reginfo->poscache_size = size;
5823 Zero(aux->poscache, size, char);
5826 reginfo->poscache_size = size;
5827 Newxz(aux->poscache, size, char);
5829 DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log,
5830 "%swhilem: Detected a super-linear match, switching on caching%s...\n",
5831 PL_colors[4], PL_colors[5])
5835 if (reginfo->poscache_iter < 0) {
5836 /* have we already failed at this position? */
5837 SSize_t offset, mask;
5839 reginfo->poscache_iter = -1; /* stop eventual underflow */
5840 offset = (scan->flags & 0xf) - 1
5841 + (locinput - reginfo->strbeg)
5843 mask = 1 << (offset % 8);
5845 if (reginfo->info_aux->poscache[offset] & mask) {
5846 DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log,
5847 "%*s whilem: (cache) already tried at this position...\n",
5848 REPORT_CODE_OFF+depth*2, "")
5850 sayNO; /* cache records failure */
5852 ST.cache_offset = offset;
5853 ST.cache_mask = mask;
5857 /* Prefer B over A for minimal matching. */
5859 if (cur_curlyx->u.curlyx.minmod) {
5860 ST.save_curlyx = cur_curlyx;
5861 cur_curlyx = cur_curlyx->u.curlyx.prev_curlyx;
5862 ST.cp = regcppush(rex, ST.save_curlyx->u.curlyx.parenfloor,
5864 REGCP_SET(ST.lastcp);
5865 PUSH_YES_STATE_GOTO(WHILEM_B_min, ST.save_curlyx->u.curlyx.B,
5867 assert(0); /* NOTREACHED */
5870 /* Prefer A over B for maximal matching. */
5872 if (n < max) { /* More greed allowed? */
5873 ST.cp = regcppush(rex, cur_curlyx->u.curlyx.parenfloor,
5875 cur_curlyx->u.curlyx.lastloc = locinput;
5876 REGCP_SET(ST.lastcp);
5877 PUSH_STATE_GOTO(WHILEM_A_max, A, locinput);
5878 assert(0); /* NOTREACHED */
5880 goto do_whilem_B_max;
5882 assert(0); /* NOTREACHED */
5884 case WHILEM_B_min: /* just matched B in a minimal match */
5885 case WHILEM_B_max: /* just matched B in a maximal match */
5886 cur_curlyx = ST.save_curlyx;
5888 assert(0); /* NOTREACHED */
5890 case WHILEM_B_max_fail: /* just failed to match B in a maximal match */
5891 cur_curlyx = ST.save_curlyx;
5892 cur_curlyx->u.curlyx.lastloc = ST.save_lastloc;
5893 cur_curlyx->u.curlyx.count--;
5895 assert(0); /* NOTREACHED */
5897 case WHILEM_A_min_fail: /* just failed to match A in a minimal match */
5899 case WHILEM_A_pre_fail: /* just failed to match even minimal A */
5900 REGCP_UNWIND(ST.lastcp);
5901 regcppop(rex, &maxopenparen);
5902 cur_curlyx->u.curlyx.lastloc = ST.save_lastloc;
5903 cur_curlyx->u.curlyx.count--;
5905 assert(0); /* NOTREACHED */
5907 case WHILEM_A_max_fail: /* just failed to match A in a maximal match */
5908 REGCP_UNWIND(ST.lastcp);
5909 regcppop(rex, &maxopenparen); /* Restore some previous $<digit>s? */
5910 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
5911 "%*s whilem: failed, trying continuation...\n",
5912 REPORT_CODE_OFF+depth*2, "")
5915 if (cur_curlyx->u.curlyx.count >= REG_INFTY
5916 && ckWARN(WARN_REGEXP)
5917 && !reginfo->warned)
5919 reginfo->warned = TRUE;
5920 Perl_warner(aTHX_ packWARN(WARN_REGEXP),
5921 "Complex regular subexpression recursion limit (%d) "
5927 ST.save_curlyx = cur_curlyx;
5928 cur_curlyx = cur_curlyx->u.curlyx.prev_curlyx;
5929 PUSH_YES_STATE_GOTO(WHILEM_B_max, ST.save_curlyx->u.curlyx.B,
5931 assert(0); /* NOTREACHED */
5933 case WHILEM_B_min_fail: /* just failed to match B in a minimal match */
5934 cur_curlyx = ST.save_curlyx;
5935 REGCP_UNWIND(ST.lastcp);
5936 regcppop(rex, &maxopenparen);
5938 if (cur_curlyx->u.curlyx.count >= /*max*/ARG2(cur_curlyx->u.curlyx.me)) {
5939 /* Maximum greed exceeded */
5940 if (cur_curlyx->u.curlyx.count >= REG_INFTY
5941 && ckWARN(WARN_REGEXP)
5942 && !reginfo->warned)
5944 reginfo->warned = TRUE;
5945 Perl_warner(aTHX_ packWARN(WARN_REGEXP),
5946 "Complex regular subexpression recursion "
5947 "limit (%d) exceeded",
5950 cur_curlyx->u.curlyx.count--;
5954 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
5955 "%*s trying longer...\n", REPORT_CODE_OFF+depth*2, "")
5957 /* Try grabbing another A and see if it helps. */
5958 cur_curlyx->u.curlyx.lastloc = locinput;
5959 ST.cp = regcppush(rex, cur_curlyx->u.curlyx.parenfloor,
5961 REGCP_SET(ST.lastcp);
5962 PUSH_STATE_GOTO(WHILEM_A_min,
5963 /*A*/ NEXTOPER(ST.save_curlyx->u.curlyx.me) + EXTRA_STEP_2ARGS,
5965 assert(0); /* NOTREACHED */
5968 #define ST st->u.branch
5970 case BRANCHJ: /* /(...|A|...)/ with long next pointer */
5971 next = scan + ARG(scan);
5974 scan = NEXTOPER(scan);
5977 case BRANCH: /* /(...|A|...)/ */
5978 scan = NEXTOPER(scan); /* scan now points to inner node */
5979 ST.lastparen = rex->lastparen;
5980 ST.lastcloseparen = rex->lastcloseparen;
5981 ST.next_branch = next;
5984 /* Now go into the branch */
5986 PUSH_YES_STATE_GOTO(BRANCH_next, scan, locinput);
5988 PUSH_STATE_GOTO(BRANCH_next, scan, locinput);
5990 assert(0); /* NOTREACHED */
5992 case CUTGROUP: /* /(*THEN)/ */
5993 sv_yes_mark = st->u.mark.mark_name = scan->flags ? NULL :
5994 MUTABLE_SV(rexi->data->data[ ARG( scan ) ]);
5995 PUSH_STATE_GOTO(CUTGROUP_next, next, locinput);
5996 assert(0); /* NOTREACHED */
5998 case CUTGROUP_next_fail:
6001 if (st->u.mark.mark_name)
6002 sv_commit = st->u.mark.mark_name;
6004 assert(0); /* NOTREACHED */
6008 assert(0); /* NOTREACHED */
6010 case BRANCH_next_fail: /* that branch failed; try the next, if any */
6015 REGCP_UNWIND(ST.cp);
6016 UNWIND_PAREN(ST.lastparen, ST.lastcloseparen);
6017 scan = ST.next_branch;
6018 /* no more branches? */
6019 if (!scan || (OP(scan) != BRANCH && OP(scan) != BRANCHJ)) {
6021 PerlIO_printf( Perl_debug_log,
6022 "%*s %sBRANCH failed...%s\n",
6023 REPORT_CODE_OFF+depth*2, "",
6029 continue; /* execute next BRANCH[J] op */
6030 assert(0); /* NOTREACHED */
6032 case MINMOD: /* next op will be non-greedy, e.g. A*? */
6037 #define ST st->u.curlym
6039 case CURLYM: /* /A{m,n}B/ where A is fixed-length */
6041 /* This is an optimisation of CURLYX that enables us to push
6042 * only a single backtracking state, no matter how many matches
6043 * there are in {m,n}. It relies on the pattern being constant
6044 * length, with no parens to influence future backrefs
6048 scan = NEXTOPER(scan) + NODE_STEP_REGNODE;
6050 ST.lastparen = rex->lastparen;
6051 ST.lastcloseparen = rex->lastcloseparen;
6053 /* if paren positive, emulate an OPEN/CLOSE around A */
6055 U32 paren = ST.me->flags;
6056 if (paren > maxopenparen)
6057 maxopenparen = paren;
6058 scan += NEXT_OFF(scan); /* Skip former OPEN. */
6066 ST.c1 = CHRTEST_UNINIT;
6069 if (!(ST.minmod ? ARG1(ST.me) : ARG2(ST.me))) /* min/max */
6072 curlym_do_A: /* execute the A in /A{m,n}B/ */
6073 PUSH_YES_STATE_GOTO(CURLYM_A, ST.A, locinput); /* match A */
6074 assert(0); /* NOTREACHED */
6076 case CURLYM_A: /* we've just matched an A */
6078 /* after first match, determine A's length: u.curlym.alen */
6079 if (ST.count == 1) {
6080 if (reginfo->is_utf8_target) {
6081 char *s = st->locinput;
6082 while (s < locinput) {
6088 ST.alen = locinput - st->locinput;
6091 ST.count = ST.minmod ? ARG1(ST.me) : ARG2(ST.me);
6094 PerlIO_printf(Perl_debug_log,
6095 "%*s CURLYM now matched %"IVdf" times, len=%"IVdf"...\n",
6096 (int)(REPORT_CODE_OFF+(depth*2)), "",
6097 (IV) ST.count, (IV)ST.alen)
6100 if (cur_eval && cur_eval->u.eval.close_paren &&
6101 cur_eval->u.eval.close_paren == (U32)ST.me->flags)
6105 I32 max = (ST.minmod ? ARG1(ST.me) : ARG2(ST.me));
6106 if ( max == REG_INFTY || ST.count < max )
6107 goto curlym_do_A; /* try to match another A */
6109 goto curlym_do_B; /* try to match B */
6111 case CURLYM_A_fail: /* just failed to match an A */
6112 REGCP_UNWIND(ST.cp);
6114 if (ST.minmod || ST.count < ARG1(ST.me) /* min*/
6115 || (cur_eval && cur_eval->u.eval.close_paren &&
6116 cur_eval->u.eval.close_paren == (U32)ST.me->flags))
6119 curlym_do_B: /* execute the B in /A{m,n}B/ */
6120 if (ST.c1 == CHRTEST_UNINIT) {
6121 /* calculate c1 and c2 for possible match of 1st char
6122 * following curly */
6123 ST.c1 = ST.c2 = CHRTEST_VOID;
6124 if (HAS_TEXT(ST.B) || JUMPABLE(ST.B)) {
6125 regnode *text_node = ST.B;
6126 if (! HAS_TEXT(text_node))
6127 FIND_NEXT_IMPT(text_node);
6130 (HAS_TEXT(text_node) && PL_regkind[OP(text_node)] == EXACT)
6132 But the former is redundant in light of the latter.
6134 if this changes back then the macro for
6135 IS_TEXT and friends need to change.
6137 if (PL_regkind[OP(text_node)] == EXACT) {
6138 if (! S_setup_EXACTISH_ST_c1_c2(aTHX_
6139 text_node, &ST.c1, ST.c1_utf8, &ST.c2, ST.c2_utf8,
6149 PerlIO_printf(Perl_debug_log,
6150 "%*s CURLYM trying tail with matches=%"IVdf"...\n",
6151 (int)(REPORT_CODE_OFF+(depth*2)),
6154 if (! NEXTCHR_IS_EOS && ST.c1 != CHRTEST_VOID) {
6155 if (! UTF8_IS_INVARIANT(nextchr) && utf8_target) {
6156 if (memNE(locinput, ST.c1_utf8, UTF8SKIP(locinput))
6157 && memNE(locinput, ST.c2_utf8, UTF8SKIP(locinput)))
6159 /* simulate B failing */
6161 PerlIO_printf(Perl_debug_log,
6162 "%*s CURLYM Fast bail next target=0x%"UVXf" c1=0x%"UVXf" c2=0x%"UVXf"\n",
6163 (int)(REPORT_CODE_OFF+(depth*2)),"",
6164 valid_utf8_to_uvchr((U8 *) locinput, NULL),
6165 valid_utf8_to_uvchr(ST.c1_utf8, NULL),
6166 valid_utf8_to_uvchr(ST.c2_utf8, NULL))
6168 state_num = CURLYM_B_fail;
6169 goto reenter_switch;
6172 else if (nextchr != ST.c1 && nextchr != ST.c2) {
6173 /* simulate B failing */
6175 PerlIO_printf(Perl_debug_log,
6176 "%*s CURLYM Fast bail next target=0x%X c1=0x%X c2=0x%X\n",
6177 (int)(REPORT_CODE_OFF+(depth*2)),"",
6178 (int) nextchr, ST.c1, ST.c2)
6180 state_num = CURLYM_B_fail;
6181 goto reenter_switch;
6186 /* emulate CLOSE: mark current A as captured */
6187 I32 paren = ST.me->flags;
6189 rex->offs[paren].start
6190 = HOPc(locinput, -ST.alen) - reginfo->strbeg;
6191 rex->offs[paren].end = locinput - reginfo->strbeg;
6192 if ((U32)paren > rex->lastparen)
6193 rex->lastparen = paren;
6194 rex->lastcloseparen = paren;
6197 rex->offs[paren].end = -1;
6198 if (cur_eval && cur_eval->u.eval.close_paren &&
6199 cur_eval->u.eval.close_paren == (U32)ST.me->flags)
6208 PUSH_STATE_GOTO(CURLYM_B, ST.B, locinput); /* match B */
6209 assert(0); /* NOTREACHED */
6211 case CURLYM_B_fail: /* just failed to match a B */
6212 REGCP_UNWIND(ST.cp);
6213 UNWIND_PAREN(ST.lastparen, ST.lastcloseparen);
6215 I32 max = ARG2(ST.me);
6216 if (max != REG_INFTY && ST.count == max)
6218 goto curlym_do_A; /* try to match a further A */
6220 /* backtrack one A */
6221 if (ST.count == ARG1(ST.me) /* min */)
6224 SET_locinput(HOPc(locinput, -ST.alen));
6225 goto curlym_do_B; /* try to match B */
6228 #define ST st->u.curly
6230 #define CURLY_SETPAREN(paren, success) \
6233 rex->offs[paren].start = HOPc(locinput, -1) - reginfo->strbeg; \
6234 rex->offs[paren].end = locinput - reginfo->strbeg; \
6235 if (paren > rex->lastparen) \
6236 rex->lastparen = paren; \
6237 rex->lastcloseparen = paren; \
6240 rex->offs[paren].end = -1; \
6241 rex->lastparen = ST.lastparen; \
6242 rex->lastcloseparen = ST.lastcloseparen; \
6246 case STAR: /* /A*B/ where A is width 1 char */
6250 scan = NEXTOPER(scan);
6253 case PLUS: /* /A+B/ where A is width 1 char */
6257 scan = NEXTOPER(scan);
6260 case CURLYN: /* /(A){m,n}B/ where A is width 1 char */
6261 ST.paren = scan->flags; /* Which paren to set */
6262 ST.lastparen = rex->lastparen;
6263 ST.lastcloseparen = rex->lastcloseparen;
6264 if (ST.paren > maxopenparen)
6265 maxopenparen = ST.paren;
6266 ST.min = ARG1(scan); /* min to match */
6267 ST.max = ARG2(scan); /* max to match */
6268 if (cur_eval && cur_eval->u.eval.close_paren &&
6269 cur_eval->u.eval.close_paren == (U32)ST.paren) {
6273 scan = regnext(NEXTOPER(scan) + NODE_STEP_REGNODE);
6276 case CURLY: /* /A{m,n}B/ where A is width 1 char */
6278 ST.min = ARG1(scan); /* min to match */
6279 ST.max = ARG2(scan); /* max to match */
6280 scan = NEXTOPER(scan) + NODE_STEP_REGNODE;
6283 * Lookahead to avoid useless match attempts
6284 * when we know what character comes next.
6286 * Used to only do .*x and .*?x, but now it allows
6287 * for )'s, ('s and (?{ ... })'s to be in the way
6288 * of the quantifier and the EXACT-like node. -- japhy
6291 assert(ST.min <= ST.max);
6292 if (! HAS_TEXT(next) && ! JUMPABLE(next)) {
6293 ST.c1 = ST.c2 = CHRTEST_VOID;
6296 regnode *text_node = next;
6298 if (! HAS_TEXT(text_node))
6299 FIND_NEXT_IMPT(text_node);
6301 if (! HAS_TEXT(text_node))
6302 ST.c1 = ST.c2 = CHRTEST_VOID;
6304 if ( PL_regkind[OP(text_node)] != EXACT ) {
6305 ST.c1 = ST.c2 = CHRTEST_VOID;
6309 /* Currently we only get here when
6311 PL_rekind[OP(text_node)] == EXACT
6313 if this changes back then the macro for IS_TEXT and
6314 friends need to change. */
6315 if (! S_setup_EXACTISH_ST_c1_c2(aTHX_
6316 text_node, &ST.c1, ST.c1_utf8, &ST.c2, ST.c2_utf8,
6328 char *li = locinput;
6331 regrepeat(rex, &li, ST.A, reginfo, ST.min, depth)
6337 if (ST.c1 == CHRTEST_VOID)
6338 goto curly_try_B_min;
6340 ST.oldloc = locinput;
6342 /* set ST.maxpos to the furthest point along the
6343 * string that could possibly match */
6344 if (ST.max == REG_INFTY) {
6345 ST.maxpos = reginfo->strend - 1;
6347 while (UTF8_IS_CONTINUATION(*(U8*)ST.maxpos))
6350 else if (utf8_target) {
6351 int m = ST.max - ST.min;
6352 for (ST.maxpos = locinput;
6353 m >0 && ST.maxpos < reginfo->strend; m--)
6354 ST.maxpos += UTF8SKIP(ST.maxpos);
6357 ST.maxpos = locinput + ST.max - ST.min;
6358 if (ST.maxpos >= reginfo->strend)
6359 ST.maxpos = reginfo->strend - 1;
6361 goto curly_try_B_min_known;
6365 /* avoid taking address of locinput, so it can remain
6367 char *li = locinput;
6368 ST.count = regrepeat(rex, &li, ST.A, reginfo, ST.max, depth);
6369 if (ST.count < ST.min)
6372 if ((ST.count > ST.min)
6373 && (PL_regkind[OP(ST.B)] == EOL) && (OP(ST.B) != MEOL))
6375 /* A{m,n} must come at the end of the string, there's
6376 * no point in backing off ... */
6378 /* ...except that $ and \Z can match before *and* after
6379 newline at the end. Consider "\n\n" =~ /\n+\Z\n/.
6380 We may back off by one in this case. */
6381 if (UCHARAT(locinput - 1) == '\n' && OP(ST.B) != EOS)
6385 goto curly_try_B_max;
6387 assert(0); /* NOTREACHED */
6390 case CURLY_B_min_known_fail:
6391 /* failed to find B in a non-greedy match where c1,c2 valid */
6393 REGCP_UNWIND(ST.cp);
6395 UNWIND_PAREN(ST.lastparen, ST.lastcloseparen);
6397 /* Couldn't or didn't -- move forward. */
6398 ST.oldloc = locinput;
6400 locinput += UTF8SKIP(locinput);
6404 curly_try_B_min_known:
6405 /* find the next place where 'B' could work, then call B */
6409 n = (ST.oldloc == locinput) ? 0 : 1;
6410 if (ST.c1 == ST.c2) {
6411 /* set n to utf8_distance(oldloc, locinput) */
6412 while (locinput <= ST.maxpos
6413 && memNE(locinput, ST.c1_utf8, UTF8SKIP(locinput)))
6415 locinput += UTF8SKIP(locinput);
6420 /* set n to utf8_distance(oldloc, locinput) */
6421 while (locinput <= ST.maxpos
6422 && memNE(locinput, ST.c1_utf8, UTF8SKIP(locinput))
6423 && memNE(locinput, ST.c2_utf8, UTF8SKIP(locinput)))
6425 locinput += UTF8SKIP(locinput);
6430 else { /* Not utf8_target */
6431 if (ST.c1 == ST.c2) {
6432 while (locinput <= ST.maxpos &&
6433 UCHARAT(locinput) != ST.c1)
6437 while (locinput <= ST.maxpos
6438 && UCHARAT(locinput) != ST.c1
6439 && UCHARAT(locinput) != ST.c2)
6442 n = locinput - ST.oldloc;
6444 if (locinput > ST.maxpos)
6447 /* In /a{m,n}b/, ST.oldloc is at "a" x m, locinput is
6448 * at b; check that everything between oldloc and
6449 * locinput matches */
6450 char *li = ST.oldloc;
6452 if (regrepeat(rex, &li, ST.A, reginfo, n, depth) < n)
6454 assert(n == REG_INFTY || locinput == li);
6456 CURLY_SETPAREN(ST.paren, ST.count);
6457 if (cur_eval && cur_eval->u.eval.close_paren &&
6458 cur_eval->u.eval.close_paren == (U32)ST.paren) {
6461 PUSH_STATE_GOTO(CURLY_B_min_known, ST.B, locinput);
6463 assert(0); /* NOTREACHED */
6466 case CURLY_B_min_fail:
6467 /* failed to find B in a non-greedy match where c1,c2 invalid */
6469 REGCP_UNWIND(ST.cp);
6471 UNWIND_PAREN(ST.lastparen, ST.lastcloseparen);
6473 /* failed -- move forward one */
6475 char *li = locinput;
6476 if (!regrepeat(rex, &li, ST.A, reginfo, 1, depth)) {
6483 if (ST.count <= ST.max || (ST.max == REG_INFTY &&
6484 ST.count > 0)) /* count overflow ? */
6487 CURLY_SETPAREN(ST.paren, ST.count);
6488 if (cur_eval && cur_eval->u.eval.close_paren &&
6489 cur_eval->u.eval.close_paren == (U32)ST.paren) {
6492 PUSH_STATE_GOTO(CURLY_B_min, ST.B, locinput);
6496 assert(0); /* NOTREACHED */
6500 /* a successful greedy match: now try to match B */
6501 if (cur_eval && cur_eval->u.eval.close_paren &&
6502 cur_eval->u.eval.close_paren == (U32)ST.paren) {
6506 bool could_match = locinput < reginfo->strend;
6508 /* If it could work, try it. */
6509 if (ST.c1 != CHRTEST_VOID && could_match) {
6510 if (! UTF8_IS_INVARIANT(UCHARAT(locinput)) && utf8_target)
6512 could_match = memEQ(locinput,
6517 UTF8SKIP(locinput));
6520 could_match = UCHARAT(locinput) == ST.c1
6521 || UCHARAT(locinput) == ST.c2;
6524 if (ST.c1 == CHRTEST_VOID || could_match) {
6525 CURLY_SETPAREN(ST.paren, ST.count);
6526 PUSH_STATE_GOTO(CURLY_B_max, ST.B, locinput);
6527 assert(0); /* NOTREACHED */
6532 case CURLY_B_max_fail:
6533 /* failed to find B in a greedy match */
6535 REGCP_UNWIND(ST.cp);
6537 UNWIND_PAREN(ST.lastparen, ST.lastcloseparen);
6540 if (--ST.count < ST.min)
6542 locinput = HOPc(locinput, -1);
6543 goto curly_try_B_max;
6547 case END: /* last op of main pattern */
6550 /* we've just finished A in /(??{A})B/; now continue with B */
6552 st->u.eval.prev_rex = rex_sv; /* inner */
6554 /* Save *all* the positions. */
6555 st->u.eval.cp = regcppush(rex, 0, maxopenparen);
6556 rex_sv = cur_eval->u.eval.prev_rex;
6557 is_utf8_pat = reginfo->is_utf8_pat = cBOOL(RX_UTF8(rex_sv));
6558 SET_reg_curpm(rex_sv);
6559 rex = ReANY(rex_sv);
6560 rexi = RXi_GET(rex);
6561 cur_curlyx = cur_eval->u.eval.prev_curlyx;
6563 REGCP_SET(st->u.eval.lastcp);
6565 /* Restore parens of the outer rex without popping the
6567 S_regcp_restore(aTHX_ rex, cur_eval->u.eval.lastcp,
6570 st->u.eval.prev_eval = cur_eval;
6571 cur_eval = cur_eval->u.eval.prev_eval;
6573 PerlIO_printf(Perl_debug_log, "%*s EVAL trying tail ... %"UVxf"\n",
6574 REPORT_CODE_OFF+depth*2, "",PTR2UV(cur_eval)););
6575 if ( nochange_depth )
6578 PUSH_YES_STATE_GOTO(EVAL_AB, st->u.eval.prev_eval->u.eval.B,
6579 locinput); /* match B */
6582 if (locinput < reginfo->till) {
6583 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
6584 "%sMatch possible, but length=%ld is smaller than requested=%ld, failing!%s\n",
6586 (long)(locinput - startpos),
6587 (long)(reginfo->till - startpos),
6590 sayNO_SILENT; /* Cannot match: too short. */
6592 sayYES; /* Success! */
6594 case SUCCEED: /* successful SUSPEND/UNLESSM/IFMATCH/CURLYM */
6596 PerlIO_printf(Perl_debug_log,
6597 "%*s %ssubpattern success...%s\n",
6598 REPORT_CODE_OFF+depth*2, "", PL_colors[4], PL_colors[5]));
6599 sayYES; /* Success! */
6602 #define ST st->u.ifmatch
6607 case SUSPEND: /* (?>A) */
6609 newstart = locinput;
6612 case UNLESSM: /* -ve lookaround: (?!A), or with flags, (?<!A) */
6614 goto ifmatch_trivial_fail_test;
6616 case IFMATCH: /* +ve lookaround: (?=A), or with flags, (?<=A) */
6618 ifmatch_trivial_fail_test:
6620 char * const s = HOPBACKc(locinput, scan->flags);
6625 sw = 1 - cBOOL(ST.wanted);
6629 next = scan + ARG(scan);
6637 newstart = locinput;
6641 ST.logical = logical;
6642 logical = 0; /* XXX: reset state of logical once it has been saved into ST */
6644 /* execute body of (?...A) */
6645 PUSH_YES_STATE_GOTO(IFMATCH_A, NEXTOPER(NEXTOPER(scan)), newstart);
6646 assert(0); /* NOTREACHED */
6649 case IFMATCH_A_fail: /* body of (?...A) failed */
6650 ST.wanted = !ST.wanted;
6653 case IFMATCH_A: /* body of (?...A) succeeded */
6655 sw = cBOOL(ST.wanted);
6657 else if (!ST.wanted)
6660 if (OP(ST.me) != SUSPEND) {
6661 /* restore old position except for (?>...) */
6662 locinput = st->locinput;
6664 scan = ST.me + ARG(ST.me);
6667 continue; /* execute B */
6671 case LONGJMP: /* alternative with many branches compiles to
6672 * (BRANCHJ; EXACT ...; LONGJMP ) x N */
6673 next = scan + ARG(scan);
6678 case COMMIT: /* (*COMMIT) */
6679 reginfo->cutpoint = reginfo->strend;
6682 case PRUNE: /* (*PRUNE) */
6684 sv_yes_mark = sv_commit = MUTABLE_SV(rexi->data->data[ ARG( scan ) ]);
6685 PUSH_STATE_GOTO(COMMIT_next, next, locinput);
6686 assert(0); /* NOTREACHED */
6688 case COMMIT_next_fail:
6692 case OPFAIL: /* (*FAIL) */
6694 assert(0); /* NOTREACHED */
6696 #define ST st->u.mark
6697 case MARKPOINT: /* (*MARK:foo) */
6698 ST.prev_mark = mark_state;
6699 ST.mark_name = sv_commit = sv_yes_mark
6700 = MUTABLE_SV(rexi->data->data[ ARG( scan ) ]);
6702 ST.mark_loc = locinput;
6703 PUSH_YES_STATE_GOTO(MARKPOINT_next, next, locinput);
6704 assert(0); /* NOTREACHED */
6706 case MARKPOINT_next:
6707 mark_state = ST.prev_mark;
6709 assert(0); /* NOTREACHED */
6711 case MARKPOINT_next_fail:
6712 if (popmark && sv_eq(ST.mark_name,popmark))
6714 if (ST.mark_loc > startpoint)
6715 reginfo->cutpoint = HOPBACKc(ST.mark_loc, 1);
6716 popmark = NULL; /* we found our mark */
6717 sv_commit = ST.mark_name;
6720 PerlIO_printf(Perl_debug_log,
6721 "%*s %ssetting cutpoint to mark:%"SVf"...%s\n",
6722 REPORT_CODE_OFF+depth*2, "",
6723 PL_colors[4], SVfARG(sv_commit), PL_colors[5]);
6726 mark_state = ST.prev_mark;
6727 sv_yes_mark = mark_state ?
6728 mark_state->u.mark.mark_name : NULL;
6730 assert(0); /* NOTREACHED */
6732 case SKIP: /* (*SKIP) */
6734 /* (*SKIP) : if we fail we cut here*/
6735 ST.mark_name = NULL;
6736 ST.mark_loc = locinput;
6737 PUSH_STATE_GOTO(SKIP_next,next, locinput);
6739 /* (*SKIP:NAME) : if there is a (*MARK:NAME) fail where it was,
6740 otherwise do nothing. Meaning we need to scan
6742 regmatch_state *cur = mark_state;
6743 SV *find = MUTABLE_SV(rexi->data->data[ ARG( scan ) ]);
6746 if ( sv_eq( cur->u.mark.mark_name,
6749 ST.mark_name = find;
6750 PUSH_STATE_GOTO( SKIP_next, next, locinput);
6752 cur = cur->u.mark.prev_mark;
6755 /* Didn't find our (*MARK:NAME) so ignore this (*SKIP:NAME) */
6758 case SKIP_next_fail:
6760 /* (*CUT:NAME) - Set up to search for the name as we
6761 collapse the stack*/
6762 popmark = ST.mark_name;
6764 /* (*CUT) - No name, we cut here.*/
6765 if (ST.mark_loc > startpoint)
6766 reginfo->cutpoint = HOPBACKc(ST.mark_loc, 1);
6767 /* but we set sv_commit to latest mark_name if there
6768 is one so they can test to see how things lead to this
6771 sv_commit=mark_state->u.mark.mark_name;
6775 assert(0); /* NOTREACHED */
6778 case LNBREAK: /* \R */
6779 if ((n=is_LNBREAK_safe(locinput, reginfo->strend, utf8_target))) {
6786 PerlIO_printf(Perl_error_log, "%"UVxf" %d\n",
6787 PTR2UV(scan), OP(scan));
6788 Perl_croak(aTHX_ "regexp memory corruption");
6790 /* this is a point to jump to in order to increment
6791 * locinput by one character */
6793 assert(!NEXTCHR_IS_EOS);
6795 locinput += PL_utf8skip[nextchr];
6796 /* locinput is allowed to go 1 char off the end, but not 2+ */
6797 if (locinput > reginfo->strend)
6806 /* switch break jumps here */
6807 scan = next; /* prepare to execute the next op and ... */
6808 continue; /* ... jump back to the top, reusing st */
6809 assert(0); /* NOTREACHED */
6812 /* push a state that backtracks on success */
6813 st->u.yes.prev_yes_state = yes_state;
6817 /* push a new regex state, then continue at scan */
6819 regmatch_state *newst;
6822 regmatch_state *cur = st;
6823 regmatch_state *curyes = yes_state;
6825 regmatch_slab *slab = PL_regmatch_slab;
6826 for (;curd > -1;cur--,curd--) {
6827 if (cur < SLAB_FIRST(slab)) {
6829 cur = SLAB_LAST(slab);
6831 PerlIO_printf(Perl_error_log, "%*s#%-3d %-10s %s\n",
6832 REPORT_CODE_OFF + 2 + depth * 2,"",
6833 curd, PL_reg_name[cur->resume_state],
6834 (curyes == cur) ? "yes" : ""
6837 curyes = cur->u.yes.prev_yes_state;
6840 DEBUG_STATE_pp("push")
6843 st->locinput = locinput;
6845 if (newst > SLAB_LAST(PL_regmatch_slab))
6846 newst = S_push_slab(aTHX);
6847 PL_regmatch_state = newst;
6849 locinput = pushinput;
6852 assert(0); /* NOTREACHED */
6857 * We get here only if there's trouble -- normally "case END" is
6858 * the terminating point.
6860 Perl_croak(aTHX_ "corrupted regexp pointers");
6866 /* we have successfully completed a subexpression, but we must now
6867 * pop to the state marked by yes_state and continue from there */
6868 assert(st != yes_state);
6870 while (st != yes_state) {
6872 if (st < SLAB_FIRST(PL_regmatch_slab)) {
6873 PL_regmatch_slab = PL_regmatch_slab->prev;
6874 st = SLAB_LAST(PL_regmatch_slab);
6878 DEBUG_STATE_pp("pop (no final)");
6880 DEBUG_STATE_pp("pop (yes)");
6886 while (yes_state < SLAB_FIRST(PL_regmatch_slab)
6887 || yes_state > SLAB_LAST(PL_regmatch_slab))
6889 /* not in this slab, pop slab */
6890 depth -= (st - SLAB_FIRST(PL_regmatch_slab) + 1);
6891 PL_regmatch_slab = PL_regmatch_slab->prev;
6892 st = SLAB_LAST(PL_regmatch_slab);
6894 depth -= (st - yes_state);
6897 yes_state = st->u.yes.prev_yes_state;
6898 PL_regmatch_state = st;
6901 locinput= st->locinput;
6902 state_num = st->resume_state + no_final;
6903 goto reenter_switch;
6906 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "%sMatch successful!%s\n",
6907 PL_colors[4], PL_colors[5]));
6909 if (reginfo->info_aux_eval) {
6910 /* each successfully executed (?{...}) block does the equivalent of
6911 * local $^R = do {...}
6912 * When popping the save stack, all these locals would be undone;
6913 * bypass this by setting the outermost saved $^R to the latest
6915 /* I dont know if this is needed or works properly now.
6916 * see code related to PL_replgv elsewhere in this file.
6919 if (oreplsv != GvSV(PL_replgv))
6920 sv_setsv(oreplsv, GvSV(PL_replgv));
6927 PerlIO_printf(Perl_debug_log,
6928 "%*s %sfailed...%s\n",
6929 REPORT_CODE_OFF+depth*2, "",
6930 PL_colors[4], PL_colors[5])
6942 /* there's a previous state to backtrack to */
6944 if (st < SLAB_FIRST(PL_regmatch_slab)) {
6945 PL_regmatch_slab = PL_regmatch_slab->prev;
6946 st = SLAB_LAST(PL_regmatch_slab);
6948 PL_regmatch_state = st;
6949 locinput= st->locinput;
6951 DEBUG_STATE_pp("pop");
6953 if (yes_state == st)
6954 yes_state = st->u.yes.prev_yes_state;
6956 state_num = st->resume_state + 1; /* failure = success + 1 */
6957 goto reenter_switch;
6962 if (rex->intflags & PREGf_VERBARG_SEEN) {
6963 SV *sv_err = get_sv("REGERROR", 1);
6964 SV *sv_mrk = get_sv("REGMARK", 1);
6966 sv_commit = &PL_sv_no;
6968 sv_yes_mark = &PL_sv_yes;
6971 sv_commit = &PL_sv_yes;
6972 sv_yes_mark = &PL_sv_no;
6974 sv_setsv(sv_err, sv_commit);
6975 sv_setsv(sv_mrk, sv_yes_mark);
6979 if (last_pushed_cv) {
6982 PERL_UNUSED_VAR(SP);
6985 assert(!result || locinput - reginfo->strbeg >= 0);
6986 return result ? locinput - reginfo->strbeg : -1;
6990 - regrepeat - repeatedly match something simple, report how many
6992 * What 'simple' means is a node which can be the operand of a quantifier like
6995 * startposp - pointer a pointer to the start position. This is updated
6996 * to point to the byte following the highest successful
6998 * p - the regnode to be repeatedly matched against.
6999 * reginfo - struct holding match state, such as strend
7000 * max - maximum number of things to match.
7001 * depth - (for debugging) backtracking depth.
7004 S_regrepeat(pTHX_ regexp *prog, char **startposp, const regnode *p,
7005 regmatch_info *const reginfo, I32 max, int depth)
7008 char *scan; /* Pointer to current position in target string */
7010 char *loceol = reginfo->strend; /* local version */
7011 I32 hardcount = 0; /* How many matches so far */
7012 bool utf8_target = reginfo->is_utf8_target;
7013 int to_complement = 0; /* Invert the result? */
7015 _char_class_number classnum;
7017 PERL_UNUSED_ARG(depth);
7020 PERL_ARGS_ASSERT_REGREPEAT;
7023 if (max == REG_INFTY)
7025 else if (! utf8_target && loceol - scan > max)
7026 loceol = scan + max;
7028 /* Here, for the case of a non-UTF-8 target we have adjusted <loceol> down
7029 * to the maximum of how far we should go in it (leaving it set to the real
7030 * end, if the maximum permissible would take us beyond that). This allows
7031 * us to make the loop exit condition that we haven't gone past <loceol> to
7032 * also mean that we haven't exceeded the max permissible count, saving a
7033 * test each time through the loop. But it assumes that the OP matches a
7034 * single byte, which is true for most of the OPs below when applied to a
7035 * non-UTF-8 target. Those relatively few OPs that don't have this
7036 * characteristic will have to compensate.
7038 * There is no adjustment for UTF-8 targets, as the number of bytes per
7039 * character varies. OPs will have to test both that the count is less
7040 * than the max permissible (using <hardcount> to keep track), and that we
7041 * are still within the bounds of the string (using <loceol>. A few OPs
7042 * match a single byte no matter what the encoding. They can omit the max
7043 * test if, for the UTF-8 case, they do the adjustment that was skipped
7046 * Thus, the code above sets things up for the common case; and exceptional
7047 * cases need extra work; the common case is to make sure <scan> doesn't
7048 * go past <loceol>, and for UTF-8 to also use <hardcount> to make sure the
7049 * count doesn't exceed the maximum permissible */
7054 while (scan < loceol && hardcount < max && *scan != '\n') {
7055 scan += UTF8SKIP(scan);
7059 while (scan < loceol && *scan != '\n')
7065 while (scan < loceol && hardcount < max) {
7066 scan += UTF8SKIP(scan);
7073 case CANY: /* Move <scan> forward <max> bytes, unless goes off end */
7074 if (utf8_target && loceol - scan > max) {
7076 /* <loceol> hadn't been adjusted in the UTF-8 case */
7084 assert(STR_LEN(p) == reginfo->is_utf8_pat ? UTF8SKIP(STRING(p)) : 1);
7088 /* Can use a simple loop if the pattern char to match on is invariant
7089 * under UTF-8, or both target and pattern aren't UTF-8. Note that we
7090 * can use UTF8_IS_INVARIANT() even if the pattern isn't UTF-8, as it's
7091 * true iff it doesn't matter if the argument is in UTF-8 or not */
7092 if (UTF8_IS_INVARIANT(c) || (! utf8_target && ! reginfo->is_utf8_pat)) {
7093 if (utf8_target && loceol - scan > max) {
7094 /* We didn't adjust <loceol> because is UTF-8, but ok to do so,
7095 * since here, to match at all, 1 char == 1 byte */
7096 loceol = scan + max;
7098 while (scan < loceol && UCHARAT(scan) == c) {
7102 else if (reginfo->is_utf8_pat) {
7104 STRLEN scan_char_len;
7106 /* When both target and pattern are UTF-8, we have to do
7108 while (hardcount < max
7110 && (scan_char_len = UTF8SKIP(scan)) <= STR_LEN(p)
7111 && memEQ(scan, STRING(p), scan_char_len))
7113 scan += scan_char_len;
7117 else if (! UTF8_IS_ABOVE_LATIN1(c)) {
7119 /* Target isn't utf8; convert the character in the UTF-8
7120 * pattern to non-UTF8, and do a simple loop */
7121 c = TWO_BYTE_UTF8_TO_NATIVE(c, *(STRING(p) + 1));
7122 while (scan < loceol && UCHARAT(scan) == c) {
7125 } /* else pattern char is above Latin1, can't possibly match the
7130 /* Here, the string must be utf8; pattern isn't, and <c> is
7131 * different in utf8 than not, so can't compare them directly.
7132 * Outside the loop, find the two utf8 bytes that represent c, and
7133 * then look for those in sequence in the utf8 string */
7134 U8 high = UTF8_TWO_BYTE_HI(c);
7135 U8 low = UTF8_TWO_BYTE_LO(c);
7137 while (hardcount < max
7138 && scan + 1 < loceol
7139 && UCHARAT(scan) == high
7140 && UCHARAT(scan + 1) == low)
7148 case EXACTFA_NO_TRIE: /* This node only generated for non-utf8 patterns */
7149 assert(! reginfo->is_utf8_pat);
7152 utf8_flags = FOLDEQ_UTF8_NOMIX_ASCII;
7156 RXp_MATCH_TAINTED_on(prog);
7157 utf8_flags = FOLDEQ_LOCALE;
7160 case EXACTF: /* This node only generated for non-utf8 patterns */
7161 assert(! reginfo->is_utf8_pat);
7167 utf8_flags = reginfo->is_utf8_pat ? FOLDEQ_S2_ALREADY_FOLDED : 0;
7171 U8 c1_utf8[UTF8_MAXBYTES+1], c2_utf8[UTF8_MAXBYTES+1];
7173 assert(STR_LEN(p) == reginfo->is_utf8_pat ? UTF8SKIP(STRING(p)) : 1);
7175 if (S_setup_EXACTISH_ST_c1_c2(aTHX_ p, &c1, c1_utf8, &c2, c2_utf8,
7178 if (c1 == CHRTEST_VOID) {
7179 /* Use full Unicode fold matching */
7180 char *tmpeol = reginfo->strend;
7181 STRLEN pat_len = reginfo->is_utf8_pat ? UTF8SKIP(STRING(p)) : 1;
7182 while (hardcount < max
7183 && foldEQ_utf8_flags(scan, &tmpeol, 0, utf8_target,
7184 STRING(p), NULL, pat_len,
7185 reginfo->is_utf8_pat, utf8_flags))
7188 tmpeol = reginfo->strend;
7192 else if (utf8_target) {
7194 while (scan < loceol
7196 && memEQ(scan, c1_utf8, UTF8SKIP(scan)))
7198 scan += UTF8SKIP(scan);
7203 while (scan < loceol
7205 && (memEQ(scan, c1_utf8, UTF8SKIP(scan))
7206 || memEQ(scan, c2_utf8, UTF8SKIP(scan))))
7208 scan += UTF8SKIP(scan);
7213 else if (c1 == c2) {
7214 while (scan < loceol && UCHARAT(scan) == c1) {
7219 while (scan < loceol &&
7220 (UCHARAT(scan) == c1 || UCHARAT(scan) == c2))
7230 while (hardcount < max
7232 && reginclass(prog, p, (U8*)scan, (U8*) loceol, utf8_target))
7234 scan += UTF8SKIP(scan);
7238 while (scan < loceol && REGINCLASS(prog, p, (U8*)scan))
7243 /* The argument (FLAGS) to all the POSIX node types is the class number */
7250 RXp_MATCH_TAINTED_on(prog);
7251 if (! utf8_target) {
7252 while (scan < loceol && to_complement ^ cBOOL(isFOO_lc(FLAGS(p),
7258 while (hardcount < max && scan < loceol
7259 && to_complement ^ cBOOL(isFOO_utf8_lc(FLAGS(p),
7262 scan += UTF8SKIP(scan);
7275 if (utf8_target && loceol - scan > max) {
7277 /* We didn't adjust <loceol> at the beginning of this routine
7278 * because is UTF-8, but it is actually ok to do so, since here, to
7279 * match, 1 char == 1 byte. */
7280 loceol = scan + max;
7282 while (scan < loceol && _generic_isCC_A((U8) *scan, FLAGS(p))) {
7295 if (! utf8_target) {
7296 while (scan < loceol && ! _generic_isCC_A((U8) *scan, FLAGS(p))) {
7302 /* The complement of something that matches only ASCII matches all
7303 * UTF-8 variant code points, plus everything in ASCII that isn't
7305 while (hardcount < max && scan < loceol
7306 && (! UTF8_IS_INVARIANT(*scan)
7307 || ! _generic_isCC_A((U8) *scan, FLAGS(p))))
7309 scan += UTF8SKIP(scan);
7320 if (! utf8_target) {
7321 while (scan < loceol && to_complement
7322 ^ cBOOL(_generic_isCC((U8) *scan, FLAGS(p))))
7329 classnum = (_char_class_number) FLAGS(p);
7330 if (classnum < _FIRST_NON_SWASH_CC) {
7332 /* Here, a swash is needed for above-Latin1 code points.
7333 * Process as many Latin1 code points using the built-in rules.
7334 * Go to another loop to finish processing upon encountering
7335 * the first Latin1 code point. We could do that in this loop
7336 * as well, but the other way saves having to test if the swash
7337 * has been loaded every time through the loop: extra space to
7339 while (hardcount < max && scan < loceol) {
7340 if (UTF8_IS_INVARIANT(*scan)) {
7341 if (! (to_complement ^ cBOOL(_generic_isCC((U8) *scan,
7348 else if (UTF8_IS_DOWNGRADEABLE_START(*scan)) {
7349 if (! (to_complement
7350 ^ cBOOL(_generic_isCC(TWO_BYTE_UTF8_TO_NATIVE(*scan,
7359 goto found_above_latin1;
7366 /* For these character classes, the knowledge of how to handle
7367 * every code point is compiled in to Perl via a macro. This
7368 * code is written for making the loops as tight as possible.
7369 * It could be refactored to save space instead */
7371 case _CC_ENUM_SPACE: /* XXX would require separate code
7372 if we revert the change of \v
7375 case _CC_ENUM_PSXSPC:
7376 while (hardcount < max
7378 && (to_complement ^ cBOOL(isSPACE_utf8(scan))))
7380 scan += UTF8SKIP(scan);
7384 case _CC_ENUM_BLANK:
7385 while (hardcount < max
7387 && (to_complement ^ cBOOL(isBLANK_utf8(scan))))
7389 scan += UTF8SKIP(scan);
7393 case _CC_ENUM_XDIGIT:
7394 while (hardcount < max
7396 && (to_complement ^ cBOOL(isXDIGIT_utf8(scan))))
7398 scan += UTF8SKIP(scan);
7402 case _CC_ENUM_VERTSPACE:
7403 while (hardcount < max
7405 && (to_complement ^ cBOOL(isVERTWS_utf8(scan))))
7407 scan += UTF8SKIP(scan);
7411 case _CC_ENUM_CNTRL:
7412 while (hardcount < max
7414 && (to_complement ^ cBOOL(isCNTRL_utf8(scan))))
7416 scan += UTF8SKIP(scan);
7421 Perl_croak(aTHX_ "panic: regrepeat() node %d='%s' has an unexpected character class '%d'", OP(p), PL_reg_name[OP(p)], classnum);
7427 found_above_latin1: /* Continuation of POSIXU and NPOSIXU */
7429 /* Load the swash if not already present */
7430 if (! PL_utf8_swash_ptrs[classnum]) {
7431 U8 flags = _CORE_SWASH_INIT_ACCEPT_INVLIST;
7432 PL_utf8_swash_ptrs[classnum] = _core_swash_init(
7436 PL_XPosix_ptrs[classnum], &flags);
7439 while (hardcount < max && scan < loceol
7440 && to_complement ^ cBOOL(_generic_utf8(
7443 swash_fetch(PL_utf8_swash_ptrs[classnum],
7447 scan += UTF8SKIP(scan);
7454 while (hardcount < max && scan < loceol &&
7455 (c=is_LNBREAK_utf8_safe(scan, loceol))) {
7460 /* LNBREAK can match one or two latin chars, which is ok, but we
7461 * have to use hardcount in this situation, and throw away the
7462 * adjustment to <loceol> done before the switch statement */
7463 loceol = reginfo->strend;
7464 while (scan < loceol && (c=is_LNBREAK_latin1_safe(scan, loceol))) {
7485 /* These are all 0 width, so match right here or not at all. */
7489 Perl_croak(aTHX_ "panic: regrepeat() called with unrecognized node type %d='%s'", OP(p), PL_reg_name[OP(p)]);
7490 assert(0); /* NOTREACHED */
7497 c = scan - *startposp;
7501 GET_RE_DEBUG_FLAGS_DECL;
7503 SV * const prop = sv_newmortal();
7504 regprop(prog, prop, p);
7505 PerlIO_printf(Perl_debug_log,
7506 "%*s %s can match %"IVdf" times out of %"IVdf"...\n",
7507 REPORT_CODE_OFF + depth*2, "", SvPVX_const(prop),(IV)c,(IV)max);
7515 #if !defined(PERL_IN_XSUB_RE) || defined(PLUGGABLE_RE_EXTENSION)
7517 - regclass_swash - prepare the utf8 swash. Wraps the shared core version to
7518 create a copy so that changes the caller makes won't change the shared one.
7519 If <altsvp> is non-null, will return NULL in it, for back-compat.
7522 Perl_regclass_swash(pTHX_ const regexp *prog, const regnode* node, bool doinit, SV** listsvp, SV **altsvp)
7524 PERL_ARGS_ASSERT_REGCLASS_SWASH;
7530 return newSVsv(core_regclass_swash(prog, node, doinit, listsvp));
7535 S_core_regclass_swash(pTHX_ const regexp *prog, const regnode* node, bool doinit, SV** listsvp)
7537 /* Returns the swash for the input 'node' in the regex 'prog'.
7538 * If <doinit> is 'true', will attempt to create the swash if not already
7540 * If <listsvp> is non-null, will return the printable contents of the
7541 * swash. This can be used to get debugging information even before the
7542 * swash exists, by calling this function with 'doinit' set to false, in
7543 * which case the components that will be used to eventually create the
7544 * swash are returned (in a printable form).
7545 * Tied intimately to how regcomp.c sets up the data structure */
7549 SV *si = NULL; /* Input swash initialization string */
7552 RXi_GET_DECL(prog,progi);
7553 const struct reg_data * const data = prog ? progi->data : NULL;
7555 PERL_ARGS_ASSERT_CORE_REGCLASS_SWASH;
7557 assert(ANYOF_NONBITMAP(node));
7559 if (data && data->count) {
7560 const U32 n = ARG(node);
7562 if (data->what[n] == 's') {
7563 SV * const rv = MUTABLE_SV(data->data[n]);
7564 AV * const av = MUTABLE_AV(SvRV(rv));
7565 SV **const ary = AvARRAY(av);
7566 U8 swash_init_flags = _CORE_SWASH_INIT_ACCEPT_INVLIST;
7568 si = *ary; /* ary[0] = the string to initialize the swash with */
7570 /* Elements 2 and 3 are either both present or both absent. [2] is
7571 * any inversion list generated at compile time; [3] indicates if
7572 * that inversion list has any user-defined properties in it. */
7573 if (av_len(av) >= 2) {
7576 swash_init_flags |= _CORE_SWASH_INIT_USER_DEFINED_PROPERTY;
7583 /* Element [1] is reserved for the set-up swash. If already there,
7584 * return it; if not, create it and store it there */
7585 if (ary[1] && SvROK(ary[1])) {
7588 else if (si && doinit) {
7590 sw = _core_swash_init("utf8", /* the utf8 package */
7594 0, /* not from tr/// */
7597 (void)av_store(av, 1, sw);
7602 /* If requested, return a printable version of what this swash matches */
7604 SV* matches_string = newSVpvn("", 0);
7606 /* The swash should be used, if possible, to get the data, as it
7607 * contains the resolved data. But this function can be called at
7608 * compile-time, before everything gets resolved, in which case we
7609 * return the currently best available information, which is the string
7610 * that will eventually be used to do that resolving, 'si' */
7611 if ((! sw || (invlist = _get_swash_invlist(sw)) == NULL)
7612 && (si && si != &PL_sv_undef))
7614 sv_catsv(matches_string, si);
7617 /* Add the inversion list to whatever we have. This may have come from
7618 * the swash, or from an input parameter */
7620 sv_catsv(matches_string, _invlist_contents(invlist));
7622 *listsvp = matches_string;
7629 - reginclass - determine if a character falls into a character class
7631 n is the ANYOF regnode
7632 p is the target string
7633 p_end points to one byte beyond the end of the target string
7634 utf8_target tells whether p is in UTF-8.
7636 Returns true if matched; false otherwise.
7638 Note that this can be a synthetic start class, a combination of various
7639 nodes, so things you think might be mutually exclusive, such as locale,
7640 aren't. It can match both locale and non-locale
7645 S_reginclass(pTHX_ regexp * const prog, const regnode * const n, const U8* const p, const U8* const p_end, const bool utf8_target)
7648 const char flags = ANYOF_FLAGS(n);
7652 PERL_ARGS_ASSERT_REGINCLASS;
7654 /* If c is not already the code point, get it. Note that
7655 * UTF8_IS_INVARIANT() works even if not in UTF-8 */
7656 if (! UTF8_IS_INVARIANT(c) && utf8_target) {
7658 c = utf8n_to_uvchr(p, p_end - p, &c_len,
7659 (UTF8_ALLOW_DEFAULT & UTF8_ALLOW_ANYUV)
7660 | UTF8_ALLOW_FFFF | UTF8_CHECK_ONLY);
7661 /* see [perl #37836] for UTF8_ALLOW_ANYUV; [perl #38293] for
7662 * UTF8_ALLOW_FFFF */
7663 if (c_len == (STRLEN)-1)
7664 Perl_croak(aTHX_ "Malformed UTF-8 character (fatal)");
7667 /* If this character is potentially in the bitmap, check it */
7669 if (ANYOF_BITMAP_TEST(n, c))
7671 else if (flags & ANYOF_NON_UTF8_NON_ASCII_ALL
7677 else if (flags & ANYOF_LOCALE) {
7678 if (flags & ANYOF_LOC_FOLD) {
7679 RXp_MATCH_TAINTED_on(prog);
7680 if (ANYOF_BITMAP_TEST(n, PL_fold_locale[c])) {
7684 if (! match && ANYOF_POSIXL_TEST_ANY_SET(n)) {
7686 /* The data structure is arranged so bits 0, 2, 4, ... are set
7687 * if the class includes the Posix character class given by
7688 * bit/2; and 1, 3, 5, ... are set if the class includes the
7689 * complemented Posix class given by int(bit/2). So we loop
7690 * through the bits, each time changing whether we complement
7691 * the result or not. Suppose for the sake of illustration
7692 * that bits 0-3 mean respectively, \w, \W, \s, \S. If bit 0
7693 * is set, it means there is a match for this ANYOF node if the
7694 * character is in the class given by the expression (0 / 2 = 0
7695 * = \w). If it is in that class, isFOO_lc() will return 1,
7696 * and since 'to_complement' is 0, the result will stay TRUE,
7697 * and we exit the loop. Suppose instead that bit 0 is 0, but
7698 * bit 1 is 1. That means there is a match if the character
7699 * matches \W. We won't bother to call isFOO_lc() on bit 0,
7700 * but will on bit 1. On the second iteration 'to_complement'
7701 * will be 1, so the exclusive or will reverse things, so we
7702 * are testing for \W. On the third iteration, 'to_complement'
7703 * will be 0, and we would be testing for \s; the fourth
7704 * iteration would test for \S, etc.
7706 * Note that this code assumes that all the classes are closed
7707 * under folding. For example, if a character matches \w, then
7708 * its fold does too; and vice versa. This should be true for
7709 * any well-behaved locale for all the currently defined Posix
7710 * classes, except for :lower: and :upper:, which are handled
7711 * by the pseudo-class :cased: which matches if either of the
7712 * other two does. To get rid of this assumption, an outer
7713 * loop could be used below to iterate over both the source
7714 * character, and its fold (if different) */
7717 int to_complement = 0;
7719 RXp_MATCH_TAINTED_on(prog);
7720 while (count < ANYOF_MAX) {
7721 if (ANYOF_POSIXL_TEST(n, count)
7722 && to_complement ^ cBOOL(isFOO_lc(count/2, (U8) c)))
7734 /* For /li matching and the current locale is a UTF-8 one, look at the
7735 * special list, valid for just these circumstances. */
7737 && (flags & ANYOF_LOC_FOLD)
7738 && IN_UTF8_CTYPE_LOCALE
7739 && ANYOF_UTF8_LOCALE_INVLIST(n))
7741 match = _invlist_contains_cp(ANYOF_UTF8_LOCALE_INVLIST(n), c);
7744 /* If the bitmap didn't (or couldn't) match, and something outside the
7745 * bitmap could match, try that. Locale nodes specify completely the
7746 * behavior of code points in the bit map (otherwise, a utf8 target would
7747 * cause them to be treated as Unicode and not locale), except in
7748 * the very unlikely event when this node is a synthetic start class, which
7749 * could be a combination of locale and non-locale nodes. So allow locale
7750 * to match for the synthetic start class, which will give a false
7751 * positive that will be resolved when the match is done again as not part
7752 * of the synthetic start class */
7754 if (c >= 256 && (flags & ANYOF_ABOVE_LATIN1_ALL)) {
7755 match = TRUE; /* Everything above 255 matches */
7757 else if (ANYOF_NONBITMAP(n)
7758 && ((flags & ANYOF_NONBITMAP_NON_UTF8)
7761 || (! (flags & ANYOF_LOCALE))
7762 || is_ANYOF_SYNTHETIC(n)))))
7764 SV * const sw = core_regclass_swash(prog, n, TRUE, 0);
7769 } else { /* Convert to utf8 */
7771 utf8_p = bytes_to_utf8(p, &len);
7774 if (swash_fetch(sw, utf8_p, TRUE)) {
7778 /* If we allocated a string above, free it */
7779 if (! utf8_target) Safefree(utf8_p);
7783 if (UNICODE_IS_SUPER(c)
7784 && (flags & ANYOF_WARN_SUPER)
7785 && ckWARN_d(WARN_NON_UNICODE))
7787 Perl_warner(aTHX_ packWARN(WARN_NON_UNICODE),
7788 "Matched non-Unicode code point 0x%04"UVXf" against Unicode property; may not be portable", c);
7792 #if ANYOF_INVERT != 1
7793 /* Depending on compiler optimization cBOOL takes time, so if don't have to
7795 # error ANYOF_INVERT needs to be set to 1, or guarded with cBOOL below,
7798 /* The xor complements the return if to invert: 1^1 = 0, 1^0 = 1 */
7799 return (flags & ANYOF_INVERT) ^ match;
7803 S_reghop3(U8 *s, SSize_t off, const U8* lim)
7805 /* return the position 'off' UTF-8 characters away from 's', forward if
7806 * 'off' >= 0, backwards if negative. But don't go outside of position
7807 * 'lim', which better be < s if off < 0 */
7811 PERL_ARGS_ASSERT_REGHOP3;
7814 while (off-- && s < lim) {
7815 /* XXX could check well-formedness here */
7820 while (off++ && s > lim) {
7822 if (UTF8_IS_CONTINUED(*s)) {
7823 while (s > lim && UTF8_IS_CONTINUATION(*s))
7826 /* XXX could check well-formedness here */
7833 S_reghop4(U8 *s, SSize_t off, const U8* llim, const U8* rlim)
7837 PERL_ARGS_ASSERT_REGHOP4;
7840 while (off-- && s < rlim) {
7841 /* XXX could check well-formedness here */
7846 while (off++ && s > llim) {
7848 if (UTF8_IS_CONTINUED(*s)) {
7849 while (s > llim && UTF8_IS_CONTINUATION(*s))
7852 /* XXX could check well-formedness here */
7859 S_reghopmaybe3(U8* s, SSize_t off, const U8* lim)
7863 PERL_ARGS_ASSERT_REGHOPMAYBE3;
7866 while (off-- && s < lim) {
7867 /* XXX could check well-formedness here */
7874 while (off++ && s > lim) {
7876 if (UTF8_IS_CONTINUED(*s)) {
7877 while (s > lim && UTF8_IS_CONTINUATION(*s))
7880 /* XXX could check well-formedness here */
7889 /* when executing a regex that may have (?{}), extra stuff needs setting
7890 up that will be visible to the called code, even before the current
7891 match has finished. In particular:
7893 * $_ is localised to the SV currently being matched;
7894 * pos($_) is created if necessary, ready to be updated on each call-out
7896 * a fake PMOP is created that can be set to PL_curpm (normally PL_curpm
7897 isn't set until the current pattern is successfully finished), so that
7898 $1 etc of the match-so-far can be seen;
7899 * save the old values of subbeg etc of the current regex, and set then
7900 to the current string (again, this is normally only done at the end
7905 S_setup_eval_state(pTHX_ regmatch_info *const reginfo)
7908 regexp *const rex = ReANY(reginfo->prog);
7909 regmatch_info_aux_eval *eval_state = reginfo->info_aux_eval;
7911 eval_state->rex = rex;
7914 /* Make $_ available to executed code. */
7915 if (reginfo->sv != DEFSV) {
7917 DEFSV_set(reginfo->sv);
7920 if (!(mg = mg_find_mglob(reginfo->sv))) {
7921 /* prepare for quick setting of pos */
7922 mg = sv_magicext_mglob(reginfo->sv);
7925 eval_state->pos_magic = mg;
7926 eval_state->pos = mg->mg_len;
7927 eval_state->pos_flags = mg->mg_flags;
7930 eval_state->pos_magic = NULL;
7932 if (!PL_reg_curpm) {
7933 /* PL_reg_curpm is a fake PMOP that we can attach the current
7934 * regex to and point PL_curpm at, so that $1 et al are visible
7935 * within a /(?{})/. It's just allocated once per interpreter the
7936 * first time its needed */
7937 Newxz(PL_reg_curpm, 1, PMOP);
7940 SV* const repointer = &PL_sv_undef;
7941 /* this regexp is also owned by the new PL_reg_curpm, which
7942 will try to free it. */
7943 av_push(PL_regex_padav, repointer);
7944 PL_reg_curpm->op_pmoffset = av_len(PL_regex_padav);
7945 PL_regex_pad = AvARRAY(PL_regex_padav);
7949 SET_reg_curpm(reginfo->prog);
7950 eval_state->curpm = PL_curpm;
7951 PL_curpm = PL_reg_curpm;
7952 if (RXp_MATCH_COPIED(rex)) {
7953 /* Here is a serious problem: we cannot rewrite subbeg,
7954 since it may be needed if this match fails. Thus
7955 $` inside (?{}) could fail... */
7956 eval_state->subbeg = rex->subbeg;
7957 eval_state->sublen = rex->sublen;
7958 eval_state->suboffset = rex->suboffset;
7959 eval_state->subcoffset = rex->subcoffset;
7961 eval_state->saved_copy = rex->saved_copy;
7963 RXp_MATCH_COPIED_off(rex);
7966 eval_state->subbeg = NULL;
7967 rex->subbeg = (char *)reginfo->strbeg;
7969 rex->subcoffset = 0;
7970 rex->sublen = reginfo->strend - reginfo->strbeg;
7974 /* destructor to clear up regmatch_info_aux and regmatch_info_aux_eval */
7977 S_cleanup_regmatch_info_aux(pTHX_ void *arg)
7980 regmatch_info_aux *aux = (regmatch_info_aux *) arg;
7981 regmatch_info_aux_eval *eval_state = aux->info_aux_eval;
7984 Safefree(aux->poscache);
7988 /* undo the effects of S_setup_eval_state() */
7990 if (eval_state->subbeg) {
7991 regexp * const rex = eval_state->rex;
7992 rex->subbeg = eval_state->subbeg;
7993 rex->sublen = eval_state->sublen;
7994 rex->suboffset = eval_state->suboffset;
7995 rex->subcoffset = eval_state->subcoffset;
7997 rex->saved_copy = eval_state->saved_copy;
7999 RXp_MATCH_COPIED_on(rex);
8001 if (eval_state->pos_magic)
8003 eval_state->pos_magic->mg_len = eval_state->pos;
8004 eval_state->pos_magic->mg_flags =
8005 (eval_state->pos_magic->mg_flags & ~MGf_BYTES)
8006 | (eval_state->pos_flags & MGf_BYTES);
8009 PL_curpm = eval_state->curpm;
8012 PL_regmatch_state = aux->old_regmatch_state;
8013 PL_regmatch_slab = aux->old_regmatch_slab;
8015 /* free all slabs above current one - this must be the last action
8016 * of this function, as aux and eval_state are allocated within
8017 * slabs and may be freed here */
8019 s = PL_regmatch_slab->next;
8021 PL_regmatch_slab->next = NULL;
8023 regmatch_slab * const osl = s;
8032 S_to_utf8_substr(pTHX_ regexp *prog)
8034 /* Converts substr fields in prog from bytes to UTF-8, calling fbm_compile
8035 * on the converted value */
8039 PERL_ARGS_ASSERT_TO_UTF8_SUBSTR;
8042 if (prog->substrs->data[i].substr
8043 && !prog->substrs->data[i].utf8_substr) {
8044 SV* const sv = newSVsv(prog->substrs->data[i].substr);
8045 prog->substrs->data[i].utf8_substr = sv;
8046 sv_utf8_upgrade(sv);
8047 if (SvVALID(prog->substrs->data[i].substr)) {
8048 if (SvTAIL(prog->substrs->data[i].substr)) {
8049 /* Trim the trailing \n that fbm_compile added last
8051 SvCUR_set(sv, SvCUR(sv) - 1);
8052 /* Whilst this makes the SV technically "invalid" (as its
8053 buffer is no longer followed by "\0") when fbm_compile()
8054 adds the "\n" back, a "\0" is restored. */
8055 fbm_compile(sv, FBMcf_TAIL);
8059 if (prog->substrs->data[i].substr == prog->check_substr)
8060 prog->check_utf8 = sv;
8066 S_to_byte_substr(pTHX_ regexp *prog)
8068 /* Converts substr fields in prog from UTF-8 to bytes, calling fbm_compile
8069 * on the converted value; returns FALSE if can't be converted. */
8074 PERL_ARGS_ASSERT_TO_BYTE_SUBSTR;
8077 if (prog->substrs->data[i].utf8_substr
8078 && !prog->substrs->data[i].substr) {
8079 SV* sv = newSVsv(prog->substrs->data[i].utf8_substr);
8080 if (! sv_utf8_downgrade(sv, TRUE)) {
8083 if (SvVALID(prog->substrs->data[i].utf8_substr)) {
8084 if (SvTAIL(prog->substrs->data[i].utf8_substr)) {
8085 /* Trim the trailing \n that fbm_compile added last
8087 SvCUR_set(sv, SvCUR(sv) - 1);
8088 fbm_compile(sv, FBMcf_TAIL);
8092 prog->substrs->data[i].substr = sv;
8093 if (prog->substrs->data[i].utf8_substr == prog->check_utf8)
8094 prog->check_substr = sv;
8103 * c-indentation-style: bsd
8105 * indent-tabs-mode: nil
8108 * ex: set ts=8 sts=4 sw=4 et:
https://perl5.git.perl.org / perl5.git / blob