This is a live mirror of the Perl 5 development currently hosted at https://github.com/perl/perl5
Change sprintf() to my_sprintf(), and use the returned length from
[perl5.git] / regexec.c
CommitLineData
a0d0e21e
LW
1/* regexec.c
2 */
3
4/*
5 * "One Ring to rule them all, One Ring to find them..."
6 */
7
61296642
DM
8/* This file contains functions for executing a regular expression. See
9 * also regcomp.c which funnily enough, contains functions for compiling
166f8a29 10 * a regular expression.
e4a054ea
DM
11 *
12 * This file is also copied at build time to ext/re/re_exec.c, where
13 * it's built with -DPERL_EXT_RE_BUILD -DPERL_EXT_RE_DEBUG -DPERL_EXT.
14 * This causes the main functions to be compiled under new names and with
15 * debugging support added, which makes "use re 'debug'" work.
166f8a29
DM
16 */
17
a687059c
LW
18/* NOTE: this is derived from Henry Spencer's regexp code, and should not
19 * confused with the original package (see point 3 below). Thanks, Henry!
20 */
21
22/* Additional note: this code is very heavily munged from Henry's version
23 * in places. In some spots I've traded clarity for efficiency, so don't
24 * blame Henry for some of the lack of readability.
25 */
26
e50aee73
AD
27/* The names of the functions have been changed from regcomp and
28 * regexec to pregcomp and pregexec in order to avoid conflicts
29 * with the POSIX routines of the same names.
30*/
31
b9d5759e 32#ifdef PERL_EXT_RE_BUILD
54df2634 33#include "re_top.h"
9041c2e3 34#endif
56953603 35
a687059c 36/*
e50aee73 37 * pregcomp and pregexec -- regsub and regerror are not used in perl
a687059c
LW
38 *
39 * Copyright (c) 1986 by University of Toronto.
40 * Written by Henry Spencer. Not derived from licensed software.
41 *
42 * Permission is granted to anyone to use this software for any
43 * purpose on any computer system, and to redistribute it freely,
44 * subject to the following restrictions:
45 *
46 * 1. The author is not responsible for the consequences of use of
47 * this software, no matter how awful, even if they arise
48 * from defects in it.
49 *
50 * 2. The origin of this software must not be misrepresented, either
51 * by explicit claim or by omission.
52 *
53 * 3. Altered versions must be plainly marked as such, and must not
54 * be misrepresented as being the original software.
55 *
56 **** Alterations to Henry's code are...
57 ****
4bb101f2 58 **** Copyright (C) 1991, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999,
b94e2f88 59 **** 2000, 2001, 2002, 2003, 2004, 2005, 2006, by Larry Wall and others
a687059c 60 ****
9ef589d8
LW
61 **** You may distribute under the terms of either the GNU General Public
62 **** License or the Artistic License, as specified in the README file.
a687059c
LW
63 *
64 * Beware that some of this code is subtly aware of the way operator
65 * precedence is structured in regular expressions. Serious changes in
66 * regular-expression syntax might require a total rethink.
67 */
68#include "EXTERN.h"
864dbfa3 69#define PERL_IN_REGEXEC_C
a687059c 70#include "perl.h"
0f5d15d6 71
54df2634
NC
72#ifdef PERL_IN_XSUB_RE
73# include "re_comp.h"
74#else
75# include "regcomp.h"
76#endif
a687059c 77
c277df42
IZ
78#define RF_tainted 1 /* tainted information used? */
79#define RF_warned 2 /* warned about big count? */
faec1544 80
ab3bbdeb 81#define RF_utf8 8 /* Pattern contains multibyte chars? */
a0ed51b3 82
eb160463 83#define UTF ((PL_reg_flags & RF_utf8) != 0)
ce862d02
IZ
84
85#define RS_init 1 /* eval environment created */
86#define RS_set 2 /* replsv value is set */
c277df42 87
a687059c
LW
88#ifndef STATIC
89#define STATIC static
90#endif
91
32fc9b6a 92#define REGINCLASS(prog,p,c) (ANYOF_FLAGS(p) ? reginclass(prog,p,c,0,0) : ANYOF_BITMAP_TEST(p,*(c)))
7d3e948e 93
c277df42
IZ
94/*
95 * Forwards.
96 */
97
33b8afdf 98#define CHR_SVLEN(sv) (do_utf8 ? sv_len_utf8(sv) : SvCUR(sv))
53c4c00c 99#define CHR_DIST(a,b) (PL_reg_match_utf8 ? utf8_distance(a,b) : a - b)
a0ed51b3 100
3dab1dad
YO
101#define HOPc(pos,off) \
102 (char *)(PL_reg_match_utf8 \
52657f30 103 ? reghop3((U8*)pos, off, (U8*)(off >= 0 ? PL_regeol : PL_bostr)) \
3dab1dad
YO
104 : (U8*)(pos + off))
105#define HOPBACKc(pos, off) \
07be1b83
YO
106 (char*)(PL_reg_match_utf8\
107 ? reghopmaybe3((U8*)pos, -off, (U8*)PL_bostr) \
108 : (pos - off >= PL_bostr) \
8e11feef 109 ? (U8*)pos - off \
3dab1dad 110 : NULL)
efb30f32 111
e7409c1b 112#define HOP3(pos,off,lim) (PL_reg_match_utf8 ? reghop3((U8*)(pos), off, (U8*)(lim)) : (U8*)(pos + off))
1aa99e6b 113#define HOP3c(pos,off,lim) ((char*)HOP3(pos,off,lim))
1aa99e6b 114
1a4fad37
AL
115#define LOAD_UTF8_CHARCLASS(class,str) STMT_START { \
116 if (!CAT2(PL_utf8_,class)) { bool ok; ENTER; save_re_context(); ok=CAT2(is_utf8_,class)((const U8*)str); assert(ok); LEAVE; } } STMT_END
117#define LOAD_UTF8_CHARCLASS_ALNUM() LOAD_UTF8_CHARCLASS(alnum,"a")
118#define LOAD_UTF8_CHARCLASS_DIGIT() LOAD_UTF8_CHARCLASS(digit,"0")
119#define LOAD_UTF8_CHARCLASS_SPACE() LOAD_UTF8_CHARCLASS(space," ")
120#define LOAD_UTF8_CHARCLASS_MARK() LOAD_UTF8_CHARCLASS(mark, "\xcd\x86")
51371543 121
3dab1dad
YO
122/* TODO: Combine JUMPABLE and HAS_TEXT to cache OP(rn) */
123
5f80c4cf 124/* for use after a quantifier and before an EXACT-like node -- japhy */
e2d8ce26
JP
125#define JUMPABLE(rn) ( \
126 OP(rn) == OPEN || OP(rn) == CLOSE || OP(rn) == EVAL || \
cca55fe3
JP
127 OP(rn) == SUSPEND || OP(rn) == IFMATCH || \
128 OP(rn) == PLUS || OP(rn) == MINMOD || \
3dab1dad 129 (PL_regkind[OP(rn)] == CURLY && ARG1(rn) > 0) \
e2d8ce26
JP
130)
131
cca55fe3 132#define HAS_TEXT(rn) ( \
3dab1dad 133 PL_regkind[OP(rn)] == EXACT || PL_regkind[OP(rn)] == REF \
cca55fe3 134)
e2d8ce26 135
a84d97b6
HS
136/*
137 Search for mandatory following text node; for lookahead, the text must
138 follow but for lookbehind (rn->flags != 0) we skip to the next step.
139*/
cca55fe3 140#define FIND_NEXT_IMPT(rn) STMT_START { \
3dab1dad
YO
141 while (JUMPABLE(rn)) { \
142 const OPCODE type = OP(rn); \
143 if (type == SUSPEND || PL_regkind[type] == CURLY) \
e2d8ce26 144 rn = NEXTOPER(NEXTOPER(rn)); \
3dab1dad 145 else if (type == PLUS) \
cca55fe3 146 rn = NEXTOPER(rn); \
3dab1dad 147 else if (type == IFMATCH) \
a84d97b6 148 rn = (rn->flags == 0) ? NEXTOPER(NEXTOPER(rn)) : rn + ARG(rn); \
e2d8ce26 149 else rn += NEXT_OFF(rn); \
3dab1dad 150 } \
5f80c4cf 151} STMT_END
74750237 152
c476f425 153
acfe0abc 154static void restore_pos(pTHX_ void *arg);
51371543 155
76e3520e 156STATIC CHECKPOINT
cea2e8a9 157S_regcppush(pTHX_ I32 parenfloor)
a0d0e21e 158{
97aff369 159 dVAR;
a3b680e6 160 const int retval = PL_savestack_ix;
b1ce53c5 161#define REGCP_PAREN_ELEMS 4
a3b680e6 162 const int paren_elems_to_push = (PL_regsize - parenfloor) * REGCP_PAREN_ELEMS;
a0d0e21e 163 int p;
40a82448 164 GET_RE_DEBUG_FLAGS_DECL;
a0d0e21e 165
e49a9654
IH
166 if (paren_elems_to_push < 0)
167 Perl_croak(aTHX_ "panic: paren_elems_to_push < 0");
168
6bda09f9 169#define REGCP_OTHER_ELEMS 8
4b3c1a47 170 SSGROW(paren_elems_to_push + REGCP_OTHER_ELEMS);
3280af22 171 for (p = PL_regsize; p > parenfloor; p--) {
b1ce53c5 172/* REGCP_PARENS_ELEMS are pushed per pairs of parentheses. */
cf93c79d
IZ
173 SSPUSHINT(PL_regendp[p]);
174 SSPUSHINT(PL_regstartp[p]);
3280af22 175 SSPUSHPTR(PL_reg_start_tmp[p]);
a0d0e21e 176 SSPUSHINT(p);
40a82448
DM
177 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
178 " saving \\%"UVuf" %"IVdf"(%"IVdf")..%"IVdf"\n",
179 (UV)p, (IV)PL_regstartp[p],
180 (IV)(PL_reg_start_tmp[p] - PL_bostr),
181 (IV)PL_regendp[p]
182 ));
a0d0e21e 183 }
b1ce53c5 184/* REGCP_OTHER_ELEMS are pushed in any case, parentheses or no. */
6bda09f9
YO
185 SSPUSHPTR(PL_regstartp);
186 SSPUSHPTR(PL_regendp);
3280af22
NIS
187 SSPUSHINT(PL_regsize);
188 SSPUSHINT(*PL_reglastparen);
a01268b5 189 SSPUSHINT(*PL_reglastcloseparen);
3280af22 190 SSPUSHPTR(PL_reginput);
41123dfd
JH
191#define REGCP_FRAME_ELEMS 2
192/* REGCP_FRAME_ELEMS are part of the REGCP_OTHER_ELEMS and
193 * are needed for the regexp context stack bookkeeping. */
194 SSPUSHINT(paren_elems_to_push + REGCP_OTHER_ELEMS - REGCP_FRAME_ELEMS);
b1ce53c5 195 SSPUSHINT(SAVEt_REGCONTEXT); /* Magic cookie. */
41123dfd 196
a0d0e21e
LW
197 return retval;
198}
199
c277df42 200/* These are needed since we do not localize EVAL nodes: */
ab3bbdeb
YO
201#define REGCP_SET(cp) \
202 DEBUG_STATE_r( \
ab3bbdeb 203 PerlIO_printf(Perl_debug_log, \
e4f74956 204 " Setting an EVAL scope, savestack=%"IVdf"\n", \
ab3bbdeb
YO
205 (IV)PL_savestack_ix)); \
206 cp = PL_savestack_ix
c3464db5 207
ab3bbdeb 208#define REGCP_UNWIND(cp) \
e4f74956 209 DEBUG_STATE_r( \
ab3bbdeb 210 if (cp != PL_savestack_ix) \
e4f74956
YO
211 PerlIO_printf(Perl_debug_log, \
212 " Clearing an EVAL scope, savestack=%"IVdf"..%"IVdf"\n", \
ab3bbdeb
YO
213 (IV)(cp), (IV)PL_savestack_ix)); \
214 regcpblow(cp)
c277df42 215
76e3520e 216STATIC char *
097eb12c 217S_regcppop(pTHX_ const regexp *rex)
a0d0e21e 218{
97aff369 219 dVAR;
b1ce53c5 220 I32 i;
a0d0e21e 221 char *input;
b1ce53c5 222
a3621e74
YO
223 GET_RE_DEBUG_FLAGS_DECL;
224
b1ce53c5 225 /* Pop REGCP_OTHER_ELEMS before the parentheses loop starts. */
a0d0e21e 226 i = SSPOPINT;
b1ce53c5
JH
227 assert(i == SAVEt_REGCONTEXT); /* Check that the magic cookie is there. */
228 i = SSPOPINT; /* Parentheses elements to pop. */
a0d0e21e 229 input = (char *) SSPOPPTR;
a01268b5 230 *PL_reglastcloseparen = SSPOPINT;
3280af22
NIS
231 *PL_reglastparen = SSPOPINT;
232 PL_regsize = SSPOPINT;
6bda09f9
YO
233 PL_regendp=(I32 *) SSPOPPTR;
234 PL_regstartp=(I32 *) SSPOPPTR;
b1ce53c5 235
6bda09f9 236
b1ce53c5 237 /* Now restore the parentheses context. */
41123dfd
JH
238 for (i -= (REGCP_OTHER_ELEMS - REGCP_FRAME_ELEMS);
239 i > 0; i -= REGCP_PAREN_ELEMS) {
1df70142 240 I32 tmps;
097eb12c 241 U32 paren = (U32)SSPOPINT;
3280af22 242 PL_reg_start_tmp[paren] = (char *) SSPOPPTR;
cf93c79d
IZ
243 PL_regstartp[paren] = SSPOPINT;
244 tmps = SSPOPINT;
3280af22
NIS
245 if (paren <= *PL_reglastparen)
246 PL_regendp[paren] = tmps;
a3621e74 247 DEBUG_EXECUTE_r(
c3464db5 248 PerlIO_printf(Perl_debug_log,
b900a521 249 " restoring \\%"UVuf" to %"IVdf"(%"IVdf")..%"IVdf"%s\n",
9041c2e3 250 (UV)paren, (IV)PL_regstartp[paren],
b900a521 251 (IV)(PL_reg_start_tmp[paren] - PL_bostr),
9041c2e3 252 (IV)PL_regendp[paren],
3280af22 253 (paren > *PL_reglastparen ? "(no)" : ""));
c277df42 254 );
a0d0e21e 255 }
a3621e74 256 DEBUG_EXECUTE_r(
bb7a0f54 257 if (*PL_reglastparen + 1 <= rex->nparens) {
c3464db5 258 PerlIO_printf(Perl_debug_log,
faccc32b 259 " restoring \\%"IVdf"..\\%"IVdf" to undef\n",
4f639d21 260 (IV)(*PL_reglastparen + 1), (IV)rex->nparens);
c277df42
IZ
261 }
262 );
daf18116 263#if 1
dafc8851
JH
264 /* It would seem that the similar code in regtry()
265 * already takes care of this, and in fact it is in
266 * a better location to since this code can #if 0-ed out
267 * but the code in regtry() is needed or otherwise tests
268 * requiring null fields (pat.t#187 and split.t#{13,14}
daf18116
JH
269 * (as of patchlevel 7877) will fail. Then again,
270 * this code seems to be necessary or otherwise
271 * building DynaLoader will fail:
272 * "Error: '*' not in typemap in DynaLoader.xs, line 164"
273 * --jhi */
bb7a0f54 274 for (i = *PL_reglastparen + 1; (U32)i <= rex->nparens; i++) {
097eb12c
AL
275 if (i > PL_regsize)
276 PL_regstartp[i] = -1;
277 PL_regendp[i] = -1;
a0d0e21e 278 }
dafc8851 279#endif
a0d0e21e
LW
280 return input;
281}
282
02db2b7b 283#define regcpblow(cp) LEAVE_SCOPE(cp) /* Ignores regcppush()ed data. */
a0d0e21e 284
a687059c 285/*
e50aee73 286 * pregexec and friends
a687059c
LW
287 */
288
76234dfb 289#ifndef PERL_IN_XSUB_RE
a687059c 290/*
c277df42 291 - pregexec - match a regexp against a string
a687059c 292 */
c277df42 293I32
864dbfa3 294Perl_pregexec(pTHX_ register regexp *prog, char *stringarg, register char *strend,
c3464db5 295 char *strbeg, I32 minend, SV *screamer, U32 nosave)
c277df42
IZ
296/* strend: pointer to null at end of string */
297/* strbeg: real beginning of string */
298/* minend: end of match must be >=minend after stringarg. */
299/* nosave: For optimizations. */
300{
301 return
9041c2e3 302 regexec_flags(prog, stringarg, strend, strbeg, minend, screamer, NULL,
c277df42
IZ
303 nosave ? 0 : REXEC_COPY_STR);
304}
76234dfb 305#endif
22e551b9 306
9041c2e3 307/*
cad2e5aa
JH
308 * Need to implement the following flags for reg_anch:
309 *
310 * USE_INTUIT_NOML - Useful to call re_intuit_start() first
311 * USE_INTUIT_ML
312 * INTUIT_AUTORITATIVE_NOML - Can trust a positive answer
313 * INTUIT_AUTORITATIVE_ML
314 * INTUIT_ONCE_NOML - Intuit can match in one location only.
315 * INTUIT_ONCE_ML
316 *
317 * Another flag for this function: SECOND_TIME (so that float substrs
318 * with giant delta may be not rechecked).
319 */
320
321/* Assumptions: if ANCH_GPOS, then strpos is anchored. XXXX Check GPOS logic */
322
3f7c398e 323/* If SCREAM, then SvPVX_const(sv) should be compatible with strpos and strend.
cad2e5aa
JH
324 Otherwise, only SvCUR(sv) is used to get strbeg. */
325
326/* XXXX We assume that strpos is strbeg unless sv. */
327
6eb5f6b9
JH
328/* XXXX Some places assume that there is a fixed substring.
329 An update may be needed if optimizer marks as "INTUITable"
330 RExen without fixed substrings. Similarly, it is assumed that
331 lengths of all the strings are no more than minlen, thus they
332 cannot come from lookahead.
333 (Or minlen should take into account lookahead.) */
334
2c2d71f5
JH
335/* A failure to find a constant substring means that there is no need to make
336 an expensive call to REx engine, thus we celebrate a failure. Similarly,
337 finding a substring too deep into the string means that less calls to
30944b6d
IZ
338 regtry() should be needed.
339
340 REx compiler's optimizer found 4 possible hints:
341 a) Anchored substring;
342 b) Fixed substring;
343 c) Whether we are anchored (beginning-of-line or \G);
344 d) First node (of those at offset 0) which may distingush positions;
6eb5f6b9 345 We use a)b)d) and multiline-part of c), and try to find a position in the
30944b6d
IZ
346 string which does not contradict any of them.
347 */
2c2d71f5 348
6eb5f6b9
JH
349/* Most of decisions we do here should have been done at compile time.
350 The nodes of the REx which we used for the search should have been
351 deleted from the finite automaton. */
352
cad2e5aa
JH
353char *
354Perl_re_intuit_start(pTHX_ regexp *prog, SV *sv, char *strpos,
355 char *strend, U32 flags, re_scream_pos_data *data)
356{
97aff369 357 dVAR;
b7953727 358 register I32 start_shift = 0;
cad2e5aa 359 /* Should be nonnegative! */
b7953727 360 register I32 end_shift = 0;
2c2d71f5
JH
361 register char *s;
362 register SV *check;
a1933d95 363 char *strbeg;
cad2e5aa 364 char *t;
1de06328 365 const bool do_utf8 = (sv && SvUTF8(sv)) ? 1 : 0; /* if no sv we have to assume bytes */
cad2e5aa 366 I32 ml_anch;
bd61b366
SS
367 register char *other_last = NULL; /* other substr checked before this */
368 char *check_at = NULL; /* check substr found at this pos */
1df70142 369 const I32 multiline = prog->reganch & PMf_MULTILINE;
30944b6d 370#ifdef DEBUGGING
890ce7af 371 const char * const i_strpos = strpos;
30944b6d 372#endif
a3621e74
YO
373
374 GET_RE_DEBUG_FLAGS_DECL;
375
a30b2f1f 376 RX_MATCH_UTF8_set(prog,do_utf8);
cad2e5aa 377
b8d68ded 378 if (prog->reganch & ROPT_UTF8) {
b8d68ded
JH
379 PL_reg_flags |= RF_utf8;
380 }
ab3bbdeb
YO
381 DEBUG_EXECUTE_r(
382 debug_start_match(prog, do_utf8, strpos, strend,
1de06328
YO
383 sv ? "Guessing start of match in sv for"
384 : "Guessing start of match in string for");
2a782b5b 385 );
cad2e5aa 386
c344f387
JH
387 /* CHR_DIST() would be more correct here but it makes things slow. */
388 if (prog->minlen > strend - strpos) {
a3621e74 389 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
a72c7584 390 "String too short... [re_intuit_start]\n"));
cad2e5aa 391 goto fail;
2c2d71f5 392 }
1de06328 393
a1933d95 394 strbeg = (sv && SvPOK(sv)) ? strend - SvCUR(sv) : strpos;
1aa99e6b 395 PL_regeol = strend;
33b8afdf
JH
396 if (do_utf8) {
397 if (!prog->check_utf8 && prog->check_substr)
398 to_utf8_substr(prog);
399 check = prog->check_utf8;
400 } else {
401 if (!prog->check_substr && prog->check_utf8)
402 to_byte_substr(prog);
403 check = prog->check_substr;
404 }
1de06328 405 if (check == &PL_sv_undef) {
a3621e74 406 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
1de06328 407 "Non-utf8 string cannot match utf8 check string\n"));
33b8afdf
JH
408 goto fail;
409 }
2c2d71f5 410 if (prog->reganch & ROPT_ANCH) { /* Match at beg-of-str or after \n */
cad2e5aa
JH
411 ml_anch = !( (prog->reganch & ROPT_ANCH_SINGLE)
412 || ( (prog->reganch & ROPT_ANCH_BOL)
7fba1cd6 413 && !multiline ) ); /* Check after \n? */
cad2e5aa 414
7e25d62c
JH
415 if (!ml_anch) {
416 if ( !(prog->reganch & (ROPT_ANCH_GPOS /* Checked by the caller */
417 | ROPT_IMPLICIT)) /* not a real BOL */
3f7c398e 418 /* SvCUR is not set on references: SvRV and SvPVX_const overlap */
7e25d62c
JH
419 && sv && !SvROK(sv)
420 && (strpos != strbeg)) {
a3621e74 421 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "Not at start...\n"));
7e25d62c
JH
422 goto fail;
423 }
424 if (prog->check_offset_min == prog->check_offset_max &&
cce850e4 425 !(prog->reganch & ROPT_CANY_SEEN)) {
2c2d71f5 426 /* Substring at constant offset from beg-of-str... */
cad2e5aa
JH
427 I32 slen;
428
1aa99e6b 429 s = HOP3c(strpos, prog->check_offset_min, strend);
1de06328 430
653099ff
GS
431 if (SvTAIL(check)) {
432 slen = SvCUR(check); /* >= 1 */
cad2e5aa 433
9041c2e3 434 if ( strend - s > slen || strend - s < slen - 1
2c2d71f5 435 || (strend - s == slen && strend[-1] != '\n')) {
a3621e74 436 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "String too long...\n"));
2c2d71f5 437 goto fail_finish;
cad2e5aa
JH
438 }
439 /* Now should match s[0..slen-2] */
440 slen--;
3f7c398e 441 if (slen && (*SvPVX_const(check) != *s
cad2e5aa 442 || (slen > 1
3f7c398e 443 && memNE(SvPVX_const(check), s, slen)))) {
2c2d71f5 444 report_neq:
a3621e74 445 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "String not equal...\n"));
2c2d71f5
JH
446 goto fail_finish;
447 }
cad2e5aa 448 }
3f7c398e 449 else if (*SvPVX_const(check) != *s
653099ff 450 || ((slen = SvCUR(check)) > 1
3f7c398e 451 && memNE(SvPVX_const(check), s, slen)))
2c2d71f5 452 goto report_neq;
c315bfe8 453 check_at = s;
2c2d71f5 454 goto success_at_start;
7e25d62c 455 }
cad2e5aa 456 }
2c2d71f5 457 /* Match is anchored, but substr is not anchored wrt beg-of-str. */
cad2e5aa 458 s = strpos;
2c2d71f5 459 start_shift = prog->check_offset_min; /* okay to underestimate on CC */
1de06328
YO
460 end_shift = prog->check_end_shift;
461
2c2d71f5 462 if (!ml_anch) {
a3b680e6 463 const I32 end = prog->check_offset_max + CHR_SVLEN(check)
653099ff 464 - (SvTAIL(check) != 0);
a3b680e6 465 const I32 eshift = CHR_DIST((U8*)strend, (U8*)s) - end;
2c2d71f5
JH
466
467 if (end_shift < eshift)
468 end_shift = eshift;
469 }
cad2e5aa 470 }
2c2d71f5 471 else { /* Can match at random position */
cad2e5aa
JH
472 ml_anch = 0;
473 s = strpos;
1de06328
YO
474 start_shift = prog->check_offset_min; /* okay to underestimate on CC */
475 end_shift = prog->check_end_shift;
476
477 /* end shift should be non negative here */
cad2e5aa
JH
478 }
479
2c2d71f5 480#ifdef DEBUGGING /* 7/99: reports of failure (with the older version) */
0033605d 481 if (end_shift < 0)
1de06328 482 Perl_croak(aTHX_ "panic: end_shift: %"IVdf" pattern:\n%s\n ",
b57a0404 483 (IV)end_shift, prog->precomp);
2c2d71f5
JH
484#endif
485
2c2d71f5
JH
486 restart:
487 /* Find a possible match in the region s..strend by looking for
488 the "check" substring in the region corrected by start/end_shift. */
1de06328
YO
489
490 {
491 I32 srch_start_shift = start_shift;
492 I32 srch_end_shift = end_shift;
493 if (srch_start_shift < 0 && strbeg - s > srch_start_shift) {
494 srch_end_shift -= ((strbeg - s) - srch_start_shift);
495 srch_start_shift = strbeg - s;
496 }
6bda09f9 497 DEBUG_OPTIMISE_MORE_r({
1de06328
YO
498 PerlIO_printf(Perl_debug_log, "Check offset min: %"IVdf" Start shift: %"IVdf" End shift %"IVdf" Real End Shift: %"IVdf"\n",
499 (IV)prog->check_offset_min,
500 (IV)srch_start_shift,
501 (IV)srch_end_shift,
502 (IV)prog->check_end_shift);
503 });
504
cad2e5aa 505 if (flags & REXEC_SCREAM) {
cad2e5aa 506 I32 p = -1; /* Internal iterator of scream. */
a3b680e6 507 I32 * const pp = data ? data->scream_pos : &p;
cad2e5aa 508
2c2d71f5
JH
509 if (PL_screamfirst[BmRARE(check)] >= 0
510 || ( BmRARE(check) == '\n'
511 && (BmPREVIOUS(check) == SvCUR(check) - 1)
512 && SvTAIL(check) ))
9041c2e3 513 s = screaminstr(sv, check,
1de06328 514 srch_start_shift + (s - strbeg), srch_end_shift, pp, 0);
cad2e5aa 515 else
2c2d71f5 516 goto fail_finish;
4addbd3b
HS
517 /* we may be pointing at the wrong string */
518 if (s && RX_MATCH_COPIED(prog))
3f7c398e 519 s = strbeg + (s - SvPVX_const(sv));
cad2e5aa
JH
520 if (data)
521 *data->scream_olds = s;
522 }
1de06328
YO
523 else {
524 U8* start_point;
525 U8* end_point;
526 if (prog->reganch & ROPT_CANY_SEEN) {
527 start_point= (U8*)(s + srch_start_shift);
528 end_point= (U8*)(strend - srch_end_shift);
529 } else {
530 start_point= HOP3(s, srch_start_shift, srch_start_shift < 0 ? strbeg : strend);
531 end_point= HOP3(strend, -srch_end_shift, strbeg);
532 }
6bda09f9 533 DEBUG_OPTIMISE_MORE_r({
56570a2c 534 PerlIO_printf(Perl_debug_log, "fbm_instr len=%d str=<%.*s>\n",
1de06328 535 (int)(end_point - start_point),
fc8cd66c 536 (int)(end_point - start_point) > 20 ? 20 : (int)(end_point - start_point),
1de06328
YO
537 start_point);
538 });
539
540 s = fbm_instr( start_point, end_point,
7fba1cd6 541 check, multiline ? FBMrf_MULTILINE : 0);
1de06328
YO
542 }
543 }
cad2e5aa
JH
544 /* Update the count-of-usability, remove useless subpatterns,
545 unshift s. */
2c2d71f5 546
ab3bbdeb
YO
547 DEBUG_EXECUTE_r({
548 RE_PV_QUOTED_DECL(quoted, do_utf8, PERL_DEBUG_PAD_ZERO(0),
549 SvPVX_const(check), RE_SV_DUMPLEN(check), 30);
550 PerlIO_printf(Perl_debug_log, "%s %s substr %s%s%s",
2c2d71f5 551 (s ? "Found" : "Did not find"),
ab3bbdeb
YO
552 (check == (do_utf8 ? prog->anchored_utf8 : prog->anchored_substr)
553 ? "anchored" : "floating"),
554 quoted,
555 RE_SV_TAIL(check),
556 (s ? " at offset " : "...\n") );
557 });
2c2d71f5
JH
558
559 if (!s)
560 goto fail_finish;
2c2d71f5 561 /* Finish the diagnostic message */
a3621e74 562 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "%ld...\n", (long)(s - i_strpos)) );
2c2d71f5 563
1de06328
YO
564 /* XXX dmq: first branch is for positive lookbehind...
565 Our check string is offset from the beginning of the pattern.
566 So we need to do any stclass tests offset forward from that
567 point. I think. :-(
568 */
569
570
571
572 check_at=s;
573
574
2c2d71f5
JH
575 /* Got a candidate. Check MBOL anchoring, and the *other* substr.
576 Start with the other substr.
577 XXXX no SCREAM optimization yet - and a very coarse implementation
a0288114 578 XXXX /ttx+/ results in anchored="ttx", floating="x". floating will
2c2d71f5
JH
579 *always* match. Probably should be marked during compile...
580 Probably it is right to do no SCREAM here...
581 */
582
1de06328
YO
583 if (do_utf8 ? (prog->float_utf8 && prog->anchored_utf8)
584 : (prog->float_substr && prog->anchored_substr))
585 {
30944b6d 586 /* Take into account the "other" substring. */
2c2d71f5
JH
587 /* XXXX May be hopelessly wrong for UTF... */
588 if (!other_last)
6eb5f6b9 589 other_last = strpos;
33b8afdf 590 if (check == (do_utf8 ? prog->float_utf8 : prog->float_substr)) {
30944b6d
IZ
591 do_other_anchored:
592 {
890ce7af
AL
593 char * const last = HOP3c(s, -start_shift, strbeg);
594 char *last1, *last2;
be8e71aa 595 char * const saved_s = s;
33b8afdf 596 SV* must;
2c2d71f5 597
2c2d71f5
JH
598 t = s - prog->check_offset_max;
599 if (s - strpos > prog->check_offset_max /* signed-corrected t > strpos */
1d86a7f9 600 && (!do_utf8
0ce71af7 601 || ((t = (char*)reghopmaybe3((U8*)s, -(prog->check_offset_max), (U8*)strpos))
2c2d71f5 602 && t > strpos)))
6f207bd3 603 NOOP;
2c2d71f5
JH
604 else
605 t = strpos;
1aa99e6b 606 t = HOP3c(t, prog->anchored_offset, strend);
6eb5f6b9
JH
607 if (t < other_last) /* These positions already checked */
608 t = other_last;
1aa99e6b 609 last2 = last1 = HOP3c(strend, -prog->minlen, strbeg);
2c2d71f5
JH
610 if (last < last1)
611 last1 = last;
1de06328
YO
612 /* XXXX It is not documented what units *_offsets are in.
613 We assume bytes, but this is clearly wrong.
614 Meaning this code needs to be carefully reviewed for errors.
615 dmq.
616 */
617
2c2d71f5 618 /* On end-of-str: see comment below. */
33b8afdf
JH
619 must = do_utf8 ? prog->anchored_utf8 : prog->anchored_substr;
620 if (must == &PL_sv_undef) {
621 s = (char*)NULL;
1de06328 622 DEBUG_r(must = prog->anchored_utf8); /* for debug */
33b8afdf
JH
623 }
624 else
625 s = fbm_instr(
626 (unsigned char*)t,
627 HOP3(HOP3(last1, prog->anchored_offset, strend)
628 + SvCUR(must), -(SvTAIL(must)!=0), strbeg),
629 must,
7fba1cd6 630 multiline ? FBMrf_MULTILINE : 0
33b8afdf 631 );
ab3bbdeb
YO
632 DEBUG_EXECUTE_r({
633 RE_PV_QUOTED_DECL(quoted, do_utf8, PERL_DEBUG_PAD_ZERO(0),
634 SvPVX_const(must), RE_SV_DUMPLEN(must), 30);
635 PerlIO_printf(Perl_debug_log, "%s anchored substr %s%s",
2c2d71f5 636 (s ? "Found" : "Contradicts"),
ab3bbdeb
YO
637 quoted, RE_SV_TAIL(must));
638 });
639
640
2c2d71f5
JH
641 if (!s) {
642 if (last1 >= last2) {
a3621e74 643 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
2c2d71f5
JH
644 ", giving up...\n"));
645 goto fail_finish;
646 }
a3621e74 647 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
2c2d71f5 648 ", trying floating at offset %ld...\n",
be8e71aa 649 (long)(HOP3c(saved_s, 1, strend) - i_strpos)));
1aa99e6b
IH
650 other_last = HOP3c(last1, prog->anchored_offset+1, strend);
651 s = HOP3c(last, 1, strend);
2c2d71f5
JH
652 goto restart;
653 }
654 else {
a3621e74 655 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, " at offset %ld...\n",
30944b6d 656 (long)(s - i_strpos)));
1aa99e6b
IH
657 t = HOP3c(s, -prog->anchored_offset, strbeg);
658 other_last = HOP3c(s, 1, strend);
be8e71aa 659 s = saved_s;
2c2d71f5
JH
660 if (t == strpos)
661 goto try_at_start;
2c2d71f5
JH
662 goto try_at_offset;
663 }
30944b6d 664 }
2c2d71f5
JH
665 }
666 else { /* Take into account the floating substring. */
33b8afdf 667 char *last, *last1;
be8e71aa 668 char * const saved_s = s;
33b8afdf
JH
669 SV* must;
670
671 t = HOP3c(s, -start_shift, strbeg);
672 last1 = last =
673 HOP3c(strend, -prog->minlen + prog->float_min_offset, strbeg);
674 if (CHR_DIST((U8*)last, (U8*)t) > prog->float_max_offset)
675 last = HOP3c(t, prog->float_max_offset, strend);
676 s = HOP3c(t, prog->float_min_offset, strend);
677 if (s < other_last)
678 s = other_last;
2c2d71f5 679 /* XXXX It is not documented what units *_offsets are in. Assume bytes. */
33b8afdf
JH
680 must = do_utf8 ? prog->float_utf8 : prog->float_substr;
681 /* fbm_instr() takes into account exact value of end-of-str
682 if the check is SvTAIL(ed). Since false positives are OK,
683 and end-of-str is not later than strend we are OK. */
684 if (must == &PL_sv_undef) {
685 s = (char*)NULL;
1de06328 686 DEBUG_r(must = prog->float_utf8); /* for debug message */
33b8afdf
JH
687 }
688 else
2c2d71f5 689 s = fbm_instr((unsigned char*)s,
33b8afdf
JH
690 (unsigned char*)last + SvCUR(must)
691 - (SvTAIL(must)!=0),
7fba1cd6 692 must, multiline ? FBMrf_MULTILINE : 0);
ab3bbdeb
YO
693 DEBUG_EXECUTE_r({
694 RE_PV_QUOTED_DECL(quoted, do_utf8, PERL_DEBUG_PAD_ZERO(0),
695 SvPVX_const(must), RE_SV_DUMPLEN(must), 30);
696 PerlIO_printf(Perl_debug_log, "%s floating substr %s%s",
33b8afdf 697 (s ? "Found" : "Contradicts"),
ab3bbdeb
YO
698 quoted, RE_SV_TAIL(must));
699 });
33b8afdf
JH
700 if (!s) {
701 if (last1 == last) {
a3621e74 702 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
33b8afdf
JH
703 ", giving up...\n"));
704 goto fail_finish;
2c2d71f5 705 }
a3621e74 706 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
33b8afdf 707 ", trying anchored starting at offset %ld...\n",
be8e71aa 708 (long)(saved_s + 1 - i_strpos)));
33b8afdf
JH
709 other_last = last;
710 s = HOP3c(t, 1, strend);
711 goto restart;
712 }
713 else {
a3621e74 714 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, " at offset %ld...\n",
33b8afdf
JH
715 (long)(s - i_strpos)));
716 other_last = s; /* Fix this later. --Hugo */
be8e71aa 717 s = saved_s;
33b8afdf
JH
718 if (t == strpos)
719 goto try_at_start;
720 goto try_at_offset;
721 }
2c2d71f5 722 }
cad2e5aa 723 }
2c2d71f5 724
1de06328 725
9ef43ace 726 t= (char*)HOP3( s, -prog->check_offset_max, (prog->check_offset_max<0) ? strend : strpos);
1de06328 727
6bda09f9 728 DEBUG_OPTIMISE_MORE_r(
1de06328
YO
729 PerlIO_printf(Perl_debug_log,
730 "Check offset min:%"IVdf" max:%"IVdf" S:%"IVdf" t:%"IVdf" D:%"IVdf" end:%"IVdf"\n",
731 (IV)prog->check_offset_min,
732 (IV)prog->check_offset_max,
733 (IV)(s-strpos),
734 (IV)(t-strpos),
735 (IV)(t-s),
736 (IV)(strend-strpos)
737 )
738 );
739
2c2d71f5 740 if (s - strpos > prog->check_offset_max /* signed-corrected t > strpos */
1d86a7f9 741 && (!do_utf8
9ef43ace 742 || ((t = (char*)reghopmaybe3((U8*)s, -prog->check_offset_max, (U8*) ((prog->check_offset_max<0) ? strend : strpos)))
1de06328
YO
743 && t > strpos)))
744 {
2c2d71f5
JH
745 /* Fixed substring is found far enough so that the match
746 cannot start at strpos. */
747 try_at_offset:
cad2e5aa 748 if (ml_anch && t[-1] != '\n') {
30944b6d
IZ
749 /* Eventually fbm_*() should handle this, but often
750 anchored_offset is not 0, so this check will not be wasted. */
751 /* XXXX In the code below we prefer to look for "^" even in
752 presence of anchored substrings. And we search even
753 beyond the found float position. These pessimizations
754 are historical artefacts only. */
755 find_anchor:
2c2d71f5 756 while (t < strend - prog->minlen) {
cad2e5aa 757 if (*t == '\n') {
4ee3650e 758 if (t < check_at - prog->check_offset_min) {
33b8afdf 759 if (do_utf8 ? prog->anchored_utf8 : prog->anchored_substr) {
4ee3650e
GS
760 /* Since we moved from the found position,
761 we definitely contradict the found anchored
30944b6d
IZ
762 substr. Due to the above check we do not
763 contradict "check" substr.
764 Thus we can arrive here only if check substr
765 is float. Redo checking for "other"=="fixed".
766 */
9041c2e3 767 strpos = t + 1;
a3621e74 768 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "Found /%s^%s/m at offset %ld, rescanning for anchored from offset %ld...\n",
e4584336 769 PL_colors[0], PL_colors[1], (long)(strpos - i_strpos), (long)(strpos - i_strpos + prog->anchored_offset)));
30944b6d
IZ
770 goto do_other_anchored;
771 }
4ee3650e
GS
772 /* We don't contradict the found floating substring. */
773 /* XXXX Why not check for STCLASS? */
cad2e5aa 774 s = t + 1;
a3621e74 775 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "Found /%s^%s/m at offset %ld...\n",
e4584336 776 PL_colors[0], PL_colors[1], (long)(s - i_strpos)));
cad2e5aa
JH
777 goto set_useful;
778 }
4ee3650e
GS
779 /* Position contradicts check-string */
780 /* XXXX probably better to look for check-string
781 than for "\n", so one should lower the limit for t? */
a3621e74 782 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "Found /%s^%s/m, restarting lookup for check-string at offset %ld...\n",
e4584336 783 PL_colors[0], PL_colors[1], (long)(t + 1 - i_strpos)));
0e41cd87 784 other_last = strpos = s = t + 1;
cad2e5aa
JH
785 goto restart;
786 }
787 t++;
788 }
a3621e74 789 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "Did not find /%s^%s/m...\n",
e4584336 790 PL_colors[0], PL_colors[1]));
2c2d71f5 791 goto fail_finish;
cad2e5aa 792 }
f5952150 793 else {
a3621e74 794 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "Starting position does not contradict /%s^%s/m...\n",
e4584336 795 PL_colors[0], PL_colors[1]));
f5952150 796 }
cad2e5aa
JH
797 s = t;
798 set_useful:
33b8afdf 799 ++BmUSEFUL(do_utf8 ? prog->check_utf8 : prog->check_substr); /* hooray/5 */
cad2e5aa
JH
800 }
801 else {
f5952150 802 /* The found string does not prohibit matching at strpos,
2c2d71f5 803 - no optimization of calling REx engine can be performed,
f5952150
GS
804 unless it was an MBOL and we are not after MBOL,
805 or a future STCLASS check will fail this. */
2c2d71f5
JH
806 try_at_start:
807 /* Even in this situation we may use MBOL flag if strpos is offset
808 wrt the start of the string. */
05b4157f 809 if (ml_anch && sv && !SvROK(sv) /* See prev comment on SvROK */
a1933d95 810 && (strpos != strbeg) && strpos[-1] != '\n'
d506a20d
IZ
811 /* May be due to an implicit anchor of m{.*foo} */
812 && !(prog->reganch & ROPT_IMPLICIT))
813 {
cad2e5aa
JH
814 t = strpos;
815 goto find_anchor;
816 }
a3621e74 817 DEBUG_EXECUTE_r( if (ml_anch)
f5952150 818 PerlIO_printf(Perl_debug_log, "Position at offset %ld does not contradict /%s^%s/m...\n",
e4584336 819 (long)(strpos - i_strpos), PL_colors[0], PL_colors[1]);
30944b6d 820 );
2c2d71f5 821 success_at_start:
30944b6d 822 if (!(prog->reganch & ROPT_NAUGHTY) /* XXXX If strpos moved? */
33b8afdf
JH
823 && (do_utf8 ? (
824 prog->check_utf8 /* Could be deleted already */
825 && --BmUSEFUL(prog->check_utf8) < 0
826 && (prog->check_utf8 == prog->float_utf8)
827 ) : (
828 prog->check_substr /* Could be deleted already */
829 && --BmUSEFUL(prog->check_substr) < 0
830 && (prog->check_substr == prog->float_substr)
831 )))
66e933ab 832 {
cad2e5aa 833 /* If flags & SOMETHING - do not do it many times on the same match */
a3621e74 834 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "... Disabling check substring...\n"));
33b8afdf
JH
835 SvREFCNT_dec(do_utf8 ? prog->check_utf8 : prog->check_substr);
836 if (do_utf8 ? prog->check_substr : prog->check_utf8)
837 SvREFCNT_dec(do_utf8 ? prog->check_substr : prog->check_utf8);
a0714e2c
SS
838 prog->check_substr = prog->check_utf8 = NULL; /* disable */
839 prog->float_substr = prog->float_utf8 = NULL; /* clear */
840 check = NULL; /* abort */
cad2e5aa 841 s = strpos;
3cf5c195
IZ
842 /* XXXX This is a remnant of the old implementation. It
843 looks wasteful, since now INTUIT can use many
6eb5f6b9 844 other heuristics. */
cad2e5aa
JH
845 prog->reganch &= ~RE_USE_INTUIT;
846 }
847 else
848 s = strpos;
849 }
850
6eb5f6b9
JH
851 /* Last resort... */
852 /* XXXX BmUSEFUL already changed, maybe multiple change is meaningful... */
1de06328
YO
853 /* trie stclasses are too expensive to use here, we are better off to
854 leave it to regmatch itself */
786e8c11 855 if (prog->regstclass && PL_regkind[OP(prog->regstclass)]!=TRIE) {
6eb5f6b9
JH
856 /* minlen == 0 is possible if regstclass is \b or \B,
857 and the fixed substr is ''$.
858 Since minlen is already taken into account, s+1 is before strend;
859 accidentally, minlen >= 1 guaranties no false positives at s + 1
860 even for \b or \B. But (minlen? 1 : 0) below assumes that
861 regstclass does not come from lookahead... */
862 /* If regstclass takes bytelength more than 1: If charlength==1, OK.
863 This leaves EXACTF only, which is dealt with in find_byclass(). */
890ce7af 864 const U8* const str = (U8*)STRING(prog->regstclass);
3dab1dad 865 const int cl_l = (PL_regkind[OP(prog->regstclass)] == EXACT
1aa99e6b 866 ? CHR_DIST(str+STR_LEN(prog->regstclass), str)
66e933ab 867 : 1);
1de06328
YO
868 char * endpos;
869 if (prog->anchored_substr || prog->anchored_utf8 || ml_anch)
870 endpos= HOP3c(s, (prog->minlen ? cl_l : 0), strend);
871 else if (prog->float_substr || prog->float_utf8)
872 endpos= HOP3c(HOP3c(check_at, -start_shift, strbeg), cl_l, strend);
873 else
874 endpos= strend;
875
56570a2c 876 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "start_shift: %"IVdf" check_at: %d s: %d endpos: %d\n",
b57a0404 877 (IV)start_shift, check_at - strbeg, s - strbeg, endpos - strbeg));
1de06328 878
6eb5f6b9 879 t = s;
3b0527fe 880 s = find_byclass(prog, prog->regstclass, s, endpos, NULL);
6eb5f6b9
JH
881 if (!s) {
882#ifdef DEBUGGING
cbbf8932 883 const char *what = NULL;
6eb5f6b9
JH
884#endif
885 if (endpos == strend) {
a3621e74 886 DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log,
6eb5f6b9
JH
887 "Could not match STCLASS...\n") );
888 goto fail;
889 }
a3621e74 890 DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log,
66e933ab 891 "This position contradicts STCLASS...\n") );
653099ff
GS
892 if ((prog->reganch & ROPT_ANCH) && !ml_anch)
893 goto fail;
6eb5f6b9 894 /* Contradict one of substrings */
33b8afdf
JH
895 if (prog->anchored_substr || prog->anchored_utf8) {
896 if ((do_utf8 ? prog->anchored_utf8 : prog->anchored_substr) == check) {
a3621e74 897 DEBUG_EXECUTE_r( what = "anchored" );
6eb5f6b9 898 hop_and_restart:
1aa99e6b 899 s = HOP3c(t, 1, strend);
66e933ab
GS
900 if (s + start_shift + end_shift > strend) {
901 /* XXXX Should be taken into account earlier? */
a3621e74 902 DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log,
66e933ab
GS
903 "Could not match STCLASS...\n") );
904 goto fail;
905 }
5e39e1e5
HS
906 if (!check)
907 goto giveup;
a3621e74 908 DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log,
f5952150 909 "Looking for %s substr starting at offset %ld...\n",
6eb5f6b9
JH
910 what, (long)(s + start_shift - i_strpos)) );
911 goto restart;
912 }
66e933ab 913 /* Have both, check_string is floating */
6eb5f6b9
JH
914 if (t + start_shift >= check_at) /* Contradicts floating=check */
915 goto retry_floating_check;
916 /* Recheck anchored substring, but not floating... */
9041c2e3 917 s = check_at;
5e39e1e5
HS
918 if (!check)
919 goto giveup;
a3621e74 920 DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log,
f5952150 921 "Looking for anchored substr starting at offset %ld...\n",
6eb5f6b9
JH
922 (long)(other_last - i_strpos)) );
923 goto do_other_anchored;
924 }
60e71179
GS
925 /* Another way we could have checked stclass at the
926 current position only: */
927 if (ml_anch) {
928 s = t = t + 1;
5e39e1e5
HS
929 if (!check)
930 goto giveup;
a3621e74 931 DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log,
f5952150 932 "Looking for /%s^%s/m starting at offset %ld...\n",
e4584336 933 PL_colors[0], PL_colors[1], (long)(t - i_strpos)) );
60e71179 934 goto try_at_offset;
66e933ab 935 }
33b8afdf 936 if (!(do_utf8 ? prog->float_utf8 : prog->float_substr)) /* Could have been deleted */
60e71179 937 goto fail;
6eb5f6b9
JH
938 /* Check is floating subtring. */
939 retry_floating_check:
940 t = check_at - start_shift;
a3621e74 941 DEBUG_EXECUTE_r( what = "floating" );
6eb5f6b9
JH
942 goto hop_and_restart;
943 }
b7953727 944 if (t != s) {
a3621e74 945 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
6eb5f6b9 946 "By STCLASS: moving %ld --> %ld\n",
b7953727
JH
947 (long)(t - i_strpos), (long)(s - i_strpos))
948 );
949 }
950 else {
a3621e74 951 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
b7953727
JH
952 "Does not contradict STCLASS...\n");
953 );
954 }
6eb5f6b9 955 }
5e39e1e5 956 giveup:
a3621e74 957 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "%s%s:%s match at offset %ld\n",
5e39e1e5
HS
958 PL_colors[4], (check ? "Guessed" : "Giving up"),
959 PL_colors[5], (long)(s - i_strpos)) );
cad2e5aa 960 return s;
2c2d71f5
JH
961
962 fail_finish: /* Substring not found */
33b8afdf
JH
963 if (prog->check_substr || prog->check_utf8) /* could be removed already */
964 BmUSEFUL(do_utf8 ? prog->check_utf8 : prog->check_substr) += 5; /* hooray */
cad2e5aa 965 fail:
a3621e74 966 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "%sMatch rejected by optimizer%s\n",
e4584336 967 PL_colors[4], PL_colors[5]));
bd61b366 968 return NULL;
cad2e5aa 969}
9661b544 970
786e8c11 971
3b0527fe 972
4cadc6a9
YO
973#define REXEC_TRIE_READ_CHAR(trie_type, trie, uc, uscan, len, uvc, charid, \
974foldlen, foldbuf, uniflags) STMT_START { \
975 switch (trie_type) { \
976 case trie_utf8_fold: \
977 if ( foldlen>0 ) { \
978 uvc = utf8n_to_uvuni( uscan, UTF8_MAXLEN, &len, uniflags ); \
979 foldlen -= len; \
980 uscan += len; \
981 len=0; \
982 } else { \
983 uvc = utf8n_to_uvuni( (U8*)uc, UTF8_MAXLEN, &len, uniflags ); \
984 uvc = to_uni_fold( uvc, foldbuf, &foldlen ); \
985 foldlen -= UNISKIP( uvc ); \
986 uscan = foldbuf + UNISKIP( uvc ); \
987 } \
988 break; \
989 case trie_utf8: \
990 uvc = utf8n_to_uvuni( (U8*)uc, UTF8_MAXLEN, &len, uniflags ); \
991 break; \
992 case trie_plain: \
993 uvc = (UV)*uc; \
994 len = 1; \
995 } \
996 \
997 if (uvc < 256) { \
998 charid = trie->charmap[ uvc ]; \
999 } \
1000 else { \
1001 charid = 0; \
1002 if (trie->widecharmap) { \
1003 SV** const svpp = hv_fetch(trie->widecharmap, \
1004 (char*)&uvc, sizeof(UV), 0); \
1005 if (svpp) \
1006 charid = (U16)SvIV(*svpp); \
1007 } \
1008 } \
1009} STMT_END
1010
1011#define REXEC_FBC_EXACTISH_CHECK(CoNd) \
1012 if ( (CoNd) \
1013 && (ln == len || \
1014 ibcmp_utf8(s, NULL, 0, do_utf8, \
1015 m, NULL, ln, (bool)UTF)) \
1016 && (!reginfo || regtry(reginfo, s)) ) \
1017 goto got_it; \
1018 else { \
1019 U8 foldbuf[UTF8_MAXBYTES_CASE+1]; \
1020 uvchr_to_utf8(tmpbuf, c); \
1021 f = to_utf8_fold(tmpbuf, foldbuf, &foldlen); \
1022 if ( f != c \
1023 && (f == c1 || f == c2) \
1024 && (ln == foldlen || \
1025 !ibcmp_utf8((char *) foldbuf, \
1026 NULL, foldlen, do_utf8, \
1027 m, \
1028 NULL, ln, (bool)UTF)) \
1029 && (!reginfo || regtry(reginfo, s)) ) \
1030 goto got_it; \
1031 } \
1032 s += len
1033
1034#define REXEC_FBC_EXACTISH_SCAN(CoNd) \
1035STMT_START { \
1036 while (s <= e) { \
1037 if ( (CoNd) \
1038 && (ln == 1 || !(OP(c) == EXACTF \
1039 ? ibcmp(s, m, ln) \
1040 : ibcmp_locale(s, m, ln))) \
1041 && (!reginfo || regtry(reginfo, s)) ) \
1042 goto got_it; \
1043 s++; \
1044 } \
1045} STMT_END
1046
1047#define REXEC_FBC_UTF8_SCAN(CoDe) \
1048STMT_START { \
1049 while (s + (uskip = UTF8SKIP(s)) <= strend) { \
1050 CoDe \
1051 s += uskip; \
1052 } \
1053} STMT_END
1054
1055#define REXEC_FBC_SCAN(CoDe) \
1056STMT_START { \
1057 while (s < strend) { \
1058 CoDe \
1059 s++; \
1060 } \
1061} STMT_END
1062
1063#define REXEC_FBC_UTF8_CLASS_SCAN(CoNd) \
1064REXEC_FBC_UTF8_SCAN( \
1065 if (CoNd) { \
1066 if (tmp && (!reginfo || regtry(reginfo, s))) \
1067 goto got_it; \
1068 else \
1069 tmp = doevery; \
1070 } \
1071 else \
1072 tmp = 1; \
1073)
1074
1075#define REXEC_FBC_CLASS_SCAN(CoNd) \
1076REXEC_FBC_SCAN( \
1077 if (CoNd) { \
1078 if (tmp && (!reginfo || regtry(reginfo, s))) \
1079 goto got_it; \
1080 else \
1081 tmp = doevery; \
1082 } \
1083 else \
1084 tmp = 1; \
1085)
1086
1087#define REXEC_FBC_TRYIT \
1088if ((!reginfo || regtry(reginfo, s))) \
1089 goto got_it
1090
1091#define REXEC_FBC_CSCAN_PRELOAD(UtFpReLoAd,CoNdUtF8,CoNd) \
1092 if (do_utf8) { \
1093 UtFpReLoAd; \
1094 REXEC_FBC_UTF8_CLASS_SCAN(CoNdUtF8); \
1095 } \
1096 else { \
1097 REXEC_FBC_CLASS_SCAN(CoNd); \
1098 } \
1099 break
1100
1101#define REXEC_FBC_CSCAN_TAINT(CoNdUtF8,CoNd) \
1102 PL_reg_flags |= RF_tainted; \
1103 if (do_utf8) { \
1104 REXEC_FBC_UTF8_CLASS_SCAN(CoNdUtF8); \
1105 } \
1106 else { \
1107 REXEC_FBC_CLASS_SCAN(CoNd); \
1108 } \
1109 break
1110
786e8c11
YO
1111#define DUMP_EXEC_POS(li,s,doutf8) \
1112 dump_exec_pos(li,s,(PL_regeol),(PL_bostr),(PL_reg_starttry),doutf8)
1113
1114/* We know what class REx starts with. Try to find this position... */
1115/* if reginfo is NULL, its a dryrun */
1116/* annoyingly all the vars in this routine have different names from their counterparts
1117 in regmatch. /grrr */
1118
3c3eec57 1119STATIC char *
07be1b83
YO
1120S_find_byclass(pTHX_ regexp * prog, const regnode *c, char *s,
1121 const char *strend, const regmatch_info *reginfo)
a687059c 1122{
27da23d5 1123 dVAR;
1df70142 1124 const I32 doevery = (prog->reganch & ROPT_SKIP) == 0;
6eb5f6b9 1125 char *m;
d8093b23 1126 STRLEN ln;
5dab1207 1127 STRLEN lnc;
078c425b 1128 register STRLEN uskip;
d8093b23 1129 unsigned int c1;
1130 unsigned int c2;
6eb5f6b9
JH
1131 char *e;
1132 register I32 tmp = 1; /* Scratch variable? */
a3b680e6 1133 register const bool do_utf8 = PL_reg_match_utf8;
cad2e5aa 1134
6eb5f6b9
JH
1135 /* We know what class it must start with. */
1136 switch (OP(c)) {
6eb5f6b9 1137 case ANYOF:
388cc4de 1138 if (do_utf8) {
4cadc6a9 1139 REXEC_FBC_UTF8_CLASS_SCAN((ANYOF_FLAGS(c) & ANYOF_UNICODE) ||
388cc4de 1140 !UTF8_IS_INVARIANT((U8)s[0]) ?
32fc9b6a 1141 reginclass(prog, c, (U8*)s, 0, do_utf8) :
4cadc6a9 1142 REGINCLASS(prog, c, (U8*)s));
388cc4de
HS
1143 }
1144 else {
1145 while (s < strend) {
1146 STRLEN skip = 1;
1147
32fc9b6a 1148 if (REGINCLASS(prog, c, (U8*)s) ||
388cc4de
HS
1149 (ANYOF_FOLD_SHARP_S(c, s, strend) &&
1150 /* The assignment of 2 is intentional:
1151 * for the folded sharp s, the skip is 2. */
1152 (skip = SHARP_S_SKIP))) {
3b0527fe 1153 if (tmp && (!reginfo || regtry(reginfo, s)))
388cc4de
HS
1154 goto got_it;
1155 else
1156 tmp = doevery;
1157 }
1158 else
1159 tmp = 1;
1160 s += skip;
1161 }
a0d0e21e 1162 }
6eb5f6b9 1163 break;
f33976b4 1164 case CANY:
4cadc6a9 1165 REXEC_FBC_SCAN(
3b0527fe 1166 if (tmp && (!reginfo || regtry(reginfo, s)))
f33976b4
DB
1167 goto got_it;
1168 else
1169 tmp = doevery;
4cadc6a9 1170 );
f33976b4 1171 break;
6eb5f6b9 1172 case EXACTF:
5dab1207
NIS
1173 m = STRING(c);
1174 ln = STR_LEN(c); /* length to match in octets/bytes */
1175 lnc = (I32) ln; /* length to match in characters */
1aa99e6b 1176 if (UTF) {
a2a2844f 1177 STRLEN ulen1, ulen2;
5dab1207 1178 U8 *sm = (U8 *) m;
89ebb4a3
JH
1179 U8 tmpbuf1[UTF8_MAXBYTES_CASE+1];
1180 U8 tmpbuf2[UTF8_MAXBYTES_CASE+1];
4ad0818d 1181 const U32 uniflags = UTF8_ALLOW_DEFAULT;
a2a2844f
JH
1182
1183 to_utf8_lower((U8*)m, tmpbuf1, &ulen1);
1184 to_utf8_upper((U8*)m, tmpbuf2, &ulen2);
1185
89ebb4a3 1186 c1 = utf8n_to_uvchr(tmpbuf1, UTF8_MAXBYTES_CASE,
041457d9 1187 0, uniflags);
89ebb4a3 1188 c2 = utf8n_to_uvchr(tmpbuf2, UTF8_MAXBYTES_CASE,
041457d9 1189 0, uniflags);
5dab1207
NIS
1190 lnc = 0;
1191 while (sm < ((U8 *) m + ln)) {
1192 lnc++;
1193 sm += UTF8SKIP(sm);
1194 }
1aa99e6b
IH
1195 }
1196 else {
1197 c1 = *(U8*)m;
1198 c2 = PL_fold[c1];
1199 }
6eb5f6b9
JH
1200 goto do_exactf;
1201 case EXACTFL:
5dab1207
NIS
1202 m = STRING(c);
1203 ln = STR_LEN(c);
1204 lnc = (I32) ln;
d8093b23 1205 c1 = *(U8*)m;
6eb5f6b9
JH
1206 c2 = PL_fold_locale[c1];
1207 do_exactf:
db12adc6 1208 e = HOP3c(strend, -((I32)lnc), s);
b3c9acc1 1209
3b0527fe 1210 if (!reginfo && e < s)
6eb5f6b9 1211 e = s; /* Due to minlen logic of intuit() */
1aa99e6b 1212
60a8b682
JH
1213 /* The idea in the EXACTF* cases is to first find the
1214 * first character of the EXACTF* node and then, if
1215 * necessary, case-insensitively compare the full
1216 * text of the node. The c1 and c2 are the first
1217 * characters (though in Unicode it gets a bit
1218 * more complicated because there are more cases
7f16dd3d
JH
1219 * than just upper and lower: one needs to use
1220 * the so-called folding case for case-insensitive
1221 * matching (called "loose matching" in Unicode).
1222 * ibcmp_utf8() will do just that. */
60a8b682 1223
1aa99e6b 1224 if (do_utf8) {
575cac57 1225 UV c, f;
89ebb4a3 1226 U8 tmpbuf [UTF8_MAXBYTES+1];
575cac57 1227 STRLEN len, foldlen;
4ad0818d 1228 const U32 uniflags = UTF8_ALLOW_DEFAULT;
09091399 1229 if (c1 == c2) {
5dab1207
NIS
1230 /* Upper and lower of 1st char are equal -
1231 * probably not a "letter". */
1aa99e6b 1232 while (s <= e) {
89ebb4a3 1233 c = utf8n_to_uvchr((U8*)s, UTF8_MAXBYTES, &len,
041457d9 1234 uniflags);
4cadc6a9 1235 REXEC_FBC_EXACTISH_CHECK(c == c1);
1aa99e6b 1236 }
09091399
JH
1237 }
1238 else {
1aa99e6b 1239 while (s <= e) {
89ebb4a3 1240 c = utf8n_to_uvchr((U8*)s, UTF8_MAXBYTES, &len,
041457d9 1241 uniflags);
80aecb99 1242
60a8b682 1243 /* Handle some of the three Greek sigmas cases.
8c01da3c
JH
1244 * Note that not all the possible combinations
1245 * are handled here: some of them are handled
1246 * by the standard folding rules, and some of
1247 * them (the character class or ANYOF cases)
1248 * are handled during compiletime in
1249 * regexec.c:S_regclass(). */
880bd946
JH
1250 if (c == (UV)UNICODE_GREEK_CAPITAL_LETTER_SIGMA ||
1251 c == (UV)UNICODE_GREEK_SMALL_LETTER_FINAL_SIGMA)
1252 c = (UV)UNICODE_GREEK_SMALL_LETTER_SIGMA;
80aecb99 1253
4cadc6a9 1254 REXEC_FBC_EXACTISH_CHECK(c == c1 || c == c2);
1aa99e6b 1255 }
09091399 1256 }
1aa99e6b
IH
1257 }
1258 else {
1259 if (c1 == c2)
4cadc6a9 1260 REXEC_FBC_EXACTISH_SCAN(*(U8*)s == c1);
1aa99e6b 1261 else
4cadc6a9 1262 REXEC_FBC_EXACTISH_SCAN(*(U8*)s == c1 || *(U8*)s == c2);
b3c9acc1
IZ
1263 }
1264 break;
bbce6d69 1265 case BOUNDL:
3280af22 1266 PL_reg_flags |= RF_tainted;
bbce6d69 1267 /* FALL THROUGH */
a0d0e21e 1268 case BOUND:
ffc61ed2 1269 if (do_utf8) {
12d33761 1270 if (s == PL_bostr)
ffc61ed2
JH
1271 tmp = '\n';
1272 else {
6136c704 1273 U8 * const r = reghop3((U8*)s, -1, (U8*)PL_bostr);
4ad0818d 1274 tmp = utf8n_to_uvchr(r, UTF8SKIP(r), 0, UTF8_ALLOW_DEFAULT);
ffc61ed2
JH
1275 }
1276 tmp = ((OP(c) == BOUND ?
9041c2e3 1277 isALNUM_uni(tmp) : isALNUM_LC_uvchr(UNI_TO_NATIVE(tmp))) != 0);
1a4fad37 1278 LOAD_UTF8_CHARCLASS_ALNUM();
4cadc6a9 1279 REXEC_FBC_UTF8_SCAN(
ffc61ed2 1280 if (tmp == !(OP(c) == BOUND ?
bb7a0f54 1281 (bool)swash_fetch(PL_utf8_alnum, (U8*)s, do_utf8) :
ffc61ed2
JH
1282 isALNUM_LC_utf8((U8*)s)))
1283 {
1284 tmp = !tmp;
4cadc6a9 1285 REXEC_FBC_TRYIT;
a687059c 1286 }
4cadc6a9 1287 );
a0d0e21e 1288 }
667bb95a 1289 else {
12d33761 1290 tmp = (s != PL_bostr) ? UCHARAT(s - 1) : '\n';
ffc61ed2 1291 tmp = ((OP(c) == BOUND ? isALNUM(tmp) : isALNUM_LC(tmp)) != 0);
4cadc6a9 1292 REXEC_FBC_SCAN(
ffc61ed2
JH
1293 if (tmp ==
1294 !(OP(c) == BOUND ? isALNUM(*s) : isALNUM_LC(*s))) {
1295 tmp = !tmp;
4cadc6a9 1296 REXEC_FBC_TRYIT;
a0ed51b3 1297 }
4cadc6a9 1298 );
a0ed51b3 1299 }
3b0527fe 1300 if ((!prog->minlen && tmp) && (!reginfo || regtry(reginfo, s)))
a0ed51b3
LW
1301 goto got_it;
1302 break;
bbce6d69 1303 case NBOUNDL:
3280af22 1304 PL_reg_flags |= RF_tainted;
bbce6d69 1305 /* FALL THROUGH */
a0d0e21e 1306 case NBOUND:
ffc61ed2 1307 if (do_utf8) {
12d33761 1308 if (s == PL_bostr)
ffc61ed2
JH
1309 tmp = '\n';
1310 else {
6136c704 1311 U8 * const r = reghop3((U8*)s, -1, (U8*)PL_bostr);
4ad0818d 1312 tmp = utf8n_to_uvchr(r, UTF8SKIP(r), 0, UTF8_ALLOW_DEFAULT);
ffc61ed2
JH
1313 }
1314 tmp = ((OP(c) == NBOUND ?
9041c2e3 1315 isALNUM_uni(tmp) : isALNUM_LC_uvchr(UNI_TO_NATIVE(tmp))) != 0);
1a4fad37 1316 LOAD_UTF8_CHARCLASS_ALNUM();
4cadc6a9 1317 REXEC_FBC_UTF8_SCAN(
ffc61ed2 1318 if (tmp == !(OP(c) == NBOUND ?
bb7a0f54 1319 (bool)swash_fetch(PL_utf8_alnum, (U8*)s, do_utf8) :
ffc61ed2
JH
1320 isALNUM_LC_utf8((U8*)s)))
1321 tmp = !tmp;
4cadc6a9
YO
1322 else REXEC_FBC_TRYIT;
1323 );
a0d0e21e 1324 }
667bb95a 1325 else {
12d33761 1326 tmp = (s != PL_bostr) ? UCHARAT(s - 1) : '\n';
ffc61ed2
JH
1327 tmp = ((OP(c) == NBOUND ?
1328 isALNUM(tmp) : isALNUM_LC(tmp)) != 0);
4cadc6a9 1329 REXEC_FBC_SCAN(
ffc61ed2
JH
1330 if (tmp ==
1331 !(OP(c) == NBOUND ? isALNUM(*s) : isALNUM_LC(*s)))
1332 tmp = !tmp;
4cadc6a9
YO
1333 else REXEC_FBC_TRYIT;
1334 );
a0ed51b3 1335 }
3b0527fe 1336 if ((!prog->minlen && !tmp) && (!reginfo || regtry(reginfo, s)))
a0ed51b3
LW
1337 goto got_it;
1338 break;
a0d0e21e 1339 case ALNUM:
4cadc6a9
YO
1340 REXEC_FBC_CSCAN_PRELOAD(
1341 LOAD_UTF8_CHARCLASS_ALNUM(),
1342 swash_fetch(PL_utf8_alnum, (U8*)s, do_utf8),
1343 isALNUM(*s)
1344 );
bbce6d69 1345 case ALNUML:
4cadc6a9
YO
1346 REXEC_FBC_CSCAN_TAINT(
1347 isALNUM_LC_utf8((U8*)s),
1348 isALNUM_LC(*s)
1349 );
a0d0e21e 1350 case NALNUM:
4cadc6a9
YO
1351 REXEC_FBC_CSCAN_PRELOAD(
1352 LOAD_UTF8_CHARCLASS_ALNUM(),
1353 !swash_fetch(PL_utf8_alnum, (U8*)s, do_utf8),
1354 !isALNUM(*s)
1355 );
bbce6d69 1356 case NALNUML:
4cadc6a9
YO
1357 REXEC_FBC_CSCAN_TAINT(
1358 !isALNUM_LC_utf8((U8*)s),
1359 !isALNUM_LC(*s)
1360 );
a0d0e21e 1361 case SPACE:
4cadc6a9
YO
1362 REXEC_FBC_CSCAN_PRELOAD(
1363 LOAD_UTF8_CHARCLASS_SPACE(),
1364 *s == ' ' || swash_fetch(PL_utf8_space,(U8*)s, do_utf8),
1365 isSPACE(*s)
1366 );
bbce6d69 1367 case SPACEL:
4cadc6a9
YO
1368 REXEC_FBC_CSCAN_TAINT(
1369 *s == ' ' || isSPACE_LC_utf8((U8*)s),
1370 isSPACE_LC(*s)
1371 );
a0d0e21e 1372 case NSPACE:
4cadc6a9
YO
1373 REXEC_FBC_CSCAN_PRELOAD(
1374 LOAD_UTF8_CHARCLASS_SPACE(),
1375 !(*s == ' ' || swash_fetch(PL_utf8_space,(U8*)s, do_utf8)),
1376 !isSPACE(*s)
1377 );
bbce6d69 1378 case NSPACEL:
4cadc6a9
YO
1379 REXEC_FBC_CSCAN_TAINT(
1380 !(*s == ' ' || isSPACE_LC_utf8((U8*)s)),
1381 !isSPACE_LC(*s)
1382 );
a0d0e21e 1383 case DIGIT:
4cadc6a9
YO
1384 REXEC_FBC_CSCAN_PRELOAD(
1385 LOAD_UTF8_CHARCLASS_DIGIT(),
1386 swash_fetch(PL_utf8_digit,(U8*)s, do_utf8),
1387 isDIGIT(*s)
1388 );
b8c5462f 1389 case DIGITL:
4cadc6a9
YO
1390 REXEC_FBC_CSCAN_TAINT(
1391 isDIGIT_LC_utf8((U8*)s),
1392 isDIGIT_LC(*s)
1393 );
a0d0e21e 1394 case NDIGIT:
4cadc6a9
YO
1395 REXEC_FBC_CSCAN_PRELOAD(
1396 LOAD_UTF8_CHARCLASS_DIGIT(),
1397 !swash_fetch(PL_utf8_digit,(U8*)s, do_utf8),
1398 !isDIGIT(*s)
1399 );
b8c5462f 1400 case NDIGITL:
4cadc6a9
YO
1401 REXEC_FBC_CSCAN_TAINT(
1402 !isDIGIT_LC_utf8((U8*)s),
1403 !isDIGIT_LC(*s)
1404 );
1de06328
YO
1405 case AHOCORASICKC:
1406 case AHOCORASICK:
07be1b83
YO
1407 {
1408 const enum { trie_plain, trie_utf8, trie_utf8_fold }
1409 trie_type = do_utf8 ?
1410 (c->flags == EXACT ? trie_utf8 : trie_utf8_fold)
1411 : trie_plain;
1412 /* what trie are we using right now */
1413 reg_ac_data *aho
1414 = (reg_ac_data*)prog->data->data[ ARG( c ) ];
1415 reg_trie_data *trie=aho->trie;
1416
1417 const char *last_start = strend - trie->minlen;
6148ee25 1418#ifdef DEBUGGING
07be1b83 1419 const char *real_start = s;
6148ee25 1420#endif
07be1b83 1421 STRLEN maxlen = trie->maxlen;
be8e71aa
YO
1422 SV *sv_points;
1423 U8 **points; /* map of where we were in the input string
786e8c11 1424 when reading a given char. For ASCII this
be8e71aa
YO
1425 is unnecessary overhead as the relationship
1426 is always 1:1, but for unicode, especially
1427 case folded unicode this is not true. */
f9e705e8 1428 U8 foldbuf[ UTF8_MAXBYTES_CASE + 1 ];
786e8c11
YO
1429 U8 *bitmap=NULL;
1430
07be1b83
YO
1431
1432 GET_RE_DEBUG_FLAGS_DECL;
1433
be8e71aa
YO
1434 /* We can't just allocate points here. We need to wrap it in
1435 * an SV so it gets freed properly if there is a croak while
1436 * running the match */
1437 ENTER;
1438 SAVETMPS;
1439 sv_points=newSV(maxlen * sizeof(U8 *));
1440 SvCUR_set(sv_points,
1441 maxlen * sizeof(U8 *));
1442 SvPOK_on(sv_points);
1443 sv_2mortal(sv_points);
1444 points=(U8**)SvPV_nolen(sv_points );
1de06328
YO
1445 if ( trie_type != trie_utf8_fold
1446 && (trie->bitmap || OP(c)==AHOCORASICKC) )
1447 {
786e8c11
YO
1448 if (trie->bitmap)
1449 bitmap=(U8*)trie->bitmap;
1450 else
1451 bitmap=(U8*)ANYOF_BITMAP(c);
07be1b83 1452 }
786e8c11
YO
1453 /* this is the Aho-Corasick algorithm modified a touch
1454 to include special handling for long "unknown char"
1455 sequences. The basic idea being that we use AC as long
1456 as we are dealing with a possible matching char, when
1457 we encounter an unknown char (and we have not encountered
1458 an accepting state) we scan forward until we find a legal
1459 starting char.
1460 AC matching is basically that of trie matching, except
1461 that when we encounter a failing transition, we fall back
1462 to the current states "fail state", and try the current char
1463 again, a process we repeat until we reach the root state,
1464 state 1, or a legal transition. If we fail on the root state
1465 then we can either terminate if we have reached an accepting
1466 state previously, or restart the entire process from the beginning
1467 if we have not.
1468
1469 */
07be1b83
YO
1470 while (s <= last_start) {
1471 const U32 uniflags = UTF8_ALLOW_DEFAULT;
1472 U8 *uc = (U8*)s;
1473 U16 charid = 0;
1474 U32 base = 1;
1475 U32 state = 1;
1476 UV uvc = 0;
1477 STRLEN len = 0;
1478 STRLEN foldlen = 0;
1479 U8 *uscan = (U8*)NULL;
1480 U8 *leftmost = NULL;
786e8c11
YO
1481#ifdef DEBUGGING
1482 U32 accepted_word= 0;
1483#endif
07be1b83
YO
1484 U32 pointpos = 0;
1485
1486 while ( state && uc <= (U8*)strend ) {
1487 int failed=0;
786e8c11
YO
1488 U32 word = aho->states[ state ].wordnum;
1489
1de06328
YO
1490 if( state==1 ) {
1491 if ( bitmap ) {
1492 DEBUG_TRIE_EXECUTE_r(
1493 if ( uc <= (U8*)last_start && !BITMAP_TEST(bitmap,*uc) ) {
1494 dump_exec_pos( (char *)uc, c, strend, real_start,
1495 (char *)uc, do_utf8 );
1496 PerlIO_printf( Perl_debug_log,
1497 " Scanning for legal start char...\n");
1498 }
1499 );
1500 while ( uc <= (U8*)last_start && !BITMAP_TEST(bitmap,*uc) ) {
1501 uc++;
786e8c11 1502 }
1de06328 1503 s= (char *)uc;
786e8c11 1504 }
786e8c11
YO
1505 if (uc >(U8*)last_start) break;
1506 }
1507
1508 if ( word ) {
1509 U8 *lpos= points[ (pointpos - trie->wordlen[word-1] ) % maxlen ];
1510 if (!leftmost || lpos < leftmost) {
1511 DEBUG_r(accepted_word=word);
07be1b83 1512 leftmost= lpos;
786e8c11 1513 }
07be1b83 1514 if (base==0) break;
786e8c11 1515
07be1b83
YO
1516 }
1517 points[pointpos++ % maxlen]= uc;
4cadc6a9
YO
1518 REXEC_TRIE_READ_CHAR(trie_type, trie, uc, uscan, len,
1519 uvc, charid, foldlen, foldbuf, uniflags);
786e8c11
YO
1520 DEBUG_TRIE_EXECUTE_r({
1521 dump_exec_pos( (char *)uc, c, strend, real_start,
1522 s, do_utf8 );
07be1b83 1523 PerlIO_printf(Perl_debug_log,
786e8c11
YO
1524 " Charid:%3u CP:%4"UVxf" ",
1525 charid, uvc);
1526 });
07be1b83
YO
1527
1528 do {
6148ee25 1529#ifdef DEBUGGING
786e8c11 1530 word = aho->states[ state ].wordnum;
6148ee25 1531#endif
07be1b83
YO
1532 base = aho->states[ state ].trans.base;
1533
786e8c11
YO
1534 DEBUG_TRIE_EXECUTE_r({
1535 if (failed)
1536 dump_exec_pos( (char *)uc, c, strend, real_start,
1537 s, do_utf8 );
07be1b83 1538 PerlIO_printf( Perl_debug_log,
786e8c11
YO
1539 "%sState: %4"UVxf", word=%"UVxf,
1540 failed ? " Fail transition to " : "",
1541 (UV)state, (UV)word);
1542 });
07be1b83
YO
1543 if ( base ) {
1544 U32 tmp;
1545 if (charid &&
1546 (base + charid > trie->uniquecharcount )
1547 && (base + charid - 1 - trie->uniquecharcount
1548 < trie->lasttrans)
1549 && trie->trans[base + charid - 1 -
1550 trie->uniquecharcount].check == state
1551 && (tmp=trie->trans[base + charid - 1 -
1552 trie->uniquecharcount ].next))
1553 {
786e8c11
YO
1554 DEBUG_TRIE_EXECUTE_r(
1555 PerlIO_printf( Perl_debug_log," - legal\n"));
07be1b83
YO
1556 state = tmp;
1557 break;
1558 }
1559 else {
786e8c11
YO
1560 DEBUG_TRIE_EXECUTE_r(
1561 PerlIO_printf( Perl_debug_log," - fail\n"));
1562 failed = 1;
1563 state = aho->fail[state];
07be1b83
YO
1564 }
1565 }
1566 else {
1567 /* we must be accepting here */
786e8c11
YO
1568 DEBUG_TRIE_EXECUTE_r(
1569 PerlIO_printf( Perl_debug_log," - accepting\n"));
1570 failed = 1;
07be1b83
YO
1571 break;
1572 }
1573 } while(state);
786e8c11 1574 uc += len;
07be1b83
YO
1575 if (failed) {
1576 if (leftmost)
1577 break;
786e8c11 1578 if (!state) state = 1;
07be1b83
YO
1579 }
1580 }
1581 if ( aho->states[ state ].wordnum ) {
1582 U8 *lpos = points[ (pointpos - trie->wordlen[aho->states[ state ].wordnum-1]) % maxlen ];
786e8c11
YO
1583 if (!leftmost || lpos < leftmost) {
1584 DEBUG_r(accepted_word=aho->states[ state ].wordnum);
07be1b83 1585 leftmost = lpos;
786e8c11 1586 }
07be1b83 1587 }
07be1b83
YO
1588 if (leftmost) {
1589 s = (char*)leftmost;
786e8c11
YO
1590 DEBUG_TRIE_EXECUTE_r({
1591 PerlIO_printf(
1592 Perl_debug_log,"Matches word #%"UVxf" at position %d. Trying full pattern...\n",
1593 (UV)accepted_word, s - real_start
1594 );
1595 });
be8e71aa
YO
1596 if (!reginfo || regtry(reginfo, s)) {
1597 FREETMPS;
1598 LEAVE;
07be1b83 1599 goto got_it;
be8e71aa 1600 }
07be1b83 1601 s = HOPc(s,1);
786e8c11
YO
1602 DEBUG_TRIE_EXECUTE_r({
1603 PerlIO_printf( Perl_debug_log,"Pattern failed. Looking for new start point...\n");
1604 });
07be1b83 1605 } else {
786e8c11
YO
1606 DEBUG_TRIE_EXECUTE_r(
1607 PerlIO_printf( Perl_debug_log,"No match.\n"));
07be1b83
YO
1608 break;
1609 }
1610 }
be8e71aa
YO
1611 FREETMPS;
1612 LEAVE;
07be1b83
YO
1613 }
1614 break;
b3c9acc1 1615 default:
3c3eec57
GS
1616 Perl_croak(aTHX_ "panic: unknown regstclass %d", (int)OP(c));
1617 break;
d6a28714 1618 }
6eb5f6b9
JH
1619 return 0;
1620 got_it:
1621 return s;
1622}
1623
1624/*
1625 - regexec_flags - match a regexp against a string
1626 */
1627I32
1628Perl_regexec_flags(pTHX_ register regexp *prog, char *stringarg, register char *strend,
1629 char *strbeg, I32 minend, SV *sv, void *data, U32 flags)
1630/* strend: pointer to null at end of string */
1631/* strbeg: real beginning of string */
1632/* minend: end of match must be >=minend after stringarg. */
1633/* data: May be used for some additional optimizations. */
1634/* nosave: For optimizations. */
1635{
97aff369 1636 dVAR;
6eb5f6b9
JH
1637 register char *s;
1638 register regnode *c;
1639 register char *startpos = stringarg;
6eb5f6b9
JH
1640 I32 minlen; /* must match at least this many chars */
1641 I32 dontbother = 0; /* how many characters not to try at end */
6eb5f6b9
JH
1642 I32 end_shift = 0; /* Same for the end. */ /* CC */
1643 I32 scream_pos = -1; /* Internal iterator of scream. */
ccac19ea 1644 char *scream_olds = NULL;
3dab1dad 1645 SV* const oreplsv = GvSV(PL_replgv);
f9f4320a 1646 const bool do_utf8 = (bool)DO_UTF8(sv);
2757e526 1647 I32 multiline;
0df25f3d 1648
3b0527fe 1649 regmatch_info reginfo; /* create some info to pass to regtry etc */
a3621e74
YO
1650
1651 GET_RE_DEBUG_FLAGS_DECL;
1652
9d4ba2ae 1653 PERL_UNUSED_ARG(data);
6eb5f6b9
JH
1654
1655 /* Be paranoid... */
1656 if (prog == NULL || startpos == NULL) {
1657 Perl_croak(aTHX_ "NULL regexp parameter");
1658 return 0;
1659 }
1660
2757e526 1661 multiline = prog->reganch & PMf_MULTILINE;
3b0527fe 1662 reginfo.prog = prog;
2757e526 1663
bac06658 1664 RX_MATCH_UTF8_set(prog, do_utf8);
1de06328
YO
1665 DEBUG_EXECUTE_r(
1666 debug_start_match(prog, do_utf8, startpos, strend,
1667 "Matching");
1668 );
bac06658 1669
6eb5f6b9 1670 minlen = prog->minlen;
1de06328
YO
1671
1672 if (strend - startpos < (minlen+(prog->check_offset_min<0?prog->check_offset_min:0))) {
a3621e74 1673 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
a72c7584
JH
1674 "String too short [regexec_flags]...\n"));
1675 goto phooey;
1aa99e6b 1676 }
6eb5f6b9 1677
1de06328 1678
6eb5f6b9
JH
1679 /* Check validity of program. */
1680 if (UCHARAT(prog->program) != REG_MAGIC) {
1681 Perl_croak(aTHX_ "corrupted regexp program");
1682 }
1683
1684 PL_reg_flags = 0;
1685 PL_reg_eval_set = 0;
1686 PL_reg_maxiter = 0;
1687
1688 if (prog->reganch & ROPT_UTF8)
1689 PL_reg_flags |= RF_utf8;
1690
1691 /* Mark beginning of line for ^ and lookbehind. */
3b0527fe 1692 reginfo.bol = startpos; /* XXX not used ??? */
6eb5f6b9 1693 PL_bostr = strbeg;
3b0527fe 1694 reginfo.sv = sv;
6eb5f6b9
JH
1695
1696 /* Mark end of line for $ (and such) */
1697 PL_regeol = strend;
1698
1699 /* see how far we have to get to not match where we matched before */
3b0527fe 1700 reginfo.till = startpos+minend;
6eb5f6b9 1701
6eb5f6b9
JH
1702 /* If there is a "must appear" string, look for it. */
1703 s = startpos;
1704
3b0527fe 1705 if (prog->reganch & ROPT_GPOS_SEEN) { /* Need to set reginfo->ganch */
6eb5f6b9
JH
1706 MAGIC *mg;
1707
1708 if (flags & REXEC_IGNOREPOS) /* Means: check only at start */
3b0527fe 1709 reginfo.ganch = startpos;
6eb5f6b9
JH
1710 else if (sv && SvTYPE(sv) >= SVt_PVMG
1711 && SvMAGIC(sv)
14befaf4
DM
1712 && (mg = mg_find(sv, PERL_MAGIC_regex_global))
1713 && mg->mg_len >= 0) {
3b0527fe 1714 reginfo.ganch = strbeg + mg->mg_len; /* Defined pos() */
6eb5f6b9 1715 if (prog->reganch & ROPT_ANCH_GPOS) {
3b0527fe 1716 if (s > reginfo.ganch)
6eb5f6b9 1717 goto phooey;
3b0527fe 1718 s = reginfo.ganch;
6eb5f6b9
JH
1719 }
1720 }
1721 else /* pos() not defined */
3b0527fe 1722 reginfo.ganch = strbeg;
6eb5f6b9
JH
1723 }
1724
a0714e2c 1725 if (!(flags & REXEC_CHECKED) && (prog->check_substr != NULL || prog->check_utf8 != NULL)) {
6eb5f6b9
JH
1726 re_scream_pos_data d;
1727
1728 d.scream_olds = &scream_olds;
1729 d.scream_pos = &scream_pos;
1730 s = re_intuit_start(prog, sv, s, strend, flags, &d);
3fa9c3d7 1731 if (!s) {
a3621e74 1732 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "Not present...\n"));
6eb5f6b9 1733 goto phooey; /* not present */
3fa9c3d7 1734 }
6eb5f6b9
JH
1735 }
1736
1de06328 1737
6eb5f6b9
JH
1738
1739 /* Simplest case: anchored match need be tried only once. */
1740 /* [unless only anchor is BOL and multiline is set] */
1741 if (prog->reganch & (ROPT_ANCH & ~ROPT_ANCH_GPOS)) {
3b0527fe 1742 if (s == startpos && regtry(&reginfo, startpos))
6eb5f6b9 1743 goto got_it;
7fba1cd6 1744 else if (multiline || (prog->reganch & ROPT_IMPLICIT)
6eb5f6b9
JH
1745 || (prog->reganch & ROPT_ANCH_MBOL)) /* XXXX SBOL? */
1746 {
1747 char *end;
1748
1749 if (minlen)
1750 dontbother = minlen - 1;
1aa99e6b 1751 end = HOP3c(strend, -dontbother, strbeg) - 1;
6eb5f6b9 1752 /* for multiline we only have to try after newlines */
33b8afdf 1753 if (prog->check_substr || prog->check_utf8) {
6eb5f6b9
JH
1754 if (s == startpos)
1755 goto after_try;
1756 while (1) {
3b0527fe 1757 if (regtry(&reginfo, s))
6eb5f6b9
JH
1758 goto got_it;
1759 after_try:
1760 if (s >= end)
1761 goto phooey;
1762 if (prog->reganch & RE_USE_INTUIT) {
1763 s = re_intuit_start(prog, sv, s + 1, strend, flags, NULL);
1764 if (!s)
1765 goto phooey;
1766 }
1767 else
1768 s++;
1769 }
1770 } else {
1771 if (s > startpos)
1772 s--;
1773 while (s < end) {
1774 if (*s++ == '\n') { /* don't need PL_utf8skip here */
3b0527fe 1775 if (regtry(&reginfo, s))
6eb5f6b9
JH
1776 goto got_it;
1777 }
1778 }
1779 }
1780 }
1781 goto phooey;
f9f4320a
YO
1782 } else if (ROPT_GPOS_CHECK == (prog->reganch & ROPT_GPOS_CHECK))
1783 {
1784 /* the warning about reginfo.ganch being used without intialization
1785 is bogus -- we set it above, when prog->reganch & ROPT_GPOS_SEEN
1786 and we only enter this block when the same bit is set. */
3b0527fe 1787 if (regtry(&reginfo, reginfo.ganch))
6eb5f6b9
JH
1788 goto got_it;
1789 goto phooey;
1790 }
1791
1792 /* Messy cases: unanchored match. */
33b8afdf 1793 if ((prog->anchored_substr || prog->anchored_utf8) && prog->reganch & ROPT_SKIP) {
6eb5f6b9
JH
1794 /* we have /x+whatever/ */
1795 /* it must be a one character string (XXXX Except UTF?) */
33b8afdf 1796 char ch;
bf93d4cc
GS
1797#ifdef DEBUGGING
1798 int did_match = 0;
1799#endif
33b8afdf
JH
1800 if (!(do_utf8 ? prog->anchored_utf8 : prog->anchored_substr))
1801 do_utf8 ? to_utf8_substr(prog) : to_byte_substr(prog);
3f7c398e 1802 ch = SvPVX_const(do_utf8 ? prog->anchored_utf8 : prog->anchored_substr)[0];
bf93d4cc 1803
1aa99e6b 1804 if (do_utf8) {
4cadc6a9 1805 REXEC_FBC_SCAN(
6eb5f6b9 1806 if (*s == ch) {
a3621e74 1807 DEBUG_EXECUTE_r( did_match = 1 );
3b0527fe 1808 if (regtry(&reginfo, s)) goto got_it;
6eb5f6b9
JH
1809 s += UTF8SKIP(s);
1810 while (s < strend && *s == ch)
1811 s += UTF8SKIP(s);
1812 }
4cadc6a9 1813 );
6eb5f6b9
JH
1814 }
1815 else {
4cadc6a9 1816 REXEC_FBC_SCAN(
6eb5f6b9 1817 if (*s == ch) {
a3621e74 1818 DEBUG_EXECUTE_r( did_match = 1 );
3b0527fe 1819 if (regtry(&reginfo, s)) goto got_it;
6eb5f6b9
JH
1820 s++;
1821 while (s < strend && *s == ch)
1822 s++;
1823 }
4cadc6a9 1824 );
6eb5f6b9 1825 }
a3621e74 1826 DEBUG_EXECUTE_r(if (!did_match)
bf93d4cc 1827 PerlIO_printf(Perl_debug_log,
b7953727
JH
1828 "Did not find anchored character...\n")
1829 );
6eb5f6b9 1830 }
a0714e2c
SS
1831 else if (prog->anchored_substr != NULL
1832 || prog->anchored_utf8 != NULL
1833 || ((prog->float_substr != NULL || prog->float_utf8 != NULL)
33b8afdf
JH
1834 && prog->float_max_offset < strend - s)) {
1835 SV *must;
1836 I32 back_max;
1837 I32 back_min;
1838 char *last;
6eb5f6b9 1839 char *last1; /* Last position checked before */
bf93d4cc
GS
1840#ifdef DEBUGGING
1841 int did_match = 0;
1842#endif
33b8afdf
JH
1843 if (prog->anchored_substr || prog->anchored_utf8) {
1844 if (!(do_utf8 ? prog->anchored_utf8 : prog->anchored_substr))
1845 do_utf8 ? to_utf8_substr(prog) : to_byte_substr(prog);
1846 must = do_utf8 ? prog->anchored_utf8 : prog->anchored_substr;
1847 back_max = back_min = prog->anchored_offset;
1848 } else {
1849 if (!(do_utf8 ? prog->float_utf8 : prog->float_substr))
1850 do_utf8 ? to_utf8_substr(prog) : to_byte_substr(prog);
1851 must = do_utf8 ? prog->float_utf8 : prog->float_substr;
1852 back_max = prog->float_max_offset;
1853 back_min = prog->float_min_offset;
1854 }
1de06328
YO
1855
1856
33b8afdf
JH
1857 if (must == &PL_sv_undef)
1858 /* could not downgrade utf8 check substring, so must fail */
1859 goto phooey;
1860
1de06328
YO
1861 if (back_min<0) {
1862 last = strend;
1863 } else {
1864 last = HOP3c(strend, /* Cannot start after this */
1865 -(I32)(CHR_SVLEN(must)
1866 - (SvTAIL(must) != 0) + back_min), strbeg);
1867 }
6eb5f6b9
JH
1868 if (s > PL_bostr)
1869 last1 = HOPc(s, -1);
1870 else
1871 last1 = s - 1; /* bogus */
1872
a0288114 1873 /* XXXX check_substr already used to find "s", can optimize if
6eb5f6b9
JH
1874 check_substr==must. */
1875 scream_pos = -1;
1876 dontbother = end_shift;
1877 strend = HOPc(strend, -dontbother);
1878 while ( (s <= last) &&
9041c2e3 1879 ((flags & REXEC_SCREAM)
1de06328 1880 ? (s = screaminstr(sv, must, HOP3c(s, back_min, (back_min<0 ? strbeg : strend)) - strbeg,
6eb5f6b9 1881 end_shift, &scream_pos, 0))
1de06328 1882 : (s = fbm_instr((unsigned char*)HOP3(s, back_min, (back_min<0 ? strbeg : strend)),
9041c2e3 1883 (unsigned char*)strend, must,
7fba1cd6 1884 multiline ? FBMrf_MULTILINE : 0))) ) {
4addbd3b
HS
1885 /* we may be pointing at the wrong string */
1886 if ((flags & REXEC_SCREAM) && RX_MATCH_COPIED(prog))
3f7c398e 1887 s = strbeg + (s - SvPVX_const(sv));
a3621e74 1888 DEBUG_EXECUTE_r( did_match = 1 );
6eb5f6b9
JH
1889 if (HOPc(s, -back_max) > last1) {
1890 last1 = HOPc(s, -back_min);
1891 s = HOPc(s, -back_max);
1892 }
1893 else {
52657f30 1894 char * const t = (last1 >= PL_bostr) ? HOPc(last1, 1) : last1 + 1;
6eb5f6b9
JH
1895
1896 last1 = HOPc(s, -back_min);
52657f30 1897 s = t;
6eb5f6b9 1898 }
1aa99e6b 1899 if (do_utf8) {
6eb5f6b9 1900 while (s <= last1) {
3b0527fe 1901 if (regtry(&reginfo, s))
6eb5f6b9
JH
1902 goto got_it;
1903 s += UTF8SKIP(s);
1904 }
1905 }
1906 else {
1907 while (s <= last1) {
3b0527fe 1908 if (regtry(&reginfo, s))
6eb5f6b9
JH
1909 goto got_it;
1910 s++;
1911 }
1912 }
1913 }
ab3bbdeb
YO
1914 DEBUG_EXECUTE_r(if (!did_match) {
1915 RE_PV_QUOTED_DECL(quoted, do_utf8, PERL_DEBUG_PAD_ZERO(0),
1916 SvPVX_const(must), RE_SV_DUMPLEN(must), 30);
1917 PerlIO_printf(Perl_debug_log, "Did not find %s substr %s%s...\n",
33b8afdf 1918 ((must == prog->anchored_substr || must == prog->anchored_utf8)
bf93d4cc 1919 ? "anchored" : "floating"),
ab3bbdeb
YO
1920 quoted, RE_SV_TAIL(must));
1921 });
6eb5f6b9
JH
1922 goto phooey;
1923 }
786e8c11 1924 else if ( (c = prog->regstclass) ) {
f14c76ed 1925 if (minlen) {
be8e71aa 1926 const OPCODE op = OP(prog->regstclass);
66e933ab 1927 /* don't bother with what can't match */
786e8c11 1928 if (PL_regkind[op] != EXACT && op != CANY && PL_regkind[op] != TRIE)
f14c76ed
RGS
1929 strend = HOPc(strend, -(minlen - 1));
1930 }
a3621e74 1931 DEBUG_EXECUTE_r({
be8e71aa 1932 SV * const prop = sv_newmortal();
32fc9b6a 1933 regprop(prog, prop, c);
0df25f3d 1934 {
ab3bbdeb
YO
1935 RE_PV_QUOTED_DECL(quoted,UTF,PERL_DEBUG_PAD_ZERO(1),
1936 s,strend-s,60);
0df25f3d 1937 PerlIO_printf(Perl_debug_log,
ab3bbdeb 1938 "Matching stclass %.*s against %s (%d chars)\n",
e4f74956 1939 (int)SvCUR(prop), SvPVX_const(prop),
ab3bbdeb 1940 quoted, (int)(strend - s));
0df25f3d 1941 }
ffc61ed2 1942 });
3b0527fe 1943 if (find_byclass(prog, c, s, strend, &reginfo))
6eb5f6b9 1944 goto got_it;
07be1b83 1945 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "Contradicts stclass... [regexec_flags]\n"));
d6a28714
JH
1946 }
1947 else {
1948 dontbother = 0;
a0714e2c 1949 if (prog->float_substr != NULL || prog->float_utf8 != NULL) {
33b8afdf 1950 /* Trim the end. */
d6a28714 1951 char *last;
33b8afdf
JH
1952 SV* float_real;
1953
1954 if (!(do_utf8 ? prog->float_utf8 : prog->float_substr))
1955 do_utf8 ? to_utf8_substr(prog) : to_byte_substr(prog);
1956 float_real = do_utf8 ? prog->float_utf8 : prog->float_substr;
d6a28714
JH
1957
1958 if (flags & REXEC_SCREAM) {
33b8afdf 1959 last = screaminstr(sv, float_real, s - strbeg,
d6a28714
JH
1960 end_shift, &scream_pos, 1); /* last one */
1961 if (!last)
ffc61ed2 1962 last = scream_olds; /* Only one occurrence. */
4addbd3b
HS
1963 /* we may be pointing at the wrong string */
1964 else if (RX_MATCH_COPIED(prog))
3f7c398e 1965 s = strbeg + (s - SvPVX_const(sv));
b8c5462f 1966 }
d6a28714
JH
1967 else {
1968 STRLEN len;
cfd0369c 1969 const char * const little = SvPV_const(float_real, len);
d6a28714 1970
33b8afdf 1971 if (SvTAIL(float_real)) {
d6a28714
JH
1972 if (memEQ(strend - len + 1, little, len - 1))
1973 last = strend - len + 1;
7fba1cd6 1974 else if (!multiline)
9041c2e3 1975 last = memEQ(strend - len, little, len)
bd61b366 1976 ? strend - len : NULL;
b8c5462f 1977 else
d6a28714
JH
1978 goto find_last;
1979 } else {
1980 find_last:
9041c2e3 1981 if (len)
d6a28714 1982 last = rninstr(s, strend, little, little + len);
b8c5462f 1983 else
a0288114 1984 last = strend; /* matching "$" */
b8c5462f 1985 }
b8c5462f 1986 }
bf93d4cc 1987 if (last == NULL) {
6bda09f9
YO
1988 DEBUG_EXECUTE_r(
1989 PerlIO_printf(Perl_debug_log,
1990 "%sCan't trim the tail, match fails (should not happen)%s\n",
1991 PL_colors[4], PL_colors[5]));
bf93d4cc
GS
1992 goto phooey; /* Should not happen! */
1993 }
d6a28714
JH
1994 dontbother = strend - last + prog->float_min_offset;
1995 }
1996 if (minlen && (dontbother < minlen))
1997 dontbother = minlen - 1;
1998 strend -= dontbother; /* this one's always in bytes! */
1999 /* We don't know much -- general case. */
1aa99e6b 2000 if (do_utf8) {
d6a28714 2001 for (;;) {
3b0527fe 2002 if (regtry(&reginfo, s))
d6a28714
JH
2003 goto got_it;
2004 if (s >= strend)
2005 break;
b8c5462f 2006 s += UTF8SKIP(s);
d6a28714
JH
2007 };
2008 }
2009 else {
2010 do {
3b0527fe 2011 if (regtry(&reginfo, s))
d6a28714
JH
2012 goto got_it;
2013 } while (s++ < strend);
2014 }
2015 }
2016
2017 /* Failure. */
2018 goto phooey;
2019
2020got_it:
2021 RX_MATCH_TAINTED_set(prog, PL_reg_flags & RF_tainted);
2022
2023 if (PL_reg_eval_set) {
2024 /* Preserve the current value of $^R */
2025 if (oreplsv != GvSV(PL_replgv))
2026 sv_setsv(oreplsv, GvSV(PL_replgv));/* So that when GvSV(replgv) is
2027 restored, the value remains
2028 the same. */
4f639d21 2029 restore_pos(aTHX_ prog);
d6a28714
JH
2030 }
2031
2032 /* make sure $`, $&, $', and $digit will work later */
2033 if ( !(flags & REXEC_NOT_FIRST) ) {
ed252734 2034 RX_MATCH_COPY_FREE(prog);
d6a28714 2035 if (flags & REXEC_COPY_STR) {
be8e71aa 2036 const I32 i = PL_regeol - startpos + (stringarg - strbeg);
f8c7b90f 2037#ifdef PERL_OLD_COPY_ON_WRITE
ed252734
NC
2038 if ((SvIsCOW(sv)
2039 || (SvFLAGS(sv) & CAN_COW_MASK) == CAN_COW_FLAGS)) {
2040 if (DEBUG_C_TEST) {
2041 PerlIO_printf(Perl_debug_log,
2042 "Copy on write: regexp capture, type %d\n",
2043 (int) SvTYPE(sv));
2044 }
2045 prog->saved_copy = sv_setsv_cow(prog->saved_copy, sv);
d5263905 2046 prog->subbeg = (char *)SvPVX_const(prog->saved_copy);
ed252734
NC
2047 assert (SvPOKp(prog->saved_copy));
2048 } else
2049#endif
2050 {
2051 RX_MATCH_COPIED_on(prog);
2052 s = savepvn(strbeg, i);
2053 prog->subbeg = s;
2054 }
d6a28714 2055 prog->sublen = i;
d6a28714
JH
2056 }
2057 else {
2058 prog->subbeg = strbeg;
2059 prog->sublen = PL_regeol - strbeg; /* strend may have been modified */
2060 }
2061 }
9041c2e3 2062
d6a28714
JH
2063 return 1;
2064
2065phooey:
a3621e74 2066 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "%sMatch failed%s\n",
e4584336 2067 PL_colors[4], PL_colors[5]));
d6a28714 2068 if (PL_reg_eval_set)
4f639d21 2069 restore_pos(aTHX_ prog);
d6a28714
JH
2070 return 0;
2071}
2072
6bda09f9 2073
d6a28714
JH
2074/*
2075 - regtry - try match at specific point
2076 */
2077STATIC I32 /* 0 failure, 1 success */
3b0527fe 2078S_regtry(pTHX_ const regmatch_info *reginfo, char *startpos)
d6a28714 2079{
97aff369 2080 dVAR;
d6a28714
JH
2081 register I32 *sp;
2082 register I32 *ep;
2083 CHECKPOINT lastcp;
3b0527fe 2084 regexp *prog = reginfo->prog;
a3621e74 2085 GET_RE_DEBUG_FLAGS_DECL;
d6a28714
JH
2086
2087 if ((prog->reganch & ROPT_EVAL_SEEN) && !PL_reg_eval_set) {
2088 MAGIC *mg;
2089
2090 PL_reg_eval_set = RS_init;
a3621e74 2091 DEBUG_EXECUTE_r(DEBUG_s(
b900a521
JH
2092 PerlIO_printf(Perl_debug_log, " setting stack tmpbase at %"IVdf"\n",
2093 (IV)(PL_stack_sp - PL_stack_base));
d6a28714 2094 ));
e8347627 2095 SAVEI32(cxstack[cxstack_ix].blk_oldsp);
d6a28714
JH
2096 cxstack[cxstack_ix].blk_oldsp = PL_stack_sp - PL_stack_base;
2097 /* Otherwise OP_NEXTSTATE will free whatever on stack now. */
2098 SAVETMPS;
2099 /* Apparently this is not needed, judging by wantarray. */
e8347627 2100 /* SAVEI8(cxstack[cxstack_ix].blk_gimme);
d6a28714
JH
2101 cxstack[cxstack_ix].blk_gimme = G_SCALAR; */
2102
3b0527fe 2103 if (reginfo->sv) {
d6a28714 2104 /* Make $_ available to executed code. */
3b0527fe 2105 if (reginfo->sv != DEFSV) {
59f00321 2106 SAVE_DEFSV;
3b0527fe 2107 DEFSV = reginfo->sv;
b8c5462f 2108 }
d6a28714 2109
3b0527fe
DM
2110 if (!(SvTYPE(reginfo->sv) >= SVt_PVMG && SvMAGIC(reginfo->sv)
2111 && (mg = mg_find(reginfo->sv, PERL_MAGIC_regex_global)))) {
d6a28714 2112 /* prepare for quick setting of pos */
d300d9fa
NC
2113#ifdef PERL_OLD_COPY_ON_WRITE
2114 if (SvIsCOW(sv))
2115 sv_force_normal_flags(sv, 0);
2116#endif
3dab1dad 2117 mg = sv_magicext(reginfo->sv, NULL, PERL_MAGIC_regex_global,
d300d9fa 2118 &PL_vtbl_mglob, NULL, 0);
d6a28714 2119 mg->mg_len = -1;
b8c5462f 2120 }
d6a28714
JH
2121 PL_reg_magic = mg;
2122 PL_reg_oldpos = mg->mg_len;
4f639d21 2123 SAVEDESTRUCTOR_X(restore_pos, prog);
d6a28714 2124 }
09687e5a 2125 if (!PL_reg_curpm) {
a02a5408 2126 Newxz(PL_reg_curpm, 1, PMOP);
09687e5a
AB
2127#ifdef USE_ITHREADS
2128 {
be8e71aa 2129 SV* const repointer = newSViv(0);
577e12cc 2130 /* so we know which PL_regex_padav element is PL_reg_curpm */
35061a7e 2131 SvFLAGS(repointer) |= SVf_BREAK;
09687e5a
AB
2132 av_push(PL_regex_padav,repointer);
2133 PL_reg_curpm->op_pmoffset = av_len(PL_regex_padav);
2134 PL_regex_pad = AvARRAY(PL_regex_padav);
2135 }
2136#endif
2137 }
aaa362c4 2138 PM_SETRE(PL_reg_curpm, prog);
d6a28714
JH
2139 PL_reg_oldcurpm = PL_curpm;
2140 PL_curpm = PL_reg_curpm;
2141 if (RX_MATCH_COPIED(prog)) {
2142 /* Here is a serious problem: we cannot rewrite subbeg,
2143 since it may be needed if this match fails. Thus
2144 $` inside (?{}) could fail... */
2145 PL_reg_oldsaved = prog->subbeg;
2146 PL_reg_oldsavedlen = prog->sublen;
f8c7b90f 2147#ifdef PERL_OLD_COPY_ON_WRITE
ed252734
NC
2148 PL_nrs = prog->saved_copy;
2149#endif
d6a28714
JH
2150 RX_MATCH_COPIED_off(prog);
2151 }
2152 else
bd61b366 2153 PL_reg_oldsaved = NULL;
d6a28714
JH
2154 prog->subbeg = PL_bostr;
2155 prog->sublen = PL_regeol - PL_bostr; /* strend may have been modified */
2156 }
6bda09f9 2157 DEBUG_EXECUTE_r(PL_reg_starttry = startpos);
973dddac 2158 prog->startp[0] = startpos - PL_bostr;
d6a28714 2159 PL_reginput = startpos;
d6a28714 2160 PL_reglastparen = &prog->lastparen;
a01268b5 2161 PL_reglastcloseparen = &prog->lastcloseparen;
d6a28714 2162 prog->lastparen = 0;
03994de8 2163 prog->lastcloseparen = 0;
d6a28714 2164 PL_regsize = 0;
6bda09f9
YO
2165 PL_regstartp = prog->startp;
2166 PL_regendp = prog->endp;
d6a28714
JH
2167 if (PL_reg_start_tmpl <= prog->nparens) {
2168 PL_reg_start_tmpl = prog->nparens*3/2 + 3;
2169 if(PL_reg_start_tmp)
2170 Renew(PL_reg_start_tmp, PL_reg_start_tmpl, char*);
2171 else
a02a5408 2172 Newx(PL_reg_start_tmp, PL_reg_start_tmpl, char*);
d6a28714
JH
2173 }
2174
2175 /* XXXX What this code is doing here?!!! There should be no need
2176 to do this again and again, PL_reglastparen should take care of
3dd2943c 2177 this! --ilya*/
dafc8851
JH
2178
2179 /* Tests pat.t#187 and split.t#{13,14} seem to depend on this code.
2180 * Actually, the code in regcppop() (which Ilya may be meaning by
daf18116
JH
2181 * PL_reglastparen), is not needed at all by the test suite
2182 * (op/regexp, op/pat, op/split), but that code is needed, oddly
2183 * enough, for building DynaLoader, or otherwise this
2184 * "Error: '*' not in typemap in DynaLoader.xs, line 164"
2185 * will happen. Meanwhile, this code *is* needed for the
2186 * above-mentioned test suite tests to succeed. The common theme
2187 * on those tests seems to be returning null fields from matches.
2188 * --jhi */
dafc8851 2189#if 1
d6a28714
JH
2190 sp = prog->startp;
2191 ep = prog->endp;
2192 if (prog->nparens) {
097eb12c 2193 register I32 i;
eb160463 2194 for (i = prog->nparens; i > (I32)*PL_reglastparen; i--) {
d6a28714
JH
2195 *++sp = -1;
2196 *++ep = -1;
2197 }
2198 }
dafc8851 2199#endif
02db2b7b 2200 REGCP_SET(lastcp);
3b0527fe 2201 if (regmatch(reginfo, prog->program + 1)) {
d6a28714
JH
2202 prog->endp[0] = PL_reginput - PL_bostr;
2203 return 1;
2204 }
02db2b7b 2205 REGCP_UNWIND(lastcp);
d6a28714
JH
2206 return 0;
2207}
2208
02db2b7b 2209
8ba1375e
MJD
2210#define sayYES goto yes
2211#define sayNO goto no
262b90c4 2212#define sayNO_SILENT goto no_silent
8ba1375e 2213
f9f4320a
YO
2214/* we dont use STMT_START/END here because it leads to
2215 "unreachable code" warnings, which are bogus, but distracting. */
2216#define CACHEsayNO \
c476f425
DM
2217 if (ST.cache_mask) \
2218 PL_reg_poscache[ST.cache_offset] |= ST.cache_mask; \
f9f4320a 2219 sayNO
3298f257 2220
a3621e74 2221/* this is used to determine how far from the left messages like
265c4333
YO
2222 'failed...' are printed. It should be set such that messages
2223 are inline with the regop output that created them.
a3621e74 2224*/
265c4333 2225#define REPORT_CODE_OFF 32
a3621e74
YO
2226
2227
2228/* Make sure there is a test for this +1 options in re_tests */
2229#define TRIE_INITAL_ACCEPT_BUFFLEN 4;
2230
40a82448
DM
2231#define CHRTEST_UNINIT -1001 /* c1/c2 haven't been calculated yet */
2232#define CHRTEST_VOID -1000 /* the c1/c2 "next char" test should be skipped */
9e137952 2233
86545054
DM
2234#define SLAB_FIRST(s) (&(s)->states[0])
2235#define SLAB_LAST(s) (&(s)->states[PERL_REGMATCH_SLAB_SLOTS-1])
2236
5d9a96ca
DM
2237/* grab a new slab and return the first slot in it */
2238
2239STATIC regmatch_state *
2240S_push_slab(pTHX)
2241{
54df2634
NC
2242#if PERL_VERSION < 9
2243 dMY_CXT;
2244#endif
5d9a96ca
DM
2245 regmatch_slab *s = PL_regmatch_slab->next;
2246 if (!s) {
2247 Newx(s, 1, regmatch_slab);
2248 s->prev = PL_regmatch_slab;
2249 s->next = NULL;
2250 PL_regmatch_slab->next = s;
2251 }
2252 PL_regmatch_slab = s;
86545054 2253 return SLAB_FIRST(s);
5d9a96ca 2254}
5b47454d 2255
95b24440 2256
40a82448
DM
2257/* push a new state then goto it */
2258
2259#define PUSH_STATE_GOTO(state, node) \
2260 scan = node; \
2261 st->resume_state = state; \
2262 goto push_state;
2263
2264/* push a new state with success backtracking, then goto it */
2265
2266#define PUSH_YES_STATE_GOTO(state, node) \
2267 scan = node; \
2268 st->resume_state = state; \
2269 goto push_yes_state;
2270
aa283a38 2271
aa283a38 2272
d6a28714 2273/*
95b24440 2274
bf1f174e
DM
2275regmatch() - main matching routine
2276
2277This is basically one big switch statement in a loop. We execute an op,
2278set 'next' to point the next op, and continue. If we come to a point which
2279we may need to backtrack to on failure such as (A|B|C), we push a
2280backtrack state onto the backtrack stack. On failure, we pop the top
2281state, and re-enter the loop at the state indicated. If there are no more
2282states to pop, we return failure.
2283
2284Sometimes we also need to backtrack on success; for example /A+/, where
2285after successfully matching one A, we need to go back and try to
2286match another one; similarly for lookahead assertions: if the assertion
2287completes successfully, we backtrack to the state just before the assertion
2288and then carry on. In these cases, the pushed state is marked as
2289'backtrack on success too'. This marking is in fact done by a chain of
2290pointers, each pointing to the previous 'yes' state. On success, we pop to
2291the nearest yes state, discarding any intermediate failure-only states.
2292Sometimes a yes state is pushed just to force some cleanup code to be
2293called at the end of a successful match or submatch; e.g. (??{$re}) uses
2294it to free the inner regex.
2295
2296Note that failure backtracking rewinds the cursor position, while
2297success backtracking leaves it alone.
2298
2299A pattern is complete when the END op is executed, while a subpattern
2300such as (?=foo) is complete when the SUCCESS op is executed. Both of these
2301ops trigger the "pop to last yes state if any, otherwise return true"
2302behaviour.
2303
2304A common convention in this function is to use A and B to refer to the two
2305subpatterns (or to the first nodes thereof) in patterns like /A*B/: so A is
2306the subpattern to be matched possibly multiple times, while B is the entire
2307rest of the pattern. Variable and state names reflect this convention.
2308
2309The states in the main switch are the union of ops and failure/success of
2310substates associated with with that op. For example, IFMATCH is the op
2311that does lookahead assertions /(?=A)B/ and so the IFMATCH state means
2312'execute IFMATCH'; while IFMATCH_A is a state saying that we have just
2313successfully matched A and IFMATCH_A_fail is a state saying that we have
2314just failed to match A. Resume states always come in pairs. The backtrack
2315state we push is marked as 'IFMATCH_A', but when that is popped, we resume
2316at IFMATCH_A or IFMATCH_A_fail, depending on whether we are backtracking
2317on success or failure.
2318
2319The struct that holds a backtracking state is actually a big union, with
2320one variant for each major type of op. The variable st points to the
2321top-most backtrack struct. To make the code clearer, within each
2322block of code we #define ST to alias the relevant union.
2323
2324Here's a concrete example of a (vastly oversimplified) IFMATCH
2325implementation:
2326
2327 switch (state) {
2328 ....
2329
2330#define ST st->u.ifmatch
2331
2332 case IFMATCH: // we are executing the IFMATCH op, (?=A)B
2333 ST.foo = ...; // some state we wish to save
95b24440 2334 ...
bf1f174e
DM
2335 // push a yes backtrack state with a resume value of
2336 // IFMATCH_A/IFMATCH_A_fail, then continue execution at the
2337 // first node of A:
2338 PUSH_YES_STATE_GOTO(IFMATCH_A, A);
2339 // NOTREACHED
2340
2341 case IFMATCH_A: // we have successfully executed A; now continue with B
2342 next = B;
2343 bar = ST.foo; // do something with the preserved value
2344 break;
2345
2346 case IFMATCH_A_fail: // A failed, so the assertion failed
2347 ...; // do some housekeeping, then ...
2348 sayNO; // propagate the failure
2349
2350#undef ST
95b24440 2351
bf1f174e
DM
2352 ...
2353 }
95b24440 2354
bf1f174e
DM
2355For any old-timers reading this who are familiar with the old recursive
2356approach, the code above is equivalent to:
95b24440 2357
bf1f174e
DM
2358 case IFMATCH: // we are executing the IFMATCH op, (?=A)B
2359 {
2360 int foo = ...
95b24440 2361 ...
bf1f174e
DM
2362 if (regmatch(A)) {
2363 next = B;
2364 bar = foo;
2365 break;
95b24440 2366 }
bf1f174e
DM
2367 ...; // do some housekeeping, then ...
2368 sayNO; // propagate the failure
95b24440 2369 }
bf1f174e
DM
2370
2371The topmost backtrack state, pointed to by st, is usually free. If you
2372want to claim it, populate any ST.foo fields in it with values you wish to
2373save, then do one of
2374
2375 PUSH_STATE_GOTO(resume_state, node);
2376 PUSH_YES_STATE_GOTO(resume_state, node);
2377
2378which sets that backtrack state's resume value to 'resume_state', pushes a
2379new free entry to the top of the backtrack stack, then goes to 'node'.
2380On backtracking, the free slot is popped, and the saved state becomes the
2381new free state. An ST.foo field in this new top state can be temporarily
2382accessed to retrieve values, but once the main loop is re-entered, it
2383becomes available for reuse.
2384
2385Note that the depth of the backtrack stack constantly increases during the
2386left-to-right execution of the pattern, rather than going up and down with
2387the pattern nesting. For example the stack is at its maximum at Z at the
2388end of the pattern, rather than at X in the following:
2389
2390 /(((X)+)+)+....(Y)+....Z/
2391
2392The only exceptions to this are lookahead/behind assertions and the cut,
2393(?>A), which pop all the backtrack states associated with A before
2394continuing.
2395
2396Bascktrack state structs are allocated in slabs of about 4K in size.
2397PL_regmatch_state and st always point to the currently active state,
2398and PL_regmatch_slab points to the slab currently containing
2399PL_regmatch_state. The first time regmatch() is called, the first slab is
2400allocated, and is never freed until interpreter destruction. When the slab
2401is full, a new one is allocated and chained to the end. At exit from
2402regmatch(), slabs allocated since entry are freed.
2403
2404*/
95b24440 2405
40a82448 2406
5bc10b2c 2407#define DEBUG_STATE_pp(pp) \
265c4333 2408 DEBUG_STATE_r({ \
5bc10b2c
DM
2409 DUMP_EXEC_POS(locinput, scan, do_utf8); \
2410 PerlIO_printf(Perl_debug_log, \
2411 " %*s"pp" %s\n", \
2412 depth*2, "", \
03363afd 2413 reg_name[st->resume_state] ); \
265c4333 2414 });
5bc10b2c 2415
40a82448 2416
3dab1dad 2417#define REG_NODE_NUM(x) ((x) ? (int)((x)-prog) : -1)
95b24440 2418
3df15adc 2419#ifdef DEBUGGING
5bc10b2c 2420
ab3bbdeb
YO
2421STATIC void
2422S_debug_start_match(pTHX_ const regexp *prog, const bool do_utf8,
2423 const char *start, const char *end, const char *blurb)
2424{
2425 const bool utf8_pat= prog->reganch & ROPT_UTF8 ? 1 : 0;
2426 if (!PL_colorset)
2427 reginitcolors();
2428 {
2429 RE_PV_QUOTED_DECL(s0, utf8_pat, PERL_DEBUG_PAD_ZERO(0),
2430 prog->precomp, prog->prelen, 60);
2431
2432 RE_PV_QUOTED_DECL(s1, do_utf8, PERL_DEBUG_PAD_ZERO(1),
2433 start, end - start, 60);
2434
2435 PerlIO_printf(Perl_debug_log,
2436 "%s%s REx%s %s against %s\n",
2437 PL_colors[4], blurb, PL_colors[5], s0, s1);
2438
2439 if (do_utf8||utf8_pat)
1de06328
YO
2440 PerlIO_printf(Perl_debug_log, "UTF-8 %s%s%s...\n",
2441 utf8_pat ? "pattern" : "",
2442 utf8_pat && do_utf8 ? " and " : "",
2443 do_utf8 ? "string" : ""
ab3bbdeb
YO
2444 );
2445 }
2446}
3df15adc
YO
2447
2448STATIC void
786e8c11
YO
2449S_dump_exec_pos(pTHX_ const char *locinput,
2450 const regnode *scan,
2451 const char *loc_regeol,
2452 const char *loc_bostr,
2453 const char *loc_reg_starttry,
2454 const bool do_utf8)
07be1b83 2455{
786e8c11 2456 const int docolor = *PL_colors[0] || *PL_colors[2] || *PL_colors[4];
07be1b83 2457 const int taill = (docolor ? 10 : 7); /* 3 chars for "> <" */
786e8c11 2458 int l = (loc_regeol - locinput) > taill ? taill : (loc_regeol - locinput);
07be1b83
YO
2459 /* The part of the string before starttry has one color
2460 (pref0_len chars), between starttry and current
2461 position another one (pref_len - pref0_len chars),
2462 after the current position the third one.
2463 We assume that pref0_len <= pref_len, otherwise we
2464 decrease pref0_len. */
786e8c11
YO
2465 int pref_len = (locinput - loc_bostr) > (5 + taill) - l
2466 ? (5 + taill) - l : locinput - loc_bostr;
07be1b83
YO
2467 int pref0_len;
2468
2469 while (do_utf8 && UTF8_IS_CONTINUATION(*(U8*)(locinput - pref_len)))
2470 pref_len++;
786e8c11
YO
2471 pref0_len = pref_len - (locinput - loc_reg_starttry);
2472 if (l + pref_len < (5 + taill) && l < loc_regeol - locinput)
2473 l = ( loc_regeol - locinput > (5 + taill) - pref_len
2474 ? (5 + taill) - pref_len : loc_regeol - locinput);
07be1b83
YO
2475 while (do_utf8 && UTF8_IS_CONTINUATION(*(U8*)(locinput + l)))
2476 l--;
2477 if (pref0_len < 0)
2478 pref0_len = 0;
2479 if (pref0_len > pref_len)
2480 pref0_len = pref_len;
2481 {
3df15adc 2482 const int is_uni = (do_utf8 && OP(scan) != CANY) ? 1 : 0;
0df25f3d 2483
ab3bbdeb 2484 RE_PV_COLOR_DECL(s0,len0,is_uni,PERL_DEBUG_PAD(0),
1de06328 2485 (locinput - pref_len),pref0_len, 60, 4, 5);
0df25f3d 2486
ab3bbdeb 2487 RE_PV_COLOR_DECL(s1,len1,is_uni,PERL_DEBUG_PAD(1),
3df15adc 2488 (locinput - pref_len + pref0_len),
1de06328 2489 pref_len - pref0_len, 60, 2, 3);
0df25f3d 2490
ab3bbdeb 2491 RE_PV_COLOR_DECL(s2,len2,is_uni,PERL_DEBUG_PAD(2),
1de06328 2492 locinput, loc_regeol - locinput, 10, 0, 1);
0df25f3d 2493
1de06328 2494 const STRLEN tlen=len0+len1+len2;
3df15adc 2495 PerlIO_printf(Perl_debug_log,
ab3bbdeb 2496 "%4"IVdf" <%.*s%.*s%s%.*s>%*s|",
786e8c11 2497 (IV)(locinput - loc_bostr),
07be1b83 2498 len0, s0,
07be1b83 2499 len1, s1,
07be1b83 2500 (docolor ? "" : "> <"),
07be1b83 2501 len2, s2,
f9f4320a 2502 (int)(tlen > 19 ? 0 : 19 - tlen),
07be1b83
YO
2503 "");
2504 }
2505}
3df15adc 2506
07be1b83
YO
2507#endif
2508
d6a28714 2509STATIC I32 /* 0 failure, 1 success */
3b0527fe 2510S_regmatch(pTHX_ const regmatch_info *reginfo, regnode *prog)
d6a28714 2511{
54df2634
NC
2512#if PERL_VERSION < 9
2513 dMY_CXT;
2514#endif
27da23d5 2515 dVAR;
95b24440 2516 register const bool do_utf8 = PL_reg_match_utf8;
4ad0818d 2517 const U32 uniflags = UTF8_ALLOW_DEFAULT;
95b24440 2518
3b0527fe
DM
2519 regexp *rex = reginfo->prog;
2520
5d9a96ca
DM
2521 regmatch_slab *orig_slab;
2522 regmatch_state *orig_state;
a3621e74 2523
5d9a96ca
DM
2524 /* the current state. This is a cached copy of PL_regmatch_state */
2525 register regmatch_state *st;
95b24440 2526
5d9a96ca
DM
2527 /* cache heavy used fields of st in registers */
2528 register regnode *scan;
2529 register regnode *next;
24d3c4a9
DM
2530 register I32 n = 0; /* general value; init to avoid compiler warning */
2531 register I32 ln = 0; /* len or last; init to avoid compiler warning */
5d9a96ca 2532 register char *locinput = PL_reginput;
5d9a96ca 2533 register I32 nextchr; /* is always set to UCHARAT(locinput) */
24d3c4a9 2534
b69b0499 2535 bool result = 0; /* return value of S_regmatch */
24d3c4a9 2536 int depth = 0; /* depth of backtrack stack */
6bda09f9 2537 int nochange_depth = 0; /* depth of RECURSE recursion with nochange*/
77cb431f
DM
2538 regmatch_state *yes_state = NULL; /* state to pop to on success of
2539 subpattern */
faec1544 2540 regmatch_state *cur_eval = NULL; /* most recent EVAL_AB state */
b8591aee 2541 struct regmatch_state *cur_curlyx = NULL; /* most recent curlyx */
40a82448 2542 U32 state_num;
10edeb5d 2543
24d3c4a9
DM
2544 /* these three flags are set by various ops to signal information to
2545 * the very next op. They have a useful lifetime of exactly one loop
2546 * iteration, and are not preserved or restored by state pushes/pops
2547 */
2548 bool sw = 0; /* the condition value in (?(cond)a|b) */
2549 bool minmod = 0; /* the next "{n,m}" is a "{n,m}?" */
2550 int logical = 0; /* the following EVAL is:
2551 0: (?{...})
2552 1: (?(?{...})X|Y)
2553 2: (??{...})
2554 or the following IFMATCH/UNLESSM is:
2555 false: plain (?=foo)
2556 true: used as a condition: (?(?=foo))
2557 */
2558
95b24440 2559#ifdef DEBUGGING
e68ec53f 2560 GET_RE_DEBUG_FLAGS_DECL;
d6a28714
JH
2561#endif
2562
5d9a96ca
DM
2563 /* on first ever call to regmatch, allocate first slab */
2564 if (!PL_regmatch_slab) {
2565 Newx(PL_regmatch_slab, 1, regmatch_slab);
2566 PL_regmatch_slab->prev = NULL;
2567 PL_regmatch_slab->next = NULL;
86545054 2568 PL_regmatch_state = SLAB_FIRST(PL_regmatch_slab);
5d9a96ca
DM
2569 }
2570
2571 /* remember current high-water mark for exit */
2572 /* XXX this should be done with SAVE* instead */
2573 orig_slab = PL_regmatch_slab;
2574 orig_state = PL_regmatch_state;
2575
2576 /* grab next free state slot */
2577 st = ++PL_regmatch_state;
86545054 2578 if (st > SLAB_LAST(PL_regmatch_slab))
5d9a96ca
DM
2579 st = PL_regmatch_state = S_push_slab(aTHX);
2580
d6a28714
JH
2581 /* Note that nextchr is a byte even in UTF */
2582 nextchr = UCHARAT(locinput);
2583 scan = prog;
2584 while (scan != NULL) {
8ba1375e 2585
a3621e74 2586 DEBUG_EXECUTE_r( {
6136c704 2587 SV * const prop = sv_newmortal();
1de06328 2588 regnode *rnext=regnext(scan);
786e8c11 2589 DUMP_EXEC_POS( locinput, scan, do_utf8 );
32fc9b6a 2590 regprop(rex, prop, scan);
07be1b83
YO
2591
2592 PerlIO_printf(Perl_debug_log,
2593 "%3"IVdf":%*s%s(%"IVdf")\n",
5bc10b2c 2594 (IV)(scan - rex->program), depth*2, "",
07be1b83 2595 SvPVX_const(prop),
1de06328
YO
2596 (PL_regkind[OP(scan)] == END || !rnext) ?
2597 0 : (IV)(rnext - rex->program));
2a782b5b 2598 });
d6a28714
JH
2599
2600 next = scan + NEXT_OFF(scan);
2601 if (next == scan)
2602 next = NULL;
40a82448 2603 state_num = OP(scan);
d6a28714 2604
40a82448
DM
2605 reenter_switch:
2606 switch (state_num) {
d6a28714 2607 case BOL:
7fba1cd6 2608 if (locinput == PL_bostr)
d6a28714 2609 {
3b0527fe 2610 /* reginfo->till = reginfo->bol; */
b8c5462f
JH
2611 break;
2612 }
d6a28714
JH
2613 sayNO;
2614 case MBOL:
12d33761
HS
2615 if (locinput == PL_bostr ||
2616 ((nextchr || locinput < PL_regeol) && locinput[-1] == '\n'))
d6a28714 2617 {
b8c5462f
JH
2618 break;
2619 }
d6a28714
JH
2620 sayNO;
2621 case SBOL:
c2a73568 2622 if (locinput == PL_bostr)
b8c5462f 2623 break;
d6a28714
JH
2624 sayNO;
2625 case GPOS:
3b0527fe 2626 if (locinput == reginfo->ganch)
d6a28714
JH
2627 break;
2628 sayNO;
2629 case EOL:
d6a28714
JH
2630 goto seol;
2631 case MEOL:
d6a28714 2632 if ((nextchr || locinput < PL_regeol) && nextchr != '\n')
b8c5462f 2633 sayNO;
b8c5462f 2634 break;
d6a28714
JH
2635 case SEOL:
2636 seol:
2637 if ((nextchr || locinput < PL_regeol) && nextchr != '\n')
b8c5462f 2638 sayNO;
d6a28714 2639 if (PL_regeol - locinput > 1)
b8c5462f 2640 sayNO;
b8c5462f 2641 break;
d6a28714
JH
2642 case EOS:
2643 if (PL_regeol != locinput)
b8c5462f 2644 sayNO;
d6a28714 2645 break;
ffc61ed2 2646 case SANY:
d6a28714 2647 if (!nextchr && locinput >= PL_regeol)
4633a7c4 2648 sayNO;
f33976b4
DB
2649 if (do_utf8) {
2650 locinput += PL_utf8skip[nextchr];
2651 if (locinput > PL_regeol)
2652 sayNO;
2653 nextchr = UCHARAT(locinput);
2654 }
2655 else
2656 nextchr = UCHARAT(++locinput);
2657 break;
2658 case CANY:
2659 if (!nextchr && locinput >= PL_regeol)
2660 sayNO;
b8c5462f 2661 nextchr = UCHARAT(++locinput);
a0d0e21e 2662 break;
ffc61ed2 2663 case REG_ANY:
1aa99e6b
IH
2664 if ((!nextchr && locinput >= PL_regeol) || nextchr == '\n')
2665 sayNO;
2666 if (do_utf8) {
b8c5462f 2667 locinput += PL_utf8skip[nextchr];
d6a28714
JH
2668 if (locinput > PL_regeol)
2669 sayNO;
a0ed51b3 2670 nextchr = UCHARAT(locinput);
a0ed51b3 2671 }
1aa99e6b
IH
2672 else
2673 nextchr = UCHARAT(++locinput);
a0ed51b3 2674 break;
166ba7cd
DM
2675
2676#undef ST
2677#define ST st->u.trie
786e8c11
YO
2678 case TRIEC:
2679 /* In this case the charclass data is available inline so
2680 we can fail fast without a lot of extra overhead.
2681 */
2682 if (scan->flags == EXACT || !do_utf8) {
2683 if(!ANYOF_BITMAP_TEST(scan, *locinput)) {
2684 DEBUG_EXECUTE_r(
2685 PerlIO_printf(Perl_debug_log,
2686 "%*s %sfailed to match trie start class...%s\n",
5bc10b2c 2687 REPORT_CODE_OFF+depth*2, "", PL_colors[4], PL_colors[5])
786e8c11
YO
2688 );
2689 sayNO_SILENT;
2690 /* NOTREACHED */
2691 }
2692 }
2693 /* FALL THROUGH */
5b47454d 2694 case TRIE:
3dab1dad 2695 {
07be1b83 2696 /* what type of TRIE am I? (utf8 makes this contextual) */
3dab1dad
YO
2697 const enum { trie_plain, trie_utf8, trie_utf8_fold }
2698 trie_type = do_utf8 ?
2699 (scan->flags == EXACT ? trie_utf8 : trie_utf8_fold)
2700 : trie_plain;
2701
2702 /* what trie are we using right now */
be8e71aa 2703 reg_trie_data * const trie
3dab1dad
YO
2704 = (reg_trie_data*)rex->data->data[ ARG( scan ) ];
2705 U32 state = trie->startstate;
166ba7cd 2706
3dab1dad
YO
2707 if (trie->bitmap && trie_type != trie_utf8_fold &&
2708 !TRIE_BITMAP_TEST(trie,*locinput)
2709 ) {
2710 if (trie->states[ state ].wordnum) {
2711 DEBUG_EXECUTE_r(
2712 PerlIO_printf(Perl_debug_log,
2713 "%*s %smatched empty string...%s\n",
5bc10b2c 2714 REPORT_CODE_OFF+depth*2, "", PL_colors[4], PL_colors[5])
3dab1dad
YO
2715 );
2716 break;
2717 } else {
2718 DEBUG_EXECUTE_r(
2719 PerlIO_printf(Perl_debug_log,
786e8c11 2720 "%*s %sfailed to match trie start class...%s\n",
5bc10b2c 2721 REPORT_CODE_OFF+depth*2, "", PL_colors[4], PL_colors[5])
3dab1dad
YO
2722 );
2723 sayNO_SILENT;
2724 }
2725 }
166ba7cd 2726
786e8c11
YO
2727 {
2728 U8 *uc = ( U8* )locinput;
2729
2730 STRLEN len = 0;
2731 STRLEN foldlen = 0;
2732 U8 *uscan = (U8*)NULL;
2733 STRLEN bufflen=0;
2734 SV *sv_accept_buff = NULL;
2735 U8 foldbuf[ UTF8_MAXBYTES_CASE + 1 ];
2736
2737 ST.accepted = 0; /* how many accepting states we have seen */
2738 ST.B = next;
2739 ST.jump = trie->jump;
2740
2741#ifdef DEBUGGING
2742 ST.me = scan;
2743#endif
2744
2745
2746
07be1b83
YO
2747 /*
2748 traverse the TRIE keeping track of all accepting states
2749 we transition through until we get to a failing node.
2750 */
2751
a3621e74 2752 while ( state && uc <= (U8*)PL_regeol ) {
786e8c11 2753 U32 base = trie->states[ state ].trans.base;
f9f4320a 2754 UV uvc = 0;
786e8c11
YO
2755 U16 charid;
2756 /* We use charid to hold the wordnum as we don't use it
2757 for charid until after we have done the wordnum logic.
2758 We define an alias just so that the wordnum logic reads
2759 more naturally. */
2760
2761#define got_wordnum charid
2762 got_wordnum = trie->states[ state ].wordnum;
2763
2764 if ( got_wordnum ) {
2765 if ( ! ST.accepted ) {
5b47454d
DM
2766 ENTER;
2767 SAVETMPS;
2768 bufflen = TRIE_INITAL_ACCEPT_BUFFLEN;
2769 sv_accept_buff=newSV(bufflen *
2770 sizeof(reg_trie_accepted) - 1);
786e8c11 2771 SvCUR_set(sv_accept_buff, 0);
5b47454d
DM
2772 SvPOK_on(sv_accept_buff);
2773 sv_2mortal(sv_accept_buff);
166ba7cd
DM
2774 SAVETMPS;
2775 ST.accept_buff =
5b47454d
DM
2776 (reg_trie_accepted*)SvPV_nolen(sv_accept_buff );
2777 }
786e8c11 2778 do {
166ba7cd 2779 if (ST.accepted >= bufflen) {
5b47454d 2780 bufflen *= 2;
166ba7cd 2781 ST.accept_buff =(reg_trie_accepted*)
5b47454d
DM
2782 SvGROW(sv_accept_buff,
2783 bufflen * sizeof(reg_trie_accepted));
2784 }
2785 SvCUR_set(sv_accept_buff,SvCUR(sv_accept_buff)
2786 + sizeof(reg_trie_accepted));
a3621e74 2787
786e8c11
YO
2788
2789 ST.accept_buff[ST.accepted].wordnum = got_wordnum;
2790 ST.accept_buff[ST.accepted].endpos = uc;
2791 ++ST.accepted;
2792 } while (trie->nextword && (got_wordnum= trie->nextword[got_wordnum]));
2793 }
2794#undef got_wordnum
a3621e74 2795
07be1b83 2796 DEBUG_TRIE_EXECUTE_r({
786e8c11 2797 DUMP_EXEC_POS( (char *)uc, scan, do_utf8 );
a3621e74 2798 PerlIO_printf( Perl_debug_log,
786e8c11 2799 "%*s %sState: %4"UVxf" Accepted: %4"UVxf" ",
5bc10b2c 2800 2+depth * 2, "", PL_colors[4],
786e8c11 2801 (UV)state, (UV)ST.accepted );
07be1b83 2802 });
a3621e74
YO
2803
2804 if ( base ) {
4cadc6a9
YO
2805 REXEC_TRIE_READ_CHAR(trie_type, trie, uc, uscan, len,
2806 uvc, charid, foldlen, foldbuf, uniflags);
a3621e74 2807
5b47454d
DM
2808 if (charid &&
2809 (base + charid > trie->uniquecharcount )
2810 && (base + charid - 1 - trie->uniquecharcount
2811 < trie->lasttrans)
2812 && trie->trans[base + charid - 1 -
2813 trie->uniquecharcount].check == state)
2814 {
2815 state = trie->trans[base + charid - 1 -
2816 trie->uniquecharcount ].next;
2817 }
2818 else {
2819 state = 0;
2820 }
2821 uc += len;
2822
2823 }
2824 else {
a3621e74
YO
2825 state = 0;
2826 }
2827 DEBUG_TRIE_EXECUTE_r(
e4584336 2828 PerlIO_printf( Perl_debug_log,
786e8c11 2829 "Charid:%3x CP:%4"UVxf" After State: %4"UVxf"%s\n",
e4584336 2830 charid, uvc, (UV)state, PL_colors[5] );
a3621e74
YO
2831 );
2832 }
166ba7cd 2833 if (!ST.accepted )
a3621e74 2834 sayNO;
a3621e74 2835
166ba7cd
DM
2836 DEBUG_EXECUTE_r(
2837 PerlIO_printf( Perl_debug_log,
2838 "%*s %sgot %"IVdf" possible matches%s\n",
5bc10b2c 2839 REPORT_CODE_OFF + depth * 2, "",
166ba7cd
DM
2840 PL_colors[4], (IV)ST.accepted, PL_colors[5] );
2841 );
786e8c11 2842 }}
166ba7cd
DM
2843
2844 /* FALL THROUGH */
2845
2846 case TRIE_next_fail: /* we failed - try next alterative */
2847
2848 if ( ST.accepted == 1 ) {
2849 /* only one choice left - just continue */
2850 DEBUG_EXECUTE_r({
2851 reg_trie_data * const trie
2852 = (reg_trie_data*)rex->data->data[ ARG(ST.me) ];
2853 SV ** const tmp = RX_DEBUG(reginfo->prog)
2854 ? av_fetch( trie->words, ST.accept_buff[ 0 ].wordnum-1, 0 )
2855 : NULL;
2856 PerlIO_printf( Perl_debug_log,
2857 "%*s %sonly one match left: #%d <%s>%s\n",
5bc10b2c 2858 REPORT_CODE_OFF+depth*2, "", PL_colors[4],
166ba7cd
DM
2859 ST.accept_buff[ 0 ].wordnum,
2860 tmp ? SvPV_nolen_const( *tmp ) : "not compiled under -Dr",
2861 PL_colors[5] );
2862 });
2863 PL_reginput = (char *)ST.accept_buff[ 0 ].endpos;
2864 /* in this case we free tmps/leave before we call regmatch
2865 as we wont be using accept_buff again. */
2866 FREETMPS;
2867 LEAVE;
2868 locinput = PL_reginput;
2869 nextchr = UCHARAT(locinput);
786e8c11
YO
2870
2871 if ( !ST.jump )
2872 scan = ST.B;
2873 else
2874 scan = ST.B - ST.jump[ST.accept_buff[0].wordnum];
2875
166ba7cd
DM
2876 continue; /* execute rest of RE */
2877 }
2878
2879 if (!ST.accepted-- ) {
2880 FREETMPS;
2881 LEAVE;
2882 sayNO;
2883 }
2884
a3621e74 2885 /*
166ba7cd
DM
2886 There are at least two accepting states left. Presumably
2887 the number of accepting states is going to be low,
2888 typically two. So we simply scan through to find the one
2889 with lowest wordnum. Once we find it, we swap the last
2890 state into its place and decrement the size. We then try to
2891 match the rest of the pattern at the point where the word
2892 ends. If we succeed, control just continues along the
2893 regex; if we fail we return here to try the next accepting
2894 state
2895 */
a3621e74 2896
166ba7cd
DM
2897 {
2898 U32 best = 0;
2899 U32 cur;
2900 for( cur = 1 ; cur <= ST.accepted ; cur++ ) {
2901 DEBUG_TRIE_EXECUTE_r(
f2278c82 2902 PerlIO_printf( Perl_debug_log,
166ba7cd 2903 "%*s %sgot %"IVdf" (%d) as best, looking at %"IVdf" (%d)%s\n",
5bc10b2c 2904 REPORT_CODE_OFF + depth * 2, "", PL_colors[4],
166ba7cd
DM
2905 (IV)best, ST.accept_buff[ best ].wordnum, (IV)cur,
2906 ST.accept_buff[ cur ].wordnum, PL_colors[5] );
2907 );
2908
2909 if (ST.accept_buff[cur].wordnum <
2910 ST.accept_buff[best].wordnum)
2911 best = cur;
a3621e74 2912 }
166ba7cd
DM
2913
2914 DEBUG_EXECUTE_r({
2915 reg_trie_data * const trie
2916 = (reg_trie_data*)rex->data->data[ ARG(ST.me) ];
2917 SV ** const tmp = RX_DEBUG(reginfo->prog)
2918 ? av_fetch( trie->words, ST.accept_buff[ best ].wordnum - 1, 0 )
2919 : NULL;
265c4333
YO
2920 regnode *nextop=!ST.jump ?
2921 ST.B :
2922 ST.B - ST.jump[ST.accept_buff[best].wordnum];
2923 PerlIO_printf( Perl_debug_log,
2924 "%*s %strying alternation #%d <%s> at node #%d %s\n",
5bc10b2c 2925 REPORT_CODE_OFF+depth*2, "", PL_colors[4],
166ba7cd 2926 ST.accept_buff[best].wordnum,
265c4333
YO
2927 tmp ? SvPV_nolen_const( *tmp ) : "not compiled under -Dr",
2928 REG_NODE_NUM(nextop),
166ba7cd
DM
2929 PL_colors[5] );
2930 });
2931
2932 if ( best<ST.accepted ) {
2933 reg_trie_accepted tmp = ST.accept_buff[ best ];
2934 ST.accept_buff[ best ] = ST.accept_buff[ ST.accepted ];
2935 ST.accept_buff[ ST.accepted ] = tmp;
2936 best = ST.accepted;
a3621e74 2937 }
166ba7cd 2938 PL_reginput = (char *)ST.accept_buff[ best ].endpos;
786e8c11
YO
2939 if ( !ST.jump ) {
2940 PUSH_STATE_GOTO(TRIE_next, ST.B);
2941 /* NOTREACHED */
2942 } else {
2943 PUSH_STATE_GOTO(TRIE_next, ST.B - ST.jump[ST.accept_buff[best].wordnum]);
2944 /* NOTREACHED */
2945 }
2946 /* NOTREACHED */
166ba7cd 2947 }
166ba7cd
DM
2948 /* NOTREACHED */
2949
2950#undef ST
2951
95b24440
DM
2952 case EXACT: {
2953 char *s = STRING(scan);
24d3c4a9 2954 ln = STR_LEN(scan);
eb160463 2955 if (do_utf8 != UTF) {
bc517b45 2956 /* The target and the pattern have differing utf8ness. */
1aa99e6b 2957 char *l = locinput;
24d3c4a9 2958 const char * const e = s + ln;
a72c7584 2959
5ff6fc6d
JH
2960 if (do_utf8) {
2961 /* The target is utf8, the pattern is not utf8. */
1aa99e6b 2962 while (s < e) {
a3b680e6 2963 STRLEN ulen;
1aa99e6b 2964 if (l >= PL_regeol)
5ff6fc6d
JH
2965 sayNO;
2966 if (NATIVE_TO_UNI(*(U8*)s) !=
89ebb4a3 2967 utf8n_to_uvuni((U8*)l, UTF8_MAXBYTES, &ulen,
041457d9 2968 uniflags))
5ff6fc6d 2969 sayNO;
bc517b45 2970 l += ulen;
5ff6fc6d 2971 s ++;
1aa99e6b 2972 }
5ff6fc6d
JH
2973 }
2974 else {
2975 /* The target is not utf8, the pattern is utf8. */
1aa99e6b 2976 while (s < e) {
a3b680e6 2977 STRLEN ulen;
1aa99e6b
IH
2978 if (l >= PL_regeol)
2979 sayNO;
5ff6fc6d 2980 if (NATIVE_TO_UNI(*((U8*)l)) !=
89ebb4a3 2981 utf8n_to_uvuni((U8*)s, UTF8_MAXBYTES, &ulen,
041457d9 2982 uniflags))
1aa99e6b 2983 sayNO;
bc517b45 2984 s += ulen;
a72c7584 2985 l ++;
1aa99e6b 2986 }
5ff6fc6d 2987 }
1aa99e6b
IH
2988 locinput = l;
2989 nextchr = UCHARAT(locinput);
2990 break;
2991 }
bc517b45 2992 /* The target and the pattern have the same utf8ness. */
d6a28714
JH
2993 /* Inline the first character, for speed. */
2994 if (UCHARAT(s) != nextchr)
2995 sayNO;
24d3c4a9 2996 if (PL_regeol - locinput < ln)
d6a28714 2997 sayNO;
24d3c4a9 2998 if (ln > 1 && memNE(s, locinput, ln))
d6a28714 2999 sayNO;
24d3c4a9 3000 locinput += ln;
d6a28714
JH
3001 nextchr = UCHARAT(locinput);
3002 break;
95b24440 3003 }
d6a28714 3004 case EXACTFL:
b8c5462f
JH
3005 PL_reg_flags |= RF_tainted;
3006 /* FALL THROUGH */
95b24440 3007 case EXACTF: {
be8e71aa 3008 char * const s = STRING(scan);
24d3c4a9 3009 ln = STR_LEN(scan);
d6a28714 3010
d07ddd77
JH
3011 if (do_utf8 || UTF) {
3012 /* Either target or the pattern are utf8. */
be8e71aa 3013 const char * const l = locinput;
d07ddd77 3014 char *e = PL_regeol;
bc517b45 3015
24d3c4a9 3016 if (ibcmp_utf8(s, 0, ln, (bool)UTF,
1feea2c7 3017 l, &e, 0, do_utf8)) {
5486206c
JH
3018 /* One more case for the sharp s:
3019 * pack("U0U*", 0xDF) =~ /ss/i,
3020 * the 0xC3 0x9F are the UTF-8
3021 * byte sequence for the U+00DF. */
3022 if (!(do_utf8 &&
3023 toLOWER(s[0]) == 's' &&
24d3c4a9 3024 ln >= 2 &&
5486206c
JH
3025 toLOWER(s[1]) == 's' &&
3026 (U8)l[0] == 0xC3 &&
3027 e - l >= 2 &&
3028 (U8)l[1] == 0x9F))
3029 sayNO;
3030 }
d07ddd77
JH
3031 locinput = e;
3032 nextchr = UCHARAT(locinput);
3033 break;
a0ed51b3 3034 }
d6a28714 3035
bc517b45
JH
3036 /* Neither the target and the pattern are utf8. */
3037
d6a28714
JH
3038 /* Inline the first character, for speed. */
3039 if (UCHARAT(s) != nextchr &&
3040 UCHARAT(s) != ((OP(scan) == EXACTF)
3041 ? PL_fold : PL_fold_locale)[nextchr])
a0ed51b3 3042 sayNO;
24d3c4a9 3043 if (PL_regeol - locinput < ln)
b8c5462f 3044 sayNO;
24d3c4a9
DM
3045 if (ln > 1 && (OP(scan) == EXACTF
3046 ? ibcmp(s, locinput, ln)
3047 : ibcmp_locale(s, locinput, ln)))
4633a7c4 3048 sayNO;
24d3c4a9 3049 locinput += ln;
d6a28714 3050 nextchr = UCHARAT(locinput);
a0d0e21e 3051 break;
95b24440 3052 }
d6a28714 3053 case ANYOF:
ffc61ed2 3054 if (do_utf8) {
9e55ce06
JH
3055 STRLEN inclasslen = PL_regeol - locinput;
3056
32fc9b6a 3057 if (!reginclass(rex, scan, (U8*)locinput, &inclasslen, do_utf8))
262b90c4 3058 goto anyof_fail;
ffc61ed2
JH
3059 if (locinput >= PL_regeol)
3060 sayNO;
0f0076b4 3061 locinput += inclasslen ? inclasslen : UTF8SKIP(locinput);
b8c5462f 3062 nextchr = UCHARAT(locinput);
e0f9d4a8 3063 break;
ffc61ed2
JH
3064 }
3065 else {
3066 if (nextchr < 0)
3067 nextchr = UCHARAT(locinput);
32fc9b6a 3068 if (!REGINCLASS(rex, scan, (U8*)locinput))
262b90c4 3069 goto anyof_fail;
ffc61ed2
JH
3070 if (!nextchr && locinput >= PL_regeol)
3071 sayNO;
3072 nextchr = UCHARAT(++locinput);
e0f9d4a8
JH
3073 break;
3074 }
262b90c4 3075 anyof_fail:
e0f9d4a8
JH
3076 /* If we might have the case of the German sharp s
3077 * in a casefolding Unicode character class. */
3078
ebc501f0
JH
3079 if (ANYOF_FOLD_SHARP_S(scan, locinput, PL_regeol)) {
3080 locinput += SHARP_S_SKIP;
e0f9d4a8 3081 nextchr = UCHARAT(locinput);
ffc61ed2 3082 }
e0f9d4a8
JH
3083 else
3084 sayNO;
b8c5462f 3085 break;
d6a28714 3086 case ALNUML:
b8c5462f
JH
3087 PL_reg_flags |= RF_tainted;
3088 /* FALL THROUGH */
d6a28714 3089 case ALNUM:
b8c5462f 3090 if (!nextchr)
4633a7c4 3091 sayNO;
ffc61ed2 3092 if (do_utf8) {
1a4fad37 3093 LOAD_UTF8_CHARCLASS_ALNUM();
ffc61ed2 3094 if (!(OP(scan) == ALNUM
bb7a0f54 3095 ? (bool)swash_fetch(PL_utf8_alnum, (U8*)locinput, do_utf8)
d6a28714 3096 : isALNUM_LC_utf8((U8*)locinput)))
b8c5462f
JH
3097 {
3098 sayNO;
a0ed51b3 3099 }
b8c5462f 3100 locinput += PL_utf8skip[nextchr];
a0ed51b3
LW
3101 nextchr = UCHARAT(locinput);
3102 break;
3103 }
ffc61ed2 3104 if (!(OP(scan) == ALNUM
d6a28714 3105 ? isALNUM(nextchr) : isALNUM_LC(nextchr)))
bbce6d69 3106 sayNO;
b8c5462f 3107 nextchr = UCHARAT(++locinput);
a0d0e21e 3108 break;
d6a28714 3109 case NALNUML:
b8c5462f
JH
3110 PL_reg_flags |= RF_tainted;
3111 /* FALL THROUGH */
d6a28714
JH
3112 case NALNUM:
3113 if (!nextchr && locinput >= PL_regeol)
a0ed51b3 3114 sayNO;
ffc61ed2 3115 if (do_utf8) {
1a4fad37 3116 LOAD_UTF8_CHARCLASS_ALNUM();
ffc61ed2 3117 if (OP(scan) == NALNUM
bb7a0f54 3118 ? (bool)swash_fetch(PL_utf8_alnum, (U8*)locinput, do_utf8)
d6a28714
JH
3119 : isALNUM_LC_utf8((U8*)locinput))
3120 {
b8c5462f 3121 sayNO;
d6a28714 3122 }
b8c5462f
JH
3123 locinput += PL_utf8skip[nextchr];
3124 nextchr = UCHARAT(locinput);
3125 break;
3126 }
ffc61ed2 3127 if (OP(scan) == NALNUM
d6a28714 3128 ? isALNUM(nextchr) : isALNUM_LC(nextchr))
b8c5462f 3129 sayNO;
76e3520e 3130 nextchr = UCHARAT(++locinput);
a0d0e21e 3131 break;
d6a28714
JH
3132 case BOUNDL:
3133 case NBOUNDL:
3280af22 3134 PL_reg_flags |= RF_tainted;
bbce6d69 3135 /* FALL THROUGH */
d6a28714
JH
3136 case BOUND:
3137 case NBOUND:
3138 /* was last char in word? */
ffc61ed2 3139 if (do_utf8) {
12d33761 3140 if (locinput == PL_bostr)
24d3c4a9 3141 ln = '\n';
ffc61ed2 3142 else {
a3b680e6 3143 const U8 * const r = reghop3((U8*)locinput, -1, (U8*)PL_bostr);
9041c2e3 3144
24d3c4a9 3145 ln = utf8n_to_uvchr(r, UTF8SKIP(r), 0, uniflags);
ffc61ed2
JH
3146 }
3147 if (OP(scan) == BOUND || OP(scan) == NBOUND) {
24d3c4a9 3148 ln = isALNUM_uni(ln);
1a4fad37 3149 LOAD_UTF8_CHARCLASS_ALNUM();
3568d838 3150 n = swash_fetch(PL_utf8_alnum, (U8*)locinput, do_utf8);
ffc61ed2
JH
3151 }
3152 else {
24d3c4a9 3153 ln = isALNUM_LC_uvchr(UNI_TO_NATIVE(ln));
ffc61ed2
JH
3154 n = isALNUM_LC_utf8((U8*)locinput);
3155 }
a0ed51b3 3156 }
d6a28714 3157 else {
24d3c4a9 3158 ln = (locinput != PL_bostr) ?
12d33761 3159 UCHARAT(locinput - 1) : '\n';
ffc61ed2 3160 if (OP(scan) == BOUND || OP(scan) == NBOUND) {
24d3c4a9 3161 ln = isALNUM(ln);
ffc61ed2
JH
3162 n = isALNUM(nextchr);
3163 }
3164 else {
24d3c4a9 3165 ln = isALNUM_LC(ln);
ffc61ed2
JH
3166 n = isALNUM_LC(nextchr);
3167 }
d6a28714 3168 }
24d3c4a9 3169 if (((!ln) == (!n)) == (OP(scan) == BOUND ||
ffc61ed2
JH
3170 OP(scan) == BOUNDL))
3171 sayNO;
a0ed51b3 3172 break;
d6a28714 3173 case SPACEL:
3280af22 3174 PL_reg_flags |= RF_tainted;
bbce6d69 3175 /* FALL THROUGH */
d6a28714 3176 case SPACE:
9442cb0e 3177 if (!nextchr)
4633a7c4 3178 sayNO;
1aa99e6b 3179 if (do_utf8) {
fd400ab9 3180 if (UTF8_IS_CONTINUED(nextchr)) {
1a4fad37 3181 LOAD_UTF8_CHARCLASS_SPACE();
ffc61ed2 3182 if (!(OP(scan) == SPACE
bb7a0f54 3183 ? (bool)swash_fetch(PL_utf8_space, (U8*)locinput, do_utf8)
ffc61ed2
JH
3184 : isSPACE_LC_utf8((U8*)locinput)))
3185 {
3186 sayNO;
3187 }
3188 locinput += PL_utf8skip[nextchr];
3189 nextchr = UCHARAT(locinput);
3190 break;
d6a28714 3191 }
ffc61ed2
JH
3192 if (!(OP(scan) == SPACE
3193 ? isSPACE(nextchr) : isSPACE_LC(nextchr)))
3194 sayNO;
3195 nextchr = UCHARAT(++locinput);
3196 }
3197 else {
3198 if (!(OP(scan) == SPACE
3199 ? isSPACE(nextchr) : isSPACE_LC(nextchr)))
3200 sayNO;
3201 nextchr = UCHARAT(++locinput);
a0ed51b3 3202 }
a0ed51b3 3203 break;
d6a28714 3204 case NSPACEL:
3280af22 3205 PL_reg_flags |= RF_tainted;
bbce6d69 3206 /* FALL THROUGH */
d6a28714 3207 case NSPACE:
9442cb0e 3208 if (!nextchr && locinput >= PL_regeol)
b8c5462f 3209 sayNO;
1aa99e6b 3210 if (do_utf8) {
1a4fad37 3211 LOAD_UTF8_CHARCLASS_SPACE();
ffc61ed2 3212 if (OP(scan) == NSPACE
bb7a0f54 3213 ? (bool)swash_fetch(PL_utf8_space, (U8*)locinput, do_utf8)
d6a28714 3214 : isSPACE_LC_utf8((U8*)locinput))
b8c5462f
JH
3215 {
3216 sayNO;
3217 }
3218 locinput += PL_utf8skip[nextchr];
3219 nextchr = UCHARAT(locinput);
3220 break;
a0ed51b3 3221 }
ffc61ed2 3222 if (OP(scan) == NSPACE
d6a28714 3223 ? isSPACE(nextchr) : isSPACE_LC(nextchr))
4633a7c4 3224 sayNO;
76e3520e 3225 nextchr = UCHARAT(++locinput);
a0d0e21e 3226 break;
d6a28714 3227 case DIGITL:
a0ed51b3
LW
3228 PL_reg_flags |= RF_tainted;
3229 /* FALL THROUGH */
d6a28714 3230 case DIGIT:
9442cb0e 3231 if (!nextchr)
a0ed51b3 3232 sayNO;
1aa99e6b 3233 if (do_utf8) {
1a4fad37 3234 LOAD_UTF8_CHARCLASS_DIGIT();
ffc61ed2 3235 if (!(OP(scan) == DIGIT
bb7a0f54 3236 ? (bool)swash_fetch(PL_utf8_digit, (U8*)locinput, do_utf8)
9442cb0e 3237 : isDIGIT_LC_utf8((U8*)locinput)))
dfe13c55 3238 {
a0ed51b3 3239 sayNO;
dfe13c55 3240 }
6f06b55f 3241 locinput += PL_utf8skip[nextchr];
a0ed51b3
LW
3242 nextchr = UCHARAT(locinput);
3243 break;
3244 }
ffc61ed2 3245 if (!(OP(scan) == DIGIT
9442cb0e 3246 ? isDIGIT(nextchr) : isDIGIT_LC(nextchr)))
a0ed51b3
LW
3247 sayNO;
3248 nextchr = UCHARAT(++locinput);
3249 break;
d6a28714 3250 case NDIGITL:
b8c5462f
JH
3251 PL_reg_flags |= RF_tainted;
3252 /* FALL THROUGH */
d6a28714 3253 case NDIGIT:
9442cb0e 3254 if (!nextchr && locinput >= PL_regeol)
b8c5462f 3255 sayNO;
1aa99e6b 3256 if (do_utf8) {
1a4fad37 3257 LOAD_UTF8_CHARCLASS_DIGIT();
ffc61ed2 3258 if (OP(scan) == NDIGIT
bb7a0f54 3259 ? (bool)swash_fetch(PL_utf8_digit, (U8*)locinput, do_utf8)
9442cb0e
GS
3260 : isDIGIT_LC_utf8((U8*)locinput))
3261 {
a0ed51b3 3262 sayNO;
9442cb0e 3263 }
6f06b55f 3264 locinput += PL_utf8skip[nextchr];
a0ed51b3
LW
3265 nextchr = UCHARAT(locinput);
3266 break;
3267 }
ffc61ed2 3268 if (OP(scan) == NDIGIT
9442cb0e 3269 ? isDIGIT(nextchr) : isDIGIT_LC(nextchr))
a0ed51b3
LW
3270 sayNO;
3271 nextchr = UCHARAT(++locinput);
3272 break;
3273 case CLUMP:
b7c83a7e 3274 if (locinput >= PL_regeol)
a0ed51b3 3275 sayNO;
b7c83a7e 3276 if (do_utf8) {
1a4fad37 3277 LOAD_UTF8_CHARCLASS_MARK();
b7c83a7e
JH
3278 if (swash_fetch(PL_utf8_mark,(U8*)locinput, do_utf8))
3279 sayNO;
3280 locinput += PL_utf8skip[nextchr];
3281 while (locinput < PL_regeol &&
3282 swash_fetch(PL_utf8_mark,(U8*)locinput, do_utf8))
3283 locinput += UTF8SKIP(locinput);
3284 if (locinput > PL_regeol)
3285 sayNO;
eb08e2da
JH
3286 }
3287 else
3288 locinput++;
a0ed51b3
LW
3289 nextchr = UCHARAT(locinput);
3290 break;
c8756f30 3291 case REFFL:
3280af22 3292 PL_reg_flags |= RF_tainted;
c8756f30 3293 /* FALL THROUGH */
c277df42 3294 case REF:
95b24440
DM
3295 case REFF: {
3296 char *s;
c277df42 3297 n = ARG(scan); /* which paren pair */
24d3c4a9 3298 ln = PL_regstartp[n];
2c2d71f5 3299 PL_reg_leftiter = PL_reg_maxiter; /* Void cache */
24d3c4a9 3300 if ((I32)*PL_reglastparen < n || ln == -1)
af3f8c16 3301 sayNO; /* Do not match unless seen CLOSEn. */
24d3c4a9 3302 if (ln == PL_regendp[n])
a0d0e21e 3303 break;
a0ed51b3 3304
24d3c4a9 3305 s = PL_bostr + ln;
1aa99e6b 3306 if (do_utf8 && OP(scan) != REF) { /* REF can do byte comparison */
a0ed51b3 3307 char *l = locinput;
a3b680e6 3308 const char *e = PL_bostr + PL_regendp[n];
a0ed51b3
LW
3309 /*
3310 * Note that we can't do the "other character" lookup trick as
3311 * in the 8-bit case (no pun intended) because in Unicode we
3312 * have to map both upper and title case to lower case.
3313 */
3314 if (OP(scan) == REFF) {
3315 while (s < e) {
a3b680e6
AL
3316 STRLEN ulen1, ulen2;
3317 U8 tmpbuf1[UTF8_MAXBYTES_CASE+1];
3318 U8 tmpbuf2[UTF8_MAXBYTES_CASE+1];
3319
a0ed51b3
LW
3320 if (l >= PL_regeol)
3321 sayNO;
a2a2844f
JH
3322 toLOWER_utf8((U8*)s, tmpbuf1, &ulen1);
3323 toLOWER_utf8((U8*)l, tmpbuf2, &ulen2);
7114a2d2 3324 if (ulen1 != ulen2 || memNE((char *)tmpbuf1, (char *)tmpbuf2, ulen1))
a0ed51b3 3325 sayNO;
a2a2844f
JH
3326 s += ulen1;
3327 l += ulen2;
a0ed51b3
LW
3328 }
3329 }
3330 locinput = l;
3331 nextchr = UCHARAT(locinput);
3332 break;
3333 }
3334
a0d0e21e 3335 /* Inline the first character, for speed. */
76e3520e 3336 if (UCHARAT(s) != nextchr &&
c8756f30
AK
3337 (OP(scan) == REF ||
3338 (UCHARAT(s) != ((OP(scan) == REFF
22c35a8c 3339 ? PL_fold : PL_fold_locale)[nextchr]))))
4633a7c4 3340 sayNO;
24d3c4a9
DM
3341 ln = PL_regendp[n] - ln;
3342 if (locinput + ln > PL_regeol)
4633a7c4 3343 sayNO;
24d3c4a9
DM
3344 if (ln > 1 && (OP(scan) == REF
3345 ? memNE(s, locinput, ln)
c8756f30 3346 : (OP(scan) == REFF
24d3c4a9
DM
3347 ? ibcmp(s, locinput, ln)
3348 : ibcmp_locale(s, locinput, ln))))
4633a7c4 3349 sayNO;
24d3c4a9 3350 locinput += ln;
76e3520e 3351 nextchr = UCHARAT(locinput);
a0d0e21e 3352 break;
95b24440 3353 }
a0d0e21e
LW
3354
3355 case NOTHING:
c277df42 3356 case TAIL:
a0d0e21e
LW
3357 break;
3358 case BACK:
3359 break;
40a82448
DM
3360
3361#undef ST
3362#define ST st->u.eval
c277df42 3363 {
c277df42 3364 SV *ret;
6bda09f9
YO
3365 regexp *re;
3366 regnode *startpoint;
3367
3368 case SRECURSE:
3369 case RECURSE: /* /(...(?1))/ */
3370 if (cur_eval && cur_eval->locinput==locinput) {
3371 if (cur_eval->u.eval.close_paren == ARG(scan))
3372 Perl_croak(aTHX_ "Infinite recursion in RECURSE in regexp");
3373 if ( ++nochange_depth > MAX_RECURSE_EVAL_NOCHANGE_DEPTH )
3374 Perl_croak(aTHX_ "RECURSE without pos change exceeded limit in regexp");
3375 } else {
3376 nochange_depth = 0;
3377 }
3378 re = rex;
3379 (void)ReREFCNT_inc(rex);
3380 if (OP(scan)==RECURSE) {
3381 startpoint = scan + ARG2L(scan);
3382 ST.close_paren = ARG(scan);
3383 } else {
3384 startpoint = re->program+1;
3385 ST.close_paren = 0;
3386 }
3387 goto eval_recurse_doit;
3388 /* NOTREACHED */
3389 case EVAL: /* /(?{A})B/ /(??{A})B/ and /(?(?{A})X|Y)B/ */
3390 if (cur_eval && cur_eval->locinput==locinput) {
3391 if ( ++nochange_depth > MAX_RECURSE_EVAL_NOCHANGE_DEPTH )
3392 Perl_croak(aTHX_ "EVAL without pos change exceeded limit in regexp");
3393 } else {
3394 nochange_depth = 0;
3395 }
8e5e9ebe 3396 {
4aabdb9b
DM
3397 /* execute the code in the {...} */
3398 dSP;
6136c704 3399 SV ** const before = SP;
4aabdb9b
DM
3400 OP_4tree * const oop = PL_op;
3401 COP * const ocurcop = PL_curcop;
3402 PAD *old_comppad;
4aabdb9b
DM
3403
3404 n = ARG(scan);
32fc9b6a 3405 PL_op = (OP_4tree*)rex->data->data[n];
4aabdb9b 3406 DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log, " re_eval 0x%"UVxf"\n", PTR2UV(PL_op)) );
32fc9b6a 3407 PAD_SAVE_LOCAL(old_comppad, (PAD*)rex->data->data[n + 2]);
4aabdb9b
DM
3408 PL_regendp[0] = PL_reg_magic->mg_len = locinput - PL_bostr;
3409
8e5e9ebe
RGS
3410 CALLRUNOPS(aTHX); /* Scalar context. */
3411 SPAGAIN;
3412 if (SP == before)
075aa684 3413 ret = &PL_sv_undef; /* protect against empty (?{}) blocks. */
8e5e9ebe
RGS
3414 else {
3415 ret = POPs;
3416 PUTBACK;
3417 }
4aabdb9b
DM
3418
3419 PL_op = oop;
3420 PAD_RESTORE_LOCAL(old_comppad);
3421 PL_curcop = ocurcop;
24d3c4a9 3422 if (!logical) {
4aabdb9b
DM
3423 /* /(?{...})/ */
3424 sv_setsv(save_scalar(PL_replgv), ret);
4aabdb9b
DM
3425 break;
3426 }
8e5e9ebe 3427 }
24d3c4a9
DM
3428 if (logical == 2) { /* Postponed subexpression: /(??{...})/ */
3429 logical = 0;
4aabdb9b 3430 {
4f639d21
DM
3431 /* extract RE object from returned value; compiling if
3432 * necessary */
3433
6136c704 3434 MAGIC *mg = NULL;
be8e71aa 3435 const SV *sv;