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