regexec.c

   1 /*    regexec.c
   2  */
   3
   4 /*
   5  *      One Ring to rule them all, One Ring to find them
   6  &
   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"]
  10  */
  11
  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.
  15  *
  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.
  20  */
  21
  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!
  24  */
  25
  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.
  29  */
  30
  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.
  34 */
  35
  36 #ifdef PERL_EXT_RE_BUILD
  37 #include "re_top.h"
  38 #endif
  39
  40 /* At least one required character in the target string is expressible only in
  41  * UTF-8. */
  42 const char* const non_utf8_target_but_utf8_required
  43                 = "Can't match, because target string needs to be in UTF-8\n";
  44
  45 /*
  46  * pregcomp and pregexec -- regsub and regerror are not used in perl
  47  *
  48  *      Copyright (c) 1986 by University of Toronto.
  49  *      Written by Henry Spencer.  Not derived from licensed software.
  50  *
  51  *      Permission is granted to anyone to use this software for any
  52  *      purpose on any computer system, and to redistribute it freely,
  53  *      subject to the following restrictions:
  54  *
  55  *      1. The author is not responsible for the consequences of use of
  56  *              this software, no matter how awful, even if they arise
  57  *              from defects in it.
  58  *
  59  *      2. The origin of this software must not be misrepresented, either
  60  *              by explicit claim or by omission.
  61  *
  62  *      3. Altered versions must be plainly marked as such, and must not
  63  *              be misrepresented as being the original software.
  64  *
  65  ****    Alterations to Henry's code are...
  66  ****
  67  ****    Copyright (C) 1991, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999,
  68  ****    2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008
  69  ****    by Larry Wall and others
  70  ****
  71  ****    You may distribute under the terms of either the GNU General Public
  72  ****    License or the Artistic License, as specified in the README file.
  73  *
  74  * Beware that some of this code is subtly aware of the way operator
  75  * precedence is structured in regular expressions.  Serious changes in
  76  * regular-expression syntax might require a total rethink.
  77  */
  78 #include "EXTERN.h"
  79 #define PERL_IN_REGEXEC_C
  80 #include "perl.h"
  81
  82 #ifdef PERL_IN_XSUB_RE
  83 #  include "re_comp.h"
  84 #else
  85 #  include "regcomp.h"
  86 #endif
  87
  88 #include "inline_invlist.c"
  89 #include "unicode_constants.h"
  90
  91 #define RF_tainted      1       /* tainted information used? e.g. locale */
  92 #define RF_warned       2               /* warned about big count? */
  93
  94 #define RF_utf8         8               /* Pattern contains multibyte chars? */
  95
  96 #define UTF_PATTERN ((PL_reg_flags & RF_utf8) != 0)
  97
  98 #define HAS_NONLATIN1_FOLD_CLOSURE(i) _HAS_NONLATIN1_FOLD_CLOSURE_ONLY_FOR_USE_BY_REGCOMP_DOT_C_AND_REGEXEC_DOT_C(i)
  99
 100 #ifndef STATIC
 101 #define STATIC  static
 102 #endif
 103
 104 /* Valid for non-utf8 strings, non-ANYOFV nodes only: 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,0,0)   \
 108                                               : ANYOF_BITMAP_TEST(p,*(c)))
 109
 110 /*
 111  * Forwards.
 112  */
 113
 114 #define CHR_SVLEN(sv) (utf8_target ? sv_len_utf8(sv) : SvCUR(sv))
 115 #define CHR_DIST(a,b) (PL_reg_match_utf8 ? utf8_distance(a,b) : a - b)
 116
 117 #define HOPc(pos,off) \
 118         (char *)(PL_reg_match_utf8 \
 119             ? reghop3((U8*)pos, off, (U8*)(off >= 0 ? PL_regeol : PL_bostr)) \
 120             : (U8*)(pos + off))
 121 #define HOPBACKc(pos, off) \
 122         (char*)(PL_reg_match_utf8\
 123             ? reghopmaybe3((U8*)pos, -off, (U8*)PL_bostr) \
 124             : (pos - off >= PL_bostr)           \
 125                 ? (U8*)pos - off                \
 126                 : NULL)
 127
 128 #define HOP3(pos,off,lim) (PL_reg_match_utf8 ? reghop3((U8*)(pos), off, (U8*)(lim)) : (U8*)(pos + off))
 129 #define HOP3c(pos,off,lim) ((char*)HOP3(pos,off,lim))
 130
 131
 132 #define NEXTCHR_EOS -10 /* nextchr has fallen off the end */
 133 #define NEXTCHR_IS_EOS (nextchr < 0)
 134
 135 #define SET_nextchr \
 136     nextchr = ((locinput < PL_regeol) ? UCHARAT(locinput) : NEXTCHR_EOS)
 137
 138 #define SET_locinput(p) \
 139     locinput = (p);  \
 140     SET_nextchr
 141
 142
 143 /* these are unrolled below in the CCC_TRY_XXX defined */
 144 #define LOAD_UTF8_CHARCLASS(class,str) STMT_START { \
 145     if (!CAT2(PL_utf8_,class)) { \
 146         bool ok; \
 147         ENTER; save_re_context(); \
 148         ok=CAT2(is_utf8_,class)((const U8*)str); \
 149         PERL_UNUSED_VAR(ok); \
 150         assert(ok); assert(CAT2(PL_utf8_,class)); LEAVE; } } STMT_END
 151 /* Doesn't do an assert to verify that is correct */
 152 #define LOAD_UTF8_CHARCLASS_NO_CHECK(class) STMT_START { \
 153     if (!CAT2(PL_utf8_,class)) { \
 154         bool throw_away PERL_UNUSED_DECL; \
 155         ENTER; save_re_context(); \
 156         throw_away = CAT2(is_utf8_,class)((const U8*)" "); \
 157         LEAVE; } } STMT_END
 158
 159 #define LOAD_UTF8_CHARCLASS_ALNUM() LOAD_UTF8_CHARCLASS(alnum,"a")
 160 #define LOAD_UTF8_CHARCLASS_DIGIT() LOAD_UTF8_CHARCLASS(digit,"0")
 161 #define LOAD_UTF8_CHARCLASS_SPACE() LOAD_UTF8_CHARCLASS(space," ")
 162
 163 #define LOAD_UTF8_CHARCLASS_GCB()  /* Grapheme cluster boundaries */        \
 164         /* No asserts are done for some of these, in case called on a   */  \
 165         /* Unicode version in which they map to nothing */                  \
 166         LOAD_UTF8_CHARCLASS(X_regular_begin, HYPHEN_UTF8);                          \
 167         LOAD_UTF8_CHARCLASS(X_extend, COMBINING_GRAVE_ACCENT_UTF8);         \
 168
 169 #define PLACEHOLDER     /* Something for the preprocessor to grab onto */
 170
 171 /* The actual code for CCC_TRY, which uses several variables from the routine
 172  * it's callable from.  It is designed to be the bulk of a case statement.
 173  * FUNC is the macro or function to call on non-utf8 targets that indicate if
 174  *      nextchr matches the class.
 175  * UTF8_TEST is the whole test string to use for utf8 targets
 176  * LOAD is what to use to test, and if not present to load in the swash for the
 177  *      class
 178  * POS_OR_NEG is either empty or ! to complement the results of FUNC or
 179  *      UTF8_TEST test.
 180  * The logic is: Fail if we're at the end-of-string; otherwise if the target is
 181  * utf8 and a variant, load the swash if necessary and test using the utf8
 182  * test.  Advance to the next character if test is ok, otherwise fail; If not
 183  * utf8 or an invariant under utf8, use the non-utf8 test, and fail if it
 184  * fails, or advance to the next character */
 185
 186 #define _CCC_TRY_CODE(POS_OR_NEG, FUNC, UTF8_TEST, CLASS, STR)                \
 187     if (NEXTCHR_IS_EOS) {                                              \
 188         sayNO;                                                                \
 189     }                                                                         \
 190     if (utf8_target && UTF8_IS_CONTINUED(nextchr)) {                          \
 191         LOAD_UTF8_CHARCLASS(CLASS, STR);                                      \
 192         if (POS_OR_NEG (UTF8_TEST)) {                                         \
 193             sayNO;                                                            \
 194         }                                                                     \
 195     }                                                                         \
 196     else if (POS_OR_NEG (FUNC(nextchr))) {                                    \
 197             sayNO;                                                            \
 198     }                                                                         \
 199     goto increment_locinput;
 200
 201 /* Handle the non-locale cases for a character class and its complement.  It
 202  * calls _CCC_TRY_CODE with a ! to complement the test for the character class.
 203  * This is because that code fails when the test succeeds, so we want to have
 204  * the test fail so that the code succeeds.  The swash is stored in a
 205  * predictable PL_ place */
 206 #define _CCC_TRY_NONLOCALE(NAME,  NNAME,  FUNC,                               \
 207                            CLASS, STR)                                        \
 208     case NAME:                                                                \
 209         _CCC_TRY_CODE( !, FUNC,                                               \
 210                           cBOOL(swash_fetch(CAT2(PL_utf8_,CLASS),             \
 211                                             (U8*)locinput, TRUE)),            \
 212                           CLASS, STR)                                         \
 213     case NNAME:                                                               \
 214         _CCC_TRY_CODE(  PLACEHOLDER , FUNC,                                   \
 215                           cBOOL(swash_fetch(CAT2(PL_utf8_,CLASS),             \
 216                                             (U8*)locinput, TRUE)),            \
 217                           CLASS, STR)                                         \
 218
 219 /* Generate the case statements for both locale and non-locale character
 220  * classes in regmatch for classes that don't have special unicode semantics.
 221  * Locales don't use an immediate swash, but an intermediary special locale
 222  * function that is called on the pointer to the current place in the input
 223  * string.  That function will resolve to needing the same swash.  One might
 224  * think that because we don't know what the locale will match, we shouldn't
 225  * check with the swash loading function that it loaded properly; ie, that we
 226  * should use LOAD_UTF8_CHARCLASS_NO_CHECK for those, but what is passed to the
 227  * regular LOAD_UTF8_CHARCLASS is in non-locale terms, and so locale is
 228  * irrelevant here */
 229 #define CCC_TRY(NAME,  NNAME,  FUNC,                                          \
 230                 NAMEL, NNAMEL, LCFUNC, LCFUNC_utf8,                           \
 231                 NAMEA, NNAMEA, FUNCA,                                         \
 232                 CLASS, STR)                                                   \
 233     case NAMEL:                                                               \
 234         PL_reg_flags |= RF_tainted;                                           \
 235         _CCC_TRY_CODE( !, LCFUNC, LCFUNC_utf8((U8*)locinput), CLASS, STR)     \
 236     case NNAMEL:                                                              \
 237         PL_reg_flags |= RF_tainted;                                           \
 238         _CCC_TRY_CODE( PLACEHOLDER, LCFUNC, LCFUNC_utf8((U8*)locinput),       \
 239                        CLASS, STR)                                            \
 240     case NAMEA:                                                               \
 241         if (NEXTCHR_IS_EOS || ! FUNCA(nextchr)) {                      \
 242             sayNO;                                                            \
 243         }                                                                     \
 244         /* Matched a utf8-invariant, so don't have to worry about utf8 */     \
 245         locinput++;                                        \
 246         break;                                                                \
 247     case NNAMEA:                                                              \
 248         if (NEXTCHR_IS_EOS || FUNCA(nextchr)) {                        \
 249             sayNO;                                                            \
 250         }                                                                     \
 251         goto increment_locinput;                                              \
 252     /* Generate the non-locale cases */                                       \
 253     _CCC_TRY_NONLOCALE(NAME, NNAME, FUNC, CLASS, STR)
 254
 255 /* This is like CCC_TRY, but has an extra set of parameters for generating case
 256  * statements to handle separate Unicode semantics nodes */
 257 #define CCC_TRY_U(NAME,  NNAME,  FUNC,                                         \
 258                   NAMEL, NNAMEL, LCFUNC, LCFUNC_utf8,                          \
 259                   NAMEU, NNAMEU, FUNCU,                                        \
 260                   NAMEA, NNAMEA, FUNCA,                                        \
 261                   CLASS, STR)                                                  \
 262     CCC_TRY(NAME, NNAME, FUNC,                                                 \
 263             NAMEL, NNAMEL, LCFUNC, LCFUNC_utf8,                                \
 264             NAMEA, NNAMEA, FUNCA,                                              \
 265             CLASS, STR)                                                        \
 266     _CCC_TRY_NONLOCALE(NAMEU, NNAMEU, FUNCU, CLASS, STR)
 267
 268 /* TODO: Combine JUMPABLE and HAS_TEXT to cache OP(rn) */
 269
 270 /* for use after a quantifier and before an EXACT-like node -- japhy */
 271 /* it would be nice to rework regcomp.sym to generate this stuff. sigh
 272  *
 273  * NOTE that *nothing* that affects backtracking should be in here, specifically
 274  * VERBS must NOT be included. JUMPABLE is used to determine  if we can ignore a
 275  * node that is in between two EXACT like nodes when ascertaining what the required
 276  * "follow" character is. This should probably be moved to regex compile time
 277  * although it may be done at run time beause of the REF possibility - more
 278  * investigation required. -- demerphq
 279 */
 280 #define JUMPABLE(rn) (      \
 281     OP(rn) == OPEN ||       \
 282     (OP(rn) == CLOSE && (!cur_eval || cur_eval->u.eval.close_paren != ARG(rn))) || \
 283     OP(rn) == EVAL ||   \
 284     OP(rn) == SUSPEND || OP(rn) == IFMATCH || \
 285     OP(rn) == PLUS || OP(rn) == MINMOD || \
 286     OP(rn) == KEEPS || \
 287     (PL_regkind[OP(rn)] == CURLY && ARG1(rn) > 0) \
 288 )
 289 #define IS_EXACT(rn) (PL_regkind[OP(rn)] == EXACT)
 290
 291 #define HAS_TEXT(rn) ( IS_EXACT(rn) || PL_regkind[OP(rn)] == REF )
 292
 293 #if 0
 294 /* Currently these are only used when PL_regkind[OP(rn)] == EXACT so
 295    we don't need this definition. */
 296 #define IS_TEXT(rn)   ( OP(rn)==EXACT   || OP(rn)==REF   || OP(rn)==NREF   )
 297 #define IS_TEXTF(rn)  ( OP(rn)==EXACTFU || OP(rn)==EXACTFU_SS || OP(rn)==EXACTFU_TRICKYFOLD || OP(rn)==EXACTFA || OP(rn)==EXACTF || OP(rn)==REFF  || OP(rn)==NREFF )
 298 #define IS_TEXTFL(rn) ( OP(rn)==EXACTFL || OP(rn)==REFFL || OP(rn)==NREFFL )
 299
 300 #else
 301 /* ... so we use this as its faster. */
 302 #define IS_TEXT(rn)   ( OP(rn)==EXACT   )
 303 #define IS_TEXTFU(rn)  ( OP(rn)==EXACTFU || OP(rn)==EXACTFU_SS || OP(rn)==EXACTFU_TRICKYFOLD || OP(rn) == EXACTFA)
 304 #define IS_TEXTF(rn)  ( OP(rn)==EXACTF  )
 305 #define IS_TEXTFL(rn) ( OP(rn)==EXACTFL )
 306
 307 #endif
 308
 309 /*
 310   Search for mandatory following text node; for lookahead, the text must
 311   follow but for lookbehind (rn->flags != 0) we skip to the next step.
 312 */
 313 #define FIND_NEXT_IMPT(rn) STMT_START { \
 314     while (JUMPABLE(rn)) { \
 315         const OPCODE type = OP(rn); \
 316         if (type == SUSPEND || PL_regkind[type] == CURLY) \
 317             rn = NEXTOPER(NEXTOPER(rn)); \
 318         else if (type == PLUS) \
 319             rn = NEXTOPER(rn); \
 320         else if (type == IFMATCH) \
 321             rn = (rn->flags == 0) ? NEXTOPER(NEXTOPER(rn)) : rn + ARG(rn); \
 322         else rn += NEXT_OFF(rn); \
 323     } \
 324 } STMT_END
 325
 326
 327 static void restore_pos(pTHX_ void *arg);
 328
 329 #define REGCP_PAREN_ELEMS 3
 330 #define REGCP_OTHER_ELEMS 3
 331 #define REGCP_FRAME_ELEMS 1
 332 /* REGCP_FRAME_ELEMS are not part of the REGCP_OTHER_ELEMS and
 333  * are needed for the regexp context stack bookkeeping. */
 334
 335 STATIC CHECKPOINT
 336 S_regcppush(pTHX_ const regexp *rex, I32 parenfloor)
 337 {
 338     dVAR;
 339     const int retval = PL_savestack_ix;
 340     const int paren_elems_to_push = (PL_regsize - parenfloor) * REGCP_PAREN_ELEMS;
 341     const UV total_elems = paren_elems_to_push + REGCP_OTHER_ELEMS;
 342     const UV elems_shifted = total_elems << SAVE_TIGHT_SHIFT;
 343     I32 p;
 344     GET_RE_DEBUG_FLAGS_DECL;
 345
 346     PERL_ARGS_ASSERT_REGCPPUSH;
 347
 348     if (paren_elems_to_push < 0)
 349         Perl_croak(aTHX_ "panic: paren_elems_to_push, %i < 0",
 350                    paren_elems_to_push);
 351
 352     if ((elems_shifted >> SAVE_TIGHT_SHIFT) != total_elems)
 353         Perl_croak(aTHX_ "panic: paren_elems_to_push offset %"UVuf
 354                    " out of range (%lu-%ld)",
 355                    total_elems, (unsigned long)PL_regsize, (long)parenfloor);
 356
 357     SSGROW(total_elems + REGCP_FRAME_ELEMS);
 358
 359     DEBUG_BUFFERS_r(
 360         if ((int)PL_regsize > (int)parenfloor)
 361             PerlIO_printf(Perl_debug_log,
 362                 "rex=0x%"UVxf" offs=0x%"UVxf": saving capture indices:\n",
 363                 PTR2UV(rex),
 364                 PTR2UV(rex->offs)
 365             );
 366     );
 367     for (p = parenfloor+1; p <= (I32)PL_regsize;  p++) {
 368 /* REGCP_PARENS_ELEMS are pushed per pairs of parentheses. */
 369         SSPUSHINT(rex->offs[p].end);
 370         SSPUSHINT(rex->offs[p].start);
 371         SSPUSHINT(rex->offs[p].start_tmp);
 372         DEBUG_BUFFERS_r(PerlIO_printf(Perl_debug_log,
 373             "    \\%"UVuf": %"IVdf"(%"IVdf")..%"IVdf"\n",
 374             (UV)p,
 375             (IV)rex->offs[p].start,
 376             (IV)rex->offs[p].start_tmp,
 377             (IV)rex->offs[p].end
 378         ));
 379     }
 380 /* REGCP_OTHER_ELEMS are pushed in any case, parentheses or no. */
 381     SSPUSHINT(PL_regsize);
 382     SSPUSHINT(rex->lastparen);
 383     SSPUSHINT(rex->lastcloseparen);
 384     SSPUSHUV(SAVEt_REGCONTEXT | elems_shifted); /* Magic cookie. */
 385
 386     return retval;
 387 }
 388
 389 /* These are needed since we do not localize EVAL nodes: */
 390 #define REGCP_SET(cp)                                           \
 391     DEBUG_STATE_r(                                              \
 392             PerlIO_printf(Perl_debug_log,                       \
 393                 "  Setting an EVAL scope, savestack=%"IVdf"\n", \
 394                 (IV)PL_savestack_ix));                          \
 395     cp = PL_savestack_ix
 396
 397 #define REGCP_UNWIND(cp)                                        \
 398     DEBUG_STATE_r(                                              \
 399         if (cp != PL_savestack_ix)                              \
 400             PerlIO_printf(Perl_debug_log,                       \
 401                 "  Clearing an EVAL scope, savestack=%"IVdf"..%"IVdf"\n", \
 402                 (IV)(cp), (IV)PL_savestack_ix));                \
 403     regcpblow(cp)
 404
 405 #define UNWIND_PAREN(lp, lcp)               \
 406     for (n = rex->lastparen; n > lp; n--)   \
 407         rex->offs[n].end = -1;              \
 408     rex->lastparen = n;                     \
 409     rex->lastcloseparen = lcp;
 410
 411
 412 STATIC void
 413 S_regcppop(pTHX_ regexp *rex)
 414 {
 415     dVAR;
 416     UV i;
 417     U32 paren;
 418     GET_RE_DEBUG_FLAGS_DECL;
 419
 420     PERL_ARGS_ASSERT_REGCPPOP;
 421
 422     /* Pop REGCP_OTHER_ELEMS before the parentheses loop starts. */
 423     i = SSPOPUV;
 424     assert((i & SAVE_MASK) == SAVEt_REGCONTEXT); /* Check that the magic cookie is there. */
 425     i >>= SAVE_TIGHT_SHIFT; /* Parentheses elements to pop. */
 426     rex->lastcloseparen = SSPOPINT;
 427     rex->lastparen = SSPOPINT;
 428     PL_regsize = SSPOPINT;
 429
 430     i -= REGCP_OTHER_ELEMS;
 431     /* Now restore the parentheses context. */
 432     DEBUG_BUFFERS_r(
 433         if (i || rex->lastparen + 1 <= rex->nparens)
 434             PerlIO_printf(Perl_debug_log,
 435                 "rex=0x%"UVxf" offs=0x%"UVxf": restoring capture indices to:\n",
 436                 PTR2UV(rex),
 437                 PTR2UV(rex->offs)
 438             );
 439     );
 440     paren = PL_regsize;
 441     for ( ; i > 0; i -= REGCP_PAREN_ELEMS) {
 442         I32 tmps;
 443         rex->offs[paren].start_tmp = SSPOPINT;
 444         rex->offs[paren].start = SSPOPINT;
 445         tmps = SSPOPINT;
 446         if (paren <= rex->lastparen)
 447             rex->offs[paren].end = tmps;
 448         DEBUG_BUFFERS_r( PerlIO_printf(Perl_debug_log,
 449             "    \\%"UVuf": %"IVdf"(%"IVdf")..%"IVdf"%s\n",
 450             (UV)paren,
 451             (IV)rex->offs[paren].start,
 452             (IV)rex->offs[paren].start_tmp,
 453             (IV)rex->offs[paren].end,
 454             (paren > rex->lastparen ? "(skipped)" : ""));
 455         );
 456         paren--;
 457     }
 458 #if 1
 459     /* It would seem that the similar code in regtry()
 460      * already takes care of this, and in fact it is in
 461      * a better location to since this code can #if 0-ed out
 462      * but the code in regtry() is needed or otherwise tests
 463      * requiring null fields (pat.t#187 and split.t#{13,14}
 464      * (as of patchlevel 7877)  will fail.  Then again,
 465      * this code seems to be necessary or otherwise
 466      * this erroneously leaves $1 defined: "1" =~ /^(?:(\d)x)?\d$/
 467      * --jhi updated by dapm */
 468     for (i = rex->lastparen + 1; i <= rex->nparens; i++) {
 469         if (i > PL_regsize)
 470             rex->offs[i].start = -1;
 471         rex->offs[i].end = -1;
 472         DEBUG_BUFFERS_r( PerlIO_printf(Perl_debug_log,
 473             "    \\%"UVuf": %s   ..-1 undeffing\n",
 474             (UV)i,
 475             (i > PL_regsize) ? "-1" : "  "
 476         ));
 477     }
 478 #endif
 479 }
 480
 481 /* restore the parens and associated vars at savestack position ix,
 482  * but without popping the stack */
 483
 484 STATIC void
 485 S_regcp_restore(pTHX_ regexp *rex, I32 ix)
 486 {
 487     I32 tmpix = PL_savestack_ix;
 488     PL_savestack_ix = ix;
 489     regcppop(rex);
 490     PL_savestack_ix = tmpix;
 491 }
 492
 493 #define regcpblow(cp) LEAVE_SCOPE(cp)   /* Ignores regcppush()ed data. */
 494
 495 /*
 496  * pregexec and friends
 497  */
 498
 499 #ifndef PERL_IN_XSUB_RE
 500 /*
 501  - pregexec - match a regexp against a string
 502  */
 503 I32
 504 Perl_pregexec(pTHX_ REGEXP * const prog, char* stringarg, register char *strend,
 505          char *strbeg, I32 minend, SV *screamer, U32 nosave)
 506 /* stringarg: the point in the string at which to begin matching */
 507 /* strend:    pointer to null at end of string */
 508 /* strbeg:    real beginning of string */
 509 /* minend:    end of match must be >= minend bytes after stringarg. */
 510 /* screamer:  SV being matched: only used for utf8 flag, pos() etc; string
 511  *            itself is accessed via the pointers above */
 512 /* nosave:    For optimizations. */
 513 {
 514     PERL_ARGS_ASSERT_PREGEXEC;
 515
 516     return
 517         regexec_flags(prog, stringarg, strend, strbeg, minend, screamer, NULL,
 518                       nosave ? 0 : REXEC_COPY_STR);
 519 }
 520 #endif
 521
 522 /*
 523  * Need to implement the following flags for reg_anch:
 524  *
 525  * USE_INTUIT_NOML              - Useful to call re_intuit_start() first
 526  * USE_INTUIT_ML
 527  * INTUIT_AUTORITATIVE_NOML     - Can trust a positive answer
 528  * INTUIT_AUTORITATIVE_ML
 529  * INTUIT_ONCE_NOML             - Intuit can match in one location only.
 530  * INTUIT_ONCE_ML
 531  *
 532  * Another flag for this function: SECOND_TIME (so that float substrs
 533  * with giant delta may be not rechecked).
 534  */
 535
 536 /* Assumptions: if ANCH_GPOS, then strpos is anchored. XXXX Check GPOS logic */
 537
 538 /* If SCREAM, then SvPVX_const(sv) should be compatible with strpos and strend.
 539    Otherwise, only SvCUR(sv) is used to get strbeg. */
 540
 541 /* XXXX We assume that strpos is strbeg unless sv. */
 542
 543 /* XXXX Some places assume that there is a fixed substring.
 544         An update may be needed if optimizer marks as "INTUITable"
 545         RExen without fixed substrings.  Similarly, it is assumed that
 546         lengths of all the strings are no more than minlen, thus they
 547         cannot come from lookahead.
 548         (Or minlen should take into account lookahead.)
 549   NOTE: Some of this comment is not correct. minlen does now take account
 550   of lookahead/behind. Further research is required. -- demerphq
 551
 552 */
 553
 554 /* A failure to find a constant substring means that there is no need to make
 555    an expensive call to REx engine, thus we celebrate a failure.  Similarly,
 556    finding a substring too deep into the string means that less calls to
 557    regtry() should be needed.
 558
 559    REx compiler's optimizer found 4 possible hints:
 560         a) Anchored substring;
 561         b) Fixed substring;
 562         c) Whether we are anchored (beginning-of-line or \G);
 563         d) First node (of those at offset 0) which may distinguish positions;
 564    We use a)b)d) and multiline-part of c), and try to find a position in the
 565    string which does not contradict any of them.
 566  */
 567
 568 /* Most of decisions we do here should have been done at compile time.
 569    The nodes of the REx which we used for the search should have been
 570    deleted from the finite automaton. */
 571
 572 char *
 573 Perl_re_intuit_start(pTHX_ REGEXP * const rx, SV *sv, char *strpos,
 574                      char *strend, const U32 flags, re_scream_pos_data *data)
 575 {
 576     dVAR;
 577     struct regexp *const prog = (struct regexp *)SvANY(rx);
 578     I32 start_shift = 0;
 579     /* Should be nonnegative! */
 580     I32 end_shift   = 0;
 581     char *s;
 582     SV *check;
 583     char *strbeg;
 584     char *t;
 585     const bool utf8_target = (sv && SvUTF8(sv)) ? 1 : 0; /* if no sv we have to assume bytes */
 586     I32 ml_anch;
 587     char *other_last = NULL;    /* other substr checked before this */
 588     char *check_at = NULL;              /* check substr found at this pos */
 589     char *checked_upto = NULL;          /* how far into the string we have already checked using find_byclass*/
 590     const I32 multiline = prog->extflags & RXf_PMf_MULTILINE;
 591     RXi_GET_DECL(prog,progi);
 592 #ifdef DEBUGGING
 593     const char * const i_strpos = strpos;
 594 #endif
 595     GET_RE_DEBUG_FLAGS_DECL;
 596
 597     PERL_ARGS_ASSERT_RE_INTUIT_START;
 598     PERL_UNUSED_ARG(flags);
 599     PERL_UNUSED_ARG(data);
 600
 601     RX_MATCH_UTF8_set(rx,utf8_target);
 602
 603     if (RX_UTF8(rx)) {
 604         PL_reg_flags |= RF_utf8;
 605     }
 606     DEBUG_EXECUTE_r(
 607         debug_start_match(rx, utf8_target, strpos, strend,
 608             sv ? "Guessing start of match in sv for"
 609                : "Guessing start of match in string for");
 610               );
 611
 612     /* CHR_DIST() would be more correct here but it makes things slow. */
 613     if (prog->minlen > strend - strpos) {
 614         DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
 615                               "String too short... [re_intuit_start]\n"));
 616         goto fail;
 617     }
 618
 619     /* XXX we need to pass strbeg as a separate arg: the following is
 620      * guesswork and can be wrong... */
 621     if (sv && SvPOK(sv)) {
 622         char * p   = SvPVX(sv);
 623         STRLEN cur = SvCUR(sv);
 624         if (p <= strpos && strpos < p + cur) {
 625             strbeg = p;
 626             assert(p <= strend && strend <= p + cur);
 627         }
 628         else
 629             strbeg = strend - cur;
 630     }
 631     else
 632         strbeg = strpos;
 633
 634     PL_regeol = strend;
 635     if (utf8_target) {
 636         if (!prog->check_utf8 && prog->check_substr)
 637             to_utf8_substr(prog);
 638         check = prog->check_utf8;
 639     } else {
 640         if (!prog->check_substr && prog->check_utf8) {
 641             if (! to_byte_substr(prog)) {
 642                 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
 643                                         non_utf8_target_but_utf8_required));
 644                 goto fail;
 645             }
 646         }
 647         check = prog->check_substr;
 648     }
 649     if (prog->extflags & RXf_ANCH) {    /* Match at beg-of-str or after \n */
 650         ml_anch = !( (prog->extflags & RXf_ANCH_SINGLE)
 651                      || ( (prog->extflags & RXf_ANCH_BOL)
 652                           && !multiline ) );    /* Check after \n? */
 653
 654         if (!ml_anch) {
 655           if ( !(prog->extflags & RXf_ANCH_GPOS) /* Checked by the caller */
 656                 && !(prog->intflags & PREGf_IMPLICIT) /* not a real BOL */
 657                /* SvCUR is not set on references: SvRV and SvPVX_const overlap */
 658                && sv && !SvROK(sv)
 659                && (strpos != strbeg)) {
 660               DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "Not at start...\n"));
 661               goto fail;
 662           }
 663           if (prog->check_offset_min == prog->check_offset_max &&
 664               !(prog->extflags & RXf_CANY_SEEN)) {
 665             /* Substring at constant offset from beg-of-str... */
 666             I32 slen;
 667
 668             s = HOP3c(strpos, prog->check_offset_min, strend);
 669
 670             if (SvTAIL(check)) {
 671                 slen = SvCUR(check);    /* >= 1 */
 672
 673                 if ( strend - s > slen || strend - s < slen - 1
 674                      || (strend - s == slen && strend[-1] != '\n')) {
 675                     DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "String too long...\n"));
 676                     goto fail_finish;
 677                 }
 678                 /* Now should match s[0..slen-2] */
 679                 slen--;
 680                 if (slen && (*SvPVX_const(check) != *s
 681                              || (slen > 1
 682                                  && memNE(SvPVX_const(check), s, slen)))) {
 683                   report_neq:
 684                     DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "String not equal...\n"));
 685                     goto fail_finish;
 686                 }
 687             }
 688             else if (*SvPVX_const(check) != *s
 689                      || ((slen = SvCUR(check)) > 1
 690                          && memNE(SvPVX_const(check), s, slen)))
 691                 goto report_neq;
 692             check_at = s;
 693             goto success_at_start;
 694           }
 695         }
 696         /* Match is anchored, but substr is not anchored wrt beg-of-str. */
 697         s = strpos;
 698         start_shift = prog->check_offset_min; /* okay to underestimate on CC */
 699         end_shift = prog->check_end_shift;
 700
 701         if (!ml_anch) {
 702             const I32 end = prog->check_offset_max + CHR_SVLEN(check)
 703                                          - (SvTAIL(check) != 0);
 704             const I32 eshift = CHR_DIST((U8*)strend, (U8*)s) - end;
 705
 706             if (end_shift < eshift)
 707                 end_shift = eshift;
 708         }
 709     }
 710     else {                              /* Can match at random position */
 711         ml_anch = 0;
 712         s = strpos;
 713         start_shift = prog->check_offset_min;  /* okay to underestimate on CC */
 714         end_shift = prog->check_end_shift;
 715
 716         /* end shift should be non negative here */
 717     }
 718
 719 #ifdef QDEBUGGING       /* 7/99: reports of failure (with the older version) */
 720     if (end_shift < 0)
 721         Perl_croak(aTHX_ "panic: end_shift: %"IVdf" pattern:\n%s\n ",
 722                    (IV)end_shift, RX_PRECOMP(prog));
 723 #endif
 724
 725   restart:
 726     /* Find a possible match in the region s..strend by looking for
 727        the "check" substring in the region corrected by start/end_shift. */
 728
 729     {
 730         I32 srch_start_shift = start_shift;
 731         I32 srch_end_shift = end_shift;
 732         U8* start_point;
 733         U8* end_point;
 734         if (srch_start_shift < 0 && strbeg - s > srch_start_shift) {
 735             srch_end_shift -= ((strbeg - s) - srch_start_shift);
 736             srch_start_shift = strbeg - s;
 737         }
 738     DEBUG_OPTIMISE_MORE_r({
 739         PerlIO_printf(Perl_debug_log, "Check offset min: %"IVdf" Start shift: %"IVdf" End shift %"IVdf" Real End Shift: %"IVdf"\n",
 740             (IV)prog->check_offset_min,
 741             (IV)srch_start_shift,
 742             (IV)srch_end_shift,
 743             (IV)prog->check_end_shift);
 744     });
 745
 746         if (prog->extflags & RXf_CANY_SEEN) {
 747             start_point= (U8*)(s + srch_start_shift);
 748             end_point= (U8*)(strend - srch_end_shift);
 749         } else {
 750             start_point= HOP3(s, srch_start_shift, srch_start_shift < 0 ? strbeg : strend);
 751             end_point= HOP3(strend, -srch_end_shift, strbeg);
 752         }
 753         DEBUG_OPTIMISE_MORE_r({
 754             PerlIO_printf(Perl_debug_log, "fbm_instr len=%d str=<%.*s>\n",
 755                 (int)(end_point - start_point),
 756                 (int)(end_point - start_point) > 20 ? 20 : (int)(end_point - start_point),
 757                 start_point);
 758         });
 759
 760         s = fbm_instr( start_point, end_point,
 761                       check, multiline ? FBMrf_MULTILINE : 0);
 762     }
 763     /* Update the count-of-usability, remove useless subpatterns,
 764         unshift s.  */
 765
 766     DEBUG_EXECUTE_r({
 767         RE_PV_QUOTED_DECL(quoted, utf8_target, PERL_DEBUG_PAD_ZERO(0),
 768             SvPVX_const(check), RE_SV_DUMPLEN(check), 30);
 769         PerlIO_printf(Perl_debug_log, "%s %s substr %s%s%s",
 770                           (s ? "Found" : "Did not find"),
 771             (check == (utf8_target ? prog->anchored_utf8 : prog->anchored_substr)
 772                 ? "anchored" : "floating"),
 773             quoted,
 774             RE_SV_TAIL(check),
 775             (s ? " at offset " : "...\n") );
 776     });
 777
 778     if (!s)
 779         goto fail_finish;
 780     /* Finish the diagnostic message */
 781     DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "%ld...\n", (long)(s - i_strpos)) );
 782
 783     /* XXX dmq: first branch is for positive lookbehind...
 784        Our check string is offset from the beginning of the pattern.
 785        So we need to do any stclass tests offset forward from that
 786        point. I think. :-(
 787      */
 788
 789
 790
 791     check_at=s;
 792
 793
 794     /* Got a candidate.  Check MBOL anchoring, and the *other* substr.
 795        Start with the other substr.
 796        XXXX no SCREAM optimization yet - and a very coarse implementation
 797        XXXX /ttx+/ results in anchored="ttx", floating="x".  floating will
 798                 *always* match.  Probably should be marked during compile...
 799        Probably it is right to do no SCREAM here...
 800      */
 801
 802     if (utf8_target ? (prog->float_utf8 && prog->anchored_utf8)
 803                 : (prog->float_substr && prog->anchored_substr))
 804     {
 805         /* Take into account the "other" substring. */
 806         /* XXXX May be hopelessly wrong for UTF... */
 807         if (!other_last)
 808             other_last = strpos;
 809         if (check == (utf8_target ? prog->float_utf8 : prog->float_substr)) {
 810           do_other_anchored:
 811             {
 812                 char * const last = HOP3c(s, -start_shift, strbeg);
 813                 char *last1, *last2;
 814                 char * const saved_s = s;
 815                 SV* must;
 816
 817                 t = s - prog->check_offset_max;
 818                 if (s - strpos > prog->check_offset_max  /* signed-corrected t > strpos */
 819                     && (!utf8_target
 820                         || ((t = (char*)reghopmaybe3((U8*)s, -(prog->check_offset_max), (U8*)strpos))
 821                             && t > strpos)))
 822                     NOOP;
 823                 else
 824                     t = strpos;
 825                 t = HOP3c(t, prog->anchored_offset, strend);
 826                 if (t < other_last)     /* These positions already checked */
 827                     t = other_last;
 828                 last2 = last1 = HOP3c(strend, -prog->minlen, strbeg);
 829                 if (last < last1)
 830                     last1 = last;
 831                 /* XXXX It is not documented what units *_offsets are in.
 832                    We assume bytes, but this is clearly wrong.
 833                    Meaning this code needs to be carefully reviewed for errors.
 834                    dmq.
 835                   */
 836
 837                 /* On end-of-str: see comment below. */
 838                 must = utf8_target ? prog->anchored_utf8 : prog->anchored_substr;
 839                 if (must == &PL_sv_undef) {
 840                     s = (char*)NULL;
 841                     DEBUG_r(must = prog->anchored_utf8);        /* for debug */
 842                 }
 843                 else
 844                     s = fbm_instr(
 845                         (unsigned char*)t,
 846                         HOP3(HOP3(last1, prog->anchored_offset, strend)
 847                                 + SvCUR(must), -(SvTAIL(must)!=0), strbeg),
 848                         must,
 849                         multiline ? FBMrf_MULTILINE : 0
 850                     );
 851                 DEBUG_EXECUTE_r({
 852                     RE_PV_QUOTED_DECL(quoted, utf8_target, PERL_DEBUG_PAD_ZERO(0),
 853                         SvPVX_const(must), RE_SV_DUMPLEN(must), 30);
 854                     PerlIO_printf(Perl_debug_log, "%s anchored substr %s%s",
 855                         (s ? "Found" : "Contradicts"),
 856                         quoted, RE_SV_TAIL(must));
 857                 });
 858
 859
 860                 if (!s) {
 861                     if (last1 >= last2) {
 862                         DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
 863                                                 ", giving up...\n"));
 864                         goto fail_finish;
 865                     }
 866                     DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
 867                         ", trying floating at offset %ld...\n",
 868                         (long)(HOP3c(saved_s, 1, strend) - i_strpos)));
 869                     other_last = HOP3c(last1, prog->anchored_offset+1, strend);
 870                     s = HOP3c(last, 1, strend);
 871                     goto restart;
 872                 }
 873                 else {
 874                     DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, " at offset %ld...\n",
 875                           (long)(s - i_strpos)));
 876                     t = HOP3c(s, -prog->anchored_offset, strbeg);
 877                     other_last = HOP3c(s, 1, strend);
 878                     s = saved_s;
 879                     if (t == strpos)
 880                         goto try_at_start;
 881                     goto try_at_offset;
 882                 }
 883             }
 884         }
 885         else {          /* Take into account the floating substring. */
 886             char *last, *last1;
 887             char * const saved_s = s;
 888             SV* must;
 889
 890             t = HOP3c(s, -start_shift, strbeg);
 891             last1 = last =
 892                 HOP3c(strend, -prog->minlen + prog->float_min_offset, strbeg);
 893             if (CHR_DIST((U8*)last, (U8*)t) > prog->float_max_offset)
 894                 last = HOP3c(t, prog->float_max_offset, strend);
 895             s = HOP3c(t, prog->float_min_offset, strend);
 896             if (s < other_last)
 897                 s = other_last;
 898  /* XXXX It is not documented what units *_offsets are in.  Assume bytes.  */
 899             must = utf8_target ? prog->float_utf8 : prog->float_substr;
 900             /* fbm_instr() takes into account exact value of end-of-str
 901                if the check is SvTAIL(ed).  Since false positives are OK,
 902                and end-of-str is not later than strend we are OK. */
 903             if (must == &PL_sv_undef) {
 904                 s = (char*)NULL;
 905                 DEBUG_r(must = prog->float_utf8);       /* for debug message */
 906             }
 907             else
 908                 s = fbm_instr((unsigned char*)s,
 909                               (unsigned char*)last + SvCUR(must)
 910                                   - (SvTAIL(must)!=0),
 911                               must, multiline ? FBMrf_MULTILINE : 0);
 912             DEBUG_EXECUTE_r({
 913                 RE_PV_QUOTED_DECL(quoted, utf8_target, PERL_DEBUG_PAD_ZERO(0),
 914                     SvPVX_const(must), RE_SV_DUMPLEN(must), 30);
 915                 PerlIO_printf(Perl_debug_log, "%s floating substr %s%s",
 916                     (s ? "Found" : "Contradicts"),
 917                     quoted, RE_SV_TAIL(must));
 918             });
 919             if (!s) {
 920                 if (last1 == last) {
 921                     DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
 922                                             ", giving up...\n"));
 923                     goto fail_finish;
 924                 }
 925                 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
 926                     ", trying anchored starting at offset %ld...\n",
 927                     (long)(saved_s + 1 - i_strpos)));
 928                 other_last = last;
 929                 s = HOP3c(t, 1, strend);
 930                 goto restart;
 931             }
 932             else {
 933                 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, " at offset %ld...\n",
 934                       (long)(s - i_strpos)));
 935                 other_last = s; /* Fix this later. --Hugo */
 936                 s = saved_s;
 937                 if (t == strpos)
 938                     goto try_at_start;
 939                 goto try_at_offset;
 940             }
 941         }
 942     }
 943
 944
 945     t= (char*)HOP3( s, -prog->check_offset_max, (prog->check_offset_max<0) ? strend : strpos);
 946
 947     DEBUG_OPTIMISE_MORE_r(
 948         PerlIO_printf(Perl_debug_log,
 949             "Check offset min:%"IVdf" max:%"IVdf" S:%"IVdf" t:%"IVdf" D:%"IVdf" end:%"IVdf"\n",
 950             (IV)prog->check_offset_min,
 951             (IV)prog->check_offset_max,
 952             (IV)(s-strpos),
 953             (IV)(t-strpos),
 954             (IV)(t-s),
 955             (IV)(strend-strpos)
 956         )
 957     );
 958
 959     if (s - strpos > prog->check_offset_max  /* signed-corrected t > strpos */
 960         && (!utf8_target
 961             || ((t = (char*)reghopmaybe3((U8*)s, -prog->check_offset_max, (U8*) ((prog->check_offset_max<0) ? strend : strpos)))
 962                  && t > strpos)))
 963     {
 964         /* Fixed substring is found far enough so that the match
 965            cannot start at strpos. */
 966       try_at_offset:
 967         if (ml_anch && t[-1] != '\n') {
 968             /* Eventually fbm_*() should handle this, but often
 969                anchored_offset is not 0, so this check will not be wasted. */
 970             /* XXXX In the code below we prefer to look for "^" even in
 971                presence of anchored substrings.  And we search even
 972                beyond the found float position.  These pessimizations
 973                are historical artefacts only.  */
 974           find_anchor:
 975             while (t < strend - prog->minlen) {
 976                 if (*t == '\n') {
 977                     if (t < check_at - prog->check_offset_min) {
 978                         if (utf8_target ? prog->anchored_utf8 : prog->anchored_substr) {
 979                             /* Since we moved from the found position,
 980                                we definitely contradict the found anchored
 981                                substr.  Due to the above check we do not
 982                                contradict "check" substr.
 983                                Thus we can arrive here only if check substr
 984                                is float.  Redo checking for "other"=="fixed".
 985                              */
 986                             strpos = t + 1;
 987                             DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "Found /%s^%s/m at offset %ld, rescanning for anchored from offset %ld...\n",
 988                                 PL_colors[0], PL_colors[1], (long)(strpos - i_strpos), (long)(strpos - i_strpos + prog->anchored_offset)));
 989                             goto do_other_anchored;
 990                         }
 991                         /* We don't contradict the found floating substring. */
 992                         /* XXXX Why not check for STCLASS? */
 993                         s = t + 1;
 994                         DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "Found /%s^%s/m at offset %ld...\n",
 995                             PL_colors[0], PL_colors[1], (long)(s - i_strpos)));
 996                         goto set_useful;
 997                     }
 998                     /* Position contradicts check-string */
 999                     /* XXXX probably better to look for check-string
1000                        than for "\n", so one should lower the limit for t? */
1001                     DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "Found /%s^%s/m, restarting lookup for check-string at offset %ld...\n",
1002                         PL_colors[0], PL_colors[1], (long)(t + 1 - i_strpos)));
1003                     other_last = strpos = s = t + 1;
1004                     goto restart;
1005                 }
1006                 t++;
1007             }
1008             DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "Did not find /%s^%s/m...\n",
1009                         PL_colors[0], PL_colors[1]));
1010             goto fail_finish;
1011         }
1012         else {
1013             DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "Starting position does not contradict /%s^%s/m...\n",
1014                         PL_colors[0], PL_colors[1]));
1015         }
1016         s = t;
1017       set_useful:
1018         ++BmUSEFUL(utf8_target ? prog->check_utf8 : prog->check_substr);        /* hooray/5 */
1019     }
1020     else {
1021         /* The found string does not prohibit matching at strpos,
1022            - no optimization of calling REx engine can be performed,
1023            unless it was an MBOL and we are not after MBOL,
1024            or a future STCLASS check will fail this. */
1025       try_at_start:
1026         /* Even in this situation we may use MBOL flag if strpos is offset
1027            wrt the start of the string. */
1028         if (ml_anch && sv && !SvROK(sv) /* See prev comment on SvROK */
1029             && (strpos != strbeg) && strpos[-1] != '\n'
1030             /* May be due to an implicit anchor of m{.*foo}  */
1031             && !(prog->intflags & PREGf_IMPLICIT))
1032         {
1033             t = strpos;
1034             goto find_anchor;
1035         }
1036         DEBUG_EXECUTE_r( if (ml_anch)
1037             PerlIO_printf(Perl_debug_log, "Position at offset %ld does not contradict /%s^%s/m...\n",
1038                           (long)(strpos - i_strpos), PL_colors[0], PL_colors[1]);
1039         );
1040       success_at_start:
1041         if (!(prog->intflags & PREGf_NAUGHTY)   /* XXXX If strpos moved? */
1042             && (utf8_target ? (
1043                 prog->check_utf8                /* Could be deleted already */
1044                 && --BmUSEFUL(prog->check_utf8) < 0
1045                 && (prog->check_utf8 == prog->float_utf8)
1046             ) : (
1047                 prog->check_substr              /* Could be deleted already */
1048                 && --BmUSEFUL(prog->check_substr) < 0
1049                 && (prog->check_substr == prog->float_substr)
1050             )))
1051         {
1052             /* If flags & SOMETHING - do not do it many times on the same match */
1053             DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "... Disabling check substring...\n"));
1054             /* XXX Does the destruction order has to change with utf8_target? */
1055             SvREFCNT_dec(utf8_target ? prog->check_utf8 : prog->check_substr);
1056             SvREFCNT_dec(utf8_target ? prog->check_substr : prog->check_utf8);
1057             prog->check_substr = prog->check_utf8 = NULL;       /* disable */
1058             prog->float_substr = prog->float_utf8 = NULL;       /* clear */
1059             check = NULL;                       /* abort */
1060             s = strpos;
1061             /* XXXX If the check string was an implicit check MBOL, then we need to unset the relevant flag
1062                     see http://bugs.activestate.com/show_bug.cgi?id=87173 */
1063             if (prog->intflags & PREGf_IMPLICIT)
1064                 prog->extflags &= ~RXf_ANCH_MBOL;
1065             /* XXXX This is a remnant of the old implementation.  It
1066                     looks wasteful, since now INTUIT can use many
1067                     other heuristics. */
1068             prog->extflags &= ~RXf_USE_INTUIT;
1069             /* XXXX What other flags might need to be cleared in this branch? */
1070         }
1071         else
1072             s = strpos;
1073     }
1074
1075     /* Last resort... */
1076     /* XXXX BmUSEFUL already changed, maybe multiple change is meaningful... */
1077     /* trie stclasses are too expensive to use here, we are better off to
1078        leave it to regmatch itself */
1079     if (progi->regstclass && PL_regkind[OP(progi->regstclass)]!=TRIE) {
1080         /* minlen == 0 is possible if regstclass is \b or \B,
1081            and the fixed substr is ''$.
1082            Since minlen is already taken into account, s+1 is before strend;
1083            accidentally, minlen >= 1 guaranties no false positives at s + 1
1084            even for \b or \B.  But (minlen? 1 : 0) below assumes that
1085            regstclass does not come from lookahead...  */
1086         /* If regstclass takes bytelength more than 1: If charlength==1, OK.
1087            This leaves EXACTF-ish only, which are dealt with in find_byclass().  */
1088         const U8* const str = (U8*)STRING(progi->regstclass);
1089         const int cl_l = (PL_regkind[OP(progi->regstclass)] == EXACT
1090                     ? CHR_DIST(str+STR_LEN(progi->regstclass), str)
1091                     : 1);
1092         char * endpos;
1093         if (prog->anchored_substr || prog->anchored_utf8 || ml_anch)
1094             endpos= HOP3c(s, (prog->minlen ? cl_l : 0), strend);
1095         else if (prog->float_substr || prog->float_utf8)
1096             endpos= HOP3c(HOP3c(check_at, -start_shift, strbeg), cl_l, strend);
1097         else
1098             endpos= strend;
1099
1100         if (checked_upto < s)
1101            checked_upto = s;
1102         DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "start_shift: %"IVdf" check_at: %"IVdf" s: %"IVdf" endpos: %"IVdf" checked_upto: %"IVdf"\n",
1103                                       (IV)start_shift, (IV)(check_at - strbeg), (IV)(s - strbeg), (IV)(endpos - strbeg), (IV)(checked_upto- strbeg)));
1104
1105         t = s;
1106         s = find_byclass(prog, progi->regstclass, checked_upto, endpos, NULL);
1107         if (s) {
1108             checked_upto = s;
1109         } else {
1110 #ifdef DEBUGGING
1111             const char *what = NULL;
1112 #endif
1113             if (endpos == strend) {
1114                 DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log,
1115                                 "Could not match STCLASS...\n") );
1116                 goto fail;
1117             }
1118             DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log,
1119                                    "This position contradicts STCLASS...\n") );
1120             if ((prog->extflags & RXf_ANCH) && !ml_anch)
1121                 goto fail;
1122             checked_upto = HOPBACKc(endpos, start_shift);
1123             DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "start_shift: %"IVdf" check_at: %"IVdf" endpos: %"IVdf" checked_upto: %"IVdf"\n",
1124                                       (IV)start_shift, (IV)(check_at - strbeg), (IV)(endpos - strbeg), (IV)(checked_upto- strbeg)));
1125             /* Contradict one of substrings */
1126             if (prog->anchored_substr || prog->anchored_utf8) {
1127                 if ((utf8_target ? prog->anchored_utf8 : prog->anchored_substr) == check) {
1128                     DEBUG_EXECUTE_r( what = "anchored" );
1129                   hop_and_restart:
1130                     s = HOP3c(t, 1, strend);
1131                     if (s + start_shift + end_shift > strend) {
1132                         /* XXXX Should be taken into account earlier? */
1133                         DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log,
1134                                                "Could not match STCLASS...\n") );
1135                         goto fail;
1136                     }
1137                     if (!check)
1138                         goto giveup;
1139                     DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log,
1140                                 "Looking for %s substr starting at offset %ld...\n",
1141                                  what, (long)(s + start_shift - i_strpos)) );
1142                     goto restart;
1143                 }
1144                 /* Have both, check_string is floating */
1145                 if (t + start_shift >= check_at) /* Contradicts floating=check */
1146                     goto retry_floating_check;
1147                 /* Recheck anchored substring, but not floating... */
1148                 s = check_at;
1149                 if (!check)
1150                     goto giveup;
1151                 DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log,
1152                           "Looking for anchored substr starting at offset %ld...\n",
1153                           (long)(other_last - i_strpos)) );
1154                 goto do_other_anchored;
1155             }
1156             /* Another way we could have checked stclass at the
1157                current position only: */
1158             if (ml_anch) {
1159                 s = t = t + 1;
1160                 if (!check)
1161                     goto giveup;
1162                 DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log,
1163                           "Looking for /%s^%s/m starting at offset %ld...\n",
1164                           PL_colors[0], PL_colors[1], (long)(t - i_strpos)) );
1165                 goto try_at_offset;
1166             }
1167             if (!(utf8_target ? prog->float_utf8 : prog->float_substr)) /* Could have been deleted */
1168                 goto fail;
1169             /* Check is floating substring. */
1170           retry_floating_check:
1171             t = check_at - start_shift;
1172             DEBUG_EXECUTE_r( what = "floating" );
1173             goto hop_and_restart;
1174         }
1175         if (t != s) {
1176             DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
1177                         "By STCLASS: moving %ld --> %ld\n",
1178                                   (long)(t - i_strpos), (long)(s - i_strpos))
1179                    );
1180         }
1181         else {
1182             DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
1183                                   "Does not contradict STCLASS...\n");
1184                    );
1185         }
1186     }
1187   giveup:
1188     DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "%s%s:%s match at offset %ld\n",
1189                           PL_colors[4], (check ? "Guessed" : "Giving up"),
1190                           PL_colors[5], (long)(s - i_strpos)) );
1191     return s;
1192
1193   fail_finish:                          /* Substring not found */
1194     if (prog->check_substr || prog->check_utf8)         /* could be removed already */
1195         BmUSEFUL(utf8_target ? prog->check_utf8 : prog->check_substr) += 5; /* hooray */
1196   fail:
1197     DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "%sMatch rejected by optimizer%s\n",
1198                           PL_colors[4], PL_colors[5]));
1199     return NULL;
1200 }
1201
1202 #define DECL_TRIE_TYPE(scan) \
1203     const enum { trie_plain, trie_utf8, trie_utf8_fold, trie_latin_utf8_fold } \
1204                     trie_type = ((scan->flags == EXACT) \
1205                               ? (utf8_target ? trie_utf8 : trie_plain) \
1206                               : (utf8_target ? trie_utf8_fold : trie_latin_utf8_fold))
1207
1208 #define REXEC_TRIE_READ_CHAR(trie_type, trie, widecharmap, uc, uscan, len,          \
1209 uvc, charid, foldlen, foldbuf, uniflags) STMT_START {                               \
1210     STRLEN skiplen;                                                                 \
1211     switch (trie_type) {                                                            \
1212     case trie_utf8_fold:                                                            \
1213         if ( foldlen>0 ) {                                                          \
1214             uvc = utf8n_to_uvuni( (const U8*) uscan, UTF8_MAXLEN, &len, uniflags ); \
1215             foldlen -= len;                                                         \
1216             uscan += len;                                                           \
1217             len=0;                                                                  \
1218         } else {                                                                    \
1219             uvc = to_utf8_fold( (const U8*) uc, foldbuf, &foldlen );                \
1220             len = UTF8SKIP(uc);                                                     \
1221             skiplen = UNISKIP( uvc );                                               \
1222             foldlen -= skiplen;                                                     \
1223             uscan = foldbuf + skiplen;                                              \
1224         }                                                                           \
1225         break;                                                                      \
1226     case trie_latin_utf8_fold:                                                      \
1227         if ( foldlen>0 ) {                                                          \
1228             uvc = utf8n_to_uvuni( (const U8*) uscan, UTF8_MAXLEN, &len, uniflags ); \
1229             foldlen -= len;                                                         \
1230             uscan += len;                                                           \
1231             len=0;                                                                  \
1232         } else {                                                                    \
1233             len = 1;                                                                \
1234             uvc = _to_fold_latin1( (U8) *uc, foldbuf, &foldlen, 1);                 \
1235             skiplen = UNISKIP( uvc );                                               \
1236             foldlen -= skiplen;                                                     \
1237             uscan = foldbuf + skiplen;                                              \
1238         }                                                                           \
1239         break;                                                                      \
1240     case trie_utf8:                                                                 \
1241         uvc = utf8n_to_uvuni( (const U8*) uc, UTF8_MAXLEN, &len, uniflags );        \
1242         break;                                                                      \
1243     case trie_plain:                                                                \
1244         uvc = (UV)*uc;                                                              \
1245         len = 1;                                                                    \
1246     }                                                                               \
1247     if (uvc < 256) {                                                                \
1248         charid = trie->charmap[ uvc ];                                              \
1249     }                                                                               \
1250     else {                                                                          \
1251         charid = 0;                                                                 \
1252         if (widecharmap) {                                                          \
1253             SV** const svpp = hv_fetch(widecharmap,                                 \
1254                         (char*)&uvc, sizeof(UV), 0);                                \
1255             if (svpp)                                                               \
1256                 charid = (U16)SvIV(*svpp);                                          \
1257         }                                                                           \
1258     }                                                                               \
1259 } STMT_END
1260
1261 #define REXEC_FBC_EXACTISH_SCAN(CoNd)                     \
1262 STMT_START {                                              \
1263     while (s <= e) {                                      \
1264         if ( (CoNd)                                       \
1265              && (ln == 1 || folder(s, pat_string, ln))    \
1266              && (!reginfo || regtry(reginfo, &s)) )       \
1267             goto got_it;                                  \
1268         s++;                                              \
1269     }                                                     \
1270 } STMT_END
1271
1272 #define REXEC_FBC_UTF8_SCAN(CoDe)                     \
1273 STMT_START {                                          \
1274     while (s < strend && s + (uskip = UTF8SKIP(s)) <= strend) {     \
1275         CoDe                                          \
1276         s += uskip;                                   \
1277     }                                                 \
1278 } STMT_END
1279
1280 #define REXEC_FBC_SCAN(CoDe)                          \
1281 STMT_START {                                          \
1282     while (s < strend) {                              \
1283         CoDe                                          \
1284         s++;                                          \
1285     }                                                 \
1286 } STMT_END
1287
1288 #define REXEC_FBC_UTF8_CLASS_SCAN(CoNd)               \
1289 REXEC_FBC_UTF8_SCAN(                                  \
1290     if (CoNd) {                                       \
1291         if (tmp && (!reginfo || regtry(reginfo, &s)))  \
1292             goto got_it;                              \
1293         else                                          \
1294             tmp = doevery;                            \
1295     }                                                 \
1296     else                                              \
1297         tmp = 1;                                      \
1298 )
1299
1300 #define REXEC_FBC_CLASS_SCAN(CoNd)                    \
1301 REXEC_FBC_SCAN(                                       \
1302     if (CoNd) {                                       \
1303         if (tmp && (!reginfo || regtry(reginfo, &s)))  \
1304             goto got_it;                              \
1305         else                                          \
1306             tmp = doevery;                            \
1307     }                                                 \
1308     else                                              \
1309         tmp = 1;                                      \
1310 )
1311
1312 #define REXEC_FBC_TRYIT               \
1313 if ((!reginfo || regtry(reginfo, &s))) \
1314     goto got_it
1315
1316 #define REXEC_FBC_CSCAN(CoNdUtF8,CoNd)                         \
1317     if (utf8_target) {                                             \
1318         REXEC_FBC_UTF8_CLASS_SCAN(CoNdUtF8);                   \
1319     }                                                          \
1320     else {                                                     \
1321         REXEC_FBC_CLASS_SCAN(CoNd);                            \
1322     }
1323
1324 #define REXEC_FBC_CSCAN_PRELOAD(UtFpReLoAd,CoNdUtF8,CoNd)      \
1325     if (utf8_target) {                                             \
1326         UtFpReLoAd;                                            \
1327         REXEC_FBC_UTF8_CLASS_SCAN(CoNdUtF8);                   \
1328     }                                                          \
1329     else {                                                     \
1330         REXEC_FBC_CLASS_SCAN(CoNd);                            \
1331     }
1332
1333 #define REXEC_FBC_CSCAN_TAINT(CoNdUtF8,CoNd)                   \
1334     PL_reg_flags |= RF_tainted;                                \
1335     if (utf8_target) {                                             \
1336         REXEC_FBC_UTF8_CLASS_SCAN(CoNdUtF8);                   \
1337     }                                                          \
1338     else {                                                     \
1339         REXEC_FBC_CLASS_SCAN(CoNd);                            \
1340     }
1341
1342 #define DUMP_EXEC_POS(li,s,doutf8) \
1343     dump_exec_pos(li,s,(PL_regeol),(PL_bostr),(PL_reg_starttry),doutf8)
1344
1345
1346 #define UTF8_NOLOAD(TEST_NON_UTF8, IF_SUCCESS, IF_FAIL) \
1347         tmp = (s != PL_bostr) ? UCHARAT(s - 1) : '\n';                         \
1348         tmp = TEST_NON_UTF8(tmp);                                              \
1349         REXEC_FBC_UTF8_SCAN(                                                   \
1350             if (tmp == ! TEST_NON_UTF8((U8) *s)) { \
1351                 tmp = !tmp;                                                    \
1352                 IF_SUCCESS;                                                    \
1353             }                                                                  \
1354             else {                                                             \
1355                 IF_FAIL;                                                       \
1356             }                                                                  \
1357         );                                                                     \
1358
1359 #define UTF8_LOAD(TeSt1_UtF8, TeSt2_UtF8, IF_SUCCESS, IF_FAIL) \
1360         if (s == PL_bostr) {                                                   \
1361             tmp = '\n';                                                        \
1362         }                                                                      \
1363         else {                                                                 \
1364             U8 * const r = reghop3((U8*)s, -1, (U8*)PL_bostr);                 \
1365             tmp = utf8n_to_uvchr(r, UTF8SKIP(r), 0, UTF8_ALLOW_DEFAULT);       \
1366         }                                                                      \
1367         tmp = TeSt1_UtF8;                                                      \
1368         LOAD_UTF8_CHARCLASS_ALNUM();                                                                \
1369         REXEC_FBC_UTF8_SCAN(                                                   \
1370             if (tmp == ! (TeSt2_UtF8)) { \
1371                 tmp = !tmp;                                                    \
1372                 IF_SUCCESS;                                                    \
1373             }                                                                  \
1374             else {                                                             \
1375                 IF_FAIL;                                                       \
1376             }                                                                  \
1377         );                                                                     \
1378
1379 /* The only difference between the BOUND and NBOUND cases is that
1380  * REXEC_FBC_TRYIT is called when matched in BOUND, and when non-matched in
1381  * NBOUND.  This is accomplished by passing it in either the if or else clause,
1382  * with the other one being empty */
1383 #define FBC_BOUND(TEST_NON_UTF8, TEST1_UTF8, TEST2_UTF8) \
1384     FBC_BOUND_COMMON(UTF8_LOAD(TEST1_UTF8, TEST2_UTF8, REXEC_FBC_TRYIT, PLACEHOLDER), TEST_NON_UTF8, REXEC_FBC_TRYIT, PLACEHOLDER)
1385
1386 #define FBC_BOUND_NOLOAD(TEST_NON_UTF8, TEST1_UTF8, TEST2_UTF8) \
1387     FBC_BOUND_COMMON(UTF8_NOLOAD(TEST_NON_UTF8, REXEC_FBC_TRYIT, PLACEHOLDER), TEST_NON_UTF8, REXEC_FBC_TRYIT, PLACEHOLDER)
1388
1389 #define FBC_NBOUND(TEST_NON_UTF8, TEST1_UTF8, TEST2_UTF8) \
1390     FBC_BOUND_COMMON(UTF8_LOAD(TEST1_UTF8, TEST2_UTF8, PLACEHOLDER, REXEC_FBC_TRYIT), TEST_NON_UTF8, PLACEHOLDER, REXEC_FBC_TRYIT)
1391
1392 #define FBC_NBOUND_NOLOAD(TEST_NON_UTF8, TEST1_UTF8, TEST2_UTF8) \
1393     FBC_BOUND_COMMON(UTF8_NOLOAD(TEST_NON_UTF8, PLACEHOLDER, REXEC_FBC_TRYIT), TEST_NON_UTF8, PLACEHOLDER, REXEC_FBC_TRYIT)
1394
1395
1396 /* Common to the BOUND and NBOUND cases.  Unfortunately the UTF8 tests need to
1397  * be passed in completely with the variable name being tested, which isn't
1398  * such a clean interface, but this is easier to read than it was before.  We
1399  * are looking for the boundary (or non-boundary between a word and non-word
1400  * character.  The utf8 and non-utf8 cases have the same logic, but the details
1401  * must be different.  Find the "wordness" of the character just prior to this
1402  * one, and compare it with the wordness of this one.  If they differ, we have
1403  * a boundary.  At the beginning of the string, pretend that the previous
1404  * character was a new-line */
1405 #define FBC_BOUND_COMMON(UTF8_CODE, TEST_NON_UTF8, IF_SUCCESS, IF_FAIL) \
1406     if (utf8_target) {                                                         \
1407                 UTF8_CODE \
1408     }                                                                          \
1409     else {  /* Not utf8 */                                                     \
1410         tmp = (s != PL_bostr) ? UCHARAT(s - 1) : '\n';                         \
1411         tmp = TEST_NON_UTF8(tmp);                                              \
1412         REXEC_FBC_SCAN(                                                        \
1413             if (tmp == ! TEST_NON_UTF8((U8) *s)) {                             \
1414                 tmp = !tmp;                                                    \
1415                 IF_SUCCESS;                                                    \
1416             }                                                                  \
1417             else {                                                             \
1418                 IF_FAIL;                                                       \
1419             }                                                                  \
1420         );                                                                     \
1421     }                                                                          \
1422     if ((!prog->minlen && tmp) && (!reginfo || regtry(reginfo, &s)))           \
1423         goto got_it;
1424
1425 /* We know what class REx starts with.  Try to find this position... */
1426 /* if reginfo is NULL, its a dryrun */
1427 /* annoyingly all the vars in this routine have different names from their counterparts
1428    in regmatch. /grrr */
1429
1430 STATIC char *
1431 S_find_byclass(pTHX_ regexp * prog, const regnode *c, char *s,
1432     const char *strend, regmatch_info *reginfo)
1433 {
1434         dVAR;
1435         const I32 doevery = (prog->intflags & PREGf_SKIP) == 0;
1436         char *pat_string;   /* The pattern's exactish string */
1437         char *pat_end;      /* ptr to end char of pat_string */
1438         re_fold_t folder;       /* Function for computing non-utf8 folds */
1439         const U8 *fold_array;   /* array for folding ords < 256 */
1440         STRLEN ln;
1441         STRLEN lnc;
1442         STRLEN uskip;
1443         U8 c1;
1444         U8 c2;
1445         char *e;
1446         I32 tmp = 1;    /* Scratch variable? */
1447         const bool utf8_target = PL_reg_match_utf8;
1448         UV utf8_fold_flags = 0;
1449         RXi_GET_DECL(prog,progi);
1450
1451         PERL_ARGS_ASSERT_FIND_BYCLASS;
1452
1453         /* We know what class it must start with. */
1454         switch (OP(c)) {
1455         case ANYOFV:
1456         case ANYOF:
1457             if (utf8_target || OP(c) == ANYOFV) {
1458                 STRLEN inclasslen = strend - s;
1459                 REXEC_FBC_UTF8_CLASS_SCAN(
1460                           reginclass(prog, c, (U8*)s, &inclasslen, utf8_target));
1461             }
1462             else {
1463                 REXEC_FBC_CLASS_SCAN(REGINCLASS(prog, c, (U8*)s));
1464             }
1465             break;
1466         case CANY:
1467             REXEC_FBC_SCAN(
1468                 if (tmp && (!reginfo || regtry(reginfo, &s)))
1469                     goto got_it;
1470                 else
1471                     tmp = doevery;
1472             );
1473             break;
1474
1475         case EXACTFA:
1476             if (UTF_PATTERN || utf8_target) {
1477                 utf8_fold_flags = FOLDEQ_UTF8_NOMIX_ASCII;
1478                 goto do_exactf_utf8;
1479             }
1480             fold_array = PL_fold_latin1;    /* Latin1 folds are not affected by */
1481             folder = foldEQ_latin1;         /* /a, except the sharp s one which */
1482             goto do_exactf_non_utf8;        /* isn't dealt with by these */
1483
1484         case EXACTF:
1485             if (utf8_target) {
1486
1487                 /* regcomp.c already folded this if pattern is in UTF-8 */
1488                 utf8_fold_flags = 0;
1489                 goto do_exactf_utf8;
1490             }
1491             fold_array = PL_fold;
1492             folder = foldEQ;
1493             goto do_exactf_non_utf8;
1494
1495         case EXACTFL:
1496             if (UTF_PATTERN || utf8_target) {
1497                 utf8_fold_flags = FOLDEQ_UTF8_LOCALE;
1498                 goto do_exactf_utf8;
1499             }
1500             fold_array = PL_fold_locale;
1501             folder = foldEQ_locale;
1502             goto do_exactf_non_utf8;
1503
1504         case EXACTFU_SS:
1505             if (UTF_PATTERN) {
1506                 utf8_fold_flags = FOLDEQ_S2_ALREADY_FOLDED;
1507             }
1508             goto do_exactf_utf8;
1509
1510         case EXACTFU_TRICKYFOLD:
1511         case EXACTFU:
1512             if (UTF_PATTERN || utf8_target) {
1513                 utf8_fold_flags = (UTF_PATTERN) ? FOLDEQ_S2_ALREADY_FOLDED : 0;
1514                 goto do_exactf_utf8;
1515             }
1516
1517             /* Any 'ss' in the pattern should have been replaced by regcomp,
1518              * so we don't have to worry here about this single special case
1519              * in the Latin1 range */
1520             fold_array = PL_fold_latin1;
1521             folder = foldEQ_latin1;
1522
1523             /* FALL THROUGH */
1524
1525         do_exactf_non_utf8: /* Neither pattern nor string are UTF8, and there
1526                                are no glitches with fold-length differences
1527                                between the target string and pattern */
1528
1529             /* The idea in the non-utf8 EXACTF* cases is to first find the
1530              * first character of the EXACTF* node and then, if necessary,
1531              * case-insensitively compare the full text of the node.  c1 is the
1532              * first character.  c2 is its fold.  This logic will not work for
1533              * Unicode semantics and the german sharp ss, which hence should
1534              * not be compiled into a node that gets here. */
1535             pat_string = STRING(c);
1536             ln  = STR_LEN(c);   /* length to match in octets/bytes */
1537
1538             /* We know that we have to match at least 'ln' bytes (which is the
1539              * same as characters, since not utf8).  If we have to match 3
1540              * characters, and there are only 2 availabe, we know without
1541              * trying that it will fail; so don't start a match past the
1542              * required minimum number from the far end */
1543             e = HOP3c(strend, -((I32)ln), s);
1544
1545             if (!reginfo && e < s) {
1546                 e = s;                  /* Due to minlen logic of intuit() */
1547             }
1548
1549             c1 = *pat_string;
1550             c2 = fold_array[c1];
1551             if (c1 == c2) { /* If char and fold are the same */
1552                 REXEC_FBC_EXACTISH_SCAN(*(U8*)s == c1);
1553             }
1554             else {
1555                 REXEC_FBC_EXACTISH_SCAN(*(U8*)s == c1 || *(U8*)s == c2);
1556             }
1557             break;
1558
1559         do_exactf_utf8:
1560         {
1561             unsigned expansion;
1562
1563
1564             /* If one of the operands is in utf8, we can't use the simpler
1565              * folding above, due to the fact that many different characters
1566              * can have the same fold, or portion of a fold, or different-
1567              * length fold */
1568             pat_string = STRING(c);
1569             ln  = STR_LEN(c);   /* length to match in octets/bytes */
1570             pat_end = pat_string + ln;
1571             lnc = (UTF_PATTERN) /* length to match in characters */
1572                     ? utf8_length((U8 *) pat_string, (U8 *) pat_end)
1573                     : ln;
1574
1575             /* We have 'lnc' characters to match in the pattern, but because of
1576              * multi-character folding, each character in the target can match
1577              * up to 3 characters (Unicode guarantees it will never exceed
1578              * this) if it is utf8-encoded; and up to 2 if not (based on the
1579              * fact that the Latin 1 folds are already determined, and the
1580              * only multi-char fold in that range is the sharp-s folding to
1581              * 'ss'.  Thus, a pattern character can match as little as 1/3 of a
1582              * string character.  Adjust lnc accordingly, rounding up, so that
1583              * if we need to match at least 4+1/3 chars, that really is 5. */
1584             expansion = (utf8_target) ? UTF8_MAX_FOLD_CHAR_EXPAND : 2;
1585             lnc = (lnc + expansion - 1) / expansion;
1586
1587             /* As in the non-UTF8 case, if we have to match 3 characters, and
1588              * only 2 are left, it's guaranteed to fail, so don't start a
1589              * match that would require us to go beyond the end of the string
1590              */
1591             e = HOP3c(strend, -((I32)lnc), s);
1592
1593             if (!reginfo && e < s) {
1594                 e = s;                  /* Due to minlen logic of intuit() */
1595             }
1596
1597             /* XXX Note that we could recalculate e to stop the loop earlier,
1598              * as the worst case expansion above will rarely be met, and as we
1599              * go along we would usually find that e moves further to the left.
1600              * This would happen only after we reached the point in the loop
1601              * where if there were no expansion we should fail.  Unclear if
1602              * worth the expense */
1603
1604             while (s <= e) {
1605                 char *my_strend= (char *)strend;
1606                 if (foldEQ_utf8_flags(s, &my_strend, 0,  utf8_target,
1607                       pat_string, NULL, ln, cBOOL(UTF_PATTERN), utf8_fold_flags)
1608                     && (!reginfo || regtry(reginfo, &s)) )
1609                 {
1610                     goto got_it;
1611                 }
1612                 s += (utf8_target) ? UTF8SKIP(s) : 1;
1613             }
1614             break;
1615         }
1616         case BOUNDL:
1617             PL_reg_flags |= RF_tainted;
1618             FBC_BOUND(isALNUM_LC,
1619                       isALNUM_LC_uvchr(UNI_TO_NATIVE(tmp)),
1620                       isALNUM_LC_utf8((U8*)s));
1621             break;
1622         case NBOUNDL:
1623             PL_reg_flags |= RF_tainted;
1624             FBC_NBOUND(isALNUM_LC,
1625                        isALNUM_LC_uvchr(UNI_TO_NATIVE(tmp)),
1626                        isALNUM_LC_utf8((U8*)s));
1627             break;
1628         case BOUND:
1629             FBC_BOUND(isWORDCHAR,
1630                       isALNUM_uni(tmp),
1631                       cBOOL(swash_fetch(PL_utf8_alnum, (U8*)s, utf8_target)));
1632             break;
1633         case BOUNDA:
1634             FBC_BOUND_NOLOAD(isWORDCHAR_A,
1635                              isWORDCHAR_A(tmp),
1636                              isWORDCHAR_A((U8*)s));
1637             break;
1638         case NBOUND:
1639             FBC_NBOUND(isWORDCHAR,
1640                        isALNUM_uni(tmp),
1641                        cBOOL(swash_fetch(PL_utf8_alnum, (U8*)s, utf8_target)));
1642             break;
1643         case NBOUNDA:
1644             FBC_NBOUND_NOLOAD(isWORDCHAR_A,
1645                               isWORDCHAR_A(tmp),
1646                               isWORDCHAR_A((U8*)s));
1647             break;
1648         case BOUNDU:
1649             FBC_BOUND(isWORDCHAR_L1,
1650                       isALNUM_uni(tmp),
1651                       cBOOL(swash_fetch(PL_utf8_alnum, (U8*)s, utf8_target)));
1652             break;
1653         case NBOUNDU:
1654             FBC_NBOUND(isWORDCHAR_L1,
1655                        isALNUM_uni(tmp),
1656                        cBOOL(swash_fetch(PL_utf8_alnum, (U8*)s, utf8_target)));
1657             break;
1658         case ALNUML:
1659             REXEC_FBC_CSCAN_TAINT(
1660                 isALNUM_LC_utf8((U8*)s),
1661                 isALNUM_LC(*s)
1662             );
1663             break;
1664         case ALNUMU:
1665             REXEC_FBC_CSCAN_PRELOAD(
1666                 LOAD_UTF8_CHARCLASS_ALNUM(),
1667                 swash_fetch(PL_utf8_alnum,(U8*)s, utf8_target),
1668                 isWORDCHAR_L1((U8) *s)
1669             );
1670             break;
1671         case ALNUM:
1672             REXEC_FBC_CSCAN_PRELOAD(
1673                 LOAD_UTF8_CHARCLASS_ALNUM(),
1674                 swash_fetch(PL_utf8_alnum,(U8*)s, utf8_target),
1675                 isWORDCHAR((U8) *s)
1676             );
1677             break;
1678         case ALNUMA:
1679             /* Don't need to worry about utf8, as it can match only a single
1680              * byte invariant character */
1681             REXEC_FBC_CLASS_SCAN( isWORDCHAR_A(*s));
1682             break;
1683         case NALNUMU:
1684             REXEC_FBC_CSCAN_PRELOAD(
1685                 LOAD_UTF8_CHARCLASS_ALNUM(),
1686                 !swash_fetch(PL_utf8_alnum,(U8*)s, utf8_target),
1687                 ! isWORDCHAR_L1((U8) *s)
1688             );
1689             break;
1690         case NALNUM:
1691             REXEC_FBC_CSCAN_PRELOAD(
1692                 LOAD_UTF8_CHARCLASS_ALNUM(),
1693                 !swash_fetch(PL_utf8_alnum, (U8*)s, utf8_target),
1694                 ! isALNUM(*s)
1695             );
1696             break;
1697         case NALNUMA:
1698             REXEC_FBC_CSCAN(
1699                 !isWORDCHAR_A(*s),
1700                 !isWORDCHAR_A(*s)
1701             );
1702             break;
1703         case NALNUML:
1704             REXEC_FBC_CSCAN_TAINT(
1705                 !isALNUM_LC_utf8((U8*)s),
1706                 !isALNUM_LC(*s)
1707             );
1708             break;
1709         case SPACEU:
1710             REXEC_FBC_CSCAN_PRELOAD(
1711                 LOAD_UTF8_CHARCLASS_SPACE(),
1712                 *s == ' ' || swash_fetch(PL_utf8_space,(U8*)s, utf8_target),
1713                 isSPACE_L1((U8) *s)
1714             );
1715             break;
1716         case SPACE:
1717             REXEC_FBC_CSCAN_PRELOAD(
1718                 LOAD_UTF8_CHARCLASS_SPACE(),
1719                 *s == ' ' || swash_fetch(PL_utf8_space,(U8*)s, utf8_target),
1720                 isSPACE((U8) *s)
1721             );
1722             break;
1723         case SPACEA:
1724             /* Don't need to worry about utf8, as it can match only a single
1725              * byte invariant character */
1726             REXEC_FBC_CLASS_SCAN( isSPACE_A(*s));
1727             break;
1728         case SPACEL:
1729             REXEC_FBC_CSCAN_TAINT(
1730                 isSPACE_LC_utf8((U8*)s),
1731                 isSPACE_LC(*s)
1732             );
1733             break;
1734         case NSPACEU:
1735             REXEC_FBC_CSCAN_PRELOAD(
1736                 LOAD_UTF8_CHARCLASS_SPACE(),
1737                 !( *s == ' ' || swash_fetch(PL_utf8_space,(U8*)s, utf8_target)),
1738                 ! isSPACE_L1((U8) *s)
1739             );
1740             break;
1741         case NSPACE:
1742             REXEC_FBC_CSCAN_PRELOAD(
1743                 LOAD_UTF8_CHARCLASS_SPACE(),
1744                 !(*s == ' ' || swash_fetch(PL_utf8_space,(U8*)s, utf8_target)),
1745                 ! isSPACE((U8) *s)
1746             );
1747             break;
1748         case NSPACEA:
1749             REXEC_FBC_CSCAN(
1750                 !isSPACE_A(*s),
1751                 !isSPACE_A(*s)
1752             );
1753             break;
1754         case NSPACEL:
1755             REXEC_FBC_CSCAN_TAINT(
1756                 !isSPACE_LC_utf8((U8*)s),
1757                 !isSPACE_LC(*s)
1758             );
1759             break;
1760         case DIGIT:
1761             REXEC_FBC_CSCAN_PRELOAD(
1762                 LOAD_UTF8_CHARCLASS_DIGIT(),
1763                 swash_fetch(PL_utf8_digit,(U8*)s, utf8_target),
1764                 isDIGIT(*s)
1765             );
1766             break;
1767         case DIGITA:
1768             /* Don't need to worry about utf8, as it can match only a single
1769              * byte invariant character */
1770             REXEC_FBC_CLASS_SCAN( isDIGIT_A(*s));
1771             break;
1772         case DIGITL:
1773             REXEC_FBC_CSCAN_TAINT(
1774                 isDIGIT_LC_utf8((U8*)s),
1775                 isDIGIT_LC(*s)
1776             );
1777             break;
1778         case NDIGIT:
1779             REXEC_FBC_CSCAN_PRELOAD(
1780                 LOAD_UTF8_CHARCLASS_DIGIT(),
1781                 !swash_fetch(PL_utf8_digit,(U8*)s, utf8_target),
1782                 !isDIGIT(*s)
1783             );
1784             break;
1785         case NDIGITA:
1786             REXEC_FBC_CSCAN(
1787                 !isDIGIT_A(*s),
1788                 !isDIGIT_A(*s)
1789             );
1790             break;
1791         case NDIGITL:
1792             REXEC_FBC_CSCAN_TAINT(
1793                 !isDIGIT_LC_utf8((U8*)s),
1794                 !isDIGIT_LC(*s)
1795             );
1796             break;
1797         case LNBREAK:
1798             REXEC_FBC_CSCAN(
1799                 is_LNBREAK_utf8_safe(s, strend),
1800                 is_LNBREAK_latin1_safe(s, strend)
1801             );
1802             break;
1803         case VERTWS:
1804             REXEC_FBC_CSCAN(
1805                 is_VERTWS_utf8_safe(s, strend),
1806                 is_VERTWS_latin1_safe(s, strend)
1807             );
1808             break;
1809         case NVERTWS:
1810             REXEC_FBC_CSCAN(
1811                 !is_VERTWS_utf8_safe(s, strend),
1812                 !is_VERTWS_latin1_safe(s, strend)
1813             );
1814             break;
1815         case HORIZWS:
1816             REXEC_FBC_CSCAN(
1817                 is_HORIZWS_utf8_safe(s, strend),
1818                 is_HORIZWS_latin1_safe(s, strend)
1819             );
1820             break;
1821         case NHORIZWS:
1822             REXEC_FBC_CSCAN(
1823                 !is_HORIZWS_utf8_safe(s, strend),
1824                 !is_HORIZWS_latin1_safe(s, strend)
1825             );
1826             break;
1827         case POSIXA:
1828             /* Don't need to worry about utf8, as it can match only a single
1829             * byte invariant character.  The flag in this node type is the
1830             * class number to pass to _generic_isCC() to build a mask for
1831             * searching in PL_charclass[] */
1832             REXEC_FBC_CLASS_SCAN( _generic_isCC_A(*s, FLAGS(c)));
1833             break;
1834         case NPOSIXA:
1835             REXEC_FBC_CSCAN(
1836                 !_generic_isCC_A(*s, FLAGS(c)),
1837                 !_generic_isCC_A(*s, FLAGS(c))
1838             );
1839             break;
1840
1841         case AHOCORASICKC:
1842         case AHOCORASICK:
1843             {
1844                 DECL_TRIE_TYPE(c);
1845                 /* what trie are we using right now */
1846                 reg_ac_data *aho
1847                     = (reg_ac_data*)progi->data->data[ ARG( c ) ];
1848                 reg_trie_data *trie
1849                     = (reg_trie_data*)progi->data->data[ aho->trie ];
1850                 HV *widecharmap = MUTABLE_HV(progi->data->data[ aho->trie + 1 ]);
1851
1852                 const char *last_start = strend - trie->minlen;
1853 #ifdef DEBUGGING
1854                 const char *real_start = s;
1855 #endif
1856                 STRLEN maxlen = trie->maxlen;
1857                 SV *sv_points;
1858                 U8 **points; /* map of where we were in the input string
1859                                 when reading a given char. For ASCII this
1860                                 is unnecessary overhead as the relationship
1861                                 is always 1:1, but for Unicode, especially
1862                                 case folded Unicode this is not true. */
1863                 U8 foldbuf[ UTF8_MAXBYTES_CASE + 1 ];
1864                 U8 *bitmap=NULL;
1865
1866
1867                 GET_RE_DEBUG_FLAGS_DECL;
1868
1869                 /* We can't just allocate points here. We need to wrap it in
1870                  * an SV so it gets freed properly if there is a croak while
1871                  * running the match */
1872                 ENTER;
1873                 SAVETMPS;
1874                 sv_points=newSV(maxlen * sizeof(U8 *));
1875                 SvCUR_set(sv_points,
1876                     maxlen * sizeof(U8 *));
1877                 SvPOK_on(sv_points);
1878                 sv_2mortal(sv_points);
1879                 points=(U8**)SvPV_nolen(sv_points );
1880                 if ( trie_type != trie_utf8_fold
1881                      && (trie->bitmap || OP(c)==AHOCORASICKC) )
1882                 {
1883                     if (trie->bitmap)
1884                         bitmap=(U8*)trie->bitmap;
1885                     else
1886                         bitmap=(U8*)ANYOF_BITMAP(c);
1887                 }
1888                 /* this is the Aho-Corasick algorithm modified a touch
1889                    to include special handling for long "unknown char"
1890                    sequences. The basic idea being that we use AC as long
1891                    as we are dealing with a possible matching char, when
1892                    we encounter an unknown char (and we have not encountered
1893                    an accepting state) we scan forward until we find a legal
1894                    starting char.
1895                    AC matching is basically that of trie matching, except
1896                    that when we encounter a failing transition, we fall back
1897                    to the current states "fail state", and try the current char
1898                    again, a process we repeat until we reach the root state,
1899                    state 1, or a legal transition. If we fail on the root state
1900                    then we can either terminate if we have reached an accepting
1901                    state previously, or restart the entire process from the beginning
1902                    if we have not.
1903
1904                  */
1905                 while (s <= last_start) {
1906                     const U32 uniflags = UTF8_ALLOW_DEFAULT;
1907                     U8 *uc = (U8*)s;
1908                     U16 charid = 0;
1909                     U32 base = 1;
1910                     U32 state = 1;
1911                     UV uvc = 0;
1912                     STRLEN len = 0;
1913                     STRLEN foldlen = 0;
1914                     U8 *uscan = (U8*)NULL;
1915                     U8 *leftmost = NULL;
1916 #ifdef DEBUGGING
1917                     U32 accepted_word= 0;
1918 #endif
1919                     U32 pointpos = 0;
1920
1921                     while ( state && uc <= (U8*)strend ) {
1922                         int failed=0;
1923                         U32 word = aho->states[ state ].wordnum;
1924
1925                         if( state==1 ) {
1926                             if ( bitmap ) {
1927                                 DEBUG_TRIE_EXECUTE_r(
1928                                     if ( uc <= (U8*)last_start && !BITMAP_TEST(bitmap,*uc) ) {
1929                                         dump_exec_pos( (char *)uc, c, strend, real_start,
1930                                             (char *)uc, utf8_target );
1931                                         PerlIO_printf( Perl_debug_log,
1932                                             " Scanning for legal start char...\n");
1933                                     }
1934                                 );
1935                                 if (utf8_target) {
1936                                     while ( uc <= (U8*)last_start && !BITMAP_TEST(bitmap,*uc) ) {
1937                                         uc += UTF8SKIP(uc);
1938                                     }
1939                                 } else {
1940                                     while ( uc <= (U8*)last_start  && !BITMAP_TEST(bitmap,*uc) ) {
1941                                         uc++;
1942                                     }
1943                                 }
1944                                 s= (char *)uc;
1945                             }
1946                             if (uc >(U8*)last_start) break;
1947                         }
1948
1949                         if ( word ) {
1950                             U8 *lpos= points[ (pointpos - trie->wordinfo[word].len) % maxlen ];
1951                             if (!leftmost || lpos < leftmost) {
1952                                 DEBUG_r(accepted_word=word);
1953                                 leftmost= lpos;
1954                             }
1955                             if (base==0) break;
1956
1957                         }
1958                         points[pointpos++ % maxlen]= uc;
1959                         if (foldlen || uc < (U8*)strend) {
1960                             REXEC_TRIE_READ_CHAR(trie_type, trie,
1961                                              widecharmap, uc,
1962                                              uscan, len, uvc, charid, foldlen,
1963                                              foldbuf, uniflags);
1964                             DEBUG_TRIE_EXECUTE_r({
1965                                 dump_exec_pos( (char *)uc, c, strend,
1966                                             real_start, s, utf8_target);
1967                                 PerlIO_printf(Perl_debug_log,
1968                                     " Charid:%3u CP:%4"UVxf" ",
1969                                      charid, uvc);
1970                             });
1971                         }
1972                         else {
1973                             len = 0;
1974                             charid = 0;
1975                         }
1976
1977
1978                         do {
1979 #ifdef DEBUGGING
1980                             word = aho->states[ state ].wordnum;
1981 #endif
1982                             base = aho->states[ state ].trans.base;
1983
1984                             DEBUG_TRIE_EXECUTE_r({
1985                                 if (failed)
1986                                     dump_exec_pos( (char *)uc, c, strend, real_start,
1987                                         s,   utf8_target );
1988                                 PerlIO_printf( Perl_debug_log,
1989                                     "%sState: %4"UVxf", word=%"UVxf,
1990                                     failed ? " Fail transition to " : "",
1991                                     (UV)state, (UV)word);
1992                             });
1993                             if ( base ) {
1994                                 U32 tmp;
1995                                 I32 offset;
1996                                 if (charid &&
1997                                      ( ((offset = base + charid
1998                                         - 1 - trie->uniquecharcount)) >= 0)
1999                                      && ((U32)offset < trie->lasttrans)
2000                                      && trie->trans[offset].check == state
2001                                      && (tmp=trie->trans[offset].next))
2002                                 {
2003                                     DEBUG_TRIE_EXECUTE_r(
2004                                         PerlIO_printf( Perl_debug_log," - legal\n"));
2005                                     state = tmp;
2006                                     break;
2007                                 }
2008                                 else {
2009                                     DEBUG_TRIE_EXECUTE_r(
2010                                         PerlIO_printf( Perl_debug_log," - fail\n"));
2011                                     failed = 1;
2012                                     state = aho->fail[state];
2013                                 }
2014                             }
2015                             else {
2016                                 /* we must be accepting here */
2017                                 DEBUG_TRIE_EXECUTE_r(
2018                                         PerlIO_printf( Perl_debug_log," - accepting\n"));
2019                                 failed = 1;
2020                                 break;
2021                             }
2022                         } while(state);
2023                         uc += len;
2024                         if (failed) {
2025                             if (leftmost)
2026                                 break;
2027                             if (!state) state = 1;
2028                         }
2029                     }
2030                     if ( aho->states[ state ].wordnum ) {
2031                         U8 *lpos = points[ (pointpos - trie->wordinfo[aho->states[ state ].wordnum].len) % maxlen ];
2032                         if (!leftmost || lpos < leftmost) {
2033                             DEBUG_r(accepted_word=aho->states[ state ].wordnum);
2034                             leftmost = lpos;
2035                         }
2036                     }
2037                     if (leftmost) {
2038                         s = (char*)leftmost;
2039                         DEBUG_TRIE_EXECUTE_r({
2040                             PerlIO_printf(
2041                                 Perl_debug_log,"Matches word #%"UVxf" at position %"IVdf". Trying full pattern...\n",
2042                                 (UV)accepted_word, (IV)(s - real_start)
2043                             );
2044                         });
2045                         if (!reginfo || regtry(reginfo, &s)) {
2046                             FREETMPS;
2047                             LEAVE;
2048                             goto got_it;
2049                         }
2050                         s = HOPc(s,1);
2051                         DEBUG_TRIE_EXECUTE_r({
2052                             PerlIO_printf( Perl_debug_log,"Pattern failed. Looking for new start point...\n");
2053                         });
2054                     } else {
2055                         DEBUG_TRIE_EXECUTE_r(
2056                             PerlIO_printf( Perl_debug_log,"No match.\n"));
2057                         break;
2058                     }
2059                 }
2060                 FREETMPS;
2061                 LEAVE;
2062             }
2063             break;
2064         default:
2065             Perl_croak(aTHX_ "panic: unknown regstclass %d", (int)OP(c));
2066             break;
2067         }
2068         return 0;
2069       got_it:
2070         return s;
2071 }
2072
2073
2074 /*
2075  - regexec_flags - match a regexp against a string
2076  */
2077 I32
2078 Perl_regexec_flags(pTHX_ REGEXP * const rx, char *stringarg, register char *strend,
2079               char *strbeg, I32 minend, SV *sv, void *data, U32 flags)
2080 /* stringarg: the point in the string at which to begin matching */
2081 /* strend:    pointer to null at end of string */
2082 /* strbeg:    real beginning of string */
2083 /* minend:    end of match must be >= minend bytes after stringarg. */
2084 /* sv:        SV being matched: only used for utf8 flag, pos() etc; string
2085  *            itself is accessed via the pointers above */
2086 /* data:      May be used for some additional optimizations.
2087               Currently its only used, with a U32 cast, for transmitting
2088               the ganch offset when doing a /g match. This will change */
2089 /* nosave:    For optimizations. */
2090
2091 {
2092     dVAR;
2093     struct regexp *const prog = (struct regexp *)SvANY(rx);
2094     /*register*/ char *s;
2095     regnode *c;
2096     /*register*/ char *startpos = stringarg;
2097     I32 minlen;         /* must match at least this many chars */
2098     I32 dontbother = 0; /* how many characters not to try at end */
2099     I32 end_shift = 0;                  /* Same for the end. */         /* CC */
2100     I32 scream_pos = -1;                /* Internal iterator of scream. */
2101     char *scream_olds = NULL;
2102     const bool utf8_target = cBOOL(DO_UTF8(sv));
2103     I32 multiline;
2104     RXi_GET_DECL(prog,progi);
2105     regmatch_info reginfo;  /* create some info to pass to regtry etc */
2106     regexp_paren_pair *swap = NULL;
2107     GET_RE_DEBUG_FLAGS_DECL;
2108
2109     PERL_ARGS_ASSERT_REGEXEC_FLAGS;
2110     PERL_UNUSED_ARG(data);
2111
2112     /* Be paranoid... */
2113     if (prog == NULL || startpos == NULL) {
2114         Perl_croak(aTHX_ "NULL regexp parameter");
2115         return 0;
2116     }
2117
2118     multiline = prog->extflags & RXf_PMf_MULTILINE;
2119     reginfo.prog = rx;   /* Yes, sorry that this is confusing.  */
2120
2121     RX_MATCH_UTF8_set(rx, utf8_target);
2122     DEBUG_EXECUTE_r(
2123         debug_start_match(rx, utf8_target, startpos, strend,
2124         "Matching");
2125     );
2126
2127     minlen = prog->minlen;
2128
2129     if (strend - startpos < (minlen+(prog->check_offset_min<0?prog->check_offset_min:0))) {
2130         DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
2131                               "String too short [regexec_flags]...\n"));
2132         goto phooey;
2133     }
2134
2135
2136     /* Check validity of program. */
2137     if (UCHARAT(progi->program) != REG_MAGIC) {
2138         Perl_croak(aTHX_ "corrupted regexp program");
2139     }
2140
2141     PL_reg_flags = 0;
2142     PL_reg_state.re_state_eval_setup_done = FALSE;
2143     PL_reg_maxiter = 0;
2144
2145     if (RX_UTF8(rx))
2146         PL_reg_flags |= RF_utf8;
2147
2148     /* Mark beginning of line for ^ and lookbehind. */
2149     reginfo.bol = startpos; /* XXX not used ??? */
2150     PL_bostr  = strbeg;
2151     reginfo.sv = sv;
2152
2153     /* Mark end of line for $ (and such) */
2154     PL_regeol = strend;
2155
2156     /* see how far we have to get to not match where we matched before */
2157     reginfo.till = startpos+minend;
2158
2159     /* If there is a "must appear" string, look for it. */
2160     s = startpos;
2161
2162     if (prog->extflags & RXf_GPOS_SEEN) { /* Need to set reginfo->ganch */
2163         MAGIC *mg;
2164         if (flags & REXEC_IGNOREPOS){   /* Means: check only at start */
2165             reginfo.ganch = startpos + prog->gofs;
2166             DEBUG_GPOS_r(PerlIO_printf(Perl_debug_log,
2167               "GPOS IGNOREPOS: reginfo.ganch = startpos + %"UVxf"\n",(UV)prog->gofs));
2168         } else if (sv && SvTYPE(sv) >= SVt_PVMG
2169                   && SvMAGIC(sv)
2170                   && (mg = mg_find(sv, PERL_MAGIC_regex_global))
2171                   && mg->mg_len >= 0) {
2172             reginfo.ganch = strbeg + mg->mg_len;        /* Defined pos() */
2173             DEBUG_GPOS_r(PerlIO_printf(Perl_debug_log,
2174                 "GPOS MAGIC: reginfo.ganch = strbeg + %"IVdf"\n",(IV)mg->mg_len));
2175
2176             if (prog->extflags & RXf_ANCH_GPOS) {
2177                 if (s > reginfo.ganch)
2178                     goto phooey;
2179                 s = reginfo.ganch - prog->gofs;
2180                 DEBUG_GPOS_r(PerlIO_printf(Perl_debug_log,
2181                      "GPOS ANCH_GPOS: s = ganch - %"UVxf"\n",(UV)prog->gofs));
2182                 if (s < strbeg)
2183                     goto phooey;
2184             }
2185         }
2186         else if (data) {
2187             reginfo.ganch = strbeg + PTR2UV(data);
2188             DEBUG_GPOS_r(PerlIO_printf(Perl_debug_log,
2189                  "GPOS DATA: reginfo.ganch= strbeg + %"UVxf"\n",PTR2UV(data)));
2190
2191         } else {                                /* pos() not defined */
2192             reginfo.ganch = strbeg;
2193             DEBUG_GPOS_r(PerlIO_printf(Perl_debug_log,
2194                  "GPOS: reginfo.ganch = strbeg\n"));
2195         }
2196     }
2197     if (PL_curpm && (PM_GETRE(PL_curpm) == rx)) {
2198         /* We have to be careful. If the previous successful match
2199            was from this regex we don't want a subsequent partially
2200            successful match to clobber the old results.
2201            So when we detect this possibility we add a swap buffer
2202            to the re, and switch the buffer each match. If we fail
2203            we switch it back, otherwise we leave it swapped.
2204         */
2205         swap = prog->offs;
2206         /* do we need a save destructor here for eval dies? */
2207         Newxz(prog->offs, (prog->nparens + 1), regexp_paren_pair);
2208         DEBUG_BUFFERS_r(PerlIO_printf(Perl_debug_log,
2209             "rex=0x%"UVxf" saving  offs: orig=0x%"UVxf" new=0x%"UVxf"\n",
2210             PTR2UV(prog),
2211             PTR2UV(swap),
2212             PTR2UV(prog->offs)
2213         ));
2214     }
2215     if (!(flags & REXEC_CHECKED) && (prog->check_substr != NULL || prog->check_utf8 != NULL)) {
2216         re_scream_pos_data d;
2217
2218         d.scream_olds = &scream_olds;
2219         d.scream_pos = &scream_pos;
2220         s = re_intuit_start(rx, sv, s, strend, flags, &d);
2221         if (!s) {
2222             DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "Not present...\n"));
2223             goto phooey;        /* not present */
2224         }
2225     }
2226
2227
2228
2229     /* Simplest case:  anchored match need be tried only once. */
2230     /*  [unless only anchor is BOL and multiline is set] */
2231     if (prog->extflags & (RXf_ANCH & ~RXf_ANCH_GPOS)) {
2232         if (s == startpos && regtry(&reginfo, &startpos))
2233             goto got_it;
2234         else if (multiline || (prog->intflags & PREGf_IMPLICIT)
2235                  || (prog->extflags & RXf_ANCH_MBOL)) /* XXXX SBOL? */
2236         {
2237             char *end;
2238
2239             if (minlen)
2240                 dontbother = minlen - 1;
2241             end = HOP3c(strend, -dontbother, strbeg) - 1;
2242             /* for multiline we only have to try after newlines */
2243             if (prog->check_substr || prog->check_utf8) {
2244                 /* because of the goto we can not easily reuse the macros for bifurcating the
2245                    unicode/non-unicode match modes here like we do elsewhere - demerphq */
2246                 if (utf8_target) {
2247                     if (s == startpos)
2248                         goto after_try_utf8;
2249                     while (1) {
2250                         if (regtry(&reginfo, &s)) {
2251                             goto got_it;
2252                         }
2253                       after_try_utf8:
2254                         if (s > end) {
2255                             goto phooey;
2256                         }
2257                         if (prog->extflags & RXf_USE_INTUIT) {
2258                             s = re_intuit_start(rx, sv, s + UTF8SKIP(s), strend, flags, NULL);
2259                             if (!s) {
2260                                 goto phooey;
2261                             }
2262                         }
2263                         else {
2264                             s += UTF8SKIP(s);
2265                         }
2266                     }
2267                 } /* end search for check string in unicode */
2268                 else {
2269                     if (s == startpos) {
2270                         goto after_try_latin;
2271                     }
2272                     while (1) {
2273                         if (regtry(&reginfo, &s)) {
2274                             goto got_it;
2275                         }
2276                       after_try_latin:
2277                         if (s > end) {
2278                             goto phooey;
2279                         }
2280                         if (prog->extflags & RXf_USE_INTUIT) {
2281                             s = re_intuit_start(rx, sv, s + 1, strend, flags, NULL);
2282                             if (!s) {
2283                                 goto phooey;
2284                             }
2285                         }
2286                         else {
2287                             s++;
2288                         }
2289                     }
2290                 } /* end search for check string in latin*/
2291             } /* end search for check string */
2292             else { /* search for newline */
2293                 if (s > startpos) {
2294                     /*XXX: The s-- is almost definitely wrong here under unicode - demeprhq*/
2295                     s--;
2296                 }
2297                 /* We can use a more efficient search as newlines are the same in unicode as they are in latin */
2298                 while (s <= end) { /* note it could be possible to match at the end of the string */
2299                     if (*s++ == '\n') { /* don't need PL_utf8skip here */
2300                         if (regtry(&reginfo, &s))
2301                             goto got_it;
2302                     }
2303                 }
2304             } /* end search for newline */
2305         } /* end anchored/multiline check string search */
2306         goto phooey;
2307     } else if (RXf_GPOS_CHECK == (prog->extflags & RXf_GPOS_CHECK))
2308     {
2309         /* the warning about reginfo.ganch being used without initialization
2310            is bogus -- we set it above, when prog->extflags & RXf_GPOS_SEEN
2311            and we only enter this block when the same bit is set. */
2312         char *tmp_s = reginfo.ganch - prog->gofs;
2313
2314         if (tmp_s >= strbeg && regtry(&reginfo, &tmp_s))
2315             goto got_it;
2316         goto phooey;
2317     }
2318
2319     /* Messy cases:  unanchored match. */
2320     if ((prog->anchored_substr || prog->anchored_utf8) && prog->intflags & PREGf_SKIP) {
2321         /* we have /x+whatever/ */
2322         /* it must be a one character string (XXXX Except UTF_PATTERN?) */
2323         char ch;
2324 #ifdef DEBUGGING
2325         int did_match = 0;
2326 #endif
2327         if (utf8_target) {
2328             if (! prog->anchored_utf8) {
2329                 to_utf8_substr(prog);
2330             }
2331             ch = SvPVX_const(prog->anchored_utf8)[0];
2332             REXEC_FBC_SCAN(
2333                 if (*s == ch) {
2334                     DEBUG_EXECUTE_r( did_match = 1 );
2335                     if (regtry(&reginfo, &s)) goto got_it;
2336                     s += UTF8SKIP(s);
2337                     while (s < strend && *s == ch)
2338                         s += UTF8SKIP(s);
2339                 }
2340             );
2341
2342         }
2343         else {
2344             if (! prog->anchored_substr) {
2345                 if (! to_byte_substr(prog)) {
2346                     DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
2347                                             non_utf8_target_but_utf8_required));
2348                     goto phooey;
2349                 }
2350             }
2351             ch = SvPVX_const(prog->anchored_substr)[0];
2352             REXEC_FBC_SCAN(
2353                 if (*s == ch) {
2354                     DEBUG_EXECUTE_r( did_match = 1 );
2355                     if (regtry(&reginfo, &s)) goto got_it;
2356                     s++;
2357                     while (s < strend && *s == ch)
2358                         s++;
2359                 }
2360             );
2361         }
2362         DEBUG_EXECUTE_r(if (!did_match)
2363                 PerlIO_printf(Perl_debug_log,
2364                                   "Did not find anchored character...\n")
2365                );
2366     }
2367     else if (prog->anchored_substr != NULL
2368               || prog->anchored_utf8 != NULL
2369               || ((prog->float_substr != NULL || prog->float_utf8 != NULL)
2370                   && prog->float_max_offset < strend - s)) {
2371         SV *must;
2372         I32 back_max;
2373         I32 back_min;
2374         char *last;
2375         char *last1;            /* Last position checked before */
2376 #ifdef DEBUGGING
2377         int did_match = 0;
2378 #endif
2379         if (prog->anchored_substr || prog->anchored_utf8) {
2380             if (utf8_target) {
2381                 if (! prog->anchored_utf8) {
2382                     to_utf8_substr(prog);
2383                 }
2384                 must = prog->anchored_utf8;
2385             }
2386             else {
2387                 if (! prog->anchored_substr) {
2388                     if (! to_byte_substr(prog)) {
2389                         DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
2390                                             non_utf8_target_but_utf8_required));
2391                         goto phooey;
2392                     }
2393                 }
2394                 must = prog->anchored_substr;
2395             }
2396             back_max = back_min = prog->anchored_offset;
2397         } else {
2398             if (utf8_target) {
2399                 if (! prog->float_utf8) {
2400                     to_utf8_substr(prog);
2401                 }
2402                 must = prog->float_utf8;
2403             }
2404             else {
2405                 if (! prog->float_substr) {
2406                     if (! to_byte_substr(prog)) {
2407                         DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
2408                                             non_utf8_target_but_utf8_required));
2409                         goto phooey;
2410                     }
2411                 }
2412                 must = prog->float_substr;
2413             }
2414             back_max = prog->float_max_offset;
2415             back_min = prog->float_min_offset;
2416         }
2417
2418         if (back_min<0) {
2419             last = strend;
2420         } else {
2421             last = HOP3c(strend,        /* Cannot start after this */
2422                   -(I32)(CHR_SVLEN(must)
2423                          - (SvTAIL(must) != 0) + back_min), strbeg);
2424         }
2425         if (s > PL_bostr)
2426             last1 = HOPc(s, -1);
2427         else
2428             last1 = s - 1;      /* bogus */
2429
2430         /* XXXX check_substr already used to find "s", can optimize if
2431            check_substr==must. */
2432         scream_pos = -1;
2433         dontbother = end_shift;
2434         strend = HOPc(strend, -dontbother);
2435         while ( (s <= last) &&
2436                 (s = fbm_instr((unsigned char*)HOP3(s, back_min, (back_min<0 ? strbeg : strend)),
2437                                   (unsigned char*)strend, must,
2438                                   multiline ? FBMrf_MULTILINE : 0)) ) {
2439             DEBUG_EXECUTE_r( did_match = 1 );
2440             if (HOPc(s, -back_max) > last1) {
2441                 last1 = HOPc(s, -back_min);
2442                 s = HOPc(s, -back_max);
2443             }
2444             else {
2445                 char * const t = (last1 >= PL_bostr) ? HOPc(last1, 1) : last1 + 1;
2446
2447                 last1 = HOPc(s, -back_min);
2448                 s = t;
2449             }
2450             if (utf8_target) {
2451                 while (s <= last1) {
2452                     if (regtry(&reginfo, &s))
2453                         goto got_it;
2454                     if (s >= last1) {
2455                         s++; /* to break out of outer loop */
2456                         break;
2457                     }
2458                     s += UTF8SKIP(s);
2459                 }
2460             }
2461             else {
2462                 while (s <= last1) {
2463                     if (regtry(&reginfo, &s))
2464                         goto got_it;
2465                     s++;
2466                 }
2467             }
2468         }
2469         DEBUG_EXECUTE_r(if (!did_match) {
2470             RE_PV_QUOTED_DECL(quoted, utf8_target, PERL_DEBUG_PAD_ZERO(0),
2471                 SvPVX_const(must), RE_SV_DUMPLEN(must), 30);
2472             PerlIO_printf(Perl_debug_log, "Did not find %s substr %s%s...\n",
2473                               ((must == prog->anchored_substr || must == prog->anchored_utf8)
2474                                ? "anchored" : "floating"),
2475                 quoted, RE_SV_TAIL(must));
2476         });
2477         goto phooey;
2478     }
2479     else if ( (c = progi->regstclass) ) {
2480         if (minlen) {
2481             const OPCODE op = OP(progi->regstclass);
2482             /* don't bother with what can't match */
2483             if (PL_regkind[op] != EXACT && op != CANY && PL_regkind[op] != TRIE)
2484                 strend = HOPc(strend, -(minlen - 1));
2485         }
2486         DEBUG_EXECUTE_r({
2487             SV * const prop = sv_newmortal();
2488             regprop(prog, prop, c);
2489             {
2490                 RE_PV_QUOTED_DECL(quoted,utf8_target,PERL_DEBUG_PAD_ZERO(1),
2491                     s,strend-s,60);
2492                 PerlIO_printf(Perl_debug_log,
2493                     "Matching stclass %.*s against %s (%d bytes)\n",
2494                     (int)SvCUR(prop), SvPVX_const(prop),
2495                      quoted, (int)(strend - s));
2496             }
2497         });
2498         if (find_byclass(prog, c, s, strend, &reginfo))
2499             goto got_it;
2500         DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "Contradicts stclass... [regexec_flags]\n"));
2501     }
2502     else {
2503         dontbother = 0;
2504         if (prog->float_substr != NULL || prog->float_utf8 != NULL) {
2505             /* Trim the end. */
2506             char *last= NULL;
2507             SV* float_real;
2508             STRLEN len;
2509             const char *little;
2510
2511             if (utf8_target) {
2512                 if (! prog->float_utf8) {
2513                     to_utf8_substr(prog);
2514                 }
2515                 float_real = prog->float_utf8;
2516             }
2517             else {
2518                 if (! prog->float_substr) {
2519                     if (! to_byte_substr(prog)) {
2520                         DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
2521                                             non_utf8_target_but_utf8_required));
2522                         goto phooey;
2523                     }
2524                 }
2525                 float_real = prog->float_substr;
2526             }
2527
2528             little = SvPV_const(float_real, len);
2529             if (SvTAIL(float_real)) {
2530                     /* This means that float_real contains an artificial \n on
2531                      * the end due to the presence of something like this:
2532                      * /foo$/ where we can match both "foo" and "foo\n" at the
2533                      * end of the string.  So we have to compare the end of the
2534                      * string first against the float_real without the \n and
2535                      * then against the full float_real with the string.  We
2536                      * have to watch out for cases where the string might be
2537                      * smaller than the float_real or the float_real without
2538                      * the \n. */
2539                     char *checkpos= strend - len;
2540                     DEBUG_OPTIMISE_r(
2541                         PerlIO_printf(Perl_debug_log,
2542                             "%sChecking for float_real.%s\n",
2543                             PL_colors[4], PL_colors[5]));
2544                     if (checkpos + 1 < strbeg) {
2545                         /* can't match, even if we remove the trailing \n
2546                          * string is too short to match */
2547                         DEBUG_EXECUTE_r(
2548                             PerlIO_printf(Perl_debug_log,
2549                                 "%sString shorter than required trailing substring, cannot match.%s\n",
2550                                 PL_colors[4], PL_colors[5]));
2551                         goto phooey;
2552                     } else if (memEQ(checkpos + 1, little, len - 1)) {
2553                         /* can match, the end of the string matches without the
2554                          * "\n" */
2555                         last = checkpos + 1;
2556                     } else if (checkpos < strbeg) {
2557                         /* cant match, string is too short when the "\n" is
2558                          * included */
2559                         DEBUG_EXECUTE_r(
2560                             PerlIO_printf(Perl_debug_log,
2561                                 "%sString does not contain required trailing substring, cannot match.%s\n",
2562                                 PL_colors[4], PL_colors[5]));
2563                         goto phooey;
2564                     } else if (!multiline) {
2565                         /* non multiline match, so compare with the "\n" at the
2566                          * end of the string */
2567                         if (memEQ(checkpos, little, len)) {
2568                             last= checkpos;
2569                         } else {
2570                             DEBUG_EXECUTE_r(
2571                                 PerlIO_printf(Perl_debug_log,
2572                                     "%sString does not contain required trailing substring, cannot match.%s\n",
2573                                     PL_colors[4], PL_colors[5]));
2574                             goto phooey;
2575                         }
2576                     } else {
2577                         /* multiline match, so we have to search for a place
2578                          * where the full string is located */
2579                         goto find_last;
2580                     }
2581             } else {
2582                   find_last:
2583                     if (len)
2584                         last = rninstr(s, strend, little, little + len);
2585                     else
2586                         last = strend;  /* matching "$" */
2587             }
2588             if (!last) {
2589                 /* at one point this block contained a comment which was
2590                  * probably incorrect, which said that this was a "should not
2591                  * happen" case.  Even if it was true when it was written I am
2592                  * pretty sure it is not anymore, so I have removed the comment
2593                  * and replaced it with this one. Yves */
2594                 DEBUG_EXECUTE_r(
2595                     PerlIO_printf(Perl_debug_log,
2596                         "String does not contain required substring, cannot match.\n"
2597                     ));
2598                 goto phooey;
2599             }
2600             dontbother = strend - last + prog->float_min_offset;
2601         }
2602         if (minlen && (dontbother < minlen))
2603             dontbother = minlen - 1;
2604         strend -= dontbother;              /* this one's always in bytes! */
2605         /* We don't know much -- general case. */
2606         if (utf8_target) {
2607             for (;;) {
2608                 if (regtry(&reginfo, &s))
2609                     goto got_it;
2610                 if (s >= strend)
2611                     break;
2612                 s += UTF8SKIP(s);
2613             };
2614         }
2615         else {
2616             do {
2617                 if (regtry(&reginfo, &s))
2618                     goto got_it;
2619             } while (s++ < strend);
2620         }
2621     }
2622
2623     /* Failure. */
2624     goto phooey;
2625
2626 got_it:
2627     DEBUG_BUFFERS_r(
2628         if (swap)
2629             PerlIO_printf(Perl_debug_log,
2630                 "rex=0x%"UVxf" freeing offs: 0x%"UVxf"\n",
2631                 PTR2UV(prog),
2632                 PTR2UV(swap)
2633             );
2634     );
2635     Safefree(swap);
2636     RX_MATCH_TAINTED_set(rx, PL_reg_flags & RF_tainted);
2637
2638     if (PL_reg_state.re_state_eval_setup_done)
2639         restore_pos(aTHX_ prog);
2640     if (RXp_PAREN_NAMES(prog))
2641         (void)hv_iterinit(RXp_PAREN_NAMES(prog));
2642
2643     /* make sure $`, $&, $', and $digit will work later */
2644     if ( !(flags & REXEC_NOT_FIRST) ) {
2645         if (flags & REXEC_COPY_STR) {
2646 #ifdef PERL_OLD_COPY_ON_WRITE
2647             if ((SvIsCOW(sv)
2648                  || (SvFLAGS(sv) & CAN_COW_MASK) == CAN_COW_FLAGS)) {
2649                 if (DEBUG_C_TEST) {
2650                     PerlIO_printf(Perl_debug_log,
2651                                   "Copy on write: regexp capture, type %d\n",
2652                                   (int) SvTYPE(sv));
2653                 }
2654                 RX_MATCH_COPY_FREE(rx);
2655                 prog->saved_copy = sv_setsv_cow(prog->saved_copy, sv);
2656                 prog->subbeg = (char *)SvPVX_const(prog->saved_copy);
2657                 assert (SvPOKp(prog->saved_copy));
2658                 prog->sublen  = PL_regeol - strbeg;
2659                 prog->suboffset = 0;
2660                 prog->subcoffset = 0;
2661             } else
2662 #endif
2663             {
2664                 I32 min = 0;
2665                 I32 max = PL_regeol - strbeg;
2666                 I32 sublen;
2667
2668                 if (    (flags & REXEC_COPY_SKIP_POST)
2669                     && !(RX_EXTFLAGS(rx) & RXf_PMf_KEEPCOPY) /* //p */
2670                     && !(PL_sawampersand & SAWAMPERSAND_RIGHT)
2671                 ) { /* don't copy $' part of string */
2672                     U32 n = 0;
2673                     max = -1;
2674                     /* calculate the right-most part of the string covered
2675                      * by a capture. Due to look-ahead, this may be to
2676                      * the right of $&, so we have to scan all captures */
2677                     while (n <= prog->lastparen) {
2678                         if (prog->offs[n].end > max)
2679                             max = prog->offs[n].end;
2680                         n++;
2681                     }
2682                     if (max == -1)
2683                         max = (PL_sawampersand & SAWAMPERSAND_LEFT)
2684                                 ? prog->offs[0].start
2685                                 : 0;
2686                     assert(max >= 0 && max <= PL_regeol - strbeg);
2687                 }
2688
2689                 if (    (flags & REXEC_COPY_SKIP_PRE)
2690                     && !(RX_EXTFLAGS(rx) & RXf_PMf_KEEPCOPY) /* //p */
2691                     && !(PL_sawampersand & SAWAMPERSAND_LEFT)
2692                 ) { /* don't copy $` part of string */
2693                     U32 n = 0;
2694                     min = max;
2695                     /* calculate the left-most part of the string covered
2696                      * by a capture. Due to look-behind, this may be to
2697                      * the left of $&, so we have to scan all captures */
2698                     while (min && n <= prog->lastparen) {
2699                         if (   prog->offs[n].start != -1
2700                             && prog->offs[n].start < min)
2701                         {
2702                             min = prog->offs[n].start;
2703                         }
2704                         n++;
2705                     }
2706                     if ((PL_sawampersand & SAWAMPERSAND_RIGHT)
2707                         && min >  prog->offs[0].end
2708                     )
2709                         min = prog->offs[0].end;
2710
2711                 }
2712
2713                 assert(min >= 0 && min <= max && min <= PL_regeol - strbeg);
2714                 sublen = max - min;
2715
2716                 if (RX_MATCH_COPIED(rx)) {
2717                     if (sublen > prog->sublen)
2718                         prog->subbeg =
2719                                 (char*)saferealloc(prog->subbeg, sublen+1);
2720                 }
2721                 else
2722                     prog->subbeg = (char*)safemalloc(sublen+1);
2723                 Copy(strbeg + min, prog->subbeg, sublen, char);
2724                 prog->subbeg[sublen] = '\0';
2725                 prog->suboffset = min;
2726                 prog->sublen = sublen;
2727                 RX_MATCH_COPIED_on(rx);
2728             }
2729             prog->subcoffset = prog->suboffset;
2730             if (prog->suboffset && utf8_target) {
2731                 /* Convert byte offset to chars.
2732                  * XXX ideally should only compute this if @-/@+
2733                  * has been seen, a la PL_sawampersand ??? */
2734
2735                 /* If there's a direct correspondence between the
2736                  * string which we're matching and the original SV,
2737                  * then we can use the utf8 len cache associated with
2738                  * the SV. In particular, it means that under //g,
2739                  * sv_pos_b2u() will use the previously cached
2740                  * position to speed up working out the new length of
2741                  * subcoffset, rather than counting from the start of
2742                  * the string each time. This stops
2743                  *   $x = "\x{100}" x 1E6; 1 while $x =~ /(.)/g;
2744                  * from going quadratic */
2745                 if (SvPOKp(sv) && SvPVX(sv) == strbeg)
2746                     sv_pos_b2u(sv, &(prog->subcoffset));
2747                 else
2748                     prog->subcoffset = utf8_length((U8*)strbeg,
2749                                         (U8*)(strbeg+prog->suboffset));
2750             }
2751         }
2752         else {
2753             RX_MATCH_COPY_FREE(rx);
2754             prog->subbeg = strbeg;
2755             prog->suboffset = 0;
2756             prog->subcoffset = 0;
2757             prog->sublen = PL_regeol - strbeg;  /* strend may have been modified */
2758         }
2759     }
2760
2761     return 1;
2762
2763 phooey:
2764     DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "%sMatch failed%s\n",
2765                           PL_colors[4], PL_colors[5]));
2766     if (PL_reg_state.re_state_eval_setup_done)
2767         restore_pos(aTHX_ prog);
2768     if (swap) {
2769         /* we failed :-( roll it back */
2770         DEBUG_BUFFERS_r(PerlIO_printf(Perl_debug_log,
2771             "rex=0x%"UVxf" rolling back offs: freeing=0x%"UVxf" restoring=0x%"UVxf"\n",
2772             PTR2UV(prog),
2773             PTR2UV(prog->offs),
2774             PTR2UV(swap)
2775         ));
2776         Safefree(prog->offs);
2777         prog->offs = swap;
2778     }
2779     return 0;
2780 }
2781
2782
2783 /* Set which rex is pointed to by PL_reg_state, handling ref counting.
2784  * Do inc before dec, in case old and new rex are the same */
2785 #define SET_reg_curpm(Re2) \
2786     if (PL_reg_state.re_state_eval_setup_done) {    \
2787         (void)ReREFCNT_inc(Re2);                    \
2788         ReREFCNT_dec(PM_GETRE(PL_reg_curpm));       \
2789         PM_SETRE((PL_reg_curpm), (Re2));            \
2790     }
2791
2792
2793 /*
2794  - regtry - try match at specific point
2795  */
2796 STATIC I32                      /* 0 failure, 1 success */
2797 S_regtry(pTHX_ regmatch_info *reginfo, char **startposp)
2798 {
2799     dVAR;
2800     CHECKPOINT lastcp;
2801     REGEXP *const rx = reginfo->prog;
2802     regexp *const prog = (struct regexp *)SvANY(rx);
2803     I32 result;
2804     RXi_GET_DECL(prog,progi);
2805     GET_RE_DEBUG_FLAGS_DECL;
2806
2807     PERL_ARGS_ASSERT_REGTRY;
2808
2809     reginfo->cutpoint=NULL;
2810
2811     if ((prog->extflags & RXf_EVAL_SEEN)
2812         && !PL_reg_state.re_state_eval_setup_done)
2813     {
2814         MAGIC *mg;
2815
2816         PL_reg_state.re_state_eval_setup_done = TRUE;
2817         if (reginfo->sv) {
2818             /* Make $_ available to executed code. */
2819             if (reginfo->sv != DEFSV) {
2820                 SAVE_DEFSV;
2821                 DEFSV_set(reginfo->sv);
2822             }
2823
2824             if (!(SvTYPE(reginfo->sv) >= SVt_PVMG && SvMAGIC(reginfo->sv)
2825                   && (mg = mg_find(reginfo->sv, PERL_MAGIC_regex_global)))) {
2826                 /* prepare for quick setting of pos */
2827 #ifdef PERL_OLD_COPY_ON_WRITE
2828                 if (SvIsCOW(reginfo->sv))
2829                     sv_force_normal_flags(reginfo->sv, 0);
2830 #endif
2831                 mg = sv_magicext(reginfo->sv, NULL, PERL_MAGIC_regex_global,
2832                                  &PL_vtbl_mglob, NULL, 0);
2833                 mg->mg_len = -1;
2834             }
2835             PL_reg_magic    = mg;
2836             PL_reg_oldpos   = mg->mg_len;
2837             SAVEDESTRUCTOR_X(restore_pos, prog);
2838         }
2839         if (!PL_reg_curpm) {
2840             Newxz(PL_reg_curpm, 1, PMOP);
2841 #ifdef USE_ITHREADS
2842             {
2843                 SV* const repointer = &PL_sv_undef;
2844                 /* this regexp is also owned by the new PL_reg_curpm, which
2845                    will try to free it.  */
2846                 av_push(PL_regex_padav, repointer);
2847                 PL_reg_curpm->op_pmoffset = av_len(PL_regex_padav);
2848                 PL_regex_pad = AvARRAY(PL_regex_padav);
2849             }
2850 #endif
2851         }
2852         SET_reg_curpm(rx);
2853         PL_reg_oldcurpm = PL_curpm;
2854         PL_curpm = PL_reg_curpm;
2855         if (RXp_MATCH_COPIED(prog)) {
2856             /*  Here is a serious problem: we cannot rewrite subbeg,
2857                 since it may be needed if this match fails.  Thus
2858                 $` inside (?{}) could fail... */
2859             PL_reg_oldsaved = prog->subbeg;
2860             PL_reg_oldsavedlen = prog->sublen;
2861             PL_reg_oldsavedoffset = prog->suboffset;
2862             PL_reg_oldsavedcoffset = prog->suboffset;
2863 #ifdef PERL_OLD_COPY_ON_WRITE
2864             PL_nrs = prog->saved_copy;
2865 #endif
2866             RXp_MATCH_COPIED_off(prog);
2867         }
2868         else
2869             PL_reg_oldsaved = NULL;
2870         prog->subbeg = PL_bostr;
2871         prog->suboffset = 0;
2872         prog->subcoffset = 0;
2873         prog->sublen = PL_regeol - PL_bostr; /* strend may have been modified */
2874     }
2875 #ifdef DEBUGGING
2876     PL_reg_starttry = *startposp;
2877 #endif
2878     prog->offs[0].start = *startposp - PL_bostr;
2879     prog->lastparen = 0;
2880     prog->lastcloseparen = 0;
2881     PL_regsize = 0;
2882
2883     /* XXXX What this code is doing here?!!!  There should be no need
2884        to do this again and again, prog->lastparen should take care of
2885        this!  --ilya*/
2886
2887     /* Tests pat.t#187 and split.t#{13,14} seem to depend on this code.
2888      * Actually, the code in regcppop() (which Ilya may be meaning by
2889      * prog->lastparen), is not needed at all by the test suite
2890      * (op/regexp, op/pat, op/split), but that code is needed otherwise
2891      * this erroneously leaves $1 defined: "1" =~ /^(?:(\d)x)?\d$/
2892      * Meanwhile, this code *is* needed for the
2893      * above-mentioned test suite tests to succeed.  The common theme
2894      * on those tests seems to be returning null fields from matches.
2895      * --jhi updated by dapm */
2896 #if 1
2897     if (prog->nparens) {
2898         regexp_paren_pair *pp = prog->offs;
2899         I32 i;
2900         for (i = prog->nparens; i > (I32)prog->lastparen; i--) {
2901             ++pp;
2902             pp->start = -1;
2903             pp->end = -1;
2904         }
2905     }
2906 #endif
2907     REGCP_SET(lastcp);
2908     result = regmatch(reginfo, *startposp, progi->program + 1);
2909     if (result != -1) {
2910         prog->offs[0].end = result;
2911         return 1;
2912     }
2913     if (reginfo->cutpoint)
2914         *startposp= reginfo->cutpoint;
2915     REGCP_UNWIND(lastcp);
2916     return 0;
2917 }
2918
2919
2920 #define sayYES goto yes
2921 #define sayNO goto no
2922 #define sayNO_SILENT goto no_silent
2923
2924 /* we dont use STMT_START/END here because it leads to
2925    "unreachable code" warnings, which are bogus, but distracting. */
2926 #define CACHEsayNO \
2927     if (ST.cache_mask) \
2928        PL_reg_poscache[ST.cache_offset] |= ST.cache_mask; \
2929     sayNO
2930
2931 /* this is used to determine how far from the left messages like
2932    'failed...' are printed. It should be set such that messages
2933    are inline with the regop output that created them.
2934 */
2935 #define REPORT_CODE_OFF 32
2936
2937
2938 #define CHRTEST_UNINIT -1001 /* c1/c2 haven't been calculated yet */
2939 #define CHRTEST_VOID   -1000 /* the c1/c2 "next char" test should be skipped */
2940
2941 #define SLAB_FIRST(s) (&(s)->states[0])
2942 #define SLAB_LAST(s)  (&(s)->states[PERL_REGMATCH_SLAB_SLOTS-1])
2943
2944 /* grab a new slab and return the first slot in it */
2945
2946 STATIC regmatch_state *
2947 S_push_slab(pTHX)
2948 {
2949 #if PERL_VERSION < 9 && !defined(PERL_CORE)
2950     dMY_CXT;
2951 #endif
2952     regmatch_slab *s = PL_regmatch_slab->next;
2953     if (!s) {
2954         Newx(s, 1, regmatch_slab);
2955         s->prev = PL_regmatch_slab;
2956         s->next = NULL;
2957         PL_regmatch_slab->next = s;
2958     }
2959     PL_regmatch_slab = s;
2960     return SLAB_FIRST(s);
2961 }
2962
2963
2964 /* push a new state then goto it */
2965
2966 #define PUSH_STATE_GOTO(state, node, input) \
2967     pushinput = input; \
2968     scan = node; \
2969     st->resume_state = state; \
2970     goto push_state;
2971
2972 /* push a new state with success backtracking, then goto it */
2973
2974 #define PUSH_YES_STATE_GOTO(state, node, input) \
2975     pushinput = input; \
2976     scan = node; \
2977     st->resume_state = state; \
2978     goto push_yes_state;
2979
2980
2981
2982
2983 /*
2984
2985 regmatch() - main matching routine
2986
2987 This is basically one big switch statement in a loop. We execute an op,
2988 set 'next' to point the next op, and continue. If we come to a point which
2989 we may need to backtrack to on failure such as (A|B|C), we push a
2990 backtrack state onto the backtrack stack. On failure, we pop the top
2991 state, and re-enter the loop at the state indicated. If there are no more
2992 states to pop, we return failure.
2993
2994 Sometimes we also need to backtrack on success; for example /A+/, where
2995 after successfully matching one A, we need to go back and try to
2996 match another one; similarly for lookahead assertions: if the assertion
2997 completes successfully, we backtrack to the state just before the assertion
2998 and then carry on.  In these cases, the pushed state is marked as
2999 'backtrack on success too'. This marking is in fact done by a chain of
3000 pointers, each pointing to the previous 'yes' state. On success, we pop to
3001 the nearest yes state, discarding any intermediate failure-only states.
3002 Sometimes a yes state is pushed just to force some cleanup code to be
3003 called at the end of a successful match or submatch; e.g. (??{$re}) uses
3004 it to free the inner regex.
3005
3006 Note that failure backtracking rewinds the cursor position, while
3007 success backtracking leaves it alone.
3008
3009 A pattern is complete when the END op is executed, while a subpattern
3010 such as (?=foo) is complete when the SUCCESS op is executed. Both of these
3011 ops trigger the "pop to last yes state if any, otherwise return true"
3012 behaviour.
3013
3014 A common convention in this function is to use A and B to refer to the two
3015 subpatterns (or to the first nodes thereof) in patterns like /A*B/: so A is
3016 the subpattern to be matched possibly multiple times, while B is the entire
3017 rest of the pattern. Variable and state names reflect this convention.
3018
3019 The states in the main switch are the union of ops and failure/success of
3020 substates associated with with that op.  For example, IFMATCH is the op
3021 that does lookahead assertions /(?=A)B/ and so the IFMATCH state means
3022 'execute IFMATCH'; while IFMATCH_A is a state saying that we have just
3023 successfully matched A and IFMATCH_A_fail is a state saying that we have
3024 just failed to match A. Resume states always come in pairs. The backtrack
3025 state we push is marked as 'IFMATCH_A', but when that is popped, we resume
3026 at IFMATCH_A or IFMATCH_A_fail, depending on whether we are backtracking
3027 on success or failure.
3028
3029 The struct that holds a backtracking state is actually a big union, with
3030 one variant for each major type of op. The variable st points to the
3031 top-most backtrack struct. To make the code clearer, within each
3032 block of code we #define ST to alias the relevant union.
3033
3034 Here's a concrete example of a (vastly oversimplified) IFMATCH
3035 implementation:
3036
3037     switch (state) {
3038     ....
3039
3040 #define ST st->u.ifmatch
3041
3042     case IFMATCH: // we are executing the IFMATCH op, (?=A)B
3043         ST.foo = ...; // some state we wish to save
3044         ...
3045         // push a yes backtrack state with a resume value of
3046         // IFMATCH_A/IFMATCH_A_fail, then continue execution at the
3047         // first node of A:
3048         PUSH_YES_STATE_GOTO(IFMATCH_A, A, newinput);
3049         // NOTREACHED
3050
3051     case IFMATCH_A: // we have successfully executed A; now continue with B
3052         next = B;
3053         bar = ST.foo; // do something with the preserved value
3054         break;
3055
3056     case IFMATCH_A_fail: // A failed, so the assertion failed
3057         ...;   // do some housekeeping, then ...
3058         sayNO; // propagate the failure
3059
3060 #undef ST
3061
3062     ...
3063     }
3064
3065 For any old-timers reading this who are familiar with the old recursive
3066 approach, the code above is equivalent to:
3067
3068     case IFMATCH: // we are executing the IFMATCH op, (?=A)B
3069     {
3070         int foo = ...
3071         ...
3072         if (regmatch(A)) {
3073             next = B;
3074             bar = foo;
3075             break;
3076         }
3077         ...;   // do some housekeeping, then ...
3078         sayNO; // propagate the failure
3079     }
3080
3081 The topmost backtrack state, pointed to by st, is usually free. If you
3082 want to claim it, populate any ST.foo fields in it with values you wish to
3083 save, then do one of
3084
3085         PUSH_STATE_GOTO(resume_state, node, newinput);
3086         PUSH_YES_STATE_GOTO(resume_state, node, newinput);
3087
3088 which sets that backtrack state's resume value to 'resume_state', pushes a
3089 new free entry to the top of the backtrack stack, then goes to 'node'.
3090 On backtracking, the free slot is popped, and the saved state becomes the
3091 new free state. An ST.foo field in this new top state can be temporarily
3092 accessed to retrieve values, but once the main loop is re-entered, it
3093 becomes available for reuse.
3094
3095 Note that the depth of the backtrack stack constantly increases during the
3096 left-to-right execution of the pattern, rather than going up and down with
3097 the pattern nesting. For example the stack is at its maximum at Z at the
3098 end of the pattern, rather than at X in the following:
3099
3100     /(((X)+)+)+....(Y)+....Z/
3101
3102 The only exceptions to this are lookahead/behind assertions and the cut,
3103 (?>A), which pop all the backtrack states associated with A before
3104 continuing.
3105
3106 Backtrack state structs are allocated in slabs of about 4K in size.
3107 PL_regmatch_state and st always point to the currently active state,
3108 and PL_regmatch_slab points to the slab currently containing
3109 PL_regmatch_state.  The first time regmatch() is called, the first slab is
3110 allocated, and is never freed until interpreter destruction. When the slab
3111 is full, a new one is allocated and chained to the end. At exit from
3112 regmatch(), slabs allocated since entry are freed.
3113
3114 */
3115
3116
3117 #define DEBUG_STATE_pp(pp)                                  \
3118     DEBUG_STATE_r({                                         \
3119         DUMP_EXEC_POS(locinput, scan, utf8_target);                 \
3120         PerlIO_printf(Perl_debug_log,                       \
3121             "    %*s"pp" %s%s%s%s%s\n",                     \
3122             depth*2, "",                                    \
3123             PL_reg_name[st->resume_state],                     \
3124             ((st==yes_state||st==mark_state) ? "[" : ""),   \
3125             ((st==yes_state) ? "Y" : ""),                   \
3126             ((st==mark_state) ? "M" : ""),                  \
3127             ((st==yes_state||st==mark_state) ? "]" : "")    \
3128         );                                                  \
3129     });
3130
3131
3132 #define REG_NODE_NUM(x) ((x) ? (int)((x)-prog) : -1)
3133
3134 #ifdef DEBUGGING
3135
3136 STATIC void
3137 S_debug_start_match(pTHX_ const REGEXP *prog, const bool utf8_target,
3138     const char *start, const char *end, const char *blurb)
3139 {
3140     const bool utf8_pat = RX_UTF8(prog) ? 1 : 0;
3141
3142     PERL_ARGS_ASSERT_DEBUG_START_MATCH;
3143
3144     if (!PL_colorset)
3145             reginitcolors();
3146     {
3147         RE_PV_QUOTED_DECL(s0, utf8_pat, PERL_DEBUG_PAD_ZERO(0),
3148             RX_PRECOMP_const(prog), RX_PRELEN(prog), 60);
3149
3150         RE_PV_QUOTED_DECL(s1, utf8_target, PERL_DEBUG_PAD_ZERO(1),
3151             start, end - start, 60);
3152
3153         PerlIO_printf(Perl_debug_log,
3154             "%s%s REx%s %s against %s\n",
3155                        PL_colors[4], blurb, PL_colors[5], s0, s1);
3156
3157         if (utf8_target||utf8_pat)
3158             PerlIO_printf(Perl_debug_log, "UTF-8 %s%s%s...\n",
3159                 utf8_pat ? "pattern" : "",
3160                 utf8_pat && utf8_target ? " and " : "",
3161                 utf8_target ? "string" : ""
3162             );
3163     }
3164 }
3165
3166 STATIC void
3167 S_dump_exec_pos(pTHX_ const char *locinput,
3168                       const regnode *scan,
3169                       const char *loc_regeol,
3170                       const char *loc_bostr,
3171                       const char *loc_reg_starttry,
3172                       const bool utf8_target)
3173 {
3174     const int docolor = *PL_colors[0] || *PL_colors[2] || *PL_colors[4];
3175     const int taill = (docolor ? 10 : 7); /* 3 chars for "> <" */
3176     int l = (loc_regeol - locinput) > taill ? taill : (loc_regeol - locinput);
3177     /* The part of the string before starttry has one color
3178        (pref0_len chars), between starttry and current
3179        position another one (pref_len - pref0_len chars),
3180        after the current position the third one.
3181        We assume that pref0_len <= pref_len, otherwise we
3182        decrease pref0_len.  */
3183     int pref_len = (locinput - loc_bostr) > (5 + taill) - l
3184         ? (5 + taill) - l : locinput - loc_bostr;
3185     int pref0_len;
3186
3187     PERL_ARGS_ASSERT_DUMP_EXEC_POS;
3188
3189     while (utf8_target && UTF8_IS_CONTINUATION(*(U8*)(locinput - pref_len)))
3190         pref_len++;
3191     pref0_len = pref_len  - (locinput - loc_reg_starttry);
3192     if (l + pref_len < (5 + taill) && l < loc_regeol - locinput)
3193         l = ( loc_regeol - locinput > (5 + taill) - pref_len
3194               ? (5 + taill) - pref_len : loc_regeol - locinput);
3195     while (utf8_target && UTF8_IS_CONTINUATION(*(U8*)(locinput + l)))
3196         l--;
3197     if (pref0_len < 0)
3198         pref0_len = 0;
3199     if (pref0_len > pref_len)
3200         pref0_len = pref_len;
3201     {
3202         const int is_uni = (utf8_target && OP(scan) != CANY) ? 1 : 0;
3203
3204         RE_PV_COLOR_DECL(s0,len0,is_uni,PERL_DEBUG_PAD(0),
3205             (locinput - pref_len),pref0_len, 60, 4, 5);
3206
3207         RE_PV_COLOR_DECL(s1,len1,is_uni,PERL_DEBUG_PAD(1),
3208                     (locinput - pref_len + pref0_len),
3209                     pref_len - pref0_len, 60, 2, 3);
3210
3211         RE_PV_COLOR_DECL(s2,len2,is_uni,PERL_DEBUG_PAD(2),
3212                     locinput, loc_regeol - locinput, 10, 0, 1);
3213
3214         const STRLEN tlen=len0+len1+len2;
3215         PerlIO_printf(Perl_debug_log,
3216                     "%4"IVdf" <%.*s%.*s%s%.*s>%*s|",
3217                     (IV)(locinput - loc_bostr),
3218                     len0, s0,
3219                     len1, s1,
3220                     (docolor ? "" : "> <"),
3221                     len2, s2,
3222                     (int)(tlen > 19 ? 0 :  19 - tlen),
3223                     "");
3224     }
3225 }
3226
3227 #endif
3228
3229 /* reg_check_named_buff_matched()
3230  * Checks to see if a named buffer has matched. The data array of
3231  * buffer numbers corresponding to the buffer is expected to reside
3232  * in the regexp->data->data array in the slot stored in the ARG() of
3233  * node involved. Note that this routine doesn't actually care about the
3234  * name, that information is not preserved from compilation to execution.
3235  * Returns the index of the leftmost defined buffer with the given name
3236  * or 0 if non of the buffers matched.
3237  */
3238 STATIC I32
3239 S_reg_check_named_buff_matched(pTHX_ const regexp *rex, const regnode *scan)
3240 {
3241     I32 n;
3242     RXi_GET_DECL(rex,rexi);
3243     SV *sv_dat= MUTABLE_SV(rexi->data->data[ ARG( scan ) ]);
3244     I32 *nums=(I32*)SvPVX(sv_dat);
3245
3246     PERL_ARGS_ASSERT_REG_CHECK_NAMED_BUFF_MATCHED;
3247
3248     for ( n=0; n<SvIVX(sv_dat); n++ ) {
3249         if ((I32)rex->lastparen >= nums[n] &&
3250             rex->offs[nums[n]].end != -1)
3251         {
3252             return nums[n];
3253         }
3254     }
3255     return 0;
3256 }
3257
3258
3259 /* free all slabs above current one  - called during LEAVE_SCOPE */
3260
3261 STATIC void
3262 S_clear_backtrack_stack(pTHX_ void *p)
3263 {
3264     regmatch_slab *s = PL_regmatch_slab->next;
3265     PERL_UNUSED_ARG(p);
3266
3267     if (!s)
3268         return;
3269     PL_regmatch_slab->next = NULL;
3270     while (s) {
3271         regmatch_slab * const osl = s;
3272         s = s->next;
3273         Safefree(osl);
3274     }
3275 }
3276 static bool
3277 S_setup_EXACTISH_ST_c1_c2(pTHX_ regnode *text_node, I32 *c1, I32 *c2)
3278 {
3279     /* This sets up a relatively quick check for the initial part of what must
3280      * match after a CURLY-type operation condition (the "B" in A*B), where B
3281      * starts with an EXACTish node, <text_node>.  If this check is not met,
3282      * the caller knows that it should continue with the loop.  If the check is
3283      * met, the caller must see if all of B is met, before making the decision.
3284      *
3285      * This function sets *<c1> and *<c2> to be the first code point of B.  If
3286      * there are two possible such code points (as when the text_node is
3287      * folded), *<c2> is set to the second.  If there are more than two (which
3288      * happens for some folds), or there is some other complication, these
3289      * parameters are set to CHRTEST_VOID, to indicate not to do a quick check:
3290      * just try all of B after every time through the loop.
3291      *
3292      * If the routine determines that there is no possible way for there to be
3293      * a match, it returns FALSE.
3294      * */
3295
3296     const bool utf8_target = PL_reg_match_utf8;
3297     const U32 uniflags = UTF8_ALLOW_DEFAULT;
3298     dVAR;
3299
3300     /* First byte from the EXACTish node */
3301     U8 *pat_byte = (U8*)STRING(text_node);
3302
3303     if (! UTF_PATTERN) {    /* Not UTF-8: the code point is the byte */
3304         *c1 = *pat_byte;
3305         if (OP(text_node) == EXACT) {
3306             *c2 = *c1;
3307         }
3308         else if (utf8_target
3309                  && HAS_NONLATIN1_FOLD_CLOSURE(*c1)
3310                  && (OP(text_node) != EXACTFA || ! isASCII(*c1)))
3311         {
3312             /* Here, there could be something above Latin1 in the target which
3313              * folds to this character in the pattern, which means there are
3314              * more than two possible beginnings of B. */
3315             *c1 = *c2 = CHRTEST_VOID;
3316         }
3317         else { /* Here nothing above Latin1 can fold to the pattern character */
3318             switch (OP(text_node)) {
3319
3320                 case EXACTFL:   /* /l rules */
3321                     *c2 = PL_fold_locale[*c1];
3322                     break;
3323
3324                 case EXACTFU_SS: /* This requires special handling: Don't
3325                                     shortcut */
3326                     *c1 = *c2 = CHRTEST_VOID;
3327                     break;
3328
3329                 case EXACTF:
3330                     if (! utf8_target) {    /* /d rules */
3331                         *c2 = PL_fold[*c1];
3332                         break;
3333                     }
3334                     /* FALLTHROUGH */
3335                     /* /u rules for all these.  This happens to work for
3336                      * EXACTFA in the ASCII range as nothing in Latin1 folds to
3337                      * ASCII */
3338                 case EXACTFA:
3339                 case EXACTFU_TRICKYFOLD:
3340                 case EXACTFU:
3341                     *c2 = PL_fold_latin1[*c1];
3342                     break;
3343
3344                 default: Perl_croak(aTHX_ "panic: Unexpected op %u", OP(text_node));
3345             }
3346         }
3347     }
3348     else { /* UTF_PATTERN */
3349         if (OP(text_node) == EXACT) {
3350             *c2 = *c1 = utf8n_to_uvchr(pat_byte, UTF8_MAXBYTES, 0, uniflags);
3351             if (*c1 < 0) {  /* Overflowed what we can handle */
3352                 *c1 = *c2 = CHRTEST_VOID;
3353             }
3354             else if (*c1 > 255 && ! utf8_target) {
3355                 return FALSE; /* Can't possibly match */
3356             }
3357         }
3358         else {
3359             if (UTF8_IS_ABOVE_LATIN1(*pat_byte)) {
3360
3361                 /* A multi-character fold is complicated, probably has more
3362                  * than two possibilities */
3363                 if (is_MULTI_CHAR_FOLD_utf8_safe((char*) pat_byte,
3364                                         (char*) pat_byte + STR_LEN(text_node)))
3365                 {
3366                     *c1 = *c2 = CHRTEST_VOID;
3367                 }
3368                 else {  /* Not a multi-char fold */
3369
3370                     /* Load the folds hash, if not already done */
3371                     SV** listp;
3372                     if (! PL_utf8_foldclosures) {
3373                         if (! PL_utf8_tofold) {
3374                             U8 dummy[UTF8_MAXBYTES+1];
3375                             STRLEN dummy_len;
3376
3377                             /* Force loading this by folding an above-Latin1
3378                              * char */
3379                             to_utf8_fold((U8*) HYPHEN_UTF8, dummy, &dummy_len);
3380                             assert(PL_utf8_tofold); /* Verify that worked */
3381                         }
3382                         PL_utf8_foldclosures =
3383                                          _swash_inversion_hash(PL_utf8_tofold);
3384                     }
3385
3386                     /* The fold closures data structure is a hash with the keys
3387                     * being every character that is folded to, like 'k', and
3388                     * the values each an array of everything that folds to its
3389                     * key.  e.g. [ 'k', 'K', KELVIN_SIGN ] */
3390                     if ((! (listp = hv_fetch(PL_utf8_foldclosures,
3391                                              (char *) pat_byte,
3392                                              UTF8SKIP(pat_byte),
3393                                              FALSE))))
3394                     {
3395                         /* Not found in the hash, therefore there are no folds
3396                          * containing it, so there is only a single char
3397                          * possible for beginning B */
3398                         *c2 = *c1 = utf8n_to_uvchr(pat_byte, STR_LEN(text_node),
3399                                                                   0, uniflags);
3400                         if (*c1 < 0) {  /* Overflowed what we can handle */
3401                             *c1 = *c2 = CHRTEST_VOID;
3402                         }
3403                     }
3404                     else {
3405                         AV* list = (AV*) *listp;
3406                         if (av_len(list) != 1) {    /* If there aren't exactly
3407                                                        two folds to this, have
3408                                                        to test B completely */
3409                             *c1 = *c2 = CHRTEST_VOID;
3410                         }
3411                         else {  /* There are two.  Set *c1 and *c2 to them */
3412                             SV** c_p = av_fetch(list, 0, FALSE);
3413                             if (c_p == NULL) {
3414                                 Perl_croak(aTHX_ "panic: invalid PL_utf8_foldclosures structure");
3415                             }
3416                             *c1 = SvUV(*c_p);
3417                             c_p = av_fetch(list, 1, FALSE);
3418                             if (c_p == NULL) {
3419                                 Perl_croak(aTHX_ "panic: invalid PL_utf8_foldclosures structure");
3420                             }
3421                             *c2 = SvUV(*c_p);
3422                         }
3423                     }
3424                 }
3425             }
3426             else {
3427                 /* Get the character represented by the UTF-8-encoded byte */
3428                 U8 c = (UTF8_IS_INVARIANT(*pat_byte))
3429                         ? *pat_byte
3430                         : TWO_BYTE_UTF8_TO_UNI(*pat_byte, *(pat_byte+1));
3431
3432                 if (HAS_NONLATIN1_FOLD_CLOSURE(c)
3433                     && (OP(text_node) != EXACTFA || ! isASCII(c)))
3434                 {   /* Something above Latin1 folds to this; hence there are
3435                        more than 2 possibilities for B to begin with */
3436                     *c1 = *c2 = CHRTEST_VOID;
3437                 }
3438                 else {
3439                     *c1 = c;
3440                     *c2 = (OP(text_node) == EXACTFL)
3441                            ? PL_fold_locale[*c1]
3442                            : PL_fold_latin1[*c1];
3443                 }
3444             }
3445         }
3446     }
3447
3448     return TRUE;
3449 }
3450
3451 /* returns -1 on failure, $+[0] on success */
3452 STATIC I32
3453 S_regmatch(pTHX_ regmatch_info *reginfo, char *startpos, regnode *prog)
3454 {
3455 #if PERL_VERSION < 9 && !defined(PERL_CORE)
3456     dMY_CXT;
3457 #endif
3458     dVAR;
3459     const bool utf8_target = PL_reg_match_utf8;
3460     const U32 uniflags = UTF8_ALLOW_DEFAULT;
3461     REGEXP *rex_sv = reginfo->prog;
3462     regexp *rex = (struct regexp *)SvANY(rex_sv);
3463     RXi_GET_DECL(rex,rexi);
3464     I32 oldsave;
3465     /* the current state. This is a cached copy of PL_regmatch_state */
3466     regmatch_state *st;
3467     /* cache heavy used fields of st in registers */
3468     regnode *scan;
3469     regnode *next;
3470     U32 n = 0;  /* general value; init to avoid compiler warning */
3471     I32 ln = 0; /* len or last;  init to avoid compiler warning */
3472     char *locinput = startpos;
3473     char *pushinput; /* where to continue after a PUSH */
3474     I32 nextchr;   /* is always set to UCHARAT(locinput) */
3475
3476     bool result = 0;        /* return value of S_regmatch */
3477     int depth = 0;          /* depth of backtrack stack */
3478     U32 nochange_depth = 0; /* depth of GOSUB recursion with nochange */
3479     const U32 max_nochange_depth =
3480         (3 * rex->nparens > MAX_RECURSE_EVAL_NOCHANGE_DEPTH) ?
3481         3 * rex->nparens : MAX_RECURSE_EVAL_NOCHANGE_DEPTH;
3482     regmatch_state *yes_state = NULL; /* state to pop to on success of
3483                                                             subpattern */
3484     /* mark_state piggy backs on the yes_state logic so that when we unwind
3485        the stack on success we can update the mark_state as we go */
3486     regmatch_state *mark_state = NULL; /* last mark state we have seen */
3487     regmatch_state *cur_eval = NULL; /* most recent EVAL_AB state */
3488     struct regmatch_state  *cur_curlyx = NULL; /* most recent curlyx */
3489     U32 state_num;
3490     bool no_final = 0;      /* prevent failure from backtracking? */
3491     bool do_cutgroup = 0;   /* no_final only until next branch/trie entry */
3492     char *startpoint = locinput;
3493     SV *popmark = NULL;     /* are we looking for a mark? */
3494     SV *sv_commit = NULL;   /* last mark name seen in failure */
3495     SV *sv_yes_mark = NULL; /* last mark name we have seen
3496                                during a successful match */
3497     U32 lastopen = 0;       /* last open we saw */
3498     bool has_cutgroup = RX_HAS_CUTGROUP(rex) ? 1 : 0;
3499     SV* const oreplsv = GvSV(PL_replgv);
3500     /* these three flags are set by various ops to signal information to
3501      * the very next op. They have a useful lifetime of exactly one loop
3502      * iteration, and are not preserved or restored by state pushes/pops
3503      */
3504     bool sw = 0;            /* the condition value in (?(cond)a|b) */
3505     bool minmod = 0;        /* the next "{n,m}" is a "{n,m}?" */
3506     int logical = 0;        /* the following EVAL is:
3507                                 0: (?{...})
3508                                 1: (?(?{...})X|Y)
3509                                 2: (??{...})
3510                                or the following IFMATCH/UNLESSM is:
3511                                 false: plain (?=foo)
3512                                 true:  used as a condition: (?(?=foo))
3513                             */
3514     PAD* last_pad = NULL;
3515     dMULTICALL;
3516     I32 gimme = G_SCALAR;
3517     CV *caller_cv = NULL;       /* who called us */
3518     CV *last_pushed_cv = NULL;  /* most recently called (?{}) CV */
3519     CHECKPOINT runops_cp;       /* savestack position before executing EVAL */
3520
3521 #ifdef DEBUGGING
3522     GET_RE_DEBUG_FLAGS_DECL;
3523 #endif
3524
3525     /* shut up 'may be used uninitialized' compiler warnings for dMULTICALL */
3526     multicall_oldcatch = 0;
3527     multicall_cv = NULL;
3528     cx = NULL;
3529     PERL_UNUSED_VAR(multicall_cop);
3530     PERL_UNUSED_VAR(newsp);
3531
3532
3533     PERL_ARGS_ASSERT_REGMATCH;
3534
3535     DEBUG_OPTIMISE_r( DEBUG_EXECUTE_r({
3536             PerlIO_printf(Perl_debug_log,"regmatch start\n");
3537     }));
3538     /* on first ever call to regmatch, allocate first slab */
3539     if (!PL_regmatch_slab) {
3540         Newx(PL_regmatch_slab, 1, regmatch_slab);
3541         PL_regmatch_slab->prev = NULL;
3542         PL_regmatch_slab->next = NULL;
3543         PL_regmatch_state = SLAB_FIRST(PL_regmatch_slab);
3544     }
3545
3546     oldsave = PL_savestack_ix;
3547     SAVEDESTRUCTOR_X(S_clear_backtrack_stack, NULL);
3548     SAVEVPTR(PL_regmatch_slab);
3549     SAVEVPTR(PL_regmatch_state);
3550
3551     /* grab next free state slot */
3552     st = ++PL_regmatch_state;
3553     if (st >  SLAB_LAST(PL_regmatch_slab))
3554         st = PL_regmatch_state = S_push_slab(aTHX);
3555
3556     /* Note that nextchr is a byte even in UTF */
3557     SET_nextchr;
3558     scan = prog;
3559     while (scan != NULL) {
3560
3561         DEBUG_EXECUTE_r( {
3562             SV * const prop = sv_newmortal();
3563             regnode *rnext=regnext(scan);
3564             DUMP_EXEC_POS( locinput, scan, utf8_target );
3565             regprop(rex, prop, scan);
3566
3567             PerlIO_printf(Perl_debug_log,
3568                     "%3"IVdf":%*s%s(%"IVdf")\n",
3569                     (IV)(scan - rexi->program), depth*2, "",
3570                     SvPVX_const(prop),
3571                     (PL_regkind[OP(scan)] == END || !rnext) ?
3572                         0 : (IV)(rnext - rexi->program));
3573         });
3574
3575         next = scan + NEXT_OFF(scan);
3576         if (next == scan)
3577             next = NULL;
3578         state_num = OP(scan);
3579
3580       reenter_switch:
3581
3582         SET_nextchr;
3583
3584         switch (state_num) {
3585         case BOL: /*  /^../  */
3586             if (locinput == PL_bostr)
3587             {
3588                 /* reginfo->till = reginfo->bol; */
3589                 break;
3590             }
3591             sayNO;
3592
3593         case MBOL: /*  /^../m  */
3594             if (locinput == PL_bostr ||
3595                 (!NEXTCHR_IS_EOS && locinput[-1] == '\n'))
3596             {
3597                 break;
3598             }
3599             sayNO;
3600
3601         case SBOL: /*  /^../s  */
3602             if (locinput == PL_bostr)
3603                 break;
3604             sayNO;
3605
3606         case GPOS: /*  \G  */
3607             if (locinput == reginfo->ganch)
3608                 break;
3609             sayNO;
3610
3611         case KEEPS: /*   \K  */
3612             /* update the startpoint */
3613             st->u.keeper.val = rex->offs[0].start;
3614             rex->offs[0].start = locinput - PL_bostr;
3615             PUSH_STATE_GOTO(KEEPS_next, next, locinput);
3616             /*NOT-REACHED*/
3617         case KEEPS_next_fail:
3618             /* rollback the start point change */
3619             rex->offs[0].start = st->u.keeper.val;
3620             sayNO_SILENT;
3621             /*NOT-REACHED*/
3622
3623         case EOL: /* /..$/  */
3624                 goto seol;
3625
3626         case MEOL: /* /..$/m  */
3627             if (!NEXTCHR_IS_EOS && nextchr != '\n')
3628                 sayNO;
3629             break;
3630
3631         case SEOL: /* /..$/s  */
3632           seol:
3633             if (!NEXTCHR_IS_EOS && nextchr != '\n')
3634                 sayNO;
3635             if (PL_regeol - locinput > 1)
3636                 sayNO;
3637             break;
3638
3639         case EOS: /*  \z  */
3640             if (!NEXTCHR_IS_EOS)
3641                 sayNO;
3642             break;
3643
3644         case SANY: /*  /./s  */
3645             if (NEXTCHR_IS_EOS)
3646                 sayNO;
3647             goto increment_locinput;
3648
3649         case CANY: /*  \C  */
3650             if (NEXTCHR_IS_EOS)
3651                 sayNO;
3652             locinput++;
3653             break;
3654
3655         case REG_ANY: /*  /./  */
3656             if ((NEXTCHR_IS_EOS) || nextchr == '\n')
3657                 sayNO;
3658             goto increment_locinput;
3659
3660
3661 #undef  ST
3662 #define ST st->u.trie
3663         case TRIEC: /* (ab|cd) with known charclass */
3664             /* In this case the charclass data is available inline so
3665                we can fail fast without a lot of extra overhead.
3666              */
3667             if(!NEXTCHR_IS_EOS && !ANYOF_BITMAP_TEST(scan, nextchr)) {
3668                 DEBUG_EXECUTE_r(
3669                     PerlIO_printf(Perl_debug_log,
3670                               "%*s  %sfailed to match trie start class...%s\n",
3671                               REPORT_CODE_OFF+depth*2, "", PL_colors[4], PL_colors[5])
3672                 );
3673                 sayNO_SILENT;
3674                 assert(0); /* NOTREACHED */
3675             }
3676             /* FALL THROUGH */
3677         case TRIE:  /* (ab|cd)  */
3678             /* the basic plan of execution of the trie is:
3679              * At the beginning, run though all the states, and
3680              * find the longest-matching word. Also remember the position
3681              * of the shortest matching word. For example, this pattern:
3682              *    1  2 3 4    5
3683              *    ab|a|x|abcd|abc
3684              * when matched against the string "abcde", will generate
3685              * accept states for all words except 3, with the longest
3686              * matching word being 4, and the shortest being 2 (with
3687              * the position being after char 1 of the string).
3688              *
3689              * Then for each matching word, in word order (i.e. 1,2,4,5),
3690              * we run the remainder of the pattern; on each try setting
3691              * the current position to the character following the word,
3692              * returning to try the next word on failure.
3693              *
3694              * We avoid having to build a list of words at runtime by
3695              * using a compile-time structure, wordinfo[].prev, which
3696              * gives, for each word, the previous accepting word (if any).
3697              * In the case above it would contain the mappings 1->2, 2->0,
3698              * 3->0, 4->5, 5->1.  We can use this table to generate, from
3699              * the longest word (4 above), a list of all words, by
3700              * following the list of prev pointers; this gives us the
3701              * unordered list 4,5,1,2. Then given the current word we have
3702              * just tried, we can go through the list and find the
3703              * next-biggest word to try (so if we just failed on word 2,
3704              * the next in the list is 4).
3705              *
3706              * Since at runtime we don't record the matching position in
3707              * the string for each word, we have to work that out for
3708              * each word we're about to process. The wordinfo table holds
3709              * the character length of each word; given that we recorded
3710              * at the start: the position of the shortest word and its
3711              * length in chars, we just need to move the pointer the
3712              * difference between the two char lengths. Depending on
3713              * Unicode status and folding, that's cheap or expensive.
3714              *
3715              * This algorithm is optimised for the case where are only a
3716              * small number of accept states, i.e. 0,1, or maybe 2.
3717              * With lots of accepts states, and having to try all of them,
3718              * it becomes quadratic on number of accept states to find all
3719              * the next words.
3720              */
3721
3722             {
3723                 /* what type of TRIE am I? (utf8 makes this contextual) */
3724                 DECL_TRIE_TYPE(scan);
3725
3726                 /* what trie are we using right now */
3727                 reg_trie_data * const trie
3728                     = (reg_trie_data*)rexi->data->data[ ARG( scan ) ];
3729                 HV * widecharmap = MUTABLE_HV(rexi->data->data[ ARG( scan ) + 1 ]);
3730                 U32 state = trie->startstate;
3731
3732                 if (   trie->bitmap
3733                     && (NEXTCHR_IS_EOS || !TRIE_BITMAP_TEST(trie, nextchr)))
3734                 {
3735                     if (trie->states[ state ].wordnum) {
3736                          DEBUG_EXECUTE_r(
3737                             PerlIO_printf(Perl_debug_log,
3738                                           "%*s  %smatched empty string...%s\n",
3739                                           REPORT_CODE_OFF+depth*2, "", PL_colors[4], PL_colors[5])
3740                         );
3741                         if (!trie->jump)
3742                             break;
3743                     } else {
3744                         DEBUG_EXECUTE_r(
3745                             PerlIO_printf(Perl_debug_log,
3746                                           "%*s  %sfailed to match trie start class...%s\n",
3747                                           REPORT_CODE_OFF+depth*2, "", PL_colors[4], PL_colors[5])
3748                         );
3749                         sayNO_SILENT;
3750                    }
3751                 }
3752
3753             {
3754                 U8 *uc = ( U8* )locinput;
3755
3756                 STRLEN len = 0;
3757                 STRLEN foldlen = 0;
3758                 U8 *uscan = (U8*)NULL;
3759                 U8 foldbuf[ UTF8_MAXBYTES_CASE + 1 ];
3760                 U32 charcount = 0; /* how many input chars we have matched */
3761                 U32 accepted = 0; /* have we seen any accepting states? */
3762
3763                 ST.jump = trie->jump;
3764                 ST.me = scan;
3765                 ST.firstpos = NULL;
3766                 ST.longfold = FALSE; /* char longer if folded => it's harder */
3767                 ST.nextword = 0;
3768
3769                 /* fully traverse the TRIE; note the position of the
3770                    shortest accept state and the wordnum of the longest
3771                    accept state */
3772
3773                 while ( state && uc <= (U8*)PL_regeol ) {
3774                     U32 base = trie->states[ state ].trans.base;
3775                     UV uvc = 0;
3776                     U16 charid = 0;
3777                     U16 wordnum;
3778                     wordnum = trie->states[ state ].wordnum;
3779
3780                     if (wordnum) { /* it's an accept state */
3781                         if (!accepted) {
3782                             accepted = 1;
3783                             /* record first match position */
3784                             if (ST.longfold) {
3785                                 ST.firstpos = (U8*)locinput;
3786                                 ST.firstchars = 0;
3787                             }
3788                             else {
3789                                 ST.firstpos = uc;
3790                                 ST.firstchars = charcount;
3791                             }
3792                         }
3793                         if (!ST.nextword || wordnum < ST.nextword)
3794                             ST.nextword = wordnum;
3795                         ST.topword = wordnum;
3796                     }
3797
3798                     DEBUG_TRIE_EXECUTE_r({
3799                                 DUMP_EXEC_POS( (char *)uc, scan, utf8_target );
3800                                 PerlIO_printf( Perl_debug_log,
3801                                     "%*s  %sState: %4"UVxf" Accepted: %c ",
3802                                     2+depth * 2, "", PL_colors[4],
3803                                     (UV)state, (accepted ? 'Y' : 'N'));
3804                     });
3805
3806                     /* read a char and goto next state */
3807                     if ( base && (foldlen || uc < (U8*)PL_regeol)) {
3808                         I32 offset;
3809                         REXEC_TRIE_READ_CHAR(trie_type, trie, widecharmap, uc,
3810                                              uscan, len, uvc, charid, foldlen,
3811                                              foldbuf, uniflags);
3812                         charcount++;
3813                         if (foldlen>0)
3814                             ST.longfold = TRUE;
3815                         if (charid &&
3816                              ( ((offset =
3817                               base + charid - 1 - trie->uniquecharcount)) >= 0)
3818
3819                              && ((U32)offset < trie->lasttrans)
3820                              && trie->trans[offset].check == state)
3821                         {
3822                             state = trie->trans[offset].next;
3823                         }
3824                         else {
3825                             state = 0;
3826                         }
3827                         uc += len;
3828
3829                     }
3830                     else {
3831                         state = 0;
3832                     }
3833                     DEBUG_TRIE_EXECUTE_r(
3834                         PerlIO_printf( Perl_debug_log,
3835                             "Charid:%3x CP:%4"UVxf" After State: %4"UVxf"%s\n",
3836                             charid, uvc, (UV)state, PL_colors[5] );
3837                     );
3838                 }
3839                 if (!accepted)
3840                    sayNO;
3841
3842                 /* calculate total number of accept states */
3843                 {
3844                     U16 w = ST.topword;
3845                     accepted = 0;
3846                     while (w) {
3847                         w = trie->wordinfo[w].prev;
3848                         accepted++;
3849