Commit | Line | Data |
---|---|---|
a0d0e21e LW |
1 | /* regexec.c |
2 | */ | |
3 | ||
4 | /* | |
4ac71550 TC |
5 | * One Ring to rule them all, One Ring to find them |
6 | & | |
7 | * [p.v of _The Lord of the Rings_, opening poem] | |
8 | * [p.50 of _The Lord of the Rings_, I/iii: "The Shadow of the Past"] | |
9 | * [p.254 of _The Lord of the Rings_, II/ii: "The Council of Elrond"] | |
a0d0e21e LW |
10 | */ |
11 | ||
61296642 DM |
12 | /* This file contains functions for executing a regular expression. See |
13 | * also regcomp.c which funnily enough, contains functions for compiling | |
166f8a29 | 14 | * a regular expression. |
e4a054ea DM |
15 | * |
16 | * This file is also copied at build time to ext/re/re_exec.c, where | |
17 | * it's built with -DPERL_EXT_RE_BUILD -DPERL_EXT_RE_DEBUG -DPERL_EXT. | |
18 | * This causes the main functions to be compiled under new names and with | |
19 | * debugging support added, which makes "use re 'debug'" work. | |
166f8a29 DM |
20 | */ |
21 | ||
a687059c LW |
22 | /* NOTE: this is derived from Henry Spencer's regexp code, and should not |
23 | * confused with the original package (see point 3 below). Thanks, Henry! | |
24 | */ | |
25 | ||
26 | /* Additional note: this code is very heavily munged from Henry's version | |
27 | * in places. In some spots I've traded clarity for efficiency, so don't | |
28 | * blame Henry for some of the lack of readability. | |
29 | */ | |
30 | ||
e50aee73 AD |
31 | /* The names of the functions have been changed from regcomp and |
32 | * regexec to pregcomp and pregexec in order to avoid conflicts | |
33 | * with the POSIX routines of the same names. | |
34 | */ | |
35 | ||
b9d5759e | 36 | #ifdef PERL_EXT_RE_BUILD |
54df2634 | 37 | #include "re_top.h" |
9041c2e3 | 38 | #endif |
56953603 | 39 | |
a687059c | 40 | /* |
e50aee73 | 41 | * pregcomp and pregexec -- regsub and regerror are not used in perl |
a687059c LW |
42 | * |
43 | * Copyright (c) 1986 by University of Toronto. | |
44 | * Written by Henry Spencer. Not derived from licensed software. | |
45 | * | |
46 | * Permission is granted to anyone to use this software for any | |
47 | * purpose on any computer system, and to redistribute it freely, | |
48 | * subject to the following restrictions: | |
49 | * | |
50 | * 1. The author is not responsible for the consequences of use of | |
51 | * this software, no matter how awful, even if they arise | |
52 | * from defects in it. | |
53 | * | |
54 | * 2. The origin of this software must not be misrepresented, either | |
55 | * by explicit claim or by omission. | |
56 | * | |
57 | * 3. Altered versions must be plainly marked as such, and must not | |
58 | * be misrepresented as being the original software. | |
59 | * | |
60 | **** Alterations to Henry's code are... | |
61 | **** | |
4bb101f2 | 62 | **** Copyright (C) 1991, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999, |
1129b882 NC |
63 | **** 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008 |
64 | **** by Larry Wall and others | |
a687059c | 65 | **** |
9ef589d8 LW |
66 | **** You may distribute under the terms of either the GNU General Public |
67 | **** License or the Artistic License, as specified in the README file. | |
a687059c LW |
68 | * |
69 | * Beware that some of this code is subtly aware of the way operator | |
70 | * precedence is structured in regular expressions. Serious changes in | |
71 | * regular-expression syntax might require a total rethink. | |
72 | */ | |
73 | #include "EXTERN.h" | |
864dbfa3 | 74 | #define PERL_IN_REGEXEC_C |
a687059c | 75 | #include "perl.h" |
0f5d15d6 | 76 | |
54df2634 NC |
77 | #ifdef PERL_IN_XSUB_RE |
78 | # include "re_comp.h" | |
79 | #else | |
80 | # include "regcomp.h" | |
81 | #endif | |
a687059c | 82 | |
81e983c1 | 83 | #include "inline_invlist.c" |
1b0f46bf | 84 | #include "unicode_constants.h" |
81e983c1 | 85 | |
e1cf74e3 CB |
86 | #ifdef DEBUGGING |
87 | /* At least one required character in the target string is expressible only in | |
88 | * UTF-8. */ | |
89 | static const char* const non_utf8_target_but_utf8_required | |
90 | = "Can't match, because target string needs to be in UTF-8\n"; | |
91 | #endif | |
92 | ||
93 | #define NON_UTF8_TARGET_BUT_UTF8_REQUIRED(target) STMT_START { \ | |
94 | DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "%s", non_utf8_target_but_utf8_required));\ | |
95 | goto target; \ | |
96 | } STMT_END | |
97 | ||
c74f6de9 KW |
98 | #define HAS_NONLATIN1_FOLD_CLOSURE(i) _HAS_NONLATIN1_FOLD_CLOSURE_ONLY_FOR_USE_BY_REGCOMP_DOT_C_AND_REGEXEC_DOT_C(i) |
99 | ||
a687059c LW |
100 | #ifndef STATIC |
101 | #define STATIC static | |
102 | #endif | |
103 | ||
2d66f61e | 104 | /* Valid only for non-utf8 strings: avoids the reginclass |
7e2509c1 KW |
105 | * call if there are no complications: i.e., if everything matchable is |
106 | * straight forward in the bitmap */ | |
3db24e1e | 107 | #define REGINCLASS(prog,p,c) (ANYOF_FLAGS(p) ? reginclass(prog,p,c,c+1,0) \ |
af364d03 | 108 | : ANYOF_BITMAP_TEST(p,*(c))) |
7d3e948e | 109 | |
c277df42 IZ |
110 | /* |
111 | * Forwards. | |
112 | */ | |
113 | ||
f2ed9b32 | 114 | #define CHR_SVLEN(sv) (utf8_target ? sv_len_utf8(sv) : SvCUR(sv)) |
ba44c216 | 115 | #define CHR_DIST(a,b) (reginfo->is_utf8_target ? utf8_distance(a,b) : a - b) |
a0ed51b3 | 116 | |
3dab1dad | 117 | #define HOPc(pos,off) \ |
ba44c216 | 118 | (char *)(reginfo->is_utf8_target \ |
220db18a | 119 | ? reghop3((U8*)pos, off, \ |
9d9163fb | 120 | (U8*)(off >= 0 ? reginfo->strend : reginfo->strbeg)) \ |
3dab1dad | 121 | : (U8*)(pos + off)) |
557f47af | 122 | |
3dab1dad | 123 | #define HOPBACKc(pos, off) \ |
ba44c216 | 124 | (char*)(reginfo->is_utf8_target \ |
9d9163fb DM |
125 | ? reghopmaybe3((U8*)pos, -off, (U8*)(reginfo->strbeg)) \ |
126 | : (pos - off >= reginfo->strbeg) \ | |
8e11feef | 127 | ? (U8*)pos - off \ |
3dab1dad | 128 | : NULL) |
efb30f32 | 129 | |
ba44c216 | 130 | #define HOP3(pos,off,lim) (reginfo->is_utf8_target ? reghop3((U8*)(pos), off, (U8*)(lim)) : (U8*)(pos + off)) |
1aa99e6b | 131 | #define HOP3c(pos,off,lim) ((char*)HOP3(pos,off,lim)) |
1aa99e6b | 132 | |
557f47af DM |
133 | /* lim must be +ve. Returns NULL on overshoot */ |
134 | #define HOPMAYBE3(pos,off,lim) \ | |
135 | (reginfo->is_utf8_target \ | |
136 | ? reghopmaybe3((U8*)pos, off, (U8*)(lim)) \ | |
137 | : ((U8*)pos + off <= lim) \ | |
138 | ? (U8*)pos + off \ | |
139 | : NULL) | |
140 | ||
8e9f2289 DM |
141 | /* like HOP3, but limits the result to <= lim even for the non-utf8 case. |
142 | * off must be >=0; args should be vars rather than expressions */ | |
143 | #define HOP3lim(pos,off,lim) (reginfo->is_utf8_target \ | |
144 | ? reghop3((U8*)(pos), off, (U8*)(lim)) \ | |
145 | : (U8*)((pos + off) > lim ? lim : (pos + off))) | |
146 | ||
2974eaec DM |
147 | #define HOP4(pos,off,llim, rlim) (reginfo->is_utf8_target \ |
148 | ? reghop4((U8*)(pos), off, (U8*)(llim), (U8*)(rlim)) \ | |
149 | : (U8*)(pos + off)) | |
150 | #define HOP4c(pos,off,llim, rlim) ((char*)HOP4(pos,off,llim, rlim)) | |
7016d6eb DM |
151 | |
152 | #define NEXTCHR_EOS -10 /* nextchr has fallen off the end */ | |
153 | #define NEXTCHR_IS_EOS (nextchr < 0) | |
154 | ||
155 | #define SET_nextchr \ | |
220db18a | 156 | nextchr = ((locinput < reginfo->strend) ? UCHARAT(locinput) : NEXTCHR_EOS) |
7016d6eb DM |
157 | |
158 | #define SET_locinput(p) \ | |
159 | locinput = (p); \ | |
160 | SET_nextchr | |
161 | ||
162 | ||
2a16ac92 | 163 | #define LOAD_UTF8_CHARCLASS(swash_ptr, property_name, invlist) STMT_START { \ |
c7304fe2 KW |
164 | if (!swash_ptr) { \ |
165 | U8 flags = _CORE_SWASH_INIT_ACCEPT_INVLIST; \ | |
c7304fe2 | 166 | swash_ptr = _core_swash_init("utf8", property_name, &PL_sv_undef, \ |
2a16ac92 | 167 | 1, 0, invlist, &flags); \ |
c7304fe2 KW |
168 | assert(swash_ptr); \ |
169 | } \ | |
170 | } STMT_END | |
171 | ||
172 | /* If in debug mode, we test that a known character properly matches */ | |
173 | #ifdef DEBUGGING | |
174 | # define LOAD_UTF8_CHARCLASS_DEBUG_TEST(swash_ptr, \ | |
175 | property_name, \ | |
2a16ac92 | 176 | invlist, \ |
c7304fe2 | 177 | utf8_char_in_property) \ |
2a16ac92 | 178 | LOAD_UTF8_CHARCLASS(swash_ptr, property_name, invlist); \ |
c7304fe2 KW |
179 | assert(swash_fetch(swash_ptr, (U8 *) utf8_char_in_property, TRUE)); |
180 | #else | |
181 | # define LOAD_UTF8_CHARCLASS_DEBUG_TEST(swash_ptr, \ | |
182 | property_name, \ | |
2a16ac92 | 183 | invlist, \ |
c7304fe2 | 184 | utf8_char_in_property) \ |
2a16ac92 | 185 | LOAD_UTF8_CHARCLASS(swash_ptr, property_name, invlist) |
c7304fe2 | 186 | #endif |
d1eb3177 | 187 | |
c7304fe2 KW |
188 | #define LOAD_UTF8_CHARCLASS_ALNUM() LOAD_UTF8_CHARCLASS_DEBUG_TEST( \ |
189 | PL_utf8_swash_ptrs[_CC_WORDCHAR], \ | |
2a16ac92 KW |
190 | "", \ |
191 | PL_XPosix_ptrs[_CC_WORDCHAR], \ | |
df38da56 | 192 | LATIN_CAPITAL_LETTER_SHARP_S_UTF8); |
c7304fe2 KW |
193 | |
194 | #define LOAD_UTF8_CHARCLASS_GCB() /* Grapheme cluster boundaries */ \ | |
195 | STMT_START { \ | |
196 | LOAD_UTF8_CHARCLASS_DEBUG_TEST(PL_utf8_X_regular_begin, \ | |
197 | "_X_regular_begin", \ | |
2a16ac92 | 198 | NULL, \ |
df38da56 | 199 | LATIN_CAPITAL_LETTER_SHARP_S_UTF8); \ |
c7304fe2 KW |
200 | LOAD_UTF8_CHARCLASS_DEBUG_TEST(PL_utf8_X_extend, \ |
201 | "_X_extend", \ | |
2a16ac92 | 202 | NULL, \ |
c7304fe2 KW |
203 | COMBINING_GRAVE_ACCENT_UTF8); \ |
204 | } STMT_END | |
d1eb3177 | 205 | |
c7304fe2 | 206 | #define PLACEHOLDER /* Something for the preprocessor to grab onto */ |
3dab1dad YO |
207 | /* TODO: Combine JUMPABLE and HAS_TEXT to cache OP(rn) */ |
208 | ||
5f80c4cf | 209 | /* for use after a quantifier and before an EXACT-like node -- japhy */ |
c35dcbe2 YO |
210 | /* it would be nice to rework regcomp.sym to generate this stuff. sigh |
211 | * | |
212 | * NOTE that *nothing* that affects backtracking should be in here, specifically | |
213 | * VERBS must NOT be included. JUMPABLE is used to determine if we can ignore a | |
214 | * node that is in between two EXACT like nodes when ascertaining what the required | |
215 | * "follow" character is. This should probably be moved to regex compile time | |
216 | * although it may be done at run time beause of the REF possibility - more | |
217 | * investigation required. -- demerphq | |
218 | */ | |
baa60164 KW |
219 | #define JUMPABLE(rn) ( \ |
220 | OP(rn) == OPEN || \ | |
3e901dc0 | 221 | (OP(rn) == CLOSE && (!cur_eval || cur_eval->u.eval.close_paren != ARG(rn))) || \ |
baa60164 KW |
222 | OP(rn) == EVAL || \ |
223 | OP(rn) == SUSPEND || OP(rn) == IFMATCH || \ | |
224 | OP(rn) == PLUS || OP(rn) == MINMOD || \ | |
225 | OP(rn) == KEEPS || \ | |
226 | (PL_regkind[OP(rn)] == CURLY && ARG1(rn) > 0) \ | |
e2d8ce26 | 227 | ) |
ee9b8eae | 228 | #define IS_EXACT(rn) (PL_regkind[OP(rn)] == EXACT) |
e2d8ce26 | 229 | |
ee9b8eae YO |
230 | #define HAS_TEXT(rn) ( IS_EXACT(rn) || PL_regkind[OP(rn)] == REF ) |
231 | ||
232 | #if 0 | |
233 | /* Currently these are only used when PL_regkind[OP(rn)] == EXACT so | |
a4525e78 | 234 | we don't need this definition. XXX These are now out-of-sync*/ |
ee9b8eae | 235 | #define IS_TEXT(rn) ( OP(rn)==EXACT || OP(rn)==REF || OP(rn)==NREF ) |
098b07d5 | 236 | #define IS_TEXTF(rn) ( OP(rn)==EXACTFU || OP(rn)==EXACTFU_SS || OP(rn)==EXACTFA || OP(rn)==EXACTFA_NO_TRIE || OP(rn)==EXACTF || OP(rn)==REFF || OP(rn)==NREFF ) |
ee9b8eae YO |
237 | #define IS_TEXTFL(rn) ( OP(rn)==EXACTFL || OP(rn)==REFFL || OP(rn)==NREFFL ) |
238 | ||
239 | #else | |
240 | /* ... so we use this as its faster. */ | |
a4525e78 KW |
241 | #define IS_TEXT(rn) ( OP(rn)==EXACT || OP(rn)==EXACTL ) |
242 | #define IS_TEXTFU(rn) ( OP(rn)==EXACTFU || OP(rn)==EXACTFLU8 || OP(rn)==EXACTFU_SS || OP(rn) == EXACTFA || OP(rn) == EXACTFA_NO_TRIE) | |
ee9b8eae YO |
243 | #define IS_TEXTF(rn) ( OP(rn)==EXACTF ) |
244 | #define IS_TEXTFL(rn) ( OP(rn)==EXACTFL ) | |
245 | ||
246 | #endif | |
e2d8ce26 | 247 | |
a84d97b6 HS |
248 | /* |
249 | Search for mandatory following text node; for lookahead, the text must | |
250 | follow but for lookbehind (rn->flags != 0) we skip to the next step. | |
251 | */ | |
baa60164 | 252 | #define FIND_NEXT_IMPT(rn) STMT_START { \ |
3dab1dad YO |
253 | while (JUMPABLE(rn)) { \ |
254 | const OPCODE type = OP(rn); \ | |
255 | if (type == SUSPEND || PL_regkind[type] == CURLY) \ | |
e2d8ce26 | 256 | rn = NEXTOPER(NEXTOPER(rn)); \ |
3dab1dad | 257 | else if (type == PLUS) \ |
cca55fe3 | 258 | rn = NEXTOPER(rn); \ |
3dab1dad | 259 | else if (type == IFMATCH) \ |
a84d97b6 | 260 | rn = (rn->flags == 0) ? NEXTOPER(NEXTOPER(rn)) : rn + ARG(rn); \ |
e2d8ce26 | 261 | else rn += NEXT_OFF(rn); \ |
3dab1dad | 262 | } \ |
5f80c4cf | 263 | } STMT_END |
74750237 | 264 | |
22913b96 KW |
265 | /* These constants are for finding GCB=LV and GCB=LVT in the CLUMP regnode. |
266 | * These are for the pre-composed Hangul syllables, which are all in a | |
267 | * contiguous block and arranged there in such a way so as to facilitate | |
268 | * alorithmic determination of their characteristics. As such, they don't need | |
269 | * a swash, but can be determined by simple arithmetic. Almost all are | |
270 | * GCB=LVT, but every 28th one is a GCB=LV */ | |
271 | #define SBASE 0xAC00 /* Start of block */ | |
272 | #define SCount 11172 /* Length of block */ | |
273 | #define TCount 28 | |
c476f425 | 274 | |
006f26b2 DM |
275 | #define SLAB_FIRST(s) (&(s)->states[0]) |
276 | #define SLAB_LAST(s) (&(s)->states[PERL_REGMATCH_SLAB_SLOTS-1]) | |
277 | ||
a75351a1 | 278 | static void S_setup_eval_state(pTHX_ regmatch_info *const reginfo); |
bf2039a9 | 279 | static void S_cleanup_regmatch_info_aux(pTHX_ void *arg); |
bf2039a9 | 280 | static regmatch_state * S_push_slab(pTHX); |
51371543 | 281 | |
87c0511b | 282 | #define REGCP_PAREN_ELEMS 3 |
f067efbf | 283 | #define REGCP_OTHER_ELEMS 3 |
e0fa7e2b | 284 | #define REGCP_FRAME_ELEMS 1 |
620d5b66 NC |
285 | /* REGCP_FRAME_ELEMS are not part of the REGCP_OTHER_ELEMS and |
286 | * are needed for the regexp context stack bookkeeping. */ | |
287 | ||
76e3520e | 288 | STATIC CHECKPOINT |
92da3157 | 289 | S_regcppush(pTHX_ const regexp *rex, I32 parenfloor, U32 maxopenparen) |
a0d0e21e | 290 | { |
a3b680e6 | 291 | const int retval = PL_savestack_ix; |
92da3157 DM |
292 | const int paren_elems_to_push = |
293 | (maxopenparen - parenfloor) * REGCP_PAREN_ELEMS; | |
e0fa7e2b NC |
294 | const UV total_elems = paren_elems_to_push + REGCP_OTHER_ELEMS; |
295 | const UV elems_shifted = total_elems << SAVE_TIGHT_SHIFT; | |
87c0511b | 296 | I32 p; |
40a82448 | 297 | GET_RE_DEBUG_FLAGS_DECL; |
a0d0e21e | 298 | |
b93070ed DM |
299 | PERL_ARGS_ASSERT_REGCPPUSH; |
300 | ||
e49a9654 | 301 | if (paren_elems_to_push < 0) |
e8a85d26 JH |
302 | Perl_croak(aTHX_ "panic: paren_elems_to_push, %i < 0, maxopenparen: %i parenfloor: %i REGCP_PAREN_ELEMS: %u", |
303 | (int)paren_elems_to_push, (int)maxopenparen, | |
304 | (int)parenfloor, (unsigned)REGCP_PAREN_ELEMS); | |
e49a9654 | 305 | |
e0fa7e2b NC |
306 | if ((elems_shifted >> SAVE_TIGHT_SHIFT) != total_elems) |
307 | Perl_croak(aTHX_ "panic: paren_elems_to_push offset %"UVuf | |
5df417d0 | 308 | " out of range (%lu-%ld)", |
92da3157 DM |
309 | total_elems, |
310 | (unsigned long)maxopenparen, | |
311 | (long)parenfloor); | |
e0fa7e2b | 312 | |
620d5b66 | 313 | SSGROW(total_elems + REGCP_FRAME_ELEMS); |
7f69552c | 314 | |
495f47a5 | 315 | DEBUG_BUFFERS_r( |
92da3157 | 316 | if ((int)maxopenparen > (int)parenfloor) |
495f47a5 DM |
317 | PerlIO_printf(Perl_debug_log, |
318 | "rex=0x%"UVxf" offs=0x%"UVxf": saving capture indices:\n", | |
319 | PTR2UV(rex), | |
320 | PTR2UV(rex->offs) | |
321 | ); | |
322 | ); | |
92da3157 | 323 | for (p = parenfloor+1; p <= (I32)maxopenparen; p++) { |
b1ce53c5 | 324 | /* REGCP_PARENS_ELEMS are pushed per pairs of parentheses. */ |
99a90e59 FC |
325 | SSPUSHIV(rex->offs[p].end); |
326 | SSPUSHIV(rex->offs[p].start); | |
1ca2007e | 327 | SSPUSHINT(rex->offs[p].start_tmp); |
e7707071 | 328 | DEBUG_BUFFERS_r(PerlIO_printf(Perl_debug_log, |
495f47a5 DM |
329 | " \\%"UVuf": %"IVdf"(%"IVdf")..%"IVdf"\n", |
330 | (UV)p, | |
331 | (IV)rex->offs[p].start, | |
332 | (IV)rex->offs[p].start_tmp, | |
333 | (IV)rex->offs[p].end | |
40a82448 | 334 | )); |
a0d0e21e | 335 | } |
b1ce53c5 | 336 | /* REGCP_OTHER_ELEMS are pushed in any case, parentheses or no. */ |
92da3157 | 337 | SSPUSHINT(maxopenparen); |
b93070ed DM |
338 | SSPUSHINT(rex->lastparen); |
339 | SSPUSHINT(rex->lastcloseparen); | |
e0fa7e2b | 340 | SSPUSHUV(SAVEt_REGCONTEXT | elems_shifted); /* Magic cookie. */ |
41123dfd | 341 | |
a0d0e21e LW |
342 | return retval; |
343 | } | |
344 | ||
c277df42 | 345 | /* These are needed since we do not localize EVAL nodes: */ |
ab3bbdeb YO |
346 | #define REGCP_SET(cp) \ |
347 | DEBUG_STATE_r( \ | |
ab3bbdeb | 348 | PerlIO_printf(Perl_debug_log, \ |
e4f74956 | 349 | " Setting an EVAL scope, savestack=%"IVdf"\n", \ |
ab3bbdeb YO |
350 | (IV)PL_savestack_ix)); \ |
351 | cp = PL_savestack_ix | |
c3464db5 | 352 | |
ab3bbdeb | 353 | #define REGCP_UNWIND(cp) \ |
e4f74956 | 354 | DEBUG_STATE_r( \ |
ab3bbdeb | 355 | if (cp != PL_savestack_ix) \ |
e4f74956 YO |
356 | PerlIO_printf(Perl_debug_log, \ |
357 | " Clearing an EVAL scope, savestack=%"IVdf"..%"IVdf"\n", \ | |
ab3bbdeb YO |
358 | (IV)(cp), (IV)PL_savestack_ix)); \ |
359 | regcpblow(cp) | |
c277df42 | 360 | |
a8d1f4b4 DM |
361 | #define UNWIND_PAREN(lp, lcp) \ |
362 | for (n = rex->lastparen; n > lp; n--) \ | |
363 | rex->offs[n].end = -1; \ | |
364 | rex->lastparen = n; \ | |
365 | rex->lastcloseparen = lcp; | |
366 | ||
367 | ||
f067efbf | 368 | STATIC void |
92da3157 | 369 | S_regcppop(pTHX_ regexp *rex, U32 *maxopenparen_p) |
a0d0e21e | 370 | { |
e0fa7e2b | 371 | UV i; |
87c0511b | 372 | U32 paren; |
a3621e74 YO |
373 | GET_RE_DEBUG_FLAGS_DECL; |
374 | ||
7918f24d NC |
375 | PERL_ARGS_ASSERT_REGCPPOP; |
376 | ||
b1ce53c5 | 377 | /* Pop REGCP_OTHER_ELEMS before the parentheses loop starts. */ |
c6bf6a65 | 378 | i = SSPOPUV; |
e0fa7e2b NC |
379 | assert((i & SAVE_MASK) == SAVEt_REGCONTEXT); /* Check that the magic cookie is there. */ |
380 | i >>= SAVE_TIGHT_SHIFT; /* Parentheses elements to pop. */ | |
b93070ed DM |
381 | rex->lastcloseparen = SSPOPINT; |
382 | rex->lastparen = SSPOPINT; | |
92da3157 | 383 | *maxopenparen_p = SSPOPINT; |
b1ce53c5 | 384 | |
620d5b66 | 385 | i -= REGCP_OTHER_ELEMS; |
b1ce53c5 | 386 | /* Now restore the parentheses context. */ |
495f47a5 DM |
387 | DEBUG_BUFFERS_r( |
388 | if (i || rex->lastparen + 1 <= rex->nparens) | |
389 | PerlIO_printf(Perl_debug_log, | |
390 | "rex=0x%"UVxf" offs=0x%"UVxf": restoring capture indices to:\n", | |
391 | PTR2UV(rex), | |
392 | PTR2UV(rex->offs) | |
393 | ); | |
394 | ); | |
92da3157 | 395 | paren = *maxopenparen_p; |
620d5b66 | 396 | for ( ; i > 0; i -= REGCP_PAREN_ELEMS) { |
ea3daa5d | 397 | SSize_t tmps; |
1ca2007e | 398 | rex->offs[paren].start_tmp = SSPOPINT; |
99a90e59 FC |
399 | rex->offs[paren].start = SSPOPIV; |
400 | tmps = SSPOPIV; | |
b93070ed DM |
401 | if (paren <= rex->lastparen) |
402 | rex->offs[paren].end = tmps; | |
495f47a5 DM |
403 | DEBUG_BUFFERS_r( PerlIO_printf(Perl_debug_log, |
404 | " \\%"UVuf": %"IVdf"(%"IVdf")..%"IVdf"%s\n", | |
405 | (UV)paren, | |
406 | (IV)rex->offs[paren].start, | |
407 | (IV)rex->offs[paren].start_tmp, | |
408 | (IV)rex->offs[paren].end, | |
409 | (paren > rex->lastparen ? "(skipped)" : "")); | |
c277df42 | 410 | ); |
87c0511b | 411 | paren--; |
a0d0e21e | 412 | } |
daf18116 | 413 | #if 1 |
dafc8851 JH |
414 | /* It would seem that the similar code in regtry() |
415 | * already takes care of this, and in fact it is in | |
416 | * a better location to since this code can #if 0-ed out | |
417 | * but the code in regtry() is needed or otherwise tests | |
418 | * requiring null fields (pat.t#187 and split.t#{13,14} | |
daf18116 JH |
419 | * (as of patchlevel 7877) will fail. Then again, |
420 | * this code seems to be necessary or otherwise | |
225593e1 DM |
421 | * this erroneously leaves $1 defined: "1" =~ /^(?:(\d)x)?\d$/ |
422 | * --jhi updated by dapm */ | |
b93070ed | 423 | for (i = rex->lastparen + 1; i <= rex->nparens; i++) { |
92da3157 | 424 | if (i > *maxopenparen_p) |
b93070ed DM |
425 | rex->offs[i].start = -1; |
426 | rex->offs[i].end = -1; | |
495f47a5 DM |
427 | DEBUG_BUFFERS_r( PerlIO_printf(Perl_debug_log, |
428 | " \\%"UVuf": %s ..-1 undeffing\n", | |
429 | (UV)i, | |
92da3157 | 430 | (i > *maxopenparen_p) ? "-1" : " " |
495f47a5 | 431 | )); |
a0d0e21e | 432 | } |
dafc8851 | 433 | #endif |
a0d0e21e LW |
434 | } |
435 | ||
74088413 DM |
436 | /* restore the parens and associated vars at savestack position ix, |
437 | * but without popping the stack */ | |
438 | ||
439 | STATIC void | |
92da3157 | 440 | S_regcp_restore(pTHX_ regexp *rex, I32 ix, U32 *maxopenparen_p) |
74088413 DM |
441 | { |
442 | I32 tmpix = PL_savestack_ix; | |
443 | PL_savestack_ix = ix; | |
92da3157 | 444 | regcppop(rex, maxopenparen_p); |
74088413 DM |
445 | PL_savestack_ix = tmpix; |
446 | } | |
447 | ||
02db2b7b | 448 | #define regcpblow(cp) LEAVE_SCOPE(cp) /* Ignores regcppush()ed data. */ |
a0d0e21e | 449 | |
31c7f561 KW |
450 | STATIC bool |
451 | S_isFOO_lc(pTHX_ const U8 classnum, const U8 character) | |
452 | { | |
453 | /* Returns a boolean as to whether or not 'character' is a member of the | |
454 | * Posix character class given by 'classnum' that should be equivalent to a | |
455 | * value in the typedef '_char_class_number'. | |
456 | * | |
457 | * Ideally this could be replaced by a just an array of function pointers | |
458 | * to the C library functions that implement the macros this calls. | |
459 | * However, to compile, the precise function signatures are required, and | |
460 | * these may vary from platform to to platform. To avoid having to figure | |
461 | * out what those all are on each platform, I (khw) am using this method, | |
7aee35ff KW |
462 | * which adds an extra layer of function call overhead (unless the C |
463 | * optimizer strips it away). But we don't particularly care about | |
464 | * performance with locales anyway. */ | |
31c7f561 KW |
465 | |
466 | switch ((_char_class_number) classnum) { | |
15861f94 | 467 | case _CC_ENUM_ALPHANUMERIC: return isALPHANUMERIC_LC(character); |
31c7f561 | 468 | case _CC_ENUM_ALPHA: return isALPHA_LC(character); |
e8d596e0 KW |
469 | case _CC_ENUM_ASCII: return isASCII_LC(character); |
470 | case _CC_ENUM_BLANK: return isBLANK_LC(character); | |
b0d691b2 KW |
471 | case _CC_ENUM_CASED: return isLOWER_LC(character) |
472 | || isUPPER_LC(character); | |
e8d596e0 | 473 | case _CC_ENUM_CNTRL: return isCNTRL_LC(character); |
31c7f561 KW |
474 | case _CC_ENUM_DIGIT: return isDIGIT_LC(character); |
475 | case _CC_ENUM_GRAPH: return isGRAPH_LC(character); | |
476 | case _CC_ENUM_LOWER: return isLOWER_LC(character); | |
477 | case _CC_ENUM_PRINT: return isPRINT_LC(character); | |
e8d596e0 | 478 | case _CC_ENUM_PSXSPC: return isPSXSPC_LC(character); |
31c7f561 | 479 | case _CC_ENUM_PUNCT: return isPUNCT_LC(character); |
e8d596e0 | 480 | case _CC_ENUM_SPACE: return isSPACE_LC(character); |
31c7f561 KW |
481 | case _CC_ENUM_UPPER: return isUPPER_LC(character); |
482 | case _CC_ENUM_WORDCHAR: return isWORDCHAR_LC(character); | |
31c7f561 | 483 | case _CC_ENUM_XDIGIT: return isXDIGIT_LC(character); |
31c7f561 KW |
484 | default: /* VERTSPACE should never occur in locales */ |
485 | Perl_croak(aTHX_ "panic: isFOO_lc() has an unexpected character class '%d'", classnum); | |
486 | } | |
487 | ||
e5964223 | 488 | NOT_REACHED; /* NOTREACHED */ |
31c7f561 KW |
489 | return FALSE; |
490 | } | |
491 | ||
3018b823 KW |
492 | STATIC bool |
493 | S_isFOO_utf8_lc(pTHX_ const U8 classnum, const U8* character) | |
494 | { | |
495 | /* Returns a boolean as to whether or not the (well-formed) UTF-8-encoded | |
496 | * 'character' is a member of the Posix character class given by 'classnum' | |
497 | * that should be equivalent to a value in the typedef | |
498 | * '_char_class_number'. | |
499 | * | |
500 | * This just calls isFOO_lc on the code point for the character if it is in | |
2f306ab9 | 501 | * the range 0-255. Outside that range, all characters use Unicode |
3018b823 KW |
502 | * rules, ignoring any locale. So use the Unicode function if this class |
503 | * requires a swash, and use the Unicode macro otherwise. */ | |
504 | ||
505 | PERL_ARGS_ASSERT_ISFOO_UTF8_LC; | |
506 | ||
507 | if (UTF8_IS_INVARIANT(*character)) { | |
508 | return isFOO_lc(classnum, *character); | |
509 | } | |
510 | else if (UTF8_IS_DOWNGRADEABLE_START(*character)) { | |
511 | return isFOO_lc(classnum, | |
94bb8c36 | 512 | TWO_BYTE_UTF8_TO_NATIVE(*character, *(character + 1))); |
3018b823 KW |
513 | } |
514 | ||
515 | if (classnum < _FIRST_NON_SWASH_CC) { | |
516 | ||
517 | /* Initialize the swash unless done already */ | |
518 | if (! PL_utf8_swash_ptrs[classnum]) { | |
519 | U8 flags = _CORE_SWASH_INIT_ACCEPT_INVLIST; | |
2a16ac92 KW |
520 | PL_utf8_swash_ptrs[classnum] = |
521 | _core_swash_init("utf8", | |
522 | "", | |
523 | &PL_sv_undef, 1, 0, | |
524 | PL_XPosix_ptrs[classnum], &flags); | |
3018b823 KW |
525 | } |
526 | ||
92a2046b KW |
527 | return cBOOL(swash_fetch(PL_utf8_swash_ptrs[classnum], (U8 *) |
528 | character, | |
529 | TRUE /* is UTF */ )); | |
3018b823 KW |
530 | } |
531 | ||
532 | switch ((_char_class_number) classnum) { | |
533 | case _CC_ENUM_SPACE: | |
534 | case _CC_ENUM_PSXSPC: return is_XPERLSPACE_high(character); | |
535 | ||
536 | case _CC_ENUM_BLANK: return is_HORIZWS_high(character); | |
537 | case _CC_ENUM_XDIGIT: return is_XDIGIT_high(character); | |
538 | case _CC_ENUM_VERTSPACE: return is_VERTWS_high(character); | |
e1ee3960 | 539 | default: break; |
3018b823 KW |
540 | } |
541 | ||
e1ee3960 | 542 | return FALSE; /* Things like CNTRL are always below 256 */ |
3018b823 KW |
543 | } |
544 | ||
a687059c | 545 | /* |
e50aee73 | 546 | * pregexec and friends |
a687059c LW |
547 | */ |
548 | ||
76234dfb | 549 | #ifndef PERL_IN_XSUB_RE |
a687059c | 550 | /* |
c277df42 | 551 | - pregexec - match a regexp against a string |
a687059c | 552 | */ |
c277df42 | 553 | I32 |
5aaab254 | 554 | Perl_pregexec(pTHX_ REGEXP * const prog, char* stringarg, char *strend, |
ea3daa5d | 555 | char *strbeg, SSize_t minend, SV *screamer, U32 nosave) |
8fd1a950 DM |
556 | /* stringarg: the point in the string at which to begin matching */ |
557 | /* strend: pointer to null at end of string */ | |
558 | /* strbeg: real beginning of string */ | |
559 | /* minend: end of match must be >= minend bytes after stringarg. */ | |
560 | /* screamer: SV being matched: only used for utf8 flag, pos() etc; string | |
561 | * itself is accessed via the pointers above */ | |
562 | /* nosave: For optimizations. */ | |
c277df42 | 563 | { |
7918f24d NC |
564 | PERL_ARGS_ASSERT_PREGEXEC; |
565 | ||
c277df42 | 566 | return |
9041c2e3 | 567 | regexec_flags(prog, stringarg, strend, strbeg, minend, screamer, NULL, |
c277df42 IZ |
568 | nosave ? 0 : REXEC_COPY_STR); |
569 | } | |
76234dfb | 570 | #endif |
22e551b9 | 571 | |
cad2e5aa | 572 | |
6eb5f6b9 | 573 | |
1a4edc3c DM |
574 | /* re_intuit_start(): |
575 | * | |
576 | * Based on some optimiser hints, try to find the earliest position in the | |
577 | * string where the regex could match. | |
578 | * | |
579 | * rx: the regex to match against | |
580 | * sv: the SV being matched: only used for utf8 flag; the string | |
581 | * itself is accessed via the pointers below. Note that on | |
582 | * something like an overloaded SV, SvPOK(sv) may be false | |
583 | * and the string pointers may point to something unrelated to | |
584 | * the SV itself. | |
585 | * strbeg: real beginning of string | |
586 | * strpos: the point in the string at which to begin matching | |
587 | * strend: pointer to the byte following the last char of the string | |
588 | * flags currently unused; set to 0 | |
589 | * data: currently unused; set to NULL | |
590 | * | |
591 | * The basic idea of re_intuit_start() is to use some known information | |
592 | * about the pattern, namely: | |
593 | * | |
594 | * a) the longest known anchored substring (i.e. one that's at a | |
595 | * constant offset from the beginning of the pattern; but not | |
596 | * necessarily at a fixed offset from the beginning of the | |
597 | * string); | |
598 | * b) the longest floating substring (i.e. one that's not at a constant | |
599 | * offset from the beginning of the pattern); | |
600 | * c) Whether the pattern is anchored to the string; either | |
601 | * an absolute anchor: /^../, or anchored to \n: /^.../m, | |
602 | * or anchored to pos(): /\G/; | |
603 | * d) A start class: a real or synthetic character class which | |
604 | * represents which characters are legal at the start of the pattern; | |
605 | * | |
606 | * to either quickly reject the match, or to find the earliest position | |
607 | * within the string at which the pattern might match, thus avoiding | |
608 | * running the full NFA engine at those earlier locations, only to | |
609 | * eventually fail and retry further along. | |
610 | * | |
611 | * Returns NULL if the pattern can't match, or returns the address within | |
612 | * the string which is the earliest place the match could occur. | |
613 | * | |
614 | * The longest of the anchored and floating substrings is called 'check' | |
615 | * and is checked first. The other is called 'other' and is checked | |
616 | * second. The 'other' substring may not be present. For example, | |
617 | * | |
618 | * /(abc|xyz)ABC\d{0,3}DEFG/ | |
619 | * | |
620 | * will have | |
621 | * | |
622 | * check substr (float) = "DEFG", offset 6..9 chars | |
623 | * other substr (anchored) = "ABC", offset 3..3 chars | |
624 | * stclass = [ax] | |
625 | * | |
626 | * Be aware that during the course of this function, sometimes 'anchored' | |
627 | * refers to a substring being anchored relative to the start of the | |
628 | * pattern, and sometimes to the pattern itself being anchored relative to | |
629 | * the string. For example: | |
630 | * | |
631 | * /\dabc/: "abc" is anchored to the pattern; | |
632 | * /^\dabc/: "abc" is anchored to the pattern and the string; | |
633 | * /\d+abc/: "abc" is anchored to neither the pattern nor the string; | |
634 | * /^\d+abc/: "abc" is anchored to neither the pattern nor the string, | |
635 | * but the pattern is anchored to the string. | |
52a21eb3 DM |
636 | */ |
637 | ||
cad2e5aa | 638 | char * |
52a21eb3 DM |
639 | Perl_re_intuit_start(pTHX_ |
640 | REGEXP * const rx, | |
641 | SV *sv, | |
642 | const char * const strbeg, | |
643 | char *strpos, | |
644 | char *strend, | |
645 | const U32 flags, | |
646 | re_scream_pos_data *data) | |
cad2e5aa | 647 | { |
8d919b0a | 648 | struct regexp *const prog = ReANY(rx); |
6b071d16 | 649 | SSize_t start_shift = prog->check_offset_min; |
cad2e5aa | 650 | /* Should be nonnegative! */ |
ea3daa5d | 651 | SSize_t end_shift = 0; |
0fc004dd DM |
652 | /* current lowest pos in string where the regex can start matching */ |
653 | char *rx_origin = strpos; | |
eb578fdb | 654 | SV *check; |
f2ed9b32 | 655 | const bool utf8_target = (sv && SvUTF8(sv)) ? 1 : 0; /* if no sv we have to assume bytes */ |
6480a6c4 | 656 | U8 other_ix = 1 - prog->substrs->check_ix; |
6ad5ffb3 | 657 | bool ml_anch = 0; |
8f4bf5fc | 658 | char *other_last = strpos;/* latest pos 'other' substr already checked to */ |
bd61b366 | 659 | char *check_at = NULL; /* check substr found at this pos */ |
bbe252da | 660 | const I32 multiline = prog->extflags & RXf_PMf_MULTILINE; |
f8fc2ecf | 661 | RXi_GET_DECL(prog,progi); |
02d5137b DM |
662 | regmatch_info reginfo_buf; /* create some info to pass to find_byclass */ |
663 | regmatch_info *const reginfo = ®info_buf; | |
a3621e74 YO |
664 | GET_RE_DEBUG_FLAGS_DECL; |
665 | ||
7918f24d | 666 | PERL_ARGS_ASSERT_RE_INTUIT_START; |
c33e64f0 FC |
667 | PERL_UNUSED_ARG(flags); |
668 | PERL_UNUSED_ARG(data); | |
7918f24d | 669 | |
1dc475d0 DM |
670 | DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, |
671 | "Intuit: trying to determine minimum start position...\n")); | |
672 | ||
fb9bbddb DM |
673 | /* for now, assume that all substr offsets are positive. If at some point |
674 | * in the future someone wants to do clever things with look-behind and | |
675 | * -ve offsets, they'll need to fix up any code in this function | |
676 | * which uses these offsets. See the thread beginning | |
677 | * <20140113145929.GF27210@iabyn.com> | |
678 | */ | |
679 | assert(prog->substrs->data[0].min_offset >= 0); | |
680 | assert(prog->substrs->data[0].max_offset >= 0); | |
681 | assert(prog->substrs->data[1].min_offset >= 0); | |
682 | assert(prog->substrs->data[1].max_offset >= 0); | |
683 | assert(prog->substrs->data[2].min_offset >= 0); | |
684 | assert(prog->substrs->data[2].max_offset >= 0); | |
685 | ||
f7022b5a | 686 | /* for now, assume that if both present, that the floating substring |
83f2232d | 687 | * doesn't start before the anchored substring. |
f7022b5a DM |
688 | * If you break this assumption (e.g. doing better optimisations |
689 | * with lookahead/behind), then you'll need to audit the code in this | |
690 | * function carefully first | |
691 | */ | |
692 | assert( | |
693 | ! ( (prog->anchored_utf8 || prog->anchored_substr) | |
694 | && (prog->float_utf8 || prog->float_substr)) | |
695 | || (prog->float_min_offset >= prog->anchored_offset)); | |
696 | ||
1a4edc3c DM |
697 | /* byte rather than char calculation for efficiency. It fails |
698 | * to quickly reject some cases that can't match, but will reject | |
699 | * them later after doing full char arithmetic */ | |
c344f387 | 700 | if (prog->minlen > strend - strpos) { |
a3621e74 | 701 | DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, |
1dc475d0 | 702 | " String too short...\n")); |
cad2e5aa | 703 | goto fail; |
2c2d71f5 | 704 | } |
d8da0584 | 705 | |
ab4e48c1 | 706 | RX_MATCH_UTF8_set(rx,utf8_target); |
6c3fea77 | 707 | reginfo->is_utf8_target = cBOOL(utf8_target); |
bf2039a9 | 708 | reginfo->info_aux = NULL; |
9d9163fb | 709 | reginfo->strbeg = strbeg; |
220db18a | 710 | reginfo->strend = strend; |
aed7b151 | 711 | reginfo->is_utf8_pat = cBOOL(RX_UTF8(rx)); |
02d5137b | 712 | reginfo->intuit = 1; |
1cb48e53 DM |
713 | /* not actually used within intuit, but zero for safety anyway */ |
714 | reginfo->poscache_maxiter = 0; | |
02d5137b | 715 | |
f2ed9b32 | 716 | if (utf8_target) { |
33b8afdf JH |
717 | if (!prog->check_utf8 && prog->check_substr) |
718 | to_utf8_substr(prog); | |
719 | check = prog->check_utf8; | |
720 | } else { | |
7e0d5ad7 KW |
721 | if (!prog->check_substr && prog->check_utf8) { |
722 | if (! to_byte_substr(prog)) { | |
6b54ddc5 | 723 | NON_UTF8_TARGET_BUT_UTF8_REQUIRED(fail); |
7e0d5ad7 KW |
724 | } |
725 | } | |
33b8afdf JH |
726 | check = prog->check_substr; |
727 | } | |
274cd312 | 728 | |
1dc475d0 DM |
729 | /* dump the various substring data */ |
730 | DEBUG_OPTIMISE_MORE_r({ | |
731 | int i; | |
732 | for (i=0; i<=2; i++) { | |
733 | SV *sv = (utf8_target ? prog->substrs->data[i].utf8_substr | |
734 | : prog->substrs->data[i].substr); | |
735 | if (!sv) | |
736 | continue; | |
737 | ||
738 | PerlIO_printf(Perl_debug_log, | |
739 | " substrs[%d]: min=%"IVdf" max=%"IVdf" end shift=%"IVdf | |
740 | " useful=%"IVdf" utf8=%d [%s]\n", | |
741 | i, | |
742 | (IV)prog->substrs->data[i].min_offset, | |
743 | (IV)prog->substrs->data[i].max_offset, | |
744 | (IV)prog->substrs->data[i].end_shift, | |
745 | BmUSEFUL(sv), | |
746 | utf8_target ? 1 : 0, | |
747 | SvPEEK(sv)); | |
748 | } | |
749 | }); | |
750 | ||
8e1490ee | 751 | if (prog->intflags & PREGf_ANCH) { /* Match at \G, beg-of-str or after \n */ |
9fc7410e DM |
752 | |
753 | /* ml_anch: check after \n? | |
754 | * | |
755 | * A note about IMPLICIT: on an un-anchored pattern beginning | |
756 | * with /.*.../, these flags will have been added by the | |
757 | * compiler: | |
758 | * /.*abc/, /.*abc/m: PREGf_IMPLICIT | PREGf_ANCH_MBOL | |
759 | * /.*abc/s: PREGf_IMPLICIT | PREGf_ANCH_SBOL | |
760 | */ | |
7d2d37f5 DM |
761 | ml_anch = (prog->intflags & PREGf_ANCH_MBOL) |
762 | && !(prog->intflags & PREGf_IMPLICIT); | |
cad2e5aa | 763 | |
343c8a29 | 764 | if (!ml_anch && !(prog->intflags & PREGf_IMPLICIT)) { |
c889ccc8 DM |
765 | /* we are only allowed to match at BOS or \G */ |
766 | ||
57fcbfa7 | 767 | /* trivially reject if there's a BOS anchor and we're not at BOS. |
7bb3b9eb DM |
768 | * |
769 | * Note that we don't try to do a similar quick reject for | |
770 | * \G, since generally the caller will have calculated strpos | |
771 | * based on pos() and gofs, so the string is already correctly | |
772 | * anchored by definition; and handling the exceptions would | |
773 | * be too fiddly (e.g. REXEC_IGNOREPOS). | |
57fcbfa7 | 774 | */ |
7bb3b9eb | 775 | if ( strpos != strbeg |
d3d47aac | 776 | && (prog->intflags & PREGf_ANCH_SBOL)) |
c889ccc8 DM |
777 | { |
778 | DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, | |
1dc475d0 | 779 | " Not at start...\n")); |
c889ccc8 DM |
780 | goto fail; |
781 | } | |
782 | ||
a5d12a4b DM |
783 | /* in the presence of an anchor, the anchored (relative to the |
784 | * start of the regex) substr must also be anchored relative | |
66b7ec5c DM |
785 | * to strpos. So quickly reject if substr isn't found there. |
786 | * This works for \G too, because the caller will already have | |
787 | * subtracted gofs from pos, and gofs is the offset from the | |
788 | * \G to the start of the regex. For example, in /.abc\Gdef/, | |
789 | * where substr="abcdef", pos()=3, gofs=4, offset_min=1: | |
790 | * caller will have set strpos=pos()-4; we look for the substr | |
791 | * at position pos()-4+1, which lines up with the "a" */ | |
a5d12a4b | 792 | |
c889ccc8 | 793 | if (prog->check_offset_min == prog->check_offset_max |
d0d44648 | 794 | && !(prog->intflags & PREGf_CANY_SEEN)) |
c889ccc8 DM |
795 | { |
796 | /* Substring at constant offset from beg-of-str... */ | |
d307bf57 | 797 | SSize_t slen = SvCUR(check); |
343c8a29 | 798 | char *s = HOP3c(strpos, prog->check_offset_min, strend); |
1de06328 | 799 | |
1dc475d0 DM |
800 | DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, |
801 | " Looking for check substr at fixed offset %"IVdf"...\n", | |
802 | (IV)prog->check_offset_min)); | |
803 | ||
7742aa66 DM |
804 | if (SvTAIL(check)) { |
805 | /* In this case, the regex is anchored at the end too. | |
806 | * Unless it's a multiline match, the lengths must match | |
807 | * exactly, give or take a \n. NB: slen >= 1 since | |
808 | * the last char of check is \n */ | |
809 | if (!multiline | |
810 | && ( strend - s > slen | |
811 | || strend - s < slen - 1 | |
812 | || (strend - s == slen && strend[-1] != '\n'))) | |
c889ccc8 DM |
813 | { |
814 | DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, | |
1dc475d0 | 815 | " String too long...\n")); |
c889ccc8 DM |
816 | goto fail_finish; |
817 | } | |
818 | /* Now should match s[0..slen-2] */ | |
819 | slen--; | |
c889ccc8 | 820 | } |
d307bf57 DM |
821 | if (slen && (*SvPVX_const(check) != *s |
822 | || (slen > 1 && memNE(SvPVX_const(check), s, slen)))) | |
823 | { | |
824 | DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, | |
1dc475d0 | 825 | " String not equal...\n")); |
d307bf57 DM |
826 | goto fail_finish; |
827 | } | |
c889ccc8 DM |
828 | |
829 | check_at = s; | |
830 | goto success_at_start; | |
cad2e5aa | 831 | } |
cad2e5aa | 832 | } |
cad2e5aa | 833 | } |
0fc004dd | 834 | |
c0e0ec46 | 835 | end_shift = prog->check_end_shift; |
cad2e5aa | 836 | |
19188028 | 837 | #ifdef DEBUGGING /* 7/99: reports of failure (with the older version) */ |
0033605d | 838 | if (end_shift < 0) |
1de06328 | 839 | Perl_croak(aTHX_ "panic: end_shift: %"IVdf" pattern:\n%s\n ", |
220fc49f | 840 | (IV)end_shift, RX_PRECOMP(prog)); |
2c2d71f5 JH |
841 | #endif |
842 | ||
2c2d71f5 | 843 | restart: |
1de06328 | 844 | |
66b7ec5c DM |
845 | /* This is the (re)entry point of the main loop in this function. |
846 | * The goal of this loop is to: | |
847 | * 1) find the "check" substring in the region rx_origin..strend | |
848 | * (adjusted by start_shift / end_shift). If not found, reject | |
849 | * immediately. | |
850 | * 2) If it exists, look for the "other" substr too if defined; for | |
851 | * example, if the check substr maps to the anchored substr, then | |
852 | * check the floating substr, and vice-versa. If not found, go | |
853 | * back to (1) with rx_origin suitably incremented. | |
854 | * 3) If we find an rx_origin position that doesn't contradict | |
855 | * either of the substrings, then check the possible additional | |
856 | * constraints on rx_origin of /^.../m or a known start class. | |
857 | * If these fail, then depending on which constraints fail, jump | |
858 | * back to here, or to various other re-entry points further along | |
859 | * that skip some of the first steps. | |
860 | * 4) If we pass all those tests, update the BmUSEFUL() count on the | |
861 | * substring. If the start position was determined to be at the | |
862 | * beginning of the string - so, not rejected, but not optimised, | |
863 | * since we have to run regmatch from position 0 - decrement the | |
864 | * BmUSEFUL() count. Otherwise increment it. | |
865 | */ | |
866 | ||
1a4edc3c DM |
867 | |
868 | /* first, look for the 'check' substring */ | |
869 | ||
1de06328 | 870 | { |
c33e64f0 FC |
871 | U8* start_point; |
872 | U8* end_point; | |
c889ccc8 | 873 | |
c889ccc8 | 874 | DEBUG_OPTIMISE_MORE_r({ |
1dc475d0 | 875 | PerlIO_printf(Perl_debug_log, |
ae5d4331 | 876 | " At restart: rx_origin=%"IVdf" Check offset min: %"IVdf |
1dc475d0 | 877 | " Start shift: %"IVdf" End shift %"IVdf |
4d281893 | 878 | " Real end Shift: %"IVdf"\n", |
197641b6 | 879 | (IV)(rx_origin - strpos), |
c889ccc8 | 880 | (IV)prog->check_offset_min, |
12fbc530 DM |
881 | (IV)start_shift, |
882 | (IV)end_shift, | |
c889ccc8 DM |
883 | (IV)prog->check_end_shift); |
884 | }); | |
1de06328 | 885 | |
0d331aaf | 886 | if (prog->intflags & PREGf_CANY_SEEN) { |
0fc004dd | 887 | start_point= (U8*)(rx_origin + start_shift); |
12fbc530 | 888 | end_point= (U8*)(strend - end_shift); |
557f47af DM |
889 | if (start_point > end_point) |
890 | goto fail_finish; | |
1de06328 | 891 | } else { |
557f47af DM |
892 | end_point = HOP3(strend, -end_shift, strbeg); |
893 | start_point = HOPMAYBE3(rx_origin, start_shift, end_point); | |
894 | if (!start_point) | |
895 | goto fail_finish; | |
1de06328 | 896 | } |
c889ccc8 | 897 | |
557f47af | 898 | |
e0362b86 | 899 | /* If the regex is absolutely anchored to either the start of the |
d3d47aac | 900 | * string (SBOL) or to pos() (ANCH_GPOS), then |
e0362b86 DM |
901 | * check_offset_max represents an upper bound on the string where |
902 | * the substr could start. For the ANCH_GPOS case, we assume that | |
903 | * the caller of intuit will have already set strpos to | |
904 | * pos()-gofs, so in this case strpos + offset_max will still be | |
905 | * an upper bound on the substr. | |
906 | */ | |
c19c836a DM |
907 | if (!ml_anch |
908 | && prog->intflags & PREGf_ANCH | |
e0362b86 | 909 | && prog->check_offset_max != SSize_t_MAX) |
c19c836a | 910 | { |
1a08ba3a | 911 | SSize_t len = SvCUR(check) - !!SvTAIL(check); |
e0362b86 DM |
912 | const char * const anchor = |
913 | (prog->intflags & PREGf_ANCH_GPOS ? strpos : strbeg); | |
914 | ||
915 | /* do a bytes rather than chars comparison. It's conservative; | |
916 | * so it skips doing the HOP if the result can't possibly end | |
917 | * up earlier than the old value of end_point. | |
918 | */ | |
919 | if ((char*)end_point - anchor > prog->check_offset_max) { | |
920 | end_point = HOP3lim((U8*)anchor, | |
921 | prog->check_offset_max, | |
922 | end_point -len) | |
923 | + len; | |
924 | } | |
d6ef1678 DM |
925 | } |
926 | ||
6bda09f9 | 927 | DEBUG_OPTIMISE_MORE_r({ |
1dc475d0 | 928 | PerlIO_printf(Perl_debug_log, " fbm_instr len=%d str=<%.*s>\n", |
1de06328 | 929 | (int)(end_point - start_point), |
fc8cd66c | 930 | (int)(end_point - start_point) > 20 ? 20 : (int)(end_point - start_point), |
1de06328 YO |
931 | start_point); |
932 | }); | |
933 | ||
ae5d4331 | 934 | check_at = fbm_instr( start_point, end_point, |
7fba1cd6 | 935 | check, multiline ? FBMrf_MULTILINE : 0); |
c889ccc8 | 936 | |
8fd34720 DM |
937 | /* Update the count-of-usability, remove useless subpatterns, |
938 | unshift s. */ | |
939 | ||
940 | DEBUG_EXECUTE_r({ | |
941 | RE_PV_QUOTED_DECL(quoted, utf8_target, PERL_DEBUG_PAD_ZERO(0), | |
942 | SvPVX_const(check), RE_SV_DUMPLEN(check), 30); | |
943 | PerlIO_printf(Perl_debug_log, " %s %s substr %s%s%s", | |
944 | (check_at ? "Found" : "Did not find"), | |
945 | (check == (utf8_target ? prog->anchored_utf8 : prog->anchored_substr) | |
946 | ? "anchored" : "floating"), | |
947 | quoted, | |
948 | RE_SV_TAIL(check), | |
949 | (check_at ? " at offset " : "...\n") ); | |
950 | }); | |
2c2d71f5 | 951 | |
8fd34720 DM |
952 | if (!check_at) |
953 | goto fail_finish; | |
954 | /* Finish the diagnostic message */ | |
955 | DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "%ld...\n", (long)(check_at - strpos)) ); | |
2c2d71f5 | 956 | |
8fd34720 DM |
957 | /* set rx_origin to the minimum position where the regex could start |
958 | * matching, given the constraint of the just-matched check substring. | |
959 | * But don't set it lower than previously. | |
960 | */ | |
fdc003fd | 961 | |
8fd34720 DM |
962 | if (check_at - rx_origin > prog->check_offset_max) |
963 | rx_origin = HOP3c(check_at, -prog->check_offset_max, rx_origin); | |
964 | } | |
fdc003fd DM |
965 | |
966 | ||
1a4edc3c | 967 | /* now look for the 'other' substring if defined */ |
2c2d71f5 | 968 | |
6480a6c4 DM |
969 | if (utf8_target ? prog->substrs->data[other_ix].utf8_substr |
970 | : prog->substrs->data[other_ix].substr) | |
1de06328 | 971 | { |
30944b6d | 972 | /* Take into account the "other" substring. */ |
6c3343a6 DM |
973 | char *last, *last1; |
974 | char *s; | |
975 | SV* must; | |
976 | struct reg_substr_datum *other; | |
977 | ||
978 | do_other_substr: | |
979 | other = &prog->substrs->data[other_ix]; | |
980 | ||
981 | /* if "other" is anchored: | |
982 | * we've previously found a floating substr starting at check_at. | |
983 | * This means that the regex origin must lie somewhere | |
984 | * between min (rx_origin): HOP3(check_at, -check_offset_max) | |
985 | * and max: HOP3(check_at, -check_offset_min) | |
986 | * (except that min will be >= strpos) | |
987 | * So the fixed substr must lie somewhere between | |
988 | * HOP3(min, anchored_offset) | |
989 | * HOP3(max, anchored_offset) + SvCUR(substr) | |
990 | */ | |
991 | ||
992 | /* if "other" is floating | |
993 | * Calculate last1, the absolute latest point where the | |
994 | * floating substr could start in the string, ignoring any | |
995 | * constraints from the earlier fixed match. It is calculated | |
996 | * as follows: | |
997 | * | |
998 | * strend - prog->minlen (in chars) is the absolute latest | |
999 | * position within the string where the origin of the regex | |
1000 | * could appear. The latest start point for the floating | |
1001 | * substr is float_min_offset(*) on from the start of the | |
1002 | * regex. last1 simply combines thee two offsets. | |
1003 | * | |
1004 | * (*) You might think the latest start point should be | |
1005 | * float_max_offset from the regex origin, and technically | |
1006 | * you'd be correct. However, consider | |
1007 | * /a\d{2,4}bcd\w/ | |
1008 | * Here, float min, max are 3,5 and minlen is 7. | |
1009 | * This can match either | |
1010 | * /a\d\dbcd\w/ | |
1011 | * /a\d\d\dbcd\w/ | |
1012 | * /a\d\d\d\dbcd\w/ | |
1013 | * In the first case, the regex matches minlen chars; in the | |
1014 | * second, minlen+1, in the third, minlen+2. | |
1015 | * In the first case, the floating offset is 3 (which equals | |
1016 | * float_min), in the second, 4, and in the third, 5 (which | |
1017 | * equals float_max). In all cases, the floating string bcd | |
1018 | * can never start more than 4 chars from the end of the | |
1019 | * string, which equals minlen - float_min. As the substring | |
1020 | * starts to match more than float_min from the start of the | |
1021 | * regex, it makes the regex match more than minlen chars, | |
1022 | * and the two cancel each other out. So we can always use | |
1023 | * float_min - minlen, rather than float_max - minlen for the | |
1024 | * latest position in the string. | |
1025 | * | |
1026 | * Note that -minlen + float_min_offset is equivalent (AFAIKT) | |
1027 | * to CHR_SVLEN(must) - !!SvTAIL(must) + prog->float_end_shift | |
1028 | */ | |
1029 | ||
e7a14a9c | 1030 | assert(prog->minlen >= other->min_offset); |
6c3343a6 DM |
1031 | last1 = HOP3c(strend, |
1032 | other->min_offset - prog->minlen, strbeg); | |
1033 | ||
4d006249 | 1034 | if (other_ix) {/* i.e. if (other-is-float) */ |
6c3343a6 DM |
1035 | /* last is the latest point where the floating substr could |
1036 | * start, *given* any constraints from the earlier fixed | |
1037 | * match. This constraint is that the floating string starts | |
1038 | * <= float_max_offset chars from the regex origin (rx_origin). | |
1039 | * If this value is less than last1, use it instead. | |
eb3831ce | 1040 | */ |
6c3343a6 DM |
1041 | assert(rx_origin <= last1); |
1042 | last = | |
1043 | /* this condition handles the offset==infinity case, and | |
1044 | * is a short-cut otherwise. Although it's comparing a | |
1045 | * byte offset to a char length, it does so in a safe way, | |
1046 | * since 1 char always occupies 1 or more bytes, | |
1047 | * so if a string range is (last1 - rx_origin) bytes, | |
1048 | * it will be less than or equal to (last1 - rx_origin) | |
1049 | * chars; meaning it errs towards doing the accurate HOP3 | |
1050 | * rather than just using last1 as a short-cut */ | |
1051 | (last1 - rx_origin) < other->max_offset | |
1052 | ? last1 | |
1053 | : (char*)HOP3lim(rx_origin, other->max_offset, last1); | |
1054 | } | |
1055 | else { | |
1056 | assert(strpos + start_shift <= check_at); | |
1057 | last = HOP4c(check_at, other->min_offset - start_shift, | |
1058 | strbeg, strend); | |
1059 | } | |
ead917d0 | 1060 | |
6c3343a6 DM |
1061 | s = HOP3c(rx_origin, other->min_offset, strend); |
1062 | if (s < other_last) /* These positions already checked */ | |
1063 | s = other_last; | |
1064 | ||
1065 | must = utf8_target ? other->utf8_substr : other->substr; | |
1066 | assert(SvPOK(must)); | |
1067 | s = fbm_instr( | |
1068 | (unsigned char*)s, | |
1069 | (unsigned char*)last + SvCUR(must) - (SvTAIL(must)!=0), | |
1070 | must, | |
1071 | multiline ? FBMrf_MULTILINE : 0 | |
1072 | ); | |
1073 | DEBUG_EXECUTE_r({ | |
1074 | RE_PV_QUOTED_DECL(quoted, utf8_target, PERL_DEBUG_PAD_ZERO(0), | |
1075 | SvPVX_const(must), RE_SV_DUMPLEN(must), 30); | |
1076 | PerlIO_printf(Perl_debug_log, " %s %s substr %s%s", | |
1077 | s ? "Found" : "Contradicts", | |
1078 | other_ix ? "floating" : "anchored", | |
1079 | quoted, RE_SV_TAIL(must)); | |
1080 | }); | |
ead917d0 | 1081 | |
ead917d0 | 1082 | |
6c3343a6 DM |
1083 | if (!s) { |
1084 | /* last1 is latest possible substr location. If we didn't | |
1085 | * find it before there, we never will */ | |
1086 | if (last >= last1) { | |
1087 | DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, | |
1088 | ", giving up...\n")); | |
1089 | goto fail_finish; | |
ead917d0 DM |
1090 | } |
1091 | ||
6c3343a6 DM |
1092 | /* try to find the check substr again at a later |
1093 | * position. Maybe next time we'll find the "other" substr | |
1094 | * in range too */ | |
1095 | DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, | |
1096 | ", trying %s at offset %ld...\n", | |
1097 | (other_ix ? "floating" : "anchored"), | |
197641b6 | 1098 | (long)(HOP3c(check_at, 1, strend) - strpos))); |
6c3343a6 DM |
1099 | |
1100 | other_last = HOP3c(last, 1, strend) /* highest failure */; | |
1101 | rx_origin = | |
4d006249 | 1102 | other_ix /* i.e. if other-is-float */ |
6c3343a6 DM |
1103 | ? HOP3c(rx_origin, 1, strend) |
1104 | : HOP4c(last, 1 - other->min_offset, strbeg, strend); | |
1105 | goto restart; | |
1106 | } | |
1107 | else { | |
1108 | DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, " at offset %ld...\n", | |
197641b6 | 1109 | (long)(s - strpos))); |
ead917d0 | 1110 | |
4d006249 | 1111 | if (other_ix) { /* if (other-is-float) */ |
6c3343a6 DM |
1112 | /* other_last is set to s, not s+1, since its possible for |
1113 | * a floating substr to fail first time, then succeed | |
1114 | * second time at the same floating position; e.g.: | |
1115 | * "-AB--AABZ" =~ /\wAB\d*Z/ | |
1116 | * The first time round, anchored and float match at | |
1117 | * "-(AB)--AAB(Z)" then fail on the initial \w character | |
1118 | * class. Second time round, they match at "-AB--A(AB)(Z)". | |
1119 | */ | |
1120 | other_last = s; | |
ead917d0 DM |
1121 | } |
1122 | else { | |
6c3343a6 DM |
1123 | rx_origin = HOP3c(s, -other->min_offset, strbeg); |
1124 | other_last = HOP3c(s, 1, strend); | |
ead917d0 | 1125 | } |
6c3343a6 | 1126 | } |
cad2e5aa | 1127 | } |
acba93e8 DM |
1128 | else { |
1129 | DEBUG_OPTIMISE_MORE_r( | |
1130 | PerlIO_printf(Perl_debug_log, | |
1131 | " Check-only match: offset min:%"IVdf" max:%"IVdf | |
1c1c599d | 1132 | " check_at:%"IVdf" rx_origin:%"IVdf" rx_origin-check_at:%"IVdf |
acba93e8 DM |
1133 | " strend-strpos:%"IVdf"\n", |
1134 | (IV)prog->check_offset_min, | |
1135 | (IV)prog->check_offset_max, | |
1c1c599d | 1136 | (IV)(check_at-strpos), |
acba93e8 | 1137 | (IV)(rx_origin-strpos), |
1c1c599d | 1138 | (IV)(rx_origin-check_at), |
acba93e8 DM |
1139 | (IV)(strend-strpos) |
1140 | ) | |
1141 | ); | |
1142 | } | |
2c2d71f5 | 1143 | |
acba93e8 | 1144 | postprocess_substr_matches: |
0991020e | 1145 | |
1a4edc3c | 1146 | /* handle the extra constraint of /^.../m if present */ |
e3c6feb0 | 1147 | |
7d2d37f5 | 1148 | if (ml_anch && rx_origin != strbeg && rx_origin[-1] != '\n') { |
4620cb61 DM |
1149 | char *s; |
1150 | ||
a62659bd DM |
1151 | DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, |
1152 | " looking for /^/m anchor")); | |
d0880ea7 DM |
1153 | |
1154 | /* we have failed the constraint of a \n before rx_origin. | |
2e759faa DM |
1155 | * Find the next \n, if any, even if it's beyond the current |
1156 | * anchored and/or floating substrings. Whether we should be | |
1157 | * scanning ahead for the next \n or the next substr is debatable. | |
1158 | * On the one hand you'd expect rare substrings to appear less | |
1159 | * often than \n's. On the other hand, searching for \n means | |
1160 | * we're effectively flipping been check_substr and "\n" on each | |
1161 | * iteration as the current "rarest" string candidate, which | |
1162 | * means for example that we'll quickly reject the whole string if | |
1163 | * hasn't got a \n, rather than trying every substr position | |
1164 | * first | |
1165 | */ | |
d0880ea7 | 1166 | |
4620cb61 DM |
1167 | s = HOP3c(strend, - prog->minlen, strpos); |
1168 | if (s <= rx_origin || | |
1169 | ! ( rx_origin = (char *)memchr(rx_origin, '\n', s - rx_origin))) | |
1170 | { | |
d0880ea7 DM |
1171 | DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, |
1172 | " Did not find /%s^%s/m...\n", | |
1173 | PL_colors[0], PL_colors[1])); | |
a62659bd DM |
1174 | goto fail_finish; |
1175 | } | |
d0880ea7 | 1176 | |
4ada1233 DM |
1177 | /* earliest possible origin is 1 char after the \n. |
1178 | * (since *rx_origin == '\n', it's safe to ++ here rather than | |
1179 | * HOP(rx_origin, 1)) */ | |
1180 | rx_origin++; | |
d0880ea7 | 1181 | |
f4f115de | 1182 | if (prog->substrs->check_ix == 0 /* check is anchored */ |
4ada1233 | 1183 | || rx_origin >= HOP3c(check_at, - prog->check_offset_min, strpos)) |
f4f115de | 1184 | { |
d0880ea7 DM |
1185 | /* Position contradicts check-string; either because |
1186 | * check was anchored (and thus has no wiggle room), | |
4ada1233 | 1187 | * or check was float and rx_origin is above the float range */ |
d0880ea7 DM |
1188 | DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, |
1189 | " Found /%s^%s/m, restarting lookup for check-string at offset %ld...\n", | |
4ada1233 | 1190 | PL_colors[0], PL_colors[1], (long)(rx_origin - strpos))); |
d0880ea7 DM |
1191 | goto restart; |
1192 | } | |
1193 | ||
1194 | /* if we get here, the check substr must have been float, | |
2e759faa | 1195 | * is in range, and we may or may not have had an anchored |
d0880ea7 DM |
1196 | * "other" substr which still contradicts */ |
1197 | assert(prog->substrs->check_ix); /* check is float */ | |
1198 | ||
1199 | if (utf8_target ? prog->anchored_utf8 : prog->anchored_substr) { | |
1200 | /* whoops, the anchored "other" substr exists, so we still | |
1201 | * contradict. On the other hand, the float "check" substr | |
1202 | * didn't contradict, so just retry the anchored "other" | |
1203 | * substr */ | |
1204 | DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, | |
1205 | " Found /%s^%s/m at offset %ld, rescanning for anchored from offset %ld...\n", | |
1206 | PL_colors[0], PL_colors[1], | |
1207 | (long)(rx_origin - strpos), | |
1208 | (long)(rx_origin - strpos + prog->anchored_offset))); | |
1209 | goto do_other_substr; | |
1210 | } | |
1211 | ||
1212 | /* success: we don't contradict the found floating substring | |
1213 | * (and there's no anchored substr). */ | |
d0880ea7 DM |
1214 | DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, |
1215 | " Found /%s^%s/m at offset %ld...\n", | |
1216 | PL_colors[0], PL_colors[1], (long)(rx_origin - strpos))); | |
e3c6feb0 DM |
1217 | } |
1218 | else { | |
2e759faa | 1219 | DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, |
fe4f3442 | 1220 | " (multiline anchor test skipped)\n")); |
e3c6feb0 DM |
1221 | } |
1222 | ||
ffad1e6a | 1223 | success_at_start: |
e3c6feb0 | 1224 | |
cad2e5aa | 1225 | |
dd170ff5 DM |
1226 | /* if we have a starting character class, then test that extra constraint. |
1227 | * (trie stclasses are too expensive to use here, we are better off to | |
1228 | * leave it to regmatch itself) */ | |
1229 | ||
f8fc2ecf | 1230 | if (progi->regstclass && PL_regkind[OP(progi->regstclass)]!=TRIE) { |
f8fc2ecf | 1231 | const U8* const str = (U8*)STRING(progi->regstclass); |
0991020e | 1232 | |
2c75e362 | 1233 | /* XXX this value could be pre-computed */ |
f8fc2ecf | 1234 | const int cl_l = (PL_regkind[OP(progi->regstclass)] == EXACT |
2c75e362 DM |
1235 | ? (reginfo->is_utf8_pat |
1236 | ? utf8_distance(str + STR_LEN(progi->regstclass), str) | |
1237 | : STR_LEN(progi->regstclass)) | |
66e933ab | 1238 | : 1); |
1de06328 | 1239 | char * endpos; |
fa3bb21d | 1240 | char *s; |
000dfd2d DM |
1241 | /* latest pos that a matching float substr constrains rx start to */ |
1242 | char *rx_max_float = NULL; | |
1243 | ||
c75a3985 DM |
1244 | /* if the current rx_origin is anchored, either by satisfying an |
1245 | * anchored substring constraint, or a /^.../m constraint, then we | |
1246 | * can reject the current origin if the start class isn't found | |
1247 | * at the current position. If we have a float-only match, then | |
1248 | * rx_origin is constrained to a range; so look for the start class | |
1249 | * in that range. if neither, then look for the start class in the | |
1250 | * whole rest of the string */ | |
1251 | ||
dd170ff5 DM |
1252 | /* XXX DAPM it's not clear what the minlen test is for, and why |
1253 | * it's not used in the floating case. Nothing in the test suite | |
1254 | * causes minlen == 0 here. See <20140313134639.GS12844@iabyn.com>. | |
1255 | * Here are some old comments, which may or may not be correct: | |
1256 | * | |
1257 | * minlen == 0 is possible if regstclass is \b or \B, | |
1258 | * and the fixed substr is ''$. | |
1259 | * Since minlen is already taken into account, rx_origin+1 is | |
1260 | * before strend; accidentally, minlen >= 1 guaranties no false | |
1261 | * positives at rx_origin + 1 even for \b or \B. But (minlen? 1 : | |
1262 | * 0) below assumes that regstclass does not come from lookahead... | |
1263 | * If regstclass takes bytelength more than 1: If charlength==1, OK. | |
1264 | * This leaves EXACTF-ish only, which are dealt with in | |
1265 | * find_byclass(). | |
1266 | */ | |
1267 | ||
7d2d37f5 | 1268 | if (prog->anchored_substr || prog->anchored_utf8 || ml_anch) |
fa3bb21d | 1269 | endpos= HOP3c(rx_origin, (prog->minlen ? cl_l : 0), strend); |
000dfd2d DM |
1270 | else if (prog->float_substr || prog->float_utf8) { |
1271 | rx_max_float = HOP3c(check_at, -start_shift, strbeg); | |
1272 | endpos= HOP3c(rx_max_float, cl_l, strend); | |
1273 | } | |
1de06328 YO |
1274 | else |
1275 | endpos= strend; | |
1276 | ||
1dc475d0 DM |
1277 | DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, |
1278 | " looking for class: start_shift: %"IVdf" check_at: %"IVdf | |
c43b5520 | 1279 | " rx_origin: %"IVdf" endpos: %"IVdf"\n", |
1dc475d0 | 1280 | (IV)start_shift, (IV)(check_at - strbeg), |
c43b5520 | 1281 | (IV)(rx_origin - strbeg), (IV)(endpos - strbeg))); |
d8080198 | 1282 | |
c43b5520 | 1283 | s = find_byclass(prog, progi->regstclass, rx_origin, endpos, |
f9176b44 | 1284 | reginfo); |
be778b1a | 1285 | if (!s) { |
6eb5f6b9 | 1286 | if (endpos == strend) { |
a3621e74 | 1287 | DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log, |
1dc475d0 | 1288 | " Could not match STCLASS...\n") ); |
6eb5f6b9 JH |
1289 | goto fail; |
1290 | } | |
a3621e74 | 1291 | DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log, |
1dc475d0 | 1292 | " This position contradicts STCLASS...\n") ); |
e0eb31e7 DM |
1293 | if ((prog->intflags & PREGf_ANCH) && !ml_anch |
1294 | && !(prog->intflags & PREGf_IMPLICIT)) | |
653099ff | 1295 | goto fail; |
9fed8d02 | 1296 | |
6eb5f6b9 | 1297 | /* Contradict one of substrings */ |
97136c8a DM |
1298 | if (prog->anchored_substr || prog->anchored_utf8) { |
1299 | if (prog->substrs->check_ix == 1) { /* check is float */ | |
1300 | /* Have both, check_string is floating */ | |
1301 | assert(rx_origin + start_shift <= check_at); | |
1302 | if (rx_origin + start_shift != check_at) { | |
1303 | /* not at latest position float substr could match: | |
c75a3985 DM |
1304 | * Recheck anchored substring, but not floating. |
1305 | * The condition above is in bytes rather than | |
1306 | * chars for efficiency. It's conservative, in | |
1307 | * that it errs on the side of doing 'goto | |
1308 | * do_other_substr', where a more accurate | |
1309 | * char-based calculation will be done */ | |
97136c8a DM |
1310 | DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log, |
1311 | " Looking for anchored substr starting at offset %ld...\n", | |
1312 | (long)(other_last - strpos)) ); | |
1313 | goto do_other_substr; | |
3369914b | 1314 | } |
3369914b DM |
1315 | } |
1316 | } | |
97136c8a | 1317 | else { |
9fed8d02 DM |
1318 | /* float-only */ |
1319 | ||
7d2d37f5 | 1320 | if (ml_anch) { |
c75a3985 DM |
1321 | /* In the presence of ml_anch, we might be able to |
1322 | * find another \n without breaking the current float | |
1323 | * constraint. */ | |
1324 | ||
1325 | /* strictly speaking this should be HOP3c(..., 1, ...), | |
1326 | * but since we goto a block of code that's going to | |
1327 | * search for the next \n if any, its safe here */ | |
9fed8d02 | 1328 | rx_origin++; |
9fed8d02 DM |
1329 | DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log, |
1330 | " Looking for /%s^%s/m starting at offset %ld...\n", | |
1331 | PL_colors[0], PL_colors[1], | |
1332 | (long)(rx_origin - strpos)) ); | |
9fed8d02 | 1333 | goto postprocess_substr_matches; |
ab60c45a | 1334 | } |
c75a3985 DM |
1335 | |
1336 | /* strictly speaking this can never be true; but might | |
1337 | * be if we ever allow intuit without substrings */ | |
1338 | if (!(utf8_target ? prog->float_utf8 : prog->float_substr)) | |
9fed8d02 | 1339 | goto fail; |
c75a3985 | 1340 | |
000dfd2d | 1341 | rx_origin = rx_max_float; |
9fed8d02 DM |
1342 | } |
1343 | ||
c75a3985 DM |
1344 | /* at this point, any matching substrings have been |
1345 | * contradicted. Start again... */ | |
1346 | ||
9fed8d02 | 1347 | rx_origin = HOP3c(rx_origin, 1, strend); |
557f47af DM |
1348 | |
1349 | /* uses bytes rather than char calculations for efficiency. | |
1350 | * It's conservative: it errs on the side of doing 'goto restart', | |
1351 | * where there is code that does a proper char-based test */ | |
9fed8d02 | 1352 | if (rx_origin + start_shift + end_shift > strend) { |
40268e5b | 1353 | DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log, |
9fed8d02 DM |
1354 | " Could not match STCLASS...\n") ); |
1355 | goto fail; | |
1356 | } | |
1357 | DEBUG_EXECUTE_r( PerlIO_printf(Perl_debug_log, | |
1358 | " Looking for %s substr starting at offset %ld...\n", | |
1359 | (prog->substrs->check_ix ? "floating" : "anchored"), | |
1360 | (long)(rx_origin + start_shift - strpos)) ); | |
1361 | goto restart; | |
6eb5f6b9 | 1362 | } |
9fed8d02 | 1363 | |
c75a3985 DM |
1364 | /* Success !!! */ |
1365 | ||
5f9c6575 | 1366 | if (rx_origin != s) { |
a3621e74 | 1367 | DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, |
1dc475d0 | 1368 | " By STCLASS: moving %ld --> %ld\n", |
5f9c6575 | 1369 | (long)(rx_origin - strpos), (long)(s - strpos)) |
b7953727 JH |
1370 | ); |
1371 | } | |
1372 | else { | |
a3621e74 | 1373 | DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, |
1dc475d0 | 1374 | " Does not contradict STCLASS...\n"); |
b7953727 JH |
1375 | ); |
1376 | } | |
6eb5f6b9 | 1377 | } |
ffad1e6a DM |
1378 | |
1379 | /* Decide whether using the substrings helped */ | |
1380 | ||
1381 | if (rx_origin != strpos) { | |
1382 | /* Fixed substring is found far enough so that the match | |
1383 | cannot start at strpos. */ | |
1384 | ||
1385 | DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, " try at offset...\n")); | |
1386 | ++BmUSEFUL(utf8_target ? prog->check_utf8 : prog->check_substr); /* hooray/5 */ | |
1387 | } | |
1388 | else { | |
70563e16 DM |
1389 | /* The found rx_origin position does not prohibit matching at |
1390 | * strpos, so calling intuit didn't gain us anything. Decrement | |
1391 | * the BmUSEFUL() count on the check substring, and if we reach | |
1392 | * zero, free it. */ | |
1393 | if (!(prog->intflags & PREGf_NAUGHTY) | |
ffad1e6a DM |
1394 | && (utf8_target ? ( |
1395 | prog->check_utf8 /* Could be deleted already */ | |
1396 | && --BmUSEFUL(prog->check_utf8) < 0 | |
1397 | && (prog->check_utf8 == prog->float_utf8) | |
1398 | ) : ( | |
1399 | prog->check_substr /* Could be deleted already */ | |
1400 | && --BmUSEFUL(prog->check_substr) < 0 | |
1401 | && (prog->check_substr == prog->float_substr) | |
1402 | ))) | |
1403 | { | |
1404 | /* If flags & SOMETHING - do not do it many times on the same match */ | |
1405 | DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, " ... Disabling check substring...\n")); | |
1406 | /* XXX Does the destruction order has to change with utf8_target? */ | |
1407 | SvREFCNT_dec(utf8_target ? prog->check_utf8 : prog->check_substr); | |
1408 | SvREFCNT_dec(utf8_target ? prog->check_substr : prog->check_utf8); | |
1409 | prog->check_substr = prog->check_utf8 = NULL; /* disable */ | |
1410 | prog->float_substr = prog->float_utf8 = NULL; /* clear */ | |
1411 | check = NULL; /* abort */ | |
ffad1e6a DM |
1412 | /* XXXX This is a remnant of the old implementation. It |
1413 | looks wasteful, since now INTUIT can use many | |
1414 | other heuristics. */ | |
1415 | prog->extflags &= ~RXf_USE_INTUIT; | |
ffad1e6a DM |
1416 | } |
1417 | } | |
1418 | ||
1419 | DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, | |
1420 | "Intuit: %sSuccessfully guessed:%s match at offset %ld\n", | |
1421 | PL_colors[4], PL_colors[5], (long)(rx_origin - strpos)) ); | |
1422 | ||
c765d6e0 | 1423 | return rx_origin; |
2c2d71f5 JH |
1424 | |
1425 | fail_finish: /* Substring not found */ | |
33b8afdf | 1426 | if (prog->check_substr || prog->check_utf8) /* could be removed already */ |
f2ed9b32 | 1427 | BmUSEFUL(utf8_target ? prog->check_utf8 : prog->check_substr) += 5; /* hooray */ |
cad2e5aa | 1428 | fail: |
a3621e74 | 1429 | DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "%sMatch rejected by optimizer%s\n", |
e4584336 | 1430 | PL_colors[4], PL_colors[5])); |
bd61b366 | 1431 | return NULL; |
cad2e5aa | 1432 | } |
9661b544 | 1433 | |
70563e16 | 1434 | |
a0a388a1 | 1435 | #define DECL_TRIE_TYPE(scan) \ |
e7fd4aa1 | 1436 | const enum { trie_plain, trie_utf8, trie_utf8_fold, trie_latin_utf8_fold, \ |
a4525e78 KW |
1437 | trie_utf8_exactfa_fold, trie_latin_utf8_exactfa_fold, \ |
1438 | trie_utf8l, trie_flu8 } \ | |
e7fd4aa1 KW |
1439 | trie_type = ((scan->flags == EXACT) \ |
1440 | ? (utf8_target ? trie_utf8 : trie_plain) \ | |
a4525e78 KW |
1441 | : (scan->flags == EXACTL) \ |
1442 | ? (utf8_target ? trie_utf8l : trie_plain) \ | |
1443 | : (scan->flags == EXACTFA) \ | |
1444 | ? (utf8_target \ | |
1445 | ? trie_utf8_exactfa_fold \ | |
1446 | : trie_latin_utf8_exactfa_fold) \ | |
1447 | : (scan->flags == EXACTFLU8 \ | |
1448 | ? trie_flu8 \ | |
1449 | : (utf8_target \ | |
1450 | ? trie_utf8_fold \ | |
1451 | : trie_latin_utf8_fold))) | |
fab2782b | 1452 | |
fd3249ee | 1453 | #define REXEC_TRIE_READ_CHAR(trie_type, trie, widecharmap, uc, uscan, len, uvc, charid, foldlen, foldbuf, uniflags) \ |
baa60164 | 1454 | STMT_START { \ |
fab2782b | 1455 | STRLEN skiplen; \ |
baa60164 | 1456 | U8 flags = FOLD_FLAGS_FULL; \ |
fab2782b | 1457 | switch (trie_type) { \ |
a4525e78 KW |
1458 | case trie_flu8: \ |
1459 | goto do_trie_utf8_fold; \ | |
31f05a37 | 1460 | case trie_utf8_exactfa_fold: \ |
baa60164 | 1461 | flags |= FOLD_FLAGS_NOMIX_ASCII; \ |
924ba076 | 1462 | /* FALLTHROUGH */ \ |
fab2782b | 1463 | case trie_utf8_fold: \ |
a4525e78 | 1464 | do_trie_utf8_fold: \ |
fab2782b | 1465 | if ( foldlen>0 ) { \ |
c80e42f3 | 1466 | uvc = utf8n_to_uvchr( (const U8*) uscan, UTF8_MAXLEN, &len, uniflags ); \ |
fab2782b YO |
1467 | foldlen -= len; \ |
1468 | uscan += len; \ | |
1469 | len=0; \ | |
1470 | } else { \ | |
445bf929 | 1471 | uvc = _to_utf8_fold_flags( (const U8*) uc, foldbuf, &foldlen, flags); \ |
fab2782b YO |
1472 | len = UTF8SKIP(uc); \ |
1473 | skiplen = UNISKIP( uvc ); \ | |
1474 | foldlen -= skiplen; \ | |
1475 | uscan = foldbuf + skiplen; \ | |
1476 | } \ | |
1477 | break; \ | |
baa60164 KW |
1478 | case trie_latin_utf8_exactfa_fold: \ |
1479 | flags |= FOLD_FLAGS_NOMIX_ASCII; \ | |
924ba076 | 1480 | /* FALLTHROUGH */ \ |
fab2782b YO |
1481 | case trie_latin_utf8_fold: \ |
1482 | if ( foldlen>0 ) { \ | |
c80e42f3 | 1483 | uvc = utf8n_to_uvchr( (const U8*) uscan, UTF8_MAXLEN, &len, uniflags ); \ |
fab2782b YO |
1484 | foldlen -= len; \ |
1485 | uscan += len; \ | |
1486 | len=0; \ | |
1487 | } else { \ | |
1488 | len = 1; \ | |
31f05a37 | 1489 | uvc = _to_fold_latin1( (U8) *uc, foldbuf, &foldlen, flags); \ |
fab2782b YO |
1490 | skiplen = UNISKIP( uvc ); \ |
1491 | foldlen -= skiplen; \ | |
1492 | uscan = foldbuf + skiplen; \ | |
1493 | } \ | |
1494 | break; \ | |
a4525e78 | 1495 | case trie_utf8l: \ |
fab2782b | 1496 | case trie_utf8: \ |
c80e42f3 | 1497 | uvc = utf8n_to_uvchr( (const U8*) uc, UTF8_MAXLEN, &len, uniflags ); \ |
fab2782b YO |
1498 | break; \ |
1499 | case trie_plain: \ | |
1500 | uvc = (UV)*uc; \ | |
1501 | len = 1; \ | |
1502 | } \ | |
1503 | if (uvc < 256) { \ | |
1504 | charid = trie->charmap[ uvc ]; \ | |
1505 | } \ | |
1506 | else { \ | |
1507 | charid = 0; \ | |
1508 | if (widecharmap) { \ | |
1509 | SV** const svpp = hv_fetch(widecharmap, \ | |
1510 | (char*)&uvc, sizeof(UV), 0); \ | |
1511 | if (svpp) \ | |
1512 | charid = (U16)SvIV(*svpp); \ | |
1513 | } \ | |
1514 | } \ | |
4cadc6a9 YO |
1515 | } STMT_END |
1516 | ||
ae7c5b9b KW |
1517 | #define DUMP_EXEC_POS(li,s,doutf8) \ |
1518 | dump_exec_pos(li,s,(reginfo->strend),(reginfo->strbeg), \ | |
1519 | startpos, doutf8) | |
1520 | ||
c84a03c5 | 1521 | #define REXEC_FBC_EXACTISH_SCAN(COND) \ |
4cadc6a9 YO |
1522 | STMT_START { \ |
1523 | while (s <= e) { \ | |
c84a03c5 | 1524 | if ( (COND) \ |
fac1af77 | 1525 | && (ln == 1 || folder(s, pat_string, ln)) \ |
02d5137b | 1526 | && (reginfo->intuit || regtry(reginfo, &s)) )\ |
4cadc6a9 YO |
1527 | goto got_it; \ |
1528 | s++; \ | |
1529 | } \ | |
1530 | } STMT_END | |
1531 | ||
c84a03c5 | 1532 | #define REXEC_FBC_UTF8_SCAN(CODE) \ |
4cadc6a9 | 1533 | STMT_START { \ |
9a902117 | 1534 | while (s < strend) { \ |
c84a03c5 | 1535 | CODE \ |
9a902117 | 1536 | s += UTF8SKIP(s); \ |
4cadc6a9 YO |
1537 | } \ |
1538 | } STMT_END | |
1539 | ||
c84a03c5 | 1540 | #define REXEC_FBC_SCAN(CODE) \ |
4cadc6a9 YO |
1541 | STMT_START { \ |
1542 | while (s < strend) { \ | |
c84a03c5 | 1543 | CODE \ |
4cadc6a9 YO |
1544 | s++; \ |
1545 | } \ | |
1546 | } STMT_END | |
1547 | ||
05bd126c KW |
1548 | #define REXEC_FBC_UTF8_CLASS_SCAN(COND) \ |
1549 | REXEC_FBC_UTF8_SCAN( /* Loops while (s < strend) */ \ | |
1550 | if (COND) { \ | |
1551 | if (tmp && (reginfo->intuit || regtry(reginfo, &s))) \ | |
1552 | goto got_it; \ | |
1553 | else \ | |
1554 | tmp = doevery; \ | |
1555 | } \ | |
1556 | else \ | |
1557 | tmp = 1; \ | |
4cadc6a9 YO |
1558 | ) |
1559 | ||
05bd126c KW |
1560 | #define REXEC_FBC_CLASS_SCAN(COND) \ |
1561 | REXEC_FBC_SCAN( /* Loops while (s < strend) */ \ | |
1562 | if (COND) { \ | |
1563 | if (tmp && (reginfo->intuit || regtry(reginfo, &s))) \ | |
1564 | goto got_it; \ | |
1565 | else \ | |
1566 | tmp = doevery; \ | |
1567 | } \ | |
1568 | else \ | |
1569 | tmp = 1; \ | |
4cadc6a9 YO |
1570 | ) |
1571 | ||
c84a03c5 | 1572 | #define REXEC_FBC_CSCAN(CONDUTF8,COND) \ |
baa60164 | 1573 | if (utf8_target) { \ |
c84a03c5 | 1574 | REXEC_FBC_UTF8_CLASS_SCAN(CONDUTF8); \ |
e1d1eefb YO |
1575 | } \ |
1576 | else { \ | |
c84a03c5 | 1577 | REXEC_FBC_CLASS_SCAN(COND); \ |
d981ef24 | 1578 | } |
05bd126c | 1579 | |
05bd126c KW |
1580 | /* The three macros below are slightly different versions of the same logic. |
1581 | * | |
1582 | * The first is for /a and /aa when the target string is UTF-8. This can only | |
1583 | * match ascii, but it must advance based on UTF-8. The other two handle the | |
1584 | * non-UTF-8 and the more generic UTF-8 cases. In all three, we are looking | |
1585 | * for the boundary (or non-boundary) between a word and non-word character. | |
1586 | * The utf8 and non-utf8 cases have the same logic, but the details must be | |
1587 | * different. Find the "wordness" of the character just prior to this one, and | |
1588 | * compare it with the wordness of this one. If they differ, we have a | |
1589 | * boundary. At the beginning of the string, pretend that the previous | |
1590 | * character was a new-line. | |
1591 | * | |
1592 | * All these macros uncleanly have side-effects with each other and outside | |
1593 | * variables. So far it's been too much trouble to clean-up | |
1594 | * | |
1595 | * TEST_NON_UTF8 is the macro or function to call to test if its byte input is | |
1596 | * a word character or not. | |
1597 | * IF_SUCCESS is code to do if it finds that we are at a boundary between | |
1598 | * word/non-word | |
1599 | * IF_FAIL is code to do if we aren't at a boundary between word/non-word | |
1600 | * | |
1601 | * Exactly one of the two IF_FOO parameters is a no-op, depending on whether we | |
1602 | * are looking for a boundary or for a non-boundary. If we are looking for a | |
1603 | * boundary, we want IF_FAIL to be the no-op, and for IF_SUCCESS to go out and | |
1604 | * see if this tentative match actually works, and if so, to quit the loop | |
1605 | * here. And vice-versa if we are looking for a non-boundary. | |
1606 | * | |
1607 | * 'tmp' below in the next three macros in the REXEC_FBC_SCAN and | |
1608 | * REXEC_FBC_UTF8_SCAN loops is a loop invariant, a bool giving the return of | |
1609 | * TEST_NON_UTF8(s-1). To see this, note that that's what it is defined to be | |
1610 | * at entry to the loop, and to get to the IF_FAIL branch, tmp must equal | |
1611 | * TEST_NON_UTF8(s), and in the opposite branch, IF_SUCCESS, tmp is that | |
1612 | * complement. But in that branch we complement tmp, meaning that at the | |
1613 | * bottom of the loop tmp is always going to be equal to TEST_NON_UTF8(s), | |
1614 | * which means at the top of the loop in the next iteration, it is | |
1615 | * TEST_NON_UTF8(s-1) */ | |
b2f4e957 | 1616 | #define FBC_UTF8_A(TEST_NON_UTF8, IF_SUCCESS, IF_FAIL) \ |
05bd126c KW |
1617 | tmp = (s != reginfo->strbeg) ? UCHARAT(s - 1) : '\n'; \ |
1618 | tmp = TEST_NON_UTF8(tmp); \ | |
1619 | REXEC_FBC_UTF8_SCAN( /* advances s while s < strend */ \ | |
1620 | if (tmp == ! TEST_NON_UTF8((U8) *s)) { \ | |
1621 | tmp = !tmp; \ | |
1622 | IF_SUCCESS; /* Is a boundary if values for s-1 and s differ */ \ | |
1623 | } \ | |
1624 | else { \ | |
1625 | IF_FAIL; \ | |
1626 | } \ | |
1627 | ); \ | |
1628 | ||
1629 | /* Like FBC_UTF8_A, but TEST_UV is a macro which takes a UV as its input, and | |
1630 | * TEST_UTF8 is a macro that for the same input code points returns identically | |
1631 | * to TEST_UV, but takes a pointer to a UTF-8 encoded string instead */ | |
236d82fd | 1632 | #define FBC_UTF8(TEST_UV, TEST_UTF8, IF_SUCCESS, IF_FAIL) \ |
05bd126c KW |
1633 | if (s == reginfo->strbeg) { \ |
1634 | tmp = '\n'; \ | |
1635 | } \ | |
1636 | else { /* Back-up to the start of the previous character */ \ | |
1637 | U8 * const r = reghop3((U8*)s, -1, (U8*)reginfo->strbeg); \ | |
1638 | tmp = utf8n_to_uvchr(r, (U8*) reginfo->strend - r, \ | |
3db24e1e | 1639 | 0, UTF8_ALLOW_DEFAULT); \ |
05bd126c KW |
1640 | } \ |
1641 | tmp = TEST_UV(tmp); \ | |
1642 | LOAD_UTF8_CHARCLASS_ALNUM(); \ | |
1643 | REXEC_FBC_UTF8_SCAN( /* advances s while s < strend */ \ | |
1644 | if (tmp == ! (TEST_UTF8((U8 *) s))) { \ | |
1645 | tmp = !tmp; \ | |
1646 | IF_SUCCESS; \ | |
1647 | } \ | |
1648 | else { \ | |
1649 | IF_FAIL; \ | |
1650 | } \ | |
1651 | ); | |
cfaf538b | 1652 | |
05bd126c KW |
1653 | /* Like the above two macros. UTF8_CODE is the complete code for handling |
1654 | * UTF-8. Common to the BOUND and NBOUND cases, set-up by the FBC_BOUND, etc | |
1655 | * macros below */ | |
baa60164 | 1656 | #define FBC_BOUND_COMMON(UTF8_CODE, TEST_NON_UTF8, IF_SUCCESS, IF_FAIL) \ |
63ac0dad | 1657 | if (utf8_target) { \ |
05bd126c | 1658 | UTF8_CODE \ |
63ac0dad KW |
1659 | } \ |
1660 | else { /* Not utf8 */ \ | |
9d9163fb | 1661 | tmp = (s != reginfo->strbeg) ? UCHARAT(s - 1) : '\n'; \ |
63ac0dad | 1662 | tmp = TEST_NON_UTF8(tmp); \ |
05bd126c | 1663 | REXEC_FBC_SCAN( /* advances s while s < strend */ \ |
63ac0dad | 1664 | if (tmp == ! TEST_NON_UTF8((U8) *s)) { \ |
63ac0dad | 1665 | IF_SUCCESS; \ |
760cfa8e | 1666 | tmp = !tmp; \ |
63ac0dad KW |
1667 | } \ |
1668 | else { \ | |
1669 | IF_FAIL; \ | |
1670 | } \ | |
1671 | ); \ | |
1672 | } \ | |
c8519dc7 KW |
1673 | /* Here, things have been set up by the previous code so that tmp is the \ |
1674 | * return of TEST_NON_UTF(s-1) or TEST_UTF8(s-1) (depending on the \ | |
1675 | * utf8ness of the target). We also have to check if this matches against \ | |
1676 | * the EOS, which we treat as a \n (which is the same value in both UTF-8 \ | |
1677 | * or non-UTF8, so can use the non-utf8 test condition even for a UTF-8 \ | |
1678 | * string */ \ | |
1679 | if (tmp == ! TEST_NON_UTF8('\n')) { \ | |
1680 | IF_SUCCESS; \ | |
1681 | } \ | |
1682 | else { \ | |
1683 | IF_FAIL; \ | |
1684 | } | |
63ac0dad | 1685 | |
ae7c5b9b KW |
1686 | /* This is the macro to use when we want to see if something that looks like it |
1687 | * could match, actually does, and if so exits the loop */ | |
1688 | #define REXEC_FBC_TRYIT \ | |
1689 | if ((reginfo->intuit || regtry(reginfo, &s))) \ | |
1690 | goto got_it | |
1691 | ||
1692 | /* The only difference between the BOUND and NBOUND cases is that | |
1693 | * REXEC_FBC_TRYIT is called when matched in BOUND, and when non-matched in | |
1694 | * NBOUND. This is accomplished by passing it as either the if or else clause, | |
1695 | * with the other one being empty (PLACEHOLDER is defined as empty). | |
1696 | * | |
1697 | * The TEST_FOO parameters are for operating on different forms of input, but | |
1698 | * all should be ones that return identically for the same underlying code | |
1699 | * points */ | |
1700 | #define FBC_BOUND(TEST_NON_UTF8, TEST_UV, TEST_UTF8) \ | |
1701 | FBC_BOUND_COMMON( \ | |
1702 | FBC_UTF8(TEST_UV, TEST_UTF8, REXEC_FBC_TRYIT, PLACEHOLDER), \ | |
1703 | TEST_NON_UTF8, REXEC_FBC_TRYIT, PLACEHOLDER) | |
1704 | ||
1705 | #define FBC_BOUND_A(TEST_NON_UTF8, TEST_UV, TEST_UTF8) \ | |
1706 | FBC_BOUND_COMMON( \ | |
1707 | FBC_UTF8_A(TEST_NON_UTF8, REXEC_FBC_TRYIT, PLACEHOLDER), \ | |
1708 | TEST_NON_UTF8, REXEC_FBC_TRYIT, PLACEHOLDER) | |
1709 | ||
1710 | #define FBC_NBOUND(TEST_NON_UTF8, TEST_UV, TEST_UTF8) \ | |
1711 | FBC_BOUND_COMMON( \ | |
1712 | FBC_UTF8(TEST_UV, TEST_UTF8, PLACEHOLDER, REXEC_FBC_TRYIT), \ | |
1713 | TEST_NON_UTF8, PLACEHOLDER, REXEC_FBC_TRYIT) | |
1714 | ||
1715 | #define FBC_NBOUND_A(TEST_NON_UTF8, TEST_UV, TEST_UTF8) \ | |
1716 | FBC_BOUND_COMMON( \ | |
1717 | FBC_UTF8_A(TEST_NON_UTF8, PLACEHOLDER, REXEC_FBC_TRYIT), \ | |
1718 | TEST_NON_UTF8, PLACEHOLDER, REXEC_FBC_TRYIT) | |
1719 | ||
05bd126c | 1720 | |
786e8c11 | 1721 | /* We know what class REx starts with. Try to find this position... */ |
02d5137b | 1722 | /* if reginfo->intuit, its a dryrun */ |
786e8c11 YO |
1723 | /* annoyingly all the vars in this routine have different names from their counterparts |
1724 | in regmatch. /grrr */ | |
3c3eec57 | 1725 | STATIC char * |
07be1b83 | 1726 | S_find_byclass(pTHX_ regexp * prog, const regnode *c, char *s, |
f9176b44 | 1727 | const char *strend, regmatch_info *reginfo) |
a687059c | 1728 | { |
73104a1b KW |
1729 | dVAR; |
1730 | const I32 doevery = (prog->intflags & PREGf_SKIP) == 0; | |
1731 | char *pat_string; /* The pattern's exactish string */ | |
1732 | char *pat_end; /* ptr to end char of pat_string */ | |
1733 | re_fold_t folder; /* Function for computing non-utf8 folds */ | |
1734 | const U8 *fold_array; /* array for folding ords < 256 */ | |
1735 | STRLEN ln; | |
1736 | STRLEN lnc; | |
73104a1b KW |
1737 | U8 c1; |
1738 | U8 c2; | |
1739 | char *e; | |
1740 | I32 tmp = 1; /* Scratch variable? */ | |
ba44c216 | 1741 | const bool utf8_target = reginfo->is_utf8_target; |
73104a1b | 1742 | UV utf8_fold_flags = 0; |
f9176b44 | 1743 | const bool is_utf8_pat = reginfo->is_utf8_pat; |
3018b823 KW |
1744 | bool to_complement = FALSE; /* Invert the result? Taking the xor of this |
1745 | with a result inverts that result, as 0^1 = | |
1746 | 1 and 1^1 = 0 */ | |
1747 | _char_class_number classnum; | |
1748 | ||
73104a1b | 1749 | RXi_GET_DECL(prog,progi); |
2f7f8cb1 | 1750 | |
73104a1b | 1751 | PERL_ARGS_ASSERT_FIND_BYCLASS; |
2f7f8cb1 | 1752 | |
73104a1b KW |
1753 | /* We know what class it must start with. */ |
1754 | switch (OP(c)) { | |
a4525e78 | 1755 | case ANYOFL: |
73104a1b KW |
1756 | case ANYOF: |
1757 | if (utf8_target) { | |
1758 | REXEC_FBC_UTF8_CLASS_SCAN( | |
3db24e1e | 1759 | reginclass(prog, c, (U8*)s, (U8*) strend, utf8_target)); |
73104a1b KW |
1760 | } |
1761 | else { | |
1762 | REXEC_FBC_CLASS_SCAN(REGINCLASS(prog, c, (U8*)s)); | |
1763 | } | |
1764 | break; | |
1765 | case CANY: | |
1766 | REXEC_FBC_SCAN( | |
02d5137b | 1767 | if (tmp && (reginfo->intuit || regtry(reginfo, &s))) |
73104a1b KW |
1768 | goto got_it; |
1769 | else | |
1770 | tmp = doevery; | |
1771 | ); | |
1772 | break; | |
1773 | ||
098b07d5 KW |
1774 | case EXACTFA_NO_TRIE: /* This node only generated for non-utf8 patterns */ |
1775 | assert(! is_utf8_pat); | |
924ba076 | 1776 | /* FALLTHROUGH */ |
73104a1b | 1777 | case EXACTFA: |
984e6dd1 | 1778 | if (is_utf8_pat || utf8_target) { |
73104a1b KW |
1779 | utf8_fold_flags = FOLDEQ_UTF8_NOMIX_ASCII; |
1780 | goto do_exactf_utf8; | |
1781 | } | |
1782 | fold_array = PL_fold_latin1; /* Latin1 folds are not affected by */ | |
1783 | folder = foldEQ_latin1; /* /a, except the sharp s one which */ | |
1784 | goto do_exactf_non_utf8; /* isn't dealt with by these */ | |
77a6d856 | 1785 | |
2fdb7295 KW |
1786 | case EXACTF: /* This node only generated for non-utf8 patterns */ |
1787 | assert(! is_utf8_pat); | |
73104a1b | 1788 | if (utf8_target) { |
73104a1b KW |
1789 | utf8_fold_flags = 0; |
1790 | goto do_exactf_utf8; | |
1791 | } | |
1792 | fold_array = PL_fold; | |
1793 | folder = foldEQ; | |
1794 | goto do_exactf_non_utf8; | |
1795 | ||
1796 | case EXACTFL: | |
31f05a37 | 1797 | if (is_utf8_pat || utf8_target || IN_UTF8_CTYPE_LOCALE) { |
cea315b6 | 1798 | utf8_fold_flags = FOLDEQ_LOCALE; |
73104a1b KW |
1799 | goto do_exactf_utf8; |
1800 | } | |
1801 | fold_array = PL_fold_locale; | |
1802 | folder = foldEQ_locale; | |
1803 | goto do_exactf_non_utf8; | |
3c760661 | 1804 | |
73104a1b | 1805 | case EXACTFU_SS: |
984e6dd1 | 1806 | if (is_utf8_pat) { |
73104a1b KW |
1807 | utf8_fold_flags = FOLDEQ_S2_ALREADY_FOLDED; |
1808 | } | |
1809 | goto do_exactf_utf8; | |
16d951b7 | 1810 | |
a4525e78 KW |
1811 | case EXACTFLU8: |
1812 | if (! utf8_target) { /* All code points in this node require | |
1813 | UTF-8 to express. */ | |
1814 | break; | |
1815 | } | |
1816 | utf8_fold_flags = FOLDEQ_S2_ALREADY_FOLDED; | |
1817 | goto do_exactf_utf8; | |
1818 | ||
73104a1b | 1819 | case EXACTFU: |
984e6dd1 DM |
1820 | if (is_utf8_pat || utf8_target) { |
1821 | utf8_fold_flags = is_utf8_pat ? FOLDEQ_S2_ALREADY_FOLDED : 0; | |
73104a1b KW |
1822 | goto do_exactf_utf8; |
1823 | } | |
fac1af77 | 1824 | |
73104a1b KW |
1825 | /* Any 'ss' in the pattern should have been replaced by regcomp, |
1826 | * so we don't have to worry here about this single special case | |
1827 | * in the Latin1 range */ | |
1828 | fold_array = PL_fold_latin1; | |
1829 | folder = foldEQ_latin1; | |
1830 | ||
924ba076 | 1831 | /* FALLTHROUGH */ |
73104a1b KW |
1832 | |
1833 | do_exactf_non_utf8: /* Neither pattern nor string are UTF8, and there | |
1834 | are no glitches with fold-length differences | |
1835 | between the target string and pattern */ | |
1836 | ||
1837 | /* The idea in the non-utf8 EXACTF* cases is to first find the | |
1838 | * first character of the EXACTF* node and then, if necessary, | |
1839 | * case-insensitively compare the full text of the node. c1 is the | |
1840 | * first character. c2 is its fold. This logic will not work for | |
1841 | * Unicode semantics and the german sharp ss, which hence should | |
1842 | * not be compiled into a node that gets here. */ | |
1843 | pat_string = STRING(c); | |
1844 | ln = STR_LEN(c); /* length to match in octets/bytes */ | |
1845 | ||
1846 | /* We know that we have to match at least 'ln' bytes (which is the | |
1847 | * same as characters, since not utf8). If we have to match 3 | |
1848 | * characters, and there are only 2 availabe, we know without | |
1849 | * trying that it will fail; so don't start a match past the | |
1850 | * required minimum number from the far end */ | |
ea3daa5d | 1851 | e = HOP3c(strend, -((SSize_t)ln), s); |
73104a1b | 1852 | |
02d5137b | 1853 | if (reginfo->intuit && e < s) { |
73104a1b KW |
1854 | e = s; /* Due to minlen logic of intuit() */ |
1855 | } | |
fac1af77 | 1856 | |
73104a1b KW |
1857 | c1 = *pat_string; |
1858 | c2 = fold_array[c1]; | |
1859 | if (c1 == c2) { /* If char and fold are the same */ | |
1860 | REXEC_FBC_EXACTISH_SCAN(*(U8*)s == c1); | |
1861 | } | |
1862 | else { | |
1863 | REXEC_FBC_EXACTISH_SCAN(*(U8*)s == c1 || *(U8*)s == c2); | |
1864 | } | |
1865 | break; | |
fac1af77 | 1866 | |
73104a1b KW |
1867 | do_exactf_utf8: |
1868 | { | |
1869 | unsigned expansion; | |
1870 | ||
1871 | /* If one of the operands is in utf8, we can't use the simpler folding | |
1872 | * above, due to the fact that many different characters can have the | |
1873 | * same fold, or portion of a fold, or different- length fold */ | |
1874 | pat_string = STRING(c); | |
1875 | ln = STR_LEN(c); /* length to match in octets/bytes */ | |
1876 | pat_end = pat_string + ln; | |
984e6dd1 | 1877 | lnc = is_utf8_pat /* length to match in characters */ |
73104a1b KW |
1878 | ? utf8_length((U8 *) pat_string, (U8 *) pat_end) |
1879 | : ln; | |
1880 | ||
1881 | /* We have 'lnc' characters to match in the pattern, but because of | |
1882 | * multi-character folding, each character in the target can match | |
1883 | * up to 3 characters (Unicode guarantees it will never exceed | |
1884 | * this) if it is utf8-encoded; and up to 2 if not (based on the | |
1885 | * fact that the Latin 1 folds are already determined, and the | |
1886 | * only multi-char fold in that range is the sharp-s folding to | |
1887 | * 'ss'. Thus, a pattern character can match as little as 1/3 of a | |
1888 | * string character. Adjust lnc accordingly, rounding up, so that | |
1889 | * if we need to match at least 4+1/3 chars, that really is 5. */ | |
1890 | expansion = (utf8_target) ? UTF8_MAX_FOLD_CHAR_EXPAND : 2; | |
1891 | lnc = (lnc + expansion - 1) / expansion; | |
1892 | ||
1893 | /* As in the non-UTF8 case, if we have to match 3 characters, and | |
1894 | * only 2 are left, it's guaranteed to fail, so don't start a | |
1895 | * match that would require us to go beyond the end of the string | |
1896 | */ | |
ea3daa5d | 1897 | e = HOP3c(strend, -((SSize_t)lnc), s); |
73104a1b | 1898 | |
02d5137b | 1899 | if (reginfo->intuit && e < s) { |
73104a1b KW |
1900 | e = s; /* Due to minlen logic of intuit() */ |
1901 | } | |
0658cdde | 1902 | |
73104a1b KW |
1903 | /* XXX Note that we could recalculate e to stop the loop earlier, |
1904 | * as the worst case expansion above will rarely be met, and as we | |
1905 | * go along we would usually find that e moves further to the left. | |
1906 | * This would happen only after we reached the point in the loop | |
1907 | * where if there were no expansion we should fail. Unclear if | |
1908 | * worth the expense */ | |
1909 | ||
1910 | while (s <= e) { | |
1911 | char *my_strend= (char *)strend; | |
1912 | if (foldEQ_utf8_flags(s, &my_strend, 0, utf8_target, | |
984e6dd1 | 1913 | pat_string, NULL, ln, is_utf8_pat, utf8_fold_flags) |
02d5137b | 1914 | && (reginfo->intuit || regtry(reginfo, &s)) ) |
73104a1b KW |
1915 | { |
1916 | goto got_it; | |
1917 | } | |
1918 | s += (utf8_target) ? UTF8SKIP(s) : 1; | |
1919 | } | |
1920 | break; | |
1921 | } | |
236d82fd | 1922 | |
73104a1b | 1923 | case BOUNDL: |
236d82fd | 1924 | FBC_BOUND(isWORDCHAR_LC, isWORDCHAR_LC_uvchr, isWORDCHAR_LC_utf8); |
73104a1b KW |
1925 | break; |
1926 | case NBOUNDL: | |
236d82fd | 1927 | FBC_NBOUND(isWORDCHAR_LC, isWORDCHAR_LC_uvchr, isWORDCHAR_LC_utf8); |
73104a1b KW |
1928 | break; |
1929 | case BOUND: | |
236d82fd | 1930 | FBC_BOUND(isWORDCHAR, isWORDCHAR_uni, isWORDCHAR_utf8); |
73104a1b KW |
1931 | break; |
1932 | case BOUNDA: | |
236d82fd | 1933 | FBC_BOUND_A(isWORDCHAR_A, isWORDCHAR_A, isWORDCHAR_A); |
73104a1b KW |
1934 | break; |
1935 | case NBOUND: | |
236d82fd | 1936 | FBC_NBOUND(isWORDCHAR, isWORDCHAR_uni, isWORDCHAR_utf8); |
73104a1b KW |
1937 | break; |
1938 | case NBOUNDA: | |
236d82fd | 1939 | FBC_NBOUND_A(isWORDCHAR_A, isWORDCHAR_A, isWORDCHAR_A); |
73104a1b KW |
1940 | break; |
1941 | case BOUNDU: | |
236d82fd | 1942 | FBC_BOUND(isWORDCHAR_L1, isWORDCHAR_uni, isWORDCHAR_utf8); |
73104a1b KW |
1943 | break; |
1944 | case NBOUNDU: | |
236d82fd | 1945 | FBC_NBOUND(isWORDCHAR_L1, isWORDCHAR_uni, isWORDCHAR_utf8); |
73104a1b | 1946 | break; |
73104a1b KW |
1947 | case LNBREAK: |
1948 | REXEC_FBC_CSCAN(is_LNBREAK_utf8_safe(s, strend), | |
1949 | is_LNBREAK_latin1_safe(s, strend) | |
1950 | ); | |
1951 | break; | |
3018b823 KW |
1952 | |
1953 | /* The argument to all the POSIX node types is the class number to pass to | |
1954 | * _generic_isCC() to build a mask for searching in PL_charclass[] */ | |
1955 | ||
1956 | case NPOSIXL: | |
1957 | to_complement = 1; | |
1958 | /* FALLTHROUGH */ | |
1959 | ||
1960 | case POSIXL: | |
3018b823 KW |
1961 | REXEC_FBC_CSCAN(to_complement ^ cBOOL(isFOO_utf8_lc(FLAGS(c), (U8 *) s)), |
1962 | to_complement ^ cBOOL(isFOO_lc(FLAGS(c), *s))); | |
73104a1b | 1963 | break; |
3018b823 KW |
1964 | |
1965 | case NPOSIXD: | |
1966 | to_complement = 1; | |
1967 | /* FALLTHROUGH */ | |
1968 | ||
1969 | case POSIXD: | |
1970 | if (utf8_target) { | |
1971 | goto posix_utf8; | |
1972 | } | |
1973 | goto posixa; | |
1974 | ||
1975 | case NPOSIXA: | |
1976 | if (utf8_target) { | |
1977 | /* The complement of something that matches only ASCII matches all | |
837226c8 KW |
1978 | * non-ASCII, plus everything in ASCII that isn't in the class. */ |
1979 | REXEC_FBC_UTF8_CLASS_SCAN(! isASCII_utf8(s) | |
3018b823 KW |
1980 | || ! _generic_isCC_A(*s, FLAGS(c))); |
1981 | break; | |
1982 | } | |
1983 | ||
1984 | to_complement = 1; | |
1985 | /* FALLTHROUGH */ | |
1986 | ||
73104a1b | 1987 | case POSIXA: |
3018b823 | 1988 | posixa: |
73104a1b | 1989 | /* Don't need to worry about utf8, as it can match only a single |
3018b823 KW |
1990 | * byte invariant character. */ |
1991 | REXEC_FBC_CLASS_SCAN( | |
1992 | to_complement ^ cBOOL(_generic_isCC_A(*s, FLAGS(c)))); | |
73104a1b | 1993 | break; |
3018b823 KW |
1994 | |
1995 | case NPOSIXU: | |
1996 | to_complement = 1; | |
1997 | /* FALLTHROUGH */ | |
1998 | ||
1999 | case POSIXU: | |
2000 | if (! utf8_target) { | |
2001 | REXEC_FBC_CLASS_SCAN(to_complement ^ cBOOL(_generic_isCC(*s, | |
2002 | FLAGS(c)))); | |
2003 | } | |
2004 | else { | |
2005 | ||
2006 | posix_utf8: | |
2007 | classnum = (_char_class_number) FLAGS(c); | |
2008 | if (classnum < _FIRST_NON_SWASH_CC) { | |
2009 | while (s < strend) { | |
2010 | ||
2011 | /* We avoid loading in the swash as long as possible, but | |
2012 | * should we have to, we jump to a separate loop. This | |
2013 | * extra 'if' statement is what keeps this code from being | |
2014 | * just a call to REXEC_FBC_UTF8_CLASS_SCAN() */ | |
2015 | if (UTF8_IS_ABOVE_LATIN1(*s)) { | |
2016 | goto found_above_latin1; | |
2017 | } | |
2018 | if ((UTF8_IS_INVARIANT(*s) | |
2019 | && to_complement ^ cBOOL(_generic_isCC((U8) *s, | |
2020 | classnum))) | |
2021 | || (UTF8_IS_DOWNGRADEABLE_START(*s) | |
2022 | && to_complement ^ cBOOL( | |
94bb8c36 KW |
2023 | _generic_isCC(TWO_BYTE_UTF8_TO_NATIVE(*s, |
2024 | *(s + 1)), | |
3018b823 KW |
2025 | classnum)))) |
2026 | { | |
02d5137b | 2027 | if (tmp && (reginfo->intuit || regtry(reginfo, &s))) |
3018b823 KW |
2028 | goto got_it; |
2029 | else { | |
2030 | tmp = doevery; | |
2031 | } | |
2032 | } | |
2033 | else { | |
2034 | tmp = 1; | |
2035 | } | |
2036 | s += UTF8SKIP(s); | |
2037 | } | |
2038 | } | |
2039 | else switch (classnum) { /* These classes are implemented as | |
2040 | macros */ | |
2041 | case _CC_ENUM_SPACE: /* XXX would require separate code if we | |
2042 | revert the change of \v matching this */ | |
924ba076 | 2043 | /* FALLTHROUGH */ |
3018b823 KW |
2044 | |
2045 | case _CC_ENUM_PSXSPC: | |
2046 | REXEC_FBC_UTF8_CLASS_SCAN( | |
2047 | to_complement ^ cBOOL(isSPACE_utf8(s))); | |
2048 | break; | |
2049 | ||
2050 | case _CC_ENUM_BLANK: | |
2051 | REXEC_FBC_UTF8_CLASS_SCAN( | |
2052 | to_complement ^ cBOOL(isBLANK_utf8(s))); | |
2053 | break; | |
2054 | ||
2055 | case _CC_ENUM_XDIGIT: | |
2056 | REXEC_FBC_UTF8_CLASS_SCAN( | |
2057 | to_complement ^ cBOOL(isXDIGIT_utf8(s))); | |
2058 | break; | |
2059 | ||
2060 | case _CC_ENUM_VERTSPACE: | |
2061 | REXEC_FBC_UTF8_CLASS_SCAN( | |
2062 | to_complement ^ cBOOL(isVERTWS_utf8(s))); | |
2063 | break; | |
2064 | ||
2065 | case _CC_ENUM_CNTRL: | |
2066 | REXEC_FBC_UTF8_CLASS_SCAN( | |
2067 | to_complement ^ cBOOL(isCNTRL_utf8(s))); | |
2068 | break; | |
2069 | ||
2070 | default: | |
2071 | Perl_croak(aTHX_ "panic: find_byclass() node %d='%s' has an unexpected character class '%d'", OP(c), PL_reg_name[OP(c)], classnum); | |
e5964223 | 2072 | NOT_REACHED; /* NOTREACHED */ |
3018b823 KW |
2073 | } |
2074 | } | |
2075 | break; | |
2076 | ||
2077 | found_above_latin1: /* Here we have to load a swash to get the result | |
2078 | for the current code point */ | |
2079 | if (! PL_utf8_swash_ptrs[classnum]) { | |
2080 | U8 flags = _CORE_SWASH_INIT_ACCEPT_INVLIST; | |
2081 | PL_utf8_swash_ptrs[classnum] = | |
2a16ac92 KW |
2082 | _core_swash_init("utf8", |
2083 | "", | |
2084 | &PL_sv_undef, 1, 0, | |
2085 | PL_XPosix_ptrs[classnum], &flags); | |
3018b823 KW |
2086 | } |
2087 | ||
2088 | /* This is a copy of the loop above for swash classes, though using the | |
2089 | * FBC macro instead of being expanded out. Since we've loaded the | |
2090 | * swash, we don't have to check for that each time through the loop */ | |
2091 | REXEC_FBC_UTF8_CLASS_SCAN( | |
2092 | to_complement ^ cBOOL(_generic_utf8( | |
2093 | classnum, | |
2094 | s, | |
2095 | swash_fetch(PL_utf8_swash_ptrs[classnum], | |
2096 | (U8 *) s, TRUE)))); | |
73104a1b KW |
2097 | break; |
2098 | ||
2099 | case AHOCORASICKC: | |
2100 | case AHOCORASICK: | |
2101 | { | |
2102 | DECL_TRIE_TYPE(c); | |
2103 | /* what trie are we using right now */ | |
2104 | reg_ac_data *aho = (reg_ac_data*)progi->data->data[ ARG( c ) ]; | |
2105 | reg_trie_data *trie = (reg_trie_data*)progi->data->data[ aho->trie ]; | |
2106 | HV *widecharmap = MUTABLE_HV(progi->data->data[ aho->trie + 1 ]); | |
2107 | ||
2108 | const char *last_start = strend - trie->minlen; | |
6148ee25 | 2109 | #ifdef DEBUGGING |
73104a1b | 2110 | const char *real_start = s; |
6148ee25 | 2111 | #endif |
73104a1b KW |
2112 | STRLEN maxlen = trie->maxlen; |
2113 | SV *sv_points; | |
2114 | U8 **points; /* map of where we were in the input string | |
2115 | when reading a given char. For ASCII this | |
2116 | is unnecessary overhead as the relationship | |
2117 | is always 1:1, but for Unicode, especially | |
2118 | case folded Unicode this is not true. */ | |
2119 | U8 foldbuf[ UTF8_MAXBYTES_CASE + 1 ]; | |
2120 | U8 *bitmap=NULL; | |
2121 | ||
2122 | ||
2123 | GET_RE_DEBUG_FLAGS_DECL; | |
2124 | ||
2125 | /* We can't just allocate points here. We need to wrap it in | |
2126 | * an SV so it gets freed properly if there is a croak while | |
2127 | * running the match */ | |
2128 | ENTER; | |
2129 | SAVETMPS; | |
2130 | sv_points=newSV(maxlen * sizeof(U8 *)); | |
2131 | SvCUR_set(sv_points, | |
2132 | maxlen * sizeof(U8 *)); | |
2133 | SvPOK_on(sv_points); | |
2134 | sv_2mortal(sv_points); | |
2135 | points=(U8**)SvPV_nolen(sv_points ); | |
2136 | if ( trie_type != trie_utf8_fold | |
2137 | && (trie->bitmap || OP(c)==AHOCORASICKC) ) | |
2138 | { | |
2139 | if (trie->bitmap) | |
2140 | bitmap=(U8*)trie->bitmap; | |
2141 | else | |
2142 | bitmap=(U8*)ANYOF_BITMAP(c); | |
2143 | } | |
2144 | /* this is the Aho-Corasick algorithm modified a touch | |
2145 | to include special handling for long "unknown char" sequences. | |
2146 | The basic idea being that we use AC as long as we are dealing | |
2147 | with a possible matching char, when we encounter an unknown char | |
2148 | (and we have not encountered an accepting state) we scan forward | |
2149 | until we find a legal starting char. | |
2150 | AC matching is basically that of trie matching, except that when | |
2151 | we encounter a failing transition, we fall back to the current | |
2152 | states "fail state", and try the current char again, a process | |
2153 | we repeat until we reach the root state, state 1, or a legal | |
2154 | transition. If we fail on the root state then we can either | |
2155 | terminate if we have reached an accepting state previously, or | |
2156 | restart the entire process from the beginning if we have not. | |
2157 | ||
2158 | */ | |
2159 | while (s <= last_start) { | |
2160 | const U32 uniflags = UTF8_ALLOW_DEFAULT; | |
2161 | U8 *uc = (U8*)s; | |
2162 | U16 charid = 0; | |
2163 | U32 base = 1; | |
2164 | U32 state = 1; | |
2165 | UV uvc = 0; | |
2166 | STRLEN len = 0; | |
2167 | STRLEN foldlen = 0; | |
2168 | U8 *uscan = (U8*)NULL; | |
2169 | U8 *leftmost = NULL; | |
2170 | #ifdef DEBUGGING | |
2171 | U32 accepted_word= 0; | |
786e8c11 | 2172 | #endif |
73104a1b KW |
2173 | U32 pointpos = 0; |
2174 | ||
2175 | while ( state && uc <= (U8*)strend ) { | |
2176 | int failed=0; | |
2177 | U32 word = aho->states[ state ].wordnum; | |
2178 | ||
2179 | if( state==1 ) { | |
2180 | if ( bitmap ) { | |
2181 | DEBUG_TRIE_EXECUTE_r( | |
2182 | if ( uc <= (U8*)last_start && !BITMAP_TEST(bitmap,*uc) ) { | |
2183 | dump_exec_pos( (char *)uc, c, strend, real_start, | |
2184 | (char *)uc, utf8_target ); | |
2185 | PerlIO_printf( Perl_debug_log, | |
2186 | " Scanning for legal start char...\n"); | |
2187 | } | |
2188 | ); | |
2189 | if (utf8_target) { | |
2190 | while ( uc <= (U8*)last_start && !BITMAP_TEST(bitmap,*uc) ) { | |
2191 | uc += UTF8SKIP(uc); | |
2192 | } | |
2193 | } else { | |
2194 | while ( uc <= (U8*)last_start && !BITMAP_TEST(bitmap,*uc) ) { | |
2195 | uc++; | |
2196 | } | |
786e8c11 | 2197 | } |
73104a1b | 2198 | s= (char *)uc; |
07be1b83 | 2199 | } |
73104a1b KW |
2200 | if (uc >(U8*)last_start) break; |
2201 | } | |
2202 | ||
2203 | if ( word ) { | |
2204 | U8 *lpos= points[ (pointpos - trie->wordinfo[word].len) % maxlen ]; | |
2205 | if (!leftmost || lpos < leftmost) { | |
2206 | DEBUG_r(accepted_word=word); | |
2207 | leftmost= lpos; | |
7016d6eb | 2208 | } |
73104a1b | 2209 | if (base==0) break; |
7016d6eb | 2210 | |
73104a1b KW |
2211 | } |
2212 | points[pointpos++ % maxlen]= uc; | |
2213 | if (foldlen || uc < (U8*)strend) { | |
2214 | REXEC_TRIE_READ_CHAR(trie_type, trie, | |
2215 | widecharmap, uc, | |
2216 | uscan, len, uvc, charid, foldlen, | |
2217 | foldbuf, uniflags); | |
2218 | DEBUG_TRIE_EXECUTE_r({ | |
2219 | dump_exec_pos( (char *)uc, c, strend, | |
2220 | real_start, s, utf8_target); | |
2221 | PerlIO_printf(Perl_debug_log, | |
2222 | " Charid:%3u CP:%4"UVxf" ", | |
2223 | charid, uvc); | |
2224 | }); | |
2225 | } | |
2226 | else { | |
2227 | len = 0; | |
2228 | charid = 0; | |
2229 | } | |
07be1b83 | 2230 | |
73104a1b KW |
2231 | |
2232 | do { | |
6148ee25 | 2233 | #ifdef DEBUGGING |
73104a1b | 2234 | word = aho->states[ state ].wordnum; |
6148ee25 | 2235 | #endif |
73104a1b KW |
2236 | base = aho->states[ state ].trans.base; |
2237 | ||
2238 | DEBUG_TRIE_EXECUTE_r({ | |
2239 | if (failed) | |
2240 | dump_exec_pos( (char *)uc, c, strend, real_start, | |
2241 | s, utf8_target ); | |
2242 | PerlIO_printf( Perl_debug_log, | |
2243 | "%sState: %4"UVxf", word=%"UVxf, | |
2244 | failed ? " Fail transition to " : "", | |
2245 | (UV)state, (UV)word); | |
2246 | }); | |
2247 | if ( base ) { | |
2248 | U32 tmp; | |
2249 | I32 offset; | |
2250 | if (charid && | |
2251 | ( ((offset = base + charid | |
2252 | - 1 - trie->uniquecharcount)) >= 0) | |
2253 | && ((U32)offset < trie->lasttrans) | |
2254 | && trie->trans[offset].check == state | |
2255 | && (tmp=trie->trans[offset].next)) | |
2256 | { | |
2257 | DEBUG_TRIE_EXECUTE_r( | |
2258 | PerlIO_printf( Perl_debug_log," - legal\n")); | |
2259 | state = tmp; | |
2260 | break; | |
07be1b83 YO |
2261 | } |
2262 | else { | |
786e8c11 | 2263 | DEBUG_TRIE_EXECUTE_r( |
73104a1b | 2264 | PerlIO_printf( Perl_debug_log," - fail\n")); |
786e8c11 | 2265 | failed = 1; |
73104a1b | 2266 | state = aho->fail[state]; |
07be1b83 | 2267 | } |
07be1b83 | 2268 | } |
73104a1b KW |
2269 | else { |
2270 | /* we must be accepting here */ | |
2271 | DEBUG_TRIE_EXECUTE_r( | |
2272 | PerlIO_printf( Perl_debug_log," - accepting\n")); | |
2273 | failed = 1; | |
2274 | break; | |
786e8c11 | 2275 | } |
73104a1b KW |
2276 | } while(state); |
2277 | uc += len; | |
2278 | if (failed) { | |
2279 | if (leftmost) | |
2280 | break; | |
2281 | if (!state) state = 1; | |
07be1b83 | 2282 | } |
73104a1b KW |
2283 | } |
2284 | if ( aho->states[ state ].wordnum ) { | |
2285 | U8 *lpos = points[ (pointpos - trie->wordinfo[aho->states[ state ].wordnum].len) % maxlen ]; | |
2286 | if (!leftmost || lpos < leftmost) { | |
2287 | DEBUG_r(accepted_word=aho->states[ state ].wordnum); | |
2288 | leftmost = lpos; | |
07be1b83 YO |
2289 | } |
2290 | } | |
73104a1b KW |
2291 | if (leftmost) { |
2292 | s = (char*)leftmost; | |
2293 | DEBUG_TRIE_EXECUTE_r({ | |
2294 | PerlIO_printf( | |
2295 | Perl_debug_log,"Matches word #%"UVxf" at position %"IVdf". Trying full pattern...\n", | |
2296 | (UV)accepted_word, (IV)(s - real_start) | |
2297 | ); | |
2298 | }); | |
02d5137b | 2299 | if (reginfo->intuit || regtry(reginfo, &s)) { |
73104a1b KW |
2300 | FREETMPS; |
2301 | LEAVE; | |
2302 | goto got_it; | |
2303 | } | |
2304 | s = HOPc(s,1); | |
2305 | DEBUG_TRIE_EXECUTE_r({ | |
2306 | PerlIO_printf( Perl_debug_log,"Pattern failed. Looking for new start point...\n"); | |
2307 | }); | |
2308 | } else { | |
2309 | DEBUG_TRIE_EXECUTE_r( | |
2310 | PerlIO_printf( Perl_debug_log,"No match.\n")); | |
2311 | break; | |
2312 | } | |
2313 | } | |
2314 | FREETMPS; | |
2315 | LEAVE; | |
2316 | } | |
2317 | break; | |
2318 | default: | |
2319 | Perl_croak(aTHX_ "panic: unknown regstclass %d", (int)OP(c)); | |
73104a1b KW |
2320 | } |
2321 | return 0; | |
2322 | got_it: | |
2323 | return s; | |
6eb5f6b9 JH |
2324 | } |
2325 | ||
60165aa4 DM |
2326 | /* set RX_SAVED_COPY, RX_SUBBEG etc. |
2327 | * flags have same meanings as with regexec_flags() */ | |
2328 | ||
749f4950 DM |
2329 | static void |
2330 | S_reg_set_capture_string(pTHX_ REGEXP * const rx, | |
60165aa4 DM |
2331 | char *strbeg, |
2332 | char *strend, | |
2333 | SV *sv, | |
2334 | U32 flags, | |
2335 | bool utf8_target) | |
2336 | { | |
2337 | struct regexp *const prog = ReANY(rx); | |
2338 | ||
60165aa4 DM |
2339 | if (flags & REXEC_COPY_STR) { |
2340 | #ifdef PERL_ANY_COW | |
2341 | if (SvCANCOW(sv)) { | |
2342 | if (DEBUG_C_TEST) { | |
2343 | PerlIO_printf(Perl_debug_log, | |
2344 | "Copy on write: regexp capture, type %d\n", | |
2345 | (int) SvTYPE(sv)); | |
2346 | } | |
5411a0e5 DM |
2347 | /* Create a new COW SV to share the match string and store |
2348 | * in saved_copy, unless the current COW SV in saved_copy | |
2349 | * is valid and suitable for our purpose */ | |
2350 | if (( prog->saved_copy | |
2351 | && SvIsCOW(prog->saved_copy) | |
2352 | && SvPOKp(prog->saved_copy) | |
2353 | && SvIsCOW(sv) | |
2354 | && SvPOKp(sv) | |
2355 | && SvPVX(sv) == SvPVX(prog->saved_copy))) | |
a76b0e90 | 2356 | { |
5411a0e5 DM |
2357 | /* just reuse saved_copy SV */ |
2358 | if (RXp_MATCH_COPIED(prog)) { | |
2359 | Safefree(prog->subbeg); | |
2360 | RXp_MATCH_COPIED_off(prog); | |
2361 | } | |
2362 | } | |
2363 | else { | |
2364 | /* create new COW SV to share string */ | |
a76b0e90 DM |
2365 | RX_MATCH_COPY_FREE(rx); |
2366 | prog->saved_copy = sv_setsv_cow(prog->saved_copy, sv); | |
a76b0e90 | 2367 | } |
5411a0e5 DM |
2368 | prog->subbeg = (char *)SvPVX_const(prog->saved_copy); |
2369 | assert (SvPOKp(prog->saved_copy)); | |
60165aa4 DM |
2370 | prog->sublen = strend - strbeg; |
2371 | prog->suboffset = 0; | |
2372 | prog->subcoffset = 0; | |
2373 | } else | |
2374 | #endif | |
2375 | { | |
99a90e59 FC |
2376 | SSize_t min = 0; |
2377 | SSize_t max = strend - strbeg; | |
ea3daa5d | 2378 | SSize_t sublen; |
60165aa4 DM |
2379 | |
2380 | if ( (flags & REXEC_COPY_SKIP_POST) | |
e322109a | 2381 | && !(prog->extflags & RXf_PMf_KEEPCOPY) /* //p */ |
60165aa4 DM |
2382 | && !(PL_sawampersand & SAWAMPERSAND_RIGHT) |
2383 | ) { /* don't copy $' part of string */ | |
2384 | U32 n = 0; | |
2385 | max = -1; | |
2386 | /* calculate the right-most part of the string covered | |
2387 | * by a capture. Due to look-ahead, this may be to | |
2388 | * the right of $&, so we have to scan all captures */ | |
2389 | while (n <= prog->lastparen) { | |
2390 | if (prog->offs[n].end > max) | |
2391 | max = prog->offs[n].end; | |
2392 | n++; | |
2393 | } | |
2394 | if (max == -1) | |
2395 | max = (PL_sawampersand & SAWAMPERSAND_LEFT) | |
2396 | ? prog->offs[0].start | |
2397 | : 0; | |
2398 | assert(max >= 0 && max <= strend - strbeg); | |
2399 | } | |
2400 | ||
2401 | if ( (flags & REXEC_COPY_SKIP_PRE) | |
e322109a | 2402 | && !(prog->extflags & RXf_PMf_KEEPCOPY) /* //p */ |
60165aa4 DM |
2403 | && !(PL_sawampersand & SAWAMPERSAND_LEFT) |
2404 | ) { /* don't copy $` part of string */ | |
2405 | U32 n = 0; | |
2406 | min = max; | |
2407 | /* calculate the left-most part of the string covered | |
2408 | * by a capture. Due to look-behind, this may be to | |
2409 | * the left of $&, so we have to scan all captures */ | |
2410 | while (min && n <= prog->lastparen) { | |
2411 | if ( prog->offs[n].start != -1 | |
2412 | && prog->offs[n].start < min) | |
2413 | { | |
2414 | min = prog->offs[n].start; | |
2415 | } | |
2416 | n++; | |
2417 | } | |
2418 | if ((PL_sawampersand & SAWAMPERSAND_RIGHT) | |
2419 | && min > prog->offs[0].end | |
2420 | ) | |
2421 | min = prog->offs[0].end; | |
2422 | ||
2423 | } | |
2424 | ||
2425 | assert(min >= 0 && min <= max && min <= strend - strbeg); | |
2426 | sublen = max - min; | |
2427 | ||
2428 | if (RX_MATCH_COPIED(rx)) { | |
2429 | if (sublen > prog->sublen) | |
2430 | prog->subbeg = | |
2431 | (char*)saferealloc(prog->subbeg, sublen+1); | |
2432 | } | |
2433 | else | |
2434 | prog->subbeg = (char*)safemalloc(sublen+1); | |
2435 | Copy(strbeg + min, prog->subbeg, sublen, char); | |
2436 | prog->subbeg[sublen] = '\0'; | |
2437 | prog->suboffset = min; | |
2438 | prog->sublen = sublen; | |
2439 | RX_MATCH_COPIED_on(rx); | |
2440 | } | |
2441 | prog->subcoffset = prog->suboffset; | |
2442 | if (prog->suboffset && utf8_target) { | |
2443 | /* Convert byte offset to chars. | |
2444 | * XXX ideally should only compute this if @-/@+ | |
2445 | * has been seen, a la PL_sawampersand ??? */ | |
2446 | ||
2447 | /* If there's a direct correspondence between the | |
2448 | * string which we're matching and the original SV, | |
2449 | * then we can use the utf8 len cache associated with | |
2450 | * the SV. In particular, it means that under //g, | |
2451 | * sv_pos_b2u() will use the previously cached | |
2452 | * position to speed up working out the new length of | |
2453 | * subcoffset, rather than counting from the start of | |
2454 | * the string each time. This stops | |
2455 | * $x = "\x{100}" x 1E6; 1 while $x =~ /(.)/g; | |
2456 | * from going quadratic */ | |
2457 | if (SvPOKp(sv) && SvPVX(sv) == strbeg) | |
ea3daa5d FC |
2458 | prog->subcoffset = sv_pos_b2u_flags(sv, prog->subcoffset, |
2459 | SV_GMAGIC|SV_CONST_RETURN); | |
60165aa4 DM |
2460 | else |
2461 | prog->subcoffset = utf8_length((U8*)strbeg, | |
2462 | (U8*)(strbeg+prog->suboffset)); | |
2463 | } | |
2464 | } | |
2465 | else { | |
2466 | RX_MATCH_COPY_FREE(rx); | |
2467 | prog->subbeg = strbeg; | |
2468 | prog->suboffset = 0; | |
2469 | prog->subcoffset = 0; | |
2470 | prog->sublen = strend - strbeg; | |
2471 | } | |
2472 | } | |
2473 | ||
2474 | ||
2475 | ||
fae667d5 | 2476 | |
6eb5f6b9 JH |
2477 | /* |
2478 | - regexec_flags - match a regexp against a string | |
2479 | */ | |
2480 | I32 | |
5aaab254 | 2481 | Perl_regexec_flags(pTHX_ REGEXP * const rx, char *stringarg, char *strend, |
ea3daa5d | 2482 | char *strbeg, SSize_t minend, SV *sv, void *data, U32 flags) |
8fd1a950 DM |
2483 | /* stringarg: the point in the string at which to begin matching */ |
2484 | /* strend: pointer to null at end of string */ | |
2485 | /* strbeg: real beginning of string */ | |
2486 | /* minend: end of match must be >= minend bytes after stringarg. */ | |
2487 | /* sv: SV being matched: only used for utf8 flag, pos() etc; string | |
2488 | * itself is accessed via the pointers above */ | |
2489 | /* data: May be used for some additional optimizations. | |
d058ec57 | 2490 | Currently unused. */ |
a340edde | 2491 | /* flags: For optimizations. See REXEC_* in regexp.h */ |
8fd1a950 | 2492 | |
6eb5f6b9 | 2493 | { |
8d919b0a | 2494 | struct regexp *const prog = ReANY(rx); |
5aaab254 | 2495 | char *s; |
eb578fdb | 2496 | regnode *c; |
03c83e26 | 2497 | char *startpos; |
ea3daa5d FC |
2498 | SSize_t minlen; /* must match at least this many chars */ |
2499 | SSize_t dontbother = 0; /* how many characters not to try at end */ | |
f2ed9b32 | 2500 | const bool utf8_target = cBOOL(DO_UTF8(sv)); |
2757e526 | 2501 | I32 multiline; |
f8fc2ecf | 2502 | RXi_GET_DECL(prog,progi); |
02d5137b DM |
2503 | regmatch_info reginfo_buf; /* create some info to pass to regtry etc */ |
2504 | regmatch_info *const reginfo = ®info_buf; | |
e9105d30 | 2505 | regexp_paren_pair *swap = NULL; |
006f26b2 | 2506 | I32 oldsave; |
a3621e74 YO |
2507 | GET_RE_DEBUG_FLAGS_DECL; |
2508 | ||
7918f24d | 2509 | PERL_ARGS_ASSERT_REGEXEC_FLAGS; |
9d4ba2ae | 2510 | PERL_UNUSED_ARG(data); |
6eb5f6b9 JH |
2511 | |
2512 | /* Be paranoid... */ | |
03c83e26 | 2513 | if (prog == NULL || stringarg == NULL) { |
6eb5f6b9 | 2514 | Perl_croak(aTHX_ "NULL regexp parameter"); |
6eb5f6b9 JH |
2515 | } |
2516 | ||
6c3fea77 | 2517 | DEBUG_EXECUTE_r( |
03c83e26 | 2518 | debug_start_match(rx, utf8_target, stringarg, strend, |
6c3fea77 DM |
2519 | "Matching"); |
2520 | ); | |
8adc0f72 | 2521 | |
b342a604 DM |
2522 | startpos = stringarg; |
2523 | ||
58430ea8 | 2524 | if (prog->intflags & PREGf_GPOS_SEEN) { |
d307c076 DM |
2525 | MAGIC *mg; |
2526 | ||
fef7148b DM |
2527 | /* set reginfo->ganch, the position where \G can match */ |
2528 | ||
2529 | reginfo->ganch = | |
2530 | (flags & REXEC_IGNOREPOS) | |
2531 | ? stringarg /* use start pos rather than pos() */ | |
2532 | : (sv && (mg = mg_find_mglob(sv)) && mg->mg_len >= 0) | |
25fdce4a FC |
2533 | /* Defined pos(): */ |
2534 | ? strbeg + MgBYTEPOS(mg, sv, strbeg, strend-strbeg) | |
fef7148b DM |
2535 | : strbeg; /* pos() not defined; use start of string */ |
2536 | ||
2537 | DEBUG_GPOS_r(PerlIO_printf(Perl_debug_log, | |
7b0eb0b8 | 2538 | "GPOS ganch set to strbeg[%"IVdf"]\n", (IV)(reginfo->ganch - strbeg))); |
fef7148b | 2539 | |
03c83e26 DM |
2540 | /* in the presence of \G, we may need to start looking earlier in |
2541 | * the string than the suggested start point of stringarg: | |
0b2c2a84 | 2542 | * if prog->gofs is set, then that's a known, fixed minimum |
03c83e26 DM |
2543 | * offset, such as |
2544 | * /..\G/: gofs = 2 | |
2545 | * /ab|c\G/: gofs = 1 | |
2546 | * or if the minimum offset isn't known, then we have to go back | |
2547 | * to the start of the string, e.g. /w+\G/ | |
2548 | */ | |
2bfbe302 | 2549 | |
8e1490ee | 2550 | if (prog->intflags & PREGf_ANCH_GPOS) { |
2bfbe302 DM |
2551 | startpos = reginfo->ganch - prog->gofs; |
2552 | if (startpos < | |
2553 | ((flags & REXEC_FAIL_ON_UNDERFLOW) ? stringarg : strbeg)) | |
2554 | { | |
2555 | DEBUG_r(PerlIO_printf(Perl_debug_log, | |
2556 | "fail: ganch-gofs before earliest possible start\n")); | |
2557 | return 0; | |
2558 | } | |
2559 | } | |
2560 | else if (prog->gofs) { | |
b342a604 DM |
2561 | if (startpos - prog->gofs < strbeg) |
2562 | startpos = strbeg; | |
2563 | else | |
2564 | startpos -= prog->gofs; | |
03c83e26 | 2565 | } |
58430ea8 | 2566 | else if (prog->intflags & PREGf_GPOS_FLOAT) |
b342a604 | 2567 | startpos = strbeg; |
03c83e26 DM |
2568 | } |
2569 | ||
2570 | minlen = prog->minlen; | |
b342a604 | 2571 | if ((startpos + minlen) > strend || startpos < strbeg) { |
03c83e26 DM |
2572 | DEBUG_r(PerlIO_printf(Perl_debug_log, |
2573 | "Regex match can't succeed, so not even tried\n")); | |
2574 | return 0; | |
2575 | } | |
2576 | ||
63a3746a DM |
2577 | /* at the end of this function, we'll do a LEAVE_SCOPE(oldsave), |
2578 | * which will call destuctors to reset PL_regmatch_state, free higher | |
2579 | * PL_regmatch_slabs, and clean up regmatch_info_aux and | |
2580 | * regmatch_info_aux_eval */ | |
2581 | ||
2582 | oldsave = PL_savestack_ix; | |
2583 | ||
dfa77d06 DM |
2584 | s = startpos; |
2585 | ||
e322109a | 2586 | if ((prog->extflags & RXf_USE_INTUIT) |
7fadf4a7 DM |
2587 | && !(flags & REXEC_CHECKED)) |
2588 | { | |
dfa77d06 | 2589 | s = re_intuit_start(rx, sv, strbeg, startpos, strend, |
7fadf4a7 | 2590 | flags, NULL); |
dfa77d06 | 2591 | if (!s) |
7fadf4a7 DM |
2592 | return 0; |
2593 | ||
e322109a | 2594 | if (prog->extflags & RXf_CHECK_ALL) { |
7fadf4a7 DM |
2595 | /* we can match based purely on the result of INTUIT. |
2596 | * Set up captures etc just for $& and $-[0] | |
2597 | * (an intuit-only match wont have $1,$2,..) */ | |
2598 | assert(!prog->nparens); | |
d5e7783a DM |
2599 | |
2600 | /* s/// doesn't like it if $& is earlier than where we asked it to | |
2601 | * start searching (which can happen on something like /.\G/) */ | |
2602 | if ( (flags & REXEC_FAIL_ON_UNDERFLOW) | |
2603 | && (s < stringarg)) | |
2604 | { | |
2605 | /* this should only be possible under \G */ | |
58430ea8 | 2606 | assert(prog->intflags & PREGf_GPOS_SEEN); |
d5e7783a DM |
2607 | DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, |
2608 | "matched, but failing for REXEC_FAIL_ON_UNDERFLOW\n")); | |
2609 | goto phooey; | |
2610 | } | |
2611 | ||
7fadf4a7 DM |
2612 | /* match via INTUIT shouldn't have any captures. |
2613 | * Let @-, @+, $^N know */ | |
2614 | prog->lastparen = prog->lastcloseparen = 0; | |
2615 | RX_MATCH_UTF8_set(rx, utf8_target); | |
3ff69bd6 DM |
2616 | prog->offs[0].start = s - strbeg; |
2617 | prog->offs[0].end = utf8_target | |
2618 | ? (char*)utf8_hop((U8*)s, prog->minlenret) - strbeg | |
2619 | : s - strbeg + prog->minlenret; | |
7fadf4a7 | 2620 | if ( !(flags & REXEC_NOT_FIRST) ) |
749f4950 | 2621 | S_reg_set_capture_string(aTHX_ rx, |
7fadf4a7 DM |
2622 | strbeg, strend, |
2623 | sv, flags, utf8_target); | |
2624 | ||
7fadf4a7 DM |
2625 | return 1; |
2626 | } | |
2627 | } | |
2628 | ||
6c3fea77 | 2629 | multiline = prog->extflags & RXf_PMf_MULTILINE; |
1de06328 | 2630 | |
dfa77d06 | 2631 | if (strend - s < (minlen+(prog->check_offset_min<0?prog->check_offset_min:0))) { |
a3621e74 | 2632 | DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, |
a72c7584 JH |
2633 | "String too short [regexec_flags]...\n")); |
2634 | goto phooey; | |
1aa99e6b | 2635 | } |
1de06328 | 2636 | |
6eb5f6b9 | 2637 | /* Check validity of program. */ |
f8fc2ecf | 2638 | if (UCHARAT(progi->program) != REG_MAGIC) { |
6eb5f6b9 JH |
2639 | Perl_croak(aTHX_ "corrupted regexp program"); |
2640 | } | |
2641 | ||
1738e041 | 2642 | RX_MATCH_TAINTED_off(rx); |
ab4e48c1 | 2643 | RX_MATCH_UTF8_set(rx, utf8_target); |
1738e041 | 2644 | |
6c3fea77 DM |
2645 | reginfo->prog = rx; /* Yes, sorry that this is confusing. */ |
2646 | reginfo->intuit = 0; | |
2647 | reginfo->is_utf8_target = cBOOL(utf8_target); | |
02d5137b DM |
2648 | reginfo->is_utf8_pat = cBOOL(RX_UTF8(rx)); |
2649 | reginfo->warned = FALSE; | |
9d9163fb | 2650 | reginfo->strbeg = strbeg; |
02d5137b | 2651 | reginfo->sv = sv; |
1cb48e53 | 2652 | reginfo->poscache_maxiter = 0; /* not yet started a countdown */ |
220db18a | 2653 | reginfo->strend = strend; |
6eb5f6b9 | 2654 | /* see how far we have to get to not match where we matched before */ |
fe3974be | 2655 | reginfo->till = stringarg + minend; |
6eb5f6b9 | 2656 | |
60779a30 | 2657 | if (prog->extflags & RXf_EVAL_SEEN && SvPADTMP(sv)) { |
82c23608 FC |
2658 | /* SAVEFREESV, not sv_mortalcopy, as this SV must last until after |
2659 | S_cleanup_regmatch_info_aux has executed (registered by | |
2660 | SAVEDESTRUCTOR_X below). S_cleanup_regmatch_info_aux modifies | |
2661 | magic belonging to this SV. | |
2662 | Not newSVsv, either, as it does not COW. | |
2663 | */ | |
2664 | reginfo->sv = newSV(0); | |
4cba5ac0 | 2665 | SvSetSV_nosteal(reginfo->sv, sv); |
82c23608 FC |
2666 | SAVEFREESV(reginfo->sv); |
2667 | } | |
2668 | ||
331b2dcc DM |
2669 | /* reserve next 2 or 3 slots in PL_regmatch_state: |
2670 | * slot N+0: may currently be in use: skip it | |
2671 | * slot N+1: use for regmatch_info_aux struct | |
2672 | * slot N+2: use for regmatch_info_aux_eval struct if we have (?{})'s | |
2673 | * slot N+3: ready for use by regmatch() | |
2674 | */ | |
bf2039a9 | 2675 | |
331b2dcc DM |
2676 | { |
2677 | regmatch_state *old_regmatch_state; | |
2678 | regmatch_slab *old_regmatch_slab; | |
2679 | int i, max = (prog->extflags & RXf_EVAL_SEEN) ? 2 : 1; | |
2680 | ||
2681 | /* on first ever match, allocate first slab */ | |
2682 | if (!PL_regmatch_slab) { | |
2683 | Newx(PL_regmatch_slab, 1, regmatch_slab); | |
2684 | PL_regmatch_slab->prev = NULL; | |
2685 | PL_regmatch_slab->next = NULL; | |
2686 | PL_regmatch_state = SLAB_FIRST(PL_regmatch_slab); | |
2687 | } | |
bf2039a9 | 2688 | |
331b2dcc DM |
2689 | old_regmatch_state = PL_regmatch_state; |
2690 | old_regmatch_slab = PL_regmatch_slab; | |
bf2039a9 | 2691 | |
331b2dcc DM |
2692 | for (i=0; i <= max; i++) { |
2693 | if (i == 1) | |
2694 | reginfo->info_aux = &(PL_regmatch_state->u.info_aux); | |
2695 | else if (i ==2) | |
2696 | reginfo->info_aux_eval = | |
2697 | reginfo->info_aux->info_aux_eval = | |
2698 | &(PL_regmatch_state->u.info_aux_eval); | |
bf2039a9 | 2699 | |
331b2dcc DM |
2700 | if (++PL_regmatch_state > SLAB_LAST(PL_regmatch_slab)) |
2701 | PL_regmatch_state = S_push_slab(aTHX); | |
2702 | } | |
bf2039a9 | 2703 | |
331b2dcc DM |
2704 | /* note initial PL_regmatch_state position; at end of match we'll |
2705 | * pop back to there and free any higher slabs */ | |
bf2039a9 | 2706 | |
331b2dcc DM |
2707 | reginfo->info_aux->old_regmatch_state = old_regmatch_state; |
2708 | reginfo->info_aux->old_regmatch_slab = old_regmatch_slab; | |
2ac8ff4b | 2709 | reginfo->info_aux->poscache = NULL; |
bf2039a9 | 2710 | |
331b2dcc | 2711 | SAVEDESTRUCTOR_X(S_cleanup_regmatch_info_aux, reginfo->info_aux); |
bf2039a9 | 2712 | |
331b2dcc DM |
2713 | if ((prog->extflags & RXf_EVAL_SEEN)) |
2714 | S_setup_eval_state(aTHX_ reginfo); | |
2715 | else | |
2716 | reginfo->info_aux_eval = reginfo->info_aux->info_aux_eval = NULL; | |
bf2039a9 | 2717 | } |
d3aa529c | 2718 | |
6eb5f6b9 | 2719 | /* If there is a "must appear" string, look for it. */ |
6eb5f6b9 | 2720 | |
288b8c02 | 2721 | if (PL_curpm && (PM_GETRE(PL_curpm) == rx)) { |
e9105d30 GG |
2722 | /* We have to be careful. If the previous successful match |
2723 | was from this regex we don't want a subsequent partially | |
2724 | successful match to clobber the old results. | |
2725 | So when we detect this possibility we add a swap buffer | |
d8da0584 KW |
2726 | to the re, and switch the buffer each match. If we fail, |
2727 | we switch it back; otherwise we leave it swapped. | |
e9105d30 GG |
2728 | */ |
2729 | swap = prog->offs; | |
2730 | /* do we need a save destructor here for eval dies? */ | |
2731 | Newxz(prog->offs, (prog->nparens + 1), regexp_paren_pair); | |
495f47a5 DM |
2732 | DEBUG_BUFFERS_r(PerlIO_printf(Perl_debug_log, |
2733 | "rex=0x%"UVxf" saving offs: orig=0x%"UVxf" new=0x%"UVxf"\n", | |
2734 | PTR2UV(prog), | |
2735 | PTR2UV(swap), | |
2736 | PTR2UV(prog->offs) | |
2737 | )); | |
c74340f9 | 2738 | } |
6eb5f6b9 JH |
2739 | |
2740 | /* Simplest case: anchored match need be tried only once. */ | |
d3d47aac | 2741 | /* [unless only anchor is MBOL - implying multiline is set] */ |
8e1490ee | 2742 | if (prog->intflags & (PREGf_ANCH & ~PREGf_ANCH_GPOS)) { |
3542935d | 2743 | if (s == startpos && regtry(reginfo, &s)) |
6eb5f6b9 | 2744 | goto got_it; |
8e1490ee | 2745 | else if (multiline || (prog->intflags & (PREGf_IMPLICIT | PREGf_ANCH_MBOL))) /* XXXX SBOL? */ |
6eb5f6b9 JH |
2746 | { |
2747 | char *end; | |
2748 | ||
2749 | if (minlen) | |
2750 | dontbother = minlen - 1; | |
1aa99e6b | 2751 | end = HOP3c(strend, -dontbother, strbeg) - 1; |
6eb5f6b9 | 2752 | /* for multiline we only have to try after newlines */ |
33b8afdf | 2753 | if (prog->check_substr || prog->check_utf8) { |
92f3d482 YO |
2754 | /* because of the goto we can not easily reuse the macros for bifurcating the |
2755 | unicode/non-unicode match modes here like we do elsewhere - demerphq */ | |
2756 | if (utf8_target) { | |
2757 | if (s == startpos) | |
2758 | goto after_try_utf8; | |
2759 | while (1) { | |
02d5137b | 2760 | if (regtry(reginfo, &s)) { |
92f3d482 YO |
2761 | goto got_it; |
2762 | } | |
2763 | after_try_utf8: | |
2764 | if (s > end) { | |
2765 | goto phooey; | |
2766 | } | |
2767 | if (prog->extflags & RXf_USE_INTUIT) { | |
52a21eb3 DM |
2768 | s = re_intuit_start(rx, sv, strbeg, |
2769 | s + UTF8SKIP(s), strend, flags, NULL); | |
92f3d482 YO |
2770 | if (!s) { |
2771 | goto phooey; | |
2772 | } | |
2773 | } | |
2774 | else { | |
2775 | s += UTF8SKIP(s); | |
2776 | } | |
2777 | } | |
2778 | } /* end search for check string in unicode */ | |
2779 | else { | |
2780 | if (s == startpos) { | |
2781 | goto after_try_latin; | |
2782 | } | |
2783 | while (1) { | |
02d5137b | 2784 | if (regtry(reginfo, &s)) { |
92f3d482 YO |
2785 | goto got_it; |
2786 | } | |
2787 | after_try_latin: | |
2788 | if (s > end) { | |
2789 | goto phooey; | |
2790 | } | |
2791 | if (prog->extflags & RXf_USE_INTUIT) { | |
52a21eb3 DM |
2792 | s = re_intuit_start(rx, sv, strbeg, |
2793 | s + 1, strend, flags, NULL); | |
92f3d482 YO |
2794 | if (!s) { |
2795 | goto phooey; | |
2796 | } | |
2797 | } | |
2798 | else { | |
2799 | s++; | |
2800 | } | |
2801 | } | |
2802 | } /* end search for check string in latin*/ | |
2803 | } /* end search for check string */ | |
2804 | else { /* search for newline */ | |
2805 | if (s > startpos) { | |
2806 | /*XXX: The s-- is almost definitely wrong here under unicode - demeprhq*/ | |
6eb5f6b9 | 2807 | s--; |
92f3d482 | 2808 | } |
21eede78 YO |
2809 | /* We can use a more efficient search as newlines are the same in unicode as they are in latin */ |
2810 | while (s <= end) { /* note it could be possible to match at the end of the string */ | |
6eb5f6b9 | 2811 | if (*s++ == '\n') { /* don't need PL_utf8skip here */ |
02d5137b | 2812 | if (regtry(reginfo, &s)) |
6eb5f6b9 JH |
2813 | goto got_it; |
2814 | } | |
92f3d482 YO |
2815 | } |
2816 | } /* end search for newline */ | |
2817 | } /* end anchored/multiline check string search */ | |
6eb5f6b9 | 2818 | goto phooey; |
a8430a8b | 2819 | } else if (prog->intflags & PREGf_ANCH_GPOS) |
f9f4320a | 2820 | { |
a8430a8b YO |
2821 | /* PREGf_ANCH_GPOS should never be true if PREGf_GPOS_SEEN is not true */ |
2822 | assert(prog->intflags & PREGf_GPOS_SEEN); | |
2bfbe302 DM |
2823 | /* For anchored \G, the only position it can match from is |
2824 | * (ganch-gofs); we already set startpos to this above; if intuit | |
2825 | * moved us on from there, we can't possibly succeed */ | |
2826 | assert(startpos == reginfo->ganch - prog->gofs); | |
2827 | if (s == startpos && regtry(reginfo, &s)) | |
6eb5f6b9 JH |
2828 | goto got_it; |
2829 | goto phooey; | |
2830 | } | |
2831 | ||
2832 | /* Messy cases: unanchored match. */ | |
bbe252da | 2833 | if ((prog->anchored_substr || prog->anchored_utf8) && prog->intflags & PREGf_SKIP) { |
6eb5f6b9 | 2834 | /* we have /x+whatever/ */ |
984e6dd1 | 2835 | /* it must be a one character string (XXXX Except is_utf8_pat?) */ |
33b8afdf | 2836 | char ch; |
bf93d4cc GS |
2837 | #ifdef DEBUGGING |
2838 | int did_match = 0; | |
2839 | #endif | |
f2ed9b32 | 2840 | if (utf8_target) { |
7e0d5ad7 KW |
2841 | if (! prog->anchored_utf8) { |
2842 | to_utf8_substr(prog); | |
2843 | } | |
2844 | ch = SvPVX_const(prog->anchored_utf8)[0]; | |
4cadc6a9 | 2845 | REXEC_FBC_SCAN( |
6eb5f6b9 | 2846 | if (*s == ch) { |
a3621e74 | 2847 | DEBUG_EXECUTE_r( did_match = 1 ); |
02d5137b | 2848 | if (regtry(reginfo, &s)) goto got_it; |
6eb5f6b9 JH |
2849 | s += UTF8SKIP(s); |
2850 | while (s < strend && *s == ch) | |
2851 | s += UTF8SKIP(s); | |
2852 | } | |
4cadc6a9 | 2853 | ); |
7e0d5ad7 | 2854 | |
6eb5f6b9 JH |
2855 | } |
2856 | else { | |
7e0d5ad7 KW |
2857 | if (! prog->anchored_substr) { |
2858 | if (! to_byte_substr(prog)) { | |
6b54ddc5 | 2859 | NON_UTF8_TARGET_BUT_UTF8_REQUIRED(phooey); |
7e0d5ad7 KW |
2860 | } |
2861 | } | |
2862 | ch = SvPVX_const(prog->anchored_substr)[0]; | |
4cadc6a9 | 2863 | REXEC_FBC_SCAN( |
6eb5f6b9 | 2864 | if (*s == ch) { |
a3621e74 | 2865 | DEBUG_EXECUTE_r( did_match = 1 ); |
02d5137b | 2866 | if (regtry(reginfo, &s)) goto got_it; |
6eb5f6b9 JH |
2867 | s++; |
2868 | while (s < strend && *s == ch) | |
2869 | s++; | |
2870 | } | |
4cadc6a9 | 2871 | ); |
6eb5f6b9 | 2872 | } |
a3621e74 | 2873 | DEBUG_EXECUTE_r(if (!did_match) |
bf93d4cc | 2874 | PerlIO_printf(Perl_debug_log, |
b7953727 JH |
2875 | "Did not find anchored character...\n") |
2876 | ); | |
6eb5f6b9 | 2877 | } |
a0714e2c SS |
2878 | else if (prog->anchored_substr != NULL |
2879 | || prog->anchored_utf8 != NULL | |
2880 | || ((prog->float_substr != NULL || prog->float_utf8 != NULL) | |
33b8afdf JH |
2881 | && prog->float_max_offset < strend - s)) { |
2882 | SV *must; | |
ea3daa5d FC |
2883 | SSize_t back_max; |
2884 | SSize_t back_min; | |
33b8afdf | 2885 | char *last; |
6eb5f6b9 | 2886 | char *last1; /* Last position checked before */ |
bf93d4cc GS |
2887 | #ifdef DEBUGGING |
2888 | int did_match = 0; | |
2889 | #endif | |
33b8afdf | 2890 | if (prog->anchored_substr || prog->anchored_utf8) { |
7e0d5ad7 KW |
2891 | if (utf8_target) { |
2892 | if (! prog->anchored_utf8) { | |
2893 | to_utf8_substr(prog); | |
2894 | } | |
2895 | must = prog->anchored_utf8; | |
2896 | } | |
2897 | else { | |
2898 | if (! prog->anchored_substr) { | |
2899 | if (! to_byte_substr(prog)) { | |
6b54ddc5 | 2900 | NON_UTF8_TARGET_BUT_UTF8_REQUIRED(phooey); |
7e0d5ad7 KW |
2901 | } |
2902 | } | |
2903 | must = prog->anchored_substr; | |
2904 | } | |
33b8afdf JH |
2905 | back_max = back_min = prog->anchored_offset; |
2906 | } else { | |
7e0d5ad7 KW |
2907 | if (utf8_target) { |
2908 | if (! prog->float_utf8) { | |
2909 | to_utf8_substr(prog); | |
2910 | } | |
2911 | must = prog->float_utf8; | |
2912 | } | |
2913 | else { | |
2914 | if (! prog->float_substr) { | |
2915 | if (! to_byte_substr(prog)) { | |
6b54ddc5 | 2916 | NON_UTF8_TARGET_BUT_UTF8_REQUIRED(phooey); |
7e0d5ad7 KW |
2917 | } |
2918 | } | |
2919 | must = prog->float_substr; | |
2920 | } | |
33b8afdf JH |
2921 | back_max = prog->float_max_offset; |
2922 | back_min = prog->float_min_offset; | |
2923 | } | |
1de06328 | 2924 | |
1de06328 YO |
2925 | if (back_min<0) { |
2926 | last = strend; | |
2927 | } else { | |
2928 | last = HOP3c(strend, /* Cannot start after this */ | |
ea3daa5d | 2929 | -(SSize_t)(CHR_SVLEN(must) |
1de06328 YO |
2930 | - (SvTAIL(must) != 0) + back_min), strbeg); |
2931 | } | |
9d9163fb | 2932 | if (s > reginfo->strbeg) |
6eb5f6b9 JH |
2933 | last1 = HOPc(s, -1); |
2934 | else | |
2935 | last1 = s - 1; /* bogus */ | |
2936 | ||
a0288114 | 2937 | /* XXXX check_substr already used to find "s", can optimize if |
6eb5f6b9 | 2938 | check_substr==must. */ |
bf05793b | 2939 | dontbother = 0; |
6eb5f6b9 JH |
2940 | strend = HOPc(strend, -dontbother); |
2941 | while ( (s <= last) && | |
e50d57d4 | 2942 | (s = fbm_instr((unsigned char*)HOP4c(s, back_min, strbeg, strend), |
9041c2e3 | 2943 | (unsigned char*)strend, must, |
c33e64f0 | 2944 | multiline ? FBMrf_MULTILINE : 0)) ) { |
a3621e74 | 2945 | DEBUG_EXECUTE_r( did_match = 1 ); |
6eb5f6b9 JH |
2946 | if (HOPc(s, -back_max) > last1) { |
2947 | last1 = HOPc(s, -back_min); | |
2948 | s = HOPc(s, -back_max); | |
2949 | } | |
2950 | else { | |
9d9163fb DM |
2951 | char * const t = (last1 >= reginfo->strbeg) |
2952 | ? HOPc(last1, 1) : last1 + 1; | |
6eb5f6b9 JH |
2953 | |
2954 | last1 = HOPc(s, -back_min); | |
52657f30 | 2955 | s = t; |
6eb5f6b9 | 2956 | } |
f2ed9b32 | 2957 | if (utf8_target) { |
6eb5f6b9 | 2958 | while (s <= last1) { |
02d5137b | 2959 | if (regtry(reginfo, &s)) |
6eb5f6b9 | 2960 | goto got_it; |
7016d6eb DM |
2961 | if (s >= last1) { |
2962 | s++; /* to break out of outer loop */ | |
2963 | break; | |
2964 | } | |
2965 | s += UTF8SKIP(s); | |
6eb5f6b9 JH |
2966 | } |
2967 | } | |
2968 | else { | |
2969 | while (s <= last1) { | |
02d5137b | 2970 | if (regtry(reginfo, &s)) |
6eb5f6b9 JH |
2971 | goto got_it; |
2972 | s++; | |
2973 | } | |
2974 | } | |
2975 | } | |
ab3bbdeb | 2976 | DEBUG_EXECUTE_r(if (!did_match) { |
f2ed9b32 | 2977 | RE_PV_QUOTED_DECL(quoted, utf8_target, PERL_DEBUG_PAD_ZERO(0), |
ab3bbdeb YO |
2978 | SvPVX_const(must), RE_SV_DUMPLEN(must), 30); |
2979 | PerlIO_printf(Perl_debug_log, "Did not find %s substr %s%s...\n", | |
33b8afdf | 2980 | ((must == prog->anchored_substr || must == prog->anchored_utf8) |
bf93d4cc | 2981 | ? "anchored" : "floating"), |
ab3bbdeb YO |
2982 | quoted, RE_SV_TAIL(must)); |
2983 | }); | |
6eb5f6b9 JH |
2984 | goto phooey; |
2985 | } | |
f8fc2ecf | 2986 | else if ( (c = progi->regstclass) ) { |
f14c76ed | 2987 | if (minlen) { |
f8fc2ecf | 2988 | const OPCODE op = OP(progi->regstclass); |
66e933ab | 2989 | /* don't bother with what can't match */ |
786e8c11 | 2990 | if (PL_regkind[op] != EXACT && op != CANY && PL_regkind[op] != TRIE) |
f14c76ed RGS |
2991 | strend = HOPc(strend, -(minlen - 1)); |
2992 | } | |
a3621e74 | 2993 | DEBUG_EXECUTE_r({ |
be8e71aa | 2994 | SV * const prop = sv_newmortal(); |
8b9781c9 | 2995 | regprop(prog, prop, c, reginfo, NULL); |
0df25f3d | 2996 | { |
f2ed9b32 | 2997 | RE_PV_QUOTED_DECL(quoted,utf8_target,PERL_DEBUG_PAD_ZERO(1), |
ab3bbdeb | 2998 | s,strend-s,60); |
0df25f3d | 2999 | PerlIO_printf(Perl_debug_log, |
1c8f8eb1 | 3000 | "Matching stclass %.*s against %s (%d bytes)\n", |
e4f74956 | 3001 | (int)SvCUR(prop), SvPVX_const(prop), |
ab3bbdeb | 3002 | quoted, (int)(strend - s)); |
0df25f3d | 3003 | } |
ffc61ed2 | 3004 | }); |
f9176b44 | 3005 | if (find_byclass(prog, c, s, strend, reginfo)) |
6eb5f6b9 | 3006 | goto got_it; |
07be1b83 | 3007 | DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "Contradicts stclass... [regexec_flags]\n")); |
d6a28714 JH |
3008 | } |
3009 | else { | |
3010 | dontbother = 0; | |
a0714e2c | 3011 | if (prog->float_substr != NULL || prog->float_utf8 != NULL) { |
33b8afdf | 3012 | /* Trim the end. */ |
6af40bd7 | 3013 | char *last= NULL; |
33b8afdf | 3014 | SV* float_real; |
c33e64f0 FC |
3015 | STRLEN len; |
3016 | const char *little; | |
33b8afdf | 3017 | |
7e0d5ad7 KW |
3018 | if (utf8_target) { |
3019 | if (! prog->float_utf8) { | |
3020 | to_utf8_substr(prog); | |
3021 | } | |
3022 | float_real = prog->float_utf8; | |
3023 | } | |
3024 | else { | |
3025 | if (! prog->float_substr) { | |
3026 | if (! to_byte_substr(prog)) { | |
6b54ddc5 | 3027 | NON_UTF8_TARGET_BUT_UTF8_REQUIRED(phooey); |
7e0d5ad7 KW |
3028 | } |
3029 | } | |
3030 | float_real = prog->float_substr; | |
3031 | } | |
d6a28714 | 3032 | |
c33e64f0 FC |
3033 | little = SvPV_const(float_real, len); |
3034 | if (SvTAIL(float_real)) { | |
7f18ad16 KW |
3035 | /* This means that float_real contains an artificial \n on |
3036 | * the end due to the presence of something like this: | |
3037 | * /foo$/ where we can match both "foo" and "foo\n" at the | |
3038 | * end of the string. So we have to compare the end of the | |
3039 | * string first against the float_real without the \n and | |
3040 | * then against the full float_real with the string. We | |
3041 | * have to watch out for cases where the string might be | |
3042 | * smaller than the float_real or the float_real without | |
3043 | * the \n. */ | |
1a13b075 YO |
3044 | char *checkpos= strend - len; |
3045 | DEBUG_OPTIMISE_r( | |
3046 | PerlIO_printf(Perl_debug_log, | |
3047 | "%sChecking for float_real.%s\n", | |
3048 | PL_colors[4], PL_colors[5])); | |
3049 | if (checkpos + 1 < strbeg) { | |
7f18ad16 KW |
3050 | /* can't match, even if we remove the trailing \n |
3051 | * string is too short to match */ | |
1a13b075 YO |
3052 | DEBUG_EXECUTE_r( |
3053 | PerlIO_printf(Perl_debug_log, | |
3054 | "%sString shorter than required trailing substring, cannot match.%s\n", | |
3055 | PL_colors[4], PL_colors[5])); | |
3056 | goto phooey; | |
3057 | } else if (memEQ(checkpos + 1, little, len - 1)) { | |
7f18ad16 KW |
3058 | /* can match, the end of the string matches without the |
3059 | * "\n" */ | |
1a13b075 YO |
3060 | last = checkpos + 1; |
3061 | } else if (checkpos < strbeg) { | |
7f18ad16 KW |
3062 | /* cant match, string is too short when the "\n" is |
3063 | * included */ | |
1a13b075 YO |
3064 | DEBUG_EXECUTE_r( |
3065 | PerlIO_printf(Perl_debug_log, | |
3066 | "%sString does not contain required trailing substring, cannot match.%s\n", | |
3067 | PL_colors[4], PL_colors[5])); | |
3068 | goto phooey; | |
3069 | } else if (!multiline) { | |
7f18ad16 KW |
3070 | /* non multiline match, so compare with the "\n" at the |
3071 | * end of the string */ | |
1a13b075 YO |
3072 | if (memEQ(checkpos, little, len)) { |
3073 | last= checkpos; | |
3074 | } else { | |
3075 | DEBUG_EXECUTE_r( | |
3076 | PerlIO_printf(Perl_debug_log, | |
3077 | "%sString does not contain required trailing substring, cannot match.%s\n", | |
3078 | PL_colors[4], PL_colors[5])); | |
3079 | goto phooey; | |
3080 | } | |
3081 | } else { | |
7f18ad16 KW |
3082 | /* multiline match, so we have to search for a place |
3083 | * where the full string is located */ | |
d6a28714 | 3084 | goto find_last; |
1a13b075 | 3085 | } |
c33e64f0 | 3086 | } else { |
d6a28714 | 3087 | find_last: |
9041c2e3 | 3088 | if (len) |
d6a28714 | 3089 | last = rninstr(s, strend, little, little + len); |
b8c5462f | 3090 | else |
a0288114 | 3091 | last = strend; /* matching "$" */ |
b8c5462f | 3092 | } |
6af40bd7 | 3093 | if (!last) { |
7f18ad16 KW |
3094 | /* at one point this block contained a comment which was |
3095 | * probably incorrect, which said that this was a "should not | |
3096 | * happen" case. Even if it was true when it was written I am | |
3097 | * pretty sure it is not anymore, so I have removed the comment | |
3098 | * and replaced it with this one. Yves */ | |
6bda09f9 YO |
3099 | DEBUG_EXECUTE_r( |
3100 | PerlIO_printf(Perl_debug_log, | |
b729e729 YO |
3101 | "%sString does not contain required substring, cannot match.%s\n", |
3102 | PL_colors[4], PL_colors[5] | |
6af40bd7 YO |
3103 | )); |
3104 | goto phooey; | |
bf93d4cc | 3105 | } |
d6a28714 JH |
3106 | dontbother = strend - last + prog->float_min_offset; |
3107 | } | |
3108 | if (minlen && (dontbother < minlen)) | |
3109 | dontbother = minlen - 1; | |
3110 | strend -= dontbother; /* this one's always in bytes! */ | |
3111 | /* We don't know much -- general case. */ | |
f2ed9b32 | 3112 | if (utf8_target) { |
d6a28714 | 3113 | for (;;) { |
02d5137b | 3114 | if (regtry(reginfo, &s)) |
d6a28714 JH |
3115 | goto got_it; |
3116 | if (s >= strend) | |
3117 | break; | |
b8c5462f | 3118 | s += UTF8SKIP(s); |
d6a28714 JH |
3119 | }; |
3120 | } | |
3121 | else { | |
3122 | do { | |
02d5137b | 3123 | if (regtry(reginfo, &s)) |
d6a28714 JH |
3124 | goto got_it; |
3125 | } while (s++ < strend); | |
3126 | } | |
3127 | } | |
3128 | ||
3129 | /* Failure. */ | |
3130 | goto phooey; | |
3131 | ||
3132 | got_it: | |
d5e7783a DM |
3133 | /* s/// doesn't like it if $& is earlier than where we asked it to |
3134 | * start searching (which can happen on something like /.\G/) */ | |
3135 | if ( (flags & REXEC_FAIL_ON_UNDERFLOW) | |
3136 | && (prog->offs[0].start < stringarg - strbeg)) | |
3137 | { | |
3138 | /* this should only be possible under \G */ | |
58430ea8 | 3139 | assert(prog->intflags & PREGf_GPOS_SEEN); |
d5e7783a DM |
3140 | DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, |
3141 | "matched, but failing for REXEC_FAIL_ON_UNDERFLOW\n")); | |
3142 | goto phooey; | |
3143 | } | |
3144 | ||
495f47a5 DM |
3145 | DEBUG_BUFFERS_r( |
3146 | if (swap) | |
3147 | PerlIO_printf(Perl_debug_log, | |
3148 | "rex=0x%"UVxf" freeing offs: 0x%"UVxf"\n", | |
3149 | PTR2UV(prog), | |
3150 | PTR2UV(swap) | |
3151 | ); | |
3152 | ); | |
e9105d30 | 3153 | Safefree(swap); |
d6a28714 | 3154 | |
bf2039a9 DM |
3155 | /* clean up; this will trigger destructors that will free all slabs |
3156 | * above the current one, and cleanup the regmatch_info_aux | |
3157 | * and regmatch_info_aux_eval sructs */ | |
8adc0f72 | 3158 | |
006f26b2 DM |
3159 | LEAVE_SCOPE(oldsave); |
3160 | ||
5daac39c NC |
3161 | if (RXp_PAREN_NAMES(prog)) |
3162 | (void)hv_iterinit(RXp_PAREN_NAMES(prog)); | |
d6a28714 JH |
3163 | |
3164 | /* make sure $`, $&, $', and $digit will work later */ | |
60165aa4 | 3165 | if ( !(flags & REXEC_NOT_FIRST) ) |
749f4950 | 3166 | S_reg_set_capture_string(aTHX_ rx, |
60165aa4 DM |
3167 | strbeg, reginfo->strend, |
3168 | sv, flags, utf8_target); | |
9041c2e3 | 3169 | |
d6a28714 JH |
3170 | return 1; |
3171 | ||
3172 | phooey: | |
a3621e74 | 3173 | DEBUG_EXECUTE_r(PerlIO_printf(Perl_debug_log, "%sMatch failed%s\n", |
e4584336 | 3174 | PL_colors[4], PL_colors[5])); |
8adc0f72 | 3175 | |
bf2039a9 DM |
3176 | /* clean up; this will trigger destructors that will free all slabs |
3177 | * above the current one, and cleanup the regmatch_info_aux | |
3178 | * and regmatch_info_aux_eval sructs */ | |
8adc0f72 | 3179 | |
006f26b2 DM |
3180 | LEAVE_SCOPE(oldsave); |
3181 | ||
e9105d30 | 3182 | if (swap) { |
c74340f9 | 3183 | /* we failed :-( roll it back */ |
495f47a5 DM |
3184 | DEBUG_BUFFERS_r(PerlIO_printf(Perl_debug_log, |
3185 | "rex=0x%"UVxf" rolling back offs: freeing=0x%"UVxf" restoring=0x%"UVxf"\n", | |
3186 | PTR2UV(prog), | |
3187 | PTR2UV(prog->offs), | |
3188 | PTR2UV(swap) | |
3189 | )); | |
e9105d30 GG |
3190 | Safefree(prog->offs); |
3191 | prog->offs = swap; | |
3192 | } | |
d6a28714 JH |
3193 | return 0; |
3194 | } | |
3195 | ||
6bda09f9 | 3196 | |
b3d298be | 3197 | /* Set which rex is pointed to by PL_reg_curpm, handling ref counting. |
ec43f78b | 3198 | * Do inc before dec, in case old and new rex are the same */ |
baa60164 | 3199 | #define SET_reg_curpm(Re2) \ |
bf2039a9 | 3200 | if (reginfo->info_aux_eval) { \ |
ec43f78b DM |
3201 | (void)ReREFCNT_inc(Re2); \ |
3202 | ReREFCNT_dec(PM_GETRE(PL_reg_curpm)); \ | |
3203 | PM_SETRE((PL_reg_curpm), (Re2)); \ | |
3204 | } | |
3205 | ||
3206 | ||
d6a28714 JH |
3207 | /* |
3208 | - regtry - try match at specific point | |
3209 | */ | |
3210 | STATIC I32 /* 0 failure, 1 success */ | |
f73aaa43 | 3211 | S_regtry(pTHX_ regmatch_info *reginfo, char **startposp) |
d6a28714 | 3212 | { |
d6a28714 | 3213 | CHECKPOINT lastcp; |
288b8c02 | 3214 | REGEXP *const rx = reginfo->prog; |
8d919b0a | 3215 | regexp *const prog = ReANY(rx); |
99a90e59 | 3216 | SSize_t result; |
f8fc2ecf | 3217 | RXi_GET_DECL(prog,progi); |
a3621e74 | 3218 | GET_RE_DEBUG_FLAGS_DECL; |
7918f24d NC |
3219 | |
3220 | PERL_ARGS_ASSERT_REGTRY; | |
3221 | ||
24b23f37 | 3222 | reginfo->cutpoint=NULL; |
d6a28714 | 3223 | |
9d9163fb | 3224 | prog->offs[0].start = *startposp - reginfo->strbeg; |
d6a28714 | 3225 | prog->lastparen = 0; |
03994de8 | 3226 | prog->lastcloseparen = 0; |
d6a28714 JH |
3227 | |
3228 | /* XXXX What this code is doing here?!!! There should be no need | |
b93070ed | 3229 | to do this again and again, prog->lastparen should take care of |
3dd2943c | 3230 | this! --ilya*/ |
dafc8851 JH |
3231 | |
3232 | /* Tests pat.t#187 and split.t#{13,14} seem to depend on this code. | |
3233 | * Actually, the code in regcppop() (which Ilya may be meaning by | |
b93070ed | 3234 | * prog->lastparen), is not needed at all by the test suite |
225593e1 DM |
3235 | * (op/regexp, op/pat, op/split), but that code is needed otherwise |
3236 | * this erroneously leaves $1 defined: "1" =~ /^(?:(\d)x)?\d$/ | |
3237 | * Meanwhile, this code *is* needed for the | |
daf18116 JH |
3238 | * above-mentioned test suite tests to succeed. The common theme |
3239 | * on those tests seems to be returning null fields from matches. | |
225593e1 | 3240 | * --jhi updated by dapm */ |
dafc8851 | 3241 | #if 1 |
d6a28714 | 3242 | if (prog->nparens) { |
b93070ed | 3243 | regexp_paren_pair *pp = prog->offs; |
eb578fdb | 3244 | I32 i; |
b93070ed | 3245 | for (i = prog->nparens; i > (I32)prog->lastparen; i--) { |
f0ab9afb NC |
3246 | ++pp; |
3247 | pp->start = -1; | |
3248 | pp->end = -1; | |
d6a28714 JH |
3249 | } |
3250 | } | |
dafc8851 | 3251 | #endif |
02db2b7b | 3252 | REGCP_SET(lastcp); |
f73aaa43 DM |
3253 | result = regmatch(reginfo, *startposp, progi->program + 1); |
3254 | if (result != -1) { | |
3255 | prog->offs[0].end = result; | |
d6a28714 JH |
3256 | return 1; |
3257 | } | |
24b23f37 | 3258 | if (reginfo->cutpoint) |
f73aaa43 | 3259 | *startposp= reginfo->cutpoint; |
02db2b7b | 3260 | REGCP_UNWIND(lastcp); |
d6a28714 JH |
3261 | return 0; |
3262 | } | |
3263 | ||
02db2b7b | 3264 | |
8ba1375e MJD |
3265 | #define sayYES goto yes |
3266 | #define sayNO goto no | |
262b90c4 | 3267 | #define sayNO_SILENT goto no_silent |
8ba1375e | 3268 | |
f9f4320a YO |
3269 | /* we dont use STMT_START/END here because it leads to |
3270 | "unreachable code" warnings, which are bogus, but distracting. */ | |
3271 | #define CACHEsayNO \ | |
c476f425 | 3272 | if (ST.cache_mask) \ |
2ac8ff4b | 3273 | reginfo->info_aux->poscache[ST.cache_offset] |= ST.cache_mask; \ |
f9f4320a | 3274 | sayNO |
3298f257 | 3275 | |
a3621e74 | 3276 | /* this is used to determine how far from the left messages like |
265c4333 YO |
3277 | 'failed...' are printed. It should be set such that messages |
3278 | are inline with the regop output that created them. | |
a3621e74 | 3279 | */ |
265c4333 | 3280 | #define REPORT_CODE_OFF 32 |
a3621e74 YO |
3281 | |
3282 | ||
40a82448 DM |
3283 | #define CHRTEST_UNINIT -1001 /* c1/c2 haven't been calculated yet */ |
3284 | #define CHRTEST_VOID -1000 /* the c1/c2 "next char" test should be skipped */ | |
79a2a0e8 KW |
3285 | #define CHRTEST_NOT_A_CP_1 -999 |
3286 | #define CHRTEST_NOT_A_CP_2 -998 | |
9e137952 | 3287 | |
5d9a96ca DM |
3288 | /* grab a new slab and return the first slot in it */ |
3289 | ||
3290 | STATIC regmatch_state * | |
3291 | S_push_slab(pTHX) | |
3292 | { | |
a35a87e7 | 3293 | #if PERL_VERSION < 9 && !defined(PERL_CORE) |
54df2634 NC |
3294 | dMY_CXT; |
3295 | #endif | |
5d9a96ca DM |
3296 | regmatch_slab *s = PL_regmatch_slab->next; |
3297 | if (!s) { | |
3298 | Newx(s, 1, regmatch_slab); | |
3299 | s->prev = PL_regmatch_slab; | |
3300 | s->next = NULL; | |
3301 | PL_regmatch_slab->next = s; | |
3302 | } | |
3303 | PL_regmatch_slab = s; | |
86545054 | 3304 | return SLAB_FIRST(s); |
5d9a96ca | 3305 | } |
5b47454d | 3306 | |
95b24440 | 3307 | |
40a82448 DM |
3308 | /* push a new state then goto it */ |
3309 | ||
4d5016e5 DM |
3310 | #define PUSH_STATE_GOTO(state, node, input) \ |
3311 | pushinput = input; \ | |
40a82448 DM |
3312 | scan = node; \ |
3313 | st->resume_state = state; \ | |
3314 | goto push_state; | |
3315 | ||
3316 | /* push a new state with success backtracking, then goto it */ | |
3317 | ||
4d5016e5 DM |
3318 | #define PUSH_YES_STATE_GOTO(state, node, input) \ |
3319 | pushinput = input; \ | |
40a82448 DM |
3320 | scan = node; \ |
3321 | st->resume_state = state; \ | |
3322 | goto push_yes_state; | |
3323 | ||
aa283a38 | 3324 | |
aa283a38 | 3325 | |
4d5016e5 | 3326 | |
d6a28714 | 3327 | /* |
95b24440 | 3328 | |
bf1f174e DM |
3329 | regmatch() - main matching routine |
3330 | ||
3331 | This is basically one big switch statement in a loop. We execute an op, | |
3332 | set 'next' to point the next op, and continue. If we come to a point which | |
3333 | we may need to backtrack to on failure such as (A|B|C), we push a | |
3334 | backtrack state onto the backtrack stack. On failure, we pop the top | |
3335 | state, and re-enter the loop at the state indicated. If there are no more | |
3336 | states to pop, we return failure. | |
3337 | ||
3338 | Sometimes we also need to backtrack on success; for example /A+/, where | |
3339 | after successfully matching one A, we need to go back and try to | |
3340 | match another one; similarly for lookahead assertions: if the assertion | |
3341 | completes successfully, we backtrack to the state just before the assertion | |
3342 | and then carry on. In these cases, the pushed state is marked as | |
3343 | 'backtrack on success too'. This marking is in fact done by a chain of | |
3344 | pointers, each pointing to the previous 'yes' state. On success, we pop to | |
3345 | the nearest yes state, discarding any intermediate failure-only states. | |
3346 | Sometimes a yes state is pushed just to force some cleanup code to be | |
3347 | called at the end of a successful match or submatch; e.g. (??{$re}) uses | |
3348 | it to free the inner regex. | |
3349 | ||
3350 | Note that failure backtracking rewinds the cursor position, while | |
3351 | success backtracking leaves it alone. | |
3352 | ||
3353 | A pattern is complete when the END op is executed, while a subpattern | |
3354 | such as (?=foo) is complete when the SUCCESS op is executed. Both of these | |
3355 | ops trigger the "pop to last yes state if any, otherwise return true" | |
3356 | behaviour. | |
3357 | ||
3358 | A common convention in this function is to use A and B to refer to the two | |
3359 | subpatterns (or to the first nodes thereof) in patterns like /A*B/: so A is | |
3360 | the subpattern to be matched possibly multiple times, while B is the entire | |
3361 | rest of the pattern. Variable and state names reflect this convention. | |
3362 | ||
3363 | The states in the main switch are the union of ops and failure/success of | |
3364 | substates associated with with that op. For example, IFMATCH is the op | |
3365 | that does lookahead assertions /(?=A)B/ and so the IFMATCH state means | |
3366 | 'execute IFMATCH'; while IFMATCH_A is a state saying that we have just | |
3367 | successfully matched A and IFMATCH_A_fail is a state saying that we have | |
3368 | just failed to match A. Resume states always come in pairs. The backtrack | |
3369 | state we push is marked as 'IFMATCH_A', but when that is popped, we resume | |
3370 | at IFMATCH_A or IFMATCH_A_fail, depending on whether we are backtracking | |
3371 | on success or failure. | |
3372 | ||
3373 | The struct that holds a backtracking state is actually a big union, with | |
3374 | one variant for each major type of op. The variable st points to the | |
3375 | top-most backtrack struct. To make the code clearer, within each | |
3376 | block of code we #define ST to alias the relevant union. | |
3377 | ||
3378 | Here's a concrete example of a (vastly oversimplified) IFMATCH | |
3379 | implementation: | |
3380 | ||
3381 | switch (state) { | |
3382 | .... | |
3383 | ||
3384 | #define ST st->u.ifmatch | |
3385 | ||
3386 | case IFMATCH: // we are executing the IFMATCH op, (?=A)B | |
3387 | ST.foo = ...; // some state we wish to save | |
95b24440 | 3388 | ... |
bf1f174e DM |
3389 | // push a yes backtrack state with a resume value of |
3390 | // IFMATCH_A/IFMATCH_A_fail, then continue execution at the | |
3391 | // first node of A: | |
4d5016e5 | 3392 | PUSH_YES_STATE_GOTO(IFMATCH_A, A, newinput); |
bf1f174e DM |
3393 | // NOTREACHED |
3394 | ||
3395 | case IFMATCH_A: // we have successfully executed A; now continue with B | |
3396 | next = B; | |
3397 | bar = ST.foo; // do something with the preserved value | |
3398 | break; | |
3399 | ||
3400 | case IFMATCH_A_fail: // A failed, so the assertion failed | |
3401 | ...; // do some housekeeping, then ... | |
3402 | sayNO; // propagate the failure | |
3403 | ||
3404 | #undef ST | |
95b24440 | 3405 | |
bf1f174e DM |
3406 | ... |
3407 | } | |
95b24440 | 3408 | |
bf1f174e DM |
3409 | For any old-timers reading this who are familiar with the old recursive |
3410 | approach, the code above is equivalent to: | |
95b24440 | 3411 | |
bf1f174e DM |
3412 | case IFMATCH: // we are executing the IFMATCH op, (?=A)B |
3413 | { | |
3414 | int foo = ... | |
95b24440 | 3415 | ... |
bf1f174e DM |
3416 | if (regmatch(A)) { |
3417 | next = B; | |
3418 | bar = foo; | |
3419 | break; | |
95b24440 | 3420 | } |
bf1f174e DM |
3421 | ...; // do some housekeeping, then ... |
3422 | sayNO; // propagate the failure | |
95b24440 | 3423 | } |
bf1f174e DM |
3424 | |
3425 | The topmost backtrack state, pointed to by st, is usually free. If you | |
3426 | want to claim it, populate any ST.foo fields in it with values you wish to | |
3427 | save, then do one of | |
3428 | ||
4d5016e5 DM |
3429 | PUSH_STATE_GOTO(resume_state, node, newinput); |
3430 | PUSH_YES_STATE_GOTO(resume_state, node, newinput); | |
bf1f174e DM |
3431 | |
3432 | which sets that backtrack state's resume value to 'resume_state', pushes a | |
3433 | new free entry to the top of the backtrack stack, then goes to 'node'. | |
3434 | On backtracking, the free slot is popped, and the saved state becomes the | |
3435 | new free state. An ST.foo field in this new top state can be temporarily | |
3436 | accessed to retrieve values, but once the main loop is re-entered, it | |
3437 | becomes available for reuse. | |
3438 | ||
3439 | Note that the depth of the backtrack stack constantly increases during the | |
3440 | left-to-right execution of the pattern, rather than going up and down with | |
3441 | the pattern nesting. For example the stack is at its maximum at Z at the | |
3442 | end of the pattern, rather than at X in the following: | |
3443 | ||
3444 | /(((X)+)+)+....(Y)+....Z/ | |
3445 | ||
3446 | The only exceptions to this are lookahead/behind assertions and the cut, | |
3447 | (?>A), which pop all the backtrack states associated with A before | |
3448 | continuing. | |
3449 | ||
486ec47a | 3450 | Backtrack state structs are allocated in slabs of about 4K in size. |
bf1f174e DM |
3451 | PL_regmatch_state and st always point to the currently active state, |
3452 | and PL_regmatch_slab points to the slab currently containing | |
3453 | PL_regmatch_state. The first time regmatch() is called, the first slab is | |
3454 | allocated, and is never freed until interpreter destruction. When the slab | |
3455 | is full, a new one is allocated and chained to the end. At exit from | |
3456 | regmatch(), slabs allocated since entry are freed. | |
3457 | ||
3458 | */ | |
95b24440 | 3459 | |
40a82448 | 3460 | |
5bc10b2c | 3461 | #define DEBUG_STATE_pp(pp) \ |
265c4333 | 3462 | DEBUG_STATE_r({ \ |
baa60164 | 3463 | DUMP_EXEC_POS(locinput, scan, utf8_target); \ |
5bc10b2c | 3464 | PerlIO_printf(Perl_debug_log, \ |
5d458dd8 | 3465 | " %*s"pp" %s%s%s%s%s\n", \ |
5bc10b2c | 3466 | depth*2, "", \ |
baa60164 | 3467 | PL_reg_name[st->resume_state], \ |
5d458dd8 YO |
3468 | ((st==yes_state||st==mark_state) ? "[" : ""), \ |
3469 | ((st==yes_state) ? "Y" : ""), \ | |
3470 | ((st==mark_state) ? "M" : ""), \ | |
3471 | ((st==yes_state||st==mark_state) ? "]" : "") \ | |
3472 | ); \ | |
265c4333 | 3473 | }); |
5bc10b2c | 3474 | |
40a82448 | 3475 | |
3dab1dad | 3476 | #define REG_NODE_NUM(x) ((x) ? (int)((x)-prog) : -1) |
95b24440 | 3477 | |
3df15adc | 3478 | #ifdef DEBUGGING |
5bc10b2c | 3479 | |
ab3bbdeb | 3480 | STATIC void |
f2ed9b32 | 3481 | S_debug_start_match(pTHX_ const REGEXP *prog, const bool utf8_target, |
ab3bbdeb YO |
3482 | const char *start, const char *end, const char *blurb) |
3483 | { | |
efd26800 | 3484 | const bool utf8_pat = RX_UTF8(prog) ? 1 : 0; |
7918f24d NC |
3485 | |
3486 | PERL_ARGS_ASSERT_DEBUG_START_MATCH; | |
3487 | ||
ab3bbdeb YO |
3488 | if (!PL_colorset) |
3489 | reginitcolors(); | |
3490 | { | |
3491 | RE_PV_QUOTED_DECL(s0, utf8_pat, PERL_DEBUG_PAD_ZERO(0), | |
d2c6dc5e | 3492 | RX_PRECOMP_const(prog), RX_PRELEN(prog), 60); |
ab3bbdeb | 3493 | |
f2ed9b32 | 3494 | RE_PV_QUOTED_DECL(s1, utf8_target, PERL_DEBUG_PAD_ZERO(1), |
ab3bbdeb YO |
3495 | start, end - start, 60); |
3496 | ||
3497 | PerlIO_printf(Perl_debug_log, | |
3498 | "%s%s REx%s %s against %s\n", | |
3499 | PL_colors[4], blurb, PL_colors[5], s0, s1); | |
3500 | ||
f2ed9b32 | 3501 | if (utf8_target||utf8_pat) |
1de06328 YO |
3502 | PerlIO_printf(Perl_debug_log, "UTF-8 %s%s%s...\n", |
3503 | utf8_pat ? "pattern" : "", | |
f2ed9b32 KW |
3504 | utf8_pat && utf8_target ? " and " : "", |
3505 | utf8_target ? "string" : "" | |
ab3bbdeb YO |
3506 | ); |
3507 | } | |
3508 | } | |
3df15adc YO |
3509 | |
3510 | STATIC void | |
786e8c11 YO |
3511 | S_dump_exec_pos(pTHX_ const char *locinput, |
3512 | const regnode *scan, | |
3513 | const char *loc_regeol, | |
3514 | const char *loc_bostr, | |
3515 | const char *loc_reg_starttry, | |
f2ed9b32 | 3516 | const bool utf8_target) |
07be1b83 | 3517 | { |
786e8c11 | 3518 | const int docolor = *PL_colors[0] || *PL_colors[2] || *PL_colors[4]; |
07be1b83 | 3519 | const int taill = (docolor ? 10 : 7); /* 3 chars for "> <" */ |
786e8c11 | 3520 | int l = (loc_regeol - locinput) > taill ? taill : (loc_regeol - locinput); |
07be1b83 YO |
3521 | /* The part of the string before starttry has one color |
3522 | (pref0_len chars), between starttry and current | |
3523 | position another one (pref_len - pref0_len chars), | |
3524 | after the current position the third one. | |
3525 | We assume that pref0_len <= pref_len, otherwise we | |
3526 | decrease pref0_len. */ | |
786e8c11 YO |
3527 | int pref_len = (locinput - loc_bostr) > (5 + taill) - l |
3528 | ? (5 + taill) - l : locinput - loc_bostr; | |
07be1b83 YO |
3529 | int pref0_len; |
3530 | ||
7918f24d NC |
3531 | PERL_ARGS_ASSERT_DUMP_EXEC_POS; |
3532 | ||
f2ed9b32 | 3533 | while (utf8_target && UTF8_IS_CONTINUATION(*(U8*)(locinput - pref_len))) |
07be1b83 | 3534 | pref_len++; |
786e8c11 YO |
3535 | pref0_len = pref_len - (locinput - loc_reg_starttry); |
3536 | if (l + pref_len < (5 + taill) && l < loc_regeol - locinput) | |
3537 | l = ( loc_regeol - locinput > (5 + taill) - pref_len | |
3538 | ? (5 + taill) - pref_len : loc_regeol - locinput); | |
f2ed9b32 | 3539 | while (utf8_target && UTF8_IS_CONTINUATION(*(U8*)(locinput + l))) |
07be1b83 YO |
3540 | l--; |
3541 | if (pref0_len < 0) | |
3542 | pref0_len = 0; | |
3543 | if (pref0_len > pref_len) | |
3544 | pref0_len = pref_len; | |
3545 | { | |