1 b3994ec5 2003-12-11 devnull #include <u.h>
2 b3994ec5 2003-12-11 devnull #include <libc.h>
3 b3994ec5 2003-12-11 devnull #include <draw.h>
4 b3994ec5 2003-12-11 devnull #include <thread.h>
5 b3994ec5 2003-12-11 devnull #include <cursor.h>
6 b3994ec5 2003-12-11 devnull #include <mouse.h>
7 b3994ec5 2003-12-11 devnull #include <keyboard.h>
8 b3994ec5 2003-12-11 devnull #include <frame.h>
9 b3994ec5 2003-12-11 devnull #include <fcall.h>
10 b3994ec5 2003-12-11 devnull #include <plumb.h>
11 67dbeee5 2017-10-10 rsc #include <libsec.h>
12 b3994ec5 2003-12-11 devnull #include "dat.h"
13 b3994ec5 2003-12-11 devnull #include "fns.h"
15 b3994ec5 2003-12-11 devnull Rangeset sel;
16 b3994ec5 2003-12-11 devnull Rune *lastregexp;
19 b3994ec5 2003-12-11 devnull * Machine Information
21 b3994ec5 2003-12-11 devnull typedef struct Inst Inst;
22 b3994ec5 2003-12-11 devnull struct Inst
24 36d9b90c 2010-07-14 rsc uint type; /* < OPERATOR ==> literal, otherwise action */
27 b3994ec5 2003-12-11 devnull int subid;
28 b3994ec5 2003-12-11 devnull int class;
29 b3994ec5 2003-12-11 devnull Inst *other;
30 b3994ec5 2003-12-11 devnull Inst *right;
33 b3994ec5 2003-12-11 devnull Inst *left;
34 b3994ec5 2003-12-11 devnull Inst *next;
38 b3994ec5 2003-12-11 devnull #define NPROG 1024
39 b3994ec5 2003-12-11 devnull Inst program[NPROG];
40 b3994ec5 2003-12-11 devnull Inst *progp;
41 b3994ec5 2003-12-11 devnull Inst *startinst; /* First inst. of program; might not be program[0] */
42 b3994ec5 2003-12-11 devnull Inst *bstartinst; /* same for backwards machine */
43 b3994ec5 2003-12-11 devnull Channel *rechan; /* chan(Inst*) */
45 b3994ec5 2003-12-11 devnull typedef struct Ilist Ilist;
46 b3994ec5 2003-12-11 devnull struct Ilist
48 b3994ec5 2003-12-11 devnull Inst *inst; /* Instruction of the thread */
49 b3994ec5 2003-12-11 devnull Rangeset se;
50 b3994ec5 2003-12-11 devnull uint startp; /* first char of match */
53 c99ef336 2007-06-09 devnull #define NLIST 127
55 b3994ec5 2003-12-11 devnull Ilist *tl, *nl; /* This list, next list */
56 c99ef336 2007-06-09 devnull Ilist list[2][NLIST+1]; /* +1 for trailing null */
57 b3994ec5 2003-12-11 devnull static Rangeset sempty;
60 b3994ec5 2003-12-11 devnull * Actions and Tokens
62 36d9b90c 2010-07-14 rsc * 0x10000xx are operators, value == precedence
63 36d9b90c 2010-07-14 rsc * 0x20000xx are tokens, i.e. operands for operators
65 36d9b90c 2010-07-14 rsc #define OPERATOR 0x1000000 /* Bit set in all operators */
66 36d9b90c 2010-07-14 rsc #define START (OPERATOR+0) /* Start, used for marker on stack */
67 36d9b90c 2010-07-14 rsc #define RBRA (OPERATOR+1) /* Right bracket, ) */
68 36d9b90c 2010-07-14 rsc #define LBRA (OPERATOR+2) /* Left bracket, ( */
69 36d9b90c 2010-07-14 rsc #define OR (OPERATOR+3) /* Alternation, | */
70 36d9b90c 2010-07-14 rsc #define CAT (OPERATOR+4) /* Concatentation, implicit operator */
71 36d9b90c 2010-07-14 rsc #define STAR (OPERATOR+5) /* Closure, * */
72 36d9b90c 2010-07-14 rsc #define PLUS (OPERATOR+6) /* a+ == aa* */
73 36d9b90c 2010-07-14 rsc #define QUEST (OPERATOR+7) /* a? == a|nothing, i.e. 0 or 1 a's */
74 36d9b90c 2010-07-14 rsc #define ANY 0x2000000 /* Any character but newline, . */
75 36d9b90c 2010-07-14 rsc #define NOP (ANY+1) /* No operation, internal use only */
76 36d9b90c 2010-07-14 rsc #define BOL (ANY+2) /* Beginning of line, ^ */
77 36d9b90c 2010-07-14 rsc #define EOL (ANY+3) /* End of line, $ */
78 36d9b90c 2010-07-14 rsc #define CCLASS (ANY+4) /* Character class, [] */
79 36d9b90c 2010-07-14 rsc #define NCCLASS (ANY+5) /* Negated character class, [^] */
80 36d9b90c 2010-07-14 rsc #define END (ANY+0x77) /* Terminate: match found */
82 36d9b90c 2010-07-14 rsc #define ISATOR OPERATOR
83 36d9b90c 2010-07-14 rsc #define ISAND ANY
85 36d9b90c 2010-07-14 rsc #define QUOTED 0x4000000 /* Bit set for \-ed lex characters */
88 b3994ec5 2003-12-11 devnull * Parser Information
90 b3994ec5 2003-12-11 devnull typedef struct Node Node;
91 b3994ec5 2003-12-11 devnull struct Node
93 b3994ec5 2003-12-11 devnull Inst *first;
94 b3994ec5 2003-12-11 devnull Inst *last;
97 b3994ec5 2003-12-11 devnull #define NSTACK 20
98 b3994ec5 2003-12-11 devnull Node andstack[NSTACK];
99 b3994ec5 2003-12-11 devnull Node *andp;
100 b3994ec5 2003-12-11 devnull int atorstack[NSTACK];
101 b3994ec5 2003-12-11 devnull int *atorp;
102 b3994ec5 2003-12-11 devnull int lastwasand; /* Last token was operand */
103 b3994ec5 2003-12-11 devnull int cursubid;
104 b3994ec5 2003-12-11 devnull int subidstack[NSTACK];
105 b3994ec5 2003-12-11 devnull int *subidp;
106 b3994ec5 2003-12-11 devnull int backwards;
107 b3994ec5 2003-12-11 devnull int nbra;
108 b3994ec5 2003-12-11 devnull Rune *exprp; /* pointer to next character in source expression */
109 b3994ec5 2003-12-11 devnull #define DCLASS 10 /* allocation increment */
110 b3994ec5 2003-12-11 devnull int nclass; /* number active */
111 b3994ec5 2003-12-11 devnull int Nclass; /* high water mark */
112 b3994ec5 2003-12-11 devnull Rune **class;
113 b3994ec5 2003-12-11 devnull int negateclass;
115 c99ef336 2007-06-09 devnull int addinst(Ilist *l, Inst *inst, Rangeset *sep);
116 b3994ec5 2003-12-11 devnull void newmatch(Rangeset*);
117 b3994ec5 2003-12-11 devnull void bnewmatch(Rangeset*);
118 b3994ec5 2003-12-11 devnull void pushand(Inst*, Inst*);
119 b3994ec5 2003-12-11 devnull void pushator(int);
120 b3994ec5 2003-12-11 devnull Node *popand(int);
121 b3994ec5 2003-12-11 devnull int popator(void);
122 b3994ec5 2003-12-11 devnull void startlex(Rune*);
123 b3994ec5 2003-12-11 devnull int lex(void);
124 b3994ec5 2003-12-11 devnull void operator(int);
125 b3994ec5 2003-12-11 devnull void operand(int);
126 b3994ec5 2003-12-11 devnull void evaluntil(int);
127 b3994ec5 2003-12-11 devnull void optimize(Inst*);
128 b3994ec5 2003-12-11 devnull void bldcclass(void);
131 b3994ec5 2003-12-11 devnull rxinit(void)
133 b3994ec5 2003-12-11 devnull rechan = chancreate(sizeof(Inst*), 0);
134 334cb1e9 2004-12-27 devnull chansetname(rechan, "rechan");
135 b3994ec5 2003-12-11 devnull lastregexp = runemalloc(1);
139 b3994ec5 2003-12-11 devnull regerror(char *e)
141 b3994ec5 2003-12-11 devnull lastregexp[0] = 0;
142 b3994ec5 2003-12-11 devnull warning(nil, "regexp: %s\n", e);
143 b3994ec5 2003-12-11 devnull sendp(rechan, nil);
144 b3994ec5 2003-12-11 devnull threadexits(nil);
148 b3994ec5 2003-12-11 devnull newinst(int t)
150 b3994ec5 2003-12-11 devnull if(progp >= &program[NPROG])
151 b3994ec5 2003-12-11 devnull regerror("expression too long");
152 b3994ec5 2003-12-11 devnull progp->type = t;
153 b3994ec5 2003-12-11 devnull progp->u1.left = nil;
154 b3994ec5 2003-12-11 devnull progp->u.right = nil;
155 b3994ec5 2003-12-11 devnull return progp++;
159 b3994ec5 2003-12-11 devnull realcompile(void *arg)
161 b3994ec5 2003-12-11 devnull int token;
162 b3994ec5 2003-12-11 devnull Rune *s;
164 b3994ec5 2003-12-11 devnull threadsetname("regcomp");
165 b3994ec5 2003-12-11 devnull s = arg;
166 b3994ec5 2003-12-11 devnull startlex(s);
167 b3994ec5 2003-12-11 devnull atorp = atorstack;
168 b3994ec5 2003-12-11 devnull andp = andstack;
169 b3994ec5 2003-12-11 devnull subidp = subidstack;
170 b3994ec5 2003-12-11 devnull cursubid = 0;
171 b3994ec5 2003-12-11 devnull lastwasand = FALSE;
172 b3994ec5 2003-12-11 devnull /* Start with a low priority operator to prime parser */
173 b3994ec5 2003-12-11 devnull pushator(START-1);
174 b3994ec5 2003-12-11 devnull while((token=lex()) != END){
175 b3994ec5 2003-12-11 devnull if((token&ISATOR) == OPERATOR)
176 b3994ec5 2003-12-11 devnull operator(token);
178 b3994ec5 2003-12-11 devnull operand(token);
180 b3994ec5 2003-12-11 devnull /* Close with a low priority operator */
181 b3994ec5 2003-12-11 devnull evaluntil(START);
182 b3994ec5 2003-12-11 devnull /* Force END */
183 b3994ec5 2003-12-11 devnull operand(END);
184 b3994ec5 2003-12-11 devnull evaluntil(START);
185 b3994ec5 2003-12-11 devnull if(nbra)
186 b3994ec5 2003-12-11 devnull regerror("unmatched `('");
187 b3994ec5 2003-12-11 devnull --andp; /* points to first and only operand */
188 b3994ec5 2003-12-11 devnull sendp(rechan, andp->first);
189 b3994ec5 2003-12-11 devnull threadexits(nil);
192 b3994ec5 2003-12-11 devnull /* r is null terminated */
194 b3994ec5 2003-12-11 devnull rxcompile(Rune *r)
196 b3994ec5 2003-12-11 devnull int i, nr;
197 b3994ec5 2003-12-11 devnull Inst *oprogp;
199 b3994ec5 2003-12-11 devnull nr = runestrlen(r)+1;
200 b3994ec5 2003-12-11 devnull if(runeeq(lastregexp, runestrlen(lastregexp)+1, r, nr)==TRUE)
201 b3994ec5 2003-12-11 devnull return TRUE;
202 b3994ec5 2003-12-11 devnull lastregexp[0] = 0;
203 b3994ec5 2003-12-11 devnull for(i=0; i<nclass; i++)
204 b3994ec5 2003-12-11 devnull free(class[i]);
205 b3994ec5 2003-12-11 devnull nclass = 0;
206 b3994ec5 2003-12-11 devnull progp = program;
207 b3994ec5 2003-12-11 devnull backwards = FALSE;
208 b3994ec5 2003-12-11 devnull bstartinst = nil;
209 b3994ec5 2003-12-11 devnull threadcreate(realcompile, r, STACK);
210 b3994ec5 2003-12-11 devnull startinst = recvp(rechan);
211 b3994ec5 2003-12-11 devnull if(startinst == nil)
212 b3994ec5 2003-12-11 devnull return FALSE;
213 b3994ec5 2003-12-11 devnull optimize(program);
214 b3994ec5 2003-12-11 devnull oprogp = progp;
215 b3994ec5 2003-12-11 devnull backwards = TRUE;
216 b3994ec5 2003-12-11 devnull threadcreate(realcompile, r, STACK);
217 b3994ec5 2003-12-11 devnull bstartinst = recvp(rechan);
218 b3994ec5 2003-12-11 devnull if(bstartinst == nil)
219 b3994ec5 2003-12-11 devnull return FALSE;
220 b3994ec5 2003-12-11 devnull optimize(oprogp);
221 b3994ec5 2003-12-11 devnull lastregexp = runerealloc(lastregexp, nr);
222 b3994ec5 2003-12-11 devnull runemove(lastregexp, r, nr);
223 b3994ec5 2003-12-11 devnull return TRUE;
227 b3994ec5 2003-12-11 devnull operand(int t)
229 b3994ec5 2003-12-11 devnull Inst *i;
230 b3994ec5 2003-12-11 devnull if(lastwasand)
231 b3994ec5 2003-12-11 devnull operator(CAT); /* catenate is implicit */
232 b3994ec5 2003-12-11 devnull i = newinst(t);
233 b3994ec5 2003-12-11 devnull if(t == CCLASS){
234 b3994ec5 2003-12-11 devnull if(negateclass)
235 b3994ec5 2003-12-11 devnull i->type = NCCLASS; /* UGH */
236 b3994ec5 2003-12-11 devnull i->u.class = nclass-1; /* UGH */
238 b3994ec5 2003-12-11 devnull pushand(i, i);
239 b3994ec5 2003-12-11 devnull lastwasand = TRUE;
243 b3994ec5 2003-12-11 devnull operator(int t)
245 b3994ec5 2003-12-11 devnull if(t==RBRA && --nbra<0)
246 b3994ec5 2003-12-11 devnull regerror("unmatched `)'");
247 b3994ec5 2003-12-11 devnull if(t==LBRA){
248 b3994ec5 2003-12-11 devnull cursubid++; /* silently ignored */
250 b3994ec5 2003-12-11 devnull if(lastwasand)
251 b3994ec5 2003-12-11 devnull operator(CAT);
253 b3994ec5 2003-12-11 devnull evaluntil(t);
254 b3994ec5 2003-12-11 devnull if(t!=RBRA)
255 b3994ec5 2003-12-11 devnull pushator(t);
256 b3994ec5 2003-12-11 devnull lastwasand = FALSE;
257 b3994ec5 2003-12-11 devnull if(t==STAR || t==QUEST || t==PLUS || t==RBRA)
258 b3994ec5 2003-12-11 devnull lastwasand = TRUE; /* these look like operands */
262 b3994ec5 2003-12-11 devnull pushand(Inst *f, Inst *l)
264 b3994ec5 2003-12-11 devnull if(andp >= &andstack[NSTACK])
265 b3994ec5 2003-12-11 devnull error("operand stack overflow");
266 b3994ec5 2003-12-11 devnull andp->first = f;
267 b3994ec5 2003-12-11 devnull andp->last = l;
272 b3994ec5 2003-12-11 devnull pushator(int t)
274 b3994ec5 2003-12-11 devnull if(atorp >= &atorstack[NSTACK])
275 b3994ec5 2003-12-11 devnull error("operator stack overflow");
276 b3994ec5 2003-12-11 devnull *atorp++=t;
277 b3994ec5 2003-12-11 devnull if(cursubid >= NRange)
278 b3994ec5 2003-12-11 devnull *subidp++= -1;
280 b3994ec5 2003-12-11 devnull *subidp++=cursubid;
284 b3994ec5 2003-12-11 devnull popand(int op)
286 b3994ec5 2003-12-11 devnull char buf[64];
288 b3994ec5 2003-12-11 devnull if(andp <= &andstack[0])
290 b3994ec5 2003-12-11 devnull sprint(buf, "missing operand for %c", op);
291 b3994ec5 2003-12-11 devnull regerror(buf);
293 b3994ec5 2003-12-11 devnull regerror("malformed regexp");
294 b3994ec5 2003-12-11 devnull return --andp;
298 b3994ec5 2003-12-11 devnull popator()
300 b3994ec5 2003-12-11 devnull if(atorp <= &atorstack[0])
301 b3994ec5 2003-12-11 devnull error("operator stack underflow");
302 b3994ec5 2003-12-11 devnull --subidp;
303 b3994ec5 2003-12-11 devnull return *--atorp;
307 b3994ec5 2003-12-11 devnull evaluntil(int pri)
309 b3994ec5 2003-12-11 devnull Node *op1, *op2, *t;
310 b3994ec5 2003-12-11 devnull Inst *inst1, *inst2;
312 b3994ec5 2003-12-11 devnull while(pri==RBRA || atorp[-1]>=pri){
313 b3994ec5 2003-12-11 devnull switch(popator()){
314 b3994ec5 2003-12-11 devnull case LBRA:
315 b3994ec5 2003-12-11 devnull op1 = popand('(');
316 b3994ec5 2003-12-11 devnull inst2 = newinst(RBRA);
317 b3994ec5 2003-12-11 devnull inst2->u.subid = *subidp;
318 b3994ec5 2003-12-11 devnull op1->last->u1.next = inst2;
319 b3994ec5 2003-12-11 devnull inst1 = newinst(LBRA);
320 b3994ec5 2003-12-11 devnull inst1->u.subid = *subidp;
321 b3994ec5 2003-12-11 devnull inst1->u1.next = op1->first;
322 b3994ec5 2003-12-11 devnull pushand(inst1, inst2);
323 b3994ec5 2003-12-11 devnull return; /* must have been RBRA */
324 b3994ec5 2003-12-11 devnull default:
325 b3994ec5 2003-12-11 devnull error("unknown regexp operator");
327 b3994ec5 2003-12-11 devnull case OR:
328 b3994ec5 2003-12-11 devnull op2 = popand('|');
329 b3994ec5 2003-12-11 devnull op1 = popand('|');
330 b3994ec5 2003-12-11 devnull inst2 = newinst(NOP);
331 b3994ec5 2003-12-11 devnull op2->last->u1.next = inst2;
332 b3994ec5 2003-12-11 devnull op1->last->u1.next = inst2;
333 b3994ec5 2003-12-11 devnull inst1 = newinst(OR);
334 b3994ec5 2003-12-11 devnull inst1->u.right = op1->first;
335 b3994ec5 2003-12-11 devnull inst1->u1.left = op2->first;
336 b3994ec5 2003-12-11 devnull pushand(inst1, inst2);
338 b3994ec5 2003-12-11 devnull case CAT:
339 b3994ec5 2003-12-11 devnull op2 = popand(0);
340 b3994ec5 2003-12-11 devnull op1 = popand(0);
341 b3994ec5 2003-12-11 devnull if(backwards && op2->first->type!=END){
342 b3994ec5 2003-12-11 devnull t = op1;
343 b3994ec5 2003-12-11 devnull op1 = op2;
344 b3994ec5 2003-12-11 devnull op2 = t;
346 b3994ec5 2003-12-11 devnull op1->last->u1.next = op2->first;
347 b3994ec5 2003-12-11 devnull pushand(op1->first, op2->last);
349 b3994ec5 2003-12-11 devnull case STAR:
350 b3994ec5 2003-12-11 devnull op2 = popand('*');
351 b3994ec5 2003-12-11 devnull inst1 = newinst(OR);
352 b3994ec5 2003-12-11 devnull op2->last->u1.next = inst1;
353 b3994ec5 2003-12-11 devnull inst1->u.right = op2->first;
354 b3994ec5 2003-12-11 devnull pushand(inst1, inst1);
356 b3994ec5 2003-12-11 devnull case PLUS:
357 b3994ec5 2003-12-11 devnull op2 = popand('+');
358 b3994ec5 2003-12-11 devnull inst1 = newinst(OR);
359 b3994ec5 2003-12-11 devnull op2->last->u1.next = inst1;
360 b3994ec5 2003-12-11 devnull inst1->u.right = op2->first;
361 b3994ec5 2003-12-11 devnull pushand(op2->first, inst1);
363 b3994ec5 2003-12-11 devnull case QUEST:
364 b3994ec5 2003-12-11 devnull op2 = popand('?');
365 b3994ec5 2003-12-11 devnull inst1 = newinst(OR);
366 b3994ec5 2003-12-11 devnull inst2 = newinst(NOP);
367 b3994ec5 2003-12-11 devnull inst1->u1.left = inst2;
368 b3994ec5 2003-12-11 devnull inst1->u.right = op2->first;
369 b3994ec5 2003-12-11 devnull op2->last->u1.next = inst2;
370 b3994ec5 2003-12-11 devnull pushand(inst1, inst2);
378 b3994ec5 2003-12-11 devnull optimize(Inst *start)
380 b3994ec5 2003-12-11 devnull Inst *inst, *target;
382 b3994ec5 2003-12-11 devnull for(inst=start; inst->type!=END; inst++){
383 b3994ec5 2003-12-11 devnull target = inst->u1.next;
384 b3994ec5 2003-12-11 devnull while(target->type == NOP)
385 b3994ec5 2003-12-11 devnull target = target->u1.next;
386 b3994ec5 2003-12-11 devnull inst->u1.next = target;
391 b3994ec5 2003-12-11 devnull startlex(Rune *s)
393 b3994ec5 2003-12-11 devnull exprp = s;
394 b3994ec5 2003-12-11 devnull nbra = 0;
399 b3994ec5 2003-12-11 devnull lex(void){
402 b3994ec5 2003-12-11 devnull c = *exprp++;
403 b3994ec5 2003-12-11 devnull switch(c){
404 b3994ec5 2003-12-11 devnull case '\\':
405 b3994ec5 2003-12-11 devnull if(*exprp)
406 b3994ec5 2003-12-11 devnull if((c= *exprp++)=='n')
410 b3994ec5 2003-12-11 devnull c = END;
411 b3994ec5 2003-12-11 devnull --exprp; /* In case we come here again */
413 b3994ec5 2003-12-11 devnull case '*':
414 b3994ec5 2003-12-11 devnull c = STAR;
416 b3994ec5 2003-12-11 devnull case '?':
417 b3994ec5 2003-12-11 devnull c = QUEST;
419 b3994ec5 2003-12-11 devnull case '+':
420 b3994ec5 2003-12-11 devnull c = PLUS;
422 b3994ec5 2003-12-11 devnull case '|':
425 b3994ec5 2003-12-11 devnull case '.':
426 b3994ec5 2003-12-11 devnull c = ANY;
428 b3994ec5 2003-12-11 devnull case '(':
429 b3994ec5 2003-12-11 devnull c = LBRA;
431 b3994ec5 2003-12-11 devnull case ')':
432 b3994ec5 2003-12-11 devnull c = RBRA;
434 b3994ec5 2003-12-11 devnull case '^':
435 b3994ec5 2003-12-11 devnull c = BOL;
437 b3994ec5 2003-12-11 devnull case '$':
438 b3994ec5 2003-12-11 devnull c = EOL;
440 b3994ec5 2003-12-11 devnull case '[':
441 b3994ec5 2003-12-11 devnull c = CCLASS;
442 b3994ec5 2003-12-11 devnull bldcclass();
445 b3994ec5 2003-12-11 devnull return c;
449 b3994ec5 2003-12-11 devnull nextrec(void)
451 b3994ec5 2003-12-11 devnull if(exprp[0]==0 || (exprp[0]=='\\' && exprp[1]==0))
452 b3994ec5 2003-12-11 devnull regerror("malformed `[]'");
453 b3994ec5 2003-12-11 devnull if(exprp[0] == '\\'){
454 b3994ec5 2003-12-11 devnull exprp++;
455 b3994ec5 2003-12-11 devnull if(*exprp=='n'){
456 b3994ec5 2003-12-11 devnull exprp++;
457 b3994ec5 2003-12-11 devnull return '\n';
459 36d9b90c 2010-07-14 rsc return *exprp++|QUOTED;
461 b3994ec5 2003-12-11 devnull return *exprp++;
465 b3994ec5 2003-12-11 devnull bldcclass(void)
467 b3994ec5 2003-12-11 devnull int c1, c2, n, na;
468 b3994ec5 2003-12-11 devnull Rune *classp;
470 b3994ec5 2003-12-11 devnull classp = runemalloc(DCLASS);
472 b3994ec5 2003-12-11 devnull na = DCLASS;
473 b3994ec5 2003-12-11 devnull /* we have already seen the '[' */
474 b3994ec5 2003-12-11 devnull if(*exprp == '^'){
475 b3994ec5 2003-12-11 devnull classp[n++] = '\n'; /* don't match newline in negate case */
476 b3994ec5 2003-12-11 devnull negateclass = TRUE;
477 b3994ec5 2003-12-11 devnull exprp++;
479 b3994ec5 2003-12-11 devnull negateclass = FALSE;
480 b3994ec5 2003-12-11 devnull while((c1 = nextrec()) != ']'){
481 b3994ec5 2003-12-11 devnull if(c1 == '-'){
483 b3994ec5 2003-12-11 devnull free(classp);
484 b3994ec5 2003-12-11 devnull regerror("malformed `[]'");
486 b3994ec5 2003-12-11 devnull if(n+4 >= na){ /* 3 runes plus NUL */
487 b3994ec5 2003-12-11 devnull na += DCLASS;
488 b3994ec5 2003-12-11 devnull classp = runerealloc(classp, na);
490 b3994ec5 2003-12-11 devnull if(*exprp == '-'){
491 b3994ec5 2003-12-11 devnull exprp++; /* eat '-' */
492 b3994ec5 2003-12-11 devnull if((c2 = nextrec()) == ']')
493 b3994ec5 2003-12-11 devnull goto Error;
494 0cadb430 2009-09-11 russcox classp[n+0] = Runemax;
495 b3994ec5 2003-12-11 devnull classp[n+1] = c1;
496 b3994ec5 2003-12-11 devnull classp[n+2] = c2;
499 36d9b90c 2010-07-14 rsc classp[n++] = c1 & ~QUOTED;
501 b3994ec5 2003-12-11 devnull classp[n] = 0;
502 b3994ec5 2003-12-11 devnull if(nclass == Nclass){
503 b3994ec5 2003-12-11 devnull Nclass += DCLASS;
504 b3994ec5 2003-12-11 devnull class = realloc(class, Nclass*sizeof(Rune*));
506 b3994ec5 2003-12-11 devnull class[nclass++] = classp;
510 b3994ec5 2003-12-11 devnull classmatch(int classno, int c, int negate)
512 b3994ec5 2003-12-11 devnull Rune *p;
514 b3994ec5 2003-12-11 devnull p = class[classno];
515 b3994ec5 2003-12-11 devnull while(*p){
516 0cadb430 2009-09-11 russcox if(*p == Runemax){
517 b3994ec5 2003-12-11 devnull if(p[1]<=c && c<=p[2])
518 b3994ec5 2003-12-11 devnull return !negate;
520 b3994ec5 2003-12-11 devnull }else if(*p++ == c)
521 b3994ec5 2003-12-11 devnull return !negate;
523 b3994ec5 2003-12-11 devnull return negate;
527 73778bae 2007-12-07 rsc * Note optimization in addinst:
528 73778bae 2007-12-07 rsc * *l must be pending when addinst called; if *l has been looked
529 73778bae 2007-12-07 rsc * at already, the optimization is a bug.
532 6f16e7fc 2007-12-07 rsc addinst(Ilist *l, Inst *inst, Rangeset *sep)
536 73778bae 2007-12-07 rsc for(p = l; p->inst; p++){
537 73778bae 2007-12-07 rsc if(p->inst==inst){
538 73778bae 2007-12-07 rsc if((sep)->r[0].q0 < p->se.r[0].q0)
539 73778bae 2007-12-07 rsc p->se= *sep; /* this would be bug */
540 73778bae 2007-12-07 rsc return 0; /* It's already there */
543 73778bae 2007-12-07 rsc p->inst = inst;
544 73778bae 2007-12-07 rsc p->se= *sep;
545 73778bae 2007-12-07 rsc (p+1)->inst = nil;
550 b3994ec5 2003-12-11 devnull rxnull(void)
552 b3994ec5 2003-12-11 devnull return startinst==nil || bstartinst==nil;
555 b3994ec5 2003-12-11 devnull /* either t!=nil or r!=nil, and we match the string in the appropriate place */
557 b3994ec5 2003-12-11 devnull rxexecute(Text *t, Rune *r, uint startp, uint eof, Rangeset *rp)
559 b3994ec5 2003-12-11 devnull int flag;
560 b3994ec5 2003-12-11 devnull Inst *inst;
561 b3994ec5 2003-12-11 devnull Ilist *tlp;
563 73778bae 2007-12-07 rsc int nnl, ntl;
564 b3994ec5 2003-12-11 devnull int nc, c;
565 b3994ec5 2003-12-11 devnull int wrapped;
566 b3994ec5 2003-12-11 devnull int startchar;
568 b3994ec5 2003-12-11 devnull flag = 0;
569 b3994ec5 2003-12-11 devnull p = startp;
570 b3994ec5 2003-12-11 devnull startchar = 0;
571 b3994ec5 2003-12-11 devnull wrapped = 0;
573 b3994ec5 2003-12-11 devnull if(startinst->type<OPERATOR)
574 b3994ec5 2003-12-11 devnull startchar = startinst->type;
575 b3994ec5 2003-12-11 devnull list[0][0].inst = list[1][0].inst = nil;
576 b3994ec5 2003-12-11 devnull sel.r[0].q0 = -1;
577 b3994ec5 2003-12-11 devnull if(t != nil)
578 b3994ec5 2003-12-11 devnull nc = t->file->b.nc;
580 b3994ec5 2003-12-11 devnull nc = runestrlen(r);
581 b3994ec5 2003-12-11 devnull /* Execute machine once for each character */
582 b3994ec5 2003-12-11 devnull for(;;p++){
584 b3994ec5 2003-12-11 devnull if(p>=eof || p>=nc){
585 b3994ec5 2003-12-11 devnull switch(wrapped++){
586 b3994ec5 2003-12-11 devnull case 0: /* let loop run one more click */
589 b3994ec5 2003-12-11 devnull case 1: /* expired; wrap to beginning */
590 b3994ec5 2003-12-11 devnull if(sel.r[0].q0>=0 || eof!=Infinity)
591 b3994ec5 2003-12-11 devnull goto Return;
592 b3994ec5 2003-12-11 devnull list[0][0].inst = list[1][0].inst = nil;
594 b3994ec5 2003-12-11 devnull goto doloop;
595 b3994ec5 2003-12-11 devnull default:
596 b3994ec5 2003-12-11 devnull goto Return;
600 73778bae 2007-12-07 rsc if(((wrapped && p>=startp) || sel.r[0].q0>0) && nnl==0)
602 b3994ec5 2003-12-11 devnull if(t != nil)
603 b3994ec5 2003-12-11 devnull c = textreadc(t, p);
605 b3994ec5 2003-12-11 devnull c = r[p];
607 b3994ec5 2003-12-11 devnull /* fast check for first char */
608 73778bae 2007-12-07 rsc if(startchar && nnl==0 && c!=startchar)
609 b3994ec5 2003-12-11 devnull continue;
610 b3994ec5 2003-12-11 devnull tl = list[flag];
611 b3994ec5 2003-12-11 devnull nl = list[flag^=1];
612 b3994ec5 2003-12-11 devnull nl->inst = nil;
615 b3994ec5 2003-12-11 devnull if(sel.r[0].q0<0 && (!wrapped || p<startp || startp==eof)){
616 b3994ec5 2003-12-11 devnull /* Add first instruction to this list */
617 c99ef336 2007-06-09 devnull sempty.r[0].q0 = p;
618 73778bae 2007-12-07 rsc if(addinst(tl, startinst, &sempty))
619 73778bae 2007-12-07 rsc if(++ntl >= NLIST){
620 b3994ec5 2003-12-11 devnull Overflow:
621 b3994ec5 2003-12-11 devnull warning(nil, "regexp list overflow\n");
622 b3994ec5 2003-12-11 devnull sel.r[0].q0 = -1;
623 b3994ec5 2003-12-11 devnull goto Return;
626 b3994ec5 2003-12-11 devnull /* Execute machine until this list is empty */
627 b3994ec5 2003-12-11 devnull for(tlp = tl; inst = tlp->inst; tlp++){ /* assignment = */
628 b3994ec5 2003-12-11 devnull Switchstmt:
629 b3994ec5 2003-12-11 devnull switch(inst->type){
630 b3994ec5 2003-12-11 devnull default: /* regular character */
631 b3994ec5 2003-12-11 devnull if(inst->type==c){
632 b3994ec5 2003-12-11 devnull Addinst:
633 73778bae 2007-12-07 rsc if(addinst(nl, inst->u1.next, &tlp->se))
634 73778bae 2007-12-07 rsc if(++nnl >= NLIST)
635 b3994ec5 2003-12-11 devnull goto Overflow;
638 b3994ec5 2003-12-11 devnull case LBRA:
639 b3994ec5 2003-12-11 devnull if(inst->u.subid>=0)
640 b3994ec5 2003-12-11 devnull tlp->se.r[inst->u.subid].q0 = p;
641 b3994ec5 2003-12-11 devnull inst = inst->u1.next;
642 b3994ec5 2003-12-11 devnull goto Switchstmt;
643 b3994ec5 2003-12-11 devnull case RBRA:
644 b3994ec5 2003-12-11 devnull if(inst->u.subid>=0)
645 b3994ec5 2003-12-11 devnull tlp->se.r[inst->u.subid].q1 = p;
646 b3994ec5 2003-12-11 devnull inst = inst->u1.next;
647 b3994ec5 2003-12-11 devnull goto Switchstmt;
648 b3994ec5 2003-12-11 devnull case ANY:
649 b3994ec5 2003-12-11 devnull if(c!='\n')
650 b3994ec5 2003-12-11 devnull goto Addinst;
652 b3994ec5 2003-12-11 devnull case BOL:
653 b3994ec5 2003-12-11 devnull if(p==0 || (t!=nil && textreadc(t, p-1)=='\n') || (r!=nil && r[p-1]=='\n')){
655 b3994ec5 2003-12-11 devnull inst = inst->u1.next;
656 b3994ec5 2003-12-11 devnull goto Switchstmt;
659 b3994ec5 2003-12-11 devnull case EOL:
660 b3994ec5 2003-12-11 devnull if(c == '\n')
661 b3994ec5 2003-12-11 devnull goto Step;
663 b3994ec5 2003-12-11 devnull case CCLASS:
664 b3994ec5 2003-12-11 devnull if(c>=0 && classmatch(inst->u.class, c, 0))
665 b3994ec5 2003-12-11 devnull goto Addinst;
667 b3994ec5 2003-12-11 devnull case NCCLASS:
668 b3994ec5 2003-12-11 devnull if(c>=0 && classmatch(inst->u.class, c, 1))
669 b3994ec5 2003-12-11 devnull goto Addinst;
671 b3994ec5 2003-12-11 devnull case OR:
672 73778bae 2007-12-07 rsc /* evaluate right choice later */
673 d694fe22 2008-01-30 rsc if(addinst(tlp, inst->u.right, &tlp->se))
674 73778bae 2007-12-07 rsc if(++ntl >= NLIST)
675 73778bae 2007-12-07 rsc goto Overflow;
676 73778bae 2007-12-07 rsc /* efficiency: advance and re-evaluate */
677 73778bae 2007-12-07 rsc inst = inst->u1.left;
678 73778bae 2007-12-07 rsc goto Switchstmt;
679 b3994ec5 2003-12-11 devnull case END: /* Match! */
680 b3994ec5 2003-12-11 devnull tlp->se.r[0].q1 = p;
681 b3994ec5 2003-12-11 devnull newmatch(&tlp->se);
687 b3994ec5 2003-12-11 devnull *rp = sel;
688 b3994ec5 2003-12-11 devnull return sel.r[0].q0 >= 0;
692 b3994ec5 2003-12-11 devnull newmatch(Rangeset *sp)
694 b3994ec5 2003-12-11 devnull if(sel.r[0].q0<0 || sp->r[0].q0<sel.r[0].q0 ||
695 b3994ec5 2003-12-11 devnull (sp->r[0].q0==sel.r[0].q0 && sp->r[0].q1>sel.r[0].q1))
696 b3994ec5 2003-12-11 devnull sel = *sp;
700 b3994ec5 2003-12-11 devnull rxbexecute(Text *t, uint startp, Rangeset *rp)
702 b3994ec5 2003-12-11 devnull int flag;
703 b3994ec5 2003-12-11 devnull Inst *inst;
704 b3994ec5 2003-12-11 devnull Ilist *tlp;
706 73778bae 2007-12-07 rsc int nnl, ntl;
708 b3994ec5 2003-12-11 devnull int wrapped;
709 b3994ec5 2003-12-11 devnull int startchar;
711 b3994ec5 2003-12-11 devnull flag = 0;
713 b3994ec5 2003-12-11 devnull wrapped = 0;
714 b3994ec5 2003-12-11 devnull p = startp;
715 b3994ec5 2003-12-11 devnull startchar = 0;
716 b3994ec5 2003-12-11 devnull if(bstartinst->type<OPERATOR)
717 b3994ec5 2003-12-11 devnull startchar = bstartinst->type;
718 b3994ec5 2003-12-11 devnull list[0][0].inst = list[1][0].inst = nil;
719 b3994ec5 2003-12-11 devnull sel.r[0].q0= -1;
720 b3994ec5 2003-12-11 devnull /* Execute machine once for each character, including terminal NUL */
721 b3994ec5 2003-12-11 devnull for(;;--p){
723 b3994ec5 2003-12-11 devnull if(p <= 0){
724 b3994ec5 2003-12-11 devnull switch(wrapped++){
725 b3994ec5 2003-12-11 devnull case 0: /* let loop run one more click */
728 b3994ec5 2003-12-11 devnull case 1: /* expired; wrap to end */
729 b3994ec5 2003-12-11 devnull if(sel.r[0].q0>=0)
730 b3994ec5 2003-12-11 devnull goto Return;
731 b3994ec5 2003-12-11 devnull list[0][0].inst = list[1][0].inst = nil;
732 b3994ec5 2003-12-11 devnull p = t->file->b.nc;
733 b3994ec5 2003-12-11 devnull goto doloop;
735 b3994ec5 2003-12-11 devnull default:
736 b3994ec5 2003-12-11 devnull goto Return;
740 73778bae 2007-12-07 rsc if(((wrapped && p<=startp) || sel.r[0].q0>0) && nnl==0)
742 b3994ec5 2003-12-11 devnull c = textreadc(t, p-1);
744 b3994ec5 2003-12-11 devnull /* fast check for first char */
745 73778bae 2007-12-07 rsc if(startchar && nnl==0 && c!=startchar)
746 b3994ec5 2003-12-11 devnull continue;
747 b3994ec5 2003-12-11 devnull tl = list[flag];
748 b3994ec5 2003-12-11 devnull nl = list[flag^=1];
749 b3994ec5 2003-12-11 devnull nl->inst = nil;
752 b3994ec5 2003-12-11 devnull if(sel.r[0].q0<0 && (!wrapped || p>startp)){
753 b3994ec5 2003-12-11 devnull /* Add first instruction to this list */
754 73778bae 2007-12-07 rsc /* the minus is so the optimizations in addinst work */
755 73778bae 2007-12-07 rsc sempty.r[0].q0 = -p;
756 73778bae 2007-12-07 rsc if(addinst(tl, bstartinst, &sempty))
757 73778bae 2007-12-07 rsc if(++ntl >= NLIST){
758 b3994ec5 2003-12-11 devnull Overflow:
759 b3994ec5 2003-12-11 devnull warning(nil, "regexp list overflow\n");
760 b3994ec5 2003-12-11 devnull sel.r[0].q0 = -1;
761 b3994ec5 2003-12-11 devnull goto Return;
764 b3994ec5 2003-12-11 devnull /* Execute machine until this list is empty */
765 b3994ec5 2003-12-11 devnull for(tlp = tl; inst = tlp->inst; tlp++){ /* assignment = */
766 b3994ec5 2003-12-11 devnull Switchstmt:
767 b3994ec5 2003-12-11 devnull switch(inst->type){
768 b3994ec5 2003-12-11 devnull default: /* regular character */
769 b3994ec5 2003-12-11 devnull if(inst->type == c){
770 b3994ec5 2003-12-11 devnull Addinst:
771 73778bae 2007-12-07 rsc if(addinst(nl, inst->u1.next, &tlp->se))
772 73778bae 2007-12-07 rsc if(++nnl >= NLIST)
773 b3994ec5 2003-12-11 devnull goto Overflow;
776 b3994ec5 2003-12-11 devnull case LBRA:
777 b3994ec5 2003-12-11 devnull if(inst->u.subid>=0)
778 b3994ec5 2003-12-11 devnull tlp->se.r[inst->u.subid].q0 = p;
779 b3994ec5 2003-12-11 devnull inst = inst->u1.next;
780 b3994ec5 2003-12-11 devnull goto Switchstmt;
781 b3994ec5 2003-12-11 devnull case RBRA:
782 b3994ec5 2003-12-11 devnull if(inst->u.subid >= 0)
783 b3994ec5 2003-12-11 devnull tlp->se.r[inst->u.subid].q1 = p;
784 b3994ec5 2003-12-11 devnull inst = inst->u1.next;
785 b3994ec5 2003-12-11 devnull goto Switchstmt;
786 b3994ec5 2003-12-11 devnull case ANY:
787 b3994ec5 2003-12-11 devnull if(c != '\n')
788 b3994ec5 2003-12-11 devnull goto Addinst;
790 b3994ec5 2003-12-11 devnull case BOL:
791 b3994ec5 2003-12-11 devnull if(c=='\n' || p==0){
793 b3994ec5 2003-12-11 devnull inst = inst->u1.next;
794 b3994ec5 2003-12-11 devnull goto Switchstmt;
797 b3994ec5 2003-12-11 devnull case EOL:
798 b3994ec5 2003-12-11 devnull if(p<t->file->b.nc && textreadc(t, p)=='\n')
799 b3994ec5 2003-12-11 devnull goto Step;
801 b3994ec5 2003-12-11 devnull case CCLASS:
802 b3994ec5 2003-12-11 devnull if(c>0 && classmatch(inst->u.class, c, 0))
803 b3994ec5 2003-12-11 devnull goto Addinst;
805 b3994ec5 2003-12-11 devnull case NCCLASS:
806 b3994ec5 2003-12-11 devnull if(c>0 && classmatch(inst->u.class, c, 1))
807 b3994ec5 2003-12-11 devnull goto Addinst;
809 b3994ec5 2003-12-11 devnull case OR:
810 73778bae 2007-12-07 rsc /* evaluate right choice later */
811 73778bae 2007-12-07 rsc if(addinst(tl, inst->u.right, &tlp->se))
812 73778bae 2007-12-07 rsc if(++ntl >= NLIST)
813 73778bae 2007-12-07 rsc goto Overflow;
814 73778bae 2007-12-07 rsc /* efficiency: advance and re-evaluate */
815 73778bae 2007-12-07 rsc inst = inst->u1.left;
816 73778bae 2007-12-07 rsc goto Switchstmt;
817 b3994ec5 2003-12-11 devnull case END: /* Match! */
818 73778bae 2007-12-07 rsc tlp->se.r[0].q0 = -tlp->se.r[0].q0; /* minus sign */
819 b3994ec5 2003-12-11 devnull tlp->se.r[0].q1 = p;
820 b3994ec5 2003-12-11 devnull bnewmatch(&tlp->se);
826 b3994ec5 2003-12-11 devnull *rp = sel;
827 b3994ec5 2003-12-11 devnull return sel.r[0].q0 >= 0;
831 b3994ec5 2003-12-11 devnull bnewmatch(Rangeset *sp)
835 b3994ec5 2003-12-11 devnull if(sel.r[0].q0<0 || sp->r[0].q0>sel.r[0].q1 || (sp->r[0].q0==sel.r[0].q1 && sp->r[0].q1<sel.r[0].q0))
836 b3994ec5 2003-12-11 devnull for(i = 0; i<NRange; i++){ /* note the reversal; q0<=q1 */
837 b3994ec5 2003-12-11 devnull sel.r[i].q0 = sp->r[i].q1;
838 b3994ec5 2003-12-11 devnull sel.r[i].q1 = sp->r[i].q0;