]> CyberLeo.Net >> Repos - FreeBSD/releng/10.2.git/blob - usr.sbin/pmcstudy/eval_expr.c
- Copy stable/10@285827 to releng/10.2 in preparation for 10.2-RC1
[FreeBSD/releng/10.2.git] / usr.sbin / pmcstudy / eval_expr.c
1 /*-
2  * Copyright (c) 2015 Netflix Inc.
3  * All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1. Redistributions of source code must retain the above copyright
9  *    notice, this list of conditions and the following disclaimer,
10  *    in this position and unchanged.
11  * 2. Redistributions in binary form must reproduce the above copyright
12  *    notice, this list of conditions and the following disclaimer in the
13  *    documentation and/or other materials provided with the distribution.
14  * 3. The name of the author may not be used to endorse or promote products
15  *    derived from this software without specific prior written permission
16  *
17  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27  */
28 #include <sys/types.h>
29 #include <stdio.h>
30 #include <stdlib.h>
31 #include <unistd.h>
32 #include <string.h>
33 #include <strings.h>
34 #include <ctype.h>
35 #include "eval_expr.h"
36 __FBSDID("$FreeBSD$");
37
38 static struct expression *
39 alloc_and_hook_expr(struct expression **exp_p, struct expression **last_p)
40 {
41         struct expression *ex, *at;
42
43         ex = malloc(sizeof(struct expression));
44         if (ex == NULL) {
45                 printf("Out of memory in exp allocation\n");
46                 exit(-2);
47         }
48         memset(ex, 0, sizeof(struct expression));
49         if (*exp_p == NULL) {
50                 *exp_p = ex;
51         }
52         at = *last_p;
53         if (at == NULL) {
54                 /* First one, its last */
55                 *last_p = ex;
56         } else {
57                 /* Chain it to the end and update last */
58                 at->next = ex;
59                 ex->prev = at;
60                 *last_p = ex;
61         }
62         return (ex);
63 }
64
65
66 static int
67 validate_expr(struct expression *exp, int val1_is_set, int op_is_set, int val2_is_set, 
68               int *op_cnt)
69 {
70         int val1, op, val2;
71         int open_cnt;
72         val1 = op = val2 = 0;
73         if (val1_is_set) {
74                 val1 = 1;
75         }
76         if (op_is_set) {
77                 op = 1;
78         }
79         if (val2_is_set) {
80                 val2 = 1;
81         }
82         open_cnt = *op_cnt;
83         if (exp == NULL) {
84                 /* End of the road */
85                 if (val1 && op && val2 && (open_cnt == 0)) {
86                         return(0);
87                 } else {
88                         return(1);
89                 }
90         }
91         switch(exp->type) {
92         case TYPE_OP_PLUS:
93         case TYPE_OP_MINUS:
94         case TYPE_OP_MULT:
95         case TYPE_OP_DIVIDE:
96                 if (val1 && op && val2) {
97                         /* We are at x + y + 
98                          * collapse back to val/op
99                          */
100                         val1 = 1;
101                         op = 1;
102                         val2 = 0;
103                 } else if ((op == 0) && (val1)) {
104                         op = 1;
105                 } else {
106                         printf("Op but no val1 set\n");
107                         return(-1);
108                 }
109                 break;
110         case TYPE_PARN_OPEN:
111                 if (exp->next == NULL) {
112                         printf("NULL after open paren\n");
113                         exit(-1);
114                 }
115                 if ((exp->next->type == TYPE_OP_PLUS) ||
116                     (exp->next->type == TYPE_OP_MINUS) ||
117                     (exp->next->type == TYPE_OP_DIVIDE) ||
118                     (exp->next->type == TYPE_OP_MULT)) {
119                         printf("'( OP' -- not allowed\n");
120                         return(-1);
121                 }
122                 if (val1 && (op == 0)) {
123                         printf("'Val (' -- not allowed\n");
124                         return(-1);
125                 }
126                 if (val1 && op && val2) {
127                         printf("'Val OP Val (' -- not allowed\n");
128                         return(-1);
129                 }
130                 open_cnt++;
131                 *op_cnt = open_cnt;
132                 if (val1) {
133                         if (validate_expr(exp->next, 0, 0, 0, op_cnt) == 0) {
134                                 val2 = 1;
135                         } else {
136                                 return(-1);
137                         }
138                 } else {
139                         return(validate_expr(exp->next, 0, 0, 0, op_cnt));
140                 }
141                 break;
142         case TYPE_PARN_CLOSE:
143                 open_cnt--;
144                 *op_cnt = open_cnt;
145                 if (val1 && op && val2) {
146                         return(0);
147                 } else {
148                         printf("Found close paren and not complete\n");
149                         return(-1);
150                 }
151                 break;
152         case TYPE_VALUE_CON:
153         case TYPE_VALUE_PMC:
154                 if (val1 == 0) {
155                         val1 = 1;
156                 } else if (val1 && op) {
157                         val2 = 1;
158                 } else {
159                         printf("val1 set, val2 about to be set op empty\n");
160                         return(-1);
161                 }
162                 break;
163         default:
164                 printf("unknown type %d\n", exp->type);
165                 exit(-5);
166                 break;
167         }
168         return(validate_expr(exp->next, val1, op, val2, op_cnt));
169 }
170
171 void
172 print_exp(struct expression *exp)
173 {
174         if (exp == NULL) {
175                 printf("\n");
176                 return;
177         }
178         switch(exp->type) {
179         case TYPE_OP_PLUS:
180                 printf(" + ");
181                 break;
182         case TYPE_OP_MINUS:
183                 printf(" - ");
184                 break;
185         case TYPE_OP_MULT:
186                 printf(" * ");
187                 break;
188         case TYPE_OP_DIVIDE:
189                 printf(" / ");
190                 break;
191         case TYPE_PARN_OPEN:
192                 printf(" ( ");
193                 break;
194         case TYPE_PARN_CLOSE:
195                 printf(" ) ");
196                 break;
197         case TYPE_VALUE_CON:
198                 printf("%f", exp->value);
199                 break;
200         case TYPE_VALUE_PMC:
201                 printf("%s", exp->name);
202                 break;
203         default:
204                 printf("Unknown op %d\n", exp->type);
205                 break;
206         }
207         print_exp(exp->next);
208 }
209
210 static void
211 walk_back_and_insert_paren(struct expression **beg, struct expression *frm)
212 {
213         struct expression *at, *ex;
214
215         /* Setup our new open paren */
216         ex = malloc(sizeof(struct expression));
217         if (ex == NULL) {
218                 printf("Out of memory in exp allocation\n");
219                 exit(-2);
220         }
221         memset(ex, 0, sizeof(struct expression));
222         ex->type = TYPE_PARN_OPEN;
223         /* Now lets place it */
224         at = frm->prev;
225         if (at == *beg) {
226                 /* We are inserting at the head of the list */
227         in_beg:
228                 ex->next = at;
229                 at->prev = ex;
230                 *beg = ex;
231                 return;
232         } else if ((at->type == TYPE_VALUE_CON) ||
233             (at->type == TYPE_VALUE_PMC)) {
234                 /* Simple case we have a value in the previous position */
235         in_mid:
236                 ex->prev = at->prev;
237                 ex->prev->next = ex;
238                 ex->next = at;
239                 at->prev = ex;
240                 return;
241         } else if (at->type == TYPE_PARN_CLOSE) {
242                 /* Skip through until we reach beg or all ( closes */
243                 int par_cnt=1;
244
245                 at = at->prev;
246                 while(par_cnt) {
247                         if (at->type == TYPE_PARN_CLOSE) {
248                                 par_cnt++;
249                         } else if (at->type == TYPE_PARN_OPEN) {
250                                 par_cnt--;
251                                 if (par_cnt == 0) {
252                                         break;
253                                 }
254                         }
255                         at = at->prev;
256                 }
257                 if (at == *beg) {
258                         /* At beginning we insert */
259                         goto in_beg;
260                 } else {
261                         goto in_mid;
262                 }
263         } else {
264                 printf("%s:Unexpected type:%d?\n", 
265                        __FUNCTION__, at->type);
266                 exit(-1);
267         }
268 }
269
270 static void
271 walk_fwd_and_insert_paren(struct expression *frm, struct expression **added)
272 {
273         struct expression *at, *ex;
274         /* Setup our new close paren */
275         ex = malloc(sizeof(struct expression));
276         if (ex == NULL) {
277                 printf("Out of memory in exp allocation\n");
278                 exit(-2);
279         }
280         memset(ex, 0, sizeof(struct expression));
281         ex->type = TYPE_PARN_CLOSE;
282         *added = ex;
283         /* Now lets place it */
284         at = frm->next;
285         if ((at->type == TYPE_VALUE_CON) ||
286             (at->type == TYPE_VALUE_PMC)) {
287                 /* Simple case we have a value in the previous position */
288         insertit:
289                 ex->next = at->next;
290                 ex->prev = at;
291                 at->next = ex;
292                 return;
293         } else if (at->type == TYPE_PARN_OPEN) {
294                 int par_cnt=1;
295                 at = at->next;
296                 while(par_cnt) {
297                         if (at->type == TYPE_PARN_OPEN) {
298                                 par_cnt++;
299                         } else if (at->type == TYPE_PARN_CLOSE) {
300                                 par_cnt--;
301                                 if (par_cnt == 0) {
302                                         break;
303                                 }
304                         }
305                         at = at->next;
306                 }
307                 goto insertit;
308         } else {
309                 printf("%s:Unexpected type:%d?\n", 
310                        __FUNCTION__,
311                        at->type);
312                 exit(-1);
313         }
314 }
315
316
317 static void
318 add_precendence(struct expression **beg, struct expression *start, struct expression *end)
319 {
320         /* 
321          * Between start and end add () around any * or /. This
322          * is quite tricky since if there is a () set inside the
323          * list we need to skip over everything in the ()'s considering
324          * that just a value.
325          */
326         struct expression *at, *newone;
327         int open_cnt;
328
329         at = start;
330         open_cnt = 0;
331         while(at != end) {
332                 if (at->type == TYPE_PARN_OPEN) {
333                         open_cnt++;
334                 }
335                 if (at->type == TYPE_PARN_CLOSE) {
336                         open_cnt--;
337                 }
338                 if (open_cnt == 0) {
339                         if ((at->type == TYPE_OP_MULT) ||
340                             (at->type == TYPE_OP_DIVIDE)) {
341                                 walk_back_and_insert_paren(beg, at);
342                                 walk_fwd_and_insert_paren(at, &newone);
343                                 at = newone->next;
344                                 continue;
345                         }
346                 }
347                 at = at->next;
348         }
349         
350 }
351
352 static void
353 set_math_precidence(struct expression **beg, struct expression *exp, struct expression **stopped)
354 {
355         struct expression *at, *start, *end;
356         int cnt_lower, cnt_upper;
357         /* 
358          * Walk through and set any math precedence to 
359          * get proper precedence we insert () around * / over + -
360          */
361         end = NULL;
362         start = at = exp;
363         cnt_lower = cnt_upper = 0;
364         while(at) { 
365                 if (at->type == TYPE_PARN_CLOSE) {
366                         /* Done with that paren */
367                         if (stopped) {
368                                 *stopped = at;
369                         }
370                         if (cnt_lower && cnt_upper) {
371                                 /* We have a mixed set ... add precedence between start/end */
372                                 add_precendence(beg, start, end);
373                         }
374                         return;
375                 }
376                 if (at->type == TYPE_PARN_OPEN) {
377                         set_math_precidence(beg, at->next, &end);
378                         at = end;
379                         continue;
380                 } else if ((at->type == TYPE_OP_PLUS) ||
381                            (at->type == TYPE_OP_MINUS)) {
382                         cnt_lower++;
383                 } else if ((at->type == TYPE_OP_DIVIDE) ||
384                            (at->type == TYPE_OP_MULT)) {
385                         cnt_upper++;
386                 }
387                 at = at->next;
388         }
389         if (cnt_lower && cnt_upper) {
390                 add_precendence(beg, start, NULL);
391         }
392 }
393
394 extern char **valid_pmcs;
395 extern int valid_pmc_cnt;
396
397 static void
398 pmc_name_set(struct expression *at)
399 {
400         int i, idx, fnd;
401
402         if (at->name[0] == '%') {
403                 /* Special number after $ gives index */
404                 idx = strtol(&at->name[1], NULL, 0);
405                 if (idx >= valid_pmc_cnt) {
406                         printf("Unknown PMC %s -- largest we have is $%d -- can't run your expression\n",
407                                at->name, valid_pmc_cnt);
408                         exit(-1);
409                 }
410                 strcpy(at->name, valid_pmcs[idx]);
411         } else {
412                 for(i=0, fnd=0; i<valid_pmc_cnt; i++) {
413                         if (strcmp(valid_pmcs[i], at->name) == 0) {
414                                 fnd = 1;
415                                 break;
416                         }
417                 }
418                 if (!fnd) {
419                         printf("PMC %s does not exist on this machine -- can't run your expression\n",
420                                at->name);
421                         exit(-1);
422                 }
423         }
424 }
425
426 struct expression *
427 parse_expression(char *str)
428 {
429         struct expression *exp=NULL, *last=NULL, *at;
430         int open_par, close_par;
431         int op_cnt=0;
432         size_t siz, i, x;
433         /* 
434          * Walk through a string expression and convert
435          * it to a linked list of actions. We do this by:
436          * a) Counting the open/close paren's, there must
437          *    be a matching number.
438          * b) If we have balanced paren's then create a linked list
439          *    of the operators, then we validate that expression further.
440          * c) Validating that we have:
441          *      val OP val <or>
442          *      val OP (  <and>
443          *    inside every paran you have a:
444          *      val OP val <or>
445          *      val OP (   <recursively>
446          * d) A final optional step (not implemented yet) would be
447          *    to insert the mathimatical precedence paran's. For
448          *    the start we will just do the left to right evaluation and
449          *    then later we can add this guy to add paran's to make it
450          *    mathimatically correct... i.e instead of 1 + 2 * 3 we
451          *    would translate it into 1 + ( 2 * 3).
452          */
453         open_par = close_par = 0;
454         siz = strlen(str);
455         /* No trailing newline please */
456         if (str[(siz-1)] == '\n') {
457                 str[(siz-1)] = 0;
458                 siz--;
459         }
460         for(i=0; i<siz; i++) {
461                 if (str[i] == '(') {
462                         open_par++;
463                 } else if (str[i] == ')') {
464                         close_par++;
465                 }
466         }
467         if (open_par != close_par) {
468                 printf("Invalid expression '%s' %d open paren's and %d close?\n",
469                        str, open_par, close_par);
470                 exit(-1);
471         }
472         for(i=0; i<siz; i++) {
473                 if (str[i] == '(') {
474                         at = alloc_and_hook_expr(&exp, &last);
475                         at->type = TYPE_PARN_OPEN;
476                 } else if (str[i] == ')') {
477                         at = alloc_and_hook_expr(&exp, &last);
478                         at->type = TYPE_PARN_CLOSE;
479                 } else if (str[i] == ' ') {
480                         /* Extra blank */
481                         continue;
482                 } else if (str[i] == '\t') {
483                         /* Extra tab */
484                         continue;
485                 } else if (str[i] == '+') {
486                         at = alloc_and_hook_expr(&exp, &last);
487                         at->type = TYPE_OP_PLUS;
488                 } else if (str[i] == '-') {
489                         at = alloc_and_hook_expr(&exp, &last);
490                         at->type = TYPE_OP_MINUS;
491                 } else if (str[i] == '/') {
492                         at = alloc_and_hook_expr(&exp, &last);
493                         at->type = TYPE_OP_DIVIDE;
494                 } else if (str[i] == '*') {
495                         at = alloc_and_hook_expr(&exp, &last);
496                         at->type = TYPE_OP_MULT;
497                 } else {
498                         /* Its a value or PMC constant */
499                         at = alloc_and_hook_expr(&exp, &last);
500                         if (isdigit(str[i]) || (str[i] == '.')) {
501                                 at->type = TYPE_VALUE_CON;
502                         } else {
503                                 at->type = TYPE_VALUE_PMC;
504                         }
505                         x = 0;
506                         while ((str[i] != ' ') && 
507                                (str[i] != '\t') && 
508                                (str[i] != 0) && 
509                                (str[i] != ')') &&
510                                (str[i] != '(')) {
511                                 /* We collect the constant until a space or tab */
512                                 at->name[x] = str[i];
513                                 i++;
514                                 x++;
515                                 if (x >=(sizeof(at->name)-1)) {
516                                         printf("Value/Constant too long %d max:%d\n",
517                                                (int)x, (int)(sizeof(at->name)-1));
518                                         exit(-3);
519                                 }
520                         }
521                         if (str[i] != 0) {
522                                 /* Need to back up and see the last char since
523                                  * the for will increment the loop.
524                                  */
525                                 i--;
526                         }
527                         /* Now we have pulled the string, set it up */
528                         if (at->type == TYPE_VALUE_CON) {
529                                 at->state = STATE_FILLED;
530                                 at->value = strtod(at->name, NULL);
531                         } else {
532                                 pmc_name_set(at);
533                         }
534                 }
535         }
536         /* Now lets validate its a workable expression */
537         if (validate_expr(exp, 0, 0, 0, &op_cnt)) {
538                 printf("Invalid expression\n");
539                 exit(-4);
540         }
541         set_math_precidence(&exp, exp, NULL);
542         return (exp);
543 }
544
545
546
547 static struct expression *
548 gather_exp_to_paren_close(struct expression *exp, double *val_fill)
549 {
550         /*
551          * I have been given ( ???
552          * so I could see either
553          * (
554          * or
555          * Val Op
556          *
557          */
558         struct expression *lastproc;
559         double val;
560
561         if (exp->type == TYPE_PARN_OPEN) {
562                 lastproc = gather_exp_to_paren_close(exp->next, &val);
563                 *val_fill = val;
564         } else {
565                 *val_fill = run_expr(exp, 0, &lastproc);
566         }
567         return(lastproc);
568 }
569
570
571 double
572 run_expr(struct expression *exp, int initial_call, struct expression **lastone)
573 {
574         /* 
575          * We expect to find either
576          * a) A Open Paren
577          * or
578          * b) Val-> Op -> Val
579          * or
580          * c) Val-> Op -> Open Paren
581          */
582         double val1, val2, res;
583         struct expression *op, *other_half, *rest;
584         
585         if (exp->type == TYPE_PARN_OPEN) {
586                 op = gather_exp_to_paren_close(exp->next, &val1);
587         } else if(exp->type == TYPE_VALUE_CON) {
588                 val1 = exp->value;
589                 op = exp->next;
590         } else if (exp->type ==  TYPE_VALUE_PMC) {
591                 val1 = exp->value;
592                 op = exp->next;
593         } else {
594                 printf("Illegal value in %s huh?\n", __FUNCTION__);
595                 exit(-1);
596         }
597         if (op == NULL) {
598                 return (val1);
599         }
600 more_to_do:
601         other_half = op->next;
602         if (other_half->type == TYPE_PARN_OPEN) {
603                 rest = gather_exp_to_paren_close(other_half->next, &val2);
604         } else if(other_half->type == TYPE_VALUE_CON) {
605                 val2 = other_half->value;
606                 rest = other_half->next;
607         } else if (other_half->type ==  TYPE_VALUE_PMC) {
608                 val2 = other_half->value;
609                 rest = other_half->next;
610         } else {
611                 printf("Illegal2 value in %s huh?\n", __FUNCTION__);
612                 exit(-1);
613         }
614         switch(op->type) {
615         case TYPE_OP_PLUS:
616                 res = val1 + val2;
617                 break;
618         case TYPE_OP_MINUS:             
619                 res = val1 - val2;
620                 break;
621         case TYPE_OP_MULT:
622                 res = val1 * val2;
623                 break;
624         case TYPE_OP_DIVIDE:
625                 if (val2 != 0.0)
626                         res = val1 / val2;
627                 else {
628                         printf("Division by zero averted\n");
629                         res = 1.0;
630                 }       
631                 break;
632         default:
633                 printf("Op is not an operator -- its %d\n",
634                        op->type);
635                 exit(-1);
636                 break;
637         }
638         if (rest == NULL) {
639                 if (lastone) {
640                         *lastone = NULL;
641                 }
642                 return (res);
643         }
644         if ((rest->type == TYPE_PARN_CLOSE) && (initial_call == 0)) {
645                 if (lastone) {
646                         *lastone = rest->next;
647                 }
648                 return(res);
649         }
650         /* There is more, as in
651          * a + b + c
652          * where we just did a + b
653          * so now it becomes val1 is set to res and
654          * we need to proceed with the rest of it.
655          */
656         val1 = res;
657         op = rest;
658         if ((op->type != TYPE_OP_PLUS) &&
659             (op->type != TYPE_OP_MULT) &&
660             (op->type != TYPE_OP_MINUS) &&
661             (op->type != TYPE_OP_DIVIDE)) {
662                 printf("%s ending on type:%d not an op??\n", __FUNCTION__, op->type);
663                 return(res);
664         }
665         if (op)
666                 goto more_to_do;
667         return (res);
668 }
669
670 #ifdef STAND_ALONE_TESTING
671
672 static double
673 calc_expr(struct expression *exp)
674 {
675         struct expression *at;
676         double xx;
677
678         /* First clear PMC's setting */
679         for(at = exp; at != NULL; at = at->next) {
680                 if (at->type == TYPE_VALUE_PMC) {
681                         at->state = STATE_UNSET;
682                 }
683         }
684         /* Now for all pmc's make up values .. here is where I would pull them */
685         for(at = exp; at != NULL; at = at->next) {
686                 if (at->type == TYPE_VALUE_PMC) {
687                         at->value = (random() * 1.0);
688                         at->state = STATE_FILLED;
689                         if (at->value == 0.0) {
690                                 /* So we don't have div by 0 */
691                                 at->value = 1.0;
692                         }
693                 }
694         }
695         /* Now lets calculate the expression */
696         print_exp(exp);
697         xx = run_expr(exp, 1, NULL);
698         printf("Answer is %f\n", xx);
699         return(xx);
700 }
701
702
703 int 
704 main(int argc, char **argv) 
705 {
706         struct expression *exp;
707         if (argc < 2) {
708                 printf("Use %s expression\n", argv[0]);
709                 return(-1);
710         }
711         exp = parse_expression(argv[1]);
712         printf("Now the calc\n");
713         calc_expr(exp);
714         return(0);
715 }
716
717 #endif