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>
14 %} <<
15 9
16 %define api.pure full !! 10 #define MAXIDLEN 256
>> 11 %}
17 12
>> 13 %pure-parser
18 %parse-param { double *final_val } 14 %parse-param { double *final_val }
19 %parse-param { struct expr_parse_ctx *ctx } !! 15 %parse-param { struct parse_ctx *ctx }
20 %parse-param { bool compute_ids } !! 16 %parse-param { const char **pp }
21 %parse-param {void *scanner} !! 17 %lex-param { const char **pp }
22 %lex-param {void* scanner} <<
23 18
24 %union { 19 %union {
25 double num; !! 20 double num;
26 char *str; !! 21 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 } 22 }
43 23
44 %token ID NUMBER MIN MAX IF ELSE LITERAL D_RAT !! 24 %token <num> NUMBER
>> 25 %token <id> ID
>> 26 %token MIN MAX IF ELSE SMT_ON
45 %left MIN MAX IF 27 %left MIN MAX IF
46 %left '|' 28 %left '|'
47 %left '^' 29 %left '^'
48 %left '&' 30 %left '&'
49 %left '<' '>' <<
50 %left '-' '+' 31 %left '-' '+'
51 %left '*' '/' '%' 32 %left '*' '/' '%'
52 %left NEG NOT 33 %left NEG NOT
53 %type <num> NUMBER LITERAL !! 34 %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 35
59 %{ 36 %{
60 static void expr_error(double *final_val __may !! 37 static int expr__lex(YYSTYPE *res, const char **pp);
61 struct expr_parse_ctx * !! 38
62 bool compute_ids __mayb !! 39 static void expr__error(double *final_val __maybe_unused,
63 void *scanner __maybe_u !! 40 struct parse_ctx *ctx __maybe_unused,
>> 41 const char **pp __maybe_unused,
64 const char *s) 42 const char *s)
65 { 43 {
66 pr_debug("%s\n", s); 44 pr_debug("%s\n", s);
67 } 45 }
68 46
69 /* !! 47 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 { 48 {
83 struct ids result = { !! 49 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 50
102 result.val = NAN; !! 51 for (i = 0; i < ctx->num_ids; i++) {
103 if (expr__resolve_id(ctx, id, !! 52 if (!strcasecmp(ctx->ids[i].name, id)) {
104 result.val = source_co !! 53 *val = ctx->ids[i].val;
105 ? expr_id_data !! 54 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 } 55 }
121 } 56 }
122 return result; !! 57 return -1;
123 } 58 }
124 59
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 %} 60 %}
145 %% 61 %%
146 62
147 start: if_expr !! 63 all_expr: if_expr { *final_val = $1; }
148 { !! 64 ;
149 if (compute_ids) <<
150 ctx->ids = ids__union($1.ids, <<
151 65
152 if (final_val) !! 66 if_expr:
153 *final_val = $1.val; !! 67 expr IF expr ELSE expr { $$ = $3 ? $1 : $5; }
154 } !! 68 | expr
155 ; !! 69 ;
>> 70
>> 71 expr: NUMBER
>> 72 | ID { if (lookup_id(ctx, $1, &$$) < 0) {
>> 73 pr_debug("%s not found\n", $1);
>> 74 YYABORT;
>> 75 }
>> 76 }
>> 77 | expr '|' expr { $$ = (long)$1 | (long)$3; }
>> 78 | expr '&' expr { $$ = (long)$1 & (long)$3; }
>> 79 | expr '^' expr { $$ = (long)$1 ^ (long)$3; }
>> 80 | expr '+' expr { $$ = $1 + $3; }
>> 81 | expr '-' expr { $$ = $1 - $3; }
>> 82 | expr '*' expr { $$ = $1 * $3; }
>> 83 | expr '/' expr { if ($3 == 0) YYABORT; $$ = $1 / $3; }
>> 84 | expr '%' expr { if ((long)$3 == 0) YYABORT; $$ = (long)$1 % (long)$3; }
>> 85 | '-' expr %prec NEG { $$ = -$2; }
>> 86 | '(' if_expr ')' { $$ = $2; }
>> 87 | MIN '(' expr ',' expr ')' { $$ = $3 < $5 ? $3 : $5; }
>> 88 | MAX '(' expr ',' expr ')' { $$ = $3 > $5 ? $3 : $5; }
>> 89 | SMT_ON { $$ = smt_on() > 0; }
>> 90 ;
156 91
157 if_expr: expr IF expr ELSE if_expr !! 92 %%
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 93
199 expr: NUMBER !! 94 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 { 95 {
214 $$.val = expr__strcmp_cpuid_str(ctx, c !! 96 char *dst = res->id;
215 $$.ids = NULL; !! 97 const char *s = p;
216 free($3); !! 98
217 } !! 99 if (*p == '#')
218 | expr '|' expr !! 100 *dst++ = *p++;
219 { !! 101
220 if (is_const($1.val) && is_const($3.va !! 102 while (isalnum(*p) || *p == '_' || *p == '.' || *p == ':' || *p == '@' || *p == '\\') {
221 assert($1.ids == NULL); !! 103 if (p - s >= MAXIDLEN)
222 assert($3.ids == NULL); !! 104 return -1;
223 $$.ids = NULL; !! 105 /*
224 $$.val = (fpclassify($1.val) = !! 106 * Allow @ instead of / to be able to specify pmu/event/ without
225 } else if (is_const($1.val)) { !! 107 * conflicts with normal division.
226 assert($1.ids == NULL); !! 108 */
227 if (fpclassify($1.val) == FP_Z !! 109 if (*p == '@')
228 $$ = $3; !! 110 *dst++ = '/';
229 } else { !! 111 else if (*p == '\\')
230 $$.val = 1; !! 112 *dst++ = *++p;
231 $$.ids = NULL; !! 113 else
232 ids__free($3.ids); !! 114 *dst++ = *p;
233 } !! 115 p++;
234 } else if (is_const($3.val)) { !! 116 }
235 assert($3.ids == NULL); !! 117 *dst = 0;
236 if (fpclassify($3.val) == FP_Z !! 118 *pp = p;
237 $$ = $1; !! 119 dst = res->id;
238 } else { !! 120 switch (dst[0]) {
239 $$.val = 1; !! 121 case 'm':
240 $$.ids = NULL; !! 122 if (!strcmp(dst, "min"))
241 ids__free($1.ids); !! 123 return MIN;
242 } !! 124 if (!strcmp(dst, "max"))
243 } else { !! 125 return MAX;
244 $$ = union_expr($1, $3); !! 126 break;
245 } !! 127 case 'i':
246 } !! 128 if (!strcmp(dst, "if"))
247 | expr '&' expr !! 129 return IF;
248 { !! 130 break;
249 if (is_const($1.val) && is_const($3.va !! 131 case 'e':
250 assert($1.ids == NULL); !! 132 if (!strcmp(dst, "else"))
251 assert($3.ids == NULL); !! 133 return ELSE;
252 $$.val = (fpclassify($1.val) ! !! 134 break;
253 $$.ids = NULL; !! 135 case '#':
254 } else if (is_const($1.val)) { !! 136 if (!strcasecmp(dst, "#smt_on"))
255 assert($1.ids == NULL); !! 137 return SMT_ON;
256 if (fpclassify($1.val) != FP_Z !! 138 break;
257 $$ = $3; !! 139 }
258 } else { !! 140 return ID;
259 $$.val = 0; !! 141 }
260 $$.ids = NULL; !! 142
261 ids__free($3.ids); !! 143 static int expr__lex(YYSTYPE *res, const char **pp)
262 } !! 144 {
263 } else if (is_const($3.val)) { !! 145 int tok;
264 assert($3.ids == NULL); !! 146 const char *s;
265 if (fpclassify($3.val) != FP_Z !! 147 const char *p = *pp;
266 $$ = $1; !! 148
267 } else { !! 149 while (isspace(*p))
268 $$.val = 0; !! 150 p++;
269 $$.ids = NULL; !! 151 s = p;
270 ids__free($1.ids); !! 152 switch (*p++) {
271 } !! 153 case '#':
272 } else { !! 154 case 'a' ... 'z':
273 $$ = union_expr($1, $3); !! 155 case 'A' ... 'Z':
274 } !! 156 return expr__symbol(res, p - 1, pp);
275 } !! 157 case '0' ... '9': case '.':
276 | expr '^' expr !! 158 res->num = strtod(s, (char **)&p);
277 { !! 159 tok = NUMBER;
278 if (is_const($1.val) && is_const($3.va !! 160 break;
279 assert($1.ids == NULL); !! 161 default:
280 assert($3.ids == NULL); !! 162 tok = *s;
281 $$.val = (fpclassify($1.val) = !! 163 break;
282 $$.ids = NULL; !! 164 }
283 } else { !! 165 *pp = p;
284 $$ = union_expr($1, $3); !! 166 return tok;
285 } !! 167 }
286 } !! 168
287 | expr '<' expr { BINARY_OP($$, <, $1, $3); } !! 169 /* Caller must make sure id is allocated */
288 | expr '>' expr { BINARY_OP($$, >, $1, $3); } !! 170 void expr__add_id(struct parse_ctx *ctx, const char *name, double val)
289 | expr '+' expr { BINARY_OP($$, +, $1, $3); } !! 171 {
290 | expr '-' expr { BINARY_OP($$, -, $1, $3); } !! 172 int idx;
291 | expr '*' expr { BINARY_OP($$, *, $1, $3); } !! 173 assert(ctx->num_ids < MAX_PARSE_ID);
292 | expr '/' expr !! 174 idx = ctx->num_ids++;
293 { !! 175 ctx->ids[idx].name = name;
294 if (fpclassify($3.val) == FP_ZERO) { !! 176 ctx->ids[idx].val = val;
295 pr_debug("division by zero\n") !! 177 }
296 assert($3.ids == NULL); !! 178
297 if (compute_ids) !! 179 void expr__ctx_init(struct parse_ctx *ctx)
298 ids__free($1.ids); !! 180 {
299 $$.val = NAN; !! 181 ctx->num_ids = 0;
300 $$.ids = NULL; !! 182 }
301 } else if (!compute_ids || (is_const($ !! 183
302 assert($1.ids == NULL); !! 184 static bool already_seen(const char *val, const char *one, const char **other,
303 assert($3.ids == NULL); !! 185 int num_other)
304 $$.val = $1.val / $3.val; !! 186 {
305 $$.ids = NULL; !! 187 int i;
306 } else { !! 188
307 /* LHS and/or RHS need computi !! 189 if (one && !strcasecmp(one, val))
308 $$ = union_expr($1, $3); !! 190 return true;
309 } !! 191 for (i = 0; i < num_other; i++)
310 } !! 192 if (!strcasecmp(other[i], val))
311 | expr '%' expr !! 193 return true;
312 { !! 194 return false;
313 if (fpclassify($3.val) == FP_ZERO) { !! 195 }
314 pr_debug("division by zero\n") !! 196
315 YYABORT; !! 197 int expr__find_other(const char *p, const char *one, const char ***other,
316 } else if (!compute_ids || (is_const($ !! 198 int *num_otherp)
317 assert($1.ids == NULL); !! 199 {
318 assert($3.ids == NULL); !! 200 const char *orig = p;
319 $$.val = (long)$1.val % (long) !! 201 int err = -1;
320 $$.ids = NULL; !! 202 int num_other;
321 } else { !! 203
322 /* LHS and/or RHS need computi !! 204 *other = malloc((EXPR_MAX_OTHER + 1) * sizeof(char *));
323 $$ = union_expr($1, $3); !! 205 if (!*other)
324 } !! 206 return -1;
325 } !! 207
326 | D_RATIO '(' expr ',' expr ')' !! 208 num_other = 0;
327 { !! 209 for (;;) {
328 if (fpclassify($5.val) == FP_ZERO) { !! 210 YYSTYPE val;
329 /* !! 211 int tok = expr__lex(&val, &p);
330 * Division by constant zero a !! 212 if (tok == 0) {
331 * are necessary. !! 213 err = 0;
332 */ !! 214 break;
333 assert($5.ids == NULL); !! 215 }
334 $$.val = 0.0; !! 216 if (tok == ID && !already_seen(val.id, one, *other, num_other)) {
335 $$.ids = NULL; !! 217 if (num_other >= EXPR_MAX_OTHER - 1) {
336 ids__free($3.ids); !! 218 pr_debug("Too many extra events in %s\n", orig);
337 } else if (!compute_ids || (is_const($ !! 219 break;
338 assert($3.ids == NULL); !! 220 }
339 assert($5.ids == NULL); !! 221 (*other)[num_other] = strdup(val.id);
340 $$.val = $3.val / $5.val; !! 222 if (!(*other)[num_other])
341 $$.ids = NULL; !! 223 return -1;
342 } else { !! 224 num_other++;
343 /* LHS and/or RHS need computi !! 225 }
344 $$ = union_expr($3, $5); !! 226 }
345 } !! 227 (*other)[num_other] = NULL;
346 } !! 228 *num_otherp = num_other;
347 | '-' expr %prec NEG !! 229 if (err) {
348 { !! 230 *num_otherp = 0;
349 $$.val = -$2.val; !! 231 free(*other);
350 $$.ids = $2.ids; !! 232 *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 } 233 }
>> 234 return err;
373 } 235 }
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.