Commit | Line | Data |
---|---|---|
a0d0e21e LW |
1 | /* regcomp.c |
2 | */ | |
3 | ||
4 | /* | |
4ac71550 TC |
5 | * 'A fair jaw-cracker dwarf-language must be.' --Samwise Gamgee |
6 | * | |
7 | * [p.285 of _The Lord of the Rings_, II/iii: "The Ring Goes South"] | |
a0d0e21e LW |
8 | */ |
9 | ||
61296642 DM |
10 | /* This file contains functions for compiling a regular expression. See |
11 | * also regexec.c which funnily enough, contains functions for executing | |
166f8a29 | 12 | * a regular expression. |
e4a054ea DM |
13 | * |
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. | |
166f8a29 DM |
18 | */ |
19 | ||
a687059c LW |
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! | |
22 | */ | |
23 | ||
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. | |
27 | */ | |
28 | ||
e50aee73 | 29 | /* The names of the functions have been changed from regcomp and |
3b753521 | 30 | * regexec to pregcomp and pregexec in order to avoid conflicts |
e50aee73 AD |
31 | * with the POSIX routines of the same names. |
32 | */ | |
33 | ||
b9d5759e | 34 | #ifdef PERL_EXT_RE_BUILD |
54df2634 | 35 | #include "re_top.h" |
b81d288d | 36 | #endif |
56953603 | 37 | |
a687059c | 38 | /* |
e50aee73 | 39 | * pregcomp and pregexec -- regsub and regerror are not used in perl |
a687059c LW |
40 | * |
41 | * Copyright (c) 1986 by University of Toronto. | |
42 | * Written by Henry Spencer. Not derived from licensed software. | |
43 | * | |
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: | |
47 | * | |
48 | * 1. The author is not responsible for the consequences of use of | |
49 | * this software, no matter how awful, even if they arise | |
50 | * from defects in it. | |
51 | * | |
52 | * 2. The origin of this software must not be misrepresented, either | |
53 | * by explicit claim or by omission. | |
54 | * | |
55 | * 3. Altered versions must be plainly marked as such, and must not | |
56 | * be misrepresented as being the original software. | |
57 | * | |
58 | * | |
59 | **** Alterations to Henry's code are... | |
60 | **** | |
4bb101f2 | 61 | **** Copyright (C) 1991, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999, |
1129b882 NC |
62 | **** 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008 |
63 | **** by Larry Wall and others | |
a687059c | 64 | **** |
9ef589d8 LW |
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. | |
67 | ||
a687059c LW |
68 | * |
69 | * Beware that some of this code is subtly aware of the way operator | |
70 | * precedence is structured in regular expressions. Serious changes in | |
71 | * regular-expression syntax might require a total rethink. | |
72 | */ | |
73 | #include "EXTERN.h" | |
864dbfa3 | 74 | #define PERL_IN_REGCOMP_C |
a687059c | 75 | #include "perl.h" |
d06ea78c | 76 | |
acfe0abc | 77 | #ifndef PERL_IN_XSUB_RE |
d06ea78c GS |
78 | # include "INTERN.h" |
79 | #endif | |
c277df42 IZ |
80 | |
81 | #define REG_COMP_C | |
54df2634 NC |
82 | #ifdef PERL_IN_XSUB_RE |
83 | # include "re_comp.h" | |
afda64e8 | 84 | EXTERN_C const struct regexp_engine my_reg_engine; |
54df2634 NC |
85 | #else |
86 | # include "regcomp.h" | |
87 | #endif | |
a687059c | 88 | |
f7e03a10 | 89 | #include "dquote_inline.h" |
b992490d | 90 | #include "invlist_inline.h" |
1b0f46bf | 91 | #include "unicode_constants.h" |
04e98a4d | 92 | |
538e84ed KW |
93 | #define HAS_NONLATIN1_FOLD_CLOSURE(i) \ |
94 | _HAS_NONLATIN1_FOLD_CLOSURE_ONLY_FOR_USE_BY_REGCOMP_DOT_C_AND_REGEXEC_DOT_C(i) | |
f12c0118 KW |
95 | #define HAS_NONLATIN1_SIMPLE_FOLD_CLOSURE(i) \ |
96 | _HAS_NONLATIN1_SIMPLE_FOLD_CLOSURE_ONLY_FOR_USE_BY_REGCOMP_DOT_C_AND_REGEXEC_DOT_C(i) | |
26faadbd | 97 | #define IS_NON_FINAL_FOLD(c) _IS_NON_FINAL_FOLD_ONLY_FOR_USE_BY_REGCOMP_DOT_C(c) |
2c61f163 | 98 | #define IS_IN_SOME_FOLD_L1(c) _IS_IN_SOME_FOLD_ONLY_FOR_USE_BY_REGCOMP_DOT_C(c) |
94dc5c2d | 99 | |
a687059c LW |
100 | #ifndef STATIC |
101 | #define STATIC static | |
102 | #endif | |
103 | ||
3f910e62 YO |
104 | /* this is a chain of data about sub patterns we are processing that |
105 | need to be handled separately/specially in study_chunk. Its so | |
106 | we can simulate recursion without losing state. */ | |
107 | struct scan_frame; | |
108 | typedef struct scan_frame { | |
109 | regnode *last_regnode; /* last node to process in this frame */ | |
110 | regnode *next_regnode; /* next node to process when last is reached */ | |
111 | U32 prev_recursed_depth; | |
112 | I32 stopparen; /* what stopparen do we use */ | |
3f910e62 YO |
113 | |
114 | struct scan_frame *this_prev_frame; /* this previous frame */ | |
115 | struct scan_frame *prev_frame; /* previous frame */ | |
116 | struct scan_frame *next_frame; /* next frame */ | |
117 | } scan_frame; | |
118 | ||
f4ae5a27 KW |
119 | /* Certain characters are output as a sequence with the first being a |
120 | * backslash. */ | |
eb7486de | 121 | #define isBACKSLASHED_PUNCT(c) strchr("-[]\\^", c) |
f4ae5a27 KW |
122 | |
123 | ||
09b2b2e6 | 124 | struct RExC_state_t { |
514a91f1 DM |
125 | U32 flags; /* RXf_* are we folding, multilining? */ |
126 | U32 pm_flags; /* PMf_* stuff from the calling PMOP */ | |
830247a4 | 127 | char *precomp; /* uncompiled string. */ |
711b303b | 128 | char *precomp_end; /* pointer to end of uncompiled string. */ |
288b8c02 | 129 | REGEXP *rx_sv; /* The SV that is the regexp. */ |
f8fc2ecf | 130 | regexp *rx; /* perl core regexp structure */ |
538e84ed KW |
131 | regexp_internal *rxi; /* internal data for regexp object |
132 | pprivate field */ | |
fac92740 | 133 | char *start; /* Start of input for compile */ |
830247a4 IZ |
134 | char *end; /* End of input for compile */ |
135 | char *parse; /* Input-scan pointer. */ | |
285b5ca0 KW |
136 | char *adjusted_start; /* 'start', adjusted. See code use */ |
137 | STRLEN precomp_adj; /* an offset beyond precomp. See code use */ | |
ea3daa5d | 138 | SSize_t whilem_seen; /* number of WHILEM in this expr */ |
fac92740 | 139 | regnode *emit_start; /* Start of emitted-code area */ |
538e84ed KW |
140 | regnode *emit_bound; /* First regnode outside of the |
141 | allocated space */ | |
f7c7e32a DM |
142 | regnode *emit; /* Code-emit pointer; if = &emit_dummy, |
143 | implies compiling, so don't emit */ | |
9a81a976 KW |
144 | regnode_ssc emit_dummy; /* placeholder for emit to point to; |
145 | large enough for the largest | |
146 | non-EXACTish node, so can use it as | |
147 | scratch in pass1 */ | |
830247a4 IZ |
148 | I32 naughty; /* How bad is this pattern? */ |
149 | I32 sawback; /* Did we see \1, ...? */ | |
150 | U32 seen; | |
ea3daa5d | 151 | SSize_t size; /* Code size. */ |
e7f023ff | 152 | I32 npar; /* Capture buffer count, (OPEN) plus |
538e84ed KW |
153 | one. ("par" 0 is the whole |
154 | pattern)*/ | |
155 | I32 nestroot; /* root parens we are in - used by | |
156 | accept */ | |
830247a4 IZ |
157 | I32 extralen; |
158 | I32 seen_zerolen; | |
40d049e4 YO |
159 | regnode **open_parens; /* pointers to open parens */ |
160 | regnode **close_parens; /* pointers to close parens */ | |
d5a00e4a | 161 | regnode *end_op; /* END node in program */ |
02daf0ab YO |
162 | I32 utf8; /* whether the pattern is utf8 or not */ |
163 | I32 orig_utf8; /* whether the pattern was originally in utf8 */ | |
164 | /* XXX use this for future optimisation of case | |
165 | * where pattern must be upgraded to utf8. */ | |
e40e74fe KW |
166 | I32 uni_semantics; /* If a d charset modifier should use unicode |
167 | rules, even if the pattern is not in | |
168 | utf8 */ | |
81714fb9 | 169 | HV *paren_names; /* Paren names */ |
538e84ed | 170 | |
40d049e4 | 171 | regnode **recurse; /* Recurse regops */ |
d5a00e4a | 172 | I32 recurse_count; /* Number of recurse regops we have generated */ |
4286711a | 173 | U8 *study_chunk_recursed; /* bitmap of which subs we have moved |
538e84ed | 174 | through */ |
09a65838 | 175 | U32 study_chunk_recursed_bytes; /* bytes in bitmap */ |
b57e4118 | 176 | I32 in_lookbehind; |
4624b182 | 177 | I32 contains_locale; |
bb3f3ed2 | 178 | I32 override_recoding; |
b6d67071 KW |
179 | #ifdef EBCDIC |
180 | I32 recode_x_to_native; | |
181 | #endif | |
9d53c457 | 182 | I32 in_multi_char_class; |
1acab4c5 | 183 | struct reg_code_blocks *code_blocks;/* positions of literal (?{}) |
68e2671b | 184 | within pattern */ |
b1603ef8 | 185 | int code_index; /* next code_blocks[] slot */ |
ee273784 | 186 | SSize_t maxlen; /* mininum possible number of chars in string to match */ |
3f910e62 YO |
187 | scan_frame *frame_head; |
188 | scan_frame *frame_last; | |
189 | U32 frame_count; | |
7eec73eb | 190 | AV *warn_text; |
dc6d7f5c | 191 | #ifdef ADD_TO_REGEXEC |
830247a4 IZ |
192 | char *starttry; /* -Dr: where regtry was called. */ |
193 | #define RExC_starttry (pRExC_state->starttry) | |
194 | #endif | |
d24ca0c5 | 195 | SV *runtime_code_qr; /* qr with the runtime code blocks */ |
3dab1dad | 196 | #ifdef DEBUGGING |
be8e71aa | 197 | const char *lastparse; |
3dab1dad | 198 | I32 lastnum; |
1f1031fe | 199 | AV *paren_name_list; /* idx -> name */ |
d9a72fcc | 200 | U32 study_chunk_recursed_count; |
c9f0d54c YO |
201 | SV *mysv1; |
202 | SV *mysv2; | |
3dab1dad YO |
203 | #define RExC_lastparse (pRExC_state->lastparse) |
204 | #define RExC_lastnum (pRExC_state->lastnum) | |
1f1031fe | 205 | #define RExC_paren_name_list (pRExC_state->paren_name_list) |
d9a72fcc | 206 | #define RExC_study_chunk_recursed_count (pRExC_state->study_chunk_recursed_count) |
c9f0d54c YO |
207 | #define RExC_mysv (pRExC_state->mysv1) |
208 | #define RExC_mysv1 (pRExC_state->mysv1) | |
209 | #define RExC_mysv2 (pRExC_state->mysv2) | |
210 | ||
3dab1dad | 211 | #endif |
512c0f5a | 212 | bool seen_unfolded_sharp_s; |
911bd04e | 213 | bool strict; |
da7cf1cc | 214 | bool study_started; |
034602eb | 215 | bool in_script_run; |
09b2b2e6 | 216 | }; |
830247a4 | 217 | |
e2509266 | 218 | #define RExC_flags (pRExC_state->flags) |
514a91f1 | 219 | #define RExC_pm_flags (pRExC_state->pm_flags) |
830247a4 | 220 | #define RExC_precomp (pRExC_state->precomp) |
285b5ca0 KW |
221 | #define RExC_precomp_adj (pRExC_state->precomp_adj) |
222 | #define RExC_adjusted_start (pRExC_state->adjusted_start) | |
711b303b | 223 | #define RExC_precomp_end (pRExC_state->precomp_end) |
288b8c02 | 224 | #define RExC_rx_sv (pRExC_state->rx_sv) |
830247a4 | 225 | #define RExC_rx (pRExC_state->rx) |
f8fc2ecf | 226 | #define RExC_rxi (pRExC_state->rxi) |
fac92740 | 227 | #define RExC_start (pRExC_state->start) |
830247a4 IZ |
228 | #define RExC_end (pRExC_state->end) |
229 | #define RExC_parse (pRExC_state->parse) | |
230 | #define RExC_whilem_seen (pRExC_state->whilem_seen) | |
512c0f5a KW |
231 | |
232 | /* Set during the sizing pass when there is a LATIN SMALL LETTER SHARP S in any | |
233 | * EXACTF node, hence was parsed under /di rules. If later in the parse, | |
234 | * something forces the pattern into using /ui rules, the sharp s should be | |
235 | * folded into the sequence 'ss', which takes up more space than previously | |
236 | * calculated. This means that the sizing pass needs to be restarted. (The | |
237 | * node also becomes an EXACTFU_SS.) For all other characters, an EXACTF node | |
238 | * that gets converted to /ui (and EXACTFU) occupies the same amount of space, | |
239 | * so there is no need to resize [perl #125990]. */ | |
240 | #define RExC_seen_unfolded_sharp_s (pRExC_state->seen_unfolded_sharp_s) | |
241 | ||
7122b237 | 242 | #ifdef RE_TRACK_PATTERN_OFFSETS |
538e84ed KW |
243 | #define RExC_offsets (pRExC_state->rxi->u.offsets) /* I am not like the |
244 | others */ | |
7122b237 | 245 | #endif |
830247a4 | 246 | #define RExC_emit (pRExC_state->emit) |
f7c7e32a | 247 | #define RExC_emit_dummy (pRExC_state->emit_dummy) |
fac92740 | 248 | #define RExC_emit_start (pRExC_state->emit_start) |
3b57cd43 | 249 | #define RExC_emit_bound (pRExC_state->emit_bound) |
830247a4 IZ |
250 | #define RExC_sawback (pRExC_state->sawback) |
251 | #define RExC_seen (pRExC_state->seen) | |
252 | #define RExC_size (pRExC_state->size) | |
ee273784 | 253 | #define RExC_maxlen (pRExC_state->maxlen) |
830247a4 | 254 | #define RExC_npar (pRExC_state->npar) |
e2e6a0f1 | 255 | #define RExC_nestroot (pRExC_state->nestroot) |
830247a4 IZ |
256 | #define RExC_extralen (pRExC_state->extralen) |
257 | #define RExC_seen_zerolen (pRExC_state->seen_zerolen) | |
1aa99e6b | 258 | #define RExC_utf8 (pRExC_state->utf8) |
e40e74fe | 259 | #define RExC_uni_semantics (pRExC_state->uni_semantics) |
02daf0ab | 260 | #define RExC_orig_utf8 (pRExC_state->orig_utf8) |
40d049e4 YO |
261 | #define RExC_open_parens (pRExC_state->open_parens) |
262 | #define RExC_close_parens (pRExC_state->close_parens) | |
5bd2d46e | 263 | #define RExC_end_op (pRExC_state->end_op) |
81714fb9 | 264 | #define RExC_paren_names (pRExC_state->paren_names) |
40d049e4 YO |
265 | #define RExC_recurse (pRExC_state->recurse) |
266 | #define RExC_recurse_count (pRExC_state->recurse_count) | |
09a65838 | 267 | #define RExC_study_chunk_recursed (pRExC_state->study_chunk_recursed) |
538e84ed KW |
268 | #define RExC_study_chunk_recursed_bytes \ |
269 | (pRExC_state->study_chunk_recursed_bytes) | |
b57e4118 | 270 | #define RExC_in_lookbehind (pRExC_state->in_lookbehind) |
4624b182 | 271 | #define RExC_contains_locale (pRExC_state->contains_locale) |
b6d67071 KW |
272 | #ifdef EBCDIC |
273 | # define RExC_recode_x_to_native (pRExC_state->recode_x_to_native) | |
274 | #endif | |
9d53c457 | 275 | #define RExC_in_multi_char_class (pRExC_state->in_multi_char_class) |
3f910e62 YO |
276 | #define RExC_frame_head (pRExC_state->frame_head) |
277 | #define RExC_frame_last (pRExC_state->frame_last) | |
278 | #define RExC_frame_count (pRExC_state->frame_count) | |
67cdf558 | 279 | #define RExC_strict (pRExC_state->strict) |
da7cf1cc | 280 | #define RExC_study_started (pRExC_state->study_started) |
7eec73eb | 281 | #define RExC_warn_text (pRExC_state->warn_text) |
034602eb | 282 | #define RExC_in_script_run (pRExC_state->in_script_run) |
830247a4 | 283 | |
99807a43 HS |
284 | /* Heuristic check on the complexity of the pattern: if TOO_NAUGHTY, we set |
285 | * a flag to disable back-off on the fixed/floating substrings - if it's | |
286 | * a high complexity pattern we assume the benefit of avoiding a full match | |
287 | * is worth the cost of checking for the substrings even if they rarely help. | |
288 | */ | |
289 | #define RExC_naughty (pRExC_state->naughty) | |
290 | #define TOO_NAUGHTY (10) | |
291 | #define MARK_NAUGHTY(add) \ | |
292 | if (RExC_naughty < TOO_NAUGHTY) \ | |
293 | RExC_naughty += (add) | |
294 | #define MARK_NAUGHTY_EXP(exp, add) \ | |
295 | if (RExC_naughty < TOO_NAUGHTY) \ | |
296 | RExC_naughty += RExC_naughty / (exp) + (add) | |
cde0cee5 | 297 | |
a687059c LW |
298 | #define ISMULT1(c) ((c) == '*' || (c) == '+' || (c) == '?') |
299 | #define ISMULT2(s) ((*s) == '*' || (*s) == '+' || (*s) == '?' || \ | |
412f55bb | 300 | ((*s) == '{' && regcurly(s))) |
a687059c LW |
301 | |
302 | /* | |
303 | * Flags to be passed up and down. | |
304 | */ | |
a687059c | 305 | #define WORST 0 /* Worst case. */ |
a3b492c3 | 306 | #define HASWIDTH 0x01 /* Known to match non-null strings. */ |
fda99bee | 307 | |
e64f369d | 308 | /* Simple enough to be STAR/PLUS operand; in an EXACTish node must be a single |
2fd92675 KW |
309 | * character. (There needs to be a case: in the switch statement in regexec.c |
310 | * for any node marked SIMPLE.) Note that this is not the same thing as | |
311 | * REGNODE_SIMPLE */ | |
fda99bee | 312 | #define SIMPLE 0x02 |
e64f369d | 313 | #define SPSTART 0x04 /* Starts with * or + */ |
8d9c2815 NC |
314 | #define POSTPONED 0x08 /* (?1),(?&name), (??{...}) or similar */ |
315 | #define TRYAGAIN 0x10 /* Weeded out a declaration. */ | |
b97943f7 KW |
316 | #define RESTART_PASS1 0x20 /* Need to restart sizing pass */ |
317 | #define NEED_UTF8 0x40 /* In conjunction with RESTART_PASS1, need to | |
318 | calcuate sizes as UTF-8 */ | |
a687059c | 319 | |
3dab1dad YO |
320 | #define REG_NODE_NUM(x) ((x) ? (int)((x)-RExC_emit_start) : -1) |
321 | ||
07be1b83 YO |
322 | /* whether trie related optimizations are enabled */ |
323 | #if PERL_ENABLE_EXTENDED_TRIE_OPTIMISATION | |
324 | #define TRIE_STUDY_OPT | |
786e8c11 | 325 | #define FULL_TRIE_STUDY |
07be1b83 YO |
326 | #define TRIE_STCLASS |
327 | #endif | |
1de06328 YO |
328 | |
329 | ||
40d049e4 YO |
330 | |
331 | #define PBYTE(u8str,paren) ((U8*)(u8str))[(paren) >> 3] | |
332 | #define PBITVAL(paren) (1 << ((paren) & 7)) | |
333 | #define PAREN_TEST(u8str,paren) ( PBYTE(u8str,paren) & PBITVAL(paren)) | |
334 | #define PAREN_SET(u8str,paren) PBYTE(u8str,paren) |= PBITVAL(paren) | |
335 | #define PAREN_UNSET(u8str,paren) PBYTE(u8str,paren) &= (~PBITVAL(paren)) | |
336 | ||
82a6ada4 | 337 | #define REQUIRE_UTF8(flagp) STMT_START { \ |
8d9c2815 | 338 | if (!UTF) { \ |
82a6ada4 KW |
339 | assert(PASS1); \ |
340 | *flagp = RESTART_PASS1|NEED_UTF8; \ | |
8d9c2815 NC |
341 | return NULL; \ |
342 | } \ | |
82a6ada4 | 343 | } STMT_END |
40d049e4 | 344 | |
512c0f5a KW |
345 | /* Change from /d into /u rules, and restart the parse if we've already seen |
346 | * something whose size would increase as a result, by setting *flagp and | |
347 | * returning 'restart_retval'. RExC_uni_semantics is a flag that indicates | |
142ece99 | 348 | * we've changed to /u during the parse. */ |
512c0f5a KW |
349 | #define REQUIRE_UNI_RULES(flagp, restart_retval) \ |
350 | STMT_START { \ | |
351 | if (DEPENDS_SEMANTICS) { \ | |
352 | assert(PASS1); \ | |
353 | set_regex_charset(&RExC_flags, REGEX_UNICODE_CHARSET); \ | |
354 | RExC_uni_semantics = 1; \ | |
355 | if (RExC_seen_unfolded_sharp_s) { \ | |
356 | *flagp |= RESTART_PASS1; \ | |
357 | return restart_retval; \ | |
358 | } \ | |
359 | } \ | |
360 | } STMT_END | |
361 | ||
fd7fc6ae YO |
362 | /* Executes a return statement with the value 'X', if 'flags' contains any of |
363 | * 'RESTART_PASS1', 'NEED_UTF8', or 'extra'. If so, *flagp is set to those | |
364 | * flags */ | |
365 | #define RETURN_X_ON_RESTART_OR_FLAGS(X, flags, flagp, extra) \ | |
366 | STMT_START { \ | |
367 | if ((flags) & (RESTART_PASS1|NEED_UTF8|(extra))) { \ | |
368 | *(flagp) = (flags) & (RESTART_PASS1|NEED_UTF8|(extra)); \ | |
369 | return X; \ | |
370 | } \ | |
371 | } STMT_END | |
372 | ||
373 | #define RETURN_NULL_ON_RESTART_OR_FLAGS(flags,flagp,extra) \ | |
374 | RETURN_X_ON_RESTART_OR_FLAGS(NULL,flags,flagp,extra) | |
375 | ||
376 | #define RETURN_X_ON_RESTART(X, flags,flagp) \ | |
377 | RETURN_X_ON_RESTART_OR_FLAGS( X, flags, flagp, 0) | |
378 | ||
379 | ||
380 | #define RETURN_NULL_ON_RESTART_FLAGP_OR_FLAGS(flagp,extra) \ | |
381 | if (*(flagp) & (RESTART_PASS1|(extra))) return NULL | |
382 | ||
383 | #define MUST_RESTART(flags) ((flags) & (RESTART_PASS1)) | |
384 | ||
385 | #define RETURN_NULL_ON_RESTART(flags,flagp) \ | |
386 | RETURN_X_ON_RESTART(NULL, flags,flagp) | |
387 | #define RETURN_NULL_ON_RESTART_FLAGP(flagp) \ | |
388 | RETURN_NULL_ON_RESTART_FLAGP_OR_FLAGS(flagp,0) | |
389 | ||
f19b1a63 KW |
390 | /* This converts the named class defined in regcomp.h to its equivalent class |
391 | * number defined in handy.h. */ | |
392 | #define namedclass_to_classnum(class) ((int) ((class) / 2)) | |
393 | #define classnum_to_namedclass(classnum) ((classnum) * 2) | |
394 | ||
de92f5e6 KW |
395 | #define _invlist_union_complement_2nd(a, b, output) \ |
396 | _invlist_union_maybe_complement_2nd(a, b, TRUE, output) | |
397 | #define _invlist_intersection_complement_2nd(a, b, output) \ | |
398 | _invlist_intersection_maybe_complement_2nd(a, b, TRUE, output) | |
399 | ||
1de06328 YO |
400 | /* About scan_data_t. |
401 | ||
402 | During optimisation we recurse through the regexp program performing | |
403 | various inplace (keyhole style) optimisations. In addition study_chunk | |
404 | and scan_commit populate this data structure with information about | |
538e84ed | 405 | what strings MUST appear in the pattern. We look for the longest |
3b753521 | 406 | string that must appear at a fixed location, and we look for the |
1de06328 YO |
407 | longest string that may appear at a floating location. So for instance |
408 | in the pattern: | |
538e84ed | 409 | |
1de06328 | 410 | /FOO[xX]A.*B[xX]BAR/ |
538e84ed | 411 | |
1de06328 YO |
412 | Both 'FOO' and 'A' are fixed strings. Both 'B' and 'BAR' are floating |
413 | strings (because they follow a .* construct). study_chunk will identify | |
414 | both FOO and BAR as being the longest fixed and floating strings respectively. | |
538e84ed | 415 | |
1de06328 | 416 | The strings can be composites, for instance |
538e84ed | 417 | |
1de06328 | 418 | /(f)(o)(o)/ |
538e84ed | 419 | |
1de06328 | 420 | will result in a composite fixed substring 'foo'. |
538e84ed | 421 | |
1de06328 | 422 | For each string some basic information is maintained: |
538e84ed | 423 | |
6ea77169 | 424 | - min_offset |
1de06328 YO |
425 | This is the position the string must appear at, or not before. |
426 | It also implicitly (when combined with minlenp) tells us how many | |
3b753521 FN |
427 | characters must match before the string we are searching for. |
428 | Likewise when combined with minlenp and the length of the string it | |
538e84ed | 429 | tells us how many characters must appear after the string we have |
1de06328 | 430 | found. |
538e84ed | 431 | |
1de06328 YO |
432 | - max_offset |
433 | Only used for floating strings. This is the rightmost point that | |
ea3daa5d | 434 | the string can appear at. If set to SSize_t_MAX it indicates that the |
1de06328 | 435 | string can occur infinitely far to the right. |
6e12f832 | 436 | For fixed strings, it is equal to min_offset. |
538e84ed | 437 | |
1de06328 | 438 | - minlenp |
2d608413 KW |
439 | A pointer to the minimum number of characters of the pattern that the |
440 | string was found inside. This is important as in the case of positive | |
538e84ed | 441 | lookahead or positive lookbehind we can have multiple patterns |
1de06328 | 442 | involved. Consider |
538e84ed | 443 | |
1de06328 | 444 | /(?=FOO).*F/ |
538e84ed | 445 | |
1de06328 YO |
446 | The minimum length of the pattern overall is 3, the minimum length |
447 | of the lookahead part is 3, but the minimum length of the part that | |
538e84ed | 448 | will actually match is 1. So 'FOO's minimum length is 3, but the |
1de06328 | 449 | minimum length for the F is 1. This is important as the minimum length |
538e84ed | 450 | is used to determine offsets in front of and behind the string being |
1de06328 | 451 | looked for. Since strings can be composites this is the length of the |
486ec47a | 452 | pattern at the time it was committed with a scan_commit. Note that |
1de06328 | 453 | the length is calculated by study_chunk, so that the minimum lengths |
538e84ed | 454 | are not known until the full pattern has been compiled, thus the |
1de06328 | 455 | pointer to the value. |
538e84ed | 456 | |
1de06328 | 457 | - lookbehind |
538e84ed | 458 | |
1de06328 | 459 | In the case of lookbehind the string being searched for can be |
538e84ed | 460 | offset past the start point of the final matching string. |
1de06328 YO |
461 | If this value was just blithely removed from the min_offset it would |
462 | invalidate some of the calculations for how many chars must match | |
463 | before or after (as they are derived from min_offset and minlen and | |
538e84ed | 464 | the length of the string being searched for). |
1de06328 YO |
465 | When the final pattern is compiled and the data is moved from the |
466 | scan_data_t structure into the regexp structure the information | |
538e84ed KW |
467 | about lookbehind is factored in, with the information that would |
468 | have been lost precalculated in the end_shift field for the | |
1de06328 YO |
469 | associated string. |
470 | ||
471 | The fields pos_min and pos_delta are used to store the minimum offset | |
538e84ed | 472 | and the delta to the maximum offset at the current point in the pattern. |
1de06328 YO |
473 | |
474 | */ | |
2c2d71f5 | 475 | |
cb6aef8b DM |
476 | struct scan_data_substrs { |
477 | SV *str; /* longest substring found in pattern */ | |
478 | SSize_t min_offset; /* earliest point in string it can appear */ | |
479 | SSize_t max_offset; /* latest point in string it can appear */ | |
480 | SSize_t *minlenp; /* pointer to the minlen relevant to the string */ | |
481 | SSize_t lookbehind; /* is the pos of the string modified by LB */ | |
11683ecb | 482 | I32 flags; /* per substring SF_* and SCF_* flags */ |
cb6aef8b DM |
483 | }; |
484 | ||
2c2d71f5 | 485 | typedef struct scan_data_t { |
1de06328 YO |
486 | /*I32 len_min; unused */ |
487 | /*I32 len_delta; unused */ | |
49f55535 | 488 | SSize_t pos_min; |
ea3daa5d | 489 | SSize_t pos_delta; |
2c2d71f5 | 490 | SV *last_found; |
ea3daa5d | 491 | SSize_t last_end; /* min value, <0 unless valid. */ |
49f55535 | 492 | SSize_t last_start_min; |
ea3daa5d | 493 | SSize_t last_start_max; |
2099df82 DM |
494 | U8 cur_is_floating; /* whether the last_* values should be set as |
495 | * the next fixed (0) or floating (1) | |
496 | * substring */ | |
6ea77169 | 497 | |
2099df82 DM |
498 | /* [0] is longest fixed substring so far, [1] is longest float so far */ |
499 | struct scan_data_substrs substrs[2]; | |
6ea77169 | 500 | |
11683ecb | 501 | I32 flags; /* common SF_* and SCF_* flags */ |
2c2d71f5 | 502 | I32 whilem_c; |
49f55535 | 503 | SSize_t *last_closep; |
b8f7bb16 | 504 | regnode_ssc *start_class; |
2c2d71f5 JH |
505 | } scan_data_t; |
506 | ||
a687059c | 507 | /* |
e50aee73 | 508 | * Forward declarations for pregcomp()'s friends. |
a687059c | 509 | */ |
a0d0e21e | 510 | |
6ea77169 | 511 | static const scan_data_t zero_scan_data = { |
a2ca2017 | 512 | 0, 0, NULL, 0, 0, 0, 0, |
6ea77169 | 513 | { |
11683ecb DM |
514 | { NULL, 0, 0, 0, 0, 0 }, |
515 | { NULL, 0, 0, 0, 0, 0 }, | |
6ea77169 DM |
516 | }, |
517 | 0, 0, NULL, NULL | |
518 | }; | |
c277df42 | 519 | |
11683ecb DM |
520 | /* study flags */ |
521 | ||
07be1b83 YO |
522 | #define SF_BEFORE_SEOL 0x0001 |
523 | #define SF_BEFORE_MEOL 0x0002 | |
11683ecb | 524 | #define SF_BEFORE_EOL (SF_BEFORE_SEOL|SF_BEFORE_MEOL) |
c277df42 | 525 | |
07be1b83 YO |
526 | #define SF_IS_INF 0x0040 |
527 | #define SF_HAS_PAR 0x0080 | |
528 | #define SF_IN_PAR 0x0100 | |
529 | #define SF_HAS_EVAL 0x0200 | |
bc604ad8 KW |
530 | |
531 | ||
532 | /* SCF_DO_SUBSTR is the flag that tells the regexp analyzer to track the | |
533 | * longest substring in the pattern. When it is not set the optimiser keeps | |
534 | * track of position, but does not keep track of the actual strings seen, | |
535 | * | |
536 | * So for instance /foo/ will be parsed with SCF_DO_SUBSTR being true, but | |
537 | * /foo/i will not. | |
538 | * | |
539 | * Similarly, /foo.*(blah|erm|huh).*fnorble/ will have "foo" and "fnorble" | |
540 | * parsed with SCF_DO_SUBSTR on, but while processing the (...) it will be | |
541 | * turned off because of the alternation (BRANCH). */ | |
07be1b83 | 542 | #define SCF_DO_SUBSTR 0x0400 |
bc604ad8 | 543 | |
653099ff GS |
544 | #define SCF_DO_STCLASS_AND 0x0800 |
545 | #define SCF_DO_STCLASS_OR 0x1000 | |
546 | #define SCF_DO_STCLASS (SCF_DO_STCLASS_AND|SCF_DO_STCLASS_OR) | |
e1901655 | 547 | #define SCF_WHILEM_VISITED_POS 0x2000 |
c277df42 | 548 | |
786e8c11 | 549 | #define SCF_TRIE_RESTUDY 0x4000 /* Do restudy? */ |
538e84ed | 550 | #define SCF_SEEN_ACCEPT 0x8000 |
688e0391 | 551 | #define SCF_TRIE_DOING_RESTUDY 0x10000 |
4286711a YO |
552 | #define SCF_IN_DEFINE 0x20000 |
553 | ||
554 | ||
555 | ||
07be1b83 | 556 | |
43fead97 | 557 | #define UTF cBOOL(RExC_utf8) |
00b27cfc KW |
558 | |
559 | /* The enums for all these are ordered so things work out correctly */ | |
a62b1201 | 560 | #define LOC (get_regex_charset(RExC_flags) == REGEX_LOCALE_CHARSET) |
538e84ed KW |
561 | #define DEPENDS_SEMANTICS (get_regex_charset(RExC_flags) \ |
562 | == REGEX_DEPENDS_CHARSET) | |
00b27cfc | 563 | #define UNI_SEMANTICS (get_regex_charset(RExC_flags) == REGEX_UNICODE_CHARSET) |
538e84ed KW |
564 | #define AT_LEAST_UNI_SEMANTICS (get_regex_charset(RExC_flags) \ |
565 | >= REGEX_UNICODE_CHARSET) | |
566 | #define ASCII_RESTRICTED (get_regex_charset(RExC_flags) \ | |
567 | == REGEX_ASCII_RESTRICTED_CHARSET) | |
568 | #define AT_LEAST_ASCII_RESTRICTED (get_regex_charset(RExC_flags) \ | |
569 | >= REGEX_ASCII_RESTRICTED_CHARSET) | |
570 | #define ASCII_FOLD_RESTRICTED (get_regex_charset(RExC_flags) \ | |
571 | == REGEX_ASCII_MORE_RESTRICTED_CHARSET) | |
a62b1201 | 572 | |
43fead97 | 573 | #define FOLD cBOOL(RExC_flags & RXf_PMf_FOLD) |
a0ed51b3 | 574 | |
f2c2a6ab KW |
575 | /* For programs that want to be strictly Unicode compatible by dying if any |
576 | * attempt is made to match a non-Unicode code point against a Unicode | |
577 | * property. */ | |
578 | #define ALWAYS_WARN_SUPER ckDEAD(packWARN(WARN_NON_UNICODE)) | |
579 | ||
93733859 | 580 | #define OOB_NAMEDCLASS -1 |
b8c5462f | 581 | |
8e661ac5 KW |
582 | /* There is no code point that is out-of-bounds, so this is problematic. But |
583 | * its only current use is to initialize a variable that is always set before | |
584 | * looked at. */ | |
585 | #define OOB_UNICODE 0xDEADBEEF | |
586 | ||
a0ed51b3 | 587 | #define CHR_SVLEN(sv) (UTF ? sv_len_utf8(sv) : SvCUR(sv)) |
a0ed51b3 | 588 | |
8615cb43 | 589 | |
b45f050a JF |
590 | /* length of regex to show in messages that don't mark a position within */ |
591 | #define RegexLengthToShowInErrorMessages 127 | |
592 | ||
593 | /* | |
594 | * If MARKER[12] are adjusted, be sure to adjust the constants at the top | |
595 | * of t/op/regmesg.t, the tests in t/op/re_tests, and those in | |
596 | * op/pragma/warn/regcomp. | |
597 | */ | |
7253e4e3 RK |
598 | #define MARKER1 "<-- HERE" /* marker as it appears in the description */ |
599 | #define MARKER2 " <-- HERE " /* marker as it appears within the regex */ | |
b81d288d | 600 | |
538e84ed | 601 | #define REPORT_LOCATION " in regex; marked by " MARKER1 \ |
147e3846 | 602 | " in m/%" UTF8f MARKER2 "%" UTF8f "/" |
b45f050a | 603 | |
285b5ca0 KW |
604 | /* The code in this file in places uses one level of recursion with parsing |
605 | * rebased to an alternate string constructed by us in memory. This can take | |
606 | * the form of something that is completely different from the input, or | |
607 | * something that uses the input as part of the alternate. In the first case, | |
608 | * there should be no possibility of an error, as we are in complete control of | |
609 | * the alternate string. But in the second case we don't control the input | |
610 | * portion, so there may be errors in that. Here's an example: | |
611 | * /[abc\x{DF}def]/ui | |
612 | * is handled specially because \x{df} folds to a sequence of more than one | |
613 | * character, 'ss'. What is done is to create and parse an alternate string, | |
614 | * which looks like this: | |
615 | * /(?:\x{DF}|[abc\x{DF}def])/ui | |
616 | * where it uses the input unchanged in the middle of something it constructs, | |
617 | * which is a branch for the DF outside the character class, and clustering | |
618 | * parens around the whole thing. (It knows enough to skip the DF inside the | |
619 | * class while in this substitute parse.) 'abc' and 'def' may have errors that | |
620 | * need to be reported. The general situation looks like this: | |
621 | * | |
622 | * sI tI xI eI | |
623 | * Input: ---------------------------------------------------- | |
624 | * Constructed: --------------------------------------------------- | |
625 | * sC tC xC eC EC | |
626 | * | |
627 | * The input string sI..eI is the input pattern. The string sC..EC is the | |
628 | * constructed substitute parse string. The portions sC..tC and eC..EC are | |
629 | * constructed by us. The portion tC..eC is an exact duplicate of the input | |
630 | * pattern tI..eI. In the diagram, these are vertically aligned. Suppose that | |
631 | * while parsing, we find an error at xC. We want to display a message showing | |
632 | * the real input string. Thus we need to find the point xI in it which | |
633 | * corresponds to xC. xC >= tC, since the portion of the string sC..tC has | |
634 | * been constructed by us, and so shouldn't have errors. We get: | |
635 | * | |
636 | * xI = sI + (tI - sI) + (xC - tC) | |
637 | * | |
638 | * and, the offset into sI is: | |
639 | * | |
640 | * (xI - sI) = (tI - sI) + (xC - tC) | |
641 | * | |
642 | * When the substitute is constructed, we save (tI -sI) as RExC_precomp_adj, | |
643 | * and we save tC as RExC_adjusted_start. | |
903c858a KW |
644 | * |
645 | * During normal processing of the input pattern, everything points to that, | |
646 | * with RExC_precomp_adj set to 0, and RExC_adjusted_start set to sI. | |
285b5ca0 KW |
647 | */ |
648 | ||
649 | #define tI_sI RExC_precomp_adj | |
650 | #define tC RExC_adjusted_start | |
651 | #define sC RExC_precomp | |
652 | #define xI_offset(xC) ((IV) (tI_sI + (xC - tC))) | |
653 | #define xI(xC) (sC + xI_offset(xC)) | |
654 | #define eC RExC_precomp_end | |
655 | ||
656 | #define REPORT_LOCATION_ARGS(xC) \ | |
657 | UTF8fARG(UTF, \ | |
658 | (xI(xC) > eC) /* Don't run off end */ \ | |
659 | ? eC - sC /* Length before the <--HERE */ \ | |
bc929b61 KW |
660 | : ((xI_offset(xC) >= 0) \ |
661 | ? xI_offset(xC) \ | |
662 | : (Perl_croak(aTHX_ "panic: %s: %d: negative offset: %" \ | |
663 | IVdf " trying to output message for " \ | |
664 | " pattern %.*s", \ | |
665 | __FILE__, __LINE__, xI_offset(xC), \ | |
666 | ((int) (eC - sC)), sC), 0)), \ | |
285b5ca0 KW |
667 | sC), /* The input pattern printed up to the <--HERE */ \ |
668 | UTF8fARG(UTF, \ | |
669 | (xI(xC) > eC) ? 0 : eC - xI(xC), /* Length after <--HERE */ \ | |
670 | (xI(xC) > eC) ? eC : xI(xC)) /* pattern after <--HERE */ | |
c1d900c3 | 671 | |
8a6d8ec6 HS |
672 | /* Used to point after bad bytes for an error message, but avoid skipping |
673 | * past a nul byte. */ | |
674 | #define SKIP_IF_CHAR(s) (!*(s) ? 0 : UTF ? UTF8SKIP(s) : 1) | |
675 | ||
b45f050a JF |
676 | /* |
677 | * Calls SAVEDESTRUCTOR_X if needed, then calls Perl_croak with the given | |
678 | * arg. Show regex, up to a maximum length. If it's too long, chop and add | |
679 | * "...". | |
680 | */ | |
58e23c8d | 681 | #define _FAIL(code) STMT_START { \ |
bfed75c6 | 682 | const char *ellipses = ""; \ |
711b303b | 683 | IV len = RExC_precomp_end - RExC_precomp; \ |
ccb2c380 MP |
684 | \ |
685 | if (!SIZE_ONLY) \ | |
a5e7bc51 | 686 | SAVEFREESV(RExC_rx_sv); \ |
ccb2c380 MP |
687 | if (len > RegexLengthToShowInErrorMessages) { \ |
688 | /* chop 10 shorter than the max, to ensure meaning of "..." */ \ | |
689 | len = RegexLengthToShowInErrorMessages - 10; \ | |
690 | ellipses = "..."; \ | |
691 | } \ | |
58e23c8d | 692 | code; \ |
ccb2c380 | 693 | } STMT_END |
8615cb43 | 694 | |
58e23c8d | 695 | #define FAIL(msg) _FAIL( \ |
147e3846 | 696 | Perl_croak(aTHX_ "%s in regex m/%" UTF8f "%s/", \ |
c1d900c3 | 697 | msg, UTF8fARG(UTF, len, RExC_precomp), ellipses)) |
58e23c8d YO |
698 | |
699 | #define FAIL2(msg,arg) _FAIL( \ | |
147e3846 | 700 | Perl_croak(aTHX_ msg " in regex m/%" UTF8f "%s/", \ |
c1d900c3 | 701 | arg, UTF8fARG(UTF, len, RExC_precomp), ellipses)) |
58e23c8d | 702 | |
b45f050a | 703 | /* |
b45f050a JF |
704 | * Simple_vFAIL -- like FAIL, but marks the current location in the scan |
705 | */ | |
ccb2c380 | 706 | #define Simple_vFAIL(m) STMT_START { \ |
ccb2c380 | 707 | Perl_croak(aTHX_ "%s" REPORT_LOCATION, \ |
d528642a | 708 | m, REPORT_LOCATION_ARGS(RExC_parse)); \ |
ccb2c380 | 709 | } STMT_END |
b45f050a JF |
710 | |
711 | /* | |
712 | * Calls SAVEDESTRUCTOR_X if needed, then Simple_vFAIL() | |
713 | */ | |
ccb2c380 MP |
714 | #define vFAIL(m) STMT_START { \ |
715 | if (!SIZE_ONLY) \ | |
a5e7bc51 | 716 | SAVEFREESV(RExC_rx_sv); \ |
ccb2c380 MP |
717 | Simple_vFAIL(m); \ |
718 | } STMT_END | |
b45f050a JF |
719 | |
720 | /* | |
721 | * Like Simple_vFAIL(), but accepts two arguments. | |
722 | */ | |
ccb2c380 | 723 | #define Simple_vFAIL2(m,a1) STMT_START { \ |
d528642a KW |
724 | S_re_croak2(aTHX_ UTF, m, REPORT_LOCATION, a1, \ |
725 | REPORT_LOCATION_ARGS(RExC_parse)); \ | |
ccb2c380 | 726 | } STMT_END |
b45f050a JF |
727 | |
728 | /* | |
729 | * Calls SAVEDESTRUCTOR_X if needed, then Simple_vFAIL2(). | |
730 | */ | |
ccb2c380 MP |
731 | #define vFAIL2(m,a1) STMT_START { \ |
732 | if (!SIZE_ONLY) \ | |
a5e7bc51 | 733 | SAVEFREESV(RExC_rx_sv); \ |
ccb2c380 MP |
734 | Simple_vFAIL2(m, a1); \ |
735 | } STMT_END | |
b45f050a JF |
736 | |
737 | ||
738 | /* | |
739 | * Like Simple_vFAIL(), but accepts three arguments. | |
740 | */ | |
ccb2c380 | 741 | #define Simple_vFAIL3(m, a1, a2) STMT_START { \ |
c1d900c3 | 742 | S_re_croak2(aTHX_ UTF, m, REPORT_LOCATION, a1, a2, \ |
d528642a | 743 | REPORT_LOCATION_ARGS(RExC_parse)); \ |
ccb2c380 | 744 | } STMT_END |
b45f050a JF |
745 | |
746 | /* | |
747 | * Calls SAVEDESTRUCTOR_X if needed, then Simple_vFAIL3(). | |
748 | */ | |
ccb2c380 MP |
749 | #define vFAIL3(m,a1,a2) STMT_START { \ |
750 | if (!SIZE_ONLY) \ | |
a5e7bc51 | 751 | SAVEFREESV(RExC_rx_sv); \ |
ccb2c380 MP |
752 | Simple_vFAIL3(m, a1, a2); \ |
753 | } STMT_END | |
b45f050a JF |
754 | |
755 | /* | |
756 | * Like Simple_vFAIL(), but accepts four arguments. | |
757 | */ | |
ccb2c380 | 758 | #define Simple_vFAIL4(m, a1, a2, a3) STMT_START { \ |
d528642a KW |
759 | S_re_croak2(aTHX_ UTF, m, REPORT_LOCATION, a1, a2, a3, \ |
760 | REPORT_LOCATION_ARGS(RExC_parse)); \ | |
ccb2c380 | 761 | } STMT_END |
b45f050a | 762 | |
95db3ffa KW |
763 | #define vFAIL4(m,a1,a2,a3) STMT_START { \ |
764 | if (!SIZE_ONLY) \ | |
765 | SAVEFREESV(RExC_rx_sv); \ | |
766 | Simple_vFAIL4(m, a1, a2, a3); \ | |
767 | } STMT_END | |
768 | ||
946095af | 769 | /* A specialized version of vFAIL2 that works with UTF8f */ |
d528642a KW |
770 | #define vFAIL2utf8f(m, a1) STMT_START { \ |
771 | if (!SIZE_ONLY) \ | |
772 | SAVEFREESV(RExC_rx_sv); \ | |
773 | S_re_croak2(aTHX_ UTF, m, REPORT_LOCATION, a1, \ | |
774 | REPORT_LOCATION_ARGS(RExC_parse)); \ | |
946095af BF |
775 | } STMT_END |
776 | ||
3ba22297 | 777 | #define vFAIL3utf8f(m, a1, a2) STMT_START { \ |
3ba22297 KW |
778 | if (!SIZE_ONLY) \ |
779 | SAVEFREESV(RExC_rx_sv); \ | |
780 | S_re_croak2(aTHX_ UTF, m, REPORT_LOCATION, a1, a2, \ | |
d528642a | 781 | REPORT_LOCATION_ARGS(RExC_parse)); \ |
3ba22297 KW |
782 | } STMT_END |
783 | ||
499333dc KW |
784 | /* These have asserts in them because of [perl #122671] Many warnings in |
785 | * regcomp.c can occur twice. If they get output in pass1 and later in that | |
786 | * pass, the pattern has to be converted to UTF-8 and the pass restarted, they | |
787 | * would get output again. So they should be output in pass2, and these | |
788 | * asserts make sure new warnings follow that paradigm. */ | |
946095af | 789 | |
5e0a247b KW |
790 | /* m is not necessarily a "literal string", in this macro */ |
791 | #define reg_warn_non_literal_string(loc, m) STMT_START { \ | |
d528642a KW |
792 | __ASSERT_(PASS2) Perl_warner(aTHX_ packWARN(WARN_REGEXP), \ |
793 | "%s" REPORT_LOCATION, \ | |
794 | m, REPORT_LOCATION_ARGS(loc)); \ | |
5e0a247b KW |
795 | } STMT_END |
796 | ||
668c081a | 797 | #define ckWARNreg(loc,m) STMT_START { \ |
d528642a KW |
798 | __ASSERT_(PASS2) Perl_ck_warner(aTHX_ packWARN(WARN_REGEXP), \ |
799 | m REPORT_LOCATION, \ | |
800 | REPORT_LOCATION_ARGS(loc)); \ | |
ccb2c380 MP |
801 | } STMT_END |
802 | ||
b927b7e9 | 803 | #define vWARN(loc, m) STMT_START { \ |
d528642a KW |
804 | __ASSERT_(PASS2) Perl_warner(aTHX_ packWARN(WARN_REGEXP), \ |
805 | m REPORT_LOCATION, \ | |
806 | REPORT_LOCATION_ARGS(loc)); \ | |
b927b7e9 KW |
807 | } STMT_END |
808 | ||
0d6106aa | 809 | #define vWARN_dep(loc, m) STMT_START { \ |
d528642a KW |
810 | __ASSERT_(PASS2) Perl_warner(aTHX_ packWARN(WARN_DEPRECATED), \ |
811 | m REPORT_LOCATION, \ | |
812 | REPORT_LOCATION_ARGS(loc)); \ | |
0d6106aa KW |
813 | } STMT_END |
814 | ||
147508a2 | 815 | #define ckWARNdep(loc,m) STMT_START { \ |
d528642a KW |
816 | __ASSERT_(PASS2) Perl_ck_warner_d(aTHX_ packWARN(WARN_DEPRECATED), \ |
817 | m REPORT_LOCATION, \ | |
818 | REPORT_LOCATION_ARGS(loc)); \ | |
147508a2 KW |
819 | } STMT_END |
820 | ||
d528642a KW |
821 | #define ckWARNregdep(loc,m) STMT_START { \ |
822 | __ASSERT_(PASS2) Perl_ck_warner_d(aTHX_ packWARN2(WARN_DEPRECATED, \ | |
823 | WARN_REGEXP), \ | |
824 | m REPORT_LOCATION, \ | |
825 | REPORT_LOCATION_ARGS(loc)); \ | |
ccb2c380 MP |
826 | } STMT_END |
827 | ||
d528642a KW |
828 | #define ckWARN2reg_d(loc,m, a1) STMT_START { \ |
829 | __ASSERT_(PASS2) Perl_ck_warner_d(aTHX_ packWARN(WARN_REGEXP), \ | |
830 | m REPORT_LOCATION, \ | |
831 | a1, REPORT_LOCATION_ARGS(loc)); \ | |
2335b3d3 KW |
832 | } STMT_END |
833 | ||
d528642a KW |
834 | #define ckWARN2reg(loc, m, a1) STMT_START { \ |
835 | __ASSERT_(PASS2) Perl_ck_warner(aTHX_ packWARN(WARN_REGEXP), \ | |
836 | m REPORT_LOCATION, \ | |
837 | a1, REPORT_LOCATION_ARGS(loc)); \ | |
ccb2c380 MP |
838 | } STMT_END |
839 | ||
d528642a KW |
840 | #define vWARN3(loc, m, a1, a2) STMT_START { \ |
841 | __ASSERT_(PASS2) Perl_warner(aTHX_ packWARN(WARN_REGEXP), \ | |
842 | m REPORT_LOCATION, \ | |
843 | a1, a2, REPORT_LOCATION_ARGS(loc)); \ | |
ccb2c380 MP |
844 | } STMT_END |
845 | ||
d528642a KW |
846 | #define ckWARN3reg(loc, m, a1, a2) STMT_START { \ |
847 | __ASSERT_(PASS2) Perl_ck_warner(aTHX_ packWARN(WARN_REGEXP), \ | |
848 | m REPORT_LOCATION, \ | |
849 | a1, a2, \ | |
850 | REPORT_LOCATION_ARGS(loc)); \ | |
668c081a NC |
851 | } STMT_END |
852 | ||
ccb2c380 | 853 | #define vWARN4(loc, m, a1, a2, a3) STMT_START { \ |
d528642a KW |
854 | __ASSERT_(PASS2) Perl_warner(aTHX_ packWARN(WARN_REGEXP), \ |
855 | m REPORT_LOCATION, \ | |
856 | a1, a2, a3, \ | |
857 | REPORT_LOCATION_ARGS(loc)); \ | |
ccb2c380 MP |
858 | } STMT_END |
859 | ||
668c081a | 860 | #define ckWARN4reg(loc, m, a1, a2, a3) STMT_START { \ |
d528642a KW |
861 | __ASSERT_(PASS2) Perl_ck_warner(aTHX_ packWARN(WARN_REGEXP), \ |
862 | m REPORT_LOCATION, \ | |
863 | a1, a2, a3, \ | |
864 | REPORT_LOCATION_ARGS(loc)); \ | |
668c081a NC |
865 | } STMT_END |
866 | ||
ccb2c380 | 867 | #define vWARN5(loc, m, a1, a2, a3, a4) STMT_START { \ |
d528642a KW |
868 | __ASSERT_(PASS2) Perl_warner(aTHX_ packWARN(WARN_REGEXP), \ |
869 | m REPORT_LOCATION, \ | |
870 | a1, a2, a3, a4, \ | |
871 | REPORT_LOCATION_ARGS(loc)); \ | |
ccb2c380 | 872 | } STMT_END |
9d1d55b5 | 873 | |
538e84ed | 874 | /* Macros for recording node offsets. 20001227 mjd@plover.com |
fac92740 MJD |
875 | * Nodes are numbered 1, 2, 3, 4. Node #n's position is recorded in |
876 | * element 2*n-1 of the array. Element #2n holds the byte length node #n. | |
877 | * Element 0 holds the number n. | |
07be1b83 | 878 | * Position is 1 indexed. |
fac92740 | 879 | */ |
7122b237 YO |
880 | #ifndef RE_TRACK_PATTERN_OFFSETS |
881 | #define Set_Node_Offset_To_R(node,byte) | |
882 | #define Set_Node_Offset(node,byte) | |
883 | #define Set_Cur_Node_Offset | |
884 | #define Set_Node_Length_To_R(node,len) | |
885 | #define Set_Node_Length(node,len) | |
6a86c6ad | 886 | #define Set_Node_Cur_Length(node,start) |
538e84ed KW |
887 | #define Node_Offset(n) |
888 | #define Node_Length(n) | |
7122b237 YO |
889 | #define Set_Node_Offset_Length(node,offset,len) |
890 | #define ProgLen(ri) ri->u.proglen | |
891 | #define SetProgLen(ri,x) ri->u.proglen = x | |
892 | #else | |
893 | #define ProgLen(ri) ri->u.offsets[0] | |
894 | #define SetProgLen(ri,x) ri->u.offsets[0] = x | |
ccb2c380 MP |
895 | #define Set_Node_Offset_To_R(node,byte) STMT_START { \ |
896 | if (! SIZE_ONLY) { \ | |
897 | MJD_OFFSET_DEBUG(("** (%d) offset of node %d is %d.\n", \ | |
2a49f0f5 | 898 | __LINE__, (int)(node), (int)(byte))); \ |
ccb2c380 | 899 | if((node) < 0) { \ |
538e84ed KW |
900 | Perl_croak(aTHX_ "value of node is %d in Offset macro", \ |
901 | (int)(node)); \ | |
ccb2c380 MP |
902 | } else { \ |
903 | RExC_offsets[2*(node)-1] = (byte); \ | |
904 | } \ | |
905 | } \ | |
906 | } STMT_END | |
907 | ||
908 | #define Set_Node_Offset(node,byte) \ | |
909 | Set_Node_Offset_To_R((node)-RExC_emit_start, (byte)-RExC_start) | |
910 | #define Set_Cur_Node_Offset Set_Node_Offset(RExC_emit, RExC_parse) | |
911 | ||
912 | #define Set_Node_Length_To_R(node,len) STMT_START { \ | |
913 | if (! SIZE_ONLY) { \ | |
914 | MJD_OFFSET_DEBUG(("** (%d) size of node %d is %d.\n", \ | |
551405c4 | 915 | __LINE__, (int)(node), (int)(len))); \ |
ccb2c380 | 916 | if((node) < 0) { \ |
538e84ed KW |
917 | Perl_croak(aTHX_ "value of node is %d in Length macro", \ |
918 | (int)(node)); \ | |
ccb2c380 MP |
919 | } else { \ |
920 | RExC_offsets[2*(node)] = (len); \ | |
921 | } \ | |
922 | } \ | |
923 | } STMT_END | |
924 | ||
925 | #define Set_Node_Length(node,len) \ | |
926 | Set_Node_Length_To_R((node)-RExC_emit_start, len) | |
6a86c6ad NC |
927 | #define Set_Node_Cur_Length(node, start) \ |
928 | Set_Node_Length(node, RExC_parse - start) | |
fac92740 MJD |
929 | |
930 | /* Get offsets and lengths */ | |
931 | #define Node_Offset(n) (RExC_offsets[2*((n)-RExC_emit_start)-1]) | |
932 | #define Node_Length(n) (RExC_offsets[2*((n)-RExC_emit_start)]) | |
933 | ||
07be1b83 YO |
934 | #define Set_Node_Offset_Length(node,offset,len) STMT_START { \ |
935 | Set_Node_Offset_To_R((node)-RExC_emit_start, (offset)); \ | |
936 | Set_Node_Length_To_R((node)-RExC_emit_start, (len)); \ | |
937 | } STMT_END | |
7122b237 | 938 | #endif |
07be1b83 YO |
939 | |
940 | #if PERL_ENABLE_EXPERIMENTAL_REGEX_OPTIMISATIONS | |
941 | #define EXPERIMENTAL_INPLACESCAN | |
f427392e | 942 | #endif /*PERL_ENABLE_EXPERIMENTAL_REGEX_OPTIMISATIONS*/ |
07be1b83 | 943 | |
cb41e5d6 YO |
944 | #ifdef DEBUGGING |
945 | int | |
6ad9a8ab | 946 | Perl_re_printf(pTHX_ const char *fmt, ...) |
cb41e5d6 YO |
947 | { |
948 | va_list ap; | |
949 | int result; | |
950 | PerlIO *f= Perl_debug_log; | |
951 | PERL_ARGS_ASSERT_RE_PRINTF; | |
952 | va_start(ap, fmt); | |
953 | result = PerlIO_vprintf(f, fmt, ap); | |
954 | va_end(ap); | |
955 | return result; | |
956 | } | |
957 | ||
958 | int | |
7b031478 | 959 | Perl_re_indentf(pTHX_ const char *fmt, U32 depth, ...) |
cb41e5d6 YO |
960 | { |
961 | va_list ap; | |
962 | int result; | |
963 | PerlIO *f= Perl_debug_log; | |
964 | PERL_ARGS_ASSERT_RE_INDENTF; | |
965 | va_start(ap, depth); | |
daeb874b | 966 | PerlIO_printf(f, "%*s", ( (int)depth % 20 ) * 2, ""); |
cb41e5d6 YO |
967 | result = PerlIO_vprintf(f, fmt, ap); |
968 | va_end(ap); | |
969 | return result; | |
970 | } | |
971 | #endif /* DEBUGGING */ | |
972 | ||
7b031478 | 973 | #define DEBUG_RExC_seen() \ |
538e84ed | 974 | DEBUG_OPTIMISE_MORE_r({ \ |
6ad9a8ab | 975 | Perl_re_printf( aTHX_ "RExC_seen: "); \ |
538e84ed | 976 | \ |
e384d5c1 | 977 | if (RExC_seen & REG_ZERO_LEN_SEEN) \ |
6ad9a8ab | 978 | Perl_re_printf( aTHX_ "REG_ZERO_LEN_SEEN "); \ |
538e84ed | 979 | \ |
e384d5c1 | 980 | if (RExC_seen & REG_LOOKBEHIND_SEEN) \ |
6ad9a8ab | 981 | Perl_re_printf( aTHX_ "REG_LOOKBEHIND_SEEN "); \ |
538e84ed | 982 | \ |
e384d5c1 | 983 | if (RExC_seen & REG_GPOS_SEEN) \ |
6ad9a8ab | 984 | Perl_re_printf( aTHX_ "REG_GPOS_SEEN "); \ |
538e84ed | 985 | \ |
e384d5c1 | 986 | if (RExC_seen & REG_RECURSE_SEEN) \ |
6ad9a8ab | 987 | Perl_re_printf( aTHX_ "REG_RECURSE_SEEN "); \ |
538e84ed | 988 | \ |
7b031478 | 989 | if (RExC_seen & REG_TOP_LEVEL_BRANCHES_SEEN) \ |
6ad9a8ab | 990 | Perl_re_printf( aTHX_ "REG_TOP_LEVEL_BRANCHES_SEEN "); \ |
538e84ed | 991 | \ |
e384d5c1 | 992 | if (RExC_seen & REG_VERBARG_SEEN) \ |
6ad9a8ab | 993 | Perl_re_printf( aTHX_ "REG_VERBARG_SEEN "); \ |
538e84ed | 994 | \ |
e384d5c1 | 995 | if (RExC_seen & REG_CUTGROUP_SEEN) \ |
6ad9a8ab | 996 | Perl_re_printf( aTHX_ "REG_CUTGROUP_SEEN "); \ |
538e84ed | 997 | \ |
e384d5c1 | 998 | if (RExC_seen & REG_RUN_ON_COMMENT_SEEN) \ |
6ad9a8ab | 999 | Perl_re_printf( aTHX_ "REG_RUN_ON_COMMENT_SEEN "); \ |
538e84ed | 1000 | \ |
e384d5c1 | 1001 | if (RExC_seen & REG_UNFOLDED_MULTI_SEEN) \ |
6ad9a8ab | 1002 | Perl_re_printf( aTHX_ "REG_UNFOLDED_MULTI_SEEN "); \ |
538e84ed | 1003 | \ |
7b031478 | 1004 | if (RExC_seen & REG_UNBOUNDED_QUANTIFIER_SEEN) \ |
6ad9a8ab | 1005 | Perl_re_printf( aTHX_ "REG_UNBOUNDED_QUANTIFIER_SEEN "); \ |
ee273784 | 1006 | \ |
6ad9a8ab | 1007 | Perl_re_printf( aTHX_ "\n"); \ |
9e9ecfdf YO |
1008 | }); |
1009 | ||
fdfb4f21 | 1010 | #define DEBUG_SHOW_STUDY_FLAG(flags,flag) \ |
6ad9a8ab | 1011 | if ((flags) & flag) Perl_re_printf( aTHX_ "%s ", #flag) |
fdfb4f21 | 1012 | |
fdfb4f21 | 1013 | |
f5a36d78 DM |
1014 | #ifdef DEBUGGING |
1015 | static void | |
1016 | S_debug_show_study_flags(pTHX_ U32 flags, const char *open_str, | |
1017 | const char *close_str) | |
1018 | { | |
1019 | if (!flags) | |
1020 | return; | |
1021 | ||
1022 | Perl_re_printf( aTHX_ "%s", open_str); | |
11683ecb DM |
1023 | DEBUG_SHOW_STUDY_FLAG(flags, SF_BEFORE_SEOL); |
1024 | DEBUG_SHOW_STUDY_FLAG(flags, SF_BEFORE_MEOL); | |
f5a36d78 DM |
1025 | DEBUG_SHOW_STUDY_FLAG(flags, SF_IS_INF); |
1026 | DEBUG_SHOW_STUDY_FLAG(flags, SF_HAS_PAR); | |
1027 | DEBUG_SHOW_STUDY_FLAG(flags, SF_IN_PAR); | |
1028 | DEBUG_SHOW_STUDY_FLAG(flags, SF_HAS_EVAL); | |
1029 | DEBUG_SHOW_STUDY_FLAG(flags, SCF_DO_SUBSTR); | |
1030 | DEBUG_SHOW_STUDY_FLAG(flags, SCF_DO_STCLASS_AND); | |
1031 | DEBUG_SHOW_STUDY_FLAG(flags, SCF_DO_STCLASS_OR); | |
1032 | DEBUG_SHOW_STUDY_FLAG(flags, SCF_DO_STCLASS); | |
1033 | DEBUG_SHOW_STUDY_FLAG(flags, SCF_WHILEM_VISITED_POS); | |
1034 | DEBUG_SHOW_STUDY_FLAG(flags, SCF_TRIE_RESTUDY); | |
1035 | DEBUG_SHOW_STUDY_FLAG(flags, SCF_SEEN_ACCEPT); | |
1036 | DEBUG_SHOW_STUDY_FLAG(flags, SCF_TRIE_DOING_RESTUDY); | |
1037 | DEBUG_SHOW_STUDY_FLAG(flags, SCF_IN_DEFINE); | |
1038 | Perl_re_printf( aTHX_ "%s", close_str); | |
1039 | } | |
1040 | ||
1041 | ||
1042 | static void | |
1043 | S_debug_studydata(pTHX_ const char *where, scan_data_t *data, | |
1044 | U32 depth, int is_inf) | |
1045 | { | |
1046 | GET_RE_DEBUG_FLAGS_DECL; | |
1047 | ||
1048 | DEBUG_OPTIMISE_MORE_r({ | |
1049 | if (!data) | |
1050 | return; | |
1051 | Perl_re_indentf(aTHX_ "%s: Pos:%" IVdf "/%" IVdf " Flags: 0x%" UVXf, | |
1052 | depth, | |
1053 | where, | |
1054 | (IV)data->pos_min, | |
1055 | (IV)data->pos_delta, | |
1056 | (UV)data->flags | |
1057 | ); | |
1058 | ||
1059 | S_debug_show_study_flags(aTHX_ data->flags," [","]"); | |
fdfb4f21 | 1060 | |
f5a36d78 DM |
1061 | Perl_re_printf( aTHX_ |
1062 | " Whilem_c: %" IVdf " Lcp: %" IVdf " %s", | |
1063 | (IV)data->whilem_c, | |
1064 | (IV)(data->last_closep ? *((data)->last_closep) : -1), | |
1065 | is_inf ? "INF " : "" | |
1066 | ); | |
1067 | ||
11683ecb | 1068 | if (data->last_found) { |
37b6262f | 1069 | int i; |
11683ecb DM |
1070 | Perl_re_printf(aTHX_ |
1071 | "Last:'%s' %" IVdf ":%" IVdf "/%" IVdf, | |
1072 | SvPVX_const(data->last_found), | |
1073 | (IV)data->last_end, | |
1074 | (IV)data->last_start_min, | |
1075 | (IV)data->last_start_max | |
1076 | ); | |
1077 | ||
2099df82 | 1078 | for (i = 0; i < 2; i++) { |
37b6262f DM |
1079 | Perl_re_printf(aTHX_ |
1080 | " %s%s: '%s' @ %" IVdf "/%" IVdf, | |
2099df82 DM |
1081 | data->cur_is_floating == i ? "*" : "", |
1082 | i ? "Float" : "Fixed", | |
37b6262f DM |
1083 | SvPVX_const(data->substrs[i].str), |
1084 | (IV)data->substrs[i].min_offset, | |
1085 | (IV)data->substrs[i].max_offset | |
1086 | ); | |
1087 | S_debug_show_study_flags(aTHX_ data->substrs[i].flags," [","]"); | |
1088 | } | |
11683ecb | 1089 | } |
f5a36d78 DM |
1090 | |
1091 | Perl_re_printf( aTHX_ "\n"); | |
1092 | }); | |
1093 | } | |
1094 | ||
1095 | ||
1096 | static void | |
1097 | S_debug_peep(pTHX_ const char *str, const RExC_state_t *pRExC_state, | |
1098 | regnode *scan, U32 depth, U32 flags) | |
1099 | { | |
1100 | GET_RE_DEBUG_FLAGS_DECL; | |
1101 | ||
1102 | DEBUG_OPTIMISE_r({ | |
1103 | regnode *Next; | |
1104 | ||
1105 | if (!scan) | |
1106 | return; | |
1107 | Next = regnext(scan); | |
1108 | regprop(RExC_rx, RExC_mysv, scan, NULL, pRExC_state); | |
1109 | Perl_re_indentf( aTHX_ "%s>%3d: %s (%d)", | |
1110 | depth, | |
1111 | str, | |
1112 | REG_NODE_NUM(scan), SvPV_nolen_const(RExC_mysv), | |
1113 | Next ? (REG_NODE_NUM(Next)) : 0 ); | |
1114 | S_debug_show_study_flags(aTHX_ flags," [ ","]"); | |
1115 | Perl_re_printf( aTHX_ "\n"); | |
1116 | }); | |
1117 | } | |
1118 | ||
1119 | ||
1120 | # define DEBUG_STUDYDATA(where, data, depth, is_inf) \ | |
1121 | S_debug_studydata(aTHX_ where, data, depth, is_inf) | |
1122 | ||
1123 | # define DEBUG_PEEP(str, scan, depth, flags) \ | |
1124 | S_debug_peep(aTHX_ str, pRExC_state, scan, depth, flags) | |
1125 | ||
1126 | #else | |
1127 | # define DEBUG_STUDYDATA(where, data, depth, is_inf) NOOP | |
1128 | # define DEBUG_PEEP(str, scan, depth, flags) NOOP | |
1129 | #endif | |
1de06328 | 1130 | |
cb41e5d6 | 1131 | |
c6871b76 KW |
1132 | /* ========================================================= |
1133 | * BEGIN edit_distance stuff. | |
1134 | * | |
1135 | * This calculates how many single character changes of any type are needed to | |
1136 | * transform a string into another one. It is taken from version 3.1 of | |
1137 | * | |
1138 | * https://metacpan.org/pod/Text::Levenshtein::Damerau::XS | |
1139 | */ | |
1140 | ||
1141 | /* Our unsorted dictionary linked list. */ | |
1142 | /* Note we use UVs, not chars. */ | |
1143 | ||
1144 | struct dictionary{ | |
1145 | UV key; | |
1146 | UV value; | |
1147 | struct dictionary* next; | |
1148 | }; | |
1149 | typedef struct dictionary item; | |
1150 | ||
1151 | ||
1152 | PERL_STATIC_INLINE item* | |
1153 | push(UV key,item* curr) | |
1154 | { | |
1155 | item* head; | |
d09f14bf | 1156 | Newx(head, 1, item); |
c6871b76 KW |
1157 | head->key = key; |
1158 | head->value = 0; | |
1159 | head->next = curr; | |
1160 | return head; | |
1161 | } | |
1162 | ||
1163 | ||
1164 | PERL_STATIC_INLINE item* | |
1165 | find(item* head, UV key) | |
1166 | { | |
1167 | item* iterator = head; | |
1168 | while (iterator){ | |
1169 | if (iterator->key == key){ | |
1170 | return iterator; | |
1171 | } | |
1172 | iterator = iterator->next; | |
1173 | } | |
1174 | ||
1175 | return NULL; | |
1176 | } | |
1177 | ||
1178 | PERL_STATIC_INLINE item* | |
1179 | uniquePush(item* head,UV key) | |
1180 | { | |
1181 | item* iterator = head; | |
1182 | ||
1183 | while (iterator){ | |
1184 | if (iterator->key == key) { | |
1185 | return head; | |
1186 | } | |
1187 | iterator = iterator->next; | |
1188 | } | |
1189 | ||
1190 | return push(key,head); | |
1191 | } | |
1192 | ||
1193 | PERL_STATIC_INLINE void | |
1194 | dict_free(item* head) | |
1195 | { | |
1196 | item* iterator = head; | |
1197 | ||
1198 | while (iterator) { | |
1199 | item* temp = iterator; | |
1200 | iterator = iterator->next; | |
1201 | Safefree(temp); | |
1202 | } | |
1203 | ||
1204 | head = NULL; | |
1205 | } | |
1206 | ||
1207 | /* End of Dictionary Stuff */ | |
1208 | ||
1209 | /* All calculations/work are done here */ | |
1210 | STATIC int | |
1211 | S_edit_distance(const UV* src, | |
1212 | const UV* tgt, | |
1213 | const STRLEN x, /* length of src[] */ | |
1214 | const STRLEN y, /* length of tgt[] */ | |
1215 | const SSize_t maxDistance | |
1216 | ) | |
1217 | { | |
1218 | item *head = NULL; | |
1219 | UV swapCount,swapScore,targetCharCount,i,j; | |
1220 | UV *scores; | |
1221 | UV score_ceil = x + y; | |
1222 | ||
1223 | PERL_ARGS_ASSERT_EDIT_DISTANCE; | |
1224 | ||
1225 | /* intialize matrix start values */ | |
d09f14bf | 1226 | Newx(scores, ( (x + 2) * (y + 2)), UV); |
c6871b76 KW |
1227 | scores[0] = score_ceil; |
1228 | scores[1 * (y + 2) + 0] = score_ceil; | |
1229 | scores[0 * (y + 2) + 1] = score_ceil; | |
1230 | scores[1 * (y + 2) + 1] = 0; | |
1231 | head = uniquePush(uniquePush(head,src[0]),tgt[0]); | |
1232 | ||
1233 | /* work loops */ | |
1234 | /* i = src index */ | |
1235 | /* j = tgt index */ | |
1236 | for (i=1;i<=x;i++) { | |
1237 | if (i < x) | |
1238 | head = uniquePush(head,src[i]); | |
1239 | scores[(i+1) * (y + 2) + 1] = i; | |
1240 | scores[(i+1) * (y + 2) + 0] = score_ceil; | |
1241 | swapCount = 0; | |
1242 | ||
1243 | for (j=1;j<=y;j++) { | |
1244 | if (i == 1) { | |
1245 | if(j < y) | |
1246 | head = uniquePush(head,tgt[j]); | |
1247 | scores[1 * (y + 2) + (j + 1)] = j; | |
1248 | scores[0 * (y + 2) + (j + 1)] = score_ceil; | |
1249 | } | |
1250 | ||
1251 | targetCharCount = find(head,tgt[j-1])->value; | |
1252 | swapScore = scores[targetCharCount * (y + 2) + swapCount] + i - targetCharCount - 1 + j - swapCount; | |
1253 | ||
1254 | if (src[i-1] != tgt[j-1]){ | |
1255 | 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)); | |
1256 | } | |
1257 | else { | |
1258 | swapCount = j; | |
1259 | scores[(i+1) * (y + 2) + (j + 1)] = MIN(scores[i * (y + 2) + j], swapScore); | |
1260 | } | |
1261 | } | |
1262 | ||
1263 | find(head,src[i-1])->value = i; | |
1264 | } | |
1265 | ||
1266 | { | |
1267 | IV score = scores[(x+1) * (y + 2) + (y + 1)]; | |
1268 | dict_free(head); | |
1269 | Safefree(scores); | |
1270 | return (maxDistance != 0 && maxDistance < score)?(-1):score; | |
1271 | } | |
1272 | } | |
1273 | ||
1274 | /* END of edit_distance() stuff | |
1275 | * ========================================================= */ | |
1276 | ||
8e35b056 KW |
1277 | /* is c a control character for which we have a mnemonic? */ |
1278 | #define isMNEMONIC_CNTRL(c) _IS_MNEMONIC_CNTRL_ONLY_FOR_USE_BY_REGCOMP_DOT_C(c) | |
1279 | ||
549b4e78 KW |
1280 | STATIC const char * |
1281 | S_cntrl_to_mnemonic(const U8 c) | |
1282 | { | |
1283 | /* Returns the mnemonic string that represents character 'c', if one | |
1284 | * exists; NULL otherwise. The only ones that exist for the purposes of | |
1285 | * this routine are a few control characters */ | |
1286 | ||
1287 | switch (c) { | |
1288 | case '\a': return "\\a"; | |
1289 | case '\b': return "\\b"; | |
1290 | case ESC_NATIVE: return "\\e"; | |
1291 | case '\f': return "\\f"; | |
1292 | case '\n': return "\\n"; | |
1293 | case '\r': return "\\r"; | |
1294 | case '\t': return "\\t"; | |
1295 | } | |
1296 | ||
1297 | return NULL; | |
1298 | } | |
1299 | ||
653099ff | 1300 | /* Mark that we cannot extend a found fixed substring at this point. |
37b6262f | 1301 | Update the longest found anchored substring or the longest found |
653099ff GS |
1302 | floating substrings if needed. */ |
1303 | ||
4327152a | 1304 | STATIC void |
ea3daa5d FC |
1305 | S_scan_commit(pTHX_ const RExC_state_t *pRExC_state, scan_data_t *data, |
1306 | SSize_t *minlenp, int is_inf) | |
c277df42 | 1307 | { |
e1ec3a88 | 1308 | const STRLEN l = CHR_SVLEN(data->last_found); |
2099df82 | 1309 | SV * const longest_sv = data->substrs[data->cur_is_floating].str; |
a2ca2017 | 1310 | const STRLEN old_l = CHR_SVLEN(longest_sv); |
1de06328 | 1311 | GET_RE_DEBUG_FLAGS_DECL; |
b81d288d | 1312 | |
7918f24d NC |
1313 | PERL_ARGS_ASSERT_SCAN_COMMIT; |
1314 | ||
c277df42 | 1315 | if ((l >= old_l) && ((l > old_l) || (data->flags & SF_BEFORE_EOL))) { |
2099df82 | 1316 | const U8 i = data->cur_is_floating; |
a2ca2017 | 1317 | SvSetMagicSV(longest_sv, data->last_found); |
37b6262f DM |
1318 | data->substrs[i].min_offset = l ? data->last_start_min : data->pos_min; |
1319 | ||
2099df82 DM |
1320 | if (!i) /* fixed */ |
1321 | data->substrs[0].max_offset = data->substrs[0].min_offset; | |
1322 | else { /* float */ | |
1323 | data->substrs[1].max_offset = (l | |
646e8787 DM |
1324 | ? data->last_start_max |
1325 | : (data->pos_delta > SSize_t_MAX - data->pos_min | |
ea3daa5d FC |
1326 | ? SSize_t_MAX |
1327 | : data->pos_min + data->pos_delta)); | |
1328 | if (is_inf | |
2099df82 DM |
1329 | || (STRLEN)data->substrs[1].max_offset > (STRLEN)SSize_t_MAX) |
1330 | data->substrs[1].max_offset = SSize_t_MAX; | |
37b6262f | 1331 | } |
11683ecb | 1332 | |
37b6262f DM |
1333 | if (data->flags & SF_BEFORE_EOL) |
1334 | data->substrs[i].flags |= (data->flags & SF_BEFORE_EOL); | |
1335 | else | |
1336 | data->substrs[i].flags &= ~SF_BEFORE_EOL; | |
1337 | data->substrs[i].minlenp = minlenp; | |
1338 | data->substrs[i].lookbehind = 0; | |
c277df42 | 1339 | } |
37b6262f | 1340 | |
c277df42 | 1341 | SvCUR_set(data->last_found, 0); |
0eda9292 | 1342 | { |
a28509cc | 1343 | SV * const sv = data->last_found; |
097eb12c AL |
1344 | if (SvUTF8(sv) && SvMAGICAL(sv)) { |
1345 | MAGIC * const mg = mg_find(sv, PERL_MAGIC_utf8); | |
1346 | if (mg) | |
1347 | mg->mg_len = 0; | |
1348 | } | |
0eda9292 | 1349 | } |
c277df42 IZ |
1350 | data->last_end = -1; |
1351 | data->flags &= ~SF_BEFORE_EOL; | |
f5a36d78 | 1352 | DEBUG_STUDYDATA("commit", data, 0, is_inf); |
c277df42 IZ |
1353 | } |
1354 | ||
cdd87c1d KW |
1355 | /* An SSC is just a regnode_charclass_posix with an extra field: the inversion |
1356 | * list that describes which code points it matches */ | |
1357 | ||
653099ff | 1358 | STATIC void |
3420edd7 | 1359 | S_ssc_anything(pTHX_ regnode_ssc *ssc) |
653099ff | 1360 | { |
cdd87c1d KW |
1361 | /* Set the SSC 'ssc' to match an empty string or any code point */ |
1362 | ||
557bd3fb | 1363 | PERL_ARGS_ASSERT_SSC_ANYTHING; |
7918f24d | 1364 | |
71068078 | 1365 | assert(is_ANYOF_SYNTHETIC(ssc)); |
3fffb88a | 1366 | |
0854ea0b KW |
1367 | /* mortalize so won't leak */ |
1368 | ssc->invlist = sv_2mortal(_add_range_to_invlist(NULL, 0, UV_MAX)); | |
93e92956 | 1369 | ANYOF_FLAGS(ssc) |= SSC_MATCHES_EMPTY_STRING; /* Plus matches empty */ |
653099ff GS |
1370 | } |
1371 | ||
653099ff | 1372 | STATIC int |
dc3bf405 | 1373 | S_ssc_is_anything(const regnode_ssc *ssc) |
653099ff | 1374 | { |
c144baaa KW |
1375 | /* Returns TRUE if the SSC 'ssc' can match the empty string and any code |
1376 | * point; FALSE otherwise. Thus, this is used to see if using 'ssc' buys | |
1377 | * us anything: if the function returns TRUE, 'ssc' hasn't been restricted | |
1378 | * in any way, so there's no point in using it */ | |
cdd87c1d KW |
1379 | |
1380 | UV start, end; | |
1381 | bool ret; | |
653099ff | 1382 | |
557bd3fb | 1383 | PERL_ARGS_ASSERT_SSC_IS_ANYTHING; |
7918f24d | 1384 | |
71068078 | 1385 | assert(is_ANYOF_SYNTHETIC(ssc)); |
cdd87c1d | 1386 | |
93e92956 | 1387 | if (! (ANYOF_FLAGS(ssc) & SSC_MATCHES_EMPTY_STRING)) { |
cdd87c1d KW |
1388 | return FALSE; |
1389 | } | |
1390 | ||
1391 | /* See if the list consists solely of the range 0 - Infinity */ | |
1392 | invlist_iterinit(ssc->invlist); | |
1393 | ret = invlist_iternext(ssc->invlist, &start, &end) | |
1394 | && start == 0 | |
1395 | && end == UV_MAX; | |
1396 | ||
1397 | invlist_iterfinish(ssc->invlist); | |
1398 | ||
1399 | if (ret) { | |
1400 | return TRUE; | |
1401 | } | |
1402 | ||
1403 | /* If e.g., both \w and \W are set, matches everything */ | |
e0e1be5f | 1404 | if (ANYOF_POSIXL_SSC_TEST_ANY_SET(ssc)) { |
cdd87c1d KW |
1405 | int i; |
1406 | for (i = 0; i < ANYOF_POSIXL_MAX; i += 2) { | |
1407 | if (ANYOF_POSIXL_TEST(ssc, i) && ANYOF_POSIXL_TEST(ssc, i+1)) { | |
1408 | return TRUE; | |
1409 | } | |
1410 | } | |
1411 | } | |
1412 | ||
1413 | return FALSE; | |
653099ff GS |
1414 | } |
1415 | ||
653099ff | 1416 | STATIC void |
cdd87c1d | 1417 | S_ssc_init(pTHX_ const RExC_state_t *pRExC_state, regnode_ssc *ssc) |
653099ff | 1418 | { |
cdd87c1d KW |
1419 | /* Initializes the SSC 'ssc'. This includes setting it to match an empty |
1420 | * string, any code point, or any posix class under locale */ | |
1421 | ||
557bd3fb | 1422 | PERL_ARGS_ASSERT_SSC_INIT; |
7918f24d | 1423 | |
557bd3fb | 1424 | Zero(ssc, 1, regnode_ssc); |
71068078 | 1425 | set_ANYOF_SYNTHETIC(ssc); |
93e92956 | 1426 | ARG_SET(ssc, ANYOF_ONLY_HAS_BITMAP); |
3420edd7 | 1427 | ssc_anything(ssc); |
cdd87c1d | 1428 | |
2f306ab9 KW |
1429 | /* If any portion of the regex is to operate under locale rules that aren't |
1430 | * fully known at compile time, initialization includes it. The reason | |
1431 | * this isn't done for all regexes is that the optimizer was written under | |
1432 | * the assumption that locale was all-or-nothing. Given the complexity and | |
1433 | * lack of documentation in the optimizer, and that there are inadequate | |
1434 | * test cases for locale, many parts of it may not work properly, it is | |
1435 | * safest to avoid locale unless necessary. */ | |
cdd87c1d KW |
1436 | if (RExC_contains_locale) { |
1437 | ANYOF_POSIXL_SETALL(ssc); | |
cdd87c1d KW |
1438 | } |
1439 | else { | |
1440 | ANYOF_POSIXL_ZERO(ssc); | |
1441 | } | |
653099ff GS |
1442 | } |
1443 | ||
b423522f | 1444 | STATIC int |
dc3bf405 BF |
1445 | S_ssc_is_cp_posixl_init(const RExC_state_t *pRExC_state, |
1446 | const regnode_ssc *ssc) | |
b423522f KW |
1447 | { |
1448 | /* Returns TRUE if the SSC 'ssc' is in its initial state with regard only | |
1449 | * to the list of code points matched, and locale posix classes; hence does | |
1450 | * not check its flags) */ | |
1451 | ||
1452 | UV start, end; | |
1453 | bool ret; | |
1454 | ||
1455 | PERL_ARGS_ASSERT_SSC_IS_CP_POSIXL_INIT; | |
1456 | ||
71068078 | 1457 | assert(is_ANYOF_SYNTHETIC(ssc)); |
b423522f KW |
1458 | |
1459 | invlist_iterinit(ssc->invlist); | |
1460 | ret = invlist_iternext(ssc->invlist, &start, &end) | |
1461 | && start == 0 | |
1462 | && end == UV_MAX; | |
1463 | ||
1464 | invlist_iterfinish(ssc->invlist); | |
1465 | ||
1466 | if (! ret) { | |
1467 | return FALSE; | |
1468 | } | |
1469 | ||
e0e1be5f | 1470 | if (RExC_contains_locale && ! ANYOF_POSIXL_SSC_TEST_ALL_SET(ssc)) { |
31f05a37 | 1471 | return FALSE; |
b423522f KW |
1472 | } |
1473 | ||
1474 | return TRUE; | |
1475 | } | |
1476 | ||
1477 | STATIC SV* | |
1478 | S_get_ANYOF_cp_list_for_ssc(pTHX_ const RExC_state_t *pRExC_state, | |
5c0f85ef | 1479 | const regnode_charclass* const node) |
b423522f KW |
1480 | { |
1481 | /* Returns a mortal inversion list defining which code points are matched | |
1482 | * by 'node', which is of type ANYOF. Handles complementing the result if | |
1483 | * appropriate. If some code points aren't knowable at this time, the | |
31f05a37 KW |
1484 | * returned list must, and will, contain every code point that is a |
1485 | * possibility. */ | |
b423522f | 1486 | |
e2506fa7 | 1487 | SV* invlist = NULL; |
1ee208c4 | 1488 | SV* only_utf8_locale_invlist = NULL; |
b423522f KW |
1489 | unsigned int i; |
1490 | const U32 n = ARG(node); | |
31f05a37 | 1491 | bool new_node_has_latin1 = FALSE; |
b423522f KW |
1492 | |
1493 | PERL_ARGS_ASSERT_GET_ANYOF_CP_LIST_FOR_SSC; | |
1494 | ||
1495 | /* Look at the data structure created by S_set_ANYOF_arg() */ | |
93e92956 | 1496 | if (n != ANYOF_ONLY_HAS_BITMAP) { |
b423522f KW |
1497 | SV * const rv = MUTABLE_SV(RExC_rxi->data->data[n]); |
1498 | AV * const av = MUTABLE_AV(SvRV(rv)); | |
1499 | SV **const ary = AvARRAY(av); | |
1500 | assert(RExC_rxi->data->what[n] == 's'); | |
1501 | ||
1502 | if (ary[1] && ary[1] != &PL_sv_undef) { /* Has compile-time swash */ | |
28118b9c | 1503 | invlist = sv_2mortal(invlist_clone(_get_swash_invlist(ary[1]), NULL)); |
b423522f KW |
1504 | } |
1505 | else if (ary[0] && ary[0] != &PL_sv_undef) { | |
1506 | ||
1507 | /* Here, no compile-time swash, and there are things that won't be | |
1508 | * known until runtime -- we have to assume it could be anything */ | |
e2506fa7 | 1509 | invlist = sv_2mortal(_new_invlist(1)); |
b423522f KW |
1510 | return _add_range_to_invlist(invlist, 0, UV_MAX); |
1511 | } | |
1ee208c4 | 1512 | else if (ary[3] && ary[3] != &PL_sv_undef) { |
b423522f KW |
1513 | |
1514 | /* Here no compile-time swash, and no run-time only data. Use the | |
1515 | * node's inversion list */ | |
28118b9c | 1516 | invlist = sv_2mortal(invlist_clone(ary[3], NULL)); |
1ee208c4 KW |
1517 | } |
1518 | ||
1519 | /* Get the code points valid only under UTF-8 locales */ | |
037715a6 | 1520 | if ((ANYOF_FLAGS(node) & ANYOFL_FOLD) |
1ee208c4 KW |
1521 | && ary[2] && ary[2] != &PL_sv_undef) |
1522 | { | |
1523 | only_utf8_locale_invlist = ary[2]; | |
b423522f KW |
1524 | } |
1525 | } | |
1526 | ||
e2506fa7 KW |
1527 | if (! invlist) { |
1528 | invlist = sv_2mortal(_new_invlist(0)); | |
1529 | } | |
1530 | ||
dcb20b36 KW |
1531 | /* An ANYOF node contains a bitmap for the first NUM_ANYOF_CODE_POINTS |
1532 | * code points, and an inversion list for the others, but if there are code | |
1533 | * points that should match only conditionally on the target string being | |
1534 | * UTF-8, those are placed in the inversion list, and not the bitmap. | |
1535 | * Since there are circumstances under which they could match, they are | |
1536 | * included in the SSC. But if the ANYOF node is to be inverted, we have | |
1537 | * to exclude them here, so that when we invert below, the end result | |
1538 | * actually does include them. (Think about "\xe0" =~ /[^\xc0]/di;). We | |
1539 | * have to do this here before we add the unconditionally matched code | |
1540 | * points */ | |
b423522f KW |
1541 | if (ANYOF_FLAGS(node) & ANYOF_INVERT) { |
1542 | _invlist_intersection_complement_2nd(invlist, | |
1543 | PL_UpperLatin1, | |
1544 | &invlist); | |
1545 | } | |
1546 | ||
1547 | /* Add in the points from the bit map */ | |
dcb20b36 | 1548 | for (i = 0; i < NUM_ANYOF_CODE_POINTS; i++) { |
b423522f | 1549 | if (ANYOF_BITMAP_TEST(node, i)) { |
6f8848d5 TC |
1550 | unsigned int start = i++; |
1551 | ||
1552 | for (; i < NUM_ANYOF_CODE_POINTS && ANYOF_BITMAP_TEST(node, i); ++i) { | |
1553 | /* empty */ | |
1554 | } | |
1555 | invlist = _add_range_to_invlist(invlist, start, i-1); | |
31f05a37 | 1556 | new_node_has_latin1 = TRUE; |
b423522f KW |
1557 | } |
1558 | } | |
1559 | ||
1560 | /* If this can match all upper Latin1 code points, have to add them | |
ac33c516 KW |
1561 | * as well. But don't add them if inverting, as when that gets done below, |
1562 | * it would exclude all these characters, including the ones it shouldn't | |
1563 | * that were added just above */ | |
1564 | if (! (ANYOF_FLAGS(node) & ANYOF_INVERT) && OP(node) == ANYOFD | |
f240c685 KW |
1565 | && (ANYOF_FLAGS(node) & ANYOF_SHARED_d_MATCHES_ALL_NON_UTF8_NON_ASCII_non_d_WARN_SUPER)) |
1566 | { | |
b423522f KW |
1567 | _invlist_union(invlist, PL_UpperLatin1, &invlist); |
1568 | } | |
1569 | ||
1570 | /* Similarly for these */ | |
93e92956 | 1571 | if (ANYOF_FLAGS(node) & ANYOF_MATCHES_ALL_ABOVE_BITMAP) { |
e0a1ff7a | 1572 | _invlist_union_complement_2nd(invlist, PL_InBitmap, &invlist); |
b423522f KW |
1573 | } |
1574 | ||
1575 | if (ANYOF_FLAGS(node) & ANYOF_INVERT) { | |
1576 | _invlist_invert(invlist); | |
1577 | } | |
037715a6 | 1578 | else if (new_node_has_latin1 && ANYOF_FLAGS(node) & ANYOFL_FOLD) { |
31f05a37 KW |
1579 | |
1580 | /* Under /li, any 0-255 could fold to any other 0-255, depending on the | |
1581 | * locale. We can skip this if there are no 0-255 at all. */ | |
1582 | _invlist_union(invlist, PL_Latin1, &invlist); | |
1583 | } | |
1584 | ||
1ee208c4 KW |
1585 | /* Similarly add the UTF-8 locale possible matches. These have to be |
1586 | * deferred until after the non-UTF-8 locale ones are taken care of just | |
1587 | * above, or it leads to wrong results under ANYOF_INVERT */ | |
1588 | if (only_utf8_locale_invlist) { | |
31f05a37 | 1589 | _invlist_union_maybe_complement_2nd(invlist, |
1ee208c4 | 1590 | only_utf8_locale_invlist, |
31f05a37 KW |
1591 | ANYOF_FLAGS(node) & ANYOF_INVERT, |
1592 | &invlist); | |
1593 | } | |
b423522f KW |
1594 | |
1595 | return invlist; | |
1596 | } | |
1597 | ||
1051e1c4 | 1598 | /* These two functions currently do the exact same thing */ |
557bd3fb | 1599 | #define ssc_init_zero ssc_init |
653099ff | 1600 | |
cdd87c1d KW |
1601 | #define ssc_add_cp(ssc, cp) ssc_add_range((ssc), (cp), (cp)) |
1602 | #define ssc_match_all_cp(ssc) ssc_add_range(ssc, 0, UV_MAX) | |
1603 | ||
557bd3fb | 1604 | /* 'AND' a given class with another one. Can create false positives. 'ssc' |
93e92956 KW |
1605 | * should not be inverted. 'and_with->flags & ANYOF_MATCHES_POSIXL' should be |
1606 | * 0 if 'and_with' is a regnode_charclass instead of a regnode_ssc. */ | |
cdd87c1d | 1607 | |
653099ff | 1608 | STATIC void |
b423522f | 1609 | S_ssc_and(pTHX_ const RExC_state_t *pRExC_state, regnode_ssc *ssc, |
7dcac5f6 | 1610 | const regnode_charclass *and_with) |
653099ff | 1611 | { |
cdd87c1d KW |
1612 | /* Accumulate into SSC 'ssc' its 'AND' with 'and_with', which is either |
1613 | * another SSC or a regular ANYOF class. Can create false positives. */ | |
40d049e4 | 1614 | |
a0dd4231 KW |
1615 | SV* anded_cp_list; |
1616 | U8 anded_flags; | |
1e6ade67 | 1617 | |
cdd87c1d | 1618 | PERL_ARGS_ASSERT_SSC_AND; |
653099ff | 1619 | |
71068078 | 1620 | assert(is_ANYOF_SYNTHETIC(ssc)); |
a0dd4231 KW |
1621 | |
1622 | /* 'and_with' is used as-is if it too is an SSC; otherwise have to extract | |
1623 | * the code point inversion list and just the relevant flags */ | |
71068078 | 1624 | if (is_ANYOF_SYNTHETIC(and_with)) { |
7dcac5f6 | 1625 | anded_cp_list = ((regnode_ssc *)and_with)->invlist; |
a0dd4231 | 1626 | anded_flags = ANYOF_FLAGS(and_with); |
e9b08962 KW |
1627 | |
1628 | /* XXX This is a kludge around what appears to be deficiencies in the | |
1629 | * optimizer. If we make S_ssc_anything() add in the WARN_SUPER flag, | |
1630 | * there are paths through the optimizer where it doesn't get weeded | |
1631 | * out when it should. And if we don't make some extra provision for | |
1632 | * it like the code just below, it doesn't get added when it should. | |
1633 | * This solution is to add it only when AND'ing, which is here, and | |
1634 | * only when what is being AND'ed is the pristine, original node | |
1635 | * matching anything. Thus it is like adding it to ssc_anything() but | |
1636 | * only when the result is to be AND'ed. Probably the same solution | |
1637 | * could be adopted for the same problem we have with /l matching, | |
1638 | * which is solved differently in S_ssc_init(), and that would lead to | |
1639 | * fewer false positives than that solution has. But if this solution | |
1640 | * creates bugs, the consequences are only that a warning isn't raised | |
1641 | * that should be; while the consequences for having /l bugs is | |
1642 | * incorrect matches */ | |
7dcac5f6 | 1643 | if (ssc_is_anything((regnode_ssc *)and_with)) { |
f240c685 | 1644 | anded_flags |= ANYOF_SHARED_d_MATCHES_ALL_NON_UTF8_NON_ASCII_non_d_WARN_SUPER; |
e9b08962 | 1645 | } |
a0dd4231 KW |
1646 | } |
1647 | else { | |
5c0f85ef | 1648 | anded_cp_list = get_ANYOF_cp_list_for_ssc(pRExC_state, and_with); |
f240c685 KW |
1649 | if (OP(and_with) == ANYOFD) { |
1650 | anded_flags = ANYOF_FLAGS(and_with) & ANYOF_COMMON_FLAGS; | |
1651 | } | |
1652 | else { | |
1653 | anded_flags = ANYOF_FLAGS(and_with) | |
1654 | &( ANYOF_COMMON_FLAGS | |
108316fb KW |
1655 | |ANYOF_SHARED_d_MATCHES_ALL_NON_UTF8_NON_ASCII_non_d_WARN_SUPER |
1656 | |ANYOF_SHARED_d_UPPER_LATIN1_UTF8_STRING_MATCHES_non_d_RUNTIME_USER_PROP); | |
d1c40ef5 KW |
1657 | if (ANYOFL_UTF8_LOCALE_REQD(ANYOF_FLAGS(and_with))) { |
1658 | anded_flags &= | |
1659 | ANYOFL_SHARED_UTF8_LOCALE_fold_HAS_MATCHES_nonfold_REQD; | |
1660 | } | |
f240c685 | 1661 | } |
a0dd4231 KW |
1662 | } |
1663 | ||
1664 | ANYOF_FLAGS(ssc) &= anded_flags; | |
cdd87c1d KW |
1665 | |
1666 | /* Below, C1 is the list of code points in 'ssc'; P1, its posix classes. | |
1667 | * C2 is the list of code points in 'and-with'; P2, its posix classes. | |
1668 | * 'and_with' may be inverted. When not inverted, we have the situation of | |
1669 | * computing: | |
1670 | * (C1 | P1) & (C2 | P2) | |
1671 | * = (C1 & (C2 | P2)) | (P1 & (C2 | P2)) | |
1672 | * = ((C1 & C2) | (C1 & P2)) | ((P1 & C2) | (P1 & P2)) | |
1673 | * <= ((C1 & C2) | P2)) | ( P1 | (P1 & P2)) | |
1674 | * <= ((C1 & C2) | P1 | P2) | |
1675 | * Alternatively, the last few steps could be: | |
1676 | * = ((C1 & C2) | (C1 & P2)) | ((P1 & C2) | (P1 & P2)) | |
1677 | * <= ((C1 & C2) | C1 ) | ( C2 | (P1 & P2)) | |
1678 | * <= (C1 | C2 | (P1 & P2)) | |
1679 | * We favor the second approach if either P1 or P2 is non-empty. This is | |
1680 | * because these components are a barrier to doing optimizations, as what | |
1681 | * they match cannot be known until the moment of matching as they are | |
1682 | * dependent on the current locale, 'AND"ing them likely will reduce or | |
1683 | * eliminate them. | |
1684 | * But we can do better if we know that C1,P1 are in their initial state (a | |
1685 | * frequent occurrence), each matching everything: | |
1686 | * (<everything>) & (C2 | P2) = C2 | P2 | |
1687 | * Similarly, if C2,P2 are in their initial state (again a frequent | |
1688 | * occurrence), the result is a no-op | |
1689 | * (C1 | P1) & (<everything>) = C1 | P1 | |
1690 | * | |
1691 | * Inverted, we have | |
1692 | * (C1 | P1) & ~(C2 | P2) = (C1 | P1) & (~C2 & ~P2) | |
1693 | * = (C1 & (~C2 & ~P2)) | (P1 & (~C2 & ~P2)) | |
1694 | * <= (C1 & ~C2) | (P1 & ~P2) | |
1695 | * */ | |
1aa99e6b | 1696 | |
a0dd4231 | 1697 | if ((ANYOF_FLAGS(and_with) & ANYOF_INVERT) |
71068078 | 1698 | && ! is_ANYOF_SYNTHETIC(and_with)) |
a0dd4231 | 1699 | { |
cdd87c1d | 1700 | unsigned int i; |
8951c461 | 1701 | |
cdd87c1d KW |
1702 | ssc_intersection(ssc, |
1703 | anded_cp_list, | |
1704 | FALSE /* Has already been inverted */ | |
1705 | ); | |
c6b76537 | 1706 | |
cdd87c1d KW |
1707 | /* If either P1 or P2 is empty, the intersection will be also; can skip |
1708 | * the loop */ | |
93e92956 | 1709 | if (! (ANYOF_FLAGS(and_with) & ANYOF_MATCHES_POSIXL)) { |
cdd87c1d KW |
1710 | ANYOF_POSIXL_ZERO(ssc); |
1711 | } | |
e0e1be5f | 1712 | else if (ANYOF_POSIXL_SSC_TEST_ANY_SET(ssc)) { |
cdd87c1d KW |
1713 | |
1714 | /* Note that the Posix class component P from 'and_with' actually | |
1715 | * looks like: | |
1716 | * P = Pa | Pb | ... | Pn | |
1717 | * where each component is one posix class, such as in [\w\s]. | |
1718 | * Thus | |
1719 | * ~P = ~(Pa | Pb | ... | Pn) | |
1720 | * = ~Pa & ~Pb & ... & ~Pn | |
1721 | * <= ~Pa | ~Pb | ... | ~Pn | |
1722 | * The last is something we can easily calculate, but unfortunately | |
1723 | * is likely to have many false positives. We could do better | |
1724 | * in some (but certainly not all) instances if two classes in | |
1725 | * P have known relationships. For example | |
1726 | * :lower: <= :alpha: <= :alnum: <= \w <= :graph: <= :print: | |
1727 | * So | |
1728 | * :lower: & :print: = :lower: | |
1729 | * And similarly for classes that must be disjoint. For example, | |
1730 | * since \s and \w can have no elements in common based on rules in | |
1731 | * the POSIX standard, | |
1732 | * \w & ^\S = nothing | |
1733 | * Unfortunately, some vendor locales do not meet the Posix | |
1734 | * standard, in particular almost everything by Microsoft. | |
1735 | * The loop below just changes e.g., \w into \W and vice versa */ | |
1736 | ||
1ee208c4 | 1737 | regnode_charclass_posixl temp; |
cdd87c1d KW |
1738 | int add = 1; /* To calculate the index of the complement */ |
1739 | ||
b1234259 | 1740 | Zero(&temp, 1, regnode_charclass_posixl); |
cdd87c1d KW |
1741 | ANYOF_POSIXL_ZERO(&temp); |
1742 | for (i = 0; i < ANYOF_MAX; i++) { | |
1743 | assert(i % 2 != 0 | |
7dcac5f6 KW |
1744 | || ! ANYOF_POSIXL_TEST((regnode_charclass_posixl*) and_with, i) |
1745 | || ! ANYOF_POSIXL_TEST((regnode_charclass_posixl*) and_with, i + 1)); | |
cdd87c1d | 1746 | |
7dcac5f6 | 1747 | if (ANYOF_POSIXL_TEST((regnode_charclass_posixl*) and_with, i)) { |
cdd87c1d KW |
1748 | ANYOF_POSIXL_SET(&temp, i + add); |
1749 | } | |
1750 | add = 0 - add; /* 1 goes to -1; -1 goes to 1 */ | |
1751 | } | |
1752 | ANYOF_POSIXL_AND(&temp, ssc); | |
c6b76537 | 1753 | |
cdd87c1d KW |
1754 | } /* else ssc already has no posixes */ |
1755 | } /* else: Not inverted. This routine is a no-op if 'and_with' is an SSC | |
1756 | in its initial state */ | |
71068078 | 1757 | else if (! is_ANYOF_SYNTHETIC(and_with) |
7dcac5f6 | 1758 | || ! ssc_is_cp_posixl_init(pRExC_state, (regnode_ssc *)and_with)) |
cdd87c1d KW |
1759 | { |
1760 | /* But if 'ssc' is in its initial state, the result is just 'and_with'; | |
1761 | * copy it over 'ssc' */ | |
1762 | if (ssc_is_cp_posixl_init(pRExC_state, ssc)) { | |
71068078 | 1763 | if (is_ANYOF_SYNTHETIC(and_with)) { |
cdd87c1d KW |
1764 | StructCopy(and_with, ssc, regnode_ssc); |
1765 | } | |
1766 | else { | |
1767 | ssc->invlist = anded_cp_list; | |
1768 | ANYOF_POSIXL_ZERO(ssc); | |
93e92956 | 1769 | if (ANYOF_FLAGS(and_with) & ANYOF_MATCHES_POSIXL) { |
7dcac5f6 | 1770 | ANYOF_POSIXL_OR((regnode_charclass_posixl*) and_with, ssc); |
cdd87c1d KW |
1771 | } |
1772 | } | |
1773 | } | |
e0e1be5f | 1774 | else if (ANYOF_POSIXL_SSC_TEST_ANY_SET(ssc) |
93e92956 | 1775 | || (ANYOF_FLAGS(and_with) & ANYOF_MATCHES_POSIXL)) |
cdd87c1d KW |
1776 | { |
1777 | /* One or the other of P1, P2 is non-empty. */ | |
93e92956 | 1778 | if (ANYOF_FLAGS(and_with) & ANYOF_MATCHES_POSIXL) { |
1ea8b7fe KW |
1779 | ANYOF_POSIXL_AND((regnode_charclass_posixl*) and_with, ssc); |
1780 | } | |
cdd87c1d KW |
1781 | ssc_union(ssc, anded_cp_list, FALSE); |
1782 | } | |
1783 | else { /* P1 = P2 = empty */ | |
1784 | ssc_intersection(ssc, anded_cp_list, FALSE); | |
1785 | } | |
137165a6 | 1786 | } |
653099ff GS |
1787 | } |
1788 | ||
653099ff | 1789 | STATIC void |
cdd87c1d | 1790 | S_ssc_or(pTHX_ const RExC_state_t *pRExC_state, regnode_ssc *ssc, |
7dcac5f6 | 1791 | const regnode_charclass *or_with) |
653099ff | 1792 | { |
cdd87c1d KW |
1793 | /* Accumulate into SSC 'ssc' its 'OR' with 'or_with', which is either |
1794 | * another SSC or a regular ANYOF class. Can create false positives if | |
1795 | * 'or_with' is to be inverted. */ | |
7918f24d | 1796 | |
a0dd4231 KW |
1797 | SV* ored_cp_list; |
1798 | U8 ored_flags; | |
c6b76537 | 1799 | |
cdd87c1d | 1800 | PERL_ARGS_ASSERT_SSC_OR; |
c6b76537 | 1801 | |
71068078 | 1802 | assert(is_ANYOF_SYNTHETIC(ssc)); |
a0dd4231 KW |
1803 | |
1804 | /* 'or_with' is used as-is if it too is an SSC; otherwise have to extract | |
1805 | * the code point inversion list and just the relevant flags */ | |
71068078 | 1806 | if (is_ANYOF_SYNTHETIC(or_with)) { |
7dcac5f6 | 1807 | ored_cp_list = ((regnode_ssc*) or_with)->invlist; |
a0dd4231 KW |
1808 | ored_flags = ANYOF_FLAGS(or_with); |
1809 | } | |
1810 | else { | |
5c0f85ef | 1811 | ored_cp_list = get_ANYOF_cp_list_for_ssc(pRExC_state, or_with); |
eff8b7dc | 1812 | ored_flags = ANYOF_FLAGS(or_with) & ANYOF_COMMON_FLAGS; |
f240c685 KW |
1813 | if (OP(or_with) != ANYOFD) { |
1814 | ored_flags | |
1815 | |= ANYOF_FLAGS(or_with) | |
108316fb KW |
1816 | & ( ANYOF_SHARED_d_MATCHES_ALL_NON_UTF8_NON_ASCII_non_d_WARN_SUPER |
1817 | |ANYOF_SHARED_d_UPPER_LATIN1_UTF8_STRING_MATCHES_non_d_RUNTIME_USER_PROP); | |
d1c40ef5 KW |
1818 | if (ANYOFL_UTF8_LOCALE_REQD(ANYOF_FLAGS(or_with))) { |
1819 | ored_flags |= | |
1820 | ANYOFL_SHARED_UTF8_LOCALE_fold_HAS_MATCHES_nonfold_REQD; | |
1821 | } | |
f240c685 | 1822 | } |
a0dd4231 KW |
1823 | } |
1824 | ||
1825 | ANYOF_FLAGS(ssc) |= ored_flags; | |
cdd87c1d KW |
1826 | |
1827 | /* Below, C1 is the list of code points in 'ssc'; P1, its posix classes. | |
1828 | * C2 is the list of code points in 'or-with'; P2, its posix classes. | |
1829 | * 'or_with' may be inverted. When not inverted, we have the simple | |
1830 | * situation of computing: | |
1831 | * (C1 | P1) | (C2 | P2) = (C1 | C2) | (P1 | P2) | |
1832 | * If P1|P2 yields a situation with both a class and its complement are | |
1833 | * set, like having both \w and \W, this matches all code points, and we | |
1834 | * can delete these from the P component of the ssc going forward. XXX We | |
1835 | * might be able to delete all the P components, but I (khw) am not certain | |
1836 | * about this, and it is better to be safe. | |
1837 | * | |
1838 | * Inverted, we have | |
1839 | * (C1 | P1) | ~(C2 | P2) = (C1 | P1) | (~C2 & ~P2) | |
1840 | * <= (C1 | P1) | ~C2 | |
1841 | * <= (C1 | ~C2) | P1 | |
1842 | * (which results in actually simpler code than the non-inverted case) | |
1843 | * */ | |
9826f543 | 1844 | |
a0dd4231 | 1845 | if ((ANYOF_FLAGS(or_with) & ANYOF_INVERT) |
71068078 | 1846 | && ! is_ANYOF_SYNTHETIC(or_with)) |
a0dd4231 | 1847 | { |
cdd87c1d | 1848 | /* We ignore P2, leaving P1 going forward */ |
1ea8b7fe | 1849 | } /* else Not inverted */ |
93e92956 | 1850 | else if (ANYOF_FLAGS(or_with) & ANYOF_MATCHES_POSIXL) { |
7dcac5f6 | 1851 | ANYOF_POSIXL_OR((regnode_charclass_posixl*)or_with, ssc); |
e0e1be5f | 1852 | if (ANYOF_POSIXL_SSC_TEST_ANY_SET(ssc)) { |
cdd87c1d KW |
1853 | unsigned int i; |
1854 | for (i = 0; i < ANYOF_MAX; i += 2) { | |
1855 | if (ANYOF_POSIXL_TEST(ssc, i) && ANYOF_POSIXL_TEST(ssc, i + 1)) | |
1856 | { | |
1857 | ssc_match_all_cp(ssc); | |
1858 | ANYOF_POSIXL_CLEAR(ssc, i); | |
1859 | ANYOF_POSIXL_CLEAR(ssc, i+1); | |
cdd87c1d KW |
1860 | } |
1861 | } | |
1862 | } | |
1aa99e6b | 1863 | } |
cdd87c1d KW |
1864 | |
1865 | ssc_union(ssc, | |
1866 | ored_cp_list, | |
1867 | FALSE /* Already has been inverted */ | |
1868 | ); | |
653099ff GS |
1869 | } |
1870 | ||
b423522f KW |
1871 | PERL_STATIC_INLINE void |
1872 | S_ssc_union(pTHX_ regnode_ssc *ssc, SV* const invlist, const bool invert2nd) | |
1873 | { | |
1874 | PERL_ARGS_ASSERT_SSC_UNION; | |
1875 | ||
71068078 | 1876 | assert(is_ANYOF_SYNTHETIC(ssc)); |
b423522f KW |
1877 | |
1878 | _invlist_union_maybe_complement_2nd(ssc->invlist, | |
1879 | invlist, | |
1880 | invert2nd, | |
1881 | &ssc->invlist); | |
1882 | } | |
1883 | ||
1884 | PERL_STATIC_INLINE void | |
1885 | S_ssc_intersection(pTHX_ regnode_ssc *ssc, | |
1886 | SV* const invlist, | |
1887 | const bool invert2nd) | |
1888 | { | |
1889 | PERL_ARGS_ASSERT_SSC_INTERSECTION; | |
1890 | ||
71068078 | 1891 | assert(is_ANYOF_SYNTHETIC(ssc)); |
b423522f KW |
1892 | |
1893 | _invlist_intersection_maybe_complement_2nd(ssc->invlist, | |
1894 | invlist, | |
1895 | invert2nd, | |
1896 | &ssc->invlist); | |
1897 | } | |
1898 | ||
1899 | PERL_STATIC_INLINE void | |
1900 | S_ssc_add_range(pTHX_ regnode_ssc *ssc, const UV start, const UV end) | |
1901 | { | |
1902 | PERL_ARGS_ASSERT_SSC_ADD_RANGE; | |
1903 | ||
71068078 | 1904 | assert(is_ANYOF_SYNTHETIC(ssc)); |
b423522f KW |
1905 | |
1906 | ssc->invlist = _add_range_to_invlist(ssc->invlist, start, end); | |
1907 | } | |
1908 | ||
1909 | PERL_STATIC_INLINE void | |
1910 | S_ssc_cp_and(pTHX_ regnode_ssc *ssc, const UV cp) | |
1911 | { | |
1912 | /* AND just the single code point 'cp' into the SSC 'ssc' */ | |
1913 | ||
1914 | SV* cp_list = _new_invlist(2); | |
1915 | ||
1916 | PERL_ARGS_ASSERT_SSC_CP_AND; | |
1917 | ||
71068078 | 1918 | assert(is_ANYOF_SYNTHETIC(ssc)); |
b423522f KW |
1919 | |
1920 | cp_list = add_cp_to_invlist(cp_list, cp); | |
1921 | ssc_intersection(ssc, cp_list, | |
1922 | FALSE /* Not inverted */ | |
1923 | ); | |
1924 | SvREFCNT_dec_NN(cp_list); | |
1925 | } | |
1926 | ||
1927 | PERL_STATIC_INLINE void | |
dc3bf405 | 1928 | S_ssc_clear_locale(regnode_ssc *ssc) |
b423522f KW |
1929 | { |
1930 | /* Set the SSC 'ssc' to not match any locale things */ | |
b423522f KW |
1931 | PERL_ARGS_ASSERT_SSC_CLEAR_LOCALE; |
1932 | ||
71068078 | 1933 | assert(is_ANYOF_SYNTHETIC(ssc)); |
b423522f KW |
1934 | |
1935 | ANYOF_POSIXL_ZERO(ssc); | |
1936 | ANYOF_FLAGS(ssc) &= ~ANYOF_LOCALE_FLAGS; | |
1937 | } | |
1938 | ||
b35552de KW |
1939 | #define NON_OTHER_COUNT NON_OTHER_COUNT_FOR_USE_ONLY_BY_REGCOMP_DOT_C |
1940 | ||
1941 | STATIC bool | |
1942 | S_is_ssc_worth_it(const RExC_state_t * pRExC_state, const regnode_ssc * ssc) | |
1943 | { | |
1944 | /* The synthetic start class is used to hopefully quickly winnow down | |
1945 | * places where a pattern could start a match in the target string. If it | |
1946 | * doesn't really narrow things down that much, there isn't much point to | |
1947 | * having the overhead of using it. This function uses some very crude | |
1948 | * heuristics to decide if to use the ssc or not. | |
1949 | * | |
1950 | * It returns TRUE if 'ssc' rules out more than half what it considers to | |
1951 | * be the "likely" possible matches, but of course it doesn't know what the | |
1952 | * actual things being matched are going to be; these are only guesses | |
1953 | * | |
1954 | * For /l matches, it assumes that the only likely matches are going to be | |
1955 | * in the 0-255 range, uniformly distributed, so half of that is 127 | |
1956 | * For /a and /d matches, it assumes that the likely matches will be just | |
1957 | * the ASCII range, so half of that is 63 | |
1958 | * For /u and there isn't anything matching above the Latin1 range, it | |
1959 | * assumes that that is the only range likely to be matched, and uses | |
1960 | * half that as the cut-off: 127. If anything matches above Latin1, | |
1961 | * it assumes that all of Unicode could match (uniformly), except for | |
1962 | * non-Unicode code points and things in the General Category "Other" | |
1963 | * (unassigned, private use, surrogates, controls and formats). This | |
1964 | * is a much large number. */ | |
1965 | ||
b35552de KW |
1966 | U32 count = 0; /* Running total of number of code points matched by |
1967 | 'ssc' */ | |
1968 | UV start, end; /* Start and end points of current range in inversion | |
1969 | list */ | |
72400949 KW |
1970 | const U32 max_code_points = (LOC) |
1971 | ? 256 | |
1972 | : (( ! UNI_SEMANTICS | |
1973 | || invlist_highest(ssc->invlist) < 256) | |
1974 | ? 128 | |
1975 | : NON_OTHER_COUNT); | |
1976 | const U32 max_match = max_code_points / 2; | |
b35552de KW |
1977 | |
1978 | PERL_ARGS_ASSERT_IS_SSC_WORTH_IT; | |
1979 | ||
1980 | invlist_iterinit(ssc->invlist); | |
1981 | while (invlist_iternext(ssc->invlist, &start, &end)) { | |
72400949 KW |
1982 | if (start >= max_code_points) { |
1983 | break; | |
b35552de | 1984 | } |
72400949 | 1985 | end = MIN(end, max_code_points - 1); |
b35552de | 1986 | count += end - start + 1; |
72400949 | 1987 | if (count >= max_match) { |
b35552de KW |
1988 | invlist_iterfinish(ssc->invlist); |
1989 | return FALSE; | |
1990 | } | |
1991 | } | |
1992 | ||
1993 | return TRUE; | |
1994 | } | |
1995 | ||
1996 | ||
b423522f KW |
1997 | STATIC void |
1998 | S_ssc_finalize(pTHX_ RExC_state_t *pRExC_state, regnode_ssc *ssc) | |
1999 | { | |
2000 | /* The inversion list in the SSC is marked mortal; now we need a more | |
2001 | * permanent copy, which is stored the same way that is done in a regular | |
dcb20b36 KW |
2002 | * ANYOF node, with the first NUM_ANYOF_CODE_POINTS code points in a bit |
2003 | * map */ | |
b423522f | 2004 | |
28118b9c | 2005 | SV* invlist = invlist_clone(ssc->invlist, NULL); |
b423522f KW |
2006 | |
2007 | PERL_ARGS_ASSERT_SSC_FINALIZE; | |
2008 | ||
71068078 | 2009 | assert(is_ANYOF_SYNTHETIC(ssc)); |
b423522f | 2010 | |
a0dd4231 | 2011 | /* The code in this file assumes that all but these flags aren't relevant |
93e92956 KW |
2012 | * to the SSC, except SSC_MATCHES_EMPTY_STRING, which should be cleared |
2013 | * by the time we reach here */ | |
f240c685 KW |
2014 | assert(! (ANYOF_FLAGS(ssc) |
2015 | & ~( ANYOF_COMMON_FLAGS | |
108316fb KW |
2016 | |ANYOF_SHARED_d_MATCHES_ALL_NON_UTF8_NON_ASCII_non_d_WARN_SUPER |
2017 | |ANYOF_SHARED_d_UPPER_LATIN1_UTF8_STRING_MATCHES_non_d_RUNTIME_USER_PROP))); | |
a0dd4231 | 2018 | |
b423522f KW |
2019 | populate_ANYOF_from_invlist( (regnode *) ssc, &invlist); |
2020 | ||
1ee208c4 KW |
2021 | set_ANYOF_arg(pRExC_state, (regnode *) ssc, invlist, |
2022 | NULL, NULL, NULL, FALSE); | |
b423522f | 2023 | |
85c8e306 KW |
2024 | /* Make sure is clone-safe */ |
2025 | ssc->invlist = NULL; | |
2026 | ||
e0e1be5f | 2027 | if (ANYOF_POSIXL_SSC_TEST_ANY_SET(ssc)) { |
93e92956 | 2028 | ANYOF_FLAGS(ssc) |= ANYOF_MATCHES_POSIXL; |
e0e1be5f | 2029 | } |
1462525b | 2030 | |
b2e90ddf KW |
2031 | if (RExC_contains_locale) { |
2032 | OP(ssc) = ANYOFL; | |
2033 | } | |
2034 | ||
1462525b | 2035 | assert(! (ANYOF_FLAGS(ssc) & ANYOF_LOCALE_FLAGS) || RExC_contains_locale); |
b423522f KW |
2036 | } |
2037 | ||
a3621e74 YO |
2038 | #define TRIE_LIST_ITEM(state,idx) (trie->states[state].trans.list)[ idx ] |
2039 | #define TRIE_LIST_CUR(state) ( TRIE_LIST_ITEM( state, 0 ).forid ) | |
2040 | #define TRIE_LIST_LEN(state) ( TRIE_LIST_ITEM( state, 0 ).newstate ) | |
538e84ed KW |
2041 | #define TRIE_LIST_USED(idx) ( trie->states[state].trans.list \ |
2042 | ? (TRIE_LIST_CUR( idx ) - 1) \ | |
2043 | : 0 ) | |
a3621e74 | 2044 | |
3dab1dad YO |
2045 | |
2046 | #ifdef DEBUGGING | |
07be1b83 | 2047 | /* |
2b8b4781 NC |
2048 | dump_trie(trie,widecharmap,revcharmap) |
2049 | dump_trie_interim_list(trie,widecharmap,revcharmap,next_alloc) | |
2050 | dump_trie_interim_table(trie,widecharmap,revcharmap,next_alloc) | |
3dab1dad YO |
2051 | |
2052 | These routines dump out a trie in a somewhat readable format. | |
07be1b83 YO |
2053 | The _interim_ variants are used for debugging the interim |
2054 | tables that are used to generate the final compressed | |
2055 | representation which is what dump_trie expects. | |
2056 | ||
486ec47a | 2057 | Part of the reason for their existence is to provide a form |
3dab1dad | 2058 | of documentation as to how the different representations function. |
07be1b83 YO |
2059 | |
2060 | */ | |
3dab1dad YO |
2061 | |
2062 | /* | |
3dab1dad YO |
2063 | Dumps the final compressed table form of the trie to Perl_debug_log. |
2064 | Used for debugging make_trie(). | |
2065 | */ | |
b9a59e08 | 2066 | |
3dab1dad | 2067 | STATIC void |
2b8b4781 NC |
2068 | S_dump_trie(pTHX_ const struct _reg_trie_data *trie, HV *widecharmap, |
2069 | AV *revcharmap, U32 depth) | |
3dab1dad YO |
2070 | { |
2071 | U32 state; | |
ab3bbdeb | 2072 | SV *sv=sv_newmortal(); |
55eed653 | 2073 | int colwidth= widecharmap ? 6 : 4; |
2e64971a | 2074 | U16 word; |
3dab1dad YO |
2075 | GET_RE_DEBUG_FLAGS_DECL; |
2076 | ||
7918f24d | 2077 | PERL_ARGS_ASSERT_DUMP_TRIE; |
ab3bbdeb | 2078 | |
6ad9a8ab | 2079 | Perl_re_indentf( aTHX_ "Char : %-6s%-6s%-4s ", |
1e37780e | 2080 | depth+1, "Match","Base","Ofs" ); |
3dab1dad YO |
2081 | |
2082 | for( state = 0 ; state < trie->uniquecharcount ; state++ ) { | |
2b8b4781 | 2083 | SV ** const tmp = av_fetch( revcharmap, state, 0); |
3dab1dad | 2084 | if ( tmp ) { |
6ad9a8ab | 2085 | Perl_re_printf( aTHX_ "%*s", |
ab3bbdeb | 2086 | colwidth, |
538e84ed | 2087 | pv_pretty(sv, SvPV_nolen_const(*tmp), SvCUR(*tmp), colwidth, |
ab3bbdeb YO |
2088 | PL_colors[0], PL_colors[1], |
2089 | (SvUTF8(*tmp) ? PERL_PV_ESCAPE_UNI : 0) | | |
538e84ed KW |
2090 | PERL_PV_ESCAPE_FIRSTCHAR |
2091 | ) | |
ab3bbdeb | 2092 | ); |
3dab1dad YO |
2093 | } |
2094 | } | |
1e37780e YO |
2095 | Perl_re_printf( aTHX_ "\n"); |
2096 | Perl_re_indentf( aTHX_ "State|-----------------------", depth+1); | |
3dab1dad YO |
2097 | |
2098 | for( state = 0 ; state < trie->uniquecharcount ; state++ ) | |
6ad9a8ab YO |
2099 | Perl_re_printf( aTHX_ "%.*s", colwidth, "--------"); |
2100 | Perl_re_printf( aTHX_ "\n"); | |
3dab1dad | 2101 | |
1e2e3d02 | 2102 | for( state = 1 ; state < trie->statecount ; state++ ) { |
be8e71aa | 2103 | const U32 base = trie->states[ state ].trans.base; |
3dab1dad | 2104 | |
147e3846 | 2105 | Perl_re_indentf( aTHX_ "#%4" UVXf "|", depth+1, (UV)state); |
3dab1dad YO |
2106 | |
2107 | if ( trie->states[ state ].wordnum ) { | |
1e37780e | 2108 | Perl_re_printf( aTHX_ " W%4X", trie->states[ state ].wordnum ); |
3dab1dad | 2109 | } else { |
6ad9a8ab | 2110 | Perl_re_printf( aTHX_ "%6s", "" ); |
3dab1dad YO |
2111 | } |
2112 | ||
147e3846 | 2113 | Perl_re_printf( aTHX_ " @%4" UVXf " ", (UV)base ); |
3dab1dad YO |
2114 | |
2115 | if ( base ) { | |
2116 | U32 ofs = 0; | |
2117 | ||
2118 | while( ( base + ofs < trie->uniquecharcount ) || | |
2119 | ( base + ofs - trie->uniquecharcount < trie->lasttrans | |
538e84ed KW |
2120 | && trie->trans[ base + ofs - trie->uniquecharcount ].check |
2121 | != state)) | |
3dab1dad YO |
2122 | ofs++; |
2123 | ||
147e3846 | 2124 | Perl_re_printf( aTHX_ "+%2" UVXf "[ ", (UV)ofs); |
3dab1dad YO |
2125 | |
2126 | for ( ofs = 0 ; ofs < trie->uniquecharcount ; ofs++ ) { | |
538e84ed KW |
2127 | if ( ( base + ofs >= trie->uniquecharcount ) |
2128 | && ( base + ofs - trie->uniquecharcount | |
2129 | < trie->lasttrans ) | |
2130 | && trie->trans[ base + ofs | |
2131 | - trie->uniquecharcount ].check == state ) | |
3dab1dad | 2132 | { |
147e3846 | 2133 | Perl_re_printf( aTHX_ "%*" UVXf, colwidth, |
1e37780e YO |
2134 | (UV)trie->trans[ base + ofs - trie->uniquecharcount ].next |
2135 | ); | |
3dab1dad | 2136 | } else { |
6ad9a8ab | 2137 | Perl_re_printf( aTHX_ "%*s",colwidth," ." ); |
3dab1dad YO |
2138 | } |
2139 | } | |
2140 | ||
6ad9a8ab | 2141 | Perl_re_printf( aTHX_ "]"); |
3dab1dad YO |
2142 | |
2143 | } | |
6ad9a8ab | 2144 | Perl_re_printf( aTHX_ "\n" ); |
3dab1dad | 2145 | } |
6ad9a8ab | 2146 | Perl_re_indentf( aTHX_ "word_info N:(prev,len)=", |
cb41e5d6 | 2147 | depth); |
2e64971a | 2148 | for (word=1; word <= trie->wordcount; word++) { |
6ad9a8ab | 2149 | Perl_re_printf( aTHX_ " %d:(%d,%d)", |
2e64971a DM |
2150 | (int)word, (int)(trie->wordinfo[word].prev), |
2151 | (int)(trie->wordinfo[word].len)); | |
2152 | } | |
6ad9a8ab | 2153 | Perl_re_printf( aTHX_ "\n" ); |
538e84ed | 2154 | } |
3dab1dad | 2155 | /* |
3dab1dad | 2156 | Dumps a fully constructed but uncompressed trie in list form. |
538e84ed | 2157 | List tries normally only are used for construction when the number of |
3dab1dad YO |
2158 | possible chars (trie->uniquecharcount) is very high. |
2159 | Used for debugging make_trie(). | |
2160 | */ | |
2161 | STATIC void | |
55eed653 | 2162 | S_dump_trie_interim_list(pTHX_ const struct _reg_trie_data *trie, |
2b8b4781 NC |
2163 | HV *widecharmap, AV *revcharmap, U32 next_alloc, |
2164 | U32 depth) | |
3dab1dad YO |
2165 | { |
2166 | U32 state; | |
ab3bbdeb | 2167 | SV *sv=sv_newmortal(); |
55eed653 | 2168 | int colwidth= widecharmap ? 6 : 4; |
3dab1dad | 2169 | GET_RE_DEBUG_FLAGS_DECL; |
7918f24d NC |
2170 | |
2171 | PERL_ARGS_ASSERT_DUMP_TRIE_INTERIM_LIST; | |
2172 | ||
3dab1dad | 2173 | /* print out the table precompression. */ |
6ad9a8ab | 2174 | Perl_re_indentf( aTHX_ "State :Word | Transition Data\n", |
cb41e5d6 | 2175 | depth+1 ); |
6ad9a8ab | 2176 | Perl_re_indentf( aTHX_ "%s", |
cb41e5d6 | 2177 | depth+1, "------:-----+-----------------\n" ); |
538e84ed | 2178 | |
3dab1dad YO |
2179 | for( state=1 ; state < next_alloc ; state ++ ) { |
2180 | U16 charid; | |
538e84ed | 2181 | |
147e3846 | 2182 | Perl_re_indentf( aTHX_ " %4" UVXf " :", |
cb41e5d6 | 2183 | depth+1, (UV)state ); |
3dab1dad | 2184 | if ( ! trie->states[ state ].wordnum ) { |
6ad9a8ab | 2185 | Perl_re_printf( aTHX_ "%5s| ",""); |
3dab1dad | 2186 | } else { |
6ad9a8ab | 2187 | Perl_re_printf( aTHX_ "W%4x| ", |
3dab1dad YO |
2188 | trie->states[ state ].wordnum |
2189 | ); | |
2190 | } | |
2191 | for( charid = 1 ; charid <= TRIE_LIST_USED( state ) ; charid++ ) { | |
538e84ed KW |
2192 | SV ** const tmp = av_fetch( revcharmap, |
2193 | TRIE_LIST_ITEM(state,charid).forid, 0); | |
ab3bbdeb | 2194 | if ( tmp ) { |
147e3846 | 2195 | Perl_re_printf( aTHX_ "%*s:%3X=%4" UVXf " | ", |
ab3bbdeb | 2196 | colwidth, |
538e84ed KW |
2197 | pv_pretty(sv, SvPV_nolen_const(*tmp), SvCUR(*tmp), |
2198 | colwidth, | |
2199 | PL_colors[0], PL_colors[1], | |
2200 | (SvUTF8(*tmp) ? PERL_PV_ESCAPE_UNI : 0) | |
2201 | | PERL_PV_ESCAPE_FIRSTCHAR | |
ab3bbdeb | 2202 | ) , |
1e2e3d02 YO |
2203 | TRIE_LIST_ITEM(state,charid).forid, |
2204 | (UV)TRIE_LIST_ITEM(state,charid).newstate | |
2205 | ); | |
538e84ed | 2206 | if (!(charid % 10)) |
6ad9a8ab | 2207 | Perl_re_printf( aTHX_ "\n%*s| ", |
664e119d | 2208 | (int)((depth * 2) + 14), ""); |
1e2e3d02 | 2209 | } |
ab3bbdeb | 2210 | } |
6ad9a8ab | 2211 | Perl_re_printf( aTHX_ "\n"); |
3dab1dad | 2212 | } |
538e84ed | 2213 | } |
3dab1dad YO |
2214 | |
2215 | /* | |
3dab1dad | 2216 | Dumps a fully constructed but uncompressed trie in table form. |
538e84ed KW |
2217 | This is the normal DFA style state transition table, with a few |
2218 | twists to facilitate compression later. | |
3dab1dad YO |
2219 | Used for debugging make_trie(). |
2220 | */ | |
2221 | STATIC void | |
55eed653 | 2222 | S_dump_trie_interim_table(pTHX_ const struct _reg_trie_data *trie, |
2b8b4781 NC |
2223 | HV *widecharmap, AV *revcharmap, U32 next_alloc, |
2224 | U32 depth) | |
3dab1dad YO |
2225 | { |
2226 | U32 state; | |
2227 | U16 charid; | |
ab3bbdeb | 2228 | SV *sv=sv_newmortal(); |
55eed653 | 2229 | int colwidth= widecharmap ? 6 : 4; |
3dab1dad | 2230 | GET_RE_DEBUG_FLAGS_DECL; |
7918f24d NC |
2231 | |
2232 | PERL_ARGS_ASSERT_DUMP_TRIE_INTERIM_TABLE; | |
538e84ed | 2233 | |
3dab1dad YO |
2234 | /* |
2235 | print out the table precompression so that we can do a visual check | |
2236 | that they are identical. | |
2237 | */ | |
538e84ed | 2238 | |
6ad9a8ab | 2239 | Perl_re_indentf( aTHX_ "Char : ", depth+1 ); |
3dab1dad YO |
2240 | |
2241 | for( charid = 0 ; charid < trie->uniquecharcount ; charid++ ) { | |
2b8b4781 | 2242 | SV ** const tmp = av_fetch( revcharmap, charid, 0); |
3dab1dad | 2243 | if ( tmp ) { |
6ad9a8ab | 2244 | Perl_re_printf( aTHX_ "%*s", |
ab3bbdeb | 2245 | colwidth, |
538e84ed | 2246 | pv_pretty(sv, SvPV_nolen_const(*tmp), SvCUR(*tmp), colwidth, |
ab3bbdeb YO |
2247 | PL_colors[0], PL_colors[1], |
2248 | (SvUTF8(*tmp) ? PERL_PV_ESCAPE_UNI : 0) | | |
538e84ed KW |
2249 | PERL_PV_ESCAPE_FIRSTCHAR |
2250 | ) | |
ab3bbdeb | 2251 | ); |
3dab1dad YO |
2252 | } |
2253 | } | |
2254 | ||
4aaafc03 YO |
2255 | Perl_re_printf( aTHX_ "\n"); |
2256 | Perl_re_indentf( aTHX_ "State+-", depth+1 ); | |
3dab1dad YO |
2257 | |
2258 | for( charid=0 ; charid < trie->uniquecharcount ; charid++ ) { | |
6ad9a8ab | 2259 | Perl_re_printf( aTHX_ "%.*s", colwidth,"--------"); |
3dab1dad YO |
2260 | } |
2261 | ||
6ad9a8ab | 2262 | Perl_re_printf( aTHX_ "\n" ); |
3dab1dad YO |
2263 | |
2264 | for( state=1 ; state < next_alloc ; state += trie->uniquecharcount ) { | |
2265 | ||
147e3846 | 2266 | Perl_re_indentf( aTHX_ "%4" UVXf " : ", |
cb41e5d6 | 2267 | depth+1, |
3dab1dad YO |
2268 | (UV)TRIE_NODENUM( state ) ); |
2269 | ||
2270 | for( charid = 0 ; charid < trie->uniquecharcount ; charid++ ) { | |
ab3bbdeb YO |
2271 | UV v=(UV)SAFE_TRIE_NODENUM( trie->trans[ state + charid ].next ); |
2272 | if (v) | |
147e3846 | 2273 | Perl_re_printf( aTHX_ "%*" UVXf, colwidth, v ); |
ab3bbdeb | 2274 | else |
6ad9a8ab | 2275 | Perl_re_printf( aTHX_ "%*s", colwidth, "." ); |
3dab1dad YO |
2276 | } |
2277 | if ( ! trie->states[ TRIE_NODENUM( state ) ].wordnum ) { | |
147e3846 | 2278 | Perl_re_printf( aTHX_ " (%4" UVXf ")\n", |
538e84ed | 2279 | (UV)trie->trans[ state ].check ); |
3dab1dad | 2280 | } else { |
147e3846 | 2281 | Perl_re_printf( aTHX_ " (%4" UVXf ") W%4X\n", |
538e84ed | 2282 | (UV)trie->trans[ state ].check, |
3dab1dad YO |
2283 | trie->states[ TRIE_NODENUM( state ) ].wordnum ); |
2284 | } | |
2285 | } | |
07be1b83 | 2286 | } |
3dab1dad YO |
2287 | |
2288 | #endif | |
2289 | ||
2e64971a | 2290 | |
786e8c11 YO |
2291 | /* make_trie(startbranch,first,last,tail,word_count,flags,depth) |
2292 | startbranch: the first branch in the whole branch sequence | |
2293 | first : start branch of sequence of branch-exact nodes. | |
2294 | May be the same as startbranch | |
2295 | last : Thing following the last branch. | |
2296 | May be the same as tail. | |
2297 | tail : item following the branch sequence | |
2298 | count : words in the sequence | |
a4525e78 | 2299 | flags : currently the OP() type we will be building one of /EXACT(|F|FA|FU|FU_SS|L|FLU8)/ |
786e8c11 | 2300 | depth : indent depth |
3dab1dad | 2301 | |
786e8c11 | 2302 | Inplace optimizes a sequence of 2 or more Branch-Exact nodes into a TRIE node. |
07be1b83 | 2303 | |
786e8c11 YO |
2304 | A trie is an N'ary tree where the branches are determined by digital |
2305 | decomposition of the key. IE, at the root node you look up the 1st character and | |
2306 | follow that branch repeat until you find the end of the branches. Nodes can be | |
2307 | marked as "accepting" meaning they represent a complete word. Eg: | |
07be1b83 | 2308 | |
786e8c11 | 2309 | /he|she|his|hers/ |
72f13be8 | 2310 | |
786e8c11 YO |
2311 | would convert into the following structure. Numbers represent states, letters |
2312 | following numbers represent valid transitions on the letter from that state, if | |
2313 | the number is in square brackets it represents an accepting state, otherwise it | |
2314 | will be in parenthesis. | |
07be1b83 | 2315 | |
786e8c11 YO |
2316 | +-h->+-e->[3]-+-r->(8)-+-s->[9] |
2317 | | | | |
2318 | | (2) | |
2319 | | | | |
2320 | (1) +-i->(6)-+-s->[7] | |
2321 | | | |
2322 | +-s->(3)-+-h->(4)-+-e->[5] | |
07be1b83 | 2323 | |
786e8c11 YO |
2324 | Accept Word Mapping: 3=>1 (he),5=>2 (she), 7=>3 (his), 9=>4 (hers) |
2325 | ||
2326 | This shows that when matching against the string 'hers' we will begin at state 1 | |
2327 | read 'h' and move to state 2, read 'e' and move to state 3 which is accepting, | |
2328 | then read 'r' and go to state 8 followed by 's' which takes us to state 9 which | |
2329 | is also accepting. Thus we know that we can match both 'he' and 'hers' with a | |
2330 | single traverse. We store a mapping from accepting to state to which word was | |
2331 | matched, and then when we have multiple possibilities we try to complete the | |
b8fda935 | 2332 | rest of the regex in the order in which they occurred in the alternation. |
786e8c11 YO |
2333 | |
2334 | The only prior NFA like behaviour that would be changed by the TRIE support is | |
2335 | the silent ignoring of duplicate alternations which are of the form: | |
2336 | ||
2337 | / (DUPE|DUPE) X? (?{ ... }) Y /x | |
2338 | ||
4b714af6 | 2339 | Thus EVAL blocks following a trie may be called a different number of times with |
786e8c11 | 2340 | and without the optimisation. With the optimisations dupes will be silently |
486ec47a | 2341 | ignored. This inconsistent behaviour of EVAL type nodes is well established as |
786e8c11 YO |
2342 | the following demonstrates: |
2343 | ||
2344 | 'words'=~/(word|word|word)(?{ print $1 })[xyz]/ | |
2345 | ||
2346 | which prints out 'word' three times, but | |
2347 | ||
2348 | 'words'=~/(word|word|word)(?{ print $1 })S/ | |
2349 | ||
2350 | which doesnt print it out at all. This is due to other optimisations kicking in. | |
2351 | ||
2352 | Example of what happens on a structural level: | |
2353 | ||
486ec47a | 2354 | The regexp /(ac|ad|ab)+/ will produce the following debug output: |
786e8c11 YO |
2355 | |
2356 | 1: CURLYM[1] {1,32767}(18) | |
2357 | 5: BRANCH(8) | |
2358 | 6: EXACT <ac>(16) | |
2359 | 8: BRANCH(11) | |
2360 | 9: EXACT <ad>(16) | |
2361 | 11: BRANCH(14) | |
2362 | 12: EXACT <ab>(16) | |
2363 | 16: SUCCEED(0) | |
2364 | 17: NOTHING(18) | |
2365 | 18: END(0) | |
2366 | ||
2367 | This would be optimizable with startbranch=5, first=5, last=16, tail=16 | |
2368 | and should turn into: | |
2369 | ||
2370 | 1: CURLYM[1] {1,32767}(18) | |
2371 | 5: TRIE(16) | |
2372 | [Words:3 Chars Stored:6 Unique Chars:4 States:5 NCP:1] | |
2373 | <ac> | |
2374 | <ad> | |
2375 | <ab> | |
2376 | 16: SUCCEED(0) | |
2377 | 17: NOTHING(18) | |
2378 | 18: END(0) | |
2379 | ||
2380 | Cases where tail != last would be like /(?foo|bar)baz/: | |
2381 | ||
2382 | 1: BRANCH(4) | |
2383 | 2: EXACT <foo>(8) | |
2384 | 4: BRANCH(7) | |
2385 | 5: EXACT <bar>(8) | |
2386 | 7: TAIL(8) | |
2387 | 8: EXACT <baz>(10) | |
2388 | 10: END(0) | |
2389 | ||
2390 | which would be optimizable with startbranch=1, first=1, last=7, tail=8 | |
2391 | and would end up looking like: | |
2392 | ||
2393 | 1: TRIE(8) | |
2394 | [Words:2 Chars Stored:6 Unique Chars:5 States:7 NCP:1] | |
2395 | <foo> | |
2396 | <bar> | |
2397 | 7: TAIL(8) | |
2398 | 8: EXACT <baz>(10) | |
2399 | 10: END(0) | |
2400 | ||
c80e42f3 | 2401 | d = uvchr_to_utf8_flags(d, uv, 0); |
786e8c11 YO |
2402 | |
2403 | is the recommended Unicode-aware way of saying | |
2404 | ||
2405 | *(d++) = uv; | |
2406 | */ | |
2407 | ||
fab2782b | 2408 | #define TRIE_STORE_REVCHAR(val) \ |
786e8c11 | 2409 | STMT_START { \ |
73031816 | 2410 | if (UTF) { \ |
668fcfea | 2411 | SV *zlopp = newSV(UTF8_MAXBYTES); \ |
88c9ea1e | 2412 | unsigned char *flrbbbbb = (unsigned char *) SvPVX(zlopp); \ |
c80e42f3 | 2413 | unsigned const char *const kapow = uvchr_to_utf8(flrbbbbb, val); \ |
73031816 NC |
2414 | SvCUR_set(zlopp, kapow - flrbbbbb); \ |
2415 | SvPOK_on(zlopp); \ | |
2416 | SvUTF8_on(zlopp); \ | |
2417 | av_push(revcharmap, zlopp); \ | |
2418 | } else { \ | |
fab2782b | 2419 | char ooooff = (char)val; \ |
73031816 NC |
2420 | av_push(revcharmap, newSVpvn(&ooooff, 1)); \ |
2421 | } \ | |
2422 | } STMT_END | |
786e8c11 | 2423 | |
914a25d5 KW |
2424 | /* This gets the next character from the input, folding it if not already |
2425 | * folded. */ | |
2426 | #define TRIE_READ_CHAR STMT_START { \ | |
2427 | wordlen++; \ | |
2428 | if ( UTF ) { \ | |
2429 | /* if it is UTF then it is either already folded, or does not need \ | |
2430 | * folding */ \ | |
1c1d615a | 2431 | uvc = valid_utf8_to_uvchr( (const U8*) uc, &len); \ |
914a25d5 KW |
2432 | } \ |
2433 | else if (folder == PL_fold_latin1) { \ | |
7d006b13 KW |
2434 | /* This folder implies Unicode rules, which in the range expressible \ |
2435 | * by not UTF is the lower case, with the two exceptions, one of \ | |
2436 | * which should have been taken care of before calling this */ \ | |
2437 | assert(*uc != LATIN_SMALL_LETTER_SHARP_S); \ | |
2438 | uvc = toLOWER_L1(*uc); \ | |
2439 | if (UNLIKELY(uvc == MICRO_SIGN)) uvc = GREEK_SMALL_LETTER_MU; \ | |
2440 | len = 1; \ | |
914a25d5 KW |
2441 | } else { \ |
2442 | /* raw data, will be folded later if needed */ \ | |
2443 | uvc = (U32)*uc; \ | |
2444 | len = 1; \ | |
2445 | } \ | |
786e8c11 YO |
2446 | } STMT_END |
2447 | ||
2448 | ||
2449 | ||
2450 | #define TRIE_LIST_PUSH(state,fid,ns) STMT_START { \ | |
2451 | if ( TRIE_LIST_CUR( state ) >=TRIE_LIST_LEN( state ) ) { \ | |
00195859 | 2452 | U32 ging = TRIE_LIST_LEN( state ) * 2; \ |
f9003953 | 2453 | Renew( trie->states[ state ].trans.list, ging, reg_trie_trans_le ); \ |
00195859 | 2454 | TRIE_LIST_LEN( state ) = ging; \ |
786e8c11 YO |
2455 | } \ |
2456 | TRIE_LIST_ITEM( state, TRIE_LIST_CUR( state ) ).forid = fid; \ | |
2457 | TRIE_LIST_ITEM( state, TRIE_LIST_CUR( state ) ).newstate = ns; \ | |
2458 | TRIE_LIST_CUR( state )++; \ | |
2459 | } STMT_END | |
07be1b83 | 2460 | |
786e8c11 | 2461 | #define TRIE_LIST_NEW(state) STMT_START { \ |
d09f14bf | 2462 | Newx( trie->states[ state ].trans.list, \ |
786e8c11 YO |
2463 | 4, reg_trie_trans_le ); \ |
2464 | TRIE_LIST_CUR( state ) = 1; \ | |
2465 | TRIE_LIST_LEN( state ) = 4; \ | |
2466 | } STMT_END | |
07be1b83 | 2467 | |
786e8c11 YO |
2468 | #define TRIE_HANDLE_WORD(state) STMT_START { \ |
2469 | U16 dupe= trie->states[ state ].wordnum; \ | |
2470 | regnode * const noper_next = regnext( noper ); \ | |
2471 | \ | |
786e8c11 YO |
2472 | DEBUG_r({ \ |
2473 | /* store the word for dumping */ \ | |
2474 | SV* tmp; \ | |
2475 | if (OP(noper) != NOTHING) \ | |
740cce10 | 2476 | tmp = newSVpvn_utf8(STRING(noper), STR_LEN(noper), UTF); \ |
786e8c11 | 2477 | else \ |
740cce10 | 2478 | tmp = newSVpvn_utf8( "", 0, UTF ); \ |
2b8b4781 | 2479 | av_push( trie_words, tmp ); \ |
786e8c11 YO |
2480 | }); \ |
2481 | \ | |
2482 | curword++; \ | |
2e64971a DM |
2483 | trie->wordinfo[curword].prev = 0; \ |
2484 | trie->wordinfo[curword].len = wordlen; \ | |
2485 | trie->wordinfo[curword].accept = state; \ | |
786e8c11 YO |
2486 | \ |
2487 | if ( noper_next < tail ) { \ | |
2488 | if (!trie->jump) \ | |
538e84ed KW |
2489 | trie->jump = (U16 *) PerlMemShared_calloc( word_count + 1, \ |
2490 | sizeof(U16) ); \ | |
7f69552c | 2491 | trie->jump[curword] = (U16)(noper_next - convert); \ |
786e8c11 YO |
2492 | if (!jumper) \ |
2493 | jumper = noper_next; \ | |
2494 | if (!nextbranch) \ | |
2495 | nextbranch= regnext(cur); \ | |
2496 | } \ | |
2497 | \ | |
2498 | if ( dupe ) { \ | |
2e64971a DM |
2499 | /* It's a dupe. Pre-insert into the wordinfo[].prev */\ |
2500 | /* chain, so that when the bits of chain are later */\ | |
2501 | /* linked together, the dups appear in the chain */\ | |
2502 | trie->wordinfo[curword].prev = trie->wordinfo[dupe].prev; \ | |
2503 | trie->wordinfo[dupe].prev = curword; \ | |
786e8c11 YO |
2504 | } else { \ |
2505 | /* we haven't inserted this word yet. */ \ | |
2506 | trie->states[ state ].wordnum = curword; \ | |
2507 | } \ | |
2508 | } STMT_END | |
07be1b83 | 2509 | |
3dab1dad | 2510 | |
786e8c11 YO |
2511 | #define TRIE_TRANS_STATE(state,base,ucharcount,charid,special) \ |
2512 | ( ( base + charid >= ucharcount \ | |
2513 | && base + charid < ubound \ | |
2514 | && state == trie->trans[ base - ucharcount + charid ].check \ | |
2515 | && trie->trans[ base - ucharcount + charid ].next ) \ | |
2516 | ? trie->trans[ base - ucharcount + charid ].next \ | |
2517 | : ( state==1 ? special : 0 ) \ | |
2518 | ) | |
3dab1dad | 2519 | |
8bcafbf4 YO |
2520 | #define TRIE_BITMAP_SET_FOLDED(trie, uvc, folder) \ |
2521 | STMT_START { \ | |
2522 | TRIE_BITMAP_SET(trie, uvc); \ | |
2523 | /* store the folded codepoint */ \ | |
2524 | if ( folder ) \ | |
2525 | TRIE_BITMAP_SET(trie, folder[(U8) uvc ]); \ | |
2526 | \ | |
2527 | if ( !UTF ) { \ | |
2528 | /* store first byte of utf8 representation of */ \ | |
2529 | /* variant codepoints */ \ | |
2530 | if (! UVCHR_IS_INVARIANT(uvc)) { \ | |
2531 | TRIE_BITMAP_SET(trie, UTF8_TWO_BYTE_HI(uvc)); \ | |
2532 | } \ | |
2533 | } \ | |
2534 | } STMT_END | |
786e8c11 YO |
2535 | #define MADE_TRIE 1 |
2536 | #define MADE_JUMP_TRIE 2 | |
2537 | #define MADE_EXACT_TRIE 4 | |
3dab1dad | 2538 | |
a3621e74 | 2539 | STATIC I32 |
538e84ed KW |
2540 | S_make_trie(pTHX_ RExC_state_t *pRExC_state, regnode *startbranch, |
2541 | regnode *first, regnode *last, regnode *tail, | |
2542 | U32 word_count, U32 flags, U32 depth) | |
a3621e74 YO |
2543 | { |
2544 | /* first pass, loop through and scan words */ | |
2545 | reg_trie_data *trie; | |
55eed653 | 2546 | HV *widecharmap = NULL; |
2b8b4781 | 2547 | AV *revcharmap = newAV(); |
a3621e74 | 2548 | regnode *cur; |
a3621e74 YO |
2549 | STRLEN len = 0; |
2550 | UV uvc = 0; | |
2551 | U16 curword = 0; | |
2552 | U32 next_alloc = 0; | |
786e8c11 YO |
2553 | regnode *jumper = NULL; |
2554 | regnode *nextbranch = NULL; | |
7f69552c | 2555 | regnode *convert = NULL; |
2e64971a | 2556 | U32 *prev_states; /* temp array mapping each state to previous one */ |
a3621e74 | 2557 | /* we just use folder as a flag in utf8 */ |
1e696034 | 2558 | const U8 * folder = NULL; |
a3621e74 | 2559 | |
3a611511 YO |
2560 | /* in the below add_data call we are storing either 'tu' or 'tuaa' |
2561 | * which stands for one trie structure, one hash, optionally followed | |
2562 | * by two arrays */ | |
2b8b4781 | 2563 | #ifdef DEBUGGING |
3a611511 | 2564 | const U32 data_slot = add_data( pRExC_state, STR_WITH_LEN("tuaa")); |
2b8b4781 NC |
2565 | AV *trie_words = NULL; |
2566 | /* along with revcharmap, this only used during construction but both are | |
2567 | * useful during debugging so we store them in the struct when debugging. | |
8e11feef | 2568 | */ |
2b8b4781 | 2569 | #else |
cf78de0b | 2570 | const U32 data_slot = add_data( pRExC_state, STR_WITH_LEN("tu")); |
3dab1dad | 2571 | STRLEN trie_charcount=0; |
3dab1dad | 2572 | #endif |
2b8b4781 | 2573 | SV *re_trie_maxbuff; |
a3621e74 | 2574 | GET_RE_DEBUG_FLAGS_DECL; |
7918f24d NC |
2575 | |
2576 | PERL_ARGS_ASSERT_MAKE_TRIE; | |
72f13be8 YO |
2577 | #ifndef DEBUGGING |
2578 | PERL_UNUSED_ARG(depth); | |
2579 | #endif | |
a3621e74 | 2580 | |
1e696034 | 2581 | switch (flags) { |
a4525e78 | 2582 | case EXACT: case EXACTL: break; |
89829bb5 | 2583 | case EXACTFAA: |
fab2782b | 2584 | case EXACTFU_SS: |
a4525e78 KW |
2585 | case EXACTFU: |
2586 | case EXACTFLU8: folder = PL_fold_latin1; break; | |
1e696034 | 2587 | case EXACTF: folder = PL_fold; break; |
fab2782b | 2588 | default: Perl_croak( aTHX_ "panic! In trie construction, unknown node type %u %s", (unsigned) flags, PL_reg_name[flags] ); |
1e696034 KW |
2589 | } |
2590 | ||
c944940b | 2591 | trie = (reg_trie_data *) PerlMemShared_calloc( 1, sizeof(reg_trie_data) ); |
a3621e74 | 2592 | trie->refcount = 1; |
3dab1dad | 2593 | trie->startstate = 1; |
786e8c11 | 2594 | trie->wordcount = word_count; |
f8fc2ecf | 2595 | RExC_rxi->data->data[ data_slot ] = (void*)trie; |
c944940b | 2596 | trie->charmap = (U16 *) PerlMemShared_calloc( 256, sizeof(U16) ); |
a4525e78 | 2597 | if (flags == EXACT || flags == EXACTL) |
c944940b | 2598 | trie->bitmap = (char *) PerlMemShared_calloc( ANYOF_BITMAP_SIZE, 1 ); |
2e64971a DM |
2599 | trie->wordinfo = (reg_trie_wordinfo *) PerlMemShared_calloc( |
2600 | trie->wordcount+1, sizeof(reg_trie_wordinfo)); | |
2601 | ||
a3621e74 | 2602 | DEBUG_r({ |
2b8b4781 | 2603 | trie_words = newAV(); |
a3621e74 | 2604 | }); |
a3621e74 | 2605 | |
0111c4fd | 2606 | re_trie_maxbuff = get_sv(RE_TRIE_MAXBUF_NAME, 1); |
316ebaf2 | 2607 | assert(re_trie_maxbuff); |
a3621e74 | 2608 | if (!SvIOK(re_trie_maxbuff)) { |
0111c4fd | 2609 | sv_setiv(re_trie_maxbuff, RE_TRIE_MAXBUF_INIT); |
a3621e74 | 2610 | } |
df826430 | 2611 | DEBUG_TRIE_COMPILE_r({ |
6ad9a8ab | 2612 | Perl_re_indentf( aTHX_ |
cb41e5d6 YO |
2613 | "make_trie start==%d, first==%d, last==%d, tail==%d depth=%d\n", |
2614 | depth+1, | |
538e84ed KW |
2615 | REG_NODE_NUM(startbranch),REG_NODE_NUM(first), |
2616 | REG_NODE_NUM(last), REG_NODE_NUM(tail), (int)depth); | |
3dab1dad | 2617 | }); |
538e84ed | 2618 | |
7f69552c YO |
2619 | /* Find the node we are going to overwrite */ |
2620 | if ( first == startbranch && OP( last ) != BRANCH ) { | |
2621 | /* whole branch chain */ | |
2622 | convert = first; | |
2623 | } else { | |
2624 | /* branch sub-chain */ | |
2625 | convert = NEXTOPER( first ); | |
2626 | } | |
538e84ed | 2627 | |
a3621e74 YO |
2628 | /* -- First loop and Setup -- |
2629 | ||
2630 | We first traverse the branches and scan each word to determine if it | |
2631 | contains widechars, and how many unique chars there are, this is | |
2632 | important as we have to build a table with at least as many columns as we | |
2633 | have unique chars. | |
2634 | ||
2635 | We use an array of integers to represent the character codes 0..255 | |
538e84ed KW |
2636 | (trie->charmap) and we use a an HV* to store Unicode characters. We use |
2637 | the native representation of the character value as the key and IV's for | |
2638 | the coded index. | |
a3621e74 YO |
2639 | |
2640 | *TODO* If we keep track of how many times each character is used we can | |
2641 | remap the columns so that the table compression later on is more | |
3b753521 | 2642 | efficient in terms of memory by ensuring the most common value is in the |
a3621e74 YO |
2643 | middle and the least common are on the outside. IMO this would be better |
2644 | than a most to least common mapping as theres a decent chance the most | |
2645 | common letter will share a node with the least common, meaning the node | |
486ec47a | 2646 | will not be compressible. With a middle is most common approach the worst |
a3621e74 YO |
2647 | case is when we have the least common nodes twice. |
2648 | ||
2649 | */ | |
2650 | ||
a3621e74 | 2651 | for ( cur = first ; cur < last ; cur = regnext( cur ) ) { |
df826430 | 2652 | regnode *noper = NEXTOPER( cur ); |
944e05e3 YO |
2653 | const U8 *uc; |
2654 | const U8 *e; | |
bc031a7d | 2655 | int foldlen = 0; |
07be1b83 | 2656 | U32 wordlen = 0; /* required init */ |
bc031a7d KW |
2657 | STRLEN minchars = 0; |
2658 | STRLEN maxchars = 0; | |
538e84ed KW |
2659 | bool set_bit = trie->bitmap ? 1 : 0; /*store the first char in the |
2660 | bitmap?*/ | |
a3621e74 | 2661 | |
3dab1dad | 2662 | if (OP(noper) == NOTHING) { |
20ed8c88 YO |
2663 | /* skip past a NOTHING at the start of an alternation |
2664 | * eg, /(?:)a|(?:b)/ should be the same as /a|b/ | |
2665 | */ | |
df826430 | 2666 | regnode *noper_next= regnext(noper); |
944e05e3 YO |
2667 | if (noper_next < tail) |
2668 | noper= noper_next; | |
2669 | } | |
2670 | ||
dca5fc4c YO |
2671 | if ( noper < tail && |
2672 | ( | |
2673 | OP(noper) == flags || | |
2674 | ( | |
2675 | flags == EXACTFU && | |
2676 | OP(noper) == EXACTFU_SS | |
2677 | ) | |
2678 | ) | |
2679 | ) { | |
944e05e3 YO |
2680 | uc= (U8*)STRING(noper); |
2681 | e= uc + STR_LEN(noper); | |
2682 | } else { | |
2683 | trie->minlen= 0; | |
2684 | continue; | |
3dab1dad | 2685 | } |
df826430 | 2686 | |
944e05e3 | 2687 | |
fab2782b | 2688 | if ( set_bit ) { /* bitmap only alloced when !(UTF&&Folding) */ |
02daf0ab YO |
2689 | TRIE_BITMAP_SET(trie,*uc); /* store the raw first byte |
2690 | regardless of encoding */ | |
fab2782b YO |
2691 | if (OP( noper ) == EXACTFU_SS) { |
2692 | /* false positives are ok, so just set this */ | |
0dc4a61d | 2693 | TRIE_BITMAP_SET(trie, LATIN_SMALL_LETTER_SHARP_S); |
fab2782b YO |
2694 | } |
2695 | } | |
dca5fc4c | 2696 | |
bc031a7d KW |
2697 | for ( ; uc < e ; uc += len ) { /* Look at each char in the current |
2698 | branch */ | |
3dab1dad | 2699 | TRIE_CHARCOUNT(trie)++; |
a3621e74 | 2700 | TRIE_READ_CHAR; |
645de4ce | 2701 | |
bc031a7d KW |
2702 | /* TRIE_READ_CHAR returns the current character, or its fold if /i |
2703 | * is in effect. Under /i, this character can match itself, or | |
2704 | * anything that folds to it. If not under /i, it can match just | |
2705 | * itself. Most folds are 1-1, for example k, K, and KELVIN SIGN | |
2706 | * all fold to k, and all are single characters. But some folds | |
2707 | * expand to more than one character, so for example LATIN SMALL | |
2708 | * LIGATURE FFI folds to the three character sequence 'ffi'. If | |
2709 | * the string beginning at 'uc' is 'ffi', it could be matched by | |
2710 | * three characters, or just by the one ligature character. (It | |
2711 | * could also be matched by two characters: LATIN SMALL LIGATURE FF | |
2712 | * followed by 'i', or by 'f' followed by LATIN SMALL LIGATURE FI). | |
2713 | * (Of course 'I' and/or 'F' instead of 'i' and 'f' can also | |
2714 | * match.) The trie needs to know the minimum and maximum number | |
2715 | * of characters that could match so that it can use size alone to | |
2716 | * quickly reject many match attempts. The max is simple: it is | |
2717 | * the number of folded characters in this branch (since a fold is | |
2718 | * never shorter than what folds to it. */ | |
2719 | ||
2720 | maxchars++; | |
2721 | ||
2722 | /* And the min is equal to the max if not under /i (indicated by | |
2723 | * 'folder' being NULL), or there are no multi-character folds. If | |
2724 | * there is a multi-character fold, the min is incremented just | |
2725 | * once, for the character that folds to the sequence. Each | |
2726 | * character in the sequence needs to be added to the list below of | |
2727 | * characters in the trie, but we count only the first towards the | |
2728 | * min number of characters needed. This is done through the | |
2729 | * variable 'foldlen', which is returned by the macros that look | |
2730 | * for these sequences as the number of bytes the sequence | |
2731 | * occupies. Each time through the loop, we decrement 'foldlen' by | |
2732 | * how many bytes the current char occupies. Only when it reaches | |
2733 | * 0 do we increment 'minchars' or look for another multi-character | |
2734 | * sequence. */ | |
2735 | if (folder == NULL) { | |
2736 | minchars++; | |
2737 | } | |
2738 | else if (foldlen > 0) { | |
2739 | foldlen -= (UTF) ? UTF8SKIP(uc) : 1; | |
645de4ce KW |
2740 | } |
2741 | else { | |
bc031a7d KW |
2742 | minchars++; |
2743 | ||
2744 | /* See if *uc is the beginning of a multi-character fold. If | |
2745 | * so, we decrement the length remaining to look at, to account | |
2746 | * for the current character this iteration. (We can use 'uc' | |
2747 | * instead of the fold returned by TRIE_READ_CHAR because for | |
2748 | * non-UTF, the latin1_safe macro is smart enough to account | |
2749 | * for all the unfolded characters, and because for UTF, the | |
2750 | * string will already have been folded earlier in the | |
2751 | * compilation process */ | |
2752 | if (UTF) { | |
2753 | if ((foldlen = is_MULTI_CHAR_FOLD_utf8_safe(uc, e))) { | |
2754 | foldlen -= UTF8SKIP(uc); | |
645de4ce KW |
2755 | } |
2756 | } | |
bc031a7d KW |
2757 | else if ((foldlen = is_MULTI_CHAR_FOLD_latin1_safe(uc, e))) { |
2758 | foldlen--; | |
2759 | } | |
645de4ce | 2760 | } |
bc031a7d KW |
2761 | |
2762 | /* The current character (and any potential folds) should be added | |
2763 | * to the possible matching characters for this position in this | |
2764 | * branch */ | |
a3621e74 | 2765 | if ( uvc < 256 ) { |
fab2782b YO |
2766 | if ( folder ) { |
2767 | U8 folded= folder[ (U8) uvc ]; | |
2768 | if ( !trie->charmap[ folded ] ) { | |
2769 | trie->charmap[ folded ]=( ++trie->uniquecharcount ); | |
2770 | TRIE_STORE_REVCHAR( folded ); | |
2771 | } | |
2772 | } | |
a3621e74 YO |
2773 | if ( !trie->charmap[ uvc ] ) { |
2774 | trie->charmap[ uvc ]=( ++trie->uniquecharcount ); | |
fab2782b | 2775 | TRIE_STORE_REVCHAR( uvc ); |
a3621e74 | 2776 | } |
02daf0ab | 2777 | if ( set_bit ) { |
62012aee KW |
2778 | /* store the codepoint in the bitmap, and its folded |
2779 | * equivalent. */ | |
8bcafbf4 | 2780 | TRIE_BITMAP_SET_FOLDED(trie, uvc, folder); |
02daf0ab YO |
2781 | set_bit = 0; /* We've done our bit :-) */ |
2782 | } | |
a3621e74 | 2783 | } else { |
bc031a7d KW |
2784 | |
2785 | /* XXX We could come up with the list of code points that fold | |
2786 | * to this using PL_utf8_foldclosures, except not for | |
2787 | * multi-char folds, as there may be multiple combinations | |
2788 | * there that could work, which needs to wait until runtime to | |
2789 | * resolve (The comment about LIGATURE FFI above is such an | |
2790 | * example */ | |
2791 | ||
a3621e74 | 2792 | SV** svpp; |
55eed653 NC |
2793 | if ( !widecharmap ) |
2794 | widecharmap = newHV(); | |
a3621e74 | 2795 | |
55eed653 | 2796 | svpp = hv_fetch( widecharmap, (char*)&uvc, sizeof( UV ), 1 ); |
a3621e74 YO |
2797 | |
2798 | if ( !svpp ) | |
147e3846 | 2799 | Perl_croak( aTHX_ "error creating/fetching widecharmap entry for 0x%" UVXf, uvc ); |
a3621e74 YO |
2800 | |
2801 | if ( !SvTRUE( *svpp ) ) { | |
2802 | sv_setiv( *svpp, ++trie->uniquecharcount ); | |
fab2782b | 2803 | TRIE_STORE_REVCHAR(uvc); |
a3621e74 YO |
2804 | } |
2805 | } | |
bc031a7d KW |
2806 | } /* end loop through characters in this branch of the trie */ |
2807 | ||
2808 | /* We take the min and max for this branch and combine to find the min | |
2809 | * and max for all branches processed so far */ | |
3dab1dad | 2810 | if( cur == first ) { |
bc031a7d KW |
2811 | trie->minlen = minchars; |
2812 | trie->maxlen = maxchars; | |
2813 | } else if (minchars < trie->minlen) { | |
2814 | trie->minlen = minchars; | |
2815 | } else if (maxchars > trie->maxlen) { | |
2816 | trie->maxlen = maxchars; | |
fab2782b | 2817 | } |
a3621e74 YO |
2818 | } /* end first pass */ |
2819 | DEBUG_TRIE_COMPILE_r( | |
6ad9a8ab | 2820 | Perl_re_indentf( aTHX_ |
cb41e5d6 YO |
2821 | "TRIE(%s): W:%d C:%d Uq:%d Min:%d Max:%d\n", |
2822 | depth+1, | |
55eed653 | 2823 | ( widecharmap ? "UTF8" : "NATIVE" ), (int)word_count, |
be8e71aa YO |
2824 | (int)TRIE_CHARCOUNT(trie), trie->uniquecharcount, |
2825 | (int)trie->minlen, (int)trie->maxlen ) | |
a3621e74 | 2826 | ); |
a3621e74 YO |
2827 | |
2828 | /* | |
2829 | We now know what we are dealing with in terms of unique chars and | |
2830 | string sizes so we can calculate how much memory a naive | |
0111c4fd RGS |
2831 | representation using a flat table will take. If it's over a reasonable |
2832 | limit (as specified by ${^RE_TRIE_MAXBUF}) we use a more memory | |
a3621e74 YO |
2833 | conservative but potentially much slower representation using an array |
2834 | of lists. | |
2835 | ||
2836 | At the end we convert both representations into the same compressed | |
2837 | form that will be used in regexec.c for matching with. The latter | |
2838 | is a form that cannot be used to construct with but has memory | |
2839 | properties similar to the list form and access properties similar | |
2840 | to the table form making it both suitable for fast searches and | |
2841 | small enough that its feasable to store for the duration of a program. | |
2842 | ||
2843 | See the comment in the code where the compressed table is produced | |
2844 | inplace from the flat tabe representation for an explanation of how | |
2845 | the compression works. | |
2846 | ||
2847 | */ | |
2848 | ||
2849 | ||
2e64971a DM |
2850 | Newx(prev_states, TRIE_CHARCOUNT(trie) + 2, U32); |
2851 | prev_states[1] = 0; | |
2852 | ||
538e84ed KW |
2853 | if ( (IV)( ( TRIE_CHARCOUNT(trie) + 1 ) * trie->uniquecharcount + 1) |
2854 | > SvIV(re_trie_maxbuff) ) | |
2855 | { | |
a3621e74 YO |
2856 | /* |
2857 | Second Pass -- Array Of Lists Representation | |
2858 | ||
2859 | Each state will be represented by a list of charid:state records | |
2860 | (reg_trie_trans_le) the first such element holds the CUR and LEN | |
2861 | points of the allocated array. (See defines above). | |
2862 | ||
2863 | We build the initial structure using the lists, and then convert | |
2864 | it into the compressed table form which allows faster lookups | |
2865 | (but cant be modified once converted). | |
a3621e74 YO |
2866 | */ |
2867 | ||
a3621e74 YO |
2868 | STRLEN transcount = 1; |
2869 | ||
6ad9a8ab | 2870 | DEBUG_TRIE_COMPILE_MORE_r( Perl_re_indentf( aTHX_ "Compiling trie using list compiler\n", |
cb41e5d6 | 2871 | depth+1)); |
686b73d4 | 2872 | |
c944940b JH |
2873 | trie->states = (reg_trie_state *) |
2874 | PerlMemShared_calloc( TRIE_CHARCOUNT(trie) + 2, | |
2875 | sizeof(reg_trie_state) ); | |
a3621e74 YO |
2876 | TRIE_LIST_NEW(1); |
2877 | next_alloc = 2; | |
2878 | ||
2879 | for ( cur = first ; cur < last ; cur = regnext( cur ) ) { | |
2880 | ||
df826430 | 2881 | regnode *noper = NEXTOPER( cur ); |
c445ea15 AL |
2882 | U32 state = 1; /* required init */ |
2883 | U16 charid = 0; /* sanity init */ | |
07be1b83 | 2884 | U32 wordlen = 0; /* required init */ |
c445ea15 | 2885 | |
df826430 YO |
2886 | if (OP(noper) == NOTHING) { |
2887 | regnode *noper_next= regnext(noper); | |
944e05e3 YO |
2888 | if (noper_next < tail) |
2889 | noper= noper_next; | |
df826430 YO |
2890 | } |
2891 | ||
944e05e3 YO |
2892 | if ( noper < tail && ( OP(noper) == flags || ( flags == EXACTFU && OP(noper) == EXACTFU_SS ) ) ) { |
2893 | const U8 *uc= (U8*)STRING(noper); | |
2894 | const U8 *e= uc + STR_LEN(noper); | |
2895 | ||
786e8c11 | 2896 | for ( ; uc < e ; uc += len ) { |
c445ea15 | 2897 | |
786e8c11 | 2898 | TRIE_READ_CHAR; |
c445ea15 | 2899 | |
786e8c11 YO |
2900 | if ( uvc < 256 ) { |
2901 | charid = trie->charmap[ uvc ]; | |
c445ea15 | 2902 | } else { |
538e84ed KW |
2903 | SV** const svpp = hv_fetch( widecharmap, |
2904 | (char*)&uvc, | |
2905 | sizeof( UV ), | |
2906 | 0); | |
786e8c11 YO |
2907 | if ( !svpp ) { |
2908 | charid = 0; | |
2909 | } else { | |
2910 | charid=(U16)SvIV( *svpp ); | |
2911 | } | |
c445ea15 | 2912 | } |
538e84ed KW |
2913 | /* charid is now 0 if we dont know the char read, or |
2914 | * nonzero if we do */ | |
786e8c11 | 2915 | if ( charid ) { |
a3621e74 | 2916 | |
786e8c11 YO |
2917 | U16 check; |
2918 | U32 newstate = 0; | |
a3621e74 | 2919 | |
786e8c11 YO |
2920 | charid--; |
2921 | if ( !trie->states[ state ].trans.list ) { | |
2922 | TRIE_LIST_NEW( state ); | |
c445ea15 | 2923 | } |
538e84ed KW |
2924 | for ( check = 1; |
2925 | check <= TRIE_LIST_USED( state ); | |
2926 | check++ ) | |
2927 | { | |
2928 | if ( TRIE_LIST_ITEM( state, check ).forid | |
2929 | == charid ) | |
2930 | { | |
786e8c11 YO |
2931 | newstate = TRIE_LIST_ITEM( state, check ).newstate; |
2932 | break; | |
2933 | } | |
2934 | } | |
2935 | if ( ! newstate ) { | |
2936 | newstate = next_alloc++; | |
2e64971a | 2937 | prev_states[newstate] = state; |
786e8c11 YO |
2938 | TRIE_LIST_PUSH( state, charid, newstate ); |
2939 | transcount++; | |
2940 | } | |
2941 | state = newstate; | |
2942 | } else { | |
147e3846 | 2943 | Perl_croak( aTHX_ "panic! In trie construction, no char mapping for %" IVdf, uvc ); |
c445ea15 | 2944 | } |
a28509cc | 2945 | } |
c445ea15 | 2946 | } |
3dab1dad | 2947 | TRIE_HANDLE_WORD(state); |
a3621e74 YO |
2948 | |
2949 | } /* end second pass */ | |
2950 | ||
1e2e3d02 | 2951 | /* next alloc is the NEXT state to be allocated */ |
538e84ed | 2952 | trie->statecount = next_alloc; |
c944940b JH |
2953 | trie->states = (reg_trie_state *) |
2954 | PerlMemShared_realloc( trie->states, | |
2955 | next_alloc | |
2956 | * sizeof(reg_trie_state) ); | |
a3621e74 | 2957 | |
3dab1dad | 2958 | /* and now dump it out before we compress it */ |
2b8b4781 NC |
2959 | DEBUG_TRIE_COMPILE_MORE_r(dump_trie_interim_list(trie, widecharmap, |
2960 | revcharmap, next_alloc, | |
2961 | depth+1) | |
1e2e3d02 | 2962 | ); |
a3621e74 | 2963 | |
c944940b JH |
2964 | trie->trans = (reg_trie_trans *) |
2965 | PerlMemShared_calloc( transcount, sizeof(reg_trie_trans) ); | |
a3621e74 YO |
2966 | { |
2967 | U32 state; | |
a3621e74 YO |
2968 | U32 tp = 0; |
2969 | U32 zp = 0; | |
2970 | ||
2971 | ||
2972 | for( state=1 ; state < next_alloc ; state ++ ) { | |
2973 | U32 base=0; | |
2974 | ||
2975 | /* | |
2976 | DEBUG_TRIE_COMPILE_MORE_r( | |
6ad9a8ab | 2977 | Perl_re_printf( aTHX_ "tp: %d zp: %d ",tp,zp) |
a3621e74 YO |
2978 | ); |
2979 | */ | |
2980 | ||
2981 | if (trie->states[state].trans.list) { | |
2982 | U16 minid=TRIE_LIST_ITEM( state, 1).forid; | |
2983 | U16 maxid=minid; | |
a28509cc | 2984 | U16 idx; |
a3621e74 YO |
2985 | |
2986 | for( idx = 2 ; idx <= TRIE_LIST_USED( state ) ; idx++ ) { | |
c445ea15 AL |
2987 | const U16 forid = TRIE_LIST_ITEM( state, idx).forid; |
2988 | if ( forid < minid ) { | |
2989 | minid=forid; | |
2990 | } else if ( forid > maxid ) { | |
2991 | maxid=forid; | |
2992 | } | |
a3621e74 YO |
2993 | } |
2994 | if ( transcount < tp + maxid - minid + 1) { | |
2995 | transcount *= 2; | |
c944940b JH |
2996 | trie->trans = (reg_trie_trans *) |
2997 | PerlMemShared_realloc( trie->trans, | |
446bd890 NC |
2998 | transcount |
2999 | * sizeof(reg_trie_trans) ); | |
538e84ed KW |
3000 | Zero( trie->trans + (transcount / 2), |
3001 | transcount / 2, | |
3002 | reg_trie_trans ); | |
a3621e74 YO |
3003 | } |
3004 | base = trie->uniquecharcount + tp - minid; | |
3005 | if ( maxid == minid ) { | |
3006 | U32 set = 0; | |
3007 | for ( ; zp < tp ; zp++ ) { | |
3008 | if ( ! trie->trans[ zp ].next ) { | |
3009 | base = trie->uniquecharcount + zp - minid; | |
538e84ed KW |
3010 | trie->trans[ zp ].next = TRIE_LIST_ITEM( state, |
3011 | 1).newstate; | |
a3621e74 YO |
3012 | trie->trans[ zp ].check = state; |
3013 | set = 1; | |
3014 | break; | |
3015 | } | |
3016 | } | |
3017 | if ( !set ) { | |
538e84ed KW |
3018 | trie->trans[ tp ].next = TRIE_LIST_ITEM( state, |
3019 | 1).newstate; | |
a3621e74 YO |
3020 | trie->trans[ tp ].check = state; |
3021 | tp++; | |
3022 | zp = tp; | |
3023 | } | |
3024 | } else { | |
3025 | for ( idx=1; idx <= TRIE_LIST_USED( state ) ; idx++ ) { | |
538e84ed KW |
3026 | const U32 tid = base |
3027 | - trie->uniquecharcount | |
3028 | + TRIE_LIST_ITEM( state, idx ).forid; | |
3029 | trie->trans[ tid ].next = TRIE_LIST_ITEM( state, | |
3030 | idx ).newstate; | |
a3621e74 YO |
3031 | trie->trans[ tid ].check = state; |
3032 | } | |
3033 | tp += ( maxid - minid + 1 ); | |
3034 | } | |
3035 | Safefree(trie->states[ state ].trans.list); | |
3036 | } | |
3037 | /* | |
3038 | DEBUG_TRIE_COMPILE_MORE_r( | |
6ad9a8ab | 3039 | Perl_re_printf( aTHX_ " base: %d\n",base); |
a3621e74 YO |
3040 | ); |
3041 | */ | |
3042 | trie->states[ state ].trans.base=base; | |
3043 | } | |
cc601c31 | 3044 | trie->lasttrans = tp + 1; |
a3621e74 YO |
3045 | } |
3046 | } else { | |
3047 | /* | |
3048 | Second Pass -- Flat Table Representation. | |
3049 | ||
b423522f KW |
3050 | we dont use the 0 slot of either trans[] or states[] so we add 1 to |
3051 | each. We know that we will need Charcount+1 trans at most to store | |
3052 | the data (one row per char at worst case) So we preallocate both | |
3053 | structures assuming worst case. | |
a3621e74 YO |
3054 | |
3055 | We then construct the trie using only the .next slots of the entry | |
3056 | structs. | |
3057 | ||
b423522f KW |
3058 | We use the .check field of the first entry of the node temporarily |
3059 | to make compression both faster and easier by keeping track of how | |
3060 | many non zero fields are in the node. | |
a3621e74 YO |
3061 | |
3062 | Since trans are numbered from 1 any 0 pointer in the table is a FAIL | |
3063 | transition. | |
3064 | ||
b423522f KW |
3065 | There are two terms at use here: state as a TRIE_NODEIDX() which is |
3066 | a number representing the first entry of the node, and state as a | |
3067 | TRIE_NODENUM() which is the trans number. state 1 is TRIE_NODEIDX(1) | |
3068 | and TRIE_NODENUM(1), state 2 is TRIE_NODEIDX(2) and TRIE_NODENUM(3) | |
3069 | if there are 2 entrys per node. eg: | |
a3621e74 YO |
3070 | |
3071 | A B A B | |
3072 | 1. 2 4 1. 3 7 | |
3073 | 2. 0 3 3. 0 5 | |
3074 | 3. 0 0 5. 0 0 | |
3075 | 4. 0 0 7. 0 0 | |
3076 | ||
b423522f KW |
3077 | The table is internally in the right hand, idx form. However as we |
3078 | also have to deal with the states array which is indexed by nodenum | |
3079 | we have to use TRIE_NODENUM() to convert. | |
a3621e74 YO |
3080 | |
3081 | */ | |
6ad9a8ab | 3082 | DEBUG_TRIE_COMPILE_MORE_r( Perl_re_indentf( aTHX_ "Compiling trie using table compiler\n", |
cb41e5d6 | 3083 | depth+1)); |
3dab1dad | 3084 | |
c944940b JH |
3085 | trie->trans = (reg_trie_trans *) |
3086 | PerlMemShared_calloc( ( TRIE_CHARCOUNT(trie) + 1 ) | |
3087 | * trie->uniquecharcount + 1, | |
3088 | sizeof(reg_trie_trans) ); | |
3089 | trie->states = (reg_trie_state *) | |
3090 | PerlMemShared_calloc( TRIE_CHARCOUNT(trie) + 2, | |
3091 | sizeof(reg_trie_state) ); | |
a3621e74 YO |
3092 | next_alloc = trie->uniquecharcount + 1; |
3093 | ||
3dab1dad | 3094 | |
a3621e74 YO |
3095 | for ( cur = first ; cur < last ; cur = regnext( cur ) ) { |
3096 | ||
df826430 | 3097 | regnode *noper = NEXTOPER( cur ); |
a3621e74 YO |
3098 | |
3099 | U32 state = 1; /* required init */ | |
3100 | ||
3101 | U16 charid = 0; /* sanity init */ | |
3102 | U32 accept_state = 0; /* sanity init */ | |
a3621e74 | 3103 | |
07be1b83 | 3104 | U32 wordlen = 0; /* required init */ |
a3621e74 | 3105 | |
df826430 YO |
3106 | if (OP(noper) == NOTHING) { |
3107 | regnode *noper_next= regnext(noper); | |
944e05e3 YO |
3108 | if (noper_next < tail) |
3109 | noper= noper_next; | |
df826430 | 3110 | } |
fab2782b | 3111 | |
944e05e3 YO |
3112 | if ( noper < tail && ( OP(noper) == flags || ( flags == EXACTFU && OP(noper) == EXACTFU_SS ) ) ) { |
3113 | const U8 *uc= (U8*)STRING(noper); | |
3114 | const U8 *e= uc + STR_LEN(noper); | |
3115 | ||
786e8c11 | 3116 | for ( ; uc < e ; uc += len ) { |
a3621e74 | 3117 | |
786e8c11 | 3118 | TRIE_READ_CHAR; |
a3621e74 | 3119 | |
786e8c11 YO |
3120 | if ( uvc < 256 ) { |
3121 | charid = trie->charmap[ uvc ]; | |
3122 | } else { | |
538e84ed KW |
3123 | SV* const * const svpp = hv_fetch( widecharmap, |
3124 | (char*)&uvc, | |
3125 | sizeof( UV ), | |
3126 | 0); | |
786e8c11 | 3127 | charid = svpp ? (U16)SvIV(*svpp) : 0; |
a3621e74 | 3128 | } |
786e8c11 YO |
3129 | if ( charid ) { |
3130 | charid--; | |
3131 | if ( !trie->trans[ state + charid ].next ) { | |
3132 | trie->trans[ state + charid ].next = next_alloc; | |
3133 | trie->trans[ state ].check++; | |
2e64971a DM |
3134 | prev_states[TRIE_NODENUM(next_alloc)] |
3135 | = TRIE_NODENUM(state); | |
786e8c11 YO |
3136 | next_alloc += trie->uniquecharcount; |
3137 | } | |
3138 | state = trie->trans[ state + charid ].next; | |
3139 | } else { | |
147e3846 | 3140 | Perl_croak( aTHX_ "panic! In trie construction, no char mapping for %" IVdf, uvc ); |
786e8c11 | 3141 | } |
538e84ed KW |
3142 | /* charid is now 0 if we dont know the char read, or |
3143 | * nonzero if we do */ | |
a3621e74 | 3144 | } |
a3621e74 | 3145 | } |
3dab1dad YO |
3146 | accept_state = TRIE_NODENUM( state ); |
3147 | TRIE_HANDLE_WORD(accept_state); | |
a3621e74 YO |
3148 | |
3149 | } /* end second pass */ | |
3150 | ||
3dab1dad | 3151 | /* and now dump it out before we compress it */ |
2b8b4781 NC |
3152 | DEBUG_TRIE_COMPILE_MORE_r(dump_trie_interim_table(trie, widecharmap, |
3153 | revcharmap, | |
3154 | next_alloc, depth+1)); | |
a3621e74 | 3155 | |
a3621e74 YO |
3156 | { |
3157 | /* | |
3158 | * Inplace compress the table.* | |
3159 | ||
3160 | For sparse data sets the table constructed by the trie algorithm will | |
3161 | be mostly 0/FAIL transitions or to put it another way mostly empty. | |
3162 | (Note that leaf nodes will not contain any transitions.) | |
3163 | ||
3164 | This algorithm compresses the tables by eliminating most such | |
3165 | transitions, at the cost of a modest bit of extra work during lookup: | |
3166 | ||
3167 | - Each states[] entry contains a .base field which indicates the | |
3168 | index in the state[] array wheres its transition data is stored. | |
3169 | ||
3b753521 | 3170 | - If .base is 0 there are no valid transitions from that node. |
a3621e74 YO |
3171 | |
3172 | - If .base is nonzero then charid is added to it to find an entry in | |
3173 | the trans array. | |
3174 | ||
3175 | -If trans[states[state].base+charid].check!=state then the | |
3176 | transition is taken to be a 0/Fail transition. Thus if there are fail | |
3177 | transitions at the front of the node then the .base offset will point | |
3178 | somewhere inside the previous nodes data (or maybe even into a node | |
3179 | even earlier), but the .check field determines if the transition is | |
3180 | valid. | |
3181 | ||
786e8c11 | 3182 | XXX - wrong maybe? |
a3621e74 | 3183 | The following process inplace converts the table to the compressed |
3b753521 | 3184 | table: We first do not compress the root node 1,and mark all its |
a3621e74 | 3185 | .check pointers as 1 and set its .base pointer as 1 as well. This |
3b753521 FN |
3186 | allows us to do a DFA construction from the compressed table later, |
3187 | and ensures that any .base pointers we calculate later are greater | |
3188 | than 0. | |
a3621e74 YO |
3189 | |
3190 | - We set 'pos' to indicate the first entry of the second node. | |
3191 | ||
3192 | - We then iterate over the columns of the node, finding the first and | |
3193 | last used entry at l and m. We then copy l..m into pos..(pos+m-l), | |
3194 | and set the .check pointers accordingly, and advance pos | |
3195 | appropriately and repreat for the next node. Note that when we copy | |
3196 | the next pointers we have to convert them from the original | |
3197 | NODEIDX form to NODENUM form as the former is not valid post | |
3198 | compression. | |
3199 | ||
3200 | - If a node has no transitions used we mark its base as 0 and do not | |
3201 | advance the pos pointer. | |
3202 | ||
3203 | - If a node only has one transition we use a second pointer into the | |
3204 | structure to fill in allocated fail transitions from other states. | |
3205 | This pointer is independent of the main pointer and scans forward | |
3206 | looking for null transitions that are allocated to a state. When it | |
3207 | finds one it writes the single transition into the "hole". If the | |
786e8c11 | 3208 | pointer doesnt find one the single transition is appended as normal. |
a3621e74 YO |
3209 | |
3210 | - Once compressed we can Renew/realloc the structures to release the | |
3211 | excess space. | |
3212 | ||
3213 | See "Table-Compression Methods" in sec 3.9 of the Red Dragon, | |
3214 | specifically Fig 3.47 and the associated pseudocode. | |
3215 | ||
3216 | demq | |
3217 | */ | |
a3b680e6 | 3218 | const U32 laststate = TRIE_NODENUM( next_alloc ); |
a28509cc | 3219 | U32 state, charid; |
a3621e74 | 3220 | U32 pos = 0, zp=0; |
1e2e3d02 | 3221 | trie->statecount = laststate; |
a3621e74 YO |
3222 | |
3223 | for ( state = 1 ; state < laststate ; state++ ) { | |
3224 | U8 flag = 0; | |
a28509cc AL |
3225 | const U32 stateidx = TRIE_NODEIDX( state ); |
3226 | const U32 o_used = trie->trans[ stateidx ].check; | |
3227 | U32 used = trie->trans[ stateidx ].check; | |
a3621e74 YO |
3228 | trie->trans[ stateidx ].check = 0; |
3229 | ||
538e84ed KW |
3230 | for ( charid = 0; |
3231 | used && charid < trie->uniquecharcount; | |
3232 | charid++ ) | |
3233 | { | |
a3621e74 YO |
3234 | if ( flag || trie->trans[ stateidx + charid ].next ) { |
3235 | if ( trie->trans[ stateidx + charid ].next ) { | |
3236 | if (o_used == 1) { | |
3237 | for ( ; zp < pos ; zp++ ) { | |
3238 | if ( ! trie->trans[ zp ].next ) { | |
3239 | break; | |
3240 | } | |
3241 | } | |
538e84ed KW |
3242 | trie->states[ state ].trans.base |
3243 | = zp | |
3244 | + trie->uniquecharcount | |
3245 | - charid ; | |
3246 | trie->trans[ zp ].next | |
3247 | = SAFE_TRIE_NODENUM( trie->trans[ stateidx | |
3248 | + charid ].next ); | |
a3621e74 YO |
3249 | trie->trans[ zp ].check = state; |
3250 | if ( ++zp > pos ) pos = zp; | |
3251 | break; | |
3252 | } | |
3253 | used--; | |
3254 | } | |
3255 | if ( !flag ) { | |
3256 | flag = 1; | |
538e84ed KW |
3257 | trie->states[ state ].trans.base |
3258 | = pos + trie->uniquecharcount - charid ; | |
a3621e74 | 3259 | } |
538e84ed KW |
3260 | trie->trans[ pos ].next |
3261 | = SAFE_TRIE_NODENUM( | |
3262 | trie->trans[ stateidx + charid ].next ); | |
a3621e74 YO |
3263 | trie->trans[ pos ].check = state; |
3264 | pos++; | |
3265 | } | |
3266 | } | |
3267 | } | |
cc601c31 | 3268 | trie->lasttrans = pos + 1; |
c944940b JH |
3269 | trie->states = (reg_trie_state *) |
3270 | PerlMemShared_realloc( trie->states, laststate | |
3271 | * sizeof(reg_trie_state) ); | |
a3621e74 | 3272 | DEBUG_TRIE_COMPILE_MORE_r( |
147e3846 | 3273 | Perl_re_indentf( aTHX_ "Alloc: %d Orig: %" IVdf " elements, Final:%" IVdf ". Savings of %%%5.2f\n", |
cb41e5d6 | 3274 | depth+1, |
538e84ed KW |
3275 | (int)( ( TRIE_CHARCOUNT(trie) + 1 ) * trie->uniquecharcount |
3276 | + 1 ), | |
3277 | (IV)next_alloc, | |
3278 | (IV)pos, | |
3279 | ( ( next_alloc - pos ) * 100 ) / (double)next_alloc ); | |
a3621e74 YO |
3280 | ); |
3281 | ||
3282 | } /* end table compress */ | |
3283 | } | |
1e2e3d02 | 3284 | DEBUG_TRIE_COMPILE_MORE_r( |
147e3846 | 3285 | Perl_re_indentf( aTHX_ "Statecount:%" UVxf " Lasttrans:%" UVxf "\n", |
cb41e5d6 | 3286 | depth+1, |
1e2e3d02 YO |
3287 | (UV)trie->statecount, |
3288 | (UV)trie->lasttrans) | |
3289 | ); | |
cc601c31 | 3290 | /* resize the trans array to remove unused space */ |
c944940b JH |
3291 | trie->trans = (reg_trie_trans *) |
3292 | PerlMemShared_realloc( trie->trans, trie->lasttrans | |
3293 | * sizeof(reg_trie_trans) ); | |
a3621e74 | 3294 | |
538e84ed | 3295 | { /* Modify the program and insert the new TRIE node */ |
3dab1dad YO |
3296 | U8 nodetype =(U8)(flags & 0xFF); |
3297 | char *str=NULL; | |
538e84ed | 3298 | |
07be1b83 | 3299 | #ifdef DEBUGGING |
e62cc96a | 3300 | regnode *optimize = NULL; |
7122b237 YO |
3301 | #ifdef RE_TRACK_PATTERN_OFFSETS |
3302 | ||
b57a0404 JH |
3303 | U32 mjd_offset = 0; |
3304 | U32 mjd_nodelen = 0; | |
7122b237 YO |
3305 | #endif /* RE_TRACK_PATTERN_OFFSETS */ |
3306 | #endif /* DEBUGGING */ | |
a3621e74 | 3307 | /* |
3dab1dad YO |
3308 | This means we convert either the first branch or the first Exact, |
3309 | depending on whether the thing following (in 'last') is a branch | |
3310 | or not and whther first is the startbranch (ie is it a sub part of | |
3311 | the alternation or is it the whole thing.) | |
3b753521 | 3312 | Assuming its a sub part we convert the EXACT otherwise we convert |
3dab1dad | 3313 | the whole branch sequence, including the first. |
a3621e74 | 3314 | */ |
3dab1dad | 3315 | /* Find the node we are going to overwrite */ |
7f69552c | 3316 | if ( first != startbranch || OP( last ) == BRANCH ) { |
07be1b83 | 3317 | /* branch sub-chain */ |
3dab1dad | 3318 | NEXT_OFF( first ) = (U16)(last - first); |
7122b237 | 3319 | #ifdef RE_TRACK_PATTERN_OFFSETS |
07be1b83 YO |
3320 | DEBUG_r({ |
3321 | mjd_offset= Node_Offset((convert)); | |
3322 | mjd_nodelen= Node_Length((convert)); | |
3323 | }); | |
7122b237 | 3324 | #endif |
7f69552c | 3325 | /* whole branch chain */ |
7122b237 YO |
3326 | } |
3327 | #ifdef RE_TRACK_PATTERN_OFFSETS | |
3328 | else { | |
7f69552c YO |
3329 | DEBUG_r({ |
3330 | const regnode *nop = NEXTOPER( convert ); | |
3331 | mjd_offset= Node_Offset((nop)); | |
3332 | mjd_nodelen= Node_Length((nop)); | |
3333 | }); | |
07be1b83 YO |
3334 | } |
3335 | DEBUG_OPTIMISE_r( | |
147e3846 | 3336 | Perl_re_indentf( aTHX_ "MJD offset:%" UVuf " MJD length:%" UVuf "\n", |
cb41e5d6 | 3337 | depth+1, |
786e8c11 | 3338 | (UV)mjd_offset, (UV)mjd_nodelen) |
07be1b83 | 3339 | ); |
7122b237 | 3340 | #endif |
538e84ed | 3341 | /* But first we check to see if there is a common prefix we can |
3dab1dad YO |
3342 | split out as an EXACT and put in front of the TRIE node. */ |
3343 | trie->startstate= 1; | |
55eed653 | 3344 | if ( trie->bitmap && !widecharmap && !trie->jump ) { |
5ee57374 YO |
3345 | /* we want to find the first state that has more than |
3346 | * one transition, if that state is not the first state | |
3347 | * then we have a common prefix which we can remove. | |
3348 | */ | |
3dab1dad | 3349 | U32 state; |
1e2e3d02 | 3350 | for ( state = 1 ; state < trie->statecount-1 ; state++ ) { |
a3621e74 | 3351 | U32 ofs = 0; |
ee0dfd0b YO |
3352 | I32 first_ofs = -1; /* keeps track of the ofs of the first |
3353 | transition, -1 means none */ | |
8e11feef RGS |
3354 | U32 count = 0; |
3355 | const U32 base = trie->states[ state ].trans.base; | |
a3621e74 | 3356 | |
5ee57374 | 3357 | /* does this state terminate an alternation? */ |
3dab1dad | 3358 | if ( trie->states[state].wordnum ) |
8e11feef | 3359 | count = 1; |
a3621e74 | 3360 | |
8e11feef | 3361 | for ( ofs = 0 ; ofs < trie->uniquecharcount ; ofs++ ) { |
cc601c31 YO |
3362 | if ( ( base + ofs >= trie->uniquecharcount ) && |
3363 | ( base + ofs - trie->uniquecharcount < trie->lasttrans ) && | |
a3621e74 YO |
3364 | trie->trans[ base + ofs - trie->uniquecharcount ].check == state ) |
3365 | { | |
3dab1dad | 3366 | if ( ++count > 1 ) { |
5ee57374 | 3367 | /* we have more than one transition */ |
d3d91c7c YO |
3368 | SV **tmp; |
3369 | U8 *ch; | |
5ee57374 YO |
3370 | /* if this is the first state there is no common prefix |
3371 | * to extract, so we can exit */ | |
8e11feef | 3372 | if ( state == 1 ) break; |
d3d91c7c YO |
3373 | tmp = av_fetch( revcharmap, ofs, 0); |
3374 | ch = (U8*)SvPV_nolen_const( *tmp ); | |
3375 | ||
5ee57374 YO |
3376 | /* if we are on count 2 then we need to initialize the |
3377 | * bitmap, and store the previous char if there was one | |
3378 | * in it*/ | |
3dab1dad | 3379 | if ( count == 2 ) { |
5ee57374 | 3380 | /* clear the bitmap */ |
3dab1dad YO |
3381 | Zero(trie->bitmap, ANYOF_BITMAP_SIZE, char); |
3382 | DEBUG_OPTIMISE_r( | |
147e3846 | 3383 | Perl_re_indentf( aTHX_ "New Start State=%" UVuf " Class: [", |
cb41e5d6 | 3384 | depth+1, |
786e8c11 | 3385 | (UV)state)); |
ee0dfd0b YO |
3386 | if (first_ofs >= 0) { |
3387 | SV ** const tmp = av_fetch( revcharmap, first_ofs, 0); | |
be8e71aa | 3388 | const U8 * const ch = (U8*)SvPV_nolen_const( *tmp ); |
8e11feef | 3389 | |
8bcafbf4 | 3390 | TRIE_BITMAP_SET_FOLDED(trie,*ch,folder); |
3dab1dad | 3391 | DEBUG_OPTIMISE_r( |
6ad9a8ab | 3392 | Perl_re_printf( aTHX_ "%s", (char*)ch) |
3dab1dad | 3393 | ); |
8e11feef RGS |
3394 | } |
3395 | } | |
8bcafbf4 YO |
3396 | /* store the current firstchar in the bitmap */ |
3397 | TRIE_BITMAP_SET_FOLDED(trie,*ch,folder); | |
6ad9a8ab | 3398 | DEBUG_OPTIMISE_r(Perl_re_printf( aTHX_ "%s", ch)); |
8e11feef | 3399 | } |
ee0dfd0b | 3400 | first_ofs = ofs; |
8e11feef | 3401 | } |
3dab1dad YO |
3402 | } |
3403 | if ( count == 1 ) { | |
5ee57374 YO |
3404 | /* This state has only one transition, its transition is part |
3405 | * of a common prefix - we need to concatenate the char it | |
3406 | * represents to what we have so far. */ | |
ee0dfd0b | 3407 | SV **tmp = av_fetch( revcharmap, first_ofs, 0); |
c490c714 YO |
3408 | STRLEN len; |
3409 | char *ch = SvPV( *tmp, len ); | |
de734bd5 A |
3410 | DEBUG_OPTIMISE_r({ |
3411 | SV *sv=sv_newmortal(); | |
147e3846 | 3412 | Perl_re_indentf( aTHX_ "Prefix State: %" UVuf " Ofs:%" UVuf " Char='%s'\n", |
cb41e5d6 | 3413 | depth+1, |
ee0dfd0b | 3414 | (UV)state, (UV)first_ofs, |
538e84ed | 3415 | pv_pretty(sv, SvPV_nolen_const(*tmp), SvCUR(*tmp), 6, |
de734bd5 A |
3416 | PL_colors[0], PL_colors[1], |
3417 | (SvUTF8(*tmp) ? PERL_PV_ESCAPE_UNI : 0) | | |
538e84ed | 3418 | PERL_PV_ESCAPE_FIRSTCHAR |
de734bd5 A |
3419 | ) |
3420 | ); | |
3421 | }); | |
3dab1dad YO |
3422 | if ( state==1 ) { |
3423 | OP( convert ) = nodetype; | |
3424 | str=STRING(convert); | |
3425 | STR_LEN(convert)=0; | |
3426 | } | |
c490c714 YO |
3427 | STR_LEN(convert) += len; |
3428 | while (len--) | |
de734bd5 | 3429 | *str++ = *ch++; |
8e11feef | 3430 | } else { |
538e84ed | 3431 | #ifdef DEBUGGING |
8e11feef | 3432 | if (state>1) |
6ad9a8ab | 3433 | DEBUG_OPTIMISE_r(Perl_re_printf( aTHX_ "]\n")); |
f9049ba1 | 3434 | #endif |
8e11feef RGS |
3435 | break; |
3436 | } | |
3437 | } | |
2e64971a | 3438 | trie->prefixlen = (state-1); |
3dab1dad | 3439 | if (str) { |
8e11feef | 3440 | regnode *n = convert+NODE_SZ_STR(convert); |
07be1b83 | 3441 | NEXT_OFF(convert) = NODE_SZ_STR(convert); |
8e11feef | 3442 | trie->startstate = state; |
07be1b83 YO |
3443 | trie->minlen -= (state - 1); |
3444 | trie->maxlen -= (state - 1); | |
33809eae JH |
3445 | #ifdef DEBUGGING |
3446 | /* At least the UNICOS C compiler choked on this | |
3447 | * being argument to DEBUG_r(), so let's just have | |
3448 | * it right here. */ | |
3449 | if ( | |
3450 | #ifdef PERL_EXT_RE_BUILD | |
3451 | 1 | |
3452 | #else | |
3453 | DEBUG_r_TEST | |
3454 | #endif | |
3455 | ) { | |
3456 | regnode *fix = convert; | |
3457 | U32 word = trie->wordcount; | |
3458 | mjd_nodelen++; | |
3459 | Set_Node_Offset_Length(convert, mjd_offset, state - 1); | |
3460 | while( ++fix < n ) { | |
3461 | Set_Node_Offset_Length(fix, 0, 0); | |
3462 | } | |
3463 | while (word--) { | |
3464 | SV ** const tmp = av_fetch( trie_words, word, 0 ); | |
3465 | if (tmp) { | |
3466 | if ( STR_LEN(convert) <= SvCUR(*tmp) ) | |
3467 | sv_chop(*tmp, SvPV_nolen(*tmp) + STR_LEN(convert)); | |
3468 | else | |
3469 | sv_chop(*tmp, SvPV_nolen(*tmp) + SvCUR(*tmp)); | |
3470 | } | |
3471 | } | |
3472 | } | |
3473 | #endif | |
8e11feef RGS |
3474 | if (trie->maxlen) { |
3475 | convert = n; | |
3476 | } else { | |
3dab1dad | 3477 | NEXT_OFF(convert) = (U16)(tail - convert); |
a5ca303d | 3478 | DEBUG_r(optimize= n); |
3dab1dad YO |
3479 | } |
3480 | } | |
3481 | } | |
538e84ed KW |
3482 | if (!jumper) |
3483 | jumper = last; | |
3dab1dad | 3484 | if ( trie->maxlen ) { |
8e11feef RGS |
3485 | NEXT_OFF( convert ) = (U16)(tail - convert); |
3486 | ARG_SET( convert, data_slot ); | |
538e84ed KW |
3487 | /* Store the offset to the first unabsorbed branch in |
3488 | jump[0], which is otherwise unused by the jump logic. | |
786e8c11 | 3489 | We use this when dumping a trie and during optimisation. */ |
538e84ed | 3490 | if (trie->jump) |