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
  47 // ----------------------------------------------------------------------------
  48 // forward function definitions
  49
  50 static inline void eval_node_free(EVAL_NODE *op);
  51 static inline EVAL_NODE *parse_full_expression(const char **string, int *error);
  52 static inline EVAL_NODE *parse_one_full_operand(const char **string, int *error);
  53 static inline calculated_number eval_node(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error);
  54 static inline void print_parsed_as_node(BUFFER *out, EVAL_NODE *op, int *error);
  55 static inline void print_parsed_as_constant(BUFFER *out, calculated_number n);
  56
  57 // ----------------------------------------------------------------------------
  58 // evaluation of expressions
  59
  60 static inline calculated_number eval_check_number(calculated_number n, int *error) {
  61     if(unlikely(isnan(n))) {
  62         *error = EVAL_ERROR_VALUE_IS_NAN;
  63         return 0;
  64     }
  65
  66     if(unlikely(isinf(n))) {
  67         *error = EVAL_ERROR_VALUE_IS_INFINITE;
  68         return 0;
  69     }
  70
  71     return n;
  72 }
  73
  74 static inline calculated_number eval_variable(EVAL_EXPRESSION *exp, EVAL_VARIABLE *v, int *error) {
  75     static uint32_t this_hash = 0;
  76
  77     if(unlikely(this_hash == 0))
  78         this_hash = simple_hash("this");
  79
  80     if(exp->this && v->hash == this_hash && !strcmp(v->name, "this")) {
  81         buffer_strcat(exp->error_msg, "[ $this = ");
  82         print_parsed_as_constant(exp->error_msg, *exp->this);
  83         buffer_strcat(exp->error_msg, " ] ");
  84         return *exp->this;
  85     }
  86
  87     calculated_number n;
  88     if(exp->rrdcalc && health_variable_lookup(v->name, v->hash, exp->rrdcalc, &n)) {
  89         buffer_sprintf(exp->error_msg, "[ $%s = ", v->name);
  90         print_parsed_as_constant(exp->error_msg, n);
  91         buffer_strcat(exp->error_msg, " ] ");
  92         return n;
  93     }
  94
  95     *error = EVAL_ERROR_UNKNOWN_VARIABLE;
  96     buffer_sprintf(exp->error_msg, "unknown variable '%s'", v->name);
  97     return 0;
  98 }
  99
 100 static inline calculated_number eval_value(EVAL_EXPRESSION *exp, EVAL_VALUE *v, int *error) {
 101     calculated_number n;
 102
 103     switch(v->type) {
 104         case EVAL_VALUE_EXPRESSION:
 105             n = eval_node(exp, v->expression, error);
 106             break;
 107
 108         case EVAL_VALUE_NUMBER:
 109             n = v->number;
 110             break;
 111
 112         case EVAL_VALUE_VARIABLE:
 113             n = eval_variable(exp, v->variable, error);
 114             break;
 115
 116         default:
 117             *error = EVAL_ERROR_INVALID_VALUE;
 118             n = 0;
 119             break;
 120     }
 121
 122     return eval_check_number(n, error);
 123 }
 124
 125 calculated_number eval_and(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error) {
 126     return eval_value(exp, &op->ops[0], error) && eval_value(exp, &op->ops[1], error);
 127 }
 128 calculated_number eval_or(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error) {
 129     return eval_value(exp, &op->ops[0], error) || eval_value(exp, &op->ops[1], error);
 130 }
 131 calculated_number eval_greater_than_or_equal(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error) {
 132     return eval_value(exp, &op->ops[0], error) >= eval_value(exp, &op->ops[1], error);
 133 }
 134 calculated_number eval_less_than_or_equal(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error) {
 135     return eval_value(exp, &op->ops[0], error) <= eval_value(exp, &op->ops[1], error);
 136 }
 137 calculated_number eval_not_equal(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error) {
 138     return eval_value(exp, &op->ops[0], error) != eval_value(exp, &op->ops[1], error);
 139 }
 140 calculated_number eval_equal(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error) {
 141     return eval_value(exp, &op->ops[0], error) == eval_value(exp, &op->ops[1], error);
 142 }
 143 calculated_number eval_less(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error) {
 144     return eval_value(exp, &op->ops[0], error) < eval_value(exp, &op->ops[1], error);
 145 }
 146 calculated_number eval_greater(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error) {
 147     return eval_value(exp, &op->ops[0], error) > eval_value(exp, &op->ops[1], error);
 148 }
 149 calculated_number eval_plus(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error) {
 150     return eval_value(exp, &op->ops[0], error) + eval_value(exp, &op->ops[1], error);
 151 }
 152 calculated_number eval_minus(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error) {
 153     return eval_value(exp, &op->ops[0], error) - eval_value(exp, &op->ops[1], error);
 154 }
 155 calculated_number eval_multiply(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error) {
 156     return eval_value(exp, &op->ops[0], error) * eval_value(exp, &op->ops[1], error);
 157 }
 158 calculated_number eval_divide(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error) {
 159     return eval_value(exp, &op->ops[0], error) / eval_value(exp, &op->ops[1], error);
 160 }
 161 calculated_number eval_nop(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error) {
 162     return eval_value(exp, &op->ops[0], error);
 163 }
 164 calculated_number eval_not(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error) {
 165     return !eval_value(exp, &op->ops[0], error);
 166 }
 167 calculated_number eval_sign_plus(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error) {
 168     return eval_value(exp, &op->ops[0], error);
 169 }
 170 calculated_number eval_sign_minus(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error) {
 171     return -eval_value(exp, &op->ops[0], error);
 172 }
 173
 174 static struct operator {
 175     const char *print_as;
 176     char precedence;
 177     char parameters;
 178     calculated_number (*eval)(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error);
 179 } operators[256] = {
 180         // this is a random access array
 181         // we always access it with a known EVAL_OPERATOR_X
 182
 183         [EVAL_OPERATOR_AND]                   = { "&&", 2, 2, eval_and },
 184         [EVAL_OPERATOR_OR]                    = { "||", 2, 2, eval_or },
 185         [EVAL_OPERATOR_GREATER_THAN_OR_EQUAL] = { ">=", 3, 2, eval_greater_than_or_equal },
 186         [EVAL_OPERATOR_LESS_THAN_OR_EQUAL]    = { "<=", 3, 2, eval_less_than_or_equal },
 187         [EVAL_OPERATOR_NOT_EQUAL]             = { "!=", 3, 2, eval_not_equal },
 188         [EVAL_OPERATOR_EQUAL]                 = { "==", 3, 2, eval_equal },
 189         [EVAL_OPERATOR_LESS]                  = { "<",  3, 2, eval_less },
 190         [EVAL_OPERATOR_GREATER]               = { ">",  3, 2, eval_greater },
 191         [EVAL_OPERATOR_PLUS]                  = { "+",  4, 2, eval_plus },
 192         [EVAL_OPERATOR_MINUS]                 = { "-",  4, 2, eval_minus },
 193         [EVAL_OPERATOR_MULTIPLY]              = { "*",  5, 2, eval_multiply },
 194         [EVAL_OPERATOR_DIVIDE]                = { "/",  5, 2, eval_divide },
 195         [EVAL_OPERATOR_NOT]                   = { "!",  6, 1, eval_not },
 196         [EVAL_OPERATOR_SIGN_PLUS]             = { "+",  6, 1, eval_sign_plus },
 197         [EVAL_OPERATOR_SIGN_MINUS]            = { "-",  6, 1, eval_sign_minus },
 198         [EVAL_OPERATOR_NOP]                   = { NULL, 7, 1, eval_nop },
 199         [EVAL_OPERATOR_EXPRESSION_OPEN]       = { NULL, 7, 1, eval_nop },
 200
 201         // this should exist in our evaluation list
 202         [EVAL_OPERATOR_EXPRESSION_CLOSE]      = { NULL, 7, 1, eval_nop }
 203 };
 204
 205 #define eval_precedence(operator) (operators[(unsigned char)(operator)].precedence)
 206
 207 static inline calculated_number eval_node(EVAL_EXPRESSION *exp, EVAL_NODE *op, int *error) {
 208     if(unlikely(op->count != operators[op->operator].parameters)) {
 209         *error = EVAL_ERROR_INVALID_NUMBER_OF_OPERANDS;
 210         return 0;
 211     }
 212
 213     calculated_number n = operators[op->operator].eval(exp, op, error);
 214
 215     return eval_check_number(n, error);
 216 }
 217
 218 // ----------------------------------------------------------------------------
 219 // parsed-as generation
 220
 221 static inline void print_parsed_as_variable(BUFFER *out, EVAL_VARIABLE *v, int *error) {
 222     (void)error;
 223     buffer_sprintf(out, "$%s", v->name);
 224 }
 225
 226 static inline void print_parsed_as_constant(BUFFER *out, calculated_number n) {
 227     if(unlikely(isnan(n))) {
 228         buffer_strcat(out, "NaN");
 229         return;
 230     }
 231
 232     if(unlikely(isinf(n))) {
 233         buffer_strcat(out, "INFINITE");
 234         return;
 235     }
 236
 237     char b[100+1], *s;
 238     snprintfz(b, 100, CALCULATED_NUMBER_FORMAT, n);
 239
 240     s = &b[strlen(b) - 1];
 241     while(s > b && *s == '0') {
 242         *s ='\0';
 243         s--;
 244     }
 245
 246     if(s > b && *s == '.')
 247         *s = '\0';
 248
 249     buffer_strcat(out, b);
 250 }
 251
 252 static inline void print_parsed_as_value(BUFFER *out, EVAL_VALUE *v, int *error) {
 253     switch(v->type) {
 254         case EVAL_VALUE_EXPRESSION:
 255             print_parsed_as_node(out, v->expression, error);
 256             break;
 257
 258         case EVAL_VALUE_NUMBER:
 259             print_parsed_as_constant(out, v->number);
 260             break;
 261
 262         case EVAL_VALUE_VARIABLE:
 263             print_parsed_as_variable(out, v->variable, error);
 264             break;
 265
 266         default:
 267             *error = EVAL_ERROR_INVALID_VALUE;
 268             break;
 269     }
 270 }
 271
 272 static inline void print_parsed_as_node(BUFFER *out, EVAL_NODE *op, int *error) {
 273     if(unlikely(op->count != operators[op->operator].parameters)) {
 274         *error = EVAL_ERROR_INVALID_NUMBER_OF_OPERANDS;
 275         return;
 276     }
 277
 278     if(operators[op->operator].parameters == 1) {
 279
 280         if(operators[op->operator].print_as)
 281             buffer_sprintf(out, "%s", operators[op->operator].print_as);
 282
 283         //if(op->operator == EVAL_OPERATOR_EXPRESSION_OPEN)
 284         //    buffer_strcat(out, "(");
 285
 286         print_parsed_as_value(out, &op->ops[0], error);
 287
 288         //if(op->operator == EVAL_OPERATOR_EXPRESSION_OPEN)
 289         //    buffer_strcat(out, ")");
 290     }
 291
 292     else if(operators[op->operator].parameters == 2) {
 293         buffer_strcat(out, "(");
 294         print_parsed_as_value(out, &op->ops[0], error);
 295
 296         if(operators[op->operator].print_as)
 297             buffer_sprintf(out, " %s ", operators[op->operator].print_as);
 298
 299         print_parsed_as_value(out, &op->ops[1], error);
 300         buffer_strcat(out, ")");
 301     }
 302 }
 303
 304 // ----------------------------------------------------------------------------
 305 // parsing expressions
 306
 307 // skip spaces
 308 static inline void skip_spaces(const char **string) {
 309     const char *s = *string;
 310     while(isspace(*s)) s++;
 311     *string = s;
 312 }
 313
 314 // what character can appear just after an operator keyword
 315 // like NOT AND OR ?
 316 static inline int isoperatorterm_word(const char s) {
 317     if(isspace(s) || s == '(' || s == '$' || s == '!' || s == '-' || s == '+' || isdigit(s) || !s)
 318         return 1;
 319
 320     return 0;
 321 }
 322
 323 // what character can appear just after an operator symbol?
 324 static inline int isoperatorterm_symbol(const char s) {
 325     if(isoperatorterm_word(s) || isalpha(s))
 326         return 1;
 327
 328     return 0;
 329 }
 330
 331 // return 1 if the character should never appear in a variable
 332 static inline int isvariableterm(const char s) {
 333     if(isalnum(s) || s == '.' || s == '_')
 334         return 0;
 335
 336     return 1;
 337 }
 338
 339 // ----------------------------------------------------------------------------
 340 // parse operators
 341
 342 static inline int parse_and(const char **string) {
 343     const char *s = *string;
 344
 345     // AND
 346     if((s[0] == 'A' || s[0] == 'a') && (s[1] == 'N' || s[1] == 'n') && (s[2] == 'D' || s[2] == 'd') && isoperatorterm_word(s[3])) {
 347         *string = &s[4];
 348         return 1;
 349     }
 350
 351     // &&
 352     if(s[0] == '&' && s[1] == '&' && isoperatorterm_symbol(s[2])) {
 353         *string = &s[2];
 354         return 1;
 355     }
 356
 357     return 0;
 358 }
 359
 360 static inline int parse_or(const char **string) {
 361     const char *s = *string;
 362
 363     // OR
 364     if((s[0] == 'O' || s[0] == 'o') && (s[1] == 'R' || s[1] == 'r') && isoperatorterm_word(s[2])) {
 365         *string = &s[3];
 366         return 1;
 367     }
 368
 369     // ||
 370     if(s[0] == '|' && s[1] == '|' && isoperatorterm_symbol(s[2])) {
 371         *string = &s[2];
 372         return 1;
 373     }
 374
 375     return 0;
 376 }
 377
 378 static inline int parse_greater_than_or_equal(const char **string) {
 379     const char *s = *string;
 380
 381     // >=
 382     if(s[0] == '>' && s[1] == '=' && isoperatorterm_symbol(s[2])) {
 383         *string = &s[2];
 384         return 1;
 385     }
 386
 387     return 0;
 388 }
 389
 390 static inline int parse_less_than_or_equal(const char **string) {
 391     const char *s = *string;
 392
 393     // <=
 394     if (s[0] == '<' && s[1] == '=' && isoperatorterm_symbol(s[2])) {
 395         *string = &s[2];
 396         return 1;
 397     }
 398
 399     return 0;
 400 }
 401
 402 static inline int parse_greater(const char **string) {
 403     const char *s = *string;
 404
 405     // >
 406     if(s[0] == '>' && isoperatorterm_symbol(s[1])) {
 407         *string = &s[1];
 408         return 1;
 409     }
 410
 411     return 0;
 412 }
 413
 414 static inline int parse_less(const char **string) {
 415     const char *s = *string;
 416
 417     // <
 418     if(s[0] == '<' && isoperatorterm_symbol(s[1])) {
 419         *string = &s[1];
 420         return 1;
 421     }
 422
 423     return 0;
 424 }
 425
 426 static inline int parse_equal(const char **string) {
 427     const char *s = *string;
 428
 429     // ==
 430     if(s[0] == '=' && s[1] == '=' && isoperatorterm_symbol(s[2])) {
 431         *string = &s[2];
 432         return 1;
 433     }
 434
 435     // =
 436     if(s[0] == '=' && isoperatorterm_symbol(s[1])) {
 437         *string = &s[1];
 438         return 1;
 439     }
 440
 441     return 0;
 442 }
 443
 444 static inline int parse_not_equal(const char **string) {
 445     const char *s = *string;
 446
 447     // !=
 448     if(s[0] == '!' && s[1] == '=' && isoperatorterm_symbol(s[2])) {
 449         *string = &s[2];
 450         return 1;
 451     }
 452
 453     // <>
 454     if(s[0] == '<' && s[1] == '>' && isoperatorterm_symbol(s[2])) {
 455         *string = &s[2];
 456     }
 457
 458     return 0;
 459 }
 460
 461 static inline int parse_not(const char **string) {
 462     const char *s = *string;
 463
 464     // NOT
 465     if((s[0] == 'N' || s[0] == 'n') && (s[1] == 'O' || s[1] == 'o') && (s[2] == 'T' || s[2] == 't') && isoperatorterm_word(s[3])) {
 466         *string = &s[3];
 467         return 1;
 468     }
 469
 470     if(s[0] == '!') {
 471         *string = &s[1];
 472         return 1;
 473     }
 474
 475     return 0;
 476 }
 477
 478 static inline int parse_multiply(const char **string) {
 479     const char *s = *string;
 480
 481     // *
 482     if(s[0] == '*' && isoperatorterm_symbol(s[1])) {
 483         *string = &s[1];
 484         return 1;
 485     }
 486
 487     return 0;
 488 }
 489
 490 static inline int parse_divide(const char **string) {
 491     const char *s = *string;
 492
 493     // /
 494     if(s[0] == '/' && isoperatorterm_symbol(s[1])) {
 495         *string = &s[1];
 496         return 1;
 497     }
 498
 499     return 0;
 500 }
 501
 502 static inline int parse_minus(const char **string) {
 503     const char *s = *string;
 504
 505     // -
 506     if(s[0] == '-' && isoperatorterm_symbol(s[1])) {
 507         *string = &s[1];
 508         return 1;
 509     }
 510
 511     return 0;
 512 }
 513
 514 static inline int parse_plus(const char **string) {
 515     const char *s = *string;
 516
 517     // +
 518     if(s[0] == '+' && isoperatorterm_symbol(s[1])) {
 519         *string = &s[1];
 520         return 1;
 521     }
 522
 523     return 0;
 524 }
 525
 526 static inline int parse_open_subexpression(const char **string) {
 527     const char *s = *string;
 528
 529     // (
 530     if(s[0] == '(') {
 531         *string = &s[1];
 532         return 1;
 533     }
 534
 535     return 0;
 536 }
 537
 538 static inline int parse_close_subexpression(const char **string) {
 539     const char *s = *string;
 540
 541     // (
 542     if(s[0] == ')') {
 543         *string = &s[1];
 544         return 1;
 545     }
 546
 547     return 0;
 548 }
 549
 550 static inline int parse_variable(const char **string, char *buffer, size_t len) {
 551     const char *s = *string;
 552
 553     // $
 554     if(s[0] == '$') {
 555         size_t i = 0;
 556         s++;
 557
 558         while(*s && !isvariableterm(*s) && i < len)
 559             buffer[i++] = *s++;
 560
 561         buffer[i] = '\0';
 562
 563         if(buffer[0]) {
 564             *string = &s[0];
 565             return 1;
 566         }
 567     }
 568
 569     return 0;
 570 }
 571
 572 static inline int parse_constant(const char **string, calculated_number *number) {
 573     char *end = NULL;
 574     calculated_number n = strtold(*string, &end);
 575     if(unlikely(!end || *string == end || isnan(n) || isinf(n))) {
 576         *number = 0;
 577         return 0;
 578     }
 579     *number = n;
 580     *string = end;
 581     return 1;
 582 }
 583
 584 static struct operator_parser {
 585     unsigned char id;
 586     int (*parse)(const char **);
 587 } operator_parsers[] = {
 588         // the order in this list is important!
 589         // the first matching will be used
 590         // so place the longer of overlapping ones
 591         // at the top
 592
 593         { EVAL_OPERATOR_AND,                   parse_and },
 594         { EVAL_OPERATOR_OR,                    parse_or },
 595         { EVAL_OPERATOR_GREATER_THAN_OR_EQUAL, parse_greater_than_or_equal },
 596         { EVAL_OPERATOR_LESS_THAN_OR_EQUAL,    parse_less_than_or_equal },
 597         { EVAL_OPERATOR_NOT_EQUAL,             parse_not_equal },
 598         { EVAL_OPERATOR_EQUAL,                 parse_equal },
 599         { EVAL_OPERATOR_LESS,                  parse_less },
 600         { EVAL_OPERATOR_GREATER,               parse_greater },
 601         { EVAL_OPERATOR_PLUS,                  parse_plus },
 602         { EVAL_OPERATOR_MINUS,                 parse_minus },
 603         { EVAL_OPERATOR_MULTIPLY,              parse_multiply },
 604         { EVAL_OPERATOR_DIVIDE,                parse_divide },
 605
 606         /* we should not put in this list the following:
 607          *
 608          *  - NOT
 609          *  - (
 610          *  - )
 611          *
 612          * these are handled in code
 613          */
 614
 615         // termination
 616         { EVAL_OPERATOR_NOP, NULL }
 617 };
 618
 619 static inline unsigned char parse_operator(const char **string, int *precedence) {
 620     skip_spaces(string);
 621
 622     int i;
 623     for(i = 0 ; operator_parsers[i].parse != NULL ; i++)
 624         if(operator_parsers[i].parse(string)) {
 625             if(precedence) *precedence = eval_precedence(operator_parsers[i].id);
 626             return operator_parsers[i].id;
 627         }
 628
 629     return EVAL_OPERATOR_NOP;
 630 }
 631
 632 // ----------------------------------------------------------------------------
 633 // memory management
 634
 635 static inline EVAL_NODE *eval_node_alloc(int count) {
 636     static int id = 1;
 637
 638     EVAL_NODE *op = callocz(1, sizeof(EVAL_NODE) + (sizeof(EVAL_VALUE) * count));
 639
 640     op->id = id++;
 641     op->operator = EVAL_OPERATOR_NOP;
 642     op->precedence = eval_precedence(EVAL_OPERATOR_NOP);
 643     op->count = count;
 644     return op;
 645 }
 646
 647 static inline void eval_node_set_value_to_node(EVAL_NODE *op, int pos, EVAL_NODE *value) {
 648     if(pos >= op->count)
 649         fatal("Invalid request to set position %d of OPERAND that has only %d values", pos + 1, op->count + 1);
 650
 651     op->ops[pos].type = EVAL_VALUE_EXPRESSION;
 652     op->ops[pos].expression = value;
 653 }
 654
 655 static inline void eval_node_set_value_to_constant(EVAL_NODE *op, int pos, calculated_number value) {
 656     if(pos >= op->count)
 657         fatal("Invalid request to set position %d of OPERAND that has only %d values", pos + 1, op->count + 1);
 658
 659     op->ops[pos].type = EVAL_VALUE_NUMBER;
 660     op->ops[pos].number = value;
 661 }
 662
 663 static inline void eval_node_set_value_to_variable(EVAL_NODE *op, int pos, const char *variable) {
 664     if(pos >= op->count)
 665         fatal("Invalid request to set position %d of OPERAND that has only %d values", pos + 1, op->count + 1);
 666
 667     op->ops[pos].type = EVAL_VALUE_VARIABLE;
 668     op->ops[pos].variable = callocz(1, sizeof(EVAL_VARIABLE));
 669     op->ops[pos].variable->name = strdupz(variable);
 670     op->ops[pos].variable->hash = simple_hash(op->ops[pos].variable->name);
 671 }
 672
 673 static inline void eval_variable_free(EVAL_VARIABLE *v) {
 674     freez(v->name);
 675     freez(v);
 676 }
 677
 678 static inline void eval_value_free(EVAL_VALUE *v) {
 679     switch(v->type) {
 680         case EVAL_VALUE_EXPRESSION:
 681             eval_node_free(v->expression);
 682             break;
 683
 684         case EVAL_VALUE_VARIABLE:
 685             eval_variable_free(v->variable);
 686             break;
 687
 688         default:
 689             break;
 690     }
 691 }
 692
 693 static inline void eval_node_free(EVAL_NODE *op) {
 694     if(op->count) {
 695         int i;
 696         for(i = op->count - 1; i >= 0 ;i--)
 697             eval_value_free(&op->ops[i]);
 698     }
 699
 700     freez(op);
 701 }
 702
 703 // ----------------------------------------------------------------------------
 704 // the parsing logic
 705
 706 // helper function to avoid allocations all over the place
 707 static inline EVAL_NODE *parse_next_operand_given_its_operator(const char **string, unsigned char operator_type, int *error) {
 708     EVAL_NODE *sub = parse_one_full_operand(string, error);
 709     if(!sub) return NULL;
 710
 711     EVAL_NODE *op = eval_node_alloc(1);
 712     op->operator = operator_type;
 713     eval_node_set_value_to_node(op, 0, sub);
 714     return op;
 715 }
 716
 717 // parse a full operand, including its sign or other associative operator (e.g. NOT)
 718 static inline EVAL_NODE *parse_one_full_operand(const char **string, int *error) {
 719     char variable_buffer[EVAL_MAX_VARIABLE_NAME_LENGTH + 1];
 720     EVAL_NODE *op1 = NULL;
 721     calculated_number number;
 722
 723     *error = EVAL_ERROR_OK;
 724
 725     skip_spaces(string);
 726     if(!(**string)) {
 727         *error = EVAL_ERROR_MISSING_OPERAND;
 728         return NULL;
 729     }
 730
 731     if(parse_not(string)) {
 732         op1 = parse_next_operand_given_its_operator(string, EVAL_OPERATOR_NOT, error);
 733         op1->precedence = eval_precedence(EVAL_OPERATOR_NOT);
 734     }
 735     else if(parse_plus(string)) {
 736         op1 = parse_next_operand_given_its_operator(string, EVAL_OPERATOR_SIGN_PLUS, error);
 737         op1->precedence = eval_precedence(EVAL_OPERATOR_SIGN_PLUS);
 738     }
 739     else if(parse_minus(string)) {
 740         op1 = parse_next_operand_given_its_operator(string, EVAL_OPERATOR_SIGN_MINUS, error);
 741         op1->precedence = eval_precedence(EVAL_OPERATOR_SIGN_MINUS);
 742     }
 743     else if(parse_open_subexpression(string)) {
 744         EVAL_NODE *sub = parse_full_expression(string, error);
 745         if(sub) {
 746             op1 = eval_node_alloc(1);
 747             op1->operator = EVAL_OPERATOR_EXPRESSION_OPEN;
 748             op1->precedence = eval_precedence(EVAL_OPERATOR_EXPRESSION_OPEN);
 749             eval_node_set_value_to_node(op1, 0, sub);
 750             if(!parse_close_subexpression(string)) {
 751                 *error = EVAL_ERROR_MISSING_CLOSE_SUBEXPRESSION;
 752                 eval_node_free(op1);
 753                 return NULL;
 754             }
 755         }
 756     }
 757     else if(parse_variable(string, variable_buffer, EVAL_MAX_VARIABLE_NAME_LENGTH)) {
 758         op1 = eval_node_alloc(1);
 759         op1->operator = EVAL_OPERATOR_NOP;
 760         eval_node_set_value_to_variable(op1, 0, variable_buffer);
 761     }
 762     else if(parse_constant(string, &number)) {
 763         op1 = eval_node_alloc(1);
 764         op1->operator = EVAL_OPERATOR_NOP;
 765         eval_node_set_value_to_constant(op1, 0, number);
 766     }
 767     else if(**string)
 768         *error = EVAL_ERROR_UNKNOWN_OPERAND;
 769     else
 770         *error = EVAL_ERROR_MISSING_OPERAND;
 771
 772     return op1;
 773 }
 774
 775 // parse an operator and the rest of the expression
 776 // precedence processing is handled here
 777 static inline EVAL_NODE *parse_rest_of_expression(const char **string, int *error, EVAL_NODE *op1) {
 778     EVAL_NODE *op2 = NULL;
 779     unsigned char operator;
 780     int precedence;
 781
 782     operator = parse_operator(string, &precedence);
 783     skip_spaces(string);
 784
 785     if(operator != EVAL_OPERATOR_NOP) {
 786         op2 = parse_one_full_operand(string, error);
 787         if(!op2) {
 788             // error is already reported
 789             eval_node_free(op1);
 790             return NULL;
 791         }
 792
 793         EVAL_NODE *op = eval_node_alloc(2);
 794         op->operator = operator;
 795         op->precedence = precedence;
 796
 797         eval_node_set_value_to_node(op, 1, op2);
 798
 799         // precedence processing
 800         // if this operator has a higher precedence compared to its next
 801         // put the next operator on top of us (top = evaluated later)
 802         // function recursion does the rest...
 803         if(op->precedence > op1->precedence && op1->count == 2 && op1->operator != '(' && op1->ops[1].type == EVAL_VALUE_EXPRESSION) {
 804             eval_node_set_value_to_node(op, 0, op1->ops[1].expression);
 805             op1->ops[1].expression = op;
 806             op = op1;
 807         }
 808         else
 809             eval_node_set_value_to_node(op, 0, op1);
 810
 811         return parse_rest_of_expression(string, error, op);
 812     }
 813     else if(**string == ')') {
 814         ;
 815     }
 816     else if(**string) {
 817         if(op1) eval_node_free(op1);
 818         op1 = NULL;
 819         *error = EVAL_ERROR_MISSING_OPERATOR;
 820     }
 821
 822     return op1;
 823 }
 824
 825 // high level function to parse an expression or a sub-expression
 826 static inline EVAL_NODE *parse_full_expression(const char **string, int *error) {
 827     EVAL_NODE *op1 = NULL;
 828
 829     op1 = parse_one_full_operand(string, error);
 830     if(!op1) {
 831         *error = EVAL_ERROR_MISSING_OPERAND;
 832         return NULL;
 833     }
 834
 835     return parse_rest_of_expression(string, error, op1);
 836 }
 837
 838 // ----------------------------------------------------------------------------
 839 // public API
 840
 841 int expression_evaluate(EVAL_EXPRESSION *exp) {
 842     exp->error = EVAL_ERROR_OK;
 843
 844     buffer_reset(exp->error_msg);
 845     exp->result = eval_node(exp, (EVAL_NODE *)exp->nodes, &exp->error);
 846
 847     if(exp->error != EVAL_ERROR_OK) {
 848         if(buffer_strlen(exp->error_msg))
 849             buffer_strcat(exp->error_msg, "; ");
 850
 851         buffer_sprintf(exp->error_msg, "failed to evaluate expression with error %d (%s)", exp->error, expression_strerror(exp->error));
 852         return 0;
 853     }
 854
 855     return 1;
 856 }
 857
 858 EVAL_EXPRESSION *expression_parse(const char *string, const char **failed_at, int *error) {
 859     const char *s = string;
 860     int err = EVAL_ERROR_OK;
 861     unsigned long pos = 0;
 862
 863     EVAL_NODE *op = parse_full_expression(&s, &err);
 864
 865     if(*s) {
 866         if(op) {
 867             eval_node_free(op);
 868             op = NULL;
 869         }
 870         err = EVAL_ERROR_REMAINING_GARBAGE;
 871     }
 872
 873     if (failed_at) *failed_at = s;
 874     if (error) *error = err;
 875
 876     if(!op) {
 877         pos = s - string + 1;
 878         error("failed to parse expression '%s': %s at character %lu (i.e.: '%s').", string, expression_strerror(err), pos, s);
 879         return NULL;
 880     }
 881
 882     BUFFER *out = buffer_create(1024);
 883     print_parsed_as_node(out, op, &err);
 884     if(err != EVAL_ERROR_OK) {
 885         error("failed to re-generate expression '%s' with reason: %s", string, expression_strerror(err));
 886         eval_node_free(op);
 887         buffer_free(out);
 888         return NULL;
 889     }
 890
 891     EVAL_EXPRESSION *exp = callocz(1, sizeof(EVAL_EXPRESSION));
 892
 893     exp->source = strdupz(string);
 894     exp->parsed_as = strdupz(buffer_tostring(out));
 895     buffer_free(out);
 896
 897     exp->error_msg = buffer_create(100);
 898     exp->nodes = (void *)op;
 899
 900     return exp;
 901 }
 902
 903 void expression_free(EVAL_EXPRESSION *exp) {
 904     if(!exp) return;
 905
 906     if(exp->nodes) eval_node_free((EVAL_NODE *)exp->nodes);
 907     freez((void *)exp->source);
 908     freez((void *)exp->parsed_as);
 909     buffer_free(exp->error_msg);
 910     freez(exp);
 911 }
 912
 913 const char *expression_strerror(int error) {
 914     switch(error) {
 915         case EVAL_ERROR_OK:
 916             return "success";
 917
 918         case EVAL_ERROR_MISSING_CLOSE_SUBEXPRESSION:
 919             return "missing closing parenthesis";
 920
 921         case EVAL_ERROR_UNKNOWN_OPERAND:
 922             return "unknown operand";
 923
 924         case EVAL_ERROR_MISSING_OPERAND:
 925             return "expected operand";
 926
 927         case EVAL_ERROR_MISSING_OPERATOR:
 928             return "expected operator";
 929
 930         case EVAL_ERROR_REMAINING_GARBAGE:
 931             return "remaining characters after expression";
 932
 933         case EVAL_ERROR_INVALID_VALUE:
 934             return "invalid value structure - internal error";
 935
 936         case EVAL_ERROR_INVALID_NUMBER_OF_OPERANDS:
 937             return "wrong number of operands for operation - internal error";
 938
 939         case EVAL_ERROR_VALUE_IS_NAN:
 940             return "value is unset";
 941
 942         case EVAL_ERROR_VALUE_IS_INFINITE:
 943             return "computed value is infinite";
 944
 945         case EVAL_ERROR_UNKNOWN_VARIABLE:
 946             return "undefined variable";
 947
 948         default:
 949             return "unknown error";
 950     }
 951 }