1 76193d7c 2003-09-30 devnull #include "sam.h"
3 76193d7c 2003-09-30 devnull Rangeset sel;
4 76193d7c 2003-09-30 devnull String lastregexp;
6 76193d7c 2003-09-30 devnull * Machine Information
8 76193d7c 2003-09-30 devnull typedef struct Inst Inst;
10 76193d7c 2003-09-30 devnull struct Inst
12 76193d7c 2003-09-30 devnull long type; /* < 0x10000 ==> literal, otherwise action */
14 76193d7c 2003-09-30 devnull int rsid;
15 76193d7c 2003-09-30 devnull int rsubid;
16 76193d7c 2003-09-30 devnull int class;
17 76193d7c 2003-09-30 devnull struct Inst *rother;
18 76193d7c 2003-09-30 devnull struct Inst *rright;
21 76193d7c 2003-09-30 devnull struct Inst *lleft;
22 76193d7c 2003-09-30 devnull struct Inst *lnext;
25 76193d7c 2003-09-30 devnull #define sid r.rsid
26 76193d7c 2003-09-30 devnull #define subid r.rsubid
27 76193d7c 2003-09-30 devnull #define rclass r.class
28 76193d7c 2003-09-30 devnull #define other r.rother
29 76193d7c 2003-09-30 devnull #define right r.rright
30 76193d7c 2003-09-30 devnull #define left l.lleft
31 76193d7c 2003-09-30 devnull #define next l.lnext
33 76193d7c 2003-09-30 devnull #define NPROG 1024
34 76193d7c 2003-09-30 devnull Inst program[NPROG];
35 76193d7c 2003-09-30 devnull Inst *progp;
36 76193d7c 2003-09-30 devnull Inst *startinst; /* First inst. of program; might not be program[0] */
37 76193d7c 2003-09-30 devnull Inst *bstartinst; /* same for backwards machine */
39 76193d7c 2003-09-30 devnull typedef struct Ilist Ilist;
40 76193d7c 2003-09-30 devnull struct Ilist
42 76193d7c 2003-09-30 devnull Inst *inst; /* Instruction of the thread */
43 76193d7c 2003-09-30 devnull Rangeset se;
44 76193d7c 2003-09-30 devnull Posn startp; /* first char of match */
47 c99ef336 2007-06-09 devnull #define NLIST 127
49 76193d7c 2003-09-30 devnull Ilist *tl, *nl; /* This list, next list */
50 c99ef336 2007-06-09 devnull Ilist list[2][NLIST+1]; /* +1 for trailing null */
51 76193d7c 2003-09-30 devnull static Rangeset sempty;
54 76193d7c 2003-09-30 devnull * Actions and Tokens
56 76193d7c 2003-09-30 devnull * 0x100xx are operators, value == precedence
57 76193d7c 2003-09-30 devnull * 0x200xx are tokens, i.e. operands for operators
59 76193d7c 2003-09-30 devnull #define OPERATOR 0x10000 /* Bitmask of all operators */
60 76193d7c 2003-09-30 devnull #define START 0x10000 /* Start, used for marker on stack */
61 76193d7c 2003-09-30 devnull #define RBRA 0x10001 /* Right bracket, ) */
62 76193d7c 2003-09-30 devnull #define LBRA 0x10002 /* Left bracket, ( */
63 76193d7c 2003-09-30 devnull #define OR 0x10003 /* Alternation, | */
64 76193d7c 2003-09-30 devnull #define CAT 0x10004 /* Concatentation, implicit operator */
65 76193d7c 2003-09-30 devnull #define STAR 0x10005 /* Closure, * */
66 76193d7c 2003-09-30 devnull #define PLUS 0x10006 /* a+ == aa* */
67 76193d7c 2003-09-30 devnull #define QUEST 0x10007 /* a? == a|nothing, i.e. 0 or 1 a's */
68 76193d7c 2003-09-30 devnull #define ANY 0x20000 /* Any character but newline, . */
69 76193d7c 2003-09-30 devnull #define NOP 0x20001 /* No operation, internal use only */
70 76193d7c 2003-09-30 devnull #define BOL 0x20002 /* Beginning of line, ^ */
71 76193d7c 2003-09-30 devnull #define EOL 0x20003 /* End of line, $ */
72 76193d7c 2003-09-30 devnull #define CCLASS 0x20004 /* Character class, [] */
73 76193d7c 2003-09-30 devnull #define NCCLASS 0x20005 /* Negated character class, [^] */
74 76193d7c 2003-09-30 devnull #define END 0x20077 /* Terminate: match found */
76 76193d7c 2003-09-30 devnull #define ISATOR 0x10000
77 76193d7c 2003-09-30 devnull #define ISAND 0x20000
80 76193d7c 2003-09-30 devnull * Parser Information
82 76193d7c 2003-09-30 devnull typedef struct Node Node;
83 76193d7c 2003-09-30 devnull struct Node
85 76193d7c 2003-09-30 devnull Inst *first;
86 76193d7c 2003-09-30 devnull Inst *last;
89 76193d7c 2003-09-30 devnull #define NSTACK 20
90 76193d7c 2003-09-30 devnull Node andstack[NSTACK];
91 76193d7c 2003-09-30 devnull Node *andp;
92 76193d7c 2003-09-30 devnull int atorstack[NSTACK];
93 76193d7c 2003-09-30 devnull int *atorp;
94 76193d7c 2003-09-30 devnull int lastwasand; /* Last token was operand */
95 76193d7c 2003-09-30 devnull int cursubid;
96 76193d7c 2003-09-30 devnull int subidstack[NSTACK];
97 76193d7c 2003-09-30 devnull int *subidp;
98 76193d7c 2003-09-30 devnull int backwards;
99 76193d7c 2003-09-30 devnull int nbra;
100 76193d7c 2003-09-30 devnull Rune *exprp; /* pointer to next character in source expression */
101 76193d7c 2003-09-30 devnull #define DCLASS 10 /* allocation increment */
102 76193d7c 2003-09-30 devnull int nclass; /* number active */
103 76193d7c 2003-09-30 devnull int Nclass; /* high water mark */
104 76193d7c 2003-09-30 devnull Rune **class;
105 76193d7c 2003-09-30 devnull int negateclass;
107 c99ef336 2007-06-09 devnull int addinst(Ilist *l, Inst *inst, Rangeset *sep);
108 76193d7c 2003-09-30 devnull void newmatch(Rangeset*);
109 76193d7c 2003-09-30 devnull void bnewmatch(Rangeset*);
110 76193d7c 2003-09-30 devnull void pushand(Inst*, Inst*);
111 76193d7c 2003-09-30 devnull void pushator(int);
112 76193d7c 2003-09-30 devnull Node *popand(int);
113 76193d7c 2003-09-30 devnull int popator(void);
114 76193d7c 2003-09-30 devnull void startlex(Rune*);
115 76193d7c 2003-09-30 devnull int lex(void);
116 76193d7c 2003-09-30 devnull void operator(int);
117 76193d7c 2003-09-30 devnull void operand(int);
118 76193d7c 2003-09-30 devnull void evaluntil(int);
119 76193d7c 2003-09-30 devnull void optimize(Inst*);
120 76193d7c 2003-09-30 devnull void bldcclass(void);
123 76193d7c 2003-09-30 devnull regerror(Err e)
125 76193d7c 2003-09-30 devnull Strzero(&lastregexp);
126 76193d7c 2003-09-30 devnull error(e);
130 76193d7c 2003-09-30 devnull regerror_c(Err e, int c)
132 76193d7c 2003-09-30 devnull Strzero(&lastregexp);
133 76193d7c 2003-09-30 devnull error_c(e, c);
137 76193d7c 2003-09-30 devnull newinst(int t)
139 76193d7c 2003-09-30 devnull if(progp >= &program[NPROG])
140 76193d7c 2003-09-30 devnull regerror(Etoolong);
141 76193d7c 2003-09-30 devnull progp->type = t;
142 76193d7c 2003-09-30 devnull progp->left = 0;
143 76193d7c 2003-09-30 devnull progp->right = 0;
144 76193d7c 2003-09-30 devnull return progp++;
148 76193d7c 2003-09-30 devnull realcompile(Rune *s)
150 76193d7c 2003-09-30 devnull int token;
152 76193d7c 2003-09-30 devnull startlex(s);
153 76193d7c 2003-09-30 devnull atorp = atorstack;
154 76193d7c 2003-09-30 devnull andp = andstack;
155 76193d7c 2003-09-30 devnull subidp = subidstack;
156 76193d7c 2003-09-30 devnull cursubid = 0;
157 76193d7c 2003-09-30 devnull lastwasand = FALSE;
158 76193d7c 2003-09-30 devnull /* Start with a low priority operator to prime parser */
159 76193d7c 2003-09-30 devnull pushator(START-1);
160 76193d7c 2003-09-30 devnull while((token=lex()) != END){
161 76193d7c 2003-09-30 devnull if((token&ISATOR) == OPERATOR)
162 76193d7c 2003-09-30 devnull operator(token);
164 76193d7c 2003-09-30 devnull operand(token);
166 76193d7c 2003-09-30 devnull /* Close with a low priority operator */
167 76193d7c 2003-09-30 devnull evaluntil(START);
168 76193d7c 2003-09-30 devnull /* Force END */
169 76193d7c 2003-09-30 devnull operand(END);
170 76193d7c 2003-09-30 devnull evaluntil(START);
171 76193d7c 2003-09-30 devnull if(nbra)
172 76193d7c 2003-09-30 devnull regerror(Eleftpar);
173 76193d7c 2003-09-30 devnull --andp; /* points to first and only operand */
174 76193d7c 2003-09-30 devnull return andp->first;
178 76193d7c 2003-09-30 devnull compile(String *s)
181 76193d7c 2003-09-30 devnull Inst *oprogp;
183 76193d7c 2003-09-30 devnull if(Strcmp(s, &lastregexp)==0)
185 76193d7c 2003-09-30 devnull for(i=0; i<nclass; i++)
186 76193d7c 2003-09-30 devnull free(class[i]);
187 76193d7c 2003-09-30 devnull nclass = 0;
188 76193d7c 2003-09-30 devnull progp = program;
189 76193d7c 2003-09-30 devnull backwards = FALSE;
190 76193d7c 2003-09-30 devnull startinst = realcompile(s->s);
191 76193d7c 2003-09-30 devnull optimize(program);
192 76193d7c 2003-09-30 devnull oprogp = progp;
193 76193d7c 2003-09-30 devnull backwards = TRUE;
194 76193d7c 2003-09-30 devnull bstartinst = realcompile(s->s);
195 76193d7c 2003-09-30 devnull optimize(oprogp);
196 76193d7c 2003-09-30 devnull Strduplstr(&lastregexp, s);
200 76193d7c 2003-09-30 devnull operand(int t)
202 76193d7c 2003-09-30 devnull Inst *i;
203 76193d7c 2003-09-30 devnull if(lastwasand)
204 76193d7c 2003-09-30 devnull operator(CAT); /* catenate is implicit */
205 76193d7c 2003-09-30 devnull i = newinst(t);
206 76193d7c 2003-09-30 devnull if(t == CCLASS){
207 76193d7c 2003-09-30 devnull if(negateclass)
208 76193d7c 2003-09-30 devnull i->type = NCCLASS; /* UGH */
209 76193d7c 2003-09-30 devnull i->rclass = nclass-1; /* UGH */
211 76193d7c 2003-09-30 devnull pushand(i, i);
212 76193d7c 2003-09-30 devnull lastwasand = TRUE;
216 76193d7c 2003-09-30 devnull operator(int t)
218 76193d7c 2003-09-30 devnull if(t==RBRA && --nbra<0)
219 76193d7c 2003-09-30 devnull regerror(Erightpar);
220 76193d7c 2003-09-30 devnull if(t==LBRA){
222 76193d7c 2003-09-30 devnull * if(++cursubid >= NSUBEXP)
223 76193d7c 2003-09-30 devnull * regerror(Esubexp);
225 76193d7c 2003-09-30 devnull cursubid++; /* silently ignored */
227 76193d7c 2003-09-30 devnull if(lastwasand)
228 76193d7c 2003-09-30 devnull operator(CAT);
230 76193d7c 2003-09-30 devnull evaluntil(t);
231 76193d7c 2003-09-30 devnull if(t!=RBRA)
232 76193d7c 2003-09-30 devnull pushator(t);
233 76193d7c 2003-09-30 devnull lastwasand = FALSE;
234 76193d7c 2003-09-30 devnull if(t==STAR || t==QUEST || t==PLUS || t==RBRA)
235 76193d7c 2003-09-30 devnull lastwasand = TRUE; /* these look like operands */
239 76193d7c 2003-09-30 devnull cant(char *s)
241 76193d7c 2003-09-30 devnull char buf[100];
243 76193d7c 2003-09-30 devnull sprint(buf, "regexp: can't happen: %s", s);
244 76193d7c 2003-09-30 devnull panic(buf);
248 76193d7c 2003-09-30 devnull pushand(Inst *f, Inst *l)
250 76193d7c 2003-09-30 devnull if(andp >= &andstack[NSTACK])
251 76193d7c 2003-09-30 devnull cant("operand stack overflow");
252 76193d7c 2003-09-30 devnull andp->first = f;
253 76193d7c 2003-09-30 devnull andp->last = l;
258 76193d7c 2003-09-30 devnull pushator(int t)
260 76193d7c 2003-09-30 devnull if(atorp >= &atorstack[NSTACK])
261 76193d7c 2003-09-30 devnull cant("operator stack overflow");
262 76193d7c 2003-09-30 devnull *atorp++=t;
263 76193d7c 2003-09-30 devnull if(cursubid >= NSUBEXP)
264 76193d7c 2003-09-30 devnull *subidp++= -1;
266 76193d7c 2003-09-30 devnull *subidp++=cursubid;
270 76193d7c 2003-09-30 devnull popand(int op)
272 76193d7c 2003-09-30 devnull if(andp <= &andstack[0])
274 76193d7c 2003-09-30 devnull regerror_c(Emissop, op);
276 76193d7c 2003-09-30 devnull regerror(Ebadregexp);
277 76193d7c 2003-09-30 devnull return --andp;
281 76193d7c 2003-09-30 devnull popator(void)
283 76193d7c 2003-09-30 devnull if(atorp <= &atorstack[0])
284 76193d7c 2003-09-30 devnull cant("operator stack underflow");
285 76193d7c 2003-09-30 devnull --subidp;
286 76193d7c 2003-09-30 devnull return *--atorp;
290 76193d7c 2003-09-30 devnull evaluntil(int pri)
292 76193d7c 2003-09-30 devnull Node *op1, *op2, *t;
293 76193d7c 2003-09-30 devnull Inst *inst1, *inst2;
295 76193d7c 2003-09-30 devnull while(pri==RBRA || atorp[-1]>=pri){
296 76193d7c 2003-09-30 devnull switch(popator()){
297 76193d7c 2003-09-30 devnull case LBRA:
298 76193d7c 2003-09-30 devnull op1 = popand('(');
299 76193d7c 2003-09-30 devnull inst2 = newinst(RBRA);
300 76193d7c 2003-09-30 devnull inst2->subid = *subidp;
301 76193d7c 2003-09-30 devnull op1->last->next = inst2;
302 76193d7c 2003-09-30 devnull inst1 = newinst(LBRA);
303 76193d7c 2003-09-30 devnull inst1->subid = *subidp;
304 76193d7c 2003-09-30 devnull inst1->next = op1->first;
305 76193d7c 2003-09-30 devnull pushand(inst1, inst2);
306 76193d7c 2003-09-30 devnull return; /* must have been RBRA */
307 76193d7c 2003-09-30 devnull default:
308 76193d7c 2003-09-30 devnull panic("unknown regexp operator");
310 76193d7c 2003-09-30 devnull case OR:
311 76193d7c 2003-09-30 devnull op2 = popand('|');
312 76193d7c 2003-09-30 devnull op1 = popand('|');
313 76193d7c 2003-09-30 devnull inst2 = newinst(NOP);
314 76193d7c 2003-09-30 devnull op2->last->next = inst2;
315 76193d7c 2003-09-30 devnull op1->last->next = inst2;
316 76193d7c 2003-09-30 devnull inst1 = newinst(OR);
317 76193d7c 2003-09-30 devnull inst1->right = op1->first;
318 76193d7c 2003-09-30 devnull inst1->left = op2->first;
319 76193d7c 2003-09-30 devnull pushand(inst1, inst2);
321 76193d7c 2003-09-30 devnull case CAT:
322 76193d7c 2003-09-30 devnull op2 = popand(0);
323 76193d7c 2003-09-30 devnull op1 = popand(0);
324 76193d7c 2003-09-30 devnull if(backwards && op2->first->type!=END)
325 76193d7c 2003-09-30 devnull t = op1, op1 = op2, op2 = t;
326 76193d7c 2003-09-30 devnull op1->last->next = op2->first;
327 76193d7c 2003-09-30 devnull pushand(op1->first, op2->last);
329 76193d7c 2003-09-30 devnull case STAR:
330 76193d7c 2003-09-30 devnull op2 = popand('*');
331 76193d7c 2003-09-30 devnull inst1 = newinst(OR);
332 76193d7c 2003-09-30 devnull op2->last->next = inst1;
333 76193d7c 2003-09-30 devnull inst1->right = op2->first;
334 76193d7c 2003-09-30 devnull pushand(inst1, inst1);
336 76193d7c 2003-09-30 devnull case PLUS:
337 76193d7c 2003-09-30 devnull op2 = popand('+');
338 76193d7c 2003-09-30 devnull inst1 = newinst(OR);
339 76193d7c 2003-09-30 devnull op2->last->next = inst1;
340 76193d7c 2003-09-30 devnull inst1->right = op2->first;
341 76193d7c 2003-09-30 devnull pushand(op2->first, inst1);
343 76193d7c 2003-09-30 devnull case QUEST:
344 76193d7c 2003-09-30 devnull op2 = popand('?');
345 76193d7c 2003-09-30 devnull inst1 = newinst(OR);
346 76193d7c 2003-09-30 devnull inst2 = newinst(NOP);
347 76193d7c 2003-09-30 devnull inst1->left = inst2;
348 76193d7c 2003-09-30 devnull inst1->right = op2->first;
349 76193d7c 2003-09-30 devnull op2->last->next = inst2;
350 76193d7c 2003-09-30 devnull pushand(inst1, inst2);
358 76193d7c 2003-09-30 devnull optimize(Inst *start)
360 76193d7c 2003-09-30 devnull Inst *inst, *target;
362 76193d7c 2003-09-30 devnull for(inst=start; inst->type!=END; inst++){
363 76193d7c 2003-09-30 devnull target = inst->next;
364 76193d7c 2003-09-30 devnull while(target->type == NOP)
365 76193d7c 2003-09-30 devnull target = target->next;
366 76193d7c 2003-09-30 devnull inst->next = target;
370 76193d7c 2003-09-30 devnull #ifdef DEBUG
372 76193d7c 2003-09-30 devnull dumpstack(void){
373 76193d7c 2003-09-30 devnull Node *stk;
374 76193d7c 2003-09-30 devnull int *ip;
376 76193d7c 2003-09-30 devnull dprint("operators\n");
377 76193d7c 2003-09-30 devnull for(ip = atorstack; ip<atorp; ip++)
378 76193d7c 2003-09-30 devnull dprint("0%o\n", *ip);
379 76193d7c 2003-09-30 devnull dprint("operands\n");
380 76193d7c 2003-09-30 devnull for(stk = andstack; stk<andp; stk++)
381 76193d7c 2003-09-30 devnull dprint("0%o\t0%o\n", stk->first->type, stk->last->type);
384 76193d7c 2003-09-30 devnull dump(void){
385 76193d7c 2003-09-30 devnull Inst *l;
387 76193d7c 2003-09-30 devnull l = program;
389 76193d7c 2003-09-30 devnull dprint("%d:\t0%o\t%d\t%d\n", l-program, l->type,
390 76193d7c 2003-09-30 devnull l->left-program, l->right-program);
391 76193d7c 2003-09-30 devnull }while(l++->type);
396 76193d7c 2003-09-30 devnull startlex(Rune *s)
398 76193d7c 2003-09-30 devnull exprp = s;
399 76193d7c 2003-09-30 devnull nbra = 0;
404 76193d7c 2003-09-30 devnull lex(void){
405 76193d7c 2003-09-30 devnull int c= *exprp++;
407 76193d7c 2003-09-30 devnull switch(c){
408 76193d7c 2003-09-30 devnull case '\\':
409 76193d7c 2003-09-30 devnull if(*exprp)
410 76193d7c 2003-09-30 devnull if((c= *exprp++)=='n')
414 76193d7c 2003-09-30 devnull c = END;
415 76193d7c 2003-09-30 devnull --exprp; /* In case we come here again */
417 76193d7c 2003-09-30 devnull case '*':
418 76193d7c 2003-09-30 devnull c = STAR;
420 76193d7c 2003-09-30 devnull case '?':
421 76193d7c 2003-09-30 devnull c = QUEST;
423 76193d7c 2003-09-30 devnull case '+':
424 76193d7c 2003-09-30 devnull c = PLUS;
426 76193d7c 2003-09-30 devnull case '|':
429 76193d7c 2003-09-30 devnull case '.':
430 76193d7c 2003-09-30 devnull c = ANY;
432 76193d7c 2003-09-30 devnull case '(':
433 76193d7c 2003-09-30 devnull c = LBRA;
435 76193d7c 2003-09-30 devnull case ')':
436 76193d7c 2003-09-30 devnull c = RBRA;
438 76193d7c 2003-09-30 devnull case '^':
439 76193d7c 2003-09-30 devnull c = BOL;
441 76193d7c 2003-09-30 devnull case '$':
442 76193d7c 2003-09-30 devnull c = EOL;
444 76193d7c 2003-09-30 devnull case '[':
445 76193d7c 2003-09-30 devnull c = CCLASS;
446 76193d7c 2003-09-30 devnull bldcclass();
449 76193d7c 2003-09-30 devnull return c;
453 76193d7c 2003-09-30 devnull nextrec(void){
454 76193d7c 2003-09-30 devnull if(exprp[0]==0 || (exprp[0]=='\\' && exprp[1]==0))
455 76193d7c 2003-09-30 devnull regerror(Ebadclass);
456 76193d7c 2003-09-30 devnull if(exprp[0] == '\\'){
457 76193d7c 2003-09-30 devnull exprp++;
458 76193d7c 2003-09-30 devnull if(*exprp=='n'){
459 76193d7c 2003-09-30 devnull exprp++;
460 76193d7c 2003-09-30 devnull return '\n';
462 76193d7c 2003-09-30 devnull return *exprp++|0x10000;
464 76193d7c 2003-09-30 devnull return *exprp++;
468 76193d7c 2003-09-30 devnull bldcclass(void)
470 76193d7c 2003-09-30 devnull long c1, c2, n, na;
471 76193d7c 2003-09-30 devnull Rune *classp;
473 76193d7c 2003-09-30 devnull classp = emalloc(DCLASS*RUNESIZE);
475 76193d7c 2003-09-30 devnull na = DCLASS;
476 76193d7c 2003-09-30 devnull /* we have already seen the '[' */
477 76193d7c 2003-09-30 devnull if(*exprp == '^'){
478 76193d7c 2003-09-30 devnull classp[n++] = '\n'; /* don't match newline in negate case */
479 76193d7c 2003-09-30 devnull negateclass = TRUE;
480 76193d7c 2003-09-30 devnull exprp++;
482 76193d7c 2003-09-30 devnull negateclass = FALSE;
483 76193d7c 2003-09-30 devnull while((c1 = nextrec()) != ']'){
484 76193d7c 2003-09-30 devnull if(c1 == '-'){
486 76193d7c 2003-09-30 devnull free(classp);
487 76193d7c 2003-09-30 devnull regerror(Ebadclass);
489 76193d7c 2003-09-30 devnull if(n+4 >= na){ /* 3 runes plus NUL */
490 76193d7c 2003-09-30 devnull na += DCLASS;
491 76193d7c 2003-09-30 devnull classp = erealloc(classp, na*RUNESIZE);
493 76193d7c 2003-09-30 devnull if(*exprp == '-'){
494 76193d7c 2003-09-30 devnull exprp++; /* eat '-' */
495 76193d7c 2003-09-30 devnull if((c2 = nextrec()) == ']')
496 76193d7c 2003-09-30 devnull goto Error;
497 76193d7c 2003-09-30 devnull classp[n+0] = 0xFFFF;
498 76193d7c 2003-09-30 devnull classp[n+1] = c1;
499 76193d7c 2003-09-30 devnull classp[n+2] = c2;
502 76193d7c 2003-09-30 devnull classp[n++] = c1;
504 76193d7c 2003-09-30 devnull classp[n] = 0;
505 76193d7c 2003-09-30 devnull if(nclass == Nclass){
506 76193d7c 2003-09-30 devnull Nclass += DCLASS;
507 76193d7c 2003-09-30 devnull class = erealloc(class, Nclass*sizeof(Rune*));
509 76193d7c 2003-09-30 devnull class[nclass++] = classp;
513 76193d7c 2003-09-30 devnull classmatch(int classno, int c, int negate)
515 76193d7c 2003-09-30 devnull Rune *p;
517 76193d7c 2003-09-30 devnull p = class[classno];
518 76193d7c 2003-09-30 devnull while(*p){
519 76193d7c 2003-09-30 devnull if(*p == 0xFFFF){
520 76193d7c 2003-09-30 devnull if(p[1]<=c && c<=p[2])
521 76193d7c 2003-09-30 devnull return !negate;
523 76193d7c 2003-09-30 devnull }else if(*p++ == c)
524 76193d7c 2003-09-30 devnull return !negate;
526 76193d7c 2003-09-30 devnull return negate;
530 76193d7c 2003-09-30 devnull * Note optimization in addinst:
531 76193d7c 2003-09-30 devnull * *l must be pending when addinst called; if *l has been looked
532 76193d7c 2003-09-30 devnull * at already, the optimization is a bug.
535 76193d7c 2003-09-30 devnull addinst(Ilist *l, Inst *inst, Rangeset *sep)
537 76193d7c 2003-09-30 devnull Ilist *p;
539 76193d7c 2003-09-30 devnull for(p = l; p->inst; p++){
540 76193d7c 2003-09-30 devnull if(p->inst==inst){
541 76193d7c 2003-09-30 devnull if((sep)->p[0].p1 < p->se.p[0].p1)
542 76193d7c 2003-09-30 devnull p->se= *sep; /* this would be bug */
543 c99ef336 2007-06-09 devnull return 0; /* It's already there */
546 76193d7c 2003-09-30 devnull p->inst = inst;
547 76193d7c 2003-09-30 devnull p->se= *sep;
548 76193d7c 2003-09-30 devnull (p+1)->inst = 0;
549 c99ef336 2007-06-09 devnull return 1;
553 76193d7c 2003-09-30 devnull execute(File *f, Posn startp, Posn eof)
555 76193d7c 2003-09-30 devnull int flag = 0;
556 76193d7c 2003-09-30 devnull Inst *inst;
557 76193d7c 2003-09-30 devnull Ilist *tlp;
558 76193d7c 2003-09-30 devnull Posn p = startp;
559 76193d7c 2003-09-30 devnull int nnl = 0, ntl;
561 76193d7c 2003-09-30 devnull int wrapped = 0;
562 76193d7c 2003-09-30 devnull int startchar = startinst->type<OPERATOR? startinst->type : 0;
564 76193d7c 2003-09-30 devnull list[0][0].inst = list[1][0].inst = 0;
565 76193d7c 2003-09-30 devnull sel.p[0].p1 = -1;
566 76193d7c 2003-09-30 devnull /* Execute machine once for each character */
567 76193d7c 2003-09-30 devnull for(;;p++){
569 76193d7c 2003-09-30 devnull c = filereadc(f, p);
570 76193d7c 2003-09-30 devnull if(p>=eof || c<0){
571 76193d7c 2003-09-30 devnull switch(wrapped++){
572 76193d7c 2003-09-30 devnull case 0: /* let loop run one more click */
575 76193d7c 2003-09-30 devnull case 1: /* expired; wrap to beginning */
576 76193d7c 2003-09-30 devnull if(sel.p[0].p1>=0 || eof!=INFINITY)
577 76193d7c 2003-09-30 devnull goto Return;
578 76193d7c 2003-09-30 devnull list[0][0].inst = list[1][0].inst = 0;
580 76193d7c 2003-09-30 devnull goto doloop;
581 76193d7c 2003-09-30 devnull default:
582 76193d7c 2003-09-30 devnull goto Return;
584 76193d7c 2003-09-30 devnull }else if(((wrapped && p>=startp) || sel.p[0].p1>0) && nnl==0)
586 76193d7c 2003-09-30 devnull /* fast check for first char */
587 76193d7c 2003-09-30 devnull if(startchar && nnl==0 && c!=startchar)
588 76193d7c 2003-09-30 devnull continue;
589 76193d7c 2003-09-30 devnull tl = list[flag];
590 76193d7c 2003-09-30 devnull nl = list[flag^=1];
591 76193d7c 2003-09-30 devnull nl->inst = 0;
592 76193d7c 2003-09-30 devnull ntl = nnl;
593 76193d7c 2003-09-30 devnull nnl = 0;
594 76193d7c 2003-09-30 devnull if(sel.p[0].p1<0 && (!wrapped || p<startp || startp==eof)){
595 76193d7c 2003-09-30 devnull /* Add first instruction to this list */
596 c99ef336 2007-06-09 devnull sempty.p[0].p1 = p;
597 c99ef336 2007-06-09 devnull if(addinst(tl, startinst, &sempty))
598 76193d7c 2003-09-30 devnull if(++ntl >= NLIST)
599 76193d7c 2003-09-30 devnull Overflow:
600 76193d7c 2003-09-30 devnull error(Eoverflow);
602 76193d7c 2003-09-30 devnull /* Execute machine until this list is empty */
603 76193d7c 2003-09-30 devnull for(tlp = tl; inst = tlp->inst; tlp++){ /* assignment = */
604 76193d7c 2003-09-30 devnull Switchstmt:
605 76193d7c 2003-09-30 devnull switch(inst->type){
606 76193d7c 2003-09-30 devnull default: /* regular character */
607 76193d7c 2003-09-30 devnull if(inst->type==c){
608 76193d7c 2003-09-30 devnull Addinst:
609 c99ef336 2007-06-09 devnull if(addinst(nl, inst->next, &tlp->se))
610 76193d7c 2003-09-30 devnull if(++nnl >= NLIST)
611 76193d7c 2003-09-30 devnull goto Overflow;
614 76193d7c 2003-09-30 devnull case LBRA:
615 76193d7c 2003-09-30 devnull if(inst->subid>=0)
616 76193d7c 2003-09-30 devnull tlp->se.p[inst->subid].p1 = p;
617 76193d7c 2003-09-30 devnull inst = inst->next;
618 76193d7c 2003-09-30 devnull goto Switchstmt;
619 76193d7c 2003-09-30 devnull case RBRA:
620 76193d7c 2003-09-30 devnull if(inst->subid>=0)
621 76193d7c 2003-09-30 devnull tlp->se.p[inst->subid].p2 = p;
622 76193d7c 2003-09-30 devnull inst = inst->next;
623 76193d7c 2003-09-30 devnull goto Switchstmt;
624 76193d7c 2003-09-30 devnull case ANY:
625 76193d7c 2003-09-30 devnull if(c!='\n')
626 76193d7c 2003-09-30 devnull goto Addinst;
628 76193d7c 2003-09-30 devnull case BOL:
629 76193d7c 2003-09-30 devnull if(p==0 || filereadc(f, p - 1)=='\n'){
631 76193d7c 2003-09-30 devnull inst = inst->next;
632 76193d7c 2003-09-30 devnull goto Switchstmt;
635 76193d7c 2003-09-30 devnull case EOL:
636 76193d7c 2003-09-30 devnull if(c == '\n')
637 76193d7c 2003-09-30 devnull goto Step;
639 76193d7c 2003-09-30 devnull case CCLASS:
640 76193d7c 2003-09-30 devnull if(c>=0 && classmatch(inst->rclass, c, 0))
641 76193d7c 2003-09-30 devnull goto Addinst;
643 76193d7c 2003-09-30 devnull case NCCLASS:
644 76193d7c 2003-09-30 devnull if(c>=0 && classmatch(inst->rclass, c, 1))
645 76193d7c 2003-09-30 devnull goto Addinst;
647 76193d7c 2003-09-30 devnull case OR:
648 76193d7c 2003-09-30 devnull /* evaluate right choice later */
649 c99ef336 2007-06-09 devnull if(addinst(tl, inst->right, &tlp->se))
650 76193d7c 2003-09-30 devnull if(++ntl >= NLIST)
651 76193d7c 2003-09-30 devnull goto Overflow;
652 76193d7c 2003-09-30 devnull /* efficiency: advance and re-evaluate */
653 76193d7c 2003-09-30 devnull inst = inst->left;
654 76193d7c 2003-09-30 devnull goto Switchstmt;
655 76193d7c 2003-09-30 devnull case END: /* Match! */
656 76193d7c 2003-09-30 devnull tlp->se.p[0].p2 = p;
657 76193d7c 2003-09-30 devnull newmatch(&tlp->se);
663 76193d7c 2003-09-30 devnull return sel.p[0].p1>=0;
667 76193d7c 2003-09-30 devnull newmatch(Rangeset *sp)
671 76193d7c 2003-09-30 devnull if(sel.p[0].p1<0 || sp->p[0].p1<sel.p[0].p1 ||
672 76193d7c 2003-09-30 devnull (sp->p[0].p1==sel.p[0].p1 && sp->p[0].p2>sel.p[0].p2))
673 76193d7c 2003-09-30 devnull for(i = 0; i<NSUBEXP; i++)
674 76193d7c 2003-09-30 devnull sel.p[i] = sp->p[i];
678 76193d7c 2003-09-30 devnull bexecute(File *f, Posn startp)
680 76193d7c 2003-09-30 devnull int flag = 0;
681 76193d7c 2003-09-30 devnull Inst *inst;
682 76193d7c 2003-09-30 devnull Ilist *tlp;
683 76193d7c 2003-09-30 devnull Posn p = startp;
684 76193d7c 2003-09-30 devnull int nnl = 0, ntl;
686 76193d7c 2003-09-30 devnull int wrapped = 0;
687 76193d7c 2003-09-30 devnull int startchar = bstartinst->type<OPERATOR? bstartinst->type : 0;
689 76193d7c 2003-09-30 devnull list[0][0].inst = list[1][0].inst = 0;
690 76193d7c 2003-09-30 devnull sel.p[0].p1= -1;
691 76193d7c 2003-09-30 devnull /* Execute machine once for each character, including terminal NUL */
692 76193d7c 2003-09-30 devnull for(;;--p){
694 76193d7c 2003-09-30 devnull if((c = filereadc(f, p - 1))==-1){
695 76193d7c 2003-09-30 devnull switch(wrapped++){
696 76193d7c 2003-09-30 devnull case 0: /* let loop run one more click */
699 76193d7c 2003-09-30 devnull case 1: /* expired; wrap to end */
700 76193d7c 2003-09-30 devnull if(sel.p[0].p1>=0)
702 76193d7c 2003-09-30 devnull goto Return;
703 76193d7c 2003-09-30 devnull list[0][0].inst = list[1][0].inst = 0;
704 522b0689 2003-09-30 devnull p = f->b.nc;
705 76193d7c 2003-09-30 devnull goto doloop;
706 76193d7c 2003-09-30 devnull default:
707 76193d7c 2003-09-30 devnull goto Return;
709 76193d7c 2003-09-30 devnull }else if(((wrapped && p<=startp) || sel.p[0].p1>0) && nnl==0)
711 76193d7c 2003-09-30 devnull /* fast check for first char */
712 76193d7c 2003-09-30 devnull if(startchar && nnl==0 && c!=startchar)
713 76193d7c 2003-09-30 devnull continue;
714 76193d7c 2003-09-30 devnull tl = list[flag];
715 76193d7c 2003-09-30 devnull nl = list[flag^=1];
716 76193d7c 2003-09-30 devnull nl->inst = 0;
717 76193d7c 2003-09-30 devnull ntl = nnl;
718 76193d7c 2003-09-30 devnull nnl = 0;
719 76193d7c 2003-09-30 devnull if(sel.p[0].p1<0 && (!wrapped || p>startp)){
720 76193d7c 2003-09-30 devnull /* Add first instruction to this list */
721 c99ef336 2007-06-09 devnull /* the minus is so the optimizations in addinst work */
722 c99ef336 2007-06-09 devnull sempty.p[0].p1 = -p;
723 c99ef336 2007-06-09 devnull if(addinst(tl, bstartinst, &sempty))
724 76193d7c 2003-09-30 devnull if(++ntl >= NLIST)
725 76193d7c 2003-09-30 devnull Overflow:
726 76193d7c 2003-09-30 devnull error(Eoverflow);
728 76193d7c 2003-09-30 devnull /* Execute machine until this list is empty */
729 76193d7c 2003-09-30 devnull for(tlp = tl; inst = tlp->inst; tlp++){ /* assignment = */
730 76193d7c 2003-09-30 devnull Switchstmt:
731 76193d7c 2003-09-30 devnull switch(inst->type){
732 76193d7c 2003-09-30 devnull default: /* regular character */
733 76193d7c 2003-09-30 devnull if(inst->type == c){
734 76193d7c 2003-09-30 devnull Addinst:
735 c99ef336 2007-06-09 devnull if(addinst(nl, inst->next, &tlp->se))
736 76193d7c 2003-09-30 devnull if(++nnl >= NLIST)
737 76193d7c 2003-09-30 devnull goto Overflow;
740 76193d7c 2003-09-30 devnull case LBRA:
741 76193d7c 2003-09-30 devnull if(inst->subid>=0)
742 76193d7c 2003-09-30 devnull tlp->se.p[inst->subid].p1 = p;
743 76193d7c 2003-09-30 devnull inst = inst->next;
744 76193d7c 2003-09-30 devnull goto Switchstmt;
745 76193d7c 2003-09-30 devnull case RBRA:
746 76193d7c 2003-09-30 devnull if(inst->subid >= 0)
747 76193d7c 2003-09-30 devnull tlp->se.p[inst->subid].p2 = p;
748 76193d7c 2003-09-30 devnull inst = inst->next;
749 76193d7c 2003-09-30 devnull goto Switchstmt;
750 76193d7c 2003-09-30 devnull case ANY:
751 76193d7c 2003-09-30 devnull if(c != '\n')
752 76193d7c 2003-09-30 devnull goto Addinst;
754 76193d7c 2003-09-30 devnull case BOL:
755 76193d7c 2003-09-30 devnull if(c=='\n' || p==0){
757 76193d7c 2003-09-30 devnull inst = inst->next;
758 76193d7c 2003-09-30 devnull goto Switchstmt;
761 76193d7c 2003-09-30 devnull case EOL:
762 522b0689 2003-09-30 devnull if(p==f->b.nc || filereadc(f, p)=='\n')
763 76193d7c 2003-09-30 devnull goto Step;
765 76193d7c 2003-09-30 devnull case CCLASS:
766 76193d7c 2003-09-30 devnull if(c>=0 && classmatch(inst->rclass, c, 0))
767 76193d7c 2003-09-30 devnull goto Addinst;
769 76193d7c 2003-09-30 devnull case NCCLASS:
770 76193d7c 2003-09-30 devnull if(c>=0 && classmatch(inst->rclass, c, 1))
771 76193d7c 2003-09-30 devnull goto Addinst;
773 76193d7c 2003-09-30 devnull case OR:
774 76193d7c 2003-09-30 devnull /* evaluate right choice later */
775 c99ef336 2007-06-09 devnull if(addinst(tl, inst->right, &tlp->se))
776 76193d7c 2003-09-30 devnull if(++ntl >= NLIST)
777 76193d7c 2003-09-30 devnull goto Overflow;
778 76193d7c 2003-09-30 devnull /* efficiency: advance and re-evaluate */
779 76193d7c 2003-09-30 devnull inst = inst->left;
780 76193d7c 2003-09-30 devnull goto Switchstmt;
781 76193d7c 2003-09-30 devnull case END: /* Match! */
782 76193d7c 2003-09-30 devnull tlp->se.p[0].p1 = -tlp->se.p[0].p1; /* minus sign */
783 76193d7c 2003-09-30 devnull tlp->se.p[0].p2 = p;
784 76193d7c 2003-09-30 devnull bnewmatch(&tlp->se);
790 76193d7c 2003-09-30 devnull return sel.p[0].p1>=0;
794 76193d7c 2003-09-30 devnull bnewmatch(Rangeset *sp)
797 76193d7c 2003-09-30 devnull if(sel.p[0].p1<0 || sp->p[0].p1>sel.p[0].p2 || (sp->p[0].p1==sel.p[0].p2 && sp->p[0].p2<sel.p[0].p1))
798 76193d7c 2003-09-30 devnull for(i = 0; i<NSUBEXP; i++){ /* note the reversal; p1<=p2 */
799 76193d7c 2003-09-30 devnull sel.p[i].p1 = sp->p[i].p2;
800 76193d7c 2003-09-30 devnull sel.p[i].p2 = sp->p[i].p1;
