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"
14 b3994ec5 2003-12-11 devnull Rangeset sel;
15 b3994ec5 2003-12-11 devnull Rune *lastregexp;
18 b3994ec5 2003-12-11 devnull * Machine Information
20 b3994ec5 2003-12-11 devnull typedef struct Inst Inst;
21 b3994ec5 2003-12-11 devnull struct Inst
23 b3994ec5 2003-12-11 devnull uint type; /* < 0x10000 ==> literal, otherwise action */
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;
32 b3994ec5 2003-12-11 devnull Inst *left;
33 b3994ec5 2003-12-11 devnull Inst *next;
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*) */
44 b3994ec5 2003-12-11 devnull typedef struct Ilist Ilist;
45 b3994ec5 2003-12-11 devnull struct Ilist
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 */
52 c99ef336 2007-06-09 devnull #define NLIST 127
54 b3994ec5 2003-12-11 devnull Ilist *tl, *nl; /* This list, next list */
55 c99ef336 2007-06-09 devnull Ilist list[2][NLIST+1]; /* +1 for trailing null */
56 b3994ec5 2003-12-11 devnull static Rangeset sempty;
59 b3994ec5 2003-12-11 devnull * Actions and Tokens
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
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 */
81 b3994ec5 2003-12-11 devnull #define ISATOR 0x10000
82 b3994ec5 2003-12-11 devnull #define ISAND 0x20000
85 b3994ec5 2003-12-11 devnull * Parser Information
87 b3994ec5 2003-12-11 devnull typedef struct Node Node;
88 b3994ec5 2003-12-11 devnull struct Node
90 b3994ec5 2003-12-11 devnull Inst *first;
91 b3994ec5 2003-12-11 devnull Inst *last;
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;
112 c99ef336 2007-06-09 devnull int 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);
128 b3994ec5 2003-12-11 devnull rxinit(void)
130 b3994ec5 2003-12-11 devnull rechan = chancreate(sizeof(Inst*), 0);
131 334cb1e9 2004-12-27 devnull chansetname(rechan, "rechan");
132 b3994ec5 2003-12-11 devnull lastregexp = runemalloc(1);
136 b3994ec5 2003-12-11 devnull regerror(char *e)
138 b3994ec5 2003-12-11 devnull lastregexp[0] = 0;
139 b3994ec5 2003-12-11 devnull warning(nil, "regexp: %s\n", e);
140 b3994ec5 2003-12-11 devnull sendp(rechan, nil);
141 b3994ec5 2003-12-11 devnull threadexits(nil);
145 b3994ec5 2003-12-11 devnull newinst(int t)
147 b3994ec5 2003-12-11 devnull if(progp >= &program[NPROG])
148 b3994ec5 2003-12-11 devnull regerror("expression too long");
149 b3994ec5 2003-12-11 devnull progp->type = t;
150 b3994ec5 2003-12-11 devnull progp->u1.left = nil;
151 b3994ec5 2003-12-11 devnull progp->u.right = nil;
152 b3994ec5 2003-12-11 devnull return progp++;
156 b3994ec5 2003-12-11 devnull realcompile(void *arg)
158 b3994ec5 2003-12-11 devnull int token;
159 b3994ec5 2003-12-11 devnull Rune *s;
161 b3994ec5 2003-12-11 devnull threadsetname("regcomp");
162 b3994ec5 2003-12-11 devnull s = arg;
163 b3994ec5 2003-12-11 devnull startlex(s);
164 b3994ec5 2003-12-11 devnull atorp = atorstack;
165 b3994ec5 2003-12-11 devnull andp = andstack;
166 b3994ec5 2003-12-11 devnull subidp = subidstack;
167 b3994ec5 2003-12-11 devnull cursubid = 0;
168 b3994ec5 2003-12-11 devnull lastwasand = FALSE;
169 b3994ec5 2003-12-11 devnull /* Start with a low priority operator to prime parser */
170 b3994ec5 2003-12-11 devnull pushator(START-1);
171 b3994ec5 2003-12-11 devnull while((token=lex()) != END){
172 b3994ec5 2003-12-11 devnull if((token&ISATOR) == OPERATOR)
173 b3994ec5 2003-12-11 devnull operator(token);
175 b3994ec5 2003-12-11 devnull operand(token);
177 b3994ec5 2003-12-11 devnull /* Close with a low priority operator */
178 b3994ec5 2003-12-11 devnull evaluntil(START);
179 b3994ec5 2003-12-11 devnull /* Force END */
180 b3994ec5 2003-12-11 devnull operand(END);
181 b3994ec5 2003-12-11 devnull evaluntil(START);
182 b3994ec5 2003-12-11 devnull if(nbra)
183 b3994ec5 2003-12-11 devnull regerror("unmatched `('");
184 b3994ec5 2003-12-11 devnull --andp; /* points to first and only operand */
185 b3994ec5 2003-12-11 devnull sendp(rechan, andp->first);
186 b3994ec5 2003-12-11 devnull threadexits(nil);
189 b3994ec5 2003-12-11 devnull /* r is null terminated */
191 b3994ec5 2003-12-11 devnull rxcompile(Rune *r)
193 b3994ec5 2003-12-11 devnull int i, nr;
194 b3994ec5 2003-12-11 devnull Inst *oprogp;
196 b3994ec5 2003-12-11 devnull nr = runestrlen(r)+1;
197 b3994ec5 2003-12-11 devnull if(runeeq(lastregexp, runestrlen(lastregexp)+1, r, nr)==TRUE)
198 b3994ec5 2003-12-11 devnull return TRUE;
199 b3994ec5 2003-12-11 devnull lastregexp[0] = 0;
200 b3994ec5 2003-12-11 devnull for(i=0; i<nclass; i++)
201 b3994ec5 2003-12-11 devnull free(class[i]);
202 b3994ec5 2003-12-11 devnull nclass = 0;
203 b3994ec5 2003-12-11 devnull progp = program;
204 b3994ec5 2003-12-11 devnull backwards = FALSE;
205 b3994ec5 2003-12-11 devnull bstartinst = nil;
206 b3994ec5 2003-12-11 devnull threadcreate(realcompile, r, STACK);
207 b3994ec5 2003-12-11 devnull startinst = recvp(rechan);
208 b3994ec5 2003-12-11 devnull if(startinst == nil)
209 b3994ec5 2003-12-11 devnull return FALSE;
210 b3994ec5 2003-12-11 devnull optimize(program);
211 b3994ec5 2003-12-11 devnull oprogp = progp;
212 b3994ec5 2003-12-11 devnull backwards = TRUE;
213 b3994ec5 2003-12-11 devnull threadcreate(realcompile, r, STACK);
214 b3994ec5 2003-12-11 devnull bstartinst = recvp(rechan);
215 b3994ec5 2003-12-11 devnull if(bstartinst == nil)
216 b3994ec5 2003-12-11 devnull return FALSE;
217 b3994ec5 2003-12-11 devnull optimize(oprogp);
218 b3994ec5 2003-12-11 devnull lastregexp = runerealloc(lastregexp, nr);
219 b3994ec5 2003-12-11 devnull runemove(lastregexp, r, nr);
220 b3994ec5 2003-12-11 devnull return TRUE;
224 b3994ec5 2003-12-11 devnull operand(int t)
226 b3994ec5 2003-12-11 devnull Inst *i;
227 b3994ec5 2003-12-11 devnull if(lastwasand)
228 b3994ec5 2003-12-11 devnull operator(CAT); /* catenate is implicit */
229 b3994ec5 2003-12-11 devnull i = newinst(t);
230 b3994ec5 2003-12-11 devnull if(t == CCLASS){
231 b3994ec5 2003-12-11 devnull if(negateclass)
232 b3994ec5 2003-12-11 devnull i->type = NCCLASS; /* UGH */
233 b3994ec5 2003-12-11 devnull i->u.class = nclass-1; /* UGH */
235 b3994ec5 2003-12-11 devnull pushand(i, i);
236 b3994ec5 2003-12-11 devnull lastwasand = TRUE;
240 b3994ec5 2003-12-11 devnull operator(int t)
242 b3994ec5 2003-12-11 devnull if(t==RBRA && --nbra<0)
243 b3994ec5 2003-12-11 devnull regerror("unmatched `)'");
244 b3994ec5 2003-12-11 devnull if(t==LBRA){
245 b3994ec5 2003-12-11 devnull cursubid++; /* silently ignored */
247 b3994ec5 2003-12-11 devnull if(lastwasand)
248 b3994ec5 2003-12-11 devnull operator(CAT);
250 b3994ec5 2003-12-11 devnull evaluntil(t);
251 b3994ec5 2003-12-11 devnull if(t!=RBRA)
252 b3994ec5 2003-12-11 devnull pushator(t);
253 b3994ec5 2003-12-11 devnull lastwasand = FALSE;
254 b3994ec5 2003-12-11 devnull if(t==STAR || t==QUEST || t==PLUS || t==RBRA)
255 b3994ec5 2003-12-11 devnull lastwasand = TRUE; /* these look like operands */
259 b3994ec5 2003-12-11 devnull pushand(Inst *f, Inst *l)
261 b3994ec5 2003-12-11 devnull if(andp >= &andstack[NSTACK])
262 b3994ec5 2003-12-11 devnull error("operand stack overflow");
263 b3994ec5 2003-12-11 devnull andp->first = f;
264 b3994ec5 2003-12-11 devnull andp->last = l;
269 b3994ec5 2003-12-11 devnull pushator(int t)
271 b3994ec5 2003-12-11 devnull if(atorp >= &atorstack[NSTACK])
272 b3994ec5 2003-12-11 devnull error("operator stack overflow");
273 b3994ec5 2003-12-11 devnull *atorp++=t;
274 b3994ec5 2003-12-11 devnull if(cursubid >= NRange)
275 b3994ec5 2003-12-11 devnull *subidp++= -1;
277 b3994ec5 2003-12-11 devnull *subidp++=cursubid;
281 b3994ec5 2003-12-11 devnull popand(int op)
283 b3994ec5 2003-12-11 devnull char buf[64];
285 b3994ec5 2003-12-11 devnull if(andp <= &andstack[0])
287 b3994ec5 2003-12-11 devnull sprint(buf, "missing operand for %c", op);
288 b3994ec5 2003-12-11 devnull regerror(buf);
290 b3994ec5 2003-12-11 devnull regerror("malformed regexp");
291 b3994ec5 2003-12-11 devnull return --andp;
295 b3994ec5 2003-12-11 devnull popator()
297 b3994ec5 2003-12-11 devnull if(atorp <= &atorstack[0])
298 b3994ec5 2003-12-11 devnull error("operator stack underflow");
299 b3994ec5 2003-12-11 devnull --subidp;
300 b3994ec5 2003-12-11 devnull return *--atorp;
304 b3994ec5 2003-12-11 devnull evaluntil(int pri)
306 b3994ec5 2003-12-11 devnull Node *op1, *op2, *t;
307 b3994ec5 2003-12-11 devnull Inst *inst1, *inst2;
309 b3994ec5 2003-12-11 devnull while(pri==RBRA || atorp[-1]>=pri){
310 b3994ec5 2003-12-11 devnull switch(popator()){
311 b3994ec5 2003-12-11 devnull case LBRA:
312 b3994ec5 2003-12-11 devnull op1 = popand('(');
313 b3994ec5 2003-12-11 devnull inst2 = newinst(RBRA);
314 b3994ec5 2003-12-11 devnull inst2->u.subid = *subidp;
315 b3994ec5 2003-12-11 devnull op1->last->u1.next = inst2;
316 b3994ec5 2003-12-11 devnull inst1 = newinst(LBRA);
317 b3994ec5 2003-12-11 devnull inst1->u.subid = *subidp;
318 b3994ec5 2003-12-11 devnull inst1->u1.next = op1->first;
319 b3994ec5 2003-12-11 devnull pushand(inst1, inst2);
320 b3994ec5 2003-12-11 devnull return; /* must have been RBRA */
321 b3994ec5 2003-12-11 devnull default:
322 b3994ec5 2003-12-11 devnull error("unknown regexp operator");
324 b3994ec5 2003-12-11 devnull case OR:
325 b3994ec5 2003-12-11 devnull op2 = popand('|');
326 b3994ec5 2003-12-11 devnull op1 = popand('|');
327 b3994ec5 2003-12-11 devnull inst2 = newinst(NOP);
328 b3994ec5 2003-12-11 devnull op2->last->u1.next = inst2;
329 b3994ec5 2003-12-11 devnull op1->last->u1.next = inst2;
330 b3994ec5 2003-12-11 devnull inst1 = newinst(OR);
331 b3994ec5 2003-12-11 devnull inst1->u.right = op1->first;
332 b3994ec5 2003-12-11 devnull inst1->u1.left = op2->first;
333 b3994ec5 2003-12-11 devnull pushand(inst1, inst2);
335 b3994ec5 2003-12-11 devnull case CAT:
336 b3994ec5 2003-12-11 devnull op2 = popand(0);
337 b3994ec5 2003-12-11 devnull op1 = popand(0);
338 b3994ec5 2003-12-11 devnull if(backwards && op2->first->type!=END){
339 b3994ec5 2003-12-11 devnull t = op1;
340 b3994ec5 2003-12-11 devnull op1 = op2;
341 b3994ec5 2003-12-11 devnull op2 = t;
343 b3994ec5 2003-12-11 devnull op1->last->u1.next = op2->first;
344 b3994ec5 2003-12-11 devnull pushand(op1->first, op2->last);
346 b3994ec5 2003-12-11 devnull case STAR:
347 b3994ec5 2003-12-11 devnull op2 = popand('*');
348 b3994ec5 2003-12-11 devnull inst1 = newinst(OR);
349 b3994ec5 2003-12-11 devnull op2->last->u1.next = inst1;
350 b3994ec5 2003-12-11 devnull inst1->u.right = op2->first;
351 b3994ec5 2003-12-11 devnull pushand(inst1, inst1);
353 b3994ec5 2003-12-11 devnull case PLUS:
354 b3994ec5 2003-12-11 devnull op2 = popand('+');
355 b3994ec5 2003-12-11 devnull inst1 = newinst(OR);
356 b3994ec5 2003-12-11 devnull op2->last->u1.next = inst1;
357 b3994ec5 2003-12-11 devnull inst1->u.right = op2->first;
358 b3994ec5 2003-12-11 devnull pushand(op2->first, inst1);
360 b3994ec5 2003-12-11 devnull case QUEST:
361 b3994ec5 2003-12-11 devnull op2 = popand('?');
362 b3994ec5 2003-12-11 devnull inst1 = newinst(OR);
363 b3994ec5 2003-12-11 devnull inst2 = newinst(NOP);
364 b3994ec5 2003-12-11 devnull inst1->u1.left = inst2;
365 b3994ec5 2003-12-11 devnull inst1->u.right = op2->first;
366 b3994ec5 2003-12-11 devnull op2->last->u1.next = inst2;
367 b3994ec5 2003-12-11 devnull pushand(inst1, inst2);
375 b3994ec5 2003-12-11 devnull optimize(Inst *start)
377 b3994ec5 2003-12-11 devnull Inst *inst, *target;
379 b3994ec5 2003-12-11 devnull for(inst=start; inst->type!=END; inst++){
380 b3994ec5 2003-12-11 devnull target = inst->u1.next;
381 b3994ec5 2003-12-11 devnull while(target->type == NOP)
382 b3994ec5 2003-12-11 devnull target = target->u1.next;
383 b3994ec5 2003-12-11 devnull inst->u1.next = target;
388 b3994ec5 2003-12-11 devnull startlex(Rune *s)
390 b3994ec5 2003-12-11 devnull exprp = s;
391 b3994ec5 2003-12-11 devnull nbra = 0;
396 b3994ec5 2003-12-11 devnull lex(void){
399 b3994ec5 2003-12-11 devnull c = *exprp++;
400 b3994ec5 2003-12-11 devnull switch(c){
401 b3994ec5 2003-12-11 devnull case '\\':
402 b3994ec5 2003-12-11 devnull if(*exprp)
403 b3994ec5 2003-12-11 devnull if((c= *exprp++)=='n')
407 b3994ec5 2003-12-11 devnull c = END;
408 b3994ec5 2003-12-11 devnull --exprp; /* In case we come here again */
410 b3994ec5 2003-12-11 devnull case '*':
411 b3994ec5 2003-12-11 devnull c = STAR;
413 b3994ec5 2003-12-11 devnull case '?':
414 b3994ec5 2003-12-11 devnull c = QUEST;
416 b3994ec5 2003-12-11 devnull case '+':
417 b3994ec5 2003-12-11 devnull c = PLUS;
419 b3994ec5 2003-12-11 devnull case '|':
422 b3994ec5 2003-12-11 devnull case '.':
423 b3994ec5 2003-12-11 devnull c = ANY;
425 b3994ec5 2003-12-11 devnull case '(':
426 b3994ec5 2003-12-11 devnull c = LBRA;
428 b3994ec5 2003-12-11 devnull case ')':
429 b3994ec5 2003-12-11 devnull c = RBRA;
431 b3994ec5 2003-12-11 devnull case '^':
432 b3994ec5 2003-12-11 devnull c = BOL;
434 b3994ec5 2003-12-11 devnull case '$':
435 b3994ec5 2003-12-11 devnull c = EOL;
437 b3994ec5 2003-12-11 devnull case '[':
438 b3994ec5 2003-12-11 devnull c = CCLASS;
439 b3994ec5 2003-12-11 devnull bldcclass();
442 b3994ec5 2003-12-11 devnull return c;
446 b3994ec5 2003-12-11 devnull nextrec(void)
448 b3994ec5 2003-12-11 devnull if(exprp[0]==0 || (exprp[0]=='\\' && exprp[1]==0))
449 b3994ec5 2003-12-11 devnull regerror("malformed `[]'");
450 b3994ec5 2003-12-11 devnull if(exprp[0] == '\\'){
451 b3994ec5 2003-12-11 devnull exprp++;
452 b3994ec5 2003-12-11 devnull if(*exprp=='n'){
453 b3994ec5 2003-12-11 devnull exprp++;
454 b3994ec5 2003-12-11 devnull return '\n';
456 b3994ec5 2003-12-11 devnull return *exprp++|0x10000;
458 b3994ec5 2003-12-11 devnull return *exprp++;
462 b3994ec5 2003-12-11 devnull bldcclass(void)
464 b3994ec5 2003-12-11 devnull int c1, c2, n, na;
465 b3994ec5 2003-12-11 devnull Rune *classp;
467 b3994ec5 2003-12-11 devnull classp = runemalloc(DCLASS);
469 b3994ec5 2003-12-11 devnull na = DCLASS;
470 b3994ec5 2003-12-11 devnull /* we have already seen the '[' */
471 b3994ec5 2003-12-11 devnull if(*exprp == '^'){
472 b3994ec5 2003-12-11 devnull classp[n++] = '\n'; /* don't match newline in negate case */
473 b3994ec5 2003-12-11 devnull negateclass = TRUE;
474 b3994ec5 2003-12-11 devnull exprp++;
476 b3994ec5 2003-12-11 devnull negateclass = FALSE;
477 b3994ec5 2003-12-11 devnull while((c1 = nextrec()) != ']'){
478 b3994ec5 2003-12-11 devnull if(c1 == '-'){
480 b3994ec5 2003-12-11 devnull free(classp);
481 b3994ec5 2003-12-11 devnull regerror("malformed `[]'");
483 b3994ec5 2003-12-11 devnull if(n+4 >= na){ /* 3 runes plus NUL */
484 b3994ec5 2003-12-11 devnull na += DCLASS;
485 b3994ec5 2003-12-11 devnull classp = runerealloc(classp, na);
487 b3994ec5 2003-12-11 devnull if(*exprp == '-'){
488 b3994ec5 2003-12-11 devnull exprp++; /* eat '-' */
489 b3994ec5 2003-12-11 devnull if((c2 = nextrec()) == ']')
490 b3994ec5 2003-12-11 devnull goto Error;
491 b3994ec5 2003-12-11 devnull classp[n+0] = 0xFFFF;
492 b3994ec5 2003-12-11 devnull classp[n+1] = c1;
493 b3994ec5 2003-12-11 devnull classp[n+2] = c2;
496 b3994ec5 2003-12-11 devnull classp[n++] = c1;
498 b3994ec5 2003-12-11 devnull classp[n] = 0;
499 b3994ec5 2003-12-11 devnull if(nclass == Nclass){
500 b3994ec5 2003-12-11 devnull Nclass += DCLASS;
501 b3994ec5 2003-12-11 devnull class = realloc(class, Nclass*sizeof(Rune*));
503 b3994ec5 2003-12-11 devnull class[nclass++] = classp;
507 b3994ec5 2003-12-11 devnull classmatch(int classno, int c, int negate)
509 b3994ec5 2003-12-11 devnull Rune *p;
511 b3994ec5 2003-12-11 devnull p = class[classno];
512 b3994ec5 2003-12-11 devnull while(*p){
513 b3994ec5 2003-12-11 devnull if(*p == 0xFFFF){
514 b3994ec5 2003-12-11 devnull if(p[1]<=c && c<=p[2])
515 b3994ec5 2003-12-11 devnull return !negate;
517 b3994ec5 2003-12-11 devnull }else if(*p++ == c)
518 b3994ec5 2003-12-11 devnull return !negate;
520 b3994ec5 2003-12-11 devnull return negate;
524 b3994ec5 2003-12-11 devnull * Note optimization in addinst:
525 b3994ec5 2003-12-11 devnull * *l must be pending when addinst called; if *l has been looked
526 b3994ec5 2003-12-11 devnull * at already, the optimization is a bug.
529 b3994ec5 2003-12-11 devnull addinst(Ilist *l, Inst *inst, Rangeset *sep)
531 b3994ec5 2003-12-11 devnull Ilist *p;
533 b3994ec5 2003-12-11 devnull for(p = l; p->inst; p++){
534 b3994ec5 2003-12-11 devnull if(p->inst==inst){
535 b3994ec5 2003-12-11 devnull if((sep)->r[0].q0 < p->se.r[0].q0)
536 b3994ec5 2003-12-11 devnull p->se= *sep; /* this would be bug */
537 c99ef336 2007-06-09 devnull return 0; /* It's already there */
540 b3994ec5 2003-12-11 devnull p->inst = inst;
541 b3994ec5 2003-12-11 devnull p->se= *sep;
542 b3994ec5 2003-12-11 devnull (p+1)->inst = nil;
543 c99ef336 2007-06-09 devnull return 1;
547 b3994ec5 2003-12-11 devnull rxnull(void)
549 b3994ec5 2003-12-11 devnull return startinst==nil || bstartinst==nil;
552 b3994ec5 2003-12-11 devnull /* either t!=nil or r!=nil, and we match the string in the appropriate place */
554 b3994ec5 2003-12-11 devnull rxexecute(Text *t, Rune *r, uint startp, uint eof, Rangeset *rp)
556 b3994ec5 2003-12-11 devnull int flag;
557 b3994ec5 2003-12-11 devnull Inst *inst;
558 b3994ec5 2003-12-11 devnull Ilist *tlp;
560 b3994ec5 2003-12-11 devnull int nnl, ntl;
561 b3994ec5 2003-12-11 devnull int nc, c;
562 b3994ec5 2003-12-11 devnull int wrapped;
563 b3994ec5 2003-12-11 devnull int startchar;
565 b3994ec5 2003-12-11 devnull flag = 0;
566 b3994ec5 2003-12-11 devnull p = startp;
567 b3994ec5 2003-12-11 devnull startchar = 0;
568 b3994ec5 2003-12-11 devnull wrapped = 0;
569 b3994ec5 2003-12-11 devnull nnl = 0;
570 b3994ec5 2003-12-11 devnull if(startinst->type<OPERATOR)
571 b3994ec5 2003-12-11 devnull startchar = startinst->type;
572 b3994ec5 2003-12-11 devnull list[0][0].inst = list[1][0].inst = nil;
573 b3994ec5 2003-12-11 devnull sel.r[0].q0 = -1;
574 b3994ec5 2003-12-11 devnull if(t != nil)
575 b3994ec5 2003-12-11 devnull nc = t->file->b.nc;
577 b3994ec5 2003-12-11 devnull nc = runestrlen(r);
578 b3994ec5 2003-12-11 devnull /* Execute machine once for each character */
579 b3994ec5 2003-12-11 devnull for(;;p++){
581 b3994ec5 2003-12-11 devnull if(p>=eof || p>=nc){
582 b3994ec5 2003-12-11 devnull switch(wrapped++){
583 b3994ec5 2003-12-11 devnull case 0: /* let loop run one more click */
586 b3994ec5 2003-12-11 devnull case 1: /* expired; wrap to beginning */
587 b3994ec5 2003-12-11 devnull if(sel.r[0].q0>=0 || eof!=Infinity)
588 b3994ec5 2003-12-11 devnull goto Return;
589 b3994ec5 2003-12-11 devnull list[0][0].inst = list[1][0].inst = nil;
591 b3994ec5 2003-12-11 devnull goto doloop;
592 b3994ec5 2003-12-11 devnull default:
593 b3994ec5 2003-12-11 devnull goto Return;
597 b3994ec5 2003-12-11 devnull if(((wrapped && p>=startp) || sel.r[0].q0>0) && nnl==0)
599 b3994ec5 2003-12-11 devnull if(t != nil)
600 b3994ec5 2003-12-11 devnull c = textreadc(t, p);
602 b3994ec5 2003-12-11 devnull c = r[p];
604 b3994ec5 2003-12-11 devnull /* fast check for first char */
605 b3994ec5 2003-12-11 devnull if(startchar && nnl==0 && c!=startchar)
606 b3994ec5 2003-12-11 devnull continue;
607 b3994ec5 2003-12-11 devnull tl = list[flag];
608 b3994ec5 2003-12-11 devnull nl = list[flag^=1];
609 b3994ec5 2003-12-11 devnull nl->inst = nil;
610 b3994ec5 2003-12-11 devnull ntl = nnl;
611 b3994ec5 2003-12-11 devnull nnl = 0;
612 b3994ec5 2003-12-11 devnull if(sel.r[0].q0<0 && (!wrapped || p<startp || startp==eof)){
613 b3994ec5 2003-12-11 devnull /* Add first instruction to this list */
614 c99ef336 2007-06-09 devnull sempty.r[0].q0 = p;
615 c99ef336 2007-06-09 devnull if(addinst(tl, startinst, &sempty))
616 b3994ec5 2003-12-11 devnull if(++ntl >= NLIST){
617 b3994ec5 2003-12-11 devnull Overflow:
618 b3994ec5 2003-12-11 devnull warning(nil, "regexp list overflow\n");
619 b3994ec5 2003-12-11 devnull sel.r[0].q0 = -1;
620 b3994ec5 2003-12-11 devnull goto Return;
623 b3994ec5 2003-12-11 devnull /* Execute machine until this list is empty */
624 b3994ec5 2003-12-11 devnull for(tlp = tl; inst = tlp->inst; tlp++){ /* assignment = */
625 b3994ec5 2003-12-11 devnull Switchstmt:
626 b3994ec5 2003-12-11 devnull switch(inst->type){
627 b3994ec5 2003-12-11 devnull default: /* regular character */
628 b3994ec5 2003-12-11 devnull if(inst->type==c){
629 b3994ec5 2003-12-11 devnull Addinst:
630 c99ef336 2007-06-09 devnull if(addinst(nl, inst->u1.next, &tlp->se))
631 b3994ec5 2003-12-11 devnull if(++nnl >= NLIST)
632 b3994ec5 2003-12-11 devnull goto Overflow;
635 b3994ec5 2003-12-11 devnull case LBRA:
636 b3994ec5 2003-12-11 devnull if(inst->u.subid>=0)
637 b3994ec5 2003-12-11 devnull tlp->se.r[inst->u.subid].q0 = p;
638 b3994ec5 2003-12-11 devnull inst = inst->u1.next;
639 b3994ec5 2003-12-11 devnull goto Switchstmt;
640 b3994ec5 2003-12-11 devnull case RBRA:
641 b3994ec5 2003-12-11 devnull if(inst->u.subid>=0)
642 b3994ec5 2003-12-11 devnull tlp->se.r[inst->u.subid].q1 = p;
643 b3994ec5 2003-12-11 devnull inst = inst->u1.next;
644 b3994ec5 2003-12-11 devnull goto Switchstmt;
645 b3994ec5 2003-12-11 devnull case ANY:
646 b3994ec5 2003-12-11 devnull if(c!='\n')
647 b3994ec5 2003-12-11 devnull goto Addinst;
649 b3994ec5 2003-12-11 devnull case BOL:
650 b3994ec5 2003-12-11 devnull if(p==0 || (t!=nil && textreadc(t, p-1)=='\n') || (r!=nil && r[p-1]=='\n')){
652 b3994ec5 2003-12-11 devnull inst = inst->u1.next;
653 b3994ec5 2003-12-11 devnull goto Switchstmt;
656 b3994ec5 2003-12-11 devnull case EOL:
657 b3994ec5 2003-12-11 devnull if(c == '\n')
658 b3994ec5 2003-12-11 devnull goto Step;
660 b3994ec5 2003-12-11 devnull case CCLASS:
661 b3994ec5 2003-12-11 devnull if(c>=0 && classmatch(inst->u.class, c, 0))
662 b3994ec5 2003-12-11 devnull goto Addinst;
664 b3994ec5 2003-12-11 devnull case NCCLASS:
665 b3994ec5 2003-12-11 devnull if(c>=0 && classmatch(inst->u.class, c, 1))
666 b3994ec5 2003-12-11 devnull goto Addinst;
668 b3994ec5 2003-12-11 devnull case OR:
669 b3994ec5 2003-12-11 devnull /* evaluate right choice later */
670 c99ef336 2007-06-09 devnull if(addinst(tl, inst->u.right, &tlp->se))
671 b3994ec5 2003-12-11 devnull if(++ntl >= NLIST)
672 b3994ec5 2003-12-11 devnull goto Overflow;
673 b3994ec5 2003-12-11 devnull /* efficiency: advance and re-evaluate */
674 b3994ec5 2003-12-11 devnull inst = inst->u1.left;
675 b3994ec5 2003-12-11 devnull goto Switchstmt;
676 b3994ec5 2003-12-11 devnull case END: /* Match! */
677 b3994ec5 2003-12-11 devnull tlp->se.r[0].q1 = p;
678 b3994ec5 2003-12-11 devnull newmatch(&tlp->se);
684 b3994ec5 2003-12-11 devnull *rp = sel;
685 b3994ec5 2003-12-11 devnull return sel.r[0].q0 >= 0;
689 b3994ec5 2003-12-11 devnull newmatch(Rangeset *sp)
691 b3994ec5 2003-12-11 devnull if(sel.r[0].q0<0 || sp->r[0].q0<sel.r[0].q0 ||
692 b3994ec5 2003-12-11 devnull (sp->r[0].q0==sel.r[0].q0 && sp->r[0].q1>sel.r[0].q1))
693 b3994ec5 2003-12-11 devnull sel = *sp;
697 b3994ec5 2003-12-11 devnull rxbexecute(Text *t, uint startp, Rangeset *rp)
699 b3994ec5 2003-12-11 devnull int flag;
700 b3994ec5 2003-12-11 devnull Inst *inst;
701 b3994ec5 2003-12-11 devnull Ilist *tlp;
703 b3994ec5 2003-12-11 devnull int nnl, ntl;
705 b3994ec5 2003-12-11 devnull int wrapped;
706 b3994ec5 2003-12-11 devnull int startchar;
708 b3994ec5 2003-12-11 devnull flag = 0;
709 b3994ec5 2003-12-11 devnull nnl = 0;
710 b3994ec5 2003-12-11 devnull wrapped = 0;
711 b3994ec5 2003-12-11 devnull p = startp;
712 b3994ec5 2003-12-11 devnull startchar = 0;
713 b3994ec5 2003-12-11 devnull if(bstartinst->type<OPERATOR)
714 b3994ec5 2003-12-11 devnull startchar = bstartinst->type;
715 b3994ec5 2003-12-11 devnull list[0][0].inst = list[1][0].inst = nil;
716 b3994ec5 2003-12-11 devnull sel.r[0].q0= -1;
717 b3994ec5 2003-12-11 devnull /* Execute machine once for each character, including terminal NUL */
718 b3994ec5 2003-12-11 devnull for(;;--p){
720 b3994ec5 2003-12-11 devnull if(p <= 0){
721 b3994ec5 2003-12-11 devnull switch(wrapped++){
722 b3994ec5 2003-12-11 devnull case 0: /* let loop run one more click */
725 b3994ec5 2003-12-11 devnull case 1: /* expired; wrap to end */
726 b3994ec5 2003-12-11 devnull if(sel.r[0].q0>=0)
727 b3994ec5 2003-12-11 devnull goto Return;
728 b3994ec5 2003-12-11 devnull list[0][0].inst = list[1][0].inst = nil;
729 b3994ec5 2003-12-11 devnull p = t->file->b.nc;
730 b3994ec5 2003-12-11 devnull goto doloop;
732 b3994ec5 2003-12-11 devnull default:
733 b3994ec5 2003-12-11 devnull goto Return;
737 b3994ec5 2003-12-11 devnull if(((wrapped && p<=startp) || sel.r[0].q0>0) && nnl==0)
739 b3994ec5 2003-12-11 devnull c = textreadc(t, p-1);
741 b3994ec5 2003-12-11 devnull /* fast check for first char */
742 b3994ec5 2003-12-11 devnull if(startchar && nnl==0 && c!=startchar)
743 b3994ec5 2003-12-11 devnull continue;
744 b3994ec5 2003-12-11 devnull tl = list[flag];
745 b3994ec5 2003-12-11 devnull nl = list[flag^=1];
746 b3994ec5 2003-12-11 devnull nl->inst = nil;
747 b3994ec5 2003-12-11 devnull ntl = nnl;
748 b3994ec5 2003-12-11 devnull nnl = 0;
749 b3994ec5 2003-12-11 devnull if(sel.r[0].q0<0 && (!wrapped || p>startp)){
750 b3994ec5 2003-12-11 devnull /* Add first instruction to this list */
751 c99ef336 2007-06-09 devnull /* the minus is so the optimizations in addinst work */
752 c99ef336 2007-06-09 devnull sempty.r[0].q0 = -p;
753 c99ef336 2007-06-09 devnull if(addinst(tl, bstartinst, &sempty))
754 b3994ec5 2003-12-11 devnull if(++ntl >= NLIST){
755 b3994ec5 2003-12-11 devnull Overflow:
756 b3994ec5 2003-12-11 devnull warning(nil, "regexp list overflow\n");
757 b3994ec5 2003-12-11 devnull sel.r[0].q0 = -1;
758 b3994ec5 2003-12-11 devnull goto Return;
761 b3994ec5 2003-12-11 devnull /* Execute machine until this list is empty */
762 b3994ec5 2003-12-11 devnull for(tlp = tl; inst = tlp->inst; tlp++){ /* assignment = */
763 b3994ec5 2003-12-11 devnull Switchstmt:
764 b3994ec5 2003-12-11 devnull switch(inst->type){
765 b3994ec5 2003-12-11 devnull default: /* regular character */
766 b3994ec5 2003-12-11 devnull if(inst->type == c){
767 b3994ec5 2003-12-11 devnull Addinst:
768 c99ef336 2007-06-09 devnull if(addinst(nl, inst->u1.next, &tlp->se))
769 b3994ec5 2003-12-11 devnull if(++nnl >= NLIST)
770 b3994ec5 2003-12-11 devnull goto Overflow;
773 b3994ec5 2003-12-11 devnull case LBRA:
774 b3994ec5 2003-12-11 devnull if(inst->u.subid>=0)
775 b3994ec5 2003-12-11 devnull tlp->se.r[inst->u.subid].q0 = p;
776 b3994ec5 2003-12-11 devnull inst = inst->u1.next;
777 b3994ec5 2003-12-11 devnull goto Switchstmt;
778 b3994ec5 2003-12-11 devnull case RBRA:
779 b3994ec5 2003-12-11 devnull if(inst->u.subid >= 0)
780 b3994ec5 2003-12-11 devnull tlp->se.r[inst->u.subid].q1 = p;
781 b3994ec5 2003-12-11 devnull inst = inst->u1.next;
782 b3994ec5 2003-12-11 devnull goto Switchstmt;
783 b3994ec5 2003-12-11 devnull case ANY:
784 b3994ec5 2003-12-11 devnull if(c != '\n')
785 b3994ec5 2003-12-11 devnull goto Addinst;
787 b3994ec5 2003-12-11 devnull case BOL:
788 b3994ec5 2003-12-11 devnull if(c=='\n' || p==0){
790 b3994ec5 2003-12-11 devnull inst = inst->u1.next;
791 b3994ec5 2003-12-11 devnull goto Switchstmt;
794 b3994ec5 2003-12-11 devnull case EOL:
795 b3994ec5 2003-12-11 devnull if(p<t->file->b.nc && textreadc(t, p)=='\n')
796 b3994ec5 2003-12-11 devnull goto Step;
798 b3994ec5 2003-12-11 devnull case CCLASS:
799 b3994ec5 2003-12-11 devnull if(c>0 && classmatch(inst->u.class, c, 0))
800 b3994ec5 2003-12-11 devnull goto Addinst;
802 b3994ec5 2003-12-11 devnull case NCCLASS:
803 b3994ec5 2003-12-11 devnull if(c>0 && classmatch(inst->u.class, c, 1))
804 b3994ec5 2003-12-11 devnull goto Addinst;
806 b3994ec5 2003-12-11 devnull case OR:
807 b3994ec5 2003-12-11 devnull /* evaluate right choice later */
808 c99ef336 2007-06-09 devnull if(addinst(tl, inst->u.right, &tlp->se))
809 b3994ec5 2003-12-11 devnull if(++ntl >= NLIST)
810 b3994ec5 2003-12-11 devnull goto Overflow;
811 b3994ec5 2003-12-11 devnull /* efficiency: advance and re-evaluate */
812 b3994ec5 2003-12-11 devnull inst = inst->u1.left;
813 b3994ec5 2003-12-11 devnull goto Switchstmt;
814 b3994ec5 2003-12-11 devnull case END: /* Match! */
815 b3994ec5 2003-12-11 devnull tlp->se.r[0].q0 = -tlp->se.r[0].q0; /* minus sign */
816 b3994ec5 2003-12-11 devnull tlp->se.r[0].q1 = p;
817 b3994ec5 2003-12-11 devnull bnewmatch(&tlp->se);
823 b3994ec5 2003-12-11 devnull *rp = sel;
824 b3994ec5 2003-12-11 devnull return sel.r[0].q0 >= 0;
828 b3994ec5 2003-12-11 devnull bnewmatch(Rangeset *sp)
832 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))
833 b3994ec5 2003-12-11 devnull for(i = 0; i<NRange; i++){ /* note the reversal; q0<=q1 */
834 b3994ec5 2003-12-11 devnull sel.r[i].q0 = sp->r[i].q1;
835 b3994ec5 2003-12-11 devnull sel.r[i].q1 = sp->r[i].q0;
