[linux-2.6-block.git] / tools / perf / util / expr.y

/* Simple expression parser */
%{
#ifndef NDEBUG
#define YYDEBUG 1
#endif
#include <assert.h>
#include <math.h>
#include <stdlib.h>
#include "util/debug.h"
#define IN_EXPR_Y 1
#include "expr.h"
#include "expr-bison.h"
int expr_lex(YYSTYPE * yylval_param , void *yyscanner);
%}

%define api.pure full

%parse-param { double *final_val }
%parse-param { struct expr_parse_ctx *ctx }
%parse-param { bool compute_ids }
%parse-param {void *scanner}
%lex-param {void* scanner}

%union {
	double	 num;
	char	*str;
	struct ids {
		/*
		 * When creating ids, holds the working set of event ids. NULL
		 * implies the set is empty.
		 */
		struct hashmap *ids;
		/*
		 * The metric value. When not creating ids this is the value
		 * read from a counter, a constant or some computed value. When
		 * creating ids the value is either a constant or BOTTOM. NAN is
		 * used as the special BOTTOM value, representing a "set of all
		 * values" case.
		 */
		double val;
	} ids;
}

%token ID NUMBER MIN MAX IF ELSE LITERAL D_RATIO SOURCE_COUNT HAS_EVENT STRCMP_CPUID_STR EXPR_ERROR
%left MIN MAX IF
%left '|'
%left '^'
%left '&'
%left '<' '>'
%left '-' '+'
%left '*' '/' '%'
%left NEG NOT
%type <num> NUMBER LITERAL
%type <str> ID
%destructor { free ($$); } <str>
%type <ids> expr if_expr
%destructor { ids__free($$.ids); } <ids>

%{
static void expr_error(double *final_val __maybe_unused,
		       struct expr_parse_ctx *ctx __maybe_unused,
		       bool compute_ids __maybe_unused,
		       void *scanner __maybe_unused,
		       const char *s)
{
	pr_debug("%s\n", s);
}

/*
 * During compute ids, the special "bottom" value uses NAN to represent the set
 * of all values. NAN is selected as it isn't a useful constant value.
 */
#define BOTTOM NAN

/* During computing ids, does val represent a constant (non-BOTTOM) value? */
static bool is_const(double val)
{
	return isfinite(val);
}

static struct ids union_expr(struct ids ids1, struct ids ids2)
{
	struct ids result = {
		.val = BOTTOM,
		.ids = ids__union(ids1.ids, ids2.ids),
	};
	return result;
}

static struct ids handle_id(struct expr_parse_ctx *ctx, char *id,
			    bool compute_ids, bool source_count)
{
	struct ids result;

	if (!compute_ids) {
		/*
		 * Compute the event's value from ID. If the ID isn't known then
		 * it isn't used to compute the formula so set to NAN.
		 */
		struct expr_id_data *data;

		result.val = NAN;
		if (expr__resolve_id(ctx, id, &data) == 0) {
			result.val = source_count
				? expr_id_data__source_count(data)
				: expr_id_data__value(data);
		}
		result.ids = NULL;
		free(id);
	} else {
		/*
		 * Set the value to BOTTOM to show that any value is possible
		 * when the event is computed. Create a set of just the ID.
		 */
		result.val = BOTTOM;
		result.ids = ids__new();
		if (!result.ids || ids__insert(result.ids, id)) {
			pr_err("Error creating IDs for '%s'", id);
			free(id);
		}
	}
	return result;
}

/*
 * If we're not computing ids or $1 and $3 are constants, compute the new
 * constant value using OP. Its invariant that there are no ids.  If computing
 * ids for non-constants union the set of IDs that must be computed.
 */
#define BINARY_OP(RESULT, OP, LHS, RHS)					\
	if (!compute_ids || (is_const(LHS.val) && is_const(RHS.val))) { \
		assert(LHS.ids == NULL);				\
		assert(RHS.ids == NULL);				\
		if (isnan(LHS.val) || isnan(RHS.val)) {			\
			RESULT.val = NAN;				\
		} else {						\
			RESULT.val = LHS.val OP RHS.val;		\
		}							\
		RESULT.ids = NULL;					\
	} else {							\
	        RESULT = union_expr(LHS, RHS);				\
	}

%}
%%

start: if_expr
{
	if (compute_ids)
		ctx->ids = ids__union($1.ids, ctx->ids);

	if (final_val)
		*final_val = $1.val;
}
;

if_expr: expr IF expr ELSE if_expr
{
	if (fpclassify($3.val) == FP_ZERO) {
		/*
		 * The IF expression evaluated to 0 so treat as false, take the
		 * ELSE and discard everything else.
		 */
		$$.val = $5.val;
		$$.ids = $5.ids;
		ids__free($1.ids);
		ids__free($3.ids);
	} else if (!compute_ids || is_const($3.val)) {
		/*
		 * If ids aren't computed then treat the expression as true. If
		 * ids are being computed and the IF expr is a non-zero
		 * constant, then also evaluate the true case.
		 */
		$$.val = $1.val;
		$$.ids = $1.ids;
		ids__free($3.ids);
		ids__free($5.ids);
	} else if ($1.val == $5.val) {
		/*
		 * LHS == RHS, so both are an identical constant. No need to
		 * evaluate any events.
		 */
		$$.val = $1.val;
		$$.ids = NULL;
		ids__free($1.ids);
		ids__free($3.ids);
		ids__free($5.ids);
	} else {
		/*
		 * Value is either the LHS or RHS and we need the IF expression
		 * to compute it.
		 */
		$$ = union_expr($1, union_expr($3, $5));
	}
}
| expr
;

