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