This is a live mirror of the Perl 5 development currently hosted at https://github.com/perl/perl5
40f33d493a2621cda3d709f0cca3b92136b714b6
[perl5.git] / regexec.c
1 /*    regexec.c
2  */
3
4 /*
5  * "One Ring to rule them all, One Ring to find them..."
6  */
7
8 /* NOTE: this is derived from Henry Spencer's regexp code, and should not
9  * confused with the original package (see point 3 below).  Thanks, Henry!
10  */
11
12 /* Additional note: this code is very heavily munged from Henry's version
13  * in places.  In some spots I've traded clarity for efficiency, so don't
14  * blame Henry for some of the lack of readability.
15  */
16
17 /* The names of the functions have been changed from regcomp and
18  * regexec to  pregcomp and pregexec in order to avoid conflicts
19  * with the POSIX routines of the same names.
20 */
21
22 #ifdef PERL_EXT_RE_BUILD
23 /* need to replace pregcomp et al, so enable that */
24 #  ifndef PERL_IN_XSUB_RE
25 #    define PERL_IN_XSUB_RE
26 #  endif
27 /* need access to debugger hooks */
28 #  if defined(PERL_EXT_RE_DEBUG) && !defined(DEBUGGING)
29 #    define DEBUGGING
30 #  endif
31 #endif
32
33 #ifdef PERL_IN_XSUB_RE
34 /* We *really* need to overwrite these symbols: */
35 #  define Perl_regexec_flags my_regexec
36 #  define Perl_regdump my_regdump
37 #  define Perl_regprop my_regprop
38 #  define Perl_re_intuit_start my_re_intuit_start
39 /* *These* symbols are masked to allow static link. */
40 #  define Perl_pregexec my_pregexec
41 #  define Perl_reginitcolors my_reginitcolors
42 #  define Perl_regclass_swash my_regclass_swash
43
44 #  define PERL_NO_GET_CONTEXT
45 #endif
46
47 /*SUPPRESS 112*/
48 /*
49  * pregcomp and pregexec -- regsub and regerror are not used in perl
50  *
51  *      Copyright (c) 1986 by University of Toronto.
52  *      Written by Henry Spencer.  Not derived from licensed software.
53  *
54  *      Permission is granted to anyone to use this software for any
55  *      purpose on any computer system, and to redistribute it freely,
56  *      subject to the following restrictions:
57  *
58  *      1. The author is not responsible for the consequences of use of
59  *              this software, no matter how awful, even if they arise
60  *              from defects in it.
61  *
62  *      2. The origin of this software must not be misrepresented, either
63  *              by explicit claim or by omission.
64  *
65  *      3. Altered versions must be plainly marked as such, and must not
66  *              be misrepresented as being the original software.
67  *
68  ****    Alterations to Henry's code are...
69  ****
70  ****    Copyright (c) 1991-2002, Larry Wall
71  ****
72  ****    You may distribute under the terms of either the GNU General Public
73  ****    License or the Artistic License, as specified in the README file.
74  *
75  * Beware that some of this code is subtly aware of the way operator
76  * precedence is structured in regular expressions.  Serious changes in
77  * regular-expression syntax might require a total rethink.
78  */
79 #include "EXTERN.h"
80 #define PERL_IN_REGEXEC_C
81 #include "perl.h"
82
83 #include "regcomp.h"
84
85 #define RF_tainted      1               /* tainted information used? */
86 #define RF_warned       2               /* warned about big count? */
87 #define RF_evaled       4               /* Did an EVAL with setting? */
88 #define RF_utf8         8               /* String contains multibyte chars? */
89
90 #define UTF ((PL_reg_flags & RF_utf8) != 0)
91
92 #define RS_init         1               /* eval environment created */
93 #define RS_set          2               /* replsv value is set */
94
95 #ifndef STATIC
96 #define STATIC  static
97 #endif
98
99 #define REGINCLASS(p,c)  (ANYOF_FLAGS(p) ? reginclass(p,c,0,0) : ANYOF_BITMAP_TEST(p,*(c)))
100
101 /*
102  * Forwards.
103  */
104
105 #define CHR_SVLEN(sv) (do_utf8 ? sv_len_utf8(sv) : SvCUR(sv))
106 #define CHR_DIST(a,b) (PL_reg_match_utf8 ? utf8_distance(a,b) : a - b)
107
108 #define reghop_c(pos,off) ((char*)reghop((U8*)pos, off))
109 #define reghopmaybe_c(pos,off) ((char*)reghopmaybe((U8*)pos, off))
110 #define HOP(pos,off) (PL_reg_match_utf8 ? reghop((U8*)pos, off) : (U8*)(pos + off))
111 #define HOPMAYBE(pos,off) (PL_reg_match_utf8 ? reghopmaybe((U8*)pos, off) : (U8*)(pos + off))
112 #define HOPc(pos,off) ((char*)HOP(pos,off))
113 #define HOPMAYBEc(pos,off) ((char*)HOPMAYBE(pos,off))
114
115 #define HOPBACK(pos, off) (             \
116     (PL_reg_match_utf8)                 \
117         ? reghopmaybe((U8*)pos, -off)   \
118     : (pos - off >= PL_bostr)           \
119         ? (U8*)(pos - off)              \
120     : (U8*)NULL                         \
121 )
122 #define HOPBACKc(pos, off) (char*)HOPBACK(pos, off)
123
124 #define reghop3_c(pos,off,lim) ((char*)reghop3((U8*)pos, off, (U8*)lim))
125 #define reghopmaybe3_c(pos,off,lim) ((char*)reghopmaybe3((U8*)pos, off, (U8*)lim))
126 #define HOP3(pos,off,lim) (PL_reg_match_utf8 ? reghop3((U8*)pos, off, (U8*)lim) : (U8*)(pos + off))
127 #define HOPMAYBE3(pos,off,lim) (PL_reg_match_utf8 ? reghopmaybe3((U8*)pos, off, (U8*)lim) : (U8*)(pos + off))
128 #define HOP3c(pos,off,lim) ((char*)HOP3(pos,off,lim))
129 #define HOPMAYBE3c(pos,off,lim) ((char*)HOPMAYBE3(pos,off,lim))
130
131 #define LOAD_UTF8_CHARCLASS(a,b) STMT_START { if (!CAT2(PL_utf8_,a)) { ENTER; save_re_context(); (void)CAT2(is_utf8_, a)((U8*)b); LEAVE; } } STMT_END
132
133 /* for use after a quantifier and before an EXACT-like node -- japhy */
134 #define JUMPABLE(rn) ( \
135     OP(rn) == OPEN || OP(rn) == CLOSE || OP(rn) == EVAL || \
136     OP(rn) == SUSPEND || OP(rn) == IFMATCH || \
137     OP(rn) == PLUS || OP(rn) == MINMOD || \
138     (PL_regkind[(U8)OP(rn)] == CURLY && ARG1(rn) > 0) \
139 )
140
141 #define HAS_TEXT(rn) ( \
142     PL_regkind[(U8)OP(rn)] == EXACT || PL_regkind[(U8)OP(rn)] == REF \
143 )
144
145 /*
146   Search for mandatory following text node; for lookahead, the text must
147   follow but for lookbehind (rn->flags != 0) we skip to the next step.
148 */
149 #define FIND_NEXT_IMPT(rn) STMT_START { \
150     while (JUMPABLE(rn)) \
151         if (OP(rn) == SUSPEND || PL_regkind[(U8)OP(rn)] == CURLY) \
152             rn = NEXTOPER(NEXTOPER(rn)); \
153         else if (OP(rn) == PLUS) \
154             rn = NEXTOPER(rn); \
155         else if (OP(rn) == IFMATCH) \
156             rn = (rn->flags == 0) ? NEXTOPER(NEXTOPER(rn)) : rn + ARG(rn); \
157         else rn += NEXT_OFF(rn); \
158 } STMT_END 
159
160 static void restore_pos(pTHX_ void *arg);
161
162 STATIC CHECKPOINT
163 S_regcppush(pTHX_ I32 parenfloor)
164 {
165     int retval = PL_savestack_ix;
166 #define REGCP_PAREN_ELEMS 4
167     int paren_elems_to_push = (PL_regsize - parenfloor) * REGCP_PAREN_ELEMS;
168     int p;
169
170     if (paren_elems_to_push < 0)
171         Perl_croak(aTHX_ "panic: paren_elems_to_push < 0");
172
173 #define REGCP_OTHER_ELEMS 6
174     SSCHECK(paren_elems_to_push + REGCP_OTHER_ELEMS);
175     for (p = PL_regsize; p > parenfloor; p--) {
176 /* REGCP_PARENS_ELEMS are pushed per pairs of parentheses. */
177         SSPUSHINT(PL_regendp[p]);
178         SSPUSHINT(PL_regstartp[p]);
179         SSPUSHPTR(PL_reg_start_tmp[p]);
180         SSPUSHINT(p);
181     }
182 /* REGCP_OTHER_ELEMS are pushed in any case, parentheses or no. */
183     SSPUSHINT(PL_regsize);
184     SSPUSHINT(*PL_reglastparen);
185     SSPUSHINT(*PL_reglastcloseparen);
186     SSPUSHPTR(PL_reginput);
187 #define REGCP_FRAME_ELEMS 2
188 /* REGCP_FRAME_ELEMS are part of the REGCP_OTHER_ELEMS and
189  * are needed for the regexp context stack bookkeeping. */
190     SSPUSHINT(paren_elems_to_push + REGCP_OTHER_ELEMS - REGCP_FRAME_ELEMS);
191     SSPUSHINT(SAVEt_REGCONTEXT); /* Magic cookie. */
192
193     return retval;
194 }
195
196 /* These are needed since we do not localize EVAL nodes: */
197 #  define REGCP_SET(cp)  DEBUG_r(PerlIO_printf(Perl_debug_log,          \
198                              "  Setting an EVAL scope, savestack=%"IVdf"\n",    \
199                              (IV)PL_savestack_ix)); cp = PL_savestack_ix
200
201 #  define REGCP_UNWIND(cp)  DEBUG_r(cp != PL_savestack_ix ?             \
202                                 PerlIO_printf(Perl_debug_log,           \
203                                 "  Clearing an EVAL scope, savestack=%"IVdf"..%"IVdf"\n", \
204                                 (IV)(cp), (IV)PL_savestack_ix) : 0); regcpblow(cp)
205
206 STATIC char *
207 S_regcppop(pTHX)
208 {
209     I32 i;
210     U32 paren = 0;
211     char *input;
212     I32 tmps;
213
214     /* Pop REGCP_OTHER_ELEMS before the parentheses loop starts. */
215     i = SSPOPINT;
216     assert(i == SAVEt_REGCONTEXT); /* Check that the magic cookie is there. */
217     i = SSPOPINT; /* Parentheses elements to pop. */
218     input = (char *) SSPOPPTR;
219     *PL_reglastcloseparen = SSPOPINT;
220     *PL_reglastparen = SSPOPINT;
221     PL_regsize = SSPOPINT;
222
223     /* Now restore the parentheses context. */
224     for (i -= (REGCP_OTHER_ELEMS - REGCP_FRAME_ELEMS);
225          i > 0; i -= REGCP_PAREN_ELEMS) {
226         paren = (U32)SSPOPINT;
227         PL_reg_start_tmp[paren] = (char *) SSPOPPTR;
228         PL_regstartp[paren] = SSPOPINT;
229         tmps = SSPOPINT;
230         if (paren <= *PL_reglastparen)
231             PL_regendp[paren] = tmps;
232         DEBUG_r(
233             PerlIO_printf(Perl_debug_log,
234                           "     restoring \\%"UVuf" to %"IVdf"(%"IVdf")..%"IVdf"%s\n",
235                           (UV)paren, (IV)PL_regstartp[paren],
236                           (IV)(PL_reg_start_tmp[paren] - PL_bostr),
237                           (IV)PL_regendp[paren],
238                           (paren > *PL_reglastparen ? "(no)" : ""));
239         );
240     }
241     DEBUG_r(
242         if ((I32)(*PL_reglastparen + 1) <= PL_regnpar) {
243             PerlIO_printf(Perl_debug_log,
244                           "     restoring \\%"IVdf"..\\%"IVdf" to undef\n",
245                           (IV)(*PL_reglastparen + 1), (IV)PL_regnpar);
246         }
247     );
248 #if 1
249     /* It would seem that the similar code in regtry()
250      * already takes care of this, and in fact it is in
251      * a better location to since this code can #if 0-ed out
252      * but the code in regtry() is needed or otherwise tests
253      * requiring null fields (pat.t#187 and split.t#{13,14}
254      * (as of patchlevel 7877)  will fail.  Then again,
255      * this code seems to be necessary or otherwise
256      * building DynaLoader will fail:
257      * "Error: '*' not in typemap in DynaLoader.xs, line 164"
258      * --jhi */
259     for (paren = *PL_reglastparen + 1; (I32)paren <= PL_regnpar; paren++) {
260         if ((I32)paren > PL_regsize)
261             PL_regstartp[paren] = -1;
262         PL_regendp[paren] = -1;
263     }
264 #endif
265     return input;
266 }
267
268 STATIC char *
269 S_regcp_set_to(pTHX_ I32 ss)
270 {
271     I32 tmp = PL_savestack_ix;
272
273     PL_savestack_ix = ss;
274     regcppop();
275     PL_savestack_ix = tmp;
276     return Nullch;
277 }
278
279 typedef struct re_cc_state
280 {
281     I32 ss;
282     regnode *node;
283     struct re_cc_state *prev;
284     CURCUR *cc;
285     regexp *re;
286 } re_cc_state;
287
288 #define regcpblow(cp) LEAVE_SCOPE(cp)   /* Ignores regcppush()ed data. */
289
290 #define TRYPAREN(paren, n, input) {                             \
291     if (paren) {                                                \
292         if (n) {                                                \
293             PL_regstartp[paren] = HOPc(input, -1) - PL_bostr;   \
294             PL_regendp[paren] = input - PL_bostr;               \
295         }                                                       \
296         else                                                    \
297             PL_regendp[paren] = -1;                             \
298     }                                                           \
299     if (regmatch(next))                                         \
300         sayYES;                                                 \
301     if (paren && n)                                             \
302         PL_regendp[paren] = -1;                                 \
303 }
304
305
306 /*
307  * pregexec and friends
308  */
309
310 /*
311  - pregexec - match a regexp against a string
312  */
313 I32
314 Perl_pregexec(pTHX_ register regexp *prog, char *stringarg, register char *strend,
315          char *strbeg, I32 minend, SV *screamer, U32 nosave)
316 /* strend: pointer to null at end of string */
317 /* strbeg: real beginning of string */
318 /* minend: end of match must be >=minend after stringarg. */
319 /* nosave: For optimizations. */
320 {
321     return
322         regexec_flags(prog, stringarg, strend, strbeg, minend, screamer, NULL,
323                       nosave ? 0 : REXEC_COPY_STR);
324 }
325
326 STATIC void
327 S_cache_re(pTHX_ regexp *prog)
328 {
329     PL_regprecomp = prog->precomp;              /* Needed for FAIL. */
330 #ifdef DEBUGGING
331     PL_regprogram = prog->program;
332 #endif
333     PL_regnpar = prog->nparens;
334     PL_regdata = prog->data;
335     PL_reg_re = prog;
336 }
337
338 /*
339  * Need to implement the following flags for reg_anch:
340  *
341  * USE_INTUIT_NOML              - Useful to call re_intuit_start() first
342  * USE_INTUIT_ML
343  * INTUIT_AUTORITATIVE_NOML     - Can trust a positive answer
344  * INTUIT_AUTORITATIVE_ML
345  * INTUIT_ONCE_NOML             - Intuit can match in one location only.
346  * INTUIT_ONCE_ML
347  *
348  * Another flag for this function: SECOND_TIME (so that float substrs
349  * with giant delta may be not rechecked).
350  */
351
352 /* Assumptions: if ANCH_GPOS, then strpos is anchored. XXXX Check GPOS logic */
353
354 /* If SCREAM, then SvPVX(sv) should be compatible with strpos and strend.
355    Otherwise, only SvCUR(sv) is used to get strbeg. */
356
357 /* XXXX We assume that strpos is strbeg unless sv. */
358
359 /* XXXX Some places assume that there is a fixed substring.
360         An update may be needed if optimizer marks as "INTUITable"
361         RExen without fixed substrings.  Similarly, it is assumed that
362         lengths of all the strings are no more than minlen, thus they
363         cannot come from lookahead.
364         (Or minlen should take into account lookahead.) */
365
366 /* A failure to find a constant substring means that there is no need to make
367    an expensive call to REx engine, thus we celebrate a failure.  Similarly,
368    finding a substring too deep into the string means that less calls to
369    regtry() should be needed.
370
371    REx compiler's optimizer found 4 possible hints:
372         a) Anchored substring;
373         b) Fixed substring;
374         c) Whether we are anchored (beginning-of-line or \G);
375         d) First node (of those at offset 0) which may distingush positions;
376    We use a)b)d) and multiline-part of c), and try to find a position in the
377    string which does not contradict any of them.
378  */
379
380 /* Most of decisions we do here should have been done at compile time.
381    The nodes of the REx which we used for the search should have been
382    deleted from the finite automaton. */
383
384 char *
385 Perl_re_intuit_start(pTHX_ regexp *prog, SV *sv, char *strpos,
386                      char *strend, U32 flags, re_scream_pos_data *data)
387 {
388     register I32 start_shift = 0;
389     /* Should be nonnegative! */
390     register I32 end_shift   = 0;
391     register char *s;
392     register SV *check;
393     char *strbeg;
394     char *t;
395     int do_utf8 = sv ? SvUTF8(sv) : 0;  /* if no sv we have to assume bytes */
396     I32 ml_anch;
397     register char *other_last = Nullch; /* other substr checked before this */
398     char *check_at = Nullch;            /* check substr found at this pos */
399 #ifdef DEBUGGING
400     char *i_strpos = strpos;
401     SV *dsv = PERL_DEBUG_PAD_ZERO(0);
402 #endif
403     RX_MATCH_UTF8_set(prog,do_utf8);
404
405     if (prog->reganch & ROPT_UTF8) {
406         DEBUG_r(PerlIO_printf(Perl_debug_log,
407                               "UTF-8 regex...\n"));
408         PL_reg_flags |= RF_utf8;
409     }
410
411     DEBUG_r({
412          char *s   = PL_reg_match_utf8 ?
413                          sv_uni_display(dsv, sv, 60, UNI_DISPLAY_REGEX) :
414                          strpos;
415          int   len = PL_reg_match_utf8 ?
416                          strlen(s) : strend - strpos;
417          if (!PL_colorset)
418               reginitcolors();
419          if (PL_reg_match_utf8)
420              DEBUG_r(PerlIO_printf(Perl_debug_log,
421                                    "UTF-8 target...\n"));
422          PerlIO_printf(Perl_debug_log,
423                        "%sGuessing start of match, REx%s `%s%.60s%s%s' against `%s%.*s%s%s'...\n",
424                        PL_colors[4],PL_colors[5],PL_colors[0],
425                        prog->precomp,
426                        PL_colors[1],
427                        (strlen(prog->precomp) > 60 ? "..." : ""),
428                        PL_colors[0],
429                        (int)(len > 60 ? 60 : len),
430                        s, PL_colors[1],
431                        (len > 60 ? "..." : "")
432               );
433     });
434
435     /* CHR_DIST() would be more correct here but it makes things slow. */
436     if (prog->minlen > strend - strpos) {
437         DEBUG_r(PerlIO_printf(Perl_debug_log,
438                               "String too short... [re_intuit_start]\n"));
439         goto fail;
440     }
441     strbeg = (sv && SvPOK(sv)) ? strend - SvCUR(sv) : strpos;
442     PL_regeol = strend;
443     if (do_utf8) {
444         if (!prog->check_utf8 && prog->check_substr)
445             to_utf8_substr(prog);
446         check = prog->check_utf8;
447     } else {
448         if (!prog->check_substr && prog->check_utf8)
449             to_byte_substr(prog);
450         check = prog->check_substr;
451     }
452    if (check == &PL_sv_undef) {
453         DEBUG_r(PerlIO_printf(Perl_debug_log,
454                 "Non-utf string cannot match utf check string\n"));
455         goto fail;
456     }
457     if (prog->reganch & ROPT_ANCH) {    /* Match at beg-of-str or after \n */
458         ml_anch = !( (prog->reganch & ROPT_ANCH_SINGLE)
459                      || ( (prog->reganch & ROPT_ANCH_BOL)
460                           && !PL_multiline ) ); /* Check after \n? */
461
462         if (!ml_anch) {
463           if ( !(prog->reganch & (ROPT_ANCH_GPOS /* Checked by the caller */
464                                   | ROPT_IMPLICIT)) /* not a real BOL */
465                /* SvCUR is not set on references: SvRV and SvPVX overlap */
466                && sv && !SvROK(sv)
467                && (strpos != strbeg)) {
468               DEBUG_r(PerlIO_printf(Perl_debug_log, "Not at start...\n"));
469               goto fail;
470           }
471           if (prog->check_offset_min == prog->check_offset_max &&
472               !(prog->reganch & ROPT_CANY_SEEN)) {
473             /* Substring at constant offset from beg-of-str... */
474             I32 slen;
475
476             s = HOP3c(strpos, prog->check_offset_min, strend);
477             if (SvTAIL(check)) {
478                 slen = SvCUR(check);    /* >= 1 */
479
480                 if ( strend - s > slen || strend - s < slen - 1
481                      || (strend - s == slen && strend[-1] != '\n')) {
482                     DEBUG_r(PerlIO_printf(Perl_debug_log, "String too long...\n"));
483                     goto fail_finish;
484                 }
485                 /* Now should match s[0..slen-2] */
486                 slen--;
487                 if (slen && (*SvPVX(check) != *s
488                              || (slen > 1
489                                  && memNE(SvPVX(check), s, slen)))) {
490                   report_neq:
491                     DEBUG_r(PerlIO_printf(Perl_debug_log, "String not equal...\n"));
492                     goto fail_finish;
493                 }
494             }
495             else if (*SvPVX(check) != *s
496                      || ((slen = SvCUR(check)) > 1
497                          && memNE(SvPVX(check), s, slen)))
498                 goto report_neq;
499             goto success_at_start;
500           }
501         }
502         /* Match is anchored, but substr is not anchored wrt beg-of-str. */
503         s = strpos;
504         start_shift = prog->check_offset_min; /* okay to underestimate on CC */
505         end_shift = prog->minlen - start_shift -
506             CHR_SVLEN(check) + (SvTAIL(check) != 0);
507         if (!ml_anch) {
508             I32 end = prog->check_offset_max + CHR_SVLEN(check)
509                                          - (SvTAIL(check) != 0);
510             I32 eshift = CHR_DIST((U8*)strend, (U8*)s) - end;
511
512             if (end_shift < eshift)
513                 end_shift = eshift;
514         }
515     }
516     else {                              /* Can match at random position */
517         ml_anch = 0;
518         s = strpos;
519         start_shift = prog->check_offset_min; /* okay to underestimate on CC */
520         /* Should be nonnegative! */
521         end_shift = prog->minlen - start_shift -
522             CHR_SVLEN(check) + (SvTAIL(check) != 0);
523     }
524
525 #ifdef DEBUGGING        /* 7/99: reports of failure (with the older version) */
526     if (end_shift < 0)
527         Perl_croak(aTHX_ "panic: end_shift");
528 #endif
529
530   restart:
531     /* Find a possible match in the region s..strend by looking for
532        the "check" substring in the region corrected by start/end_shift. */
533     if (flags & REXEC_SCREAM) {
534         I32 p = -1;                     /* Internal iterator of scream. */
535         I32 *pp = data ? data->scream_pos : &p;
536
537         if (PL_screamfirst[BmRARE(check)] >= 0
538             || ( BmRARE(check) == '\n'
539                  && (BmPREVIOUS(check) == SvCUR(check) - 1)
540                  && SvTAIL(check) ))
541             s = screaminstr(sv, check,
542                             start_shift + (s - strbeg), end_shift, pp, 0);
543         else
544             goto fail_finish;
545         /* we may be pointing at the wrong string */
546         if (s && RX_MATCH_COPIED(prog))
547             s = prog->subbeg + (s - SvPVX(sv));
548         if (data)
549             *data->scream_olds = s;
550     }
551     else if (prog->reganch & ROPT_CANY_SEEN)
552         s = fbm_instr((U8*)(s + start_shift),
553                       (U8*)(strend - end_shift),
554                       check, PL_multiline ? FBMrf_MULTILINE : 0);
555     else
556         s = fbm_instr(HOP3(s, start_shift, strend),
557                       HOP3(strend, -end_shift, strbeg),
558                       check, PL_multiline ? FBMrf_MULTILINE : 0);
559
560     /* Update the count-of-usability, remove useless subpatterns,
561         unshift s.  */
562
563     DEBUG_r(PerlIO_printf(Perl_debug_log, "%s %s substr `%s%.*s%s'%s%s",
564                           (s ? "Found" : "Did not find"),
565                           (check == (do_utf8 ? prog->anchored_utf8 : prog->anchored_substr) ? "anchored" : "floating"),
566                           PL_colors[0],
567                           (int)(SvCUR(check) - (SvTAIL(check)!=0)),
568                           SvPVX(check),
569                           PL_colors[1], (SvTAIL(check) ? "$" : ""),
570                           (s ? " at offset " : "...\n") ) );
571
572     if (!s)
573         goto fail_finish;
574
575     check_at = s;
576
577     /* Finish the diagnostic message */
578     DEBUG_r(PerlIO_printf(Perl_debug_log, "%ld...\n", (long)(s - i_strpos)) );
579
580     /* Got a candidate.  Check MBOL anchoring, and the *other* substr.
581        Start with the other substr.
582        XXXX no SCREAM optimization yet - and a very coarse implementation
583        XXXX /ttx+/ results in anchored=`ttx', floating=`x'.  floating will
584                 *always* match.  Probably should be marked during compile...
585        Probably it is right to do no SCREAM here...
586      */
587
588     if (do_utf8 ? (prog->float_utf8 && prog->anchored_utf8) : (prog->float_substr && prog->anchored_substr)) {
589         /* Take into account the "other" substring. */
590         /* XXXX May be hopelessly wrong for UTF... */
591         if (!other_last)
592             other_last = strpos;
593         if (check == (do_utf8 ? prog->float_utf8 : prog->float_substr)) {
594           do_other_anchored:
595             {
596                 char *last = HOP3c(s, -start_shift, strbeg), *last1, *last2;
597                 char *s1 = s;
598                 SV* must;
599
600                 t = s - prog->check_offset_max;
601                 if (s - strpos > prog->check_offset_max  /* signed-corrected t > strpos */
602                     && (!do_utf8
603                         || ((t = reghopmaybe3_c(s, -(prog->check_offset_max), strpos))
604                             && t > strpos)))
605                     /* EMPTY */;
606                 else
607                     t = strpos;
608                 t = HOP3c(t, prog->anchored_offset, strend);
609                 if (t < other_last)     /* These positions already checked */
610                     t = other_last;
611                 last2 = last1 = HOP3c(strend, -prog->minlen, strbeg);
612                 if (last < last1)
613                     last1 = last;
614  /* XXXX It is not documented what units *_offsets are in.  Assume bytes.  */
615                 /* On end-of-str: see comment below. */
616                 must = do_utf8 ? prog->anchored_utf8 : prog->anchored_substr;
617                 if (must == &PL_sv_undef) {
618                     s = (char*)NULL;
619                     DEBUG_r(must = prog->anchored_utf8);        /* for debug */
620                 }
621                 else
622                     s = fbm_instr(
623                         (unsigned char*)t,
624                         HOP3(HOP3(last1, prog->anchored_offset, strend)
625                                 + SvCUR(must), -(SvTAIL(must)!=0), strbeg),
626                         must,
627                         PL_multiline ? FBMrf_MULTILINE : 0
628                     );
629                 DEBUG_r(PerlIO_printf(Perl_debug_log,
630                         "%s anchored substr `%s%.*s%s'%s",
631                         (s ? "Found" : "Contradicts"),
632                         PL_colors[0],
633                           (int)(SvCUR(must)
634                           - (SvTAIL(must)!=0)),
635                           SvPVX(must),
636                           PL_colors[1], (SvTAIL(must) ? "$" : "")));
637                 if (!s) {
638                     if (last1 >= last2) {
639                         DEBUG_r(PerlIO_printf(Perl_debug_log,
640                                                 ", giving up...\n"));
641                         goto fail_finish;
642                     }
643                     DEBUG_r(PerlIO_printf(Perl_debug_log,
644                         ", trying floating at offset %ld...\n",
645                         (long)(HOP3c(s1, 1, strend) - i_strpos)));
646                     other_last = HOP3c(last1, prog->anchored_offset+1, strend);
647                     s = HOP3c(last, 1, strend);
648                     goto restart;
649                 }
650                 else {
651                     DEBUG_r(PerlIO_printf(Perl_debug_log, " at offset %ld...\n",
652                           (long)(s - i_strpos)));
653                     t = HOP3c(s, -prog->anchored_offset, strbeg);
654                     other_last = HOP3c(s, 1, strend);
655                     s = s1;
656                     if (t == strpos)
657                         goto try_at_start;
658                     goto try_at_offset;
659                 }
660             }
661         }
662         else {          /* Take into account the floating substring. */
663             char *last, *last1;
664             char *s1 = s;
665             SV* must;
666
667             t = HOP3c(s, -start_shift, strbeg);
668             last1 = last =
669                 HOP3c(strend, -prog->minlen + prog->float_min_offset, strbeg);
670             if (CHR_DIST((U8*)last, (U8*)t) > prog->float_max_offset)
671                 last = HOP3c(t, prog->float_max_offset, strend);
672             s = HOP3c(t, prog->float_min_offset, strend);
673             if (s < other_last)
674                 s = other_last;
675  /* XXXX It is not documented what units *_offsets are in.  Assume bytes.  */
676             must = do_utf8 ? prog->float_utf8 : prog->float_substr;
677             /* fbm_instr() takes into account exact value of end-of-str
678                if the check is SvTAIL(ed).  Since false positives are OK,
679                and end-of-str is not later than strend we are OK. */
680             if (must == &PL_sv_undef) {
681                 s = (char*)NULL;
682                 DEBUG_r(must = prog->float_utf8);       /* for debug message */
683             }
684             else
685                 s = fbm_instr((unsigned char*)s,
686                               (unsigned char*)last + SvCUR(must)
687                                   - (SvTAIL(must)!=0),
688                               must, PL_multiline ? FBMrf_MULTILINE : 0);
689             DEBUG_r(PerlIO_printf(Perl_debug_log, "%s floating substr `%s%.*s%s'%s",
690                     (s ? "Found" : "Contradicts"),
691                     PL_colors[0],
692                       (int)(SvCUR(must) - (SvTAIL(must)!=0)),
693                       SvPVX(must),
694                       PL_colors[1], (SvTAIL(must) ? "$" : "")));
695             if (!s) {
696                 if (last1 == last) {
697                     DEBUG_r(PerlIO_printf(Perl_debug_log,
698                                             ", giving up...\n"));
699                     goto fail_finish;
700                 }
701                 DEBUG_r(PerlIO_printf(Perl_debug_log,
702                     ", trying anchored starting at offset %ld...\n",
703                     (long)(s1 + 1 - i_strpos)));
704                 other_last = last;
705                 s = HOP3c(t, 1, strend);
706                 goto restart;
707             }
708             else {
709                 DEBUG_r(PerlIO_printf(Perl_debug_log, " at offset %ld...\n",
710                       (long)(s - i_strpos)));
711                 other_last = s; /* Fix this later. --Hugo */
712                 s = s1;
713                 if (t == strpos)
714                     goto try_at_start;
715                 goto try_at_offset;
716             }
717         }
718     }
719
720     t = s - prog->check_offset_max;
721     if (s - strpos > prog->check_offset_max  /* signed-corrected t > strpos */
722         && (!do_utf8
723             || ((t = reghopmaybe3_c(s, -prog->check_offset_max, strpos))
724                  && t > strpos))) {
725         /* Fixed substring is found far enough so that the match
726            cannot start at strpos. */
727       try_at_offset:
728         if (ml_anch && t[-1] != '\n') {
729             /* Eventually fbm_*() should handle this, but often
730                anchored_offset is not 0, so this check will not be wasted. */
731             /* XXXX In the code below we prefer to look for "^" even in
732                presence of anchored substrings.  And we search even
733                beyond the found float position.  These pessimizations
734                are historical artefacts only.  */
735           find_anchor:
736             while (t < strend - prog->minlen) {
737                 if (*t == '\n') {
738                     if (t < check_at - prog->check_offset_min) {
739                         if (do_utf8 ? prog->anchored_utf8 : prog->anchored_substr) {
740                             /* Since we moved from the found position,
741                                we definitely contradict the found anchored
742                                substr.  Due to the above check we do not
743                                contradict "check" substr.
744                                Thus we can arrive here only if check substr
745                                is float.  Redo checking for "other"=="fixed".
746                              */
747                             strpos = t + 1;                     
748                             DEBUG_r(PerlIO_printf(Perl_debug_log, "Found /%s^%s/m at offset %ld, rescanning for anchored from offset %ld...\n",
749                                 PL_colors[0],PL_colors[1], (long)(strpos - i_strpos), (long)(strpos - i_strpos + prog->anchored_offset)));
750                             goto do_other_anchored;
751                         }
752                         /* We don't contradict the found floating substring. */
753                         /* XXXX Why not check for STCLASS? */
754                         s = t + 1;
755                         DEBUG_r(PerlIO_printf(Perl_debug_log, "Found /%s^%s/m at offset %ld...\n",
756                             PL_colors[0],PL_colors[1], (long)(s - i_strpos)));
757                         goto set_useful;
758                     }
759                     /* Position contradicts check-string */
760                     /* XXXX probably better to look for check-string
761                        than for "\n", so one should lower the limit for t? */
762                     DEBUG_r(PerlIO_printf(Perl_debug_log, "Found /%s^%s/m, restarting lookup for check-string at offset %ld...\n",
763                         PL_colors[0],PL_colors[1], (long)(t + 1 - i_strpos)));
764                     other_last = strpos = s = t + 1;
765                     goto restart;
766                 }
767                 t++;
768             }
769             DEBUG_r(PerlIO_printf(Perl_debug_log, "Did not find /%s^%s/m...\n",
770                         PL_colors[0],PL_colors[1]));
771             goto fail_finish;
772         }
773         else {
774             DEBUG_r(PerlIO_printf(Perl_debug_log, "Starting position does not contradict /%s^%s/m...\n",
775                         PL_colors[0],PL_colors[1]));
776         }
777         s = t;
778       set_useful:
779         ++BmUSEFUL(do_utf8 ? prog->check_utf8 : prog->check_substr);    /* hooray/5 */
780     }
781     else {
782         /* The found string does not prohibit matching at strpos,
783            - no optimization of calling REx engine can be performed,
784            unless it was an MBOL and we are not after MBOL,
785            or a future STCLASS check will fail this. */
786       try_at_start:
787         /* Even in this situation we may use MBOL flag if strpos is offset
788            wrt the start of the string. */
789         if (ml_anch && sv && !SvROK(sv) /* See prev comment on SvROK */
790             && (strpos != strbeg) && strpos[-1] != '\n'
791             /* May be due to an implicit anchor of m{.*foo}  */
792             && !(prog->reganch & ROPT_IMPLICIT))
793         {
794             t = strpos;
795             goto find_anchor;
796         }
797         DEBUG_r( if (ml_anch)
798             PerlIO_printf(Perl_debug_log, "Position at offset %ld does not contradict /%s^%s/m...\n",
799                         (long)(strpos - i_strpos), PL_colors[0],PL_colors[1]);
800         );
801       success_at_start:
802         if (!(prog->reganch & ROPT_NAUGHTY)     /* XXXX If strpos moved? */
803             && (do_utf8 ? (
804                 prog->check_utf8                /* Could be deleted already */
805                 && --BmUSEFUL(prog->check_utf8) < 0
806                 && (prog->check_utf8 == prog->float_utf8)
807             ) : (
808                 prog->check_substr              /* Could be deleted already */
809                 && --BmUSEFUL(prog->check_substr) < 0
810                 && (prog->check_substr == prog->float_substr)
811             )))
812         {
813             /* If flags & SOMETHING - do not do it many times on the same match */
814             DEBUG_r(PerlIO_printf(Perl_debug_log, "... Disabling check substring...\n"));
815             SvREFCNT_dec(do_utf8 ? prog->check_utf8 : prog->check_substr);
816             if (do_utf8 ? prog->check_substr : prog->check_utf8)
817                 SvREFCNT_dec(do_utf8 ? prog->check_substr : prog->check_utf8);
818             prog->check_substr = prog->check_utf8 = Nullsv;     /* disable */
819             prog->float_substr = prog->float_utf8 = Nullsv;     /* clear */
820             check = Nullsv;                     /* abort */
821             s = strpos;
822             /* XXXX This is a remnant of the old implementation.  It
823                     looks wasteful, since now INTUIT can use many
824                     other heuristics. */
825             prog->reganch &= ~RE_USE_INTUIT;
826         }
827         else
828             s = strpos;
829     }
830
831     /* Last resort... */
832     /* XXXX BmUSEFUL already changed, maybe multiple change is meaningful... */
833     if (prog->regstclass) {
834         /* minlen == 0 is possible if regstclass is \b or \B,
835            and the fixed substr is ''$.
836            Since minlen is already taken into account, s+1 is before strend;
837            accidentally, minlen >= 1 guaranties no false positives at s + 1
838            even for \b or \B.  But (minlen? 1 : 0) below assumes that
839            regstclass does not come from lookahead...  */
840         /* If regstclass takes bytelength more than 1: If charlength==1, OK.
841            This leaves EXACTF only, which is dealt with in find_byclass().  */
842         U8* str = (U8*)STRING(prog->regstclass);
843         int cl_l = (PL_regkind[(U8)OP(prog->regstclass)] == EXACT
844                     ? CHR_DIST(str+STR_LEN(prog->regstclass), str)
845                     : 1);
846         char *endpos = (prog->anchored_substr || prog->anchored_utf8 || ml_anch)
847                 ? HOP3c(s, (prog->minlen ? cl_l : 0), strend)
848                 : (prog->float_substr || prog->float_utf8
849                    ? HOP3c(HOP3c(check_at, -start_shift, strbeg),
850                            cl_l, strend)
851                    : strend);
852         char *startpos = strbeg;
853
854         t = s;
855         if (prog->reganch & ROPT_UTF8) {        
856             PL_regdata = prog->data;
857             PL_bostr = startpos;
858         }
859         cache_re(prog);
860         s = find_byclass(prog, prog->regstclass, s, endpos, startpos, 1);
861         if (!s) {
862 #ifdef DEBUGGING
863             char *what = 0;
864 #endif
865             if (endpos == strend) {
866                 DEBUG_r( PerlIO_printf(Perl_debug_log,
867                                 "Could not match STCLASS...\n") );
868                 goto fail;
869             }
870             DEBUG_r( PerlIO_printf(Perl_debug_log,
871                                    "This position contradicts STCLASS...\n") );
872             if ((prog->reganch & ROPT_ANCH) && !ml_anch)
873                 goto fail;
874             /* Contradict one of substrings */
875             if (prog->anchored_substr || prog->anchored_utf8) {
876                 if ((do_utf8 ? prog->anchored_utf8 : prog->anchored_substr) == check) {
877                     DEBUG_r( what = "anchored" );
878                   hop_and_restart:
879                     s = HOP3c(t, 1, strend);
880                     if (s + start_shift + end_shift > strend) {
881                         /* XXXX Should be taken into account earlier? */
882                         DEBUG_r( PerlIO_printf(Perl_debug_log,
883                                                "Could not match STCLASS...\n") );
884                         goto fail;
885                     }
886                     if (!check)
887                         goto giveup;
888                     DEBUG_r( PerlIO_printf(Perl_debug_log,
889                                 "Looking for %s substr starting at offset %ld...\n",
890                                  what, (long)(s + start_shift - i_strpos)) );
891                     goto restart;
892                 }
893                 /* Have both, check_string is floating */
894                 if (t + start_shift >= check_at) /* Contradicts floating=check */
895                     goto retry_floating_check;
896                 /* Recheck anchored substring, but not floating... */
897                 s = check_at;
898                 if (!check)
899                     goto giveup;
900                 DEBUG_r( PerlIO_printf(Perl_debug_log,
901                           "Looking for anchored substr starting at offset %ld...\n",
902                           (long)(other_last - i_strpos)) );
903                 goto do_other_anchored;
904             }
905             /* Another way we could have checked stclass at the
906                current position only: */
907             if (ml_anch) {
908                 s = t = t + 1;
909                 if (!check)
910                     goto giveup;
911                 DEBUG_r( PerlIO_printf(Perl_debug_log,
912                           "Looking for /%s^%s/m starting at offset %ld...\n",
913                           PL_colors[0],PL_colors[1], (long)(t - i_strpos)) );
914                 goto try_at_offset;
915             }
916             if (!(do_utf8 ? prog->float_utf8 : prog->float_substr))     /* Could have been deleted */
917                 goto fail;
918             /* Check is floating subtring. */
919           retry_floating_check:
920             t = check_at - start_shift;
921             DEBUG_r( what = "floating" );
922             goto hop_and_restart;
923         }
924         if (t != s) {
925             DEBUG_r(PerlIO_printf(Perl_debug_log,
926                         "By STCLASS: moving %ld --> %ld\n",
927                                   (long)(t - i_strpos), (long)(s - i_strpos))
928                    );
929         }
930         else {
931             DEBUG_r(PerlIO_printf(Perl_debug_log,
932                                   "Does not contradict STCLASS...\n"); 
933                    );
934         }
935     }
936   giveup:
937     DEBUG_r(PerlIO_printf(Perl_debug_log, "%s%s:%s match at offset %ld\n",
938                           PL_colors[4], (check ? "Guessed" : "Giving up"),
939                           PL_colors[5], (long)(s - i_strpos)) );
940     return s;
941
942   fail_finish:                          /* Substring not found */
943     if (prog->check_substr || prog->check_utf8)         /* could be removed already */
944         BmUSEFUL(do_utf8 ? prog->check_utf8 : prog->check_substr) += 5; /* hooray */
945   fail:
946     DEBUG_r(PerlIO_printf(Perl_debug_log, "%sMatch rejected by optimizer%s\n",
947                           PL_colors[4],PL_colors[5]));
948     return Nullch;
949 }
950
951 /* We know what class REx starts with.  Try to find this position... */
952 STATIC char *
953 S_find_byclass(pTHX_ regexp * prog, regnode *c, char *s, char *strend, char *startpos, I32 norun)
954 {
955         I32 doevery = (prog->reganch & ROPT_SKIP) == 0;
956         char *m;
957         STRLEN ln;
958         unsigned int c1;
959         unsigned int c2;
960         char *e;
961         register I32 tmp = 1;   /* Scratch variable? */
962         register bool do_utf8 = PL_reg_match_utf8;
963
964         /* We know what class it must start with. */
965         switch (OP(c)) {
966         case ANYOF:
967             if (do_utf8) {
968                  while (s < strend) {
969                       if ((ANYOF_FLAGS(c) & ANYOF_UNICODE) ||
970                           !UTF8_IS_INVARIANT((U8)s[0]) ?
971                           reginclass(c, (U8*)s, 0, do_utf8) :
972                           REGINCLASS(c, (U8*)s)) {
973                            if (tmp && (norun || regtry(prog, s)))
974                                 goto got_it;
975                            else
976                                 tmp = doevery;
977                       }
978                       else 
979                            tmp = 1;
980                       s += UTF8SKIP(s);
981                  }
982             }
983             else {
984                  while (s < strend) {
985                       STRLEN skip = 1;
986
987                       if (REGINCLASS(c, (U8*)s) ||
988                           (ANYOF_FOLD_SHARP_S(c, s, strend) &&
989                            /* The assignment of 2 is intentional:
990                             * for the folded sharp s, the skip is 2. */
991                            (skip = SHARP_S_SKIP))) {
992                            if (tmp && (norun || regtry(prog, s)))
993                                 goto got_it;
994                            else
995                                 tmp = doevery;
996                       }
997                       else 
998                            tmp = 1;
999                       s += skip;
1000                  }
1001             }
1002             break;
1003         case CANY:
1004             while (s < strend) {
1005                 if (tmp && (norun || regtry(prog, s)))
1006                     goto got_it;
1007                 else
1008                     tmp = doevery;
1009                 s++;
1010             }
1011             break;
1012         case EXACTF:
1013             m = STRING(c);
1014             ln = STR_LEN(c);
1015             if (UTF) {
1016                 STRLEN ulen1, ulen2;
1017                 U8 tmpbuf1[UTF8_MAXLEN_UCLC+1];
1018                 U8 tmpbuf2[UTF8_MAXLEN_UCLC+1];
1019
1020                 to_utf8_lower((U8*)m, tmpbuf1, &ulen1);
1021                 to_utf8_upper((U8*)m, tmpbuf2, &ulen2);
1022
1023                 c1 = utf8n_to_uvchr(tmpbuf1, UTF8_MAXLEN_UCLC, 
1024                                     0, ckWARN(WARN_UTF8) ? 0 : UTF8_ALLOW_ANY);
1025                 c2 = utf8n_to_uvchr(tmpbuf2, UTF8_MAXLEN_UCLC,
1026                                     0, ckWARN(WARN_UTF8) ? 0 : UTF8_ALLOW_ANY);
1027             }
1028             else {
1029                 c1 = *(U8*)m;
1030                 c2 = PL_fold[c1];
1031             }
1032             goto do_exactf;
1033         case EXACTFL:
1034             m = STRING(c);
1035             ln = STR_LEN(c);
1036             c1 = *(U8*)m;
1037             c2 = PL_fold_locale[c1];
1038           do_exactf:
1039             e = HOP3c(strend, -(I32)ln, s);
1040
1041             if (norun && e < s)
1042                 e = s;                  /* Due to minlen logic of intuit() */
1043
1044             /* The idea in the EXACTF* cases is to first find the
1045              * first character of the EXACTF* node and then, if
1046              * necessary, case-insensitively compare the full
1047              * text of the node.  The c1 and c2 are the first
1048              * characters (though in Unicode it gets a bit
1049              * more complicated because there are more cases
1050              * than just upper and lower: one needs to use
1051              * the so-called folding case for case-insensitive
1052              * matching (called "loose matching" in Unicode).
1053              * ibcmp_utf8() will do just that. */
1054
1055             if (do_utf8) {
1056                 UV c, f;
1057                 U8 tmpbuf [UTF8_MAXLEN+1];
1058                 U8 foldbuf[UTF8_MAXLEN_FOLD+1];
1059                 STRLEN len, foldlen;
1060                 
1061                 if (c1 == c2) {
1062                     while (s <= e) {
1063                         c = utf8n_to_uvchr((U8*)s, UTF8_MAXLEN, &len,
1064                                            ckWARN(WARN_UTF8) ?
1065                                            0 : UTF8_ALLOW_ANY);
1066                         if ( c == c1
1067                              && (ln == len ||
1068                                  ibcmp_utf8(s, (char **)0, 0,  do_utf8,
1069                                             m, (char **)0, ln, (bool)UTF))
1070                              && (norun || regtry(prog, s)) )
1071                             goto got_it;
1072                         else {
1073                              uvchr_to_utf8(tmpbuf, c);
1074                              f = to_utf8_fold(tmpbuf, foldbuf, &foldlen);
1075                              if ( f != c
1076                                   && (f == c1 || f == c2)
1077                                   && (ln == foldlen ||
1078                                       !ibcmp_utf8((char *) foldbuf,
1079                                                   (char **)0, foldlen, do_utf8,
1080                                                   m,
1081                                                   (char **)0, ln, (bool)UTF))
1082                                   && (norun || regtry(prog, s)) )
1083                                   goto got_it;
1084                         }
1085                         s += len;
1086                     }
1087                 }
1088                 else {
1089                     while (s <= e) {
1090                       c = utf8n_to_uvchr((U8*)s, UTF8_MAXLEN, &len,
1091                                            ckWARN(WARN_UTF8) ?
1092                                            0 : UTF8_ALLOW_ANY);
1093
1094                         /* Handle some of the three Greek sigmas cases.
1095                          * Note that not all the possible combinations
1096                          * are handled here: some of them are handled
1097                          * by the standard folding rules, and some of
1098                          * them (the character class or ANYOF cases)
1099                          * are handled during compiletime in
1100                          * regexec.c:S_regclass(). */
1101                         if (c == (UV)UNICODE_GREEK_CAPITAL_LETTER_SIGMA ||
1102                             c == (UV)UNICODE_GREEK_SMALL_LETTER_FINAL_SIGMA)
1103                             c = (UV)UNICODE_GREEK_SMALL_LETTER_SIGMA;
1104
1105                         if ( (c == c1 || c == c2)
1106                              && (ln == len ||
1107                                  ibcmp_utf8(s, (char **)0, 0,  do_utf8,
1108                                             m, (char **)0, ln, (bool)UTF))
1109                              && (norun || regtry(prog, s)) )
1110                             goto got_it;
1111                         else {
1112                              uvchr_to_utf8(tmpbuf, c);
1113                              f = to_utf8_fold(tmpbuf, foldbuf, &foldlen);
1114                              if ( f != c
1115                                   && (f == c1 || f == c2)
1116                                   && (ln == foldlen ||
1117                                       !ibcmp_utf8((char *) foldbuf,
1118                                                   (char **)0, foldlen, do_utf8,
1119                                                   m,
1120                                                   (char **)0, ln, (bool)UTF))
1121                                   && (norun || regtry(prog, s)) )
1122                                   goto got_it;
1123                         }
1124                         s += len;
1125                     }
1126                 }
1127             }
1128             else {
1129                 if (c1 == c2)
1130                     while (s <= e) {
1131                         if ( *(U8*)s == c1
1132                              && (ln == 1 || !(OP(c) == EXACTF
1133                                               ? ibcmp(s, m, ln)
1134                                               : ibcmp_locale(s, m, ln)))
1135                              && (norun || regtry(prog, s)) )
1136                             goto got_it;
1137                         s++;
1138                     }
1139                 else
1140                     while (s <= e) {
1141                         if ( (*(U8*)s == c1 || *(U8*)s == c2)
1142                              && (ln == 1 || !(OP(c) == EXACTF
1143                                               ? ibcmp(s, m, ln)
1144                                               : ibcmp_locale(s, m, ln)))
1145                              && (norun || regtry(prog, s)) )
1146                             goto got_it;
1147                         s++;
1148                     }
1149             }
1150             break;
1151         case BOUNDL:
1152             PL_reg_flags |= RF_tainted;
1153             /* FALL THROUGH */
1154         case BOUND:
1155             if (do_utf8) {
1156                 if (s == PL_bostr)
1157                     tmp = '\n';
1158                 else {
1159                     U8 *r = reghop3((U8*)s, -1, (U8*)PL_bostr);
1160                 
1161                     tmp = utf8n_to_uvchr(r, UTF8SKIP(r), 0, 0);
1162                 }
1163                 tmp = ((OP(c) == BOUND ?
1164                         isALNUM_uni(tmp) : isALNUM_LC_uvchr(UNI_TO_NATIVE(tmp))) != 0);
1165                 LOAD_UTF8_CHARCLASS(alnum,"a");
1166                 while (s < strend) {
1167                     if (tmp == !(OP(c) == BOUND ?
1168                                  swash_fetch(PL_utf8_alnum, (U8*)s, do_utf8) :
1169                                  isALNUM_LC_utf8((U8*)s)))
1170                     {
1171                         tmp = !tmp;
1172                         if ((norun || regtry(prog, s)))
1173                             goto got_it;
1174                     }
1175                     s += UTF8SKIP(s);
1176                 }
1177             }
1178             else {
1179                 tmp = (s != PL_bostr) ? UCHARAT(s - 1) : '\n';
1180                 tmp = ((OP(c) == BOUND ? isALNUM(tmp) : isALNUM_LC(tmp)) != 0);
1181                 while (s < strend) {
1182                     if (tmp ==
1183                         !(OP(c) == BOUND ? isALNUM(*s) : isALNUM_LC(*s))) {
1184                         tmp = !tmp;
1185                         if ((norun || regtry(prog, s)))
1186                             goto got_it;
1187                     }
1188                     s++;
1189                 }
1190             }
1191             if ((!prog->minlen && tmp) && (norun || regtry(prog, s)))
1192                 goto got_it;
1193             break;
1194         case NBOUNDL:
1195             PL_reg_flags |= RF_tainted;
1196             /* FALL THROUGH */
1197         case NBOUND:
1198             if (do_utf8) {
1199                 if (s == PL_bostr)
1200                     tmp = '\n';
1201                 else {
1202                     U8 *r = reghop3((U8*)s, -1, (U8*)PL_bostr);
1203                 
1204                     tmp = utf8n_to_uvchr(r, UTF8SKIP(r), 0, 0);
1205                 }
1206                 tmp = ((OP(c) == NBOUND ?
1207                         isALNUM_uni(tmp) : isALNUM_LC_uvchr(UNI_TO_NATIVE(tmp))) != 0);
1208                 LOAD_UTF8_CHARCLASS(alnum,"a");
1209                 while (s < strend) {
1210                     if (tmp == !(OP(c) == NBOUND ?
1211                                  swash_fetch(PL_utf8_alnum, (U8*)s, do_utf8) :
1212                                  isALNUM_LC_utf8((U8*)s)))
1213                         tmp = !tmp;
1214                     else if ((norun || regtry(prog, s)))
1215                         goto got_it;
1216                     s += UTF8SKIP(s);
1217                 }
1218             }
1219             else {
1220                 tmp = (s != PL_bostr) ? UCHARAT(s - 1) : '\n';
1221                 tmp = ((OP(c) == NBOUND ?
1222                         isALNUM(tmp) : isALNUM_LC(tmp)) != 0);
1223                 while (s < strend) {
1224                     if (tmp ==
1225                         !(OP(c) == NBOUND ? isALNUM(*s) : isALNUM_LC(*s)))
1226                         tmp = !tmp;
1227                     else if ((norun || regtry(prog, s)))
1228                         goto got_it;
1229                     s++;
1230                 }
1231             }
1232             if ((!prog->minlen && !tmp) && (norun || regtry(prog, s)))
1233                 goto got_it;
1234             break;
1235         case ALNUM:
1236             if (do_utf8) {
1237                 LOAD_UTF8_CHARCLASS(alnum,"a");
1238                 while (s < strend) {
1239                     if (swash_fetch(PL_utf8_alnum, (U8*)s, do_utf8)) {
1240                         if (tmp && (norun || regtry(prog, s)))
1241                             goto got_it;
1242                         else
1243                             tmp = doevery;
1244                     }
1245                     else
1246                         tmp = 1;
1247                     s += UTF8SKIP(s);
1248                 }
1249             }
1250             else {
1251                 while (s < strend) {
1252                     if (isALNUM(*s)) {
1253                         if (tmp && (norun || regtry(prog, s)))
1254                             goto got_it;
1255                         else
1256                             tmp = doevery;
1257                     }
1258                     else
1259                         tmp = 1;
1260                     s++;
1261                 }
1262             }
1263             break;
1264         case ALNUML:
1265             PL_reg_flags |= RF_tainted;
1266             if (do_utf8) {
1267                 while (s < strend) {
1268                     if (isALNUM_LC_utf8((U8*)s)) {
1269                         if (tmp && (norun || regtry(prog, s)))
1270                             goto got_it;
1271                         else
1272                             tmp = doevery;
1273                     }
1274                     else
1275                         tmp = 1;
1276                     s += UTF8SKIP(s);
1277                 }
1278             }
1279             else {
1280                 while (s < strend) {
1281                     if (isALNUM_LC(*s)) {
1282                         if (tmp && (norun || regtry(prog, s)))
1283                             goto got_it;
1284                         else
1285                             tmp = doevery;
1286                     }
1287                     else
1288                         tmp = 1;
1289                     s++;
1290                 }
1291             }
1292             break;
1293         case NALNUM:
1294             if (do_utf8) {
1295                 LOAD_UTF8_CHARCLASS(alnum,"a");
1296                 while (s < strend) {
1297                     if (!swash_fetch(PL_utf8_alnum, (U8*)s, do_utf8)) {
1298                         if (tmp && (norun || regtry(prog, s)))
1299                             goto got_it;
1300                         else
1301                             tmp = doevery;
1302                     }
1303                     else
1304                         tmp = 1;
1305                     s += UTF8SKIP(s);
1306                 }
1307             }
1308             else {
1309                 while (s < strend) {
1310                     if (!isALNUM(*s)) {
1311                         if (tmp && (norun || regtry(prog, s)))
1312                             goto got_it;
1313                         else
1314                             tmp = doevery;
1315                     }
1316                     else
1317                         tmp = 1;
1318                     s++;
1319                 }
1320             }
1321             break;
1322         case NALNUML:
1323             PL_reg_flags |= RF_tainted;
1324             if (do_utf8) {
1325                 while (s < strend) {
1326                     if (!isALNUM_LC_utf8((U8*)s)) {
1327                         if (tmp && (norun || regtry(prog, s)))
1328                             goto got_it;
1329                         else
1330                             tmp = doevery;
1331                     }
1332                     else
1333                         tmp = 1;
1334                     s += UTF8SKIP(s);
1335                 }
1336             }
1337             else {
1338                 while (s < strend) {
1339                     if (!isALNUM_LC(*s)) {
1340                         if (tmp && (norun || regtry(prog, s)))
1341                             goto got_it;
1342                         else
1343                             tmp = doevery;
1344                     }
1345                     else
1346                         tmp = 1;
1347                     s++;
1348                 }
1349             }
1350             break;
1351         case SPACE:
1352             if (do_utf8) {
1353                 LOAD_UTF8_CHARCLASS(space," ");
1354                 while (s < strend) {
1355                     if (*s == ' ' || swash_fetch(PL_utf8_space,(U8*)s, do_utf8)) {
1356                         if (tmp && (norun || regtry(prog, s)))
1357                             goto got_it;
1358                         else
1359                             tmp = doevery;
1360                     }
1361                     else
1362                         tmp = 1;
1363                     s += UTF8SKIP(s);
1364                 }
1365             }
1366             else {
1367                 while (s < strend) {
1368                     if (isSPACE(*s)) {
1369                         if (tmp && (norun || regtry(prog, s)))
1370                             goto got_it;
1371                         else
1372                             tmp = doevery;
1373                     }
1374                     else
1375                         tmp = 1;
1376                     s++;
1377                 }
1378             }
1379             break;
1380         case SPACEL:
1381             PL_reg_flags |= RF_tainted;
1382             if (do_utf8) {
1383                 while (s < strend) {
1384                     if (*s == ' ' || isSPACE_LC_utf8((U8*)s)) {
1385                         if (tmp && (norun || regtry(prog, s)))
1386                             goto got_it;
1387                         else
1388                             tmp = doevery;
1389                     }
1390                     else
1391                         tmp = 1;
1392                     s += UTF8SKIP(s);
1393                 }
1394             }
1395             else {
1396                 while (s < strend) {
1397                     if (isSPACE_LC(*s)) {
1398                         if (tmp && (norun || regtry(prog, s)))
1399                             goto got_it;
1400                         else
1401                             tmp = doevery;
1402                     }
1403                     else
1404                         tmp = 1;
1405                     s++;
1406                 }
1407             }
1408             break;
1409         case NSPACE:
1410             if (do_utf8) {
1411                 LOAD_UTF8_CHARCLASS(space," ");
1412                 while (s < strend) {
1413                     if (!(*s == ' ' || swash_fetch(PL_utf8_space,(U8*)s, do_utf8))) {
1414                         if (tmp && (norun || regtry(prog, s)))
1415                             goto got_it;
1416                         else
1417                             tmp = doevery;
1418                     }
1419                     else
1420                         tmp = 1;
1421                     s += UTF8SKIP(s);
1422                 }
1423             }
1424             else {
1425                 while (s < strend) {
1426                     if (!isSPACE(*s)) {
1427                         if (tmp && (norun || regtry(prog, s)))
1428                             goto got_it;
1429                         else
1430                             tmp = doevery;
1431                     }
1432                     else
1433                         tmp = 1;
1434                     s++;
1435                 }
1436             }
1437             break;
1438         case NSPACEL:
1439             PL_reg_flags |= RF_tainted;
1440             if (do_utf8) {
1441                 while (s < strend) {
1442                     if (!(*s == ' ' || isSPACE_LC_utf8((U8*)s))) {
1443                         if (tmp && (norun || regtry(prog, s)))
1444                             goto got_it;
1445                         else
1446                             tmp = doevery;
1447                     }
1448                     else
1449                         tmp = 1;
1450                     s += UTF8SKIP(s);
1451                 }
1452             }
1453             else {
1454                 while (s < strend) {
1455                     if (!isSPACE_LC(*s)) {
1456                         if (tmp && (norun || regtry(prog, s)))
1457                             goto got_it;
1458                         else
1459                             tmp = doevery;
1460                     }
1461                     else
1462                         tmp = 1;
1463                     s++;
1464                 }
1465             }
1466             break;
1467         case DIGIT:
1468             if (do_utf8) {
1469                 LOAD_UTF8_CHARCLASS(digit,"0");
1470                 while (s < strend) {
1471                     if (swash_fetch(PL_utf8_digit,(U8*)s, do_utf8)) {
1472                         if (tmp && (norun || regtry(prog, s)))
1473                             goto got_it;
1474                         else
1475                             tmp = doevery;
1476                     }
1477                     else
1478                         tmp = 1;
1479                     s += UTF8SKIP(s);
1480                 }
1481             }
1482             else {
1483                 while (s < strend) {
1484                     if (isDIGIT(*s)) {
1485                         if (tmp && (norun || regtry(prog, s)))
1486                             goto got_it;
1487                         else
1488                             tmp = doevery;
1489                     }
1490                     else
1491                         tmp = 1;
1492                     s++;
1493                 }
1494             }
1495             break;
1496         case DIGITL:
1497             PL_reg_flags |= RF_tainted;
1498             if (do_utf8) {
1499                 while (s < strend) {
1500                     if (isDIGIT_LC_utf8((U8*)s)) {
1501                         if (tmp && (norun || regtry(prog, s)))
1502                             goto got_it;
1503                         else
1504                             tmp = doevery;
1505                     }
1506                     else
1507                         tmp = 1;
1508                     s += UTF8SKIP(s);
1509                 }
1510             }
1511             else {
1512                 while (s < strend) {
1513                     if (isDIGIT_LC(*s)) {
1514                         if (tmp && (norun || regtry(prog, s)))
1515                             goto got_it;
1516                         else
1517                             tmp = doevery;
1518                     }
1519                     else
1520                         tmp = 1;
1521                     s++;
1522                 }
1523             }
1524             break;
1525         case NDIGIT:
1526             if (do_utf8) {
1527                 LOAD_UTF8_CHARCLASS(digit,"0");
1528                 while (s < strend) {
1529                     if (!swash_fetch(PL_utf8_digit,(U8*)s, do_utf8)) {
1530                         if (tmp && (norun || regtry(prog, s)))
1531                             goto got_it;
1532                         else
1533                             tmp = doevery;
1534                     }
1535                     else
1536                         tmp = 1;
1537                     s += UTF8SKIP(s);
1538                 }
1539             }
1540             else {
1541                 while (s < strend) {
1542                     if (!isDIGIT(*s)) {
1543                         if (tmp && (norun || regtry(prog, s)))
1544                             goto got_it;
1545                         else
1546                             tmp = doevery;
1547                     }
1548                     else
1549                         tmp = 1;
1550                     s++;
1551                 }
1552             }
1553             break;
1554         case NDIGITL:
1555             PL_reg_flags |= RF_tainted;
1556             if (do_utf8) {
1557                 while (s < strend) {
1558                     if (!isDIGIT_LC_utf8((U8*)s)) {
1559                         if (tmp && (norun || regtry(prog, s)))
1560                             goto got_it;
1561                         else
1562                             tmp = doevery;
1563                     }
1564                     else
1565                         tmp = 1;
1566                     s += UTF8SKIP(s);
1567                 }
1568             }
1569             else {
1570                 while (s < strend) {
1571                     if (!isDIGIT_LC(*s)) {
1572                         if (tmp && (norun || regtry(prog, s)))
1573                             goto got_it;
1574                         else
1575                             tmp = doevery;
1576                     }
1577                     else
1578                         tmp = 1;
1579                     s++;
1580                 }
1581             }
1582             break;
1583         default:
1584             Perl_croak(aTHX_ "panic: unknown regstclass %d", (int)OP(c));
1585             break;
1586         }
1587         return 0;
1588       got_it:
1589         return s;
1590 }
1591
1592 /*
1593  - regexec_flags - match a regexp against a string
1594  */
1595 I32
1596 Perl_regexec_flags(pTHX_ register regexp *prog, char *stringarg, register char *strend,
1597               char *strbeg, I32 minend, SV *sv, void *data, U32 flags)
1598 /* strend: pointer to null at end of string */
1599 /* strbeg: real beginning of string */
1600 /* minend: end of match must be >=minend after stringarg. */
1601 /* data: May be used for some additional optimizations. */
1602 /* nosave: For optimizations. */
1603 {
1604     register char *s;
1605     register regnode *c;
1606     register char *startpos = stringarg;
1607     I32 minlen;         /* must match at least this many chars */
1608     I32 dontbother = 0; /* how many characters not to try at end */
1609     /* I32 start_shift = 0; */          /* Offset of the start to find
1610                                          constant substr. */            /* CC */
1611     I32 end_shift = 0;                  /* Same for the end. */         /* CC */
1612     I32 scream_pos = -1;                /* Internal iterator of scream. */
1613     char *scream_olds;
1614     SV* oreplsv = GvSV(PL_replgv);
1615     bool do_utf8 = DO_UTF8(sv);
1616 #ifdef DEBUGGING
1617     SV *dsv0 = PERL_DEBUG_PAD_ZERO(0);
1618     SV *dsv1 = PERL_DEBUG_PAD_ZERO(1);
1619 #endif
1620     RX_MATCH_UTF8_set(prog,do_utf8);
1621
1622     PL_regcc = 0;
1623
1624     cache_re(prog);
1625 #ifdef DEBUGGING
1626     PL_regnarrate = DEBUG_r_TEST;
1627 #endif
1628
1629     /* Be paranoid... */
1630     if (prog == NULL || startpos == NULL) {
1631         Perl_croak(aTHX_ "NULL regexp parameter");
1632         return 0;
1633     }
1634
1635     minlen = prog->minlen;
1636     if (strend - startpos < minlen) {
1637         DEBUG_r(PerlIO_printf(Perl_debug_log,
1638                               "String too short [regexec_flags]...\n"));
1639         goto phooey;
1640     }
1641
1642     /* Check validity of program. */
1643     if (UCHARAT(prog->program) != REG_MAGIC) {
1644         Perl_croak(aTHX_ "corrupted regexp program");
1645     }
1646
1647     PL_reg_flags = 0;
1648     PL_reg_eval_set = 0;
1649     PL_reg_maxiter = 0;
1650
1651     if (prog->reganch & ROPT_UTF8)
1652         PL_reg_flags |= RF_utf8;
1653
1654     /* Mark beginning of line for ^ and lookbehind. */
1655     PL_regbol = startpos;
1656     PL_bostr  = strbeg;
1657     PL_reg_sv = sv;
1658
1659     /* Mark end of line for $ (and such) */
1660     PL_regeol = strend;
1661
1662     /* see how far we have to get to not match where we matched before */
1663     PL_regtill = startpos+minend;
1664
1665     /* We start without call_cc context.  */
1666     PL_reg_call_cc = 0;
1667
1668     /* If there is a "must appear" string, look for it. */
1669     s = startpos;
1670
1671     if (prog->reganch & ROPT_GPOS_SEEN) { /* Need to have PL_reg_ganch */
1672         MAGIC *mg;
1673
1674         if (flags & REXEC_IGNOREPOS)    /* Means: check only at start */
1675             PL_reg_ganch = startpos;
1676         else if (sv && SvTYPE(sv) >= SVt_PVMG
1677                   && SvMAGIC(sv)
1678                   && (mg = mg_find(sv, PERL_MAGIC_regex_global))
1679                   && mg->mg_len >= 0) {
1680             PL_reg_ganch = strbeg + mg->mg_len; /* Defined pos() */
1681             if (prog->reganch & ROPT_ANCH_GPOS) {
1682                 if (s > PL_reg_ganch)
1683                     goto phooey;
1684                 s = PL_reg_ganch;
1685             }
1686         }
1687         else                            /* pos() not defined */
1688             PL_reg_ganch = strbeg;
1689     }
1690
1691     if (!(flags & REXEC_CHECKED) && (prog->check_substr != Nullsv || prog->check_utf8 != Nullsv)) {
1692         re_scream_pos_data d;
1693
1694         d.scream_olds = &scream_olds;
1695         d.scream_pos = &scream_pos;
1696         s = re_intuit_start(prog, sv, s, strend, flags, &d);
1697         if (!s) {
1698             DEBUG_r(PerlIO_printf(Perl_debug_log, "Not present...\n"));
1699             goto phooey;        /* not present */
1700         }
1701     }
1702
1703     DEBUG_r({
1704          char *s0   = UTF ?
1705            pv_uni_display(dsv0, (U8*)prog->precomp, prog->prelen, 60,
1706                           UNI_DISPLAY_REGEX) :
1707            prog->precomp;
1708          int   len0 = UTF ? SvCUR(dsv0) : prog->prelen;
1709          char *s1   = do_utf8 ? sv_uni_display(dsv1, sv, 60,
1710                                                UNI_DISPLAY_REGEX) : startpos;
1711          int   len1 = do_utf8 ? SvCUR(dsv1) : strend - startpos;
1712          if (!PL_colorset)
1713              reginitcolors();
1714          PerlIO_printf(Perl_debug_log,
1715                        "%sMatching REx%s `%s%*.*s%s%s' against `%s%.*s%s%s'\n",
1716                        PL_colors[4],PL_colors[5],PL_colors[0],
1717                        len0, len0, s0,
1718                        PL_colors[1],
1719                        len0 > 60 ? "..." : "",
1720                        PL_colors[0],
1721                        (int)(len1 > 60 ? 60 : len1),
1722                        s1, PL_colors[1],
1723                        (len1 > 60 ? "..." : "")
1724               );
1725     });
1726
1727     /* Simplest case:  anchored match need be tried only once. */
1728     /*  [unless only anchor is BOL and multiline is set] */
1729     if (prog->reganch & (ROPT_ANCH & ~ROPT_ANCH_GPOS)) {
1730         if (s == startpos && regtry(prog, startpos))
1731             goto got_it;
1732         else if (PL_multiline || (prog->reganch & ROPT_IMPLICIT)
1733                  || (prog->reganch & ROPT_ANCH_MBOL)) /* XXXX SBOL? */
1734         {
1735             char *end;
1736
1737             if (minlen)
1738                 dontbother = minlen - 1;
1739             end = HOP3c(strend, -dontbother, strbeg) - 1;
1740             /* for multiline we only have to try after newlines */
1741             if (prog->check_substr || prog->check_utf8) {
1742                 if (s == startpos)
1743                     goto after_try;
1744                 while (1) {
1745                     if (regtry(prog, s))
1746                         goto got_it;
1747                   after_try:
1748                     if (s >= end)
1749                         goto phooey;
1750                     if (prog->reganch & RE_USE_INTUIT) {
1751                         s = re_intuit_start(prog, sv, s + 1, strend, flags, NULL);
1752                         if (!s)
1753                             goto phooey;
1754                     }
1755                     else
1756                         s++;
1757                 }               
1758             } else {
1759                 if (s > startpos)
1760                     s--;
1761                 while (s < end) {
1762                     if (*s++ == '\n') { /* don't need PL_utf8skip here */
1763                         if (regtry(prog, s))
1764                             goto got_it;
1765                     }
1766                 }               
1767             }
1768         }
1769         goto phooey;
1770     } else if (prog->reganch & ROPT_ANCH_GPOS) {
1771         if (regtry(prog, PL_reg_ganch))
1772             goto got_it;
1773         goto phooey;
1774     }
1775
1776     /* Messy cases:  unanchored match. */
1777     if ((prog->anchored_substr || prog->anchored_utf8) && prog->reganch & ROPT_SKIP) {
1778         /* we have /x+whatever/ */
1779         /* it must be a one character string (XXXX Except UTF?) */
1780         char ch;
1781 #ifdef DEBUGGING
1782         int did_match = 0;
1783 #endif
1784         if (!(do_utf8 ? prog->anchored_utf8 : prog->anchored_substr))
1785             do_utf8 ? to_utf8_substr(prog) : to_byte_substr(prog);
1786         ch = SvPVX(do_utf8 ? prog->anchored_utf8 : prog->anchored_substr)[0];
1787
1788         if (do_utf8) {
1789             while (s < strend) {
1790                 if (*s == ch) {
1791                     DEBUG_r( did_match = 1 );
1792                     if (regtry(prog, s)) goto got_it;
1793                     s += UTF8SKIP(s);
1794                     while (s < strend && *s == ch)
1795                         s += UTF8SKIP(s);
1796                 }
1797                 s += UTF8SKIP(s);
1798             }
1799         }
1800         else {
1801             while (s < strend) {
1802                 if (*s == ch) {
1803                     DEBUG_r( did_match = 1 );
1804                     if (regtry(prog, s)) goto got_it;
1805                     s++;
1806                     while (s < strend && *s == ch)
1807                         s++;
1808                 }
1809                 s++;
1810             }
1811         }
1812         DEBUG_r(if (!did_match)
1813                 PerlIO_printf(Perl_debug_log,
1814                                   "Did not find anchored character...\n")
1815                );
1816     }
1817     /*SUPPRESS 560*/
1818     else if (prog->anchored_substr != Nullsv
1819               || prog->anchored_utf8 != Nullsv
1820               || ((prog->float_substr != Nullsv || prog->float_utf8 != Nullsv)
1821                   && prog->float_max_offset < strend - s)) {
1822         SV *must;
1823         I32 back_max;
1824         I32 back_min;
1825         char *last;
1826         char *last1;            /* Last position checked before */
1827 #ifdef DEBUGGING
1828         int did_match = 0;
1829 #endif
1830         if (prog->anchored_substr || prog->anchored_utf8) {
1831             if (!(do_utf8 ? prog->anchored_utf8 : prog->anchored_substr))
1832                 do_utf8 ? to_utf8_substr(prog) : to_byte_substr(prog);
1833             must = do_utf8 ? prog->anchored_utf8 : prog->anchored_substr;
1834             back_max = back_min = prog->anchored_offset;
1835         } else {
1836             if (!(do_utf8 ? prog->float_utf8 : prog->float_substr))
1837                 do_utf8 ? to_utf8_substr(prog) : to_byte_substr(prog);
1838             must = do_utf8 ? prog->float_utf8 : prog->float_substr;
1839             back_max = prog->float_max_offset;
1840             back_min = prog->float_min_offset;
1841         }
1842         if (must == &PL_sv_undef)
1843             /* could not downgrade utf8 check substring, so must fail */
1844             goto phooey;
1845
1846         last = HOP3c(strend,    /* Cannot start after this */
1847                           -(I32)(CHR_SVLEN(must)
1848                                  - (SvTAIL(must) != 0) + back_min), strbeg);
1849
1850         if (s > PL_bostr)
1851             last1 = HOPc(s, -1);
1852         else
1853             last1 = s - 1;      /* bogus */
1854
1855         /* XXXX check_substr already used to find `s', can optimize if
1856            check_substr==must. */
1857         scream_pos = -1;
1858         dontbother = end_shift;
1859         strend = HOPc(strend, -dontbother);
1860         while ( (s <= last) &&
1861                 ((flags & REXEC_SCREAM)
1862                  ? (s = screaminstr(sv, must, HOP3c(s, back_min, strend) - strbeg,
1863                                     end_shift, &scream_pos, 0))
1864                  : (s = fbm_instr((unsigned char*)HOP3(s, back_min, strend),
1865                                   (unsigned char*)strend, must,
1866                                   PL_multiline ? FBMrf_MULTILINE : 0))) ) {
1867             /* we may be pointing at the wrong string */
1868             if ((flags & REXEC_SCREAM) && RX_MATCH_COPIED(prog))
1869                 s = prog->subbeg + (s - SvPVX(sv));
1870             DEBUG_r( did_match = 1 );
1871             if (HOPc(s, -back_max) > last1) {
1872                 last1 = HOPc(s, -back_min);
1873                 s = HOPc(s, -back_max);
1874             }
1875             else {
1876                 char *t = (last1 >= PL_bostr) ? HOPc(last1, 1) : last1 + 1;
1877
1878                 last1 = HOPc(s, -back_min);
1879                 s = t;          
1880             }
1881             if (do_utf8) {
1882                 while (s <= last1) {
1883                     if (regtry(prog, s))
1884                         goto got_it;
1885                     s += UTF8SKIP(s);
1886                 }
1887             }
1888             else {
1889                 while (s <= last1) {
1890                     if (regtry(prog, s))
1891                         goto got_it;
1892                     s++;
1893                 }
1894             }
1895         }
1896         DEBUG_r(if (!did_match)
1897                     PerlIO_printf(Perl_debug_log, 
1898                                   "Did not find %s substr `%s%.*s%s'%s...\n",
1899                               ((must == prog->anchored_substr || must == prog->anchored_utf8)
1900                                ? "anchored" : "floating"),
1901                               PL_colors[0],
1902                               (int)(SvCUR(must) - (SvTAIL(must)!=0)),
1903                               SvPVX(must),
1904                                   PL_colors[1], (SvTAIL(must) ? "$" : ""))
1905                );
1906         goto phooey;
1907     }
1908     else if ((c = prog->regstclass)) {
1909         if (minlen) {
1910             I32 op = (U8)OP(prog->regstclass);
1911             /* don't bother with what can't match */
1912             if (PL_regkind[op] != EXACT && op != CANY)
1913                 strend = HOPc(strend, -(minlen - 1));
1914         }
1915         DEBUG_r({
1916             SV *prop = sv_newmortal();
1917             char *s0;
1918             char *s1;
1919             int len0;
1920             int len1;
1921
1922             regprop(prop, c);
1923             s0 = UTF ?
1924               pv_uni_display(dsv0, (U8*)SvPVX(prop), SvCUR(prop), 60,
1925                              UNI_DISPLAY_REGEX) :
1926               SvPVX(prop);
1927             len0 = UTF ? SvCUR(dsv0) : SvCUR(prop);
1928             s1 = UTF ?
1929               sv_uni_display(dsv1, sv, 60, UNI_DISPLAY_REGEX) : s;
1930             len1 = UTF ? SvCUR(dsv1) : strend - s;
1931             PerlIO_printf(Perl_debug_log,
1932                           "Matching stclass `%*.*s' against `%*.*s'\n",
1933                           len0, len0, s0,
1934                           len1, len1, s1);
1935         });
1936         if (find_byclass(prog, c, s, strend, startpos, 0))
1937             goto got_it;
1938         DEBUG_r(PerlIO_printf(Perl_debug_log, "Contradicts stclass...\n"));
1939     }
1940     else {
1941         dontbother = 0;
1942         if (prog->float_substr != Nullsv || prog->float_utf8 != Nullsv) {
1943             /* Trim the end. */
1944             char *last;
1945             SV* float_real;
1946
1947             if (!(do_utf8 ? prog->float_utf8 : prog->float_substr))
1948                 do_utf8 ? to_utf8_substr(prog) : to_byte_substr(prog);
1949             float_real = do_utf8 ? prog->float_utf8 : prog->float_substr;
1950
1951             if (flags & REXEC_SCREAM) {
1952                 last = screaminstr(sv, float_real, s - strbeg,
1953                                    end_shift, &scream_pos, 1); /* last one */
1954                 if (!last)
1955                     last = scream_olds; /* Only one occurrence. */
1956                 /* we may be pointing at the wrong string */
1957                 else if (RX_MATCH_COPIED(prog))
1958                     s = prog->subbeg + (s - SvPVX(sv));
1959             }
1960             else {
1961                 STRLEN len;
1962                 char *little = SvPV(float_real, len);
1963
1964                 if (SvTAIL(float_real)) {
1965                     if (memEQ(strend - len + 1, little, len - 1))
1966                         last = strend - len + 1;
1967                     else if (!PL_multiline)
1968                         last = memEQ(strend - len, little, len)
1969                             ? strend - len : Nullch;
1970                     else
1971                         goto find_last;
1972                 } else {
1973                   find_last:
1974                     if (len)
1975                         last = rninstr(s, strend, little, little + len);
1976                     else
1977                         last = strend;  /* matching `$' */
1978                 }
1979             }
1980             if (last == NULL) {
1981                 DEBUG_r(PerlIO_printf(Perl_debug_log,
1982                                       "%sCan't trim the tail, match fails (should not happen)%s\n",
1983                                       PL_colors[4],PL_colors[5]));
1984                 goto phooey; /* Should not happen! */
1985             }
1986             dontbother = strend - last + prog->float_min_offset;
1987         }
1988         if (minlen && (dontbother < minlen))
1989             dontbother = minlen - 1;
1990         strend -= dontbother;              /* this one's always in bytes! */
1991         /* We don't know much -- general case. */
1992         if (do_utf8) {
1993             for (;;) {
1994                 if (regtry(prog, s))
1995                     goto got_it;
1996                 if (s >= strend)
1997                     break;
1998                 s += UTF8SKIP(s);
1999             };
2000         }
2001         else {
2002             do {
2003                 if (regtry(prog, s))
2004                     goto got_it;
2005             } while (s++ < strend);
2006         }
2007     }
2008
2009     /* Failure. */
2010     goto phooey;
2011
2012 got_it:
2013     RX_MATCH_TAINTED_set(prog, PL_reg_flags & RF_tainted);
2014
2015     if (PL_reg_eval_set) {
2016         /* Preserve the current value of $^R */
2017         if (oreplsv != GvSV(PL_replgv))
2018             sv_setsv(oreplsv, GvSV(PL_replgv));/* So that when GvSV(replgv) is
2019                                                   restored, the value remains
2020                                                   the same. */
2021         restore_pos(aTHX_ 0);
2022     }
2023
2024     /* make sure $`, $&, $', and $digit will work later */
2025     if ( !(flags & REXEC_NOT_FIRST) ) {
2026         if (RX_MATCH_COPIED(prog)) {
2027             Safefree(prog->subbeg);
2028             RX_MATCH_COPIED_off(prog);
2029         }
2030         if (flags & REXEC_COPY_STR) {
2031             I32 i = PL_regeol - startpos + (stringarg - strbeg);
2032
2033             s = savepvn(strbeg, i);
2034             prog->subbeg = s;
2035             prog->sublen = i;
2036             RX_MATCH_COPIED_on(prog);
2037         }
2038         else {
2039             prog->subbeg = strbeg;
2040             prog->sublen = PL_regeol - strbeg;  /* strend may have been modified */
2041         }
2042     }
2043
2044     return 1;
2045
2046 phooey:
2047     DEBUG_r(PerlIO_printf(Perl_debug_log, "%sMatch failed%s\n",
2048                           PL_colors[4],PL_colors[5]));
2049     if (PL_reg_eval_set)
2050         restore_pos(aTHX_ 0);
2051     return 0;
2052 }
2053
2054 /*
2055  - regtry - try match at specific point
2056  */
2057 STATIC I32                      /* 0 failure, 1 success */
2058 S_regtry(pTHX_ regexp *prog, char *startpos)
2059 {
2060     register I32 i;
2061     register I32 *sp;
2062     register I32 *ep;
2063     CHECKPOINT lastcp;
2064
2065 #ifdef DEBUGGING
2066     PL_regindent = 0;   /* XXXX Not good when matches are reenterable... */
2067 #endif
2068     if ((prog->reganch & ROPT_EVAL_SEEN) && !PL_reg_eval_set) {
2069         MAGIC *mg;
2070
2071         PL_reg_eval_set = RS_init;
2072         DEBUG_r(DEBUG_s(
2073             PerlIO_printf(Perl_debug_log, "  setting stack tmpbase at %"IVdf"\n",
2074                           (IV)(PL_stack_sp - PL_stack_base));
2075             ));
2076         SAVEI32(cxstack[cxstack_ix].blk_oldsp);
2077         cxstack[cxstack_ix].blk_oldsp = PL_stack_sp - PL_stack_base;
2078         /* Otherwise OP_NEXTSTATE will free whatever on stack now.  */
2079         SAVETMPS;
2080         /* Apparently this is not needed, judging by wantarray. */
2081         /* SAVEI8(cxstack[cxstack_ix].blk_gimme);
2082            cxstack[cxstack_ix].blk_gimme = G_SCALAR; */
2083
2084         if (PL_reg_sv) {
2085             /* Make $_ available to executed code. */
2086             if (PL_reg_sv != DEFSV) {
2087                 /* SAVE_DEFSV does *not* suffice here for USE_5005THREADS */
2088                 SAVESPTR(DEFSV);
2089                 DEFSV = PL_reg_sv;
2090             }
2091         
2092             if (!(SvTYPE(PL_reg_sv) >= SVt_PVMG && SvMAGIC(PL_reg_sv)
2093                   && (mg = mg_find(PL_reg_sv, PERL_MAGIC_regex_global)))) {
2094                 /* prepare for quick setting of pos */
2095                 sv_magic(PL_reg_sv, (SV*)0,
2096                         PERL_MAGIC_regex_global, Nullch, 0);
2097                 mg = mg_find(PL_reg_sv, PERL_MAGIC_regex_global);
2098                 mg->mg_len = -1;
2099             }
2100             PL_reg_magic    = mg;
2101             PL_reg_oldpos   = mg->mg_len;
2102             SAVEDESTRUCTOR_X(restore_pos, 0);
2103         }
2104         if (!PL_reg_curpm) {
2105             Newz(22,PL_reg_curpm, 1, PMOP);
2106 #ifdef USE_ITHREADS
2107             {
2108                 SV* repointer = newSViv(0);
2109                 /* so we know which PL_regex_padav element is PL_reg_curpm */
2110                 SvFLAGS(repointer) |= SVf_BREAK;
2111                 av_push(PL_regex_padav,repointer);
2112                 PL_reg_curpm->op_pmoffset = av_len(PL_regex_padav);
2113                 PL_regex_pad = AvARRAY(PL_regex_padav);
2114             }
2115 #endif      
2116         }
2117         PM_SETRE(PL_reg_curpm, prog);
2118         PL_reg_oldcurpm = PL_curpm;
2119         PL_curpm = PL_reg_curpm;
2120         if (RX_MATCH_COPIED(prog)) {
2121             /*  Here is a serious problem: we cannot rewrite subbeg,
2122                 since it may be needed if this match fails.  Thus
2123                 $` inside (?{}) could fail... */
2124             PL_reg_oldsaved = prog->subbeg;
2125             PL_reg_oldsavedlen = prog->sublen;
2126             RX_MATCH_COPIED_off(prog);
2127         }
2128         else
2129             PL_reg_oldsaved = Nullch;
2130         prog->subbeg = PL_bostr;
2131         prog->sublen = PL_regeol - PL_bostr; /* strend may have been modified */
2132     }
2133     prog->startp[0] = startpos - PL_bostr;
2134     PL_reginput = startpos;
2135     PL_regstartp = prog->startp;
2136     PL_regendp = prog->endp;
2137     PL_reglastparen = &prog->lastparen;
2138     PL_reglastcloseparen = &prog->lastcloseparen;
2139     prog->lastparen = 0;
2140     prog->lastcloseparen = 0;
2141     PL_regsize = 0;
2142     DEBUG_r(PL_reg_starttry = startpos);
2143     if (PL_reg_start_tmpl <= prog->nparens) {
2144         PL_reg_start_tmpl = prog->nparens*3/2 + 3;
2145         if(PL_reg_start_tmp)
2146             Renew(PL_reg_start_tmp, PL_reg_start_tmpl, char*);
2147         else
2148             New(22,PL_reg_start_tmp, PL_reg_start_tmpl, char*);
2149     }
2150
2151     /* XXXX What this code is doing here?!!!  There should be no need
2152        to do this again and again, PL_reglastparen should take care of
2153        this!  --ilya*/
2154
2155     /* Tests pat.t#187 and split.t#{13,14} seem to depend on this code.
2156      * Actually, the code in regcppop() (which Ilya may be meaning by
2157      * PL_reglastparen), is not needed at all by the test suite
2158      * (op/regexp, op/pat, op/split), but that code is needed, oddly
2159      * enough, for building DynaLoader, or otherwise this
2160      * "Error: '*' not in typemap in DynaLoader.xs, line 164"
2161      * will happen.  Meanwhile, this code *is* needed for the
2162      * above-mentioned test suite tests to succeed.  The common theme
2163      * on those tests seems to be returning null fields from matches.
2164      * --jhi */
2165 #if 1
2166     sp = prog->startp;
2167     ep = prog->endp;
2168     if (prog->nparens) {
2169         for (i = prog->nparens; i > (I32)*PL_reglastparen; i--) {
2170             *++sp = -1;
2171             *++ep = -1;
2172         }
2173     }
2174 #endif
2175     REGCP_SET(lastcp);
2176     if (regmatch(prog->program + 1)) {
2177         prog->endp[0] = PL_reginput - PL_bostr;
2178         return 1;
2179     }
2180     REGCP_UNWIND(lastcp);
2181     return 0;
2182 }
2183
2184 #define RE_UNWIND_BRANCH        1
2185 #define RE_UNWIND_BRANCHJ       2
2186
2187 union re_unwind_t;
2188
2189 typedef struct {                /* XX: makes sense to enlarge it... */
2190     I32 type;
2191     I32 prev;
2192     CHECKPOINT lastcp;
2193 } re_unwind_generic_t;
2194
2195 typedef struct {
2196     I32 type;
2197     I32 prev;
2198     CHECKPOINT lastcp;
2199     I32 lastparen;
2200     regnode *next;
2201     char *locinput;
2202     I32 nextchr;
2203 #ifdef DEBUGGING
2204     int regindent;
2205 #endif
2206 } re_unwind_branch_t;
2207
2208 typedef union re_unwind_t {
2209     I32 type;
2210     re_unwind_generic_t generic;
2211     re_unwind_branch_t branch;
2212 } re_unwind_t;
2213
2214 #define sayYES goto yes
2215 #define sayNO goto no
2216 #define sayNO_ANYOF goto no_anyof
2217 #define sayYES_FINAL goto yes_final
2218 #define sayYES_LOUD  goto yes_loud
2219 #define sayNO_FINAL  goto no_final
2220 #define sayNO_SILENT goto do_no
2221 #define saySAME(x) if (x) goto yes; else goto no
2222
2223 #define REPORT_CODE_OFF 24
2224
2225 /*
2226  - regmatch - main matching routine
2227  *
2228  * Conceptually the strategy is simple:  check to see whether the current
2229  * node matches, call self recursively to see whether the rest matches,
2230  * and then act accordingly.  In practice we make some effort to avoid
2231  * recursion, in particular by going through "ordinary" nodes (that don't
2232  * need to know whether the rest of the match failed) by a loop instead of
2233  * by recursion.
2234  */
2235 /* [lwall] I've hoisted the register declarations to the outer block in order to
2236  * maybe save a little bit of pushing and popping on the stack.  It also takes
2237  * advantage of machines that use a register save mask on subroutine entry.
2238  */
2239 STATIC I32                      /* 0 failure, 1 success */
2240 S_regmatch(pTHX_ regnode *prog)
2241 {
2242     register regnode *scan;     /* Current node. */
2243     regnode *next;              /* Next node. */
2244     regnode *inner;             /* Next node in internal branch. */
2245     register I32 nextchr;       /* renamed nextchr - nextchar colides with
2246                                    function of same name */
2247     register I32 n;             /* no or next */
2248     register I32 ln = 0;        /* len or last */
2249     register char *s = Nullch;  /* operand or save */
2250     register char *locinput = PL_reginput;
2251     register I32 c1 = 0, c2 = 0, paren; /* case fold search, parenth */
2252     int minmod = 0, sw = 0, logical = 0;
2253     I32 unwind = 0;
2254 #if 0
2255     I32 firstcp = PL_savestack_ix;
2256 #endif
2257     register bool do_utf8 = PL_reg_match_utf8;
2258 #ifdef DEBUGGING
2259     SV *dsv0 = PERL_DEBUG_PAD_ZERO(0);
2260     SV *dsv1 = PERL_DEBUG_PAD_ZERO(1);
2261     SV *dsv2 = PERL_DEBUG_PAD_ZERO(2);
2262 #endif
2263
2264 #ifdef DEBUGGING
2265     PL_regindent++;
2266 #endif
2267
2268     /* Note that nextchr is a byte even in UTF */
2269     nextchr = UCHARAT(locinput);
2270     scan = prog;
2271     while (scan != NULL) {
2272
2273         DEBUG_r( {
2274             SV *prop = sv_newmortal();
2275             int docolor = *PL_colors[0];
2276             int taill = (docolor ? 10 : 7); /* 3 chars for "> <" */
2277             int l = (PL_regeol - locinput) > taill ? taill : (PL_regeol - locinput);
2278             /* The part of the string before starttry has one color
2279                (pref0_len chars), between starttry and current
2280                position another one (pref_len - pref0_len chars),
2281                after the current position the third one.
2282                We assume that pref0_len <= pref_len, otherwise we
2283                decrease pref0_len.  */
2284             int pref_len = (locinput - PL_bostr) > (5 + taill) - l
2285                 ? (5 + taill) - l : locinput - PL_bostr;
2286             int pref0_len;
2287
2288             while (do_utf8 && UTF8_IS_CONTINUATION(*(U8*)(locinput - pref_len)))
2289                 pref_len++;
2290             pref0_len = pref_len  - (locinput - PL_reg_starttry);
2291             if (l + pref_len < (5 + taill) && l < PL_regeol - locinput)
2292                 l = ( PL_regeol - locinput > (5 + taill) - pref_len
2293                       ? (5 + taill) - pref_len : PL_regeol - locinput);
2294             while (do_utf8 && UTF8_IS_CONTINUATION(*(U8*)(locinput + l)))
2295                 l--;
2296             if (pref0_len < 0)
2297                 pref0_len = 0;
2298             if (pref0_len > pref_len)
2299                 pref0_len = pref_len;
2300             regprop(prop, scan);
2301             {
2302               char *s0 =
2303                 do_utf8 && OP(scan) != CANY ?
2304                 pv_uni_display(dsv0, (U8*)(locinput - pref_len),
2305                                pref0_len, 60, UNI_DISPLAY_REGEX) :
2306                 locinput - pref_len;
2307               int len0 = do_utf8 ? strlen(s0) : pref0_len;
2308               char *s1 = do_utf8 && OP(scan) != CANY ?
2309                 pv_uni_display(dsv1, (U8*)(locinput - pref_len + pref0_len),
2310                                pref_len - pref0_len, 60, UNI_DISPLAY_REGEX) :
2311                 locinput - pref_len + pref0_len;
2312               int len1 = do_utf8 ? strlen(s1) : pref_len - pref0_len;
2313               char *s2 = do_utf8 && OP(scan) != CANY ?
2314                 pv_uni_display(dsv2, (U8*)locinput,
2315                                PL_regeol - locinput, 60, UNI_DISPLAY_REGEX) :
2316                 locinput;
2317               int len2 = do_utf8 ? strlen(s2) : l;
2318               PerlIO_printf(Perl_debug_log,
2319                             "%4"IVdf" <%s%.*s%s%s%.*s%s%s%s%.*s%s>%*s|%3"IVdf":%*s%s\n",
2320                             (IV)(locinput - PL_bostr),
2321                             PL_colors[4],
2322                             len0, s0,
2323                             PL_colors[5],
2324                             PL_colors[2],
2325                             len1, s1,
2326                             PL_colors[3],
2327                             (docolor ? "" : "> <"),
2328                             PL_colors[0],
2329                             len2, s2,
2330                             PL_colors[1],
2331                             15 - l - pref_len + 1,
2332                             "",
2333                             (IV)(scan - PL_regprogram), PL_regindent*2, "",
2334                             SvPVX(prop));
2335             }
2336         });
2337
2338         next = scan + NEXT_OFF(scan);
2339         if (next == scan)
2340             next = NULL;
2341
2342         switch (OP(scan)) {
2343         case BOL:
2344             if (locinput == PL_bostr || (PL_multiline &&
2345                 (nextchr || locinput < PL_regeol) && locinput[-1] == '\n') )
2346             {
2347                 /* regtill = regbol; */
2348                 break;
2349             }
2350             sayNO;
2351         case MBOL:
2352             if (locinput == PL_bostr ||
2353                 ((nextchr || locinput < PL_regeol) && locinput[-1] == '\n'))
2354             {
2355                 break;
2356             }
2357             sayNO;
2358         case SBOL:
2359             if (locinput == PL_bostr)
2360                 break;
2361             sayNO;
2362         case GPOS:
2363             if (locinput == PL_reg_ganch)
2364                 break;
2365             sayNO;
2366         case EOL:
2367             if (PL_multiline)
2368                 goto meol;
2369             else
2370                 goto seol;
2371         case MEOL:
2372           meol:
2373             if ((nextchr || locinput < PL_regeol) && nextchr != '\n')
2374                 sayNO;
2375             break;
2376         case SEOL:
2377           seol:
2378             if ((nextchr || locinput < PL_regeol) && nextchr != '\n')
2379                 sayNO;
2380             if (PL_regeol - locinput > 1)
2381                 sayNO;
2382             break;
2383         case EOS:
2384             if (PL_regeol != locinput)
2385                 sayNO;
2386             break;
2387         case SANY:
2388             if (!nextchr && locinput >= PL_regeol)
2389                 sayNO;
2390             if (do_utf8) {
2391                 locinput += PL_utf8skip[nextchr];
2392                 if (locinput > PL_regeol)
2393                     sayNO;
2394                 nextchr = UCHARAT(locinput);
2395             }
2396             else
2397                 nextchr = UCHARAT(++locinput);
2398             break;
2399         case CANY:
2400             if (!nextchr && locinput >= PL_regeol)
2401                 sayNO;
2402             nextchr = UCHARAT(++locinput);
2403             break;
2404         case REG_ANY:
2405             if ((!nextchr && locinput >= PL_regeol) || nextchr == '\n')
2406                 sayNO;
2407             if (do_utf8) {
2408                 locinput += PL_utf8skip[nextchr];
2409                 if (locinput > PL_regeol)
2410                     sayNO;
2411                 nextchr = UCHARAT(locinput);
2412             }
2413             else
2414                 nextchr = UCHARAT(++locinput);
2415             break;
2416         case EXACT:
2417             s = STRING(scan);
2418             ln = STR_LEN(scan);
2419             if (do_utf8 != UTF) {
2420                 /* The target and the pattern have differing utf8ness. */
2421                 char *l = locinput;
2422                 char *e = s + ln;
2423                 STRLEN ulen;
2424
2425                 if (do_utf8) {
2426                     /* The target is utf8, the pattern is not utf8. */
2427                     while (s < e) {
2428                         if (l >= PL_regeol)
2429                              sayNO;
2430                         if (NATIVE_TO_UNI(*(U8*)s) !=
2431                             utf8n_to_uvuni((U8*)l, UTF8_MAXLEN, &ulen,
2432                                            ckWARN(WARN_UTF8) ?
2433                                            0 : UTF8_ALLOW_ANY))
2434                              sayNO;
2435                         l += ulen;
2436                         s ++;
2437                     }
2438                 }
2439                 else {
2440                     /* The target is not utf8, the pattern is utf8. */
2441                     while (s < e) {
2442                         if (l >= PL_regeol)
2443                             sayNO;
2444                         if (NATIVE_TO_UNI(*((U8*)l)) !=
2445                             utf8n_to_uvuni((U8*)s, UTF8_MAXLEN, &ulen,
2446                                            ckWARN(WARN_UTF8) ?
2447                                            0 : UTF8_ALLOW_ANY))
2448                             sayNO;
2449                         s += ulen;
2450                         l ++;
2451                     }
2452                 }
2453                 locinput = l;
2454                 nextchr = UCHARAT(locinput);
2455                 break;
2456             }
2457             /* The target and the pattern have the same utf8ness. */
2458             /* Inline the first character, for speed. */
2459             if (UCHARAT(s) != nextchr)
2460                 sayNO;
2461             if (PL_regeol - locinput < ln)
2462                 sayNO;
2463             if (ln > 1 && memNE(s, locinput, ln))
2464                 sayNO;
2465             locinput += ln;
2466             nextchr = UCHARAT(locinput);
2467             break;
2468         case EXACTFL:
2469             PL_reg_flags |= RF_tainted;
2470             /* FALL THROUGH */
2471         case EXACTF:
2472             s = STRING(scan);
2473             ln = STR_LEN(scan);
2474
2475             if (do_utf8 || UTF) {
2476               /* Either target or the pattern are utf8. */
2477                 char *l = locinput;
2478                 char *e = PL_regeol;
2479
2480                 if (ibcmp_utf8(s, 0,  ln, (bool)UTF,
2481                                l, &e, 0,  do_utf8)) {
2482                      /* One more case for the sharp s:
2483                       * pack("U0U*", 0xDF) =~ /ss/i,
2484                       * the 0xC3 0x9F are the UTF-8
2485                       * byte sequence for the U+00DF. */
2486                      if (!(do_utf8 &&
2487                            toLOWER(s[0]) == 's' &&
2488                            ln >= 2 &&
2489                            toLOWER(s[1]) == 's' &&
2490                            (U8)l[0] == 0xC3 &&
2491                            e - l >= 2 &&
2492                            (U8)l[1] == 0x9F))
2493                           sayNO;
2494                 }
2495                 locinput = e;
2496                 nextchr = UCHARAT(locinput);
2497                 break;
2498             }
2499
2500             /* Neither the target and the pattern are utf8. */
2501
2502             /* Inline the first character, for speed. */
2503             if (UCHARAT(s) != nextchr &&
2504                 UCHARAT(s) != ((OP(scan) == EXACTF)
2505                                ? PL_fold : PL_fold_locale)[nextchr])
2506                 sayNO;
2507             if (PL_regeol - locinput < ln)
2508                 sayNO;
2509             if (ln > 1 && (OP(scan) == EXACTF
2510                            ? ibcmp(s, locinput, ln)
2511                            : ibcmp_locale(s, locinput, ln)))
2512                 sayNO;
2513             locinput += ln;
2514             nextchr = UCHARAT(locinput);
2515             break;
2516         case ANYOF:
2517             if (do_utf8) {
2518                 STRLEN inclasslen = PL_regeol - locinput;
2519
2520                 if (!reginclass(scan, (U8*)locinput, &inclasslen, do_utf8))
2521                     sayNO_ANYOF;
2522                 if (locinput >= PL_regeol)
2523                     sayNO;
2524                 locinput += inclasslen ? inclasslen : UTF8SKIP(locinput);
2525                 nextchr = UCHARAT(locinput);
2526                 break;
2527             }
2528             else {
2529                 if (nextchr < 0)
2530                     nextchr = UCHARAT(locinput);
2531                 if (!REGINCLASS(scan, (U8*)locinput))
2532                     sayNO_ANYOF;
2533                 if (!nextchr && locinput >= PL_regeol)
2534                     sayNO;
2535                 nextchr = UCHARAT(++locinput);
2536                 break;
2537             }
2538         no_anyof:
2539             /* If we might have the case of the German sharp s
2540              * in a casefolding Unicode character class. */
2541
2542             if (ANYOF_FOLD_SHARP_S(scan, locinput, PL_regeol)) {
2543                  locinput += SHARP_S_SKIP;
2544                  nextchr = UCHARAT(locinput);
2545             }
2546             else
2547                  sayNO;
2548             break;
2549         case ALNUML:
2550             PL_reg_flags |= RF_tainted;
2551             /* FALL THROUGH */
2552         case ALNUM:
2553             if (!nextchr)
2554                 sayNO;
2555             if (do_utf8) {
2556                 LOAD_UTF8_CHARCLASS(alnum,"a");
2557                 if (!(OP(scan) == ALNUM
2558                       ? swash_fetch(PL_utf8_alnum, (U8*)locinput, do_utf8)
2559                       : isALNUM_LC_utf8((U8*)locinput)))
2560                 {
2561                     sayNO;
2562                 }
2563                 locinput += PL_utf8skip[nextchr];
2564                 nextchr = UCHARAT(locinput);
2565                 break;
2566             }
2567             if (!(OP(scan) == ALNUM
2568                   ? isALNUM(nextchr) : isALNUM_LC(nextchr)))
2569                 sayNO;
2570             nextchr = UCHARAT(++locinput);
2571             break;
2572         case NALNUML:
2573             PL_reg_flags |= RF_tainted;
2574             /* FALL THROUGH */
2575         case NALNUM:
2576             if (!nextchr && locinput >= PL_regeol)
2577                 sayNO;
2578             if (do_utf8) {
2579                 LOAD_UTF8_CHARCLASS(alnum,"a");
2580                 if (OP(scan) == NALNUM
2581                     ? swash_fetch(PL_utf8_alnum, (U8*)locinput, do_utf8)
2582                     : isALNUM_LC_utf8((U8*)locinput))
2583                 {
2584                     sayNO;
2585                 }
2586                 locinput += PL_utf8skip[nextchr];
2587                 nextchr = UCHARAT(locinput);
2588                 break;
2589             }
2590             if (OP(scan) == NALNUM
2591                 ? isALNUM(nextchr) : isALNUM_LC(nextchr))
2592                 sayNO;
2593             nextchr = UCHARAT(++locinput);
2594             break;
2595         case BOUNDL:
2596         case NBOUNDL:
2597             PL_reg_flags |= RF_tainted;
2598             /* FALL THROUGH */
2599         case BOUND:
2600         case NBOUND:
2601             /* was last char in word? */
2602             if (do_utf8) {
2603                 if (locinput == PL_bostr)
2604                     ln = '\n';
2605                 else {
2606                     U8 *r = reghop3((U8*)locinput, -1, (U8*)PL_bostr);
2607                 
2608                     ln = utf8n_to_uvchr(r, UTF8SKIP(r), 0, 0);
2609                 }
2610                 if (OP(scan) == BOUND || OP(scan) == NBOUND) {
2611                     ln = isALNUM_uni(ln);
2612                     LOAD_UTF8_CHARCLASS(alnum,"a");
2613                     n = swash_fetch(PL_utf8_alnum, (U8*)locinput, do_utf8);
2614                 }
2615                 else {
2616                     ln = isALNUM_LC_uvchr(UNI_TO_NATIVE(ln));
2617                     n = isALNUM_LC_utf8((U8*)locinput);
2618                 }
2619             }
2620             else {
2621                 ln = (locinput != PL_bostr) ?
2622                     UCHARAT(locinput - 1) : '\n';
2623                 if (OP(scan) == BOUND || OP(scan) == NBOUND) {
2624                     ln = isALNUM(ln);
2625                     n = isALNUM(nextchr);
2626                 }
2627                 else {
2628                     ln = isALNUM_LC(ln);
2629                     n = isALNUM_LC(nextchr);
2630                 }
2631             }
2632             if (((!ln) == (!n)) == (OP(scan) == BOUND ||
2633                                     OP(scan) == BOUNDL))
2634                     sayNO;
2635             break;
2636         case SPACEL:
2637             PL_reg_flags |= RF_tainted;
2638             /* FALL THROUGH */
2639         case SPACE:
2640             if (!nextchr)
2641                 sayNO;
2642             if (do_utf8) {
2643                 if (UTF8_IS_CONTINUED(nextchr)) {
2644                     LOAD_UTF8_CHARCLASS(space," ");
2645                     if (!(OP(scan) == SPACE
2646                           ? swash_fetch(PL_utf8_space, (U8*)locinput, do_utf8)
2647                           : isSPACE_LC_utf8((U8*)locinput)))
2648                     {
2649                         sayNO;
2650                     }
2651                     locinput += PL_utf8skip[nextchr];
2652                     nextchr = UCHARAT(locinput);
2653                     break;
2654                 }
2655                 if (!(OP(scan) == SPACE
2656                       ? isSPACE(nextchr) : isSPACE_LC(nextchr)))
2657                     sayNO;
2658                 nextchr = UCHARAT(++locinput);
2659             }
2660             else {
2661                 if (!(OP(scan) == SPACE
2662                       ? isSPACE(nextchr) : isSPACE_LC(nextchr)))
2663                     sayNO;
2664                 nextchr = UCHARAT(++locinput);
2665             }
2666             break;
2667         case NSPACEL:
2668             PL_reg_flags |= RF_tainted;
2669             /* FALL THROUGH */
2670         case NSPACE:
2671             if (!nextchr && locinput >= PL_regeol)
2672                 sayNO;
2673             if (do_utf8) {
2674                 LOAD_UTF8_CHARCLASS(space," ");
2675                 if (OP(scan) == NSPACE
2676                     ? swash_fetch(PL_utf8_space, (U8*)locinput, do_utf8)
2677                     : isSPACE_LC_utf8((U8*)locinput))
2678                 {
2679                     sayNO;
2680                 }
2681                 locinput += PL_utf8skip[nextchr];
2682                 nextchr = UCHARAT(locinput);
2683                 break;
2684             }
2685             if (OP(scan) == NSPACE
2686                 ? isSPACE(nextchr) : isSPACE_LC(nextchr))
2687                 sayNO;
2688             nextchr = UCHARAT(++locinput);
2689             break;
2690         case DIGITL:
2691             PL_reg_flags |= RF_tainted;
2692             /* FALL THROUGH */
2693         case DIGIT:
2694             if (!nextchr)
2695                 sayNO;
2696             if (do_utf8) {
2697                 LOAD_UTF8_CHARCLASS(digit,"0");
2698                 if (!(OP(scan) == DIGIT
2699                       ? swash_fetch(PL_utf8_digit, (U8*)locinput, do_utf8)
2700                       : isDIGIT_LC_utf8((U8*)locinput)))
2701                 {
2702                     sayNO;
2703                 }
2704                 locinput += PL_utf8skip[nextchr];
2705                 nextchr = UCHARAT(locinput);
2706                 break;
2707             }
2708             if (!(OP(scan) == DIGIT
2709                   ? isDIGIT(nextchr) : isDIGIT_LC(nextchr)))
2710                 sayNO;
2711             nextchr = UCHARAT(++locinput);
2712             break;
2713         case NDIGITL:
2714             PL_reg_flags |= RF_tainted;
2715             /* FALL THROUGH */
2716         case NDIGIT:
2717             if (!nextchr && locinput >= PL_regeol)
2718                 sayNO;
2719             if (do_utf8) {
2720                 LOAD_UTF8_CHARCLASS(digit,"0");
2721                 if (OP(scan) == NDIGIT
2722                     ? swash_fetch(PL_utf8_digit, (U8*)locinput, do_utf8)
2723                     : isDIGIT_LC_utf8((U8*)locinput))
2724                 {
2725                     sayNO;
2726                 }
2727                 locinput += PL_utf8skip[nextchr];
2728                 nextchr = UCHARAT(locinput);
2729                 break;
2730             }
2731             if (OP(scan) == NDIGIT
2732                 ? isDIGIT(nextchr) : isDIGIT_LC(nextchr))
2733                 sayNO;
2734             nextchr = UCHARAT(++locinput);
2735             break;
2736         case CLUMP:
2737             if (locinput >= PL_regeol)
2738                 sayNO;
2739             if  (do_utf8) {
2740                 LOAD_UTF8_CHARCLASS(mark,"~");
2741                 if (swash_fetch(PL_utf8_mark,(U8*)locinput, do_utf8))
2742                     sayNO;
2743                 locinput += PL_utf8skip[nextchr];
2744                 while (locinput < PL_regeol &&
2745                        swash_fetch(PL_utf8_mark,(U8*)locinput, do_utf8))
2746                     locinput += UTF8SKIP(locinput);
2747                 if (locinput > PL_regeol)
2748                     sayNO;
2749             } 
2750             else
2751                locinput++;
2752             nextchr = UCHARAT(locinput);
2753             break;
2754         case REFFL:
2755             PL_reg_flags |= RF_tainted;
2756             /* FALL THROUGH */
2757         case REF:
2758         case REFF:
2759             n = ARG(scan);  /* which paren pair */
2760             ln = PL_regstartp[n];
2761             PL_reg_leftiter = PL_reg_maxiter;           /* Void cache */
2762             if ((I32)*PL_reglastparen < n || ln == -1)
2763                 sayNO;                  /* Do not match unless seen CLOSEn. */
2764             if (ln == PL_regendp[n])
2765                 break;
2766
2767             s = PL_bostr + ln;
2768             if (do_utf8 && OP(scan) != REF) {   /* REF can do byte comparison */
2769                 char *l = locinput;
2770                 char *e = PL_bostr + PL_regendp[n];
2771                 /*
2772                  * Note that we can't do the "other character" lookup trick as
2773                  * in the 8-bit case (no pun intended) because in Unicode we
2774                  * have to map both upper and title case to lower case.
2775                  */
2776                 if (OP(scan) == REFF) {
2777                     STRLEN ulen1, ulen2;
2778                     U8 tmpbuf1[UTF8_MAXLEN_UCLC+1];
2779                     U8 tmpbuf2[UTF8_MAXLEN_UCLC+1];
2780                     while (s < e) {
2781                         if (l >= PL_regeol)
2782                             sayNO;
2783                         toLOWER_utf8((U8*)s, tmpbuf1, &ulen1);
2784                         toLOWER_utf8((U8*)l, tmpbuf2, &ulen2);
2785                         if (ulen1 != ulen2 || memNE((char *)tmpbuf1, (char *)tmpbuf2, ulen1))
2786                             sayNO;
2787                         s += ulen1;
2788                         l += ulen2;
2789                     }
2790                 }
2791                 locinput = l;
2792                 nextchr = UCHARAT(locinput);
2793                 break;
2794             }
2795
2796             /* Inline the first character, for speed. */
2797             if (UCHARAT(s) != nextchr &&
2798                 (OP(scan) == REF ||
2799                  (UCHARAT(s) != ((OP(scan) == REFF
2800                                   ? PL_fold : PL_fold_locale)[nextchr]))))
2801                 sayNO;
2802             ln = PL_regendp[n] - ln;
2803             if (locinput + ln > PL_regeol)
2804                 sayNO;
2805             if (ln > 1 && (OP(scan) == REF
2806                            ? memNE(s, locinput, ln)
2807                            : (OP(scan) == REFF
2808                               ? ibcmp(s, locinput, ln)
2809                               : ibcmp_locale(s, locinput, ln))))
2810                 sayNO;
2811             locinput += ln;
2812             nextchr = UCHARAT(locinput);
2813             break;
2814
2815         case NOTHING:
2816         case TAIL:
2817             break;
2818         case BACK:
2819             break;
2820         case EVAL:
2821         {
2822             dSP;
2823             OP_4tree *oop = PL_op;
2824             COP *ocurcop = PL_curcop;
2825             PAD *old_comppad;
2826             SV *ret;
2827         
2828             n = ARG(scan);
2829             PL_op = (OP_4tree*)PL_regdata->data[n];
2830             DEBUG_r( PerlIO_printf(Perl_debug_log, "  re_eval 0x%"UVxf"\n", PTR2UV(PL_op)) );
2831             PAD_SAVE_LOCAL(old_comppad, (PAD*)PL_regdata->data[n + 2]);
2832             PL_regendp[0] = PL_reg_magic->mg_len = locinput - PL_bostr;
2833
2834             {
2835                 SV **before = SP;
2836                 CALLRUNOPS(aTHX);                       /* Scalar context. */
2837                 SPAGAIN;
2838                 if (SP == before)
2839                     ret = &PL_sv_undef;   /* protect against empty (?{}) blocks. */
2840                 else {
2841                     ret = POPs;
2842                     PUTBACK;
2843                 }
2844             }
2845
2846             PL_op = oop;
2847             PAD_RESTORE_LOCAL(old_comppad);
2848             PL_curcop = ocurcop;
2849             if (logical) {
2850                 if (logical == 2) {     /* Postponed subexpression. */
2851                     regexp *re;
2852                     MAGIC *mg = Null(MAGIC*);
2853                     re_cc_state state;
2854                     CHECKPOINT cp, lastcp;
2855                     int toggleutf;
2856
2857                     if(SvROK(ret) || SvRMAGICAL(ret)) {
2858                         SV *sv = SvROK(ret) ? SvRV(ret) : ret;
2859
2860                         if(SvMAGICAL(sv))
2861                             mg = mg_find(sv, PERL_MAGIC_qr);
2862                     }
2863                     if (mg) {
2864                         re = (regexp *)mg->mg_obj;
2865                         (void)ReREFCNT_inc(re);
2866                     }
2867                     else {
2868                         STRLEN len;
2869                         char *t = SvPV(ret, len);
2870                         PMOP pm;
2871                         char *oprecomp = PL_regprecomp;
2872                         I32 osize = PL_regsize;
2873                         I32 onpar = PL_regnpar;
2874
2875                         Zero(&pm, 1, PMOP);
2876                         if (DO_UTF8(ret)) pm.op_pmdynflags |= PMdf_DYN_UTF8;
2877                         re = CALLREGCOMP(aTHX_ t, t + len, &pm);
2878                         if (!(SvFLAGS(ret)
2879                               & (SVs_TEMP | SVs_PADTMP | SVf_READONLY)))
2880                             sv_magic(ret,(SV*)ReREFCNT_inc(re),
2881                                         PERL_MAGIC_qr,0,0);
2882                         PL_regprecomp = oprecomp;
2883                         PL_regsize = osize;
2884                         PL_regnpar = onpar;
2885                     }
2886                     DEBUG_r(
2887                         PerlIO_printf(Perl_debug_log,
2888                                       "Entering embedded `%s%.60s%s%s'\n",
2889                                       PL_colors[0],
2890                                       re->precomp,
2891                                       PL_colors[1],
2892                                       (strlen(re->precomp) > 60 ? "..." : ""))
2893                         );
2894                     state.node = next;
2895                     state.prev = PL_reg_call_cc;
2896                     state.cc = PL_regcc;
2897                     state.re = PL_reg_re;
2898
2899                     PL_regcc = 0;
2900                 
2901                     cp = regcppush(0);  /* Save *all* the positions. */
2902                     REGCP_SET(lastcp);
2903                     cache_re(re);
2904                     state.ss = PL_savestack_ix;
2905                     *PL_reglastparen = 0;
2906                     *PL_reglastcloseparen = 0;
2907                     PL_reg_call_cc = &state;
2908                     PL_reginput = locinput;
2909                     toggleutf = ((PL_reg_flags & RF_utf8) != 0) ^
2910                                 ((re->reganch & ROPT_UTF8) != 0);
2911                     if (toggleutf) PL_reg_flags ^= RF_utf8;
2912
2913                     /* XXXX This is too dramatic a measure... */
2914                     PL_reg_maxiter = 0;
2915
2916                     if (regmatch(re->program + 1)) {
2917                         /* Even though we succeeded, we need to restore
2918                            global variables, since we may be wrapped inside
2919                            SUSPEND, thus the match may be not finished yet. */
2920
2921                         /* XXXX Do this only if SUSPENDed? */
2922                         PL_reg_call_cc = state.prev;
2923                         PL_regcc = state.cc;
2924                         PL_reg_re = state.re;
2925                         cache_re(PL_reg_re);
2926                         if (toggleutf) PL_reg_flags ^= RF_utf8;
2927
2928                         /* XXXX This is too dramatic a measure... */
2929                         PL_reg_maxiter = 0;
2930
2931                         /* These are needed even if not SUSPEND. */
2932                         ReREFCNT_dec(re);
2933                         regcpblow(cp);
2934                         sayYES;
2935                     }
2936                     ReREFCNT_dec(re);
2937                     REGCP_UNWIND(lastcp);
2938                     regcppop();
2939                     PL_reg_call_cc = state.prev;
2940                     PL_regcc = state.cc;
2941                     PL_reg_re = state.re;
2942                     cache_re(PL_reg_re);
2943                     if (toggleutf) PL_reg_flags ^= RF_utf8;
2944
2945                     /* XXXX This is too dramatic a measure... */
2946                     PL_reg_maxiter = 0;
2947
2948                     logical = 0;
2949                     sayNO;
2950                 }
2951                 sw = SvTRUE(ret);
2952                 logical = 0;
2953             }
2954             else
2955                 sv_setsv(save_scalar(PL_replgv), ret);
2956             break;
2957         }
2958         case OPEN:
2959             n = ARG(scan);  /* which paren pair */
2960             PL_reg_start_tmp[n] = locinput;
2961             if (n > PL_regsize)
2962                 PL_regsize = n;
2963             break;
2964         case CLOSE:
2965             n = ARG(scan);  /* which paren pair */
2966             PL_regstartp[n] = PL_reg_start_tmp[n] - PL_bostr;
2967             PL_regendp[n] = locinput - PL_bostr;
2968             if (n > (I32)*PL_reglastparen)
2969                 *PL_reglastparen = n;
2970             *PL_reglastcloseparen = n;
2971             break;
2972         case GROUPP:
2973             n = ARG(scan);  /* which paren pair */
2974             sw = ((I32)*PL_reglastparen >= n && PL_regendp[n] != -1);
2975             break;
2976         case IFTHEN:
2977             PL_reg_leftiter = PL_reg_maxiter;           /* Void cache */
2978             if (sw)
2979                 next = NEXTOPER(NEXTOPER(scan));
2980             else {
2981                 next = scan + ARG(scan);
2982                 if (OP(next) == IFTHEN) /* Fake one. */
2983                     next = NEXTOPER(NEXTOPER(next));
2984             }
2985             break;
2986         case LOGICAL:
2987             logical = scan->flags;
2988             break;
2989 /*******************************************************************
2990  PL_regcc contains infoblock about the innermost (...)* loop, and
2991  a pointer to the next outer infoblock.
2992
2993  Here is how Y(A)*Z is processed (if it is compiled into CURLYX/WHILEM):
2994
2995    1) After matching X, regnode for CURLYX is processed;
2996
2997    2) This regnode creates infoblock on the stack, and calls
2998       regmatch() recursively with the starting point at WHILEM node;
2999
3000    3) Each hit of WHILEM node tries to match A and Z (in the order
3001       depending on the current iteration, min/max of {min,max} and
3002       greediness).  The information about where are nodes for "A"
3003       and "Z" is read from the infoblock, as is info on how many times "A"
3004       was already matched, and greediness.
3005
3006    4) After A matches, the same WHILEM node is hit again.
3007
3008    5) Each time WHILEM is hit, PL_regcc is the infoblock created by CURLYX
3009       of the same pair.  Thus when WHILEM tries to match Z, it temporarily
3010       resets PL_regcc, since this Y(A)*Z can be a part of some other loop:
3011       as in (Y(A)*Z)*.  If Z matches, the automaton will hit the WHILEM node
3012       of the external loop.
3013
3014  Currently present infoblocks form a tree with a stem formed by PL_curcc
3015  and whatever it mentions via ->next, and additional attached trees
3016  corresponding to temporarily unset infoblocks as in "5" above.
3017
3018  In the following picture infoblocks for outer loop of
3019  (Y(A)*?Z)*?T are denoted O, for inner I.  NULL starting block
3020  is denoted by x.  The matched string is YAAZYAZT.  Temporarily postponed
3021  infoblocks are drawn below the "reset" infoblock.
3022
3023  In fact in the picture below we do not show failed matches for Z and T
3024  by WHILEM blocks.  [We illustrate minimal matches, since for them it is
3025  more obvious *why* one needs to *temporary* unset infoblocks.]
3026
3027   Matched       REx position    InfoBlocks      Comment
3028                 (Y(A)*?Z)*?T    x
3029                 Y(A)*?Z)*?T     x <- O
3030   Y             (A)*?Z)*?T      x <- O
3031   Y             A)*?Z)*?T       x <- O <- I
3032   YA            )*?Z)*?T        x <- O <- I
3033   YA            A)*?Z)*?T       x <- O <- I
3034   YAA           )*?Z)*?T        x <- O <- I
3035   YAA           Z)*?T           x <- O          # Temporary unset I
3036                                      I
3037
3038   YAAZ          Y(A)*?Z)*?T     x <- O
3039                                      I
3040
3041   YAAZY         (A)*?Z)*?T      x <- O
3042                                      I
3043
3044   YAAZY         A)*?Z)*?T       x <- O <- I
3045                                      I
3046
3047   YAAZYA        )*?Z)*?T        x <- O <- I     
3048                                      I
3049
3050   YAAZYA        Z)*?T           x <- O          # Temporary unset I
3051                                      I,I
3052
3053   YAAZYAZ       )*?T            x <- O
3054                                      I,I
3055
3056   YAAZYAZ       T               x               # Temporary unset O
3057                                 O
3058                                 I,I
3059
3060   YAAZYAZT                      x
3061                                 O
3062                                 I,I
3063  *******************************************************************/
3064         case CURLYX: {
3065                 CURCUR cc;
3066                 CHECKPOINT cp = PL_savestack_ix;
3067                 /* No need to save/restore up to this paren */
3068                 I32 parenfloor = scan->flags;
3069
3070                 if (OP(PREVOPER(next)) == NOTHING) /* LONGJMP */
3071                     next += ARG(next);
3072                 cc.oldcc = PL_regcc;
3073                 PL_regcc = &cc;
3074                 /* XXXX Probably it is better to teach regpush to support
3075                    parenfloor > PL_regsize... */
3076                 if (parenfloor > (I32)*PL_reglastparen)
3077                     parenfloor = *PL_reglastparen; /* Pessimization... */
3078                 cc.parenfloor = parenfloor;
3079                 cc.cur = -1;
3080                 cc.min = ARG1(scan);
3081                 cc.max  = ARG2(scan);
3082                 cc.scan = NEXTOPER(scan) + EXTRA_STEP_2ARGS;
3083                 cc.next = next;
3084                 cc.minmod = minmod;
3085                 cc.lastloc = 0;
3086                 PL_reginput = locinput;
3087                 n = regmatch(PREVOPER(next));   /* start on the WHILEM */
3088                 regcpblow(cp);
3089                 PL_regcc = cc.oldcc;
3090                 saySAME(n);
3091             }
3092             /* NOT REACHED */
3093         case WHILEM: {
3094                 /*
3095                  * This is really hard to understand, because after we match
3096                  * what we're trying to match, we must make sure the rest of
3097                  * the REx is going to match for sure, and to do that we have
3098                  * to go back UP the parse tree by recursing ever deeper.  And
3099                  * if it fails, we have to reset our parent's current state
3100                  * that we can try again after backing off.
3101                  */
3102
3103                 CHECKPOINT cp, lastcp;
3104                 CURCUR* cc = PL_regcc;
3105                 char *lastloc = cc->lastloc; /* Detection of 0-len. */
3106                 
3107                 n = cc->cur + 1;        /* how many we know we matched */
3108                 PL_reginput = locinput;
3109
3110                 DEBUG_r(
3111                     PerlIO_printf(Perl_debug_log,
3112                                   "%*s  %ld out of %ld..%ld  cc=%"UVxf"\n",
3113                                   REPORT_CODE_OFF+PL_regindent*2, "",
3114                                   (long)n, (long)cc->min,
3115                                   (long)cc->max, PTR2UV(cc))
3116                     );
3117
3118                 /* If degenerate scan matches "", assume scan done. */
3119
3120                 if (locinput == cc->lastloc && n >= cc->min) {
3121                     PL_regcc = cc->oldcc;
3122                     if (PL_regcc)
3123                         ln = PL_regcc->cur;
3124                     DEBUG_r(
3125                         PerlIO_printf(Perl_debug_log,
3126                            "%*s  empty match detected, try continuation...\n",
3127                            REPORT_CODE_OFF+PL_regindent*2, "")
3128                         );
3129                     if (regmatch(cc->next))
3130                         sayYES;
3131                     if (PL_regcc)
3132                         PL_regcc->cur = ln;
3133                     PL_regcc = cc;
3134                     sayNO;
3135                 }
3136
3137                 /* First just match a string of min scans. */
3138
3139                 if (n < cc->min) {
3140                     cc->cur = n;
3141                     cc->lastloc = locinput;
3142                     if (regmatch(cc->scan))
3143                         sayYES;
3144                     cc->cur = n - 1;
3145                     cc->lastloc = lastloc;
3146                     sayNO;
3147                 }
3148
3149                 if (scan->flags) {
3150                     /* Check whether we already were at this position.
3151                         Postpone detection until we know the match is not
3152                         *that* much linear. */
3153                 if (!PL_reg_maxiter) {
3154                     PL_reg_maxiter = (PL_regeol - PL_bostr + 1) * (scan->flags>>4);
3155                     PL_reg_leftiter = PL_reg_maxiter;
3156                 }
3157                 if (PL_reg_leftiter-- == 0) {
3158                     I32 size = (PL_reg_maxiter + 7)/8;
3159                     if (PL_reg_poscache) {
3160                         if ((I32)PL_reg_poscache_size < size) {
3161                             Renew(PL_reg_poscache, size, char);
3162                             PL_reg_poscache_size = size;
3163                         }
3164                         Zero(PL_reg_poscache, size, char);
3165                     }
3166                     else {
3167                         PL_reg_poscache_size = size;
3168                         Newz(29, PL_reg_poscache, size, char);
3169                     }
3170                     DEBUG_r(
3171                         PerlIO_printf(Perl_debug_log,
3172               "%sDetected a super-linear match, switching on caching%s...\n",
3173                                       PL_colors[4], PL_colors[5])
3174                         );
3175                 }
3176                 if (PL_reg_leftiter < 0) {
3177                     I32 o = locinput - PL_bostr, b;
3178
3179                     o = (scan->flags & 0xf) - 1 + o * (scan->flags>>4);
3180                     b = o % 8;
3181                     o /= 8;
3182                     if (PL_reg_poscache[o] & (1<<b)) {
3183                     DEBUG_r(
3184                         PerlIO_printf(Perl_debug_log,
3185                                       "%*s  already tried at this position...\n",
3186                                       REPORT_CODE_OFF+PL_regindent*2, "")
3187                         );
3188                         sayNO_SILENT;
3189                     }
3190                     PL_reg_poscache[o] |= (1<<b);
3191                 }
3192                 }
3193
3194                 /* Prefer next over scan for minimal matching. */
3195
3196                 if (cc->minmod) {
3197                     PL_regcc = cc->oldcc;
3198                     if (PL_regcc)
3199                         ln = PL_regcc->cur;
3200                     cp = regcppush(cc->parenfloor);
3201                     REGCP_SET(lastcp);
3202                     if (regmatch(cc->next)) {
3203                         regcpblow(cp);
3204                         sayYES; /* All done. */
3205                     }
3206                     REGCP_UNWIND(lastcp);
3207                     regcppop();
3208                     if (PL_regcc)
3209                         PL_regcc->cur = ln;
3210                     PL_regcc = cc;
3211
3212                     if (n >= cc->max) { /* Maximum greed exceeded? */
3213                         if (ckWARN(WARN_REGEXP) && n >= REG_INFTY
3214                             && !(PL_reg_flags & RF_warned)) {
3215                             PL_reg_flags |= RF_warned;
3216                             Perl_warner(aTHX_ packWARN(WARN_REGEXP), "%s limit (%d) exceeded",
3217                                  "Complex regular subexpression recursion",
3218                                  REG_INFTY - 1);
3219                         }
3220                         sayNO;
3221                     }
3222
3223                     DEBUG_r(
3224                         PerlIO_printf(Perl_debug_log,
3225                                       "%*s  trying longer...\n",
3226                                       REPORT_CODE_OFF+PL_regindent*2, "")
3227                         );
3228                     /* Try scanning more and see if it helps. */
3229                     PL_reginput = locinput;
3230                     cc->cur = n;
3231                     cc->lastloc = locinput;
3232                     cp = regcppush(cc->parenfloor);
3233                     REGCP_SET(lastcp);
3234                     if (regmatch(cc->scan)) {
3235                         regcpblow(cp);
3236                         sayYES;
3237                     }
3238                     REGCP_UNWIND(lastcp);
3239                     regcppop();
3240                     cc->cur = n - 1;
3241                     cc->lastloc = lastloc;
3242                     sayNO;
3243                 }
3244
3245                 /* Prefer scan over next for maximal matching. */
3246
3247                 if (n < cc->max) {      /* More greed allowed? */
3248                     cp = regcppush(cc->parenfloor);
3249                     cc->cur = n;
3250                     cc->lastloc = locinput;
3251                     REGCP_SET(lastcp);
3252                     if (regmatch(cc->scan)) {
3253                         regcpblow(cp);
3254                         sayYES;
3255                     }
3256                     REGCP_UNWIND(lastcp);
3257                     regcppop();         /* Restore some previous $<digit>s? */
3258                     PL_reginput = locinput;
3259                     DEBUG_r(
3260                         PerlIO_printf(Perl_debug_log,
3261                                       "%*s  failed, try continuation...\n",
3262                                       REPORT_CODE_OFF+PL_regindent*2, "")
3263                         );
3264                 }
3265                 if (ckWARN(WARN_REGEXP) && n >= REG_INFTY
3266                         && !(PL_reg_flags & RF_warned)) {
3267                     PL_reg_flags |= RF_warned;
3268                     Perl_warner(aTHX_ packWARN(WARN_REGEXP), "%s limit (%d) exceeded",
3269                          "Complex regular subexpression recursion",
3270                          REG_INFTY - 1);
3271                 }
3272
3273                 /* Failed deeper matches of scan, so see if this one works. */
3274                 PL_regcc = cc->oldcc;
3275                 if (PL_regcc)
3276                     ln = PL_regcc->cur;
3277                 if (regmatch(cc->next))
3278                     sayYES;
3279                 if (PL_regcc)
3280                     PL_regcc->cur = ln;
3281                 PL_regcc = cc;
3282                 cc->cur = n - 1;
3283                 cc->lastloc = lastloc;
3284                 sayNO;
3285             }
3286             /* NOT REACHED */
3287         case BRANCHJ:
3288             next = scan + ARG(scan);
3289             if (next == scan)
3290                 next = NULL;
3291             inner = NEXTOPER(NEXTOPER(scan));
3292             goto do_branch;
3293         case BRANCH:
3294             inner = NEXTOPER(scan);
3295           do_branch:
3296             {
3297                 c1 = OP(scan);
3298                 if (OP(next) != c1)     /* No choice. */
3299                     next = inner;       /* Avoid recursion. */
3300                 else {
3301                     I32 lastparen = *PL_reglastparen;
3302                     I32 unwind1;
3303                     re_unwind_branch_t *uw;
3304
3305                     /* Put unwinding data on stack */
3306                     unwind1 = SSNEWt(1,re_unwind_branch_t);
3307                     uw = SSPTRt(unwind1,re_unwind_branch_t);
3308                     uw->prev = unwind;
3309                     unwind = unwind1;
3310                     uw->type = ((c1 == BRANCH)
3311                                 ? RE_UNWIND_BRANCH
3312                                 : RE_UNWIND_BRANCHJ);
3313                     uw->lastparen = lastparen;
3314                     uw->next = next;
3315                     uw->locinput = locinput;
3316                     uw->nextchr = nextchr;
3317 #ifdef DEBUGGING
3318                     uw->regindent = ++PL_regindent;
3319 #endif
3320
3321                     REGCP_SET(uw->lastcp);
3322
3323                     /* Now go into the first branch */
3324                     next = inner;
3325                 }
3326             }
3327             break;
3328         case MINMOD:
3329             minmod = 1;
3330             break;
3331         case CURLYM:
3332         {
3333             I32 l = 0;
3334             CHECKPOINT lastcp;
3335         
3336             /* We suppose that the next guy does not need
3337                backtracking: in particular, it is of constant length,
3338                and has no parenths to influence future backrefs. */
3339             ln = ARG1(scan);  /* min to match */
3340             n  = ARG2(scan);  /* max to match */
3341             paren = scan->flags;
3342             if (paren) {
3343                 if (paren > PL_regsize)
3344                     PL_regsize = paren;
3345                 if (paren > (I32)*PL_reglastparen)
3346                     *PL_reglastparen = paren;
3347             }
3348             scan = NEXTOPER(scan) + NODE_STEP_REGNODE;
3349             if (paren)
3350                 scan += NEXT_OFF(scan); /* Skip former OPEN. */
3351             PL_reginput = locinput;
3352             if (minmod) {
3353                 minmod = 0;
3354                 if (ln && regrepeat_hard(scan, ln, &l) < ln)
3355                     sayNO;
3356                 /* if we matched something zero-length we don't need to
3357                    backtrack - capturing parens are already defined, so
3358                    the caveat in the maximal case doesn't apply
3359
3360                    XXXX if ln == 0, we can redo this check first time
3361                    through the following loop
3362                 */
3363                 if (ln && l == 0)
3364                     n = ln;     /* don't backtrack */
3365                 locinput = PL_reginput;
3366                 if (HAS_TEXT(next) || JUMPABLE(next)) {
3367                     regnode *text_node = next;
3368
3369                     if (! HAS_TEXT(text_node)) FIND_NEXT_IMPT(text_node);
3370
3371                     if (! HAS_TEXT(text_node)) c1 = c2 = -1000;
3372                     else {
3373                         if (PL_regkind[(U8)OP(text_node)] == REF) {
3374                             I32 n, ln;
3375                             n = ARG(text_node);  /* which paren pair */
3376                             ln = PL_regstartp[n];
3377                             /* assume yes if we haven't seen CLOSEn */
3378                             if (
3379                                 (I32)*PL_reglastparen < n ||
3380                                 ln == -1 ||
3381                                 ln == PL_regendp[n]
3382                             ) {
3383                                 c1 = c2 = -1000;
3384                                 goto assume_ok_MM;
3385                             }
3386                             c1 = *(PL_bostr + ln);
3387                         }
3388                         else { c1 = (U8)*STRING(text_node); }
3389                         if (OP(text_node) == EXACTF || OP(text_node) == REFF)
3390                             c2 = PL_fold[c1];
3391                         else if (OP(text_node) == EXACTFL || OP(text_node) == REFFL)
3392                             c2 = PL_fold_locale[c1];
3393                         else
3394                             c2 = c1;
3395                     }
3396                 }
3397                 else
3398                     c1 = c2 = -1000;
3399             assume_ok_MM:
3400                 REGCP_SET(lastcp);
3401                 /* This may be improved if l == 0.  */
3402                 while (n >= ln || (n == REG_INFTY && ln > 0 && l)) { /* ln overflow ? */
3403                     /* If it could work, try it. */
3404                     if (c1 == -1000 ||
3405                         UCHARAT(PL_reginput) == c1 ||
3406                         UCHARAT(PL_reginput) == c2)
3407                     {
3408                         if (paren) {
3409                             if (ln) {
3410                                 PL_regstartp[paren] =
3411                                     HOPc(PL_reginput, -l) - PL_bostr;
3412                                 PL_regendp[paren] = PL_reginput - PL_bostr;
3413                             }
3414                             else
3415                                 PL_regendp[paren] = -1;
3416                         }
3417                         if (regmatch(next))
3418                             sayYES;
3419                         REGCP_UNWIND(lastcp);
3420                     }
3421                     /* Couldn't or didn't -- move forward. */
3422                     PL_reginput = locinput;
3423                     if (regrepeat_hard(scan, 1, &l)) {
3424                         ln++;
3425                         locinput = PL_reginput;
3426                     }
3427                     else
3428                         sayNO;
3429                 }
3430             }
3431             else {
3432                 n = regrepeat_hard(scan, n, &l);
3433                 /* if we matched something zero-length we don't need to
3434                    backtrack, unless the minimum count is zero and we
3435                    are capturing the result - in that case the capture
3436                    being defined or not may affect later execution
3437                 */
3438                 if (n != 0 && l == 0 && !(paren && ln == 0))
3439                     ln = n;     /* don't backtrack */
3440                 locinput = PL_reginput;
3441                 DEBUG_r(
3442                     PerlIO_printf(Perl_debug_log,
3443                                   "%*s  matched %"IVdf" times, len=%"IVdf"...\n",
3444                                   (int)(REPORT_CODE_OFF+PL_regindent*2), "",
3445                                   (IV) n, (IV)l)
3446                     );
3447                 if (n >= ln) {
3448                     if (HAS_TEXT(next) || JUMPABLE(next)) {
3449                         regnode *text_node = next;
3450
3451                         if (! HAS_TEXT(text_node)) FIND_NEXT_IMPT(text_node);
3452
3453                         if (! HAS_TEXT(text_node)) c1 = c2 = -1000;
3454                         else {
3455                             if (PL_regkind[(U8)OP(text_node)] == REF) {
3456                                 I32 n, ln;
3457                                 n = ARG(text_node);  /* which paren pair */
3458                                 ln = PL_regstartp[n];
3459                                 /* assume yes if we haven't seen CLOSEn */
3460                                 if (
3461                                     (I32)*PL_reglastparen < n ||
3462                                     ln == -1 ||
3463                                     ln == PL_regendp[n]
3464                                 ) {
3465                                     c1 = c2 = -1000;
3466                                     goto assume_ok_REG;
3467                                 }
3468                                 c1 = *(PL_bostr + ln);
3469                             }
3470                             else { c1 = (U8)*STRING(text_node); }
3471
3472                             if (OP(text_node) == EXACTF || OP(text_node) == REFF)
3473                                 c2 = PL_fold[c1];
3474                             else if (OP(text_node) == EXACTFL || OP(text_node) == REFFL)
3475                                 c2 = PL_fold_locale[c1];
3476                             else
3477                                 c2 = c1;
3478                         }
3479                     }
3480                     else
3481                         c1 = c2 = -1000;
3482                 }
3483             assume_ok_REG:
3484                 REGCP_SET(lastcp);
3485                 while (n >= ln) {
3486                     /* If it could work, try it. */
3487                     if (c1 == -1000 ||
3488                         UCHARAT(PL_reginput) == c1 ||
3489                         UCHARAT(PL_reginput) == c2)
3490                     {
3491                         DEBUG_r(
3492                                 PerlIO_printf(Perl_debug_log,
3493                                               "%*s  trying tail with n=%"IVdf"...\n",
3494                                               (int)(REPORT_CODE_OFF+PL_regindent*2), "", (IV)n)
3495                             );
3496                         if (paren) {
3497                             if (n) {
3498                                 PL_regstartp[paren] = HOPc(PL_reginput, -l) - PL_bostr;
3499                                 PL_regendp[paren] = PL_reginput - PL_bostr;
3500                             }
3501                             else
3502                                 PL_regendp[paren] = -1;
3503                         }
3504                         if (regmatch(next))
3505                             sayYES;
3506                         REGCP_UNWIND(lastcp);
3507                     }
3508                     /* Couldn't or didn't -- back up. */
3509                     n--;
3510                     locinput = HOPc(locinput, -l);
3511                     PL_reginput = locinput;
3512                 }
3513             }
3514             sayNO;
3515             break;
3516         }
3517         case CURLYN:
3518             paren = scan->flags;        /* Which paren to set */
3519             if (paren > PL_regsize)
3520                 PL_regsize = paren;
3521             if (paren > (I32)*PL_reglastparen)
3522                 *PL_reglastparen = paren;
3523             ln = ARG1(scan);  /* min to match */
3524             n  = ARG2(scan);  /* max to match */
3525             scan = regnext(NEXTOPER(scan) + NODE_STEP_REGNODE);
3526             goto repeat;
3527         case CURLY:
3528             paren = 0;
3529             ln = ARG1(scan);  /* min to match */
3530             n  = ARG2(scan);  /* max to match */
3531             scan = NEXTOPER(scan) + NODE_STEP_REGNODE;
3532             goto repeat;
3533         case STAR:
3534             ln = 0;
3535             n = REG_INFTY;
3536             scan = NEXTOPER(scan);
3537             paren = 0;
3538             goto repeat;
3539         case PLUS:
3540             ln = 1;
3541             n = REG_INFTY;
3542             scan = NEXTOPER(scan);
3543             paren = 0;
3544           repeat:
3545             /*
3546             * Lookahead to avoid useless match attempts
3547             * when we know what character comes next.
3548             */
3549
3550             /*
3551             * Used to only do .*x and .*?x, but now it allows
3552             * for )'s, ('s and (?{ ... })'s to be in the way
3553             * of the quantifier and the EXACT-like node.  -- japhy
3554             */
3555
3556             if (HAS_TEXT(next) || JUMPABLE(next)) {
3557                 U8 *s;
3558                 regnode *text_node = next;
3559
3560                 if (! HAS_TEXT(text_node)) FIND_NEXT_IMPT(text_node);
3561
3562                 if (! HAS_TEXT(text_node)) c1 = c2 = -1000;
3563                 else {
3564                     if (PL_regkind[(U8)OP(text_node)] == REF) {
3565                         I32 n, ln;
3566                         n = ARG(text_node);  /* which paren pair */
3567                         ln = PL_regstartp[n];
3568                         /* assume yes if we haven't seen CLOSEn */
3569                         if (
3570                             (I32)*PL_reglastparen < n ||
3571                             ln == -1 ||
3572                             ln == PL_regendp[n]
3573                         ) {
3574                             c1 = c2 = -1000;
3575                             goto assume_ok_easy;
3576                         }
3577                         s = (U8*)PL_bostr + ln;
3578                     }
3579                     else { s = (U8*)STRING(text_node); }
3580
3581                     if (!UTF) {
3582                         c2 = c1 = *s;
3583                         if (OP(text_node) == EXACTF || OP(text_node) == REFF)
3584                             c2 = PL_fold[c1];
3585                         else if (OP(text_node) == EXACTFL || OP(text_node) == REFFL)
3586                             c2 = PL_fold_locale[c1];
3587                     }
3588                     else { /* UTF */
3589                         if (OP(text_node) == EXACTF || OP(text_node) == REFF) {
3590                              STRLEN ulen1, ulen2;
3591                              U8 tmpbuf1[UTF8_MAXLEN_UCLC+1];
3592                              U8 tmpbuf2[UTF8_MAXLEN_UCLC+1];
3593
3594                              to_utf8_lower((U8*)s, tmpbuf1, &ulen1);
3595                              to_utf8_upper((U8*)s, tmpbuf2, &ulen2);
3596
3597                              c1 = utf8n_to_uvuni(tmpbuf1, UTF8_MAXLEN, 0,
3598                                                  ckWARN(WARN_UTF8) ?
3599                                                  0 : UTF8_ALLOW_ANY);
3600                              c2 = utf8n_to_uvuni(tmpbuf2, UTF8_MAXLEN, 0,
3601                                                  ckWARN(WARN_UTF8) ?
3602                                                  0 : UTF8_ALLOW_ANY);
3603                         }
3604                         else {
3605                             c2 = c1 = utf8n_to_uvchr(s, UTF8_MAXLEN, 0,
3606                                                      ckWARN(WARN_UTF8) ?
3607                                                      0 : UTF8_ALLOW_ANY);
3608                         }
3609                     }
3610                 }
3611             }
3612             else
3613                 c1 = c2 = -1000;
3614         assume_ok_easy:
3615             PL_reginput = locinput;
3616             if (minmod) {
3617                 CHECKPOINT lastcp;
3618                 minmod = 0;
3619                 if (ln && regrepeat(scan, ln) < ln)
3620                     sayNO;
3621                 locinput = PL_reginput;
3622                 REGCP_SET(lastcp);
3623                 if (c1 != -1000) {
3624                     char *e; /* Should not check after this */
3625                     char *old = locinput;
3626                     int count = 0;
3627
3628                     if  (n == REG_INFTY) {
3629                         e = PL_regeol - 1;
3630                         if (do_utf8)
3631                             while (UTF8_IS_CONTINUATION(*(U8*)e))
3632                                 e--;
3633                     }
3634                     else if (do_utf8) {
3635                         int m = n - ln;
3636                         for (e = locinput;
3637                              m >0 && e + UTF8SKIP(e) <= PL_regeol; m--)
3638                             e += UTF8SKIP(e);
3639                     }
3640                     else {
3641                         e = locinput + n - ln;
3642                         if (e >= PL_regeol)
3643                             e = PL_regeol - 1;
3644                     }
3645                     while (1) {
3646                         /* Find place 'next' could work */
3647                         if (!do_utf8) {
3648                             if (c1 == c2) {
3649                                 while (locinput <= e &&
3650                                        UCHARAT(locinput) != c1)
3651                                     locinput++;
3652                             } else {
3653                                 while (locinput <= e
3654                                        && UCHARAT(locinput) != c1
3655                                        && UCHARAT(locinput) != c2)
3656                                     locinput++;
3657                             }
3658                             count = locinput - old;
3659                         }
3660                         else {
3661                             STRLEN len;
3662                             if (c1 == c2) {
3663                                 /* count initialised to
3664                                  * utf8_distance(old, locinput) */
3665                                 while (locinput <= e &&
3666                                        utf8n_to_uvchr((U8*)locinput,
3667                                                       UTF8_MAXLEN, &len,
3668                                                       ckWARN(WARN_UTF8) ?
3669                                                       0 : UTF8_ALLOW_ANY) != (UV)c1) {
3670                                     locinput += len;
3671                                     count++;
3672                                 }
3673                             } else {
3674                                 /* count initialised to
3675                                  * utf8_distance(old, locinput) */
3676                                 while (locinput <= e) {
3677                                     UV c = utf8n_to_uvchr((U8*)locinput,
3678                                                           UTF8_MAXLEN, &len,
3679                                                           ckWARN(WARN_UTF8) ?
3680                                                           0 : UTF8_ALLOW_ANY);
3681                                     if (c == (UV)c1 || c == (UV)c2)
3682                                         break;
3683                                     locinput += len;
3684                                     count++;
3685                                 }
3686                             }
3687                         }
3688                         if (locinput > e)
3689                             sayNO;
3690                         /* PL_reginput == old now */
3691                         if (locinput != old) {
3692                             ln = 1;     /* Did some */
3693                             if (regrepeat(scan, count) < count)
3694                                 sayNO;
3695                         }
3696                         /* PL_reginput == locinput now */
3697                         TRYPAREN(paren, ln, locinput);
3698                         PL_reginput = locinput; /* Could be reset... */
3699                         REGCP_UNWIND(lastcp);
3700                         /* Couldn't or didn't -- move forward. */
3701                         old = locinput;
3702                         if (do_utf8)
3703                             locinput += UTF8SKIP(locinput);
3704                         else
3705                             locinput++;
3706                         count = 1;
3707                     }
3708                 }
3709                 else
3710                 while (n >= ln || (n == REG_INFTY && ln > 0)) { /* ln overflow ? */
3711                     UV c;
3712                     if (c1 != -1000) {
3713                         if (do_utf8)
3714                             c = utf8n_to_uvchr((U8*)PL_reginput,
3715                                                UTF8_MAXLEN, 0,
3716                                                ckWARN(WARN_UTF8) ?
3717                                                0 : UTF8_ALLOW_ANY);
3718                         else
3719                             c = UCHARAT(PL_reginput);
3720                         /* If it could work, try it. */
3721                         if (c == (UV)c1 || c == (UV)c2)
3722                         {
3723                             TRYPAREN(paren, ln, PL_reginput);
3724                             REGCP_UNWIND(lastcp);
3725                         }
3726                     }
3727                     /* If it could work, try it. */
3728                     else if (c1 == -1000)
3729                     {
3730                         TRYPAREN(paren, ln, PL_reginput);
3731                         REGCP_UNWIND(lastcp);
3732                     }
3733                     /* Couldn't or didn't -- move forward. */
3734                     PL_reginput = locinput;
3735                     if (regrepeat(scan, 1)) {
3736                         ln++;
3737                         locinput = PL_reginput;
3738                     }
3739                     else
3740                         sayNO;
3741                 }
3742             }
3743             else {
3744                 CHECKPOINT lastcp;
3745                 n = regrepeat(scan, n);
3746                 locinput = PL_reginput;
3747                 if (ln < n && PL_regkind[(U8)OP(next)] == EOL &&
3748                     ((!PL_multiline && OP(next) != MEOL) ||
3749                         OP(next) == SEOL || OP(next) == EOS))
3750                 {
3751                     ln = n;                     /* why back off? */
3752                     /* ...because $ and \Z can match before *and* after
3753                        newline at the end.  Consider "\n\n" =~ /\n+\Z\n/.
3754                        We should back off by one in this case. */
3755                     if (UCHARAT(PL_reginput - 1) == '\n' && OP(next) != EOS)
3756                         ln--;
3757                 }
3758                 REGCP_SET(lastcp);
3759                 if (paren) {
3760                     UV c = 0;
3761                     while (n >= ln) {
3762                         if (c1 != -1000) {
3763                             if (do_utf8)
3764                                 c = utf8n_to_uvchr((U8*)PL_reginput,
3765                                                    UTF8_MAXLEN, 0,
3766                                                    ckWARN(WARN_UTF8) ?
3767                                                    0 : UTF8_ALLOW_ANY);
3768                             else
3769                                 c = UCHARAT(PL_reginput);
3770                         }
3771                         /* If it could work, try it. */
3772                         if (c1 == -1000 || c == (UV)c1 || c == (UV)c2)
3773                             {
3774                                 TRYPAREN(paren, n, PL_reginput);
3775                                 REGCP_UNWIND(lastcp);
3776                             }
3777                         /* Couldn't or didn't -- back up. */
3778                         n--;
3779                         PL_reginput = locinput = HOPc(locinput, -1);
3780                     }
3781                 }
3782                 else {
3783                     UV c = 0;
3784                     while (n >= ln) {
3785                         if (c1 != -1000) {
3786                             if (do_utf8)
3787                                 c = utf8n_to_uvchr((U8*)PL_reginput,
3788                                                    UTF8_MAXLEN, 0,
3789                                                    ckWARN(WARN_UTF8) ?
3790                                                    0 : UTF8_ALLOW_ANY);
3791                             else
3792                                 c = UCHARAT(PL_reginput);
3793                         }
3794                         /* If it could work, try it. */
3795                         if (c1 == -1000 || c == (UV)c1 || c == (UV)c2)
3796                             {
3797                                 TRYPAREN(paren, n, PL_reginput);
3798                                 REGCP_UNWIND(lastcp);
3799                             }
3800                         /* Couldn't or didn't -- back up. */
3801                         n--;
3802                         PL_reginput = locinput = HOPc(locinput, -1);
3803                     }
3804                 }
3805             }
3806             sayNO;
3807             break;
3808         case END:
3809             if (PL_reg_call_cc) {
3810                 re_cc_state *cur_call_cc = PL_reg_call_cc;
3811                 CURCUR *cctmp = PL_regcc;
3812                 regexp *re = PL_reg_re;
3813                 CHECKPOINT cp, lastcp;
3814                 
3815                 cp = regcppush(0);      /* Save *all* the positions. */
3816                 REGCP_SET(lastcp);
3817                 regcp_set_to(PL_reg_call_cc->ss); /* Restore parens of
3818                                                     the caller. */
3819                 PL_reginput = locinput; /* Make position available to
3820                                            the callcc. */
3821                 cache_re(PL_reg_call_cc->re);
3822                 PL_regcc = PL_reg_call_cc->cc;
3823                 PL_reg_call_cc = PL_reg_call_cc->prev;
3824                 if (regmatch(cur_call_cc->node)) {
3825                     PL_reg_call_cc = cur_call_cc;
3826                     regcpblow(cp);
3827                     sayYES;
3828                 }
3829                 REGCP_UNWIND(lastcp);
3830                 regcppop();
3831                 PL_reg_call_cc = cur_call_cc;
3832                 PL_regcc = cctmp;
3833                 PL_reg_re = re;
3834                 cache_re(re);
3835
3836