From ac6925def2988f29fd21c8226e4b435bc0f34b62 Mon Sep 17 00:00:00 2001 From: Costa Tsaousis Date: Thu, 11 Aug 2016 14:28:17 +0300 Subject: [PATCH] expression parser now re-generates the expression showing the precedence it applied to it; more code cleanups --- profile/test-eval.c | 27 ++- src/eval.c | 562 +++++++++++++++++++++++++++++--------------- src/eval.h | 76 +++--- src/health.c | 2 +- src/rrd.h | 2 +- src/web_buffer.h | 2 +- src/web_client.c | 4 +- 7 files changed, 435 insertions(+), 240 deletions(-) diff --git a/profile/test-eval.c b/profile/test-eval.c index 33fd7635..76b4336f 100644 --- a/profile/test-eval.c +++ b/profile/test-eval.c @@ -3,7 +3,7 @@ * 1. build netdata (as normally) * 2. cd profile/ * 3. compile with: - * gcc -O1 -ggdb -Wall -Wextra -I ../src/ -I ../ -o test-eval test-eval.c ../src/log.o ../src/eval.o ../src/common.o -pthread + * gcc -O1 -ggdb -Wall -Wextra -I ../src/ -I ../ -o test-eval test-eval.c ../src/log.o ../src/eval.o ../src/common.o ../src/web_buffer.o ../src/storage_number.o -pthread -lm * */ @@ -11,6 +11,7 @@ void netdata_cleanup_and_exit(int ret) { exit(ret); } +/* void indent(int level, int show) { int i = level; while(i--) printf(" | "); @@ -237,6 +238,7 @@ calculated_number evaluate(EVAL_NODE *op, int depth) { return r; } + void print_expression(EVAL_NODE *op, const char *failed_at, int error) { if(op) { printf("expression tree:\n"); @@ -255,17 +257,32 @@ void print_expression(EVAL_NODE *op, const char *failed_at, int error) { printf("error: %d, failed_at: '%s'\n", error, (failed_at)?failed_at:""); } } - +*/ int main(int argc, char **argv) { if(argc != 2) { - fprintf(stderr, "I need an epxression\n"); + fprintf(stderr, "I need an epxression (enclose it in single-quotes (') as a single parameter)\n"); exit(1); } const char *failed_at = NULL; int error; - EVAL_NODE *op = expression_parse(argv[1], &failed_at, &error); - print_expression(op, failed_at, error); + + EVAL_EXPRESSION *exp = expression_parse(argv[1], &failed_at, &error); + if(!exp) + printf("\nFAILED\nExpression: '%s'\nParsing stopped at: '%s'\nError code: %d (%s)\n", argv[1], (failed_at)?failed_at:"", error, expression_strerror(error)); + + else { + printf("\nOK\nExpression: '%s'\nParsed as : '%s'\nError code: %d (%s)\n", argv[1], exp->parsed_as, error, expression_strerror(error)); + + if(expression_evaluate(exp)) { + printf("\nEvaluates to: %Lf\n\n", exp->result); + } + else { + printf("\nEvaluation failed with code %d and message: %s\n\n", exp->error, buffer_tostring(exp->error_msg)); + } + expression_free(exp); + } + return 0; } diff --git a/src/eval.c b/src/eval.c index 93d768cf..a0f18e00 100644 --- a/src/eval.c +++ b/src/eval.c @@ -1,30 +1,310 @@ #include "common.h" -// forward definitions +// ---------------------------------------------------------------------------- +// data structures for storing the parsed expression in memory + +typedef struct eval_value { + int type; + + union { + calculated_number number; + EVAL_VARIABLE *variable; + struct eval_node *expression; + }; +} EVAL_VALUE; + +typedef struct eval_node { + int id; + unsigned char operator; + int precedence; + + int count; + EVAL_VALUE ops[]; +} EVAL_NODE; + +// these are used for EVAL_NODE.operator +// they are used as internal IDs to identify an operator +// THEY ARE NOT USED FOR PARSING OPERATORS LIKE THAT +#define EVAL_OPERATOR_NOP '\0' +#define EVAL_OPERATOR_VALUE ':' +#define EVAL_OPERATOR_EXPRESSION_OPEN '(' +#define EVAL_OPERATOR_EXPRESSION_CLOSE ')' +#define EVAL_OPERATOR_NOT '!' +#define EVAL_OPERATOR_PLUS '+' +#define EVAL_OPERATOR_MINUS '-' +#define EVAL_OPERATOR_AND '&' +#define EVAL_OPERATOR_OR '|' +#define EVAL_OPERATOR_GREATER_THAN_OR_EQUAL 'G' +#define EVAL_OPERATOR_LESS_THAN_OR_EQUAL 'L' +#define EVAL_OPERATOR_NOT_EQUAL '~' +#define EVAL_OPERATOR_EQUAL '=' +#define EVAL_OPERATOR_LESS '<' +#define EVAL_OPERATOR_GREATER '>' +#define EVAL_OPERATOR_MULTIPLY '*' +#define EVAL_OPERATOR_DIVIDE '/' +#define EVAL_OPERATOR_SIGN_PLUS 'P' +#define EVAL_OPERATOR_SIGN_MINUS 'M' + +// ---------------------------------------------------------------------------- +// forward function definitions + static inline void eval_node_free(EVAL_NODE *op); static inline EVAL_NODE *parse_full_expression(const char **string, int *error); static inline EVAL_NODE *parse_one_full_operand(const char **string, int *error); -static inline calculated_number eval_node(EVAL_NODE *op, int *error); +static inline calculated_number eval_node(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error); +static inline void print_parsed_as_node(BUFFER *out, EVAL_NODE *op, int *error); + +// ---------------------------------------------------------------------------- +// evaluation of expressions + +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; +} + +static inline calculated_number eval_variable(EVAL_EXPRESSION *exp, EVAL_VARIABLE *v, int *error) { + // FIXME: do the variable look up here + +// if(!exp->data) { + *error = EVAL_ERROR_UNKNOWN_VARIABLE; + buffer_sprintf(exp->error_msg, "unknown variable '%s'", v->name); +// } + + return 0; +} + +static inline calculated_number eval_value(EVAL_EXPRESSION *exp, EVAL_VALUE *v, int *error) { + calculated_number n; + + switch(v->type) { + case EVAL_VALUE_EXPRESSION: + n = eval_node(exp, v->expression, error); + break; + case EVAL_VALUE_NUMBER: + n = v->number; + break; + + case EVAL_VALUE_VARIABLE: + n = eval_variable(exp, v->variable, error); + break; + + default: + *error = EVAL_ERROR_INVALID_VALUE; + n = 0; + break; + } + + return eval_check_number(n, error); +} + +calculated_number eval_and(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error) { + return eval_value(exp, &op->ops[0], error) && eval_value(exp, &op->ops[1], error); +} +calculated_number eval_or(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error) { + return eval_value(exp, &op->ops[0], error) || eval_value(exp, &op->ops[1], error); +} +calculated_number eval_greater_than_or_equal(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error) { + return eval_value(exp, &op->ops[0], error) >= eval_value(exp, &op->ops[1], error); +} +calculated_number eval_less_than_or_equal(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error) { + return eval_value(exp, &op->ops[0], error) <= eval_value(exp, &op->ops[1], error); +} +calculated_number eval_not_equal(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error) { + return eval_value(exp, &op->ops[0], error) != eval_value(exp, &op->ops[1], error); +} +calculated_number eval_equal(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error) { + return eval_value(exp, &op->ops[0], error) == eval_value(exp, &op->ops[1], error); +} +calculated_number eval_less(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error) { + return eval_value(exp, &op->ops[0], error) < eval_value(exp, &op->ops[1], error); +} +calculated_number eval_greater(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error) { + return eval_value(exp, &op->ops[0], error) > eval_value(exp, &op->ops[1], error); +} +calculated_number eval_plus(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error) { + return eval_value(exp, &op->ops[0], error) + eval_value(exp, &op->ops[1], error); +} +calculated_number eval_minus(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error) { + return eval_value(exp, &op->ops[0], error) - eval_value(exp, &op->ops[1], error); +} +calculated_number eval_multiply(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error) { + return eval_value(exp, &op->ops[0], error) * eval_value(exp, &op->ops[1], error); +} +calculated_number eval_divide(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error) { + return eval_value(exp, &op->ops[0], error) / eval_value(exp, &op->ops[1], error); +} +calculated_number eval_nop(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error) { + return eval_value(exp, &op->ops[0], error); +} +calculated_number eval_not(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error) { + return !eval_value(exp, &op->ops[0], error); +} +calculated_number eval_sign_plus(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error) { + return eval_value(exp, &op->ops[0], error); +} +calculated_number eval_sign_minus(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error) { + return -eval_value(exp, &op->ops[0], error); +} + +static struct operator { + const char *print_as; + char precedence; + char parameters; + calculated_number (*eval)(EVAL_EXPRESSION *exp, EVAL_NODE *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, 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] = { NULL, 7, 1, eval_nop }, + + // this should exist in our evaluation list + [EVAL_OPERATOR_EXPRESSION_CLOSE] = { NULL, 7, 1, eval_nop } +}; + +#define eval_precedence(operator) (operators[(unsigned char)(operator)].precedence) + +static inline calculated_number eval_node(EVAL_EXPRESSION *exp, EVAL_NODE *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(exp, op, error); + + return eval_check_number(n, error); +} + +// ---------------------------------------------------------------------------- +// parsed-as generation + +static inline void print_parsed_as_variable(BUFFER *out, EVAL_VARIABLE *v, int *error) { + (void)error; + buffer_sprintf(out, "$%s", v->name); +} + +static inline void print_parsed_as_constant(BUFFER *out, calculated_number n) { + char b[100+1], *s; + snprintfz(b, 100, CALCULATED_NUMBER_FORMAT, n); + + s = &b[strlen(b) - 1]; + while(s > b && *s == '0') { + *s ='\0'; + s--; + } + + if(s > b && *s == '.') + *s = '\0'; + + buffer_strcat(out, b); +} + +static inline void print_parsed_as_value(BUFFER *out, EVAL_VALUE *v, int *error) { + switch(v->type) { + case EVAL_VALUE_EXPRESSION: + print_parsed_as_node(out, v->expression, error); + break; + + case EVAL_VALUE_NUMBER: + print_parsed_as_constant(out, v->number); + break; + + case EVAL_VALUE_VARIABLE: + print_parsed_as_variable(out, v->variable, error); + break; + + default: + *error = EVAL_ERROR_INVALID_VALUE; + break; + } +} + +static inline void print_parsed_as_node(BUFFER *out, EVAL_NODE *op, int *error) { + if(unlikely(op->count != operators[op->operator].parameters)) { + *error = EVAL_ERROR_INVALID_NUMBER_OF_OPERANDS; + return; + } + + if(operators[op->operator].parameters == 1) { + + if(operators[op->operator].print_as) + buffer_sprintf(out, "%s", operators[op->operator].print_as); + + //if(op->operator == EVAL_OPERATOR_EXPRESSION_OPEN) + // buffer_strcat(out, "("); + + print_parsed_as_value(out, &op->ops[0], error); + + //if(op->operator == EVAL_OPERATOR_EXPRESSION_OPEN) + // buffer_strcat(out, ")"); + } + + else if(operators[op->operator].parameters == 2) { + buffer_strcat(out, "("); + print_parsed_as_value(out, &op->ops[0], error); + + if(operators[op->operator].print_as) + buffer_sprintf(out, " %s ", operators[op->operator].print_as); + + print_parsed_as_value(out, &op->ops[1], error); + buffer_strcat(out, ")"); + } +} + +// ---------------------------------------------------------------------------- +// parsing expressions + +// skip spaces static inline void skip_spaces(const char **string) { const char *s = *string; while(isspace(*s)) s++; *string = s; } -// ---------------------------------------------------------------------------- -// operators that work on 2 operands - +// what character can appear just after an operator keyword +// like NOT AND OR ? static inline int isoperatorterm_word(const char s) { - if(isspace(s) || s == '(' || s == '$' || s == '!' || s == '-' || s == '+' || isdigit(s)) return 1; + if(isspace(s) || s == '(' || s == '$' || s == '!' || s == '-' || s == '+' || isdigit(s) || !s) + return 1; + return 0; } +// what character can appear just after an operator symbol? static inline int isoperatorterm_symbol(const char s) { if(isoperatorterm_word(s) || isalpha(s)) return 1; return 0; } +// ---------------------------------------------------------------------------- +// parse operators + static inline int parse_and(const char **string) { const char *s = *string; @@ -144,6 +424,23 @@ static inline int parse_not_equal(const char **string) { return 0; } +static inline int parse_not(const char **string) { + const char *s = *string; + + // NOT + if((s[0] == 'N' || s[0] == 'n') && (s[1] == 'O' || s[1] == 'o') && (s[2] == 'T' || s[2] == 't') && isoperatorterm_word(s[3])) { + *string = &s[3]; + return 1; + } + + if(s[0] == '!') { + *string = &s[1]; + return 1; + } + + return 0; +} + static inline int parse_multiply(const char **string) { const char *s = *string; @@ -228,26 +525,6 @@ static inline int parse_constant(const char **string, calculated_number *number) return 1; } -// ---------------------------------------------------------------------------- -// operators that affect a single operand - -static inline int parse_not(const char **string) { - const char *s = *string; - - // NOT - if((s[0] == 'N' || s[0] == 'n') && (s[1] == 'O' || s[1] == 'o') && (s[2] == 'T' || s[2] == 't') && isoperatorterm_word(s[3])) { - *string = &s[3]; - return 1; - } - - if(s[0] == EVAL_OPERATOR_NOT) { - *string = &s[1]; - return 1; - } - - return 0; -} - static struct operator_parser { unsigned char id; int (*parse)(const char **); @@ -279,146 +556,10 @@ static struct operator_parser { * these are handled in code */ + // termination { EVAL_OPERATOR_NOP, NULL } }; -// ---------------------------------------------------------------------------- -// evaluation of operations - -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; -} - -static inline calculated_number eval_value(EVAL_VALUE *v, int *error) { - calculated_number n; - - switch(v->type) { - case EVAL_VALUE_EXPRESSION: - n = eval_node(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_and(EVAL_NODE *op, int *error) { - return eval_value(&op->ops[0], error) && eval_value(&op->ops[1], error); -} -calculated_number eval_or(EVAL_NODE *op, int *error) { - return eval_value(&op->ops[0], error) || eval_value(&op->ops[1], error); -} -calculated_number eval_greater_than_or_equal(EVAL_NODE *op, int *error) { - return eval_value(&op->ops[0], error) >= eval_value(&op->ops[1], error); -} -calculated_number eval_less_than_or_equal(EVAL_NODE *op, int *error) { - return eval_value(&op->ops[0], error) <= eval_value(&op->ops[1], error); -} -calculated_number eval_not_equal(EVAL_NODE *op, int *error) { - return eval_value(&op->ops[0], error) != eval_value(&op->ops[1], error); -} -calculated_number eval_equal(EVAL_NODE *op, int *error) { - return eval_value(&op->ops[0], error) == eval_value(&op->ops[1], error); -} -calculated_number eval_less(EVAL_NODE *op, int *error) { - return eval_value(&op->ops[0], error) < eval_value(&op->ops[1], error); -} -calculated_number eval_greater(EVAL_NODE *op, int *error) { - return eval_value(&op->ops[0], error) > eval_value(&op->ops[1], error); -} -calculated_number eval_plus(EVAL_NODE *op, int *error) { - return eval_value(&op->ops[0], error) + eval_value(&op->ops[1], error); -} -calculated_number eval_minus(EVAL_NODE *op, int *error) { - return eval_value(&op->ops[0], error) - eval_value(&op->ops[1], error); -} -calculated_number eval_multiply(EVAL_NODE *op, int *error) { - return eval_value(&op->ops[0], error) * eval_value(&op->ops[1], error); -} -calculated_number eval_divide(EVAL_NODE *op, int *error) { - return eval_value(&op->ops[0], error) / eval_value(&op->ops[1], error); -} -calculated_number eval_nop(EVAL_NODE *op, int *error) { - return eval_value(&op->ops[0], error); -} -calculated_number eval_not(EVAL_NODE *op, int *error) { - return !eval_value(&op->ops[0], error); -} -calculated_number eval_sign_plus(EVAL_NODE *op, int *error) { - return eval_value(&op->ops[0], error); -} -calculated_number eval_sign_minus(EVAL_NODE *op, int *error) { - return -eval_value(&op->ops[0], error); -} - -static struct operator { - const char *print_as; - char precedence; - char parameters; - calculated_number (*eval)(EVAL_NODE *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, 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, 1, eval_nop } -}; - -#define eval_precedence(operator) (operators[(unsigned char)(operator)].precedence) - -static inline calculated_number eval_node(EVAL_NODE *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 unsigned char parse_operator(const char **string, int *precedence) { skip_spaces(string); @@ -432,6 +573,9 @@ static inline unsigned char parse_operator(const char **string, int *precedence) return EVAL_OPERATOR_NOP; } +// ---------------------------------------------------------------------------- +// memory management + static inline EVAL_NODE *eval_node_alloc(int count) { static int id = 1; @@ -453,7 +597,7 @@ static inline void eval_node_set_value_to_node(EVAL_NODE *op, int pos, EVAL_NODE op->ops[pos].expression = value; } -static inline void node_set_value_to_constant(EVAL_NODE *op, int pos, calculated_number value) { +static inline void eval_node_set_value_to_constant(EVAL_NODE *op, int pos, calculated_number value) { if(pos >= op->count) fatal("Invalid request to set position %d of OPERAND that has only %d values", pos + 1, op->count + 1); @@ -461,19 +605,19 @@ static inline void node_set_value_to_constant(EVAL_NODE *op, int pos, calculated op->ops[pos].number = value; } -static inline void variable_free(VARIABLE *v) { +static inline void eval_variable_free(EVAL_VARIABLE *v) { free(v); } -static inline void value_free(EVAL_VALUE *v) { +static inline void eval_value_free(EVAL_VALUE *v) { switch(v->type) { case EVAL_VALUE_EXPRESSION: eval_node_free(v->expression); break; -// case EVAL_VALUE_VARIABLE: -// variable_free(v->variable); -// break; + case EVAL_VALUE_VARIABLE: + eval_variable_free(v->variable); + break; default: break; @@ -484,12 +628,16 @@ static inline void eval_node_free(EVAL_NODE *op) { if(op->count) { int i; for(i = op->count - 1; i >= 0 ;i--) - value_free(&op->ops[i]); + eval_value_free(&op->ops[i]); } free(op); } +// ---------------------------------------------------------------------------- +// the parsing logic + +// helper function to avoid allocations all over the place static inline EVAL_NODE *parse_next_operand_given_its_operator(const char **string, unsigned char operator_type, int *error) { EVAL_NODE *sub = parse_one_full_operand(string, error); if(!sub) return NULL; @@ -500,6 +648,7 @@ static inline EVAL_NODE *parse_next_operand_given_its_operator(const char **stri return op; } +// parse a full operand, including its sign or other associative operator (e.g. NOT) static inline EVAL_NODE *parse_one_full_operand(const char **string, int *error) { EVAL_NODE *op1 = NULL; calculated_number number; @@ -544,7 +693,7 @@ static inline EVAL_NODE *parse_one_full_operand(const char **string, int *error) else if(parse_constant(string, &number)) { op1 = eval_node_alloc(1); op1->operator = EVAL_OPERATOR_VALUE; - node_set_value_to_constant(op1, 0, number); + eval_node_set_value_to_constant(op1, 0, number); } else if(*string) *error = EVAL_ERROR_UNKNOWN_OPERAND; @@ -554,6 +703,8 @@ static inline EVAL_NODE *parse_one_full_operand(const char **string, int *error) return op1; } +// parse an operator and the rest of the expression +// precedence processing is handled here static inline EVAL_NODE *parse_rest_of_expression(const char **string, int *error, EVAL_NODE *op1) { EVAL_NODE *op2 = NULL; unsigned char operator; @@ -574,14 +725,19 @@ static inline EVAL_NODE *parse_rest_of_expression(const char **string, int *erro op->operator = operator; op->precedence = precedence; - eval_node_set_value_to_node(op, 0, op1); eval_node_set_value_to_node(op, 1, op2); + // precedence processing + // if this operator has a higher precedence compared to its next + // put the next operator on top of us (top = evaluated later) + // function recursion does the rest... if(op->precedence > op1->precedence && op1->count == 2 && op1->operator != '(' && op1->ops[1].type == EVAL_VALUE_EXPRESSION) { eval_node_set_value_to_node(op, 0, op1->ops[1].expression); op1->ops[1].expression = op; op = op1; } + else + eval_node_set_value_to_node(op, 0, op1); return parse_rest_of_expression(string, error, op); } @@ -597,6 +753,7 @@ static inline EVAL_NODE *parse_rest_of_expression(const char **string, int *erro return op1; } +// high level function to parse an expression or a sub-expression static inline EVAL_NODE *parse_full_expression(const char **string, int *error) { EVAL_NODE *op1 = NULL; @@ -612,7 +769,24 @@ static inline EVAL_NODE *parse_full_expression(const char **string, int *error) // ---------------------------------------------------------------------------- // public API -EVAL_NODE *expression_parse(const char *string, const char **failed_at, int *error) { +int expression_evaluate(EVAL_EXPRESSION *exp) { + exp->error = EVAL_ERROR_OK; + + buffer_reset(exp->error_msg); + exp->result = eval_node(exp, (EVAL_NODE *)exp->nodes, &exp->error); + + if(exp->error != EVAL_ERROR_OK) { + if(buffer_strlen(exp->error_msg)) + buffer_strcat(exp->error_msg, "; "); + + buffer_sprintf(exp->error_msg, "failed to evaluate expression with error %d (%s)", exp->error, expression_strerror(exp->error)); + return 0; + } + + return 1; +} + +EVAL_EXPRESSION *expression_parse(const char *string, const char **failed_at, int *error) { const char *s; int err = EVAL_ERROR_OK; unsigned long pos = 0; @@ -626,26 +800,39 @@ EVAL_NODE *expression_parse(const char *string, const char **failed_at, int *err if(!op) { pos = s - string + 1; error("failed to parse expression '%s': %s at character %lu (i.e.: '%s').", string, expression_strerror(err), pos, s); + return NULL; } - return op; -} - -calculated_number expression_evaluate(EVAL_NODE *expression, int *error) { - int err = EVAL_ERROR_OK; - calculated_number ret = eval_node(expression, &err); - + BUFFER *out = buffer_create(1024); + print_parsed_as_node(out, op, &err); if(err != EVAL_ERROR_OK) { - error("Failed to execute expression with error %d (%s)", err, expression_strerror(err)); - if(error) *error = err; - return 0; + error("failed to re-generate expression '%s' with reason: %s", string, expression_strerror(err)); + eval_node_free(op); + buffer_free(out); + return NULL; } - return ret; + EVAL_EXPRESSION *exp = calloc(1, sizeof(EVAL_EXPRESSION)); + if(!exp) fatal("Cannot allocate EVAL_EXPRESSION"); + + exp->parsed_as = strdup(buffer_tostring(out)); + if(!exp->parsed_as) fatal("Cannot allocate memory for parsed-as string"); + buffer_free(out); + + exp->error_msg = buffer_create(100); + exp->nodes = (void *)op; + + return exp; } -void expression_free(EVAL_NODE *op) { - if(op) eval_node_free(op); +void expression_free(EVAL_EXPRESSION *exp) { + if(!exp) return; + + if(exp->nodes) eval_node_free((EVAL_NODE *)exp->nodes); + free((void *)exp->source); + free((void *)exp->parsed_as); + buffer_free(exp->error_msg); + free(exp); } const char *expression_strerror(int error) { @@ -677,6 +864,9 @@ const char *expression_strerror(int error) { case EVAL_ERROR_VALUE_IS_INFINITE: return "computed value is infinite"; + case EVAL_ERROR_UNKNOWN_VARIABLE: + return "undefined variable"; + default: return "unknown error"; } diff --git a/src/eval.h b/src/eval.h index a645b31b..1d1f9e02 100644 --- a/src/eval.h +++ b/src/eval.h @@ -1,38 +1,33 @@ #ifndef NETDATA_EVAL_H #define NETDATA_EVAL_H -typedef struct variable { +typedef struct eval_variable { char *name; struct rrdvar *rrdvar; - struct variable *next; -} VARIABLE; + struct eval_variable *next; +} EVAL_VARIABLE; + +typedef struct eval_expression { + const char *source; + const char *parsed_as; + + calculated_number result; + + int error; + BUFFER *error_msg; + + // hidden EVAL_NODE * + void *nodes; + + // custom data to be used for looking up variables + void *data; +} EVAL_EXPRESSION; #define EVAL_VALUE_INVALID 0 #define EVAL_VALUE_NUMBER 1 #define EVAL_VALUE_VARIABLE 2 #define EVAL_VALUE_EXPRESSION 3 -// these are used for EVAL_NODE.operator -#define EVAL_OPERATOR_NOP '\0' -#define EVAL_OPERATOR_VALUE ':' -#define EVAL_OPERATOR_EXPRESSION_OPEN '(' -#define EVAL_OPERATOR_EXPRESSION_CLOSE ')' -#define EVAL_OPERATOR_NOT '!' -#define EVAL_OPERATOR_PLUS '+' -#define EVAL_OPERATOR_MINUS '-' -#define EVAL_OPERATOR_AND '&' -#define EVAL_OPERATOR_OR '|' -#define EVAL_OPERATOR_GREATER_THAN_OR_EQUAL 'G' -#define EVAL_OPERATOR_LESS_THAN_OR_EQUAL 'L' -#define EVAL_OPERATOR_NOT_EQUAL '~' -#define EVAL_OPERATOR_EQUAL '=' -#define EVAL_OPERATOR_LESS '<' -#define EVAL_OPERATOR_GREATER '>' -#define EVAL_OPERATOR_MULTIPLY '*' -#define EVAL_OPERATOR_DIVIDE '/' -#define EVAL_OPERATOR_SIGN_PLUS 'P' -#define EVAL_OPERATOR_SIGN_MINUS 'M' - #define EVAL_ERROR_OK 0 // parsing errors @@ -46,29 +41,22 @@ typedef struct variable { #define EVAL_ERROR_INVALID_NUMBER_OF_OPERANDS 6 #define EVAL_ERROR_VALUE_IS_NAN 7 #define EVAL_ERROR_VALUE_IS_INFINITE 8 +#define EVAL_ERROR_UNKNOWN_VARIABLE 9 -typedef struct eval_value { - int type; - - union { - calculated_number number; - VARIABLE *variable; - struct eval_node *expression; - }; -} EVAL_VALUE; +// parse the given string as an expression and return: +// a pointer to an expression if it parsed OK +// NULL in which case the pointer to error has the error code +extern EVAL_EXPRESSION *expression_parse(const char *string, const char **failed_at, int *error); -typedef struct eval_node { - int id; - unsigned char operator; - int precedence; +// free all resources allocated for an expression +extern void expression_free(EVAL_EXPRESSION *op); - int count; - EVAL_VALUE ops[]; -} EVAL_NODE; - -extern EVAL_NODE *expression_parse(const char *string, const char **failed_at, int *error); -extern calculated_number expression_evaluate(EVAL_NODE *expression, int *error); -extern void expression_free(EVAL_NODE *op); +// convert an error code to a message extern const char *expression_strerror(int error); +// evaluate an expression and return +// 1 = OK, the result is in: expression->result +// 2 = FAILED, the error message is in: buffer_tostring(expression->error_msg) +extern int expression_evaluate(EVAL_EXPRESSION *expression); + #endif //NETDATA_EVAL_H diff --git a/src/health.c b/src/health.c index 98e9013d..28bc464e 100644 --- a/src/health.c +++ b/src/health.c @@ -49,7 +49,7 @@ static inline void rrdvar_free(RRDHOST *host, RRDVAR *rv) { if(host) { // FIXME: we may need some kind of locking here // to have mutually exclusive access with eval() - VARIABLE *rf; + EVAL_VARIABLE *rf; for (rf = host->references; rf; rf = rf->next) if (rf->rrdvar == rv) rf->rrdvar = NULL; } diff --git a/src/rrd.h b/src/rrd.h index e7bdc5a8..ca6165e9 100644 --- a/src/rrd.h +++ b/src/rrd.h @@ -301,7 +301,7 @@ struct rrdhost { // all variable references are linked here // RRDVARs may be free'd, so every time this happens // we need to find all their references and invalidate them - VARIABLE *references; + EVAL_VARIABLE *references; }; typedef struct rrdhost RRDHOST; diff --git a/src/web_buffer.h b/src/web_buffer.h index 6b10c525..0370491e 100644 --- a/src/web_buffer.h +++ b/src/web_buffer.h @@ -1,7 +1,7 @@ #ifndef NETDATA_WEB_BUFFER_H #define NETDATA_WEB_BUFFER_H 1 -#define WEB_DATA_LENGTH_INCREASE_STEP 16384 +#define WEB_DATA_LENGTH_INCREASE_STEP 1024 typedef struct web_buffer { size_t size; // allocation size of buffer diff --git a/src/web_client.c b/src/web_client.c index 952aa358..91ae335d 100644 --- a/src/web_client.c +++ b/src/web_client.c @@ -698,7 +698,7 @@ int web_client_api_v1_badge(struct web_client *w, char *url) { if(!strcmp(name, "chart")) chart = value; else if(!strcmp(name, "dimension") || !strcmp(name, "dim") || !strcmp(name, "dimensions") || !strcmp(name, "dims")) { if(!dimensions) - dimensions = buffer_create(strlen(value)); + dimensions = buffer_create(100); if(dimensions) { buffer_strcat(dimensions, "|"); @@ -860,7 +860,7 @@ int web_client_api_request_v1_data(struct web_client *w, char *url) if(!strcmp(name, "chart")) chart = value; else if(!strcmp(name, "dimension") || !strcmp(name, "dim") || !strcmp(name, "dimensions") || !strcmp(name, "dims")) { - if(!dimensions) dimensions = buffer_create(strlen(value)); + if(!dimensions) dimensions = buffer_create(100); if(dimensions) { buffer_strcat(dimensions, "|"); buffer_strcat(dimensions, value); -- 2.39.2