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