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