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 #include "expr-bison.h"
11 int expr_lex(YYSTYPE * yylval_param , void *yyscanner);
12 %}
13 
14 %define api.pure full
15 
16 %parse-param { double *final_val }
17 %parse-param { struct expr_parse_ctx *ctx }
18 %parse-param { bool compute_ids }
19 %parse-param {void *scanner}
20 %lex-param {void* scanner}
21 
22 %union {
23 	double	 num;
24 	char	*str;
25 	struct ids {
26 		/*
27 		 * When creating ids, holds the working set of event ids. NULL
28 		 * implies the set is empty.
29 		 */
30 		struct hashmap *ids;
31 		/*
32 		 * The metric value. When not creating ids this is the value
33 		 * read from a counter, a constant or some computed value. When
34 		 * creating ids the value is either a constant or BOTTOM. NAN is
35 		 * used as the special BOTTOM value, representing a "set of all
36 		 * values" case.
37 		 */
38 		double val;
39 	} ids;
40 }
41 
42 %token ID NUMBER MIN MAX IF ELSE LITERAL D_RATIO SOURCE_COUNT HAS_EVENT STRCMP_CPUID_STR EXPR_ERROR
43 %left MIN MAX IF
44 %left '|'
45 %left '^'
46 %left '&'
47 %left '<' '>'
48 %left '-' '+'
49 %left '*' '/' '%'
50 %left NEG NOT
51 %type <num> NUMBER LITERAL
52 %type <str> ID
53 %destructor { free ($$); } <str>
54 %type <ids> expr if_expr
55 %destructor { ids__free($$.ids); } <ids>
56 
57 %{
58 static void expr_error(double *final_val __maybe_unused,
59 		       struct expr_parse_ctx *ctx __maybe_unused,
60 		       bool compute_ids __maybe_unused,
61 		       void *scanner __maybe_unused,
62 		       const char *s)
63 {
64 	pr_debug("%s\n", s);
65 }
66 
67 /*
68  * During compute ids, the special "bottom" value uses NAN to represent the set
69  * of all values. NAN is selected as it isn't a useful constant value.
70  */
71 #define BOTTOM NAN
72 
73 /* During computing ids, does val represent a constant (non-BOTTOM) value? */
74 static bool is_const(double val)
75 {
76 	return isfinite(val);
77 }
78 
79 static struct ids union_expr(struct ids ids1, struct ids ids2)
80 {
81 	struct ids result = {
82 		.val = BOTTOM,
83 		.ids = ids__union(ids1.ids, ids2.ids),
84 	};
85 	return result;
86 }
87 
88 static struct ids handle_id(struct expr_parse_ctx *ctx, char *id,
89 			    bool compute_ids, bool source_count)
90 {
91 	struct ids result;
92 
93 	if (!compute_ids) {
94 		/*
95 		 * Compute the event's value from ID. If the ID isn't known then
96 		 * it isn't used to compute the formula so set to NAN.
97 		 */
98 		struct expr_id_data *data;
99 
100 		result.val = NAN;
101 		if (expr__resolve_id(ctx, id, &data) == 0) {
102 			result.val = source_count
103 				? expr_id_data__source_count(data)
104 				: expr_id_data__value(data);
105 		}
106 		result.ids = NULL;
107 		free(id);
108 	} else {
109 		/*
110 		 * Set the value to BOTTOM to show that any value is possible
111 		 * when the event is computed. Create a set of just the ID.
112 		 */
113 		result.val = BOTTOM;
114 		result.ids = ids__new();
115 		if (!result.ids || ids__insert(result.ids, id)) {
116 			pr_err("Error creating IDs for '%s'", id);
117 			free(id);
118 		}
119 	}
120 	return result;
121 }
122 
123 /*
124  * If we're not computing ids or $1 and $3 are constants, compute the new
125  * constant value using OP. Its invariant that there are no ids.  If computing
126  * ids for non-constants union the set of IDs that must be computed.
127  */
128 #define BINARY_OP(RESULT, OP, LHS, RHS)					\
129 	if (!compute_ids || (is_const(LHS.val) && is_const(RHS.val))) { \
130 		assert(LHS.ids == NULL);				\
131 		assert(RHS.ids == NULL);				\
132 		if (isnan(LHS.val) || isnan(RHS.val)) {			\
133 			RESULT.val = NAN;				\
134 		} else {						\
135 			RESULT.val = LHS.val OP RHS.val;		\
136 		}							\
137 		RESULT.ids = NULL;					\
138 	} else {							\
139 	        RESULT = union_expr(LHS, RHS);				\
140 	}
141 
142 %}
143 %%
144 
145 start: if_expr
146 {
147 	if (compute_ids)
148 		ctx->ids = ids__union($1.ids, ctx->ids);
149 
150 	if (final_val)
151 		*final_val = $1.val;
152 }
153 ;
154 
155 if_expr: expr IF expr ELSE if_expr
156 {
157 	if (fpclassify($3.val) == FP_ZERO) {
158 		/*
159 		 * The IF expression evaluated to 0 so treat as false, take the
160 		 * ELSE and discard everything else.
161 		 */
162 		$$.val = $5.val;
163 		$$.ids = $5.ids;
164 		ids__free($1.ids);
165 		ids__free($3.ids);
166 	} else if (!compute_ids || is_const($3.val)) {
167 		/*
168 		 * If ids aren't computed then treat the expression as true. If
169 		 * ids are being computed and the IF expr is a non-zero
170 		 * constant, then also evaluate the true case.
171 		 */
172 		$$.val = $1.val;
173 		$$.ids = $1.ids;
174 		ids__free($3.ids);
175 		ids__free($5.ids);
176 	} else if ($1.val == $5.val) {
177 		/*
178 		 * LHS == RHS, so both are an identical constant. No need to
179 		 * evaluate any events.
180 		 */
181 		$$.val = $1.val;
182 		$$.ids = NULL;
183 		ids__free($1.ids);
184 		ids__free($3.ids);
185 		ids__free($5.ids);
186 	} else {
187 		/*
188 		 * Value is either the LHS or RHS and we need the IF expression
189 		 * to compute it.
190 		 */
191 		$$ = union_expr($1, union_expr($3, $5));
192 	}
193 }
194 | expr
195 ;
196 
197 expr: NUMBER
198 {
199 	$$.val = $1;
200 	$$.ids = NULL;
201 }
202 | ID				{ $$ = handle_id(ctx, $1, compute_ids, /*source_count=*/false); }
203 | SOURCE_COUNT '(' ID ')'	{ $$ = handle_id(ctx, $3, compute_ids, /*source_count=*/true); }
204 | HAS_EVENT '(' ID ')'
205 {
206 	$$.val = expr__has_event(ctx, compute_ids, $3);
207 	$$.ids = NULL;
208 	free($3);
209 }
210 | STRCMP_CPUID_STR '(' ID ')'
211 {
212 	$$.val = expr__strcmp_cpuid_str(ctx, compute_ids, $3);
213 	$$.ids = NULL;
214 	free($3);
215 }
216 | expr '|' expr
217 {
218 	if (is_const($1.val) && is_const($3.val)) {
219 		assert($1.ids == NULL);
220 		assert($3.ids == NULL);
221 		$$.ids = NULL;
222 		$$.val = (fpclassify($1.val) == FP_ZERO && fpclassify($3.val) == FP_ZERO) ? 0 : 1;
223 	} else if (is_const($1.val)) {
224 		assert($1.ids == NULL);
225 		if (fpclassify($1.val) == FP_ZERO) {
226 			$$ = $3;
227 		} else {
228 			$$.val = 1;
229 			$$.ids = NULL;
230 			ids__free($3.ids);
231 		}
232 	} else if (is_const($3.val)) {
233 		assert($3.ids == NULL);
234 		if (fpclassify($3.val) == FP_ZERO) {
235 			$$ = $1;
236 		} else {
237 			$$.val = 1;
238 			$$.ids = NULL;
239 			ids__free($1.ids);
240 		}
241 	} else {
242 		$$ = union_expr($1, $3);
243 	}
244 }
245 | expr '&' expr
246 {
247 	if (is_const($1.val) && is_const($3.val)) {
248 		assert($1.ids == NULL);
249 		assert($3.ids == NULL);
250 		$$.val = (fpclassify($1.val) != FP_ZERO && fpclassify($3.val) != FP_ZERO) ? 1 : 0;
251 		$$.ids = NULL;
252 	} else if (is_const($1.val)) {
253 		assert($1.ids == NULL);
254 		if (fpclassify($1.val) != FP_ZERO) {
255 			$$ = $3;
256 		} else {
257 			$$.val = 0;
258 			$$.ids = NULL;
259 			ids__free($3.ids);
260 		}
261 	} else if (is_const($3.val)) {
262 		assert($3.ids == NULL);
263 		if (fpclassify($3.val) != FP_ZERO) {
264 			$$ = $1;
265 		} else {
266 			$$.val = 0;
267 			$$.ids = NULL;
268 			ids__free($1.ids);
269 		}
270 	} else {
271 		$$ = union_expr($1, $3);
272 	}
273 }
274 | expr '^' expr
275 {
276 	if (is_const($1.val) && is_const($3.val)) {
277 		assert($1.ids == NULL);
278 		assert($3.ids == NULL);
279 		$$.val = (fpclassify($1.val) == FP_ZERO) != (fpclassify($3.val) == FP_ZERO) ? 1 : 0;
280 		$$.ids = NULL;
281 	} else {
282 		$$ = union_expr($1, $3);
283 	}
284 }
285 | expr '<' expr { BINARY_OP($$, <, $1, $3); }
286 | expr '>' expr { BINARY_OP($$, >, $1, $3); }
287 | expr '+' expr { BINARY_OP($$, +, $1, $3); }
288 | expr '-' expr { BINARY_OP($$, -, $1, $3); }
289 | expr '*' expr { BINARY_OP($$, *, $1, $3); }
290 | expr '/' expr
291 {
292 	if (fpclassify($3.val) == FP_ZERO) {
293 		pr_debug("division by zero\n");
294 		assert($3.ids == NULL);
295 		if (compute_ids)
296 			ids__free($1.ids);
297 		$$.val = NAN;
298 		$$.ids = NULL;
299 	} else if (!compute_ids || (is_const($1.val) && is_const($3.val))) {
300 		assert($1.ids == NULL);
301 		assert($3.ids == NULL);
302 		$$.val = $1.val / $3.val;
303 		$$.ids = NULL;
304 	} else {
305 		/* LHS and/or RHS need computing from event IDs so union. */
306 		$$ = union_expr($1, $3);
307 	}
308 }
309 | expr '%' expr
310 {
311 	if (fpclassify($3.val) == FP_ZERO) {
312 		pr_debug("division by zero\n");
313 		YYABORT;
314 	} else if (!compute_ids || (is_const($1.val) && is_const($3.val))) {
315 		assert($1.ids == NULL);
316 		assert($3.ids == NULL);
317 		$$.val = (long)$1.val % (long)$3.val;
318 		$$.ids = NULL;
319 	} else {
320 		/* LHS and/or RHS need computing from event IDs so union. */
321 		$$ = union_expr($1, $3);
322 	}
323 }
324 | D_RATIO '(' expr ',' expr ')'
325 {
326 	if (fpclassify($5.val) == FP_ZERO) {
327 		/*
328 		 * Division by constant zero always yields zero and no events
329 		 * are necessary.
330 		 */
331 		assert($5.ids == NULL);
332 		$$.val = 0.0;
333 		$$.ids = NULL;
334 		ids__free($3.ids);
335 	} else if (!compute_ids || (is_const($3.val) && is_const($5.val))) {
336 		assert($3.ids == NULL);
337 		assert($5.ids == NULL);
338 		$$.val = $3.val / $5.val;
339 		$$.ids = NULL;
340 	} else {
341 		/* LHS and/or RHS need computing from event IDs so union. */
342 		$$ = union_expr($3, $5);
343 	}
344 }
345 | '-' expr %prec NEG
346 {
347 	$$.val = -$2.val;
348 	$$.ids = $2.ids;
349 }
350 | '(' if_expr ')'
351 {
352 	$$ = $2;
353 }
354 | MIN '(' expr ',' expr ')'
355 {
356 	if (!compute_ids) {
357 		$$.val = $3.val < $5.val ? $3.val : $5.val;
358 		$$.ids = NULL;
359 	} else {
360 		$$ = union_expr($3, $5);
361 	}
362 }
363 | MAX '(' expr ',' expr ')'
364 {
365 	if (!compute_ids) {
366 		$$.val = $3.val > $5.val ? $3.val : $5.val;
367 		$$.ids = NULL;
368 	} else {
369 		$$ = union_expr($3, $5);
370 	}
371 }
372 | LITERAL
373 {
374 	$$.val = $1;
375 	$$.ids = NULL;
376 }
377 ;
378 
379 %%
380