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