4 static inline void eval_node_free(EVAL_NODE *op);
5 static inline EVAL_NODE *parse_full_expression(const char **string, int *error);
6 static inline EVAL_NODE *parse_one_full_operand(const char **string, int *error);
7 static inline calculated_number eval_node(EVAL_NODE *op, int *error);
9 static inline void skip_spaces(const char **string) {
10 const char *s = *string;
11 while(isspace(*s)) s++;
15 // ----------------------------------------------------------------------------
16 // operators that work on 2 operands
18 static inline int isoperatorterm_word(const char s) {
19 if(isspace(s) || s == '(' || s == '$' || s == '!' || s == '-' || s == '+' || isdigit(s)) return 1;
23 static inline int isoperatorterm_symbol(const char s) {
24 if(isoperatorterm_word(s) || isalpha(s)) return 1;
28 static inline int parse_and(const char **string) {
29 const char *s = *string;
32 if((s[0] == 'A' || s[0] == 'a') && (s[1] == 'N' || s[1] == 'n') && (s[2] == 'D' || s[2] == 'd') && isoperatorterm_word(s[3])) {
38 if(s[0] == '&' && s[1] == '&' && isoperatorterm_symbol(s[2])) {
46 static inline int parse_or(const char **string) {
47 const char *s = *string;
50 if((s[0] == 'O' || s[0] == 'o') && (s[1] == 'R' || s[1] == 'r') && isoperatorterm_word(s[2])) {
56 if(s[0] == '|' && s[1] == '|' && isoperatorterm_symbol(s[2])) {
64 static inline int parse_greater_than_or_equal(const char **string) {
65 const char *s = *string;
68 if(s[0] == '>' && s[1] == '=' && isoperatorterm_symbol(s[2])) {
76 static inline int parse_less_than_or_equal(const char **string) {
77 const char *s = *string;
80 if (s[0] == '<' && s[1] == '=' && isoperatorterm_symbol(s[2])) {
88 static inline int parse_greater(const char **string) {
89 const char *s = *string;
92 if(s[0] == '>' && isoperatorterm_symbol(s[1])) {
100 static inline int parse_less(const char **string) {
101 const char *s = *string;
104 if(s[0] == '<' && isoperatorterm_symbol(s[1])) {
112 static inline int parse_equal(const char **string) {
113 const char *s = *string;
116 if(s[0] == '=' && s[1] == '=' && isoperatorterm_symbol(s[2])) {
122 if(s[0] == '=' && isoperatorterm_symbol(s[1])) {
130 static inline int parse_not_equal(const char **string) {
131 const char *s = *string;
134 if(s[0] == '!' && s[1] == '=' && isoperatorterm_symbol(s[2])) {
140 if(s[0] == '<' && s[1] == '>' && isoperatorterm_symbol(s[2])) {
147 static inline int parse_multiply(const char **string) {
148 const char *s = *string;
151 if(s[0] == '*' && isoperatorterm_symbol(s[1])) {
159 static inline int parse_divide(const char **string) {
160 const char *s = *string;
163 if(s[0] == '/' && isoperatorterm_symbol(s[1])) {
171 static inline int parse_minus(const char **string) {
172 const char *s = *string;
175 if(s[0] == '-' && isoperatorterm_symbol(s[1])) {
183 static inline int parse_plus(const char **string) {
184 const char *s = *string;
187 if(s[0] == '+' && isoperatorterm_symbol(s[1])) {
195 static inline int parse_open_subexpression(const char **string) {
196 const char *s = *string;
207 static inline int parse_close_subexpression(const char **string) {
208 const char *s = *string;
219 static inline int parse_constant(const char **string, calculated_number *number) {
221 calculated_number n = strtold(*string, &end);
222 if(unlikely(!end || *string == end || isnan(n) || isinf(n))) {
231 // ----------------------------------------------------------------------------
232 // operators that affect a single operand
234 static inline int parse_not(const char **string) {
235 const char *s = *string;
238 if((s[0] == 'N' || s[0] == 'n') && (s[1] == 'O' || s[1] == 'o') && (s[2] == 'T' || s[2] == 't') && isoperatorterm_word(s[3])) {
243 if(s[0] == EVAL_OPERATOR_NOT) {
251 static struct operator_parser {
253 int (*parse)(const char **);
254 } operator_parsers[] = {
255 // the order in this list is important!
256 // the first matching will be used
257 // so place the longer of overlapping ones
260 { EVAL_OPERATOR_AND, parse_and },
261 { EVAL_OPERATOR_OR, parse_or },
262 { EVAL_OPERATOR_GREATER_THAN_OR_EQUAL, parse_greater_than_or_equal },
263 { EVAL_OPERATOR_LESS_THAN_OR_EQUAL, parse_less_than_or_equal },
264 { EVAL_OPERATOR_NOT_EQUAL, parse_not_equal },
265 { EVAL_OPERATOR_EQUAL, parse_equal },
266 { EVAL_OPERATOR_LESS, parse_less },
267 { EVAL_OPERATOR_GREATER, parse_greater },
268 { EVAL_OPERATOR_PLUS, parse_plus },
269 { EVAL_OPERATOR_MINUS, parse_minus },
270 { EVAL_OPERATOR_MULTIPLY, parse_multiply },
271 { EVAL_OPERATOR_DIVIDE, parse_divide },
273 /* we should not put in this list the following:
279 * these are handled in code
282 { EVAL_OPERATOR_NOP, NULL }
285 // ----------------------------------------------------------------------------
286 // evaluation of operations
288 static inline calculated_number eval_check_number(calculated_number n, int *error) {
289 if(unlikely(isnan(n))) {
290 *error = EVAL_ERROR_VALUE_IS_NAN;
294 if(unlikely(isinf(n))) {
295 *error = EVAL_ERROR_VALUE_IS_INFINITE;
302 static inline calculated_number eval_value(EVAL_VALUE *v, int *error) {
306 case EVAL_VALUE_EXPRESSION:
307 n = eval_node(v->expression, error);
310 case EVAL_VALUE_NUMBER:
314 // case EVAL_VALUE_VARIABLE:
318 *error = EVAL_ERROR_INVALID_VALUE;
323 return eval_check_number(n, error);
326 calculated_number eval_and(EVAL_NODE *op, int *error) {
327 return eval_value(&op->ops[0], error) && eval_value(&op->ops[1], error);
329 calculated_number eval_or(EVAL_NODE *op, int *error) {
330 return eval_value(&op->ops[0], error) || eval_value(&op->ops[1], error);
332 calculated_number eval_greater_than_or_equal(EVAL_NODE *op, int *error) {
333 return eval_value(&op->ops[0], error) >= eval_value(&op->ops[1], error);
335 calculated_number eval_less_than_or_equal(EVAL_NODE *op, int *error) {
336 return eval_value(&op->ops[0], error) <= eval_value(&op->ops[1], error);
338 calculated_number eval_not_equal(EVAL_NODE *op, int *error) {
339 return eval_value(&op->ops[0], error) != eval_value(&op->ops[1], error);
341 calculated_number eval_equal(EVAL_NODE *op, int *error) {
342 return eval_value(&op->ops[0], error) == eval_value(&op->ops[1], error);
344 calculated_number eval_less(EVAL_NODE *op, int *error) {
345 return eval_value(&op->ops[0], error) < eval_value(&op->ops[1], error);
347 calculated_number eval_greater(EVAL_NODE *op, int *error) {
348 return eval_value(&op->ops[0], error) > eval_value(&op->ops[1], error);
350 calculated_number eval_plus(EVAL_NODE *op, int *error) {
351 return eval_value(&op->ops[0], error) + eval_value(&op->ops[1], error);
353 calculated_number eval_minus(EVAL_NODE *op, int *error) {
354 return eval_value(&op->ops[0], error) - eval_value(&op->ops[1], error);
356 calculated_number eval_multiply(EVAL_NODE *op, int *error) {
357 return eval_value(&op->ops[0], error) * eval_value(&op->ops[1], error);
359 calculated_number eval_divide(EVAL_NODE *op, int *error) {
360 return eval_value(&op->ops[0], error) / eval_value(&op->ops[1], error);
362 calculated_number eval_nop(EVAL_NODE *op, int *error) {
363 return eval_value(&op->ops[0], error);
365 calculated_number eval_not(EVAL_NODE *op, int *error) {
366 return !eval_value(&op->ops[0], error);
368 calculated_number eval_sign_plus(EVAL_NODE *op, int *error) {
369 return eval_value(&op->ops[0], error);
371 calculated_number eval_sign_minus(EVAL_NODE *op, int *error) {
372 return -eval_value(&op->ops[0], error);
375 static struct operator {
376 const char *print_as;
379 calculated_number (*eval)(EVAL_NODE *op, int *error);
381 // this is a random access array
382 // we always access it with a known EVAL_OPERATOR_X
384 [EVAL_OPERATOR_AND] = { "&&", 2, 2, eval_and },
385 [EVAL_OPERATOR_OR] = { "||", 2, 2, eval_or },
386 [EVAL_OPERATOR_GREATER_THAN_OR_EQUAL] = { ">=", 3, 2, eval_greater_than_or_equal },
387 [EVAL_OPERATOR_LESS_THAN_OR_EQUAL] = { "<=", 3, 2, eval_less_than_or_equal },
388 [EVAL_OPERATOR_NOT_EQUAL] = { "!=", 3, 2, eval_not_equal },
389 [EVAL_OPERATOR_EQUAL] = { "==", 3, 2, eval_equal },
390 [EVAL_OPERATOR_LESS] = { "<", 3, 2, eval_less },
391 [EVAL_OPERATOR_GREATER] = { ">", 3, 2, eval_greater },
392 [EVAL_OPERATOR_PLUS] = { "+", 4, 2, eval_plus },
393 [EVAL_OPERATOR_MINUS] = { "-", 4, 2, eval_minus },
394 [EVAL_OPERATOR_MULTIPLY] = { "*", 5, 2, eval_multiply },
395 [EVAL_OPERATOR_DIVIDE] = { "/", 5, 2, eval_divide },
396 [EVAL_OPERATOR_NOT] = { "!", 6, 1, eval_not },
397 [EVAL_OPERATOR_SIGN_PLUS] = { "+", 6, 1, eval_sign_plus },
398 [EVAL_OPERATOR_SIGN_MINUS] = { "-", 6, 1, eval_sign_minus },
399 [EVAL_OPERATOR_NOP] = { NULL, 7, 1, eval_nop },
400 [EVAL_OPERATOR_VALUE] = { NULL, 7, 1, eval_nop },
401 [EVAL_OPERATOR_EXPRESSION_OPEN] = { "(", 7, 1, eval_nop },
403 // this should exist in our evaluation list
404 [EVAL_OPERATOR_EXPRESSION_CLOSE] = { ")", 7, 1, eval_nop }
407 #define eval_precedence(operator) (operators[(unsigned char)(operator)].precedence)
409 static inline calculated_number eval_node(EVAL_NODE *op, int *error) {
410 if(unlikely(op->count != operators[op->operator].parameters)) {
411 *error = EVAL_ERROR_INVALID_NUMBER_OF_OPERANDS;
415 calculated_number n = operators[op->operator].eval(op, error);
417 return eval_check_number(n, error);
420 // ----------------------------------------------------------------------------
422 static inline unsigned char parse_operator(const char **string, int *precedence) {
426 for(i = 0 ; operator_parsers[i].parse != NULL ; i++)
427 if(operator_parsers[i].parse(string)) {
428 if(precedence) *precedence = eval_precedence(operator_parsers[i].id);
429 return operator_parsers[i].id;
432 return EVAL_OPERATOR_NOP;
435 static inline EVAL_NODE *eval_node_alloc(int count) {
438 EVAL_NODE *op = calloc(1, sizeof(EVAL_NODE) + (sizeof(EVAL_VALUE) * count));
439 if(!op) fatal("Cannot allocate memory for OPERAND with %d slots", count);
442 op->operator = EVAL_OPERATOR_NOP;
443 op->precedence = eval_precedence(EVAL_OPERATOR_NOP);
448 static inline void eval_node_set_value_to_node(EVAL_NODE *op, int pos, EVAL_NODE *value) {
450 fatal("Invalid request to set position %d of OPERAND that has only %d values", pos + 1, op->count + 1);
452 op->ops[pos].type = EVAL_VALUE_EXPRESSION;
453 op->ops[pos].expression = value;
456 static inline void node_set_value_to_constant(EVAL_NODE *op, int pos, calculated_number value) {
458 fatal("Invalid request to set position %d of OPERAND that has only %d values", pos + 1, op->count + 1);
460 op->ops[pos].type = EVAL_VALUE_NUMBER;
461 op->ops[pos].number = value;
464 static inline void variable_free(VARIABLE *v) {
468 static inline void value_free(EVAL_VALUE *v) {
470 case EVAL_VALUE_EXPRESSION:
471 eval_node_free(v->expression);
474 // case EVAL_VALUE_VARIABLE:
475 // variable_free(v->variable);
483 static inline void eval_node_free(EVAL_NODE *op) {
486 for(i = op->count - 1; i >= 0 ;i--)
487 value_free(&op->ops[i]);
493 static inline EVAL_NODE *parse_next_operand_given_its_operator(const char **string, unsigned char operator_type, int *error) {
494 EVAL_NODE *sub = parse_one_full_operand(string, error);
495 if(!sub) return NULL;
497 EVAL_NODE *op = eval_node_alloc(1);
498 op->operator = operator_type;
499 eval_node_set_value_to_node(op, 0, sub);
503 static inline EVAL_NODE *parse_one_full_operand(const char **string, int *error) {
504 EVAL_NODE *op1 = NULL;
505 calculated_number number;
507 *error = EVAL_ERROR_OK;
511 *error = EVAL_ERROR_MISSING_OPERAND;
515 if(parse_not(string)) {
516 op1 = parse_next_operand_given_its_operator(string, EVAL_OPERATOR_NOT, error);
517 op1->precedence = eval_precedence(EVAL_OPERATOR_NOT);
519 else if(parse_plus(string)) {
520 op1 = parse_next_operand_given_its_operator(string, EVAL_OPERATOR_SIGN_PLUS, error);
521 op1->precedence = eval_precedence(EVAL_OPERATOR_SIGN_PLUS);
523 else if(parse_minus(string)) {
524 op1 = parse_next_operand_given_its_operator(string, EVAL_OPERATOR_SIGN_MINUS, error);
525 op1->precedence = eval_precedence(EVAL_OPERATOR_SIGN_MINUS);
527 else if(parse_open_subexpression(string)) {
528 EVAL_NODE *sub = parse_full_expression(string, error);
530 op1 = eval_node_alloc(1);
531 op1->operator = EVAL_OPERATOR_EXPRESSION_OPEN;
532 op1->precedence = eval_precedence(EVAL_OPERATOR_EXPRESSION_OPEN);
533 eval_node_set_value_to_node(op1, 0, sub);
534 if(!parse_close_subexpression(string)) {
535 *error = EVAL_ERROR_MISSING_CLOSE_SUBEXPRESSION;
541 // else if(parse_variable(string)) {
544 else if(parse_constant(string, &number)) {
545 op1 = eval_node_alloc(1);
546 op1->operator = EVAL_OPERATOR_VALUE;
547 node_set_value_to_constant(op1, 0, number);
550 *error = EVAL_ERROR_UNKNOWN_OPERAND;
552 *error = EVAL_ERROR_MISSING_OPERAND;
557 static inline EVAL_NODE *parse_rest_of_expression(const char **string, int *error, EVAL_NODE *op1) {
558 EVAL_NODE *op2 = NULL;
559 unsigned char operator;
562 operator = parse_operator(string, &precedence);
565 if(operator != EVAL_OPERATOR_NOP) {
566 op2 = parse_one_full_operand(string, error);
568 // error is already reported
573 EVAL_NODE *op = eval_node_alloc(2);
574 op->operator = operator;
575 op->precedence = precedence;
577 eval_node_set_value_to_node(op, 0, op1);
578 eval_node_set_value_to_node(op, 1, op2);
580 if(op->precedence > op1->precedence && op1->count == 2 && op1->operator != '(' && op1->ops[1].type == EVAL_VALUE_EXPRESSION) {
581 eval_node_set_value_to_node(op, 0, op1->ops[1].expression);
582 op1->ops[1].expression = op;
586 return parse_rest_of_expression(string, error, op);
588 else if(**string == EVAL_OPERATOR_EXPRESSION_CLOSE) {
592 if(op1) eval_node_free(op1);
594 *error = EVAL_ERROR_MISSING_OPERATOR;
600 static inline EVAL_NODE *parse_full_expression(const char **string, int *error) {
601 EVAL_NODE *op1 = NULL;
603 op1 = parse_one_full_operand(string, error);
605 *error = EVAL_ERROR_MISSING_OPERAND;
609 return parse_rest_of_expression(string, error, op1);
612 // ----------------------------------------------------------------------------
615 EVAL_NODE *expression_parse(const char *string, const char **failed_at, int *error) {
617 int err = EVAL_ERROR_OK;
618 unsigned long pos = 0;
621 EVAL_NODE *op = parse_full_expression(&s, &err);
623 if (failed_at) *failed_at = s;
624 if (error) *error = err;
627 pos = s - string + 1;
628 error("failed to parse expression '%s': %s at character %lu (i.e.: '%s').", string, expression_strerror(err), pos, s);
634 calculated_number expression_evaluate(EVAL_NODE *expression, int *error) {
635 int err = EVAL_ERROR_OK;
636 calculated_number ret = eval_node(expression, &err);
638 if(err != EVAL_ERROR_OK) {
639 error("Failed to execute expression with error %d (%s)", err, expression_strerror(err));
640 if(error) *error = err;
647 void expression_free(EVAL_NODE *op) {
648 if(op) eval_node_free(op);
651 const char *expression_strerror(int error) {
656 case EVAL_ERROR_MISSING_CLOSE_SUBEXPRESSION:
657 return "missing closing parenthesis";
659 case EVAL_ERROR_UNKNOWN_OPERAND:
660 return "unknown operand";
662 case EVAL_ERROR_MISSING_OPERAND:
663 return "expected operand";
665 case EVAL_ERROR_MISSING_OPERATOR:
666 return "expected operator";
668 case EVAL_ERROR_INVALID_VALUE:
669 return "invalid value structure - internal error";
671 case EVAL_ERROR_INVALID_NUMBER_OF_OPERANDS:
672 return "wrong number of operands for operation - internal error";
674 case EVAL_ERROR_VALUE_IS_NAN:
675 return "value or variable is missing or is not a number";
677 case EVAL_ERROR_VALUE_IS_INFINITE:
678 return "computed value is infinite";
681 return "unknown error";