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