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