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