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