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