home *** CD-ROM | disk | FTP | other *** search
/ CD Actual Thematic 7: Programming / CDAT7.iso / Share / Editores / Perl5 / perl / lib / CORE / regcomp.h < prev    next >
Encoding:
C/C++ Source or Header  |  1997-08-10  |  9.0 KB  |  282 lines
  1. /*    regcomp.h
  2.  */
  3.  
  4. /*
  5.  * The "internal use only" fields in regexp.h are present to pass info from
  6.  * compile to execute that permits the execute phase to run lots faster on
  7.  * simple cases.  They are:
  8.  *
  9.  * regstart    sv that must begin a match; Nullch if none obvious
  10.  * reganch    is the match anchored (at beginning-of-line only)?
  11.  * regmust    string (pointer into program) that match must include, or NULL
  12.  *  [regmust changed to SV* for bminstr()--law]
  13.  * regmlen    length of regmust string
  14.  *  [regmlen not used currently]
  15.  *
  16.  * Regstart and reganch permit very fast decisions on suitable starting points
  17.  * for a match, cutting down the work a lot.  Regmust permits fast rejection
  18.  * of lines that cannot possibly match.  The regmust tests are costly enough
  19.  * that pregcomp() supplies a regmust only if the r.e. contains something
  20.  * potentially expensive (at present, the only such thing detected is * or +
  21.  * at the start of the r.e., which can involve a lot of backup).  Regmlen is
  22.  * supplied because the test in pregexec() needs it and pregcomp() is computing
  23.  * it anyway.
  24.  * [regmust is now supplied always.  The tests that use regmust have a
  25.  * heuristic that disables the test if it usually matches.]
  26.  *
  27.  * [In fact, we now use regmust in many cases to locate where the search
  28.  * starts in the string, so if regback is >= 0, the regmust search is never
  29.  * wasted effort.  The regback variable says how many characters back from
  30.  * where regmust matched is the earliest possible start of the match.
  31.  * For instance, /[a-z].foo/ has a regmust of 'foo' and a regback of 2.]
  32.  */
  33.  
  34. /*
  35.  * Structure for regexp "program".  This is essentially a linear encoding
  36.  * of a nondeterministic finite-state machine (aka syntax charts or
  37.  * "railroad normal form" in parsing technology).  Each node is an opcode
  38.  * plus a "next" pointer, possibly plus an operand.  "Next" pointers of
  39.  * all nodes except BRANCH implement concatenation; a "next" pointer with
  40.  * a BRANCH on both ends of it is connecting two alternatives.  (Here we
  41.  * have one of the subtle syntax dependencies:  an individual BRANCH (as
  42.  * opposed to a collection of them) is never concatenated with anything
  43.  * because of operator precedence.)  The operand of some types of node is
  44.  * a literal string; for others, it is a node leading into a sub-FSM.  In
  45.  * particular, the operand of a BRANCH node is the first node of the branch.
  46.  * (NB this is *not* a tree structure:  the tail of the branch connects
  47.  * to the thing following the set of BRANCHes.)  The opcodes are:
  48.  */
  49.  
  50. /* definition    number    opnd?    meaning */
  51. #define    END     0    /* no    End of program. */
  52. #define    BOL     1    /* no    Match "" at beginning of line. */
  53. #define MBOL     2    /* no    Same, assuming multiline. */
  54. #define SBOL     3    /* no    Same, assuming singleline. */
  55. #define    EOL     4    /* no    Match "" at end of line. */
  56. #define MEOL     5    /* no    Same, assuming multiline. */
  57. #define SEOL     6    /* no    Same, assuming singleline. */
  58. #define    ANY     7    /* no    Match any one character (except newline). */
  59. #define    SANY     8    /* no    Match any one character. */
  60. #define    ANYOF     9    /* sv    Match character in (or not in) this class. */
  61. #define    CURLY    10    /* sv    Match this simple thing {n,m} times. */
  62. #define    CURLYX    11    /* sv    Match this complex thing {n,m} times. */
  63. #define    BRANCH    12    /* node    Match this alternative, or the next... */
  64. #define    BACK    13    /* no    Match "", "next" ptr points backward. */
  65. #define    EXACT    14    /* sv    Match this string (preceded by length). */
  66. #define    EXACTF    15    /* sv    Match this string, folded (prec. by length). */
  67. #define    EXACTFL    16    /* sv    Match this string, folded in locale (w/len). */
  68. #define    NOTHING    17    /* no    Match empty string. */
  69. #define    STAR    18    /* node    Match this (simple) thing 0 or more times. */
  70. #define    PLUS    19    /* node    Match this (simple) thing 1 or more times. */
  71. #define BOUND    20    /* no    Match "" at any word boundary */
  72. #define BOUNDL    21    /* no    Match "" at any word boundary */
  73. #define NBOUND    22    /* no    Match "" at any word non-boundary */
  74. #define NBOUNDL    23    /* no    Match "" at any word non-boundary */
  75. #define REF    24    /* num    Match already matched string */
  76. #define REFF    25    /* num    Match already matched string, folded */
  77. #define REFFL    26    /* num    Match already matched string, folded in loc. */
  78. #define    OPEN    27    /* num    Mark this point in input as start of #n. */
  79. #define    CLOSE    28    /* num    Analogous to OPEN. */
  80. #define MINMOD    29    /* no    Next operator is not greedy. */
  81. #define GPOS    30    /* no    Matches where last m//g left off. */
  82. #define IFMATCH    31    /* no    Succeeds if the following matches. */
  83. #define UNLESSM    32    /* no    Fails if the following matches. */
  84. #define SUCCEED    33    /* no    Return from a subroutine, basically. */
  85. #define WHILEM    34    /* no    Do curly processing and see if rest matches. */
  86. #define ALNUM    35    /* no    Match any alphanumeric character */
  87. #define ALNUML    36     /* no    Match any alphanumeric char in locale */
  88. #define NALNUM    37    /* no    Match any non-alphanumeric character */
  89. #define NALNUML    38    /* no    Match any non-alphanumeric char in locale */
  90. #define SPACE    39    /* no    Match any whitespace character */
  91. #define SPACEL    40    /* no    Match any whitespace char in locale */
  92. #define NSPACE    41    /* no    Match any non-whitespace character */
  93. #define NSPACEL    42    /* no    Match any non-whitespace char in locale */
  94. #define DIGIT    43    /* no    Match any numeric character */
  95. #define NDIGIT    44    /* no    Match any non-numeric character */
  96.  
  97. /*
  98.  * Opcode notes:
  99.  *
  100.  * BRANCH    The set of branches constituting a single choice are hooked
  101.  *        together with their "next" pointers, since precedence prevents
  102.  *        anything being concatenated to any individual branch.  The
  103.  *        "next" pointer of the last BRANCH in a choice points to the
  104.  *        thing following the whole choice.  This is also where the
  105.  *        final "next" pointer of each individual branch points; each
  106.  *        branch starts with the operand node of a BRANCH node.
  107.  *
  108.  * BACK        Normal "next" pointers all implicitly point forward; BACK
  109.  *        exists to make loop structures possible.
  110.  *
  111.  * STAR,PLUS    '?', and complex '*' and '+', are implemented as circular
  112.  *        BRANCH structures using BACK.  Simple cases (one character
  113.  *        per match) are implemented with STAR and PLUS for speed
  114.  *        and to minimize recursive plunges.
  115.  *
  116.  * OPEN,CLOSE    ...are numbered at compile time.
  117.  */
  118.  
  119. #ifndef DOINIT
  120. EXT char regarglen[];
  121. #else
  122. EXT char regarglen[] = {
  123.     0,0,0,0,0,0,0,0,0,0,
  124.     /*CURLY*/ 4, /*CURLYX*/ 4,
  125.     0,0,0,0,0,0,0,0,0,0,0,0,
  126.     /*REF*/ 2, 2, 2, /*OPEN*/ 2, /*CLOSE*/ 2,
  127.     0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
  128. };
  129. #endif
  130.  
  131. #ifndef DOINIT
  132. EXT char regkind[];
  133. #else
  134. EXT char regkind[] = {
  135.     END,
  136.     BOL,
  137.     BOL,
  138.     BOL,
  139.     EOL,
  140.     EOL,
  141.     EOL,
  142.     ANY,
  143.     ANY,
  144.     ANYOF,
  145.     CURLY,
  146.     CURLY,
  147.     BRANCH,
  148.     BACK,
  149.     EXACT,
  150.     EXACT,
  151.     EXACT,
  152.     NOTHING,
  153.     STAR,
  154.     PLUS,
  155.     BOUND,
  156.     BOUND,
  157.     NBOUND,
  158.     NBOUND,
  159.     REF,
  160.     REF,
  161.     REF,
  162.     OPEN,
  163.     CLOSE,
  164.     MINMOD,
  165.     GPOS,
  166.     BRANCH,
  167.     BRANCH,
  168.     END,
  169.     WHILEM,
  170.     ALNUM,
  171.     ALNUM,
  172.     NALNUM,
  173.     NALNUM,
  174.     SPACE,
  175.     SPACE,
  176.     NSPACE,
  177.     NSPACE,
  178.     DIGIT,
  179.     NDIGIT,
  180. };
  181. #endif
  182.  
  183. /* The following have no fixed length. */
  184. #ifndef DOINIT
  185. EXT char varies[];
  186. #else
  187. EXT char varies[] = {
  188.     BRANCH, BACK, STAR, PLUS, CURLY, CURLYX, REF, REFF, REFFL, WHILEM, 0
  189. };
  190. #endif
  191.  
  192. /* The following always have a length of 1. */
  193. #ifndef DOINIT
  194. EXT char simple[];
  195. #else
  196. EXT char simple[] = {
  197.     ANY, SANY, ANYOF,
  198.     ALNUM, ALNUML, NALNUM, NALNUML,
  199.     SPACE, SPACEL, NSPACE, NSPACEL,
  200.     DIGIT, NDIGIT, 0
  201. };
  202. #endif
  203.  
  204. EXT char regdummy;
  205.  
  206. /*
  207.  * A node is one char of opcode followed by two chars of "next" pointer.
  208.  * "Next" pointers are stored as two 8-bit pieces, high order first.  The
  209.  * value is a positive offset from the opcode of the node containing it.
  210.  * An operand, if any, simply follows the node.  (Note that much of the
  211.  * code generation knows about this implicit relationship.)
  212.  *
  213.  * Using two bytes for the "next" pointer is vast overkill for most things,
  214.  * but allows patterns to get big without disasters.
  215.  *
  216.  * [If REGALIGN is defined, the "next" pointer is always aligned on an even
  217.  * boundary, and reads the offset directly as a short.  Also, there is no
  218.  * special test to reverse the sign of BACK pointers since the offset is
  219.  * stored negative.]
  220.  */
  221.  
  222. #ifndef gould
  223. #ifndef cray
  224. #ifndef eta10
  225. #define REGALIGN
  226. #endif
  227. #endif
  228. #endif
  229.  
  230. #define    OP(p)    (*(p))
  231.  
  232. #ifndef lint
  233. #ifdef REGALIGN
  234. #define NEXT(p) (*(short*)(p+1))
  235. #define ARG1(p) (*(unsigned short*)(p+3))
  236. #define ARG2(p) (*(unsigned short*)(p+5))
  237. #else
  238. #define    NEXT(p)    (((*((p)+1)&0377)<<8) + (*((p)+2)&0377))
  239. #define    ARG1(p)    (((*((p)+3)&0377)<<8) + (*((p)+4)&0377))
  240. #define    ARG2(p)    (((*((p)+5)&0377)<<8) + (*((p)+6)&0377))
  241. #endif
  242. #else /* lint */
  243. #define NEXT(p) 0
  244. #endif /* lint */
  245.  
  246. #define    OPERAND(p)    ((p) + 3)
  247.  
  248. #ifdef REGALIGN
  249. #define    NEXTOPER(p)    ((p) + 4)
  250. #define    PREVOPER(p)    ((p) - 4)
  251. #else
  252. #define    NEXTOPER(p)    ((p) + 3)
  253. #define    PREVOPER(p)    ((p) - 3)
  254. #endif
  255.  
  256. #define MAGIC 0234
  257.  
  258. /* Flags for first parameter byte of ANYOF */
  259. #define ANYOF_INVERT    0x40
  260. #define ANYOF_FOLD    0x20
  261. #define ANYOF_LOCALE    0x10
  262. #define ANYOF_ISA    0x0F
  263. #define ANYOF_ALNUML     0x08
  264. #define ANYOF_NALNUML     0x04
  265. #define ANYOF_SPACEL     0x02
  266. #define ANYOF_NSPACEL     0x01
  267.  
  268. /*
  269.  * Utility definitions.
  270.  */
  271. #ifndef lint
  272. #ifndef CHARMASK
  273. #define    UCHARAT(p)    ((int)*(unsigned char *)(p))
  274. #else
  275. #define    UCHARAT(p)    ((int)*(p)&CHARMASK)
  276. #endif
  277. #else /* lint */
  278. #define UCHARAT(p)    regdummy
  279. #endif /* lint */
  280.  
  281. #define    FAIL(m)    croak("/%.127s/: %s",regprecomp,m)
  282.