src/eval.c

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