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