summaryrefslogtreecommitdiff
path: root/regcomp.h
blob: 74888fa80ad4f3dd6e71f4411e1fb16dcbd6fe0b (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
/*    regcomp.h
 */

/*
 * The "internal use only" fields in regexp.h are present to pass info from
 * compile to execute that permits the execute phase to run lots faster on
 * simple cases.  They are:
 *
 * regstart	sv that must begin a match; Nullch if none obvious
 * reganch	is the match anchored (at beginning-of-line only)?
 * regmust	string (pointer into program) that match must include, or NULL
 *  [regmust changed to SV* for bminstr()--law]
 * regmlen	length of regmust string
 *  [regmlen not used currently]
 *
 * Regstart and reganch permit very fast decisions on suitable starting points
 * for a match, cutting down the work a lot.  Regmust permits fast rejection
 * of lines that cannot possibly match.  The regmust tests are costly enough
 * that pregcomp() supplies a regmust only if the r.e. contains something
 * potentially expensive (at present, the only such thing detected is * or +
 * at the start of the r.e., which can involve a lot of backup).  Regmlen is
 * supplied because the test in pregexec() needs it and pregcomp() is computing
 * it anyway.
 * [regmust is now supplied always.  The tests that use regmust have a
 * heuristic that disables the test if it usually matches.]
 *
 * [In fact, we now use regmust in many cases to locate where the search
 * starts in the string, so if regback is >= 0, the regmust search is never
 * wasted effort.  The regback variable says how many characters back from
 * where regmust matched is the earliest possible start of the match.
 * For instance, /[a-z].foo/ has a regmust of 'foo' and a regback of 2.]
 */

/*
 * Structure for regexp "program".  This is essentially a linear encoding
 * of a nondeterministic finite-state machine (aka syntax charts or
 * "railroad normal form" in parsing technology).  Each node is an opcode
 * plus a "next" pointer, possibly plus an operand.  "Next" pointers of
 * all nodes except BRANCH implement concatenation; a "next" pointer with
 * a BRANCH on both ends of it is connecting two alternatives.  (Here we
 * have one of the subtle syntax dependencies:  an individual BRANCH (as
 * opposed to a collection of them) is never concatenated with anything
 * because of operator precedence.)  The operand of some types of node is
 * a literal string; for others, it is a node leading into a sub-FSM.  In
 * particular, the operand of a BRANCH node is the first node of the branch.
 * (NB this is *not* a tree structure:  the tail of the branch connects
 * to the thing following the set of BRANCHes.)  The opcodes are:
 */

/* definition	number	opnd?	meaning */
#define	END	 0	/* no	End of program. */
#define	BOL	 1	/* no	Match "" at beginning of line. */
#define MBOL	 2	/* no	Same, assuming multiline. */
#define SBOL	 3	/* no	Same, assuming singleline. */
#define	EOL	 4	/* no	Match "" at end of line. */
#define MEOL	 5	/* no	Same, assuming multiline. */
#define SEOL	 6	/* no	Same, assuming singleline. */
#define	ANY	 7	/* no	Match any one character (except newline). */
#define	SANY	 8	/* no	Match any one character. */
#define	ANYOF	 9	/* sv	Match character in (or not in) this class. */
#define	CURLY	10	/* sv	Match this simple thing {n,m} times. */
#define	CURLYX	11	/* sv	Match this complex thing {n,m} times. */
#define	BRANCH	12	/* node	Match this alternative, or the next... */
#define	BACK	13	/* no	Match "", "next" ptr points backward. */
#define	EXACT	14	/* sv	Match this string (preceded by length). */
#define	EXACTF	15	/* sv	Match this string, folded (prec. by length). */
#define	EXACTFL	16	/* sv	Match this string, folded in locale (w/len). */
#define	NOTHING	17	/* no	Match empty string. */
#define	STAR	18	/* node	Match this (simple) thing 0 or more times. */
#define	PLUS	19	/* node	Match this (simple) thing 1 or more times. */
#define BOUND	20	/* no	Match "" at any word boundary */
#define BOUNDL	21	/* no	Match "" at any word boundary */
#define NBOUND	22	/* no	Match "" at any word non-boundary */
#define NBOUNDL	23	/* no	Match "" at any word non-boundary */
#define REF	24	/* num	Match already matched string */
#define REFF	25	/* num	Match already matched string, folded */
#define REFFL	26	/* num	Match already matched string, folded in loc. */
#define	OPEN	27	/* num	Mark this point in input as start of #n. */
#define	CLOSE	28	/* num	Analogous to OPEN. */
#define MINMOD	29	/* no	Next operator is not greedy. */
#define GPOS	30	/* no	Matches where last m//g left off. */
#define IFMATCH	31	/* no	Succeeds if the following matches. */
#define UNLESSM	32	/* no	Fails if the following matches. */
#define SUCCEED	33	/* no	Return from a subroutine, basically. */
#define WHILEM	34	/* no	Do curly processing and see if rest matches. */
#define ALNUM	35	/* no	Match any alphanumeric character */
#define ALNUML	36 	/* no	Match any alphanumeric char in locale */
#define NALNUM	37	/* no	Match any non-alphanumeric character */
#define NALNUML	38	/* no	Match any non-alphanumeric char in locale */
#define SPACE	39	/* no	Match any whitespace character */
#define SPACEL	40	/* no	Match any whitespace char in locale */
#define NSPACE	41	/* no	Match any non-whitespace character */
#define NSPACEL	42	/* no	Match any non-whitespace char in locale */
#define DIGIT	43	/* no	Match any numeric character */
#define NDIGIT	44	/* no	Match any non-numeric character */

/*
 * Opcode notes:
 *
 * BRANCH	The set of branches constituting a single choice are hooked
 *		together with their "next" pointers, since precedence prevents
 *		anything being concatenated to any individual branch.  The
 *		"next" pointer of the last BRANCH in a choice points to the
 *		thing following the whole choice.  This is also where the
 *		final "next" pointer of each individual branch points; each
 *		branch starts with the operand node of a BRANCH node.
 *
 * BACK		Normal "next" pointers all implicitly point forward; BACK
 *		exists to make loop structures possible.
 *
 * STAR,PLUS	'?', and complex '*' and '+', are implemented as circular
 *		BRANCH structures using BACK.  Simple cases (one character
 *		per match) are implemented with STAR and PLUS for speed
 *		and to minimize recursive plunges.
 *
 * OPEN,CLOSE	...are numbered at compile time.
 */

#ifndef DOINIT
EXT char regarglen[];
#else
EXT char regarglen[] = {
    0,0,0,0,0,0,0,0,0,0,
    /*CURLY*/ 4, /*CURLYX*/ 4,
    0,0,0,0,0,0,0,0,0,0,0,0,
    /*REF*/ 2, 2, 2, /*OPEN*/ 2, /*CLOSE*/ 2,
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
};
#endif

#ifndef DOINIT
EXT char regkind[];
#else
EXT char regkind[] = {
	END,
	BOL,
	BOL,
	BOL,
	EOL,
	EOL,
	EOL,
	ANY,
	ANY,
	ANYOF,
	CURLY,
	CURLY,
	BRANCH,
	BACK,
	EXACT,
	EXACT,
	EXACT,
	NOTHING,
	STAR,
	PLUS,
	BOUND,
	BOUND,
	NBOUND,
	NBOUND,
	REF,
	REF,
	REF,
	OPEN,
	CLOSE,
	MINMOD,
	GPOS,
	BRANCH,
	BRANCH,
	END,
	WHILEM,
	ALNUM,
	ALNUM,
	NALNUM,
	NALNUM,
	SPACE,
	SPACE,
	NSPACE,
	NSPACE,
	DIGIT,
	NDIGIT,
};
#endif

/* The following have no fixed length. */
#ifndef DOINIT
EXT char varies[];
#else
EXT char varies[] = {
    BRANCH, BACK, STAR, PLUS, CURLY, CURLYX, REF, REFF, REFFL, WHILEM, 0
};
#endif

/* The following always have a length of 1. */
#ifndef DOINIT
EXT char simple[];
#else
EXT char simple[] = {
    ANY, SANY, ANYOF,
    ALNUM, ALNUML, NALNUM, NALNUML,
    SPACE, SPACEL, NSPACE, NSPACEL,
    DIGIT, NDIGIT, 0
};
#endif

EXT char regdummy;

/*
 * A node is one char of opcode followed by two chars of "next" pointer.
 * "Next" pointers are stored as two 8-bit pieces, high order first.  The
 * value is a positive offset from the opcode of the node containing it.
 * An operand, if any, simply follows the node.  (Note that much of the
 * code generation knows about this implicit relationship.)
 *
 * Using two bytes for the "next" pointer is vast overkill for most things,
 * but allows patterns to get big without disasters.
 *
 * [If REGALIGN is defined, the "next" pointer is always aligned on an even
 * boundary, and reads the offset directly as a short.  Also, there is no
 * special test to reverse the sign of BACK pointers since the offset is
 * stored negative.]
 */

#ifndef gould
#ifndef cray
#ifndef eta10
#define REGALIGN
#endif
#endif
#endif

#define	OP(p)	(*(p))

#ifndef lint
#ifdef REGALIGN
#define NEXT(p) (*(short*)(p+1))
#define ARG1(p) (*(unsigned short*)(p+3))
#define ARG2(p) (*(unsigned short*)(p+5))
#else
#define	NEXT(p)	(((*((p)+1)&0377)<<8) + (*((p)+2)&0377))
#define	ARG1(p)	(((*((p)+3)&0377)<<8) + (*((p)+4)&0377))
#define	ARG2(p)	(((*((p)+5)&0377)<<8) + (*((p)+6)&0377))
#endif
#else /* lint */
#define NEXT(p) 0
#endif /* lint */

#define	OPERAND(p)	((p) + 3)

#ifdef REGALIGN
#define	NEXTOPER(p)	((p) + 4)
#define	PREVOPER(p)	((p) - 4)
#else
#define	NEXTOPER(p)	((p) + 3)
#define	PREVOPER(p)	((p) - 3)
#endif

#define MAGIC 0234

/* Flags for first parameter byte of ANYOF */
#define ANYOF_INVERT	0x40
#define ANYOF_FOLD	0x20
#define ANYOF_LOCALE	0x10
#define ANYOF_ISA	0x0F
#define ANYOF_ALNUML	 0x08
#define ANYOF_NALNUML	 0x04
#define ANYOF_SPACEL	 0x02
#define ANYOF_NSPACEL	 0x01

/* Utility macros for bitmap of ANYOF */
#define ANYOF_BYTE(p,c)     (p)[1 + (((c) >> 3) & 31)]
#define ANYOF_BIT(c)        (1 << ((c) & 7))
#define ANYOF_SET(p,c)      (ANYOF_BYTE(p,c) |=  ANYOF_BIT(c))
#define ANYOF_CLEAR(p,c)    (ANYOF_BYTE(p,c) &= ~ANYOF_BIT(c))
#define ANYOF_TEST(p,c)     (ANYOF_BYTE(p,c) &   ANYOF_BIT(c))

/*
 * Utility definitions.
 */
#ifndef lint
#ifndef CHARMASK
#define	UCHARAT(p)	((int)*(unsigned char *)(p))
#else
#define	UCHARAT(p)	((int)*(p)&CHARMASK)
#endif
#else /* lint */
#define UCHARAT(p)	regdummy
#endif /* lint */

#define	FAIL(m)	croak("/%.127s/: %s",regprecomp,m)