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