1 b2cfc4e2 2003-09-30 devnull #include "lib9.h"
2 b2cfc4e2 2003-09-30 devnull #include "regexp9.h"
3 b2cfc4e2 2003-09-30 devnull #include "regcomp.h"
5 b2cfc4e2 2003-09-30 devnull #define TRUE 1
6 b2cfc4e2 2003-09-30 devnull #define FALSE 0
9 b2cfc4e2 2003-09-30 devnull * Parser Information
12 b2cfc4e2 2003-09-30 devnull struct Node
14 b2cfc4e2 2003-09-30 devnull Reinst* first;
15 b2cfc4e2 2003-09-30 devnull Reinst* last;
18 b2cfc4e2 2003-09-30 devnull #define NSTACK 20
19 b2cfc4e2 2003-09-30 devnull static Node andstack[NSTACK];
20 b2cfc4e2 2003-09-30 devnull static Node *andp;
21 b2cfc4e2 2003-09-30 devnull static int atorstack[NSTACK];
22 b2cfc4e2 2003-09-30 devnull static int* atorp;
23 b2cfc4e2 2003-09-30 devnull static int cursubid; /* id of current subexpression */
24 b2cfc4e2 2003-09-30 devnull static int subidstack[NSTACK]; /* parallel to atorstack */
25 b2cfc4e2 2003-09-30 devnull static int* subidp;
26 b2cfc4e2 2003-09-30 devnull static int lastwasand; /* Last token was operand */
27 b2cfc4e2 2003-09-30 devnull static int nbra;
28 b2cfc4e2 2003-09-30 devnull static char* exprp; /* pointer to next character in source expression */
29 b2cfc4e2 2003-09-30 devnull static int lexdone;
30 b2cfc4e2 2003-09-30 devnull static int nclass;
31 b2cfc4e2 2003-09-30 devnull static Reclass*classp;
32 b2cfc4e2 2003-09-30 devnull static Reinst* freep;
33 b2cfc4e2 2003-09-30 devnull static int errors;
34 b2cfc4e2 2003-09-30 devnull static Rune yyrune; /* last lex'd rune */
35 b2cfc4e2 2003-09-30 devnull static Reclass*yyclassp; /* last lex'd class */
37 b2cfc4e2 2003-09-30 devnull /* predeclared crap */
38 b2cfc4e2 2003-09-30 devnull static void operator(int);
39 b2cfc4e2 2003-09-30 devnull static void pushand(Reinst*, Reinst*);
40 b2cfc4e2 2003-09-30 devnull static void pushator(int);
41 b2cfc4e2 2003-09-30 devnull static void evaluntil(int);
42 b2cfc4e2 2003-09-30 devnull static int bldcclass(void);
44 b2cfc4e2 2003-09-30 devnull static jmp_buf regkaboom;
46 b2cfc4e2 2003-09-30 devnull static void
47 b2cfc4e2 2003-09-30 devnull rcerror(char *s)
49 b2cfc4e2 2003-09-30 devnull errors++;
50 b2cfc4e2 2003-09-30 devnull regerror(s);
51 b2cfc4e2 2003-09-30 devnull longjmp(regkaboom, 1);
54 b2cfc4e2 2003-09-30 devnull static Reinst*
55 b2cfc4e2 2003-09-30 devnull newinst(int t)
57 b2cfc4e2 2003-09-30 devnull freep->type = t;
58 b2cfc4e2 2003-09-30 devnull freep->u2.left = 0;
59 b2cfc4e2 2003-09-30 devnull freep->u1.right = 0;
60 b2cfc4e2 2003-09-30 devnull return freep++;
63 b2cfc4e2 2003-09-30 devnull static void
64 b2cfc4e2 2003-09-30 devnull operand(int t)
66 b2cfc4e2 2003-09-30 devnull Reinst *i;
68 b2cfc4e2 2003-09-30 devnull if(lastwasand)
69 b2cfc4e2 2003-09-30 devnull operator(CAT); /* catenate is implicit */
70 b2cfc4e2 2003-09-30 devnull i = newinst(t);
72 b2cfc4e2 2003-09-30 devnull if(t == CCLASS || t == NCCLASS)
73 b2cfc4e2 2003-09-30 devnull i->u1.cp = yyclassp;
74 b2cfc4e2 2003-09-30 devnull if(t == RUNE)
75 b2cfc4e2 2003-09-30 devnull i->u1.r = yyrune;
77 b2cfc4e2 2003-09-30 devnull pushand(i, i);
78 b2cfc4e2 2003-09-30 devnull lastwasand = TRUE;
81 b2cfc4e2 2003-09-30 devnull static void
82 b2cfc4e2 2003-09-30 devnull operator(int t)
84 b2cfc4e2 2003-09-30 devnull if(t==RBRA && --nbra<0)
85 b2cfc4e2 2003-09-30 devnull rcerror("unmatched right paren");
86 b2cfc4e2 2003-09-30 devnull if(t==LBRA){
87 b2cfc4e2 2003-09-30 devnull if(++cursubid >= NSUBEXP)
88 b2cfc4e2 2003-09-30 devnull rcerror ("too many subexpressions");
90 b2cfc4e2 2003-09-30 devnull if(lastwasand)
91 b2cfc4e2 2003-09-30 devnull operator(CAT);
93 b2cfc4e2 2003-09-30 devnull evaluntil(t);
94 b2cfc4e2 2003-09-30 devnull if(t != RBRA)
95 b2cfc4e2 2003-09-30 devnull pushator(t);
96 b2cfc4e2 2003-09-30 devnull lastwasand = FALSE;
97 b2cfc4e2 2003-09-30 devnull if(t==STAR || t==QUEST || t==PLUS || t==RBRA)
98 b2cfc4e2 2003-09-30 devnull lastwasand = TRUE; /* these look like operands */
101 b2cfc4e2 2003-09-30 devnull static void
102 b2cfc4e2 2003-09-30 devnull regerr2(char *s, int c)
104 b2cfc4e2 2003-09-30 devnull char buf[100];
105 b2cfc4e2 2003-09-30 devnull char *cp = buf;
106 b2cfc4e2 2003-09-30 devnull while(*s)
107 b2cfc4e2 2003-09-30 devnull *cp++ = *s++;
108 b2cfc4e2 2003-09-30 devnull *cp++ = c;
109 b2cfc4e2 2003-09-30 devnull *cp = '\0';
110 b2cfc4e2 2003-09-30 devnull rcerror(buf);
113 b2cfc4e2 2003-09-30 devnull static void
114 b2cfc4e2 2003-09-30 devnull cant(char *s)
116 b2cfc4e2 2003-09-30 devnull char buf[100];
117 b2cfc4e2 2003-09-30 devnull strcpy(buf, "can't happen: ");
118 b2cfc4e2 2003-09-30 devnull strcat(buf, s);
119 b2cfc4e2 2003-09-30 devnull rcerror(buf);
122 b2cfc4e2 2003-09-30 devnull static void
123 b2cfc4e2 2003-09-30 devnull pushand(Reinst *f, Reinst *l)
125 b2cfc4e2 2003-09-30 devnull if(andp >= &andstack[NSTACK])
126 b2cfc4e2 2003-09-30 devnull cant("operand stack overflow");
127 b2cfc4e2 2003-09-30 devnull andp->first = f;
128 b2cfc4e2 2003-09-30 devnull andp->last = l;
132 b2cfc4e2 2003-09-30 devnull static void
133 b2cfc4e2 2003-09-30 devnull pushator(int t)
135 b2cfc4e2 2003-09-30 devnull if(atorp >= &atorstack[NSTACK])
136 b2cfc4e2 2003-09-30 devnull cant("operator stack overflow");
137 b2cfc4e2 2003-09-30 devnull *atorp++ = t;
138 b2cfc4e2 2003-09-30 devnull *subidp++ = cursubid;
141 b2cfc4e2 2003-09-30 devnull static Node*
142 b2cfc4e2 2003-09-30 devnull popand(int op)
144 b2cfc4e2 2003-09-30 devnull Reinst *inst;
146 b2cfc4e2 2003-09-30 devnull if(andp <= &andstack[0]){
147 b2cfc4e2 2003-09-30 devnull regerr2("missing operand for ", op);
148 b2cfc4e2 2003-09-30 devnull inst = newinst(NOP);
149 b2cfc4e2 2003-09-30 devnull pushand(inst,inst);
151 b2cfc4e2 2003-09-30 devnull return --andp;
154 b2cfc4e2 2003-09-30 devnull static int
155 b2cfc4e2 2003-09-30 devnull popator(void)
157 b2cfc4e2 2003-09-30 devnull if(atorp <= &atorstack[0])
158 b2cfc4e2 2003-09-30 devnull cant("operator stack underflow");
159 b2cfc4e2 2003-09-30 devnull --subidp;
160 b2cfc4e2 2003-09-30 devnull return *--atorp;
163 b2cfc4e2 2003-09-30 devnull static void
164 b2cfc4e2 2003-09-30 devnull evaluntil(int pri)
166 b2cfc4e2 2003-09-30 devnull Node *op1, *op2;
167 b2cfc4e2 2003-09-30 devnull Reinst *inst1, *inst2;
169 b2cfc4e2 2003-09-30 devnull while(pri==RBRA || atorp[-1]>=pri){
170 b2cfc4e2 2003-09-30 devnull switch(popator()){
171 b2cfc4e2 2003-09-30 devnull default:
172 b2cfc4e2 2003-09-30 devnull rcerror("unknown operator in evaluntil");
174 b2cfc4e2 2003-09-30 devnull case LBRA: /* must have been RBRA */
175 b2cfc4e2 2003-09-30 devnull op1 = popand('(');
176 b2cfc4e2 2003-09-30 devnull inst2 = newinst(RBRA);
177 b2cfc4e2 2003-09-30 devnull inst2->u1.subid = *subidp;
178 b2cfc4e2 2003-09-30 devnull op1->last->u2.next = inst2;
179 b2cfc4e2 2003-09-30 devnull inst1 = newinst(LBRA);
180 b2cfc4e2 2003-09-30 devnull inst1->u1.subid = *subidp;
181 b2cfc4e2 2003-09-30 devnull inst1->u2.next = op1->first;
182 b2cfc4e2 2003-09-30 devnull pushand(inst1, inst2);
184 b2cfc4e2 2003-09-30 devnull case OR:
185 b2cfc4e2 2003-09-30 devnull op2 = popand('|');
186 b2cfc4e2 2003-09-30 devnull op1 = popand('|');
187 b2cfc4e2 2003-09-30 devnull inst2 = newinst(NOP);
188 b2cfc4e2 2003-09-30 devnull op2->last->u2.next = inst2;
189 b2cfc4e2 2003-09-30 devnull op1->last->u2.next = inst2;
190 b2cfc4e2 2003-09-30 devnull inst1 = newinst(OR);
191 b2cfc4e2 2003-09-30 devnull inst1->u1.right = op1->first;
192 b2cfc4e2 2003-09-30 devnull inst1->u2.left = op2->first;
193 b2cfc4e2 2003-09-30 devnull pushand(inst1, inst2);
195 b2cfc4e2 2003-09-30 devnull case CAT:
196 b2cfc4e2 2003-09-30 devnull op2 = popand(0);
197 b2cfc4e2 2003-09-30 devnull op1 = popand(0);
198 b2cfc4e2 2003-09-30 devnull op1->last->u2.next = op2->first;
199 b2cfc4e2 2003-09-30 devnull pushand(op1->first, op2->last);
201 b2cfc4e2 2003-09-30 devnull case STAR:
202 b2cfc4e2 2003-09-30 devnull op2 = popand('*');
203 b2cfc4e2 2003-09-30 devnull inst1 = newinst(OR);
204 b2cfc4e2 2003-09-30 devnull op2->last->u2.next = inst1;
205 b2cfc4e2 2003-09-30 devnull inst1->u1.right = op2->first;
206 b2cfc4e2 2003-09-30 devnull pushand(inst1, inst1);
208 b2cfc4e2 2003-09-30 devnull case PLUS:
209 b2cfc4e2 2003-09-30 devnull op2 = popand('+');
210 b2cfc4e2 2003-09-30 devnull inst1 = newinst(OR);
211 b2cfc4e2 2003-09-30 devnull op2->last->u2.next = inst1;
212 b2cfc4e2 2003-09-30 devnull inst1->u1.right = op2->first;
213 b2cfc4e2 2003-09-30 devnull pushand(op2->first, inst1);
215 b2cfc4e2 2003-09-30 devnull case QUEST:
216 b2cfc4e2 2003-09-30 devnull op2 = popand('?');
217 b2cfc4e2 2003-09-30 devnull inst1 = newinst(OR);
218 b2cfc4e2 2003-09-30 devnull inst2 = newinst(NOP);
219 b2cfc4e2 2003-09-30 devnull inst1->u2.left = inst2;
220 b2cfc4e2 2003-09-30 devnull inst1->u1.right = op2->first;
221 b2cfc4e2 2003-09-30 devnull op2->last->u2.next = inst2;
222 b2cfc4e2 2003-09-30 devnull pushand(inst1, inst2);
228 b2cfc4e2 2003-09-30 devnull static Reprog*
229 b2cfc4e2 2003-09-30 devnull optimize(Reprog *pp)
231 b2cfc4e2 2003-09-30 devnull Reinst *inst, *target;
232 b2cfc4e2 2003-09-30 devnull int size;
233 b2cfc4e2 2003-09-30 devnull Reprog *npp;
234 b2cfc4e2 2003-09-30 devnull Reclass *cl;
235 b2cfc4e2 2003-09-30 devnull int diff;
238 b2cfc4e2 2003-09-30 devnull * get rid of NOOP chains
240 b2cfc4e2 2003-09-30 devnull for(inst=pp->firstinst; inst->type!=END; inst++){
241 b2cfc4e2 2003-09-30 devnull target = inst->u2.next;
242 b2cfc4e2 2003-09-30 devnull while(target->type == NOP)
243 b2cfc4e2 2003-09-30 devnull target = target->u2.next;
244 b2cfc4e2 2003-09-30 devnull inst->u2.next = target;
248 b2cfc4e2 2003-09-30 devnull * The original allocation is for an area larger than
249 b2cfc4e2 2003-09-30 devnull * necessary. Reallocate to the actual space used
250 b2cfc4e2 2003-09-30 devnull * and then relocate the code.
252 b2cfc4e2 2003-09-30 devnull size = sizeof(Reprog) + (freep - pp->firstinst)*sizeof(Reinst);
253 62390091 2004-03-05 devnull npp = realloc(pp, size);
254 b2cfc4e2 2003-09-30 devnull if(npp==0 || npp==pp)
255 b2cfc4e2 2003-09-30 devnull return pp;
256 b2cfc4e2 2003-09-30 devnull diff = (char *)npp - (char *)pp;
257 b2cfc4e2 2003-09-30 devnull freep = (Reinst *)((char *)freep + diff);
258 b2cfc4e2 2003-09-30 devnull for(inst=npp->firstinst; inst<freep; inst++){
259 b2cfc4e2 2003-09-30 devnull switch(inst->type){
260 b2cfc4e2 2003-09-30 devnull case OR:
261 b2cfc4e2 2003-09-30 devnull case STAR:
262 b2cfc4e2 2003-09-30 devnull case PLUS:
263 b2cfc4e2 2003-09-30 devnull case QUEST:
264 4515de8f 2006-04-20 devnull *(char**)(void*)&inst->u1.right += diff;
266 b2cfc4e2 2003-09-30 devnull case CCLASS:
267 b2cfc4e2 2003-09-30 devnull case NCCLASS:
268 4515de8f 2006-04-20 devnull *(char**)(void*)&inst->u1.right += diff;
269 b2cfc4e2 2003-09-30 devnull cl = inst->u1.cp;
270 4515de8f 2006-04-20 devnull *(char**)(void*)&cl->end += diff;
273 4515de8f 2006-04-20 devnull *(char**)(void*)&inst->u2.left += diff;
275 4515de8f 2006-04-20 devnull *(char**)(void*)&npp->startinst += diff;
276 b2cfc4e2 2003-09-30 devnull return npp;
279 b2cfc4e2 2003-09-30 devnull #ifdef DEBUG
280 b2cfc4e2 2003-09-30 devnull static void
281 b2cfc4e2 2003-09-30 devnull dumpstack(void){
282 b2cfc4e2 2003-09-30 devnull Node *stk;
283 b2cfc4e2 2003-09-30 devnull int *ip;
285 b2cfc4e2 2003-09-30 devnull print("operators\n");
286 b2cfc4e2 2003-09-30 devnull for(ip=atorstack; ip<atorp; ip++)
287 b2cfc4e2 2003-09-30 devnull print("0%o\n", *ip);
288 b2cfc4e2 2003-09-30 devnull print("operands\n");
289 b2cfc4e2 2003-09-30 devnull for(stk=andstack; stk<andp; stk++)
290 b2cfc4e2 2003-09-30 devnull print("0%o\t0%o\n", stk->first->type, stk->last->type);
293 b2cfc4e2 2003-09-30 devnull static void
294 b2cfc4e2 2003-09-30 devnull dump(Reprog *pp)
296 b2cfc4e2 2003-09-30 devnull Reinst *l;
297 b2cfc4e2 2003-09-30 devnull Rune *p;
299 b2cfc4e2 2003-09-30 devnull l = pp->firstinst;
301 b2cfc4e2 2003-09-30 devnull print("%d:\t0%o\t%d\t%d", l-pp->firstinst, l->type,
302 b2cfc4e2 2003-09-30 devnull l->u2.left-pp->firstinst, l->u1.right-pp->firstinst);
303 b2cfc4e2 2003-09-30 devnull if(l->type == RUNE)
304 62390091 2004-03-05 devnull print("\t%C\n", l->u1.r);
305 b2cfc4e2 2003-09-30 devnull else if(l->type == CCLASS || l->type == NCCLASS){
306 b2cfc4e2 2003-09-30 devnull print("\t[");
307 b2cfc4e2 2003-09-30 devnull if(l->type == NCCLASS)
308 b2cfc4e2 2003-09-30 devnull print("^");
309 62390091 2004-03-05 devnull for(p = l->u1.cp->spans; p < l->u1.cp->end; p += 2)
310 b2cfc4e2 2003-09-30 devnull if(p[0] == p[1])
311 b2cfc4e2 2003-09-30 devnull print("%C", p[0]);
313 b2cfc4e2 2003-09-30 devnull print("%C-%C", p[0], p[1]);
314 b2cfc4e2 2003-09-30 devnull print("]\n");
316 b2cfc4e2 2003-09-30 devnull print("\n");
317 b2cfc4e2 2003-09-30 devnull }while(l++->type);
321 b2cfc4e2 2003-09-30 devnull static Reclass*
322 b2cfc4e2 2003-09-30 devnull newclass(void)
324 b2cfc4e2 2003-09-30 devnull if(nclass >= NCLASS)
325 b2cfc4e2 2003-09-30 devnull regerr2("too many character classes; limit", NCLASS+'0');
326 b2cfc4e2 2003-09-30 devnull return &(classp[nclass++]);
329 b2cfc4e2 2003-09-30 devnull static int
330 b2cfc4e2 2003-09-30 devnull nextc(Rune *rp)
332 b2cfc4e2 2003-09-30 devnull if(lexdone){
333 b2cfc4e2 2003-09-30 devnull *rp = 0;
334 b2cfc4e2 2003-09-30 devnull return 1;
336 b2cfc4e2 2003-09-30 devnull exprp += chartorune(rp, exprp);
337 bb0266fe 2005-05-07 devnull if(*rp == '\\'){
338 b2cfc4e2 2003-09-30 devnull exprp += chartorune(rp, exprp);
339 b2cfc4e2 2003-09-30 devnull return 1;
341 b2cfc4e2 2003-09-30 devnull if(*rp == 0)
342 b2cfc4e2 2003-09-30 devnull lexdone = 1;
343 b2cfc4e2 2003-09-30 devnull return 0;
346 b2cfc4e2 2003-09-30 devnull static int
347 b2cfc4e2 2003-09-30 devnull lex(int literal, int dot_type)
349 b2cfc4e2 2003-09-30 devnull int quoted;
351 b2cfc4e2 2003-09-30 devnull quoted = nextc(&yyrune);
352 b2cfc4e2 2003-09-30 devnull if(literal || quoted){
353 b2cfc4e2 2003-09-30 devnull if(yyrune == 0)
354 b2cfc4e2 2003-09-30 devnull return END;
355 b2cfc4e2 2003-09-30 devnull return RUNE;
358 b2cfc4e2 2003-09-30 devnull switch(yyrune){
360 b2cfc4e2 2003-09-30 devnull return END;
361 bb0266fe 2005-05-07 devnull case '*':
362 b2cfc4e2 2003-09-30 devnull return STAR;
363 bb0266fe 2005-05-07 devnull case '?':
364 b2cfc4e2 2003-09-30 devnull return QUEST;
365 bb0266fe 2005-05-07 devnull case '+':
366 b2cfc4e2 2003-09-30 devnull return PLUS;
367 bb0266fe 2005-05-07 devnull case '|':
368 b2cfc4e2 2003-09-30 devnull return OR;
369 bb0266fe 2005-05-07 devnull case '.':
370 b2cfc4e2 2003-09-30 devnull return dot_type;
371 bb0266fe 2005-05-07 devnull case '(':
372 b2cfc4e2 2003-09-30 devnull return LBRA;
373 bb0266fe 2005-05-07 devnull case ')':
374 b2cfc4e2 2003-09-30 devnull return RBRA;
375 bb0266fe 2005-05-07 devnull case '^':
376 bb0266fe 2005-05-07 devnull return BOL;
377 bb0266fe 2005-05-07 devnull case '$':
378 b2cfc4e2 2003-09-30 devnull return EOL;
379 bb0266fe 2005-05-07 devnull case '[':
380 b2cfc4e2 2003-09-30 devnull return bldcclass();
382 b2cfc4e2 2003-09-30 devnull return RUNE;
385 b2cfc4e2 2003-09-30 devnull static int
386 b2cfc4e2 2003-09-30 devnull bldcclass(void)
388 b2cfc4e2 2003-09-30 devnull int type;
389 b2cfc4e2 2003-09-30 devnull Rune r[NCCRUNE];
390 b2cfc4e2 2003-09-30 devnull Rune *p, *ep, *np;
391 b2cfc4e2 2003-09-30 devnull Rune rune;
392 b2cfc4e2 2003-09-30 devnull int quoted;
394 b2cfc4e2 2003-09-30 devnull /* we have already seen the '[' */
395 b2cfc4e2 2003-09-30 devnull type = CCLASS;
396 b2cfc4e2 2003-09-30 devnull yyclassp = newclass();
398 b2cfc4e2 2003-09-30 devnull /* look ahead for negation */
399 b2cfc4e2 2003-09-30 devnull /* SPECIAL CASE!!! negated classes don't match \n */
401 b2cfc4e2 2003-09-30 devnull quoted = nextc(&rune);
402 bb0266fe 2005-05-07 devnull if(!quoted && rune == '^'){
403 b2cfc4e2 2003-09-30 devnull type = NCCLASS;
404 b2cfc4e2 2003-09-30 devnull quoted = nextc(&rune);
405 bb0266fe 2005-05-07 devnull *ep++ = '\n';
406 bb0266fe 2005-05-07 devnull *ep++ = '\n';
409 b2cfc4e2 2003-09-30 devnull /* parse class into a set of spans */
410 b2cfc4e2 2003-09-30 devnull for(; ep<&r[NCCRUNE];){
411 b2cfc4e2 2003-09-30 devnull if(rune == 0){
412 b2cfc4e2 2003-09-30 devnull rcerror("malformed '[]'");
413 b2cfc4e2 2003-09-30 devnull return 0;
415 bb0266fe 2005-05-07 devnull if(!quoted && rune == ']')
417 bb0266fe 2005-05-07 devnull if(!quoted && rune == '-'){
418 b2cfc4e2 2003-09-30 devnull if(ep == r){
419 b2cfc4e2 2003-09-30 devnull rcerror("malformed '[]'");
420 b2cfc4e2 2003-09-30 devnull return 0;
422 b2cfc4e2 2003-09-30 devnull quoted = nextc(&rune);
423 bb0266fe 2005-05-07 devnull if((!quoted && rune == ']') || rune == 0){
424 b2cfc4e2 2003-09-30 devnull rcerror("malformed '[]'");
425 b2cfc4e2 2003-09-30 devnull return 0;
427 b2cfc4e2 2003-09-30 devnull *(ep-1) = rune;
428 b2cfc4e2 2003-09-30 devnull } else {
429 b2cfc4e2 2003-09-30 devnull *ep++ = rune;
430 b2cfc4e2 2003-09-30 devnull *ep++ = rune;
432 b2cfc4e2 2003-09-30 devnull quoted = nextc(&rune);
435 b2cfc4e2 2003-09-30 devnull /* sort on span start */
436 b2cfc4e2 2003-09-30 devnull for(p = r; p < ep; p += 2){
437 b2cfc4e2 2003-09-30 devnull for(np = p; np < ep; np += 2)
438 b2cfc4e2 2003-09-30 devnull if(*np < *p){
439 b2cfc4e2 2003-09-30 devnull rune = np[0];
440 b2cfc4e2 2003-09-30 devnull np[0] = p[0];
441 b2cfc4e2 2003-09-30 devnull p[0] = rune;
442 b2cfc4e2 2003-09-30 devnull rune = np[1];
443 b2cfc4e2 2003-09-30 devnull np[1] = p[1];
444 b2cfc4e2 2003-09-30 devnull p[1] = rune;
448 b2cfc4e2 2003-09-30 devnull /* merge spans */
449 b2cfc4e2 2003-09-30 devnull np = yyclassp->spans;
451 b2cfc4e2 2003-09-30 devnull if(r == ep)
452 b2cfc4e2 2003-09-30 devnull yyclassp->end = np;
454 b2cfc4e2 2003-09-30 devnull np[0] = *p++;
455 b2cfc4e2 2003-09-30 devnull np[1] = *p++;
456 b2cfc4e2 2003-09-30 devnull for(; p < ep; p += 2)
457 b2cfc4e2 2003-09-30 devnull if(p[0] <= np[1]){
458 b2cfc4e2 2003-09-30 devnull if(p[1] > np[1])
459 b2cfc4e2 2003-09-30 devnull np[1] = p[1];
460 b2cfc4e2 2003-09-30 devnull } else {
461 b2cfc4e2 2003-09-30 devnull np += 2;
462 b2cfc4e2 2003-09-30 devnull np[0] = p[0];
463 b2cfc4e2 2003-09-30 devnull np[1] = p[1];
465 b2cfc4e2 2003-09-30 devnull yyclassp->end = np+2;
468 b2cfc4e2 2003-09-30 devnull return type;
471 b2cfc4e2 2003-09-30 devnull static Reprog*
472 b2cfc4e2 2003-09-30 devnull regcomp1(char *s, int literal, int dot_type)
474 b2cfc4e2 2003-09-30 devnull int token;
475 5ba56e91 2005-01-14 devnull Reprog *volatile pp;
477 b2cfc4e2 2003-09-30 devnull /* get memory for the program */
478 62390091 2004-03-05 devnull pp = malloc(sizeof(Reprog) + 6*sizeof(Reinst)*strlen(s));
479 b2cfc4e2 2003-09-30 devnull if(pp == 0){
480 b2cfc4e2 2003-09-30 devnull regerror("out of memory");
481 b2cfc4e2 2003-09-30 devnull return 0;
483 b2cfc4e2 2003-09-30 devnull freep = pp->firstinst;
484 b2cfc4e2 2003-09-30 devnull classp = pp->class;
485 b2cfc4e2 2003-09-30 devnull errors = 0;
487 b2cfc4e2 2003-09-30 devnull if(setjmp(regkaboom))
488 b2cfc4e2 2003-09-30 devnull goto out;
490 b2cfc4e2 2003-09-30 devnull /* go compile the sucker */
491 b2cfc4e2 2003-09-30 devnull lexdone = 0;
492 b2cfc4e2 2003-09-30 devnull exprp = s;
493 b2cfc4e2 2003-09-30 devnull nclass = 0;
494 b2cfc4e2 2003-09-30 devnull nbra = 0;
495 b2cfc4e2 2003-09-30 devnull atorp = atorstack;
496 b2cfc4e2 2003-09-30 devnull andp = andstack;
497 b2cfc4e2 2003-09-30 devnull subidp = subidstack;
498 b2cfc4e2 2003-09-30 devnull lastwasand = FALSE;
499 b2cfc4e2 2003-09-30 devnull cursubid = 0;
501 b2cfc4e2 2003-09-30 devnull /* Start with a low priority operator to prime parser */
502 b2cfc4e2 2003-09-30 devnull pushator(START-1);
503 b2cfc4e2 2003-09-30 devnull while((token = lex(literal, dot_type)) != END){
504 b2cfc4e2 2003-09-30 devnull if((token&0300) == OPERATOR)
505 b2cfc4e2 2003-09-30 devnull operator(token);
507 b2cfc4e2 2003-09-30 devnull operand(token);
510 b2cfc4e2 2003-09-30 devnull /* Close with a low priority operator */
511 b2cfc4e2 2003-09-30 devnull evaluntil(START);
513 b2cfc4e2 2003-09-30 devnull /* Force END */
514 b2cfc4e2 2003-09-30 devnull operand(END);
515 b2cfc4e2 2003-09-30 devnull evaluntil(START);
516 b2cfc4e2 2003-09-30 devnull #ifdef DEBUG
517 b2cfc4e2 2003-09-30 devnull dumpstack();
519 b2cfc4e2 2003-09-30 devnull if(nbra)
520 b2cfc4e2 2003-09-30 devnull rcerror("unmatched left paren");
521 b2cfc4e2 2003-09-30 devnull --andp; /* points to first and only operand */
522 b2cfc4e2 2003-09-30 devnull pp->startinst = andp->first;
523 b2cfc4e2 2003-09-30 devnull #ifdef DEBUG
524 b2cfc4e2 2003-09-30 devnull dump(pp);
526 b2cfc4e2 2003-09-30 devnull pp = optimize(pp);
527 b2cfc4e2 2003-09-30 devnull #ifdef DEBUG
528 b2cfc4e2 2003-09-30 devnull print("start: %d\n", andp->first-pp->firstinst);
529 b2cfc4e2 2003-09-30 devnull dump(pp);
532 b2cfc4e2 2003-09-30 devnull if(errors){
533 b2cfc4e2 2003-09-30 devnull free(pp);
536 b2cfc4e2 2003-09-30 devnull return pp;
539 b2cfc4e2 2003-09-30 devnull extern Reprog*
540 b2cfc4e2 2003-09-30 devnull regcomp(char *s)
542 b2cfc4e2 2003-09-30 devnull return regcomp1(s, 0, ANY);
545 b2cfc4e2 2003-09-30 devnull extern Reprog*
546 b2cfc4e2 2003-09-30 devnull regcomplit(char *s)
548 b2cfc4e2 2003-09-30 devnull return regcomp1(s, 1, ANY);
551 b2cfc4e2 2003-09-30 devnull extern Reprog*
552 b2cfc4e2 2003-09-30 devnull regcompnl(char *s)
554 b2cfc4e2 2003-09-30 devnull return regcomp1(s, 0, ANYNL);