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