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