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 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_LONG_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 		RESULT.val = (long)LHS.val OP (long)RHS.val;		\
131 		RESULT.ids = NULL;					\
132 	} else {							\
133 	        RESULT = union_expr(LHS, RHS);				\
134 	}
135 
136 #define BINARY_OP(RESULT, OP, LHS, RHS)					\
137 	if (!compute_ids || (is_const(LHS.val) && is_const(RHS.val))) { \
138 		assert(LHS.ids == NULL);				\
139 		assert(RHS.ids == NULL);				\
140 		RESULT.val = LHS.val OP RHS.val;			\
141 		RESULT.ids = NULL;					\
142 	} else {							\
143 	        RESULT = union_expr(LHS, RHS);				\
144 	}
145 
146 %}
147 %%
148 
149 start: if_expr
150 {
151 	if (compute_ids)
152 		ctx->ids = ids__union($1.ids, ctx->ids);
153 
154 	if (final_val)
155 		*final_val = $1.val;
156 }
157 ;
158 
159 if_expr: expr IF expr ELSE expr
160 {
161 	if (fpclassify($3.val) == FP_ZERO) {
162 		/*
163 		 * The IF expression evaluated to 0 so treat as false, take the
164 		 * ELSE and discard everything else.
165 		 */
166 		$$.val = $5.val;
167 		$$.ids = $5.ids;
168 		ids__free($1.ids);
169 		ids__free($3.ids);
170 	} else if (!compute_ids || is_const($3.val)) {
171 		/*
172 		 * If ids aren't computed then treat the expression as true. If
173 		 * ids are being computed and the IF expr is a non-zero
174 		 * constant, then also evaluate the true case.
175 		 */
176 		$$.val = $1.val;
177 		$$.ids = $1.ids;
178 		ids__free($3.ids);
179 		ids__free($5.ids);
180 	} else if ($1.val == $5.val) {
181 		/*
182 		 * LHS == RHS, so both are an identical constant. No need to
183 		 * evaluate any events.
184 		 */
185 		$$.val = $1.val;
186 		$$.ids = NULL;
187 		ids__free($1.ids);
188 		ids__free($3.ids);
189 		ids__free($5.ids);
190 	} else {
191 		/*
192 		 * Value is either the LHS or RHS and we need the IF expression
193 		 * to compute it.
194 		 */
195 		$$ = union_expr($1, union_expr($3, $5));
196 	}
197 }
198 | expr
199 ;
200 
201 expr: NUMBER
202 {
203 	$$.val = $1;
204 	$$.ids = NULL;
205 }
206 | ID				{ $$ = handle_id(ctx, $1, compute_ids, /*source_count=*/false); }
207 | SOURCE_COUNT '(' ID ')'	{ $$ = handle_id(ctx, $3, compute_ids, /*source_count=*/true); }
208 | expr '|' expr { BINARY_LONG_OP($$, |, $1, $3); }
209 | expr '&' expr { BINARY_LONG_OP($$, &, $1, $3); }
210 | expr '^' expr { BINARY_LONG_OP($$, ^, $1, $3); }
211 | expr '<' expr { BINARY_OP($$, <, $1, $3); }
212 | expr '>' expr { BINARY_OP($$, >, $1, $3); }
213 | expr '+' expr { BINARY_OP($$, +, $1, $3); }
214 | expr '-' expr { BINARY_OP($$, -, $1, $3); }
215 | expr '*' expr { BINARY_OP($$, *, $1, $3); }
216 | expr '/' expr
217 {
218 	if (fpclassify($3.val) == FP_ZERO) {
219 		pr_debug("division by zero\n");
220 		YYABORT;
221 	} else if (!compute_ids || (is_const($1.val) && is_const($3.val))) {
222 		assert($1.ids == NULL);
223 		assert($3.ids == NULL);
224 		$$.val = $1.val / $3.val;
225 		$$.ids = NULL;
226 	} else {
227 		/* LHS and/or RHS need computing from event IDs so union. */
228 		$$ = union_expr($1, $3);
229 	}
230 }
231 | expr '%' expr
232 {
233 	if (fpclassify($3.val) == FP_ZERO) {
234 		pr_debug("division by zero\n");
235 		YYABORT;
236 	} else if (!compute_ids || (is_const($1.val) && is_const($3.val))) {
237 		assert($1.ids == NULL);
238 		assert($3.ids == NULL);
239 		$$.val = (long)$1.val % (long)$3.val;
240 		$$.ids = NULL;
241 	} else {
242 		/* LHS and/or RHS need computing from event IDs so union. */
243 		$$ = union_expr($1, $3);
244 	}
245 }
246 | D_RATIO '(' expr ',' expr ')'
247 {
248 	if (fpclassify($5.val) == FP_ZERO) {
249 		/*
250 		 * Division by constant zero always yields zero and no events
251 		 * are necessary.
252 		 */
253 		assert($5.ids == NULL);
254 		$$.val = 0.0;
255 		$$.ids = NULL;
256 		ids__free($3.ids);
257 	} else if (!compute_ids || (is_const($3.val) && is_const($5.val))) {
258 		assert($3.ids == NULL);
259 		assert($5.ids == NULL);
260 		$$.val = $3.val / $5.val;
261 		$$.ids = NULL;
262 	} else {
263 		/* LHS and/or RHS need computing from event IDs so union. */
264 		$$ = union_expr($3, $5);
265 	}
266 }
267 | '-' expr %prec NEG
268 {
269 	$$.val = -$2.val;
270 	$$.ids = $2.ids;
271 }
272 | '(' if_expr ')'
273 {
274 	$$ = $2;
275 }
276 | MIN '(' expr ',' expr ')'
277 {
278 	if (!compute_ids) {
279 		$$.val = $3.val < $5.val ? $3.val : $5.val;
280 		$$.ids = NULL;
281 	} else {
282 		$$ = union_expr($3, $5);
283 	}
284 }
285 | MAX '(' expr ',' expr ')'
286 {
287 	if (!compute_ids) {
288 		$$.val = $3.val > $5.val ? $3.val : $5.val;
289 		$$.ids = NULL;
290 	} else {
291 		$$ = union_expr($3, $5);
292 	}
293 }
294 | LITERAL
295 {
296 	$$.val = $1;
297 	$$.ids = NULL;
298 }
299 ;
300 
301 %%
302