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