1 76193d7c 2003-09-30 devnull #include "sam.h"
  2 76193d7c 2003-09-30 devnull 
  3 76193d7c 2003-09-30 devnull Rangeset	sel;
  4 76193d7c 2003-09-30 devnull String		lastregexp;
  5 76193d7c 2003-09-30 devnull /*
  6 76193d7c 2003-09-30 devnull  * Machine Information
  7 76193d7c 2003-09-30 devnull  */
  8 76193d7c 2003-09-30 devnull typedef struct Inst Inst;
  9 76193d7c 2003-09-30 devnull 
 10 76193d7c 2003-09-30 devnull struct Inst
 11 76193d7c 2003-09-30 devnull {
 12 36d9b90c 2010-07-14 rsc 	long	type;	/* < OPERATOR ==> literal, otherwise action */
 13 76193d7c 2003-09-30 devnull 	union {
 14 76193d7c 2003-09-30 devnull 		int rsid;
 15 76193d7c 2003-09-30 devnull 		int rsubid;
 16 76193d7c 2003-09-30 devnull 		int class;
 17 76193d7c 2003-09-30 devnull 		struct Inst *rother;
 18 76193d7c 2003-09-30 devnull 		struct Inst *rright;
 19 76193d7c 2003-09-30 devnull 	} r;
 20 76193d7c 2003-09-30 devnull 	union{
 21 76193d7c 2003-09-30 devnull 		struct Inst *lleft;
 22 76193d7c 2003-09-30 devnull 		struct Inst *lnext;
 23 76193d7c 2003-09-30 devnull 	} l;
 24 76193d7c 2003-09-30 devnull };
 25 76193d7c 2003-09-30 devnull #define	sid	r.rsid
 26 76193d7c 2003-09-30 devnull #define	subid	r.rsubid
 27 76193d7c 2003-09-30 devnull #define	rclass	r.class
 28 76193d7c 2003-09-30 devnull #define	other	r.rother
 29 76193d7c 2003-09-30 devnull #define	right	r.rright
 30 76193d7c 2003-09-30 devnull #define	left	l.lleft
 31 76193d7c 2003-09-30 devnull #define	next	l.lnext
 32 76193d7c 2003-09-30 devnull 
 33 76193d7c 2003-09-30 devnull #define	NPROG	1024
 34 76193d7c 2003-09-30 devnull Inst	program[NPROG];
 35 76193d7c 2003-09-30 devnull Inst	*progp;
 36 76193d7c 2003-09-30 devnull Inst	*startinst;	/* First inst. of program; might not be program[0] */
 37 76193d7c 2003-09-30 devnull Inst	*bstartinst;	/* same for backwards machine */
 38 76193d7c 2003-09-30 devnull 
 39 76193d7c 2003-09-30 devnull typedef struct Ilist Ilist;
 40 76193d7c 2003-09-30 devnull struct Ilist
 41 76193d7c 2003-09-30 devnull {
 42 76193d7c 2003-09-30 devnull 	Inst	*inst;		/* Instruction of the thread */
 43 76193d7c 2003-09-30 devnull 	Rangeset se;
 44 76193d7c 2003-09-30 devnull 	Posn	startp;		/* first char of match */
 45 76193d7c 2003-09-30 devnull };
 46 76193d7c 2003-09-30 devnull 
 47 c99ef336 2007-06-09 devnull #define	NLIST	127
 48 76193d7c 2003-09-30 devnull 
 49 76193d7c 2003-09-30 devnull Ilist	*tl, *nl;	/* This list, next list */
 50 c99ef336 2007-06-09 devnull Ilist	list[2][NLIST+1];	/* +1 for trailing null */
 51 76193d7c 2003-09-30 devnull static	Rangeset sempty;
 52 76193d7c 2003-09-30 devnull 
 53 76193d7c 2003-09-30 devnull /*
 54 76193d7c 2003-09-30 devnull  * Actions and Tokens
 55 76193d7c 2003-09-30 devnull  *
 56 36d9b90c 2010-07-14 rsc  *	0x10000xx are operators, value == precedence
 57 36d9b90c 2010-07-14 rsc  *	0x20000xx are tokens, i.e. operands for operators
 58 76193d7c 2003-09-30 devnull  */
 59 36d9b90c 2010-07-14 rsc #define	OPERATOR	0x1000000	/* Bit set in all operators */
 60 36d9b90c 2010-07-14 rsc #define	START		(OPERATOR+0)	/* Start, used for marker on stack */
 61 36d9b90c 2010-07-14 rsc #define	RBRA		(OPERATOR+1)	/* Right bracket, ) */
 62 36d9b90c 2010-07-14 rsc #define	LBRA		(OPERATOR+2)	/* Left bracket, ( */
 63 36d9b90c 2010-07-14 rsc #define	OR		(OPERATOR+3)	/* Alternation, | */
 64 36d9b90c 2010-07-14 rsc #define	CAT		(OPERATOR+4)	/* Concatentation, implicit operator */
 65 36d9b90c 2010-07-14 rsc #define	STAR		(OPERATOR+5)	/* Closure, * */
 66 36d9b90c 2010-07-14 rsc #define	PLUS		(OPERATOR+6)	/* a+ == aa* */
 67 36d9b90c 2010-07-14 rsc #define	QUEST		(OPERATOR+7)	/* a? == a|nothing, i.e. 0 or 1 a's */
 68 36d9b90c 2010-07-14 rsc #define	ANY		0x2000000	/* Any character but newline, . */
 69 36d9b90c 2010-07-14 rsc #define	NOP		(ANY+1)	/* No operation, internal use only */
 70 36d9b90c 2010-07-14 rsc #define	BOL		(ANY+2)	/* Beginning of line, ^ */
 71 36d9b90c 2010-07-14 rsc #define	EOL		(ANY+3)	/* End of line, $ */
 72 36d9b90c 2010-07-14 rsc #define	CCLASS		(ANY+4)	/* Character class, [] */
 73 36d9b90c 2010-07-14 rsc #define	NCCLASS		(ANY+5)	/* Negated character class, [^] */
 74 36d9b90c 2010-07-14 rsc #define	END		(ANY+0x77)	/* Terminate: match found */
 75 76193d7c 2003-09-30 devnull 
 76 36d9b90c 2010-07-14 rsc #define	ISATOR		OPERATOR
 77 36d9b90c 2010-07-14 rsc #define	ISAND		ANY
 78 76193d7c 2003-09-30 devnull 
 79 36d9b90c 2010-07-14 rsc #define	QUOTED	0x4000000	/* Bit set for \-ed lex characters */
 80 36d9b90c 2010-07-14 rsc 
 81 76193d7c 2003-09-30 devnull /*
 82 76193d7c 2003-09-30 devnull  * Parser Information
 83 76193d7c 2003-09-30 devnull  */
 84 76193d7c 2003-09-30 devnull typedef struct Node Node;
 85 76193d7c 2003-09-30 devnull struct Node
 86 76193d7c 2003-09-30 devnull {
 87 76193d7c 2003-09-30 devnull 	Inst	*first;
 88 76193d7c 2003-09-30 devnull 	Inst	*last;
 89 76193d7c 2003-09-30 devnull };
 90 76193d7c 2003-09-30 devnull 
 91 76193d7c 2003-09-30 devnull #define	NSTACK	20
 92 76193d7c 2003-09-30 devnull Node	andstack[NSTACK];
 93 76193d7c 2003-09-30 devnull Node	*andp;
 94 76193d7c 2003-09-30 devnull int	atorstack[NSTACK];
 95 76193d7c 2003-09-30 devnull int	*atorp;
 96 76193d7c 2003-09-30 devnull int	lastwasand;	/* Last token was operand */
 97 76193d7c 2003-09-30 devnull int	cursubid;
 98 76193d7c 2003-09-30 devnull int	subidstack[NSTACK];
 99 76193d7c 2003-09-30 devnull int	*subidp;
