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