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