src/eval.c

   1 #include "common.h"
   2
   3 // ----------------------------------------------------------------------------
   4 // data structures for storing the parsed expression in memory
   5
   6 typedef struct eval_value {
   7     int type;
   8
   9     union {
  10         calculated_number number;
  11         EVAL_VARIABLE *variable;
  12         struct eval_node *expression;
  13     };
  14 } EVAL_VALUE;
  15
  16 typedef struct eval_node {
  17     int id;
  18     unsigned char operator;
  19     int precedence;
  20
  21     int count;
  22     EVAL_VALUE ops[];
  23 } EVAL_NODE;
  24
  25 // these are used for EVAL_NODE.operator
  26 // they are used as internal IDs to identify an operator
  27 // THEY ARE NOT USED FOR PARSING OPERATORS LIKE THAT
  28 #define EVAL_OPERATOR_NOP                   '\0'
  29 #define EVAL_OPERATOR_EXPRESSION_OPEN       '('
  30 #define EVAL_OPERATOR_EXPRESSION_CLOSE      ')'
  31 #define EVAL_OPERATOR_NOT                   '!'
  32 #define EVAL_OPERATOR_PLUS                  '+'
  33 #define EVAL_OPERATOR_MINUS                 '-'
  34 #define EVAL_OPERATOR_AND                   '&'
  35 #define EVAL_OPERATOR_OR                    '|'
  36 #define EVAL_OPERATOR_GREATER_THAN_OR_EQUAL 'G'
  37 #define EVAL_OPERATOR_LESS_THAN_OR_EQUAL    'L'
  38 #define EVAL_OPERATOR_NOT_EQUAL             '~'
  39 #define EVAL_OPERATOR_EQUAL                 '='
  40 #define EVAL_OPERATOR_LESS                  '<'
  41 #define EVAL_OPERATOR_GREATER               '>'
  42 #define EVAL_OPERATOR_MULTIPLY              '*'
  43 #define EVAL_OPERATOR_DIVIDE                '/'
  44 #define EVAL_OPERATOR_SIGN_PLUS             'P'
  45 #define EVAL_OPERATOR_SIGN_MINUS            'M'
  46 #define EVAL_OPERATOR_ABS                   'A'
  47 #define EVAL_OPERATOR_IF_THEN_ELSE          '?'
  48
  49 // ----------------------------------------------------------------------------
  50 // forward function definitions
  51
  52 static inline void eval_node_free(EVAL_NODE *op);
  53 static inline EVAL_NODE *parse_full_expression(const char **string, int *error);
  54 static inline EVAL_NODE *parse_one_full_operand(const char **string, int *error);
  55 static inline calculated_number eval_node(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error);
  56 static inline void print_parsed_as_node(BUFFER *out, EVAL_NODE *op, int *error);
  57 static inline void print_parsed_as_constant(BUFFER *out, calculated_number n);
  58
  59 // ----------------------------------------------------------------------------
  60 // evaluation of expressions
  61
  62 static inline calculated_number eval_variable(EVAL_EXPRESSION *exp, EVAL_VARIABLE *v, int *error) {
  63     static uint32_t this_hash = 0, now_hash = 0, after_hash = 0, before_hash = 0, status_hash = 0, removed_hash = 0, uninitialized_hash = 0, undefined_hash = 0, clear_hash = 0, warning_hash = 0, critical_hash = 0;
  64     calculated_number n;
  65
  66     if(unlikely(this_hash == 0)) {
  67         this_hash = simple_hash("this");
  68         now_hash = simple_hash("now");
  69         after_hash = simple_hash("after");
  70         before_hash = simple_hash("before");
  71         status_hash = simple_hash("status");
  72         removed_hash = simple_hash("REMOVED");
  73         uninitialized_hash = simple_hash("UNINITIALIZED");
  74         undefined_hash = simple_hash("UNDEFINED");
  75         clear_hash = simple_hash("CLEAR");
  76         warning_hash = simple_hash("WARNING");
  77         critical_hash = simple_hash("CRITICAL");
  78     }
  79
  80     if(unlikely(v->hash == this_hash && !strcmp(v->name, "this"))) {
  81         n = (exp->this)?*exp->this:NAN;
  82         buffer_strcat(exp->error_msg, "[ $this = ");
  83         print_parsed_as_constant(exp->error_msg, n);
  84         buffer_strcat(exp->error_msg, " ] ");
  85         return n;
  86     }
  87
  88     if(unlikely(v->hash == after_hash && !strcmp(v->name, "after"))) {
  89         n = (exp->after && *exp->after)?*exp->after:NAN;
  90         buffer_strcat(exp->error_msg, "[ $after = ");
  91         print_parsed_as_constant(exp->error_msg, n);
  92         buffer_strcat(exp->error_msg, " ] ");
  93         return n;
  94     }
  95
  96     if(unlikely(v->hash == before_hash && !strcmp(v->name, "before"))) {
  97         n = (exp->before && *exp->before)?*exp->before:NAN;
  98         buffer_strcat(exp->error_msg, "[ $before = ");
  99         print_parsed_as_constant(exp->error_msg, n);
 100         buffer_strcat(exp->error_msg, " ] ");
 101         return n;
 102     }
 103
 104     if(unlikely(v->hash == now_hash && !strcmp(v->name, "now"))) {
 105         n = now_realtime_sec();
 106         buffer_strcat(exp->error_msg, "[ $now = ");
 107         print_parsed_as_constant(exp->error_msg, n);
 108         buffer_strcat(exp->error_msg, " ] ");
 109         return n;
 110     }
 111
 112     if(unlikely(v->hash == status_hash && !strcmp(v->name, "status"))) {
 113         n = (exp->status)?*exp->status:RRDCALC_STATUS_UNINITIALIZED;
 114         buffer_strcat(exp->error_msg, "[ $status = ");
 115         print_parsed_as_constant(exp->error_msg, n);
 116         buffer_strcat(exp->error_msg, " ] ");
 117         return n;
 118     }
 119
 120     if(unlikely(v->hash == removed_hash && !strcmp(v->name, "REMOVED"))) {
 121         n = RRDCALC_STATUS_REMOVED;
 122         buffer_strcat(exp->error_msg, "[ $REMOVED = ");
 123         print_parsed_as_constant(exp->error_msg, n);
 124         buffer_strcat(exp->error_msg, " ] ");
 125         return n;
 126     }
 127
 128     if(unlikely(v->hash == uninitialized_hash && !strcmp(v->name, "UNINITIALIZED"))) {
 129         n = RRDCALC_STATUS_UNINITIALIZED;
 130         buffer_strcat(exp->error_msg, "[ $UNINITIALIZED = ");
 131         print_parsed_as_constant(exp->error_msg, n);
 132         buffer_strcat(exp->error_msg, " ] ");
 133         return n;
 134     }
 135
 136     if(unlikely(v->hash == undefined_hash && !strcmp(v->name, "UNDEFINED"))) {
 137         n = RRDCALC_STATUS_UNDEFINED;
 138         buffer_strcat(exp->error_msg, "[ $UNDEFINED = ");
 139         print_parsed_as_constant(exp->error_msg, n);
 140         buffer_strcat(exp->error_msg, " ] ");
 141         return n;
 142     }
 143
 144     if(unlikely(v->hash == clear_hash && !strcmp(v->name, "CLEAR"))) {
 145         n = RRDCALC_STATUS_CLEAR;
 146         buffer_strcat(exp->error_msg, "[ $CLEAR = ");
 147         print_parsed_as_constant(exp->error_msg, n);
 148         buffer_strcat(exp->error_msg, " ] ");
 149         return n;
 150     }
 151
 152     if(unlikely(v->hash == warning_hash && !strcmp(v->name, "WARNING"))) {
 153         n = RRDCALC_STATUS_WARNING;
 154         buffer_strcat(exp->error_msg, "[ $WARNING = ");
 155         print_parsed_as_constant(exp->error_msg, n);
 156         buffer_strcat(exp->error_msg, " ] ");
 157         return n;
 158     }
 159
 160     if(unlikely(v->hash == critical_hash && !strcmp(v->name, "CRITICAL"))) {
 161         n = RRDCALC_STATUS_CRITICAL;
 162         buffer_strcat(exp->error_msg, "[ $CRITICAL = ");
 163         print_parsed_as_constant(exp->error_msg, n);
 164         buffer_strcat(exp->error_msg, " ] ");
 165         return n;
 166     }
 167
 168     if(exp->rrdcalc && health_variable_lookup(v->name, v->hash, exp->rrdcalc, &n)) {
 169         buffer_sprintf(exp->error_msg, "[ $%s = ", v->name);
 170         print_parsed_as_constant(exp->error_msg, n);
 171         buffer_strcat(exp->error_msg, " ] ");
 172         return n;
 173     }
 174
 175     *error = EVAL_ERROR_UNKNOWN_VARIABLE;
 176     buffer_sprintf(exp->error_msg, "[ undefined variable '%s' ] ", v->name);
 177     return 0;
 178 }
 179
 180 static inline calculated_number eval_value(EVAL_EXPRESSION *exp, EVAL_VALUE *v, int *error) {
 181     calculated_number n;
 182
 183     switch(v->type) {
 184         case EVAL_VALUE_EXPRESSION:
 185             n = eval_node(exp, v->expression, error);
 186             break;
 187
 188         case EVAL_VALUE_NUMBER:
 189             n = v->number;
 190             break;
 191
 192         case EVAL_VALUE_VARIABLE:
 193             n = eval_variable(exp, v->variable, error);
 194             break;
 195
 196         default:
 197             *error = EVAL_ERROR_INVALID_VALUE;
 198             n = 0;
 199             break;
 200     }
 201
 202     return n;
 203 }
 204
 205 static inline int is_true(calculated_number n) {
 206     if(isnan(n)) return 0;
 207     if(isinf(n)) return 1;
 208     if(n == 0) return 0;
 209     return 1;
 210 }
 211
 212 calculated_number eval_and(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error) {
 213     return is_true(eval_value(exp, &op->ops[0], error)) && is_true(eval_value(exp, &op->ops[1], error));
 214 }
 215 calculated_number eval_or(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error) {
 216     return is_true(eval_value(exp, &op->ops[0], error)) || is_true(eval_value(exp, &op->ops[1], error));
 217 }
 218 calculated_number eval_greater_than_or_equal(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error) {
 219     calculated_number n1 = eval_value(exp, &op->ops[0], error);
 220     calculated_number n2 = eval_value(exp, &op->ops[1], error);
 221     return isgreaterequal(n1, n2);
 222 }
 223 calculated_number eval_less_than_or_equal(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error) {
 224     calculated_number n1 = eval_value(exp, &op->ops[0], error);
 225     calculated_number n2 = eval_value(exp, &op->ops[1], error);
 226     return islessequal(n1, n2);
 227 }
 228 calculated_number eval_equal(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error) {
 229     calculated_number n1 = eval_value(exp, &op->ops[0], error);
 230     calculated_number n2 = eval_value(exp, &op->ops[1], error);
 231     if(isnan(n1) && isnan(n2)) return 1;
 232     if(isinf(n1) && isinf(n2)) return 1;
 233     if(isnan(n1) || isnan(n2)) return 0;
 234     if(isinf(n1) || isinf(n2)) return 0;
 235     return n1 == n2;
 236 }
 237 calculated_number eval_not_equal(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error) {
 238     return !eval_equal(exp, op, error);
 239 }
 240 calculated_number eval_less(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error) {
 241     calculated_number n1 = eval_value(exp, &op->ops[0], error);
 242     calculated_number n2 = eval_value(exp, &op->ops[1], error);
 243     return isless(n1, n2);
 244 }
 245 calculated_number eval_greater(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error) {
 246     calculated_number n1 = eval_value(exp, &op->ops[0], error);
 247     calculated_number n2 = eval_value(exp, &op->ops[1], error);
 248     return isgreater(n1, n2);
 249 }
 250 calculated_number eval_plus(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error) {
 251     calculated_number n1 = eval_value(exp, &op->ops[0], error);
 252     calculated_number n2 = eval_value(exp, &op->ops[1], error);
 253     if(isnan(n1) || isnan(n2)) return NAN;
 254     if(isinf(n1) || isinf(n2)) return INFINITY;
 255     return n1 + n2;
 256 }
 257 calculated_number eval_minus(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error) {
 258     calculated_number n1 = eval_value(exp, &op->ops[0], error);
 259     calculated_number n2 = eval_value(exp, &op->ops[1], error);
 260     if(isnan(n1) || isnan(n2)) return NAN;
 261     if(isinf(n1) || isinf(n2)) return INFINITY;
 262     return n1 - n2;
 263 }
 264 calculated_number eval_multiply(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error) {
 265     calculated_number n1 = eval_value(exp, &op->ops[0], error);
 266     calculated_number n2 = eval_value(exp, &op->ops[1], error);
 267     if(isnan(n1) || isnan(n2)) return NAN;
 268     if(isinf(n1) || isinf(n2)) return INFINITY;
 269     return n1 * n2;
 270 }
 271 calculated_number eval_divide(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error) {
 272     calculated_number n1 = eval_value(exp, &op->ops[0], error);
 273     calculated_number n2 = eval_value(exp, &op->ops[1], error);
 274     if(isnan(n1) || isnan(n2)) return NAN;
 275     if(isinf(n1) || isinf(n2)) return INFINITY;
 276     return n1 / n2;
 277 }
 278 calculated_number eval_nop(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error) {
 279     return eval_value(exp, &op->ops[0], error);
 280 }
 281 calculated_number eval_not(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error) {
 282     return !is_true(eval_value(exp, &op->ops[0], error));
 283 }
 284 calculated_number eval_sign_plus(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error) {
 285     return eval_value(exp, &op->ops[0], error);
 286 }
 287 calculated_number eval_sign_minus(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error) {
 288     calculated_number n1 = eval_value(exp, &op->ops[0], error);
 289     if(isnan(n1)) return NAN;
 290     if(isinf(n1)) return INFINITY;
 291     return -n1;
 292 }
 293 calculated_number eval_abs(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error) {
 294     calculated_number n1 = eval_value(exp, &op->ops[0], error);
 295     if(isnan(n1)) return NAN;
 296     if(isinf(n1)) return INFINITY;
 297     return abs(n1);
 298 }
 299 calculated_number eval_if_then_else(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error) {
 300     if(is_true(eval_value(exp, &op->ops[0], error)))
 301         return eval_value(exp, &op->ops[1], error);
 302     else
 303         return eval_value(exp, &op->ops[2], error);
 304 }
 305
 306 static struct operator {
 307     const char *print_as;
 308     char precedence;
 309     char parameters;
 310     char isfunction;
 311     calculated_number (*eval)(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error);
 312 } operators[256] = {
 313         // this is a random access array
 314         // we always access it with a known EVAL_OPERATOR_X
 315
 316         [EVAL_OPERATOR_AND]                   = { "&&", 2, 2, 0, eval_and },
 317         [EVAL_OPERATOR_OR]                    = { "||", 2, 2, 0, eval_or },
 318         [EVAL_OPERATOR_GREATER_THAN_OR_EQUAL] = { ">=", 3, 2, 0, eval_greater_than_or_equal },
 319         [EVAL_OPERATOR_LESS_THAN_OR_EQUAL]    = { "<=", 3, 2, 0, eval_less_than_or_equal },
 320         [EVAL_OPERATOR_NOT_EQUAL]             = { "!=", 3, 2, 0, eval_not_equal },
 321         [EVAL_OPERATOR_EQUAL]                 = { "==", 3, 2, 0, eval_equal },
 322         [EVAL_OPERATOR_LESS]                  = { "<",  3, 2, 0, eval_less },
 323         [EVAL_OPERATOR_GREATER]               = { ">",  3, 2, 0, eval_greater },
 324         [EVAL_OPERATOR_PLUS]                  = { "+",  4, 2, 0, eval_plus },
 325         [EVAL_OPERATOR_MINUS]                 = { "-",  4, 2, 0, eval_minus },
 326         [EVAL_OPERATOR_MULTIPLY]              = { "*",  5, 2, 0, eval_multiply },
 327         [EVAL_OPERATOR_DIVIDE]                = { "/",  5, 2, 0, eval_divide },
 328         [EVAL_OPERATOR_NOT]                   = { "!",  6, 1, 0, eval_not },
 329         [EVAL_OPERATOR_SIGN_PLUS]             = { "+",  6, 1, 0, eval_sign_plus },
 330         [EVAL_OPERATOR_SIGN_MINUS]            = { "-",  6, 1, 0, eval_sign_minus },
 331         [EVAL_OPERATOR_ABS]                   = { "abs(",6,1, 1, eval_abs },
 332         [EVAL_OPERATOR_IF_THEN_ELSE]          = { "?",  7, 3, 0, eval_if_then_else },
 333         [EVAL_OPERATOR_NOP]                   = { NULL, 8, 1, 0, eval_nop },
 334         [EVAL_OPERATOR_EXPRESSION_OPEN]       = { NULL, 8, 1, 0, eval_nop },
 335
 336         // this should exist in our evaluation list
 337         [EVAL_OPERATOR_EXPRESSION_CLOSE]      = { NULL, 99, 1, 0, eval_nop }
 338 };
 339
 340 #define eval_precedence(operator) (operators[(unsigned char)(operator)].precedence)
 341
 342 static inline calculated_number eval_node(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error) {
 343     if(unlikely(op->count != operators[op->operator].parameters)) {
 344         *error = EVAL_ERROR_INVALID_NUMBER_OF_OPERANDS;
 345         return 0;
 346     }
 347
 348     calculated_number n = operators[op->operator].eval(exp, op, error);
 349
 350     return n;
 351 }
 352
 353 // ----------------------------------------------------------------------------
 354 // parsed-as generation
 355
 356 static inline void print_parsed_as_variable(BUFFER *out, EVAL_VARIABLE *v, int *error) {
 357     (void)error;
 358     buffer_sprintf(out, "$%s", v->name);
 359 }
 360
 361 static inline void print_parsed_as_constant(BUFFER *out, calculated_number n) {
 362     if(unlikely(isnan(n))) {
 363         buffer_strcat(out, "nan");
 364         return;
 365     }
 366
 367     if(unlikely(isinf(n))) {
 368         buffer_strcat(out, "inf");
 369         return;
 370     }
 371
 372     char b[100+1], *s;
 373     snprintfz(b, 100, CALCULATED_NUMBER_FORMAT, n);
 374
 375     s = &b[strlen(b) - 1];
 376     while(s > b && *s == '0') {
 377         *s ='\0';
 378         s--;
 379     }
 380
 381     if(s > b && *s == '.')
 382         *s = '\0';
 383
 384     buffer_strcat(out, b);
 385 }
 386
 387 static inline void print_parsed_as_value(BUFFER *out, EVAL_VALUE *v, int *error) {
 388     switch(v->type) {
 389         case EVAL_VALUE_EXPRESSION:
 390             print_parsed_as_node(out, v->expression, error);
 391             break;
 392
 393         case EVAL_VALUE_NUMBER:
 394             print_parsed_as_constant(out, v->number);
 395             break;
 396
 397         case EVAL_VALUE_VARIABLE:
 398             print_parsed_as_variable(out, v->variable, error);
 399             break;
 400
 401         default:
 402             *error = EVAL_ERROR_INVALID_VALUE;
 403             break;
 404     }
 405 }
 406
 407 static inline void print_parsed_as_node(BUFFER *out, EVAL_NODE *op, int *error) {
 408     if(unlikely(op->count != operators[op->operator].parameters)) {
 409         *error = EVAL_ERROR_INVALID_NUMBER_OF_OPERANDS;
 410         return;
 411     }
 412
 413     if(operators[op->operator].parameters == 1) {
 414
 415         if(operators[op->operator].print_as)
 416             buffer_sprintf(out, "%s", operators[op->operator].print_as);
 417
 418         //if(op->operator == EVAL_OPERATOR_EXPRESSION_OPEN)
 419         //    buffer_strcat(out, "(");
 420
 421         print_parsed_as_value(out, &op->ops[0], error);
 422
 423         //if(op->operator == EVAL_OPERATOR_EXPRESSION_OPEN)
 424         //    buffer_strcat(out, ")");
 425     }
 426
 427     else if(operators[op->operator].parameters == 2) {
 428         buffer_strcat(out, "(");
 429         print_parsed_as_value(out, &op->ops[0], error);
 430
 431         if(operators[op->operator].print_as)
 432             buffer_sprintf(out, " %s ", operators[op->operator].print_as);
 433
 434         print_parsed_as_value(out, &op->ops[1], error);
 435         buffer_strcat(out, ")");
 436     }
 437     else if(op->operator == EVAL_OPERATOR_IF_THEN_ELSE && operators[op->operator].parameters == 3) {
 438         buffer_strcat(out, "(");
 439         print_parsed_as_value(out, &op->ops[0], error);
 440
 441         if(operators[op->operator].print_as)
 442             buffer_sprintf(out, " %s ", operators[op->operator].print_as);
 443
 444         print_parsed_as_value(out, &op->ops[1], error);
 445         buffer_strcat(out, " : ");
 446         print_parsed_as_value(out, &op->ops[2], error);
 447         buffer_strcat(out, ")");
 448     }
 449
 450     if(operators[op->operator].isfunction)
 451         buffer_strcat(out, ")");
 452 }
 453
 454 // ----------------------------------------------------------------------------
 455 // parsing expressions
 456
 457 // skip spaces
 458 static inline void skip_spaces(const char **string) {
 459     const char *s = *string;
 460     while(isspace(*s)) s++;
 461     *string = s;
 462 }
 463
 464 // what character can appear just after an operator keyword
 465 // like NOT AND OR ?
 466 static inline int isoperatorterm_word(const char s) {
 467     if(isspace(s) || s == '(' || s == '$' || s == '!' || s == '-' || s == '+' || isdigit(s) || !s)
 468         return 1;
 469
 470     return 0;
 471 }
 472
 473 // what character can appear just after an operator symbol?
 474 static inline int isoperatorterm_symbol(const char s) {
 475     if(isoperatorterm_word(s) || isalpha(s))
 476         return 1;
 477
 478     return 0;
 479 }
 480
 481 // return 1 if the character should never appear in a variable
 482 static inline int isvariableterm(const char s) {
 483     if(isalnum(s) || s == '.' || s == '_')
 484         return 0;
 485
 486     return 1;
 487 }
 488
 489 // ----------------------------------------------------------------------------
 490 // parse operators
 491
 492 static inline int parse_and(const char **string) {
 493     const char *s = *string;
 494
 495     // AND
 496     if((s[0] == 'A' || s[0] == 'a') && (s[1] == 'N' || s[1] == 'n') && (s[2] == 'D' || s[2] == 'd') && isoperatorterm_word(s[3])) {
 497         *string = &s[4];
 498         return 1;
 499     }
 500
 501     // &&
 502     if(s[0] == '&' && s[1] == '&' && isoperatorterm_symbol(s[2])) {
 503         *string = &s[2];
 504         return 1;
 505     }
 506
 507     return 0;
 508 }
 509
 510 static inline int parse_or(const char **string) {
 511     const char *s = *string;
 512
 513     // OR
 514     if((s[0] == 'O' || s[0] == 'o') && (s[1] == 'R' || s[1] == 'r') && isoperatorterm_word(s[2])) {
 515         *string = &s[3];
 516         return 1;
 517     }
 518
 519     // ||
 520     if(s[0] == '|' && s[1] == '|' && isoperatorterm_symbol(s[2])) {
 521         *string = &s[2];
 522         return 1;
 523     }
 524
 525     return 0;
 526 }
 527
 528 static inline int parse_greater_than_or_equal(const char **string) {
 529     const char *s = *string;
 530
 531     // >=
 532     if(s[0] == '>' && s[1] == '=' && isoperatorterm_symbol(s[2])) {
 533         *string = &s[2];
 534         return 1;
 535     }
 536
 537     return 0;
 538 }
 539
 540 static inline int parse_less_than_or_equal(const char **string) {
 541     const char *s = *string;
 542
 543     // <=
 544     if (s[0] == '<' && s[1] == '=' && isoperatorterm_symbol(s[2])) {
 545         *string = &s[2];
 546         return 1;
 547     }
 548
 549     return 0;
 550 }
 551
 552 static inline int parse_greater(const char **string) {
 553     const char *s = *string;
 554
 555     // >
 556     if(s[0] == '>' && isoperatorterm_symbol(s[1])) {
 557         *string = &s[1];
 558         return 1;
 559     }
 560
 561     return 0;
 562 }
 563
 564 static inline int parse_less(const char **string) {
 565     const char *s = *string;
 566
 567     // <
 568     if(s[0] == '<' && isoperatorterm_symbol(s[1])) {
 569         *string = &s[1];
 570         return 1;
 571     }
 572
 573     return 0;
 574 }
 575
 576 static inline int parse_equal(const char **string) {
 577     const char *s = *string;
 578
 579     // ==
 580     if(s[0] == '=' && s[1] == '=' && isoperatorterm_symbol(s[2])) {
 581         *string = &s[2];
 582         return 1;
 583     }
 584
 585     // =
 586     if(s[0] == '=' && isoperatorterm_symbol(s[1])) {
 587         *string = &s[1];
 588         return 1;
 589     }
 590
 591     return 0;
 592 }
 593
 594 static inline int parse_not_equal(const char **string) {
 595     const char *s = *string;
 596
 597     // !=
 598     if(s[0] == '!' && s[1] == '=' && isoperatorterm_symbol(s[2])) {
 599         *string = &s[2];
 600         return 1;
 601     }
 602
 603     // <>
 604     if(s[0] == '<' && s[1] == '>' && isoperatorterm_symbol(s[2])) {
 605         *string = &s[2];
 606     }
 607
 608     return 0;
 609 }
 610
 611 static inline int parse_not(const char **string) {
 612     const char *s = *string;
 613
 614     // NOT
 615     if((s[0] == 'N' || s[0] == 'n') && (s[1] == 'O' || s[1] == 'o') && (s[2] == 'T' || s[2] == 't') && isoperatorterm_word(s[3])) {
 616         *string = &s[3];
 617         return 1;
 618     }
 619
 620     if(s[0] == '!') {
 621         *string = &s[1];
 622         return 1;
 623     }
 624
 625     return 0;
 626 }
 627
 628 static inline int parse_multiply(const char **string) {
 629     const char *s = *string;
 630
 631     // *
 632     if(s[0] == '*' && isoperatorterm_symbol(s[1])) {
 633         *string = &s[1];
 634         return 1;
 635     }
 636
 637     return 0;
 638 }
 639
 640 static inline int parse_divide(const char **string) {
 641     const char *s = *string;
 642
 643     // /
 644     if(s[0] == '/' && isoperatorterm_symbol(s[1])) {
 645         *string = &s[1];
 646         return 1;
 647     }
 648
 649     return 0;
 650 }
 651
 652 static inline int parse_minus(const char **string) {
 653     const char *s = *string;
 654
 655     // -
 656     if(s[0] == '-' && isoperatorterm_symbol(s[1])) {
 657         *string = &s[1];
 658         return 1;
 659     }
 660
 661     return 0;
 662 }
 663
 664 static inline int parse_plus(const char **string) {
 665     const char *s = *string;
 666
 667     // +
 668     if(s[0] == '+' && isoperatorterm_symbol(s[1])) {
 669         *string = &s[1];
 670         return 1;
 671     }
 672
 673     return 0;
 674 }
 675
 676 static inline int parse_open_subexpression(const char **string) {
 677     const char *s = *string;
 678
 679     // (
 680     if(s[0] == '(') {
 681         *string = &s[1];
 682         return 1;
 683     }
 684
 685     return 0;
 686 }
 687
 688 #define parse_close_function(x) parse_close_subexpression(x)
 689
 690 static inline int parse_close_subexpression(const char **string) {
 691     const char *s = *string;
 692
 693     // )
 694     if(s[0] == ')') {
 695         *string = &s[1];
 696         return 1;
 697     }
 698
 699     return 0;
 700 }
 701
 702 static inline int parse_variable(const char **string, char *buffer, size_t len) {
 703     const char *s = *string;
 704
 705     // $
 706     if(s[0] == '$') {
 707         size_t i = 0;
 708         s++;
 709
 710         while(*s && !isvariableterm(*s) && i < len)
 711             buffer[i++] = *s++;
 712
 713         buffer[i] = '\0';
 714
 715         if(buffer[0]) {
 716             *string = &s[0];
 717             return 1;
 718         }
 719     }
 720
 721     return 0;
 722 }
 723
 724 static inline int parse_constant(const char **string, calculated_number *number) {
 725     char *end = NULL;
 726     calculated_number n = strtold(*string, &end);
 727     if(unlikely(!end || *string == end)) {
 728         *number = 0;
 729         return 0;
 730     }
 731     *number = n;
 732     *string = end;
 733     return 1;
 734 }
 735
 736 static inline int parse_abs(const char **string) {
 737     const char *s = *string;
 738
 739     // ABS
 740     if((s[0] == 'A' || s[0] == 'a') && (s[1] == 'B' || s[1] == 'b') && (s[2] == 'S' || s[2] == 's') && s[3] == '(') {
 741         *string = &s[3];
 742         return 1;
 743     }
 744
 745     return 0;
 746 }
 747
 748 static inline int parse_if_then_else(const char **string) {
 749     const char *s = *string;
 750
 751     // ?
 752     if(s[0] == '?') {
 753         *string = &s[1];
 754         return 1;
 755     }
 756
 757     return 0;
 758 }
 759
 760 static struct operator_parser {
 761     unsigned char id;
 762     int (*parse)(const char **);
 763 } operator_parsers[] = {
 764         // the order in this list is important!
 765         // the first matching will be used
 766         // so place the longer of overlapping ones
 767         // at the top
 768
 769         { EVAL_OPERATOR_AND,                   parse_and },
 770         { EVAL_OPERATOR_OR,                    parse_or },
 771         { EVAL_OPERATOR_GREATER_THAN_OR_EQUAL, parse_greater_than_or_equal },
 772         { EVAL_OPERATOR_LESS_THAN_OR_EQUAL,    parse_less_than_or_equal },
 773         { EVAL_OPERATOR_NOT_EQUAL,             parse_not_equal },
 774         { EVAL_OPERATOR_EQUAL,                 parse_equal },
 775         { EVAL_OPERATOR_LESS,                  parse_less },
 776         { EVAL_OPERATOR_GREATER,               parse_greater },
 777         { EVAL_OPERATOR_PLUS,                  parse_plus },
 778         { EVAL_OPERATOR_MINUS,                 parse_minus },
 779         { EVAL_OPERATOR_MULTIPLY,              parse_multiply },
 780         { EVAL_OPERATOR_DIVIDE,                parse_divide },
 781         { EVAL_OPERATOR_IF_THEN_ELSE,          parse_if_then_else },
 782
 783         /* we should not put in this list the following:
 784          *
 785          *  - NOT
 786          *  - (
 787          *  - )
 788          *
 789          * these are handled in code
 790          */
 791
 792         // termination
 793         { EVAL_OPERATOR_NOP, NULL }
 794 };
 795
 796 static inline unsigned char parse_operator(const char **string, int *precedence) {
 797     skip_spaces(string);
 798
 799     int i;
 800     for(i = 0 ; operator_parsers[i].parse != NULL ; i++)
 801         if(operator_parsers[i].parse(string)) {
 802             if(precedence) *precedence = eval_precedence(operator_parsers[i].id);
 803             return operator_parsers[i].id;
 804         }
 805
 806     return EVAL_OPERATOR_NOP;
 807 }
 808
 809 // ----------------------------------------------------------------------------
 810 // memory management
 811
 812 static inline EVAL_NODE *eval_node_alloc(int count) {
 813     static int id = 1;
 814
 815     EVAL_NODE *op = callocz(1, sizeof(EVAL_NODE) + (sizeof(EVAL_VALUE) * count));
 816
 817     op->id = id++;
 818     op->operator = EVAL_OPERATOR_NOP;
 819     op->precedence = eval_precedence(EVAL_OPERATOR_NOP);
 820     op->count = count;
 821     return op;
 822 }
 823
 824 static inline void eval_node_set_value_to_node(EVAL_NODE *op, int pos, EVAL_NODE *value) {
 825     if(pos >= op->count)
 826         fatal("Invalid request to set position %d of OPERAND that has only %d values", pos + 1, op->count + 1);
 827
 828     op->ops[pos].type = EVAL_VALUE_EXPRESSION;
 829     op->ops[pos].expression = value;
 830 }
 831
 832 static inline void eval_node_set_value_to_constant(EVAL_NODE *op, int pos, calculated_number value) {
 833     if(pos >= op->count)
 834         fatal("Invalid request to set position %d of OPERAND that has only %d values", pos + 1, op->count + 1);
 835
 836     op->ops[pos].type = EVAL_VALUE_NUMBER;
 837     op->ops[pos].number = value;
 838 }
 839
 840 static inline void eval_node_set_value_to_variable(EVAL_NODE *op, int pos, const char *variable) {
 841     if(pos >= op->count)
 842         fatal("Invalid request to set position %d of OPERAND that has only %d values", pos + 1, op->count + 1);
 843
 844     op->ops[pos].type = EVAL_VALUE_VARIABLE;
 845     op->ops[pos].variable = callocz(1, sizeof(EVAL_VARIABLE));
 846     op->ops[pos].variable->name = strdupz(variable);
 847     op->ops[pos].variable->hash = simple_hash(op->ops[pos].variable->name);
 848 }
 849
 850 static inline void eval_variable_free(EVAL_VARIABLE *v) {
 851     freez(v->name);
 852     freez(v);
 853 }
 854
 855 static inline void eval_value_free(EVAL_VALUE *v) {
 856     switch(v->type) {
 857         case EVAL_VALUE_EXPRESSION:
 858             eval_node_free(v->expression);
 859             break;
 860
 861         case EVAL_VALUE_VARIABLE:
 862             eval_variable_free(v->variable);
 863             break;
 864
 865         default:
 866             break;
 867     }
 868 }
 869
 870 static inline void eval_node_free(EVAL_NODE *op) {
 871     if(op->count) {
 872         int i;
 873         for(i = op->count - 1; i >= 0 ;i--)
 874             eval_value_free(&op->ops[i]);
 875     }
 876
 877     freez(op);
 878 }
 879
 880 // ----------------------------------------------------------------------------
 881 // the parsing logic
 882
 883 // helper function to avoid allocations all over the place
 884 static inline EVAL_NODE *parse_next_operand_given_its_operator(const char **string, unsigned char operator_type, int *error) {
 885     EVAL_NODE *sub = parse_one_full_operand(string, error);
 886     if(!sub) return NULL;
 887
 888     EVAL_NODE *op = eval_node_alloc(1);
 889     op->operator = operator_type;
 890     eval_node_set_value_to_node(op, 0, sub);
 891     return op;
 892 }
 893
 894 // parse a full operand, including its sign or other associative operator (e.g. NOT)
 895 static inline EVAL_NODE *parse_one_full_operand(const char **string, int *error) {
 896     char variable_buffer[EVAL_MAX_VARIABLE_NAME_LENGTH + 1];
 897     EVAL_NODE *op1 = NULL;
 898     calculated_number number;
 899
 900     *error = EVAL_ERROR_OK;
 901
 902     skip_spaces(string);
 903     if(!(**string)) {
 904         *error = EVAL_ERROR_MISSING_OPERAND;
 905         return NULL;
 906     }
 907
 908     if(parse_not(string)) {
 909         op1 = parse_next_operand_given_its_operator(string, EVAL_OPERATOR_NOT, error);
 910         op1->precedence = eval_precedence(EVAL_OPERATOR_NOT);
 911     }
 912     else if(parse_plus(string)) {
 913         op1 = parse_next_operand_given_its_operator(string, EVAL_OPERATOR_SIGN_PLUS, error);
 914         op1->precedence = eval_precedence(EVAL_OPERATOR_SIGN_PLUS);
 915     }
 916     else if(parse_minus(string)) {
 917         op1 = parse_next_operand_given_its_operator(string, EVAL_OPERATOR_SIGN_MINUS, error);
 918         op1->precedence = eval_precedence(EVAL_OPERATOR_SIGN_MINUS);
 919     }
 920     else if(parse_abs(string)) {
 921         op1 = parse_next_operand_given_its_operator(string, EVAL_OPERATOR_ABS, error);
 922         op1->precedence = eval_precedence(EVAL_OPERATOR_ABS);
 923     }
 924     else if(parse_open_subexpression(string)) {
 925         EVAL_NODE *sub = parse_full_expression(string, error);
 926         if(sub) {
 927             op1 = eval_node_alloc(1);
 928             op1->operator = EVAL_OPERATOR_EXPRESSION_OPEN;
 929             op1->precedence = eval_precedence(EVAL_OPERATOR_EXPRESSION_OPEN);
 930             eval_node_set_value_to_node(op1, 0, sub);
 931             if(!parse_close_subexpression(string)) {
 932                 *error = EVAL_ERROR_MISSING_CLOSE_SUBEXPRESSION;
 933                 eval_node_free(op1);
 934                 return NULL;
 935             }
 936         }
 937     }
 938     else if(parse_variable(string, variable_buffer, EVAL_MAX_VARIABLE_NAME_LENGTH)) {
 939         op1 = eval_node_alloc(1);
 940         op1->operator = EVAL_OPERATOR_NOP;
 941         eval_node_set_value_to_variable(op1, 0, variable_buffer);
 942     }
 943     else if(parse_constant(string, &number)) {
 944         op1 = eval_node_alloc(1);
 945         op1->operator = EVAL_OPERATOR_NOP;
 946         eval_node_set_value_to_constant(op1, 0, number);
 947     }
 948     else if(**string)
 949         *error = EVAL_ERROR_UNKNOWN_OPERAND;
 950     else
 951         *error = EVAL_ERROR_MISSING_OPERAND;
 952
 953     return op1;
 954 }
 955
 956 // parse an operator and the rest of the expression
 957 // precedence processing is handled here
 958 static inline EVAL_NODE *parse_rest_of_expression(const char **string, int *error, EVAL_NODE *op1) {
 959     EVAL_NODE *op2 = NULL;
 960     unsigned char operator;
 961     int precedence;
 962
 963     operator = parse_operator(string, &precedence);
 964     skip_spaces(string);
 965
 966     if(operator != EVAL_OPERATOR_NOP) {
 967         op2 = parse_one_full_operand(string, error);
 968         if(!op2) {
 969             // error is already reported
 970             eval_node_free(op1);
 971             return NULL;
 972         }
 973
 974         EVAL_NODE *op = eval_node_alloc(operators[operator].parameters);
 975         op->operator = operator;
 976         op->precedence = precedence;
 977
 978         if(operator == EVAL_OPERATOR_IF_THEN_ELSE && op->count == 3) {
 979             skip_spaces(string);
 980
 981             if(**string != ':') {
 982                 eval_node_free(op);
 983                 eval_node_free(op1);
 984                 eval_node_free(op2);
 985                 *error = EVAL_ERROR_IF_THEN_ELSE_MISSING_ELSE;
 986                 return NULL;
 987             }
 988             (*string)++;
 989
 990             skip_spaces(string);
 991
 992             EVAL_NODE *op3 = parse_one_full_operand(string, error);
 993             if(!op3) {
 994                 eval_node_free(op);
 995                 eval_node_free(op1);
 996                 eval_node_free(op2);
 997                 // error is already reported
 998                 return NULL;
 999             }
1000
1001             eval_node_set_value_to_node(op, 2, op3);
1002         }
1003
1004         eval_node_set_value_to_node(op, 1, op2);
1005
1006         // precedence processing
1007         // if this operator has a higher precedence compared to its next
1008         // put the next operator on top of us (top = evaluated later)
1009         // function recursion does the rest...
1010         if(op->precedence > op1->precedence && op1->count == 2 && op1->operator != '(' && op1->ops[1].type == EVAL_VALUE_EXPRESSION) {
1011             eval_node_set_value_to_node(op, 0, op1->ops[1].expression);
1012             op1->ops[1].expression = op;
1013             op = op1;
1014         }
1015         else
1016             eval_node_set_value_to_node(op, 0, op1);
1017
1018         return parse_rest_of_expression(string, error, op);
1019     }
1020     else if(**string == ')') {
1021         ;
1022     }
1023     else if(**string) {
1024         eval_node_free(op1);
1025         op1 = NULL;
1026         *error = EVAL_ERROR_MISSING_OPERATOR;
1027     }
1028
1029     return op1;
1030 }
1031
1032 // high level function to parse an expression or a sub-expression
1033 static inline EVAL_NODE *parse_full_expression(const char **string, int *error) {
1034     EVAL_NODE *op1 = parse_one_full_operand(string, error);
1035     if(!op1) {
1036         *error = EVAL_ERROR_MISSING_OPERAND;
1037         return NULL;
1038     }
1039
1040     return parse_rest_of_expression(string, error, op1);
1041 }
1042
1043 // ----------------------------------------------------------------------------
1044 // public API
1045
1046 int expression_evaluate(EVAL_EXPRESSION *exp) {
1047     exp->error = EVAL_ERROR_OK;
1048
1049     buffer_reset(exp->error_msg);
1050     exp->result = eval_node(exp, (EVAL_NODE *)exp->nodes, &exp->error);
1051
1052     if(unlikely(isnan(exp->result))) {
1053         if(exp->error == EVAL_ERROR_OK)
1054             exp->error = EVAL_ERROR_VALUE_IS_NAN;
1055     }
1056     else if(unlikely(isinf(exp->result))) {
1057         if(exp->error == EVAL_ERROR_OK)
1058             exp->error = EVAL_ERROR_VALUE_IS_INFINITE;
1059     }
1060     else if(unlikely(exp->error == EVAL_ERROR_UNKNOWN_VARIABLE)) {
1061         // although there is an unknown variable
1062         // the expression was evaluated successfully
1063         exp->error = EVAL_ERROR_OK;
1064     }
1065
1066     if(exp->error != EVAL_ERROR_OK) {
1067         exp->result = NAN;
1068
1069         if(buffer_strlen(exp->error_msg))
1070             buffer_strcat(exp->error_msg, "; ");
1071
1072         buffer_sprintf(exp->error_msg, "failed to evaluate expression with error %d (%s)", exp->error, expression_strerror(exp->error));
1073         return 0;
1074     }
1075
1076     return 1;
1077 }
1078
1079 EVAL_EXPRESSION *expression_parse(const char *string, const char **failed_at, int *error) {
1080     const char *s = string;
1081     int err = EVAL_ERROR_OK;
1082
1083     EVAL_NODE *op = parse_full_expression(&s, &err);
1084
1085     if(*s) {
1086         if(op) {
1087             eval_node_free(op);
1088             op = NULL;
1089         }
1090         err = EVAL_ERROR_REMAINING_GARBAGE;
1091     }
1092
1093     if (failed_at) *failed_at = s;
1094     if (error) *error = err;
1095
1096     if(!op) {
1097         unsigned long pos = s - string + 1;
1098         error("failed to parse expression '%s': %s at character %lu (i.e.: '%s').", string, expression_strerror(err), pos, s);
1099         return NULL;
1100     }
1101
1102     BUFFER *out = buffer_create(1024);
1103     print_parsed_as_node(out, op, &err);
1104     if(err != EVAL_ERROR_OK) {
1105         error("failed to re-generate expression '%s' with reason: %s", string, expression_strerror(err));
1106         eval_node_free(op);
1107         buffer_free(out);
1108         return NULL;
1109     }
1110
1111     EVAL_EXPRESSION *exp = callocz(1, sizeof(EVAL_EXPRESSION));
1112
1113     exp->source = strdupz(string);
1114     exp->parsed_as = strdupz(buffer_tostring(out));
1115     buffer_free(out);
1116
1117     exp->error_msg = buffer_create(100);
1118     exp->nodes = (void *)op;
1119
1120     return exp;
1121 }
1122
1123 void expression_free(EVAL_EXPRESSION *exp) {
1124     if(!exp) return;
1125
1126     if(exp->nodes) eval_node_free((EVAL_NODE *)exp->nodes);
1127     freez((void *)exp->source);
1128     freez((void *)exp->parsed_as);
1129     buffer_free(exp->error_msg);
1130     freez(exp);
1131 }
1132
1133 const char *expression_strerror(int error) {
1134     switch(error) {
1135         case EVAL_ERROR_OK:
1136             return "success";
1137
1138         case EVAL_ERROR_MISSING_CLOSE_SUBEXPRESSION:
1139             return "missing closing parenthesis";
1140
1141         case EVAL_ERROR_UNKNOWN_OPERAND:
1142             return "unknown operand";
1143
1144         case EVAL_ERROR_MISSING_OPERAND:
1145             return "expected operand";
1146
1147         case EVAL_ERROR_MISSING_OPERATOR:
1148             return "expected operator";
1149
1150         case EVAL_ERROR_REMAINING_GARBAGE:
1151             return "remaining characters after expression";
1152
1153         case EVAL_ERROR_INVALID_VALUE:
1154             return "invalid value structure - internal error";
1155
1156         case EVAL_ERROR_INVALID_NUMBER_OF_OPERANDS:
1157             return "wrong number of operands for operation - internal error";
1158
1159         case EVAL_ERROR_VALUE_IS_NAN:
1160             return "value is unset";
1161
1162         case EVAL_ERROR_VALUE_IS_INFINITE:
1163             return "computed value is infinite";
1164
1165         case EVAL_ERROR_UNKNOWN_VARIABLE:
1166             return "undefined variable";
1167
1168         case EVAL_ERROR_IF_THEN_ELSE_MISSING_ELSE:
1169             return "missing second sub-expression of inline conditional";
1170
1171         default:
1172             return "unknown error";
1173     }
1174 }