100 76193d7c 2003-09-30 devnull int	backwards;
101 76193d7c 2003-09-30 devnull int	nbra;
102 76193d7c 2003-09-30 devnull Rune	*exprp;		/* pointer to next character in source expression */
103 76193d7c 2003-09-30 devnull #define	DCLASS	10	/* allocation increment */
104 76193d7c 2003-09-30 devnull int	nclass;		/* number active */
105 76193d7c 2003-09-30 devnull int	Nclass;		/* high water mark */
106 76193d7c 2003-09-30 devnull Rune	**class;
107 76193d7c 2003-09-30 devnull int	negateclass;
108 76193d7c 2003-09-30 devnull 
109 c99ef336 2007-06-09 devnull int	addinst(Ilist *l, Inst *inst, Rangeset *sep);
110 76193d7c 2003-09-30 devnull void	newmatch(Rangeset*);
111 76193d7c 2003-09-30 devnull void	bnewmatch(Rangeset*);
112 76193d7c 2003-09-30 devnull void	pushand(Inst*, Inst*);
113 76193d7c 2003-09-30 devnull void	pushator(int);
114 76193d7c 2003-09-30 devnull Node	*popand(int);
115 76193d7c 2003-09-30 devnull int	popator(void);
116 76193d7c 2003-09-30 devnull void	startlex(Rune*);
117 76193d7c 2003-09-30 devnull int	lex(void);
118 76193d7c 2003-09-30 devnull void	operator(int);
119 76193d7c 2003-09-30 devnull void	operand(int);
120 76193d7c 2003-09-30 devnull void	evaluntil(int);
121 76193d7c 2003-09-30 devnull void	optimize(Inst*);
122 76193d7c 2003-09-30 devnull void	bldcclass(void);
123 76193d7c 2003-09-30 devnull 
124 76193d7c 2003-09-30 devnull void
125 76193d7c 2003-09-30 devnull regerror(Err e)
126 76193d7c 2003-09-30 devnull {
127 76193d7c 2003-09-30 devnull 	Strzero(&lastregexp);
128 76193d7c 2003-09-30 devnull 	error(e);
129 76193d7c 2003-09-30 devnull }
130 76193d7c 2003-09-30 devnull 
131 76193d7c 2003-09-30 devnull void
132 76193d7c 2003-09-30 devnull regerror_c(Err e, int c)
133 76193d7c 2003-09-30 devnull {
134 76193d7c 2003-09-30 devnull 	Strzero(&lastregexp);
135 76193d7c 2003-09-30 devnull 	error_c(e, c);
136 76193d7c 2003-09-30 devnull }
137 76193d7c 2003-09-30 devnull 
138 76193d7c 2003-09-30 devnull Inst *
139 76193d7c 2003-09-30 devnull newinst(int t)
140 76193d7c 2003-09-30 devnull {
141 76193d7c 2003-09-30 devnull 	if(progp >= &program[NPROG])
142 76193d7c 2003-09-30 devnull 		regerror(Etoolong);
143 76193d7c 2003-09-30 devnull 	progp->type = t;
144 76193d7c 2003-09-30 devnull 	progp->left = 0;
145 76193d7c 2003-09-30 devnull 	progp->right = 0;
146 76193d7c 2003-09-30 devnull 	return progp++;
147 76193d7c 2003-09-30 devnull }
148 76193d7c 2003-09-30 devnull 
149 76193d7c 2003-09-30 devnull Inst *
150 76193d7c 2003-09-30 devnull realcompile(Rune *s)
151 76193d7c 2003-09-30 devnull {
152 76193d7c 2003-09-30 devnull 	int token;
153 76193d7c 2003-09-30 devnull 
154 76193d7c 2003-09-30 devnull 	startlex(s);
155 76193d7c 2003-09-30 devnull 	atorp = atorstack;
156 76193d7c 2003-09-30 devnull 	andp = andstack;
157 76193d7c 2003-09-30 devnull 	subidp = subidstack;
158 76193d7c 2003-09-30 devnull 	cursubid = 0;
159 76193d7c 2003-09-30 devnull 	lastwasand = FALSE;
160 76193d7c 2003-09-30 devnull 	/* Start with a low priority operator to prime parser */
161 76193d7c 2003-09-30 devnull 	pushator(START-1);
162 76193d7c 2003-09-30 devnull 	while((token=lex()) != END){
163 76193d7c 2003-09-30 devnull 		if((token&ISATOR) == OPERATOR)
164 76193d7c 2003-09-30 devnull 			operator(token);
165 76193d7c 2003-09-30 devnull 		else
166 76193d7c 2003-09-30 devnull 			operand(token);
167 76193d7c 2003-09-30 devnull 	}
168 76193d7c 2003-09-30 devnull 	/* Close with a low priority operator */
169 76193d7c 2003-09-30 devnull 	evaluntil(START);
170 76193d7c 2003-09-30 devnull 	/* Force END */
171 76193d7c 2003-09-30 devnull 	operand(END);
172 76193d7c 2003-09-30 devnull 	evaluntil(START);
173 76193d7c 2003-09-30 devnull 	if(nbra)
174 76193d7c 2003-09-30 devnull 		regerror(Eleftpar);
175 76193d7c 2003-09-30 devnull 	--andp;	/* points to first and only operand */
176 76193d7c 2003-09-30 devnull 	return andp->first;
177 76193d7c 2003-09-30 devnull }
178 76193d7c 2003-09-30 devnull 
179 76193d7c 2003-09-30 devnull void
180 76193d7c 2003-09-30 devnull compile(String *s)
181 76193d7c 2003-09-30 devnull {
182 76193d7c 2003-09-30 devnull 	int i;
183 76193d7c 2003-09-30 devnull 	Inst *oprogp;
184 76193d7c 2003-09-30 devnull 
185 76193d7c 2003-09-30 devnull 	if(Strcmp(s, &lastregexp)==0)
186 76193d7c 2003-09-30 devnull 		return;
187 76193d7c 2003-09-30 devnull 	for(i=0; i<nclass; i++)
188 76193d7c 2003-09-30 devnull 		free(class[i]);
189 76193d7c 2003-09-30 devnull 	nclass = 0;
190 76193d7c 2003-09-30 devnull 	progp = program;
191 76193d7c 2003-09-30 devnull 	backwards = FALSE;
192 76193d7c 2003-09-30 devnull 	startinst = realcompile(s->s);
193 76193d7c 2003-09-30 devnull 	optimize(program);
194 76193d7c 2003-09-30 devnull 	oprogp = progp;
195 76193d7c 2003-09-30 devnull 	backwards = TRUE;
196 76193d7c 2003-09-30 devnull 	bstartinst = realcompile(s->s);
197 76193d7c 2003-09-30 devnull 	optimize(oprogp);
198 76193d7c 2003-09-30 devnull 	Strduplstr(&lastregexp, s);
199 76193d7c 2003-09-30 devnull }
200 76193d7c 2003-09-30 devnull 
201 76193d7c 2003-09-30 devnull void
202 76193d7c 2003-09-30 devnull operand(int t)
203 76193d7c 2003-09-30 devnull {
204 76193d7c 2003-09-30 devnull 	Inst *i;
205 76193d7c 2003-09-30 devnull 	if(lastwasand)
206 76193d7c 2003-09-30 devnull 		operator(CAT);	/* catenate is implicit */
207 76193d7c 2003-09-30 devnull 	i = newinst(t);
208 76193d7c 2003-09-30 devnull 	if(t == CCLASS){
209 76193d7c 2003-09-30 devnull 		if(negateclass)
210 76193d7c 2003-09-30 devnull 			i->type = NCCLASS;	/* UGH */
211 76193d7c 2003-09-30 devnull 		i->rclass = nclass-1;		/* UGH */
212 76193d7c 2003-09-30 devnull 	}
213 76193d7c 2003-09-30 devnull 	pushand(i, i);
214 76193d7c 2003-09-30 devnull 	lastwasand = TRUE;
215 76193d7c 2003-09-30 devnull }
216 76193d7c 2003-09-30 devnull 
217 76193d7c 2003-09-30 devnull void
218 76193d7c 2003-09-30 devnull operator(int t)
219 76193d7c 2003-09-30 devnull {
220 76193d7c 2003-09-30 devnull 	if(t==RBRA && --nbra<0)
221 76193d7c 2003-09-30 devnull 		regerror(Erightpar);
222 76193d7c 2003-09-30 devnull 	if(t==LBRA){
223 76193d7c 2003-09-30 devnull /*
224 76193d7c 2003-09-30 devnull  *		if(++cursubid >= NSUBEXP)
225 76193d7c 2003-09-30 devnull  *			regerror(Esubexp);
226 76193d7c 2003-09-30 devnull  */
227 76193d7c 2003-09-30 devnull 		cursubid++;	/* silently ignored */
228 76193d7c 2003-09-30 devnull 		nbra++;
229 76193d7c 2003-09-30 devnull 		if(lastwasand)
230 76193d7c 2003-09-30 devnull 			operator(CAT);
231 76193d7c 2003-09-30 devnull 	}else
232 76193d7c 2003-09-30 devnull 		evaluntil(t);
233 76193d7c 2003-09-30 devnull 	if(t!=RBRA)
234 76193d7c 2003-09-30 devnull 		pushator(t);
235 76193d7c 2003-09-30 devnull 	lastwasand = FALSE;
236 76193d7c 2003-09-30 devnull 	if(t==STAR || t==QUEST || t==PLUS || t==RBRA)
237 76193d7c 2003-09-30 devnull 		lastwasand = TRUE;	/* these look like operands */
238 76193d7c 2003-09-30 devnull }
239 76193d7c 2003-09-30 devnull 
240 76193d7c 2003-09-30 devnull void
241 76193d7c 2003-09-30 devnull cant(char *s)
242 76193d7c 2003-09-30 devnull {
243 76193d7c 2003-09-30 devnull 	char buf[100];
244 76193d7c 2003-09-30 devnull 
245 76193d7c 2003-09-30 devnull 	sprint(buf, "regexp: can't happen: %s", s);
246 76193d7c 2003-09-30 devnull 	panic(buf);
247 76193d7c 2003-09-30 devnull }
248 76193d7c 2003-09-30 devnull 
249 76193d7c 2003-09-30 devnull void
250 76193d7c 2003-09-30 devnull pushand(Inst *f, Inst *l)
251 76193d7c 2003-09-30 devnull {
252 76193d7c 2003-09-30 devnull 	if(andp >= &andstack[NSTACK])
253 76193d7c 2003-09-30 devnull 		cant("operand stack overflow");
254 76193d7c 2003-09-30 devnull 	andp->first = f;
255 76193d7c 2003-09-30 devnull 	andp->last = l;
256 76193d7c 2003-09-30 devnull 	andp++;
257 76193d7c 2003-09-30 devnull }
258 76193d7c 2003-09-30 devnull 
259 76193d7c 2003-09-30 devnull void
260 76193d7c 2003-09-30 devnull pushator(int t)
261 76193d7c 2003-09-30 devnull {
262 76193d7c 2003-09-30 devnull 	if(atorp >= &atorstack[NSTACK])
263 76193d7c 2003-09-30 devnull 		cant("operator stack overflow");
264 76193d7c 2003-09-30 devnull 	*atorp++=t;
265 76193d7c 2003-09-30 devnull 	if(cursubid >= NSUBEXP)
266 76193d7c 2003-09-30 devnull 		*subidp++= -1;
267 76193d7c 2003-09-30 devnull 	else
268 76193d7c 2003-09-30 devnull 		*subidp++=cursubid;
269 76193d7c 2003-09-30 devnull }
270 76193d7c 2003-09-30 devnull 
271 76193d7c 2003-09-30 devnull Node *
272 76193d7c 2003-09-30 devnull popand(int op)
273 76193d7c 2003-09-30 devnull {
274 76193d7c 2003-09-30 devnull 	if(andp <= &andstack[0])
275 76193d7c 2003-09-30 devnull 		if(op)
276 76193d7c 2003-09-30 devnull 			regerror_c(Emissop, op);
277 76193d7c 2003-09-30 devnull 		else
278 76193d7c 2003-09-30 devnull 			regerror(Ebadregexp);
279 76193d7c 2003-09-30 devnull 	return --andp;
280 76193d7c 2003-09-30 devnull }
281 76193d7c 2003-09-30 devnull 
282 76193d7c 2003-09-30 devnull int
283 76193d7c 2003-09-30 devnull popator(void)
284 76193d7c 2003-09-30 devnull {
285 76193d7c 2003-09-30 devnull 	if(atorp <= &atorstack[0])
286 76193d7c 2003-09-30 devnull 		cant("operator stack underflow");
287 76193d7c 2003-09-30 devnull 	--subidp;
288 76193d7c 2003-09-30 devnull 	return *--atorp;
289 76193d7c 2003-09-30 devnull }
290 76193d7c 2003-09-30 devnull 
291 76193d7c 2003-09-30 devnull void
292 76193d7c 2003-09-30 devnull evaluntil(int pri)
293 76193d7c 2003-09-30 devnull {
294 76193d7c 2003-09-30 devnull 	Node *op1, *op2, *t;
295 76193d7c 2003-09-30 devnull 	Inst *inst1, *inst2;
296 76193d7c 2003-09-30 devnull 
297 76193d7c 2003-09-30 devnull 	while(pri==RBRA || atorp[-1]>=pri){
298 76193d7c 2003-09-30 devnull 		switch(popator()){
299 76193d7c 2003-09-30 devnull 		case LBRA:
300 76193d7c 2003-09-30 devnull 			op1 = popand('(');
301 76193d7c 2003-09-30 devnull 			inst2 = newinst(RBRA);
302 76193d7c 2003-09-30 devnull 			inst2->subid = *subidp;
303 76193d7c 2003-09-30 devnull 			op1->last->next = inst2;
304 76193d7c 2003-09-30 devnull 			inst1 = newinst(LBRA);
305 76193d7c 2003-09-30 devnull 			inst1->subid = *subidp;
306 76193d7c 2003-09-30 devnull 			inst1->next = op1->first;
307 76193d7c 2003-09-30 devnull 			pushand(inst1, inst2);
308 76193d7c 2003-09-30 devnull 			return;		/* must have been RBRA */
309 76193d7c 2003-09-30 devnull 		default:
310 76193d7c 2003-09-30 devnull 			panic("unknown regexp operator");
311 76193d7c 2003-09-30 devnull 			break;
312 76193d7c 2003-09-30 devnull 		case OR:
313 76193d7c 2003-09-30 devnull 			op2 = popand('|');
314 76193d7c 2003-09-30 devnull 			op1 = popand('|');
315 76193d7c 2003-09-30 devnull 			inst2 = newinst(NOP);
316 76193d7c 2003-09-30 devnull 			op2->last->next = inst2;
317 76193d7c 2003-09-30 devnull 			op1->last->next = inst2;
318 76193d7c 2003-09-30 devnull 			inst1 = newinst(OR);
319 76193d7c 2003-09-30 devnull 			inst1->right = op1->first;
320 76193d7c 2003-09-30 devnull 			inst1->left = op2->first;
321 76193d7c 2003-09-30 devnull 			pushand(inst1, inst2);
322 76193d7c 2003-09-30 devnull 			break;
323 76193d7c 2003-09-30 devnull 		case CAT:
324 76193d7c 2003-09-30 devnull 			op2 = popand(0);
325 76193d7c 2003-09-30 devnull 			op1 = popand(0);
326 76193d7c 2003-09-30 devnull 			if(backwards && op2->first->type!=END)
327 76193d7c 2003-09-30 devnull 				t = op1, op1 = op2, op2 = t;
328 76193d7c 2003-09-30 devnull 			op1->last->next = op2->first;
329 76193d7c 2003-09-30 devnull 			pushand(op1->first, op2->last);
330 76193d7c 2003-09-30 devnull 			break;
331 76193d7c 2003-09-30 devnull 		case STAR:
332 76193d7c 2003-09-30 devnull 			op2 = popand('*');
333 76193d7c 2003-09-30 devnull 			inst1 = newinst(OR);
334 76193d7c 2003-09-30 devnull 			op2->last->next = inst1;
335 76193d7c 2003-09-30 devnull 			inst1->right = op2->first;
336 76193d7c 2003-09-30 devnull 			pushand(inst1, inst1);
337 76193d7c 2003-09-30 devnull 			break;
338 76193d7c 2003-09-30 devnull 		case PLUS:
339 76193d7c 2003-09-30 devnull 			op2 = popand('+');
340 76193d7c 2003-09-30 devnull 			inst1 = newinst(OR);
341 76193d7c 2003-09-30 devnull 			op2->last->next = inst1;
342 76193d7c 2003-09-30 devnull 			inst1->right = op2->first;
343 76193d7c 2003-09-30 devnull 			pushand(op2->first, inst1);
344 76193d7c 2003-09-30 devnull 			break;
345 76193d7c 2003-09-30 devnull 		case QUEST:
346 76193d7c 2003-09-30 devnull 			op2 = popand('?');
347 76193d7c 2003-09-30 devnull 			inst1 = newinst(OR);
348 76193d7c 2003-09-30 devnull 			inst2 = newinst(NOP);
349 76193d7c 2003-09-30 devnull 			inst1->left = inst2;
350 76193d7c 2003-09-30 devnull 			inst1->right = op2->first;
351 76193d7c 2003-09-30 devnull 			op2->last->next = inst2;
352 76193d7c 2003-09-30 devnull 			pushand(inst1, inst2);
353 76193d7c 2003-09-30 devnull 			break;
354 76193d7c 2003-09-30 devnull 		}
355 76193d7c 2003-09-30 devnull 	}
356 76193d7c 2003-09-30 devnull }
357 76193d7c 2003-09-30 devnull 
358 76193d7c 2003-09-30 devnull 
359 76193d7c 2003-09-30 devnull void
360 76193d7c 2003-09-30 devnull optimize(Inst *start)
361 76193d7c 2003-09-30 devnull {
362 76193d7c 2003-09-30 devnull 	Inst *inst, *target;
363 76193d7c 2003-09-30 devnull 
364 76193d7c 2003-09-30 devnull 	for(inst=start; inst->type!=END; inst++){
365 76193d7c 2003-09-30 devnull 		target = inst->next;
366 76193d7c 2003-09-30 devnull 		while(target->type == NOP)
367 76193d7c 2003-09-30 devnull 			target = target->next;
368 76193d7c 2003-09-30 devnull 		inst->next = target;
369 76193d7c 2003-09-30 devnull 	}
370 76193d7c 2003-09-30 devnull }
371 76193d7c 2003-09-30 devnull 
372 76193d7c 2003-09-30 devnull #ifdef	DEBUG
373 76193d7c 2003-09-30 devnull void
374 76193d7c 2003-09-30 devnull dumpstack(void){
375 76193d7c 2003-09-30 devnull 	Node *stk;
376 76193d7c 2003-09-30 devnull 	int *ip;
377 76193d7c 2003-09-30 devnull 
378 76193d7c 2003-09-30 devnull 	dprint("operators\n");
379 76193d7c 2003-09-30 devnull 	for(ip = atorstack; ip<atorp; ip++)
380 76193d7c 2003-09-30 devnull 		dprint("0%o\n", *ip);
381 76193d7c 2003-09-30 devnull 	dprint("operands\n");
382 76193d7c 2003-09-30 devnull 	for(stk = andstack; stk<andp; stk++)
383 76193d7c 2003-09-30 devnull 		dprint("0%o\t0%o\n", stk->first->type, stk->last->type);
384 76193d7c 2003-09-30 devnull }
385 76193d7c 2003-09-30 devnull void
386 76193d7c 2003-09-30 devnull dump(void){
387 76193d7c 2003-09-30 devnull 	Inst *l;
388 76193d7c 2003-09-30 devnull 
389 76193d7c 2003-09-30 devnull 	l = program;
390 76193d7c 2003-09-30 devnull 	do{
391 76193d7c 2003-09-30 devnull 		dprint("%d:\t0%o\t%d\t%d\n", l-program, l->type,
392 76193d7c 2003-09-30 devnull 			l->left-program, l->right-program);
393 76193d7c 2003-09-30 devnull 	}while(l++->type);
394 76193d7c 2003-09-30 devnull }
395 76193d7c 2003-09-30 devnull #endif
396 76193d7c 2003-09-30 devnull 
397 76193d7c 2003-09-30 devnull void
398 76193d7c 2003-09-30 devnull startlex(Rune *s)
399 76193d7c 2003-09-30 devnull {
400 76193d7c 2003-09-30 devnull 	exprp = s;
401 76193d7c 2003-09-30 devnull 	nbra = 0;
402 76193d7c 2003-09-30 devnull }
403 76193d7c 2003-09-30 devnull 
404 76193d7c 2003-09-30 devnull 
405 76193d7c 2003-09-30 devnull int
406 76193d7c 2003-09-30 devnull lex(void){
407 76193d7c 2003-09-30 devnull 	int c= *exprp++;
408 76193d7c 2003-09-30 devnull 
409 76193d7c 2003-09-30 devnull 	switch(c){
410 76193d7c 2003-09-30 devnull 	case '\\':
411 76193d7c 2003-09-30 devnull 		if(*exprp)
412 76193d7c 2003-09-30 devnull 			if((c= *exprp++)=='n')
413 76193d7c 2003-09-30 devnull 				c='\n';
414 76193d7c 2003-09-30 devnull 		break;
415 76193d7c 2003-09-30 devnull 	case 0:
416 76193d7c 2003-09-30 devnull 		c = END;
417 76193d7c 2003-09-30 devnull 		--exprp;	/* In case we come here again */
418 76193d7c 2003-09-30 devnull 		break;
419 76193d7c 2003-09-30 devnull 	case '*':
420 76193d7c 2003-09-30 devnull 		c = STAR;
421 76193d7c 2003-09-30 devnull 		break;
422 76193d7c 2003-09-30 devnull 	case '?':
423 76193d7c 2003-09-30 devnull 		c = QUEST;
424 76193d7c 2003-09-30 devnull 		break;
425 76193d7c 2003-09-30 devnull 	case '+':
426 76193d7c 2003-09-30 devnull 		c = PLUS;
427 76193d7c 2003-09-30 devnull 		break;
428 76193d7c 2003-09-30 devnull 	case '|':
429 76193d7c 2003-09-30 devnull 		c = OR;
430 76193d7c 2003-09-30 devnull 		break;
431 76193d7c 2003-09-30 devnull 	case '.':
432 76193d7c 2003-09-30 devnull 		c = ANY;
433 76193d7c 2003-09-30 devnull 		break;
434 76193d7c 2003-09-30 devnull 	case '(':
435 76193d7c 2003-09-30 devnull 		c = LBRA;
436 76193d7c 2003-09-30 devnull 		break;
437 76193d7c 2003-09-30 devnull 	case ')':
438 76193d7c 2003-09-30 devnull 		c = RBRA;
439 76193d7c 2003-09-30 devnull 		break;
440 76193d7c 2003-09-30 devnull 	case '^':
441 76193d7c 2003-09-30 devnull 		c = BOL;
442 76193d7c 2003-09-30 devnull 		break;
443 76193d7c 2003-09-30 devnull 	case '$':
444 76193d7c 2003-09-30 devnull 		c = EOL;
445 76193d7c 2003-09-30 devnull 		break;
446 76193d7c 2003-09-30 devnull 	case '[':
447 76193d7c 2003-09-30 devnull 		c = CCLASS;
448 76193d7c 2003-09-30 devnull 		bldcclass();
449 76193d7c 2003-09-30 devnull 		break;
450 76193d7c 2003-09-30 devnull 	}
451 76193d7c 2003-09-30 devnull 	return c;
452 76193d7c 2003-09-30 devnull }
453 76193d7c 2003-09-30 devnull 
454 76193d7c 2003-09-30 devnull long
455 76193d7c 2003-09-30 devnull nextrec(void){
456 76193d7c 2003-09-30 devnull 	if(exprp[0]==0 || (exprp[0]=='\\' && exprp[1]==0))
457 76193d7c 2003-09-30 devnull 		regerror(Ebadclass);
458 76193d7c 2003-09-30 devnull 	if(exprp[0] == '\\'){
459 76193d7c 2003-09-30 devnull 		exprp++;
460 76193d7c 2003-09-30 devnull 		if(*exprp=='n'){
461 76193d7c 2003-09-30 devnull 			exprp++;
462 76193d7c 2003-09-30 devnull 			return '\n';
463 76193d7c 2003-09-30 devnull 		}
464 36d9b90c 2010-07-14 rsc 		return *exprp++|QUOTED;
465 76193d7c 2003-09-30 devnull 	}
466 76193d7c 2003-09-30 devnull 	return *exprp++;
467 76193d7c 2003-09-30 devnull }
468 76193d7c 2003-09-30 devnull 
469 76193d7c 2003-09-30 devnull void
470 76193d7c 2003-09-30 devnull bldcclass(void)
471 76193d7c 2003-09-30 devnull {
472 76193d7c 2003-09-30 devnull 	long c1, c2, n, na;
473 76193d7c 2003-09-30 devnull 	Rune *classp;
474 76193d7c 2003-09-30 devnull 
475 76193d7c 2003-09-30 devnull 	classp = emalloc(DCLASS*RUNESIZE);
476 76193d7c 2003-09-30 devnull 	n = 0;
477 76193d7c 2003-09-30 devnull 	na = DCLASS;
478 76193d7c 2003-09-30 devnull 	/* we have already seen the '[' */
479 76193d7c 2003-09-30 devnull 	if(*exprp == '^'){
480 76193d7c 2003-09-30 devnull 		classp[n++] = '\n';	/* don't match newline in negate case */
481 76193d7c 2003-09-30 devnull 		negateclass = TRUE;
482 76193d7c 2003-09-30 devnull 		exprp++;
483 76193d7c 2003-09-30 devnull 	}else
484 76193d7c 2003-09-30 devnull 		negateclass = FALSE;
485 76193d7c 2003-09-30 devnull 	while((c1 = nextrec()) != ']'){
486 76193d7c 2003-09-30 devnull 		if(c1 == '-'){
487 76193d7c 2003-09-30 devnull     Error:
488 76193d7c 2003-09-30 devnull 			free(classp);
489 76193d7c 2003-09-30 devnull 			regerror(Ebadclass);
490 76193d7c 2003-09-30 devnull 		}
491 76193d7c 2003-09-30 devnull 		if(n+4 >= na){		/* 3 runes plus NUL */
492 76193d7c 2003-09-30 devnull 			na += DCLASS;
493 76193d7c 2003-09-30 devnull 			classp = erealloc(classp, na*RUNESIZE);
494 76193d7c 2003-09-30 devnull 		}
495 76193d7c 2003-09-30 devnull 		if(*exprp == '-'){
496 76193d7c 2003-09-30 devnull 			exprp++;	/* eat '-' */
497 76193d7c 2003-09-30 devnull 			if((c2 = nextrec()) == ']')
498 76193d7c 2003-09-30 devnull 				goto Error;
499 0cadb430 2009-09-11 russcox 			classp[n+0] = Runemax;
500 76193d7c 2003-09-30 devnull 			classp[n+1] = c1;
501 76193d7c 2003-09-30 devnull 			classp[n+2] = c2;
502 76193d7c 2003-09-30 devnull 			n += 3;
503 76193d7c 2003-09-30 devnull 		}else
504 36d9b90c 2010-07-14 rsc 			classp[n++] = c1 & ~QUOTED;
505 76193d7c 2003-09-30 devnull 	}
506 76193d7c 2003-09-30 devnull 	classp[n] = 0;
507 76193d7c 2003-09-30 devnull 	if(nclass == Nclass){
508 76193d7c 2003-09-30 devnull 		Nclass += DCLASS;
509 76193d7c 2003-09-30 devnull 		class = erealloc(class, Nclass*sizeof(Rune*));
510 76193d7c 2003-09-30 devnull 	}
511 76193d7c 2003-09-30 devnull 	class[nclass++] = classp;
512 76193d7c 2003-09-30 devnull }
513 76193d7c 2003-09-30 devnull 
514 76193d7c 2003-09-30 devnull int
515 76193d7c 2003-09-30 devnull classmatch(int classno, int c, int negate)
516 76193d7c 2003-09-30 devnull {
517 76193d7c 2003-09-30 devnull 	Rune *p;
518 76193d7c 2003-09-30 devnull 
519 76193d7c 2003-09-30 devnull 	p = class[classno];
520 76193d7c 2003-09-30 devnull 	while(*p){
521 0cadb430 2009-09-11 russcox 		if(*p == Runemax){
522 76193d7c 2003-09-30 devnull 			if(p[1]<=c && c<=p[2])
523 76193d7c 2003-09-30 devnull 				return !negate;
524 76193d7c 2003-09-30 devnull 			p += 3;
525 76193d7c 2003-09-30 devnull 		}else if(*p++ == c)
526 76193d7c 2003-09-30 devnull 			return !negate;
527 76193d7c 2003-09-30 devnull 	}
528 76193d7c 2003-09-30 devnull 	return negate;
529 76193d7c 2003-09-30 devnull }
530 76193d7c 2003-09-30 devnull 
531 76193d7c 2003-09-30 devnull /*
532 2deda14e 2007-12-07 rsc  * Note optimization in addinst:
533 2deda14e 2007-12-07 rsc  * 	*l must be pending when addinst called; if *l has been looked
534 2deda14e 2007-12-07 rsc  *		at already, the optimization is a bug.
535 76193d7c 2003-09-30 devnull  */
536 608a0928 2007-12-07 rsc int
537 608a0928 2007-12-07 rsc addinst(Ilist *l, Inst *inst, Rangeset *sep)
538 608a0928 2007-12-07 rsc {
539 2deda14e 2007-12-07 rsc 	Ilist *p;
540 2deda14e 2007-12-07 rsc 
541 2deda14e 2007-12-07 rsc 	for(p = l; p->inst; p++){
542 2deda14e 2007-12-07 rsc 		if(p->inst==inst){
543 2deda14e 2007-12-07 rsc 			if((sep)->p[0].p1 < p->se.p[0].p1)
544 2deda14e 2007-12-07 rsc 				p->se= *sep;	/* this would be bug */
545 2deda14e 2007-12-07 rsc 			return 0;	/* It's already there */
546 608a0928 2007-12-07 rsc 		}
547 608a0928 2007-12-07 rsc 	}
548 2deda14e 2007-12-07 rsc 	p->inst = inst;
549 2deda14e 2007-12-07 rsc 	p->se= *sep;
550 2deda14e 2007-12-07 rsc 	(p+1)->inst = 0;
551 2deda14e 2007-12-07 rsc 	return 1;
552 76193d7c 2003-09-30 devnull }
553 76193d7c 2003-09-30 devnull 
554 76193d7c 2003-09-30 devnull int
555 76193d7c 2003-09-30 devnull execute(File *f, Posn startp, Posn eof)
556 76193d7c 2003-09-30 devnull {
557 76193d7c 2003-09-30 devnull 	int flag = 0;
558 76193d7c 2003-09-30 devnull 	Inst *inst;
559 76193d7c 2003-09-30 devnull 	Ilist *tlp;
560 76193d7c 2003-09-30 devnull 	Posn p = startp;
561 2deda14e 2007-12-07 rsc 	int nnl = 0, ntl;
562 76193d7c 2003-09-30 devnull 	int c;
563 76193d7c 2003-09-30 devnull 	int wrapped = 0;
564 76193d7c 2003-09-30 devnull 	int startchar = startinst->type<OPERATOR? startinst->type : 0;
565 76193d7c 2003-09-30 devnull 
566 76193d7c 2003-09-30 devnull 	list[0][0].inst = list[1][0].inst = 0;
567 76193d7c 2003-09-30 devnull 	sel.p[0].p1 = -1;
568 76193d7c 2003-09-30 devnull 	/* Execute machine once for each character */
569 76193d7c 2003-09-30 devnull 	for(;;p++){
570 76193d7c 2003-09-30 devnull 	doloop:
571 76193d7c 2003-09-30 devnull 		c = filereadc(f, p);
572 76193d7c 2003-09-30 devnull 		if(p>=eof || c<0){
573 76193d7c 2003-09-30 devnull 			switch(wrapped++){
574 76193d7c 2003-09-30 devnull 			case 0:		/* let loop run one more click */
575 76193d7c 2003-09-30 devnull 			case 2:
576 76193d7c 2003-09-30 devnull 				break;
577 76193d7c 2003-09-30 devnull 			case 1:		/* expired; wrap to beginning */
578 76193d7c 2003-09-30 devnull 				if(sel.p[0].p1>=0 || eof!=INFINITY)
579 76193d7c 2003-09-30 devnull 					goto Return;
580 76193d7c 2003-09-30 devnull 				list[0][0].inst = list[1][0].inst = 0;
581 76193d7c 2003-09-30 devnull 				p = 0;
582 76193d7c 2003-09-30 devnull 				goto doloop;
583 76193d7c 2003-09-30 devnull 			default:
584 76193d7c 2003-09-30 devnull 				goto Return;
585 76193d7c 2003-09-30 devnull 			}
586 2deda14e 2007-12-07 rsc 		}else if(((wrapped && p>=startp) || sel.p[0].p1>0) && nnl==0)
587 76193d7c 2003-09-30 devnull 			break;
588 76193d7c 2003-09-30 devnull 		/* fast check for first char */
589 2deda14e 2007-12-07 rsc 		if(startchar && nnl==0 && c!=startchar)
590 76193d7c 2003-09-30 devnull 			continue;
591 76193d7c 2003-09-30 devnull 		tl = list[flag];
592 76193d7c 2003-09-30 devnull 		nl = list[flag^=1];
593 76193d7c 2003-09-30 devnull 		nl->inst = 0;
594 2deda14e 2007-12-07 rsc 		ntl = nnl;
595 2deda14e 2007-12-07 rsc 		nnl = 0;
596 76193d7c 2003-09-30 devnull 		if(sel.p[0].p1<0 && (!wrapped || p<startp || startp==eof)){
597 76193d7c 2003-09-30 devnull 			/* Add first instruction to this list */
598 c99ef336 2007-06-09 devnull 			sempty.p[0].p1 = p;
599 2deda14e 2007-12-07 rsc 			if(addinst(tl, startinst, &sempty))
600 2deda14e 2007-12-07 rsc 			if(++ntl >= NLIST)
601 76193d7c 2003-09-30 devnull 	Overflow:
602 76193d7c 2003-09-30 devnull 				error(Eoverflow);
603 76193d7c 2003-09-30 devnull 		}
604 76193d7c 2003-09-30 devnull 		/* Execute machine until this list is empty */
605 76193d7c 2003-09-30 devnull 		for(tlp = tl; inst = tlp->inst; tlp++){	/* assignment = */
606 76193d7c 2003-09-30 devnull 	Switchstmt:
607 76193d7c 2003-09-30 devnull 			switch(inst->type){
608 76193d7c 2003-09-30 devnull 			default:	/* regular character */
609 76193d7c 2003-09-30 devnull 				if(inst->type==c){
610 76193d7c 2003-09-30 devnull 	Addinst:
611 2deda14e 2007-12-07 rsc 					if(addinst(nl, inst->next, &tlp->se))
612 2deda14e 2007-12-07 rsc 					if(++nnl >= NLIST)
613 76193d7c 2003-09-30 devnull 						goto Overflow;
614 76193d7c 2003-09-30 devnull 				}
615 76193d7c 2003-09-30 devnull 				break;
616 76193d7c 2003-09-30 devnull 			case LBRA:
617 76193d7c 2003-09-30 devnull 				if(inst->subid>=0)
618 76193d7c 2003-09-30 devnull 					tlp->se.p[inst->subid].p1 = p;
619 76193d7c 2003-09-30 devnull 				inst = inst->next;
620 76193d7c 2003-09-30 devnull 				goto Switchstmt;
621 76193d7c 2003-09-30 devnull 			case RBRA:
622 76193d7c 2003-09-30 devnull 				if(inst->subid>=0)
623 76193d7c 2003-09-30 devnull 					tlp->se.p[inst->subid].p2 = p;
624 76193d7c 2003-09-30 devnull 				inst = inst->next;
625 76193d7c 2003-09-30 devnull 				goto Switchstmt;
626 76193d7c 2003-09-30 devnull 			case ANY:
627 76193d7c 2003-09-30 devnull 				if(c!='\n')
628 76193d7c 2003-09-30 devnull 					goto Addinst;
629 76193d7c 2003-09-30 devnull 				break;
630 76193d7c 2003-09-30 devnull 			case BOL:
631 76193d7c 2003-09-30 devnull 				if(p==0 || filereadc(f, p - 1)=='\n'){
632 76193d7c 2003-09-30 devnull 	Step:
633 76193d7c 2003-09-30 devnull 					inst = inst->next;
634 76193d7c 2003-09-30 devnull 					goto Switchstmt;
635 76193d7c 2003-09-30 devnull 				}
636 76193d7c 2003-09-30 devnull 				break;
637 76193d7c 2003-09-30 devnull 			case EOL:
638 76193d7c 2003-09-30 devnull 				if(c == '\n')
639 76193d7c 2003-09-30 devnull 					goto Step;
640 76193d7c 2003-09-30 devnull 				break;
641 76193d7c 2003-09-30 devnull 			case CCLASS:
642 76193d7c 2003-09-30 devnull 				if(c>=0 && classmatch(inst->rclass, c, 0))
643 76193d7c 2003-09-30 devnull 					goto Addinst;
644 76193d7c 2003-09-30 devnull 				break;
645 76193d7c 2003-09-30 devnull 			case NCCLASS:
646 76193d7c 2003-09-30 devnull 				if(c>=0 && classmatch(inst->rclass, c, 1))
647 76193d7c 2003-09-30 devnull 					goto Addinst;
648 76193d7c 2003-09-30 devnull 				break;
649 76193d7c 2003-09-30 devnull 			case OR:
650 2deda14e 2007-12-07 rsc 				/* evaluate right choice later */
651 2deda14e 2007-12-07 rsc 				if(addinst(tl, inst->right, &tlp->se))
652 2deda14e 2007-12-07 rsc 				if(++ntl >= NLIST)
653 2deda14e 2007-12-07 rsc 					goto Overflow;
654 2deda14e 2007-12-07 rsc 				/* efficiency: advance and re-evaluate */
655 2deda14e 2007-12-07 rsc 				inst = inst->left;
656 2deda14e 2007-12-07 rsc 				goto Switchstmt;
657 76193d7c 2003-09-30 devnull 			case END:	/* Match! */
658 76193d7c 2003-09-30 devnull 				tlp->se.p[0].p2 = p;
659 76193d7c 2003-09-30 devnull 				newmatch(&tlp->se);
660 76193d7c 2003-09-30 devnull 				break;
661 76193d7c 2003-09-30 devnull 			}
662 76193d7c 2003-09-30 devnull 		}
663 76193d7c 2003-09-30 devnull 	}
664 76193d7c 2003-09-30 devnull     Return:
665 76193d7c 2003-09-30 devnull 	return sel.p[0].p1>=0;
666 76193d7c 2003-09-30 devnull }
667 76193d7c 2003-09-30 devnull 
668 76193d7c 2003-09-30 devnull void
669 76193d7c 2003-09-30 devnull newmatch(Rangeset *sp)
670 76193d7c 2003-09-30 devnull {
671 76193d7c 2003-09-30 devnull 	int i;
672 76193d7c 2003-09-30 devnull 
673 76193d7c 2003-09-30 devnull 	if(sel.p[0].p1<0 || sp->p[0].p1<sel.p[0].p1 ||
674 76193d7c 2003-09-30 devnull 	   (sp->p[0].p1==sel.p[0].p1 && sp->p[0].p2>sel.p[0].p2))
675 76193d7c 2003-09-30 devnull 		for(i = 0; i<NSUBEXP; i++)
676 76193d7c 2003-09-30 devnull 			sel.p[i] = sp->p[i];
677 76193d7c 2003-09-30 devnull }
678 76193d7c 2003-09-30 devnull 
679 76193d7c 2003-09-30 devnull int
680 76193d7c 2003-09-30 devnull bexecute(File *f, Posn startp)
681 76193d7c 2003-09-30 devnull {
682 76193d7c 2003-09-30 devnull 	int flag = 0;
683 76193d7c 2003-09-30 devnull 	Inst *inst;
684 76193d7c 2003-09-30 devnull 	Ilist *tlp;
685 76193d7c 2003-09-30 devnull 	Posn p = startp;
686 2deda14e 2007-12-07 rsc 	int nnl = 0, ntl;
687 76193d7c 2003-09-30 devnull 	int c;
688 76193d7c 2003-09-30 devnull 	int wrapped = 0;
689 76193d7c 2003-09-30 devnull 	int startchar = bstartinst->type<OPERATOR? bstartinst->type : 0;
690 76193d7c 2003-09-30 devnull 
691 76193d7c 2003-09-30 devnull 	list[0][0].inst = list[1][0].inst = 0;
692 76193d7c 2003-09-30 devnull 	sel.p[0].p1= -1;
693 76193d7c 2003-09-30 devnull 	/* Execute machine once for each character, including terminal NUL */
694 76193d7c 2003-09-30 devnull 	for(;;--p){
695 76193d7c 2003-09-30 devnull 	doloop:
696 76193d7c 2003-09-30 devnull 		if((c = filereadc(f, p - 1))==-1){
697 76193d7c 2003-09-30 devnull 			switch(wrapped++){
698 76193d7c 2003-09-30 devnull 			case 0:		/* let loop run one more click */
699 76193d7c 2003-09-30 devnull 			case 2:
700 76193d7c 2003-09-30 devnull 				break;
701 76193d7c 2003-09-30 devnull 			case 1:		/* expired; wrap to end */
702 76193d7c 2003-09-30 devnull 				if(sel.p[0].p1>=0)
703 76193d7c 2003-09-30 devnull 			case 3:
704 76193d7c 2003-09-30 devnull 					goto Return;
705 76193d7c 2003-09-30 devnull 				list[0][0].inst = list[1][0].inst = 0;
706 522b0689 2003-09-30 devnull 				p = f->b.nc;
707 76193d7c 2003-09-30 devnull 				goto doloop;
708 76193d7c 2003-09-30 devnull 			default:
709 76193d7c 2003-09-30 devnull 				goto Return;
710 76193d7c 2003-09-30 devnull 			}
711 2deda14e 2007-12-07 rsc 		}else if(((wrapped && p<=startp) || sel.p[0].p1>0) && nnl==0)
712 76193d7c 2003-09-30 devnull 			break;
713 76193d7c 2003-09-30 devnull 		/* fast check for first char */
714 2deda14e 2007-12-07 rsc 		if(startchar && nnl==0 && c!=startchar)
715 76193d7c 2003-09-30 devnull 			continue;
716 76193d7c 2003-09-30 devnull 		tl = list[flag];
717 76193d7c 2003-09-30 devnull 		nl = list[flag^=1];
718 76193d7c 2003-09-30 devnull 		nl->inst = 0;
719 2deda14e 2007-12-07 rsc 		ntl = nnl;
720 2deda14e 2007-12-07 rsc 		nnl = 0;
721 76193d7c 2003-09-30 devnull 		if(sel.p[0].p1<0 && (!wrapped || p>startp)){
722 76193d7c 2003-09-30 devnull 			/* Add first instruction to this list */
723 2deda14e 2007-12-07 rsc 			/* the minus is so the optimizations in addinst work */
724 2deda14e 2007-12-07 rsc 			sempty.p[0].p1 = -p;
725 2deda14e 2007-12-07 rsc 			if(addinst(tl, bstartinst, &sempty))
726 2deda14e 2007-12-07 rsc 			if(++ntl >= NLIST)
727 76193d7c 2003-09-30 devnull 	Overflow:
728 76193d7c 2003-09-30 devnull 				error(Eoverflow);
729 76193d7c 2003-09-30 devnull 		}
730 76193d7c 2003-09-30 devnull 		/* Execute machine until this list is empty */
731 76193d7c 2003-09-30 devnull 		for(tlp = tl; inst = tlp->inst; tlp++){	/* assignment = */
732 76193d7c 2003-09-30 devnull 	Switchstmt:
733 76193d7c 2003-09-30 devnull 			switch(inst->type){
734 76193d7c 2003-09-30 devnull 			default:	/* regular character */
735 76193d7c 2003-09-30 devnull 				if(inst->type == c){
736 76193d7c 2003-09-30 devnull 	Addinst:
737 2deda14e 2007-12-07 rsc 					if(addinst(nl, inst->next, &tlp->se))
738 2deda14e 2007-12-07 rsc 					if(++nnl >= NLIST)
739 76193d7c 2003-09-30 devnull 						goto Overflow;
740 76193d7c 2003-09-30 devnull 				}
741 76193d7c 2003-09-30 devnull 				break;
742 76193d7c 2003-09-30 devnull 			case LBRA:
743 76193d7c 2003-09-30 devnull 				if(inst->subid>=0)
744 76193d7c 2003-09-30 devnull 					tlp->se.p[inst->subid].p1 = p;
745 76193d7c 2003-09-30 devnull 				inst = inst->next;
746 76193d7c 2003-09-30 devnull 				goto Switchstmt;
747 76193d7c 2003-09-30 devnull 			case RBRA:
748 76193d7c 2003-09-30 devnull 				if(inst->subid >= 0)
749 76193d7c 2003-09-30 devnull 					tlp->se.p[inst->subid].p2 = p;
750 76193d7c 2003-09-30 devnull 				inst = inst->next;
751 76193d7c 2003-09-30 devnull 				goto Switchstmt;
752 76193d7c 2003-09-30 devnull 			case ANY:
753 76193d7c 2003-09-30 devnull 				if(c != '\n')
754 76193d7c 2003-09-30 devnull 					goto Addinst;
755 76193d7c 2003-09-30 devnull 				break;
756 76193d7c 2003-09-30 devnull 			case BOL:
757 76193d7c 2003-09-30 devnull 				if(c=='\n' || p==0){
758 76193d7c 2003-09-30 devnull 	Step:
759 76193d7c 2003-09-30 devnull 					inst = inst->next;
760 76193d7c 2003-09-30 devnull 					goto Switchstmt;
761 76193d7c 2003-09-30 devnull 				}
762 76193d7c 2003-09-30 devnull 				break;
763 76193d7c 2003-09-30 devnull 			case EOL:
764 522b0689 2003-09-30 devnull 				if(p==f->b.nc || filereadc(f, p)=='\n')
765 76193d7c 2003-09-30 devnull 					goto Step;
766 76193d7c 2003-09-30 devnull 				break;
767 76193d7c 2003-09-30 devnull 			case CCLASS:
768 76193d7c 2003-09-30 devnull 				if(c>=0 && classmatch(inst->rclass, c, 0))
769 76193d7c 2003-09-30 devnull 					goto Addinst;
770 76193d7c 2003-09-30 devnull 				break;
771 76193d7c 2003-09-30 devnull 			case NCCLASS:
772 76193d7c 2003-09-30 devnull 				if(c>=0 && classmatch(inst->rclass, c, 1))
773 76193d7c 2003-09-30 devnull 					goto Addinst;
774 76193d7c 2003-09-30 devnull 				break;
775 76193d7c 2003-09-30 devnull 			case OR:
776 2deda14e 2007-12-07 rsc 				/* evaluate right choice later */
777 3a9401ae 2008-01-30 rsc 				if(addinst(tlp, inst->right, &tlp->se))
778 2deda14e 2007-12-07 rsc 				if(++ntl >= NLIST)
779 2deda14e 2007-12-07 rsc 					goto Overflow;
780 2deda14e 2007-12-07 rsc 				/* efficiency: advance and re-evaluate */
781 2deda14e 2007-12-07 rsc 				inst = inst->left;
782 2deda14e 2007-12-07 rsc 				goto Switchstmt;
783 76193d7c 2003-09-30 devnull 			case END:	/* Match! */
784 2deda14e 2007-12-07 rsc 				tlp->se.p[0].p1 = -tlp->se.p[0].p1; /* minus sign */
785 76193d7c 2003-09-30 devnull 				tlp->se.p[0].p2 = p;
786 76193d7c 2003-09-30 devnull 				bnewmatch(&tlp->se);
787 76193d7c 2003-09-30 devnull 				break;
788 76193d7c 2003-09-30 devnull 			}
789 76193d7c 2003-09-30 devnull 		}
790 76193d7c 2003-09-30 devnull 	}
791 76193d7c 2003-09-30 devnull     Return:
792 76193d7c 2003-09-30 devnull 	return sel.p[0].p1>=0;
793 76193d7c 2003-09-30 devnull }
794 76193d7c 2003-09-30 devnull 
795 76193d7c 2003-09-30 devnull void
796 76193d7c 2003-09-30 devnull bnewmatch(Rangeset *sp)
797 76193d7c 2003-09-30 devnull {
798 76193d7c 2003-09-30 devnull         int  i;
799 76193d7c 2003-09-30 devnull         if(sel.p[0].p1<0 || sp->p[0].p1>sel.p[0].p2 || (sp->p[0].p1==sel.p[0].p2 && sp->p[0].p2<sel.p[0].p1))
800 76193d7c 2003-09-30 devnull                 for(i = 0; i<NSUBEXP; i++){       /* note the reversal; p1<=p2 */
801 76193d7c 2003-09-30 devnull                         sel.p[i].p1 = sp->p[i].p2;
802 76193d7c 2003-09-30 devnull                         sel.p[i].p2 = sp->p[i].p1;
803 76193d7c 2003-09-30 devnull                 }
804 76193d7c 2003-09-30 devnull }