1 /* Simple expression parser */ 2 %{ 3 #define YYDEBUG 1 4 #include <assert.h> 5 #include <math.h> 6 #include "util/debug.h" 7 #include "smt.h" 8 #define IN_EXPR_Y 1 9 #include "expr.h" 10 %} 11 12 %define api.pure full 13 14 %parse-param { double *final_val } 15 %parse-param { struct expr_parse_ctx *ctx } 16 %parse-param { bool compute_ids } 17 %parse-param {void *scanner} 18 %lex-param {void* scanner} 19 20 %union { 21 double num; 22 char *str; 23 struct ids { 24 /* 25 * When creating ids, holds the working set of event ids. NULL 26 * implies the set is empty. 27 */ 28 struct hashmap *ids; 29 /* 30 * The metric value. When not creating ids this is the value 31 * read from a counter, a constant or some computed value. When 32 * creating ids the value is either a constant or BOTTOM. NAN is 33 * used as the special BOTTOM value, representing a "set of all 34 * values" case. 35 */ 36 double val; 37 } ids; 38 } 39 40 %token ID NUMBER MIN MAX IF ELSE SMT_ON D_RATIO EXPR_ERROR 41 %left MIN MAX IF 42 %left '|' 43 %left '^' 44 %left '&' 45 %left '<' '>' 46 %left '-' '+' 47 %left '*' '/' '%' 48 %left NEG NOT 49 %type <num> NUMBER 50 %type <str> ID 51 %destructor { free ($$); } <str> 52 %type <ids> expr if_expr 53 %destructor { ids__free($$.ids); } <ids> 54 55 %{ 56 static void expr_error(double *final_val __maybe_unused, 57 struct expr_parse_ctx *ctx __maybe_unused, 58 bool compute_ids __maybe_unused, 59 void *scanner, 60 const char *s) 61 { 62 pr_debug("%s\n", s); 63 } 64 65 /* 66 * During compute ids, the special "bottom" value uses NAN to represent the set 67 * of all values. NAN is selected as it isn't a useful constant value. 68 */ 69 #define BOTTOM NAN 70 71 /* During computing ids, does val represent a constant (non-BOTTOM) value? */ 72 static bool is_const(double val) 73 { 74 return isfinite(val); 75 } 76 77 static struct ids union_expr(struct ids ids1, struct ids ids2) 78 { 79 struct ids result = { 80 .val = BOTTOM, 81 .ids = ids__union(ids1.ids, ids2.ids), 82 }; 83 return result; 84 } 85 86 /* 87 * If we're not computing ids or $1 and $3 are constants, compute the new 88 * constant value using OP. Its invariant that there are no ids. If computing 89 * ids for non-constants union the set of IDs that must be computed. 90 */ 91 #define BINARY_LONG_OP(RESULT, OP, LHS, RHS) \ 92 if (!compute_ids || (is_const(LHS.val) && is_const(RHS.val))) { \ 93 assert(LHS.ids == NULL); \ 94 assert(RHS.ids == NULL); \ 95 RESULT.val = (long)LHS.val OP (long)RHS.val; \ 96 RESULT.ids = NULL; \ 97 } else { \ 98 RESULT = union_expr(LHS, RHS); \ 99 } 100 101 #define BINARY_OP(RESULT, OP, LHS, RHS) \ 102 if (!compute_ids || (is_const(LHS.val) && is_const(RHS.val))) { \ 103 assert(LHS.ids == NULL); \ 104 assert(RHS.ids == NULL); \ 105 RESULT.val = LHS.val OP RHS.val; \ 106 RESULT.ids = NULL; \ 107 } else { \ 108 RESULT = union_expr(LHS, RHS); \ 109 } 110 111 %} 112 %% 113 114 start: if_expr 115 { 116 if (compute_ids) 117 ctx->ids = ids__union($1.ids, ctx->ids); 118 119 if (final_val) 120 *final_val = $1.val; 121 } 122 ; 123 124 if_expr: expr IF expr ELSE expr 125 { 126 if (fpclassify($3.val) == FP_ZERO) { 127 /* 128 * The IF expression evaluated to 0 so treat as false, take the 129 * ELSE and discard everything else. 130 */ 131 $$.val = $5.val; 132 $$.ids = $5.ids; 133 ids__free($1.ids); 134 ids__free($3.ids); 135 } else if (!compute_ids || is_const($3.val)) { 136 /* 137 * If ids aren't computed then treat the expression as true. If 138 * ids are being computed and the IF expr is a non-zero 139 * constant, then also evaluate the true case. 140 */ 141 $$.val = $1.val; 142 $$.ids = $1.ids; 143 ids__free($3.ids); 144 ids__free($5.ids); 145 } else if ($1.val == $5.val) { 146 /* 147 * LHS == RHS, so both are an identical constant. No need to 148 * evaluate any events. 149 */ 150 $$.val = $1.val; 151 $$.ids = NULL; 152 ids__free($1.ids); 153 ids__free($3.ids); 154 ids__free($5.ids); 155 } else { 156 /* 157 * Value is either the LHS or RHS and we need the IF expression 158 * to compute it. 159 */ 160 $$ = union_expr($1, union_expr($3, $5)); 161 } 162 } 163 | expr 164 ; 165 166 expr: NUMBER 167 { 168 $$.val = $1; 169 $$.ids = NULL; 170 } 171 | ID 172 { 173 if (!compute_ids) { 174 /* 175 * Compute the event's value from ID. If the ID isn't known then 176 * it isn't used to compute the formula so set to NAN. 177 */ 178 struct expr_id_data *data; 179 180 $$.val = NAN; 181 if (expr__resolve_id(ctx, $1, &data) == 0) 182 $$.val = expr_id_data__value(data); 183 184 $$.ids = NULL; 185 free($1); 186 } else { 187 /* 188 * Set the value to BOTTOM to show that any value is possible 189 * when the event is computed. Create a set of just the ID. 190 */ 191 $$.val = BOTTOM; 192 $$.ids = ids__new(); 193 if (!$$.ids || ids__insert($$.ids, $1)) 194 YYABORT; 195 } 196 } 197 | expr '|' expr { BINARY_LONG_OP($$, |, $1, $3); } 198 | expr '&' expr { BINARY_LONG_OP($$, &, $1, $3); } 199 | expr '^' expr { BINARY_LONG_OP($$, ^, $1, $3); } 200 | expr '<' expr { BINARY_OP($$, <, $1, $3); } 201 | expr '>' expr { BINARY_OP($$, >, $1, $3); } 202 | expr '+' expr { BINARY_OP($$, +, $1, $3); } 203 | expr '-' expr { BINARY_OP($$, -, $1, $3); } 204 | expr '*' expr { BINARY_OP($$, *, $1, $3); } 205 | expr '/' expr 206 { 207 if (fpclassify($3.val) == FP_ZERO) { 208 pr_debug("division by zero\n"); 209 YYABORT; 210 } else if (!compute_ids || (is_const($1.val) && is_const($3.val))) { 211 assert($1.ids == NULL); 212 assert($3.ids == NULL); 213 $$.val = $1.val / $3.val; 214 $$.ids = NULL; 215 } else { 216 /* LHS and/or RHS need computing from event IDs so union. */ 217 $$ = union_expr($1, $3); 218 } 219 } 220 | expr '%' expr 221 { 222 if (fpclassify($3.val) == FP_ZERO) { 223 pr_debug("division by zero\n"); 224 YYABORT; 225 } else if (!compute_ids || (is_const($1.val) && is_const($3.val))) { 226 assert($1.ids == NULL); 227 assert($3.ids == NULL); 228 $$.val = (long)$1.val % (long)$3.val; 229 $$.ids = NULL; 230 } else { 231 /* LHS and/or RHS need computing from event IDs so union. */ 232 $$ = union_expr($1, $3); 233 } 234 } 235 | D_RATIO '(' expr ',' expr ')' 236 { 237 if (fpclassify($5.val) == FP_ZERO) { 238 /* 239 * Division by constant zero always yields zero and no events 240 * are necessary. 241 */ 242 assert($5.ids == NULL); 243 $$.val = 0.0; 244 $$.ids = NULL; 245 ids__free($3.ids); 246 } else if (!compute_ids || (is_const($3.val) && is_const($5.val))) { 247 assert($3.ids == NULL); 248 assert($5.ids == NULL); 249 $$.val = $3.val / $5.val; 250 $$.ids = NULL; 251 } else { 252 /* LHS and/or RHS need computing from event IDs so union. */ 253 $$ = union_expr($3, $5); 254 } 255 } 256 | '-' expr %prec NEG 257 { 258 $$.val = -$2.val; 259 $$.ids = $2.ids; 260 } 261 | '(' if_expr ')' 262 { 263 $$ = $2; 264 } 265 | MIN '(' expr ',' expr ')' 266 { 267 if (!compute_ids) { 268 $$.val = $3.val < $5.val ? $3.val : $5.val; 269 $$.ids = NULL; 270 } else { 271 $$ = union_expr($3, $5); 272 } 273 } 274 | MAX '(' expr ',' expr ')' 275 { 276 if (!compute_ids) { 277 $$.val = $3.val > $5.val ? $3.val : $5.val; 278 $$.ids = NULL; 279 } else { 280 $$ = union_expr($3, $5); 281 } 282 } 283 | SMT_ON 284 { 285 $$.val = smt_on() > 0 ? 1.0 : 0.0; 286 $$.ids = NULL; 287 } 288 ; 289 290 %% 291