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