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