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 /* Note on debug output:
76 * This is set up so that -Dr turns on debugging like all other flags that are
77 * enabled by -DDEBUGGING. -Drv gives more verbose output. This applies to
78 * all regular expressions encountered in a program, and gives a huge amount of
79 * output for all but the shortest programs.
81 * The ability to output pattern debugging information lexically, and with much
82 * finer grained control was added, with 'use re qw(Debug ....);' available even
83 * in non-DEBUGGING builds. This is accomplished by copying the contents of
84 * regcomp.c to ext/re/re_comp.c, and regexec.c is copied to ext/re/re_exec.c.
85 * Those files are compiled and linked into the perl executable, and they are
86 * compiled essentially as if DEBUGGING were enabled, and controlled by calls
89 * That would normally mean linking errors when two functions of the same name
90 * are attempted to be placed into the same executable. That is solved in one
92 * 1) Static functions aren't known outside the file they are in, so for the
93 * many functions of that type in this file, it just isn't a problem.
94 * 2) Most externally known functions are enclosed in
95 * #ifndef PERL_IN_XSUB_RE
98 * blocks, so there is only one defintion for them in the whole
99 * executable, the one in regcomp.c (or regexec.c). The implication of
100 * that is any debugging info that comes from them is controlled only by
101 * -Dr. Further, any static function they call will also be the version
102 * in regcomp.c (or regexec.c), so its debugging will also be by -Dr.
103 * 3) About a dozen external functions are re-#defined in ext/re/re_top.h, to
104 * have different names, so that what gets loaded in the executable is
105 * 'Perl_foo' from regcomp.c (and regexec.c), and the identical function
106 * from re_comp.c (and re_exec.c), but with the name 'my_foo' Debugging
107 * in the 'Perl_foo' versions is controlled by -Dr, but the 'my_foo'
108 * versions and their callees are under control of re.pm. The catch is
109 * that references to all these go through the regexp_engine structure,
110 * which is initialized in regcomp.h to the Perl_foo versions, and
111 * substituted out in lexical scopes where 'use re' is in effect to the
112 * 'my_foo' ones. That structure is public API, so it would be a hard
113 * sell to add any additional members.
114 * 4) For functions in regcomp.c and re_comp.c that are called only from,
115 * respectively, regexec.c and re_exec.c, they can have two different
116 * names, depending on #ifdef'ing PERL_IN_XSUB_RE, in both regexec.c and
119 * The bottom line is that if you add code to one of the public functions
120 * listed in ext/re/re_top.h, debugging automagically works. But if you write
121 * a new function that needs to do debugging or there is a chain of calls from
122 * it that need to do debugging, all functions in the chain should use options
125 * A function may have to be split so that debugging stuff is static, but it
126 * calls out to some other function that only gets compiled in regcomp.c to
127 * access data that we don't want to duplicate.
131 #define PERL_IN_REGCOMP_C
135 #ifdef PERL_IN_XSUB_RE
136 # include "re_comp.h"
137 EXTERN_C const struct regexp_engine my_reg_engine;
138 EXTERN_C const struct regexp_engine wild_reg_engine;
140 # include "regcomp.h"
143 #include "invlist_inline.h"
144 #include "unicode_constants.h"
146 #define HAS_NONLATIN1_FOLD_CLOSURE(i) \
147 _HAS_NONLATIN1_FOLD_CLOSURE_ONLY_FOR_USE_BY_REGCOMP_DOT_C_AND_REGEXEC_DOT_C(i)
148 #define HAS_NONLATIN1_SIMPLE_FOLD_CLOSURE(i) \
149 _HAS_NONLATIN1_SIMPLE_FOLD_CLOSURE_ONLY_FOR_USE_BY_REGCOMP_DOT_C_AND_REGEXEC_DOT_C(i)
150 #define IS_NON_FINAL_FOLD(c) _IS_NON_FINAL_FOLD_ONLY_FOR_USE_BY_REGCOMP_DOT_C(c)
151 #define IS_IN_SOME_FOLD_L1(c) _IS_IN_SOME_FOLD_ONLY_FOR_USE_BY_REGCOMP_DOT_C(c)
154 #define STATIC static
157 /* this is a chain of data about sub patterns we are processing that
158 need to be handled separately/specially in study_chunk. Its so
159 we can simulate recursion without losing state. */
161 typedef struct scan_frame {
162 regnode *last_regnode; /* last node to process in this frame */
163 regnode *next_regnode; /* next node to process when last is reached */
164 U32 prev_recursed_depth;
165 I32 stopparen; /* what stopparen do we use */
166 bool in_gosub; /* this or an outer frame is for GOSUB */
168 struct scan_frame *this_prev_frame; /* this previous frame */
169 struct scan_frame *prev_frame; /* previous frame */
170 struct scan_frame *next_frame; /* next frame */
173 /* Certain characters are output as a sequence with the first being a
175 #define isBACKSLASHED_PUNCT(c) memCHRs("-[]\\^", c)
178 struct RExC_state_t {
179 U32 flags; /* RXf_* are we folding, multilining? */
180 U32 pm_flags; /* PMf_* stuff from the calling PMOP */
181 char *precomp; /* uncompiled string. */
182 char *precomp_end; /* pointer to end of uncompiled string. */
183 REGEXP *rx_sv; /* The SV that is the regexp. */
184 regexp *rx; /* perl core regexp structure */
185 regexp_internal *rxi; /* internal data for regexp object
187 char *start; /* Start of input for compile */
188 char *end; /* End of input for compile */
189 char *parse; /* Input-scan pointer. */
190 char *copy_start; /* start of copy of input within
191 constructed parse string */
192 char *save_copy_start; /* Provides one level of saving
193 and restoring 'copy_start' */
194 char *copy_start_in_input; /* Position in input string
195 corresponding to copy_start */
196 SSize_t whilem_seen; /* number of WHILEM in this expr */
197 regnode *emit_start; /* Start of emitted-code area */
198 regnode_offset emit; /* Code-emit pointer */
199 I32 naughty; /* How bad is this pattern? */
200 I32 sawback; /* Did we see \1, ...? */
201 SSize_t size; /* Number of regnode equivalents in
203 Size_t sets_depth; /* Counts recursion depth of already-
204 compiled regex set patterns */
207 I32 parens_buf_size; /* #slots malloced open/close_parens */
208 regnode_offset *open_parens; /* offsets to open parens */
209 regnode_offset *close_parens; /* offsets to close parens */
210 HV *paren_names; /* Paren names */
212 /* position beyond 'precomp' of the warning message furthest away from
213 * 'precomp'. During the parse, no warnings are raised for any problems
214 * earlier in the parse than this position. This works if warnings are
215 * raised the first time a given spot is parsed, and if only one
216 * independent warning is raised for any given spot */
217 Size_t latest_warn_offset;
219 I32 npar; /* Capture buffer count so far in the
220 parse, (OPEN) plus one. ("par" 0 is
222 I32 total_par; /* During initial parse, is either 0,
223 or -1; the latter indicating a
224 reparse is needed. After that pass,
225 it is what 'npar' became after the
226 pass. Hence, it being > 0 indicates
227 we are in a reparse situation */
228 I32 nestroot; /* root parens we are in - used by
231 regnode *end_op; /* END node in program */
232 I32 utf8; /* whether the pattern is utf8 or not */
233 I32 orig_utf8; /* whether the pattern was originally in utf8 */
234 /* XXX use this for future optimisation of case
235 * where pattern must be upgraded to utf8. */
236 I32 uni_semantics; /* If a d charset modifier should use unicode
237 rules, even if the pattern is not in
240 I32 recurse_count; /* Number of recurse regops we have generated */
241 regnode **recurse; /* Recurse regops */
242 U8 *study_chunk_recursed; /* bitmap of which subs we have moved
244 U32 study_chunk_recursed_bytes; /* bytes in bitmap */
247 I32 override_recoding;
248 I32 recode_x_to_native;
249 I32 in_multi_char_class;
250 int code_index; /* next code_blocks[] slot */
251 struct reg_code_blocks *code_blocks;/* positions of literal (?{})
253 SSize_t maxlen; /* mininum possible number of chars in string to match */
254 scan_frame *frame_head;
255 scan_frame *frame_last;
259 SV *runtime_code_qr; /* qr with the runtime code blocks */
261 const char *lastparse;
263 U32 study_chunk_recursed_count;
264 AV *paren_name_list; /* idx -> name */
268 #define RExC_lastparse (pRExC_state->lastparse)
269 #define RExC_lastnum (pRExC_state->lastnum)
270 #define RExC_paren_name_list (pRExC_state->paren_name_list)
271 #define RExC_study_chunk_recursed_count (pRExC_state->study_chunk_recursed_count)
272 #define RExC_mysv (pRExC_state->mysv1)
273 #define RExC_mysv1 (pRExC_state->mysv1)
274 #define RExC_mysv2 (pRExC_state->mysv2)
282 bool sWARN_EXPERIMENTAL__VLB;
283 bool sWARN_EXPERIMENTAL__REGEX_SETS;
286 #define RExC_flags (pRExC_state->flags)
287 #define RExC_pm_flags (pRExC_state->pm_flags)
288 #define RExC_precomp (pRExC_state->precomp)
289 #define RExC_copy_start_in_input (pRExC_state->copy_start_in_input)
290 #define RExC_copy_start_in_constructed (pRExC_state->copy_start)
291 #define RExC_save_copy_start_in_constructed (pRExC_state->save_copy_start)
292 #define RExC_precomp_end (pRExC_state->precomp_end)
293 #define RExC_rx_sv (pRExC_state->rx_sv)
294 #define RExC_rx (pRExC_state->rx)
295 #define RExC_rxi (pRExC_state->rxi)
296 #define RExC_start (pRExC_state->start)
297 #define RExC_end (pRExC_state->end)
298 #define RExC_parse (pRExC_state->parse)
299 #define RExC_latest_warn_offset (pRExC_state->latest_warn_offset )
300 #define RExC_whilem_seen (pRExC_state->whilem_seen)
301 #define RExC_seen_d_op (pRExC_state->seen_d_op) /* Seen something that differs
302 under /d from /u ? */
304 #ifdef RE_TRACK_PATTERN_OFFSETS
305 # define RExC_offsets (RExC_rxi->u.offsets) /* I am not like the
308 #define RExC_emit (pRExC_state->emit)
309 #define RExC_emit_start (pRExC_state->emit_start)
310 #define RExC_sawback (pRExC_state->sawback)
311 #define RExC_seen (pRExC_state->seen)
312 #define RExC_size (pRExC_state->size)
313 #define RExC_maxlen (pRExC_state->maxlen)
314 #define RExC_npar (pRExC_state->npar)
315 #define RExC_total_parens (pRExC_state->total_par)
316 #define RExC_parens_buf_size (pRExC_state->parens_buf_size)
317 #define RExC_nestroot (pRExC_state->nestroot)
318 #define RExC_seen_zerolen (pRExC_state->seen_zerolen)
319 #define RExC_utf8 (pRExC_state->utf8)
320 #define RExC_uni_semantics (pRExC_state->uni_semantics)
321 #define RExC_orig_utf8 (pRExC_state->orig_utf8)
322 #define RExC_open_parens (pRExC_state->open_parens)
323 #define RExC_close_parens (pRExC_state->close_parens)
324 #define RExC_end_op (pRExC_state->end_op)
325 #define RExC_paren_names (pRExC_state->paren_names)
326 #define RExC_recurse (pRExC_state->recurse)
327 #define RExC_recurse_count (pRExC_state->recurse_count)
328 #define RExC_sets_depth (pRExC_state->sets_depth)
329 #define RExC_study_chunk_recursed (pRExC_state->study_chunk_recursed)
330 #define RExC_study_chunk_recursed_bytes \
331 (pRExC_state->study_chunk_recursed_bytes)
332 #define RExC_in_lookaround (pRExC_state->in_lookaround)
333 #define RExC_contains_locale (pRExC_state->contains_locale)
334 #define RExC_recode_x_to_native (pRExC_state->recode_x_to_native)
337 # define SET_recode_x_to_native(x) \
338 STMT_START { RExC_recode_x_to_native = (x); } STMT_END
340 # define SET_recode_x_to_native(x) NOOP
343 #define RExC_in_multi_char_class (pRExC_state->in_multi_char_class)
344 #define RExC_frame_head (pRExC_state->frame_head)
345 #define RExC_frame_last (pRExC_state->frame_last)
346 #define RExC_frame_count (pRExC_state->frame_count)
347 #define RExC_strict (pRExC_state->strict)
348 #define RExC_study_started (pRExC_state->study_started)
349 #define RExC_warn_text (pRExC_state->warn_text)
350 #define RExC_in_script_run (pRExC_state->in_script_run)
351 #define RExC_use_BRANCHJ (pRExC_state->use_BRANCHJ)
352 #define RExC_warned_WARN_EXPERIMENTAL__VLB (pRExC_state->sWARN_EXPERIMENTAL__VLB)
353 #define RExC_warned_WARN_EXPERIMENTAL__REGEX_SETS (pRExC_state->sWARN_EXPERIMENTAL__REGEX_SETS)
354 #define RExC_unlexed_names (pRExC_state->unlexed_names)
356 /* Heuristic check on the complexity of the pattern: if TOO_NAUGHTY, we set
357 * a flag to disable back-off on the fixed/floating substrings - if it's
358 * a high complexity pattern we assume the benefit of avoiding a full match
359 * is worth the cost of checking for the substrings even if they rarely help.
361 #define RExC_naughty (pRExC_state->naughty)
362 #define TOO_NAUGHTY (10)
363 #define MARK_NAUGHTY(add) \
364 if (RExC_naughty < TOO_NAUGHTY) \
365 RExC_naughty += (add)
366 #define MARK_NAUGHTY_EXP(exp, add) \
367 if (RExC_naughty < TOO_NAUGHTY) \
368 RExC_naughty += RExC_naughty / (exp) + (add)
370 #define ISMULT1(c) ((c) == '*' || (c) == '+' || (c) == '?')
371 #define ISMULT2(s) (ISMULT1(*s) || ((*s) == '{' && regcurly(s)))
374 * Flags to be passed up and down.
376 #define HASWIDTH 0x01 /* Known to not match null strings, could match
378 #define SIMPLE 0x02 /* Exactly one character wide */
379 /* (or LNBREAK as a special case) */
380 #define POSTPONED 0x08 /* (?1),(?&name), (??{...}) or similar */
381 #define TRYAGAIN 0x10 /* Weeded out a declaration. */
382 #define RESTART_PARSE 0x20 /* Need to redo the parse */
383 #define NEED_UTF8 0x40 /* In conjunction with RESTART_PARSE, need to
384 calcuate sizes as UTF-8 */
386 #define REG_NODE_NUM(x) ((x) ? (int)((x)-RExC_emit_start) : -1)
388 /* whether trie related optimizations are enabled */
389 #if PERL_ENABLE_EXTENDED_TRIE_OPTIMISATION
390 #define TRIE_STUDY_OPT
391 #define FULL_TRIE_STUDY
397 #define PBYTE(u8str,paren) ((U8*)(u8str))[(paren) >> 3]
398 #define PBITVAL(paren) (1 << ((paren) & 7))
399 #define PAREN_OFFSET(depth) \
400 (RExC_study_chunk_recursed + (depth) * RExC_study_chunk_recursed_bytes)
401 #define PAREN_TEST(depth, paren) \
402 (PBYTE(PAREN_OFFSET(depth), paren) & PBITVAL(paren))
403 #define PAREN_SET(depth, paren) \
404 (PBYTE(PAREN_OFFSET(depth), paren) |= PBITVAL(paren))
405 #define PAREN_UNSET(depth, paren) \
406 (PBYTE(PAREN_OFFSET(depth), paren) &= ~PBITVAL(paren))
408 #define REQUIRE_UTF8(flagp) STMT_START { \
410 *flagp = RESTART_PARSE|NEED_UTF8; \
415 /* /u is to be chosen if we are supposed to use Unicode rules, or if the
416 * pattern is in UTF-8. This latter condition is in case the outermost rules
417 * are locale. See GH #17278 */
418 #define toUSE_UNI_CHARSET_NOT_DEPENDS (RExC_uni_semantics || UTF)
420 /* Change from /d into /u rules, and restart the parse. RExC_uni_semantics is
421 * a flag that indicates we need to override /d with /u as a result of
422 * something in the pattern. It should only be used in regards to calling
423 * set_regex_charset() or get_regex_charset() */
424 #define REQUIRE_UNI_RULES(flagp, restart_retval) \
426 if (DEPENDS_SEMANTICS) { \
427 set_regex_charset(&RExC_flags, REGEX_UNICODE_CHARSET); \
428 RExC_uni_semantics = 1; \
429 if (RExC_seen_d_op && LIKELY(! IN_PARENS_PASS)) { \
430 /* No need to restart the parse if we haven't seen \
431 * anything that differs between /u and /d, and no need \
432 * to restart immediately if we're going to reparse \
433 * anyway to count parens */ \
434 *flagp |= RESTART_PARSE; \
435 return restart_retval; \
440 #define REQUIRE_BRANCHJ(flagp, restart_retval) \
442 RExC_use_BRANCHJ = 1; \
443 *flagp |= RESTART_PARSE; \
444 return restart_retval; \
447 /* Until we have completed the parse, we leave RExC_total_parens at 0 or
448 * less. After that, it must always be positive, because the whole re is
449 * considered to be surrounded by virtual parens. Setting it to negative
450 * indicates there is some construct that needs to know the actual number of
451 * parens to be properly handled. And that means an extra pass will be
452 * required after we've counted them all */
453 #define ALL_PARENS_COUNTED (RExC_total_parens > 0)
454 #define REQUIRE_PARENS_PASS \
455 STMT_START { /* No-op if have completed a pass */ \
456 if (! ALL_PARENS_COUNTED) RExC_total_parens = -1; \
458 #define IN_PARENS_PASS (RExC_total_parens < 0)
461 /* This is used to return failure (zero) early from the calling function if
462 * various flags in 'flags' are set. Two flags always cause a return:
463 * 'RESTART_PARSE' and 'NEED_UTF8'. 'extra' can be used to specify any
464 * additional flags that should cause a return; 0 if none. If the return will
465 * be done, '*flagp' is first set to be all of the flags that caused the
467 #define RETURN_FAIL_ON_RESTART_OR_FLAGS(flags,flagp,extra) \
469 if ((flags) & (RESTART_PARSE|NEED_UTF8|(extra))) { \
470 *(flagp) = (flags) & (RESTART_PARSE|NEED_UTF8|(extra)); \
475 #define MUST_RESTART(flags) ((flags) & (RESTART_PARSE))
477 #define RETURN_FAIL_ON_RESTART(flags,flagp) \
478 RETURN_FAIL_ON_RESTART_OR_FLAGS( flags, flagp, 0)
479 #define RETURN_FAIL_ON_RESTART_FLAGP(flagp) \
480 if (MUST_RESTART(*(flagp))) return 0
482 /* This converts the named class defined in regcomp.h to its equivalent class
483 * number defined in handy.h. */
484 #define namedclass_to_classnum(class) ((int) ((class) / 2))
485 #define classnum_to_namedclass(classnum) ((classnum) * 2)
487 #define _invlist_union_complement_2nd(a, b, output) \
488 _invlist_union_maybe_complement_2nd(a, b, TRUE, output)
489 #define _invlist_intersection_complement_2nd(a, b, output) \
490 _invlist_intersection_maybe_complement_2nd(a, b, TRUE, output)
492 /* We add a marker if we are deferring expansion of a property that is both
493 * 1) potentiallly user-defined; and
494 * 2) could also be an official Unicode property.
496 * Without this marker, any deferred expansion can only be for a user-defined
497 * one. This marker shouldn't conflict with any that could be in a legal name,
498 * and is appended to its name to indicate this. There is a string and
500 #define DEFERRED_COULD_BE_OFFICIAL_MARKERs "~"
501 #define DEFERRED_COULD_BE_OFFICIAL_MARKERc '~'
503 /* What is infinity for optimization purposes */
504 #define OPTIMIZE_INFTY SSize_t_MAX
506 /* About scan_data_t.
508 During optimisation we recurse through the regexp program performing
509 various inplace (keyhole style) optimisations. In addition study_chunk
510 and scan_commit populate this data structure with information about
511 what strings MUST appear in the pattern. We look for the longest
512 string that must appear at a fixed location, and we look for the
513 longest string that may appear at a floating location. So for instance
518 Both 'FOO' and 'A' are fixed strings. Both 'B' and 'BAR' are floating
519 strings (because they follow a .* construct). study_chunk will identify
520 both FOO and BAR as being the longest fixed and floating strings respectively.
522 The strings can be composites, for instance
526 will result in a composite fixed substring 'foo'.
528 For each string some basic information is maintained:
531 This is the position the string must appear at, or not before.
532 It also implicitly (when combined with minlenp) tells us how many
533 characters must match before the string we are searching for.
534 Likewise when combined with minlenp and the length of the string it
535 tells us how many characters must appear after the string we have
539 Only used for floating strings. This is the rightmost point that
540 the string can appear at. If set to OPTIMIZE_INFTY it indicates that the
541 string can occur infinitely far to the right.
542 For fixed strings, it is equal to min_offset.
545 A pointer to the minimum number of characters of the pattern that the
546 string was found inside. This is important as in the case of positive
547 lookahead or positive lookbehind we can have multiple patterns
552 The minimum length of the pattern overall is 3, the minimum length
553 of the lookahead part is 3, but the minimum length of the part that
554 will actually match is 1. So 'FOO's minimum length is 3, but the
555 minimum length for the F is 1. This is important as the minimum length
556 is used to determine offsets in front of and behind the string being
557 looked for. Since strings can be composites this is the length of the
558 pattern at the time it was committed with a scan_commit. Note that
559 the length is calculated by study_chunk, so that the minimum lengths
560 are not known until the full pattern has been compiled, thus the
561 pointer to the value.
565 In the case of lookbehind the string being searched for can be
566 offset past the start point of the final matching string.
567 If this value was just blithely removed from the min_offset it would
568 invalidate some of the calculations for how many chars must match
569 before or after (as they are derived from min_offset and minlen and
570 the length of the string being searched for).
571 When the final pattern is compiled and the data is moved from the
572 scan_data_t structure into the regexp structure the information
573 about lookbehind is factored in, with the information that would
574 have been lost precalculated in the end_shift field for the
577 The fields pos_min and pos_delta are used to store the minimum offset
578 and the delta to the maximum offset at the current point in the pattern.
582 struct scan_data_substrs {
583 SV *str; /* longest substring found in pattern */
584 SSize_t min_offset; /* earliest point in string it can appear */
585 SSize_t max_offset; /* latest point in string it can appear */
586 SSize_t *minlenp; /* pointer to the minlen relevant to the string */
587 SSize_t lookbehind; /* is the pos of the string modified by LB */
588 I32 flags; /* per substring SF_* and SCF_* flags */
591 typedef struct scan_data_t {
592 /*I32 len_min; unused */
593 /*I32 len_delta; unused */
597 SSize_t last_end; /* min value, <0 unless valid. */
598 SSize_t last_start_min;
599 SSize_t last_start_max;
600 U8 cur_is_floating; /* whether the last_* values should be set as
601 * the next fixed (0) or floating (1)
604 /* [0] is longest fixed substring so far, [1] is longest float so far */
605 struct scan_data_substrs substrs[2];
607 I32 flags; /* common SF_* and SCF_* flags */
609 SSize_t *last_closep;
610 regnode_ssc *start_class;
614 * Forward declarations for pregcomp()'s friends.
617 static const scan_data_t zero_scan_data = {
618 0, 0, NULL, 0, 0, 0, 0,
620 { NULL, 0, 0, 0, 0, 0 },
621 { NULL, 0, 0, 0, 0, 0 },
628 #define SF_BEFORE_SEOL 0x0001
629 #define SF_BEFORE_MEOL 0x0002
630 #define SF_BEFORE_EOL (SF_BEFORE_SEOL|SF_BEFORE_MEOL)
632 #define SF_IS_INF 0x0040
633 #define SF_HAS_PAR 0x0080
634 #define SF_IN_PAR 0x0100
635 #define SF_HAS_EVAL 0x0200
638 /* SCF_DO_SUBSTR is the flag that tells the regexp analyzer to track the
639 * longest substring in the pattern. When it is not set the optimiser keeps
640 * track of position, but does not keep track of the actual strings seen,
642 * So for instance /foo/ will be parsed with SCF_DO_SUBSTR being true, but
645 * Similarly, /foo.*(blah|erm|huh).*fnorble/ will have "foo" and "fnorble"
646 * parsed with SCF_DO_SUBSTR on, but while processing the (...) it will be
647 * turned off because of the alternation (BRANCH). */
648 #define SCF_DO_SUBSTR 0x0400
650 #define SCF_DO_STCLASS_AND 0x0800
651 #define SCF_DO_STCLASS_OR 0x1000
652 #define SCF_DO_STCLASS (SCF_DO_STCLASS_AND|SCF_DO_STCLASS_OR)
653 #define SCF_WHILEM_VISITED_POS 0x2000
655 #define SCF_TRIE_RESTUDY 0x4000 /* Do restudy? */
656 #define SCF_SEEN_ACCEPT 0x8000
657 #define SCF_TRIE_DOING_RESTUDY 0x10000
658 #define SCF_IN_DEFINE 0x20000
663 #define UTF cBOOL(RExC_utf8)
665 /* The enums for all these are ordered so things work out correctly */
666 #define LOC (get_regex_charset(RExC_flags) == REGEX_LOCALE_CHARSET)
667 #define DEPENDS_SEMANTICS (get_regex_charset(RExC_flags) \
668 == REGEX_DEPENDS_CHARSET)
669 #define UNI_SEMANTICS (get_regex_charset(RExC_flags) == REGEX_UNICODE_CHARSET)
670 #define AT_LEAST_UNI_SEMANTICS (get_regex_charset(RExC_flags) \
671 >= REGEX_UNICODE_CHARSET)
672 #define ASCII_RESTRICTED (get_regex_charset(RExC_flags) \
673 == REGEX_ASCII_RESTRICTED_CHARSET)
674 #define AT_LEAST_ASCII_RESTRICTED (get_regex_charset(RExC_flags) \
675 >= REGEX_ASCII_RESTRICTED_CHARSET)
676 #define ASCII_FOLD_RESTRICTED (get_regex_charset(RExC_flags) \
677 == REGEX_ASCII_MORE_RESTRICTED_CHARSET)
679 #define FOLD cBOOL(RExC_flags & RXf_PMf_FOLD)
681 /* For programs that want to be strictly Unicode compatible by dying if any
682 * attempt is made to match a non-Unicode code point against a Unicode
684 #define ALWAYS_WARN_SUPER ckDEAD(packWARN(WARN_NON_UNICODE))
686 #define OOB_NAMEDCLASS -1
688 /* There is no code point that is out-of-bounds, so this is problematic. But
689 * its only current use is to initialize a variable that is always set before
691 #define OOB_UNICODE 0xDEADBEEF
693 #define CHR_SVLEN(sv) (UTF ? sv_len_utf8(sv) : SvCUR(sv))
696 /* length of regex to show in messages that don't mark a position within */
697 #define RegexLengthToShowInErrorMessages 127
700 * If MARKER[12] are adjusted, be sure to adjust the constants at the top
701 * of t/op/regmesg.t, the tests in t/op/re_tests, and those in
702 * op/pragma/warn/regcomp.
704 #define MARKER1 "<-- HERE" /* marker as it appears in the description */
705 #define MARKER2 " <-- HERE " /* marker as it appears within the regex */
707 #define REPORT_LOCATION " in regex; marked by " MARKER1 \
708 " in m/%" UTF8f MARKER2 "%" UTF8f "/"
710 /* The code in this file in places uses one level of recursion with parsing
711 * rebased to an alternate string constructed by us in memory. This can take
712 * the form of something that is completely different from the input, or
713 * something that uses the input as part of the alternate. In the first case,
714 * there should be no possibility of an error, as we are in complete control of
715 * the alternate string. But in the second case we don't completely control
716 * the input portion, so there may be errors in that. Here's an example:
718 * is handled specially because \x{df} folds to a sequence of more than one
719 * character: 'ss'. What is done is to create and parse an alternate string,
720 * which looks like this:
721 * /(?:\x{DF}|[abc\x{DF}def])/ui
722 * where it uses the input unchanged in the middle of something it constructs,
723 * which is a branch for the DF outside the character class, and clustering
724 * parens around the whole thing. (It knows enough to skip the DF inside the
725 * class while in this substitute parse.) 'abc' and 'def' may have errors that
726 * need to be reported. The general situation looks like this:
728 * |<------- identical ------>|
730 * Input: ---------------------------------------------------------------
731 * Constructed: ---------------------------------------------------
733 * |<------- identical ------>|
735 * sI..eI is the portion of the input pattern we are concerned with here.
736 * sC..EC is the constructed substitute parse string.
737 * sC..tC is constructed by us
738 * tC..eC is an exact duplicate of the portion of the input pattern tI..eI.
739 * In the diagram, these are vertically aligned.
740 * eC..EC is also constructed by us.
741 * xC is the position in the substitute parse string where we found a
743 * xI is the position in the original pattern corresponding to xC.
745 * We want to display a message showing the real input string. Thus we need to
746 * translate from xC to xI. We know that xC >= tC, since the portion of the
747 * string sC..tC has been constructed by us, and so shouldn't have errors. We
749 * xI = tI + (xC - tC)
751 * When the substitute parse is constructed, the code needs to set:
754 * RExC_copy_start_in_input (tI)
755 * RExC_copy_start_in_constructed (tC)
756 * and restore them when done.
758 * During normal processing of the input pattern, both
759 * 'RExC_copy_start_in_input' and 'RExC_copy_start_in_constructed' are set to
760 * sI, so that xC equals xI.
763 #define sI RExC_precomp
764 #define eI RExC_precomp_end
765 #define sC RExC_start
767 #define tI RExC_copy_start_in_input
768 #define tC RExC_copy_start_in_constructed
769 #define xI(xC) (tI + (xC - tC))
770 #define xI_offset(xC) (xI(xC) - sI)
772 #define REPORT_LOCATION_ARGS(xC) \
774 (xI(xC) > eI) /* Don't run off end */ \
775 ? eI - sI /* Length before the <--HERE */ \
776 : ((xI_offset(xC) >= 0) \
778 : (Perl_croak(aTHX_ "panic: %s: %d: negative offset: %" \
779 IVdf " trying to output message for " \
781 __FILE__, __LINE__, (IV) xI_offset(xC), \
782 ((int) (eC - sC)), sC), 0)), \
783 sI), /* The input pattern printed up to the <--HERE */ \
785 (xI(xC) > eI) ? 0 : eI - xI(xC), /* Length after <--HERE */ \
786 (xI(xC) > eI) ? eI : xI(xC)) /* pattern after <--HERE */
788 /* Used to point after bad bytes for an error message, but avoid skipping
789 * past a nul byte. */
790 #define SKIP_IF_CHAR(s, e) (!*(s) ? 0 : UTF ? UTF8_SAFE_SKIP(s, e) : 1)
792 /* Set up to clean up after our imminent demise */
793 #define PREPARE_TO_DIE \
796 SAVEFREESV(RExC_rx_sv); \
797 if (RExC_open_parens) \
798 SAVEFREEPV(RExC_open_parens); \
799 if (RExC_close_parens) \
800 SAVEFREEPV(RExC_close_parens); \
804 * Calls SAVEDESTRUCTOR_X if needed, then calls Perl_croak with the given
805 * arg. Show regex, up to a maximum length. If it's too long, chop and add
808 #define _FAIL(code) STMT_START { \
809 const char *ellipses = ""; \
810 IV len = RExC_precomp_end - RExC_precomp; \
813 if (len > RegexLengthToShowInErrorMessages) { \
814 /* chop 10 shorter than the max, to ensure meaning of "..." */ \
815 len = RegexLengthToShowInErrorMessages - 10; \
821 #define FAIL(msg) _FAIL( \
822 Perl_croak(aTHX_ "%s in regex m/%" UTF8f "%s/", \
823 msg, UTF8fARG(UTF, len, RExC_precomp), ellipses))
825 #define FAIL2(msg,arg) _FAIL( \
826 Perl_croak(aTHX_ msg " in regex m/%" UTF8f "%s/", \
827 arg, UTF8fARG(UTF, len, RExC_precomp), ellipses))
829 #define FAIL3(msg,arg1,arg2) _FAIL( \
830 Perl_croak(aTHX_ msg " in regex m/%" UTF8f "%s/", \
831 arg1, arg2, UTF8fARG(UTF, len, RExC_precomp), ellipses))
834 * Simple_vFAIL -- like FAIL, but marks the current location in the scan
836 #define Simple_vFAIL(m) STMT_START { \
837 Perl_croak(aTHX_ "%s" REPORT_LOCATION, \
838 m, REPORT_LOCATION_ARGS(RExC_parse)); \
842 * Calls SAVEDESTRUCTOR_X if needed, then Simple_vFAIL()
844 #define vFAIL(m) STMT_START { \
850 * Like Simple_vFAIL(), but accepts two arguments.
852 #define Simple_vFAIL2(m,a1) STMT_START { \
853 S_re_croak(aTHX_ UTF, m REPORT_LOCATION, a1, \
854 REPORT_LOCATION_ARGS(RExC_parse)); \
858 * Calls SAVEDESTRUCTOR_X if needed, then Simple_vFAIL2().
860 #define vFAIL2(m,a1) STMT_START { \
862 Simple_vFAIL2(m, a1); \
867 * Like Simple_vFAIL(), but accepts three arguments.
869 #define Simple_vFAIL3(m, a1, a2) STMT_START { \
870 S_re_croak(aTHX_ UTF, m REPORT_LOCATION, a1, a2, \
871 REPORT_LOCATION_ARGS(RExC_parse)); \
875 * Calls SAVEDESTRUCTOR_X if needed, then Simple_vFAIL3().
877 #define vFAIL3(m,a1,a2) STMT_START { \
879 Simple_vFAIL3(m, a1, a2); \
883 * Like Simple_vFAIL(), but accepts four arguments.
885 #define Simple_vFAIL4(m, a1, a2, a3) STMT_START { \
886 S_re_croak(aTHX_ UTF, m REPORT_LOCATION, a1, a2, a3, \
887 REPORT_LOCATION_ARGS(RExC_parse)); \
890 #define vFAIL4(m,a1,a2,a3) STMT_START { \
892 Simple_vFAIL4(m, a1, a2, a3); \
895 /* A specialized version of vFAIL2 that works with UTF8f */
896 #define vFAIL2utf8f(m, a1) STMT_START { \
898 S_re_croak(aTHX_ UTF, m REPORT_LOCATION, a1, \
899 REPORT_LOCATION_ARGS(RExC_parse)); \
902 #define vFAIL3utf8f(m, a1, a2) STMT_START { \
904 S_re_croak(aTHX_ UTF, m REPORT_LOCATION, a1, a2, \
905 REPORT_LOCATION_ARGS(RExC_parse)); \
908 /* Setting this to NULL is a signal to not output warnings */
909 #define TURN_OFF_WARNINGS_IN_SUBSTITUTE_PARSE \
911 RExC_save_copy_start_in_constructed = RExC_copy_start_in_constructed;\
912 RExC_copy_start_in_constructed = NULL; \
914 #define RESTORE_WARNINGS \
915 RExC_copy_start_in_constructed = RExC_save_copy_start_in_constructed
917 /* Since a warning can be generated multiple times as the input is reparsed, we
918 * output it the first time we come to that point in the parse, but suppress it
919 * otherwise. 'RExC_copy_start_in_constructed' being NULL is a flag to not
920 * generate any warnings */
921 #define TO_OUTPUT_WARNINGS(loc) \
922 ( RExC_copy_start_in_constructed \
923 && ((xI(loc)) - RExC_precomp) > (Ptrdiff_t) RExC_latest_warn_offset)
925 /* After we've emitted a warning, we save the position in the input so we don't
927 #define UPDATE_WARNINGS_LOC(loc) \
929 if (TO_OUTPUT_WARNINGS(loc)) { \
930 RExC_latest_warn_offset = MAX(sI, MIN(eI, xI(loc))) \
935 /* 'warns' is the output of the packWARNx macro used in 'code' */
936 #define _WARN_HELPER(loc, warns, code) \
938 if (! RExC_copy_start_in_constructed) { \
939 Perl_croak( aTHX_ "panic! %s: %d: Tried to warn when none" \
940 " expected at '%s'", \
941 __FILE__, __LINE__, loc); \
943 if (TO_OUTPUT_WARNINGS(loc)) { \
947 UPDATE_WARNINGS_LOC(loc); \
951 /* m is not necessarily a "literal string", in this macro */
952 #define warn_non_literal_string(loc, packed_warn, m) \
953 _WARN_HELPER(loc, packed_warn, \
954 Perl_warner(aTHX_ packed_warn, \
955 "%s" REPORT_LOCATION, \
956 m, REPORT_LOCATION_ARGS(loc)))
957 #define reg_warn_non_literal_string(loc, m) \
958 warn_non_literal_string(loc, packWARN(WARN_REGEXP), m)
960 #define ckWARN2_non_literal_string(loc, packwarn, m, a1) \
963 Size_t format_size = strlen(m) + strlen(REPORT_LOCATION)+ 1;\
964 Newx(format, format_size, char); \
965 my_strlcpy(format, m, format_size); \
966 my_strlcat(format, REPORT_LOCATION, format_size); \
967 SAVEFREEPV(format); \
968 _WARN_HELPER(loc, packwarn, \
969 Perl_ck_warner(aTHX_ packwarn, \
971 a1, REPORT_LOCATION_ARGS(loc))); \
974 #define ckWARNreg(loc,m) \
975 _WARN_HELPER(loc, packWARN(WARN_REGEXP), \
976 Perl_ck_warner(aTHX_ packWARN(WARN_REGEXP), \
978 REPORT_LOCATION_ARGS(loc)))
980 #define vWARN(loc, m) \
981 _WARN_HELPER(loc, packWARN(WARN_REGEXP), \
982 Perl_warner(aTHX_ packWARN(WARN_REGEXP), \
984 REPORT_LOCATION_ARGS(loc))) \
986 #define vWARN_dep(loc, m) \
987 _WARN_HELPER(loc, packWARN(WARN_DEPRECATED), \
988 Perl_warner(aTHX_ packWARN(WARN_DEPRECATED), \
990 REPORT_LOCATION_ARGS(loc)))
992 #define ckWARNdep(loc,m) \
993 _WARN_HELPER(loc, packWARN(WARN_DEPRECATED), \
994 Perl_ck_warner_d(aTHX_ packWARN(WARN_DEPRECATED), \
996 REPORT_LOCATION_ARGS(loc)))
998 #define ckWARNregdep(loc,m) \
999 _WARN_HELPER(loc, packWARN2(WARN_DEPRECATED, WARN_REGEXP), \
1000 Perl_ck_warner_d(aTHX_ packWARN2(WARN_DEPRECATED, \
1002 m REPORT_LOCATION, \
1003 REPORT_LOCATION_ARGS(loc)))
1005 #define ckWARN2reg_d(loc,m, a1) \
1006 _WARN_HELPER(loc, packWARN(WARN_REGEXP), \
1007 Perl_ck_warner_d(aTHX_ packWARN(WARN_REGEXP), \
1008 m REPORT_LOCATION, \
1009 a1, REPORT_LOCATION_ARGS(loc)))
1011 #define ckWARN2reg(loc, m, a1) \
1012 _WARN_HELPER(loc, packWARN(WARN_REGEXP), \
1013 Perl_ck_warner(aTHX_ packWARN(WARN_REGEXP), \
1014 m REPORT_LOCATION, \
1015 a1, REPORT_LOCATION_ARGS(loc)))
1017 #define vWARN3(loc, m, a1, a2) \
1018 _WARN_HELPER(loc, packWARN(WARN_REGEXP), \
1019 Perl_warner(aTHX_ packWARN(WARN_REGEXP), \
1020 m REPORT_LOCATION, \
1021 a1, a2, REPORT_LOCATION_ARGS(loc)))
1023 #define ckWARN3reg(loc, m, a1, a2) \
1024 _WARN_HELPER(loc, packWARN(WARN_REGEXP), \
1025 Perl_ck_warner(aTHX_ packWARN(WARN_REGEXP), \
1026 m REPORT_LOCATION, \
1028 REPORT_LOCATION_ARGS(loc)))
1030 #define vWARN4(loc, m, a1, a2, a3) \
1031 _WARN_HELPER(loc, packWARN(WARN_REGEXP), \
1032 Perl_warner(aTHX_ packWARN(WARN_REGEXP), \
1033 m REPORT_LOCATION, \
1035 REPORT_LOCATION_ARGS(loc)))
1037 #define ckWARN4reg(loc, m, a1, a2, a3) \
1038 _WARN_HELPER(loc, packWARN(WARN_REGEXP), \
1039 Perl_ck_warner(aTHX_ packWARN(WARN_REGEXP), \
1040 m REPORT_LOCATION, \
1042 REPORT_LOCATION_ARGS(loc)))
1044 #define vWARN5(loc, m, a1, a2, a3, a4) \
1045 _WARN_HELPER(loc, packWARN(WARN_REGEXP), \
1046 Perl_warner(aTHX_ packWARN(WARN_REGEXP), \
1047 m REPORT_LOCATION, \
1049 REPORT_LOCATION_ARGS(loc)))
1051 #define ckWARNexperimental(loc, class, m) \
1053 if (! RExC_warned_ ## class) { /* warn once per compilation */ \
1054 RExC_warned_ ## class = 1; \
1055 _WARN_HELPER(loc, packWARN(class), \
1056 Perl_ck_warner_d(aTHX_ packWARN(class), \
1057 m REPORT_LOCATION, \
1058 REPORT_LOCATION_ARGS(loc)));\
1062 /* Convert between a pointer to a node and its offset from the beginning of the
1064 #define REGNODE_p(offset) (RExC_emit_start + (offset))
1065 #define REGNODE_OFFSET(node) ((node) - RExC_emit_start)
1067 /* Macros for recording node offsets. 20001227 mjd@plover.com
1068 * Nodes are numbered 1, 2, 3, 4. Node #n's position is recorded in
1069 * element 2*n-1 of the array. Element #2n holds the byte length node #n.
1070 * Element 0 holds the number n.
1071 * Position is 1 indexed.
1073 #ifndef RE_TRACK_PATTERN_OFFSETS
1074 #define Set_Node_Offset_To_R(offset,byte)
1075 #define Set_Node_Offset(node,byte)
1076 #define Set_Cur_Node_Offset
1077 #define Set_Node_Length_To_R(node,len)
1078 #define Set_Node_Length(node,len)
1079 #define Set_Node_Cur_Length(node,start)
1080 #define Node_Offset(n)
1081 #define Node_Length(n)
1082 #define Set_Node_Offset_Length(node,offset,len)
1083 #define ProgLen(ri) ri->u.proglen
1084 #define SetProgLen(ri,x) ri->u.proglen = x
1085 #define Track_Code(code)
1087 #define ProgLen(ri) ri->u.offsets[0]
1088 #define SetProgLen(ri,x) ri->u.offsets[0] = x
1089 #define Set_Node_Offset_To_R(offset,byte) STMT_START { \
1090 MJD_OFFSET_DEBUG(("** (%d) offset of node %d is %d.\n", \
1091 __LINE__, (int)(offset), (int)(byte))); \
1092 if((offset) < 0) { \
1093 Perl_croak(aTHX_ "value of node is %d in Offset macro", \
1096 RExC_offsets[2*(offset)-1] = (byte); \
1100 #define Set_Node_Offset(node,byte) \
1101 Set_Node_Offset_To_R(REGNODE_OFFSET(node), (byte)-RExC_start)
1102 #define Set_Cur_Node_Offset Set_Node_Offset(RExC_emit, RExC_parse)
1104 #define Set_Node_Length_To_R(node,len) STMT_START { \
1105 MJD_OFFSET_DEBUG(("** (%d) size of node %d is %d.\n", \
1106 __LINE__, (int)(node), (int)(len))); \
1108 Perl_croak(aTHX_ "value of node is %d in Length macro", \
1111 RExC_offsets[2*(node)] = (len); \
1115 #define Set_Node_Length(node,len) \
1116 Set_Node_Length_To_R(REGNODE_OFFSET(node), len)
1117 #define Set_Node_Cur_Length(node, start) \
1118 Set_Node_Length(node, RExC_parse - start)
1120 /* Get offsets and lengths */
1121 #define Node_Offset(n) (RExC_offsets[2*(REGNODE_OFFSET(n))-1])
1122 #define Node_Length(n) (RExC_offsets[2*(REGNODE_OFFSET(n))])
1124 #define Set_Node_Offset_Length(node,offset,len) STMT_START { \
1125 Set_Node_Offset_To_R(REGNODE_OFFSET(node), (offset)); \
1126 Set_Node_Length_To_R(REGNODE_OFFSET(node), (len)); \
1129 #define Track_Code(code) STMT_START { code } STMT_END
1132 #if PERL_ENABLE_EXPERIMENTAL_REGEX_OPTIMISATIONS
1133 #define EXPERIMENTAL_INPLACESCAN
1134 #endif /*PERL_ENABLE_EXPERIMENTAL_REGEX_OPTIMISATIONS*/
1138 Perl_re_printf(pTHX_ const char *fmt, ...)
1142 PerlIO *f= Perl_debug_log;
1143 PERL_ARGS_ASSERT_RE_PRINTF;
1145 result = PerlIO_vprintf(f, fmt, ap);
1151 Perl_re_indentf(pTHX_ const char *fmt, U32 depth, ...)
1155 PerlIO *f= Perl_debug_log;
1156 PERL_ARGS_ASSERT_RE_INDENTF;
1157 va_start(ap, depth);
1158 PerlIO_printf(f, "%*s", ( (int)depth % 20 ) * 2, "");
1159 result = PerlIO_vprintf(f, fmt, ap);
1163 #endif /* DEBUGGING */
1165 #define DEBUG_RExC_seen() \
1166 DEBUG_OPTIMISE_MORE_r({ \
1167 Perl_re_printf( aTHX_ "RExC_seen: "); \
1169 if (RExC_seen & REG_ZERO_LEN_SEEN) \
1170 Perl_re_printf( aTHX_ "REG_ZERO_LEN_SEEN "); \
1172 if (RExC_seen & REG_LOOKBEHIND_SEEN) \
1173 Perl_re_printf( aTHX_ "REG_LOOKBEHIND_SEEN "); \
1175 if (RExC_seen & REG_GPOS_SEEN) \
1176 Perl_re_printf( aTHX_ "REG_GPOS_SEEN "); \
1178 if (RExC_seen & REG_RECURSE_SEEN) \
1179 Perl_re_printf( aTHX_ "REG_RECURSE_SEEN "); \
1181 if (RExC_seen & REG_TOP_LEVEL_BRANCHES_SEEN) \
1182 Perl_re_printf( aTHX_ "REG_TOP_LEVEL_BRANCHES_SEEN "); \
1184 if (RExC_seen & REG_VERBARG_SEEN) \
1185 Perl_re_printf( aTHX_ "REG_VERBARG_SEEN "); \
1187 if (RExC_seen & REG_CUTGROUP_SEEN) \
1188 Perl_re_printf( aTHX_ "REG_CUTGROUP_SEEN "); \
1190 if (RExC_seen & REG_RUN_ON_COMMENT_SEEN) \
1191 Perl_re_printf( aTHX_ "REG_RUN_ON_COMMENT_SEEN "); \
1193 if (RExC_seen & REG_UNFOLDED_MULTI_SEEN) \
1194 Perl_re_printf( aTHX_ "REG_UNFOLDED_MULTI_SEEN "); \
1196 if (RExC_seen & REG_UNBOUNDED_QUANTIFIER_SEEN) \
1197 Perl_re_printf( aTHX_ "REG_UNBOUNDED_QUANTIFIER_SEEN "); \
1199 Perl_re_printf( aTHX_ "\n"); \
1202 #define DEBUG_SHOW_STUDY_FLAG(flags,flag) \
1203 if ((flags) & flag) Perl_re_printf( aTHX_ "%s ", #flag)
1208 S_debug_show_study_flags(pTHX_ U32 flags, const char *open_str,
1209 const char *close_str)
1214 Perl_re_printf( aTHX_ "%s", open_str);
1215 DEBUG_SHOW_STUDY_FLAG(flags, SF_BEFORE_SEOL);
1216 DEBUG_SHOW_STUDY_FLAG(flags, SF_BEFORE_MEOL);
1217 DEBUG_SHOW_STUDY_FLAG(flags, SF_IS_INF);
1218 DEBUG_SHOW_STUDY_FLAG(flags, SF_HAS_PAR);
1219 DEBUG_SHOW_STUDY_FLAG(flags, SF_IN_PAR);
1220 DEBUG_SHOW_STUDY_FLAG(flags, SF_HAS_EVAL);
1221 DEBUG_SHOW_STUDY_FLAG(flags, SCF_DO_SUBSTR);
1222 DEBUG_SHOW_STUDY_FLAG(flags, SCF_DO_STCLASS_AND);
1223 DEBUG_SHOW_STUDY_FLAG(flags, SCF_DO_STCLASS_OR);
1224 DEBUG_SHOW_STUDY_FLAG(flags, SCF_DO_STCLASS);
1225 DEBUG_SHOW_STUDY_FLAG(flags, SCF_WHILEM_VISITED_POS);
1226 DEBUG_SHOW_STUDY_FLAG(flags, SCF_TRIE_RESTUDY);
1227 DEBUG_SHOW_STUDY_FLAG(flags, SCF_SEEN_ACCEPT);
1228 DEBUG_SHOW_STUDY_FLAG(flags, SCF_TRIE_DOING_RESTUDY);
1229 DEBUG_SHOW_STUDY_FLAG(flags, SCF_IN_DEFINE);
1230 Perl_re_printf( aTHX_ "%s", close_str);
1235 S_debug_studydata(pTHX_ const char *where, scan_data_t *data,
1236 U32 depth, int is_inf)
1238 DECLARE_AND_GET_RE_DEBUG_FLAGS;
1240 DEBUG_OPTIMISE_MORE_r({
1243 Perl_re_indentf(aTHX_ "%s: Pos:%" IVdf "/%" IVdf " Flags: 0x%" UVXf,
1247 (IV)data->pos_delta,
1251 S_debug_show_study_flags(aTHX_ data->flags," [","]");
1253 Perl_re_printf( aTHX_
1254 " Whilem_c: %" IVdf " Lcp: %" IVdf " %s",
1256 (IV)(data->last_closep ? *((data)->last_closep) : -1),
1257 is_inf ? "INF " : ""
1260 if (data->last_found) {
1262 Perl_re_printf(aTHX_
1263 "Last:'%s' %" IVdf ":%" IVdf "/%" IVdf,
1264 SvPVX_const(data->last_found),
1266 (IV)data->last_start_min,
1267 (IV)data->last_start_max
1270 for (i = 0; i < 2; i++) {
1271 Perl_re_printf(aTHX_
1272 " %s%s: '%s' @ %" IVdf "/%" IVdf,
1273 data->cur_is_floating == i ? "*" : "",
1274 i ? "Float" : "Fixed",
1275 SvPVX_const(data->substrs[i].str),
1276 (IV)data->substrs[i].min_offset,
1277 (IV)data->substrs[i].max_offset
1279 S_debug_show_study_flags(aTHX_ data->substrs[i].flags," [","]");
1283 Perl_re_printf( aTHX_ "\n");
1289 S_debug_peep(pTHX_ const char *str, const RExC_state_t *pRExC_state,
1290 regnode *scan, U32 depth, U32 flags)
1292 DECLARE_AND_GET_RE_DEBUG_FLAGS;
1299 Next = regnext(scan);
1300 regprop(RExC_rx, RExC_mysv, scan, NULL, pRExC_state);
1301 Perl_re_indentf( aTHX_ "%s>%3d: %s (%d)",
1304 REG_NODE_NUM(scan), SvPV_nolen_const(RExC_mysv),
1305 Next ? (REG_NODE_NUM(Next)) : 0 );
1306 S_debug_show_study_flags(aTHX_ flags," [ ","]");
1307 Perl_re_printf( aTHX_ "\n");
1312 # define DEBUG_STUDYDATA(where, data, depth, is_inf) \
1313 S_debug_studydata(aTHX_ where, data, depth, is_inf)
1315 # define DEBUG_PEEP(str, scan, depth, flags) \
1316 S_debug_peep(aTHX_ str, pRExC_state, scan, depth, flags)
1319 # define DEBUG_STUDYDATA(where, data, depth, is_inf) NOOP
1320 # define DEBUG_PEEP(str, scan, depth, flags) NOOP
1324 /* =========================================================
1325 * BEGIN edit_distance stuff.
1327 * This calculates how many single character changes of any type are needed to
1328 * transform a string into another one. It is taken from version 3.1 of
1330 * https://metacpan.org/pod/Text::Levenshtein::Damerau::XS
1333 /* Our unsorted dictionary linked list. */
1334 /* Note we use UVs, not chars. */
1339 struct dictionary* next;
1341 typedef struct dictionary item;
1344 PERL_STATIC_INLINE item*
1345 push(UV key, item* curr)
1348 Newx(head, 1, item);
1356 PERL_STATIC_INLINE item*
1357 find(item* head, UV key)
1359 item* iterator = head;
1361 if (iterator->key == key){
1364 iterator = iterator->next;
1370 PERL_STATIC_INLINE item*
1371 uniquePush(item* head, UV key)
1373 item* iterator = head;
1376 if (iterator->key == key) {
1379 iterator = iterator->next;
1382 return push(key, head);
1385 PERL_STATIC_INLINE void
1386 dict_free(item* head)
1388 item* iterator = head;
1391 item* temp = iterator;
1392 iterator = iterator->next;
1399 /* End of Dictionary Stuff */
1401 /* All calculations/work are done here */
1403 S_edit_distance(const UV* src,
1405 const STRLEN x, /* length of src[] */
1406 const STRLEN y, /* length of tgt[] */
1407 const SSize_t maxDistance
1411 UV swapCount, swapScore, targetCharCount, i, j;
1413 UV score_ceil = x + y;
1415 PERL_ARGS_ASSERT_EDIT_DISTANCE;
1417 /* intialize matrix start values */
1418 Newx(scores, ( (x + 2) * (y + 2)), UV);
1419 scores[0] = score_ceil;
1420 scores[1 * (y + 2) + 0] = score_ceil;
1421 scores[0 * (y + 2) + 1] = score_ceil;
1422 scores[1 * (y + 2) + 1] = 0;
1423 head = uniquePush(uniquePush(head, src[0]), tgt[0]);
1428 for (i=1;i<=x;i++) {
1430 head = uniquePush(head, src[i]);
1431 scores[(i+1) * (y + 2) + 1] = i;
1432 scores[(i+1) * (y + 2) + 0] = score_ceil;
1435 for (j=1;j<=y;j++) {
1438 head = uniquePush(head, tgt[j]);
1439 scores[1 * (y + 2) + (j + 1)] = j;
1440 scores[0 * (y + 2) + (j + 1)] = score_ceil;
1443 targetCharCount = find(head, tgt[j-1])->value;
1444 swapScore = scores[targetCharCount * (y + 2) + swapCount] + i - targetCharCount - 1 + j - swapCount;
1446 if (src[i-1] != tgt[j-1]){
1447 scores[(i+1) * (y + 2) + (j + 1)] = MIN(swapScore,(MIN(scores[i * (y + 2) + j], MIN(scores[(i+1) * (y + 2) + j], scores[i * (y + 2) + (j + 1)])) + 1));
1451 scores[(i+1) * (y + 2) + (j + 1)] = MIN(scores[i * (y + 2) + j], swapScore);
1455 find(head, src[i-1])->value = i;
1459 IV score = scores[(x+1) * (y + 2) + (y + 1)];
1462 return (maxDistance != 0 && maxDistance < score)?(-1):score;
1466 /* END of edit_distance() stuff
1467 * ========================================================= */
1469 /* Mark that we cannot extend a found fixed substring at this point.
1470 Update the longest found anchored substring or the longest found
1471 floating substrings if needed. */
1474 S_scan_commit(pTHX_ const RExC_state_t *pRExC_state, scan_data_t *data,
1475 SSize_t *minlenp, int is_inf)
1477 const STRLEN l = CHR_SVLEN(data->last_found);
1478 SV * const longest_sv = data->substrs[data->cur_is_floating].str;
1479 const STRLEN old_l = CHR_SVLEN(longest_sv);
1480 DECLARE_AND_GET_RE_DEBUG_FLAGS;
1482 PERL_ARGS_ASSERT_SCAN_COMMIT;
1484 if ((l >= old_l) && ((l > old_l) || (data->flags & SF_BEFORE_EOL))) {
1485 const U8 i = data->cur_is_floating;
1486 SvSetMagicSV(longest_sv, data->last_found);
1487 data->substrs[i].min_offset = l ? data->last_start_min : data->pos_min;
1490 data->substrs[0].max_offset = data->substrs[0].min_offset;
1492 data->substrs[1].max_offset =
1496 ? data->last_start_max
1497 /* temporary underflow guard for 5.32 */
1498 : data->pos_delta < 0 ? OPTIMIZE_INFTY
1499 : (data->pos_delta > OPTIMIZE_INFTY - data->pos_min
1501 : data->pos_min + data->pos_delta));
1504 data->substrs[i].flags &= ~SF_BEFORE_EOL;
1505 data->substrs[i].flags |= data->flags & SF_BEFORE_EOL;
1506 data->substrs[i].minlenp = minlenp;
1507 data->substrs[i].lookbehind = 0;
1510 SvCUR_set(data->last_found, 0);
1512 SV * const sv = data->last_found;
1513 if (SvUTF8(sv) && SvMAGICAL(sv)) {
1514 MAGIC * const mg = mg_find(sv, PERL_MAGIC_utf8);
1519 data->last_end = -1;
1520 data->flags &= ~SF_BEFORE_EOL;
1521 DEBUG_STUDYDATA("commit", data, 0, is_inf);
1524 /* An SSC is just a regnode_charclass_posix with an extra field: the inversion
1525 * list that describes which code points it matches */
1528 S_ssc_anything(pTHX_ regnode_ssc *ssc)
1530 /* Set the SSC 'ssc' to match an empty string or any code point */
1532 PERL_ARGS_ASSERT_SSC_ANYTHING;
1534 assert(is_ANYOF_SYNTHETIC(ssc));
1536 /* mortalize so won't leak */
1537 ssc->invlist = sv_2mortal(_add_range_to_invlist(NULL, 0, UV_MAX));
1538 ANYOF_FLAGS(ssc) |= SSC_MATCHES_EMPTY_STRING; /* Plus matches empty */
1542 S_ssc_is_anything(const regnode_ssc *ssc)
1544 /* Returns TRUE if the SSC 'ssc' can match the empty string and any code
1545 * point; FALSE otherwise. Thus, this is used to see if using 'ssc' buys
1546 * us anything: if the function returns TRUE, 'ssc' hasn't been restricted
1547 * in any way, so there's no point in using it */
1552 PERL_ARGS_ASSERT_SSC_IS_ANYTHING;
1554 assert(is_ANYOF_SYNTHETIC(ssc));
1556 if (! (ANYOF_FLAGS(ssc) & SSC_MATCHES_EMPTY_STRING)) {
1560 /* See if the list consists solely of the range 0 - Infinity */
1561 invlist_iterinit(ssc->invlist);
1562 ret = invlist_iternext(ssc->invlist, &start, &end)
1566 invlist_iterfinish(ssc->invlist);
1572 /* If e.g., both \w and \W are set, matches everything */
1573 if (ANYOF_POSIXL_SSC_TEST_ANY_SET(ssc)) {
1575 for (i = 0; i < ANYOF_POSIXL_MAX; i += 2) {
1576 if (ANYOF_POSIXL_TEST(ssc, i) && ANYOF_POSIXL_TEST(ssc, i+1)) {
1586 S_ssc_init(pTHX_ const RExC_state_t *pRExC_state, regnode_ssc *ssc)
1588 /* Initializes the SSC 'ssc'. This includes setting it to match an empty
1589 * string, any code point, or any posix class under locale */
1591 PERL_ARGS_ASSERT_SSC_INIT;
1593 Zero(ssc, 1, regnode_ssc);
1594 set_ANYOF_SYNTHETIC(ssc);
1595 ARG_SET(ssc, ANYOF_ONLY_HAS_BITMAP);
1598 /* If any portion of the regex is to operate under locale rules that aren't
1599 * fully known at compile time, initialization includes it. The reason
1600 * this isn't done for all regexes is that the optimizer was written under
1601 * the assumption that locale was all-or-nothing. Given the complexity and
1602 * lack of documentation in the optimizer, and that there are inadequate
1603 * test cases for locale, many parts of it may not work properly, it is
1604 * safest to avoid locale unless necessary. */
1605 if (RExC_contains_locale) {
1606 ANYOF_POSIXL_SETALL(ssc);
1609 ANYOF_POSIXL_ZERO(ssc);
1614 S_ssc_is_cp_posixl_init(const RExC_state_t *pRExC_state,
1615 const regnode_ssc *ssc)
1617 /* Returns TRUE if the SSC 'ssc' is in its initial state with regard only
1618 * to the list of code points matched, and locale posix classes; hence does
1619 * not check its flags) */
1624 PERL_ARGS_ASSERT_SSC_IS_CP_POSIXL_INIT;
1626 assert(is_ANYOF_SYNTHETIC(ssc));
1628 invlist_iterinit(ssc->invlist);
1629 ret = invlist_iternext(ssc->invlist, &start, &end)
1633 invlist_iterfinish(ssc->invlist);
1639 if (RExC_contains_locale && ! ANYOF_POSIXL_SSC_TEST_ALL_SET(ssc)) {
1646 #define INVLIST_INDEX 0
1647 #define ONLY_LOCALE_MATCHES_INDEX 1
1648 #define DEFERRED_USER_DEFINED_INDEX 2
1651 S_get_ANYOF_cp_list_for_ssc(pTHX_ const RExC_state_t *pRExC_state,
1652 const regnode_charclass* const node)
1654 /* Returns a mortal inversion list defining which code points are matched
1655 * by 'node', which is of type ANYOF. Handles complementing the result if
1656 * appropriate. If some code points aren't knowable at this time, the
1657 * returned list must, and will, contain every code point that is a
1661 SV* only_utf8_locale_invlist = NULL;
1663 const U32 n = ARG(node);
1664 bool new_node_has_latin1 = FALSE;
1665 const U8 flags = (inRANGE(OP(node), ANYOFH, ANYOFRb))
1667 : ANYOF_FLAGS(node);
1669 PERL_ARGS_ASSERT_GET_ANYOF_CP_LIST_FOR_SSC;
1671 /* Look at the data structure created by S_set_ANYOF_arg() */
1672 if (n != ANYOF_ONLY_HAS_BITMAP) {
1673 SV * const rv = MUTABLE_SV(RExC_rxi->data->data[n]);
1674 AV * const av = MUTABLE_AV(SvRV(rv));
1675 SV **const ary = AvARRAY(av);
1676 assert(RExC_rxi->data->what[n] == 's');
1678 if (av_tindex_skip_len_mg(av) >= DEFERRED_USER_DEFINED_INDEX) {
1680 /* Here there are things that won't be known until runtime -- we
1681 * have to assume it could be anything */
1682 invlist = sv_2mortal(_new_invlist(1));
1683 return _add_range_to_invlist(invlist, 0, UV_MAX);
1685 else if (ary[INVLIST_INDEX]) {
1687 /* Use the node's inversion list */
1688 invlist = sv_2mortal(invlist_clone(ary[INVLIST_INDEX], NULL));
1691 /* Get the code points valid only under UTF-8 locales */
1692 if ( (flags & ANYOFL_FOLD)
1693 && av_tindex_skip_len_mg(av) >= ONLY_LOCALE_MATCHES_INDEX)
1695 only_utf8_locale_invlist = ary[ONLY_LOCALE_MATCHES_INDEX];
1700 invlist = sv_2mortal(_new_invlist(0));
1703 /* An ANYOF node contains a bitmap for the first NUM_ANYOF_CODE_POINTS
1704 * code points, and an inversion list for the others, but if there are code
1705 * points that should match only conditionally on the target string being
1706 * UTF-8, those are placed in the inversion list, and not the bitmap.
1707 * Since there are circumstances under which they could match, they are
1708 * included in the SSC. But if the ANYOF node is to be inverted, we have
1709 * to exclude them here, so that when we invert below, the end result
1710 * actually does include them. (Think about "\xe0" =~ /[^\xc0]/di;). We
1711 * have to do this here before we add the unconditionally matched code
1713 if (flags & ANYOF_INVERT) {
1714 _invlist_intersection_complement_2nd(invlist,
1719 /* Add in the points from the bit map */
1720 if (! inRANGE(OP(node), ANYOFH, ANYOFRb)) {
1721 for (i = 0; i < NUM_ANYOF_CODE_POINTS; i++) {
1722 if (ANYOF_BITMAP_TEST(node, i)) {
1723 unsigned int start = i++;
1725 for (; i < NUM_ANYOF_CODE_POINTS
1726 && ANYOF_BITMAP_TEST(node, i); ++i)
1730 invlist = _add_range_to_invlist(invlist, start, i-1);
1731 new_node_has_latin1 = TRUE;
1736 /* If this can match all upper Latin1 code points, have to add them
1737 * as well. But don't add them if inverting, as when that gets done below,
1738 * it would exclude all these characters, including the ones it shouldn't
1739 * that were added just above */
1740 if (! (flags & ANYOF_INVERT) && OP(node) == ANYOFD
1741 && (flags & ANYOF_SHARED_d_MATCHES_ALL_NON_UTF8_NON_ASCII_non_d_WARN_SUPER))
1743 _invlist_union(invlist, PL_UpperLatin1, &invlist);
1746 /* Similarly for these */
1747 if (flags & ANYOF_MATCHES_ALL_ABOVE_BITMAP) {
1748 _invlist_union_complement_2nd(invlist, PL_InBitmap, &invlist);
1751 if (flags & ANYOF_INVERT) {
1752 _invlist_invert(invlist);
1754 else if (flags & ANYOFL_FOLD) {
1755 if (new_node_has_latin1) {
1757 /* Under /li, any 0-255 could fold to any other 0-255, depending on
1758 * the locale. We can skip this if there are no 0-255 at all. */
1759 _invlist_union(invlist, PL_Latin1, &invlist);
1761 invlist = add_cp_to_invlist(invlist, LATIN_SMALL_LETTER_DOTLESS_I);
1762 invlist = add_cp_to_invlist(invlist, LATIN_CAPITAL_LETTER_I_WITH_DOT_ABOVE);
1765 if (_invlist_contains_cp(invlist, LATIN_SMALL_LETTER_DOTLESS_I)) {
1766 invlist = add_cp_to_invlist(invlist, 'I');
1768 if (_invlist_contains_cp(invlist,
1769 LATIN_CAPITAL_LETTER_I_WITH_DOT_ABOVE))
1771 invlist = add_cp_to_invlist(invlist, 'i');
1776 /* Similarly add the UTF-8 locale possible matches. These have to be
1777 * deferred until after the non-UTF-8 locale ones are taken care of just
1778 * above, or it leads to wrong results under ANYOF_INVERT */
1779 if (only_utf8_locale_invlist) {
1780 _invlist_union_maybe_complement_2nd(invlist,
1781 only_utf8_locale_invlist,
1782 flags & ANYOF_INVERT,
1789 /* These two functions currently do the exact same thing */
1790 #define ssc_init_zero ssc_init
1792 #define ssc_add_cp(ssc, cp) ssc_add_range((ssc), (cp), (cp))
1793 #define ssc_match_all_cp(ssc) ssc_add_range(ssc, 0, UV_MAX)
1795 /* 'AND' a given class with another one. Can create false positives. 'ssc'
1796 * should not be inverted. 'and_with->flags & ANYOF_MATCHES_POSIXL' should be
1797 * 0 if 'and_with' is a regnode_charclass instead of a regnode_ssc. */
1800 S_ssc_and(pTHX_ const RExC_state_t *pRExC_state, regnode_ssc *ssc,
1801 const regnode_charclass *and_with)
1803 /* Accumulate into SSC 'ssc' its 'AND' with 'and_with', which is either
1804 * another SSC or a regular ANYOF class. Can create false positives. */
1807 U8 and_with_flags = inRANGE(OP(and_with), ANYOFH, ANYOFRb)
1809 : ANYOF_FLAGS(and_with);
1812 PERL_ARGS_ASSERT_SSC_AND;
1814 assert(is_ANYOF_SYNTHETIC(ssc));
1816 /* 'and_with' is used as-is if it too is an SSC; otherwise have to extract
1817 * the code point inversion list and just the relevant flags */
1818 if (is_ANYOF_SYNTHETIC(and_with)) {
1819 anded_cp_list = ((regnode_ssc *)and_with)->invlist;
1820 anded_flags = and_with_flags;
1822 /* XXX This is a kludge around what appears to be deficiencies in the
1823 * optimizer. If we make S_ssc_anything() add in the WARN_SUPER flag,
1824 * there are paths through the optimizer where it doesn't get weeded
1825 * out when it should. And if we don't make some extra provision for
1826 * it like the code just below, it doesn't get added when it should.
1827 * This solution is to add it only when AND'ing, which is here, and
1828 * only when what is being AND'ed is the pristine, original node
1829 * matching anything. Thus it is like adding it to ssc_anything() but
1830 * only when the result is to be AND'ed. Probably the same solution
1831 * could be adopted for the same problem we have with /l matching,
1832 * which is solved differently in S_ssc_init(), and that would lead to
1833 * fewer false positives than that solution has. But if this solution
1834 * creates bugs, the consequences are only that a warning isn't raised
1835 * that should be; while the consequences for having /l bugs is
1836 * incorrect matches */
1837 if (ssc_is_anything((regnode_ssc *)and_with)) {
1838 anded_flags |= ANYOF_SHARED_d_MATCHES_ALL_NON_UTF8_NON_ASCII_non_d_WARN_SUPER;
1842 anded_cp_list = get_ANYOF_cp_list_for_ssc(pRExC_state, and_with);
1843 if (OP(and_with) == ANYOFD) {
1844 anded_flags = and_with_flags & ANYOF_COMMON_FLAGS;
1847 anded_flags = and_with_flags
1848 &( ANYOF_COMMON_FLAGS
1849 |ANYOF_SHARED_d_MATCHES_ALL_NON_UTF8_NON_ASCII_non_d_WARN_SUPER
1850 |ANYOF_SHARED_d_UPPER_LATIN1_UTF8_STRING_MATCHES_non_d_RUNTIME_USER_PROP);
1851 if (ANYOFL_UTF8_LOCALE_REQD(and_with_flags)) {
1853 ANYOFL_SHARED_UTF8_LOCALE_fold_HAS_MATCHES_nonfold_REQD;
1858 ANYOF_FLAGS(ssc) &= anded_flags;
1860 /* Below, C1 is the list of code points in 'ssc'; P1, its posix classes.
1861 * C2 is the list of code points in 'and-with'; P2, its posix classes.
1862 * 'and_with' may be inverted. When not inverted, we have the situation of
1864 * (C1 | P1) & (C2 | P2)
1865 * = (C1 & (C2 | P2)) | (P1 & (C2 | P2))
1866 * = ((C1 & C2) | (C1 & P2)) | ((P1 & C2) | (P1 & P2))
1867 * <= ((C1 & C2) | P2)) | ( P1 | (P1 & P2))
1868 * <= ((C1 & C2) | P1 | P2)
1869 * Alternatively, the last few steps could be:
1870 * = ((C1 & C2) | (C1 & P2)) | ((P1 & C2) | (P1 & P2))
1871 * <= ((C1 & C2) | C1 ) | ( C2 | (P1 & P2))
1872 * <= (C1 | C2 | (P1 & P2))
1873 * We favor the second approach if either P1 or P2 is non-empty. This is
1874 * because these components are a barrier to doing optimizations, as what
1875 * they match cannot be known until the moment of matching as they are
1876 * dependent on the current locale, 'AND"ing them likely will reduce or
1878 * But we can do better if we know that C1,P1 are in their initial state (a
1879 * frequent occurrence), each matching everything:
1880 * (<everything>) & (C2 | P2) = C2 | P2
1881 * Similarly, if C2,P2 are in their initial state (again a frequent
1882 * occurrence), the result is a no-op
1883 * (C1 | P1) & (<everything>) = C1 | P1
1886 * (C1 | P1) & ~(C2 | P2) = (C1 | P1) & (~C2 & ~P2)
1887 * = (C1 & (~C2 & ~P2)) | (P1 & (~C2 & ~P2))
1888 * <= (C1 & ~C2) | (P1 & ~P2)
1891 if ((and_with_flags & ANYOF_INVERT)
1892 && ! is_ANYOF_SYNTHETIC(and_with))
1896 ssc_intersection(ssc,
1898 FALSE /* Has already been inverted */
1901 /* If either P1 or P2 is empty, the intersection will be also; can skip
1903 if (! (and_with_flags & ANYOF_MATCHES_POSIXL)) {
1904 ANYOF_POSIXL_ZERO(ssc);
1906 else if (ANYOF_POSIXL_SSC_TEST_ANY_SET(ssc)) {
1908 /* Note that the Posix class component P from 'and_with' actually
1910 * P = Pa | Pb | ... | Pn
1911 * where each component is one posix class, such as in [\w\s].
1913 * ~P = ~(Pa | Pb | ... | Pn)
1914 * = ~Pa & ~Pb & ... & ~Pn
1915 * <= ~Pa | ~Pb | ... | ~Pn
1916 * The last is something we can easily calculate, but unfortunately
1917 * is likely to have many false positives. We could do better
1918 * in some (but certainly not all) instances if two classes in
1919 * P have known relationships. For example
1920 * :lower: <= :alpha: <= :alnum: <= \w <= :graph: <= :print:
1922 * :lower: & :print: = :lower:
1923 * And similarly for classes that must be disjoint. For example,
1924 * since \s and \w can have no elements in common based on rules in
1925 * the POSIX standard,
1926 * \w & ^\S = nothing
1927 * Unfortunately, some vendor locales do not meet the Posix
1928 * standard, in particular almost everything by Microsoft.
1929 * The loop below just changes e.g., \w into \W and vice versa */
1931 regnode_charclass_posixl temp;
1932 int add = 1; /* To calculate the index of the complement */
1934 Zero(&temp, 1, regnode_charclass_posixl);
1935 ANYOF_POSIXL_ZERO(&temp);
1936 for (i = 0; i < ANYOF_MAX; i++) {
1938 || ! ANYOF_POSIXL_TEST((regnode_charclass_posixl*) and_with, i)
1939 || ! ANYOF_POSIXL_TEST((regnode_charclass_posixl*) and_with, i + 1));
1941 if (ANYOF_POSIXL_TEST((regnode_charclass_posixl*) and_with, i)) {
1942 ANYOF_POSIXL_SET(&temp, i + add);
1944 add = 0 - add; /* 1 goes to -1; -1 goes to 1 */
1946 ANYOF_POSIXL_AND(&temp, ssc);
1948 } /* else ssc already has no posixes */
1949 } /* else: Not inverted. This routine is a no-op if 'and_with' is an SSC
1950 in its initial state */
1951 else if (! is_ANYOF_SYNTHETIC(and_with)
1952 || ! ssc_is_cp_posixl_init(pRExC_state, (regnode_ssc *)and_with))
1954 /* But if 'ssc' is in its initial state, the result is just 'and_with';
1955 * copy it over 'ssc' */
1956 if (ssc_is_cp_posixl_init(pRExC_state, ssc)) {
1957 if (is_ANYOF_SYNTHETIC(and_with)) {
1958 StructCopy(and_with, ssc, regnode_ssc);
1961 ssc->invlist = anded_cp_list;
1962 ANYOF_POSIXL_ZERO(ssc);
1963 if (and_with_flags & ANYOF_MATCHES_POSIXL) {
1964 ANYOF_POSIXL_OR((regnode_charclass_posixl*) and_with, ssc);
1968 else if (ANYOF_POSIXL_SSC_TEST_ANY_SET(ssc)
1969 || (and_with_flags & ANYOF_MATCHES_POSIXL))
1971 /* One or the other of P1, P2 is non-empty. */
1972 if (and_with_flags & ANYOF_MATCHES_POSIXL) {
1973 ANYOF_POSIXL_AND((regnode_charclass_posixl*) and_with, ssc);
1975 ssc_union(ssc, anded_cp_list, FALSE);
1977 else { /* P1 = P2 = empty */
1978 ssc_intersection(ssc, anded_cp_list, FALSE);
1984 S_ssc_or(pTHX_ const RExC_state_t *pRExC_state, regnode_ssc *ssc,
1985 const regnode_charclass *or_with)
1987 /* Accumulate into SSC 'ssc' its 'OR' with 'or_with', which is either
1988 * another SSC or a regular ANYOF class. Can create false positives if
1989 * 'or_with' is to be inverted. */
1993 U8 or_with_flags = inRANGE(OP(or_with), ANYOFH, ANYOFRb)
1995 : ANYOF_FLAGS(or_with);
1997 PERL_ARGS_ASSERT_SSC_OR;
1999 assert(is_ANYOF_SYNTHETIC(ssc));
2001 /* 'or_with' is used as-is if it too is an SSC; otherwise have to extract
2002 * the code point inversion list and just the relevant flags */
2003 if (is_ANYOF_SYNTHETIC(or_with)) {
2004 ored_cp_list = ((regnode_ssc*) or_with)->invlist;
2005 ored_flags = or_with_flags;
2008 ored_cp_list = get_ANYOF_cp_list_for_ssc(pRExC_state, or_with);
2009 ored_flags = or_with_flags & ANYOF_COMMON_FLAGS;
2010 if (OP(or_with) != ANYOFD) {
2013 & ( ANYOF_SHARED_d_MATCHES_ALL_NON_UTF8_NON_ASCII_non_d_WARN_SUPER
2014 |ANYOF_SHARED_d_UPPER_LATIN1_UTF8_STRING_MATCHES_non_d_RUNTIME_USER_PROP);
2015 if (ANYOFL_UTF8_LOCALE_REQD(or_with_flags)) {
2017 ANYOFL_SHARED_UTF8_LOCALE_fold_HAS_MATCHES_nonfold_REQD;
2022 ANYOF_FLAGS(ssc) |= ored_flags;
2024 /* Below, C1 is the list of code points in 'ssc'; P1, its posix classes.
2025 * C2 is the list of code points in 'or-with'; P2, its posix classes.
2026 * 'or_with' may be inverted. When not inverted, we have the simple
2027 * situation of computing:
2028 * (C1 | P1) | (C2 | P2) = (C1 | C2) | (P1 | P2)
2029 * If P1|P2 yields a situation with both a class and its complement are
2030 * set, like having both \w and \W, this matches all code points, and we
2031 * can delete these from the P component of the ssc going forward. XXX We
2032 * might be able to delete all the P components, but I (khw) am not certain
2033 * about this, and it is better to be safe.
2036 * (C1 | P1) | ~(C2 | P2) = (C1 | P1) | (~C2 & ~P2)
2037 * <= (C1 | P1) | ~C2
2038 * <= (C1 | ~C2) | P1
2039 * (which results in actually simpler code than the non-inverted case)
2042 if ((or_with_flags & ANYOF_INVERT)
2043 && ! is_ANYOF_SYNTHETIC(or_with))
2045 /* We ignore P2, leaving P1 going forward */
2046 } /* else Not inverted */
2047 else if (or_with_flags & ANYOF_MATCHES_POSIXL) {
2048 ANYOF_POSIXL_OR((regnode_charclass_posixl*)or_with, ssc);
2049 if (ANYOF_POSIXL_SSC_TEST_ANY_SET(ssc)) {
2051 for (i = 0; i < ANYOF_MAX; i += 2) {
2052 if (ANYOF_POSIXL_TEST(ssc, i) && ANYOF_POSIXL_TEST(ssc, i + 1))
2054 ssc_match_all_cp(ssc);
2055 ANYOF_POSIXL_CLEAR(ssc, i);
2056 ANYOF_POSIXL_CLEAR(ssc, i+1);
2064 FALSE /* Already has been inverted */
2069 S_ssc_union(pTHX_ regnode_ssc *ssc, SV* const invlist, const bool invert2nd)
2071 PERL_ARGS_ASSERT_SSC_UNION;
2073 assert(is_ANYOF_SYNTHETIC(ssc));
2075 _invlist_union_maybe_complement_2nd(ssc->invlist,
2082 S_ssc_intersection(pTHX_ regnode_ssc *ssc,
2084 const bool invert2nd)
2086 PERL_ARGS_ASSERT_SSC_INTERSECTION;
2088 assert(is_ANYOF_SYNTHETIC(ssc));
2090 _invlist_intersection_maybe_complement_2nd(ssc->invlist,
2097 S_ssc_add_range(pTHX_ regnode_ssc *ssc, const UV start, const UV end)
2099 PERL_ARGS_ASSERT_SSC_ADD_RANGE;
2101 assert(is_ANYOF_SYNTHETIC(ssc));
2103 ssc->invlist = _add_range_to_invlist(ssc->invlist, start, end);
2107 S_ssc_cp_and(pTHX_ regnode_ssc *ssc, const UV cp)
2109 /* AND just the single code point 'cp' into the SSC 'ssc' */
2111 SV* cp_list = _new_invlist(2);
2113 PERL_ARGS_ASSERT_SSC_CP_AND;
2115 assert(is_ANYOF_SYNTHETIC(ssc));
2117 cp_list = add_cp_to_invlist(cp_list, cp);
2118 ssc_intersection(ssc, cp_list,
2119 FALSE /* Not inverted */
2121 SvREFCNT_dec_NN(cp_list);
2125 S_ssc_clear_locale(regnode_ssc *ssc)
2127 /* Set the SSC 'ssc' to not match any locale things */
2128 PERL_ARGS_ASSERT_SSC_CLEAR_LOCALE;
2130 assert(is_ANYOF_SYNTHETIC(ssc));
2132 ANYOF_POSIXL_ZERO(ssc);
2133 ANYOF_FLAGS(ssc) &= ~ANYOF_LOCALE_FLAGS;
2136 #define NON_OTHER_COUNT NON_OTHER_COUNT_FOR_USE_ONLY_BY_REGCOMP_DOT_C
2139 S_is_ssc_worth_it(const RExC_state_t * pRExC_state, const regnode_ssc * ssc)
2141 /* The synthetic start class is used to hopefully quickly winnow down
2142 * places where a pattern could start a match in the target string. If it
2143 * doesn't really narrow things down that much, there isn't much point to
2144 * having the overhead of using it. This function uses some very crude
2145 * heuristics to decide if to use the ssc or not.
2147 * It returns TRUE if 'ssc' rules out more than half what it considers to
2148 * be the "likely" possible matches, but of course it doesn't know what the
2149 * actual things being matched are going to be; these are only guesses
2151 * For /l matches, it assumes that the only likely matches are going to be
2152 * in the 0-255 range, uniformly distributed, so half of that is 127
2153 * For /a and /d matches, it assumes that the likely matches will be just
2154 * the ASCII range, so half of that is 63
2155 * For /u and there isn't anything matching above the Latin1 range, it
2156 * assumes that that is the only range likely to be matched, and uses
2157 * half that as the cut-off: 127. If anything matches above Latin1,
2158 * it assumes that all of Unicode could match (uniformly), except for
2159 * non-Unicode code points and things in the General Category "Other"
2160 * (unassigned, private use, surrogates, controls and formats). This
2161 * is a much large number. */
2163 U32 count = 0; /* Running total of number of code points matched by
2165 UV start, end; /* Start and end points of current range in inversion
2166 XXX outdated. UTF-8 locales are common, what about invert? list */
2167 const U32 max_code_points = (LOC)
2169 : (( ! UNI_SEMANTICS
2170 || invlist_highest(ssc->invlist) < 256)
2173 const U32 max_match = max_code_points / 2;
2175 PERL_ARGS_ASSERT_IS_SSC_WORTH_IT;
2177 invlist_iterinit(ssc->invlist);
2178 while (invlist_iternext(ssc->invlist, &start, &end)) {
2179 if (start >= max_code_points) {
2182 end = MIN(end, max_code_points - 1);
2183 count += end - start + 1;
2184 if (count >= max_match) {
2185 invlist_iterfinish(ssc->invlist);
2195 S_ssc_finalize(pTHX_ RExC_state_t *pRExC_state, regnode_ssc *ssc)
2197 /* The inversion list in the SSC is marked mortal; now we need a more
2198 * permanent copy, which is stored the same way that is done in a regular
2199 * ANYOF node, with the first NUM_ANYOF_CODE_POINTS code points in a bit
2202 SV* invlist = invlist_clone(ssc->invlist, NULL);
2204 PERL_ARGS_ASSERT_SSC_FINALIZE;
2206 assert(is_ANYOF_SYNTHETIC(ssc));
2208 /* The code in this file assumes that all but these flags aren't relevant
2209 * to the SSC, except SSC_MATCHES_EMPTY_STRING, which should be cleared
2210 * by the time we reach here */
2211 assert(! (ANYOF_FLAGS(ssc)
2212 & ~( ANYOF_COMMON_FLAGS
2213 |ANYOF_SHARED_d_MATCHES_ALL_NON_UTF8_NON_ASCII_non_d_WARN_SUPER
2214 |ANYOF_SHARED_d_UPPER_LATIN1_UTF8_STRING_MATCHES_non_d_RUNTIME_USER_PROP)));
2216 populate_ANYOF_from_invlist( (regnode *) ssc, &invlist);
2218 set_ANYOF_arg(pRExC_state, (regnode *) ssc, invlist, NULL, NULL);
2219 SvREFCNT_dec(invlist);
2221 /* Make sure is clone-safe */
2222 ssc->invlist = NULL;
2224 if (ANYOF_POSIXL_SSC_TEST_ANY_SET(ssc)) {
2225 ANYOF_FLAGS(ssc) |= ANYOF_MATCHES_POSIXL;
2226 OP(ssc) = ANYOFPOSIXL;
2228 else if (RExC_contains_locale) {
2232 assert(! (ANYOF_FLAGS(ssc) & ANYOF_LOCALE_FLAGS) || RExC_contains_locale);
2235 #define TRIE_LIST_ITEM(state,idx) (trie->states[state].trans.list)[ idx ]
2236 #define TRIE_LIST_CUR(state) ( TRIE_LIST_ITEM( state, 0 ).forid )
2237 #define TRIE_LIST_LEN(state) ( TRIE_LIST_ITEM( state, 0 ).newstate )
2238 #define TRIE_LIST_USED(idx) ( trie->states[state].trans.list \
2239 ? (TRIE_LIST_CUR( idx ) - 1) \
2245 dump_trie(trie,widecharmap,revcharmap)
2246 dump_trie_interim_list(trie,widecharmap,revcharmap,next_alloc)
2247 dump_trie_interim_table(trie,widecharmap,revcharmap,next_alloc)
2249 These routines dump out a trie in a somewhat readable format.
2250 The _interim_ variants are used for debugging the interim
2251 tables that are used to generate the final compressed
2252 representation which is what dump_trie expects.
2254 Part of the reason for their existence is to provide a form
2255 of documentation as to how the different representations function.
2260 Dumps the final compressed table form of the trie to Perl_debug_log.
2261 Used for debugging make_trie().
2265 S_dump_trie(pTHX_ const struct _reg_trie_data *trie, HV *widecharmap,
2266 AV *revcharmap, U32 depth)
2269 SV *sv=sv_newmortal();
2270 int colwidth= widecharmap ? 6 : 4;
2272 DECLARE_AND_GET_RE_DEBUG_FLAGS;
2274 PERL_ARGS_ASSERT_DUMP_TRIE;
2276 Perl_re_indentf( aTHX_ "Char : %-6s%-6s%-4s ",
2277 depth+1, "Match","Base","Ofs" );
2279 for( state = 0 ; state < trie->uniquecharcount ; state++ ) {
2280 SV ** const tmp = av_fetch( revcharmap, state, 0);
2282 Perl_re_printf( aTHX_ "%*s",
2284 pv_pretty(sv, SvPV_nolen_const(*tmp), SvCUR(*tmp), colwidth,
2285 PL_colors[0], PL_colors[1],
2286 (SvUTF8(*tmp) ? PERL_PV_ESCAPE_UNI : 0) |
2287 PERL_PV_ESCAPE_FIRSTCHAR
2292 Perl_re_printf( aTHX_ "\n");
2293 Perl_re_indentf( aTHX_ "State|-----------------------", depth+1);
2295 for( state = 0 ; state < trie->uniquecharcount ; state++ )
2296 Perl_re_printf( aTHX_ "%.*s", colwidth, "--------");
2297 Perl_re_printf( aTHX_ "\n");
2299 for( state = 1 ; state < trie->statecount ; state++ ) {
2300 const U32 base = trie->states[ state ].trans.base;
2302 Perl_re_indentf( aTHX_ "#%4" UVXf "|", depth+1, (UV)state);
2304 if ( trie->states[ state ].wordnum ) {
2305 Perl_re_printf( aTHX_ " W%4X", trie->states[ state ].wordnum );
2307 Perl_re_printf( aTHX_ "%6s", "" );
2310 Perl_re_printf( aTHX_ " @%4" UVXf " ", (UV)base );
2315 while( ( base + ofs < trie->uniquecharcount ) ||
2316 ( base + ofs - trie->uniquecharcount < trie->lasttrans
2317 && trie->trans[ base + ofs - trie->uniquecharcount ].check
2321 Perl_re_printf( aTHX_ "+%2" UVXf "[ ", (UV)ofs);
2323 for ( ofs = 0 ; ofs < trie->uniquecharcount ; ofs++ ) {
2324 if ( ( base + ofs >= trie->uniquecharcount )
2325 && ( base + ofs - trie->uniquecharcount
2327 && trie->trans[ base + ofs
2328 - trie->uniquecharcount ].check == state )
2330 Perl_re_printf( aTHX_ "%*" UVXf, colwidth,
2331 (UV)trie->trans[ base + ofs - trie->uniquecharcount ].next
2334 Perl_re_printf( aTHX_ "%*s", colwidth," ." );
2338 Perl_re_printf( aTHX_ "]");
2341 Perl_re_printf( aTHX_ "\n" );
2343 Perl_re_indentf( aTHX_ "word_info N:(prev,len)=",
2345 for (word=1; word <= trie->wordcount; word++) {
2346 Perl_re_printf( aTHX_ " %d:(%d,%d)",
2347 (int)word, (int)(trie->wordinfo[word].prev),
2348 (int)(trie->wordinfo[word].len));
2350 Perl_re_printf( aTHX_ "\n" );
2353 Dumps a fully constructed but uncompressed trie in list form.
2354 List tries normally only are used for construction when the number of
2355 possible chars (trie->uniquecharcount) is very high.
2356 Used for debugging make_trie().
2359 S_dump_trie_interim_list(pTHX_ const struct _reg_trie_data *trie,
2360 HV *widecharmap, AV *revcharmap, U32 next_alloc,
2364 SV *sv=sv_newmortal();
2365 int colwidth= widecharmap ? 6 : 4;
2366 DECLARE_AND_GET_RE_DEBUG_FLAGS;
2368 PERL_ARGS_ASSERT_DUMP_TRIE_INTERIM_LIST;
2370 /* print out the table precompression. */
2371 Perl_re_indentf( aTHX_ "State :Word | Transition Data\n",
2373 Perl_re_indentf( aTHX_ "%s",
2374 depth+1, "------:-----+-----------------\n" );
2376 for( state=1 ; state < next_alloc ; state ++ ) {
2379 Perl_re_indentf( aTHX_ " %4" UVXf " :",
2380 depth+1, (UV)state );
2381 if ( ! trie->states[ state ].wordnum ) {
2382 Perl_re_printf( aTHX_ "%5s| ","");
2384 Perl_re_printf( aTHX_ "W%4x| ",
2385 trie->states[ state ].wordnum
2388 for( charid = 1 ; charid <= TRIE_LIST_USED( state ) ; charid++ ) {
2389 SV ** const tmp = av_fetch( revcharmap,
2390 TRIE_LIST_ITEM(state, charid).forid, 0);
2392 Perl_re_printf( aTHX_ "%*s:%3X=%4" UVXf " | ",
2394 pv_pretty(sv, SvPV_nolen_const(*tmp), SvCUR(*tmp),
2396 PL_colors[0], PL_colors[1],
2397 (SvUTF8(*tmp) ? PERL_PV_ESCAPE_UNI : 0)
2398 | PERL_PV_ESCAPE_FIRSTCHAR
2400 TRIE_LIST_ITEM(state, charid).forid,
2401 (UV)TRIE_LIST_ITEM(state, charid).newstate
2404 Perl_re_printf( aTHX_ "\n%*s| ",
2405 (int)((depth * 2) + 14), "");
2408 Perl_re_printf( aTHX_ "\n");
2413 Dumps a fully constructed but uncompressed trie in table form.
2414 This is the normal DFA style state transition table, with a few
2415 twists to facilitate compression later.
2416 Used for debugging make_trie().
2419 S_dump_trie_interim_table(pTHX_ const struct _reg_trie_data *trie,
2420 HV *widecharmap, AV *revcharmap, U32 next_alloc,
2425 SV *sv=sv_newmortal();
2426 int colwidth= widecharmap ? 6 : 4;
2427 DECLARE_AND_GET_RE_DEBUG_FLAGS;
2429 PERL_ARGS_ASSERT_DUMP_TRIE_INTERIM_TABLE;
2432 print out the table precompression so that we can do a visual check
2433 that they are identical.
2436 Perl_re_indentf( aTHX_ "Char : ", depth+1 );
2438 for( charid = 0 ; charid < trie->uniquecharcount ; charid++ ) {
2439 SV ** const tmp = av_fetch( revcharmap, charid, 0);
2441 Perl_re_printf( aTHX_ "%*s",
2443 pv_pretty(sv, SvPV_nolen_const(*tmp), SvCUR(*tmp), colwidth,
2444 PL_colors[0], PL_colors[1],
2445 (SvUTF8(*tmp) ? PERL_PV_ESCAPE_UNI : 0) |
2446 PERL_PV_ESCAPE_FIRSTCHAR
2452 Perl_re_printf( aTHX_ "\n");
2453 Perl_re_indentf( aTHX_ "State+-", depth+1 );
2455 for( charid=0 ; charid < trie->uniquecharcount ; charid++ ) {
2456 Perl_re_printf( aTHX_ "%.*s", colwidth,"--------");
2459 Perl_re_printf( aTHX_ "\n" );
2461 for( state=1 ; state < next_alloc ; state += trie->uniquecharcount ) {
2463 Perl_re_indentf( aTHX_ "%4" UVXf " : ",
2465 (UV)TRIE_NODENUM( state ) );
2467 for( charid = 0 ; charid < trie->uniquecharcount ; charid++ ) {
2468 UV v=(UV)SAFE_TRIE_NODENUM( trie->trans[ state + charid ].next );
2470 Perl_re_printf( aTHX_ "%*" UVXf, colwidth, v );
2472 Perl_re_printf( aTHX_ "%*s", colwidth, "." );
2474 if ( ! trie->states[ TRIE_NODENUM( state ) ].wordnum ) {
2475 Perl_re_printf( aTHX_ " (%4" UVXf ")\n",
2476 (UV)trie->trans[ state ].check );
2478 Perl_re_printf( aTHX_ " (%4" UVXf ") W%4X\n",
2479 (UV)trie->trans[ state ].check,
2480 trie->states[ TRIE_NODENUM( state ) ].wordnum );
2488 /* make_trie(startbranch,first,last,tail,word_count,flags,depth)
2489 startbranch: the first branch in the whole branch sequence
2490 first : start branch of sequence of branch-exact nodes.
2491 May be the same as startbranch
2492 last : Thing following the last branch.
2493 May be the same as tail.
2494 tail : item following the branch sequence
2495 count : words in the sequence
2496 flags : currently the OP() type we will be building one of /EXACT(|F|FA|FU|FU_SS|L|FLU8)/
2497 depth : indent depth
2499 Inplace optimizes a sequence of 2 or more Branch-Exact nodes into a TRIE node.
2501 A trie is an N'ary tree where the branches are determined by digital
2502 decomposition of the key. IE, at the root node you look up the 1st character and
2503 follow that branch repeat until you find the end of the branches. Nodes can be
2504 marked as "accepting" meaning they represent a complete word. Eg:
2508 would convert into the following structure. Numbers represent states, letters
2509 following numbers represent valid transitions on the letter from that state, if
2510 the number is in square brackets it represents an accepting state, otherwise it
2511 will be in parenthesis.
2513 +-h->+-e->[3]-+-r->(8)-+-s->[9]
2517 (1) +-i->(6)-+-s->[7]
2519 +-s->(3)-+-h->(4)-+-e->[5]
2521 Accept Word Mapping: 3=>1 (he),5=>2 (she), 7=>3 (his), 9=>4 (hers)
2523 This shows that when matching against the string 'hers' we will begin at state 1
2524 read 'h' and move to state 2, read 'e' and move to state 3 which is accepting,
2525 then read 'r' and go to state 8 followed by 's' which takes us to state 9 which
2526 is also accepting. Thus we know that we can match both 'he' and 'hers' with a
2527 single traverse. We store a mapping from accepting to state to which word was
2528 matched, and then when we have multiple possibilities we try to complete the
2529 rest of the regex in the order in which they occurred in the alternation.
2531 The only prior NFA like behaviour that would be changed by the TRIE support is
2532 the silent ignoring of duplicate alternations which are of the form:
2534 / (DUPE|DUPE) X? (?{ ... }) Y /x
2536 Thus EVAL blocks following a trie may be called a different number of times with
2537 and without the optimisation. With the optimisations dupes will be silently
2538 ignored. This inconsistent behaviour of EVAL type nodes is well established as
2539 the following demonstrates:
2541 'words'=~/(word|word|word)(?{ print $1 })[xyz]/
2543 which prints out 'word' three times, but
2545 'words'=~/(word|word|word)(?{ print $1 })S/
2547 which doesnt print it out at all. This is due to other optimisations kicking in.
2549 Example of what happens on a structural level:
2551 The regexp /(ac|ad|ab)+/ will produce the following debug output:
2553 1: CURLYM[1] {1,32767}(18)
2564 This would be optimizable with startbranch=5, first=5, last=16, tail=16
2565 and should turn into:
2567 1: CURLYM[1] {1,32767}(18)
2569 [Words:3 Chars Stored:6 Unique Chars:4 States:5 NCP:1]
2577 Cases where tail != last would be like /(?foo|bar)baz/:
2587 which would be optimizable with startbranch=1, first=1, last=7, tail=8
2588 and would end up looking like:
2591 [Words:2 Chars Stored:6 Unique Chars:5 States:7 NCP:1]
2598 d = uvchr_to_utf8_flags(d, uv, 0);
2600 is the recommended Unicode-aware way of saying
2605 #define TRIE_STORE_REVCHAR(val) \
2608 SV *zlopp = newSV(UTF8_MAXBYTES); \
2609 unsigned char *flrbbbbb = (unsigned char *) SvPVX(zlopp); \
2610 unsigned char *const kapow = uvchr_to_utf8(flrbbbbb, val); \
2612 SvCUR_set(zlopp, kapow - flrbbbbb); \
2615 av_push(revcharmap, zlopp); \
2617 char ooooff = (char)val; \
2618 av_push(revcharmap, newSVpvn(&ooooff, 1)); \
2622 /* This gets the next character from the input, folding it if not already
2624 #define TRIE_READ_CHAR STMT_START { \
2627 /* if it is UTF then it is either already folded, or does not need \
2629 uvc = valid_utf8_to_uvchr( (const U8*) uc, &len); \
2631 else if (folder == PL_fold_latin1) { \
2632 /* This folder implies Unicode rules, which in the range expressible \
2633 * by not UTF is the lower case, with the two exceptions, one of \
2634 * which should have been taken care of before calling this */ \
2635 assert(*uc != LATIN_SMALL_LETTER_SHARP_S); \
2636 uvc = toLOWER_L1(*uc); \
2637 if (UNLIKELY(uvc == MICRO_SIGN)) uvc = GREEK_SMALL_LETTER_MU; \
2640 /* raw data, will be folded later if needed */ \
2648 #define TRIE_LIST_PUSH(state,fid,ns) STMT_START { \
2649 if ( TRIE_LIST_CUR( state ) >=TRIE_LIST_LEN( state ) ) { \
2650 U32 ging = TRIE_LIST_LEN( state ) * 2; \
2651 Renew( trie->states[ state ].trans.list, ging, reg_trie_trans_le ); \
2652 TRIE_LIST_LEN( state ) = ging; \
2654 TRIE_LIST_ITEM( state, TRIE_LIST_CUR( state ) ).forid = fid; \
2655 TRIE_LIST_ITEM( state, TRIE_LIST_CUR( state ) ).newstate = ns; \
2656 TRIE_LIST_CUR( state )++; \
2659 #define TRIE_LIST_NEW(state) STMT_START { \
2660 Newx( trie->states[ state ].trans.list, \
2661 4, reg_trie_trans_le ); \
2662 TRIE_LIST_CUR( state ) = 1; \
2663 TRIE_LIST_LEN( state ) = 4; \
2666 #define TRIE_HANDLE_WORD(state) STMT_START { \
2667 U16 dupe= trie->states[ state ].wordnum; \
2668 regnode * const noper_next = regnext( noper ); \
2671 /* store the word for dumping */ \
2673 if (OP(noper) != NOTHING) \
2674 tmp = newSVpvn_utf8(STRING(noper), STR_LEN(noper), UTF); \
2676 tmp = newSVpvn_utf8( "", 0, UTF ); \
2677 av_push( trie_words, tmp ); \
2681 trie->wordinfo[curword].prev = 0; \
2682 trie->wordinfo[curword].len = wordlen; \
2683 trie->wordinfo[curword].accept = state; \
2685 if ( noper_next < tail ) { \
2687 trie->jump = (U16 *) PerlMemShared_calloc( word_count + 1, \
2689 trie->jump[curword] = (U16)(noper_next - convert); \
2691 jumper = noper_next; \
2693 nextbranch= regnext(cur); \
2697 /* It's a dupe. Pre-insert into the wordinfo[].prev */\
2698 /* chain, so that when the bits of chain are later */\
2699 /* linked together, the dups appear in the chain */\
2700 trie->wordinfo[curword].prev = trie->wordinfo[dupe].prev; \
2701 trie->wordinfo[dupe].prev = curword; \
2703 /* we haven't inserted this word yet. */ \
2704 trie->states[ state ].wordnum = curword; \
2709 #define TRIE_TRANS_STATE(state,base,ucharcount,charid,special) \
2710 ( ( base + charid >= ucharcount \
2711 && base + charid < ubound \
2712 && state == trie->trans[ base - ucharcount + charid ].check \
2713 && trie->trans[ base - ucharcount + charid ].next ) \
2714 ? trie->trans[ base - ucharcount + charid ].next \
2715 : ( state==1 ? special : 0 ) \
2718 #define TRIE_BITMAP_SET_FOLDED(trie, uvc, folder) \
2720 TRIE_BITMAP_SET(trie, uvc); \
2721 /* store the folded codepoint */ \
2723 TRIE_BITMAP_SET(trie, folder[(U8) uvc ]); \
2726 /* store first byte of utf8 representation of */ \
2727 /* variant codepoints */ \
2728 if (! UVCHR_IS_INVARIANT(uvc)) { \
2729 TRIE_BITMAP_SET(trie, UTF8_TWO_BYTE_HI(uvc)); \
2734 #define MADE_JUMP_TRIE 2
2735 #define MADE_EXACT_TRIE 4
2738 S_make_trie(pTHX_ RExC_state_t *pRExC_state, regnode *startbranch,
2739 regnode *first, regnode *last, regnode *tail,
2740 U32 word_count, U32 flags, U32 depth)
2742 /* first pass, loop through and scan words */
2743 reg_trie_data *trie;
2744 HV *widecharmap = NULL;
2745 AV *revcharmap = newAV();
2751 regnode *jumper = NULL;
2752 regnode *nextbranch = NULL;
2753 regnode *convert = NULL;
2754 U32 *prev_states; /* temp array mapping each state to previous one */
2755 /* we just use folder as a flag in utf8 */
2756 const U8 * folder = NULL;
2758 /* in the below add_data call we are storing either 'tu' or 'tuaa'
2759 * which stands for one trie structure, one hash, optionally followed
2762 const U32 data_slot = add_data( pRExC_state, STR_WITH_LEN("tuaa"));
2763 AV *trie_words = NULL;
2764 /* along with revcharmap, this only used during construction but both are
2765 * useful during debugging so we store them in the struct when debugging.
2768 const U32 data_slot = add_data( pRExC_state, STR_WITH_LEN("tu"));
2769 STRLEN trie_charcount=0;
2771 SV *re_trie_maxbuff;
2772 DECLARE_AND_GET_RE_DEBUG_FLAGS;
2774 PERL_ARGS_ASSERT_MAKE_TRIE;
2776 PERL_UNUSED_ARG(depth);
2780 case EXACT: case EXACT_REQ8: case EXACTL: break;
2784 case EXACTFLU8: folder = PL_fold_latin1; break;
2785 case EXACTF: folder = PL_fold; break;
2786 default: Perl_croak( aTHX_ "panic! In trie construction, unknown node type %u %s", (unsigned) flags, PL_reg_name[flags] );
2789 trie = (reg_trie_data *) PerlMemShared_calloc( 1, sizeof(reg_trie_data) );
2791 trie->startstate = 1;
2792 trie->wordcount = word_count;
2793 RExC_rxi->data->data[ data_slot ] = (void*)trie;
2794 trie->charmap = (U16 *) PerlMemShared_calloc( 256, sizeof(U16) );
2795 if (flags == EXACT || flags == EXACT_REQ8 || flags == EXACTL)
2796 trie->bitmap = (char *) PerlMemShared_calloc( ANYOF_BITMAP_SIZE, 1 );
2797 trie->wordinfo = (reg_trie_wordinfo *) PerlMemShared_calloc(
2798 trie->wordcount+1, sizeof(reg_trie_wordinfo));
2801 trie_words = newAV();
2804 re_trie_maxbuff = get_sv(RE_TRIE_MAXBUF_NAME, GV_ADD);
2805 assert(re_trie_maxbuff);
2806 if (!SvIOK(re_trie_maxbuff)) {
2807 sv_setiv(re_trie_maxbuff, RE_TRIE_MAXBUF_INIT);
2809 DEBUG_TRIE_COMPILE_r({
2810 Perl_re_indentf( aTHX_
2811 "make_trie start==%d, first==%d, last==%d, tail==%d depth=%d\n",
2813 REG_NODE_NUM(startbranch), REG_NODE_NUM(first),
2814 REG_NODE_NUM(last), REG_NODE_NUM(tail), (int)depth);
2817 /* Find the node we are going to overwrite */
2818 if ( first == startbranch && OP( last ) != BRANCH ) {
2819 /* whole branch chain */
2822 /* branch sub-chain */
2823 convert = NEXTOPER( first );
2826 /* -- First loop and Setup --
2828 We first traverse the branches and scan each word to determine if it
2829 contains widechars, and how many unique chars there are, this is
2830 important as we have to build a table with at least as many columns as we
2833 We use an array of integers to represent the character codes 0..255
2834 (trie->charmap) and we use a an HV* to store Unicode characters. We use
2835 the native representation of the character value as the key and IV's for
2838 *TODO* If we keep track of how many times each character is used we can
2839 remap the columns so that the table compression later on is more
2840 efficient in terms of memory by ensuring the most common value is in the
2841 middle and the least common are on the outside. IMO this would be better
2842 than a most to least common mapping as theres a decent chance the most
2843 common letter will share a node with the least common, meaning the node
2844 will not be compressible. With a middle is most common approach the worst
2845 case is when we have the least common nodes twice.
2849 for ( cur = first ; cur < last ; cur = regnext( cur ) ) {
2850 regnode *noper = NEXTOPER( cur );
2854 U32 wordlen = 0; /* required init */
2855 STRLEN minchars = 0;
2856 STRLEN maxchars = 0;
2857 bool set_bit = trie->bitmap ? 1 : 0; /*store the first char in the
2860 if (OP(noper) == NOTHING) {
2861 /* skip past a NOTHING at the start of an alternation
2862 * eg, /(?:)a|(?:b)/ should be the same as /a|b/
2864 * If the next node is not something we are supposed to process
2865 * we will just ignore it due to the condition guarding the
2869 regnode *noper_next= regnext(noper);
2870 if (noper_next < tail)
2875 && ( OP(noper) == flags
2876 || (flags == EXACT && OP(noper) == EXACT_REQ8)
2877 || (flags == EXACTFU && ( OP(noper) == EXACTFU_REQ8
2878 || OP(noper) == EXACTFUP))))
2880 uc= (U8*)STRING(noper);
2881 e= uc + STR_LEN(noper);
2888 if ( set_bit ) { /* bitmap only alloced when !(UTF&&Folding) */
2889 TRIE_BITMAP_SET(trie,*uc); /* store the raw first byte
2890 regardless of encoding */
2891 if (OP( noper ) == EXACTFUP) {
2892 /* false positives are ok, so just set this */
2893 TRIE_BITMAP_SET(trie, LATIN_SMALL_LETTER_SHARP_S);
2897 for ( ; uc < e ; uc += len ) { /* Look at each char in the current
2899 TRIE_CHARCOUNT(trie)++;
2902 /* TRIE_READ_CHAR returns the current character, or its fold if /i
2903 * is in effect. Under /i, this character can match itself, or
2904 * anything that folds to it. If not under /i, it can match just
2905 * itself. Most folds are 1-1, for example k, K, and KELVIN SIGN
2906 * all fold to k, and all are single characters. But some folds
2907 * expand to more than one character, so for example LATIN SMALL
2908 * LIGATURE FFI folds to the three character sequence 'ffi'. If
2909 * the string beginning at 'uc' is 'ffi', it could be matched by
2910 * three characters, or just by the one ligature character. (It
2911 * could also be matched by two characters: LATIN SMALL LIGATURE FF
2912 * followed by 'i', or by 'f' followed by LATIN SMALL LIGATURE FI).
2913 * (Of course 'I' and/or 'F' instead of 'i' and 'f' can also
2914 * match.) The trie needs to know the minimum and maximum number
2915 * of characters that could match so that it can use size alone to
2916 * quickly reject many match attempts. The max is simple: it is
2917 * the number of folded characters in this branch (since a fold is
2918 * never shorter than what folds to it. */
2922 /* And the min is equal to the max if not under /i (indicated by
2923 * 'folder' being NULL), or there are no multi-character folds. If
2924 * there is a multi-character fold, the min is incremented just
2925 * once, for the character that folds to the sequence. Each
2926 * character in the sequence needs to be added to the list below of
2927 * characters in the trie, but we count only the first towards the
2928 * min number of characters needed. This is done through the
2929 * variable 'foldlen', which is returned by the macros that look
2930 * for these sequences as the number of bytes the sequence
2931 * occupies. Each time through the loop, we decrement 'foldlen' by
2932 * how many bytes the current char occupies. Only when it reaches
2933 * 0 do we increment 'minchars' or look for another multi-character
2935 if (folder == NULL) {
2938 else if (foldlen > 0) {
2939 foldlen -= (UTF) ? UTF8SKIP(uc) : 1;
2944 /* See if *uc is the beginning of a multi-character fold. If
2945 * so, we decrement the length remaining to look at, to account
2946 * for the current character this iteration. (We can use 'uc'
2947 * instead of the fold returned by TRIE_READ_CHAR because the
2948 * macro is smart enough to account for any unfolded
2951 if ((foldlen = is_MULTI_CHAR_FOLD_utf8_safe(uc, e))) {
2952 foldlen -= UTF8SKIP(uc);
2955 else if ((foldlen = is_MULTI_CHAR_FOLD_latin1_safe(uc, e))) {
2960 /* The current character (and any potential folds) should be added
2961 * to the possible matching characters for this position in this
2965 U8 folded= folder[ (U8) uvc ];
2966 if ( !trie->charmap[ folded ] ) {
2967 trie->charmap[ folded ]=( ++trie->uniquecharcount );
2968 TRIE_STORE_REVCHAR( folded );
2971 if ( !trie->charmap[ uvc ] ) {
2972 trie->charmap[ uvc ]=( ++trie->uniquecharcount );
2973 TRIE_STORE_REVCHAR( uvc );
2976 /* store the codepoint in the bitmap, and its folded
2978 TRIE_BITMAP_SET_FOLDED(trie, uvc, folder);
2979 set_bit = 0; /* We've done our bit :-) */
2983 /* XXX We could come up with the list of code points that fold
2984 * to this using PL_utf8_foldclosures, except not for
2985 * multi-char folds, as there may be multiple combinations
2986 * there that could work, which needs to wait until runtime to
2987 * resolve (The comment about LIGATURE FFI above is such an
2992 widecharmap = newHV();
2994 svpp = hv_fetch( widecharmap, (char*)&uvc, sizeof( UV ), 1 );
2997 Perl_croak( aTHX_ "error creating/fetching widecharmap entry for 0x%" UVXf, uvc );
2999 if ( !SvTRUE( *svpp ) ) {
3000 sv_setiv( *svpp, ++trie->uniquecharcount );
3001 TRIE_STORE_REVCHAR(uvc);
3004 } /* end loop through characters in this branch of the trie */
3006 /* We take the min and max for this branch and combine to find the min
3007 * and max for all branches processed so far */
3008 if( cur == first ) {
3009 trie->minlen = minchars;
3010 trie->maxlen = maxchars;
3011 } else if (minchars < trie->minlen) {
3012 trie->minlen = minchars;
3013 } else if (maxchars > trie->maxlen) {
3014 trie->maxlen = maxchars;
3016 } /* end first pass */
3017 DEBUG_TRIE_COMPILE_r(
3018 Perl_re_indentf( aTHX_
3019 "TRIE(%s): W:%d C:%d Uq:%d Min:%d Max:%d\n",
3021 ( widecharmap ? "UTF8" : "NATIVE" ), (int)word_count,
3022 (int)TRIE_CHARCOUNT(trie), trie->uniquecharcount,
3023 (int)trie->minlen, (int)trie->maxlen )
3027 We now know what we are dealing with in terms of unique chars and
3028 string sizes so we can calculate how much memory a naive
3029 representation using a flat table will take. If it's over a reasonable
3030 limit (as specified by ${^RE_TRIE_MAXBUF}) we use a more memory
3031 conservative but potentially much slower representation using an array
3034 At the end we convert both representations into the same compressed
3035 form that will be used in regexec.c for matching with. The latter
3036 is a form that cannot be used to construct with but has memory
3037 properties similar to the list form and access properties similar
3038 to the table form making it both suitable for fast searches and
3039 small enough that its feasable to store for the duration of a program.
3041 See the comment in the code where the compressed table is produced
3042 inplace from the flat tabe representation for an explanation of how
3043 the compression works.
3048 Newx(prev_states, TRIE_CHARCOUNT(trie) + 2, U32);
3051 if ( (IV)( ( TRIE_CHARCOUNT(trie) + 1 ) * trie->uniquecharcount + 1)
3052 > SvIV(re_trie_maxbuff) )
3055 Second Pass -- Array Of Lists Representation
3057 Each state will be represented by a list of charid:state records
3058 (reg_trie_trans_le) the first such element holds the CUR and LEN
3059 points of the allocated array. (See defines above).
3061 We build the initial structure using the lists, and then convert
3062 it into the compressed table form which allows faster lookups
3063 (but cant be modified once converted).
3066 STRLEN transcount = 1;
3068 DEBUG_TRIE_COMPILE_MORE_r( Perl_re_indentf( aTHX_ "Compiling trie using list compiler\n",
3071 trie->states = (reg_trie_state *)
3072 PerlMemShared_calloc( TRIE_CHARCOUNT(trie) + 2,
3073 sizeof(reg_trie_state) );
3077 for ( cur = first ; cur < last ; cur = regnext( cur ) ) {
3079 regnode *noper = NEXTOPER( cur );
3080 U32 state = 1; /* required init */
3081 U16 charid = 0; /* sanity init */
3082 U32 wordlen = 0; /* required init */
3084 if (OP(noper) == NOTHING) {
3085 regnode *noper_next= regnext(noper);
3086 if (noper_next < tail)
3088 /* we will undo this assignment if noper does not
3089 * point at a trieable type in the else clause of
3090 * the following statement. */
3094 && ( OP(noper) == flags
3095 || (flags == EXACT && OP(noper) == EXACT_REQ8)
3096 || (flags == EXACTFU && ( OP(noper) == EXACTFU_REQ8
3097 || OP(noper) == EXACTFUP))))
3099 const U8 *uc= (U8*)STRING(noper);
3100 const U8 *e= uc + STR_LEN(noper);
3102 for ( ; uc < e ; uc += len ) {
3107 charid = trie->charmap[ uvc ];
3109 SV** const svpp = hv_fetch( widecharmap,
3116 charid=(U16)SvIV( *svpp );
3119 /* charid is now 0 if we dont know the char read, or
3120 * nonzero if we do */
3127 if ( !trie->states[ state ].trans.list ) {
3128 TRIE_LIST_NEW( state );
3131 check <= TRIE_LIST_USED( state );
3134 if ( TRIE_LIST_ITEM( state, check ).forid
3137 newstate = TRIE_LIST_ITEM( state, check ).newstate;
3142 newstate = next_alloc++;
3143 prev_states[newstate] = state;
3144 TRIE_LIST_PUSH( state, charid, newstate );
3149 Perl_croak( aTHX_ "panic! In trie construction, no char mapping for %" IVdf, uvc );
3153 /* If we end up here it is because we skipped past a NOTHING, but did not end up
3154 * on a trieable type. So we need to reset noper back to point at the first regop
3155 * in the branch before we call TRIE_HANDLE_WORD()
3157 noper= NEXTOPER(cur);
3159 TRIE_HANDLE_WORD(state);
3161 } /* end second pass */
3163 /* next alloc is the NEXT state to be allocated */
3164 trie->statecount = next_alloc;
3165 trie->states = (reg_trie_state *)
3166 PerlMemShared_realloc( trie->states,
3168 * sizeof(reg_trie_state) );
3170 /* and now dump it out before we compress it */
3171 DEBUG_TRIE_COMPILE_MORE_r(dump_trie_interim_list(trie, widecharmap,
3172 revcharmap, next_alloc,
3176 trie->trans = (reg_trie_trans *)
3177 PerlMemShared_calloc( transcount, sizeof(reg_trie_trans) );
3184 for( state=1 ; state < next_alloc ; state ++ ) {
3188 DEBUG_TRIE_COMPILE_MORE_r(
3189 Perl_re_printf( aTHX_ "tp: %d zp: %d ",tp,zp)
3193 if (trie->states[state].trans.list) {
3194 U16 minid=TRIE_LIST_ITEM( state, 1).forid;
3198 for( idx = 2 ; idx <= TRIE_LIST_USED( state ) ; idx++ ) {
3199 const U16 forid = TRIE_LIST_ITEM( state, idx).forid;
3200 if ( forid < minid ) {
3202 } else if ( forid > maxid ) {
3206 if ( transcount < tp + maxid - minid + 1) {
3208 trie->trans = (reg_trie_trans *)
3209 PerlMemShared_realloc( trie->trans,
3211 * sizeof(reg_trie_trans) );
3212 Zero( trie->trans + (transcount / 2),
3216 base = trie->uniquecharcount + tp - minid;
3217 if ( maxid == minid ) {
3219 for ( ; zp < tp ; zp++ ) {
3220 if ( ! trie->trans[ zp ].next ) {
3221 base = trie->uniquecharcount + zp - minid;
3222 trie->trans[ zp ].next = TRIE_LIST_ITEM( state,
3224 trie->trans[ zp ].check = state;
3230 trie->trans[ tp ].next = TRIE_LIST_ITEM( state,
3232 trie->trans[ tp ].check = state;
3237 for ( idx=1; idx <= TRIE_LIST_USED( state ) ; idx++ ) {
3238 const U32 tid = base
3239 - trie->uniquecharcount
3240 + TRIE_LIST_ITEM( state, idx ).forid;
3241 trie->trans[ tid ].next = TRIE_LIST_ITEM( state,
3243 trie->trans[ tid ].check = state;
3245 tp += ( maxid - minid + 1 );
3247 Safefree(trie->states[ state ].trans.list);
3250 DEBUG_TRIE_COMPILE_MORE_r(
3251 Perl_re_printf( aTHX_ " base: %d\n",base);
3254 trie->states[ state ].trans.base=base;
3256 trie->lasttrans = tp + 1;
3260 Second Pass -- Flat Table Representation.
3262 we dont use the 0 slot of either trans[] or states[] so we add 1 to
3263 each. We know that we will need Charcount+1 trans at most to store
3264 the data (one row per char at worst case) So we preallocate both
3265 structures assuming worst case.
3267 We then construct the trie using only the .next slots of the entry
3270 We use the .check field of the first entry of the node temporarily
3271 to make compression both faster and easier by keeping track of how
3272 many non zero fields are in the node.
3274 Since trans are numbered from 1 any 0 pointer in the table is a FAIL
3277 There are two terms at use here: state as a TRIE_NODEIDX() which is
3278 a number representing the first entry of the node, and state as a
3279 TRIE_NODENUM() which is the trans number. state 1 is TRIE_NODEIDX(1)
3280 and TRIE_NODENUM(1), state 2 is TRIE_NODEIDX(2) and TRIE_NODENUM(3)
3281 if there are 2 entrys per node. eg:
3289 The table is internally in the right hand, idx form. However as we
3290 also have to deal with the states array which is indexed by nodenum
3291 we have to use TRIE_NODENUM() to convert.
3294 DEBUG_TRIE_COMPILE_MORE_r( Perl_re_indentf( aTHX_ "Compiling trie using table compiler\n",
3297 trie->trans = (reg_trie_trans *)
3298 PerlMemShared_calloc( ( TRIE_CHARCOUNT(trie) + 1 )
3299 * trie->uniquecharcount + 1,
3300 sizeof(reg_trie_trans) );
3301 trie->states = (reg_trie_state *)
3302 PerlMemShared_calloc( TRIE_CHARCOUNT(trie) + 2,
3303 sizeof(reg_trie_state) );
3304 next_alloc = trie->uniquecharcount + 1;
3307 for ( cur = first ; cur < last ; cur = regnext( cur ) ) {
3309 regnode *noper = NEXTOPER( cur );
3311 U32 state = 1; /* required init */
3313 U16 charid = 0; /* sanity init */
3314 U32 accept_state = 0; /* sanity init */
3316 U32 wordlen = 0; /* required init */
3318 if (OP(noper) == NOTHING) {
3319 regnode *noper_next= regnext(noper);
3320 if (noper_next < tail)
3322 /* we will undo this assignment if noper does not
3323 * point at a trieable type in the else clause of
3324 * the following statement. */
3328 && ( OP(noper) == flags
3329 || (flags == EXACT && OP(noper) == EXACT_REQ8)
3330 || (flags == EXACTFU && ( OP(noper) == EXACTFU_REQ8
3331 || OP(noper) == EXACTFUP))))
3333 const U8 *uc= (U8*)STRING(noper);
3334 const U8 *e= uc + STR_LEN(noper);
3336 for ( ; uc < e ; uc += len ) {
3341 charid = trie->charmap[ uvc ];
3343 SV* const * const svpp = hv_fetch( widecharmap,
3347 charid = svpp ? (U16)SvIV(*svpp) : 0;
3351 if ( !trie->trans[ state + charid ].next ) {
3352 trie->trans[ state + charid ].next = next_alloc;
3353 trie->trans[ state ].check++;
3354 prev_states[TRIE_NODENUM(next_alloc)]
3355 = TRIE_NODENUM(state);
3356 next_alloc += trie->uniquecharcount;
3358 state = trie->trans[ state + charid ].next;
3360 Perl_croak( aTHX_ "panic! In trie construction, no char mapping for %" IVdf, uvc );
3362 /* charid is now 0 if we dont know the char read, or
3363 * nonzero if we do */
3366 /* If we end up here it is because we skipped past a NOTHING, but did not end up
3367 * on a trieable type. So we need to reset noper back to point at the first regop
3368 * in the branch before we call TRIE_HANDLE_WORD().
3370 noper= NEXTOPER(cur);
3372 accept_state = TRIE_NODENUM( state );
3373 TRIE_HANDLE_WORD(accept_state);
3375 } /* end second pass */
3377 /* and now dump it out before we compress it */
3378 DEBUG_TRIE_COMPILE_MORE_r(dump_trie_interim_table(trie, widecharmap,
3380 next_alloc, depth+1));
3384 * Inplace compress the table.*
3386 For sparse data sets the table constructed by the trie algorithm will
3387 be mostly 0/FAIL transitions or to put it another way mostly empty.
3388 (Note that leaf nodes will not contain any transitions.)
3390 This algorithm compresses the tables by eliminating most such
3391 transitions, at the cost of a modest bit of extra work during lookup:
3393 - Each states[] entry contains a .base field which indicates the
3394 index in the state[] array wheres its transition data is stored.
3396 - If .base is 0 there are no valid transitions from that node.
3398 - If .base is nonzero then charid is added to it to find an entry in
3401 -If trans[states[state].base+charid].check!=state then the
3402 transition is taken to be a 0/Fail transition. Thus if there are fail
3403 transitions at the front of the node then the .base offset will point
3404 somewhere inside the previous nodes data (or maybe even into a node
3405 even earlier), but the .check field determines if the transition is
3409 The following process inplace converts the table to the compressed
3410 table: We first do not compress the root node 1,and mark all its
3411 .check pointers as 1 and set its .base pointer as 1 as well. This
3412 allows us to do a DFA construction from the compressed table later,
3413 and ensures that any .base pointers we calculate later are greater
3416 - We set 'pos' to indicate the first entry of the second node.
3418 - We then iterate over the columns of the node, finding the first and
3419 last used entry at l and m. We then copy l..m into pos..(pos+m-l),
3420 and set the .check pointers accordingly, and advance pos
3421 appropriately and repreat for the next node. Note that when we copy
3422 the next pointers we have to convert them from the original
3423 NODEIDX form to NODENUM form as the former is not valid post
3426 - If a node has no transitions used we mark its base as 0 and do not
3427 advance the pos pointer.
3429 - If a node only has one transition we use a second pointer into the
3430 structure to fill in allocated fail transitions from other states.
3431 This pointer is independent of the main pointer and scans forward
3432 looking for null transitions that are allocated to a state. When it
3433 finds one it writes the single transition into the "hole". If the
3434 pointer doesnt find one the single transition is appended as normal.
3436 - Once compressed we can Renew/realloc the structures to release the
3439 See "Table-Compression Methods" in sec 3.9 of the Red Dragon,
3440 specifically Fig 3.47 and the associated pseudocode.
3444 const U32 laststate = TRIE_NODENUM( next_alloc );
3447 trie->statecount = laststate;
3449 for ( state = 1 ; state < laststate ; state++ ) {
3451 const U32 stateidx = TRIE_NODEIDX( state );
3452 const U32 o_used = trie->trans[ stateidx ].check;
3453 U32 used = trie->trans[ stateidx ].check;
3454 trie->trans[ stateidx ].check = 0;
3457 used && charid < trie->uniquecharcount;
3460 if ( flag || trie->trans[ stateidx + charid ].next ) {
3461 if ( trie->trans[ stateidx + charid ].next ) {
3463 for ( ; zp < pos ; zp++ ) {
3464 if ( ! trie->trans[ zp ].next ) {
3468 trie->states[ state ].trans.base
3470 + trie->uniquecharcount
3472 trie->trans[ zp ].next
3473 = SAFE_TRIE_NODENUM( trie->trans[ stateidx
3475 trie->trans[ zp ].check = state;
3476 if ( ++zp > pos ) pos = zp;
3483 trie->states[ state ].trans.base
3484 = pos + trie->uniquecharcount - charid ;
3486 trie->trans[ pos ].next
3487 = SAFE_TRIE_NODENUM(
3488 trie->trans[ stateidx + charid ].next );
3489 trie->trans[ pos ].check = state;
3494 trie->lasttrans = pos + 1;
3495 trie->states = (reg_trie_state *)
3496 PerlMemShared_realloc( trie->states, laststate
3497 * sizeof(reg_trie_state) );
3498 DEBUG_TRIE_COMPILE_MORE_r(
3499 Perl_re_indentf( aTHX_ "Alloc: %d Orig: %" IVdf " elements, Final:%" IVdf ". Savings of %%%5.2f\n",
3501 (int)( ( TRIE_CHARCOUNT(trie) + 1 ) * trie->uniquecharcount
3505 ( ( next_alloc - pos ) * 100 ) / (double)next_alloc );
3508 } /* end table compress */
3510 DEBUG_TRIE_COMPILE_MORE_r(
3511 Perl_re_indentf( aTHX_ "Statecount:%" UVxf " Lasttrans:%" UVxf "\n",
3513 (UV)trie->statecount,
3514 (UV)trie->lasttrans)
3516 /* resize the trans array to remove unused space */
3517 trie->trans = (reg_trie_trans *)
3518 PerlMemShared_realloc( trie->trans, trie->lasttrans
3519 * sizeof(reg_trie_trans) );
3521 { /* Modify the program and insert the new TRIE node */
3522 U8 nodetype =(U8)(flags & 0xFF);
3526 regnode *optimize = NULL;
3527 #ifdef RE_TRACK_PATTERN_OFFSETS
3530 U32 mjd_nodelen = 0;
3531 #endif /* RE_TRACK_PATTERN_OFFSETS */
3532 #endif /* DEBUGGING */
3534 This means we convert either the first branch or the first Exact,
3535 depending on whether the thing following (in 'last') is a branch
3536 or not and whther first is the startbranch (ie is it a sub part of
3537 the alternation or is it the whole thing.)
3538 Assuming its a sub part we convert the EXACT otherwise we convert
3539 the whole branch sequence, including the first.
3541 /* Find the node we are going to overwrite */
3542 if ( first != startbranch || OP( last ) == BRANCH ) {
3543 /* branch sub-chain */
3544 NEXT_OFF( first ) = (U16)(last - first);
3545 #ifdef RE_TRACK_PATTERN_OFFSETS
3547 mjd_offset= Node_Offset((convert));
3548 mjd_nodelen= Node_Length((convert));
3551 /* whole branch chain */
3553 #ifdef RE_TRACK_PATTERN_OFFSETS
3556 const regnode *nop = NEXTOPER( convert );
3557 mjd_offset= Node_Offset((nop));
3558 mjd_nodelen= Node_Length((nop));
3562 Perl_re_indentf( aTHX_ "MJD offset:%" UVuf " MJD length:%" UVuf "\n",
3564 (UV)mjd_offset, (UV)mjd_nodelen)
3567 /* But first we check to see if there is a common prefix we can
3568 split out as an EXACT and put in front of the TRIE node. */
3569 trie->startstate= 1;
3570 if ( trie->bitmap && !widecharmap && !trie->jump ) {
3571 /* we want to find the first state that has more than
3572 * one transition, if that state is not the first state
3573 * then we have a common prefix which we can remove.
3576 for ( state = 1 ; state < trie->statecount-1 ; state++ ) {
3578 I32 first_ofs = -1; /* keeps track of the ofs of the first
3579 transition, -1 means none */
3581 const U32 base = trie->states[ state ].trans.base;
3583 /* does this state terminate an alternation? */
3584 if ( trie->states[state].wordnum )
3587 for ( ofs = 0 ; ofs < trie->uniquecharcount ; ofs++ ) {
3588 if ( ( base + ofs >= trie->uniquecharcount ) &&
3589 ( base + ofs - trie->uniquecharcount < trie->lasttrans ) &&
3590 trie->trans[ base + ofs - trie->uniquecharcount ].check == state )
3592 if ( ++count > 1 ) {
3593 /* we have more than one transition */
3596 /* if this is the first state there is no common prefix
3597 * to extract, so we can exit */
3598 if ( state == 1 ) break;
3599 tmp = av_fetch( revcharmap, ofs, 0);
3600 ch = (U8*)SvPV_nolen_const( *tmp );
3602 /* if we are on count 2 then we need to initialize the
3603 * bitmap, and store the previous char if there was one
3606 /* clear the bitmap */
3607 Zero(trie->bitmap, ANYOF_BITMAP_SIZE, char);
3609 Perl_re_indentf( aTHX_ "New Start State=%" UVuf " Class: [",
3612 if (first_ofs >= 0) {
3613 SV ** const tmp = av_fetch( revcharmap, first_ofs, 0);
3614 const U8 * const ch = (U8*)SvPV_nolen_const( *tmp );
3616 TRIE_BITMAP_SET_FOLDED(trie,*ch, folder);
3618 Perl_re_printf( aTHX_ "%s", (char*)ch)
3622 /* store the current firstchar in the bitmap */
3623 TRIE_BITMAP_SET_FOLDED(trie,*ch, folder);
3624 DEBUG_OPTIMISE_r(Perl_re_printf( aTHX_ "%s", ch));
3630 /* This state has only one transition, its transition is part
3631 * of a common prefix - we need to concatenate the char it
3632 * represents to what we have so far. */
3633 SV **tmp = av_fetch( revcharmap, first_ofs, 0);
3635 char *ch = SvPV( *tmp, len );
3637 SV *sv=sv_newmortal();
3638 Perl_re_indentf( aTHX_ "Prefix State: %" UVuf " Ofs:%" UVuf " Char='%s'\n",
3640 (UV)state, (UV)first_ofs,
3641 pv_pretty(sv, SvPV_nolen_const(*tmp), SvCUR(*tmp), 6,
3642 PL_colors[0], PL_colors[1],
3643 (SvUTF8(*tmp) ? PERL_PV_ESCAPE_UNI : 0) |
3644 PERL_PV_ESCAPE_FIRSTCHAR
3649 OP( convert ) = nodetype;
3650 str=STRING(convert);
3651 setSTR_LEN(convert, 0);
3653 assert( ( STR_LEN(convert) + len ) < 256 );
3654 setSTR_LEN(convert, (U8)(STR_LEN(convert) + len));
3660 DEBUG_OPTIMISE_r(Perl_re_printf( aTHX_ "]\n"));
3665 trie->prefixlen = (state-1);
3667 regnode *n = convert+NODE_SZ_STR(convert);
3668 assert( NODE_SZ_STR(convert) <= U16_MAX );
3669 NEXT_OFF(convert) = (U16)(NODE_SZ_STR(convert));
3670 trie->startstate = state;
3671 trie->minlen -= (state - 1);
3672 trie->maxlen -= (state - 1);
3674 /* At least the UNICOS C compiler choked on this
3675 * being argument to DEBUG_r(), so let's just have
3678 #ifdef PERL_EXT_RE_BUILD
3684 regnode *fix = convert;
3685 U32 word = trie->wordcount;
3686 #ifdef RE_TRACK_PATTERN_OFFSETS
3689 Set_Node_Offset_Length(convert, mjd_offset, state - 1);
3690 while( ++fix < n ) {
3691 Set_Node_Offset_Length(fix, 0, 0);
3694 SV ** const tmp = av_fetch( trie_words, word, 0 );
3696 if ( STR_LEN(convert) <= SvCUR(*tmp) )
3697 sv_chop(*tmp, SvPV_nolen(*tmp) + STR_LEN(convert));
3699 sv_chop(*tmp, SvPV_nolen(*tmp) + SvCUR(*tmp));
3707 NEXT_OFF(convert) = (U16)(tail - convert);
3708 DEBUG_r(optimize= n);
3714 if ( trie->maxlen ) {
3715 NEXT_OFF( convert ) = (U16)(tail - convert);
3716 ARG_SET( convert, data_slot );
3717 /* Store the offset to the first unabsorbed branch in
3718 jump[0], which is otherwise unused by the jump logic.
3719 We use this when dumping a trie and during optimisation. */
3721 trie->jump[0] = (U16)(nextbranch - convert);
3723 /* If the start state is not accepting (meaning there is no empty string/NOTHING)
3724 * and there is a bitmap
3725 * and the first "jump target" node we found leaves enough room
3726 * then convert the TRIE node into a TRIEC node, with the bitmap
3727 * embedded inline in the opcode - this is hypothetically faster.
3729 if ( !trie->states[trie->startstate].wordnum
3731 && ( (char *)jumper - (char *)convert) >= (int)sizeof(struct regnode_charclass) )
3733 OP( convert ) = TRIEC;
3734 Copy(trie->bitmap, ((struct regnode_charclass *)convert)->bitmap, ANYOF_BITMAP_SIZE, char);
3735 PerlMemShared_free(trie->bitmap);
3738 OP( convert ) = TRIE;
3740 /* store the type in the flags */
3741 convert->flags = nodetype;
3745 + regarglen[ OP( convert ) ];
3747 /* XXX We really should free up the resource in trie now,
3748 as we won't use them - (which resources?) dmq */
3750 /* needed for dumping*/
3751 DEBUG_r(if (optimize) {
3752 regnode *opt = convert;
3754 while ( ++opt < optimize) {
3755 Set_Node_Offset_Length(opt, 0, 0);
3758 Try to clean up some of the debris left after the
3761 while( optimize < jumper ) {
3762 Track_Code( mjd_nodelen += Node_Length((optimize)); );
3763 OP( optimize ) = OPTIMIZED;
3764 Set_Node_Offset_Length(optimize, 0, 0);
3767 Set_Node_Offset_Length(convert, mjd_offset, mjd_nodelen);
3769 } /* end node insert */
3771 /* Finish populating the prev field of the wordinfo array. Walk back
3772 * from each accept state until we find another accept state, and if
3773 * so, point the first word's .prev field at the second word. If the
3774 * second already has a .prev field set, stop now. This will be the
3775 * case either if we've already processed that word's accept state,
3776 * or that state had multiple words, and the overspill words were
3777 * already linked up earlier.
3784 for (word=1; word <= trie->wordcount; word++) {
3786 if (trie->wordinfo[word].prev)
3788 state = trie->wordinfo[word].accept;
3790 state = prev_states[state];
3793 prev = trie->states[state].wordnum;
3797 trie->wordinfo[word].prev = prev;
3799 Safefree(prev_states);
3803 /* and now dump out the compressed format */
3804 DEBUG_TRIE_COMPILE_r(dump_trie(trie, widecharmap, revcharmap, depth+1));
3806 RExC_rxi->data->data[ data_slot + 1 ] = (void*)widecharmap;
3808 RExC_rxi->data->data[ data_slot + TRIE_WORDS_OFFSET ] = (void*)trie_words;
3809 RExC_rxi->data->data[ data_slot + 3 ] = (void*)revcharmap;
3811 SvREFCNT_dec_NN(revcharmap);
3815 : trie->startstate>1
3821 S_construct_ahocorasick_from_trie(pTHX_ RExC_state_t *pRExC_state, regnode *source, U32 depth)
3823 /* The Trie is constructed and compressed now so we can build a fail array if
3826 This is basically the Aho-Corasick algorithm. Its from exercise 3.31 and
3828 "Red Dragon" -- Compilers, principles, techniques, and tools. Aho, Sethi,
3832 We find the fail state for each state in the trie, this state is the longest
3833 proper suffix of the current state's 'word' that is also a proper prefix of
3834 another word in our trie. State 1 represents the word '' and is thus the
3835 default fail state. This allows the DFA not to have to restart after its
3836 tried and failed a word at a given point, it simply continues as though it
3837 had been matching the other word in the first place.
3839 'abcdgu'=~/abcdefg|cdgu/
3840 When we get to 'd' we are still matching the first word, we would encounter
3841 'g' which would fail, which would bring us to the state representing 'd' in
3842 the second word where we would try 'g' and succeed, proceeding to match
3845 /* add a fail transition */
3846 const U32 trie_offset = ARG(source);
3847 reg_trie_data *trie=(reg_trie_data *)RExC_rxi->data->data[trie_offset];
3849 const U32 ucharcount = trie->uniquecharcount;
3850 const U32 numstates = trie->statecount;
3851 const U32 ubound = trie->lasttrans + ucharcount;
3855 U32 base = trie->states[ 1 ].trans.base;
3858 const U32 data_slot = add_data( pRExC_state, STR_WITH_LEN("T"));
3860 DECLARE_AND_GET_RE_DEBUG_FLAGS;
3862 PERL_ARGS_ASSERT_CONSTRUCT_AHOCORASICK_FROM_TRIE;
3863 PERL_UNUSED_CONTEXT;
3865 PERL_UNUSED_ARG(depth);
3868 if ( OP(source) == TRIE ) {
3869 struct regnode_1 *op = (struct regnode_1 *)
3870 PerlMemShared_calloc(1, sizeof(struct regnode_1));
3871 StructCopy(source, op, struct regnode_1);
3872 stclass = (regnode *)op;
3874 struct regnode_charclass *op = (struct regnode_charclass *)
3875 PerlMemShared_calloc(1, sizeof(struct regnode_charclass));
3876 StructCopy(source, op, struct regnode_charclass);
3877 stclass = (regnode *)op;
3879 OP(stclass)+=2; /* convert the TRIE type to its AHO-CORASICK equivalent */
3881 ARG_SET( stclass, data_slot );
3882 aho = (reg_ac_data *) PerlMemShared_calloc( 1, sizeof(reg_ac_data) );
3883 RExC_rxi->data->data[ data_slot ] = (void*)aho;
3884 aho->trie=trie_offset;
3885 aho->states=(reg_trie_state *)PerlMemShared_malloc( numstates * sizeof(reg_trie_state) );
3886 Copy( trie->states, aho->states, numstates, reg_trie_state );
3887 Newx( q, numstates, U32);
3888 aho->fail = (U32 *) PerlMemShared_calloc( numstates, sizeof(U32) );
3891 /* initialize fail[0..1] to be 1 so that we always have
3892 a valid final fail state */
3893 fail[ 0 ] = fail[ 1 ] = 1;
3895 for ( charid = 0; charid < ucharcount ; charid++ ) {
3896 const U32 newstate = TRIE_TRANS_STATE( 1, base, ucharcount, charid, 0 );
3898 q[ q_write ] = newstate;
3899 /* set to point at the root */
3900 fail[ q[ q_write++ ] ]=1;
3903 while ( q_read < q_write) {
3904 const U32 cur = q[ q_read++ % numstates ];
3905 base = trie->states[ cur ].trans.base;
3907 for ( charid = 0 ; charid < ucharcount ; charid++ ) {
3908 const U32 ch_state = TRIE_TRANS_STATE( cur, base, ucharcount, charid, 1 );
3910 U32 fail_state = cur;
3913 fail_state = fail[ fail_state ];
3914 fail_base = aho->states[ fail_state ].trans.base;
3915 } while ( !TRIE_TRANS_STATE( fail_state, fail_base, ucharcount, charid, 1 ) );
3917 fail_state = TRIE_TRANS_STATE( fail_state, fail_base, ucharcount, charid, 1 );
3918 fail[ ch_state ] = fail_state;
3919 if ( !aho->states[ ch_state ].wordnum && aho->states[ fail_state ].wordnum )
3921 aho->states[ ch_state ].wordnum = aho->states[ fail_state ].wordnum;
3923 q[ q_write++ % numstates] = ch_state;
3927 /* restore fail[0..1] to 0 so that we "fall out" of the AC loop
3928 when we fail in state 1, this allows us to use the
3929 charclass scan to find a valid start char. This is based on the principle
3930 that theres a good chance the string being searched contains lots of stuff
3931 that cant be a start char.
3933 fail[ 0 ] = fail[ 1 ] = 0;
3934 DEBUG_TRIE_COMPILE_r({
3935 Perl_re_indentf( aTHX_ "Stclass Failtable (%" UVuf " states): 0",
3936 depth, (UV)numstates
3938 for( q_read=1; q_read<numstates; q_read++ ) {
3939 Perl_re_printf( aTHX_ ", %" UVuf, (UV)fail[q_read]);
3941 Perl_re_printf( aTHX_ "\n");
3944 /*RExC_seen |= REG_TRIEDFA_SEEN;*/
3949 /* The below joins as many adjacent EXACTish nodes as possible into a single
3950 * one. The regop may be changed if the node(s) contain certain sequences that
3951 * require special handling. The joining is only done if:
3952 * 1) there is room in the current conglomerated node to entirely contain the
3954 * 2) they are compatible node types
3956 * The adjacent nodes actually may be separated by NOTHING-kind nodes, and
3957 * these get optimized out
3959 * XXX khw thinks this should be enhanced to fill EXACT (at least) nodes as full
3960 * as possible, even if that means splitting an existing node so that its first
3961 * part is moved to the preceeding node. This would maximise the efficiency of
3962 * memEQ during matching.
3964 * If a node is to match under /i (folded), the number of characters it matches
3965 * can be different than its character length if it contains a multi-character
3966 * fold. *min_subtract is set to the total delta number of characters of the
3969 * And *unfolded_multi_char is set to indicate whether or not the node contains
3970 * an unfolded multi-char fold. This happens when it won't be known until
3971 * runtime whether the fold is valid or not; namely
3972 * 1) for EXACTF nodes that contain LATIN SMALL LETTER SHARP S, as only if the
3973 * target string being matched against turns out to be UTF-8 is that fold
3975 * 2) for EXACTFL nodes whose folding rules depend on the locale in force at
3977 * (Multi-char folds whose components are all above the Latin1 range are not
3978 * run-time locale dependent, and have already been folded by the time this
3979 * function is called.)
https://perl5.git.perl.org / perl5.git / blob