src/eval.c

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