This is a live mirror of the Perl 5 development currently hosted at https://github.com/perl/perl5
Add Regexp::Keep \K functionality to regex engine as well as add \v and \V, cleanup...
[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 */
e2d8ce26
JP
125#define JUMPABLE(rn) ( \
126 OP(rn) == OPEN || OP(rn) == CLOSE || OP(rn) == EVAL || \
cca55fe3
JP
127 OP(rn) == SUSPEND || OP(rn) == IFMATCH || \
128 OP(rn) == PLUS || OP(rn) == MINMOD || \
ee9b8eae 129 OP(rn) == KEEPS || (PL_regkind[OP(rn)] == VERB) || \
3dab1dad 130 (PL_regkind[OP(rn)] == CURLY && ARG1(rn) > 0) \
e2d8ce26 131)
ee9b8eae 132#define IS_EXACT(rn) (PL_regkind[OP(rn)] == EXACT)
e2d8ce26 133
ee9b8eae
YO
134#define HAS_TEXT(rn) ( IS_EXACT(rn) || PL_regkind[OP(rn)] == REF )
135
136#if 0
137/* Currently these are only used when PL_regkind[OP(rn)] == EXACT so
138 we don't need this definition. */
139#define IS_TEXT(rn) ( OP(rn)==EXACT || OP(rn)==REF || OP(rn)==NREF )
140#define IS_TEXTF(rn) ( OP(rn)==EXACTF || OP(rn)==REFF || OP(rn)==NREFF )
141#define IS_TEXTFL(rn) ( OP(rn)==EXACTFL || OP(rn)==REFFL || OP(rn)==NREFFL )
142
143#else
144/* ... so we use this as its faster. */
145#define IS_TEXT(rn) ( OP(rn)==EXACT )
146#define IS_TEXTF(rn) ( OP(rn)==EXACTF )
147#define IS_TEXTFL(rn) ( OP(rn)==EXACTFL )
148
149#endif
e2d8ce26 150
a84d97b6
HS
151/*
152 Search for mandatory following text node; for lookahead, the text must
153 follow but for lookbehind (rn->flags != 0) we skip to the next step.
154*/
cca55fe3 155#define FIND_NEXT_IMPT(rn) STMT_START { \
3dab1dad
YO
156 while (JUMPABLE(rn)) { \
157 const OPCODE type = OP(rn); \
158 if (type == SUSPEND || PL_regkind[type] == CURLY) \
e2d8ce26 159 rn = NEXTOPER(NEXTOPER(rn)); \
3dab1dad 160 else if (type == PLUS) \
cca55fe3 161 rn = NEXTOPER(rn); \
3dab1dad 162 else if (type == IFMATCH) \
a84d97b6 163 rn = (rn->flags == 0) ? NEXTOPER(NEXTOPER(rn)) : rn + ARG(rn); \
e2d8ce26 164 else rn += NEXT_OFF(rn); \
3dab1dad 165 } \
5f80c4cf 166} STMT_END
74750237 167
c476f425 168
acfe0abc 169static void restore_pos(pTHX_ void *arg);
51371543 170
76e3520e 171STATIC CHECKPOINT
cea2e8a9 172S_regcppush(pTHX_ I32 parenfloor)
a0d0e21e 173{
97aff369 174 dVAR;
a3b680e6 175 const int retval = PL_savestack_ix;
b1ce53c5 176#define REGCP_PAREN_ELEMS 4
a3b680e6 177 const int paren_elems_to_push = (PL_regsize - parenfloor) * REGCP_PAREN_ELEMS;
a0d0e21e 178 int p;
40a82448 179 GET_RE_DEBUG_FLAGS_DECL;
a0d0e21e 180
e49a9654
IH
181 if (paren_elems_to_push < 0)
182 Perl_croak(aTHX_ "panic: paren_elems_to_push < 0");
183
6bda09f9 184#define REGCP_OTHER_ELEMS 8
4b3c1a47 185 SSGROW(paren_elems_to_push + REGCP_OTHER_ELEMS);
7f69552c 186
3280af22 187 for (p = PL_regsize; p > parenfloor; p--) {
b1ce53c5 188/* REGCP_PARENS_ELEMS are pushed per pairs of parentheses. */
cf93c79d
IZ
189 SSPUSHINT(PL_regendp[p]);
190 SSPUSHINT(PL_regstartp[p]);
3280af22 191 SSPUSHPTR(PL_reg_start_tmp[p]);
a0d0e21e 192 SSPUSHINT(p);
40a82448
DM
193 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
194 " saving \\%"UVuf" %"IVdf"(%"IVdf")..%"IVdf"\n",
195 (UV)p, (IV)PL_regstartp[p],
196 (IV)(PL_reg_start_tmp[p] - PL_bostr),
197 (IV)PL_regendp[p]
198 ));
a0d0e21e 199 }
b1ce53c5 200/* REGCP_OTHER_ELEMS are pushed in any case, parentheses or no. */
6bda09f9
YO
201 SSPUSHPTR(PL_regstartp);
202 SSPUSHPTR(PL_regendp);
3280af22
NIS
203 SSPUSHINT(PL_regsize);
204 SSPUSHINT(*PL_reglastparen);
a01268b5 205 SSPUSHINT(*PL_reglastcloseparen);
3280af22 206 SSPUSHPTR(PL_reginput);
41123dfd
JH
207#define REGCP_FRAME_ELEMS 2
208/* REGCP_FRAME_ELEMS are part of the REGCP_OTHER_ELEMS and
209 * are needed for the regexp context stack bookkeeping. */
210 SSPUSHINT(paren_elems_to_push + REGCP_OTHER_ELEMS - REGCP_FRAME_ELEMS);
b1ce53c5 211 SSPUSHINT(SAVEt_REGCONTEXT); /* Magic cookie. */
41123dfd 212
a0d0e21e
LW
213 return retval;
214}
215
c277df42 216/* These are needed since we do not localize EVAL nodes: */
ab3bbdeb
YO
217#define REGCP_SET(cp) \
218 DEBUG_STATE_r( \
ab3bbdeb 219 PerlIO_printf(Perl_debug_log, \
e4f74956 220 " Setting an EVAL scope, savestack=%"IVdf"\n", \
ab3bbdeb
YO
221 (IV)PL_savestack_ix)); \
222 cp = PL_savestack_ix
c3464db5 223
ab3bbdeb 224#define REGCP_UNWIND(cp) \
e4f74956 225 DEBUG_STATE_r( \
ab3bbdeb 226 if (cp != PL_savestack_ix) \
e4f74956
YO
227 PerlIO_printf(Perl_debug_log, \
228 " Clearing an EVAL scope, savestack=%"IVdf"..%"IVdf"\n", \
ab3bbdeb
YO
229 (IV)(cp), (IV)PL_savestack_ix)); \
230 regcpblow(cp)
c277df42 231
76e3520e 232STATIC char *
097eb12c 233S_regcppop(pTHX_ const regexp *rex)
a0d0e21e 234{
97aff369 235 dVAR;
3b6647e0 236 U32 i;
a0d0e21e 237 char *input;
b1ce53c5 238
a3621e74
YO
239 GET_RE_DEBUG_FLAGS_DECL;
240
b1ce53c5 241 /* Pop REGCP_OTHER_ELEMS before the parentheses loop starts. */
a0d0e21e 242 i = SSPOPINT;
b1ce53c5
JH
243 assert(i == SAVEt_REGCONTEXT); /* Check that the magic cookie is there. */
244 i = SSPOPINT; /* Parentheses elements to pop. */
a0d0e21e 245 input = (char *) SSPOPPTR;
a01268b5 246 *PL_reglastcloseparen = SSPOPINT;
3280af22
NIS
247 *PL_reglastparen = SSPOPINT;
248 PL_regsize = SSPOPINT;
6bda09f9
YO
249 PL_regendp=(I32 *) SSPOPPTR;
250 PL_regstartp=(I32 *) SSPOPPTR;
b1ce53c5 251
6bda09f9 252
b1ce53c5 253 /* Now restore the parentheses context. */
41123dfd
JH
254 for (i -= (REGCP_OTHER_ELEMS - REGCP_FRAME_ELEMS);
255 i > 0; i -= REGCP_PAREN_ELEMS) {
1df70142 256 I32 tmps;
097eb12c 257 U32 paren = (U32)SSPOPINT;
3280af22 258 PL_reg_start_tmp[paren] = (char *) SSPOPPTR;
cf93c79d
IZ
259 PL_regstartp[paren] = SSPOPINT;
260 tmps = SSPOPINT;
3280af22
NIS
261 if (paren <= *PL_reglastparen)
262 PL_regendp[paren] = tmps;
a3621e74 263 DEBUG_EXECUTE_r(
c3464db5 264 PerlIO_printf(Perl_debug_log,
b900a521 265 " restoring \\%"UVuf" to %"IVdf"(%"IVdf")..%"IVdf"%s\n",
9041c2e3 266 (UV)paren, (IV)PL_regstartp[paren],
b900a521 267 (IV)(PL_reg_start_tmp[paren] - PL_bostr),
9041c2e3 268 (IV)PL_regendp[paren],
3280af22 269 (paren > *PL_reglastparen ? "(no)" : ""));
c277df42 270 );
a0d0e21e 271 }
a3621e74 272 DEBUG_EXECUTE_r(
bb7a0f54 273 if (*PL_reglastparen + 1 <= rex->nparens) {
c3464db5 274 PerlIO_printf(Perl_debug_log,
faccc32b 275 " restoring \\%"IVdf"..\\%"IVdf" to undef\n",
4f639d21 276 (IV)(*PL_reglastparen + 1), (IV)rex->nparens);
c277df42
IZ
277 }
278 );
daf18116 279#if 1
dafc8851
JH
280 /* It would seem that the similar code in regtry()
281 * already takes care of this, and in fact it is in
282 * a better location to since this code can #if 0-ed out
283 * but the code in regtry() is needed or otherwise tests
284 * requiring null fields (pat.t#187 and split.t#{13,14}
daf18116
JH
285 * (as of patchlevel 7877) will fail. Then again,
286 * this code seems to be necessary or otherwise
287 * building DynaLoader will fail:
288 * "Error: '*' not in typemap in DynaLoader.xs, line 164"
289 * --jhi */
3b6647e0 290 for (i = *PL_reglastparen + 1; i <= rex->nparens; i++) {
097eb12c
AL
291 if (i > PL_regsize)
292 PL_regstartp[i] = -1;
293 PL_regendp[i] = -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
864dbfa3 310Perl_pregexec(pTHX_ register regexp *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
JH
373char *
374Perl_re_intuit_start(pTHX_ regexp *prog, SV *sv, char *strpos,
375 char *strend, U32 flags, re_scream_pos_data *data)
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
2c2d71f5 501#ifdef DEBUGGING /* 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
1112#define REXEC_FBC_CSCAN_PRELOAD(UtFpReLoAd,CoNdUtF8,CoNd) \
1113 if (do_utf8) { \
1114 UtFpReLoAd; \
1115 REXEC_FBC_UTF8_CLASS_SCAN(CoNdUtF8); \
1116 } \
1117 else { \
1118 REXEC_FBC_CLASS_SCAN(CoNd); \
1119 } \
1120 break
1121
1122#define REXEC_FBC_CSCAN_TAINT(CoNdUtF8,CoNd) \
1123 PL_reg_flags |= RF_tainted; \
1124 if (do_utf8) { \
1125 REXEC_FBC_UTF8_CLASS_SCAN(CoNdUtF8); \
1126 } \
1127 else { \
1128 REXEC_FBC_CLASS_SCAN(CoNd); \
1129 } \
1130 break
1131
786e8c11
YO
1132#define DUMP_EXEC_POS(li,s,doutf8) \
1133 dump_exec_pos(li,s,(PL_regeol),(PL_bostr),(PL_reg_starttry),doutf8)
1134
1135/* We know what class REx starts with. Try to find this position... */
1136/* if reginfo is NULL, its a dryrun */
1137/* annoyingly all the vars in this routine have different names from their counterparts
1138 in regmatch. /grrr */
1139
3c3eec57 1140STATIC char *
07be1b83 1141S_find_byclass(pTHX_ regexp * prog, const regnode *c, char *s,
24b23f37 1142 const char *strend, regmatch_info *reginfo)
a687059c 1143{
27da23d5 1144 dVAR;
bbe252da 1145 const I32 doevery = (prog->intflags & PREGf_SKIP) == 0;
6eb5f6b9 1146 char *m;
d8093b23 1147 STRLEN ln;
5dab1207 1148 STRLEN lnc;
078c425b 1149 register STRLEN uskip;
d8093b23 1150 unsigned int c1;
1151 unsigned int c2;
6eb5f6b9
JH
1152 char *e;
1153 register I32 tmp = 1; /* Scratch variable? */
a3b680e6 1154 register const bool do_utf8 = PL_reg_match_utf8;
f8fc2ecf
YO
1155 RXi_GET_DECL(prog,progi);
1156
6eb5f6b9
JH
1157 /* We know what class it must start with. */
1158 switch (OP(c)) {
6eb5f6b9 1159 case ANYOF:
388cc4de 1160 if (do_utf8) {
4cadc6a9 1161 REXEC_FBC_UTF8_CLASS_SCAN((ANYOF_FLAGS(c) & ANYOF_UNICODE) ||
388cc4de 1162 !UTF8_IS_INVARIANT((U8)s[0]) ?
32fc9b6a 1163 reginclass(prog, c, (U8*)s, 0, do_utf8) :
4cadc6a9 1164 REGINCLASS(prog, c, (U8*)s));
388cc4de
HS
1165 }
1166 else {
1167 while (s < strend) {
1168 STRLEN skip = 1;
1169
32fc9b6a 1170 if (REGINCLASS(prog, c, (U8*)s) ||
388cc4de
HS
1171 (ANYOF_FOLD_SHARP_S(c, s, strend) &&
1172 /* The assignment of 2 is intentional:
1173 * for the folded sharp s, the skip is 2. */
1174 (skip = SHARP_S_SKIP))) {
24b23f37 1175 if (tmp && (!reginfo || regtry(reginfo, &s)))
388cc4de
HS
1176 goto got_it;
1177 else
1178 tmp = doevery;
1179 }
1180 else
1181 tmp = 1;
1182 s += skip;
1183 }
a0d0e21e 1184 }
6eb5f6b9 1185 break;
f33976b4 1186 case CANY:
4cadc6a9 1187 REXEC_FBC_SCAN(
24b23f37 1188 if (tmp && (!reginfo || regtry(reginfo, &s)))
f33976b4
DB
1189 goto got_it;
1190 else
1191 tmp = doevery;
4cadc6a9 1192 );
f33976b4 1193 break;
6eb5f6b9 1194 case EXACTF:
5dab1207
NIS
1195 m = STRING(c);
1196 ln = STR_LEN(c); /* length to match in octets/bytes */
1197 lnc = (I32) ln; /* length to match in characters */
1aa99e6b 1198 if (UTF) {
a2a2844f 1199 STRLEN ulen1, ulen2;
5dab1207 1200 U8 *sm = (U8 *) m;
89ebb4a3
JH
1201 U8 tmpbuf1[UTF8_MAXBYTES_CASE+1];
1202 U8 tmpbuf2[UTF8_MAXBYTES_CASE+1];
4ad0818d 1203 const U32 uniflags = UTF8_ALLOW_DEFAULT;
a2a2844f
JH
1204
1205 to_utf8_lower((U8*)m, tmpbuf1, &ulen1);
1206 to_utf8_upper((U8*)m, tmpbuf2, &ulen2);
1207
89ebb4a3 1208 c1 = utf8n_to_uvchr(tmpbuf1, UTF8_MAXBYTES_CASE,
041457d9 1209 0, uniflags);
89ebb4a3 1210 c2 = utf8n_to_uvchr(tmpbuf2, UTF8_MAXBYTES_CASE,
041457d9 1211 0, uniflags);
5dab1207
NIS
1212 lnc = 0;
1213 while (sm < ((U8 *) m + ln)) {
1214 lnc++;
1215 sm += UTF8SKIP(sm);
1216 }
1aa99e6b
IH
1217 }
1218 else {
1219 c1 = *(U8*)m;
1220 c2 = PL_fold[c1];
1221 }
6eb5f6b9
JH
1222 goto do_exactf;
1223 case EXACTFL:
5dab1207
NIS
1224 m = STRING(c);
1225 ln = STR_LEN(c);
1226 lnc = (I32) ln;
d8093b23 1227 c1 = *(U8*)m;
6eb5f6b9
JH
1228 c2 = PL_fold_locale[c1];
1229 do_exactf:
db12adc6 1230 e = HOP3c(strend, -((I32)lnc), s);
b3c9acc1 1231
3b0527fe 1232 if (!reginfo && e < s)
6eb5f6b9 1233 e = s; /* Due to minlen logic of intuit() */
1aa99e6b 1234
60a8b682
JH
1235 /* The idea in the EXACTF* cases is to first find the
1236 * first character of the EXACTF* node and then, if
1237 * necessary, case-insensitively compare the full
1238 * text of the node. The c1 and c2 are the first
1239 * characters (though in Unicode it gets a bit
1240 * more complicated because there are more cases
7f16dd3d
JH
1241 * than just upper and lower: one needs to use
1242 * the so-called folding case for case-insensitive
1243 * matching (called "loose matching" in Unicode).
1244 * ibcmp_utf8() will do just that. */
60a8b682 1245
1aa99e6b 1246 if (do_utf8) {
575cac57 1247 UV c, f;
89ebb4a3 1248 U8 tmpbuf [UTF8_MAXBYTES+1];
575cac57 1249 STRLEN len, foldlen;
4ad0818d 1250 const U32 uniflags = UTF8_ALLOW_DEFAULT;
09091399 1251 if (c1 == c2) {
5dab1207
NIS
1252 /* Upper and lower of 1st char are equal -
1253 * probably not a "letter". */
1aa99e6b 1254 while (s <= e) {
89ebb4a3 1255 c = utf8n_to_uvchr((U8*)s, UTF8_MAXBYTES, &len,
041457d9 1256 uniflags);
4cadc6a9 1257 REXEC_FBC_EXACTISH_CHECK(c == c1);
1aa99e6b 1258 }
09091399
JH
1259 }
1260 else {
1aa99e6b 1261 while (s <= e) {
89ebb4a3 1262 c = utf8n_to_uvchr((U8*)s, UTF8_MAXBYTES, &len,
041457d9 1263 uniflags);
80aecb99 1264
60a8b682 1265 /* Handle some of the three Greek sigmas cases.
8c01da3c
JH
1266 * Note that not all the possible combinations
1267 * are handled here: some of them are handled
1268 * by the standard folding rules, and some of
1269 * them (the character class or ANYOF cases)
1270 * are handled during compiletime in
1271 * regexec.c:S_regclass(). */
880bd946
JH
1272 if (c == (UV)UNICODE_GREEK_CAPITAL_LETTER_SIGMA ||
1273 c == (UV)UNICODE_GREEK_SMALL_LETTER_FINAL_SIGMA)
1274 c = (UV)UNICODE_GREEK_SMALL_LETTER_SIGMA;
80aecb99 1275
4cadc6a9 1276 REXEC_FBC_EXACTISH_CHECK(c == c1 || c == c2);
1aa99e6b 1277 }
09091399 1278 }
1aa99e6b
IH
1279 }
1280 else {
1281 if (c1 == c2)
4cadc6a9 1282 REXEC_FBC_EXACTISH_SCAN(*(U8*)s == c1);
1aa99e6b 1283 else
4cadc6a9 1284 REXEC_FBC_EXACTISH_SCAN(*(U8*)s == c1 || *(U8*)s == c2);
b3c9acc1
IZ
1285 }
1286 break;
bbce6d69 1287 case BOUNDL:
3280af22 1288 PL_reg_flags |= RF_tainted;
bbce6d69 1289 /* FALL THROUGH */
a0d0e21e 1290 case BOUND:
ffc61ed2 1291 if (do_utf8) {
12d33761 1292 if (s == PL_bostr)
ffc61ed2
JH
1293 tmp = '\n';
1294 else {
6136c704 1295 U8 * const r = reghop3((U8*)s, -1, (U8*)PL_bostr);
4ad0818d 1296 tmp = utf8n_to_uvchr(r, UTF8SKIP(r), 0, UTF8_ALLOW_DEFAULT);
ffc61ed2
JH
1297 }
1298 tmp = ((OP(c) == BOUND ?
9041c2e3 1299 isALNUM_uni(tmp) : isALNUM_LC_uvchr(UNI_TO_NATIVE(tmp))) != 0);
1a4fad37 1300 LOAD_UTF8_CHARCLASS_ALNUM();
4cadc6a9 1301 REXEC_FBC_UTF8_SCAN(
ffc61ed2 1302 if (tmp == !(OP(c) == BOUND ?
bb7a0f54 1303 (bool)swash_fetch(PL_utf8_alnum, (U8*)s, do_utf8) :
ffc61ed2
JH
1304 isALNUM_LC_utf8((U8*)s)))
1305 {
1306 tmp = !tmp;
4cadc6a9 1307 REXEC_FBC_TRYIT;
a687059c 1308 }
4cadc6a9 1309 );
a0d0e21e 1310 }
667bb95a 1311 else {
12d33761 1312 tmp = (s != PL_bostr) ? UCHARAT(s - 1) : '\n';
ffc61ed2 1313 tmp = ((OP(c) == BOUND ? isALNUM(tmp) : isALNUM_LC(tmp)) != 0);
4cadc6a9 1314 REXEC_FBC_SCAN(
ffc61ed2
JH
1315 if (tmp ==
1316 !(OP(c) == BOUND ? isALNUM(*s) : isALNUM_LC(*s))) {
1317 tmp = !tmp;
4cadc6a9 1318 REXEC_FBC_TRYIT;
a0ed51b3 1319 }
4cadc6a9 1320 );
a0ed51b3 1321 }
24b23f37 1322 if ((!prog->minlen && tmp) && (!reginfo || regtry(reginfo, &s)))
a0ed51b3
LW
1323 goto got_it;
1324 break;
bbce6d69 1325 case NBOUNDL:
3280af22 1326 PL_reg_flags |= RF_tainted;
bbce6d69 1327 /* FALL THROUGH */
a0d0e21e 1328 case NBOUND:
ffc61ed2 1329 if (do_utf8) {
12d33761 1330 if (s == PL_bostr)
ffc61ed2
JH
1331 tmp = '\n';
1332 else {
6136c704 1333 U8 * const r = reghop3((U8*)s, -1, (U8*)PL_bostr);
4ad0818d 1334 tmp = utf8n_to_uvchr(r, UTF8SKIP(r), 0, UTF8_ALLOW_DEFAULT);
ffc61ed2
JH
1335 }
1336 tmp = ((OP(c) == NBOUND ?
9041c2e3 1337 isALNUM_uni(tmp) : isALNUM_LC_uvchr(UNI_TO_NATIVE(tmp))) != 0);
1a4fad37 1338 LOAD_UTF8_CHARCLASS_ALNUM();
4cadc6a9 1339 REXEC_FBC_UTF8_SCAN(
ffc61ed2 1340 if (tmp == !(OP(c) == NBOUND ?
bb7a0f54 1341 (bool)swash_fetch(PL_utf8_alnum, (U8*)s, do_utf8) :
ffc61ed2
JH
1342 isALNUM_LC_utf8((U8*)s)))
1343 tmp = !tmp;
4cadc6a9
YO
1344 else REXEC_FBC_TRYIT;
1345 );
a0d0e21e 1346 }
667bb95a 1347 else {
12d33761 1348 tmp = (s != PL_bostr) ? UCHARAT(s - 1) : '\n';
ffc61ed2
JH
1349 tmp = ((OP(c) == NBOUND ?
1350 isALNUM(tmp) : isALNUM_LC(tmp)) != 0);
4cadc6a9 1351 REXEC_FBC_SCAN(
ffc61ed2
JH
1352 if (tmp ==
1353 !(OP(c) == NBOUND ? isALNUM(*s) : isALNUM_LC(*s)))
1354 tmp = !tmp;
4cadc6a9
YO
1355 else REXEC_FBC_TRYIT;
1356 );
a0ed51b3 1357 }
24b23f37 1358 if ((!prog->minlen && !tmp) && (!reginfo || regtry(reginfo, &s)))
a0ed51b3
LW
1359 goto got_it;
1360 break;
a0d0e21e 1361 case ALNUM:
4cadc6a9
YO
1362 REXEC_FBC_CSCAN_PRELOAD(
1363 LOAD_UTF8_CHARCLASS_ALNUM(),
1364 swash_fetch(PL_utf8_alnum, (U8*)s, do_utf8),
1365 isALNUM(*s)
1366 );
bbce6d69 1367 case ALNUML:
4cadc6a9
YO
1368 REXEC_FBC_CSCAN_TAINT(
1369 isALNUM_LC_utf8((U8*)s),
1370 isALNUM_LC(*s)
1371 );
a0d0e21e 1372 case NALNUM:
4cadc6a9
YO
1373 REXEC_FBC_CSCAN_PRELOAD(
1374 LOAD_UTF8_CHARCLASS_ALNUM(),
1375 !swash_fetch(PL_utf8_alnum, (U8*)s, do_utf8),
1376 !isALNUM(*s)
1377 );
bbce6d69 1378 case NALNUML:
4cadc6a9
YO
1379 REXEC_FBC_CSCAN_TAINT(
1380 !isALNUM_LC_utf8((U8*)s),
1381 !isALNUM_LC(*s)
1382 );
a0d0e21e 1383 case SPACE:
4cadc6a9
YO
1384 REXEC_FBC_CSCAN_PRELOAD(
1385 LOAD_UTF8_CHARCLASS_SPACE(),
1386 *s == ' ' || swash_fetch(PL_utf8_space,(U8*)s, do_utf8),
1387 isSPACE(*s)
1388 );
bbce6d69 1389 case SPACEL:
4cadc6a9
YO
1390 REXEC_FBC_CSCAN_TAINT(
1391 *s == ' ' || isSPACE_LC_utf8((U8*)s),
1392 isSPACE_LC(*s)
1393 );
a0d0e21e 1394 case NSPACE:
4cadc6a9
YO
1395 REXEC_FBC_CSCAN_PRELOAD(
1396 LOAD_UTF8_CHARCLASS_SPACE(),
1397 !(*s == ' ' || swash_fetch(PL_utf8_space,(U8*)s, do_utf8)),
1398 !isSPACE(*s)
1399 );
bbce6d69 1400 case NSPACEL:
4cadc6a9
YO
1401 REXEC_FBC_CSCAN_TAINT(
1402 !(*s == ' ' || isSPACE_LC_utf8((U8*)s)),
1403 !isSPACE_LC(*s)
1404 );
a0d0e21e 1405 case DIGIT:
4cadc6a9
YO
1406 REXEC_FBC_CSCAN_PRELOAD(
1407 LOAD_UTF8_CHARCLASS_DIGIT(),
1408 swash_fetch(PL_utf8_digit,(U8*)s, do_utf8),
1409 isDIGIT(*s)
1410 );
b8c5462f 1411 case DIGITL:
4cadc6a9
YO
1412 REXEC_FBC_CSCAN_TAINT(
1413 isDIGIT_LC_utf8((U8*)s),
1414 isDIGIT_LC(*s)
1415 );
a0d0e21e 1416 case NDIGIT:
4cadc6a9
YO
1417 REXEC_FBC_CSCAN_PRELOAD(
1418 LOAD_UTF8_CHARCLASS_DIGIT(),
1419 !swash_fetch(PL_utf8_digit,(U8*)s, do_utf8),
1420 !isDIGIT(*s)
1421 );
b8c5462f 1422 case NDIGITL:
4cadc6a9
YO
1423 REXEC_FBC_CSCAN_TAINT(
1424 !isDIGIT_LC_utf8((U8*)s),
1425 !isDIGIT_LC(*s)
1426 );
1de06328
YO
1427 case AHOCORASICKC:
1428 case AHOCORASICK:
07be1b83
YO
1429 {
1430 const enum { trie_plain, trie_utf8, trie_utf8_fold }
1431 trie_type = do_utf8 ?
1432 (c->flags == EXACT ? trie_utf8 : trie_utf8_fold)
1433 : trie_plain;
1434 /* what trie are we using right now */
1435 reg_ac_data *aho
f8fc2ecf 1436 = (reg_ac_data*)progi->data->data[ ARG( c ) ];
3251b653
NC
1437 reg_trie_data *trie
1438 = (reg_trie_data*)progi->data->data[ aho->trie ];
55eed653 1439 HV *widecharmap = (HV*) progi->data->data[ aho->trie + 1 ];
07be1b83
YO
1440
1441 const char *last_start = strend - trie->minlen;
6148ee25 1442#ifdef DEBUGGING
07be1b83 1443 const char *real_start = s;
6148ee25 1444#endif
07be1b83 1445 STRLEN maxlen = trie->maxlen;
be8e71aa
YO
1446 SV *sv_points;
1447 U8 **points; /* map of where we were in the input string
786e8c11 1448 when reading a given char. For ASCII this
be8e71aa
YO
1449 is unnecessary overhead as the relationship
1450 is always 1:1, but for unicode, especially
1451 case folded unicode this is not true. */
f9e705e8 1452 U8 foldbuf[ UTF8_MAXBYTES_CASE + 1 ];
786e8c11
YO
1453 U8 *bitmap=NULL;
1454
07be1b83
YO
1455
1456 GET_RE_DEBUG_FLAGS_DECL;
1457
be8e71aa
YO
1458 /* We can't just allocate points here. We need to wrap it in
1459 * an SV so it gets freed properly if there is a croak while
1460 * running the match */
1461 ENTER;
1462 SAVETMPS;
1463 sv_points=newSV(maxlen * sizeof(U8 *));
1464 SvCUR_set(sv_points,
1465 maxlen * sizeof(U8 *));
1466 SvPOK_on(sv_points);
1467 sv_2mortal(sv_points);
1468 points=(U8**)SvPV_nolen(sv_points );
1de06328
YO
1469 if ( trie_type != trie_utf8_fold
1470 && (trie->bitmap || OP(c)==AHOCORASICKC) )
1471 {
786e8c11
YO
1472 if (trie->bitmap)
1473 bitmap=(U8*)trie->bitmap;
1474 else
1475 bitmap=(U8*)ANYOF_BITMAP(c);
07be1b83 1476 }
786e8c11
YO
1477 /* this is the Aho-Corasick algorithm modified a touch
1478 to include special handling for long "unknown char"
1479 sequences. The basic idea being that we use AC as long
1480 as we are dealing with a possible matching char, when
1481 we encounter an unknown char (and we have not encountered
1482 an accepting state) we scan forward until we find a legal
1483 starting char.
1484 AC matching is basically that of trie matching, except
1485 that when we encounter a failing transition, we fall back
1486 to the current states "fail state", and try the current char
1487 again, a process we repeat until we reach the root state,
1488 state 1, or a legal transition. If we fail on the root state
1489 then we can either terminate if we have reached an accepting
1490 state previously, or restart the entire process from the beginning
1491 if we have not.
1492
1493 */
07be1b83
YO
1494 while (s <= last_start) {
1495 const U32 uniflags = UTF8_ALLOW_DEFAULT;
1496 U8 *uc = (U8*)s;
1497 U16 charid = 0;
1498 U32 base = 1;
1499 U32 state = 1;
1500 UV uvc = 0;
1501 STRLEN len = 0;
1502 STRLEN foldlen = 0;
1503 U8 *uscan = (U8*)NULL;
1504 U8 *leftmost = NULL;
786e8c11
YO
1505#ifdef DEBUGGING
1506 U32 accepted_word= 0;
1507#endif
07be1b83
YO
1508 U32 pointpos = 0;
1509
1510 while ( state && uc <= (U8*)strend ) {
1511 int failed=0;
786e8c11
YO
1512 U32 word = aho->states[ state ].wordnum;
1513
1de06328
YO
1514 if( state==1 ) {
1515 if ( bitmap ) {
1516 DEBUG_TRIE_EXECUTE_r(
1517 if ( uc <= (U8*)last_start && !BITMAP_TEST(bitmap,*uc) ) {
1518 dump_exec_pos( (char *)uc, c, strend, real_start,
1519 (char *)uc, do_utf8 );
1520 PerlIO_printf( Perl_debug_log,
1521 " Scanning for legal start char...\n");
1522 }
1523 );
1524 while ( uc <= (U8*)last_start && !BITMAP_TEST(bitmap,*uc) ) {
1525 uc++;
786e8c11 1526 }
1de06328 1527 s= (char *)uc;
786e8c11 1528 }
786e8c11
YO
1529 if (uc >(U8*)last_start) break;
1530 }
1531
1532 if ( word ) {
1533 U8 *lpos= points[ (pointpos - trie->wordlen[word-1] ) % maxlen ];
1534 if (!leftmost || lpos < leftmost) {
1535 DEBUG_r(accepted_word=word);
07be1b83 1536 leftmost= lpos;
786e8c11 1537 }
07be1b83 1538 if (base==0) break;
786e8c11 1539
07be1b83
YO
1540 }
1541 points[pointpos++ % maxlen]= uc;
55eed653
NC
1542 REXEC_TRIE_READ_CHAR(trie_type, trie, widecharmap, uc,
1543 uscan, len, uvc, charid, foldlen,
1544 foldbuf, uniflags);
786e8c11
YO
1545 DEBUG_TRIE_EXECUTE_r({
1546 dump_exec_pos( (char *)uc, c, strend, real_start,
1547 s, do_utf8 );
07be1b83 1548 PerlIO_printf(Perl_debug_log,
786e8c11
YO
1549 " Charid:%3u CP:%4"UVxf" ",
1550 charid, uvc);
1551 });
07be1b83
YO
1552
1553 do {
6148ee25 1554#ifdef DEBUGGING
786e8c11 1555 word = aho->states[ state ].wordnum;
6148ee25 1556#endif
07be1b83
YO
1557 base = aho->states[ state ].trans.base;
1558
786e8c11
YO
1559 DEBUG_TRIE_EXECUTE_r({
1560 if (failed)
1561 dump_exec_pos( (char *)uc, c, strend, real_start,
1562 s, do_utf8 );
07be1b83 1563 PerlIO_printf( Perl_debug_log,
786e8c11
YO
1564 "%sState: %4"UVxf", word=%"UVxf,
1565 failed ? " Fail transition to " : "",
1566 (UV)state, (UV)word);
1567 });
07be1b83
YO
1568 if ( base ) {
1569 U32 tmp;
1570 if (charid &&
1571 (base + charid > trie->uniquecharcount )
1572 && (base + charid - 1 - trie->uniquecharcount
1573 < trie->lasttrans)
1574 && trie->trans[base + charid - 1 -
1575 trie->uniquecharcount].check == state
1576 && (tmp=trie->trans[base + charid - 1 -
1577 trie->uniquecharcount ].next))
1578 {
786e8c11
YO
1579 DEBUG_TRIE_EXECUTE_r(
1580 PerlIO_printf( Perl_debug_log," - legal\n"));
07be1b83
YO
1581 state = tmp;
1582 break;
1583 }
1584 else {
786e8c11
YO
1585 DEBUG_TRIE_EXECUTE_r(
1586 PerlIO_printf( Perl_debug_log," - fail\n"));
1587 failed = 1;
1588 state = aho->fail[state];
07be1b83
YO
1589 }
1590 }
1591 else {
1592 /* we must be accepting here */
786e8c11
YO
1593 DEBUG_TRIE_EXECUTE_r(
1594 PerlIO_printf( Perl_debug_log," - accepting\n"));
1595 failed = 1;
07be1b83
YO
1596 break;
1597 }
1598 } while(state);
786e8c11 1599 uc += len;
07be1b83
YO
1600 if (failed) {
1601 if (leftmost)
1602 break;
786e8c11 1603 if (!state) state = 1;
07be1b83
YO
1604 }
1605 }
1606 if ( aho->states[ state ].wordnum ) {
1607 U8 *lpos = points[ (pointpos - trie->wordlen[aho->states[ state ].wordnum-1]) % maxlen ];
786e8c11
YO
1608 if (!leftmost || lpos < leftmost) {
1609 DEBUG_r(accepted_word=aho->states[ state ].wordnum);
07be1b83 1610 leftmost = lpos;
786e8c11 1611 }
07be1b83 1612 }
07be1b83
YO
1613 if (leftmost) {
1614 s = (char*)leftmost;
786e8c11
YO
1615 DEBUG_TRIE_EXECUTE_r({
1616 PerlIO_printf(
70685ca0
JH
1617 Perl_debug_log,"Matches word #%"UVxf" at position %"IVdf". Trying full pattern...\n",
1618 (UV)accepted_word, (IV)(s - real_start)
786e8c11
YO
1619 );
1620 });
24b23f37 1621 if (!reginfo || regtry(reginfo, &s)) {
be8e71aa
YO
1622 FREETMPS;
1623 LEAVE;
07be1b83 1624 goto got_it;
be8e71aa 1625 }
07be1b83 1626 s = HOPc(s,1);
786e8c11
YO
1627 DEBUG_TRIE_EXECUTE_r({
1628 PerlIO_printf( Perl_debug_log,"Pattern failed. Looking for new start point...\n");
1629 });
07be1b83 1630 } else {
786e8c11
YO
1631 DEBUG_TRIE_EXECUTE_r(
1632 PerlIO_printf( Perl_debug_log,"No match.\n"));
07be1b83
YO
1633 break;
1634 }
1635 }
be8e71aa
YO
1636 FREETMPS;
1637 LEAVE;
07be1b83
YO
1638 }
1639 break;
b3c9acc1 1640 default:
3c3eec57
GS
1641 Perl_croak(aTHX_ "panic: unknown regstclass %d", (int)OP(c));
1642 break;
d6a28714 1643 }
6eb5f6b9
JH
1644 return 0;
1645 got_it:
1646 return s;
1647}
1648
1649/*
1650 - regexec_flags - match a regexp against a string
1651 */
1652I32
1653Perl_regexec_flags(pTHX_ register regexp *prog, char *stringarg, register char *strend,
1654 char *strbeg, I32 minend, SV *sv, void *data, U32 flags)
1655/* strend: pointer to null at end of string */
1656/* strbeg: real beginning of string */
1657/* minend: end of match must be >=minend after stringarg. */
58e23c8d
YO
1658/* data: May be used for some additional optimizations.
1659 Currently its only used, with a U32 cast, for transmitting
1660 the ganch offset when doing a /g match. This will change */
6eb5f6b9
JH
1661/* nosave: For optimizations. */
1662{
97aff369 1663 dVAR;
24b23f37 1664 /*register*/ char *s;
6eb5f6b9 1665 register regnode *c;
24b23f37 1666 /*register*/ char *startpos = stringarg;
6eb5f6b9
JH
1667 I32 minlen; /* must match at least this many chars */
1668 I32 dontbother = 0; /* how many characters not to try at end */
6eb5f6b9
JH
1669 I32 end_shift = 0; /* Same for the end. */ /* CC */
1670 I32 scream_pos = -1; /* Internal iterator of scream. */
ccac19ea 1671 char *scream_olds = NULL;
3dab1dad 1672 SV* const oreplsv = GvSV(PL_replgv);
f9f4320a 1673 const bool do_utf8 = (bool)DO_UTF8(sv);
2757e526 1674 I32 multiline;
f8fc2ecf 1675 RXi_GET_DECL(prog,progi);
3b0527fe 1676 regmatch_info reginfo; /* create some info to pass to regtry etc */
a3621e74
YO
1677
1678 GET_RE_DEBUG_FLAGS_DECL;
1679
9d4ba2ae 1680 PERL_UNUSED_ARG(data);
6eb5f6b9
JH
1681
1682 /* Be paranoid... */
1683 if (prog == NULL || startpos == NULL) {
1684 Perl_croak(aTHX_ "NULL regexp parameter");
1685 return 0;
1686 }
1687
bbe252da 1688 multiline = prog->extflags & RXf_PMf_MULTILINE;
3b0527fe 1689 reginfo.prog = prog;
2757e526 1690
bac06658 1691 RX_MATCH_UTF8_set(prog, do_utf8);
1de06328
YO
1692 DEBUG_EXECUTE_r(
1693 debug_start_match(prog, do_utf8, startpos, strend,
1694 "Matching");
1695 );
bac06658 1696
6eb5f6b9 1697 minlen = prog->minlen;
1de06328
YO
1698
1699 if (strend - startpos < (minlen+(prog->check_offset_min<0?prog->check_offset_min:0))) {
a3621e74 1700 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
a72c7584
JH
1701 "String too short [regexec_flags]...\n"));
1702 goto phooey;
1aa99e6b 1703 }
6eb5f6b9 1704
1de06328 1705
6eb5f6b9 1706 /* Check validity of program. */
f8fc2ecf 1707 if (UCHARAT(progi->program) != REG_MAGIC) {
6eb5f6b9
JH
1708 Perl_croak(aTHX_ "corrupted regexp program");
1709 }
1710
1711 PL_reg_flags = 0;
1712 PL_reg_eval_set = 0;
1713 PL_reg_maxiter = 0;
1714
bbe252da 1715 if (prog->extflags & RXf_UTF8)
6eb5f6b9
JH
1716 PL_reg_flags |= RF_utf8;
1717
1718 /* Mark beginning of line for ^ and lookbehind. */
3b0527fe 1719 reginfo.bol = startpos; /* XXX not used ??? */
6eb5f6b9 1720 PL_bostr = strbeg;
3b0527fe 1721 reginfo.sv = sv;
6eb5f6b9
JH
1722
1723 /* Mark end of line for $ (and such) */
1724 PL_regeol = strend;
1725
1726 /* see how far we have to get to not match where we matched before */
3b0527fe 1727 reginfo.till = startpos+minend;
6eb5f6b9 1728
6eb5f6b9
JH
1729 /* If there is a "must appear" string, look for it. */
1730 s = startpos;
1731
bbe252da 1732 if (prog->extflags & RXf_GPOS_SEEN) { /* Need to set reginfo->ganch */
6eb5f6b9
JH
1733 MAGIC *mg;
1734
1735 if (flags & REXEC_IGNOREPOS) /* Means: check only at start */
58e23c8d 1736 reginfo.ganch = startpos + prog->gofs;
6eb5f6b9
JH
1737 else if (sv && SvTYPE(sv) >= SVt_PVMG
1738 && SvMAGIC(sv)
14befaf4
DM
1739 && (mg = mg_find(sv, PERL_MAGIC_regex_global))
1740 && mg->mg_len >= 0) {
3b0527fe 1741 reginfo.ganch = strbeg + mg->mg_len; /* Defined pos() */
bbe252da 1742 if (prog->extflags & RXf_ANCH_GPOS) {
3b0527fe 1743 if (s > reginfo.ganch)
6eb5f6b9 1744 goto phooey;
58e23c8d 1745 s = reginfo.ganch - prog->gofs;
6eb5f6b9
JH
1746 }
1747 }
58e23c8d 1748 else if (data) {
70685ca0 1749 reginfo.ganch = strbeg + PTR2UV(data);
58e23c8d 1750 } else /* pos() not defined */
3b0527fe 1751 reginfo.ganch = strbeg;
6eb5f6b9 1752 }
c74340f9
YO
1753 if (PL_curpm && (PM_GETRE(PL_curpm) == prog)) {
1754 I32 *t;
f8fc2ecf 1755 if (!progi->swap) {
c74340f9
YO
1756 /* We have to be careful. If the previous successful match
1757 was from this regex we don't want a subsequent paritally
1758 successful match to clobber the old results.
1759 So when we detect this possibility we add a swap buffer
1760 to the re, and switch the buffer each match. If we fail
1761 we switch it back, otherwise we leave it swapped.
1762 */
f8fc2ecf 1763 Newxz(progi->swap, 1, regexp_paren_ofs);
c74340f9 1764 /* no need to copy these */
f8fc2ecf
YO
1765 Newxz(progi->swap->startp, prog->nparens + 1, I32);
1766 Newxz(progi->swap->endp, prog->nparens + 1, I32);
c74340f9 1767 }
f8fc2ecf
YO
1768 t = progi->swap->startp;
1769 progi->swap->startp = prog->startp;
c74340f9 1770 prog->startp = t;
f8fc2ecf
YO
1771 t = progi->swap->endp;
1772 progi->swap->endp = prog->endp;
c74340f9
YO
1773 prog->endp = t;
1774 }
a0714e2c 1775 if (!(flags & REXEC_CHECKED) && (prog->check_substr != NULL || prog->check_utf8 != NULL)) {
6eb5f6b9
JH
1776 re_scream_pos_data d;
1777
1778 d.scream_olds = &scream_olds;
1779 d.scream_pos = &scream_pos;
1780 s = re_intuit_start(prog, sv, s, strend, flags, &d);
3fa9c3d7 1781 if (!s) {
a3621e74 1782 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "Not present...\n"));
6eb5f6b9 1783 goto phooey; /* not present */
3fa9c3d7 1784 }
6eb5f6b9
JH
1785 }
1786
1de06328 1787
6eb5f6b9
JH
1788
1789 /* Simplest case: anchored match need be tried only once. */
1790 /* [unless only anchor is BOL and multiline is set] */
bbe252da 1791 if (prog->extflags & (RXf_ANCH & ~RXf_ANCH_GPOS)) {
24b23f37 1792 if (s == startpos && regtry(&reginfo, &startpos))
6eb5f6b9 1793 goto got_it;
bbe252da
YO
1794 else if (multiline || (prog->intflags & PREGf_IMPLICIT)
1795 || (prog->extflags & RXf_ANCH_MBOL)) /* XXXX SBOL? */
6eb5f6b9
JH
1796 {
1797 char *end;
1798
1799 if (minlen)
1800 dontbother = minlen - 1;
1aa99e6b 1801 end = HOP3c(strend, -dontbother, strbeg) - 1;
6eb5f6b9 1802 /* for multiline we only have to try after newlines */
33b8afdf 1803 if (prog->check_substr || prog->check_utf8) {
6eb5f6b9
JH
1804 if (s == startpos)
1805 goto after_try;
1806 while (1) {
24b23f37 1807 if (regtry(&reginfo, &s))
6eb5f6b9
JH
1808 goto got_it;
1809 after_try:
1810 if (s >= end)
1811 goto phooey;
bbe252da 1812 if (prog->extflags & RXf_USE_INTUIT) {
6eb5f6b9
JH
1813 s = re_intuit_start(prog, sv, s + 1, strend, flags, NULL);
1814 if (!s)
1815 goto phooey;
1816 }
1817 else
1818 s++;
1819 }
1820 } else {
1821 if (s > startpos)
1822 s--;
1823 while (s < end) {
1824 if (*s++ == '\n') { /* don't need PL_utf8skip here */
24b23f37 1825 if (regtry(&reginfo, &s))
6eb5f6b9
JH
1826 goto got_it;
1827 }
1828 }
1829 }
1830 }
1831 goto phooey;
bbe252da 1832 } else if (RXf_GPOS_CHECK == (prog->extflags & RXf_GPOS_CHECK))
f9f4320a
YO
1833 {
1834 /* the warning about reginfo.ganch being used without intialization
bbe252da 1835 is bogus -- we set it above, when prog->extflags & RXf_GPOS_SEEN
f9f4320a 1836 and we only enter this block when the same bit is set. */
58e23c8d
YO
1837 char *tmp_s = reginfo.ganch - prog->gofs;
1838 if (regtry(&reginfo, &tmp_s))
6eb5f6b9
JH
1839 goto got_it;
1840 goto phooey;
1841 }
1842
1843 /* Messy cases: unanchored match. */
bbe252da 1844 if ((prog->anchored_substr || prog->anchored_utf8) && prog->intflags & PREGf_SKIP) {
6eb5f6b9
JH
1845 /* we have /x+whatever/ */
1846 /* it must be a one character string (XXXX Except UTF?) */
33b8afdf 1847 char ch;
bf93d4cc
GS
1848#ifdef DEBUGGING
1849 int did_match = 0;
1850#endif
33b8afdf
JH
1851 if (!(do_utf8 ? prog->anchored_utf8 : prog->anchored_substr))
1852 do_utf8 ? to_utf8_substr(prog) : to_byte_substr(prog);
3f7c398e 1853 ch = SvPVX_const(do_utf8 ? prog->anchored_utf8 : prog->anchored_substr)[0];
bf93d4cc 1854
1aa99e6b 1855 if (do_utf8) {
4cadc6a9 1856 REXEC_FBC_SCAN(
6eb5f6b9 1857 if (*s == ch) {
a3621e74 1858 DEBUG_EXECUTE_r( did_match = 1 );
24b23f37 1859 if (regtry(&reginfo, &s)) goto got_it;
6eb5f6b9
JH
1860 s += UTF8SKIP(s);
1861 while (s < strend && *s == ch)
1862 s += UTF8SKIP(s);
1863 }
4cadc6a9 1864 );
6eb5f6b9
JH
1865 }
1866 else {
4cadc6a9 1867 REXEC_FBC_SCAN(
6eb5f6b9 1868 if (*s == ch) {
a3621e74 1869 DEBUG_EXECUTE_r( did_match = 1 );
24b23f37 1870 if (regtry(&reginfo, &s)) goto got_it;
6eb5f6b9
JH
1871 s++;
1872 while (s < strend && *s == ch)
1873 s++;
1874 }
4cadc6a9 1875 );
6eb5f6b9 1876 }
a3621e74 1877 DEBUG_EXECUTE_r(if (!did_match)
bf93d4cc 1878 PerlIO_printf(Perl_debug_log,
b7953727
JH
1879 "Did not find anchored character...\n")
1880 );
6eb5f6b9 1881 }
a0714e2c
SS
1882 else if (prog->anchored_substr != NULL
1883 || prog->anchored_utf8 != NULL
1884 || ((prog->float_substr != NULL || prog->float_utf8 != NULL)
33b8afdf
JH
1885 && prog->float_max_offset < strend - s)) {
1886 SV *must;
1887 I32 back_max;
1888 I32 back_min;
1889 char *last;
6eb5f6b9 1890 char *last1; /* Last position checked before */
bf93d4cc
GS
1891#ifdef DEBUGGING
1892 int did_match = 0;
1893#endif
33b8afdf
JH
1894 if (prog->anchored_substr || prog->anchored_utf8) {
1895 if (!(do_utf8 ? prog->anchored_utf8 : prog->anchored_substr))
1896 do_utf8 ? to_utf8_substr(prog) : to_byte_substr(prog);
1897 must = do_utf8 ? prog->anchored_utf8 : prog->anchored_substr;
1898 back_max = back_min = prog->anchored_offset;
1899 } else {
1900 if (!(do_utf8 ? prog->float_utf8 : prog->float_substr))
1901 do_utf8 ? to_utf8_substr(prog) : to_byte_substr(prog);
1902 must = do_utf8 ? prog->float_utf8 : prog->float_substr;
1903 back_max = prog->float_max_offset;
1904 back_min = prog->float_min_offset;
1905 }
1de06328
YO
1906
1907
33b8afdf
JH
1908 if (must == &PL_sv_undef)
1909 /* could not downgrade utf8 check substring, so must fail */
1910 goto phooey;
1911
1de06328
YO
1912 if (back_min<0) {
1913 last = strend;
1914 } else {
1915 last = HOP3c(strend, /* Cannot start after this */
1916 -(I32)(CHR_SVLEN(must)
1917 - (SvTAIL(must) != 0) + back_min), strbeg);
1918 }
6eb5f6b9
JH
1919 if (s > PL_bostr)
1920 last1 = HOPc(s, -1);
1921 else
1922 last1 = s - 1; /* bogus */
1923
a0288114 1924 /* XXXX check_substr already used to find "s", can optimize if
6eb5f6b9
JH
1925 check_substr==must. */
1926 scream_pos = -1;
1927 dontbother = end_shift;
1928 strend = HOPc(strend, -dontbother);
1929 while ( (s <= last) &&
9041c2e3 1930 ((flags & REXEC_SCREAM)
1de06328 1931 ? (s = screaminstr(sv, must, HOP3c(s, back_min, (back_min<0 ? strbeg : strend)) - strbeg,
6eb5f6b9 1932 end_shift, &scream_pos, 0))
1de06328 1933 : (s = fbm_instr((unsigned char*)HOP3(s, back_min, (back_min<0 ? strbeg : strend)),
9041c2e3 1934 (unsigned char*)strend, must,
7fba1cd6 1935 multiline ? FBMrf_MULTILINE : 0))) ) {
4addbd3b
HS
1936 /* we may be pointing at the wrong string */
1937 if ((flags & REXEC_SCREAM) && RX_MATCH_COPIED(prog))
3f7c398e 1938 s = strbeg + (s - SvPVX_const(sv));
a3621e74 1939 DEBUG_EXECUTE_r( did_match = 1 );
6eb5f6b9
JH
1940 if (HOPc(s, -back_max) > last1) {
1941 last1 = HOPc(s, -back_min);
1942 s = HOPc(s, -back_max);
1943 }
1944 else {
52657f30 1945 char * const t = (last1 >= PL_bostr) ? HOPc(last1, 1) : last1 + 1;
6eb5f6b9
JH
1946
1947 last1 = HOPc(s, -back_min);
52657f30 1948 s = t;
6eb5f6b9 1949 }
1aa99e6b 1950 if (do_utf8) {
6eb5f6b9 1951 while (s <= last1) {
24b23f37 1952 if (regtry(&reginfo, &s))
6eb5f6b9
JH
1953 goto got_it;
1954 s += UTF8SKIP(s);
1955 }
1956 }
1957 else {
1958 while (s <= last1) {
24b23f37 1959 if (regtry(&reginfo, &s))
6eb5f6b9
JH
1960 goto got_it;
1961 s++;
1962 }
1963 }
1964 }
ab3bbdeb
YO
1965 DEBUG_EXECUTE_r(if (!did_match) {
1966 RE_PV_QUOTED_DECL(quoted, do_utf8, PERL_DEBUG_PAD_ZERO(0),
1967 SvPVX_const(must), RE_SV_DUMPLEN(must), 30);
1968 PerlIO_printf(Perl_debug_log, "Did not find %s substr %s%s...\n",
33b8afdf 1969 ((must == prog->anchored_substr || must == prog->anchored_utf8)
bf93d4cc 1970 ? "anchored" : "floating"),
ab3bbdeb
YO
1971 quoted, RE_SV_TAIL(must));
1972 });
6eb5f6b9
JH
1973 goto phooey;
1974 }
f8fc2ecf 1975 else if ( (c = progi->regstclass) ) {
f14c76ed 1976 if (minlen) {
f8fc2ecf 1977 const OPCODE op = OP(progi->regstclass);
66e933ab 1978 /* don't bother with what can't match */
786e8c11 1979 if (PL_regkind[op] != EXACT && op != CANY && PL_regkind[op] != TRIE)
f14c76ed
RGS
1980 strend = HOPc(strend, -(minlen - 1));
1981 }
a3621e74 1982 DEBUG_EXECUTE_r({
be8e71aa 1983 SV * const prop = sv_newmortal();
32fc9b6a 1984 regprop(prog, prop, c);
0df25f3d 1985 {
ab3bbdeb
YO
1986 RE_PV_QUOTED_DECL(quoted,UTF,PERL_DEBUG_PAD_ZERO(1),
1987 s,strend-s,60);
0df25f3d 1988 PerlIO_printf(Perl_debug_log,
ab3bbdeb 1989 "Matching stclass %.*s against %s (%d chars)\n",
e4f74956 1990 (int)SvCUR(prop), SvPVX_const(prop),
ab3bbdeb 1991 quoted, (int)(strend - s));
0df25f3d 1992 }
ffc61ed2 1993 });
3b0527fe 1994 if (find_byclass(prog, c, s, strend, &reginfo))
6eb5f6b9 1995 goto got_it;
07be1b83 1996 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "Contradicts stclass... [regexec_flags]\n"));
d6a28714
JH
1997 }
1998 else {
1999 dontbother = 0;
a0714e2c 2000 if (prog->float_substr != NULL || prog->float_utf8 != NULL) {
33b8afdf 2001 /* Trim the end. */
d6a28714 2002 char *last;
33b8afdf
JH
2003 SV* float_real;
2004
2005 if (!(do_utf8 ? prog->float_utf8 : prog->float_substr))
2006 do_utf8 ? to_utf8_substr(prog) : to_byte_substr(prog);
2007 float_real = do_utf8 ? prog->float_utf8 : prog->float_substr;
d6a28714
JH
2008
2009 if (flags & REXEC_SCREAM) {
33b8afdf 2010 last = screaminstr(sv, float_real, s - strbeg,
d6a28714
JH
2011 end_shift, &scream_pos, 1); /* last one */
2012 if (!last)
ffc61ed2 2013 last = scream_olds; /* Only one occurrence. */
4addbd3b
HS
2014 /* we may be pointing at the wrong string */
2015 else if (RX_MATCH_COPIED(prog))
3f7c398e 2016 s = strbeg + (s - SvPVX_const(sv));
b8c5462f 2017 }
d6a28714
JH
2018 else {
2019 STRLEN len;
cfd0369c 2020 const char * const little = SvPV_const(float_real, len);
d6a28714 2021
33b8afdf 2022 if (SvTAIL(float_real)) {
d6a28714
JH
2023 if (memEQ(strend - len + 1, little, len - 1))
2024 last = strend - len + 1;
7fba1cd6 2025 else if (!multiline)
9041c2e3 2026 last = memEQ(strend - len, little, len)
bd61b366 2027 ? strend - len : NULL;
b8c5462f 2028 else
d6a28714
JH
2029 goto find_last;
2030 } else {
2031 find_last:
9041c2e3 2032 if (len)
d6a28714 2033 last = rninstr(s, strend, little, little + len);
b8c5462f 2034 else
a0288114 2035 last = strend; /* matching "$" */
b8c5462f 2036 }
b8c5462f 2037 }
bf93d4cc 2038 if (last == NULL) {
6bda09f9
YO
2039 DEBUG_EXECUTE_r(
2040 PerlIO_printf(Perl_debug_log,
2041 "%sCan't trim the tail, match fails (should not happen)%s\n",
2042 PL_colors[4], PL_colors[5]));
bf93d4cc
GS
2043 goto phooey; /* Should not happen! */
2044 }
d6a28714
JH
2045 dontbother = strend - last + prog->float_min_offset;
2046 }
2047 if (minlen && (dontbother < minlen))
2048 dontbother = minlen - 1;
2049 strend -= dontbother; /* this one's always in bytes! */
2050 /* We don't know much -- general case. */
1aa99e6b 2051 if (do_utf8) {
d6a28714 2052 for (;;) {
24b23f37 2053 if (regtry(&reginfo, &s))
d6a28714
JH
2054 goto got_it;
2055 if (s >= strend)
2056 break;
b8c5462f 2057 s += UTF8SKIP(s);
d6a28714
JH
2058 };
2059 }
2060 else {
2061 do {
24b23f37 2062 if (regtry(&reginfo, &s))
d6a28714
JH
2063 goto got_it;
2064 } while (s++ < strend);
2065 }
2066 }
2067
2068 /* Failure. */
2069 goto phooey;
2070
2071got_it:
2072 RX_MATCH_TAINTED_set(prog, PL_reg_flags & RF_tainted);
2073
2074 if (PL_reg_eval_set) {
2075 /* Preserve the current value of $^R */
2076 if (oreplsv != GvSV(PL_replgv))
2077 sv_setsv(oreplsv, GvSV(PL_replgv));/* So that when GvSV(replgv) is
2078 restored, the value remains
2079 the same. */
4f639d21 2080 restore_pos(aTHX_ prog);
d6a28714 2081 }
81714fb9
YO
2082 if (prog->paren_names)
2083 (void)hv_iterinit(prog->paren_names);
d6a28714
JH
2084
2085 /* make sure $`, $&, $', and $digit will work later */
2086 if ( !(flags & REXEC_NOT_FIRST) ) {
ed252734 2087 RX_MATCH_COPY_FREE(prog);
d6a28714 2088 if (flags & REXEC_COPY_STR) {
be8e71aa 2089 const I32 i = PL_regeol - startpos + (stringarg - strbeg);
f8c7b90f 2090#ifdef PERL_OLD_COPY_ON_WRITE
ed252734
NC
2091 if ((SvIsCOW(sv)
2092 || (SvFLAGS(sv) & CAN_COW_MASK) == CAN_COW_FLAGS)) {
2093 if (DEBUG_C_TEST) {
2094 PerlIO_printf(Perl_debug_log,
2095 "Copy on write: regexp capture, type %d\n",
2096 (int) SvTYPE(sv));
2097 }
2098 prog->saved_copy = sv_setsv_cow(prog->saved_copy, sv);
d5263905 2099 prog->subbeg = (char *)SvPVX_const(prog->saved_copy);
ed252734
NC
2100 assert (SvPOKp(prog->saved_copy));
2101 } else
2102#endif
2103 {
2104 RX_MATCH_COPIED_on(prog);
2105 s = savepvn(strbeg, i);
2106 prog->subbeg = s;
2107 }
d6a28714 2108 prog->sublen = i;
d6a28714
JH
2109 }
2110 else {
2111 prog->subbeg = strbeg;
2112 prog->sublen = PL_regeol - strbeg; /* strend may have been modified */
2113 }
2114 }
9041c2e3 2115
d6a28714
JH
2116 return 1;
2117
2118phooey:
a3621e74 2119 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "%sMatch failed%s\n",
e4584336 2120 PL_colors[4], PL_colors[5]));
d6a28714 2121 if (PL_reg_eval_set)
4f639d21 2122 restore_pos(aTHX_ prog);
f8fc2ecf 2123 if (progi->swap) {
c74340f9
YO
2124 /* we failed :-( roll it back */
2125 I32 *t;
f8fc2ecf
YO
2126 t = progi->swap->startp;
2127 progi->swap->startp = prog->startp;
c74340f9 2128 prog->startp = t;
f8fc2ecf
YO
2129 t = progi->swap->endp;
2130 progi->swap->endp = prog->endp;
c74340f9
YO
2131 prog->endp = t;
2132 }
d6a28714
JH
2133 return 0;
2134}
2135
6bda09f9 2136
d6a28714
JH
2137/*
2138 - regtry - try match at specific point
2139 */
2140STATIC I32 /* 0 failure, 1 success */
24b23f37 2141S_regtry(pTHX_ regmatch_info *reginfo, char **startpos)
d6a28714 2142{
97aff369 2143 dVAR;
d6a28714
JH
2144 register I32 *sp;
2145 register I32 *ep;
2146 CHECKPOINT lastcp;
3b0527fe 2147 regexp *prog = reginfo->prog;
f8fc2ecf 2148 RXi_GET_DECL(prog,progi);
a3621e74 2149 GET_RE_DEBUG_FLAGS_DECL;
24b23f37 2150 reginfo->cutpoint=NULL;
d6a28714 2151
bbe252da 2152 if ((prog->extflags & RXf_EVAL_SEEN) && !PL_reg_eval_set) {
d6a28714
JH
2153 MAGIC *mg;
2154
2155 PL_reg_eval_set = RS_init;
a3621e74 2156 DEBUG_EXECUTE_r(DEBUG_s(
b900a521
JH
2157 PerlIO_printf(Perl_debug_log, " setting stack tmpbase at %"IVdf"\n",
2158 (IV)(PL_stack_sp - PL_stack_base));
d6a28714 2159 ));
ea8d6ae1 2160 SAVESTACK_CXPOS();
d6a28714
JH
2161 cxstack[cxstack_ix].blk_oldsp = PL_stack_sp - PL_stack_base;
2162 /* Otherwise OP_NEXTSTATE will free whatever on stack now. */
2163 SAVETMPS;
2164 /* Apparently this is not needed, judging by wantarray. */
e8347627 2165 /* SAVEI8(cxstack[cxstack_ix].blk_gimme);
d6a28714
JH
2166 cxstack[cxstack_ix].blk_gimme = G_SCALAR; */
2167
3b0527fe 2168 if (reginfo->sv) {
d6a28714 2169 /* Make $_ available to executed code. */
3b0527fe 2170 if (reginfo->sv != DEFSV) {
59f00321 2171 SAVE_DEFSV;
3b0527fe 2172 DEFSV = reginfo->sv;
b8c5462f 2173 }
d6a28714 2174
3b0527fe
DM
2175 if (!(SvTYPE(reginfo->sv) >= SVt_PVMG && SvMAGIC(reginfo->sv)
2176 && (mg = mg_find(reginfo->sv, PERL_MAGIC_regex_global)))) {
d6a28714 2177 /* prepare for quick setting of pos */
d300d9fa 2178#ifdef PERL_OLD_COPY_ON_WRITE
51a9ea20
NC
2179 if (SvIsCOW(reginfo->sv))
2180 sv_force_normal_flags(reginfo->sv, 0);
d300d9fa 2181#endif
3dab1dad 2182 mg = sv_magicext(reginfo->sv, NULL, PERL_MAGIC_regex_global,
d300d9fa 2183 &PL_vtbl_mglob, NULL, 0);
d6a28714 2184 mg->mg_len = -1;
b8c5462f 2185 }
d6a28714
JH
2186 PL_reg_magic = mg;
2187 PL_reg_oldpos = mg->mg_len;
4f639d21 2188 SAVEDESTRUCTOR_X(restore_pos, prog);
d6a28714 2189 }
09687e5a 2190 if (!PL_reg_curpm) {
a02a5408 2191 Newxz(PL_reg_curpm, 1, PMOP);
09687e5a
AB
2192#ifdef USE_ITHREADS
2193 {
be8e71aa 2194 SV* const repointer = newSViv(0);
577e12cc 2195 /* so we know which PL_regex_padav element is PL_reg_curpm */
35061a7e 2196 SvFLAGS(repointer) |= SVf_BREAK;
09687e5a
AB
2197 av_push(PL_regex_padav,repointer);
2198 PL_reg_curpm->op_pmoffset = av_len(PL_regex_padav);
2199 PL_regex_pad = AvARRAY(PL_regex_padav);
2200 }
2201#endif
2202 }
aaa362c4 2203 PM_SETRE(PL_reg_curpm, prog);
d6a28714
JH
2204 PL_reg_oldcurpm = PL_curpm;
2205 PL_curpm = PL_reg_curpm;
2206 if (RX_MATCH_COPIED(prog)) {
2207 /* Here is a serious problem: we cannot rewrite subbeg,
2208 since it may be needed if this match fails. Thus
2209 $` inside (?{}) could fail... */
2210 PL_reg_oldsaved = prog->subbeg;
2211 PL_reg_oldsavedlen = prog->sublen;
f8c7b90f 2212#ifdef PERL_OLD_COPY_ON_WRITE
ed252734
NC
2213 PL_nrs = prog->saved_copy;
2214#endif
d6a28714
JH
2215 RX_MATCH_COPIED_off(prog);
2216 }
2217 else
bd61b366 2218 PL_reg_oldsaved = NULL;
d6a28714
JH
2219 prog->subbeg = PL_bostr;
2220 prog->sublen = PL_regeol - PL_bostr; /* strend may have been modified */
2221 }
24b23f37
YO
2222 DEBUG_EXECUTE_r(PL_reg_starttry = *startpos);
2223 prog->startp[0] = *startpos - PL_bostr;
2224 PL_reginput = *startpos;
d6a28714 2225 PL_reglastparen = &prog->lastparen;
a01268b5 2226 PL_reglastcloseparen = &prog->lastcloseparen;
d6a28714 2227 prog->lastparen = 0;
03994de8 2228 prog->lastcloseparen = 0;
d6a28714 2229 PL_regsize = 0;
6bda09f9
YO
2230 PL_regstartp = prog->startp;
2231 PL_regendp = prog->endp;
d6a28714
JH
2232 if (PL_reg_start_tmpl <= prog->nparens) {
2233 PL_reg_start_tmpl = prog->nparens*3/2 + 3;
2234 if(PL_reg_start_tmp)
2235 Renew(PL_reg_start_tmp, PL_reg_start_tmpl, char*);
2236 else
a02a5408 2237 Newx(PL_reg_start_tmp, PL_reg_start_tmpl, char*);
d6a28714
JH
2238 }
2239
2240 /* XXXX What this code is doing here?!!! There should be no need
2241 to do this again and again, PL_reglastparen should take care of
3dd2943c 2242 this! --ilya*/
dafc8851
JH
2243
2244 /* Tests pat.t#187 and split.t#{13,14} seem to depend on this code.
2245 * Actually, the code in regcppop() (which Ilya may be meaning by
daf18116
JH
2246 * PL_reglastparen), is not needed at all by the test suite
2247 * (op/regexp, op/pat, op/split), but that code is needed, oddly
2248 * enough, for building DynaLoader, or otherwise this
2249 * "Error: '*' not in typemap in DynaLoader.xs, line 164"
2250 * will happen. Meanwhile, this code *is* needed for the
2251 * above-mentioned test suite tests to succeed. The common theme
2252 * on those tests seems to be returning null fields from matches.
2253 * --jhi */
dafc8851 2254#if 1
c74340f9
YO
2255 sp = PL_regstartp;
2256 ep = PL_regendp;
d6a28714 2257 if (prog->nparens) {
097eb12c 2258 register I32 i;
eb160463 2259 for (i = prog->nparens; i > (I32)*PL_reglastparen; i--) {
d6a28714
JH
2260 *++sp = -1;
2261 *++ep = -1;
2262 }
2263 }
dafc8851 2264#endif
02db2b7b 2265 REGCP_SET(lastcp);
f8fc2ecf 2266 if (regmatch(reginfo, progi->program + 1)) {
c74340f9 2267 PL_regendp[0] = PL_reginput - PL_bostr;
d6a28714
JH
2268 return 1;
2269 }
24b23f37
YO
2270 if (reginfo->cutpoint)
2271 *startpos= reginfo->cutpoint;
02db2b7b 2272 REGCP_UNWIND(lastcp);
d6a28714
JH
2273 return 0;
2274}
2275
02db2b7b 2276
8ba1375e
MJD
2277#define sayYES goto yes
2278#define sayNO goto no
262b90c4 2279#define sayNO_SILENT goto no_silent
8ba1375e 2280
f9f4320a
YO
2281/* we dont use STMT_START/END here because it leads to
2282 "unreachable code" warnings, which are bogus, but distracting. */
2283#define CACHEsayNO \
c476f425
DM
2284 if (ST.cache_mask) \
2285 PL_reg_poscache[ST.cache_offset] |= ST.cache_mask; \
f9f4320a 2286 sayNO
3298f257 2287
a3621e74 2288/* this is used to determine how far from the left messages like
265c4333
YO
2289 'failed...' are printed. It should be set such that messages
2290 are inline with the regop output that created them.
a3621e74 2291*/
265c4333 2292#define REPORT_CODE_OFF 32
a3621e74
YO
2293
2294
2295/* Make sure there is a test for this +1 options in re_tests */
2296#define TRIE_INITAL_ACCEPT_BUFFLEN 4;
2297
40a82448
DM
2298#define CHRTEST_UNINIT -1001 /* c1/c2 haven't been calculated yet */
2299#define CHRTEST_VOID -1000 /* the c1/c2 "next char" test should be skipped */
9e137952 2300
86545054
DM
2301#define SLAB_FIRST(s) (&(s)->states[0])
2302#define SLAB_LAST(s) (&(s)->states[PERL_REGMATCH_SLAB_SLOTS-1])
2303
5d9a96ca
DM
2304/* grab a new slab and return the first slot in it */
2305
2306STATIC regmatch_state *
2307S_push_slab(pTHX)
2308{
54df2634
NC
2309#if PERL_VERSION < 9
2310 dMY_CXT;
2311#endif
5d9a96ca
DM
2312 regmatch_slab *s = PL_regmatch_slab->next;
2313 if (!s) {
2314 Newx(s, 1, regmatch_slab);
2315 s->prev = PL_regmatch_slab;
2316 s->next = NULL;
2317 PL_regmatch_slab->next = s;
2318 }
2319 PL_regmatch_slab = s;
86545054 2320 return SLAB_FIRST(s);
5d9a96ca 2321}
5b47454d 2322
95b24440 2323
40a82448
DM
2324/* push a new state then goto it */
2325
2326#define PUSH_STATE_GOTO(state, node) \
2327 scan = node; \
2328 st->resume_state = state; \
2329 goto push_state;
2330
2331/* push a new state with success backtracking, then goto it */
2332
2333#define PUSH_YES_STATE_GOTO(state, node) \
2334 scan = node; \
2335 st->resume_state = state; \
2336 goto push_yes_state;
2337
aa283a38 2338
aa283a38 2339
d6a28714 2340/*
95b24440 2341
bf1f174e
DM
2342regmatch() - main matching routine
2343
2344This is basically one big switch statement in a loop. We execute an op,
2345set 'next' to point the next op, and continue. If we come to a point which
2346we may need to backtrack to on failure such as (A|B|C), we push a
2347backtrack state onto the backtrack stack. On failure, we pop the top
2348state, and re-enter the loop at the state indicated. If there are no more
2349states to pop, we return failure.
2350
2351Sometimes we also need to backtrack on success; for example /A+/, where
2352after successfully matching one A, we need to go back and try to
2353match another one; similarly for lookahead assertions: if the assertion
2354completes successfully, we backtrack to the state just before the assertion
2355and then carry on. In these cases, the pushed state is marked as
2356'backtrack on success too'. This marking is in fact done by a chain of
2357pointers, each pointing to the previous 'yes' state. On success, we pop to
2358the nearest yes state, discarding any intermediate failure-only states.
2359Sometimes a yes state is pushed just to force some cleanup code to be
2360called at the end of a successful match or submatch; e.g. (??{$re}) uses
2361it to free the inner regex.
2362
2363Note that failure backtracking rewinds the cursor position, while
2364success backtracking leaves it alone.
2365
2366A pattern is complete when the END op is executed, while a subpattern
2367such as (?=foo) is complete when the SUCCESS op is executed. Both of these
2368ops trigger the "pop to last yes state if any, otherwise return true"
2369behaviour.
2370
2371A common convention in this function is to use A and B to refer to the two
2372subpatterns (or to the first nodes thereof) in patterns like /A*B/: so A is
2373the subpattern to be matched possibly multiple times, while B is the entire
2374rest of the pattern. Variable and state names reflect this convention.
2375
2376The states in the main switch are the union of ops and failure/success of
2377substates associated with with that op. For example, IFMATCH is the op
2378that does lookahead assertions /(?=A)B/ and so the IFMATCH state means
2379'execute IFMATCH'; while IFMATCH_A is a state saying that we have just
2380successfully matched A and IFMATCH_A_fail is a state saying that we have
2381just failed to match A. Resume states always come in pairs. The backtrack
2382state we push is marked as 'IFMATCH_A', but when that is popped, we resume
2383at IFMATCH_A or IFMATCH_A_fail, depending on whether we are backtracking
2384on success or failure.
2385
2386The struct that holds a backtracking state is actually a big union, with
2387one variant for each major type of op. The variable st points to the
2388top-most backtrack struct. To make the code clearer, within each
2389block of code we #define ST to alias the relevant union.
2390
2391Here's a concrete example of a (vastly oversimplified) IFMATCH
2392implementation:
2393
2394 switch (state) {
2395 ....
2396
2397#define ST st->u.ifmatch
2398
2399 case IFMATCH: // we are executing the IFMATCH op, (?=A)B
2400 ST.foo = ...; // some state we wish to save
95b24440 2401 ...
bf1f174e
DM
2402 // push a yes backtrack state with a resume value of
2403 // IFMATCH_A/IFMATCH_A_fail, then continue execution at the
2404 // first node of A:
2405 PUSH_YES_STATE_GOTO(IFMATCH_A, A);
2406 // NOTREACHED
2407
2408 case IFMATCH_A: // we have successfully executed A; now continue with B
2409 next = B;
2410 bar = ST.foo; // do something with the preserved value
2411 break;
2412
2413 case IFMATCH_A_fail: // A failed, so the assertion failed
2414 ...; // do some housekeeping, then ...
2415 sayNO; // propagate the failure
2416
2417#undef ST
95b24440 2418
bf1f174e
DM
2419 ...
2420 }
95b24440 2421
bf1f174e
DM
2422For any old-timers reading this who are familiar with the old recursive
2423approach, the code above is equivalent to:
95b24440 2424
bf1f174e
DM
2425 case IFMATCH: // we are executing the IFMATCH op, (?=A)B
2426 {
2427 int foo = ...
95b24440 2428 ...
bf1f174e
DM
2429 if (regmatch(A)) {
2430 next = B;
2431 bar = foo;
2432 break;
95b24440 2433 }
bf1f174e
DM
2434 ...; // do some housekeeping, then ...
2435 sayNO; // propagate the failure
95b24440 2436 }
bf1f174e
DM
2437
2438The topmost backtrack state, pointed to by st, is usually free. If you
2439want to claim it, populate any ST.foo fields in it with values you wish to
2440save, then do one of
2441
2442 PUSH_STATE_GOTO(resume_state, node);
2443 PUSH_YES_STATE_GOTO(resume_state, node);
2444
2445which sets that backtrack state's resume value to 'resume_state', pushes a
2446new free entry to the top of the backtrack stack, then goes to 'node'.
2447On backtracking, the free slot is popped, and the saved state becomes the
2448new free state. An ST.foo field in this new top state can be temporarily
2449accessed to retrieve values, but once the main loop is re-entered, it
2450becomes available for reuse.
2451
2452Note that the depth of the backtrack stack constantly increases during the
2453left-to-right execution of the pattern, rather than going up and down with
2454the pattern nesting. For example the stack is at its maximum at Z at the
2455end of the pattern, rather than at X in the following:
2456
2457 /(((X)+)+)+....(Y)+....Z/
2458
2459The only exceptions to this are lookahead/behind assertions and the cut,
2460(?>A), which pop all the backtrack states associated with A before
2461continuing.
2462
2463Bascktrack state structs are allocated in slabs of about 4K in size.
2464PL_regmatch_state and st always point to the currently active state,
2465and PL_regmatch_slab points to the slab currently containing
2466PL_regmatch_state. The first time regmatch() is called, the first slab is
2467allocated, and is never freed until interpreter destruction. When the slab
2468is full, a new one is allocated and chained to the end. At exit from
2469regmatch(), slabs allocated since entry are freed.
2470
2471*/
95b24440 2472
40a82448 2473
5bc10b2c 2474#define DEBUG_STATE_pp(pp) \
265c4333 2475 DEBUG_STATE_r({ \
5bc10b2c
DM
2476 DUMP_EXEC_POS(locinput, scan, do_utf8); \
2477 PerlIO_printf(Perl_debug_log, \
5d458dd8 2478 " %*s"pp" %s%s%s%s%s\n", \
5bc10b2c 2479 depth*2, "", \
5d458dd8
YO
2480 reg_name[st->resume_state], \
2481 ((st==yes_state||st==mark_state) ? "[" : ""), \
2482 ((st==yes_state) ? "Y" : ""), \
2483 ((st==mark_state) ? "M" : ""), \
2484 ((st==yes_state||st==mark_state) ? "]" : "") \
2485 ); \
265c4333 2486 });
5bc10b2c 2487
40a82448 2488
3dab1dad 2489#define REG_NODE_NUM(x) ((x) ? (int)((x)-prog) : -1)
95b24440 2490
3df15adc 2491#ifdef DEBUGGING
5bc10b2c 2492
ab3bbdeb
YO
2493STATIC void
2494S_debug_start_match(pTHX_ const regexp *prog, const bool do_utf8,
2495 const char *start, const char *end, const char *blurb)
2496{
bbe252da 2497 const bool utf8_pat= prog->extflags & RXf_UTF8 ? 1 : 0;
ab3bbdeb
YO
2498 if (!PL_colorset)
2499 reginitcolors();
2500 {
2501 RE_PV_QUOTED_DECL(s0, utf8_pat, PERL_DEBUG_PAD_ZERO(0),
2502 prog->precomp, prog->prelen, 60);
2503
2504 RE_PV_QUOTED_DECL(s1, do_utf8, PERL_DEBUG_PAD_ZERO(1),
2505 start, end - start, 60);
2506
2507 PerlIO_printf(Perl_debug_log,
2508 "%s%s REx%s %s against %s\n",
2509 PL_colors[4], blurb, PL_colors[5], s0, s1);
2510
2511 if (do_utf8||utf8_pat)
1de06328
YO
2512 PerlIO_printf(Perl_debug_log, "UTF-8 %s%s%s...\n",
2513 utf8_pat ? "pattern" : "",
2514 utf8_pat && do_utf8 ? " and " : "",
2515 do_utf8 ? "string" : ""
ab3bbdeb
YO
2516 );
2517 }
2518}
3df15adc
YO
2519
2520STATIC void
786e8c11
YO
2521S_dump_exec_pos(pTHX_ const char *locinput,
2522 const regnode *scan,
2523 const char *loc_regeol,
2524 const char *loc_bostr,
2525 const char *loc_reg_starttry,
2526 const bool do_utf8)
07be1b83 2527{
786e8c11 2528 const int docolor = *PL_colors[0] || *PL_colors[2] || *PL_colors[4];
07be1b83 2529 const int taill = (docolor ? 10 : 7); /* 3 chars for "> <" */
786e8c11 2530 int l = (loc_regeol - locinput) > taill ? taill : (loc_regeol - locinput);
07be1b83
YO
2531 /* The part of the string before starttry has one color
2532 (pref0_len chars), between starttry and current
2533 position another one (pref_len - pref0_len chars),
2534 after the current position the third one.
2535 We assume that pref0_len <= pref_len, otherwise we
2536 decrease pref0_len. */
786e8c11
YO
2537 int pref_len = (locinput - loc_bostr) > (5 + taill) - l
2538 ? (5 + taill) - l : locinput - loc_bostr;
07be1b83
YO
2539 int pref0_len;
2540
2541 while (do_utf8 && UTF8_IS_CONTINUATION(*(U8*)(locinput - pref_len)))
2542 pref_len++;
786e8c11
YO
2543 pref0_len = pref_len - (locinput - loc_reg_starttry);
2544 if (l + pref_len < (5 + taill) && l < loc_regeol - locinput)
2545 l = ( loc_regeol - locinput > (5 + taill) - pref_len
2546 ? (5 + taill) - pref_len : loc_regeol - locinput);
07be1b83
YO
2547 while (do_utf8 && UTF8_IS_CONTINUATION(*(U8*)(locinput + l)))
2548 l--;
2549 if (pref0_len < 0)
2550 pref0_len = 0;
2551 if (pref0_len > pref_len)
2552 pref0_len = pref_len;
2553 {
3df15adc 2554 const int is_uni = (do_utf8 && OP(scan) != CANY) ? 1 : 0;
0df25f3d 2555
ab3bbdeb 2556 RE_PV_COLOR_DECL(s0,len0,is_uni,PERL_DEBUG_PAD(0),
1de06328 2557 (locinput - pref_len),pref0_len, 60, 4, 5);
0df25f3d 2558
ab3bbdeb 2559 RE_PV_COLOR_DECL(s1,len1,is_uni,PERL_DEBUG_PAD(1),
3df15adc 2560 (locinput - pref_len + pref0_len),
1de06328 2561 pref_len - pref0_len, 60, 2, 3);
0df25f3d 2562
ab3bbdeb 2563 RE_PV_COLOR_DECL(s2,len2,is_uni,PERL_DEBUG_PAD(2),
1de06328 2564 locinput, loc_regeol - locinput, 10, 0, 1);
0df25f3d 2565
1de06328 2566 const STRLEN tlen=len0+len1+len2;
3df15adc 2567 PerlIO_printf(Perl_debug_log,
ab3bbdeb 2568 "%4"IVdf" <%.*s%.*s%s%.*s>%*s|",
786e8c11 2569 (IV)(locinput - loc_bostr),
07be1b83 2570 len0, s0,
07be1b83 2571 len1, s1,
07be1b83 2572 (docolor ? "" : "> <"),
07be1b83 2573 len2, s2,
f9f4320a 2574 (int)(tlen > 19 ? 0 : 19 - tlen),
07be1b83
YO
2575 "");
2576 }
2577}
3df15adc 2578
07be1b83
YO
2579#endif
2580
0a4db386
YO
2581/* reg_check_named_buff_matched()
2582 * Checks to see if a named buffer has matched. The data array of
2583 * buffer numbers corresponding to the buffer is expected to reside
2584 * in the regexp->data->data array in the slot stored in the ARG() of
2585 * node involved. Note that this routine doesn't actually care about the
2586 * name, that information is not preserved from compilation to execution.
2587 * Returns the index of the leftmost defined buffer with the given name
2588 * or 0 if non of the buffers matched.
2589 */
2590STATIC I32
2591S_reg_check_named_buff_matched(pTHX_ const regexp *rex, const regnode *scan) {
2592 I32 n;
f8fc2ecf
YO
2593 RXi_GET_DECL(rex,rexi);
2594 SV *sv_dat=(SV*)rexi->data->data[ ARG( scan ) ];
0a4db386
YO
2595 I32 *nums=(I32*)SvPVX(sv_dat);
2596 for ( n=0; n<SvIVX(sv_dat); n++ ) {
2597 if ((I32)*PL_reglastparen >= nums[n] &&
2598 PL_regendp[nums[n]] != -1)
2599 {
2600 return nums[n];
2601 }
2602 }
2603 return 0;
2604}
2605
d6a28714 2606STATIC I32 /* 0 failure, 1 success */
24b23f37 2607S_regmatch(pTHX_ regmatch_info *reginfo, regnode *prog)
d6a28714 2608{
54df2634
NC
2609#if PERL_VERSION < 9
2610 dMY_CXT;
2611#endif
27da23d5 2612 dVAR;
95b24440 2613 register const bool do_utf8 = PL_reg_match_utf8;
4ad0818d 2614 const U32 uniflags = UTF8_ALLOW_DEFAULT;
95b24440 2615
3b0527fe 2616 regexp *rex = reginfo->prog;
f8fc2ecf
YO
2617 RXi_GET_DECL(rex,rexi);
2618
5d9a96ca
DM
2619 regmatch_slab *orig_slab;
2620 regmatch_state *orig_state;
a3621e74 2621
5d9a96ca
DM
2622 /* the current state. This is a cached copy of PL_regmatch_state */
2623 register regmatch_state *st;
95b24440 2624
5d9a96ca
DM
2625 /* cache heavy used fields of st in registers */
2626 register regnode *scan;
2627 register regnode *next;
438e9bae 2628 register U32 n = 0; /* general value; init to avoid compiler warning */
24d3c4a9 2629 register I32 ln = 0; /* len or last; init to avoid compiler warning */
5d9a96ca 2630 register char *locinput = PL_reginput;
5d9a96ca 2631 register I32 nextchr; /* is always set to UCHARAT(locinput) */
24d3c4a9 2632
b69b0499 2633 bool result = 0; /* return value of S_regmatch */
24d3c4a9 2634 int depth = 0; /* depth of backtrack stack */
1a147d38 2635 int nochange_depth = 0; /* depth of GOSUB recursion with nochange*/
77cb431f
DM
2636 regmatch_state *yes_state = NULL; /* state to pop to on success of
2637 subpattern */
e2e6a0f1
YO
2638 /* mark_state piggy backs on the yes_state logic so that when we unwind
2639 the stack on success we can update the mark_state as we go */
2640 regmatch_state *mark_state = NULL; /* last mark state we have seen */
5d458dd8 2641
faec1544 2642 regmatch_state *cur_eval = NULL; /* most recent EVAL_AB state */
b8591aee 2643 struct regmatch_state *cur_curlyx = NULL; /* most recent curlyx */
40a82448 2644 U32 state_num;
5d458dd8
YO
2645 bool no_final = 0; /* prevent failure from backtracking? */
2646 bool do_cutgroup = 0; /* no_final only until next branch/trie entry */
e2e6a0f1 2647 char *startpoint = PL_reginput;
5d458dd8
YO
2648 SV *popmark = NULL; /* are we looking for a mark? */
2649 SV *sv_commit = NULL; /* last mark name seen in failure */
2650 SV *sv_yes_mark = NULL; /* last mark name we have seen
2651 during a successfull match */
2652 U32 lastopen = 0; /* last open we saw */
2653 bool has_cutgroup = RX_HAS_CUTGROUP(rex) ? 1 : 0;
58e23c8d 2654
5d458dd8 2655
24d3c4a9
DM
2656 /* these three flags are set by various ops to signal information to
2657 * the very next op. They have a useful lifetime of exactly one loop
2658 * iteration, and are not preserved or restored by state pushes/pops
2659 */
2660 bool sw = 0; /* the condition value in (?(cond)a|b) */
2661 bool minmod = 0; /* the next "{n,m}" is a "{n,m}?" */
2662 int logical = 0; /* the following EVAL is:
2663 0: (?{...})
2664 1: (?(?{...})X|Y)
2665 2: (??{...})
2666 or the following IFMATCH/UNLESSM is:
2667 false: plain (?=foo)
2668 true: used as a condition: (?(?=foo))
2669 */
2670
95b24440 2671#ifdef DEBUGGING
e68ec53f 2672 GET_RE_DEBUG_FLAGS_DECL;
d6a28714
JH
2673#endif
2674
58e23c8d 2675 DEBUG_OPTIMISE_r( {
24b23f37
YO
2676 PerlIO_printf(Perl_debug_log,"regmatch start\n");
2677 });
5d9a96ca
DM
2678 /* on first ever call to regmatch, allocate first slab */
2679 if (!PL_regmatch_slab) {
2680 Newx(PL_regmatch_slab, 1, regmatch_slab);
2681 PL_regmatch_slab->prev = NULL;
2682 PL_regmatch_slab->next = NULL;
86545054 2683 PL_regmatch_state = SLAB_FIRST(PL_regmatch_slab);
5d9a96ca
DM
2684 }
2685
2686 /* remember current high-water mark for exit */
2687 /* XXX this should be done with SAVE* instead */
2688 orig_slab = PL_regmatch_slab;
2689 orig_state = PL_regmatch_state;
2690
2691 /* grab next free state slot */
2692 st = ++PL_regmatch_state;
86545054 2693 if (st > SLAB_LAST(PL_regmatch_slab))
5d9a96ca
DM
2694 st = PL_regmatch_state = S_push_slab(aTHX);
2695
d6a28714
JH
2696 /* Note that nextchr is a byte even in UTF */
2697 nextchr = UCHARAT(locinput);
2698 scan = prog;
2699 while (scan != NULL) {
8ba1375e 2700
a3621e74 2701 DEBUG_EXECUTE_r( {
6136c704 2702 SV * const prop = sv_newmortal();
1de06328 2703 regnode *rnext=regnext(scan);
786e8c11 2704 DUMP_EXEC_POS( locinput, scan, do_utf8 );
32fc9b6a 2705 regprop(rex, prop, scan);
07be1b83
YO
2706
2707 PerlIO_printf(Perl_debug_log,
2708 "%3"IVdf":%*s%s(%"IVdf")\n",
f8fc2ecf 2709 (IV)(scan - rexi->program), depth*2, "",
07be1b83 2710 SvPVX_const(prop),
1de06328 2711 (PL_regkind[OP(scan)] == END || !rnext) ?
f8fc2ecf 2712 0 : (IV)(rnext - rexi->program));
2a782b5b 2713 });
d6a28714
JH
2714
2715 next = scan + NEXT_OFF(scan);
2716 if (next == scan)
2717 next = NULL;
40a82448 2718 state_num = OP(scan);
d6a28714 2719
40a82448
DM
2720 reenter_switch:
2721 switch (state_num) {
d6a28714 2722 case BOL:
7fba1cd6 2723 if (locinput == PL_bostr)
d6a28714 2724 {
3b0527fe 2725 /* reginfo->till = reginfo->bol; */
b8c5462f
JH
2726 break;
2727 }
d6a28714
JH
2728 sayNO;
2729 case MBOL:
12d33761
HS
2730 if (locinput == PL_bostr ||
2731 ((nextchr || locinput < PL_regeol) && locinput[-1] == '\n'))
d6a28714 2732 {
b8c5462f
JH
2733 break;
2734 }
d6a28714
JH
2735 sayNO;
2736 case SBOL:
c2a73568 2737 if (locinput == PL_bostr)
b8c5462f 2738 break;
d6a28714
JH
2739 sayNO;
2740 case GPOS:
3b0527fe 2741 if (locinput == reginfo->ganch)
d6a28714
JH
2742 break;
2743 sayNO;
ee9b8eae
YO
2744
2745 case KEEPS:
2746 /* update the startpoint */
2747 st->u.keeper.val = PL_regstartp[0];
2748 PL_reginput = locinput;
2749 PL_regstartp[0] = locinput - PL_bostr;
2750 PUSH_STATE_GOTO(KEEPS_next, next);
2751 /*NOT-REACHED*/
2752 case KEEPS_next_fail:
2753 /* rollback the start point change */
2754 PL_regstartp[0] = st->u.keeper.val;
2755 sayNO_SILENT;
2756 /*NOT-REACHED*/
d6a28714 2757 case EOL:
d6a28714
JH
2758 goto seol;
2759 case MEOL:
d6a28714 2760 if ((nextchr || locinput < PL_regeol) && nextchr != '\n')
b8c5462f 2761 sayNO;
b8c5462f 2762 break;
d6a28714
JH
2763 case SEOL:
2764 seol:
2765 if ((nextchr || locinput < PL_regeol) && nextchr != '\n')
b8c5462f 2766 sayNO;
d6a28714 2767 if (PL_regeol - locinput > 1)
b8c5462f 2768 sayNO;
b8c5462f 2769 break;
d6a28714
JH
2770 case EOS:
2771 if (PL_regeol != locinput)
b8c5462f 2772 sayNO;
d6a28714 2773 break;
ffc61ed2 2774 case SANY:
d6a28714 2775 if (!nextchr && locinput >= PL_regeol)
4633a7c4 2776 sayNO;
f33976b4
DB
2777 if (do_utf8) {
2778 locinput += PL_utf8skip[nextchr];
2779 if (locinput > PL_regeol)
2780 sayNO;
2781 nextchr = UCHARAT(locinput);
2782 }
2783 else
2784 nextchr = UCHARAT(++locinput);
2785 break;
2786 case CANY:
2787 if (!nextchr && locinput >= PL_regeol)
2788 sayNO;
b8c5462f 2789 nextchr = UCHARAT(++locinput);
a0d0e21e 2790 break;
ffc61ed2 2791 case REG_ANY:
1aa99e6b
IH
2792 if ((!nextchr && locinput >= PL_regeol) || nextchr == '\n')
2793 sayNO;
2794 if (do_utf8) {
b8c5462f 2795 locinput += PL_utf8skip[nextchr];
d6a28714
JH
2796 if (locinput > PL_regeol)
2797 sayNO;
a0ed51b3 2798 nextchr = UCHARAT(locinput);
a0ed51b3 2799 }
1aa99e6b
IH
2800 else
2801 nextchr = UCHARAT(++locinput);
a0ed51b3 2802 break;
166ba7cd
DM
2803
2804#undef ST
2805#define ST st->u.trie
786e8c11
YO
2806 case TRIEC:
2807 /* In this case the charclass data is available inline so
2808 we can fail fast without a lot of extra overhead.
2809 */
2810 if (scan->flags == EXACT || !do_utf8) {
2811 if(!ANYOF_BITMAP_TEST(scan, *locinput)) {
2812 DEBUG_EXECUTE_r(
2813 PerlIO_printf(Perl_debug_log,
2814 "%*s %sfailed to match trie start class...%s\n",
5bc10b2c 2815 REPORT_CODE_OFF+depth*2, "", PL_colors[4], PL_colors[5])
786e8c11
YO
2816 );
2817 sayNO_SILENT;
2818 /* NOTREACHED */
2819 }
2820 }
2821 /* FALL THROUGH */
5b47454d 2822 case TRIE:
3dab1dad 2823 {
07be1b83 2824 /* what type of TRIE am I? (utf8 makes this contextual) */
3dab1dad
YO
2825 const enum { trie_plain, trie_utf8, trie_utf8_fold }
2826 trie_type = do_utf8 ?
2827 (scan->flags == EXACT ? trie_utf8 : trie_utf8_fold)
2828 : trie_plain;
2829
2830 /* what trie are we using right now */
be8e71aa 2831 reg_trie_data * const trie
f8fc2ecf 2832 = (reg_trie_data*)rexi->data->data[ ARG( scan ) ];
55eed653 2833 HV * widecharmap = (HV *)rexi->data->data[ ARG( scan ) + 1 ];
3dab1dad 2834 U32 state = trie->startstate;
166ba7cd 2835
3dab1dad
YO
2836 if (trie->bitmap && trie_type != trie_utf8_fold &&
2837 !TRIE_BITMAP_TEST(trie,*locinput)
2838 ) {
2839 if (trie->states[ state ].wordnum) {
2840 DEBUG_EXECUTE_r(
2841 PerlIO_printf(Perl_debug_log,
2842 "%*s %smatched empty string...%s\n",
5bc10b2c 2843 REPORT_CODE_OFF+depth*2, "", PL_colors[4], PL_colors[5])
3dab1dad
YO
2844 );
2845 break;
2846 } else {
2847 DEBUG_EXECUTE_r(
2848 PerlIO_printf(Perl_debug_log,
786e8c11 2849 "%*s %sfailed to match trie start class...%s\n",
5bc10b2c 2850 REPORT_CODE_OFF+depth*2, "", PL_colors[4], PL_colors[5])
3dab1dad
YO
2851 );
2852 sayNO_SILENT;
2853 }
2854 }
166ba7cd 2855
786e8c11
YO
2856 {
2857 U8 *uc = ( U8* )locinput;
2858
2859 STRLEN len = 0;
2860 STRLEN foldlen = 0;
2861 U8 *uscan = (U8*)NULL;
2862 STRLEN bufflen=0;
2863 SV *sv_accept_buff = NULL;
2864 U8 foldbuf[ UTF8_MAXBYTES_CASE + 1 ];
2865
2866 ST.accepted = 0; /* how many accepting states we have seen */
2867 ST.B = next;
2868 ST.jump = trie->jump;
786e8c11 2869 ST.me = scan;
786e8c11 2870
07be1b83
YO
2871 /*
2872 traverse the TRIE keeping track of all accepting states
2873 we transition through until we get to a failing node.
2874 */
2875
a3621e74 2876 while ( state && uc <= (U8*)PL_regeol ) {
786e8c11 2877 U32 base = trie->states[ state ].trans.base;
f9f4320a 2878 UV uvc = 0;
786e8c11
YO
2879 U16 charid;
2880 /* We use charid to hold the wordnum as we don't use it
2881 for charid until after we have done the wordnum logic.
2882 We define an alias just so that the wordnum logic reads
2883 more naturally. */
2884
2885#define got_wordnum charid
2886 got_wordnum = trie->states[ state ].wordnum;
2887
2888 if ( got_wordnum ) {
2889 if ( ! ST.accepted ) {
5b47454d
DM
2890 ENTER;
2891 SAVETMPS;
2892 bufflen = TRIE_INITAL_ACCEPT_BUFFLEN;
2893 sv_accept_buff=newSV(bufflen *
2894 sizeof(reg_trie_accepted) - 1);
786e8c11 2895 SvCUR_set(sv_accept_buff, 0);
5b47454d
DM
2896 SvPOK_on(sv_accept_buff);
2897 sv_2mortal(sv_accept_buff);
166ba7cd
DM
2898 SAVETMPS;
2899 ST.accept_buff =
5b47454d
DM
2900 (reg_trie_accepted*)SvPV_nolen(sv_accept_buff );
2901 }
786e8c11 2902 do {
166ba7cd 2903 if (ST.accepted >= bufflen) {
5b47454d 2904 bufflen *= 2;
166ba7cd 2905 ST.accept_buff =(reg_trie_accepted*)
5b47454d
DM
2906 SvGROW(sv_accept_buff,
2907 bufflen * sizeof(reg_trie_accepted));
2908 }
2909 SvCUR_set(sv_accept_buff,SvCUR(sv_accept_buff)
2910 + sizeof(reg_trie_accepted));
a3621e74 2911
786e8c11
YO
2912
2913 ST.accept_buff[ST.accepted].wordnum = got_wordnum;
2914 ST.accept_buff[ST.accepted].endpos = uc;
2915 ++ST.accepted;
2916 } while (trie->nextword && (got_wordnum= trie->nextword[got_wordnum]));
2917 }
2918#undef got_wordnum
a3621e74 2919
07be1b83 2920 DEBUG_TRIE_EXECUTE_r({
786e8c11 2921 DUMP_EXEC_POS( (char *)uc, scan, do_utf8 );
a3621e74 2922 PerlIO_printf( Perl_debug_log,
786e8c11 2923 "%*s %sState: %4"UVxf" Accepted: %4"UVxf" ",
5bc10b2c 2924 2+depth * 2, "", PL_colors[4],
786e8c11 2925 (UV)state, (UV)ST.accepted );
07be1b83 2926 });
a3621e74
YO
2927
2928 if ( base ) {
55eed653
NC
2929 REXEC_TRIE_READ_CHAR(trie_type, trie, widecharmap, uc,
2930 uscan, len, uvc, charid, foldlen,
2931 foldbuf, uniflags);
a3621e74 2932
5b47454d
DM
2933 if (charid &&
2934 (base + charid > trie->uniquecharcount )
2935 && (base + charid - 1 - trie->uniquecharcount
2936 < trie->lasttrans)
2937 && trie->trans[base + charid - 1 -
2938 trie->uniquecharcount].check == state)
2939 {
2940 state = trie->trans[base + charid - 1 -
2941 trie->uniquecharcount ].next;
2942 }
2943 else {
2944 state = 0;
2945 }
2946 uc += len;
2947
2948 }
2949 else {
a3621e74
YO
2950 state = 0;
2951 }
2952 DEBUG_TRIE_EXECUTE_r(
e4584336 2953 PerlIO_printf( Perl_debug_log,
786e8c11 2954 "Charid:%3x CP:%4"UVxf" After State: %4"UVxf"%s\n",
e4584336 2955 charid, uvc, (UV)state, PL_colors[5] );
a3621e74
YO
2956 );
2957 }
166ba7cd 2958 if (!ST.accepted )
a3621e74 2959 sayNO;
a3621e74 2960
166ba7cd
DM
2961 DEBUG_EXECUTE_r(
2962 PerlIO_printf( Perl_debug_log,
2963 "%*s %sgot %"IVdf" possible matches%s\n",
5bc10b2c 2964 REPORT_CODE_OFF + depth * 2, "",
166ba7cd
DM
2965 PL_colors[4], (IV)ST.accepted, PL_colors[5] );
2966 );
786e8c11 2967 }}
166ba7cd
DM
2968
2969 /* FALL THROUGH */
166ba7cd 2970 case TRIE_next_fail: /* we failed - try next alterative */
5d458dd8
YO
2971 if (do_cutgroup) {
2972 do_cutgroup = 0;
2973 no_final = 0;
2974 }
166ba7cd
DM
2975 if ( ST.accepted == 1 ) {
2976 /* only one choice left - just continue */
2977 DEBUG_EXECUTE_r({
2b8b4781
NC
2978 AV *const trie_words
2979 = (AV *) rexi->data->data[ARG(ST.me)+TRIE_WORDS_OFFSET];
2980 SV ** const tmp = av_fetch( trie_words,
5c9f2f80 2981 ST.accept_buff[ 0 ].wordnum-1, 0 );
de734bd5
A
2982 SV *sv= tmp ? sv_newmortal() : NULL;
2983
166ba7cd
DM
2984 PerlIO_printf( Perl_debug_log,
2985 "%*s %sonly one match left: #%d <%s>%s\n",
5bc10b2c 2986 REPORT_CODE_OFF+depth*2, "", PL_colors[4],
166ba7cd 2987 ST.accept_buff[ 0 ].wordnum,
de734bd5
A
2988 tmp ? pv_pretty(sv, SvPV_nolen_const(*tmp), SvCUR(*tmp), 0,
2989 PL_colors[0], PL_colors[1],
2990 (SvUTF8(*tmp) ? PERL_PV_ESCAPE_UNI : 0)
2991 )
2992 : "not compiled under -Dr",
166ba7cd
DM
2993 PL_colors[5] );
2994 });
2995 PL_reginput = (char *)ST.accept_buff[ 0 ].endpos;
2996 /* in this case we free tmps/leave before we call regmatch
2997 as we wont be using accept_buff again. */
5d458dd8 2998
166ba7cd
DM
2999 locinput = PL_reginput;
3000 nextchr = UCHARAT(locinput);
5d458dd8
YO
3001 if ( !ST.jump || !ST.jump[ST.accept_buff[0].wordnum])
3002 scan = ST.B;
3003 else
3004 scan = ST.me + ST.jump[ST.accept_buff[0].wordnum];
3005 if (!has_cutgroup) {
3006 FREETMPS;
3007 LEAVE;
3008 } else {
3009 ST.accepted--;
3010 PUSH_YES_STATE_GOTO(TRIE_next, scan);
3011 }
786e8c11 3012
166ba7cd
DM
3013 continue; /* execute rest of RE */
3014 }
3015
3016 if (!ST.accepted-- ) {
5d458dd8
YO
3017 DEBUG_EXECUTE_r({
3018 PerlIO_printf( Perl_debug_log,
3019 "%*s %sTRIE failed...%s\n",
3020 REPORT_CODE_OFF+depth*2, "",
3021 PL_colors[4],
3022 PL_colors[5] );
3023 });
166ba7cd
DM
3024 FREETMPS;
3025 LEAVE;
5d458dd8 3026 sayNO_SILENT;
166ba7cd
DM
3027 }
3028
a3621e74 3029 /*
166ba7cd
DM
3030 There are at least two accepting states left. Presumably
3031 the number of accepting states is going to be low,
3032 typically two. So we simply scan through to find the one
3033 with lowest wordnum. Once we find it, we swap the last
3034 state into its place and decrement the size. We then try to
3035 match the rest of the pattern at the point where the word
3036 ends. If we succeed, control just continues along the
3037 regex; if we fail we return here to try the next accepting
3038 state
3039 */
a3621e74 3040
166ba7cd
DM
3041 {
3042 U32 best = 0;
3043 U32 cur;
3044 for( cur = 1 ; cur <= ST.accepted ; cur++ ) {
3045 DEBUG_TRIE_EXECUTE_r(
f2278c82 3046 PerlIO_printf( Perl_debug_log,
166ba7cd 3047 "%*s %sgot %"IVdf" (%d) as best, looking at %"IVdf" (%d)%s\n",
5bc10b2c 3048 REPORT_CODE_OFF + depth * 2, "", PL_colors[4],
166ba7cd
DM
3049 (IV)best, ST.accept_buff[ best ].wordnum, (IV)cur,
3050 ST.accept_buff[ cur ].wordnum, PL_colors[5] );
3051 );
3052
3053 if (ST.accept_buff[cur].wordnum <
3054 ST.accept_buff[best].wordnum)
3055 best = cur;
a3621e74 3056 }
166ba7cd
DM
3057
3058 DEBUG_EXECUTE_r({
2b8b4781
NC
3059 AV *const trie_words
3060 = (AV *) rexi->data->data[ARG(ST.me)+TRIE_WORDS_OFFSET];
3061 SV ** const tmp = av_fetch( trie_words,
5c9f2f80 3062 ST.accept_buff[ best ].wordnum - 1, 0 );
7f69552c 3063 regnode *nextop=(!ST.jump || !ST.jump[ST.accept_buff[best].wordnum]) ?
265c4333 3064 ST.B :
7f69552c 3065 ST.me + ST.jump[ST.accept_buff[best].wordnum];
de734bd5
A
3066 SV *sv= tmp ? sv_newmortal() : NULL;
3067
265c4333
YO
3068 PerlIO_printf( Perl_debug_log,
3069 "%*s %strying alternation #%d <%s> at node #%d %s\n",
5bc10b2c 3070 REPORT_CODE_OFF+depth*2, "", PL_colors[4],
166ba7cd 3071 ST.accept_buff[best].wordnum,
de734bd5
A
3072 tmp ? pv_pretty(sv, SvPV_nolen_const(*tmp), SvCUR(*tmp), 0,
3073 PL_colors[0], PL_colors[1],
3074 (SvUTF8(*tmp) ? PERL_PV_ESCAPE_UNI : 0)
3075 ) : "not compiled under -Dr",
265c4333 3076 REG_NODE_NUM(nextop),
166ba7cd
DM
3077 PL_colors[5] );
3078 });
3079
3080 if ( best<ST.accepted ) {
3081 reg_trie_accepted tmp = ST.accept_buff[ best ];
3082 ST.accept_buff[ best ] = ST.accept_buff[ ST.accepted ];
3083 ST.accept_buff[ ST.accepted ] = tmp;
3084 best = ST.accepted;
a3621e74 3085 }
166ba7cd 3086 PL_reginput = (char *)ST.accept_buff[ best ].endpos;
7f69552c 3087 if ( !ST.jump || !ST.jump[ST.accept_buff[best].wordnum]) {
5d458dd8 3088 scan = ST.B;
786e8c11
YO
3089 /* NOTREACHED */
3090 } else {
5d458dd8 3091 scan = ST.me + ST.jump[ST.accept_buff[best].wordnum];
786e8c11
YO
3092 /* NOTREACHED */
3093 }
5d458dd8
YO
3094 if (has_cutgroup) {
3095 PUSH_YES_STATE_GOTO(TRIE_next, scan);
3096 /* NOTREACHED */
3097 } else {
3098 PUSH_STATE_GOTO(TRIE_next, scan);
3099 /* NOTREACHED */
3100 }
786e8c11 3101 /* NOTREACHED */
166ba7cd 3102 }
166ba7cd 3103 /* NOTREACHED */
5d458dd8
YO
3104 case TRIE_next:
3105 FREETMPS;
3106 LEAVE;
3107 sayYES;
166ba7cd
DM
3108#undef ST
3109
95b24440
DM
3110 case EXACT: {
3111 char *s = STRING(scan);
24d3c4a9 3112 ln = STR_LEN(scan);
eb160463 3113 if (do_utf8 != UTF) {
bc517b45 3114 /* The target and the pattern have differing utf8ness. */
1aa99e6b 3115 char *l = locinput;
24d3c4a9 3116 const char * const e = s + ln;
a72c7584 3117
5ff6fc6d
JH
3118 if (do_utf8) {
3119 /* The target is utf8, the pattern is not utf8. */
1aa99e6b 3120 while (s < e) {
a3b680e6 3121 STRLEN ulen;
1aa99e6b 3122 if (l >= PL_regeol)
5ff6fc6d
JH
3123 sayNO;
3124 if (NATIVE_TO_UNI(*(U8*)s) !=
89ebb4a3 3125 utf8n_to_uvuni((U8*)l, UTF8_MAXBYTES, &ulen,
041457d9 3126 uniflags))
5ff6fc6d 3127 sayNO;
bc517b45 3128 l += ulen;
5ff6fc6d 3129 s ++;
1aa99e6b 3130 }
5ff6fc6d
JH
3131 }
3132 else {
3133 /* The target is not utf8, the pattern is utf8. */
1aa99e6b 3134 while (s < e) {
a3b680e6 3135 STRLEN ulen;
1aa99e6b
IH
3136 if (l >= PL_regeol)
3137 sayNO;
5ff6fc6d 3138 if (NATIVE_TO_UNI(*((U8*)l)) !=
89ebb4a3 3139 utf8n_to_uvuni((U8*)s, UTF8_MAXBYTES, &ulen,
041457d9 3140 uniflags))
1aa99e6b 3141 sayNO;
bc517b45 3142 s += ulen;
a72c7584 3143 l ++;
1aa99e6b 3144 }
5ff6fc6d 3145 }
1aa99e6b
IH
3146 locinput = l;
3147 nextchr = UCHARAT(locinput);
3148 break;
3149 }
bc517b45 3150 /* The target and the pattern have the same utf8ness. */
d6a28714
JH
3151 /* Inline the first character, for speed. */
3152 if (UCHARAT(s) != nextchr)
3153 sayNO;
24d3c4a9 3154 if (PL_regeol - locinput < ln)
d6a28714 3155 sayNO;
24d3c4a9 3156 if (ln > 1 && memNE(s, locinput, ln))
d6a28714 3157 sayNO;
24d3c4a9 3158 locinput += ln;
d6a28714
JH
3159 nextchr = UCHARAT(locinput);
3160 break;
95b24440 3161 }
d6a28714 3162 case EXACTFL:
b8c5462f
JH
3163 PL_reg_flags |= RF_tainted;
3164 /* FALL THROUGH */
95b24440 3165 case EXACTF: {
be8e71aa 3166 char * const s = STRING(scan);
24d3c4a9 3167 ln = STR_LEN(scan);
d6a28714 3168
d07ddd77
JH
3169 if (do_utf8 || UTF) {
3170 /* Either target or the pattern are utf8. */
be8e71aa 3171 const char * const l = locinput;
d07ddd77 3172 char *e = PL_regeol;
bc517b45 3173
24d3c4a9 3174 if (ibcmp_utf8(s, 0, ln, (bool)UTF,
1feea2c7 3175 l, &e, 0, do_utf8)) {
5486206c
JH
3176 /* One more case for the sharp s:
3177 * pack("U0U*", 0xDF) =~ /ss/i,
3178 * the 0xC3 0x9F are the UTF-8
3179 * byte sequence for the U+00DF. */
3180 if (!(do_utf8 &&
3181 toLOWER(s[0]) == 's' &&
24d3c4a9 3182 ln >= 2 &&
5486206c
JH
3183 toLOWER(s[1]) == 's' &&
3184 (U8)l[0] == 0xC3 &&
3185 e - l >= 2 &&
3186 (U8)l[1] == 0x9F))
3187 sayNO;
3188 }
d07ddd77
JH
3189 locinput = e;
3190 nextchr = UCHARAT(locinput);
3191 break;
a0ed51b3 3192 }
d6a28714 3193
bc517b45
JH
3194 /* Neither the target and the pattern are utf8. */
3195
d6a28714
JH
3196 /* Inline the first character, for speed. */
3197 if (UCHARAT(s) != nextchr &&
3198 UCHARAT(s) != ((OP(scan) == EXACTF)
3199 ? PL_fold : PL_fold_locale)[nextchr])
a0ed51b3 3200 sayNO;
24d3c4a9 3201 if (PL_regeol - locinput < ln)
b8c5462f 3202 sayNO;
24d3c4a9
DM
3203 if (ln > 1 && (OP(scan) == EXACTF
3204 ? ibcmp(s, locinput, ln)
3205 : ibcmp_locale(s, locinput, ln)))
4633a7c4 3206 sayNO;
24d3c4a9 3207 locinput += ln;
d6a28714 3208 nextchr = UCHARAT(locinput);
a0d0e21e 3209 break;
95b24440 3210 }
d6a28714 3211 case ANYOF:
ffc61ed2 3212 if (do_utf8) {
9e55ce06
JH
3213 STRLEN inclasslen = PL_regeol - locinput;
3214
32fc9b6a 3215 if (!reginclass(rex, scan, (U8*)locinput, &inclasslen, do_utf8))
262b90c4 3216 goto anyof_fail;
ffc61ed2
JH
3217 if (locinput >= PL_regeol)
3218 sayNO;
0f0076b4 3219 locinput += inclasslen ? inclasslen : UTF8SKIP(locinput);
b8c5462f 3220 nextchr = UCHARAT(locinput);
e0f9d4a8 3221 break;
ffc61ed2
JH
3222 }
3223 else {
3224 if (nextchr < 0)
3225 nextchr = UCHARAT(locinput);
32fc9b6a 3226 if (!REGINCLASS(rex, scan, (U8*)locinput))
262b90c4 3227 goto anyof_fail;
ffc61ed2
JH
3228 if (!nextchr && locinput >= PL_regeol)
3229 sayNO;
3230 nextchr = UCHARAT(++locinput);
e0f9d4a8
JH
3231 break;
3232 }
262b90c4 3233 anyof_fail:
e0f9d4a8
JH
3234 /* If we might have the case of the German sharp s
3235 * in a casefolding Unicode character class. */
3236
ebc501f0
JH
3237 if (ANYOF_FOLD_SHARP_S(scan, locinput, PL_regeol)) {
3238 locinput += SHARP_S_SKIP;
e0f9d4a8 3239 nextchr = UCHARAT(locinput);
ffc61ed2 3240 }
e0f9d4a8
JH
3241 else
3242 sayNO;
b8c5462f 3243 break;
d6a28714 3244 case ALNUML:
b8c5462f
JH
3245 PL_reg_flags |= RF_tainted;
3246 /* FALL THROUGH */
d6a28714 3247 case ALNUM:
b8c5462f 3248 if (!nextchr)
4633a7c4 3249 sayNO;
ffc61ed2 3250 if (do_utf8) {
1a4fad37 3251 LOAD_UTF8_CHARCLASS_ALNUM();
ffc61ed2 3252 if (!(OP(scan) == ALNUM
bb7a0f54 3253 ? (bool)swash_fetch(PL_utf8_alnum, (U8*)locinput, do_utf8)
d6a28714 3254 : isALNUM_LC_utf8((U8*)locinput)))
b8c5462f
JH
3255 {
3256 sayNO;
a0ed51b3 3257 }
b8c5462f 3258 locinput += PL_utf8skip[nextchr];
a0ed51b3
LW
3259 nextchr = UCHARAT(locinput);
3260 break;
3261 }
ffc61ed2 3262 if (!(OP(scan) == ALNUM
d6a28714 3263 ? isALNUM(nextchr) : isALNUM_LC(nextchr)))
bbce6d69 3264 sayNO;
b8c5462f 3265 nextchr = UCHARAT(++locinput);
a0d0e21e 3266 break;
d6a28714 3267 case NALNUML:
b8c5462f
JH
3268 PL_reg_flags |= RF_tainted;
3269 /* FALL THROUGH */
d6a28714
JH
3270 case NALNUM:
3271 if (!nextchr && locinput >= PL_regeol)
a0ed51b3 3272 sayNO;
ffc61ed2 3273 if (do_utf8) {
1a4fad37 3274 LOAD_UTF8_CHARCLASS_ALNUM();
ffc61ed2 3275 if (OP(scan) == NALNUM
bb7a0f54 3276 ? (bool)swash_fetch(PL_utf8_alnum, (U8*)locinput, do_utf8)
d6a28714
JH
3277 : isALNUM_LC_utf8((U8*)locinput))
3278 {
b8c5462f 3279 sayNO;
d6a28714 3280 }
b8c5462f
JH
3281 locinput += PL_utf8skip[nextchr];
3282 nextchr = UCHARAT(locinput);
3283 break;
3284 }
ffc61ed2 3285 if (OP(scan) == NALNUM
d6a28714 3286 ? isALNUM(nextchr) : isALNUM_LC(nextchr))
b8c5462f 3287 sayNO;
76e3520e 3288 nextchr = UCHARAT(++locinput);
a0d0e21e 3289 break;
d6a28714
JH
3290 case BOUNDL:
3291 case NBOUNDL:
3280af22 3292 PL_reg_flags |= RF_tainted;
bbce6d69 3293 /* FALL THROUGH */
d6a28714
JH
3294 case BOUND:
3295 case NBOUND:
3296 /* was last char in word? */
ffc61ed2 3297 if (do_utf8) {
12d33761 3298 if (locinput == PL_bostr)
24d3c4a9 3299 ln = '\n';
ffc61ed2 3300 else {
a3b680e6 3301 const U8 * const r = reghop3((U8*)locinput, -1, (U8*)PL_bostr);
9041c2e3 3302
24d3c4a9 3303 ln = utf8n_to_uvchr(r, UTF8SKIP(r), 0, uniflags);
ffc61ed2
JH
3304 }
3305 if (OP(scan) == BOUND || OP(scan) == NBOUND) {
24d3c4a9 3306 ln = isALNUM_uni(ln);
1a4fad37 3307 LOAD_UTF8_CHARCLASS_ALNUM();
3568d838 3308 n = swash_fetch(PL_utf8_alnum, (U8*)locinput, do_utf8);
ffc61ed2
JH
3309 }
3310 else {
24d3c4a9 3311 ln = isALNUM_LC_uvchr(UNI_TO_NATIVE(ln));
ffc61ed2
JH
3312 n = isALNUM_LC_utf8((U8*)locinput);
3313 }
a0ed51b3 3314 }
d6a28714 3315 else {
24d3c4a9 3316 ln = (locinput != PL_bostr) ?
12d33761 3317 UCHARAT(locinput - 1) : '\n';
ffc61ed2 3318 if (OP(scan) == BOUND || OP(scan) == NBOUND) {
24d3c4a9 3319 ln = isALNUM(ln);
ffc61ed2
JH
3320 n = isALNUM(nextchr);
3321 }
3322 else {
24d3c4a9 3323 ln = isALNUM_LC(ln);
ffc61ed2
JH
3324 n = isALNUM_LC(nextchr);
3325 }
d6a28714 3326 }
24d3c4a9 3327 if (((!ln) == (!n)) == (OP(scan) == BOUND ||
ffc61ed2
JH
3328 OP(scan) == BOUNDL))
3329 sayNO;
a0ed51b3 3330 break;
d6a28714 3331 case SPACEL:
3280af22 3332 PL_reg_flags |= RF_tainted;
bbce6d69 3333 /* FALL THROUGH */
d6a28714 3334 case SPACE:
9442cb0e 3335 if (!nextchr)
4633a7c4 3336 sayNO;
1aa99e6b 3337 if (do_utf8) {
fd400ab9 3338 if (UTF8_IS_CONTINUED(nextchr)) {
1a4fad37 3339 LOAD_UTF8_CHARCLASS_SPACE();
ffc61ed2 3340 if (!(OP(scan) == SPACE
bb7a0f54 3341 ? (bool)swash_fetch(PL_utf8_space, (U8*)locinput, do_utf8)
ffc61ed2
JH
3342 : isSPACE_LC_utf8((U8*)locinput)))
3343 {
3344 sayNO;
3345 }
3346 locinput += PL_utf8skip[nextchr];
3347 nextchr = UCHARAT(locinput);
3348 break;
d6a28714 3349 }
ffc61ed2
JH
3350 if (!(OP(scan) == SPACE
3351 ? isSPACE(nextchr) : isSPACE_LC(nextchr)))
3352 sayNO;
3353 nextchr = UCHARAT(++locinput);
3354 }
3355 else {
3356 if (!(OP(scan) == SPACE
3357 ? isSPACE(nextchr) : isSPACE_LC(nextchr)))
3358 sayNO;
3359 nextchr = UCHARAT(++locinput);
a0ed51b3 3360 }
a0ed51b3 3361 break;
d6a28714 3362 case NSPACEL:
3280af22 3363 PL_reg_flags |= RF_tainted;
bbce6d69 3364 /* FALL THROUGH */
d6a28714 3365 case NSPACE:
9442cb0e 3366 if (!nextchr && locinput >= PL_regeol)
b8c5462f 3367 sayNO;
1aa99e6b 3368 if (do_utf8) {
1a4fad37 3369 LOAD_UTF8_CHARCLASS_SPACE();
ffc61ed2 3370 if (OP(scan) == NSPACE
bb7a0f54 3371 ? (bool)swash_fetch(PL_utf8_space, (U8*)locinput, do_utf8)
d6a28714 3372 : isSPACE_LC_utf8((U8*)locinput))
b8c5462f
JH
3373 {
3374 sayNO;
3375 }
3376 locinput += PL_utf8skip[nextchr];
3377 nextchr = UCHARAT(locinput);
3378 break;
a0ed51b3 3379 }
ffc61ed2 3380 if (OP(scan) == NSPACE
d6a28714 3381 ? isSPACE(nextchr) : isSPACE_LC(nextchr))
4633a7c4 3382 sayNO;
76e3520e 3383 nextchr = UCHARAT(++locinput);
a0d0e21e 3384 break;
d6a28714 3385 case DIGITL:
a0ed51b3
LW
3386 PL_reg_flags |= RF_tainted;
3387 /* FALL THROUGH */
d6a28714 3388 case DIGIT:
9442cb0e 3389 if (!nextchr)
a0ed51b3 3390 sayNO;
1aa99e6b 3391 if (do_utf8) {
1a4fad37 3392 LOAD_UTF8_CHARCLASS_DIGIT();
ffc61ed2 3393 if (!(OP(scan) == DIGIT
bb7a0f54 3394 ? (bool)swash_fetch(PL_utf8_digit, (U8*)locinput, do_utf8)
9442cb0e 3395 : isDIGIT_LC_utf8((U8*)locinput)))
dfe13c55 3396 {
a0ed51b3 3397 sayNO;
dfe13c55 3398 }
6f06b55f 3399 locinput += PL_utf8skip[nextchr];