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