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