regcomp.h

   1 /* $Header: regcomp.h,v 3.0.1.2 90/11/10 01:58:28 lwall Locked $
   2  *
   3  * $Log:        regcomp.h,v $
   4  * Revision 3.0.1.2  90/11/10  01:58:28  lwall
   5  * patch38: random cleanup
   6  *
   7  * Revision 3.0.1.1  90/08/09  05:06:49  lwall
   8  * patch19: sped up {m,n} on simple items
   9  *
  10  * Revision 3.0  89/10/18  15:22:39  lwall
  11  * 3.0 baseline
  12  *
  13  */
  14
  15 /*
  16  * The "internal use only" fields in regexp.h are present to pass info from
  17  * compile to execute that permits the execute phase to run lots faster on
  18  * simple cases.  They are:
  19  *
  20  * regstart     str that must begin a match; Nullch if none obvious
  21  * reganch      is the match anchored (at beginning-of-line only)?
  22  * regmust      string (pointer into program) that match must include, or NULL
  23  *  [regmust changed to STR* for bminstr()--law]
  24  * regmlen      length of regmust string
  25  *  [regmlen not used currently]
  26  *
  27  * Regstart and reganch permit very fast decisions on suitable starting points
  28  * for a match, cutting down the work a lot.  Regmust permits fast rejection
  29  * of lines that cannot possibly match.  The regmust tests are costly enough
  30  * that regcomp() supplies a regmust only if the r.e. contains something
  31  * potentially expensive (at present, the only such thing detected is * or +
  32  * at the start of the r.e., which can involve a lot of backup).  Regmlen is
  33  * supplied because the test in regexec() needs it and regcomp() is computing
  34  * it anyway.
  35  * [regmust is now supplied always.  The tests that use regmust have a
  36  * heuristic that disables the test if it usually matches.]
  37  *
  38  * [In fact, we now use regmust in many cases to locate where the search
  39  * starts in the string, so if regback is >= 0, the regmust search is never
  40  * wasted effort.  The regback variable says how many characters back from
  41  * where regmust matched is the earliest possible start of the match.
  42  * For instance, /[a-z].foo/ has a regmust of 'foo' and a regback of 2.]
  43  */
  44
  45 /*
  46  * Structure for regexp "program".  This is essentially a linear encoding
  47  * of a nondeterministic finite-state machine (aka syntax charts or
  48  * "railroad normal form" in parsing technology).  Each node is an opcode
  49  * plus a "next" pointer, possibly plus an operand.  "Next" pointers of
  50  * all nodes except BRANCH implement concatenation; a "next" pointer with
  51  * a BRANCH on both ends of it is connecting two alternatives.  (Here we
  52  * have one of the subtle syntax dependencies:  an individual BRANCH (as
  53  * opposed to a collection of them) is never concatenated with anything
  54  * because of operator precedence.)  The operand of some types of node is
  55  * a literal string; for others, it is a node leading into a sub-FSM.  In
  56  * particular, the operand of a BRANCH node is the first node of the branch.
  57  * (NB this is *not* a tree structure:  the tail of the branch connects
  58  * to the thing following the set of BRANCHes.)  The opcodes are:
  59  */
  60
  61 /* definition   number  opnd?   meaning */
  62 #define END     0       /* no   End of program. */
  63 #define BOL     1       /* no   Match "" at beginning of line. */
  64 #define EOL     2       /* no   Match "" at end of line. */
  65 #define ANY     3       /* no   Match any one character. */
  66 #define ANYOF   4       /* str  Match character in (or not in) this class. */
  67 #define CURLY   5       /* str  Match this simple thing {n,m} times. */
  68 #define BRANCH  6       /* node Match this alternative, or the next... */
  69 #define BACK    7       /* no   Match "", "next" ptr points backward. */
  70 #define EXACTLY 8       /* str  Match this string (preceded by length). */
  71 #define NOTHING 9       /* no   Match empty string. */
  72 #define STAR    10      /* node Match this (simple) thing 0 or more times. */
  73 #define PLUS    11      /* node Match this (simple) thing 1 or more times. */
  74 #define ALNUM   12      /* no   Match any alphanumeric character */
  75 #define NALNUM  13      /* no   Match any non-alphanumeric character */
  76 #define BOUND   14      /* no   Match "" at any word boundary */
  77 #define NBOUND  15      /* no   Match "" at any word non-boundary */
  78 #define SPACE   16      /* no   Match any whitespace character */
  79 #define NSPACE  17      /* no   Match any non-whitespace character */
  80 #define DIGIT   18      /* no   Match any numeric character */
  81 #define NDIGIT  19      /* no   Match any non-numeric character */
  82 #define REF     20      /* no   Match some already matched string */
  83 #define OPEN    30      /* no   Mark this point in input as start of #n. */
  84                         /*      OPEN+1 is number 1, etc. */
  85 #define CLOSE   40      /* no   Analogous to OPEN. */
  86 /* CLOSE must be last one! see regmust finder */
  87
  88 /*
  89  * Opcode notes:
  90  *
  91  * BRANCH       The set of branches constituting a single choice are hooked
  92  *              together with their "next" pointers, since precedence prevents
  93  *              anything being concatenated to any individual branch.  The
  94  *              "next" pointer of the last BRANCH in a choice points to the
  95  *              thing following the whole choice.  This is also where the
  96  *              final "next" pointer of each individual branch points; each
  97  *              branch starts with the operand node of a BRANCH node.
  98  *
  99  * BACK         Normal "next" pointers all implicitly point forward; BACK
 100  *              exists to make loop structures possible.
 101  *
 102  * STAR,PLUS    '?', and complex '*' and '+', are implemented as circular
 103  *              BRANCH structures using BACK.  Simple cases (one character
 104  *              per match) are implemented with STAR and PLUS for speed
 105  *              and to minimize recursive plunges.
 106  *
 107  * OPEN,CLOSE   ...are numbered at compile time.
 108  */
 109
 110 /* The following have no fixed length. */
 111 #ifndef DOINIT
 112 extern char varies[];
 113 #else
 114 char varies[] = {BRANCH,BACK,STAR,PLUS,CURLY,
 115         REF+1,REF+2,REF+3,REF+4,REF+5,REF+6,REF+7,REF+8,REF+9,0};
 116 #endif
 117
 118 /* The following always have a length of 1. */
 119 #ifndef DOINIT
 120 extern char simple[];
 121 #else
 122 char simple[] = {ANY,ANYOF,ALNUM,NALNUM,SPACE,NSPACE,DIGIT,NDIGIT,0};
 123 #endif
 124
 125 EXT char regdummy;
 126
 127 /*
 128  * A node is one char of opcode followed by two chars of "next" pointer.
 129  * "Next" pointers are stored as two 8-bit pieces, high order first.  The
 130  * value is a positive offset from the opcode of the node containing it.
 131  * An operand, if any, simply follows the node.  (Note that much of the
 132  * code generation knows about this implicit relationship.)
 133  *
 134  * Using two bytes for the "next" pointer is vast overkill for most things,
 135  * but allows patterns to get big without disasters.
 136  *
 137  * [If REGALIGN is defined, the "next" pointer is always aligned on an even
 138  * boundary, and reads the offset directly as a short.  Also, there is no
 139  * special test to reverse the sign of BACK pointers since the offset is
 140  * stored negative.]
 141  */
 142
 143 #ifndef gould
 144 #ifndef cray
 145 #ifndef eta10
 146 #define REGALIGN
 147 #endif
 148 #endif
 149 #endif
 150
 151 #define OP(p)   (*(p))
 152
 153 #ifndef lint
 154 #ifdef REGALIGN
 155 #define NEXT(p) (*(short*)(p+1))
 156 #define ARG1(p) (*(unsigned short*)(p+3))
 157 #define ARG2(p) (*(unsigned short*)(p+5))
 158 #else
 159 #define NEXT(p) (((*((p)+1)&0377)<<8) + (*((p)+2)&0377))
 160 #define ARG1(p) (((*((p)+3)&0377)<<8) + (*((p)+4)&0377))
 161 #define ARG2(p) (((*((p)+5)&0377)<<8) + (*((p)+6)&0377))
 162 #endif
 163 #else /* lint */
 164 #define NEXT(p) 0
 165 #endif /* lint */
 166
 167 #define OPERAND(p)      ((p) + 3)
 168
 169 #ifdef REGALIGN
 170 #define NEXTOPER(p)     ((p) + 4)
 171 #else
 172 #define NEXTOPER(p)     ((p) + 3)
 173 #endif
 174
 175 #define MAGIC 0234
 176
 177 /*
 178  * Utility definitions.
 179  */
 180 #ifndef lint
 181 #ifndef CHARBITS
 182 #define UCHARAT(p)      ((int)*(unsigned char *)(p))
 183 #else
 184 #define UCHARAT(p)      ((int)*(p)&CHARBITS)
 185 #endif
 186 #else /* lint */
 187 #define UCHARAT(p)      regdummy
 188 #endif /* lint */
 189
 190 #define FAIL(m) fatal("/%s/: %s",regprecomp,m)
 191
 192 char *regnext();
 193 #ifdef DEBUGGING
 194 void regdump();
 195 char *regprop();
 196 #endif
 197