op public repos

Blame

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