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