This is a live mirror of the Perl 5 development currently hosted at https://github.com/perl/perl5
Re: regexp trie fails compile on VMS
[perl5.git] / regcomp.h
1 /*    regcomp.h
2  *
3  *    Copyright (C) 1991, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999,
4  *    2000, 2001, 2002, 2003, by Larry Wall and others
5  *
6  *    You may distribute under the terms of either the GNU General Public
7  *    License or the Artistic License, as specified in the README file.
8  *
9  */
10
11 typedef OP OP_4tree;                    /* Will be redefined later. */
12
13 /*
14  * The "internal use only" fields in regexp.h are present to pass info from
15  * compile to execute that permits the execute phase to run lots faster on
16  * simple cases.  They are:
17  *
18  * regstart     sv that must begin a match; Nullch if none obvious
19  * reganch      is the match anchored (at beginning-of-line only)?
20  * regmust      string (pointer into program) that match must include, or NULL
21  *  [regmust changed to SV* for bminstr()--law]
22  * regmlen      length of regmust string
23  *  [regmlen not used currently]
24  *
25  * Regstart and reganch permit very fast decisions on suitable starting points
26  * for a match, cutting down the work a lot.  Regmust permits fast rejection
27  * of lines that cannot possibly match.  The regmust tests are costly enough
28  * that pregcomp() supplies a regmust only if the r.e. contains something
29  * potentially expensive (at present, the only such thing detected is * or +
30  * at the start of the r.e., which can involve a lot of backup).  Regmlen is
31  * supplied because the test in pregexec() needs it and pregcomp() is computing
32  * it anyway.
33  * [regmust is now supplied always.  The tests that use regmust have a
34  * heuristic that disables the test if it usually matches.]
35  *
36  * [In fact, we now use regmust in many cases to locate where the search
37  * starts in the string, so if regback is >= 0, the regmust search is never
38  * wasted effort.  The regback variable says how many characters back from
39  * where regmust matched is the earliest possible start of the match.
40  * For instance, /[a-z].foo/ has a regmust of 'foo' and a regback of 2.]
41  */
42
43 /*
44  * Structure for regexp "program".  This is essentially a linear encoding
45  * of a nondeterministic finite-state machine (aka syntax charts or
46  * "railroad normal form" in parsing technology).  Each node is an opcode
47  * plus a "next" pointer, possibly plus an operand.  "Next" pointers of
48  * all nodes except BRANCH implement concatenation; a "next" pointer with
49  * a BRANCH on both ends of it is connecting two alternatives.  (Here we
50  * have one of the subtle syntax dependencies:  an individual BRANCH (as
51  * opposed to a collection of them) is never concatenated with anything
52  * because of operator precedence.)  The operand of some types of node is
53  * a literal string; for others, it is a node leading into a sub-FSM.  In
54  * particular, the operand of a BRANCH node is the first node of the branch.
55  * (NB this is *not* a tree structure:  the tail of the branch connects
56  * to the thing following the set of BRANCHes.)  The opcodes are defined
57  * in regnodes.h which is generated from regcomp.sym by regcomp.pl.
58  */
59
60 /*
61  * A node is one char of opcode followed by two chars of "next" pointer.
62  * "Next" pointers are stored as two 8-bit pieces, high order first.  The
63  * value is a positive offset from the opcode of the node containing it.
64  * An operand, if any, simply follows the node.  (Note that much of the
65  * code generation knows about this implicit relationship.)
66  *
67  * Using two bytes for the "next" pointer is vast overkill for most things,
68  * but allows patterns to get big without disasters.
69  *
70  * [The "next" pointer is always aligned on an even
71  * boundary, and reads the offset directly as a short.  Also, there is no
72  * special test to reverse the sign of BACK pointers since the offset is
73  * stored negative.]
74  */
75
76 struct regnode_string {
77     U8  str_len;
78     U8  type;
79     U16 next_off;
80     char string[1];
81 };
82
83 struct regnode_1 {
84     U8  flags;
85     U8  type;
86     U16 next_off;
87     U32 arg1;
88 };
89
90 struct regnode_2 {
91     U8  flags;
92     U8  type;
93     U16 next_off;
94     U16 arg1;
95     U16 arg2;
96 };
97
98 #define ANYOF_BITMAP_SIZE       32      /* 256 b/(8 b/B) */
99 #define ANYOF_CLASSBITMAP_SIZE   4      /* up to 32 (8*4) named classes */
100
101 struct regnode_charclass {
102     U8  flags;
103     U8  type;
104     U16 next_off;
105     U32 arg1;
106     char bitmap[ANYOF_BITMAP_SIZE];     /* only compile-time */
107 };
108
109 struct regnode_charclass_class {        /* has [[:blah:]] classes */
110     U8  flags;                          /* should have ANYOF_CLASS here */
111     U8  type;
112     U16 next_off;
113     U32 arg1;
114     char bitmap[ANYOF_BITMAP_SIZE];             /* both compile-time */
115     char classflags[ANYOF_CLASSBITMAP_SIZE];    /* and run-time */
116 };
117
118 /* XXX fix this description.
119    Impose a limit of REG_INFTY on various pattern matching operations
120    to limit stack growth and to avoid "infinite" recursions.
121 */
122 /* The default size for REG_INFTY is I16_MAX, which is the same as
123    SHORT_MAX (see perl.h).  Unfortunately I16 isn't necessarily 16 bits
124    (see handy.h).  On the Cray C90, sizeof(short)==4 and hence I16_MAX is
125    ((1<<31)-1), while on the Cray T90, sizeof(short)==8 and I16_MAX is
126    ((1<<63)-1).  To limit stack growth to reasonable sizes, supply a
127    smaller default.
128         --Andy Dougherty  11 June 1998
129 */
130 #if SHORTSIZE > 2
131 #  ifndef REG_INFTY
132 #    define REG_INFTY ((1<<15)-1)
133 #  endif
134 #endif
135
136 #ifndef REG_INFTY
137 #  define REG_INFTY I16_MAX
138 #endif
139
140 #define ARG_VALUE(arg) (arg)
141 #define ARG__SET(arg,val) ((arg) = (val))
142
143 #undef ARG
144 #undef ARG1
145 #undef ARG2
146
147 #define ARG(p) ARG_VALUE(ARG_LOC(p))
148 #define ARG1(p) ARG_VALUE(ARG1_LOC(p))
149 #define ARG2(p) ARG_VALUE(ARG2_LOC(p))
150 #define ARG_SET(p, val) ARG__SET(ARG_LOC(p), (val))
151 #define ARG1_SET(p, val) ARG__SET(ARG1_LOC(p), (val))
152 #define ARG2_SET(p, val) ARG__SET(ARG2_LOC(p), (val))
153
154 #undef NEXT_OFF
155 #undef NODE_ALIGN
156
157 #ifndef lint
158 #  define NEXT_OFF(p) ((p)->next_off)
159 #  define NODE_ALIGN(node)
160 #  define NODE_ALIGN_FILL(node) ((node)->flags = 0xde) /* deadbeef */
161 #else /* lint */
162 #  define NEXT_OFF(p) 0
163 #  define NODE_ALIGN(node)
164 #  define NODE_ALIGN_FILL(node)
165 #endif /* lint */
166
167 #define SIZE_ALIGN NODE_ALIGN
168
169 #undef OP
170 #undef OPERAND
171 #undef MASK
172 #undef STRING
173
174 #define OP(p)           ((p)->type)
175 #define OPERAND(p)      (((struct regnode_string *)p)->string)
176 #define MASK(p)         ((char*)OPERAND(p))
177 #define STR_LEN(p)      (((struct regnode_string *)p)->str_len)
178 #define STRING(p)       (((struct regnode_string *)p)->string)
179 #define STR_SZ(l)       ((l + sizeof(regnode) - 1) / sizeof(regnode))
180 #define NODE_SZ_STR(p)  (STR_SZ(STR_LEN(p))+1)
181
182 #undef NODE_ALIGN
183 #undef ARG_LOC
184 #undef NEXTOPER
185 #undef PREVOPER
186
187 #define NODE_ALIGN(node)
188 #define ARG_LOC(p)      (((struct regnode_1 *)p)->arg1)
189 #define ARG1_LOC(p)     (((struct regnode_2 *)p)->arg1)
190 #define ARG2_LOC(p)     (((struct regnode_2 *)p)->arg2)
191 #define NODE_STEP_REGNODE       1       /* sizeof(regnode)/sizeof(regnode) */
192 #define EXTRA_STEP_2ARGS        EXTRA_SIZE(struct regnode_2)
193
194 #define NODE_STEP_B     4
195
196 #define NEXTOPER(p)     ((p) + NODE_STEP_REGNODE)
197 #define PREVOPER(p)     ((p) - NODE_STEP_REGNODE)
198
199 #define FILL_ADVANCE_NODE(ptr, op) STMT_START { \
200     (ptr)->type = op;    (ptr)->next_off = 0;   (ptr)++; } STMT_END
201 #define FILL_ADVANCE_NODE_ARG(ptr, op, arg) STMT_START { \
202     ARG_SET(ptr, arg);  FILL_ADVANCE_NODE(ptr, op); (ptr) += 1; } STMT_END
203
204 #define REG_MAGIC 0234
205
206 #define SIZE_ONLY (RExC_emit == &PL_regdummy)
207
208 /* Flags for node->flags of ANYOF */
209
210 #define ANYOF_CLASS             0x08    /* has [[:blah:]] classes */
211 #define ANYOF_INVERT            0x04
212 #define ANYOF_FOLD              0x02
213 #define ANYOF_LOCALE            0x01
214
215 /* Used for regstclass only */
216 #define ANYOF_EOS               0x10            /* Can match an empty string too */
217
218 /* There is a character or a range past 0xff */
219 #define ANYOF_UNICODE           0x20
220 #define ANYOF_UNICODE_ALL       0x40    /* Can match any char past 0xff */
221
222 /* size of node is large (includes class pointer) */
223 #define ANYOF_LARGE             0x80
224
225 /* Are there any runtime flags on in this node? */
226 #define ANYOF_RUNTIME(s)        (ANYOF_FLAGS(s) & 0x0f)
227
228 #define ANYOF_FLAGS_ALL         0xff
229
230 /* Character classes for node->classflags of ANYOF */
231 /* Should be synchronized with a table in regprop() */
232 /* 2n should pair with 2n+1 */
233
234 #define ANYOF_ALNUM      0      /* \w, PL_utf8_alnum, utf8::IsWord, ALNUM */
235 #define ANYOF_NALNUM     1
236 #define ANYOF_SPACE      2      /* \s */
237 #define ANYOF_NSPACE     3
238 #define ANYOF_DIGIT      4
239 #define ANYOF_NDIGIT     5
240 #define ANYOF_ALNUMC     6      /* isalnum(3), utf8::IsAlnum, ALNUMC */
241 #define ANYOF_NALNUMC    7
242 #define ANYOF_ALPHA      8
243 #define ANYOF_NALPHA     9
244 #define ANYOF_ASCII     10
245 #define ANYOF_NASCII    11
246 #define ANYOF_CNTRL     12
247 #define ANYOF_NCNTRL    13
248 #define ANYOF_GRAPH     14
249 #define ANYOF_NGRAPH    15
250 #define ANYOF_LOWER     16
251 #define ANYOF_NLOWER    17
252 #define ANYOF_PRINT     18
253 #define ANYOF_NPRINT    19
254 #define ANYOF_PUNCT     20
255 #define ANYOF_NPUNCT    21
256 #define ANYOF_UPPER     22
257 #define ANYOF_NUPPER    23
258 #define ANYOF_XDIGIT    24
259 #define ANYOF_NXDIGIT   25
260 #define ANYOF_PSXSPC    26      /* POSIX space: \s plus the vertical tab */
261 #define ANYOF_NPSXSPC   27
262 #define ANYOF_BLANK     28      /* GNU extension: space and tab: non-vertical space */
263 #define ANYOF_NBLANK    29
264
265 #define ANYOF_MAX       32
266
267 /* Backward source code compatibility. */
268
269 #define ANYOF_ALNUML     ANYOF_ALNUM
270 #define ANYOF_NALNUML    ANYOF_NALNUM
271 #define ANYOF_SPACEL     ANYOF_SPACE
272 #define ANYOF_NSPACEL    ANYOF_NSPACE
273
274 /* Utility macros for the bitmap and classes of ANYOF */
275
276 #define ANYOF_SIZE              (sizeof(struct regnode_charclass))
277 #define ANYOF_CLASS_SIZE        (sizeof(struct regnode_charclass_class))
278
279 #define ANYOF_FLAGS(p)          ((p)->flags)
280
281 #define ANYOF_BIT(c)            (1 << ((c) & 7))
282
283 #define ANYOF_CLASS_BYTE(p, c)  (((struct regnode_charclass_class*)(p))->classflags[((c) >> 3) & 3])
284 #define ANYOF_CLASS_SET(p, c)   (ANYOF_CLASS_BYTE(p, c) |=  ANYOF_BIT(c))
285 #define ANYOF_CLASS_CLEAR(p, c) (ANYOF_CLASS_BYTE(p, c) &= ~ANYOF_BIT(c))
286 #define ANYOF_CLASS_TEST(p, c)  (ANYOF_CLASS_BYTE(p, c) &   ANYOF_BIT(c))
287
288 #define ANYOF_CLASS_ZERO(ret)   Zero(((struct regnode_charclass_class*)(ret))->classflags, ANYOF_CLASSBITMAP_SIZE, char)
289 #define ANYOF_BITMAP_ZERO(ret)  Zero(((struct regnode_charclass*)(ret))->bitmap, ANYOF_BITMAP_SIZE, char)
290
291 #define ANYOF_BITMAP(p)         (((struct regnode_charclass*)(p))->bitmap)
292 #define ANYOF_BITMAP_BYTE(p, c) (ANYOF_BITMAP(p)[((c) >> 3) & 31])
293 #define ANYOF_BITMAP_SET(p, c)  (ANYOF_BITMAP_BYTE(p, c) |=  ANYOF_BIT(c))
294 #define ANYOF_BITMAP_CLEAR(p,c) (ANYOF_BITMAP_BYTE(p, c) &= ~ANYOF_BIT(c))
295 #define ANYOF_BITMAP_TEST(p, c) (ANYOF_BITMAP_BYTE(p, c) &   ANYOF_BIT(c))
296
297 #define ANYOF_BITMAP_SETALL(p)          \
298         memset (ANYOF_BITMAP(p), 255, ANYOF_BITMAP_SIZE)
299 #define ANYOF_BITMAP_CLEARALL(p)        \
300         Zero (ANYOF_BITMAP(p), ANYOF_BITMAP_SIZE)
301 /* Check that all 256 bits are all set.  Used in S_cl_is_anything()  */
302 #define ANYOF_BITMAP_TESTALLSET(p)      \
303         memEQ (ANYOF_BITMAP(p), "\377\377\377\377\377\377\377\377\377\377\377\377\377\377\377\377\377\377\377\377\377\377\377\377\377\377\377\377\377\377\377\377", ANYOF_BITMAP_SIZE)
304
305 #define ANYOF_SKIP              ((ANYOF_SIZE - 1)/sizeof(regnode))
306 #define ANYOF_CLASS_SKIP        ((ANYOF_CLASS_SIZE - 1)/sizeof(regnode))
307 #define ANYOF_CLASS_ADD_SKIP    (ANYOF_CLASS_SKIP - ANYOF_SKIP)
308
309 /*
310  * Utility definitions.
311  */
312 #ifndef lint
313 #ifndef CHARMASK
314 #define UCHARAT(p)      ((int)*(U8*)(p))
315 #else
316 #define UCHARAT(p)      ((int)*(p)&CHARMASK)
317 #endif
318 #else /* lint */
319 #define UCHARAT(p)      PL_regdummy
320 #endif /* lint */
321
322 #define EXTRA_SIZE(guy) ((sizeof(guy)-1)/sizeof(struct regnode))
323
324 #define REG_SEEN_ZERO_LEN        1
325 #define REG_SEEN_LOOKBEHIND      2
326 #define REG_SEEN_GPOS            4
327 #define REG_SEEN_EVAL            8
328 #define REG_SEEN_CANY           16
329 #define REG_SEEN_SANY           REG_SEEN_CANY /* src bckwrd cmpt */
330
331 START_EXTERN_C
332
333 #include "regnodes.h"
334
335 /* The following have no fixed length. U8 so we can do strchr() on it. */
336 #ifndef DOINIT
337 EXTCONST U8 PL_varies[];
338 #else
339 EXTCONST U8 PL_varies[] = {
340     BRANCH, BACK, STAR, PLUS, CURLY, CURLYX, REF, REFF, REFFL, 
341     WHILEM, CURLYM, CURLYN, BRANCHJ, IFTHEN, SUSPEND, CLUMP, 0
342 };
343 #endif
344
345 /* The following always have a length of 1. U8 we can do strchr() on it. */
346 /* (Note that length 1 means "one character" under UTF8, not "one octet".) */
347 #ifndef DOINIT
348 EXTCONST U8 PL_simple[];
349 #else
350 EXTCONST U8 PL_simple[] = {
351     REG_ANY,    SANY,   CANY,
352     ANYOF,
353     ALNUM,      ALNUML,
354     NALNUM,     NALNUML,
355     SPACE,      SPACEL,
356     NSPACE,     NSPACEL,
357     DIGIT,      NDIGIT,
358     0
359 };
360 #endif
361
362 END_EXTERN_C
363
364 typedef struct re_scream_pos_data_s
365 {
366     char **scream_olds;         /* match pos */
367     I32 *scream_pos;            /* Internal iterator of scream. */
368 } re_scream_pos_data;
369
370 /* .what is a character array with one character for each member of .data
371  * The character describes the function of the corresponding .data item:
372  *   f - start-class data for regstclass optimization  
373  *   n - Root of op tree for (?{EVAL}) item
374  *   o - Start op for (?{EVAL}) item
375  *   p - Pad for (?{EVAL} item
376  *   s - swash for unicode-style character class, and the multicharacter
377  *       strings resulting from casefolding the single-character entries
378  *       in the character class
379  *   t - trie struct
380  * 20010712 mjd@plover.com
381  * (Remember to update re_dup() and pregfree() if you add any items.)
382  */
383 struct reg_data {
384     U32 count;
385     U8 *what;
386     void* data[1];
387 };
388
389 struct reg_substr_datum {
390     I32 min_offset;
391     I32 max_offset;
392     SV *substr;         /* non-utf8 variant */
393     SV *utf8_substr;    /* utf8 variant */
394 };
395
396 struct reg_substr_data {
397     struct reg_substr_datum data[3];    /* Actual array */
398 };
399
400 #define anchored_substr substrs->data[0].substr
401 #define anchored_utf8 substrs->data[0].utf8_substr
402 #define anchored_offset substrs->data[0].min_offset
403 #define float_substr substrs->data[1].substr
404 #define float_utf8 substrs->data[1].utf8_substr
405 #define float_min_offset substrs->data[1].min_offset
406 #define float_max_offset substrs->data[1].max_offset
407 #define check_substr substrs->data[2].substr
408 #define check_utf8 substrs->data[2].utf8_substr
409 #define check_offset_min substrs->data[2].min_offset
410 #define check_offset_max substrs->data[2].max_offset
411
412
413
414 /* trie related stuff */
415 /* an accepting state/position*/
416 struct _reg_trie_accepted {
417     U8   *endpos;
418     U16  wordnum;
419 };
420 /* a transition record for the state machine. the
421    check field determines which state "owns" the
422    transition. the char the transition is for is
423    determined by offset from the owning states base
424    field.  the next field determines which state
425    is to be transitioned to if any.
426 */
427 struct _reg_trie_trans {
428   U32 next;
429   U32 check;
430 };
431
432 /* a transition list element for the list based representation */
433 struct _reg_trie_trans_list_elem {
434     U16 forid;
435     U32 newstate;
436 };
437 typedef struct _reg_trie_trans_list_elem reg_trie_trans_le;
438
439 /* a state for compressed nodes. base is an offset
440   into an array of reg_trie_trans array. If wordnum is
441   nonzero the state is accepting. if base is zero then
442   the state has no children (and will be accepting)
443 */
444 struct _reg_trie_state {
445   U16 wordnum;
446   union {
447     U32                base;
448     reg_trie_trans_le* list;
449   } trans;
450 };
451
452
453
454 typedef struct _reg_trie_accepted reg_trie_accepted;
455 typedef struct _reg_trie_state    reg_trie_state;
456 typedef struct _reg_trie_trans    reg_trie_trans;
457
458
459 /* anything in here that needs to be freed later
460 should be dealt with in pregfree */
461 struct _reg_trie_data {
462     U16              uniquecharcount;
463     U16              wordcount;
464     STRLEN           charcount;
465     U32              laststate;
466     U32              lasttrans;
467     U16              *charmap;
468     HV               *widecharmap;
469     reg_trie_state   *states;
470     reg_trie_trans   *trans;
471     U32              refcount;
472 #ifdef DEBUGGING
473     AV               *words;
474     AV               *revcharmap;
475 #endif
476 };
477
478 typedef struct _reg_trie_data reg_trie_data;
479
480 /* these defines assume uniquecharcount is the correct variable, and state may be evaluated twice */
481 #define TRIE_NODENUM(state) (((state)-1)/(trie->uniquecharcount)+1)
482 #define SAFE_TRIE_NODENUM(state) ((state) ? (((state)-1)/(trie->uniquecharcount)+1) : (state))
483 #define TRIE_NODEIDX(state) ((state) ? (((state)-1)*(trie->uniquecharcount)+1) : (state))
484
485 #define DO_TRIE 1
486 #define TRIE_DEBUG 1
487
488
489 #define TRIE_SIMPLE_MAX_BUFF 65536
490 #define RE_TRIE_MAXBUFF "\022E_TRIE_MAXBUFF"
491 #define RE_DEBUG_FLAGS "\022E_DEBUG_FLAGS"
492
493 /* If you change these be sure to update ext/re/re.pm as well */
494 #define RE_DEBUG_COMPILE       1
495 #define RE_DEBUG_EXECUTE       2
496 #define RE_DEBUG_TRIE_COMPILE  4
497 #define RE_DEBUG_TRIE_EXECUTE  8
498 #define RE_DEBUG_TRIE_MORE    16
499 #define RE_DEBUG_OPTIMISE     32
500 #define RE_DEBUG_OFFSETS      64
501
502 #define DEBUG_OPTIMISE_r(x) DEBUG_r( if (SvIV(re_debug_flags) & RE_DEBUG_OPTIMISE) x  )
503 #define DEBUG_EXECUTE_r(x) DEBUG_r( if (SvIV(re_debug_flags) & RE_DEBUG_EXECUTE) x  )
504 #define DEBUG_COMPILE_r(x) DEBUG_r( if (SvIV(re_debug_flags) & RE_DEBUG_COMPILE) x  )
505 #define DEBUG_OFFSETS_r(x) DEBUG_r( if (SvIV(re_debug_flags) & RE_DEBUG_OFFSETS) x  )
506 #define DEBUG_TRIE_r(x) DEBUG_r( \
507    if (SvIV(re_debug_flags) & RE_DEBUG_TRIE_COMPILE       \
508        || SvIV(re_debug_flags) & RE_DEBUG_TRIE_EXECUTE )  \
509    x  \
510 )
511 #define DEBUG_TRIE_EXECUTE_r(x) \
512     DEBUG_r( if (SvIV(re_debug_flags) & RE_DEBUG_TRIE_EXECUTE) x )
513
514 #define DEBUG_TRIE_COMPILE_r(x) \
515     DEBUG_r( if (SvIV(re_debug_flags) & RE_DEBUG_TRIE_COMPILE) x )
516
517 #define DEBUG_TRIE_EXECUTE_MORE_r(x) \
518     DEBUG_TRIE_EXECUTE_r( if (SvIV(re_debug_flags) & RE_DEBUG_TRIE_MORE) x )
519
520 #define DEBUG_TRIE_COMPILE_MORE_r(x) \
521     DEBUG_TRIE_COMPILE_r( if (SvIV(re_debug_flags) & RE_DEBUG_TRIE_MORE) x )
522
523 #define GET_RE_DEBUG_FLAGS DEBUG_r( \
524         re_debug_flags=get_sv(RE_DEBUG_FLAGS, 1); \
525         if (!SvIOK(re_debug_flags)) { \
526             sv_setiv(re_debug_flags, RE_DEBUG_COMPILE | RE_DEBUG_EXECUTE | RE_DEBUG_OFFSETS); \
527         } \
528     )
529
530
531 #ifdef DEBUGGING
532 #define GET_RE_DEBUG_FLAGS_DECL SV *re_debug_flags; GET_RE_DEBUG_FLAGS;
533 #else
534 #define GET_RE_DEBUG_FLAGS_DECL
535 #endif
536
537