src/eval.c

   1 #include "common.h"
   2
   3 static inline void skip_spaces(const char **string) {
   4     const char *s = *string;
   5     while(isspace(*s)) s++;
   6     *string = s;
   7 }
   8
   9 // ----------------------------------------------------------------------------
  10 // operators that work on 2 operands
  11
  12 static inline int isoperatorterm_word(const char s) {
  13     if(isspace(s) || s == '(' || s == '$' || s == '!' || s == '-' || s == '+' || isdigit(s)) return 1;
  14     return 0;
  15 }
  16
  17 static inline int isoperatorterm_symbol(const char s) {
  18     if(isoperatorterm_word(s) || isalpha(s)) return 1;
  19     return 0;
  20 }
  21
  22 static inline int parse_and(const char **string) {
  23     const char *s = *string;
  24
  25     // AND
  26     if((s[0] == 'A' || s[0] == 'a') && (s[1] == 'N' || s[1] == 'n') && (s[2] == 'D' || s[2] == 'd') && isoperatorterm_word(s[3])) {
  27         *string = &s[4];
  28         return 1;
  29     }
  30
  31     // &&
  32     if(s[0] == '&' && s[1] == '&' && isoperatorterm_symbol(s[2])) {
  33         *string = &s[2];
  34         return 1;
  35     }
  36
  37     return 0;
  38 }
  39
  40 static inline int parse_or(const char **string) {
  41     const char *s = *string;
  42
  43     // OR
  44     if((s[0] == 'O' || s[0] == 'o') && (s[1] == 'R' || s[1] == 'r') && isoperatorterm_word(s[2])) {
  45         *string = &s[3];
  46         return 1;
  47     }
  48
  49     // ||
  50     if(s[0] == '|' && s[1] == '|' && isoperatorterm_symbol(s[2])) {
  51         *string = &s[2];
  52         return 1;
  53     }
  54
  55     return 0;
  56 }
  57
  58 static inline int parse_greater_than_or_equal(const char **string) {
  59     const char *s = *string;
  60
  61     // >=
  62     if(s[0] == '>' && s[1] == '=' && isoperatorterm_symbol(s[2])) {
  63         *string = &s[2];
  64         return 1;
  65     }
  66
  67     return 0;
  68 }
  69
  70 static inline int parse_less_than_or_equal(const char **string) {
  71     const char *s = *string;
  72
  73     // <=
  74     if (s[0] == '<' && s[1] == '=' && isoperatorterm_symbol(s[2])) {
  75         *string = &s[2];
  76         return 1;
  77     }
  78
  79     return 0;
  80 }
  81
  82 static inline int parse_greater(const char **string) {
  83     const char *s = *string;
  84
  85     // >
  86     if(s[0] == '>' && isoperatorterm_symbol(s[1])) {
  87         *string = &s[1];
  88         return 1;
  89     }
  90
  91     return 0;
  92 }
  93
  94 static inline int parse_less(const char **string) {
  95     const char *s = *string;
  96
  97     // <
  98     if(s[0] == '<' && isoperatorterm_symbol(s[1])) {
  99         *string = &s[1];
 100         return 1;
 101     }
 102
 103     return 0;
 104 }
 105
 106 static inline int parse_equal(const char **string) {
 107     const char *s = *string;
 108
 109     // ==
 110     if(s[0] == '=' && s[1] == '=' && isoperatorterm_symbol(s[2])) {
 111         *string = &s[2];
 112         return 1;
 113     }
 114
 115     // =
 116     if(s[0] == '=' && isoperatorterm_symbol(s[1])) {
 117         *string = &s[1];
 118         return 1;
 119     }
 120
 121     return 0;
 122 }
 123
 124 static inline int parse_not_equal(const char **string) {
 125     const char *s = *string;
 126
 127     // !=
 128     if(s[0] == '!' && s[1] == '=' && isoperatorterm_symbol(s[2])) {
 129         *string = &s[2];
 130         return 1;
 131     }
 132
 133     // <>
 134     if(s[0] == '<' && s[1] == '>' && isoperatorterm_symbol(s[2])) {
 135         *string = &s[2];
 136     }
 137
 138     return 0;
 139 }
 140
 141 static inline int parse_multiply(const char **string) {
 142     const char *s = *string;
 143
 144     // *
 145     if(s[0] == '*' && isoperatorterm_symbol(s[1])) {
 146         *string = &s[1];
 147         return 1;
 148     }
 149
 150     return 0;
 151 }
 152
 153 static inline int parse_divide(const char **string) {
 154     const char *s = *string;
 155
 156     // /
 157     if(s[0] == '/' && isoperatorterm_symbol(s[1])) {
 158         *string = &s[1];
 159         return 1;
 160     }
 161
 162     return 0;
 163 }
 164
 165 static inline int parse_minus(const char **string) {
 166     const char *s = *string;
 167
 168     // -
 169     if(s[0] == '-' && isoperatorterm_symbol(s[1])) {
 170         *string = &s[1];
 171         return 1;
 172     }
 173
 174     return 0;
 175 }
 176
 177 static inline int parse_plus(const char **string) {
 178     const char *s = *string;
 179
 180     // +
 181     if(s[0] == '+' && isoperatorterm_symbol(s[1])) {
 182         *string = &s[1];
 183         return 1;
 184     }
 185
 186     return 0;
 187 }
 188
 189 static inline int parse_open_subexpression(const char **string) {
 190     const char *s = *string;
 191
 192     // (
 193     if(s[0] == '(') {
 194         *string = &s[1];
 195         return 1;
 196     }
 197
 198     return 0;
 199 }
 200
 201 static inline int parse_close_subexpression(const char **string) {
 202     const char *s = *string;
 203
 204     // (
 205     if(s[0] == ')') {
 206         *string = &s[1];
 207         return 1;
 208     }
 209
 210     return 0;
 211 }
 212
 213 static inline int parse_literal(const char **string, calculated_number *number) {
 214     char *end = NULL;
 215     *number = strtold(*string, &end);
 216     if(!end || *string == end) return 0;
 217
 218     *string = end;
 219     return 1;
 220 }
 221
 222 // ----------------------------------------------------------------------------
 223 // operators that affect a single operand
 224
 225 static inline int parse_not(const char **string) {
 226     const char *s = *string;
 227
 228     // NOT
 229     if((s[0] == 'N' || s[0] == 'n') && (s[1] == 'O' || s[1] == 'o') && (s[2] == 'T' || s[2] == 't') && isoperatorterm_word(s[3])) {
 230         *string = &s[3];
 231         return 1;
 232     }
 233
 234     if(s[0] == EVAL_OPERATOR_NOT) {
 235         *string = &s[1];
 236         return 1;
 237     }
 238
 239     return 0;
 240 }
 241
 242 static struct operator_parser {
 243     char id;
 244     int (*parse)(const char **);
 245 } operator_parsers[] = {
 246         // the order in this list is important!
 247         // the first matching will be used
 248         // so place the longer of overlapping ones
 249         // at the top
 250
 251         { EVAL_OPERATOR_AND,                   parse_and },
 252         { EVAL_OPERATOR_OR,                    parse_or },
 253         { EVAL_OPERATOR_GREATER_THAN_OR_EQUAL, parse_greater_than_or_equal },
 254         { EVAL_OPERATOR_LESS_THAN_OR_EQUAL,    parse_less_than_or_equal },
 255         { EVAL_OPERATOR_NOT_EQUAL,             parse_not_equal },
 256         { EVAL_OPERATOR_EQUAL,                 parse_equal },
 257         { EVAL_OPERATOR_LESS,                  parse_less },
 258         { EVAL_OPERATOR_GREATER,               parse_greater },
 259         { EVAL_OPERATOR_PLUS,                  parse_plus },
 260         { EVAL_OPERATOR_MINUS,                 parse_minus },
 261         { EVAL_OPERATOR_MULTIPLY,              parse_multiply },
 262         { EVAL_OPERATOR_DIVIDE,                parse_divide },
 263
 264         /* we should not put
 265          *
 266          *  - NOT
 267          *  - (
 268          *  - )
 269          *
 270          * in this list
 271          */
 272
 273         { EVAL_OPERATOR_NOP, NULL }
 274 };
 275
 276 // ----------------------------------------------------------------------------
 277 // evaluation of operations
 278
 279 calculated_number eval_and(EVAL_OPERAND *op) {
 280     return 0;
 281 }
 282 calculated_number eval_or(EVAL_OPERAND *op) {
 283     return 0;
 284 }
 285 calculated_number eval_greater_than_or_equal(EVAL_OPERAND *op) {
 286     return 0;
 287 }
 288 calculated_number eval_less_than_or_equal(EVAL_OPERAND *op) {
 289     return 0;
 290 }
 291 calculated_number eval_not_equal(EVAL_OPERAND *op) {
 292     return 0;
 293 }
 294 calculated_number eval_equal(EVAL_OPERAND *op) {
 295     return 0;
 296 }
 297 calculated_number eval_less(EVAL_OPERAND *op) {
 298     return 0;
 299 }
 300 calculated_number eval_greater(EVAL_OPERAND *op) {
 301     return 0;
 302 }
 303 calculated_number eval_plus(EVAL_OPERAND *op) {
 304     return 0;
 305 }
 306 calculated_number eval_minus(EVAL_OPERAND *op) {
 307     return 0;
 308 }
 309 calculated_number eval_multiply(EVAL_OPERAND *op) {
 310     return 0;
 311 }
 312 calculated_number eval_divide(EVAL_OPERAND *op) {
 313     return 0;
 314 }
 315 calculated_number eval_nop(EVAL_OPERAND *op) {
 316     return 0;
 317 }
 318 calculated_number eval_not(EVAL_OPERAND *op) {
 319     return 0;
 320 }
 321 calculated_number eval_sign_plus(EVAL_OPERAND *op) {
 322     return 0;
 323 }
 324 calculated_number eval_sign_minus(EVAL_OPERAND *op) {
 325     return 0;
 326 }
 327
 328 static struct operator {
 329     const char *print_as;
 330     char precedence;
 331     calculated_number (*eval)(EVAL_OPERAND *op);
 332 } operators[256] = {
 333         // this is a random access array
 334         // we always access it with a known EVAL_OPERATOR_X
 335
 336         [EVAL_OPERATOR_AND]                   = { "&&", 2, eval_and },
 337         [EVAL_OPERATOR_OR]                    = { "||", 2, eval_or },
 338         [EVAL_OPERATOR_GREATER_THAN_OR_EQUAL] = { ">=", 3, eval_greater_than_or_equal },
 339         [EVAL_OPERATOR_LESS_THAN_OR_EQUAL]    = { "<=", 3, eval_less_than_or_equal },
 340         [EVAL_OPERATOR_NOT_EQUAL]             = { "!=", 3, eval_not_equal },
 341         [EVAL_OPERATOR_EQUAL]                 = { "==", 3, eval_equal },
 342         [EVAL_OPERATOR_LESS]                  = { "<",  3, eval_less },
 343         [EVAL_OPERATOR_GREATER]               = { ">",  3, eval_greater },
 344         [EVAL_OPERATOR_PLUS]                  = { "+",  4, eval_plus },
 345         [EVAL_OPERATOR_MINUS]                 = { "-",  4, eval_minus },
 346         [EVAL_OPERATOR_MULTIPLY]              = { "*",  5, eval_multiply },
 347         [EVAL_OPERATOR_DIVIDE]                = { "/",  5, eval_divide },
 348         [EVAL_OPERATOR_NOT]                   = { "!",  6, eval_not },
 349         [EVAL_OPERATOR_SIGN_PLUS]             = { "+",  6, eval_sign_plus },
 350         [EVAL_OPERATOR_SIGN_MINUS]            = { "-",  6, eval_sign_minus },
 351         [EVAL_OPERATOR_NOP]                   = { NULL, 7, eval_nop },
 352         [EVAL_OPERATOR_VALUE]                 = { NULL, 7, eval_nop },
 353         [EVAL_OPERATOR_EXPRESSION_OPEN]       = { "(",  7, eval_nop },
 354
 355         // this should exist in our evaluation list
 356         [EVAL_OPERATOR_EXPRESSION_CLOSE]      = { ")",  7, eval_nop }
 357 };
 358
 359 #define eval_precedence(operator) (operators[(unsigned char)(operator)].precedence)
 360
 361 // ----------------------------------------------------------------------------
 362
 363 static inline char parse_operator(const char **string, int *precedence) {
 364     skip_spaces(string);
 365
 366     int i;
 367     for(i = 0 ; operator_parsers[i].parse != NULL ; i++)
 368         if(operator_parsers[i].parse(string)) {
 369             if(precedence) *precedence = eval_precedence(operator_parsers[i].id);
 370             return operator_parsers[i].id;
 371         }
 372
 373     return EVAL_OPERATOR_NOP;
 374 }
 375
 376
 377 static inline EVAL_OPERAND *operand_alloc(int count) {
 378     static int id = 1;
 379
 380     EVAL_OPERAND *op = calloc(1, sizeof(EVAL_OPERAND) + (sizeof(EVAL_VALUE) * count));
 381     if(!op) fatal("Cannot allocate memory for OPERAND with %d slots", count);
 382
 383     op->id = id++;
 384     op->operator = EVAL_OPERATOR_NOP;
 385     op->precedence = eval_precedence(EVAL_OPERATOR_NOP);
 386     op->count = count;
 387     return op;
 388 }
 389
 390 static inline void operand_set_value_operand(EVAL_OPERAND *op, int pos, EVAL_OPERAND *value) {
 391     if(pos >= op->count)
 392         fatal("Invalid request to set position %d of OPERAND that has only %d values", pos + 1, op->count + 1);
 393
 394     op->ops[pos].type = EVAL_VALUE_EXPRESSION;
 395     op->ops[pos].expression = value;
 396 }
 397
 398 static inline void operand_set_value_literal(EVAL_OPERAND *op, int pos, calculated_number value) {
 399     if(pos >= op->count)
 400         fatal("Invalid request to set position %d of OPERAND that has only %d values", pos + 1, op->count + 1);
 401
 402     op->ops[pos].type = EVAL_VALUE_NUMBER;
 403     op->ops[pos].number = value;
 404 }
 405
 406 // forward definitions
 407 static inline void operand_free(EVAL_OPERAND *op);
 408 static inline EVAL_OPERAND *parse_operand(const char **string, int *error);
 409 static inline EVAL_OPERAND *parse_operand1(const char **string, int *error);
 410
 411 static inline void variable_free(VARIABLE *v) {
 412     free(v);
 413 }
 414
 415 static inline void value_free(EVAL_VALUE *v) {
 416     switch(v->type) {
 417         case EVAL_VALUE_EXPRESSION:
 418             operand_free(v->expression);
 419             break;
 420
 421         case EVAL_VALUE_VARIABLE:
 422             variable_free(v->variable);
 423             break;
 424
 425         default:
 426             break;
 427     }
 428 }
 429
 430 static inline void operand_free(EVAL_OPERAND *op) {
 431     if(op->count) {
 432         int i;
 433         for(i = op->count - 1; i >= 0 ;i--)
 434             value_free(&op->ops[i]);
 435     }
 436
 437     free(op);
 438 }
 439
 440 static inline EVAL_OPERAND *parse_operand_with_operator(const char **string, char type, int *error) {
 441     EVAL_OPERAND *sub = parse_operand1(string, error);
 442     if(!sub) return NULL;
 443
 444     EVAL_OPERAND *op = operand_alloc(1);
 445     op->operator = type;
 446     operand_set_value_operand(op, 0, sub);
 447     return op;
 448 }
 449
 450 static inline EVAL_OPERAND *parse_operand1(const char **string, int *error) {
 451     EVAL_OPERAND *op1 = NULL;
 452     calculated_number number;
 453
 454     *error = EVAL_ERROR_OK;
 455
 456     skip_spaces(string);
 457     if(!(**string)) {
 458         *error = EVAL_ERROR_MISSING_OPERAND;
 459         return NULL;
 460     }
 461
 462     if(parse_not(string)) {
 463         op1 = parse_operand_with_operator(string, EVAL_OPERATOR_NOT, error);
 464         op1->precedence = eval_precedence(EVAL_OPERATOR_NOT);
 465     }
 466     else if(parse_plus(string)) {
 467         op1 = parse_operand_with_operator(string, EVAL_OPERATOR_SIGN_PLUS, error);
 468         op1->precedence = eval_precedence(EVAL_OPERATOR_SIGN_PLUS);
 469     }
 470     else if(parse_minus(string)) {
 471         op1 = parse_operand_with_operator(string, EVAL_OPERATOR_SIGN_MINUS, error);
 472         op1->precedence = eval_precedence(EVAL_OPERATOR_SIGN_MINUS);
 473     }
 474     else if(parse_open_subexpression(string)) {
 475         EVAL_OPERAND *sub = parse_operand(string, error);
 476         if(sub) {
 477             op1 = operand_alloc(1);
 478             op1->operator = EVAL_OPERATOR_EXPRESSION_OPEN;
 479             op1->precedence = eval_precedence(EVAL_OPERATOR_EXPRESSION_OPEN);
 480             operand_set_value_operand(op1, 0, sub);
 481             if(!parse_close_subexpression(string)) {
 482                 *error = EVAL_ERROR_MISSING_CLOSE_SUBEXPRESSION;
 483                 operand_free(op1);
 484                 return NULL;
 485             }
 486         }
 487     }
 488 //    else if(parse_variable(string)) {
 489 //
 490 //    }
 491     else if(parse_literal(string, &number)) {
 492         op1 = operand_alloc(1);
 493         op1->operator = EVAL_OPERATOR_VALUE;
 494         operand_set_value_literal(op1, 0, number);
 495     }
 496     else if(*string)
 497         *error = EVAL_ERROR_UNKNOWN_OPERAND;
 498     else
 499         *error = EVAL_ERROR_MISSING_OPERAND;
 500
 501     return op1;
 502 }
 503
 504 static inline EVAL_OPERAND *parse_operand_rest(const char **string, int *error, EVAL_OPERAND *op1) {
 505     EVAL_OPERAND *op2 = NULL;
 506     char operator;
 507     int precedence;
 508
 509     operator = parse_operator(string, &precedence);
 510     skip_spaces(string);
 511
 512     if(operator != EVAL_OPERATOR_NOP) {
 513         op2 = parse_operand1(string, error);
 514         if(!op2) {
 515             operand_free(op1);
 516             return NULL;
 517         }
 518
 519         EVAL_OPERAND *op = operand_alloc(2);
 520         op->operator = operator;
 521         op->precedence = precedence;
 522
 523         operand_set_value_operand(op, 0, op1);
 524         operand_set_value_operand(op, 1, op2);
 525
 526         if(op->precedence > op1->precedence && op1->count == 2 && op1->operator != '(' && op1->ops[1].type == EVAL_VALUE_EXPRESSION) {
 527             operand_set_value_operand(op, 0, op1->ops[1].expression);
 528             op1->ops[1].expression = op;
 529             op = op1;
 530         }
 531
 532         return parse_operand_rest(string, error, op);
 533     }
 534     else if(**string == EVAL_OPERATOR_EXPRESSION_CLOSE) {
 535         ;
 536     }
 537     else if(**string) {
 538         if(op1) operand_free(op1);
 539         op1 = NULL;
 540         *error = EVAL_ERROR_MISSING_OPERATOR;
 541     }
 542
 543     return op1;
 544 }
 545
 546 static inline EVAL_OPERAND *parse_operand(const char **string, int *error) {
 547     EVAL_OPERAND *op1 = NULL;
 548
 549     op1 = parse_operand1(string, error);
 550     if(!op1) {
 551         *error = EVAL_ERROR_MISSING_OPERAND;
 552         return NULL;
 553     }
 554
 555     return parse_operand_rest(string, error, op1);
 556 }
 557
 558 const char *eval_error(int error) {
 559     switch(error) {
 560         case EVAL_ERROR_OK:
 561             return "success";
 562
 563         case EVAL_ERROR_MISSING_CLOSE_SUBEXPRESSION:
 564             return "missing closing parenthesis";
 565
 566         case EVAL_ERROR_UNKNOWN_OPERAND:
 567             return "unknown operand";
 568
 569         case EVAL_ERROR_MISSING_OPERAND:
 570             return "expected operand";
 571
 572         case EVAL_ERROR_MISSING_OPERATOR:
 573             return "expected operator";
 574
 575         default:
 576             return "unknown error";
 577     }
 578 }
 579
 580 EVAL_OPERAND *parse_expression(const char *string, const char **failed_at, int *error) {
 581     const char *s;
 582     int err = EVAL_ERROR_OK;
 583     unsigned long pos = 0;
 584
 585     s = string;
 586     EVAL_OPERAND *op = parse_operand(&s, &err);
 587
 588     if (failed_at) *failed_at = s;
 589     if (error) *error = err;
 590
 591     if(!op) {
 592         pos = s - string + 1;
 593         error("failed to parse expression '%s': %s at character %lu (i.e.: '%s').", string, eval_error(err), pos, s);
 594     }
 595
 596     return op;
 597 }
 598
 599 void free_expression(EVAL_OPERAND *op) {
 600     if(op) operand_free(op);
 601 }