This is a live mirror of the Perl 5 development currently hosted at https://github.com/perl/perl5
reginclass: Remove unnecessary test
[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) {
4cadc6a9 1362 REXEC_FBC_UTF8_CLASS_SCAN((ANYOF_FLAGS(c) & ANYOF_UNICODE) ||
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 }
1783 );
1784 while ( uc <= (U8*)last_start && !BITMAP_TEST(bitmap,*uc) ) {
1785 uc++;
786e8c11 1786 }
1de06328 1787 s= (char *)uc;
786e8c11 1788 }
786e8c11
YO
1789 if (uc >(U8*)last_start) break;
1790 }
1791
1792 if ( word ) {
2e64971a 1793 U8 *lpos= points[ (pointpos - trie->wordinfo[word].len) % maxlen ];
786e8c11
YO
1794 if (!leftmost || lpos < leftmost) {
1795 DEBUG_r(accepted_word=word);
07be1b83 1796 leftmost= lpos;
786e8c11 1797 }
07be1b83 1798 if (base==0) break;
786e8c11 1799
07be1b83
YO
1800 }
1801 points[pointpos++ % maxlen]= uc;
55eed653
NC
1802 REXEC_TRIE_READ_CHAR(trie_type, trie, widecharmap, uc,
1803 uscan, len, uvc, charid, foldlen,
1804 foldbuf, uniflags);
786e8c11
YO
1805 DEBUG_TRIE_EXECUTE_r({
1806 dump_exec_pos( (char *)uc, c, strend, real_start,
f2ed9b32 1807 s, utf8_target );
07be1b83 1808 PerlIO_printf(Perl_debug_log,
786e8c11
YO
1809 " Charid:%3u CP:%4"UVxf" ",
1810 charid, uvc);
1811 });
07be1b83
YO
1812
1813 do {
6148ee25 1814#ifdef DEBUGGING
786e8c11 1815 word = aho->states[ state ].wordnum;
6148ee25 1816#endif
07be1b83
YO
1817 base = aho->states[ state ].trans.base;
1818
786e8c11
YO
1819 DEBUG_TRIE_EXECUTE_r({
1820 if (failed)
1821 dump_exec_pos( (char *)uc, c, strend, real_start,
f2ed9b32 1822 s, utf8_target );
07be1b83 1823 PerlIO_printf( Perl_debug_log,
786e8c11
YO
1824 "%sState: %4"UVxf", word=%"UVxf,
1825 failed ? " Fail transition to " : "",
1826 (UV)state, (UV)word);
1827 });
07be1b83
YO
1828 if ( base ) {
1829 U32 tmp;
6dd2be57 1830 I32 offset;
07be1b83 1831 if (charid &&
6dd2be57
DM
1832 ( ((offset = base + charid
1833 - 1 - trie->uniquecharcount)) >= 0)
1834 && ((U32)offset < trie->lasttrans)
1835 && trie->trans[offset].check == state
1836 && (tmp=trie->trans[offset].next))
07be1b83 1837 {
786e8c11
YO
1838 DEBUG_TRIE_EXECUTE_r(
1839 PerlIO_printf( Perl_debug_log," - legal\n"));
07be1b83
YO
1840 state = tmp;
1841 break;
1842 }
1843 else {
786e8c11
YO
1844 DEBUG_TRIE_EXECUTE_r(
1845 PerlIO_printf( Perl_debug_log," - fail\n"));
1846 failed = 1;
1847 state = aho->fail[state];
07be1b83
YO
1848 }
1849 }
1850 else {
1851 /* we must be accepting here */
786e8c11
YO
1852 DEBUG_TRIE_EXECUTE_r(
1853 PerlIO_printf( Perl_debug_log," - accepting\n"));
1854 failed = 1;
07be1b83
YO
1855 break;
1856 }
1857 } while(state);
786e8c11 1858 uc += len;
07be1b83
YO
1859 if (failed) {
1860 if (leftmost)
1861 break;
786e8c11 1862 if (!state) state = 1;
07be1b83
YO
1863 }
1864 }
1865 if ( aho->states[ state ].wordnum ) {
2e64971a 1866 U8 *lpos = points[ (pointpos - trie->wordinfo[aho->states[ state ].wordnum].len) % maxlen ];
786e8c11
YO
1867 if (!leftmost || lpos < leftmost) {
1868 DEBUG_r(accepted_word=aho->states[ state ].wordnum);
07be1b83 1869 leftmost = lpos;
786e8c11 1870 }
07be1b83 1871 }
07be1b83
YO
1872 if (leftmost) {
1873 s = (char*)leftmost;
786e8c11
YO
1874 DEBUG_TRIE_EXECUTE_r({
1875 PerlIO_printf(
70685ca0
JH
1876 Perl_debug_log,"Matches word #%"UVxf" at position %"IVdf". Trying full pattern...\n",
1877 (UV)accepted_word, (IV)(s - real_start)
786e8c11
YO
1878 );
1879 });
24b23f37 1880 if (!reginfo || regtry(reginfo, &s)) {
be8e71aa
YO
1881 FREETMPS;
1882 LEAVE;
07be1b83 1883 goto got_it;
be8e71aa 1884 }
07be1b83 1885 s = HOPc(s,1);
786e8c11
YO
1886 DEBUG_TRIE_EXECUTE_r({
1887 PerlIO_printf( Perl_debug_log,"Pattern failed. Looking for new start point...\n");
1888 });
07be1b83 1889 } else {
786e8c11
YO
1890 DEBUG_TRIE_EXECUTE_r(
1891 PerlIO_printf( Perl_debug_log,"No match.\n"));
07be1b83
YO
1892 break;
1893 }
1894 }
be8e71aa
YO
1895 FREETMPS;
1896 LEAVE;
07be1b83
YO
1897 }
1898 break;
b3c9acc1 1899 default:
3c3eec57
GS
1900 Perl_croak(aTHX_ "panic: unknown regstclass %d", (int)OP(c));
1901 break;
d6a28714 1902 }
6eb5f6b9
JH
1903 return 0;
1904 got_it:
1905 return s;
1906}
1907
fae667d5 1908
6eb5f6b9
JH
1909/*
1910 - regexec_flags - match a regexp against a string
1911 */
1912I32
288b8c02 1913Perl_regexec_flags(pTHX_ REGEXP * const rx, char *stringarg, register char *strend,
6eb5f6b9
JH
1914 char *strbeg, I32 minend, SV *sv, void *data, U32 flags)
1915/* strend: pointer to null at end of string */
1916/* strbeg: real beginning of string */
1917/* minend: end of match must be >=minend after stringarg. */
58e23c8d
YO
1918/* data: May be used for some additional optimizations.
1919 Currently its only used, with a U32 cast, for transmitting
1920 the ganch offset when doing a /g match. This will change */
6eb5f6b9
JH
1921/* nosave: For optimizations. */
1922{
97aff369 1923 dVAR;
288b8c02 1924 struct regexp *const prog = (struct regexp *)SvANY(rx);
24b23f37 1925 /*register*/ char *s;
6eb5f6b9 1926 register regnode *c;
24b23f37 1927 /*register*/ char *startpos = stringarg;
6eb5f6b9
JH
1928 I32 minlen; /* must match at least this many chars */
1929 I32 dontbother = 0; /* how many characters not to try at end */
6eb5f6b9
JH
1930 I32 end_shift = 0; /* Same for the end. */ /* CC */
1931 I32 scream_pos = -1; /* Internal iterator of scream. */
ccac19ea 1932 char *scream_olds = NULL;
f2ed9b32 1933 const bool utf8_target = cBOOL(DO_UTF8(sv));
2757e526 1934 I32 multiline;
f8fc2ecf 1935 RXi_GET_DECL(prog,progi);
3b0527fe 1936 regmatch_info reginfo; /* create some info to pass to regtry etc */
e9105d30 1937 regexp_paren_pair *swap = NULL;
a3621e74
YO
1938 GET_RE_DEBUG_FLAGS_DECL;
1939
7918f24d 1940 PERL_ARGS_ASSERT_REGEXEC_FLAGS;
9d4ba2ae 1941 PERL_UNUSED_ARG(data);
6eb5f6b9
JH
1942
1943 /* Be paranoid... */
1944 if (prog == NULL || startpos == NULL) {
1945 Perl_croak(aTHX_ "NULL regexp parameter");
1946 return 0;
1947 }
1948
bbe252da 1949 multiline = prog->extflags & RXf_PMf_MULTILINE;
288b8c02 1950 reginfo.prog = rx; /* Yes, sorry that this is confusing. */
2757e526 1951
f2ed9b32 1952 RX_MATCH_UTF8_set(rx, utf8_target);
1de06328 1953 DEBUG_EXECUTE_r(
f2ed9b32 1954 debug_start_match(rx, utf8_target, startpos, strend,
1de06328
YO
1955 "Matching");
1956 );
bac06658 1957
6eb5f6b9 1958 minlen = prog->minlen;
1de06328
YO
1959
1960 if (strend - startpos < (minlen+(prog->check_offset_min<0?prog->check_offset_min:0))) {
a3621e74 1961 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log,
a72c7584
JH
1962 "String too short [regexec_flags]...\n"));
1963 goto phooey;
1aa99e6b 1964 }
6eb5f6b9 1965
1de06328 1966
6eb5f6b9 1967 /* Check validity of program. */
f8fc2ecf 1968 if (UCHARAT(progi->program) != REG_MAGIC) {
6eb5f6b9
JH
1969 Perl_croak(aTHX_ "corrupted regexp program");
1970 }
1971
1972 PL_reg_flags = 0;
1973 PL_reg_eval_set = 0;
1974 PL_reg_maxiter = 0;
1975
3c8556c3 1976 if (RX_UTF8(rx))
6eb5f6b9
JH
1977 PL_reg_flags |= RF_utf8;
1978
1979 /* Mark beginning of line for ^ and lookbehind. */
3b0527fe 1980 reginfo.bol = startpos; /* XXX not used ??? */
6eb5f6b9 1981 PL_bostr = strbeg;
3b0527fe 1982 reginfo.sv = sv;
6eb5f6b9
JH
1983
1984 /* Mark end of line for $ (and such) */
1985 PL_regeol = strend;
1986
1987 /* see how far we have to get to not match where we matched before */
3b0527fe 1988 reginfo.till = startpos+minend;
6eb5f6b9 1989
6eb5f6b9
JH
1990 /* If there is a "must appear" string, look for it. */
1991 s = startpos;
1992
bbe252da 1993 if (prog->extflags & RXf_GPOS_SEEN) { /* Need to set reginfo->ganch */
6eb5f6b9 1994 MAGIC *mg;
2c296965 1995 if (flags & REXEC_IGNOREPOS){ /* Means: check only at start */
58e23c8d 1996 reginfo.ganch = startpos + prog->gofs;
2c296965 1997 DEBUG_GPOS_r(PerlIO_printf(Perl_debug_log,
ed549f2e 1998 "GPOS IGNOREPOS: reginfo.ganch = startpos + %"UVxf"\n",(UV)prog->gofs));
2c296965 1999 } else if (sv && SvTYPE(sv) >= SVt_PVMG
6eb5f6b9 2000 && SvMAGIC(sv)
14befaf4
DM
2001 && (mg = mg_find(sv, PERL_MAGIC_regex_global))
2002 && mg->mg_len >= 0) {
3b0527fe 2003 reginfo.ganch = strbeg + mg->mg_len; /* Defined pos() */
2c296965 2004 DEBUG_GPOS_r(PerlIO_printf(Perl_debug_log,
ed549f2e 2005 "GPOS MAGIC: reginfo.ganch = strbeg + %"IVdf"\n",(IV)mg->mg_len));
2c296965 2006
bbe252da 2007 if (prog->extflags & RXf_ANCH_GPOS) {
3b0527fe 2008 if (s > reginfo.ganch)
6eb5f6b9 2009 goto phooey;
58e23c8d 2010 s = reginfo.ganch - prog->gofs;
2c296965 2011 DEBUG_GPOS_r(PerlIO_printf(Perl_debug_log,
ed549f2e 2012 "GPOS ANCH_GPOS: s = ganch - %"UVxf"\n",(UV)prog->gofs));
c584a96e
YO
2013 if (s < strbeg)
2014 goto phooey;
6eb5f6b9
JH
2015 }
2016 }
58e23c8d 2017 else if (data) {
70685ca0 2018 reginfo.ganch = strbeg + PTR2UV(data);
2c296965
YO
2019 DEBUG_GPOS_r(PerlIO_printf(Perl_debug_log,
2020 "GPOS DATA: reginfo.ganch= strbeg + %"UVxf"\n",PTR2UV(data)));
2021
2022 } else { /* pos() not defined */
3b0527fe 2023 reginfo.ganch = strbeg;
2c296965
YO
2024 DEBUG_GPOS_r(PerlIO_printf(Perl_debug_log,
2025 "GPOS: reginfo.ganch = strbeg\n"));
2026 }
6eb5f6b9 2027 }
288b8c02 2028 if (PL_curpm && (PM_GETRE(PL_curpm) == rx)) {
e9105d30
GG
2029 /* We have to be careful. If the previous successful match
2030 was from this regex we don't want a subsequent partially
2031 successful match to clobber the old results.
2032 So when we detect this possibility we add a swap buffer
2033 to the re, and switch the buffer each match. If we fail
2034 we switch it back, otherwise we leave it swapped.
2035 */
2036 swap = prog->offs;
2037 /* do we need a save destructor here for eval dies? */
2038 Newxz(prog->offs, (prog->nparens + 1), regexp_paren_pair);
c74340f9 2039 }
a0714e2c 2040 if (!(flags & REXEC_CHECKED) && (prog->check_substr != NULL || prog->check_utf8 != NULL)) {
6eb5f6b9
JH
2041 re_scream_pos_data d;
2042
2043 d.scream_olds = &scream_olds;
2044 d.scream_pos = &scream_pos;
288b8c02 2045 s = re_intuit_start(rx, sv, s, strend, flags, &d);
3fa9c3d7 2046 if (!s) {
a3621e74 2047 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "Not present...\n"));
6eb5f6b9 2048 goto phooey; /* not present */
3fa9c3d7 2049 }
6eb5f6b9
JH
2050 }
2051
1de06328 2052
6eb5f6b9
JH
2053
2054 /* Simplest case: anchored match need be tried only once. */
2055 /* [unless only anchor is BOL and multiline is set] */
bbe252da 2056 if (prog->extflags & (RXf_ANCH & ~RXf_ANCH_GPOS)) {
24b23f37 2057 if (s == startpos && regtry(&reginfo, &startpos))
6eb5f6b9 2058 goto got_it;
bbe252da
YO
2059 else if (multiline || (prog->intflags & PREGf_IMPLICIT)
2060 || (prog->extflags & RXf_ANCH_MBOL)) /* XXXX SBOL? */
6eb5f6b9
JH
2061 {
2062 char *end;
2063
2064 if (minlen)
2065 dontbother = minlen - 1;
1aa99e6b 2066 end = HOP3c(strend, -dontbother, strbeg) - 1;
6eb5f6b9 2067 /* for multiline we only have to try after newlines */
33b8afdf 2068 if (prog->check_substr || prog->check_utf8) {
92f3d482
YO
2069 /* because of the goto we can not easily reuse the macros for bifurcating the
2070 unicode/non-unicode match modes here like we do elsewhere - demerphq */
2071 if (utf8_target) {
2072 if (s == startpos)
2073 goto after_try_utf8;
2074 while (1) {
2075 if (regtry(&reginfo, &s)) {
2076 goto got_it;
2077 }
2078 after_try_utf8:
2079 if (s > end) {
2080 goto phooey;
2081 }
2082 if (prog->extflags & RXf_USE_INTUIT) {
2083 s = re_intuit_start(rx, sv, s + UTF8SKIP(s), strend, flags, NULL);
2084 if (!s) {
2085 goto phooey;
2086 }
2087 }
2088 else {
2089 s += UTF8SKIP(s);
2090 }
2091 }
2092 } /* end search for check string in unicode */
2093 else {
2094 if (s == startpos) {
2095 goto after_try_latin;
2096 }
2097 while (1) {
2098 if (regtry(&reginfo, &s)) {
2099 goto got_it;
2100 }
2101 after_try_latin:
2102 if (s > end) {
2103 goto phooey;
2104 }
2105 if (prog->extflags & RXf_USE_INTUIT) {
2106 s = re_intuit_start(rx, sv, s + 1, strend, flags, NULL);
2107 if (!s) {
2108 goto phooey;
2109 }
2110 }
2111 else {
2112 s++;
2113 }
2114 }
2115 } /* end search for check string in latin*/
2116 } /* end search for check string */
2117 else { /* search for newline */
2118 if (s > startpos) {
2119 /*XXX: The s-- is almost definitely wrong here under unicode - demeprhq*/
6eb5f6b9 2120 s--;
92f3d482
YO
2121 }
2122 /* We can use a more efficient search as newlines are the same in unicode as they are in latin */
6eb5f6b9
JH
2123 while (s < end) {
2124 if (*s++ == '\n') { /* don't need PL_utf8skip here */
24b23f37 2125 if (regtry(&reginfo, &s))
6eb5f6b9
JH
2126 goto got_it;
2127 }
92f3d482
YO
2128 }
2129 } /* end search for newline */
2130 } /* end anchored/multiline check string search */
6eb5f6b9 2131 goto phooey;
bbe252da 2132 } else if (RXf_GPOS_CHECK == (prog->extflags & RXf_GPOS_CHECK))
f9f4320a
YO
2133 {
2134 /* the warning about reginfo.ganch being used without intialization
bbe252da 2135 is bogus -- we set it above, when prog->extflags & RXf_GPOS_SEEN
f9f4320a 2136 and we only enter this block when the same bit is set. */
58e23c8d 2137 char *tmp_s = reginfo.ganch - prog->gofs;
c584a96e
YO
2138
2139 if (tmp_s >= strbeg && regtry(&reginfo, &tmp_s))
6eb5f6b9
JH
2140 goto got_it;
2141 goto phooey;
2142 }
2143
2144 /* Messy cases: unanchored match. */
bbe252da 2145 if ((prog->anchored_substr || prog->anchored_utf8) && prog->intflags & PREGf_SKIP) {
6eb5f6b9 2146 /* we have /x+whatever/ */
f2ed9b32 2147 /* it must be a one character string (XXXX Except UTF_PATTERN?) */
33b8afdf 2148 char ch;
bf93d4cc
GS
2149#ifdef DEBUGGING
2150 int did_match = 0;
2151#endif
f2ed9b32
KW
2152 if (!(utf8_target ? prog->anchored_utf8 : prog->anchored_substr))
2153 utf8_target ? to_utf8_substr(prog) : to_byte_substr(prog);
2154 ch = SvPVX_const(utf8_target ? prog->anchored_utf8 : prog->anchored_substr)[0];
bf93d4cc 2155
f2ed9b32 2156 if (utf8_target) {
4cadc6a9 2157 REXEC_FBC_SCAN(
6eb5f6b9 2158 if (*s == ch) {
a3621e74 2159 DEBUG_EXECUTE_r( did_match = 1 );
24b23f37 2160 if (regtry(&reginfo, &s)) goto got_it;
6eb5f6b9
JH
2161 s += UTF8SKIP(s);
2162 while (s < strend && *s == ch)
2163 s += UTF8SKIP(s);
2164 }
4cadc6a9 2165 );
6eb5f6b9
JH
2166 }
2167 else {
4cadc6a9 2168 REXEC_FBC_SCAN(
6eb5f6b9 2169 if (*s == ch) {
a3621e74 2170 DEBUG_EXECUTE_r( did_match = 1 );
24b23f37 2171 if (regtry(&reginfo, &s)) goto got_it;
6eb5f6b9
JH
2172 s++;
2173 while (s < strend && *s == ch)
2174 s++;
2175 }
4cadc6a9 2176 );
6eb5f6b9 2177 }
a3621e74 2178 DEBUG_EXECUTE_r(if (!did_match)
bf93d4cc 2179 PerlIO_printf(Perl_debug_log,
b7953727
JH
2180 "Did not find anchored character...\n")
2181 );
6eb5f6b9 2182 }
a0714e2c
SS
2183 else if (prog->anchored_substr != NULL
2184 || prog->anchored_utf8 != NULL
2185 || ((prog->float_substr != NULL || prog->float_utf8 != NULL)
33b8afdf
JH
2186 && prog->float_max_offset < strend - s)) {
2187 SV *must;
2188 I32 back_max;
2189 I32 back_min;
2190 char *last;
6eb5f6b9 2191 char *last1; /* Last position checked before */
bf93d4cc
GS
2192#ifdef DEBUGGING
2193 int did_match = 0;
2194#endif
33b8afdf 2195 if (prog->anchored_substr || prog->anchored_utf8) {
f2ed9b32
KW
2196 if (!(utf8_target ? prog->anchored_utf8 : prog->anchored_substr))
2197 utf8_target ? to_utf8_substr(prog) : to_byte_substr(prog);
2198 must = utf8_target ? prog->anchored_utf8 : prog->anchored_substr;
33b8afdf
JH
2199 back_max = back_min = prog->anchored_offset;
2200 } else {
f2ed9b32
KW
2201 if (!(utf8_target ? prog->float_utf8 : prog->float_substr))
2202 utf8_target ? to_utf8_substr(prog) : to_byte_substr(prog);
2203 must = utf8_target ? prog->float_utf8 : prog->float_substr;
33b8afdf
JH
2204 back_max = prog->float_max_offset;
2205 back_min = prog->float_min_offset;
2206 }
1de06328
YO
2207
2208
33b8afdf
JH
2209 if (must == &PL_sv_undef)
2210 /* could not downgrade utf8 check substring, so must fail */
2211 goto phooey;
2212
1de06328
YO
2213 if (back_min<0) {
2214 last = strend;
2215 } else {
2216 last = HOP3c(strend, /* Cannot start after this */
2217 -(I32)(CHR_SVLEN(must)
2218 - (SvTAIL(must) != 0) + back_min), strbeg);
2219 }
6eb5f6b9
JH
2220 if (s > PL_bostr)
2221 last1 = HOPc(s, -1);
2222 else
2223 last1 = s - 1; /* bogus */
2224
a0288114 2225 /* XXXX check_substr already used to find "s", can optimize if
6eb5f6b9
JH
2226 check_substr==must. */
2227 scream_pos = -1;
2228 dontbother = end_shift;
2229 strend = HOPc(strend, -dontbother);
2230 while ( (s <= last) &&
9041c2e3 2231 ((flags & REXEC_SCREAM)
1de06328 2232 ? (s = screaminstr(sv, must, HOP3c(s, back_min, (back_min<0 ? strbeg : strend)) - strbeg,
6eb5f6b9 2233 end_shift, &scream_pos, 0))
1de06328 2234 : (s = fbm_instr((unsigned char*)HOP3(s, back_min, (back_min<0 ? strbeg : strend)),
9041c2e3 2235 (unsigned char*)strend, must,
7fba1cd6 2236 multiline ? FBMrf_MULTILINE : 0))) ) {
4addbd3b 2237 /* we may be pointing at the wrong string */
07bc277f 2238 if ((flags & REXEC_SCREAM) && RXp_MATCH_COPIED(prog))
3f7c398e 2239 s = strbeg + (s - SvPVX_const(sv));
a3621e74 2240 DEBUG_EXECUTE_r( did_match = 1 );
6eb5f6b9
JH
2241 if (HOPc(s, -back_max) > last1) {
2242 last1 = HOPc(s, -back_min);
2243 s = HOPc(s, -back_max);
2244 }
2245 else {
52657f30 2246 char * const t = (last1 >= PL_bostr) ? HOPc(last1, 1) : last1 + 1;
6eb5f6b9
JH
2247
2248 last1 = HOPc(s, -back_min);
52657f30 2249 s = t;
6eb5f6b9 2250 }
f2ed9b32 2251 if (utf8_target) {
6eb5f6b9 2252 while (s <= last1) {
24b23f37 2253 if (regtry(&reginfo, &s))
6eb5f6b9
JH
2254 goto got_it;
2255 s += UTF8SKIP(s);
2256 }
2257 }
2258 else {
2259 while (s <= last1) {
24b23f37 2260 if (regtry(&reginfo, &s))
6eb5f6b9
JH
2261 goto got_it;
2262 s++;
2263 }
2264 }
2265 }
ab3bbdeb 2266 DEBUG_EXECUTE_r(if (!did_match) {
f2ed9b32 2267 RE_PV_QUOTED_DECL(quoted, utf8_target, PERL_DEBUG_PAD_ZERO(0),
ab3bbdeb
YO
2268 SvPVX_const(must), RE_SV_DUMPLEN(must), 30);
2269 PerlIO_printf(Perl_debug_log, "Did not find %s substr %s%s...\n",
33b8afdf 2270 ((must == prog->anchored_substr || must == prog->anchored_utf8)
bf93d4cc 2271 ? "anchored" : "floating"),
ab3bbdeb
YO
2272 quoted, RE_SV_TAIL(must));
2273 });
6eb5f6b9
JH
2274 goto phooey;
2275 }
f8fc2ecf 2276 else if ( (c = progi->regstclass) ) {
f14c76ed 2277 if (minlen) {
f8fc2ecf 2278 const OPCODE op = OP(progi->regstclass);
66e933ab 2279 /* don't bother with what can't match */
786e8c11 2280 if (PL_regkind[op] != EXACT && op != CANY && PL_regkind[op] != TRIE)
f14c76ed
RGS
2281 strend = HOPc(strend, -(minlen - 1));
2282 }
a3621e74 2283 DEBUG_EXECUTE_r({
be8e71aa 2284 SV * const prop = sv_newmortal();
32fc9b6a 2285 regprop(prog, prop, c);
0df25f3d 2286 {
f2ed9b32 2287 RE_PV_QUOTED_DECL(quoted,utf8_target,PERL_DEBUG_PAD_ZERO(1),
ab3bbdeb 2288 s,strend-s,60);
0df25f3d 2289 PerlIO_printf(Perl_debug_log,
1c8f8eb1 2290 "Matching stclass %.*s against %s (%d bytes)\n",
e4f74956 2291 (int)SvCUR(prop), SvPVX_const(prop),
ab3bbdeb 2292 quoted, (int)(strend - s));
0df25f3d 2293 }
ffc61ed2 2294 });
3b0527fe 2295 if (find_byclass(prog, c, s, strend, &reginfo))
6eb5f6b9 2296 goto got_it;
07be1b83 2297 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "Contradicts stclass... [regexec_flags]\n"));
d6a28714
JH
2298 }
2299 else {
2300 dontbother = 0;
a0714e2c 2301 if (prog->float_substr != NULL || prog->float_utf8 != NULL) {
33b8afdf 2302 /* Trim the end. */
d6a28714 2303 char *last;
33b8afdf
JH
2304 SV* float_real;
2305
f2ed9b32
KW
2306 if (!(utf8_target ? prog->float_utf8 : prog->float_substr))
2307 utf8_target ? to_utf8_substr(prog) : to_byte_substr(prog);
2308 float_real = utf8_target ? prog->float_utf8 : prog->float_substr;
d6a28714
JH
2309
2310 if (flags & REXEC_SCREAM) {
33b8afdf 2311 last = screaminstr(sv, float_real, s - strbeg,
d6a28714
JH
2312 end_shift, &scream_pos, 1); /* last one */
2313 if (!last)
ffc61ed2 2314 last = scream_olds; /* Only one occurrence. */
4addbd3b 2315 /* we may be pointing at the wrong string */
07bc277f 2316 else if (RXp_MATCH_COPIED(prog))
3f7c398e 2317 s = strbeg + (s - SvPVX_const(sv));
b8c5462f 2318 }
d6a28714
JH
2319 else {
2320 STRLEN len;
cfd0369c 2321 const char * const little = SvPV_const(float_real, len);
d6a28714 2322
33b8afdf 2323 if (SvTAIL(float_real)) {
d6a28714
JH
2324 if (memEQ(strend - len + 1, little, len - 1))
2325 last = strend - len + 1;
7fba1cd6 2326 else if (!multiline)
9041c2e3 2327 last = memEQ(strend - len, little, len)
bd61b366 2328 ? strend - len : NULL;
b8c5462f 2329 else
d6a28714
JH
2330 goto find_last;
2331 } else {
2332 find_last:
9041c2e3 2333 if (len)
d6a28714 2334 last = rninstr(s, strend, little, little + len);
b8c5462f 2335 else
a0288114 2336 last = strend; /* matching "$" */
b8c5462f 2337 }
b8c5462f 2338 }
bf93d4cc 2339 if (last == NULL) {
6bda09f9
YO
2340 DEBUG_EXECUTE_r(
2341 PerlIO_printf(Perl_debug_log,
2342 "%sCan't trim the tail, match fails (should not happen)%s\n",
2343 PL_colors[4], PL_colors[5]));
bf93d4cc
GS
2344 goto phooey; /* Should not happen! */
2345 }
d6a28714
JH
2346 dontbother = strend - last + prog->float_min_offset;
2347 }
2348 if (minlen && (dontbother < minlen))
2349 dontbother = minlen - 1;
2350 strend -= dontbother; /* this one's always in bytes! */
2351 /* We don't know much -- general case. */
f2ed9b32 2352 if (utf8_target) {
d6a28714 2353 for (;;) {
24b23f37 2354 if (regtry(&reginfo, &s))
d6a28714
JH
2355 goto got_it;
2356 if (s >= strend)
2357 break;
b8c5462f 2358 s += UTF8SKIP(s);
d6a28714
JH
2359 };
2360 }
2361 else {
2362 do {
24b23f37 2363 if (regtry(&reginfo, &s))
d6a28714
JH
2364 goto got_it;
2365 } while (s++ < strend);
2366 }
2367 }
2368
2369 /* Failure. */
2370 goto phooey;
2371
2372got_it:
e9105d30 2373 Safefree(swap);
288b8c02 2374 RX_MATCH_TAINTED_set(rx, PL_reg_flags & RF_tainted);
d6a28714 2375
19b95bf0 2376 if (PL_reg_eval_set)
4f639d21 2377 restore_pos(aTHX_ prog);
5daac39c
NC
2378 if (RXp_PAREN_NAMES(prog))
2379 (void)hv_iterinit(RXp_PAREN_NAMES(prog));
d6a28714
JH
2380
2381 /* make sure $`, $&, $', and $digit will work later */
2382 if ( !(flags & REXEC_NOT_FIRST) ) {
288b8c02 2383 RX_MATCH_COPY_FREE(rx);
d6a28714 2384 if (flags & REXEC_COPY_STR) {
be8e71aa 2385 const I32 i = PL_regeol - startpos + (stringarg - strbeg);
f8c7b90f 2386#ifdef PERL_OLD_COPY_ON_WRITE
ed252734
NC
2387 if ((SvIsCOW(sv)
2388 || (SvFLAGS(sv) & CAN_COW_MASK) == CAN_COW_FLAGS)) {
2389 if (DEBUG_C_TEST) {
2390 PerlIO_printf(Perl_debug_log,
2391 "Copy on write: regexp capture, type %d\n",
2392 (int) SvTYPE(sv));
2393 }
2394 prog->saved_copy = sv_setsv_cow(prog->saved_copy, sv);
d5263905 2395 prog->subbeg = (char *)SvPVX_const(prog->saved_copy);
ed252734
NC
2396 assert (SvPOKp(prog->saved_copy));
2397 } else
2398#endif
2399 {
288b8c02 2400 RX_MATCH_COPIED_on(rx);
ed252734
NC
2401 s = savepvn(strbeg, i);
2402 prog->subbeg = s;
2403 }
d6a28714 2404 prog->sublen = i;
d6a28714
JH
2405 }
2406 else {
2407 prog->subbeg = strbeg;
2408 prog->sublen = PL_regeol - strbeg; /* strend may have been modified */
2409 }
2410 }
9041c2e3 2411
d6a28714
JH
2412 return 1;
2413
2414phooey:
a3621e74 2415 DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "%sMatch failed%s\n",
e4584336 2416 PL_colors[4], PL_colors[5]));
d6a28714 2417 if (PL_reg_eval_set)
4f639d21 2418 restore_pos(aTHX_ prog);
e9105d30 2419 if (swap) {
c74340f9 2420 /* we failed :-( roll it back */
e9105d30
GG
2421 Safefree(prog->offs);
2422 prog->offs = swap;
2423 }
2424
d6a28714
JH
2425 return 0;
2426}
2427
6bda09f9 2428
d6a28714
JH
2429/*
2430 - regtry - try match at specific point
2431 */
2432STATIC I32 /* 0 failure, 1 success */
24b23f37 2433S_regtry(pTHX_ regmatch_info *reginfo, char **startpos)
d6a28714 2434{
97aff369 2435 dVAR;
d6a28714 2436 CHECKPOINT lastcp;
288b8c02
NC
2437 REGEXP *const rx = reginfo->prog;
2438 regexp *const prog = (struct regexp *)SvANY(rx);
f8fc2ecf 2439 RXi_GET_DECL(prog,progi);
a3621e74 2440 GET_RE_DEBUG_FLAGS_DECL;
7918f24d
NC
2441
2442 PERL_ARGS_ASSERT_REGTRY;
2443
24b23f37 2444 reginfo->cutpoint=NULL;
d6a28714 2445
bbe252da 2446 if ((prog->extflags & RXf_EVAL_SEEN) && !PL_reg_eval_set) {
d6a28714
JH
2447 MAGIC *mg;
2448
2449 PL_reg_eval_set = RS_init;
a3621e74 2450 DEBUG_EXECUTE_r(DEBUG_s(
b900a521
JH
2451 PerlIO_printf(Perl_debug_log, " setting stack tmpbase at %"IVdf"\n",
2452 (IV)(PL_stack_sp - PL_stack_base));
d6a28714 2453 ));
ea8d6ae1 2454 SAVESTACK_CXPOS();
d6a28714
JH
2455 cxstack[cxstack_ix].blk_oldsp = PL_stack_sp - PL_stack_base;
2456 /* Otherwise OP_NEXTSTATE will free whatever on stack now. */
2457 SAVETMPS;
2458 /* Apparently this is not needed, judging by wantarray. */
e8347627 2459 /* SAVEI8(cxstack[cxstack_ix].blk_gimme);
d6a28714
JH
2460 cxstack[cxstack_ix].blk_gimme = G_SCALAR; */
2461
3b0527fe 2462 if (reginfo->sv) {
d6a28714 2463 /* Make $_ available to executed code. */
3b0527fe 2464 if (reginfo->sv != DEFSV) {
59f00321 2465 SAVE_DEFSV;
414bf5ae 2466 DEFSV_set(reginfo->sv);
b8c5462f 2467 }
d6a28714 2468
3b0527fe
DM
2469 if (!(SvTYPE(reginfo->sv) >= SVt_PVMG && SvMAGIC(reginfo->sv)
2470 && (mg = mg_find(reginfo->sv, PERL_MAGIC_regex_global)))) {
d6a28714 2471 /* prepare for quick setting of pos */
d300d9fa 2472#ifdef PERL_OLD_COPY_ON_WRITE
51a9ea20
NC
2473 if (SvIsCOW(reginfo->sv))
2474 sv_force_normal_flags(reginfo->sv, 0);
d300d9fa 2475#endif
3dab1dad 2476 mg = sv_magicext(reginfo->sv, NULL, PERL_MAGIC_regex_global,
d300d9fa 2477 &PL_vtbl_mglob, NULL, 0);
d6a28714 2478 mg->mg_len = -1;
b8c5462f 2479 }
d6a28714
JH
2480 PL_reg_magic = mg;
2481 PL_reg_oldpos = mg->mg_len;
4f639d21 2482 SAVEDESTRUCTOR_X(restore_pos, prog);
d6a28714 2483 }
09687e5a 2484 if (!PL_reg_curpm) {
a02a5408 2485 Newxz(PL_reg_curpm, 1, PMOP);
09687e5a
AB
2486#ifdef USE_ITHREADS
2487 {
14a49a24 2488 SV* const repointer = &PL_sv_undef;
92313705
NC
2489 /* this regexp is also owned by the new PL_reg_curpm, which
2490 will try to free it. */
d2ece331 2491 av_push(PL_regex_padav, repointer);
09687e5a
AB
2492 PL_reg_curpm->op_pmoffset = av_len(PL_regex_padav);
2493 PL_regex_pad = AvARRAY(PL_regex_padav);
2494 }
2495#endif
2496 }
86c29d75
NC
2497#ifdef USE_ITHREADS
2498 /* It seems that non-ithreads works both with and without this code.
2499 So for efficiency reasons it seems best not to have the code
2500 compiled when it is not needed. */
92313705
NC
2501 /* This is safe against NULLs: */
2502 ReREFCNT_dec(PM_GETRE(PL_reg_curpm));
2503 /* PM_reg_curpm owns a reference to this regexp. */
2504 ReREFCNT_inc(rx);
86c29d75 2505#endif
288b8c02 2506 PM_SETRE(PL_reg_curpm, rx);
d6a28714
JH
2507 PL_reg_oldcurpm = PL_curpm;
2508 PL_curpm = PL_reg_curpm;
07bc277f 2509 if (RXp_MATCH_COPIED(prog)) {
d6a28714
JH
2510 /* Here is a serious problem: we cannot rewrite subbeg,
2511 since it may be needed if this match fails. Thus
2512 $` inside (?{}) could fail... */
2513 PL_reg_oldsaved = prog->subbeg;
2514 PL_reg_oldsavedlen = prog->sublen;
f8c7b90f 2515#ifdef PERL_OLD_COPY_ON_WRITE
ed252734
NC
2516 PL_nrs = prog->saved_copy;
2517#endif
07bc277f 2518 RXp_MATCH_COPIED_off(prog);
d6a28714
JH
2519 }
2520 else
bd61b366 2521 PL_reg_oldsaved = NULL;
d6a28714
JH
2522 prog->subbeg = PL_bostr;
2523 prog->sublen = PL_regeol - PL_bostr; /* strend may have been modified */
2524 }
24b23f37 2525 DEBUG_EXECUTE_r(PL_reg_starttry = *startpos);
f0ab9afb 2526 prog->offs[0].start = *startpos - PL_bostr;
24b23f37 2527 PL_reginput = *startpos;
d6a28714 2528 PL_reglastparen = &prog->lastparen;
a01268b5 2529 PL_reglastcloseparen = &prog->lastcloseparen;
d6a28714 2530 prog->lastparen = 0;
03994de8 2531 prog->lastcloseparen = 0;
d6a28714 2532 PL_regsize = 0;
f0ab9afb 2533 PL_regoffs = prog->offs;
d6a28714
JH
2534 if (PL_reg_start_tmpl <= prog->nparens) {
2535 PL_reg_start_tmpl = prog->nparens*3/2 + 3;
2536 if(PL_reg_start_tmp)
2537 Renew(PL_reg_start_tmp, PL_reg_start_tmpl, char*);
2538 else
a02a5408 2539 Newx(PL_reg_start_tmp, PL_reg_start_tmpl, char*);
d6a28714
JH
2540 }
2541
2542 /* XXXX What this code is doing here?!!! There should be no need
2543 to do this again and again, PL_reglastparen should take care of
3dd2943c 2544 this! --ilya*/
dafc8851
JH
2545
2546 /* Tests pat.t#187 and split.t#{13,14} seem to depend on this code.
2547 * Actually, the code in regcppop() (which Ilya may be meaning by
daf18116 2548 * PL_reglastparen), is not needed at all by the test suite
225593e1
DM
2549 * (op/regexp, op/pat, op/split), but that code is needed otherwise
2550 * this erroneously leaves $1 defined: "1" =~ /^(?:(\d)x)?\d$/
2551 * Meanwhile, this code *is* needed for the
daf18116
JH
2552 * above-mentioned test suite tests to succeed. The common theme
2553 * on those tests seems to be returning null fields from matches.
225593e1 2554 * --jhi updated by dapm */
dafc8851 2555#if 1
d6a28714 2556 if (prog->nparens) {
f0ab9afb 2557 regexp_paren_pair *pp = PL_regoffs;
097eb12c 2558 register I32 i;
eb160463 2559 for (i = prog->nparens; i > (I32)*PL_reglastparen; i--) {
f0ab9afb
NC
2560 ++pp;
2561 pp->start = -1;
2562 pp->end = -1;
d6a28714
JH
2563 }
2564 }
dafc8851 2565#endif
02db2b7b 2566 REGCP_SET(lastcp);
f8fc2ecf 2567 if (regmatch(reginfo, progi->program + 1)) {
f0ab9afb 2568 PL_regoffs[0].end = PL_reginput - PL_bostr;
d6a28714
JH
2569 return 1;
2570 }
24b23f37
YO
2571 if (reginfo->cutpoint)
2572 *startpos= reginfo->cutpoint;
02db2b7b 2573 REGCP_UNWIND(lastcp);
d6a28714
JH
2574 return 0;
2575}
2576
02db2b7b 2577
8ba1375e
MJD
2578#define sayYES goto yes
2579#define sayNO goto no
262b90c4 2580#define sayNO_SILENT goto no_silent
8ba1375e 2581
f9f4320a
YO
2582/* we dont use STMT_START/END here because it leads to
2583 "unreachable code" warnings, which are bogus, but distracting. */
2584#define CACHEsayNO \
c476f425
DM
2585 if (ST.cache_mask) \
2586 PL_reg_poscache[ST.cache_offset] |= ST.cache_mask; \
f9f4320a 2587 sayNO
3298f257 2588
a3621e74 2589/* this is used to determine how far from the left messages like
265c4333
YO
2590 'failed...' are printed. It should be set such that messages
2591 are inline with the regop output that created them.
a3621e74 2592*/
265c4333 2593#define REPORT_CODE_OFF 32
a3621e74
YO
2594
2595
40a82448
DM
2596#define CHRTEST_UNINIT -1001 /* c1/c2 haven't been calculated yet */
2597#define CHRTEST_VOID -1000 /* the c1/c2 "next char" test should be skipped */
9e137952 2598
86545054
DM
2599#define SLAB_FIRST(s) (&(s)->states[0])
2600#define SLAB_LAST(s) (&(s)->states[PERL_REGMATCH_SLAB_SLOTS-1])
2601
5d9a96ca
DM
2602/* grab a new slab and return the first slot in it */
2603
2604STATIC regmatch_state *
2605S_push_slab(pTHX)
2606{
a35a87e7 2607#if PERL_VERSION < 9 && !defined(PERL_CORE)
54df2634
NC
2608 dMY_CXT;
2609#endif
5d9a96ca
DM
2610 regmatch_slab *s = PL_regmatch_slab->next;
2611 if (!s) {
2612 Newx(s, 1, regmatch_slab);
2613 s->prev = PL_regmatch_slab;
2614 s->next = NULL;
2615 PL_regmatch_slab->next = s;
2616 }
2617 PL_regmatch_slab = s;
86545054 2618 return SLAB_FIRST(s);
5d9a96ca 2619}
5b47454d 2620
95b24440 2621
40a82448
DM
2622/* push a new state then goto it */
2623
2624#define PUSH_STATE_GOTO(state, node) \
2625 scan = node; \
2626 st->resume_state = state; \
2627 goto push_state;
2628
2629/* push a new state with success backtracking, then goto it */
2630
2631#define PUSH_YES_STATE_GOTO(state, node) \
2632 scan = node; \
2633 st->resume_state = state; \
2634 goto push_yes_state;
2635
aa283a38 2636
aa283a38 2637
d6a28714 2638/*
95b24440 2639
bf1f174e
DM
2640regmatch() - main matching routine
2641
2642This is basically one big switch statement in a loop. We execute an op,
2643set 'next' to point the next op, and continue. If we come to a point which
2644we may need to backtrack to on failure such as (A|B|C), we push a
2645backtrack state onto the backtrack stack. On failure, we pop the top
2646state, and re-enter the loop at the state indicated. If there are no more
2647states to pop, we return failure.
2648
2649Sometimes we also need to backtrack on success; for example /A+/, where
2650after successfully matching one A, we need to go back and try to
2651match another one; similarly for lookahead assertions: if the assertion
2652completes successfully, we backtrack to the state just before the assertion
2653and then carry on. In these cases, the pushed state is marked as
2654'backtrack on success too'. This marking is in fact done by a chain of
2655pointers, each pointing to the previous 'yes' state. On success, we pop to
2656the nearest yes state, discarding any intermediate failure-only states.
2657Sometimes a yes state is pushed just to force some cleanup code to be
2658called at the end of a successful match or submatch; e.g. (??{$re}) uses
2659it to free the inner regex.
2660
2661Note that failure backtracking rewinds the cursor position, while
2662success backtracking leaves it alone.
2663
2664A pattern is complete when the END op is executed, while a subpattern
2665such as (?=foo) is complete when the SUCCESS op is executed. Both of these
2666ops trigger the "pop to last yes state if any, otherwise return true"
2667behaviour.
2668
2669A common convention in this function is to use A and B to refer to the two
2670subpatterns (or to the first nodes thereof) in patterns like /A*B/: so A is
2671the subpattern to be matched possibly multiple times, while B is the entire
2672rest of the pattern. Variable and state names reflect this convention.
2673
2674The states in the main switch are the union of ops and failure/success of
2675substates associated with with that op. For example, IFMATCH is the op
2676that does lookahead assertions /(?=A)B/ and so the IFMATCH state means
2677'execute IFMATCH'; while IFMATCH_A is a state saying that we have just
2678successfully matched A and IFMATCH_A_fail is a state saying that we have
2679just failed to match A. Resume states always come in pairs. The backtrack
2680state we push is marked as 'IFMATCH_A', but when that is popped, we resume
2681at IFMATCH_A or IFMATCH_A_fail, depending on whether we are backtracking
2682on success or failure.
2683
2684The struct that holds a backtracking state is actually a big union, with
2685one variant for each major type of op. The variable st points to the
2686top-most backtrack struct. To make the code clearer, within each
2687block of code we #define ST to alias the relevant union.
2688
2689Here's a concrete example of a (vastly oversimplified) IFMATCH
2690implementation:
2691
2692 switch (state) {
2693 ....
2694
2695#define ST st->u.ifmatch
2696
2697 case IFMATCH: // we are executing the IFMATCH op, (?=A)B
2698 ST.foo = ...; // some state we wish to save
95b24440 2699 ...
bf1f174e
DM
2700 // push a yes backtrack state with a resume value of
2701 // IFMATCH_A/IFMATCH_A_fail, then continue execution at the
2702 // first node of A:
2703 PUSH_YES_STATE_GOTO(IFMATCH_A, A);
2704 // NOTREACHED
2705
2706 case IFMATCH_A: // we have successfully executed A; now continue with B
2707 next = B;
2708 bar = ST.foo; // do something with the preserved value
2709 break;
2710
2711 case IFMATCH_A_fail: // A failed, so the assertion failed
2712 ...; // do some housekeeping, then ...
2713 sayNO; // propagate the failure
2714
2715#undef ST
95b24440 2716
bf1f174e
DM
2717 ...
2718 }
95b24440 2719
bf1f174e
DM
2720For any old-timers reading this who are familiar with the old recursive
2721approach, the code above is equivalent to:
95b24440 2722
bf1f174e
DM
2723 case IFMATCH: // we are executing the IFMATCH op, (?=A)B
2724 {
2725 int foo = ...
95b24440 2726 ...
bf1f174e
DM
2727 if (regmatch(A)) {
2728 next = B;
2729 bar = foo;
2730 break;
95b24440 2731 }
bf1f174e
DM
2732 ...; // do some housekeeping, then ...
2733 sayNO; // propagate the failure
95b24440 2734 }
bf1f174e
DM
2735
2736The topmost backtrack state, pointed to by st, is usually free. If you
2737want to claim it, populate any ST.foo fields in it with values you wish to
2738save, then do one of
2739
2740 PUSH_STATE_GOTO(resume_state, node);
2741 PUSH_YES_STATE_GOTO(resume_state, node);
2742
2743which sets that backtrack state's resume value to 'resume_state', pushes a
2744new free entry to the top of the backtrack stack, then goes to 'node'.
2745On backtracking, the free slot is popped, and the saved state becomes the
2746new free state. An ST.foo field in this new top state can be temporarily
2747accessed to retrieve values, but once the main loop is re-entered, it
2748becomes available for reuse.
2749
2750Note that the depth of the backtrack stack constantly increases during the
2751left-to-right execution of the pattern, rather than going up and down with
2752the pattern nesting. For example the stack is at its maximum at Z at the
2753end of the pattern, rather than at X in the following:
2754
2755 /(((X)+)+)+....(Y)+....Z/
2756
2757The only exceptions to this are lookahead/behind assertions and the cut,
2758(?>A), which pop all the backtrack states associated with A before
2759continuing.
2760
2761Bascktrack state structs are allocated in slabs of about 4K in size.
2762PL_regmatch_state and st always point to the currently active state,
2763and PL_regmatch_slab points to the slab currently containing
2764PL_regmatch_state. The first time regmatch() is called, the first slab is
2765allocated, and is never freed until interpreter destruction. When the slab
2766is full, a new one is allocated and chained to the end. At exit from
2767regmatch(), slabs allocated since entry are freed.
2768
2769*/
95b24440 2770
40a82448 2771
5bc10b2c 2772#define DEBUG_STATE_pp(pp) \
265c4333 2773 DEBUG_STATE_r({ \
f2ed9b32 2774 DUMP_EXEC_POS(locinput, scan, utf8_target); \
5bc10b2c 2775 PerlIO_printf(Perl_debug_log, \
5d458dd8 2776 " %*s"pp" %s%s%s%s%s\n", \
5bc10b2c 2777 depth*2, "", \
13d6edb4 2778 PL_reg_name[st->resume_state], \
5d458dd8
YO
2779 ((st==yes_state||st==mark_state) ? "[" : ""), \
2780 ((st==yes_state) ? "Y" : ""), \
2781 ((st==mark_state) ? "M" : ""), \
2782 ((st==yes_state||st==mark_state) ? "]" : "") \
2783 ); \
265c4333 2784 });
5bc10b2c 2785
40a82448 2786
3dab1dad 2787#define REG_NODE_NUM(x) ((x) ? (int)((x)-prog) : -1)
95b24440 2788
3df15adc 2789#ifdef DEBUGGING
5bc10b2c 2790
ab3bbdeb 2791STATIC void
f2ed9b32 2792S_debug_start_match(pTHX_ const REGEXP *prog, const bool utf8_target,
ab3bbdeb
YO
2793 const char *start, const char *end, const char *blurb)
2794{
efd26800 2795 const bool utf8_pat = RX_UTF8(prog) ? 1 : 0;
7918f24d
NC
2796
2797 PERL_ARGS_ASSERT_DEBUG_START_MATCH;
2798
ab3bbdeb
YO
2799 if (!PL_colorset)
2800 reginitcolors();
2801 {
2802 RE_PV_QUOTED_DECL(s0, utf8_pat, PERL_DEBUG_PAD_ZERO(0),
d2c6dc5e 2803 RX_PRECOMP_const(prog), RX_PRELEN(prog), 60);
ab3bbdeb 2804
f2ed9b32 2805 RE_PV_QUOTED_DECL(s1, utf8_target, PERL_DEBUG_PAD_ZERO(1),
ab3bbdeb
YO
2806 start, end - start, 60);
2807
2808 PerlIO_printf(Perl_debug_log,
2809 "%s%s REx%s %s against %s\n",
2810 PL_colors[4], blurb, PL_colors[5], s0, s1);
2811
f2ed9b32 2812 if (utf8_target||utf8_pat)
1de06328
YO
2813 PerlIO_printf(Perl_debug_log, "UTF-8 %s%s%s...\n",
2814 utf8_pat ? "pattern" : "",
f2ed9b32
KW
2815 utf8_pat && utf8_target ? " and " : "",
2816 utf8_target ? "string" : ""
ab3bbdeb
YO
2817 );
2818 }
2819}
3df15adc
YO
2820
2821STATIC void
786e8c11
YO
2822S_dump_exec_pos(pTHX_ const char *locinput,
2823 const regnode *scan,
2824 const char *loc_regeol,
2825 const char *loc_bostr,
2826 const char *loc_reg_starttry,
f2ed9b32 2827 const bool utf8_target)
07be1b83 2828{
786e8c11 2829 const int docolor = *PL_colors[0] || *PL_colors[2] || *PL_colors[4];
07be1b83 2830 const int taill = (docolor ? 10 : 7); /* 3 chars for "> <" */
786e8c11 2831 int l = (loc_regeol - locinput) > taill ? taill : (loc_regeol - locinput);
07be1b83
YO
2832 /* The part of the string before starttry has one color
2833 (pref0_len chars), between starttry and current
2834 position another one (pref_len - pref0_len chars),
2835 after the current position the third one.
2836 We assume that pref0_len <= pref_len, otherwise we
2837 decrease pref0_len. */
786e8c11
YO
2838 int pref_len = (locinput - loc_bostr) > (5 + taill) - l
2839 ? (5 + taill) - l : locinput - loc_bostr;
07be1b83
YO
2840 int pref0_len;
2841
7918f24d
NC
2842 PERL_ARGS_ASSERT_DUMP_EXEC_POS;
2843
f2ed9b32 2844 while (utf8_target && UTF8_IS_CONTINUATION(*(U8*)(locinput - pref_len)))
07be1b83 2845 pref_len++;
786e8c11
YO
2846 pref0_len = pref_len - (locinput - loc_reg_starttry);
2847 if (l + pref_len < (5 + taill) && l < loc_regeol - locinput)
2848 l = ( loc_regeol - locinput > (5 + taill) - pref_len
2849 ? (5 + taill) - pref_len : loc_regeol - locinput);
f2ed9b32 2850 while (utf8_target && UTF8_IS_CONTINUATION(*(U8*)(locinput + l)))
07be1b83
YO
2851 l--;
2852 if (pref0_len < 0)
2853 pref0_len = 0;
2854 if (pref0_len > pref_len)
2855 pref0_len = pref_len;
2856 {
f2ed9b32 2857 const int is_uni = (utf8_target && OP(scan) != CANY) ? 1 : 0;
0df25f3d 2858
ab3bbdeb 2859 RE_PV_COLOR_DECL(s0,len0,is_uni,PERL_DEBUG_PAD(0),
1de06328 2860 (locinput - pref_len),pref0_len, 60, 4, 5);
0df25f3d 2861
ab3bbdeb 2862 RE_PV_COLOR_DECL(s1,len1,is_uni,PERL_DEBUG_PAD(1),
3df15adc 2863 (locinput - pref_len + pref0_len),
1de06328 2864 pref_len - pref0_len, 60, 2, 3);
0df25f3d 2865
ab3bbdeb 2866 RE_PV_COLOR_DECL(s2,len2,is_uni,PERL_DEBUG_PAD(2),
1de06328 2867 locinput, loc_regeol - locinput, 10, 0, 1);
0df25f3d 2868
1de06328 2869 const STRLEN tlen=len0+len1+len2;
3df15adc 2870 PerlIO_printf(Perl_debug_log,
ab3bbdeb 2871 "%4"IVdf" <%.*s%.*s%s%.*s>%*s|",
786e8c11 2872 (IV)(locinput - loc_bostr),
07be1b83 2873 len0, s0,
07be1b83 2874 len1, s1,
07be1b83 2875 (docolor ? "" : "> <"),
07be1b83 2876 len2, s2,
f9f4320a 2877 (int)(tlen > 19 ? 0 : 19 - tlen),
07be1b83
YO
2878 "");
2879 }
2880}
3df15adc 2881
07be1b83
YO
2882#endif
2883
0a4db386
YO
2884/* reg_check_named_buff_matched()
2885 * Checks to see if a named buffer has matched. The data array of
2886 * buffer numbers corresponding to the buffer is expected to reside
2887 * in the regexp->data->data array in the slot stored in the ARG() of
2888 * node involved. Note that this routine doesn't actually care about the
2889 * name, that information is not preserved from compilation to execution.
2890 * Returns the index of the leftmost defined buffer with the given name
2891 * or 0 if non of the buffers matched.
2892 */
2893STATIC I32
7918f24d
NC
2894S_reg_check_named_buff_matched(pTHX_ const regexp *rex, const regnode *scan)
2895{
0a4db386 2896 I32 n;
f8fc2ecf 2897 RXi_GET_DECL(rex,rexi);
ad64d0ec 2898 SV *sv_dat= MUTABLE_SV(rexi->data->data[ ARG( scan ) ]);
0a4db386 2899 I32 *nums=(I32*)SvPVX(sv_dat);
7918f24d
NC
2900
2901 PERL_ARGS_ASSERT_REG_CHECK_NAMED_BUFF_MATCHED;
2902
0a4db386
YO
2903 for ( n=0; n<SvIVX(sv_dat); n++ ) {
2904 if ((I32)*PL_reglastparen >= nums[n] &&
f0ab9afb 2905 PL_regoffs[nums[n]].end != -1)
0a4db386
YO
2906 {
2907 return nums[n];
2908 }
2909 }
2910 return 0;
2911}
2912
2f554ef7
DM
2913
2914/* free all slabs above current one - called during LEAVE_SCOPE */
2915
2916STATIC void
2917S_clear_backtrack_stack(pTHX_ void *p)
2918{
2919 regmatch_slab *s = PL_regmatch_slab->next;
2920 PERL_UNUSED_ARG(p);
2921
2922 if (!s)
2923 return;
2924 PL_regmatch_slab->next = NULL;
2925 while (s) {
2926 regmatch_slab * const osl = s;
2927 s = s->next;
2928 Safefree(osl);
2929 }
2930}
2931
2932
28d8d7f4
YO
2933#define SETREX(Re1,Re2) \
2934 if (PL_reg_eval_set) PM_SETRE((PL_reg_curpm), (Re2)); \
2935 Re1 = (Re2)
2936
d6a28714 2937STATIC I32 /* 0 failure, 1 success */
24b23f37 2938S_regmatch(pTHX_ regmatch_info *reginfo, regnode *prog)
d6a28714 2939{
a35a87e7 2940#if PERL_VERSION < 9 && !defined(PERL_CORE)
54df2634
NC
2941 dMY_CXT;
2942#endif
27da23d5 2943 dVAR;
f2ed9b32 2944 register const bool utf8_target = PL_reg_match_utf8;
4ad0818d 2945 const U32 uniflags = UTF8_ALLOW_DEFAULT;
288b8c02
NC
2946 REGEXP *rex_sv = reginfo->prog;
2947 regexp *rex = (struct regexp *)SvANY(rex_sv);
f8fc2ecf 2948 RXi_GET_DECL(rex,rexi);
2f554ef7 2949 I32 oldsave;
5d9a96ca
DM
2950 /* the current state. This is a cached copy of PL_regmatch_state */
2951 register regmatch_state *st;
5d9a96ca
DM
2952 /* cache heavy used fields of st in registers */
2953 register regnode *scan;
2954 register regnode *next;
438e9bae 2955 register U32 n = 0; /* general value; init to avoid compiler warning */
24d3c4a9 2956 register I32 ln = 0; /* len or last; init to avoid compiler warning */
5d9a96ca 2957 register char *locinput = PL_reginput;
5d9a96ca 2958 register I32 nextchr; /* is always set to UCHARAT(locinput) */
24d3c4a9 2959
b69b0499 2960 bool result = 0; /* return value of S_regmatch */
24d3c4a9 2961 int depth = 0; /* depth of backtrack stack */
4b196cd4
YO
2962 U32 nochange_depth = 0; /* depth of GOSUB recursion with nochange */
2963 const U32 max_nochange_depth =
2964 (3 * rex->nparens > MAX_RECURSE_EVAL_NOCHANGE_DEPTH) ?
2965 3 * rex->nparens : MAX_RECURSE_EVAL_NOCHANGE_DEPTH;
77cb431f
DM
2966 regmatch_state *yes_state = NULL; /* state to pop to on success of
2967 subpattern */
e2e6a0f1
YO
2968 /* mark_state piggy backs on the yes_state logic so that when we unwind
2969 the stack on success we can update the mark_state as we go */
2970 regmatch_state *mark_state = NULL; /* last mark state we have seen */
faec1544 2971 regmatch_state *cur_eval = NULL; /* most recent EVAL_AB state */
b8591aee 2972 struct regmatch_state *cur_curlyx = NULL; /* most recent curlyx */
40a82448 2973 U32 state_num;
5d458dd8
YO
2974 bool no_final = 0; /* prevent failure from backtracking? */
2975 bool do_cutgroup = 0; /* no_final only until next branch/trie entry */
e2e6a0f1 2976 char *startpoint = PL_reginput;
5d458dd8
YO
2977 SV *popmark = NULL; /* are we looking for a mark? */
2978 SV *sv_commit = NULL; /* last mark name seen in failure */
2979 SV *sv_yes_mark = NULL; /* last mark name we have seen
2980 during a successfull match */
2981 U32 lastopen = 0; /* last open we saw */
2982 bool has_cutgroup = RX_HAS_CUTGROUP(rex) ? 1 : 0;
19b95bf0 2983 SV* const oreplsv = GvSV(PL_replgv);
24d3c4a9
DM
2984 /* these three flags are set by various ops to signal information to
2985 * the very next op. They have a useful lifetime of exactly one loop
2986 * iteration, and are not preserved or restored by state pushes/pops
2987 */
2988 bool sw = 0; /* the condition value in (?(cond)a|b) */
2989 bool minmod = 0; /* the next "{n,m}" is a "{n,m}?" */
2990 int logical = 0; /* the following EVAL is:
2991 0: (?{...})
2992 1: (?(?{...})X|Y)
2993 2: (??{...})
2994 or the following IFMATCH/UNLESSM is:
2995 false: plain (?=foo)
2996 true: used as a condition: (?(?=foo))
2997 */
95b24440 2998#ifdef DEBUGGING
e68ec53f 2999 GET_RE_DEBUG_FLAGS_DECL;
d6a28714
JH
3000#endif
3001
7918f24d
NC
3002 PERL_ARGS_ASSERT_REGMATCH;
3003
3b57cd43 3004 DEBUG_OPTIMISE_r( DEBUG_EXECUTE_r({
24b23f37 3005 PerlIO_printf(Perl_debug_log,"regmatch start\n");
3b57cd43 3006 }));
5d9a96ca
DM
3007 /* on first ever call to regmatch, allocate first slab */
3008 if (!PL_regmatch_slab) {
3009 Newx(PL_regmatch_slab, 1, regmatch_slab);
3010 PL_regmatch_slab->prev = NULL;
3011 PL_regmatch_slab->next = NULL;
86545054 3012 PL_regmatch_state = SLAB_FIRST(PL_regmatch_slab);
5d9a96ca
DM
3013 }
3014
2f554ef7
DM
3015 oldsave = PL_savestack_ix;
3016 SAVEDESTRUCTOR_X(S_clear_backtrack_stack, NULL);
3017 SAVEVPTR(PL_regmatch_slab);
3018 SAVEVPTR(PL_regmatch_state);
5d9a96ca
DM
3019
3020 /* grab next free state slot */
3021 st = ++PL_regmatch_state;
86545054 3022 if (st > SLAB_LAST(PL_regmatch_slab))
5d9a96ca
DM
3023 st = PL_regmatch_state = S_push_slab(aTHX);
3024
d6a28714
JH
3025 /* Note that nextchr is a byte even in UTF */
3026 nextchr = UCHARAT(locinput);
3027 scan = prog;
3028 while (scan != NULL) {
8ba1375e 3029
a3621e74 3030 DEBUG_EXECUTE_r( {
6136c704 3031 SV * const prop = sv_newmortal();
1de06328 3032 regnode *rnext=regnext(scan);
f2ed9b32 3033 DUMP_EXEC_POS( locinput, scan, utf8_target );
32fc9b6a 3034 regprop(rex, prop, scan);
07be1b83
YO
3035
3036 PerlIO_printf(Perl_debug_log,
3037 "%3"IVdf":%*s%s(%"IVdf")\n",
f8fc2ecf 3038 (IV)(scan - rexi->program), depth*2, "",
07be1b83 3039 SvPVX_const(prop),
1de06328 3040 (PL_regkind[OP(scan)] == END || !rnext) ?
f8fc2ecf 3041 0 : (IV)(rnext - rexi->program));
2a782b5b 3042 });
d6a28714
JH
3043
3044 next = scan + NEXT_OFF(scan);
3045 if (next == scan)
3046 next = NULL;
40a82448 3047 state_num = OP(scan);
d6a28714 3048
40a82448 3049 reenter_switch:
34a81e2b
B
3050
3051 assert(PL_reglastparen == &rex->lastparen);
3052 assert(PL_reglastcloseparen == &rex->lastcloseparen);
3053 assert(PL_regoffs == rex->offs);
3054
40a82448 3055 switch (state_num) {
d6a28714 3056 case BOL:
7fba1cd6 3057 if (locinput == PL_bostr)
d6a28714 3058 {
3b0527fe 3059 /* reginfo->till = reginfo->bol; */
b8c5462f
JH
3060 break;
3061 }
d6a28714
JH
3062 sayNO;
3063 case MBOL:
12d33761
HS
3064 if (locinput == PL_bostr ||
3065 ((nextchr || locinput < PL_regeol) && locinput[-1] == '\n'))
d6a28714 3066 {
b8c5462f
JH
3067 break;
3068 }
d6a28714
JH
3069 sayNO;
3070 case SBOL:
c2a73568 3071 if (locinput == PL_bostr)
b8c5462f 3072 break;
d6a28714
JH
3073 sayNO;
3074 case GPOS:
3b0527fe 3075 if (locinput == reginfo->ganch)
d6a28714
JH
3076 break;
3077 sayNO;
ee9b8eae
YO
3078
3079 case KEEPS:
3080 /* update the startpoint */
f0ab9afb 3081 st->u.keeper.val = PL_regoffs[0].start;
ee9b8eae 3082 PL_reginput = locinput;
f0ab9afb 3083 PL_regoffs[0].start = locinput - PL_bostr;
ee9b8eae
YO
3084 PUSH_STATE_GOTO(KEEPS_next, next);
3085 /*NOT-REACHED*/
3086 case KEEPS_next_fail:
3087 /* rollback the start point change */
f0ab9afb 3088 PL_regoffs[0].start = st->u.keeper.val;
ee9b8eae
YO
3089 sayNO_SILENT;
3090 /*NOT-REACHED*/
d6a28714 3091 case EOL:
d6a28714
JH
3092 goto seol;
3093 case MEOL:
d6a28714 3094 if ((nextchr || locinput < PL_regeol) && nextchr != '\n')
b8c5462f 3095 sayNO;
b8c5462f 3096 break;
d6a28714
JH
3097 case SEOL:
3098 seol:
3099 if ((nextchr || locinput < PL_regeol) && nextchr != '\n')
b8c5462f 3100 sayNO;
d6a28714 3101 if (PL_regeol - locinput > 1)
b8c5462f 3102 sayNO;
b8c5462f 3103 break;
d6a28714
JH
3104 case EOS:
3105 if (PL_regeol != locinput)
b8c5462f 3106 sayNO;
d6a28714 3107 break;
ffc61ed2 3108 case SANY:
d6a28714 3109 if (!nextchr && locinput >= PL_regeol)
4633a7c4 3110 sayNO;
f2ed9b32 3111 if (utf8_target) {
f33976b4
DB
3112 locinput += PL_utf8skip[nextchr];
3113 if (locinput > PL_regeol)
3114 sayNO;
3115 nextchr = UCHARAT(locinput);
3116 }
3117 else
3118 nextchr = UCHARAT(++locinput);
3119 break;
3120 case CANY:
3121 if (!nextchr && locinput >= PL_regeol)
3122 sayNO;
b8c5462f 3123 nextchr = UCHARAT(++locinput);
a0d0e21e 3124 break;
ffc61ed2 3125 case REG_ANY:
1aa99e6b
IH
3126 if ((!nextchr && locinput >= PL_regeol) || nextchr == '\n')
3127 sayNO;
f2ed9b32 3128 if (utf8_target) {
b8c5462f 3129 locinput += PL_utf8skip[nextchr];
d6a28714
JH
3130 if (locinput > PL_regeol)
3131 sayNO;
a0ed51b3 3132 nextchr = UCHARAT(locinput);
a0ed51b3 3133 }
1aa99e6b
IH
3134 else
3135 nextchr = UCHARAT(++locinput);
a0ed51b3 3136 break;
166ba7cd
DM
3137
3138#undef ST
3139#define ST st->u.trie
786e8c11
YO
3140 case TRIEC:
3141 /* In this case the charclass data is available inline so
3142 we can fail fast without a lot of extra overhead.
3143 */
f2ed9b32 3144 if (scan->flags == EXACT || !utf8_target) {
786e8c11
YO
3145 if(!ANYOF_BITMAP_TEST(scan, *locinput)) {
3146 DEBUG_EXECUTE_r(
3147 PerlIO_printf(Perl_debug_log,
3148 "%*s %sfailed to match trie start class...%s\n",
5bc10b2c 3149 REPORT_CODE_OFF+depth*2, "", PL_colors[4], PL_colors[5])
786e8c11
YO
3150 );
3151 sayNO_SILENT;
3152 /* NOTREACHED */
3153 }
3154 }
3155 /* FALL THROUGH */
5b47454d 3156 case TRIE:
2e64971a
DM
3157 /* the basic plan of execution of the trie is:
3158 * At the beginning, run though all the states, and
3159 * find the longest-matching word. Also remember the position
3160 * of the shortest matching word. For example, this pattern:
3161 * 1 2 3 4 5
3162 * ab|a|x|abcd|abc
3163 * when matched against the string "abcde", will generate
3164 * accept states for all words except 3, with the longest
3165 * matching word being 4, and the shortest being 1 (with
3166 * the position being after char 1 of the string).
3167 *
3168 * Then for each matching word, in word order (i.e. 1,2,4,5),
3169 * we run the remainder of the pattern; on each try setting
3170 * the current position to the character following the word,
3171 * returning to try the next word on failure.
3172 *
3173 * We avoid having to build a list of words at runtime by
3174 * using a compile-time structure, wordinfo[].prev, which
3175 * gives, for each word, the previous accepting word (if any).
3176 * In the case above it would contain the mappings 1->2, 2->0,
3177 * 3->0, 4->5, 5->1. We can use this table to generate, from
3178 * the longest word (4 above), a list of all words, by
3179 * following the list of prev pointers; this gives us the
3180 * unordered list 4,5,1,2. Then given the current word we have
3181 * just tried, we can go through the list and find the
3182 * next-biggest word to try (so if we just failed on word 2,
3183 * the next in the list is 4).
3184 *
3185 * Since at runtime we don't record the matching position in
3186 * the string for each word, we have to work that out for
3187 * each word we're about to process. The wordinfo table holds
3188 * the character length of each word; given that we recorded
3189 * at the start: the position of the shortest word and its
3190 * length in chars, we just need to move the pointer the
3191 * difference between the two char lengths. Depending on
3192 * Unicode status and folding, that's cheap or expensive.
3193 *
3194 * This algorithm is optimised for the case where are only a
3195 * small number of accept states, i.e. 0,1, or maybe 2.
3196 * With lots of accepts states, and having to try all of them,
3197 * it becomes quadratic on number of accept states to find all
3198 * the next words.
3199 */
3200
3dab1dad 3201 {
07be1b83 3202 /* what type of TRIE am I? (utf8 makes this contextual) */
a0a388a1 3203 DECL_TRIE_TYPE(scan);
3dab1dad
YO
3204
3205 /* what trie are we using right now */
be8e71aa 3206 reg_trie_data * const trie
f8fc2ecf 3207 = (reg_trie_data*)rexi->data->data[ ARG( scan ) ];
85fbaab2 3208 HV * widecharmap = MUTABLE_HV(rexi->data->data[ ARG( scan ) + 1 ]);
3dab1dad 3209 U32 state = trie->startstate;
166ba7cd 3210
3dab1dad
YO
3211 if (trie->bitmap && trie_type != trie_utf8_fold &&
3212 !TRIE_BITMAP_TEST(trie,*locinput)
3213 ) {
3214 if (trie->states[ state ].wordnum) {
3215 DEBUG_EXECUTE_r(
3216 PerlIO_printf(Perl_debug_log,
3217 "%*s %smatched empty string...%s\n",
5bc10b2c 3218 REPORT_CODE_OFF+depth*2, "", PL_colors[4], PL_colors[5])
3dab1dad
YO
3219 );
3220 break;
3221 } else {
3222 DEBUG_EXECUTE_r(
3223 PerlIO_printf(Perl_debug_log,
786e8c11 3224 "%*s %sfailed to match trie start class...%s\n",
5bc10b2c 3225 REPORT_CODE_OFF+depth*2, "", PL_colors[4], PL_colors[5])
3dab1dad
YO
3226 );
3227 sayNO_SILENT;
3228 }
3229 }
166ba7cd 3230
786e8c11
YO
3231 {
3232 U8 *uc = ( U8* )locinput;
3233
3234 STRLEN len = 0;
3235 STRLEN foldlen = 0;
3236 U8 *uscan = (U8*)NULL;
786e8c11 3237 U8 foldbuf[ UTF8_MAXBYTES_CASE + 1 ];
2e64971a
DM
3238 U32 charcount = 0; /* how many input chars we have matched */
3239 U32 accepted = 0; /* have we seen any accepting states? */
786e8c11 3240
786e8c11
YO
3241 ST.B = next;
3242 ST.jump = trie->jump;
786e8c11 3243 ST.me = scan;
2e64971a
DM
3244 ST.firstpos = NULL;
3245 ST.longfold = FALSE; /* char longer if folded => it's harder */
3246 ST.nextword = 0;
3247
3248 /* fully traverse the TRIE; note the position of the
3249 shortest accept state and the wordnum of the longest
3250 accept state */
07be1b83 3251
a3621e74 3252 while ( state && uc <= (U8*)PL_regeol ) {
786e8c11 3253 U32 base = trie->states[ state ].trans.base;
f9f4320a 3254 UV uvc = 0;
acb909b4 3255 U16 charid = 0;
2e64971a
DM
3256 U16 wordnum;
3257 wordnum = trie->states[ state ].wordnum;
3258
3259 if (wordnum) { /* it's an accept state */
3260 if (!accepted) {
3261 accepted = 1;
3262 /* record first match position */
3263 if (ST.longfold) {
3264 ST.firstpos = (U8*)locinput;
3265 ST.firstchars = 0;
5b47454d 3266 }
2e64971a
DM
3267 else {
3268 ST.firstpos = uc;
3269 ST.firstchars = charcount;
3270 }
3271 }
3272 if (!ST.nextword || wordnum < ST.nextword)
3273 ST.nextword = wordnum;
3274 ST.topword = wordnum;
786e8c11 3275 }
a3621e74 3276
07be1b83 3277 DEBUG_TRIE_EXECUTE_r({
f2ed9b32 3278 DUMP_EXEC_POS( (char *)uc, scan, utf8_target );
a3621e74 3279 PerlIO_printf( Perl_debug_log,
2e64971a 3280 "%*s %sState: %4"UVxf" Accepted: %c ",
5bc10b2c 3281 2+depth * 2, "", PL_colors[4],
2e64971a 3282 (UV)state, (accepted ? 'Y' : 'N'));
07be1b83 3283 });
a3621e74 3284
2e64971a 3285 /* read a char and goto next state */
a3621e74 3286 if ( base ) {
6dd2be57 3287 I32 offset;
55eed653
NC
3288 REXEC_TRIE_READ_CHAR(trie_type, trie, widecharmap, uc,
3289 uscan, len, uvc, charid, foldlen,
3290 foldbuf, uniflags);
2e64971a
DM
3291 charcount++;
3292 if (foldlen>0)
3293 ST.longfold = TRUE;
5b47454d 3294 if (charid &&
6dd2be57
DM
3295 ( ((offset =
3296 base + charid - 1 - trie->uniquecharcount)) >= 0)
3297
3298 && ((U32)offset < trie->lasttrans)
3299 && trie->trans[offset].check == state)
5b47454d 3300 {
6dd2be57 3301 state = trie->trans[offset].next;
5b47454d
DM
3302 }
3303 else {
3304 state = 0;
3305 }
3306 uc += len;
3307
3308 }
3309 else {
a3621e74
YO
3310 state = 0;
3311 }
3312 DEBUG_TRIE_EXECUTE_r(
e4584336 3313 PerlIO_printf( Perl_debug_log,
786e8c11 3314 "Charid:%3x CP:%4"UVxf" After State: %4"UVxf"%s\n",
e4584336 3315 charid, uvc, (UV)state, PL_colors[5] );
a3621e74
YO
3316 );
3317 }
2e64971a 3318 if (!accepted)
a3621e74 3319 sayNO;
a3621e74 3320
2e64971a
DM
3321 /* calculate total number of accept states */
3322 {
3323 U16 w = ST.topword;
3324 accepted = 0;
3325 while (w) {
3326 w = trie->wordinfo[w].prev;
3327 accepted++;
3328 }
3329 ST.accepted = accepted;
3330 }
3331
166ba7cd
DM
3332 DEBUG_EXECUTE_r(
3333 PerlIO_printf( Perl_debug_log,
3334 "%*s %sgot %"IVdf" possible matches%s\n",
5bc10b2c 3335 REPORT_CODE_OFF + depth * 2, "",
166ba7cd
DM
3336 PL_colors[4], (IV)ST.accepted, PL_colors[5] );
3337 );
2e64971a 3338 goto trie_first_try; /* jump into the fail handler */
786e8c11 3339 }}
fae667d5 3340 /* NOTREACHED */
2e64971a
DM
3341
3342 case TRIE_next_fail: /* we failed - try next alternative */
fae667d5
YO
3343 if ( ST.jump) {
3344 REGCP_UNWIND(ST.cp);
3345 for (n = *PL_reglastparen; n > ST.lastparen; n--)
f0ab9afb 3346 PL_regoffs[n].end = -1;
fae667d5
YO
3347 *PL_reglastparen = n;
3348 }
2e64971a
DM
3349 if (!--ST.accepted) {
3350 DEBUG_EXECUTE_r({
3351 PerlIO_printf( Perl_debug_log,
3352 "%*s %sTRIE failed...%s\n",
3353 REPORT_CODE_OFF+depth*2, "",
3354 PL_colors[4],
3355 PL_colors[5] );
3356 });
3357 sayNO_SILENT;
3358 }
3359 {
3360 /* Find next-highest word to process. Note that this code
3361 * is O(N^2) per trie run (O(N) per branch), so keep tight */
d9a396a3
DM
3362 register U16 min = 0;
3363 register U16 word;
2e64971a
DM
3364 register U16 const nextword = ST.nextword;
3365 register reg_trie_wordinfo * const wordinfo
3366 = ((reg_trie_data*)rexi->data->data[ARG(ST.me)])->wordinfo;
3367 for (word=ST.topword; word; word=wordinfo[word].prev) {
3368 if (word > nextword && (!min || word < min))
3369 min = word;
3370 }
3371 ST.nextword = min;