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