home *** CD-ROM | disk | FTP | other *** search
/ Mac Easy 2010 May / Mac Life Ubuntu.iso / casper / filesystem.squashfs / usr / lib / perl / 5.10.0 / CORE / regcomp.h < prev    next >
Encoding:
C/C++ Source or Header  |  2009-06-26  |  27.8 KB  |  819 lines
  1. /*    regcomp.h
  2.  *
  3.  *    Copyright (C) 1991, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999,
  4.  *    2000, 2001, 2002, 2003, 2005, 2006, 2007, 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. #include "regcharclass.h"
  11.  
  12. typedef OP OP_4tree;            /* Will be redefined later. */
  13.  
  14.  
  15. /* Convert branch sequences to more efficient trie ops? */
  16. #define PERL_ENABLE_TRIE_OPTIMISATION 1
  17.  
  18. /* Be really agressive about optimising patterns with trie sequences? */
  19. #define PERL_ENABLE_EXTENDED_TRIE_OPTIMISATION 1
  20.  
  21. /* Should the optimiser take positive assertions into account? */
  22. #define PERL_ENABLE_POSITIVE_ASSERTION_STUDY 0
  23.  
  24. /* Not for production use: */
  25. #define PERL_ENABLE_EXPERIMENTAL_REGEX_OPTIMISATIONS 0
  26.  
  27. /* Activate offsets code - set to if 1 to enable */
  28. #ifdef DEBUGGING
  29. #define RE_TRACK_PATTERN_OFFSETS
  30. #endif
  31.  
  32. /* Unless the next line is uncommented it is illegal to combine lazy 
  33.    matching with possessive matching. Frankly it doesn't make much sense 
  34.    to allow it as X*?+ matches nothing, X+?+ matches a single char only, 
  35.    and X{min,max}?+ matches min times only.
  36.  */
  37. /* #define REG_ALLOW_MINMOD_SUSPEND */
  38.  
  39. /*
  40.  * The "internal use only" fields in regexp.h are present to pass info from
  41.  * compile to execute that permits the execute phase to run lots faster on
  42.  * simple cases.  They are:
  43.  *
  44.  * regstart    sv that must begin a match; NULL if none obvious
  45.  * reganch    is the match anchored (at beginning-of-line only)?
  46.  * regmust    string (pointer into program) that match must include, or NULL
  47.  *  [regmust changed to SV* for bminstr()--law]
  48.  * regmlen    length of regmust string
  49.  *  [regmlen not used currently]
  50.  *
  51.  * Regstart and reganch permit very fast decisions on suitable starting points
  52.  * for a match, cutting down the work a lot.  Regmust permits fast rejection
  53.  * of lines that cannot possibly match.  The regmust tests are costly enough
  54.  * that pregcomp() supplies a regmust only if the r.e. contains something
  55.  * potentially expensive (at present, the only such thing detected is * or +
  56.  * at the start of the r.e., which can involve a lot of backup).  Regmlen is
  57.  * supplied because the test in pregexec() needs it and pregcomp() is computing
  58.  * it anyway.
  59.  * [regmust is now supplied always.  The tests that use regmust have a
  60.  * heuristic that disables the test if it usually matches.]
  61.  *
  62.  * [In fact, we now use regmust in many cases to locate where the search
  63.  * starts in the string, so if regback is >= 0, the regmust search is never
  64.  * wasted effort.  The regback variable says how many characters back from
  65.  * where regmust matched is the earliest possible start of the match.
  66.  * For instance, /[a-z].foo/ has a regmust of 'foo' and a regback of 2.]
  67.  */
  68.  
  69. /*
  70.  * Structure for regexp "program".  This is essentially a linear encoding
  71.  * of a nondeterministic finite-state machine (aka syntax charts or
  72.  * "railroad normal form" in parsing technology).  Each node is an opcode
  73.  * plus a "next" pointer, possibly plus an operand.  "Next" pointers of
  74.  * all nodes except BRANCH implement concatenation; a "next" pointer with
  75.  * a BRANCH on both ends of it is connecting two alternatives.  (Here we
  76.  * have one of the subtle syntax dependencies:  an individual BRANCH (as
  77.  * opposed to a collection of them) is never concatenated with anything
  78.  * because of operator precedence.)  The operand of some types of node is
  79.  * a literal string; for others, it is a node leading into a sub-FSM.  In
  80.  * particular, the operand of a BRANCH node is the first node of the branch.
  81.  * (NB this is *not* a tree structure:  the tail of the branch connects
  82.  * to the thing following the set of BRANCHes.)  The opcodes are defined
  83.  * in regnodes.h which is generated from regcomp.sym by regcomp.pl.
  84.  */
  85.  
  86. /*
  87.  * A node is one char of opcode followed by two chars of "next" pointer.
  88.  * "Next" pointers are stored as two 8-bit pieces, high order first.  The
  89.  * value is a positive offset from the opcode of the node containing it.
  90.  * An operand, if any, simply follows the node.  (Note that much of the
  91.  * code generation knows about this implicit relationship.)
  92.  *
  93.  * Using two bytes for the "next" pointer is vast overkill for most things,
  94.  * but allows patterns to get big without disasters.
  95.  *
  96.  * [The "next" pointer is always aligned on an even
  97.  * boundary, and reads the offset directly as a short.  Also, there is no
  98.  * special test to reverse the sign of BACK pointers since the offset is
  99.  * stored negative.]
  100.  */
  101.  
  102. /* This is the stuff that used to live in regexp.h that was truly
  103.    private to the engine itself. It now lives here. */
  104.  
  105.  
  106.  
  107.  typedef struct regexp_internal {
  108.         int name_list_idx;    /* Optional data index of an array of paren names */
  109.         union {
  110.         U32 *offsets;           /* offset annotations 20001228 MJD
  111.                                        data about mapping the program to the
  112.                                        string -
  113.                                        offsets[0] is proglen when this is used
  114.                                        */
  115.             U32 proglen;
  116.         } u;
  117.  
  118.         regnode *regstclass;    /* Optional startclass as identified or constructed
  119.                                    by the optimiser */
  120.         struct reg_data *data;    /* Additional miscellaneous data used by the program.
  121.                                    Used to make it easier to clone and free arbitrary
  122.                                    data that the regops need. Often the ARG field of
  123.                                    a regop is an index into this structure */
  124.     regnode program[1];    /* Unwarranted chumminess with compiler. */
  125. } regexp_internal;
  126.  
  127. #define RXi_SET(x,y) (x)->pprivate = (void*)(y)   
  128. #define RXi_GET(x)   ((regexp_internal *)((x)->pprivate))
  129. #define RXi_GET_DECL(r,ri) regexp_internal *ri = RXi_GET(r)
  130. /*
  131.  * Flags stored in regexp->intflags
  132.  * These are used only internally to the regexp engine
  133.  *
  134.  * See regexp.h for flags used externally to the regexp engine
  135.  */
  136. #define PREGf_SKIP        0x00000001
  137. #define PREGf_IMPLICIT        0x00000002 /* Converted .* to ^.* */
  138. #define PREGf_NAUGHTY        0x00000004 /* how exponential is this pattern? */
  139. #define PREGf_VERBARG_SEEN    0x00000008
  140. #define PREGf_CUTGROUP_SEEN    0x00000010
  141.  
  142.  
  143. /* this is where the old regcomp.h started */
  144.  
  145. struct regnode_string {
  146.     U8    str_len;
  147.     U8  type;
  148.     U16 next_off;
  149.     char string[1];
  150. };
  151.  
  152. /* Argument bearing node - workhorse, 
  153.    arg1 is often for the data field */
  154. struct regnode_1 {
  155.     U8    flags;
  156.     U8  type;
  157.     U16 next_off;
  158.     U32 arg1;
  159. };
  160.  
  161. /* Similar to a regnode_1 but with an extra signed argument */
  162. struct regnode_2L {
  163.     U8    flags;
  164.     U8  type;
  165.     U16 next_off;
  166.     U32 arg1;
  167.     I32 arg2;
  168. };
  169.  
  170. /* 'Two field' -- Two 16 bit unsigned args */
  171. struct regnode_2 {
  172.     U8    flags;
  173.     U8  type;
  174.     U16 next_off;
  175.     U16 arg1;
  176.     U16 arg2;
  177. };
  178.  
  179.  
  180. #define ANYOF_BITMAP_SIZE    32    /* 256 b/(8 b/B) */
  181. #define ANYOF_CLASSBITMAP_SIZE     4    /* up to 40 (8*5) named classes */
  182.  
  183. /* also used by trie */
  184. struct regnode_charclass {
  185.     U8    flags;
  186.     U8  type;
  187.     U16 next_off;
  188.     U32 arg1;
  189.     char bitmap[ANYOF_BITMAP_SIZE];    /* only compile-time */
  190. };
  191.  
  192. struct regnode_charclass_class {    /* has [[:blah:]] classes */
  193.     U8    flags;                /* should have ANYOF_CLASS here */
  194.     U8  type;
  195.     U16 next_off;
  196.     U32 arg1;
  197.     char bitmap[ANYOF_BITMAP_SIZE];        /* both compile-time */
  198.     char classflags[ANYOF_CLASSBITMAP_SIZE];    /* and run-time */
  199. };
  200.  
  201. /* XXX fix this description.
  202.    Impose a limit of REG_INFTY on various pattern matching operations
  203.    to limit stack growth and to avoid "infinite" recursions.
  204. */
  205. /* The default size for REG_INFTY is I16_MAX, which is the same as
  206.    SHORT_MAX (see perl.h).  Unfortunately I16 isn't necessarily 16 bits
  207.    (see handy.h).  On the Cray C90, sizeof(short)==4 and hence I16_MAX is
  208.    ((1<<31)-1), while on the Cray T90, sizeof(short)==8 and I16_MAX is
  209.    ((1<<63)-1).  To limit stack growth to reasonable sizes, supply a
  210.    smaller default.
  211.     --Andy Dougherty  11 June 1998
  212. */
  213. #if SHORTSIZE > 2
  214. #  ifndef REG_INFTY
  215. #    define REG_INFTY ((1<<15)-1)
  216. #  endif
  217. #endif
  218.  
  219. #ifndef REG_INFTY
  220. #  define REG_INFTY I16_MAX
  221. #endif
  222.  
  223. #define ARG_VALUE(arg) (arg)
  224. #define ARG__SET(arg,val) ((arg) = (val))
  225.  
  226. #undef ARG
  227. #undef ARG1
  228. #undef ARG2
  229.  
  230. #define ARG(p) ARG_VALUE(ARG_LOC(p))
  231. #define ARG1(p) ARG_VALUE(ARG1_LOC(p))
  232. #define ARG2(p) ARG_VALUE(ARG2_LOC(p))
  233. #define ARG2L(p) ARG_VALUE(ARG2L_LOC(p))
  234.  
  235. #define ARG_SET(p, val) ARG__SET(ARG_LOC(p), (val))
  236. #define ARG1_SET(p, val) ARG__SET(ARG1_LOC(p), (val))
  237. #define ARG2_SET(p, val) ARG__SET(ARG2_LOC(p), (val))
  238. #define ARG2L_SET(p, val) ARG__SET(ARG2L_LOC(p), (val))
  239.  
  240. #undef NEXT_OFF
  241. #undef NODE_ALIGN
  242.  
  243. #define NEXT_OFF(p) ((p)->next_off)
  244. #define NODE_ALIGN(node)
  245. #define NODE_ALIGN_FILL(node) ((node)->flags = 0xde) /* deadbeef */
  246.  
  247. #define SIZE_ALIGN NODE_ALIGN
  248.  
  249. #undef OP
  250. #undef OPERAND
  251. #undef MASK
  252. #undef STRING
  253.  
  254. #define    OP(p)        ((p)->type)
  255. #define    OPERAND(p)    (((struct regnode_string *)p)->string)
  256. #define MASK(p)        ((char*)OPERAND(p))
  257. #define    STR_LEN(p)    (((struct regnode_string *)p)->str_len)
  258. #define    STRING(p)    (((struct regnode_string *)p)->string)
  259. #define STR_SZ(l)    ((l + sizeof(regnode) - 1) / sizeof(regnode))
  260. #define NODE_SZ_STR(p)    (STR_SZ(STR_LEN(p))+1)
  261.  
  262. #undef NODE_ALIGN
  263. #undef ARG_LOC
  264. #undef NEXTOPER
  265. #undef PREVOPER
  266.  
  267. #define    NODE_ALIGN(node)
  268. #define    ARG_LOC(p)    (((struct regnode_1 *)p)->arg1)
  269. #define    ARG1_LOC(p)    (((struct regnode_2 *)p)->arg1)
  270. #define    ARG2_LOC(p)    (((struct regnode_2 *)p)->arg2)
  271. #define ARG2L_LOC(p)    (((struct regnode_2L *)p)->arg2)
  272.  
  273. #define NODE_STEP_REGNODE    1    /* sizeof(regnode)/sizeof(regnode) */
  274. #define EXTRA_STEP_2ARGS    EXTRA_SIZE(struct regnode_2)
  275.  
  276. #define NODE_STEP_B    4
  277.  
  278. #define    NEXTOPER(p)    ((p) + NODE_STEP_REGNODE)
  279. #define    PREVOPER(p)    ((p) - NODE_STEP_REGNODE)
  280.  
  281. #define FILL_ADVANCE_NODE(ptr, op) STMT_START { \
  282.     (ptr)->type = op;    (ptr)->next_off = 0;   (ptr)++; } STMT_END
  283. #define FILL_ADVANCE_NODE_ARG(ptr, op, arg) STMT_START { \
  284.     ARG_SET(ptr, arg);  FILL_ADVANCE_NODE(ptr, op); (ptr) += 1; } STMT_END
  285.  
  286. #define REG_MAGIC 0234
  287.  
  288. #define SIZE_ONLY (RExC_emit == &PL_regdummy)
  289.  
  290. /* Flags for node->flags of ANYOF */
  291.  
  292. #define ANYOF_CLASS        0x08    /* has [[:blah:]] classes */
  293. #define ANYOF_INVERT        0x04
  294. #define ANYOF_FOLD        0x02
  295. #define ANYOF_LOCALE        0x01
  296.  
  297. /* Used for regstclass only */
  298. #define ANYOF_EOS        0x10        /* Can match an empty string too */
  299.  
  300. /* There is a character or a range past 0xff */
  301. #define ANYOF_UNICODE        0x20
  302. #define ANYOF_UNICODE_ALL    0x40    /* Can match any char past 0xff */
  303.  
  304. /* size of node is large (includes class pointer) */
  305. #define ANYOF_LARGE         0x80
  306.  
  307. /* Are there any runtime flags on in this node? */
  308. #define ANYOF_RUNTIME(s)    (ANYOF_FLAGS(s) & 0x0f)
  309.  
  310. #define ANYOF_FLAGS_ALL        0xff
  311.  
  312. /* Character classes for node->classflags of ANYOF */
  313. /* Should be synchronized with a table in regprop() */
  314. /* 2n should pair with 2n+1 */
  315.  
  316. #define ANYOF_ALNUM     0    /* \w, PL_utf8_alnum, utf8::IsWord, ALNUM */
  317. #define ANYOF_NALNUM     1
  318. #define ANYOF_SPACE     2    /* \s */
  319. #define ANYOF_NSPACE     3
  320. #define ANYOF_DIGIT     4
  321. #define ANYOF_NDIGIT     5
  322. #define ANYOF_ALNUMC     6    /* isalnum(3), utf8::IsAlnum, ALNUMC */
  323. #define ANYOF_NALNUMC     7
  324. #define ANYOF_ALPHA     8
  325. #define ANYOF_NALPHA     9
  326. #define ANYOF_ASCII    10
  327. #define ANYOF_NASCII    11
  328. #define ANYOF_CNTRL    12
  329. #define ANYOF_NCNTRL    13
  330. #define ANYOF_GRAPH    14
  331. #define ANYOF_NGRAPH    15
  332. #define ANYOF_LOWER    16
  333. #define ANYOF_NLOWER    17
  334. #define ANYOF_PRINT    18
  335. #define ANYOF_NPRINT    19
  336. #define ANYOF_PUNCT    20
  337. #define ANYOF_NPUNCT    21
  338. #define ANYOF_UPPER    22
  339. #define ANYOF_NUPPER    23
  340. #define ANYOF_XDIGIT    24
  341. #define ANYOF_NXDIGIT    25
  342. #define ANYOF_PSXSPC    26    /* POSIX space: \s plus the vertical tab */
  343. #define ANYOF_NPSXSPC    27
  344. #define ANYOF_BLANK    28    /* GNU extension: space and tab: non-vertical space */
  345. #define ANYOF_NBLANK    29
  346.  
  347. #define ANYOF_MAX    32
  348.  
  349. /* pseudo classes, not stored in the class bitmap, but used as flags
  350.    during compilation of char classes */
  351.  
  352. #define ANYOF_VERTWS    (ANYOF_MAX+1)
  353. #define ANYOF_NVERTWS    (ANYOF_MAX+2)
  354. #define ANYOF_HORIZWS    (ANYOF_MAX+3)
  355. #define ANYOF_NHORIZWS    (ANYOF_MAX+4)
  356.  
  357. /* Backward source code compatibility. */
  358.  
  359. #define ANYOF_ALNUML     ANYOF_ALNUM
  360. #define ANYOF_NALNUML     ANYOF_NALNUM
  361. #define ANYOF_SPACEL     ANYOF_SPACE
  362. #define ANYOF_NSPACEL     ANYOF_NSPACE
  363.  
  364. /* Utility macros for the bitmap and classes of ANYOF */
  365.  
  366. #define ANYOF_SIZE        (sizeof(struct regnode_charclass))
  367. #define ANYOF_CLASS_SIZE    (sizeof(struct regnode_charclass_class))
  368.  
  369. #define ANYOF_FLAGS(p)        ((p)->flags)
  370.  
  371. #define ANYOF_BIT(c)        (1 << ((c) & 7))
  372.  
  373. #define ANYOF_CLASS_BYTE(p, c)    (((struct regnode_charclass_class*)(p))->classflags[((c) >> 3) & 3])
  374. #define ANYOF_CLASS_SET(p, c)    (ANYOF_CLASS_BYTE(p, c) |=  ANYOF_BIT(c))
  375. #define ANYOF_CLASS_CLEAR(p, c)    (ANYOF_CLASS_BYTE(p, c) &= ~ANYOF_BIT(c))
  376. #define ANYOF_CLASS_TEST(p, c)    (ANYOF_CLASS_BYTE(p, c) &   ANYOF_BIT(c))
  377.  
  378. #define ANYOF_CLASS_ZERO(ret)    Zero(((struct regnode_charclass_class*)(ret))->classflags, ANYOF_CLASSBITMAP_SIZE, char)
  379. #define ANYOF_BITMAP_ZERO(ret)    Zero(((struct regnode_charclass*)(ret))->bitmap, ANYOF_BITMAP_SIZE, char)
  380.  
  381. #define ANYOF_BITMAP(p)        (((struct regnode_charclass*)(p))->bitmap)
  382. #define ANYOF_BITMAP_BYTE(p, c)    (ANYOF_BITMAP(p)[(((U8)(c)) >> 3) & 31])
  383. #define ANYOF_BITMAP_SET(p, c)    (ANYOF_BITMAP_BYTE(p, c) |=  ANYOF_BIT(c))
  384. #define ANYOF_BITMAP_CLEAR(p,c)    (ANYOF_BITMAP_BYTE(p, c) &= ~ANYOF_BIT(c))
  385. #define ANYOF_BITMAP_TEST(p, c)    (ANYOF_BITMAP_BYTE(p, c) &   ANYOF_BIT(c))
  386.  
  387. #define ANYOF_BITMAP_SETALL(p)        \
  388.     memset (ANYOF_BITMAP(p), 255, ANYOF_BITMAP_SIZE)
  389. #define ANYOF_BITMAP_CLEARALL(p)    \
  390.     Zero (ANYOF_BITMAP(p), ANYOF_BITMAP_SIZE)
  391. /* Check that all 256 bits are all set.  Used in S_cl_is_anything()  */
  392. #define ANYOF_BITMAP_TESTALLSET(p)    \
  393.     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)
  394.  
  395. #define ANYOF_SKIP        ((ANYOF_SIZE - 1)/sizeof(regnode))
  396. #define ANYOF_CLASS_SKIP    ((ANYOF_CLASS_SIZE - 1)/sizeof(regnode))
  397. #define ANYOF_CLASS_ADD_SKIP    (ANYOF_CLASS_SKIP - ANYOF_SKIP)
  398.  
  399.  
  400. /*
  401.  * Utility definitions.
  402.  */
  403. #ifndef CHARMASK
  404. #  define UCHARAT(p)    ((int)*(const U8*)(p))
  405. #else
  406. #  define UCHARAT(p)    ((int)*(p)&CHARMASK)
  407. #endif
  408.  
  409. #define EXTRA_SIZE(guy) ((sizeof(guy)-1)/sizeof(struct regnode))
  410.  
  411. #define REG_SEEN_ZERO_LEN    0x00000001
  412. #define REG_SEEN_LOOKBEHIND    0x00000002
  413. #define REG_SEEN_GPOS        0x00000004
  414. #define REG_SEEN_EVAL        0x00000008
  415. #define REG_SEEN_CANY        0x00000010
  416. #define REG_SEEN_SANY        REG_SEEN_CANY /* src bckwrd cmpt */
  417. #define REG_SEEN_RECURSE        0x00000020
  418. #define REG_TOP_LEVEL_BRANCHES  0x00000040
  419. #define REG_SEEN_VERBARG        0x00000080
  420. #define REG_SEEN_CUTGROUP       0x00000100
  421. #define REG_SEEN_RUN_ON_COMMENT 0x00000200
  422.  
  423. START_EXTERN_C
  424.  
  425. #ifdef PLUGGABLE_RE_EXTENSION
  426. #include "re_nodes.h"
  427. #else
  428. #include "regnodes.h"
  429. #endif
  430.  
  431. /* The following have no fixed length. U8 so we can do strchr() on it. */
  432. #ifndef DOINIT
  433. EXTCONST U8 PL_varies[];
  434. #else
  435. EXTCONST U8 PL_varies[] = {
  436.     BRANCH, BACK, STAR, PLUS, CURLY, CURLYX, REF, REFF, REFFL,
  437.     WHILEM, CURLYM, CURLYN, BRANCHJ, IFTHEN, SUSPEND, CLUMP,
  438.     NREF, NREFF, NREFFL,
  439.     0
  440. };
  441. #endif
  442.  
  443. /* The following always have a length of 1. U8 we can do strchr() on it. */
  444. /* (Note that length 1 means "one character" under UTF8, not "one octet".) */
  445. #ifndef DOINIT
  446. EXTCONST U8 PL_simple[];
  447. #else
  448. EXTCONST U8 PL_simple[] = {
  449.     REG_ANY,    SANY,    CANY,
  450.     ANYOF,
  451.     ALNUM,    ALNUML,
  452.     NALNUM,    NALNUML,
  453.     SPACE,    SPACEL,
  454.     NSPACE,    NSPACEL,
  455.     DIGIT,    NDIGIT,
  456.     VERTWS,     NVERTWS,
  457.     HORIZWS,    NHORIZWS,
  458.     0
  459. };
  460. #endif
  461.  
  462. #ifndef PLUGGABLE_RE_EXTENSION
  463. #ifndef DOINIT
  464. EXTCONST regexp_engine PL_core_reg_engine;
  465. #else /* DOINIT */
  466. EXTCONST regexp_engine PL_core_reg_engine = { 
  467.         Perl_re_compile,
  468.         Perl_regexec_flags,
  469.         Perl_re_intuit_start,
  470.         Perl_re_intuit_string, 
  471.         Perl_regfree_internal,
  472.         Perl_reg_numbered_buff_fetch,
  473.         Perl_reg_numbered_buff_store,
  474.         Perl_reg_numbered_buff_length,
  475.         Perl_reg_named_buff,
  476.         Perl_reg_named_buff_iter,
  477.         Perl_reg_qr_package,
  478. #if defined(USE_ITHREADS)        
  479.         Perl_regdupe_internal
  480. #endif        
  481. };
  482. #endif /* DOINIT */
  483. #endif /* PLUGGABLE_RE_EXTENSION */
  484.  
  485.  
  486. END_EXTERN_C
  487.  
  488.  
  489. /* .what is a character array with one character for each member of .data
  490.  * The character describes the function of the corresponding .data item:
  491.  *   f - start-class data for regstclass optimization
  492.  *   n - Root of op tree for (?{EVAL}) item
  493.  *   o - Start op for (?{EVAL}) item
  494.  *   p - Pad for (?{EVAL}) item
  495.  *   s - swash for Unicode-style character class, and the multicharacter
  496.  *       strings resulting from casefolding the single-character entries
  497.  *       in the character class
  498.  *   t - trie struct
  499.  *   u - trie struct's widecharmap (a HV, so can't share, must dup)
  500.  *       also used for revcharmap and words under DEBUGGING
  501.  *   T - aho-trie struct
  502.  *   S - sv for named capture lookup
  503.  * 20010712 mjd@plover.com
  504.  * (Remember to update re_dup() and pregfree() if you add any items.)
  505.  */
  506. struct reg_data {
  507.     U32 count;
  508.     U8 *what;
  509.     void* data[1];
  510. };
  511.  
  512. /* Code in S_to_utf8_substr() and S_to_byte_substr() in regexec.c accesses
  513.    anchored* and float* via array indexes 0 and 1.  */
  514. #define anchored_substr substrs->data[0].substr
  515. #define anchored_utf8 substrs->data[0].utf8_substr
  516. #define anchored_offset substrs->data[0].min_offset
  517. #define anchored_end_shift substrs->data[0].end_shift
  518.  
  519. #define float_substr substrs->data[1].substr
  520. #define float_utf8 substrs->data[1].utf8_substr
  521. #define float_min_offset substrs->data[1].min_offset
  522. #define float_max_offset substrs->data[1].max_offset
  523. #define float_end_shift substrs->data[1].end_shift
  524.  
  525. #define check_substr substrs->data[2].substr
  526. #define check_utf8 substrs->data[2].utf8_substr
  527. #define check_offset_min substrs->data[2].min_offset
  528. #define check_offset_max substrs->data[2].max_offset
  529. #define check_end_shift substrs->data[2].end_shift
  530.  
  531.  
  532.  
  533. /* trie related stuff */
  534.  
  535. /* a transition record for the state machine. the
  536.    check field determines which state "owns" the
  537.    transition. the char the transition is for is
  538.    determined by offset from the owning states base
  539.    field.  the next field determines which state
  540.    is to be transitioned to if any.
  541. */
  542. struct _reg_trie_trans {
  543.   U32 next;
  544.   U32 check;
  545. };
  546.  
  547. /* a transition list element for the list based representation */
  548. struct _reg_trie_trans_list_elem {
  549.     U16 forid;
  550.     U32 newstate;
  551. };
  552. typedef struct _reg_trie_trans_list_elem reg_trie_trans_le;
  553.  
  554. /* a state for compressed nodes. base is an offset
  555.   into an array of reg_trie_trans array. If wordnum is
  556.   nonzero the state is accepting. if base is zero then
  557.   the state has no children (and will be accepting)
  558. */
  559. struct _reg_trie_state {
  560.   U16 wordnum;
  561.   union {
  562.     U32                base;
  563.     reg_trie_trans_le* list;
  564.   } trans;
  565. };
  566.  
  567.  
  568.  
  569. typedef struct _reg_trie_state    reg_trie_state;
  570. typedef struct _reg_trie_trans    reg_trie_trans;
  571.  
  572.  
  573. /* anything in here that needs to be freed later
  574.    should be dealt with in pregfree.
  575.    refcount is first in both this and _reg_ac_data to allow a space
  576.    optimisation in Perl_regdupe.  */
  577. struct _reg_trie_data {
  578.     U32             refcount;        /* number of times this trie is referenced */
  579.     U32             lasttrans;       /* last valid transition element */
  580.     U16             *charmap;        /* byte to charid lookup array */
  581.     reg_trie_state  *states;         /* state data */
  582.     reg_trie_trans  *trans;          /* array of transition elements */
  583.     char            *bitmap;         /* stclass bitmap */
  584.     U32             *wordlen;        /* array of lengths of words */
  585.     U16         *jump;           /* optional 1 indexed array of offsets before tail 
  586.                                         for the node following a given word. */
  587.     U16                *nextword;       /* optional 1 indexed array to support linked list
  588.                                         of duplicate wordnums */
  589.     U16             uniquecharcount; /* unique chars in trie (width of trans table) */
  590.     U32             startstate;      /* initial state - used for common prefix optimisation */
  591.     STRLEN          minlen;          /* minimum length of words in trie - build/opt only? */
  592.     STRLEN          maxlen;          /* maximum length of words in trie - build/opt only? */
  593.     U32             statecount;      /* Build only - number of states in the states array 
  594.                                         (including the unused zero state) */
  595.     U32             wordcount;       /* Build only */
  596. #ifdef DEBUGGING
  597.     STRLEN          charcount;       /* Build only */
  598. #endif
  599. };
  600. /* There is one (3 under DEBUGGING) pointers that logically belong in this
  601.    structure, but are held outside as they need duplication on thread cloning,
  602.    whereas the rest of the structure can be read only:
  603.     HV              *widecharmap;    code points > 255 to charid
  604. #ifdef DEBUGGING
  605.     AV              *words;          Array of words contained in trie, for dumping
  606.     AV              *revcharmap;     Map of each charid back to its character representation
  607. #endif
  608. */
  609.  
  610. #define TRIE_WORDS_OFFSET 2
  611.  
  612. typedef struct _reg_trie_data reg_trie_data;
  613.  
  614. /* refcount is first in both this and _reg_trie_data to allow a space
  615.    optimisation in Perl_regdupe.  */
  616. struct _reg_ac_data {
  617.     U32              refcount;
  618.     U32              trie;
  619.     U32              *fail;
  620.     reg_trie_state   *states;
  621. };
  622. typedef struct _reg_ac_data reg_ac_data;
  623.  
  624. /* ANY_BIT doesnt use the structure, so we can borrow it here.
  625.    This is simpler than refactoring all of it as wed end up with
  626.    three different sets... */
  627.  
  628. #define TRIE_BITMAP(p)        (((reg_trie_data *)(p))->bitmap)
  629. #define TRIE_BITMAP_BYTE(p, c)    (TRIE_BITMAP(p)[(((U8)(c)) >> 3) & 31])
  630. #define TRIE_BITMAP_SET(p, c)    (TRIE_BITMAP_BYTE(p, c) |=  ANYOF_BIT((U8)c))
  631. #define TRIE_BITMAP_CLEAR(p,c)    (TRIE_BITMAP_BYTE(p, c) &= ~ANYOF_BIT((U8)c))
  632. #define TRIE_BITMAP_TEST(p, c)    (TRIE_BITMAP_BYTE(p, c) &   ANYOF_BIT((U8)c))
  633.  
  634. #define IS_ANYOF_TRIE(op) ((op)==TRIEC || (op)==AHOCORASICKC)
  635. #define IS_TRIE_AC(op) ((op)>=AHOCORASICK)
  636.  
  637.  
  638. #define BITMAP_BYTE(p, c)    (((U8*)p)[(((U8)(c)) >> 3) & 31])
  639. #define BITMAP_TEST(p, c)    (BITMAP_BYTE(p, c) &   ANYOF_BIT((U8)c))
  640.  
  641. /* these defines assume uniquecharcount is the correct variable, and state may be evaluated twice */
  642. #define TRIE_NODENUM(state) (((state)-1)/(trie->uniquecharcount)+1)
  643. #define SAFE_TRIE_NODENUM(state) ((state) ? (((state)-1)/(trie->uniquecharcount)+1) : (state))
  644. #define TRIE_NODEIDX(state) ((state) ? (((state)-1)*(trie->uniquecharcount)+1) : (state))
  645.  
  646. #ifdef DEBUGGING
  647. #define TRIE_CHARCOUNT(trie) ((trie)->charcount)
  648. #else
  649. #define TRIE_CHARCOUNT(trie) (trie_charcount)
  650. #endif
  651.  
  652. #define RE_TRIE_MAXBUF_INIT 65536
  653. #define RE_TRIE_MAXBUF_NAME "\022E_TRIE_MAXBUF"
  654. #define RE_DEBUG_FLAGS "\022E_DEBUG_FLAGS"
  655.  
  656. /*
  657.  
  658. RE_DEBUG_FLAGS is used to control what debug output is emitted
  659. its divided into three groups of options, some of which interact.
  660. The three groups are: Compile, Execute, Extra. There is room for a
  661. further group, as currently only the low three bytes are used.
  662.  
  663.     Compile Options:
  664.     
  665.     PARSE
  666.     PEEP
  667.     TRIE
  668.     PROGRAM
  669.     OFFSETS
  670.  
  671.     Execute Options:
  672.  
  673.     INTUIT
  674.     MATCH
  675.     TRIE
  676.  
  677.     Extra Options
  678.  
  679.     TRIE
  680.     OFFSETS
  681.  
  682. If you modify any of these make sure you make corresponding changes to
  683. re.pm, especially to the documentation.
  684.  
  685. */
  686.  
  687.  
  688. /* Compile */
  689. #define RE_DEBUG_COMPILE_MASK      0x0000FF
  690. #define RE_DEBUG_COMPILE_PARSE     0x000001
  691. #define RE_DEBUG_COMPILE_OPTIMISE  0x000002
  692. #define RE_DEBUG_COMPILE_TRIE      0x000004
  693. #define RE_DEBUG_COMPILE_DUMP      0x000008
  694. #define RE_DEBUG_COMPILE_FLAGS     0x000010
  695.  
  696. /* Execute */
  697. #define RE_DEBUG_EXECUTE_MASK      0x00FF00
  698. #define RE_DEBUG_EXECUTE_INTUIT    0x000100
  699. #define RE_DEBUG_EXECUTE_MATCH     0x000200
  700. #define RE_DEBUG_EXECUTE_TRIE      0x000400
  701.  
  702. /* Extra */
  703. #define RE_DEBUG_EXTRA_MASK        0xFF0000
  704. #define RE_DEBUG_EXTRA_TRIE        0x010000
  705. #define RE_DEBUG_EXTRA_OFFSETS     0x020000
  706. #define RE_DEBUG_EXTRA_OFFDEBUG    0x040000
  707. #define RE_DEBUG_EXTRA_STATE       0x080000
  708. #define RE_DEBUG_EXTRA_OPTIMISE    0x100000
  709. #define RE_DEBUG_EXTRA_BUFFERS     0x400000
  710. /* combined */
  711. #define RE_DEBUG_EXTRA_STACK       0x280000
  712.  
  713. #define RE_DEBUG_FLAG(x) (re_debug_flags & x)
  714. /* Compile */
  715. #define DEBUG_COMPILE_r(x) DEBUG_r( \
  716.     if (re_debug_flags & RE_DEBUG_COMPILE_MASK) x  )
  717. #define DEBUG_PARSE_r(x) DEBUG_r( \
  718.     if (re_debug_flags & RE_DEBUG_COMPILE_PARSE) x  )
  719. #define DEBUG_OPTIMISE_r(x) DEBUG_r( \
  720.     if (re_debug_flags & RE_DEBUG_COMPILE_OPTIMISE) x  )
  721. #define DEBUG_PARSE_r(x) DEBUG_r( \
  722.     if (re_debug_flags & RE_DEBUG_COMPILE_PARSE) x  )
  723. #define DEBUG_DUMP_r(x) DEBUG_r( \
  724.     if (re_debug_flags & RE_DEBUG_COMPILE_DUMP) x  )
  725. #define DEBUG_TRIE_COMPILE_r(x) DEBUG_r( \
  726.     if (re_debug_flags & RE_DEBUG_COMPILE_TRIE) x )
  727. #define DEBUG_FLAGS_r(x) DEBUG_r( \
  728.     if (re_debug_flags & RE_DEBUG_COMPILE_FLAGS) x )
  729. /* Execute */
  730. #define DEBUG_EXECUTE_r(x) DEBUG_r( \
  731.     if (re_debug_flags & RE_DEBUG_EXECUTE_MASK) x  )
  732. #define DEBUG_INTUIT_r(x) DEBUG_r( \
  733.     if (re_debug_flags & RE_DEBUG_EXECUTE_INTUIT) x  )
  734. #define DEBUG_MATCH_r(x) DEBUG_r( \
  735.     if (re_debug_flags & RE_DEBUG_EXECUTE_MATCH) x  )
  736. #define DEBUG_TRIE_EXECUTE_r(x) DEBUG_r( \
  737.     if (re_debug_flags & RE_DEBUG_EXECUTE_TRIE) x )
  738.  
  739. /* Extra */
  740. #define DEBUG_EXTRA_r(x) DEBUG_r( \
  741.     if (re_debug_flags & RE_DEBUG_EXTRA_MASK) x  )
  742. #define DEBUG_OFFSETS_r(x) DEBUG_r( \
  743.     if (re_debug_flags & RE_DEBUG_EXTRA_OFFSETS) x  )
  744. #define DEBUG_STATE_r(x) DEBUG_r( \
  745.     if (re_debug_flags & RE_DEBUG_EXTRA_STATE) x )
  746. #define DEBUG_STACK_r(x) DEBUG_r( \
  747.     if (re_debug_flags & RE_DEBUG_EXTRA_STACK) x )
  748. #define DEBUG_BUFFERS_r(x) DEBUG_r( \
  749.     if (re_debug_flags & RE_DEBUG_EXTRA_BUFFERS) x )
  750.  
  751. #define DEBUG_OPTIMISE_MORE_r(x) DEBUG_r( \
  752.     if ((RE_DEBUG_EXTRA_OPTIMISE|RE_DEBUG_COMPILE_OPTIMISE) == \
  753.          (re_debug_flags & (RE_DEBUG_EXTRA_OPTIMISE|RE_DEBUG_COMPILE_OPTIMISE)) ) x )
  754. #define MJD_OFFSET_DEBUG(x) DEBUG_r( \
  755.     if (re_debug_flags & RE_DEBUG_EXTRA_OFFDEBUG) \
  756.         Perl_warn_nocontext x )
  757. #define DEBUG_TRIE_COMPILE_MORE_r(x) DEBUG_TRIE_COMPILE_r( \
  758.     if (re_debug_flags & RE_DEBUG_EXTRA_TRIE) x )
  759. #define DEBUG_TRIE_EXECUTE_MORE_r(x) DEBUG_TRIE_EXECUTE_r( \
  760.     if (re_debug_flags & RE_DEBUG_EXTRA_TRIE) x )
  761.  
  762. #define DEBUG_TRIE_r(x) DEBUG_r( \
  763.     if (re_debug_flags & (RE_DEBUG_COMPILE_TRIE \
  764.         | RE_DEBUG_EXECUTE_TRIE )) x )
  765.  
  766. /* initialization */
  767. /* get_sv() can return NULL during global destruction. */
  768. #define GET_RE_DEBUG_FLAGS DEBUG_r({ \
  769.         SV * re_debug_flags_sv = NULL; \
  770.         re_debug_flags_sv = get_sv(RE_DEBUG_FLAGS, 1); \
  771.         if (re_debug_flags_sv) { \
  772.             if (!SvIOK(re_debug_flags_sv)) \
  773.                 sv_setuv(re_debug_flags_sv, RE_DEBUG_COMPILE_DUMP | RE_DEBUG_EXECUTE_MASK ); \
  774.             re_debug_flags=SvIV(re_debug_flags_sv); \
  775.         }\
  776. })
  777.  
  778. #ifdef DEBUGGING
  779.  
  780. #define GET_RE_DEBUG_FLAGS_DECL IV re_debug_flags = 0; GET_RE_DEBUG_FLAGS;
  781.  
  782. #define RE_PV_COLOR_DECL(rpv,rlen,isuni,dsv,pv,l,m,c1,c2) \
  783.     const char * const rpv =                          \
  784.         pv_pretty((dsv), (pv), (l), (m), \
  785.             PL_colors[(c1)],PL_colors[(c2)], \
  786.             PERL_PV_ESCAPE_RE |((isuni) ? PERL_PV_ESCAPE_UNI : 0) );         \
  787.     const int rlen = SvCUR(dsv)
  788.  
  789. #define RE_SV_ESCAPE(rpv,isuni,dsv,sv,m) \
  790.     const char * const rpv =                          \
  791.         pv_pretty((dsv), (SvPV_nolen_const(sv)), (SvCUR(sv)), (m), \
  792.             PL_colors[(c1)],PL_colors[(c2)], \
  793.             PERL_PV_ESCAPE_RE |((isuni) ? PERL_PV_ESCAPE_UNI : 0) )
  794.  
  795. #define RE_PV_QUOTED_DECL(rpv,isuni,dsv,pv,l,m)                    \
  796.     const char * const rpv =                                       \
  797.         pv_pretty((dsv), (pv), (l), (m), \
  798.             PL_colors[0], PL_colors[1], \
  799.             ( PERL_PV_PRETTY_QUOTE | PERL_PV_ESCAPE_RE | PERL_PV_PRETTY_ELLIPSES | \
  800.               ((isuni) ? PERL_PV_ESCAPE_UNI : 0))                  \
  801.         )
  802.  
  803. #define RE_SV_DUMPLEN(ItEm) (SvCUR(ItEm) - (SvTAIL(ItEm)!=0))
  804. #define RE_SV_TAIL(ItEm) (SvTAIL(ItEm) ? "$" : "")
  805.     
  806. #else /* if not DEBUGGING */
  807.  
  808. #define GET_RE_DEBUG_FLAGS_DECL
  809. #define RE_PV_COLOR_DECL(rpv,rlen,isuni,dsv,pv,l,m,c1,c2)
  810. #define RE_SV_ESCAPE(rpv,isuni,dsv,sv,m)
  811. #define RE_PV_QUOTED_DECL(rpv,isuni,dsv,pv,l,m)
  812. #define RE_SV_DUMPLEN(ItEm)
  813. #define RE_SV_TAIL(ItEm)
  814.  
  815. #endif /* DEBUG RELATED DEFINES */
  816.  
  817.  
  818.  
  819.