This is a live mirror of the Perl 5 development currently hosted at https://github.com/perl/perl5
In struct regexp replace the two arrays of I32s accessed via startp
[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;
3dab1dad 1693 SV* const oreplsv = GvSV(PL_replgv);
f9f4320a 1694 const bool do_utf8 = (bool)DO_UTF8(sv);
2757e526 1695 I32 multiline;
f8fc2ecf 1696 RXi_GET_DECL(prog,progi);
3b0527fe 1697 regmatch_info reginfo; /* create some info to pass to regtry etc */
fae667d5 1698 bool swap_on_fail = 0;
a3621e74
YO
1699
1700 GET_RE_DEBUG_FLAGS_DECL;
1701
9d4ba2ae 1702 PERL_UNUSED_ARG(data);
6eb5f6b9
JH
1703
1704 /* Be paranoid... */
1705 if (prog == NULL || startpos == NULL) {
1706 Perl_croak(aTHX_ "NULL regexp parameter");
1707 return 0;
1708 }
1709
bbe252da 1710 multiline = prog->extflags & RXf_PMf_MULTILINE;
3b0527fe 1711 reginfo.prog = prog;
2757e526 1712
bac06658 1713 RX_MATCH_UTF8_set(prog, do_utf8);
1de06328
YO
1714 DEBUG_EXECUTE_r(
1715 debug_start_match(prog, do_utf8, startpos, strend,
1716 "Matching");
1717 );
bac06658 1718
6eb5f6b9 1719 minlen = prog->minlen;
1de06328
YO
1720
1721 if (strend - startpos < (minlen+(prog->check_offset_min<0?prog->check_offset_min:0))) {
a3621e74 1722 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
a72c7584
JH
1723 "String too short [regexec_flags]...\n"));
1724 goto phooey;
1aa99e6b 1725 }
6eb5f6b9 1726
1de06328 1727
6eb5f6b9 1728 /* Check validity of program. */
f8fc2ecf 1729 if (UCHARAT(progi->program) != REG_MAGIC) {
6eb5f6b9
JH
1730 Perl_croak(aTHX_ "corrupted regexp program");
1731 }
1732
1733 PL_reg_flags = 0;
1734 PL_reg_eval_set = 0;
1735 PL_reg_maxiter = 0;
1736
bbe252da 1737 if (prog->extflags & RXf_UTF8)
6eb5f6b9
JH
1738 PL_reg_flags |= RF_utf8;
1739
1740 /* Mark beginning of line for ^ and lookbehind. */
3b0527fe 1741 reginfo.bol = startpos; /* XXX not used ??? */
6eb5f6b9 1742 PL_bostr = strbeg;
3b0527fe 1743 reginfo.sv = sv;
6eb5f6b9
JH
1744
1745 /* Mark end of line for $ (and such) */
1746 PL_regeol = strend;
1747
1748 /* see how far we have to get to not match where we matched before */
3b0527fe 1749 reginfo.till = startpos+minend;
6eb5f6b9 1750
6eb5f6b9
JH
1751 /* If there is a "must appear" string, look for it. */
1752 s = startpos;
1753
bbe252da 1754 if (prog->extflags & RXf_GPOS_SEEN) { /* Need to set reginfo->ganch */
6eb5f6b9
JH
1755 MAGIC *mg;
1756
1757 if (flags & REXEC_IGNOREPOS) /* Means: check only at start */
58e23c8d 1758 reginfo.ganch = startpos + prog->gofs;
6eb5f6b9
JH
1759 else if (sv && SvTYPE(sv) >= SVt_PVMG
1760 && SvMAGIC(sv)
14befaf4
DM
1761 && (mg = mg_find(sv, PERL_MAGIC_regex_global))
1762 && mg->mg_len >= 0) {
3b0527fe 1763 reginfo.ganch = strbeg + mg->mg_len; /* Defined pos() */
bbe252da 1764 if (prog->extflags & RXf_ANCH_GPOS) {
3b0527fe 1765 if (s > reginfo.ganch)
6eb5f6b9 1766 goto phooey;
58e23c8d 1767 s = reginfo.ganch - prog->gofs;
6eb5f6b9
JH
1768 }
1769 }
58e23c8d 1770 else if (data) {
70685ca0 1771 reginfo.ganch = strbeg + PTR2UV(data);
58e23c8d 1772 } else /* pos() not defined */
3b0527fe 1773 reginfo.ganch = strbeg;
6eb5f6b9 1774 }
c74340f9 1775 if (PL_curpm && (PM_GETRE(PL_curpm) == prog)) {
fae667d5
YO
1776 swap_on_fail = 1;
1777 swap_match_buff(prog); /* do we need a save destructor here for
1778 eval dies? */
c74340f9 1779 }
a0714e2c 1780 if (!(flags & REXEC_CHECKED) && (prog->check_substr != NULL || prog->check_utf8 != NULL)) {
6eb5f6b9
JH
1781 re_scream_pos_data d;
1782
1783 d.scream_olds = &scream_olds;
1784 d.scream_pos = &scream_pos;
1785 s = re_intuit_start(prog, sv, s, strend, flags, &d);
3fa9c3d7 1786 if (!s) {
a3621e74 1787 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "Not present...\n"));
6eb5f6b9 1788 goto phooey; /* not present */
3fa9c3d7 1789 }
6eb5f6b9
JH
1790 }
1791
1de06328 1792
6eb5f6b9
JH
1793
1794 /* Simplest case: anchored match need be tried only once. */
1795 /* [unless only anchor is BOL and multiline is set] */
bbe252da 1796 if (prog->extflags & (RXf_ANCH & ~RXf_ANCH_GPOS)) {
24b23f37 1797 if (s == startpos && regtry(&reginfo, &startpos))
6eb5f6b9 1798 goto got_it;
bbe252da
YO
1799 else if (multiline || (prog->intflags & PREGf_IMPLICIT)
1800 || (prog->extflags & RXf_ANCH_MBOL)) /* XXXX SBOL? */
6eb5f6b9
JH
1801 {
1802 char *end;
1803
1804 if (minlen)
1805 dontbother = minlen - 1;
1aa99e6b 1806 end = HOP3c(strend, -dontbother, strbeg) - 1;
6eb5f6b9 1807 /* for multiline we only have to try after newlines */
33b8afdf 1808 if (prog->check_substr || prog->check_utf8) {
6eb5f6b9
JH
1809 if (s == startpos)
1810 goto after_try;
1811 while (1) {
24b23f37 1812 if (regtry(&reginfo, &s))
6eb5f6b9
JH
1813 goto got_it;
1814 after_try:
1815 if (s >= end)
1816 goto phooey;
bbe252da 1817 if (prog->extflags & RXf_USE_INTUIT) {
6eb5f6b9
JH
1818 s = re_intuit_start(prog, sv, s + 1, strend, flags, NULL);
1819 if (!s)
1820 goto phooey;
1821 }
1822 else
1823 s++;
1824 }
1825 } else {
1826 if (s > startpos)
1827 s--;
1828 while (s < end) {
1829 if (*s++ == '\n') { /* don't need PL_utf8skip here */
24b23f37 1830 if (regtry(&reginfo, &s))
6eb5f6b9
JH
1831 goto got_it;
1832 }
1833 }
1834 }
1835 }
1836 goto phooey;
bbe252da 1837 } else if (RXf_GPOS_CHECK == (prog->extflags & RXf_GPOS_CHECK))
f9f4320a
YO
1838 {
1839 /* the warning about reginfo.ganch being used without intialization
bbe252da 1840 is bogus -- we set it above, when prog->extflags & RXf_GPOS_SEEN
f9f4320a 1841 and we only enter this block when the same bit is set. */
58e23c8d
YO
1842 char *tmp_s = reginfo.ganch - prog->gofs;
1843 if (regtry(&reginfo, &tmp_s))
6eb5f6b9
JH
1844 goto got_it;
1845 goto phooey;
1846 }
1847
1848 /* Messy cases: unanchored match. */
bbe252da 1849 if ((prog->anchored_substr || prog->anchored_utf8) && prog->intflags & PREGf_SKIP) {
6eb5f6b9
JH
1850 /* we have /x+whatever/ */
1851 /* it must be a one character string (XXXX Except UTF?) */
33b8afdf 1852 char ch;
bf93d4cc
GS
1853#ifdef DEBUGGING
1854 int did_match = 0;
1855#endif
33b8afdf
JH
1856 if (!(do_utf8 ? prog->anchored_utf8 : prog->anchored_substr))
1857 do_utf8 ? to_utf8_substr(prog) : to_byte_substr(prog);
3f7c398e 1858 ch = SvPVX_const(do_utf8 ? prog->anchored_utf8 : prog->anchored_substr)[0];
bf93d4cc 1859
1aa99e6b 1860 if (do_utf8) {
4cadc6a9 1861 REXEC_FBC_SCAN(
6eb5f6b9 1862 if (*s == ch) {
a3621e74 1863 DEBUG_EXECUTE_r( did_match = 1 );
24b23f37 1864 if (regtry(&reginfo, &s)) goto got_it;
6eb5f6b9
JH
1865 s += UTF8SKIP(s);
1866 while (s < strend && *s == ch)
1867 s += UTF8SKIP(s);
1868 }
4cadc6a9 1869 );
6eb5f6b9
JH
1870 }
1871 else {
4cadc6a9 1872 REXEC_FBC_SCAN(
6eb5f6b9 1873 if (*s == ch) {
a3621e74 1874 DEBUG_EXECUTE_r( did_match = 1 );
24b23f37 1875 if (regtry(&reginfo, &s)) goto got_it;
6eb5f6b9
JH
1876 s++;
1877 while (s < strend && *s == ch)
1878 s++;
1879 }
4cadc6a9 1880 );
6eb5f6b9 1881 }
a3621e74 1882 DEBUG_EXECUTE_r(if (!did_match)
bf93d4cc 1883 PerlIO_printf(Perl_debug_log,
b7953727
JH
1884 "Did not find anchored character...\n")
1885 );
6eb5f6b9 1886 }
a0714e2c
SS
1887 else if (prog->anchored_substr != NULL
1888 || prog->anchored_utf8 != NULL
1889 || ((prog->float_substr != NULL || prog->float_utf8 != NULL)
33b8afdf
JH
1890 && prog->float_max_offset < strend - s)) {
1891 SV *must;
1892 I32 back_max;
1893 I32 back_min;
1894 char *last;
6eb5f6b9 1895 char *last1; /* Last position checked before */
bf93d4cc
GS
1896#ifdef DEBUGGING
1897 int did_match = 0;
1898#endif
33b8afdf
JH
1899 if (prog->anchored_substr || prog->anchored_utf8) {
1900 if (!(do_utf8 ? prog->anchored_utf8 : prog->anchored_substr))
1901 do_utf8 ? to_utf8_substr(prog) : to_byte_substr(prog);
1902 must = do_utf8 ? prog->anchored_utf8 : prog->anchored_substr;
1903 back_max = back_min = prog->anchored_offset;
1904 } else {
1905 if (!(do_utf8 ? prog->float_utf8 : prog->float_substr))
1906 do_utf8 ? to_utf8_substr(prog) : to_byte_substr(prog);
1907 must = do_utf8 ? prog->float_utf8 : prog->float_substr;
1908 back_max = prog->float_max_offset;
1909 back_min = prog->float_min_offset;
1910 }
1de06328
YO
1911
1912
33b8afdf
JH
1913 if (must == &PL_sv_undef)
1914 /* could not downgrade utf8 check substring, so must fail */
1915 goto phooey;
1916
1de06328
YO
1917 if (back_min<0) {
1918 last = strend;
1919 } else {
1920 last = HOP3c(strend, /* Cannot start after this */
1921 -(I32)(CHR_SVLEN(must)
1922 - (SvTAIL(must) != 0) + back_min), strbeg);
1923 }
6eb5f6b9
JH
1924 if (s > PL_bostr)
1925 last1 = HOPc(s, -1);
1926 else
1927 last1 = s - 1; /* bogus */
1928
a0288114 1929 /* XXXX check_substr already used to find "s", can optimize if
6eb5f6b9
JH
1930 check_substr==must. */
1931 scream_pos = -1;
1932 dontbother = end_shift;
1933 strend = HOPc(strend, -dontbother);
1934 while ( (s <= last) &&
9041c2e3 1935 ((flags & REXEC_SCREAM)
1de06328 1936 ? (s = screaminstr(sv, must, HOP3c(s, back_min, (back_min<0 ? strbeg : strend)) - strbeg,
6eb5f6b9 1937 end_shift, &scream_pos, 0))
1de06328 1938 : (s = fbm_instr((unsigned char*)HOP3(s, back_min, (back_min<0 ? strbeg : strend)),
9041c2e3 1939 (unsigned char*)strend, must,
7fba1cd6 1940 multiline ? FBMrf_MULTILINE : 0))) ) {
4addbd3b
HS
1941 /* we may be pointing at the wrong string */
1942 if ((flags & REXEC_SCREAM) && RX_MATCH_COPIED(prog))
3f7c398e 1943 s = strbeg + (s - SvPVX_const(sv));
a3621e74 1944 DEBUG_EXECUTE_r( did_match = 1 );
6eb5f6b9
JH
1945 if (HOPc(s, -back_max) > last1) {
1946 last1 = HOPc(s, -back_min);
1947 s = HOPc(s, -back_max);
1948 }
1949 else {
52657f30 1950 char * const t = (last1 >= PL_bostr) ? HOPc(last1, 1) : last1 + 1;
6eb5f6b9
JH
1951
1952 last1 = HOPc(s, -back_min);
52657f30 1953 s = t;
6eb5f6b9 1954 }
1aa99e6b 1955 if (do_utf8) {
6eb5f6b9 1956 while (s <= last1) {
24b23f37 1957 if (regtry(&reginfo, &s))
6eb5f6b9
JH
1958 goto got_it;
1959 s += UTF8SKIP(s);
1960 }
1961 }
1962 else {
1963 while (s <= last1) {
24b23f37 1964 if (regtry(&reginfo, &s))
6eb5f6b9
JH
1965 goto got_it;
1966 s++;
1967 }
1968 }
1969 }
ab3bbdeb
YO
1970 DEBUG_EXECUTE_r(if (!did_match) {
1971 RE_PV_QUOTED_DECL(quoted, do_utf8, PERL_DEBUG_PAD_ZERO(0),
1972 SvPVX_const(must), RE_SV_DUMPLEN(must), 30);
1973 PerlIO_printf(Perl_debug_log, "Did not find %s substr %s%s...\n",
33b8afdf 1974 ((must == prog->anchored_substr || must == prog->anchored_utf8)
bf93d4cc 1975 ? "anchored" : "floating"),
ab3bbdeb
YO
1976 quoted, RE_SV_TAIL(must));
1977 });
6eb5f6b9
JH
1978 goto phooey;
1979 }
f8fc2ecf 1980 else if ( (c = progi->regstclass) ) {
f14c76ed 1981 if (minlen) {
f8fc2ecf 1982 const OPCODE op = OP(progi->regstclass);
66e933ab 1983 /* don't bother with what can't match */
786e8c11 1984 if (PL_regkind[op] != EXACT && op != CANY && PL_regkind[op] != TRIE)
f14c76ed
RGS
1985 strend = HOPc(strend, -(minlen - 1));
1986 }
a3621e74 1987 DEBUG_EXECUTE_r({
be8e71aa 1988 SV * const prop = sv_newmortal();
32fc9b6a 1989 regprop(prog, prop, c);
0df25f3d 1990 {
02daf0ab 1991 RE_PV_QUOTED_DECL(quoted,do_utf8,PERL_DEBUG_PAD_ZERO(1),
ab3bbdeb 1992 s,strend-s,60);
0df25f3d 1993 PerlIO_printf(Perl_debug_log,
ab3bbdeb 1994 "Matching stclass %.*s against %s (%d chars)\n",
e4f74956 1995 (int)SvCUR(prop), SvPVX_const(prop),
ab3bbdeb 1996 quoted, (int)(strend - s));
0df25f3d 1997 }
ffc61ed2 1998 });
3b0527fe 1999 if (find_byclass(prog, c, s, strend, &reginfo))
6eb5f6b9 2000 goto got_it;
07be1b83 2001 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "Contradicts stclass... [regexec_flags]\n"));
d6a28714
JH
2002 }
2003 else {
2004 dontbother = 0;
a0714e2c 2005 if (prog->float_substr != NULL || prog->float_utf8 != NULL) {
33b8afdf 2006 /* Trim the end. */
d6a28714 2007 char *last;
33b8afdf
JH
2008 SV* float_real;
2009
2010 if (!(do_utf8 ? prog->float_utf8 : prog->float_substr))
2011 do_utf8 ? to_utf8_substr(prog) : to_byte_substr(prog);
2012 float_real = do_utf8 ? prog->float_utf8 : prog->float_substr;
d6a28714
JH
2013
2014 if (flags & REXEC_SCREAM) {
33b8afdf 2015 last = screaminstr(sv, float_real, s - strbeg,
d6a28714
JH
2016 end_shift, &scream_pos, 1); /* last one */
2017 if (!last)
ffc61ed2 2018 last = scream_olds; /* Only one occurrence. */
4addbd3b
HS
2019 /* we may be pointing at the wrong string */
2020 else if (RX_MATCH_COPIED(prog))
3f7c398e 2021 s = strbeg + (s - SvPVX_const(sv));
b8c5462f 2022 }
d6a28714
JH
2023 else {
2024 STRLEN len;
cfd0369c 2025 const char * const little = SvPV_const(float_real, len);
d6a28714 2026
33b8afdf 2027 if (SvTAIL(float_real)) {
d6a28714
JH
2028 if (memEQ(strend - len + 1, little, len - 1))
2029 last = strend - len + 1;
7fba1cd6 2030 else if (!multiline)
9041c2e3 2031 last = memEQ(strend - len, little, len)
bd61b366 2032 ? strend - len : NULL;
b8c5462f 2033 else
d6a28714
JH
2034 goto find_last;
2035 } else {
2036 find_last:
9041c2e3 2037 if (len)
d6a28714 2038 last = rninstr(s, strend, little, little + len);
b8c5462f 2039 else
a0288114 2040 last = strend; /* matching "$" */
b8c5462f 2041 }
b8c5462f 2042 }
bf93d4cc 2043 if (last == NULL) {
6bda09f9
YO
2044 DEBUG_EXECUTE_r(
2045 PerlIO_printf(Perl_debug_log,
2046 "%sCan't trim the tail, match fails (should not happen)%s\n",
2047 PL_colors[4], PL_colors[5]));
bf93d4cc
GS
2048 goto phooey; /* Should not happen! */
2049 }
d6a28714
JH
2050 dontbother = strend - last + prog->float_min_offset;
2051 }
2052 if (minlen && (dontbother < minlen))
2053 dontbother = minlen - 1;
2054 strend -= dontbother; /* this one's always in bytes! */
2055 /* We don't know much -- general case. */
1aa99e6b 2056 if (do_utf8) {
d6a28714 2057 for (;;) {
24b23f37 2058 if (regtry(&reginfo, &s))
d6a28714
JH
2059 goto got_it;
2060 if (s >= strend)
2061 break;
b8c5462f 2062 s += UTF8SKIP(s);
d6a28714
JH
2063 };
2064 }
2065 else {
2066 do {
24b23f37 2067 if (regtry(&reginfo, &s))
d6a28714
JH
2068 goto got_it;
2069 } while (s++ < strend);
2070 }
2071 }
2072
2073 /* Failure. */
2074 goto phooey;
2075
2076got_it:
2077 RX_MATCH_TAINTED_set(prog, PL_reg_flags & RF_tainted);
2078
2079 if (PL_reg_eval_set) {
2080 /* Preserve the current value of $^R */
2081 if (oreplsv != GvSV(PL_replgv))
2082 sv_setsv(oreplsv, GvSV(PL_replgv));/* So that when GvSV(replgv) is
2083 restored, the value remains
2084 the same. */
4f639d21 2085 restore_pos(aTHX_ prog);
d6a28714 2086 }
81714fb9
YO
2087 if (prog->paren_names)
2088 (void)hv_iterinit(prog->paren_names);
d6a28714
JH
2089
2090 /* make sure $`, $&, $', and $digit will work later */
2091 if ( !(flags & REXEC_NOT_FIRST) ) {
ed252734 2092 RX_MATCH_COPY_FREE(prog);
d6a28714 2093 if (flags & REXEC_COPY_STR) {
be8e71aa 2094 const I32 i = PL_regeol - startpos + (stringarg - strbeg);
f8c7b90f 2095#ifdef PERL_OLD_COPY_ON_WRITE
ed252734
NC
2096 if ((SvIsCOW(sv)
2097 || (SvFLAGS(sv) & CAN_COW_MASK) == CAN_COW_FLAGS)) {
2098 if (DEBUG_C_TEST) {
2099 PerlIO_printf(Perl_debug_log,
2100 "Copy on write: regexp capture, type %d\n",
2101 (int) SvTYPE(sv));
2102 }
2103 prog->saved_copy = sv_setsv_cow(prog->saved_copy, sv);
d5263905 2104 prog->subbeg = (char *)SvPVX_const(prog->saved_copy);
ed252734
NC
2105 assert (SvPOKp(prog->saved_copy));
2106 } else
2107#endif
2108 {
2109 RX_MATCH_COPIED_on(prog);
2110 s = savepvn(strbeg, i);
2111 prog->subbeg = s;
2112 }
d6a28714 2113 prog->sublen = i;
d6a28714
JH
2114 }
2115 else {
2116 prog->subbeg = strbeg;
2117 prog->sublen = PL_regeol - strbeg; /* strend may have been modified */
2118 }
2119 }
9041c2e3 2120
d6a28714
JH
2121 return 1;
2122
2123phooey:
a3621e74 2124 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "%sMatch failed%s\n",
e4584336 2125 PL_colors[4], PL_colors[5]));
d6a28714 2126 if (PL_reg_eval_set)
4f639d21 2127 restore_pos(aTHX_ prog);
fae667d5 2128 if (swap_on_fail)
c74340f9 2129 /* we failed :-( roll it back */
fae667d5
YO
2130 swap_match_buff(prog);
2131
d6a28714
JH
2132 return 0;
2133}
2134
6bda09f9 2135
d6a28714
JH
2136/*
2137 - regtry - try match at specific point
2138 */
2139STATIC I32 /* 0 failure, 1 success */
24b23f37 2140S_regtry(pTHX_ regmatch_info *reginfo, char **startpos)
d6a28714 2141{
97aff369 2142 dVAR;
d6a28714 2143 CHECKPOINT lastcp;
3b0527fe 2144 regexp *prog = reginfo->prog;
f8fc2ecf 2145 RXi_GET_DECL(prog,progi);
a3621e74 2146 GET_RE_DEBUG_FLAGS_DECL;
24b23f37 2147 reginfo->cutpoint=NULL;
d6a28714 2148
bbe252da 2149 if ((prog->extflags & RXf_EVAL_SEEN) && !PL_reg_eval_set) {
d6a28714
JH
2150 MAGIC *mg;
2151
2152 PL_reg_eval_set = RS_init;
a3621e74 2153 DEBUG_EXECUTE_r(DEBUG_s(
b900a521
JH
2154 PerlIO_printf(Perl_debug_log, " setting stack tmpbase at %"IVdf"\n",
2155 (IV)(PL_stack_sp - PL_stack_base));
d6a28714 2156 ));
ea8d6ae1 2157 SAVESTACK_CXPOS();
d6a28714
JH
2158 cxstack[cxstack_ix].blk_oldsp = PL_stack_sp - PL_stack_base;
2159 /* Otherwise OP_NEXTSTATE will free whatever on stack now. */
2160 SAVETMPS;
2161 /* Apparently this is not needed, judging by wantarray. */
e8347627 2162 /* SAVEI8(cxstack[cxstack_ix].blk_gimme);
d6a28714
JH
2163 cxstack[cxstack_ix].blk_gimme = G_SCALAR; */
2164
3b0527fe 2165 if (reginfo->sv) {
d6a28714 2166 /* Make $_ available to executed code. */
3b0527fe 2167 if (reginfo->sv != DEFSV) {
59f00321 2168 SAVE_DEFSV;
3b0527fe 2169 DEFSV = reginfo->sv;
b8c5462f 2170 }
d6a28714 2171
3b0527fe
DM
2172 if (!(SvTYPE(reginfo->sv) >= SVt_PVMG && SvMAGIC(reginfo->sv)
2173 && (mg = mg_find(reginfo->sv, PERL_MAGIC_regex_global)))) {
d6a28714 2174 /* prepare for quick setting of pos */
d300d9fa 2175#ifdef PERL_OLD_COPY_ON_WRITE
51a9ea20
NC
2176 if (SvIsCOW(reginfo->sv))
2177 sv_force_normal_flags(reginfo->sv, 0);
d300d9fa 2178#endif
3dab1dad 2179 mg = sv_magicext(reginfo->sv, NULL, PERL_MAGIC_regex_global,
d300d9fa 2180 &PL_vtbl_mglob, NULL, 0);
d6a28714 2181 mg->mg_len = -1;
b8c5462f 2182 }
d6a28714
JH
2183 PL_reg_magic = mg;
2184 PL_reg_oldpos = mg->mg_len;
4f639d21 2185 SAVEDESTRUCTOR_X(restore_pos, prog);
d6a28714 2186 }
09687e5a 2187 if (!PL_reg_curpm) {
a02a5408 2188 Newxz(PL_reg_curpm, 1, PMOP);
09687e5a
AB
2189#ifdef USE_ITHREADS
2190 {
be8e71aa 2191 SV* const repointer = newSViv(0);
577e12cc 2192 /* so we know which PL_regex_padav element is PL_reg_curpm */
35061a7e 2193 SvFLAGS(repointer) |= SVf_BREAK;
09687e5a
AB
2194 av_push(PL_regex_padav,repointer);
2195 PL_reg_curpm->op_pmoffset = av_len(PL_regex_padav);
2196 PL_regex_pad = AvARRAY(PL_regex_padav);
2197 }
2198#endif
2199 }
aaa362c4 2200 PM_SETRE(PL_reg_curpm, prog);
d6a28714
JH
2201 PL_reg_oldcurpm = PL_curpm;
2202 PL_curpm = PL_reg_curpm;
2203 if (RX_MATCH_COPIED(prog)) {
2204 /* Here is a serious problem: we cannot rewrite subbeg,
2205 since it may be needed if this match fails. Thus
2206 $` inside (?{}) could fail... */
2207 PL_reg_oldsaved = prog->subbeg;
2208 PL_reg_oldsavedlen = prog->sublen;
f8c7b90f 2209#ifdef PERL_OLD_COPY_ON_WRITE
ed252734
NC
2210 PL_nrs = prog->saved_copy;
2211#endif
d6a28714
JH
2212 RX_MATCH_COPIED_off(prog);
2213 }
2214 else
bd61b366 2215 PL_reg_oldsaved = NULL;
d6a28714
JH
2216 prog->subbeg = PL_bostr;
2217 prog->sublen = PL_regeol - PL_bostr; /* strend may have been modified */
2218 }
24b23f37 2219 DEBUG_EXECUTE_r(PL_reg_starttry = *startpos);
f0ab9afb 2220 prog->offs[0].start = *startpos - PL_bostr;
24b23f37 2221 PL_reginput = *startpos;
d6a28714 2222 PL_reglastparen = &prog->lastparen;
a01268b5 2223 PL_reglastcloseparen = &prog->lastcloseparen;
d6a28714 2224 prog->lastparen = 0;
03994de8 2225 prog->lastcloseparen = 0;
d6a28714 2226 PL_regsize = 0;
f0ab9afb 2227 PL_regoffs = prog->offs;
d6a28714
JH
2228 if (PL_reg_start_tmpl <= prog->nparens) {
2229 PL_reg_start_tmpl = prog->nparens*3/2 + 3;
2230 if(PL_reg_start_tmp)
2231 Renew(PL_reg_start_tmp, PL_reg_start_tmpl, char*);
2232 else
a02a5408 2233 Newx(PL_reg_start_tmp, PL_reg_start_tmpl, char*);
d6a28714
JH
2234 }
2235
2236 /* XXXX What this code is doing here?!!! There should be no need
2237 to do this again and again, PL_reglastparen should take care of
3dd2943c 2238 this! --ilya*/
dafc8851
JH
2239
2240 /* Tests pat.t#187 and split.t#{13,14} seem to depend on this code.
2241 * Actually, the code in regcppop() (which Ilya may be meaning by
daf18116
JH
2242 * PL_reglastparen), is not needed at all by the test suite
2243 * (op/regexp, op/pat, op/split), but that code is needed, oddly
2244 * enough, for building DynaLoader, or otherwise this
2245 * "Error: '*' not in typemap in DynaLoader.xs, line 164"
2246 * will happen. Meanwhile, this code *is* needed for the
2247 * above-mentioned test suite tests to succeed. The common theme
2248 * on those tests seems to be returning null fields from matches.
2249 * --jhi */
dafc8851 2250#if 1
d6a28714 2251 if (prog->nparens) {
f0ab9afb 2252 regexp_paren_pair *pp = PL_regoffs;
097eb12c 2253 register I32 i;
eb160463 2254 for (i = prog->nparens; i > (I32)*PL_reglastparen; i--) {
f0ab9afb
NC
2255 ++pp;
2256 pp->start = -1;
2257 pp->end = -1;
d6a28714
JH
2258 }
2259 }
dafc8851 2260#endif
02db2b7b 2261 REGCP_SET(lastcp);
f8fc2ecf 2262 if (regmatch(reginfo, progi->program + 1)) {
f0ab9afb 2263 PL_regoffs[0].end = PL_reginput - PL_bostr;
d6a28714
JH
2264 return 1;
2265 }
24b23f37
YO
2266 if (reginfo->cutpoint)
2267 *startpos= reginfo->cutpoint;
02db2b7b 2268 REGCP_UNWIND(lastcp);
d6a28714
JH
2269 return 0;
2270}
2271
02db2b7b 2272
8ba1375e
MJD
2273#define sayYES goto yes
2274#define sayNO goto no
262b90c4 2275#define sayNO_SILENT goto no_silent
8ba1375e 2276
f9f4320a
YO
2277/* we dont use STMT_START/END here because it leads to
2278 "unreachable code" warnings, which are bogus, but distracting. */
2279#define CACHEsayNO \
c476f425
DM
2280 if (ST.cache_mask) \
2281 PL_reg_poscache[ST.cache_offset] |= ST.cache_mask; \
f9f4320a 2282 sayNO
3298f257 2283
a3621e74 2284/* this is used to determine how far from the left messages like
265c4333
YO
2285 'failed...' are printed. It should be set such that messages
2286 are inline with the regop output that created them.
a3621e74 2287*/
265c4333 2288#define REPORT_CODE_OFF 32
a3621e74
YO
2289
2290
2291/* Make sure there is a test for this +1 options in re_tests */
2292#define TRIE_INITAL_ACCEPT_BUFFLEN 4;
2293
40a82448
DM
2294#define CHRTEST_UNINIT -1001 /* c1/c2 haven't been calculated yet */
2295#define CHRTEST_VOID -1000 /* the c1/c2 "next char" test should be skipped */
9e137952 2296
86545054
DM
2297#define SLAB_FIRST(s) (&(s)->states[0])
2298#define SLAB_LAST(s) (&(s)->states[PERL_REGMATCH_SLAB_SLOTS-1])
2299
5d9a96ca
DM
2300/* grab a new slab and return the first slot in it */
2301
2302STATIC regmatch_state *
2303S_push_slab(pTHX)
2304{
a35a87e7 2305#if PERL_VERSION < 9 && !defined(PERL_CORE)
54df2634
NC
2306 dMY_CXT;
2307#endif
5d9a96ca
DM
2308 regmatch_slab *s = PL_regmatch_slab->next;
2309 if (!s) {
2310 Newx(s, 1, regmatch_slab);
2311 s->prev = PL_regmatch_slab;
2312 s->next = NULL;
2313 PL_regmatch_slab->next = s;
2314 }
2315 PL_regmatch_slab = s;
86545054 2316 return SLAB_FIRST(s);
5d9a96ca 2317}
5b47454d 2318
95b24440 2319
40a82448
DM
2320/* push a new state then goto it */
2321
2322#define PUSH_STATE_GOTO(state, node) \
2323 scan = node; \
2324 st->resume_state = state; \
2325 goto push_state;
2326
2327/* push a new state with success backtracking, then goto it */
2328
2329#define PUSH_YES_STATE_GOTO(state, node) \
2330 scan = node; \
2331 st->resume_state = state; \
2332 goto push_yes_state;
2333
aa283a38 2334
aa283a38 2335
d6a28714 2336/*
95b24440 2337
bf1f174e
DM
2338regmatch() - main matching routine
2339
2340This is basically one big switch statement in a loop. We execute an op,
2341set 'next' to point the next op, and continue. If we come to a point which
2342we may need to backtrack to on failure such as (A|B|C), we push a
2343backtrack state onto the backtrack stack. On failure, we pop the top
2344state, and re-enter the loop at the state indicated. If there are no more
2345states to pop, we return failure.
2346
2347Sometimes we also need to backtrack on success; for example /A+/, where
2348after successfully matching one A, we need to go back and try to
2349match another one; similarly for lookahead assertions: if the assertion
2350completes successfully, we backtrack to the state just before the assertion
2351and then carry on. In these cases, the pushed state is marked as
2352'backtrack on success too'. This marking is in fact done by a chain of
2353pointers, each pointing to the previous 'yes' state. On success, we pop to
2354the nearest yes state, discarding any intermediate failure-only states.
2355Sometimes a yes state is pushed just to force some cleanup code to be
2356called at the end of a successful match or submatch; e.g. (??{$re}) uses
2357it to free the inner regex.
2358
2359Note that failure backtracking rewinds the cursor position, while
2360success backtracking leaves it alone.
2361
2362A pattern is complete when the END op is executed, while a subpattern
2363such as (?=foo) is complete when the SUCCESS op is executed. Both of these
2364ops trigger the "pop to last yes state if any, otherwise return true"
2365behaviour.
2366
2367A common convention in this function is to use A and B to refer to the two
2368subpatterns (or to the first nodes thereof) in patterns like /A*B/: so A is
2369the subpattern to be matched possibly multiple times, while B is the entire
2370rest of the pattern. Variable and state names reflect this convention.
2371
2372The states in the main switch are the union of ops and failure/success of
2373substates associated with with that op. For example, IFMATCH is the op
2374that does lookahead assertions /(?=A)B/ and so the IFMATCH state means
2375'execute IFMATCH'; while IFMATCH_A is a state saying that we have just
2376successfully matched A and IFMATCH_A_fail is a state saying that we have
2377just failed to match A. Resume states always come in pairs. The backtrack
2378state we push is marked as 'IFMATCH_A', but when that is popped, we resume
2379at IFMATCH_A or IFMATCH_A_fail, depending on whether we are backtracking
2380on success or failure.
2381
2382The struct that holds a backtracking state is actually a big union, with
2383one variant for each major type of op. The variable st points to the
2384top-most backtrack struct. To make the code clearer, within each
2385block of code we #define ST to alias the relevant union.
2386
2387Here's a concrete example of a (vastly oversimplified) IFMATCH
2388implementation:
2389
2390 switch (state) {
2391 ....
2392
2393#define ST st->u.ifmatch
2394
2395 case IFMATCH: // we are executing the IFMATCH op, (?=A)B
2396 ST.foo = ...; // some state we wish to save
95b24440 2397 ...
bf1f174e
DM
2398 // push a yes backtrack state with a resume value of
2399 // IFMATCH_A/IFMATCH_A_fail, then continue execution at the
2400 // first node of A:
2401 PUSH_YES_STATE_GOTO(IFMATCH_A, A);
2402 // NOTREACHED
2403
2404 case IFMATCH_A: // we have successfully executed A; now continue with B
2405 next = B;
2406 bar = ST.foo; // do something with the preserved value
2407 break;
2408
2409 case IFMATCH_A_fail: // A failed, so the assertion failed
2410 ...; // do some housekeeping, then ...
2411 sayNO; // propagate the failure
2412
2413#undef ST
95b24440 2414
bf1f174e
DM
2415 ...
2416 }
95b24440 2417
bf1f174e
DM
2418For any old-timers reading this who are familiar with the old recursive
2419approach, the code above is equivalent to:
95b24440 2420
bf1f174e
DM
2421 case IFMATCH: // we are executing the IFMATCH op, (?=A)B
2422 {
2423 int foo = ...
95b24440 2424 ...
bf1f174e
DM
2425 if (regmatch(A)) {
2426 next = B;
2427 bar = foo;
2428 break;
95b24440 2429 }
bf1f174e
DM
2430 ...; // do some housekeeping, then ...
2431 sayNO; // propagate the failure
95b24440 2432 }
bf1f174e
DM
2433
2434The topmost backtrack state, pointed to by st, is usually free. If you
2435want to claim it, populate any ST.foo fields in it with values you wish to
2436save, then do one of
2437
2438 PUSH_STATE_GOTO(resume_state, node);
2439 PUSH_YES_STATE_GOTO(resume_state, node);
2440
2441which sets that backtrack state's resume value to 'resume_state', pushes a
2442new free entry to the top of the backtrack stack, then goes to 'node'.
2443On backtracking, the free slot is popped, and the saved state becomes the
2444new free state. An ST.foo field in this new top state can be temporarily
2445accessed to retrieve values, but once the main loop is re-entered, it
2446becomes available for reuse.
2447
2448Note that the depth of the backtrack stack constantly increases during the
2449left-to-right execution of the pattern, rather than going up and down with
2450the pattern nesting. For example the stack is at its maximum at Z at the
2451end of the pattern, rather than at X in the following:
2452
2453 /(((X)+)+)+....(Y)+....Z/
2454
2455The only exceptions to this are lookahead/behind assertions and the cut,
2456(?>A), which pop all the backtrack states associated with A before
2457continuing.
2458
2459Bascktrack state structs are allocated in slabs of about 4K in size.
2460PL_regmatch_state and st always point to the currently active state,
2461and PL_regmatch_slab points to the slab currently containing
2462PL_regmatch_state. The first time regmatch() is called, the first slab is
2463allocated, and is never freed until interpreter destruction. When the slab
2464is full, a new one is allocated and chained to the end. At exit from
2465regmatch(), slabs allocated since entry are freed.
2466
2467*/
95b24440 2468
40a82448 2469
5bc10b2c 2470#define DEBUG_STATE_pp(pp) \
265c4333 2471 DEBUG_STATE_r({ \
5bc10b2c
DM
2472 DUMP_EXEC_POS(locinput, scan, do_utf8); \
2473 PerlIO_printf(Perl_debug_log, \
5d458dd8 2474 " %*s"pp" %s%s%s%s%s\n", \
5bc10b2c 2475 depth*2, "", \
13d6edb4 2476 PL_reg_name[st->resume_state], \
5d458dd8
YO
2477 ((st==yes_state||st==mark_state) ? "[" : ""), \
2478 ((st==yes_state) ? "Y" : ""), \
2479 ((st==mark_state) ? "M" : ""), \
2480 ((st==yes_state||st==mark_state) ? "]" : "") \
2481 ); \
265c4333 2482 });
5bc10b2c 2483
40a82448 2484
3dab1dad 2485#define REG_NODE_NUM(x) ((x) ? (int)((x)-prog) : -1)
95b24440 2486
3df15adc 2487#ifdef DEBUGGING
5bc10b2c 2488
ab3bbdeb
YO
2489STATIC void
2490S_debug_start_match(pTHX_ const regexp *prog, const bool do_utf8,
2491 const char *start, const char *end, const char *blurb)
2492{
bbe252da 2493 const bool utf8_pat= prog->extflags & RXf_UTF8 ? 1 : 0;
ab3bbdeb
YO
2494 if (!PL_colorset)
2495 reginitcolors();
2496 {
2497 RE_PV_QUOTED_DECL(s0, utf8_pat, PERL_DEBUG_PAD_ZERO(0),
2498 prog->precomp, prog->prelen, 60);
2499
2500 RE_PV_QUOTED_DECL(s1, do_utf8, PERL_DEBUG_PAD_ZERO(1),
2501 start, end - start, 60);
2502
2503 PerlIO_printf(Perl_debug_log,
2504 "%s%s REx%s %s against %s\n",
2505 PL_colors[4], blurb, PL_colors[5], s0, s1);
2506
2507 if (do_utf8||utf8_pat)
1de06328
YO
2508 PerlIO_printf(Perl_debug_log, "UTF-8 %s%s%s...\n",
2509 utf8_pat ? "pattern" : "",
2510 utf8_pat && do_utf8 ? " and " : "",
2511 do_utf8 ? "string" : ""
ab3bbdeb
YO
2512 );
2513 }
2514}
3df15adc
YO
2515
2516STATIC void
786e8c11
YO
2517S_dump_exec_pos(pTHX_ const char *locinput,
2518 const regnode *scan,
2519 const char *loc_regeol,
2520 const char *loc_bostr,
2521 const char *loc_reg_starttry,
2522 const bool do_utf8)
07be1b83 2523{
786e8c11 2524 const int docolor = *PL_colors[0] || *PL_colors[2] || *PL_colors[4];
07be1b83 2525 const int taill = (docolor ? 10 : 7); /* 3 chars for "> <" */
786e8c11 2526 int l = (loc_regeol - locinput) > taill ? taill : (loc_regeol - locinput);
07be1b83
YO
2527 /* The part of the string before starttry has one color
2528 (pref0_len chars), between starttry and current
2529 position another one (pref_len - pref0_len chars),
2530 after the current position the third one.
2531 We assume that pref0_len <= pref_len, otherwise we
2532 decrease pref0_len. */
786e8c11
YO
2533 int pref_len = (locinput - loc_bostr) > (5 + taill) - l
2534 ? (5 + taill) - l : locinput - loc_bostr;
07be1b83
YO
2535 int pref0_len;
2536
2537 while (do_utf8 && UTF8_IS_CONTINUATION(*(U8*)(locinput - pref_len)))
2538 pref_len++;
786e8c11
YO
2539 pref0_len = pref_len - (locinput - loc_reg_starttry);
2540 if (l + pref_len < (5 + taill) && l < loc_regeol - locinput)
2541 l = ( loc_regeol - locinput > (5 + taill) - pref_len
2542 ? (5 + taill) - pref_len : loc_regeol - locinput);
07be1b83
YO
2543 while (do_utf8 && UTF8_IS_CONTINUATION(*(U8*)(locinput + l)))
2544 l--;
2545 if (pref0_len < 0)
2546 pref0_len = 0;
2547 if (pref0_len > pref_len)
2548 pref0_len = pref_len;
2549 {
3df15adc 2550 const int is_uni = (do_utf8 && OP(scan) != CANY) ? 1 : 0;
0df25f3d 2551
ab3bbdeb 2552 RE_PV_COLOR_DECL(s0,len0,is_uni,PERL_DEBUG_PAD(0),
1de06328 2553 (locinput - pref_len),pref0_len, 60, 4, 5);
0df25f3d 2554
ab3bbdeb 2555 RE_PV_COLOR_DECL(s1,len1,is_uni,PERL_DEBUG_PAD(1),
3df15adc 2556 (locinput - pref_len + pref0_len),
1de06328 2557 pref_len - pref0_len, 60, 2, 3);
0df25f3d 2558
ab3bbdeb 2559 RE_PV_COLOR_DECL(s2,len2,is_uni,PERL_DEBUG_PAD(2),
1de06328 2560 locinput, loc_regeol - locinput, 10, 0, 1);
0df25f3d 2561
1de06328 2562 const STRLEN tlen=len0+len1+len2;
3df15adc 2563 PerlIO_printf(Perl_debug_log,
ab3bbdeb 2564 "%4"IVdf" <%.*s%.*s%s%.*s>%*s|",
786e8c11 2565 (IV)(locinput - loc_bostr),
07be1b83 2566 len0, s0,
07be1b83 2567 len1, s1,
07be1b83 2568 (docolor ? "" : "> <"),
07be1b83 2569 len2, s2,
f9f4320a 2570 (int)(tlen > 19 ? 0 : 19 - tlen),
07be1b83
YO
2571 "");
2572 }
2573}
3df15adc 2574
07be1b83
YO
2575#endif
2576
0a4db386
YO
2577/* reg_check_named_buff_matched()
2578 * Checks to see if a named buffer has matched. The data array of
2579 * buffer numbers corresponding to the buffer is expected to reside
2580 * in the regexp->data->data array in the slot stored in the ARG() of
2581 * node involved. Note that this routine doesn't actually care about the
2582 * name, that information is not preserved from compilation to execution.
2583 * Returns the index of the leftmost defined buffer with the given name
2584 * or 0 if non of the buffers matched.
2585 */
2586STATIC I32
2587S_reg_check_named_buff_matched(pTHX_ const regexp *rex, const regnode *scan) {
2588 I32 n;
f8fc2ecf
YO
2589 RXi_GET_DECL(rex,rexi);
2590 SV *sv_dat=(SV*)rexi->data->data[ ARG( scan ) ];
0a4db386
YO
2591 I32 *nums=(I32*)SvPVX(sv_dat);
2592 for ( n=0; n<SvIVX(sv_dat); n++ ) {
2593 if ((I32)*PL_reglastparen >= nums[n] &&
f0ab9afb 2594 PL_regoffs[nums[n]].end != -1)
0a4db386
YO
2595 {
2596 return nums[n];
2597 }
2598 }
2599 return 0;
2600}
2601
28d8d7f4
YO
2602#define SETREX(Re1,Re2) \
2603 if (PL_reg_eval_set) PM_SETRE((PL_reg_curpm), (Re2)); \
2604 Re1 = (Re2)
2605
d6a28714 2606STATIC I32 /* 0 failure, 1 success */
24b23f37 2607S_regmatch(pTHX_ regmatch_info *reginfo, regnode *prog)
d6a28714 2608{
a35a87e7 2609#if PERL_VERSION < 9 && !defined(PERL_CORE)
54df2634
NC
2610 dMY_CXT;
2611#endif
27da23d5 2612 dVAR;
95b24440 2613 register const bool do_utf8 = PL_reg_match_utf8;
4ad0818d 2614 const U32 uniflags = UTF8_ALLOW_DEFAULT;
95b24440 2615
3b0527fe 2616 regexp *rex = reginfo->prog;
f8fc2ecf
YO
2617 RXi_GET_DECL(rex,rexi);
2618
5d9a96ca
DM
2619 regmatch_slab *orig_slab;
2620 regmatch_state *orig_state;
a3621e74 2621
5d9a96ca
DM
2622 /* the current state. This is a cached copy of PL_regmatch_state */
2623 register regmatch_state *st;
95b24440 2624
5d9a96ca
DM
2625 /* cache heavy used fields of st in registers */
2626 register regnode *scan;
2627 register regnode *next;
438e9bae 2628 register U32 n = 0; /* general value; init to avoid compiler warning */
24d3c4a9 2629 register I32 ln = 0; /* len or last; init to avoid compiler warning */
5d9a96ca 2630 register char *locinput = PL_reginput;
5d9a96ca 2631 register I32 nextchr; /* is always set to UCHARAT(locinput) */
24d3c4a9 2632
b69b0499 2633 bool result = 0; /* return value of S_regmatch */
24d3c4a9 2634 int depth = 0; /* depth of backtrack stack */
4b196cd4
YO
2635 U32 nochange_depth = 0; /* depth of GOSUB recursion with nochange */
2636 const U32 max_nochange_depth =
2637 (3 * rex->nparens > MAX_RECURSE_EVAL_NOCHANGE_DEPTH) ?
2638 3 * rex->nparens : MAX_RECURSE_EVAL_NOCHANGE_DEPTH;
2639
77cb431f
DM
2640 regmatch_state *yes_state = NULL; /* state to pop to on success of
2641 subpattern */
e2e6a0f1
YO
2642 /* mark_state piggy backs on the yes_state logic so that when we unwind
2643 the stack on success we can update the mark_state as we go */
2644 regmatch_state *mark_state = NULL; /* last mark state we have seen */
5d458dd8 2645
faec1544 2646 regmatch_state *cur_eval = NULL; /* most recent EVAL_AB state */
b8591aee 2647 struct regmatch_state *cur_curlyx = NULL; /* most recent curlyx */
40a82448 2648 U32 state_num;
5d458dd8
YO
2649 bool no_final = 0; /* prevent failure from backtracking? */
2650 bool do_cutgroup = 0; /* no_final only until next branch/trie entry */
e2e6a0f1 2651 char *startpoint = PL_reginput;
5d458dd8
YO
2652 SV *popmark = NULL; /* are we looking for a mark? */
2653 SV *sv_commit = NULL; /* last mark name seen in failure */
2654 SV *sv_yes_mark = NULL; /* last mark name we have seen
2655 during a successfull match */
2656 U32 lastopen = 0; /* last open we saw */
2657 bool has_cutgroup = RX_HAS_CUTGROUP(rex) ? 1 : 0;
58e23c8d 2658
5d458dd8 2659
24d3c4a9
DM
2660 /* these three flags are set by various ops to signal information to
2661 * the very next op. They have a useful lifetime of exactly one loop
2662 * iteration, and are not preserved or restored by state pushes/pops
2663 */
2664 bool sw = 0; /* the condition value in (?(cond)a|b) */
2665 bool minmod = 0; /* the next "{n,m}" is a "{n,m}?" */
2666 int logical = 0; /* the following EVAL is:
2667 0: (?{...})
2668 1: (?(?{...})X|Y)
2669 2: (??{...})
2670 or the following IFMATCH/UNLESSM is:
2671 false: plain (?=foo)
2672 true: used as a condition: (?(?=foo))
2673 */
2674
95b24440 2675#ifdef DEBUGGING
e68ec53f 2676 GET_RE_DEBUG_FLAGS_DECL;
d6a28714
JH
2677#endif
2678
3b57cd43 2679 DEBUG_OPTIMISE_r( DEBUG_EXECUTE_r({
24b23f37 2680 PerlIO_printf(Perl_debug_log,"regmatch start\n");
3b57cd43 2681 }));
5d9a96ca
DM
2682 /* on first ever call to regmatch, allocate first slab */
2683 if (!PL_regmatch_slab) {
2684 Newx(PL_regmatch_slab, 1, regmatch_slab);
2685 PL_regmatch_slab->prev = NULL;
2686 PL_regmatch_slab->next = NULL;
86545054 2687 PL_regmatch_state = SLAB_FIRST(PL_regmatch_slab);
5d9a96ca
DM
2688 }
2689
2690 /* remember current high-water mark for exit */
2691 /* XXX this should be done with SAVE* instead */
2692 orig_slab = PL_regmatch_slab;
2693 orig_state = PL_regmatch_state;
2694
2695 /* grab next free state slot */
2696 st = ++PL_regmatch_state;
86545054 2697 if (st > SLAB_LAST(PL_regmatch_slab))
5d9a96ca
DM
2698 st = PL_regmatch_state = S_push_slab(aTHX);
2699
d6a28714
JH
2700 /* Note that nextchr is a byte even in UTF */
2701 nextchr = UCHARAT(locinput);
2702 scan = prog;
2703 while (scan != NULL) {
8ba1375e 2704
a3621e74 2705 DEBUG_EXECUTE_r( {
6136c704 2706 SV * const prop = sv_newmortal();
1de06328 2707 regnode *rnext=regnext(scan);
786e8c11 2708 DUMP_EXEC_POS( locinput, scan, do_utf8 );
32fc9b6a 2709 regprop(rex, prop, scan);
07be1b83
YO
2710
2711 PerlIO_printf(Perl_debug_log,
2712 "%3"IVdf":%*s%s(%"IVdf")\n",
f8fc2ecf 2713 (IV)(scan - rexi->program), depth*2, "",
07be1b83 2714 SvPVX_const(prop),
1de06328 2715 (PL_regkind[OP(scan)] == END || !rnext) ?
f8fc2ecf 2716 0 : (IV)(rnext - rexi->program));
2a782b5b 2717 });
d6a28714
JH
2718
2719 next = scan + NEXT_OFF(scan);
2720 if (next == scan)
2721 next = NULL;
40a82448 2722 state_num = OP(scan);
d6a28714 2723
40a82448
DM
2724 reenter_switch:
2725 switch (state_num) {
d6a28714 2726 case BOL:
7fba1cd6 2727 if (locinput == PL_bostr)
d6a28714 2728 {
3b0527fe 2729 /* reginfo->till = reginfo->bol; */
b8c5462f
JH
2730 break;
2731 }
d6a28714
JH
2732 sayNO;
2733 case MBOL:
12d33761
HS
2734 if (locinput == PL_bostr ||
2735 ((nextchr || locinput < PL_regeol) && locinput[-1] == '\n'))
d6a28714 2736 {
b8c5462f
JH
2737 break;
2738 }
d6a28714
JH
2739 sayNO;
2740 case SBOL:
c2a73568 2741 if (locinput == PL_bostr)
b8c5462f 2742 break;
d6a28714
JH
2743 sayNO;
2744 case GPOS:
3b0527fe 2745 if (locinput == reginfo->ganch)
d6a28714
JH
2746 break;
2747 sayNO;
ee9b8eae
YO
2748
2749 case KEEPS:
2750 /* update the startpoint */
f0ab9afb 2751 st->u.keeper.val = PL_regoffs[0].start;
ee9b8eae 2752 PL_reginput = locinput;
f0ab9afb 2753 PL_regoffs[0].start = locinput - PL_bostr;
ee9b8eae
YO
2754 PUSH_STATE_GOTO(KEEPS_next, next);
2755 /*NOT-REACHED*/
2756 case KEEPS_next_fail:
2757 /* rollback the start point change */
f0ab9afb 2758 PL_regoffs[0].start = st->u.keeper.val;
ee9b8eae
YO
2759 sayNO_SILENT;
2760 /*NOT-REACHED*/
d6a28714 2761 case EOL:
d6a28714
JH
2762 goto seol;
2763 case MEOL:
d6a28714 2764 if ((nextchr || locinput < PL_regeol) && nextchr != '\n')
b8c5462f 2765 sayNO;
b8c5462f 2766 break;
d6a28714
JH
2767 case SEOL:
2768 seol:
2769 if ((nextchr || locinput < PL_regeol) && nextchr != '\n')
b8c5462f 2770 sayNO;
d6a28714 2771 if (PL_regeol - locinput > 1)
b8c5462f 2772 sayNO;
b8c5462f 2773 break;
d6a28714
JH
2774 case EOS:
2775 if (PL_regeol != locinput)
b8c5462f 2776 sayNO;
d6a28714 2777 break;
ffc61ed2 2778 case SANY:
d6a28714 2779 if (!nextchr && locinput >= PL_regeol)
4633a7c4 2780 sayNO;
f33976b4
DB
2781 if (do_utf8) {
2782 locinput += PL_utf8skip[nextchr];
2783 if (locinput > PL_regeol)
2784 sayNO;
2785 nextchr = UCHARAT(locinput);
2786 }
2787 else
2788 nextchr = UCHARAT(++locinput);
2789 break;
2790 case CANY:
2791 if (!nextchr && locinput >= PL_regeol)
2792 sayNO;
b8c5462f 2793 nextchr = UCHARAT(++locinput);
a0d0e21e 2794 break;
ffc61ed2 2795 case REG_ANY:
1aa99e6b
IH
2796 if ((!nextchr && locinput >= PL_regeol) || nextchr == '\n')
2797 sayNO;
2798 if (do_utf8) {
b8c5462f 2799 locinput += PL_utf8skip[nextchr];
d6a28714
JH
2800 if (locinput > PL_regeol)
2801 sayNO;
a0ed51b3 2802 nextchr = UCHARAT(locinput);
a0ed51b3 2803 }
1aa99e6b
IH
2804 else
2805 nextchr = UCHARAT(++locinput);
a0ed51b3 2806 break;
166ba7cd
DM
2807
2808#undef ST
2809#define ST st->u.trie
786e8c11
YO
2810 case TRIEC:
2811 /* In this case the charclass data is available inline so
2812 we can fail fast without a lot of extra overhead.
2813 */
2814 if (scan->flags == EXACT || !do_utf8) {
2815 if(!ANYOF_BITMAP_TEST(scan, *locinput)) {
2816 DEBUG_EXECUTE_r(
2817 PerlIO_printf(Perl_debug_log,
2818 "%*s %sfailed to match trie start class...%s\n",
5bc10b2c 2819 REPORT_CODE_OFF+depth*2, "", PL_colors[4], PL_colors[5])
786e8c11
YO
2820 );
2821 sayNO_SILENT;
2822 /* NOTREACHED */
2823 }
2824 }
2825 /* FALL THROUGH */
5b47454d 2826 case TRIE:
3dab1dad 2827 {
07be1b83 2828 /* what type of TRIE am I? (utf8 makes this contextual) */
3dab1dad
YO
2829 const enum { trie_plain, trie_utf8, trie_utf8_fold }
2830 trie_type = do_utf8 ?
2831 (scan->flags == EXACT ? trie_utf8 : trie_utf8_fold)
2832 : trie_plain;
2833
2834 /* what trie are we using right now */
be8e71aa 2835 reg_trie_data * const trie
f8fc2ecf 2836 = (reg_trie_data*)rexi->data->data[ ARG( scan ) ];
55eed653 2837 HV * widecharmap = (HV *)rexi->data->data[ ARG( scan ) + 1 ];
3dab1dad 2838 U32 state = trie->startstate;
166ba7cd 2839
3dab1dad
YO
2840 if (trie->bitmap && trie_type != trie_utf8_fold &&
2841 !TRIE_BITMAP_TEST(trie,*locinput)
2842 ) {
2843 if (trie->states[ state ].wordnum) {
2844 DEBUG_EXECUTE_r(
2845 PerlIO_printf(Perl_debug_log,
2846 "%*s %smatched empty string...%s\n",
5bc10b2c 2847 REPORT_CODE_OFF+depth*2, "", PL_colors[4], PL_colors[5])
3dab1dad
YO
2848 );
2849 break;
2850 } else {
2851 DEBUG_EXECUTE_r(
2852 PerlIO_printf(Perl_debug_log,
786e8c11 2853 "%*s %sfailed to match trie start class...%s\n",
5bc10b2c 2854 REPORT_CODE_OFF+depth*2, "", PL_colors[4], PL_colors[5])
3dab1dad
YO
2855 );
2856 sayNO_SILENT;
2857 }
2858 }
166ba7cd 2859
786e8c11
YO
2860 {
2861 U8 *uc = ( U8* )locinput;
2862
2863 STRLEN len = 0;
2864 STRLEN foldlen = 0;
2865 U8 *uscan = (U8*)NULL;
2866 STRLEN bufflen=0;
2867 SV *sv_accept_buff = NULL;
2868 U8 foldbuf[ UTF8_MAXBYTES_CASE + 1 ];
2869
2870 ST.accepted = 0; /* how many accepting states we have seen */
2871 ST.B = next;
2872 ST.jump = trie->jump;
786e8c11 2873 ST.me = scan;
07be1b83
YO
2874 /*
2875 traverse the TRIE keeping track of all accepting states
2876 we transition through until we get to a failing node.
2877 */
2878
a3621e74 2879 while ( state && uc <= (U8*)PL_regeol ) {
786e8c11 2880 U32 base = trie->states[ state ].trans.base;
f9f4320a 2881 UV uvc = 0;
786e8c11
YO
2882 U16 charid;
2883 /* We use charid to hold the wordnum as we don't use it
2884 for charid until after we have done the wordnum logic.
2885 We define an alias just so that the wordnum logic reads
2886 more naturally. */
2887
2888#define got_wordnum charid
2889 got_wordnum = trie->states[ state ].wordnum;
2890
2891 if ( got_wordnum ) {
2892 if ( ! ST.accepted ) {
5b47454d
DM
2893 ENTER;
2894 SAVETMPS;
2895 bufflen = TRIE_INITAL_ACCEPT_BUFFLEN;
2896 sv_accept_buff=newSV(bufflen *
2897 sizeof(reg_trie_accepted) - 1);
786e8c11 2898 SvCUR_set(sv_accept_buff, 0);
5b47454d
DM
2899 SvPOK_on(sv_accept_buff);
2900 sv_2mortal(sv_accept_buff);
166ba7cd
DM
2901 SAVETMPS;
2902 ST.accept_buff =
5b47454d
DM
2903 (reg_trie_accepted*)SvPV_nolen(sv_accept_buff );
2904 }
786e8c11 2905 do {
166ba7cd 2906 if (ST.accepted >= bufflen) {
5b47454d 2907 bufflen *= 2;
166ba7cd 2908 ST.accept_buff =(reg_trie_accepted*)
5b47454d
DM
2909 SvGROW(sv_accept_buff,
2910 bufflen * sizeof(reg_trie_accepted));
2911 }
2912 SvCUR_set(sv_accept_buff,SvCUR(sv_accept_buff)
2913 + sizeof(reg_trie_accepted));
a3621e74 2914
786e8c11
YO
2915
2916 ST.accept_buff[ST.accepted].wordnum = got_wordnum;
2917 ST.accept_buff[ST.accepted].endpos = uc;
2918 ++ST.accepted;
2919 } while (trie->nextword && (got_wordnum= trie->nextword[got_wordnum]));
2920 }
2921#undef got_wordnum
a3621e74 2922
07be1b83 2923 DEBUG_TRIE_EXECUTE_r({
786e8c11 2924 DUMP_EXEC_POS( (char *)uc, scan, do_utf8 );
a3621e74 2925 PerlIO_printf( Perl_debug_log,
786e8c11 2926 "%*s %sState: %4"UVxf" Accepted: %4"UVxf" ",
5bc10b2c 2927 2+depth * 2, "", PL_colors[4],
786e8c11 2928 (UV)state, (UV)ST.accepted );
07be1b83 2929 });
a3621e74
YO
2930
2931 if ( base ) {
55eed653
NC
2932 REXEC_TRIE_READ_CHAR(trie_type, trie, widecharmap, uc,
2933 uscan, len, uvc, charid, foldlen,
2934 foldbuf, uniflags);
a3621e74 2935
5b47454d
DM
2936 if (charid &&
2937 (base + charid > trie->uniquecharcount )
2938 && (base + charid - 1 - trie->uniquecharcount
2939 < trie->lasttrans)
2940 && trie->trans[base + charid - 1 -
2941 trie->uniquecharcount].check == state)
2942 {
2943 state = trie->trans[base + charid - 1 -
2944 trie->uniquecharcount ].next;
2945 }
2946 else {
2947 state = 0;
2948 }
2949 uc += len;
2950
2951 }
2952 else {
a3621e74
YO
2953 state = 0;
2954 }
2955 DEBUG_TRIE_EXECUTE_r(
e4584336 2956 PerlIO_printf( Perl_debug_log,
786e8c11 2957 "Charid:%3x CP:%4"UVxf" After State: %4"UVxf"%s\n",
e4584336 2958 charid, uvc, (UV)state, PL_colors[5] );
a3621e74
YO
2959 );
2960 }
166ba7cd 2961 if (!ST.accepted )
a3621e74 2962 sayNO;
a3621e74 2963
166ba7cd
DM
2964 DEBUG_EXECUTE_r(
2965 PerlIO_printf( Perl_debug_log,
2966 "%*s %sgot %"IVdf" possible matches%s\n",
5bc10b2c 2967 REPORT_CODE_OFF + depth * 2, "",
166ba7cd
DM
2968 PL_colors[4], (IV)ST.accepted, PL_colors[5] );
2969 );
786e8c11 2970 }}
fae667d5
YO
2971 goto trie_first_try; /* jump into the fail handler */
2972 /* NOTREACHED */
166ba7cd 2973 case TRIE_next_fail: /* we failed - try next alterative */
fae667d5
YO
2974 if ( ST.jump) {
2975 REGCP_UNWIND(ST.cp);
2976 for (n = *PL_reglastparen; n > ST.lastparen; n--)
f0ab9afb 2977 PL_regoffs[n].end = -1;
fae667d5
YO
2978 *PL_reglastparen = n;
2979 }
2980 trie_first_try:
5d458dd8
YO
2981 if (do_cutgroup) {
2982 do_cutgroup = 0;
2983 no_final = 0;
2984 }
fae667d5
YO
2985
2986 if ( ST.jump) {
2987 ST.lastparen = *PL_reglastparen;
2988 REGCP_SET(ST.cp);
2989 }
166ba7cd
DM
2990 if ( ST.accepted == 1 ) {
2991 /* only one choice left - just continue */
2992 DEBUG_EXECUTE_r({
2b8b4781
NC
2993 AV *const trie_words
2994 = (AV *) rexi->data->data[ARG(ST.me)+TRIE_WORDS_OFFSET];
2995 SV ** const tmp = av_fetch( trie_words,
5c9f2f80 2996 ST.accept_buff[ 0 ].wordnum-1, 0 );
de734bd5
A
2997 SV *sv= tmp ? sv_newmortal() : NULL;
2998
166ba7cd
DM
2999 PerlIO_printf( Perl_debug_log,
3000 "%*s %sonly one match left: #%d <%s>%s\n",
5bc10b2c 3001 REPORT_CODE_OFF+depth*2, "", PL_colors[4],
166ba7cd 3002 ST.accept_buff[ 0 ].wordnum,
de734bd5
A
3003 tmp ? pv_pretty(sv, SvPV_nolen_const(*tmp), SvCUR(*tmp), 0,
3004 PL_colors[0], PL_colors[1],
3005 (SvUTF8(*tmp) ? PERL_PV_ESCAPE_UNI : 0)
3006 )
3007 : "not compiled under -Dr",
166ba7cd
DM
3008 PL_colors[5] );
3009 });
3010 PL_reginput = (char *)ST.accept_buff[ 0 ].endpos;
3011 /* in this case we free tmps/leave before we call regmatch
3012 as we wont be using accept_buff again. */
5d458dd8 3013
166ba7cd
DM
3014 locinput = PL_reginput;
3015 nextchr = UCHARAT(locinput);
5d458dd8
YO
3016 if ( !ST.jump || !ST.jump[ST.accept_buff[0].wordnum])
3017 scan = ST.B;
3018 else
3019 scan = ST.me + ST.jump[ST.accept_buff[0].wordnum];
3020 if (!has_cutgroup) {
3021 FREETMPS;
3022 LEAVE;
3023 } else {
3024 ST.accepted--;
3025 PUSH_YES_STATE_GOTO(TRIE_next, scan);
3026 }
786e8c11 3027
166ba7cd
DM
3028 continue; /* execute rest of RE */
3029 }
fae667d5
YO
3030
3031 if ( !ST.accepted-- ) {
5d458dd8
YO
3032 DEBUG_EXECUTE_r({
3033 PerlIO_printf( Perl_debug_log,
3034 "%*s %sTRIE failed...%s\n",
3035 REPORT_CODE_OFF+depth*2, "",
3036 PL_colors[4],
3037 PL_colors[5] );
3038 });
166ba7cd
DM
3039 FREETMPS;
3040 LEAVE;
5d458dd8 3041 sayNO_SILENT;
fae667d5
YO
3042 /*NOTREACHED*/
3043 }
166ba7cd 3044
a3621e74 3045 /*
166ba7cd
DM
3046 There are at least two accepting states left. Presumably
3047 the number of accepting states is going to be low,
3048 typically two. So we simply scan through to find the one
3049 with lowest wordnum. Once we find it, we swap the last
3050 state into its place and decrement the size. We then try to
3051 match the rest of the pattern at the point where the word
3052 ends. If we succeed, control just continues along the
3053 regex; if we fail we return here to try the next accepting
3054 state
3055 */
a3621e74 3056
166ba7cd
DM
3057 {
3058 U32 best = 0;
3059 U32 cur;
3060 for( cur = 1 ; cur <= ST.accepted ; cur++ ) {
3061 DEBUG_TRIE_EXECUTE_r(
f2278c82 3062 PerlIO_printf( Perl_debug_log,
166ba7cd 3063 "%*s %sgot %"IVdf" (%d) as best, looking at %"IVdf" (%d)%s\n",
5bc10b2c 3064 REPORT_CODE_OFF + depth * 2, "", PL_colors[4],
166ba7cd
DM
3065 (IV)best, ST.accept_buff[ best ].wordnum, (IV)cur,
3066 ST.accept_buff[ cur ].wordnum, PL_colors[5] );
3067 );
3068
3069 if (ST.accept_buff[cur].wordnum <
3070 ST.accept_buff[best].wordnum)
3071 best = cur;
a3621e74 3072 }
166ba7cd
DM
3073
3074 DEBUG_EXECUTE_r({
2b8b4781
NC
3075 AV *const trie_words
3076 = (AV *) rexi->data->data[ARG(ST.me)+TRIE_WORDS_OFFSET];
3077 SV ** const tmp = av_fetch( trie_words,
5c9f2f80 3078 ST.accept_buff[ best ].wordnum - 1, 0 );
7f69552c 3079 regnode *nextop=(!ST.jump || !ST.jump[ST.accept_buff[best].wordnum]) ?
265c4333 3080 ST.B :
7f69552c 3081 ST.me + ST.jump[ST.accept_buff[best].wordnum];
de734bd5
A
3082 SV *sv= tmp ? sv_newmortal() : NULL;
3083
265c4333
YO
3084 PerlIO_printf( Perl_debug_log,
3085 "%*s %strying alternation #%d <%s> at node #%d %s\n",
5bc10b2c 3086 REPORT_CODE_OFF+depth*2, "", PL_colors[4],
166ba7cd 3087 ST.accept_buff[best].wordnum,
de734bd5
A
3088 tmp ? pv_pretty(sv, SvPV_nolen_const(*tmp), SvCUR(*tmp), 0,
3089 PL_colors[0], PL_colors[1],
3090 (SvUTF8(*tmp) ? PERL_PV_ESCAPE_UNI : 0)
3091 ) : "not compiled under -Dr",
265c4333 3092 REG_NODE_NUM(nextop),
166ba7cd
DM
3093 PL_colors[5] );
3094 });
3095
3096 if ( best<ST.accepted ) {
3097 reg_trie_accepted tmp = ST.accept_buff[ best ];
3098 ST.accept_buff[ best ] = ST.accept_buff[ ST.accepted ];
3099 ST.accept_buff[ ST.accepted ] = tmp;
3100 best = ST.accepted;
a3621e74 3101 }
166ba7cd 3102 PL_reginput = (char *)ST.accept_buff[ best ].endpos;
7f69552c 3103 if ( !ST.jump || !ST.jump[ST.accept_buff[best].wordnum]) {
5d458dd8 3104 scan = ST.B;
786e8c11
YO
3105 /* NOTREACHED */
3106 } else {
5d458dd8 3107 scan = ST.me + ST.jump[ST.accept_buff[best].wordnum];
786e8c11
YO
3108 /* NOTREACHED */
3109 }
5d458dd8
YO
3110 if (has_cutgroup) {
3111 PUSH_YES_STATE_GOTO(TRIE_next, scan);
3112 /* NOTREACHED */
3113 } else {
3114 PUSH_STATE_GOTO(TRIE_next, scan);
3115 /* NOTREACHED */
3116 }
786e8c11 3117 /* NOTREACHED */
166ba7cd 3118 }
166ba7cd 3119 /* NOTREACHED */
5d458dd8
YO
3120 case TRIE_next:
3121 FREETMPS;
3122 LEAVE;
3123 sayYES;
166ba7cd
DM
3124#undef ST
3125
95b24440
DM
3126 case EXACT: {
3127 char *s = STRING(scan);
24d3c4a9 3128 ln = STR_LEN(scan);
eb160463 3129 if (do_utf8 != UTF) {
bc517b45 3130 /* The target and the pattern have differing utf8ness. */
1aa99e6b 3131 char *l = locinput;
24d3c4a9 3132 const char * const e = s + ln;
a72c7584 3133
5ff6fc6d
JH
3134 if (do_utf8) {
3135 /* The target is utf8, the pattern is not utf8. */
1aa99e6b 3136 while (s < e) {
a3b680e6 3137 STRLEN ulen;
1aa99e6b 3138 if (l >= PL_regeol)
5ff6fc6d
JH
3139 sayNO;
3140 if (NATIVE_TO_UNI(*(U8*)s) !=
89ebb4a3 3141 utf8n_to_uvuni((U8*)l, UTF8_MAXBYTES, &ulen,
041457d9 3142 uniflags))
5ff6fc6d 3143 sayNO;
bc517b45 3144 l += ulen;
5ff6fc6d 3145 s ++;
1aa99e6b 3146 }
5ff6fc6d
JH
3147 }
3148 else {
3149 /* The target is not utf8, the pattern is utf8. */
1aa99e6b 3150 while (s < e) {
a3b680e6 3151 STRLEN ulen;
1aa99e6b
IH
3152 if (l >= PL_regeol)
3153 sayNO;
5ff6fc6d 3154 if (NATIVE_TO_UNI(*((U8*)l)) !=
89ebb4a3 3155 utf8n_to_uvuni((U8*)s, UTF8_MAXBYTES, &ulen,
041457d9 3156 uniflags))
1aa99e6b 3157 sayNO;
bc517b45 3158 s += ulen;
a72c7584 3159 l ++;
1aa99e6b 3160 }
5ff6fc6d 3161 }
1aa99e6b
IH
3162 locinput = l;
3163 nextchr = UCHARAT(locinput);
3164 break;
3165 }
bc517b45 3166 /* The target and the pattern have the same utf8ness. */
d6a28714
JH
3167 /* Inline the first character, for speed. */
3168 if (UCHARAT(s) != nextchr)
3169 sayNO;
24d3c4a9 3170 if (PL_regeol - locinput < ln)
d6a28714 3171 sayNO;
24d3c4a9 3172 if (ln > 1 && memNE(s, locinput, ln))
d6a28714 3173 sayNO;
24d3c4a9 3174 locinput += ln;
d6a28714
JH
3175 nextchr = UCHARAT(locinput);
3176 break;
95b24440 3177 }
d6a28714 3178 case EXACTFL:
b8c5462f
JH
3179 PL_reg_flags |= RF_tainted;
3180 /* FALL THROUGH */
95b24440 3181 case EXACTF: {
be8e71aa 3182 char * const s = STRING(scan);
24d3c4a9 3183 ln = STR_LEN(scan);
d6a28714 3184
d07ddd77
JH
3185 if (do_utf8 || UTF) {
3186 /* Either target or the pattern are utf8. */
be8e71aa 3187 const char * const l = locinput;
d07ddd77 3188 char *e = PL_regeol;
bc517b45 3189
24d3c4a9 3190 if (ibcmp_utf8(s, 0, ln, (bool)UTF,
1feea2c7 3191 l, &e, 0, do_utf8)) {
5486206c
JH
3192 /* One more case for the sharp s:
3193 * pack("U0U*", 0xDF) =~ /ss/i,
3194 * the 0xC3 0x9F are the UTF-8
3195 * byte sequence for the U+00DF. */
3196 if (!(do_utf8 &&
3197 toLOWER(s[0]) == 's' &&
24d3c4a9 3198 ln >= 2 &&
5486206c
JH
3199 toLOWER(s[1]) == 's' &&
3200 (U8)l[0] == 0xC3 &&
3201 e - l >= 2 &&
3202 (U8)l[1] == 0x9F))
3203 sayNO;
3204 }
d07ddd77
JH
3205 locinput = e;
3206 nextchr = UCHARAT(locinput);
3207 break;
a0ed51b3 3208 }
d6a28714 3209
bc517b45
JH
3210 /* Neither the target and the pattern are utf8. */
3211
d6a28714
JH
3212 /* Inline the first character, for speed. */
3213 if (UCHARAT(s) != nextchr &&
3214 UCHARAT(s) != ((OP(scan) == EXACTF)
3215 ? PL_fold : PL_fold_locale)[nextchr])
a0ed51b3 3216 sayNO;
24d3c4a9 3217 if (PL_regeol - locinput < ln)
b8c5462f 3218 sayNO;
24d3c4a9
DM
3219 if (ln > 1 && (OP(scan) == EXACTF
3220 ? ibcmp(s, locinput, ln)
3221 : ibcmp_locale(s, locinput, ln)))
4633a7c4 3222 sayNO;
24d3c4a9 3223 locinput += ln;
d6a28714 3224 nextchr = UCHARAT(locinput);
a0d0e21e 3225 break;
95b24440 3226 }
d6a28714 3227 case ANYOF:
ffc61ed2 3228 if (do_utf8) {
9e55ce06
JH
3229 STRLEN inclasslen = PL_regeol - locinput;
3230
32fc9b6a 3231 if (!reginclass(rex, scan, (U8*)locinput, &inclasslen, do_utf8))
262b90c4 3232 goto anyof_fail;
ffc61ed2
JH
3233 if (locinput >= PL_regeol)
3234 sayNO;
0f0076b4 3235 locinput += inclasslen ? inclasslen : UTF8SKIP(locinput);
b8c5462f 3236 nextchr = UCHARAT(locinput);
e0f9d4a8 3237 break;
ffc61ed2
JH
3238 }
3239 else {
3240 if (nextchr < 0)
3241 nextchr = UCHARAT(locinput);
32fc9b6a 3242 if (!REGINCLASS(rex, scan, (U8*)locinput))
262b90c4 3243 goto anyof_fail;
ffc61ed2
JH
3244 if (!nextchr && locinput >= PL_regeol)
3245 sayNO;
3246 nextchr = UCHARAT(++locinput);
e0f9d4a8
JH
3247 break;
3248 }
262b90c4 3249 anyof_fail:
e0f9d4a8
JH
3250 /* If we might have the case of the German sharp s
3251 * in a casefolding Unicode character class. */
3252
ebc501f0
JH
3253 if (ANYOF_FOLD_SHARP_S(scan, locinput, PL_regeol)) {
3254 locinput += SHARP_S_SKIP;
e0f9d4a8 3255 nextchr = UCHARAT(locinput);
ffc61ed2 3256 }
e0f9d4a8
JH
3257 else
3258 sayNO;
b8c5462f 3259 break;
d6a28714 3260 case ALNUML:
b8c5462f
JH
3261 PL_reg_flags |= RF_tainted;
3262 /* FALL THROUGH */
d6a28714 3263 case ALNUM:
b8c5462f 3264 if (!nextchr)
4633a7c4 3265 sayNO;
ffc61ed2 3266 if (do_utf8) {
1a4fad37 3267 LOAD_UTF8_CHARCLASS_ALNUM();
ffc61ed2 3268 if (!(OP(scan) == ALNUM
bb7a0f54 3269 ? (bool)swash_fetch(PL_utf8_alnum, (U8*)locinput, do_utf8)
d6a28714 3270 : isALNUM_LC_utf8((U8*)locinput)))
b8c5462f
JH
3271 {
3272 sayNO;
a0ed51b3 3273 }
b8c5462f 3274 locinput += PL_utf8skip[nextchr];
a0ed51b3
LW
3275 nextchr = UCHARAT(locinput);
3276 break;
3277 }
ffc61ed2 3278 if (!(OP(scan) == ALNUM
d6a28714 3279 ? isALNUM(nextchr) : isALNUM_LC(nextchr)))
bbce6d69 3280 sayNO;
b8c5462f 3281 nextchr = UCHARAT(++locinput);
a0d0e21e 3282 break;
d6a28714 3283 case NALNUML:
b8c5462f
JH
3284 PL_reg_flags |= RF_tainted;
3285 /* FALL THROUGH */
d6a28714
JH
3286 case NALNUM:
3287 if (!nextchr && locinput >= PL_regeol)
a0ed51b3 3288 sayNO;
ffc61ed2 3289 if (do_utf8) {
1a4fad37 3290 LOAD_UTF8_CHARCLASS_ALNUM();
ffc61ed2 3291 if (OP(scan) == NALNUM
bb7a0f54 3292 ? (bool)swash_fetch(PL_utf8_alnum, (U8*)locinput, do_utf8)
d6a28714
JH
3293 : isALNUM_LC_utf8((U8*)locinput))
3294 {
b8c5462f 3295 sayNO;
d6a28714 3296 }
b8c5462f
JH
3297 locinput += PL_utf8skip[nextchr];
3298 nextchr = UCHARAT(locinput);
3299 break;
3300 }
ffc61ed2 3301 if (OP(scan) == NALNUM
d6a28714 3302 ? isALNUM(nextchr) : isALNUM_LC(nextchr))
b8c5462f 3303 sayNO;
76e3520e 3304 nextchr = UCHARAT(++locinput);
a0d0e21e 3305 break;
d6a28714
JH
3306 case BOUNDL:
3307 case NBOUNDL:
3280af22 3308 PL_reg_flags |= RF_tainted;
bbce6d69 3309 /* FALL THROUGH */
d6a28714
JH
3310 case BOUND:
3311 case NBOUND:
3312 /* was last char in word? */
ffc61ed2 3313 if (do_utf8) {
12d33761 3314 if (locinput == PL_bostr)
24d3c4a9 3315 ln = '\n';
ffc61ed2 3316 else {
a3b680e6 3317 const U8 * const r = reghop3((U8*)locinput, -1, (U8*)PL_bostr);
9041c2e3 3318
24d3c4a9 3319 ln = utf8n_to_uvchr(r, UTF8SKIP(r), 0, uniflags);
ffc61ed2
JH
3320 }
3321 if (OP(scan) == BOUND || OP(scan) == NBOUND) {
24d3c4a9 3322 ln = isALNUM_uni(ln);
1a4fad37 3323 LOAD_UTF8_CHARCLASS_ALNUM();
3568d838 3324 n = swash_fetch(PL_utf8_alnum, (U8*)locinput, do_utf8);
ffc61ed2
JH
3325 }
3326 else {
24d3c4a9 3327 ln = isALNUM_LC_uvchr(UNI_TO_NATIVE(ln));
ffc61ed2
JH
3328 n = isALNUM_LC_utf8((U8*)locinput);
3329 }
a0ed51b3 3330 }
d6a28714 3331 else {
24d3c4a9 3332 ln = (locinput != PL_bostr) ?
12d33761 3333 UCHARAT(locinput - 1) : '\n';
ffc61ed2 3334 if (OP(scan) == BOUND || OP(scan) == NBOUND) {
24d3c4a9 3335 ln = isALNUM(ln);
ffc61ed2
JH
3336 n = isALNUM(nextchr);
3337 }
3338 else {
24d3c4a9 3339 ln = isALNUM_LC(ln);
ffc61ed2
JH
3340 n = isALNUM_LC(nextchr);
3341 }
d6a28714 3342 }
24d3c4a9 3343 if (((!ln) == (!n)) == (OP(scan) == BOUND ||
ffc61ed2
JH
3344 OP(scan) == BOUNDL))
3345 sayNO;
a0ed51b3 3346 break;
d6a28714 3347 case SPACEL:
3280af22 3348 PL_reg_flags |= RF_tainted;
bbce6d69 3349 /* FALL THROUGH */
d6a28714 3350 case SPACE:
9442cb0e 3351 if (!nextchr)
4633a7c4 3352 sayNO;
1aa99e6b 3353 if (do_utf8) {
fd400ab9 3354 if (UTF8_IS_CONTINUED(nextchr)) {
1a4fad37 3355 LOAD_UTF8_CHARCLASS_SPACE();
ffc61ed2 3356 if (!(OP(scan) == SPACE
bb7a0f54 3357 ? (bool)swash_fetch(PL_utf8_space, (U8*)locinput, do_utf8)
ffc61ed2
JH
3358 : isSPACE_LC_utf8((U8*)locinput)))
3359 {
3360 sayNO;
3361 }
3362 locinput += PL_utf8skip[nextchr];
3363 nextchr = UCHARAT(locinput);
3364 break;
d6a28714 3365 }
ffc61ed2
JH
3366 if (!(OP(scan) == SPACE
3367 ? isSPACE(nextchr) : isSPACE_LC(nextchr)))
3368 sayNO;
3369 nextchr = UCHARAT(++locinput);
3370 }
3371 else {
3372 if (!(OP(scan) == SPACE
3373 ? isSPACE(nextchr) : isSPACE_LC(nextchr)))
3374 sayNO;
3375 nextchr = UCHARAT(++locinput);
a0ed51b3 3376 }
a0ed51b3 3377 break;
d6a28714 3378 case NSPACEL:
3280af22 3379 PL_reg_flags |= RF_tainted;
bbce6d69 3380 /* FALL THROUGH */
d6a28714 3381 case NSPACE:
9442cb0e 3382 if (!nextchr && locinput >= PL_regeol)
b8c5462f 3383 sayNO;
1aa99e6b 3384 if (do_utf8) {
1a4fad37 3385 LOAD_UTF8_CHARCLASS_SPACE();
ffc61ed2 3386 if (OP(scan) == NSPACE
bb7a0f54 3387 ? (bool)swash_fetch(PL_utf8_space, (U8*)locinput, do_utf8)
d6a28714 3388 : isSPACE_LC_utf8((U8*)locinput))
b8c5462f
JH
3389 {
3390 sayNO;
3391