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