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