1 /* Simple expression parser */ 2 %{ 3 #define YYDEBUG 1 4 #include <assert.h> 5 #include <math.h> 6 #include <stdlib.h> 7 #include "util/debug.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 LITERAL D_RATIO SOURCE_COUNT HAS_EVENT 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 LITERAL 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 static struct ids handle_id(struct expr_parse_ctx *ctx, char *id, 87 bool compute_ids, bool source_count) 88 { 89 struct ids result; 90 91 if (!compute_ids) { 92 /* 93 * Compute the event's value from ID. If the ID isn't known then 94 * it isn't used to compute the formula so set to NAN. 95 */ 96 struct expr_id_data *data; 97 98 result.val = NAN; 99 if (expr__resolve_id(ctx, id, &data) == 0) { 100 result.val = source_count 101 ? expr_id_data__source_count(data) 102 : expr_id_data__value(data); 103 } 104 result.ids = NULL; 105 free(id); 106 } else { 107 /* 108 * Set the value to BOTTOM to show that any value is possible 109 * when the event is computed. Create a set of just the ID. 110 */ 111 result.val = BOTTOM; 112 result.ids = ids__new(); 113 if (!result.ids || ids__insert(result.ids, id)) { 114 pr_err("Error creating IDs for '%s'", id); 115 free(id); 116 } 117 } 118 return result; 119 } 120 121 /* 122 * If we're not computing ids or $1 and $3 are constants, compute the new 123 * constant value using OP. Its invariant that there are no ids. If computing 124 * ids for non-constants union the set of IDs that must be computed. 125 */ 126 #define BINARY_OP(RESULT, OP, LHS, RHS) \ 127 if (!compute_ids || (is_const(LHS.val) && is_const(RHS.val))) { \ 128 assert(LHS.ids == NULL); \ 129 assert(RHS.ids == NULL); \ 130 if (isnan(LHS.val) || isnan(RHS.val)) { \ 131 RESULT.val = NAN; \ 132 } else { \ 133 RESULT.val = LHS.val OP RHS.val; \ 134 } \ 135 RESULT.ids = NULL; \ 136 } else { \ 137 RESULT = union_expr(LHS, RHS); \ 138 } 139 140 %} 141 %% 142 143 start: if_expr 144 { 145 if (compute_ids) 146 ctx->ids = ids__union($1.ids, ctx->ids); 147 148 if (final_val) 149 *final_val = $1.val; 150 } 151 ; 152 153 if_expr: expr IF expr ELSE if_expr 154 { 155 if (fpclassify($3.val) == FP_ZERO) { 156 /* 157 * The IF expression evaluated to 0 so treat as false, take the 158 * ELSE and discard everything else. 159 */ 160 $$.val = $5.val; 161 $$.ids = $5.ids; 162 ids__free($1.ids); 163 ids__free($3.ids); 164 } else if (!compute_ids || is_const($3.val)) { 165 /* 166 * If ids aren't computed then treat the expression as true. If 167 * ids are being computed and the IF expr is a non-zero 168 * constant, then also evaluate the true case. 169 */ 170 $$.val = $1.val; 171 $$.ids = $1.ids; 172 ids__free($3.ids); 173 ids__free($5.ids); 174 } else if ($1.val == $5.val) { 175 /* 176 * LHS == RHS, so both are an identical constant. No need to 177 * evaluate any events. 178 */ 179 $$.val = $1.val; 180 $$.ids = NULL; 181 ids__free($1.ids); 182 ids__free($3.ids); 183 ids__free($5.ids); 184 } else { 185 /* 186 * Value is either the LHS or RHS and we need the IF expression 187 * to compute it. 188 */ 189 $$ = union_expr($1, union_expr($3, $5)); 190 } 191 } 192 | expr 193 ; 194 195 expr: NUMBER 196 { 197 $$.val = $1; 198 $$.ids = NULL; 199 } 200 | ID { $$ = handle_id(ctx, $1, compute_ids, /*source_count=*/false); } 201 | SOURCE_COUNT '(' ID ')' { $$ = handle_id(ctx, $3, compute_ids, /*source_count=*/true); } 202 | HAS_EVENT '(' ID ')' 203 { 204 $$.val = expr__has_event(ctx, compute_ids, $3); 205 $$.ids = NULL; 206 free($3); 207 } 208 | expr '|' expr 209 { 210 if (is_const($1.val) && is_const($3.val)) { 211 assert($1.ids == NULL); 212 assert($3.ids == NULL); 213 $$.ids = NULL; 214 $$.val = (fpclassify($1.val) == FP_ZERO && fpclassify($3.val) == FP_ZERO) ? 0 : 1; 215 } else if (is_const($1.val)) { 216 assert($1.ids == NULL); 217 if (fpclassify($1.val) == FP_ZERO) { 218 $$ = $3; 219 } else { 220 $$.val = 1; 221 $$.ids = NULL; 222 ids__free($3.ids); 223 } 224 } else if (is_const($3.val)) { 225 assert($3.ids == NULL); 226 if (fpclassify($3.val) == FP_ZERO) { 227 $$ = $1; 228 } else { 229 $$.val = 1; 230 $$.ids = NULL; 231 ids__free($1.ids); 232 } 233 } else { 234 $$ = union_expr($1, $3); 235 } 236 } 237 | expr '&' expr 238 { 239 if (is_const($1.val) && is_const($3.val)) { 240 assert($1.ids == NULL); 241 assert($3.ids == NULL); 242 $$.val = (fpclassify($1.val) != FP_ZERO && fpclassify($3.val) != FP_ZERO) ? 1 : 0; 243 $$.ids = NULL; 244 } else if (is_const($1.val)) { 245 assert($1.ids == NULL); 246 if (fpclassify($1.val) != FP_ZERO) { 247 $$ = $3; 248 } else { 249 $$.val = 0; 250 $$.ids = NULL; 251 ids__free($3.ids); 252 } 253 } else if (is_const($3.val)) { 254 assert($3.ids == NULL); 255 if (fpclassify($3.val) != FP_ZERO) { 256 $$ = $1; 257 } else { 258 $$.val = 0; 259 $$.ids = NULL; 260 ids__free($1.ids); 261 } 262 } else { 263 $$ = union_expr($1, $3); 264 } 265 } 266 | expr '^' expr 267 { 268 if (is_const($1.val) && is_const($3.val)) { 269 assert($1.ids == NULL); 270 assert($3.ids == NULL); 271 $$.val = (fpclassify($1.val) == FP_ZERO) != (fpclassify($3.val) == FP_ZERO) ? 1 : 0; 272 $$.ids = NULL; 273 } else { 274 $$ = union_expr($1, $3); 275 } 276 } 277 | expr '<' expr { BINARY_OP($$, <, $1, $3); } 278 | expr '>' expr { BINARY_OP($$, >, $1, $3); } 279 | expr '+' expr { BINARY_OP($$, +, $1, $3); } 280 | expr '-' expr { BINARY_OP($$, -, $1, $3); } 281 | expr '*' expr { BINARY_OP($$, *, $1, $3); } 282 | expr '/' expr 283 { 284 if (fpclassify($3.val) == FP_ZERO) { 285 pr_debug("division by zero\n"); 286 assert($3.ids == NULL); 287 if (compute_ids) 288 ids__free($1.ids); 289 $$.val = NAN; 290 $$.ids = NULL; 291 } else if (!compute_ids || (is_const($1.val) && is_const($3.val))) { 292 assert($1.ids == NULL); 293 assert($3.ids == NULL); 294 $$.val = $1.val / $3.val; 295 $$.ids = NULL; 296 } else { 297 /* LHS and/or RHS need computing from event IDs so union. */ 298 $$ = union_expr($1, $3); 299 } 300 } 301 | expr '%' expr 302 { 303 if (fpclassify($3.val) == FP_ZERO) { 304 pr_debug("division by zero\n"); 305 YYABORT; 306 } else if (!compute_ids || (is_const($1.val) && is_const($3.val))) { 307 assert($1.ids == NULL); 308 assert($3.ids == NULL); 309 $$.val = (long)$1.val % (long)$3.val; 310 $$.ids = NULL; 311 } else { 312 /* LHS and/or RHS need computing from event IDs so union. */ 313 $$ = union_expr($1, $3); 314 } 315 } 316 | D_RATIO '(' expr ',' expr ')' 317 { 318 if (fpclassify($5.val) == FP_ZERO) { 319 /* 320 * Division by constant zero always yields zero and no events 321 * are necessary. 322 */ 323 assert($5.ids == NULL); 324 $$.val = 0.0; 325 $$.ids = NULL; 326 ids__free($3.ids); 327 } else if (!compute_ids || (is_const($3.val) && is_const($5.val))) { 328 assert($3.ids == NULL); 329 assert($5.ids == NULL); 330 $$.val = $3.val / $5.val; 331 $$.ids = NULL; 332 } else { 333 /* LHS and/or RHS need computing from event IDs so union. */ 334 $$ = union_expr($3, $5); 335 } 336 } 337 | '-' expr %prec NEG 338 { 339 $$.val = -$2.val; 340 $$.ids = $2.ids; 341 } 342 | '(' if_expr ')' 343 { 344 $$ = $2; 345 } 346 | MIN '(' expr ',' expr ')' 347 { 348 if (!compute_ids) { 349 $$.val = $3.val < $5.val ? $3.val : $5.val; 350 $$.ids = NULL; 351 } else { 352 $$ = union_expr($3, $5); 353 } 354 } 355 | MAX '(' expr ',' expr ')' 356 { 357 if (!compute_ids) { 358 $$.val = $3.val > $5.val ? $3.val : $5.val; 359 $$.ids = NULL; 360 } else { 361 $$ = union_expr($3, $5); 362 } 363 } 364 | LITERAL 365 { 366 $$.val = $1; 367 $$.ids = NULL; 368 } 369 ; 370 371 %% 372