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