1 /* Simple expression parser */ 1 /* Simple expression parser */
2 %{ 2 %{
3 #ifndef NDEBUG !! 3 #include "util.h"
4 #define YYDEBUG 1 <<
5 #endif <<
6 #include <assert.h> <<
7 #include <math.h> <<
8 #include <stdlib.h> <<
9 #include "util/debug.h" 4 #include "util/debug.h"
10 #define IN_EXPR_Y 1 5 #define IN_EXPR_Y 1
11 #include "expr.h" 6 #include "expr.h"
12 #include "expr-bison.h" !! 7 #include "smt.h"
13 int expr_lex(YYSTYPE * yylval_param , void *yy !! 8 #include <string.h>
>> 9
>> 10 #define MAXIDLEN 256
14 %} 11 %}
15 12
16 %define api.pure full 13 %define api.pure full
17 14
18 %parse-param { double *final_val } 15 %parse-param { double *final_val }
19 %parse-param { struct expr_parse_ctx *ctx } !! 16 %parse-param { struct parse_ctx *ctx }
20 %parse-param { bool compute_ids } !! 17 %parse-param { const char **pp }
21 %parse-param {void *scanner} !! 18 %lex-param { const char **pp }
22 %lex-param {void* scanner} <<
23 19
24 %union { 20 %union {
25 double num; !! 21 double num;
26 char *str; !! 22 char id[MAXIDLEN+1];
27 struct ids { <<
28 /* <<
29 * When creating ids, holds th <<
30 * implies the set is empty. <<
31 */ <<
32 struct hashmap *ids; <<
33 /* <<
34 * The metric value. When not <<
35 * read from a counter, a cons <<
36 * creating ids the value is e <<
37 * used as the special BOTTOM <<
38 * values" case. <<
39 */ <<
40 double val; <<
41 } ids; <<
42 } 23 }
43 24
44 %token ID NUMBER MIN MAX IF ELSE LITERAL D_RAT !! 25 %token <num> NUMBER
>> 26 %token <id> ID
>> 27 %token MIN MAX IF ELSE SMT_ON
45 %left MIN MAX IF 28 %left MIN MAX IF
46 %left '|' 29 %left '|'
47 %left '^' 30 %left '^'
48 %left '&' 31 %left '&'
49 %left '<' '>' <<
50 %left '-' '+' 32 %left '-' '+'
51 %left '*' '/' '%' 33 %left '*' '/' '%'
52 %left NEG NOT 34 %left NEG NOT
53 %type <num> NUMBER LITERAL !! 35 %type <num> expr if_expr
54 %type <str> ID <<
55 %destructor { free ($$); } <str> <<
56 %type <ids> expr if_expr <<
57 %destructor { ids__free($$.ids); } <ids> <<
58 36
59 %{ 37 %{
60 static void expr_error(double *final_val __may !! 38 static int expr__lex(YYSTYPE *res, const char **pp);
61 struct expr_parse_ctx * !! 39
62 bool compute_ids __mayb !! 40 static void expr__error(double *final_val __maybe_unused,
63 void *scanner __maybe_u !! 41 struct parse_ctx *ctx __maybe_unused,
>> 42 const char **pp __maybe_unused,
64 const char *s) 43 const char *s)
65 { 44 {
66 pr_debug("%s\n", s); 45 pr_debug("%s\n", s);
67 } 46 }
68 47
69 /* !! 48 static int lookup_id(struct parse_ctx *ctx, char *id, double *val)
70 * During compute ids, the special "bottom" va <<
71 * of all values. NAN is selected as it isn't <<
72 */ <<
73 #define BOTTOM NAN <<
74 <<
75 /* During computing ids, does val represent a <<
76 static bool is_const(double val) <<
77 { <<
78 return isfinite(val); <<
79 } <<
80 <<
81 static struct ids union_expr(struct ids ids1, <<
82 { 49 {
83 struct ids result = { !! 50 int i;
84 .val = BOTTOM, <<
85 .ids = ids__union(ids1.ids, id <<
86 }; <<
87 return result; <<
88 } <<
89 <<
90 static struct ids handle_id(struct expr_parse_ <<
91 bool compute_ids, <<
92 { <<
93 struct ids result; <<
94 <<
95 if (!compute_ids) { <<
96 /* <<
97 * Compute the event's value f <<
98 * it isn't used to compute th <<
99 */ <<
100 struct expr_id_data *data; <<
101 51
102 result.val = NAN; !! 52 for (i = 0; i < ctx->num_ids; i++) {
103 if (expr__resolve_id(ctx, id, !! 53 if (!strcasecmp(ctx->ids[i].name, id)) {
104 result.val = source_co !! 54 *val = ctx->ids[i].val;
105 ? expr_id_data !! 55 return 0;
106 : expr_id_data <<
107 } <<
108 result.ids = NULL; <<
109 free(id); <<
110 } else { <<
111 /* <<
112 * Set the value to BOTTOM to <<
113 * when the event is computed. <<
114 */ <<
115 result.val = BOTTOM; <<
116 result.ids = ids__new(); <<
117 if (!result.ids || ids__insert <<
118 pr_err("Error creating <<
119 free(id); <<
120 } 56 }
121 } 57 }
122 return result; !! 58 return -1;
123 } 59 }
124 60
125 /* <<
126 * If we're not computing ids or $1 and $3 are <<
127 * constant value using OP. Its invariant that <<
128 * ids for non-constants union the set of IDs <<
129 */ <<
130 #define BINARY_OP(RESULT, OP, LHS, RHS) <<
131 if (!compute_ids || (is_const(LHS.val) <<
132 assert(LHS.ids == NULL); <<
133 assert(RHS.ids == NULL); <<
134 if (isnan(LHS.val) || isnan(RH <<
135 RESULT.val = NAN; <<
136 } else { <<
137 RESULT.val = LHS.val O <<
138 } <<
139 RESULT.ids = NULL; <<
140 } else { <<
141 RESULT = union_expr(LHS, RHS); <<
142 } <<
143 <<
144 %} 61 %}
145 %% 62 %%
146 63
147 start: if_expr !! 64 all_expr: if_expr { *final_val = $1; }
148 { !! 65 ;
149 if (compute_ids) <<
150 ctx->ids = ids__union($1.ids, <<
151 66
152 if (final_val) !! 67 if_expr:
153 *final_val = $1.val; !! 68 expr IF expr ELSE expr { $$ = $3 ? $1 : $5; }
154 } !! 69 | expr
155 ; !! 70 ;
>> 71
>> 72 expr: NUMBER
>> 73 | ID { if (lookup_id(ctx, $1, &$$) < 0) {
>> 74 pr_debug("%s not found\n", $1);
>> 75 YYABORT;
>> 76 }
>> 77 }
>> 78 | expr '|' expr { $$ = (long)$1 | (long)$3; }
>> 79 | expr '&' expr { $$ = (long)$1 & (long)$3; }
>> 80 | expr '^' expr { $$ = (long)$1 ^ (long)$3; }
>> 81 | expr '+' expr { $$ = $1 + $3; }
>> 82 | expr '-' expr { $$ = $1 - $3; }
>> 83 | expr '*' expr { $$ = $1 * $3; }
>> 84 | expr '/' expr { if ($3 == 0) YYABORT; $$ = $1 / $3; }
>> 85 | expr '%' expr { if ((long)$3 == 0) YYABORT; $$ = (long)$1 % (long)$3; }
>> 86 | '-' expr %prec NEG { $$ = -$2; }
>> 87 | '(' if_expr ')' { $$ = $2; }
>> 88 | MIN '(' expr ',' expr ')' { $$ = $3 < $5 ? $3 : $5; }
>> 89 | MAX '(' expr ',' expr ')' { $$ = $3 > $5 ? $3 : $5; }
>> 90 | SMT_ON { $$ = smt_on() > 0; }
>> 91 ;
156 92
157 if_expr: expr IF expr ELSE if_expr !! 93 %%
158 { <<
159 if (fpclassify($3.val) == FP_ZERO) { <<
160 /* <<
161 * The IF expression evaluated <<
162 * ELSE and discard everything <<
163 */ <<
164 $$.val = $5.val; <<
165 $$.ids = $5.ids; <<
166 ids__free($1.ids); <<
167 ids__free($3.ids); <<
168 } else if (!compute_ids || is_const($3 <<
169 /* <<
170 * If ids aren't computed then <<
171 * ids are being computed and <<
172 * constant, then also evaluat <<
173 */ <<
174 $$.val = $1.val; <<
175 $$.ids = $1.ids; <<
176 ids__free($3.ids); <<
177 ids__free($5.ids); <<
178 } else if ($1.val == $5.val) { <<
179 /* <<
180 * LHS == RHS, so both are an <<
181 * evaluate any events. <<
182 */ <<
183 $$.val = $1.val; <<
184 $$.ids = NULL; <<
185 ids__free($1.ids); <<
186 ids__free($3.ids); <<
187 ids__free($5.ids); <<
188 } else { <<
189 /* <<
190 * Value is either the LHS or <<
191 * to compute it. <<
192 */ <<
193 $$ = union_expr($1, union_expr <<
194 } <<
195 } <<
196 | expr <<
197 ; <<
198 94
199 expr: NUMBER !! 95 static int expr__symbol(YYSTYPE *res, const char *p, const char **pp)
200 { <<
201 $$.val = $1; <<
202 $$.ids = NULL; <<
203 } <<
204 | ID { $$ = handle_ <<
205 | SOURCE_COUNT '(' ID ')' { $$ = handle_ <<
206 | HAS_EVENT '(' ID ')' <<
207 { <<
208 $$.val = expr__has_event(ctx, compute_ <<
209 $$.ids = NULL; <<
210 free($3); <<
211 } <<
212 | STRCMP_CPUID_STR '(' ID ')' <<
213 { 96 {
214 $$.val = expr__strcmp_cpuid_str(ctx, c !! 97 char *dst = res->id;
215 $$.ids = NULL; !! 98 const char *s = p;
216 free($3); !! 99
217 } !! 100 if (*p == '#')
218 | expr '|' expr !! 101 *dst++ = *p++;
219 { !! 102
220 if (is_const($1.val) && is_const($3.va !! 103 while (isalnum(*p) || *p == '_' || *p == '.' || *p == ':' || *p == '@' || *p == '\\') {
221 assert($1.ids == NULL); !! 104 if (p - s >= MAXIDLEN)
222 assert($3.ids == NULL); !! 105 return -1;
223 $$.ids = NULL; !! 106 /*
224 $$.val = (fpclassify($1.val) = !! 107 * Allow @ instead of / to be able to specify pmu/event/ without
225 } else if (is_const($1.val)) { !! 108 * conflicts with normal division.
226 assert($1.ids == NULL); !! 109 */
227 if (fpclassify($1.val) == FP_Z !! 110 if (*p == '@')
228 $$ = $3; !! 111 *dst++ = '/';
229 } else { !! 112 else if (*p == '\\')
230 $$.val = 1; !! 113 *dst++ = *++p;
231 $$.ids = NULL; !! 114 else
232 ids__free($3.ids); !! 115 *dst++ = *p;
233 } !! 116 p++;
234 } else if (is_const($3.val)) { !! 117 }
235 assert($3.ids == NULL); !! 118 *dst = 0;
236 if (fpclassify($3.val) == FP_Z !! 119 *pp = p;
237 $$ = $1; !! 120 dst = res->id;
238 } else { !! 121 switch (dst[0]) {
239 $$.val = 1; !! 122 case 'm':
240 $$.ids = NULL; !! 123 if (!strcmp(dst, "min"))
241 ids__free($1.ids); !! 124 return MIN;
242 } !! 125 if (!strcmp(dst, "max"))
243 } else { !! 126 return MAX;
244 $$ = union_expr($1, $3); !! 127 break;
245 } !! 128 case 'i':
246 } !! 129 if (!strcmp(dst, "if"))
247 | expr '&' expr !! 130 return IF;
248 { !! 131 break;
249 if (is_const($1.val) && is_const($3.va !! 132 case 'e':
250 assert($1.ids == NULL); !! 133 if (!strcmp(dst, "else"))
251 assert($3.ids == NULL); !! 134 return ELSE;
252 $$.val = (fpclassify($1.val) ! !! 135 break;
253 $$.ids = NULL; !! 136 case '#':
254 } else if (is_const($1.val)) { !! 137 if (!strcasecmp(dst, "#smt_on"))
255 assert($1.ids == NULL); !! 138 return SMT_ON;
256 if (fpclassify($1.val) != FP_Z !! 139 break;
257 $$ = $3; !! 140 }
258 } else { !! 141 return ID;
259 $$.val = 0; !! 142 }
260 $$.ids = NULL; !! 143
261 ids__free($3.ids); !! 144 static int expr__lex(YYSTYPE *res, const char **pp)
262 } !! 145 {
263 } else if (is_const($3.val)) { !! 146 int tok;
264 assert($3.ids == NULL); !! 147 const char *s;
265 if (fpclassify($3.val) != FP_Z !! 148 const char *p = *pp;
266 $$ = $1; !! 149
267 } else { !! 150 while (isspace(*p))
268 $$.val = 0; !! 151 p++;
269 $$.ids = NULL; !! 152 s = p;
270 ids__free($1.ids); !! 153 switch (*p++) {
271 } !! 154 case '#':
272 } else { !! 155 case 'a' ... 'z':
273 $$ = union_expr($1, $3); !! 156 case 'A' ... 'Z':
274 } !! 157 return expr__symbol(res, p - 1, pp);
275 } !! 158 case '0' ... '9': case '.':
276 | expr '^' expr !! 159 res->num = strtod(s, (char **)&p);
277 { !! 160 tok = NUMBER;
278 if (is_const($1.val) && is_const($3.va !! 161 break;
279 assert($1.ids == NULL); !! 162 default:
280 assert($3.ids == NULL); !! 163 tok = *s;
281 $$.val = (fpclassify($1.val) = !! 164 break;
282 $$.ids = NULL; !! 165 }
283 } else { !! 166 *pp = p;
284 $$ = union_expr($1, $3); !! 167 return tok;
285 } !! 168 }
286 } !! 169
287 | expr '<' expr { BINARY_OP($$, <, $1, $3); } !! 170 /* Caller must make sure id is allocated */
288 | expr '>' expr { BINARY_OP($$, >, $1, $3); } !! 171 void expr__add_id(struct parse_ctx *ctx, const char *name, double val)
289 | expr '+' expr { BINARY_OP($$, +, $1, $3); } !! 172 {
290 | expr '-' expr { BINARY_OP($$, -, $1, $3); } !! 173 int idx;
291 | expr '*' expr { BINARY_OP($$, *, $1, $3); } !! 174 assert(ctx->num_ids < MAX_PARSE_ID);
292 | expr '/' expr !! 175 idx = ctx->num_ids++;
293 { !! 176 ctx->ids[idx].name = name;
294 if (fpclassify($3.val) == FP_ZERO) { !! 177 ctx->ids[idx].val = val;
295 pr_debug("division by zero\n") !! 178 }
296 assert($3.ids == NULL); !! 179
297 if (compute_ids) !! 180 void expr__ctx_init(struct parse_ctx *ctx)
298 ids__free($1.ids); !! 181 {
299 $$.val = NAN; !! 182 ctx->num_ids = 0;
300 $$.ids = NULL; !! 183 }
301 } else if (!compute_ids || (is_const($ !! 184
302 assert($1.ids == NULL); !! 185 static bool already_seen(const char *val, const char *one, const char **other,
303 assert($3.ids == NULL); !! 186 int num_other)
304 $$.val = $1.val / $3.val; !! 187 {
305 $$.ids = NULL; !! 188 int i;
306 } else { !! 189
307 /* LHS and/or RHS need computi !! 190 if (one && !strcasecmp(one, val))
308 $$ = union_expr($1, $3); !! 191 return true;
309 } !! 192 for (i = 0; i < num_other; i++)
310 } !! 193 if (!strcasecmp(other[i], val))
311 | expr '%' expr !! 194 return true;
312 { !! 195 return false;
313 if (fpclassify($3.val) == FP_ZERO) { !! 196 }
314 pr_debug("division by zero\n") !! 197
315 YYABORT; !! 198 int expr__find_other(const char *p, const char *one, const char ***other,
316 } else if (!compute_ids || (is_const($ !! 199 int *num_otherp)
317 assert($1.ids == NULL); !! 200 {
318 assert($3.ids == NULL); !! 201 const char *orig = p;
319 $$.val = (long)$1.val % (long) !! 202 int err = -1;
320 $$.ids = NULL; !! 203 int num_other;
321 } else { !! 204
322 /* LHS and/or RHS need computi !! 205 *other = malloc((EXPR_MAX_OTHER + 1) * sizeof(char *));
323 $$ = union_expr($1, $3); !! 206 if (!*other)
324 } !! 207 return -1;
325 } !! 208
326 | D_RATIO '(' expr ',' expr ')' !! 209 num_other = 0;
327 { !! 210 for (;;) {
328 if (fpclassify($5.val) == FP_ZERO) { !! 211 YYSTYPE val;
329 /* !! 212 int tok = expr__lex(&val, &p);
330 * Division by constant zero a !! 213 if (tok == 0) {
331 * are necessary. !! 214 err = 0;
332 */ !! 215 break;
333 assert($5.ids == NULL); !! 216 }
334 $$.val = 0.0; !! 217 if (tok == ID && !already_seen(val.id, one, *other, num_other)) {
335 $$.ids = NULL; !! 218 if (num_other >= EXPR_MAX_OTHER - 1) {
336 ids__free($3.ids); !! 219 pr_debug("Too many extra events in %s\n", orig);
337 } else if (!compute_ids || (is_const($ !! 220 break;
338 assert($3.ids == NULL); !! 221 }
339 assert($5.ids == NULL); !! 222 (*other)[num_other] = strdup(val.id);
340 $$.val = $3.val / $5.val; !! 223 if (!(*other)[num_other])
341 $$.ids = NULL; !! 224 return -1;
342 } else { !! 225 num_other++;
343 /* LHS and/or RHS need computi !! 226 }
344 $$ = union_expr($3, $5); !! 227 }
345 } !! 228 (*other)[num_other] = NULL;
346 } !! 229 *num_otherp = num_other;
347 | '-' expr %prec NEG !! 230 if (err) {
348 { !! 231 *num_otherp = 0;
349 $$.val = -$2.val; !! 232 free(*other);
350 $$.ids = $2.ids; !! 233 *other = NULL;
351 } <<
352 | '(' if_expr ')' <<
353 { <<
354 $$ = $2; <<
355 } <<
356 | MIN '(' expr ',' expr ')' <<
357 { <<
358 if (!compute_ids) { <<
359 $$.val = $3.val < $5.val ? $3. <<
360 $$.ids = NULL; <<
361 } else { <<
362 $$ = union_expr($3, $5); <<
363 } <<
364 } <<
365 | MAX '(' expr ',' expr ')' <<
366 { <<
367 if (!compute_ids) { <<
368 $$.val = $3.val > $5.val ? $3. <<
369 $$.ids = NULL; <<
370 } else { <<
371 $$ = union_expr($3, $5); <<
372 } 234 }
>> 235 return err;
373 } 236 }
374 | LITERAL <<
375 { <<
376 $$.val = $1; <<
377 $$.ids = NULL; <<
378 } <<
379 ; <<
380 <<
381 %% <<
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.