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