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 b3994ec5 2003-12-11 devnull #define NLIST 128
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;
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 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);
128 b3994ec5 2003-12-11 devnull rxinit(void)
130 b3994ec5 2003-12-11 devnull rechan = chancreate(sizeof(Inst*), 0);
131 b3994ec5 2003-12-11 devnull lastregexp = runemalloc(1);
135 b3994ec5 2003-12-11 devnull regerror(char *e)
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);
144 b3994ec5 2003-12-11 devnull newinst(int t)
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++;
155 b3994ec5 2003-12-11 devnull realcompile(void *arg)
157 b3994ec5 2003-12-11 devnull int token;
158 b3994ec5 2003-12-11 devnull Rune *s;
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);
174 b3994ec5 2003-12-11 devnull operand(token);
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);
188 b3994ec5 2003-12-11 devnull /* r is null terminated */
190 b3994ec5 2003-12-11 devnull rxcompile(Rune *r)
192 b3994ec5 2003-12-11 devnull int i, nr;
193 b3994ec5 2003-12-11 devnull Inst *oprogp;
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;
223 b3994ec5 2003-12-11 devnull operand(int t)
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 */
234 b3994ec5 2003-12-11 devnull pushand(i, i);
235 b3994ec5 2003-12-11 devnull lastwasand = TRUE;
239 b3994ec5 2003-12-11 devnull operator(int t)
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 */
246 b3994ec5 2003-12-11 devnull if(lastwasand)
247 b3994ec5 2003-12-11 devnull operator(CAT);
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 */
258 b3994ec5 2003-12-11 devnull pushand(Inst *f, Inst *l)
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;
268 b3994ec5 2003-12-11 devnull pushator(int t)
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;
276 b3994ec5 2003-12-11 devnull *subidp++=cursubid;
280 b3994ec5 2003-12-11 devnull popand(int op)
282 b3994ec5 2003-12-11 devnull char buf[64];
284 b3994ec5 2003-12-11 devnull if(andp <= &andstack[0])
286 b3994ec5 2003-12-11 devnull sprint(buf, "missing operand for %c", op);
287 b3994ec5 2003-12-11 devnull regerror(buf);
289 b3994ec5 2003-12-11 devnull regerror("malformed regexp");
290 b3994ec5 2003-12-11 devnull return --andp;
294 b3994ec5 2003-12-11 devnull popator()
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;
303 b3994ec5 2003-12-11 devnull evaluntil(int pri)
305 b3994ec5 2003-12-11 devnull Node *op1, *op2, *t;
306 b3994ec5 2003-12-11 devnull Inst *inst1, *inst2;
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");
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);
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;
342 b3994ec5 2003-12-11 devnull op1->last->u1.next = op2->first;
343 b3994ec5 2003-12-11 devnull pushand(op1->first, op2->last);
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);
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);
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);
374 b3994ec5 2003-12-11 devnull optimize(Inst *start)
376 b3994ec5 2003-12-11 devnull Inst *inst, *target;
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;
387 b3994ec5 2003-12-11 devnull startlex(Rune *s)
389 b3994ec5 2003-12-11 devnull exprp = s;
390 b3994ec5 2003-12-11 devnull nbra = 0;
395 b3994ec5 2003-12-11 devnull lex(void){
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')
406 b3994ec5 2003-12-11 devnull c = END;
407 b3994ec5 2003-12-11 devnull --exprp; /* In case we come here again */
409 b3994ec5 2003-12-11 devnull case '*':
410 b3994ec5 2003-12-11 devnull c = STAR;
412 b3994ec5 2003-12-11 devnull case '?':
413 b3994ec5 2003-12-11 devnull c = QUEST;
415 b3994ec5 2003-12-11 devnull case '+':
416 b3994ec5 2003-12-11 devnull c = PLUS;
418 b3994ec5 2003-12-11 devnull case '|':
421 b3994ec5 2003-12-11 devnull case '.':
422 b3994ec5 2003-12-11 devnull c = ANY;
424 b3994ec5 2003-12-11 devnull case '(':
425 b3994ec5 2003-12-11 devnull c = LBRA;
427 b3994ec5 2003-12-11 devnull case ')':
428 b3994ec5 2003-12-11 devnull c = RBRA;
430 b3994ec5 2003-12-11 devnull case '^':
431 b3994ec5 2003-12-11 devnull c = BOL;
433 b3994ec5 2003-12-11 devnull case '$':
434 b3994ec5 2003-12-11 devnull c = EOL;
436 b3994ec5 2003-12-11 devnull case '[':
437 b3994ec5 2003-12-11 devnull c = CCLASS;
438 b3994ec5 2003-12-11 devnull bldcclass();
441 b3994ec5 2003-12-11 devnull return c;
445 b3994ec5 2003-12-11 devnull nextrec(void)
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';
455 b3994ec5 2003-12-11 devnull return *exprp++|0x10000;
457 b3994ec5 2003-12-11 devnull return *exprp++;
461 b3994ec5 2003-12-11 devnull bldcclass(void)
463 b3994ec5 2003-12-11 devnull int c1, c2, n, na;
464 b3994ec5 2003-12-11 devnull Rune *classp;
466 b3994ec5 2003-12-11 devnull classp = runemalloc(DCLASS);
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++;
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 == '-'){
479 b3994ec5 2003-12-11 devnull free(classp);
480 b3994ec5 2003-12-11 devnull regerror("malformed `[]'");
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);
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;
495 b3994ec5 2003-12-11 devnull classp[n++] = c1;
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*));
502 b3994ec5 2003-12-11 devnull class[nclass++] = classp;
506 b3994ec5 2003-12-11 devnull classmatch(int classno, int c, int negate)
508 b3994ec5 2003-12-11 devnull Rune *p;
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;
516 b3994ec5 2003-12-11 devnull }else if(*p++ == c)
517 b3994ec5 2003-12-11 devnull return !negate;
519 b3994ec5 2003-12-11 devnull return negate;
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.
528 b3994ec5 2003-12-11 devnull addinst(Ilist *l, Inst *inst, Rangeset *sep)
530 b3994ec5 2003-12-11 devnull Ilist *p;
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 */
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;
545 b3994ec5 2003-12-11 devnull rxnull(void)
547 b3994ec5 2003-12-11 devnull return startinst==nil || bstartinst==nil;
550 b3994ec5 2003-12-11 devnull /* either t!=nil or r!=nil, and we match the string in the appropriate place */
552 b3994ec5 2003-12-11 devnull rxexecute(Text *t, Rune *r, uint startp, uint eof, Rangeset *rp)
554 b3994ec5 2003-12-11 devnull int flag;
555 b3994ec5 2003-12-11 devnull Inst *inst;
556 b3994ec5 2003-12-11 devnull Ilist *tlp;
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;
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;
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++){
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 */
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;
589 b3994ec5 2003-12-11 devnull goto doloop;
590 b3994ec5 2003-12-11 devnull default:
591 b3994ec5 2003-12-11 devnull goto Return;
595 b3994ec5 2003-12-11 devnull if(((wrapped && p>=startp) || sel.r[0].q0>0) && nnl==0)
597 b3994ec5 2003-12-11 devnull if(t != nil)
598 b3994ec5 2003-12-11 devnull c = textreadc(t, p);
600 b3994ec5 2003-12-11 devnull c = r[p];
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;
618 b3994ec5 2003-12-11 devnull sempty.r[0].q0 = p;
619 b3994ec5 2003-12-11 devnull addinst(tl, startinst, &sempty);
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);
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;
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')){
650 b3994ec5 2003-12-11 devnull inst = inst->u1.next;
651 b3994ec5 2003-12-11 devnull goto Switchstmt;
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;
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;
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;
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);
682 b3994ec5 2003-12-11 devnull *rp = sel;
683 b3994ec5 2003-12-11 devnull return sel.r[0].q0 >= 0;
687 b3994ec5 2003-12-11 devnull newmatch(Rangeset *sp)
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;
695 b3994ec5 2003-12-11 devnull rxbexecute(Text *t, uint startp, Rangeset *rp)
697 b3994ec5 2003-12-11 devnull int flag;
698 b3994ec5 2003-12-11 devnull Inst *inst;
699 b3994ec5 2003-12-11 devnull Ilist *tlp;
701 b3994ec5 2003-12-11 devnull int nnl, ntl;
703 b3994ec5 2003-12-11 devnull int wrapped;
704 b3994ec5 2003-12-11 devnull int startchar;
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){
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 */
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;
730 b3994ec5 2003-12-11 devnull default:
731 b3994ec5 2003-12-11 devnull goto Return;
735 b3994ec5 2003-12-11 devnull if(((wrapped && p<=startp) || sel.r[0].q0>0) && nnl==0)
737 b3994ec5 2003-12-11 devnull c = textreadc(t, p-1);
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;
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);
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);
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;
785 b3994ec5 2003-12-11 devnull case BOL:
786 b3994ec5 2003-12-11 devnull if(c=='\n' || p==0){
788 b3994ec5 2003-12-11 devnull inst = inst->u1.next;
789 b3994ec5 2003-12-11 devnull goto Switchstmt;
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;
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;
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;
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);
821 b3994ec5 2003-12-11 devnull *rp = sel;
822 b3994ec5 2003-12-11 devnull return sel.r[0].q0 >= 0;
826 b3994ec5 2003-12-11 devnull bnewmatch(Rangeset *sp)
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;