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