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