5 * 'A fair jaw-cracker dwarf-language must be.' --Samwise Gamgee
7 * [p.285 of _The Lord of the Rings_, II/iii: "The Ring Goes South"]
10 /* This file contains functions for compiling a regular expression. See
11 * also regexec.c which funnily enough, contains functions for executing
12 * a regular expression.
14 * This file is also copied at build time to ext/re/re_comp.c, where
15 * it's built with -DPERL_EXT_RE_BUILD -DPERL_EXT_RE_DEBUG -DPERL_EXT.
16 * This causes the main functions to be compiled under new names and with
17 * debugging support added, which makes "use re 'debug'" work.
20 /* NOTE: this is derived from Henry Spencer's regexp code, and should not
21 * confused with the original package (see point 3 below). Thanks, Henry!
24 /* Additional note: this code is very heavily munged from Henry's version
25 * in places. In some spots I've traded clarity for efficiency, so don't
26 * blame Henry for some of the lack of readability.
29 /* The names of the functions have been changed from regcomp and
30 * regexec to pregcomp and pregexec in order to avoid conflicts
31 * with the POSIX routines of the same names.
34 #ifdef PERL_EXT_RE_BUILD
39 * pregcomp and pregexec -- regsub and regerror are not used in perl
41 * Copyright (c) 1986 by University of Toronto.
42 * Written by Henry Spencer. Not derived from licensed software.
44 * Permission is granted to anyone to use this software for any
45 * purpose on any computer system, and to redistribute it freely,
46 * subject to the following restrictions:
48 * 1. The author is not responsible for the consequences of use of
49 * this software, no matter how awful, even if they arise
52 * 2. The origin of this software must not be misrepresented, either
53 * by explicit claim or by omission.
55 * 3. Altered versions must be plainly marked as such, and must not
56 * be misrepresented as being the original software.
59 **** Alterations to Henry's code are...
61 **** Copyright (C) 1991, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999,
62 **** 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008
63 **** by Larry Wall and others
65 **** You may distribute under the terms of either the GNU General Public
66 **** License or the Artistic License, as specified in the README file.
69 * Beware that some of this code is subtly aware of the way operator
70 * precedence is structured in regular expressions. Serious changes in
71 * regular-expression syntax might require a total rethink.
74 #define PERL_IN_REGCOMP_C
77 #ifndef PERL_IN_XSUB_RE
82 #ifdef PERL_IN_XSUB_RE
84 extern const struct regexp_engine my_reg_engine;
89 #include "dquote_static.c"
90 #include "charclass_invlists.h"
91 #include "inline_invlist.c"
92 #include "unicode_constants.h"
94 #define HAS_NONLATIN1_FOLD_CLOSURE(i) _HAS_NONLATIN1_FOLD_CLOSURE_ONLY_FOR_USE_BY_REGCOMP_DOT_C_AND_REGEXEC_DOT_C(i)
95 #define IS_NON_FINAL_FOLD(c) _IS_NON_FINAL_FOLD_ONLY_FOR_USE_BY_REGCOMP_DOT_C(c)
96 #define IS_IN_SOME_FOLD_L1(c) _IS_IN_SOME_FOLD_ONLY_FOR_USE_BY_REGCOMP_DOT_C(c)
103 # if defined(BUGGY_MSC6)
104 /* MSC 6.00A breaks on op/regexp.t test 85 unless we turn this off */
105 # pragma optimize("a",off)
106 /* But MSC 6.00A is happy with 'w', for aliases only across function calls*/
107 # pragma optimize("w",on )
108 # endif /* BUGGY_MSC6 */
112 #define STATIC static
116 typedef struct RExC_state_t {
117 U32 flags; /* RXf_* are we folding, multilining? */
118 U32 pm_flags; /* PMf_* stuff from the calling PMOP */
119 char *precomp; /* uncompiled string. */
120 REGEXP *rx_sv; /* The SV that is the regexp. */
121 regexp *rx; /* perl core regexp structure */
122 regexp_internal *rxi; /* internal data for regexp object pprivate field */
123 char *start; /* Start of input for compile */
124 char *end; /* End of input for compile */
125 char *parse; /* Input-scan pointer. */
126 I32 whilem_seen; /* number of WHILEM in this expr */
127 regnode *emit_start; /* Start of emitted-code area */
128 regnode *emit_bound; /* First regnode outside of the allocated space */
129 regnode *emit; /* Code-emit pointer; ®dummy = don't = compiling */
130 I32 naughty; /* How bad is this pattern? */
131 I32 sawback; /* Did we see \1, ...? */
133 I32 size; /* Code size. */
134 I32 npar; /* Capture buffer count, (OPEN). */
135 I32 cpar; /* Capture buffer count, (CLOSE). */
136 I32 nestroot; /* root parens we are in - used by accept */
139 regnode **open_parens; /* pointers to open parens */
140 regnode **close_parens; /* pointers to close parens */
141 regnode *opend; /* END node in program */
142 I32 utf8; /* whether the pattern is utf8 or not */
143 I32 orig_utf8; /* whether the pattern was originally in utf8 */
144 /* XXX use this for future optimisation of case
145 * where pattern must be upgraded to utf8. */
146 I32 uni_semantics; /* If a d charset modifier should use unicode
147 rules, even if the pattern is not in
149 HV *paren_names; /* Paren names */
151 regnode **recurse; /* Recurse regops */
152 I32 recurse_count; /* Number of recurse regops */
155 I32 override_recoding;
156 I32 in_multi_char_class;
157 struct reg_code_block *code_blocks; /* positions of literal (?{})
159 int num_code_blocks; /* size of code_blocks[] */
160 int code_index; /* next code_blocks[] slot */
162 char *starttry; /* -Dr: where regtry was called. */
163 #define RExC_starttry (pRExC_state->starttry)
165 SV *runtime_code_qr; /* qr with the runtime code blocks */
167 const char *lastparse;
169 AV *paren_name_list; /* idx -> name */
170 #define RExC_lastparse (pRExC_state->lastparse)
171 #define RExC_lastnum (pRExC_state->lastnum)
172 #define RExC_paren_name_list (pRExC_state->paren_name_list)
176 #define RExC_flags (pRExC_state->flags)
177 #define RExC_pm_flags (pRExC_state->pm_flags)
178 #define RExC_precomp (pRExC_state->precomp)
179 #define RExC_rx_sv (pRExC_state->rx_sv)
180 #define RExC_rx (pRExC_state->rx)
181 #define RExC_rxi (pRExC_state->rxi)
182 #define RExC_start (pRExC_state->start)
183 #define RExC_end (pRExC_state->end)
184 #define RExC_parse (pRExC_state->parse)
185 #define RExC_whilem_seen (pRExC_state->whilem_seen)
186 #ifdef RE_TRACK_PATTERN_OFFSETS
187 #define RExC_offsets (pRExC_state->rxi->u.offsets) /* I am not like the others */
189 #define RExC_emit (pRExC_state->emit)
190 #define RExC_emit_start (pRExC_state->emit_start)
191 #define RExC_emit_bound (pRExC_state->emit_bound)
192 #define RExC_naughty (pRExC_state->naughty)
193 #define RExC_sawback (pRExC_state->sawback)
194 #define RExC_seen (pRExC_state->seen)
195 #define RExC_size (pRExC_state->size)
196 #define RExC_npar (pRExC_state->npar)
197 #define RExC_nestroot (pRExC_state->nestroot)
198 #define RExC_extralen (pRExC_state->extralen)
199 #define RExC_seen_zerolen (pRExC_state->seen_zerolen)
200 #define RExC_utf8 (pRExC_state->utf8)
201 #define RExC_uni_semantics (pRExC_state->uni_semantics)
202 #define RExC_orig_utf8 (pRExC_state->orig_utf8)
203 #define RExC_open_parens (pRExC_state->open_parens)
204 #define RExC_close_parens (pRExC_state->close_parens)
205 #define RExC_opend (pRExC_state->opend)
206 #define RExC_paren_names (pRExC_state->paren_names)
207 #define RExC_recurse (pRExC_state->recurse)
208 #define RExC_recurse_count (pRExC_state->recurse_count)
209 #define RExC_in_lookbehind (pRExC_state->in_lookbehind)
210 #define RExC_contains_locale (pRExC_state->contains_locale)
211 #define RExC_override_recoding (pRExC_state->override_recoding)
212 #define RExC_in_multi_char_class (pRExC_state->in_multi_char_class)
215 #define ISMULT1(c) ((c) == '*' || (c) == '+' || (c) == '?')
216 #define ISMULT2(s) ((*s) == '*' || (*s) == '+' || (*s) == '?' || \
217 ((*s) == '{' && regcurly(s, FALSE)))
220 #undef SPSTART /* dratted cpp namespace... */
223 * Flags to be passed up and down.
225 #define WORST 0 /* Worst case. */
226 #define HASWIDTH 0x01 /* Known to match non-null strings. */
228 /* Simple enough to be STAR/PLUS operand; in an EXACTish node must be a single
229 * character. (There needs to be a case: in the switch statement in regexec.c
230 * for any node marked SIMPLE.) Note that this is not the same thing as
233 #define SPSTART 0x04 /* Starts with * or + */
234 #define POSTPONED 0x08 /* (?1),(?&name), (??{...}) or similar */
235 #define TRYAGAIN 0x10 /* Weeded out a declaration. */
236 #define RESTART_UTF8 0x20 /* Restart, need to calcuate sizes as UTF-8 */
238 #define REG_NODE_NUM(x) ((x) ? (int)((x)-RExC_emit_start) : -1)
240 /* whether trie related optimizations are enabled */
241 #if PERL_ENABLE_EXTENDED_TRIE_OPTIMISATION
242 #define TRIE_STUDY_OPT
243 #define FULL_TRIE_STUDY
249 #define PBYTE(u8str,paren) ((U8*)(u8str))[(paren) >> 3]
250 #define PBITVAL(paren) (1 << ((paren) & 7))
251 #define PAREN_TEST(u8str,paren) ( PBYTE(u8str,paren) & PBITVAL(paren))
252 #define PAREN_SET(u8str,paren) PBYTE(u8str,paren) |= PBITVAL(paren)
253 #define PAREN_UNSET(u8str,paren) PBYTE(u8str,paren) &= (~PBITVAL(paren))
255 #define REQUIRE_UTF8 STMT_START { \
257 *flagp = RESTART_UTF8; \
262 /* This converts the named class defined in regcomp.h to its equivalent class
263 * number defined in handy.h. */
264 #define namedclass_to_classnum(class) ((int) ((class) / 2))
265 #define classnum_to_namedclass(classnum) ((classnum) * 2)
267 /* About scan_data_t.
269 During optimisation we recurse through the regexp program performing
270 various inplace (keyhole style) optimisations. In addition study_chunk
271 and scan_commit populate this data structure with information about
272 what strings MUST appear in the pattern. We look for the longest
273 string that must appear at a fixed location, and we look for the
274 longest string that may appear at a floating location. So for instance
279 Both 'FOO' and 'A' are fixed strings. Both 'B' and 'BAR' are floating
280 strings (because they follow a .* construct). study_chunk will identify
281 both FOO and BAR as being the longest fixed and floating strings respectively.
283 The strings can be composites, for instance
287 will result in a composite fixed substring 'foo'.
289 For each string some basic information is maintained:
291 - offset or min_offset
292 This is the position the string must appear at, or not before.
293 It also implicitly (when combined with minlenp) tells us how many
294 characters must match before the string we are searching for.
295 Likewise when combined with minlenp and the length of the string it
296 tells us how many characters must appear after the string we have
300 Only used for floating strings. This is the rightmost point that
301 the string can appear at. If set to I32 max it indicates that the
302 string can occur infinitely far to the right.
305 A pointer to the minimum number of characters of the pattern that the
306 string was found inside. This is important as in the case of positive
307 lookahead or positive lookbehind we can have multiple patterns
312 The minimum length of the pattern overall is 3, the minimum length
313 of the lookahead part is 3, but the minimum length of the part that
314 will actually match is 1. So 'FOO's minimum length is 3, but the
315 minimum length for the F is 1. This is important as the minimum length
316 is used to determine offsets in front of and behind the string being
317 looked for. Since strings can be composites this is the length of the
318 pattern at the time it was committed with a scan_commit. Note that
319 the length is calculated by study_chunk, so that the minimum lengths
320 are not known until the full pattern has been compiled, thus the
321 pointer to the value.
325 In the case of lookbehind the string being searched for can be
326 offset past the start point of the final matching string.
327 If this value was just blithely removed from the min_offset it would
328 invalidate some of the calculations for how many chars must match
329 before or after (as they are derived from min_offset and minlen and
330 the length of the string being searched for).
331 When the final pattern is compiled and the data is moved from the
332 scan_data_t structure into the regexp structure the information
333 about lookbehind is factored in, with the information that would
334 have been lost precalculated in the end_shift field for the
337 The fields pos_min and pos_delta are used to store the minimum offset
338 and the delta to the maximum offset at the current point in the pattern.
342 typedef struct scan_data_t {
343 /*I32 len_min; unused */
344 /*I32 len_delta; unused */
348 I32 last_end; /* min value, <0 unless valid. */
351 SV **longest; /* Either &l_fixed, or &l_float. */
352 SV *longest_fixed; /* longest fixed string found in pattern */
353 I32 offset_fixed; /* offset where it starts */
354 I32 *minlen_fixed; /* pointer to the minlen relevant to the string */
355 I32 lookbehind_fixed; /* is the position of the string modfied by LB */
356 SV *longest_float; /* longest floating string found in pattern */
357 I32 offset_float_min; /* earliest point in string it can appear */
358 I32 offset_float_max; /* latest point in string it can appear */
359 I32 *minlen_float; /* pointer to the minlen relevant to the string */
360 I32 lookbehind_float; /* is the position of the string modified by LB */
364 struct regnode_charclass_class *start_class;
368 * Forward declarations for pregcomp()'s friends.
371 static const scan_data_t zero_scan_data =
372 { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ,0};
374 #define SF_BEFORE_EOL (SF_BEFORE_SEOL|SF_BEFORE_MEOL)
375 #define SF_BEFORE_SEOL 0x0001
376 #define SF_BEFORE_MEOL 0x0002
377 #define SF_FIX_BEFORE_EOL (SF_FIX_BEFORE_SEOL|SF_FIX_BEFORE_MEOL)
378 #define SF_FL_BEFORE_EOL (SF_FL_BEFORE_SEOL|SF_FL_BEFORE_MEOL)
381 # define SF_FIX_SHIFT_EOL (0+2)
382 # define SF_FL_SHIFT_EOL (0+4)
384 # define SF_FIX_SHIFT_EOL (+2)
385 # define SF_FL_SHIFT_EOL (+4)
388 #define SF_FIX_BEFORE_SEOL (SF_BEFORE_SEOL << SF_FIX_SHIFT_EOL)
389 #define SF_FIX_BEFORE_MEOL (SF_BEFORE_MEOL << SF_FIX_SHIFT_EOL)
391 #define SF_FL_BEFORE_SEOL (SF_BEFORE_SEOL << SF_FL_SHIFT_EOL)
392 #define SF_FL_BEFORE_MEOL (SF_BEFORE_MEOL << SF_FL_SHIFT_EOL) /* 0x20 */
393 #define SF_IS_INF 0x0040
394 #define SF_HAS_PAR 0x0080
395 #define SF_IN_PAR 0x0100
396 #define SF_HAS_EVAL 0x0200
397 #define SCF_DO_SUBSTR 0x0400
398 #define SCF_DO_STCLASS_AND 0x0800
399 #define SCF_DO_STCLASS_OR 0x1000
400 #define SCF_DO_STCLASS (SCF_DO_STCLASS_AND|SCF_DO_STCLASS_OR)
401 #define SCF_WHILEM_VISITED_POS 0x2000
403 #define SCF_TRIE_RESTUDY 0x4000 /* Do restudy? */
404 #define SCF_SEEN_ACCEPT 0x8000
406 #define UTF cBOOL(RExC_utf8)
408 /* The enums for all these are ordered so things work out correctly */
409 #define LOC (get_regex_charset(RExC_flags) == REGEX_LOCALE_CHARSET)
410 #define DEPENDS_SEMANTICS (get_regex_charset(RExC_flags) == REGEX_DEPENDS_CHARSET)
411 #define UNI_SEMANTICS (get_regex_charset(RExC_flags) == REGEX_UNICODE_CHARSET)
412 #define AT_LEAST_UNI_SEMANTICS (get_regex_charset(RExC_flags) >= REGEX_UNICODE_CHARSET)
413 #define ASCII_RESTRICTED (get_regex_charset(RExC_flags) == REGEX_ASCII_RESTRICTED_CHARSET)
414 #define AT_LEAST_ASCII_RESTRICTED (get_regex_charset(RExC_flags) >= REGEX_ASCII_RESTRICTED_CHARSET)
415 #define ASCII_FOLD_RESTRICTED (get_regex_charset(RExC_flags) == REGEX_ASCII_MORE_RESTRICTED_CHARSET)
417 #define FOLD cBOOL(RExC_flags & RXf_PMf_FOLD)
419 #define OOB_NAMEDCLASS -1
421 /* There is no code point that is out-of-bounds, so this is problematic. But
422 * its only current use is to initialize a variable that is always set before
424 #define OOB_UNICODE 0xDEADBEEF
426 #define CHR_SVLEN(sv) (UTF ? sv_len_utf8(sv) : SvCUR(sv))
427 #define CHR_DIST(a,b) (UTF ? utf8_distance(a,b) : a - b)
430 /* length of regex to show in messages that don't mark a position within */
431 #define RegexLengthToShowInErrorMessages 127
434 * If MARKER[12] are adjusted, be sure to adjust the constants at the top
435 * of t/op/regmesg.t, the tests in t/op/re_tests, and those in
436 * op/pragma/warn/regcomp.
438 #define MARKER1 "<-- HERE" /* marker as it appears in the description */
439 #define MARKER2 " <-- HERE " /* marker as it appears within the regex */
441 #define REPORT_LOCATION " in regex; marked by " MARKER1 " in m/%.*s" MARKER2 "%s/"
444 * Calls SAVEDESTRUCTOR_X if needed, then calls Perl_croak with the given
445 * arg. Show regex, up to a maximum length. If it's too long, chop and add
448 #define _FAIL(code) STMT_START { \
449 const char *ellipses = ""; \
450 IV len = RExC_end - RExC_precomp; \
453 SAVEFREESV(RExC_rx_sv); \
454 if (len > RegexLengthToShowInErrorMessages) { \
455 /* chop 10 shorter than the max, to ensure meaning of "..." */ \
456 len = RegexLengthToShowInErrorMessages - 10; \
462 #define FAIL(msg) _FAIL( \
463 Perl_croak(aTHX_ "%s in regex m/%.*s%s/", \
464 msg, (int)len, RExC_precomp, ellipses))
466 #define FAIL2(msg,arg) _FAIL( \
467 Perl_croak(aTHX_ msg " in regex m/%.*s%s/", \
468 arg, (int)len, RExC_precomp, ellipses))
471 * Simple_vFAIL -- like FAIL, but marks the current location in the scan
473 #define Simple_vFAIL(m) STMT_START { \
474 const IV offset = RExC_parse - RExC_precomp; \
475 Perl_croak(aTHX_ "%s" REPORT_LOCATION, \
476 m, (int)offset, RExC_precomp, RExC_precomp + offset); \
480 * Calls SAVEDESTRUCTOR_X if needed, then Simple_vFAIL()
482 #define vFAIL(m) STMT_START { \
484 SAVEFREESV(RExC_rx_sv); \
489 * Like Simple_vFAIL(), but accepts two arguments.
491 #define Simple_vFAIL2(m,a1) STMT_START { \
492 const IV offset = RExC_parse - RExC_precomp; \
493 S_re_croak2(aTHX_ m, REPORT_LOCATION, a1, \
494 (int)offset, RExC_precomp, RExC_precomp + offset); \
498 * Calls SAVEDESTRUCTOR_X if needed, then Simple_vFAIL2().
500 #define vFAIL2(m,a1) STMT_START { \
502 SAVEFREESV(RExC_rx_sv); \
503 Simple_vFAIL2(m, a1); \
508 * Like Simple_vFAIL(), but accepts three arguments.
510 #define Simple_vFAIL3(m, a1, a2) STMT_START { \
511 const IV offset = RExC_parse - RExC_precomp; \
512 S_re_croak2(aTHX_ m, REPORT_LOCATION, a1, a2, \
513 (int)offset, RExC_precomp, RExC_precomp + offset); \
517 * Calls SAVEDESTRUCTOR_X if needed, then Simple_vFAIL3().
519 #define vFAIL3(m,a1,a2) STMT_START { \
521 SAVEFREESV(RExC_rx_sv); \
522 Simple_vFAIL3(m, a1, a2); \
526 * Like Simple_vFAIL(), but accepts four arguments.
528 #define Simple_vFAIL4(m, a1, a2, a3) STMT_START { \
529 const IV offset = RExC_parse - RExC_precomp; \
530 S_re_croak2(aTHX_ m, REPORT_LOCATION, a1, a2, a3, \
531 (int)offset, RExC_precomp, RExC_precomp + offset); \
534 #define vFAIL4(m,a1,a2,a3) STMT_START { \
536 SAVEFREESV(RExC_rx_sv); \
537 Simple_vFAIL4(m, a1, a2, a3); \
540 /* m is not necessarily a "literal string", in this macro */
541 #define reg_warn_non_literal_string(loc, m) STMT_START { \
542 const IV offset = loc - RExC_precomp; \
543 Perl_warner(aTHX_ packWARN(WARN_REGEXP), "%s" REPORT_LOCATION, \
544 m, (int)offset, RExC_precomp, RExC_precomp + offset); \
547 #define ckWARNreg(loc,m) STMT_START { \
548 const IV offset = loc - RExC_precomp; \
549 Perl_ck_warner(aTHX_ packWARN(WARN_REGEXP), m REPORT_LOCATION, \
550 (int)offset, RExC_precomp, RExC_precomp + offset); \
553 #define vWARN_dep(loc, m) STMT_START { \
554 const IV offset = loc - RExC_precomp; \
555 Perl_warner(aTHX_ packWARN(WARN_DEPRECATED), m REPORT_LOCATION, \
556 (int)offset, RExC_precomp, RExC_precomp + offset); \
559 #define ckWARNdep(loc,m) STMT_START { \
560 const IV offset = loc - RExC_precomp; \
561 Perl_ck_warner_d(aTHX_ packWARN(WARN_DEPRECATED), \
563 (int)offset, RExC_precomp, RExC_precomp + offset); \
566 #define ckWARNregdep(loc,m) STMT_START { \
567 const IV offset = loc - RExC_precomp; \
568 Perl_ck_warner_d(aTHX_ packWARN2(WARN_DEPRECATED, WARN_REGEXP), \
570 (int)offset, RExC_precomp, RExC_precomp + offset); \
573 #define ckWARN2regdep(loc,m, a1) STMT_START { \
574 const IV offset = loc - RExC_precomp; \
575 Perl_ck_warner_d(aTHX_ packWARN2(WARN_DEPRECATED, WARN_REGEXP), \
577 a1, (int)offset, RExC_precomp, RExC_precomp + offset); \
580 #define ckWARN2reg(loc, m, a1) STMT_START { \
581 const IV offset = loc - RExC_precomp; \
582 Perl_ck_warner(aTHX_ packWARN(WARN_REGEXP), m REPORT_LOCATION, \
583 a1, (int)offset, RExC_precomp, RExC_precomp + offset); \
586 #define vWARN3(loc, m, a1, a2) STMT_START { \
587 const IV offset = loc - RExC_precomp; \
588 Perl_warner(aTHX_ packWARN(WARN_REGEXP), m REPORT_LOCATION, \
589 a1, a2, (int)offset, RExC_precomp, RExC_precomp + offset); \
592 #define ckWARN3reg(loc, m, a1, a2) STMT_START { \
593 const IV offset = loc - RExC_precomp; \
594 Perl_ck_warner(aTHX_ packWARN(WARN_REGEXP), m REPORT_LOCATION, \
595 a1, a2, (int)offset, RExC_precomp, RExC_precomp + offset); \
598 #define vWARN4(loc, m, a1, a2, a3) STMT_START { \
599 const IV offset = loc - RExC_precomp; \
600 Perl_warner(aTHX_ packWARN(WARN_REGEXP), m REPORT_LOCATION, \
601 a1, a2, a3, (int)offset, RExC_precomp, RExC_precomp + offset); \
604 #define ckWARN4reg(loc, m, a1, a2, a3) STMT_START { \
605 const IV offset = loc - RExC_precomp; \
606 Perl_ck_warner(aTHX_ packWARN(WARN_REGEXP), m REPORT_LOCATION, \
607 a1, a2, a3, (int)offset, RExC_precomp, RExC_precomp + offset); \
610 #define vWARN5(loc, m, a1, a2, a3, a4) STMT_START { \
611 const IV offset = loc - RExC_precomp; \
612 Perl_warner(aTHX_ packWARN(WARN_REGEXP), m REPORT_LOCATION, \
613 a1, a2, a3, a4, (int)offset, RExC_precomp, RExC_precomp + offset); \
617 /* Allow for side effects in s */
618 #define REGC(c,s) STMT_START { \
619 if (!SIZE_ONLY) *(s) = (c); else (void)(s); \
622 /* Macros for recording node offsets. 20001227 mjd@plover.com
623 * Nodes are numbered 1, 2, 3, 4. Node #n's position is recorded in
624 * element 2*n-1 of the array. Element #2n holds the byte length node #n.
625 * Element 0 holds the number n.
626 * Position is 1 indexed.
628 #ifndef RE_TRACK_PATTERN_OFFSETS
629 #define Set_Node_Offset_To_R(node,byte)
630 #define Set_Node_Offset(node,byte)
631 #define Set_Cur_Node_Offset
632 #define Set_Node_Length_To_R(node,len)
633 #define Set_Node_Length(node,len)
634 #define Set_Node_Cur_Length(node)
635 #define Node_Offset(n)
636 #define Node_Length(n)
637 #define Set_Node_Offset_Length(node,offset,len)
638 #define ProgLen(ri) ri->u.proglen
639 #define SetProgLen(ri,x) ri->u.proglen = x
641 #define ProgLen(ri) ri->u.offsets[0]
642 #define SetProgLen(ri,x) ri->u.offsets[0] = x
643 #define Set_Node_Offset_To_R(node,byte) STMT_START { \
645 MJD_OFFSET_DEBUG(("** (%d) offset of node %d is %d.\n", \
646 __LINE__, (int)(node), (int)(byte))); \
648 Perl_croak(aTHX_ "value of node is %d in Offset macro", (int)(node)); \
650 RExC_offsets[2*(node)-1] = (byte); \
655 #define Set_Node_Offset(node,byte) \
656 Set_Node_Offset_To_R((node)-RExC_emit_start, (byte)-RExC_start)
657 #define Set_Cur_Node_Offset Set_Node_Offset(RExC_emit, RExC_parse)
659 #define Set_Node_Length_To_R(node,len) STMT_START { \
661 MJD_OFFSET_DEBUG(("** (%d) size of node %d is %d.\n", \
662 __LINE__, (int)(node), (int)(len))); \
664 Perl_croak(aTHX_ "value of node is %d in Length macro", (int)(node)); \
666 RExC_offsets[2*(node)] = (len); \
671 #define Set_Node_Length(node,len) \
672 Set_Node_Length_To_R((node)-RExC_emit_start, len)
673 #define Set_Cur_Node_Length(len) Set_Node_Length(RExC_emit, len)
674 #define Set_Node_Cur_Length(node) \
675 Set_Node_Length(node, RExC_parse - parse_start)
677 /* Get offsets and lengths */
678 #define Node_Offset(n) (RExC_offsets[2*((n)-RExC_emit_start)-1])
679 #define Node_Length(n) (RExC_offsets[2*((n)-RExC_emit_start)])
681 #define Set_Node_Offset_Length(node,offset,len) STMT_START { \
682 Set_Node_Offset_To_R((node)-RExC_emit_start, (offset)); \
683 Set_Node_Length_To_R((node)-RExC_emit_start, (len)); \
687 #if PERL_ENABLE_EXPERIMENTAL_REGEX_OPTIMISATIONS
688 #define EXPERIMENTAL_INPLACESCAN
689 #endif /*PERL_ENABLE_EXPERIMENTAL_REGEX_OPTIMISATIONS*/
691 #define DEBUG_STUDYDATA(str,data,depth) \
692 DEBUG_OPTIMISE_MORE_r(if(data){ \
693 PerlIO_printf(Perl_debug_log, \
694 "%*s" str "Pos:%"IVdf"/%"IVdf \
695 " Flags: 0x%"UVXf" Whilem_c: %"IVdf" Lcp: %"IVdf" %s", \
696 (int)(depth)*2, "", \
697 (IV)((data)->pos_min), \
698 (IV)((data)->pos_delta), \
699 (UV)((data)->flags), \
700 (IV)((data)->whilem_c), \
701 (IV)((data)->last_closep ? *((data)->last_closep) : -1), \
702 is_inf ? "INF " : "" \
704 if ((data)->last_found) \
705 PerlIO_printf(Perl_debug_log, \
706 "Last:'%s' %"IVdf":%"IVdf"/%"IVdf" %sFixed:'%s' @ %"IVdf \
707 " %sFloat: '%s' @ %"IVdf"/%"IVdf"", \
708 SvPVX_const((data)->last_found), \
709 (IV)((data)->last_end), \
710 (IV)((data)->last_start_min), \
711 (IV)((data)->last_start_max), \
712 ((data)->longest && \
713 (data)->longest==&((data)->longest_fixed)) ? "*" : "", \
714 SvPVX_const((data)->longest_fixed), \
715 (IV)((data)->offset_fixed), \
716 ((data)->longest && \
717 (data)->longest==&((data)->longest_float)) ? "*" : "", \
718 SvPVX_const((data)->longest_float), \
719 (IV)((data)->offset_float_min), \
720 (IV)((data)->offset_float_max) \
722 PerlIO_printf(Perl_debug_log,"\n"); \
725 /* Mark that we cannot extend a found fixed substring at this point.
726 Update the longest found anchored substring and the longest found
727 floating substrings if needed. */
730 S_scan_commit(pTHX_ const RExC_state_t *pRExC_state, scan_data_t *data, I32 *minlenp, int is_inf)
732 const STRLEN l = CHR_SVLEN(data->last_found);
733 const STRLEN old_l = CHR_SVLEN(*data->longest);
734 GET_RE_DEBUG_FLAGS_DECL;
736 PERL_ARGS_ASSERT_SCAN_COMMIT;
738 if ((l >= old_l) && ((l > old_l) || (data->flags & SF_BEFORE_EOL))) {
739 SvSetMagicSV(*data->longest, data->last_found);
740 if (*data->longest == data->longest_fixed) {
741 data->offset_fixed = l ? data->last_start_min : data->pos_min;
742 if (data->flags & SF_BEFORE_EOL)
744 |= ((data->flags & SF_BEFORE_EOL) << SF_FIX_SHIFT_EOL);
746 data->flags &= ~SF_FIX_BEFORE_EOL;
747 data->minlen_fixed=minlenp;
748 data->lookbehind_fixed=0;
750 else { /* *data->longest == data->longest_float */
751 data->offset_float_min = l ? data->last_start_min : data->pos_min;
752 data->offset_float_max = (l
753 ? data->last_start_max
754 : (data->pos_delta == I32_MAX ? I32_MAX : data->pos_min + data->pos_delta));
755 if (is_inf || (U32)data->offset_float_max > (U32)I32_MAX)
756 data->offset_float_max = I32_MAX;
757 if (data->flags & SF_BEFORE_EOL)
759 |= ((data->flags & SF_BEFORE_EOL) << SF_FL_SHIFT_EOL);
761 data->flags &= ~SF_FL_BEFORE_EOL;
762 data->minlen_float=minlenp;
763 data->lookbehind_float=0;
766 SvCUR_set(data->last_found, 0);
768 SV * const sv = data->last_found;
769 if (SvUTF8(sv) && SvMAGICAL(sv)) {
770 MAGIC * const mg = mg_find(sv, PERL_MAGIC_utf8);
776 data->flags &= ~SF_BEFORE_EOL;
777 DEBUG_STUDYDATA("commit: ",data,0);
780 /* These macros set, clear and test whether the synthetic start class ('ssc',
781 * given by the parameter) matches an empty string (EOS). This uses the
782 * 'next_off' field in the node, to save a bit in the flags field. The ssc
783 * stands alone, so there is never a next_off, so this field is otherwise
784 * unused. The EOS information is used only for compilation, but theoretically
785 * it could be passed on to the execution code. This could be used to store
786 * more than one bit of information, but only this one is currently used. */
787 #define SET_SSC_EOS(node) STMT_START { (node)->next_off = TRUE; } STMT_END
788 #define CLEAR_SSC_EOS(node) STMT_START { (node)->next_off = FALSE; } STMT_END
789 #define TEST_SSC_EOS(node) cBOOL((node)->next_off)
791 /* Can match anything (initialization) */
793 S_cl_anything(const RExC_state_t *pRExC_state, struct regnode_charclass_class *cl)
795 PERL_ARGS_ASSERT_CL_ANYTHING;
797 ANYOF_BITMAP_SETALL(cl);
798 cl->flags = ANYOF_UNICODE_ALL;
801 /* If any portion of the regex is to operate under locale rules,
802 * initialization includes it. The reason this isn't done for all regexes
803 * is that the optimizer was written under the assumption that locale was
804 * all-or-nothing. Given the complexity and lack of documentation in the
805 * optimizer, and that there are inadequate test cases for locale, so many
806 * parts of it may not work properly, it is safest to avoid locale unless
808 if (RExC_contains_locale) {
809 ANYOF_CLASS_SETALL(cl); /* /l uses class */
810 cl->flags |= ANYOF_LOCALE|ANYOF_CLASS|ANYOF_LOC_FOLD;
813 ANYOF_CLASS_ZERO(cl); /* Only /l uses class now */
817 /* Can match anything (initialization) */
819 S_cl_is_anything(const struct regnode_charclass_class *cl)
823 PERL_ARGS_ASSERT_CL_IS_ANYTHING;
825 for (value = 0; value < ANYOF_MAX; value += 2)
826 if (ANYOF_CLASS_TEST(cl, value) && ANYOF_CLASS_TEST(cl, value + 1))
828 if (!(cl->flags & ANYOF_UNICODE_ALL))
830 if (!ANYOF_BITMAP_TESTALLSET((const void*)cl))
835 /* Can match anything (initialization) */
837 S_cl_init(const RExC_state_t *pRExC_state, struct regnode_charclass_class *cl)
839 PERL_ARGS_ASSERT_CL_INIT;
841 Zero(cl, 1, struct regnode_charclass_class);
843 cl_anything(pRExC_state, cl);
844 ARG_SET(cl, ANYOF_NONBITMAP_EMPTY);
847 /* These two functions currently do the exact same thing */
848 #define cl_init_zero S_cl_init
850 /* 'AND' a given class with another one. Can create false positives. 'cl'
851 * should not be inverted. 'and_with->flags & ANYOF_CLASS' should be 0 if
852 * 'and_with' is a regnode_charclass instead of a regnode_charclass_class. */
854 S_cl_and(struct regnode_charclass_class *cl,
855 const struct regnode_charclass_class *and_with)
857 PERL_ARGS_ASSERT_CL_AND;
859 assert(PL_regkind[and_with->type] == ANYOF);
861 /* I (khw) am not sure all these restrictions are necessary XXX */
862 if (!(ANYOF_CLASS_TEST_ANY_SET(and_with))
863 && !(ANYOF_CLASS_TEST_ANY_SET(cl))
864 && (and_with->flags & ANYOF_LOCALE) == (cl->flags & ANYOF_LOCALE)
865 && !(and_with->flags & ANYOF_LOC_FOLD)
866 && !(cl->flags & ANYOF_LOC_FOLD)) {
869 if (and_with->flags & ANYOF_INVERT)
870 for (i = 0; i < ANYOF_BITMAP_SIZE; i++)
871 cl->bitmap[i] &= ~and_with->bitmap[i];
873 for (i = 0; i < ANYOF_BITMAP_SIZE; i++)
874 cl->bitmap[i] &= and_with->bitmap[i];
875 } /* XXXX: logic is complicated otherwise, leave it along for a moment. */
877 if (and_with->flags & ANYOF_INVERT) {
879 /* Here, the and'ed node is inverted. Get the AND of the flags that
880 * aren't affected by the inversion. Those that are affected are
881 * handled individually below */
882 U8 affected_flags = cl->flags & ~INVERSION_UNAFFECTED_FLAGS;
883 cl->flags &= (and_with->flags & INVERSION_UNAFFECTED_FLAGS);
884 cl->flags |= affected_flags;
886 /* We currently don't know how to deal with things that aren't in the
887 * bitmap, but we know that the intersection is no greater than what
888 * is already in cl, so let there be false positives that get sorted
889 * out after the synthetic start class succeeds, and the node is
890 * matched for real. */
892 /* The inversion of these two flags indicate that the resulting
893 * intersection doesn't have them */
894 if (and_with->flags & ANYOF_UNICODE_ALL) {
895 cl->flags &= ~ANYOF_UNICODE_ALL;
897 if (and_with->flags & ANYOF_NON_UTF8_LATIN1_ALL) {
898 cl->flags &= ~ANYOF_NON_UTF8_LATIN1_ALL;
901 else { /* and'd node is not inverted */
902 U8 outside_bitmap_but_not_utf8; /* Temp variable */
904 if (! ANYOF_NONBITMAP(and_with)) {
906 /* Here 'and_with' doesn't match anything outside the bitmap
907 * (except possibly ANYOF_UNICODE_ALL), which means the
908 * intersection can't either, except for ANYOF_UNICODE_ALL, in
909 * which case we don't know what the intersection is, but it's no
910 * greater than what cl already has, so can just leave it alone,
911 * with possible false positives */
912 if (! (and_with->flags & ANYOF_UNICODE_ALL)) {
913 ARG_SET(cl, ANYOF_NONBITMAP_EMPTY);
914 cl->flags &= ~ANYOF_NONBITMAP_NON_UTF8;
917 else if (! ANYOF_NONBITMAP(cl)) {
919 /* Here, 'and_with' does match something outside the bitmap, and cl
920 * doesn't have a list of things to match outside the bitmap. If
921 * cl can match all code points above 255, the intersection will
922 * be those above-255 code points that 'and_with' matches. If cl
923 * can't match all Unicode code points, it means that it can't
924 * match anything outside the bitmap (since the 'if' that got us
925 * into this block tested for that), so we leave the bitmap empty.
927 if (cl->flags & ANYOF_UNICODE_ALL) {
928 ARG_SET(cl, ARG(and_with));
930 /* and_with's ARG may match things that don't require UTF8.
931 * And now cl's will too, in spite of this being an 'and'. See
932 * the comments below about the kludge */
933 cl->flags |= and_with->flags & ANYOF_NONBITMAP_NON_UTF8;
937 /* Here, both 'and_with' and cl match something outside the
938 * bitmap. Currently we do not do the intersection, so just match
939 * whatever cl had at the beginning. */
943 /* Take the intersection of the two sets of flags. However, the
944 * ANYOF_NONBITMAP_NON_UTF8 flag is treated as an 'or'. This is a
945 * kludge around the fact that this flag is not treated like the others
946 * which are initialized in cl_anything(). The way the optimizer works
947 * is that the synthetic start class (SSC) is initialized to match
948 * anything, and then the first time a real node is encountered, its
949 * values are AND'd with the SSC's with the result being the values of
950 * the real node. However, there are paths through the optimizer where
951 * the AND never gets called, so those initialized bits are set
952 * inappropriately, which is not usually a big deal, as they just cause
953 * false positives in the SSC, which will just mean a probably
954 * imperceptible slow down in execution. However this bit has a
955 * higher false positive consequence in that it can cause utf8.pm,
956 * utf8_heavy.pl ... to be loaded when not necessary, which is a much
957 * bigger slowdown and also causes significant extra memory to be used.
958 * In order to prevent this, the code now takes a different tack. The
959 * bit isn't set unless some part of the regular expression needs it,
960 * but once set it won't get cleared. This means that these extra
961 * modules won't get loaded unless there was some path through the
962 * pattern that would have required them anyway, and so any false
963 * positives that occur by not ANDing them out when they could be
964 * aren't as severe as they would be if we treated this bit like all
966 outside_bitmap_but_not_utf8 = (cl->flags | and_with->flags)
967 & ANYOF_NONBITMAP_NON_UTF8;
968 cl->flags &= and_with->flags;
969 cl->flags |= outside_bitmap_but_not_utf8;
973 /* 'OR' a given class with another one. Can create false positives. 'cl'
974 * should not be inverted. 'or_with->flags & ANYOF_CLASS' should be 0 if
975 * 'or_with' is a regnode_charclass instead of a regnode_charclass_class. */
977 S_cl_or(const RExC_state_t *pRExC_state, struct regnode_charclass_class *cl, const struct regnode_charclass_class *or_with)
979 PERL_ARGS_ASSERT_CL_OR;
981 if (or_with->flags & ANYOF_INVERT) {
983 /* Here, the or'd node is to be inverted. This means we take the
984 * complement of everything not in the bitmap, but currently we don't
985 * know what that is, so give up and match anything */
986 if (ANYOF_NONBITMAP(or_with)) {
987 cl_anything(pRExC_state, cl);
990 * (B1 | CL1) | (!B2 & !CL2) = (B1 | !B2 & !CL2) | (CL1 | (!B2 & !CL2))
991 * <= (B1 | !B2) | (CL1 | !CL2)
992 * which is wasteful if CL2 is small, but we ignore CL2:
993 * (B1 | CL1) | (!B2 & !CL2) <= (B1 | CL1) | !B2 = (B1 | !B2) | CL1
994 * XXXX Can we handle case-fold? Unclear:
995 * (OK1(i) | OK1(i')) | !(OK1(i) | OK1(i')) =
996 * (OK1(i) | OK1(i')) | (!OK1(i) & !OK1(i'))
998 else if ( (or_with->flags & ANYOF_LOCALE) == (cl->flags & ANYOF_LOCALE)
999 && !(or_with->flags & ANYOF_LOC_FOLD)
1000 && !(cl->flags & ANYOF_LOC_FOLD) ) {
1003 for (i = 0; i < ANYOF_BITMAP_SIZE; i++)
1004 cl->bitmap[i] |= ~or_with->bitmap[i];
1005 } /* XXXX: logic is complicated otherwise */
1007 cl_anything(pRExC_state, cl);
1010 /* And, we can just take the union of the flags that aren't affected
1011 * by the inversion */
1012 cl->flags |= or_with->flags & INVERSION_UNAFFECTED_FLAGS;
1014 /* For the remaining flags:
1015 ANYOF_UNICODE_ALL and inverted means to not match anything above
1016 255, which means that the union with cl should just be
1017 what cl has in it, so can ignore this flag
1018 ANYOF_NON_UTF8_LATIN1_ALL and inverted means if not utf8 and ord
1019 is 127-255 to match them, but then invert that, so the
1020 union with cl should just be what cl has in it, so can
1023 } else { /* 'or_with' is not inverted */
1024 /* (B1 | CL1) | (B2 | CL2) = (B1 | B2) | (CL1 | CL2)) */
1025 if ( (or_with->flags & ANYOF_LOCALE) == (cl->flags & ANYOF_LOCALE)
1026 && (!(or_with->flags & ANYOF_LOC_FOLD)
1027 || (cl->flags & ANYOF_LOC_FOLD)) ) {
1030 /* OR char bitmap and class bitmap separately */
1031 for (i = 0; i < ANYOF_BITMAP_SIZE; i++)
1032 cl->bitmap[i] |= or_with->bitmap[i];
1033 if (or_with->flags & ANYOF_CLASS) {
1034 ANYOF_CLASS_OR(or_with, cl);
1037 else { /* XXXX: logic is complicated, leave it along for a moment. */
1038 cl_anything(pRExC_state, cl);
1041 if (ANYOF_NONBITMAP(or_with)) {
1043 /* Use the added node's outside-the-bit-map match if there isn't a
1044 * conflict. If there is a conflict (both nodes match something
1045 * outside the bitmap, but what they match outside is not the same
1046 * pointer, and hence not easily compared until XXX we extend
1047 * inversion lists this far), give up and allow the start class to
1048 * match everything outside the bitmap. If that stuff is all above
1049 * 255, can just set UNICODE_ALL, otherwise caould be anything. */
1050 if (! ANYOF_NONBITMAP(cl)) {
1051 ARG_SET(cl, ARG(or_with));
1053 else if (ARG(cl) != ARG(or_with)) {
1055 if ((or_with->flags & ANYOF_NONBITMAP_NON_UTF8)) {
1056 cl_anything(pRExC_state, cl);
1059 cl->flags |= ANYOF_UNICODE_ALL;
1064 /* Take the union */
1065 cl->flags |= or_with->flags;
1069 #define TRIE_LIST_ITEM(state,idx) (trie->states[state].trans.list)[ idx ]
1070 #define TRIE_LIST_CUR(state) ( TRIE_LIST_ITEM( state, 0 ).forid )
1071 #define TRIE_LIST_LEN(state) ( TRIE_LIST_ITEM( state, 0 ).newstate )
1072 #define TRIE_LIST_USED(idx) ( trie->states[state].trans.list ? (TRIE_LIST_CUR( idx ) - 1) : 0 )
1077 dump_trie(trie,widecharmap,revcharmap)
1078 dump_trie_interim_list(trie,widecharmap,revcharmap,next_alloc)
1079 dump_trie_interim_table(trie,widecharmap,revcharmap,next_alloc)
1081 These routines dump out a trie in a somewhat readable format.
1082 The _interim_ variants are used for debugging the interim
1083 tables that are used to generate the final compressed
1084 representation which is what dump_trie expects.
1086 Part of the reason for their existence is to provide a form
1087 of documentation as to how the different representations function.
1092 Dumps the final compressed table form of the trie to Perl_debug_log.
1093 Used for debugging make_trie().
1097 S_dump_trie(pTHX_ const struct _reg_trie_data *trie, HV *widecharmap,
1098 AV *revcharmap, U32 depth)
1101 SV *sv=sv_newmortal();
1102 int colwidth= widecharmap ? 6 : 4;
1104 GET_RE_DEBUG_FLAGS_DECL;
1106 PERL_ARGS_ASSERT_DUMP_TRIE;
1108 PerlIO_printf( Perl_debug_log, "%*sChar : %-6s%-6s%-4s ",
1109 (int)depth * 2 + 2,"",
1110 "Match","Base","Ofs" );
1112 for( state = 0 ; state < trie->uniquecharcount ; state++ ) {
1113 SV ** const tmp = av_fetch( revcharmap, state, 0);
1115 PerlIO_printf( Perl_debug_log, "%*s",
1117 pv_pretty(sv, SvPV_nolen_const(*tmp), SvCUR(*tmp), colwidth,
1118 PL_colors[0], PL_colors[1],
1119 (SvUTF8(*tmp) ? PERL_PV_ESCAPE_UNI : 0) |
1120 PERL_PV_ESCAPE_FIRSTCHAR
1125 PerlIO_printf( Perl_debug_log, "\n%*sState|-----------------------",
1126 (int)depth * 2 + 2,"");
1128 for( state = 0 ; state < trie->uniquecharcount ; state++ )
1129 PerlIO_printf( Perl_debug_log, "%.*s", colwidth, "--------");
1130 PerlIO_printf( Perl_debug_log, "\n");
1132 for( state = 1 ; state < trie->statecount ; state++ ) {
1133 const U32 base = trie->states[ state ].trans.base;
1135 PerlIO_printf( Perl_debug_log, "%*s#%4"UVXf"|", (int)depth * 2 + 2,"", (UV)state);
1137 if ( trie->states[ state ].wordnum ) {
1138 PerlIO_printf( Perl_debug_log, " W%4X", trie->states[ state ].wordnum );
1140 PerlIO_printf( Perl_debug_log, "%6s", "" );
1143 PerlIO_printf( Perl_debug_log, " @%4"UVXf" ", (UV)base );
1148 while( ( base + ofs < trie->uniquecharcount ) ||
1149 ( base + ofs - trie->uniquecharcount < trie->lasttrans
1150 && trie->trans[ base + ofs - trie->uniquecharcount ].check != state))
1153 PerlIO_printf( Perl_debug_log, "+%2"UVXf"[ ", (UV)ofs);
1155 for ( ofs = 0 ; ofs < trie->uniquecharcount ; ofs++ ) {
1156 if ( ( base + ofs >= trie->uniquecharcount ) &&
1157 ( base + ofs - trie->uniquecharcount < trie->lasttrans ) &&
1158 trie->trans[ base + ofs - trie->uniquecharcount ].check == state )
1160 PerlIO_printf( Perl_debug_log, "%*"UVXf,
1162 (UV)trie->trans[ base + ofs - trie->uniquecharcount ].next );
1164 PerlIO_printf( Perl_debug_log, "%*s",colwidth," ." );
1168 PerlIO_printf( Perl_debug_log, "]");
1171 PerlIO_printf( Perl_debug_log, "\n" );
1173 PerlIO_printf(Perl_debug_log, "%*sword_info N:(prev,len)=", (int)depth*2, "");
1174 for (word=1; word <= trie->wordcount; word++) {
1175 PerlIO_printf(Perl_debug_log, " %d:(%d,%d)",
1176 (int)word, (int)(trie->wordinfo[word].prev),
1177 (int)(trie->wordinfo[word].len));
1179 PerlIO_printf(Perl_debug_log, "\n" );
1182 Dumps a fully constructed but uncompressed trie in list form.
1183 List tries normally only are used for construction when the number of
1184 possible chars (trie->uniquecharcount) is very high.
1185 Used for debugging make_trie().
1188 S_dump_trie_interim_list(pTHX_ const struct _reg_trie_data *trie,
1189 HV *widecharmap, AV *revcharmap, U32 next_alloc,
1193 SV *sv=sv_newmortal();
1194 int colwidth= widecharmap ? 6 : 4;
1195 GET_RE_DEBUG_FLAGS_DECL;
1197 PERL_ARGS_ASSERT_DUMP_TRIE_INTERIM_LIST;
1199 /* print out the table precompression. */
1200 PerlIO_printf( Perl_debug_log, "%*sState :Word | Transition Data\n%*s%s",
1201 (int)depth * 2 + 2,"", (int)depth * 2 + 2,"",
1202 "------:-----+-----------------\n" );
1204 for( state=1 ; state < next_alloc ; state ++ ) {
1207 PerlIO_printf( Perl_debug_log, "%*s %4"UVXf" :",
1208 (int)depth * 2 + 2,"", (UV)state );
1209 if ( ! trie->states[ state ].wordnum ) {
1210 PerlIO_printf( Perl_debug_log, "%5s| ","");
1212 PerlIO_printf( Perl_debug_log, "W%4x| ",
1213 trie->states[ state ].wordnum
1216 for( charid = 1 ; charid <= TRIE_LIST_USED( state ) ; charid++ ) {
1217 SV ** const tmp = av_fetch( revcharmap, TRIE_LIST_ITEM(state,charid).forid, 0);
1219 PerlIO_printf( Perl_debug_log, "%*s:%3X=%4"UVXf" | ",
1221 pv_pretty(sv, SvPV_nolen_const(*tmp), SvCUR(*tmp), colwidth,
1222 PL_colors[0], PL_colors[1],
1223 (SvUTF8(*tmp) ? PERL_PV_ESCAPE_UNI : 0) |
1224 PERL_PV_ESCAPE_FIRSTCHAR
1226 TRIE_LIST_ITEM(state,charid).forid,
1227 (UV)TRIE_LIST_ITEM(state,charid).newstate
1230 PerlIO_printf(Perl_debug_log, "\n%*s| ",
1231 (int)((depth * 2) + 14), "");
1234 PerlIO_printf( Perl_debug_log, "\n");
1239 Dumps a fully constructed but uncompressed trie in table form.
1240 This is the normal DFA style state transition table, with a few
1241 twists to facilitate compression later.
1242 Used for debugging make_trie().
1245 S_dump_trie_interim_table(pTHX_ const struct _reg_trie_data *trie,
1246 HV *widecharmap, AV *revcharmap, U32 next_alloc,
1251 SV *sv=sv_newmortal();
1252 int colwidth= widecharmap ? 6 : 4;
1253 GET_RE_DEBUG_FLAGS_DECL;
1255 PERL_ARGS_ASSERT_DUMP_TRIE_INTERIM_TABLE;
1258 print out the table precompression so that we can do a visual check
1259 that they are identical.
1262 PerlIO_printf( Perl_debug_log, "%*sChar : ",(int)depth * 2 + 2,"" );
1264 for( charid = 0 ; charid < trie->uniquecharcount ; charid++ ) {
1265 SV ** const tmp = av_fetch( revcharmap, charid, 0);
1267 PerlIO_printf( Perl_debug_log, "%*s",
1269 pv_pretty(sv, SvPV_nolen_const(*tmp), SvCUR(*tmp), colwidth,
1270 PL_colors[0], PL_colors[1],
1271 (SvUTF8(*tmp) ? PERL_PV_ESCAPE_UNI : 0) |
1272 PERL_PV_ESCAPE_FIRSTCHAR
1278 PerlIO_printf( Perl_debug_log, "\n%*sState+-",(int)depth * 2 + 2,"" );
1280 for( charid=0 ; charid < trie->uniquecharcount ; charid++ ) {
1281 PerlIO_printf( Perl_debug_log, "%.*s", colwidth,"--------");
1284 PerlIO_printf( Perl_debug_log, "\n" );
1286 for( state=1 ; state < next_alloc ; state += trie->uniquecharcount ) {
1288 PerlIO_printf( Perl_debug_log, "%*s%4"UVXf" : ",
1289 (int)depth * 2 + 2,"",
1290 (UV)TRIE_NODENUM( state ) );
1292 for( charid = 0 ; charid < trie->uniquecharcount ; charid++ ) {
1293 UV v=(UV)SAFE_TRIE_NODENUM( trie->trans[ state + charid ].next );
1295 PerlIO_printf( Perl_debug_log, "%*"UVXf, colwidth, v );
1297 PerlIO_printf( Perl_debug_log, "%*s", colwidth, "." );
1299 if ( ! trie->states[ TRIE_NODENUM( state ) ].wordnum ) {
1300 PerlIO_printf( Perl_debug_log, " (%4"UVXf")\n", (UV)trie->trans[ state ].check );
1302 PerlIO_printf( Perl_debug_log, " (%4"UVXf") W%4X\n", (UV)trie->trans[ state ].check,
1303 trie->states[ TRIE_NODENUM( state ) ].wordnum );
1311 /* make_trie(startbranch,first,last,tail,word_count,flags,depth)
1312 startbranch: the first branch in the whole branch sequence
1313 first : start branch of sequence of branch-exact nodes.
1314 May be the same as startbranch
1315 last : Thing following the last branch.
1316 May be the same as tail.
1317 tail : item following the branch sequence
1318 count : words in the sequence
1319 flags : currently the OP() type we will be building one of /EXACT(|F|Fl)/
1320 depth : indent depth
1322 Inplace optimizes a sequence of 2 or more Branch-Exact nodes into a TRIE node.
1324 A trie is an N'ary tree where the branches are determined by digital
1325 decomposition of the key. IE, at the root node you look up the 1st character and
1326 follow that branch repeat until you find the end of the branches. Nodes can be
1327 marked as "accepting" meaning they represent a complete word. Eg:
1331 would convert into the following structure. Numbers represent states, letters
1332 following numbers represent valid transitions on the letter from that state, if
1333 the number is in square brackets it represents an accepting state, otherwise it
1334 will be in parenthesis.
1336 +-h->+-e->[3]-+-r->(8)-+-s->[9]
1340 (1) +-i->(6)-+-s->[7]
1342 +-s->(3)-+-h->(4)-+-e->[5]
1344 Accept Word Mapping: 3=>1 (he),5=>2 (she), 7=>3 (his), 9=>4 (hers)
1346 This shows that when matching against the string 'hers' we will begin at state 1
1347 read 'h' and move to state 2, read 'e' and move to state 3 which is accepting,
1348 then read 'r' and go to state 8 followed by 's' which takes us to state 9 which
1349 is also accepting. Thus we know that we can match both 'he' and 'hers' with a
1350 single traverse. We store a mapping from accepting to state to which word was
1351 matched, and then when we have multiple possibilities we try to complete the
1352 rest of the regex in the order in which they occured in the alternation.
1354 The only prior NFA like behaviour that would be changed by the TRIE support is
1355 the silent ignoring of duplicate alternations which are of the form:
1357 / (DUPE|DUPE) X? (?{ ... }) Y /x
1359 Thus EVAL blocks following a trie may be called a different number of times with
1360 and without the optimisation. With the optimisations dupes will be silently
1361 ignored. This inconsistent behaviour of EVAL type nodes is well established as
1362 the following demonstrates:
1364 'words'=~/(word|word|word)(?{ print $1 })[xyz]/
1366 which prints out 'word' three times, but
1368 'words'=~/(word|word|word)(?{ print $1 })S/
1370 which doesnt print it out at all. This is due to other optimisations kicking in.
1372 Example of what happens on a structural level:
1374 The regexp /(ac|ad|ab)+/ will produce the following debug output:
1376 1: CURLYM[1] {1,32767}(18)
1387 This would be optimizable with startbranch=5, first=5, last=16, tail=16
1388 and should turn into:
1390 1: CURLYM[1] {1,32767}(18)
1392 [Words:3 Chars Stored:6 Unique Chars:4 States:5 NCP:1]
1400 Cases where tail != last would be like /(?foo|bar)baz/:
1410 which would be optimizable with startbranch=1, first=1, last=7, tail=8
1411 and would end up looking like:
1414 [Words:2 Chars Stored:6 Unique Chars:5 States:7 NCP:1]
1421 d = uvuni_to_utf8_flags(d, uv, 0);
1423 is the recommended Unicode-aware way of saying
1428 #define TRIE_STORE_REVCHAR(val) \
1431 SV *zlopp = newSV(7); /* XXX: optimize me */ \
1432 unsigned char *flrbbbbb = (unsigned char *) SvPVX(zlopp); \
1433 unsigned const char *const kapow = uvuni_to_utf8(flrbbbbb, val); \
1434 SvCUR_set(zlopp, kapow - flrbbbbb); \
1437 av_push(revcharmap, zlopp); \
1439 char ooooff = (char)val; \
1440 av_push(revcharmap, newSVpvn(&ooooff, 1)); \
1444 #define TRIE_READ_CHAR STMT_START { \
1447 /* if it is UTF then it is either already folded, or does not need folding */ \
1448 uvc = utf8n_to_uvuni( (const U8*) uc, UTF8_MAXLEN, &len, uniflags); \
1450 else if (folder == PL_fold_latin1) { \
1451 /* if we use this folder we have to obey unicode rules on latin-1 data */ \
1452 if ( foldlen > 0 ) { \
1453 uvc = utf8n_to_uvuni( (const U8*) scan, UTF8_MAXLEN, &len, uniflags ); \
1459 uvc = _to_fold_latin1( (U8) *uc, foldbuf, &foldlen, FOLD_FLAGS_FULL); \
1460 skiplen = UNISKIP(uvc); \
1461 foldlen -= skiplen; \
1462 scan = foldbuf + skiplen; \
1465 /* raw data, will be folded later if needed */ \
1473 #define TRIE_LIST_PUSH(state,fid,ns) STMT_START { \
1474 if ( TRIE_LIST_CUR( state ) >=TRIE_LIST_LEN( state ) ) { \
1475 U32 ging = TRIE_LIST_LEN( state ) *= 2; \
1476 Renew( trie->states[ state ].trans.list, ging, reg_trie_trans_le ); \
1478 TRIE_LIST_ITEM( state, TRIE_LIST_CUR( state ) ).forid = fid; \
1479 TRIE_LIST_ITEM( state, TRIE_LIST_CUR( state ) ).newstate = ns; \
1480 TRIE_LIST_CUR( state )++; \
1483 #define TRIE_LIST_NEW(state) STMT_START { \
1484 Newxz( trie->states[ state ].trans.list, \
1485 4, reg_trie_trans_le ); \
1486 TRIE_LIST_CUR( state ) = 1; \
1487 TRIE_LIST_LEN( state ) = 4; \
1490 #define TRIE_HANDLE_WORD(state) STMT_START { \
1491 U16 dupe= trie->states[ state ].wordnum; \
1492 regnode * const noper_next = regnext( noper ); \
1495 /* store the word for dumping */ \
1497 if (OP(noper) != NOTHING) \
1498 tmp = newSVpvn_utf8(STRING(noper), STR_LEN(noper), UTF); \
1500 tmp = newSVpvn_utf8( "", 0, UTF ); \
1501 av_push( trie_words, tmp ); \
1505 trie->wordinfo[curword].prev = 0; \
1506 trie->wordinfo[curword].len = wordlen; \
1507 trie->wordinfo[curword].accept = state; \
1509 if ( noper_next < tail ) { \
1511 trie->jump = (U16 *) PerlMemShared_calloc( word_count + 1, sizeof(U16) ); \
1512 trie->jump[curword] = (U16)(noper_next - convert); \
1514 jumper = noper_next; \
1516 nextbranch= regnext(cur); \
1520 /* It's a dupe. Pre-insert into the wordinfo[].prev */\
1521 /* chain, so that when the bits of chain are later */\
1522 /* linked together, the dups appear in the chain */\
1523 trie->wordinfo[curword].prev = trie->wordinfo[dupe].prev; \
1524 trie->wordinfo[dupe].prev = curword; \
1526 /* we haven't inserted this word yet. */ \
1527 trie->states[ state ].wordnum = curword; \
1532 #define TRIE_TRANS_STATE(state,base,ucharcount,charid,special) \
1533 ( ( base + charid >= ucharcount \
1534 && base + charid < ubound \
1535 && state == trie->trans[ base - ucharcount + charid ].check \
1536 && trie->trans[ base - ucharcount + charid ].next ) \
1537 ? trie->trans[ base - ucharcount + charid ].next \
1538 : ( state==1 ? special : 0 ) \
1542 #define MADE_JUMP_TRIE 2
1543 #define MADE_EXACT_TRIE 4
1546 S_make_trie(pTHX_ RExC_state_t *pRExC_state, regnode *startbranch, regnode *first, regnode *last, regnode *tail, U32 word_count, U32 flags, U32 depth)
1549 /* first pass, loop through and scan words */
1550 reg_trie_data *trie;
1551 HV *widecharmap = NULL;
1552 AV *revcharmap = newAV();
1554 const U32 uniflags = UTF8_ALLOW_DEFAULT;
1559 regnode *jumper = NULL;
1560 regnode *nextbranch = NULL;
1561 regnode *convert = NULL;
1562 U32 *prev_states; /* temp array mapping each state to previous one */
1563 /* we just use folder as a flag in utf8 */
1564 const U8 * folder = NULL;
1567 const U32 data_slot = add_data( pRExC_state, 4, "tuuu" );
1568 AV *trie_words = NULL;
1569 /* along with revcharmap, this only used during construction but both are
1570 * useful during debugging so we store them in the struct when debugging.
1573 const U32 data_slot = add_data( pRExC_state, 2, "tu" );
1574 STRLEN trie_charcount=0;
1576 SV *re_trie_maxbuff;
1577 GET_RE_DEBUG_FLAGS_DECL;
1579 PERL_ARGS_ASSERT_MAKE_TRIE;
1581 PERL_UNUSED_ARG(depth);
1588 case EXACTFU_TRICKYFOLD:
1589 case EXACTFU: folder = PL_fold_latin1; break;
1590 case EXACTF: folder = PL_fold; break;
1591 case EXACTFL: folder = PL_fold_locale; break;
1592 default: Perl_croak( aTHX_ "panic! In trie construction, unknown node type %u %s", (unsigned) flags, PL_reg_name[flags] );
1595 trie = (reg_trie_data *) PerlMemShared_calloc( 1, sizeof(reg_trie_data) );
1597 trie->startstate = 1;
1598 trie->wordcount = word_count;
1599 RExC_rxi->data->data[ data_slot ] = (void*)trie;
1600 trie->charmap = (U16 *) PerlMemShared_calloc( 256, sizeof(U16) );
1602 trie->bitmap = (char *) PerlMemShared_calloc( ANYOF_BITMAP_SIZE, 1 );
1603 trie->wordinfo = (reg_trie_wordinfo *) PerlMemShared_calloc(
1604 trie->wordcount+1, sizeof(reg_trie_wordinfo));
1607 trie_words = newAV();
1610 re_trie_maxbuff = get_sv(RE_TRIE_MAXBUF_NAME, 1);
1611 if (!SvIOK(re_trie_maxbuff)) {
1612 sv_setiv(re_trie_maxbuff, RE_TRIE_MAXBUF_INIT);
1614 DEBUG_TRIE_COMPILE_r({
1615 PerlIO_printf( Perl_debug_log,
1616 "%*smake_trie start==%d, first==%d, last==%d, tail==%d depth=%d\n",
1617 (int)depth * 2 + 2, "",
1618 REG_NODE_NUM(startbranch),REG_NODE_NUM(first),
1619 REG_NODE_NUM(last), REG_NODE_NUM(tail),
1623 /* Find the node we are going to overwrite */
1624 if ( first == startbranch && OP( last ) != BRANCH ) {
1625 /* whole branch chain */
1628 /* branch sub-chain */
1629 convert = NEXTOPER( first );
1632 /* -- First loop and Setup --
1634 We first traverse the branches and scan each word to determine if it
1635 contains widechars, and how many unique chars there are, this is
1636 important as we have to build a table with at least as many columns as we
1639 We use an array of integers to represent the character codes 0..255
1640 (trie->charmap) and we use a an HV* to store Unicode characters. We use the
1641 native representation of the character value as the key and IV's for the
1644 *TODO* If we keep track of how many times each character is used we can
1645 remap the columns so that the table compression later on is more
1646 efficient in terms of memory by ensuring the most common value is in the
1647 middle and the least common are on the outside. IMO this would be better
1648 than a most to least common mapping as theres a decent chance the most
1649 common letter will share a node with the least common, meaning the node
1650 will not be compressible. With a middle is most common approach the worst
1651 case is when we have the least common nodes twice.
1655 for ( cur = first ; cur < last ; cur = regnext( cur ) ) {
1656 regnode *noper = NEXTOPER( cur );
1657 const U8 *uc = (U8*)STRING( noper );
1658 const U8 *e = uc + STR_LEN( noper );
1660 U8 foldbuf[ UTF8_MAXBYTES_CASE + 1 ];
1662 const U8 *scan = (U8*)NULL;
1663 U32 wordlen = 0; /* required init */
1665 bool set_bit = trie->bitmap ? 1 : 0; /*store the first char in the bitmap?*/
1667 if (OP(noper) == NOTHING) {
1668 regnode *noper_next= regnext(noper);
1669 if (noper_next != tail && OP(noper_next) == flags) {
1671 uc= (U8*)STRING(noper);
1672 e= uc + STR_LEN(noper);
1673 trie->minlen= STR_LEN(noper);
1680 if ( set_bit ) { /* bitmap only alloced when !(UTF&&Folding) */
1681 TRIE_BITMAP_SET(trie,*uc); /* store the raw first byte
1682 regardless of encoding */
1683 if (OP( noper ) == EXACTFU_SS) {
1684 /* false positives are ok, so just set this */
1685 TRIE_BITMAP_SET(trie,0xDF);
1688 for ( ; uc < e ; uc += len ) {
1689 TRIE_CHARCOUNT(trie)++;
1694 U8 folded= folder[ (U8) uvc ];
1695 if ( !trie->charmap[ folded ] ) {
1696 trie->charmap[ folded ]=( ++trie->uniquecharcount );
1697 TRIE_STORE_REVCHAR( folded );
1700 if ( !trie->charmap[ uvc ] ) {
1701 trie->charmap[ uvc ]=( ++trie->uniquecharcount );
1702 TRIE_STORE_REVCHAR( uvc );
1705 /* store the codepoint in the bitmap, and its folded
1707 TRIE_BITMAP_SET(trie, uvc);
1709 /* store the folded codepoint */
1710 if ( folder ) TRIE_BITMAP_SET(trie, folder[(U8) uvc ]);
1713 /* store first byte of utf8 representation of
1714 variant codepoints */
1715 if (! UNI_IS_INVARIANT(uvc)) {
1716 TRIE_BITMAP_SET(trie, UTF8_TWO_BYTE_HI(uvc));
1719 set_bit = 0; /* We've done our bit :-) */
1724 widecharmap = newHV();
1726 svpp = hv_fetch( widecharmap, (char*)&uvc, sizeof( UV ), 1 );
1729 Perl_croak( aTHX_ "error creating/fetching widecharmap entry for 0x%"UVXf, uvc );
1731 if ( !SvTRUE( *svpp ) ) {
1732 sv_setiv( *svpp, ++trie->uniquecharcount );
1733 TRIE_STORE_REVCHAR(uvc);
1737 if( cur == first ) {
1738 trie->minlen = chars;
1739 trie->maxlen = chars;
1740 } else if (chars < trie->minlen) {
1741 trie->minlen = chars;
1742 } else if (chars > trie->maxlen) {
1743 trie->maxlen = chars;
1745 if (OP( noper ) == EXACTFU_SS) {
1746 /* XXX: workaround - 'ss' could match "\x{DF}" so minlen could be 1 and not 2*/
1747 if (trie->minlen > 1)
1750 if (OP( noper ) == EXACTFU_TRICKYFOLD) {
1751 /* XXX: workround - things like "\x{1FBE}\x{0308}\x{0301}" can match "\x{0390}"
1752 * - We assume that any such sequence might match a 2 byte string */
1753 if (trie->minlen > 2 )
1757 } /* end first pass */
1758 DEBUG_TRIE_COMPILE_r(
1759 PerlIO_printf( Perl_debug_log, "%*sTRIE(%s): W:%d C:%d Uq:%d Min:%d Max:%d\n",
1760 (int)depth * 2 + 2,"",
1761 ( widecharmap ? "UTF8" : "NATIVE" ), (int)word_count,
1762 (int)TRIE_CHARCOUNT(trie), trie->uniquecharcount,
1763 (int)trie->minlen, (int)trie->maxlen )
1767 We now know what we are dealing with in terms of unique chars and
1768 string sizes so we can calculate how much memory a naive
1769 representation using a flat table will take. If it's over a reasonable
1770 limit (as specified by ${^RE_TRIE_MAXBUF}) we use a more memory
1771 conservative but potentially much slower representation using an array
1774 At the end we convert both representations into the same compressed
1775 form that will be used in regexec.c for matching with. The latter
1776 is a form that cannot be used to construct with but has memory
1777 properties similar to the list form and access properties similar
1778 to the table form making it both suitable for fast searches and
1779 small enough that its feasable to store for the duration of a program.
1781 See the comment in the code where the compressed table is produced
1782 inplace from the flat tabe representation for an explanation of how
1783 the compression works.
1788 Newx(prev_states, TRIE_CHARCOUNT(trie) + 2, U32);
1791 if ( (IV)( ( TRIE_CHARCOUNT(trie) + 1 ) * trie->uniquecharcount + 1) > SvIV(re_trie_maxbuff) ) {
1793 Second Pass -- Array Of Lists Representation
1795 Each state will be represented by a list of charid:state records
1796 (reg_trie_trans_le) the first such element holds the CUR and LEN
1797 points of the allocated array. (See defines above).
1799 We build the initial structure using the lists, and then convert
1800 it into the compressed table form which allows faster lookups
1801 (but cant be modified once converted).
1804 STRLEN transcount = 1;
1806 DEBUG_TRIE_COMPILE_MORE_r( PerlIO_printf( Perl_debug_log,
1807 "%*sCompiling trie using list compiler\n",
1808 (int)depth * 2 + 2, ""));
1810 trie->states = (reg_trie_state *)
1811 PerlMemShared_calloc( TRIE_CHARCOUNT(trie) + 2,
1812 sizeof(reg_trie_state) );
1816 for ( cur = first ; cur < last ; cur = regnext( cur ) ) {
1818 regnode *noper = NEXTOPER( cur );
1819 U8 *uc = (U8*)STRING( noper );
1820 const U8 *e = uc + STR_LEN( noper );
1821 U32 state = 1; /* required init */
1822 U16 charid = 0; /* sanity init */
1823 U8 *scan = (U8*)NULL; /* sanity init */
1824 STRLEN foldlen = 0; /* required init */
1825 U32 wordlen = 0; /* required init */
1826 U8 foldbuf[ UTF8_MAXBYTES_CASE + 1 ];
1829 if (OP(noper) == NOTHING) {
1830 regnode *noper_next= regnext(noper);
1831 if (noper_next != tail && OP(noper_next) == flags) {
1833 uc= (U8*)STRING(noper);
1834 e= uc + STR_LEN(noper);
1838 if (OP(noper) != NOTHING) {
1839 for ( ; uc < e ; uc += len ) {
1844 charid = trie->charmap[ uvc ];
1846 SV** const svpp = hv_fetch( widecharmap, (char*)&uvc, sizeof( UV ), 0);
1850 charid=(U16)SvIV( *svpp );
1853 /* charid is now 0 if we dont know the char read, or nonzero if we do */
1860 if ( !trie->states[ state ].trans.list ) {
1861 TRIE_LIST_NEW( state );
1863 for ( check = 1; check <= TRIE_LIST_USED( state ); check++ ) {
1864 if ( TRIE_LIST_ITEM( state, check ).forid == charid ) {
1865 newstate = TRIE_LIST_ITEM( state, check ).newstate;
1870 newstate = next_alloc++;
1871 prev_states[newstate] = state;
1872 TRIE_LIST_PUSH( state, charid, newstate );
1877 Perl_croak( aTHX_ "panic! In trie construction, no char mapping for %"IVdf, uvc );
1881 TRIE_HANDLE_WORD(state);
1883 } /* end second pass */
1885 /* next alloc is the NEXT state to be allocated */
1886 trie->statecount = next_alloc;
1887 trie->states = (reg_trie_state *)
1888 PerlMemShared_realloc( trie->states,
1890 * sizeof(reg_trie_state) );
1892 /* and now dump it out before we compress it */
1893 DEBUG_TRIE_COMPILE_MORE_r(dump_trie_interim_list(trie, widecharmap,
1894 revcharmap, next_alloc,
1898 trie->trans = (reg_trie_trans *)
1899 PerlMemShared_calloc( transcount, sizeof(reg_trie_trans) );
1906 for( state=1 ; state < next_alloc ; state ++ ) {
1910 DEBUG_TRIE_COMPILE_MORE_r(
1911 PerlIO_printf( Perl_debug_log, "tp: %d zp: %d ",tp,zp)
1915 if (trie->states[state].trans.list) {
1916 U16 minid=TRIE_LIST_ITEM( state, 1).forid;
1920 for( idx = 2 ; idx <= TRIE_LIST_USED( state ) ; idx++ ) {
1921 const U16 forid = TRIE_LIST_ITEM( state, idx).forid;
1922 if ( forid < minid ) {
1924 } else if ( forid > maxid ) {
1928 if ( transcount < tp + maxid - minid + 1) {
1930 trie->trans = (reg_trie_trans *)
1931 PerlMemShared_realloc( trie->trans,
1933 * sizeof(reg_trie_trans) );
1934 Zero( trie->trans + (transcount / 2), transcount / 2 , reg_trie_trans );
1936 base = trie->uniquecharcount + tp - minid;
1937 if ( maxid == minid ) {
1939 for ( ; zp < tp ; zp++ ) {
1940 if ( ! trie->trans[ zp ].next ) {
1941 base = trie->uniquecharcount + zp - minid;
1942 trie->trans[ zp ].next = TRIE_LIST_ITEM( state, 1).newstate;
1943 trie->trans[ zp ].check = state;
1949 trie->trans[ tp ].next = TRIE_LIST_ITEM( state, 1).newstate;
1950 trie->trans[ tp ].check = state;
1955 for ( idx=1; idx <= TRIE_LIST_USED( state ) ; idx++ ) {
1956 const U32 tid = base - trie->uniquecharcount + TRIE_LIST_ITEM( state, idx ).forid;
1957 trie->trans[ tid ].next = TRIE_LIST_ITEM( state, idx ).newstate;
1958 trie->trans[ tid ].check = state;
1960 tp += ( maxid - minid + 1 );
1962 Safefree(trie->states[ state ].trans.list);
1965 DEBUG_TRIE_COMPILE_MORE_r(
1966 PerlIO_printf( Perl_debug_log, " base: %d\n",base);
1969 trie->states[ state ].trans.base=base;
1971 trie->lasttrans = tp + 1;
1975 Second Pass -- Flat Table Representation.
1977 we dont use the 0 slot of either trans[] or states[] so we add 1 to each.
1978 We know that we will need Charcount+1 trans at most to store the data
1979 (one row per char at worst case) So we preallocate both structures
1980 assuming worst case.
1982 We then construct the trie using only the .next slots of the entry
1985 We use the .check field of the first entry of the node temporarily to
1986 make compression both faster and easier by keeping track of how many non
1987 zero fields are in the node.
1989 Since trans are numbered from 1 any 0 pointer in the table is a FAIL
1992 There are two terms at use here: state as a TRIE_NODEIDX() which is a
1993 number representing the first entry of the node, and state as a
1994 TRIE_NODENUM() which is the trans number. state 1 is TRIE_NODEIDX(1) and
1995 TRIE_NODENUM(1), state 2 is TRIE_NODEIDX(2) and TRIE_NODENUM(3) if there
1996 are 2 entrys per node. eg:
2004 The table is internally in the right hand, idx form. However as we also
2005 have to deal with the states array which is indexed by nodenum we have to
2006 use TRIE_NODENUM() to convert.
2009 DEBUG_TRIE_COMPILE_MORE_r( PerlIO_printf( Perl_debug_log,
2010 "%*sCompiling trie using table compiler\n",
2011 (int)depth * 2 + 2, ""));
2013 trie->trans = (reg_trie_trans *)
2014 PerlMemShared_calloc( ( TRIE_CHARCOUNT(trie) + 1 )
2015 * trie->uniquecharcount + 1,
2016 sizeof(reg_trie_trans) );
2017 trie->states = (reg_trie_state *)
2018 PerlMemShared_calloc( TRIE_CHARCOUNT(trie) + 2,
2019 sizeof(reg_trie_state) );
2020 next_alloc = trie->uniquecharcount + 1;
2023 for ( cur = first ; cur < last ; cur = regnext( cur ) ) {
2025 regnode *noper = NEXTOPER( cur );
2026 const U8 *uc = (U8*)STRING( noper );
2027 const U8 *e = uc + STR_LEN( noper );
2029 U32 state = 1; /* required init */
2031 U16 charid = 0; /* sanity init */
2032 U32 accept_state = 0; /* sanity init */
2033 U8 *scan = (U8*)NULL; /* sanity init */
2035 STRLEN foldlen = 0; /* required init */
2036 U32 wordlen = 0; /* required init */
2038 U8 foldbuf[ UTF8_MAXBYTES_CASE + 1 ];
2040 if (OP(noper) == NOTHING) {
2041 regnode *noper_next= regnext(noper);
2042 if (noper_next != tail && OP(noper_next) == flags) {
2044 uc= (U8*)STRING(noper);
2045 e= uc + STR_LEN(noper);
2049 if ( OP(noper) != NOTHING ) {
2050 for ( ; uc < e ; uc += len ) {
2055 charid = trie->charmap[ uvc ];
2057 SV* const * const svpp = hv_fetch( widecharmap, (char*)&uvc, sizeof( UV ), 0);
2058 charid = svpp ? (U16)SvIV(*svpp) : 0;
2062 if ( !trie->trans[ state + charid ].next ) {
2063 trie->trans[ state + charid ].next = next_alloc;
2064 trie->trans[ state ].check++;
2065 prev_states[TRIE_NODENUM(next_alloc)]
2066 = TRIE_NODENUM(state);
2067 next_alloc += trie->uniquecharcount;
2069 state = trie->trans[ state + charid ].next;
2071 Perl_croak( aTHX_ "panic! In trie construction, no char mapping for %"IVdf, uvc );
2073 /* charid is now 0 if we dont know the char read, or nonzero if we do */
2076 accept_state = TRIE_NODENUM( state );
2077 TRIE_HANDLE_WORD(accept_state);
2079 } /* end second pass */
2081 /* and now dump it out before we compress it */
2082 DEBUG_TRIE_COMPILE_MORE_r(dump_trie_interim_table(trie, widecharmap,
2084 next_alloc, depth+1));
2088 * Inplace compress the table.*
2090 For sparse data sets the table constructed by the trie algorithm will
2091 be mostly 0/FAIL transitions or to put it another way mostly empty.
2092 (Note that leaf nodes will not contain any transitions.)
2094 This algorithm compresses the tables by eliminating most such
2095 transitions, at the cost of a modest bit of extra work during lookup:
2097 - Each states[] entry contains a .base field which indicates the
2098 index in the state[] array wheres its transition data is stored.
2100 - If .base is 0 there are no valid transitions from that node.
2102 - If .base is nonzero then charid is added to it to find an entry in
2105 -If trans[states[state].base+charid].check!=state then the
2106 transition is taken to be a 0/Fail transition. Thus if there are fail
2107 transitions at the front of the node then the .base offset will point
2108 somewhere inside the previous nodes data (or maybe even into a node
2109 even earlier), but the .check field determines if the transition is
2113 The following process inplace converts the table to the compressed
2114 table: We first do not compress the root node 1,and mark all its
2115 .check pointers as 1 and set its .base pointer as 1 as well. This
2116 allows us to do a DFA construction from the compressed table later,
2117 and ensures that any .base pointers we calculate later are greater
2120 - We set 'pos' to indicate the first entry of the second node.
2122 - We then iterate over the columns of the node, finding the first and
2123 last used entry at l and m. We then copy l..m into pos..(pos+m-l),
2124 and set the .check pointers accordingly, and advance pos
2125 appropriately and repreat for the next node. Note that when we copy
2126 the next pointers we have to convert them from the original
2127 NODEIDX form to NODENUM form as the former is not valid post
2130 - If a node has no transitions used we mark its base as 0 and do not
2131 advance the pos pointer.
2133 - If a node only has one transition we use a second pointer into the
2134 structure to fill in allocated fail transitions from other states.
2135 This pointer is independent of the main pointer and scans forward
2136 looking for null transitions that are allocated to a state. When it
2137 finds one it writes the single transition into the "hole". If the
2138 pointer doesnt find one the single transition is appended as normal.
2140 - Once compressed we can Renew/realloc the structures to release the
2143 See "Table-Compression Methods" in sec 3.9 of the Red Dragon,
2144 specifically Fig 3.47 and the associated pseudocode.
2148 const U32 laststate = TRIE_NODENUM( next_alloc );
2151 trie->statecount = laststate;
2153 for ( state = 1 ; state < laststate ; state++ ) {
2155 const U32 stateidx = TRIE_NODEIDX( state );
2156 const U32 o_used = trie->trans[ stateidx ].check;
2157 U32 used = trie->trans[ stateidx ].check;
2158 trie->trans[ stateidx ].check = 0;
2160 for ( charid = 0 ; used && charid < trie->uniquecharcount ; charid++ ) {
2161 if ( flag || trie->trans[ stateidx + charid ].next ) {
2162 if ( trie->trans[ stateidx + charid ].next ) {
2164 for ( ; zp < pos ; zp++ ) {
2165 if ( ! trie->trans[ zp ].next ) {
2169 trie->states[ state ].trans.base = zp + trie->uniquecharcount - charid ;
2170 trie->trans[ zp ].next = SAFE_TRIE_NODENUM( trie->trans[ stateidx + charid ].next );
2171 trie->trans[ zp ].check = state;
2172 if ( ++zp > pos ) pos = zp;
2179 trie->states[ state ].trans.base = pos + trie->uniquecharcount - charid ;
2181 trie->trans[ pos ].next = SAFE_TRIE_NODENUM( trie->trans[ stateidx + charid ].next );
2182 trie->trans[ pos ].check = state;
2187 trie->lasttrans = pos + 1;
2188 trie->states = (reg_trie_state *)
2189 PerlMemShared_realloc( trie->states, laststate
2190 * sizeof(reg_trie_state) );
2191 DEBUG_TRIE_COMPILE_MORE_r(
2192 PerlIO_printf( Perl_debug_log,
2193 "%*sAlloc: %d Orig: %"IVdf" elements, Final:%"IVdf". Savings of %%%5.2f\n",
2194 (int)depth * 2 + 2,"",
2195 (int)( ( TRIE_CHARCOUNT(trie) + 1 ) * trie->uniquecharcount + 1 ),
2198 ( ( next_alloc - pos ) * 100 ) / (double)next_alloc );
2201 } /* end table compress */
2203 DEBUG_TRIE_COMPILE_MORE_r(
2204 PerlIO_printf(Perl_debug_log, "%*sStatecount:%"UVxf" Lasttrans:%"UVxf"\n",
2205 (int)depth * 2 + 2, "",
2206 (UV)trie->statecount,
2207 (UV)trie->lasttrans)
2209 /* resize the trans array to remove unused space */
2210 trie->trans = (reg_trie_trans *)
2211 PerlMemShared_realloc( trie->trans, trie->lasttrans
2212 * sizeof(reg_trie_trans) );
2214 { /* Modify the program and insert the new TRIE node */
2215 U8 nodetype =(U8)(flags & 0xFF);
2219 regnode *optimize = NULL;
2220 #ifdef RE_TRACK_PATTERN_OFFSETS
2223 U32 mjd_nodelen = 0;
2224 #endif /* RE_TRACK_PATTERN_OFFSETS */
2225 #endif /* DEBUGGING */
2227 This means we convert either the first branch or the first Exact,
2228 depending on whether the thing following (in 'last') is a branch
2229 or not and whther first is the startbranch (ie is it a sub part of
2230 the alternation or is it the whole thing.)
2231 Assuming its a sub part we convert the EXACT otherwise we convert
2232 the whole branch sequence, including the first.
2234 /* Find the node we are going to overwrite */
2235 if ( first != startbranch || OP( last ) == BRANCH ) {
2236 /* branch sub-chain */
2237 NEXT_OFF( first ) = (U16)(last - first);
2238 #ifdef RE_TRACK_PATTERN_OFFSETS
2240 mjd_offset= Node_Offset((convert));
2241 mjd_nodelen= Node_Length((convert));
2244 /* whole branch chain */
2246 #ifdef RE_TRACK_PATTERN_OFFSETS
2249 const regnode *nop = NEXTOPER( convert );
2250 mjd_offset= Node_Offset((nop));
2251 mjd_nodelen= Node_Length((nop));
2255 PerlIO_printf(Perl_debug_log, "%*sMJD offset:%"UVuf" MJD length:%"UVuf"\n",
2256 (int)depth * 2 + 2, "",
2257 (UV)mjd_offset, (UV)mjd_nodelen)
2260 /* But first we check to see if there is a common prefix we can
2261 split out as an EXACT and put in front of the TRIE node. */
2262 trie->startstate= 1;
2263 if ( trie->bitmap && !widecharmap && !trie->jump ) {
2265 for ( state = 1 ; state < trie->statecount-1 ; state++ ) {
2269 const U32 base = trie->states[ state ].trans.base;
2271 if ( trie->states[state].wordnum )
2274 for ( ofs = 0 ; ofs < trie->uniquecharcount ; ofs++ ) {
2275 if ( ( base + ofs >= trie->uniquecharcount ) &&
2276 ( base + ofs - trie->uniquecharcount < trie->lasttrans ) &&
2277 trie->trans[ base + ofs - trie->uniquecharcount ].check == state )
2279 if ( ++count > 1 ) {
2280 SV **tmp = av_fetch( revcharmap, ofs, 0);
2281 const U8 *ch = (U8*)SvPV_nolen_const( *tmp );
2282 if ( state == 1 ) break;
2284 Zero(trie->bitmap, ANYOF_BITMAP_SIZE, char);
2286 PerlIO_printf(Perl_debug_log,
2287 "%*sNew Start State=%"UVuf" Class: [",
2288 (int)depth * 2 + 2, "",
2291 SV ** const tmp = av_fetch( revcharmap, idx, 0);
2292 const U8 * const ch = (U8*)SvPV_nolen_const( *tmp );
2294 TRIE_BITMAP_SET(trie,*ch);
2296 TRIE_BITMAP_SET(trie, folder[ *ch ]);
2298 PerlIO_printf(Perl_debug_log, "%s", (char*)ch)
2302 TRIE_BITMAP_SET(trie,*ch);
2304 TRIE_BITMAP_SET(trie,folder[ *ch ]);
2305 DEBUG_OPTIMISE_r(PerlIO_printf( Perl_debug_log,"%s", ch));
2311 SV **tmp = av_fetch( revcharmap, idx, 0);
2313 char *ch = SvPV( *tmp, len );
2315 SV *sv=sv_newmortal();
2316 PerlIO_printf( Perl_debug_log,
2317 "%*sPrefix State: %"UVuf" Idx:%"UVuf" Char='%s'\n",
2318 (int)depth * 2 + 2, "",
2320 pv_pretty(sv, SvPV_nolen_const(*tmp), SvCUR(*tmp), 6,
2321 PL_colors[0], PL_colors[1],
2322 (SvUTF8(*tmp) ? PERL_PV_ESCAPE_UNI : 0) |
2323 PERL_PV_ESCAPE_FIRSTCHAR
2328 OP( convert ) = nodetype;
2329 str=STRING(convert);
2332 STR_LEN(convert) += len;
2338 DEBUG_OPTIMISE_r(PerlIO_printf( Perl_debug_log,"]\n"));
2343 trie->prefixlen = (state-1);
2345 regnode *n = convert+NODE_SZ_STR(convert);
2346 NEXT_OFF(convert) = NODE_SZ_STR(convert);
2347 trie->startstate = state;
2348 trie->minlen -= (state - 1);
2349 trie->maxlen -= (state - 1);
2351 /* At least the UNICOS C compiler choked on this
2352 * being argument to DEBUG_r(), so let's just have
2355 #ifdef PERL_EXT_RE_BUILD
2361 regnode *fix = convert;
2362 U32 word = trie->wordcount;
2364 Set_Node_Offset_Length(convert, mjd_offset, state - 1);
2365 while( ++fix < n ) {
2366 Set_Node_Offset_Length(fix, 0, 0);
2369 SV ** const tmp = av_fetch( trie_words, word, 0 );
2371 if ( STR_LEN(convert) <= SvCUR(*tmp) )
2372 sv_chop(*tmp, SvPV_nolen(*tmp) + STR_LEN(convert));
2374 sv_chop(*tmp, SvPV_nolen(*tmp) + SvCUR(*tmp));
2382 NEXT_OFF(convert) = (U16)(tail - convert);
2383 DEBUG_r(optimize= n);
2389 if ( trie->maxlen ) {
2390 NEXT_OFF( convert ) = (U16)(tail - convert);
2391 ARG_SET( convert, data_slot );
2392 /* Store the offset to the first unabsorbed branch in
2393 jump[0], which is otherwise unused by the jump logic.
2394 We use this when dumping a trie and during optimisation. */
2396 trie->jump[0] = (U16)(nextbranch - convert);
2398 /* If the start state is not accepting (meaning there is no empty string/NOTHING)
2399 * and there is a bitmap
2400 * and the first "jump target" node we found leaves enough room
2401 * then convert the TRIE node into a TRIEC node, with the bitmap
2402 * embedded inline in the opcode - this is hypothetically faster.
2404 if ( !trie->states[trie->startstate].wordnum
2406 && ( (char *)jumper - (char *)convert) >= (int)sizeof(struct regnode_charclass) )
2408 OP( convert ) = TRIEC;
2409 Copy(trie->bitmap, ((struct regnode_charclass *)convert)->bitmap, ANYOF_BITMAP_SIZE, char);
2410 PerlMemShared_free(trie->bitmap);
2413 OP( convert ) = TRIE;
2415 /* store the type in the flags */
2416 convert->flags = nodetype;
2420 + regarglen[ OP( convert ) ];
2422 /* XXX We really should free up the resource in trie now,
2423 as we won't use them - (which resources?) dmq */
2425 /* needed for dumping*/
2426 DEBUG_r(if (optimize) {
2427 regnode *opt = convert;
2429 while ( ++opt < optimize) {
2430 Set_Node_Offset_Length(opt,0,0);
2433 Try to clean up some of the debris left after the
2436 while( optimize < jumper ) {
2437 mjd_nodelen += Node_Length((optimize));
2438 OP( optimize ) = OPTIMIZED;
2439 Set_Node_Offset_Length(optimize,0,0);
2442 Set_Node_Offset_Length(convert,mjd_offset,mjd_nodelen);
2444 } /* end node insert */
2446 /* Finish populating the prev field of the wordinfo array. Walk back
2447 * from each accept state until we find another accept state, and if
2448 * so, point the first word's .prev field at the second word. If the
2449 * second already has a .prev field set, stop now. This will be the
2450 * case either if we've already processed that word's accept state,
2451 * or that state had multiple words, and the overspill words were
2452 * already linked up earlier.
2459 for (word=1; word <= trie->wordcount; word++) {
2461 if (trie->wordinfo[word].prev)
2463 state = trie->wordinfo[word].accept;
2465 state = prev_states[state];
2468 prev = trie->states[state].wordnum;
2472 trie->wordinfo[word].prev = prev;
2474 Safefree(prev_states);
2478 /* and now dump out the compressed format */
2479 DEBUG_TRIE_COMPILE_r(dump_trie(trie, widecharmap, revcharmap, depth+1));
2481 RExC_rxi->data->data[ data_slot + 1 ] = (void*)widecharmap;
2483 RExC_rxi->data->data[ data_slot + TRIE_WORDS_OFFSET ] = (void*)trie_words;
2484 RExC_rxi->data->data[ data_slot + 3 ] = (void*)revcharmap;
2486 SvREFCNT_dec_NN(revcharmap);
2490 : trie->startstate>1
2496 S_make_trie_failtable(pTHX_ RExC_state_t *pRExC_state, regnode *source, regnode *stclass, U32 depth)
2498 /* The Trie is constructed and compressed now so we can build a fail array if it's needed
2500 This is basically the Aho-Corasick algorithm. Its from exercise 3.31 and 3.32 in the
2501 "Red Dragon" -- Compilers, principles, techniques, and tools. Aho, Sethi, Ullman 1985/88
2504 We find the fail state for each state in the trie, this state is the longest proper
2505 suffix of the current state's 'word' that is also a proper prefix of another word in our
2506 trie. State 1 represents the word '' and is thus the default fail state. This allows
2507 the DFA not to have to restart after its tried and failed a word at a given point, it
2508 simply continues as though it had been matching the other word in the first place.
2510 'abcdgu'=~/abcdefg|cdgu/
2511 When we get to 'd' we are still matching the first word, we would encounter 'g' which would
2512 fail, which would bring us to the state representing 'd' in the second word where we would
2513 try 'g' and succeed, proceeding to match 'cdgu'.
2515 /* add a fail transition */
2516 const U32 trie_offset = ARG(source);
2517 reg_trie_data *trie=(reg_trie_data *)RExC_rxi->data->data[trie_offset];
2519 const U32 ucharcount = trie->uniquecharcount;
2520 const U32 numstates = trie->statecount;
2521 const U32 ubound = trie->lasttrans + ucharcount;
2525 U32 base = trie->states[ 1 ].trans.base;
2528 const U32 data_slot = add_data( pRExC_state, 1, "T" );
2529 GET_RE_DEBUG_FLAGS_DECL;
2531 PERL_ARGS_ASSERT_MAKE_TRIE_FAILTABLE;
2533 PERL_UNUSED_ARG(depth);
2537 ARG_SET( stclass, data_slot );
2538 aho = (reg_ac_data *) PerlMemShared_calloc( 1, sizeof(reg_ac_data) );
2539 RExC_rxi->data->data[ data_slot ] = (void*)aho;
2540 aho->trie=trie_offset;
2541 aho->states=(reg_trie_state *)PerlMemShared_malloc( numstates * sizeof(reg_trie_state) );
2542 Copy( trie->states, aho->states, numstates, reg_trie_state );
2543 Newxz( q, numstates, U32);
2544 aho->fail = (U32 *) PerlMemShared_calloc( numstates, sizeof(U32) );
2547 /* initialize fail[0..1] to be 1 so that we always have
2548 a valid final fail state */
2549 fail[ 0 ] = fail[ 1 ] = 1;
2551 for ( charid = 0; charid < ucharcount ; charid++ ) {
2552 const U32 newstate = TRIE_TRANS_STATE( 1, base, ucharcount, charid, 0 );
2554 q[ q_write ] = newstate;
2555 /* set to point at the root */
2556 fail[ q[ q_write++ ] ]=1;
2559 while ( q_read < q_write) {
2560 const U32 cur = q[ q_read++ % numstates ];
2561 base = trie->states[ cur ].trans.base;
2563 for ( charid = 0 ; charid < ucharcount ; charid++ ) {
2564 const U32 ch_state = TRIE_TRANS_STATE( cur, base, ucharcount, charid, 1 );
2566 U32 fail_state = cur;
2569 fail_state = fail[ fail_state ];
2570 fail_base = aho->states[ fail_state ].trans.base;
2571 } while ( !TRIE_TRANS_STATE( fail_state, fail_base, ucharcount, charid, 1 ) );
2573 fail_state = TRIE_TRANS_STATE( fail_state, fail_base, ucharcount, charid, 1 );
2574 fail[ ch_state ] = fail_state;
2575 if ( !aho->states[ ch_state ].wordnum && aho->states[ fail_state ].wordnum )
2577 aho->states[ ch_state ].wordnum = aho->states[ fail_state ].wordnum;
2579 q[ q_write++ % numstates] = ch_state;
2583 /* restore fail[0..1] to 0 so that we "fall out" of the AC loop
2584 when we fail in state 1, this allows us to use the
2585 charclass scan to find a valid start char. This is based on the principle
2586 that theres a good chance the string being searched contains lots of stuff
2587 that cant be a start char.
2589 fail[ 0 ] = fail[ 1 ] = 0;
2590 DEBUG_TRIE_COMPILE_r({
2591 PerlIO_printf(Perl_debug_log,
2592 "%*sStclass Failtable (%"UVuf" states): 0",
2593 (int)(depth * 2), "", (UV)numstates
2595 for( q_read=1; q_read<numstates; q_read++ ) {
2596 PerlIO_printf(Perl_debug_log, ", %"UVuf, (UV)fail[q_read]);
2598 PerlIO_printf(Perl_debug_log, "\n");
2601 /*RExC_seen |= REG_SEEN_TRIEDFA;*/
2606 * There are strange code-generation bugs caused on sparc64 by gcc-2.95.2.
2607 * These need to be revisited when a newer toolchain becomes available.
2609 #if defined(__sparc64__) && defined(__GNUC__)
2610 # if __GNUC__ < 2 || (__GNUC__ == 2 && __GNUC_MINOR__ < 96)
2611 # undef SPARC64_GCC_WORKAROUND
2612 # define SPARC64_GCC_WORKAROUND 1
2616 #define DEBUG_PEEP(str,scan,depth) \
2617 DEBUG_OPTIMISE_r({if (scan){ \
2618 SV * const mysv=sv_newmortal(); \
2619 regnode *Next = regnext(scan); \
2620 regprop(RExC_rx, mysv, scan); \
2621 PerlIO_printf(Perl_debug_log, "%*s" str ">%3d: %s (%d)\n", \
2622 (int)depth*2, "", REG_NODE_NUM(scan), SvPV_nolen_const(mysv),\
2623 Next ? (REG_NODE_NUM(Next)) : 0 ); \
2627 /* The below joins as many adjacent EXACTish nodes as possible into a single
2628 * one. The regop may be changed if the node(s) contain certain sequences that
2629 * require special handling. The joining is only done if:
2630 * 1) there is room in the current conglomerated node to entirely contain the
2632 * 2) they are the exact same node type
2634 * The adjacent nodes actually may be separated by NOTHING-kind nodes, and
2635 * these get optimized out
2637 * If a node is to match under /i (folded), the number of characters it matches
2638 * can be different than its character length if it contains a multi-character
2639 * fold. *min_subtract is set to the total delta of the input nodes.
2641 * And *has_exactf_sharp_s is set to indicate whether or not the node is EXACTF
2642 * and contains LATIN SMALL LETTER SHARP S
2644 * This is as good a place as any to discuss the design of handling these
2645 * multi-character fold sequences. It's been wrong in Perl for a very long
2646 * time. There are three code points in Unicode whose multi-character folds
2647 * were long ago discovered to mess things up. The previous designs for
2648 * dealing with these involved assigning a special node for them. This
2649 * approach doesn't work, as evidenced by this example:
2650 * "\xDFs" =~ /s\xDF/ui # Used to fail before these patches
2651 * Both these fold to "sss", but if the pattern is parsed to create a node that
2652 * would match just the \xDF, it won't be able to handle the case where a
2653 * successful match would have to cross the node's boundary. The new approach
2654 * that hopefully generally solves the problem generates an EXACTFU_SS node
2657 * It turns out that there are problems with all multi-character folds, and not
2658 * just these three. Now the code is general, for all such cases, but the
2659 * three still have some special handling. The approach taken is:
2660 * 1) This routine examines each EXACTFish node that could contain multi-
2661 * character fold sequences. It returns in *min_subtract how much to
2662 * subtract from the the actual length of the string to get a real minimum
2663 * match length; it is 0 if there are no multi-char folds. This delta is
2664 * used by the caller to adjust the min length of the match, and the delta
2665 * between min and max, so that the optimizer doesn't reject these
2666 * possibilities based on size constraints.
2667 * 2) Certain of these sequences require special handling by the trie code,
2668 * so, if found, this code changes the joined node type to special ops:
2669 * EXACTFU_TRICKYFOLD and EXACTFU_SS.
2670 * 3) For the sequence involving the Sharp s (\xDF), the node type EXACTFU_SS
2671 * is used for an EXACTFU node that contains at least one "ss" sequence in
2672 * it. For non-UTF-8 patterns and strings, this is the only case where
2673 * there is a possible fold length change. That means that a regular
2674 * EXACTFU node without UTF-8 involvement doesn't have to concern itself
2675 * with length changes, and so can be processed faster. regexec.c takes
2676 * advantage of this. Generally, an EXACTFish node that is in UTF-8 is
2677 * pre-folded by regcomp.c. This saves effort in regex matching.
2678 * However, the pre-folding isn't done for non-UTF8 patterns because the
2679 * fold of the MICRO SIGN requires UTF-8, and we don't want to slow things
2680 * down by forcing the pattern into UTF8 unless necessary. Also what
2681 * EXACTF and EXACTFL nodes fold to isn't known until runtime. The fold
2682 * possibilities for the non-UTF8 patterns are quite simple, except for
2683 * the sharp s. All the ones that don't involve a UTF-8 target string are
2684 * members of a fold-pair, and arrays are set up for all of them so that
2685 * the other member of the pair can be found quickly. Code elsewhere in
2686 * this file makes sure that in EXACTFU nodes, the sharp s gets folded to
2687 * 'ss', even if the pattern isn't UTF-8. This avoids the issues
2688 * described in the next item.
2689 * 4) A problem remains for the sharp s in EXACTF and EXACTFA nodes when the
2690 * pattern isn't in UTF-8. (BTW, there cannot be an EXACTF node with a
2691 * UTF-8 pattern.) An assumption that the optimizer part of regexec.c
2692 * (probably unwittingly, in Perl_regexec_flags()) makes is that a
2693 * character in the pattern corresponds to at most a single character in
2694 * the target string. (And I do mean character, and not byte here, unlike
2695 * other parts of the documentation that have never been updated to
2696 * account for multibyte Unicode.) sharp s in EXACTF nodes can match the
2697 * two character string 'ss'; in EXACTFA nodes it can match
2698 * "\x{17F}\x{17F}". These violate the assumption, and they are the only
2699 * instances where it is violated. I'm reluctant to try to change the
2700 * assumption, as the code involved is impenetrable to me (khw), so
2701 * instead the code here punts. This routine examines (when the pattern
2702 * isn't UTF-8) EXACTF and EXACTFA nodes for the sharp s, and returns a
2703 * boolean indicating whether or not the node contains a sharp s. When it
2704 * is true, the caller sets a flag that later causes the optimizer in this
2705 * file to not set values for the floating and fixed string lengths, and
2706 * thus avoids the optimizer code in regexec.c that makes the invalid
2707 * assumption. Thus, there is no optimization based on string lengths for
2708 * non-UTF8-pattern EXACTF and EXACTFA nodes that contain the sharp s.
2709 * (The reason the assumption is wrong only in these two cases is that all
2710 * other non-UTF-8 folds are 1-1; and, for UTF-8 patterns, we pre-fold all
2711 * other folds to their expanded versions. We can't prefold sharp s to
2712 * 'ss' in EXACTF nodes because we don't know at compile time if it
2713 * actually matches 'ss' or not. It will match iff the target string is
2714 * in UTF-8, unlike the EXACTFU nodes, where it always matches; and
2715 * EXACTFA and EXACTFL where it never does. In an EXACTFA node in a UTF-8
2716 * pattern, sharp s is folded to "\x{17F}\x{17F}, avoiding the problem;
2717 * but in a non-UTF8 pattern, folding it to that above-Latin1 string would
2718 * require the pattern to be forced into UTF-8, the overhead of which we
2722 #define JOIN_EXACT(scan,min_subtract,has_exactf_sharp_s, flags) \
2723 if (PL_regkind[OP(scan)] == EXACT) \
2724 join_exact(pRExC_state,(scan),(min_subtract),has_exactf_sharp_s, (flags),NULL,depth+1)
2727 S_join_exact(pTHX_ RExC_state_t *pRExC_state, regnode *scan, UV *min_subtract, bool *has_exactf_sharp_s, U32 flags,regnode *val, U32 depth) {
2728 /* Merge several consecutive EXACTish nodes into one. */
2729 regnode *n = regnext(scan);
2731 regnode *next = scan + NODE_SZ_STR(scan);
2735 regnode *stop = scan;
2736 GET_RE_DEBUG_FLAGS_DECL;
2738 PERL_UNUSED_ARG(depth);
2741 PERL_ARGS_ASSERT_JOIN_EXACT;
2742 #ifndef EXPERIMENTAL_INPLACESCAN
2743 PERL_UNUSED_ARG(flags);
2744 PERL_UNUSED_ARG(val);
2746 DEBUG_PEEP("join",scan,depth);
2748 /* Look through the subsequent nodes in the chain. Skip NOTHING, merge
2749 * EXACT ones that are mergeable to the current one. */
2751 && (PL_regkind[OP(n)] == NOTHING
2752 || (stringok && OP(n) == OP(scan)))
2754 && NEXT_OFF(scan) + NEXT_OFF(n) < I16_MAX)
2757 if (OP(n) == TAIL || n > next)
2759 if (PL_regkind[OP(n)] == NOTHING) {
2760 DEBUG_PEEP("skip:",n,depth);
2761 NEXT_OFF(scan) += NEXT_OFF(n);
2762 next = n + NODE_STEP_REGNODE;
2769 else if (stringok) {
2770 const unsigned int oldl = STR_LEN(scan);
2771 regnode * const nnext = regnext(n);
2773 /* XXX I (khw) kind of doubt that this works on platforms where
2774 * U8_MAX is above 255 because of lots of other assumptions */
2775 /* Don't join if the sum can't fit into a single node */
2776 if (oldl + STR_LEN(n) > U8_MAX)
2779 DEBUG_PEEP("merg",n,depth);
2782 NEXT_OFF(scan) += NEXT_OFF(n);
2783 STR_LEN(scan) += STR_LEN(n);
2784 next = n + NODE_SZ_STR(n);
2785 /* Now we can overwrite *n : */
2786 Move(STRING(n), STRING(scan) + oldl, STR_LEN(n), char);
2794 #ifdef EXPERIMENTAL_INPLACESCAN
2795 if (flags && !NEXT_OFF(n)) {
2796 DEBUG_PEEP("atch", val, depth);
2797 if (reg_off_by_arg[OP(n)]) {
2798 ARG_SET(n, val - n);
2801 NEXT_OFF(n) = val - n;
2809 *has_exactf_sharp_s = FALSE;
2811 /* Here, all the adjacent mergeable EXACTish nodes have been merged. We
2812 * can now analyze for sequences of problematic code points. (Prior to
2813 * this final joining, sequences could have been split over boundaries, and
2814 * hence missed). The sequences only happen in folding, hence for any
2815 * non-EXACT EXACTish node */
2816 if (OP(scan) != EXACT) {
2817 const U8 * const s0 = (U8*) STRING(scan);
2819 const U8 * const s_end = s0 + STR_LEN(scan);
2821 /* One pass is made over the node's string looking for all the
2822 * possibilities. to avoid some tests in the loop, there are two main
2823 * cases, for UTF-8 patterns (which can't have EXACTF nodes) and
2827 /* Examine the string for a multi-character fold sequence. UTF-8
2828 * patterns have all characters pre-folded by the time this code is
2830 while (s < s_end - 1) /* Can stop 1 before the end, as minimum
2831 length sequence we are looking for is 2 */
2834 int len = is_MULTI_CHAR_FOLD_utf8_safe(s, s_end);
2835 if (! len) { /* Not a multi-char fold: get next char */
2840 /* Nodes with 'ss' require special handling, except for EXACTFL
2841 * and EXACTFA for which there is no multi-char fold to this */
2842 if (len == 2 && *s == 's' && *(s+1) == 's'
2843 && OP(scan) != EXACTFL && OP(scan) != EXACTFA)
2846 OP(scan) = EXACTFU_SS;
2849 else if (len == 6 /* len is the same in both ASCII and EBCDIC
2851 && (memEQ(s, GREEK_SMALL_LETTER_IOTA_UTF8
2852 COMBINING_DIAERESIS_UTF8
2853 COMBINING_ACUTE_ACCENT_UTF8,
2855 || memEQ(s, GREEK_SMALL_LETTER_UPSILON_UTF8
2856 COMBINING_DIAERESIS_UTF8
2857 COMBINING_ACUTE_ACCENT_UTF8,
2862 /* These two folds require special handling by trie's, so
2863 * change the node type to indicate this. If EXACTFA and
2864 * EXACTFL were ever to be handled by trie's, this would
2865 * have to be changed. If this node has already been
2866 * changed to EXACTFU_SS in this loop, leave it as is. (I
2867 * (khw) think it doesn't matter in regexec.c for UTF
2868 * patterns, but no need to change it */
2869 if (OP(scan) == EXACTFU) {
2870 OP(scan) = EXACTFU_TRICKYFOLD;
2874 else { /* Here is a generic multi-char fold. */
2875 const U8* multi_end = s + len;
2877 /* Count how many characters in it. In the case of /l and
2878 * /aa, no folds which contain ASCII code points are
2879 * allowed, so check for those, and skip if found. (In
2880 * EXACTFL, no folds are allowed to any Latin1 code point,
2881 * not just ASCII. But there aren't any of these
2882 * currently, nor ever likely, so don't take the time to
2883 * test for them. The code that generates the
2884 * is_MULTI_foo() macros croaks should one actually get put
2885 * into Unicode .) */
2886 if (OP(scan) != EXACTFL && OP(scan) != EXACTFA) {
2887 count = utf8_length(s, multi_end);
2891 while (s < multi_end) {
2894 goto next_iteration;
2904 /* The delta is how long the sequence is minus 1 (1 is how long
2905 * the character that folds to the sequence is) */
2906 *min_subtract += count - 1;
2910 else if (OP(scan) == EXACTFA) {
2912 /* Non-UTF-8 pattern, EXACTFA node. There can't be a multi-char
2913 * fold to the ASCII range (and there are no existing ones in the
2914 * upper latin1 range). But, as outlined in the comments preceding
2915 * this function, we need to flag any occurrences of the sharp s */
2917 if (*s == LATIN_SMALL_LETTER_SHARP_S) {
2918 *has_exactf_sharp_s = TRUE;
2925 else if (OP(scan) != EXACTFL) {
2927 /* Non-UTF-8 pattern, not EXACTFA nor EXACTFL node. Look for the
2928 * multi-char folds that are all Latin1. (This code knows that
2929 * there are no current multi-char folds possible with EXACTFL,
2930 * relying on fold_grind.t to catch any errors if the very unlikely
2931 * event happens that some get added in future Unicode versions.)
2932 * As explained in the comments preceding this function, we look
2933 * also for the sharp s in EXACTF nodes; it can be in the final
2934 * position. Otherwise we can stop looking 1 byte earlier because
2935 * have to find at least two characters for a multi-fold */
2936 const U8* upper = (OP(scan) == EXACTF) ? s_end : s_end -1;
2938 /* The below is perhaps overboard, but this allows us to save a
2939 * test each time through the loop at the expense of a mask. This
2940 * is because on both EBCDIC and ASCII machines, 'S' and 's' differ
2941 * by a single bit. On ASCII they are 32 apart; on EBCDIC, they
2942 * are 64. This uses an exclusive 'or' to find that bit and then
2943 * inverts it to form a mask, with just a single 0, in the bit
2944 * position where 'S' and 's' differ. */
2945 const U8 S_or_s_mask = (U8) ~ ('S' ^ 's');
2946 const U8 s_masked = 's' & S_or_s_mask;
2949 int len = is_MULTI_CHAR_FOLD_latin1_safe(s, s_end);
2950 if (! len) { /* Not a multi-char fold. */
2951 if (*s == LATIN_SMALL_LETTER_SHARP_S && OP(scan) == EXACTF)
2953 *has_exactf_sharp_s = TRUE;
2960 && ((*s & S_or_s_mask) == s_masked)
2961 && ((*(s+1) & S_or_s_mask) == s_masked))
2964 /* EXACTF nodes need to know that the minimum length
2965 * changed so that a sharp s in the string can match this
2966 * ss in the pattern, but they remain EXACTF nodes, as they
2967 * won't match this unless the target string is is UTF-8,
2968 * which we don't know until runtime */
2969 if (OP(scan) != EXACTF) {
2970 OP(scan) = EXACTFU_SS;
2974 *min_subtract += len - 1;
2981 /* Allow dumping but overwriting the collection of skipped
2982 * ops and/or strings with fake optimized ops */
2983 n = scan + NODE_SZ_STR(scan);
2991 DEBUG_OPTIMISE_r(if (merged){DEBUG_PEEP("finl",scan,depth)});
2995 /* REx optimizer. Converts nodes into quicker variants "in place".
2996 Finds fixed substrings. */
2998 /* Stops at toplevel WHILEM as well as at "last". At end *scanp is set
2999 to the position after last scanned or to NULL. */
3001 #define INIT_AND_WITHP \
3002 assert(!and_withp); \
3003 Newx(and_withp,1,struct regnode_charclass_class); \
3004 SAVEFREEPV(and_withp)
3006 /* this is a chain of data about sub patterns we are processing that
3007 need to be handled separately/specially in study_chunk. Its so
3008 we can simulate recursion without losing state. */
3010 typedef struct scan_frame {
3011 regnode *last; /* last node to process in this frame */
3012 regnode *next; /* next node to process when last is reached */
3013 struct scan_frame *prev; /*previous frame*/
3014 I32 stop; /* what stopparen do we use */
3018 #define SCAN_COMMIT(s, data, m) scan_commit(s, data, m, is_inf)
3021 S_study_chunk(pTHX_ RExC_state_t *pRExC_state, regnode **scanp,
3022 I32 *minlenp, I32 *deltap,
3027 struct regnode_charclass_class *and_withp,
3028 U32 flags, U32 depth)
3029 /* scanp: Start here (read-write). */
3030 /* deltap: Write maxlen-minlen here. */
3031 /* last: Stop before this one. */
3032 /* data: string data about the pattern */
3033 /* stopparen: treat close N as END */
3034 /* recursed: which subroutines have we recursed into */
3035 /* and_withp: Valid if flags & SCF_DO_STCLASS_OR */
3038 I32 min = 0; /* There must be at least this number of characters to match */
3040 regnode *scan = *scanp, *next;
3042 int is_inf = (flags & SCF_DO_SUBSTR) && (data->flags & SF_IS_INF);
3043 int is_inf_internal = 0; /* The studied chunk is infinite */
3044 I32 is_par = OP(scan) == OPEN ? ARG(scan) : 0;
3045 scan_data_t data_fake;
3046 SV *re_trie_maxbuff = NULL;
3047 regnode *first_non_open = scan;
3048 I32 stopmin = I32_MAX;
3049 scan_frame *frame = NULL;
3050 GET_RE_DEBUG_FLAGS_DECL;
3052 PERL_ARGS_ASSERT_STUDY_CHUNK;
3055 StructCopy(&zero_scan_data, &data_fake, scan_data_t);
3059 while (first_non_open && OP(first_non_open) == OPEN)
3060 first_non_open=regnext(first_non_open);
3065 while ( scan && OP(scan) != END && scan < last ){
3066 UV min_subtract = 0; /* How mmany chars to subtract from the minimum
3067 node length to get a real minimum (because
3068 the folded version may be shorter) */
3069 bool has_exactf_sharp_s = FALSE;
3070 /* Peephole optimizer: */
3071 DEBUG_STUDYDATA("Peep:", data,depth);
3072 DEBUG_PEEP("Peep",scan,depth);
3074 /* Its not clear to khw or hv why this is done here, and not in the
3075 * clauses that deal with EXACT nodes. khw's guess is that it's
3076 * because of a previous design */
3077 JOIN_EXACT(scan,&min_subtract, &has_exactf_sharp_s, 0);
3079 /* Follow the next-chain of the current node and optimize
3080 away all the NOTHINGs from it. */
3081 if (OP(scan) != CURLYX) {
3082 const int max = (reg_off_by_arg[OP(scan)]
3084 /* I32 may be smaller than U16 on CRAYs! */
3085 : (I32_MAX < U16_MAX ? I32_MAX : U16_MAX));
3086 int off = (reg_off_by_arg[OP(scan)] ? ARG(scan) : NEXT_OFF(scan));
3090 /* Skip NOTHING and LONGJMP. */
3091 while ((n = regnext(n))
3092 && ((PL_regkind[OP(n)] == NOTHING && (noff = NEXT_OFF(n)))
3093 || ((OP(n) == LONGJMP) && (noff = ARG(n))))
3094 && off + noff < max)
3096 if (reg_off_by_arg[OP(scan)])
3099 NEXT_OFF(scan) = off;
3104 /* The principal pseudo-switch. Cannot be a switch, since we
3105 look into several different things. */
3106 if (OP(scan) == BRANCH || OP(scan) == BRANCHJ
3107 || OP(scan) == IFTHEN) {
3108 next = regnext(scan);
3110 /* demq: the op(next)==code check is to see if we have "branch-branch" AFAICT */
3112 if (OP(next) == code || code == IFTHEN) {
3113 /* NOTE - There is similar code to this block below for handling
3114 TRIE nodes on a re-study. If you change stuff here check there
3116 I32 max1 = 0, min1 = I32_MAX, num = 0;
3117 struct regnode_charclass_class accum;
3118 regnode * const startbranch=scan;
3120 if (flags & SCF_DO_SUBSTR)
3121 SCAN_COMMIT(pRExC_state, data, minlenp); /* Cannot merge strings after this. */
3122 if (flags & SCF_DO_STCLASS)
3123 cl_init_zero(pRExC_state, &accum);
3125 while (OP(scan) == code) {
3126 I32 deltanext, minnext, f = 0, fake;
3127 struct regnode_charclass_class this_class;
3130 data_fake.flags = 0;
3132 data_fake.whilem_c = data->whilem_c;
3133 data_fake.last_closep = data->last_closep;
3136 data_fake.last_closep = &fake;
3138 data_fake.pos_delta = delta;
3139 next = regnext(scan);
3140 scan = NEXTOPER(scan);
3142 scan = NEXTOPER(scan);
3143 if (flags & SCF_DO_STCLASS) {
3144 cl_init(pRExC_state, &this_class);
3145 data_fake.start_class = &this_class;
3146 f = SCF_DO_STCLASS_AND;
3148 if (flags & SCF_WHILEM_VISITED_POS)
3149 f |= SCF_WHILEM_VISITED_POS;
3151 /* we suppose the run is continuous, last=next...*/
3152 minnext = study_chunk(pRExC_state, &scan, minlenp, &deltanext,
3154 stopparen, recursed, NULL, f,depth+1);
3157 if (deltanext == I32_MAX) {
3158 is_inf = is_inf_internal = 1;
3160 } else if (max1 < minnext + deltanext)
3161 max1 = minnext + deltanext;
3163 if (data_fake.flags & (SF_HAS_PAR|SF_IN_PAR))
3165 if (data_fake.flags & SCF_SEEN_ACCEPT) {
3166 if ( stopmin > minnext)
3167 stopmin = min + min1;
3168 flags &= ~SCF_DO_SUBSTR;
3170 data->flags |= SCF_SEEN_ACCEPT;
3173 if (data_fake.flags & SF_HAS_EVAL)
3174 data->flags |= SF_HAS_EVAL;
3175 data->whilem_c = data_fake.whilem_c;
3177 if (flags & SCF_DO_STCLASS)
3178 cl_or(pRExC_state, &accum, &this_class);
3180 if (code == IFTHEN && num < 2) /* Empty ELSE branch */
3182 if (flags & SCF_DO_SUBSTR) {
3183 data->pos_min += min1;
3184 if (data->pos_delta >= I32_MAX - (max1 - min1))
3185 data->pos_delta = I32_MAX;
3187 data->pos_delta += max1 - min1;
3188 if (max1 != min1 || is_inf)
3189 data->longest = &(data->longest_float);
3192 if (delta == I32_MAX || I32_MAX - delta - (max1 - min1) < 0)
3195 delta += max1 - min1;
3196 if (flags & SCF_DO_STCLASS_OR) {
3197 cl_or(pRExC_state, data->start_class, &accum);
3199 cl_and(data->start_class, and_withp);
3200 flags &= ~SCF_DO_STCLASS;
3203 else if (flags & SCF_DO_STCLASS_AND) {
3205 cl_and(data->start_class, &accum);
3206 flags &= ~SCF_DO_STCLASS;
3209 /* Switch to OR mode: cache the old value of
3210 * data->start_class */
3212 StructCopy(data->start_class, and_withp,
3213 struct regnode_charclass_class);
3214 flags &= ~SCF_DO_STCLASS_AND;
3215 StructCopy(&accum, data->start_class,
3216 struct regnode_charclass_class);
3217 flags |= SCF_DO_STCLASS_OR;
3218 SET_SSC_EOS(data->start_class);
3222 if (PERL_ENABLE_TRIE_OPTIMISATION && OP( startbranch ) == BRANCH ) {
3225 Assuming this was/is a branch we are dealing with: 'scan' now
3226 points at the item that follows the branch sequence, whatever
3227 it is. We now start at the beginning of the sequence and look
3234 which would be constructed from a pattern like /A|LIST|OF|WORDS/
3236 If we can find such a subsequence we need to turn the first
3237 element into a trie and then add the subsequent branch exact
3238 strings to the trie.
3242 1. patterns where the whole set of branches can be converted.
3244 2. patterns where only a subset can be converted.
3246 In case 1 we can replace the whole set with a single regop
3247 for the trie. In case 2 we need to keep the start and end
3250 'BRANCH EXACT; BRANCH EXACT; BRANCH X'
3251 becomes BRANCH TRIE; BRANCH X;
3253 There is an additional case, that being where there is a
3254 common prefix, which gets split out into an EXACT like node
3255 preceding the TRIE node.
3257 If x(1..n)==tail then we can do a simple trie, if not we make
3258 a "jump" trie, such that when we match the appropriate word
3259 we "jump" to the appropriate tail node. Essentially we turn
3260 a nested if into a case structure of sorts.
3265 if (!re_trie_maxbuff) {
3266 re_trie_maxbuff = get_sv(RE_TRIE_MAXBUF_NAME, 1);
3267 if (!SvIOK(re_trie_maxbuff))
3268 sv_setiv(re_trie_maxbuff, RE_TRIE_MAXBUF_INIT);
3270 if ( SvIV(re_trie_maxbuff)>=0 ) {
3272 regnode *first = (regnode *)NULL;
3273 regnode *last = (regnode *)NULL;
3274 regnode *tail = scan;
3279 SV * const mysv = sv_newmortal(); /* for dumping */
3281 /* var tail is used because there may be a TAIL
3282 regop in the way. Ie, the exacts will point to the
3283 thing following the TAIL, but the last branch will
3284 point at the TAIL. So we advance tail. If we
3285 have nested (?:) we may have to move through several
3289 while ( OP( tail ) == TAIL ) {
3290 /* this is the TAIL generated by (?:) */
3291 tail = regnext( tail );
3295 DEBUG_TRIE_COMPILE_r({
3296 regprop(RExC_rx, mysv, tail );
3297 PerlIO_printf( Perl_debug_log, "%*s%s%s\n",
3298 (int)depth * 2 + 2, "",
3299 "Looking for TRIE'able sequences. Tail node is: ",
3300 SvPV_nolen_const( mysv )
3306 Step through the branches
3307 cur represents each branch,
3308 noper is the first thing to be matched as part of that branch
3309 noper_next is the regnext() of that node.
3311 We normally handle a case like this /FOO[xyz]|BAR[pqr]/
3312 via a "jump trie" but we also support building with NOJUMPTRIE,
3313 which restricts the trie logic to structures like /FOO|BAR/.
3315 If noper is a trieable nodetype then the branch is a possible optimization
3316 target. If we are building under NOJUMPTRIE then we require that noper_next
3317 is the same as scan (our current position in the regex program).
3319 Once we have two or more consecutive such branches we can create a
3320 trie of the EXACT's contents and stitch it in place into the program.
3322 If the sequence represents all of the branches in the alternation we
3323 replace the entire thing with a single TRIE node.
3325 Otherwise when it is a subsequence we need to stitch it in place and
3326 replace only the relevant branches. This means the first branch has
3327 to remain as it is used by the alternation logic, and its next pointer,
3328 and needs to be repointed at the item on the branch chain following
3329 the last branch we have optimized away.
3331 This could be either a BRANCH, in which case the subsequence is internal,
3332 or it could be the item following the branch sequence in which case the
3333 subsequence is at the end (which does not necessarily mean the first node
3334 is the start of the alternation).
3336 TRIE_TYPE(X) is a define which maps the optype to a trietype.
3339 ----------------+-----------
3343 EXACTFU_SS | EXACTFU
3344 EXACTFU_TRICKYFOLD | EXACTFU
3349 #define TRIE_TYPE(X) ( ( NOTHING == (X) ) ? NOTHING : \
3350 ( EXACT == (X) ) ? EXACT : \
3351 ( EXACTFU == (X) || EXACTFU_SS == (X) || EXACTFU_TRICKYFOLD == (X) ) ? EXACTFU : \
3354 /* dont use tail as the end marker for this traverse */
3355 for ( cur = startbranch ; cur != scan ; cur = regnext( cur ) ) {
3356 regnode * const noper = NEXTOPER( cur );
3357 U8 noper_type = OP( noper );
3358 U8 noper_trietype = TRIE_TYPE( noper_type );
3359 #if defined(DEBUGGING) || defined(NOJUMPTRIE)
3360 regnode * const noper_next = regnext( noper );
3361 U8 noper_next_type = (noper_next && noper_next != tail) ? OP(noper_next) : 0;
3362 U8 noper_next_trietype = (noper_next && noper_next != tail) ? TRIE_TYPE( noper_next_type ) :0;
3365 DEBUG_TRIE_COMPILE_r({
3366 regprop(RExC_rx, mysv, cur);
3367 PerlIO_printf( Perl_debug_log, "%*s- %s (%d)",
3368 (int)depth * 2 + 2,"", SvPV_nolen_const( mysv ), REG_NODE_NUM(cur) );
3370 regprop(RExC_rx, mysv, noper);
3371 PerlIO_printf( Perl_debug_log, " -> %s",
3372 SvPV_nolen_const(mysv));
3375 regprop(RExC_rx, mysv, noper_next );
3376 PerlIO_printf( Perl_debug_log,"\t=> %s\t",
3377 SvPV_nolen_const(mysv));
3379 PerlIO_printf( Perl_debug_log, "(First==%d,Last==%d,Cur==%d,tt==%s,nt==%s,nnt==%s)\n",
3380 REG_NODE_NUM(first), REG_NODE_NUM(last), REG_NODE_NUM(cur),
3381 PL_reg_name[trietype], PL_reg_name[noper_trietype], PL_reg_name[noper_next_trietype]
3385 /* Is noper a trieable nodetype that can be merged with the
3386 * current trie (if there is one)? */
3390 ( noper_trietype == NOTHING)
3391 || ( trietype == NOTHING )
3392 || ( trietype == noper_trietype )
3395 && noper_next == tail
3399 /* Handle mergable triable node
3400 * Either we are the first node in a new trieable sequence,
3401 * in which case we do some bookkeeping, otherwise we update
3402 * the end pointer. */
3405 if ( noper_trietype == NOTHING ) {
3406 #if !defined(DEBUGGING) && !defined(NOJUMPTRIE)
3407 regnode * const noper_next = regnext( noper );
3408 U8 noper_next_type = (noper_next && noper_next!=tail) ? OP(noper_next) : 0;
3409 U8 noper_next_trietype = noper_next_type ? TRIE_TYPE( noper_next_type ) :0;
3412 if ( noper_next_trietype ) {
3413 trietype = noper_next_trietype;
3414 } else if (noper_next_type) {
3415 /* a NOTHING regop is 1 regop wide. We need at least two
3416 * for a trie so we can't merge this in */
3420 trietype = noper_trietype;
3423 if ( trietype == NOTHING )
3424 trietype = noper_trietype;
3429 } /* end handle mergable triable node */
3431 /* handle unmergable node -
3432 * noper may either be a triable node which can not be tried
3433 * together with the current trie, or a non triable node */
3435 /* If last is set and trietype is not NOTHING then we have found
3436 * at least two triable branch sequences in a row of a similar
3437 * trietype so we can turn them into a trie. If/when we
3438 * allow NOTHING to start a trie sequence this condition will be
3439 * required, and it isn't expensive so we leave it in for now. */
3440 if ( trietype && trietype != NOTHING )
3441 make_trie( pRExC_state,
3442 startbranch, first, cur, tail, count,
3443 trietype, depth+1 );
3444 last = NULL; /* note: we clear/update first, trietype etc below, so we dont do it here */
3448 && noper_next == tail
3451 /* noper is triable, so we can start a new trie sequence */
3454 trietype = noper_trietype;
3456 /* if we already saw a first but the current node is not triable then we have
3457 * to reset the first information. */
3462 } /* end handle unmergable node */
3463 } /* loop over branches */
3464 DEBUG_TRIE_COMPILE_r({
3465 regprop(RExC_rx, mysv, cur);
3466 PerlIO_printf( Perl_debug_log,
3467 "%*s- %s (%d) <SCAN FINISHED>\n", (int)depth * 2 + 2,
3468 "", SvPV_nolen_const( mysv ),REG_NODE_NUM(cur));
3471 if ( last && trietype ) {
3472 if ( trietype != NOTHING ) {
3473 /* the last branch of the sequence was part of a trie,
3474 * so we have to construct it here outside of the loop
3476 made= make_trie( pRExC_state, startbranch, first, scan, tail, count, trietype, depth+1 );
3477 #ifdef TRIE_STUDY_OPT
3478 if ( ((made == MADE_EXACT_TRIE &&
3479 startbranch == first)
3480 || ( first_non_open == first )) &&
3482 flags |= SCF_TRIE_RESTUDY;
3483 if ( startbranch == first
3486 RExC_seen &=~REG_TOP_LEVEL_BRANCHES;
3491 /* at this point we know whatever we have is a NOTHING sequence/branch
3492 * AND if 'startbranch' is 'first' then we can turn the whole thing into a NOTHING
3494 if ( startbranch == first ) {
3496 /* the entire thing is a NOTHING sequence, something like this:
3497 * (?:|) So we can turn it into a plain NOTHING op. */
3498 DEBUG_TRIE_COMPILE_r({
3499 regprop(RExC_rx, mysv, cur);
3500 PerlIO_printf( Perl_debug_log,
3501 "%*s- %s (%d) <NOTHING BRANCH SEQUENCE>\n", (int)depth * 2 + 2,
3502 "", SvPV_nolen_const( mysv ),REG_NODE_NUM(cur));
3505 OP(startbranch)= NOTHING;
3506 NEXT_OFF(startbranch)= tail - startbranch;
3507 for ( opt= startbranch + 1; opt < tail ; opt++ )
3511 } /* end if ( last) */
3512 } /* TRIE_MAXBUF is non zero */
3517 else if ( code == BRANCHJ ) { /* single branch is optimized. */
3518 scan = NEXTOPER(NEXTOPER(scan));
3519 } else /* single branch is optimized. */
3520 scan = NEXTOPER(scan);
3522 } else if (OP(scan) == SUSPEND || OP(scan) == GOSUB || OP(scan) == GOSTART) {
3523 scan_frame *newframe = NULL;
3528 if (OP(scan) != SUSPEND) {
3529 /* set the pointer */
3530 if (OP(scan) == GOSUB) {
3532 RExC_recurse[ARG2L(scan)] = scan;
3533 start = RExC_open_parens[paren-1];
3534 end = RExC_close_parens[paren-1];
3537 start = RExC_rxi->program + 1;
3541 Newxz(recursed, (((RExC_npar)>>3) +1), U8);
3542 SAVEFREEPV(recursed);
3544 if (!PAREN_TEST(recursed,paren+1)) {
3545 PAREN_SET(recursed,paren+1);
3546 Newx(newframe,1,scan_frame);
3548 if (flags & SCF_DO_SUBSTR) {
3549 SCAN_COMMIT(pRExC_state,data,minlenp);
3550 data->longest = &(data->longest_float);
3552 is_inf = is_inf_internal = 1;
3553 if (flags & SCF_DO_STCLASS_OR) /* Allow everything */
3554 cl_anything(pRExC_state, data->start_class);
3555 flags &= ~SCF_DO_STCLASS;
3558 Newx(newframe,1,scan_frame);
3561 end = regnext(scan);
3566 SAVEFREEPV(newframe);
3567 newframe->next = regnext(scan);
3568 newframe->last = last;
3569 newframe->stop = stopparen;
3570 newframe->prev = frame;
3580 else if (OP(scan) == EXACT) {
3581 I32 l = STR_LEN(scan);
3584 const U8 * const s = (U8*)STRING(scan);
3585 uc = utf8_to_uvchr_buf(s, s + l, NULL);
3586 l = utf8_length(s, s + l);
3588 uc = *((U8*)STRING(scan));
3591 if (flags & SCF_DO_SUBSTR) { /* Update longest substr. */
3592 /* The code below prefers earlier match for fixed
3593 offset, later match for variable offset. */
3594 if (data->last_end == -1) { /* Update the start info. */
3595 data->last_start_min = data->pos_min;
3596 data->last_start_max = is_inf
3597 ? I32_MAX : data->pos_min + data->pos_delta;
3599 sv_catpvn(data->last_found, STRING(scan), STR_LEN(scan));
3601 SvUTF8_on(data->last_found);
3603 SV * const sv = data->last_found;
3604 MAGIC * const mg = SvUTF8(sv) && SvMAGICAL(sv) ?
3605 mg_find(sv, PERL_MAGIC_utf8) : NULL;
3606 if (mg && mg->mg_len >= 0)
3607 mg->mg_len += utf8_length((U8*)STRING(scan),
3608 (U8*)STRING(scan)+STR_LEN(scan));
3610 data->last_end = data->pos_min + l;
3611 data->pos_min += l; /* As in the first entry. */
3612 data->flags &= ~SF_BEFORE_EOL;
3614 if (flags & SCF_DO_STCLASS_AND) {
3615 /* Check whether it is compatible with what we know already! */
3619 /* If compatible, we or it in below. It is compatible if is
3620 * in the bitmp and either 1) its bit or its fold is set, or 2)
3621 * it's for a locale. Even if there isn't unicode semantics
3622 * here, at runtime there may be because of matching against a
3623 * utf8 string, so accept a possible false positive for
3624 * latin1-range folds */
3626 (!(data->start_class->flags & ANYOF_LOCALE)
3627 && !ANYOF_BITMAP_TEST(data->start_class, uc)
3628 && (!(data->start_class->flags & ANYOF_LOC_FOLD)
3629 || !ANYOF_BITMAP_TEST(data->start_class, PL_fold_latin1[uc])))
3634 ANYOF_CLASS_ZERO(data->start_class);
3635 ANYOF_BITMAP_ZERO(data->start_class);
3637 ANYOF_BITMAP_SET(data->start_class, uc);
3638 else if (uc >= 0x100) {
3641 /* Some Unicode code points fold to the Latin1 range; as
3642 * XXX temporary code, instead of figuring out if this is
3643 * one, just assume it is and set all the start class bits
3644 * that could be some such above 255 code point's fold
3645 * which will generate fals positives. As the code
3646 * elsewhere that does compute the fold settles down, it
3647 * can be extracted out and re-used here */
3648 for (i = 0; i < 256; i++){
3649 if (HAS_NONLATIN1_FOLD_CLOSURE(i)) {
3650 ANYOF_BITMAP_SET(data->start_class, i);
3654 CLEAR_SSC_EOS(data->start_class);
3656 data->start_class->flags &= ~ANYOF_UNICODE_ALL;
3658 else if (flags & SCF_DO_STCLASS_OR) {
3659 /* false positive possible if the class is case-folded */
3661 ANYOF_BITMAP_SET(data->start_class, uc);
3663 data->start_class->flags |= ANYOF_UNICODE_ALL;
3664 CLEAR_SSC_EOS(data->start_class);
3665 cl_and(data->start_class, and_withp);
3667 flags &= ~SCF_DO_STCLASS;
3669 else if (PL_regkind[OP(scan)] == EXACT) { /* But OP != EXACT! */
3670 I32 l = STR_LEN(scan);
3671 UV uc = *((U8*)STRING(scan));
3673 /* Search for fixed substrings supports EXACT only. */
3674 if (flags & SCF_DO_SUBSTR) {
3676 SCAN_COMMIT(pRExC_state, data, minlenp);
3679 const U8 * const s = (U8 *)STRING(scan);
3680 uc = utf8_to_uvchr_buf(s, s + l, NULL);
3681 l = utf8_length(s, s + l);
3683 if (has_exactf_sharp_s) {
3684 RExC_seen |= REG_SEEN_EXACTF_SHARP_S;
3686 min += l - min_subtract;
3688 delta += min_subtract;
3689 if (flags & SCF_DO_SUBSTR) {
3690 data->pos_min += l - min_subtract;
3691 if (data->pos_min < 0) {
3694 data->pos_delta += min_subtract;
3696 data->longest = &(data->longest_float);
3699 if (flags & SCF_DO_STCLASS_AND) {
3700 /* Check whether it is compatible with what we know already! */
3703 (!(data->start_class->flags & ANYOF_LOCALE)
3704 && !ANYOF_BITMAP_TEST(data->start_class, uc)
3705 && !ANYOF_BITMAP_TEST(data->start_class, PL_fold_latin1[uc])))
3709 ANYOF_CLASS_ZERO(data->start_class);
3710 ANYOF_BITMAP_ZERO(data->start_class);
3712 ANYOF_BITMAP_SET(data->start_class, uc);
3713 CLEAR_SSC_EOS(data->start_class);
3714 if (OP(scan) == EXACTFL) {
3715 /* XXX This set is probably no longer necessary, and
3716 * probably wrong as LOCALE now is on in the initial
3718 data->start_class->flags |= ANYOF_LOCALE|ANYOF_LOC_FOLD;
3722 /* Also set the other member of the fold pair. In case
3723 * that unicode semantics is called for at runtime, use
3724 * the full latin1 fold. (Can't do this for locale,
3725 * because not known until runtime) */
3726 ANYOF_BITMAP_SET(data->start_class, PL_fold_latin1[uc]);
3728 /* All other (EXACTFL handled above) folds except under
3729 * /iaa that include s, S, and sharp_s also may include
3731 if (OP(scan) != EXACTFA) {
3732 if (uc == 's' || uc == 'S') {
3733 ANYOF_BITMAP_SET(data->start_class,
3734 LATIN_SMALL_LETTER_SHARP_S);
3736 else if (uc == LATIN_SMALL_LETTER_SHARP_S) {
3737 ANYOF_BITMAP_SET(data->start_class, 's');
3738 ANYOF_BITMAP_SET(data->start_class, 'S');
3743 else if (uc >= 0x100) {
3745 for (i = 0; i < 256; i++){
3746 if (_HAS_NONLATIN1_FOLD_CLOSURE_ONLY_FOR_USE_BY_REGCOMP_DOT_C_AND_REGEXEC_DOT_C(i)) {
3747 ANYOF_BITMAP_SET(data->start_class, i);
3752 else if (flags & SCF_DO_STCLASS_OR) {
3753 if (data->start_class->flags & ANYOF_LOC_FOLD) {
3754 /* false positive possible if the class is case-folded.
3755 Assume that the locale settings are the same... */
3757 ANYOF_BITMAP_SET(data->start_class, uc);
3758 if (OP(scan) != EXACTFL) {
3760 /* And set the other member of the fold pair, but
3761 * can't do that in locale because not known until
3763 ANYOF_BITMAP_SET(data->start_class,
3764 PL_fold_latin1[uc]);
3766 /* All folds except under /iaa that include s, S,
3767 * and sharp_s also may include the others */
3768 if (OP(scan) != EXACTFA) {
3769 if (uc == 's' || uc == 'S') {
3770 ANYOF_BITMAP_SET(data->start_class,
3771 LATIN_SMALL_LETTER_SHARP_S);
3773 else if (uc == LATIN_SMALL_LETTER_SHARP_S) {
3774 ANYOF_BITMAP_SET(data->start_class, 's');
3775 ANYOF_BITMAP_SET(data->start_class, 'S');
3780 CLEAR_SSC_EOS(data->start_class);
3782 cl_and(data->start_class, and_withp);
3784 flags &= ~SCF_DO_STCLASS;
3786 else if (REGNODE_VARIES(OP(scan))) {
3787 I32 mincount, maxcount, minnext, deltanext, fl = 0;
3788 I32 f = flags, pos_before = 0;
3789 regnode * const oscan = scan;
3790 struct regnode_charclass_class this_class;
3791 struct regnode_charclass_class *oclass = NULL;
3792 I32 next_is_eval = 0;
3794 switch (PL_regkind[OP(scan)]) {
3795 case WHILEM: /* End of (?:...)* . */
3796 scan = NEXTOPER(scan);
3799 if (flags & (SCF_DO_SUBSTR | SCF_DO_STCLASS)) {
3800 next = NEXTOPER(scan);
3801 if (OP(next) == EXACT || (flags & SCF_DO_STCLASS)) {
3803 maxcount = REG_INFTY;
3804 next = regnext(scan);
3805 scan = NEXTOPER(scan);
3809 if (flags & SCF_DO_SUBSTR)
3814 if (flags & SCF_DO_STCLASS) {
3816 maxcount = REG_INFTY;
3817 next = regnext(scan);
3818 scan = NEXTOPER(scan);
3821 is_inf = is_inf_internal = 1;
3822 scan = regnext(scan);
3823 if (flags & SCF_DO_SUBSTR) {
3824 SCAN_COMMIT(pRExC_state, data, minlenp); /* Cannot extend fixed substrings */
3825 data->longest = &(data->longest_float);
3827 goto optimize_curly_tail;
3829 if (stopparen>0 && (OP(scan)==CURLYN || OP(scan)==CURLYM)
3830 && (scan->flags == stopparen))
3835 mincount = ARG1(scan);
3836 maxcount = ARG2(scan);
https://perl5.git.perl.org / perl5.git / blob