From 3f52dca264fee6721813bd662811e020b62e6748 Mon Sep 17 00:00:00 2001 From: Costa Tsaousis Date: Thu, 11 Aug 2016 00:14:22 +0300 Subject: [PATCH] operational evaluator for expressions --- profile/test-eval.c | 152 ++++++++++++++++++++++++++++----- src/eval.c | 199 +++++++++++++++++++++++++++++++------------- src/eval.h | 11 ++- 3 files changed, 279 insertions(+), 83 deletions(-) diff --git a/profile/test-eval.c b/profile/test-eval.c index 509eab56..f471234a 100644 --- a/profile/test-eval.c +++ b/profile/test-eval.c @@ -56,82 +56,181 @@ void print_operand(EVAL_OPERAND *op, int level) { while(i--) print_value(&op->ops[i], level + 1); } -calculated_number evaluate(EVAL_OPERAND *op); +calculated_number evaluate(EVAL_OPERAND *op, int depth); -calculated_number evaluate_value(EVAL_VALUE *v) { +calculated_number evaluate_value(EVAL_VALUE *v, int depth) { switch(v->type) { case EVAL_VALUE_NUMBER: return v->number; case EVAL_VALUE_EXPRESSION: - return evaluate(v->expression); + return evaluate(v->expression, depth); default: fatal("I don't know how to handle EVAL_VALUE type %d", v->type); } } -calculated_number evaluate(EVAL_OPERAND *op) { +void print_depth(int depth) { + static int count = 0; + + printf("%d. ", ++count); + while(depth--) printf(" "); +} + +calculated_number evaluate(EVAL_OPERAND *op, int depth) { calculated_number n1, n2, r; switch(op->operator) { case EVAL_OPERATOR_SIGN_PLUS: - r = evaluate_value(&op->ops[0]); + r = evaluate_value(&op->ops[0], depth); break; case EVAL_OPERATOR_SIGN_MINUS: - r = -evaluate_value(&op->ops[0]); + r = -evaluate_value(&op->ops[0], depth); break; case EVAL_OPERATOR_PLUS: if(op->count != 2) fatal("Operator '%c' requires 2 values, but we have %d", op->operator, op->count); - n1 = evaluate_value(&op->ops[0]); - n2 = evaluate_value(&op->ops[1]); + n1 = evaluate_value(&op->ops[0], depth); + n2 = evaluate_value(&op->ops[1], depth); r = n1 + n2; - printf("%Lf = %Lf %c %Lf\n", r, n1, op->operator, n2); + print_depth(depth); + printf("%Lf = %Lf + %Lf\n", r, n1, n2); break; case EVAL_OPERATOR_MINUS: if(op->count != 2) fatal("Operator '%c' requires 2 values, but we have %d", op->operator, op->count); - n1 = evaluate_value(&op->ops[0]); - n2 = evaluate_value(&op->ops[1]); + n1 = evaluate_value(&op->ops[0], depth); + n2 = evaluate_value(&op->ops[1], depth); r = n1 - n2; - printf("%Lf = %Lf %c %Lf\n", r, n1, op->operator, n2); + print_depth(depth); + printf("%Lf = %Lf - %Lf\n", r, n1, n2); break; case EVAL_OPERATOR_MULTIPLY: if(op->count != 2) fatal("Operator '%c' requires 2 values, but we have %d", op->operator, op->count); - n1 = evaluate_value(&op->ops[0]); - n2 = evaluate_value(&op->ops[1]); + n1 = evaluate_value(&op->ops[0], depth); + n2 = evaluate_value(&op->ops[1], depth); r = n1 * n2; - printf("%Lf = %Lf %c %Lf\n", r, n1, op->operator, n2); + print_depth(depth); + printf("%Lf = %Lf * %Lf\n", r, n1, n2); break; case EVAL_OPERATOR_DIVIDE: if(op->count != 2) fatal("Operator '%c' requires 2 values, but we have %d", op->operator, op->count); - n1 = evaluate_value(&op->ops[0]); - n2 = evaluate_value(&op->ops[1]); + n1 = evaluate_value(&op->ops[0], depth); + n2 = evaluate_value(&op->ops[1], depth); r = n1 / n2; - printf("%Lf = %Lf %c %Lf\n", r, n1, op->operator, n2); + print_depth(depth); + printf("%Lf = %Lf / %Lf\n", r, n1, n2); + break; + + case EVAL_OPERATOR_NOT: + n1 = evaluate_value(&op->ops[0], depth); + r = !n1; + print_depth(depth); + printf("%Lf = NOT %Lf\n", r, n1); + break; + + case EVAL_OPERATOR_AND: + if(op->count != 2) + fatal("Operator '%c' requires 2 values, but we have %d", op->operator, op->count); + n1 = evaluate_value(&op->ops[0], depth); + n2 = evaluate_value(&op->ops[1], depth); + r = n1 && n2; + print_depth(depth); + printf("%Lf = %Lf AND %Lf\n", r, n1, n2); + break; + + case EVAL_OPERATOR_OR: + if(op->count != 2) + fatal("Operator '%c' requires 2 values, but we have %d", op->operator, op->count); + n1 = evaluate_value(&op->ops[0], depth); + n2 = evaluate_value(&op->ops[1], depth); + r = n1 || n2; + print_depth(depth); + printf("%Lf = %Lf OR %Lf\n", r, n1, n2); + break; + + case EVAL_OPERATOR_GREATER_THAN_OR_EQUAL: + if(op->count != 2) + fatal("Operator '%c' requires 2 values, but we have %d", op->operator, op->count); + n1 = evaluate_value(&op->ops[0], depth); + n2 = evaluate_value(&op->ops[1], depth); + r = n1 >= n2; + print_depth(depth); + printf("%Lf = %Lf >= %Lf\n", r, n1, n2); + break; + + case EVAL_OPERATOR_LESS_THAN_OR_EQUAL: + if(op->count != 2) + fatal("Operator '%c' requires 2 values, but we have %d", op->operator, op->count); + n1 = evaluate_value(&op->ops[0], depth); + n2 = evaluate_value(&op->ops[1], depth); + r = n1 <= n2; + print_depth(depth); + printf("%Lf = %Lf <= %Lf\n", r, n1, n2); + break; + + case EVAL_OPERATOR_GREATER: + if(op->count != 2) + fatal("Operator '%c' requires 2 values, but we have %d", op->operator, op->count); + n1 = evaluate_value(&op->ops[0], depth); + n2 = evaluate_value(&op->ops[1], depth); + r = n1 > n2; + print_depth(depth); + printf("%Lf = %Lf > %Lf\n", r, n1, n2); + break; + + case EVAL_OPERATOR_LESS: + if(op->count != 2) + fatal("Operator '%c' requires 2 values, but we have %d", op->operator, op->count); + n1 = evaluate_value(&op->ops[0], depth); + n2 = evaluate_value(&op->ops[1], depth); + r = n1 < n2; + print_depth(depth); + printf("%Lf = %Lf < %Lf\n", r, n1, n2); + break; + + case EVAL_OPERATOR_NOT_EQUAL: + if(op->count != 2) + fatal("Operator '%c' requires 2 values, but we have %d", op->operator, op->count); + n1 = evaluate_value(&op->ops[0], depth); + n2 = evaluate_value(&op->ops[1], depth); + r = n1 != n2; + print_depth(depth); + printf("%Lf = %Lf <> %Lf\n", r, n1, n2); + break; + + case EVAL_OPERATOR_EQUAL: + if(op->count != 2) + fatal("Operator '%c' requires 2 values, but we have %d", op->operator, op->count); + n1 = evaluate_value(&op->ops[0], depth); + n2 = evaluate_value(&op->ops[1], depth); + r = n1 == n2; + print_depth(depth); + printf("%Lf = %Lf == %Lf\n", r, n1, n2); break; case EVAL_OPERATOR_EXPRESSION_OPEN: printf("BEGIN SUB-EXPRESSION\n"); - r = evaluate_value(&op->ops[0]); + r = evaluate_value(&op->ops[0], depth + 1); printf("END SUB-EXPRESSION\n"); break; case EVAL_OPERATOR_NOP: case EVAL_OPERATOR_VALUE: - r = evaluate_value(&op->ops[0]); + r = evaluate_value(&op->ops[0], depth); break; default: - fatal("I don't know how to handle operator '%c'", op->operator); + error("I don't know how to handle operator '%c'", op->operator); + r = 0; break; } @@ -140,9 +239,16 @@ calculated_number evaluate(EVAL_OPERAND *op) { void print_expression(EVAL_OPERAND *op, const char *failed_at, int error) { if(op) { - printf("\n"); + printf("expression tree:\n"); print_operand(op, 0); - evaluate(op); + + printf("\nevaluation steps:\n"); + evaluate(op, 0); + + int error; + calculated_number ret = evaluate_expression(op, &error); + printf("\ninternal evaluator:\nSTATUS: %d, RESULT = %Lf\n", error, ret); + free_expression(op); } else { diff --git a/src/eval.c b/src/eval.c index 5ed62b21..ff121b5c 100644 --- a/src/eval.c +++ b/src/eval.c @@ -1,5 +1,12 @@ #include "common.h" +// forward definitions +static inline void operand_free(EVAL_OPERAND *op); +static inline EVAL_OPERAND *parse_operand(const char **string, int *error); +static inline EVAL_OPERAND *parse_operand1(const char **string, int *error); +static inline calculated_number eval_operand(EVAL_OPERAND *op, int *error); + + static inline void skip_spaces(const char **string) { const char *s = *string; while(isspace(*s)) s++; @@ -212,8 +219,12 @@ static inline int parse_close_subexpression(const char **string) { static inline int parse_literal(const char **string, calculated_number *number) { char *end = NULL; - *number = strtold(*string, &end); - if(!end || *string == end) return 0; + calculated_number n = strtold(*string, &end); + if(unlikely(!end || *string == end || isnan(n) || isinf(n))) { + *number = 0; + return 0; + } + *number = n; *string = end; return 1; @@ -276,88 +287,138 @@ static struct operator_parser { // ---------------------------------------------------------------------------- // evaluation of operations -calculated_number eval_and(EVAL_OPERAND *op) { - return 0; +static inline calculated_number eval_check_number(calculated_number n, int *error) { + if(unlikely(isnan(n))) { + *error = EVAL_ERROR_VALUE_IS_NAN; + return 0; + } + + if(unlikely(isinf(n))) { + *error = EVAL_ERROR_VALUE_IS_INFINITE; + return 0; + } + + return n; } -calculated_number eval_or(EVAL_OPERAND *op) { - return 0; + +static inline calculated_number eval_value(EVAL_VALUE *v, int *error) { + calculated_number n; + + switch(v->type) { + case EVAL_VALUE_EXPRESSION: + n = eval_operand(v->expression, error); + break; + + case EVAL_VALUE_NUMBER: + n = v->number; + break; + +// case EVAL_VALUE_VARIABLE: +// break; + + default: + *error = EVAL_ERROR_INVALID_VALUE; + n = 0; + break; + } + + return eval_check_number(n, error); } -calculated_number eval_greater_than_or_equal(EVAL_OPERAND *op) { - return 0; + +calculated_number eval_and(EVAL_OPERAND *op, int *error) { + return eval_value(&op->ops[0], error) && eval_value(&op->ops[1], error); } -calculated_number eval_less_than_or_equal(EVAL_OPERAND *op) { - return 0; +calculated_number eval_or(EVAL_OPERAND *op, int *error) { + return eval_value(&op->ops[0], error) || eval_value(&op->ops[1], error); } -calculated_number eval_not_equal(EVAL_OPERAND *op) { - return 0; +calculated_number eval_greater_than_or_equal(EVAL_OPERAND *op, int *error) { + return eval_value(&op->ops[0], error) >= eval_value(&op->ops[1], error); } -calculated_number eval_equal(EVAL_OPERAND *op) { - return 0; +calculated_number eval_less_than_or_equal(EVAL_OPERAND *op, int *error) { + return eval_value(&op->ops[0], error) <= eval_value(&op->ops[1], error); } -calculated_number eval_less(EVAL_OPERAND *op) { - return 0; +calculated_number eval_not_equal(EVAL_OPERAND *op, int *error) { + return eval_value(&op->ops[0], error) != eval_value(&op->ops[1], error); } -calculated_number eval_greater(EVAL_OPERAND *op) { - return 0; +calculated_number eval_equal(EVAL_OPERAND *op, int *error) { + return eval_value(&op->ops[0], error) == eval_value(&op->ops[1], error); } -calculated_number eval_plus(EVAL_OPERAND *op) { - return 0; +calculated_number eval_less(EVAL_OPERAND *op, int *error) { + return eval_value(&op->ops[0], error) < eval_value(&op->ops[1], error); } -calculated_number eval_minus(EVAL_OPERAND *op) { - return 0; +calculated_number eval_greater(EVAL_OPERAND *op, int *error) { + return eval_value(&op->ops[0], error) > eval_value(&op->ops[1], error); } -calculated_number eval_multiply(EVAL_OPERAND *op) { - return 0; +calculated_number eval_plus(EVAL_OPERAND *op, int *error) { + return eval_value(&op->ops[0], error) + eval_value(&op->ops[1], error); } -calculated_number eval_divide(EVAL_OPERAND *op) { - return 0; +calculated_number eval_minus(EVAL_OPERAND *op, int *error) { + return eval_value(&op->ops[0], error) - eval_value(&op->ops[1], error); } -calculated_number eval_nop(EVAL_OPERAND *op) { - return 0; +calculated_number eval_multiply(EVAL_OPERAND *op, int *error) { + return eval_value(&op->ops[0], error) * eval_value(&op->ops[1], error); } -calculated_number eval_not(EVAL_OPERAND *op) { - return 0; +calculated_number eval_divide(EVAL_OPERAND *op, int *error) { + return eval_value(&op->ops[0], error) / eval_value(&op->ops[1], error); } -calculated_number eval_sign_plus(EVAL_OPERAND *op) { - return 0; +calculated_number eval_nop(EVAL_OPERAND *op, int *error) { + return eval_value(&op->ops[0], error); } -calculated_number eval_sign_minus(EVAL_OPERAND *op) { - return 0; +calculated_number eval_not(EVAL_OPERAND *op, int *error) { + return !eval_value(&op->ops[0], error); +} +calculated_number eval_sign_plus(EVAL_OPERAND *op, int *error) { + return eval_value(&op->ops[0], error); +} +calculated_number eval_sign_minus(EVAL_OPERAND *op, int *error) { + return -eval_value(&op->ops[0], error); } static struct operator { const char *print_as; char precedence; - calculated_number (*eval)(EVAL_OPERAND *op); + char parameters; + calculated_number (*eval)(EVAL_OPERAND *op, int *error); } operators[256] = { // this is a random access array // we always access it with a known EVAL_OPERATOR_X - [EVAL_OPERATOR_AND] = { "&&", 2, eval_and }, - [EVAL_OPERATOR_OR] = { "||", 2, eval_or }, - [EVAL_OPERATOR_GREATER_THAN_OR_EQUAL] = { ">=", 3, eval_greater_than_or_equal }, - [EVAL_OPERATOR_LESS_THAN_OR_EQUAL] = { "<=", 3, eval_less_than_or_equal }, - [EVAL_OPERATOR_NOT_EQUAL] = { "!=", 3, eval_not_equal }, - [EVAL_OPERATOR_EQUAL] = { "==", 3, eval_equal }, - [EVAL_OPERATOR_LESS] = { "<", 3, eval_less }, - [EVAL_OPERATOR_GREATER] = { ">", 3, eval_greater }, - [EVAL_OPERATOR_PLUS] = { "+", 4, eval_plus }, - [EVAL_OPERATOR_MINUS] = { "-", 4, eval_minus }, - [EVAL_OPERATOR_MULTIPLY] = { "*", 5, eval_multiply }, - [EVAL_OPERATOR_DIVIDE] = { "/", 5, eval_divide }, - [EVAL_OPERATOR_NOT] = { "!", 6, eval_not }, - [EVAL_OPERATOR_SIGN_PLUS] = { "+", 6, eval_sign_plus }, - [EVAL_OPERATOR_SIGN_MINUS] = { "-", 6, eval_sign_minus }, - [EVAL_OPERATOR_NOP] = { NULL, 7, eval_nop }, - [EVAL_OPERATOR_VALUE] = { NULL, 7, eval_nop }, - [EVAL_OPERATOR_EXPRESSION_OPEN] = { "(", 7, eval_nop }, + [EVAL_OPERATOR_AND] = { "&&", 2, 2, eval_and }, + [EVAL_OPERATOR_OR] = { "||", 2, 2, eval_or }, + [EVAL_OPERATOR_GREATER_THAN_OR_EQUAL] = { ">=", 3, 2, eval_greater_than_or_equal }, + [EVAL_OPERATOR_LESS_THAN_OR_EQUAL] = { "<=", 3, 2, eval_less_than_or_equal }, + [EVAL_OPERATOR_NOT_EQUAL] = { "!=", 3, 2, eval_not_equal }, + [EVAL_OPERATOR_EQUAL] = { "==", 3, 2, eval_equal }, + [EVAL_OPERATOR_LESS] = { "<", 3, 2, eval_less }, + [EVAL_OPERATOR_GREATER] = { ">", 3, 2, eval_greater }, + [EVAL_OPERATOR_PLUS] = { "+", 4, 2, eval_plus }, + [EVAL_OPERATOR_MINUS] = { "-", 4, 2, eval_minus }, + [EVAL_OPERATOR_MULTIPLY] = { "*", 5, 2, eval_multiply }, + [EVAL_OPERATOR_DIVIDE] = { "/", 5, 2, eval_divide }, + [EVAL_OPERATOR_NOT] = { "!", 6, 1, eval_not }, + [EVAL_OPERATOR_SIGN_PLUS] = { "+", 6, 1, eval_sign_plus }, + [EVAL_OPERATOR_SIGN_MINUS] = { "-", 6, 1, eval_sign_minus }, + [EVAL_OPERATOR_NOP] = { NULL, 7, 1, eval_nop }, + [EVAL_OPERATOR_VALUE] = { NULL, 7, 1, eval_nop }, + [EVAL_OPERATOR_EXPRESSION_OPEN] = { "(", 7, 1, eval_nop }, // this should exist in our evaluation list - [EVAL_OPERATOR_EXPRESSION_CLOSE] = { ")", 7, eval_nop } + [EVAL_OPERATOR_EXPRESSION_CLOSE] = { ")", 7, 1, eval_nop } }; #define eval_precedence(operator) (operators[(unsigned char)(operator)].precedence) +static inline calculated_number eval_operand(EVAL_OPERAND *op, int *error) { + if(unlikely(op->count != operators[op->operator].parameters)) { + *error = EVAL_ERROR_INVALID_NUMBER_OF_OPERANDS; + return 0; + } + + calculated_number n = operators[op->operator].eval(op, error); + + return eval_check_number(n, error); +} + // ---------------------------------------------------------------------------- static inline char parse_operator(const char **string, int *precedence) { @@ -403,11 +464,6 @@ static inline void operand_set_value_literal(EVAL_OPERAND *op, int pos, calculat op->ops[pos].number = value; } -// forward definitions -static inline void operand_free(EVAL_OPERAND *op); -static inline EVAL_OPERAND *parse_operand(const char **string, int *error); -static inline EVAL_OPERAND *parse_operand1(const char **string, int *error); - static inline void variable_free(VARIABLE *v) { free(v); } @@ -572,6 +628,18 @@ const char *eval_error(int error) { case EVAL_ERROR_MISSING_OPERATOR: return "expected operator"; + case EVAL_ERROR_INVALID_VALUE: + return "invalid value structure - internal error"; + + case EVAL_ERROR_INVALID_NUMBER_OF_OPERANDS: + return "wrong number of operands for operation - internal error"; + + case EVAL_ERROR_VALUE_IS_NAN: + return "value or variable is missing or is not a number"; + + case EVAL_ERROR_VALUE_IS_INFINITE: + return "computed value is infinite"; + default: return "unknown error"; } @@ -596,6 +664,19 @@ EVAL_OPERAND *parse_expression(const char *string, const char **failed_at, int * return op; } +calculated_number evaluate_expression(EVAL_OPERAND *expression, int *error) { + int err = EVAL_ERROR_OK; + calculated_number ret = eval_operand(expression, &err); + + if(err != EVAL_ERROR_OK) { + error("Failed to execute expression with error %d (%s)", err, eval_error(err)); + if(error) *error = err; + return 0; + } + + return ret; +} + void free_expression(EVAL_OPERAND *op) { if(op) operand_free(op); } diff --git a/src/eval.h b/src/eval.h index ed040f60..157abc63 100644 --- a/src/eval.h +++ b/src/eval.h @@ -34,11 +34,19 @@ typedef struct variable { #define EVAL_OPERATOR_SIGN_MINUS 'M' #define EVAL_ERROR_OK 0 + +// parsing errors #define EVAL_ERROR_MISSING_CLOSE_SUBEXPRESSION 1 #define EVAL_ERROR_UNKNOWN_OPERAND 2 #define EVAL_ERROR_MISSING_OPERAND 3 #define EVAL_ERROR_MISSING_OPERATOR 4 +// evaluation errors +#define EVAL_ERROR_INVALID_VALUE 5 +#define EVAL_ERROR_INVALID_NUMBER_OF_OPERANDS 6 +#define EVAL_ERROR_VALUE_IS_NAN 7 +#define EVAL_ERROR_VALUE_IS_INFINITE 8 + typedef struct eval_value { int type; @@ -51,7 +59,7 @@ typedef struct eval_value { typedef struct eval_operand { int id; - char operator; + unsigned char operator; int precedence; int count; @@ -59,6 +67,7 @@ typedef struct eval_operand { } EVAL_OPERAND; extern EVAL_OPERAND *parse_expression(const char *string, const char **failed_at, int *error); +extern calculated_number evaluate_expression(EVAL_OPERAND *expression, int *error); extern void free_expression(EVAL_OPERAND *op); #endif //NETDATA_EVAL_H -- 2.39.2