home *** CD-ROM | disk | FTP | other *** search
/ PC World 2005 December (Special) / PCWorld_2005-12_Special_cd.bin / Bezpecnost / lsti / lsti.exe / framework-2.5.exe / regcomp.h < prev    next >
C/C++ Source or Header  |  2005-01-27  |  14KB  |  409 lines
  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:
  57.  */
  58.  
  59. /*
  60.  * A node is one char of opcode followed by two chars of "next" pointer.
  61.  * "Next" pointers are stored as two 8-bit pieces, high order first.  The
  62.  * value is a positive offset from the opcode of the node containing it.
  63.  * An operand, if any, simply follows the node.  (Note that much of the
  64.  * code generation knows about this implicit relationship.)
  65.  *
  66.  * Using two bytes for the "next" pointer is vast overkill for most things,
  67.  * but allows patterns to get big without disasters.
  68.  *
  69.  * [The "next" pointer is always aligned on an even
  70.  * boundary, and reads the offset directly as a short.  Also, there is no
  71.  * special test to reverse the sign of BACK pointers since the offset is
  72.  * stored negative.]
  73.  */
  74.  
  75. struct regnode_string {
  76.     U8    str_len;
  77.     U8  type;
  78.     U16 next_off;
  79.     char string[1];
  80. };
  81.  
  82. struct regnode_1 {
  83.     U8    flags;
  84.     U8  type;
  85.     U16 next_off;
  86.     U32 arg1;
  87. };
  88.  
  89. struct regnode_2 {
  90.     U8    flags;
  91.     U8  type;
  92.     U16 next_off;
  93.     U16 arg1;
  94.     U16 arg2;
  95. };
  96.  
  97. #define ANYOF_BITMAP_SIZE    32    /* 256 b/(8 b/B) */
  98. #define ANYOF_CLASSBITMAP_SIZE     4    /* up to 32 (8*4) named classes */
  99.  
  100. struct regnode_charclass {
  101.     U8    flags;
  102.     U8  type;
  103.     U16 next_off;
  104.     U32 arg1;
  105.     char bitmap[ANYOF_BITMAP_SIZE];    /* only compile-time */
  106. };
  107.  
  108. struct regnode_charclass_class {    /* has [[:blah:]] classes */
  109.     U8    flags;                /* should have ANYOF_CLASS here */
  110.     U8  type;
  111.     U16 next_off;
  112.     U32 arg1;
  113.     char bitmap[ANYOF_BITMAP_SIZE];        /* both compile-time */
  114.     char classflags[ANYOF_CLASSBITMAP_SIZE];    /* and run-time */
  115. };
  116.  
  117. /* XXX fix this description.
  118.    Impose a limit of REG_INFTY on various pattern matching operations
  119.    to limit stack growth and to avoid "infinite" recursions.
  120. */
  121. /* The default size for REG_INFTY is I16_MAX, which is the same as
  122.    SHORT_MAX (see perl.h).  Unfortunately I16 isn't necessarily 16 bits
  123.    (see handy.h).  On the Cray C90, sizeof(short)==4 and hence I16_MAX is
  124.    ((1<<31)-1), while on the Cray T90, sizeof(short)==8 and I16_MAX is
  125.    ((1<<63)-1).  To limit stack growth to reasonable sizes, supply a
  126.    smaller default.
  127.     --Andy Dougherty  11 June 1998
  128. */
  129. #if SHORTSIZE > 2
  130. #  ifndef REG_INFTY
  131. #    define REG_INFTY ((1<<15)-1)
  132. #  endif
  133. #endif
  134.  
  135. #ifndef REG_INFTY
  136. #  define REG_INFTY I16_MAX
  137. #endif
  138.  
  139. #define ARG_VALUE(arg) (arg)
  140. #define ARG__SET(arg,val) ((arg) = (val))
  141.  
  142. #undef ARG
  143. #undef ARG1
  144. #undef ARG2
  145.  
  146. #define ARG(p) ARG_VALUE(ARG_LOC(p))
  147. #define ARG1(p) ARG_VALUE(ARG1_LOC(p))
  148. #define ARG2(p) ARG_VALUE(ARG2_LOC(p))
  149. #define ARG_SET(p, val) ARG__SET(ARG_LOC(p), (val))
  150. #define ARG1_SET(p, val) ARG__SET(ARG1_LOC(p), (val))
  151. #define ARG2_SET(p, val) ARG__SET(ARG2_LOC(p), (val))
  152.  
  153. #undef NEXT_OFF
  154. #undef NODE_ALIGN
  155.  
  156. #ifndef lint
  157. #  define NEXT_OFF(p) ((p)->next_off)
  158. #  define NODE_ALIGN(node)
  159. #  define NODE_ALIGN_FILL(node) ((node)->flags = 0xde) /* deadbeef */
  160. #else /* lint */
  161. #  define NEXT_OFF(p) 0
  162. #  define NODE_ALIGN(node)
  163. #  define NODE_ALIGN_FILL(node)
  164. #endif /* lint */
  165.  
  166. #define SIZE_ALIGN NODE_ALIGN
  167.  
  168. #undef OP
  169. #undef OPERAND
  170. #undef MASK
  171. #undef STRING
  172.  
  173. #define    OP(p)        ((p)->type)
  174. #define    OPERAND(p)    (((struct regnode_string *)p)->string)
  175. #define MASK(p)        ((char*)OPERAND(p))
  176. #define    STR_LEN(p)    (((struct regnode_string *)p)->str_len)
  177. #define    STRING(p)    (((struct regnode_string *)p)->string)
  178. #define STR_SZ(l)    ((l + sizeof(regnode) - 1) / sizeof(regnode))
  179. #define NODE_SZ_STR(p)    (STR_SZ(STR_LEN(p))+1)
  180.  
  181. #undef NODE_ALIGN
  182. #undef ARG_LOC
  183. #undef NEXTOPER
  184. #undef PREVOPER
  185.  
  186. #define    NODE_ALIGN(node)
  187. #define    ARG_LOC(p)    (((struct regnode_1 *)p)->arg1)
  188. #define    ARG1_LOC(p)    (((struct regnode_2 *)p)->arg1)
  189. #define    ARG2_LOC(p)    (((struct regnode_2 *)p)->arg2)
  190. #define NODE_STEP_REGNODE    1    /* sizeof(regnode)/sizeof(regnode) */
  191. #define EXTRA_STEP_2ARGS    EXTRA_SIZE(struct regnode_2)
  192.  
  193. #define NODE_STEP_B    4
  194.  
  195. #define    NEXTOPER(p)    ((p) + NODE_STEP_REGNODE)
  196. #define    PREVOPER(p)    ((p) - NODE_STEP_REGNODE)
  197.  
  198. #define FILL_ADVANCE_NODE(ptr, op) STMT_START { \
  199.     (ptr)->type = op;    (ptr)->next_off = 0;   (ptr)++; } STMT_END
  200. #define FILL_ADVANCE_NODE_ARG(ptr, op, arg) STMT_START { \
  201.     ARG_SET(ptr, arg);  FILL_ADVANCE_NODE(ptr, op); (ptr) += 1; } STMT_END
  202.  
  203. #define REG_MAGIC 0234
  204.  
  205. #define SIZE_ONLY (RExC_emit == &PL_regdummy)
  206.  
  207. /* Flags for node->flags of ANYOF */
  208.  
  209. #define ANYOF_CLASS        0x08    /* has [[:blah:]] classes */
  210. #define ANYOF_INVERT        0x04
  211. #define ANYOF_FOLD        0x02
  212. #define ANYOF_LOCALE        0x01
  213.  
  214. /* Used for regstclass only */
  215. #define ANYOF_EOS        0x10        /* Can match an empty string too */
  216.  
  217. /* There is a character or a range past 0xff */
  218. #define ANYOF_UNICODE        0x20
  219. #define ANYOF_UNICODE_ALL    0x40    /* Can match any char past 0xff */
  220.  
  221. /* size of node is large (includes class pointer) */
  222. #define ANYOF_LARGE         0x80
  223.  
  224. /* Are there any runtime flags on in this node? */
  225. #define ANYOF_RUNTIME(s)    (ANYOF_FLAGS(s) & 0x0f)
  226.  
  227. #define ANYOF_FLAGS_ALL        0xff
  228.  
  229. /* Character classes for node->classflags of ANYOF */
  230. /* Should be synchronized with a table in regprop() */
  231. /* 2n should pair with 2n+1 */
  232.  
  233. #define ANYOF_ALNUM     0    /* \w, PL_utf8_alnum, utf8::IsWord, ALNUM */
  234. #define ANYOF_NALNUM     1
  235. #define ANYOF_SPACE     2    /* \s */
  236. #define ANYOF_NSPACE     3
  237. #define ANYOF_DIGIT     4
  238. #define ANYOF_NDIGIT     5
  239. #define ANYOF_ALNUMC     6    /* isalnum(3), utf8::IsAlnum, ALNUMC */
  240. #define ANYOF_NALNUMC     7
  241. #define ANYOF_ALPHA     8
  242. #define ANYOF_NALPHA     9
  243. #define ANYOF_ASCII    10
  244. #define ANYOF_NASCII    11
  245. #define ANYOF_CNTRL    12
  246. #define ANYOF_NCNTRL    13
  247. #define ANYOF_GRAPH    14
  248. #define ANYOF_NGRAPH    15
  249. #define ANYOF_LOWER    16
  250. #define ANYOF_NLOWER    17
  251. #define ANYOF_PRINT    18
  252. #define ANYOF_NPRINT    19
  253. #define ANYOF_PUNCT    20
  254. #define ANYOF_NPUNCT    21
  255. #define ANYOF_UPPER    22
  256. #define ANYOF_NUPPER    23
  257. #define ANYOF_XDIGIT    24
  258. #define ANYOF_NXDIGIT    25
  259. #define ANYOF_PSXSPC    26    /* POSIX space: \s plus the vertical tab */
  260. #define ANYOF_NPSXSPC    27
  261. #define ANYOF_BLANK    28    /* GNU extension: space and tab: non-vertical space */
  262. #define ANYOF_NBLANK    29
  263.  
  264. #define ANYOF_MAX    32
  265.  
  266. /* Backward source code compatibility. */
  267.  
  268. #define ANYOF_ALNUML     ANYOF_ALNUM
  269. #define ANYOF_NALNUML     ANYOF_NALNUM
  270. #define ANYOF_SPACEL     ANYOF_SPACE
  271. #define ANYOF_NSPACEL     ANYOF_NSPACE
  272.  
  273. /* Utility macros for the bitmap and classes of ANYOF */
  274.  
  275. #define ANYOF_SIZE        (sizeof(struct regnode_charclass))
  276. #define ANYOF_CLASS_SIZE    (sizeof(struct regnode_charclass_class))
  277.  
  278. #define ANYOF_FLAGS(p)        ((p)->flags)
  279.  
  280. #define ANYOF_BIT(c)        (1 << ((c) & 7))
  281.  
  282. #define ANYOF_CLASS_BYTE(p, c)    (((struct regnode_charclass_class*)(p))->classflags[((c) >> 3) & 3])
  283. #define ANYOF_CLASS_SET(p, c)    (ANYOF_CLASS_BYTE(p, c) |=  ANYOF_BIT(c))
  284. #define ANYOF_CLASS_CLEAR(p, c)    (ANYOF_CLASS_BYTE(p, c) &= ~ANYOF_BIT(c))
  285. #define ANYOF_CLASS_TEST(p, c)    (ANYOF_CLASS_BYTE(p, c) &   ANYOF_BIT(c))
  286.  
  287. #define ANYOF_CLASS_ZERO(ret)    Zero(((struct regnode_charclass_class*)(ret))->classflags, ANYOF_CLASSBITMAP_SIZE, char)
  288. #define ANYOF_BITMAP_ZERO(ret)    Zero(((struct regnode_charclass*)(ret))->bitmap, ANYOF_BITMAP_SIZE, char)
  289.  
  290. #define ANYOF_BITMAP(p)        (((struct regnode_charclass*)(p))->bitmap)
  291. #define ANYOF_BITMAP_BYTE(p, c)    (ANYOF_BITMAP(p)[((c) >> 3) & 31])
  292. #define ANYOF_BITMAP_SET(p, c)    (ANYOF_BITMAP_BYTE(p, c) |=  ANYOF_BIT(c))
  293. #define ANYOF_BITMAP_CLEAR(p,c)    (ANYOF_BITMAP_BYTE(p, c) &= ~ANYOF_BIT(c))
  294. #define ANYOF_BITMAP_TEST(p, c)    (ANYOF_BITMAP_BYTE(p, c) &   ANYOF_BIT(c))
  295.  
  296. #define ANYOF_BITMAP_SETALL(p)        \
  297.     memset (ANYOF_BITMAP(p), 255, ANYOF_BITMAP_SIZE)
  298. #define ANYOF_BITMAP_CLEARALL(p)    \
  299.     Zero (ANYOF_BITMAP(p), ANYOF_BITMAP_SIZE)
  300. /* Check that all 256 bits are all set.  Used in S_cl_is_anything()  */
  301. #define ANYOF_BITMAP_TESTALLSET(p)    \
  302.     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)
  303.  
  304. #define ANYOF_SKIP        ((ANYOF_SIZE - 1)/sizeof(regnode))
  305. #define ANYOF_CLASS_SKIP    ((ANYOF_CLASS_SIZE - 1)/sizeof(regnode))
  306. #define ANYOF_CLASS_ADD_SKIP    (ANYOF_CLASS_SKIP - ANYOF_SKIP)
  307.  
  308. /*
  309.  * Utility definitions.
  310.  */
  311. #ifndef lint
  312. #ifndef CHARMASK
  313. #define    UCHARAT(p)    ((int)*(U8*)(p))
  314. #else
  315. #define    UCHARAT(p)    ((int)*(p)&CHARMASK)
  316. #endif
  317. #else /* lint */
  318. #define UCHARAT(p)    PL_regdummy
  319. #endif /* lint */
  320.  
  321. #define EXTRA_SIZE(guy) ((sizeof(guy)-1)/sizeof(struct regnode))
  322.  
  323. #define REG_SEEN_ZERO_LEN     1
  324. #define REG_SEEN_LOOKBEHIND     2
  325. #define REG_SEEN_GPOS         4
  326. #define REG_SEEN_EVAL         8
  327. #define REG_SEEN_CANY        16
  328. #define REG_SEEN_SANY        REG_SEEN_CANY /* src bckwrd cmpt */
  329.  
  330. START_EXTERN_C
  331.  
  332. #include "regnodes.h"
  333.  
  334. /* The following have no fixed length. U8 so we can do strchr() on it. */
  335. #ifndef DOINIT
  336. EXTCONST U8 PL_varies[];
  337. #else
  338. EXTCONST U8 PL_varies[] = {
  339.     BRANCH, BACK, STAR, PLUS, CURLY, CURLYX, REF, REFF, REFFL, 
  340.     WHILEM, CURLYM, CURLYN, BRANCHJ, IFTHEN, SUSPEND, CLUMP, 0
  341. };
  342. #endif
  343.  
  344. /* The following always have a length of 1. U8 we can do strchr() on it. */
  345. /* (Note that length 1 means "one character" under UTF8, not "one octet".) */
  346. #ifndef DOINIT
  347. EXTCONST U8 PL_simple[];
  348. #else
  349. EXTCONST U8 PL_simple[] = {
  350.     REG_ANY,    SANY,    CANY,
  351.     ANYOF,
  352.     ALNUM,    ALNUML,
  353.     NALNUM,    NALNUML,
  354.     SPACE,    SPACEL,
  355.     NSPACE,    NSPACEL,
  356.     DIGIT,    NDIGIT,
  357.     0
  358. };
  359. #endif
  360.  
  361. END_EXTERN_C
  362.  
  363. typedef struct re_scream_pos_data_s
  364. {
  365.     char **scream_olds;        /* match pos */
  366.     I32 *scream_pos;        /* Internal iterator of scream. */
  367. } re_scream_pos_data;
  368.  
  369. /* .what is a character array with one character for each member of .data
  370.  * The character describes the function of the corresponding .data item:
  371.  *   f - start-class data for regstclass optimization  
  372.  *   n - Root of op tree for (?{EVAL}) item
  373.  *   o - Start op for (?{EVAL}) item
  374.  *   p - Pad for (?{EVAL} item
  375.  *   s - swash for unicode-style character class, and the multicharacter
  376.  *       strings resulting from casefolding the single-character entries
  377.  *       in the character class
  378.  * 20010712 mjd@plover.com
  379.  * (Remember to update re_dup() and pregfree() if you add any items.)
  380.  */
  381. struct reg_data {
  382.     U32 count;
  383.     U8 *what;
  384.     void* data[1];
  385. };
  386.  
  387. struct reg_substr_datum {
  388.     I32 min_offset;
  389.     I32 max_offset;
  390.     SV *substr;        /* non-utf8 variant */
  391.     SV *utf8_substr;    /* utf8 variant */
  392. };
  393.  
  394. struct reg_substr_data {
  395.     struct reg_substr_datum data[3];    /* Actual array */
  396. };
  397.  
  398. #define anchored_substr substrs->data[0].substr
  399. #define anchored_utf8 substrs->data[0].utf8_substr
  400. #define anchored_offset substrs->data[0].min_offset
  401. #define float_substr substrs->data[1].substr
  402. #define float_utf8 substrs->data[1].utf8_substr
  403. #define float_min_offset substrs->data[1].min_offset
  404. #define float_max_offset substrs->data[1].max_offset
  405. #define check_substr substrs->data[2].substr
  406. #define check_utf8 substrs->data[2].utf8_substr
  407. #define check_offset_min substrs->data[2].min_offset
  408. #define check_offset_max substrs->data[2].max_offset
  409.