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%{
 56static 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? */
 72static bool is_const(double val)
 73{
 74	return isfinite(val);
 75}
 76
 77static 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
 86static 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
149start: 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
159if_expr: expr IF expr ELSE if_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
201expr: 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%%