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