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 36d9b90c 2010-07-14 rsc uint type; /* < OPERATOR ==> 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 36d9b90c 2010-07-14 rsc * 0x10000xx are operators, value == precedence
62 36d9b90c 2010-07-14 rsc * 0x20000xx are tokens, i.e. operands for operators
64 36d9b90c 2010-07-14 rsc #define OPERATOR 0x1000000 /* Bit set in all operators */
65 36d9b90c 2010-07-14 rsc #define START (OPERATOR+0) /* Start, used for marker on stack */
66 36d9b90c 2010-07-14 rsc #define RBRA (OPERATOR+1) /* Right bracket, ) */
67 36d9b90c 2010-07-14 rsc #define LBRA (OPERATOR+2) /* Left bracket, ( */
68 36d9b90c 2010-07-14 rsc #define OR (OPERATOR+3) /* Alternation, | */
69 36d9b90c 2010-07-14 rsc #define CAT (OPERATOR+4) /* Concatentation, implicit operator */
70 36d9b90c 2010-07-14 rsc #define STAR (OPERATOR+5) /* Closure, * */
71 36d9b90c 2010-07-14 rsc #define PLUS (OPERATOR+6) /* a+ == aa* */
72 36d9b90c 2010-07-14 rsc #define QUEST (OPERATOR+7) /* a? == a|nothing, i.e. 0 or 1 a's */
73 36d9b90c 2010-07-14 rsc #define ANY 0x2000000 /* Any character but newline, . */
74 36d9b90c 2010-07-14 rsc #define NOP (ANY+1) /* No operation, internal use only */
75 36d9b90c 2010-07-14 rsc #define BOL (ANY+2) /* Beginning of line, ^ */
76 36d9b90c 2010-07-14 rsc #define EOL (ANY+3) /* End of line, $ */
77 36d9b90c 2010-07-14 rsc #define CCLASS (ANY+4) /* Character class, [] */
78 36d9b90c 2010-07-14 rsc #define NCCLASS (ANY+5) /* Negated character class, [^] */
79 36d9b90c 2010-07-14 rsc #define END (ANY+0x77) /* Terminate: match found */
81 36d9b90c 2010-07-14 rsc #define ISATOR OPERATOR
82 36d9b90c 2010-07-14 rsc #define ISAND ANY
84 36d9b90c 2010-07-14 rsc #define QUOTED 0x4000000 /* Bit set for \-ed lex characters */
87 b3994ec5 2003-12-11 devnull * Parser Information
89 b3994ec5 2003-12-11 devnull typedef struct Node Node;
90 b3994ec5 2003-12-11 devnull struct Node
92 b3994ec5 2003-12-11 devnull Inst *first;
93 b3994ec5 2003-12-11 devnull Inst *last;
96 b3994ec5 2003-12-11 devnull #define NSTACK 20
97 b3994ec5 2003-12-11 devnull Node andstack[NSTACK];
98 b3994ec5 2003-12-11 devnull Node *andp;
99 b3994ec5 2003-12-11 devnull int atorstack[NSTACK];
100 b3994ec5 2003-12-11 devnull int *atorp;
101 b3994ec5 2003-12-11 devnull int lastwasand; /* Last token was operand */
102 b3994ec5 2003-12-11 devnull int cursubid;
103 b3994ec5 2003-12-11 devnull int subidstack[NSTACK];
104 b3994ec5 2003-12-11 devnull int *subidp;
105 b3994ec5 2003-12-11 devnull int backwards;
106 b3994ec5 2003-12-11 devnull int nbra;
107 b3994ec5 2003-12-11 devnull Rune *exprp; /* pointer to next character in source expression */
108 b3994ec5 2003-12-11 devnull #define DCLASS 10 /* allocation increment */
109 b3994ec5 2003-12-11 devnull int nclass; /* number active */
110 b3994ec5 2003-12-11 devnull int Nclass; /* high water mark */
111 b3994ec5 2003-12-11 devnull Rune **class;
112 b3994ec5 2003-12-11 devnull int negateclass;
114 c99ef336 2007-06-09 devnull int addinst(Ilist *l, Inst *inst, Rangeset *sep);
115 b3994ec5 2003-12-11 devnull void newmatch(Rangeset*);
116 b3994ec5 2003-12-11 devnull void bnewmatch(Rangeset*);
117 b3994ec5 2003-12-11 devnull void pushand(Inst*, Inst*);
118 b3994ec5 2003-12-11 devnull void pushator(int);
119 b3994ec5 2003-12-11 devnull Node *popand(int);
120 b3994ec5 2003-12-11 devnull int popator(void);
121 b3994ec5 2003-12-11 devnull void startlex(Rune*);
122 b3994ec5 2003-12-11 devnull int lex(void);
123 b3994ec5 2003-12-11 devnull void operator(int);
124 b3994ec5 2003-12-11 devnull void operand(int);
125 b3994ec5 2003-12-11 devnull void evaluntil(int);
126 b3994ec5 2003-12-11 devnull void optimize(Inst*);
127 b3994ec5 2003-12-11 devnull void bldcclass(void);
130 b3994ec5 2003-12-11 devnull rxinit(void)
132 b3994ec5 2003-12-11 devnull rechan = chancreate(sizeof(Inst*), 0);
133 334cb1e9 2004-12-27 devnull chansetname(rechan, "rechan");
134 b3994ec5 2003-12-11 devnull lastregexp = runemalloc(1);
138 b3994ec5 2003-12-11 devnull regerror(char *e)
140 b3994ec5 2003-12-11 devnull lastregexp[0] = 0;
141 b3994ec5 2003-12-11 devnull warning(nil, "regexp: %s\n", e);
142 b3994ec5 2003-12-11 devnull sendp(rechan, nil);
143 b3994ec5 2003-12-11 devnull threadexits(nil);
147 b3994ec5 2003-12-11 devnull newinst(int t)
149 b3994ec5 2003-12-11 devnull if(progp >= &program[NPROG])
150 b3994ec5 2003-12-11 devnull regerror("expression too long");
151 b3994ec5 2003-12-11 devnull progp->type = t;
152 b3994ec5 2003-12-11 devnull progp->u1.left = nil;
153 b3994ec5 2003-12-11 devnull progp->u.right = nil;
154 b3994ec5 2003-12-11 devnull return progp++;
158 b3994ec5 2003-12-11 devnull realcompile(void *arg)
160 b3994ec5 2003-12-11 devnull int token;
161 b3994ec5 2003-12-11 devnull Rune *s;
163 b3994ec5 2003-12-11 devnull threadsetname("regcomp");
164 b3994ec5 2003-12-11 devnull s = arg;
165 b3994ec5 2003-12-11 devnull startlex(s);
166 b3994ec5 2003-12-11 devnull atorp = atorstack;
167 b3994ec5 2003-12-11 devnull andp = andstack;
168 b3994ec5 2003-12-11 devnull subidp = subidstack;
169 b3994ec5 2003-12-11 devnull cursubid = 0;
170 b3994ec5 2003-12-11 devnull lastwasand = FALSE;
171 b3994ec5 2003-12-11 devnull /* Start with a low priority operator to prime parser */
172 b3994ec5 2003-12-11 devnull pushator(START-1);
173 b3994ec5 2003-12-11 devnull while((token=lex()) != END){
174 b3994ec5 2003-12-11 devnull if((token&ISATOR) == OPERATOR)
175 b3994ec5 2003-12-11 devnull operator(token);
177 b3994ec5 2003-12-11 devnull operand(token);
179 b3994ec5 2003-12-11 devnull /* Close with a low priority operator */
180 b3994ec5 2003-12-11 devnull evaluntil(START);
181 b3994ec5 2003-12-11 devnull /* Force END */
182 b3994ec5 2003-12-11 devnull operand(END);
183 b3994ec5 2003-12-11 devnull evaluntil(START);
184 b3994ec5 2003-12-11 devnull if(nbra)
185 b3994ec5 2003-12-11 devnull regerror("unmatched `('");
186 b3994ec5 2003-12-11 devnull --andp; /* points to first and only operand */
187 b3994ec5 2003-12-11 devnull sendp(rechan, andp->first);
188 b3994ec5 2003-12-11 devnull threadexits(nil);
191 b3994ec5 2003-12-11 devnull /* r is null terminated */
193 b3994ec5 2003-12-11 devnull rxcompile(Rune *r)
195 b3994ec5 2003-12-11 devnull int i, nr;
196 b3994ec5 2003-12-11 devnull Inst *oprogp;
198 b3994ec5 2003-12-11 devnull nr = runestrlen(r)+1;
199 b3994ec5 2003-12-11 devnull if(runeeq(lastregexp, runestrlen(lastregexp)+1, r, nr)==TRUE)
200 b3994ec5 2003-12-11 devnull return TRUE;
201 b3994ec5 2003-12-11 devnull lastregexp[0] = 0;
202 b3994ec5 2003-12-11 devnull for(i=0; i<nclass; i++)
203 b3994ec5 2003-12-11 devnull free(class[i]);
204 b3994ec5 2003-12-11 devnull nclass = 0;
205 b3994ec5 2003-12-11 devnull progp = program;
206 b3994ec5 2003-12-11 devnull backwards = FALSE;
207 b3994ec5 2003-12-11 devnull bstartinst = nil;
208 b3994ec5 2003-12-11 devnull threadcreate(realcompile, r, STACK);
209 b3994ec5 2003-12-11 devnull startinst = recvp(rechan);
210 b3994ec5 2003-12-11 devnull if(startinst == nil)
211 b3994ec5 2003-12-11 devnull return FALSE;
212 b3994ec5 2003-12-11 devnull optimize(program);
213 b3994ec5 2003-12-11 devnull oprogp = progp;
214 b3994ec5 2003-12-11 devnull backwards = TRUE;
215 b3994ec5 2003-12-11 devnull threadcreate(realcompile, r, STACK);
216 b3994ec5 2003-12-11 devnull bstartinst = recvp(rechan);
217 b3994ec5 2003-12-11 devnull if(bstartinst == nil)
218 b3994ec5 2003-12-11 devnull return FALSE;
219 b3994ec5 2003-12-11 devnull optimize(oprogp);
220 b3994ec5 2003-12-11 devnull lastregexp = runerealloc(lastregexp, nr);
221 b3994ec5 2003-12-11 devnull runemove(lastregexp, r, nr);
222 b3994ec5 2003-12-11 devnull return TRUE;
226 b3994ec5 2003-12-11 devnull operand(int t)
228 b3994ec5 2003-12-11 devnull Inst *i;
229 b3994ec5 2003-12-11 devnull if(lastwasand)
230 b3994ec5 2003-12-11 devnull operator(CAT); /* catenate is implicit */
231 b3994ec5 2003-12-11 devnull i = newinst(t);
232 b3994ec5 2003-12-11 devnull if(t == CCLASS){
233 b3994ec5 2003-12-11 devnull if(negateclass)
234 b3994ec5 2003-12-11 devnull i->type = NCCLASS; /* UGH */
235 b3994ec5 2003-12-11 devnull i->u.class = nclass-1; /* UGH */
237 b3994ec5 2003-12-11 devnull pushand(i, i);
238 b3994ec5 2003-12-11 devnull lastwasand = TRUE;
242 b3994ec5 2003-12-11 devnull operator(int t)
244 b3994ec5 2003-12-11 devnull if(t==RBRA && --nbra<0)
245 b3994ec5 2003-12-11 devnull regerror("unmatched `)'");
246 b3994ec5 2003-12-11 devnull if(t==LBRA){
247 b3994ec5 2003-12-11 devnull cursubid++; /* silently ignored */
249 b3994ec5 2003-12-11 devnull if(lastwasand)
250 b3994ec5 2003-12-11 devnull operator(CAT);
252 b3994ec5 2003-12-11 devnull evaluntil(t);
253 b3994ec5 2003-12-11 devnull if(t!=RBRA)
254 b3994ec5 2003-12-11 devnull pushator(t);
255 b3994ec5 2003-12-11 devnull lastwasand = FALSE;
256 b3994ec5 2003-12-11 devnull if(t==STAR || t==QUEST || t==PLUS || t==RBRA)
257 b3994ec5 2003-12-11 devnull lastwasand = TRUE; /* these look like operands */
261 b3994ec5 2003-12-11 devnull pushand(Inst *f, Inst *l)
263 b3994ec5 2003-12-11 devnull if(andp >= &andstack[NSTACK])
264 b3994ec5 2003-12-11 devnull error("operand stack overflow");
265 b3994ec5 2003-12-11 devnull andp->first = f;
266 b3994ec5 2003-12-11 devnull andp->last = l;
271 b3994ec5 2003-12-11 devnull pushator(int t)
273 b3994ec5 2003-12-11 devnull if(atorp >= &atorstack[NSTACK])
274 b3994ec5 2003-12-11 devnull error("operator stack overflow");
275 b3994ec5 2003-12-11 devnull *atorp++=t;
276 b3994ec5 2003-12-11 devnull if(cursubid >= NRange)
277 b3994ec5 2003-12-11 devnull *subidp++= -1;
279 b3994ec5 2003-12-11 devnull *subidp++=cursubid;
283 b3994ec5 2003-12-11 devnull popand(int op)
285 b3994ec5 2003-12-11 devnull char buf[64];
287 b3994ec5 2003-12-11 devnull if(andp <= &andstack[0])
289 b3994ec5 2003-12-11 devnull sprint(buf, "missing operand for %c", op);
290 b3994ec5 2003-12-11 devnull regerror(buf);
292 b3994ec5 2003-12-11 devnull regerror("malformed regexp");
293 b3994ec5 2003-12-11 devnull return --andp;
297 b3994ec5 2003-12-11 devnull popator()
299 b3994ec5 2003-12-11 devnull if(atorp <= &atorstack[0])
300 b3994ec5 2003-12-11 devnull error("operator stack underflow");
301 b3994ec5 2003-12-11 devnull --subidp;
302 b3994ec5 2003-12-11 devnull return *--atorp;
306 b3994ec5 2003-12-11 devnull evaluntil(int pri)
308 b3994ec5 2003-12-11 devnull Node *op1, *op2, *t;
309 b3994ec5 2003-12-11 devnull Inst *inst1, *inst2;
311 b3994ec5 2003-12-11 devnull while(pri==RBRA || atorp[-1]>=pri){
312 b3994ec5 2003-12-11 devnull switch(popator()){
313 b3994ec5 2003-12-11 devnull case LBRA:
314 b3994ec5 2003-12-11 devnull op1 = popand('(');
315 b3994ec5 2003-12-11 devnull inst2 = newinst(RBRA);
316 b3994ec5 2003-12-11 devnull inst2->u.subid = *subidp;
317 b3994ec5 2003-12-11 devnull op1->last->u1.next = inst2;
318 b3994ec5 2003-12-11 devnull inst1 = newinst(LBRA);
319 b3994ec5 2003-12-11 devnull inst1->u.subid = *subidp;
320 b3994ec5 2003-12-11 devnull inst1->u1.next = op1->first;
321 b3994ec5 2003-12-11 devnull pushand(inst1, inst2);
322 b3994ec5 2003-12-11 devnull return; /* must have been RBRA */
323 b3994ec5 2003-12-11 devnull default:
324 b3994ec5 2003-12-11 devnull error("unknown regexp operator");
326 b3994ec5 2003-12-11 devnull case OR:
327 b3994ec5 2003-12-11 devnull op2 = popand('|');
328 b3994ec5 2003-12-11 devnull op1 = popand('|');
329 b3994ec5 2003-12-11 devnull inst2 = newinst(NOP);
330 b3994ec5 2003-12-11 devnull op2->last->u1.next = inst2;
331 b3994ec5 2003-12-11 devnull op1->last->u1.next = inst2;
332 b3994ec5 2003-12-11 devnull inst1 = newinst(OR);
333 b3994ec5 2003-12-11 devnull inst1->u.right = op1->first;
334 b3994ec5 2003-12-11 devnull inst1->u1.left = op2->first;
335 b3994ec5 2003-12-11 devnull pushand(inst1, inst2);
337 b3994ec5 2003-12-11 devnull case CAT:
338 b3994ec5 2003-12-11 devnull op2 = popand(0);
339 b3994ec5 2003-12-11 devnull op1 = popand(0);
340 b3994ec5 2003-12-11 devnull if(backwards && op2->first->type!=END){
341 b3994ec5 2003-12-11 devnull t = op1;
342 b3994ec5 2003-12-11 devnull op1 = op2;
343 b3994ec5 2003-12-11 devnull op2 = t;
345 b3994ec5 2003-12-11 devnull op1->last->u1.next = op2->first;
346 b3994ec5 2003-12-11 devnull pushand(op1->first, op2->last);
348 b3994ec5 2003-12-11 devnull case STAR:
349 b3994ec5 2003-12-11 devnull op2 = popand('*');
350 b3994ec5 2003-12-11 devnull inst1 = newinst(OR);
351 b3994ec5 2003-12-11 devnull op2->last->u1.next = inst1;
352 b3994ec5 2003-12-11 devnull inst1->u.right = op2->first;
353 b3994ec5 2003-12-11 devnull pushand(inst1, inst1);
355 b3994ec5 2003-12-11 devnull case PLUS:
356 b3994ec5 2003-12-11 devnull op2 = popand('+');
357 b3994ec5 2003-12-11 devnull inst1 = newinst(OR);
358 b3994ec5 2003-12-11 devnull op2->last->u1.next = inst1;
359 b3994ec5 2003-12-11 devnull inst1->u.right = op2->first;
360 b3994ec5 2003-12-11 devnull pushand(op2->first, inst1);
362 b3994ec5 2003-12-11 devnull case QUEST:
363 b3994ec5 2003-12-11 devnull op2 = popand('?');
364 b3994ec5 2003-12-11 devnull inst1 = newinst(OR);
365 b3994ec5 2003-12-11 devnull inst2 = newinst(NOP);
366 b3994ec5 2003-12-11 devnull inst1->u1.left = inst2;
367 b3994ec5 2003-12-11 devnull inst1->u.right = op2->first;
368 b3994ec5 2003-12-11 devnull op2->last->u1.next = inst2;
369 b3994ec5 2003-12-11 devnull pushand(inst1, inst2);
377 b3994ec5 2003-12-11 devnull optimize(Inst *start)
379 b3994ec5 2003-12-11 devnull Inst *inst, *target;
381 b3994ec5 2003-12-11 devnull for(inst=start; inst->type!=END; inst++){
382 b3994ec5 2003-12-11 devnull target = inst->u1.next;
383 b3994ec5 2003-12-11 devnull while(target->type == NOP)
384 b3994ec5 2003-12-11 devnull target = target->u1.next;
385 b3994ec5 2003-12-11 devnull inst->u1.next = target;
390 b3994ec5 2003-12-11 devnull startlex(Rune *s)
392 b3994ec5 2003-12-11 devnull exprp = s;
393 b3994ec5 2003-12-11 devnull nbra = 0;
398 b3994ec5 2003-12-11 devnull lex(void){
401 b3994ec5 2003-12-11 devnull c = *exprp++;
402 b3994ec5 2003-12-11 devnull switch(c){
403 b3994ec5 2003-12-11 devnull case '\\':
404 b3994ec5 2003-12-11 devnull if(*exprp)
405 b3994ec5 2003-12-11 devnull if((c= *exprp++)=='n')
409 b3994ec5 2003-12-11 devnull c = END;
410 b3994ec5 2003-12-11 devnull --exprp; /* In case we come here again */
412 b3994ec5 2003-12-11 devnull case '*':
413 b3994ec5 2003-12-11 devnull c = STAR;
415 b3994ec5 2003-12-11 devnull case '?':
416 b3994ec5 2003-12-11 devnull c = QUEST;
418 b3994ec5 2003-12-11 devnull case '+':
419 b3994ec5 2003-12-11 devnull c = PLUS;
421 b3994ec5 2003-12-11 devnull case '|':
424 b3994ec5 2003-12-11 devnull case '.':
425 b3994ec5 2003-12-11 devnull c = ANY;
427 b3994ec5 2003-12-11 devnull case '(':
428 b3994ec5 2003-12-11 devnull c = LBRA;
430 b3994ec5 2003-12-11 devnull case ')':
431 b3994ec5 2003-12-11 devnull c = RBRA;
433 b3994ec5 2003-12-11 devnull case '^':
434 b3994ec5 2003-12-11 devnull c = BOL;
436 b3994ec5 2003-12-11 devnull case '$':
437 b3994ec5 2003-12-11 devnull c = EOL;
439 b3994ec5 2003-12-11 devnull case '[':
440 b3994ec5 2003-12-11 devnull c = CCLASS;
441 b3994ec5 2003-12-11 devnull bldcclass();
444 b3994ec5 2003-12-11 devnull return c;
448 b3994ec5 2003-12-11 devnull nextrec(void)
450 b3994ec5 2003-12-11 devnull if(exprp[0]==0 || (exprp[0]=='\\' && exprp[1]==0))
451 b3994ec5 2003-12-11 devnull regerror("malformed `[]'");
452 b3994ec5 2003-12-11 devnull if(exprp[0] == '\\'){
453 b3994ec5 2003-12-11 devnull exprp++;
454 b3994ec5 2003-12-11 devnull if(*exprp=='n'){
455 b3994ec5 2003-12-11 devnull exprp++;
456 b3994ec5 2003-12-11 devnull return '\n';
458 36d9b90c 2010-07-14 rsc return *exprp++|QUOTED;
460 b3994ec5 2003-12-11 devnull return *exprp++;
464 b3994ec5 2003-12-11 devnull bldcclass(void)
466 b3994ec5 2003-12-11 devnull int c1, c2, n, na;
467 b3994ec5 2003-12-11 devnull Rune *classp;
469 b3994ec5 2003-12-11 devnull classp = runemalloc(DCLASS);
471 b3994ec5 2003-12-11 devnull na = DCLASS;
472 b3994ec5 2003-12-11 devnull /* we have already seen the '[' */
473 b3994ec5 2003-12-11 devnull if(*exprp == '^'){
474 b3994ec5 2003-12-11 devnull classp[n++] = '\n'; /* don't match newline in negate case */
475 b3994ec5 2003-12-11 devnull negateclass = TRUE;
476 b3994ec5 2003-12-11 devnull exprp++;
478 b3994ec5 2003-12-11 devnull negateclass = FALSE;
479 b3994ec5 2003-12-11 devnull while((c1 = nextrec()) != ']'){
480 b3994ec5 2003-12-11 devnull if(c1 == '-'){
482 b3994ec5 2003-12-11 devnull free(classp);
483 b3994ec5 2003-12-11 devnull regerror("malformed `[]'");
485 b3994ec5 2003-12-11 devnull if(n+4 >= na){ /* 3 runes plus NUL */
486 b3994ec5 2003-12-11 devnull na += DCLASS;
487 b3994ec5 2003-12-11 devnull classp = runerealloc(classp, na);
489 b3994ec5 2003-12-11 devnull if(*exprp == '-'){
490 b3994ec5 2003-12-11 devnull exprp++; /* eat '-' */
491 b3994ec5 2003-12-11 devnull if((c2 = nextrec()) == ']')
492 b3994ec5 2003-12-11 devnull goto Error;
493 0cadb430 2009-09-11 russcox classp[n+0] = Runemax;
494 b3994ec5 2003-12-11 devnull classp[n+1] = c1;
495 b3994ec5 2003-12-11 devnull classp[n+2] = c2;
498 36d9b90c 2010-07-14 rsc classp[n++] = c1 & ~QUOTED;
500 b3994ec5 2003-12-11 devnull classp[n] = 0;
501 b3994ec5 2003-12-11 devnull if(nclass == Nclass){
502 b3994ec5 2003-12-11 devnull Nclass += DCLASS;
503 b3994ec5 2003-12-11 devnull class = realloc(class, Nclass*sizeof(Rune*));
505 b3994ec5 2003-12-11 devnull class[nclass++] = classp;
509 b3994ec5 2003-12-11 devnull classmatch(int classno, int c, int negate)
511 b3994ec5 2003-12-11 devnull Rune *p;
513 b3994ec5 2003-12-11 devnull p = class[classno];
514 b3994ec5 2003-12-11 devnull while(*p){
515 0cadb430 2009-09-11 russcox if(*p == Runemax){
516 b3994ec5 2003-12-11 devnull if(p[1]<=c && c<=p[2])
517 b3994ec5 2003-12-11 devnull return !negate;
519 b3994ec5 2003-12-11 devnull }else if(*p++ == c)
520 b3994ec5 2003-12-11 devnull return !negate;
522 b3994ec5 2003-12-11 devnull return negate;
526 73778bae 2007-12-07 rsc * Note optimization in addinst:
527 73778bae 2007-12-07 rsc * *l must be pending when addinst called; if *l has been looked
528 73778bae 2007-12-07 rsc * at already, the optimization is a bug.
531 6f16e7fc 2007-12-07 rsc addinst(Ilist *l, Inst *inst, Rangeset *sep)
535 73778bae 2007-12-07 rsc for(p = l; p->inst; p++){
536 73778bae 2007-12-07 rsc if(p->inst==inst){
537 73778bae 2007-12-07 rsc if((sep)->r[0].q0 < p->se.r[0].q0)
538 73778bae 2007-12-07 rsc p->se= *sep; /* this would be bug */
539 73778bae 2007-12-07 rsc return 0; /* It's already there */
542 73778bae 2007-12-07 rsc p->inst = inst;
543 73778bae 2007-12-07 rsc p->se= *sep;
544 73778bae 2007-12-07 rsc (p+1)->inst = nil;
549 b3994ec5 2003-12-11 devnull rxnull(void)
551 b3994ec5 2003-12-11 devnull return startinst==nil || bstartinst==nil;
554 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 rxexecute(Text *t, Rune *r, uint startp, uint eof, Rangeset *rp)
558 b3994ec5 2003-12-11 devnull int flag;
559 b3994ec5 2003-12-11 devnull Inst *inst;
560 b3994ec5 2003-12-11 devnull Ilist *tlp;
562 73778bae 2007-12-07 rsc int nnl, ntl;
563 b3994ec5 2003-12-11 devnull int nc, c;
564 b3994ec5 2003-12-11 devnull int wrapped;
565 b3994ec5 2003-12-11 devnull int startchar;
567 b3994ec5 2003-12-11 devnull flag = 0;
568 b3994ec5 2003-12-11 devnull p = startp;
569 b3994ec5 2003-12-11 devnull startchar = 0;
570 b3994ec5 2003-12-11 devnull wrapped = 0;
572 b3994ec5 2003-12-11 devnull if(startinst->type<OPERATOR)
573 b3994ec5 2003-12-11 devnull startchar = startinst->type;
574 b3994ec5 2003-12-11 devnull list[0][0].inst = list[1][0].inst = nil;
575 b3994ec5 2003-12-11 devnull sel.r[0].q0 = -1;
576 b3994ec5 2003-12-11 devnull if(t != nil)
577 b3994ec5 2003-12-11 devnull nc = t->file->b.nc;
579 b3994ec5 2003-12-11 devnull nc = runestrlen(r);
580 b3994ec5 2003-12-11 devnull /* Execute machine once for each character */
581 b3994ec5 2003-12-11 devnull for(;;p++){
583 b3994ec5 2003-12-11 devnull if(p>=eof || p>=nc){
584 b3994ec5 2003-12-11 devnull switch(wrapped++){
585 b3994ec5 2003-12-11 devnull case 0: /* let loop run one more click */
588 b3994ec5 2003-12-11 devnull case 1: /* expired; wrap to beginning */
589 b3994ec5 2003-12-11 devnull if(sel.r[0].q0>=0 || eof!=Infinity)
590 b3994ec5 2003-12-11 devnull goto Return;
591 b3994ec5 2003-12-11 devnull list[0][0].inst = list[1][0].inst = nil;
593 b3994ec5 2003-12-11 devnull goto doloop;
594 b3994ec5 2003-12-11 devnull default:
595 b3994ec5 2003-12-11 devnull goto Return;
599 73778bae 2007-12-07 rsc if(((wrapped && p>=startp) || sel.r[0].q0>0) && nnl==0)
601 b3994ec5 2003-12-11 devnull if(t != nil)
602 b3994ec5 2003-12-11 devnull c = textreadc(t, p);
604 b3994ec5 2003-12-11 devnull c = r[p];
606 b3994ec5 2003-12-11 devnull /* fast check for first char */
607 73778bae 2007-12-07 rsc if(startchar && nnl==0 && c!=startchar)
608 b3994ec5 2003-12-11 devnull continue;
609 b3994ec5 2003-12-11 devnull tl = list[flag];
610 b3994ec5 2003-12-11 devnull nl = list[flag^=1];
611 b3994ec5 2003-12-11 devnull nl->inst = nil;
614 b3994ec5 2003-12-11 devnull if(sel.r[0].q0<0 && (!wrapped || p<startp || startp==eof)){
615 b3994ec5 2003-12-11 devnull /* Add first instruction to this list */
616 c99ef336 2007-06-09 devnull sempty.r[0].q0 = p;
617 73778bae 2007-12-07 rsc if(addinst(tl, startinst, &sempty))
618 73778bae 2007-12-07 rsc if(++ntl >= NLIST){
619 b3994ec5 2003-12-11 devnull Overflow:
620 b3994ec5 2003-12-11 devnull warning(nil, "regexp list overflow\n");
621 b3994ec5 2003-12-11 devnull sel.r[0].q0 = -1;
622 b3994ec5 2003-12-11 devnull goto Return;
625 b3994ec5 2003-12-11 devnull /* Execute machine until this list is empty */
626 b3994ec5 2003-12-11 devnull for(tlp = tl; inst = tlp->inst; tlp++){ /* assignment = */
627 b3994ec5 2003-12-11 devnull Switchstmt:
628 b3994ec5 2003-12-11 devnull switch(inst->type){
629 b3994ec5 2003-12-11 devnull default: /* regular character */
630 b3994ec5 2003-12-11 devnull if(inst->type==c){
631 b3994ec5 2003-12-11 devnull Addinst:
632 73778bae 2007-12-07 rsc if(addinst(nl, inst->u1.next, &tlp->se))
633 73778bae 2007-12-07 rsc if(++nnl >= NLIST)
634 b3994ec5 2003-12-11 devnull goto Overflow;
637 b3994ec5 2003-12-11 devnull case LBRA:
638 b3994ec5 2003-12-11 devnull if(inst->u.subid>=0)
639 b3994ec5 2003-12-11 devnull tlp->se.r[inst->u.subid].q0 = p;
640 b3994ec5 2003-12-11 devnull inst = inst->u1.next;
641 b3994ec5 2003-12-11 devnull goto Switchstmt;
642 b3994ec5 2003-12-11 devnull case RBRA:
643 b3994ec5 2003-12-11 devnull if(inst->u.subid>=0)
644 b3994ec5 2003-12-11 devnull tlp->se.r[inst->u.subid].q1 = p;
645 b3994ec5 2003-12-11 devnull inst = inst->u1.next;
646 b3994ec5 2003-12-11 devnull goto Switchstmt;
647 b3994ec5 2003-12-11 devnull case ANY:
648 b3994ec5 2003-12-11 devnull if(c!='\n')
649 b3994ec5 2003-12-11 devnull goto Addinst;
651 b3994ec5 2003-12-11 devnull case BOL:
652 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 inst = inst->u1.next;
655 b3994ec5 2003-12-11 devnull goto Switchstmt;
658 b3994ec5 2003-12-11 devnull case EOL:
659 b3994ec5 2003-12-11 devnull if(c == '\n')
660 b3994ec5 2003-12-11 devnull goto Step;
662 b3994ec5 2003-12-11 devnull case CCLASS:
663 b3994ec5 2003-12-11 devnull if(c>=0 && classmatch(inst->u.class, c, 0))
664 b3994ec5 2003-12-11 devnull goto Addinst;
666 b3994ec5 2003-12-11 devnull case NCCLASS:
667 b3994ec5 2003-12-11 devnull if(c>=0 && classmatch(inst->u.class, c, 1))
668 b3994ec5 2003-12-11 devnull goto Addinst;
670 b3994ec5 2003-12-11 devnull case OR:
671 73778bae 2007-12-07 rsc /* evaluate right choice later */
672 d694fe22 2008-01-30 rsc if(addinst(tlp, inst->u.right, &tlp->se))
673 73778bae 2007-12-07 rsc if(++ntl >= NLIST)
674 73778bae 2007-12-07 rsc goto Overflow;
675 73778bae 2007-12-07 rsc /* efficiency: advance and re-evaluate */
676 73778bae 2007-12-07 rsc inst = inst->u1.left;
677 73778bae 2007-12-07 rsc goto Switchstmt;
678 b3994ec5 2003-12-11 devnull case END: /* Match! */
679 b3994ec5 2003-12-11 devnull tlp->se.r[0].q1 = p;
680 b3994ec5 2003-12-11 devnull newmatch(&tlp->se);
686 b3994ec5 2003-12-11 devnull *rp = sel;
687 b3994ec5 2003-12-11 devnull return sel.r[0].q0 >= 0;
691 b3994ec5 2003-12-11 devnull newmatch(Rangeset *sp)
693 b3994ec5 2003-12-11 devnull if(sel.r[0].q0<0 || sp->r[0].q0<sel.r[0].q0 ||
694 b3994ec5 2003-12-11 devnull (sp->r[0].q0==sel.r[0].q0 && sp->r[0].q1>sel.r[0].q1))
695 b3994ec5 2003-12-11 devnull sel = *sp;
699 b3994ec5 2003-12-11 devnull rxbexecute(Text *t, uint startp, Rangeset *rp)
701 b3994ec5 2003-12-11 devnull int flag;
702 b3994ec5 2003-12-11 devnull Inst *inst;
703 b3994ec5 2003-12-11 devnull Ilist *tlp;
705 73778bae 2007-12-07 rsc int nnl, ntl;
707 b3994ec5 2003-12-11 devnull int wrapped;
708 b3994ec5 2003-12-11 devnull int startchar;
710 b3994ec5 2003-12-11 devnull flag = 0;
712 b3994ec5 2003-12-11 devnull wrapped = 0;
713 b3994ec5 2003-12-11 devnull p = startp;
714 b3994ec5 2003-12-11 devnull startchar = 0;
715 b3994ec5 2003-12-11 devnull if(bstartinst->type<OPERATOR)
716 b3994ec5 2003-12-11 devnull startchar = bstartinst->type;
717 b3994ec5 2003-12-11 devnull list[0][0].inst = list[1][0].inst = nil;
718 b3994ec5 2003-12-11 devnull sel.r[0].q0= -1;
719 b3994ec5 2003-12-11 devnull /* Execute machine once for each character, including terminal NUL */
720 b3994ec5 2003-12-11 devnull for(;;--p){
722 b3994ec5 2003-12-11 devnull if(p <= 0){
723 b3994ec5 2003-12-11 devnull switch(wrapped++){
724 b3994ec5 2003-12-11 devnull case 0: /* let loop run one more click */
727 b3994ec5 2003-12-11 devnull case 1: /* expired; wrap to end */
728 b3994ec5 2003-12-11 devnull if(sel.r[0].q0>=0)
729 b3994ec5 2003-12-11 devnull goto Return;
730 b3994ec5 2003-12-11 devnull list[0][0].inst = list[1][0].inst = nil;
731 b3994ec5 2003-12-11 devnull p = t->file->b.nc;
732 b3994ec5 2003-12-11 devnull goto doloop;
734 b3994ec5 2003-12-11 devnull default:
735 b3994ec5 2003-12-11 devnull goto Return;
739 73778bae 2007-12-07 rsc if(((wrapped && p<=startp) || sel.r[0].q0>0) && nnl==0)
741 b3994ec5 2003-12-11 devnull c = textreadc(t, p-1);
743 b3994ec5 2003-12-11 devnull /* fast check for first char */
744 73778bae 2007-12-07 rsc if(startchar && nnl==0 && c!=startchar)
745 b3994ec5 2003-12-11 devnull continue;
746 b3994ec5 2003-12-11 devnull tl = list[flag];
747 b3994ec5 2003-12-11 devnull nl = list[flag^=1];
748 b3994ec5 2003-12-11 devnull nl->inst = nil;
751 b3994ec5 2003-12-11 devnull if(sel.r[0].q0<0 && (!wrapped || p>startp)){
752 b3994ec5 2003-12-11 devnull /* Add first instruction to this list */
753 73778bae 2007-12-07 rsc /* the minus is so the optimizations in addinst work */
754 73778bae 2007-12-07 rsc sempty.r[0].q0 = -p;
755 73778bae 2007-12-07 rsc if(addinst(tl, bstartinst, &sempty))
756 73778bae 2007-12-07 rsc if(++ntl >= NLIST){
757 b3994ec5 2003-12-11 devnull Overflow:
758 b3994ec5 2003-12-11 devnull warning(nil, "regexp list overflow\n");
759 b3994ec5 2003-12-11 devnull sel.r[0].q0 = -1;
760 b3994ec5 2003-12-11 devnull goto Return;
763 b3994ec5 2003-12-11 devnull /* Execute machine until this list is empty */
764 b3994ec5 2003-12-11 devnull for(tlp = tl; inst = tlp->inst; tlp++){ /* assignment = */
765 b3994ec5 2003-12-11 devnull Switchstmt:
766 b3994ec5 2003-12-11 devnull switch(inst->type){
767 b3994ec5 2003-12-11 devnull default: /* regular character */
768 b3994ec5 2003-12-11 devnull if(inst->type == c){
769 b3994ec5 2003-12-11 devnull Addinst:
770 73778bae 2007-12-07 rsc if(addinst(nl, inst->u1.next, &tlp->se))
771 73778bae 2007-12-07 rsc if(++nnl >= NLIST)
772 b3994ec5 2003-12-11 devnull goto Overflow;
775 b3994ec5 2003-12-11 devnull case LBRA:
776 b3994ec5 2003-12-11 devnull if(inst->u.subid>=0)
777 b3994ec5 2003-12-11 devnull tlp->se.r[inst->u.subid].q0 = p;
778 b3994ec5 2003-12-11 devnull inst = inst->u1.next;
779 b3994ec5 2003-12-11 devnull goto Switchstmt;
780 b3994ec5 2003-12-11 devnull case RBRA:
781 b3994ec5 2003-12-11 devnull if(inst->u.subid >= 0)
782 b3994ec5 2003-12-11 devnull tlp->se.r[inst->u.subid].q1 = p;
783 b3994ec5 2003-12-11 devnull inst = inst->u1.next;
784 b3994ec5 2003-12-11 devnull goto Switchstmt;
785 b3994ec5 2003-12-11 devnull case ANY:
786 b3994ec5 2003-12-11 devnull if(c != '\n')
787 b3994ec5 2003-12-11 devnull goto Addinst;
789 b3994ec5 2003-12-11 devnull case BOL:
790 b3994ec5 2003-12-11 devnull if(c=='\n' || p==0){
792 b3994ec5 2003-12-11 devnull inst = inst->u1.next;
793 b3994ec5 2003-12-11 devnull goto Switchstmt;
796 b3994ec5 2003-12-11 devnull case EOL:
797 b3994ec5 2003-12-11 devnull if(p<t->file->b.nc && textreadc(t, p)=='\n')
798 b3994ec5 2003-12-11 devnull goto Step;
800 b3994ec5 2003-12-11 devnull case CCLASS:
801 b3994ec5 2003-12-11 devnull if(c>0 && classmatch(inst->u.class, c, 0))
802 b3994ec5 2003-12-11 devnull goto Addinst;
804 b3994ec5 2003-12-11 devnull case NCCLASS:
805 b3994ec5 2003-12-11 devnull if(c>0 && classmatch(inst->u.class, c, 1))
806 b3994ec5 2003-12-11 devnull goto Addinst;
808 b3994ec5 2003-12-11 devnull case OR:
809 73778bae 2007-12-07 rsc /* evaluate right choice later */
810 73778bae 2007-12-07 rsc if(addinst(tl, inst->u.right, &tlp->se))
811 73778bae 2007-12-07 rsc if(++ntl >= NLIST)
812 73778bae 2007-12-07 rsc goto Overflow;
813 73778bae 2007-12-07 rsc /* efficiency: advance and re-evaluate */
814 73778bae 2007-12-07 rsc inst = inst->u1.left;
815 73778bae 2007-12-07 rsc goto Switchstmt;
816 b3994ec5 2003-12-11 devnull case END: /* Match! */
817 73778bae 2007-12-07 rsc tlp->se.r[0].q0 = -tlp->se.r[0].q0; /* minus sign */
818 b3994ec5 2003-12-11 devnull tlp->se.r[0].q1 = p;
819 b3994ec5 2003-12-11 devnull bnewmatch(&tlp->se);
825 b3994ec5 2003-12-11 devnull *rp = sel;
826 b3994ec5 2003-12-11 devnull return sel.r[0].q0 >= 0;
830 b3994ec5 2003-12-11 devnull bnewmatch(Rangeset *sp)
834 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))
835 b3994ec5 2003-12-11 devnull for(i = 0; i<NRange; i++){ /* note the reversal; q0<=q1 */
836 b3994ec5 2003-12-11 devnull sel.r[i].q0 = sp->r[i].q1;
837 b3994ec5 2003-12-11 devnull sel.r[i].q1 = sp->r[i].q0;