expr: NUMBER
{
	$$.val = $1;
	$$.ids = NULL;
}
| ID				{ $$ = handle_id(ctx, $1, compute_ids, /*source_count=*/false); }
| SOURCE_COUNT '(' ID ')'	{ $$ = handle_id(ctx, $3, compute_ids, /*source_count=*/true); }
| HAS_EVENT '(' ID ')'
{
	$$.val = expr__has_event(ctx, compute_ids, $3);
	$$.ids = NULL;
	free($3);
}
| STRCMP_CPUID_STR '(' ID ')'
{
	$$.val = expr__strcmp_cpuid_str(ctx, compute_ids, $3);
	$$.ids = NULL;
	free($3);
}
| expr '|' expr
{
	if (is_const($1.val) && is_const($3.val)) {
		assert($1.ids == NULL);
		assert($3.ids == NULL);
		$$.ids = NULL;
		$$.val = (fpclassify($1.val) == FP_ZERO && fpclassify($3.val) == FP_ZERO) ? 0 : 1;
	} else if (is_const($1.val)) {
		assert($1.ids == NULL);
		if (fpclassify($1.val) == FP_ZERO) {
			$$ = $3;
		} else {
			$$.val = 1;
			$$.ids = NULL;
			ids__free($3.ids);
		}
	} else if (is_const($3.val)) {
		assert($3.ids == NULL);
		if (fpclassify($3.val) == FP_ZERO) {
			$$ = $1;
		} else {
			$$.val = 1;
			$$.ids = NULL;
			ids__free($1.ids);
		}
	} else {
		$$ = union_expr($1, $3);
	}
}
| expr '&' expr
{
	if (is_const($1.val) && is_const($3.val)) {
		assert($1.ids == NULL);
		assert($3.ids == NULL);
		$$.val = (fpclassify($1.val) != FP_ZERO && fpclassify($3.val) != FP_ZERO) ? 1 : 0;
		$$.ids = NULL;
	} else if (is_const($1.val)) {
		assert($1.ids == NULL);
		if (fpclassify($1.val) != FP_ZERO) {
			$$ = $3;
		} else {
			$$.val = 0;
			$$.ids = NULL;
			ids__free($3.ids);
		}
	} else if (is_const($3.val)) {
		assert($3.ids == NULL);
		if (fpclassify($3.val) != FP_ZERO) {
			$$ = $1;
		} else {
			$$.val = 0;
			$$.ids = NULL;
			ids__free($1.ids);
		}
	} else {
		$$ = union_expr($1, $3);
	}
}
| expr '^' expr
{
	if (is_const($1.val) && is_const($3.val)) {
		assert($1.ids == NULL);
		assert($3.ids == NULL);
		$$.val = (fpclassify($1.val) == FP_ZERO) != (fpclassify($3.val) == FP_ZERO) ? 1 : 0;
		$$.ids = NULL;
	} else {
		$$ = union_expr($1, $3);
	}
}
| expr '<' expr { BINARY_OP($$, <, $1, $3); }
| expr '>' expr { BINARY_OP($$, >, $1, $3); }
| expr '+' expr { BINARY_OP($$, +, $1, $3); }
| expr '-' expr { BINARY_OP($$, -, $1, $3); }
| expr '*' expr { BINARY_OP($$, *, $1, $3); }
| expr '/' expr
{
	if (fpclassify($3.val) == FP_ZERO) {
		pr_debug("division by zero\n");
		assert($3.ids == NULL);
		if (compute_ids)
			ids__free($1.ids);
		$$.val = NAN;
		$$.ids = NULL;
	} else if (!compute_ids || (is_const($1.val) && is_const($3.val))) {
		assert($1.ids == NULL);
		assert($3.ids == NULL);
		$$.val = $1.val / $3.val;
		$$.ids = NULL;
	} else {
		/* LHS and/or RHS need computing from event IDs so union. */
		$$ = union_expr($1, $3);
	}
}
| expr '%' expr
{
	if (fpclassify($3.val) == FP_ZERO) {
		pr_debug("division by zero\n");
		YYABORT;
	} else if (!compute_ids || (is_const($1.val) && is_const($3.val))) {
		assert($1.ids == NULL);
		assert($3.ids == NULL);
		$$.val = (long)$1.val % (long)$3.val;
		$$.ids = NULL;
	} else {
		/* LHS and/or RHS need computing from event IDs so union. */
		$$ = union_expr($1, $3);
	}
}
| D_RATIO '(' expr ',' expr ')'
{
	if (fpclassify($5.val) == FP_ZERO) {
		/*
		 * Division by constant zero always yields zero and no events
		 * are necessary.
		 */
		assert($5.ids == NULL);
		$$.val = 0.0;
		$$.ids = NULL;
		ids__free($3.ids);
	} else if (!compute_ids || (is_const($3.val) && is_const($5.val))) {
		assert($3.ids == NULL);
		assert($5.ids == NULL);
		$$.val = $3.val / $5.val;
		$$.ids = NULL;
	} else {
		/* LHS and/or RHS need computing from event IDs so union. */
		$$ = union_expr($3, $5);
	}
}
| '-' expr %prec NEG
{
	$$.val = -$2.val;
	$$.ids = $2.ids;
}
| '(' if_expr ')'
{
	$$ = $2;
}
| MIN '(' expr ',' expr ')'
{
	if (!compute_ids) {
		$$.val = $3.val < $5.val ? $3.val : $5.val;
		$$.ids = NULL;
	} else {
		$$ = union_expr($3, $5);
	}
}
| MAX '(' expr ',' expr ')'
{
	if (!compute_ids) {
		$$.val = $3.val > $5.val ? $3.val : $5.val;
		$$.ids = NULL;
	} else {
		$$ = union_expr($3, $5);
	}
}
| LITERAL
{
	$$.val = $1;
	$$.ids = NULL;
}
;

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