1 /****************************************************************************
2 Copyright (C) 1987-2015 by Jeffery P. Hansen
3
4 This program is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; either version 2 of the License, or
7 (at your option) any later version.
8
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
13
14 You should have received a copy of the GNU General Public License along
15 with this program; if not, write to the Free Software Foundation, Inc.,
16 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
17 ****************************************************************************/
18 #include <stdlib.h>
19 #include <stdio.h>
20 #include <string.h>
21 #include "yybasic.h"
22 #include "vgrammar.h"
23 #include "hash.h"
24 #include "ycmalloc.h"
25
26 struct opsym {
27 int opCode;
28 char *opSym;
29 };
30
31 int expr_error;
32 const char *expr_errsym = 0;
33
34 static int Expr_eval_aux(SHash *H,Expr *e,int *rval,EValueLookup *f,void *d);
35
36 struct opsym opsymTable[] = {
37 {ADD,"+"},
38 {SUB,"-"},
39 {MUL,"*"},
40 {POW,"**"},
41 {DIV,"/"},
42 {OR,"||"},
43 {AND,"&&"},
44 {GT,">"},
45 {GE,">="},
46 {LT,"<"},
47 {LE,"<="},
48 {EQ,"=="},
49 {NE,"!="},
50 {NOT,"!"},
51 };
52
findSymbol(int code)53 static const char *findSymbol(int code)
54 {
55 int n = sizeof(opsymTable)/sizeof(opsymTable[0]);
56 int i;
57
58 for (i = 0;i < n;i++)
59 if (code == opsymTable[i].opCode)
60 return opsymTable[i].opSym;
61 return "?";
62 }
63
intdup(int n)64 static int *intdup(int n)
65 {
66 int *p = (int*)malloc(sizeof(int));
67 *p = n;
68 return p;
69 }
70
new_Expr()71 static Expr *new_Expr()
72 {
73 Expr *E = (Expr*) malloc(sizeof(Expr));
74
75 memset(E,0,sizeof(*E));
76
77 return E;
78 }
79
delete_Expr(Expr * E)80 void delete_Expr(Expr *E)
81 {
82 if (!E) return;
83 if (E->lit) free(E->lit);
84 if (E->l) delete_Expr(E->l);
85 if (E->r) delete_Expr(E->r);
86 if (E->x) delete_Expr(E->x);
87 free(E);
88 }
89
90
Expr_lit(const char * l)91 Expr *Expr_lit(const char *l)
92 {
93 Expr *E = new_Expr();
94
95 E->op = LITERAL;
96 E->lit = strdup(l);
97
98 return E;
99 }
100
Expr_num(int n)101 Expr *Expr_num(int n)
102 {
103 Expr *E = new_Expr();
104
105 E->op = NUMBER;
106 E->value = n;
107
108 return E;
109 }
110
Expr_op(int op,Expr * l,Expr * r)111 Expr *Expr_op(int op,Expr *l,Expr *r)
112 {
113 Expr *E = new_Expr();
114
115 E->op = op;
116 E->l = l;
117 E->r = r;
118
119 return E;
120 }
121
Expr_op3(int op,Expr * l,Expr * r,Expr * x)122 Expr *Expr_op3(int op,Expr *l,Expr *r,Expr *x)
123 {
124 Expr *E = new_Expr();
125
126 E->op = op;
127 E->l = l;
128 E->r = r;
129 E->x = x;
130
131 return E;
132 }
133
Expr_case(int op,int tag)134 Expr *Expr_case(int op,int tag)
135 {
136 Expr *E = new_Expr();
137
138 E->op = op;
139 E->value = tag;
140
141 return E;
142 }
Expr_func(const char * f,Expr * l,Expr * r)143 Expr *Expr_func(const char *f,Expr *l,Expr *r)
144 {
145 Expr *E = new_Expr();
146
147 E->op = FUNC;
148 E->lit = strdup(f);
149 E->l = l;
150 E->r = r;
151
152 return E;
153 }
154
apply_op(int op,int a,int b,int * err)155 static int apply_op(int op,int a,int b,int *err)
156 {
157 *err = 0;
158
159 switch (op) {
160 case ADD :
161 return a+b;
162 case SUB :
163 return a-b;
164 case POW :
165 {
166 int p = 1;
167 if (b > 32) *err = EE_OVERFLOW;
168 while (b-- > 0) p *= a;
169 return p;
170 }
171 case MUL :
172 return a*b;
173 case DIV :
174 if (b != 0) return a/b;
175 else *err = EE_DIV0;
176 break;
177 case OR :
178 return a||b;
179 case AND :
180 return a&&b;
181 case GT :
182 return a>b;
183 case GE :
184 return a>=b;
185 case LT :
186 return a<b;
187 case LE :
188 return a<=b;
189 case EQ :
190 return a==b;
191 case NE :
192 return a!=b;
193 case NOT :
194 return !b;
195 case UNEG :
196 return -b;
197 }
198 return 0;
199 }
200
Expr_eval_default(SHash * H,Expr * e,int * rval,EValueLookup * f,void * d)201 static int Expr_eval_default(SHash *H,Expr *e,int *rval,EValueLookup *f,void *d)
202 {
203 int rr;
204
205 if (!e) return EE_NOCASE;
206
207
208 if (e->op == DEFAULT) return 0;
209 if (e->op != NEXT) {
210 return EE_NOCASE;
211 }
212
213 rr = Expr_eval_default(H,e->l,rval,f,d);
214 if (rr == EE_NOCASE)
215 rr = Expr_eval_default(H,e->r,rval,f,d);
216 else if (!rr)
217 rr = Expr_eval_aux(H,e->r,rval,f,d);
218
219 return rr;
220 }
221
Expr_eval_switch(int s,SHash * H,Expr * e,int * rval,EValueLookup * f,void * d)222 static int Expr_eval_switch(int s,SHash *H,Expr *e,int *rval,EValueLookup *f,void *d)
223 {
224 int rr;
225
226 if (!e) return EE_NOCASE;
227
228
229 if (e->op == CASE && e->value == s) return 0;
230 if (e->op != NEXT) {
231 return EE_NOCASE;
232 }
233
234 rr = Expr_eval_switch(s,H,e->l,rval,f,d);
235 if (rr == EE_NOCASE)
236 rr = Expr_eval_switch(s,H,e->r,rval,f,d);
237 else if (!rr)
238 rr = Expr_eval_aux(H,e->r,rval,f,d);
239
240 return rr;
241 }
242
Expr_eval_aux(SHash * H,Expr * e,int * rval,EValueLookup * f,void * d)243 static int Expr_eval_aux(SHash *H,Expr *e,int *rval,EValueLookup *f,void *d)
244 {
245 if (!e) {
246 *rval = 0;
247 return 0;
248 }
249
250 switch (e->op) {
251 case LITERAL :
252 {
253 int *h = 0;
254
255 if (H)
256 h = SHash_find(H,e->lit);
257
258 if (!h) {
259 expr_errsym = e->lit;
260 return EE_NOTDEF;
261 }
262
263 *rval = *h;
264 return 0;
265 }
266 break;
267 case FUNC :
268 {
269 int nl = 0,nr = 0,nx = 0,rr;
270
271 if (strcmp(e->lit,"bits") == 0
272 || strcmp(e->lit,"inv") == 0
273 || strcmp(e->lit,"num") == 0) {
274 if (e->l->op != LITERAL) return EE_NOTLIT;
275 if (!f) {
276 expr_errsym = e->l->lit;
277 return EE_NOTDEF;
278 }
279 return (*f)(e->lit,e->l->lit,d,rval);
280 }
281
282 if (e->l && (rr = Expr_eval_aux(H,e->l,&nl,f,d))) return rr;
283 if (e->r && (rr = Expr_eval_aux(H,e->r,&nr,f,d) < 0)) return rr;
284 if (e->x && (rr = Expr_eval_aux(H,e->x,&nx,f,d) < 0)) return rr;
285
286 if (strcmp(e->lit,"log") == 0) {
287 int n = 0;
288 int a = 0;
289 while (nl) {
290 if ((nl != 1) && (nl & 1)) a = 1;
291 nl >>= 1;
292 n++;
293 }
294 n += a;
295 *rval = n;
296 return 0;
297 } else {
298 expr_errsym = e->lit;
299 return EE_BADFUNC;
300 }
301 }
302 break;
303 case NUMBER :
304 *rval = e->value;
305 return 0;
306 break;
307 case ADD :
308 case SUB :
309 case MUL :
310 case POW :
311 case DIV :
312 case OR :
313 case AND :
314 case GT :
315 case GE :
316 case LT :
317 case LE :
318 case EQ :
319 case NE :
320 {
321 int nl,nr,rr,err;
322
323 if (!e->l || !e->r) return EE_INTERNAL;
324 if ((rr = Expr_eval_aux(H,e->l,&nl,f,d))) return rr;
325 if ((rr = Expr_eval_aux(H,e->r,&nr,f,d))) return rr;
326
327 *rval = apply_op(e->op,nl,nr,&err);
328 return err;
329 }
330 break;
331 case NOT :
332 case UNEG :
333 {
334 int nr,rr,err;
335
336 if (!e->r) return EE_INTERNAL;
337 if ((rr = Expr_eval_aux(H,e->r,&nr,f,d))) return rr;
338
339 *rval = apply_op(e->op,0,nr,&err);
340 return err;
341 }
342 break;
343 case NEXT :
344 {
345 int rr;
346
347 if (e->l && (rr = Expr_eval_aux(H,e->l,rval,f,d))) return rr;
348 if (e->r && (rr = Expr_eval_aux(H,e->r,rval,f,d))) return rr;
349 return 0;
350 }
351 break;
352 case ASGN :
353 {
354 int rr;
355 int *h;
356
357 if (!H) return EE_INTERNAL;
358 if (!e->l || e->l->op != LITERAL) return EE_INTERNAL;
359 if ((rr = Expr_eval_aux(H,e->r,rval,f,d))) return rr;
360
361 if ((h = SHash_find(H,e->l->lit))) {
362 SHash_remove(H,e->l->lit);
363 free(h);
364 }
365 SHash_insert(H,e->l->lit,intdup(*rval));
366 return 0;
367 }
368 break;
369 case IF :
370 {
371 int rr,c;
372
373 if ((rr = Expr_eval_aux(H,e->l,&c,f,d))) return rr;
374
375 if (c) {
376 if ((rr = Expr_eval_aux(H,e->r,rval,f,d))) return rr;
377 } else {
378 if ((rr = Expr_eval_aux(H,e->x,rval,f,d))) return rr;
379 }
380
381 return 0;
382 }
383 break;
384 case BREAK :
385 *rval = 0;
386 return EE_BREAK;
387 case RETURN :
388 {
389 int rr;
390
391 if ((rr = Expr_eval_aux(H,e->l,rval,f,d))) return rr;
392 return EE_RETURN;
393 }
394 break;
395 case DEFAULT :
396 case CASE :
397 return 0;
398 case SWITCH :
399 {
400 int rr,s;
401
402 if ((rr = Expr_eval_aux(H,e->l,&s,f,d))) return rr;
403
404 rr = Expr_eval_switch(s,H,e->r,rval,f,d);
405 if (rr == EE_OK) return 0;
406 if (rr == EE_BREAK) return 0;
407 if (rr == EE_RETURN) return rr;
408 if (rr != EE_NOCASE) return rr;
409
410 rr = Expr_eval_default(H,e->r,rval,f,d);
411 if (rr == EE_BREAK) return 0;
412 if (rr == EE_NOCASE) return 0;
413 return rr;
414 }
415 }
416 return EE_INTERNAL;
417 }
418
Expr_eval(Expr * e,int * rval,EValueLookup * f,void * d)419 int Expr_eval(Expr *e,int *rval,EValueLookup *f,void *d)
420 {
421 if (e && e->op == NEXT) {
422 int ec;
423 SHash *H = new_SHash_noob();
424
425 ec = Expr_eval_aux(H,e,rval,f,d);
426 delete_SHash(H);
427
428 if (ec == EE_RETURN) ec = EE_OK;
429 return ec;
430 } else
431 return Expr_eval_aux(0,e,rval,f,d);
432
433
434 }
435
436 /*****************************************************************************
437 *
438 * Print an expression to a string a la sprintf
439 *
440 * Parameters:
441 *
442 * s Buffer to which to print expression
443 * n Size of the string buffer.
444 * e Expression to print
445 *
446 * Returns: Number of characters printed on success, -1 on failure.
447 *
448 * Note, only basic expression are supported by this function.
449 *
450 *****************************************************************************/
Expr_sprint(char * s,int n,Expr * e)451 int Expr_sprint(char *s,int n,Expr *e)
452 {
453 int l;
454 char *start = s;
455
456 if (!e) return -1;
457
458 switch (e->op) {
459 case LITERAL :
460 if (strlen(e->lit) >= n)
461 return -1;
462
463 strcpy(s,e->lit);
464 return strlen(s);
465 case FUNC :
466 if (strlen(e->lit)+strlen(e->l->lit)+2 >= n)
467 return -1;
468
469 return sprintf(s,"%s(%s)",e->lit,e->l->lit);
470 case NUMBER :
471 {
472 char buf[1024];
473 sprintf(buf,"%d",e->value);
474
475 if (strlen(buf) >= n)
476 return -1;
477
478 strcpy(s,buf);
479 return strlen(s);
480 }
481 break;
482 case ADD :
483 case SUB :
484 case MUL :
485 case POW :
486 case DIV :
487 case OR :
488 case AND :
489 case GT :
490 case GE :
491 case LT :
492 case LE :
493 case EQ :
494 case NE :
495 if (n < 4) return -1;
496 s += sprintf(s,"(");n--;
497 l = Expr_sprint(s,n,e->l);
498 if (l < 0) return -1;
499 s += l; n -= l;
500 if (n < 4) return -1;
501 s += sprintf(s,"%s",findSymbol(e->op));n -= strlen(s);
502 l = Expr_sprint(s,n,e->r);
503 if (l < 0) return -1;
504 s += l; n -= l;
505 if (n < 2) return -1;
506 s += sprintf(s,")");
507
508 return strlen(start);
509 case NOT :
510 if (n < 2) return -1;
511 *s++ = '!'; n--;
512 l = Expr_sprint(s,n,e->l);
513 if (l < 0) return -1;
514 return strlen(start);
515 case UNEG :
516 if (n < 2) return -1;
517 *s++ = '-'; n--;
518 l = Expr_sprint(s,n,e->l);
519 if (l < 0) return -1;
520 return strlen(start);
521 }
522 return -1;
523 }
524
Expr_print(Expr * e)525 int Expr_print(Expr *e)
526 {
527 if (!e) {
528 printf("; ");
529 return 0;
530 }
531
532 switch (e->op) {
533 case LITERAL :
534 printf("%s",e->lit);
535 break;
536 case FUNC :
537 printf("%s(%s)",e->lit,e->l->lit);
538 break;
539 case NUMBER :
540 printf("%d",e->value);
541 break;
542 case ADD :
543 case SUB :
544 case MUL :
545 case POW :
546 case DIV :
547 case OR :
548 case AND :
549 case GT :
550 case GE :
551 case LT :
552 case LE :
553 case EQ :
554 case NE :
555 printf("("); Expr_print(e->l); printf("%s",findSymbol(e->op)); Expr_print(e->r); printf(")");
556 break;
557 case NOT :
558 printf("!");
559 Expr_print(e->l);
560 break;
561 case UNEG :
562 printf("-");
563 Expr_print(e->l);
564 break;
565 case NEXT :
566 printf("{");
567 if (e->l) {
568 Expr_print(e->l);
569 }
570 if (e->r) {
571 Expr_print(e->r);
572 }
573 printf("}");
574 break;
575 case ASGN :
576 printf("%s = ",e->l->lit);
577 Expr_print(e->r);
578 printf("; ");
579 break;
580 case IF :
581 printf("if (");
582 Expr_print(e->l);
583 printf(")");
584 Expr_print(e->r);
585 if (e->x) {
586 printf(" else ");
587 Expr_print(e->x);
588 }
589 break;
590 case BREAK :
591 printf(" break;");
592 break;
593 case RETURN :
594 printf(" return;");
595 break;
596 case DEFAULT :
597 printf(" default :");
598 break;
599 case CASE :
600 printf(" case %d :",e->value);
601 break;
602 case SWITCH :
603 printf("switch (");
604 Expr_print(e->l);
605 printf(")");
606 Expr_print(e->r);
607 }
608 return 0;
609 }
610