5 * "A fair jaw-cracker dwarf-language must be." --Samwise Gamgee
8 /* This file contains functions for compiling a regular expression. See
9 * also regexec.c which funnily enough, contains functions for executing
10 * a regular expression.
12 * This file is also copied at build time to ext/re/re_comp.c, where
13 * it's built with -DPERL_EXT_RE_BUILD -DPERL_EXT_RE_DEBUG -DPERL_EXT.
14 * This causes the main functions to be compiled under new names and with
15 * debugging support added, which makes "use re 'debug'" work.
18 /* NOTE: this is derived from Henry Spencer's regexp code, and should not
19 * confused with the original package (see point 3 below). Thanks, Henry!
22 /* Additional note: this code is very heavily munged from Henry's version
23 * in places. In some spots I've traded clarity for efficiency, so don't
24 * blame Henry for some of the lack of readability.
27 /* The names of the functions have been changed from regcomp and
28 * regexec to pregcomp and pregexec in order to avoid conflicts
29 * with the POSIX routines of the same names.
32 #ifdef PERL_EXT_RE_BUILD
37 * pregcomp and pregexec -- regsub and regerror are not used in perl
39 * Copyright (c) 1986 by University of Toronto.
40 * Written by Henry Spencer. Not derived from licensed software.
42 * Permission is granted to anyone to use this software for any
43 * purpose on any computer system, and to redistribute it freely,
44 * subject to the following restrictions:
46 * 1. The author is not responsible for the consequences of use of
47 * this software, no matter how awful, even if they arise
50 * 2. The origin of this software must not be misrepresented, either
51 * by explicit claim or by omission.
53 * 3. Altered versions must be plainly marked as such, and must not
54 * be misrepresented as being the original software.
57 **** Alterations to Henry's code are...
59 **** Copyright (C) 1991, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999,
60 **** 2000, 2001, 2002, 2003, 2004, 2005, 2006, by Larry Wall and others
62 **** You may distribute under the terms of either the GNU General Public
63 **** License or the Artistic License, as specified in the README file.
66 * Beware that some of this code is subtly aware of the way operator
67 * precedence is structured in regular expressions. Serious changes in
68 * regular-expression syntax might require a total rethink.
71 #define PERL_IN_REGCOMP_C
74 #ifndef PERL_IN_XSUB_RE
79 #ifdef PERL_IN_XSUB_RE
90 # if defined(BUGGY_MSC6)
91 /* MSC 6.00A breaks on op/regexp.t test 85 unless we turn this off */
92 # pragma optimize("a",off)
93 /* But MSC 6.00A is happy with 'w', for aliases only across function calls*/
94 # pragma optimize("w",on )
95 # endif /* BUGGY_MSC6 */
102 typedef struct RExC_state_t {
103 U32 flags; /* are we folding, multilining? */
104 char *precomp; /* uncompiled string. */
106 char *start; /* Start of input for compile */
107 char *end; /* End of input for compile */
108 char *parse; /* Input-scan pointer. */
109 I32 whilem_seen; /* number of WHILEM in this expr */
110 regnode *emit_start; /* Start of emitted-code area */
111 regnode *emit; /* Code-emit pointer; ®dummy = don't = compiling */
112 I32 naughty; /* How bad is this pattern? */
113 I32 sawback; /* Did we see \1, ...? */
115 I32 size; /* Code size. */
116 I32 npar; /* () count. */
122 char *starttry; /* -Dr: where regtry was called. */
123 #define RExC_starttry (pRExC_state->starttry)
127 #define RExC_flags (pRExC_state->flags)
128 #define RExC_precomp (pRExC_state->precomp)
129 #define RExC_rx (pRExC_state->rx)
130 #define RExC_start (pRExC_state->start)
131 #define RExC_end (pRExC_state->end)
132 #define RExC_parse (pRExC_state->parse)
133 #define RExC_whilem_seen (pRExC_state->whilem_seen)
134 #define RExC_offsets (pRExC_state->rx->offsets) /* I am not like the others */
135 #define RExC_emit (pRExC_state->emit)
136 #define RExC_emit_start (pRExC_state->emit_start)
137 #define RExC_naughty (pRExC_state->naughty)
138 #define RExC_sawback (pRExC_state->sawback)
139 #define RExC_seen (pRExC_state->seen)
140 #define RExC_size (pRExC_state->size)
141 #define RExC_npar (pRExC_state->npar)
142 #define RExC_extralen (pRExC_state->extralen)
143 #define RExC_seen_zerolen (pRExC_state->seen_zerolen)
144 #define RExC_seen_evals (pRExC_state->seen_evals)
145 #define RExC_utf8 (pRExC_state->utf8)
147 #define ISMULT1(c) ((c) == '*' || (c) == '+' || (c) == '?')
148 #define ISMULT2(s) ((*s) == '*' || (*s) == '+' || (*s) == '?' || \
149 ((*s) == '{' && regcurly(s)))
152 #undef SPSTART /* dratted cpp namespace... */
155 * Flags to be passed up and down.
157 #define WORST 0 /* Worst case. */
158 #define HASWIDTH 0x1 /* Known to match non-null strings. */
159 #define SIMPLE 0x2 /* Simple enough to be STAR/PLUS operand. */
160 #define SPSTART 0x4 /* Starts with * or +. */
161 #define TRYAGAIN 0x8 /* Weeded out a declaration. */
163 /* Length of a variant. */
165 typedef struct scan_data_t {
171 I32 last_end; /* min value, <0 unless valid. */
174 SV **longest; /* Either &l_fixed, or &l_float. */
178 I32 offset_float_min;
179 I32 offset_float_max;
183 struct regnode_charclass_class *start_class;
187 * Forward declarations for pregcomp()'s friends.
190 static const scan_data_t zero_scan_data =
191 { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
193 #define SF_BEFORE_EOL (SF_BEFORE_SEOL|SF_BEFORE_MEOL)
194 #define SF_BEFORE_SEOL 0x1
195 #define SF_BEFORE_MEOL 0x2
196 #define SF_FIX_BEFORE_EOL (SF_FIX_BEFORE_SEOL|SF_FIX_BEFORE_MEOL)
197 #define SF_FL_BEFORE_EOL (SF_FL_BEFORE_SEOL|SF_FL_BEFORE_MEOL)
200 # define SF_FIX_SHIFT_EOL (0+2)
201 # define SF_FL_SHIFT_EOL (0+4)
203 # define SF_FIX_SHIFT_EOL (+2)
204 # define SF_FL_SHIFT_EOL (+4)
207 #define SF_FIX_BEFORE_SEOL (SF_BEFORE_SEOL << SF_FIX_SHIFT_EOL)
208 #define SF_FIX_BEFORE_MEOL (SF_BEFORE_MEOL << SF_FIX_SHIFT_EOL)
210 #define SF_FL_BEFORE_SEOL (SF_BEFORE_SEOL << SF_FL_SHIFT_EOL)
211 #define SF_FL_BEFORE_MEOL (SF_BEFORE_MEOL << SF_FL_SHIFT_EOL) /* 0x20 */
212 #define SF_IS_INF 0x40
213 #define SF_HAS_PAR 0x80
214 #define SF_IN_PAR 0x100
215 #define SF_HAS_EVAL 0x200
216 #define SCF_DO_SUBSTR 0x400
217 #define SCF_DO_STCLASS_AND 0x0800
218 #define SCF_DO_STCLASS_OR 0x1000
219 #define SCF_DO_STCLASS (SCF_DO_STCLASS_AND|SCF_DO_STCLASS_OR)
220 #define SCF_WHILEM_VISITED_POS 0x2000
222 #define UTF (RExC_utf8 != 0)
223 #define LOC ((RExC_flags & PMf_LOCALE) != 0)
224 #define FOLD ((RExC_flags & PMf_FOLD) != 0)
226 #define OOB_UNICODE 12345678
227 #define OOB_NAMEDCLASS -1
229 #define CHR_SVLEN(sv) (UTF ? sv_len_utf8(sv) : SvCUR(sv))
230 #define CHR_DIST(a,b) (UTF ? utf8_distance(a,b) : a - b)
233 /* length of regex to show in messages that don't mark a position within */
234 #define RegexLengthToShowInErrorMessages 127
237 * If MARKER[12] are adjusted, be sure to adjust the constants at the top
238 * of t/op/regmesg.t, the tests in t/op/re_tests, and those in
239 * op/pragma/warn/regcomp.
241 #define MARKER1 "<-- HERE" /* marker as it appears in the description */
242 #define MARKER2 " <-- HERE " /* marker as it appears within the regex */
244 #define REPORT_LOCATION " in regex; marked by " MARKER1 " in m/%.*s" MARKER2 "%s/"
247 * Calls SAVEDESTRUCTOR_X if needed, then calls Perl_croak with the given
248 * arg. Show regex, up to a maximum length. If it's too long, chop and add
251 #define FAIL(msg) STMT_START { \
252 const char *ellipses = ""; \
253 IV len = RExC_end - RExC_precomp; \
256 SAVEDESTRUCTOR_X(clear_re,(void*)RExC_rx); \
257 if (len > RegexLengthToShowInErrorMessages) { \
258 /* chop 10 shorter than the max, to ensure meaning of "..." */ \
259 len = RegexLengthToShowInErrorMessages - 10; \
262 Perl_croak(aTHX_ "%s in regex m/%.*s%s/", \
263 msg, (int)len, RExC_precomp, ellipses); \
267 * Simple_vFAIL -- like FAIL, but marks the current location in the scan
269 #define Simple_vFAIL(m) STMT_START { \
270 const IV offset = RExC_parse - RExC_precomp; \
271 Perl_croak(aTHX_ "%s" REPORT_LOCATION, \
272 m, (int)offset, RExC_precomp, RExC_precomp + offset); \
276 * Calls SAVEDESTRUCTOR_X if needed, then Simple_vFAIL()
278 #define vFAIL(m) STMT_START { \
280 SAVEDESTRUCTOR_X(clear_re,(void*)RExC_rx); \
285 * Like Simple_vFAIL(), but accepts two arguments.
287 #define Simple_vFAIL2(m,a1) STMT_START { \
288 const IV offset = RExC_parse - RExC_precomp; \
289 S_re_croak2(aTHX_ m, REPORT_LOCATION, a1, \
290 (int)offset, RExC_precomp, RExC_precomp + offset); \
294 * Calls SAVEDESTRUCTOR_X if needed, then Simple_vFAIL2().
296 #define vFAIL2(m,a1) STMT_START { \
298 SAVEDESTRUCTOR_X(clear_re,(void*)RExC_rx); \
299 Simple_vFAIL2(m, a1); \
304 * Like Simple_vFAIL(), but accepts three arguments.
306 #define Simple_vFAIL3(m, a1, a2) STMT_START { \
307 const IV offset = RExC_parse - RExC_precomp; \
308 S_re_croak2(aTHX_ m, REPORT_LOCATION, a1, a2, \
309 (int)offset, RExC_precomp, RExC_precomp + offset); \
313 * Calls SAVEDESTRUCTOR_X if needed, then Simple_vFAIL3().
315 #define vFAIL3(m,a1,a2) STMT_START { \
317 SAVEDESTRUCTOR_X(clear_re,(void*)RExC_rx); \
318 Simple_vFAIL3(m, a1, a2); \
322 * Like Simple_vFAIL(), but accepts four arguments.
324 #define Simple_vFAIL4(m, a1, a2, a3) STMT_START { \
325 const IV offset = RExC_parse - RExC_precomp; \
326 S_re_croak2(aTHX_ m, REPORT_LOCATION, a1, a2, a3, \
327 (int)offset, RExC_precomp, RExC_precomp + offset); \
330 #define vWARN(loc,m) STMT_START { \
331 const IV offset = loc - RExC_precomp; \
332 Perl_warner(aTHX_ packWARN(WARN_REGEXP), "%s" REPORT_LOCATION, \
333 m, (int)offset, RExC_precomp, RExC_precomp + offset); \
336 #define vWARNdep(loc,m) STMT_START { \
337 const IV offset = loc - RExC_precomp; \
338 Perl_warner(aTHX_ packWARN2(WARN_DEPRECATED, WARN_REGEXP), \
339 "%s" REPORT_LOCATION, \
340 m, (int)offset, RExC_precomp, RExC_precomp + offset); \
344 #define vWARN2(loc, m, a1) STMT_START { \
345 const IV offset = loc - RExC_precomp; \
346 Perl_warner(aTHX_ packWARN(WARN_REGEXP), m REPORT_LOCATION, \
347 a1, (int)offset, RExC_precomp, RExC_precomp + offset); \
350 #define vWARN3(loc, m, a1, a2) STMT_START { \
351 const IV offset = loc - RExC_precomp; \
352 Perl_warner(aTHX_ packWARN(WARN_REGEXP), m REPORT_LOCATION, \
353 a1, a2, (int)offset, RExC_precomp, RExC_precomp + offset); \
356 #define vWARN4(loc, m, a1, a2, a3) STMT_START { \
357 const IV offset = loc - RExC_precomp; \
358 Perl_warner(aTHX_ packWARN(WARN_REGEXP), m REPORT_LOCATION, \
359 a1, a2, a3, (int)offset, RExC_precomp, RExC_precomp + offset); \
362 #define vWARN5(loc, m, a1, a2, a3, a4) STMT_START { \
363 const IV offset = loc - RExC_precomp; \
364 Perl_warner(aTHX_ packWARN(WARN_REGEXP), m REPORT_LOCATION, \
365 a1, a2, a3, a4, (int)offset, RExC_precomp, RExC_precomp + offset); \
369 /* Allow for side effects in s */
370 #define REGC(c,s) STMT_START { \
371 if (!SIZE_ONLY) *(s) = (c); else (void)(s); \
374 /* Macros for recording node offsets. 20001227 mjd@plover.com
375 * Nodes are numbered 1, 2, 3, 4. Node #n's position is recorded in
376 * element 2*n-1 of the array. Element #2n holds the byte length node #n.
377 * Element 0 holds the number n.
380 #define MJD_OFFSET_DEBUG(x)
381 /* #define MJD_OFFSET_DEBUG(x) DEBUG_r(Perl_warn_nocontext x) */
384 #define Set_Node_Offset_To_R(node,byte) STMT_START { \
386 MJD_OFFSET_DEBUG(("** (%d) offset of node %d is %d.\n", \
387 __LINE__, (node), (byte))); \
389 Perl_croak(aTHX_ "value of node is %d in Offset macro", (int)(node)); \
391 RExC_offsets[2*(node)-1] = (byte); \
396 #define Set_Node_Offset(node,byte) \
397 Set_Node_Offset_To_R((node)-RExC_emit_start, (byte)-RExC_start)
398 #define Set_Cur_Node_Offset Set_Node_Offset(RExC_emit, RExC_parse)
400 #define Set_Node_Length_To_R(node,len) STMT_START { \
402 MJD_OFFSET_DEBUG(("** (%d) size of node %d is %d.\n", \
403 __LINE__, (int)(node), (int)(len))); \
405 Perl_croak(aTHX_ "value of node is %d in Length macro", (int)(node)); \
407 RExC_offsets[2*(node)] = (len); \
412 #define Set_Node_Length(node,len) \
413 Set_Node_Length_To_R((node)-RExC_emit_start, len)
414 #define Set_Cur_Node_Length(len) Set_Node_Length(RExC_emit, len)
415 #define Set_Node_Cur_Length(node) \
416 Set_Node_Length(node, RExC_parse - parse_start)
418 /* Get offsets and lengths */
419 #define Node_Offset(n) (RExC_offsets[2*((n)-RExC_emit_start)-1])
420 #define Node_Length(n) (RExC_offsets[2*((n)-RExC_emit_start)])
422 static void clear_re(pTHX_ void *r);
424 /* Mark that we cannot extend a found fixed substring at this point.
425 Updata the longest found anchored substring and the longest found
426 floating substrings if needed. */
429 S_scan_commit(pTHX_ const RExC_state_t *pRExC_state, scan_data_t *data)
431 const STRLEN l = CHR_SVLEN(data->last_found);
432 const STRLEN old_l = CHR_SVLEN(*data->longest);
434 if ((l >= old_l) && ((l > old_l) || (data->flags & SF_BEFORE_EOL))) {
435 SvSetMagicSV(*data->longest, data->last_found);
436 if (*data->longest == data->longest_fixed) {
437 data->offset_fixed = l ? data->last_start_min : data->pos_min;
438 if (data->flags & SF_BEFORE_EOL)
440 |= ((data->flags & SF_BEFORE_EOL) << SF_FIX_SHIFT_EOL);
442 data->flags &= ~SF_FIX_BEFORE_EOL;
445 data->offset_float_min = l ? data->last_start_min : data->pos_min;
446 data->offset_float_max = (l
447 ? data->last_start_max
448 : data->pos_min + data->pos_delta);
449 if ((U32)data->offset_float_max > (U32)I32_MAX)
450 data->offset_float_max = I32_MAX;
451 if (data->flags & SF_BEFORE_EOL)
453 |= ((data->flags & SF_BEFORE_EOL) << SF_FL_SHIFT_EOL);
455 data->flags &= ~SF_FL_BEFORE_EOL;
458 SvCUR_set(data->last_found, 0);
460 SV * const sv = data->last_found;
461 if (SvUTF8(sv) && SvMAGICAL(sv)) {
462 MAGIC * const mg = mg_find(sv, PERL_MAGIC_utf8);
468 data->flags &= ~SF_BEFORE_EOL;
471 /* Can match anything (initialization) */
473 S_cl_anything(const RExC_state_t *pRExC_state, struct regnode_charclass_class *cl)
475 ANYOF_CLASS_ZERO(cl);
476 ANYOF_BITMAP_SETALL(cl);
477 cl->flags = ANYOF_EOS|ANYOF_UNICODE_ALL;
479 cl->flags |= ANYOF_LOCALE;
482 /* Can match anything (initialization) */
484 S_cl_is_anything(const struct regnode_charclass_class *cl)
488 for (value = 0; value <= ANYOF_MAX; value += 2)
489 if (ANYOF_CLASS_TEST(cl, value) && ANYOF_CLASS_TEST(cl, value + 1))
491 if (!(cl->flags & ANYOF_UNICODE_ALL))
493 if (!ANYOF_BITMAP_TESTALLSET(cl))
498 /* Can match anything (initialization) */
500 S_cl_init(const RExC_state_t *pRExC_state, struct regnode_charclass_class *cl)
502 Zero(cl, 1, struct regnode_charclass_class);
504 cl_anything(pRExC_state, cl);
508 S_cl_init_zero(const RExC_state_t *pRExC_state, struct regnode_charclass_class *cl)
510 Zero(cl, 1, struct regnode_charclass_class);
512 cl_anything(pRExC_state, cl);
514 cl->flags |= ANYOF_LOCALE;
517 /* 'And' a given class with another one. Can create false positives */
518 /* We assume that cl is not inverted */
520 S_cl_and(struct regnode_charclass_class *cl,
521 const struct regnode_charclass_class *and_with)
523 if (!(and_with->flags & ANYOF_CLASS)
524 && !(cl->flags & ANYOF_CLASS)
525 && (and_with->flags & ANYOF_LOCALE) == (cl->flags & ANYOF_LOCALE)
526 && !(and_with->flags & ANYOF_FOLD)
527 && !(cl->flags & ANYOF_FOLD)) {
530 if (and_with->flags & ANYOF_INVERT)
531 for (i = 0; i < ANYOF_BITMAP_SIZE; i++)
532 cl->bitmap[i] &= ~and_with->bitmap[i];
534 for (i = 0; i < ANYOF_BITMAP_SIZE; i++)
535 cl->bitmap[i] &= and_with->bitmap[i];
536 } /* XXXX: logic is complicated otherwise, leave it along for a moment. */
537 if (!(and_with->flags & ANYOF_EOS))
538 cl->flags &= ~ANYOF_EOS;
540 if (cl->flags & ANYOF_UNICODE_ALL && and_with->flags & ANYOF_UNICODE &&
541 !(and_with->flags & ANYOF_INVERT)) {
542 cl->flags &= ~ANYOF_UNICODE_ALL;
543 cl->flags |= ANYOF_UNICODE;
544 ARG_SET(cl, ARG(and_with));
546 if (!(and_with->flags & ANYOF_UNICODE_ALL) &&
547 !(and_with->flags & ANYOF_INVERT))
548 cl->flags &= ~ANYOF_UNICODE_ALL;
549 if (!(and_with->flags & (ANYOF_UNICODE|ANYOF_UNICODE_ALL)) &&
550 !(and_with->flags & ANYOF_INVERT))
551 cl->flags &= ~ANYOF_UNICODE;
554 /* 'OR' a given class with another one. Can create false positives */
555 /* We assume that cl is not inverted */
557 S_cl_or(const RExC_state_t *pRExC_state, struct regnode_charclass_class *cl, const struct regnode_charclass_class *or_with)
559 if (or_with->flags & ANYOF_INVERT) {
561 * (B1 | CL1) | (!B2 & !CL2) = (B1 | !B2 & !CL2) | (CL1 | (!B2 & !CL2))
562 * <= (B1 | !B2) | (CL1 | !CL2)
563 * which is wasteful if CL2 is small, but we ignore CL2:
564 * (B1 | CL1) | (!B2 & !CL2) <= (B1 | CL1) | !B2 = (B1 | !B2) | CL1
565 * XXXX Can we handle case-fold? Unclear:
566 * (OK1(i) | OK1(i')) | !(OK1(i) | OK1(i')) =
567 * (OK1(i) | OK1(i')) | (!OK1(i) & !OK1(i'))
569 if ( (or_with->flags & ANYOF_LOCALE) == (cl->flags & ANYOF_LOCALE)
570 && !(or_with->flags & ANYOF_FOLD)
571 && !(cl->flags & ANYOF_FOLD) ) {
574 for (i = 0; i < ANYOF_BITMAP_SIZE; i++)
575 cl->bitmap[i] |= ~or_with->bitmap[i];
576 } /* XXXX: logic is complicated otherwise */
578 cl_anything(pRExC_state, cl);
581 /* (B1 | CL1) | (B2 | CL2) = (B1 | B2) | (CL1 | CL2)) */
582 if ( (or_with->flags & ANYOF_LOCALE) == (cl->flags & ANYOF_LOCALE)
583 && (!(or_with->flags & ANYOF_FOLD)
584 || (cl->flags & ANYOF_FOLD)) ) {
587 /* OR char bitmap and class bitmap separately */
588 for (i = 0; i < ANYOF_BITMAP_SIZE; i++)
589 cl->bitmap[i] |= or_with->bitmap[i];
590 if (or_with->flags & ANYOF_CLASS) {
591 for (i = 0; i < ANYOF_CLASSBITMAP_SIZE; i++)
592 cl->classflags[i] |= or_with->classflags[i];
593 cl->flags |= ANYOF_CLASS;
596 else { /* XXXX: logic is complicated, leave it along for a moment. */
597 cl_anything(pRExC_state, cl);
600 if (or_with->flags & ANYOF_EOS)
601 cl->flags |= ANYOF_EOS;
603 if (cl->flags & ANYOF_UNICODE && or_with->flags & ANYOF_UNICODE &&
604 ARG(cl) != ARG(or_with)) {
605 cl->flags |= ANYOF_UNICODE_ALL;
606 cl->flags &= ~ANYOF_UNICODE;
608 if (or_with->flags & ANYOF_UNICODE_ALL) {
609 cl->flags |= ANYOF_UNICODE_ALL;
610 cl->flags &= ~ANYOF_UNICODE;
616 make_trie(startbranch,first,last,tail,flags)
617 startbranch: the first branch in the whole branch sequence
618 first : start branch of sequence of branch-exact nodes.
619 May be the same as startbranch
620 last : Thing following the last branch.
621 May be the same as tail.
622 tail : item following the branch sequence
623 flags : currently the OP() type we will be building one of /EXACT(|F|Fl)/
625 Inplace optimizes a sequence of 2 or more Branch-Exact nodes into a TRIE node.
627 A trie is an N'ary tree where the branches are determined by digital
628 decomposition of the key. IE, at the root node you look up the 1st character and
629 follow that branch repeat until you find the end of the branches. Nodes can be
630 marked as "accepting" meaning they represent a complete word. Eg:
634 would convert into the following structure. Numbers represent states, letters
635 following numbers represent valid transitions on the letter from that state, if
636 the number is in square brackets it represents an accepting state, otherwise it
637 will be in parenthesis.
639 +-h->+-e->[3]-+-r->(8)-+-s->[9]
643 (1) +-i->(6)-+-s->[7]
645 +-s->(3)-+-h->(4)-+-e->[5]
647 Accept Word Mapping: 3=>1 (he),5=>2 (she), 7=>3 (his), 9=>4 (hers)
649 This shows that when matching against the string 'hers' we will begin at state 1
650 read 'h' and move to state 2, read 'e' and move to state 3 which is accepting,
651 then read 'r' and go to state 8 followed by 's' which takes us to state 9 which
652 is also accepting. Thus we know that we can match both 'he' and 'hers' with a
653 single traverse. We store a mapping from accepting to state to which word was
654 matched, and then when we have multiple possibilities we try to complete the
655 rest of the regex in the order in which they occured in the alternation.
657 The only prior NFA like behaviour that would be changed by the TRIE support is
658 the silent ignoring of duplicate alternations which are of the form:
660 / (DUPE|DUPE) X? (?{ ... }) Y /x
662 Thus EVAL blocks follwing a trie may be called a different number of times with
663 and without the optimisation. With the optimisations dupes will be silently
664 ignored. This inconsistant behaviour of EVAL type nodes is well established as
665 the following demonstrates:
667 'words'=~/(word|word|word)(?{ print $1 })[xyz]/
669 which prints out 'word' three times, but
671 'words'=~/(word|word|word)(?{ print $1 })S/
673 which doesnt print it out at all. This is due to other optimisations kicking in.
675 Example of what happens on a structural level:
677 The regexp /(ac|ad|ab)+/ will produce the folowing debug output:
679 1: CURLYM[1] {1,32767}(18)
690 This would be optimizable with startbranch=5, first=5, last=16, tail=16
691 and should turn into:
693 1: CURLYM[1] {1,32767}(18)
695 [Words:3 Chars Stored:6 Unique Chars:4 States:5 NCP:1]
703 Cases where tail != last would be like /(?foo|bar)baz/:
713 which would be optimizable with startbranch=1, first=1, last=7, tail=8
714 and would end up looking like:
717 [Words:2 Chars Stored:6 Unique Chars:5 States:7 NCP:1]
726 #define TRIE_DEBUG_CHAR \
727 DEBUG_TRIE_COMPILE_r({ \
730 tmp = newSVpvs( "" ); \
731 pv_uni_display( tmp, uc, len, 60, UNI_DISPLAY_REGEX ); \
733 tmp = Perl_newSVpvf_nocontext( "%c", (int)uvc ); \
735 av_push( trie->revcharmap, tmp ); \
738 #define TRIE_READ_CHAR STMT_START { \
741 if ( foldlen > 0 ) { \
742 uvc = utf8n_to_uvuni( scan, UTF8_MAXLEN, &len, uniflags ); \
747 uvc = utf8n_to_uvuni( (const U8*)uc, UTF8_MAXLEN, &len, uniflags);\
748 uvc = to_uni_fold( uvc, foldbuf, &foldlen ); \
749 foldlen -= UNISKIP( uvc ); \
750 scan = foldbuf + UNISKIP( uvc ); \
753 uvc = utf8n_to_uvuni( (const U8*)uc, UTF8_MAXLEN, &len, uniflags);\
762 #define TRIE_LIST_ITEM(state,idx) (trie->states[state].trans.list)[ idx ]
763 #define TRIE_LIST_CUR(state) ( TRIE_LIST_ITEM( state, 0 ).forid )
764 #define TRIE_LIST_LEN(state) ( TRIE_LIST_ITEM( state, 0 ).newstate )
765 #define TRIE_LIST_USED(idx) ( trie->states[state].trans.list ? (TRIE_LIST_CUR( idx ) - 1) : 0 )
767 #define TRIE_LIST_PUSH(state,fid,ns) STMT_START { \
768 if ( TRIE_LIST_CUR( state ) >=TRIE_LIST_LEN( state ) ) { \
769 TRIE_LIST_LEN( state ) *= 2; \
770 Renew( trie->states[ state ].trans.list, \
771 TRIE_LIST_LEN( state ), reg_trie_trans_le ); \
773 TRIE_LIST_ITEM( state, TRIE_LIST_CUR( state ) ).forid = fid; \
774 TRIE_LIST_ITEM( state, TRIE_LIST_CUR( state ) ).newstate = ns; \
775 TRIE_LIST_CUR( state )++; \
778 #define TRIE_LIST_NEW(state) STMT_START { \
779 Newxz( trie->states[ state ].trans.list, \
780 4, reg_trie_trans_le ); \
781 TRIE_LIST_CUR( state ) = 1; \
782 TRIE_LIST_LEN( state ) = 4; \
786 S_make_trie(pTHX_ RExC_state_t *pRExC_state, regnode *startbranch, regnode *first, regnode *last, regnode *tail, U32 flags)
789 /* first pass, loop through and scan words */
792 const U32 uniflags = UTF8_ALLOW_DEFAULT;
797 /* we just use folder as a flag in utf8 */
798 const U8 * const folder = ( flags == EXACTF
806 const U32 data_slot = add_data( pRExC_state, 1, "t" );
809 GET_RE_DEBUG_FLAGS_DECL;
811 Newxz( trie, 1, reg_trie_data );
813 RExC_rx->data->data[ data_slot ] = (void*)trie;
814 Newxz( trie->charmap, 256, U16 );
816 trie->words = newAV();
817 trie->revcharmap = newAV();
821 re_trie_maxbuff = get_sv(RE_TRIE_MAXBUF_NAME, 1);
822 if (!SvIOK(re_trie_maxbuff)) {
823 sv_setiv(re_trie_maxbuff, RE_TRIE_MAXBUF_INIT);
826 /* -- First loop and Setup --
828 We first traverse the branches and scan each word to determine if it
829 contains widechars, and how many unique chars there are, this is
830 important as we have to build a table with at least as many columns as we
833 We use an array of integers to represent the character codes 0..255
834 (trie->charmap) and we use a an HV* to store unicode characters. We use the
835 native representation of the character value as the key and IV's for the
838 *TODO* If we keep track of how many times each character is used we can
839 remap the columns so that the table compression later on is more
840 efficient in terms of memory by ensuring most common value is in the
841 middle and the least common are on the outside. IMO this would be better
842 than a most to least common mapping as theres a decent chance the most
843 common letter will share a node with the least common, meaning the node
844 will not be compressable. With a middle is most common approach the worst
845 case is when we have the least common nodes twice.
850 for ( cur = first ; cur < last ; cur = regnext( cur ) ) {
851 regnode * const noper = NEXTOPER( cur );
852 const U8 *uc = (U8*)STRING( noper );
853 const U8 * const e = uc + STR_LEN( noper );
855 U8 foldbuf[ UTF8_MAXBYTES_CASE + 1 ];
856 const U8 *scan = (U8*)NULL;
858 for ( ; uc < e ; uc += len ) {
862 if ( !trie->charmap[ uvc ] ) {
863 trie->charmap[ uvc ]=( ++trie->uniquecharcount );
865 trie->charmap[ folder[ uvc ] ] = trie->charmap[ uvc ];
870 if ( !trie->widecharmap )
871 trie->widecharmap = newHV();
873 svpp = hv_fetch( trie->widecharmap, (char*)&uvc, sizeof( UV ), 1 );
876 Perl_croak( aTHX_ "error creating/fetching widecharmap entry for 0x%"UVXf, uvc );
878 if ( !SvTRUE( *svpp ) ) {
879 sv_setiv( *svpp, ++trie->uniquecharcount );
885 } /* end first pass */
886 DEBUG_TRIE_COMPILE_r(
887 PerlIO_printf( Perl_debug_log, "TRIE(%s): W:%d C:%d Uq:%d \n",
888 ( trie->widecharmap ? "UTF8" : "NATIVE" ), trie->wordcount,
889 (int)trie->charcount, trie->uniquecharcount )
894 We now know what we are dealing with in terms of unique chars and
895 string sizes so we can calculate how much memory a naive
896 representation using a flat table will take. If it's over a reasonable
897 limit (as specified by ${^RE_TRIE_MAXBUF}) we use a more memory
898 conservative but potentially much slower representation using an array
901 At the end we convert both representations into the same compressed
902 form that will be used in regexec.c for matching with. The latter
903 is a form that cannot be used to construct with but has memory
904 properties similar to the list form and access properties similar
905 to the table form making it both suitable for fast searches and
906 small enough that its feasable to store for the duration of a program.
908 See the comment in the code where the compressed table is produced
909 inplace from the flat tabe representation for an explanation of how
910 the compression works.
915 if ( (IV)( ( trie->charcount + 1 ) * trie->uniquecharcount + 1) > SvIV(re_trie_maxbuff) ) {
917 Second Pass -- Array Of Lists Representation
919 Each state will be represented by a list of charid:state records
920 (reg_trie_trans_le) the first such element holds the CUR and LEN
921 points of the allocated array. (See defines above).
923 We build the initial structure using the lists, and then convert
924 it into the compressed table form which allows faster lookups
925 (but cant be modified once converted).
931 STRLEN transcount = 1;
933 Newxz( trie->states, trie->charcount + 2, reg_trie_state );
937 for ( cur = first ; cur < last ; cur = regnext( cur ) ) {
939 regnode * const noper = NEXTOPER( cur );
940 U8 *uc = (U8*)STRING( noper );
941 const U8 * const e = uc + STR_LEN( noper );
942 U32 state = 1; /* required init */
943 U16 charid = 0; /* sanity init */
944 U8 *scan = (U8*)NULL; /* sanity init */
945 STRLEN foldlen = 0; /* required init */
946 U8 foldbuf[ UTF8_MAXBYTES_CASE + 1 ];
948 for ( ; uc < e ; uc += len ) {
953 charid = trie->charmap[ uvc ];
955 SV** const svpp = hv_fetch( trie->widecharmap, (char*)&uvc, sizeof( UV ), 0);
959 charid=(U16)SvIV( *svpp );
968 if ( !trie->states[ state ].trans.list ) {
969 TRIE_LIST_NEW( state );
971 for ( check = 1; check <= TRIE_LIST_USED( state ); check++ ) {
972 if ( TRIE_LIST_ITEM( state, check ).forid == charid ) {
973 newstate = TRIE_LIST_ITEM( state, check ).newstate;
978 newstate = next_alloc++;
979 TRIE_LIST_PUSH( state, charid, newstate );
984 Perl_croak( aTHX_ "panic! In trie construction, no char mapping for %"IVdf, uvc );
986 /* charid is now 0 if we dont know the char read, or nonzero if we do */
989 if ( !trie->states[ state ].wordnum ) {
990 /* we havent inserted this word into the structure yet. */
991 trie->states[ state ].wordnum = ++curword;
994 /* store the word for dumping */
995 SV* tmp = newSVpvn( STRING( noper ), STR_LEN( noper ) );
996 if ( UTF ) SvUTF8_on( tmp );
997 av_push( trie->words, tmp );
1001 NOOP; /* It's a dupe. So ignore it. */
1004 } /* end second pass */
1006 trie->laststate = next_alloc;
1007 Renew( trie->states, next_alloc, reg_trie_state );
1009 DEBUG_TRIE_COMPILE_MORE_r({
1012 /* print out the table precompression. */
1014 PerlIO_printf( Perl_debug_log, "\nState :Word | Transition Data\n" );
1015 PerlIO_printf( Perl_debug_log, "------:-----+-----------------" );
1017 for( state=1 ; state < next_alloc ; state ++ ) {
1020 PerlIO_printf( Perl_debug_log, "\n %04"UVXf" :", (UV)state );
1021 if ( ! trie->states[ state ].wordnum ) {
1022 PerlIO_printf( Perl_debug_log, "%5s| ","");
1024 PerlIO_printf( Perl_debug_log, "W%04x| ",
1025 trie->states[ state ].wordnum
1028 for( charid = 1 ; charid <= TRIE_LIST_USED( state ) ; charid++ ) {
1029 SV **tmp = av_fetch( trie->revcharmap, TRIE_LIST_ITEM(state,charid).forid, 0);
1030 PerlIO_printf( Perl_debug_log, "%s:%3X=%04"UVXf" | ",
1031 SvPV_nolen_const( *tmp ),
1032 TRIE_LIST_ITEM(state,charid).forid,
1033 (UV)TRIE_LIST_ITEM(state,charid).newstate
1038 PerlIO_printf( Perl_debug_log, "\n\n" );
1041 Newxz( trie->trans, transcount ,reg_trie_trans );
1048 for( state=1 ; state < next_alloc ; state ++ ) {
1052 DEBUG_TRIE_COMPILE_MORE_r(
1053 PerlIO_printf( Perl_debug_log, "tp: %d zp: %d ",tp,zp)
1057 if (trie->states[state].trans.list) {
1058 U16 minid=TRIE_LIST_ITEM( state, 1).forid;
1062 for( idx = 2 ; idx <= TRIE_LIST_USED( state ) ; idx++ ) {
1063 const U16 forid = TRIE_LIST_ITEM( state, idx).forid;
1064 if ( forid < minid ) {
1066 } else if ( forid > maxid ) {
1070 if ( transcount < tp + maxid - minid + 1) {
1072 Renew( trie->trans, transcount, reg_trie_trans );
1073 Zero( trie->trans + (transcount / 2), transcount / 2 , reg_trie_trans );
1075 base = trie->uniquecharcount + tp - minid;
1076 if ( maxid == minid ) {
1078 for ( ; zp < tp ; zp++ ) {
1079 if ( ! trie->trans[ zp ].next ) {
1080 base = trie->uniquecharcount + zp - minid;
1081 trie->trans[ zp ].next = TRIE_LIST_ITEM( state, 1).newstate;
1082 trie->trans[ zp ].check = state;
1088 trie->trans[ tp ].next = TRIE_LIST_ITEM( state, 1).newstate;
1089 trie->trans[ tp ].check = state;
1094 for ( idx=1; idx <= TRIE_LIST_USED( state ) ; idx++ ) {
1095 const U32 tid = base - trie->uniquecharcount + TRIE_LIST_ITEM( state, idx ).forid;
1096 trie->trans[ tid ].next = TRIE_LIST_ITEM( state, idx ).newstate;
1097 trie->trans[ tid ].check = state;
1099 tp += ( maxid - minid + 1 );
1101 Safefree(trie->states[ state ].trans.list);
1104 DEBUG_TRIE_COMPILE_MORE_r(
1105 PerlIO_printf( Perl_debug_log, " base: %d\n",base);
1108 trie->states[ state ].trans.base=base;
1110 trie->lasttrans = tp + 1;
1114 Second Pass -- Flat Table Representation.
1116 we dont use the 0 slot of either trans[] or states[] so we add 1 to each.
1117 We know that we will need Charcount+1 trans at most to store the data
1118 (one row per char at worst case) So we preallocate both structures
1119 assuming worst case.
1121 We then construct the trie using only the .next slots of the entry
1124 We use the .check field of the first entry of the node temporarily to
1125 make compression both faster and easier by keeping track of how many non
1126 zero fields are in the node.
1128 Since trans are numbered from 1 any 0 pointer in the table is a FAIL
1131 There are two terms at use here: state as a TRIE_NODEIDX() which is a
1132 number representing the first entry of the node, and state as a
1133 TRIE_NODENUM() which is the trans number. state 1 is TRIE_NODEIDX(1) and
1134 TRIE_NODENUM(1), state 2 is TRIE_NODEIDX(2) and TRIE_NODENUM(3) if there
1135 are 2 entrys per node. eg:
1143 The table is internally in the right hand, idx form. However as we also
1144 have to deal with the states array which is indexed by nodenum we have to
1145 use TRIE_NODENUM() to convert.
1149 Newxz( trie->trans, ( trie->charcount + 1 ) * trie->uniquecharcount + 1,
1151 Newxz( trie->states, trie->charcount + 2, reg_trie_state );
1152 next_alloc = trie->uniquecharcount + 1;
1154 for ( cur = first ; cur < last ; cur = regnext( cur ) ) {
1156 regnode * const noper = NEXTOPER( cur );
1157 const U8 *uc = (U8*)STRING( noper );
1158 const U8 * const e = uc + STR_LEN( noper );
1160 U32 state = 1; /* required init */
1162 U16 charid = 0; /* sanity init */
1163 U32 accept_state = 0; /* sanity init */
1164 U8 *scan = (U8*)NULL; /* sanity init */
1166 STRLEN foldlen = 0; /* required init */
1167 U8 foldbuf[ UTF8_MAXBYTES_CASE + 1 ];
1170 for ( ; uc < e ; uc += len ) {
1175 charid = trie->charmap[ uvc ];
1177 SV* const * const svpp = hv_fetch( trie->widecharmap, (char*)&uvc, sizeof( UV ), 0);
1178 charid = svpp ? (U16)SvIV(*svpp) : 0;
1182 if ( !trie->trans[ state + charid ].next ) {
1183 trie->trans[ state + charid ].next = next_alloc;
1184 trie->trans[ state ].check++;
1185 next_alloc += trie->uniquecharcount;
1187 state = trie->trans[ state + charid ].next;
1189 Perl_croak( aTHX_ "panic! In trie construction, no char mapping for %"IVdf, uvc );
1191 /* charid is now 0 if we dont know the char read, or nonzero if we do */
1194 accept_state = TRIE_NODENUM( state );
1195 if ( !trie->states[ accept_state ].wordnum ) {
1196 /* we havent inserted this word into the structure yet. */
1197 trie->states[ accept_state ].wordnum = ++curword;
1200 /* store the word for dumping */
1201 SV* tmp = newSVpvn( STRING( noper ), STR_LEN( noper ) );
1202 if ( UTF ) SvUTF8_on( tmp );
1203 av_push( trie->words, tmp );
1207 NOOP; /* Its a dupe. So ignore it. */
1210 } /* end second pass */
1212 DEBUG_TRIE_COMPILE_MORE_r({
1214 print out the table precompression so that we can do a visual check
1215 that they are identical.
1219 PerlIO_printf( Perl_debug_log, "\nChar : " );
1221 for( charid = 0 ; charid < trie->uniquecharcount ; charid++ ) {
1222 SV **tmp = av_fetch( trie->revcharmap, charid, 0);
1224 PerlIO_printf( Perl_debug_log, "%4.4s ", SvPV_nolen_const( *tmp ) );
1228 PerlIO_printf( Perl_debug_log, "\nState+-" );
1230 for( charid=0 ; charid < trie->uniquecharcount ; charid++ ) {
1231 PerlIO_printf( Perl_debug_log, "%4s-", "----" );
1234 PerlIO_printf( Perl_debug_log, "\n" );
1236 for( state=1 ; state < next_alloc ; state += trie->uniquecharcount ) {
1238 PerlIO_printf( Perl_debug_log, "%04"UVXf" : ", (UV)TRIE_NODENUM( state ) );
1240 for( charid = 0 ; charid < trie->uniquecharcount ; charid++ ) {
1241 PerlIO_printf( Perl_debug_log, "%04"UVXf" ",
1242 (UV)SAFE_TRIE_NODENUM( trie->trans[ state + charid ].next ) );
1244 if ( ! trie->states[ TRIE_NODENUM( state ) ].wordnum ) {
1245 PerlIO_printf( Perl_debug_log, " (%04"UVXf")\n", (UV)trie->trans[ state ].check );
1247 PerlIO_printf( Perl_debug_log, " (%04"UVXf") W%04X\n", (UV)trie->trans[ state ].check,
1248 trie->states[ TRIE_NODENUM( state ) ].wordnum );
1251 PerlIO_printf( Perl_debug_log, "\n\n" );
1255 * Inplace compress the table.*
1257 For sparse data sets the table constructed by the trie algorithm will
1258 be mostly 0/FAIL transitions or to put it another way mostly empty.
1259 (Note that leaf nodes will not contain any transitions.)
1261 This algorithm compresses the tables by eliminating most such
1262 transitions, at the cost of a modest bit of extra work during lookup:
1264 - Each states[] entry contains a .base field which indicates the
1265 index in the state[] array wheres its transition data is stored.
1267 - If .base is 0 there are no valid transitions from that node.
1269 - If .base is nonzero then charid is added to it to find an entry in
1272 -If trans[states[state].base+charid].check!=state then the
1273 transition is taken to be a 0/Fail transition. Thus if there are fail
1274 transitions at the front of the node then the .base offset will point
1275 somewhere inside the previous nodes data (or maybe even into a node
1276 even earlier), but the .check field determines if the transition is
1279 The following process inplace converts the table to the compressed
1280 table: We first do not compress the root node 1,and mark its all its
1281 .check pointers as 1 and set its .base pointer as 1 as well. This
1282 allows to do a DFA construction from the compressed table later, and
1283 ensures that any .base pointers we calculate later are greater than
1286 - We set 'pos' to indicate the first entry of the second node.
1288 - We then iterate over the columns of the node, finding the first and
1289 last used entry at l and m. We then copy l..m into pos..(pos+m-l),
1290 and set the .check pointers accordingly, and advance pos
1291 appropriately and repreat for the next node. Note that when we copy
1292 the next pointers we have to convert them from the original
1293 NODEIDX form to NODENUM form as the former is not valid post
1296 - If a node has no transitions used we mark its base as 0 and do not
1297 advance the pos pointer.
1299 - If a node only has one transition we use a second pointer into the
1300 structure to fill in allocated fail transitions from other states.
1301 This pointer is independent of the main pointer and scans forward
1302 looking for null transitions that are allocated to a state. When it
1303 finds one it writes the single transition into the "hole". If the
1304 pointer doesnt find one the single transition is appeneded as normal.
1306 - Once compressed we can Renew/realloc the structures to release the
1309 See "Table-Compression Methods" in sec 3.9 of the Red Dragon,
1310 specifically Fig 3.47 and the associated pseudocode.
1314 const U32 laststate = TRIE_NODENUM( next_alloc );
1317 trie->laststate = laststate;
1319 for ( state = 1 ; state < laststate ; state++ ) {
1321 const U32 stateidx = TRIE_NODEIDX( state );
1322 const U32 o_used = trie->trans[ stateidx ].check;
1323 U32 used = trie->trans[ stateidx ].check;
1324 trie->trans[ stateidx ].check = 0;
1326 for ( charid = 0 ; used && charid < trie->uniquecharcount ; charid++ ) {
1327 if ( flag || trie->trans[ stateidx + charid ].next ) {
1328 if ( trie->trans[ stateidx + charid ].next ) {
1330 for ( ; zp < pos ; zp++ ) {
1331 if ( ! trie->trans[ zp ].next ) {
1335 trie->states[ state ].trans.base = zp + trie->uniquecharcount - charid ;
1336 trie->trans[ zp ].next = SAFE_TRIE_NODENUM( trie->trans[ stateidx + charid ].next );
1337 trie->trans[ zp ].check = state;
1338 if ( ++zp > pos ) pos = zp;
1345 trie->states[ state ].trans.base = pos + trie->uniquecharcount - charid ;
1347 trie->trans[ pos ].next = SAFE_TRIE_NODENUM( trie->trans[ stateidx + charid ].next );
1348 trie->trans[ pos ].check = state;
1353 trie->lasttrans = pos + 1;
1354 Renew( trie->states, laststate + 1, reg_trie_state);
1355 DEBUG_TRIE_COMPILE_MORE_r(
1356 PerlIO_printf( Perl_debug_log,
1357 " Alloc: %d Orig: %"IVdf" elements, Final:%"IVdf". Savings of %%%5.2f\n",
1358 (int)( ( trie->charcount + 1 ) * trie->uniquecharcount + 1 ),
1361 ( ( next_alloc - pos ) * 100 ) / (double)next_alloc );
1364 } /* end table compress */
1366 /* resize the trans array to remove unused space */
1367 Renew( trie->trans, trie->lasttrans, reg_trie_trans);
1369 DEBUG_TRIE_COMPILE_r({
1372 Now we print it out again, in a slightly different form as there is additional
1373 info we want to be able to see when its compressed. They are close enough for
1374 visual comparison though.
1376 PerlIO_printf( Perl_debug_log, "\nChar : %-6s%-6s%-4s ","Match","Base","Ofs" );
1378 for( state = 0 ; state < trie->uniquecharcount ; state++ ) {
1379 SV **tmp = av_fetch( trie->revcharmap, state, 0);
1381 PerlIO_printf( Perl_debug_log, "%4.4s ", SvPV_nolen_const( *tmp ) );
1384 PerlIO_printf( Perl_debug_log, "\n-----:-----------------------");
1386 for( state = 0 ; state < trie->uniquecharcount ; state++ )
1387 PerlIO_printf( Perl_debug_log, "-----");
1388 PerlIO_printf( Perl_debug_log, "\n");
1390 for( state = 1 ; state < trie->laststate ; state++ ) {
1391 const U32 base = trie->states[ state ].trans.base;
1393 PerlIO_printf( Perl_debug_log, "#%04"UVXf" ", (UV)state);
1395 if ( trie->states[ state ].wordnum ) {
1396 PerlIO_printf( Perl_debug_log, " W%04X", trie->states[ state ].wordnum );
1398 PerlIO_printf( Perl_debug_log, "%6s", "" );
1401 PerlIO_printf( Perl_debug_log, " @%04"UVXf" ", (UV)base );
1406 while( ( base + ofs < trie->uniquecharcount ) ||
1407 ( base + ofs - trie->uniquecharcount < trie->lasttrans
1408 && trie->trans[ base + ofs - trie->uniquecharcount ].check != state))
1411 PerlIO_printf( Perl_debug_log, "+%02"UVXf"[ ", (UV)ofs);
1413 for ( ofs = 0 ; ofs < trie->uniquecharcount ; ofs++ ) {
1414 if ( ( base + ofs >= trie->uniquecharcount ) &&
1415 ( base + ofs - trie->uniquecharcount < trie->lasttrans ) &&
1416 trie->trans[ base + ofs - trie->uniquecharcount ].check == state )
1418 PerlIO_printf( Perl_debug_log, "%04"UVXf" ",
1419 (UV)trie->trans[ base + ofs - trie->uniquecharcount ].next );
1421 PerlIO_printf( Perl_debug_log, "%4s "," 0" );
1425 PerlIO_printf( Perl_debug_log, "]");
1428 PerlIO_printf( Perl_debug_log, "\n" );
1433 /* now finally we "stitch in" the new TRIE node
1434 This means we convert either the first branch or the first Exact,
1435 depending on whether the thing following (in 'last') is a branch
1436 or not and whther first is the startbranch (ie is it a sub part of
1437 the alternation or is it the whole thing.)
1438 Assuming its a sub part we conver the EXACT otherwise we convert
1439 the whole branch sequence, including the first.
1446 if ( first == startbranch && OP( last ) != BRANCH ) {
1449 convert = NEXTOPER( first );
1450 NEXT_OFF( first ) = (U16)(last - first);
1453 OP( convert ) = TRIE + (U8)( flags - EXACT );
1454 NEXT_OFF( convert ) = (U16)(tail - convert);
1455 ARG_SET( convert, data_slot );
1457 /* tells us if we need to handle accept buffers specially */
1458 convert->flags = ( RExC_seen_evals ? 1 : 0 );
1461 /* needed for dumping*/
1463 regnode *optimize = convert + NODE_STEP_REGNODE + regarglen[ TRIE ];
1464 /* We now need to mark all of the space originally used by the
1465 branches as optimized away. This keeps the dumpuntil from
1466 throwing a wobbly as it doesnt use regnext() to traverse the
1469 while( optimize < last ) {
1470 OP( optimize ) = OPTIMIZED;
1474 } /* end node insert */
1481 * There are strange code-generation bugs caused on sparc64 by gcc-2.95.2.
1482 * These need to be revisited when a newer toolchain becomes available.
1484 #if defined(__sparc64__) && defined(__GNUC__)
1485 # if __GNUC__ < 2 || (__GNUC__ == 2 && __GNUC_MINOR__ < 96)
1486 # undef SPARC64_GCC_WORKAROUND
1487 # define SPARC64_GCC_WORKAROUND 1
1491 /* REx optimizer. Converts nodes into quickier variants "in place".
1492 Finds fixed substrings. */
1494 /* Stops at toplevel WHILEM as well as at "last". At end *scanp is set
1495 to the position after last scanned or to NULL. */
1499 S_study_chunk(pTHX_ RExC_state_t *pRExC_state, regnode **scanp, I32 *deltap,
1500 regnode *last, scan_data_t *data, U32 flags, U32 depth)
1501 /* scanp: Start here (read-write). */
1502 /* deltap: Write maxlen-minlen here. */
1503 /* last: Stop before this one. */
1506 I32 min = 0, pars = 0, code;
1507 regnode *scan = *scanp, *next;
1509 int is_inf = (flags & SCF_DO_SUBSTR) && (data->flags & SF_IS_INF);
1510 int is_inf_internal = 0; /* The studied chunk is infinite */
1511 I32 is_par = OP(scan) == OPEN ? ARG(scan) : 0;
1512 scan_data_t data_fake;
1513 struct regnode_charclass_class and_with; /* Valid if flags & SCF_DO_STCLASS_OR */
1514 SV *re_trie_maxbuff = NULL;
1516 GET_RE_DEBUG_FLAGS_DECL;
1518 while (scan && OP(scan) != END && scan < last) {
1519 /* Peephole optimizer: */
1521 SV * const mysv=sv_newmortal();
1522 regprop(RExC_rx, mysv, scan);
1523 PerlIO_printf(Perl_debug_log, "%*speep: %s (0x%08"UVXf")\n",
1524 (int)depth*2, "", SvPV_nolen_const(mysv), PTR2UV(scan));
1527 if (PL_regkind[(U8)OP(scan)] == EXACT) {
1528 /* Merge several consecutive EXACTish nodes into one. */
1529 regnode *n = regnext(scan);
1532 regnode *stop = scan;
1535 next = scan + NODE_SZ_STR(scan);
1536 /* Skip NOTHING, merge EXACT*. */
1538 ( PL_regkind[(U8)OP(n)] == NOTHING ||
1539 (stringok && (OP(n) == OP(scan))))
1541 && NEXT_OFF(scan) + NEXT_OFF(n) < I16_MAX) {
1542 if (OP(n) == TAIL || n > next)
1544 if (PL_regkind[(U8)OP(n)] == NOTHING) {
1545 NEXT_OFF(scan) += NEXT_OFF(n);
1546 next = n + NODE_STEP_REGNODE;
1553 else if (stringok) {
1554 const int oldl = STR_LEN(scan);
1555 regnode * const nnext = regnext(n);
1557 if (oldl + STR_LEN(n) > U8_MAX)
1559 NEXT_OFF(scan) += NEXT_OFF(n);
1560 STR_LEN(scan) += STR_LEN(n);
1561 next = n + NODE_SZ_STR(n);
1562 /* Now we can overwrite *n : */
1563 Move(STRING(n), STRING(scan) + oldl, STR_LEN(n), char);
1571 if (UTF && ( OP(scan) == EXACTF ) && ( STR_LEN(scan) >= 6 ) ) {
1573 Two problematic code points in Unicode casefolding of EXACT nodes:
1575 U+0390 - GREEK SMALL LETTER IOTA WITH DIALYTIKA AND TONOS
1576 U+03B0 - GREEK SMALL LETTER UPSILON WITH DIALYTIKA AND TONOS
1582 U+03B9 U+0308 U+0301 0xCE 0xB9 0xCC 0x88 0xCC 0x81
1583 U+03C5 U+0308 U+0301 0xCF 0x85 0xCC 0x88 0xCC 0x81
1585 This means that in case-insensitive matching (or "loose matching",
1586 as Unicode calls it), an EXACTF of length six (the UTF-8 encoded byte
1587 length of the above casefolded versions) can match a target string
1588 of length two (the byte length of UTF-8 encoded U+0390 or U+03B0).
1589 This would rather mess up the minimum length computation.
1591 What we'll do is to look for the tail four bytes, and then peek
1592 at the preceding two bytes to see whether we need to decrease
1593 the minimum length by four (six minus two).
1595 Thanks to the design of UTF-8, there cannot be false matches:
1596 A sequence of valid UTF-8 bytes cannot be a subsequence of
1597 another valid sequence of UTF-8 bytes.
1600 char * const s0 = STRING(scan), *s, *t;
1601 char * const s1 = s0 + STR_LEN(scan) - 1;
1602 char * const s2 = s1 - 4;
1603 const char t0[] = "\xcc\x88\xcc\x81";
1604 const char * const t1 = t0 + 3;
1607 s < s2 && (t = ninstr(s, s1, t0, t1));
1609 if (((U8)t[-1] == 0xB9 && (U8)t[-2] == 0xCE) ||
1610 ((U8)t[-1] == 0x85 && (U8)t[-2] == 0xCF))
1617 n = scan + NODE_SZ_STR(scan);
1619 if (PL_regkind[(U8)OP(n)] != NOTHING || OP(n) == NOTHING) {
1630 /* Follow the next-chain of the current node and optimize
1631 away all the NOTHINGs from it. */
1632 if (OP(scan) != CURLYX) {
1633 const int max = (reg_off_by_arg[OP(scan)]
1635 /* I32 may be smaller than U16 on CRAYs! */
1636 : (I32_MAX < U16_MAX ? I32_MAX : U16_MAX));
1637 int off = (reg_off_by_arg[OP(scan)] ? ARG(scan) : NEXT_OFF(scan));
1641 /* Skip NOTHING and LONGJMP. */
1642 while ((n = regnext(n))
1643 && ((PL_regkind[(U8)OP(n)] == NOTHING && (noff = NEXT_OFF(n)))
1644 || ((OP(n) == LONGJMP) && (noff = ARG(n))))
1645 && off + noff < max)
1647 if (reg_off_by_arg[OP(scan)])
1650 NEXT_OFF(scan) = off;
1653 /* The principal pseudo-switch. Cannot be a switch, since we
1654 look into several different things. */
1655 if (OP(scan) == BRANCH || OP(scan) == BRANCHJ
1656 || OP(scan) == IFTHEN || OP(scan) == SUSPEND) {
1657 next = regnext(scan);
1659 /* demq: the op(next)==code check is to see if we have "branch-branch" AFAICT */
1661 if (OP(next) == code || code == IFTHEN || code == SUSPEND) {
1662 I32 max1 = 0, min1 = I32_MAX, num = 0;
1663 struct regnode_charclass_class accum;
1664 regnode * const startbranch=scan;
1666 if (flags & SCF_DO_SUBSTR) /* XXXX Add !SUSPEND? */
1667 scan_commit(pRExC_state, data); /* Cannot merge strings after this. */
1668 if (flags & SCF_DO_STCLASS)
1669 cl_init_zero(pRExC_state, &accum);
1671 while (OP(scan) == code) {
1672 I32 deltanext, minnext, f = 0, fake;
1673 struct regnode_charclass_class this_class;
1676 data_fake.flags = 0;
1678 data_fake.whilem_c = data->whilem_c;
1679 data_fake.last_closep = data->last_closep;
1682 data_fake.last_closep = &fake;
1683 next = regnext(scan);
1684 scan = NEXTOPER(scan);
1686 scan = NEXTOPER(scan);
1687 if (flags & SCF_DO_STCLASS) {
1688 cl_init(pRExC_state, &this_class);
1689 data_fake.start_class = &this_class;
1690 f = SCF_DO_STCLASS_AND;
1692 if (flags & SCF_WHILEM_VISITED_POS)
1693 f |= SCF_WHILEM_VISITED_POS;
1695 /* we suppose the run is continuous, last=next...*/
1696 minnext = study_chunk(pRExC_state, &scan, &deltanext,
1697 next, &data_fake, f,depth+1);
1700 if (max1 < minnext + deltanext)
1701 max1 = minnext + deltanext;
1702 if (deltanext == I32_MAX)
1703 is_inf = is_inf_internal = 1;
1705 if (data_fake.flags & (SF_HAS_PAR|SF_IN_PAR))
1707 if (data && (data_fake.flags & SF_HAS_EVAL))
1708 data->flags |= SF_HAS_EVAL;
1710 data->whilem_c = data_fake.whilem_c;
1711 if (flags & SCF_DO_STCLASS)
1712 cl_or(pRExC_state, &accum, &this_class);
1713 if (code == SUSPEND)
1716 if (code == IFTHEN && num < 2) /* Empty ELSE branch */
1718 if (flags & SCF_DO_SUBSTR) {
1719 data->pos_min += min1;
1720 data->pos_delta += max1 - min1;
1721 if (max1 != min1 || is_inf)
1722 data->longest = &(data->longest_float);
1725 delta += max1 - min1;
1726 if (flags & SCF_DO_STCLASS_OR) {
1727 cl_or(pRExC_state, data->start_class, &accum);
1729 cl_and(data->start_class, &and_with);
1730 flags &= ~SCF_DO_STCLASS;
1733 else if (flags & SCF_DO_STCLASS_AND) {
1735 cl_and(data->start_class, &accum);
1736 flags &= ~SCF_DO_STCLASS;
1739 /* Switch to OR mode: cache the old value of
1740 * data->start_class */
1741 StructCopy(data->start_class, &and_with,
1742 struct regnode_charclass_class);
1743 flags &= ~SCF_DO_STCLASS_AND;
1744 StructCopy(&accum, data->start_class,
1745 struct regnode_charclass_class);
1746 flags |= SCF_DO_STCLASS_OR;
1747 data->start_class->flags |= ANYOF_EOS;
1753 Assuming this was/is a branch we are dealing with: 'scan' now
1754 points at the item that follows the branch sequence, whatever
1755 it is. We now start at the beginning of the sequence and look
1761 which would be constructed from a pattern like /A|LIST|OF|WORDS/
1763 If we can find such a subseqence we need to turn the first
1764 element into a trie and then add the subsequent branch exact
1765 strings to the trie.
1769 1. patterns where the whole set of branch can be converted to a trie,
1771 2. patterns where only a subset of the alternations can be
1772 converted to a trie.
1774 In case 1 we can replace the whole set with a single regop
1775 for the trie. In case 2 we need to keep the start and end
1778 'BRANCH EXACT; BRANCH EXACT; BRANCH X'
1779 becomes BRANCH TRIE; BRANCH X;
1781 Hypthetically when we know the regex isnt anchored we can
1782 turn a case 1 into a DFA and let it rip... Every time it finds a match
1783 it would just call its tail, no WHILEM/CURLY needed.
1787 if (!re_trie_maxbuff) {
1788 re_trie_maxbuff = get_sv(RE_TRIE_MAXBUF_NAME, 1);
1789 if (!SvIOK(re_trie_maxbuff))
1790 sv_setiv(re_trie_maxbuff, RE_TRIE_MAXBUF_INIT);
1792 if ( SvIV(re_trie_maxbuff)>=0 && OP( startbranch )==BRANCH ) {
1794 regnode *first = (regnode *)NULL;
1795 regnode *last = (regnode *)NULL;
1796 regnode *tail = scan;
1801 SV * const mysv = sv_newmortal(); /* for dumping */
1803 /* var tail is used because there may be a TAIL
1804 regop in the way. Ie, the exacts will point to the
1805 thing following the TAIL, but the last branch will
1806 point at the TAIL. So we advance tail. If we
1807 have nested (?:) we may have to move through several
1811 while ( OP( tail ) == TAIL ) {
1812 /* this is the TAIL generated by (?:) */
1813 tail = regnext( tail );
1817 regprop(RExC_rx, mysv, tail );
1818 PerlIO_printf( Perl_debug_log, "%*s%s%s%s\n",
1819 (int)depth * 2 + 2, "", "Tail node is:", SvPV_nolen_const( mysv ),
1820 (RExC_seen_evals) ? "[EVAL]" : ""
1825 step through the branches, cur represents each
1826 branch, noper is the first thing to be matched
1827 as part of that branch and noper_next is the
1828 regnext() of that node. if noper is an EXACT
1829 and noper_next is the same as scan (our current
1830 position in the regex) then the EXACT branch is
1831 a possible optimization target. Once we have
1832 two or more consequetive such branches we can
1833 create a trie of the EXACT's contents and stich
1834 it in place. If the sequence represents all of
1835 the branches we eliminate the whole thing and
1836 replace it with a single TRIE. If it is a
1837 subsequence then we need to stitch it in. This
1838 means the first branch has to remain, and needs
1839 to be repointed at the item on the branch chain
1840 following the last branch optimized. This could
1841 be either a BRANCH, in which case the
1842 subsequence is internal, or it could be the
1843 item following the branch sequence in which
1844 case the subsequence is at the end.
1848 /* dont use tail as the end marker for this traverse */
1849 for ( cur = startbranch ; cur != scan ; cur = regnext( cur ) ) {
1850 regnode * const noper = NEXTOPER( cur );
1851 regnode * const noper_next = regnext( noper );
1854 regprop(RExC_rx, mysv, cur);
1855 PerlIO_printf( Perl_debug_log, "%*s%s",
1856 (int)depth * 2 + 2," ", SvPV_nolen_const( mysv ) );
1858 regprop(RExC_rx, mysv, noper);
1859 PerlIO_printf( Perl_debug_log, " -> %s",
1860 SvPV_nolen_const(mysv));
1863 regprop(RExC_rx, mysv, noper_next );
1864 PerlIO_printf( Perl_debug_log,"\t=> %s\t",
1865 SvPV_nolen_const(mysv));
1867 PerlIO_printf( Perl_debug_log, "0x%p,0x%p,0x%p)\n",
1868 (void*)first, (void*)last, (void*)cur );
1870 if ( ( first ? OP( noper ) == optype
1871 : PL_regkind[ (U8)OP( noper ) ] == EXACT )
1872 && noper_next == tail && count<U16_MAX)
1877 optype = OP( noper );
1881 regprop(RExC_rx, mysv, first);
1882 PerlIO_printf( Perl_debug_log, "%*s%s",
1883 (int)depth * 2 + 2, "F:", SvPV_nolen_const( mysv ) );
1884 regprop(RExC_rx, mysv, NEXTOPER(first) );
1885 PerlIO_printf( Perl_debug_log, " -> %s\n",
1886 SvPV_nolen_const( mysv ) );
1891 regprop(RExC_rx, mysv, cur);
1892 PerlIO_printf( Perl_debug_log, "%*s%s",
1893 (int)depth * 2 + 2, "N:", SvPV_nolen_const( mysv ) );
1894 regprop(RExC_rx, mysv, noper );
1895 PerlIO_printf( Perl_debug_log, " -> %s\n",
1896 SvPV_nolen_const( mysv ) );
1902 PerlIO_printf( Perl_debug_log, "%*s%s\n",
1903 (int)depth * 2 + 2, "E:", "**END**" );
1905 make_trie( pRExC_state, startbranch, first, cur, tail, optype );
1907 if ( PL_regkind[ (U8)OP( noper ) ] == EXACT
1908 && noper_next == tail )
1912 optype = OP( noper );
1922 regprop(RExC_rx, mysv, cur);
1923 PerlIO_printf( Perl_debug_log,
1924 "%*s%s\t(0x%p,0x%p,0x%p)\n", (int)depth * 2 + 2,
1925 " ", SvPV_nolen_const( mysv ), (void*)first, (void*)last, (void*)cur);
1930 PerlIO_printf( Perl_debug_log, "%*s%s\n",
1931 (int)depth * 2 + 2, "E:", "==END==" );
1933 make_trie( pRExC_state, startbranch, first, scan, tail, optype );
1938 else if ( code == BRANCHJ ) { /* single branch is optimized. */
1939 scan = NEXTOPER(NEXTOPER(scan));
1940 } else /* single branch is optimized. */
1941 scan = NEXTOPER(scan);
1944 else if (OP(scan) == EXACT) {
1945 I32 l = STR_LEN(scan);
1948 const U8 * const s = (U8*)STRING(scan);
1949 l = utf8_length(s, s + l);
1950 uc = utf8_to_uvchr(s, NULL);
1952 uc = *((U8*)STRING(scan));
1955 if (flags & SCF_DO_SUBSTR) { /* Update longest substr. */
1956 /* The code below prefers earlier match for fixed
1957 offset, later match for variable offset. */
1958 if (data->last_end == -1) { /* Update the start info. */
1959 data->last_start_min = data->pos_min;
1960 data->last_start_max = is_inf
1961 ? I32_MAX : data->pos_min + data->pos_delta;
1963 sv_catpvn(data->last_found, STRING(scan), STR_LEN(scan));
1965 SvUTF8_on(data->last_found);
1967 SV * const sv = data->last_found;
1968 MAGIC * const mg = SvUTF8(sv) && SvMAGICAL(sv) ?
1969 mg_find(sv, PERL_MAGIC_utf8) : NULL;
1970 if (mg && mg->mg_len >= 0)
1971 mg->mg_len += utf8_length((U8*)STRING(scan),
1972 (U8*)STRING(scan)+STR_LEN(scan));
1974 data->last_end = data->pos_min + l;
1975 data->pos_min += l; /* As in the first entry. */
1976 data->flags &= ~SF_BEFORE_EOL;
1978 if (flags & SCF_DO_STCLASS_AND) {
1979 /* Check whether it is compatible with what we know already! */
1983 (!(data->start_class->flags & (ANYOF_CLASS | ANYOF_LOCALE))
1984 && !ANYOF_BITMAP_TEST(data->start_class, uc)
1985 && (!(data->start_class->flags & ANYOF_FOLD)
1986 || !ANYOF_BITMAP_TEST(data->start_class, PL_fold[uc])))
1989 ANYOF_CLASS_ZERO(data->start_class);
1990 ANYOF_BITMAP_ZERO(data->start_class);
1992 ANYOF_BITMAP_SET(data->start_class, uc);
1993 data->start_class->flags &= ~ANYOF_EOS;
1995 data->start_class->flags &= ~ANYOF_UNICODE_ALL;
1997 else if (flags & SCF_DO_STCLASS_OR) {
1998 /* false positive possible if the class is case-folded */
2000 ANYOF_BITMAP_SET(data->start_class, uc);
2002 data->start_class->flags |= ANYOF_UNICODE_ALL;
2003 data->start_class->flags &= ~ANYOF_EOS;
2004 cl_and(data->start_class, &and_with);
2006 flags &= ~SCF_DO_STCLASS;
2008 else if (PL_regkind[(U8)OP(scan)] == EXACT) { /* But OP != EXACT! */
2009 I32 l = STR_LEN(scan);
2010 UV uc = *((U8*)STRING(scan));
2012 /* Search for fixed substrings supports EXACT only. */
2013 if (flags & SCF_DO_SUBSTR) {
2015 scan_commit(pRExC_state, data);
2018 const U8 * const s = (U8 *)STRING(scan);
2019 l = utf8_length(s, s + l);
2020 uc = utf8_to_uvchr(s, NULL);
2023 if (flags & SCF_DO_SUBSTR)
2025 if (flags & SCF_DO_STCLASS_AND) {
2026 /* Check whether it is compatible with what we know already! */
2030 (!(data->start_class->flags & (ANYOF_CLASS | ANYOF_LOCALE))
2031 && !ANYOF_BITMAP_TEST(data->start_class, uc)
2032 && !ANYOF_BITMAP_TEST(data->start_class, PL_fold[uc])))
2034 ANYOF_CLASS_ZERO(data->start_class);
2035 ANYOF_BITMAP_ZERO(data->start_class);
2037 ANYOF_BITMAP_SET(data->start_class, uc);
2038 data->start_class->flags &= ~ANYOF_EOS;
2039 data->start_class->flags |= ANYOF_FOLD;
2040 if (OP(scan) == EXACTFL)
2041 data->start_class->flags |= ANYOF_LOCALE;
2044 else if (flags & SCF_DO_STCLASS_OR) {
2045 if (data->start_class->flags & ANYOF_FOLD) {
2046 /* false positive possible if the class is case-folded.
2047 Assume that the locale settings are the same... */
2049 ANYOF_BITMAP_SET(data->start_class, uc);
2050 data->start_class->flags &= ~ANYOF_EOS;
2052 cl_and(data->start_class, &and_with);
2054 flags &= ~SCF_DO_STCLASS;
2056 else if (strchr((const char*)PL_varies,OP(scan))) {
2057 I32 mincount, maxcount, minnext, deltanext, fl = 0;
2058 I32 f = flags, pos_before = 0;
2059 regnode * const oscan = scan;
2060 struct regnode_charclass_class this_class;
2061 struct regnode_charclass_class *oclass = NULL;
2062 I32 next_is_eval = 0;
2064 switch (PL_regkind[(U8)OP(scan)]) {
2065 case WHILEM: /* End of (?:...)* . */
2066 scan = NEXTOPER(scan);
2069 if (flags & (SCF_DO_SUBSTR | SCF_DO_STCLASS)) {
2070 next = NEXTOPER(scan);
2071 if (OP(next) == EXACT || (flags & SCF_DO_STCLASS)) {
2073 maxcount = REG_INFTY;
2074 next = regnext(scan);
2075 scan = NEXTOPER(scan);
2079 if (flags & SCF_DO_SUBSTR)
2084 if (flags & SCF_DO_STCLASS) {
2086 maxcount = REG_INFTY;
2087 next = regnext(scan);
2088 scan = NEXTOPER(scan);
2091 is_inf = is_inf_internal = 1;
2092 scan = regnext(scan);
2093 if (flags & SCF_DO_SUBSTR) {
2094 scan_commit(pRExC_state, data); /* Cannot extend fixed substrings */
2095 data->longest = &(data->longest_float);
2097 goto optimize_curly_tail;
2099 mincount = ARG1(scan);
2100 maxcount = ARG2(scan);
2101 next = regnext(scan);
2102 if (OP(scan) == CURLYX) {
2103 I32 lp = (data ? *(data->last_closep) : 0);
2104 scan->flags = ((lp <= U8_MAX) ? (U8)lp : U8_MAX);
2106 scan = NEXTOPER(scan) + EXTRA_STEP_2ARGS;
2107 next_is_eval = (OP(scan) == EVAL);
2109 if (flags & SCF_DO_SUBSTR) {
2110 if (mincount == 0) scan_commit(pRExC_state,data); /* Cannot extend fixed substrings */
2111 pos_before = data->pos_min;
2115 data->flags &= ~(SF_HAS_PAR|SF_IN_PAR|SF_HAS_EVAL);
2117 data->flags |= SF_IS_INF;
2119 if (flags & SCF_DO_STCLASS) {
2120 cl_init(pRExC_state, &this_class);
2121 oclass = data->start_class;
2122 data->start_class = &this_class;
2123 f |= SCF_DO_STCLASS_AND;
2124 f &= ~SCF_DO_STCLASS_OR;
2126 /* These are the cases when once a subexpression
2127 fails at a particular position, it cannot succeed
2128 even after backtracking at the enclosing scope.
2130 XXXX what if minimal match and we are at the
2131 initial run of {n,m}? */
2132 if ((mincount != maxcount - 1) && (maxcount != REG_INFTY))
2133 f &= ~SCF_WHILEM_VISITED_POS;
2135 /* This will finish on WHILEM, setting scan, or on NULL: */
2136 minnext = study_chunk(pRExC_state, &scan, &deltanext, last, data,
2138 ? (f & ~SCF_DO_SUBSTR) : f),depth+1);
2140 if (flags & SCF_DO_STCLASS)
2141 data->start_class = oclass;
2142 if (mincount == 0 || minnext == 0) {
2143 if (flags & SCF_DO_STCLASS_OR) {
2144 cl_or(pRExC_state, data->start_class, &this_class);
2146 else if (flags & SCF_DO_STCLASS_AND) {
2147 /* Switch to OR mode: cache the old value of
2148 * data->start_class */
2149 StructCopy(data->start_class, &and_with,
2150 struct regnode_charclass_class);
2151 flags &= ~SCF_DO_STCLASS_AND;
2152 StructCopy(&this_class, data->start_class,
2153 struct regnode_charclass_class);
2154 flags |= SCF_DO_STCLASS_OR;
2155 data->start_class->flags |= ANYOF_EOS;
2157 } else { /* Non-zero len */
2158 if (flags & SCF_DO_STCLASS_OR) {
2159 cl_or(pRExC_state, data->start_class, &this_class);
2160 cl_and(data->start_class, &and_with);
2162 else if (flags & SCF_DO_STCLASS_AND)
2163 cl_and(data->start_class, &this_class);
2164 flags &= ~SCF_DO_STCLASS;
2166 if (!scan) /* It was not CURLYX, but CURLY. */
2168 if ( /* ? quantifier ok, except for (?{ ... }) */
2169 (next_is_eval || !(mincount == 0 && maxcount == 1))
2170 && (minnext == 0) && (deltanext == 0)
2171 && data && !(data->flags & (SF_HAS_PAR|SF_IN_PAR))
2172 && maxcount <= REG_INFTY/3 /* Complement check for big count */
2173 && ckWARN(WARN_REGEXP))
2176 "Quantifier unexpected on zero-length expression");
2179 min += minnext * mincount;
2180 is_inf_internal |= ((maxcount == REG_INFTY
2181 && (minnext + deltanext) > 0)
2182 || deltanext == I32_MAX);
2183 is_inf |= is_inf_internal;
2184 delta += (minnext + deltanext) * maxcount - minnext * mincount;
2186 /* Try powerful optimization CURLYX => CURLYN. */
2187 if ( OP(oscan) == CURLYX && data
2188 && data->flags & SF_IN_PAR
2189 && !(data->flags & SF_HAS_EVAL)
2190 && !deltanext && minnext == 1 ) {
2191 /* Try to optimize to CURLYN. */
2192 regnode *nxt = NEXTOPER(oscan) + EXTRA_STEP_2ARGS;
2193 regnode * const nxt1 = nxt;
2200 if (!strchr((const char*)PL_simple,OP(nxt))
2201 && !(PL_regkind[(U8)OP(nxt)] == EXACT
2202 && STR_LEN(nxt) == 1))
2208 if (OP(nxt) != CLOSE)
2210 /* Now we know that nxt2 is the only contents: */
2211 oscan->flags = (U8)ARG(nxt);
2213 OP(nxt1) = NOTHING; /* was OPEN. */
2215 OP(nxt1 + 1) = OPTIMIZED; /* was count. */
2216 NEXT_OFF(nxt1+ 1) = 0; /* just for consistancy. */
2217 NEXT_OFF(nxt2) = 0; /* just for consistancy with CURLY. */
2218 OP(nxt) = OPTIMIZED; /* was CLOSE. */
2219 OP(nxt + 1) = OPTIMIZED; /* was count. */
2220 NEXT_OFF(nxt+ 1) = 0; /* just for consistancy. */
2225 /* Try optimization CURLYX => CURLYM. */
2226 if ( OP(oscan) == CURLYX && data
2227 && !(data->flags & SF_HAS_PAR)
2228 && !(data->flags & SF_HAS_EVAL)
2229 && !deltanext /* atom is fixed width */
2230 && minnext != 0 /* CURLYM can't handle zero width */
2232 /* XXXX How to optimize if data == 0? */
2233 /* Optimize to a simpler form. */
2234 regnode *nxt = NEXTOPER(oscan) + EXTRA_STEP_2ARGS; /* OPEN */
2238 while ( (nxt2 = regnext(nxt)) /* skip over embedded stuff*/
2239 && (OP(nxt2) != WHILEM))
2241 OP(nxt2) = SUCCEED; /* Whas WHILEM */
2242 /* Need to optimize away parenths. */
2243 if (data->flags & SF_IN_PAR) {
2244 /* Set the parenth number. */
2245 regnode *nxt1 = NEXTOPER(oscan) + EXTRA_STEP_2ARGS; /* OPEN*/
2247 if (OP(nxt) != CLOSE)
2248 FAIL("Panic opt close");
2249 oscan->flags = (U8)ARG(nxt);
2250 OP(nxt1) = OPTIMIZED; /* was OPEN. */
2251 OP(nxt) = OPTIMIZED; /* was CLOSE. */
2253 OP(nxt1 + 1) = OPTIMIZED; /* was count. */
2254 OP(nxt + 1) = OPTIMIZED; /* was count. */
2255 NEXT_OFF(nxt1 + 1) = 0; /* just for consistancy. */
2256 NEXT_OFF(nxt + 1) = 0; /* just for consistancy. */
2259 while ( nxt1 && (OP(nxt1) != WHILEM)) {
2260 regnode *nnxt = regnext(nxt1);
2263 if (reg_off_by_arg[OP(nxt1)])
2264 ARG_SET(nxt1, nxt2 - nxt1);
2265 else if (nxt2 - nxt1 < U16_MAX)
2266 NEXT_OFF(nxt1) = nxt2 - nxt1;
2268 OP(nxt) = NOTHING; /* Cannot beautify */
2273 /* Optimize again: */
2274 study_chunk(pRExC_state, &nxt1, &deltanext, nxt,
2280 else if ((OP(oscan) == CURLYX)
2281 && (flags & SCF_WHILEM_VISITED_POS)
2282 /* See the comment on a similar expression above.
2283 However, this time it not a subexpression
2284 we care about, but the expression itself. */
2285 && (maxcount == REG_INFTY)
2286 && data && ++data->whilem_c < 16) {
2287 /* This stays as CURLYX, we can put the count/of pair. */
2288 /* Find WHILEM (as in regexec.c) */
2289 regnode *nxt = oscan + NEXT_OFF(oscan);
2291 if (OP(PREVOPER(nxt)) == NOTHING) /* LONGJMP */
2293 PREVOPER(nxt)->flags = (U8)(data->whilem_c
2294 | (RExC_whilem_seen << 4)); /* On WHILEM */
2296 if (data && fl & (SF_HAS_PAR|SF_IN_PAR))
2298 if (flags & SCF_DO_SUBSTR) {
2299 SV *last_str = NULL;
2300 int counted = mincount != 0;
2302 if (data->last_end > 0 && mincount != 0) { /* Ends with a string. */
2303 #if defined(SPARC64_GCC_WORKAROUND)
2306 const char *s = NULL;
2309 if (pos_before >= data->last_start_min)
2312 b = data->last_start_min;
2315 s = SvPV_const(data->last_found, l);
2316 old = b - data->last_start_min;
2319 I32 b = pos_before >= data->last_start_min
2320 ? pos_before : data->last_start_min;
2322 const char * const s = SvPV_const(data->last_found, l);
2323 I32 old = b - data->last_start_min;
2327 old = utf8_hop((U8*)s, old) - (U8*)s;
2330 /* Get the added string: */
2331 last_str = newSVpvn(s + old, l);
2333 SvUTF8_on(last_str);
2334 if (deltanext == 0 && pos_before == b) {
2335 /* What was added is a constant string */
2337 SvGROW(last_str, (mincount * l) + 1);
2338 repeatcpy(SvPVX(last_str) + l,
2339 SvPVX_const(last_str), l, mincount - 1);
2340 SvCUR_set(last_str, SvCUR(last_str) * mincount);
2341 /* Add additional parts. */
2342 SvCUR_set(data->last_found,
2343 SvCUR(data->last_found) - l);
2344 sv_catsv(data->last_found, last_str);
2346 SV * sv = data->last_found;
2348 SvUTF8(sv) && SvMAGICAL(sv) ?
2349 mg_find(sv, PERL_MAGIC_utf8) : NULL;
2350 if (mg && mg->mg_len >= 0)
2351 mg->mg_len += CHR_SVLEN(last_str);
2353 data->last_end += l * (mincount - 1);
2356 /* start offset must point into the last copy */
2357 data->last_start_min += minnext * (mincount - 1);
2358 data->last_start_max += is_inf ? I32_MAX
2359 : (maxcount - 1) * (minnext + data->pos_delta);
2362 /* It is counted once already... */
2363 data->pos_min += minnext * (mincount - counted);
2364 data->pos_delta += - counted * deltanext +
2365 (minnext + deltanext) * maxcount - minnext * mincount;
2366 if (mincount != maxcount) {
2367 /* Cannot extend fixed substrings found inside
2369 scan_commit(pRExC_state,data);
2370 if (mincount && last_str) {
2371 SV * const sv = data->last_found;
2372 MAGIC * const mg = SvUTF8(sv) && SvMAGICAL(sv) ?
2373 mg_find(sv, PERL_MAGIC_utf8) : NULL;
2377 sv_setsv(sv, last_str);
2378 data->last_end = data->pos_min;
2379 data->last_start_min =
2380 data->pos_min - CHR_SVLEN(last_str);
2381 data->last_start_max = is_inf
2383 : data->pos_min + data->pos_delta
2384 - CHR_SVLEN(last_str);
2386 data->longest = &(data->longest_float);
2388 SvREFCNT_dec(last_str);
2390 if (data && (fl & SF_HAS_EVAL))
2391 data->flags |= SF_HAS_EVAL;
2392 optimize_curly_tail:
2393 if (OP(oscan) != CURLYX) {
2394 while (PL_regkind[(U8)OP(next = regnext(oscan))] == NOTHING
2396 NEXT_OFF(oscan) += NEXT_OFF(next);
2399 default: /* REF and CLUMP only? */
2400 if (flags & SCF_DO_SUBSTR) {
2401 scan_commit(pRExC_state,data); /* Cannot expect anything... */
2402 data->longest = &(data->longest_float);
2404 is_inf = is_inf_internal = 1;
2405 if (flags & SCF_DO_STCLASS_OR)
2406 cl_anything(pRExC_state, data->start_class);
2407 flags &= ~SCF_DO_STCLASS;
2411 else if (strchr((const char*)PL_simple,OP(scan))) {
2414 if (flags & SCF_DO_SUBSTR) {
2415 scan_commit(pRExC_state,data);
2419 if (flags & SCF_DO_STCLASS) {
2420 data->start_class->flags &= ~ANYOF_EOS; /* No match on empty */
2422 /* Some of the logic below assumes that switching
2423 locale on will only add false positives. */
2424 switch (PL_regkind[(U8)OP(scan)]) {
2428 /* Perl_croak(aTHX_ "panic: unexpected simple REx opcode %d", OP(scan)); */
2429 if (flags & SCF_DO_STCLASS_OR) /* Allow everything */
2430 cl_anything(pRExC_state, data->start_class);
2433 if (OP(scan) == SANY)
2435 if (flags & SCF_DO_STCLASS_OR) { /* Everything but \n */
2436 value = (ANYOF_BITMAP_TEST(data->start_class,'\n')
2437 || (data->start_class->flags & ANYOF_CLASS));
2438 cl_anything(pRExC_state, data->start_class);
2440 if (flags & SCF_DO_STCLASS_AND || !value)
2441 ANYOF_BITMAP_CLEAR(data->start_class,'\n');
2444 if (flags & SCF_DO_STCLASS_AND)
2445 cl_and(data->start_class,
2446 (struct regnode_charclass_class*)scan);
2448 cl_or(pRExC_state, data->start_class,
2449 (struct regnode_charclass_class*)scan);
2452 if (flags & SCF_DO_STCLASS_AND) {
2453 if (!(data->start_class->flags & ANYOF_LOCALE)) {
2454 ANYOF_CLASS_CLEAR(data->start_class,ANYOF_NALNUM);
2455 for (value = 0; value < 256; value++)
2456 if (!isALNUM(value))
2457 ANYOF_BITMAP_CLEAR(data->start_class, value);
2461 if (data->start_class->flags & ANYOF_LOCALE)
2462 ANYOF_CLASS_SET(data->start_class,ANYOF_ALNUM);
2464 for (value = 0; value < 256; value++)
2466 ANYOF_BITMAP_SET(data->start_class, value);
2471 if (flags & SCF_DO_STCLASS_AND) {
2472 if (data->start_class->flags & ANYOF_LOCALE)
2473 ANYOF_CLASS_CLEAR(data->start_class,ANYOF_NALNUM);
2476 ANYOF_CLASS_SET(data->start_class,ANYOF_ALNUM);
2477 data->start_class->flags |= ANYOF_LOCALE;
2481 if (flags & SCF_DO_STCLASS_AND) {
2482 if (!(data->start_class->flags & ANYOF_LOCALE)) {
2483 ANYOF_CLASS_CLEAR(data->start_class,ANYOF_ALNUM);
2484 for (value = 0; value < 256; value++)
2486 ANYOF_BITMAP_CLEAR(data->start_class, value);
2490 if (data->start_class->flags & ANYOF_LOCALE)
2491 ANYOF_CLASS_SET(data->start_class,ANYOF_NALNUM);
2493 for (value = 0; value < 256; value++)
2494 if (!isALNUM(value))
2495 ANYOF_BITMAP_SET(data->start_class, value);
2500 if (flags & SCF_DO_STCLASS_AND) {
2501 if (data->start_class->flags & ANYOF_LOCALE)
2502 ANYOF_CLASS_CLEAR(data->start_class,ANYOF_ALNUM);
2505 data->start_class->flags |= ANYOF_LOCALE;
2506 ANYOF_CLASS_SET(data->start_class,ANYOF_NALNUM);
2510 if (flags & SCF_DO_STCLASS_AND) {
2511 if (!(data->start_class->flags & ANYOF_LOCALE)) {
2512 ANYOF_CLASS_CLEAR(data->start_class,ANYOF_NSPACE);
2513 for (value = 0; value < 256; value++)
2514 if (!isSPACE(value))
2515 ANYOF_BITMAP_CLEAR(data->start_class, value);
2519 if (data->start_class->flags & ANYOF_LOCALE)
2520 ANYOF_CLASS_SET(data->start_class,ANYOF_SPACE);
2522 for (value = 0; value < 256; value++)
2524 ANYOF_BITMAP_SET(data->start_class, value);
2529 if (flags & SCF_DO_STCLASS_AND) {
2530 if (data->start_class->flags & ANYOF_LOCALE)
2531 ANYOF_CLASS_CLEAR(data->start_class,ANYOF_NSPACE);
2534 data->start_class->flags |= ANYOF_LOCALE;
2535 ANYOF_CLASS_SET(data->start_class,ANYOF_SPACE);
2539 if (flags & SCF_DO_STCLASS_AND) {
2540 if (!(data->start_class->flags & ANYOF_LOCALE)) {
2541 ANYOF_CLASS_CLEAR(data->start_class,ANYOF_SPACE);
2542 for (value = 0; value < 256; value++)
2544 ANYOF_BITMAP_CLEAR(data->start_class, value);
2548 if (data->start_class->flags & ANYOF_LOCALE)
2549 ANYOF_CLASS_SET(data->start_class,ANYOF_NSPACE);
2551 for (value = 0; value < 256; value++)
2552 if (!isSPACE(value))
2553 ANYOF_BITMAP_SET(data->start_class, value);
2558 if (flags & SCF_DO_STCLASS_AND) {
2559 if (data->start_class->flags & ANYOF_LOCALE) {
2560 ANYOF_CLASS_CLEAR(data->start_class,ANYOF_SPACE);
2561 for (value = 0; value < 256; value++)
2562 if (!isSPACE(value))
2563 ANYOF_BITMAP_CLEAR(data->start_class, value);
2567 data->start_class->flags |= ANYOF_LOCALE;
2568 ANYOF_CLASS_SET(data->start_class,ANYOF_NSPACE);
2572 if (flags & SCF_DO_STCLASS_AND) {
2573 ANYOF_CLASS_CLEAR(data->start_class,ANYOF_NDIGIT);
2574 for (value = 0; value < 256; value++)
2575 if (!isDIGIT(value))
2576 ANYOF_BITMAP_CLEAR(data->start_class, value);
2579 if (data->start_class->flags & ANYOF_LOCALE)
2580 ANYOF_CLASS_SET(data->start_class,ANYOF_DIGIT);
2582 for (value = 0; value < 256; value++)
2584 ANYOF_BITMAP_SET(data->start_class, value);
2589 if (flags & SCF_DO_STCLASS_AND) {
2590 ANYOF_CLASS_CLEAR(data->start_class,ANYOF_DIGIT);
2591 for (value = 0; value < 256; value++)
2593 ANYOF_BITMAP_CLEAR(data->start_class, value);
2596 if (data->start_class->flags & ANYOF_LOCALE)
2597 ANYOF_CLASS_SET(data->start_class,ANYOF_NDIGIT);
2599 for (value = 0; value < 256; value++)
2600 if (!isDIGIT(value))
2601 ANYOF_BITMAP_SET(data->start_class, value);
2606 if (flags & SCF_DO_STCLASS_OR)
2607 cl_and(data->start_class, &and_with);
2608 flags &= ~SCF_DO_STCLASS;
2611 else if (PL_regkind[(U8)OP(scan)] == EOL && flags & SCF_DO_SUBSTR) {
2612 data->flags |= (OP(scan) == MEOL
2616 else if ( PL_regkind[(U8)OP(scan)] == BRANCHJ
2617 /* Lookbehind, or need to calculate parens/evals/stclass: */
2618 && (scan->flags || data || (flags & SCF_DO_STCLASS))
2619 && (OP(scan) == IFMATCH || OP(scan) == UNLESSM)) {
2620 /* Lookahead/lookbehind */
2621 I32 deltanext, minnext, fake = 0;
2623 struct regnode_charclass_class intrnl;
2626 data_fake.flags = 0;
2628 data_fake.whilem_c = data->whilem_c;
2629 data_fake.last_closep = data->last_closep;
2632 data_fake.last_closep = &fake;
2633 if ( flags & SCF_DO_STCLASS && !scan->flags
2634 && OP(scan) == IFMATCH ) { /* Lookahead */
2635 cl_init(pRExC_state, &intrnl);
2636 data_fake.start_class = &intrnl;
2637 f |= SCF_DO_STCLASS_AND;
2639 if (flags & SCF_WHILEM_VISITED_POS)
2640 f |= SCF_WHILEM_VISITED_POS;
2641 next = regnext(scan);
2642 nscan = NEXTOPER(NEXTOPER(scan));
2643 minnext = study_chunk(pRExC_state, &nscan, &deltanext, last, &data_fake, f,depth+1);
2646 vFAIL("Variable length lookbehind not implemented");
2648 else if (minnext > U8_MAX) {
2649 vFAIL2("Lookbehind longer than %"UVuf" not implemented", (UV)U8_MAX);
2651 scan->flags = (U8)minnext;
2653 if (data && data_fake.flags & (SF_HAS_PAR|SF_IN_PAR))
2655 if (data && (data_fake.flags & SF_HAS_EVAL))
2656 data->flags |= SF_HAS_EVAL;
2658 data->whilem_c = data_fake.whilem_c;
2659 if (f & SCF_DO_STCLASS_AND) {
2660 const int was = (data->start_class->flags & ANYOF_EOS);
2662 cl_and(data->start_class, &intrnl);
2664 data->start_class->flags |= ANYOF_EOS;
2667 else if (OP(scan) == OPEN) {
2670 else if (OP(scan) == CLOSE) {
2671 if ((I32)ARG(scan) == is_par) {
2672 next = regnext(scan);
2674 if ( next && (OP(next) != WHILEM) && next < last)
2675 is_par = 0; /* Disable optimization */
2678 *(data->last_closep) = ARG(scan);
2680 else if (OP(scan) == EVAL) {
2682 data->flags |= SF_HAS_EVAL;
2684 else if (OP(scan) == LOGICAL && scan->flags == 2) { /* Embedded follows */
2685 if (flags & SCF_DO_SUBSTR) {
2686 scan_commit(pRExC_state,data);
2687 data->longest = &(data->longest_float);
2689 is_inf = is_inf_internal = 1;
2690 if (flags & SCF_DO_STCLASS_OR) /* Allow everything */
2691 cl_anything(pRExC_state, data->start_class);
2692 flags &= ~SCF_DO_STCLASS;
2694 /* Else: zero-length, ignore. */
2695 scan = regnext(scan);
2700 *deltap = is_inf_internal ? I32_MAX : delta;
2701 if (flags & SCF_DO_SUBSTR && is_inf)
2702 data->pos_delta = I32_MAX - data->pos_min;
2703 if (is_par > U8_MAX)
2705 if (is_par && pars==1 && data) {
2706 data->flags |= SF_IN_PAR;
2707 data->flags &= ~SF_HAS_PAR;
2709 else if (pars && data) {
2710 data->flags |= SF_HAS_PAR;
2711 data->flags &= ~SF_IN_PAR;
2713 if (flags & SCF_DO_STCLASS_OR)
2714 cl_and(data->start_class, &and_with);
2719 S_add_data(RExC_state_t *pRExC_state, I32 n, const char *s)
2721 if (RExC_rx->data) {
2722 Renewc(RExC_rx->data,
2723 sizeof(*RExC_rx->data) + sizeof(void*) * (RExC_rx->data->count + n - 1),
2724 char, struct reg_data);
2725 Renew(RExC_rx->data->what, RExC_rx->data->count + n, U8);
2726 RExC_rx->data->count += n;
2729 Newxc(RExC_rx->data, sizeof(*RExC_rx->data) + sizeof(void*) * (n - 1),
2730 char, struct reg_data);
2731 Newx(RExC_rx->data->what, n, U8);
2732 RExC_rx->data->count = n;
2734 Copy(s, RExC_rx->data->what + RExC_rx->data->count - n, n, U8);
2735 return RExC_rx->data->count - n;
2738 #ifndef PERL_IN_XSUB_RE
2740 Perl_reginitcolors(pTHX)
2743 const char * const s = PerlEnv_getenv("PERL_RE_COLORS");
2745 char *t = savepv(s);
2749 t = strchr(t, '\t');
2755 PL_colors[i] = t = (char *)"";
2760 PL_colors[i++] = (char *)"";
2767 - pregcomp - compile a regular expression into internal code
2769 * We can't allocate space until we know how big the compiled form will be,
2770 * but we can't compile it (and thus know how big it is) until we've got a
2771 * place to put the code. So we cheat: we compile it twice, once with code
2772 * generation turned off and size counting turned on, and once "for real".
2773 * This also means that we don't allocate space until we are sure that the
2774 * thing really will compile successfully, and we never have to move the
2775 * code and thus invalidate pointers into it. (Note that it has to be in
2776 * one piece because free() must be able to free it all.) [NB: not true in perl]
2778 * Beware that the optimization-preparation code in here knows about some
2779 * of the structure of the compiled regexp. [I'll say.]
2782 Perl_pregcomp(pTHX_ char *exp, char *xend, PMOP *pm)
2793 RExC_state_t RExC_state;
2794 RExC_state_t *pRExC_state = &RExC_state;
2796 GET_RE_DEBUG_FLAGS_DECL;
2799 FAIL("NULL regexp argument");
2801 RExC_utf8 = pm->op_pmdynflags & PMdf_CMP_UTF8;
2804 DEBUG_r(if (!PL_colorset) reginitcolors());
2806 PerlIO_printf(Perl_debug_log, "%sCompiling REx%s \"%s%*s%s\"\n",
2807 PL_colors[4],PL_colors[5],PL_colors[0],
2808 (int)(xend - exp), RExC_precomp, PL_colors[1]);
2810 RExC_flags = pm->op_pmflags;
2814 RExC_seen_zerolen = *exp == '^' ? -1 : 0;
2815 RExC_seen_evals = 0;
2818 /* First pass: determine size, legality. */
2825 RExC_emit = &PL_regdummy;
2826 RExC_whilem_seen = 0;
2827 #if 0 /* REGC() is (currently) a NOP at the first pass.
2828 * Clever compilers notice this and complain. --jhi */
2829 REGC((U8)REG_MAGIC, (char*)RExC_emit);
2831 if (reg(pRExC_state, 0, &flags) == NULL) {
2832 RExC_precomp = NULL;
2835 DEBUG_COMPILE_r(PerlIO_printf(Perl_debug_log, "size %"IVdf" ", (IV)RExC_size));
2837 /* Small enough for pointer-storage convention?
2838 If extralen==0, this means that we will not need long jumps. */
2839 if (RExC_size >= 0x10000L && RExC_extralen)
2840 RExC_size += RExC_extralen;
2843 if (RExC_whilem_seen > 15)
2844 RExC_whilem_seen = 15;
2846 /* Allocate space and initialize. */
2847 Newxc(r, sizeof(regexp) + (unsigned)RExC_size * sizeof(regnode),
2850 FAIL("Regexp out of space");
2853 /* avoid reading uninitialized memory in DEBUGGING code in study_chunk() */
2854 Zero(r, sizeof(regexp) + (unsigned)RExC_size * sizeof(regnode), char);
2857 r->prelen = xend - exp;
2858 r->precomp = savepvn(RExC_precomp, r->prelen);
2860 #ifdef PERL_OLD_COPY_ON_WRITE
2861 r->saved_copy = NULL;
2863 r->reganch = pm->op_pmflags & PMf_COMPILETIME;
2864 r->nparens = RExC_npar - 1; /* set early to validate backrefs */
2865 r->lastparen = 0; /* mg.c reads this. */
2867 r->substrs = 0; /* Useful during FAIL. */
2868 r->startp = 0; /* Useful during FAIL. */
2869 r->endp = 0; /* Useful during FAIL. */
2871 Newxz(r->offsets, 2*RExC_size+1, U32); /* MJD 20001228 */
2873 r->offsets[0] = RExC_size;
2875 DEBUG_OFFSETS_r(PerlIO_printf(Perl_debug_log,
2876 "%s %"UVuf" bytes for offset annotations.\n",
2877 r->offsets ? "Got" : "Couldn't get",
2878 (UV)((2*RExC_size+1) * sizeof(U32))));
2882 /* Second pass: emit code. */
2883 RExC_flags = pm->op_pmflags; /* don't let top level (?i) bleed */
2888 RExC_emit_start = r->program;
2889 RExC_emit = r->program;
2890 /* Store the count of eval-groups for security checks: */
2891 RExC_emit->next_off = (U16)((RExC_seen_evals > U16_MAX) ? U16_MAX : RExC_seen_evals);
2892 REGC((U8)REG_MAGIC, (char*) RExC_emit++);
2894 if (reg(pRExC_state, 0, &flags) == NULL)
2898 /* Dig out information for optimizations. */
2899 r->reganch = pm->op_pmflags & PMf_COMPILETIME; /* Again? */
2900 pm->op_pmflags = RExC_flags;
2902 r->reganch |= ROPT_UTF8; /* Unicode in it? */
2903 r->regstclass = NULL;
2904 if (RExC_naughty >= 10) /* Probably an expensive pattern. */
2905 r->reganch |= ROPT_NAUGHTY;
2906 scan = r->program + 1; /* First BRANCH. */
2908 /* XXXX To minimize changes to RE engine we always allocate
2909 3-units-long substrs field. */
2910 Newxz(r->substrs, 1, struct reg_substr_data);
2912 StructCopy(&zero_scan_data, &data, scan_data_t);
2913 /* XXXX Should not we check for something else? Usually it is OPEN1... */
2914 if (OP(scan) != BRANCH) { /* Only one top-level choice. */
2916 STRLEN longest_float_length, longest_fixed_length;
2917 struct regnode_charclass_class ch_class;
2922 /* Skip introductions and multiplicators >= 1. */
2923 while ((OP(first) == OPEN && (sawopen = 1)) ||
2924 /* An OR of *one* alternative - should not happen now. */
2925 (OP(first) == BRANCH && OP(regnext(first)) != BRANCH) ||
2926 (OP(first) == PLUS) ||
2927 (OP(first) == MINMOD) ||
2928 /* An {n,m} with n>0 */
2929 (PL_regkind[(U8)OP(first)] == CURLY && ARG1(first) > 0) ) {
2930 if (OP(first) == PLUS)
2933 first += regarglen[(U8)OP(first)];
2934 first = NEXTOPER(first);
2937 /* Starting-point info. */
2939 if (PL_regkind[(U8)OP(first)] == EXACT) {
2940 if (OP(first) == EXACT)
2941 NOOP; /* Empty, get anchored substr later. */
2942 else if ((OP(first) == EXACTF || OP(first) == EXACTFL))
2943 r->regstclass = first;
2945 else if (strchr((const char*)PL_simple,OP(first)))
2946 r->regstclass = first;
2947 else if (PL_regkind[(U8)OP(first)] == BOUND ||
2948 PL_regkind[(U8)OP(first)] == NBOUND)
2949 r->regstclass = first;
2950 else if (PL_regkind[(U8)OP(first)] == BOL) {
2951 r->reganch |= (OP(first) == MBOL
2953 : (OP(first) == SBOL
2956 first = NEXTOPER(first);
2959 else if (OP(first) == GPOS) {
2960 r->reganch |= ROPT_ANCH_GPOS;
2961 first = NEXTOPER(first);
2964 else if (!sawopen && (OP(first) == STAR &&
2965 PL_regkind[(U8)OP(NEXTOPER(first))] == REG_ANY) &&
2966 !(r->reganch & ROPT_ANCH) )
2968 /* turn .* into ^.* with an implied $*=1 */
2970 (OP(NEXTOPER(first)) == REG_ANY)
2973 r->reganch |= type | ROPT_IMPLICIT;
2974 first = NEXTOPER(first);
2977 if (sawplus && (!sawopen || !RExC_sawback)
2978 && !(RExC_seen & REG_SEEN_EVAL)) /* May examine pos and $& */
2979 /* x+ must match at the 1st pos of run of x's */
2980 r->reganch |= ROPT_SKIP;
2982 /* Scan is after the zeroth branch, first is atomic matcher. */
2983 DEBUG_COMPILE_r(PerlIO_printf(Perl_debug_log, "first at %"IVdf"\n",
2984 (IV)(first - scan + 1)));
2986 * If there's something expensive in the r.e., find the
2987 * longest literal string that must appear and make it the
2988 * regmust. Resolve ties in favor of later strings, since
2989 * the regstart check works with the beginning of the r.e.
2990 * and avoiding duplication strengthens checking. Not a
2991 * strong reason, but sufficient in the absence of others.
2992 * [Now we resolve ties in favor of the earlier string if
2993 * it happens that c_offset_min has been invalidated, since the
2994 * earlier string may buy us something the later one won't.]
2998 data.longest_fixed = newSVpvs("");
2999 data.longest_float = newSVpvs("");
3000 data.last_found = newSVpvs("");
3001 data.longest = &(data.longest_fixed);
3003 if (!r->regstclass) {
3004 cl_init(pRExC_state, &ch_class);
3005 data.start_class = &ch_class;
3006 stclass_flag = SCF_DO_STCLASS_AND;
3007 } else /* XXXX Check for BOUND? */
3009 data.last_closep = &last_close;
3011 minlen = study_chunk(pRExC_state, &first, &fake, scan + RExC_size, /* Up to end */
3012 &data, SCF_DO_SUBSTR | SCF_WHILEM_VISITED_POS | stclass_flag,0);
3013 if ( RExC_npar == 1 && data.longest == &(data.longest_fixed)
3014 && data.last_start_min == 0 && data.last_end > 0
3015 && !RExC_seen_zerolen
3016 && (!(RExC_seen & REG_SEEN_GPOS) || (r->reganch & ROPT_ANCH_GPOS)))
3017 r->reganch |= ROPT_CHECK_ALL;
3018 scan_commit(pRExC_state, &data);
3019 SvREFCNT_dec(data.last_found);
3021 longest_float_length = CHR_SVLEN(data.longest_float);
3022 if (longest_float_length
3023 || (data.flags & SF_FL_BEFORE_EOL
3024 && (!(data.flags & SF_FL_BEFORE_MEOL)
3025 || (RExC_flags & PMf_MULTILINE)))) {
3028 if (SvCUR(data.longest_fixed) /* ok to leave SvCUR */
3029 && data.offset_fixed == data.offset_float_min
3030 && SvCUR(data.longest_fixed) == SvCUR(data.longest_float))
3031 goto remove_float; /* As in (a)+. */
3033 if (SvUTF8(data.longest_float)) {
3034 r->float_utf8 = data.longest_float;
3035 r->float_substr = NULL;
3037 r->float_substr = data.longest_float;
3038 r->float_utf8 = NULL;
3040 r->float_min_offset = data.offset_float_min;
3041 r->float_max_offset = data.offset_float_max;
3042 t = (data.flags & SF_FL_BEFORE_EOL /* Can't have SEOL and MULTI */
3043 && (!(data.flags & SF_FL_BEFORE_MEOL)
3044 || (RExC_flags & PMf_MULTILINE)));
3045 fbm_compile(data.longest_float, t ? FBMcf_TAIL : 0);
3049 r->float_substr = r->float_utf8 = NULL;
3050 SvREFCNT_dec(data.longest_float);
3051 longest_float_length = 0;
3054 longest_fixed_length = CHR_SVLEN(data.longest_fixed);
3055 if (longest_fixed_length
3056 || (data.flags & SF_FIX_BEFORE_EOL /* Cannot have SEOL and MULTI */
3057 && (!(data.flags & SF_FIX_BEFORE_MEOL)
3058 || (RExC_flags & PMf_MULTILINE)))) {
3061 if (SvUTF8(data.longest_fixed)) {
3062 r->anchored_utf8 = data.longest_fixed;
3063 r->anchored_substr = NULL;
3065 r->anchored_substr = data.longest_fixed;
3066 r->anchored_utf8 = NULL;
3068 r->anchored_offset = data.offset_fixed;
3069 t = (data.flags & SF_FIX_BEFORE_EOL /* Can't have SEOL and MULTI */
3070 && (!(data.flags & SF_FIX_BEFORE_MEOL)
3071 || (RExC_flags & PMf_MULTILINE)));
3072 fbm_compile(data.longest_fixed, t ? FBMcf_TAIL : 0);
3075 r->anchored_substr = r->anchored_utf8 = NULL;
3076 SvREFCNT_dec(data.longest_fixed);
3077 longest_fixed_length = 0;
3080 && (OP(r->regstclass) == REG_ANY || OP(r->regstclass) == SANY))
3081 r->regstclass = NULL;
3082 if ((!(r->anchored_substr || r->anchored_utf8) || r->anchored_offset)
3084 && !(data.start_class->flags & ANYOF_EOS)
3085 && !cl_is_anything(data.start_class))
3087 const I32 n = add_data(pRExC_state, 1, "f");
3089 Newx(RExC_rx->data->data[n], 1,
3090 struct regnode_charclass_class);
3091 StructCopy(data.start_class,
3092 (struct regnode_charclass_class*)RExC_rx->data->data[n],
3093 struct regnode_charclass_class);
3094 r->regstclass = (regnode*)RExC_rx->data->data[n];
3095 r->reganch &= ~ROPT_SKIP; /* Used in find_byclass(). */
3096 DEBUG_COMPILE_r({ SV *sv = sv_newmortal();
3097 regprop(r, sv, (regnode*)data.start_class);
3098 PerlIO_printf(Perl_debug_log,
3099 "synthetic stclass \"%s\".\n",
3100 SvPVX_const(sv));});
3103 /* A temporary algorithm prefers floated substr to fixed one to dig more info. */
3104 if (longest_fixed_length > longest_float_length) {
3105 r->check_substr = r->anchored_substr;
3106 r->check_utf8 = r->anchored_utf8;
3107 r->check_offset_min = r->check_offset_max = r->anchored_offset;
3108 if (r->reganch & ROPT_ANCH_SINGLE)
3109 r->reganch |= ROPT_NOSCAN;
3112 r->check_substr = r->float_substr;
3113 r->check_utf8 = r->float_utf8;
3114 r->check_offset_min = data.offset_float_min;
3115 r->check_offset_max = data.offset_float_max;
3117 /* XXXX Currently intuiting is not compatible with ANCH_GPOS.
3118 This should be changed ASAP! */
3119 if ((r->check_substr || r->check_utf8) && !(r->reganch & ROPT_ANCH_GPOS)) {
3120 r->reganch |= RE_USE_INTUIT;
3121 if (SvTAIL(r->check_substr ? r->check_substr : r->check_utf8))
3122 r->reganch |= RE_INTUIT_TAIL;
3126 /* Several toplevels. Best we can is to set minlen. */
3128 struct regnode_charclass_class ch_class;
3131 DEBUG_COMPILE_r(PerlIO_printf(Perl_debug_log, "\n"));
3132 scan = r->program + 1;
3133 cl_init(pRExC_state, &ch_class);
3134 data.start_class = &ch_class;
3135 data.last_closep = &last_close;
3136 minlen = study_chunk(pRExC_state, &scan, &fake, scan + RExC_size, &data, SCF_DO_STCLASS_AND|SCF_WHILEM_VISITED_POS,0);
3137 r->check_substr = r->check_utf8 = r->anchored_substr = r->anchored_utf8
3138 = r->float_substr = r->float_utf8 = NULL;
3139 if (!(data.start_class->flags & ANYOF_EOS)
3140 && !cl_is_anything(data.start_class))
3142 const I32 n = add_data(pRExC_state, 1, "f");
3144 Newx(RExC_rx->data->data[n], 1,
3145 struct regnode_charclass_class);
3146 StructCopy(data.start_class,
3147 (struct regnode_charclass_class*)RExC_rx->data->data[n],
3148 struct regnode_charclass_class);
3149 r->regstclass = (regnode*)RExC_rx->data->data[n];
3150 r->reganch &= ~ROPT_SKIP; /* Used in find_byclass(). */
3151 DEBUG_COMPILE_r({ SV* sv = sv_newmortal();
3152 regprop(r, sv, (regnode*)data.start_class);
3153 PerlIO_printf(Perl_debug_log,
3154 "synthetic stclass \"%s\".\n",
3155 SvPVX_const(sv));});
3160 if (RExC_seen & REG_SEEN_GPOS)
3161 r->reganch |= ROPT_GPOS_SEEN;
3162 if (RExC_seen & REG_SEEN_LOOKBEHIND)
3163 r->reganch |= ROPT_LOOKBEHIND_SEEN;
3164 if (RExC_seen & REG_SEEN_EVAL)
3165 r->reganch |= ROPT_EVAL_SEEN;
3166 if (RExC_seen & REG_SEEN_CANY)
3167 r->reganch |= ROPT_CANY_SEEN;
3168 Newxz(r->startp, RExC_npar, I32);
3169 Newxz(r->endp, RExC_npar, I32);
3170 DEBUG_COMPILE_r(regdump(r));
3175 - reg - regular expression, i.e. main body or parenthesized thing
3177 * Caller must absorb opening parenthesis.
3179 * Combining parenthesis handling with the base level of regular expression
3180 * is a trifle forced, but the need to tie the tails of the branches to what
3181 * follows makes it hard to avoid.
3184 S_reg(pTHX_ RExC_state_t *pRExC_state, I32 paren, I32 *flagp)
3185 /* paren: Parenthesized? 0=top, 1=(, inside: changed to letter. */
3188 register regnode *ret; /* Will be the head of the group. */
3189 register regnode *br;
3190 register regnode *lastbr;
3191 register regnode *ender = NULL;
3192 register I32 parno = 0;
3194 const I32 oregflags = RExC_flags;
3195 bool have_branch = 0;
3198 /* for (?g), (?gc), and (?o) warnings; warning
3199 about (?c) will warn about (?g) -- japhy */
3201 #define WASTED_O 0x01
3202 #define WASTED_G 0x02
3203 #define WASTED_C 0x04
3204 #define WASTED_GC (0x02|0x04)
3205 I32 wastedflags = 0x00;
3207 char * parse_start = RExC_parse; /* MJD */
3208 char * const oregcomp_parse = RExC_parse;
3210 *flagp = 0; /* Tentatively. */
3213 /* Make an OPEN node, if parenthesized. */
3215 if (*RExC_parse == '?') { /* (?...) */
3216 U32 posflags = 0, negflags = 0;
3217 U32 *flagsp = &posflags;
3218 bool is_logical = 0;
3219 const char * const seqstart = RExC_parse;
3222 paren = *RExC_parse++;
3223 ret = NULL; /* For look-ahead/behind. */
3225 case '<': /* (?<...) */
3226 RExC_seen |= REG_SEEN_LOOKBEHIND;
3227 if (*RExC_parse == '!')
3229 if (*RExC_parse != '=' && *RExC_parse != '!')
3232 case '=': /* (?=...) */
3233 case '!': /* (?!...) */
3234 RExC_seen_zerolen++;
3235 case ':': /* (?:...) */
3236 case '>': /* (?>...) */
3238 case '$': /* (?$...) */
3239 case '@': /* (?@...) */
3240 vFAIL2("Sequence (?%c...) not implemented", (int)paren);
3242 case '#': /* (?#...) */
3243 while (*RExC_parse && *RExC_parse != ')')
3245 if (*RExC_parse != ')')
3246 FAIL("Sequence (?#... not terminated");
3247 nextchar(pRExC_state);
3250 case 'p': /* (?p...) */
3251 if (SIZE_ONLY && ckWARN2(WARN_DEPRECATED, WARN_REGEXP))
3252 vWARNdep(RExC_parse, "(?p{}) is deprecated - use (??{})");
3254 case '?': /* (??...) */
3256 if (*RExC_parse != '{')
3258 paren = *RExC_parse++;
3260 case '{': /* (?{...}) */
3262 I32 count = 1, n = 0;
3264 char *s = RExC_parse;
3266 RExC_seen_zerolen++;
3267 RExC_seen |= REG_SEEN_EVAL;
3268 while (count && (c = *RExC_parse)) {
3279 if (*RExC_parse != ')') {
3281 vFAIL("Sequence (?{...}) not terminated or not {}-balanced");
3285 OP_4tree *sop, *rop;
3286 SV * const sv = newSVpvn(s, RExC_parse - 1 - s);
3289 Perl_save_re_context(aTHX);
3290 rop = sv_compile_2op(sv, &sop, "re", &pad);
3291 sop->op_private |= OPpREFCOUNTED;
3292 /* re_dup will OpREFCNT_inc */
3293 OpREFCNT_set(sop, 1);
3296 n = add_data(pRExC_state, 3, "nop");
3297 RExC_rx->data->data[n] = (void*)rop;
3298 RExC_rx->data->data[n+1] = (void*)sop;
3299 RExC_rx->data->data[n+2] = (void*)pad;
3302 else { /* First pass */
3303 if (PL_reginterp_cnt < ++RExC_seen_evals
3305 /* No compiled RE interpolated, has runtime
3306 components ===> unsafe. */
3307 FAIL("Eval-group not allowed at runtime, use re 'eval'");
3308 if (PL_tainting && PL_tainted)
3309 FAIL("Eval-group in insecure regular expression");
3310 #if PERL_VERSION > 8
3311 if (IN_PERL_COMPILETIME)
3316 nextchar(pRExC_state);
3318 ret = reg_node(pRExC_state, LOGICAL);
3321 regtail(pRExC_state, ret, reganode(pRExC_state, EVAL, n));
3322 /* deal with the length of this later - MJD */
3325 ret = reganode(pRExC_state, EVAL, n);
3326 Set_Node_Length(ret, RExC_parse - parse_start + 1);
3327 Set_Node_Offset(ret, parse_start);
3330 case '(': /* (?(?{...})...) and (?(?=...)...) */
3332 if (RExC_parse[0] == '?') { /* (?(?...)) */
3333 if (RExC_parse[1] == '=' || RExC_parse[1] == '!'
3334 || RExC_parse[1] == '<'
3335 || RExC_parse[1] == '{') { /* Lookahead or eval. */
3338 ret = reg_node(pRExC_state, LOGICAL);
3341 regtail(pRExC_state, ret, reg(pRExC_state, 1, &flag));
3345 else if (RExC_parse[0] >= '1' && RExC_parse[0] <= '9' ) {
3348 parno = atoi(RExC_parse++);
3350 while (isDIGIT(*RExC_parse))
3352 ret = reganode(pRExC_state, GROUPP, parno);
3354 if ((c = *nextchar(pRExC_state)) != ')')
3355 vFAIL("Switch condition not recognized");
3357 regtail(pRExC_state, ret, reganode(pRExC_state, IFTHEN, 0));
3358 br = regbranch(pRExC_state, &flags, 1);
3360 br = reganode(pRExC_state, LONGJMP, 0);
3362 regtail(pRExC_state, br, reganode(pRExC_state, LONGJMP, 0));
3363 c = *nextchar(pRExC_state);
3367 lastbr = reganode(pRExC_state, IFTHEN, 0); /* Fake one for optimizer. */
3368 regbranch(pRExC_state, &flags, 1);
3369 regtail(pRExC_state, ret, lastbr);
3372 c = *nextchar(pRExC_state);
3377 vFAIL("Switch (?(condition)... contains too many branches");
3378 ender = reg_node(pRExC_state, TAIL);
3379 regtail(pRExC_state, br, ender);
3381 regtail(pRExC_state, lastbr, ender);
3382 regtail(pRExC_state, NEXTOPER(NEXTOPER(lastbr)), ender);
3385 regtail(pRExC_state, ret, ender);
3389 vFAIL2("Unknown switch condition (?(%.2s", RExC_parse);
3393 RExC_parse--; /* for vFAIL to print correctly */
3394 vFAIL("Sequence (? incomplete");
3398 parse_flags: /* (?i) */
3399 while (*RExC_parse && strchr("iogcmsx", *RExC_parse)) {
3400 /* (?g), (?gc) and (?o) are useless here
3401 and must be globally applied -- japhy */
3403 if (*RExC_parse == 'o' || *RExC_parse == 'g') {
3404 if (SIZE_ONLY && ckWARN(WARN_REGEXP)) {
3405 const I32 wflagbit = *RExC_parse == 'o' ? WASTED_O : WASTED_G;
3406 if (! (wastedflags & wflagbit) ) {
3407 wastedflags |= wflagbit;
3410 "Useless (%s%c) - %suse /%c modifier",
3411 flagsp == &negflags ? "?-" : "?",
3413 flagsp == &negflags ? "don't " : "",
3419 else if (*RExC_parse == 'c') {
3420 if (SIZE_ONLY && ckWARN(WARN_REGEXP)) {
3421 if (! (wastedflags & WASTED_C) ) {
3422 wastedflags |= WASTED_GC;
3425 "Useless (%sc) - %suse /gc modifier",
3426 flagsp == &negflags ? "?-" : "?",
3427 flagsp == &negflags ? "don't " : ""
3432 else { pmflag(flagsp, *RExC_parse); }
3436 if (*RExC_parse == '-') {
3438 wastedflags = 0; /* reset so (?g-c) warns twice */
3442 RExC_flags |= posflags;
3443 RExC_flags &= ~negflags;
3444 if (*RExC_parse == ':') {
3450 if (*RExC_parse != ')') {
3452 vFAIL3("Sequence (%.*s...) not recognized", RExC_parse-seqstart, seqstart);
3454 nextchar(pRExC_state);
3462 ret = reganode(pRExC_state, OPEN, parno);
3463 Set_Node_Length(ret, 1); /* MJD */
3464 Set_Node_Offset(ret, RExC_parse); /* MJD */
3471 /* Pick up the branches, linking them together. */
3472 parse_start = RExC_parse; /* MJD */
3473 br = regbranch(pRExC_state, &flags, 1);
3474 /* branch_len = (paren != 0); */
3478 if (*RExC_parse == '|') {
3479 if (!SIZE_ONLY && RExC_extralen) {
3480 reginsert(pRExC_state, BRANCHJ, br);
3483 reginsert(pRExC_state, BRANCH, br);
3484 Set_Node_Length(br, paren != 0);
3485 Set_Node_Offset_To_R(br-RExC_emit_start, parse_start-RExC_start);
3489 RExC_extralen += 1; /* For BRANCHJ-BRANCH. */
3491 else if (paren == ':') {
3492 *flagp |= flags&SIMPLE;
3494 if (is_open) { /* Starts with OPEN. */
3495 regtail(pRExC_state, ret, br); /* OPEN -> first. */
3497 else if (paren != '?') /* Not Conditional */
3499 *flagp |= flags & (SPSTART | HASWIDTH);
3501 while (*RExC_parse == '|') {
3502 if (!SIZE_ONLY && RExC_extralen) {
3503 ender = reganode(pRExC_state, LONGJMP,0);
3504 regtail(pRExC_state, NEXTOPER(NEXTOPER(lastbr)), ender); /* Append to the previous. */
3507 RExC_extralen += 2; /* Account for LONGJMP. */
3508 nextchar(pRExC_state);
3509 br = regbranch(pRExC_state, &flags, 0);
3513 regtail(pRExC_state, lastbr, br); /* BRANCH -> BRANCH. */
3517 *flagp |= flags&SPSTART;
3520 if (have_branch || paren != ':') {
3521 /* Make a closing node, and hook it on the end. */
3524 ender = reg_node(pRExC_state, TAIL);
3527 ender = reganode(pRExC_state, CLOSE, parno);
3528 Set_Node_Offset(ender,RExC_parse+1); /* MJD */
3529 Set_Node_Length(ender,1); /* MJD */
3535 *flagp &= ~HASWIDTH;
3538 ender = reg_node(pRExC_state, SUCCEED);
3541 ender = reg_node(pRExC_state, END);
3544 regtail(pRExC_state, lastbr, ender);
3547 /* Hook the tails of the branches to the closing node. */
3548 for (br = ret; br != NULL; br = regnext(br)) {
3549 regoptail(pRExC_state, br, ender);
3556 static const char parens[] = "=!<,>";
3558 if (paren && (p = strchr(parens, paren))) {
3559 U8 node = ((p - parens) % 2) ? UNLESSM : IFMATCH;
3560 int flag = (p - parens) > 1;
3563 node = SUSPEND, flag = 0;
3564 reginsert(pRExC_state, node,ret);
3565 Set_Node_Cur_Length(ret);
3566 Set_Node_Offset(ret, parse_start + 1);
3568 regtail(pRExC_state, ret, reg_node(pRExC_state, TAIL));
3572 /* Check for proper termination. */
3574 RExC_flags = oregflags;
3575 if (RExC_parse >= RExC_end || *nextchar(pRExC_state) != ')') {
3576 RExC_parse = oregcomp_parse;
3577 vFAIL("Unmatched (");
3580 else if (!paren && RExC_parse < RExC_end) {
3581 if (*RExC_parse == ')') {
3583 vFAIL("Unmatched )");
3586 FAIL("Junk on end of regexp"); /* "Can't happen". */
3594 - regbranch - one alternative of an | operator
3596 * Implements the concatenation operator.
3599 S_regbranch(pTHX_ RExC_state_t *pRExC_state, I32 *flagp, I32 first)
3602 register regnode *ret;
3603 register regnode *chain = NULL;
3604 register regnode *latest;
3605 I32 flags = 0, c = 0;
3610 if (!SIZE_ONLY && RExC_extralen)
3611 ret = reganode(pRExC_state, BRANCHJ,0);
3613 ret = reg_node(pRExC_state, BRANCH);
3614 Set_Node_Length(ret, 1);
3618 if (!first && SIZE_ONLY)
3619 RExC_extralen += 1; /* BRANCHJ */
3621 *flagp = WORST; /* Tentatively. */
3624 nextchar(pRExC_state);
3625 while (RExC_parse < RExC_end && *RExC_parse != '|' && *RExC_parse != ')') {
3627 latest = regpiece(pRExC_state, &flags);
3628 if (latest == NULL) {
3629 if (flags & TRYAGAIN)
3633 else if (ret == NULL)
3635 *flagp |= flags&HASWIDTH;
3636 if (chain == NULL) /* First piece. */
3637 *flagp |= flags&SPSTART;
3640 regtail(pRExC_state, chain, latest);
3645 if (chain == NULL) { /* Loop ran zero times. */
3646 chain = reg_node(pRExC_state, NOTHING);
3651 *flagp |= flags&SIMPLE;
3658 - regpiece - something followed by possible [*+?]
3660 * Note that the branching code sequences used for ? and the general cases
3661 * of * and + are somewhat optimized: they use the same NOTHING node as
3662 * both the endmarker for their branch list and the body of the last branch.
3663 * It might seem that this node could be dispensed with entirely, but the
3664 * endmarker role is not redundant.
3667 S_regpiece(pTHX_ RExC_state_t *pRExC_state, I32 *flagp)
3670 register regnode *ret;
3672 register char *next;
3674 const char * const origparse = RExC_parse;
3677 I32 max = REG_INFTY;
3680 ret = regatom(pRExC_state, &flags);
3682 if (flags & TRYAGAIN)
3689 if (op == '{' && regcurly(RExC_parse)) {
3690 parse_start = RExC_parse; /* MJD */
3691 next = RExC_parse + 1;
3693 while (isDIGIT(*next) || *next == ',') {
3702 if (*next == '}') { /* got one */
3706 min = atoi(RExC_parse);
3710 maxpos = RExC_parse;
3712 if (!max && *maxpos != '0')
3713 max = REG_INFTY; /* meaning "infinity" */
3714 else if (max >= REG_INFTY)
3715 vFAIL2("Quantifier in {,} bigger than %d", REG_INFTY - 1);
3717 nextchar(pRExC_state);
3720 if ((flags&SIMPLE)) {
3721 RExC_naughty += 2 + RExC_naughty / 2;
3722 reginsert(pRExC_state, CURLY, ret);
3723 Set_Node_Offset(ret, parse_start+1); /* MJD */
3724 Set_Node_Cur_Length(ret);
3727 regnode *w = reg_node(pRExC_state, WHILEM);
3730 regtail(pRExC_state, ret, w);
3731 if (!SIZE_ONLY && RExC_extralen) {
3732 reginsert(pRExC_state, LONGJMP,ret);
3733 reginsert(pRExC_state, NOTHING,ret);
3734 NEXT_OFF(ret) = 3; /* Go over LONGJMP. */
3736 reginsert(pRExC_state, CURLYX,ret);
3738 Set_Node_Offset(ret, parse_start+1);
3739 Set_Node_Length(ret,
3740 op == '{' ? (RExC_parse - parse_start) : 1);
3742 if (!SIZE_ONLY && RExC_extralen)
3743 NEXT_OFF(ret) = 3; /* Go over NOTHING to LONGJMP. */
3744 regtail(pRExC_state, ret, reg_node(pRExC_state, NOTHING));
3746 RExC_whilem_seen++, RExC_extralen += 3;
3747 RExC_naughty += 4 + RExC_naughty; /* compound interest */
3755 if (max && max < min)
3756 vFAIL("Can't do {n,m} with n > m");
3758 ARG1_SET(ret, (U16)min);
3759 ARG2_SET(ret, (U16)max);
3771 #if 0 /* Now runtime fix should be reliable. */
3773 /* if this is reinstated, don't forget to put this back into perldiag:
3775 =item Regexp *+ operand could be empty at {#} in regex m/%s/
3777 (F) The part of the regexp subject to either the * or + quantifier
3778 could match an empty string. The {#} shows in the regular
3779 expression about where the problem was discovered.
3783 if (!(flags&HASWIDTH) && op != '?')
3784 vFAIL("Regexp *+ operand could be empty");
3787 parse_start = RExC_parse;
3788 nextchar(pRExC_state);
3790 *flagp = (op != '+') ? (WORST|SPSTART|HASWIDTH) : (WORST|HASWIDTH);
3792 if (op == '*' && (flags&SIMPLE)) {
3793 reginsert(pRExC_state, STAR, ret);
3797 else if (op == '*') {
3801 else if (op == '+' && (flags&SIMPLE)) {
3802 reginsert(pRExC_state, PLUS, ret);
3806 else if (op == '+') {
3810 else if (op == '?') {
3815 if (!SIZE_ONLY && !(flags&HASWIDTH) && max > REG_INFTY/3 && ckWARN(WARN_REGEXP)) {
3817 "%.*s matches null string many times",
3818 (int)(RExC_parse >= origparse ? RExC_parse - origparse : 0),
3822 if (*RExC_parse == '?') {
3823 nextchar(pRExC_state);
3824 reginsert(pRExC_state, MINMOD, ret);
3825 regtail(pRExC_state, ret, ret + NODE_STEP_REGNODE);
3827 if (ISMULT2(RExC_parse)) {
3829 vFAIL("Nested quantifiers");
3836 - regatom - the lowest level
3838 * Optimization: gobbles an entire sequence of ordinary characters so that
3839 * it can turn them into a single node, which is smaller to store and
3840 * faster to run. Backslashed characters are exceptions, each becoming a
3841 * separate node; the code is simpler that way and it's not worth fixing.
3843 * [Yes, it is worth fixing, some scripts can run twice the speed.] */
3845 S_regatom(pTHX_ RExC_state_t *pRExC_state, I32 *flagp)
3848 register regnode *ret = NULL;
3850 char *parse_start = RExC_parse;
3852 *flagp = WORST; /* Tentatively. */
3855 switch (*RExC_parse) {
3857 RExC_seen_zerolen++;
3858 nextchar(pRExC_state);
3859 if (RExC_flags & PMf_MULTILINE)
3860 ret = reg_node(pRExC_state, MBOL);
3861 else if (RExC_flags & PMf_SINGLELINE)
3862 ret = reg_node(pRExC_state, SBOL);
3864 ret = reg_node(pRExC_state, BOL);
3865 Set_Node_Length(ret, 1); /* MJD */
3868 nextchar(pRExC_state);
3870 RExC_seen_zerolen++;
3871 if (RExC_flags & PMf_MULTILINE)
3872 ret = reg_node(pRExC_state, MEOL);
3873 else if (RExC_flags & PMf_SINGLELINE)
3874 ret = reg_node(pRExC_state, SEOL);
3876 ret = reg_node(pRExC_state, EOL);
3877 Set_Node_Length(ret, 1); /* MJD */
3880 nextchar(pRExC_state);
3881 if (RExC_flags & PMf_SINGLELINE)
3882 ret = reg_node(pRExC_state, SANY);
3884 ret = reg_node(pRExC_state, REG_ANY);
3885 *flagp |= HASWIDTH|SIMPLE;
3887 Set_Node_Length(ret, 1); /* MJD */
3891 char *oregcomp_parse = ++RExC_parse;
3892 ret = regclass(pRExC_state);
3893 if (*RExC_parse != ']') {
3894 RExC_parse = oregcomp_parse;
3895 vFAIL("Unmatched [");
3897 nextchar(pRExC_state);
3898 *flagp |= HASWIDTH|SIMPLE;
3899 Set_Node_Length(ret, RExC_parse - oregcomp_parse + 1); /* MJD */
3903 nextchar(pRExC_state);
3904 ret = reg(pRExC_state, 1, &flags);
3906 if (flags & TRYAGAIN) {
3907 if (RExC_parse == RExC_end) {
3908 /* Make parent create an empty node if needed. */
3916 *flagp |= flags&(HASWIDTH|SPSTART|SIMPLE);
3920 if (flags & TRYAGAIN) {
3924 vFAIL("Internal urp");
3925 /* Supposed to be caught earlier. */
3928 if (!regcurly(RExC_parse)) {
3937 vFAIL("Quantifier follows nothing");
3940 switch (*++RExC_parse) {
3942 RExC_seen_zerolen++;
3943 ret = reg_node(pRExC_state, SBOL);
3945 nextchar(pRExC_state);
3946 Set_Node_Length(ret, 2); /* MJD */
3949 ret = reg_node(pRExC_state, GPOS);
3950 RExC_seen |= REG_SEEN_GPOS;
3952 nextchar(pRExC_state);
3953 Set_Node_Length(ret, 2); /* MJD */
3956 ret = reg_node(pRExC_state, SEOL);
3958 RExC_seen_zerolen++; /* Do not optimize RE away */
3959 nextchar(pRExC_state);
3962 ret = reg_node(pRExC_state, EOS);
3964 RExC_seen_zerolen++; /* Do not optimize RE away */
3965 nextchar(pRExC_state);
3966 Set_Node_Length(ret, 2); /* MJD */
3969 ret = reg_node(pRExC_state, CANY);
3970 RExC_seen |= REG_SEEN_CANY;
3971 *flagp |= HASWIDTH|SIMPLE;
3972 nextchar(pRExC_state);
3973 Set_Node_Length(ret, 2); /* MJD */
3976 ret = reg_node(pRExC_state, CLUMP);
3978 nextchar(pRExC_state);
3979 Set_Node_Length(ret, 2); /* MJD */
3982 ret = reg_node(pRExC_state, (U8)(LOC ? ALNUML : ALNUM));
3983 *flagp |= HASWIDTH|SIMPLE;
3984 nextchar(pRExC_state);
3985 Set_Node_Length(ret, 2); /* MJD */
3988 ret = reg_node(pRExC_state, (U8)(LOC ? NALNUML : NALNUM));
3989 *flagp |= HASWIDTH|SIMPLE;
3990 nextchar(pRExC_state);
3991 Set_Node_Length(ret, 2); /* MJD */
3994 RExC_seen_zerolen++;
3995 RExC_seen |= REG_SEEN_LOOKBEHIND;
3996 ret = reg_node(pRExC_state, (U8)(LOC ? BOUNDL : BOUND));
3998 nextchar(pRExC_state);
3999 Set_Node_Length(ret, 2); /* MJD */
4002 RExC_seen_zerolen++;
4003 RExC_seen |= REG_SEEN_LOOKBEHIND;
4004 ret = reg_node(pRExC_state, (U8)(LOC ? NBOUNDL : NBOUND));
4006 nextchar(pRExC_state);
4007 Set_Node_Length(ret, 2); /* MJD */
4010 ret = reg_node(pRExC_state, (U8)(LOC ? SPACEL : SPACE));
4011 *flagp |= HASWIDTH|SIMPLE;
4012 nextchar(pRExC_state);
4013 Set_Node_Length(ret, 2); /* MJD */
4016 ret = reg_node(pRExC_state, (U8)(LOC ? NSPACEL : NSPACE));
4017 *flagp |= HASWIDTH|SIMPLE;
4018 nextchar(pRExC_state);
4019 Set_Node_Length(ret, 2); /* MJD */
4022 ret = reg_node(pRExC_state, DIGIT);
4023 *flagp |= HASWIDTH|SIMPLE;
4024 nextchar(pRExC_state);
4025 Set_Node_Length(ret, 2); /* MJD */
4028 ret = reg_node(pRExC_state, NDIGIT);
4029 *flagp |= HASWIDTH|SIMPLE;
4030 nextchar(pRExC_state);
4031 Set_Node_Length(ret, 2); /* MJD */
4036 char* oldregxend = RExC_end;
4037 char* parse_start = RExC_parse - 2;
4039 if (RExC_parse[1] == '{') {
4040 /* a lovely hack--pretend we saw [\pX] instead */
4041 RExC_end = strchr(RExC_parse, '}');
4043 U8 c = (U8)*RExC_parse;
4045 RExC_end = oldregxend;
4046 vFAIL2("Missing right brace on \\%c{}", c);
4051 RExC_end = RExC_parse + 2;
4052 if (RExC_end > oldregxend)
4053 RExC_end = oldregxend;
4057 ret = regclass(pRExC_state);
4059 RExC_end = oldregxend;
4062 Set_Node_Offset(ret, parse_start + 2);
4063 Set_Node_Cur_Length(ret);
4064 nextchar(pRExC_state);
4065 *flagp |= HASWIDTH|SIMPLE;
4078 case '1': case '2': case '3': case '4':
4079 case '5': case '6': case '7': case '8': case '9':
4081 const I32 num = atoi(RExC_parse);
4083 if (num > 9 && num >= RExC_npar)
4086 char * parse_start = RExC_parse - 1; /* MJD */
4087 while (isDIGIT(*RExC_parse))
4090 if (!SIZE_ONLY && num > (I32)RExC_rx->nparens)
4091 vFAIL("Reference to nonexistent group");
4093 ret = reganode(pRExC_state,
4094 (U8)(FOLD ? (LOC ? REFFL : REFF) : REF),
4098 /* override incorrect value set in reganode MJD */
4099 Set_Node_Offset(ret, parse_start+1);
4100 Set_Node_Cur_Length(ret); /* MJD */
4102 nextchar(pRExC_state);
4107 if (RExC_parse >= RExC_end)
4108 FAIL("Trailing \\");
4111 /* Do not generate "unrecognized" warnings here, we fall
4112 back into the quick-grab loop below */
4119 if (RExC_flags & PMf_EXTENDED) {
4120 while (RExC_parse < RExC_end && *RExC_parse != '\n') RExC_parse++;
4121 if (RExC_parse < RExC_end)
4127 register STRLEN len;
4132 U8 tmpbuf[UTF8_MAXBYTES_CASE+1], *foldbuf;
4134 parse_start = RExC_parse - 1;
4140 ret = reg_node(pRExC_state,
4141 (U8)(FOLD ? (LOC ? EXACTFL : EXACTF) : EXACT));
4143 for (len = 0, p = RExC_parse - 1;
4144 len < 127 && p < RExC_end;
4149 if (RExC_flags & PMf_EXTENDED)
4150 p = regwhite(p, RExC_end);
4197 ender = ASCII_TO_NATIVE('\033');
4201 ender = ASCII_TO_NATIVE('\007');
4206 char* const e = strchr(p, '}');
4210 vFAIL("Missing right brace on \\x{}");
4213 I32 flags = PERL_SCAN_ALLOW_UNDERSCORES
4214 | PERL_SCAN_DISALLOW_PREFIX;
4215 STRLEN numlen = e - p - 1;
4216 ender = grok_hex(p + 1, &numlen, &flags, NULL);
4223 I32 flags = PERL_SCAN_DISALLOW_PREFIX;
4225 ender = grok_hex(p, &numlen, &flags, NULL);
4231 ender = UCHARAT(p++);
4232 ender = toCTRL(ender);
4234 case '0': case '1': case '2': case '3':case '4':
4235 case '5': case '6': case '7': case '8':case '9':
4237 (isDIGIT(p[1]) && atoi(p) >= RExC_npar) ) {
4240 ender = grok_oct(p, &numlen, &flags, NULL);
4250 FAIL("Trailing \\");
4253 if (!SIZE_ONLY&& isALPHA(*p) && ckWARN(WARN_REGEXP))
4254 vWARN2(p + 1, "Unrecognized escape \\%c passed through", UCHARAT(p));
4255 goto normal_default;
4260 if (UTF8_IS_START(*p) && UTF) {
4262 ender = utf8n_to_uvchr((U8*)p, RExC_end - p,
4263 &numlen, UTF8_ALLOW_DEFAULT);
4270 if (RExC_flags & PMf_EXTENDED)
4271 p = regwhite(p, RExC_end);
4273 /* Prime the casefolded buffer. */
4274 ender = toFOLD_uni(ender, tmpbuf, &foldlen);
4276 if (ISMULT2(p)) { /* Back off on ?+*. */
4283 /* Emit all the Unicode characters. */
4285 for (foldbuf = tmpbuf;
4287 foldlen -= numlen) {
4288 ender = utf8_to_uvchr(foldbuf, &numlen);
4290 reguni(pRExC_state, ender, s, &unilen);
4293 /* In EBCDIC the numlen
4294 * and unilen can differ. */
4296 if (numlen >= foldlen)
4300 break; /* "Can't happen." */
4304 reguni(pRExC_state, ender, s, &unilen);
4313 REGC((char)ender, s++);
4321 /* Emit all the Unicode characters. */
4323 for (foldbuf = tmpbuf;
4325 foldlen -= numlen) {
4326 ender = utf8_to_uvchr(foldbuf, &numlen);
4328 reguni(pRExC_state, ender, s, &unilen);
4331 /* In EBCDIC the numlen
4332 * and unilen can differ. */
4334 if (numlen >= foldlen)
4342 reguni(pRExC_state, ender, s, &unilen);
4351 REGC((char)ender, s++);
4355 Set_Node_Cur_Length(ret); /* MJD */
4356 nextchar(pRExC_state);
4358 /* len is STRLEN which is unsigned, need to copy to signed */
4361 vFAIL("Internal disaster");
4365 if (len == 1 && UNI_IS_INVARIANT(ender))
4370 RExC_size += STR_SZ(len);
4372 RExC_emit += STR_SZ(len);
4377 /* If the encoding pragma is in effect recode the text of
4378 * any EXACT-kind nodes. */
4379 if (PL_encoding && PL_regkind[(U8)OP(ret)] == EXACT) {
4380 STRLEN oldlen = STR_LEN(ret);
4381 SV *sv = sv_2mortal(newSVpvn(STRING(ret), oldlen));
4385 if (sv_utf8_downgrade(sv, TRUE)) {
4386 const char * const s = sv_recode_to_utf8(sv, PL_encoding);
4387 const STRLEN newlen = SvCUR(sv);
4392 GET_RE_DEBUG_FLAGS_DECL;
4393 DEBUG_COMPILE_r(PerlIO_printf(Perl_debug_log, "recode %*s to %*s\n",
4394 (int)oldlen, STRING(ret),
4396 Copy(s, STRING(ret), newlen, char);
4397 STR_LEN(ret) += newlen - oldlen;
4398 RExC_emit += STR_SZ(newlen) - STR_SZ(oldlen);
4400 RExC_size += STR_SZ(newlen) - STR_SZ(oldlen);
4408 S_regwhite(char *p, const char *e)
4413 else if (*p == '#') {
4416 } while (p < e && *p != '\n');
4424 /* Parse POSIX character classes: [[:foo:]], [[=foo=]], [[.foo.]].
4425 Character classes ([:foo:]) can also be negated ([:^foo:]).
4426 Returns a named class id (ANYOF_XXX) if successful, -1 otherwise.
4427 Equivalence classes ([=foo=]) and composites ([.foo.]) are parsed,
4428 but trigger failures because they are currently unimplemented. */
4430 #define POSIXCC_DONE(c) ((c) == ':')
4431 #define POSIXCC_NOTYET(c) ((c) == '=' || (c) == '.')
4432 #define POSIXCC(c) (POSIXCC_DONE(c) || POSIXCC_NOTYET(c))
4435 S_regpposixcc(pTHX_ RExC_state_t *pRExC_state, I32 value)
4438 I32 namedclass = OOB_NAMEDCLASS;
4440 if (value == '[' && RExC_parse + 1 < RExC_end &&
4441 /* I smell either [: or [= or [. -- POSIX has been here, right? */
4442 POSIXCC(UCHARAT(RExC_parse))) {
4443 const char c = UCHARAT(RExC_parse);
4444 char* const s = RExC_parse++;
4446 while (RExC_parse < RExC_end && UCHARAT(RExC_parse) != c)
4448 if (RExC_parse == RExC_end)
4449 /* Grandfather lone [:, [=, [. */
4452 const char* t = RExC_parse++; /* skip over the c */
4453 const char *posixcc;
4457 if (UCHARAT(RExC_parse) == ']') {
4458 RExC_parse++; /* skip over the ending ] */
4461 const I32 complement = *posixcc == '^' ? *posixcc++ : 0;
4462 const I32 skip = t - posixcc;
4464 /* Initially switch on the length of the name. */
4467 if (memEQ(posixcc, "word", 4)) {
4468 /* this is not POSIX, this is the Perl \w */;
4470 = complement ? ANYOF_NALNUM : ANYOF_ALNUM;
4474 /* Names all of length 5. */
4475 /* alnum alpha ascii blank cntrl digit graph lower
4476 print punct space upper */
4477 /* Offset 4 gives the best switch position. */
4478 switch (posixcc[4]) {
4480 if (memEQ(posixcc, "alph", 4)) {
4483 = complement ? ANYOF_NALPHA : ANYOF_ALPHA;
4487 if (memEQ(posixcc, "spac", 4)) {
4490 = complement ? ANYOF_NPSXSPC : ANYOF_PSXSPC;
4494 if (memEQ(posixcc, "grap", 4)) {
4497 = complement ? ANYOF_NGRAPH : ANYOF_GRAPH;
4501 if (memEQ(posixcc, "asci", 4)) {
4504 = complement ? ANYOF_NASCII : ANYOF_ASCII;
4508 if (memEQ(posixcc, "blan", 4)) {
4511 = complement ? ANYOF_NBLANK : ANYOF_BLANK;
4515 if (memEQ(posixcc, "cntr", 4)) {
4518 = complement ? ANYOF_NCNTRL : ANYOF_CNTRL;
4522 if (memEQ(posixcc, "alnu", 4)) {
4525 = complement ? ANYOF_NALNUMC : ANYOF_ALNUMC;
4529 if (memEQ(posixcc, "lowe", 4)) {
4532 = complement ? ANYOF_NLOWER : ANYOF_LOWER;
4534 if (memEQ(posixcc, "uppe", 4)) {
4537 = complement ? ANYOF_NUPPER : ANYOF_UPPER;
4541 if (memEQ(posixcc, "digi", 4)) {
4544 = complement ? ANYOF_NDIGIT : ANYOF_DIGIT;
4546 if (memEQ(posixcc, "prin", 4)) {
4549 = complement ? ANYOF_NPRINT : ANYOF_PRINT;
4551 if (memEQ(posixcc, "punc", 4)) {
4554 = complement ? ANYOF_NPUNCT : ANYOF_PUNCT;
4560 if (memEQ(posixcc, "xdigit", 6)) {
4562 = complement ? ANYOF_NXDIGIT : ANYOF_XDIGIT;
4567 if (namedclass == OOB_NAMEDCLASS)
4569 Simple_vFAIL3("POSIX class [:%.*s:] unknown",
4572 assert (posixcc[skip] == ':');
4573 assert (posixcc[skip+1] == ']');
4574 } else if (!SIZE_ONLY) {
4575 /* [[=foo=]] and [[.foo.]] are still future. */
4577 /* adjust RExC_parse so the warning shows after
4579 while (UCHARAT(RExC_parse) && UCHARAT(RExC_parse) != ']')
4581 Simple_vFAIL3("POSIX syntax [%c %c] is reserved for future extensions", c, c);
4584 /* Maternal grandfather:
4585 * "[:" ending in ":" but not in ":]" */
4595 S_checkposixcc(pTHX_ RExC_state_t *pRExC_state)
4598 if (!SIZE_ONLY && POSIXCC(UCHARAT(RExC_parse))) {
4599 const char *s = RExC_parse;
4600 const char c = *s++;
4602 while(*s && isALNUM(*s))
4604 if (*s && c == *s && s[1] == ']') {
4605 if (ckWARN(WARN_REGEXP))
4607 "POSIX syntax [%c %c] belongs inside character classes",
4610 /* [[=foo=]] and [[.foo.]] are still future. */
4611 if (POSIXCC_NOTYET(c)) {
4612 /* adjust RExC_parse so the error shows after
4614 while (UCHARAT(RExC_parse) && UCHARAT(RExC_parse++) != ']')
4616 Simple_vFAIL3("POSIX syntax [%c %c] is reserved for future extensions", c, c);
4623 S_regclass(pTHX_ RExC_state_t *pRExC_state)
4627 register UV nextvalue;
4628 register IV prevvalue = OOB_UNICODE;
4629 register IV range = 0;
4630 register regnode *ret;
4633 char *rangebegin = NULL;
4634 bool need_class = 0;
4638 bool optimize_invert = TRUE;
4639 AV* unicode_alternate = NULL;
4641 UV literal_endpoint = 0;
4644 ret = reganode(pRExC_state, ANYOF, 0);
4647 ANYOF_FLAGS(ret) = 0;
4649 if (UCHARAT(RExC_parse) == '^') { /* Complement of range. */
4653 ANYOF_FLAGS(ret) |= ANYOF_INVERT;
4657 RExC_size += ANYOF_SKIP;
4658 listsv = &PL_sv_undef; /* For code scanners: listsv always non-NULL. */
4661 RExC_emit += ANYOF_SKIP;
4663 ANYOF_FLAGS(ret) |= ANYOF_FOLD;
4665 ANYOF_FLAGS(ret) |= ANYOF_LOCALE;
4666 ANYOF_BITMAP_ZERO(ret);
4667 listsv = newSVpvs("# comment\n");
4670 nextvalue = RExC_parse < RExC_end ? UCHARAT(RExC_parse) : 0;
4672 if (!SIZE_ONLY && POSIXCC(nextvalue))
4673 checkposixcc(pRExC_state);
4675 /* allow 1st char to be ] (allowing it to be - is dealt with later) */
4676 if (UCHARAT(RExC_parse) == ']')
4679 while (RExC_parse < RExC_end && UCHARAT(RExC_parse) != ']') {
4683 namedclass = OOB_NAMEDCLASS; /* initialize as illegal */
4686 rangebegin = RExC_parse;
4688 value = utf8n_to_uvchr((U8*)RExC_parse,
4689 RExC_end - RExC_parse,
4690 &numlen, UTF8_ALLOW_DEFAULT);
4691 RExC_parse += numlen;
4694 value = UCHARAT(RExC_parse++);
4695 nextvalue = RExC_parse < RExC_end ? UCHARAT(RExC_parse) : 0;
4696 if (value == '[' && POSIXCC(nextvalue))
4697 namedclass = regpposixcc(pRExC_state, value);
4698 else if (value == '\\') {
4700 value = utf8n_to_uvchr((U8*)RExC_parse,
4701 RExC_end - RExC_parse,
4702 &numlen, UTF8_ALLOW_DEFAULT);
4703 RExC_parse += numlen;
4706 value = UCHARAT(RExC_parse++);
4707 /* Some compilers cannot handle switching on 64-bit integer
4708 * values, therefore value cannot be an UV. Yes, this will
4709 * be a problem later if we want switch on Unicode.
4710 * A similar issue a little bit later when switching on
4711 * namedclass. --jhi */
4712 switch ((I32)value) {
4713 case 'w': namedclass = ANYOF_ALNUM; break;
4714 case 'W': namedclass = ANYOF_NALNUM; break;
4715 case 's': namedclass = ANYOF_SPACE; break;
4716 case 'S': namedclass = ANYOF_NSPACE; break;
4717 case 'd': namedclass = ANYOF_DIGIT; break;
4718 case 'D': namedclass = ANYOF_NDIGIT; break;
4721 if (RExC_parse >= RExC_end)
4722 vFAIL2("Empty \\%c{}", (U8)value);
4723 if (*RExC_parse == '{') {
4724 const U8 c = (U8)value;
4725 e = strchr(RExC_parse++, '}');
4727 vFAIL2("Missing right brace on \\%c{}", c);
4728 while (isSPACE(UCHARAT(RExC_parse)))
4730 if (e == RExC_parse)
4731 vFAIL2("Empty \\%c{}", c);
4733 while (isSPACE(UCHARAT(RExC_parse + n - 1)))
4741 if (UCHARAT(RExC_parse) == '^') {
4744 value = value == 'p' ? 'P' : 'p'; /* toggle */
4745 while (isSPACE(UCHARAT(RExC_parse))) {
4750 Perl_sv_catpvf(aTHX_ listsv, "%cutf8::%.*s\n",
4751 (value=='p' ? '+' : '!'), (int)n, RExC_parse);
4754 ANYOF_FLAGS(ret) |= ANYOF_UNICODE;
4755 namedclass = ANYOF_MAX; /* no official name, but it's named */
4757 case 'n': value = '\n'; break;
4758 case 'r': value = '\r'; break;
4759 case 't': value = '\t'; break;
4760 case 'f': value = '\f'; break;
4761 case 'b': value = '\b'; break;
4762 case 'e': value = ASCII_TO_NATIVE('\033');break;
4763 case 'a': value = ASCII_TO_NATIVE('\007');break;
4765 if (*RExC_parse == '{') {
4766 I32 flags = PERL_SCAN_ALLOW_UNDERSCORES
4767 | PERL_SCAN_DISALLOW_PREFIX;
4768 e = strchr(RExC_parse++, '}');
4770 vFAIL("Missing right brace on \\x{}");
4772 numlen = e - RExC_parse;
4773 value = grok_hex(RExC_parse, &numlen, &flags, NULL);
4777 I32 flags = PERL_SCAN_DISALLOW_PREFIX;
4779 value = grok_hex(RExC_parse, &numlen, &flags, NULL);
4780 RExC_parse += numlen;
4784 value = UCHARAT(RExC_parse++);
4785 value = toCTRL(value);
4787 case '0': case '1': case '2': case '3': case '4':
4788 case '5': case '6': case '7': case '8': case '9':
4792 value = grok_oct(--RExC_parse, &numlen, &flags, NULL);
4793 RExC_parse += numlen;
4797 if (!SIZE_ONLY && isALPHA(value) && ckWARN(WARN_REGEXP))
4799 "Unrecognized escape \\%c in character class passed through",
4803 } /* end of \blah */
4809 if (namedclass > OOB_NAMEDCLASS) { /* this is a named class \blah */
4811 if (!SIZE_ONLY && !need_class)
4812 ANYOF_CLASS_ZERO(ret);
4816 /* a bad range like a-\d, a-[:digit:] ? */
4819 if (ckWARN(WARN_REGEXP)) {
4821 RExC_parse >= rangebegin ?
4822 RExC_parse - rangebegin : 0;
4824 "False [] range \"%*.*s\"",
4827 if (prevvalue < 256) {
4828 ANYOF_BITMAP_SET(ret, prevvalue);
4829 ANYOF_BITMAP_SET(ret, '-');
4832 ANYOF_FLAGS(ret) |= ANYOF_UNICODE;
4833 Perl_sv_catpvf(aTHX_ listsv,
4834 "%04"UVxf"\n%04"UVxf"\n", (UV)prevvalue, (UV) '-');
4838 range = 0; /* this was not a true range */
4842 const char *what = NULL;
4845 if (namedclass > OOB_NAMEDCLASS)
4846 optimize_invert = FALSE;
4847 /* Possible truncation here but in some 64-bit environments
4848 * the compiler gets heartburn about switch on 64-bit values.
4849 * A similar issue a little earlier when switching on value.
4851 switch ((I32)namedclass) {
4854 ANYOF_CLASS_SET(ret, ANYOF_ALNUM);
4856 for (value = 0; value < 256; value++)
4858 ANYOF_BITMAP_SET(ret, value);
4865 ANYOF_CLASS_SET(ret, ANYOF_NALNUM);
4867 for (value = 0; value < 256; value++)
4868 if (!isALNUM(value))
4869 ANYOF_BITMAP_SET(ret, value);
4876 ANYOF_CLASS_SET(ret, ANYOF_ALNUMC);
4878 for (value = 0; value < 256; value++)
4879 if (isALNUMC(value))
4880 ANYOF_BITMAP_SET(ret, value);
4887 ANYOF_CLASS_SET(ret, ANYOF_NALNUMC);
4889 for (value = 0; value < 256; value++)
4890 if (!isALNUMC(value))
4891 ANYOF_BITMAP_SET(ret, value);
4898 ANYOF_CLASS_SET(ret, ANYOF_ALPHA);
4900 for (value = 0; value < 256; value++)
4902 ANYOF_BITMAP_SET(ret, value);
4909 ANYOF_CLASS_SET(ret, ANYOF_NALPHA);
4911 for (value = 0; value < 256; value++)
4912 if (!isALPHA(value))
4913 ANYOF_BITMAP_SET(ret, value);
4920 ANYOF_CLASS_SET(ret, ANYOF_ASCII);
4923 for (value = 0; value < 128; value++)
4924 ANYOF_BITMAP_SET(ret, value);
4926 for (value = 0; value < 256; value++) {
4928 ANYOF_BITMAP_SET(ret, value);
4937 ANYOF_CLASS_SET(ret, ANYOF_NASCII);
4940 for (value = 128; value < 256; value++)
4941 ANYOF_BITMAP_SET(ret, value);
4943 for (value = 0; value < 256; value++) {
4944 if (!isASCII(value))
4945 ANYOF_BITMAP_SET(ret, value);
4954 ANYOF_CLASS_SET(ret, ANYOF_BLANK);
4956 for (value = 0; value < 256; value++)
4958 ANYOF_BITMAP_SET(ret, value);
4965 ANYOF_CLASS_SET(ret, ANYOF_NBLANK);
4967 for (value = 0; value < 256; value++)
4968 if (!isBLANK(value))
4969 ANYOF_BITMAP_SET(ret, value);
4976 ANYOF_CLASS_SET(ret, ANYOF_CNTRL);
4978 for (value = 0; value < 256; value++)
4980 ANYOF_BITMAP_SET(ret, value);
4987 ANYOF_CLASS_SET(ret, ANYOF_NCNTRL);
4989 for (value = 0; value < 256; value++)
4990 if (!isCNTRL(value))
4991 ANYOF_BITMAP_SET(ret, value);
4998 ANYOF_CLASS_SET(ret, ANYOF_DIGIT);
5000 /* consecutive digits assumed */
5001 for (value = '0'; value <= '9'; value++)
5002 ANYOF_BITMAP_SET(ret, value);
5009 ANYOF_CLASS_SET(ret, ANYOF_NDIGIT);
5011 /* consecutive digits assumed */
5012 for (value = 0; value < '0'; value++)
5013 ANYOF_BITMAP_SET(ret, value);
5014 for (value = '9' + 1; value < 256; value++)
5015 ANYOF_BITMAP_SET(ret, value);
5022 ANYOF_CLASS_SET(ret, ANYOF_GRAPH);
5024 for (value = 0; value < 256; value++)
5026 ANYOF_BITMAP_SET(ret, value);
5033 ANYOF_CLASS_SET(ret, ANYOF_NGRAPH);
5035 for (value = 0; value < 256; value++)
5036 if (!isGRAPH(value))
5037 ANYOF_BITMAP_SET(ret, value);
5044 ANYOF_CLASS_SET(ret, ANYOF_LOWER);
5046 for (value = 0; value < 256; value++)
5048 ANYOF_BITMAP_SET(ret, value);
5055 ANYOF_CLASS_SET(ret, ANYOF_NLOWER);
5057 for (value = 0; value < 256; value++)
5058 if (!isLOWER(value))
5059 ANYOF_BITMAP_SET(ret, value);
5066 ANYOF_CLASS_SET(ret, ANYOF_PRINT);
5068 for (value = 0; value < 256; value++)
5070 ANYOF_BITMAP_SET(ret, value);
5077 ANYOF_CLASS_SET(ret, ANYOF_NPRINT);
5079 for (value = 0; value < 256; value++)
5080 if (!isPRINT(value))
5081 ANYOF_BITMAP_SET(ret, value);
5088 ANYOF_CLASS_SET(ret, ANYOF_PSXSPC);
5090 for (value = 0; value < 256; value++)
5091 if (isPSXSPC(value))
5092 ANYOF_BITMAP_SET(ret, value);
5099 ANYOF_CLASS_SET(ret, ANYOF_NPSXSPC);
5101 for (value = 0; value < 256; value++)
5102 if (!isPSXSPC(value))
5103 ANYOF_BITMAP_SET(ret, value);
5110 ANYOF_CLASS_SET(ret, ANYOF_PUNCT);
5112 for (value = 0; value < 256; value++)
5114 ANYOF_BITMAP_SET(ret, value);
5121 ANYOF_CLASS_SET(ret, ANYOF_NPUNCT);
5123 for (value = 0; value < 256; value++)
5124 if (!isPUNCT(value))
5125 ANYOF_BITMAP_SET(ret, value);
5132 ANYOF_CLASS_SET(ret, ANYOF_SPACE);
5134 for (value = 0; value < 256; value++)
5136 ANYOF_BITMAP_SET(ret, value);
5143 ANYOF_CLASS_SET(ret, ANYOF_NSPACE);
5145 for (value = 0; value < 256; value++)
5146 if (!isSPACE(value))
5147 ANYOF_BITMAP_SET(ret, value);
5154 ANYOF_CLASS_SET(ret, ANYOF_UPPER);
5156 for (value = 0; value < 256; value++)
5158 ANYOF_BITMAP_SET(ret, value);
5165 ANYOF_CLASS_SET(ret, ANYOF_NUPPER);
5167 for (value = 0; value < 256; value++)
5168 if (!isUPPER(value))
5169 ANYOF_BITMAP_SET(ret, value);
5176 ANYOF_CLASS_SET(ret, ANYOF_XDIGIT);
5178 for (value = 0; value < 256; value++)
5179 if (isXDIGIT(value))
5180 ANYOF_BITMAP_SET(ret, value);
5187 ANYOF_CLASS_SET(ret, ANYOF_NXDIGIT);
5189 for (value = 0; value < 256; value++)
5190 if (!isXDIGIT(value))
5191 ANYOF_BITMAP_SET(ret, value);
5197 /* this is to handle \p and \P */
5200 vFAIL("Invalid [::] class");
5204 /* Strings such as "+utf8::isWord\n" */
5205 Perl_sv_catpvf(aTHX_ listsv, "%cutf8::Is%s\n", yesno, what);
5208 ANYOF_FLAGS(ret) |= ANYOF_CLASS;
5211 } /* end of namedclass \blah */
5214 if (prevvalue > (IV)value) /* b-a */ {
5215 const int w = RExC_parse - rangebegin;
5216 Simple_vFAIL4("Invalid [] range \"%*.*s\"", w, w, rangebegin);
5217 range = 0; /* not a valid range */
5221 prevvalue = value; /* save the beginning of the range */
5222 if (*RExC_parse == '-' && RExC_parse+1 < RExC_end &&
5223 RExC_parse[1] != ']') {
5226 /* a bad range like \w-, [:word:]- ? */
5227 if (namedclass > OOB_NAMEDCLASS) {
5228 if (ckWARN(WARN_REGEXP)) {
5230 RExC_parse >= rangebegin ?
5231 RExC_parse - rangebegin : 0;
5233 "False [] range \"%*.*s\"",
5237 ANYOF_BITMAP_SET(ret, '-');
5239 range = 1; /* yeah, it's a range! */
5240 continue; /* but do it the next time */
5244 /* now is the next time */
5248 if (prevvalue < 256) {
5249 const IV ceilvalue = value < 256 ? value : 255;
5252 /* In EBCDIC [\x89-\x91] should include
5253 * the \x8e but [i-j] should not. */
5254 if (literal_endpoint == 2 &&
5255 ((isLOWER(prevvalue) && isLOWER(ceilvalue)) ||
5256 (isUPPER(prevvalue) && isUPPER(ceilvalue))))
5258 if (isLOWER(prevvalue)) {
5259 for (i = prevvalue; i <= ceilvalue; i++)
5261 ANYOF_BITMAP_SET(ret, i);
5263 for (i = prevvalue; i <= ceilvalue; i++)
5265 ANYOF_BITMAP_SET(ret, i);
5270 for (i = prevvalue; i <= ceilvalue; i++)
5271 ANYOF_BITMAP_SET(ret, i);
5273 if (value > 255 || UTF) {
5274 const UV prevnatvalue = NATIVE_TO_UNI(prevvalue);
5275 const UV natvalue = NATIVE_TO_UNI(value);
5277 ANYOF_FLAGS(ret) |= ANYOF_UNICODE;
5278 if (prevnatvalue < natvalue) { /* what about > ? */
5279 Perl_sv_catpvf(aTHX_ listsv, "%04"UVxf"\t%04"UVxf"\n",
5280 prevnatvalue, natvalue);
5282 else if (prevnatvalue == natvalue) {
5283 Perl_sv_catpvf(aTHX_ listsv, "%04"UVxf"\n", natvalue);
5285 U8 foldbuf[UTF8_MAXBYTES_CASE+1];
5287 const UV f = to_uni_fold(natvalue, foldbuf, &foldlen);
5289 /* If folding and foldable and a single
5290 * character, insert also the folded version
5291 * to the charclass. */
5293 if (foldlen == (STRLEN)UNISKIP(f))
5294 Perl_sv_catpvf(aTHX_ listsv,
5297 /* Any multicharacter foldings
5298 * require the following transform:
5299 * [ABCDEF] -> (?:[ABCabcDEFd]|pq|rst)
5300 * where E folds into "pq" and F folds
5301 * into "rst", all other characters
5302 * fold to single characters. We save
5303 * away these multicharacter foldings,
5304 * to be later saved as part of the
5305 * additional "s" data. */
5308 if (!unicode_alternate)
5309 unicode_alternate = newAV();
5310 sv = newSVpvn((char*)foldbuf, foldlen);
5312 av_push(unicode_alternate, sv);
5316 /* If folding and the value is one of the Greek
5317 * sigmas insert a few more sigmas to make the
5318 * folding rules of the sigmas to work right.
5319 * Note that not all the possible combinations
5320 * are handled here: some of them are handled
5321 * by the standard folding rules, and some of
5322 * them (literal or EXACTF cases) are handled
5323 * during runtime in regexec.c:S_find_byclass(). */
5324 if (value == UNICODE_GREEK_SMALL_LETTER_FINAL_SIGMA) {
5325 Perl_sv_catpvf(aTHX_ listsv, "%04"UVxf"\n",
5326 (UV)UNICODE_GREEK_CAPITAL_LETTER_SIGMA);
5327 Perl_sv_catpvf(aTHX_ listsv, "%04"UVxf"\n",
5328 (UV)UNICODE_GREEK_SMALL_LETTER_SIGMA);
5330 else if (value == UNICODE_GREEK_CAPITAL_LETTER_SIGMA)
5331 Perl_sv_catpvf(aTHX_ listsv, "%04"UVxf"\n",
5332 (UV)UNICODE_GREEK_SMALL_LETTER_SIGMA);
5337 literal_endpoint = 0;
5341 range = 0; /* this range (if it was one) is done now */
5345 ANYOF_FLAGS(ret) |= ANYOF_LARGE;
5347 RExC_size += ANYOF_CLASS_ADD_SKIP;
5349 RExC_emit += ANYOF_CLASS_ADD_SKIP;
5352 /* optimize case-insensitive simple patterns (e.g. /[a-z]/i) */
5354 /* If the only flag is folding (plus possibly inversion). */
5355 ((ANYOF_FLAGS(ret) & (ANYOF_FLAGS_ALL ^ ANYOF_INVERT)) == ANYOF_FOLD)
5357 for (value = 0; value < 256; ++value) {
5358 if (ANYOF_BITMAP_TEST(ret, value)) {
5359 UV fold = PL_fold[value];
5362 ANYOF_BITMAP_SET(ret, fold);
5365 ANYOF_FLAGS(ret) &= ~ANYOF_FOLD;
5368 /* optimize inverted simple patterns (e.g. [^a-z]) */
5369 if (!SIZE_ONLY && optimize_invert &&
5370 /* If the only flag is inversion. */
5371 (ANYOF_FLAGS(ret) & ANYOF_FLAGS_ALL) == ANYOF_INVERT) {
5372 for (value = 0; value < ANYOF_BITMAP_SIZE; ++value)
5373 ANYOF_BITMAP(ret)[value] ^= ANYOF_FLAGS_ALL;
5374 ANYOF_FLAGS(ret) = ANYOF_UNICODE_ALL;
5378 AV * const av = newAV();
5381 /* The 0th element stores the character class description
5382 * in its textual form: used later (regexec.c:Perl_regclass_swash())
5383 * to initialize the appropriate swash (which gets stored in
5384 * the 1st element), and also useful for dumping the regnode.
5385 * The 2nd element stores the multicharacter foldings,
5386 * used later (regexec.c:S_reginclass()). */
5387 av_store(av, 0, listsv);
5388 av_store(av, 1, NULL);
5389 av_store(av, 2, (SV*)unicode_alternate);
5390 rv = newRV_noinc((SV*)av);
5391 n = add_data(pRExC_state, 1, "s");
5392 RExC_rx->data->data[n] = (void*)rv;
5400 S_nextchar(pTHX_ RExC_state_t *pRExC_state)
5402 char* const retval = RExC_parse++;
5405 if (*RExC_parse == '(' && RExC_parse[1] == '?' &&
5406 RExC_parse[2] == '#') {
5407 while (*RExC_parse != ')') {
5408 if (RExC_parse == RExC_end)
5409 FAIL("Sequence (?#... not terminated");
5415 if (RExC_flags & PMf_EXTENDED) {
5416 if (isSPACE(*RExC_parse)) {
5420 else if (*RExC_parse == '#') {
5421 while (RExC_parse < RExC_end)
5422 if (*RExC_parse++ == '\n') break;
5431 - reg_node - emit a node
5433 STATIC regnode * /* Location. */
5434 S_reg_node(pTHX_ RExC_state_t *pRExC_state, U8 op)
5437 register regnode *ptr;
5438 regnode * const ret = RExC_emit;
5441 SIZE_ALIGN(RExC_size);
5446 NODE_ALIGN_FILL(ret);
5448 FILL_ADVANCE_NODE(ptr, op);
5449 if (RExC_offsets) { /* MJD */
5450 MJD_OFFSET_DEBUG(("%s:%u: (op %s) %s %u <- %u (len %u) (max %u).\n",
5451 "reg_node", __LINE__,
5453 RExC_emit - RExC_emit_start > RExC_offsets[0]
5454 ? "Overwriting end of array!\n" : "OK",
5455 RExC_emit - RExC_emit_start,
5456 RExC_parse - RExC_start,
5458 Set_Node_Offset(RExC_emit, RExC_parse + (op == END));
5467 - reganode - emit a node with an argument
5469 STATIC regnode * /* Location. */
5470 S_reganode(pTHX_ RExC_state_t *pRExC_state, U8 op, U32 arg)
5473 register regnode *ptr;
5474 regnode * const ret = RExC_emit;
5477 SIZE_ALIGN(RExC_size);
5482 NODE_ALIGN_FILL(ret);
5484 FILL_ADVANCE_NODE_ARG(ptr, op, arg);
5485 if (RExC_offsets) { /* MJD */
5486 MJD_OFFSET_DEBUG(("%s(%d): (op %s) %s %u <- %u (max %u).\n",
5490 RExC_emit - RExC_emit_start > RExC_offsets[0] ?
5491 "Overwriting end of array!\n" : "OK",
5492 RExC_emit - RExC_emit_start,
5493 RExC_parse - RExC_start,
5495 Set_Cur_Node_Offset;
5504 - reguni - emit (if appropriate) a Unicode character
5507 S_reguni(pTHX_ const RExC_state_t *pRExC_state, UV uv, char* s, STRLEN* lenp)
5510 *lenp = SIZE_ONLY ? UNISKIP(uv) : (uvchr_to_utf8((U8*)s, uv) - (U8*)s);
5514 - reginsert - insert an operator in front of already-emitted operand
5516 * Means relocating the operand.
5519 S_reginsert(pTHX_ RExC_state_t *pRExC_state, U8 op, regnode *opnd)
5522 register regnode *src;
5523 register regnode *dst;
5524 register regnode *place;
5525 const int offset = regarglen[(U8)op];
5527 /* (PL_regkind[(U8)op] == CURLY ? EXTRA_STEP_2ARGS : 0); */
5530 RExC_size += NODE_STEP_REGNODE + offset;
5535 RExC_emit += NODE_STEP_REGNODE + offset;
5537 while (src > opnd) {
5538 StructCopy(--src, --dst, regnode);
5539 if (RExC_offsets) { /* MJD 20010112 */
5540 MJD_OFFSET_DEBUG(("%s(%d): (op %s) %s copy %u -> %u (max %u).\n",
5544 dst - RExC_emit_start > RExC_offsets[0]
5545 ? "Overwriting end of array!\n" : "OK",
5546 src - RExC_emit_start,
5547 dst - RExC_emit_start,
5549 Set_Node_Offset_To_R(dst-RExC_emit_start, Node_Offset(src));
5550 Set_Node_Length_To_R(dst-RExC_emit_start, Node_Length(src));
5555 place = opnd; /* Op node, where operand used to be. */
5556 if (RExC_offsets) { /* MJD */
5557 MJD_OFFSET_DEBUG(("%s(%d): (op %s) %s %u <- %u (max %u).\n",
5561 place - RExC_emit_start > RExC_offsets[0]
5562 ? "Overwriting end of array!\n" : "OK",
5563 place - RExC_emit_start,
5564 RExC_parse - RExC_start,
5566 Set_Node_Offset(place, RExC_parse);
5567 Set_Node_Length(place, 1);
5569 src = NEXTOPER(place);
5570 FILL_ADVANCE_NODE(place, op);
5571 Zero(src, offset, regnode);
5575 - regtail - set the next-pointer at the end of a node chain of p to val.
5577 /* TODO: All three parms should be const */
5579 S_regtail(pTHX_ const RExC_state_t *pRExC_state, regnode *p, const regnode *val)
5582 register regnode *scan;
5587 /* Find last node. */
5590 regnode * const temp = regnext(scan);
5596 if (reg_off_by_arg[OP(scan)]) {
5597 ARG_SET(scan, val - scan);
5600 NEXT_OFF(scan) = val - scan;
5605 - regoptail - regtail on operand of first argument; nop if operandless
5607 /* TODO: All three parms should be const */
5609 S_regoptail(pTHX_ const RExC_state_t *pRExC_state, regnode *p, const regnode *val)
5612 /* "Operandless" and "op != BRANCH" are synonymous in practice. */
5613 if (p == NULL || SIZE_ONLY)
5615 if (PL_regkind[(U8)OP(p)] == BRANCH) {
5616 regtail(pRExC_state, NEXTOPER(p), val);
5618 else if ( PL_regkind[(U8)OP(p)] == BRANCHJ) {
5619 regtail(pRExC_state, NEXTOPER(NEXTOPER(p)), val);
5626 - regcurly - a little FSA that accepts {\d+,?\d*}
5629 S_regcurly(register const char *s)
5648 - regdump - dump a regexp onto Perl_debug_log in vaguely comprehensible form
5651 Perl_regdump(pTHX_ const regexp *r)
5655 SV * const sv = sv_newmortal();
5657 (void)dumpuntil(r, r->program, r->program + 1, NULL, sv, 0);
5659 /* Header fields of interest. */
5660 if (r->anchored_substr)
5661 PerlIO_printf(Perl_debug_log,
5662 "anchored \"%s%.*s%s\"%s at %"IVdf" ",
5664 (int)(SvCUR(r->anchored_substr) - (SvTAIL(r->anchored_substr)!=0)),
5665 SvPVX_const(r->anchored_substr),
5667 SvTAIL(r->anchored_substr) ? "$" : "",
5668 (IV)r->anchored_offset);
5669 else if (r->anchored_utf8)
5670 PerlIO_printf(Perl_debug_log,
5671 "anchored utf8 \"%s%.*s%s\"%s at %"IVdf" ",
5673 (int)(SvCUR(r->anchored_utf8) - (SvTAIL(r->anchored_utf8)!=0)),
5674 SvPVX_const(r->anchored_utf8),
5676 SvTAIL(r->anchored_utf8) ? "$" : "",
5677 (IV)r->anchored_offset);
5678 if (r->float_substr)
5679 PerlIO_printf(Perl_debug_log,
5680 "floating \"%s%.*s%s\"%s at %"IVdf"..%"UVuf" ",
5682 (int)(SvCUR(r->float_substr) - (SvTAIL(r->float_substr)!=0)),
5683 SvPVX_const(r->float_substr),
5685 SvTAIL(r->float_substr) ? "$" : "",
5686 (IV)r->float_min_offset, (UV)r->float_max_offset);
5687 else if (r->float_utf8)
5688 PerlIO_printf(Perl_debug_log,
5689 "floating utf8 \"%s%.*s%s\"%s at %"IVdf"..%"UVuf" ",
5691 (int)(SvCUR(r->float_utf8) - (SvTAIL(r->float_utf8)!=0)),
5692 SvPVX_const(r->float_utf8),
5694 SvTAIL(r->float_utf8) ? "$" : "",
5695 (IV)r->float_min_offset, (UV)r->float_max_offset);
5696 if (r->check_substr || r->check_utf8)
5697 PerlIO_printf(Perl_debug_log,
5698 r->check_substr == r->float_substr
5699 && r->check_utf8 == r->float_utf8
5700 ? "(checking floating" : "(checking anchored");
5701 if (r->reganch & ROPT_NOSCAN)
5702 PerlIO_printf(Perl_debug_log, " noscan");
5703 if (r->reganch & ROPT_CHECK_ALL)
5704 PerlIO_printf(Perl_debug_log, " isall");
5705 if (r->check_substr || r->check_utf8)
5706 PerlIO_printf(Perl_debug_log, ") ");
5708 if (r->regstclass) {
5709 regprop(r, sv, r->regstclass);
5710 PerlIO_printf(Perl_debug_log, "stclass \"%s\" ", SvPVX_const(sv));
5712 if (r->reganch & ROPT_ANCH) {
5713 PerlIO_printf(Perl_debug_log, "anchored");
5714 if (r->reganch & ROPT_ANCH_BOL)
5715 PerlIO_printf(Perl_debug_log, "(BOL)");
5716 if (r->reganch & ROPT_ANCH_MBOL)
5717 PerlIO_printf(Perl_debug_log, "(MBOL)");
5718 if (r->reganch & ROPT_ANCH_SBOL)
5719 PerlIO_printf(Perl_debug_log, "(SBOL)");
5720 if (r->reganch & ROPT_ANCH_GPOS)
5721 PerlIO_printf(Perl_debug_log, "(GPOS)");
5722 PerlIO_putc(Perl_debug_log, ' ');
5724 if (r->reganch & ROPT_GPOS_SEEN)
5725 PerlIO_printf(Perl_debug_log, "GPOS ");
5726 if (r->reganch & ROPT_SKIP)
5727 PerlIO_printf(Perl_debug_log, "plus ");
5728 if (r->reganch & ROPT_IMPLICIT)
5729 PerlIO_printf(Perl_debug_log, "implicit ");
5730 PerlIO_printf(Perl_debug_log, "minlen %ld ", (long) r->minlen);
5731 if (r->reganch & ROPT_EVAL_SEEN)
5732 PerlIO_printf(Perl_debug_log, "with eval ");
5733 PerlIO_printf(Perl_debug_log, "\n");
5735 const U32 len = r->offsets[0];
5736 GET_RE_DEBUG_FLAGS_DECL;
5739 PerlIO_printf(Perl_debug_log, "Offsets: [%"UVuf"]\n\t", (UV)r->offsets[0]);
5740 for (i = 1; i <= len; i++)
5741 PerlIO_printf(Perl_debug_log, "%"UVuf"[%"UVuf"] ",
5742 (UV)r->offsets[i*2-1], (UV)r->offsets[i*2]);
5743 PerlIO_printf(Perl_debug_log, "\n");
5747 PERL_UNUSED_CONTEXT;
5749 #endif /* DEBUGGING */
5753 - regprop - printable representation of opcode
5756 Perl_regprop(pTHX_ const regexp *prog, SV *sv, const regnode *o)
5762 sv_setpvn(sv, "", 0);
5763 if (OP(o) >= reg_num) /* regnode.type is unsigned */
5764 /* It would be nice to FAIL() here, but this may be called from
5765 regexec.c, and it would be hard to supply pRExC_state. */
5766 Perl_croak(aTHX_ "Corrupted regexp opcode");
5767 sv_catpv(sv, reg_name[OP(o)]); /* Take off const! */
5769 k = PL_regkind[(U8)OP(o)];
5772 SV * const dsv = sv_2mortal(newSVpvs(""));
5773 /* Using is_utf8_string() is a crude hack but it may
5774 * be the best for now since we have no flag "this EXACTish
5775 * node was UTF-8" --jhi */
5776 const bool do_utf8 = is_utf8_string((U8*)STRING(o), STR_LEN(o));
5777 const char * const s = do_utf8 ?
5778 pv_uni_display(dsv, (U8*)STRING(o), STR_LEN(o), 60,
5779 UNI_DISPLAY_REGEX) :
5781 const int len = do_utf8 ?
5784 Perl_sv_catpvf(aTHX_ sv, " <%s%.*s%s>",
5788 } else if (k == TRIE) {
5790 /* print the details od the trie in dumpuntil instead, as
5791 * prog->data isn't available here */
5792 } else if (k == CURLY) {
5793 if (OP(o) == CURLYM || OP(o) == CURLYN || OP(o) == CURLYX)
5794 Perl_sv_catpvf(aTHX_ sv, "[%d]", o->flags); /* Parenth number */
5795 Perl_sv_catpvf(aTHX_ sv, " {%d,%d}", ARG1(o), ARG2(o));
5797 else if (k == WHILEM && o->flags) /* Ordinal/of */
5798 Perl_sv_catpvf(aTHX_ sv, "[%d/%d]", o->flags & 0xf, o->flags>>4);
5799 else if (k == REF || k == OPEN || k == CLOSE || k == GROUPP )
5800 Perl_sv_catpvf(aTHX_ sv, "%d", (int)ARG(o)); /* Parenth number */
5801 else if (k == LOGICAL)
5802 Perl_sv_catpvf(aTHX_ sv, "[%d]", o->flags); /* 2: embedded, otherwise 1 */
5803 else if (k == ANYOF) {
5804 int i, rangestart = -1;
5805 const U8 flags = ANYOF_FLAGS(o);
5807 /* Should be synchronized with * ANYOF_ #xdefines in regcomp.h */
5808 static const char * const anyofs[] = {
5841 if (flags & ANYOF_LOCALE)
5842 sv_catpvs(sv, "{loc}");
5843 if (flags & ANYOF_FOLD)
5844 sv_catpvs(sv, "{i}");
5845 Perl_sv_catpvf(aTHX_ sv, "[%s", PL_colors[0]);
5846 if (flags & ANYOF_INVERT)
5848 for (i = 0; i <= 256; i++) {
5849 if (i < 256 && ANYOF_BITMAP_TEST(o,i)) {
5850 if (rangestart == -1)
5852 } else if (rangestart != -1) {
5853 if (i <= rangestart + 3)
5854 for (; rangestart < i; rangestart++)
5855 put_byte(sv, rangestart);
5857 put_byte(sv, rangestart);
5859 put_byte(sv, i - 1);
5865 if (o->flags & ANYOF_CLASS)
5866 for (i = 0; i < (int)(sizeof(anyofs)/sizeof(char*)); i++)
5867 if (ANYOF_CLASS_TEST(o,i))
5868 sv_catpv(sv, anyofs[i]);
5870 if (flags & ANYOF_UNICODE)
5871 sv_catpvs(sv, "{unicode}");
5872 else if (flags & ANYOF_UNICODE_ALL)
5873 sv_catpvs(sv, "{unicode_all}");
5877 SV * const sw = regclass_swash(prog, o, FALSE, &lv, 0);
5881 U8 s[UTF8_MAXBYTES_CASE+1];
5883 for (i = 0; i <= 256; i++) { /* just the first 256 */
5884 uvchr_to_utf8(s, i);
5886 if (i < 256 && swash_fetch(sw, s, TRUE)) {
5887 if (rangestart == -1)
5889 } else if (rangestart != -1) {
5890 if (i <= rangestart + 3)
5891 for (; rangestart < i; rangestart++) {
5892 const U8 * const e = uvchr_to_utf8(s,rangestart);
5894 for(p = s; p < e; p++)
5898 const U8 *e = uvchr_to_utf8(s,rangestart);
5900 for (p = s; p < e; p++)
5903 e = uvchr_to_utf8(s, i-1);
5904 for (p = s; p < e; p++)
5911 sv_catpvs(sv, "..."); /* et cetera */
5915 char *s = savesvpv(lv);
5916 char * const origs = s;
5918 while(*s && *s != '\n') s++;
5921 const char * const t = ++s;
5939 Perl_sv_catpvf(aTHX_ sv, "%s]", PL_colors[1]);
5941 else if (k == BRANCHJ && (OP(o) == UNLESSM || OP(o) == IFMATCH))
5942 Perl_sv_catpvf(aTHX_ sv, "[-%d]", o->flags);
5944 PERL_UNUSED_CONTEXT;
5945 PERL_UNUSED_ARG(sv);
5947 #endif /* DEBUGGING */
5951 Perl_re_intuit_string(pTHX_ regexp *prog)
5952 { /* Assume that RE_INTUIT is set */
5954 GET_RE_DEBUG_FLAGS_DECL;
5955 PERL_UNUSED_CONTEXT;
5959 const char * const s = SvPV_nolen_const(prog->check_substr
5960 ? prog->check_substr : prog->check_utf8);
5962 if (!PL_colorset) reginitcolors();
5963 PerlIO_printf(Perl_debug_log,
5964 "%sUsing REx %ssubstr:%s \"%s%.60s%s%s\"\n",
5966 prog->check_substr ? "" : "utf8 ",
5967 PL_colors[5],PL_colors[0],
5970 (strlen(s) > 60 ? "..." : ""));
5973 return prog->check_substr ? prog->check_substr : prog->check_utf8;
5977 Perl_pregfree(pTHX_ struct regexp *r)
5981 SV * const dsv = PERL_DEBUG_PAD_ZERO(0);
5983 GET_RE_DEBUG_FLAGS_DECL;
5985 if (!r || (--r->refcnt > 0))
5987 DEBUG_r(if (re_debug_flags && (SvIV(re_debug_flags) & RE_DEBUG_COMPILE)) {
5988 const char * const s = (r->reganch & ROPT_UTF8)
5989 ? pv_uni_display(dsv, (U8*)r->precomp, r->prelen, 60, UNI_DISPLAY_REGEX)
5990 : pv_display(dsv, r->precomp, r->prelen, 0, 60);
5991 const int len = SvCUR(dsv);
5994 PerlIO_printf(Perl_debug_log,
5995 "%sFreeing REx:%s %s%*.*s%s%s\n",
5996 PL_colors[4],PL_colors[5],PL_colors[0],
5999 len > 60 ? "..." : "");
6002 /* gcov results gave these as non-null 100% of the time, so there's no
6003 optimisation in checking them before calling Safefree */
6004 Safefree(r->precomp);
6005 Safefree(r->offsets); /* 20010421 MJD */
6006 RX_MATCH_COPY_FREE(r);
6007 #ifdef PERL_OLD_COPY_ON_WRITE
6009 SvREFCNT_dec(r->saved_copy);
6012 if (r->anchored_substr)
6013 SvREFCNT_dec(r->anchored_substr);
6014 if (r->anchored_utf8)
6015 SvREFCNT_dec(r->anchored_utf8);
6016 if (r->float_substr)
6017 SvREFCNT_dec(r->float_substr);
6019 SvREFCNT_dec(r->float_utf8);
6020 Safefree(r->substrs);
6023 int n = r->data->count;
6024 PAD* new_comppad = NULL;
6029 /* If you add a ->what type here, update the comment in regcomp.h */
6030 switch (r->data->what[n]) {
6032 SvREFCNT_dec((SV*)r->data->data[n]);
6035 Safefree(r->data->data[n]);
6038 new_comppad = (AV*)r->data->data[n];
6041 if (new_comppad == NULL)
6042 Perl_croak(aTHX_ "panic: pregfree comppad");
6043 PAD_SAVE_LOCAL(old_comppad,
6044 /* Watch out for global destruction's random ordering. */
6045 (SvTYPE(new_comppad) == SVt_PVAV) ? new_comppad : NULL
6048 refcnt = OpREFCNT_dec((OP_4tree*)r->data->data[n]);
6051 op_free((OP_4tree*)r->data->data[n]);
6053 PAD_RESTORE_LOCAL(old_comppad);
6054 SvREFCNT_dec((SV*)new_comppad);
6061 reg_trie_data * const trie=(reg_trie_data*)r->data->data[n];
6064 refcount = --trie->refcount;
6067 Safefree(trie->charmap);
6068 if (trie->widecharmap)
6069 SvREFCNT_dec((SV*)trie->widecharmap);
6070 Safefree(trie->states);
6071 Safefree(trie->trans);
6074 SvREFCNT_dec((SV*)trie->words);
6075 if (trie->revcharmap)
6076 SvREFCNT_dec((SV*)trie->revcharmap);
6078 Safefree(r->data->data[n]); /* do this last!!!! */
6083 Perl_croak(aTHX_ "panic: regfree data code '%c'", r->data->what[n]);
6086 Safefree(r->data->what);
6089 Safefree(r->startp);
6094 #ifndef PERL_IN_XSUB_RE
6096 - regnext - dig the "next" pointer out of a node
6099 Perl_regnext(pTHX_ register regnode *p)
6102 register I32 offset;
6104 if (p == &PL_regdummy)
6107 offset = (reg_off_by_arg[OP(p)] ? ARG(p) : NEXT_OFF(p));
6116 S_re_croak2(pTHX_ const char* pat1,const char* pat2,...)
6119 STRLEN l1 = strlen(pat1);
6120 STRLEN l2 = strlen(pat2);
6123 const char *message;
6129 Copy(pat1, buf, l1 , char);
6130 Copy(pat2, buf + l1, l2 , char);
6131 buf[l1 + l2] = '\n';
6132 buf[l1 + l2 + 1] = '\0';
6134 /* ANSI variant takes additional second argument */
6135 va_start(args, pat2);
6139 msv = vmess(buf, &args);
6141 message = SvPV_const(msv,l1);
6144 Copy(message, buf, l1 , char);
6145 buf[l1-1] = '\0'; /* Overwrite \n */
6146 Perl_croak(aTHX_ "%s", buf);
6149 /* XXX Here's a total kludge. But we need to re-enter for swash routines. */
6151 #ifndef PERL_IN_XSUB_RE
6153 Perl_save_re_context(pTHX)
6157 struct re_save_state *state;
6159 SAVEVPTR(PL_curcop);
6160 SSGROW(SAVESTACK_ALLOC_FOR_RE_SAVE_STATE + 1);
6162 state = (struct re_save_state *)(PL_savestack + PL_savestack_ix);
6163 PL_savestack_ix += SAVESTACK_ALLOC_FOR_RE_SAVE_STATE;
6164 SSPUSHINT(SAVEt_RE_STATE);
6166 Copy(&PL_reg_state, state, 1, struct re_save_state);
6168 PL_reg_start_tmp = 0;
6169 PL_reg_start_tmpl = 0;
6170 PL_reg_oldsaved = NULL;
6171 PL_reg_oldsavedlen = 0;
6173 PL_reg_leftiter = 0;
6174 PL_reg_poscache = NULL;
6175 PL_reg_poscache_size = 0;
6176 #ifdef PERL_OLD_COPY_ON_WRITE
6180 /* Save $1..$n (#18107: UTF-8 s/(\w+)/uc($1)/e); AMS 20021106. */
6182 const REGEXP * const rx = PM_GETRE(PL_curpm);
6185 for (i = 1; i <= rx->nparens; i++) {
6186 char digits[TYPE_CHARS(long)];
6188 const STRLEN len = snprintf(digits, sizeof(digits), "%lu", (long)i);
6190 const STRLEN len = my_sprintf(digits, "%lu", (long)i);
6191 #endif /* #ifdef USE_SNPRINTF */
6192 GV *const *const gvp
6193 = (GV**)hv_fetch(PL_defstash, digits, len, 0);
6196 GV * const gv = *gvp;
6197 if (SvTYPE(gv) == SVt_PVGV && GvSV(gv))
6207 clear_re(pTHX_ void *r)
6210 ReREFCNT_dec((regexp *)r);
6216 S_put_byte(pTHX_ SV *sv, int c)
6218 if (isCNTRL(c) || c == 255 || !isPRINT(c))
6219 Perl_sv_catpvf(aTHX_ sv, "\\%o", c);
6220 else if (c == '-' || c == ']' || c == '\\' || c == '^')
6221 Perl_sv_catpvf(aTHX_ sv, "\\%c", c);
6223 Perl_sv_catpvf(aTHX_ sv, "%c", c);
6227 STATIC const regnode *
6228 S_dumpuntil(pTHX_ const regexp *r, const regnode *start, const regnode *node,
6229 const regnode *last, SV* sv, I32 l)
6232 register U8 op = EXACT; /* Arbitrary non-END op. */
6233 register const regnode *next;
6235 while (op != END && (!last || node < last)) {
6236 /* While that wasn't END last time... */
6242 next = regnext((regnode *)node);
6244 if (OP(node) == OPTIMIZED)
6246 regprop(r, sv, node);
6247 PerlIO_printf(Perl_debug_log, "%4"IVdf":%*s%s", (IV)(node - start),
6248 (int)(2*l + 1), "", SvPVX_const(sv));
6249 if (next == NULL) /* Next ptr. */
6250 PerlIO_printf(Perl_debug_log, "(0)");
6252 PerlIO_printf(Perl_debug_log, "(%"IVdf")", (IV)(next - start));
6253 (void)PerlIO_putc(Perl_debug_log, '\n');
6255 if (PL_regkind[(U8)op] == BRANCHJ) {
6256 register const regnode *nnode = (OP(next) == LONGJMP
6257 ? regnext((regnode *)next)
6259 if (last && nnode > last)
6261 node = dumpuntil(r, start, NEXTOPER(NEXTOPER(node)), nnode, sv, l + 1);
6263 else if (PL_regkind[(U8)op] == BRANCH) {
6264 node = dumpuntil(r, start, NEXTOPER(node), next, sv, l + 1);
6266 else if ( PL_regkind[(U8)op] == TRIE ) {
6267 const I32 n = ARG(node);
6268 const reg_trie_data * const trie = (reg_trie_data*)r->data->data[n];
6269 const I32 arry_len = av_len(trie->words)+1;
6271 PerlIO_printf(Perl_debug_log,
6272 "%*s[Words:%d Chars Stored:%d Unique Chars:%d States:%"IVdf"%s]\n",
6276 (int)trie->charcount,
6277 trie->uniquecharcount,
6278 (IV)trie->laststate-1,
6279 node->flags ? " EVAL mode" : "");
6281 for (word_idx=0; word_idx < arry_len; word_idx++) {
6282 SV ** const elem_ptr = av_fetch(trie->words,word_idx,0);
6284 PerlIO_printf(Perl_debug_log, "%*s<%s%s%s>\n",
6287 SvPV_nolen_const(*elem_ptr),
6292 PerlIO_printf(Perl_debug_log, "(0)\n");
6294 PerlIO_printf(Perl_debug_log, "(%"IVdf")\n", (IV)(next - start));
6300 node = NEXTOPER(node);
6301 node += regarglen[(U8)op];
6304 else if ( op == CURLY) { /* "next" might be very big: optimizer */
6305 node = dumpuntil(r, start, NEXTOPER(node) + EXTRA_STEP_2ARGS,
6306 NEXTOPER(node) + EXTRA_STEP_2ARGS + 1, sv, l + 1);
6308 else if (PL_regkind[(U8)op] == CURLY && op != CURLYX) {
6309 node = dumpuntil(r, start, NEXTOPER(node) + EXTRA_STEP_2ARGS,
6312 else if ( op == PLUS || op == STAR) {
6313 node = dumpuntil(r, start, NEXTOPER(node), NEXTOPER(node) + 1, sv, l + 1);
6315 else if (op == ANYOF) {
6316 /* arglen 1 + class block */
6317 node += 1 + ((ANYOF_FLAGS(node) & ANYOF_LARGE)
6318 ? ANYOF_CLASS_SKIP : ANYOF_SKIP);
6319 node = NEXTOPER(node);
6321 else if (PL_regkind[(U8)op] == EXACT) {
6322 /* Literal string, where present. */
6323 node += NODE_SZ_STR(node) - 1;
6324 node = NEXTOPER(node);
6327 node = NEXTOPER(node);
6328 node += regarglen[(U8)op];
6330 if (op == CURLYX || op == OPEN)
6332 else if (op == WHILEM)
6338 #endif /* DEBUGGING */
6342 * c-indentation-style: bsd
6344 * indent-tabs-mode: t
6347 * ex: set ts=8 sts=4 sw=4 noet: