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