0001 /* Simple expression parser */
0002 %{
0003 #define YYDEBUG 1
0004 #include <assert.h>
0005 #include <math.h>
0006 #include <stdlib.h>
0007 #include "util/debug.h"
0008 #define IN_EXPR_Y 1
0009 #include "expr.h"
0010 %}
0011
0012 %define api.pure full
0013
0014 %parse-param { double *final_val }
0015 %parse-param { struct expr_parse_ctx *ctx }
0016 %parse-param { bool compute_ids }
0017 %parse-param {void *scanner}
0018 %lex-param {void* scanner}
0019
0020 %union {
0021 double num;
0022 char *str;
0023 struct ids {
0024 /*
0025 * When creating ids, holds the working set of event ids. NULL
0026 * implies the set is empty.
0027 */
0028 struct hashmap *ids;
0029 /*
0030 * The metric value. When not creating ids this is the value
0031 * read from a counter, a constant or some computed value. When
0032 * creating ids the value is either a constant or BOTTOM. NAN is
0033 * used as the special BOTTOM value, representing a "set of all
0034 * values" case.
0035 */
0036 double val;
0037 } ids;
0038 }
0039
0040 %token ID NUMBER MIN MAX IF ELSE LITERAL D_RATIO SOURCE_COUNT EXPR_ERROR
0041 %left MIN MAX IF
0042 %left '|'
0043 %left '^'
0044 %left '&'
0045 %left '<' '>'
0046 %left '-' '+'
0047 %left '*' '/' '%'
0048 %left NEG NOT
0049 %type <num> NUMBER LITERAL
0050 %type <str> ID
0051 %destructor { free ($$); } <str>
0052 %type <ids> expr if_expr
0053 %destructor { ids__free($$.ids); } <ids>
0054
0055 %{
0056 static void expr_error(double *final_val __maybe_unused,
0057 struct expr_parse_ctx *ctx __maybe_unused,
0058 bool compute_ids __maybe_unused,
0059 void *scanner,
0060 const char *s)
0061 {
0062 pr_debug("%s\n", s);
0063 }
0064
0065 /*
0066 * During compute ids, the special "bottom" value uses NAN to represent the set
0067 * of all values. NAN is selected as it isn't a useful constant value.
0068 */
0069 #define BOTTOM NAN
0070
0071 /* During computing ids, does val represent a constant (non-BOTTOM) value? */
0072 static bool is_const(double val)
0073 {
0074 return isfinite(val);
0075 }
0076
0077 static struct ids union_expr(struct ids ids1, struct ids ids2)
0078 {
0079 struct ids result = {
0080 .val = BOTTOM,
0081 .ids = ids__union(ids1.ids, ids2.ids),
0082 };
0083 return result;
0084 }
0085
0086 static struct ids handle_id(struct expr_parse_ctx *ctx, char *id,
0087 bool compute_ids, bool source_count)
0088 {
0089 struct ids result;
0090
0091 if (!compute_ids) {
0092 /*
0093 * Compute the event's value from ID. If the ID isn't known then
0094 * it isn't used to compute the formula so set to NAN.
0095 */
0096 struct expr_id_data *data;
0097
0098 result.val = NAN;
0099 if (expr__resolve_id(ctx, id, &data) == 0) {
0100 result.val = source_count
0101 ? expr_id_data__source_count(data)
0102 : expr_id_data__value(data);
0103 }
0104 result.ids = NULL;
0105 free(id);
0106 } else {
0107 /*
0108 * Set the value to BOTTOM to show that any value is possible
0109 * when the event is computed. Create a set of just the ID.
0110 */
0111 result.val = BOTTOM;
0112 result.ids = ids__new();
0113 if (!result.ids || ids__insert(result.ids, id)) {
0114 pr_err("Error creating IDs for '%s'", id);
0115 free(id);
0116 }
0117 }
0118 return result;
0119 }
0120
0121 /*
0122 * If we're not computing ids or $1 and $3 are constants, compute the new
0123 * constant value using OP. Its invariant that there are no ids. If computing
0124 * ids for non-constants union the set of IDs that must be computed.
0125 */
0126 #define BINARY_LONG_OP(RESULT, OP, LHS, RHS) \
0127 if (!compute_ids || (is_const(LHS.val) && is_const(RHS.val))) { \
0128 assert(LHS.ids == NULL); \
0129 assert(RHS.ids == NULL); \
0130 RESULT.val = (long)LHS.val OP (long)RHS.val; \
0131 RESULT.ids = NULL; \
0132 } else { \
0133 RESULT = union_expr(LHS, RHS); \
0134 }
0135
0136 #define BINARY_OP(RESULT, OP, LHS, RHS) \
0137 if (!compute_ids || (is_const(LHS.val) && is_const(RHS.val))) { \
0138 assert(LHS.ids == NULL); \
0139 assert(RHS.ids == NULL); \
0140 RESULT.val = LHS.val OP RHS.val; \
0141 RESULT.ids = NULL; \
0142 } else { \
0143 RESULT = union_expr(LHS, RHS); \
0144 }
0145
0146 %}
0147 %%
0148
0149 start: if_expr
0150 {
0151 if (compute_ids)
0152 ctx->ids = ids__union($1.ids, ctx->ids);
0153
0154 if (final_val)
0155 *final_val = $1.val;
0156 }
0157 ;
0158
0159 if_expr: expr IF expr ELSE expr
0160 {
0161 if (fpclassify($3.val) == FP_ZERO) {
0162 /*
0163 * The IF expression evaluated to 0 so treat as false, take the
0164 * ELSE and discard everything else.
0165 */
0166 $$.val = $5.val;
0167 $$.ids = $5.ids;
0168 ids__free($1.ids);
0169 ids__free($3.ids);
0170 } else if (!compute_ids || is_const($3.val)) {
0171 /*
0172 * If ids aren't computed then treat the expression as true. If
0173 * ids are being computed and the IF expr is a non-zero
0174 * constant, then also evaluate the true case.
0175 */
0176 $$.val = $1.val;
0177 $$.ids = $1.ids;
0178 ids__free($3.ids);
0179 ids__free($5.ids);
0180 } else if ($1.val == $5.val) {
0181 /*
0182 * LHS == RHS, so both are an identical constant. No need to
0183 * evaluate any events.
0184 */
0185 $$.val = $1.val;
0186 $$.ids = NULL;
0187 ids__free($1.ids);
0188 ids__free($3.ids);
0189 ids__free($5.ids);
0190 } else {
0191 /*
0192 * Value is either the LHS or RHS and we need the IF expression
0193 * to compute it.
0194 */
0195 $$ = union_expr($1, union_expr($3, $5));
0196 }
0197 }
0198 | expr
0199 ;
0200
0201 expr: NUMBER
0202 {
0203 $$.val = $1;
0204 $$.ids = NULL;
0205 }
0206 | ID { $$ = handle_id(ctx, $1, compute_ids, /*source_count=*/false); }
0207 | SOURCE_COUNT '(' ID ')' { $$ = handle_id(ctx, $3, compute_ids, /*source_count=*/true); }
0208 | expr '|' expr { BINARY_LONG_OP($$, |, $1, $3); }
0209 | expr '&' expr { BINARY_LONG_OP($$, &, $1, $3); }
0210 | expr '^' expr { BINARY_LONG_OP($$, ^, $1, $3); }
0211 | expr '<' expr { BINARY_OP($$, <, $1, $3); }
0212 | expr '>' expr { BINARY_OP($$, >, $1, $3); }
0213 | expr '+' expr { BINARY_OP($$, +, $1, $3); }
0214 | expr '-' expr { BINARY_OP($$, -, $1, $3); }
0215 | expr '*' expr { BINARY_OP($$, *, $1, $3); }
0216 | expr '/' expr
0217 {
0218 if (fpclassify($3.val) == FP_ZERO) {
0219 pr_debug("division by zero\n");
0220 YYABORT;
0221 } else if (!compute_ids || (is_const($1.val) && is_const($3.val))) {
0222 assert($1.ids == NULL);
0223 assert($3.ids == NULL);
0224 $$.val = $1.val / $3.val;
0225 $$.ids = NULL;
0226 } else {
0227 /* LHS and/or RHS need computing from event IDs so union. */
0228 $$ = union_expr($1, $3);
0229 }
0230 }
0231 | expr '%' expr
0232 {
0233 if (fpclassify($3.val) == FP_ZERO) {
0234 pr_debug("division by zero\n");
0235 YYABORT;
0236 } else if (!compute_ids || (is_const($1.val) && is_const($3.val))) {
0237 assert($1.ids == NULL);
0238 assert($3.ids == NULL);
0239 $$.val = (long)$1.val % (long)$3.val;
0240 $$.ids = NULL;
0241 } else {
0242 /* LHS and/or RHS need computing from event IDs so union. */
0243 $$ = union_expr($1, $3);
0244 }
0245 }
0246 | D_RATIO '(' expr ',' expr ')'
0247 {
0248 if (fpclassify($5.val) == FP_ZERO) {
0249 /*
0250 * Division by constant zero always yields zero and no events
0251 * are necessary.
0252 */
0253 assert($5.ids == NULL);
0254 $$.val = 0.0;
0255 $$.ids = NULL;
0256 ids__free($3.ids);
0257 } else if (!compute_ids || (is_const($3.val) && is_const($5.val))) {
0258 assert($3.ids == NULL);
0259 assert($5.ids == NULL);
0260 $$.val = $3.val / $5.val;
0261 $$.ids = NULL;
0262 } else {
0263 /* LHS and/or RHS need computing from event IDs so union. */
0264 $$ = union_expr($3, $5);
0265 }
0266 }
0267 | '-' expr %prec NEG
0268 {
0269 $$.val = -$2.val;
0270 $$.ids = $2.ids;
0271 }
0272 | '(' if_expr ')'
0273 {
0274 $$ = $2;
0275 }
0276 | MIN '(' expr ',' expr ')'
0277 {
0278 if (!compute_ids) {
0279 $$.val = $3.val < $5.val ? $3.val : $5.val;
0280 $$.ids = NULL;
0281 } else {
0282 $$ = union_expr($3, $5);
0283 }
0284 }
0285 | MAX '(' expr ',' expr ')'
0286 {
0287 if (!compute_ids) {
0288 $$.val = $3.val > $5.val ? $3.val : $5.val;
0289 $$.ids = NULL;
0290 } else {
0291 $$ = union_expr($3, $5);
0292 }
0293 }
0294 | LITERAL
0295 {
0296 $$.val = $1;
0297 $$.ids = NULL;
0298 }
0299 ;
0300
0301 %%
