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