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