Document where to find maintainers of dual live modules
[p5sagit/p5-mst-13.2.git] / regcomp.h
1 /*    regcomp.h
2  *
3  *    Copyright (C) 1991, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999,
4  *    2000, 2001, 2002, 2003, 2005 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 #define NEXT_OFF(p) ((p)->next_off)
158 #define NODE_ALIGN(node)
159 #define NODE_ALIGN_FILL(node) ((node)->flags = 0xde) /* deadbeef */
160
161 #define SIZE_ALIGN NODE_ALIGN
162
163 #undef OP
164 #undef OPERAND
165 #undef MASK
166 #undef STRING
167
168 #define OP(p)           ((p)->type)
169 #define OPERAND(p)      (((struct regnode_string *)p)->string)
170 #define MASK(p)         ((char*)OPERAND(p))
171 #define STR_LEN(p)      (((struct regnode_string *)p)->str_len)
172 #define STRING(p)       (((struct regnode_string *)p)->string)
173 #define STR_SZ(l)       ((l + sizeof(regnode) - 1) / sizeof(regnode))
174 #define NODE_SZ_STR(p)  (STR_SZ(STR_LEN(p))+1)
175
176 #undef NODE_ALIGN
177 #undef ARG_LOC
178 #undef NEXTOPER
179 #undef PREVOPER
180
181 #define NODE_ALIGN(node)
182 #define ARG_LOC(p)      (((struct regnode_1 *)p)->arg1)
183 #define ARG1_LOC(p)     (((struct regnode_2 *)p)->arg1)
184 #define ARG2_LOC(p)     (((struct regnode_2 *)p)->arg2)
185 #define NODE_STEP_REGNODE       1       /* sizeof(regnode)/sizeof(regnode) */
186 #define EXTRA_STEP_2ARGS        EXTRA_SIZE(struct regnode_2)
187
188 #define NODE_STEP_B     4
189
190 #define NEXTOPER(p)     ((p) + NODE_STEP_REGNODE)
191 #define PREVOPER(p)     ((p) - NODE_STEP_REGNODE)
192
193 #define FILL_ADVANCE_NODE(ptr, op) STMT_START { \
194     (ptr)->type = op;    (ptr)->next_off = 0;   (ptr)++; } STMT_END
195 #define FILL_ADVANCE_NODE_ARG(ptr, op, arg) STMT_START { \
196     ARG_SET(ptr, arg);  FILL_ADVANCE_NODE(ptr, op); (ptr) += 1; } STMT_END
197
198 #define REG_MAGIC 0234
199
200 #define SIZE_ONLY (RExC_emit == &PL_regdummy)
201
202 /* Flags for node->flags of ANYOF */
203
204 #define ANYOF_CLASS             0x08    /* has [[:blah:]] classes */
205 #define ANYOF_INVERT            0x04
206 #define ANYOF_FOLD              0x02
207 #define ANYOF_LOCALE            0x01
208
209 /* Used for regstclass only */
210 #define ANYOF_EOS               0x10            /* Can match an empty string too */
211
212 /* There is a character or a range past 0xff */
213 #define ANYOF_UNICODE           0x20
214 #define ANYOF_UNICODE_ALL       0x40    /* Can match any char past 0xff */
215
216 /* size of node is large (includes class pointer) */
217 #define ANYOF_LARGE             0x80
218
219 /* Are there any runtime flags on in this node? */
220 #define ANYOF_RUNTIME(s)        (ANYOF_FLAGS(s) & 0x0f)
221
222 #define ANYOF_FLAGS_ALL         0xff
223
224 /* Character classes for node->classflags of ANYOF */
225 /* Should be synchronized with a table in regprop() */
226 /* 2n should pair with 2n+1 */
227
228 #define ANYOF_ALNUM      0      /* \w, PL_utf8_alnum, utf8::IsWord, ALNUM */
229 #define ANYOF_NALNUM     1
230 #define ANYOF_SPACE      2      /* \s */
231 #define ANYOF_NSPACE     3
232 #define ANYOF_DIGIT      4
233 #define ANYOF_NDIGIT     5
234 #define ANYOF_ALNUMC     6      /* isalnum(3), utf8::IsAlnum, ALNUMC */
235 #define ANYOF_NALNUMC    7
236 #define ANYOF_ALPHA      8
237 #define ANYOF_NALPHA     9
238 #define ANYOF_ASCII     10
239 #define ANYOF_NASCII    11
240 #define ANYOF_CNTRL     12
241 #define ANYOF_NCNTRL    13
242 #define ANYOF_GRAPH     14
243 #define ANYOF_NGRAPH    15
244 #define ANYOF_LOWER     16
245 #define ANYOF_NLOWER    17
246 #define ANYOF_PRINT     18
247 #define ANYOF_NPRINT    19
248 #define ANYOF_PUNCT     20
249 #define ANYOF_NPUNCT    21
250 #define ANYOF_UPPER     22
251 #define ANYOF_NUPPER    23
252 #define ANYOF_XDIGIT    24
253 #define ANYOF_NXDIGIT   25
254 #define ANYOF_PSXSPC    26      /* POSIX space: \s plus the vertical tab */
255 #define ANYOF_NPSXSPC   27
256 #define ANYOF_BLANK     28      /* GNU extension: space and tab: non-vertical space */
257 #define ANYOF_NBLANK    29
258
259 #define ANYOF_MAX       32
260
261 /* Backward source code compatibility. */
262
263 #define ANYOF_ALNUML     ANYOF_ALNUM
264 #define ANYOF_NALNUML    ANYOF_NALNUM
265 #define ANYOF_SPACEL     ANYOF_SPACE
266 #define ANYOF_NSPACEL    ANYOF_NSPACE
267
268 /* Utility macros for the bitmap and classes of ANYOF */
269
270 #define ANYOF_SIZE              (sizeof(struct regnode_charclass))
271 #define ANYOF_CLASS_SIZE        (sizeof(struct regnode_charclass_class))
272
273 #define ANYOF_FLAGS(p)          ((p)->flags)
274
275 #define ANYOF_BIT(c)            (1 << ((c) & 7))
276
277 #define ANYOF_CLASS_BYTE(p, c)  (((struct regnode_charclass_class*)(p))->classflags[((c) >> 3) & 3])
278 #define ANYOF_CLASS_SET(p, c)   (ANYOF_CLASS_BYTE(p, c) |=  ANYOF_BIT(c))
279 #define ANYOF_CLASS_CLEAR(p, c) (ANYOF_CLASS_BYTE(p, c) &= ~ANYOF_BIT(c))
280 #define ANYOF_CLASS_TEST(p, c)  (ANYOF_CLASS_BYTE(p, c) &   ANYOF_BIT(c))
281
282 #define ANYOF_CLASS_ZERO(ret)   Zero(((struct regnode_charclass_class*)(ret))->classflags, ANYOF_CLASSBITMAP_SIZE, char)
283 #define ANYOF_BITMAP_ZERO(ret)  Zero(((struct regnode_charclass*)(ret))->bitmap, ANYOF_BITMAP_SIZE, char)
284
285 #define ANYOF_BITMAP(p)         (((struct regnode_charclass*)(p))->bitmap)
286 #define ANYOF_BITMAP_BYTE(p, c) (ANYOF_BITMAP(p)[((c) >> 3) & 31])
287 #define ANYOF_BITMAP_SET(p, c)  (ANYOF_BITMAP_BYTE(p, c) |=  ANYOF_BIT(c))
288 #define ANYOF_BITMAP_CLEAR(p,c) (ANYOF_BITMAP_BYTE(p, c) &= ~ANYOF_BIT(c))
289 #define ANYOF_BITMAP_TEST(p, c) (ANYOF_BITMAP_BYTE(p, c) &   ANYOF_BIT(c))
290
291 #define ANYOF_BITMAP_SETALL(p)          \
292         memset (ANYOF_BITMAP(p), 255, ANYOF_BITMAP_SIZE)
293 #define ANYOF_BITMAP_CLEARALL(p)        \
294         Zero (ANYOF_BITMAP(p), ANYOF_BITMAP_SIZE)
295 /* Check that all 256 bits are all set.  Used in S_cl_is_anything()  */
296 #define ANYOF_BITMAP_TESTALLSET(p)      \
297         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)
298
299 #define ANYOF_SKIP              ((ANYOF_SIZE - 1)/sizeof(regnode))
300 #define ANYOF_CLASS_SKIP        ((ANYOF_CLASS_SIZE - 1)/sizeof(regnode))
301 #define ANYOF_CLASS_ADD_SKIP    (ANYOF_CLASS_SKIP - ANYOF_SKIP)
302
303 /*
304  * Utility definitions.
305  */
306 #ifndef CHARMASK
307 #  define UCHARAT(p)    ((int)*(const U8*)(p))
308 #else
309 #  define UCHARAT(p)    ((int)*(p)&CHARMASK)
310 #endif
311
312 #define EXTRA_SIZE(guy) ((sizeof(guy)-1)/sizeof(struct regnode))
313
314 #define REG_SEEN_ZERO_LEN        1
315 #define REG_SEEN_LOOKBEHIND      2
316 #define REG_SEEN_GPOS            4
317 #define REG_SEEN_EVAL            8
318 #define REG_SEEN_CANY           16
319 #define REG_SEEN_SANY           REG_SEEN_CANY /* src bckwrd cmpt */
320
321 START_EXTERN_C
322
323 #include "regnodes.h"
324
325 /* The following have no fixed length. U8 so we can do strchr() on it. */
326 #ifndef DOINIT
327 EXTCONST U8 PL_varies[];
328 #else
329 EXTCONST U8 PL_varies[] = {
330     BRANCH, BACK, STAR, PLUS, CURLY, CURLYX, REF, REFF, REFFL,
331     WHILEM, CURLYM, CURLYN, BRANCHJ, IFTHEN, SUSPEND, CLUMP, 0
332 };
333 #endif
334
335 /* The following always have a length of 1. U8 we can do strchr() on it. */
336 /* (Note that length 1 means "one character" under UTF8, not "one octet".) */
337 #ifndef DOINIT
338 EXTCONST U8 PL_simple[];
339 #else
340 EXTCONST U8 PL_simple[] = {
341     REG_ANY,    SANY,   CANY,
342     ANYOF,
343     ALNUM,      ALNUML,
344     NALNUM,     NALNUML,
345     SPACE,      SPACEL,
346     NSPACE,     NSPACEL,
347     DIGIT,      NDIGIT,
348     0
349 };
350 #endif
351
352 END_EXTERN_C
353
354 typedef struct re_scream_pos_data_s
355 {
356     char **scream_olds;         /* match pos */
357     I32 *scream_pos;            /* Internal iterator of scream. */
358 } re_scream_pos_data;
359
360 /* .what is a character array with one character for each member of .data
361  * The character describes the function of the corresponding .data item:
362  *   f - start-class data for regstclass optimization
363  *   n - Root of op tree for (?{EVAL}) item
364  *   o - Start op for (?{EVAL}) item
365  *   p - Pad for (?{EVAL} item
366  *   s - swash for unicode-style character class, and the multicharacter
367  *       strings resulting from casefolding the single-character entries
368  *       in the character class
369  *   t - trie struct
370  * 20010712 mjd@plover.com
371  * (Remember to update re_dup() and pregfree() if you add any items.)
372  */
373 struct reg_data {
374     U32 count;
375     U8 *what;
376     void* data[1];
377 };
378
379 struct reg_substr_datum {
380     I32 min_offset;
381     I32 max_offset;
382     SV *substr;         /* non-utf8 variant */
383     SV *utf8_substr;    /* utf8 variant */
384 };
385
386 struct reg_substr_data {
387     struct reg_substr_datum data[3];    /* Actual array */
388 };
389
390 #define anchored_substr substrs->data[0].substr
391 #define anchored_utf8 substrs->data[0].utf8_substr
392 #define anchored_offset substrs->data[0].min_offset
393 #define float_substr substrs->data[1].substr
394 #define float_utf8 substrs->data[1].utf8_substr
395 #define float_min_offset substrs->data[1].min_offset
396 #define float_max_offset substrs->data[1].max_offset
397 #define check_substr substrs->data[2].substr
398 #define check_utf8 substrs->data[2].utf8_substr
399 #define check_offset_min substrs->data[2].min_offset
400 #define check_offset_max substrs->data[2].max_offset
401
402
403
404 /* trie related stuff */
405 /* an accepting state/position*/
406 struct _reg_trie_accepted {
407     U8   *endpos;
408     U16  wordnum;
409 };
410 /* a transition record for the state machine. the
411    check field determines which state "owns" the
412    transition. the char the transition is for is
413    determined by offset from the owning states base
414    field.  the next field determines which state
415    is to be transitioned to if any.
416 */
417 struct _reg_trie_trans {
418   U32 next;
419   U32 check;
420 };
421
422 /* a transition list element for the list based representation */
423 struct _reg_trie_trans_list_elem {
424     U16 forid;
425     U32 newstate;
426 };
427 typedef struct _reg_trie_trans_list_elem reg_trie_trans_le;
428
429 /* a state for compressed nodes. base is an offset
430   into an array of reg_trie_trans array. If wordnum is
431   nonzero the state is accepting. if base is zero then
432   the state has no children (and will be accepting)
433 */
434 struct _reg_trie_state {
435   U16 wordnum;
436   union {
437     U32                base;
438     reg_trie_trans_le* list;
439   } trans;
440 };
441
442
443
444 typedef struct _reg_trie_accepted reg_trie_accepted;
445 typedef struct _reg_trie_state    reg_trie_state;
446 typedef struct _reg_trie_trans    reg_trie_trans;
447
448
449 /* anything in here that needs to be freed later
450 should be dealt with in pregfree */
451 struct _reg_trie_data {
452     U16              uniquecharcount;
453     U16              wordcount;
454     STRLEN           charcount;
455     U32              laststate;
456     U32              lasttrans;
457     U16              *charmap;
458     HV               *widecharmap;
459     reg_trie_state   *states;
460     reg_trie_trans   *trans;
461     U32              refcount;
462 #ifdef DEBUGGING
463     AV               *words;
464     AV               *revcharmap;
465 #endif
466 };
467
468 typedef struct _reg_trie_data reg_trie_data;
469
470 /* these defines assume uniquecharcount is the correct variable, and state may be evaluated twice */
471 #define TRIE_NODENUM(state) (((state)-1)/(trie->uniquecharcount)+1)
472 #define SAFE_TRIE_NODENUM(state) ((state) ? (((state)-1)/(trie->uniquecharcount)+1) : (state))
473 #define TRIE_NODEIDX(state) ((state) ? (((state)-1)*(trie->uniquecharcount)+1) : (state))
474
475 #define DO_TRIE 1
476 #define TRIE_DEBUG 1
477
478 #define RE_TRIE_MAXBUF_INIT 65536
479 #define RE_TRIE_MAXBUF_NAME "\022E_TRIE_MAXBUF"
480 #define RE_DEBUG_FLAGS "\022E_DEBUG_FLAGS"
481
482 /* If you change these be sure to update ext/re/re.pm as well */
483 #define RE_DEBUG_COMPILE       1
484 #define RE_DEBUG_EXECUTE       2
485 #define RE_DEBUG_TRIE_COMPILE  4
486 #define RE_DEBUG_TRIE_EXECUTE  8
487 #define RE_DEBUG_TRIE_MORE    16
488 #define RE_DEBUG_OPTIMISE     32
489 #define RE_DEBUG_OFFSETS      64
490
491 #define DEBUG_OPTIMISE_r(x) DEBUG_r( if (SvIV(re_debug_flags) & RE_DEBUG_OPTIMISE) x  )
492 #define DEBUG_EXECUTE_r(x) DEBUG_r( if (SvIV(re_debug_flags) & RE_DEBUG_EXECUTE) x  )
493 #define DEBUG_COMPILE_r(x) DEBUG_r( if (SvIV(re_debug_flags) & RE_DEBUG_COMPILE) x  )
494 #define DEBUG_OFFSETS_r(x) DEBUG_r( if (SvIV(re_debug_flags) & RE_DEBUG_OFFSETS) x  )
495 #define DEBUG_TRIE_r(x) DEBUG_r( \
496    if (SvIV(re_debug_flags) & RE_DEBUG_TRIE_COMPILE       \
497        || SvIV(re_debug_flags) & RE_DEBUG_TRIE_EXECUTE )  \
498    x  \
499 )
500 #define DEBUG_TRIE_EXECUTE_r(x) \
501     DEBUG_r( if (SvIV(re_debug_flags) & RE_DEBUG_TRIE_EXECUTE) x )
502
503 #define DEBUG_TRIE_COMPILE_r(x) \
504     DEBUG_r( if (SvIV(re_debug_flags) & RE_DEBUG_TRIE_COMPILE) x )
505
506 #define DEBUG_TRIE_EXECUTE_MORE_r(x) \
507     DEBUG_TRIE_EXECUTE_r( if (SvIV(re_debug_flags) & RE_DEBUG_TRIE_MORE) x )
508
509 #define DEBUG_TRIE_COMPILE_MORE_r(x) \
510     DEBUG_TRIE_COMPILE_r( if (SvIV(re_debug_flags) & RE_DEBUG_TRIE_MORE) x )
511
512 #define GET_RE_DEBUG_FLAGS DEBUG_r( \
513         re_debug_flags=get_sv(RE_DEBUG_FLAGS, 1); \
514         if (!SvIOK(re_debug_flags)) { \
515             sv_setiv(re_debug_flags, RE_DEBUG_COMPILE | RE_DEBUG_EXECUTE | RE_DEBUG_OFFSETS); \
516         } \
517     )
518
519
520 #ifdef DEBUGGING
521 #define GET_RE_DEBUG_FLAGS_DECL SV *re_debug_flags = NULL; GET_RE_DEBUG_FLAGS;
522 #else
523 #define GET_RE_DEBUG_FLAGS_DECL
524 #endif
525
526